一種面向連接的快速多維包分類算法

張斌; 吳浩明

doi:10.11999/JEIT190434

一種面向連接的快速多維包分類算法

doi: 10.11999/JEIT190434 cstr: 32379.14.JEIT190434

張斌,
吳浩明^,

1.
中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001
2.
河南省信息安全重點(diǎn)實(shí)驗(yàn)室鄭州 450001

基金項(xiàng)目: 河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃基金(142300413201)，信息工程大學(xué)新興科研方向培育基金(2016604703)，信息工程大學(xué)科研項(xiàng)目(2019f3303)

詳細(xì)信息

作者簡介:
張斌：男，1969年生，教授、博士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)空間安全

吳浩明：男，1995年生，碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)流量檢測

通訊作者:
吳浩明　wuhaoming0512@126.com

中圖分類號: TN919; TP391
計(jì)量
- 文章訪問數(shù): 2601
- HTML全文瀏覽量: 1082
- PDF下載量: 59
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-06-13
- 修回日期: 2020-03-03
- 網(wǎng)絡(luò)出版日期: 2020-03-27
- 刊出日期: 2020-06-22

A Connection-oriented Fast Multi-dimensional Packet Classification Algorithm

Bin ZHANG,
Haoming WU^,

1.
PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China
2.
Henan Key Laboratory of Information Security, Zhengzhou 450001, China

Funds: The Foundation and Frontier Technology Research Project of Henan Province (142300413201), The New Research Direction Cultivation Fund of Information Engineering University (2016604703), The Research Project of Information Engineering University (2019f3303)

摘要

摘要:
為進(jìn)一步提高聚合位向量(ABV)算法分類數(shù)據(jù)包的速度，該文提出一種面向連接的改進(jìn)ABV(IABV)算法。該算法利用同一連接包分類查找規(guī)則相對一致的特點(diǎn)，建立哈希表-規(guī)則庫兩級優(yōu)化查找結(jié)構(gòu)，首先通過哈希表查找包分類規(guī)則，若未命中繼續(xù)從規(guī)則庫中查找。利用連接時效性特點(diǎn)設(shè)計(jì)哈希表沖突處理機(jī)制，根據(jù)表項(xiàng)最近命中時間判斷是否進(jìn)行覆寫更新，避免規(guī)則累積導(dǎo)致查找時間增加；其次對ABV算法各維度進(jìn)行等分處理，為各等分區(qū)間建立數(shù)組索引，從而快速縮小向量查找范圍，加快查找規(guī)則庫速度；最后，將規(guī)則中前綴轉(zhuǎn)化為范圍降低輔助查找結(jié)構(gòu)復(fù)雜度，以減少內(nèi)存空間占用量并加快規(guī)則查找速度。實(shí)驗(yàn)結(jié)果表明，將規(guī)則中前綴轉(zhuǎn)化為范圍后能夠有效提升算法性能，相同條件下IABV算法相比ABV算法時間性能有顯著提高。
- 包分類 /
- 聚合位向量算法 /
- 哈希表 /
- 維度切分
Abstract:
In order to increase the classification speed of Aggregated Bit Vector (ABV) algorithm, an Improved Aggregated Bit Vector (IABV) algorithm is proposed, which is connection-oriented. Based on the characteristic that the packets which belong to the same connection have similar classification results, IABV establishes a Hash table-rule set two-level searching structure. It first searches in the Hash table to check the packet classification rule and then finds the matching rule in the rule set when the Hash table lookup fails. To avoid the accumulation of rules in the table, a collision handling mechanism is proposed. It judges whether to overwrite the Hash table entry which is collision according to the last hit time of the entry; Secondly, for the purpose of accelerate rule set searching, IABV divides each dimension into multiple intervals equally and employs array to index these intervals; Finally, the prefix in the rule is converted into range to reduce the complexity of the search structure, so that the time and memory consumption of the algorithm can be decreased. The experiment result shows that the performance of the algorithm can be improved by converting prefix into range and the time performance of IABV algorithm is significantly improved compared with the ABV algorithm under the same conditions.
- Packet classification /
- Aggregated Bit Vector (ABV) algorithm /
- Hash table /
- Dimension cutting

HTML全文

圖 1 特里樹切分示例

