低速率流淘汰與d-Left散列相結(jié)合的大流檢測算法

李春強 董永強, 吳國新,

1(東南大學計算機科學與工程學院 南京 211189)2 (計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室(東南大學) 南京 211189)

大量研究[1-4]表明：網(wǎng)絡(luò)中少數(shù)具有較大數(shù)據(jù)量的數(shù)據(jù)流生成了網(wǎng)絡(luò)的大部分流量，而其他大量的數(shù)據(jù)流的數(shù)據(jù)量總和僅占小部分的網(wǎng)絡(luò)流量；數(shù)據(jù)流在帶寬占用上也表現(xiàn)出不均衡性，其中少量具有較高速率的數(shù)據(jù)流消耗了大量的網(wǎng)絡(luò)帶寬[4].網(wǎng)絡(luò)中數(shù)據(jù)流的這種分布特征嚴重影響了網(wǎng)絡(luò)傳輸?shù)挠行訹4-6]，導致了數(shù)據(jù)流傳輸帶寬占用上的不公平性，對報文的傳輸時延產(chǎn)生了較大影響[7]，嚴重時甚至發(fā)生擁塞導致報文丟失.在網(wǎng)絡(luò)設(shè)備上，有效檢測出這些數(shù)據(jù)流，進行適當?shù)墓芾砼c控制[8-11]，可以改善網(wǎng)絡(luò)傳輸?shù)挠行裕罕热缇徑饩W(wǎng)絡(luò)擁塞[12]、增加網(wǎng)絡(luò)的有效吞吐率、降低報文傳輸時延及報文丟失率、改善網(wǎng)絡(luò)傳輸?shù)墓叫訹13]等.

目前的研究根據(jù)數(shù)據(jù)流的統(tǒng)計特征定義了大流(elephant flow)與小流(mice flow).文獻[7-9,12]將數(shù)據(jù)量超過一定門限(如64 KB,1 MB,100 MB等)的流定義為大流，這一定義主要關(guān)注的是數(shù)據(jù)流的數(shù)據(jù)量；文獻[14]將數(shù)據(jù)傳輸速率達到鏈路容量的一定比例(如鏈路容量的1%,0.1%)的流定義為大流，這一定義重點關(guān)注的是數(shù)據(jù)流的傳輸速率.

由于網(wǎng)絡(luò)的可用帶寬是動態(tài)變化的，通常各數(shù)據(jù)流源端根據(jù)探測到的網(wǎng)絡(luò)狀況總是不斷嘗試以盡可能高的速率發(fā)送數(shù)據(jù)，這使得共享同一瓶頸鏈路的多個數(shù)據(jù)流的數(shù)據(jù)傳輸速率之和會超出鏈路的帶寬容量而導致?lián)砣?由于鏈路的帶寬容量是以數(shù)據(jù)傳輸速率衡量的，因此準確及時地檢測出具有高傳輸速率的數(shù)據(jù)流是實施流量的管理與控制、改善網(wǎng)絡(luò)傳輸有效性的關(guān)鍵.然而對具有較高的傳輸速率但僅有少量數(shù)據(jù)的數(shù)據(jù)流而言，其生存期短，對網(wǎng)絡(luò)傳輸?shù)挠行圆粫a(chǎn)生持續(xù)性影響，因此在進行傳輸控制時可以將其忽略.對于具有較高的傳輸速率和較大數(shù)據(jù)量的數(shù)據(jù)流，由于不斷競爭網(wǎng)絡(luò)的可用帶寬而對網(wǎng)絡(luò)傳輸?shù)挠行援a(chǎn)生持續(xù)性影響，成為網(wǎng)絡(luò)傳輸控制的主要對象.綜上所述，本文將具有較高傳輸速率和較大數(shù)據(jù)量的數(shù)據(jù)流定義為大流.由于網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)報文大小并不統(tǒng)一，大報文的數(shù)據(jù)量甚至相當于小報文的幾十倍，數(shù)據(jù)流的報文發(fā)送頻率與數(shù)據(jù)流的傳輸速率并不是完全等價的，為了確保檢測的準確性，將數(shù)據(jù)流的傳輸速率而不是報文的發(fā)送頻率作為大流檢測的重要依據(jù).

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，傳輸鏈路的帶寬容量和數(shù)據(jù)流的傳輸速率越來越高.目前，支持100 Gbps鏈路的網(wǎng)絡(luò)設(shè)備[15-16]已經(jīng)可以商用；高速網(wǎng)絡(luò)的轉(zhuǎn)發(fā)能力對數(shù)據(jù)流檢測算法的處理提出了高的性能要求.Hash表具有良好的平均查找性能且易于實現(xiàn)，將Hash表應(yīng)用到網(wǎng)絡(luò)報文處理上得到了廣泛的研究.然而對于普通的Hash表，當待查找的條目存在Hash沖突時，需要多次存儲器訪問才能獲得查找結(jié)果，無法確保最差情形下的處理性能.如何有效處理Hash沖突、降低存儲器的訪問次數(shù)，是Hash表實現(xiàn)高效查找的關(guān)鍵.d-Left散列通過使用多個子表，可以有效改進Hash表的處理性能，因此本文針對高速網(wǎng)絡(luò)中，以流量管理與控制為主要目標的大流檢測，為了高效識別出速率和數(shù)據(jù)量均超過一定門限的大流，將低于速率門限的數(shù)據(jù)流的淘汰與d-Left散列表的存儲結(jié)構(gòu)相結(jié)合，提出了基于d-Left散列的低速流淘汰檢測方案(lowest rate flow eviction integrated withd-Left Hash, LRE-DH)，論文的主要貢獻包括：

1) 對來自實際網(wǎng)絡(luò)中流量數(shù)據(jù)的分布特征進行分析，為基于速率與數(shù)據(jù)量的雙門限檢測方案提供現(xiàn)實依據(jù)；

2) 使用d-Left散列[17]表存儲流檢測的數(shù)據(jù)結(jié)構(gòu)，將d-Left散列表的存儲結(jié)構(gòu)與基于流速率的流緩存替換算法相結(jié)合以實現(xiàn)高效的大流檢測，通過適當配置d-Left散列的子表數(shù)，確保算法的準確性及最差情形下的處理性能；

3) 對算法的準確性與存儲開銷等進行了理論分析；

4) 通過真實網(wǎng)絡(luò)數(shù)據(jù)對提出的算法進行了仿真測試，結(jié)果表明：在相近的存儲開銷下，保持高的處理性能的同時，本文算法的準確性優(yōu)于LRU派生算法S-LRU[5]和L-LRU[18-19]，以及CSS[20]與WCSS[20]算法.

1 網(wǎng)絡(luò)流量特征

網(wǎng)絡(luò)的流量特征是進行大流檢測、實施網(wǎng)絡(luò)傳輸控制的基礎(chǔ)與依據(jù).不失一般性，分析了6組流量數(shù)據(jù)的特征.這些流量數(shù)據(jù)分別是：來自WIDE項目中MAWI(measurement and analysis on the WIDE Internet)工作組[21]的跨太平洋骨干鏈路的流量數(shù)據(jù)T2014，T2015，T2016，T2017，還有WAND網(wǎng)絡(luò)研究組[22]提供的網(wǎng)絡(luò)邊緣鏈路的流量數(shù)據(jù)T2011，以及某高校數(shù)據(jù)中心[23]的流量數(shù)據(jù)UNV.流量數(shù)據(jù)的概要信息如表1所示：

數(shù)據(jù)流基于速率與數(shù)據(jù)量的分布特征是雙門限大流檢測的實現(xiàn)依據(jù)，圖1給出了速率與數(shù)據(jù)量2個維度下數(shù)據(jù)流的聯(lián)合分布特征，由于T2015，T2016與T2017的分布特征相似，因此在圖1中沒有提供.圖1(a)給出了超過給定速率門限和字節(jié)數(shù)的數(shù)據(jù)流的數(shù)據(jù)量占總數(shù)據(jù)量的比例，圖1(b)給出的是超過給定速率門限和字節(jié)數(shù)的數(shù)據(jù)流的流數(shù)目占總流數(shù)目的比例.從圖1可以看出：網(wǎng)絡(luò)中的主要數(shù)據(jù)流量集中在少量的具有較高速率和較大數(shù)據(jù)量的數(shù)據(jù)流數(shù)目中，即少量具有較高的速率和較大數(shù)據(jù)量的數(shù)據(jù)流消耗了大量的網(wǎng)絡(luò)帶寬.比如：在T2017的數(shù)據(jù)中，數(shù)據(jù)量超過100 KB、傳輸速率超過0.01%鏈路帶寬容量的數(shù)據(jù)流的數(shù)據(jù)量之和超過了總數(shù)據(jù)量的89%以上，而相應(yīng)的流數(shù)目不到總流數(shù)的1%.

Fig. 1 Flows distribution features of their size and rate both exceeding certain threshold圖1 速率與數(shù)據(jù)量超出各門限的數(shù)據(jù)流的分布特征

從圖1(b)可以看出：一部分數(shù)據(jù)流的速率超過了一定門限但僅發(fā)送了少量的數(shù)據(jù)，即網(wǎng)絡(luò)中一部分數(shù)據(jù)流屬于高速短流，結(jié)合圖1(a)可以看出這部分數(shù)據(jù)流的流量少，對于流量管理而言可以忽略；而另一部分數(shù)據(jù)流以較低的傳輸速率發(fā)送了較多的數(shù)據(jù)，即網(wǎng)絡(luò)中一部分數(shù)據(jù)流是低速長流，結(jié)合圖1(a)可知這部分數(shù)據(jù)流占用的網(wǎng)絡(luò)帶寬份額非常低，對于流量管理而言也可以忽略.

2 相關(guān)研究

對于網(wǎng)絡(luò)中的大流檢測而言，一種簡單直觀的方法就是對網(wǎng)絡(luò)中所有的數(shù)據(jù)流進行統(tǒng)計，這一思路雖然非常簡單，但對存儲技術(shù)提出了非常高的挑戰(zhàn)；這是因為隨著網(wǎng)絡(luò)帶寬的增加，并發(fā)傳輸?shù)臄?shù)據(jù)流數(shù)目非常大(如表1中的T2014,T2015,T2016,T2017所示，15 min的網(wǎng)絡(luò)流量的數(shù)據(jù)流數(shù)目超過了300萬條)，報文到達的速率非常高，需要存儲器具有大的存儲容量與高的訪問速度.DRAM(dynamic random access memory)具有大的容量但訪問速度難以滿足高速網(wǎng)絡(luò)大流檢測的要求；SRAM(static random access memory)雖然具有高的訪問速度但其容量有限.因此，受存儲技術(shù)的限制，難以通過維護全部數(shù)據(jù)流的統(tǒng)計信息來檢測大流.大流檢測在網(wǎng)絡(luò)管理等領(lǐng)域的應(yīng)用，引起了研究人員的大量關(guān)注.尤其是隨著應(yīng)用場景的拓展，網(wǎng)絡(luò)鏈路帶寬的增加，不斷涌現(xiàn)出新的研究成果；這些新成果從準確性、性能、存儲開銷等方面對已有的研究進行了改進.根據(jù)存儲結(jié)構(gòu)中是否維護數(shù)據(jù)流的標識符信息可分為無狀態(tài)流統(tǒng)計檢測方案與基于部分流統(tǒng)計的檢測方案.

