一種快速的五元一維包分類算法

摘要:包分類算法在網(wǎng)絡(luò)安全產(chǎn)品中至關(guān)重要，該文介紹常見(jiàn)的包分類算法，針對(duì)現(xiàn)有包分類算法的不足，構(gòu)造了一種基于Hash函數(shù)的可快速查找、快速定位五元一維包分類算法，并給出算法準(zhǔn)確性、快速性的理論證明。

關(guān)鍵詞:包分類;Hash函數(shù);線性查找算法

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)36-10568-03

A New Fast Five-to-one Dimensional Packet Classification Algorithm

PEI Lin

(The People's Bank of China， Urumqi Central Sub-Branch， 830002 Wulumuqi， China)

Abstract: The packet classification algorithm is important in product of network security. This paper introduces the common packet classification algorithms， analyses the flaws of these algorithms， and constructs a new five-to-one packet classification algorithm based on Hash function. At last， the accurancy and rapidity of the new packet classification algrithom is given.

Key words: packet classification; Hash fuction; sequential search algorithm

網(wǎng)絡(luò)和信息技術(shù)已經(jīng)日漸深入到人們的日常生活和工作中，社會(huì)信息化和信息網(wǎng)絡(luò)化日益提高。在互聯(lián)網(wǎng)帶給我們便利的同時(shí)，也給我們帶來(lái)了揮之不去的安全問(wèn)題。例如黑客攻擊、計(jì)算機(jī)病毒、特洛伊木馬、拒絕服務(wù)器攻擊、信息泄露或丟失等安全威脅，會(huì)給一些用戶和企業(yè)帶來(lái)了嚴(yán)重的經(jīng)濟(jì)損失。網(wǎng)絡(luò)安全問(wèn)題引起國(guó)內(nèi)外的廣泛關(guān)注。

作為最早、技術(shù)最成熟的網(wǎng)絡(luò)安全技術(shù)，防火墻通過(guò)在網(wǎng)絡(luò)間執(zhí)行控制策略，保障網(wǎng)絡(luò)安全，其核心技術(shù)[1]就是網(wǎng)絡(luò)數(shù)據(jù)包的攔截與分類。其它一些網(wǎng)絡(luò)安全技術(shù)，如入侵檢測(cè)、網(wǎng)絡(luò)監(jiān)控、安全審計(jì)、虛擬專用網(wǎng)等，也是以數(shù)據(jù)包分類為基礎(chǔ)的。數(shù)據(jù)包分類[2]就是把網(wǎng)絡(luò)中數(shù)據(jù)包歸屬為某個(gè)流的過(guò)程，然后根據(jù)用戶預(yù)先設(shè)置的過(guò)濾規(guī)則對(duì)每一類數(shù)據(jù)包進(jìn)行相應(yīng)的處理，這些過(guò)濾規(guī)則是依據(jù)數(shù)據(jù)包頭的內(nèi)容把數(shù)據(jù)包分為不同的類。數(shù)據(jù)包分類的正確性、快速性將直接影響安全產(chǎn)品的性能與效率。由此可見(jiàn)，對(duì)數(shù)據(jù)包分類算法的研究具有重要的現(xiàn)實(shí)意義。

1 常見(jiàn)的包分類算法

現(xiàn)在的包分類算法主要有以下四種類型[3]:

1)基于數(shù)據(jù)結(jié)構(gòu)的算法

該類算法的主要特點(diǎn)是使用基本的數(shù)據(jù)結(jié)構(gòu)來(lái)組織并優(yōu)化流分類問(wèn)題的查找、定位及匹配問(wèn)題。主要的數(shù)據(jù)類型包括線性和樹型結(jié)構(gòu)等。最簡(jiǎn)單的基于線性結(jié)構(gòu)的分類算法是順序查找方法。其中，基于Tries樹結(jié)構(gòu)算法是一種常用算法。如Grid-of-Tries樹、層次Tries樹、多比特Tries樹等。

2)基于幾何空間的算法

主要思想是將整個(gè)搜索空間遞歸的按照某種規(guī)則分割成某些子空間，然后通過(guò)預(yù)處理計(jì)算這些子空間與規(guī)則之間的關(guān)系，根據(jù)這些信息構(gòu)建決策樹以進(jìn)行搜索。如交叉乘積(cross-Product)、基于區(qū)間劃分的四叉樹(Area base Quadtree)、FIS算法(Fat Inverted Tree)等。

