Compress the Route Table Stored in TCAM by Using Memory Filter

摘要

With the continuous advances in communications technology, the link transmission speed of the Internet backbone networks has been increasing rapidly. This in turn demands more powerful IP address lookup engines. Being well-suited for high performance parallel lookup, Ternary Content Addressable Memory (TCAM) has been widely used in this area for years. Nevertheless, the limited storage, high power consumption and expensive price restrict its further application as link rates increase. Motivated by the prevalence of cheaper and faster conventional memory, such as SRAM and DRAM, we propose a range-based partitioning algorithm called "Max-splitting" which divides the entire route table into several sub-tries with disjoint range boundaries. With an extra index and a new lookup structure called Memory Filter, some sub-tries could be stored outside the TCAM. The experiments on real-life BGP route table will demonstrate that, by allocating little more conventional memory space, the proposed scheme reduces the TCAM storage requirement by 92% and significantly cuts down the power consumption.