路由查找算法研究综述 被引量：43

1

作者 徐恪 徐明伟 +1 位作者 吴建平 吴剑 《软件学报》 EI CSCD 北大核心 2002年第1期42-50,共9页

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps^10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分... 随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps^10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀区配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向. 展开更多

关键词 路由器 路由查找算法 IP地址 INTERNET

下载PDF 职称材料

路由查找算法评价系统的设计与实现 被引量：3

2

作者 徐恪 吴建平 吴剑 《小型微型计算机系统》 CSCD 北大核心 2003年第2期273-276,共4页

路由查找是决定路由器报文转发能力的重要因素 .近年来 ,为了提高路由查找的速度 ,研究人员提出了多种新的路由查找算法 .本文首先提出了路由查找算法的评价标准 .为了对查找算法进行全面评价 ,设计和实现了路由查找算法评价系统 ,并对... 路由查找是决定路由器报文转发能力的重要因素 .近年来 ,为了提高路由查找的速度 ,研究人员提出了多种新的路由查找算法 .本文首先提出了路由查找算法的评价标准 .为了对查找算法进行全面评价 ,设计和实现了路由查找算法评价系统 ,并对主要的几种路由查找算法进行了分析评价 . 展开更多

关键词 路由查找算法 评价系统 设计 评价标准 计算机网络 路由器

下载PDF 职称材料

基于二分查找和Trie的IPv6路由查找算法 被引量：4

3

作者 杨玉梅 黎仁国 《兰州理工大学学报》 CAS 北大核心 2012年第4期98-102,共5页

分析基于前缀长度的二分路由查找算法和基于Trie的路由查找算法的优缺点,在此基础上提出一个改进的路由查找算法,并给出其在IPv6下的实现方案.由于基于前缀长度的二分路由查找算法扩展性好、查找速度快,而基于Trie的路由查找算法实现灵... 分析基于前缀长度的二分路由查找算法和基于Trie的路由查找算法的优缺点,在此基础上提出一个改进的路由查找算法,并给出其在IPv6下的实现方案.由于基于前缀长度的二分路由查找算法扩展性好、查找速度快,而基于Trie的路由查找算法实现灵活、转发表动态更新快,这使得所提算法具备路由转发表动态更新快、查找速度快、对前缀长度扩展性好等优点.模拟实验表明该算法能够较好地满足IPv6的要求. 展开更多

关键词 IPV6 路由查找算法 二分查找 路由转发表

下载PDF 职称材料

基于二分法搜索hash表的快速IP路由查找算法 被引量：3

4

作者 张明杰 卢锡城 《计算机工程与科学》 CSCD 2000年第5期14-16,共3页

路由器设计中 ,IP地址的路由查找算法设计很重要 ,算法的性能将直接影响路由器的性能。本文对 Waldvogel等人提出的二分法查找 hash表算法进行了改进 ,使路由查找效率从至多 5次hash表访问减少为至多 3次 hash表访问。

关键词 路由器 IP地址 路由查找算法 HASH表 二分法搜索

下载PDF 职称材料

基于FPGA的高速路由查找算法 被引量：4

5

作者 张毅 郭玲丽 《电子元器件应用》 2009年第9期22-23,27,共3页

随着因特网速度的不断提高、网络流量的不断增加和路由表项数目的不断增大,IP路由查找速度已经成为制约核心路由器性能的主要瓶颈。为了减少存储器的访问次数,提高路由查找速度。文中提出了一种基于四级流水线的并行查找方法,即并行查... 随着因特网速度的不断提高、网络流量的不断增加和路由表项数目的不断增大,IP路由查找速度已经成为制约核心路由器性能的主要瓶颈。为了减少存储器的访问次数,提高路由查找速度。文中提出了一种基于四级流水线的并行查找方法,即并行查找四片存储器并进行最长前缀匹配,从而在一次访问存储器时间内完成查找的实现方法,同时给出了其硬件实现结构。仿真实验结果显示,该算法可实现100Mpps的查找速度并具有查找速度快、支持动态更新和易于硬件实现的特点,能满足20Gbps的核心路由器环境要求。 展开更多

