Multiwavelength optical networks: architectures, design, and control

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 9
Figures......Page 19
Tables......Page 31
Preface to the Second Edition......Page 33
Acknowledgments......Page 37
1.1 Why Optical Networks?......Page 41
1.2 Objectives of an Optical Network Architecture......Page 44
1.3 Optics versus Electronics: The Case for Transparent Multiwavelength Networks......Page 49
1.4 Optics and Electronics: The Case for Multilayered Networks......Page 52
1.5 Network Hierarchies......Page 56
1.6 A Little History......Page 58
1.7 Overview and Road Map......Page 62
Bibliography......Page 65
2 The Layered Architecture and Its Resources......Page 68
2.1 Layers and Sublayers......Page 69
2.2 Network Links: Spectrum Partitioning......Page 74
2.3 Optical Network Nodes: Routing, Switching, and Wavelength Conversion......Page 79
2.3.1 Static Nodes......Page 80
2.3.1.1 Directional Couplers......Page 82
2.3.1.2 Static Routers......Page 84
2.3.2 Dynamic Nodes......Page 86
2.3.2.1 Permutation Switches: Characterization and Complexity......Page 88
Characterization of Blocking......Page 90
2.3.2.2 Generalized Switches......Page 92
2.3.2.3 Linear Divider-Combiners......Page 93
2.3.2.4 Waveband-Space Switches......Page 96
2.3.2.5 Wavelength-Space-Time Switches: Optical Packet Switching......Page 100
2.3.2.6 Cross-Talk......Page 102
Wavelength-Interchanging Switches......Page 105
2.4 Network Access Stations......Page 107
2.4.1 Transmitting Side......Page 110
2.4.2 Receiving Side......Page 111
2.5 Overlay Processors......Page 114
2.5.2 Wavelength Interchange......Page 116
2.6 Logical Network Overlays......Page 117
2.6.1 SONET Networks......Page 119
2.6.2 ATM Networks......Page 121
2.6.3 IP Networks......Page 123
2.6.4 MPLS and Its Extensions......Page 124
2.7 Summary......Page 125
2.8 Problems......Page 127
Bibliography......Page 129
3 Network Connections......Page 131
3.1 Connection Management and Control......Page 136
3.1.2 Logical Connections......Page 140
3.1.2.1 Stream and Packet Traffic......Page 141
3.2 Static Networks......Page 142
3.2.1 Point-to-Point and Multipoint Connections......Page 143
3.2.1.1 Time-Division Techniques......Page 146
3.2.1.2 Time-Wavelength-Division Techniques......Page 149
3.2.2 Packet Switching in the Optical Layer: The MAC Sublayer......Page 151
3.2.3 Additional Comments on Broadcast-and-Select......Page 161
3.3 Wavelength-Routed Networks......Page 162
3.3.1.1 Dedicated and Switched Connections: Rearrangeability......Page 164
3.3.1.2 Channel Assignment Constraints......Page 165
3.3.2 Routing and Channel Assignment Examples......Page 168
3.3.2.1 The Bidirectional Ring......Page 169
3.3.2.2 A Mesh Network......Page 171
3.4 Linear Lightwave Networks: Waveband Routing......Page 173
3.4.1 Routing and Channel Assignment......Page 175
3.4.2 Multipoint Subnets in LLNs......Page 180
3.4.3 A Seven-Station Example......Page 183
3.4.3.2 LLN Realization: Fully Shared Logical Topology......Page 185
3.4.3.3 LLN Realization: Hypernet Logical Topology......Page 187
3.4.3.5 Comparisons......Page 189
3.5 Logically-Routed Networks......Page 191
3.5.1 Point-to-Point Logical Topologies......Page 193
3.5.2 Multipoint Logical Topologies: Hypernets......Page 196
3.6 Summary......Page 202
3.7 Problems......Page 203
Bibliography......Page 204
4 Enabling Technology......Page 205
4.1 Evolution of Transmission and Switching Technology......Page 206
4.2 Overview of the Optical Connection......Page 207
4.3.1.1 Rays: Geometric Optics......Page 208
4.3.1.2 Modes: The Wave Picture......Page 211
4.3.2.1 Fiber Geometry and Fiber Cables......Page 214
4.3.2.2 Attenuation......Page 215
Intermodal Dispersion......Page 217
Chromatic Dispersion......Page 218
Polarization Mode Dispersion......Page 219
Effects of Dispersion on Maximum Bit Rates......Page 220
Dispersion Management......Page 221
Stimulated Raman Scattering......Page 223
Four-Wave Mixing......Page 224
Effective Interaction Length......Page 225
Nonlinear Effects in Multiwavelength Systems......Page 226
4.3.3 Solitons......Page 227
4.3.4 Photonic Crystal Fibers......Page 228
4.4 Amplifiers......Page 230
4.4.1 Erbium-Doped Fiber Amplifiers......Page 231
4.4.1.2 Gain Saturation......Page 234
4.4.1.3 Noise and Noise Figure......Page 235
4.4.1.4 Amplifier Chains......Page 237
4.4.2 Raman Amplifiers......Page 238
4.4.3 Semiconductor Optical Amplifiers......Page 241
Quantum Dot SOAs......Page 243
4.4.4 Amplification Trends in Metro Optical Networks: Amplets......Page 244
4.5.1 Lasers......Page 245
4.5.1.1 Single-Frequency Operation......Page 247
4.5.1.3 Supercontinuum Generation......Page 248
4.5.1.4 Tunability......Page 250
4.5.2 Vertical Cavity Surface Emitting Lasers......Page 251
4.5.3.1 Direct Modulation......Page 252
4.5.3.2 External Modulation......Page 254
4.5.3.3 Electro-absorption Modulated Lasers......Page 255
4.6.1 Photodetectors......Page 257
4.6.1.2 Avalanche Photodiodes......Page 258
4.6.2 Front-End Amplifier: Signal-to-Noise Ratio......Page 259
4.6.3 Digital Signal Detection: Noise, Interference, and Bit Error Rate......Page 261
4.6.4 Analog Systems: Carrier-to-Noise Ratio......Page 267
4.7 The End-to-End Transmission Channel......Page 268
4.7.1 Modulation Formats......Page 269
4.7.2 Forward Error Correction......Page 271
4.7.3 Equalization......Page 273
4.8 Coherent Optical Systems......Page 274
4.9.1 Cross-Talk......Page 275
4.9.2 Signal Power Divergence......Page 279
4.9.4 Optical Filter Concatenation: Distortion-Induced Penalty......Page 280
4.10 Optical and Photonic Device Technology......Page 281
4.10.1 Couplers and Switches......Page 282
Controllable Directional Coupler......Page 284
Mach–Zehnder Interferometric Switch......Page 286
Cascaded Mach–Zehnder Switches......Page 287
Gate Arrays......Page 288
Bubble Switch......Page 289
4.10.1.2 Microelectromechanical Systems: MEMS......Page 290
4.10.1.3 Liquid Crystal Switch Architectures......Page 294
4.10.2 Reciprocity......Page 295
4.10.4 Optical Filtering Technology......Page 297
4.10.4.1 Fabry–Perot Filters......Page 300
4.10.4.2 Multilayer Interference Filters......Page 301
4.10.4.3 Fiber andWaveguide Gratings......Page 303
4.10.4.4 ArrayedWaveguide Gratings......Page 305
4.10.5 Multiwavelength Switch Technology......Page 306
4.10.5.1 Acousto-Optic Tunable Filters......Page 307
4.10.5.2 Liquid Crystal Multiwavelength Switch......Page 309
4.10.5.3 MEMS-Based Wavelength-Selective Switches......Page 310
4.10.5.5 AWG-Based Switches......Page 311
4.10.5.6 Wavelength Dilation......Page 313
4.11 Wavelength Conversion and Signal Regeneration......Page 314
4.11.1 All-Optical Wavelength Conversion......Page 315
4.11.2 Opaque Wavelength Conversion and Signal Regeneration......Page 318
4.12.1.1 Crossbar Switches......Page 321
4.12.1.2 Routers/Selectors......Page 324
4.12.1.3 Benes Switches......Page 325
4.12.1.4 Switch Cross-Talk......Page 326
4.12.2 Wavelength-Selective Switches......Page 328
4.12.2.1 Optical Add/Drop Multiplexers......Page 329
4.12.2.2 Optical Cross-Connects......Page 333
4.13 Performance Evaluation: Methodology and Case Studies......Page 337
4.13.1 Physical-Layer Simulation: Three-Step Approach......Page 338
4.13.2.1 Study of aWavelength Add/Drop Multiplexer Chain......Page 341
4.13.2.2 Modeling Performance Impairments in a Metro WDM Network Composed of Interconnected Rings......Page 342
4.13.2.3 Engineering the Performance of a DWDM Metro Network Deployment Scenario......Page 348
4.14 Problems......Page 351
Bibliography......Page 354
5.1 Shared Media: The Broadcast Star......Page 364
5.2 Representative Multiplexing and Multiple-Access Schemes......Page 367
5.2.1 Time-Wavelength-Division Multiplexing/Multiple Access......Page 368
5.2.1.1 Scheduling Efficiency......Page 372
5.2.1.2 Transmission Constraints: Optical Spectral Efficiency......Page 373
5.2.2.1 Principles of SCMA......Page 376
5.2.2.2 Spectra......Page 379
5.2.2.3 TDM/T-SCMA......Page 385
5.2.2.4 Packet Switching Using SCMA......Page 387
5.2.2.5 SCM/SCMA......Page 388
5.2.2.6 SCM/WDMA/SCMA......Page 389
5.2.3 Code Division Multiple Access......Page 392
5.2.3.1 Electronic Processing: Intensity-Modulated Direct-Detection Systems......Page 394
5.2.3.2 CDMA with Optical Processing......Page 399
Intensity-Modulated Systems......Page 400
Fast Frequency Hopping CDMA Using FBGs......Page 401
Optical CDMA Using Phase Masks......Page 403
Optical CDMA Using Superstructure Fiber Gratings......Page 405
5.2.3.5 Concluding Remarks on CDMA......Page 406
5.3 Traffic Constraints in Shared-Channel Networks......Page 407
5.3.2 Unbalanced Traffic......Page 410
5.4.1 Fixed-Frame Scheduling for Stream Traffic......Page 411
5.4.1.1 Channel Assignments: Tunability......Page 413
5.4.1.2 Examples of Optimal Schedules......Page 415
5.4.1.3 Traffic Matrix Scaling......Page 419
5.4.1.4 Multicast Logical Connections......Page 420
5.4.2 Fixed-Frame Scheduling for Packet Traffic......Page 423
5.5 Demand-Assigned Connections......Page 429
5.5.1 Blocking Calculations in WDMA Networks......Page 430
5.5.2 Blocking in Combined Time-Wavelength-Division Networks......Page 435
Admission Control......Page 437
Rearrangeability Revisited......Page 438
5.6 Packet Switching in the Optical Layer......Page 439
5.6.1 Uncontrolled Scheduling: Random Access......Page 441
5.6.2 Scheduling with Loss......Page 443
5.6.3 Lossless Scheduling: Reservations......Page 445
5.6.4 Perfect Scheduling......Page 447
5.6.5 Dynamic versus Fixed Capacity Allocation......Page 448
5.7 The Passive Optical Network......Page 449
5.7.1 ATM and Fixed-Frame PONs......Page 452
5.7.2 Ethernet-Based PONs......Page 454
5.7.3 WDM PONs......Page 456
5.7.4 Optical-Wireless Access......Page 460
5.7.5 Recent Trends......Page 462
5.8 Summary......Page 464
5.9 Problems......Page 465
Bibliography......Page 467
6.1 Introduction......Page 472
6.2 Physical Topologies......Page 474
6.3 Wavelength-Routed Networks: Static Routing and Channel Assignment......Page 482
6.3.1 Flow Bounds: Matching the Physical and Logical Topologies......Page 484
6.3.1.1 Aggregate Network Capacity Bound......Page 485
6.3.1.2 Limiting Cut Bound......Page 486
6.3.2 Nonblocking Stations......Page 488
6.3.3 RCA as a Graph Coloring Problem......Page 489
6.3.4 Rings......Page 492
6.3.4.1 Shared-Protection Rings......Page 493
6.3.4.2 RCA in WDM Shared-Protection Rings......Page 495
Wavelength Assignment: Single Fiber Pair Access Case......Page 496
Arbitrary Connectivity on the Ring: One Wavelength Interchanger......Page 497
6.3.5 Ring Decomposition of General Mesh Networks......Page 498
Eulerian Networks......Page 499
Sparse Wavelength Interchange......Page 500
Bridges as Logical Switches......Page 501
6.3.6 Multistar Wavelength-Routed Networks......Page 502
6.3.7 RCA as an Optimization Problem......Page 504
6.3.7.1 NoWavelength Interchange: RCA-I......Page 505
6.3.7.2 Full λ-Interchange: RCA-II......Page 508
6.3.7.3 Sparse λ-Interchange......Page 509
6.3.7.4 The Fluid Flow Bound......Page 510
6.3.7.5 Maximizing Carried Traffic......Page 511
6.3.8.1 A Minimum-Hop Heuristic......Page 514
6.3.8.2 A Monte Carlo Approach......Page 519
6.4.1 Some Basic Routing and Channel Assignment Algorithms......Page 524
6.4.1.1 Characterization of Routing......Page 525
6.4.1.2 Characterization of Channel Assignment......Page 526
6.4.1.4 Shortest Path with Deletions......Page 527
6.4.1.6 Fairness......Page 529
6.4.2 Case Study: Bidirectional Rings......Page 531
6.4.2.1 Rings with FullWavelength Interchange......Page 533
6.4.3 Performance of Dynamic Routing Rules on Meshes......Page 534
6.4.4 Case Study: An Interconnected Ring......Page 535
6.4.5 Routing Multicast Connections in WRNs......Page 537
Optical Multicasting with Optical Layer Constraints......Page 544
Sparse Multicasting: Placement of Optical Splitters......Page 545
6.5 Linear Lightwave Networks: Static Routing Rules......Page 547
6.5.1 Routing of Optical Paths......Page 549
6.5.2 Optical Connections: λ-Channel Assignment......Page 556
6.5.3 Significance of Nonblocking Access Stations in LLNs......Page 558
6.5.4 Local Access to LLNs......Page 559
6.5.5 Routing Waveband and Channel Assignment on the Petersen Network......Page 561
Case 1: W = 3, Multicast Optical Paths......Page 562
Case 2: W = 5, Point-to-Point Optical Paths......Page 566
6.5.6.1 λ-Channel Assignment......Page 568
Petersen Network: W = 5......Page 570
Multicast Optical Connections......Page 572
Many-to-Many Optical Connections......Page 573
6.5.6.3 Performance Comparisons......Page 575
Case 2: W = 5......Page 577
6.5.6.4 Demand-Assigned Logical Connections......Page 578
6.5.7 Multistar Linear Lightwave Networks......Page 580
6.6.1 Point-to-Point Connections......Page 584
6.6.1.1 Selection of a Waveband......Page 585
6.6.1.2 Routing within a Given Waveband......Page 586
k-SP......Page 588
Min-Int......Page 589
6.6.1.3 Channel Allocation......Page 590
6.6.1.4 Performance of Dynamic Algorithms: Point-to-Point Connections......Page 591
Case 1: Single Waveband; Max Reuse versus Min Reuse Channel Allocation......Page 592
Case 3: Single Waveband; 2-SP versus Min-Int Routing......Page 593
Case 4: Single Waveband; Multifiber Links......Page 594
Case 5: Multiple Wavebands......Page 595
6.6.1.5 Summary of Point-to-Point Dynamic Routing in LLNs......Page 597
6.6.2.1 Routing within a GivenWaveband: Multicast Trees......Page 598
6.6.2.2 Preselecting Edge–Disjoint Trees on a Waveband......Page 600
Shortest Path Routing......Page 601
Rooted Routing on a Tree......Page 604
Channel Allocation on a Tree......Page 606
6.6.2.5 Results of Simulations......Page 607
6.7 Problems......Page 608
Bibliography......Page 611
7.1 Introduction: Why Logically-Routed Networks?......Page 616
7.1.1 Multitier Networks: Grooming......Page 621
7.2 Point-to-Point Logical Topologies: Multihop Networks......Page 625
7.2.1 ShuffleNets......Page 627
7.2.2 Families of Dense Logical Topologies......Page 629
7.3.1 Logical-Layer Design......Page 631
7.3.2 Physical-Layer Design......Page 634
7.3.3 Traffic Grooming in Point-to-Point Logical Topologies......Page 637
7.3.3.1 Traffic Grooming in WDM Rings......Page 638
7.3.3.2 Traffic Grooming in WDM Mesh Networks......Page 642
7.4 Multipoint Logical Topologies: Hypernets......Page 647
The Underlying Graph of a Hypergraph......Page 650
7.4.1 Capacity of a Multipoint Subnet......Page 651
7.4.2 Families of Dense Hypernets......Page 653
7.4.3 Kautz Hypernets......Page 655
7.4.3.1 From Graphs to Hypergraphs: Duality......Page 656
DK H(1, D, s) by Duality......Page 657
7.4.3.2 Edge Grouping......Page 660
7.4.3.3 Generalized Kautz Hypergraphs......Page 661
Address Shift Routing......Page 663
Routing in the Undirected Case......Page 665
7.4.3.5 Performance Comparisons......Page 666
7.4.4 Hypernet versus Multihop......Page 668
7.4.5 Multicast Virtual Connections......Page 671
7.5.1 Logical-Layer Design......Page 672
Tree Routing......Page 674
Waveband Assignment......Page 675
7.5.3 Traffic Grooming in Multipoint Logical Topologies......Page 677
7.5.4 Multistar Realizations......Page 679
7.6 Summary......Page 681
7.7 Problems......Page 682
Bibliography......Page 683
8 Survivability: Protection and Restoration......Page 687
8.1 Objectives of Protection and Restoration......Page 688
8.2.1 Point-to-Point Systems......Page 690
8.2.1.1 (1 + 1) Facility Protection......Page 691
8.2.1.3 (1:N) Facility Protection......Page 693
8.2.2 SONET Self-Healing Rings......Page 694
8.2.2.1 Unidirectional Path-Switched Ring Architecture......Page 695
Two-Fiber Bidirectional Line-Switched Rings......Page 696
8.2.3 SONET Self-Healing Ring Interconnection Techniques......Page 697
8.2.3.3 Interconnected BLSR–UPSR Architectures......Page 699
8.2.4 Architectures with Arbitrary Mesh Topologies......Page 703
8.2.4.1 Mesh Architectures Using Ring Covers for Survivability......Page 704
8.2.4.2 DCS-Based Centralized Restoration Techniques......Page 705
8.2.4.3 DCS-Based Distributed Restoration Techniques......Page 706
8.3.1.1 (1 + 1) Optical Protection......Page 709
8.3.1.2 (1:1) Optical Protection......Page 710
8.3.1.3 (1:N) Optical Protection......Page 711
8.3.2.1 Unidirectional WDM Path-Protected Ring Architecture......Page 712
8.3.2.2 Four-Fiber WDM Shared Protection Ring Architecture......Page 713
8.3.2.3 Two-Fiber WDM Shared Protection Ring Architecture......Page 715
8.4 Optical-Layer Protection: Mesh Architectures......Page 717
Centralized versus Distributed Backup Route Computation......Page 718
8.4.1.1 Why Shared Optical Line-Based Protection?......Page 719
8.4.1.2 Cycle Double Covers......Page 720
Link Failure Protection......Page 721
The Planar Case......Page 723
The Nonplanar Case......Page 725
Implementation of APS for Link Failures Using Protection Cycles......Page 726
8.4.1.3 p-Cycles......Page 728
8.4.1.4 Generalized Loopbacks......Page 730
8.4.2.1 (1 + 1) Dedicated Backup Path Protection......Page 732
8.4.2.2 Shared Backup Path Protection......Page 733
ILP: Shared Path-Based Protection......Page 735
8.4.2.4 Shared Risk Groups......Page 737
8.4.3 Segment Protection......Page 740
8.4.4 Survivability Techniques for Multicast Connections......Page 742
8.5 Summary......Page 743
8.6 Problems......Page 746
Bibliography......Page 747
9 Optical Control Plane......Page 754
9.1 Introduction to the Optical Control Plane......Page 756
9.1.2 Control-Plane Interfaces......Page 759
9.1.3 Control-Plane Functions......Page 761
9.2.1 Packet Transport through an MPLS Network......Page 762
9.2.2 MPLS Protocol Stack......Page 767
9.2.3.2 Quality of Service/Class of Service......Page 768
9.3 Overview of Generalized Multiprotocol Label Switching......Page 769
9.3.1.1 Neighbor Discovery......Page 771
9.3.1.2 Link Management Protocol......Page 772
9.3.2.1 General Features of Routing Protocols......Page 774
Path Protection and Physically Diverse Paths......Page 776
9.3.2.3 Open Shortest Path First......Page 777
9.3.2.4 OSPF-TE with Enhancements for GMPLS Support......Page 778
Link-State Information Dissemination......Page 779
Transparent Networks......Page 781
9.3.3.1 Optical User-Network Interface (UNI) and Network-Network Interface (NNI)......Page 782
9.3.3.2 Overview of the Resource Reservation Protocol......Page 785
9.3.3.3 RSVP with Traffic Engineering Extensions......Page 787
LSP Tunnel Establishment......Page 788
9.3.3.4 RSVP-TE with Enhancements for GMPLS Support......Page 789
9.3.3.5 Signaling for Protection and Restoration in Optical Networks......Page 790
9.4 Conclusions......Page 791
Bibliography......Page 793
10 Optical Packet-Switched Networks......Page 796
10.1 Optical Packet-Switched Network Architectures......Page 798
10.1.1 Unbuffered Networks......Page 799
10.1.2 Deflection Routing......Page 804
10.1.3 Performance Analysis of Deflection Routing......Page 806
Packet Loss in SP Routing......Page 807
Packet Loss in Limited Deflection Routing......Page 808
10.1.4.1 Buffered Nodes......Page 810
10.1.4.2 Dump-and-Insert Buffering......Page 814
10.1.5 Buffering and Wavelength Conversion: Time/Wavelength Domain Contention Resolution......Page 818
10.1.5.1 Switches with Tunable Wavelength Converters......Page 819
10.1.5.2 Shared Wavelength Converters......Page 821
10.1.6 Comparison of Contention Resolution Techniques for Asynchronous OPS Networks......Page 822
10.1.7 Hybrid Electronic and Optical Buffering......Page 824
Performance Analysis......Page 825
10.2 OPS Enabling Technologies......Page 827
10.2.3 Optical Switching......Page 828
10.2.6 Optical Buffering......Page 829
10.3.1 CORD Testbed......Page 831
10.3.2 KEOPS Testbed......Page 833
10.3.3 WASPNET Testbed......Page 836
10.4 Optical Burst Switching......Page 838
10.4.1 Just Enough Time Protocol......Page 841
10.4.2 Just In Time Protocol......Page 843
10.4.2.1 JIT Signaling Performance......Page 844
10.4.3 Contention Resolution in OBS Networks......Page 846
10.5 Optical Label Switching......Page 848
10.5.1 All-Optical Label Swapping......Page 849
10.5.3.1 Early OLS Testbed Demonstrations......Page 851
10.5.3.2 More Recent OLS Testbed Demonstrations......Page 853
10.6 Conclusions......Page 860
10.7 Problems......Page 862
Bibliography......Page 863
11.1 Business Drivers and Economics......Page 868
11.1.1 Cost Issues for WDM Point-to-Point Systems......Page 871
11.1.2 Cost Issues for WDM Rings......Page 872
11.1.3 Cost Issues for WDM Cross-Connect Networks......Page 873
11.1.4 Open versus Closed WDM Installations......Page 875
11.2.1 Optical Networks Technology Consortium......Page 878
11.2.3 European Multiwavelength Optical Network Trials......Page 879
11.2.6 The Importance of the Testbeds in Driving the Telecommunications Infrastructure......Page 880
11.3.1 Metro Network Unique Characteristics......Page 881
11.3.2 Defining the Metropolitan Networking Domain......Page 882
11.3.3.1 The Initial Vision......Page 884
11.3.3.2 What Has Happened Instead......Page 885
10-Gigabit Ethernet......Page 887
Multiservice Provisioning Platform......Page 889
11.3.4.3 Network Elements......Page 890
11.3.4.4 Metro WDM Network Deployments......Page 891
11.4.1 Current Considerations in Wide Area Network Architectures......Page 894
11.4.2 Some Recent Commercial Network Deployments......Page 896
11.5.2 Virtual Private Optical Networks......Page 898
11.5.3 Bandwidth Trading......Page 899
11.6 Conclusions......Page 901
Bibliography......Page 902
A.1 Graphs......Page 909
A.1.2 Eulerian Graphs......Page 912
A.1.4 Matchings in Graphs......Page 913
A.1.5 Graph Coloring......Page 914
A.1.7 Moore Bounds......Page 915
A.1.8 Max Flow–Min Cut......Page 916
A.2.1 Undirected Hypergraphs......Page 917
A.2.2 Directed Hypergraphs......Page 918
B Fixed Scheduling Algorithm......Page 919
B.1 Column/Row–Expansion Algorithm......Page 920
B.3 Column/Row–Compression Algorithm......Page 923
C.1 Random Processes......Page 924
C.2 Markov Processes......Page 925
C.3 Queues......Page 927
C.3.2 The M|G|1 Queue......Page 928
C.3.3 Little’s Formula......Page 929
D.1 The Multicommodity Flow Problem and Limiting Cuts......Page 930
D.2.1 Swap (X, Y)......Page 931
D.2.2 Limcut......Page 932
E.1 The Image Network......Page 933
E.2 The Min-Int Algorithm......Page 934
E.3 Minimum Interference......Page 935
F Synopsis of the SONET Standard......Page 936
G A Looping Algorithm......Page 940
Appendices A–G Bibliography......Page 942
Acronyms......Page 943
Index......Page 955