//img.uscri.be/pth/78f2202e30cb3625d525c4d6a0b877014aaaea7f
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

286 pages
Routing and Capacity Optimizationfor IP Networksvorgelegt vonDipl.-Math.oec. Andreas BleyDessauVon der Fakultat II — Mathematik und Naturwissenschaften¨der Technischen Universita¨t Berlinzur Erlangung des akademischen GradesDoktor der NaturwissenschaftenDr. rer. nat.genehmigte DissertationPromotionsausschuss:Vorsitzender: Prof. Dr. Volker Mehrmann1. Berichter: Prof. Dr. Dr. h.c. Martin Grotschel¨2. Berichter: Prof. Dr. Daniel BienstockTag der Wissenschaftlichen Aussprache: 7. Februar 2007Berlin 2007D83iAbstractThis 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 theInternet. With these routing protocols, all end-to-end data streams arerouted along shortest paths with respect to a metric of link lengths. Thenetworkadministratorcanconfiguretheroutingonlybymodifyingthismet-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 canbe controlled only indirectly via the routing metric and that all routingpaths depend on the same routing metric. This leads to rather compli-cated and subtle interdependencies among the paths that comprise a validrouting.
Voir plus Voir moins

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 Functionality . . . . . . . . . . . . . . 22
3.3 Shortest Path Routing . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Optimization Problems in IP networks . . . . . . . . . . . . . 28
3.5 Mathematical Model . . . . . . . . . . . . . . . . . . . . . . . 31
I Metrics and Routing Paths 37
4 The Inverse Unique Shortest Paths Problem 39
4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 Finding Real-Valued Lengths . . . . . . . . . . . . . . . . . . 44
4.4 Inapproximability Results for Integer Lengths . . . . . . . . . 47
4.5 An LP-Rounding Algorithm . . . . . . . . . . . . . . . . . . . 56
4.6 Unique Shortest Path Forwardings . . . . . . . . . . . . . . . 60
4.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . 66
5 Unique Shortest Path Systems 69
5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
viiviii CONTENTS
5.2 Basic Definitions and Observations . . . . . . . . . . . . . . . 71
5.3 Properties of Unique Shortest Path Systems . . . . . . . . . . 75
5.4 Finding Irreducible Non-Unique Shortest Path Systems . . . 81
5.5 Finding Maximum Unique Shortest Path Systems . . . . . . . 90
5.6 Undirected Unique Shortest Paths Systems . . . . . . . . . . 96
5.7 Unique Shortest Path Forwardings . . . . . . . . . . . . . . . 103
II Hardness and Approximability 111
6 Approximability of Unsplittable Shortest Path Routing 113
6.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2 Unsplittable Shortest Path Routing Problems . . . . . . . . . 117
6.3 Relation to Other Routing Schemes . . . . . . . . . . . . . . . 120
6.4 Inapproximability Results . . . . . . . . . . . . . . . . . . . . 124
6.5 General Approximation Algorithms . . . . . . . . . . . . . . . 137
6.6 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . 153
III An Integer Programming Solution Approach 155
7 Integer Linear Programming Models 157
7.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.2 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.3 Path Routing Formulations . . . . . . . . . . . . . . . . . . . 164
7.4 Arc Routing Formulations . . . . . . . . . . . . . . . . . . . . 167
7.5 Solving the LP Relaxations . . . . . . . . . . . . . . . . . . . 174
7.6 Strength of the LP Relaxations . . . . . . . . . . . . . . . . . 186
8 Valid Inequalities 193
8.1 Routing Inequalities . . . . . . . . . . . . . . . . . . . . . . . 194
8.2 Superadditive Metric Inequalities . . . . . . . . . . . . . . . . 201
8.3 Precedence Constrained Knapsack Inequalities . . . . . . . . 209
9 Implementation and Computational Results 221
9.1 Modeling the Real Problem . . . . . . . . . . . . . . . . . . . 222
9.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 237
9.3 Computational Results . . . . . . . . . . . . . . . . . . . . . . 247
9.4 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 259
Bibliography 261