# George Varghese - Network Algorithmics (Highlights)  ## Metadata **Cover**:: https://learning.oreilly.com/library/view/network-algorithmics/9780120884773/ibis_generated_cover_thumbnail.jpg **Source**:: #from/readwise **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[George Varghese]] **Full Title**:: Network Algorithmics **Category**:: #books #readwise/books **Category Icon**:: 📚 **Highlighted**:: [[2021-03-11]] **Created**:: [[2022-09-26]] ## Highlights ### Preface ### Chapter 2: Network Implementation Models - In essence, this book is about three things: fundamental networking implementation bottlenecks, general principles to address new bottlenecks, and techniques for specific bottlenecks that can be derived from the general principles. #### Network Implementation Models - Implementation guide: Implementors who care about performance may wish to read all of Part I and then sample Parts II and III according to their needs. ##### 2.1 PROTOCOLS ### Part I: The Rules of the Game - 2.1.1 TRANSPORT AND ROUTING PROTOCOLS - A protocol is a state machine for all nodes participating in the protocol, together with interfaces and message formats. ### Chapter 1: Introducing Network Algorithmics - • Poor Latencies: Real round-trip delays exceed speed-of-light limitations; measurements in Crovella and Carter [CC95] report a mean of 241 msec across the United States compared to speed-of-light delays of less than 30 msec. ### Chapter 3: Fifteen Implementation Principles - network algorithmics recognizes the primary importance of taking an interdisciplinary systems approach to streamlining network implementations. #### Fifteen Implementation Principles ##### 3.3.1 SYSTEMS PRINCIPLES - Endnodes are the endpoints of the network. - P1: AVOID OBVIOUS WASTE IN COMMON SITUATIONS - Structure ... the combination of layered software, protection mechanisms, and excessive generality can slow down networking software greatly, even with the fastest processors. - Notice that each operation (e.g., walk to pantry, line of code, single packet copy) considered by itself has no obvious waste. It is the sequence of operations (two trips to the pantry, two statements that recompute a subexpression, two copies) that have obvious waste. ### 1.1 THE PROBLEM: NETWORK BOTTLENECKS - P2: SHIFT COMPUTATION IN TIME - Scale ... Many operating systems use inefficient data structures and algorithms that were designed for an era when the number of connections was small. - Structure ... the combination of layered software, protection mechanisms, and excessive generality can slow down networking software greatly, even with the fastest processors. - P2a: Precompute. This refers to computing quantities before they are actually used, to save time at the point of use. - P2b: Evaluate Lazily. This refers to postponing expensive operations at critical times, hoping that either the operation will not be needed later or a less busy time will be found to perform the operation. - P2c: Share Expenses. This refers to taking advantage of expensive operations done by other parts of the system. An important example of expense sharing is batching, where several expensive operations can be done together more cheaply than doing each separately. - Scale ... Many operating systems use inefficient data structures and algorithms that were designed for an era when the number of connections was small. - Services ... the very success of the Internet requires careful attention in the next decade to make it more effective by providing guarantees in terms of performance, security, and reliability. - P3a: Trade Certainty for Time. Systems designers can fool themselves into believing that their systems offer deterministic guarantees, when in fact we all depend on probabilities. - think of a router as a “generic network interconnection device.” - P3b: Trade Accuracy for Time. Similarly, numerical analysis cures us of the illusion that computers are perfectly accurate. Thus it can pay to relax accuracy requirements for speed. - Scale: Network devices face two areas of scaling: bandwidth scaling and population scaling. - P3c: Shift Computation in Space. ... moving computation from one subsystem to another - Services ... the very success of the Internet requires careful attention in the next decade to make it more effective by providing guarantees in terms of performance, security, and reliability. - P4: LEVERAGE OFF SYSTEM COMPONENTS - P4a: Exploit Locality. - Definition: Network algorithmics is the use of an interdisciplinary systems approach, seasoned with algorithmic thinking, to design fast implementations of network processing tasks at servers, routers, and other networking devices. - P4b: Trade Memory for Speed. The obvious technique is to use more memory, such as lookup tables, to save processing time. - P4c: Exploit Hardware Features. - If this principle is carried too far, the modularity of the system will be in jeopardy. Two techniques alleviate this problem. First, if we exploit other system features only to improve performance, then changes to those system features can only affect performance and not correctness. Second, we use this technique only for system components that profiling has shown to be a bottleneck. - P5: ADD HARDWARE TO IMPROVE PERFORMANCE - P5a: Use Memory Interleaving and Pipelining. - P5b: Use Wide Word Parallelism. - P5c: Combine DRAM and SRAM. ##### 3.3.2 PRINCIPLES FOR MODULARITY WITH EFFICIENCY - P6: CREATE EFFICIENT SPECIALIZED ROUTINES BY REPLACING INEFFICIENT GENERAL-PURPOSE ROUTINES - P7: AVOID UNNECESSARY GENERALITY - P8: DON’T BE TIED TO REFERENCE IMPLEMENTATIONS - P9: PASS HINTS IN MODULE INTERFACES - A hint is information passed from a client to a service that, if correct, can avoid expensive computation by the service. - P10: PASS HINTS IN PROTOCOL HEADERS ##### 3.3.3 PRINCIPLES FOR SPEEDING UP ROUTINES - P11: OPTIMIZE THE EXPECTED CASE - P11a: USE CACHES - P12: ADD OR EXPLOIT STATE TO GAIN SPEED - P13: OPTIMIZE DEGREES OF FREEDOM - P14: USE SPECIAL TECHNIQUES FOR FINITE UNIVERSES SUCH AS INTEGERS - P15: USE ALGORITHMIC TECHNIQUES TO CREATE EFFICIENT DATA STRUCTURES ### Chapter 4: Principles in Action #### Principles in Action ### Part II: Playing with Endnodes ### PART II Playing with Endnodes