Improving telecommunications network throughput by incremental demand routing

This investigation addresses an important and difficult combinatorial optimization problem in the design and management of telecommunication systems known as the path assignment problem. In this problem, one is given a network with fixed link capacities and a list of point-to-point demands (origin-destination pairs), each with a set of candidate routing paths. A path assignment is said to be feasible if it meets the following two criteria. First, all traffic for a given origin-destination pair must be routed along (assigned to) exactly one of the paths available for that pair. Second, the total volume of traffic routed over any particular link must be within the given capacity limit. Given a network and a path assignment, the problem of interest is to maximize the available bandwidth (throughput) for a new demand. Network managers are concerned with the quality of service provided by their networks, and so they are reluctant to make major changes to an operating network that may inadvertently result in service disruptions for numerous clients simultaneously. Therefore, the objective of this investigation is to develop and test solution procedures that produce a series of throughput-improving modifications to the original path assignment. This allows network managers to implement the improved routing in stages with minimal changes to the overall routing plan between any two consecutive stages. Although the procedure may only reroute a few demands at each stage, the routing after the last stage should be as close as possible to an optimal routing. That is, it must maximize the throughput for the new demand. This investigation took three different approaches: path based models, node-arc models, and min-max path assignment models and all of them will optimize the network throughput. We present integer programming models and associated solution algorithms to maximize the throughput with a sequence of incremental path modifications. The different methodologies in this investigation were implemented with the AMPL modeling language and the CPLEX ILP solver, and tested on a family of five different data sets based on a European network widely studied in the literature. Empirical results show that the incremental approach finds near-optimal results within reasonable limits on CPU time.