Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Valid inequalities for a shortest-path routing optimization problem

In English

Författare

  • Artur Tomaszewski
  • Michal Pioro
  • Mateusz Dzida
  • Mariusz Mycek
  • Michal Zagozdzon

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.

Publiceringsår

2007

Språk

Engelska

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