3)啟發(fā)式的算法

啟發(fā)式分類算法[4]是指針對(duì)特定應(yīng)用環(huán)境的研究，利用規(guī)則庫(kù)內(nèi)的結(jié)構(gòu)和兀余度，根據(jù)某種特點(diǎn)而設(shè)計(jì)出流分類問(wèn)題的解決方案。如遞歸流分類算法(Recursive Floww Classification)、分層只能查找算法(Hierarchical Intelligent Cuttings)、元組空間查找算法(Tuplc Space Search)。

4)基于硬件的算法

該算法將所有的規(guī)則用硬件來(lái)實(shí)現(xiàn)，對(duì)硬件資源要求和存儲(chǔ)空間要求都很大，只適用于對(duì)速率要求很高，規(guī)則維數(shù)和個(gè)數(shù)都很少的情況。如三元內(nèi)容尋址存儲(chǔ)器(Ternary Content Addressable Memory)、位圖交集算法(Bitmap Intersection)等。

2 基于Hash函數(shù)的五元一維包分類算法

現(xiàn)有的包分類算法中[5]，一維、二維分類算法比較成熟，應(yīng)用廣泛，而對(duì)于多維包分類算法由于對(duì)要求內(nèi)存空間過(guò)大無(wú)法滿足低成本的要求，或由于其分類的速度無(wú)法滿足高速網(wǎng)絡(luò)環(huán)境的應(yīng)用需求。由于Hash函數(shù)具有快速查找和快速定位的特性，構(gòu)造了一個(gè)包分類算法——基于Hash函數(shù)的五元一維包分類算法，不但提高了查找速度，而且減少了存儲(chǔ)空間，并對(duì)算法的準(zhǔn)確性和快速性給以證明。

2.1 Hash算法的特點(diǎn)

Hash算法[6]既是一種常見(jiàn)的存儲(chǔ)方法，也是一種查找方法。Hash算法以關(guān)鍵字的值為自變量，通過(guò)一定的函數(shù)關(guān)系，計(jì)算出對(duì)應(yīng)的函數(shù)值，把這個(gè)值解釋為節(jié)點(diǎn)的存儲(chǔ)地址——Hash地址，將節(jié)點(diǎn)存入到這個(gè)存儲(chǔ)單元里去。查找時(shí)再根據(jù)查找的關(guān)鍵字用同樣的Hash函數(shù)計(jì)算地址，然后到相應(yīng)的地址單元里去取要找的節(jié)點(diǎn)。在理想情況下，不經(jīng)過(guò)任何比較，一次Hash運(yùn)算便可找到所要的節(jié)點(diǎn)。

2.2 算法設(shè)計(jì)

基于Hash函數(shù)的五元一維包分類算法包括兩個(gè)部分:過(guò)濾規(guī)則庫(kù)的建立過(guò)程和包分類的過(guò)程。下面定義幾個(gè)相關(guān)定義:

定義3.1 分類規(guī)則是一個(gè)六元組{sip，dip，sp，dp，pt，act}，其中sip代表數(shù)據(jù)包的源IP地址，dip代表數(shù)據(jù)包的目的IP地址，sp代表數(shù)據(jù)包的源端口，dp代表數(shù)據(jù)包的目的端口，pt代表數(shù)據(jù)包的協(xié)議類型，act代表符合前面條件的數(shù)據(jù)包對(duì)應(yīng)的動(dòng)作。act動(dòng)作可以簡(jiǎn)單的分為“允許”和“拒絕”，即讓符合規(guī)則的數(shù)據(jù)包進(jìn)入系統(tǒng)，或者丟棄。

定義3.2 主機(jī)IP地址:即使用本數(shù)據(jù)包分類系統(tǒng)的主機(jī)IP地址。

定義3.3 本地IP地址:即本主機(jī)所對(duì)應(yīng)的IP地址，當(dāng)發(fā)送數(shù)據(jù)時(shí)，包頭中對(duì)應(yīng)的源地址為本地IP 地址;當(dāng)接收數(shù)據(jù)時(shí)，包頭中對(duì)應(yīng)的目的IP地址。

