網絡斷層掃描:理論與算法*

李惠康,高 藝,董 瑋,陳 純

(浙江大學 計算機科學與技術學院,浙江 杭州 310027)

隨著互聯網的飛速發展,網絡在組成結構、數據流量和商業用途等方面變得越來越復雜.如何認知這些網絡,對理解網絡時代下用戶行為有著重要意義.同時,這也是有效管理網絡、保證可靠網絡服務的基礎.網絡測量是指遵照一定的方法和技術,利用軟硬件工具來測試、驗證及表征網絡性能和狀態的一系列活動.網絡測量可以是對網絡性能的測量,如延時、丟包率、網絡流量[1],也包括對網絡拓撲[2]、路由信息等其他網絡特征的測量.它是理解和認識網絡行為的重要手段,在網絡建模、網絡安全、網絡管理和優化等許多領域都有廣泛應用[3].國內外學術界和研究機構對網絡測量技術進行了大量的研究,總體上,這些網絡測量技術一般采用分布式測量結構,在網絡內部的相關節點上,通過測量代理采集有關測量數據,如報文丟失率、延遲和流量等,這些測量數據將匯集到一個中心節點上,通過建立適當的數學模型,對測量數據進行分析和計算,從而實現對網絡系統的性能評估[4].這種網絡測量技術屬于網絡內部測量,與網絡體系結構和網絡協議密切相關,并且需要網絡內部相關節點的密切協作,具有較高的測量精確度.但也存在一些缺陷,主要表現在如下兩個方面:(1) 網絡測量依賴于特定的網絡協議(如TCP/IP 協議、SNMP 協議),無法實現與網絡結構和協議無關的測量;(2) 測量依賴于自治系統內部節點之間的協作,出于網絡安全和商業利益等原因,有些自治系統并不對外開放,難以實現內部節點的協作和信息交流,無法保證測量準確性.

為此,近些年來,國際上許多學術機構都在尋求其他途徑來研究網絡的整體性能及其相互影響,將已成功應用于醫學、地震學、地質勘探等領域的成熟理論和方法應用于通信網絡領域,衍生出了網絡斷層掃描(network tomography)技術[5].它是根據網絡外部(即網絡邊界)的測量信息來分析和推斷網絡內部的性能及狀態,是一種在沒有網絡節點協作的條件下,通過主動發包探測或被動收集網絡內部有用信息的新技術,結合數理統計方法,能夠有效地推測出網絡鏈路上的QoS 指標,如延遲分布、丟包率、吞吐率和流量等.

目前,網絡斷層掃描的研究主要集中于兩個方面:一是測量數據的收集,主要研究如何收集網絡內部相關的有用信息;二是測量數據的分析,主要研究如何根據收集的數據來獲取網絡內部的性能指標和運行狀態.本文在簡要介紹網絡斷層掃描基本概念和形式化表述的基礎上,從測量數據收集和測量數據分析兩個主要方面綜述了網絡斷層掃描的研究現狀與關鍵技術.隨后分析了已有網絡斷層掃描方法在實際應用中的核心缺陷,并系統介紹了針對這些核心缺陷近年來提出的最新理論及算法.最后,基于現有研究成果對網絡斷層掃描技術的發展趨勢和下一步的研究方向進行了討論.

1 網絡斷層掃描基礎

1.1 網絡斷層掃描的基本概念

網絡斷層掃描通過在網絡邊界上進行端到端(end-to-end)的測量,來推斷網絡內部狀態和通信行為.為此,基于網絡斷層掃描的測量方法包含3 個主要步驟:①網絡模型構建階段,明確網絡拓撲結構和網絡性能模型;② 測量數據收集階段,通過在網絡節點或邊界上部署具有監測能力的裝置(即監測節點),并采用主動測量或被動測量的方式,從監測節點上收集端到端的網絡測量數據;③測量數據分析階段,根據網絡性能模型建立性能推測方法,運用統計學理論對測量數據進行分析處理,從而推算出網絡內部性能指標.

網絡斷層掃描技術對網絡性能的推算依賴于監測節點的測量數據值,測量方式的不同,會影響到推算結果的準確性.根據測量過程中是否向被測網絡中注入額外的數據包,網絡測量方式可分為主動測量和被動測量[6].其中,主動測量通過向網絡中發送特定的探測數據包,并通過分析探測數據包在網絡中發生的特性變化,推算得到網絡內部性能和行為參數,比如鏈路時延和丟包率等性能指標;被動測量通過在網絡中部署監測節點(或數據包捕獲器),收集網絡節點或鏈路上的數據包信息,被動地監測網絡,獲知網絡行為狀況.被動測量方式不必向網絡發送探測數據包,不會占用額外的網絡資源.然而,被動測量要依賴所測量網絡節點上的負載情況及測量鏈路上的通信流量,從而使得其可用性較差,實現復雜性高,難以保證測量的準確性.

當前,網絡性能測量成為了網絡斷層掃描的一個主要研究目標.通過對網絡時延、丟包率和吞吐量等性能指標進行數據采集和統計,分析網絡特定范圍或端到端路徑的連通性及有效性,以便于發現網絡瓶頸,優化網絡配置,保障網絡服務質量.此外,通過網絡斷層掃描測量得到的數據,可用于網絡故障的定位,從而有助于網絡維護管理.

1.2 網絡斷層掃描的形式化表述

為了便于網絡斷層掃描方法的研究與設計,通常需要對網絡模型、測量目標和測量方法進行形式化的表述.下面將簡要介紹網絡斷層掃描在這幾方面常見的形式化表述方式.

首先,網絡模型是網絡斷層掃描的基礎,主要指在實現網絡斷層掃描技術時所采用的拓撲結構.為進行簡潔的描述,可用G=(V,L)表示被測網絡的拓撲結構.其中,V為網絡節點集合,L為網絡鏈路集合.每個節點表示一個計算機終端(terminal)、路由器(router)或者一個包括多個計算機/路由器的子網(subnetwork).任意兩個節點間的連接稱為路徑(path),每條路徑由一條或多條鏈路組成,任意兩個節點之間的直接連接(不需要中間節點)稱為鏈路(link),鏈路可以是單向的也可以是雙向的.每條鏈路可以是一條物理鏈路,也可以是幾條物理鏈路的抽象.對于如圖1 所示的網絡拓撲,其節點集合V={v1,v2,v3,v4},鏈路集合L={l1,l2,l3,l4,l5,l6},節點v1與v3之間存在5 條不經過重復節點的路徑:l5,l2l3,l1l4,l2l6l4,l1l6l3.

Fig.1 A sample network topology圖1 一個簡單網絡拓撲

為了獲得端到端的測量數據,網絡斷層掃描方法需要在網絡部分節點上部署監測節點.用集合M={m1,m2,…,mμ}表示網絡部署的監測節點,在這些監測節點上可以發送和接收探測數據包.相應地,網絡中其余的節點稱為普通節點,用集合N(N=VM)表示.依賴于網絡采用的路由策略,監測節點通過沿著某些測量路徑發送探測數據包的形式,推算出網絡節點及鏈路的性能指標和運行狀態.在給定網絡拓撲G和監測節點M的情況下,用集合P代表監測節點間的一組測量路徑.需要注意的是,不同的路由策略可能會產生不同的測量路徑集合.例如,當網絡所有節點都運行了源路由機制(source routing[7])時,監測節點能夠嚴格地控制和指定每一個探測數據包的路由路徑.因此,在源路由機制下,測量路徑P可以包含監測節點間任意形式的路徑.相反,當探測數據包的路由策略完全由網絡正常運行的路由協議決定時,測量路徑P只能包含監測節點間一組特定形式的路徑,如最短路徑.

對于一個含有n條鏈路的網絡G(即n=|L|),用表示G中的鏈路集合,以及用x=(x1,…,xn)T表示鏈路性能指標向量,其中,xi表示鏈路li的性能.給定監測節點間的一組測量路徑,用c=(c1,…,cγ)T表示測量路徑性能指標向量,其中,ci表示路徑pi的性能.在很多網絡應用中,鏈路性能指標是可以累加的(additive).例如,多條鏈路上的時延是單條鏈路時延之和;多條鏈路的原始丟包率雖然為單條鏈路丟包率的乘積,但在經過對數函數(log(·))轉換后,也可以表示成單條鏈路丟包率累加的形式.對于可累加的鏈路性能指標,一條測量路徑的性能值等于這條路徑上所有鏈路性能值的總和.因此,我們可以用一個線性方程組的方式將已知的路徑測量數據與未知的鏈路性能指標關聯起來:

