Design, measurement and management of large-scale IP networks: bridging the gap between theory and practice

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 9
Acknowledgments......Page 13
1 Introduction......Page 15
1.1 Skeleton of the book......Page 16
1.2 How to read this book......Page 17
2.1 What is the Internet?......Page 19
2.2 Maintaining end-to-end service through multiple ISPs: physical and logical interconnection agreements and the associated financial value......Page 21
2.3 Typical Tier-1 ISP network architecture: the Sprint IP backbone......Page 25
2.4 Overview of TCP/IP......Page 29
2.4.1 Intra-domain and inter-domain routing protocols......Page 32
2.5 Specifying requirements in managed IP networks: design and traffic engineering, monitoring and security operational criteria......Page 34
Part I Network monitoring and management......Page 37
3 The need for monitoring in ISP network design and management......Page 39
3.1 Current measurement capabilities......Page 40
3.2.1 Simple Network Management Protocol......Page 41
3.3 Monitoring the state of the routing protocols......Page 43
3.3.2 Path-level information......Page 44
3.4 Monitoring the traffic flow......Page 45
3.4.1 Flow-level information......Page 46
3.4.2 Packet-level information......Page 48
3.5.1 Packet-capture system architecture......Page 49
Data-rate requirements......Page 51
Timestamp requirements......Page 52
Remote administration requirements......Page 53
3.5.2 Packet capture on demand......Page 54
3.6.1 Research......Page 55
Traffic matrix......Page 56
Topology design......Page 57
Capacity planning and forecasting......Page 58
Data- and control-plane security......Page 59
3.7 Summary......Page 60
4 Understanding through-router delay......Page 61
4.1.1 Router architecture......Page 62
Timestamping of POS packets......Page 63
4.1.2 Experimental setup......Page 64
4.1.3 Packet matching......Page 65
4.2 Preliminary delay analysis......Page 67
4.2.1 System definition......Page 69
4.2.2 Delay statistics......Page 70
4.3.1 The fluid queue......Page 72
4.3.2 Simple router model......Page 73
4.3.3 Evaluation......Page 75
4.4 Understanding and reporting delay performance......Page 80
Statistics......Page 81
Origins......Page 82
4.4.2 Modeling busy periods......Page 84
4.4.3 Reporting busy-period statistics......Page 87
4.5 Micro-congestion episodes and their causes......Page 88
Bandwidth reduction......Page 89
4.5.2 Methodology and results......Page 90
4.5.3 Reduction in bandwidth......Page 92
4.5.4 Link multiplexing......Page 93
4.5.5 Flow burstiness......Page 95
4.6 Lessons learned......Page 98
5 Traffic matrices: measurement, inference and modeling......Page 99
5.1 What is an IP traffic matrix?......Page 100
5.1.2 The backbone network......Page 102
5.1.3 Identifying the egress node......Page 103
Centralized approach......Page 104
Toward distributed approaches......Page 105
5.1.5 TM overheads: a concrete example......Page 106
5.1.6 Storage, communications and computational overheads......Page 107
5.2 TM estimation from SNMP link counts......Page 108
5.3.2 Tomogravity method......Page 112
5.3.3 Route change method......Page 114
5.3.4 Fanout method......Page 115
5.3.5 Principal components method......Page 117
5.3.6 Kalman-filtering-based method......Page 119
Prediction step......Page 120
Estimation step......Page 121
5.4 Performance analysis......Page 122
5.4.1 Spatial and temporal errors......Page 123
5.4.2 Over-modeling......Page 126
5.4.3 Measurement overhead......Page 128
5.4.4 Handling dynamic changes in the TM elements......Page 130
5.5 Lessons learned......Page 135
Part II Network design and traffic engineering......Page 137
6.1 Overview of IP-over-WDM technology......Page 139
6.2 Network design: principles and processes......Page 142
6.2.1 Edge versus core: from routers to PoPs......Page 143
Survivability to physical failures......Page 144
Survivability to logical failures......Page 145
Topology and routing protocol......Page 147
6.3 Network design process: sketching out our methodology......Page 148
7 Topology design resilient to long-lived failures......Page 150
7.1 Fault-tolerant logical topology design problem......Page 152
Notation......Page 153
Constraints......Page 154
Extension to shortest-path routing......Page 156
7.3 Mapping between physical and logical topology: GDAP......Page 158
GDAP algorithm......Page 159
7.4.1 General description of Tabu Search......Page 160
Moves and neighborhood generation......Page 161
7.4.3 TabuFLTDP pseudo-code......Page 162
7.6 Numerical results......Page 164
7.7 Lessons learned......Page 171
8.1 Introduction......Page 173
Network protection and disjointness......Page 176
Delay constraints......Page 178
8.2.2 Approach......Page 179
Delay requirements......Page 180
8.3.1 Problem definition......Page 181
Decision variables......Page 182
Constraints......Page 183
Objective function......Page 184
Pre-computation step......Page 185
Tabu list......Page 186
8.4.1 Topologies and metrics......Page 187
8.4.2 Jointness and maximum delay......Page 189
8.4.3 Impact of priorities......Page 191
8.4.4 Improving the network design......Page 192
8.5 Lessons learned......Page 194
9 Performance enhancement and resilience to short-lived failures via routing optimization......Page 195
9.1 Link-weight selection problem......Page 198
9.2 ILP for general routing problem......Page 199
Constraints......Page 200
Initial solution......Page 203
Tabu list......Page 204
9.4.1 North American and European Sprint IP backbones......Page 205
Gravity model......Page 206
9.4.3 Reducing the size of the search space......Page 207
9.5 Applications......Page 209
9.5.1 Selecting the range of allowable link weights......Page 210
9.5.2 Aiding topology design......Page 211
9.6 Lessons learned......Page 213
10 Measuring the shared fate of IGP engineering: considerations and take-away......Page 215
10.1 Problem description......Page 216
10.2 Collection of all required inputs......Page 219
10.3 Analysis......Page 221
10.4.1 Scope of problem......Page 222
10.4.2 Impact of hot-potato shifts on IGP engineering......Page 223
10.4.3 Impact of IGP engineering on neighbors......Page 226
10.4.4 Impact of more frequent changes......Page 228
10.5 Lessons learned......Page 230
11.1 Objectives......Page 231
11.2.1 Data collected and analysis......Page 234
11.2.2 Initial observations......Page 235
11.3.1 Wavelet MRA overview......Page 239
11.3.2 MRA application on inter-PoP aggregate demands......Page 240
11.3.3 Analysis of variance......Page 242
11.3.5 Implications for modeling......Page 245
11.4.1 Overview of linear time series models......Page 247
11.4.2 Time series analysis of the long-term trend and deviation......Page 248
11.4.3 Models for l(j) and dt3(j)......Page 249
11.5 Evaluation of forecasts......Page 251
11.6 Forecasting a dynamic environment......Page 253
11.6.1 Identification of “extreme” forecasts......Page 255
11.6.2 Uncertainty in forecasts as a network artifact......Page 257
Uncertainty in forecasts......Page 258
11.7 Lessons learned......Page 260
Part III From bits to services......Page 263
12 From bits to services: information is power......Page 265
12.1 Building intelligence: extracting information from bits......Page 266
12.2 Bridging the gap between network infrastructure and applications: cleaning the bits......Page 268
Denial of Service......Page 269
Malicious routes and bogus prefixes......Page 270
Firewalls and IDSs: merits and weaknesses......Page 271
12.3 Summary......Page 273
13.1 State of the art and context......Page 275
Tunability......Page 276
13.2 Background......Page 277
13.3.1 Payload packet traces......Page 278
13.3.2 Payload classification......Page 280
13.3.3 Application breakdown......Page 282
13.4.1 Overview of BLINC......Page 283
Examining the social behavior of single hosts......Page 284
Detecting communities of hosts......Page 285
“Perfect” cliques: a hint for malicious flows......Page 286
Conclusion and rules......Page 287
13.4.3 Classification at the functional level......Page 288
Conclusion and rules......Page 289
13.4.4 Classification at the application level......Page 290
Heuristic 2: using the cardinality of sets......Page 293
Heuristic 6: non-payload flows......Page 294
BLINC classifies the majority of the traffic with high accuracy......Page 295
High per-application accuracy......Page 296
13.5.2 Fine-tuning BLINC......Page 297
Non-payload flows......Page 298
Creating the graphlets......Page 300
13.6.2 Limitations......Page 301
Practical impact and the grand vision......Page 302
14 Classification of multimedia hybrid flows in real time......Page 304
Video streams......Page 307
14.1.2 Data sets......Page 308
14.2.1 Challenges......Page 309
14.2.2 Intuition and approach......Page 311
14.2.3 Chat traffic versus file transfer traffic in hybrid flows......Page 313
14.3.1 Training phase: FE......Page 314
14.3.2 Training phase: VSG......Page 315
Subspace bases identification......Page 316
14.3.3 Detection phase: FE......Page 317
14.3.4 Detection phase: VCL......Page 318
14.4.1 Feature extractor module......Page 319
14.4.2 Voice and video subspace generator......Page 320
14.4.3 Overall system......Page 321
14.5 Lessons learned......Page 323
15 Detection of data plane malware: DoS and computer worms......Page 324
15.1 Understanding denial of service......Page 325
15.2 Understanding worms......Page 328
15.2.1 Target discovery......Page 329
15.2.3 Activation......Page 330
15.2.4 Intent of the attack......Page 331
15.3.1 Worms......Page 332
15.3.2 Denial of Service......Page 333
15.4 NBA-DS: logical architecture and network deployment......Page 335
15.5.1 Classifier and Histogram Extraction Module......Page 337
15.5.2 PMER/PJER Computation Module......Page 340
Single global metric......Page 341
15.5.3 Baselining and Alerting Module......Page 342
15.5.4 Selecting the flows that matter: Flow-Filter Mask Generation Module......Page 344
15.5.5 Example of Packet Payload Module: worm fingerprinting......Page 345
15.6 Case study: worm attacks......Page 347
15.6.2 PMER versus PJER metric......Page 348
15.6.3 Low-rate worm......Page 350
15.6.4 Fingerprinting......Page 352
15.7 Lessons learned......Page 354
16 Detection of control-plane anomalies: beyond prefix hijacking......Page 355
16.1 Brief introduction to the Border Gateway Protocol......Page 357
16.2 Vulnerabilities, consequences and common practices......Page 359
16.3 Related work......Page 361
16.4 Detection system architecture......Page 362
16.5.1 Collecting routing information objects......Page 363
16.5.2 Bogus routes detection algorithm......Page 364
16.5.4 Justifying the detection algorithm......Page 365
16.6.1 Removing transient routing information objects......Page 367
Attacker behavior heuristics......Page 368
Common-practice heuristics......Page 369
16.6.3 Event-base clustering and calibration......Page 370
Thresholds for legitimate objects......Page 371
Observation-window size......Page 372
Validation metrics......Page 373
Heuristics for inferring prefix-originAS associations......Page 374
Evaluation metrics......Page 375
Baseline evaluation......Page 376
Impact of number of views on detection performance......Page 377
Evaluation with documented incidents......Page 378
16.8 Lessons learned......Page 379
Appendix A: How to link original and measured flow characteristics when packet sampling is used: bytes, packets and flows......Page 381
A.1 From original to measured data streams: average number of total flows and their duration......Page 382
A.3 From measured to original data streams: total number of original TCP flows and their average size......Page 383
B.1 UDP bit strings......Page 385
B.2 TCP bit strings......Page 386
Appendix C: BLINC implementation details......Page 389
Appendix D: Validation of direction-conforming rule......Page 393
Other links......Page 394
References......Page 396
Index......Page 407