網(wǎng)絡(luò)斷層掃描:理論與算法*

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

(浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310027)

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

為此,近些年來(lái),國(guó)際上許多學(xué)術(shù)機(jī)構(gòu)都在尋求其他途徑來(lái)研究網(wǎng)絡(luò)的整體性能及其相互影響,將已成功應(yīng)用于醫(yī)學(xué)、地震學(xué)、地質(zhì)勘探等領(lǐng)域的成熟理論和方法應(yīng)用于通信網(wǎng)絡(luò)領(lǐng)域,衍生出了網(wǎng)絡(luò)斷層掃描(network tomography)技術(shù)[5].它是根據(jù)網(wǎng)絡(luò)外部(即網(wǎng)絡(luò)邊界)的測(cè)量信息來(lái)分析和推斷網(wǎng)絡(luò)內(nèi)部的性能及狀態(tài),是一種在沒(méi)有網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的條件下,通過(guò)主動(dòng)發(fā)包探測(cè)或被動(dòng)收集網(wǎng)絡(luò)內(nèi)部有用信息的新技術(shù),結(jié)合數(shù)理統(tǒng)計(jì)方法,能夠有效地推測(cè)出網(wǎng)絡(luò)鏈路上的QoS 指標(biāo),如延遲分布、丟包率、吞吐率和流量等.

目前,網(wǎng)絡(luò)斷層掃描的研究主要集中于兩個(gè)方面:一是測(cè)量數(shù)據(jù)的收集,主要研究如何收集網(wǎng)絡(luò)內(nèi)部相關(guān)的有用信息;二是測(cè)量數(shù)據(jù)的分析,主要研究如何根據(jù)收集的數(shù)據(jù)來(lái)獲取網(wǎng)絡(luò)內(nèi)部的性能指標(biāo)和運(yùn)行狀態(tài).本文在簡(jiǎn)要介紹網(wǎng)絡(luò)斷層掃描基本概念和形式化表述的基礎(chǔ)上,從測(cè)量數(shù)據(jù)收集和測(cè)量數(shù)據(jù)分析兩個(gè)主要方面綜述了網(wǎng)絡(luò)斷層掃描的研究現(xiàn)狀與關(guān)鍵技術(shù).隨后分析了已有網(wǎng)絡(luò)斷層掃描方法在實(shí)際應(yīng)用中的核心缺陷,并系統(tǒng)介紹了針對(duì)這些核心缺陷近年來(lái)提出的最新理論及算法.最后,基于現(xiàn)有研究成果對(duì)網(wǎng)絡(luò)斷層掃描技術(shù)的發(fā)展趨勢(shì)和下一步的研究方向進(jìn)行了討論.

1 網(wǎng)絡(luò)斷層掃描基礎(chǔ)

1.1 網(wǎng)絡(luò)斷層掃描的基本概念

網(wǎng)絡(luò)斷層掃描通過(guò)在網(wǎng)絡(luò)邊界上進(jìn)行端到端(end-to-end)的測(cè)量,來(lái)推斷網(wǎng)絡(luò)內(nèi)部狀態(tài)和通信行為.為此,基于網(wǎng)絡(luò)斷層掃描的測(cè)量方法包含3 個(gè)主要步驟:①網(wǎng)絡(luò)模型構(gòu)建階段,明確網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)性能模型;② 測(cè)量數(shù)據(jù)收集階段,通過(guò)在網(wǎng)絡(luò)節(jié)點(diǎn)或邊界上部署具有監(jiān)測(cè)能力的裝置(即監(jiān)測(cè)節(jié)點(diǎn)),并采用主動(dòng)測(cè)量或被動(dòng)測(cè)量的方式,從監(jiān)測(cè)節(jié)點(diǎn)上收集端到端的網(wǎng)絡(luò)測(cè)量數(shù)據(jù);③測(cè)量數(shù)據(jù)分析階段,根據(jù)網(wǎng)絡(luò)性能模型建立性能推測(cè)方法,運(yùn)用統(tǒng)計(jì)學(xué)理論對(duì)測(cè)量數(shù)據(jù)進(jìn)行分析處理,從而推算出網(wǎng)絡(luò)內(nèi)部性能指標(biāo).

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

當(dāng)前,網(wǎng)絡(luò)性能測(cè)量成為了網(wǎng)絡(luò)斷層掃描的一個(gè)主要研究目標(biāo).通過(guò)對(duì)網(wǎng)絡(luò)時(shí)延、丟包率和吞吐量等性能指標(biāo)進(jìn)行數(shù)據(jù)采集和統(tǒng)計(jì),分析網(wǎng)絡(luò)特定范圍或端到端路徑的連通性及有效性,以便于發(fā)現(xiàn)網(wǎng)絡(luò)瓶頸,優(yōu)化網(wǎng)絡(luò)配置,保障網(wǎng)絡(luò)服務(wù)質(zhì)量.此外,通過(guò)網(wǎng)絡(luò)斷層掃描測(cè)量得到的數(shù)據(jù),可用于網(wǎng)絡(luò)故障的定位,從而有助于網(wǎng)絡(luò)維護(hù)管理.

1.2 網(wǎng)絡(luò)斷層掃描的形式化表述

為了便于網(wǎng)絡(luò)斷層掃描方法的研究與設(shè)計(jì),通常需要對(duì)網(wǎng)絡(luò)模型、測(cè)量目標(biāo)和測(cè)量方法進(jìn)行形式化的表述.下面將簡(jiǎn)要介紹網(wǎng)絡(luò)斷層掃描在這幾方面常見(jiàn)的形式化表述方式.

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

Fig.1 A sample network topology圖1 一個(gè)簡(jiǎn)單網(wǎng)絡(luò)拓?fù)?/p>

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

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

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

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

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

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

需要說(shuō)明的是:雖然方程組(1)和方程組(2)表述的是對(duì)鏈路性能和狀態(tài)的測(cè)量,但網(wǎng)絡(luò)中節(jié)點(diǎn)的性能和狀態(tài)可以等價(jià)轉(zhuǎn)換為與其關(guān)聯(lián)鏈路的性能和狀態(tài),所以網(wǎng)絡(luò)斷層掃描方法仍然可以用方程組(1)和方程組(2)的形式來(lái)求解網(wǎng)絡(luò)節(jié)點(diǎn)的性能和狀態(tài).

1.3 網(wǎng)絡(luò)斷層掃描的簡(jiǎn)單例子

圖2 所示為一個(gè)包含7 個(gè)節(jié)點(diǎn)和11 條鏈路(鏈路l1～l11)的網(wǎng)絡(luò)拓?fù)?其中,m1,m2和m3為部署的3 個(gè)監(jiān)測(cè)節(jié)點(diǎn).為了測(cè)量出所有鏈路的時(shí)延,網(wǎng)絡(luò)斷層掃描方法在3 個(gè)監(jiān)測(cè)節(jié)點(diǎn)之間構(gòu)造了11 條測(cè)量路徑p1～p11.其中,1 條為m1與m2間的測(cè)量路徑,7 條為m1與m3間的測(cè)量路徑,3 條為m2與m3間的測(cè)量路徑.

Fig.2 A network topology with three monitors:m1,m2and m3圖2 部署3 個(gè)監(jiān)測(cè)節(jié)點(diǎn)(m1,m2和m3)的網(wǎng)絡(luò)拓?fù)?/p>

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

對(duì)于線性方程組Rx=c,由于測(cè)量矩陣R是列滿秩的(即rank(R)=11),所以鏈路時(shí)延x有唯一解,即x=R-1c.在圖2 中,盡管監(jiān)測(cè)節(jié)點(diǎn)間還可以選取其他形式的測(cè)量路徑(如l2l5l7l9),但這些額外的測(cè)量路徑都是與已有測(cè)量路徑(p1～p11)線性相關(guān)的,即,其他形式的路徑都可以用已有路徑(p1～p11)線性表示.因此,從鏈路性能測(cè)量的角度來(lái)說(shuō),p1～p11是一組最優(yōu)的測(cè)量路徑.此外,當(dāng)我們?nèi)我庖瞥粋€(gè)監(jiān)測(cè)節(jié)點(diǎn)(如m2)后,用剩余的7 條測(cè)量路徑(p2～p8)構(gòu)成的測(cè)量矩陣將不是列滿秩的,即剩余的7 條測(cè)量路徑將不能保證所有鏈路的可識(shí)別性.因此,從鏈路性能測(cè)量的角度來(lái)說(shuō),m1,m2和m3是一種最優(yōu)的監(jiān)測(cè)節(jié)點(diǎn)部署方式.

從圖2 的例子中可以看出,監(jiān)測(cè)節(jié)點(diǎn)部署和測(cè)量路徑構(gòu)造(或選取)對(duì)網(wǎng)絡(luò)斷層掃描方法的有效性有著重要的影響.下一節(jié)我們將詳細(xì)綜述國(guó)內(nèi)外在網(wǎng)絡(luò)斷層掃描監(jiān)測(cè)節(jié)點(diǎn)部署和測(cè)量路徑構(gòu)造等方面的研究進(jìn)展.

2 相關(guān)工作

