基于MapReduce的并行CCBF大流識(shí)別算法

張惠民，馮林生

(陸軍裝甲兵學(xué)院， 北京 100072)

網(wǎng)絡(luò)行為監(jiān)控是網(wǎng)絡(luò)安全管理的基礎(chǔ)性工作，將具有相同五元組的數(shù)據(jù)包進(jìn)行歸類就得到了流(flow)數(shù)據(jù)，基于流(flow)數(shù)據(jù)的測量為網(wǎng)絡(luò)監(jiān)控提供了新的途徑。流對(duì)象分布呈現(xiàn)出顯著的重尾分布特征，少部分的大流量對(duì)象形成了大部分的網(wǎng)絡(luò)流量[8,10]；在OC-768鏈路上，40 B大小的分組僅需8 ns的傳輸時(shí)間，集中式的處理方式難以滿足大規(guī)模網(wǎng)絡(luò)流量數(shù)據(jù)(以下簡稱“大流”)的處理需求。流對(duì)象之間在計(jì)算上不存在相關(guān)關(guān)系，非常適合于分布式并行計(jì)算。

MapReduce是Google提出的一種分布式的并行計(jì)算框架，Hadoop對(duì)MapReduce進(jìn)行了開源實(shí)現(xiàn)，將復(fù)雜的計(jì)算任務(wù)抽象成多路的Map過程和Reduce過程[6]，便于并行化計(jì)算任務(wù)的實(shí)現(xiàn)。

本文在CCBF算法[1]的基礎(chǔ)上，設(shè)計(jì)了在Hadoop平臺(tái)運(yùn)行的并行CCBF算法，并通過實(shí)驗(yàn)驗(yàn)證了算法的性能。

1 MapReduce模型的并行特性

在Hadoop框架中，MapReduce分布式處理框架由Map過程、Partition過程以及Reduce過程構(gòu)成，如圖1所示。主函數(shù)負(fù)責(zé)完成對(duì)MapReduce作業(yè)正確運(yùn)行所需參數(shù)配置，并顯式指定作業(yè)執(zhí)行流程。Map函數(shù)定義為一個(gè)類(稱為Mapper類)。在Mapper類中可以定義setup、map和cleanup等方法。相應(yīng)地，Reduce函數(shù)定義為一個(gè)稱為Reducer的類，在Reducer類中可以定義setup、reduce和cleanup等方法。map、reduce方法的一般形式表示如下：

map：( K1,V1)→list( K2,V2)

reduce：(K2,list( V2)) →list( K3,V3)

其中，(K1，V1)是數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)分片中的記錄經(jīng)過Hadoop框架解析后提供的鍵/值對(duì)表示，list( K2，V2)、list(K3，V3)分別是map和reduce方法輸出的鍵/值對(duì)列表。Combine函數(shù)和Map函數(shù)運(yùn)行于TaskTracker節(jié)點(diǎn)，partition函數(shù)將map過程輸出的鍵值對(duì)定位到相應(yīng)的reduce過程。

2 CCBF算法的并行化策略

2.1 CCBF算法思想

吳樺等[1]提出利用計(jì)數(shù)型布魯姆計(jì)數(shù)器[2,9]進(jìn)行大流的識(shí)別記錄以及小流量對(duì)象的過濾，提出了CCBF算法,在數(shù)據(jù)量較大的情況下，該算法具有較小的錯(cuò)誤率。

2.1.1 描述

CCBF算法采用計(jì)數(shù)型布魯姆過濾器對(duì)流(flow)進(jìn)行計(jì)數(shù)，只有每個(gè)Hash表項(xiàng)的計(jì)數(shù)都超過閾值時(shí)，該流(flow)才被判斷為大流，并建立流的記錄，同時(shí)采用布魯姆過濾器進(jìn)行大流存在的記錄，CCBF算法的結(jié)構(gòu)如圖2所示。

2.1.2 算法

CCBF算法的具體描述如下：

while packet arrives

calculate H = h(1),h(2),…,h(K)

if H exist in Longflow_BF

{

Increase Longflow records

}

else

{

increase corresponding counters in Filter_CBF;

if min_counter>DemandValue{

decrease corresponding counters in Filter_CBF;

increase corresponding counters in Longflow_BF;

add new Long flow records;

}

}

end while

export flow record；

2.1.3 特性分析

