利用深度學(xué)習(xí)的高速網(wǎng)絡(luò)流基數(shù)估計(jì)算法

楊東陽(yáng),韓軼凡,孫玉娥,李 姝,杜 揚(yáng),黃 河

1(蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 蘇州 215006)

2(蘇州大學(xué) 軌道交通學(xué)院,江蘇 蘇州 215131)

3(沈陽(yáng)理工大學(xué) 裝備工程學(xué)院,沈陽(yáng) 110159)

1 引 言

在高速網(wǎng)絡(luò)中實(shí)時(shí)準(zhǔn)確地估計(jì)每條流的流量[1-21]可以為流量工程、異常檢測(cè)和網(wǎng)絡(luò)安全等提供可靠的基礎(chǔ)數(shù)據(jù),對(duì)大量網(wǎng)絡(luò)應(yīng)用來(lái)說(shuō)至關(guān)重要.隨著大網(wǎng)絡(luò)數(shù)據(jù)時(shí)代的演化和發(fā)展,網(wǎng)絡(luò)流速和規(guī)模日益增長(zhǎng).據(jù)Cisco發(fā)布的白皮書《Cisco Visual Networking Index:Forecast and Trends》[22]預(yù)測(cè),到2022年全球的IP流量將達(dá)到每年4.8澤字節(jié),是2017年的3.7倍.而要實(shí)時(shí)處理如此高速海量的網(wǎng)絡(luò)數(shù)據(jù)需要消耗大量的高速存儲(chǔ)和計(jì)算資源,這為高速處理資源極度緊缺環(huán)境下的高精度流量測(cè)量提出了嚴(yán)峻的挑戰(zhàn).

高速網(wǎng)絡(luò)流量測(cè)量主要包括流大小測(cè)量和流基數(shù)測(cè)量,其中流大小測(cè)量主要是計(jì)算流中數(shù)據(jù)包的個(gè)數(shù)或字節(jié)數(shù),而流基數(shù)的測(cè)量則是估計(jì)流中不同元素的數(shù)量.在這里,流和元素是可以根據(jù)應(yīng)用的實(shí)際需求定義,例如將發(fā)送至同一個(gè)目的地址的所有數(shù)據(jù)包抽象為一條目的地址流,而將流中每個(gè)源地址抽象為一個(gè)元素.顯然,流基數(shù)的測(cè)量由于需要去除流中的重復(fù)元素,因此比流大小測(cè)量更具挑戰(zhàn)性.為了保證數(shù)據(jù)包能夠被實(shí)時(shí)處理,目前大多數(shù)流基數(shù)測(cè)量方法利用緊湊型數(shù)據(jù)摘要(Sketch),把整個(gè)流基數(shù)記錄模塊全部放置在能夠匹配流速的網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間.例如,文獻(xiàn)[6]為每條流分配一個(gè)虛擬位圖(virtual Bitmap),而所有的虛擬位圖共享同一段實(shí)際物理內(nèi)存來(lái)實(shí)現(xiàn)存儲(chǔ)資源受限下的流基數(shù)估計(jì).文獻(xiàn)[7]則為每條流分配了一組虛擬寄存器,而讓不同的流通過(guò)所有虛擬寄存器共享同一段物理內(nèi)存來(lái)實(shí)現(xiàn)流基數(shù)估計(jì).上述解決方案利用哈希技術(shù)將實(shí)時(shí)到達(dá)的元素隨機(jī)映射到所分配實(shí)際物理空間的一個(gè)或多個(gè)比特位,并以一定概率將其置1,最終根據(jù)置位概率推導(dǎo)出置位結(jié)果與實(shí)際元素?cái)?shù)量之間的關(guān)系式,從而得到流基數(shù)估計(jì)器.然后,這些機(jī)制為了盡可能地降低片上存儲(chǔ)資源的占用,均使用比特級(jí)或寄存器級(jí)的存儲(chǔ)資源共享技術(shù),讓多條流共享同一段物理存儲(chǔ)空間,使得不同流的信息混雜在一起,從而為后面的流基數(shù)估計(jì)引入了噪聲.為了進(jìn)一步降低噪聲的影響,已有機(jī)制大都通過(guò)概率分析的方式,分析出每條流引入的平均噪聲,并在估計(jì)時(shí)將平均噪聲濾除,進(jìn)而得到一個(gè)相對(duì)準(zhǔn)確的估計(jì)結(jié)果.

上述去除噪聲的方法并不總是高效的,當(dāng)實(shí)際引入的噪聲與期望的平均噪聲偏差較大時(shí),會(huì)嚴(yán)重影響流基數(shù)的估計(jì)精度.要進(jìn)一步提高流基數(shù)估計(jì)的精度,就需要設(shè)計(jì)新的方法來(lái)降低流之間存儲(chǔ)共享所帶來(lái)的噪聲影響.

