路由器中的包分类算法研究

计算机科学２００６Ｖｏ１．３３Ｎｏ．１１　路由器中的包分类算法研究　）　’　甘利杰　（重庆工商大学计算机科学与信息工程学院　重庆４０００６７）　摘要在Ｉｎｔｅｒｎｅｔ路由器中将数据包分类成流采用了散列算法的基本思想，并引入了流的局部性原理来加速散列　查找的过程，用软件对该算法进行了仿真测试，并在最后从时间复杂度和空间复杂度两个方面对其进行了性能分析。　实验结果表明，该算法能够快速地实现分流。　关键词　包分类，数据包，流　Ｔｈｅ　Ｓｔｕｄｙ　ｏｆ　ａｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｐａｃｋｅｔ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｏｆ　Ｒｏｕｔｅｒ　ＧＡＮ　Ｌｉ＿．『ｉｅ　（Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｃｏｌｌｅｇｅ。Ｃｈｏｎｇｑｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ＆Ｂｕｓｉｎｅｓｓ　Ｕｎｉｖｅｒｓｉｔｙ．Ｃｈｏｎｇｑｉｎｇ　４０００６７）　Ａｂｓｔｒａｃｔ　Ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｃａｔｅｇｏｒｉｚｉｎｇ　ｐａｃｋｅｔｓ　ｉｎｔｏ“ｆｌｏｗｓ”ｉｎ　ａｎ　Ｉｎｔｅｒｎｅｔ　ｒｏｕｔｅｒ　ｉｓ　ｃａｌｌｅｄ　ｐａｃｋｅｔ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ．Ａｌｌ　ｐａｃｋｅｔｓ　ｂｅｌｏｎｇｉｎｇ　ｔＯ　ｔｈｅ　ｓａｍｅ　ｆｌｏｗ　ｏｂｅｙ　ａ　ｐｒｅ￣ｄｅｆｉｎｅｄ　ｒｕｌｅ　ａｎｄ　ａｒｅ　ｐｒｏｃｅｓｓｅｄ　ｉｎ　ａ　ｓｉｍｉｌａｒ　ｍａｎｎｅｒ　ｂｙ　ｔｈｅ　ｒｏｕｔｅｒ．Ｔｈｅ　ｍａｉｎ　ｉｄｅａ　ｉＳ　Ｈａｓｈ　ａｌｇｏｒｉｔｈｍ．ＨＯＷ　ｔＯ　ｓｐｅｅｄ　ｔｈｅ　ｈａｓｈ　ｓｅａｒｃｈ　ｗｉｔｈ　ｔｈｅ　ｌｏｃａｌｎｅｓｓ　ｏｆ　ｆｌｏｗ　ｈａｓ　ｂｅｅｎ　ｉｎｔｒｏｄｕｅｅｄ．Ａｔ　ｌａｓｔ，ｉｔｓ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ｓｐａｃｅ　ｃｏｍｐｌｅｘｉｔｙ　ｉｓ　ａｎａｌｙｚｅｄ．Ｔｈｅ　ａｎａｌｙｓｉｓ　ｓｈｏＷＳ　ｔｈａｔ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｎｉｃｅ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ｓｐａｃｅ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ｃａｎ　ａｃｈｉｅｖｅ　ｌａｓｔ　ｓｈｕｎｔ．　Ｋｅｙｗｏｒｄｓ　Ｐａｃｋｅｔ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｄａｔａ　ｐａｃｋｅｔ，Ｆｌｏｗ　１　引言　关键功能。数据包处理既存在于网络核心，也存在于接入／边　缘网络。设备在网络中的位置以及服务供应商的需求决定了　随着Ｉｎｔｅｒｎｅｔ规模的不断扩大与应用技术的不断进步，　所需要的数据包处理的类型和数量、线路速率和功能，也决定　越来越多的业务需要对数据包（Ｐａｃｋｅｔ）［卜　］进行实时、快速　了数据包处理的正确方法，以及半导体器件的选择。　的分类　在对分类算法的应用环境进行分析后，发现分类算　基于类的数据包分类算法和基于流的数据包分类算法在　法所针对的规则库可以是静态的，也可以是动态的。静态的　规则库和流表的表现形式和规模上的不同，针对它们各自的　规则库比如路由表查找中的路由表，包过滤技术中的过滤器　特点在算法的研究上有各自的侧重点　比如基于类的数据包　等；动态规则库比如基于流的应用中的流表。因此可以把数　分类算法主要解决对于类的优先级的处理，而基于流的数据　据包分类算法分为两个大的类别，它们分别是针对静态规则　包分类算法也主要解决流表的大规模和变化频繁所带来的问　库而采用的数据包分类算法和针对动态规则库采用的数据包　题。　分流算法，它们的相同点在于这两种算法都是把一个数据包　应用于高速网络业务量测量系统中的基于“类”的数据包　与已有的规则进行匹配的过程。　分类算法，用于针对网络管理员指定的规则库进行匹配分类，　数据包的结构非常复杂，主要由“目的ＩＰ地址”、“源ＩＰ　以作为统计分析的前提。　地址”、“净载数据”等部分构成。数据包处理包含数据包拆卸　和组装；数据包分类；数据包修改；业务／流量管理；队列和策　２包分类算法　略管理；安全性处理；控制和管理等功能。数据包处理是指对　基于“类”的数据包分类算法由两个部分构成：预处理部　通过数字通信和网络设备的数据包进行处理，是网络处理的　分和查找部分ｍ。算法Ｌ６］的示意图如图ｉ所示。　图１数据包分类　＊）本研究由重庆市自然科学基金支持项目（Ｎｏ，２００４ＢＢ２１８２）资助。甘利杰主要研究方向：软件工程、操作系统等。　・　５４　・　维普资讯 http://www.cqvip.com