2.1 無狀態(tài)流統(tǒng)計檢測方案

在該類方案中不必存儲數(shù)據(jù)流標識符，而是通過Hash函數(shù)將數(shù)據(jù)流的統(tǒng)計信息與一組計數(shù)器關(guān)聯(lián)，當與之關(guān)聯(lián)的所有計數(shù)器都超過所設(shè)定的門限后將其標識為大流.由于存在Hash沖突，因此一個計數(shù)器會與多個數(shù)據(jù)流相關(guān).這類方案的代表有多階段過濾器(multi-stage filter, MSF)[14]、Count-Min[24]、基于CBF(count Bloom filter)[25]的檢測算法等.這類方案本質(zhì)上是基于概率的檢測方案，具有較小的存儲開銷；但會導致將速率和數(shù)據(jù)量都非常小的流誤識別為大流，誤識別率與總的流數(shù)目及存儲開銷密切相關(guān)；總的流數(shù)目越大，誤識別率也越高.雖然可以通過增加存儲開銷來降低誤識別率，然而，對網(wǎng)絡(luò)數(shù)據(jù)流而言，隨著檢測時間的推移，進入系統(tǒng)中的數(shù)據(jù)流數(shù)目越來越多，Hash沖突率隨之增加，從而導致檢測的誤報率增加；由于網(wǎng)絡(luò)設(shè)備連續(xù)工作的時間非常長，數(shù)據(jù)流的數(shù)目可以看作無限多，而存儲空間是有限的；為了降低這種錯誤率則需要對部分低于一定門限的計數(shù)進行清理，清理時需要掃描整個存儲結(jié)構(gòu)，由于報文是連續(xù)到達的，清理操作可能會導致部分到達的報文來不及處理，以至于檢測性能下降.尤其是誤識別的小流對以改善網(wǎng)絡(luò)傳輸為主要功能的大流識別是難以接受的.λ-HCount[26],FDCMSS(forward decay count-min and space saving)[27]給出了基于時間衰減模型的流檢測方案，在新報文到達進行計數(shù)統(tǒng)計時，對已經(jīng)存儲的統(tǒng)計值乘以衰減值(衰減值等于λt，t是已存儲統(tǒng)計值的生存時間，0<λ<1)后加上新報文的權(quán)重，這相當于對新到達的報文給予更高的計數(shù)權(quán)重，可以起到清理過期信息的作用；這類方案可以實現(xiàn)常數(shù)級的清理操作，但其檢測的準確性跟衰減參數(shù)的設(shè)置密切相關(guān)；而且其中的統(tǒng)計數(shù)值缺乏實際的物理意義.

2.2 基于部分流統(tǒng)計的檢測方案

這類方案需要存儲流的標識符及相應(yīng)的統(tǒng)計信息，由于存儲空間是有限的，因此只能維護一部分流的信息，而且需要根據(jù)一定的策略對檢測緩存中的條目進行淘汰.根據(jù)檢測緩存條目的淘汰方式可分為：集中式淘汰與分散式淘汰.

在集中式淘汰的部分流統(tǒng)計方案中，每次進行緩存條目淘汰時，需要掃描整個緩存空間，按照預先設(shè)定的規(guī)則淘汰非大流緩存條目.這類方案的代表有基于采樣保持S&H(sample and hold)的檢測算法[14]、有損計數(shù)LC(lossy counting)檢測算法[28]、概率型有損計數(shù)PLC(possibility lossy counting)檢測算法[29]、加權(quán)有損計數(shù)WLC(weight lossy counting)檢測算法[30]、IM-SUM[31](iterative median summing) 算法等.這類方案中，將網(wǎng)絡(luò)流量劃分為多個片段(按照時間或數(shù)據(jù)量、報文數(shù))，在每個片段的末尾淘汰部分非大流信息.這類方案存在的問題是：在淘汰非大流信息時，新到達的報文可能來不及處理而影響報文的轉(zhuǎn)發(fā)性能.

計數(shù)類(LC,PLC,WLC等)檢測算法以及IM-SUM算法，在數(shù)據(jù)流量有限的前提下可以確保檢測的準確性，然而這與網(wǎng)絡(luò)中的數(shù)據(jù)流量應(yīng)該近似的看成是無限的情況是不相符的.

分散式淘汰每次只要淘汰一個緩存條目.基于最近最少使用[7](least recently used， LRU)的流檢測算法屬于分散式淘汰，該算法根據(jù)大流通常具有較高的報文到達頻率，因此使用隊列維護流條目被淘汰的順序，根據(jù)數(shù)據(jù)流報文的到達情況修改流在隊列中位置；然而大量突發(fā)到達的小流會嚴重影響算法的準確性.為了緩解突發(fā)小流對準確性的影響，文獻[18-19] 提出了基于界標的LRU(landmark-LRU，L-LRU)算法，該算法的基本思路是：為了避免候選的大流條目被突發(fā)到達的小流淘汰，使用界標將存儲器分成至少2個片段，不同存儲器片段存儲的流條目具有不同的淘汰優(yōu)先級.新創(chuàng)建的流條目首先放在最低優(yōu)先級的存儲器片段，當報文到達頻率超過一定門限后，則放到更高優(yōu)先級的存儲器片段中，而當高優(yōu)先級的存儲器片段滿后，并不直接淘汰相應(yīng)的流條目而是先放到低優(yōu)先存儲器片段中.LRU類的檢測算法對于任意到達的報文的處理復雜度都是常數(shù)級，能夠滿足高速網(wǎng)絡(luò)的性能需求，但其準確性易受存儲開銷及數(shù)據(jù)流到達分布特征等因素的影響.

