前缀基于多处理机结构的IP路由搜索技术

基于多处理机结构的IP路由搜索技术

孙艳峰,徐永安

(江苏扬州大学信息工程学院计算机系,江苏扬州225009)

摘要:随着因特网的飞速发展以及 128位地址的IPV6的出现,路由表变得日益庞大,这给IP 目标地址的查找速度提出了更高的要求。 IP地址查询使用的不是精确匹配,而是最长前缀匹配,因查询极其复杂。论文针对现有的IP查询技术的缺点和不足,提出了一种基于多处理器结构的搜索技术, 这种技术减少了查找的比较次数和存储空间。

关键词: IP地址搜索;高效路由;多处理器结构

中图分类号:TP393 文献标识码:A 文章编号: 1009-3044(2007)03- 10709-03

A Technique for IP Routing Search Based onMulti-processor

SUN Yan-feng,XU Yong-an

(Institute of Information Engineering,Yangzhou University,Yangzhou 225009,China)

Abstract:IP address lookup is a challenging problem because of increasing routing table sizes,increased traffic,and the occurrence to 128 bitIPv6 addresses The longest matching prefix requiring finding the routing entry has been difficult for the conventional solutions like hashing todeal with In this paper,A based multiprocessor organization lookup technique is proposed This approach is efficient in reducing the number ofcomp arison and storage sp ace

Key words:IP Address Search;Good Performance R outing;Multiprocessor Organization

1引言 将前缀分成16种类。 不同类以不同的存储模式存储,因此,可最

网络的普遍使用,使得网络流量剧增。 同时多媒体网络应用 多让16类IPV6地址同时进行查询。通过4位ID组将IP地址进程序和设备的使用又对网络流速提出了更高的要求。高速链路和 行分类,对每类IP地址进行的最长匹配前缀的搜索是从包含同类高速路由器则是因特网速度提高的关键。 地址的存储模式中开始的。

作为网络的灵魂,路由器将数据包从输入接口传递到输出接 3对(N+1-ary)算法的改进

根据其目的IP地址确定其应转发的输出端口号和下一跳地址。 的IP地址广播至N个处理器,同一子序列中的每一个处理器同时

索,这可通过使用多个处理器并行搜索得到。 本文描述提出一个 32前缀的排序

新的对128位IPV6地址使用SROW(Simultaneous Read and Only 在下列算法中, 以并行的方式对处理器前缀进行排序。设 S=<

搜索操作需要找到一个逐字匹配的前缀。使用基于 hash表或 排序算法的伪代码为:

二叉树搜索的传统算法只可进行精确匹配的搜索。在无类域间路 for i=1 to n do //可同时进行

收稿日期:2006- 12- 1 1

作者简介:孙艳峰( 1976- ) ,女,江苏盐城人,讲师,硕士,研究方向:网络互联,无线网络。

网络通讯与安全 本栏目责任编辑:冯蕾发送前缀的伪代码为: 且减少查询时间,就需限制IP地址前缀长度,而这可用控制前缀for每一个处理器do 扩展来将前缀集由任意长度减至预定的长度。

发送数据包的IP地址给所有的处理器, 使用有共享存储器 6性能分析

队列去模仿多处理34前缀的查询 设IP地址到达的速率为λ,处理速率为μ ,对有N个处理器

(1)如果Si>x,那么,若x在序列中,它必须在Si的前面,因此 处理速率:

(a)q:=Li- 1+1 好顺序算法和并行算法在最坏情况下的运行时间比。

710 电脑知识与技术

5 客户图端2界面学生的选内课容分展析数现据立方体拓扑结构 [2]王虹等基于OLAP与DM一体化的数据建模技术的研究OLAP提供了一组从服务器传递到客户端的工具—数据透视 [J]计算机工程与应用,2002,38