多維報文分類算法研究
發(fā)布時間：2019-03-26 13:34
【摘要】：隨著社會信息化程度的逐漸提高,互聯(lián)網(wǎng)已廣泛滲透到社會生活的各個領(lǐng)域。報文分類作為互聯(lián)網(wǎng)的支撐技術(shù)之一,在網(wǎng)絡(luò)測量、防火墻訪問列表控制、負(fù)載均衡和網(wǎng)絡(luò)入侵檢測系統(tǒng)等諸多領(lǐng)域發(fā)揮著重要的作用。互聯(lián)網(wǎng)規(guī)模的急劇增長給報文分類技術(shù)帶來了嚴(yán)峻的挑戰(zhàn),為了解決當(dāng)前報文分類算法吞吐率不足、內(nèi)存使用較大和更新性能難以滿足網(wǎng)絡(luò)需求的問題,本文依托國家863計劃課題“面向三網(wǎng)融合的統(tǒng)一安全管控網(wǎng)絡(luò)”,提出了三種報文分類算法并設(shè)計了一種多維報文分類子系統(tǒng)。主要研究內(nèi)容和創(chuàng)新點(diǎn)如下:1、傳統(tǒng)的報文分類算法存在較多規(guī)則冗余,導(dǎo)致時間性能無法滿足網(wǎng)絡(luò)需求。針對此問題,提出一種基于動態(tài)點(diǎn)切分的報文分類算法(GroupCuts)。首先在分析規(guī)則集特征的基礎(chǔ)上,通過聚類具有相似空間交叉關(guān)系的規(guī)則,劃分規(guī)則集為若干子集;然后在每個子集中動態(tài)的選取規(guī)則投影點(diǎn)完成空間分解;最后建立多決策樹查找結(jié)構(gòu)。仿真結(jié)果表明,在保證算法的空間性能前提下,GroupCuts算法的內(nèi)存訪問較代表算法減少了約61%。2、當(dāng)前報文分類算法在處理大規(guī)模復(fù)雜規(guī)則集時,空間性能不夠理想,為了提高算法的空間性能,提出一種采用混合切分法的報文分類算法(HIC,Hybrid Intelligent Cuttings)。該算法首先按照IP地址前綴長度將規(guī)則集分組;然后在每個分組中根據(jù)當(dāng)前切分域的特點(diǎn),分別對IP域和端口域采用比特位切分法和精確投影點(diǎn)切分法實(shí)現(xiàn)空間分解;最后構(gòu)建混合切分結(jié)構(gòu)的決策樹。仿真結(jié)果表明,HIC算法具有較好的規(guī)則集適應(yīng)性,其內(nèi)存使用比代表算法減少了約74%。3、針對當(dāng)前報文分類算法增量更新性能不足問題,提出一種基于前綴劃分的報文分類算法(PreCuts)。該算法根據(jù)規(guī)則IP域的特點(diǎn),依次采用三種啟發(fā)式方法建立具有三層查找結(jié)構(gòu)的決策樹。在第一層中,按照規(guī)則IP地址的最高Byte分組規(guī)則。在第二層中,將具有相同IP前綴長度的規(guī)則劃分到同一個分組。第三層決策樹采用前綴比特位劃分法,選取相應(yīng)的劃分比特將規(guī)則集劃分為不同的子集。PreCuts算法所采用的啟發(fā)式方法不會引入規(guī)則復(fù)制,算法查找結(jié)構(gòu)中不存在冗余規(guī)則,因此增量更新不會降低算法的時間和空間性能。仿真結(jié)果表明,與代表算法相比,Pre Cuts不僅在時間和空間性能上有所提升,并且增量更新性能提升了50%以上。4、針對當(dāng)前報文分類系統(tǒng)對網(wǎng)絡(luò)中大容量、復(fù)雜規(guī)則集適應(yīng)性不足的問題,結(jié)合本單位三網(wǎng)融合業(yè)務(wù)安全管控的要求,設(shè)計了一種基于FPGA的多維報文分類子系統(tǒng)。該系統(tǒng)采用二維流水線架構(gòu),提高了系統(tǒng)的運(yùn)算性能,使其可以處理網(wǎng)絡(luò)中大容量、復(fù)雜規(guī)則集。測試結(jié)果表明,該系統(tǒng)能夠達(dá)到60Gbps的報文分類速率,很好的滿足了當(dāng)前三網(wǎng)融合網(wǎng)絡(luò)管控的需求。
[Abstract]:With the gradual improvement of the degree of social informatization, the Internet has been widely infiltrated into various fields of social life. As one of the supporting technologies of Internet, packet classification plays an important role in many fields such as network measurement, firewall access list control, load balancing and network intrusion detection system. The rapid growth of Internet has brought serious challenges to packet classification technology. In order to solve the problems of insufficient throughput of current packet classification algorithms, large memory usage and update performance, it is difficult to meet the needs of the network. Based on the national 863 project "Unified Security Control Network for three Networks Convergence", this paper proposes three kinds of packet classification algorithms and designs a multi-dimensional message classification subsystem. The main research contents and innovations are as follows: 1. The traditional packet classification algorithm has more rules redundancy which leads to the time performance can not meet the needs of the network. In order to solve this problem, a message classification algorithm (GroupCuts). Based on dynamic point segmentation is proposed. On the basis of analyzing the features of the rule set, the rule set is divided into several subsets by clustering the rules with similar spatial crossover relations, and then the spatial decomposition is accomplished by dynamically selecting the projection points of the rules in each subset. Finally, a multi-decision tree search structure is established. The simulation results show that under the premise of guaranteeing the spatial performance of the algorithm, the memory access of the GroupCuts algorithm is about 61% less than that of the representative algorithm, and the spatial performance of the current packet classification algorithm is not satisfactory when dealing with large-scale complex rule sets. In order to improve the spatial performance of the algorithm, a message classification algorithm based on mixed segmentation (HIC,Hybrid Intelligent Cuttings).) is proposed. Firstly, the rule set is grouped according to the length of the IP address prefix, and then in each packet according to the characteristics of the current segmentation domain, the bit splitting method and the precise projection point segmentation method are used to realize the spatial decomposition of the IP domain and the port domain respectively. Finally, the decision tree with mixed segmentation structure is constructed. The simulation results show that the HIC algorithm has good rule set adaptability, and its memory usage is about 74% less than that of the representative algorithm, and the performance of incremental update of the current packet classification algorithm is insufficient. A message classification algorithm (PreCuts). Based on prefix partition is proposed. According to the characteristics of regular IP domain, three heuristic methods are used to build a decision tree with a three-layer search structure. In the first layer, the highest Byte grouping rule is based on a regular IP address. In layer 2, rules with the same IP prefix length are divided into the same group. The third layer decision tree adopts the prefix bit partition method, and selects the corresponding partition bits to divide the rule set into different subsets. The heuristic method used in PreCuts algorithm will not introduce rule replication, and there are no redundant rules in the search structure of the algorithm. Therefore, incremental updating does not degrade the temporal and spatial performance of the algorithm. The simulation results show that compared with the representative algorithm, Pre Cuts not only improves the performance of time and space, but also improves the performance of incremental update by more than 50%. 4. For the current packet classification system, it has a large capacity in the network. Due to the lack of adaptability of complex rule set, a multi-dimensional message classification subsystem based on FPGA is designed according to the requirement of security management and control of the three networks fusion business. The two-dimensional pipeline architecture is adopted in this system, which improves the performance of the system and enables it to deal with large capacity and complex rule sets in the network. The test results show that the system can achieve the packet classification rate of 60Gbps and meet the requirements of the current three-network convergence network management and control.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.08
本文編號：2447594
[Abstract]:With the gradual improvement of the degree of social informatization, the Internet has been widely infiltrated into various fields of social life. As one of the supporting technologies of Internet, packet classification plays an important role in many fields such as network measurement, firewall access list control, load balancing and network intrusion detection system. The rapid growth of Internet has brought serious challenges to packet classification technology. In order to solve the problems of insufficient throughput of current packet classification algorithms, large memory usage and update performance, it is difficult to meet the needs of the network. Based on the national 863 project "Unified Security Control Network for three Networks Convergence", this paper proposes three kinds of packet classification algorithms and designs a multi-dimensional message classification subsystem. The main research contents and innovations are as follows: 1. The traditional packet classification algorithm has more rules redundancy which leads to the time performance can not meet the needs of the network. In order to solve this problem, a message classification algorithm (GroupCuts). Based on dynamic point segmentation is proposed. On the basis of analyzing the features of the rule set, the rule set is divided into several subsets by clustering the rules with similar spatial crossover relations, and then the spatial decomposition is accomplished by dynamically selecting the projection points of the rules in each subset. Finally, a multi-decision tree search structure is established. The simulation results show that under the premise of guaranteeing the spatial performance of the algorithm, the memory access of the GroupCuts algorithm is about 61% less than that of the representative algorithm, and the spatial performance of the current packet classification algorithm is not satisfactory when dealing with large-scale complex rule sets. In order to improve the spatial performance of the algorithm, a message classification algorithm based on mixed segmentation (HIC,Hybrid Intelligent Cuttings).) is proposed. Firstly, the rule set is grouped according to the length of the IP address prefix, and then in each packet according to the characteristics of the current segmentation domain, the bit splitting method and the precise projection point segmentation method are used to realize the spatial decomposition of the IP domain and the port domain respectively. Finally, the decision tree with mixed segmentation structure is constructed. The simulation results show that the HIC algorithm has good rule set adaptability, and its memory usage is about 74% less than that of the representative algorithm, and the performance of incremental update of the current packet classification algorithm is insufficient. A message classification algorithm (PreCuts). Based on prefix partition is proposed. According to the characteristics of regular IP domain, three heuristic methods are used to build a decision tree with a three-layer search structure. In the first layer, the highest Byte grouping rule is based on a regular IP address. In layer 2, rules with the same IP prefix length are divided into the same group. The third layer decision tree adopts the prefix bit partition method, and selects the corresponding partition bits to divide the rule set into different subsets. The heuristic method used in PreCuts algorithm will not introduce rule replication, and there are no redundant rules in the search structure of the algorithm. Therefore, incremental updating does not degrade the temporal and spatial performance of the algorithm. The simulation results show that compared with the representative algorithm, Pre Cuts not only improves the performance of time and space, but also improves the performance of incremental update by more than 50%. 4. For the current packet classification system, it has a large capacity in the network. Due to the lack of adaptability of complex rule set, a multi-dimensional message classification subsystem based on FPGA is designed according to the requirement of security management and control of the three networks fusion business. The two-dimensional pipeline architecture is adopted in this system, which improves the performance of the system and enables it to deal with large capacity and complex rule sets in the network. The test results show that the system can achieve the packet classification rate of 60Gbps and meet the requirements of the current three-network convergence network management and control.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.08
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 韓偉濤;伊鵬;扈紅超;;基于動態(tài)點(diǎn)切分的多決策樹包分類算法[J];電子與信息學(xué)報;2013年12期
2 韓偉濤;伊鵬;扈紅超;毛苗;賈辰龍;;一種基于幾何區(qū)域分割的網(wǎng)包分類算法[J];計算機(jī)應(yīng)用研究;2013年07期
3 謝鯤;趙姣姣;張大方;;聯(lián)合元組空間和位圖設(shè)計的二維分組分類算法[J];通信學(xué)報;2011年09期
4 李玉峰;蘭巨龍;薛向陽;;面向三網(wǎng)融合的統(tǒng)一安全管控技術(shù)[J];中興通訊技術(shù);2011年04期
5 張樹壯;羅浩;方濱興;;一種支持實(shí)時增量更新的并行包分類算法[J];計算機(jī)研究與發(fā)展;2010年11期
6 謝鯤;趙姣姣;張大方;畢夏安;;基于計數(shù)布魯姆過濾器的快速多維包分類算法[J];電子學(xué)報;2010年05期
7 陳兵;潘宇科;丁秋林;;一種采用啟發(fā)式分割點(diǎn)計算的包分類算法[J];電子與信息學(xué)報;2009年07期
8 尚鳳軍;潘英俊;潘雪增;畢斌;;基于隨機(jī)分布的多比特Trie樹IP數(shù)據(jù)包分類算法研究[J];通信學(xué)報;2008年07期
9 李振強(qiáng);張圣亮;馬嚴(yán);趙曉宇;;多決策樹包分類算法[J];電子與信息學(xué)報;2008年04期
10 鄭波;林闖;曲揚(yáng);;一種適合于網(wǎng)絡(luò)處理器的并行多維分類算法AM-Trie[J];軟件學(xué)報;2006年09期
，本文編號：2447594
本文鏈接：http://sikaile.net/guanlilunwen/ydhl/2447594.html
最近更新
教材專著