定義3.4 外地IP地址:即發(fā)送數(shù)據(jù)時(shí)，包頭中對(duì)應(yīng)的目的IP地址;接收數(shù)據(jù)時(shí)，包頭中對(duì)應(yīng)源IP地址。

定義3.5 哈希沖突:當(dāng){sp1，dp1，pt1}∩{sp2，dp2，pt1}=φ時(shí)，若Hash{sp1，dp1，pt1}≠Hash{sp2，dp2，pt1}，則不存在哈希沖突，即不同結(jié)點(diǎn)存儲(chǔ)在不同的地址;否則，若 ，則存在哈希沖突，即不同結(jié)點(diǎn)存儲(chǔ)在相同的地址。

本算法構(gòu)造的Hash函數(shù)如下:

Hash{sp1，dp1，pt1}+Hash{sp2，dp2，pt1}%M=HashAdd

Hash函數(shù)的輸入為數(shù)據(jù)包頭的源端口sp目的端口dp、協(xié)議類型pt，Hash運(yùn)算是源端口sp和目的端口dp分別與協(xié)議類型pt異或相加，最后結(jié)果對(duì)M取模運(yùn)算，M比規(guī)則庫(kù)實(shí)際存儲(chǔ)的規(guī)則數(shù)N大20%左右的素?cái)?shù)，模運(yùn)算的結(jié)果即為結(jié)點(diǎn)存儲(chǔ)的地址——Hash地址HashAdd。

本文構(gòu)造的基于Hash函數(shù)的五元一維包分類算法包括兩個(gè)部分:規(guī)則庫(kù)的建立過(guò)程、數(shù)據(jù)包分類過(guò)程。

算法3.1 規(guī)則庫(kù)的建立算法

假設(shè)規(guī)則庫(kù)中實(shí)際存儲(chǔ)N條規(guī)則，為了減少Hash沖突，規(guī)則庫(kù)的實(shí)際大小為M(M比N大20%左右的素?cái)?shù))。規(guī)則庫(kù)的建立過(guò)程如下:

1) 分配存儲(chǔ)空間，能容納M條分類規(guī)則的規(guī)則庫(kù);

2) 初始化規(guī)則庫(kù)，每條規(guī)則置空NULL;

3) Hash運(yùn)算，得到存儲(chǔ)規(guī)則的Hash地址;

4) 在Hash地址存儲(chǔ)對(duì)應(yīng)的外地IP地址;

i) 如果無(wú)哈希沖突時(shí)，外地IP地址直接存儲(chǔ)在已計(jì)算的Hash地址中;

ii) 如果有哈希沖突，外地IP地址存儲(chǔ)在已計(jì)算的Hash地址對(duì)應(yīng)的單鏈表的尾部;

5) 重復(fù) 3)、4)步驟存儲(chǔ)所有的規(guī)則;

6) 返回規(guī)則庫(kù)的首地址，規(guī)則庫(kù)的建立完畢。

算法3.2數(shù)據(jù)包的分類算法

1) 取出數(shù)據(jù)包的本地IP地址;

2) 本地IP地址與主機(jī)地址相比較;

3) 取出數(shù)據(jù)包的源端口sp、目的端口dp、協(xié)議類型pt;

i) 如果相等，則是本機(jī)要接收的，或本主機(jī)要發(fā)送的數(shù)據(jù)包，進(jìn)入下一步;

ii) 如果不相等，則不是本機(jī)要接收的，或本主機(jī)不允許發(fā)送的數(shù)據(jù)包，丟棄該數(shù)據(jù)包。

4) Hash運(yùn)算，得到Hash表的入口地址;

5) 取出數(shù)據(jù)包的外地IP地址與Hash表中存儲(chǔ)的信息相比較;

i) 如果對(duì)應(yīng)Hash地址的值為NULL，則丟棄該數(shù)據(jù)包;

ii) 如果對(duì)應(yīng)Hash地址中只存入一個(gè)外地IP 地址，則數(shù)據(jù)包的外地IP地址直接與其相比，匹配則按照預(yù)先設(shè)置的規(guī)則對(duì)數(shù)據(jù)包進(jìn)行處理，不匹配則丟棄該數(shù)據(jù)包;

