Survivability and traffic grooming in WDM optical networks

Half-title......Page 2
Title......Page 4
Copyright......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 14
Acknowledgments......Page 20
1 Optical networking technology......Page 22
1.1 Wavelength-division multiplexing......Page 23
1.2 Broadcast-and-select networks......Page 25
1.2.1 Broadcast-and-select network design......Page 26
1.3 Wavelength-routed WDM networks......Page 28
1.4 Wavelength conversion in WDM networks......Page 31
1.4.1 Conversion technology......Page 32
1.6 Optical burst switching......Page 33
1.7 The rest of the book......Page 34
2.1 Network design......Page 35
2.2 Network model......Page 36
2.3.1 Routing algorithm......Page 38
2.3.2 Wavelength assignment......Page 39
2.3.3 Design of wavelength switching with conversion......Page 41
2.4 Multi-fiber networks......Page 44
2.5 Survivability......Page 46
2.6 Restoration methods......Page 47
2.6.1 Resource saving......Page 48
2.7 Traffic grooming in WDM networks......Page 49
2.8 Optical packet switching......Page 51
2.9 Optical burst switching......Page 52
2.9.1 Challenges......Page 53
3 Restoration approaches......Page 55
3.2 Upgradeable network design......Page 59
3.3 Notation......Page 61
3.4 Cost model......Page 62
3.5 Design problem......Page 65
3.5.1 Problem formulation......Page 66
3.5.2 Summary and example......Page 68
3.5.3 Evolution with cost and technology trends......Page 70
3.6 Heuristic approach for network design......Page 72
3.6.1 Simulated annealing steps......Page 73
3.7 Network upgrade......Page 76
3.8.1 Observations......Page 77
4.1 Design of p-cycle restorable networks......Page 83
4.2 Cycle selection algorithms......Page 84
4.2.1 Use of preselecting a p-cycle candidate set......Page 85
4.2.3 High-efficiency p-cycle optimization heuristic algorithm......Page 86
4.4 A p-cycle-based design for dynamic traffic......Page 87
4.4.1 Performance matrix......Page 88
4.4.2.1 Notation......Page 89
4.4.2.3 Directed-link networks and p-cycle protection......Page 90
4.4.3 Accommodating connections: routing strategies......Page 91
4.4.3.1 Wavelength continuity constraint......Page 92
4.4.4 Effectiveness of the p-cycle-based design......Page 93
4.4.5.1 COST 239 network......Page 96
4.4.5.2 Effect of the network connectivity......Page 100
4.5 Algorithm for finding all cycles......Page 103
5.1 Capacity minimization......Page 107
5.2 Revenue maximization......Page 108
5.3 Capacity minimization: problem formulation......Page 109
5.4 Revenue maximization: problem formulation......Page 111
5.5 Solution methodology......Page 114
5.6 Performance evaluation......Page 116
5.6.1 Capacity minimization......Page 117
5.6.2 Revenue maximization......Page 119
6.1 Online algorithm......Page 123
6.1.2 Preprocessing step......Page 124
6.2 Example......Page 126
6.3 LP formulation......Page 127
6.3.1 Feasibility of solution......Page 128
6.5 Quality of the LP heuristic algorithm......Page 131
6.6 ILP and LP solution run times......Page 134
6.7 Run times for the LP heuristic algorithm......Page 136
7 Subgraph-based protection strategy......Page 137
7.1 Subgraph-based routing and fault tolerance model......Page 138
7.1.1 Fault tolerance with subgraph-based routing......Page 139
7.2 Performance of subgraph-based routing......Page 140
7.2.1 Performance metrics......Page 141
7.2.2 Network structures......Page 143
7.3.1 Blocking probability......Page 144
7.3.2 Average path length......Page 145
7.3.4 Comparison between network topologies......Page 146
7.3.5 Probability of reassignment......Page 147
7.4.1 Network and fault model......Page 148
7.4.3 Complexity analysis for subgraph routing......Page 149
7.4.4 Sub-graph routing for tolerating SRLG failures......Page 150
7.5 Constrained subgraph routing......Page 151
7.6 Example......Page 152
7.7 Observations......Page 161
8 Managing multiple link failures......Page 164
8.1 Link-based protection for two link failures......Page 165
8.1.1 Backup multiplexing in link-based protection......Page 167
8.2.1 Backup multiplexing in path-based protection......Page 168
8.3 Formulating two link failures......Page 169
8.3.1 Notation used......Page 170
8.3.2 ILP formulation......Page 171
8.4.1 Link-based protection......Page 176
8.4.2 Path-based protection......Page 177
8.5 Dual-link failure coverage of single-failure protection schemes......Page 178
8.6 Dual-link failure coverage using shared-mesh protection......Page 180
8.7.1 Dual-link subgraph routing complexity......Page 182
8.8 Coverage computation......Page 184
8.9 Observations......Page 188
9 Traffic grooming in WDM networks......Page 190
9.2 Static traffic grooming in rings......Page 194
9.3 Dynamic traffic grooming in WDM networks......Page 199
9.3.1 Connection setup and release......Page 201
9.3.2 Grooming example......Page 202
10 Gains of traffic grooming......Page 205
10.1 Network parameters......Page 206
10.2 Modeling constrained grooming networks......Page 207
10.2.1 Single-wavelength link......Page 208
10.2.2 Analysis of a single-wavelength two-hop path......Page 209
10.2.3 A multi-hop single-wavelength path......Page 210
10.2.3.2 Capacity correlation model......Page 211
10.2.4 Network analysis......Page 213
10.3 Sparse grooming network......Page 215
10.4 Validation of the model......Page 216
11 Capacity fairness in grooming......Page 222
11.1 Managing longer paths......Page 223
11.2 Capacity fairness......Page 224
11.3 Fairness performance of RWA algorithms......Page 226
11.4 Connection admission control for fairness......Page 227
11.4.1 Performance of the CAC algorithm......Page 230
12 Survivable traffic grooming......Page 231
12.1 Traffic stream multiplexing on a single wavelength link......Page 232
12.2.1 Sharing backup capacity......Page 234
12.3 Routing and wavelength assignment......Page 237
12.3.1 Wavelength assignment......Page 238
12.4 Effect of traffic grooming......Page 239
12.4.1 Effect of wavelength assignment and topology......Page 240
12.4.2 Effect of the grooming granularity......Page 242
12.4.3 Effect of the number of alternate paths......Page 243
13.1 Design problem......Page 245
13.1.1 Dedicated backup reservation......Page 246
13.1.2 Capacity reservation with backup multiplexing......Page 247
13.1.3.1 Objective: minimize the total wavelength links......Page 249
13.1.3.2 Constraints......Page 250
13.1.4.1 Objective......Page 251
13.2 Example......Page 252
14.1 Channels and trunks......Page 257
14.2 Modeling a WDM grooming network as a TSN......Page 258
14.3 Node architecture......Page 259
14.4 Free and busy trunks......Page 262
14.5.2 Network state information......Page 264
14.5.3 Path-selection algorithms......Page 265
14.5.4 Resource assignment......Page 266
14.6 Grooming network model......Page 267
14.7.1 Link information......Page 268
14.7.2 Path information......Page 271
14.8 A two-pass approach......Page 273
14.8.1 Path selection......Page 274
14.8.2 Subtrunk assignment......Page 275
14.9 Modeling a channel-space switch in MICRON......Page 278
15.1 Blocking model......Page 282
15.2 Estimation of call arrival rates on a link......Page 283
15.3 Path blocking performance......Page 285
15.4 Free trunk distribution......Page 290
15.5 Modeling switches......Page 294
15.6 Heterogeneous switch architectures......Page 295
15.7 Improving the accuracy of the analytical model......Page 299
16 Validation of the TSN model......Page 301
16.1 Simulation setup......Page 302
16.2 Homogeneous networks performance......Page 303
16.3 Heterogeneous networks performance......Page 308
16.4 Observations......Page 313
17.1 Information collection......Page 314
17.1.2 Sparse full-grooming networks......Page 315
17.1.3 Constrained grooming networks......Page 316
17.2 Path-selection algorithms......Page 317
17.4 Performance of routing algorithms......Page 319
17.5.1 Performance metrics......Page 320
17.5.2 Blocking performance......Page 321
17.5.4 Average path length......Page 322
17.5.5 Average shortest path length......Page 323
17.5.6 Effect of dispersity routing......Page 324
17.5.7 Effect of dispersity vs. grooming capability......Page 325
18 IP over WDM traffic grooming......Page 330
18.1 IP traffic grooming in WDM networks......Page 332
18.2 IP traffic grooming problem formulation......Page 334
18.3 Solution for an optimal strategy......Page 336
18.3.2 Problem formulation......Page 337
18.5 Traffic aggregation algorithm......Page 339
18.5.1 Complexity analysis......Page 341
18.6.1 Solutions and results......Page 342
18.6.2 Observations......Page 343
18.7 Performance study......Page 345
18.8 Examples......Page 346
19.1 Light trail......Page 351
19.2 Node structure......Page 352
19.3 Light trail characteristics......Page 354
19.4 Light trail design......Page 355
19.4.1 Step I: traffic matrix preprocessing......Page 356
19.4.2 Step II: ILP formulation......Page 357
19.5 Solution considerations......Page 358
19.5.1 The best-fit approach......Page 359
19.5.2 Algorithm design......Page 360
19.5.3 Discussions......Page 361
19.5.4 Algorithm performance......Page 362
19.6 Light trail hop-length limit: Tlmax = 4......Page 364
19.6.1 Light trail hop-length limit: Tlmax = 3......Page 366
19.7.1 Discussions......Page 367
19.8 Restoration in the light trail architecture......Page 368
19.8.2 Link-based protection......Page 369
19.8.3 Comparison of connection-based and link-based protection......Page 370
19.10 ILP formulation: connection-based protection......Page 371
19.10.2 Objective......Page 372
19.10.3 Solutions......Page 373
19.10.4 A simple example......Page 374
19.10.5 Example 2......Page 376
A1.1 Fiber optic cables......Page 378
A1.1.1 Light propagation in optical fibers......Page 379
A1.1.1.1 Modal dispersion......Page 380
A1.1.2 Fiber dispersion......Page 381
A1.1.3 Fiber non-linearities......Page 382
A1.2 Filters, multiplexors and demultiplexors......Page 383
A1.2.3 Mach–Zehnder filter......Page 384
A1.2.4 Acousto-optic filter......Page 385
A1.2.8 Fiber Bragg gratings......Page 386
A1.2.10 Arrayed waveguide grating......Page 387
A1.3.1 Laser......Page 388
A1.3.2 Light-emitting diode......Page 389
A1.4.2 Erbium-doped fiber amplifier......Page 390
A1.4.4.2 External modulators......Page 391
A1.5.1 PIN......Page 392
A1.6 Couplers......Page 393
A1.9 Repeaters......Page 394
A1.11 Optical switches......Page 395
A1.12 Wavelength converters......Page 397
A2.1 Network topology......Page 398
A2.2 Transmission technology......Page 400
A2.3 Traffic control and network management techniques......Page 402
A2.4 Cost......Page 403
A2.5 Approaches to network design......Page 404
A2.6 Quality of service requirements......Page 405
A2.7 Probability distributions......Page 406
A2.8 Delays in networks......Page 408
A2.9 Queuing models......Page 409
Appendix 3 Graph model for network......Page 411
A4.1 Shortest-path routing......Page 414
A4.1.1 Bellman's equations......Page 415
A4.2.1 Dijkstra method......Page 416
A4.3 Shortest paths between all pairs of nodes......Page 417
A4.3.1 Floyd–Warshall method......Page 419
A4.5 Minimum spanning tree (MST)......Page 420
A4.5.2 Prim's algorithm......Page 421
A4.5.3 Constrained MST......Page 422
A4.6 Tree traversal......Page 423
A4.7 Network (Max) flow......Page 424
Appendix 5 Routing algorithm......Page 427
A5.1 Embedding arbitrary connection requests......Page 428
A6.1 Regular topologies......Page 429
A6.1.1 Completely connected topologies......Page 430
A6.1.3 Rings and multi-rings......Page 431
A6.1.6 Dynamic topologies......Page 432
A6.2.2 Enhanced hypercube......Page 433
A6.3 Arbitrary topology design......Page 434
A6.4 Linear programming problems......Page 435
References......Page 437
Index......Page 455