支持快速增量更新的包分类算法研究

《支持快速增量更新的包分类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要随着Internet的迅速发展，网络服务日趋多样化，新的网络应用层出不穷。包分类技术足网络服务多样化的基础，它使得路由器能够区分地处理网络流量。随着一些实时性要求很高的新兴应用出现，服务质量(QualityofService)保证技术越来越重要，该技术通常需要频繁地更新分类规则集。然而，现有大多数包分类算法主要关心分类速度和空间需求的改进，而不太重视更新性能。更新操作过‘r复杂，有的甚至需要重建整个数据结构，更新代价昂贵。这使得这些算法不适合那些要求动态分类的新兴应用，动态分类必须在满足线速(L

2、ine．rate)的同时快速地更新规则集。因此，研究如何实现一个支持快速增量更新并且满足线速分类要求的包分类算法具有重要的实际意义。本文先分析了现有典型的包分类算法。发现递归空间分解是目前更新性能最好的二二维包分类算法，因为它具有非常好的更新局部性。并发现两阶段多维包分类笄TIC很好地利J}j了规则集特征，其第，一阶段采用RFC缩减树，第二阶段引入解释器方法。RFC是目前分类速度最快的多维包分类算法，但其缩减树不支持增量更新。TIC相比RFC极大地减少了存储消耗和预处理时间，并保持了与RFC相当的分类速

3、度，但它仍不支持增量更新。因此，本文利用递归空间分解来替换TIC第一阶段的RFC缩减树，提出了一个支持快速增量更新的两阶段多维包分类算法TICS。但是，递归空间分解生成的AQT树中存在很多空结点，AQT树路径过长导致查找性能不佳。通过两种路径压缩技术来压缩树路径，以提高查找性能。利用树结构特点，采用局部数据结构重建替换的方法，并结合对数据结构的内存管理，在多核平台上实现了共享数据结构的尊写者多读者并行无锁实时规则集增量更新，消除了更新和查找共享数据结构之间的同步开销，避免了更新导致的查找中断。实验结果表

4、明，TICS算法的更新速度比现有更新最快算法至少提升了一个数量级。路径压缩技术既减少了存储消耗，又提高了查找性能。虽然TICS算法相比TIC算法绝对分类速度差距较大，但TICS算法具有优异的并行可扩放性，可以通过提高并行度来达到线速分类要求，并且TICS的预处理时间较TIC降低了3个数帑级。TICS算法更新和查找并行同步进行时，二者的相互影响很小。当更新频率不太高时，更新对查找性能几乎没有影响。尽管全速更新，查找速度的下降也很少。关键词：包分类；增鼋更新；动态分类：并行；无锁AbstractABSTRC

5、ATWiththerapiddevelopmentofIntemet．therehascomeoutlotsofnewnetworkapplicationsasthenetworkservicesbecomemoreandmorediverse．PacketclassificationiSthefoundationofdiversifjcationofnetworkservices．Itallowstheroutertoprocessnetworktrafficdifferentially．Withth

6、eemergenceofnewnetworkapplicationsinvolvinghighreal—timedemand，theassuranceofQualityofService(QoS)ismoreandmoreimportant，whichusuallyrequiresfrequentupdatesoftheclassificationruleset．However,themostofexistingpacketclassificationalgorithmsjusthavepaidatte

7、ntiontoimprovingthesearchspeedandstoragerequirement，buthaven’tthoughtmuchoftheupdateperformance．Theupdateoperationistoocomplicated，andsomeevenneedtoreconstructthewholedatastructure．Theupdateoperationisstillveryexpensive．Thus，thesepacketclassificationalgo

8、rithmsarenotsuitablefortheemergingapplicationsthatneeddynamicclassifiation．Dynamicclassificationhastosatisfytheline—rateandfastupdatetherulesetatthesametime．Therefore，ithasimportantpracticalsignificancetoresearchhowtoimple