其中,R=(Rij)為一個γ×n階的測量矩陣(measurement matrix),并且測量矩陣R的元素值要么為0,要么為1,即Rij∈{0,1}.具體地,當測量路徑pi經過鏈路lj時,Rij=1;否則,Rij=0.因此,在數據分析階段,網絡斷層掃描的目標是在給定R和c的情況下,通過求解線性方程組(1),獲得鏈路性能x的值.

當鏈路li的性能指標xi在線性方程組(1)中有唯一解時,稱鏈路li為可識別的(identifiable),否則稱li為不可識別的(unidentifiable).另外,當網絡G中所有鏈路都是可識別的,稱網絡G為完全可識別的(completely identifiable);否則,當網絡G中只有部分鏈路是可識別的,稱網絡G為部分可識別的(partially identifiable).基于線性代數理論,只有當方程組(1)的測量矩陣R列滿秩時(即rank(R)=n),網絡G才能是完全可識別的.即:為了確切地計算出網絡中n鏈路的性能x,網絡斷層掃描必須要獲得監測節點間n條線性無關的測量路徑的性能數據.

進一步地.當網絡測量的目標是判斷鏈路通信是否正常(即鏈路測量指標只有正常和失效兩種狀態)時,我們將用到布爾網絡斷層掃描方法(Boolean netowrk tomgoraphy).與常規網絡斷層掃描思想類似,布爾網絡斷層掃描通過測量監測節點間一組路徑的狀態,推斷出網絡內部鏈路的狀態.形式化地,用x=(x1,…,xn)T表示鏈路狀態向量以及c=(c1,…,cγ)T表示測量路徑狀態向量.與常規網絡斷層掃描不同的是,x和c為布爾向量,即元素xi和ci只有0 和1 兩種取值.當xi=1(或ci=1)時,表示鏈路li(或路徑pi)通信發生失效;反之,當xi=0(或ci=0)時,表示鏈路li(或路徑pi)通信正常.考慮到對于一條路徑pi,只有當pi包含失效鏈路時,pi才會發生通信失效,可以用如下方式將已知的測量路徑狀態信息與未知的鏈路狀態信息關聯起來:

其中,R=(Rij)為γ×n階的測量矩陣(measurement matrix),并且元素Rij∈{0,1}.“⊙”為布爾矩陣的乘積運算,即.布爾網絡斷層掃描的目標是在給定R和c的情況下,通過求解布爾方程組(2),獲得鏈路狀態x.同理,當鏈路li的狀態xi可以由方程組(2)唯一確定時,稱鏈路li為可識別的(identifiable).

需要說明的是:雖然方程組(1)和方程組(2)表述的是對鏈路性能和狀態的測量,但網絡中節點的性能和狀態可以等價轉換為與其關聯鏈路的性能和狀態,所以網絡斷層掃描方法仍然可以用方程組(1)和方程組(2)的形式來求解網絡節點的性能和狀態.

1.3 網絡斷層掃描的簡單例子

圖2 所示為一個包含7 個節點和11 條鏈路(鏈路l1～l11)的網絡拓撲,其中,m1,m2和m3為部署的3 個監測節點.為了測量出所有鏈路的時延,網絡斷層掃描方法在3 個監測節點之間構造了11 條測量路徑p1～p11.其中,1 條為m1與m2間的測量路徑,7 條為m1與m3間的測量路徑,3 條為m2與m3間的測量路徑.

Fig.2 A network topology with three monitors:m1,m2and m3圖2 部署3 個監測節點(m1,m2和m3)的網絡拓撲

用向量x=(x1,…,x11)T表示鏈路l1～l11的時延,用向量c=(c1,…,c11)T表示測量路徑p1～p11的時延,從而可以得到如下形式的測量矩陣R:

對于線性方程組Rx=c,由于測量矩陣R是列滿秩的(即rank(R)=11),所以鏈路時延x有唯一解,即x=R-1c.在圖2 中,盡管監測節點間還可以選取其他形式的測量路徑(如l2l5l7l9),但這些額外的測量路徑都是與已有測量路徑(p1～p11)線性相關的,即,其他形式的路徑都可以用已有路徑(p1～p11)線性表示.因此,從鏈路性能測量的角度來說,p1～p11是一組最優的測量路徑.此外,當我們任意移除一個監測節點(如m2)后,用剩余的7 條測量路徑(p2～p8)構成的測量矩陣將不是列滿秩的,即剩余的7 條測量路徑將不能保證所有鏈路的可識別性.因此,從鏈路性能測量的角度來說,m1,m2和m3是一種最優的監測節點部署方式.

從圖2 的例子中可以看出,監測節點部署和測量路徑構造(或選取)對網絡斷層掃描方法的有效性有著重要的影響.下一節我們將詳細綜述國內外在網絡斷層掃描監測節點部署和測量路徑構造等方面的研究進展.

2 相關工作

近些年,網絡斷層掃描作為網絡測量領域的一個研究熱點,得到了國內外學者的廣泛關注.總體上,網絡斷層掃描包含網絡模型構建、測量數據收集與測量數據分析這3 個主要步驟.其中,測量數據收集包含監測節點部署、測量路徑構造與選取.本節從監測節點部署、測量路徑構造與選取、測量數據分析與推斷這3 個方面對近些年國內外代表性的研究工作進行歸納分析,其中也包含對各研究工作網絡模型的闡述.

2.1 網絡監測節點部署

如何獲取網絡內部的有用信息,是網絡斷層掃描研究的重要組成部分.當前,網絡斷層掃描的測量對象一般可分為網絡狀態參數和網絡性能指標.其中,網絡狀態參數包含網絡節點的配置信息和網絡鏈路的狀態信息,網絡性能指標包括鏈路吞吐率、鏈路丟包率和鏈路時延等.這些指標反映網絡的實時運行狀態.根據測量對象的不同,網絡監測節點部署可以分為傳統網絡斷層掃描監測節點部署和布爾網絡斷層掃描監測節點部署.

2.1.1 傳統網絡斷層掃描監測節點部署

傳統網絡斷層掃描技術主要針對網絡性能指標的測量,即:基于監測節點間端到端的測量數據,推斷網絡內部鏈路性能指標.由于網絡端到端測量數據的收集依賴于網絡模型(包括網絡拓撲、網絡性能模型)和路由策略等的設定,當前的研究工作考慮了網絡斷層掃描在不同網絡模型和路由策略下的監測節點部署問題.

就網絡拓撲結構而言,通?？煞譃橛邢蛲負浜蜔o向拓撲兩種類型:在有向網絡拓撲中,兩節點間鏈路(如v1v2)性能在其不同通信方向上(如v1→v2和v2→v1)具有不同的表現;相反,在無向網絡拓撲中,兩節點間鏈路性能在其不同通信方向上有相同的表現.對于有向網絡拓撲的鏈路性能測量,Xia 等人[8]證明了除非網絡中所有的節點都是監測節點,否則并不是所有鏈路的性能指標都是可測的.Gurewitz 等人[9]進一步證明了:當只使用環路形式的測量路徑(measurement cycle)時,即使在網絡中每個節點都是監測節點的情況下,仍然不能準確測量出所有鏈路的性能指標.對于無向網絡拓撲的鏈路性能測量,文獻[10-13]提出了基于探測包往返時間RTT(round-trip time)逐跳式(hop-by-hop)地測量鏈路時延的方法.該方法需要網絡所有節點都運行了網際控制報文協議(ICMP).然而在有些實際的網絡中,并不是所有的節點都允許使用ICMP 協議.此外,受因特網路由協議以及ICMP 協議的限制,探測包的往返路徑可能是不對稱的,從而難以保證其測量結果的準確性.由于逐跳測量方法在應用上存在的缺陷,很多工作研究了端到端(end-to-end)測量方法的可行性.

