Algorithms for Next Generation Networks (eBook)

Endorsements 6
Foreword 7
Preface 10
Acknowledgements 13
Contents 14
List of Contributors 16
Part I Network Design 18
1 Design for Optimizability: Traffic Management of a Future Internet 19
1.1 Introduction 19
1.2 Traffic Management Today 21
1.2.1 Traffic Engineering 21
1.2.2 Pros and Cons of Traffic Management 23
1.3 Design Optimizable Protocols 23
1.3.1 Changing the Shape of the Constraint Set 24
1.3.2 Adding Variables to Decouple Constraints 26
1.3.3 Combining Objectives to Derive Protocols 28
1.4 Open Challenges in Traffic Management Optimization 30
1.4.1 Performance vs. Overhead Trade-Off 30
1.4.2 End-to-End Traffic Management 31
1.4.3 Placement of Functionality 32
1.5 Conclusions and Future Work 33
References 34
2 Valiant Load-Balancing: Building Networks That Can Support All Traffic Matrices 35
2.1 Introduction 35
2.1.1 The Wide Use of VLB 36
2.1.2 A Simple VLB Network 37
2.2 VLB in Heterogeneous Networks 38
2.3 Fault-Tolerance in a VLB Network 41
2.4 VLB for Peering Traffic 43
2.5 Discussions 44
References 45
3 Geometric Capacity Provisioning for Wavelength-Switched WDM Networks 47
3.1 Introduction 47
3.1.1 System Model 49
3.2 Wavelength-Granularity Switching 51
3.2.1 Asymptotic Analysis 52
3.2.2 Minimum Distance Constraints 53
3.2.3 Optimal Provisioning 55
3.2.4 Numerical Example 57
3.2.5 Non-IID Traffic 59
3.3 Conclusion 61
References 61
4 Spectrum and Interference Managementin Next-Generation Wireless Networks 63
4.1 Introduction 63
4.2 Review of Enabling Technologies 65
4.2.1 Contiguous and Non-contiguous Orthogonal Frequency Division Multiple Access 65
4.2.2 MIMO Signal Processing 65
4.3 Fractional Frequency Reuse 66
4.3.1 Concept Overview 66
4.3.2 Algorithm Overview 67
4.3.3 Algorithm Performance 69
4.4 Network MIMO 73
4.4.1 Algorithms 75
4.4.2 Simulation Results 78
4.5 Challenges in Taking Theory to Practice 79
4.6 Summary 80
References 80
5 Cross-Layer Capacity Estimation and Throughput Maximization in Wireless Networks 82
5.1 Introduction 82
5.2 Network Model 85
5.2.1 Interference Models 86
5.2.2 Network Flows 87
5.3 Capacity of Random Wireless Networks 88
5.3.1 Capacity Upper Bound 89
5.3.2 Lower Bound 91
5.4 Capacity of Arbitrary Wireless Networks 93
5.4.1 An Approximation Algorithm for MAXFLOW 93
5.4.1.1 Geometric Packing Based Necessary Conditions for Link Scheduling 94
5.4.1.2 Inductive Scheduling Algorithm 95
5.4.1.3 Link-Flow Stability: Sufficient Conditions 96
5.4.1.4 Scheduling End-to-End Flows 97
5.5 Dynamic Control for Network Stability 99
5.5.1 Network Layer Capacity Region 100
5.5.2 Dynamic Back-Pressure Algorithm 102
5.5.3 Analysis 103
5.5.4 Complexity Issues 105
5.6 Survey of Cross-Layer Throughput Estimation and Optimization in Wireless Networks 106
5.6.1 Scaling Laws for Random Networks 106
5.6.2 Estimating the Throughput Capacity 107
5.6.2.1 Linear Programming Techniques for Arrival Processes with Constant Bit Rate 107
5.6.2.2 Techniques for Admissible Stochastic Arrival Processes 108
5.6.2.3 Techniques for Adversarial Queuing Models 108
5.7 Open Problems 109
References 110
6 Resource Allocation Algorithms for the Next Generation Cellular Networks 114
6.1 Introduction 114
6.2 Cell Planning Problems 117
6.2.1 The Main New Factors in Planning Future Networks 119
6.2.2 On Discrete Location Problems in Combinatorial Optimization 120
6.2.3 Formulation and Background 121
6.2.4 The Interference Model 121
6.2.5 The Budgeted Cell-Planning Problem 123
6.2.6 How Well the Budgeted Cell Planning Problem (BCPP) Can Be Approximated? 123
6.2.7 The k4k-Budgeted Cell Planning Problem 124
6.2.8 An e-13e-1-Approximation Algorithm 125
6.2.8.1 The Client Assignment Problem 126
6.2.8.2 The Budgeted Maximum Assignment Problem 127
6.2.8.3 Approximating k4k-BCPP 128
6.2.9 The Minimum-Cost Cell Planning Problem 129
6.2.10 A Greedy O(logW)-Approximation Algorithm 131
6.2.11 Challenges and Open Problems 133
6.3 Cell Selection Problems 134
6.3.1 Model and Definitions 138
6.3.2 Approximating AoNDM and r-AoNDM Problems 138
6.3.3 A Cover-by-one 1-r2-r-Approximation Algorithm 139
6.3.4 Challenges and Open Problems 141
6.4 Concluding Remarks 142
References 142
7 Ethernet-Based Services for Next Generation Networks 145
7.1 Introduction 145
7.2 Carrier Ethernet Services Architecture 147
7.2.1 Ethernet Virtual Connection 148
7.2.2 Defining Ethernet Services 149
7.2.3 Ethernet Service Definitions 149
7.2.3.1 Ethernet Line (E-Line) Services 149
7.2.3.2 Ethernet LAN Services 150
7.2.3.3 Ethernet E-TREE Services 152
7.3 Ethernet Service Attributes 153
7.3.1 Ethernet Virtual Connection Type (EVC Type) 153
7.3.2 Class of Service Identifier (CoS ID) 156
7.3.2.1 Physical Port 156
7.3.2.2 Priority Code Point/User Priority 156
7.3.2.3 IP/MPLS DiffServ/IP TOS 157
7.3.2.4 Ethernet Control Protocols 157
7.3.3 Bandwidth Profile (BWP) 157
7.3.4 Traffic Descriptors 159
7.3.4.1 Frame Color and Token Disposition 159
7.3.4.2 Frame Coloring and Frame Disposition 159
7.3.5 Performance Service Attribute 160
7.3.5.1 Frame Loss 160
7.3.5.2 Frame Delay 161
7.3.5.3 Frame Delay Variation 161
7.3.5.4 Ethernet Quality of Service 162
7.4 Implementing Ethernet Transport Services 163
7.4.1 Addressing Ethernet as Dedicated Network Infrastructure 163
7.4.2 Addressing Ethernet as Switched Network Infrastructure 164
7.4.3 Addressing Ethernet Connectivity Service 166
7.4.4 Addressing Ethernet as a Service Interface 166
References 167
8 Overlay Networks: Applications, Coexistence with IP Layer, and Transient Dynamics 170
8.1 Introduction 170
8.1.1 Overlay Network Architecture 172
8.1.2 Challenges and Design Issues 173
8.2 Applications of Overlay Networks 174
8.3 Coexistence of Overlay and IP Layers 175
8.3.1 Equilibrium Behavior 176
8.3.2 Transient Behavior 176
8.3.3 Coping with Cross-Layer Interactions 178
8.4 Interactions Between Multiple CoexistingOverlay Networks 179
8.4.1 Interactions Leading to Suboptimal Equilibrium Point 180
8.4.2 Transient Overlay Network Protocol Interactions 180
8.4.2.1 Conditions for Traffic Oscillations 181
8.4.2.2 Analyzing Traffic Oscillations 183
8.4.3 Coping with Interactions Between Coexisting Overlays 187
8.5 Summary 187
References 188
Part II Network Operations 191
9 Hash-Based Techniques for High-Speed Packet Processing 192
9.1 Introduction 192
9.2 Background 193
9.2.1 Hash-Based Data Structures 194
9.2.1.1 Hash Functions 194
9.2.1.2 Bloom Filters and Their Variants 196
9.2.1.3 Hash Tables 200
9.2.2 Application Performance Measures and Memory Models 203
9.2.3 History of Hash-Based Techniques 205
9.3 Lookups in a Non-uniform Memory Model: On-Chip Summaries of Off-Chip Hash Tables 207
9.4 Lookups in a Uniform Memory Model: Hardware Hash Tables with Moves 211
9.4.1 The First Approach: The Power of One Move 211
9.4.2 The Second Approach: De-amortizing Cuckoo Hashing 213
9.5 Bloom Filter Techniques 214
9.5.1 Improved (Counting) Bloom Filters 214
9.5.2 Approximate Concurrent State Machines 217
9.5.3 More Applications of Bloom Filters 217
9.6 Measurement Applications Using Hash-Based Algorithms 220
9.6.1 Finding Heavy-Hitters and Flow Size Distributions 220
9.6.2 Measuring the Number of Flows on a Link 222
9.7 Conclusion 224
References 225
10 Fast Packet Pattern-Matching Algorithms 230
10.1 Motivation 230
10.2 Introduction to Regular Expressions 232
10.3 Traditional Regular Expression Matching Schemes 232
10.3.1 DFA 233
10.3.2 NFA 233
10.3.3 Lazy DFA 235
10.4 Regular Expression Matching in Network Scanning Applications 235
10.4.1 Patterns Used in Networking Applications 235
10.4.2 Analysis of Regular Expressions That Generates Large DFAs 237
10.4.2.1 DFAs of Quadratic Size 237
10.4.2.2 DFAs of Exponential Size 239
10.5 Regular Expression Rewriting Techniques 240
10.5.1 Rationale Behind Pattern Rewriting 240
10.5.2 Rewrite Rules for DFAs with Quadratic Size 242
10.5.3 Rewrite Rule for DFAs of Exponential Size 242
10.5.4 Guidelines for Pattern Writers 244
10.6 D2FA: Algorithms to Reduce DFA Space 245
10.7 Bifurcated, History-Augmented DFA Techniques 247
10.8 Summary 249
References 249
11 Anomaly Detection Approaches for Communication Networks 250
11.1 Introduction 250
11.2 Discrete Algorithms for Network Anomaly Detection 252
11.2.1 Heavy-Hitter Detection 253
11.2.2 Heavy-Change Detection 255
11.3 Statistical Approaches for Network Anomaly Detection 257
11.3.1 Model-Based Detection 258
11.3.1.1 Change-Point Detection 258
11.3.1.2 Kalman Filter 259
11.3.2 Model-Based Learning – Approximating an Assumed Model 259
11.3.2.1 Covariance Matrix Analysis 259
11.3.2.2 Wavelet Analysis 260
11.3.2.3 Information Theoretic Approaches 261
11.3.3 Statistical Learning for Anomaly Detection 262
11.3.3.1 Unsupervised Anomaly Detection 263
11.3.3.2 Learning with Additional Information 268
11.4 Challenges and Deployment Issues 269
References 270
12 Model-Based Anomaly Detection for a Transparent Optical Transmission System 273
12.1 Introduction 273
12.2 Background on Raman-Amplified Transmission Systems 275
12.3 Establishing Baseline Distributions for Alarm Decision Rules 277
12.3.1 The Ripple Measure as a Performance Metric 278
12.3.1.1 Prediction of Ripple via Simulation 278
12.3.2 Issues in Using Simulation to Generate Null Distributions 279
12.3.3 Experimental Design 279
12.3.4 Simulation Results & ANOVA
12.3.5 Derivation of Alarm Decision Rules 285
12.4 Anomaly Detection Using the Detailed Physical Model 287
12.4.1 Calibration Procedure for Detailed Physical Model 289
12.4.2 Detection of Poor Fit to Raman Gain Profile 290
12.4.3 Detection of Premature Signal Degradation and Pump Failure 291
12.5 Anomaly Detection Using the R-Beta Model 292
12.6 Conclusions 295
References 296
13 In-Network Monitoring 297
13.1 Introduction 298
13.2 Basic Monitoring Techniques and the Cost of Monitoring 299
13.3 End-to-End Aggregate QoS Monitoring 301
13.3.1 Autonomous Monitoring of Streams 303
13.3.1.1 Single Flow Analysis 305
13.3.2 Simulation Results 307
13.3.2.1 Single Flow Simulations 307
13.3.2.2 Multiple Flow Simulations 309
13.4 Continuous Monitoring of Network-Wide Aggregates 312
13.4.1 The Problem 314
13.4.2 Data Structures 314
13.4.3 The Execution Model 315
13.4.4 Ancillary Functions 315
13.4.5 The Algorithm 316
13.5 Refinements of the Generic Protocol for Tree-Based Aggregation 317
13.5.1 Continuous Monitoring of Aggregates with Performance Objectives 318
13.5.1.1 Problem Statement 318
13.5.1.2 Filter Computation 318
13.5.1.3 Evaluation Results 319
13.5.1.4 Related Work 321
13.5.2 Efficient Detection of Threshold Crossing 321
13.5.2.1 Problem Statement 321
13.5.2.2 Local Threshold and Hysteresis Mechanism 321
13.5.2.3 Local Threshold Recomputation 323
13.5.2.4 Evaluation Results 324
13.5.2.5 Related Work 325
References 326
14 Algebraic Approaches for Scalable End-to-End Monitoring and Diagnosis 328
14.1 Introduction 328
14.2 Related Work 331
14.2.1 End-to-End Monitoring 331
14.2.2 End-to-End Diagnosis 331
14.3 Models and Architecture 333
14.3.1 Algebraic Model 334
14.3.2 System Architecture 336
14.4 Tomography-Based Overlay Monitoring System (TOM) 337
14.4.1 Measurement Path Selection 337
14.4.2 Path Loss Rate Calculations 337
14.5 Least-Biased End-to-End Network Diagnosis System 338
14.5.1 Minimal Identifiable Link Sequence 338
14.5.2 MILSes in Undirected Graphs 340
14.5.3 MILSes in Directed Graphs 341
14.5.3.1 Special Properties for Directed Graphs 341
14.5.3.2 Practical Inference Methods for Directed Graphs 342
14.6 Evaluations 343
14.6.1 Scalability Analysis 344
14.6.1.1 Explanation from Internet Topology 346
14.6.2 Internet Experiments 346
14.6.2.1 Granularity of MILSes and Diagnosis 346
14.7 Conclusions 347
References 348
Part III Emerging Applications 350
15 Network Coding and Its Applications in Communication Networks 351
15.1 Introduction 351
15.1.1 Motivation 351
15.1.2 Related Work 354
15.2 Network Coding Fundamentals 354
15.2.1 Network Model 354
15.2.2 Encoding Model 356
15.2.3 Coding Advantage 358
15.3 Algebraic Framework 358
15.4 Required Field Size 363
15.5 Random Network Coding 366
15.6 Polynomial-Time Algorithm 367
15.7 Network Coding in Undirected Networks 371
15.8 Practical Implementation 373
15.8.1 Peer-to-Peer Networks 375
15.8.2 Wireless Networks 377
15.9 Conclusion 379
References 379
16 Next Generation Search 381
16.1 Introduction 381
16.2 Search in the Web 383
16.2.1 Text-Based Web Search 383
16.2.2 Link-Based Web Search 385
16.2.2.1 PageRank 385
16.2.2.2 HITS 386
16.3 Distributed Search 387
16.3.1 BlockRank 388
16.3.2 Distributed Computation of Ranking Scores 390
16.3.2.1 ServerRank 390
16.3.2.2 SiteRank 390
16.3.3 The JXP Method for Robust PageRank Approximation 391
16.3.3.1 Optimization: Light-Weight Merging of Local Graphs 393
16.3.3.2 Convergence Analysis 393
16.4 Social Search 394
16.4.1 Structure of Social Networks 395
16.4.2 Navigating in Small-World Graphs 396
16.4.3 Search in Social Tagging Systems 398
16.5 Other Topics 400
16.5.1 Searching the Live Web 400
16.5.1.1 Blog Search 400
16.5.1.2 News Search 403
16.5.2 Searching with Context 405
16.6 Conclusions 406
References 406
17 At the Intersection of Networks and Highly Interactive Online Games 410
17.1 Introduction 410
17.1.1 Game Genres 411
17.1.2 Communication Models 412
17.1.3 Potential for Collateral Damage 413
17.1.4 Chapter Outline 414
17.2 Phases of Network Activity Caused by First-Person Shooter Games 415
17.2.1 Server Discovery 415
17.2.2 Game Play 416
17.2.3 Content Download 416
17.3 Sensitivities of Game Players to Network Latency 417
17.3.1 Observed Impact of Latency 417
17.3.2 Mitigating Latency 418
17.4 Server Discovery Protocols 419
17.4.1 Counterstrike:Source Server Discovery 419
17.4.2 Reducing Probe Traffic during Counterstrike: SourceServer Discovery 422
17.4.2.1 Clustering, Calibration, and Optimized Probing 423
17.4.2.2 Illustrating AS-Based Optimization 424
17.4.2.3 Implementation Issues for AS-Based Optimization 425
17.4.3 Impact of Access Links on Server RTT Estimation 426
17.5 Measuring and Synthesizing Long- and Short-Term Traffic Patterns 428
17.5.1 Long-Timescale Game-Play and Server-Discovery Traffic 429
17.5.2 Short-Timescale Game-Play Traffic 431
17.5.3 Synthesizing Large Numbers of Players 433
17.5.4 Short-Timescale Server Discovery Traffic 435
17.6 Detection of Live Game Traffic 436
17.7 Conclusion 438
References 439
18 Wayfinding in Social Networks 442
18.1 Introduction 442
18.2 The Small-World Phenomenon 443
18.3 Kleinberg's Small-World Model: the Navigable Grid 445
18.4 Geography and Small Worlds 448
18.5 Variable Population Density and Rank-Based Friendship 451
18.6 Going Off the Grid 454
18.6.1 Non-Grid-Based Measures of Similarity 454
18.6.2 Simultaneously Using Many Different Notions of Similarity 456
18.6.3 From Birds of a Feather to Social Butterflies (of a Feather) 457
18.7 Discussion 458
References 461
Index 464