令n為已經(jīng)處理的報(bào)文的個(gè)數(shù)，k為Hash函數(shù)的個(gè)數(shù)，m為計(jì)數(shù)型布魯姆過濾器(CBF)結(jié)構(gòu)中計(jì)數(shù)器的數(shù)目，j為大流的閾值，從而CCBF算法的誤判率為

(1)

CCBF大流識(shí)別算法以較低的時(shí)間和空間復(fù)雜度實(shí)現(xiàn)了高速鏈路大流的高精度識(shí)別，在數(shù)據(jù)量較大的情況下，該算法具有較小的平均錯(cuò)誤率，在排除輸入、輸出影響的情況下，該算法可以應(yīng)用于大規(guī)模主干網(wǎng)的流量分析。

2.2 基于MapReduce的并行化改造

2.2.1 描述

在基于流(flow)的網(wǎng)絡(luò)數(shù)據(jù)測量中，流對(duì)象之間在流的大小統(tǒng)計(jì)上不存在相關(guān)性；本文基于MapReduce的并行CCBF大流識(shí)別，在map過程中完成數(shù)據(jù)報(bào)基于流的特征提取，在partition過程中完成數(shù)據(jù)報(bào)基于流的分發(fā)，在reduce過程中完成長流的識(shí)別以及流長的計(jì)算。

2.2.2 map過程的設(shè)計(jì)

在MapReduce框架中，Map函數(shù)的輸入為p，p表示報(bào)文序列pi(i=1，2，…)。從報(bào)文序列中提取出五元組信息作為value，為實(shí)現(xiàn)良好的并行性，降低算法在各節(jié)點(diǎn)的耦合度，對(duì)五元組進(jìn)行Hash操作，并將結(jié)果作為key，之后輸出〈key，value〉。

map函數(shù)的偽代碼如下所示：

input:p

output:〈key,value〉

key = hash(p.info)；

value=p.info；

2.2.3 partition過程的設(shè)計(jì)

在MapReduce分布式運(yùn)行框架中，Partition過程用來完成對(duì)Map過程輸出的分區(qū)處理，Partition過程根據(jù)Reduce節(jié)點(diǎn)的個(gè)數(shù)完成對(duì)Map輸出的分區(qū)。因?yàn)樵趍ap過程中已經(jīng)完成了hash操作，所以為提高算法的運(yùn)行效率，在本文的算法中定制的Partition函數(shù)為

getpartition(K key,V value,int numReduceTasks)

{

return new long key;

}

2.2.4 reduce過程的設(shè)計(jì)

Reduce函數(shù)的輸入是〈key,[value]〉鍵值對(duì)。輸出為〈key′,value′〉鍵值對(duì)，其中key′為數(shù)據(jù)流的五元組標(biāo)識(shí)符；value′數(shù)據(jù)流的長度，單位為數(shù)據(jù)包。Reduce函數(shù)首先通過Filter_CBF過濾掉小流，提取超過閾值的數(shù)據(jù)流存入鏈表，并用Longflow_BF結(jié)構(gòu)標(biāo)識(shí)長流是否存在，之后將鏈表中各節(jié)點(diǎn)存儲(chǔ)的五元組以及流長作為鍵值對(duì)輸出。

reduce函數(shù)的偽代碼如下所示：

input:〈key,[value]〉

output:〈key′,value′〉

while(value exist)

{

H = h1(value),h2(value),…h(huán)k(value);

if(H exist in Longflow_List)

{

update Longflow_List;

}

else

{

increase Filter_CBF;

if(Filter_CBFmin>threshold)

{

insert Longflow_BF;

insert Longflow_List;

decrease Filter_CBF;

}

}

}

node= Longflow_List->node;

key′=Longflow_Listi.info;

value′=Longflow_Listi.num;

context.write(key′,value′);

while(node->next != null){

node=node->next;

key′=node.info;

value′=node.num;

context.write(key′,value′);

}

3 算法分析

評(píng)價(jià)大流識(shí)別算法存在嚴(yán)格的標(biāo)準(zhǔn)，需要從算法運(yùn)行的時(shí)間效率以及算法結(jié)果的正確性這兩個(gè)方面進(jìn)行評(píng)價(jià)，在大流識(shí)別算法中這兩個(gè)方面是相互聯(lián)系互相制約的。其中算法的時(shí)間效率是主要方面，時(shí)間效率高的算法才可能被應(yīng)用于大規(guī)模主干網(wǎng)上進(jìn)行網(wǎng)絡(luò)流分析，時(shí)間效率將在后面的實(shí)驗(yàn)中進(jìn)行分析；算法的正確性決定了算法應(yīng)用質(zhì)量，從而決定了算法是否會(huì)被采用，下面從誤判率來分析算法的正確性。

