Survivable Optical WDM Networks (eBook)

Canhui (Sam) Ou received a Ph.D. degree from the University of California, Davis, in 2004. His technical interests include WDM networks, MPLS, optical Ethernet, and FTTx. He is a Principal Member of Technical Staff at SBC Communications, Inc. He worked at Sprint Advanced Technology Laboratories and Fujitsu Laboratories of America as an intern. Biswanath Mukherjee received a Ph.D. degree from University of Washington, Seattle, in 1987. In 1987, he joined the University of California, Davis, where he has been Professor of computer science since 1995, and served as Chairman of computer science during 1997-2000. He is author of Optical Communication Networks book. He is a Member of the Board of Directors of IPLocks, a Silicon Valley startup company. He has consulted for and served on the Technical Advisory Board of a number of startup companies in optical networking. His research interests include lightwave networks, network security, and wireless networks. Dr. Mukherjee is winner of the 2004 Distinguished Graduate Mentoring Award from UC Davis. He serves or has served on the Editorial Boards of the IEEE/ACM Transactions on Networking, IEEE Network, ACM/Baltzer Wireless Networks (WINET), Photonic Network Communications, and others. He also served as Editor-at-Large for optical networking and communications for the IEEE Communications Society. He served as the Technical Program Chair of the IEEE INFOCOM’96 Conference.