文獻[11,12]研究了基于網絡默認路由策略的鏈路性能測量問題,并證明了部署最少數量監測節點來獲得網絡中所有鏈路的性能指標是NP 難問題.文獻[13]進一步證明了:即使在部分節點可以控制其本地路由策略的情況下,部署最少數量監測節點來獲得網絡中所有鏈路性能指標的問題仍是NP 難的.文獻[14]研究了在給定網絡路由策略時的鏈路性能測量問題,并提出了一個有效的近似計算方法,以基于網絡節點的連接信息估算出一個自治系統內部鏈路的性能指標.Gopalan 等人[15]研究了當探測包路徑可控的情況下,基于網絡斷層掃描技術的鏈路性能測量問題.Gopalan 等人[15]還在分析鏈路性能可測性(link identifiability)、網絡拓撲和監測節點數量及位置三者之間關系的基礎上,提出了一種最優的監測節點部署算法,并通過使用環路形式的測量路徑進行探測包的發送和收集,從而計算出網絡所有鏈路的性能指標.由于很多網絡禁止兜圈子路由的方式,基于環路形式測量路徑的測量方法在應用中難以實現.因此,基于非環路形式測量路徑的鏈路性能識別問題受到了越來越多的關注.Ma 等人[16]推導了在僅僅使用非環路形式測量路徑的情況下,網絡中所有鏈路都可測的網絡拓撲結構特征,并設計了一個最優的監測節點部署算法MMP(minimum monitor placement)[17].基于對拓撲連通性的劃分,MMP 迭代地在每個連通分支上部署必要的監測節點,從而可以在線性時間內最小化監測節點的整體數量.這些早期工作為網絡斷層掃描技術的演變與改進提供了基礎和指導.

現有的大多數監測節點部署算法旨在實現整個網絡的可識別性,需要精確測量所有鏈路的性能指標.為了實現這一目標,即便最優的算法也可能需要部署數目不少的監測節點,如將ISP 網絡中,64%的節點部署為監測節點[17].因此,部分網絡可識別性(partial identifiability)問題受到了越來越多的關注.基于探測包可控路由的假設,文獻[18]提出了一個有效的判別算法DIL-2M,以快速地識別出一個部署有兩個監測節點的網絡中所有可識別的鏈路.基于該算法,文獻[19]提出了一個近似最優的監測節點部署算法GMMP,通過優化對給定數目監測節點的部署,從而最大化網絡中可測鏈路的數量.另一方面,注意到有些實際應用往往只需要獲取網絡某些鏈路的性能,如處在網絡關鍵位置上的鏈路.

為了提高網絡斷層掃描的靈活性,Dong 等人[20,21]提出了優先鏈路(preferential link)的概念,將網絡中需要測量的鏈路指定為優先鏈路.為了降低優先鏈路測量的復雜度及減小監測節點的部署范圍,Dong 等人首先提出了一種網絡拓撲裁剪算法Scalpel[20].Scalpel 包含兩個主要階段:第1 個階段,從原拓撲中裁掉不含優先鏈路的2-點連通分支(biconnected component)(如圖3(a)所示);第2 個階段,從第1 階段裁剪后的圖中裁掉一些邊緣的3-點連通分支(triconnected component)和環分支(cycle).需要注意的是:在剩余的拓撲圖中部署監測節點,可能無法達到在原拓撲圖中部署的效果.為了不影響監測節點部署的性能,Scalpel 會從每一個被裁剪的分支中選取一個輔助節點(如圖3(b)所示).在使用Scalpel 算法對原拓撲圖G進行裁剪后,得到一個剩余的拓撲圖Gt及輔助節點集合H.以圖Gt和節點集合H為輸入,Dong 等人進一步設計了最優監測節點部署算法OMA(optimal monitor assignment)[21],通過從圖Gt和輔助節點集合H中選取最少數量的節點作為監測節點,實現對原網絡拓撲G中所有優先鏈路的性能指標的測量.上述這些旨在實現部分網絡可識別性的監測節點部署算法有助于服務提供商和管理員以較小的成本滿足網絡測量需求,提高了網絡斷層掃描算法的靈活性.

Fig.3 Illustrative example for the two stages of topology trimming algorithm圖3 網絡拓撲裁剪算法包含的兩個階段的說明示例

2.1.2 布爾網絡斷層掃描監測節點部署

當服務提供商和管理員想要測量的是網絡狀態參數時,要用到布爾形式的網絡斷層掃描技術.其中,網絡內部運行狀態可以用有限個零散數值表示,例如,用“0”表示鏈路通信正常,用“1”表示鏈路通信故障.

網絡擁塞已成為網絡傳輸性能和擴展性的重要影響因素,及時準確地定位網絡擁塞,有助于網絡性能調優和協議設計.基于網絡中同時發生擁塞的鏈路數目較少的假設和給定的端到端路徑測量信息,文獻[22-24]使用壓縮感知技術來識別因特網中發生擁塞的鏈路.在算法的實現中,通過引入一個用于判斷鏈路通信正常與否的閾值,從而將鏈路性能小于閾值的數值轉化為零.通過壓縮感知技術,可以有效地恢復出鏈路性能大于閾值的數值,即識別網絡中擁塞的鏈路.對于鏈路通信故障的定位問題,文獻[25-28]利用概率統計方法從網絡中找出一組最少數量的鏈路故障,從而能夠完全解釋測量的端到端的路徑狀態信息.文獻[29,30]基于端到端的測量信息,使用貝葉斯方法計算網絡中每一條鏈路發生故障的概率.

上述研究工作對網絡允許的鏈路故障數目具有較嚴格的要求,在大規模網絡場景中,難以保證其有效性.針對特定形式的通信模型(如客戶-服務器),其網絡拓撲往往相對固定.Duffield 等人[31]提出了一種簡捷有效的鏈路故障定位算法,利用客戶端與服務器之間路徑的相似性,能夠基于少數端到端測量信息,定位網絡故障鏈路.進一步地,Ahuja 等人[32]形式化分析了網絡拓撲結構、監測節點部署和鏈路故障識別三者的關系,并推導了在使用包含環路的測量路徑時,鏈路故障的可識別性條件,并提出了一個最優監測節點部署算法,以準確定位出任意k條鏈路的通信故障.另一方面,有些工作關注于對網絡節點通信故障的監測和定位.文獻[33-35]研究了在不同探測包路由策略(任意可控路由、可控無環路由和不可控路由)下,網絡節點通信故障的定位問題.具體地,文獻[33,34]提出了有效的算法來計算對于給定的網絡拓撲和監測節點部署,在一個特定節點集合中,最多可以同時發生故障的節點數目,以及給定允許發生故障的節點數目時,可以明確推算出狀態的最大節點集合.針對采用客戶-服務器通信模型的網絡,He 等人[36]提出了有效的服務器節點部署算法,通過測量服務器節點與客戶端之間的路徑信息,從而最大化可定位節點故障的數量.該算法有利于拓展布爾網絡斷層掃描的適用范圍.更為一般地,Bartolini 等人[37]推導了在給定測量路徑數目、路由策略和網絡拓撲形式(如樹狀和網狀拓撲)等一般性信息的情況下,可以定位的發生通信故障節點的最大數量.該理論結果可以為網絡拓撲設計和路由選擇等操作提供參考和指導.

2.2 測量路徑構造與選取

在網絡斷層掃描中,端到端測量數據的收集取決于使用的測量路徑形式,不同的測量路徑很可能產生不同的測量數據,從而可能得到不同的測量結果.近些年,很多工作從幾何代數的角度研究了測量路徑的構造和選取問題.當測量路徑可以包含環路時,Gopalan 等人[38]提出了一種基于給定網絡監測節點的線性無關(linearly independent)測量路徑構造方法,并形式化證明了算法構造的測量路徑是監測節點之間存在的一組最大數量的線性無關路徑.該算法為基于環路測量路徑的網絡斷層掃描技術(如最少監測節點部署[18])的實際應用奠定了基礎.當測量路徑不允許包含環路時,Wing 等人[39]推導了不同網絡(有向和無向拓撲網絡)中線性無關路徑數目的界限值.

另一方面,Ma 等人[40]提出了一種具有多項式時間復雜度的無環測量路徑構造算法STPC,基于網絡中部署的監測節點構造出一組最大數量的線性無關且不含環路的測量路徑,實現對所有鏈路性能的測量.該算法也為基于無環測量路徑的網絡斷層掃描(如最少監測節點部署[17])的實際應用奠定了基礎.為了簡化監測節點間測量路徑的構造,STPC 首先對網絡監測節點進行合并操作.具體地,在網絡拓撲中,STPC 引入一個虛擬監測節點,并分別用一條虛擬鏈路將原有的每個監測節點與虛擬監測節點連接起來.由于原拓撲鏈路(及路徑)與新拓撲鏈路(及路徑)之間存在著一一對應的關系,監測節點合并操作不會影響網絡鏈路的可識別性,從而可以將原監測節點間無環測量路徑的構造問題轉換為虛擬監測節點上有環測量路徑的構造問題.鑒于生成樹不含回路的特性,STPC 接著在新拓撲圖中以虛擬監測節點為根節點,構造了3 棵獨立的生成樹(如圖4 所示).在每個網絡節點上,通過這3 棵生成樹的兩兩組合,可以得到3 條從該網絡節點到虛擬監測節點的測量路徑.最后,再將虛擬監測節點上的測量路徑轉換為實際監測節點間的測量路徑.此外,將測量路徑數據表示為線性方程組的形式后,生成樹各節點上測量路徑的嵌套結構使得對方程組的求解不需要采用傳統高斯消元法的方式,即顯示反轉方程組系數矩陣.因此,STPC 能夠確保在線性時間內計算出所有網絡鏈路的性能指標.需要說明的是:STPC 在構造測量路徑時需要網絡中存在足夠多的監測節點,以確保對所有鏈路性能指標的推算.這一前提條件可能會給網絡管理員帶來不小的測量成本,從而導致STPC 在實際應用時面臨局限性.