下載: 全尺寸圖片幻燈片

圖 2 IABV算法流程

下載: 全尺寸圖片幻燈片

圖 3 BV, ABV和IABV算法內(nèi)存占用量對比

下載: 全尺寸圖片幻燈片

表 1 IABV算法偽代碼

輸入：數(shù)據(jù)包Packet, 規(guī)則庫${R_{1,2,···,N}}$
輸出：數(shù)據(jù)包匹配的規(guī)則Rule
(1)　${\rm{Axis}}[1,2, ··· ,d]{\rm{ = Project}}({R_{1,2,···,N}})$//將所有規(guī)則$d$個維度分別投影到數(shù)軸上;
(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])$//對各維等分區(qū)間建立相應(yīng)數(shù)據(jù)結(jié)構(gòu)對其內(nèi)的投影區(qū)間進(jìn)行索引，并建立數(shù)組索　　引各維等分區(qū)間上的數(shù)據(jù)結(jié)構(gòu);
(6) ${\rm{BuildVector(Array}}[m][n],{R_{1,2,···,N}})$//根據(jù)規(guī)則庫中規(guī)則對位向量以及聚合位向量進(jìn)行設(shè)置;
(7) 　END FOR
(8) END FOR
(9) ${\rm{Build(HashTable}}[1,2, ··· ,S],t[1,2, ··· ,S],\sigma ,{\rm{clk}})$//建立哈希表與時鐘，對哈希表每個單元設(shè)置最近命中時間${t_j}(j = 1,2,···,S)$，設(shè)置命　　中時間差閾值$\sigma $并開啟時鐘${\rm{clk}}$;
(10) WHILE PacketArrive()//接收到數(shù)據(jù)包時進(jìn)行操作;
(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)$//計(jì)算哈希地址;
(13)　　　IF ${\rm{Field[1,2,}}···{\rm{,}}d{\rm{]}} \in {\rm{HashTable[}}j{\rm{]}}$//若哈希表中存儲的規(guī)則與數(shù)據(jù)包匹配，更新命中時間并返回規(guī)則;
(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]$//計(jì)算字段值所在的數(shù)組單元，取出子結(jié)構(gòu)根結(jié)點(diǎn);
(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])$//查找子結(jié)構(gòu)，找到位向量與聚合位向量;
(20)　　　END FOR
(21)　　　$P = {\rm{ABV}}[1]\& ··· \& {\rm{ABV}}[d]$//聚合位向量按位與;
(22)　　　FOR $x = 1$ TO $P.{\rm{Length}}$//對$P$中每一位執(zhí)行循環(huán);
(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對應(yīng)的$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 $//判斷規(guī)則是否寫入哈希表;
(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}}$//返回默認(rèn)規(guī)則;
(36) END WHILE

下載: 導(dǎo)出CSV

表 2 算法預(yù)處理時間對比(ms)

數(shù)據(jù)結(jié)構(gòu)		規(guī)則庫規(guī)模
		10 k			20 k			30 k
		ACL	FW	IPC	ACL	FW	IPC	ACL	FW	IPC
Trie-1	BV	1174	12540	42496	3699	106915	195698	5075	202435	430327
	ABV	1192	12602	45231	3798	110567	196068	5125	209298	440421
	IABV	1237	12659	45563	4101	111206	196624	5163	209871	443620
Trie-2	BV	1201	7083	25146	3453	66191	118100	4987	126026	266448
	ABV	1262	7390	26131	3531	67828	118219	5043	129580	270810
	IABV	1323	7536	26579	3834	68622	118793	5158	131054	272014
Trie-4	BV	1368	7182	23571	3973	62380	105742	6124	120220	242206
	ABV	1396	7503	24300	4055	64571	106346	6233	123834	250471
	IABV	1427	7620	24667	4151	66576	111140	6301	127998	255087
RTree	BV	1069	3448	10514	3207	28270	43799	4905	56598	106005
	ABV	1117	3589	10675	3273	28775	44428	4910	57610	106186
	IABV	1131	3793	11095	3284	29200	44890	4996	59252	107847

下載: 導(dǎo)出CSV

表 3 算法內(nèi)存訪問次數(shù)對比

