Three methods for optimizing singleshortest path routing
(2008) The 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008) In [Host publication title missing] p.6168 Abstract
 Intradomain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting leastcost paths determine routes between pairs of routers. If several such equalcost paths exist between a pair of routers, it may not be clear which of them is actually used to route traffic. This makes it difficult to predict the network traffic flow distribution. Therefore, the selected link costs should assure uniqueness of the shortest paths. On top of that, the link costs can be optimized with respect to some traffic objective. The resulting optimization problem, referred to as SSPP, turns out to be NPhard. SSPP can be formulated as a mixedinteger programming problem and, as such, solved... (More)
 Intradomain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting leastcost paths determine routes between pairs of routers. If several such equalcost paths exist between a pair of routers, it may not be clear which of them is actually used to route traffic. This makes it difficult to predict the network traffic flow distribution. Therefore, the selected link costs should assure uniqueness of the shortest paths. On top of that, the link costs can be optimized with respect to some traffic objective. The resulting optimization problem, referred to as SSPP, turns out to be NPhard. SSPP can be formulated as a mixedinteger programming problem and, as such, solved with branchand bound (B&B). In this paper, we consider three methods for SSPP. Two of them are exact methods based on B&B, namely branch andcut and constraint programming. Since the exact solutions of SSPP may require excessive computation time and may not always be effective when applied to practical networks, we also study a fast heuristic method. Finally, in a numerical study, we compare the effectiveness of the three approaches. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1366161
 author
 Dzida, M; Zagozdzon, M; Zotkiewicz, M; Wallander, Mats Petter ^{LU} ; Pioro, Michal ^{LU} ; Duelli, M and Menth, M
 organization
 publishing date
 2008
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 [Host publication title missing]
 pages
 61  68
 conference name
 The 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008)
 external identifiers

 scopus:51149109344
 ISBN
 1424417848
 DOI
 10.1109/NGI.2008.15
 language
 English
 LU publication?
 yes
 id
 5f8767e0fbee4b1ca126dd5f88329ed6 (old id 1366161)
 date added to LUP
 20090327 12:25:29
 date last changed
 20170604 04:45:56
@inproceedings{5f8767e0fbee4b1ca126dd5f88329ed6, abstract = {Intradomain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting leastcost paths determine routes between pairs of routers. If several such equalcost paths exist between a pair of routers, it may not be clear which of them is actually used to route traffic. This makes it difficult to predict the network traffic flow distribution. Therefore, the selected link costs should assure uniqueness of the shortest paths. On top of that, the link costs can be optimized with respect to some traffic objective. The resulting optimization problem, referred to as SSPP, turns out to be NPhard. SSPP can be formulated as a mixedinteger programming problem and, as such, solved with branchand bound (B&B). In this paper, we consider three methods for SSPP. Two of them are exact methods based on B&B, namely branch andcut and constraint programming. Since the exact solutions of SSPP may require excessive computation time and may not always be effective when applied to practical networks, we also study a fast heuristic method. Finally, in a numerical study, we compare the effectiveness of the three approaches.}, author = {Dzida, M and Zagozdzon, M and Zotkiewicz, M and Wallander, Mats Petter and Pioro, Michal and Duelli, M and Menth, M}, booktitle = {[Host publication title missing]}, isbn = {1424417848}, language = {eng}, pages = {6168}, title = {Three methods for optimizing singleshortest path routing}, url = {http://dx.doi.org/10.1109/NGI.2008.15}, year = {2008}, }