近些年,網(wǎng)絡(luò)斷層掃描作為網(wǎng)絡(luò)測(cè)量領(lǐng)域的一個(gè)研究熱點(diǎn),得到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注.總體上,網(wǎng)絡(luò)斷層掃描包含網(wǎng)絡(luò)模型構(gòu)建、測(cè)量數(shù)據(jù)收集與測(cè)量數(shù)據(jù)分析這3 個(gè)主要步驟.其中,測(cè)量數(shù)據(jù)收集包含監(jiān)測(cè)節(jié)點(diǎn)部署、測(cè)量路徑構(gòu)造與選取.本節(jié)從監(jiān)測(cè)節(jié)點(diǎn)部署、測(cè)量路徑構(gòu)造與選取、測(cè)量數(shù)據(jù)分析與推斷這3 個(gè)方面對(duì)近些年國(guó)內(nèi)外代表性的研究工作進(jìn)行歸納分析,其中也包含對(duì)各研究工作網(wǎng)絡(luò)模型的闡述.

2.1 網(wǎng)絡(luò)監(jiān)測(cè)節(jié)點(diǎn)部署

如何獲取網(wǎng)絡(luò)內(nèi)部的有用信息,是網(wǎng)絡(luò)斷層掃描研究的重要組成部分.當(dāng)前,網(wǎng)絡(luò)斷層掃描的測(cè)量對(duì)象一般可分為網(wǎng)絡(luò)狀態(tài)參數(shù)和網(wǎng)絡(luò)性能指標(biāo).其中,網(wǎng)絡(luò)狀態(tài)參數(shù)包含網(wǎng)絡(luò)節(jié)點(diǎn)的配置信息和網(wǎng)絡(luò)鏈路的狀態(tài)信息,網(wǎng)絡(luò)性能指標(biāo)包括鏈路吞吐率、鏈路丟包率和鏈路時(shí)延等.這些指標(biāo)反映網(wǎng)絡(luò)的實(shí)時(shí)運(yùn)行狀態(tài).根據(jù)測(cè)量對(duì)象的不同,網(wǎng)絡(luò)監(jiān)測(cè)節(jié)點(diǎn)部署可以分為傳統(tǒng)網(wǎng)絡(luò)斷層掃描監(jiān)測(cè)節(jié)點(diǎn)部署和布爾網(wǎng)絡(luò)斷層掃描監(jiān)測(cè)節(jié)點(diǎn)部署.

2.1.1 傳統(tǒng)網(wǎng)絡(luò)斷層掃描監(jiān)測(cè)節(jié)點(diǎn)部署

傳統(tǒng)網(wǎng)絡(luò)斷層掃描技術(shù)主要針對(duì)網(wǎng)絡(luò)性能指標(biāo)的測(cè)量,即:基于監(jiān)測(cè)節(jié)點(diǎn)間端到端的測(cè)量數(shù)據(jù),推斷網(wǎng)絡(luò)內(nèi)部鏈路性能指標(biāo).由于網(wǎng)絡(luò)端到端測(cè)量數(shù)據(jù)的收集依賴于網(wǎng)絡(luò)模型(包括網(wǎng)絡(luò)拓?fù)?、網(wǎng)絡(luò)性能模型)和路由策略等的設(shè)定,當(dāng)前的研究工作考慮了網(wǎng)絡(luò)斷層掃描在不同網(wǎng)絡(luò)模型和路由策略下的監(jiān)測(cè)節(jié)點(diǎn)部署問(wèn)題.

就網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)而言,通常可分為有向拓?fù)浜蜔o(wú)向拓?fù)鋬煞N類(lèi)型:在有向網(wǎng)絡(luò)拓?fù)渲?兩節(jié)點(diǎn)間鏈路(如v1v2)性能在其不同通信方向上(如v1→v2和v2→v1)具有不同的表現(xiàn);相反,在無(wú)向網(wǎng)絡(luò)拓?fù)渲?兩節(jié)點(diǎn)間鏈路性能在其不同通信方向上有相同的表現(xiàn).對(duì)于有向網(wǎng)絡(luò)拓?fù)涞逆溌沸阅軠y(cè)量,Xia 等人[8]證明了除非網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都是監(jiān)測(cè)節(jié)點(diǎn),否則并不是所有鏈路的性能指標(biāo)都是可測(cè)的.Gurewitz 等人[9]進(jìn)一步證明了:當(dāng)只使用環(huán)路形式的測(cè)量路徑(measurement cycle)時(shí),即使在網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都是監(jiān)測(cè)節(jié)點(diǎn)的情況下,仍然不能準(zhǔn)確測(cè)量出所有鏈路的性能指標(biāo).對(duì)于無(wú)向網(wǎng)絡(luò)拓?fù)涞逆溌沸阅軠y(cè)量,文獻(xiàn)[10-13]提出了基于探測(cè)包往返時(shí)間RTT(round-trip time)逐跳式(hop-by-hop)地測(cè)量鏈路時(shí)延的方法.該方法需要網(wǎng)絡(luò)所有節(jié)點(diǎn)都運(yùn)行了網(wǎng)際控制報(bào)文協(xié)議(ICMP).然而在有些實(shí)際的網(wǎng)絡(luò)中,并不是所有的節(jié)點(diǎn)都允許使用ICMP 協(xié)議.此外,受因特網(wǎng)路由協(xié)議以及ICMP 協(xié)議的限制,探測(cè)包的往返路徑可能是不對(duì)稱(chēng)的,從而難以保證其測(cè)量結(jié)果的準(zhǔn)確性.由于逐跳測(cè)量方法在應(yīng)用上存在的缺陷,很多工作研究了端到端(end-to-end)測(cè)量方法的可行性.

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

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

為了提高網(wǎng)絡(luò)斷層掃描的靈活性,Dong 等人[20,21]提出了優(yōu)先鏈路(preferential link)的概念,將網(wǎng)絡(luò)中需要測(cè)量的鏈路指定為優(yōu)先鏈路.為了降低優(yōu)先鏈路測(cè)量的復(fù)雜度及減小監(jiān)測(cè)節(jié)點(diǎn)的部署范圍,Dong 等人首先提出了一種網(wǎng)絡(luò)拓?fù)洳眉羲惴⊿calpel[20].Scalpel 包含兩個(gè)主要階段:第1 個(gè)階段,從原拓?fù)渲胁玫舨缓瑑?yōu)先鏈路的2-點(diǎn)連通分支(biconnected component)(如圖3(a)所示);第2 個(gè)階段,從第1 階段裁剪后的圖中裁掉一些邊緣的3-點(diǎn)連通分支(triconnected component)和環(huán)分支(cycle).需要注意的是:在剩余的拓?fù)鋱D中部署監(jiān)測(cè)節(jié)點(diǎn),可能無(wú)法達(dá)到在原拓?fù)鋱D中部署的效果.為了不影響監(jiān)測(cè)節(jié)點(diǎn)部署的性能,Scalpel 會(huì)從每一個(gè)被裁剪的分支中選取一個(gè)輔助節(jié)點(diǎn)(如圖3(b)所示).在使用Scalpel 算法對(duì)原拓?fù)鋱DG進(jìn)行裁剪后,得到一個(gè)剩余的拓?fù)鋱DGt及輔助節(jié)點(diǎn)集合H.以圖Gt和節(jié)點(diǎn)集合H為輸入,Dong 等人進(jìn)一步設(shè)計(jì)了最優(yōu)監(jiān)測(cè)節(jié)點(diǎn)部署算法OMA(optimal monitor assignment)[21],通過(guò)從圖Gt和輔助節(jié)點(diǎn)集合H中選取最少數(shù)量的節(jié)點(diǎn)作為監(jiān)測(cè)節(jié)點(diǎn),實(shí)現(xiàn)對(duì)原網(wǎng)絡(luò)拓?fù)銰中所有優(yōu)先鏈路的性能指標(biāo)的測(cè)量.上述這些旨在實(shí)現(xiàn)部分網(wǎng)絡(luò)可識(shí)別性的監(jiān)測(cè)節(jié)點(diǎn)部署算法有助于服務(wù)提供商和管理員以較小的成本滿足網(wǎng)絡(luò)測(cè)量需求,提高了網(wǎng)絡(luò)斷層掃描算法的靈活性.

Fig.3 Illustrative example for the two stages of topology trimming algorithm圖3 網(wǎng)絡(luò)拓?fù)洳眉羲惴ò膬蓚€(gè)階段的說(shuō)明示例

2.1.2 布爾網(wǎng)絡(luò)斷層掃描監(jiān)測(cè)節(jié)點(diǎn)部署

當(dāng)服務(wù)提供商和管理員想要測(cè)量的是網(wǎng)絡(luò)狀態(tài)參數(shù)時(shí),要用到布爾形式的網(wǎng)絡(luò)斷層掃描技術(shù).其中,網(wǎng)絡(luò)內(nèi)部運(yùn)行狀態(tài)可以用有限個(gè)零散數(shù)值表示,例如,用“0”表示鏈路通信正常,用“1”表示鏈路通信故障.

