一种基于重叠位图的路由查找算法

An Overlay Bitmap-based Routing Lookup Scheme

路由查找是路由器的核心功能之一,可分为基于硬件和基于软件的查找算法两大类.前者使用专用的可并行硬件实现高速的查找性能,比如FPGA算法、GPU算法和TCAM算法.后者可以部署在通用CPU上,具有更高的灵活性、更低的功耗和成本优势,并且可以利用CPU的Cache实现快速查找.因此,基于软件的路由查找算法已成为软件定义网络和网络功能虚拟化中的关键技术之一.尽管软件查找算法具有很大的优势,它也面临着许多新的挑战.首先,当今骨干网路由器的路由表项数目已达到600K,并且每年保持大约15%的增长率,给路由查找和存储带来了巨大压力.同时,路由表更新速度也逐年稳定增长,并且峰值更新速率已超过10K/s,这就要求路由查找算法具有高速的更新性能.基础的树结构软件查找算法能够支持快速更新,但是过多的访存次数导致查找速度较低,而且其存储开销已经超过16MB,远远高于一般路由器中CPU的Cache大小,进一步影响了查找速度.以Lulea算法为代表的传统位图压缩方法虽然降低了数据结构的存储开销,但是会导致更新困难,复杂而低效的更新操作也会在一定程度上影响查找性能.本文提出了一种基于重叠位图压缩的软件路由查找算法,它通过层次遍历构造重叠式位图结构,比具有高压缩率的Lulea算法占用更小的存储空间(提高Cache的命中率,从而进一步提高查找速度).而且,本算法使用位图分割和多种更新优化技术实现快速的增量更新.实验结果表明本算法能够把包含600K条前缀的路由表压缩到2.3MB,平均比Lulea算法减少26%的存储空间,只有树结构的1/8左右.而且本算法具有良好的拓展性,从2008年的5.06字节/前缀降低到2016年的3.94字节/前缀.实际流量下,本算法平均查找速度达到111.41M/s,是Lulea算法查找速度的2.5倍.同时,在保证10~100K/s的更新速率前提下,实现90~100M/s的查找速度.

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 600 K.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 10 K 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 600 K 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 600 K 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 0x09 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-100 K updates per second at the same time.