一种基于重叠位图的路由查找算法
计 算 机 学 报 2017 年在线发布 CHINESE JOURNAL OF COMPUTERS 2017 Online 本课题得到国家自然科学基金(61432009, 61373143, 61602271)、博士后面上基金(016M591182)、教育部博士学科点专项科研基金(0130002110084)资助. 刘斌, 男, 1964年生, 博士, 教授, 中国计算机学会(CCF)专业会员(22229M), 主要研究领域为高性能交换机/路由器、网络处理器、命名数据网络、软件定义网络等. E-mail: liubmail.tsinghua.edu.cn. 张楚文(通讯作者), 男, 1992年生, 博士研究生, 主要研究领域为高性能交换机/路由器、命名数据网络、车联网等. E-mail: chuwen1992gmail.com. 一种基于重叠位图的路由查找算法 刘斌 张楚文 (清华大学计算机系, 北京 100084) 摘 要 路由查找是路由器的核心功能之一，可分为基于硬件和基于软件的查找算法两大类。前者使用专用的可并行硬件实现高速的查找性能，比如 FPGA 算法、GPU 算法和 TCAM 算法。后者可以部署在通用 CPU 上，具有更高的灵活性、更低的功耗和成本优势，并且可以利用 CPU 的 Cache 实现快速查找。因此，基于软件的路由查找算法已成为软件定义网络和网络功能虚拟化中的关键技术之一。尽管软件查找算法具有很大的优势，它也面临着许多新的挑战。首先，当今骨干网路由器的路由表项数目已达到 600K，并且每年保持大约 15%的增长率，给路由查找和存储带来了巨大压力。同时，路由表更新速度也逐年稳定增长，并且峰值更新速率已超过 10K 更新/秒，这就要求路由查找算法具有高速的更新性能。基础的树结构软件查找算法能够支持快速更新，但是过多的访存次数导致查找速度较低，而且其存储开销已经超过 16MB，远远高于一般路由器中 CPU 的 Cache 大小，进一步影响了查找速度。以 Lulea 算法为代表的传统的位图压缩方法虽然降低了数据结构的存储开销，但是会导致更新困难，复杂而低效的更新操作也会在一定程度上影响查找性能。本文提出了一种基于重叠位图压缩的软件路由查找算法，它通过层次遍历构造重叠式位图结构，比具有高压缩率的 Lulea 算法占用的更小的存储空间（提高Cache 的命中率，从而进一步提高查找速度） 。而且，本算法使用位图分割和多种更新优化技术实现快速的增量更新。实验结果表明本算法能够把包含 600K 条前缀的路由表压缩到 2.3MB， 平均比 Lulea 算法减少 26%的存储空间， 只有树结构的 1/8左右。而且本算法具有良好的拓展性，从 2008 年的 5.06 字节/前缀降低到 2016 年的 3.94 字节/前缀。实际流量下，本算法平均查找速度达到111.41M查找/秒， 是Lulea算法查找速度的2.5倍。 同时， 在保证10100K更新/秒的前提下， 实现90M100M查找/秒的查找速度。 关键词 路由查找；位图压缩；增量更新；层次遍历；重叠位图 中图法分类号 TN915 An Overlay Bitmap-based Routing Lookup Scheme LIU Bin ZHANG Chu-Wen (Department of Computer Science, Tsinghua University, Beijing 100084) Abstract 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 at10K 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 计算机学报2 计 算 机 学 报 2017 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 90100 MSPS with the ability to handle 10100K updates per second at the same time. Key words routing lookup; bitmap compression; incremental update; level traversal; overlay bitmap 1 引言 路由查找是路由器根据路由表为网络流量选 择路径的过程。路由查找算法的功能包括将路由表 存储为高效的数据结构，并实现查找和更新。路由 查找算法的性能在很大程度上决定了路由器的性 能，故其研究意义重大。 路由查找算法可以分为基于硬件的查找算法 和基于软件的查找算法两大类。
