Feasibility issues in shortest-path routing with traffic flow split
Författare
Summary, in English
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.
Publiceringsår
2007
Språk
Engelska
Fulltext
- Available as PDF - 378 kB
- Download statistics
Dokumenttyp
Konferensbidrag
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Nyckelord
- IP networks
- OSPF routing
- ECMP flow
- branch-and-cut
Conference name
International Network Optimization Conference INOC 2007
Conference date
2007-04-22 - 2007-04-25
Conference place
Spa, Belgium
Status
Published