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

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

项目编号： No.61202489

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 杨仝

作者单位： 中国人民解放军空军工程大学

项目金额： 23万元

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

中文关键词： 路由压缩；路由表查找；快速增量更新；盲点算法；航海算法

英文摘要： 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.

英文关键词： routing table compression；routing lookup；fast incremental update；blind spot；SAIL