基于多維空間動(dòng)態(tài)劃分與RFC的包分類改進(jìn)算法

陳小雨，陸月明

?

基于多維空間動(dòng)態(tài)劃分與RFC的包分類改進(jìn)算法

陳小雨1,2，陸月明1,2

（1. 北京郵電大學(xué)信息與通信工程學(xué)院，北京 100876；2. 可信分布式計(jì)算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100876）

針對(duì)RFC算法隨著規(guī)則集規(guī)模的增加，占用的內(nèi)存空間以近似指數(shù)規(guī)模驟然增大的問題，提出了一種改進(jìn)型的包分類算法HRFC（Hybrid-RFC）。該算法通過決策樹完成規(guī)則集多維空間的動(dòng)態(tài)劃分，借助多階段縮減樹完成對(duì)每個(gè)子集的映射，從而實(shí)現(xiàn)包的快速高效分類。實(shí)驗(yàn)表明，該算法能夠在保障分類速度的同時(shí)，有效地降低空間開銷。

RFC；包分類；決策樹；劃分

1 引言

隨著互聯(lián)網(wǎng)架構(gòu)的不斷演進(jìn)、互聯(lián)網(wǎng)應(yīng)用的不斷涌現(xiàn)以及互聯(lián)網(wǎng)用戶的爆發(fā)式增長(zhǎng)，基于單一地址的傳統(tǒng)路由技術(shù)已經(jīng)不能滿足日益增長(zhǎng)的網(wǎng)絡(luò)業(yè)務(wù)和網(wǎng)絡(luò)安全需求。而數(shù)據(jù)分組分類能夠依據(jù)數(shù)據(jù)分組的包頭信息對(duì)網(wǎng)絡(luò)流量進(jìn)行劃分，進(jìn)而提供差異式服務(wù)，這使該技術(shù)在路由器、安全網(wǎng)關(guān)、流量控制器等各類網(wǎng)絡(luò)安全與管理設(shè)備中得到了廣泛應(yīng)用[1,2]。與此同時(shí)，隨著數(shù)據(jù)中心網(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、天地一體化網(wǎng)絡(luò)等前沿網(wǎng)絡(luò)技術(shù)的發(fā)展，高性能的數(shù)據(jù)分組分類技術(shù)也成為下一代網(wǎng)絡(luò)發(fā)展和演進(jìn)中的研究熱點(diǎn)[3,4]。

由于包分類算法的重要性和應(yīng)用的廣泛性，很多研究人員進(jìn)行了研究，也出現(xiàn)了很多的優(yōu)秀算法，如圖1所示。傳統(tǒng)的包分類一般使用線性查找，在規(guī)則數(shù)目比較少的情況下這是最佳的方法；但當(dāng)規(guī)則集規(guī)模較大時(shí)，該算法時(shí)間性能會(huì)非常差。基于三態(tài)內(nèi)容尋址存儲(chǔ)器（TCAM, ternary content addressable memory）的大規(guī)模并行查找[5]也是窮舉法的一種，該方法是目前速度最快的包分類算法，但由于是基于硬件實(shí)現(xiàn)，成本較高，并不適合大范圍的應(yīng)用；基于Trie樹分割[6~8]的算法通過規(guī)則的前綴構(gòu)建Trie樹，算法實(shí)現(xiàn)簡(jiǎn)單，但對(duì)規(guī)則維數(shù)的擴(kuò)展性差，且不支持范圍匹配；基于元組空間的二元組空間查找（TSS, tuple space search）算法[9]根據(jù)前綴長(zhǎng)度的不同，通過預(yù)計(jì)算對(duì)規(guī)則進(jìn)行分組，這種方法空間占用率小、平均性能好，但是Hash函數(shù)的使用使其性能不穩(wěn)定。基于維度分解的算法是軟件實(shí)現(xiàn)的算法中速度較快的，但是隨著規(guī)則集規(guī)模的增大，空間消耗在最差情況下會(huì)以指數(shù)的形式驟增，空間代價(jià)較高，此類別的代表算法有交叉乘積[8]、RFC[10]、ABV（aggregated bit vector）[11]等；基于幾何分割的HiCuts[12]、HyperCuts[13]等算法把規(guī)則集映射為多維空間，使用決策樹實(shí)現(xiàn)規(guī)則集的分割，通過幾何搜索完成包的分類。

目前，RFC算法是除硬件方案之外較快的多維數(shù)據(jù)分組分類算法，但該算法也存在較多缺陷。Pak[14]致力于完善RFC遞歸樹的快速構(gòu)建，Trivedi等[15]解決了RFC的增量更新問題；本文的關(guān)注點(diǎn)為RFC隨著規(guī)則集規(guī)模的增加而可能出現(xiàn)的內(nèi)存爆炸問題[10]。本文所提的算法結(jié)合多維空間的幾何區(qū)域分割與RFC算法的優(yōu)點(diǎn)，能夠達(dá)到在犧牲較小分類速度的同時(shí)，大大改善空間消耗的效果。

圖1 常見包分類算法

2 HRFC算法

對(duì)較大規(guī)模的規(guī)則集進(jìn)行處理時(shí)，RFC空間消耗十分巨大，造成這一問題的主要原因是交叉乘積表會(huì)隨著規(guī)則數(shù)的增大而以近似指數(shù)的規(guī)模增長(zhǎng)[10]。本文從這一點(diǎn)出發(fā)進(jìn)行改進(jìn)，提出了HRFC（Hybrid-RFC）算法。該算法采用化大為小的思想對(duì)規(guī)則集進(jìn)行預(yù)處理，會(huì)犧牲一定的分類速度，但能夠?qū)崿F(xiàn)對(duì)空間消耗的顯著優(yōu)化。

