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

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

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

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

1 引 言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 相關(guān)方法

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

表1 主要符號及其含義Table 1 Main symbols and their meanings

3.1 問題定義

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

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

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

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

vRfi=max{vRfi,rank}

(1)

(2)

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

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

(3)

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

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

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

4.1 系統(tǒng)模型

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

網(wǎng)絡(luò)處理器的片下存儲空間包含一個基于歷史數(shù)據(jù)訓(xùn)練好的深度學(xué)習(xí)模型M,用來根據(jù)每條流的編碼結(jié)果預(yù)測其基數(shù).在每個測量周期結(jié)束后,網(wǎng)絡(luò)處理器芯片的片上存儲空間中寄存器的數(shù)據(jù)會被離線下載到片下存儲空間.每條流的虛擬寄存器中的數(shù)值會被進(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 寄存器更新過程

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

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

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

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

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

rank=VRfi+1

(4)

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

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

算法1.寄存器更新算法

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

輸出:寄存器組中各個寄存器的值

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

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

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

4.h″=H″(e)

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

6.ifi

7.ifh″的第i個字段的值<8

8.B[i]=1

9.else

10.ifh″的第i個字段的值<11

11.B[i]=1

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

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

14.ifrank=VRfi+1

15.VRfi=rank

16.returnR

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

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

對于每條流f,令其共享的s個虛擬寄存器為{Rf1,Rf2,…,Rfs},其中Rfi=R[Hi(f)modm].然后統(tǒng)計(jì)該流對應(yīng)的s個虛擬寄存器中包含的1,2,…,7的虛擬寄存器的個數(shù),以一個7維數(shù)組記錄每條流編碼后的數(shù)據(jù),其中第i維表示值為i的寄存器的數(shù)量.當(dāng)虛擬寄存器中保留的數(shù)值為0時,不對其進(jìn)行計(jì)數(shù).最終每條流的數(shù)維度由s縮減到7,具體的編碼過程如算法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ì)了一個包含4個含參數(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個隱藏層,每個隱藏層的神經(jīng)元的個數(shù)都是25個.所有隱藏層的神經(jīng)元采用的激活函數(shù)都是ReLU(修正線性單元),它可以高效的加速神經(jīng)網(wǎng)絡(luò)的訓(xù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ù)處理過程,而且流的真實(shí)基數(shù)信息是可以輕易獲取的,從而獲得大量的訓(xùn)練數(shù)據(jù).損失函數(shù)采用的是均方根誤差損失,神經(jīng)網(wǎng)絡(luò)模型的優(yōu)化器用的是Adam(自適應(yīng)矩估計(jì))優(yōu)化方法,它經(jīng)常用于解決包含很高噪聲和稀疏梯度的問題.

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

流基數(shù)估計(jì)過程是簡單且高效的,對于每條流f,僅需找到其編碼后的數(shù)據(jù)rstf,然后將其作為輸入傳送給已經(jīng)訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)模型M,該模型會對每條流的基數(shù)進(jìn)行準(zhǔn)確的預(yù)測.具體的基數(shù)估計(jì)過程如算法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ò)處理器芯片的片上存儲空間的消耗,并設(shè)計(jì)了一個全連接神經(jīng)網(wǎng)絡(luò)模型來提高基數(shù)估計(jì)的性能.

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

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

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

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

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

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

本文采用兩個常用的性能評估指標(biāo)來衡量算法的精確性:

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

(6)

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

(7)

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

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

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

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

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

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

圖5 EvHLL在128KB的片上存儲空間下的每條網(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ò)處理器芯片的片上存儲空間為256KB的情況下兩者的估計(jì)精度,可以看出EvHLL算法相較于vHLL無論對于小流的基數(shù)還是大流的基數(shù)都有更高的估計(jì)精度.

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

圖7 EvHLL在256KB的片上存儲空間下的每條網(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),兩者的平均相對誤差.從表3中知在128KB片上存儲空間時,在基數(shù)區(qū)間為1到10時,EvHLL的ARE減少了99.15%;在基數(shù)區(qū)間為10到100時,EvHLL的ARE減少了92.41%;在基數(shù)區(qū)間為100到1000時,EvHLL的ARE減少了89.67%;在基數(shù)區(qū)間為1000到10000時,EvHLL的ARE減少了13.34%.同樣,在表4中可以看到在內(nèi)存空間為256KB的情況下,EvHLL算法同樣具有更低的平均相對誤差.

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

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

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

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

5.4 性能分析

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

此外,為了驗(yàn)證機(jī)器學(xué)習(xí)算法的適應(yīng)性,我們在其他現(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片上存儲空間下的整體估計(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ì)了一個深度學(xué)習(xí)模型,用于從每條流的編碼數(shù)據(jù)中提取潛在的信息提高基數(shù)估計(jì)的性能.基于真實(shí)世界的CAIDA數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,EvHLL算法在相同的存儲空間的條件下,具有更低的平均相對誤差和更低的平均絕對誤差.