CS 636 InternetworkingCS 636 InternetworkingRamana KompellaEND NODE ALGORITHMICSLecture 12: Protocol Processing1CS 636 InternetworkingOutline Buffer management CRCs and checksums TCP header prediction Packet reassembly2CS 636 InternetworkingDynamic memory allocation Kernel buffers required by all protocols Goals◦ Allocation and deallocation should be fast◦ Try not to deny requests due to fragmentation◦ Fairness across connections Hard problem in the unconstrained case◦ Fine tune allocation mechanisms to usage patterns of protocol implementations3CS 636 InternetworkingTypes of buffers BSD mbufs◦ Three sizes – 100, 108 and 2048 bytes◦ Easy to grow and less fragmentation◦ Accesses and copies are harder Van Jacobson’s pbufs (and Linux sk_buf)◦ One contiguous buffer per packet ◦ Save space for headers in advance◦ Results in more fragmentation4Buffer allocators  Standard textbook allocators ◦ First-fit◦ Best-fit We will consider◦ Segregated pool allocator◦ Linux allocator◦ Batch allocatorCS 636 Internetworking 5CS 636 InternetworkingSegregated pool allocator [Kingsley] BSD 4.2 UNIX malloc() implementation Separate pools of 2Xbytes buffers Any request served from nearest 2X pool No attempt to split or coalesce buffers◦ A variant buddy system can be used to do so. Very fast allocate and deallocate What it worst case memory wastage?6CS 636 InternetworkingLinux allocator [Lea] Referred to as dlmalloc() after Doug Lea. Memory broken into128 pools ◦ first 64 sizes – from 16 to 512 in increments of 8◦ last 64 sizes – exponential increase  Buffer sizes closer to requested size Adjacent free buffers coalesced and promoted Implementation trick: the “next” pointers in the free lists can be stored in the free buffer7CS 636 InternetworkingBatch allocation Allocate sequentially Curr=Curr+B Spare chunk built in background Problem: deallocates come in any order Solutions: ◦ More spare chunks◦ Page-remapping◦ Compaction8BcurrentReplenish sparecopy in the backgroundusing page remappingFair buffer allocation Buffer stealing (McKinney’s algorithm)◦ Fair buffer allocation for packet queues in router◦ When a queue needs a buffer and all allocated, it steals from the queue with most buffers◦ Use a list instead of a heapCS 636 Internetworking 93028 26P4P2P1P3P1 28highestCS 636 InternetworkingFair buffer allocation10 Dynamic thresholds [Choudhury and Hahne] Observation: Single threshold overly limiting and unduly ddangerous No user gets more buffers once it has at least cF buffers◦ F number of free buffers Fairness only long term Even simpler high speed implementation◦ Choose c to be a power of 2 (shift + comparison)CS 636 InternetworkingOutline Buffer management CRCs and checksums TCP header prediction Packet reassembly11CS 636 InternetworkingCRCs and checksums Both are hash functions such as H(P) ≠ H(P’) for “most common corruptions” P→P’ CRCs designed for powerful error detection (usually implemented in hardware) Checksums weaker but much simpler to implement in software12CS 636 InternetworkingCRC refresher Generator G repeatedly subtracted (using XOR) from message until remainder smaller than G Naive implementation: test MSB, if 1, XOR with G, shift left13CS 636 InternetworkingNaïve CRC 3 clock cycles to shift a bit◦ Comparison for the MSB in cycle 1◦ Actual XOR in cycle 2◦ Shift in cycle 314CS 636 InternetworkingCRC hardware with LFSRs Linear feedback shift registers (LFSRs) The XORs are combined with the shift by placing XOR gates to the right of bits based on generator G  If the MSB is 0, the XOR gates do nothing Takes 1 cycle per bit Can handle multiple bits at once using lookup tables15CS 636 InternetworkingInternet checksums Specification◦ Break message into 16 bit chunks (numbers)◦ Add number to crt checksum, test for carry◦ If carry add 1 Problems◦ Byte swapping – machine has wrong byte order◦ Masking – machine has 32 bit (or 64 bit) words◦ Check for carry – slows down the algorithm16CS 636 InternetworkingFaster Algorithm Ignore byte order – reverse at end Use natural word length and Lazy carry checking – check only after many iterations (the first 16 bits will accumulate the sum of all carry bits)17CS 636 InternetworkingIncremental checksums IP header checksums protect the TTL field which changes at every hop Instead of recomputing checksum over all fields just update the old one H to reflect the change If a 16-bit field m changes to m’ then, ◦ H’ = H + m’ – m◦ Some subtleties need to be taken care