多维IP包分类算法研究

钟平峰

钟平峰

（重庆重邮信科通信技术有限公司，重庆400065）

摘要：IP包分类算法是应用在路由器数据平面的核心算法，其中一维的IP包分类算法就是路由地址查找算法，为路由器的基本转发功能提供支持，与此对应的多维的IP包分类算法是为支持第4层交换的路由器提供对IP数据报的分类，使路由器能对每一个特定的数据报作出预先定义好的处理，以便为了新的网络应用提供数据包过滤、防火墙、基于策略的路由、区分服务、QoS、流量计费等功能。本文介绍了两种典型的多维IP包分类算法在国内外研究现状及综述研究。

关键词：IP包分类算法；多维

中图分类号：TP393文献标识码：A文章编号：1007-9599(2010)05-0000-02

ClassificationAlgorithmStudyofMulti-dimensionalIPPacket

ZhongPingfeng

(ChongqingCYITCommunicationTechnologyCo.,Ltd,Chongqing400065,China)

Abstract:IPpacketclassificationalgorithmisappliedintherouterdataplaneofthecorealgorithm,one-dimensionalIPpacketclassificationalgorithmistheroutingaddresslookupalgorithm,thebasicforwardingfortheroutertoprovidesupportandthecorrespondingmulti-dimensionalIPpacketclassificationalgorithmisInsupportofLayer4switchingroutersprovideIPpacketclassification,sotheroutertoeachpackettoaparticularpre-definedprocessingtoapplicationsfornewnetworkpacketfiltering,firewall,policy-basedrouting,differentiatedservice,QoS,flowmeterfeesfunction.Thisarticledescribestwotypicalmulti-dimensionalIPpacketclassificationalgorithmandtheReviewofresearchstatus.

Keywords:IPpacketclassificationalgorithm;Multidimensional

一、问题定义

IP包分类算法本质上是一种检索算法，它用来提供RFC1812中对路由器功能要求的支持。RFC1812中对路由器的功能要求定义为，一：路由器必须支持IP数据报的转发操作即决定IP数据报从路由器哪一个端口转发出去；二：路由器必须支持IP数据报的交换即将IP数据报放在路由器的合适的接口上；三：可选操作－对到来的数据报作特殊处理。IP包分类算法正是对功能一和功能三提供支持的算法。一维的IP包分类算法提供功能一，多维IP包分类算法提供功能三。

（一）IP分类问题的解决方法的思想

从数学上看，IP分类问题与计算几何中的一些问题很相似。在计算几何中有一个多维空间的点定位问题（[1]）：给定多维空间中的一些互不相交的区域，找出包含指定点的区域。

一般说来，IP分类问题比多维空间的点定位问题复杂。假定不同区域互不相交时，对N条过滤规则和K(K>3)的情形，计算几何的结果给出的最好结果是：在空间复杂度为O(NK)时，时间复杂度为O(logN)；或者是在空间复杂度为O(N)时，时间复杂度为O(logKN)。也就是说，对100条过滤规则，每条规则4个域的情况，空间大概为100MB，时间大约是访存350次。这种效率显然是不可接受的。

但是数据流的分布和特定数据库中过滤规则的分布都有一定的规律性，或者说有内在的结构。所以很多好的IP分类问题的解决方案都是考察到它们分布的某一点规律性提出的。

此外，二维的IP分类问题（即针对目的IP-源IP对的分类）相对简单，而且二维的IP分类在Multicast和VPN中都有广泛的应用（[2]），具有实际的意义，因此对二维的IP分类问题的研究较成熟，有一些优秀的算法作为基础。所以，IP分类问题的解决的一个重要的思想，就是降维，将高维问题转化为二维乃至一维的问题。在下一部分中，我们将介绍IP分类问题的几个典型的算法，这些算法很清楚地体现了这些思想。

本节将介绍几种有代表性的算法。

二、GridofTries算法

（一）二维GridofTries算法

GridofTries（[4]）主要是针对二维情况下的IP分类问题提出的有效的解决方案。实际中，这种目的－源过滤规则在VPN和多播转发中有着广泛的应用。如果将数据结构中的Trie树（[5]）从一维扩展到二维，就形成GridofTries树。以表4.1中的数据库为例来说明这个扩展过程。先不考虑过滤规则数据库中源IP地址，根据过滤规则数据库中目的地址前缀构造一棵Trie树（称为Dest-Trie树）。这个目的前缀Trie树中每个节点，如果在数据库中存在其对应的目的地址前缀，则会指向一棵源地址Trie树（称为Src-Trie树），否则相应的指针为空。GridofTries算法在查找过程中是分成两步的，第一步是通过对目的IP地址做最长匹配前缀，然后再通过查找对应的源地址Trie树得到代价最小的过滤规则。这意味着，任意一个Dest-Trie树中的节点不但包含过滤规则数据库中与该节点对应的源地址前缀，还应当包含该目的前缀的“前缀”（即它在Dest-Trie树中的祖先）所有的源地址前缀。

