Traffic engineering in MPLS networks with multiple objectives: modeling and optimization [Elektronische Ressource] / vorgelegt von Selin Kardelen Cerav-Erbas

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2004
• Nombre de lectures: 22
• Langue: English

Extrait

Tra c Engineering in MPLS Networks with
Multiple Objectives: Modeling and Optimization
Von der Fakultat fur Mathematik, Informatik und Naturwissenschaften
der Rheinisch-Westfalisc hen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades einer Doktorin
der Naturwissenschaften genehmigte Dissertation
vorgelegt von
Selin Kardelen Cerav-Erbas
Master of Science in Industrial and Systems Engineering
aus Manisa, Turkei
Berichter: Universitatsprofessor Dr. Rudolf Mathar
Universitatsp Dr. Otto Spaniol
Tag der mundlichen Prufung: 21 Juli 2004
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar.Acknowledgments
There is a list of people without whom this study would not have come to an end.
Their technical and psychological support has been a great motivation for me to
complete this thesis.
Initially, I would like to thank my supervisor, Prof. Dr. Rudolf Mathar, for giving
me the opportunity to do research in his department. As an expert, his technical and
strategic advices have provided me clear solutions to the di cu lt questions encoun-
tered during the last 3 years.
I would like to thank also Prof. Dr. Otto Spaniol for his help and support to my
research. The environment which he has provided among the group of "Graduate
College" has been very friendly and enlightening.
My husband, Ca gkan, has been very patient with me during the last 3 years. His
both technical and moral support has made me stay calm and positive during di cu lt
times.
Priv.-Doz. Dr. Yubao Guo and Prof. Dr. Dr. h.c. Hubertus Jongen, provided me great
help to get prepared for the exam.
My sisters, Ozlem and Yasemin, and my mother, Ayten, have been very supportive,
although they were very far away from Germany. "Tesekkurler!"
I would like to thank all of my colleagues in the department in Aachen: Eric Beutner,
Daniel Catrein, Anke Feiten, Wolfgang Her , Lorenz Imhof, Birgit Kaiser, Michael
Meier, Natalie and Michael Naehrig, Ole Nordho , Michael Reyer, Michael Schmeink,
Volker Schmitz, Reinhard Schwab, Andreas Tillmans, and Iskender Yasar. Their helpand friendship have made me feel like at home in Germany.
Lastly, I would thank my new colleagues in Louvain-la-Neuve. Prof. Bernard Fortz
and Hakan Umit have been very understanding when I needed some extra time for
my PhD work. I am also grateful to Roman Kasperzec and Mathias Lorenz especially
for their help in the translation of the abstract.Abstract
With the increasing usage of QoS-based applications, tra c engineering in commu-
nication networks has become more crucial. For the optimal utilization of network
resources, service providers need to consider multiple criteria that can be customer-
or tra c-orien ted. Multiprotocol Label Switching (MPLS) has been developed to ap-
ply more convenient tra c engineering in autonomous systems. This thesis focuses
on the multiobjective optimization of Label Switched Path design problem in MPLS
networks. Minimal routing cost, optimal load-balance in the network, and minimal
splitting of tra c form the objectives. The problem is formulated as a zero-one mixed
integer program and aims at exploring the trade-o s among the objectives. The in-
teger constraints make the problem NP-hard. In the thesis rst both the exact and
heuristic multiobjective optimization approaches are discussed, and then a heuris-
tic framework based on simulated annealing is developed. Various search strategies
within the framework are investigated and experimental studies are carried out for a
performance comparison.Zusammenfassung
Mit zunehmenden Einsatz von QoS-Anwendungen wird Tra c Engineering in
Kommunikationsnetzen immer wichtiger. Fur eine optimale Ressourcenverwendung
im Netz mussen Service Provider mehrere Kriterien beachten, die kunden- oder
verkehrsorientiert sein kon nen. Multiprotocol Label Switching (MPLS) ist entwick-
elt worden, um Tra c Engineering in autonomen Systemen bequemer zu gestalten.
Die vorliegende Dissertation konzentriert sich auf die Mehrzieloptimierung des Label
Switched Path Design-Problems in MPLS Netzen. Minimale Routingkosten, optimale
Eingabebalance im Netz und minimale Verkehrsaufspaltung sind die verfolgten Ziel-
funktionen. Die Problemformulierung fuhrt zu einem binaren gemischt-ganzzahligen
Programm, mit dem die Wechselwirkung zwischen den Zielfunktionen untersucht
werden. Wegen der Ganzzahligkeit erweist sich das Problem als NP-hart. In der vor-
liegenden Dissertation werden zunachst Ansatze zur exakten Losung und Heuristiken
der Mehrzieloptimierung untersucht. Anschliessend werden auf Simulated Annealing
basierende heuristische Ansatze entwickelt. Hiermit werden verschiedene Suchalgo-
rithmen bezuglich ihrer Leistungsfah igkeit experimentell verglichen.
viiviiiContents
1 Introduction 1
2 Multiobjective Optimization and Exact Solution Approaches 3
2.1 Search versus Decision Making . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Key Concepts and Terminology . . . . . . . . . . . . . . . . . . . . . 5
2.3 Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 The Weighted Sum Method . . . . . . . . . . . . . . . . . . . 10
2.3.2 The -Constraint Method . . . . . . . . . . . . . . . . . . . . 11
2.3.3 The Lexicographic Weighted Chebyshev Programming . . . . 14
2.4 Discussion of Exact Solution Approaches . . . . . . . . . . . . . . . . 17
3 An O -line Multiobjective Model for MPLS Networks 19
3.1 How does MPLS work? . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Policies and Constrained-based Routing . . . . . . . . . . . . 22
3.2 Classi cation of Tra c Engineering . . . . . . . . . . . . . . . . . . . 23
3.2.1 Time-dependent Versus State-dependent . . . . . . . . . . . . 23
3.2.2 O -lin e Versus On-line . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Overview of Tra c Engineering Models . . . . . . . . . . . . . . . . . 24
3.4 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5 Model Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.6 Extensions of the Model . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6.1 Multiple Priority Case . . . . . . . . . . . . . . . . . . . . . . 36
3.6.2 Admission Control . . . . . . . . . . . . . . . . . . . . . . . . 37
3.7 Multiobjective Analysis of the Model by Exact Methods . . . . . . . 37
3.8 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.9 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Modern Heuristic Approaches for Multiobjective Optimization 51
4.1 Overview of Modern Heuristic Approaches . . . . . . . . . . . . . . . 51
4.2 Key Issues in Multiobjective Heuristic Approaches . . . . . . . . . . . 55
4.3 Heuristic Techniques with Multiple Objectives . . . . . . . . . . . . . 57
ix