高性能內(nèi)容過(guò)濾與分發(fā)技術(shù)研究.pdf

1、隨著網(wǎng)絡(luò)帶寬和業(yè)務(wù)流量的迅猛增長(zhǎng),數(shù)據(jù)包內(nèi)容過(guò)濾技術(shù)面臨高性能挑戰(zhàn),即如何滿(mǎn)足深度數(shù)據(jù)包檢測(cè)(Deep Packet Inspection,DPI)的線(xiàn)速處理和低存儲(chǔ)空間需求。隨著網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大、節(jié)點(diǎn)呈現(xiàn)出動(dòng)態(tài)性和異構(gòu)性,P2P內(nèi)容分發(fā)技術(shù)面臨高性能挑戰(zhàn),即如何在大規(guī)模網(wǎng)絡(luò)中實(shí)現(xiàn)高效、健壯和可伸縮的內(nèi)容分發(fā)。本文研究高性能數(shù)據(jù)包內(nèi)容過(guò)濾技術(shù),探討如何折衷考慮DPI的時(shí)間和空間需求；研究高性能P2P內(nèi)容分發(fā)技術(shù),探討如何折衷考慮內(nèi)容分發(fā)

2、的效率、公平性和負(fù)載均衡等。
　　 (1)高性能數(shù)據(jù)包內(nèi)容過(guò)濾技術(shù)包括基于硬件的數(shù)據(jù)包預(yù)處理方法和特征匹配算法:
　　 快速哈希表存在更新開(kāi)銷(xiāo)高和片外存儲(chǔ)空間需求大等問(wèn)題。本文提出了一種基于雙計(jì)數(shù)布魯姆過(guò)濾器的哈希表(Double-counter Bloom filtered Hash Table,DBHT)。雙計(jì)數(shù)布魯姆過(guò)濾器采用插入和刪除計(jì)數(shù)器,分別記錄每個(gè)存儲(chǔ)桶中插入和刪除的元素個(gè)數(shù)。實(shí)驗(yàn)結(jié)果表明,DBHT是一種時(shí)

3、空高效的哈希表,即顯著減少更新操作的片外存儲(chǔ)器訪(fǎng)問(wèn)次數(shù)和片外元素個(gè)數(shù),僅需要增加少量片上存儲(chǔ)空間大小。
　　 特里位圖內(nèi)容分析器存在更新開(kāi)銷(xiāo)高和假陽(yáng)性訪(fǎng)問(wèn)次數(shù)多等問(wèn)題,而共享節(jié)點(diǎn)快速哈希表存在更新開(kāi)銷(xiāo)高和存儲(chǔ)空間需求大等問(wèn)題。本文提出了一種索引拆分布魯姆過(guò)濾器(Index-Split Bloom Filten,ISBF)。在ISBF中,元素的片外索引值被拆分成多組比特,每組比特采用多個(gè)片上并行計(jì)數(shù)布魯姆過(guò)濾器表示元素集。為了降低

4、ISBF的更新開(kāi)銷(xiāo),本文又提出了懶惰刪除算法和空缺插入算法。實(shí)驗(yàn)結(jié)果表明,ISBF支持快速和存儲(chǔ)高效的查找,即顯著減少片外存儲(chǔ)器訪(fǎng)問(wèn)次數(shù)、處理時(shí)間以及片上和片外存儲(chǔ)空間需求。
　　 比特拆分字符串匹配算法存在不必要的狀態(tài)遷移問(wèn)題。本文提出了一種字節(jié)過(guò)濾字符串匹配算法(Byte-Filtered String Matching Algorithm),即在比特拆分字符串匹配之前,采用布魯姆過(guò)濾器預(yù)處理數(shù)據(jù)包內(nèi)容的每個(gè)讀入字符。實(shí)驗(yàn)結(jié)

5、果表明,與比特拆分算法相比,字節(jié)過(guò)濾算法減少了字符串匹配時(shí)間和狀態(tài)遷移次數(shù),從而提高了DPI的吞吐量。
　　 擴(kuò)展有限自動(dòng)機(jī)是在狀態(tài)上增加輔助變量及操作指令,從狀態(tài)方面減少正則表達(dá)式匹配的存儲(chǔ)空間需求。本文提出了一種基于緊湊型有限自動(dòng)機(jī)(CompactFinite Automaton,CFA)的正則表達(dá)式匹配算法,從遷移邊方面進(jìn)一步減少存儲(chǔ)空間需求。CFA采用基于優(yōu)先級(jí)的遷移邊壓縮方法,壓縮相同目的狀態(tài)最多的遷移邊;采用基于位圖

6、的遷移邊查找方法,并行查找不同優(yōu)先級(jí)的遷移邊子集。實(shí)驗(yàn)結(jié)果表明,CFA顯著減少遷移邊條數(shù)和存儲(chǔ)空間大小,且在匹配時(shí)間上與擴(kuò)展有限自動(dòng)機(jī)基本相同。
　　 (2)高性能P2P內(nèi)容分發(fā)技術(shù)包括BitTorrent性能優(yōu)化方法和基于DHT的負(fù)載均衡廣播算法:
　　 BitTorrent的上傳節(jié)點(diǎn)和請(qǐng)求節(jié)點(diǎn)之間存在“供需悖論”問(wèn)題。本文提出了一種基于動(dòng)態(tài)配額(Dynamic Quota)的節(jié)點(diǎn)選擇策略,即按照投資收益原則,上傳節(jié)點(diǎn)

7、動(dòng)態(tài)地分配。TFT算法和OU算法的上傳配額。實(shí)驗(yàn)結(jié)果表明,基于動(dòng)態(tài)配額的節(jié)點(diǎn)選擇策略是一種效率和公平折衷的方法,即以多上傳部分文件塊為代價(jià)來(lái)提高BitTorrent的下載效率。分析自私節(jié)點(diǎn)的搭便車(chē)(FteeRiding)對(duì)BitTorrent性能、公平性和健壯性的影響。本文提出了一種基于活躍度(Activeness)的種子節(jié)點(diǎn)阻塞算法,即定義請(qǐng)求節(jié)點(diǎn)的可用下載帶寬和可用上傳帶寬的比值為活躍度,種子節(jié)點(diǎn)優(yōu)先選擇活躍度高的請(qǐng)求節(jié)點(diǎn)來(lái)上傳文件

8、塊。實(shí)驗(yàn)結(jié)果表明,基于活躍度的種子節(jié)點(diǎn)阻塞算法不僅抑制自私節(jié)點(diǎn)的搭便車(chē),而且提高良性節(jié)點(diǎn)的性能,從而增強(qiáng)了BitTorrent健壯性。
　　 已有的基于DHT的廣播算法是利用貪婪的指針路由算法來(lái)構(gòu)建分布式廣播樹(shù),存在可伸縮性差和負(fù)載不均衡等問(wèn)題。本文提出了兩種基于DHT的輕量級(jí)廣播算法。當(dāng)節(jié)點(diǎn)標(biāo)識(shí)符空間是均勻分布時(shí),提出了基于令牌(Token)的廣播算法,即每個(gè)節(jié)點(diǎn)根據(jù)令牌值從指針節(jié)點(diǎn)中選擇其孩子節(jié)點(diǎn);當(dāng)節(jié)點(diǎn)標(biāo)識(shí)符空間是任意分布