Meny

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

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

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • IP networks
  • OSPF routing optimization
  • ECMP flow
  • Branch-and-cut

Övriga

International Network Optimization Conference INOC 2007
2007-04-22/2007-04-25
Spa, Belgium
Published
Yes

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