An Overlay Bitmap-based Routing Lookup Scheme

Routing lookup is one of the key functions of network routers, which can be divided into hardware-based and software-based algorithm. The former, such as FPGA-based, TCAM-based and GPU-based algorithms, uses dedicated and parallelizable hardware to achieve high lookup speed. The latter, which can be deployed on a commodity CPU, is more flexible, more energy-saving and cheaper, and the lookup performance can also be improved by exploiting the CPU cache. Therefore, it has become one of the key technologies in SDN (software defined network) and NFV (network functional virtualization). While software-based routing lookup algorithm is attractive, it faces some new challenges. Nowadays, Backbone route tables maintain an annual growth rate of around 15% and the number of route table prefixes has reached up to 600K. The drastic expansion of the route table brings enormous pressure on lookup speed and storage space. Meanwhile, the update rate grows steadily and reaches a peak update rate at 10K updates per second, which requires the advent of algorithms with high-speed update performance. The binary trie is the basic software-based routing lookup algorithm. Although it can support fast updates, its lookup speed is slow because of too many times of memory access. And its storage space has exceeded 16 MB to store a route table of 600K prefixes, much higher than the CPU cache size in the line-card of a general router, which will decrease the slow lookup speed further. The traditional bitmap-based routing lookup schemes represented by Lulea algorithm can compress storage redundancy and build small data structure to fit into caches. However, they usually aggravate the incremental update and cannot meet the requirement of update speed in real networks. Their inefficient update will also interrupt the normal lookup and thus decrease the lookup throughput. In this paper, we propose an overlay bitmap-based software routing lookup scheme. It constructs overlay bitmap structures through hierarchical traversal, which can eliminate the horizontal redundancy in traditional bitmap and achieve even smaller storage than the high compressed bitmap-based scheme Lulea (increasing the cache hit rate and thus boosting lookup speed further). In addition, it performs fast incremental update using bitmap segmentation and a variety of update optimization techniques. Experimental results show that our scheme can compress a route table of 600K prefixes to a 2.3 MB data structure, reducing 26% storage space than Lulea algorithm on average, which is only about 1/8 of the binary trie. Besides, the storage space of our scheme is more scalable, decreasing from 5.06 bytes per prefix in 2008 to 3.94 bytes per prefix in 2016. Under the real network traffic, its average lookup speed can reach up to 111.41 MSPS (million searches per second), about 2.5 times as fast as that of Lulea algorithm, benefiting from the smaller memory footprint and higher cache hit rate. Tests on update performance show that it can sustain up to 1.82 million updates per second. And it can achieve a fast lookup up to 90-100 MSPS with the ability to handle 10-100K updates per second at the same time. © 2018, Science Press. All right reserved.