Efficient optimization methods for communication network planning and assessment [Elektronische Ressource] / Moritz B. Kiese

Moritz B. Kiese

Informations

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

Extrait

TechnischeUniversitätMünchen
LehrstuhlfürKommunikationsnetze
Efficient Optimization Methods for
Communication Network Planning and
Assessment
Dipl. Ing. Univ. MoritzB.Kiese
VollständigerAbdruckdervonderFakultätElektrotechnikundInformationstechnik
derTechnischenUniversitätMünchenzurErlangungdesakademischenGradeseines
Doktor Ingenieurs(Dr. Ing.)
genehmigtenDissertation.
Vorsitzender: Univ. Prof. Dr. Ing. RalphKennel
PrüferderDissertation: 1. Univ. Prof. Dr. Ing. JörgEberspächer
2. Prof. ThomasK.Stidsen,Ph.D.
TechnicalUniversityofDenmark
Die Dissertation wurde am 01.10.2009 bei der Technischen Universität München ein
gereichtunddurchdieFakultätfürElektrotechnikundInformationstechnikam04.02.2010
angenommen.Ihavealwaysfoundthatplansareuseless,
butplanningisindispensable.
–DwightD.EisenhowerAbstract
Inthiswork,wedevelopefficientmathematicalplanningmethodstodesigncommu
nication networks. First, we examine future technologies for optical backbone net
works. As new, more intelligent nodes cause higher dynamics in the transport net
works, fastplanningmethodsarerequired. Tothisend, wedevelopaheuristicplan
ning algorithm. The evaluation of the cost efficiency of new, adapative transmission
techniquescomprisesthesecondtopicofthissection. Inthesecondpartofthiswork,
weoptimallyplanandassessnumerousprotectionmethodswithcolumn generation
and branch and price. The former method forms also the foundation of an extensive
planning method to determine optimal bounds on the connectivity of wireless mesh
networkswithbeamformingantennas,whichwedevelopinthelastpartofthiswork
andemployittoassessexistingdistributedheuristics.
Kurzfassung
In dieser Arbeit werden effiziente mathematische Planungsmethoden zum Entwurf
von Telekommunikationsnetzen entwickelt. Zunächst werden zukünftige Technolo
gienfüroptischeTransportnetzeuntersucht. Daneue,intelligentereNetzknoteneine
höhere Dynamisierung der Transportnetze zur Folge haben, werden schnelle Pla
nungsmethoden benötigt. Hierfür wird ein heuristisches Verfahren entwickelt. Die
UntersuchungderKosteneffizienzvonneuartigenadaptivenÜbertragungsverfahren
im Gesamtnetz bildet den weiteren Schwerpunkt dieses Abschnitts. Verschiedene
FehlerschutzmechanismenwerdenimzweitenTeilderArbeitmittelsColumn Gener
ation und Branch and Price Verfahren optimal geplant und bewertet. Erstere Meth
odebildetauchdieGrundlageeinesumfangreichenPlanungsverfahren,dasReferen
zwerte zur Konnektivitätsanalyse von drahtlosen Mesh Netzen mit Richtantennen
liefert,dasimletztenTeilderArbeitentwickeltundzurBewertungbestehenderverteil
terHeuristikeneingesetztwird.
vviAcknowledgements
Duringthecourseofthisthesis,Iwasfortunateenoughtobesupportedbysuperiors,
colleagues, and partners, many of whom have become far more for me than their
formalrolemightimply.
First and foremost, I am indebted to Prof. Dr. Ing. Eberspächer who created the In
stitutefor Communication Networks or “LKN”, which was at the least my academic
home during the last four years. Without his steady support and astonishing confi
dence in my abilities and the resulting freedom to follow my own ideas, this thesis
simplywouldnothavebeenpossible.
During INFORMS Telecommunication Conference in spring 2006, I was introduced
to Prof. Thomas K. Stidsen, PhD, who showed great interest in my work with Claus
Gruber. While being a visiting researcher at Nokia Siemens Networks in fall 2006,
westartedtoinvestigatethepossibilitiesofbranch and pricealgorithmsfornetwork
planning problems. The then newly started cooperation between TU München and
DTU financed a number of mutual research visits, during which we delved deeper
anddeeperintotheactualimplementationofbranch and pricealgorithms. Iammore
thangratefulforhisoffertobethesecondexaminerofmythesis.
IamthankingProf.Dr. Ing.RalphKennelforpresidingmythesiscommittee.
Thanks to Prof. Eberspächer’s efforts, at LKN I found many partners for discussions
aboutnetworks,computers,programming,scienceingeneral,students,coffeeandall
other topics of vital importance for upcoming scientists. A very special part of the
culture at LKN is the lively contact to our alumni (or a bit less flattering, but with
similaraffection“oldies”). Someofthesediscussionsresultedinnewresearch,others
in barbecues, and other were “just” an exchange of ideas, but I utterly enjoyed all of
them. In this sense I am specially indebted to Dr. Claus Gruber, Dr. Christian Hart
mann,Dr.MartinMaier,Dr.CarmenMasMachuca,Dr.DominicSchupke,Dr.Robert
Vilzmann,JanEllenbeck,OliverHanka,JuliusKammerl,SilkeMeister,BerndMüller-
Rathgeber,RobertNagel,RobertPrinz,MatthiasScheffel,andChristophSpleiss.
During the first three years, I participated in the BMBF funded research project EI
BONEinasubcontractofSiemensCorporateTechnologyandlateronNokiaSiemens
Networks. Duringthistime,Dr.AchimAutenriethandThomasEngelwereimportant
partners for discussion and started to build my knowledge of optical networks. Fur-
thermoretheirconstantinterestandconstructivecriticismhelpedmeenormouslynot
to drift away into the domain of purely mathematically interesting problems and to
keepusefulapplicationsinmind. Apartfromthismainteam,Iwouldliketoexpress
mygratitudetowardsDr.MarcoHoffmann,SaschaKallin,Dr.ThomasMichaelis,and
MatthiasSchuster.
I furthermore would like to thank my students Adriana Bocoi, Juan Camilo Cardone
Restreppo, Elisabeth Georgieva, Julian Lamberty, Velislava Marcheva, and Michal
Markowski. Itwasapleasuretobeyouradvisour.
Although I spent quite some time at institute, I am indebted to my friends outside
viithe institute, who provided distraction whenever I needed some (which might have
becomeobvioustomeonlyafterwards). Iamluckytohaveyou.
Just as my academic advisours showed great trust in my abilities, my family did the
same and has been even before I started my journey in the academic world. Without
yoursupport,encouragementandwisdomthisthesiswouldhaveneverhappened.
Lastbutnotleast,thankyoumydearCaroforbeingtherewheneverIneededyou.
viiiContents
1 Introduction 1
1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 StructureofThisThesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 NetworkDesign 5
2.1 NetworkArchitectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 HistoricalBackground . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 VerticalLayers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 HorizontalLayers . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 NetworkAssessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 FeasibilityCriteria . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 NetworkPlanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 FibreTopologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 DemandModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.3 CostModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Multi LayerModels . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Optimization 21
3.1 LinearProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 TheStandardFormofLinearPrograms . . . . . . . . . . . . . . . 22
3.1.2 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.3 SolvingLinearPrograms. . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.4 ComputationalComplexity . . . . . . . . . . . . . . . . . . . . . . 28
3.2 (Mixed)IntegerProgramming . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 StandardForm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.2 SolvingMIPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 NetworkOptimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 GraphTheory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.2 BasicFormulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.3 BasicNetworkModels . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 CapacityPlanningofIP/DWDMTransportNetworks 41
4.1 FastHeuristicPlanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.1 DWDM Grooming . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.2 Multi LayerNetworks . . . . . . . . . . . . . . . . . . . . . . . . . 55
ixContents
4.2 AdaptiveDWDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.1 TechnologicalFoundations . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 NetworkModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2.3 OptimizationModel . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.4Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.5 CaseStudy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67