針對(duì)上述問(wèn)題,本文在流基數(shù)估計(jì)中引入了深度學(xué)習(xí)技術(shù),致力于降低由于存儲(chǔ)資源共享所帶來(lái)的噪聲影響,進(jìn)而提高流基數(shù)估計(jì)的精度.為此,本文首先借鑒已有的虛擬寄存器技術(shù),改進(jìn)了已有的數(shù)據(jù)包實(shí)時(shí)處理和記錄存儲(chǔ)方法,提出了一種更高效的寄存器數(shù)值編碼技術(shù),以盡可能地降低虛擬寄存器中的噪聲并降低流基數(shù)估計(jì)的復(fù)雜度.然后,進(jìn)一步引入深度學(xué)習(xí)技術(shù),用于學(xué)習(xí)和提取置位結(jié)果與引入噪聲之間的潛在模式,并依此來(lái)更好地去除噪聲,提高估計(jì)精度,所提出的基于深度學(xué)習(xí)的流基數(shù)估計(jì)算法EvHLL(Enhanced virtual HyperLogLog)主要包含為每條流分配虛擬寄存器組、對(duì)元素進(jìn)行哈希并根據(jù)哈希結(jié)果決定是否更新相關(guān)寄存器中的數(shù)值、對(duì)每條流所對(duì)應(yīng)的寄存器組中的數(shù)值進(jìn)行編碼以提高流基數(shù)估計(jì)效率以及利用每條流的編碼結(jié)果和訓(xùn)練好的深度學(xué)習(xí)模型來(lái)估計(jì)流基數(shù)4個(gè)階段.與已有研究相比,本文的主要貢獻(xiàn)在于:

1)改進(jìn)了流元素的置位和幾率存儲(chǔ)方式,進(jìn)一步增大了緊湊型數(shù)據(jù)結(jié)構(gòu)的估計(jì)范圍,進(jìn)而減低了所需的片上存儲(chǔ)空間.

2)設(shè)計(jì)了一種基于累進(jìn)遞增的寄存器更新規(guī)則,大幅降低了由概率隨機(jī)性所帶來(lái)的噪聲,使得實(shí)際噪聲更趨向于期望值.

3)提出了一種高效的數(shù)據(jù)編碼方式來(lái)編碼每條流的虛擬寄存器中的結(jié)果,并引入深度學(xué)習(xí)模型提取每條流編碼的數(shù)據(jù)中的潛在的模式來(lái)提高基數(shù)估計(jì)的精度.

4)本文基于真實(shí)世界的數(shù)據(jù)集(CAIDA)[23]在不同的片上存儲(chǔ)空間中進(jìn)行了仿真實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果顯示,相較于vHLL算法,本文提出的EvHLL算法具有更高的估計(jì)精度和更低的內(nèi)存開(kāi)銷.

2 相關(guān)工作

為了在高速處理資源極度緊缺的環(huán)境下進(jìn)行精準(zhǔn)的流基數(shù)估計(jì),研究者們?cè)谶^(guò)去的幾十年提出了大量的流基數(shù)估計(jì)算法[1-13].其中,大部分現(xiàn)有的算法都是利用緊湊型數(shù)據(jù)摘要(Sketch)來(lái)處理流元素并記錄流基數(shù)信息,最終根據(jù)Sketch中的置位結(jié)果及置位概率推導(dǎo)出流基數(shù).

例如,Bitmap算法[4]需要在網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間為每條流維護(hù)一個(gè)固定長(zhǎng)度的位數(shù)組,對(duì)每個(gè)到達(dá)的數(shù)據(jù)包,首先提取其流標(biāo)簽和流元素,然后根據(jù)流標(biāo)簽找到記錄該流信息的位數(shù)組,接著對(duì)其元素進(jìn)行哈希,根據(jù)哈希結(jié)果對(duì)該位數(shù)組進(jìn)行置位操作,最終根據(jù)位數(shù)組的長(zhǎng)度及其置位結(jié)果估計(jì)每條流的基數(shù).不同于Bitmap算法,HyperLogLog算法[5]在網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間為每條流維護(hù)了一組寄存器,對(duì)于每個(gè)數(shù)據(jù)包,同樣首先提取其流標(biāo)簽和流元素,然后根據(jù)流標(biāo)簽查找其對(duì)應(yīng)的寄存器組,接著將流元素哈希為一個(gè)特定長(zhǎng)度的比特串(通常為32位),根據(jù)哈希結(jié)果的前若干位來(lái)計(jì)算該元素在該流的寄存器組中對(duì)應(yīng)的寄存器,然后計(jì)算其余比特位的rank值(即其余比特位中最左邊0的位置),當(dāng)且僅當(dāng)rank值大于寄存器中的數(shù)值時(shí),用rank值替換掉寄存器中保存的數(shù)值,最終根據(jù)每條流寄存器組中保存的數(shù)值來(lái)估計(jì)每條流的基數(shù).

