Network Algorithmics

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

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright page
  5. Dedication
  6. Preface
    1. AUDIENCE
    2. WHAT THIS BOOK IS ABOUT
    3. ORGANIZATION OF THE BOOK
    4. FEATURES
    5. USAGE
    6. WHY THIS BOOK WAS WRITTEN
    7. ACKNOWLEDGMENTS
  7. Part I: The Rules of the Game
    1. Introduction
    2. Chapter 1: Introducing Network Algorithmics
      1. 1.1 THE PROBLEM: NETWORK BOTTLENECKS
      2. 1.2 THE TECHNIQUES: NETWORK ALGORITHMICS
      3. 1.3 EXERCISE
    3. Chapter 2: Network Implementation Models
      1. 2.1 PROTOCOLS
      2. 2.2 HARDWARE
      3. 2.3 NETWORK DEVICE ARCHITECTURES
      4. 2.4 OPERATING SYSTEMS
      5. 2.5 SUMMARY
      6. 2.6 EXERCISES
    4. Chapter 3: Fifteen Implementation Principles
      1. 3.1 MOTIVATING THE USE OF PRINCIPLES — UPDATING TERNARY CONTENT-ADDRESSABLE MEMORIES
      2. 3.2 ALGORITHMS VERSUS ALGORITHMICS
      3. 3.3 FIFTEEN IMPLEMENTATION PRINCIPLES — CATEGORIZATION AND DESCRIPTION
      4. 3.4 DESIGN VERSUS IMPLEMENTATION PRINCIPLES
      5. 3.5 CAVEATS
      6. 3.6 SUMMARY
      7. 3.7 EXERCISES
    5. Chapter 4: Principles in Action
      1. 4.1 BUFFER VALIDATION OF APPLICATION DEVICE CHANNELS
      2. 4.2 SCHEDULER FOR ASYNCHRONOUS TRANSFER MODE FLOW CONTROL
      3. 4.3 ROUTE COMPUTATION USING DIJKSTRA’S ALGORITHM
      4. 4.4 ETHERNET MONITOR USING BRIDGE HARDWARE
      5. 4.5 DEMULTIPLEXING IN THE X-KERNEL
      6. 4.6 TRIES WITH NODE COMPRESSION
      7. 4.7 PACKET FILTERING IN ROUTERS
      8. 4.8 AVOIDING FRAGMENTATION OF LINK STATE PACKETS
      9. 4.9 POLICING TRAFFIC PATTERNS
      10. 4.10 IDENTIFYING A RESOURCE HOG
      11. 4.11 GETTING RID OF THE TCP OPEN CONNECTION LIST
      12. 4.12 ACKNOWLEDGMENT WITH HOLDING
      13. 4.13 INCREMENTALLY READING A LARGE DATABASE
      14. 4.14 BINARY SEARCH OF LONG IDENTIFIERS
      15. 4.15 VIDEO CONFERENCING VIA ASYNCHRONOUS TRANSFER MODE
  8. Part II: Playing with Endnodes
    1. Introduction
    2. Chapter 5: Copying Data
      1. 5.1 WHY DATA COPIES
      2. 5.2 REDUCING COPYING VIA LOCAL RESTRUCTURING
      3. 5.3 AVOIDING COPYING USING REMOTE DMA
      4. 5.4 BROADENING TO FILE SYSTEMS
      5. 5.5 BROADENING BEYOND COPIES
      6. 5.6 BROADENING BEYOND DATA MANIPULATIONS
      7. 5.7 CONCLUSIONS
      8. 5.8 EXERCISES
    3. Chapter 6: Transferring Control
      1. 6.1 WHY CONTROL OVERHEAD?
      2. 6.2 AVOIDING SCHEDULING OVERHEAD IN NETWORKING CODE
      3. 6.3 AVOIDING CONTEXT-SWITCHING OVERHEAD IN APPLICATIONS
      4. 6.4 FAST SELECT
      5. 6.5 AVOIDING SYSTEM CALLS
      6. 6.6 REDUCING INTERRUPTS
      7. 6.7 CONCLUSIONS
      8. 6.8 EXERCISES
    4. Chapter 7: Maintaining Timers
      1. 7.1 WHY TIMERS?
      2. 7.2 MODEL AND PERFORMANCE MEASURES
      3. 7.3 SIMPLEST TIMER SCHEMES
      4. 7.4 TIMING WHEELS
      5. 7.5 HASHED WHEELS
      6. 7.6 HIERARCHICAL WHEELS
      7. 7.7 BSD IMPLEMENTATION
      8. 7.8 OBTAINING FINE-GRANULARITY TIMERS
      9. 7.9 CONCLUSIONS
      10. 7.10 EXERCISES
    5. Chapter 8: Demultiplexing
      1. 8.1 OPPORTUNITIES AND CHALLENGES OF EARLY DEMULTIPLEXING
      2. 8.2 GOALS
      3. 8.3 CMU/STANFORD PACKET FILTER: PIONEERING PACKET FILTERS
      4. 8.4 BERKELEY PACKET FILTER: ENABLING HIGH-PERFORMANCE MONITORING
      5. 8.5 PATHFINDER: FACTORING OUT COMMON CHECKS
      6. 8.6 DYNAMIC PACKET FILTER: COMPILERS TO THE RESCUE
      7. 8.7 CONCLUSIONS
      8. 8.8 EXERCISES
    6. Chapter 9: Protocol Processing
      1. 9.1 BUFFER MANAGEMENT
      2. 9.2 CYCLIC REDUNDANCY CHECKS AND CHECKSUMS
      3. 9.3 GENERIC PROTOCOL PROCESSING
      4. 9.4 REASSEMBLY
      5. 9.5 CONCLUSIONS
      6. 9.6 EXERCISES
  9. Part III: Playing with Routers
    1. Introduction
    2. Chapter 10: Exact-Match Lookups
      1. 10.1 CHALLENGE 1: ETHERNET UNDER FIRE
      2. 10.2 CHALLENGE 2: WIRE SPEED FORWARDING
      3. 10.3 CHALLENGE 3: SCALING LOOKUPS TO HIGHER SPEEDS
      4. 10.4 SUMMARY
      5. 10.5 EXERCISE
    3. Chapter 11: Prefix-Match Lookups
      1. 11.1 INTRODUCTION TO PREFIX LOOKUPS
      2. 11.2 FINESSING LOOKUPS
      3. 11.3 NONALGORITHMIC TECHNIQUES FOR PREFIX MATCHING
      4. 11.4 UNIBIT TRIES
      5. 11.5 MULTIBIT TRIES
      6. 11.6 LEVEL-COMPRESSED (LC) TRIES
      7. 11.7 Lulea-Compressed Tries
      8. 11.8 TREE BITMAP
      9. 11.9 BINARY SEARCH ON RANGES
      10. 11.10 BINARY SEARCH ON PREFIX LENGTHS
      11. 11.11 MEMORY ALLOCATION IN COMPRESSED SCHEMES
      12. 11.12 LOOKUP-CHIP MODEL
      13. 11.13 CONCLUSIONS
      14. 11.14 EXERCISES
    4. Chapter 12: Packet Classification
      1. 12.1 WHY PACKET CLASSIFICATION?
      2. 12.2 PACKET-CLASSIFICATION PROBLEM
      3. 12.3 REQUIREMENTS AND METRICS
      4. 12.4 SIMPLE SOLUTIONS
      5. 12.5 TWO-DIMENSIONAL SCHEMES
      6. 12.6 APPROACHES TO GENERAL RULE SETS
      7. 12.7 EXTENDING TWO-DIMENSIONAL SCHEMES
      8. 12.8 USING DIVIDE-AND-CONQUER
      9. 12.9 BIT VECTOR LINEAR SEARCH
      10. 12.10 CROSS-PRODUCTING
      11. 12.11 EQUIVALENCED CROSS-PRODUCTING
      12. 12.12 DECISION TREE APPROACHES
      13. 12.13 CONCLUSIONS
      14. 12.14 EXERCISES
    5. Chapter 13: Switching
      1. 13.1 ROUTER VERSUS TELEPHONE SWITCHES
      2. 13.2 SHARED-MEMORY SWITCHES
      3. 13.3 ROUTER HISTORY: FROM BUSES TO CROSSBARS
      4. 13.4 THE TAKE-A-TICKET CROSSBAR SCHEDULER
      5. 13.5 HEAD-OF-LINE BLOCKING
      6. 13.6 AVOIDING HEAD-OF-LINE BLOCKING VIA OUTPUT QUEUING
      7. 13.7 AVOIDING HEAD-OF-LINE BLOCKING BY USING PARALLEL ITERATIVE MATCHING
      8. 13.8 AVOIDING RANDOMIZATION WITH iSLIP
      9. 13.9 SCALING TO LARGER SWITCHES
      10. 13.10 SCALING TO FASTER SWITCHES
      11. 13.11 CONCLUSIONS
      12. 13.12 EXERCISES
    6. Chapter 14: Scheduling Packets
      1. 14.1 MOTIVATION FOR QUALITY OF SERVICE
      2. 14.2 RANDOM EARLY DETECTION
      3. 14.3 TOKEN BUCKET POLICING
      4. 14.4 MULTIPLE OUTBOUND QUEUES AND PRIORITY
      5. 14.5 A QUICK DETOUR INTO RESERVATION PROTOCOLS
      6. 14.6 PROVIDING BANDWIDTH GUARANTEES
      7. 14.7 SCHEDULERS THAT PROVIDE DELAY GUARANTEES
      8. 14.8 SCALABLE FAIR QUEUING
      9. 14.9 SUMMARY
      10. 14.10 EXERCISES
    7. Chapter 15: Routers as Distributed Systems
      1. 15.1 INTERNAL FLOW CONTROL
      2. 15.2 INTERNAL STRIPING
      3. 15.3 ASYNCHRONOUS UPDATES
      4. 15.4 CONCLUSIONS
      5. 15.5 EXERCISES
  10. Part IV: Endgame
    1. Introduction
    2. Chapter 16: Measuring Network Traffic
      1. 16.1 WHY MEASUREMENT IS HARD
      2. 16.2 REDUCING SRAM WIDTH USING DRAM BACKING STORE
      3. 16.3 REDUCING COUNTER WIDTH USING RANDOMIZED COUNTING
      4. 16.4 REDUCING COUNTERS USING THRESHOLD AGGREGATION
      5. 16.5 REDUCING COUNTERS USING FLOW COUNTING
      6. 16.6 REDUCING PROCESSING USING SAMPLED NETFLOW
      7. 16.7 REDUCING REPORTING USING SAMPLED CHARGING
      8. 16.8 CORRELATING MEASUREMENTS USING TRAJECTORY SAMPLING
      9. 16.9 A CONCERTED APPROACH TO ACCOUNTING
      10. 16.10 COMPUTING TRAFFIC MATRICES
      11. 16.11 STING AS AN EXAMPLE OF PASSIVE MEASUREMENT
      12. 16.12 CONCLUSION
      13. 16.13 EXERCISES
    3. Chapter 17: Network Security
      1. 17.1 SEARCHING FOR MULTIPLE STRINGS IN PACKET PAYLOADS
      2. 17.2 APPROXIMATE STRING MATCHING
      3. 17.3 IP TRACEBACK VIA PROBABILISTIC MARKING
      4. 17.4 IP TRACEBACK VIA LOGGING
      5. 17.5 DETECTING WORMS
      6. 17.6 CONCLUSION
      7. 17.7 EXERCISES
    4. Chapter 18: Conclusions
      1. 18.1 WHAT THIS BOOK HAS BEEN ABOUT
      2. 18.2 WHAT NETWORK ALGORITHMICS IS ABOUT
      3. 18.3 NETWORK ALGORITHMICS AND REAL PRODUCTS
      4. 18.4 NETWORK ALGORITHMICS: BACK TO THE FUTURE
      5. 18.5 THE INNER LIFE OF A NETWORKING DEVICE
  11. Appendix: Detailed Models
    1. A.1 TCP AND IP
    2. A.2 HARDWARE MODELS
    3. A.3 SWITCHING THEORY
    4. A.4 THE INTERCONNECTION NETWORK ZOO
  12. Bibliography
  13. Index

Product information

  • Title: Network Algorithmics
  • Author(s): George Varghese
  • Release date: December 2004
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080479644