关键词 路由查找算法 最长前缀匹配 硬件实现

下载PDF 职称材料

IPv6快速路由查找算法分析与研究 被引量：1

6

作者 刘宏义 《微电子学与计算机》 CSCD 北大核心 2008年第4期181-184,共4页

分析了IPv6路由结构的特点,介绍了IPv6中的各种路由查找技术,提出了基于聚集位向量的快速路由查找算法,并对该算法和常用二分查找算法的性能进行了分析比较,实验结果表明该算法较好地提高了查找速度,减少了对内存的消耗.

关键词 IPV6 路由查找算法 聚集位向量

下载PDF 职称材料

散列索引多分支Trie树快速路由查找算法

7

作者 崔尚森 冯博琴 《计算机应用与软件》 CSCD 北大核心 2005年第9期115-117,共3页

路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进... 路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点。 展开更多

关键词 最长前缀匹配 路由查找算法 散列表 多分支Trie树 快速路由查找算法 TRIE树 索引 散列 IPv4地址 IP分组

下载PDF 职称材料

扩展压缩树算法——一种基于树型结构的快速路由查找算法

8

作者 孙卫强 洪佩琳 +1 位作者 李津生 杨海军 《计算机工程与应用》 CSCD 北大核心 2001年第22期50-53,共4页

摘要随着近几年因特网上业务的飞速发展,基于第三层交换技术的路由器研究也有了很大的突破。基于硬件的快速路由查找技术是下一代路由器设计的核心技术之一。文章将讨论一种基于树型结构的IPv4快速路由查找算法,对这种算法的性能进行分... 摘要随着近几年因特网上业务的飞速发展,基于第三层交换技术的路由器研究也有了很大的突破。基于硬件的快速路由查找技术是下一代路由器设计的核心技术之一。文章将讨论一种基于树型结构的IPv4快速路由查找算法,对这种算法的性能进行分析,提出算法本身存在的问题和性能上的不足,然后按照研究结果,提出了一种改进的算法———扩展压缩树算法。最后,将证明无论在性能和还是在可实现性上,扩展压缩树算法都比原算法有较大的提高。 展开更多

关键词 INTERNET 扩展压缩树算法 树型结构 快速路由查找算法

下载PDF 职称材料

Linux IP路由查找算法研究

9

作者 李金库 张德运 张勇 《小型微型计算机系统》 CSCD 北大核心 2001年第9期1141-1143,共3页

随着 Internet技术的发展 ,尤其是网络带宽的不断扩展 ,在 IP路由器中 ,当数据包到达时 ,需要极快的路由查找速度 ,但现存的路由查找受其设计算法的限制 ,越来越难以满足这种需要 .本文在分析了 L inux下的路由查找机制的基础上 。

关键词 INTERNET LINUX IP地址 路由器 路由查找算法

下载PDF 职称材料

IPv4/IPv6双栈四分搜索路由查找算法与实现

10

作者 王振兴 张彦肖 邬江兴 《通信学报》 EI CSCD 北大核心 2005年第7期8-15,共8页

IPv4/IPv6双协议栈核心路由器需要高性能一体化路由查找。传统的前缀长度二分查找算法完成一次IPv6路由查找需多达7步搜索,而核心路由器常用的单级TCAM方案要求转发表的存储必须按前缀长度相对地址降序排列,这种降序操作严重影响表项更... IPv4/IPv6双协议栈核心路由器需要高性能一体化路由查找。传统的前缀长度二分查找算法完成一次IPv6路由查找需多达7步搜索,而核心路由器常用的单级TCAM方案要求转发表的存储必须按前缀长度相对地址降序排列,这种降序操作严重影响表项更新速度和路由查找连续性。与对前缀长度二分查找和单级TCAM方案不同,作者提出了一种独特的对前缀范围四分搜索路由查找算法,并用3级TCAM实现了IPv4/IPv6双栈一体化QSPE查找方案。一次查找仅需3步搜索、转发表无需排序、表项更新快、查找速率高且连续性好,满足IPv4/IPv6双栈核心路由器OC-768(40Gbit/s)端口的线速率转发。 展开更多