Fig.4 Illustrative example with a network topology and three independent spanning trees rooted at node 1圖4 網絡拓撲及其以節點1 為根節點的3 棵獨立生成樹的說明示例

測量路徑的使用數量,很大程度上決定了探測包流量的大小[41-44].為降低測量負載對網絡正常通信的影響,有些工作關注于對測量路徑的選取及測量路徑數目的減少.針對網絡路徑性能測量問題,Chen 等人[45]提出了一個在給定監測節點部署的測量路徑選取方法,通過選取并測量一定數量線性無關的路徑,從而可以計算出其他路徑的性能指標.為了說明測量路徑選取方法的可擴展性,Chen 等人[45]還推導了在任意規模的網絡中,線性無關路徑選取數目的界限值,并將該界限值表達成網絡鏈路數目的線性函數形式.該結果為路徑選取方法在大規模網絡中的應用提供了堅實的理論依據.注意到網絡路徑大多都是線性相關的,文獻[46,47]基于給定的一組路徑測量信息,利用線性代數方法計算出其他未被測量的子路徑上的性能指標.針對網絡鏈路性能測量問題,Tang等人[48]基于網絡拓撲和路徑相關性信息設計了一種有效的路徑選取方法,通過收集監測節點間少量路徑的性能數據,推算出網絡內部細粒度的鏈路性能界限值.

此外,針對網絡中指定鏈路(即優先鏈路)的性能識別問題,基于實現網絡部分可識別性的最優監測節點部署算法(如OMA[21]),Zheng 等人[49]設計了一種測量路徑選取方法PathSelection.為了盡可能地減少測量路徑的數目,PathSelection 首先從給定監測節點間的候選路徑中確定出冗余的測量路徑:可以被其他路徑代替的路徑以及對優先鏈路性能識別沒有幫助的路徑.然后,PathSelection 基于二分圖模型(bipartite model)分析每一條優先鏈路識別與路徑組合的關系,并迭代式地從二分圖中找出一組可以識別所有優先鏈路且數目最少的路徑作為最終使用的測量路徑.在給定候選路徑的情況下,PathSelection 雖然可以有效地減少測量路徑數目,但在大規模網絡中,要從給定的候選路徑中找出所有可以識別優先鏈路性能的路徑組合,并在二分圖中確定一組數量最少的路徑,可能會造成很大的時間開銷.因此,如何從候選路徑中快速地找到一組對鏈路性能識別最有幫助的測量路徑,仍然是提高網絡斷層掃描有效性的一個關鍵問題.

2.3 測量數據分析與推斷

在網絡斷層掃描技術中,監測節點按照一定規律(如周期性)或一定模式(如泊松分布)沿著測量路徑發送探測數據包,將可以收集到一組(或一系列)端到端的測量數據.如何基于收集的測量數據準確地推斷網絡內部性能和狀態對測量方法的有效性顯得尤為重要.本節將簡要介紹網絡斷層掃描常用的數據分析與推斷方法.

根據網絡性能參數特征,現有網絡斷層掃描的數據分析方法大致可以分為統計學習方法和代數計算方法.其中,統計學習方法針對的是性能參數在探測包收集過程中會變化的測量數據,而代數計算方法針對的是性能參數在探測包收集過程中相對穩定的測量數據.

基于統計學習的數據分析方法將路徑性能和狀態作為一個整體,通過端到端測量數據收集一個測量樣本,并結合網絡拓撲模型和網絡性能模型推測出鏈路性能或通信狀態的概率分布.其基本思想是:利用第1.2 節公式(1)或公式(2)所示模型構造一個分布函數f(c;x)來描述網絡性能指標或通信狀態特性的依賴關系.如果存在完整觀測樣本,就可以用參數估計的方法確定x.然而在網絡斷層掃描中,通常只能觀測到部分樣本數據,這使得數據推斷變得比較復雜,需用統計學習的方法來估計那部分不確定的、觀測不到的數據[50].常見的基于統計學習的測量數據分析過程如圖5 所示.網絡性能指標或通信狀態對應于一個未知向量x,并在參數空間定義一個點,意味著已確定的推理估計目標.端到端測量數據c是觀測空間的一些點,每個測量數據都在這個空間產生一個特有的點.函數f(c;x)表示這些空間之間連接的統計量,實際上是一組概率密度函數.通過這些觀測數據,推理方法就能利用估計規則x′=g(c)來揭示測量對象x的值.目前,網絡斷層掃描主要的統計學習方法包含極大似然估計方法(maximum likelihood estimation,簡稱MLE)[51,52]、期望最大化(expectation maximization,簡稱EM)方法[53]和貝葉斯(Bayesian)估計方法[54]等.

Fig.5 Statistical learning procedures for measurement data analysis圖5 測量數據分析的統計學習過程

為測量所有鏈路性能的概率分布,在測量數據收集階段,文獻[55,56]利用多播的方式進行網絡探測包的發送和接收,并提出了相應的多播樹構造算法,證明了這種測量方式具有覆蓋范圍廣、測量開銷低的優勢.在測量數據分析階段,Chen 等人[57]應用傅里葉變換的技術對給定的路徑性能數據做預處理后,結合廣義矩估計的方法推斷出單條鏈路性能參數的概率分布.注意到測量數據的質量可能影響到數據分析準確性,與傳統給定路徑測量信息來推斷鏈路性能的方法不同的是,He 等人[58]基于費希爾信息(Fisher information)理論設計了一種探測包分配框架,用于計算在給定一組測量路徑和給定探測包總數目的情況下,單條測量路徑上探測包的發送數量,以使得收集到的路徑測量信息可以最大化鏈路性能估計的準確率.同時,文獻[58]將該探測包分配框架應用到鏈路時延測量和鏈路丟包率測量的實際問題中,基于框架收集到的路徑測量信息和優化算法(D-最優化和A-最優化),準確地估算出了網絡鏈路時延和丟包率的概率分布情況.針對網絡鏈路通信故障的定位問題,文獻[25-28]利用極大似然估計方法從網絡中找出一組最少數目的鏈路故障,從而能夠完全解釋收集的端到端路徑狀態信息.文獻[29,30]基于給定的端到端的測量數據,利用貝葉斯學習方法計算網絡中每一條鏈路故障的概率.

基于代數計算的數據分析方法的基本思想是:將鏈路性能指標或通信狀態刻畫為一個未知常量,通過收集一組端到端路徑的測量數據,結合網絡拓撲模型和網絡性能模型推測出鏈路的性能或狀態.對于可累加的網絡性能指標(如鏈路時延),一條端到端路徑的性能指標等于路徑上所有鏈路性能指標的總和.因此,代數計算方法可以將收集的路徑測量數據表述成一個線性方程組的形式(如公式(1)所示),然后應用線性代數理論求解形式化的線性方程組,從而獲得有唯一解(即唯一確定)的鏈路性能指標值.目前,網絡斷層掃描主要的代數計算方法有高斯消元法[18,19]、LU 分解法[22,23]、逆矩陣法[15,16]和增廣矩陣法[49]等.基于高斯消元法的數據分析具有較好的通用性,在實際網絡斷層掃描中應用得較多,但其計算復雜度較大,在可擴展性方面有局限性.相反,基于LU 分解法和逆矩陣法的數據分析具有相對穩定的計算開銷,但方法的使用需要滿足一定的前提條件,如LU 分解法需方程組系數矩陣(公式(1)中的R)可分解成兩個三角矩陣的乘積,逆矩陣法需方程組系數矩陣(第1.2 節公式(1)中的R)是滿秩可逆的.基于增廣矩陣的數據分析也具有較好的通用性,適用于需要測量不可識別(即無唯一解)的鏈路性能指標范圍的場景.

