Abstract
In the Internet’s autonomous systems packets are routed on shortest paths to their destinations. A related problem is how to find an admissible traffic routing configuration using paths that can be generated by a system of weights assigned to IP links. This problem is NP-hard. It can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective cuts (valid inequalities) can be derived. In this paper we discuss admissibility of shortest-path routing configurations represented by binary variables specifying whether or not a particular link is on a shortest path to a particular destination. We present a linear programming problem for testing routing admissibility and derive solutions of this problem which characterize non-admissible routing configurations.
| Original language | English |
|---|---|
| Number of pages | 7 |
| Publication status | Published - 2007 |
| Event | International Network Optimization Conference INOC 2007 - Spa, Belgium Duration: 2007 Apr 22 → 2007 Apr 25 |
Conference
| Conference | International Network Optimization Conference INOC 2007 |
|---|---|
| Country/Territory | Belgium |
| City | Spa |
| Period | 2007/04/22 → 2007/04/25 |
Subject classification (UKÄ)
- Electrical Engineering, Electronic Engineering, Information Engineering
Free keywords
- IP networks
- OSPF routing
- ECMP flow
- branch-and-cut