liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Shortest Path Routing Modelling, Infeasibility and Polyhedra
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2012 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The Internet is constantly growing but the available resources, i.e. bandwidth, are limited. Using bandwidth efficiently to provide high quality of service to users is referred to as traffic engineering. This is of utmost importance. Traffic in IP networks is commonly routed along shortest paths with respect to auxiliary link weights, e.g. using the OSPF or IS-IS protocol. Here, shortest path routing is indirectly controlled via the link weights only, and it is therefore crucial to have a profound understanding of the shortest path routing mechanism to solve traffic engineering problems in IP networks. The theoretical aspects of such problems have received little attention.

Traffic engineering in IP networks leads to very difficult optimization problems and the key element in exact methods for such problems is an inverse shortest path routing problem. It is used to answer the fundamental question of whether there exist link weights that reproduce a set of tentative paths. Path sets that cannot be obtained correspond to routing conflicts. Valid inequalities are instrumental to prohibit such routing conflicts.

We analyze the inverse shortest path routing problem thoroughly. We show that the problem is NP-complete, contrary to what is claimed in the literature, and propose a stronger relaxation. Its Farkas system is used to develop a novel and compact formulation based on cycle bases, and to classify and characterize minimal infeasible subsystems. Valid inequalities that prevent routing conflicts are derived and separation algorithms are developed for such inequalities.

We also consider several approaches to modelling traffic engineering problems, especially Dantzig–Wolfe reformulations and extended formulations. We give characterizations of facets for some relaxations of traffic engineering problems.

Our results contribute to the theoretical understanding, modelling and solution of problems related to traffic engineering in IP networks.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2012. , 270 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1486
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-85547ISBN: 978-91-7519-751-7 (print)OAI: oai:DiVA.org:liu-85547DiVA: diva2:571482
Public defence
2012-11-29, Nobel (BL32), Hus B, ingång 23, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2012-11-22 Created: 2012-11-22 Last updated: 2013-09-10Bibliographically approved

Open Access in DiVA

Shortest Path Routing Modelling, Infeasibility and Polyhedra(1484 kB)1179 downloads
File information
File name FULLTEXT01.pdfFile size 1484 kBChecksum SHA-512
d9809aeb1370eac157a06f8babd132f77f4b951d5e562dd075989872e4f78bc2dbc6cedec81fe42d01755050cb74a31c87f6fce920742d07f04277df7977c748
Type fulltextMimetype application/pdf
omslag(81 kB)83 downloads
File information
File name COVER01.pdfFile size 81 kBChecksum SHA-512
1719e95edb90cd459b37eefebe11639ac9f2f4b796583aa40762f0559218b16e4bb552d5e19669d3c01106d820294dab6ad4900a58f9c1662d51e6ea9b05c303
Type coverMimetype application/pdf

Authority records BETA

Call, Mikael

Search in DiVA

By author/editor
Call, Mikael
By organisation
Optimization The Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1179 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 671 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf