Table of Contents
Chapter 1: Introducing Network Algorithmics
1.1 THE PROBLEM: NETWORK BOTTLENECKS
1.2 THE TECHNIQUES: NETWORK ALGORITHMICS
Chapter 2: Network Implementation Models
2.3 NETWORK DEVICE ARCHITECTURES
Chapter 3: Fifteen Implementation Principles
3.1 MOTIVATING THE USE OF PRINCIPLES — UPDATING TERNARY CONTENT-ADDRESSABLE MEMORIES
3.2 ALGORITHMS VERSUS ALGORITHMICS
3.3 FIFTEEN IMPLEMENTATION PRINCIPLES — CATEGORIZATION AND DESCRIPTION
3.4 DESIGN VERSUS IMPLEMENTATION PRINCIPLES
Chapter 4: Principles in Action
4.1 BUFFER VALIDATION OF APPLICATION DEVICE CHANNELS
4.2 SCHEDULER FOR ASYNCHRONOUS TRANSFER MODE FLOW CONTROL
4.3 ROUTE COMPUTATION USING DIJKSTRA’S ALGORITHM
4.4 ETHERNET MONITOR USING BRIDGE HARDWARE
4.5 DEMULTIPLEXING IN THE X-KERNEL
4.6 TRIES WITH NODE COMPRESSION
4.7 PACKET FILTERING IN ROUTERS
4.8 AVOIDING FRAGMENTATION OF LINK STATE PACKETS
4.10 IDENTIFYING A RESOURCE HOG
4.11 GETTING RID OF THE TCP OPEN CONNECTION LIST
4.12 ACKNOWLEDGMENT WITH HOLDING
4.13 INCREMENTALLY READING A LARGE DATABASE
Part II: Playing with Endnodes
5.2 REDUCING COPYING VIA LOCAL RESTRUCTURING
5.3 AVOIDING COPYING USING REMOTE DMA
5.4 BROADENING TO FILE SYSTEMS
5.6 BROADENING BEYOND DATA MANIPULATIONS
Chapter 6: Transferring Control
6.2 AVOIDING SCHEDULING OVERHEAD IN NETWORKING CODE
6.3 AVOIDING CONTEXT-SWITCHING OVERHEAD IN APPLICATIONS
7.2 MODEL AND PERFORMANCE MEASURES
7.8 OBTAINING FINE-GRANULARITY TIMERS
8.1 OPPORTUNITIES AND CHALLENGES OF EARLY DEMULTIPLEXING
8.3 CMU/STANFORD PACKET FILTER: PIONEERING PACKET FILTERS
8.4 BERKELEY PACKET FILTER: ENABLING HIGH-PERFORMANCE MONITORING
8.5 PATHFINDER: FACTORING OUT COMMON CHECKS
8.6 DYNAMIC PACKET FILTER: COMPILERS TO THE RESCUE
Chapter 9: Protocol Processing
9.2 CYCLIC REDUNDANCY CHECKS AND CHECKSUMS
Part III: Playing with Routers
Chapter 10: Exact-Match Lookups
10.1 CHALLENGE 1: ETHERNET UNDER FIRE
10.2 CHALLENGE 2: WIRE SPEED FORWARDING
10.3 CHALLENGE 3: SCALING LOOKUPS TO HIGHER SPEEDS
Chapter 11: Prefix-Match Lookups
11.1 INTRODUCTION TO PREFIX LOOKUPS
11.3 NONALGORITHMIC TECHNIQUES FOR PREFIX MATCHING
11.6 LEVEL-COMPRESSED (LC) TRIES
11.10 BINARY SEARCH ON PREFIX LENGTHS
11.11 MEMORY ALLOCATION IN COMPRESSED SCHEMES
Chapter 12: Packet Classification
12.1 WHY PACKET CLASSIFICATION?
12.2 PACKET-CLASSIFICATION PROBLEM
12.6 APPROACHES TO GENERAL RULE SETS
12.7 EXTENDING TWO-DIMENSIONAL SCHEMES
12.11 EQUIVALENCED CROSS-PRODUCTING
12.12 DECISION TREE APPROACHES
13.1 ROUTER VERSUS TELEPHONE SWITCHES
13.3 ROUTER HISTORY: FROM BUSES TO CROSSBARS
13.4 THE TAKE-A-TICKET CROSSBAR SCHEDULER
13.6 AVOIDING HEAD-OF-LINE BLOCKING VIA OUTPUT QUEUING
13.7 AVOIDING HEAD-OF-LINE BLOCKING BY USING PARALLEL ITERATIVE MATCHING
13.8 AVOIDING RANDOMIZATION WITH iSLIP
13.9 SCALING TO LARGER SWITCHES
13.10 SCALING TO FASTER SWITCHES
Chapter 14: Scheduling Packets
14.1 MOTIVATION FOR QUALITY OF SERVICE
14.4 MULTIPLE OUTBOUND QUEUES AND PRIORITY
14.5 A QUICK DETOUR INTO RESERVATION PROTOCOLS
14.6 PROVIDING BANDWIDTH GUARANTEES
14.7 SCHEDULERS THAT PROVIDE DELAY GUARANTEES
Chapter 16: Measuring Network Traffic
16.2 REDUCING SRAM WIDTH USING DRAM BACKING STORE
16.3 REDUCING COUNTER WIDTH USING RANDOMIZED COUNTING
16.4 REDUCING COUNTERS USING THRESHOLD AGGREGATION
16.5 REDUCING COUNTERS USING FLOW COUNTING
16.6 REDUCING PROCESSING USING SAMPLED NETFLOW
16.7 REDUCING REPORTING USING SAMPLED CHARGING
16.8 CORRELATING MEASUREMENTS USING TRAJECTORY SAMPLING
16.9 A CONCERTED APPROACH TO ACCOUNTING
16.10 COMPUTING TRAFFIC MATRICES
16.11 STING AS AN EXAMPLE OF PASSIVE MEASUREMENT
17.1 SEARCHING FOR MULTIPLE STRINGS IN PACKET PAYLOADS
17.2 APPROXIMATE STRING MATCHING
17.3 IP TRACEBACK VIA PROBABILISTIC MARKING
18.1 WHAT THIS BOOK HAS BEEN ABOUT
18.2 WHAT NETWORK ALGORITHMICS IS ABOUT
18.3 NETWORK ALGORITHMICS AND REAL PRODUCTS