主被動結合的網絡測量技術研究

王阿領，劉 淵，王曉鋒

1.江南大學 數字媒體學院，江蘇 無錫 214122

2.江南大學 物聯網工程學院，江蘇 無錫 214122

1 引言

隨著互聯網的快速發展和網絡規模的不斷擴大，網絡的異構性變得越來越復雜，人們對網絡行為的特征、網絡結構，以及網絡模型的理解會變得更加困難。因此在遇到網絡漏洞和網絡安全問題[1]的時候，很難及時地得到一個合理的解決方案，從而導致網絡的服務質量（Quality of Service）與用戶的實際需求產生較大的差距。在不完全了解目標網絡的協議、配置以及拓撲的情況下，通過網絡測量技術[2]能夠獲取當前的網絡性能測量信息。這些信息能幫助網絡研究者分析網絡行為、查看網絡潛在的網絡安全以及發現異常和定位異常，這對網絡運維有著非常重要的意義。如文獻[3]在N-Nakagami信道下，通過建立移動通信網絡模型，針對平均安全容量和安全中斷概率使用Monte-Carlo技術進行仿真驗證獲取相應的網絡性能測量信息，從而達到量化分析系統安全性能的目的。

網絡測量是指按照一定的方法和技術，利用軟件和硬件工具來測量網絡性能、檢測網絡質量和理解網絡行為的一系列活動的總和。一般常用的網絡性能測量方法主要包括主動測量[4-9]和被動測量[4-9]：

（1）主動測量就是按照較小的時間間隔向待測網絡中發送探測數據包，通過對主機的反饋信息做出判斷，從而得到網絡端到端的行為信息。一般情況下，對網絡端到端的延遲、丟包率、路由以及網絡拓撲的測量都是采用主動測量方式。如Ping[5]可以獲得網絡的連通狀況，從而得到往返延遲、丟包率等性能參數。如Traceroute[10]主要是用來獲得網絡端到端路由信息。Pathload[5]通過UDP協議發送探測數據包隊列獲得可用帶寬的性能參數。

（2）被動測量不需要向網絡中發送探測數據包，而是通過兩點監控或者單點監測的方式，在相應的網絡節點上部署網絡探針作為被動監測設備，監聽和捕獲經過測量設備的網絡信息數據流，并采集真實的數據鏈路信息。如網絡帶寬、路徑吞吐量[5]等參數使用的是被動測量方式。被動測量工具和技術主要有Sniffer（嗅探器）、Wireshark、WinCap、Network General、SNOR[4]等。被動測量不需要向網絡發送探測數據包，所以一般不會對網絡本身的運行產生影響。

主動測量和被動測量都有各自的優勢。主動測量會向網絡中注入探測流量包，導致測量有偏差；而被動測量方式可擴展性不強，難以對端到端網絡行為進行整體地理解和分析。由于網絡丟包率和路由信息能夠比較直觀地反映網絡性能和網絡結構，因此采用主動和被動相結合的測量方式可以更準確地獲得網絡丟包率和路由信息測量結果。該方式不僅保持了主動測量和被動測量各自的優點，更使得測量結果能更好地反映網絡的真實情況，對理解網絡性能和網絡結構具有非常重要的意義。同時，也能夠能達到簡化網絡運維、增強網絡魯棒性[11]的目的。

2 主要工作

目前針對網絡丟包率和路由信息測量的研究成果有很多。文獻[7]提出一種基于自適應采樣的丟包率測量方法，利用時延和丟包率之間的相關特性調整主動發包測量周期。探測周期的調整采用減半和倍增的方式，并設置最大探測周期為5 s，最小探測周期為0.05 s。此方式在測量精度和測量時間開銷上都較好的折中，能有效地降低發包探測量以及丟包率測量誤差。文獻[12]提出一種貪婪啟發式擁塞鏈路丟包率范圍推斷算法，借助多時隙路徑探測，避開單時隙對時鐘同步的強依賴。代替傳統以瓶頸鏈路作為擁塞鏈路定位的方法，通過聚類方式循環推斷擁塞鏈路丟包率的范圍。相對于通過網絡吞吐量和時延信息推測鏈路情況，此方式魯棒性較強。但是算法的時間復雜度較高，比較適合規模較小的鏈路。文獻[10，13]提出一種基于軟件定義網絡的主動測量的方式。在控制器與交換機之間采用OpenFlow進行通信，讓源交換機發出特定的測量報文序列，通過SDN 網絡逐級跳轉至目的交換機。目的交換機在收到探測報文后返還給源交換機之后，利用控制器周期輪詢交換機上的數據流并統計測量數據，獲得時延抖動、丟包率等重要網絡性能參數。此方式雖然測量的丟包率結果比接收端測量得到的背景流量丟包率較低，但是此方式采集粒度較大，沒有考慮往返網絡測量數據包的匹配與處理。

