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

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

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

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