流量測(cè)量的關(guān)鍵技術(shù)分析與研究

摘 要:流量測(cè)量在流量計(jì)費(fèi)、網(wǎng)絡(luò)資源優(yōu)化和異常檢測(cè)等方面有廣泛的應(yīng)用。針對(duì)傳統(tǒng)的流量測(cè)量模型缺乏可擴(kuò)展性的缺點(diǎn)，提出了一種適用于高速網(wǎng)絡(luò)的可擴(kuò)展的流量測(cè)量模型。該模型采用報(bào)文分批處理的思想引入了兩級(jí)緩沖區(qū)結(jié)構(gòu)，使得緩存報(bào)文和流量統(tǒng)計(jì)兩個(gè)過(guò)程同時(shí)進(jìn)行。基于此模型，抽象了流量測(cè)量的兩大關(guān)鍵技術(shù)，即流量抽樣測(cè)量技術(shù)和概要數(shù)據(jù)結(jié)構(gòu)。運(yùn)用此模型進(jìn)行高速網(wǎng)絡(luò)的流量測(cè)量，不僅會(huì)降低資源的需求、提高分析的速度，而且還不會(huì)失去準(zhǔn)確性。

關(guān)鍵詞:流量測(cè)量; 兩級(jí)緩沖區(qū)結(jié)構(gòu); 抽樣測(cè)量; 概要數(shù)據(jù)結(jié)構(gòu)

中圖分類(lèi)號(hào):TP393文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2009)09-3442-06

doi:10.3969/j.issn.1001-3695.2009.09.068

Analysis and research on key techniques of traffic measurement

ZHANG Zhen， WANG Bin-qiang， ZHU Ke

(National Digital Switching System Engineering Technology R D Center， Zhengzhou 450002， China)

Abstract:Traffic measurement is an important component of network applications including usage-based charging， network optimization and anomaly detection. Based on the research of three typical flow mea-surement techniques， this paper presented a novel scalable flow measurement model deployed in high-speed network to circumvent the deficiency of traditional flow measurement model. Introducing the idea of processing in batches， the model designd two-stage buffer structure to conduct buffering packets and measuring traffic simultaneously. Referred flow sampling technique and referred synopsis data structure as two key techniques in the light of the above model. Implementing the model to measure traffic can not only meet the demand of resources， but also improve the analytical speed without sacrificing accuracy.

Key words:traffic measurement; two-stage buffer structure; sampling measurement; synopsis data structure

0 引言

隨著Internet重要性的日益提高和網(wǎng)絡(luò)結(jié)構(gòu)的日益復(fù)雜，越來(lái)越有必要對(duì)網(wǎng)絡(luò)的整體拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)行為和整個(gè)網(wǎng)絡(luò)的業(yè)務(wù)組進(jìn)行深入分析，以利于發(fā)現(xiàn)網(wǎng)絡(luò)瓶頸，優(yōu)化網(wǎng)絡(luò)配置，并進(jìn)一步發(fā)現(xiàn)網(wǎng)絡(luò)中可能存在的潛在危險(xiǎn)。為此，需要對(duì)大規(guī)模的網(wǎng)絡(luò)流量進(jìn)行統(tǒng)計(jì)、分析和測(cè)量，并根據(jù)網(wǎng)絡(luò)流量的變化分析網(wǎng)絡(luò)的性能，為加強(qiáng)網(wǎng)絡(luò)管理、提高網(wǎng)絡(luò)利用率、防范大規(guī)模網(wǎng)絡(luò)攻擊提供技術(shù)平臺(tái)。高速網(wǎng)絡(luò)流量測(cè)量已成為學(xué)術(shù)界、企業(yè)界和國(guó)家政府部門(mén)普遍關(guān)心的重要問(wèn)題。目前，高速網(wǎng)絡(luò)流量測(cè)量主要有兩種方法:

a)主動(dòng)測(cè)量技術(shù)。該方法是為了監(jiān)測(cè)兩指定端點(diǎn)之間的性能而向網(wǎng)絡(luò)中注入流量的方法。主動(dòng)意味著測(cè)量過(guò)程中產(chǎn)生新的網(wǎng)絡(luò)流量。主動(dòng)流量可以引起網(wǎng)絡(luò)部件的特殊響應(yīng)(如traceroute)，也可以用于觀測(cè)網(wǎng)絡(luò)的性能(如treno)。主動(dòng)測(cè)量給網(wǎng)絡(luò)增加了潛在的網(wǎng)絡(luò)負(fù)載，附加的流量可能會(huì)擾亂網(wǎng)絡(luò)，影響分析結(jié)果。例如，為了測(cè)量在IP網(wǎng)絡(luò)中瓶頸鏈路的帶寬，定期地向網(wǎng)絡(luò)發(fā)送巨大的TCP傳輸，由此產(chǎn)生的附加流量可能會(huì)引起Heisenberg效應(yīng)，并使測(cè)量的網(wǎng)絡(luò)吞吐量低于實(shí)際的瓶頸鏈路的帶寬。

b)被動(dòng)測(cè)量技術(shù)。該方法是從網(wǎng)絡(luò)中的某一點(diǎn)收集流量信息，如使用路由器或交換機(jī)收集數(shù)據(jù)，或者使用一個(gè)獨(dú)立的探針設(shè)備被動(dòng)地監(jiān)測(cè)網(wǎng)絡(luò)鏈路的流量。被動(dòng)測(cè)量可以完全取消附加流量和Heisenberg效應(yīng)，這些優(yōu)點(diǎn)使得被動(dòng)測(cè)量技術(shù)越來(lái)越受到重視，在實(shí)際應(yīng)用中也越來(lái)越廣泛。被動(dòng)測(cè)量獲得的數(shù)據(jù)是一些大小不一的分組信息，可以用來(lái)進(jìn)行各種流量分析，如總體流量中各種業(yè)務(wù)所占比重、業(yè)務(wù)分組的大小分布、分組的時(shí)間間隔和詳細(xì)的流量矩陣信息等，這些能為下一代互聯(lián)網(wǎng)的設(shè)計(jì)提供幫助。本文主要對(duì)應(yīng)用廣泛的被動(dòng)流量測(cè)量技術(shù)進(jìn)行了詳細(xì)探討。

鏈路帶寬的快速增長(zhǎng)和網(wǎng)絡(luò)流量的急劇膨脹給流量測(cè)量帶來(lái)了極大的挑戰(zhàn):處理器資源的大量消耗導(dǎo)致路由器整體性能的下降;產(chǎn)生的海量數(shù)據(jù)將占有大部分存儲(chǔ)器的資源;輸出的流量記錄占用大量的傳輸帶寬。而流量抽樣測(cè)量技術(shù)的引入是一種可擴(kuò)展的解決方案，即將抽樣技術(shù)用于高速網(wǎng)絡(luò)流量測(cè)量，可以在滿足測(cè)量精度的條件下，減少用于測(cè)量、存儲(chǔ)和處理的數(shù)據(jù)量。網(wǎng)絡(luò)流量的抽樣測(cè)量主要解決了如下問(wèn)題:

a)降低了資源的需求。采用流量抽樣測(cè)量的方法，由于僅需要處理整體流量中的抽樣樣本，這不僅降低了對(duì)CPU資源的需求，同時(shí)也降低了存儲(chǔ)流量信息的空間。

b)提高了分析的速度。在對(duì)采樣的報(bào)文進(jìn)行分析時(shí)，抽樣測(cè)量的樣本比整體的流量總量要少得多，因此，數(shù)據(jù)總量的減少，對(duì)這些數(shù)據(jù)的維護(hù)和分析也更加容易，特別是在進(jìn)行離線分析時(shí)，能夠在很大程度上提高分析處理的速度。

流量抽樣測(cè)量的方法主要分為兩種:

a)通過(guò)采樣流經(jīng)鏈路的分組來(lái)進(jìn)行的流量測(cè)量。它能夠支持廣泛的分析和應(yīng)用，但可擴(kuò)展性較差。

b)流(flow)級(jí)別的抽樣測(cè)量。它既能提供詳細(xì)的流量信息，又具備一定的可擴(kuò)展性，因而受到廣泛的關(guān)注并得到大量應(yīng)用。

本文主要研究第二種方法，即流級(jí)別的抽樣測(cè)量。本文抽象了傳統(tǒng)的流量測(cè)量模型，針對(duì)傳統(tǒng)流量測(cè)量模型的缺點(diǎn)，建立了適用于高速網(wǎng)絡(luò)的可擴(kuò)展的流量測(cè)量模型，并以該模型為基礎(chǔ)，深入分析高速網(wǎng)絡(luò)流量測(cè)量的兩大關(guān)鍵技術(shù)。

1 傳統(tǒng)的流量測(cè)量模型

為了更加有針對(duì)性地解決高速網(wǎng)絡(luò)中流量測(cè)量面臨的可擴(kuò)展性挑戰(zhàn)，需要抽象高速網(wǎng)絡(luò)流量測(cè)量的模型，把復(fù)雜的流量測(cè)量問(wèn)題形象化、模塊化和具體化，以便提煉出針對(duì)各個(gè)流量測(cè)量模塊的關(guān)鍵技術(shù)。因此，本章針對(duì)傳統(tǒng)流量測(cè)量模型面臨的挑戰(zhàn)，建立了高速網(wǎng)絡(luò)流量測(cè)量的模型，以便實(shí)時(shí)在線地處理大規(guī)模的流量數(shù)據(jù)。

傳統(tǒng)的流量測(cè)量模型就是為每條活動(dòng)的數(shù)據(jù)流維護(hù)一個(gè)狀態(tài)信息，并逐包更新，如圖1所示。數(shù)據(jù)流指的是一組具有相同流標(biāo)志，并且相鄰兩者的到達(dá)時(shí)間間隔不超過(guò)某一上限的一組數(shù)據(jù)包的集合。不同的應(yīng)用可以定義不同的流標(biāo)志，一般采用熟知的五元組(〈源IP地址、目的IP地址、協(xié)議類(lèi)型、源端口號(hào)、目的端口號(hào)〉)作為流標(biāo)志(flow_ID)。

歸并數(shù)據(jù)流指將一組具有相同屬性的數(shù)據(jù)合成一條流記錄。由于一次網(wǎng)絡(luò)會(huì)話由一條或多條數(shù)據(jù)流組成，數(shù)據(jù)流級(jí)的歸并成為一種自然的選擇。數(shù)據(jù)流級(jí)的歸并在數(shù)據(jù)約簡(jiǎn)幅度與信息保存率之間取得了良好的折中，并且被Cisco、Juniper等主要網(wǎng)絡(luò)設(shè)備制造商所支持。一般歸并后形成的流記錄包含流標(biāo)志、流開(kāi)始時(shí)間、流結(jié)束時(shí)間、流量大小等。

在高速骨干網(wǎng)絡(luò)鏈路上，傳統(tǒng)的流量測(cè)量方法由于實(shí)現(xiàn)代價(jià)極高而在實(shí)際應(yīng)用中不可行。這主要是由于:a)骨干網(wǎng)鏈路數(shù)據(jù)率高，報(bào)文的到達(dá)時(shí)間小(如在OC-192高速鏈路上，傳輸一個(gè)40 Byte的數(shù)據(jù)包只需32 ns)，因此，為了對(duì)流狀態(tài)進(jìn)行逐包更新，必須采用高速存儲(chǔ)器(static random access memory，SRAM)來(lái)存儲(chǔ)流狀態(tài)信息，此外，還需要專(zhuān)用硬件如內(nèi)容尋址的存儲(chǔ)器(CAM)完成從流標(biāo)志到流狀態(tài)空間地址的映射;b)骨干鏈路網(wǎng)鏈路上并發(fā)流的數(shù)量巨大，常常達(dá)到0.5～1 MB[1]，這就需要保存流狀態(tài)的SRAM以及從流標(biāo)志到流狀態(tài)空間地址的映射的CAM容量足夠大。可見(jiàn)，在高速骨干鏈路上，采用傳統(tǒng)的流處理的方法需要大容量的高速存儲(chǔ)器。

存儲(chǔ)器的速度和容量是一對(duì)矛盾的性能指標(biāo)，速度快的存儲(chǔ)器其容量小，如當(dāng)前主流的SRAM容量為18 Mbps，高端的CAM容量為512×80 bit[2];而容量大的存儲(chǔ)器如DRAM，其速度較慢。此外，由于網(wǎng)絡(luò)流量的增長(zhǎng)速率遠(yuǎn)高于存儲(chǔ)器性能的提高速率，傳統(tǒng)的流量測(cè)量方法不具備可擴(kuò)展性。

2 可擴(kuò)展的流量測(cè)量模型

區(qū)別于傳統(tǒng)的流量測(cè)量模型，高速網(wǎng)絡(luò)中的流量數(shù)據(jù)模型具有以下四點(diǎn)共性:a)數(shù)據(jù)流實(shí)時(shí)到達(dá);b)數(shù)據(jù)流到達(dá)次序獨(dú)立，不受應(yīng)用系統(tǒng)所控制;c)數(shù)據(jù)流規(guī)模宏大且不能預(yù)知其最大值;d)數(shù)據(jù)流一經(jīng)處理，除非特意保存，否則不能被再次取出處理，或者再次提取數(shù)據(jù)代價(jià)昂貴。

利用傳統(tǒng)的流量處理模型，必須將全部的流記錄信息存儲(chǔ)到介質(zhì)中，然后交給后端平臺(tái)獲取查詢結(jié)果。但是，由于數(shù)據(jù)規(guī)模宏大且到達(dá)速度很快，傳統(tǒng)技術(shù)難以滿足實(shí)時(shí)要求。為了更好地支持高速骨干網(wǎng)鏈路的流量統(tǒng)計(jì)和分析，下面抽象并建立了一種具有可擴(kuò)展性的流量測(cè)量的模型，能夠在測(cè)量收益與實(shí)現(xiàn)代價(jià)之間取得良好的折中。圖2給出了可擴(kuò)展的流量測(cè)量模型。該模型主要包括三個(gè)部分，即兩級(jí)緩沖區(qū)結(jié)構(gòu)、流量抽樣測(cè)量過(guò)程和概要數(shù)據(jù)結(jié)構(gòu)。

2.1 兩級(jí)緩沖區(qū)結(jié)構(gòu)[3]

對(duì)于流量測(cè)量任務(wù)來(lái)說(shuō)，測(cè)量緩沖區(qū)中只需存放分組頭部的某些域及其他相關(guān)統(tǒng)計(jì)信息。例如，分組頭部中的域有服務(wù)類(lèi)型(type of service，TOS)、總長(zhǎng)度(total length)、協(xié)議(protocol)、源IP地址、目的IP地址、源端口號(hào)、目的端口號(hào)、TCP的標(biāo)志比特(flag bit);其他統(tǒng)計(jì)信息有分組到達(dá)時(shí)的時(shí)間戳(用來(lái)計(jì)算流的起止時(shí)間)、每流字節(jié)數(shù)以及每流報(bào)文數(shù)等。

為了提高流量測(cè)量的效率，該模型采用報(bào)文分批處理的思想，使得緩存報(bào)文和流量統(tǒng)計(jì)兩個(gè)過(guò)程同時(shí)進(jìn)行，進(jìn)而提高流量測(cè)量的效率。為簡(jiǎn)單起見(jiàn)，緩沖區(qū)的設(shè)計(jì)如下:整個(gè)緩沖區(qū)由A與B兩部分組成，每部分可存放n個(gè)分組信息，只有當(dāng)緩沖區(qū)緩存的分組信息總數(shù)等于n時(shí)，才對(duì)該測(cè)量緩沖區(qū)進(jìn)行讀操作。

測(cè)量緩沖區(qū)緩存到達(dá)的數(shù)據(jù)報(bào)文過(guò)程如下:按照時(shí)間的先后順序?qū)B續(xù)到達(dá)的n個(gè)數(shù)據(jù)報(bào)文進(jìn)行分批處理，并對(duì)分批到達(dá)的數(shù)據(jù)報(bào)文進(jìn)行編號(hào)i=1，2，3，…，當(dāng)i(即第i批報(bào)文)為奇數(shù)時(shí)，從鏈路到達(dá)且需要緩存的分組信息進(jìn)入緩沖區(qū)A，而測(cè)量進(jìn)程從緩沖區(qū)B讀取信息(當(dāng)i=1時(shí)，B中無(wú)報(bào)文信息);當(dāng)i為偶數(shù)時(shí)，從線路到達(dá)且需要緩存的分組信息進(jìn)入緩沖區(qū)B，而流測(cè)量模塊從緩沖區(qū)A讀取信息。

由于兩級(jí)緩沖區(qū)對(duì)順序到達(dá)的數(shù)據(jù)報(bào)文進(jìn)行分批處理，即只需要緩存線速到達(dá)的n個(gè)分組信息，則相應(yīng)的存儲(chǔ)器也必須支持n個(gè)分組信息的線速存儲(chǔ)，緩沖區(qū)需要用靜態(tài)隨機(jī)訪問(wèn)存儲(chǔ)器SRAM來(lái)實(shí)現(xiàn)。對(duì)于能容納12 000個(gè)分組信息的緩沖區(qū)來(lái)說(shuō)，如果每個(gè)分組信息需要21 Byte，則最多需要3.85 Mbit的SRAM。根據(jù)當(dāng)前的半導(dǎo)體技術(shù)，提供這種大小的SRAM是可行的。

2.2 流量抽樣測(cè)量過(guò)程

高速網(wǎng)絡(luò)已成為網(wǎng)絡(luò)發(fā)展的必然趨勢(shì)，要支持高速網(wǎng)絡(luò)測(cè)量最直接也是最核心的目標(biāo)就是盡量減少測(cè)量設(shè)備的時(shí)間開(kāi)銷(xiāo)和數(shù)據(jù)存儲(chǔ)的空間開(kāi)銷(xiāo)，同時(shí)還要求達(dá)到一定的測(cè)量精度。解決此問(wèn)題的綜合辦法是引入具有可擴(kuò)展性的流量測(cè)量原理和算法。流量抽樣測(cè)量技術(shù)能夠很好地在測(cè)量收益與測(cè)量代價(jià)之間取得平衡，它是當(dāng)前網(wǎng)絡(luò)測(cè)量領(lǐng)域的一個(gè)研究熱點(diǎn)。