２．１预处理　为地址从ｈａｓｈ表中取出ｄａｔａ与ｋ比较，看是否相等，如果相　等，则得到分流结果，如果不相等，采用线性探测再散列法继　续向后查找，查找到则得分流结果，否则表示它是一个新的　流，再看散列表是否满，若没有满，则直接插人，否则去掉散列　表中一个值，将这个新的值ｋ插入到散列表中　预处理部分完成对规则的预处理和对规则变化时ＢＭＴ　表的维护。　第一步：根据各个地址字段建立相应的ＢＭＴ表ＢＭＴＩ　ＢＭＴ　Ｋ。每个ＢＭＴ表的容量为２ｍ×ｎ（ｍ为该ＢＭＴ表对　应地址字段的长度，　为规则数）。各个ＢＭＴ表的存储单元　初始值为０。表示没有规则对应。　第二步：根据各规则所涉及的地址字段到各个相应的　ＢＭＴ表中进行处理。如果规则对应某个地址字段值，则到对　应的ＢＭＴ表的对应该规则的比特置“１”，表示规则和地址字　段匹配。如果规则和某个地址范围匹配，则到对应的ＢＭＴ　表的对应区域把该规则对应的比特置“１”，表示规则和这些地　址字段匹配。　第三步：当规则发生变化的时候，需要对ＢＭＴ表进行维　护：　当添加一条新规则的时候，根据该规则所对应的各个地　址字段值，到各ＢＭＴ表中的对应该规则的比特置“１”，表示　规则和地址字段匹配。　当删除一条规则的时候，根据该规则所对应的各个地址　字段值，把各ＢＭＴ表中相应该规则的比特清“０”，表示任何　一个数据包都不能和这条规则匹配。实际上就意味着这条规　则不存在了。以后还可以用一条新的规则替代这条旧规则。　当对一条规则进行修改的时候，首先根据旧规则所对应　的各个地址字段，把各ＢＭＴ表的相应该规则的比特清“０”，　表示规则不再和该地址相匹配。然后根据新规则所对应的各　个地址字段，到各ＢＭＴ表的相应新规则的比特置“１”，表示　新规则和该地址单元匹配。　２．２查找　查找算法完成对每一个输人数据包的查找。　（１）把数据包到结果缓冲区中进行查找，查找可以用线性　查找、二分查找、散列（Ｈａｓｈ）查找等一些常见的算法。如果　能匹配，则对应的结果中“１”比特对应于和该数据包匹配的规　则，否则，转（２）。　（２）根据数据包的各个地址字段的值到各个相应的ＢＭＴ　表中查找对应的表项。　（３）把各个表项的值进行“与”运算，得到结果为“１”的比　特位对应于和该数据包匹配的规则。　３包分类算法实现　Ｍａｉｎ（）函数先从数据包数据文件中找到源地址行取出　源地址，然后读取目的地址行取出目的地址，合并源地址和目　的地址得字符串ｓＬｉｎｅｔｅｍｐ，由它可以实例化一个ｈａｓｈ表项，　然后查找ｈａｓｈ表，查找不成功则在ｈａｓｈ表里插入一个新的　项，如果插人失败表示ｈａｓｈ表已满，这个时候要更新ｈａｓｈ　表，去掉其中一个项，然后将新项插人。　程序中主要函数的功能：　ｐｕｂｌｉｃ　ｃｌａｓｓ　ｈａｓｈｔａｂｌｅｅ（）；ｈａｓｈｔａｂｌｅｅ类，含有关键字　ｋｅｙ、标志ｆｌａｇ、标志ｈａｓｈ表上这个位置是否为空。　ｐｕｂｌｉｃ　ｖｏｉｄ　ｉｎｉｔ（ｒｅｆ　ｈａｓｈｔａｂｌｅｅ［］ｈｔ）；ｈａｓｈ表初始化函　数，将各个节点的标志置为空。　ｐｕｂｌｉｃ　ｂｏｏｌ　ｉｎｓｅｒｔ（ｒｅｆ　ｈａｓｈｔａｂｌｅｅ［］ｈｔ，ｈａｓｈｔａｂｌｅｅ　ｅ）；往　ｈａｓｈ表插入一个元素，成功后返回ｔｒｕｅＩ不成功返回ｆａｌｓｅ。　ｐｕｂｌｉｃ　ｉｎｔ　ｓｅａｒｃｈ（ｈａｓｈｔａｂｌｅｅ［］ｈｔ，ｓｔｒｉｎｇ　ｋ）；查找ｈａｓｈ表　ｈｔ，根据字符串即源地址和目的地址计算关键字ｋｅｙ，以ｋｅｙ　图２主程序流程图　获取　地址　‘　折叠法计算　ｌ　除留余数法计算得到Ｋ值　图３　Ｋ值计算流程图　ｐｕｂｌｉｃ　ｖｏｉｄ　ｕｐｄａｔｅｔａｂｌｅ（ｒｅｆ　ｈａｓｈｔａｂｌｅｅ［］ｈｔ，ｓｔｒｉｎｇ　ｋ）；更　新ｈａｓｈ表，去掉一个不常用的关键字，用关键字ｋ替代，查找　不成功时将用到。　、　ｐｕｂｌｉｃ　ｉｎｔ　ｄｅｌｅｔｅ（ｔｅｌ　ｈａｓｈｔａｂｌｅｅＥ￣ｈｔ）；删除一个最近不常　用的关键字。　ｐｕｂｌｉｃ　ｃｌａｓｓ　ｐａｃｋｅｔｌｉｎｅ￣存储数据包的一行。　ｐｕｂｌｉｃ　ｃｌａｓｓ　ｂｕｆｆｅｒ￣缓冲区，可以存储数据包的若干行。　ｐｕｂｌｉｃ　ｓｔａｔｉｃ　ｖｏｉｄ　ｇｅｔｎｅｘｔ，ｐｕｂｌｉｃ　ｓｔａｔｉｃ　ｉｎｔ　ｆｉｎｄｐｏｓ；用于　定位到某个数据包　４包分流算法实现　基于“流”的数据包分类算法的特点是流表的容量大，流　表的更新速度较快　Ｊｕｎ　Ｘｕ等人提出了用散列（Ｈａｓｈ）的方　法来进行处理，在硬件实现方案中，Ｊｕｎ　Ｘｕ等人设计了一个　面向第四层路由的高速缓存体系结构，它可以达到很高的命　中率（９２　），并且命中率稳定（方差０．６　），这是传统的缓存　管理算法无法达到的，ｌｕｎ　Ｘｕ等人采用了近似ＬＲＵ算法，该　算法充分运用了Ｉｎｔｅｍｅｔ的第四层流量的本地性行为。Ｊｕｎ　Ｘｕ　（下转第６３页）　・　５５　・　维普资讯 http://www.cqvip.com

