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

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

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

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

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