Network algorithmics : an interdisciplinary approach to designing fast networked devices

CONTENTS......Page 7
PART I The Rules of the Game......Page 25
1.1 The Problem: Network Bottlenecks......Page 27
1.1.1 Endnode Bottlenecks......Page 28
1.1.2 Router Bottlenecks......Page 29
1.2 The Techniques: Network Algorithmics......Page 31
1.2.1 Warm-up Example: Scenting an Evil Packet......Page 32
1.2.3 Thinking Algorithmically......Page 33
1.2.4 Refining the Algorithm: Exploiting Hardware......Page 34
1.2.5 Cleaning Up......Page 35
1.2.6 Characteristics of Network Algorithmics......Page 37
1.3 Exercise......Page 39
2 Network Implementation Models......Page 40
2.1.2 Abstract Protocol Model......Page 41
2.1.3 Performance Environment and Measures......Page 43
2.2.1 Combinatorial Logic......Page 45
2.2.2 Timing and Power......Page 46
2.2.3 Raising the Abstraction Level of Hardware Design......Page 47
2.2.4 Memories......Page 49
2.2.5 Memory Subsystem Design Techniques......Page 53
2.2.6 Component-Level Design......Page 54
2.2.7 Final Hardware Lessons......Page 55
2.3.1 Endnode Architecture......Page 56
2.3.2 Router Architecture......Page 58
2.4.1 Uninterrupted Computation via Processes......Page 63
2.4.2 Infinite Memory via Virtual Memory......Page 65
2.4.3 Simple I/O via System Calls......Page 67
2.6 Exercises......Page 68
3.1 Motivating the Use of Principles - Updating Ternary Content-Addressable Memories......Page 74
3.2 Algorithms versus Algorithmics......Page 78
3.3.1 Systems Principles......Page 80
3.3.2 Principles for Modularity with Efficiency......Page 85
3.3.3 Principles for Speeding Up Routines......Page 87
3.4 Design versus Implementation Principles......Page 89
3.5 Caveats......Page 90
3.5.1 Eight Cautionary Questions......Page 92
3.7 Exercises......Page 94
4 Principles in Action......Page 97
4.1 Buffer Validation of Application Device Channels......Page 98
4.2 Scheduler for Asynchronous Transfer Mode Flow Control......Page 100
4.3 Route Computation Using Dijkstra\'s Algorithm......Page 101
4.4 Ethernet Monitor Using Bridge Hardware......Page 104
4.5 Demultiplexing in the X-Kernel......Page 105
4.6 Tries with Node Compression......Page 107
4.7 Packet Filtering in Routers......Page 109
4.8 Avoiding Fragmentation of Link State Packets......Page 111
4.9 Policing Traffic Patterns......Page 114
4.10 Identifying a Resource Hog......Page 116
4.11 Getting Rid of the TCP Open Connection List......Page 117
4.12 Acknowledgment Withholding......Page 120
4.13 Incrementally Reading a Large Database......Page 122
4.14 Binary Search of Long Identifiers......Page 124
4.15 Video Conferencing via Asynchronous Transfer Mode......Page 126
PART II Playing with Endnodes......Page 129
5 Copying Data......Page 131
5.1 Why Data Copies......Page 133
5.2.1 Exploiting Adaptor Memory......Page 135
5.2.2 Using Copy-on-Write......Page 137
5.2.3 Fbufs: Optimizing Page Remapping......Page 139
5.2.4 Transparently Emulating Copy Semantics......Page 143
5.3 Avoiding Copying Using Remote DMA......Page 145
5.3.1 Avoiding Copying in a Cluster......Page 146
5.3.2 Modern-Day Incarnations of RDMA......Page 147
5.4.1 Shared Memory......Page 149
5.4.2 IO-Lite: A Unified View of Buffering......Page 150
5.4.3 Avoiding File System Copies via I/O Splicing......Page 152
5.5 Broadening beyond Copies......Page 153
5.6.1 Using Caches Effectively......Page 155
5.7 Conclusions......Page 159
5.8 Exercises......Page 161
6 Transferring Control......Page 163
6.1 Why Control Overhead?......Page 165
6.2 Avoiding Scheduling Overhead in Networking Code......Page 167
6.2.1 Making User-Level Protocol Implementations Real......Page 168
6.3 Avoiding Context-Switching Overhead in Applications......Page 170
6.3.1 Process per Client......Page 171
6.3.2 Thread per Client......Page 172
6.3.4 Event-Driven Server with Helper Processes......Page 174
6.3.5 Task-Based Structuring......Page 175
6.4.1 A Server Mystery......Page 177
6.4.2 Existing Use and Implementation of Select()......Page 178
6.4.3 Analysis of Select()......Page 179
6.4.4 Speeding Up Select() without Changing the API......Page 181
6.4.5 Speeding Up Select() by Changing the API......Page 182
6.5 Avoiding System Calls......Page 183
6.5.1 The Virtual Interface Architecture (VIA) Proposal......Page 186
6.6 Reducing Interrupts......Page 187
6.6.1 Avoiding Receiver Livelock......Page 188
6.7 Conclusions......Page 189
6.8 Exercises......Page 190
7.1 Why Timers?......Page 193
7.2 Model and Performance Measures......Page 195
7.3 Simplest Timer Schemes......Page 196
7.4 Timing Wheels......Page 197
7.5 Hashed Wheels......Page 199
7.6 Hierarchical Wheels......Page 200
7.7 BSD Implementation......Page 202
7.8 Obtaining Fine-Granularity Timers......Page 203
7.9 Conclusions......Page 204
7.10 Exercises......Page 205
8 Demultiplexing......Page 206
8.2 Goals......Page 208
8.3 CMU/Stanford Packet Filter: Pioneering Packet Filters......Page 209
8.4 Berkeley Packet Filter: Enabling High-Performance Monitoring......Page 210
8.5 Pathfinder: Factoring Out Common Checks......Page 213
8.6 Dynamic Packet Filter: Compilers to the Rescue......Page 216
8.8 Exercises......Page 219
9 Protocol Processing......Page 221
9.1 Buffer Management......Page 222
9.1.1 Buffer Allocation......Page 223
9.1.2 Sharing Buffers......Page 225
9.2 Cyclic Redundancy Checks and Checksums......Page 227
9.2.1 Cyclic Redundancy Checks......Page 228
9.2.2 Internet Checksums......Page 231
9.3 Generic Protocol Processing......Page 233
9.3.1 UDP Processing......Page 236
9.4 Reassembly......Page 237
9.4.1 Efficient Reassembly......Page 238
9.5 Conclusions......Page 240
9.6 Exercises......Page 241
PART III Playing with Routers......Page 243
10 Exact-Match Lookups......Page 245
10.1 Challenge 1: Ethernet under Fire......Page 246
10.2 Challenge 2: Wire Speed Forwarding......Page 248
10.3.1 Scaling via Hashing......Page 252
10.3.2 Using Hardware Parallelism......Page 254
10.4 Summary......Page 255
10.5 Exercise......Page 256
11 Prefix-Match Lookups......Page 257
11.1.1 Prefix Notation......Page 258
11.1.2 Why Variable-Length Prefixes?......Page 259
11.1.3 Lookup Model......Page 260
11.2.1 Threaded Indices and Tag Switching......Page 262
11.2.2 Flow Switching......Page 264
11.2.3 Status of Tag Switching, Flow Switching, and Multiprotocol Label Switching......Page 265
11.3.2 Ternary Content-Addressable Memories......Page 266
11.4 Unibit Tries......Page 267
11.5 Multibit Tries......Page 269
11.5.1 Fixed-Stride Tries......Page 270
11.5.2 Variable-Stride Tries......Page 271
11.6 Level-Compressed (LC) Tries......Page 274
11.7 Lulea-Compressed Tries......Page 276
11.8.1 Tree Bitmap Ideas......Page 279
11.8.2 Tree Bitmap Search Algorithm......Page 280
11.9 Binary Search on Ranges......Page 281
11.10 Binary Search on Prefix Lengths......Page 283
11.11 Memory Allocation in Compressed Schemes......Page 285
11.11.1 Frame-Based Compaction......Page 286
11.12 Lookup-Chip Model......Page 287
11.13 Conclusions......Page 289
11.14 Exercises......Page 290
12 Packet Classification......Page 294
12.1 Why Packet Classification?......Page 295
12.2 Packet-Classification Problem......Page 297
12.3 Requirements and Metrics......Page 299
12.4.2 Caching......Page 300
12.4.4 Passing Labels......Page 301
12.5.1 Fast Searching Using Set-Pruning Trees......Page 302
12.5.3 The Best of BothWorlds: Grid of Tries......Page 305
12.6.1 Geometric View of Classification......Page 308
12.6.3 Beyond Two Dimensions: The Good News......Page 310
12.7 Extending Two-Dimensional Schemes......Page 311
12.8 Using Divide-and-Conquer......Page 312
12.9 Bit Vector Linear Search......Page 313
12.10 Cross-Producting......Page 316
12.11 Equivalenced Cross-Producting......Page 317
12.12 Decision Tree Approaches......Page 320
12.13 Conclusions......Page 323
12.14 Exercises......Page 324
13 Switching......Page 326
13.1 Router versus Telephone Switches......Page 328
13.3 Router History: From Buses to Crossbars......Page 329
13.4 The Take-a-Ticket Crossbar Scheduler......Page 331
13.5 Head-of-Line Blocking......Page 335
13.6 Avoiding Head-of-Line Blocking via Output Queuing......Page 336
13.7 Avoiding Head-of-Line Blocking by Using Parallel Iterative Matching......Page 338
13.8 Avoiding Randomization with iSLIP......Page 340
13.8.1 Extending iSLIP to Multicast and Priority......Page 344
13.8.2 iSLIP Implementation Notes......Page 346
13.9 Scaling to Larger Switches......Page 347
13.9.2 Clos Networks for Medium-Size Routers......Page 348
13.9.3 Benes Networks for Larger Routers......Page 352
13.10.1 Using Bit Slicing for Higher-Speed Fabrics......Page 357
13.10.2 Using Short Links for Higher-Speed Fabrics......Page 358
13.10.3 Memory Scaling Using Randomization......Page 359
13.11 Conclusions......Page 360
13.12 Exercises......Page 361
14 Scheduling Packets......Page 363
14.1 Motivation for Quality of Service......Page 364
14.2 Random Early Detection......Page 366
14.3 Token Bucket Policing......Page 369
14.4 Multiple Outbound Queues and Priority......Page 370
14.5 A Quick Detour into Reservation Protocols......Page 371
14.6.1 The Parochial Parcel Service......Page 372
14.6.2 Deficit Round-Robin......Page 374
14.6.3 Implementation and Extensions of Deficit Round-Robin......Page 375
14.7 Schedulers That Provide Delay Guarantees......Page 378
14.8 Scalable Fair Queuing......Page 382
14.8.2 Edge Aggregation......Page 383
14.8.3 Edge Aggregation with Policing......Page 384
14.10 Exercises......Page 385
15 Routers as Distributed Systems......Page 386
15.1 Internal Flow Control......Page 387
15.1.1 Improving Performance......Page 388
15.1.2 Rescuing Reliability......Page 389
15.2.1 Improving Performance......Page 392
15.2.2 Rescuing Reliability......Page 393
15.3 Asynchronous Updates......Page 395
15.3.1 Improving Performance......Page 396
15.4 Conclusions......Page 397
15.5 Exercises......Page 398
PART IV Endgame......Page 401
16 Measuring Network Traffic......Page 403
16.1.1 Why Counting Is Hard......Page 405
16.2 Reducing SRAM Width Using DRAM Backing Store......Page 406
16.3 Reducing Counter Width Using Randomized Counting......Page 408
16.4 Reducing Counters Using Threshold Aggregation......Page 409
16.5 Reducing Counters Using Flow Counting......Page 411
16.6 Reducing Processing Using Sampled NetFlow......Page 412
16.7 Reducing Reporting Using Sampled Charging......Page 413
16.8 Correlating Measurements Using Trajectory Sampling......Page 414
16.9 A Concerted Approach to Accounting......Page 416
16.10 Computing Traffic Matrices......Page 417
16.10.2 Approach 2: Per-Prefix Counters......Page 418
16.11 Sting as an Example of Passive Measurement......Page 419
16.12 Conclusion......Page 420
16.13 Exercises......Page 421
17 Network Security......Page 423
17.1 Searching for Multiple Strings in Packet Payloads......Page 425
17.1.1 Integrated String Matching Using Aho–Corasick......Page 426
17.1.2 Integrated String Matching Using Boyer–Moore......Page 427
17.2 Approximate String Matching......Page 429
17.3 IP Traceback via Probabilistic Marking......Page 430
17.4 IP Traceback via Logging......Page 433
17.4.1 Bloom Filters......Page 434
17.4.2 Bloom Filter Implementation of Packet Logging......Page 436
17.5 Detecting Worms......Page 437
17.7 Exercises......Page 439
18 Conclusions......Page 441
18.1.1 Endnode Algorithmics......Page 442
18.1.2 Router Algorithmics......Page 443
18.1.3 Toward a Synthesis......Page 444
18.2.1 Interdisciplinary Thinking......Page 447
18.2.2 Systems Thinking......Page 448
18.2.3 Algorithmic Thinking......Page 449
18.3 Network Algorithmics and Real Products......Page 451
18.4.1 New Abstractions......Page 453
18.4.2 New Connecting Disciplines......Page 454
18.5 The Inner Life of a Networking Device......Page 455
A.1.1 Transport Protocols......Page 457
A.1.2 Routing Protocols......Page 460
A.2.1 From Transistors to Logic Gates......Page 461
A.2.3 Hardware Design Building Blocks......Page 463
A.2.4 Memories: The Inside Scoop......Page 464
A.2.5 Chip Design......Page 465
A.3.1 Matching Algorithms for Clos Networks with k = n......Page 466
Appendix 4  The Interconnection Network Zoo......Page 467
Bibliography......Page 469
Index......Page 481