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

摘要:包分類算法在網絡安全產品中至關重要，該文介紹常見的包分類算法，針對現有包分類算法的不足，構造了一種基于Hash函數的可快速查找、快速定位五元一維包分類算法，并給出算法準確性、快速性的理論證明。

關鍵詞:包分類;Hash函數;線性查找算法

中圖分類號:TP311文獻標識碼:A文章編號: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

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

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

1 常見的包分類算法

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

1)基于數據結構的算法

該類算法的主要特點是使用基本的數據結構來組織并優化流分類問題的查找、定位及匹配問題。主要的數據類型包括線性和樹型結構等。最簡單的基于線性結構的分類算法是順序查找方法。其中，基于Tries樹結構算法是一種常用算法。如Grid-of-Tries樹、層次Tries樹、多比特Tries樹等。

2)基于幾何空間的算法

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

3)啟發式的算法

啟發式分類算法[4]是指針對特定應用環境的研究，利用規則庫內的結構和兀余度，根據某種特點而設計出流分類問題的解決方案。如遞歸流分類算法(Recursive Floww Classification)、分層只能查找算法(Hierarchical Intelligent Cuttings)、元組空間查找算法(Tuplc Space Search)。

4)基于硬件的算法

該算法將所有的規則用硬件來實現，對硬件資源要求和存儲空間要求都很大，只適用于對速率要求很高，規則維數和個數都很少的情況。如三元內容尋址存儲器(Ternary Content Addressable Memory)、位圖交集算法(Bitmap Intersection)等。

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

現有的包分類算法中[5]，一維、二維分類算法比較成熟，應用廣泛，而對于多維包分類算法由于對要求內存空間過大無法滿足低成本的要求，或由于其分類的速度無法滿足高速網絡環境的應用需求。由于Hash函數具有快速查找和快速定位的特性，構造了一個包分類算法——基于Hash函數的五元一維包分類算法，不但提高了查找速度，而且減少了存儲空間，并對算法的準確性和快速性給以證明。

2.1 Hash算法的特點

Hash算法[6]既是一種常見的存儲方法，也是一種查找方法。Hash算法以關鍵字的值為自變量，通過一定的函數關系，計算出對應的函數值，把這個值解釋為節點的存儲地址——Hash地址，將節點存入到這個存儲單元里去。查找時再根據查找的關鍵字用同樣的Hash函數計算地址，然后到相應的地址單元里去取要找的節點。在理想情況下，不經過任何比較，一次Hash運算便可找到所要的節點。

2.2 算法設計

基于Hash函數的五元一維包分類算法包括兩個部分:過濾規則庫的建立過程和包分類的過程。下面定義幾個相關定義:

定義3.1 分類規則是一個六元組{sip，dip，sp，dp，pt，act}，其中sip代表數據包的源IP地址，dip代表數據包的目的IP地址，sp代表數據包的源端口，dp代表數據包的目的端口，pt代表數據包的協議類型，act代表符合前面條件的數據包對應的動作。act動作可以簡單的分為“允許”和“拒絕”，即讓符合規則的數據包進入系統，或者丟棄。

定義3.2 主機IP地址:即使用本數據包分類系統的主機IP地址。

定義3.3 本地IP地址:即本主機所對應的IP地址，當發送數據時，包頭中對應的源地址為本地IP 地址;當接收數據時，包頭中對應的目的IP地址。

定義3.4 外地IP地址:即發送數據時，包頭中對應的目的IP地址;接收數據時，包頭中對應源IP地址。

定義3.5 哈希沖突:當{sp1，dp1，pt1}∩{sp2，dp2，pt1}=φ時，若Hash{sp1，dp1，pt1}≠Hash{sp2，dp2，pt1}，則不存在哈希沖突，即不同結點存儲在不同的地址;否則，若 ，則存在哈希沖突，即不同結點存儲在相同的地址。

本算法構造的Hash函數如下:

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

Hash函數的輸入為數據包頭的源端口sp目的端口dp、協議類型pt，Hash運算是源端口sp和目的端口dp分別與協議類型pt異或相加，最后結果對M取模運算，M比規則庫實際存儲的規則數N大20%左右的素數，模運算的結果即為結點存儲的地址——Hash地址HashAdd。

本文構造的基于Hash函數的五元一維包分類算法包括兩個部分:規則庫的建立過程、數據包分類過程。

算法3.1 規則庫的建立算法

假設規則庫中實際存儲N條規則，為了減少Hash沖突，規則庫的實際大小為M(M比N大20%左右的素數)。規則庫的建立過程如下:

1) 分配存儲空間，能容納M條分類規則的規則庫;

2) 初始化規則庫，每條規則置空NULL;

3) Hash運算，得到存儲規則的Hash地址;

4) 在Hash地址存儲對應的外地IP地址;

i) 如果無哈希沖突時，外地IP地址直接存儲在已計算的Hash地址中;

ii) 如果有哈希沖突，外地IP地址存儲在已計算的Hash地址對應的單鏈表的尾部;

5) 重復 3)、4)步驟存儲所有的規則;

6) 返回規則庫的首地址，規則庫的建立完畢。

算法3.2數據包的分類算法

1) 取出數據包的本地IP地址;

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

3) 取出數據包的源端口sp、目的端口dp、協議類型pt;

i) 如果相等，則是本機要接收的，或本主機要發送的數據包，進入下一步;

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

4) Hash運算，得到Hash表的入口地址;

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

i) 如果對應Hash地址的值為NULL，則丟棄該數據包;

ii) 如果對應Hash地址中只存入一個外地IP 地址，則數據包的外地IP地址直接與其相比，匹配則按照預先設置的規則對數據包進行處理，不匹配則丟棄該數據包;

iii) 如果對應Hash地址中存入多個外地IP地址，則數據包的外地IP 地址依次與其相比，直到匹配為止則按照預先設置的規則對數據包進行處理，不匹配則丟棄該數據包。

規則庫的建立和數據包分類過程兩個部分是不可分割的整體，規則庫的建立是數據包分類的前提，兩個過程都用到了相同的Hash函數，前者由Hash運算得到存儲外地IP地址的Hash地址，后者由Hash運算來定位Hash地址，判斷這個地址是否存儲了與之相比較的外地IP地址，如果有則數據包被預置規則分類。

下面給出理論證明，證明該算法的準確性。

定理3.1 由算法3.1建立規則庫，凡是進出主機的數據包依據算法3.2，都能被已建立的規則庫分類。

證明:符號約定:inip代表本地IP地址，outip代表外地IP地址，sp代表源端口，dp代表目的端口，pt代表協議類型，p代表數據包，hostip代表主機IP地址。假設規則庫R存儲N條規則，為了減少哈希沖突，采用拉鏈法，規則庫實際大小為M(M比N大20%左右的素數)

1)規則庫的建立

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

p=

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

對于任意Pi∈Np， 1?燮i?燮N;

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

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

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

則HashAddi=outipi//在HashAddi僅存儲outipi①

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

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

其它哈希地址置空NULL

規則庫建立完畢

2)數據包的分類

對于進出主機的任意數據包p，取出包頭的五元組信息，即

P=;

如果inip≠hostip //丟棄該數據包

如果inip=hostip //進行下步處理

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

如果HashAdd=HashAddi

由①得，必然有HashAddi=outipi，如果outip=outipi， 則該數據包被規則分類，否則丟棄該數據包

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

證明完畢

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

定理3.2 基于Hash函數的五元一維包分類算法優于線性查找算法

證明:假設規則庫中存儲了N條規則，線性查找的平均查找長度為

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

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

假設規則庫的Hash表無哈希沖突，可一次定位，則基于Hash函數的五元一維包分類算法的平均查找長度為:ASLSS=1

假設規則庫的Hash表存在哈希沖突，在最壞情況下，m個無哈希沖突(1

那么，

因為n>m>1，所以，即基于Hash函數的五元一維包分類算法優于線性查找算法成立。

3 算法性能分析

數據包分類算法的性能評價，通常從空間復雜度、時間復雜度和是否易于更新等多個方面去考慮。下面從這三個方面分析本文設計的算法性能。

3.1 時間復雜度

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

3.2 空間復雜度

本文的算法占用空間主要是用來存儲32bit的外地IP地址，空間大小主要與哈希沖突的數目有關，哈希沖突越多點用空間越多。由于存在哈希沖突的情況，所以空間大小不能精確預計。但是壞蛋其它算法把五元組都存儲相比，還是有了質的提高。

3.3 是否易于更新

由于Hash函數具有一步定們的特點，所以該算法易于更新。當增加或者刪除規則時，只需要進行局部操作，不會影響整個結構。更新實際上是對Hash鏈表進行操作，所以更新的時間復雜度為O(1)，具有更新速度快的特點。

4 結束語

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

參考文獻:

[1] 朱雁輝.Windows防火墻與網絡封包截獲技術[M].北京:電子工業出版社，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] 林闖，單志廣，任豐源.計算機網絡的服務質量(Qos)[M].北京:清華大學出版社，2004:119-120.

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

[6] 嚴蔚敏，吳偉民.數據結構[M].北京:清華大學出版社，2004:214-262.