Cuckoo Hashing

Hash tables play an important role in routers and switches because lookups need to done in constant time. Minimal size packets (64 bytes on Ethernet) on a 100 Gb/s link arrive at a rate of once every 6.7 ns. All packet handling (lookup, rewrite of next hop, updating CRC, etc.) must be done within that time. Hash tables satisfy that requirement and they are typically used for exact match lookups, such as the MAC addressing forwarding table or host IP route lookups.

read more...