文獻[14]提出基于接觸圖的預計算路由策略和動態路由響應機制，利用主動發包的方式，對測量的數據流進行粒度匹配。此方式需要預先建立一個鄰接網絡節點結構圖，并對網絡節點的權值進行標記。但是這種方法時間復雜度較高，比較適合規模較小的網絡。文獻[15-16]提出基于流粒度生成的接觸圖路由算法，通過捕獲探測數據包對數據流進行逐跳跟蹤，并輸出完整的路由跟蹤路徑。但是這種方式同樣需要提前構建好網絡拓撲節點數據庫，并且每次遍歷節點都要重新啟動路由，測量周期較長，時間復雜度也比較高。文獻[17]提出一種基于背景流量感知的主被動結合的Traceroute測量算法，當網絡中沒有流量時，采用主動測量的方式周期性地向目標網絡發送探測數據包；當網絡中有流量時，采用被動測量方式監聽目標網絡。此方法雖然一定程度上降低了因背景流量帶來的測量誤差，但沒有具體說明主動測量和被動測量之間的觸發和調度機制。文獻[18]采用主動測量的方式，預先建立一個鄰接網絡節點結構圖，對網絡節點的權值進行標記，并以Dijkstra算法為基礎增廣每個信宿節點的路由集。在路由尋路探測過程中設置一個組播延遲上界，利用延遲ts作為路徑長度的度量，將延遲過大的路由舍棄。但是理論上延遲上界往往使網絡達不到最大的組播容量，所以每次尋路都需要分離經過相同的信宿節點。

本文在分析目前現有的針對網絡丟包率和路由信息測量技術的基礎上，提出了一種主被動結合的網絡測量技術。在網絡鏈路中合理地設置被動監測設備和軟件，實時監聽捕獲的網絡數據報文信息。被動測量將捕獲采集到的數據信息經控制器進行哈希過濾、分類和統計計數，最終進行匹配和篩選。當匹配到有效的數據信息時，則會觸發引導丟包率和路由信息測量任務的執行。與傳統的網絡測量技術相比，主被動結合的網絡測量技術能夠在壓縮測量規模的同時還保持了測量精度的穩定。對于規模較大或較小的網絡都適用。在測量網絡丟包率時，本文提出了一種周期動態調整的主動發包方式，以降低網絡突發情況下持續丟包對測量結果產生的影響。文獻[7]采用的是減半或者倍增的發包調整策略，但是這種調整幅度是幾何量級的，相比較一些需要快速測量丟包率的網絡應用，此方式調整周期的相對誤差率超過20%。本文采用的是一種周期動態調整的發包策略，利用時延和丟包率之間的相關特性判定網絡是否處于突發時段，并據此設置兩個動態調整參量和調整區間，動態調整參量取調整區間內的隨機值。相較于幾何形式的發包調整策略，動態參量隨機值的調整策略誤差抖動較小，穩定性和準確性都較高。由于高速網絡吞吐量較高，突發丟包并不頻繁。因此，本文研究并采用基于泊松分布的丟包率采樣方式，相比較一般的周期采樣方式，采樣樣本的準確率較高。

在測量網絡路由路徑信息時，本文提出一種多路徑動態路由測量算法，目的是減少路由尋路探測跟蹤時間，提升單位時間內的路由探測效率。針對已經探測過的目標網絡節點不再重復地發送探測數據包，以降低主動發送探測包的時間開銷。與文獻[14]、文獻[15]和文獻[18]相比，本文最大的優勢在于不需要預先建立一個鄰接網絡節點結構圖，在主動測量任務執行之前就已經將無關測量的數據過濾掉，提煉并壓縮了測量的有效數據量。并且算法在執行過程中匹配的相關指標參量較少，減少了路由尋路執行過程中的算法迭代次數，因而算法的時間復雜度相對較低。文獻[18]以Dijkstra 算法為基礎增廣每個信宿節點的路由集，將延遲較大的節點舍棄。而本文則利用棧的方式記錄探測尋路路由信息，根據設置的時延閾值將匹配遍歷的節點進行入棧和出棧操作，其算法的平均時間復雜度為O(knlgmn)。此方式在尋路探測過程中不會額外增加路由負載。

3 主被動結合的網絡測量關鍵技術實現

