Book description
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
Table of contents
- Cover image
- Title page
- Table of Contents
- Copyright page
- Dedication
- Preface
-
Part I: The Rules of the Game
- Introduction
- Chapter 1: Introducing Network Algorithmics
- Chapter 2: Network Implementation Models
- Chapter 3: Fifteen 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.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
- Chapter 6: Transferring Control
- Chapter 7: Maintaining Timers
-
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
-
Part III: Playing with Routers
- Introduction
- Chapter 10: Exact-Match Lookups
-
Chapter 11: Prefix-Match Lookups
- 11.1 INTRODUCTION TO PREFIX LOOKUPS
- 11.2 FINESSING LOOKUPS
- 11.3 NONALGORITHMIC TECHNIQUES FOR PREFIX MATCHING
- 11.4 UNIBIT TRIES
- 11.5 MULTIBIT TRIES
- 11.6 LEVEL-COMPRESSED (LC) TRIES
- 11.7 Lulea-Compressed Tries
- 11.8 TREE BITMAP
- 11.9 BINARY SEARCH ON RANGES
- 11.10 BINARY SEARCH ON PREFIX LENGTHS
- 11.11 MEMORY ALLOCATION IN COMPRESSED SCHEMES
- 11.12 LOOKUP-CHIP MODEL
- 11.13 CONCLUSIONS
- 11.14 EXERCISES
-
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
-
Part IV: Endgame
- Introduction
-
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
- Chapter 18: Conclusions
- Appendix: Detailed Models
- Bibliography
- Index
Product information
- Title: Network Algorithmics
- Author(s):
- Release date: December 2004
- Publisher(s): Morgan Kaufmann
- ISBN: 9780080479644
You might also like
book
Network Processors
Network processors are the basic building blocks of today's high-speed, high-demand, quality-oriented communication networks. Designing and …
book
Network Routing, 2nd Edition
Network Routing: Algorithms, Protocols, and Architectures, Second Edition, explores network routing and how it can be …
book
Network Algorithmics, 2nd Edition
Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Second Edition takes an interdisciplinary approach …
book
The Illustrated Network
In 1994, W. Richard Stevens and Addison-Wesley published a networking classic: TCP/IP Illustrated. The model for …