Abstract | ||
---|---|---|
Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the
links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their
destination.
In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem,
which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands,
the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion
over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present
the integer and linear programming models used to solve the master and the client problem, and discuss the most important
implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency
of our algorithm.
|
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/s00453-009-9381-5 | European Symposium on Algorithms |
Keywords | DocType | Volume |
ip networks,shortest path,data packet,integer programming algorithm,client problem,resulting routing,data network,administrative routing length,shortest path protocol,minimum congestion unsplittable shortest,shortest path routing · integer programming,routing optimization,unique shortest path,directed graph,integer programming,linear program | Journal | 60 |
Issue | ISSN | Citations |
1 | 0178-4617 | 3 |
PageRank | References | Authors |
0.42 | 17 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andreas Bley | 1 | 189 | 18.40 |