iii) 如果對(duì)應(yīng)Hash地址中存入多個(gè)外地IP地址，則數(shù)據(jù)包的外地IP 地址依次與其相比，直到匹配為止則按照預(yù)先設(shè)置的規(guī)則對(duì)數(shù)據(jù)包進(jìn)行處理，不匹配則丟棄該數(shù)據(jù)包。

規(guī)則庫(kù)的建立和數(shù)據(jù)包分類過(guò)程兩個(gè)部分是不可分割的整體，規(guī)則庫(kù)的建立是數(shù)據(jù)包分類的前提，兩個(gè)過(guò)程都用到了相同的Hash函數(shù)，前者由Hash運(yùn)算得到存儲(chǔ)外地IP地址的Hash地址，后者由Hash運(yùn)算來(lái)定位Hash地址，判斷這個(gè)地址是否存儲(chǔ)了與之相比較的外地IP地址，如果有則數(shù)據(jù)包被預(yù)置規(guī)則分類。

下面給出理論證明，證明該算法的準(zhǔn)確性。

定理3.1 由算法3.1建立規(guī)則庫(kù)，凡是進(jìn)出主機(jī)的數(shù)據(jù)包依據(jù)算法3.2，都能被已建立的規(guī)則庫(kù)分類。

證明:符號(hào)約定:inip代表本地IP地址，outip代表外地IP地址，sp代表源端口，dp代表目的端口，pt代表協(xié)議類型，p代表數(shù)據(jù)包，hostip代表主機(jī)IP地址。假設(shè)規(guī)則庫(kù)R存儲(chǔ)N條規(guī)則，為了減少哈希沖突，采用拉鏈法，規(guī)則庫(kù)實(shí)際大小為M(M比N大20%左右的素?cái)?shù))

1)規(guī)則庫(kù)的建立

R={outip1， outip2， …… ，outipN}

p=

Np={p1， p2， ……， pN}

對(duì)于任意Pi∈Np， 1?燮i?燮N;

Hash(spi，dpi，pti)+(spi^pti+dpi^pti)=HashAddi //得到Hash表的地址

pj∈Np， 1?燮j?燮N， 且j≠i//outipi存儲(chǔ)在HashAddi

如果 Hash(spj，dpj，ptj)≠Hash(spi， dpi，pti)//無(wú)哈希沖突

則HashAddi=outipi//在HashAddi僅存儲(chǔ)outipi①

如果Hash(spj，dpj，ptj)=Hash(spi，dpi，pti)//哈希沖突

則HashAddi={outipi， outipj} 在HashAddi僅存儲(chǔ)outipi，outipj兩面條規(guī)則，且outipj鏈接在outipi后面，依此類推，有多少哈希地址相同的就在同一地址存儲(chǔ)多少規(guī)則②

其它哈希地址置空NULL

規(guī)則庫(kù)建立完畢

2)數(shù)據(jù)包的分類

對(duì)于進(jìn)出主機(jī)的任意數(shù)據(jù)包p，取出包頭的五元組信息，即

P=;

如果inip≠hostip //丟棄該數(shù)據(jù)包

如果inip=hostip //進(jìn)行下步處理

Hash(sp，dp，pt)+(sp^pt+dp^pt)%M=HashAdd //得到Hash地址

如果HashAdd=HashAddi

由①得，必然有HashAddi=outipi，如果outip=outipi， 則該數(shù)據(jù)包被規(guī)則分類，否則丟棄該數(shù)據(jù)包

由②得，必然有HashAddi {outipi， outipj， ……}，如果outip∈{outipi， outipj， ……}，則該數(shù)據(jù)包被規(guī)則分類，否則丟棄該數(shù)據(jù)包

證明完畢

上述證明了該算法可以準(zhǔn)確的對(duì)數(shù)據(jù)包進(jìn)行分類，另外也可以看出雖然在包分類的過(guò)程中，用到了數(shù)據(jù)包的五元信息，通過(guò)一次比較和一次Hash運(yùn)算，最終在規(guī)則庫(kù)中只存儲(chǔ)了外地IP地址，因此不但從五元降到了一維，也減小了存儲(chǔ)空間，提高了包分類的效率。

