Valid inequalities for a shortest-path routing optimization problem
Författare
Summary, in English
In autonomous systems of the Internet packets are routed on shortest paths to their destinations, for example
according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized
on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem
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 present exact and approximate LP- and MIPbased
methods for generating valid inequalities that separate fractional solutions of the basic problem.
Besides, a family of complementary valid inequalities, generated with a shortest-path algorithm, related
to combinatorial properties of feasible traffic routes is introduced to speed up the cut generation process.
Results of a numerical study illustrating computational issues are discussed.
according to the ECMP principle. The problem of finding a feasible traffic routing configuration realized
on paths which can be generated by a system of weights assigned to IP links is NP-hard. This problem
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 present exact and approximate LP- and MIPbased
methods for generating valid inequalities that separate fractional solutions of the basic problem.
Besides, a family of complementary valid inequalities, generated with a shortest-path algorithm, related
to combinatorial properties of feasible traffic routes is introduced to speed up the cut generation process.
Results of a numerical study illustrating computational issues are discussed.
Publiceringsår
2007
Språk
Engelska
Länkar
Dokumenttyp
Konferensbidrag
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Nyckelord
- IP networks
- OSPF routing optimization
- 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