论文部分内容阅读
该文对路由器中的快速路由查找算法进行了研究.针对路由查找算法在查找速度、算法空间复杂度以及插入和删除表项的难度等方面存在的问题,提出了一种快速路由查找算法.该算法通过构造两级索引表结构来减小路由查找的访存次数以提高查找速度;利用前缀扩展的特性并采用特殊的数据结构来构建索引表,能支持动态插入、删除和更新路由;采用压缩技术对二级索引表进行压缩,从而大大减小了路由所需的存储空间.该算法最多四次访存,最少两次访存就完成一次路由查找.由于采用了压缩方法,所需存储空间很小,该算法不仅适合于软件实现,也适合于硬件实现.