上述方法的共同點(diǎn)是都需要為每條流保存單獨(dú)的Sketch數(shù)據(jù),即每條流對(duì)應(yīng)單獨(dú)的物理存儲(chǔ)空間,這在僅需估計(jì)少量流的情況下具有一定的可行性.然后,在大網(wǎng)絡(luò)數(shù)據(jù)時(shí)代,網(wǎng)絡(luò)流量中包含了海量的流數(shù)據(jù),極度緊缺的高速處理資源無(wú)法滿足處理海量流數(shù)據(jù)所需的存儲(chǔ)空間.為了解決Bitmap算法和HyperLogLog算法需要為每條流保存單獨(dú)的Sketch數(shù)據(jù),并單獨(dú)占用一定物理存儲(chǔ)空間造成昂貴的資源消耗的問(wèn)題,Li等人[6]在Bitmap算法的基礎(chǔ)上,通過(guò)讓所有流共享網(wǎng)絡(luò)處理器芯片中的同一段物理存儲(chǔ)空間提出了virtual Bitmap(vBitmap)算法,其中每條流和其他流共用同一段物理存儲(chǔ)空間(即同一個(gè)大的位圖),而每條流邏輯上占用的位圖稱為虛擬位圖;Xiao等人[7]提出了讓所有流數(shù)據(jù)共享同一組寄存器的virtual HyperLogLog(vHLL)算法,其中每條流與其他流共享同一段物理存儲(chǔ)空間,每條流邏輯上占用的寄存器組稱為虛擬寄存器組.然而,讓多條流共享同一段網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間會(huì)使得多條流的信息混雜在一起,從而在基數(shù)估計(jì)階段引入大量的噪聲,顯著降低基數(shù)估計(jì)的精確度.

最近,利用機(jī)器學(xué)習(xí)技術(shù)(尤其是深度學(xué)習(xí)技術(shù))來(lái)提高傳統(tǒng)算法的性能層出不窮.例如,Hsu等人[19]利用深度學(xué)習(xí)算法基于歷史數(shù)據(jù)訓(xùn)練了一個(gè)預(yù)言機(jī)(Oracle),通過(guò)學(xué)習(xí)數(shù)據(jù)包中五元組(源IP地址、目的IP地址、源端口、目的端口和網(wǎng)絡(luò)協(xié)議類型)的特征來(lái)區(qū)分大小流,并用單獨(dú)的片上存儲(chǔ)空間來(lái)保存大流的信息,從而提高了每條流的頻率估計(jì)的精度.Yang等人[21]利用一種通用的機(jī)器學(xué)習(xí)框架來(lái)減少Sketch的精度對(duì)網(wǎng)絡(luò)流量特征的依賴性,并且在網(wǎng)絡(luò)流大小、top-k流以及流的數(shù)量等任務(wù)上證明了提出的方法具有更高的性能.Cohen等人[24]利用在線機(jī)器學(xué)習(xí)算法來(lái)自適應(yīng)地學(xué)習(xí)流的大小分布信息,并設(shè)計(jì)了良好的數(shù)據(jù)特征來(lái)執(zhí)行網(wǎng)絡(luò)數(shù)據(jù)流的基數(shù)估計(jì).上述方法證明了機(jī)器學(xué)習(xí)技術(shù)可以有效的改進(jìn)傳統(tǒng)算法,并具有良好的性能.

這些工作促使思考是否可以設(shè)計(jì)一個(gè)簡(jiǎn)單有效的深度學(xué)習(xí)模型來(lái)學(xué)習(xí)每條流虛擬寄存器組存儲(chǔ)的數(shù)據(jù)中的潛在的模式,來(lái)進(jìn)一步改進(jìn)具有大量噪聲的vHLL基數(shù)估計(jì)算法的性能,在不增加計(jì)算復(fù)雜度的前提下提高每條流基數(shù)估計(jì)的性能,減少網(wǎng)絡(luò)處理器片上存儲(chǔ)空間的消耗.

3 相關(guān)方法

本章首先給出了本文所研究的問(wèn)題,然后介紹了已有相關(guān)研究virtual HyperLogLog(vHLL)算法的設(shè)計(jì)思想.表1列出了本文主要使用的一些符號(hào).

表1 主要符號(hào)及其含義Table 1 Main symbols and their meanings

3.1 問(wèn)題定義

高速網(wǎng)絡(luò)環(huán)境下的流基數(shù)估計(jì)是指在某個(gè)測(cè)量周期內(nèi)估計(jì)每條流中不同元素的數(shù)量,其中流標(biāo)簽和元素標(biāo)簽可以是源IP地址、目的IP地址、源端口、目的端口或者其他特定的數(shù)據(jù)包頭部字段.例如,估計(jì)發(fā)往某個(gè)特定目的IP的不同元素的數(shù)量可以有效的檢測(cè)分布式拒絕服務(wù)(DDoS)攻擊;測(cè)量從某個(gè)特定源IP地址發(fā)出的不同元素的數(shù)量可以檢測(cè)超級(jí)傳播者(Superspread)和掃描者攻擊(Scanner).

3.2 vHLL基數(shù)估計(jì)算法

