IPv6下路由器快速路径查找算法

IPv6下路由器快速路径查找算法 摘 要：在IPv6下由于地址长度的增加，路由器的处理负担更重，要求更高，目前很多已有的算法扩展到IPv6后无法适应新的需求。因而提出了一套IPv6 的快速路径查找机制，利用中间的Hash Table(HT32)来达到快速查找的索引。本方法可以加速路由器处理网络封包，提升网络速度。 关键词：路径查找算法；路由器；因特网通信协议第六版中图法分类号：TP393 文献标识码：A 文章编号：1001-3695(2006)10-0241-03Fast IP Lookup Algorithm for IPv6?Middle Hash TableHUA Wei?chen,HONG Mei，ZHANG Xiu?qiong(College of Computer, Sichuan University, Chengdu Sichuan 610064, China)Abstract: With the increase of the address in IPv6,the routers? burden becomes much heavier,many of the thesises using now can not apply to new requests.In this thesis, we propose a fast IP lookup scheme for IPv6. We utilize a middle hash table (HT32) to provide guidelines to achieve faster search.Key words:IP Lookup；Router；IPv6随着网络的成长以及一些新型态多媒体网络应用的出现，使得网络流量急速增加影响了整个网络的速度。要使网络速度提升，其中最重要的一个关键就是路由器的效能，因为路由器必须对每一个进来的封包根据其目的地址作最长符合前缀的查找(Longest Prefix Matching)，以决定下一个路由器位置的输出端口。这个IP查找(IP Lookup)的过程是相当复杂的，所以已经成为影响目前及下一代路由器效能的瓶颈。也使得路由器成为目前网络的瓶颈，要解决这个问题，就必须靠一套快速的路径查找机制，才能使网络的速度有所提升。下一代网络协议IPv6 虽然提供了安全性、认证等功能，但它并没有提供一套可以加速路由器处理封包的机制。因为地址长度从IPv4 的32bits变为IPv6的128bits，使得路由器在执行最长符合前置位查找过程变得更为复杂，影响路由器的效能，因此在IPv6上必须有一套快速且弹性大的IP查找机制，可以在不改变任何通信协议的情况下提升路由器的效能及网络的速度。虽然目前在IPv4 上已经有许多快速的IP 查找机制，但是大部分的方法延伸到IPv6上都有很大的问题，综合性能低且难以适应IPv6转发。IPv6上IP查找是非常重要的，本文的主要内容是在IPv6上提出一个适合硬件实现的快速IP查找机制。1 最长前缀匹配问题路由器在执行IP查找动作，其实就是最长符合前缀的处理，当一个封包进入路由器时，路由器会取出此封包的目的地址，然后依据此目的地址到路由表中去寻找相符合的输出端口，这个查表的动作就叫做IP查找或路由查找。在整个查表的过程中并不是作精确匹配查找，而是找出路由表中相符合而且是最长的前缀，这就是最长符合前置位。以表1、表2为例。如果一个封包的目的地址为10001000.x.x.x，则与此目的地址相符的只有100*/3这个前缀，所以此封包将送往端口A；若又进来一个封包，其目的地址为10010101.x.x.x，则此目的地址将符合上表的所有前缀，其中最长的为1001010*/7，所以该封包将往端口D传送。2 IPv4上IP查找方法21 线性查找这是最简单的方法,此方法一般将过滤规则按照优先级排序,并放到一个数组中。一个数据包到达后,依次与数组中的规则进行比较,直到找到合适的规则。该方法简单,并且具有低空间复杂度(因为每个规则必须而且只存放一次) ,但是这种方法不利于规则的增减,而且查找时间与规则的长度呈线性关系。线性查找可以轻易扩展到IPv6；其唯一缺点就是速度慢。对线性查找算法的改进：按前缀长度排序，更新复杂度变为O(N)。22 传统Trie架构算法将过滤规则表示成一棵树,查找时从根节点出发,依次查找树的各级枝干,直到找到合适的树叶(规则) 为止。由于规则表用树结构表示,而且规则均在树叶节点上,所以该算法容易对规则进行增减。这种算法也被称为多层树、回溯树等。 一般传统的路由器均采用Trie架构，以传统Trie架构去作查找，其内存访问的最坏情形为O(W)，W为IP地址的长度。以IPv4而言其最坏的情形为32次，IPv6则为128次，在这种架构下需要大量的内存空间。其例子如图1所示。23 Hash查找算法首先建立一个Hash 表,将每一条过滤规则放到Hash表的某一行,查询时对输入包进行Hash变换,再到相应的一行查询。这种算法基于Hash技术,所以对规则的增减比较容易。Hash函数的优点是时间复杂度为O(1)；其缺点是不能解决重入问题，一个Hash表通常只处理同一长度的前缀。Hash查找示例如图2所示。24 CAM方法CAM（Content Addressable Memory，内容寻址存储器）是能在一个时钟周期内完成关键字精确匹配的硬件，内部保存。对于输入的key，CAM同时将其与所有表项进行比较，输出与之匹配的一项NextHop。CAM方法的不足：一个CAM表只能存一个长度的前缀，IPv4需要32个CAM，N个表项；CAM很昂贵；其扩展性不好，适应不了路由表项的膨胀。25 Routing Lookups in Hardware at Memory Access Speeds方法P.Gupta等人所提出的 Routing Lookups in Hardware at Memory Access Speeds方法，主要是希望藉由硬件实现来达到快速的IP查找，达到只需一次内存访问就可以完成一次查找的动作。此方法是在路由器的设计上以速度为优先考虑因素并根据分析路由表的分布情形，可以发现有99.93%的前缀均小于等于24。因此它将IPv4的地址划分为两部分，并利用两个表TBL24及TBLLong，将前缀的前24bits完全展开存到TBL24中，再将长度大于24bits的前缀存到TBLLong中，然后在TBL24中利用一位的Flag来标志在TBLLong中是否有较长的前缀存在。查找的方式是以目的地址的前24bits当作索引，先到TBL24表中查找，再依照Flag的值来判断是否要往TBLLong作查找。当Flag为1时则取目的地址的最后8 bits到TBLLong中查找；若Flag为0则TBL24中所存的即为下一跳的输出位置。其架构如图3所示。该方法的优点是平均只要一次内存访问就可以完成一次IP查找，最坏的情形也只需要两次；缺点是需要较多的内存空间，所以若将此方法延伸到IPv6上就必须加以修改，否则记体将会过于庞大。 3 算法思想与依据由于IPv4和IPv6地址格式不同，所以在IP查找的设计上必须依照IPv6的特性加以考虑，IPv6的路由器需处理Global Unicast Address和Multicast Address这两种地址格式。由于目前IPv6的Multicast Address只使用到128bits的最后32bits，而这32bits暂时还是采用IPv4的Multicast Address格式，所以对于这种地址的查找，可以归类到IPv4的IP查找上作处理。因此在目前Multicast Address的处理上可以使用现存快速的IPv4路径查找方法来处理最长符合前缀的查找问题，而在Global Unicast Address这方面，必须对以前的一些方法加以修改，或提出一套新的路径查找机制，才能符合标准IPv6 Global Unicast Address的格式。前面分析了一些目前IPv4下IP查找的方法，我们认为在IPv6下的IP 查找不适合采用压缩的方式，因为过多的压缩会增加内存的存取次数，也会加重路由器在处理上的负担。我们参考了Routing Lookups in Hardware at Memory Access Speeds方法，并且采用了Hash的观念，对上面两种方法加以改良再加上目前IPv6的地址特性，提出了一套可以适合硬件实现的简单快速的IP查找方法。分析6Bone上前缀长度的分布情形，并参考现行IPv6 的IP分配政策，作为未来IPv6骨干网络上前缀长度分布的依据，本文也是参考此数据来设计的。图4为CERNET 6Bone骨干网络路由器连续几个月路由表前缀长度分布情形的统计数据，其中前缀长度等于32bits的前缀大约占了58.48%。从目前IPv6的地址分配政策来看，未来IPv6骨干网络前缀长度的分布情形将有50%以上是长度为32bits的前缀，这也与图中所统计出的前缀长度分布情形相符合。因此在设计上我们以第32bits为中心将IPv6 128bits的地址分为1bit31bits，33bits128bits两大部分，如图5所示。我们将128bits以第32bits为中心分为前后两部分后，再分别对每一部分影响最长符合前缀查找的位加以细分，以减少内存需求，划分方式如下：(1)区段一(1bit31bits)。因为我们所要处理的是Global Unicast Address，所以此区段前三个位为固定值“001”，并不会有最长符合前缀的问题。在区段一中只有4bits31bits会有最长符合前缀的问题存在，为了能同时兼顾内存存取次数与减少内存需求，我们将4bits31bits又分为4bits23bits、24bits31bits这两个区段，每一段地址均是相对应表的偏移量。(2)中心点(第32bits)。此中心点也是我们路径查找方法时的起始点，在该中心点会有一个前缀信息表，称为HT32(Hash Table 32)，这个表是由前缀长度等于32的前缀与其相对应的输出端口所构成的，采用哈希的方式将这些前缀存到HT32中。以第32bits为查找中心，是因为从骨干网络上前缀长度分布情形的分析中显示，有一半以上的前缀长度是落在此处的，这也代表可能会有一半以上的最长符合前缀会发生在这个地方，因此在第32bits的位置建立一个哈希表并从这个表开始查找，将可以改善整体IP查找的速度。(3)区段二(33bits128 bits)。在标准Global Unicast Address格式中4bits48bits为Global Routing Prefix，49bits64bits为Subnet ID，所以4bits64bits将与最长符合前缀查找问题有关；而65bits128bits为Interface ID，在RFC 3513中提到此字段的值具有全球唯一性，且不会有任意的长度，因此将不会有最长符合前缀查找的问题存在。依目前IPv6的规定，若有前缀长度介于65bits128bits之间则此前缀通常是属于Multicast Address，而长度落在65bits128bits之间的Global Unicast Address，其长度一定为128，这是由IPv6地址分配政策所决定的。由上述的结论，我们将区段二再分为33bits64bits，65bits128bits两部分，其中我们又将33bits64bits这个区段以48bits为中心再分为两个区段33bits48bits，49bits64bits，每一个地址均为相对应表的偏移量，由于前缀长度介于65bits128bits的前缀数量再经过扣除Multicast Address之后其数量很少，大约只占整个骨干网络路由表的1%，因此在处理上，我们将前缀长度大于64的这些前缀以哈希的方式存到HT128这个表中。综合上述的分段处理结果，我们将IPv6 128位的Global Unicats Address切割成七段，如图6所示。其中4bits23bits为相对应Table?4?23的偏移量，24bits31bits为相对应Table24?31的偏移量，33bits48bits为第一层Table33?48的偏移量，49bits64bits为第二层Table49?64的偏移量， 64bits128bits作为HT128的哈希使用，1bit32bits作为HT32的哈希使用，通过这些分段的地址来当作各表的偏移量就可以直接存取表的值，找出最长符合前缀。其中，HT32及HT128均是哈希表，所以在建表时是以哈希的方式将条目放到表中，在查找条目时也是采用同一个哈希函数。4 Middle Hash Table算法算法的整个架构如图7所示。当封包进来时，藉由封包目的地址的前三位来判断此地址是Global Unicast Address(001)还是Multicast Address(111)。该查找方法只处理开头为001 的Global Unicast Address，而暂不处理Multicast Address。路径查找方法的流程如图7所示，查找一开始会先取出目的地址的前三位判断是否为Global Unicast Address，如果是，则其详细的路经查找步骤如下：取出目的地址1bit32bits经由哈希运算(Hash32)后，到Hash Table HT32中找出相对应的条目：(1) 若此条目为NULL ?荼硎久挥腥魏纬取?32的匹配前缀，因此取出目的地址的4bits23bits，到Table?4?23找出相对应的条目。(1.1)若此条目的Flag=0?菡业?Best Matching Prefix(BMP)，结束查找。(1.2)若此条目的Flag=1?荼硎就?下可能还有更长的匹配前缀，则取出目的地址的24bits31bits，到Table24?31中找出相对应的条目，此条目所存的即为输出端口，结束查找。(2)若此条目不为NULL。(2.1)若此条目的Flag=0?菡业?BMP，此条目的Port字段所存的即为输出端口，结束查找。(2.2)若此条目的Flag=1?荼硎就?下可能还有更长的匹配前缀，取出目的地址的33bits48bits，到此条目所指的Table33?48中找出相对应的条目。 (2.2.1)若此条目的Flag=0?菡业?BMP，此条目对应的即为输出端口，结束查找。 (2.2.2)若此条目的Flag=1?荼硎就?下可能还有更长的匹配前缀，取出目的地址的49bits64bits，到 Table49?64中找出相对应的条目。(2.2.2.1)若此条目的Flag=0?菡业?BMP，此条目对应的即为输出端口，结束查找。(2.2.2.2)若此条目的Flag=1?荼硎就?下可能还有更长的匹配前缀，不过必须先记录此时的输出端口，若往下在 HT128中没有找到符合的前缀，将以此值为最后的输出端口，取出目的地址的65bits128bits经由哈希运算(Hash128)后，到HT128中找出相对应的条目。若此条目为NULL?荼硎久挥姓业饺魏纬取?65的匹配前缀，此时将以(2.2.2.2)所记录的输出端口为最后的输出端口，结束查找。若此条目不为NULL?菡业?BMP，此条目的Port字段所存的即为输出端口，结束查找。5 小结上面给出了一套很适合骨干网络环境的路由查找机制，我们根据IPv6地址的特性与前缀长度的分布情形来设计，可利用快速的SRAM 来存储Hash Table32,Hash Table128 这些内存需求较小的哈希表，然后利用DRAM来存储Table?4?23,Table24?31,Table33?48,Table49?64这些内存需求较大的表，在不需要大量内存的情况下就可以达到快速查找的目的。参考文献：1James F Kurose, Keith W RossComputer Networking:A Top?Down Approach Featuring the InternetM.Addison Wesley，2003.2R Hinden,S Deering.Internet Protocol version 6 (IPv6) SpecificationS.RFC 2460,1998.3P Gupta, S Lin,N McKeown.Routing Lookups in Hardware at Memory Access SpeedsCSan Francisco:Proc.of IEEE INFOCOM?B98,19981240?1247.4Marcel Waldvogel.Scalable High Speed IP Routing LookupsCACM SIGCOMM97,1997.25-365W Z Zhang.On the Routing Lookup Algorithm for IPv6Z，1999.6Lu?Meng B Hsu. Fast IP Lookup Scheme for Next Generation RouterDMaster Thesis, Institute of Computer Science, National Chung?Hsing University, 1999.7谭兴烈, 吴远成, 周明天,等高速访问控制表搜索算法研究J计算机应用研究，2003，20(10)：33-35