SS(space saving)算法[32]同樣是一種基于分散式淘汰的部分流統(tǒng)計檢測方案，該算法將數(shù)據(jù)流包含的報文數(shù)作為大流檢測依據(jù)，在流檢測緩存中維護與數(shù)據(jù)流的報文數(shù)密切相關(guān)的統(tǒng)計計數(shù)，該統(tǒng)計計數(shù)值等于數(shù)據(jù)流收到的報文數(shù)與一個誤差值的和.每當新流到達且無可用存儲空間時，將統(tǒng)計計數(shù)值最小的流條目淘汰，并將這一統(tǒng)計計數(shù)作為誤差值.SS算法實現(xiàn)常數(shù)級的淘汰與報文處理操作，但需要動態(tài)分配存儲空間并維護大量的指針，不利于硬件實現(xiàn).CSS(compact space-saving)算法[20]對SS算法進行了改進，雖然實現(xiàn)了靜態(tài)存儲空間分配，但其處理操作仍然比較復雜.在CSS算法的基礎(chǔ)上，文獻[20]提出了基于滑動窗口模型的WCSS(window compact space-saving)大流檢測算法.對于報文的到達和流的淘汰，CSS及WCSS算法雖然可以常數(shù)級的操作，但處理的過程較為復雜.

2.3 大流檢測的其他相關(guān)方案

通常，為了降低系統(tǒng)的資源開銷，減少單位時間處理的報文數(shù)以及流數(shù)目，將采樣技術(shù)[33]應(yīng)用于高速網(wǎng)絡(luò)的大流檢測中.文獻[34]提出了通過周期性報文采樣實現(xiàn)大流檢測的方案，該方案根據(jù)大流檢測的誤報率和漏報率的折中使用貝葉斯理論計算出采樣率，方案存在較大的檢測誤差且無法避免誤報率.采樣還可以用于減少突發(fā)小流的到達對大流檢測的干擾，比如在S-LRU(sample LRU)檢測[5]算法中，報文到達后，在檢測緩存中查找報文所屬的流，若已存儲相應(yīng)的流條目，則調(diào)整流在排序隊列中的位置，若未存儲新到達報文所屬的流，則通過采樣的方法確定新到報文所屬的流是否進入檢測緩存中的.對基于采樣的方案而言，采樣率的設(shè)置以及數(shù)據(jù)流的分布特征對大流檢測的準確性有著較大的影響.

文獻[35-37]提出了基于滑動窗口的大流檢測方案，這種類型的方案只根據(jù)最近所發(fā)送網(wǎng)絡(luò)流量的統(tǒng)計信息來檢測大流，使用數(shù)據(jù)窗口維護最近發(fā)生的報文信息，當新的報文到達，則將窗口中最舊的報文信息及所屬流的相應(yīng)統(tǒng)計信息刪除；其中窗口大小的設(shè)置對大流檢測的效果有著很大影響.

為了改善大流檢測算法的準確性、性能、存儲開銷，還出現(xiàn)了將幾種檢測技術(shù)組合進行大流檢測的方案：比如TCBF-LRU[38],LRU-BF[39-40]等.其中TCBF -LRU使用TBF(time Bloom filter)和CBF根據(jù)到達報文的時間間隔與統(tǒng)計計數(shù)過濾小流，使用LRU結(jié)構(gòu)檢測大流；其中的CBF結(jié)構(gòu)中小流的統(tǒng)計信息無法被有效清理，隨著流數(shù)目的增加會導致過濾效果越來越弱.LRU-BF算法使用BF(bloom filter)存儲已識別出的大流、判斷到達的報文是否屬于已識別出的大流，通過LRU算法過濾小流；該方案主要的問題是，隨著檢測出的大流數(shù)目的增加導致大流識別的誤報率增加.

針對無限的流數(shù)目與數(shù)據(jù)量，在存儲空間有限的條件下，不管何種檢測算法，及時有效地清理小流的統(tǒng)計信息，對改善高速大流檢測的性能與準確性都是至關(guān)重要的.基于Hash映射的無狀態(tài)檢測方案，如果不能及時有效地清理與小流相關(guān)的統(tǒng)計信息，隨著檢測時間的推移，進入系統(tǒng)中數(shù)據(jù)流數(shù)目的增多，檢測的準確性會逐步下降；如果按照數(shù)據(jù)流片段的方式消除與小流相關(guān)的統(tǒng)計信息，需要掃描整個數(shù)據(jù)結(jié)構(gòu)，而報文的到達是連續(xù)的，這會影響報文處理的實時性與性能.LRU類檢測算法根據(jù)數(shù)據(jù)流中最近的報文相對命中頻率而不是流的傳輸速率，淘汰系統(tǒng)中的流條目，易受突發(fā)到達的小流的干擾而影響算法的準確性.

3 低速流淘汰與d-Left散列相結(jié)合的大流檢測算法

定義1. 網(wǎng)絡(luò)中傳輸速率超過一定門限的數(shù)據(jù)流定義為高速流；所有高速率構(gòu)成的集合稱為高速流集合.

定義2. 網(wǎng)絡(luò)中數(shù)據(jù)量超過一定門限的數(shù)據(jù)流定義為長流；所有長流構(gòu)成的集合稱為長流集合.

