高级搜索

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

张斌 吴浩明

引用本文: 张斌, 吴浩明. 一种面向连接的快速多维包分类算法[J]. 电子与信息学报, 2020, 42(6): 1526-1533. 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, 2020, 42(6): 1526-1533. 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[C]. 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]

      王一宾, 裴根生, 程玉胜. 基于标记密度分类间隔面的组类属属性学习. 电子与信息学报, 2020, 42(5): 1179-1187.

    2. [2]

      赵国繁, 唐伦, 胡彦娟, 赵培培, 陈前斌. 面向可靠性的5G网络切片重构及映射算法. 电子与信息学报, 2020, 42(6): 1478-1485.

    3. [3]

      王威丽, 陈前斌, 唐伦. 虚拟网络切片中的在线异常检测算法研究. 电子与信息学报, 2020, 42(6): 1460-1467.

    4. [4]

      马彬, 王梦雪, 谢显中. 超密集异构无线网络中基于位置预测的切换算法. 电子与信息学报, 2020, 42(0): 1-9.

    5. [5]

      全英汇, 高霞, 沙明辉, 陈侠达, 李亚超, 邢孟道, 岳超良. 基于期望最大化算法的捷变频联合正交频分复用雷达高速多目标参数估计. 电子与信息学报, 2020, 42(7): 1611-1618.

    6. [6]

      谢永, 李香, 张松松, 吴黎兵. 一种可证安全的车联网无证书聚合签名改进方案. 电子与信息学报, 2020, 42(5): 1125-1131.

    7. [7]

      陈容, 陈岚, WAHLAArfan Haider. 基于公式递推法的可变计算位宽的循环冗余校验设计与实现. 电子与信息学报, 2020, 42(5): 1261-1267.

    8. [8]

      王延峰, 张桢桢, 王盼如, 孙军伟. 基于DNA链置换的两位格雷码减法器分子电路设计. 电子与信息学报, 2020, 42(0): 1-9.

    9. [9]

      袁庆军, 张勋成, 高杨, 王永娟. 轻量级分组密码PUFFIN的差分故障攻击. 电子与信息学报, 2020, 42(6): 1519-1525.

    10. [10]

      贺利芳, 吴雪霜, 张天骐. 正交多载波降噪差分混沌键控通信系统. 电子与信息学报, 2020, 41(0): 1-9.

    11. [11]

      柳娟, 谢文彬, 汪改英, 汤敏丽. 基于DNA和限制性核酸内切酶的基本逻辑门设计. 电子与信息学报, 2020, 42(6): 1332-1339.

    12. [12]

      贺利芳, 陈俊, 张天骐. 短参考多用户差分混沌移位键控通信系统性能分析. 电子与信息学报, 2020, 42(0): 1-8.

    13. [13]

      贺利芳, 吴雪霜, 张天骐. 正交多用户短参考差分混沌移位键控通信系统性能分析. 电子与信息学报, 2020, 42(0): 1-9.

    14. [14]

      唐伦, 魏延南, 谭颀, 唐睿, 陈前斌. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略. 电子与信息学报, 2020, 42(5): 1244-1252.

    15. [15]

      刘焕淋, 杜理想, 陈勇, 胡会霞. 串扰感知的空分弹性光网络频谱转换器稀疏配置和资源分配方法. 电子与信息学报, 2020, 42(7): 1718-1725.

    16. [16]

      魏宏安, 吴小清, 张昂. 基于能量误差的人体有限元模型网格剖分优化研究. 电子与信息学报, 2020, 42(0): 1-6.

    17. [17]

      王永娟, 王涛, 袁庆军, 高杨, 王相宾. 密码算法旁路立方攻击改进与应用. 电子与信息学报, 2020, 42(5): 1087-1093.

    18. [18]

      贾连印, 陈明鲜, 李孟娟, 游进国, 丁家满. 基于状态视图的高效Hilbert编码和解码算法. 电子与信息学报, 2020, 42(6): 1494-1501.

    19. [19]

      徐宇, 林郁, 杨海钢. FPGA双端口存储器映射优化算法. 电子与信息学报, 2020, 41(0): 1-8.

    20. [20]

      赵海霞, 韦永壮, 刘争红. 一种变体BISON分组密码算法及分析. 电子与信息学报, 2020, 42(7): 1796-1802.

  • 图 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下载量:  20
  • 文章访问数:  871
  • HTML全文浏览量:  269
文章相关
  • 通讯作者:  吴浩明, wuhaoming0512@126.com
  • 收稿日期:  2019-06-13
  • 录用日期:  2020-03-03
  • 网络出版日期:  2020-03-27
  • 刊出日期:  2020-06-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章