线速数据包输入处理技术 被引量：13

1

作者 冯东雷 张勇 白英彩 《计算机研究与发展》 EI CSCD 北大核心 2002年第1期41-48,共8页

随着因特网的高速发展 ,因特网主干需要具备多业务能力的 G位、甚至 T位路由器 .这就使得数据包输入处理成为主干路由器的瓶颈 .线速数据包输入处理不仅对因特网主干路由器有重要意义 ,同时还可以应用在多层交换机、高速防火墙、高速入... 随着因特网的高速发展 ,因特网主干需要具备多业务能力的 G位、甚至 T位路由器 .这就使得数据包输入处理成为主干路由器的瓶颈 .线速数据包输入处理不仅对因特网主干路由器有重要意义 ,同时还可以应用在多层交换机、高速防火墙、高速入侵检测系统中 .综述了近年来数据包输入处理的最新研究进展 ,详细分析了线速数据包输入处理的关键问题和解决方案 .最后 。 展开更多

关键词 线速数据包输入处理 路由器 高速防火墙 入侵检测系统 服务质量 INTERNET

下载PDF 职称材料

一种基于跳转表的多维IP分类算法 被引量：6

2

作者 徐恪 梁志勇 吴建平 《小型微型计算机系统》 CSCD 北大核心 2001年第12期1409-1413,共5页

网络应用的发展要求路由器必须有能力支持防火墙、提供 Qo S、流量计费等一系列功能 ,这些功能都要求路由器对 IP包进行分类来完成对数据包的不同处理 .本文提出的算法直接从多维 IP分类问题入手 ,经过一个跳转表 ,把多维 IP分类问题转... 网络应用的发展要求路由器必须有能力支持防火墙、提供 Qo S、流量计费等一系列功能 ,这些功能都要求路由器对 IP包进行分类来完成对数据包的不同处理 .本文提出的算法直接从多维 IP分类问题入手 ,经过一个跳转表 ,把多维 IP分类问题转化为二维的 IP分类问题 ,从而提高了分类速度 .该算法可以充分发挥二维分类算法高效率的特点 。 展开更多

关键词 INTERNET 多维IP分类算法 路由器 跳转表 服务质量

下载PDF 职称材料

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

3

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

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

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

下载PDF 职称材料

一种基于哈希表和Trie树的快速IP路由查找算法 被引量：7

4

作者 崔尚森 张白一 《计算机工程与应用》 CSCD 北大核心 2005年第9期156-158,共3页

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。... Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。 展开更多

关键词 路由查找 最长前缀匹配 哈希 TRIE树

下载PDF 职称材料

高性能安全路由器BW7000的设计与实现 被引量：7

5

作者 徐明伟 徐恪 +4 位作者 熊勇强 江勇 孙晓霞 吴剑 喻中超 《中国工程科学》 2002年第3期54-62,共9页

高性能和安全是计算机网络研究的两个主要问题。路由器在保证转发性能的前提下提供网络安全保护已经成为当前的研究热点。文章介绍了在完成国家“八六三”计划重大课题“高性能安全路由器”的过程中解决的若干关键技术问题。高性能安全... 高性能和安全是计算机网络研究的两个主要问题。路由器在保证转发性能的前提下提供网络安全保护已经成为当前的研究热点。文章介绍了在完成国家“八六三”计划重大课题“高性能安全路由器”的过程中解决的若干关键技术问题。高性能安全路由器BW 70 0 0基于自主设计的高性能路由器操作系统HEROS。为保证高性能的路由转发 ,设计实现了基于RAM的高性能路由查找算法 ;为支持服务质量控制和安全管理 ,设计实现了基于无冲突Hash Trie树的分组分类算法和基于反馈的分布式分组调度算法 ;为保证网络安全 ,提出了基于分布式密钥管理的路由器安全体系结构。 展开更多

关键词 BW7000 设计 路由器 安全 操作系统 路由查找 计算机网络 结构

下载PDF 职称材料

Bitmap结构在高性能网络算法设计中的应用 被引量：4

6

作者 杨保华 亓亚烜 +1 位作者 薛一波 李军 《计算机工程与应用》 CSCD 北大核心 2009年第15期1-5,共5页