定理3.2 基于Hash函數(shù)的五元一維包分類算法優(yōu)于線性查找算法

證明:假設(shè)規(guī)則庫(kù)中存儲(chǔ)了N條規(guī)則，線性查找的平均查找長(zhǎng)度為

ASLSS=P1+2P2+ … +(n-1)Pn-1+nPn

在等概率的條件下:pi=1/n， 即ASLSS=1/n(1+2+ … +n) – (n+1)/2

假設(shè)規(guī)則庫(kù)的Hash表無(wú)哈希沖突，可一次定位，則基于Hash函數(shù)的五元一維包分類算法的平均查找長(zhǎng)度為:ASLSS=1

假設(shè)規(guī)則庫(kù)的Hash表存在哈希沖突，在最壞情況下，m個(gè)無(wú)哈希沖突(1

那么，

因?yàn)閚>m>1，所以，即基于Hash函數(shù)的五元一維包分類算法優(yōu)于線性查找算法成立。

3 算法性能分析

數(shù)據(jù)包分類算法的性能評(píng)價(jià)，通常從空間復(fù)雜度、時(shí)間復(fù)雜度和是否易于更新等多個(gè)方面去考慮。下面從這三個(gè)方面分析本文設(shè)計(jì)的算法性能。

3.1 時(shí)間復(fù)雜度

Hash算法在理論上，它的時(shí)間復(fù)雜度是O(1)，但實(shí)際上由于沖突的存在，它的平均查找長(zhǎng)度將會(huì)1大。該算法采用拉鏈法解決沖突，由于拉鏈法查找就是在單鏈表上查找，單鏈表中第一個(gè)結(jié)點(diǎn)查找1次，第2個(gè)結(jié)點(diǎn)查找2次，其余依次類推。由于在構(gòu)造Hash函數(shù)時(shí)，充分考慮了第個(gè)域的信息，降低了Hash沖突的概率，因此在同一哈希地址存儲(chǔ)的規(guī)則個(gè)數(shù)也不會(huì)太多。

3.2 空間復(fù)雜度

本文的算法占用空間主要是用來(lái)存儲(chǔ)32bit的外地IP地址，空間大小主要與哈希沖突的數(shù)目有關(guān)，哈希沖突越多點(diǎn)用空間越多。由于存在哈希沖突的情況，所以空間大小不能精確預(yù)計(jì)。但是壞蛋其它算法把五元組都存儲(chǔ)相比，還是有了質(zhì)的提高。

3.3 是否易于更新

由于Hash函數(shù)具有一步定們的特點(diǎn)，所以該算法易于更新。當(dāng)增加或者刪除規(guī)則時(shí)，只需要進(jìn)行局部操作，不會(huì)影響整個(gè)結(jié)構(gòu)。更新實(shí)際上是對(duì)Hash鏈表進(jìn)行操作，所以更新的時(shí)間復(fù)雜度為O(1)，具有更新速度快的特點(diǎn)。

4 結(jié)束語(yǔ)

本文根據(jù)Hash函數(shù)快速查找、快速定位的特性，提出了一種基于Hash函數(shù)的五元一維包分類算法。雖然此算法是基于數(shù)據(jù)包的五元組，但最終存儲(chǔ)在規(guī)則庫(kù)中的只有外地IP地址，減小了存儲(chǔ)空間，提高了包分類效率，并且給出了算法準(zhǔn)確性、快速性的理論分析。

參考文獻(xiàn):

[1] 朱雁輝.Windows防火墻與網(wǎng)絡(luò)封包截獲技術(shù)[M].北京:電子工業(yè)出版社，2002:119-131.

[2] Pankaj Gupta，Nick Mckcown.Algorithms for Packet Classification[C].IEEE Network.March，2001.

[3] Xue hong.IP Address Lookup and Packet Classification Alogrithms[D].Ottawa，Ontario，Carleton University，2003:43-45.

[4] 林闖，單志廣，任豐源.計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量(Qos)[M].北京:清華大學(xué)出版社，2004:119-120.

[5] 徐恪，徐明偉，吳建平，喻中越.IP分類技術(shù)研究綜述[J].電子學(xué)報(bào)，2001(2):773-779.

[6] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2004:214-262.