申江云

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

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

一、背景介紹

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

二、算法分析及介紹

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

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

具體說明如下：

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

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

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

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

三、算法的價(jià)值及優(yōu)點(diǎn)

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

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

參 考 文 獻(xiàn)

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

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

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

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