基于Bitmap数据结构的数据压缩技术是一种针对线性存储结构的有效压缩方法,虽被广泛用于网络处理的多个领域(路由查找、网包分类等),却一直缺乏深入的分析。给出了Bitmap结构能提高算法空间性能的理论根据。总结了Bitmap结构在典型网络... 基于Bitmap数据结构的数据压缩技术是一种针对线性存储结构的有效压缩方法,虽被广泛用于网络处理的多个领域(路由查找、网包分类等),却一直缺乏深入的分析。给出了Bitmap结构能提高算法空间性能的理论根据。总结了Bitmap结构在典型网络处理算法中的各种应用,给出了Bitmap结构的数学模型,并通过实例分析了Bitmap结构的优势和不足。Bitmap技术是一种能有效改善网络处理算法存储空间性能的通用技术,并给未来高性能网络处理算法设计提出以及现有算法的改进都提供了启发思路。 展开更多

关键词 BITMAP 路由查找 网包分类 模式匹配 高性能网络处理

下载PDF 职称材料

快速路由器的路由查找和流分类算法研究 被引量：1

7

作者 姚兴苗 李乐民 胡光岷 《电子科技大学学报》 EI CAS CSCD 北大核心 2004年第6期663-666,共4页

分析了路由器的体系结构发展,研究了路由查找算法和流分类算法在快速路由器中的应用。研究表明,基于分段压缩的路由查找算法支持IPv6路由查找,具有合理的存储容量和快速的查找时间;采用按值分支树的多维综合流分类算法支持前缀和范围匹... 分析了路由器的体系结构发展,研究了路由查找算法和流分类算法在快速路由器中的应用。研究表明,基于分段压缩的路由查找算法支持IPv6路由查找,具有合理的存储容量和快速的查找时间;采用按值分支树的多维综合流分类算法支持前缀和范围匹配,可扩展性强,适合大容量规则数据库。两种算法适合在快速路由器中应用。 展开更多

关键词 体系结构 路由查找 流分类 快速路由器

下载PDF 职称材料

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

8

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

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

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

下载PDF 职称材料

基于软件的网络处理器的路由高速缓存算法研究 被引量：2

9

作者 刘祯 刘斌 郑凯 《软件学报》 EI CSCD 北大核心 2007年第12期3115-3123,共9页

路由器需要以较低的代价灵活、高速地实现路由查找这一基本功能.为网络处理器设计了一种基于软件的路由查找高速缓存算法.网络处理器片上高速存储器中的一部分空间被划分出来,由指令代码来维护一个路由查找结果缓存表.通过选择合适的哈... 路由器需要以较低的代价灵活、高速地实现路由查找这一基本功能.为网络处理器设计了一种基于软件的路由查找高速缓存算法.网络处理器片上高速存储器中的一部分空间被划分出来,由指令代码来维护一个路由查找结果缓存表.通过选择合适的哈希函数,平衡表项之间的冲突并刷新复杂度,该算法可以缩短路由查找的延迟,减少多处理单元对存储器总线的竞争,为其他网络应用提供更多的处理时间.基于真实网络流量的实验表明,即便每个处理单元中仅有少量表项,网络处理器的吞吐量仍然可以得到有效的提升. 展开更多

关键词 路由高速缓存 网络处理器 路由查找

下载PDF 职称材料

自相似活跃子网前缀空间的路由查找

10

作者 彭艳兵 龚俭 +1 位作者 丁伟 徐加羚 《计算机学报》 EI CSCD 北大核心 2005年第8期1351-1359,共9页

IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空间是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化.文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前... IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空间是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化.文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前缀在不同的聚类规模上的次序统计量服从Pareto分布,主干路由表项的次序统计量也近似服从Pareto分布.该文提出了一种基于活跃度排序的路由逐次查找算法———SOSL,对IP地址查询进行了优化,在该文的模拟实验中,活跃路由表的规模、刷新周期和活跃度判定下限间存在一些对数线性关系,使得作者可以以很小的活跃路由表来实现全部路由查找需求的99%;为SOSL实现中最关键的活跃路由表排序问题提出了一个基于计数器溢出的方案,复杂度为O(1).对比发现该文的算法与TCAM结合能够提高TCAM的效率,高效地控制活跃路由表的规模,易于硬件实现. 展开更多

关键词 活跃IP 子网前缀 重尾分布 路由查询 统计优化 溢出排序

下载PDF 职称材料

高速网络路由器IP报文转发技术的研究与实现

11

作者 张晓明 唐玉华 张民选 《计算机工程》 CAS CSCD 北大核心 2001年第6期27-28,共2页

随着Internet的迅猛发展，高性能网络路由器在新一代高速IP网络中发挥着巨大的作用。而制约高性能网络路由器性能的瓶颈之一是IP报文的转发速度。针对当前先进的路由器体系结构，介绍了一种快速IP报文转发部件的设计方法及实现。

关键词 高速网络路由器 IP报文转发 INTERNET IP地址

下载PDF 职称材料

基于哈希表与多比特树的路由查找算法 被引量：2

12

作者 范富明 李念军 +1 位作者 雷升平 吉萌 《计算机工程》 CAS CSCD 北大核心 2015年第9期63-67,共5页

网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求。为此，将哈希表和多比特树相结合，提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中，采用哈希表存储路由下一跳的信... 网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求。为此，将哈希表和多比特树相结合，提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中，采用哈希表存储路由下一跳的信息，根据目的IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位，并通过表项的信息在对应的哈希表中读取下一跳信息，进行数据转发。在多核平台上的测试结果表明，该算法在百万条路由环境下可达到双向10GB／s的速度，平均查找次数介于1～2次之间，平均延时小于30μs。 展开更多

关键词 路由器 路由查找 哈希表 多比特树 最长前缀匹配

下载PDF 职称材料

基于OPNET的二叉树路由查找算法的设计与实现 被引量：1

13

作者 戴泽华 张连连 +1 位作者 邓全才 葛宇 《河北建筑工程学院学报》 CAS 2012年第3期55-59,共5页

路由器是构成因特网的中间节点,其转发性能决定了因特网的整体性能.IP查表算法的优劣直接影响了当前和未来因特网网络的整体性能.深入研究了二叉树路由查找算法,并在OPNET上对其进行了设计实现,从路由查询次数,单次查询所需时间。

关键词 二叉树 路由查找 OPNET

下载PDF 职称材料

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

14

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

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

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

下载PDF 职称材料

基于OPNET的卫星路由查找算法仿真分析

15

作者 邓全才 张连连 孙志田 《河北建筑工程学院学报》 CAS 2015年第1期113-116,共4页

为了更加直观的比较线性表算法、Trie tree算法以及Hash算法在卫星路由查找的性能,通过OPNET平台进行建模仿真.实验结果表明,三种算法路由查询次数相同.如果以访问次数为标准,选择Trie tree算法为宜.如果以查询深度为标准,选择Trie tre... 为了更加直观的比较线性表算法、Trie tree算法以及Hash算法在卫星路由查找的性能,通过OPNET平台进行建模仿真.实验结果表明,三种算法路由查询次数相同.如果以访问次数为标准,选择Trie tree算法为宜.如果以查询深度为标准,选择Trie tree算法为宜.如果以响应时间为标准,由于Hash算法不稳定,选择线性表算法和Trie tree算法为宜.因此实验结论为,Trie tree算法总体性能最佳,但算法实现比较复杂,Hash算法不稳定,但对规则的增减比较容易,线性表算法易于实现,但访问次数较高. 展开更多

关键词 路由查找 算法比较 键树 哈希 线性表

下载PDF 职称材料

测井网络路由器的研究与实现

16

作者 伍瑞卿 顾庆水 +1 位作者 陈伟 陈天麒 《北京邮电大学学报》 EI CAS CSCD 北大核心 2010年第2期116-120,共5页

为满足测井数据传输的实时性和可靠性要求,提出了轻量级的路由器设计方案.将点到点协议的状态机精简为3个状态和5个事件,缩小了逃逸字符的数量.路由缓存管理采用了最长首部对齐的预分配策略和减少搬移缓存数据的方法,设计了线性静态路... 为满足测井数据传输的实时性和可靠性要求,提出了轻量级的路由器设计方案.将点到点协议的状态机精简为3个状态和5个事件,缩小了逃逸字符的数量.路由缓存管理采用了最长首部对齐的预分配策略和减少搬移缓存数据的方法,设计了线性静态路由表的查找方法,并以数字信号处理器的定时器驱动和直接存储器访问方式快速处理缓存数据.试验结果表明,该轻量级路由器开销小,转发延迟和延迟抖动小,满足测井网络的需要. 展开更多

关键词 缓存管理 测井网络 路由查找 状态机 时延

下载PDF 职称材料

一种快速IPv6路由查找方案 被引量：5

17

作者 姚兴苗 李乐民 《计算机学报》 EI CSCD 北大核心 2005年第2期214-219,共6页

提出了一个可硬件实现的基于分段的快速IPv6路由查找方案.该方案支持快速的IP地址查找,并能有效地对路由前缀进行插入和删除操作.方案采用基于比特位置区分的压缩算法,与其它的 IPv6 路由查找方案相比较,所需存储器空间小,路由查找的平... 提出了一个可硬件实现的基于分段的快速IPv6路由查找方案.该方案支持快速的IP地址查找,并能有效地对路由前缀进行插入和删除操作.方案采用基于比特位置区分的压缩算法,与其它的 IPv6 路由查找方案相比较,所需存储器空间小,路由查找的平均时间少.如果采用SRAM流水线查找,可实现 125×106次/秒的查找速度.由于缺少实际的 IPv6路由前缀,该文生成了模拟路由前缀数据库.仿真试验结果表明:文章提出的方案具有合理的查找时间、空间和更新复杂度,容易硬件实现. 展开更多

关键词 IPV6路由查找 分段查找 压缩算法

下载PDF 职称材料

一种基于分段压缩的IPv6路由查找算法 被引量：2

18

作者 姚兴苗 李乐民 胡光岷 《通信学报》 EI CSCD 北大核心 2004年第10期51-57,共7页

提出了一种基于分段压缩的快速 IPv6 路由查找算法。与文献中的 LLCAT 算法相比,该算法节省了存储空间,当某扩展节点的表项所对应的前缀数量小于预先设定的值时,前缀不再扩展而使用压缩算法。同时,最坏情况下算法的查找时间和更新复杂... 提出了一种基于分段压缩的快速 IPv6 路由查找算法。与文献中的 LLCAT 算法相比,该算法节省了存储空间,当某扩展节点的表项所对应的前缀数量小于预先设定的值时,前缀不再扩展而使用压缩算法。同时,最坏情况下算法的查找时间和更新复杂度基本没有改变。仿真试验结果表明:算法的平均查找时间和消耗的存储器容量都优于 LLCAT 算法。 展开更多

关键词 IPV6路由查找 分段压缩 扩展前缀

下载PDF 职称材料

高速路由查找算法的研究

19

作者 廖恬瑜 涂晓东 黄协 《电子科技大学学报》 EI CAS CSCD 北大核心 2004年第6期722-725,729,共5页

介绍了路由查找算法的研究背景和一些技术指标,描述了几种具有代表性的IPv4高速路由查找算法,分析了其优缺点。阐述了基于硬件实现的高速路由查找算法——6级路由查找算法,给出了硬件实现结构,其仿真结果显示该算法实现了50×106次... 介绍了路由查找算法的研究背景和一些技术指标,描述了几种具有代表性的IPv4高速路由查找算法,分析了其优缺点。阐述了基于硬件实现的高速路由查找算法——6级路由查找算法,给出了硬件实现结构,其仿真结果显示该算法实现了50×106次路由查找/s。 展开更多

关键词 路由查找算法 6级路由查找 硬件实现

下载PDF 职称材料

基于前驱查找的快速IP路由查找和更新方案 被引量：1

20

作者 陆笑天 李曦 +1 位作者 周学海 纪金松 《计算机工程》 CAS CSCD 北大核心 2007年第13期127-129,152,共4页

路由器的转发速率通常受限于选择路由的速度,因此路由查找和更新的方法在路由器设计中至关重要。文章提出了一种可硬件实现的快速IP路由查找和更新方法,将IP前缀匹配等价为地址范围搜索,采用B-树结构存储路由表。这种方案对存储要求较低... 路由器的转发速率通常受限于选择路由的速度,因此路由查找和更新的方法在路由器设计中至关重要。文章提出了一种可硬件实现的快速IP路由查找和更新方法,将IP前缀匹配等价为地址范围搜索,采用B-树结构存储路由表。这种方案对存储要求较低,仅由小容量的片上SRAM和片外DRAM构成。实验表明,该方案在简单硬件支持下就能够达到OC-48的转发要求。 展开更多

关键词 IP路由查找 IP路由更新 B-树 地址范围 前驱查找

下载PDF 职称材料