Change search
ReferencesLink to record
Permanent link

Direct link
Inverse Shortest Path Routing Problems in the Design of IP Networks
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2010 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

This thesis is concerned with problems related to shortest pathrouting (SPR) in Internet protocol (IP) networks. In IP routing, alldata traffic is routed in accordance with an SPR protocol, e.g. OSPF.That is, the routing paths are shortest paths w.r.t. some artificialmetric. This implies that the majority of the Internet traffic isdirected by SPR. Since the Internet is steadily growing, efficientutilization of its resources is of major importance. In theoperational planning phase the objective is to utilize the availableresources as efficiently as possible without changing the actualdesign. That is, only by re-configuration of the routing. This isreferred to as traffic engineering (TE). In this thesis, TE in IPnetworks and related problems are approached by integer linearprogramming.

Most TE problems are closely related to multicommodity routingproblems and they are regularly solved by integer programmingtechniques. However, TE in IP networks has not been studied as much,and is in fact a lot harder than ordinary TE problems without IProuting since the complicating shortest path aspect has to be takeninto account. In a TE problem in an IP network the routing isperformed in accordance with an SPR protocol that depends on a metric,the so called set of administrative weights. The major differencebetween ordinary TE problems and TE in IP networks is that all routingpaths must be simultaneously realizable as shortest paths w.r.t. thismetric. This restriction implies that the set of feasible routingpatterns is significantly reduced and that the only means available toadjust and control the routing is indirectly, via the administrativeweights.

A constraint generation method for solving TE problems in IP networksis outlined in this thesis. Given an "original" TE problem, the ideais to iteratively generate and augment valid inequalities that handlethe SPR aspect of IP networks. These valid inequalities are derived byanalyzing the inverse SPR problem. The inverse SPR problem is todecide if a set of tentative routing patterns is simultaneouslyrealizable as shortest paths w.r.t. some metric. When this is not thecase, an SPR conflict exists which must be prohibited by a validinequality that is then augmented to the original TE problem. Toderive strong valid inequalities that prohibit SPR conflicts, athorough analysis of the inverse SPR problem is first performed. Inthe end, this allows us to draw conclusions for the design problem,which was the initial primary concern.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2010. , 215 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1448
National Category
Computational Mathematics
URN: urn:nbn:se:liu:diva-66378ISBN: 978-91-7393-329-2 (print)OAI: diva2:403478
2010-09-09, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Available from: 2011-03-25 Created: 2011-03-14 Last updated: 2013-08-29Bibliographically approved

Open Access in DiVA

Inverse Shortest Path Routing Problems in the Design of IP Networks(1541 kB)1194 downloads
File information
File name FULLTEXT01.pdfFile size 1541 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Optimization The Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1194 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

Total: 151 hits
ReferencesLink to record
Permanent link

Direct link