針對本文中具體的研究內容，搭建了一個基于主被動結合的網絡測量實驗測試環境，并部署相應的硬件和軟件設備。測量的網絡數據均來自于真實的校園網絡。相應的硬件和軟件設備主要包括服務器、Open-Flow 交換機、控制器、被動監測設備Netflow、兩臺可供實驗操作的控制平臺以及監測軟件Wireshark和網絡仿真器NS3（Network Simulator version 3）等。

3.1 主被動結合的網絡測量技術描述

本文提出一種主被動結合的網絡測量技術，其主要思路是：通過被動測量的結果觸發引導主動測量任務的執行，得到目標網絡丟包率和路由信息。主被動結合的網絡測量技術體系架構主要分為三個模塊：目標網絡、數據轉發和被動監測以及控制中心。目標網絡來源于真實的校園網網絡。數據轉發和被動監測控制的主要功能就是控制被動監測數據的轉發以及主動探測數據包的傳送。控制中心主要包括數據采集模塊、數據存儲和管理模塊、數據匹配和篩選模塊、丟包和路由測量模塊。連接目標網絡和控制中心的依次是OpenFlow交換機、網絡控制器以及被動監測設備NetFlow。基于圖1的主被動結合的網絡測量技術體系架構，其測量過程描述如下：

（1）目標網絡通過實體交換機和路由器接入本地服務器。通過使用OpenFlow測量控制協議[10，19-20]，實現控制器與其相連的OpenFlow交換機之間能進行數據流的轉發。即當源交換機收到目的主機發送的協議報文之后，根據數據流表對數據包進行識別，并由Netflow被動檢測設備和TCPDUMP進行捕獲。OpenFlow交換機依據內部的多級流表（flow table）和組表（group table）對被動采集的數據報文進行分類，經控制器傳送給數據采集模塊。數據報文信息在數據采集模塊中進行簡單的預處理。

（2）為了保證在高速鏈路中能及時地捕獲到探測數據包，報文的獲取、打時間戳、基于流的壓縮和轉發等過程均采用線程技術[21]來實現。捕獲的數據報文信息在數據采集模塊中通過簡單的預處理操作將包中的協議字段、標識位、源和目的IP地址字段、端口等讀取出來并進行分類。分類的數據報文信息會生成實時更新的本地聚合日志，并存儲在數據存儲和管理模塊中的本地MySQL數據庫中。本地聚合日志可供控制中心的Kali Linux控制平臺實時查看和調用。

圖1 主被動結合的網絡測量技術體系架構

（3）待監測任務結束后，更新的本地聚合日志依據匹配和篩選機制在數據匹配和篩選模塊中依次進行匹配和篩選，匹配和篩選機制基于正則表達式、散列匹配技術、以及可擴展的統計函數，篩選、過濾掉冗余和無效的數據信息，提取并保留實際有效的目標網絡信息。最終匹配生成的數據信息將觸發引導丟包率和路由測量任務的執行。

（4）在丟包和路由測量模塊中，控制平臺會根據構造不同類型的測量數據包分別對目標網絡的丟包率和路由信息進行測量。主動探測數據包類型的構造依據事先被動監測統計分類的數據流信息。在對目標網絡進行丟包率測量時，采用周期動態調整的主動發包方式，目的是降低因網絡突發而導致的持續丟包事件。最終根據測量的丟包率數據分析當前網絡性能；在對目標網絡進行路由路徑跳數跟蹤測量時，事先要在NS3網絡仿真軟件上進行仿真測試，測試其鏈路是否可通。隨后測量真實目標網絡的路由路徑信息，并統計測量結果。每次測量的路由路徑跳數信息會實時傳送至控制平臺。

3.2 基于正則表達式的數據信息處理

傳統的網絡測量技術研究主要是基于抽樣技術和數據流技術[13]，通過犧牲測量精度來壓縮采樣測量數據的規模，可拓展性不強，在實際應用中受到很大程度的制約。而本文采用的是一種主被動結合的網絡測量技術，采用基于正則表達式的過濾和篩選機制從被動采集的海量測量數據中過濾掉冗余和無效的數據報文信息，保留實際有效的測量信息。此方式不僅壓縮了采樣測量的數據規模，同時保持了測量精度的穩定。被動捕獲的一些冗余和無效的數據報文信息直接被內核丟棄掉，而有效的數據報文信息則需要經過控制中心的數據采集平臺進行哈希過濾、分類與計數處理生成本地聚合日志。由于被動測量的數據包粒度很細，則測量記錄產生的數據量比較龐大，所以要從本地聚合日志中匹配和篩選出有效的測量數據，則必須要調用事先編寫的基于正則表達式的匹配和篩選算法，實現對本地聚合日志的數據處理和分析的能力。開發語言使用的是Python，采用CentOS 7操作系統自帶的編譯器對算法進行編譯和執行。

探測數據信息匹配的目的一方面是為了對本地聚合日志做進一步過濾和篩選，保留所需要的真正有效的探測數據包。同時，對被動測量觸發引導主動測量任務的執行起到了輔助作用，為下一步主動測量獲取網絡丟包率和路由信息做準備。與傳統的數據信息挖掘方式相比，基于正則表達式的數據信息匹配和篩選機制實現方式相對方便，一方面不需要額外的硬件支持，另一方面算法在匹配和篩選時循環迭代比較的次數相對較少，降低了其執行過程中的時間復雜度。

數據信息的匹配和篩選策略：建立一個實時更新的動態采集數據存儲數據庫和一個動態調用的匹配規則庫，針對聚合日志中的每條數據都進行細粒度的匹配、篩選、過濾和分類。探測數據的匹配和篩選算法遵循正則表達式，匹配的內容主要包括本地IP地址、目標IP地址、端口以及數據包類型等信息。數據的篩選基于哈希函數并依據篩選條件對特定的數據流信息按照指定的字段依次過濾，篩選掉與測量無關的冗余數據，以達到降低數據耦合度的目的。圖2 描述的是數據信息的匹配和篩選過程。

算法1 描述了測量的數據信息匹配和篩選的具體算法。對已經過濾掉的數據進行統計和分類，將源端和目的端信息在總控中心映射為端信息EPI（End Point Information），即IP 信息、端口信息等。并用組表（group table）的形式存儲數據，目的是方便引導主動測量任務的執行。

算法1數據信息匹配和篩選算法

1.Receive_Match（）{

圖2 數據信息的匹配和篩選過程

2.whilepacketsis inLocate_log

3.do setmatch_process（）

4.Target.addr（）

5.Target.ports（）

6.Target.type（）

7.whileTarget.addris not in Match andportnot inrange

8.do setfilter_algorithm（）

9.ifTarget_add.freq>1

10.SkipnextTarget.addr

11.else

12.do setClassify_process（）

13.Target.type=TRUE

14.end if

15.end while

16.resetreceive packets

17.end while

18.}

當數據匹配和篩選過濾結束后，通過主動發送探測數據包的方式測量目標網絡的丟包率和路由信息。針對已經探測過的目標網絡節點不再重復地發送探測數據包，以降低主動發包對測量結果的影響。根據本地聚合日志中不同類型的數據信息構造不同類型的探測數據包，如TCP類型、UDP類型、ICMP類型等。

3.3 基于周期動態調整的丟包率測量

丟包率是指在某段時間內由源主機向目的主機發送的數據包中丟失的數據包占傳輸總數據包的比率，鏈路丟包率能及時反映網絡傳輸性能以及由網絡突發[22]導致的網絡擁塞[23]等問題。假設從源端發送的數據包個數為Packets_start，達到目的端的數據包個數為Packets_end，則數據包在單條鏈路上的丟包率為：

丟包率的測量方法主要是主動測量和被動測量，但是被動測量無法取得端到端的路徑信息，所以一般鏈路丟包率大多采用主動測量的方式。主動測量丟包率的基本過程是在指定時間內，周期性地由源端向目的端持續發送探測數據包，若某個探測包在規定的時間閾值內沒有收到響應數據包，則記為一次丟包事件。如Ping、BADABING[8]、Iperf均采用此方式。丟包率的測量需要線程監聽目標流的首尾交換機，根據兩個交換機節點的抽樣結果進行估算和后繼測量。每一次測量任務結束，任務線程都會記錄相應的測量結果，以便回溯到上層調用和查看。

3.3.1 網絡突發判定及發包周期調整

在IP網絡中，由于網絡流量的波動具有不規則的特性，所以丟包事件一般是由網絡流量的突發和急劇波動造成的。網絡流量的突發和急劇波動往往會導致網絡在短時間內出現擁塞，增加網絡鏈路的往返時延，從而導致探測數據包的丟失。由于網絡流量具有隨機突發性，因此丟包也具有隨機突發的特性。在使用主動測量方式測量鏈路丟包率時，若測量周期過大，則丟包率的測量結果不準確；若測量周期過小，則會影響網絡端到端的測量負載，導致測量結果出現偏差。所以要準確地測量鏈路丟包率，就需要一種周期動態調整的發包策略。本文在研究過程中采用周期動態調整的主動發包測量方式，根據網絡是否處于突發時段來適度調整主動發包的測量周期。

假設丟包測試實驗共執行了N次測量任務，則探測時延結果序列為：{T1,T2,…,TN}。其中di表示每次主動發包后探測得到的平均時延。如果發送第i次探測包產生丟包，則設置Ti的值為0，否則Ti的值不變。只判斷Ti的值是無法判斷當前測量階段是否屬于丟包突發時段，此時根據排隊時延定義一個丟包突發指標PT，如公式（2）所示：

其中，Tmin是第i次測量得到的往返時延的最小值，Tpre表示所探測到的前一個丟包事件中時延的平均值。公式（2）中的指標函數可視為判斷當前時延信息是否發生丟包突發時段。當Ti的值為0時，表示當前探測已經產生時延，將PT的值置為1；當Ti的值為不等于0 且PT的值小于1 時，則表明第i次發包探測所產生的平均時延小于前一個丟包事件的最小排隊時延，此時鏈路上的丟包事件屬于突發；若Ti的值為不等于0且PT的值大于1 時，則表明第i次發包探測所產生的平均時延大于前一個丟包事件的最小排隊時延，即連續發生丟包事件，則會增加下次發包丟包的概率。所以需要增加下次發包的探測周期，減小因網絡突發導致的測量誤差，使后續發包測量任務趨于穩定。

假設當前測量時間周期為ΔTi，引入兩個周期動態調整參量β1、β2，其中β1∈(0,1)、β2∈(1,2)。β1是0到1 之間的隨機數，而β2是1 到2 之間的隨機數。若當前測量產生連續丟包事件時，則將下一個測量周期調整為ΔTi+1=ΔTi×β2；若測量趨于平穩時，則將下一個測量周期調整為ΔTi+1=ΔTi×β1，以提高測量精度。據此可定義每次測量周期最大時延閾值特征函數為式（3）所示：

其中，ΔTi表示當前發包測量周期，λ表示前i次測量周期的均值。φ(t)為規定的第i+1 次發包測量時最大約束時延閾值。

3.3.2 基于泊松分布的周期采樣方式

依據以上網絡突發引起的鏈路丟包情況，對發包周期做了動態調整，主動發包測量會在短時間內向目標網絡發送大量的探測數據包，能夠在網絡突發時段采集到真實的丟包數據。一般高速網絡吞吐量較高，突發丟包并不頻繁。因此，本文研究并采用基于泊松分布的丟包采樣方式，采集實際測量的鏈路丟包率。當出現往返時延較大且連續丟包事件時，則減小采樣間隔，使采集的丟包率數據更為準確；當時延較為平緩時，則增大采樣間隔，使其丟包率的測量保持較小的網絡負載。

泊松分布的采樣間隔特征函數如公式（4）所示：

P表示采樣的樣本間隔，λ表示前i次測量周期的均值。由于泊松采樣具有漸進性的特點，在平均采樣頻率不高時可以降低因網絡波動帶來的測量誤差，并提高丟包測量的準確性。

3.4 多路徑動態路由測量描述

3.4.1 路由路徑跳數測量策略

路由測量在網絡性能測量中占據著非常重要的一部分，對研究鏈路吞吐量、改善網絡負載均衡、理解網絡結構以及網絡行為等方面都具有非常重要的意義。選擇合適的端到端路由測量方式可以有效地提高路由探測的效率，減少因網絡負載帶來的影響。網絡路由測量一般采用的是以Traceroute[17]為主的主動測量方式。利用TTL記錄終端節點的值與起始節點值之間的差值確定單條鏈路的路徑跳數。一般一次目標網絡路由跟蹤的路徑跳數不超過30跳。文獻[15-16]提出基于流粒度生成的接觸圖路由算法，通過捕獲探測數據包對數據流進行逐跳跟蹤，并輸出完整的路由跟蹤路徑。但是這種方式需要提前構建好網絡拓撲節點數據庫，每次遍歷節點都要重新啟動路由，測量周期較長，時間復雜度也比較高。因此，此方法比較適合規模較小的網絡。

文獻[18]提出一種Dijkstra廣度優先搜索遍歷算法，實現從源端到目標網絡的路由測量。但是需要預先建立一個鄰接網絡節點結構圖，并對網絡節點的權值進行標記，從技術上來講工程量太大。一般復雜的高速網絡大都是基于網狀網絡結構，如圖3所示。若要對目標網絡節點進行理由跟蹤，則必須要考慮到鏈路的空間復雜度。據此，本文提出一種多路徑動態路由測量算法，探測目標網絡路由路徑跳數信息，采用此方式的目的是為了簡化路由探測規模、減少路由尋路探測跟蹤時間。

圖3 典型的網狀網絡結構

3.4.2 多路徑動態路由測量

在大規模的網狀結構網絡中，一般測量一個網絡節點經過單條路徑時的收斂時間在2～10 s 內。此時可定義單條路徑最大傳輸時間閾值為End_Time。如公式（5）所示：

