共查询到20条相似文献,搜索用时 31 毫秒
1.
为了提高IPv6的路由查找效率,根据IPv6路由前缀分布规律和前缀层次关系,提出了基于无冲突哈希表和多比特树的两级IPv6路由查找算法。该算法将地址前缀划分区间并按长度为32,40,48比特分别存储于3个哈希表中,剩下不足的前缀比特由多比特树存储,IPv6路由查找时在无冲突哈希表和多比特树中两级查找。实验表明,该查找算法的平均查找路径数为1.0~1.7,适用于高速的IPv6路由查找。 相似文献
2.
为了提高IPv6地址查找效率,在分析IPv6路由前缀长度分布规律的基础上,提出了基于哈希表及树位图(Tree-bitmap)的两级IPv6地址查找算法.算法将长度为16,32,48和64比特的前缀分别存储在4个Hash表中,其余前缀的前16,32和48比特利用已有的Hash表存储,剩余的不足16比特的部分前缀利用树位图存储,并将树位图的入口地址保存在Hash表中.IP地址查找时在Hash表和树位图中进行两级查找.实验表明,该查找算法的平均内存访问次数为1~2,最坏情况下为7,适用于高速IPv6地址查找. 相似文献
3.
分析了现有IPv4路由表查找算法和IPv6地址的特性以及主干网路由表的前缀分布特点,借鉴LFT哈希表结构简单、查找快速的特点,提出了以32bits为查找路由前缀起点的分段哈希表和多分支Tile树相结合的IPv6路由查找算法.该算法结构简单、查找效率高、易于更新,多数情况下只需一次内存访问就可查找到路由信息,提高了IPv6主干网路由器转发速度,以满足下一代互联网IPv6发展的需求. 相似文献
4.
为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和Bloom filter相结合的IPv6路由查找算法(BTBF)。BTBF分为B-树和Bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到Bloom filter,再利用Bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和Bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。 相似文献
5.
路由查找算法是网络路由器关键技术之一,为了提高数据查询性能,提出一种基于改进哈希编码的路由查询匹配算法。利用哈希函数压缩数据名字,采用状态转换阵列实现名称最长前缀的快速匹配,将路由节点缓存因素引入路由决策,采用仿真对比实验对算法的性能进行测试。结果表明,与其它路由查询匹配算法相比,本文算法不仅降低了数据内存开销,大幅度减少平均查询时间,而且提高了数据路由查询的效率。 相似文献
6.
根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法。根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中。不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度。 相似文献
7.
8.
9.
10.
在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。 相似文献
11.
在基于分布式哈希表构造的对等网络中,路由表的结构影响关键字的查询效率。B+树是一种有效查找的树型索引结构。考虑便于管理网络中众多的节点路由信息,提出一种基于B+树的路由结构,它通过为节点的路由信息建立索引,不仅提高了查询效率,将查找长度控制在树的高度内,而且使每个节点维护的路由信息尽可能少,减少了存储开销。 相似文献
12.
随着IPv6协议的广泛应用,传统的IPv4路由表查找算法不再适应IPv6网络环境中路由转发的需要。因而提出一种IPv6路由查找算法,利用Bloom滤波器来实现并行的最长前缀匹配,缩小查找范围,使得每次查找的平均hash探索次数有所减少.从而提高查找速度。 相似文献
13.
14.
IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空问是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化.文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前缀在不同的聚类规模上的次序统计量服从Pareto分布,主干路由表项的次序统计量也近似服从Pareto分布.该文提出了一种基于活跃度排序的路由逐次查找算法——SOSL,对IP地址查询进行了优化,在该文的模拟实验中,活跃路由表的规模、刷新周期和活跃度判定下限间存在一些对数线性关系,使得作者可以以很小的活跃路由表来实现全部路由查找需求的99%;为SOSL实现中最关键的活跃路由表排序问题提出了一个基于计数器溢出的方案,复杂度为O(1).对比发现该文的算法与TCAM结合能够提高TCAM的效率,高效地控制活跃路由表的规模,易于硬件实现. 相似文献
15.
M+树:一种新型、高效的动态哈希算法 总被引:1,自引:0,他引:1
通常哈希函数只支持等值查找,这给哈希函数的应用带来了很大的限制。该文提出了一种新型的哈希索引算法——M 树索引。该算法能够支持等值和范围查找,实验表明,该算法无论在查询效率还是可维护性方面都优于同类索引算法。 相似文献
16.
介绍了网络处理器基本特点,以及如何基于Intel IXP1200网络处理器采用微码实现路由表的路由查找功能.路由查找功能采用Intel提供的TRIE表结构,实现32位IP地址最长前缀匹配算法. 相似文献
17.
基于分布式哈希表(DHT)的结构化P2P网络具有扩展性好、健壮和自组织等优点,但只支持精确匹配的查询.本文提出一种基于分布式范围树的结构化P2P范围查询方法(DRT-RQ),该方法将多维索引的分布式范围树分发到已有的结构化DHT覆盖网络中,利用DHT系统提供的数据查找接口,有效实现数据对象的范围查询.实验结果表明,基于分布式范围树的范围查询(DRT-RQ)比基于前缀哈希树的范围查询(PHT-RQ)需要更短的查询延时. 相似文献
18.
为了弥补多字符串模式匹配效率低下的缺陷,给出了一种基于双哈希表的多模式匹配算法。这个算法通过两个相关联的哈希表对模式串进行存储,同时采用一个转移表将发生失配时的跳跃距离存储。处于匹配阶段时:如果模式串无公共前缀,那么仅仅于第一个哈希表中进行查找;如果模式串有公共前缀,那么就在两个哈希表中顺序查找。经分析发现,此算法在最短模式串长度很长的环境中尤为适用,相对于经典算法,其时间复杂度较低,且其尝试次数也比较少。最后经实验可以证明,该算法具备较好的时空性能。 相似文献
19.
哈希表由于其速度快的优点在数据查询中有着广泛的应用。本文在结合冲突解决机制和数据元素被查找的先验概率的基础上,提出了一种提高哈希表查找效率的优化方法,并对该方法在链地址法处理哈希冲突的情况下进行了理论分析,与原哈希表方法相比,该方法降低了冲突时执行查询的查找长度,从而使查询响应时间更短。最后对该方法进行行了实例验证,实验结果表明,新方法是有效并且简便的。 相似文献