網(wǎng)絡(luò)擁塞已成為網(wǎng)絡(luò)傳輸性能和擴(kuò)展性的重要影響因素,及時(shí)準(zhǔn)確地定位網(wǎng)絡(luò)擁塞,有助于網(wǎng)絡(luò)性能調(diào)優(yōu)和協(xié)議設(shè)計(jì).基于網(wǎng)絡(luò)中同時(shí)發(fā)生擁塞的鏈路數(shù)目較少的假設(shè)和給定的端到端路徑測(cè)量信息,文獻(xiàn)[22-24]使用壓縮感知技術(shù)來(lái)識(shí)別因特網(wǎng)中發(fā)生擁塞的鏈路.在算法的實(shí)現(xiàn)中,通過(guò)引入一個(gè)用于判斷鏈路通信正常與否的閾值,從而將鏈路性能小于閾值的數(shù)值轉(zhuǎn)化為零.通過(guò)壓縮感知技術(shù),可以有效地恢復(fù)出鏈路性能大于閾值的數(shù)值,即識(shí)別網(wǎng)絡(luò)中擁塞的鏈路.對(duì)于鏈路通信故障的定位問(wèn)題,文獻(xiàn)[25-28]利用概率統(tǒng)計(jì)方法從網(wǎng)絡(luò)中找出一組最少數(shù)量的鏈路故障,從而能夠完全解釋測(cè)量的端到端的路徑狀態(tài)信息.文獻(xiàn)[29,30]基于端到端的測(cè)量信息,使用貝葉斯方法計(jì)算網(wǎng)絡(luò)中每一條鏈路發(fā)生故障的概率.

上述研究工作對(duì)網(wǎng)絡(luò)允許的鏈路故障數(shù)目具有較嚴(yán)格的要求,在大規(guī)模網(wǎng)絡(luò)場(chǎng)景中,難以保證其有效性.針對(duì)特定形式的通信模型(如客戶-服務(wù)器),其網(wǎng)絡(luò)拓?fù)渫鄬?duì)固定.Duffield 等人[31]提出了一種簡(jiǎn)捷有效的鏈路故障定位算法,利用客戶端與服務(wù)器之間路徑的相似性,能夠基于少數(shù)端到端測(cè)量信息,定位網(wǎng)絡(luò)故障鏈路.進(jìn)一步地,Ahuja 等人[32]形式化分析了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、監(jiān)測(cè)節(jié)點(diǎn)部署和鏈路故障識(shí)別三者的關(guān)系,并推導(dǎo)了在使用包含環(huán)路的測(cè)量路徑時(shí),鏈路故障的可識(shí)別性條件,并提出了一個(gè)最優(yōu)監(jiān)測(cè)節(jié)點(diǎn)部署算法,以準(zhǔn)確定位出任意k條鏈路的通信故障.另一方面,有些工作關(guān)注于對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)通信故障的監(jiān)測(cè)和定位.文獻(xiàn)[33-35]研究了在不同探測(cè)包路由策略(任意可控路由、可控?zé)o環(huán)路由和不可控路由)下,網(wǎng)絡(luò)節(jié)點(diǎn)通信故障的定位問(wèn)題.具體地,文獻(xiàn)[33,34]提出了有效的算法來(lái)計(jì)算對(duì)于給定的網(wǎng)絡(luò)拓?fù)浜捅O(jiān)測(cè)節(jié)點(diǎn)部署,在一個(gè)特定節(jié)點(diǎn)集合中,最多可以同時(shí)發(fā)生故障的節(jié)點(diǎn)數(shù)目,以及給定允許發(fā)生故障的節(jié)點(diǎn)數(shù)目時(shí),可以明確推算出狀態(tài)的最大節(jié)點(diǎn)集合.針對(duì)采用客戶-服務(wù)器通信模型的網(wǎng)絡(luò),He 等人[36]提出了有效的服務(wù)器節(jié)點(diǎn)部署算法,通過(guò)測(cè)量服務(wù)器節(jié)點(diǎn)與客戶端之間的路徑信息,從而最大化可定位節(jié)點(diǎn)故障的數(shù)量.該算法有利于拓展布爾網(wǎng)絡(luò)斷層掃描的適用范圍.更為一般地,Bartolini 等人[37]推導(dǎo)了在給定測(cè)量路徑數(shù)目、路由策略和網(wǎng)絡(luò)拓?fù)湫问?如樹(shù)狀和網(wǎng)狀拓?fù)?等一般性信息的情況下,可以定位的發(fā)生通信故障節(jié)點(diǎn)的最大數(shù)量.該理論結(jié)果可以為網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)和路由選擇等操作提供參考和指導(dǎo).

2.2 測(cè)量路徑構(gòu)造與選取

在網(wǎng)絡(luò)斷層掃描中,端到端測(cè)量數(shù)據(jù)的收集取決于使用的測(cè)量路徑形式,不同的測(cè)量路徑很可能產(chǎn)生不同的測(cè)量數(shù)據(jù),從而可能得到不同的測(cè)量結(jié)果.近些年,很多工作從幾何代數(shù)的角度研究了測(cè)量路徑的構(gòu)造和選取問(wèn)題.當(dāng)測(cè)量路徑可以包含環(huán)路時(shí),Gopalan 等人[38]提出了一種基于給定網(wǎng)絡(luò)監(jiān)測(cè)節(jié)點(diǎn)的線性無(wú)關(guān)(linearly independent)測(cè)量路徑構(gòu)造方法,并形式化證明了算法構(gòu)造的測(cè)量路徑是監(jiān)測(cè)節(jié)點(diǎn)之間存在的一組最大數(shù)量的線性無(wú)關(guān)路徑.該算法為基于環(huán)路測(cè)量路徑的網(wǎng)絡(luò)斷層掃描技術(shù)(如最少監(jiān)測(cè)節(jié)點(diǎn)部署[18])的實(shí)際應(yīng)用奠定了基礎(chǔ).當(dāng)測(cè)量路徑不允許包含環(huán)路時(shí),Wing 等人[39]推導(dǎo)了不同網(wǎng)絡(luò)(有向和無(wú)向拓?fù)渚W(wǎng)絡(luò))中線性無(wú)關(guān)路徑數(shù)目的界限值.

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

Fig.4 Illustrative example with a network topology and three independent spanning trees rooted at node 1圖4 網(wǎng)絡(luò)拓?fù)浼捌湟怨?jié)點(diǎn)1 為根節(jié)點(diǎn)的3 棵獨(dú)立生成樹(shù)的說(shuō)明示例

測(cè)量路徑的使用數(shù)量,很大程度上決定了探測(cè)包流量的大小[41-44].為降低測(cè)量負(fù)載對(duì)網(wǎng)絡(luò)正常通信的影響,有些工作關(guān)注于對(duì)測(cè)量路徑的選取及測(cè)量路徑數(shù)目的減少.針對(duì)網(wǎng)絡(luò)路徑性能測(cè)量問(wèn)題,Chen 等人[45]提出了一個(gè)在給定監(jiān)測(cè)節(jié)點(diǎn)部署的測(cè)量路徑選取方法,通過(guò)選取并測(cè)量一定數(shù)量線性無(wú)關(guān)的路徑,從而可以計(jì)算出其他路徑的性能指標(biāo).為了說(shuō)明測(cè)量路徑選取方法的可擴(kuò)展性,Chen 等人[45]還推導(dǎo)了在任意規(guī)模的網(wǎng)絡(luò)中,線性無(wú)關(guān)路徑選取數(shù)目的界限值,并將該界限值表達(dá)成網(wǎng)絡(luò)鏈路數(shù)目的線性函數(shù)形式.該結(jié)果為路徑選取方法在大規(guī)模網(wǎng)絡(luò)中的應(yīng)用提供了堅(jiān)實(shí)的理論依據(jù).注意到網(wǎng)絡(luò)路徑大多都是線性相關(guān)的,文獻(xiàn)[46,47]基于給定的一組路徑測(cè)量信息,利用線性代數(shù)方法計(jì)算出其他未被測(cè)量的子路徑上的性能指標(biāo).針對(duì)網(wǎng)絡(luò)鏈路性能測(cè)量問(wèn)題,Tang等人[48]基于網(wǎng)絡(luò)拓?fù)浜吐窂较嚓P(guān)性信息設(shè)計(jì)了一種有效的路徑選取方法,通過(guò)收集監(jiān)測(cè)節(jié)點(diǎn)間少量路徑的性能數(shù)據(jù),推算出網(wǎng)絡(luò)內(nèi)部細(xì)粒度的鏈路性能界限值.

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

2.3 測(cè)量數(shù)據(jù)分析與推斷

在網(wǎng)絡(luò)斷層掃描技術(shù)中,監(jiān)測(cè)節(jié)點(diǎn)按照一定規(guī)律(如周期性)或一定模式(如泊松分布)沿著測(cè)量路徑發(fā)送探測(cè)數(shù)據(jù)包,將可以收集到一組(或一系列)端到端的測(cè)量數(shù)據(jù).如何基于收集的測(cè)量數(shù)據(jù)準(zhǔn)確地推斷網(wǎng)絡(luò)內(nèi)部性能和狀態(tài)對(duì)測(cè)量方法的有效性顯得尤為重要.本節(jié)將簡(jiǎn)要介紹網(wǎng)絡(luò)斷層掃描常用的數(shù)據(jù)分析與推斷方法.

根據(jù)網(wǎng)絡(luò)性能參數(shù)特征,現(xiàn)有網(wǎng)絡(luò)斷層掃描的數(shù)據(jù)分析方法大致可以分為統(tǒng)計(jì)學(xué)習(xí)方法和代數(shù)計(jì)算方法.其中,統(tǒng)計(jì)學(xué)習(xí)方法針對(duì)的是性能參數(shù)在探測(cè)包收集過(guò)程中會(huì)變化的測(cè)量數(shù)據(jù),而代數(shù)計(jì)算方法針對(duì)的是性能參數(shù)在探測(cè)包收集過(guò)程中相對(duì)穩(wěn)定的測(cè)量數(shù)據(jù).

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

