[發明專利]基于網絡流量統計信息的快速網包分類方法

有效

• 申請號: 200910088173.2
• 申請日: 2009-07-10
• 公開（公告）號: CN101594303A
• 公開（公告）日: 2009-12-02
• 發明（設計）人: 徐波;李軍
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 北京清亦華知識產權代理事務所（普通合伙）
• 代理人: 羅文群

1.一種基于網絡流量統計信息的快速網包分類方法，其特征在于該方法包括以下各步驟：

(1)根據用戶預先設定的網包分類規則集，分別確定網包包頭的源網絡層地址、目的網絡層地址、源傳輸層端口、目的傳輸層端口四個域在各自全空間中的空間劃分，為四個域分別建立空間劃分與網包分類規則之間的第一、第二、第三、第四規則映射表；

(2)以源網絡層地址的空間劃分序號SIP₁～SIP_u為列，以目的網絡層地址的空間劃分序號DIP₁～DIP_v為行，建立地址查找表，根據上述第一和第二規則映射表，分別將與源網絡層地址的每個空間劃分SIP_a相對應的規則映射和與目的網絡層地址的每個空間劃分DIP_b相對應的規則映射做“位與”運算，其中1≤a≤u，1≤b≤v，對運算所得的每個非重復的規則映射按出現的先后進行編號，得到地址編號AST₁～AST_p，并將編號1～p寫入以SIP_a為列、以DIP_b為行的地址查找表中的相應單元中，同時建立地址編號AST₁～AST_p與網包分類規則之間的第五規則映射表；

(3)以源傳輸層端口的空間劃分序號SP₁～SP_m為列，以目的傳輸層端口的空間劃分序號DP₁～DP_n為行建立端口查找表，根據上述第三和第四規則映射表，分別將與源傳輸層端口的每個空間劃分SP_c相對應的規則映射和與目的傳輸層端口的每個空間劃分DP_d相對應的規則映射做“位與”運算，其中1≤c≤m，1≤d≤n，對運算所得的每個非重復的規則映射按出現的先后進行編號，得到端口編號PST₁～PST_q，并將編號1～q寫入以SP_c為列、以DP_d為行的端口查找表的單元中，同時建立端口編號PST₁～PST_q與網包分類規則之間的第六規則映射表；

(4)以地址查找表中的地址編號AST₁～AST_p為列，以端口查找表中的端口編號PST₁～PST_q為行，建立規則查找表，根據上述第五和第六規則映射表，分別將與地址查找表中的每個地址編號AST_e相對應的規則映射和與端口查找表中的每個端口編號PST_f相對應的規則映射做“位與”運算，其中1≤e≤p，1≤f≤q，從右至左在運算所得的每個的規則映射中查找第一個為1的比特位的序號，將該序號寫入以AST_e為列、以PST_f為行的端口查找表的單元中，該序號為匹配的優先級最高的規則序號，刪除第一至第六規則映射表；

(5)根據用戶設定的采樣間隔，記錄網絡流量中輸入的網包包頭在各個域的空間劃分中出現的次數，并在更新時刻對各個域的統計信息做歸一化處理，從而得到各個域在空間劃分中的先驗分布；

(6)根據各個域在空間劃分中的先驗分布，利用字母搜索樹分別建立一棵空間搜索樹；

(7)對接收到的網包進行規則匹配：

根據網包包頭的源/目的網絡層地址，源/目的傳輸層端口四個域，利用四個域的字母搜索樹分別確定網包包頭四個域所在的空間劃分的序號；

利用源/目的網絡層地址的空間劃分序號，檢索地址查找表，同時利用源/目的傳輸層端口的空間序號檢索端口查找表；

利用檢索地址查找表得到的地址編號以及檢索端口查找表得到的端口編號檢索規則查找表，得到最終匹配的網包分類規則序號，并根據此序號指示的規則對網包進行放行或者阻止操作；

(8)重復步驟(7)，對網絡流量中的網包進行連續匹配，并根據用戶預先設定的更新頻率，在更新時刻到來時，重新執行步驟(5)～(8)。

2.如權利要求1所述的方法，其特征在于所述的步驟(5)根據用戶設定的采樣間隔，記錄網絡流量輸入的網包包頭在各個域的空間劃分中的出現的次數，并在更新時刻對各個域的統計信息做歸一化處理，從而得到各個域在空間劃分中的先驗分布，其具體過程如下：

(5-1)設采樣間隔為N個網包，從輸入的網絡包頭信息隊列中每N個連續到達的網包中抽取一個五元組包頭信息作為一個采樣樣本，每個樣本由下述四個域組成的數據組：

32位源網絡層地址，用int32?SIP表示，int表示整數類型，下同；

32位目標網絡層地址，用int32?DIP表示；

16位源傳輸層端口，用int16?SP表示；

16位目標傳輸層端口，用int16?DP表示；

(5-2)記錄采樣所得的樣本網包包頭在各個域的空間劃分中出現的次數：

用數組int32?Stats_SIP[u]記錄采樣的網絡包頭在源網絡層地址的u個空間劃分中分別出現的次數；

用數組int32?Stats_DIP[v]記錄采樣的網絡包頭在目的網絡層地址的v個空間劃分中分別出現的次數；

用數組int32?Stats_SP[m]記錄采樣的網絡包頭在源傳輸層端口的m個空間劃分中分別出現的次數；

用數組int32?Stats_DP[n]記錄采樣的網絡包頭在目的傳輸層端口的n個空間劃分中分別出現的次數；

(5-3)最后做歸一化，得到網包包頭各個域在其空間劃分中的先驗分布，歸一化的方法為：

對于源網絡層地址，其空間劃分的先驗分布為：

Prior_SIP[i]=Stats_SIP[i]Σj=1uStats_SIP[j],]]>其中1≤i≤u，

對于目的網絡層地址，其空間劃分的先驗分布為：

Prior_DIP[i]=Stats_DIP[i]Σj=1vStats_DIP[j],]]>其中1≤i≤v，

對于源傳輸層端口，其空間劃分的先驗分布為：

Prior_SP[i]=Stats_SP[i]Σj=1mStats_SP[j],]]>其中1≤i≤m，

對于目的傳輸層端口，其空間劃分的先驗分布為：

Prior_DP[i]=Stats_DP[i]Σj=1nStats_DP[j],]]>其中1≤i≤n。