vHLL算法的主要思想是在HyperLogLog算法的基礎(chǔ)上通過(guò)虛擬寄存器組的共享,從而實(shí)現(xiàn)利用少量的片上存儲(chǔ)空間估計(jì)某個(gè)測(cè)量周期內(nèi)所有流的基數(shù)的目標(biāo).在詳細(xì)闡述vHLL算法之前,首先介紹一下物理寄存器和虛擬寄存器的區(qū)別和聯(lián)系:物理寄存器是指網(wǎng)絡(luò)處理器的片上存儲(chǔ)空間中實(shí)際分配給基數(shù)估計(jì)算法的寄存器,而虛擬寄存器是指每條流邏輯上占用的物理寄存器,因?yàn)檫@些寄存器是共享的,不是單獨(dú)占用的,因此稱為虛擬寄存器.通過(guò)虛擬寄存器間的共享,可以大量減少片上存儲(chǔ)空間的消耗,為其他更加重要的網(wǎng)絡(luò)應(yīng)用留下更多寶貴的片上存儲(chǔ)資源.vHLL算法的具體過(guò)程如下所述:

假設(shè)網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間包含了m個(gè)物理寄存器,測(cè)量每條流所需的虛擬寄存器的個(gè)數(shù)為s.對(duì)于每個(gè)到達(dá)的數(shù)據(jù)包P,網(wǎng)絡(luò)處理器會(huì)首先提取P中包含的流標(biāo)簽f和元素標(biāo)簽e,并根據(jù)流標(biāo)簽f來(lái)計(jì)算測(cè)量該流基數(shù)所需要的s個(gè)虛擬寄存器,將測(cè)量該流基數(shù)的s個(gè)虛擬寄存器記為:Rf={Rf1,Rf2,…,Rfs}.然后,對(duì)e執(zhí)行哈希計(jì)算h′=H′(e),其中H′的哈希范圍為[0,232-1),并將其表示為32位的二進(jìn)制符號(hào).接著,根據(jù)其二進(jìn)制符號(hào)串中前q位的數(shù)值來(lái)計(jì)算(即將其前q位的二進(jìn)制轉(zhuǎn)換為十進(jìn)制)該元素對(duì)應(yīng)的虛擬寄存器Rfi,其中q=log2s,并計(jì)算該元素二進(jìn)制符號(hào)串的后(32-q)位的rank值.最終根據(jù)式(1)來(lái)更新虛擬寄存器Rfi中存儲(chǔ)的數(shù)值vRfi:

vRfi=max{vRfi,rank}

(1)

(2)

其中,αs是偏差修正常量,在實(shí)踐中αs通常使用的數(shù)值是α16=0.673,α32=0.697,α64=0.709,當(dāng)大于等于128時(shí),αs=0.7213/(1+1.079/s).

公式(2)在對(duì)大流的估計(jì)上性能良好,但在小流的基數(shù)估計(jì)上往往具有嚴(yán)重的偏差.因此,需要對(duì)小流的估計(jì)值進(jìn)行偏差修正.對(duì)于基數(shù)較小的流,將Rf視為一個(gè)具有s個(gè)比特的位數(shù)組,即將Rf中的每個(gè)虛擬寄存器Rfi轉(zhuǎn)化為一個(gè)比特,當(dāng)且僅當(dāng)VRfi>0時(shí),將其轉(zhuǎn)換為1,否則將其轉(zhuǎn)換為0,然后根據(jù)估計(jì)公式(3)估計(jì)該流的基數(shù):

(3)

其中,V表示轉(zhuǎn)換后位數(shù)組中0的個(gè)數(shù).公式(3)僅在公式(2)的估計(jì)結(jié)果小于2.5s的時(shí)候使用以對(duì)小流基數(shù)估計(jì)結(jié)果進(jìn)行偏差修正從而提高其估計(jì)精度.

4 基于深度學(xué)習(xí)的流基數(shù)估計(jì)算法

本章詳細(xì)介紹了基于深度學(xué)習(xí)的流基數(shù)估計(jì)算法EvHLL.首先,從較高的角度概述了系統(tǒng)模型;然后,詳細(xì)討論了EvHLL算法中包含的4個(gè)主要階段;最后,對(duì)提出的算法進(jìn)行了總結(jié).

4.1 系統(tǒng)模型

本文提出了一種基于深度學(xué)習(xí)的流基數(shù)估計(jì)算法EvHLL,同vHLL一樣,網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間包含了由m個(gè)寄存器組成的物理寄存器組R,其中每條流僅占用s個(gè)虛擬寄存器,不同的流共享虛擬寄存器組.

網(wǎng)絡(luò)處理器的片下存儲(chǔ)空間包含一個(gè)基于歷史數(shù)據(jù)訓(xùn)練好的深度學(xué)習(xí)模型M,用來(lái)根據(jù)每條流的編碼結(jié)果預(yù)測(cè)其基數(shù).在每個(gè)測(cè)量周期結(jié)束后,網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間中寄存器的數(shù)據(jù)會(huì)被離線下載到片下存儲(chǔ)空間.每條流的虛擬寄存器中的數(shù)值會(huì)被進(jìn)一步編碼,從而減少輸入數(shù)據(jù)的維度,并將編碼結(jié)果作為輸入傳遞給神經(jīng)網(wǎng)絡(luò)模型用于估計(jì)每條流的基數(shù).詳細(xì)的系統(tǒng)模型如圖1所示.

圖1 系統(tǒng)模型Fig.1 System model

4.2 寄存器更新過(guò)程

