15 October 2014

Network Algorithmics by Varghese

I skimmed Network Algorithmics by George Varghese (2005). This book presents common tricks used at the OS, hardware, and architecture levels to prevent network bottlenecks. Here are 15 principles listed on the first page.

Number Principle Example
1 Avoid obvious waste Zero-copy interfaces
2 Shift computation in time
2a Precompute Application device channels
2b Evaluate lazily Copy-on-write
2c Share expenses, batch Integrated layer processing
3 Relax system requirements
3a Trade certainty for time Stochastic fair queuing
3b Trade accuracy for time Switch load balancing
3c Shift computation in space IPv6 fragmentation
4 Leverage off system components
4a Exploit locality Locality-driven receiver
4b Trade memory for speed Processing, Lulea IP lookups
4c Exploit existing hardware Fast TCP checksum
5 Add hardware
5a Use memory interleaving and pipelining Pipelined IP lookups
5b Use wide word parallelism Shared memory switches
5c Combine DRAM and SRAM effectively Maintaining counters
6 Create efficient specialized routines UDP checksums
7 Avoid unnecessary generality Fbufs
8 Do not be tied to reference implementation Upcalls
9 Pass hints in layer interfaces Packet filters
10 Pass hints in protocol headers Tag switching
11 Optimize the expected case Header prediction
11a Use caches Fbufs
12 Add state for speed Active virtual circuit list
12a Compute incrementally Recomputing CRCs
13 Optimize degrees of freedom IP trie lookups
14 Use bucket sorting, bitmaps Timing wheels
15 Create efficient data structures Level-4 switching

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.