Valid inequalities for a shortest-path routing optimization problem

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.

• Author: Artur Tomaszewski; Michal Pioro; Mateusz Dzida; Mariusz Mycek; Michal Zagozdzon
• Department/s: Department of Electrical and Information Technology
• Publishing year: 2007
• Language: English
• Links: http://www.poms.ucl.ac.be/inoc2007/Papers/author.95/paper/paper.95.pdf
• Document type: Conference paper
• Topic: Electrical Engineering, Electronic Engineering, Information Engineering
• Keywords: 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