Fig.5 Statistical learning procedures for measurement data analysis圖5 測(cè)量數(shù)據(jù)分析的統(tǒng)計(jì)學(xué)習(xí)過(guò)程

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

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

3 應(yīng)用挑戰(zhàn)與關(guān)鍵技術(shù)

表1 總結(jié)了近些年網(wǎng)絡(luò)斷層掃描方法的相關(guān)研究成果.

概況地說(shuō),文獻(xiàn)[11,12,15,17]從探測(cè)數(shù)據(jù)包路由策略的角度研究了在實(shí)現(xiàn)網(wǎng)絡(luò)完全可識(shí)別性時(shí)的監(jiān)測(cè)節(jié)點(diǎn)部署問(wèn)題.其中,文獻(xiàn)[11,12]基于網(wǎng)絡(luò)默認(rèn)路由協(xié)議的鏈路性能測(cè)量問(wèn)題,并證明在基于網(wǎng)絡(luò)默認(rèn)路由(即不可控路由)策略下最少監(jiān)測(cè)節(jié)點(diǎn)的部署是一個(gè)NP 難問(wèn)題.隨后,文獻(xiàn)[15,17]分別從測(cè)量路徑是否允許包含環(huán)路的角度提出了基于可控路由策略的監(jiān)測(cè)節(jié)點(diǎn)部署理論和線性時(shí)間復(fù)雜度算法,從而為網(wǎng)絡(luò)斷層掃描技術(shù)的演變和改進(jìn)奠定了基礎(chǔ).受網(wǎng)絡(luò)測(cè)量成本的限制,文獻(xiàn)[18-21]從實(shí)現(xiàn)網(wǎng)絡(luò)部分可識(shí)別性的角度解決了監(jiān)測(cè)節(jié)點(diǎn)的部署問(wèn)題,確保可以用有限的成本滿足服務(wù)提供商和網(wǎng)絡(luò)管理員的測(cè)量需求,從而提高了網(wǎng)絡(luò)斷層掃描算法的靈活性.另一方面,網(wǎng)絡(luò)內(nèi)部運(yùn)行狀態(tài)也是網(wǎng)絡(luò)測(cè)量的重要組成部分.文獻(xiàn)[32-34,36]從探測(cè)數(shù)據(jù)包路由策略的角度研究了對(duì)特定數(shù)目鏈路(或節(jié)點(diǎn))失效定位的監(jiān)測(cè)節(jié)點(diǎn)部署問(wèn)題,從而進(jìn)一步拓展了網(wǎng)絡(luò)斷層掃描技術(shù)的適用范圍.此外,文獻(xiàn)[38,40,45,49]從測(cè)量對(duì)象和路由策略的角度研究了測(cè)量路徑的構(gòu)造和選取問(wèn)題,并提出了相應(yīng)的多項(xiàng)式時(shí)間復(fù)雜度算法.這些工作為網(wǎng)絡(luò)斷層掃描技術(shù)在各種形式網(wǎng)絡(luò)中的實(shí)際應(yīng)用提供了必要的基礎(chǔ).

從表1 中可以看出:當(dāng)前已有許多網(wǎng)絡(luò)斷層掃描的理論和方法,但這些方法的設(shè)計(jì)在測(cè)量目標(biāo)(或測(cè)量對(duì)象)、網(wǎng)絡(luò)模型和測(cè)量成本等方面都有較為明確且嚴(yán)格的規(guī)定(或假設(shè)).這些規(guī)定假設(shè)雖然有利于方法的演變與驗(yàn)證,但也給方法的實(shí)際應(yīng)用帶來(lái)了局限性.

總體上,現(xiàn)有的網(wǎng)絡(luò)斷層掃描方法在性能測(cè)量粒度(及精度)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)通信模型這3 個(gè)核心方面都帶有較強(qiáng)的假設(shè)和要求(見(jiàn)表2),這影響了網(wǎng)絡(luò)斷層掃描方法在實(shí)際應(yīng)用中的有效性和通用性,甚至使得方法在有些網(wǎng)絡(luò)場(chǎng)景中難以被使用.總體上,設(shè)計(jì)一個(gè)通用、高效及魯棒的網(wǎng)絡(luò)斷層掃描方法面臨以下3 項(xiàng)關(guān)鍵挑戰(zhàn):測(cè)量成本非常受限、網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)性以及網(wǎng)絡(luò)通信的易失效性.近兩年,越來(lái)越多的研究者開(kāi)始關(guān)注已有網(wǎng)絡(luò)斷層掃描方法的局限性,并提出了相應(yīng)理論和關(guān)鍵技術(shù),以有效應(yīng)對(duì)這些挑戰(zhàn).本節(jié)歸納了在應(yīng)對(duì)上述挑戰(zhàn)的一些代表性研究工作及其關(guān)鍵技術(shù).

Table 1 Summary of network tomography methods表1 網(wǎng)絡(luò)斷層掃描方法總結(jié)

Table 2 Research status and key application challenges表2 現(xiàn)狀及應(yīng)用挑戰(zhàn)

3.1 粒度可調(diào)網(wǎng)絡(luò)斷層掃描理論與技術(shù)

· 挑戰(zhàn)

現(xiàn)有的網(wǎng)絡(luò)斷層掃描方法大多著重于實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中所有鏈路性能指標(biāo)確切值的測(cè)量,即測(cè)量粒度(及精度)單一且固定.這些方法存在兩個(gè)主要缺陷:一是受網(wǎng)絡(luò)拓?fù)浜吐酚刹呗缘鹊南拗?測(cè)量網(wǎng)絡(luò)所有鏈路性能的目標(biāo)在很多應(yīng)用場(chǎng)景中難以實(shí)現(xiàn);二是測(cè)量鏈路性能指標(biāo)的確切值往往會(huì)帶來(lái)很大的開(kāi)銷(xiāo),例如需要部署很多監(jiān)測(cè)節(jié)點(diǎn)和發(fā)送大量探測(cè)數(shù)據(jù)包.為此,提出粒度(及精度)可調(diào)的網(wǎng)絡(luò)斷層掃描理論,并設(shè)計(jì)一種粒度(及精度)可調(diào)的網(wǎng)絡(luò)斷層掃描算法以有效平衡性能指標(biāo)測(cè)量的精度與測(cè)量的開(kāi)銷(xiāo),顯得很有必要.

· 關(guān)鍵技術(shù)

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

以圖6 為例,網(wǎng)絡(luò)中有兩個(gè)節(jié)點(diǎn)(v2和v3)部署為了監(jiān)測(cè)節(jié)點(diǎn).假設(shè)網(wǎng)絡(luò)中10 條鏈路(l1～l10)上的時(shí)延分別為{x1=7,x2=1,x3=5,x4=4,x5=6,x6=8,x7=13,x8=10,x9=3,x10=3}.需要說(shuō)明的是,服務(wù)提供商與網(wǎng)絡(luò)管理員一開(kāi)始并不知道這些鏈路的時(shí)延,只有通過(guò)收集兩個(gè)監(jiān)測(cè)節(jié)點(diǎn)間端到端路徑的時(shí)延數(shù)據(jù),才能推算出單條鏈路的時(shí)延.因?yàn)榫W(wǎng)絡(luò)中只有v2和v3為監(jiān)測(cè)節(jié)點(diǎn),基于鏈路可識(shí)別性條件[16,18],已有的網(wǎng)絡(luò)斷層掃描方法只能測(cè)量出鏈路l1和l6的時(shí)延,即只有鏈路l1和l6是可識(shí)別的.而對(duì)于網(wǎng)絡(luò)中不可識(shí)別鏈路(l2～l5和l7～l10)的時(shí)延,已有的網(wǎng)絡(luò)斷層掃描方法不能提供任何信息.不同的是,通過(guò)使用文獻(xiàn)[60]的網(wǎng)絡(luò)斷層掃描方法,網(wǎng)絡(luò)管理員可以計(jì)算出不可識(shí)別鏈路上的時(shí)延范圍: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 測(cè)量性能指標(biāo)界限值的網(wǎng)絡(luò)斷層掃描說(shuō)明示例

通過(guò)對(duì)推算的鏈路性能指標(biāo)界限值區(qū)間長(zhǎng)度(bound interval length)賦上不同的約束,我們可以實(shí)現(xiàn)一種粒度可調(diào)的網(wǎng)絡(luò)斷層掃描.特別地,當(dāng)要求鏈路性能指標(biāo)界限值的區(qū)間長(zhǎng)度為0 時(shí)(即要獲得鏈路性能指標(biāo)的確切值),文獻(xiàn)[60]的方法轉(zhuǎn)化為已有網(wǎng)絡(luò)斷層掃描方法.因此,文獻(xiàn)[60]中的網(wǎng)絡(luò)斷層掃描方法是已有的網(wǎng)絡(luò)斷層掃描方法在測(cè)量目標(biāo)上的一種推廣演變.相比已有的旨在實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)所有鏈路性能指標(biāo)確切值的方法,雖然文獻(xiàn)[60]的網(wǎng)絡(luò)斷層掃描方法通過(guò)推算鏈路性能指標(biāo)界限值的方式能夠在很大程度上減少測(cè)量的開(kāi)銷(xiāo),但推算網(wǎng)絡(luò)所有鏈路性能指標(biāo)界限值的復(fù)雜度與網(wǎng)絡(luò)規(guī)模有很大關(guān)系,在大規(guī)模網(wǎng)絡(luò)中容易造成指數(shù)級(jí)時(shí)間復(fù)雜度.

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