EvHLL算法具有和vHLL算法完全不同的哈希策略和寄存器的更新規(guī)則.通過(guò)新的哈希策略,可以大幅減少網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間的損耗,通過(guò)新的寄存器更新規(guī)則,可以減少基數(shù)估計(jì)過(guò)程中由于寄存器更新過(guò)程中的噪聲對(duì)估計(jì)精度帶來(lái)的影響.

哈希映射策略:對(duì)于持續(xù)到達(dá)的每個(gè)數(shù)據(jù)包P,網(wǎng)絡(luò)處理器會(huì)首先從P中提取其流標(biāo)簽f和元素標(biāo)簽e.然后,它會(huì)對(duì)e執(zhí)行一個(gè)哈希運(yùn)算:h″=H″(e),其中H″的取值范圍是[0,2128-1).h″用128位的二進(jìn)制符號(hào)串來(lái)表示.值得提前注意的是,每條流元素的最終哈希結(jié)果是一個(gè)32位的二進(jìn)制比特串,將其記為B.由于每條流共享的虛擬寄存器的個(gè)數(shù)為s,用B中的前l(fā)og2s位的取值決定每個(gè)元素對(duì)應(yīng)的寄存器,后面32-log2s位的取值決定是否更新該寄存器中的數(shù)值.為了將h″映射到32位的比特串,將其以4比特為單位劃分位32個(gè)二進(jìn)制字段,每個(gè)字段與B中的每個(gè)比特位按次序一一對(duì)應(yīng).

為了使每個(gè)元素被映射到每個(gè)寄存器的概率保持一致,對(duì)于h″的前l(fā)og2s個(gè)字段,當(dāng)且僅當(dāng)該字段對(duì)應(yīng)的數(shù)值小于8(由于每個(gè)字段的取值范圍為[0,16))的時(shí)候,將B中相應(yīng)的比特位置1,否則該位為0.為了減少內(nèi)存空間的消耗和數(shù)值噪聲,對(duì)h″的后32-log2s個(gè)字段執(zhí)行不一樣的操作,當(dāng)且僅當(dāng)這些字段對(duì)應(yīng)的數(shù)值小于11的時(shí)候(11在實(shí)驗(yàn)中具有最優(yōu)的估計(jì)精度),將B中相應(yīng)的比特位置1,否則該位為0.通過(guò)上述兩階段的計(jì)算,每個(gè)元素經(jīng)過(guò)新的哈希策略,會(huì)被映射到32位的二進(jìn)制符號(hào)串,每一位被置0或置1的概率不盡相同.具體的哈希映射策略如圖2所示.

圖2 哈希映射策略Fig.2 Hash map strategy

寄存器的更新:每條流的s個(gè)寄存器由預(yù)先設(shè)定的s個(gè)哈希函數(shù){H1,H2,…,Hs}確定的,如第i個(gè)寄存器是寄存器數(shù)組R中的第Hi(f)modm個(gè)寄存器.根據(jù)每個(gè)元素e的哈希映射結(jié)果,可以計(jì)算出其對(duì)應(yīng)的虛擬寄存器Rfi,即B的前l(fā)og2s位對(duì)應(yīng)的數(shù)值.然后計(jì)算B的后32-log2s位的rank值.當(dāng)且僅當(dāng)rank值滿足式(4)的時(shí)候,以rank值取代寄存器中的數(shù)值:

rank=VRfi+1

(4)

通過(guò)式(4),可以消除寄存器更新過(guò)程中由于概率隨機(jī)性導(dǎo)致的大量噪聲,寄存器中的數(shù)值只會(huì)以累進(jìn)加1的方式進(jìn)行更新,當(dāng)某個(gè)元素的哈希結(jié)果會(huì)導(dǎo)致出現(xiàn)大的偏差的時(shí)候,對(duì)應(yīng)的寄存器會(huì)沒(méi)有任何選擇地忽略掉該異常值,并保留原先存儲(chǔ)的數(shù)值.

通過(guò)這樣的每條流元素處理方式,消除了基數(shù)估計(jì)過(guò)程中的大量隨機(jī)噪聲.而且實(shí)驗(yàn)過(guò)程中每個(gè)寄存器僅需3個(gè)比特即可滿足測(cè)量要求,相比于vHLL算法,如果寄存器個(gè)數(shù)不變,內(nèi)存空間將節(jié)省40%,這對(duì)于寶貴的片上空間來(lái)說(shuō)是非常重要的,可以留下更多寶貴的空間給其他更加重要的應(yīng)用.詳細(xì)的寄存器更新過(guò)程的偽代碼如算法1所示:

算法1.寄存器更新算法

輸入:某測(cè)量周期內(nèi)的數(shù)據(jù)包集合{P1,P2,P3,…}

輸出:寄存器組中各個(gè)寄存器的值

1.for {P1,P2,P3,…}中的每個(gè)數(shù)據(jù)包P

2. 初始化B的每一個(gè)比特位的值為0

3. 提取P的流標(biāo)簽f和元素標(biāo)簽e;

4.h″=H″(e)

5. foriin {1,2,…,32}

