Elsevier S & T

Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices

In stock

No reviews

31.500 KD inc. VAT

License

perpetual

Table of contents

Table of contentsvii
Prefacexix
Audiencexx
What This Book is Aboutxx
Organitztion of the Bookxxi
Featuresxxii
Usagexxiii
Why This Book Was Writtenxxiii
Acknowledgementsxxiv
PART I The Rules of the Game1
CHAPTER 1 Introducing Network Algorithmics3
1.1 THE PROBLEM: NETWORK BOTTLENECKS3
1.1.1 Endnode Bottlenecks4
1.1.2 Router Bottlenecks5
1.2 THE TECHNIQUES: NETWORK ALGORITHMICS7
1.2.1 Warm-up Example: Scenting an Evil Packet8
1.2.2 Strawman Solution9
1.2.3 Thinking Algorithmically9
1.2.4 Refining the Algorithm: Exploiting Hardware10
1.2.5 Cleaning Up11
1.2.6 Characteristics of Network Algorithmics13
1.3 EXERCISE15
CHAPTER 2 Network Implementation Models16
2.1 PROTOCOLS17
2.1.1 Transport and Routing Protocols17
2.1.2 Abstract Protocol Model17
2.1.3 Performance Environment and Measures19
2.2 HARDWARE21
2.2.1 Combinatorial Logic21
2.2.2 Timing and Power22
2.2.3 Raising the Abstraction Level of Hardware Design23
2.2.4 Memories25
2.2.5 Memory Subsystem Design Techniques29
2.2.6 Component-Level Design30
2.2.7 Final Hardware Lessons31
2.3 NETWORK DEVICE ARCHITECTURES32
2.3.1 Endnode Architecture32
2.3.2 Router Architecture34
2.4 OPERATING SYSTEMS39
2.4.1 Uninterrupted Computation via Processes39
2.4.2 Infinite Memory via Virtual Memory41
2.4.3 Simple I/O via System Calls43
2.5 SUMMARY44
2.6 EXERCISES44
CHAPTER 3 Fifteen Implementation Principles50
3.1 MOTIVATING THE USE OF PRINCIPLES „ UPDATING TERNARY CONTENT-ADDRESSABLE MEMORIES50
3.2 ALGORITHMS VERSUS ALGORITHMICS54
3.3 FIFTEEN IMPLEMENTATION PRINCIPLES „ CATEGORIZATION AND DESCRIPTION56
3.3.1 Systems Principles56
3.3.2 Principles for Modularity with Efficiency61
3.3.3 Principles for Speeding Up Routines63
3.4 DESIGN VERSUS IMPLEMENTATION PRINCIPLES65
3.5 CAVEATS66
3.5.1 Eight Cautionary Questions68
3.6 SUMMARY70
3.7 EXERCISES70
CHAPTER 4 Principles in Action73
4.1 BUFFER VALIDATION OF APPLICATION DEVICE CHANNELS74
4.2 SCHEDULER FOR ASYNCHRONOUS TRANSFER MODE FLOW CONTROL76
4.3 ROUTE COMPUTATION USING DIJKSTRA’S ALGORITHM77
4.4 ETHERNET MONITOR USING BRIDGE HARDWARE80
4.5 DEMULTIPLEXING IN THE X-KERNEL81
4.6 TRIES WITH NODE COMPRESSION83
4.7 PACKET FILTERING IN ROUTERS85
4.8 AVOIDING FRAGMENTATION OF LINK STATE PACKETS87
4.9 POLICING TRAFFIC PATTERNS90
4.10 IDENTIFYING A RESOURCE HOG92
4.11 GETTING RID OF THE TCP OPEN CONNECTION LIST93
4.12 ACKNOWLEDGMENT WITHHOLDING96
4.13 INCREMENTALLY READING A LARGE DATABASE98
4.14 BINARY SEARCH OF LONG IDENTIFIERS100
4.15 VIDEO CONFERENCING VIA ASYNCHRONOUS TRANSFER MODE102
PART II Playing with Endnodes105
CHAPTER 5 Copying Data107
5.1 WHY DATA COPIES109
5.2 REDUCING COPYING VIA LOCAL RESTRUCTURING111
5.2.1 Exploiting Adaptor Memory111
5.2.2 Using Copy-on-Write113
5.2.3 Fbufs: Optimizing Page Remapping115
5.2.4 Transparently Emulating Copy Semantics119
5.3 AVOIDING COPYING USING REMOTE DMA121
5.3.1 Avoiding Copying in a Cluster122
5.3.2 Modern-Day Incarnations of RDMA123
5.4 BROADENING TO FILE SYSTEMS125
5.4.1 Shared Memory125
5.4.2 IO-Lite: A Unified View of Buffering126
5.4.3 Avoiding File System Copies via I/O Splicing128
5.5 BROADENING BEYOND COPIES129
5.6 BROADENING BEYOND DATA MANIPULATIONS131
5.6.1 Using Caches Effectively131
5.6.2 Direct Memory Access versus Programmed I/O135
5.7 CONCLUSIONS135
5.8 EXERCISES137
CHAPTER 6 Transferring Control139
6.1 WHY CONTROL OVERHEAD?141
6.2 AVOIDING SCHEDULING OVERHEAD IN NETWORKING CODE143
6.2.1 Making User-Level Protocol Implementations Real144
6.3 AVOIDING CONTEXT-SWITCHING OVERHEAD IN APPLICATIONS146
6.3.1 Process per Client147
6.3.2 Thread per Client148
6.3.3 Event-Driven Scheduler150
6.3.4 Event-Driven Server with Helper Processes150
6.3.5 Task-Based Structuring151
6.4 FAST SELECT153
6.4.1 A Server Mystery153
6.4.2 Existing Use and Implementation of select()154
6.4.3 Analysis of Select()155
6.4.4 Speeding Up Select() without Changing the API157
6.4.5 Speeding Up Select() by Changing the API158
6.5 AVOIDING SYSTEM CALLS159
6.5.1 The Virtual Interface Architecture (VIA) Proposal162
6.6 REDUCING INTERRUPTS163
6.6.1 Avoiding Receiver Livelock164
6.7 CONCLUSIONS165
6.8 EXERCISES166
CHAPTER 7 Maintaining Timers169
7.1 WHY TIMERS?169
7.2 MODEL AND PERFORMANCE MEASURES171
7.3 SIMPLEST TIMER SCHEMES172
7.4 TIMING WHEELS173
7.5 HASHED WHEELS175
7.6 HIERARCHICAL WHEELS176
7.7 BSD IMPLEMENTATION178
7.8 OBTAINING FINE-GRANULARITY TIMERS179
7.9 CONCLUSIONS180
7.10 EXERCISES181
CHAPTER 8 Demultiplexing182
8.1 OPPORTUNITIES AND CHALLENGES OF EARLY DEMULTIPLEXING184
8.2 GOALS184
8.3 CMU/STANFORD PACKET FILTER: PIONEERING PACKET FILTERS185
8.4 BERKELEY PACKET FILTER: ENABLING HIGH-PERFORMANCE MONITORING186
8.5 PATHFINDER: FACTORING OUT COMMON CHECKS189
8.6 DYNAMIC PACKET FILTER: COMPILERS TO THE RESCUE192
8.7 CONCLUSIONS195
8.8 EXERCISES195
CHAPTER 9 Protocol Processing197
9.1 BUFFER MANAGEMENT198
9.1.1 Buffer Allocation199
9.1.2 Sharing Buffers201
9.2 CYCLIC REDUNDANCY CHECKS AND CHECKSUMS203
9.2.1 Cyclic Redundancy Checks204
9.2.2 Internet Checksums207
9.2.3 Finessing Checksums209
9.3 GENERIC PROTOCOL PROCESSING209
9.3.1 UDP Processing212
9.4 REASSEMBLY213
9.4.1 Efficient Reassembly214
9.5 CONCLUSIONS216
9.6 EXERCISES217
PART III Playing with Routers219
CHAPTER 10 Exact-Match Lookups221
10.1 CHALLENGE 1: ETHERNET UNDER FIRE222
10.2 CHALLENGE 2: WIRE SPEED FORWARDING224
10.3 CHALLENGE 3: SCALING LOOKUPS TO HIGHER SPEEDS228
10.3.1 Scaling via Hashing228
10.3.2 Using Hardware Parallelism230
10.4 SUMMARY231
10.5 EXERCISE232
CHAPTER 11 Prefix-Match Lookups233
11.1 INTRODUCTION TO PREFIX LOOKUPS234
11.1.1 Prefix Notation234
11.1.2 Why Variable-Length Prefixes?235
11.1.3 Lookup Model236
11.2 FINESSING LOOKUPS238
11.2.1 Threaded Indices and Tag Switching238
11.2.2 Flow Switching240
11.2.3 Status of Tag Switching, Flow Switching, and Multiprotocol Label Switching241
11.3 NONALGORITHMIC TECHNIQUES FOR PREFIX MATCHING242
11.3.1 Caching242
11.3.2 Ternary Content-Addressable Memories242
11.4 UNIBIT TRIES243
11.5 MULTIBIT TRIES245
11.5.1 Fixed-Stride Tries246
11.5.2 Variable-Stride Tries247
11.5.3 Incremental Update250
11.6 LEVEL-COMPRESSED (LC) TRIES250
11.7 LULEA-COMPRESSED TRIES252
11.8 TREE BITMAP255
11.8.1 Tree Bitmap Ideas255
11.8.2 Tree Bitmap Search Algorithm256
11.9 BINARY SEARCH ON RANGES257
11.10 BINARY SEARCH ON PREFIX LENGTHS259
11.11 MEMORY ALLOCATION IN COMPRESSED SCHEMES261
11.11.1 Frame-Based Compaction262
11.12 LOOKUP-CHIP MODEL263
11.13 CONCLUSIONS265
11.14 EXERCISES266
CHAPTER 12 Packet Classification270
12.1 WHY PACKET CLASSIFICATION?271
12.2 PACKET-CLASSIFICATION PROBLEM273
12.3 REQUIREMENTS AND METRICS275
12.4 SIMPLE SOLUTIONS276
12.4.1 Linear Search276
12.4.2 Caching276
12.4.3 Demultiplexing Algorithms277
12.4.4 Passing Labels277
12.4.5 Content-Addressable Memories278
12.5 TWO-DIMENSIONAL SCHEMES278
12.5.1 Fast Searching Using Set-Pruning Tries278
12.5.2 Reducing Memory Using Backtracking281
12.5.3 The Best of Both Worlds: Grid of Tries281
12.6 APPROACHES TO GENERAL RULE SETS284
12.6.1 Geometric View of Classification284
12.6.2 Beyond Two Dimensions: The Bad News286
12.6.3 Beyond Two Dimensions: The Good News286
12.7 EXTENDING TWO-DIMENSIONAL SCHEMES287
12.8 USING DIVIDE-AND-CONQUER288
12.9 BIT VECTOR LINEAR SEARCH289
12.10 CROSS-PRODUCTING292
12.11 EQUIVALENCED CROSS-PRODUCTING293
12.12 DECISION TREE APPROACHES296
12.13 CONCLUSIONS299
12.14 EXERCISES300
CHAPTER 13 Switching302
13.1 ROUTER VERSUS TELEPHONE SWITCHES304
13.2 SHARED-MEMORY SWITCHES305
13.3 ROUTER HISTORY: FROM BUSES TO CROSSBARS305
13.4 THE TAKE-A-TICKET CROSSBAR SCHEDULER307
13.5 HEAD-OF-LINE BLOCKING311
13.6 AVOIDING HEAD-OF-LINE BLOCKING VIA OUTPUT QUEUING312
13.7 AVOIDING HEAD-OF-LINE BLOCKING BY USING PARALLEL ITERATIVE MATCHING314
13.8 AVOIDING RANDOMIZATION WITH iSLIP316
13.8.1 Extending iSLIP to Multicast and Priority320
13.8.2 iSLIP Implementation Notes322
13.9 SCALING TO LARGER SWITCHES323
13.9.1 Measuring Switch Cost324
13.9.2 Clos Networks for Medium-Size Routers324
13.9.3 Benes Networks for Larger Routers328
13.10 SCALING TO FASTER SWITCHES333
13.10.1 Using Bit Slicing for Higher-Speed Fabrics333
13.10.2 Using Short Links for Higher-Speed Fabrics334
13.10.3 Memory Scaling Using Randomization335
13.11 CONCLUSIONS336
13.12 EXERCISES337
CHAPTER 14 Scheduling Packets339
14.1 MOTIVATION FOR QUALITY OF SERVICE340
14.2 RANDOM EARLY DETECTION342
14.3 TOKEN BUCKET POLICING345
14.4 MULTIPLE OUTBOUND QUEUES AND PRIORITY346
14.5 A QUICK DETOUR INTO RESERVATION PROTOCOLS347
14.6 PROVIDING BANDWIDTH GUARANTEES348
14.6.1 The Parochial Parcel Service348
14.6.2 Deficit Round-Robin350
14.6.3 Implementation and Extensions of Deficit Round-Robin351
14.7 SCHEDULERS THAT PROVIDE DELAY GUARANTEES354
14.8 SCALABLE FAIR QUEUING358
14.8.1 Random Aggregation359
14.8.2 Edge Aggregation359
14.8.3 Edge Aggregation with Policing360
14.9 SUMMARY361
14.10 EXERCISES361
CHAPTER 15 Routers as Distributed Systems362
15.1 INTERNAL FLOW CONTROL363
15.1.1 Improving Performance364
15.1.2 Rescuing Reliability365
15.2 INTERNAL STRIPING368
15.2.1 Improving Performance368
15.2.2 Rescuing Reliability369
15.3 ASYNCHRONOUS UPDATES371
15.3.1 Improving Performance372
15.3.2 Rescuing Reliability373
15.4 CONCLUSIONS373
15.5 EXERCISES374
PART IV Endgame377
CHAPTER 16 Measuring Network Traffic379
16.1 WHY MEASUREMENT IS HARD381
16.1.1 Why Counting Is Hard381
16.2 REDUCING SRAM WIDTH USING DRAM BACKING STORE382
16.3 REDUCING COUNTER WIDTH USING RANDOMIZED COUNTING384
16.4 REDUCING COUNTERS USING THRESHOLD AGGREGATION385
16.5 REDUCING COUNTERS USING FLOW COUNTING387
16.6 REDUCING PROCESSING USING SAMPLED NETFLOW388
16.7 REDUCING REPORTING USING SAMPLED CHARGING389
16.8 CORRELATING MEASUREMENTS USING TRAJECTORY SAMPLING390
16.9 A CONCERTED APPROACH TO ACCOUNTING392
16.10 COMPUTING TRAFFIC MATRICES393
16.10.1 Approach 1: Internet Tomography394
16.10.2 Approach 2: Per-Prefix Counters394
16.10.3 Approach 3: Class Counters395
16.11 STING AS AN EXAMPLE OF PASSIVE MEASUREMENT395
16.12 CONCLUSION396
16.13 EXERCISES397
CHAPTER 17 Network Security399
17.1 SEARCHING FOR MULTIPLE STRINGS IN PACKET PAYLOADS401
17.1.1 Integrated String Matching Using Aho–Corasick402
17.1.2 Integrated String Matching Using Boyer–Moore403
17.2 APPROXIMATE STRING MATCHING405
17.3 IP TRACEBACK VIA PROBABILISTIC MARKING406
17.4 IP TRACEBACK VIA LOGGING409
17.4.1 Bloom Filters410
17.4.2 Bloom Filter Implementation of Packet Logging412
17.5 DETECTING WORMS413
17.6 CONCLUSION415
17.7 EXERCISES415
CHAPTER 18 Conclusions417
18.1 WHAT THIS BOOK HAS BEEN ABOUT418
18.1.1 Endnode Algorithmics418
18.1.2 Router Algorithmics419
18.1.3 Toward a Synthesis420
18.2 WHAT NETWORK ALGORITHMICS IS ABOUT423
18.2.1 Interdisciplinary Thinking423
18.2.2 Systems Thinking424
18.2.3 Algorithmic Thinking425
18.3 NETWORK ALGORITHMICS AND REAL PRODUCTS427
18.4 NETWORK ALGORITHMICS: BACK TO THE FUTURE429
18.4.1 New Abstractions429
18.4.2 New Connecting Disciplines430
18.4.3 New Requirements431
18.5 THE INNER LIFE OF A NETWORKING DEVICE431
APPENDIX Detailed Models433
A.1 TCP AND IP433
A.1.1 Transport Protocols433
A.1.2 Routing Protocols436
A.2 HARDWARE MODELS437
A.2.1 From Transistors to Logic Gates437
A.2.2 Timing Delays439
A.2.3 Hardware Design Building Blocks439
A.2.4 Memories: The Inside Scoop440
A.2.5 Chip Design441
A.3 SWITCHING THEORY442
A.3.1 Matching Algorithms for Clos Networks with k = n442
A.4 THE INTERCONNECTION NETWORK ZOO443
BIBLIOGRAPHY445
INDEX457
15 Principles Used to Overcome Network Bottlenecks466