考慮到服務(wù)提供商與網(wǎng)絡(luò)管理員在不同階段可能具有不同的測(cè)量需求,如:在網(wǎng)絡(luò)運(yùn)行階段,關(guān)注的是如何通過(guò)已有監(jiān)測(cè)節(jié)點(diǎn)有效地計(jì)算出網(wǎng)絡(luò)中優(yōu)先鏈路性能的界限值;在網(wǎng)絡(luò)擴(kuò)建或升級(jí)階段,關(guān)注的是如何部署更多數(shù)目的監(jiān)測(cè)節(jié)點(diǎn)以縮小計(jì)算的優(yōu)先鏈路性能界限的距離.為此,我們?cè)谖墨I(xiàn)[63]中同時(shí)解決了以下兩個(gè)關(guān)鍵問(wèn)題.

· 優(yōu)先鏈路性能指標(biāo)界限值計(jì)算:在一個(gè)給定監(jiān)測(cè)節(jié)點(diǎn)和優(yōu)先鏈路的網(wǎng)絡(luò)中,如何有效地推算出這些優(yōu)先鏈路性能指標(biāo)的最緊界限值,即最緊的上界值和最緊的下界值?

· 監(jiān)測(cè)節(jié)點(diǎn)部署:在一個(gè)給定初始監(jiān)測(cè)節(jié)點(diǎn)和優(yōu)先鏈路的網(wǎng)絡(luò)中,如何通過(guò)部署額外的監(jiān)測(cè)節(jié)點(diǎn)以進(jìn)一步縮小優(yōu)先鏈路性能界限區(qū)間的長(zhǎng)度(即上界值和下界值的差值)?

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

對(duì)于監(jiān)測(cè)節(jié)點(diǎn)部署問(wèn)題,基于對(duì)鏈路可識(shí)別性與優(yōu)先鏈路性能界限值松緊程度關(guān)系的分析,我們?cè)O(shè)計(jì)了一個(gè)高效的監(jiān)測(cè)節(jié)點(diǎn)部署算法NMPI[63].在網(wǎng)絡(luò)原有監(jiān)測(cè)節(jié)點(diǎn)的基礎(chǔ)上,部署一個(gè)新的監(jiān)測(cè)節(jié)點(diǎn),從而最大程度上減小優(yōu)先鏈路性能界限區(qū)間的長(zhǎng)度.首先,NMPI 的設(shè)計(jì)基于一個(gè)重要的觀察:在一個(gè)包含一組優(yōu)先鏈路的網(wǎng)絡(luò)中,對(duì)于新監(jiān)測(cè)節(jié)點(diǎn)的部署,不可識(shí)別的優(yōu)先鏈路性能指標(biāo)界限區(qū)間長(zhǎng)度只會(huì)受由新監(jiān)測(cè)節(jié)點(diǎn)部署增加的可識(shí)別鏈路的影響,從而相同的鏈路可識(shí)別性也會(huì)造成相同的優(yōu)先鏈路性能指標(biāo)界限區(qū)間長(zhǎng)度.因此,在監(jiān)測(cè)節(jié)點(diǎn)部署過(guò)程中,對(duì)網(wǎng)絡(luò)鏈路可識(shí)別性變化的分析成為了一個(gè)關(guān)鍵的問(wèn)題.

由于網(wǎng)絡(luò)可能部署有多個(gè)監(jiān)測(cè)節(jié)點(diǎn),而鏈路可識(shí)別性與單個(gè)監(jiān)測(cè)節(jié)點(diǎn)之間存在著復(fù)雜的關(guān)系,為了簡(jiǎn)化監(jiān)測(cè)節(jié)點(diǎn)部署對(duì)網(wǎng)絡(luò)鏈路可識(shí)別性變化的分析,NMPI 對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行擴(kuò)展操作.具體地,對(duì)于一個(gè)已有κ(κ≥2)個(gè)監(jiān)測(cè)節(jié)點(diǎn)的網(wǎng)絡(luò)G,引入兩個(gè)虛擬監(jiān)測(cè)節(jié)點(diǎn)(virtual monitor)1m′和m2′,同時(shí),在實(shí)際監(jiān)測(cè)節(jié)點(diǎn)(actual monitor)和虛擬監(jiān)測(cè)節(jié)點(diǎn)間增加2κ條虛擬鏈路,在兩個(gè)虛擬監(jiān)測(cè)節(jié)點(diǎn)之間也增加一條虛擬鏈路(virtual link),將新生成的拓?fù)浞Q(chēng)為網(wǎng)絡(luò)擴(kuò)展圖Gex(如圖7 所示).由于原網(wǎng)絡(luò)拓?fù)鋵?shí)際監(jiān)測(cè)節(jié)點(diǎn)之間的端到端測(cè)量都可以轉(zhuǎn)化為虛擬監(jiān)測(cè)節(jié)點(diǎn)1m′和m2′之間的端到端測(cè)量,并且對(duì)于網(wǎng)絡(luò)鏈路的測(cè)量,1m′和m2′之間的端到端測(cè)量相比實(shí)際監(jiān)測(cè)節(jié)點(diǎn)之間的端到端測(cè)量不會(huì)提供額外的信息,所以原網(wǎng)絡(luò)拓?fù)銰的鏈路可識(shí)別性與擴(kuò)展圖Gex的鏈路可識(shí)別性是一樣的,從而NMPI 可以關(guān)注于僅包含兩個(gè)監(jiān)測(cè)節(jié)點(diǎn)的擴(kuò)展圖Gex鏈路可識(shí)別性的變化.隨后,NMPI 通過(guò)對(duì)新監(jiān)測(cè)節(jié)點(diǎn)部署與網(wǎng)絡(luò)擴(kuò)展圖Gex結(jié)構(gòu)變化關(guān)系的分析,實(shí)現(xiàn)了新監(jiān)測(cè)節(jié)點(diǎn)在網(wǎng)絡(luò)擴(kuò)展圖Gex及原拓?fù)銰中的最優(yōu)部署.

Fig.7 Illustration of topology extension operation圖7 拓?fù)鋱D擴(kuò)展操作示例

此外,還有一些工作從測(cè)量對(duì)象的角度研究了粒度可調(diào)的網(wǎng)絡(luò)斷層掃描理論與技術(shù).注意到在實(shí)際應(yīng)用中,網(wǎng)絡(luò)用戶通常關(guān)心的是所用網(wǎng)絡(luò)服務(wù)的性能,例如從客戶端向服務(wù)器發(fā)送請(qǐng)求到客戶端收到回應(yīng)的時(shí)延,Yang等人[64]解決了網(wǎng)絡(luò)任意節(jié)點(diǎn)間端到端通信路徑性能的測(cè)量問(wèn)題,并提出了一種最優(yōu)的監(jiān)測(cè)節(jié)點(diǎn)部署算法MPIP,通過(guò)收集監(jiān)測(cè)節(jié)點(diǎn)間一組端到端測(cè)量數(shù)據(jù),以實(shí)現(xiàn)對(duì)任意指定路徑(即優(yōu)先路徑,interested path)性能指標(biāo)的推算.為便于網(wǎng)絡(luò)監(jiān)測(cè)節(jié)點(diǎn)的部署,文獻(xiàn)[64]首先研究了基于斷層掃描的網(wǎng)絡(luò)優(yōu)先路徑性能的可識(shí)別性理論,形式化表述了拓?fù)浣Y(jié)構(gòu)、監(jiān)測(cè)節(jié)點(diǎn)和路徑可識(shí)別性這三者的關(guān)系,并解決了給定監(jiān)測(cè)節(jié)點(diǎn)部署時(shí),網(wǎng)絡(luò)可識(shí)別路徑的判斷問(wèn)題.基于網(wǎng)絡(luò)路徑可識(shí)別性條件,MPIP 將網(wǎng)絡(luò)拓?fù)鋭澐殖啥鄠€(gè)2-點(diǎn)連通和3-點(diǎn)連通分支,根據(jù)各連通分支中優(yōu)先路徑特性,迭代地在各連通分支中部署必要的監(jiān)測(cè)節(jié)點(diǎn),從而用最少的監(jiān)測(cè)節(jié)點(diǎn)實(shí)現(xiàn)對(duì)所有優(yōu)先路徑性能指標(biāo)的計(jì)算.需要說(shuō)明的是,上述這些粒度(及精度)可調(diào)網(wǎng)絡(luò)斷層掃描方法[60,63,64]在實(shí)現(xiàn)過(guò)程中,使用的是不含環(huán)路的端到端測(cè)量路徑,這有利于提高方法在實(shí)際網(wǎng)絡(luò)中的可用性.

3.2 動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)斷層掃描理論與技術(shù)

· 挑戰(zhàn)