2.1 主要思想

HRFC算法通過決策樹[14]完成規(guī)則集的劃分，之后對(duì)每個(gè)規(guī)則子集構(gòu)建多階段縮減樹。對(duì)于決策樹的中間節(jié)點(diǎn)，本算法根據(jù)規(guī)則集的特點(diǎn)不斷對(duì)其所包含規(guī)則的某個(gè)維度進(jìn)行動(dòng)態(tài)切割，直到每個(gè)節(jié)點(diǎn)所包含的規(guī)則數(shù)目均小于閾值參數(shù)；對(duì)于決策樹的葉節(jié)點(diǎn)，構(gòu)建多階段縮減樹，完成規(guī)則子集的快速匹配。算法的整體結(jié)構(gòu)如圖2所示。當(dāng)參數(shù)大于等于原始規(guī)則集的規(guī)則總數(shù)時(shí)，HRFC會(huì)轉(zhuǎn)化為標(biāo)準(zhǔn)的RFC算法。因此，RFC可看作本算法的一種特例。

2.2 規(guī)則集的劃分

依據(jù)功能差異，用于對(duì)維規(guī)則集進(jìn)行劃分的決策樹的節(jié)點(diǎn)分為中間節(jié)點(diǎn)與葉節(jié)點(diǎn)。中間節(jié)點(diǎn)不斷對(duì)規(guī)則集進(jìn)行劃分，直至規(guī)則子集總數(shù)滿足規(guī)模要求。對(duì)于葉節(jié)點(diǎn)，主要完成其所含規(guī)則子集的多階段縮減樹的構(gòu)建。

對(duì)于任意的一個(gè)中間節(jié)點(diǎn)，包含如下屬性。

1)()：節(jié)點(diǎn)包含的規(guī)則集；特別地，樹的根節(jié)點(diǎn)包含所有的規(guī)則。

2)：被選中用于劃分規(guī)則子集的維度。規(guī)定每個(gè)維度僅能被選用一次。

中間節(jié)點(diǎn)首先需要選取用于劃分規(guī)則子集的維度，之后確定劃分點(diǎn)集合()，并依據(jù)()完成規(guī)則集的劃分，下面具體闡述。

2.2.1 維度選取

依據(jù)式(1)，定義規(guī)則集在維度上的熵H為

