高性能多維包分類算法的研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展以及網(wǎng)絡(luò)應(yīng)用的層出不窮，互聯(lián)網(wǎng)用戶對(duì)網(wǎng)絡(luò)服務(wù)的可靠性、安全性、多樣性都提出了更深層次的要求。路由器需要提供有差別的網(wǎng)絡(luò)服務(wù)才能滿足不同用戶的需求，如包過濾防火墻、流量計(jì)費(fèi)、流量控制、區(qū)分服務(wù)、QoS等。為了支撐這些新型的網(wǎng)絡(luò)服務(wù)，傳統(tǒng)的單獨(dú)依據(jù)目標(biāo)地址進(jìn)行匹配的單維包分類算法已經(jīng)不能滿足多樣化的網(wǎng)絡(luò)新需求，路由器需要根據(jù)數(shù)據(jù)包頭的多個(gè)域?qū)?shù)據(jù)進(jìn)行分類處理，例如數(shù)據(jù)報(bào)文的5元組(源IP地址、目的IP地址、源端口、目的

2、端口、協(xié)議)。研究表明，Internet持續(xù)迅猛的發(fā)展對(duì)多維包分類算法提出越來越高的性能要求，不僅要求匹配速度快、空間占用少，且對(duì)算法動(dòng)態(tài)更新及擴(kuò)展性能也有高的要求。研究高性能的多維包分類算法是大規(guī)模高速網(wǎng)絡(luò)發(fā)展的必然要求。本文提出兩種高性能的多維包分類算法，一種屬于軟件范疇，一種屬于硬件范疇，如下所述：
　　 軟件算法方面，提出一種基于元組空間的高性能二維包分類算法TB(JointTuple Space and Bitmap)

3、，該算法從維度分解思想出發(fā)，聯(lián)合元組空間和位圖設(shè)計(jì)并實(shí)現(xiàn)。TB算法首先分別對(duì)源IP和目的IP進(jìn)行單維匹配后，運(yùn)用交叉組合思想形成訪問元組空間的路線，并通過位圖過濾技術(shù)進(jìn)一步減少訪問元組空間的個(gè)數(shù)。相比傳統(tǒng)的元組空間算法，TB算法結(jié)構(gòu)清晰簡潔易于實(shí)現(xiàn)，時(shí)間和空間性能較為優(yōu)越，規(guī)則庫更新較易，且算法擴(kuò)展性能較好。實(shí)驗(yàn)證明，TB算法平均訪問內(nèi)存次數(shù)低于元組空間代表算法RSFR約26.6％，空間性能平均低于RSFR算法35.1％。
　　

4、 硬件算法方面，提出一種基于計(jì)數(shù)布魯姆過濾器的快速多維包分類算法CBHT(Counting Bloom filter and Hash Table)，該算法從數(shù)據(jù)包匹配規(guī)則的聚集特性出發(fā)，結(jié)合計(jì)數(shù)布魯姆過濾器和哈希表設(shè)計(jì)并實(shí)現(xiàn)?；诰奂匦?，對(duì)于五維包分類問題，CBHT算法首先利用計(jì)數(shù)布魯姆過濾器的過濾功能結(jié)合單域匹配獲得與前兩維匹配的小規(guī)模規(guī)則集，而后在此有限規(guī)則集中對(duì)后三維進(jìn)行匹配。CBHT運(yùn)用數(shù)據(jù)包匹配的聚集特性對(duì)傳統(tǒng)的硬件算法結(jié)