以上方法建立的GridofTries树是Trie树的简单扩展，其时间复杂度为O(W)，但是很明显，在内存方面，它存在着极大的浪费，每个Dest-Trie节点不但存储它自身的源地址前缀，还存储其祖先的源地址前缀。在最坏情况下，其空间复杂度可达到Θ()（[6]）。一种改进的办法就是去掉这些多余的拷贝。每个目的地址前缀只包含在过滤规则数据库中与该目的地址配对的源地址前缀。由此我们得到一种改进的GridofTries树。当去掉冗余拷贝之后，查找一个目的－源地址对对应的最小代价的classID，不仅要从目的地址的最长匹配前缀所指向的Src-Trie树中进行搜索，还必须对该目的地址的最长匹配前缀的祖先所指向的Src-Trie树中进行搜索，从搜索所经过的路径中找出代价最小的过滤规则的classID。这使得时间复杂度上升到O()。一个巧妙的解决方法是引入转向指针，即通过预处理将Src-Trie树中的空指针指向其Dst-Trie树的某个祖先对应的Src-Trie中的节点，使得在查找过程中沿着最长匹配路径能够尽可能的前进。此外，为了确保算法的正确性，还必须保证目的－源IP前缀对中前缀长的节点，对应的代价也小（即IP前缀匹配越精确代价越小），这些都是通过预处理完成的。对一个包，查找最小代价过滤规则的过程如下：先对目的地址做最长前缀匹配，然后沿着目的地址最长匹配前缀所指向的Src-Trie根据包头的源地址沿着0、1指针尽可能的前进，直到无法继续前进为止，沿途经过的结点中存储的过滤规则代价最小的过滤规则所对应的classID，即是其分类的classID。此时算法的时间复杂度为O(W)，空间复杂度为O(NW)。

（二）多维的GridofTries

由于传输层协议仅限于几个值，因此可以假定所有过滤规则的协议只取三个值TCP、UDP和通配符(“*”)，对取值为通配符的过滤规则，改写过滤规则。将一条规则重复3次，分别对应TCP、UDP和所有其它情况（记为OTHER）。这样经过处理的过滤规则数据库只包含TCP、UDP和OTHER三个值。根据目的端口和源端口不同组合，建立4个哈希表，分别对应（目的端口，源端口）二元组为（DstPort,*），（DstPort,SrcPort），（*,SrcPort），（*,*）。其中通配符表示端口可取任何值。每个哈希表项，都是一颗上述的GridofTries树，哈希表的索引都是相应的端口地址和协议号的某种组合（或者函数）。查找一个包的时候，同时查找4个哈希表。分别用协议号和端口地址的某种组合作为索引，找到相应的GridofTries树，然后再根据上述查找方法找到每棵GridofTries树的最小代价的过滤规则，这个结果也是该哈希表中的最好结果。取多个结果中的代价最小者的classID，则为最终的结果。

三、Modular算法

Modular算法([7])假定与每个过滤规则Fi相联系有一个权值Wi。在知道了Wi的情况下，Modular算法试图建立更加有效的查找数据结构。

Modular算法的数据结构

从较高层面上讲，Modular算法将查找空间分为三个层次。

（一）跳转表——所有过滤规则依据规则位串中的某些位划分为不同的组，该位串通常是过滤规则不同域的前缀，其选择通常也是根据统计特性作出；

（二）查找树（一）中分成的各组的过滤规则组成一棵2m叉查找树。通过每次检查过滤规则中的m位，将其分为2m组。这m位是从当前规则位串中尚未检查的各位中选择。其选择通常遵循两个原则：减少重复拷贝和2m棵子树的平衡，算法中还同时考虑根据权值通过加权来进一步改善查找树的性能。建立查找树的过程实际上就是一个不断分组的过程，分组中止于叶子节点，也就是下面的filterbucket；

（三）Filterbucket——当剩下的过滤规则数目小于某个给定的值，则不再做进一步的划分，该节点即为叶子节点。由于叶子节点中的过滤规则数目比较少，因此可以采用与（二）中利用查找树查找不同的查找方法。叶子节点是不同查找方法的分界点。

Modular算法的查找

查找过程如下。整个包头中的全部域视为一个比特串，称为包头位串。首先以包头位串中的特定位为索引查跳转表，得到查找树的入口地址；然后，沿着查找树，每次根据包头位串中m位的值不断“下降”，直到到达叶子节点。然后在叶子节点中，查找最小代价的过滤规则。Filterbucket是最终存储过滤规则的地方，对filterbucket中过滤规则的查找，可以有不同的方法，如可以用硬件流水线来进行线性查找。Modular的时间复杂性和空间复杂性比较复杂。在极坏的情况下时间和空间都可能达到无穷（不收敛）。设filterbucket的最大容量为V，一棵树根对应的过滤规则数目为M，粗略的估算结果是时间复杂度为O(log(M/V)+V)（其中=_hkMN2），空间复杂度约为((1+2/)−2_hk)ONV。如果过滤规则中有大量的通配符存在，则时间复杂度和空间复杂度会大得多，甚至会达到无穷。从上式也可看出，V对时间和空间都有直接的影响。V越大，空间消耗得越少，但是时间消耗得越多。所以在时间和空间的tradeoff是存在的。

参考文献：

[1]G.Eason,B.Noble,andI.N.Sneddon,“OncertainintegralsofLipschitz-HankeltypeinvolvingproductsofBesselfunctions,”Phil.Trans.Roy.Soc.London,vol.A247,pp.529–551,April1955.

[2]J.ClerkMaxwell,ATreatiseonElectricityandMagnetism,3rded.,vol.2.Oxford:Clarendon,1892,pp.68–73.

[3]I.S.JacobsandC.P.Bean,“Fineparticles,thinfilmsandexchangeanisotropy,”inMagnetism,vol.III,G.T.RadoandH.Suhl,Eds.NewYork:Academic,1963,pp.271–350.

[4]K.Elissa,“Titleofpaperifknown,”unpublished.