熵H能夠在一定程度上反應(yīng)規(guī)則子集在維度的分布情況。H越大，表明規(guī)則子集在該維度的分布越均勻；反之，表明規(guī)則子集在該維度的分布越集中。劃分的目的是盡可能地將規(guī)則集分成滿足指定規(guī)模要求的規(guī)則子集，那么規(guī)則集在某個(gè)維度分布越均勻，越容易完成劃分，從而降低決策樹的高度，減小分類的時(shí)間消耗。因此，從這一角度考慮，熵值的維度越大，越適用于規(guī)則集的劃分。

圖2 HRFC算法

2.2.2 規(guī)則集劃分

對(duì)于無(wú)法滿足參數(shù)劃分要求的連續(xù)的最小規(guī)則子集，通過合并的方式減小劃分點(diǎn)個(gè)數(shù)，即

圖3展示了以目的端口（簡(jiǎn)記為）為劃分維度，取值范圍為[,]、取值為4時(shí)的劃分結(jié)果。

2.3 多階段縮減樹的構(gòu)建

圖3 針對(duì)維度DP進(jìn)行劃分

為了減小eqID表項(xiàng)的存儲(chǔ)，可將上述過程中的一次映射轉(zhuǎn)變?yōu)槎嚯A段映射，每一個(gè)階段映射都將較大的集合映射成若干個(gè)較小的集合，并將映射結(jié)果用交叉乘積表[8]組合起來(lái)，如此反復(fù)迭代，最終完成所有的長(zhǎng)為的比特串到eqID的映射。算法在執(zhí)行過程中，由多階段映射所構(gòu)建的數(shù)據(jù)結(jié)構(gòu)稱為多階段縮減樹[10]。

圖4展示了針對(duì)表1所示的二維規(guī)則集構(gòu)建的二階段縮減樹，以及對(duì)含有二維信息<001,100>的對(duì)象與表1所示的規(guī)則集的匹配過程。

表1 二維規(guī)則集示例

2.4 查找分類過程

查找分類過程可分為確定規(guī)則子集和通過縮減樹匹配這2部分。

規(guī)則子集的確定是通過預(yù)處理部分所創(chuàng)建的決策樹完成的。首先提取待匹配的數(shù)據(jù)分組的五元組信息，然后從決策樹的根節(jié)點(diǎn)開始，逐層做決策，直到葉子節(jié)點(diǎn)為止。在葉子節(jié)點(diǎn)處，通過與之相連的多階段縮減樹完成數(shù)據(jù)分組信息到規(guī)則的映射與匹配。

圖4 構(gòu)建多階縮減樹

需要說明的是，當(dāng)規(guī)則表中有不止一條規(guī)則匹配數(shù)據(jù)分組時(shí)，可能出現(xiàn)規(guī)則沖突。對(duì)于這一問題，本算法借助最優(yōu)匹配加以解決，也可以使用最長(zhǎng)前綴匹配或其他方法，該問題非本文討論重點(diǎn)，不做過多討論。查詢算法的偽代碼如算法1所示。

算法1 HRFC的查找分類算法偽代碼

輸入 root,packet

輸出 rule

1) SA0,SA1,DA0,DA1,DP,PROT = getInfo (packet)

2) curNode = root

3) while ! curNode.isLeaf then

4) for← 0 to root.conditionLen?1

5) if curNode.getCondition(i). satisfied(packet) then

6) curNode = curNode.getChild(i)

7) Break

8) End if

9) End for

10) End while

11) index00 = curNode.rfc.phase0(SA0,SA1)

12) index01 = curNode.rfc.phase0(DA0,DA1)

13) index02 = curNode.rfc.phase0(SP,DP)

14) index10 = curNode.rfc.phase1 (index00, index01)

15) index11 = curNode.rfc.phase1 (index02, PROT)

16) index2 = curNode.rfc.phase2 (index10, index11)

17) rule = curNode.rfc.phase3(index2)

