Power-saving and memory-efficient network search engines with fast updating.

摘要

Ternary Content Addressable Memories (TCAMs) have been widely considered as the most promising devices for composing hardware solutions for speedy IP address lookups. Their parallel search functionality and triple state characteristic ease the complex Longest Prefix Match (LPM) procedure traditionally implemented using the relatively involved trie structure. Despite their prominent search performance, however, TCAMs traditionally suffer from lengthy updating and excessive power consumption. Internet instability and growth severely challenge the design of a high-performance, TCAM-based IP address search engine (SE). In this dissertation, we elaborate three network search engine architectures aimed at tackling the two aforementioned shortcomings of TCAM. The key idea behind the MIPS-based search engine is to store and maintain a forwarding table in TCAM according to the Minimum Independent Prefix Set (MIPS), totally eliminating the prefix order constraint and simplifying the TCAM updating procedure. The technique named Bounded Prefix Expansion and Compression (BPEC) is proposed to fairly stabilize the incremental updates on generic TCAMs by bounding the maximum number of TCAM insertions for each MIPS update. As a result, frequent routing table updates no longer have a marked adverse impact on lookup performance in our schemes. Moreover, both the MIPS- and BPEC-based solutions exhibit considerable forwarding table compression in practice, which helps to save the relatively valuable TCAM space and reduce TCAM power consumption. The third solution is proposed for the purpose of conserving TCAM power. Its design is based on a high-efficiency algorithm denoted as Exact Table Partitioning (ETAP), which enables only one single segment of a TCAM to be involved in each search operation. Eventually, the ETAP-based solution is able to confine the overall system power consumption within a pre-determined power budget. The effectiveness of the three network search engine solutions has been verified by extensive experiments conducted using real-world routing tables obtained from the Internet. Their performance is evaluated and compared with some earlier works, showing that our designs are clearly superior.