Book details

Vendor Elsevier S & T
SKU 9780120884773
ISBN-13 9780080479644

Do you have questions about this book?

Ask an expert!

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.

FOR INSTRUCTORS: To obtain access to the solutions manual for this title simply register on our textbook website (textbooks.elsevier.com)and request access to the Computer Science subject area. Once approved (usually within one business day) you will be able to access all of the instructor-only materials through the "Instructor Manual" link on this book's academic web page at textbooks.elsevier.com.

· Addresses the bottlenecks found in all kinds of network devices, (data copying, control transfer, demultiplexing, timers, and more) and offers ways to break them.
· Presents techniques suitable specifically for endnodes, including Web servers.
· Presents techniques suitable specifically for interconnect devices, including routers, bridges, and gateways.
· Written as a practical guide for implementers but full of valuable insights for students, teachers, and researchers.
· Includes end-of-chapter summaries and exercises.

Instant delivery by email
Your access email arrives within minutes of checkout, with a sign-in link for each book — no shipping, no waiting.

Read on any device
Books open in VitalSource Bookshelf on your phone, tablet, or computer, online or offline. Your library is always available at aafaq.vitalsource.com — just log in with the email you used at checkout.

Lost the email?
Resend it to yourself in seconds from My eBook orders, or email cs@aafaqeducation.com and we'll help.