定義3. 網(wǎng)絡(luò)中同時滿足高速流和長流特征的數(shù)據(jù)流定義為大流；所有的大流構(gòu)成的集合稱為大流集合.

為了改善網(wǎng)絡(luò)傳輸?shù)挠行裕枰獙W(wǎng)絡(luò)中大流進行控制.為了有效檢測出網(wǎng)絡(luò)中的大流，避免將小流誤識別為大流，本文采用了部分流統(tǒng)計的檢測方案.該方案的基本思路為：當已存儲的數(shù)據(jù)流有新報文到達時，計算出數(shù)據(jù)流的傳輸速率與數(shù)據(jù)量，若數(shù)據(jù)流的傳輸速率與數(shù)據(jù)量均達到給定門限時，將其標識為大流.當淘汰緩存中一條數(shù)據(jù)流為新數(shù)據(jù)流分配存儲條目時，根據(jù)緩存中已存儲數(shù)據(jù)流的傳輸速率選出需要淘汰的數(shù)據(jù)流條目.

3.1 基于傳輸速率的流條目淘汰

當?shù)竭_的報文屬于新的數(shù)據(jù)流但無可用的存儲空間時，需要依據(jù)流的傳輸速率淘汰一個流條目.流的傳輸速率等于流傳輸?shù)臄?shù)據(jù)量除以流的生存時間，流的生存時間為從流的創(chuàng)建時間與當前時刻之差，因此系統(tǒng)中所有流的傳輸速率隨著時間的推移而不斷變化，需要動態(tài)地計算.這一方法的優(yōu)勢在于：對于存儲結(jié)構(gòu)中已過期的流，由于不再有報文到達，隨著時間的推移，其生存時間越長，計算出的傳輸速率會越來越小，自然會被淘汰；尤其對于僅包含單個報文的流，可以較快地將其從存儲結(jié)構(gòu)中淘汰掉，有效緩解了大量單報文流的突發(fā)到達對檢測效果的干擾.

當報文到達時，需要在存儲器中查找當前報文所屬的數(shù)據(jù)流；如果未發(fā)現(xiàn)所屬的數(shù)據(jù)流，且無可用存儲空間時，則還需要進一步掃描存儲器，根據(jù)數(shù)據(jù)流的傳輸速率淘汰一條數(shù)據(jù)流.對于存儲器的查找而言，內(nèi)容可尋址存儲器(content addressable memory， CAM)具有優(yōu)異的查找性能可以滿足高速網(wǎng)絡(luò)中報文處理的查找需求；然而若選擇一條流淘汰，則需要掃描已存儲的多個流條目才能確定出要淘汰的流，導致檢測算法處理性能的急劇下降，難以滿足高速網(wǎng)絡(luò)的處理要求.Hash表具有良好的平均查找性能且易于實現(xiàn)，將Hash表應(yīng)用到網(wǎng)絡(luò)報文處理上得到了廣泛的研究.然而對于普通的Hash表，當待查找的條目存在Hash沖突時，需要多次存儲器訪問才能獲得查找結(jié)果，無法確保最差情形下的查找性能.而且，當新流的報文到達，不存在空閑條目時，流條目的淘汰是大流檢測方案的關(guān)鍵點.

3.2 LRE-DH檢測算法及分析

使用普通Hash表存儲大流檢測流條目的主要問題是Hash沖突的存在導致流條目的查找與淘汰的處理難以滿足高速網(wǎng)絡(luò)中大流檢測的性能要求.為了確保大流檢測的性能，采用了d-Left散列表[17]存儲大流檢測的流條目.基于流的大小與傳輸速率的雙門限檢測算法的具體描述見算法1.

d-Left散列表中包含d個子表，為了便于分析與說明，對d個子表從0到d-1進行編號.網(wǎng)絡(luò)中新的報文達到時，提取報文的頭部字段生成流標識符，以待查的流標識符為輸入使用d個不同的Hash函數(shù)生成d個索引，分別在d個子表中相應(yīng)的Hash桶進行查找；若找到對應(yīng)的流條目，則進行字節(jié)數(shù)的累加，并判斷數(shù)據(jù)量是否達到大流的數(shù)據(jù)量門限，若達到數(shù)據(jù)量門限則再計算流速率是否達到大流的速率門限.若未發(fā)現(xiàn)新收到報文對應(yīng)的流條目，從編號最小子表的Hash桶開始判斷是否存在空閑的存儲空間，若存在空閑的存儲空間，則將新流的條目插入到其中.若沒有可用的存儲空間，則在當前新流Flow對應(yīng)的d個子表的Hash桶中找出傳輸速率最小的流minFlow，如果該數(shù)據(jù)流的傳輸速率小于淘汰門限，則將該流淘汰，釋放后的空間分配給當前的新流Flow，記錄新流Flow的生成時間及其字節(jié)數(shù)；如果minFlow的速率超過了淘汰門限，則忽略當前到達的新流Flow.這樣的處理可能會導致大流的漏檢，下面對該方案的漏檢率進行分析.

算法1. 基于d-Left散列的低速流淘汰檢測算法(LRE-DH).

①Receive(Packet);*報文Packet到達提取報文Packet的頭部字段,生成所屬的流Flow的標識符Flow.Id*

②Flow.ID=GetFlowID(Packet);

③Found=false,k=0;

④ While (k

⑤Index[k]=Hash[k](Flow.Id);

⑥ If (在子表k的Index[k]對應(yīng)的Hash桶中找到Flow對應(yīng)的條目)

⑦Flow.Size+=Packet.Size;

⑧ If (Flow.Size≥Size_Threshold)

⑩Flow.Rate=CalcFlowRate(Flow);

中國目前執(zhí)行固定上網(wǎng)電價制度，給予可再生能源一定補貼，但補貼缺口不斷在增加，截至2016年年底補貼缺口超過700億元。隨著新增裝機規(guī)模的進一步擴大，補貼資金缺口將會越來越大。雖然中國暫未實施強制性的可再生能源綠色電力證書交易制度，但是中國在2017年初，發(fā)布了《關(guān)于試行可再生能源綠色電力證書核發(fā)及自愿認購交易制度的通知》，我國已實行綠色電力證書核發(fā)和自愿認購，這標志著我國實施綠色電力證書交易制度已進入倒計時。

設(shè)d-Left散列各子表Hash桶的數(shù)目均為Hd，在插入t×H個元素后，第k個子表恰好包含i個元素的Hash桶的概率為Pk(i)，記xk,i=Pk(≥i)；根據(jù)文獻[41]的分析可得出：

(1)

取d-Left散列的每個子表的Hash桶只存儲一個流條目，則任一條新流被插入到d-Left散列表的概率為

(2)

因此，新流被漏檢的概率為

(3)

由于大流一定是高速流，因此大流的數(shù)目不超過高速流的數(shù)目，大流的條目數(shù)漏檢率期望值小于等于L.

定理1. 以C表示數(shù)據(jù)鏈路的帶寬容量，數(shù)據(jù)流淘汰的速率門限為Cm，則緩存中并發(fā)高速流的數(shù)目H≤(m-1)[ln(m-1)+ln(S1Pmin)]+2，其中Pmin是最小報文的字節(jié)數(shù)，S1是流檢測結(jié)構(gòu)中創(chuàng)建最早的高速流的字節(jié)數(shù).

證明. 流檢測結(jié)構(gòu)AF中的n-1個數(shù)據(jù)流記為fi(1≤i≤n-1)，其生存期為Ti(1≤i≤n-1)且Ti>Ti-1(2≤i≤n-1)，字節(jié)數(shù)為Si(1≤i≤n-1)，顯然Si≥Pmin.若新收到的報文屬于已存儲在AF中的流，則AF中的流數(shù)目不會增加，假設(shè)新收到的報文不屬于已存儲在AF中的流，其大小為Sn，Tn為接收該報文花的時間，記新創(chuàng)建的數(shù)據(jù)流為fn.設(shè)流fn創(chuàng)建后，存儲在AF中的流fi(1≤i≤n-1)仍然為活動高速率，則

(4)

成立，由式(4)可得出：

(5)

由式(5)可得出式(6)(7)：

(6)

(7)

由式(6)得出：

(8)

由式(8)得出：

(9)

將式(7)帶入式(9)得出：

(10)

由式(5)(10)得出：

(11)

由式(11)得出：

(12)

由于Sn≥Pmin，結(jié)合式(12)得出：

(13)

由式(13)得出：

(14)

當m?1時，ln[m(m-1)]≈1(m-1)，結(jié)合式(14)得出：

n≤(m-1)[ln(m-1)+ln(S1Pmin)]+2.

(15)

證畢.

定理1給出的是最大并發(fā)高速流的理論上限，這一上限在下面3個條件同時成立時才能取得.這3個條件是：1)網(wǎng)絡(luò)設(shè)備以線速速率從鏈路上接收報文；2)數(shù)據(jù)流按照數(shù)據(jù)量從大到小的順序依次創(chuàng)建；3)不同數(shù)據(jù)流的報文傳輸過程中不存在交叉.實際上，網(wǎng)絡(luò)鏈路不會長時間持續(xù)工作在線速速率狀態(tài)下；而且任何類型的網(wǎng)絡(luò)鏈路都會對最小報文的大小有限制；此外鏈路上不同數(shù)據(jù)流的報文通常是交替?zhèn)鬏數(shù)模淮嬖诮徊娴母怕蕵O低.因此網(wǎng)絡(luò)中最大并發(fā)流的數(shù)目通常遠小于理論上限.

證明. 一條數(shù)據(jù)量為V的大流，其報文數(shù)Np≈V.由于Hash沖突的存在，新流到達的報文以φ的概率被存儲到流檢測緩存中；設(shè)收到第X個報文，該大流被存儲到流檢測緩存中；隨機變量X服從幾何分布，即X～G(φ)，φ=1-ε.當大流條目在檢測緩存中被創(chuàng)建，其數(shù)據(jù)量的統(tǒng)計值少于門限值Eth被漏檢，即當V-(X-1)×時該大流被漏檢，因此當X>1+(V-Eth)時，大流被漏檢，漏檢概率

(16)

由式(16)得出：

(17)

證畢.

由于報文是網(wǎng)絡(luò)設(shè)備收發(fā)與處理的基本單位，所以定理2從報文而不是字節(jié)數(shù)的角度出發(fā)分析了大流的漏檢率，這一分析的準確性是建立在大流的報文數(shù)與字節(jié)數(shù)線性相關(guān)的基礎(chǔ)上的.從定理2可以看出：隨著大流數(shù)據(jù)量的增加，任一大流被漏檢的概率逐漸降低.

4 實驗與評價

對于大流檢測算法的評價需要從存儲開銷、時間復雜度、準確性等方面綜合考慮.在高速網(wǎng)絡(luò)中，常數(shù)級的時間復雜度是對報文處理算法的基本要求.S-LRU，L-LRU，CSS，WCSS等大流檢測算法在進行流條目的淘汰或更新上都可以通過常數(shù)級的操作實現(xiàn).在進行報文處理時，頻繁的存儲器訪問是制約報文處理性能的關(guān)鍵因素，因此表2從存儲器訪問的角度對各算法處理的時間復雜對進行了對比.對于LRE-DH算法而言，無論是執(zhí)行流條目的統(tǒng)計更新還是緩存替換，最差情形下，需要每個子表都訪問一次，即需要d次存儲器的訪問.