6.ifi

7.ifh″的第i個(gè)字段的值<8

8.B[i]=1

9.else

10.ifh″的第i個(gè)字段的值<11

11.B[i]=1

12.計(jì)算其對(duì)應(yīng)的寄存器Rfi,其存儲(chǔ)的數(shù)值為VRfi

13.計(jì)算B的后32-log2s的rank值

14.ifrank=VRfi+1

15.VRfi=rank

16.returnR

4.3 數(shù)據(jù)編碼

對(duì)數(shù)據(jù)進(jìn)行有效的編碼可以在數(shù)據(jù)信息沒(méi)有任何衰減的情況下有效地減少數(shù)據(jù)維度,從而提高基數(shù)估計(jì)的效率.如上所述,每個(gè)寄存器僅需3個(gè)比特即可滿足測(cè)量需求,因此,每個(gè)寄存器中存儲(chǔ)的最大數(shù)值僅能為7.在此基礎(chǔ)上,可以利用有效的編碼方式來(lái)進(jìn)一步處理數(shù)據(jù).具體的編碼方式如下:

對(duì)于每條流f,令其共享的s個(gè)虛擬寄存器為{Rf1,Rf2,…,Rfs},其中Rfi=R[Hi(f)modm].然后統(tǒng)計(jì)該流對(duì)應(yīng)的s個(gè)虛擬寄存器中包含的1,2,…,7的虛擬寄存器的個(gè)數(shù),以一個(gè)7維數(shù)組記錄每條流編碼后的數(shù)據(jù),其中第i維表示值為i的寄存器的數(shù)量.當(dāng)虛擬寄存器中保留的數(shù)值為0時(shí),不對(duì)其進(jìn)行計(jì)數(shù).最終每條流的數(shù)維度由s縮減到7,具體的編碼過(guò)程如算法2所示.

算法2.數(shù)據(jù)編碼

輸入:流的集合{f1,f2,f3,…}

輸出:每條流的編碼結(jié)果

1.forfin {f1,f2,f3,…}

2.初始化7維數(shù)組rstf保存編碼結(jié)果

3.foriin {1,2,…,64}

4.ifRfi不等于0

5.rstf[VRfi]=rstf[VRfi]+1

6.returnrstf

4.4 深度學(xué)習(xí)模型及其訓(xùn)練

為了從每條流的編碼數(shù)據(jù)中提取有效信息從而進(jìn)行精確的流基數(shù)估計(jì),本文設(shè)計(jì)了一個(gè)包含4個(gè)含參數(shù)層的全連接神經(jīng)網(wǎng)絡(luò)模型,用于進(jìn)行基數(shù)估計(jì).詳細(xì)的網(wǎng)絡(luò)模型如圖3所示.

圖3 神經(jīng)網(wǎng)絡(luò)模型Fig.3 Deep learning model

神經(jīng)網(wǎng)絡(luò)的輸入是每條流編碼的7維數(shù)組,并包含3個(gè)隱藏層,每個(gè)隱藏層的神經(jīng)元的個(gè)數(shù)都是25個(gè).所有隱藏層的神經(jīng)元采用的激活函數(shù)都是ReLU(修正線性單元),它可以高效的加速神經(jīng)網(wǎng)絡(luò)的訓(xùn)練,避免梯度消失和梯度爆炸等問(wèn)題,而且簡(jiǎn)化了網(wǎng)絡(luò)的運(yùn)算,降低了模型的復(fù)雜度.ReLU的表達(dá)式如式(5)所示:

f(x)=max(0,x)

(5)

模型的訓(xùn)練是基于歷史流量數(shù)據(jù)進(jìn)行的,在歷史網(wǎng)絡(luò)數(shù)據(jù)流中模擬數(shù)據(jù)處理過(guò)程,而且流的真實(shí)基數(shù)信息是可以輕易獲取的,從而獲得大量的訓(xùn)練數(shù)據(jù).損失函數(shù)采用的是均方根誤差損失,神經(jīng)網(wǎng)絡(luò)模型的優(yōu)化器用的是Adam(自適應(yīng)矩估計(jì))優(yōu)化方法,它經(jīng)常用于解決包含很高噪聲和稀疏梯度的問(wèn)題.

4.5 基數(shù)估計(jì)過(guò)程

流基數(shù)估計(jì)過(guò)程是簡(jiǎn)單且高效的,對(duì)于每條流f,僅需找到其編碼后的數(shù)據(jù)rstf,然后將其作為輸入傳送給已經(jīng)訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)模型M,該模型會(huì)對(duì)每條流的基數(shù)進(jìn)行準(zhǔn)確的預(yù)測(cè).具體的基數(shù)估計(jì)過(guò)程如算法3所示.

算法3.基數(shù)估計(jì)

輸入:流的集合{f1,f2,f3,…}

1.forfin {f1,f2,f3,…}

2.查找rstf

4.6 小 結(jié)

