Wednesday, October 15, 2008

DCII 15.10.08

IP Addresses (now, lamentably, referred to as IPs) have to be matched to the longest matching prefix (at least in IPv4) - there are a bunch of cool algorithms for this based in fast multi-level hashes (linux), Tries, and in specialized hardware (ternary Content Addressable Memory- CAMs) - so "most specifics"are found (last resort is all match- default route). For the first elegant paper on a data structure for doing this see Degermark's small fast route lookuup work. BSD and Linux kernel code are also informative.

IPv6 has enough bits to let you do proper separation of identity and location, so that one can at least consider a sensible way to support 3 different address allocation policies (topological, provider and geographic), as well as support both multi-homing and mobility. However, none of this is seeing much deployment yet (except in China).

Finally, the Host Identity Protocol (HIP) uses crypto-assigned addresses as a way to generate unique identities and then uses other services to map from ID to location - this, together with appropriate shim software (similar to the shims to let it work on v6) lets TCP work across host movements (or multi-homed - similar problem really) - the HIP RFC also cites other work on IPv6 and the basic problem of IPv4:)

An amusing (and not incorrect) map of the IPv4 Address Allocation today was done in the ever marvellous xkcd.

No comments: