[發明專利]一種基于社區發現的包分類方法及系統

有效

• 申請號: 201711220576.9
• 申請日: 2017-11-29
• 公開（公告）號: CN107888494B
• 公開（公告）日: 2020-06-26
• 發明（設計）人: 張大方;李果;李彥彪
• 申請（專利權）人: 湖南大學
• 主分類號: H04L12/715
• 分類號: H04L12/715;H04L12/721;H04L12/741
• 代理公司: 長沙正奇專利事務所有限責任公司 43113
• 代理人: 馬強;王娟

本發明公開了一種基于社區發現的包分類方法及系統，包括以下步驟：使用規則生成器生成原始規則集；將原始規則集中的規則使用環形窗口、規則相似性算法組成新的社區集合，每個社區內的規則都具有相同的處理動作；對達到路由器的數據包，提取頭部字段的五元組屬性；將數據包屬性與社區集合進行匹配，并直接將社區的動作應用到對數據包的處理上；當路由規則更新時，判斷社區結構中間層是否需要更新。本發明提供了一種使用社區發現技術來快速找到數據包處理動作的方法，使路由器在對數據包進行處理時，能夠將規則匹配和處理動作兩個步驟進行結合，從而提高了數據包轉發效率，并且社區結構中間層適合未來網絡中路由器規則需要頻繁更新的場景。

技術領域

本發明涉及網絡數據包分類領域，特別是一種基于社區發現技術的網絡數據包分類處理方法。

背景技術

網絡數據包分類是指當數據包到達路由器后，路由器先提取數據包的頭部字段進行規則匹配，然后執行對應規則中對數據包的處理動作。

傳統包分類算法研究使用的規則集，一般是基于模擬的規則生成工具，例如使用ClassBench產生。使用模擬規則的原因是，真實的規則集一般都要保密且難以獲取，而模擬規則能較好地進行仿真并被大量使用，所以成為了包分類算法研究的一種基準。但是在傳統的研究中，包分類算法的最后一步是規則匹配，路由器執行匹配規則中對數據包的處理動作并不在包分類算法的考慮中。當我們用基于ClassBench產生的規則與數據進行實驗，并把實驗擴展到真實的帶有多網口的服務器轉發平臺時，我們發現不會有系統自動幫我們執行轉發的動作，這個動作需要我們在包分類算法匹配之后完成。而且原始規則的數量一般比較多，但是規則中定義的動作種類卻相對少得多，執行動作一般是從某個網口轉發或者拒絕丟棄等。因此我們的研究目的是發現規則和動作之間是否存在一定的聯系，并研究是否能將規則匹配和執行動作兩個步驟相結合進行考慮。

包分類算法作為一項長期研究的課題，已有多種方法從不同的規則匹配角度來進行研究。路由規則中的IP地址、端口等字段在計算機中是以二進制形式存儲，所以做規則的匹配時，可以直接用二進制比較的方式進行查找。當從二進制運算角度來看待IP地址時，IP地址“54.112.26.127”是等效于“00110110 01110000 00011010 01111111”。如果采用通配符*表示既可為0又可為1，則通配符“**”可以代表“00”、“01”、“10”和“11”四種組合，這種方案可以使用特里樹結構來進行規則匹配。

當從整數運算角度來看待IP地址時，IP地址“54.112.26.127”又可以等效于數值“913316479”，這個數值的計算過程是(5424)+(11216)+(268)+127。當設置整數范圍段從913316476到913316479時，即可表示二進制形式中最后兩位為通配符“0011011001110000 00011010 011111**”。從集合分割的角度來看，規則能夠被映射到數學平面上。因而可以采用HiCuts等幾何分割方法來進行規則匹配。

我們發現從不同的角度來分析規則，會得到不同類型的解決方法。IP地址在設計時分為網絡號和主機號，網絡地址在分配時，是人為劃定網絡號范圍并分配到某個物理地區。而且路由器上的規則也是由人來配置并維護的，路由器上的規則集在長期的演進中，工程師會有意或無意的在規則集中加入一些社會網絡的特性。社會網絡的一個重要特點就是社區性，即社會網絡中一組具有相似性的節點可以構成一個社區，這個社區內的節點具有相同的特性。通過社區發現算法，能夠在網絡中找到具有共同特征的一組節點。所以我們從社區發現的角度來看待規則，對應到包分類的應用場景，規則就是網絡中的節點，而處理動作就是每個規則的一種特征，通過社區發現算法中的相似性比較，可以把具有相同處理動作的規則進行聚類。

當前在網絡數據包分類領域，提高數據包分類速度性能是最主要的研究點，但是隨著未來網絡的興起，包分類規則的更新也變得更頻繁。因此，為了適應未來網絡的發展，提出一種既能提高包分類速度，又能適應規則頻繁更新的包分類算法，具有重要的實際應用價值。

發明內容