隨著物聯(lián)網(wǎng)、軟件定義網(wǎng)絡(luò)等新型網(wǎng)絡(luò)形態(tài)與網(wǎng)絡(luò)技術(shù)的興起,動(dòng)態(tài)的網(wǎng)絡(luò)路由拓?fù)湓絹?lái)越成為這些新型網(wǎng)絡(luò)的重要特點(diǎn)[65].例如在典型的物聯(lián)網(wǎng)場(chǎng)景中,動(dòng)態(tài)路由協(xié)議(如RPL[66]、低功耗藍(lán)牙m(xù)esh 網(wǎng)絡(luò)路由等)被廣泛用于應(yīng)對(duì)無(wú)線信道、節(jié)點(diǎn)位置等的動(dòng)態(tài)性,從而使得網(wǎng)絡(luò)路由拓?fù)洳粩喟l(fā)生變化.而在軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)中,流量分割(traffic splitting)[67]技術(shù)及重路由(re-routing)[68]技術(shù)被廣泛用于負(fù)載均衡,使得同一個(gè)數(shù)據(jù)流的數(shù)據(jù)包可以通過(guò)不同的路由到達(dá)接收端,從而導(dǎo)致了網(wǎng)絡(luò)路由拓?fù)涞膭?dòng)態(tài)性.現(xiàn)有網(wǎng)絡(luò)斷層掃描技術(shù)[16,17,19,21]的典型工作模式是基于已知的靜態(tài)網(wǎng)絡(luò)拓?fù)?部署一定數(shù)量的監(jiān)測(cè)節(jié)點(diǎn)并獲取監(jiān)測(cè)節(jié)點(diǎn)間探測(cè)包的測(cè)量數(shù)據(jù),然后結(jié)合網(wǎng)絡(luò)拓?fù)湫畔⒔㈥P(guān)于內(nèi)部運(yùn)行狀態(tài)的方程組,最后通過(guò)求解方程組完成網(wǎng)絡(luò)測(cè)量的目標(biāo).然而,當(dāng)網(wǎng)絡(luò)路由拓?fù)鋭?dòng)態(tài)變化時(shí),某一時(shí)刻存在的路由路徑下一時(shí)刻可能就不存在了,而某一時(shí)刻必要的監(jiān)測(cè)節(jié)點(diǎn)在另一時(shí)刻可能是冗余的.因此,如何在動(dòng)態(tài)拓?fù)涞臈l件下進(jìn)行精確、高效的網(wǎng)絡(luò)斷層掃描,是一個(gè)非常重要的問(wèn)題.

· 關(guān)鍵技術(shù)

在動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中,由于鏈路(或節(jié)點(diǎn))的動(dòng)態(tài)性,在某一個(gè)時(shí)刻的拓?fù)渲胁渴鸬谋O(jiān)測(cè)節(jié)點(diǎn)可能并不適用于另一個(gè)時(shí)刻拓?fù)渲墟溌返男阅軠y(cè)量.一種簡(jiǎn)捷的動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)測(cè)量方法是:當(dāng)網(wǎng)絡(luò)拓?fù)渥兓?利用基于靜態(tài)拓?fù)涞木W(wǎng)絡(luò)斷層掃描方法[21,25]在新生成的網(wǎng)絡(luò)拓?fù)渲兄匦虏渴鹨槐楸O(jiān)測(cè)節(jié)點(diǎn).這種應(yīng)急式(reactively)的部署方法雖然可以實(shí)現(xiàn)對(duì)多個(gè)網(wǎng)絡(luò)拓?fù)涞男阅軠y(cè)量,但頻繁地更換監(jiān)測(cè)節(jié)點(diǎn)部署位置一方面給網(wǎng)絡(luò)管理員帶來(lái)了不小的成本開(kāi)銷(xiāo),另一方面也不利于網(wǎng)絡(luò)測(cè)量任務(wù)的平穩(wěn)進(jìn)行.因此,在網(wǎng)絡(luò)拓?fù)渥兓?先驗(yàn)式(proactively)地實(shí)現(xiàn)對(duì)鏈路性能的測(cè)量顯得尤為重要.

He 等人[69]首次研究了動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)鏈路性能的測(cè)量問(wèn)題,并提出了一種有效的網(wǎng)絡(luò)斷層掃描方法,通過(guò)在網(wǎng)絡(luò)規(guī)劃初期,一次性部署一定數(shù)目的監(jiān)測(cè)節(jié)點(diǎn),以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)所有可能拓?fù)渲兴墟溌返男阅軠y(cè)量.然而,要想獲得動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中所有鏈路的性能,即使最優(yōu)的監(jiān)測(cè)節(jié)點(diǎn)部署算法也可能需要使用大量監(jiān)測(cè)節(jié)點(diǎn)(如網(wǎng)絡(luò)90%以上的節(jié)點(diǎn)需為監(jiān)測(cè)節(jié)點(diǎn)[69]),這將會(huì)造成很大的測(cè)量成本.另一方面,很多時(shí)候,服務(wù)提供商與網(wǎng)絡(luò)管理員只關(guān)注網(wǎng)絡(luò)某些鏈路的性能指標(biāo),例如處在網(wǎng)絡(luò)關(guān)鍵位置上的鏈路性能指標(biāo).通過(guò)測(cè)量網(wǎng)絡(luò)中優(yōu)先鏈路的性能指標(biāo),在滿足應(yīng)用需求的同時(shí),也可以很大程度上降低測(cè)量成本.為此,我們研究了面向動(dòng)態(tài)拓?fù)涞膬?yōu)先鏈路測(cè)量理論及技術(shù),其中包含多種高效及魯棒的網(wǎng)絡(luò)斷層掃描方法[70],通過(guò)在動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中部署盡量少的監(jiān)測(cè)節(jié)點(diǎn),以實(shí)現(xiàn)對(duì)所有可能拓?fù)渲袃?yōu)先鏈路的性能測(cè)量.不同于文獻(xiàn)[69]計(jì)算網(wǎng)絡(luò)所有鏈路性能指標(biāo)的要求,我們的方法旨在用更少的成本計(jì)算出網(wǎng)絡(luò)中任意指定的一組優(yōu)先鏈路的性能指標(biāo).當(dāng)指定網(wǎng)絡(luò)所有鏈路為優(yōu)先鏈路時(shí),對(duì)優(yōu)先鏈路性能指標(biāo)的測(cè)量問(wèn)題將轉(zhuǎn)化為對(duì)網(wǎng)絡(luò)所有鏈路性能指標(biāo)的測(cè)量問(wèn)題.因此,我們提出的網(wǎng)絡(luò)斷層掃描方法[70]是文獻(xiàn)[69]中網(wǎng)絡(luò)斷層掃描方法的泛化,具有更好的測(cè)量靈活性.下面我們簡(jiǎn)要介紹實(shí)現(xiàn)對(duì)動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中優(yōu)先鏈路性能有效測(cè)量的網(wǎng)絡(luò)斷層掃描方法[70]的核心思想.

網(wǎng)絡(luò)斷層掃描方法的設(shè)計(jì)需要網(wǎng)絡(luò)拓?fù)湫畔⒆鳛榛A(chǔ),而盡早地獲取動(dòng)態(tài)網(wǎng)絡(luò)在各個(gè)時(shí)刻的拓?fù)湫畔?有助于監(jiān)測(cè)節(jié)點(diǎn)的部署.因此,我們首先研究了基于網(wǎng)絡(luò)拓?fù)漕A(yù)測(cè)的優(yōu)先鏈路可識(shí)別性理論,從而為動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)監(jiān)測(cè)節(jié)點(diǎn)的部署提供指導(dǎo).由于動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的周期性和可預(yù)測(cè)性(例如行車(chē)路線和運(yùn)行時(shí)刻固定的公交車(chē)網(wǎng)絡(luò)、睡眠/工作模式周期性交替的低功耗傳感網(wǎng)),可以利用拓?fù)鋾r(shí)空相關(guān)性及過(guò)去一段時(shí)間的網(wǎng)絡(luò)拓?fù)?預(yù)測(cè)未來(lái)一段時(shí)間內(nèi)的網(wǎng)絡(luò)拓?fù)?另一方面,我們?cè)O(shè)計(jì)了一種通用及簡(jiǎn)潔的時(shí)變網(wǎng)絡(luò)模型來(lái)刻畫(huà)動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)的在各個(gè)時(shí)刻的拓?fù)浣Y(jié)構(gòu).簡(jiǎn)單地說(shuō),我們將網(wǎng)絡(luò)測(cè)量周期(或生命周期)劃分成若干個(gè)等長(zhǎng)的時(shí)隙,然后將網(wǎng)絡(luò)在各個(gè)時(shí)隙上的拓?fù)浣Y(jié)構(gòu)用如下序列的形式來(lái)表述:

其中Gt表示網(wǎng)絡(luò)在第t個(gè)時(shí)隙上的拓?fù)?

圖8 所示為一個(gè)具有4 個(gè)節(jié)點(diǎn)(A～D)的動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)在3 個(gè)不同時(shí)隙上的拓?fù)浣Y(jié)構(gòu).

Fig.8 Illustrative example for topologies in different slots of a dynamic network圖8 動(dòng)態(tài)網(wǎng)絡(luò)在不同時(shí)隙的拓?fù)浣Y(jié)構(gòu)示例