在运行这段代码时，后台进行了以下的工作。　１．当初始化时，ＬｏｇｉｎＣｏｎｔｅｘｔ对象首先在ＪＡＡＳ配置文　件中找到Ｓａｍｐｌｅ文件，然后根据配置文件的内容决定该加载　哪个ＬｏｇｉｎＭｏｄｕｌｅ对象。　／ＤＲ，　）发送给服务提供者Ｐ。代码可以表示为：　ｉｆ　ＡｕｔｈＣｏｄｅ＝ｈ（ｋ，Ｉａ，Ｄ　）｛…………｝　在服务提供者Ｐ的Ｌｏｇｉｎ模块中，根据Ｊ　，随机数　和共享密钥ｋ，计算ｈ（ｋ，ＩＤｅ，　）并于代理ｐｒｏｘｙ发送过来　的值比较，实现对代理ｐｒｏｘｙ的鉴别。如果相同，则判断代理　ｐｒｏｘｙ是合法代理ｐｒｏｘｙ。代码可以表示为：　ｉｆ　ＡｕｔｈＣｏｄｅ＝ｈ（ｋ，ＩＤｖ，　Ｐ）｛…………）　２．在登录时，ＬｏｇｉｎＣｏｎｔｅｘｔ对象调用每个ＬｏｇｉｎＭｏｄｕｌｅ　对象的ｌｏｇｉｎ（）Ｔｙ法。　３．每个ｌｏｇｉｎ（）方法进行验证操作或获得一个Ｃａｌｌｂａｃｋ—　Ｈａｎｄｌｅ对象。　４．ＣａｌｌｂａｃｋＨａｎｄｌｅ对象通过使用一个或多个ＣａｌｌＢａｃｋ　方法同用户进行交互，获得用户输入。　５．向一个新的Ｓｕｂｊｅｃｔ对象中填入验证信息。　５安全性分析　本文提出了一个Ｊｉｎｉ系统中服务提供者和服务请求者的　鉴别协议，并通过双方交互建立安全连接，具有以下特点：　（１）服务提供者和服务请求者共享一对称密钥，使用带　密钥的Ｈａｓｈ函数实现了双方的双向认证。　（２）每次认证时，双方都选择不同的随机数，可以防止攻　击者的重发攻击。　（下转第７５页）　在鉴别实现中，我们在服务提供者Ｐ和可下载到本地的　代理ｐｒｏｘｙ上分别部署一个Ｌｏｇｉｎ模块。在可下载到本地的　代理ｐｒｏｘｙ上，根据ＩＤａ信息，以及随机数ｎＡ和共享密钥ｋ，　计算ｈ（ｋ，ＩＤａ，ｎＡ）并于服务提供者Ｐ发送过来的值比较，实　现对服务提供者Ｐ的鉴别。如果相同，则判断服务提供者Ｐ　是合法用户，同时生成一个随机数ｎｐ，并把，ＤＰ，　，ｈ（　，　（上接第５５页）　等人还提出一种称为动态集相关的模型，这是一种基于新型　的统计的并行散列模型。该技术可以降低散列冲突不命　中率达到７５　～９Ｏ　，使用惰性回写技术，吞吐量可以进一　步达到３７．５／７５Ｍｐｐｓ。　关键字Ｋ，散列函数可选取折叠法加除留余数法；　（２）根据散列计算的结果关键字Ｋ的值，到散列表中进　行散列查找。如果找到则得到分流的结果。如果找不到则转　（３）；　（３）如果找不到则说明这是一个新流，则为这个流建立一　４．１散列算法　散列（Ｈａｓｈ）算法的基本思想是以关键字的值为自变量，　个新的散列表项，插入到关键字Ｋ对应的同义词子表，作为　第一个节点。　通过一定的函数关系，计算出对应的函数值来，把这个值解释　为节点的存储地址，将节点存入到这个存储单元里去。查找　时再根据要查找的关键字用同样的散列函数计算地址，然后　到相应的地址单元里去取要找的节点。所以这种方法也被称　为关键字一地址转换法。用散列法存储的线性表叫做散列表。　在散列表里可以实现对节点进行快速的查找。　５算法复杂度分析　算法的执行时间由散列计算的时间（记为丁计算）和散　列查找的时间（记为Ｔ查找）组成，执行时间为Ｔ计算＋Ｔ　查找。通常情况下，计算的时间要远小于查找的时间，所以　算法的时间约等于丁查找，而散列查找的时间ＴＳ要取决于　冲突的次数。当查找的关键字是Ｎ，散列表的基本区的大小　是Ｍ的时候，散列查找的平均次数是Ｎ／２Ｍ，算法的时间复　杂度是０（Ｎ／Ｍ）。同时，算法中使用的流的局部性原理可以　加速查找过程，最好的情况下一次查找就能得到结果。　算法的占用存储空间主要是散列表的存储空间ＵＨａｓｈ。　而散列表主要用于对系统中的流进行存储。假设系统中流的　数目是Ｍ，且每个流的记录要占用Ｎ个字节，则ＵＨａｓｈ要占　用的存储空间是ＭＸ　Ｎ，算法所占用的存储空间大约是０　（Ｎ）。　散列算法由两个部分构成：散列计算和散列查找，散列计　算的计算过程应该做到两个方面：一是计算简单，二是计算应　该尽量减小散列冲突。散列计算比较常用的算法是平方法、　折叠法、除留余数法等，在本算法中，采用了折叠法加除留余　数法。即首先把流的地址字段分段，然后进行顺叠相加，最后　把相加的结果和散列表的大小进行模运算，得到散列地址。　这样处理计算简单，得到散列地址也有较好的随机性。　散列函数的选取可以减少冲突但是不能避免冲突，因此　如何解决冲突就是散列法中一个必须要解决的问题。处理散　列冲突的方法基本上有两类，一类叫做拉链法，另一类叫做开　地址法。在本算法中，采用了拉链法进行解决散列冲突。　４。２定时清除　结束语程序的运行结果根据不同的环境，结果有所不　随着时间的推移，冲突次数的增加，存储空间如果不做处　理的话将会被耗尽。另一方面，某些流已经退出使用，比如某　个ＩＰ地址已经不在进行网络使用，则在内存中保存的记录也　应该被清除，把数据记录保存到外存中，比如数据库中。释放　的存储空间可以为后面到达的新流继续使用。在数据包分类　算法中，采用了定时清除的方法，每个数据包到达之后用该数　据包的时间戳更新所属流的时间标记，以反映该流的活跃时　间，然后定时清除已经不再活跃的流。定时清除部分完成定　时对散列表中的记录进行扫描，清除已经不再活跃的流，释放　存储空间。　分流部分的流程如下：　同。影响结果的因素有，硬件环境（即仿真计算机的配置）、所　确定的散列表的容量、处理的数据包数、处理数据包的相关　性、包在散列表中的活跃时间、定时扫描的时间等。算法分析　表明算法具有良好的时间复杂度和空间复杂度，算法可以实　现快速的分流。　参考文献　１　付歌，杨明福．一个快速的二维数据包分类算法．计算机工程．　２００４，３０（６）：７６￣７８　２　Ｔｅｌｉｋｅｐａｌｌｉ久数据包处理方法和解决方案ＦＪ３．今日电子，２００２，　７：２１～２５　３　小高知宏．ＴＣＰ／ＩＰ数据包分析程序篇［Ｍ］．北京：科学出版社，　２００３　（１）根据源ＩＰ地址、目的ＩＰ地址进行散列计算，计算出　４　Ｃｏｍｅｒ　Ｄ　Ｅ，等著．用ＴＣＰ／ＩＰ进行网际互联（第二卷：设计、实现　与内核）［Ｍ］．张娟，等译．北京：电子工业出版社，２００３　５　徐士良．计算机常用算法．北京：清华大学出版社，１９９５　・　６３　・