其中Max_TranTime是指所有目標節點的最大傳輸時間；Packet_TranSize是指單次路由測量發送的數據包的大小；Max_Bandwidth是指當前網絡傳輸的最大帶寬，主要與目標網絡的鏈路吞吐量有關；Packet_Distance是指源節點和目標節點之間的通信距離；Packet_TranSpeed是指數據包的發送速度，也與鏈路帶寬和吞吐量有關。由于每條鏈路的傳輸距離都不相同，設置單條路徑最大傳輸時間閾值的目的是保證每條探測路徑都有足夠的探測時間。

依據多路徑動態路由路徑測量策略，將目標網絡測量的節點通過算法和數據存儲的方式加以實驗驗證。算法中所涉及到的數據變量如表1所示。

表1 算法中使用的相關變量

多路徑動態路由測量算法結合了Nmap SYN 主動發送探測包的方式，通過p0f 日志捕獲的方式跟蹤其路由路徑跳數。圖4 描述了利用多路徑動態路由測量方式探測尋路的執行過程。每次發包前均需按照不同協議的數據類型構造不同類型的探測數據包。探測數據包的預設信息主要包括源節點、目標節點、測量協議、端口等信息。在對數據包中的目標節點與探測節點進行匹配時，需要將節點的信息進行入棧操作。每一條探測路徑在探測時均需要打印遍歷節點，并記錄單條路徑的路徑跳數。若單條路徑的路徑條數沒有超過預設值且請求超時，則路徑跳數TTL的值減1進入下一路徑，對于已探測的節點不再重復發送探測包，并重復以上整個過程。直到發送的數據包中的探測節點與目標網絡節點匹配成功時，則表示路由探測跟蹤成功，輸出其路徑跳數。同時將TTL的值重新置為0，開始測量下一個目標網絡節點。如果在規定時間閾值內或者超過最大路徑跳數，則表示探測失敗，開始測量下一個目標網絡節點。重復以上整個過程，直至所有的目標網絡節點路由跟蹤測量任務結束。

探測路徑的選擇是隨機的，在數據鏈路探測過程中事先不考慮鄰近節點，只考慮路徑是否可達。若探測到目的節點，則執行進入下一個目標節點的路徑探測任務；否則，路徑節點退棧，進入鄰近節點路徑，重復以上操作直至成功匹配目標節點。多路徑動態路由測量算法如算法2所示。

圖4 多路徑動態路由探測尋路過程

算法2多路徑動態路由測量算法

輸入：Src_Nodes，Des_Nodes，Path_List，Stack_Nodes。

輸出：Stack_Nodes，TTL。

1.whileSrc_addrinSrc_NodesandDes_addrinDes_Nodes

2.StoreCurrent_time，Each_Hop

3.AddDes_addrinPath_List

4.AddDes_addrinStack_Nodes

5.TTL←TTL+1

6.whileCurrent_timein beforeEnd_Time

7.UpdateCurrent_time

8.CalculateCurrent_time，TTL

9.whileDes_addris not inPath_List

10.ifCurrent_timeis beforeEnd_Time

11.ifTTLis beforeEach_Hop

12.print→Stack_Nodes

13.whileCurrent_Timeis afterEnd_Time||TTLis afterMax_Hop

14.wai（tDeadLine）

15.Send_an_ICMP_Reques（ttimeout）

16.RemoveDes_addrfromStack_Nodes

17.TTL←TTL-1

18.ifPath_ListandStack_Nodesis not empty

19.UpdatePath_List，Stack_Nodes，TTL

20.CalculateCurrent_time，timeout.Number，TTL

21.iftimeout.Numberis afterFinal.Number||TTLis afterMax_Hop

22.Send_an_ICMP_Reques（tTracking failure）

23.else

24.print→Stack_Nodes&&TTL

25.End while

26.ResetCurrent_time，Each_Hop，TTL

文獻[17]一般情況下其路由尋路探測的平均時間復雜度為O(kn2)，而文獻[18]以Dijkstra 算法為基礎的路由增廣路經集探測方式其平均時間復雜度為O(khs(E+nlgn))。而本文提出的多路徑動態路由測量算法平均時間復雜度為O(knlgmn)。由于多路徑動態路由測量算法在執行過程中需要匹配的相關指標參量較少，所以此方式可以有效地減少路由尋路執行過程中的算法迭代次數，因而算法的時間復雜度相對較低。路由探測過程中其算法的時間復雜度受到循環次數k和探測的數據量n以及匹配比較次數m等綜合因素的影響。

4 實驗結果與數據分析

