Home Page Icon
Home Page
Table of Contents for
Part I: The Rules of the Game
Close
Part I: The Rules of the Game
by George Varghese
Network Algorithmics
Cover image
Title page
Table of Contents
Copyright page
Dedication
Preface
AUDIENCE
WHAT THIS BOOK IS ABOUT
ORGANIZATION OF THE BOOK
FEATURES
USAGE
WHY THIS BOOK WAS WRITTEN
ACKNOWLEDGMENTS
Part I: The Rules of the Game
Introduction
Chapter 1: Introducing Network Algorithmics
1.1 THE PROBLEM: NETWORK BOTTLENECKS
1.2 THE TECHNIQUES: NETWORK ALGORITHMICS
1.3 EXERCISE
Chapter 2: Network Implementation Models
2.1 PROTOCOLS
2.2 HARDWARE
2.3 NETWORK DEVICE ARCHITECTURES
2.4 OPERATING SYSTEMS
2.5 SUMMARY
2.6 EXERCISES
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
3.5 CAVEATS
3.6 SUMMARY
3.7 EXERCISES
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.9 POLICING TRAFFIC PATTERNS
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
4.14 BINARY SEARCH OF LONG IDENTIFIERS
4.15 VIDEO CONFERENCING VIA ASYNCHRONOUS TRANSFER MODE
Part II: Playing with Endnodes
Introduction
Chapter 5: Copying Data
5.1 WHY DATA COPIES
5.2 REDUCING COPYING VIA LOCAL RESTRUCTURING
5.3 AVOIDING COPYING USING REMOTE DMA
5.4 BROADENING TO FILE SYSTEMS
5.5 BROADENING BEYOND COPIES
5.6 BROADENING BEYOND DATA MANIPULATIONS
5.7 CONCLUSIONS
5.8 EXERCISES
Chapter 6: Transferring Control
6.1 WHY CONTROL OVERHEAD?
6.2 AVOIDING SCHEDULING OVERHEAD IN NETWORKING CODE
6.3 AVOIDING CONTEXT-SWITCHING OVERHEAD IN APPLICATIONS
6.4 FAST SELECT
6.5 AVOIDING SYSTEM CALLS
6.6 REDUCING INTERRUPTS
6.7 CONCLUSIONS
6.8 EXERCISES
Chapter 7: Maintaining Timers
7.1 WHY TIMERS?
7.2 MODEL AND PERFORMANCE MEASURES
7.3 SIMPLEST TIMER SCHEMES
7.4 TIMING WHEELS
7.5 HASHED WHEELS
7.6 HIERARCHICAL WHEELS
7.7 BSD IMPLEMENTATION
7.8 OBTAINING FINE-GRANULARITY TIMERS
7.9 CONCLUSIONS
7.10 EXERCISES
Chapter 8: Demultiplexing
8.1 OPPORTUNITIES AND CHALLENGES OF EARLY DEMULTIPLEXING
8.2 GOALS
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
8.7 CONCLUSIONS
8.8 EXERCISES
Chapter 9: Protocol Processing
9.1 BUFFER MANAGEMENT
9.2 CYCLIC REDUNDANCY CHECKS AND CHECKSUMS
9.3 GENERIC PROTOCOL PROCESSING
9.4 REASSEMBLY
9.5 CONCLUSIONS
9.6 EXERCISES
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
10.4 SUMMARY
10.5 EXERCISE
Chapter 12: Packet Classification
12.1 WHY PACKET CLASSIFICATION?
12.2 PACKET-CLASSIFICATION PROBLEM
12.3 REQUIREMENTS AND METRICS
12.4 SIMPLE SOLUTIONS
12.5 TWO-DIMENSIONAL SCHEMES
12.6 APPROACHES TO GENERAL RULE SETS
12.7 EXTENDING TWO-DIMENSIONAL SCHEMES
12.8 USING DIVIDE-AND-CONQUER
12.9 BIT VECTOR LINEAR SEARCH
12.10 CROSS-PRODUCTING
12.11 EQUIVALENCED CROSS-PRODUCTING
12.12 DECISION TREE APPROACHES
12.13 CONCLUSIONS
12.14 EXERCISES
Chapter 13: Switching
13.1 ROUTER VERSUS TELEPHONE SWITCHES
13.2 SHARED-MEMORY SWITCHES
13.3 ROUTER HISTORY: FROM BUSES TO CROSSBARS
13.4 THE TAKE-A-TICKET CROSSBAR SCHEDULER
13.5 HEAD-OF-LINE BLOCKING
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
13.11 CONCLUSIONS
13.12 EXERCISES
Chapter 14: Scheduling Packets
14.1 MOTIVATION FOR QUALITY OF SERVICE
14.2 RANDOM EARLY DETECTION
14.3 TOKEN BUCKET POLICING
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
14.8 SCALABLE FAIR QUEUING
14.9 SUMMARY
14.10 EXERCISES
Chapter 15: Routers as Distributed Systems
15.1 INTERNAL FLOW CONTROL
15.2 INTERNAL STRIPING
15.3 ASYNCHRONOUS UPDATES
15.4 CONCLUSIONS
15.5 EXERCISES
Part IV: Endgame
Chapter 16: Measuring Network Traffic
16.1 WHY MEASUREMENT IS HARD
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
16.12 CONCLUSION
16.13 EXERCISES
Chapter 17: Network Security
17.1 SEARCHING FOR MULTIPLE STRINGS IN PACKET PAYLOADS
17.2 APPROXIMATE STRING MATCHING
17.3 IP TRACEBACK VIA PROBABILISTIC MARKING
17.4 IP TRACEBACK VIA LOGGING
17.5 DETECTING WORMS
17.6 CONCLUSION
17.7 EXERCISES
Chapter 18: Conclusions
18.1 WHAT THIS BOOK HAS BEEN ABOUT
18.2 WHAT NETWORK ALGORITHMICS IS ABOUT
18.3 NETWORK ALGORITHMICS AND REAL PRODUCTS
18.4 NETWORK ALGORITHMICS: BACK TO THE FUTURE
18.5 THE INNER LIFE OF A NETWORKING DEVICE
Appendix: Detailed Models
A.1 TCP AND IP
A.2 HARDWARE MODELS
A.3 SWITCHING THEORY
A.4 THE INTERCONNECTION NETWORK ZOO
Bibliography
Index
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Preface
Next
Next Chapter
Introduction
Part I
The Rules of the Game
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset