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

1、    快速過(guò)濾算法在手機(jī)上網(wǎng)加速網(wǎng)絡(luò)中的研究    申江云【摘要】 傳統(tǒng)的包過(guò)濾技術(shù)一般是由多個(gè)過(guò)濾規(guī)則組成，這些規(guī)則在網(wǎng)絡(luò)設(shè)備內(nèi)被有序地組織起來(lái)形成一個(gè)鏈表。當(dāng)使用訪問(wèn)控制列表來(lái)處理數(shù)據(jù)包時(shí)，網(wǎng)絡(luò)設(shè)備順序地查找該鏈表以發(fā)現(xiàn)匹配地條目。被匹配的條目用來(lái)決定對(duì)數(shù)據(jù)包的處理，在線性的查找過(guò)程中，平均查找時(shí)間與規(guī)則的大小成正比。傳統(tǒng)的算法在處理手機(jī)上網(wǎng)加速網(wǎng)絡(luò)海量數(shù)據(jù)小包時(shí)，存在處理時(shí)間長(zhǎng)，不適應(yīng)現(xiàn)有大數(shù)據(jù)分析的發(fā)展方向?！娟P(guān)鍵詞】 快速過(guò)濾算法 gprs 緩存加速 unix一、背景介紹雖然近年來(lái)中國(guó)移動(dòng)在快速發(fā)展4g用戶，但是由于4g覆蓋不足和投資成本的制

2、約，中國(guó)移動(dòng)通過(guò)2g/3g上網(wǎng)用戶仍高達(dá)3億用戶，如何提升這部分用戶的感知？是擺在每個(gè)移動(dòng)員工的迫切問(wèn)題。通過(guò)分析低速網(wǎng)絡(luò)上網(wǎng)行為的特征，為提升用戶感知，河北移動(dòng)搭建了手機(jī)上網(wǎng)緩存加速系統(tǒng)。隨著時(shí)間的推移，緩存的海量小包處理時(shí)間越來(lái)越長(zhǎng)，迫切需要一種基于unix操作平臺(tái)的快速過(guò)濾算法提升整個(gè)緩存系統(tǒng)處理能力和效率。二、算法分析及介紹本文提出的快速過(guò)濾算法是一個(gè)高性能的報(bào)文分類算法， 本算法是其衍生出來(lái)的一個(gè)支持unix內(nèi)核框架包過(guò)濾模塊，由用戶態(tài)應(yīng)用程序和內(nèi)核態(tài)模塊組成，用于代替一般包過(guò)濾算法。本算法和一般包過(guò)濾算法對(duì)比起來(lái)，其優(yōu)點(diǎn)主要在于分類規(guī)模很大時(shí)依然能夠保持較好的性能。本算法基本上是將

3、報(bào)文分類抽象為多維的范圍匹配問(wèn)題，算法分為四個(gè)步驟如圖1所示。具體說(shuō)明如下：步驟1：根據(jù)數(shù)據(jù)通信中的tcp/ip模型，按照數(shù)據(jù)中包含的網(wǎng)絡(luò)層、應(yīng)用層的相關(guān)數(shù)據(jù)，初始化形成成有粗到細(xì)的多維匹配規(guī)則樹(shù)；步驟2：算法逐包分析串行數(shù)據(jù)數(shù)據(jù)包相應(yīng)的信息并開(kāi)始進(jìn)行規(guī)則樹(shù)匹配；步驟3：數(shù)據(jù)包按照有粗到細(xì)的匹配樹(shù)逐層匹配相關(guān)的信息，直到最后一層；步驟4：從最后的匹配域中查找匹配規(guī)則，數(shù)據(jù)包有規(guī)則存儲(chǔ)到相應(yīng)的位置，方便下一步查詢和使用。三、算法的價(jià)值及優(yōu)點(diǎn)本算法沒(méi)有使用位圖，因?yàn)閡nix不允許以空間換時(shí)間。沒(méi)有使用位圖，這是因?yàn)樵撍惴ú恍枰粓D 。cisco包過(guò)濾算法則是并行的同時(shí)得到了所有匹配域值表的位圖，因

4、此只要將它們and，就能得到最終結(jié)果，原因在于unix并不是并行操作的，而是串行的，本算法對(duì)于每一個(gè)匹配域也有一個(gè)值表，由于一系列的匹配域按照一定的順序排列好，比如：源地址-目的地址-協(xié)議-源端口-目的端口，因此其值表也有這樣的串接關(guān)系，如下：在找到目的地址的匹配之前，是不會(huì)匹配協(xié)議以及后面的匹配域的。具體的規(guī)則掛接在最后的匹配域值表中。本算法沒(méi)有保留原始的配置規(guī)則，然后通過(guò)位圖找到它們，而是直接將規(guī)則掛在了它“應(yīng)該在”的位置。參 考 文 獻(xiàn)1劉胤，楊世平，二種基于rfc算法的快速多維數(shù)據(jù)包分類算法，計(jì)算機(jī)工程，2008年第6期。2王嫣然，陳梅，王翰虎，張?chǎng)?，一種基于內(nèi)容過(guò)濾的科技文獻(xiàn)推薦算法，計(jì)算機(jī)技術(shù)與發(fā)展， 2011， 21（2）：66-693白麗君，基于內(nèi)容和協(xié)作的科技文獻(xiàn)過(guò)濾方法研究，山西大學(xué)學(xué)，20134范立新，用位并行法進(jìn)行過(guò)濾的中文近似串匹配算法，浙江大學(xué)，2006中國(guó)新通信2016年9期中國(guó)新通信的其它文章網(wǎng)絡(luò)與通信技術(shù)在計(jì)算機(jī)控制中的運(yùn)用分析信息化建設(shè)對(duì)醫(yī)院發(fā)展的重要性基于lin