4.1 實驗設計與環境搭建

為了驗證通過引導被動測量結果引導主動測量的技術可行性和實驗數據的有效性，本文搭建了一個主被動結合的網絡測量實驗環境。包括兩臺Dell Power-Edge R730 2U 機架式服務器，兩臺 Intel?Xeon?CPU E5-2620 v3 處理器，內存 16 GB。一臺 OpenFlow 交換機，其中控制機通過帶內方式與OpenFlow 交換機相連。一臺操作系統為Centos 7的終端，用來采集和存儲網絡數據流。控制平臺采用的是基于Debian 的Kali Linux 操作系統。軟件工具包括Visual C++ 6.0、Wireshark、NS3 網絡仿真器以及網絡抓包工具TCPDUMP等。通過被動測量的結果觸發引導主動測量任務的執行，即對網絡丟包率以及路由信息進行測量。實驗事先需要在NS3網絡仿真器中進行仿真測試，測試目標網絡鏈路是否連通，隨后在真實測試環境下對目標網絡進行丟包率和路由信息測量。

4.2 數據信息匹配和篩選機制實驗驗證

本次測試實驗所采集的網絡數據集均來自混雜模式下的本地校園網網絡。采集的海量數據通過OpenFlow交換機轉發，處理器處理，經被動檢測設備檢測以及內核處理。目的是清洗過濾出冗余的測量數據，匹配篩選出真實有效的測量數據。本次測量時間共持續了20天，采集源端和目標網絡往返數據報文信息，以方便查看其往返數據包收發情況。測量數據結果如圖5所示。

圖5 往返數據包的收發測量結果

通過圖5 可知大部分收發的無效和冗余的數據包是被過濾器和系統內核丟棄，而匹配和篩選過的有效的數據包占比低于30%，說明本文提出的基于正則表達式的匹配和篩選算法效率較高，能夠將絕大多數無效或冗余數據包過濾掉。隨著測量時間的增加，在第11天前后過濾和被動捕獲的數據包數量均達到最大值，說明這段時間網絡收發的數據包的數量持續增加，網絡流量屬于突發時段，在這段時間最容易產生丟包。但在隨后一段時間內數據包的收發又趨于穩定狀態。數據匹配和篩選的主要目的是為了去除冗余數據，而保留真實有效的測量數據。為后續目標網絡丟包率和路由信息的測量做準備。

4.3 丟包率測量實驗驗證

在對鏈路丟包率進行測量時，本文采用周期動態調整的主動發包方式與文獻[8]提到的Ping 和基于BADABING 測量結果做對比，分析周期動態調整的丟包率測量方式的有效性和優勢。實驗將被動采集匹配和篩選過濾的125個目標網絡節點進行丟包率測量，發包時間周期采用周期動態調整的主動發包方式。而Ping和BADABING 則使用減半或倍增的周期發包方式，分別向目標網絡發送125個探測數據包，測量其鏈路丟包率。將測量得到的丟包率數據采用泊松分布樣本的采樣間隔獲取其丟包率數據。采樣得到的丟包率數據如圖6所示。

圖6 丟包率測量結果

圖6數據顯示周期動態調整的主動發包方式與Ping和BADABING測量方式所測得的丟包率對比結果。從圖6 整體可知，隨著探測數據包數量的增加，三種丟包率測量方式單位時間內丟包率也都出現峰值，說明探測數據包的短時擁塞對丟包率會產生一定的影響。測量初期丟包率均處于較低水平，而隨著探測數據包數量的增加，三種發包測量方式所測量得到的丟包率均呈現不規則的波動，說明網絡波動也會對鏈路丟包率產生影響。

待發包周期調整之后，丟包率也會隨之降低。據圖6可知，利用周期動態調整的主動發包方式在測量鏈路丟包率時，整體上所測得的丟包率的值均低于Ping 和BADABING 測量方式。通過數據統計計算，可知周期動態調整的主動發包方式與Ping和BADABING利用減半或倍增的周期發包方式相比，可以將鏈路丟包率降低60%以上；說明周期動態調整的發包測量方式能夠有效地調整主動測量的發包周期，降低探測鏈路的丟包率。更直觀地說明了動態參量隨機值的調整策略誤差抖動較小，比減半或者倍增的幾何發包周期調整策略更加穩定，降低鏈路丟包率的效果更明顯。同時也證明了泊松分布的采樣方式能夠比較準確地采集到真實測量的丟包率數據。真正實現了在壓縮采樣規模的同時保持了測量精度的穩定。

4.4 多路徑動態路由測量實驗驗證