規(guī)則庫	Trie-1									Trie-2
	最小內(nèi)存訪問次數(shù)			最大內(nèi)存訪問次數(shù)			平均內(nèi)存訪問次數(shù)			最小內(nèi)存訪問次數(shù)			最大內(nèi)存訪問次數(shù)			平均內(nèi)存訪問次數(shù)
	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV
ACL 10k	78	78	5	1103	471	466	605	110	48	46	51	5	1071	450	453	579	83	40
ACL 20k	78	83	5	3273	923	919	1524	137	70	46	51	5	3241	891	895	1498	111	61
ACL 30k	46	48	5	4638	1018	1014	2181	177	88	31	35	5	4606	986	990	2154	151	79
FW 10k	41	30	5	292	278	280	145	121	57	30	27	5	267	261	268	130	106	53
FW 20k	75	57	5	3271	2256	2251	1608	621	240	46	39	5	3260	2248	2248	1592	605	236
FW 30k	75	56	5	4720	2858	2853	3045	965	197	47	39	5	4715	2852	2852	3031	951	194
IPC 10k	43	48	5	1614	658	664	824	244	75	29	34	5	1596	644	654	803	223	71
IPC 20k	73	59	5	3163	733	735	1614	219	89	43	45	5	3149	719	727	1592	197	84
IPC 30k	70	64	5	4755	1092	1097	2280	386	203	42	46	5	4727	1078	1088	2258	365	196
規(guī)則庫	Trie-4									RTree
	最小內(nèi)存訪問次數(shù)			最大內(nèi)存訪問次數(shù)			平均內(nèi)存訪問次數(shù)			最小內(nèi)存訪問次數(shù)			最大內(nèi)存訪問次數(shù)			平均內(nèi)存訪問次數(shù)
	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV	BV	ABV	IABV
ACL 10k	30	35	5	1055	439	446	566	70	36	29	34	5	1054	441	448	567	71	36
ACL 20k	30	35	5	3225	875	883	1484	97	56	30	35	5	3226	876	883	1486	99	56
ACL 30k	24	28	5	4590	970	978	2141	137	74	32	37	5	4593	973	977	2145	124	74
FW 10k	24	25	5	255	252	262	122	98	51	38	42	5	269	264	260	135	110	52
FW 20k	31	30	5	3255	2244	2247	1583	596	234	37	42	5	3270	2260	2249	1595	608	236
FW 30k	32	30	5	4713	2848	2851	3023	943	192	38	42	5	4731	2866	2854	3036	957	194
IPC 10k	22	27	5	1587	637	649	793	213	68	39	44	5	1604	656	655	809	229	71
IPC 20k	28	32	5	3142	712	723	1580	185	81	41	46	5	3163	732	732	1597	202	84
IPC 30k	28	32	5	4713	1072	1084	2247	354	192	41	46	5	4733	1093	1091	2265	372	197

下載: 導(dǎo)出CSV

參考文獻(xiàn)(15)

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

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

亓亞烜, 李軍. 高性能網(wǎng)包分類理論與算法綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 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

陳小雨, 陸月明. 基于多維空間動態(tài)劃分與RFC的包分類改進(jìn)算法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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

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

萬云凱, 嵩天, 劉苗苗, 等. 流量自適應(yīng)的多維度包分類方法研究[J]. 計(jì)算機(jī)學(xué)報(bào), 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

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

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

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

賀亞威, 侯整風(fēng), 吳亮亮. 一種基于位向量流分類算法的改進(jìn)[J]. 合肥工業(yè)大學(xué)學(xué)報(bào): 自然科學(xué)版, 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

李林. 防火墻規(guī)則集關(guān)鍵技術(shù)研究[D]. [博士論文], 電子科技大學(xué), 2009.

LI Lin. Research on key techniques of firewall rule set[D]. [Ph.D. dissertation], University of Electronic Science and Technology of China, 2009.

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

顏天信, 王永綱, 石江濤, 等. 區(qū)域分割包分類算法的優(yōu)化實(shí)現(xiàn)[J]. 通信學(xué)報(bào), 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

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.

孫鵬浩, 蘭巨龍, 陸肖元, 等. 一種基于匹配域裁剪的包分類規(guī)則集壓縮方法[J]. 電子與信息學(xué)報(bào), 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

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)