骨干网路由表查找、压缩及增量更新技术研究

With the fast development of Internet, the size of backbone routing table maintains a rapid growth, which brings three major problems: routing table compression, routing lookup, fast incremental update. These three problems are closely connected. Existing researches often sacrifice the incremental update performance in pursuit of high routing compression ratio or fast lookup, and a complete solution coving the three problems have not been presented as far as we know. The system performance will be optimized, only if the three problems are solved simultaneously. Based on our previous work, we strive to make innovations in the following aspects: 1) study a novel routing table compression algorithm, which can achieve high compression ratio, fast compression speed, fast incremental update, and long recompression interval; 2) study a universal fast incremental update algorithm; 3) study a software-based parallel lookup soltion coving the three problems; 4) study a hardware-based parallel lookup solution coving the three problems.

近年来，随着互联网的迅速发展，骨干网路由表飞速膨胀，引发了三个亟待解决的关键问题：路由表压缩、路由表查找和快速增量更新。这三个问题紧密联系、相互影响。已有的文献在追求高压缩率或快速查找的过程中往往牺牲了系统增量更新的能力，尚未看到可以同时兼顾这三个问题的解决方案。要实现高性能路由器，三个问题都必须得到妥善的解决。本项目立足于前期工作，力求从以下三个方面寻求突破和创新：1）研究出一种压缩率高、压缩速度快、增量更新快、重压缩间隔长的路由表压缩算法；2）研究出一种通用的快速增量更新算法；3）研究出一种可以兼顾三个问题的软件并行查找方案；4）研究出一种可以兼顾三个问题的硬件并行查找方案。本项目研究的三种关键技术对高性能路由器的实现和下一代互联网的发展有着重要的理论意义和应用前景。

近年来，随着互联网规模的不断扩大，骨干网路由表条目数快速增长，给路由表的存储带来了很大的压力，一种有效的解决方案是采用路由表压缩技术。同时，骨干网的链路速率也在不断提高，对路由表查找速度提出了更高的要求。此外，各种新应用使得互联网的动态特性增强，导致路由表更新越来越频繁，而且呈现出突发性，这就要求路由表在实施压缩和提高查找速度的同时，必须具有快速增量更新的能力。本项目围绕这三个问题展开研究，取得了如下成果：.(1) 提出了一种二维分割框架，然后在该框架下对分割后的两部分数据结构进行优化。提出一族SAIL算法，该算法同时实现O(1)的查找时间和O(1)的片内内存，在应用到虚拟路由表的查找后，该方案不但保证了O(1)的查找时间和O(1)的片内内存，而且与虚拟路由表的个数、特征、大小无关。.(2) 针对一些路由器无法容纳飞速增长的路由表的问题，采用社会学中种子选举的思想，提出了两种压缩率高、压缩速度快、增量更新快、重压缩周期长的路由表压缩算法；针对前缀重叠给查找和更新带来诸多困难的问题，提出了一种构建最优的无重叠路由表的压缩算法；针对已有路由表压缩算法缺乏理论支持的问题，提出了一套通用的数学分析证明方法。.已有的文献大都在追求高压缩率或快速查找的过程中牺牲了系统增量更新的性能，尚未看到可以很好兼顾这三个问题的解决方案。不同级别的路由器对路由表查找的需求不同，本项目在针对下面三个典型的场景给出对应的解决方案：.(2) 场景一：未来互联网需要极高性能的路由器，可以容忍高硬件成本和高功耗。本项目在CLPL方案的基础上，提出了一套可以兼顾压缩、查找、更新的并行硬件查找方案CLUE。.(3) 场景二：一些核心路由器需要进行高速查找，而不愿付出高硬件成本和高功耗。本项目提出了一次片内访存就可以完成一次查找的基于布隆过滤器（Bloom filter）的软硬件结合查找方案TDDBF，该方案支持快速增量更新。 .(4) 场景三：一些中高档路由器需要进行快速查找，希望用技术成本换取硬件成本，采用速度较快的基于trie树的精妙而复杂的路由表查找算法，却无法解决其更新问题。本项目根据更新消息的两个特性，提出了一种通用的超高速增量更新算法，该算法可以应用到所有基于trie树的路由表压缩和查找算法。.本项目研究的三种关键技术对高性能路由器的实现和未来互联网的发展有着重要的理论意义和应用前景。