算法的主體結(jié)構(gòu)是使用計(jì)數(shù)型布魯姆過濾器進(jìn)行大流識(shí)別判斷的，結(jié)合算法流程以及哈希沖突可知算法存在錯(cuò)誤增加流長的誤判，使流長錯(cuò)誤增加一次的誤判率為

(2)

這個(gè)概率是誤判一次的概率，根據(jù)計(jì)數(shù)型布魯姆過濾器的功能存在誤判兩次以上的概率，誤判兩次以上的概率遠(yuǎn)遠(yuǎn)低于誤判一次的概率，因而算法的誤判率取誤判一次的概率。分析誤判率公式，可以看出影響算法誤判率的4個(gè)參數(shù)：

N為布魯姆過濾器表示的元素個(gè)數(shù)，在Longflow_CBF中表示長流的總數(shù)，在Filter_CBF中表示網(wǎng)絡(luò)流的總數(shù)。隨著n的增大，算法的誤差增大，減小n的值就能相應(yīng)地降低誤差，因此在固定的時(shí)間間隔內(nèi)將布魯姆過濾器初始化，能夠降低誤判率。

K為Hash函數(shù)的個(gè)數(shù)。在n和m確定的情況下，為使算法的誤判率達(dá)到最小，k值為：

(3)

N表示在MapReduce運(yùn)行框架中，reduce任務(wù)的個(gè)數(shù)。

M為布魯姆過濾器中表示集合元素的單元個(gè)數(shù)，m取值越大，誤判率越小，但是內(nèi)存消耗也越大，因此需要在內(nèi)存消耗和誤判率之間找一個(gè)平衡點(diǎn)。

將式(2)代入式(1)得：

(4)

從以上的分析可知算法的誤判率受硬件資源和被處理報(bào)文數(shù)量的影響。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

在實(shí)驗(yàn)室搭建的Hadoop平臺(tái)上運(yùn)行所有實(shí)驗(yàn)。Hadoop實(shí)驗(yàn)平臺(tái)由6臺(tái)機(jī)器組成，其中1臺(tái)為主節(jié)點(diǎn)，另外5臺(tái)為從節(jié)點(diǎn)。6臺(tái)機(jī)器的配置是：CPU的主頻頻率為8核2.40 GHz、32 GB內(nèi)存和100 M網(wǎng)卡。操作系統(tǒng)為CentOS7。Hadoop版本是2.7.3，因?yàn)閿?shù)據(jù)節(jié)點(diǎn)的采用的是8核CPU，所以reduce任務(wù)個(gè)數(shù)參數(shù)設(shè)置為8的倍數(shù)。6臺(tái)機(jī)器通過交換機(jī)和網(wǎng)線搭建一個(gè)局域網(wǎng)。

應(yīng)用JAVA編程語言完成了文獻(xiàn)[1]中提出的CCBF算法以及本文提出的基于MapReduce的并行CCBF長流識(shí)別算法和不采用基于MapReduce的并行CCBF表流識(shí)別算法[1]。并進(jìn)行了3組數(shù)據(jù)集實(shí)驗(yàn)，分別測試了算法的運(yùn)行時(shí)間、可擴(kuò)展性以及加速比。實(shí)驗(yàn)選取的數(shù)據(jù)源CAIDA-OC48數(shù)據(jù)集是在美國西海岸的一個(gè)OC48對(duì)等鏈路上采集的，采集于2012年9月，僅包括匿名的數(shù)據(jù)報(bào)頭部信息；CAIDA-OC192數(shù)據(jù)集是在CAIDA組織所監(jiān)控的一個(gè)OC192鏈路上采集的，采集于2012年6月，僅包括匿名的數(shù)據(jù)報(bào)頭部信息，如表1所示，分別從中獲取2.9億個(gè)數(shù)據(jù)報(bào)文，使用從中獲得五元組(源地址、源端口、目的地址、目的端口、協(xié)議類型)[10]和二元組(源地址、目的地址)得到了4個(gè)數(shù)據(jù)集(CAIDA-OC48-5、CAIDA-OC48-2、CAIDA-OC192-5、CAIDA-OC192-2)。

表1 算法使用的數(shù)據(jù)源

