Searching very large routing tables in fast SRAM

Abstract

The balanced routing table search (BaRTs) scheme is a novel method for searching large routing tables at OC-192 and OC-768 speeds. The scheme employs a compression technique that leaves all prefix information intact and creates a stand-alone data structure that can be incrementally updated. Performance-critical parts of the update operation are suitable for hardware implementation, enabling update rates beyond several hundred thousand per second. Simulations with actual routing tables have shown that BaRTs supports a routing table with 36,292 entries in only 292 KB of storage, a table with 72,825 entries in 555 KB, and a future table with 500,000 entries is estimated to fit in 3.7 MB.