快速過濾算法在手機上網(wǎng)加速網(wǎng)絡(luò)中的研究

申江云

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

【關(guān)鍵詞】 快速過濾算法 GPRS 緩存加速 UNIX

一、背景介紹

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

二、算法分析及介紹

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

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

具體說明如下：

步驟1：根據(jù)數(shù)據(jù)通信中的TCP/IP模型，按照數(shù)據(jù)中包含的網(wǎng)絡(luò)層、應(yīng)用層的相關(guān)數(shù)據(jù)，初始化形成成有粗到細的多維匹配規(guī)則樹；

步驟2：算法逐包分析串行數(shù)據(jù)數(shù)據(jù)包相應(yīng)的信息并開始進行規(guī)則樹匹配；

步驟3：數(shù)據(jù)包按照有粗到細的匹配樹逐層匹配相關(guān)的信息，直到最后一層；

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

三、算法的價值及優(yōu)點

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

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

參 考 文 獻

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

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

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

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