18) return rule

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)中所使用的規(guī)則集及對(duì)應(yīng)分類測(cè)試數(shù)據(jù)分組均由ClassBench[16]產(chǎn)生。ClassBench是由華盛頓大學(xué)路易斯分校的Taylor團(tuán)隊(duì)所開發(fā)的開源工具。該工具被數(shù)據(jù)分組分類研究廣泛使用，是目前較為權(quán)威的規(guī)則集產(chǎn)生與測(cè)試工具。實(shí)驗(yàn)中使用的規(guī)則集如表2所示。

表2 實(shí)驗(yàn)規(guī)則集示例

3.1 規(guī)則總數(shù)對(duì)空間消耗的影響

分析圖5可知，在規(guī)則數(shù)較小時(shí)（如1 000、2 000、3 000），HRFC的空間優(yōu)化效果并不明顯，空間消耗量與RFC算法相差無(wú)幾。而在規(guī)則數(shù)較大時(shí)（如7 000、8 000），HRFC的空間開銷要明顯優(yōu)于RFC。隨著規(guī)則總數(shù)的增加，RFC的空間消耗會(huì)發(fā)生驟增，而HRFC通過規(guī)則集的劃分，有效地改善了這一問題，且規(guī)則總數(shù)越大，改善效果越明顯。

圖5 HRFC與RFC的空間消耗比較

3.2 規(guī)則總數(shù)對(duì)分類時(shí)間的影響

在3.1節(jié)實(shí)驗(yàn)所構(gòu)建結(jié)構(gòu)的基礎(chǔ)之上，本節(jié)進(jìn)一步測(cè)試了2種算法的分類時(shí)間。每種規(guī)則集各進(jìn)行100次分類測(cè)試，結(jié)果如圖6所示。

HRFC的分類速度要略慢于RFC，這主要是由決策樹的決策判斷所造成的。此外，HRFC的分類速度波動(dòng)性稍大，這是由于分類速度與被匹配規(guī)則在決策樹中的位置有關(guān)；被匹配規(guī)則所在節(jié)點(diǎn)的深度越低，分類速度越快，而被匹配規(guī)則的深度是不定的，這造成了HRFC分類速度的波動(dòng)，但總體來(lái)說，HRFC分類速度曲線的趨勢(shì)與RFC類似，并未隨著規(guī)則總數(shù)的增加而驟增。

圖6 HRFC與RFC的分類時(shí)間比較

3.3 閾值th對(duì)空間消耗及分類時(shí)間的影響

圖7 閾值th對(duì)HRFC空間消耗的影響（規(guī)則總數(shù)為5 000條）

圖8 閾值th對(duì)HRFC分類時(shí)間的影響（規(guī)則總數(shù)為5 000條）

4 結(jié)束語(yǔ)

針對(duì)RFC算法在結(jié)構(gòu)構(gòu)建時(shí)空間開銷大的缺陷，本文提出了一種改進(jìn)型算法HRFC。該算法將規(guī)則集看作是多維空間，借助于決策樹對(duì)規(guī)則集進(jìn)行切分，而后對(duì)每個(gè)子集進(jìn)行縮減樹的構(gòu)建。該算法犧牲了一定的包分類速度，卻能夠有效地降低結(jié)構(gòu)構(gòu)建階段的空間開銷。此外，本文也就規(guī)則集劃分參數(shù)對(duì)性能的影響進(jìn)行了探討。

[1] 林闖, 單志廣, 任豐原. 計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量[M].北京：清華大學(xué)出版社, 2004.

LIN C, SHAN Z G, REN F Y. Service quality of computer netwoek[M]. Beijing: Tsinghua University Press, 2004.

[2] JOSEPH D A, TAVAKOLI A, STOICA I. A policy-aware switching layer for data centers[C]//ACM SIGCOMM 2008 Conference on Data Communication. 2008: 51-62.

[3] 萬(wàn)云凱, 嵩天, 劉苗苗, 等. 流量自適應(yīng)的多維度包分類方法研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2017, 40(7): 543-1555.

WANG Y K, SONG T, LIU M M, et al. Study on multidimensional packet classification method of Flow self-adaptation[J]. Chinese Journal of Computers, 2017, 40(7): 1543-1555.

