论文部分内容阅读
摘要：随着因特网的飞速发展以及128位地址的IPV6的出现，路由表变得日益庞大，这给IP目标地址的查找速度提出了更高的要求。 IP地址查询使用的不是精确匹配，而是最长前缀匹配，因查询极其复杂。论文针对现有的IP查询技术的缺点和不足，提出了一种基于多处理器结构的搜索技术，这种技术减少了查找的比较次数和存储空间。
关键词： IP地址搜索；高效路由；多处理器结构
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)03-10709-03
1 引言
网络的普遍使用，使得网络流量剧增。同时多媒体网络应用程序和设备的使用又对网络流速提出了更高的要求。高速链路和高速路由器则是因特网速度提高的关键。
作为网络的灵魂，路由器将数据包从输入接口传递到输出接口，数据包的目的地址称为IP地址。一个选路表包含许多（N，R）序偶，其中N是目的網络的IP地址，R是到网络N的路径上的“下一跳”路由器的IP地址[1]。路由查找是对每个到达的IP报文根据其目的IP地址确定其应转发的输出端口号和下一跳地址。变长地址前缀的采用提高了IP地址的利用率，但在路由查找时就有可能找到多个匹配的表项，因此需要进行最长前缀匹配。
路由器一收到数据包，就将选路表中的下一跳地址与数据包中的目标地址相比较，取前缀匹配最长的那个，然后将数据包转发给前缀最长匹配输出端它的输出端口。在数据包转发过程中，IPV6地址的增加使得最长匹配前缀问题日益成为转发的瓶颈。可以想象，当选路表包含几百万IP地址时，不可能存储所有已存在的IP地址，因此IP地址搜索问题是一个复杂的选路表查询问题。提高数据包转发速度的方法之一是同时对目标地址提供多重搜索，这可通过使用多个处理器并行搜索得到。本文描述提出一个新的对128位IPV6地址使用SROW（Simultaneous Read and Only Write）的多处理器搜索技术。每一个处理器存储n/N个前缀，提出了一并使用（N+1-ary）搜索技术的高效算法。
2 已存在的一些IP查找算法
搜索操作需要找到一个逐字匹配的前缀。使用基于hash表或二叉树搜索的传统算法只可进行精确匹配的搜索。在无类域间路由（Classless Inter-Domain Routing，CIDR）[2]技术中，地址前缀长度可为不超过IPV4地址宽度的任意长度。变长地址前缀的使用使得IP地址的层次性分配成为可能。
2.1基于Trie的层次方法
这种方法最先在BSD内核中实现，最坏的情况下，该算法需要O（W）次查找，其中W为地址长度，所以，对于IPV4来说完成一次查询最多访问存储器32次，对于IPV6最多需要是128次查询存储访问。效率不够高。
2.2分布式存储结构
在选路表中，这种方式依赖前缀中的特定位以平均几组的形式进行存储[2]。例如，选路表中的位63，64，65，66（称ID位）用来将前缀分成16种类。不同类以不同的存储模式存储，因此，可最多让16类IPV6地址同时进行查询。通过4位ID组将IP地址进行分类，对每类IP地址进行的最长匹配前缀的搜索是从包含同类地址的存储模式中开始的。
3 对（N+1-ary）算法的改进
3.1多处理器结构
本文提出一个基于多处理器的路由器结构。将所有前缀集划分成平均长度的子序列，每个子序列对应一个处理器。这样，将目的IP地址广播至N个处理器，同一子序列中的每一个处理器同时搜索前缀。由于它是并行进行的，所以它减少了查询时间。
图1 基于多处理器的路由器的结构
3.2前缀的排序
在下列算法中，以并行的方式对处理器前缀进行排序。设S=，表示未排序的输入序列，其中Si为元素的位置，由比它小的数决定ri。当算法中止时，ri将包括输入序列中比Si小的元素的数目，把Si放在第（ri+1）的位置上，这样就生成了一个以升序排序的序列。
排序算法的伪代码为：
for i=1 to n do //可同时进行
for j=1 to n do
if (Sij )
then ri=ri+1
end if
end for
把Si放在第（ri+1）的位置上
end for
该算法的时间复杂度为O（n）。
3.3前缀的发送
已排好序的前缀以n/N的大小分成子序列，每个子序列发送给一个处理器。这样，每个处理器在子序列中比较其输入地址。（Pi代表第i个处理器）
发送前缀的伪代码为：
for 每一个处理器 do
send ( 子序列i, Pi )
end for
for 每一个处理器 do
send (目的地址, Pi)
end for
例如，假定有30（n=30）个前缀和6(N=6)个处理器，这30个前缀被分列成长度为5(n/N)的子序列，即每个处理器包含一个有5个前缀的子序列。
发送数据包的IP地址给所有的处理器，使用有共享存储器的PRAM模式， 那么，所有的处理器就会在一固定的时间内同时读取目标地址。因此地址可被N个处理器同时读取而仅写一次（SROW）。广播的过程仅需O（1）的时间。
3.4前缀的查询
借助于（N+1-ary）搜索的思想，每一步序列以相同的长度分成（N+1）个子序列。N个处理器在序列的两端同时搜索，Si表示在子序列两端的元素。处理器Pi将x与Si相比（x为要查询的IP地址）。
(1)如果Si>x，那么，若x在序列中，它必须在Si的前面，因此Si和所有它右边的元素不予考虑。
(2)如果Si 每一个子序列的长度以（N+1）的因素在减少，所以需要logN+1(n+1)个子序列。因此，最坏情况下算法的复杂度为O（logN+1(n+1)）。当N=1时，算法运行的时间是固定的。
由上可得到匹配算法的伪代码：
4 最优使用前缀扩展
控制前缀扩展将前缀集转换成前缀长度较少的相等的前缀集。在[3]中0或1填充前缀以增加前缀的长度，如果要增加的字符串已经在数据库中，就不增加，字符串仍在原来的位置。例如，如果扩前缀到足够长，那整个前缀搜索问题可转换为一般的队列搜索。对临界点的搜索将更容易，但这种解决方法是不理想的，对IPV6，队列将需要2128的空间。要使所需的总的存储空间最小，且减少查询时间，就需限制IP地址前缀长度，而这可用控制前缀扩展来将前缀集由任意长度减至预定的长度。
5多处理器结构的实现
假设有N个处理器，每个处理器的主频为700MHz。每一处理器存在一个通用的L1缓存，所有的处理器都同时共享它，客户端同时收到服务器创建的共用的套接字，套接字将所有的处理器都连接起来；客户机使用它的端口号和主机名绑定到服务器上，服务器将收到的数据包转发给客户机，服务器和客户机使用TCP套接字相互通信。随着处理器数目的增加，前缀比较的时间明显减少。
6 性能分析
6.1队列系统分析
由于有N个处理器，因此，需使用M/M/N队列去模仿多处理器机构。
设IP地址到达的速率为λ，处理速率为μ，对有N个处理器的多处理器结构来说，则到达的速率就为λ/N，每一台处理器的处理时间为1/μ，这样可对前缀的排序时间（Ts）和输入的IP地址的广播时间（Tb）进行测试。设前缀的数目为 n，IP地址数为m，处理器数为N。
处理速率：
6.2仿真结果
随着处理器数目的增加，系统时间和实际消耗的时间都在减少。（如图2所示）由此可知：对IPV6地址的搜索，该方案比现存的算法效率要高。
图2 并行程度对实际消耗时间和系统时间的影响
分析并行算法性能的又一个常用指标是加速度。加速度指最好顺序算法和并行算法在最坏情况下的运行时间比。
Accelerated speed=最好顺序算法的运行时间/并行算法的运行时间
表1 并行程度和加速度之间的关系
表1表明：随着并行程度的增加，加速度也在增加。
评价算法的另一指标是代价。代价（cost）是并行算法的运行时间和使用的处理器的数目的乘积，即代价=运行时间*处理器的数目。虽然多处理器结构的代价较高，但与其在搜索时间上显示出的巨大的优越性相比，还是值得的。
7 结论
基于多处理器结构的IP搜索算法的SROW，为下一代IPV6的地址搜索提供了一种最长前缀匹配的搜索技术。由于使用了前缀最优化存储的（N+1-ary）搜索方法，则要比较的前缀的数目显著减少，所以这种方法十分有效。
将每个处理器的前缀分类，可为每一个数据包的IP地址提供N个同时搜索到的最长匹配。在IPV6地址格式方面，这从根本上提高了路由器转发数据包的速率，也优化了存储在每一处理器中的前缀，并且存储前缀的容量进一步减少。另外，与现存的基于hash表的二叉树的搜索算法相比，在搜索与IPV6地址最长匹配的前缀方面，基于多处理器结构的（N+1-ary）搜索算法性能更好。
下一步还可改进算法的适应性以及扩展性，在不同的网络流量下提供不同的相适应的搜索提示函数以进一步提高算法性能。
参考文献：
[1]Douglas E.Coner.Interworking with TCP/IP VOL I:Principles,Protocols,and Architectures Fourth Editor[M].北京:电子工业出版社,2000.
[2]王振兴.等.基于二分搜索Trie的IPV4/IPV6路由快速查找算法[M].计算机工程,2005年1月.
[3]Bulter Lampson, Venkatachary Srinivasan,GeorgeVarghese IP Lookups Using Multiway and Multicolumn Search IEEE/ACM Transactions on Networking, Vol.7,No.3, June 1999.
本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。
关键词： IP地址搜索；高效路由；多处理器结构
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)03-10709-03
1 引言
网络的普遍使用，使得网络流量剧增。同时多媒体网络应用程序和设备的使用又对网络流速提出了更高的要求。高速链路和高速路由器则是因特网速度提高的关键。
作为网络的灵魂，路由器将数据包从输入接口传递到输出接口，数据包的目的地址称为IP地址。一个选路表包含许多（N，R）序偶，其中N是目的網络的IP地址，R是到网络N的路径上的“下一跳”路由器的IP地址[1]。路由查找是对每个到达的IP报文根据其目的IP地址确定其应转发的输出端口号和下一跳地址。变长地址前缀的采用提高了IP地址的利用率，但在路由查找时就有可能找到多个匹配的表项，因此需要进行最长前缀匹配。
路由器一收到数据包，就将选路表中的下一跳地址与数据包中的目标地址相比较，取前缀匹配最长的那个，然后将数据包转发给前缀最长匹配输出端它的输出端口。在数据包转发过程中，IPV6地址的增加使得最长匹配前缀问题日益成为转发的瓶颈。可以想象，当选路表包含几百万IP地址时，不可能存储所有已存在的IP地址，因此IP地址搜索问题是一个复杂的选路表查询问题。提高数据包转发速度的方法之一是同时对目标地址提供多重搜索，这可通过使用多个处理器并行搜索得到。本文描述提出一个新的对128位IPV6地址使用SROW（Simultaneous Read and Only Write）的多处理器搜索技术。每一个处理器存储n/N个前缀，提出了一并使用（N+1-ary）搜索技术的高效算法。
2 已存在的一些IP查找算法
搜索操作需要找到一个逐字匹配的前缀。使用基于hash表或二叉树搜索的传统算法只可进行精确匹配的搜索。在无类域间路由（Classless Inter-Domain Routing，CIDR）[2]技术中，地址前缀长度可为不超过IPV4地址宽度的任意长度。变长地址前缀的使用使得IP地址的层次性分配成为可能。
2.1基于Trie的层次方法
这种方法最先在BSD内核中实现，最坏的情况下，该算法需要O（W）次查找，其中W为地址长度，所以，对于IPV4来说完成一次查询最多访问存储器32次，对于IPV6最多需要是128次查询存储访问。效率不够高。
2.2分布式存储结构
在选路表中，这种方式依赖前缀中的特定位以平均几组的形式进行存储[2]。例如，选路表中的位63，64，65，66（称ID位）用来将前缀分成16种类。不同类以不同的存储模式存储，因此，可最多让16类IPV6地址同时进行查询。通过4位ID组将IP地址进行分类，对每类IP地址进行的最长匹配前缀的搜索是从包含同类地址的存储模式中开始的。
3 对（N+1-ary）算法的改进
3.1多处理器结构
本文提出一个基于多处理器的路由器结构。将所有前缀集划分成平均长度的子序列，每个子序列对应一个处理器。这样，将目的IP地址广播至N个处理器，同一子序列中的每一个处理器同时搜索前缀。由于它是并行进行的，所以它减少了查询时间。
图1 基于多处理器的路由器的结构
3.2前缀的排序
在下列算法中，以并行的方式对处理器前缀进行排序。设S=
排序算法的伪代码为：
for i=1 to n do //可同时进行
for j=1 to n do
if (Si
then ri=ri+1
end if
end for
把Si放在第（ri+1）的位置上
end for
该算法的时间复杂度为O（n）。
3.3前缀的发送
已排好序的前缀以n/N的大小分成子序列，每个子序列发送给一个处理器。这样，每个处理器在子序列中比较其输入地址。（Pi代表第i个处理器）
发送前缀的伪代码为：
for 每一个处理器 do
send ( 子序列i, Pi )
end for
for 每一个处理器 do
send (目的地址, Pi)
end for
例如，假定有30（n=30）个前缀和6(N=6)个处理器，这30个前缀被分列成长度为5(n/N)的子序列，即每个处理器包含一个有5个前缀的子序列。
发送数据包的IP地址给所有的处理器，使用有共享存储器的PRAM模式， 那么，所有的处理器就会在一固定的时间内同时读取目标地址。因此地址可被N个处理器同时读取而仅写一次（SROW）。广播的过程仅需O（1）的时间。
3.4前缀的查询
借助于（N+1-ary）搜索的思想，每一步序列以相同的长度分成（N+1）个子序列。N个处理器在序列的两端同时搜索，Si表示在子序列两端的元素。处理器Pi将x与Si相比（x为要查询的IP地址）。
(1)如果Si>x，那么，若x在序列中，它必须在Si的前面，因此Si和所有它右边的元素不予考虑。
(2)如果Si
由上可得到匹配算法的伪代码：
4 最优使用前缀扩展
控制前缀扩展将前缀集转换成前缀长度较少的相等的前缀集。在[3]中0或1填充前缀以增加前缀的长度，如果要增加的字符串已经在数据库中，就不增加，字符串仍在原来的位置。例如，如果扩前缀到足够长，那整个前缀搜索问题可转换为一般的队列搜索。对临界点的搜索将更容易，但这种解决方法是不理想的，对IPV6，队列将需要2128的空间。要使所需的总的存储空间最小，且减少查询时间，就需限制IP地址前缀长度，而这可用控制前缀扩展来将前缀集由任意长度减至预定的长度。
5多处理器结构的实现
假设有N个处理器，每个处理器的主频为700MHz。每一处理器存在一个通用的L1缓存，所有的处理器都同时共享它，客户端同时收到服务器创建的共用的套接字，套接字将所有的处理器都连接起来；客户机使用它的端口号和主机名绑定到服务器上，服务器将收到的数据包转发给客户机，服务器和客户机使用TCP套接字相互通信。随着处理器数目的增加，前缀比较的时间明显减少。
6 性能分析
6.1队列系统分析
由于有N个处理器，因此，需使用M/M/N队列去模仿多处理器机构。
设IP地址到达的速率为λ，处理速率为μ，对有N个处理器的多处理器结构来说，则到达的速率就为λ/N，每一台处理器的处理时间为1/μ，这样可对前缀的排序时间（Ts）和输入的IP地址的广播时间（Tb）进行测试。设前缀的数目为 n，IP地址数为m，处理器数为N。
处理速率：
6.2仿真结果
随着处理器数目的增加，系统时间和实际消耗的时间都在减少。（如图2所示）由此可知：对IPV6地址的搜索，该方案比现存的算法效率要高。
图2 并行程度对实际消耗时间和系统时间的影响
分析并行算法性能的又一个常用指标是加速度。加速度指最好顺序算法和并行算法在最坏情况下的运行时间比。
Accelerated speed=最好顺序算法的运行时间/并行算法的运行时间
表1 并行程度和加速度之间的关系
表1表明：随着并行程度的增加，加速度也在增加。
评价算法的另一指标是代价。代价（cost）是并行算法的运行时间和使用的处理器的数目的乘积，即代价=运行时间*处理器的数目。虽然多处理器结构的代价较高，但与其在搜索时间上显示出的巨大的优越性相比，还是值得的。
7 结论
基于多处理器结构的IP搜索算法的SROW，为下一代IPV6的地址搜索提供了一种最长前缀匹配的搜索技术。由于使用了前缀最优化存储的（N+1-ary）搜索方法，则要比较的前缀的数目显著减少，所以这种方法十分有效。
将每个处理器的前缀分类，可为每一个数据包的IP地址提供N个同时搜索到的最长匹配。在IPV6地址格式方面，这从根本上提高了路由器转发数据包的速率，也优化了存储在每一处理器中的前缀，并且存储前缀的容量进一步减少。另外，与现存的基于hash表的二叉树的搜索算法相比，在搜索与IPV6地址最长匹配的前缀方面，基于多处理器结构的（N+1-ary）搜索算法性能更好。
下一步还可改进算法的适应性以及扩展性，在不同的网络流量下提供不同的相适应的搜索提示函数以进一步提高算法性能。
参考文献：
[1]Douglas E.Coner.Interworking with TCP/IP VOL I:Principles,Protocols,and Architectures Fourth Editor[M].北京:电子工业出版社,2000.
[2]王振兴.等.基于二分搜索Trie的IPV4/IPV6路由快速查找算法[M].计算机工程,2005年1月.
[3]Bulter Lampson, Venkatachary Srinivasan,GeorgeVarghese IP Lookups Using Multiway and Multicolumn Search IEEE/ACM Transactions on Networking, Vol.7,No.3, June 1999.
本文中所涉及到的圖表、注解、公式等内容请以PDF格式阅读原文。