关键词 计算机网络 路由查找算法 四分搜索 快速更新 查找连续性 IPV4/IPV6双栈

下载PDF 职称材料

一种基于ABV的IPV6快速路由查找算法

11

作者 党小超 李焱 李学军 《兰州大学学报（自然科学版）》 CAS CSCD 北大核心 2006年第2期92-95,共4页

分析了 IPV6路由结构的特点,介绍了 IPV6各种路由查找技术,提出了基于 ABV 的快速路由查找算法,并对算法的性能进行了分析比较．

关键词 IPV6 路由查找算法 ABV

下载PDF 职称材料

TCAM快更新高速路由查找算法与实现

12

作者 王振兴 张毅 张彦肖 《电讯技术》 2006年第1期63-67,共5页

常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性。本文提出并实现了一种独特的对前缀范围对分搜索的IPv4五步TCAM流水查找方法。突出... 常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性。本文提出并实现了一种独特的对前缀范围对分搜索的IPv4五步TCAM流水查找方法。突出特点是转发表不需排序,查找速率高,表项更新快,查表连续性好,可满足IPv4核心路由器双OC-768(40Gbps)端口、48B包的线速转发。 展开更多

关键词 核心路由器 IP路由查找 对分搜索 快速更新 查表连续性 TCAM流水处理 路由查找算法 TCAM 更新速度 高速

下载PDF 职称材料

基于无冲突哈希表和多比特树的两级IPv6路由查找算法 被引量：5

13

作者 杜飞 董治国 +1 位作者 苗琳 庹宇鹏 《计算机应用》 CSCD 北大核心 2013年第5期1194-1196,1202,共4页

为了提高IPv6的路由查找效率,根据IPv6路由前缀分布规律和前缀层次关系,提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中,剩下不足的前缀比特由多比特... 为了提高IPv6的路由查找效率,根据IPv6路由前缀分布规律和前缀层次关系,提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中,剩下不足的前缀比特由多比特树存储,IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明,该查找算法的平均查找路径数为1.0～1.7,适用于高速的IPv6路由查找。 展开更多

关键词 路由查找算法 IPV6 多比特 哈希表 无冲突 查找效率 层次关系 分布规律

下载PDF 职称材料

采用Trie和二分查找的IPv6路由查找算法

14

作者 陈超 《控制工程期刊（中英文版）》 2013年第3期147-154,共8页

在IPv6下由于地址长度增加，导致路由器负担加重，目前很多已有的路由查找算法扩展到IPv6后无法适应新的需求。因此，路由查找算法要达到对IPv6很好的适应性，必须要在缓存策略、压缩策略、前缀扩展、独立前缀转化等各个方面都具有很好... 在IPv6下由于地址长度增加，导致路由器负担加重，目前很多已有的路由查找算法扩展到IPv6后无法适应新的需求。因此，路由查找算法要达到对IPv6很好的适应性，必须要在缓存策略、压缩策略、前缀扩展、独立前缀转化等各个方面都具有很好的性能。本文首先简要分析了基于Trie的路由查找算法和基于前缀长度的二分路由查找算法的优缺点，在此基础上提供了一个改进的路由查找算法并给出了其在IPv6下的实现方案。该改进算法把基于Trie的路由查找算法和基于前缀长度的二分路由查找算法结合起来，从而使其具备路由转发表动态更新、查找速度快、对前缀长度扩展性好等特点。仿真实验表明该算法能够较好地满足IPv6的要求。 展开更多

关键词 二分查找 IPV6 路由查找算法 路由转发表 MVRF

下载PDF 职称材料

基于Bloom滤波器的IPv6路由查找算法

15

