Optimization of network mesh topologies and link capacities for congestion relief

Abstract

Network design problems usually include the selection of nodes and arcs from lists of potential sets to accomplish certain desirable properties. Foremost is often the capability to accommodate the flow demands at a reasonable cost. In many applications it is also imperative to have built-in reliability or survivability of the network. Delays of traffic are undesirable since it affects Quality of Service (QoS) to clients of the network. It is seldom possible to start a design for a new network and have the luxury of designing topology as well as the optimal flow(routing). In this dissertation we consider the construction of a network optimization system. This system may be used in the planning of network mesh topologies and link capacities to avoid costly designs and congestion or to give advice on congestion relief in existing networks. This is done by selecting parts of a network that may be prone to congestion and model this part by using mixed integer programming techniques. These models are then solved by using a software product called CPLEX and various facilities are built into the decision support system to allow the decision maker to experiment with some topological and flow requirement changes.