3 應用挑戰與關鍵技術

表1 總結了近些年網絡斷層掃描方法的相關研究成果.

概況地說,文獻[11,12,15,17]從探測數據包路由策略的角度研究了在實現網絡完全可識別性時的監測節點部署問題.其中,文獻[11,12]基于網絡默認路由協議的鏈路性能測量問題,并證明在基于網絡默認路由(即不可控路由)策略下最少監測節點的部署是一個NP 難問題.隨后,文獻[15,17]分別從測量路徑是否允許包含環路的角度提出了基于可控路由策略的監測節點部署理論和線性時間復雜度算法,從而為網絡斷層掃描技術的演變和改進奠定了基礎.受網絡測量成本的限制,文獻[18-21]從實現網絡部分可識別性的角度解決了監測節點的部署問題,確?？梢杂糜邢薜某杀緷M足服務提供商和網絡管理員的測量需求,從而提高了網絡斷層掃描算法的靈活性.另一方面,網絡內部運行狀態也是網絡測量的重要組成部分.文獻[32-34,36]從探測數據包路由策略的角度研究了對特定數目鏈路(或節點)失效定位的監測節點部署問題,從而進一步拓展了網絡斷層掃描技術的適用范圍.此外,文獻[38,40,45,49]從測量對象和路由策略的角度研究了測量路徑的構造和選取問題,并提出了相應的多項式時間復雜度算法.這些工作為網絡斷層掃描技術在各種形式網絡中的實際應用提供了必要的基礎.

從表1 中可以看出:當前已有許多網絡斷層掃描的理論和方法,但這些方法的設計在測量目標(或測量對象)、網絡模型和測量成本等方面都有較為明確且嚴格的規定(或假設).這些規定假設雖然有利于方法的演變與驗證,但也給方法的實際應用帶來了局限性.

總體上,現有的網絡斷層掃描方法在性能測量粒度(及精度)、網絡拓撲結構和網絡通信模型這3 個核心方面都帶有較強的假設和要求(見表2),這影響了網絡斷層掃描方法在實際應用中的有效性和通用性,甚至使得方法在有些網絡場景中難以被使用.總體上,設計一個通用、高效及魯棒的網絡斷層掃描方法面臨以下3 項關鍵挑戰:測量成本非常受限、網絡拓撲的動態性以及網絡通信的易失效性.近兩年,越來越多的研究者開始關注已有網絡斷層掃描方法的局限性,并提出了相應理論和關鍵技術,以有效應對這些挑戰.本節歸納了在應對上述挑戰的一些代表性研究工作及其關鍵技術.

Table 1 Summary of network tomography methods表1 網絡斷層掃描方法總結

Table 2 Research status and key application challenges表2 現狀及應用挑戰

3.1 粒度可調網絡斷層掃描理論與技術

· 挑戰

現有的網絡斷層掃描方法大多著重于實現對網絡中所有鏈路性能指標確切值的測量,即測量粒度(及精度)單一且固定.這些方法存在兩個主要缺陷:一是受網絡拓撲和路由策略等的限制,測量網絡所有鏈路性能的目標在很多應用場景中難以實現;二是測量鏈路性能指標的確切值往往會帶來很大的開銷,例如需要部署很多監測節點和發送大量探測數據包.為此,提出粒度(及精度)可調的網絡斷層掃描理論,并設計一種粒度(及精度)可調的網絡斷層掃描算法以有效平衡性能指標測量的精度與測量的開銷,顯得很有必要.

· 關鍵技術

在很多實際應用中,服務提供商與網絡管理員通常關注的是網絡內部性能是否符合與用戶簽訂的服務水平協議(service level agreement,簡稱SLA)的要求,如網絡丟包率是否處在SLA 規定的范圍內[59].因此,鏈路性能指標的界限值將足以滿足服務提供商與網絡管理員的性能測量需求.鑒于此,Feng 等人[60]提出了一種有效的網絡斷層掃描方法,基于給定的監測節點和端到端路徑測量數據,推算出網絡中所有鏈路性能指標的界限值(包括性能上界和性能下界).簡單地說,對于可識別的鏈路,其性能指標值可由與端到端測量數據對應的線性方程組唯一確定,所以可識別鏈路的界限值為同一個數,即,其性能界限的上界值等于下界值.對于不可識別的鏈路,已有網絡斷層掃描方法不會提供任何關于其性能指標的信息,而文獻[60]的方法可以求解出其性能指標的界限值,且此時其上界值不等于下界值.

以圖6 為例,網絡中有兩個節點(v2和v3)部署為了監測節點.假設網絡中10 條鏈路(l1～l10)上的時延分別為{x1=7,x2=1,x3=5,x4=4,x5=6,x6=8,x7=13,x8=10,x9=3,x10=3}.需要說明的是,服務提供商與網絡管理員一開始并不知道這些鏈路的時延,只有通過收集兩個監測節點間端到端路徑的時延數據,才能推算出單條鏈路的時延.因為網絡中只有v2和v3為監測節點,基于鏈路可識別性條件[16,18],已有的網絡斷層掃描方法只能測量出鏈路l1和l6的時延,即只有鏈路l1和l6是可識別的.而對于網絡中不可識別鏈路(l2～l5和l7～l10)的時延,已有的網絡斷層掃描方法不能提供任何信息.不同的是,通過使用文獻[60]的網絡斷層掃描方法,網絡管理員可以計算出不可識別鏈路上的時延范圍:B(x2)=[0,7],B(x3)=[2,9],B(x4)=[3,10],B(x7)=[0,27],B(x8)=[0,27],B(x9)=[0,7],B(x10)=[0,7].

Fig.6 Illustrative example of network tomography for inferring performance metric bounds圖6 測量性能指標界限值的網絡斷層掃描說明示例

通過對推算的鏈路性能指標界限值區間長度(bound interval length)賦上不同的約束,我們可以實現一種粒度可調的網絡斷層掃描.特別地,當要求鏈路性能指標界限值的區間長度為0 時(即要獲得鏈路性能指標的確切值),文獻[60]的方法轉化為已有網絡斷層掃描方法.因此,文獻[60]中的網絡斷層掃描方法是已有的網絡斷層掃描方法在測量目標上的一種推廣演變.相比已有的旨在實現對網絡所有鏈路性能指標確切值的方法,雖然文獻[60]的網絡斷層掃描方法通過推算鏈路性能指標界限值的方式能夠在很大程度上減少測量的開銷,但推算網絡所有鏈路性能指標界限值的復雜度與網絡規模有很大關系,在大規模網絡中容易造成指數級時間復雜度.

然而有些場景并不需要測量所有鏈路性能指標界限值,相反,服務提供商與網絡管理員只需要獲取一部分網絡鏈路的性能指標界限值.比如在因特網中,被用戶反映通信不正常的鏈路要比其他鏈路重要得多[61];在無線傳感網中,位于基站(或網關)附近的鏈路由于承載的數據流量更大,通常成為限制整個網路系統性能的瓶頸[62].通過測量網絡中這些優先鏈路(或目標鏈路)的性能指標界限值,可以進一步減少測量開銷.更重要的是,還可以降低測量復雜度,有利于提高方法在大規模網絡中的有效性.為此,我們研究了基于斷層掃描的網絡優先鏈路(preferential link 或interesting link)性能指標界限值的計算理論及測量技術[63].不同于文獻[60]需推算網絡所有鏈路性能指標界限值的要求,我們的方法關注于對服務提供商和網絡管理員在網絡中任意指定的一組優先鏈路性能指標界限值的高效測量.當指定網絡所有鏈路為優先鏈路時,優先鏈路性能指標界限值的求解問題將轉化為網絡所有鏈路性能指標界限值的求解問題.因此,我們提出的網絡斷層掃描算法[63]相比文獻[60]的網絡斷層掃描方法更加靈活和普適,具有更大的應用范圍.下面我們簡要介紹實現對優先鏈路性能測量粒度可調的網絡斷層掃描理論及技術[63]的核心思想.

考慮到服務提供商與網絡管理員在不同階段可能具有不同的測量需求,如:在網絡運行階段,關注的是如何通過已有監測節點有效地計算出網絡中優先鏈路性能的界限值;在網絡擴建或升級階段,關注的是如何部署更多數目的監測節點以縮小計算的優先鏈路性能界限的距離.為此,我們在文獻[63]中同時解決了以下兩個關鍵問題.

· 優先鏈路性能指標界限值計算:在一個給定監測節點和優先鏈路的網絡中,如何有效地推算出這些優先鏈路性能指標的最緊界限值,即最緊的上界值和最緊的下界值?