Table 2 The Comparison of Detection Algorithm Complexity表2 檢測算法基本操作復雜度對比

在滿足一定的處理性能和存儲開銷的前提下，大流檢測算法的準確性一直是研究與關(guān)注的重點.通常流檢測算法的準確性包含漏檢率(false negative rate, FNR)與誤報率(false positive rate, FPR)2個方面；由于LRE-DH算法的檢測門限是同時根據(jù)速率和數(shù)據(jù)量識別活動大流，不存在誤報問題，因此我們只對LRE-DH算法的漏檢率進行測試與分析.對于流量管理與控制類應(yīng)用，主要關(guān)注的是所檢測出大流的總數(shù)據(jù)流量；因此漏檢率的測試包含流條目數(shù)的漏檢率與數(shù)據(jù)量的漏檢率2個方面；記算法檢測出的大流條目數(shù)為Nf，網(wǎng)絡(luò)流量中實際的大流條目數(shù)為Nr，則流條目數(shù)的漏檢率FN=(Nr-Nf)Nr；記算法檢出的大流數(shù)據(jù)量為Vr，網(wǎng)絡(luò)流量中實際的大流總數(shù)據(jù)量為Vr，則數(shù)據(jù)量的漏檢率FV=(Vr-Vr)Vr.

4.1 最大并發(fā)高速流的數(shù)目

為了便于硬件實現(xiàn)，LRE-DH算法采用固定存儲空間分配的方案.對于固定存儲空間分配，最大并發(fā)高速流的數(shù)目是其存儲空間的分配依據(jù).圖2分別給出了15 min各時間段內(nèi)速率門限為帶寬容量1%,0.1%,0.01%,0.001%的最大并發(fā)高速流的數(shù)目.

Fig. 2 Maximum number of concurrent flows under different time and rate threshold圖2 不同速率門限下各時間段的最大并發(fā)高速流的數(shù)目

從第3節(jié)中定理1的證明過程可以看出，鏈路的傳輸速率、不同字節(jié)數(shù)的數(shù)據(jù)流的創(chuàng)建順序、不同數(shù)據(jù)流間報文的到達順序等因素都會影響最大并發(fā)高速流的數(shù)目.因此圖2中不同時刻的最大并發(fā)高速流的數(shù)目存在很大的變化；T2017,T2016,T2015,T2014的平均傳輸速率比T2011,UNV高出一個數(shù)量級，其最大并發(fā)高速流的數(shù)目也比T2011,UNV高一個數(shù)量級.

圖3給出了15 min內(nèi)最大并發(fā)高速流的數(shù)目與理論上限的對比，其中最大并發(fā)流數(shù)目的理論上限是根據(jù)定理1計算出的.實際上，網(wǎng)絡(luò)上不同數(shù)據(jù)流的報文是交替?zhèn)鬏數(shù)?，當多個高速流輪流傳輸數(shù)據(jù)時，通常超過速率門限Cm的并發(fā)高速流數(shù)目不超過m個.

Fig. 3 Maximum number of concurrent flows under different rate threshold圖3 不同速率門限下最大并發(fā)高速流的數(shù)目

根據(jù)第2節(jié)的網(wǎng)絡(luò)流量特征分析，選取0.01%和0.1%鏈路容量作為大流檢測的速率門限.使用0.01%作為速率門限時，對于網(wǎng)絡(luò)流量數(shù)據(jù)T2014,T2015,T2016,T2017分別分配4 000個流條目空間；對于網(wǎng)絡(luò)流量T2011,UNV分別分配800個流條目空間.當使用0.1%鏈路容量作為速率門限時，針對T2014,T2015,T2016,T2017分別分配了400個流條目空間；為T2011,UNV分別分配了120個流條目的存儲空間.

4.2 d-Left散列子表數(shù)對LRE-DH算法準確性的影響

通過限制d-Left散列的子表數(shù)目，可以確保LRE-DH處理算法最差情形下的處理性能，但這也導致了數(shù)據(jù)流的漏檢，根據(jù)3.2節(jié)中的理論分析及4.1節(jié)中測出的最大并發(fā)高速流數(shù)目，圖4給出了高速流漏檢率理論期望值.從圖4可以看出隨著d-Left散列子表數(shù)的增加，高速流漏檢率逐漸下降，尤其是在Hash表的負載較輕的情況下，漏檢率的下降趨勢非常明顯.

Fig. 4 The theoretical FNR of high rate flows圖4 高速流漏檢率的理論值

本節(jié)通過真實網(wǎng)絡(luò)數(shù)據(jù)通過仿真實驗測試了d-Left散列的子表數(shù)對LRE-DH檢測算法漏檢率的影響.通常一個數(shù)據(jù)流至少包含一個滿窗口尺寸的數(shù)據(jù)量時，才值得去進行流量的管理與控制，因此選取64 KB作為一個大流檢測的數(shù)據(jù)量門限值；另外根據(jù)第3節(jié)的網(wǎng)絡(luò)流量特征分析，少量的數(shù)據(jù)流超過了2 MB，因此還選擇2 MB作為大流檢測的一個數(shù)據(jù)量門限.

