Book description
Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Second Edition takes an interdisciplinary approach to applying principles for efficient implementation of network devices, offering solutions to the problem of network implementation bottlenecks. In designing a network device, there are dozens of decisions that affect the speed with which it will perform – sometimes for better, but sometimes for worse. The book provides a complete and coherent methodology for maximizing speed while meeting network design goals. The book is uniquely focused on the seamless integration of data structures, algorithms, operating systems and hardware/software co-designs for high-performance routers/switches and network end systems.
Thoroughly updated based on courses taught by the authors over the past decade, the book lays out the bottlenecks most often encountered at four disparate levels of implementation: protocol, OS, hardware and architecture. It then develops fifteen principles key to breaking these bottlenecks, systematically applying them to bottlenecks found in end-nodes, interconnect devices and specialty functions located along the network. Later sections discuss the inherent challenges of modern cloud computing and data center networking.
- Offers techniques that address common bottlenecks of interconnect devices, including routers, bridges, gateways, endnodes, and Web servers
- Presents many practical algorithmic concepts that students and readers can work with immediately
- Revised and updated throughout to discuss the latest developments from authors’ courses, including measurement algorithmics, randomization, regular expression matching, and software-defined networking
- Includes a new, rich set of homework exercises and exam questions to facilitate classroom use
Table of contents
- Cover image
- Title page
- Table of Contents
- Copyright
- Dedication
- Preface to the second edition
- Preface
- 15 principles used to overcome network bottlenecks
-
Part 1: 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
- Abstract
- 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 LSPs
- 4.9. Policing traffic patterns
- 4.10. Identifying a resource hog
- 4.11. Getting rid of the TCP open connection list
- 4.12. Acknowledgment withholding
- 4.13. Incrementally reading a large database
- 4.14. Binary search of long identifiers
- 4.15. Video conferencing via asynchronous transfer mode
- References
-
Part 2: Playing with endnodes
- Introduction
- Chapter 5: Copying data
-
Chapter 6: Transferring control
- Abstract
- 6.1. Why control overhead?
- 6.2. Avoiding scheduling overhead in networking code
- 6.3. Avoiding context-switching overhead in applications
- 6.4. Scalable I/O Notification
- 6.5. Avoiding system calls or Kernel Bypass
- 6.6. Radical Restructuring of Operating Systems
- 6.7. Reducing interrupts
- 6.8. Conclusions
- 6.9. Exercises
- References
- Chapter 7: Maintaining timers
-
Chapter 8: Demultiplexing
- Abstract
- 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
- References
- Chapter 9: Protocol processing
-
Part 3: Playing with routers
- Introduction
- Chapter 10: Exact-match lookups
-
Chapter 11: Prefix-match lookups
- Abstract
- 11.1. Introduction to prefix lookups
- 11.2. Finessing lookups
- 11.3. Non-algorithmic 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 ranges with Initial Lookup Table
- 11.11. Binary search on prefix lengths
- 11.12. Linear search on prefix lengths with hardware assist
- 11.13. Memory allocation in compressed schemes
- 11.14. Fixed Function Lookup-chip models
- 11.15. Programmable Lookup Chips and P4
- 11.16. Conclusions
- 11.17. Exercises
- References
-
Chapter 12: Packet classification
- Abstract
- 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. Hybrid algorithms
- 12.14. Conclusions
- 12.15. Exercises
- References
-
Chapter 13: Switching
- Abstract
- 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 HOL blocking via output queuing
- 13.7. Avoiding HOL blocking via virtual output queuing
- 13.8. Input-queued switching as a bipartite matching problem
- 13.9. Parallel iterative matching (PIM)
- 13.10. Avoiding randomization with iSLIP
- 13.11. Computing near-optimal matchings via learning
- 13.12. Sample-and-compare: a stunningly simple adaptive algorithm
- 13.13. SERENA: an improved adaptive algorithm
- 13.14. The queue-proportional sampling strategy
- 13.15. QPS implementation
- 13.16. Small-batch QPS and sliding-window QPS
- 13.17. Combined input and output queueing
- 13.18. Scaling to larger and faster switches
- 13.19. Scaling to faster link speeds
- 13.20. Conclusions
- 13.21. Exercises
- References
-
Chapter 14: Scheduling packets
- Abstract
- 14.1. Motivation for quality of service
- 14.2. Random early detection
- 14.3. Approximate fair dropping
- 14.4. Token bucket policing
- 14.5. Multiple outbound queues and priority
- 14.6. A quick detour into reservation protocols
- 14.7. Providing bandwidth guarantees
- 14.8. Schedulers that provide delay guarantees
- 14.9. Generalized processor sharing
- 14.10. Weighted fair queueing
- 14.11. Worst-case fair weighed fair queueing
- 14.12. The data structure and algorithm for efficient GPS clock tracking
- 14.13. Implementing WFQ and WF2Q
- 14.14. Quick fair queueing (QFQ)
- 14.15. Towards programmable packet scheduling
- 14.16. Scalable fair queuing
- 14.17. Summary
- 14.18. Exercises
- References
- Chapter 15: Routers as distributed systems
-
Part 4: Endgame
- Introduction
-
Chapter 16: Measuring network traffic
- Abstract
- 16.1. Why measurement is hard
- 16.2. Reducing SRAM width using DRAM backing store
- 16.3. A randomized counter scheme
- 16.4. Maintain active counters using BRICK
- 16.5. Extending BRICK for maintaining associated states
- 16.6. Reducing counter width using approximate counting
- 16.7. Reducing counters using threshold aggregation
- 16.8. Reducing counters using flow counting
- 16.9. Reducing processing using sampled NetFlow
- 16.10. Reducing reporting using sampled charging
- 16.11. Correlating measurements using trajectory sampling
- 16.12. A concerted approach to accounting
- 16.13. Computing traffic matrices
- 16.14. Sting as an example of passive measurement
- 16.15. Generating better traffic logs via data streaming
- 16.16. Counting the number of distinct flows
- 16.17. Detection of heavy hitters
- 16.18. Estimation of flow-size distribution
- 16.19. The Tug-of-War algorithm for estimating F2
- 16.20. Conclusion
- 16.21. Exercises
- References
-
Chapter 17: Network security
- Abstract
- 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. EarlyBird system for worm detection
- 17.7. Carousel: scalable logging for intrusion prevention systems
- 17.8. Conclusion
- 17.9. Exercises
- References
- Chapter 18: Conclusions
- Appendix A: Detailed models
- References
- Index
Product information
- Title: Network Algorithmics, 2nd Edition
- Author(s):
- Release date: November 2022
- Publisher(s): Morgan Kaufmann
- ISBN: 9780128099865
You might also like
book
Computer Networks, Fifth Edition
Computer Networks, 5/e is appropriate for Computer Networking or Introduction to Networking courses at both the …
video
CISSP, 4th Edition
28+ hours of video instruction Get the edge you need to ace the CISSP exam! Understand …
book
Zero Trust Networks, 2nd Edition
This practical book provides a detailed explanation of the zero trust security model. Zero trust is …
book
ISC2 CISSP Certified Information Systems Security Professional Official Study Guide, 10th Edition
CISSP Study Guide - fully updated for the 2024 CISSP Body of Knowledge ISC2 Certified Information …