Title :
Searching very large routing tables in fast SRAM
Author :
Van Lunteren, Jan
Author_Institution :
IBM Zurich Res. Lab., Ruschlikon, Switzerland
fDate :
6/23/1905 12:00:00 AM
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
Keywords :
SRAM chips; data compression; data structures; table lookup; telecommunication computing; telecommunication network routing; 292 KB; 3.7 MB; 555 KB; OC-192; OC-768; SRAM; balanced routing table search; compression technique; hardware implementation; prefix information; stand-alone data structure; Bandwidth; Data structures; Hardware; Internet; Laboratories; Random access memory; Routing; SDRAM; Spine; Table lookup;
Conference_Titel :
Computer Communications and Networks, 2001. Proceedings. Tenth International Conference on
Conference_Location :
Scottsdale, AZ
Print_ISBN :
0-7803-7128-3
DOI :
10.1109/ICCCN.2001.956212
