Table of Contents
1 Introduction ……………………………………………………………………………………………………….. 1
1-1 Routing in the Internet ………………………………………………………………………………… 1
1-2 Quality of service …………………………………………………………………………………………. 2
1-3 Notation ……………………………………………………………………………………………………….. 6
1-4 Problem statement ……………………………………………………………………………………. 7
1-5 Outline …………………………………………………………………………………………………………. 8
2 Graphs, algorithms and complexity ……………………………………………………………….. 11
2-1 Graph theory ………………………………………………………………………………………………. 11
2-1-1 Graph definitions ………………………………………………………………………………… 11
2-1-2 Graph representation ………………………………………………………………………… 12
2-2 Classes of graphs ………………………………………………………………………………………… 14
2-2-1 Random graph …………………………………………………………………………………… 14
2-2-2 Waxman graph ………………………………………………………………………………….. 15
2-2-3 Power-law graph ……………………………………………………………………………….. 15
2-2-4 Lattice ………………………………………………………………………………………………… 16
2-3 Algorithmic complexity ………………………………………………………………………………… 18
2-4 NP-completeness ………………………………………………………………………………………… 21
3 Shortest path algorithms ………………………………………………………………………………… 23
3-1 Elementary graph algorithms ………………………………………………………………………… 24
3-1-1 Breadth-first search ………………………………………………………………………….. 25
3-1-2 Depth-first search ……………………………………………………………………………… 25
3-2 Classical shortest path algorithms ……………………………………………………………….. 25
3-2-1 Bellman-Ford algorithm ………………………………………………………………….. 27
3-2-2 Dijkstra algorithm ………………………………………………………………………………. 29
3-2-3 Bi-directional search ………………………………………………………………………….. 31
3-3 Best-first search ………………………………………………………………………………………….. 36
3-3-1 A* algorithm …………………………………………………………………………………….. 36
3-4 Mathematical programming …………………………………………………………………………… 37
3-4-1 Linear programming …………………………………………………………………………. 38
3-4-2 Dynamic programming (Floyd-Warshall algorithm) …………………………………. 41
4 Concepts of exact MCP algorithms ………………………………………………………………. 45
4-1 Definition of the path length l(P) …………………………………………………………………….. 45
4-1-1 Different (non-linear) length functions ……………………………………………………. 48
4-1-2 Visualization of the search space …………………………………………………………… 50
4-2 The k-shortest path algorithm ……………………………………………………………………… 51
4-3 Dominated paths …………………………………………………………………………………………… 54
4-3-1 Definition of non-dominance ………………………………………………………………. 54
4-3-2 An attainable bound for kmax ………………………………………………………………… 56
4-4 Look-ahead ………………………………………………………………………………………………… 60
4-4-1 The look-ahead concept ……………………………………………………………………… 60
4-4-2 Complexity of look-ahead …………………………………………………………………….. 62
4-4-3 Other look-ahead applications …………………………………………………………….. 62
4-5 Bi-directional search in multiple dimensions ……………………………………………………… 63
4-6 The SAMCRA algorithm …………………………………………………………………………….. 64
4-6-1 Meta-code SAMCRA …………………………………………………………………………. 65
4-6-2 Complexity of SAMCRA ……………………………………………………………………. 67
4-6-3 Example of the operation of SAMCRA ……………………………………………………….. 69
4-7 Conclusions ………………………………………………………………………………………………… 72
5 Overview of QoS algorithms ………………………………………………………………………….. 77
5-1 Heuristics ……………………………………………………………………………………………………… 77
5-1-1 Jaffe’s algorithm ………………………………………………………………………………… 77
5-1-2 Iwata’s algorithm …………………………………………………………………………………. 78
5-1-3 TAMCRA …………………………………………………………………………………………… 79
5-1-4 Chen’s algorithm …………………………………………………………………………………. 80
5-1-5 Randomized algorithm ………………………………………………………………………… 81
5-1-6 H_MCOP ……………………………………………………………………………………………. 81
5-1-7 Limited path heuristic …………………………………………………………………………. 82
5-2 ε-approximation …………………………………………………………………………………………… 83
5-2-1 Puri’s algorithm ………………………………………………………………………………….. 84
5-2-2 Xue’s algorithm ………………………………………………………………………………….. 84
5-3 Exact algorithms …………………………………………………………………………………………. 85
5-3-1 SAMCRA ………………………………………………………………………………………….. 85
5-3-2 HAMCRA ………………………………………………………………………………………….. 86
5-3-3 A*Prune …………………………………………………………………………………………….. 87
5-4 Special (non-MCP) QoS algorithms ………………………………………………………………… 87
5-5 Performance evaluation …………………………………………………………………………………. 88
5-5-1 Simulation set-up ………………………………………………………………………………… 88
5-5-2 Simulation results ……………………………………………………………………………….. 89
5-5-3 Simulation conclusions ……………………………………………………………………… 91
5-6 Conclusions ………………………………………………………………………………………………… 92
6 Multicast QoS routing …………………………………………………………………………………….. 95
6-1 Problem definition ……………………………………………………………………………………….. 96
6-2 Properties of multicast QoS routing ……………………………………………………………….. 97
6-3 MAMCRA …………………………………………………………………………………………………….. 100
6-4 Discussion of multicast QoS routing ……………………………………………………………… 105
6-4-1 Tuning MAMCRA ……………………………………………………………………………….. 105
6-4-2 QoS negotiation ………………………………………………………………………………….. 105
6-4-3 QoS multicast protocol ………………………………………………………………………… 106
6-4-4 QoS multicast in an active network ………………………………………………………. 106
6-5 Performance evaluation of MAMCRA …………………………………………………………… 107
6-6 Conclusions ………………………………………………………………………………………………… 109
7 Link-disjoint QoS routing …………………………………………………………………………….. 111
7-1 Problem definition ………………………………………………………………………………………. 111
7-2 Related work ……………………………………………………………………………………………….. 113
7-2-1 Link-disjoint paths in one dimension ……………………………………………………….. 113
7-2-2 Disjoint paths in multiple dimensions ……………………………………………………….. 114
7-3 Path augmentation for solving LPP ……………………………………………………………….. 115
7-3-1 The steps of LBA ………………………………………………………………………………… 115
7-3-2 LBA is based on the shortest path …………………………………………………………… 118
7-3-3 LBA is loop-free ……………………………………………………………………………………. 120
7-3-4 Optimality of LBA …………………………………………………………………………………. 121
7-4 Extending LBA to multiple dimensions ………………………………………………………….. 121
7-4-1 Operations of MLBA ……………………………………………………………………………. 121
7-4-2 Problems in multiple dimensions ……………………………………………………………. 123
7-5 DIMCRA ……………………………………………………………………………………………………… 125
7-5-1 Operations of DIMCRA ………………………………………………………………………… 125
7-5-2 Properties of DIMCRA ………………………………………………………………………….. 128
7-6 Conclusions ………………………………………………………………………………………………… 129
8 The complexity of exact MCP algorithms ………………………………………………………. 131
8-1 Related work ………………………………………………………………………………………………. 131
8-2 Worst-case complexity analysis ……………………………………………………………………. 133
8-3 The impact of link correlation on complexity ……………………………………………………… 139
8-3-1 Theory ………………………………………………………………………………………………. 139
8-3-2 Simulation results ………………………………………………………………………………….. 142
8-3-3 Inter-link correlation …………………………………………………………………………… 148
8-4 The impact of constraints on complexity ………………………………………………………… 153
8-4-1 Theory ………………………………………………………………………………………………. 153
8-4-2 Simulation results …………………………………………………………………………………. 157
8-4-3 Estimation of the shortest path length in a lattice ………………………………………….. 160
8-5 Conclusions ………………………………………………………………………………………………… 163
9 QoS dynamics ………………………………………………………………………………………………. 165
9-1 Introduction to QoS stability …………………………………………………………………………… 165
9-2 Related work ………………………………………………………………………………………………… 167
9-2-1 Traffic prediction ………………………………………………………………………………….. 168
9-2-2 Network update triggering ……………………………………………………………………. 168
9-2-3 Network update distribution ………………………………………………………………… 168
9-2-4 Inaccurate network state ……………………………………………………………………….. 169
9-3 Stability of a path ………………………………………………………………………………………….. 169
9-3-1 Mathematical analysis …………………………………………………………………………. 170
9-3-2 Simulations for ∆w ………………………………………………………………………………. 172
9-3-3 Simulations for ∆l ………………………………………………………………………………… 174
9-4 Conclusions on QoS stability ………………………………………………………………………… 176
9-5 Introduction to dynamic QoS algorithms ………………………………………………………… 177
9-6 Problem statement ……………………………………………………………………………………….. 177
9-7 Traffic engineering algorithms ……………………………………………………………………… 178
9-7-1 Overview …………………………………………………………………………………………… 178
9-7-2 Limitations ………………………………………………………………………………………….. 179
9-8 SAMCRA-B ………………………………………………………………………………………………….. 179
9-9 Performance evaluation …………………………………………………………………………………. 180
9-9-1 Scenario 1: influence of bandwidth constraint …………………………………………….. 182
9-9-2 Scenario 2: influence of one QoS constraint ……………………………………………….. 183
9-9-3 Scenario 3: influence of both QoS constraints ……………………………………………… 184
9-10 Conclusions on dynamic QoS algorithms ………………………………………………………. 184
10 Conclusions ……………………………………………………………………………………………….. 187
A Approximate analysis ……………………………………………………………………………………. 193
A-1 Approximate analysis of QoS complexity ………………………………………………………… 193
A-1-1 Analysis for a single link weight (m = 1) ……………………………………………………… 193
A-1-2 Analysis for multiple link weights (m > 1) …………………………………………………….. 195
A-1-3 Perfect negative correlation (m = 2) …………………………………………………………. 197
A-2 Approximate analysis of path stability …………………………………………………………….. 198
B Abbreviations ………………………………………………………………………………………………. 203
Bibliography ………………………………………………………………………………………………………. 205
Samenvatting (Summary in Dutch) ………………………………………………………………….. 219
Acknowledgements …………………………………………………………………………………………… 223
Curriculum Vitae ………………………………………………………………………………………………. 225
Abstract
The Internet consists of many network elements that direct packets on the correct path leading towards the destination. This process of finding and following a path to the destination is called routing. Routing is not infallible and packets may get lost: the current Internet cannot give any quality guarantees regarding the packets it transports. However, many new multi-media applications (e.g., VoIP) cannot properly operate without such guarantees. Finding paths that can meet such demands is called Quality of Service (QoS) routing. This thesis identifies several algorithmic concepts of QoS routing, which are all incorporated into our exact SAMCRA algorithm. The first large-scale performance evaluation of QoS algorithms indicates that the SAMCRA algorithm performs best. Besides SAMCRA, also algorithms for multicast QoS routing and link-disjoint QoS routing are proposed in this thesis. QoS routing is NP-complete, which means that to find the exact solution, algorithms require, in the worst case, a running time that cannot be bounded by a polynomial function. This thesis also analyzes the complexity of QoS routing and argues that it is feasible in practice. Hence, exact algorithms like SAMCRA should be used instead of heuristics. Finally, the dynamics of QoS routing are discussed and some preliminary work in this area is provided. Here, too, SAMCRA outperformed the other implemented algorithms.
