Design and optimization of resilient multipath networks [Elektronische Ressource] / Claus Günter Gruber

Informations

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

Extrait

Lehrstuhl fu¨r Kommunikationsnetze
der Technischen Universit¨at Mu¨nchen
Design and Optimization of
Resilient Multipath Networks
Claus Gu¨nter Gruber
Vollst¨andiger Abdruck der von der Fakult¨at fu¨r Elektrotechnik und Informationstechnik
der Technischen Universit¨at Mu¨nchen zur Erlangung des akademischen Grades eines
Doktor–Ingenieurs (Dr.–Ing.)
genehmigten Dissertation.
Vorsitzender:
Univ.–Prof. Dr.–Ing. Ulf Schlichtmann
Pru¨fer der Dissertation:
1. Univ.–Prof. Dr.–Ing. Jo¨rg Ebersp¨acher
2. Univ.–Prof. Dr.–Ing. Ralf Lehnert,
Technische Universita¨t Dresden
DieDissertationwurdeam12.12.2006beiderTechnischenUniversit¨atMu¨ncheneingereicht
unddurchdieFakult¨atfu¨rElektrotechnikundInformationstechnikam22.6.2007angenom-
men.Design and Optimization of
Resilient Multipath Networks
Claus Gu¨nter Gruber
Munich, GermanyTo my parents and my sister.Only if an optimal solution is known,
suboptimal solutions can be accepted.Acknowledgments
ThisthesiswaswrittenduringmyworkasresearcherandteachingassistantattheInstitute
of Communication Networks (LKN) at Munich University of Technology (TUM). A time
I will always remember as a very interesting moment of my life where helpful colleagues
have surrounded me. Many of them became friends.
Foremost, I sincerely would like to thank Prof. Dr.-Ing. J¨org Ebersp¨acher, the insti-
tute’s head and my Ph.D. advisor for his constant support and guidance throughout the
work. While giving considerable advice he gave me the freedom to develop own ideas. He
created an environment where it was a pleasure to conduct research. Furthermore, I would
like to thank Prof. Dr.-Ing. Ralf Lehnert for being second examiner and Prof. Dr.-Ing.
Ulf Schlichtmann for presiding the dissertation committee.
Attheinstitute,mythanksgotomyformercolleagues. Especially, Iwouldliketothank
Dr.-Ing. Dominic Schupke who was the supervisor of my diploma thesis and encouraged
me to proceed the work at the institute. During many hours he was a counterpart for
fruitful technical and not-so-technical discussions. I also had the pleasure to work with
Thomas Schwabe, Matthias Scheffel, Robert Prinz, Dr.-Ing. Achim Autenrieth, Thomas
Fischer,andDr.-Ing. MarieTromparentthatweremembersoftheresearchgroup’Photonic
Networks and Network Resilience Group’ atLKN. This research group provided the forum
formanydiscussionsaboutthefutureofresilientnetworksandtopicsincludedinthisthesis.
A special thanks go to Hans-Martin Zimmermann and Andrea B¨or for the interesting
discussions about mobile networks, e-learning strategies and topics across all layers.
In addition, I would like to express my thanks to Jochen Frings who introduced me to
the world of telecommunication and with whom I co-founded a company. In this respect,
further thanks go to Prof. Dr.-Ing. J¨org Ebersp¨acher, Dr.-Ing. Martin Maier, Maren
Jopen, andStefanThallmaier, who supportedusconsiderably duringthefounding process.
Furthermore, it was a pleasure to work with Dr.-Ing. Joachim Charzinski and all
participants of the research project ’Key Components for the mobile Internet of Next
Generation’ (KING). Additionally, I would like to thank Prof. Dr. Thomas Stidsen at
DTU and Dr. Roland Wess¨aly, Dr. Arie Koster, Sebastian Orlowski, and Adrian Zymolka
at ZIB for many discussions and the exchange of experience and ideas concerning network
optimization and resilience.vi
Other special thanks go to my graduate students. Especially, the work with Svetoslav
Duhovnikov,WolfgangMu¨hlbauer,MatthiasWimmer,TiloEisslerandArnoSchmid-Egger
contributed to this thesis. Very special thanks go to Moritz Kiese, who contributed twice
to the thesis and who I had the pleasure to advise him on his outstanding diploma thesis.
Last but not least, I would like to thank my family and all of my friends for their encour-
agement, support and the enjoyable time spent together.
Munich, December 2006 Claus G. GruberAbstract
An efficient and reliable communication infrastructure has become an important funda-
mental of oursociety. To guarantee the smooth transportationof data, transport networks
have to fullfill strict quality of service and resilience requirements. The choice of the used
resilience mechanisms has a substantial influence on capital and operational expenditures
and is an important criterion when designing telecommunication networks.
This thesis investigates the cost-efficient design and planning of resilient transport net-
works. We analyze the network planning process and present the Resilience Classification
Framework (RCF). This framework enables the systematic description, comparison, and
analysisofanyresilience mechanism. Weperformexampleclassifications andpresent novel
resilience approaches that are able to react dynamically and quickly to traffic load changes
and network equipment failures.
In the second part of the thesis, we analyze and assess approaches for the planning
of resilient multipath networks. We present mathematical formulations based on linear
programming that enable the cost-efficient optimization of resilient transport networks.
Apart from complete formulations of flow- and path-based equation systems for promising
multipath resilience mechanisms, we apply a new mathematical decomposition approach
called Column Generation that enhances the planning of resilient networks considerably.
With this technique, even very large resilient transport networks can be planned efficiently
that cannot be optimized using classical approaches.
In order to provide more insights in resilience mechanisms and cost-optimal topology
and path-selection, this thesis furthermore evaluates five popular path-based protection
and restorationmechanisms. Next to a mechanism comparison using the RCF, we perform
case-study optimizations andanalyzeresults todeduct quantitative capacity requirements.
Furthermore, we present recovery-time analysis results forOSPF andMPLS networks. We
analyze the influence of multipath routing on capacity requirements in order to provide
guidelines for the development of faster algorithms and heuristics for the planning of re-
silient networks.viii