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

李春強 董永強, 吳國新,

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

大量研究[1-4]表明：網絡中少數具有較大數據量的數據流生成了網絡的大部分流量，而其他大量的數據流的數據量總和僅占小部分的網絡流量；數據流在帶寬占用上也表現出不均衡性，其中少量具有較高速率的數據流消耗了大量的網絡帶寬[4].網絡中數據流的這種分布特征嚴重影響了網絡傳輸的有效性[4-6]，導致了數據流傳輸帶寬占用上的不公平性，對報文的傳輸時延產生了較大影響[7]，嚴重時甚至發生擁塞導致報文丟失.在網絡設備上，有效檢測出這些數據流，進行適當的管理與控制[8-11]，可以改善網絡傳輸的有效性：比如緩解網絡擁塞[12]、增加網絡的有效吞吐率、降低報文傳輸時延及報文丟失率、改善網絡傳輸的公平性[13]等.

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

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

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

1) 對來自實際網絡中流量數據的分布特征進行分析，為基于速率與數據量的雙門限檢測方案提供現實依據；

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

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

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

1 網絡流量特征

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

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

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

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

2 相關研究

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

2.1 無狀態流統計檢測方案

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

2.2 基于部分流統計的檢測方案

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

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

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

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

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

2.3 大流檢測的其他相關方案

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

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

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

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

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

定義1. 網絡中傳輸速率超過一定門限的數據流定義為高速流；所有高速率構成的集合稱為高速流集合.

定義2. 網絡中數據量超過一定門限的數據流定義為長流；所有長流構成的集合稱為長流集合.

定義3. 網絡中同時滿足高速流和長流特征的數據流定義為大流；所有的大流構成的集合稱為大流集合.

為了改善網絡傳輸的有效性，需要對網絡中大流進行控制.為了有效檢測出網絡中的大流，避免將小流誤識別為大流，本文采用了部分流統計的檢測方案.該方案的基本思路為：當已存儲的數據流有新報文到達時，計算出數據流的傳輸速率與數據量，若數據流的傳輸速率與數據量均達到給定門限時，將其標識為大流.當淘汰緩存中一條數據流為新數據流分配存儲條目時，根據緩存中已存儲數據流的傳輸速率選出需要淘汰的數據流條目.

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

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

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

3.2 LRE-DH檢測算法及分析

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

d-Left散列表中包含d個子表，為了便于分析與說明，對d個子表從0到d-1進行編號.網絡中新的報文達到時，提取報文的頭部字段生成流標識符，以待查的流標識符為輸入使用d個不同的Hash函數生成d個索引，分別在d個子表中相應的Hash桶進行查找；若找到對應的流條目，則進行字節數的累加，并判斷數據量是否達到大流的數據量門限，若達到數據量門限則再計算流速率是否達到大流的速率門限.若未發現新收到報文對應的流條目，從編號最小子表的Hash桶開始判斷是否存在空閑的存儲空間，若存在空閑的存儲空間，則將新流的條目插入到其中.若沒有可用的存儲空間，則在當前新流Flow對應的d個子表的Hash桶中找出傳輸速率最小的流minFlow，如果該數據流的傳輸速率小于淘汰門限，則將該流淘汰，釋放后的空間分配給當前的新流Flow，記錄新流Flow的生成時間及其字節數；如果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]對應的Hash桶中找到Flow對應的條目)

⑦Flow.Size+=Packet.Size;

⑧ If (Flow.Size≥Size_Threshold)

⑩Flow.Rate=CalcFlowRate(Flow);

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

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

(1)

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

(2)

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

(3)

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

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

證明. 流檢測結構AF中的n-1個數據流記為fi(1≤i≤n-1)，其生存期為Ti(1≤i≤n-1)且Ti>Ti-1(2≤i≤n-1)，字節數為Si(1≤i≤n-1)，顯然Si≥Pmin.若新收到的報文屬于已存儲在AF中的流，則AF中的流數目不會增加，假設新收到的報文不屬于已存儲在AF中的流，其大小為Sn，Tn為接收該報文花的時間，記新創建的數據流為fn.設流fn創建后，存儲在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，結合式(12)得出：

(13)

由式(13)得出：

(14)

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

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

(15)

證畢.

定理1給出的是最大并發高速流的理論上限，這一上限在下面3個條件同時成立時才能取得.這3個條件是：1)網絡設備以線速速率從鏈路上接收報文；2)數據流按照數據量從大到小的順序依次創建；3)不同數據流的報文傳輸過程中不存在交叉.實際上，網絡鏈路不會長時間持續工作在線速速率狀態下；而且任何類型的網絡鏈路都會對最小報文的大小有限制；此外鏈路上不同數據流的報文通常是交替傳輸的，不存在交叉的概率極低.因此網絡中最大并發流的數目通常遠小于理論上限.

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

(16)

由式(16)得出：

(17)

證畢.

由于報文是網絡設備收發與處理的基本單位，所以定理2從報文而不是字節數的角度出發分析了大流的漏檢率，這一分析的準確性是建立在大流的報文數與字節數線性相關的基礎上的.從定理2可以看出：隨著大流數據量的增加，任一大流被漏檢的概率逐漸降低.

4 實驗與評價

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

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

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

4.1 最大并發高速流的數目

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

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

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

圖3給出了15 min內最大并發高速流的數目與理論上限的對比，其中最大并發流數目的理論上限是根據定理1計算出的.實際上，網絡上不同數據流的報文是交替傳輸的，當多個高速流輪流傳輸數據時，通常超過速率門限Cm的并發高速流數目不超過m個.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 小 結

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