Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Valid inequalities for a shortest-path routing optimization problem

Publiceringsår: 2007
Språk: Engelska
Sidor: 10
Dokumenttyp: Konferensbidrag


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.



  • Electrical Engineering, Electronic Engineering, Information Engineering
  • IP networks
  • OSPF routing optimization
  • ECMP flow
  • Branch-and-cut


International Network Optimization Conference INOC 2007
Spa, Belgium

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen