一种改进的IPV6最长前缀匹配路由查找算法

本文就是在研究已有算法的基础上,结合IPv6地址的特征以及路由表中前缀的分布规律,提出了一种改进的、基于索引表和Trie树的查找算法,该算法在时间复杂度和空间复杂度上表现出了较好的性能。     

一种改进的二分查找算法

当前在有序数列查找中二分查找最为常用,但是二分查找在一些特殊情况下,其查找效率很低,如查找元素是数列中的第一个元素和最后一个元素。针对这种情况,结合数列特性,设计了一种改进的二分查找算法。改进的二分查找算法经理论和实验证明,其平均查找长度介于1和n+1/nlog2(n+1)-1之间,明显优于二分查找的平均查找长度n+1/nlog2(n+1)-1,实现难度比参考文献[1]要容易。     

快速路由查找算法研究

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

一种新的快速IPv6路由查找算法

在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。     

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

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

一种改进的二分法IPv6路由查找算法

随着IPv6协议的广泛应用，传统的IPv4路由表查找算法不再适应IPv6网络环境中路由转发的需要。该文在基于hash表的二分查找算法基础之上，提出了一种改进算法，该算法应用于超大规模路由表时能表现出较好、稳定的运行效率。为了减小内存消耗，还针对该算法提出了优化方案，并通过实验数据进行了对比分析。     

一个多功能路由查找引擎的设计与实现

针对网络边缘和接入层设备需处理多种网络协议和价格敏感的特点,文中介绍了一种能支持精确匹配和最长前缀匹配的多功能查找引擎。此引擎以五级环行多功能流水线为核心,通过SRAM接口与主机交互,采用ZBTSRAM作为路由表存储器。文中着重介绍了引擎的硬件结构、软件系统和软硬件联合验证方法。性能评测表明,基于FPGA的实现主频可达到50MHz,性能可以满足1Gbps￣2Gbps的接入和边缘层设备要求。     

基于RAM和TCAM存储结构的高速路由查找算法

由于因特网速度的不断提高,网络流量的不断增加和路由表规模的不断扩大,IP路由查找已经成为制约核心路由器性能的主要瓶颈。文章分析了两种常用的基于硬件存储器的路由查找算法,并结合它们各自优点,提出了一种基于RAM和TCAM存储结构的路由查找算法,该算法克服了上述两种算法的不足,具有查找速率高、更新时间快、存储代价低、易于实现等特点,是一种理想的适合于高速核心路由器环境的查找机制。     

一种新的二分路由查找方法

分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2max_level+1)个TCAM时钟周期内完成1次路由查找,其中max_level为最大的前缀覆盖级别,目前max_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.     

路由查找算法研究综述

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

一种无回溯的最长前缀匹配搜索算法

研究网络处理器中的搜索算法,提出一种基于Patricia树的无回溯搜索算法,并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz时,每秒可以执行约7 000 000次搜索操作,实现了资源消耗和性能的折中。     

基于二分法搜索hash表的快速IP路由查找算法

路由器设计中,ＩＰ地址的路由查找算法设计很重要,算法的性能将直接影响路由器的性能。本文对Ｗａｌｄｖｏｇｅｌ等人提出的二分法查找ｈａｓｈ表算法进行了改进,使路由查找效率从至多５次ｈａｓｈ表访问减少为至多３次ｈａｓｈ表访问。     

索引折半查找算法的研究与设计

当前对有序数列查找常用二分查找,但是二分查找具有一定的约束性和特殊情况下的低效性,为此研究并设计了索引折半查找算法,理论上其平均查找效率优于二分查找的平均查找效率。对比实验验证了索引折半查找算法的良好性能。     

改进二进制和声搜索算法求解多维背包问题

和声搜索（HS）是一种已广泛应用于连续优化问题的元启发式方法。针对典型的组合优化问题——多维背包问题（MKP）,提出一种改进二进制和声搜索（IBHS）算法。算法通过伯努利随机过程生成二进制群体,在候选和声生成算子中,引入动态自适应参数,通过算法参数的自适应调整来协调算法的全局搜索和局部搜索,并提出一种新的更有效的衡量商品多维加权价值密度的方法用于二进制个体修正和优化;引入精英局部搜索机制进行协同寻优,提高IBHS的收敛速度。通过求解10组不同规模的典型多维背包算例和与贪心二进制狮群优化（GBLSO）算法、改进的差分演化（MBDE）算法以及二进制修正和声（BMHS）算法的对比分析,实验结果表明,所提算法在求解MKP时有具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

WSN中改进的IPv6路由查找算法

针对无线传感器网络(WSN)中的全局单播地址,提出一种IPv6快速路由查找机制。利用布鲁姆过滤器作为存储结构,以合适的存储方法降低错误率,采用最长前缀匹配算法合理分配前缀,以减少静态随机存取存储器的数量,降低成本。实验结果表明,利用该算法可以减少每一次查找的散列探头,从而提高路由表的查找速度,改善WSN的性能。     

RFID二进制树型折半搜索防碰撞算法

为提高RFID系统中多标签读取的工作效率,分析了二进制树型搜索防碰撞算法,提出一种改进型的二进制树型折半搜索算法．通过构建哈夫曼树,使用自定义编码,采用堆栈操作确定碰撞位,用折半查找方式减少重复路径访问量,并最终确定最短路径长度．数据分析及实验结果表明,二进制树型折半搜索防碰撞算法可以明显降低搜索深度,显著提高RFID多标签读取的工作效率。     

基于前缀树的关联规则挖掘算法分析与设计

通过研究项集之间的关系,发现大项集之间存在着一种特定的关系,即k-项集一定是由一个（k-1）-项集加上一个单独的项构成的。基于这种项集关系,本文提出基于前缀树的TIUA算法,算法摆脱了传统算法多次迭代的不足,并利用挖掘出的结果,只需扫描一次数据库,就能满足各种要求,通过以空间换时间,达到提高挖掘效率的目的。     

一种改进的新二分查找算法的研究与实现

基于传统的二分查找算法,给出了有序表中任意两元素之间距离的最优表示方法,改进了low和high的取值,得到一种基于距离的新二分查找算法。该算法与传统的二分查找算法相比,判定树高度得到有效降低;随着有序表元素的增加,平均查找长度ASL显著减少,查找速度明显提升。     

基于前缀扩展的快速路由查找算法

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

基于计数机制的多状态二进制搜索防碰撞算法

针对目前二进制搜索防碰撞算法存在查询搜索次数多、数据传输量大、识别时间长等问题,提出一种基于计数机制的多状态二进制搜索防碰撞算法.经过预处理得到标签的冲突信息,在多状态二进制搜索中引入最高冲突位计数机制.仿真结果表明,与传统的二进制搜索防碰撞算法相比,该算法减少了读写器的查询搜索次数、读写器发送命令和标签每次响应命令的数据长度,以及识别读写器读写范围内标签的时间.