Three methods for optimizing single-shortest path routing
(2008) The 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008) p.61-68- Abstract
- Intra-domain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting least-cost paths determine routes between pairs of routers. If several such equal-cost 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 NP-hard. SSPP can be formulated as a mixed-integer programming problem and, as such, solved... (More)
- Intra-domain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting least-cost paths determine routes between pairs of routers. If several such equal-cost 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 NP-hard. SSPP can be formulated as a mixed-integer programming problem and, as such, solved with branch-and- bound (B&B). In this paper, we consider three methods for SSPP. Two of them are exact methods based on B&B, namely branch- and-cut 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:
https://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
- host publication
- [Host publication title missing]
- pages
- 61 - 68
- conference name
- The 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008)
- conference location
- Cracow, Poland
- conference dates
- 2008-04-28 - 2008-04-30
- external identifiers
-
- scopus:51149109344
- ISBN
- 1-4244-1784-8
- DOI
- 10.1109/NGI.2008.15
- language
- English
- LU publication?
- yes
- id
- 5f8767e0-fbee-4b1c-a126-dd5f88329ed6 (old id 1366161)
- date added to LUP
- 2016-04-04 13:53:19
- date last changed
- 2022-01-30 01:07:15
@inproceedings{5f8767e0-fbee-4b1c-a126-dd5f88329ed6,
abstract = {{Intra-domain routing in IP networks is based on the shortest path principle by assigning administrative weights (costs) to links. The resulting least-cost paths determine routes between pairs of routers. If several such equal-cost 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 NP-hard. SSPP can be formulated as a mixed-integer programming problem and, as such, solved with branch-and- bound (B&B). In this paper, we consider three methods for SSPP. Two of them are exact methods based on B&B, namely branch- and-cut 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 = {{1-4244-1784-8}},
language = {{eng}},
pages = {{61--68}},
title = {{Three methods for optimizing single-shortest path routing}},
url = {{http://dx.doi.org/10.1109/NGI.2008.15}},
doi = {{10.1109/NGI.2008.15}},
year = {{2008}},
}