检索结果-南通市图书馆

微型机与应用 2012年第19期31卷 61-64页

作者：唐丽梅邢素霞陈天华北京工商大学计算机与信息工程学院北京100048 北京英瑞博系统技术有限公司北京100039

根据路由表前缀扩展特性,采用特殊的结构构造索引表,提出了一种基于3级索引的储存表查找方法,进行流水线方式的并行查找。引入了缓冲池的思想,提出了一种改进的路由表更新方法,同时该算法支持动态更新。与基于压缩算法相比,该算法数据... 详细信息

根据路由表前缀扩展特性,采用特殊的结构构造索引表,提出了一种基于3级索引的储存表查找方法,进行流水线方式的并行查找。引入了缓冲池的思想,提出了一种改进的路由表更新方法,同时该算法支持动态更新。与基于压缩算法相比,该算法数据结构简单;与传统TCAM路由查找相比,可以节省约40%的功耗。此外,该算法在查找性能、路由更新和存储空间方面也有很大优势,能够达到最少访问一次存储器,最多需要访问3次实现处理一个IP数据包。

关键词：路由查找前缀扩展索引表下一跳索引

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

IP路由缓存技术研究

引用

计算机研究与发展 2012年第4期49卷 710-716页

作者：朱国胜余少华徐宁华中科技大学计算机科学和技术学院武汉430074 武汉邮电科学研究院武汉430074

针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性,分析了骨干网路由表前缀重叠特征,提出了一种基于阈值的IP路由缓存方法,该方法结合了地址缓存和前缀缓存技术,无需进行前缀扩展,克服了地址缓存技术缓存空间要求过大、前... 详细信息

针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性,分析了骨干网路由表前缀重叠特征,提出了一种基于阈值的IP路由缓存方法,该方法结合了地址缓存和前缀缓存技术,无需进行前缀扩展,克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题,在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势;仿真实验表明对于路由条目超过260000的路由表,缓存空间大小为30000,选择阈值K=4时97%以上的节点可实现1:1缓存,其余节点采用地址缓存,缓存失效率小于0.02,可以用小的缓存空间实现高速线速转发.

关键词：路由查找路由缓存地址缓存前缀缓存前缀扩展阈值

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

基于Trie的高性能IP查找算法研究

基于Trie的高性能IP查找算法研究

引用

作者：闫锟湖南大学

学位级别：硕士

随着物理链路速度的增长和路由表规模的不断增大,作为路由器的一项核心技术,IP地址查找面临着巨大的性能挑战。首先,IP地址查找必须能够响应越来越多的查询请求,这些请求的数量往往超过了几百万甚至上千万条,而且还在不断增长。其次,IP... 详细信息

随着物理链路速度的增长和路由表规模的不断增大,作为路由器的一项核心技术,IP地址查找面临着巨大的性能挑战。首先,IP地址查找必须能够响应越来越多的查询请求,这些请求的数量往往超过了几百万甚至上千万条,而且还在不断增长。其次,IP地址查找还必须考虑数据结构的存储效率,此外,虚拟化路由器、软件定义网络(SDN)和命名数据网络(NDN)等新兴网络技术及未来网络架构的提出与发展也对IP地址查找提出了新的需求。本文提出了两种基于Trie的高性能IP地址查找算法。1)PEST算法。它既采用了x-level extension技术来提高IP地址查找速度,又利用了存储空间连续、占用内存小的Bitmap数组来减少内存空间的消耗,另外,prefix splitting策略使本算法能够顺利扩展应用于地址长度为128位的ipv6地址。2)NewTrie算法。它以2-multiway trie为基础,将2-multiway trie中的后代数组改进为一个位向量vector,vector中的1和0分别用来表示后代子节点为内部节点或者叶节点,通过使用指令popcnt来计算vector中1的数量和0的数量,这些值分别用来作为后代节点数组或者叶子结点数组的间接索引值。此外,叶向量leafvec的引入减少了冗余的叶子节点,节省了内存空间,s步长跳转策略使得IP地址查找能够在O(1)时间复杂度内完成。实验结果表明,与现有的IP地址查找算法相比较,本文提出的两种不同的基于Trie的算法具有较好的性能。PEST算法能够有效地提高IP地址查找速度,同时降低内存空间的开销;NewTrie算法能够进一步提高IP地址的查找速度,但需要消耗更多的内存空间,总体来看,两种算法都具有良好的可扩展性,能够适应日益更新的互联网时代。

关键词：特里树 IP地址查找前缀扩展前缀划分最长前最匹配

来源：

同方学位论文库评论