4.2 采用與不采用基于MapReduce的并行CCBF大流識(shí)別算法性能對(duì)比

使用單機(jī)偽分布式方法搭建了一個(gè)Hadoop集群運(yùn)行本文提出的算法，與運(yùn)行CCBF算法的主機(jī)進(jìn)行運(yùn)行時(shí)間計(jì)算，結(jié)果如表2所示。

表2 算法執(zhí)行時(shí)間 s

從表2可以看出，不采用基于MapReduce的并行CCBF大流識(shí)別算法的執(zhí)行時(shí)間長于基于MapReduce的并行CCBF大流識(shí)別算法的執(zhí)行時(shí)間，這是因?yàn)楸疚奶岢龅乃惴ㄊ遣⑿袌?zhí)行的，對(duì)多核CPU的利用率比串行執(zhí)行的CCBF算法要高。

4.3 基于MapReduce的并行CCBF大流識(shí)別算法的加速比測試

文獻(xiàn)[4-6]給出了評(píng)價(jià)算法性能的重要指標(biāo)加速比的公式，公式如下：

(5)

其中，t1、tn分別表示在1個(gè)節(jié)點(diǎn)和n個(gè)節(jié)點(diǎn)上的執(zhí)行時(shí)間。

使用表1列出的OC48數(shù)據(jù)集驗(yàn)證并行CCBF算法的加速比，取得的實(shí)驗(yàn)結(jié)果如圖3所示。從圖3可以得出，算法具有較高的加速比。

4.4 基于MapReduce的并行CCBF大流識(shí)別算法的可擴(kuò)展性測試

文獻(xiàn)[7]給出了評(píng)價(jià)算法性能的重要指標(biāo)可擴(kuò)展性的計(jì)算公式如下：

(6)

其中，w、p表示問題規(guī)模和集群規(guī)模，w′、p′表示擴(kuò)展后的問題規(guī)模和集群規(guī)模。

為了便于測試算法的可擴(kuò)展性，從表1選取OC192作為實(shí)驗(yàn)數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如圖4所示。實(shí)驗(yàn)結(jié)果表明：并行CCBF算法能夠取得較好的可擴(kuò)展性。

5 結(jié)論

CCBF算法是一種高效的大流識(shí)別算法，受單機(jī)計(jì)算性能的限制，CCBF算法對(duì)大數(shù)據(jù)環(huán)境下的大流識(shí)別存在執(zhí)行時(shí)間過長、效率不高的問題。針對(duì)該問題，本文在MapReduce并行編程環(huán)境下提出了基于MapReduce的并行CCBF大流識(shí)別算法，并對(duì)算法進(jìn)行了實(shí)驗(yàn)分析，在多個(gè)數(shù)據(jù)集上的測試表明：基于MapReduce的并行CCBF大流識(shí)別算法具有較高的加速比和可擴(kuò)展性。

：

[1] 吳樺,龔儉,楊望.一種基于雙重Counter Bloom Filter的長流識(shí)別算法[J].軟件學(xué)報(bào),2010,21(5):1115-1126.

[2] BURTON H.Bloom.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970,13(7):422-426.

[3] FAN L,CAO P,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.

[4] 周麗娟,王慧,王文伯,等.面向海量數(shù)據(jù)的并行KMeans算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,12(40):150-152.

[5] ZHAO Weizhong,Ma Huifang,He Qing.Parallel KMeans Clustering based on MapReduce[J].Lecture Notes in Computer Science.2009,5931:674-679.

[6] 陳興蜀,張帥,童浩,等.基于布爾矩陣和MapReduce的FP-Growth算法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,42(1):135-141.

[7] 陳軍,莫?jiǎng)t堯,李曉梅,等.大規(guī)模并行應(yīng)用程序的可擴(kuò)展性研究[J].計(jì)算機(jī)研究與發(fā)展,2000,37(11):1382-1388.

[8] 王風(fēng)宇,郭山清,李亮雄,云曉春.一種高效率的大流提取方法[J].計(jì)算機(jī)研究與發(fā)展,2013,50(4):731-740.

[9] 田小梅,張大方,謝鯤,等.計(jì)數(shù)布魯姆過濾器代數(shù)運(yùn)算[J].計(jì)算機(jī)學(xué)報(bào),2012,35(12):2598-2617.

[10]朱應(yīng)武,楊家海,張金祥.基于流量信息結(jié)構(gòu)的異常檢測[J].軟件學(xué)報(bào),2010,21(10):2573-2583.