· 監測節點部署:在一個給定初始監測節點和優先鏈路的網絡中,如何通過部署額外的監測節點以進一步縮小優先鏈路性能界限區間的長度(即上界值和下界值的差值)?

對于優先鏈路性能指標界限值的計算問題,基于對由端到端測量構造的線性方程組的可解情況及解空間分析,我們提出了網絡優先鏈路性能指標界限值的計算理論,其中包含多種降低優先鏈路性能界限值計算復雜度的策略.由線性代數理論可知:方程組中不可解的變量可以分為自由變量和非自由變量兩種類型,其中每個非自由變量可以表示成若干個自由變量的線性表達形式.然而,在一個沒有唯一解的方差組中,通常有非常多種自由變量的組合方式.而每種自由變量組合方式都對應著一種方程組解的形式,在每種方程組解的形式中,都可以獲得一個優先鏈路性能指標界限值.因此,在優先鏈路性能指標界限值的計算問題中,一個關鍵的挑戰是如何確定出可以導致優先鏈路性能指標界限值最緊的一種自由變量組合方式.通過枚舉所有自由變量組合方式并比較每種組合方式下優先鏈路性能指標界限值的方法,容易造成指數級的時間復雜度.注意到:在線性方程組中,對于一個特定變量(即目標變量),只有與其線性相關的變量才能影響到目標變量的求解.為此,在優先鏈路性能指標界限值的求解過程中,我們只選擇與優先鏈路性能變量線性相關的變量作為自由變量,從而可以很大程度上縮小自由變量的選取范圍,降低優先鏈路性能界限值計算的時間復雜度.

對于監測節點部署問題,基于對鏈路可識別性與優先鏈路性能界限值松緊程度關系的分析,我們設計了一個高效的監測節點部署算法NMPI[63].在網絡原有監測節點的基礎上,部署一個新的監測節點,從而最大程度上減小優先鏈路性能界限區間的長度.首先,NMPI 的設計基于一個重要的觀察:在一個包含一組優先鏈路的網絡中,對于新監測節點的部署,不可識別的優先鏈路性能指標界限區間長度只會受由新監測節點部署增加的可識別鏈路的影響,從而相同的鏈路可識別性也會造成相同的優先鏈路性能指標界限區間長度.因此,在監測節點部署過程中,對網絡鏈路可識別性變化的分析成為了一個關鍵的問題.

由于網絡可能部署有多個監測節點,而鏈路可識別性與單個監測節點之間存在著復雜的關系,為了簡化監測節點部署對網絡鏈路可識別性變化的分析,NMPI 對網絡拓撲進行擴展操作.具體地,對于一個已有κ(κ≥2)個監測節點的網絡G,引入兩個虛擬監測節點(virtual monitor)1m′和m2′,同時,在實際監測節點(actual monitor)和虛擬監測節點間增加2κ條虛擬鏈路,在兩個虛擬監測節點之間也增加一條虛擬鏈路(virtual link),將新生成的拓撲稱為網絡擴展圖Gex(如圖7 所示).由于原網絡拓撲實際監測節點之間的端到端測量都可以轉化為虛擬監測節點1m′和m2′之間的端到端測量,并且對于網絡鏈路的測量,1m′和m2′之間的端到端測量相比實際監測節點之間的端到端測量不會提供額外的信息,所以原網絡拓撲G的鏈路可識別性與擴展圖Gex的鏈路可識別性是一樣的,從而NMPI 可以關注于僅包含兩個監測節點的擴展圖Gex鏈路可識別性的變化.隨后,NMPI 通過對新監測節點部署與網絡擴展圖Gex結構變化關系的分析,實現了新監測節點在網絡擴展圖Gex及原拓撲G中的最優部署.

Fig.7 Illustration of topology extension operation圖7 拓撲圖擴展操作示例

此外,還有一些工作從測量對象的角度研究了粒度可調的網絡斷層掃描理論與技術.注意到在實際應用中,網絡用戶通常關心的是所用網絡服務的性能,例如從客戶端向服務器發送請求到客戶端收到回應的時延,Yang等人[64]解決了網絡任意節點間端到端通信路徑性能的測量問題,并提出了一種最優的監測節點部署算法MPIP,通過收集監測節點間一組端到端測量數據,以實現對任意指定路徑(即優先路徑,interested path)性能指標的推算.為便于網絡監測節點的部署,文獻[64]首先研究了基于斷層掃描的網絡優先路徑性能的可識別性理論,形式化表述了拓撲結構、監測節點和路徑可識別性這三者的關系,并解決了給定監測節點部署時,網絡可識別路徑的判斷問題.基于網絡路徑可識別性條件,MPIP 將網絡拓撲劃分成多個2-點連通和3-點連通分支,根據各連通分支中優先路徑特性,迭代地在各連通分支中部署必要的監測節點,從而用最少的監測節點實現對所有優先路徑性能指標的計算.需要說明的是,上述這些粒度(及精度)可調網絡斷層掃描方法[60,63,64]在實現過程中,使用的是不含環路的端到端測量路徑,這有利于提高方法在實際網絡中的可用性.

3.2 動態拓撲網絡斷層掃描理論與技術

· 挑戰

隨著物聯網、軟件定義網絡等新型網絡形態與網絡技術的興起,動態的網絡路由拓撲越來越成為這些新型網絡的重要特點[65].例如在典型的物聯網場景中,動態路由協議(如RPL[66]、低功耗藍牙mesh 網絡路由等)被廣泛用于應對無線信道、節點位置等的動態性,從而使得網絡路由拓撲不斷發生變化.而在軟件定義數據中心網絡中,流量分割(traffic splitting)[67]技術及重路由(re-routing)[68]技術被廣泛用于負載均衡,使得同一個數據流的數據包可以通過不同的路由到達接收端,從而導致了網絡路由拓撲的動態性.現有網絡斷層掃描技術[16,17,19,21]的典型工作模式是基于已知的靜態網絡拓撲,部署一定數量的監測節點并獲取監測節點間探測包的測量數據,然后結合網絡拓撲信息建立關于內部運行狀態的方程組,最后通過求解方程組完成網絡測量的目標.然而,當網絡路由拓撲動態變化時,某一時刻存在的路由路徑下一時刻可能就不存在了,而某一時刻必要的監測節點在另一時刻可能是冗余的.因此,如何在動態拓撲的條件下進行精確、高效的網絡斷層掃描,是一個非常重要的問題.

· 關鍵技術

在動態拓撲網絡中,由于鏈路(或節點)的動態性,在某一個時刻的拓撲中部署的監測節點可能并不適用于另一個時刻拓撲中鏈路的性能測量.一種簡捷的動態拓撲網絡測量方法是:當網絡拓撲變化后,利用基于靜態拓撲的網絡斷層掃描方法[21,25]在新生成的網絡拓撲中重新部署一遍監測節點.這種應急式(reactively)的部署方法雖然可以實現對多個網絡拓撲的性能測量,但頻繁地更換監測節點部署位置一方面給網絡管理員帶來了不小的成本開銷,另一方面也不利于網絡測量任務的平穩進行.因此,在網絡拓撲變化前,先驗式(proactively)地實現對鏈路性能的測量顯得尤為重要.

He 等人[69]首次研究了動態拓撲網絡鏈路性能的測量問題,并提出了一種有效的網絡斷層掃描方法,通過在網絡規劃初期,一次性部署一定數目的監測節點,以實現對網絡所有可能拓撲中所有鏈路的性能測量.然而,要想獲得動態拓撲網絡中所有鏈路的性能,即使最優的監測節點部署算法也可能需要使用大量監測節點(如網絡90%以上的節點需為監測節點[69]),這將會造成很大的測量成本.另一方面,很多時候,服務提供商與網絡管理員只關注網絡某些鏈路的性能指標,例如處在網絡關鍵位置上的鏈路性能指標.通過測量網絡中優先鏈路的性能指標,在滿足應用需求的同時,也可以很大程度上降低測量成本.為此,我們研究了面向動態拓撲的優先鏈路測量理論及技術,其中包含多種高效及魯棒的網絡斷層掃描方法[70],通過在動態拓撲網絡中部署盡量少的監測節點,以實現對所有可能拓撲中優先鏈路的性能測量.不同于文獻[69]計算網絡所有鏈路性能指標的要求,我們的方法旨在用更少的成本計算出網絡中任意指定的一組優先鏈路的性能指標.當指定網絡所有鏈路為優先鏈路時,對優先鏈路性能指標的測量問題將轉化為對網絡所有鏈路性能指標的測量問題.因此,我們提出的網絡斷層掃描方法[70]是文獻[69]中網絡斷層掃描方法的泛化,具有更好的測量靈活性.下面我們簡要介紹實現對動態拓撲網絡中優先鏈路性能有效測量的網絡斷層掃描方法[70]的核心思想.

