流量測(cè)量系統(tǒng)中基于特定流的流匹配算法研究.pdf

1、下一代網(wǎng)絡(luò)(NGN)將是以IP為核心的高速網(wǎng)絡(luò)。由于IP網(wǎng)絡(luò)固有的缺陷，其QoS得不到很好保證。通過對(duì)網(wǎng)絡(luò)中的流量進(jìn)行準(zhǔn)確測(cè)量，并以此為依據(jù)進(jìn)行網(wǎng)絡(luò)控制和管理，可以顯著提高網(wǎng)絡(luò)的QoS。然而，在高速網(wǎng)絡(luò)中，要想測(cè)量全部的流幾乎是不可能的。目前，基于特定流的流量測(cè)量已成為高速網(wǎng)絡(luò)流量測(cè)量的一個(gè)新的研究方向。因此流匹配算法是對(duì)高速網(wǎng)絡(luò)中特定流進(jìn)行準(zhǔn)確測(cè)量的關(guān)鍵。 目前可用于流匹配的算法有很多。論文對(duì)多種IP數(shù)據(jù)包分類算法進(jìn)行了較為全

2、面的分析比較。通過研究，我們發(fā)現(xiàn)遞歸流分類(RFC)算法的分類速度較快，且適合于硬件實(shí)現(xiàn)，它的最大缺點(diǎn)是內(nèi)存消耗大。研究還發(fā)現(xiàn)Hash算法用于流匹配具有預(yù)處理時(shí)間短、內(nèi)存消耗低、支持匹配規(guī)則數(shù)多等優(yōu)點(diǎn)，但常規(guī)的Hash算法用于流匹配時(shí)沖突率較高。 論文針對(duì)RFC算法的不足，提出了一種多階段無沖突歸并(MPNCM)流匹配算法。MPNCM流匹配算法采用標(biāo)記桶實(shí)現(xiàn)最長(zhǎng)前綴匹配，用最小區(qū)間劃分進(jìn)行范圍匹配，同時(shí)增加了提前丟包的處理。該算

3、法在平均匹配速度和內(nèi)存消耗上優(yōu)于RFC算法。由于MPNCM內(nèi)存消耗仍然較大且不能支持較大的匹配規(guī)則集，論文又進(jìn)一步研究了Hash算法，提出了一種隨機(jī)矩陣映射(SMM)Hash算法。SMMHash算法采用了隨機(jī)矩陣映射，使計(jì)算出的Hash關(guān)鍵值服從均勻分布且能減少自相關(guān)沖突，因此該算法在沖突率、匹配時(shí)間等方面都優(yōu)于常規(guī)Hash算法，并且支持的匹配規(guī)則數(shù)可達(dá)5萬條以上。 MPNCM算法和SMMHash算法具有不同的應(yīng)用場(chǎng)合，MPNC