本小節(jié)詳細(xì)介紹了提出的基于深度學(xué)習(xí)的流基數(shù)估計(jì)算法EvHLL,該算法在vHLL的基礎(chǔ)上重新設(shè)計(jì)了每條流元素的兩階段哈希策略及寄存器數(shù)值的更新規(guī)則,有效的減少了基于虛擬寄存器共享的vHLL基數(shù)估計(jì)算法中由于隨機(jī)性而造成的大量噪聲,減少了網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間的消耗,并設(shè)計(jì)了一個(gè)全連接神經(jīng)網(wǎng)絡(luò)模型來(lái)提高基數(shù)估計(jì)的性能.

5 實(shí)驗(yàn)分析

本節(jié)對(duì)基于真實(shí)世界的數(shù)據(jù)集對(duì)提出的EvHLL算法進(jìn)行評(píng)估.首先介紹實(shí)驗(yàn)采用的CAIDA數(shù)據(jù)集;其次介紹基數(shù)估計(jì)性能的評(píng)估指標(biāo);最后,展示并分析了實(shí)驗(yàn)結(jié)果.

5.1 數(shù)據(jù)集

在實(shí)驗(yàn)過(guò)程中,采用的數(shù)據(jù)集是2016年CAIDA在equinix-chicago高速監(jiān)視器上被動(dòng)監(jiān)聽(tīng)的匿名流量蹤跡[23].據(jù)統(tǒng)計(jì),一分鐘的CAIDA數(shù)據(jù)集包含了超過(guò)3千萬(wàn)個(gè)數(shù)據(jù)包,58萬(wàn)個(gè)源地址流和16萬(wàn)個(gè)目的地址流.用CAIDA數(shù)據(jù)集中前5分鐘的數(shù)據(jù)進(jìn)行相關(guān)實(shí)驗(yàn),每一分鐘為一個(gè)測(cè)量周期,并在目的地址流上評(píng)估了算法的性能.其中前2分鐘的數(shù)據(jù)用來(lái)訓(xùn)練模型,第4分鐘的數(shù)據(jù)作為驗(yàn)證集評(píng)估模型的性能,第5分鐘的數(shù)據(jù)作為測(cè)試集.數(shù)據(jù)集的具體劃分如表2所示.

表2 數(shù)據(jù)集Table 2 Dataset

5.2 性能評(píng)估指標(biāo)

本文采用兩個(gè)常用的性能評(píng)估指標(biāo)來(lái)衡量算法的精確性:

1)平均相對(duì)誤差(ARE):平均相對(duì)誤差的計(jì)算公式如式(6)所示:

(6)

2)平均絕對(duì)誤差(MAE):平均絕對(duì)誤差的計(jì)算公式如式(7)所示:

(7)

一般來(lái)說(shuō),相對(duì)誤差往往更能反映估計(jì)的精確程度.相對(duì)于平均相對(duì)誤差,平均絕對(duì)誤差往往更能反映出預(yù)測(cè)值誤差的實(shí)際情況.

在不同的網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間上對(duì)提出的算法和對(duì)比算法基于以上兩個(gè)指標(biāo)進(jìn)行評(píng)估.

5.3 實(shí)驗(yàn)結(jié)果

本文分別在128KB的片上存儲(chǔ)空間和256KB的片上存儲(chǔ)空間下對(duì)EvHLL算法和vHLL算法進(jìn)行對(duì)比實(shí)驗(yàn),并在不同的基數(shù)區(qū)間內(nèi)比較兩者的平均相對(duì)誤差A(yù)RE.其中,基數(shù)區(qū)間在log級(jí)上進(jìn)行劃分.另外,在整體數(shù)據(jù)集上評(píng)估了兩者的平均相對(duì)誤差和平均絕對(duì)誤差,實(shí)驗(yàn)精度如圖3～圖6所示.

圖4和圖5展示了在網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間為128KB的情況下vHLL算法和EvHLL算法的基數(shù)估計(jì)精度.通過(guò)圖4可知,在片上存儲(chǔ)空間非常有限的情況下,vHLL對(duì)小流的誤差幾乎沒(méi)有任何修正效果,從而導(dǎo)致對(duì)小流的基數(shù)估計(jì)仍然具有較大的偏差,這說(shuō)明vHLL的修正算法具有一定的局限性.然而,小流的基數(shù)在一些情況下是特別重要的,如隱匿的DDoS攻擊[25].圖5顯示EvHLL算法在小流基數(shù)估計(jì)方面具有更高的估計(jì)精度.

圖4 vHLL在128KB的片上存儲(chǔ)空間下的每條網(wǎng)絡(luò)流的基數(shù)估計(jì)結(jié)果Fig.4 Per-flow cardinality estimation results of vHLL under 128KB on-chip memory space

圖5 EvHLL在128KB的片上存儲(chǔ)空間下的每條網(wǎng)絡(luò)流的基數(shù)估計(jì)結(jié)果Fig.5 Per-flow cardinality estimation results of EvHLL under 128KB on-chip memory space

圖6和圖7顯示了在網(wǎng)絡(luò)處理器芯片的片上存儲(chǔ)空間為256KB的情況下兩者的估計(jì)精度,可以看出EvHLL算法相較于vHLL無(wú)論對(duì)于小流的基數(shù)還是大流的基數(shù)都有更高的估計(jì)精度.

圖6 vHLL在256KB的片上存儲(chǔ)空間下的每條網(wǎng)絡(luò)流的基數(shù)估計(jì)結(jié)果Fig.6 Per-flow cardinality estimation results of vHLL under 256KB on-chip memory space

圖7 EvHLL在256KB的片上存儲(chǔ)空間下的每條網(wǎng)絡(luò)流的基數(shù)估計(jì)結(jié)果Fig.7 Per-flow cardinality estimation results of EvHLL under 256KB on-chip memory space

表3和表4分別列舉了不同的基數(shù)區(qū)間內(nèi),兩者的平均相對(duì)誤差.從表3中知在128KB片上存儲(chǔ)空間時(shí),在基數(shù)區(qū)間為1到10時(shí),EvHLL的ARE減少了99.15%;在基數(shù)區(qū)間為10到100時(shí),EvHLL的ARE減少了92.41%;在基數(shù)區(qū)間為100到1000時(shí),EvHLL的ARE減少了89.67%;在基數(shù)區(qū)間為1000到10000時(shí),EvHLL的ARE減少了13.34%.同樣,在表4中可以看到在內(nèi)存空間為256KB的情況下,EvHLL算法同樣具有更低的平均相對(duì)誤差.

表3 128KB片上存儲(chǔ)空間下不同基數(shù)區(qū)間的ARETable 3 ARE in distinct cardinality intervals under 28KB on-chip memory space

表4 256KB片上存儲(chǔ)空間下不同基數(shù)區(qū)間的ARETable 4 ARE in distinct cardinality intervals under 128KB on-chip memory space

表5展示了整個(gè)測(cè)試集上在不同的片上存儲(chǔ)空間下的估計(jì)精度.可以看到,在128KB的內(nèi)存空間下,EvHLL的ARE減少了99.13%,MSE減少了98.37%;在256KB的內(nèi)存空間下,EvHLL的ARE減少了82.39%,MSE減少了68.05%.整體看來(lái),EvHLL算法遠(yuǎn)遠(yuǎn)優(yōu)于vHLL.

表5 128KB和256KB片上存儲(chǔ)空間下的整體估計(jì)指標(biāo)Table 5 Overall estimation metrics under 128KB and 256KB on-chip memory space

5.4 性能分析

本文提出的EvHLL算法在數(shù)據(jù)包處理及Sketch更新過(guò)程中僅需使用速度極高的片上存儲(chǔ)(SRAM)并且僅需一次內(nèi)存訪問(wèn),可以實(shí)現(xiàn)以線性速度高效的處理每一個(gè)數(shù)據(jù)包.然而,由于查詢過(guò)程中需要一定的內(nèi)存訪問(wèn)和計(jì)算資源,且受限于SRAM的制造工藝和高昂價(jià)格,如同vHLL,EvHLL算法的查詢過(guò)程在容量不受限的片下存儲(chǔ)空間(DRAM)進(jìn)行.在每一個(gè)測(cè)量周期結(jié)束后,所有數(shù)據(jù)被下載到片下存儲(chǔ)空間,并對(duì)其進(jìn)一步處理.訓(xùn)練好的深度學(xué)習(xí)模型置于片下存儲(chǔ)空間,以響應(yīng)每條流的基數(shù)查詢.實(shí)驗(yàn)結(jié)果表明,本文提出的學(xué)習(xí)模型響應(yīng)每條流的基數(shù)查詢僅需29.35us,完全滿足相關(guān)的測(cè)量需求.

此外,為了驗(yàn)證機(jī)器學(xué)習(xí)算法的適應(yīng)性,我們?cè)谄渌F(xiàn)實(shí)世界的數(shù)據(jù)集[26]上進(jìn)行了相關(guān)實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表6所示,可以看到,在128KB的內(nèi)存空間下,EvHLL的ARE減少了99.56%,MSE減少了99.18%;在256KB的內(nèi)存空間下,EvHLL的ARE減少了95.34%,MSE減少了87.65%.

表6 128KB和256KB片上存儲(chǔ)空間下的整體估計(jì)指標(biāo)Table 6 Overall estimation metrics under 128KB and 256KB on-chip memory space

6 結(jié) 論

本文提出了一種基于深度學(xué)習(xí)的流基數(shù)估計(jì)算法EvHLL.在vHLL的基礎(chǔ)上,重新設(shè)計(jì)了每條流元素的哈希策略,減少了內(nèi)存空間的消耗,重新制定了寄存器的更新規(guī)則,減少了概率算法中由于隨機(jī)性的存在而導(dǎo)致的大量噪聲.采用了一種高效的數(shù)據(jù)編碼方式,用于減少輸入數(shù)據(jù)的維度.本文設(shè)計(jì)了一個(gè)深度學(xué)習(xí)模型,用于從每條流的編碼數(shù)據(jù)中提取潛在的信息提高基數(shù)估計(jì)的性能.基于真實(shí)世界的CAIDA數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,EvHLL算法在相同的存儲(chǔ)空間的條件下,具有更低的平均相對(duì)誤差和更低的平均絕對(duì)誤差.