網絡斷層掃描方法的設計需要網絡拓撲信息作為基礎,而盡早地獲取動態網絡在各個時刻的拓撲信息,有助于監測節點的部署.因此,我們首先研究了基于網絡拓撲預測的優先鏈路可識別性理論,從而為動態拓撲網絡監測節點的部署提供指導.由于動態網絡拓撲結構的周期性和可預測性(例如行車路線和運行時刻固定的公交車網絡、睡眠/工作模式周期性交替的低功耗傳感網),可以利用拓撲時空相關性及過去一段時間的網絡拓撲,預測未來一段時間內的網絡拓撲.另一方面,我們設計了一種通用及簡潔的時變網絡模型來刻畫動態拓撲網絡的在各個時刻的拓撲結構.簡單地說,我們將網絡測量周期(或生命周期)劃分成若干個等長的時隙,然后將網絡在各個時隙上的拓撲結構用如下序列的形式來表述:

其中Gt表示網絡在第t個時隙上的拓撲.

圖8 所示為一個具有4 個節點(A～D)的動態拓撲網絡在3 個不同時隙上的拓撲結構.

Fig.8 Illustrative example for topologies in different slots of a dynamic network圖8 動態網絡在不同時隙的拓撲結構示例

確定了動態網絡在各個不同時刻上的拓撲后,我們提出了動態拓撲網絡中優先鏈路的可識別性理論,解決如何一次性部署盡量少的監測節點以保證對網絡所有拓撲中優先鏈路的性能測量問題.具體地,考慮到監測節點可能部署位置的數目將隨著網絡規模呈指數增長,我們分析優先鏈路的可識別性與監測節點部署位置的關系,通過裁剪掉對優先鏈路性能測量無影響的部分節點,縮小監測節點部署的選擇范圍,從而加快網絡斷層掃描的實現過程.

隨后,我們解決了動態拓撲網絡的監測節點部署問題.注意到現有工作[20,21]已實現對靜態拓撲網絡中優先鏈路性能測量的監測節點部署算法,存在一種比較直接的動態拓撲網絡監測節點部署方式:在網絡拓撲序列(如公式(4)所示)中依次應用靜態拓撲的監測節點部署算法,獲得網絡各時隙上的監測節點部署,再將所有時隙上監測節點部署的并集作為動態拓撲網絡最終的監測節點部署結果.這種監測節點部署方式雖然可以保證各網絡拓撲中優先鏈路的可識別性,但可能會部署上冗余的監測節點,給服務提供商與網絡管理員造成了不必要的開銷.以圖9 所示的動態網絡為例,在該網絡中,節點v2和節點v6在時隙1 的拓撲G1中連通,在時隙2 的拓撲G2中斷開.在網絡兩個時隙的拓撲中,假設網絡管理員只需要測量鏈路v1v4和鏈路v1v5的性能.在拓撲G1中,為了獲得這兩條優先鏈路的性能,基于文獻[21]中的部署算法,我們可以從{v2,v3,v6,v7,v8}中任選兩個節點部署監測節點,所以M1={v6,v7}為一種可行的部署方式;而在拓撲G2中,選v2和v3作為監測節點,可以測量出優先鏈路v1v4和v1v5的性能,即M2={v2,v3}.因此,最終我們在該動態網絡中部署的監測節點為M1∪M2={v2,v3,v6,v7},即需要4個監測節點.由于M2本身也適用于拓撲G1中優先鏈路性能的測量,這種對不同時隙網絡拓撲單獨處理的方式部署了兩個冗余的監測節點,即v6和v7.

Fig.9 Illustrative example for monitoring node placement in a dynamic network圖9 動態拓撲網絡中監測節點的部署示例

為此,在監測節點的部署過程中,我們綜合考慮了動態網絡各時隙拓撲中監測節點的部署需求,并用如下約束條件的方式刻畫單個拓撲的監測節點部署:

其中,Si為網絡節點集合,表示在單個拓撲中可供選擇的監測節點部署位置;ni表示從Si中至少需要選擇的節點數目.

得到動態網絡每個拓撲中監測節點部署的約束條件后,我們將監測節點的部署問題規劃成最小碰撞集問題(minimum hitting set problem,簡稱min-HSP).利用最優化理論,可以從整個網絡中選取出最少數目的節點作為監測節點,以滿足各約束條件.相應地,我們能夠用最少的監測節點來保證動態網絡中優先鏈路的可識別性.

3.3 通信失效網絡斷層掃描理論與技術

· 挑戰

現有的很多關于網絡斷層掃描技術的研究工作嘗試回答網絡拓撲與鏈路可識別性具有何種關系這一問題[15,16,18,19],想要了解對于給定拓撲,如何部署監測節點測量出網絡中所有(或部分)鏈路的性能指標.但是這些工作假設在測量過程中網絡通信都是完全可靠的,未考慮到網絡通信失效的情況.然而在實際應用中,通信失效在多種形式的網絡中是較為常見的[71],如鏈路故障、節點變更和信道沖突等.因此,提出通信失效網絡斷層掃描理論并設計魯棒的網絡斷層掃描算法,以保障在網絡發生通信失效時測量任務的順利進行,也是一個亟待解決的問題.

· 關鍵技術

對于特定的監測節點部署,當發生通信失效(如鏈路失效)時,其能觀測到的路徑是不同的,包含失效鏈路的路徑將不能被觀測到,從而可能使原來可識別的鏈路變得不可識別.以圖10 中鏈路l6的測量為例,在該網絡拓撲中,節點v2被部署為監測節點,通過測量3 條起止于v2的路徑性能數據(p1:l2l1l6,p2:l3l4l6,p3:l2l1l4l3),可以推算出鏈路l6的性能(如時延).用xi表示鏈路li的性能,ci表示路徑pi的性能,則3 條測量路徑的性能與鏈路性能可以用圖10 中的線性方程組關聯起來,其中每條測量路徑分別對應于方程組中的一個線性方程.通過求解該線性方程組,可以計算出鏈路l6的性能指標值c6=(c1+c2-c3)/2,即鏈路l6在監測節點v2下是可識別的.然而,當鏈路l2發生通信失效時,測量路徑p1:l2l1l6和p3:l2l1l4l3由于包含l2將變得不可用,方程組將只包含方程②的信息,此時鏈路l6將變得不可識別.因此,現有的監測節點部署方法無法有效應對鏈路失效對網絡性能測量的影響.值得注意的是,有些鏈路在網絡中任意其他k條鏈路失效的情況下仍然是可識別的.例如圖10 中l3在網絡其他任意1 條鏈路失效時,仍可以通過其他測量路徑的端到端數據推算出其性能指標值.如果我們能夠了解怎樣的拓撲特征可以使得鏈路具有這種性質,將有助于指導監測節點的部署以及網絡拓撲的設計,實現魯棒的網絡測量.此外,不同的監測節點部署也可能導致不同的鏈路可識別性.如果將監測節點部署在v5,那么無論有無鏈路失效發生,網絡中所有的鏈路都將變得不可識別.

?Fig.10 Example to illustrate the impact of link failures on network tomography圖10 鏈路失效對網絡斷層掃描的影響示例

針對這種情況,我們在文獻[72,73]中研究了網絡失效下的鏈路可識別性理論,包含一條鏈路在其他任意k(k≥0)條鏈路失效情況下仍然可以識別的充分必要條件,并根據鏈路可識別性理論設計了監測節點的部署算法,解決了如何在有鏈路失效的情況下部署監測節點,以進行魯棒的網絡斷層掃描.首先,為了量化鏈路失效對鏈路性能識別性的影響,我們提出了k-可識別性(k-identifiability)的概念.

· 一條鏈路(非失效鏈路)被稱為k-可識別的(k-identifiable),當且僅當該鏈路在網絡中任意k條鏈路失效時仍是可識別的;

· 一個網絡被稱為k-可識別的,當且僅當網絡中所有鏈路都是k-可識別的.

