Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices

George Varghese9780120884773, 0120884771

In designing a network device, you make dozens of decisions that affect the speed with which it will perform – sometimes for better, but sometimes for worse. Network Algorithmics provides a complete, coherent methodology for maximizing speed while meeting your other design goals.Author George Varghese begins by laying out the implementation bottlenecks that are most often encountered at four disparate levels of implementation: protocol, OS, hardware, and architecture. He then derives 15 solid principles – ranging from the commonly recognized to the groundbreaking – that are key to breaking these bottlenecks.The rest of the book is devoted to a systematic application of these principles to bottlenecks found specifically in endnodes, interconnect devices, and specialty functions such as security and measurement that can be located anywhere along the network. This immensely practical, clearly presented information will benefit anyone involved with network implementation, as well as students who have made this work their goal.

---

Table of contents :
Cover……Page 1
CONTENTS……Page 8
P R E F A C E x i……Page 20
PART I The Rules of the Game……Page 26
1.1 The Problem: Network Bottlenecks……Page 28
1.1.1 Endnode Bottlenecks……Page 29
1.1.2 Router Bottlenecks……Page 30
1.2 The Techniques: Network Algorithmics……Page 32
1.2.1 Warm-up Example: Scenting an Evil Packet……Page 33
1.2.3 Thinking Algorithmically……Page 34
1.2.4 Refining the Algorithm: Exploiting Hardware……Page 35
1.2.5 Cleaning Up……Page 36
1.2.6 Characteristics of Network Algorithmics……Page 38
1.3 Exercise……Page 40
C H A P T E R 2 Network Implementation Models……Page 41
2.1.2 Abstract Protocol Model……Page 42
2.1.3 Performance Environment and Measures……Page 44
2.2.1 Combinatorial Logic……Page 46
2.2.2 Timing and Power……Page 47
2.2.3 Raising the Abstraction Level of Hardware Design……Page 48
2.2.4 Memories……Page 50
2.2.5 Memory Subsystem Design Techniques……Page 54
2.2.6 Component-Level Design……Page 55
2.2.7 Final Hardware Lessons……Page 56
2.3.1 Endnode Architecture……Page 57
2.3.2 Router Architecture……Page 59
2.4.1 Uninterrupted Computation via Processes……Page 64
2.4.2 Infinite Memory via Virtual Memory……Page 66
2.4.3 Simple I/O via System Calls……Page 68
2.6 Exercises……Page 69
3.1 Motivating the Use of Principles – Updating Ternary Content-Addressable Memories……Page 75
3.2 Algorithms versus Algorithmics……Page 79
3.3.1 Systems Principles……Page 81
3.3.2 Principles for Modularity with Efficiency……Page 86
3.3.3 Principles for Speeding Up Routines……Page 88
3.4 Design versus Implementation Principles……Page 90
3.5 Caveats……Page 91
3.5.1 Eight Cautionary Questions……Page 93
3.7 Exercises……Page 95
C H A P T E R 4 Principles in Action……Page 98
4.1 Buffer Validation of Application Device Channels……Page 99
4.2 Scheduler for Asynchronous Transfer Mode Flow Control……Page 101
4.3 Route Computation Using Dijkstra’s Algorithm……Page 102
4.4 Ethernet Monitor Using Bridge Hardware……Page 105
4.5 Demultiplexing in the X-Kernel……Page 106
4.6 Tries with Node Compression……Page 108
4.7 Packet Filtering in Routers……Page 110
4.8 Avoiding Fragmentation of Link State Packets……Page 112
4.9 Policing Traffic Patterns……Page 115
4.10 Identifying a Resource Hog……Page 117
4.11 Getting Rid of the TCP Open Connection List……Page 118
4.12 Acknowledgment Withholding……Page 121
4.13 Incrementally Reading a Large Database……Page 123
4.14 Binary Search of Long Identifiers……Page 125
4.15 Video Conferencing via Asynchronous Transfer Mode……Page 127
PART II Playing with Endnodes……Page 130
C H A P T E R 5 Copying Data……Page 132
5.1 Why Data Copies……Page 134
5.2.1 Exploiting Adaptor Memory……Page 136
5.2.2 Using Copy-on-Write……Page 138
5.2.3 Fbufs: Optimizing Page Remapping……Page 140
5.2.4 Transparently Emulating Copy Semantics……Page 144
5.3 Avoiding Copying Using Remote DMA……Page 146
5.3.1 Avoiding Copying in a Cluster……Page 147
5.3.2 Modern-Day Incarnations of RDMA……Page 148
5.4.1 Shared Memory……Page 150
5.4.2 IO-Lite: A Unified View of Buffering……Page 151
5.4.3 Avoiding File System Copies via I/O Splicing……Page 153
5.5 Broadening beyond Copies……Page 154
5.6.1 Using Caches Effectively……Page 156
5.7 Conclusions……Page 160
5.8 Exercises……Page 162
C H A P T E R 6 Transferring Control……Page 164
6.1 Why Control Overhead?……Page 166
6.2 Avoiding Scheduling Overhead in Networking Code……Page 168
6.2.1 Making User-Level Protocol Implementations Real……Page 169
6.3 Avoiding Context-Switching Overhead in Applications……Page 171
6.3.1 Process per Client……Page 172
6.3.2 Thread per Client……Page 173
6.3.4 Event-Driven Server with Helper Processes……Page 175
6.3.5 Task-Based Structuring……Page 176
6.4.1 A Server Mystery……Page 178
6.4.2 Existing Use and Implementation of Select()……Page 179
6.4.3 Analysis of Select()……Page 180
6.4.4 Speeding Up Select() without Changing the API……Page 182
6.4.5 Speeding Up Select() by Changing the API……Page 183
6.5 Avoiding System Calls……Page 184
6.5.1 The Virtual Interface Architecture (VIA) Proposal……Page 187
6.6 Reducing Interrupts……Page 188
6.6.1 Avoiding Receiver Livelock……Page 189
6.7 Conclusions……Page 190
6.8 Exercises……Page 191
7.1 Why Timers?……Page 194
7.2 Model and Performance Measures……Page 196
7.3 Simplest Timer Schemes……Page 197
7.4 Timing Wheels……Page 198
7.5 Hashed Wheels……Page 200
7.6 Hierarchical Wheels……Page 201
7.7 BSD Implementation……Page 203
7.8 Obtaining Fine-Granularity Timers……Page 204
7.9 Conclusions……Page 205
7.10 Exercises……Page 206
C H A P T E R 8 Demultiplexing……Page 207
8.2 Goals……Page 209
8.3 CMU/Stanford Packet Filter: Pioneering Packet Filters……Page 210
8.4 Berkeley Packet Filter: Enabling High-Performance Monitoring……Page 211
8.5 Pathfinder: Factoring Out Common Checks……Page 214
8.6 Dynamic Packet Filter: Compilers to the Rescue……Page 217
8.8 Exercises……Page 220
C H A P T E R 9 Protocol Processing……Page 222
9.1 Buffer Management……Page 223
9.1.1 Buffer Allocation……Page 224
9.1.2 Sharing Buffers……Page 226
9.2 Cyclic Redundancy Checks and Checksums……Page 228
9.2.1 Cyclic Redundancy Checks……Page 229
9.2.2 Internet Checksums……Page 232
9.3 Generic Protocol Processing……Page 234
9.3.1 UDP Processing……Page 237
9.4 Reassembly……Page 238
9.4.1 Efficient Reassembly……Page 239
9.5 Conclusions……Page 241
9.6 Exercises……Page 242
PART III Playing with Routers……Page 244
C H A P T E R 1 0 Exact-Match Lookups……Page 246
10.1 Challenge 1: Ethernet under Fire……Page 247
10.2 Challenge 2: Wire Speed Forwarding……Page 249
10.3.1 Scaling via Hashing……Page 253
10.3.2 Using Hardware Parallelism……Page 255
10.4 Summary……Page 256
10.5 Exercise……Page 257
C H A P T E R 1 1 Prefix-Match Lookups……Page 258
11.1.1 Prefix Notation……Page 259
11.1.2 Why Variable-Length Prefixes?……Page 260
11.1.3 Lookup Model……Page 261
11.2.1 Threaded Indices and Tag Switching……Page 263
11.2.2 Flow Switching……Page 265
11.2.3 Status of Tag Switching, Flow Switching, and Multiprotocol Label Switching……Page 266
11.3.2 Ternary Content-Addressable Memories……Page 267
11.4 Unibit Tries……Page 268
11.5 Multibit Tries……Page 270
11.5.1 Fixed-Stride Tries……Page 271
11.5.2 Variable-Stride Tries……Page 272
11.6 Level-Compressed (LC) Tries……Page 275
11.7 Lulea-Compressed Tries……Page 277
11.8.1 Tree Bitmap Ideas……Page 280
11.8.2 Tree Bitmap Search Algorithm……Page 281
11.9 Binary Search on Ranges……Page 282
11.10 Binary Search on Prefix Lengths……Page 284
11.11 Memory Allocation in Compressed Schemes……Page 286
11.11.1 Frame-Based Compaction……Page 287
11.12 Lookup-Chip Model……Page 288
11.13 Conclusions……Page 290
11.14 Exercises……Page 291
C H A P T E R 1 2 Packet Classification……Page 295
12.1 Why Packet Classification?……Page 296
12.2 Packet-Classification Problem……Page 298
12.3 Requirements and Metrics……Page 300
12.4.2 Caching……Page 301
12.4.4 Passing Labels……Page 302
12.5.1 Fast Searching Using Set-Pruning Trees……Page 303
12.5.3 The Best of BothWorlds: Grid of Tries……Page 306
12.6.1 Geometric View of Classification……Page 309
12.6.3 Beyond Two Dimensions: The Good News……Page 311
12.7 Extending Two-Dimensional Schemes……Page 312
12.8 Using Divide-and-Conquer……Page 313
12.9 Bit Vector Linear Search……Page 314
12.10 Cross-Producting……Page 317
12.11 Equivalenced Cross-Producting……Page 318
12.12 Decision Tree Approaches……Page 321
12.13 Conclusions……Page 324
12.14 Exercises……Page 325
C H A P T E R 1 3 Switching……Page 327
13.1 Router versus Telephone Switches……Page 329
13.3 Router History: From Buses to Crossbars……Page 330
13.4 The Take-a-Ticket Crossbar Scheduler……Page 332
13.5 Head-of-Line Blocking……Page 336
13.6 Avoiding Head-of-Line Blocking via Output Queuing……Page 337
13.7 Avoiding Head-of-Line Blocking by Using Parallel Iterative Matching……Page 339
13.8 Avoiding Randomization with iSLIP……Page 341
13.8.1 Extending iSLIP to Multicast and Priority……Page 345
13.8.2 iSLIP Implementation Notes……Page 347
13.9 Scaling to Larger Switches……Page 348
13.9.2 Clos Networks for Medium-Size Routers……Page 349
13.9.3 Benes Networks for Larger Routers……Page 353
13.10.1 Using Bit Slicing for Higher-Speed Fabrics……Page 358
13.10.2 Using Short Links for Higher-Speed Fabrics……Page 359
13.10.3 Memory Scaling Using Randomization……Page 360
13.11 Conclusions……Page 361
13.12 Exercises……Page 362
C H A P T E R 1 4 Scheduling Packets……Page 364
14.1 Motivation for Quality of Service……Page 365
14.2 Random Early Detection……Page 367
14.3 Token Bucket Policing……Page 370
14.4 Multiple Outbound Queues and Priority……Page 371
14.5 A Quick Detour into Reservation Protocols……Page 372
14.6.1 The Parochial Parcel Service……Page 373
14.6.2 Deficit Round-Robin……Page 375
14.6.3 Implementation and Extensions of Deficit Round-Robin……Page 376
14.7 Schedulers That Provide Delay Guarantees……Page 379
14.8 Scalable Fair Queuing……Page 383
14.8.2 Edge Aggregation……Page 384
14.8.3 Edge Aggregation with Policing……Page 385
14.10 Exercises……Page 386
C H A P T E R 1 5 Routers as Distributed Systems……Page 387
15.1 Internal Flow Control……Page 388
15.1.1 Improving Performance……Page 389
15.1.2 Rescuing Reliability……Page 390
15.2.1 Improving Performance……Page 393
15.2.2 Rescuing Reliability……Page 394
15.3 Asynchronous Updates……Page 396
15.3.1 Improving Performance……Page 397
15.4 Conclusions……Page 398
15.5 Exercises……Page 399
PART IV Endgame……Page 402
C H A P T E R 1 6 Measuring Network Traffic……Page 404
16.1.1 Why Counting Is Hard……Page 406
16.2 Reducing SRAM Width Using DRAM Backing Store……Page 407
16.3 Reducing Counter Width Using Randomized Counting……Page 409
16.4 Reducing Counters Using Threshold Aggregation……Page 410
16.5 Reducing Counters Using Flow Counting……Page 412
16.6 Reducing Processing Using Sampled NetFlow……Page 413
16.7 Reducing Reporting Using Sampled Charging……Page 414
16.8 Correlating Measurements Using Trajectory Sampling……Page 415
16.9 A Concerted Approach to Accounting……Page 417
16.10 Computing Traffic Matrices……Page 418
16.10.2 Approach 2: Per-Prefix Counters……Page 419
16.11 Sting as an Example of Passive Measurement……Page 420
16.12 Conclusion……Page 421
16.13 Exercises……Page 422
C H A P T E R 1 7 Network Security……Page 424
17.1 Searching for Multiple Strings in Packet Payloads……Page 426
17.1.1 Integrated String Matching Using Aho–Corasick……Page 427
17.1.2 Integrated String Matching Using Boyer–Moore……Page 428
17.2 Approximate String Matching……Page 430
17.3 IP Traceback via Probabilistic Marking……Page 431
17.4 IP Traceback via Logging……Page 434
17.4.1 Bloom Filters……Page 435
17.4.2 Bloom Filter Implementation of Packet Logging……Page 437
17.5 Detecting Worms……Page 438
17.7 Exercises……Page 440
C H A P T E R 1 8 Conclusions……Page 442
18.1.1 Endnode Algorithmics……Page 443
18.1.2 Router Algorithmics……Page 444
18.1.3 Toward a Synthesis……Page 445
18.2.1 Interdisciplinary Thinking……Page 448
18.2.2 Systems Thinking……Page 449
18.2.3 Algorithmic Thinking……Page 450
18.3 Network Algorithmics and Real Products……Page 452
18.4.1 New Abstractions……Page 454
18.4.2 New Connecting Disciplines……Page 455
18.5 The Inner Life of a Networking Device……Page 456
A.1.1 Transport Protocols……Page 458
A.1.2 Routing Protocols……Page 461
A.2.1 From Transistors to Logic Gates……Page 462
A.2.3 Hardware Design Building Blocks……Page 464
A.2.4 Memories: The Inside Scoop……Page 465
A.2.5 Chip Design……Page 466
A.3.1 Matching Algorithms for Clos Networks with k = n……Page 467
A.4 The Interconnection Network Zoo……Page 468
Bibliography……Page 470
Index……Page 482