流量抽樣測(cè)量技術(shù)可以在滿足一定測(cè)量精度的前提下，一方面大大減少流量測(cè)量記錄文件的大小，另一方面也降低了測(cè)量過(guò)程對(duì)系統(tǒng)造成的負(fù)荷，更適宜于高速網(wǎng)絡(luò)中的實(shí)時(shí)流量統(tǒng)計(jì)和分析。主要從以下三個(gè)方面來(lái)衡量抽樣測(cè)量的性能:

a)準(zhǔn)確性。在互聯(lián)網(wǎng)的現(xiàn)有環(huán)境下，抽樣測(cè)量技術(shù)所面臨的首要問(wèn)題是準(zhǔn)確性。不準(zhǔn)確的流量測(cè)量不僅會(huì)達(dá)不到流量測(cè)量和流量監(jiān)控的目的，而且會(huì)引導(dǎo)網(wǎng)絡(luò)管理員作出錯(cuò)誤的決策。

b)自適應(yīng)性。為了使流量測(cè)量具有可擴(kuò)展性，應(yīng)該盡量避免過(guò)抽樣和欠抽樣。這就要求自適應(yīng)地動(dòng)態(tài)調(diào)整抽樣率(sampling rate)，避免測(cè)量時(shí)因抽樣率不可變而造成使用上的不便:高抽樣率會(huì)因過(guò)多消耗資源而引起系統(tǒng)整體性能的降低;低抽樣率因獲取樣本數(shù)量過(guò)少、總體信息缺失過(guò)多而造成分析結(jié)果誤差加大。

c)資源的可控性。由于流量變化比較頻繁，導(dǎo)致資源缺乏保護(hù)功能。特別是當(dāng)網(wǎng)絡(luò)受到泛洪攻擊時(shí)，大量有用資源被占用，引起系統(tǒng)整體功能的下降。尋求一種具有資源(處理器資源、存儲(chǔ)器資源等)保護(hù)功能的流量抽樣測(cè)量算法，使得系統(tǒng)資源不致于因網(wǎng)絡(luò)流量的急劇增大而被過(guò)度消耗，具有重要的研究意義。

2.3 概要數(shù)據(jù)結(jié)構(gòu)

該模型通過(guò)流量抽樣技術(shù)對(duì)高速網(wǎng)絡(luò)中的大規(guī)模數(shù)據(jù)流進(jìn)行快速處理，并實(shí)時(shí)更新保存在內(nèi)存中的概要數(shù)據(jù)結(jié)構(gòu)。概要數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)了數(shù)據(jù)流的統(tǒng)計(jì)特征，是對(duì)數(shù)據(jù)流的一種壓縮總結(jié)，借助于它無(wú)須對(duì)數(shù)據(jù)流進(jìn)行多遍掃描即可獲得誤差可控的近似結(jié)果。而且據(jù)此設(shè)計(jì)的處理算法同樣可適用于海量靜態(tài)數(shù)據(jù)的情況，當(dāng)數(shù)據(jù)可再次存取和掃描時(shí)，某些算法可獲得更加準(zhǔn)確的處理結(jié)果。

如圖2所示，當(dāng)一個(gè)無(wú)限的數(shù)據(jù)流序列快速流入時(shí)，要求在僅對(duì)數(shù)據(jù)集進(jìn)行一遍掃描的情況下，利用有限的存儲(chǔ)空間快速完成計(jì)算，以實(shí)時(shí)響應(yīng)用戶請(qǐng)求。因此，那些需要對(duì)靜態(tài)數(shù)據(jù)進(jìn)行多遍的傳統(tǒng)的處理模型和方法已不再適用，而只能用遠(yuǎn)小于數(shù)據(jù)流量規(guī)模的概要數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)數(shù)據(jù)流的實(shí)時(shí)連續(xù)處理。

由于概要數(shù)據(jù)結(jié)構(gòu)只能近似存儲(chǔ)流記錄信息，并且數(shù)據(jù)流的短暫易逝導(dǎo)致數(shù)據(jù)無(wú)法回溯(backtracking)，只能得到近似的處理結(jié)果。該流量測(cè)量模型的另一個(gè)關(guān)鍵技術(shù)在于設(shè)計(jì)一個(gè)遠(yuǎn)小于數(shù)據(jù)集規(guī)模的概要數(shù)據(jù)結(jié)構(gòu)，從而可以在高速緩存(SRAM)中處理數(shù)據(jù)。主要利用以下三個(gè)指標(biāo)來(lái)衡量概要數(shù)據(jù)結(jié)構(gòu)性能:

a)準(zhǔn)確性。通過(guò)流量的抽樣處理，獲得各個(gè)業(yè)務(wù)流的流量信息，并實(shí)時(shí)地對(duì)概要數(shù)據(jù)結(jié)構(gòu)進(jìn)行更新。只有對(duì)流量信息進(jìn)行一些變換運(yùn)算和處理(如hash變換和小波變換等)，才能獲得較好的信息壓縮效果。但在信息查詢和還原過(guò)程中，難免會(huì)存在信息的丟失或誤判。因此，準(zhǔn)確性是衡量概要數(shù)據(jù)結(jié)構(gòu)性能的一個(gè)重要方面。

b)空間利用率。在高速網(wǎng)絡(luò)流量測(cè)量中，由于存儲(chǔ)空間的限制，算法的空間利用率尤為重要，它是評(píng)價(jià)其性能優(yōu)劣的首要指標(biāo)。本文中的空間利用率定義為:每元素占用的存儲(chǔ)空間(bit/元素)。

c)計(jì)算復(fù)雜度。為了能夠?qū)崟r(shí)在線地流量測(cè)量，概要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)必須要支持流記錄的實(shí)時(shí)更新和在線查詢。計(jì)算復(fù)雜度定義為:每次更新或查詢操作中處理單元訪問(wèn)存儲(chǔ)單元的次數(shù)。因此，計(jì)算復(fù)雜度是影響流量測(cè)量效率的關(guān)鍵因素。

總之，高速網(wǎng)絡(luò)中流量測(cè)量的主要目標(biāo)就是設(shè)計(jì)單遍掃描算法(one-pass algorithm)，實(shí)時(shí)地給出滿足一定測(cè)量誤差要求的查詢結(jié)果。算法的關(guān)鍵在于數(shù)據(jù)流處理的相關(guān)算法(取數(shù)據(jù)的相關(guān)算法)和簡(jiǎn)潔高效的概要數(shù)據(jù)結(jié)構(gòu)(存數(shù)據(jù)的相關(guān)概要數(shù)據(jù)結(jié)構(gòu))。因此，基于可擴(kuò)展的流量測(cè)量模型，抽樣測(cè)量技術(shù)和概要數(shù)據(jù)結(jié)構(gòu)是高速網(wǎng)絡(luò)流量測(cè)量的兩大關(guān)鍵技術(shù)，本文第3章將分別詳細(xì)闡述這兩個(gè)關(guān)鍵技術(shù)。

3 高速網(wǎng)絡(luò)中流量測(cè)量的關(guān)鍵技術(shù)

3.1 抽樣測(cè)量技術(shù)

3.1.1 研究現(xiàn)狀

高速網(wǎng)絡(luò)中的流量抽樣測(cè)量技術(shù)是被動(dòng)測(cè)量的一種典型應(yīng)用形式。早在1989年，文獻(xiàn)[4]首先將抽樣測(cè)量技術(shù)引進(jìn)流量測(cè)量領(lǐng)域。1993年，Claffy系統(tǒng)研究了抽樣技術(shù)在流量統(tǒng)計(jì)和測(cè)量中的應(yīng)用，分析了簡(jiǎn)單隨機(jī)抽樣、系統(tǒng)抽樣和分層抽樣技術(shù)用于估計(jì)分組大小和分組到達(dá)時(shí)間[5]。自進(jìn)入21世紀(jì)以來(lái)，抽樣測(cè)量技術(shù)有了新的發(fā)展，比較有代表性的流量測(cè)量算法有:2002年，Estan[6]提出的“Sample and hold”和“Multistage filters”兩種大流檢測(cè)算法;文獻(xiàn)[7]研究了一種根據(jù)流大小建立不等概率的抽樣模型(sketch guided sampling ，SGS)。

1)Sample and hold[6]

Sample and hold算法的基本思想是:當(dāng)某個(gè)數(shù)據(jù)報(bào)文到達(dá)時(shí)，如果該報(bào)文所屬的流記錄在緩存中存在，則更新該流記錄;否則以一定概率p采樣該報(bào)文，若該報(bào)文被抽中，則創(chuàng)建該流記錄，如圖3所示。但是該抽樣測(cè)量方法不同于以往的采樣方法，對(duì)于在緩存中已經(jīng)有記錄的流，以后屬于該流的報(bào)文均被抽樣。該算法的錯(cuò)誤概率為1/M。其中M為算法所需的內(nèi)存，優(yōu)于傳統(tǒng)的隨機(jī)采樣方法(錯(cuò)誤概率為I(xiàn)/M)。

2)Multistage filters[6]

Multistage filters算法應(yīng)用多級(jí)過(guò)濾器:每級(jí)過(guò)濾器是一個(gè)計(jì)數(shù)器向量，每個(gè)報(bào)文到達(dá)時(shí)，通過(guò)hash函數(shù)映射到每級(jí)過(guò)濾器中的對(duì)應(yīng)計(jì)數(shù)器上，然后更新對(duì)應(yīng)計(jì)數(shù)器的值。如果每級(jí)相應(yīng)的計(jì)數(shù)器均超過(guò)了預(yù)設(shè)定的閾值，則認(rèn)為該流是大流，然后緩存該流，如圖4所示。

3)SGS算法

文獻(xiàn)[7]提出了草圖指導(dǎo)的抽樣算法SGS。SGS的核心思想是:設(shè)置包抽樣比為該數(shù)據(jù)包所屬數(shù)據(jù)流當(dāng)前流量的單調(diào)遞減函數(shù)。SGS抽樣算法通過(guò)犧牲長(zhǎng)流的包抽樣率以換取短流的包抽樣率，與隨機(jī)抽樣相比，在相同的包抽樣比下，SGS抽樣算法能獲取更詳細(xì)的流量信息。但SGS抽樣算法的缺點(diǎn)是需要實(shí)時(shí)獲知每條數(shù)據(jù)流的流量。

為了制定標(biāo)準(zhǔn)化的流量測(cè)量框架，2002年4月，IETF成立了兩個(gè)工作組，即PSAMP(packet sampling)和IPFIX(IP flow information export)。其任務(wù)是建立被動(dòng)方式的抽樣測(cè)量的標(biāo)準(zhǔn)，其標(biāo)準(zhǔn)需要可靠、詳細(xì)和實(shí)時(shí)地支持已有和未來(lái)的應(yīng)用，且在硬件設(shè)備中容易實(shí)現(xiàn)。而抽樣方法隨觸發(fā)抽樣事件的不同而不同，如由報(bào)文到達(dá)時(shí)間觸發(fā)(基于時(shí)間抽樣)、由報(bào)文在流中所處的位置觸發(fā)(基于數(shù)目抽樣)或由報(bào)文的內(nèi)容觸發(fā)(基于內(nèi)容抽樣)等;也隨抽樣策略的不同而不同，如隨機(jī)抽樣、系統(tǒng)抽樣和分層抽樣等。

3.1.2 事件觸發(fā)式抽樣

激發(fā)事件決定樣本開(kāi)始被抽樣的時(shí)刻和結(jié)束抽樣的時(shí)刻，因此激發(fā)事件決定抽樣的頻率和間距。目前，比較典型的事件觸發(fā)式抽樣主要有基于時(shí)間的觸發(fā)式抽樣、基于分組數(shù)目的觸發(fā)式抽樣和基于分組內(nèi)容的觸發(fā)式抽樣。

1)基于時(shí)間的觸發(fā)式抽樣

在基于時(shí)間的觸發(fā)式抽樣中，分組到達(dá)定時(shí)器的時(shí)間決定分組是否被抽樣，如每隔30 s開(kāi)始抽樣，持續(xù)測(cè)量10 s，然后停止測(cè)量。也就是說(shuō)，在這種抽樣方式的過(guò)程中，需要設(shè)定一個(gè)定時(shí)器來(lái)決定抽樣間隔的邊界。

2)基于分組數(shù)目的觸發(fā)式抽樣

根據(jù)分組到達(dá)計(jì)數(shù)器的數(shù)目激發(fā)開(kāi)始抽樣和結(jié)束抽樣，在抽樣過(guò)程中需要一個(gè)包計(jì)數(shù)器來(lái)決定抽樣間隔的邊界。

3)基于分組內(nèi)容的觸發(fā)式抽樣

文獻(xiàn)[8]提出基于掩碼匹配的抽樣方法，它是一種基于統(tǒng)計(jì)分析的全新的網(wǎng)絡(luò)流量抽樣測(cè)量算法。其核心思想是用確定的掩碼與IP報(bào)頭標(biāo)志字段的若干位進(jìn)行匹配，匹配成功則抽取該報(bào)文。基于掩碼匹配的抽樣方法不僅適用于集中式的測(cè)量環(huán)境中，也適用于分布式的測(cè)量環(huán)境中;不僅可用于一次抽樣，也可用于多次抽樣。

3.1.3 策略不同的抽樣

依據(jù)不同的抽樣策略，抽樣測(cè)量方法有很多種類(lèi)，但不同方法的估計(jì)量和精度、適用的場(chǎng)合都不同，需要分別進(jìn)行研究。比較常見(jiàn)的有以下幾種:

a)簡(jiǎn)單隨機(jī)抽樣。它是最簡(jiǎn)單的概率抽樣方法，也是其他抽樣方法的基礎(chǔ)。設(shè)抽樣概率為f，流量總體中的每個(gè)分組單元等概率地被抽取，并且每個(gè)分組被抽樣的事件是相互獨(dú)立的。在具體抽取樣本時(shí)，通過(guò)產(chǎn)生隨機(jī)數(shù)來(lái)決定分組的抽樣與否，如圖5(a)所示。

b)系統(tǒng)抽樣。它也稱(chēng)為等間距抽樣(或周期抽樣)，一般是事先定義抽樣概率為f，計(jì)算出最大抽樣間距L=[1/f]，然后從流量總體中等間距地抽取一個(gè)單元報(bào)文(每個(gè)間距內(nèi)抽取第一個(gè)報(bào)文)，如圖5(b)所示。系統(tǒng)抽樣簡(jiǎn)單易行，如果系統(tǒng)抽樣的樣本較為均勻地散于總體中，常有較好的代表性;如果網(wǎng)絡(luò)流量樣本分布并不均勻，或者存在周期性，則系統(tǒng)抽樣的分析結(jié)果將可能產(chǎn)生較大的估計(jì)偏差。

c)分層抽樣。就是按照某種規(guī)則(實(shí)際的流量測(cè)量中，把相近的分組單元?dú)w于一層)把流量總體劃分成若干層，然后在每一層內(nèi)再進(jìn)行抽樣，各層之間的抽樣是相互獨(dú)立的，如圖5(c)所示。特別地，如果每一層采取簡(jiǎn)單隨機(jī)抽樣的方法，則稱(chēng)為分層隨機(jī)抽樣。分層抽樣的估計(jì)是先在各層內(nèi)進(jìn)行，再由各層的估計(jì)量進(jìn)行加權(quán)平均或求和，從而得出總體的估計(jì)量。在實(shí)際的流量測(cè)量中，由于把總體流量分成了若干層，可以單獨(dú)對(duì)各層進(jìn)行抽樣處理，從而提高了抽樣測(cè)量的效率。分層抽樣在流量測(cè)量領(lǐng)域應(yīng)用最為廣泛。

3.2 概要數(shù)據(jù)結(jié)構(gòu)

布魯姆過(guò)濾器(Bloom filter)是一種精簡(jiǎn)的信息表示方案，是一種特殊的hash運(yùn)算結(jié)構(gòu)。布魯姆過(guò)濾器對(duì)集合采用一個(gè)位串向量表示，并能支持元素的散列查找，是一種能夠表示集合、支持集合查詢的空間簡(jiǎn)潔的數(shù)據(jù)結(jié)構(gòu)。由于布魯姆過(guò)濾器結(jié)構(gòu)具備了空間效率高、計(jì)算復(fù)雜度低、并行程度高等優(yōu)點(diǎn)，使之特別適合于硬件實(shí)現(xiàn)，具有很好的實(shí)用價(jià)值。

3.2.1 研究現(xiàn)狀

布魯姆過(guò)濾器的存儲(chǔ)和查詢算法一直是研究的熱點(diǎn)問(wèn)題。針對(duì)不同的應(yīng)用需求，布魯姆過(guò)濾器的結(jié)構(gòu)一直在不斷地改進(jìn)。計(jì)數(shù)型布魯姆過(guò)濾器結(jié)構(gòu)是一種比較經(jīng)典的結(jié)構(gòu)，它是基本布魯姆過(guò)濾器的一種擴(kuò)展形式，能夠支持元素的表示、查詢和統(tǒng)計(jì)計(jì)數(shù)。其中比較有代表性的計(jì)數(shù)型布魯姆過(guò)濾器有三種，即簡(jiǎn)單計(jì)數(shù)型布魯姆過(guò)濾器(naive counting Bloom filter，NCBF)、空碼布魯姆過(guò)濾器(space-code Bloom filter，SCBF)和d-left哈希函數(shù)構(gòu)建的計(jì)數(shù)型布魯姆過(guò)濾器(d-left counting Bloom filter， dlCBF)。

1)NCBF結(jié)構(gòu)

L. Fan等人[9]提出了簡(jiǎn)單計(jì)數(shù)型布魯姆過(guò)濾器NCBF。NCBF用一個(gè)計(jì)數(shù)器向量C取代了布魯姆過(guò)濾器的比特向量V。如圖6所示，當(dāng)向S中插入某個(gè)元素e時(shí)，將C(h1(e))，C(h2(e))，…，C(hk(e))+1;當(dāng)從S中刪除某個(gè)元素e時(shí)，將C(h1(e))，C(h2(e))，…，C(hk(e))-1。文獻(xiàn)[9]的分析表明，每個(gè)計(jì)數(shù)器的寬度設(shè)為4 bit，可保證計(jì)數(shù)器的溢出概率不大于1.37#8226;m#8226;10-15，對(duì)于大部分應(yīng)用而言，如此低的計(jì)數(shù)器溢出概率可以忽略不計(jì)。除了支持對(duì)集合S中元素的刪除操作外，NCBF還可以支持元素在S中的出現(xiàn)頻率查詢，或者稱(chēng)為計(jì)數(shù)查詢。

2)SCBF結(jié)構(gòu)

文獻(xiàn)[10]提出了空碼布魯姆過(guò)濾器SCBF用于高速骨網(wǎng)鏈路數(shù)據(jù)流的流量測(cè)量。SCBF的本質(zhì)是同時(shí)生成多個(gè)布魯姆過(guò)濾器，各個(gè)布魯姆過(guò)濾器有一組彼此獨(dú)立的哈希函數(shù)，但是共享比特向量V。向S中插入元素e時(shí)，隨機(jī)選擇一組哈希函數(shù)，設(shè)為hi1(e)，hi2(e)，…，hik(e)，置V(hi1(e))，V(hi2(e))，…，V(hik(e))為1。查詢某個(gè)元素e在S中的出現(xiàn)頻率時(shí)，需輪詢各個(gè)布魯姆過(guò)濾器，根據(jù)元素e在所有布魯姆過(guò)濾器中總的出現(xiàn)頻率來(lái)估計(jì)e的出現(xiàn)頻率。

SCBF區(qū)別于其他計(jì)數(shù)型布魯姆過(guò)濾器的一個(gè)顯著優(yōu)點(diǎn)在于其計(jì)算復(fù)雜度低。SCBF中，元素的插入過(guò)程只需對(duì)存儲(chǔ)單元進(jìn)行寫(xiě)操作即可，而無(wú)須向其他計(jì)數(shù)型布魯姆過(guò)濾器那樣進(jìn)行“讀—改—寫(xiě)”三步操作。SCBF的只寫(xiě)更新過(guò)程使得流水化的硬件實(shí)現(xiàn)成為可能，從而增加有效的提高計(jì)算效率。SCBF的缺陷在于:

a)由于過(guò)度犧牲了空間復(fù)雜度以換取低的計(jì)算復(fù)雜度，SCBF算法的空間復(fù)雜度過(guò)高，不適于基于FPGA實(shí)現(xiàn);

b)由于每次訪存只寫(xiě)1 bit，SCBF不能充分利用片外存儲(chǔ)器的帶寬[2];

c)SCBF只能支持線速更新而不能支持線速查詢。

3)dlCBF結(jié)構(gòu)

文獻(xiàn)[11]提出了一種采用d-left哈希函數(shù)構(gòu)建的計(jì)數(shù)型布魯姆過(guò)濾器。d-left哈希函數(shù)[12]是一種空間高效的哈希算法，其將存儲(chǔ)空間劃分為若干個(gè)塊，每塊包含若干個(gè)桶，每桶包含若干個(gè)桶單元，元素存放于桶單元中。例如，圖7中的d-left哈希函數(shù)的存儲(chǔ)區(qū)劃分為四個(gè)塊，每塊五個(gè)桶，每桶深度為4。當(dāng)插入元素e時(shí)，由d個(gè)獨(dú)立的哈希函數(shù)計(jì)算元素e在各個(gè)塊中的桶地址，分別記做h1(e)，h2(e)，… ，hd(e);然后，將e插入到BV1(h1(e))，BV2(h2(e))，…，BVd(hd(e))中負(fù)載最輕的那個(gè)桶中。如果存在多個(gè)負(fù)載最輕的桶，則選擇最左邊那個(gè)，如圖7所示，將元素e插入到桶BV1中。遵循上述選擇策略，可使得各個(gè)桶的負(fù)載較為平均，從而各個(gè)桶在平均負(fù)載的基礎(chǔ)上，再增加一個(gè)較小的額外桶空間，即可保證桶的溢出概率極低，從而有效地提高空間利用率[12]。

采用d-left哈希函數(shù)構(gòu)建計(jì)數(shù)型布魯姆過(guò)濾器時(shí)，在d-left哈希函數(shù)的各個(gè)桶單元中存放的內(nèi)容為元素指紋和元素頻率計(jì)數(shù)器，如圖7所示。dlCBF的優(yōu)點(diǎn)在于空間效率高。文獻(xiàn)[11]的結(jié)論表明，與NCBF相比，dlCBF的空間復(fù)雜度約為NCBF的一半;dlCBF的缺陷在于其計(jì)算復(fù)雜度比NCBF和SCBF略高。

3.2.2 應(yīng)用布魯姆過(guò)濾器進(jìn)行流量測(cè)量

最近10年，隨著網(wǎng)絡(luò)研究的發(fā)展以及新的覆蓋網(wǎng)絡(luò)和P2P網(wǎng)絡(luò)應(yīng)用技術(shù)的涌現(xiàn)，出現(xiàn)了基于布魯姆過(guò)濾器存儲(chǔ)和查詢算法的研究高潮，應(yīng)用于網(wǎng)絡(luò)的領(lǐng)域和方式越來(lái)越多，包括覆蓋網(wǎng)和P2P網(wǎng)節(jié)點(diǎn)協(xié)作交互、數(shù)據(jù)幀路由標(biāo)簽、網(wǎng)絡(luò)測(cè)量管理和網(wǎng)絡(luò)入侵檢測(cè)等網(wǎng)絡(luò)應(yīng)用領(lǐng)域。基于布魯姆過(guò)濾器的骨干網(wǎng)流量分析算法設(shè)計(jì)也成為當(dāng)前的一個(gè)研究熱點(diǎn)。例如，文獻(xiàn)[10]采用布魯姆過(guò)濾器用于高速骨干網(wǎng)的逐流流量測(cè)量;文獻(xiàn)[13]采用布魯姆過(guò)濾器構(gòu)建大規(guī)模并發(fā)狀態(tài)機(jī)。

圖8為應(yīng)用布魯姆過(guò)濾器進(jìn)行數(shù)據(jù)流處理的一般系統(tǒng)結(jié)構(gòu)模型，新到達(dá)的數(shù)據(jù)可能觸發(fā)更新操作或查詢操作，查詢請(qǐng)求將觸發(fā)查詢操作。更新操作指的是對(duì)于新到達(dá)的元素e，更新其在計(jì)數(shù)型布魯姆過(guò)濾器中的重?cái)?shù)計(jì)數(shù)值;查詢操作指的是讀取元素e在計(jì)數(shù)型布魯姆過(guò)濾器中的重?cái)?shù)計(jì)數(shù)值，并據(jù)此給出其重?cái)?shù)的估計(jì)值。需要指出的是，某些計(jì)數(shù)型布魯姆過(guò)濾器(如SCBF)的更新操作無(wú)須對(duì)存儲(chǔ)單元進(jìn)行讀操作，而僅僅進(jìn)行寫(xiě)操作。在高速骨干網(wǎng)流量分析等海量數(shù)據(jù)的高速處理場(chǎng)合中，處理單元通常由ASIC、FPGA或者專(zhuān)用CPU等高性能處理器件實(shí)現(xiàn);存儲(chǔ)單元通常由高速SRAM實(shí)現(xiàn)。

總之，本文應(yīng)用擴(kuò)展的布魯姆過(guò)濾器結(jié)構(gòu)作為業(yè)務(wù)流信息表示、查詢和統(tǒng)計(jì)的概要數(shù)據(jù)結(jié)構(gòu)，主要有以下原因:

a)布魯姆過(guò)濾器能快速地鑒別流的信息，并能把TCP流的信息維護(hù)從96 bit的五元組映射到很短的哈希串所代表的空間，極大地減少了由于維護(hù)五元組信息而帶來(lái)的資源開(kāi)銷(xiāo)。

b)由于統(tǒng)計(jì)業(yè)務(wù)流過(guò)程只需要一次hash映射計(jì)數(shù)以及hash函數(shù)的并行操作性，避免了蠻力地查找流緩存中相應(yīng)的流記錄是否存在，使得流量測(cè)量的計(jì)算復(fù)雜度大大降低。

c)應(yīng)用多維計(jì)數(shù)型布魯姆過(guò)濾器能夠?qū)崟r(shí)在線地支持多維業(yè)務(wù)流信息的表示、查詢和計(jì)數(shù)。

4 結(jié)束語(yǔ)

流量測(cè)量在流量計(jì)費(fèi)、網(wǎng)絡(luò)資源優(yōu)化和異常檢測(cè)等方面有廣泛的應(yīng)用。本文首先針對(duì)傳統(tǒng)的流量測(cè)量模型缺乏可擴(kuò)展性的缺點(diǎn)，提出了一種適用于高速網(wǎng)絡(luò)的可擴(kuò)展的流量測(cè)量模型;然后基于此模型，抽象了流量測(cè)量的兩大關(guān)鍵技術(shù)，即流量抽樣測(cè)量技術(shù)和概要數(shù)據(jù)結(jié)構(gòu);最后詳細(xì)討論了兩個(gè)關(guān)鍵技術(shù)的相關(guān)研究方法。

流量抽樣測(cè)量技術(shù)不僅可以在滿足一定測(cè)量精度的前提下，一方面大大減少流量測(cè)量記錄文件的大小，另一方面也降低了測(cè)量過(guò)程對(duì)系統(tǒng)造成的負(fù)荷，更適宜于高速網(wǎng)絡(luò)中的實(shí)時(shí)流量統(tǒng)計(jì)和分析。高效的概要數(shù)據(jù)結(jié)構(gòu)能夠在對(duì)數(shù)據(jù)集進(jìn)行一遍掃描的情況下，利用有限的存儲(chǔ)空間快速完成更新和查詢，以實(shí)時(shí)響應(yīng)用戶請(qǐng)求。布魯姆過(guò)濾器是一種精簡(jiǎn)的信息表示方案，具有空間效率高、計(jì)算復(fù)雜度低、并行程度高等優(yōu)勢(shì)，適合于硬件實(shí)現(xiàn)，具有很好的實(shí)用價(jià)值。

參考文獻(xiàn):

[1]FANG Wen-jia， PETERSON L. Inter-AS traffic patterns and their implications[C]//Proc of IEEE GLOBECOM. Boston:[s.n.]， 1999: 1859-1868.

[2]IDT.SRAMs[EB/OL].http://www.idt.com/?catID=58743source=memory_app.

[3]WANG Hong-bo， WEI An-ming， LIN Yu， et al. Time stratified packet sampling based on measurement buffer for flow measurement[J]. Journal of Software， 2006， 17(8):1775-1784.

[4]AMER P D， CASSEL L N. Management of sampled real-time network measurements[C]//Proc of the 14th Conference on Local Computer Networks. 1989: 62-68.

[5]CLAFFY K C， POLYZOS G C， BRAUN H W. Application of sampling methodologies to network traffic characterization[C]//Proc of ACM Sigcomm. Madison:[s.n.]， 1993: 267-280.

[6]ESTAN C. New directions in traffic measurement and accounting[C]//Proc of ACM Sigcomm. Oklahoma City:[s.n.]， 2002: 562-574.

[7]KUMAR A， XU Jun. Sketch guided sampling:using on-line estimates of flow size for adaptive data collection[C]//Proc of IEEE INFOCOM’06. Barcelona:[s.n.]， 2006.

[8]程光， 龔儉， 丁偉. 基于統(tǒng)計(jì)分析的高速網(wǎng)絡(luò)分布式抽樣測(cè)量模型[J]. 計(jì)算機(jī)學(xué)報(bào)， 2003， 26(10): 1266-1272.

[9]FAN Li， CAO Pei， ALMEIDA J， et al. Summary cache: a scalable wide-area Web cache sharing protocol [J]. IEEE/ACM Trans on Networking， 2000， 8(3):281-293.

[10]KUMAR A， XU Jun. Space-code Bloom filter for efficient per-flow traffic measurement[C]//Proc of IEEE INFOCOM’04. Hong Kong:[s.n.]， 2004: 315-328.

[11]BONOMI F， MITZENMACHER M， PANIGRAHY R， et al. An improved construction for counting Bloom filters[C]//Proc of European Symposium on Algorithms. Sydney:[s.n.] ， 2006: 678-680.

[12]VOCKING B. How asymmetry helps load balancing[J]. Journal of the ACM on Computer， 2003， 50(4): 568-589.

[13]BONOMI F， MITZENMACHER M， PANIGRAHY R， et al. Beyond Bloom filters: from approximate membership checks to approximate state machines[C]//Proc of ACM SIGCOMM. 2006: 342-356.