DISCLAIMER 6
Dedication Page 7
Table of Contents 8
List of Figures 13
Preface 18
The Topic 18
Intended Audience 19
Organization of the Book 19
Feedback 20
Acknowledgments 21
Chapter 1 INTRODUCTION 23
1.1 Optical Networking 23
1.1.1 Telecommunication Networks 23
1.1.2 Wavelength-Routed WDM Mesh Networks 24
1.1.3 Survivable WDM Mesh Networks 25
1.2 An Overview of the Book 27
1.2.1 Shared-Path Protection 27
1.2.2 Sub-Path Protection for Scalability and Fast Recovery 27
1.2.3 Segment Protection 27
1.2.4 Survivable Traffic Grooming-Dedicated Protection 28
1.2.5 Survivable Traffic Grooming-Shared Protection 28
1.2.6 Survivable Virtual Concatenation for Data over SONET/SDH 29
Chapter 2 SHARED-PATH PROTECTION FOR RESOURCE EFFICIENCY 30
2.1 Introduction 30
2.2 Problem Statement and Complexity Analysis 32
2.2.1 Problem Statement 32
2.2.2 ComplexityAnalysis 34
2.3 Compute A FEasible Solution (CAFES) 35
2.3.1 Trap Topology 36
2.3.2 Backup-Sharing-Caused Trap 36
2.4 Optimization (OPT) 37
2.5 Illustrative Numerical Results 41
2.5.1 Blocking Probability 42
2.5.2 Percentage of Unreachable Blocking 43
2.5.3 Resource Overbuild 44
2.5.4 Average Hop Distance 44
2.6 Conclusion 45
APPENDIX 2.A: NP-Completeness of DSPLP Problem 46
Chapter 3 SUB-PATHPROTECTIONFORSCALABILITYAND FAST RECOVERY 50
3.1 Introduction 50
3.1.1 Related Work 50
3.1.2 Multi-Domain Optical Networks and Our Proposal 52
3.1.3 Organization 53
3.2 Sub-Path Protection 53
3.2.1 An Illustrative Example 53
3.2.2 Different Cases 54
3.2.3 Domain-Border-Node (DBN) Failures 55
3.2.4 Problem Statement 56
3.2.5 Proof of NP-Completeness 57
3.3 ILP Formulation for RWA with Sub-Path Protection 58
3.3.1 Notations 59
3.3.2 Sub-Path Protection: Split ILP Formulation 59
3.3.2.1 Part I: Routing 59
3.3.2.2 Part II: Wavelength Assignment 62
3.3.3 Equivalence of the Split ILP and the Original Problem 64
3.4 Heuristic 64
3.4.1 Phase 1: Find Shortest Path Pair for Each Lightpath with Respect to Domain Constraints 65
3.4.2 Phase 2: Wavelength Assignment 67
3.4.3 Phase 3: Optimization 67
3.4.4 Complexity 70
3.5 Results and Discussions 70
3.5.1 Recovery Time 71
3.5.2 Survivability 73
3.5.3 Scalability 74
3.5.4 Resource Utilization 75
3.6 Conclusion 78
APPENDIX 3.A: NP-Completeness of RWA for Shared-Path Protection 78
APPENDIX 3.B: NP-Completeness of Optimal Backup Routing (OBR) 80
Chapter 4 SEGMENT PROTECTION FOR BANDWIDTH EFFICIENCY AND DIFFERENTIATED QUALITY OF PROTECTION 81
4.1 Introduction 81
4.2 Generalized Segment Protection 82
4.2.1 Generalized Segment Protection 82
4.2.2 The GSP Heuristic 84
4.2.2.1 Notations 84
4.2.2.2 GSP Heuristic 85
4.2.2.3 Computational Complexity 86
4.2.3 Illustrative Numerical Results 88
4.2.3.1 Blocking Probability 88
4.2.3.2 Performance Gain 90
4.2.3.3 Protection-Switching Time 90
4.2.3.4 Controland Management Complexity 91
4.2.3.5 Resource Efficiency 92
4.3 Providing Differentiated Quality of Protection (QoP) Based on Generalized Segment Protection 93
4.3.1 Motivation 94
4.3.2 GSP_QoP Heuristic 95
4.3.3 Illustrative Numerical Results 97
4.3.3.1 Blocking probability under different values of E 97
4.3.3.2 Blocking probability under different values of H b 100
4.3.3.3 Blocking probability for Iightpath requests with differentiated QoP requirements 101
4.3.3.4 Blocking probability for different values of H 102
4.4 Conclusion 102
Chapter 5 SURVIVABLE TRAFFIC GROOMINGDEDICATED PROTECTION 105
5.1 Introduction 105
5.1.1 Traffic Grooming 106
5.1.2 Lightpath Protection 106
5.1.3 Survivable Traffic Grooming 107
5.1.4 Our Proposal 107
5.2 Grooming-Node Architecture 108
5.3 Problem Statement 109
5.4 Proposed Approaches 109
5.4.1 Protection-at-Lightpath (PAL) Level 110
5.4.1.1 Basic idea 110
5.4.1.2 Example 110
5.4.2 Protection-at-Connection (PAC) Level 111
5.4.2:1 Basic idea 111
5.4.2.2 Example 112
5.4.3 PAL vs. PAC: A Qualitative Comparison 112
5.4.3.1 Routing 112
5.4.3.2 Solution space 113
5.4.3.3 Operational complexity 114
5.5 PAL Heuristic 114
5.5.1 Problem Complexity 114
5.5.2 PAL Heuristic 115
5.5.3 Explanation 115
5.5.4 Optimality 117
5.5.5 Variations 117
5.5.6 Computational Complexity 117
5.6 PAC Heuristic 117
5.6.1 Grooming-Node Modeling and Network-State Representation 118
5.6.2 Route Computation 119
5.6.3 Lightpath-Setup Strategy 120
5.6.4 Computational Complexity 122
5.7 Illustrative Numerical Results 122
5.7.1 Bandwidth-Blocking Ratio (BBR) 124
5.7.1.1 PAL vs. PAC 124
5.7.1.2 Impact of grooming capacity on PAL 124
5.7.1.3 Impact of grooming capacity on PAC 124
5.7.2 Resource Utilization 124
5.7.2.1 Grooming-port utilization 125
5.7.2.2 Wavelength utilization 126
5.7.2.3 Lightpath utilization 127
5.7.3 Resource-Efficiency Ratio (RER) 127
5.7.3.1 Definition 127
5.7.3.2 Wavelength efficiency 128
5.7.3.3 Grooming-port efficiency 128
5.7.3.4 Tradeoff between wavelengths and grooming ports 128
5.7.4 Effect of Different Parameters 130
5.7.4.1 Cost-slack parameter d in PAL 130
5.7.4.2 Threshold t in PAC 131
5.8 Conclusion 132
APPENDIX 5.A: NP-Completeness of WDM-PAC 132
Chapter 6 SURVIVABLE TRAFFIC GROOMINGSHARED PROTECTION 134
6.1 Problem Statement 134
6.2 Proposed Schemes 135
6.2.1 Protection-at-Lightpath (PAL) Level 135
6.2.1.1 Basic idea 135
6.2.1.2 Example 136
6.2.2 Mixed Protection-at-Connection (MPAC) Level 138
6.2.2.1 Basic idea 138
6.2.2.2 Example 138
6.2.3 Separate Protection-at-Connection (SPAC) Level 139
6.2.3.1 Basic idea 139
6.2.3.2 Example 139
6.2.4 A Qualitative Comparison 140
6.2.4.1 Routing 140
6.2.4.2 Backup sharing 141
6.2.4.3 Operational complexity 143
6.3 Heuristic Algorithms 143
6.3.1 MPAC Heuristic 143
6.3.1.1 Backup-sharing measurement 144
6.3.1.2 Grooming-node modeling and network-state representation 144
6.3.1.3 Route computation 145
6.3.1.4 Modified algorithm for computing K distinct loopless paths 146
6.3.1.5 Computational complexity 149
6.3.2 SPAC Heuristic 149
6.3.2.1 Backup-sharing measurement 149
6.3.2.2 Route computation 149
6.3.3 PAL Heuristic 150
6.3.3.1 Backup-sharing measurement 150
6.3.3.2 Network-state representation 150
6.3.3.3 Route computation 151
6.3.3.4 Computational complexity 152
6.4 Illustrative Numerical Results 154
6.4.1 Bandwidth-Blocking Ratio 154
6.4.2 Resource Utilization 156
6.4.2.1 Grooming-port utilization 156
6.4.2.2 Wavelength utilization 157
6.4.3 Resource-Efficiency Ratio 158
6.4.3.1 Definition 158
6.4.3.2 Wavelength efficiency 158
6.4.3.3 Grooming-port efficiency 159
6.4.3.4 Tradeoff between wavelengths and grooming ports 159
6.4.4 Effects of Different Parameters 160
6.5 Conclusion 161
Chapter 7 SURVIVABLE VIRTUAL CONCATENATION FOR DATA OVER SONET/SDH 163
7.1 Introduction 163
7.1.1 Next-Generation SONET/SDH Technologies 163
7.1.2 Motivation for Survivable DoS 165
7.1.3 Our Contribution 166
7.1.4 Organization 166
7.2 Protecting Individual VCG Member (PIVM) 167
7.2.1 Basic Idea 167
7.2.2 An Example 167
7.2.3 Route Computation: General Case 168
7.2.3.1 Notations 168
7.2.3.2 Problem Statement 169
7.2.3.3 The PIVM Heuristic 169
7.3 Provisioning fast REstorable VCG (PREV) 171
7.3.1 Basic Idea 171
7.3.2 An Example 171
7.3.3 Pre-Select a Backup Path for Every Node Pair 172
7.3.4 Route Computation 174
7.3.4.1 Problem Formulation 174
7.3.4.2 The PREY Algorithm 175
7.4 Route Computation with Extensions to Control the Number of VCG Members 178
7.5 Performance: PIVM vs. PREV 179
7.5.1 Bandwidth-Blocking Ratio 179
7.5.2 Resource Overbuild 180
7.5.3 Fault-Recovery Time 181
7.5.3.1 PIVM 181
7.5.3.2 PREY 182
7.5.4 Impact of VCG Size 183
7.6 Conclusion 184
APPENDIX 7.A: NP-Completeness of the CMCMP Problem 185
References 189
Index 198