作者 李慧敏 林锦贤 《福建电脑》 2008年第12期7-8,共2页

随着IPv6协议的广泛应用,传统的IPv4路由表查找算法不再适应IPv6网络环境中路由转发的需要。因而提出一种IPv6路由查找算法,利用Bloom滤波器来实现并行的最长前缀匹配,缩小查找范围,使得每次查找的平均hash探索次数有所减少,从而提高查... 随着IPv6协议的广泛应用,传统的IPv4路由表查找算法不再适应IPv6网络环境中路由转发的需要。因而提出一种IPv6路由查找算法,利用Bloom滤波器来实现并行的最长前缀匹配,缩小查找范围,使得每次查找的平均hash探索次数有所减少,从而提高查找速度。 展开更多

关键词 路由查找算法 BLOOM滤波器 IPV6

下载PDF 职称材料

快速路由查找算法研究 被引量：4

16

作者 王智强 王振兴 张定心 《计算机应用研究》 CSCD 北大核心 2004年第2期231-234,240,共5页

随着互联网络光链路速率不断提高,路由查找已成为路由器报文转发的瓶颈。主要介绍近年来提出的各种路由查找方法,并对各种方法的性能及对IPv6适应性进行了分析比较。

关键词 路由查找算法 最长前缀匹配 性能比较

下载PDF 职称材料

高速路由器中基于树型结构路由查找算法的研究与实现 被引量：5

17

作者 刘永锋 杨宗凯 《计算机工程与科学》 CSCD 2004年第1期22-25,共4页

本文在比较各种基于树型结构查找算法的基础上提出了一种改进的路由查找算法,该算法具有查找速度快、所需存储空间小、更新速度快、硬件实现简单等特点,能够满足10Gbps核心路由器环境的要求。

关键词 路由器 树型结构 路由查找算法 功能模块 硬件模块

下载PDF 职称材料

B-树和bloom filter相结合的IPv6路由查找算法 被引量：1

18

作者 姚明 赵晶晶 +1 位作者 贺兴亚 杨云 《计算机应用研究》 CSCD 北大核心 2019年第9期2764-2768,共5页

为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和bloom filter相结合的IPv6路由查找算法(BTBF)。BTBF分为B-树和bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向... 为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和bloom filter相结合的IPv6路由查找算法(BTBF)。BTBF分为B-树和bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到bloom filter,再利用bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。 展开更多

关键词 路由查找算法 B-树 BLOOM filter IPv6骨干路由表

下载PDF 职称材料

基于Trie的快速路由查找算法 被引量：1

19

作者 王智强 王振兴 张定心 《信息工程大学学报》 2003年第3期10-13,共4页

随着互联网络光链路速率不断提高,路由查找已成为路由器报文转发的瓶颈。本文主要介绍近年来基于Trie的各种路由查找方法,同时对各种方法的性能进行了比较,最后介绍了一种性能优良的基于Trie的路由查找算法———压缩树算法。

关键词 路由查找算法 最长前缀匹配 TRIE 压缩树

下载PDF 职称材料

动态快速路由查找算法 被引量：1

20

作者 刘亚林 《中国工程科学》 2002年第7期60-68,共9页

给出了动态快速路由查找算法 (DFR)的原理和实现。该算法采用特殊的数据结构来构建索引表 ,能支持动态插入、删除和更新路由 ;DFR算法最多 4次访存 ,最少 2次访存 ,就能找到完整的路由信息。该算法不仅适用于软件实现 ,而且由于查找简... 给出了动态快速路由查找算法 (DFR)的原理和实现。该算法采用特殊的数据结构来构建索引表 ,能支持动态插入、删除和更新路由 ;DFR算法最多 4次访存 ,最少 2次访存 ,就能找到完整的路由信息。该算法不仅适用于软件实现 ,而且由于查找简单 ,也适合于硬件实现。 展开更多

关键词 动态快速路由查找算法 前缀扩展 DFR 路由查找 设计 路由器

下载PDF 职称材料