基于規(guī)則聚集特征的高速包分類算法.pdf

1、迅速發(fā)展的云計(jì)算技術(shù)與大數(shù)據(jù)技術(shù)使得互聯(lián)網(wǎng)承載著越來越多的應(yīng)用業(yè)務(wù)，數(shù)據(jù)規(guī)模大幅擴(kuò)增，盡力而為的傳統(tǒng)網(wǎng)絡(luò)服務(wù)根本滿足不了廣大用戶的需求。包分類技術(shù)是下一代互聯(lián)網(wǎng)絡(luò)設(shè)備提供多種應(yīng)用服務(wù)的關(guān)鍵技術(shù)，所以快速地進(jìn)行數(shù)據(jù)包分類對(duì)于網(wǎng)絡(luò)發(fā)展具有重大意義。目前，研究人員開始將包分類的研究領(lǐng)域轉(zhuǎn)向更廣泛的范圍，而數(shù)據(jù)挖掘中的聚類思想可以很好地解決包分類領(lǐng)域中遇到的問題?；诰垲惖陌诸愃惴ㄍǔＲ刖垲惙治隼碚搶?duì)包分類問題形式化分析，利用規(guī)則的聚集特征

2、來設(shè)計(jì)高效、靈活的包分類結(jié)構(gòu)、算法和機(jī)制，以提升包分類技術(shù)的綜合性能。近年來，IPv4地址短缺，未來互聯(lián)網(wǎng)的發(fā)展離不開對(duì)IPv6的支持和應(yīng)用。因此設(shè)計(jì)一種簡(jiǎn)單且能支持IPv4和IPv6的包分類算法，是一個(gè)極富挑戰(zhàn)的工作。針對(duì)上述問題，本文做了以下工作:
　　(1)提出了基于地址前綴長(zhǎng)度和聚類的包分類算法。通過分析及利用真實(shí)IPv4規(guī)則的聚集特征，該算法設(shè)計(jì)了一種高效的混合層次搜索結(jié)構(gòu):第一層結(jié)構(gòu)根據(jù)規(guī)則的源/目的地址前綴長(zhǎng)度和進(jìn)行

3、聚類，并依據(jù)所得聚類以及聚類中規(guī)則的最高優(yōu)先級(jí)建立一棵基于優(yōu)先級(jí)剪枝的搜索樹，每個(gè)聚類為搜索樹中的一個(gè)有效結(jié)點(diǎn)。針對(duì)傳統(tǒng)的四向樹算法搜索結(jié)構(gòu)中存在大量的空白結(jié)點(diǎn)，極大浪費(fèi)內(nèi)存空間的問題，算法第二層結(jié)構(gòu)為每個(gè)聚類建立一棵基于優(yōu)先級(jí)的四向樹，該優(yōu)先級(jí)四向樹將優(yōu)先級(jí)高的規(guī)則放到四向樹中較低層次的空結(jié)點(diǎn)，從而壓縮了中間的空白結(jié)點(diǎn)，加快了數(shù)據(jù)包查找速度。
　　(2)提出了基于優(yōu)先級(jí)Trie樹的IPv6包分類算法。通過對(duì)真實(shí)網(wǎng)絡(luò)中的IPv6規(guī)

4、則進(jìn)行研究與分析發(fā)現(xiàn):IPv6規(guī)則的源/目的地址前綴的前16位前綴值約有9種;大多數(shù)規(guī)則的源/目的地址前綴是以前綴值0x2001開頭的，其余前綴值的規(guī)則是極少的;規(guī)則的源/目的地址前綴長(zhǎng)度少于16也是極少的。根據(jù)這些特征，算法從規(guī)則的源/目的地址前綴的第17位開始進(jìn)行降維，即對(duì)源/目的地址前綴進(jìn)行按位異或運(yùn)算，最后得一復(fù)合IP地址前綴，并根據(jù)這復(fù)合IP地址前綴構(gòu)建優(yōu)先級(jí)Trie樹。優(yōu)先級(jí)Trie樹將優(yōu)先級(jí)高的規(guī)則提前放置在Trie樹中較