需要說明的是:當k=0 時,k-可識別表示當網絡無通信失效時鏈路是可識別的(即已有網絡斷層掃描方法的可識別性),此時也記為0-可識別.k-可識別的鏈路一定是(k-1)可識別的,k越大,表示該鏈路對于其他鏈路失效的容忍度越大.可以看出:如果我們能得到鏈路k-可識別和網絡拓撲結構的關系,將幫助網絡管理者有效地部署監測節點,以使得網絡中k-可識別的鏈路數目盡可能多.同時,這也能幫助網絡設計者了解如何設計網絡能夠使得網絡鏈路為k-可識別的,實現魯棒的網絡斷層掃描[74].

具體地,我們在文獻[72,73]中通過回答以下兩個密切相關的問題,來幫助網絡設計者和網絡管理員達到上述目標.

· 對于一個給定監測節點部署的網絡,哪些鏈路是k-可識別的?

· 對于一個給定監測節點數目的網絡,如何部署這些監測節點,以使網絡中k-可識別的鏈路數目最大?

針對k-可識別性鏈路的判斷問題,對于一個有n條鏈路的網絡來說,網絡中k條鏈路失效的場景有種,通過枚舉每一種失效場景去判斷一條鏈路是否是k-可識別的是不可行的.為此,我們選擇通過對網絡拓撲進行適當劃分來研究鏈路k-可識別性在監測節點部署和拓撲結構方面的判定理論.具體地,我們給出并證明了在不考慮鏈路失效(k=0)時,鏈路可識別(0-可識別)的充分必要條件(見表3).在此基礎上,進一步給出并證明了在考慮鏈路失效(k>0)時,鏈路可識別(k-可識別)的充分必要條件(見表3).基于這些證明的鏈路k-可識別性條件,我們可以基于網絡拓撲結構和監測節點部署位置,在多項式時間內判斷出一條鏈路是否是k-可識別的,而不需要枚舉所有鏈路失效情況,顯著降低了k-可識別性鏈路判定的復雜度.

Table 3 Necessary and sufficient conditions for k-identifiability of links[72,73]表3 鏈路k-可識別性的充要條件[72,73]

對于特定數目(κ個)監測節點的部署問題,一種比較直接的方法是:根據鏈路k可識別性的判定條件,在網絡中枚舉所有監測節點部署位置,并比較每種部署情形下k可識別鏈路的數目,最后輸出使得k可識別鏈路數目最大的監測節點部署方式.考慮到網絡中存在種可能的監測節點部署方式,這種枚舉方法的復雜度將隨著網絡規模呈指數級增長,不具有可擴展性.相反,我們在文獻[72,73]中形式化地表述了特定數目監測節點的部署問題,并說明了這是一個NP 完全問題.隨后,我們提出了一種貪心算法MPK 來解決這個問題.MPK 的核心思想是:因為在網絡的(k+3)-邊連通分支中部署一個監測節點必然能使其中的鏈路都是k-可識別的(見表3),所以MPK首先在(網絡的每個(k+3)-邊連通分支中隨機地選擇一個節點,構成監測節點部署的候選集合.接著,MPK 枚舉了第1 個監測節點部署的所有位置,這是因為第1 個監測節點不同的部署往往會給算法最后的結果帶來較大的影響.當第1 個監測節點的位置選定后,MPK 將一個一個地從候選集合中選定剩余的κ-1 個監測節點.每次選擇中,MPK 都將選擇使得當前k-可識別的鏈路數目最多的位置部署監測節點.需要說明的是:通過此算法,我們可以逐步增加監測節點的數目,直到網絡中所有鏈路都為k-可識別時,此時的監測節點部署為開銷最小的部署方式.

雖然文獻[72,73]中的監測節點部署能夠確保鏈路在網絡失效情況下的k-可識別性,但k-可識別性概念針對的是網絡隨機(或任意的)鏈路失效場景,同時,監測節點部署過程也將網絡鏈路失效刻畫為不可預測的.這種悲觀式鏈路失效刻畫方式容易生成次優的監測節點部署結果,即部署冗余的監測節點.然而在很多網絡場景中,基于網絡通信模式特征和現有拓撲預測模型[75,76],服務提供商和網絡管理員能夠一定程度上預測出未來一段時間內的網絡失效情況,即存在一部分可預測的網絡失效.為此,我們在文獻[77]中進一步提出了一種能夠同時應對可預測和不可預測鏈路失效的網絡斷層掃描方法,基于對網絡鏈路失效的預測,在保證鏈路k-可識別性的同時,進一步減少監測節點部署數量,降低測量的成本.為了滿足網絡管理員在測量成本與實現復雜性上的不同需求,我們還提出了多種監測節點部署算法[77](如簡單取并集法、增量部署法和綜合部署法等),以達到監測節點部署成本和時間復雜度之間的平衡.

4 總結和未來工作

與傳統網絡內部測量方法不同,網絡斷層掃描作為一種新型的網絡外部測量方法,能夠在沒有中間節點協作的條件下,根據網絡邊緣的測量數據推測出網絡內部性能指標和運行狀態,從而實現與網絡組成及協議無關的網絡測量.本文首先給出了網絡斷層掃描的基本概念和形式化表述,并指出了影響網絡斷層掃描性能的3 個重要因素:監測節點部署、測量路徑構建和測量數據分析.接著,對近年來學術界在這3 個影響因素方面的代表性研究工作進行了歸納分析.其中,針對網絡狀態識別問題,本文還介紹了布爾形式網絡斷層掃描在監測節點部署方面的研究成果.隨后,本文分析了已有網絡斷層掃描工作在實際應用中的核心缺陷,并總結了針對這些核心缺陷近年來提出的最新理論及算法.

目前,網絡斷層掃描的發展和應用仍然是網絡測量領域研究的熱點,存在大量開放性問題有待更加深入的研究.以下列舉出幾個未來可能的發展方向.

(1) 通用有效的網絡斷層掃描性能模型.當前,學術界已經提出了很多網絡斷層掃描算法,如MMP[16],OMA[21],MPIP[64]和MAPLink[70]等.這些網絡斷層掃描算法依賴于不同的網絡模型,具有不同的數據收集和數據分析方式.此外,這些算法在測量開銷、測量精度(及粒度)、實現復雜度等方面也有不同的表現.因此,設計一個通用有效的網絡斷層掃描性能模型,以準確刻畫測量可用資源(帶寬資源、計算資源、存儲資源)與測量算法性能之間的關系,將有助于服務提供商與網絡管理員在相同條件下(如給定測量開銷)對比不同方法的優劣,從而便于根據當前網絡的特性和測量的需求選擇最合適的網絡斷層掃描算法,實現測量開銷和測量精度之間的平衡.

(2) 更魯棒的測量算法和分析方法.網絡斷層掃描技術的應用,離不開測量數據的收集和分析.測量數據收集的質量,直接影響測量結果的性能.由于采用間接測量的方式,網絡斷層掃描測量數據的收集容易受到許多實際因素的影響,如鏈路擁塞狀況、節點存儲狀況和網絡路由等.而其中任意一個因素的變化,將很可能使得傳統網絡斷層掃描方法變得不可用.雖然近幾年已有部分工作[69,70,72,77]考慮了魯棒斷層掃描問題,但大多針對的是特定因素的影響,如節點位置更新和鏈路失效等.如何考慮更加全面及實際的網絡設置,根據其特征進一步擴展和改進網絡斷層掃描算法,仍然是一個需要思考的問題.此外,受環境干擾、網絡流量等影響,監測節點上收集的測量數據可能帶有一些誤差.雖然已有統計學習方法可以在一定程度上規避測量數據的噪聲,但其往往具有較大的復雜度,難以保證測量的實時性.因此,未來需要在目前研究基礎上探索更加魯棒的網絡測量算法和更加通用的數據分析方法.

(3) 網絡測量信息挖掘和智能分析.針對大規模網絡的性能測量,是近年來網絡測量領域的研究熱點之一[74].目前,實現對大規模網絡的性能評估,需要長時間持續不斷地測量才能獲取全面而準確的數據.因此,網絡斷層掃描還要面對大規模測量可能帶來的海量數據和數據時效性的問題[3].另外,通過對網絡斷層掃描測量信息的跟蹤與統計分析,有助于服務提供商與網絡管理員迅速、直觀地判斷網絡性能的變化趨勢,并及時定位網絡瓶頸和故障的位置,在網絡性能惡化之前予以解決,保證網絡服務的可用性和有效性.因此,實現網絡測量信息的智能分析和預測將有助于網絡的管理及優化,具有廣泛的研究意義和應用價值.可以預見:一種高效、魯棒及智能的網絡斷層掃描技術將可以提升我們了解網絡運行機理的能力,支撐網絡性能的持續優化.