本文在匹配篩選的所有目標網絡節點中隨機選取100 個進行路由跟蹤探測實驗，并按照文獻[20]提出的Traceroute測量方法和文獻[18]提出的Dijkstra路由測量方法以及本文提出的多路徑動態路由測量方法的測量結果進行對比分析。三種測量方法均規定單次路由探測最大路徑跳數均不超過30。并分別對三種測量方法所得到的路由測量結果進行分類統計，統計每次測試的路徑跳數以及總的測量時間開銷。測量結束后對所探測的目標節點路由信息進行分類統計和編號。

據圖7可知，三種路由測量方法最終成功跟蹤70個目標網絡節點。在測量同一目標網絡節點時，三種測量方法獲得的路徑跳數值相差很小。可以證明多路徑動態路由測量方法在測量目標節點路由路徑時其準確度較高，且路由尋路探測可行性較強。

圖7 路由路徑跳數測量結果

表2反映的是利用三種測量方式測量目標節點時，跟蹤成功的路徑跳數平均值、路由探測總的時間開銷和跟蹤成功的平均時間開銷之間的數據對比結果。從表2統計數據可知，多路徑動態路由測量方法與Dijkstra 和Traceroute測量方法跟蹤成功的路徑跳數的平均值分別為：15、16和18。可以看出多路徑動態路由測量方法比Dijkstra 和Traceroute 測量方法測量的路由路徑跳數的平均值都要少，說明多路徑動態路由測量方法在探測路由路徑時，能在一定程度上降低探測路徑的復雜度。由于多路徑動態路由測量方法算法開銷較小，故在探測時會以最短路徑作為路由跟蹤成功的探測路徑。三種測量方法路由探測總的時間開銷分別為：1 962 s、1 682 s、1 887 s，跟蹤成功的平均探測時間分別為：5.69 s、7.32 s、5.16 s。可以看出多路徑動態路由測量方法與Dijkstra和Traceroute 測量方法相比，雖然路由探測總得時間開銷相差不大，但是多路徑動態路由測量方法比Dijkstra和Traceroute測量方法跟蹤成功的平均路由探測時間都要低。多路徑動態路由測量方法與Dijkstra測量方法相比，探測成功的平均路由跟蹤時間降低了大約10%；與Traceroute 測量方法相比，探測成功的平均路由跟蹤時間降低了大約42%。據此次路由測試實驗數據結果可知，多路徑動態路由測量方法可以有效地降低路由探測過程中的復雜度，減少探測過程中的平均路由跟蹤時間。

表2 路由跟蹤測量結果

5 結束語

本文通過搭建一個主被動結合的網絡測量技術測試環境，并利用被動測量的數據結果觸發引導主動測量任務的執行。相比較與傳統的網絡測量技術，主被動結合的網絡測量技術能夠實現在壓縮測量規模的同時，還能保持測量精度的穩定。對于規模較大或較小的網絡都適用。此方式不僅保持了主動測量和被動測量的優點，使得測量結果能更好地反映網絡的真實情況，對理解網絡性能和網絡行為具有非常重要的意義。在對被動測量生成的本地聚合日志數據進行處理時，本文提出一種基于正則表達式的數據匹配和篩選算法，將采集到的無效和冗余的數據信息篩選過濾掉，保留有效的測量數據信息。與傳統的數據信息挖掘方式相比，實現方式相對方便，一方面不需要額外的硬件支持，另一方面算法在匹配和篩選時迭代比較的次數相對較少，降低了其執行過程中的時間復雜度。在對目標網絡進行丟包率測量時，本文研究并提出一種周期動態調整的主動發包方式測量鏈路丟包率，根據網絡是否發生突發來適當調整探測包的發包時間周期。相較于減半或者倍增的幾何形式的發包調整策略，動態參量隨機值的調整策略測量誤差抖動較小，相對來說比較穩定。隨后對測量的丟包率數據采用泊松分布的采樣方式進行采樣，獲取采樣樣本周期內的真實丟包率測量數據，降低因網絡突發導致的測量誤差。相比較一般的周期采樣方式，采樣樣本的準確率較高。在對目的網絡進行路由跟蹤測量時，本文研究并提出一種多路徑動態路由測量方法。與Dijkstra和Traceroute測量方法相比，多路徑動態路由測量方法測量得到的路由路徑跳數的平均值較小，且跟蹤成功的平均路由探測時間較少。由于算法在執行過程中匹配的相關指標參量較少，減少了路由尋路執行過程中迭代次數，因而算法的時間復雜度相對較低，故屬于一種輕型易用的路由信息測量方法。如何在減少路由跟蹤時間的同時，又能提高總體目標節點路由跟蹤的成功率，則是下一步工作要重點研究的內容。