Binary Search on Prefix Covered Levels for IP Address Lookup

IP address lookup is a challenging problem because of increasing forwarding table size, increasing Internet traffic, higher link speed, frequent prefix updates, migration to 128 bit IPv6 addresses and higher power consumption. IP address lookup need to do two dimensions match to find the longest match prefix. Traditional schemes implement IP address lookup using linear or binary search on prefix lengths or prefix values at the cost of slow lookup speed, complex pre-computation or high power consumption. A novel binary search algorithm based on prefix covered levels is proposed in this paper. At each level we use TCAMs to determine whether there is a match. TCAM entries need not be sorted because prefixes at each level are disjoint. Precomputation is no longer needed and incremental updates are supported. IP address lookup can be done in O(log₂max_level+1) TCAM clock cycle at the worst case where max_level is the max number of overlapping prefixes. The current max_level is 7 for IPv4 and 2 for IPv6. With single TCAM chip having several blocks and keeping one block working and the other blocks power off, or with several independent TCAM chips arranged in pipeline architecture, we can support 40 Gbps line-speed forwarding and reduce the power consumption about 50%. Complexity comparison and performance evaluation shows the proposed scheme has better performance over other schemes.