確定了動(dòng)態(tài)網(wǎng)絡(luò)在各個(gè)不同時(shí)刻上的拓?fù)浜?我們提出了動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中優(yōu)先鏈路的可識(shí)別性理論,解決如何一次性部署盡量少的監(jiān)測(cè)節(jié)點(diǎn)以保證對(duì)網(wǎng)絡(luò)所有拓?fù)渲袃?yōu)先鏈路的性能測(cè)量問(wèn)題.具體地,考慮到監(jiān)測(cè)節(jié)點(diǎn)可能部署位置的數(shù)目將隨著網(wǎng)絡(luò)規(guī)模呈指數(shù)增長(zhǎng),我們分析優(yōu)先鏈路的可識(shí)別性與監(jiān)測(cè)節(jié)點(diǎn)部署位置的關(guān)系,通過(guò)裁剪掉對(duì)優(yōu)先鏈路性能測(cè)量無(wú)影響的部分節(jié)點(diǎn),縮小監(jiān)測(cè)節(jié)點(diǎn)部署的選擇范圍,從而加快網(wǎng)絡(luò)斷層掃描的實(shí)現(xiàn)過(guò)程.

隨后,我們解決了動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)的監(jiān)測(cè)節(jié)點(diǎn)部署問(wèn)題.注意到現(xiàn)有工作[20,21]已實(shí)現(xiàn)對(duì)靜態(tài)拓?fù)渚W(wǎng)絡(luò)中優(yōu)先鏈路性能測(cè)量的監(jiān)測(cè)節(jié)點(diǎn)部署算法,存在一種比較直接的動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)監(jiān)測(cè)節(jié)點(diǎn)部署方式:在網(wǎng)絡(luò)拓?fù)湫蛄?如公式(4)所示)中依次應(yīng)用靜態(tài)拓?fù)涞谋O(jiān)測(cè)節(jié)點(diǎn)部署算法,獲得網(wǎng)絡(luò)各時(shí)隙上的監(jiān)測(cè)節(jié)點(diǎn)部署,再將所有時(shí)隙上監(jiān)測(cè)節(jié)點(diǎn)部署的并集作為動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)最終的監(jiān)測(cè)節(jié)點(diǎn)部署結(jié)果.這種監(jiān)測(cè)節(jié)點(diǎn)部署方式雖然可以保證各網(wǎng)絡(luò)拓?fù)渲袃?yōu)先鏈路的可識(shí)別性,但可能會(huì)部署上冗余的監(jiān)測(cè)節(jié)點(diǎn),給服務(wù)提供商與網(wǎng)絡(luò)管理員造成了不必要的開(kāi)銷(xiāo).以圖9 所示的動(dòng)態(tài)網(wǎng)絡(luò)為例,在該網(wǎng)絡(luò)中,節(jié)點(diǎn)v2和節(jié)點(diǎn)v6在時(shí)隙1 的拓?fù)銰1中連通,在時(shí)隙2 的拓?fù)銰2中斷開(kāi).在網(wǎng)絡(luò)兩個(gè)時(shí)隙的拓?fù)渲?假設(shè)網(wǎng)絡(luò)管理員只需要測(cè)量鏈路v1v4和鏈路v1v5的性能.在拓?fù)銰1中,為了獲得這兩條優(yōu)先鏈路的性能,基于文獻(xiàn)[21]中的部署算法,我們可以從{v2,v3,v6,v7,v8}中任選兩個(gè)節(jié)點(diǎn)部署監(jiān)測(cè)節(jié)點(diǎn),所以M1={v6,v7}為一種可行的部署方式;而在拓?fù)銰2中,選v2和v3作為監(jiān)測(cè)節(jié)點(diǎn),可以測(cè)量出優(yōu)先鏈路v1v4和v1v5的性能,即M2={v2,v3}.因此,最終我們?cè)谠搫?dòng)態(tài)網(wǎng)絡(luò)中部署的監(jiān)測(cè)節(jié)點(diǎn)為M1∪M2={v2,v3,v6,v7},即需要4個(gè)監(jiān)測(cè)節(jié)點(diǎn).由于M2本身也適用于拓?fù)銰1中優(yōu)先鏈路性能的測(cè)量,這種對(duì)不同時(shí)隙網(wǎng)絡(luò)拓?fù)鋯为?dú)處理的方式部署了兩個(gè)冗余的監(jiān)測(cè)節(jié)點(diǎn),即v6和v7.

Fig.9 Illustrative example for monitoring node placement in a dynamic network圖9 動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)中監(jiān)測(cè)節(jié)點(diǎn)的部署示例

為此,在監(jiān)測(cè)節(jié)點(diǎn)的部署過(guò)程中,我們綜合考慮了動(dòng)態(tài)網(wǎng)絡(luò)各時(shí)隙拓?fù)渲斜O(jiān)測(cè)節(jié)點(diǎn)的部署需求,并用如下約束條件的方式刻畫(huà)單個(gè)拓?fù)涞谋O(jiān)測(cè)節(jié)點(diǎn)部署:

其中,Si為網(wǎng)絡(luò)節(jié)點(diǎn)集合,表示在單個(gè)拓?fù)渲锌晒┻x擇的監(jiān)測(cè)節(jié)點(diǎn)部署位置;ni表示從Si中至少需要選擇的節(jié)點(diǎn)數(shù)目.

得到動(dòng)態(tài)網(wǎng)絡(luò)每個(gè)拓?fù)渲斜O(jiān)測(cè)節(jié)點(diǎn)部署的約束條件后,我們將監(jiān)測(cè)節(jié)點(diǎn)的部署問(wèn)題規(guī)劃成最小碰撞集問(wèn)題(minimum hitting set problem,簡(jiǎn)稱(chēng)min-HSP).利用最優(yōu)化理論,可以從整個(gè)網(wǎng)絡(luò)中選取出最少數(shù)目的節(jié)點(diǎn)作為監(jiān)測(cè)節(jié)點(diǎn),以滿足各約束條件.相應(yīng)地,我們能夠用最少的監(jiān)測(cè)節(jié)點(diǎn)來(lái)保證動(dòng)態(tài)網(wǎng)絡(luò)中優(yōu)先鏈路的可識(shí)別性.

3.3 通信失效網(wǎng)絡(luò)斷層掃描理論與技術(shù)

· 挑戰(zhàn)

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

· 關(guān)鍵技術(shù)

對(duì)于特定的監(jiān)測(cè)節(jié)點(diǎn)部署,當(dāng)發(fā)生通信失效(如鏈路失效)時(shí),其能觀測(cè)到的路徑是不同的,包含失效鏈路的路徑將不能被觀測(cè)到,從而可能使原來(lái)可識(shí)別的鏈路變得不可識(shí)別.以圖10 中鏈路l6的測(cè)量為例,在該網(wǎng)絡(luò)拓?fù)渲?節(jié)點(diǎn)v2被部署為監(jiān)測(cè)節(jié)點(diǎn),通過(guò)測(cè)量3 條起止于v2的路徑性能數(shù)據(jù)(p1:l2l1l6,p2:l3l4l6,p3:l2l1l4l3),可以推算出鏈路l6的性能(如時(shí)延).用xi表示鏈路li的性能,ci表示路徑pi的性能,則3 條測(cè)量路徑的性能與鏈路性能可以用圖10 中的線性方程組關(guān)聯(lián)起來(lái),其中每條測(cè)量路徑分別對(duì)應(yīng)于方程組中的一個(gè)線性方程.通過(guò)求解該線性方程組,可以計(jì)算出鏈路l6的性能指標(biāo)值c6=(c1+c2-c3)/2,即鏈路l6在監(jiān)測(cè)節(jié)點(diǎn)v2下是可識(shí)別的.然而,當(dāng)鏈路l2發(fā)生通信失效時(shí),測(cè)量路徑p1:l2l1l6和p3:l2l1l4l3由于包含l2將變得不可用,方程組將只包含方程②的信息,此時(shí)鏈路l6將變得不可識(shí)別.因此,現(xiàn)有的監(jiān)測(cè)節(jié)點(diǎn)部署方法無(wú)法有效應(yīng)對(duì)鏈路失效對(duì)網(wǎng)絡(luò)性能測(cè)量的影響.值得注意的是,有些鏈路在網(wǎng)絡(luò)中任意其他k條鏈路失效的情況下仍然是可識(shí)別的.例如圖10 中l(wèi)3在網(wǎng)絡(luò)其他任意1 條鏈路失效時(shí),仍可以通過(guò)其他測(cè)量路徑的端到端數(shù)據(jù)推算出其性能指標(biāo)值.如果我們能夠了解怎樣的拓?fù)涮卣骺梢允沟面溌肪哂羞@種性質(zhì),將有助于指導(dǎo)監(jiān)測(cè)節(jié)點(diǎn)的部署以及網(wǎng)絡(luò)拓?fù)涞脑O(shè)計(jì),實(shí)現(xiàn)魯棒的網(wǎng)絡(luò)測(cè)量.此外,不同的監(jiān)測(cè)節(jié)點(diǎn)部署也可能導(dǎo)致不同的鏈路可識(shí)別性.如果將監(jiān)測(cè)節(jié)點(diǎn)部署在v5,那么無(wú)論有無(wú)鏈路失效發(fā)生,網(wǎng)絡(luò)中所有的鏈路都將變得不可識(shí)別.

?Fig.10 Example to illustrate the impact of link failures on network tomography圖10 鏈路失效對(duì)網(wǎng)絡(luò)斷層掃描的影響示例

