快速過濾算法在手機上網加速網絡中的研究

申江云

【摘要】 傳統的包過濾技術一般是由多個過濾規則組成，這些規則在網絡設備內被有序地組織起來形成一個鏈表。當使用訪問控制列表來處理數據包時，網絡設備順序地查找該鏈表以發現匹配地條目。被匹配的條目用來決定對數據包的處理，在線性的查找過程中，平均查找時間與規則的大小成正比。傳統的算法在處理手機上網加速網絡海量數據小包時，存在處理時間長，不適應現有大數據分析的發展方向。

【關鍵詞】 快速過濾算法 GPRS 緩存加速 UNIX

一、背景介紹

雖然近年來中國移動在快速發展4G用戶，但是由于4G覆蓋不足和投資成本的制約，中國移動通過2G/3G上網用戶仍高達3億用戶，如何提升這部分用戶的感知？是擺在每個移動員工的迫切問題。通過分析低速網絡上網行為的特征，為提升用戶感知，河北移動搭建了手機上網緩存加速系統。隨著時間的推移，緩存的海量小包處理時間越來越長，迫切需要一種基于UNIX操作平臺的快速過濾算法提升整個緩存系統處理能力和效率。

二、算法分析及介紹

本文提出的快速過濾算法是一個高性能的報文分類算法， 本算法是其衍生出來的一個支持Unix內核框架包過濾模塊，由用戶態應用程序和內核態模塊組成，用于代替一般包過濾算法。本算法和一般包過濾算法對比起來，其優點主要在于分類規模很大時依然能夠保持較好的性能。

本算法基本上是將報文分類抽象為多維的范圍匹配問題，算法分為四個步驟如圖1所示。

具體說明如下：

步驟1：根據數據通信中的TCP/IP模型，按照數據中包含的網絡層、應用層的相關數據，初始化形成成有粗到細的多維匹配規則樹；

步驟2：算法逐包分析串行數據數據包相應的信息并開始進行規則樹匹配；

步驟3：數據包按照有粗到細的匹配樹逐層匹配相關的信息，直到最后一層；

步驟4：從最后的匹配域中查找匹配規則，數據包有規則存儲到相應的位置，方便下一步查詢和使用。

三、算法的價值及優點

本算法沒有使用位圖，因為Unix不允許以空間換時間。沒有使用位圖，這是因為該算法不需要位圖 。Cisco包過濾算法則是并行的同時得到了所有匹配域值表的位圖，因此只要將它們AND，就能得到最終結果，原因在于UNIX并不是并行操作的，而是串行的，本算法對于每一個匹配域也有一個值表，由于一系列的匹配域按照一定的順序排列好，比如：源地址-目的地址-協議-源端口-目的端口，因此其值表也有這樣的串接關系，如下：

在找到目的地址的匹配之前，是不會匹配協議以及后面的匹配域的。具體的規則掛接在最后的匹配域值表中。本算法沒有保留原始的配置規則，然后通過位圖找到它們，而是直接將規則掛在了它“應該在”的位置。

參 考 文 獻

[1]劉胤，楊世平，二種基于RFC算法的快速多維數據包分類算法，計算機工程，2008年第6期。

[2]王嫣然，陳梅，王翰虎，張鑫，一種基于內容過濾的科技文獻推薦算法，計算機技術與發展， 2011， 21（2）：66-69

[3]白麗君，基于內容和協作的科技文獻過濾方法研究，山西大學學，2013

[4]范立新，用位并行法進行過濾的中文近似串匹配算法，浙江大學，2006