高级搜索

一种面向连接的快速多维包分类算法

张斌 吴浩明

引用本文: 张斌, 吴浩明. 一种面向连接的快速多维包分类算法[J]. 电子与信息学报, doi: 10.11999/JEIT190434 shu
Citation:  Bin ZHANG, Haoming WU. A Connection-oriented Fast Multi-dimensional Packet Classification Algorithm[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190434 shu

一种面向连接的快速多维包分类算法

    作者简介: 张斌: 男,1969年生,教授、博士生导师,研究方向为网络空间安全;
    吴浩明: 男,1995年生,硕士生,主要研究方向为网络流量检测
    通讯作者: 吴浩明,wuhaoming0512@126.com
  • 基金项目: 河南省基础与前沿技术研究计划基金(142300413201),信息工程大学新兴科研方向培育基金(2016604703),信息工程大学科研项目(2019f3303)

摘要: 为进一步提高聚合位向量(ABV)算法分类数据包的速度,该文提出一种面向连接的改进ABV(IABV)算法。该算法利用同一连接包分类查找规则相对一致的特点,建立哈希表-规则库两级优化查找结构,首先通过哈希表查找包分类规则,若未命中继续从规则库中查找。利用连接时效性特点设计哈希表冲突处理机制,根据表项最近命中时间判断是否进行覆写更新,避免规则累积导致查找时间增加;其次对ABV算法各维度进行等分处理,为各等分区间建立数组索引,从而快速缩小向量查找范围,加快查找规则库速度;最后,将规则中前缀转化为范围降低辅助查找结构复杂度,以减少内存空间占用量并加快规则查找速度。实验结果表明,将规则中前缀转化为范围后能够有效提升算法性能,相同条件下IABV算法相比ABV算法时间性能有显著提高。

English

    1. [1]

      SHEN Tong, ZHANG Dafang, XIE Gaogang, et al. Optimizing multi-dimensional packet classification for multi-core systems[J]. Journal of Computer Science and Technology, 2018, 33(5): 1056–1071. doi: 10.1007/s11390-018-1873-9

    2. [2]

      BI Xiaan, LUO Xianhao, and SUN Qi. Branch tire packet classification algorithm based on single-linkage clustering[J]. Mathematics and Computers in Simulation, 2019, 155: 78–91. doi: 10.1016/j.matcom.2017.11.003

    3. [3]

      亓亚烜, 李军. 高性能网包分类理论与算法综述[J]. 计算机学报, 2013, 36(2): 408–421. doi: 10.3724/SP.J.1016.2013.00408
      QI Yaxuan and LI Jun. Theoretical analysis and algorithm design of high-performance packet classification algorithms[J]. Chinese Journal of Computers, 2013, 36(2): 408–421. doi: 10.3724/SP.J.1016.2013.00408

    4. [4]

      陈小雨, 陆月明. 基于多维空间动态划分与RFC的包分类改进算法[J]. 网络与信息安全学报, 2018, 4(3): 35–41. doi: 10.11959/j.issn.2096-109x.2018024
      CHEN Xiaoyu and LU Yueming. Improved packet classification algorithm based on multidimensional space dynamic division and RFC[J]. Chinese Journal of Network and Information Security, 2018, 4(3): 35–41. doi: 10.11959/j.issn.2096-109x.2018024

    5. [5]

      LAKSHMAN T V and STILIADIS D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching[J]. ACM SIGCOMM Computer Communication Review, 1998, 28(14): 203–214. doi: 10.1145/285243.285283

    6. [6]

      万云凯, 嵩天, 刘苗苗, 等. 流量自适应的多维度包分类方法研究[J]. 计算机学报, 2017, 40(7): 1543–1555. doi: 10.11897/SP.J.1016.2017.01543
      WAN Yunkai, SONG Tian, LIU Miaomiao, et al. A flow adaptive multi-dimensional packet classification algorithm[J]. Chinese Journal of Computers, 2017, 40(7): 1543–1555. doi: 10.11897/SP.J.1016.2017.01543

    7. [7]

      ZHOU Shijie, QU Y R, and PRASANNA V K. Multi-core implementation of decomposition-based packet classification algorithms[J]. The Journal of Supercomputing, 2014, 69(1): 34–42. doi: 10.1007/s11227-014-1205-y

    8. [8]

      ABBASI M, TAHOURI R, and RAFIEE M. Enhancing the performance of the aggregated bit vector algorithm in network packet classification using GPU[J]. PeerJ Computer Science, 2019, 5: e185. doi: 10.7717/peerj-cs.185

    9. [9]

      BABOESCU F and VARGHESE G. Scalable packet classification[J]. IEEE/ACM Transactions on Networking, 2005, 13(1): 2–14. doi: 10.1109/TNET.2004.842232

    10. [10]

      贺亚威, 侯整风, 吴亮亮. 一种基于位向量流分类算法的改进[J]. 合肥工业大学学报: 自然科学版, 2015, 38(3): 331–335. doi: 10.3969/j.issn.1003-5060.2015.03.009
      HE Yawei, HOU Zhengfeng, and WU Liangliang. An improved flow classification algorithm based on bit vector[J]. Journal of Hefei University of Technology:Natural Science, 2015, 38(3): 331–335. doi: 10.3969/j.issn.1003-5060.2015.03.009

    11. [11]

      李林. 防火墙规则集关键技术研究[D]. [博士论文], 电子科技大学, 2009.
      LI Lin. Research on key techniques of firewall rule set[D]. [Ph.D. dissertation], University of Electronic Science and Technology of China, 2009.

    12. [12]

      CAIDA. The CAIDA UCSD anonymized internet traces 2016[EB/OL]. http://www.caida.org/data/passive/passive_2016_dataset.xml, 2016.

    13. [13]

      颜天信, 王永纲, 石江涛, 等. 区域分割包分类算法的优化实现[J]. 通信学报, 2004, 25(6): 80–88. doi: 10.3321/j.issn:1000-436X.2004.06.011
      YAN Tianxin, WANG Yonggang, SHI Jiangtao, et al. Optimized implementation of regional partition algorithm for packet classification[J]. Journal of China Institute of Communications, 2004, 25(6): 80–88. doi: 10.3321/j.issn:1000-436X.2004.06.011

    14. [14]

      TAYLOR D E and TURNER J S. ClassBench: A packet classification benchmark[J]. Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, USA, 2005: 2068–2079. doi: 10.1109/INFCOM.2005.1498483

    15. [15]

      孙鹏浩, 兰巨龙, 陆肖元, 等. 一种基于匹配域裁剪的包分类规则集压缩方法[J]. 电子与信息学报, 2017, 39(5): 1185–1192. doi: 10.11999/JEIT160740
      SUN Penghao, LAN Julong, LU Xiaoyuan, et al. Field-trimming compression model for rule set of packet classification[J]. Journal of Electronics &Information Technology, 2017, 39(5): 1185–1192. doi: 10.11999/JEIT160740

    1. [1]

      孙鹏浩, 兰巨龙, 陆肖元, 胡宇翔, 马腾. 一种基于匹配域裁剪的包分类规则集压缩方法. 电子与信息学报,

    2. [2]

      李振强, 张圣亮, 马严, 赵晓宇. 多决策树包分类算法. 电子与信息学报,

    3. [3]

      万成威, 邬江兴, 李玉峰, 兰巨龙. CAM辅助的哈希表查找性能分析. 电子与信息学报,

    4. [4]

      陈兵, 潘宇科, 丁秋林. 一种采用启发式分割点计算的包分类算法. 电子与信息学报,

    5. [5]

      胡正平, 王玲丽. 基于L1范数凸包数据描述的多观测样本分类算法. 电子与信息学报,

    6. [6]

      项世军, 杨建权. 基于约束随机分块的NMF图像哈希算法. 电子与信息学报,

    7. [7]

      付强, 丁晓青, 蒋焰. 基于多信息融合的中文手写地址字符串切分与识别. 电子与信息学报,

    8. [8]

      吕国云, 蒋冬梅, 樊养余, 赵荣椿, H.Sahli, W.Verhelst. 基于多流三音素DBN模型的音视频语音识别和音素切分. 电子与信息学报,

    9. [9]

      张战成, 王士同, 邓赵红, ChungFu-lai. 支持向量机的一种快速分类算法. 电子与信息学报,

    10. [10]

      周烨, 杨旭, 李勇, 苏厉, 金德鹏, 曾烈光. 基于分类的软件定义网络流表更新一致性方案. 电子与信息学报,

    11. [11]

      金炜, 潘英俊, 魏彪, 冯鹏. 一种基于Contourlet的无表零树图像编码算法. 电子与信息学报,

    12. [12]

      殷茗, 王文杰, 张煊宇, 姜继娇. 一种基于邻接表的最大频繁项集挖掘算法. 电子与信息学报,

    13. [13]

      陈泽华, 闫继雄, 柴晶. 基于形式概念分析的多输入多输出真值表并行约简算法. 电子与信息学报,

    14. [14]

      胡欣, 王刚, 王自成, 罗积润. 查找表联合记忆效应补偿技术的宽带自适应预失真算法. 电子与信息学报,

    15. [15]

      陈泽华, 马贺. 基于粒矩阵的多输入多输出真值表快速并行约简算法. 电子与信息学报,

    16. [16]

      胡致远, 宋晓凤, 黄天聪, 李晓娣, 周瑞芳, 徐鑫, 蒙占宇, 彭强. 四表集抄通信网络虚拟化方案及组网算法研究. 电子与信息学报,

    17. [17]

      赵夙, 张涛, 朱晓荣. 超密集分簇网络中基于预测门限滞后余量可调的切换算法. 电子与信息学报,

    18. [18]

      杨新武, 马壮, 袁顺. 基于弱分类器调整的多分类Adaboost算法. 电子与信息学报,

    19. [19]

      兰巨龙, 黄河, 邬江兴. 包交换系统中的一种DSI算法. 电子与信息学报,

    20. [20]

      胡宇翔, 兰巨龙, 邬钧霆. 多级交换中支持包保序的交换结构及调度算法. 电子与信息学报,

  • 图 1  特里树切分示例

    图 2  IABV算法流程

    图 3  BV, ABV和IABV算法内存占用量对比

    表 1  IABV算法伪代码

     输入:数据包Packet, 规则库${R_{1,2,···,N}}$
     输出:数据包匹配的规则Rule
     (1) ${\rm{Axis}}[1,2, ··· ,d]{\rm{ = Project}}({R_{1,2,···,N}})$//将所有规则$d$个维度分别投影到数轴上;
     (2) ${\rm{AxisCut}}[1,2,···,d][1,2,···,e]{\rm{ = CutDimension(Axis}}[1,2,···,d],e)$//将各维$e$等分;
     (3) FOR $m{\rm{ }} = {\rm{ }}1$ TO $d$;
     (4) FOR $n{\rm{ }} = {\rm{ }}1$ TO $e$;
     (5)   ${\rm{Array}}[m][n] = {\rm{BuildSearchStructure}}({\rm{AxisCut}}[m][n])$//对各维等分区间建立相应数据结构对其内的投影区间进行索引,并建立
          数组索引各维等分区间上的数据结构;
     (6)   ${\rm{BuildVector(Array}}[m][n],{R_{1,2,···,N}})$//根据规则库中规则对位向量以及聚合位向量进行设置;
     (7) END FOR
     (8) END FOR
     (9) ${\rm{Build(HashTable}}[1,2, ··· ,S],t[1,2, ··· ,S],\sigma ,{\rm{clk}})$//建立哈希表与时钟,对哈希表每个单元设置最近命中时间${t_j}(j = 1,2,···,S)$,设置命
       中时间差阈值$\sigma $并开启时钟${\rm{clk}}$;
     (10) WHILE PacketArrive()//接收到数据包时进行操作;
     (11)   ${\rm{Field[1,2,}}···{\rm{,}}d{\rm{] }} = {\rm{ GetField}}\left( {{\rm{Packet}}} \right)$//取出$d$个包头字段;
     (12)   $j = {\rm{Hash}}\left( {{\rm{Field[1,2,}}···{\rm{,}}d{\rm{]}}} \right)\% \left( {S + 1} \right)$//计算哈希地址;
     (13)   IF ${\rm{Field[1,2,}}···{\rm{,}}d{\rm{]}} \in {\rm{HashTable[}}j{\rm{]}}$//若哈希表中存储的规则与数据包匹配,更新命中时间并返回规则;
     (14)      ${t_j}{\rm{ = clk}}$;
     (15)      RETURN ${\rm{HashTable[}}j{\rm{]}}$;
     (16)   END IF
     (17)   FOR $i{\rm{ }} = {\rm{ }}1$ TO $d$//$d$个维度分别查找向量;
     (18)      ${\rm{Root} }[i]{\rm{ } } = {\rm{ Array} }[i]\left[\left\lceil {{ {e*{\rm{Field} }[i]} }/{ { {\rm{Range} }({\rm{Field} }[i])} } } \right\rceil \right]$//计算字段值所在的数组单元,取出子结构根结点;
     (19)      ${\rm{ABV}}[i][1,2, ··· ,\left\lceil {N/L} \right\rceil ],{\rm{BV}}[i][1,2,···,N] = {\rm{FindVector}}({\rm{Root}}[i],{\rm{Field}}[i])$//查找子结构,找到位向量与聚合位向量;
     (20)   END FOR
     (21)   $P = {\rm{ABV}}[1]\& ··· \& {\rm{ABV}}[d]$//聚合位向量按位与;
     (22)   FOR $x = 1$ TO $P.{\rm{Length}}$//对$P$中每一位执行循环;
     (23)      IF $P[x] = 1$//如果$P$中第$x$位为比特1;
     (24)            ${Q_x} = {\rm{BV}}[1][L \cdot (x - 1) + 1,L \cdot (x - 1) + 2,···,L \cdot x]\& ···\& {\rm{BV}}[d][L \cdot (x - 1) + 1,L \cdot (x - 1) + 2$,
                   $···,L \cdot x]$//取出BV中与x对应的$L$位按位与;
     (25)            IF ${Q_x}! = 0$;
     (26)             $c = {Q_x}.{\rm{FirstBitPosition}}(1)$//${Q_x}$中第1个比特1的位置;
     (27)             IF ${\rm{clk} } - {t_j} \ge \sigma $//判断规则是否写入哈希表;
     (28)               ${\rm{HashTable[}}j{\rm{]}} = {R_{L(x - 1) + c}}$;
     (29)               ${t_j} = {\rm{clk}}$;
     (30)             END IF
     (31)             RETURN ${R_{L(x - 1) + c}}$;
     (32)          END IF
     (33)        END IF
     (34)      END FOR
     (35)  RETURN ${\rm{DefaultRule}}$//返回默认规则;
     (36) END WHILE
    下载: 导出CSV

    表 2  算法预处理时间对比(ms)

    数据结构规则库规模
    10 k20 k30 k
    ACLFWIPCACLFWIPCACLFWIPC
    Trie-1BV1174125404249636991069151956985075202435430327
    ABV1192126024523137981105671960685125209298440421
    IABV1237126594556341011112061966245163209871443620
    Trie-2BV12017083251463453661911181004987126026266448
    ABV12627390261313531678281182195043129580270810
    IABV13237536265793834686221187935158131054272014
    Trie-4BV13687182235713973623801057426124120220242206
    ABV13967503243004055645711063466233123834250471
    IABV14277620246674151665761111406301127998255087
    RTreeBV106934481051432072827043799490556598106005
    ABV111735891067532732877544428491057610106186
    IABV113137931109532842920044890499659252107847
    下载: 导出CSV

    表 3  算法内存访问次数对比

    规则库Trie-1Trie-2
    最小内存访问次数最大内存访问次数平均内存访问次数最小内存访问次数最大内存访问次数平均内存访问次数
    BVABVIABVBVABVIABVBVABVIABVBVABVIABVBVABVIABVBVABVIABV
    ACL 10k787851103471466605110484651510714504535798340
    ACL 20k788353273923919152413770465153241891895149811161
    ACL 30k46485463810181014218117788313554606986990215415179
    FW 10k41305292278280145121573027526726126813010653
    FW 20k755753271225622511608621240463953260224822481592605236
    FW 30k755654720285828533045965197473954715285228523031951194
    IPC 10k4348516146586648242447529345159664465480322371
    IPC 20k735953163733735161421989434553149719727159219784
    IPC 30k706454755109210972280386203424654727107810882258365196
    规则库Trie-4RTree
    最小内存访问次数最大内存访问次数平均内存访问次数最小内存访问次数最大内存访问次数平均内存访问次数
    BVABVIABVBVABVIABVBVABVIABVBVABVIABVBVABVIABVBVABVIABV
    ACL 10k30355105543944656670362934510544414485677136
    ACL 20k3035532258758831484975630355322687688314869956
    ACL 30k242854590970978214113774323754593973977214512474
    FW 10k2425525525226212298513842526926426013511052
    FW 20k313053255224422471583596234374253270226022491595608236
    FW 30k323054713284828513023943192384254731286628543036957194
    IPC 10k2227515876376497932136839445160465665580922971
    IPC 20k283253142712723158018581414653163732732159720284
    IPC 30k283254713107210842247354192414654733109310912265372197
    下载: 导出CSV
  • 加载中
图(3)表(3)
计量
  • PDF下载量:  7
  • 文章访问数:  652
  • HTML全文浏览量:  169
文章相关
  • 通讯作者:  吴浩明, wuhaoming0512@126.com
  • 收稿日期:  2019-06-13
  • 录用日期:  2020-03-03
  • 网络出版日期:  2020-03-27
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章