針對(duì)這種情況,我們?cè)谖墨I(xiàn)[72,73]中研究了網(wǎng)絡(luò)失效下的鏈路可識(shí)別性理論,包含一條鏈路在其他任意k(k≥0)條鏈路失效情況下仍然可以識(shí)別的充分必要條件,并根據(jù)鏈路可識(shí)別性理論設(shè)計(jì)了監(jiān)測(cè)節(jié)點(diǎn)的部署算法,解決了如何在有鏈路失效的情況下部署監(jiān)測(cè)節(jié)點(diǎn),以進(jìn)行魯棒的網(wǎng)絡(luò)斷層掃描.首先,為了量化鏈路失效對(duì)鏈路性能識(shí)別性的影響,我們提出了k-可識(shí)別性(k-identifiability)的概念.

· 一條鏈路(非失效鏈路)被稱(chēng)為k-可識(shí)別的(k-identifiable),當(dāng)且僅當(dāng)該鏈路在網(wǎng)絡(luò)中任意k條鏈路失效時(shí)仍是可識(shí)別的;

· 一個(gè)網(wǎng)絡(luò)被稱(chēng)為k-可識(shí)別的,當(dāng)且僅當(dāng)網(wǎng)絡(luò)中所有鏈路都是k-可識(shí)別的.

需要說(shuō)明的是:當(dāng)k=0 時(shí),k-可識(shí)別表示當(dāng)網(wǎng)絡(luò)無(wú)通信失效時(shí)鏈路是可識(shí)別的(即已有網(wǎng)絡(luò)斷層掃描方法的可識(shí)別性),此時(shí)也記為0-可識(shí)別.k-可識(shí)別的鏈路一定是(k-1)可識(shí)別的,k越大,表示該鏈路對(duì)于其他鏈路失效的容忍度越大.可以看出:如果我們能得到鏈路k-可識(shí)別和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的關(guān)系,將幫助網(wǎng)絡(luò)管理者有效地部署監(jiān)測(cè)節(jié)點(diǎn),以使得網(wǎng)絡(luò)中k-可識(shí)別的鏈路數(shù)目盡可能多.同時(shí),這也能幫助網(wǎng)絡(luò)設(shè)計(jì)者了解如何設(shè)計(jì)網(wǎng)絡(luò)能夠使得網(wǎng)絡(luò)鏈路為k-可識(shí)別的,實(shí)現(xiàn)魯棒的網(wǎng)絡(luò)斷層掃描[74].

具體地,我們?cè)谖墨I(xiàn)[72,73]中通過(guò)回答以下兩個(gè)密切相關(guān)的問(wèn)題,來(lái)幫助網(wǎng)絡(luò)設(shè)計(jì)者和網(wǎng)絡(luò)管理員達(dá)到上述目標(biāo).

· 對(duì)于一個(gè)給定監(jiān)測(cè)節(jié)點(diǎn)部署的網(wǎng)絡(luò),哪些鏈路是k-可識(shí)別的?

· 對(duì)于一個(gè)給定監(jiān)測(cè)節(jié)點(diǎn)數(shù)目的網(wǎng)絡(luò),如何部署這些監(jiān)測(cè)節(jié)點(diǎn),以使網(wǎng)絡(luò)中k-可識(shí)別的鏈路數(shù)目最大?

針對(duì)k-可識(shí)別性鏈路的判斷問(wèn)題,對(duì)于一個(gè)有n條鏈路的網(wǎng)絡(luò)來(lái)說(shuō),網(wǎng)絡(luò)中k條鏈路失效的場(chǎng)景有種,通過(guò)枚舉每一種失效場(chǎng)景去判斷一條鏈路是否是k-可識(shí)別的是不可行的.為此,我們選擇通過(guò)對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行適當(dāng)劃分來(lái)研究鏈路k-可識(shí)別性在監(jiān)測(cè)節(jié)點(diǎn)部署和拓?fù)浣Y(jié)構(gòu)方面的判定理論.具體地,我們給出并證明了在不考慮鏈路失效(k=0)時(shí),鏈路可識(shí)別(0-可識(shí)別)的充分必要條件(見(jiàn)表3).在此基礎(chǔ)上,進(jìn)一步給出并證明了在考慮鏈路失效(k>0)時(shí),鏈路可識(shí)別(k-可識(shí)別)的充分必要條件(見(jiàn)表3).基于這些證明的鏈路k-可識(shí)別性條件,我們可以基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和監(jiān)測(cè)節(jié)點(diǎn)部署位置,在多項(xiàng)式時(shí)間內(nèi)判斷出一條鏈路是否是k-可識(shí)別的,而不需要枚舉所有鏈路失效情況,顯著降低了k-可識(shí)別性鏈路判定的復(fù)雜度.

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

對(duì)于特定數(shù)目(κ個(gè))監(jiān)測(cè)節(jié)點(diǎn)的部署問(wèn)題,一種比較直接的方法是:根據(jù)鏈路k可識(shí)別性的判定條件,在網(wǎng)絡(luò)中枚舉所有監(jiān)測(cè)節(jié)點(diǎn)部署位置,并比較每種部署情形下k可識(shí)別鏈路的數(shù)目,最后輸出使得k可識(shí)別鏈路數(shù)目最大的監(jiān)測(cè)節(jié)點(diǎn)部署方式.考慮到網(wǎng)絡(luò)中存在種可能的監(jiān)測(cè)節(jié)點(diǎn)部署方式,這種枚舉方法的復(fù)雜度將隨著網(wǎng)絡(luò)規(guī)模呈指數(shù)級(jí)增長(zhǎng),不具有可擴(kuò)展性.相反,我們?cè)谖墨I(xiàn)[72,73]中形式化地表述了特定數(shù)目監(jiān)測(cè)節(jié)點(diǎn)的部署問(wèn)題,并說(shuō)明了這是一個(gè)NP 完全問(wèn)題.隨后,我們提出了一種貪心算法MPK 來(lái)解決這個(gè)問(wèn)題.MPK 的核心思想是:因?yàn)樵诰W(wǎng)絡(luò)的(k+3)-邊連通分支中部署一個(gè)監(jiān)測(cè)節(jié)點(diǎn)必然能使其中的鏈路都是k-可識(shí)別的(見(jiàn)表3),所以MPK首先在(網(wǎng)絡(luò)的每個(gè)(k+3)-邊連通分支中隨機(jī)地選擇一個(gè)節(jié)點(diǎn),構(gòu)成監(jiān)測(cè)節(jié)點(diǎn)部署的候選集合.接著,MPK 枚舉了第1 個(gè)監(jiān)測(cè)節(jié)點(diǎn)部署的所有位置,這是因?yàn)榈? 個(gè)監(jiān)測(cè)節(jié)點(diǎn)不同的部署往往會(huì)給算法最后的結(jié)果帶來(lái)較大的影響.當(dāng)?shù)? 個(gè)監(jiān)測(cè)節(jié)點(diǎn)的位置選定后,MPK 將一個(gè)一個(gè)地從候選集合中選定剩余的κ-1 個(gè)監(jiān)測(cè)節(jié)點(diǎn).每次選擇中,MPK 都將選擇使得當(dāng)前k-可識(shí)別的鏈路數(shù)目最多的位置部署監(jiān)測(cè)節(jié)點(diǎn).需要說(shuō)明的是:通過(guò)此算法,我們可以逐步增加監(jiān)測(cè)節(jié)點(diǎn)的數(shù)目,直到網(wǎng)絡(luò)中所有鏈路都為k-可識(shí)別時(shí),此時(shí)的監(jiān)測(cè)節(jié)點(diǎn)部署為開(kāi)銷(xiāo)最小的部署方式.

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

4 總結(jié)和未來(lái)工作

與傳統(tǒng)網(wǎng)絡(luò)內(nèi)部測(cè)量方法不同,網(wǎng)絡(luò)斷層掃描作為一種新型的網(wǎng)絡(luò)外部測(cè)量方法,能夠在沒(méi)有中間節(jié)點(diǎn)協(xié)作的條件下,根據(jù)網(wǎng)絡(luò)邊緣的測(cè)量數(shù)據(jù)推測(cè)出網(wǎng)絡(luò)內(nèi)部性能指標(biāo)和運(yùn)行狀態(tài),從而實(shí)現(xiàn)與網(wǎng)絡(luò)組成及協(xié)議無(wú)關(guān)的網(wǎng)絡(luò)測(cè)量.本文首先給出了網(wǎng)絡(luò)斷層掃描的基本概念和形式化表述,并指出了影響網(wǎng)絡(luò)斷層掃描性能的3 個(gè)重要因素:監(jiān)測(cè)節(jié)點(diǎn)部署、測(cè)量路徑構(gòu)建和測(cè)量數(shù)據(jù)分析.接著,對(duì)近年來(lái)學(xué)術(shù)界在這3 個(gè)影響因素方面的代表性研究工作進(jìn)行了歸納分析.其中,針對(duì)網(wǎng)絡(luò)狀態(tài)識(shí)別問(wèn)題,本文還介紹了布爾形式網(wǎng)絡(luò)斷層掃描在監(jiān)測(cè)節(jié)點(diǎn)部署方面的研究成果.隨后,本文分析了已有網(wǎng)絡(luò)斷層掃描工作在實(shí)際應(yīng)用中的核心缺陷,并總結(jié)了針對(duì)這些核心缺陷近年來(lái)提出的最新理論及算法.

目前,網(wǎng)絡(luò)斷層掃描的發(fā)展和應(yīng)用仍然是網(wǎng)絡(luò)測(cè)量領(lǐng)域研究的熱點(diǎn),存在大量開(kāi)放性問(wèn)題有待更加深入的研究.以下列舉出幾個(gè)未來(lái)可能的發(fā)展方向.

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

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

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