Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, 2nd Edition
- Length: 594 pages
- Edition: 2
- Language: English
- Publisher: Morgan Kaufmann
- Publication Date: 2022-12-09
- ISBN-10: 0128099275
- ISBN-13: 9780128099278
- Sales Rank: #1251820 (See Top 100 Books)
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.
Cover image Title page Table of Contents Copyright Dedication Preface to the second edition Preface Audience What this book is about Organization of the book Features Usage Why this book was written Acknowledgments 15 principles used to overcome network bottlenecks Part 1: The rules of the game Introduction Chapter 1: Introducing network algorithmics Abstract 1.1. The problem: network bottlenecks 1.2. The techniques: network algorithmics 1.3. Exercise Chapter 2: Network implementation models Abstract 2.1. Protocols 2.2. Hardware 2.3. Network device architectures 2.4. Operating systems 2.5. Summary 2.6. Exercises References Chapter 3: Fifteen implementation principles Abstract 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 References 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 Abstract 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 References 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 Abstract 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. Google Carousel implementation 7.9. Obtaining finer granularity timers 7.10. Conclusions 7.11. Exercises References 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 Abstract 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 References Part 3: Playing with routers Introduction Chapter 10: Exact-match lookups Abstract 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 References 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 Abstract 15.1. Internal flow control 15.2. Internal Link Striping 15.3. Distributed Memory 15.4. Asynchronous updates 15.5. Conclusions 15.6. Exercises References 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 Abstract 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 References Appendix A: Detailed models A.1. TCP and IP A.2. Hardware models A.3. Switching theory A.4. The interconnection network Zoo References References References Index
Donate to keep this site alive
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.