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

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

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

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