圖5給出了在相同存儲開銷的條件下，隨Hash桶容量增加LRE-DH算法流條目數(shù)漏檢率的變化趨勢.通過圖4與圖5對比可以看出：根據(jù)網(wǎng)絡(luò)數(shù)據(jù)測試得到的大流漏檢率低于高速流漏檢率的理論值，尤其是T2017,T2016,T2015的大流漏檢率明顯低于其理論值，這是因為T2017,T2016,T2015的大部分高速流只含有較少的數(shù)據(jù)量.從圖5可以看出，隨Hash桶容量的增加，無論是LRE-DH算法流數(shù)目的漏檢率還是數(shù)據(jù)量的漏檢率均逐漸降低.其中圖5分別給出了檢測門限為64 KB,0.01%,64 KB,0.1%,2 MB,0.01%,2 MB,0.1%時流數(shù)目與數(shù)據(jù)量漏檢率的變化趨勢.從圖5可以看出，在Hash桶容量不小于4的情況下，數(shù)據(jù)量的漏檢率均低于0.3%.

定理2對漏檢率的分析是建立在大流的報文數(shù)與字節(jié)數(shù)線性相關(guān)的基礎(chǔ)上的，從圖6可以看出大流的報文數(shù)與字節(jié)數(shù)高度線性相關(guān)，因此定理2的理論分析具有較高的準確性.

Fig. 5 The variation trend of the FNR of identifying algorithm with the increase of Hash capacity圖5 檢測算法的漏檢率隨Hash桶容量增加的變化趨勢

4.3 LRE-DH與其他算法檢測準確性的比較

本節(jié)選取了S-LRU,L-LRU,CSS,WCSS等算法與LRE-DH算法在檢測的準確性上進行比較.由于LRU派生算法主要依據(jù)流的數(shù)據(jù)量作為評價指標，而未考慮數(shù)據(jù)流的速率，即LRE-DH與S-LRU,L-LRU,CSS,WCSS算法的檢測標準不完全一致，因此只進行大流漏檢率的比較.對于LRU及其派生算法，每當報文到達，至少需要4次以上的存儲器訪問；因此選取子表數(shù)為4的LRE-DH算法與S-LRU,L-LRU,CSS,WCSS算法進行漏檢率的比較.

使用網(wǎng)絡(luò)流量數(shù)據(jù)T2011,T2014,T2015,T2016,T2017,UNV測試了不同數(shù)據(jù)量門限(64 KB,128 KB,256 KB,512 KB,1 MB,2 MB,4 MB)和速率門限(0.01%,0.1%)組合下的5種算法的漏檢率(見圖7).

其中圖7(a)是速率門限為0.1%的帶寬容量下得出的測試結(jié)果；圖7(b)是速率門限為0.01%的帶寬容量下得出的測試結(jié)果.

從圖7可以看出，LRE-DH算法流數(shù)目的漏檢率和數(shù)據(jù)量的漏檢率比S-LRU,L-LRU,CSS,WCSS等算法要低.S-LRU算法漏檢率高的主要原因在于：這類算法主要根據(jù)短時期內(nèi)報文的命中率，而不是數(shù)據(jù)量的字節(jié)傳輸速率進行流的淘汰，同時報文大小并不是一致的，通常報文大小從幾十到1 500 B變化，所以在存儲空間不大的情形下，即使數(shù)據(jù)流具有較高的傳輸速率但單位時間內(nèi)的報文數(shù)相對較低時也會被淘汰，導致漏檢；通過采樣的方案，可以緩解由于大量突發(fā)小流的到達導致的漏檢，即S-LRU算法在采樣率設(shè)置適當?shù)那闆r下，可以獲得較好的準確性，但是采樣也會引入新的檢測誤差；L-LRU使用分級淘汰策略，可以進一步緩解突發(fā)小流對檢測準確性的干擾，盡量將包含數(shù)據(jù)量多的流保持在緩存中；所以從總體來看，與S-LRU相比，L-LRU算法具有較高的準確性.受存儲空間的限制，CSS算法在淘汰流條目時，會導致統(tǒng)計誤差逐步增大，而且流條目的淘汰依據(jù)報文的發(fā)送頻率而不是傳輸速率，因此會存在一定的誤差.WCSS算法通過窗口機制可以在一定程度上緩解CSS算法由于流條目的淘汰導致誤差的累計，但窗口的截斷機制也引入了新的誤差.而基于速率的淘汰機制可以有效抑制突發(fā)小流的干擾，將低速率的數(shù)據(jù)流及時從緩存中淘汰，因此LRE-DH算法相比上述算法具有較高的準確性.

Fig. 7 FNR comparison of different algorithms under different Rate_Threshold圖7 不同檢測門限下5種算法漏檢率的對比

Fig. 6 The correlation between the packets number and the bytes number in flows圖6 數(shù)據(jù)流的報文數(shù)與字節(jié)數(shù)的相關(guān)性

5 小 結(jié)

針對高速網(wǎng)絡(luò)中以流量管理與控制為主要目標的大流檢測，提出了低速流淘汰與d-Left散列相結(jié)合的大流檢測算法(LRE-DH).通過適當配置d-Left散列子表的數(shù)目，確保了LRE-DH檢測算法的準確性及最差情形下的處理能力.對所提出LRE-DH算法的存儲開銷、性能及準確性進行了理論分析；使用實際網(wǎng)絡(luò)流量數(shù)據(jù)測試結(jié)果表明：在相同存儲開銷下，隨著d-Left散列子表數(shù)目的增加，LRE-DH算法的漏檢率逐漸降低；在相似的性能及存儲開銷條件下，LRE-DH算法的準確性優(yōu)于S-LRU,L-LRU,CSS,WCSS算法.