網路流量測量是網路監測、管理和控制的基礎,隨著網際網路的發展,網路行為變得越來越複雜,網路流量也越來越大,使直接對流量進行全面測量變得極為困難。
為解決這一問題,目前主要採用抽樣技術和哈希技術。其中,Bloom filter是最近逐漸在網路領域受到關注的一種高效的哈希結構,它對數據集合採用一個位串表示並能有效支持集合元素的哈希查找操作,以允許一定的誤稱率(false positive error)為代價,獲得很高的查找效率和很小的空間消耗。
此外,基於DCF(Dynamic Count filter)的資源可控流抽樣則是基於網路流級別的抽樣測量,DCF是Bloom filter的改進結構,支持多重集的元素頻率查詢。該方法對測量間隔內到達的報文進行固定數量的抽樣,並採用DCF哈希算法維護流記錄,從限制抽樣流樣本數和對抽樣流的處理兩方面來有效地控制資源消耗,抽樣率自適應實際流量變化而變化,並具有簡單性和準確性。
對於很多套用,了解長流就已足夠。長流是指報文數超過某個值的流,它占據了大部分網路流量但數量上相對較少。基於抽樣和Bloom filters的長流檢測,首先對報文進行抽樣,然後經過Bloom filters哈希運算,Bloom filters維護多個哈希函式降低了哈希衝突,在記憶體中用臨時表和流信息表來判斷到達閾值的流並維護其信息,滿足了高速網路環境下對長流檢測的要求,在保證測量精度的同時有效得控制了資源消耗。