[4] 肖瑋, 陳性元, 包義保, 等. 基于多級(jí)關(guān)聯(lián)信號(hào)樹的高效可重構(gòu)網(wǎng)包分類方法研究[J]. 高技術(shù)通訊, 2014, 24(9):928-934.

XIAO W, CHEN X Y, BAO Y B, et al. The efficient econfigurable network packet classification method based on multilevel correlation signal tree[J]. Chinese High Technology Letters, 2014, 24(9): 928-934.

[5] ZANE F, NARLIKAR G, BASU A. Coolcams: power-efficient TCAMs for forwarding engines[C]//Joint Conference of the IEEE Computer and Communications. 2003:42-52.

[6] KNUTH D. Fundamental algorithms: sorting and searching[DB/OL]. https://www.researchgate.net/publication/243573812_ Fundamental_algorithms_vol_3_sorting_and_searching.

[7] TSUCHIYA P F. A search algorithm for table entries with non- contiguous wildcarding[DB/OL]. https://www.researchgate.net/publication/2804328_A_Search_Algorithm_for_Table_Entries_with_Non-contiguous_Wildcarding.

[8] SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable layer four switching[C]//ACM Sigcomm'98 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. 1998:191-202.

[9] SRINIVASAN V, SURI S, VARGHESE G. Packet classification using tuple space search[J]. Sigcomm Computer Communication Review, 1999, 29(4):135-146.

[10] GUPTA P, MCKEOWN N. Packet classification on multiple fields[J]. Sigcomm Computer Communication Review, 1999, 29(4): 147-160.

[11] LAKSHMAN T V, STILIADIS D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching[DB/OL]// https://www.researchgate.net/publication/2505564_High- Speed_Policy- based_Packet_Forwarding_Using_Efficient_Multi-dimensional_Range_Matching.

[12] GUPTA P, MCKEOWN N. Classifying packets with hierarchical intelligent cuttings[EB/OL]. https://www.researchgate.net/publication/ 3215123_Classifying_packets_with_hierarchical_intelligent_cuttings.

[13] SINGH S, BABOESCU F, VARGHESE G, et al. Packet classification using multidimensional cutting[C]//Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. 2003: 213-224.

[14] PAK W, BAHK S. FRFC: fast table building algorithm for recursive flow classification[J]. IEEE Communications Letters, 2010, 14(12):1182-1184.

[15] TRIVEDI U, JANGIR M L. An optimized RFC algorithm with incremental update[C]//The International Conference on Advances in Computing, Communications and Informatics. 2014:120-127.

[16] TAYLOR D E. ClassBench: a packet classification benchmark[J]. IEEE//ACM Transactions on Networking, 2007, 15(3): 499-511.

Improved packet classification algorithm based onmultidimensional space dynamic division and RFC

CHEN Xiaoyu1,2, LU Yueming1,2

1. School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China 2. Key Laboratory of Trustworthy Distributed Computing and Service, Ministry of Education, Beijing 100876, China

According to the existing problem that memory usage grows exponentially with the size increase of rule set in RFC (recursive flow classification) algorithm, an improved packet classification algorithm, HRFC (Hybrid-RFC) was put forward. The new algorithm completes the dynamic division of a multidimensional space rule set by a decision tree, accomplishes the mapping of each subset with multiple phase reduction trees, so as to realize fast and efficient packet classification. The simulation results show that the new algorithm can reduce the space usage effectively while guaranteeing the performance of classification speed.

RFC, packet classification, decision tree, division

TP393.08

A

10.11959/j.issn.2096-109x.2018024

2018-01-03；

2018-02-15

陳小雨，chenxiaoyu12345@126.com

國(guó)家重點(diǎn)研究計(jì)劃基金資助項(xiàng)目（No.2016YFB0800302）

The National Key R&D Program of China (No.2016YFB0800302)

陳小雨（1993-），男，北京人，北京郵電大學(xué)碩士生，主要研究方向?yàn)榉植际接?jì)算與信息安全。

陸月明（1969-），男，江蘇蘇州人，北京郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榉植际接?jì)算、信息安全。