Routing and capacity optimization for IP networks [Elektronische Ressource] / vorgelegt von Andreas Bley

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2007
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Routing and Capacity Optimization
for IP Networks
vorgelegt von
Dipl.-Math.oec. Andreas Bley
Dessau
Von der Fakultat II — Mathematik und Naturwissenschaften¨
der Technischen Universita¨t Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
Dr. rer. nat.
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Volker Mehrmann
1. Berichter: Prof. Dr. Dr. h.c. Martin Grotschel¨
2. Berichter: Prof. Dr. Daniel Bienstock
Tag der Wissenschaftlichen Aussprache: 7. Februar 2007
Berlin 2007
D83i
Abstract
This thesis is concerned with dimensioning and routing optimization prob-
lems for communication networks that employ a shortest path routing pro-
tocol such as OSPF, IS-IS, or RIP. These protocols are widely used in the
Internet. With these routing protocols, all end-to-end data streams are
routed along shortest paths with respect to a metric of link lengths. The
networkadministratorcanconfiguretheroutingonlybymodifyingthismet-
ric. Inthis thesis weconsider theunsplittableshortest pathroutingvariant,
where each communication demand must be sent unsplit through the net-
work. This requires that all shortest paths are uniquely determined.
The major difficulties in planning such networks are that the routing can
be controlled only indirectly via the routing metric and that all routing
paths depend on the same routing metric. This leads to rather compli-
cated and subtle interdependencies among the paths that comprise a valid
routing. In contrast to most other routing schemes, the paths for different
communication demands cannot be configured independent of each other.
PartIofthethesisisdedicatedtotherelationbetweenpathsetsandrout-
ingmetrics and to the combinatorial properties of those path sets that com-
prise a valid unsplittable shortest path routing. Besides reviewing known
approachestofindacompatiblemetricforagiven pathset (or toprovethat
none exists) and discussingsome properties of valid path sets, we show that
the problem of finding a compatible metric with integer lengths as small as
possible and the problem of finding a smallest possible conflict in the given
path set are both NP-hard to approximate within a constant factor.
InPart II of thethesis we discussthe relation between unsplittableshort-
est path routing and several other routing schemes and we analyze the
computational complexity of three basic unsplittable shortest path routing
problems. We show that the lowest congestion that can be obtained with
unsplittable shortest path routing may significantly exceed that achievable
with other routing paradigms and we prove several non-approximability re-
sults for unsplittable shortest path routing problems that are stronger than
those for the corresponding unsplittable flow problems. In addition, we
derive various polynomial time approximation algorithms for general and
special cases of these problems.
In Part III of the thesis we finally develop an integer linear programming
approach to solve these and more realistic unsplittable shortest path rout-
ing problems to optimality. We present alternative formulations for these
problems, discuss their strength and computational complexity, and show
how to derive strong valid inequalities. Eventually, we describe our im-
plementation of this solution approach and report on the numerical results
obtained for real-world problems that came up in the planning the Ger-
man National Research and Education Networks G-WiN and X-WiN and
for several benchmark instances.iiiii
Zusammenfassung
Die Arbeit befasst sich mit der Kapazit¨ats- und Routenplanung fu¨r Kom-
munikationsnetze,dieeinkurzeste-WegeRoutingprotokollverwenden. Diese¨
Art von Protokollen ist im Internet weit verbreitet. Bei diesen Routingver-
fahren wird fur jede Verbindung im Netz ein Langenwert festgelegt, diese¨ ¨
L¨angen formen die sogenannte Routingmetrik. Die Routingwege der Kom-
munikationsbedarfesinddanndiejeweiligenkurzestenWegebezuglichdieser¨ ¨
Metrik. BeiderinderArbeituntersuchtenVariantedieserRoutingprotokolle
wird zusatzlich verlangt, dass es je Kommunikationsbedarf genau einen ein-¨
deutigen kurzesten Weg gibt.¨
Die Schwierigkeit bei der Planung solcher Netze besteht darin, dass sich
dieRoutingwege einerseits nurindirektuberdieRoutingmetrik beeinflussen¨
lassen,andererseitsaberalleRoutingwegevondergleichenMetrikabh¨angen.
DadurchkonnendieWegederverschiedenenKommunikationsanforderungen¨
nicht wie bei anderen Routingverfahren unabha¨ngig voneinander gewa¨hlt
werden.
ImerstemTeilderArbeitwerdenderZusammenhangzwischengegebenen
WegesystemenundkompatiblenRoutingmetrikensowiedieBeziehungender
Wegeeineszula¨ssigen eindeutige-ku¨rzeste-Wege-Routings untereinanderun-
tersucht. Dabei wird unter Anderem gezeigt, dass es NP-schwer ist, eine
kompatible Metrik mit kleinstmoglichen Routinglangen zu einem gegebe-¨ ¨
nen Wegesystem zu finden. Es wird auch bewiesen, dass das Finden eines
kleinstmoglichen Konfliktes in einem gegebenen Wegesystem, zu dem keine¨
kompatible Metrik existiert, NP-schwer ist.
Im zweiten Teil der Arbeit wird die Approximierbarkeit von drei grundle-
gendenNetz- undRoutenplanungsproblemenmiteindeutige-ku¨rzeste-Wege-
Routing untersucht. Fur diese Problemewerden starkere Nichtapproximier-¨ ¨
barkeitsresultate als fu¨r die entsprechenden Einwege-Routing Probleme be-
wiesen und es werden verschiedene polynomiale Approximationsverfahren
fu¨r allgemeine und Spezialfa¨lle entworfen. Ausserdem wird die Beziehung
zwischen eindeutige-ku¨rzeste-Wege-Routing und anderen Routingverfahren
diskutiert.
Im dritten und letzten Teil der Arbeit wird ein (gemischt-) ganzzahliger
LosungsansatzfurPlanungsproblememiteindeutige-kurzeste-Wege-Routing¨ ¨ ¨
vorgestellt. Fu¨r die im zweiten Teil diskutierten grundlegenden Netz- und
Routenplanungsprobleme werden verschiedene (gemischt-) ganzzahlige lin-
eare Modelle vorgestellt und es wird deren Lo¨sbarkeit und die Sta¨rke ihrer
LP Relaxierungen untersucht. Es wird auch gezeigt, wie sich starke gultig¨
Ungleichungen ausdenindiesenModellen enthalten Substrukturenableiten
lassen. SchließlichwerdenamEndederArbeitdieSoftware-Implementierung
diesesLosungsverfahrensfureinepraxisrelevanteVerallgemeinerungderPla-¨ ¨
nungsproblemesowiediedamit erzielten numerischenErgebnissevorgestellt
und diskutiert.ivv
Acknowledgments
Thiswork couldnot have been writtenwithout thehelp andencouragement
of many people. I am extremely fortunate to be surrounded by a truly
wonderful ensemble of fellow researchers and friends.
The greatest thanks goes to my supervisor Prof. Martin Grotschel for¨
giving me the chance to work on this very interesting topic. His steady
supportandmotivation gave methefreedomandthetimeIneededtofinish
my research.
My colleagues and the staff at the Konrad–Zuse–Zentrum fur Informa-¨
tionstechnik Berlin (ZIB) have provided a supportive and friendly working
environmentandIwishtoexpressmygratitudetoallofthem. Iamparticu-
larly grateful to Roland Wessaly, Adrian Zymolka, Arie M.C.A. Koster, An-¨
dreas Eisenbla¨tter, Sebastian Orlowski, and Volker Kaibel for proof-reading
several parts of the manuscript. Their feedback helped me to put things
into the right perspective and made this thesis immeasurably better. Spe-
cial thanks also go the entire Discnet team at ZIB and at Atesio GmbH
for the effective cooperation in software development.
I would also like to thank my fellow researchers and friends at the Tech-
nical University Berlin, especially those in the Combinatorial Optimization
and Graph Algorithms group, for lots of interesting mathematical seminars
and discussions and many exciting basketball games.
This thesis was motivated by the problems arising in the planning and
operation of the German national research and education network operated
by the DFN-Verein. I have to thank all the people at the DFN-Verein and
in particular Marcus Pattloch for an excellent cooperation in this research
project. They ensured that the mathematics developed in line with the
practical needs and they provided access to the real problems.
And last, but certainly not least, a very big thankyou to my family and
all my friends for their understanding and encouragement throughout the
course of this PhD.viContents
1 Introduction 1
1.1 Focus of this Thesis . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contributions of this Thesis . . . . . . . . . . . . . . . . . . . 3
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Mathematical Preliminaries 7
2.1 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Linear and Integer Linear Programming . . . . . . . . . . . . 8
2.3 Graphs and Hypergraphs . . . . . . . . . . . . . . . . . . . . 10
2.4 Walks, Paths, and Connectivity . . . . . . . . . . . . . . . . . 11
2.5 Independence systems and Matroids . . . . . . . . . . . . . . 13
2.6 Computational Complexity and Approximation . . . . . . . . 14
3 Internet Routing and Planning Problems 21
3.1 History of the Internet . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Architecture and Basic Functionalit