一種不完全可測環(huán)境下的覆蓋網(wǎng)絡(luò)構(gòu)造方法

廖 怡，盛益強(qiáng)，王勁林

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190； 2.中國科學(xué)院大學(xué),北京 100049)

0 引 言

隨著計算機(jī)和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)中的接入設(shè)備不斷增多，尤其是移動設(shè)備的爆發(fā)式增長，極大地增加了網(wǎng)絡(luò)的移動性和動態(tài)性?；ヂ?lián)網(wǎng)規(guī)模的擴(kuò)展，服務(wù)需求不斷增長，對服務(wù)需求的處理提出了更高的要求，如何有效地管理大規(guī)模異構(gòu)節(jié)點、提高服務(wù)質(zhì)量是許多系統(tǒng)中的一個關(guān)鍵問題。在此背景下覆蓋網(wǎng)絡(luò)(overlay)構(gòu)造技術(shù)應(yīng)運(yùn)而生。

覆蓋網(wǎng)絡(luò)是構(gòu)建在現(xiàn)有的互聯(lián)網(wǎng)基礎(chǔ)之上，通過選擇和連接節(jié)點構(gòu)建一層新的網(wǎng)絡(luò)，節(jié)點之間通過虛擬邏輯鏈路連接起來，提供類似基礎(chǔ)設(shè)置所提供的基礎(chǔ)性服務(wù)，如路由、組播、內(nèi)容分發(fā)等[1]。覆蓋網(wǎng)絡(luò)通過探測底層物理網(wǎng)絡(luò)的鏈路狀態(tài)信息，并可根據(jù)需求在覆蓋網(wǎng)絡(luò)中為數(shù)據(jù)流計算路由路徑，再將數(shù)據(jù)流的轉(zhuǎn)發(fā)路徑發(fā)送給底層物理網(wǎng)絡(luò)，由底層物理網(wǎng)絡(luò)按指定的路徑傳輸。由于在選擇覆蓋節(jié)點構(gòu)建覆蓋網(wǎng)絡(luò)時，未充分考慮節(jié)點位置信息，或是對物理拓?fù)湫畔⑺鸭蝗虿粶?zhǔn)確，易導(dǎo)致拓?fù)洳黄ヅ鋯栴}[2]。拓?fù)洳黄ヅ渲饕?個在覆蓋網(wǎng)絡(luò)中相鄰的節(jié)點映射到實際物理網(wǎng)絡(luò)中卻相距很遠(yuǎn)，造成邏輯鏈路與底層物理鏈路不一致的現(xiàn)象[3]。在依據(jù)覆蓋網(wǎng)絡(luò)計算路由路徑時，僅依賴覆蓋網(wǎng)絡(luò)本身，未充分考慮互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的影響，易導(dǎo)致較大的時延開銷[1]。

近些年來，基于主動測量技術(shù)的覆蓋網(wǎng)絡(luò)構(gòu)造技術(shù)變得熱門，該類方法通過測量跳數(shù)、時延、帶寬甚至節(jié)點操作的歷史數(shù)據(jù)等信息構(gòu)造覆蓋網(wǎng)絡(luò)[4-6]。跳數(shù)、網(wǎng)絡(luò)延遲、帶寬等指標(biāo)能較好地反映底層物理網(wǎng)絡(luò)狀態(tài)。通過網(wǎng)絡(luò)測量可了解實時網(wǎng)絡(luò)狀態(tài)數(shù)據(jù)以便對覆蓋網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行調(diào)整，適應(yīng)網(wǎng)絡(luò)的動態(tài)性。然而基于測量技術(shù)的覆蓋網(wǎng)絡(luò)構(gòu)造方法其主要缺點是需要測量全局信息，或是在有限的時間內(nèi)難以獲取足夠多的節(jié)點信息，導(dǎo)致部分節(jié)點間的網(wǎng)絡(luò)狀態(tài)信息缺失，本文稱之為“不完全可測量”(Incomplete Measurable)問題。為此，首先定義不完全可測網(wǎng)絡(luò)的概念，其定義如下：

定義1不完全可測網(wǎng)絡(luò)

不完全可測網(wǎng)絡(luò)是指受網(wǎng)絡(luò)測量條件及方法所限或者網(wǎng)絡(luò)狀態(tài)及網(wǎng)絡(luò)條件所限導(dǎo)致網(wǎng)絡(luò)狀態(tài)信息不完全可測量的網(wǎng)絡(luò)。

網(wǎng)絡(luò)拓?fù)鋱D可用G={V,E,A,W}表示,其中，V為網(wǎng)絡(luò)中節(jié)點集合；E為節(jié)點間邊的集合，表示節(jié)點間的連接關(guān)系；A為網(wǎng)絡(luò)連接狀態(tài)屬性集合，該屬性可以是跳數(shù)、時延、帶寬等；W為A中對應(yīng)屬性的屬性值集合。若在網(wǎng)絡(luò)圖中的對象x在a∈A的屬性值a(x)為0，或者為空，則稱該網(wǎng)絡(luò)為不完全可測網(wǎng)絡(luò)(Incompletely Measurable Network， IMN)。

為解決信息不完全可測量的問題，在其他領(lǐng)域已有一些研究工作。文獻(xiàn)[7]提出了利用狀態(tài)估計的方法解決復(fù)雜網(wǎng)絡(luò)中無法直接測量所有狀態(tài)變量的問題，通過狀態(tài)估計方法減少由于不完全測量引起的偏差。在無線傳感器網(wǎng)絡(luò)中，可依據(jù)網(wǎng)絡(luò)測量技術(shù)對節(jié)點進(jìn)行定位，也存在不完全測量問題。文獻(xiàn)[8]針對不完全測距(即節(jié)點間的測距信息不完全，如傳感器網(wǎng)絡(luò)中因電子干擾、傳感器探測范圍有限和障礙物遮擋等因素導(dǎo)致部分節(jié)點間距離不可測)的高精度移動節(jié)點定位問題提出了基于分布式的多維標(biāo)度定位算法進(jìn)行局部定位與拼合，給出不完全測距下的移動傳感器網(wǎng)絡(luò)定位算法。

文獻(xiàn)[2]提出了一種基于測量的啟發(fā)式拓?fù)淦ヅ鋬?yōu)化算法(Measurement-based Heuristic Topology Matching Optimization Algorithm， MHTMOA)。該算法包括了節(jié)點加入、退出和失效算法，用于維護(hù)一個或者多個樹形覆蓋網(wǎng)絡(luò)，可應(yīng)用于廣域網(wǎng)絡(luò)的覆蓋網(wǎng)絡(luò)構(gòu)建。該算法通過網(wǎng)絡(luò)測量技術(shù)，獲取底層物理網(wǎng)絡(luò)中局部節(jié)點的跳數(shù)信息，利用跳數(shù)三角形的邊長關(guān)系，有效地將相近節(jié)點逐漸地匯聚，并通過三角不等式違反(Triangle Inequality Violation， TIV)感知以及啟發(fā)式規(guī)則選擇鄰居節(jié)點，每個節(jié)點最終可獲得一個準(zhǔn)確度較高的鄰居節(jié)點集合，生成的樹結(jié)構(gòu)能較好地與底層物理網(wǎng)絡(luò)匹配。TIV可對路由路徑進(jìn)行優(yōu)化，可有效減少長路由路徑，降低路由時延。

然而，MHTMOA拓?fù)錁?gòu)造方法也面臨著“不完全可測量”問題。在MHTMOA中網(wǎng)絡(luò)測量為按需測量，“需要什么測什么”。該方法易受網(wǎng)絡(luò)實時狀態(tài)的影響，一旦部分指標(biāo)不可測或不可獲取，將導(dǎo)致節(jié)點加入失敗。此外，隨著節(jié)點規(guī)模的增大，單個節(jié)點所需測量的節(jié)點信息呈線性增長，拓?fù)渚S護(hù)代價過高。對于結(jié)構(gòu)化的覆蓋網(wǎng)絡(luò)，尤其是在節(jié)點頻繁加入、頻繁退出的高攪動系統(tǒng)中，需要一個復(fù)雜度低、易于實現(xiàn)和維護(hù)的節(jié)點加入機(jī)制以提高系統(tǒng)運(yùn)行效率，節(jié)約運(yùn)營成本。

為此，本文在MHTMOA的基礎(chǔ)上實現(xiàn)一種用于不完全可測網(wǎng)絡(luò)的低復(fù)雜度、易于大規(guī)模擴(kuò)展的動態(tài)生成樹方法TCIM(Topology Construction for Incompletely Measurable)，以解決MHTMOA所存在的生成樹擴(kuò)展性較差、難以適用于節(jié)點頻繁加入/退出的環(huán)境、網(wǎng)絡(luò)信息難以完全測量等問題。該方法與MHTMOA的區(qū)別在于：

1)在MHTMOA中，采用路由跳數(shù)作為節(jié)點加入指標(biāo)，以選擇臨近的鄰居節(jié)點；在TCIM中，對指標(biāo)進(jìn)行擴(kuò)展，采用時延作為節(jié)點加入的指標(biāo)，評估基于時延所得覆蓋網(wǎng)絡(luò)的性能。

2)在MHTMOA的基礎(chǔ)上，提出一種基于常數(shù)測量次數(shù)的低復(fù)雜度節(jié)點加入算法，在保持一定的拓?fù)淦ヅ錅?zhǔn)確度的基礎(chǔ)上，根據(jù)節(jié)點規(guī)模和測量條件，自適應(yīng)地選擇常數(shù)個節(jié)點進(jìn)行測量，以實現(xiàn)低復(fù)雜度節(jié)點加入。在后文中，稱MHTMOA為高精度節(jié)點加入算法，高精度節(jié)點加入算法和低復(fù)雜度節(jié)點加入算法一起構(gòu)成了TCIM。

1 相關(guān)工作

覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)造方法有著廣泛的用途，在P2P[9-11]、無線自組織網(wǎng)絡(luò)[12-14]、IP多播[15-17]等領(lǐng)域發(fā)揮著重要作用。隨著網(wǎng)絡(luò)虛擬化技術(shù)的發(fā)展，借助軟件定義網(wǎng)絡(luò)(Software Defined Network， SDN)，基于SDN的覆蓋網(wǎng)絡(luò)解決方案變得熱門。SDN采用控制與轉(zhuǎn)發(fā)分離架構(gòu)，控制器作為集中式管理設(shè)備收集交換器相關(guān)的網(wǎng)絡(luò)拓?fù)涞男畔⒑彤?dāng)前網(wǎng)絡(luò)狀態(tài)信息，用于制定數(shù)據(jù)轉(zhuǎn)發(fā)路徑?，F(xiàn)有的許多SDN方案都是基于虛擬機(jī)所在的服務(wù)器上的軟件交換器構(gòu)建覆蓋網(wǎng)絡(luò)，SDN覆蓋網(wǎng)絡(luò)允許虛擬網(wǎng)絡(luò)拓?fù)浜团渲锚毩⒂谖锢砭W(wǎng)絡(luò)拓?fù)洹?/p>

不同的覆蓋網(wǎng)絡(luò)設(shè)計可實現(xiàn)不同的目標(biāo)。文獻(xiàn)[18]提出了一種在SDN控制器通過基于位置感知的多播方法(Location-Aware Multicast Approach， LAMA)構(gòu)建多組共享樹結(jié)構(gòu)，通過構(gòu)建多個由交換器節(jié)點構(gòu)成的共享樹結(jié)構(gòu)解決SDN覆蓋網(wǎng)絡(luò)的擴(kuò)展性問題。在LAMA中，每個共享樹可覆蓋多個組播組，控制器首先對位置相近的多播源進(jìn)行聚類。對于每個多播集群，控制器選擇一個與所有組播源的最小距離的中心交換器作為其會合點(Rendezvous Point， RP)，然后構(gòu)造從RP到其主機(jī)的最短路徑組播樹。基于構(gòu)建的多組共享樹，控制器可以在交換機(jī)上轉(zhuǎn)發(fā)流的目數(shù)。文獻(xiàn)[19]提出了一種基于覆蓋網(wǎng)絡(luò)的負(fù)載均衡方法，用于解決SDN中的流量工程問題?，F(xiàn)有的覆蓋網(wǎng)絡(luò)有很多的優(yōu)點，然而將經(jīng)典流量工程算法應(yīng)用于SDN覆蓋網(wǎng)絡(luò)中卻存在問題。該方法利用SDN集中控制的優(yōu)點，可針對異構(gòu)流量實現(xiàn)負(fù)載均衡。文獻(xiàn)[20]考慮采用基于OpenFlow的覆蓋網(wǎng)絡(luò)，建立現(xiàn)有網(wǎng)絡(luò)中服務(wù)器到OpenFlow覆蓋網(wǎng)絡(luò)中節(jié)點的映射以降低系統(tǒng)遷移成本。提議方法根據(jù)VLAN標(biāo)簽、VM和物理服務(wù)器IP地址自動構(gòu)建覆蓋網(wǎng)絡(luò)。

覆蓋網(wǎng)絡(luò)技術(shù)也被用作網(wǎng)絡(luò)疊加層以增加網(wǎng)絡(luò)彈性和恢復(fù)力。文獻(xiàn)[21]提出了一種通過“路由拐點”集合形成覆蓋網(wǎng)絡(luò)的方法，并利用該覆蓋網(wǎng)絡(luò)選擇2個數(shù)據(jù)中心之間最適合底層流量QoS需求的路徑。文獻(xiàn)[22]提出了一種彈性覆蓋網(wǎng)絡(luò)(Resilient Overlay Networks， RON)，在該網(wǎng)絡(luò)中通過主動測量技術(shù)探測覆蓋網(wǎng)絡(luò)中節(jié)點間的鏈路狀態(tài)，并基于測量結(jié)果構(gòu)建覆蓋網(wǎng)絡(luò)。在該方法中，在構(gòu)建彈性覆蓋網(wǎng)絡(luò)時需考慮底層網(wǎng)絡(luò)的結(jié)構(gòu)。主動測量能夠幫助覆蓋網(wǎng)絡(luò)快速地對故障做出反應(yīng)，以便及時對網(wǎng)絡(luò)狀態(tài)進(jìn)行調(diào)整，提高網(wǎng)絡(luò)的彈性。文獻(xiàn)[23]提出了一種基于并行化蟻群算法的網(wǎng)絡(luò)測量方法，解決網(wǎng)絡(luò)測量節(jié)點的自動選取問題。該方法對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，使其適用于網(wǎng)絡(luò)測量中測量節(jié)點的選取。其次，該文中設(shè)計并實現(xiàn)了蟻群算法的并行化框架，所提出的并行化蟻群算法不僅能滿足網(wǎng)絡(luò)測量節(jié)點選取的要求，同時相比于非并行化算法具有更快的收斂速度，更適用于大規(guī)模網(wǎng)絡(luò)測量。文獻(xiàn)[24]提出了一種與網(wǎng)絡(luò)操作無關(guān)的關(guān)鍵任務(wù)彈性覆蓋網(wǎng)絡(luò)(Resilient Overlay for Mission Critical Applications, ROMCA)。該方法使用中央目錄服務(wù)器存儲節(jié)點拓?fù)湫畔⒁院喕?jié)點發(fā)現(xiàn)過程，使用分布式的路由協(xié)議構(gòu)建不同的覆蓋網(wǎng)絡(luò)之間的路由，并使用基于ICMP的traceroute定期測量實現(xiàn)多路徑路由，實現(xiàn)覆蓋網(wǎng)絡(luò)之間路由路徑的多樣性。

此外覆蓋網(wǎng)絡(luò)也被應(yīng)用于內(nèi)容的傳播和推送。文獻(xiàn)[25]提出了一種用于地理分布式的數(shù)據(jù)中心中，發(fā)布/訂閱系統(tǒng)的主題連接覆蓋網(wǎng)絡(luò)(Topic Connected Overlay， TCO)構(gòu)建方法。該構(gòu)建方法同樣考慮將底層信息合并到覆蓋網(wǎng)絡(luò)設(shè)計中，對每個主題構(gòu)建子覆蓋網(wǎng)絡(luò)樹結(jié)構(gòu)。TCO中的節(jié)點是所有對相同主題感興趣的用戶節(jié)點。為使構(gòu)建覆蓋拓?fù)溆幸嬗诘讓佑嗛?分布系統(tǒng)網(wǎng)絡(luò)流量的最小化，在構(gòu)建覆蓋網(wǎng)絡(luò)時捕獲底層網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點間的物理位置，基于一些網(wǎng)絡(luò)級度量指標(biāo)來測量節(jié)點距離并作為TCO構(gòu)建的權(quán)值。

綜上，現(xiàn)有的覆蓋網(wǎng)絡(luò)可依據(jù)不同的需求和設(shè)計目標(biāo)構(gòu)建，為提高覆蓋網(wǎng)絡(luò)效率，可考慮利用底層物理網(wǎng)絡(luò)信息構(gòu)建拓?fù)?，利用現(xiàn)有的網(wǎng)絡(luò)測量技術(shù)獲取節(jié)點間的位置關(guān)系以提高覆蓋路由效率、QoS等，同時需考慮拓?fù)涞木S護(hù)代價、負(fù)載均衡、網(wǎng)絡(luò)彈性、容錯性和恢復(fù)力等因素。

2 一種用于不完全可測網(wǎng)絡(luò)的拓?fù)錁?gòu)造方法

2.1 TCIM算法

TCIM由2個子算法構(gòu)成，分別為高精度節(jié)點加入算法和低復(fù)雜度節(jié)點加入算法。其中高精度節(jié)點加入算法是基于MHTMOA[2]實現(xiàn)的，用于小規(guī)?；蜢o態(tài)/低動態(tài)性條件下的節(jié)點加入；低復(fù)雜度節(jié)點加入方法是在MHTMOA生成的小規(guī)模樹結(jié)構(gòu)之后的節(jié)點加入，可用于大規(guī)模、高動態(tài)以及網(wǎng)絡(luò)不完全可測條件下節(jié)點的加入。TCIM算法流程圖如圖1所示，其基本步驟是：

圖1 TCIM算法流程圖

步驟1檢測網(wǎng)絡(luò)中是否有節(jié)點加入/退出。若無，則系統(tǒng)等待，直到檢測到節(jié)點加入；若檢測到節(jié)點退出，則啟用MHTMOA中的節(jié)點退出方法，完成節(jié)點退出，再等待新的節(jié)點加入/退出；若檢測到節(jié)點加入，轉(zhuǎn)至步驟2。

步驟2判斷當(dāng)前生成樹的節(jié)點個數(shù)是否達(dá)到閾值N_initial。若當(dāng)前生成樹的規(guī)模未達(dá)到N_initial，先判斷拓?fù)涫欠裢耆蓽y，轉(zhuǎn)至步驟3。若當(dāng)前生成樹規(guī)模達(dá)到閾值N_initial，則啟用低復(fù)雜度節(jié)點加入方法，完成節(jié)點加入。

N_initial的選擇可根據(jù)用戶自定義。使用高精度節(jié)點加入算法生成的覆蓋網(wǎng)絡(luò)可保持較高的拓?fù)淦ヅ涠?；低?fù)雜度節(jié)點加入算法的維護(hù)成本低，因而用戶可根據(jù)所需生成的覆蓋網(wǎng)絡(luò)的精度需求和維護(hù)代價折衷地設(shè)置N_initial的值。

步驟3若所需的節(jié)點信息不完全可測，則切換到低復(fù)雜度節(jié)點加入方法，實現(xiàn)節(jié)點加入；若拓?fù)渫耆蓽y，則啟用高精度節(jié)點加入算法完成節(jié)點加入。節(jié)點加入操作完成后系統(tǒng)等待新的節(jié)點加入/退出。

2.2 高精度節(jié)點加入算法

圖2 時延三角形示意圖

圖3所示為按高精度節(jié)點加入算法生成的樹形覆蓋網(wǎng)絡(luò)結(jié)構(gòu)圖。從圖3(a)、圖3(b)可看出采用時延指標(biāo)的高精度節(jié)點算法生成的樹形覆蓋網(wǎng)絡(luò)可較好地保持節(jié)點間的鄰居關(guān)系，與物理網(wǎng)絡(luò)匹配程度高。

圖3 基于時延構(gòu)建的生成樹結(jié)構(gòu)

2.3 低復(fù)雜度節(jié)點加入算法

若當(dāng)前樹形節(jié)點總數(shù)達(dá)到算法啟動閾值N_initial，則啟用低復(fù)雜度節(jié)點加入算法，算法流程如圖4所示。其基本步驟如下：

圖4 低復(fù)雜度節(jié)點加入算法流程圖

步驟1設(shè)置節(jié)點探測個數(shù)N_detect的初始化范圍[N_detectmin，N_detectmax]以及自適應(yīng)調(diào)整步長的默認(rèn)值S。

步驟2利用網(wǎng)絡(luò)感知技術(shù)，測量當(dāng)前網(wǎng)絡(luò)狀態(tài)，獲取網(wǎng)絡(luò)狀態(tài)參數(shù)，例如時延、帶寬等，并以當(dāng)前的網(wǎng)絡(luò)狀態(tài)參數(shù)和樹形結(jié)構(gòu)的總數(shù)作為節(jié)點探測自適應(yīng)方法的輸入?yún)?shù)，查找自適應(yīng)調(diào)整步長表，得到當(dāng)前節(jié)點探測個數(shù)調(diào)整步長Sat、當(dāng)前節(jié)點探測個數(shù)N_detect=N_detect+Sat，其中Sat可正可負(fù)，最終得到動態(tài)的節(jié)點探測個數(shù)。

系統(tǒng)中先預(yù)存了一張網(wǎng)絡(luò)狀況指標(biāo)-節(jié)點規(guī)模-調(diào)整步長的映射表。該表在對網(wǎng)絡(luò)狀況指標(biāo)進(jìn)行量化分級的基礎(chǔ)上，結(jié)合節(jié)點規(guī)模，得到相應(yīng)的調(diào)整步長Sat。

步驟3根據(jù)得到的N_detect，從已有的樹形節(jié)點中隨機(jī)或者有條件地選擇N_detect個節(jié)點，利用網(wǎng)絡(luò)測量技術(shù)測量待加入節(jié)點到探測節(jié)點間的時延。

步驟4選擇時延最小的節(jié)點作為待加入節(jié)點的父節(jié)點；更新加入節(jié)點的父節(jié)點指針，更新選中的節(jié)點的子節(jié)點個數(shù)及子節(jié)點列表。

TCIM具有復(fù)雜度低、適用于大規(guī)模節(jié)點、適用于高動態(tài)性系統(tǒng)等優(yōu)點。TCIM中的高精度節(jié)點加入方法相較于用最小生成樹算法(例如Prime算法、Kruskal算法)，時間復(fù)雜度為O(ElogV)(其中E為邊的總數(shù)，V為節(jié)點總數(shù))。TCIM中的低復(fù)雜度節(jié)點加入算法將時間復(fù)雜度降為O(1)，時間復(fù)雜度低，有利于生成樹的大規(guī)模擴(kuò)展。其次，TCIM生成樹方法是動態(tài)的，不需要獲取網(wǎng)絡(luò)全局信息，只需根據(jù)網(wǎng)絡(luò)測量獲得的少量局部信息即可完成節(jié)點的加入。在節(jié)點加入過程中，每個節(jié)點只需要存儲鄰居節(jié)點信息，可實現(xiàn)鄰域自治，樹形結(jié)構(gòu)易于維護(hù)，算法的空間復(fù)雜度低。

3 仿真結(jié)果及分析

3.1 實驗設(shè)置

本文的對比方法采用Anysee2中使用的經(jīng)典的基于節(jié)點編碼的最長前綴匹配算法[26]，并將該方法與界標(biāo)法相結(jié)合作為對比算法(簡稱Landmark+Anysee)和Pan[27]在2015年提出的基于DHT的覆蓋構(gòu)造算法(后文簡稱Pan)，該算法利用不同的界標(biāo)節(jié)點和IP來解決拓?fù)洳黄ヅ鋯栴}。在Landmark+Anysee方法中，界標(biāo)個數(shù)為12。

本文通過BRITE拓?fù)渖善鱗28]產(chǎn)生了3種不同模型的網(wǎng)絡(luò)拓?fù)?，分別為Waxman、BA、Top-Down模型，作為底層物理網(wǎng)絡(luò)，并在不同的網(wǎng)絡(luò)節(jié)點規(guī)模下比較本文提議的TCIM算法與對比方法的性能。在3種網(wǎng)絡(luò)模型中，BA模型和Waxman模型是扁平網(wǎng)絡(luò)模型；Top-Down是自上而下的雙層網(wǎng)絡(luò)模型，tier-0表示AS級網(wǎng)絡(luò)，tier-1表示底層網(wǎng)絡(luò)節(jié)點。3種網(wǎng)絡(luò)模型的度分布如圖5所示，拓?fù)涞膮?shù)設(shè)置如表1所示。仿真實驗是在Window64、Intel i5 8250U CPU、8 GB RAM硬件環(huán)境中實現(xiàn)的。

圖5 3種網(wǎng)絡(luò)模型的度分布

表1 實驗參數(shù)設(shè)置

參數(shù)名稱設(shè)置節(jié)點規(guī)模N100,200,400,800,1600,3200,6400節(jié)點最小度m2節(jié)點帶寬范圍(100 kB,1 MB)Waxman參數(shù)α=0.15,β=0.2

本文使用Latency Stretch(LS)表示物理網(wǎng)絡(luò)和覆蓋網(wǎng)絡(luò)之間的匹配度。此外還采用了文獻(xiàn)[2]中定義的全局拓?fù)淦ヅ浔?GTMR)和局部鄰居節(jié)點準(zhǔn)確率(LNA)2個指標(biāo)，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上描述覆蓋網(wǎng)絡(luò)與物理網(wǎng)絡(luò)的匹配程度。GTMR表示在實際的物理網(wǎng)絡(luò)中直接相連的2個點，根據(jù)節(jié)點加入算法加入樹形拓?fù)浣Y(jié)構(gòu)后2個節(jié)點仍然保持連接關(guān)系的鏈路數(shù)占整個樹形邏輯鏈路總數(shù)的百分比。LNA表示覆蓋網(wǎng)絡(luò)中單個節(jié)點1-hop鄰居節(jié)點與其在物理網(wǎng)絡(luò)中1-hop鄰居節(jié)點之間匹配的比例。用節(jié)點加入過程中產(chǎn)生的消息數(shù)目作為拓?fù)渚S護(hù)代價。

對TICM算法仿真時，設(shè)置了2個參數(shù)N_initial和N_detect，分別表示低復(fù)雜度算法啟動閾值和低復(fù)雜度算法中界標(biāo)節(jié)點個數(shù)。在樹結(jié)構(gòu)生成時，首先指定物理網(wǎng)絡(luò)中的一個節(jié)點為根節(jié)點，再隨機(jī)抽取物理網(wǎng)絡(luò)中其他節(jié)點按高精度節(jié)點加入方法添加到樹結(jié)構(gòu)覆蓋網(wǎng)絡(luò)中，直到節(jié)點規(guī)模達(dá)到N_initial；之后再按低復(fù)雜度節(jié)點加入方法加入覆蓋網(wǎng)絡(luò)，直到所有節(jié)點都完成加入，最后統(tǒng)計樹形覆蓋網(wǎng)絡(luò)的GTMR、LNA和時延伸縮比、樹的深度以及節(jié)點維護(hù)開銷。對每個拓?fù)鋱D重復(fù)試驗了5次，選擇不同的根節(jié)點和不同的節(jié)點加入順序，統(tǒng)計仿真結(jié)果。

3.2 實驗結(jié)果分析

1)時延伸縮比(Latency Stretch， LS)。

圖6所示為3種網(wǎng)絡(luò)拓?fù)淠Ｐ拖耇CIM與對比方法的時延伸縮比的比較。LS表示覆蓋網(wǎng)絡(luò)中節(jié)點間路由路徑的平均時延與底層物理路由路徑的平均時延的比值，其理想值為1。時延伸縮比越低，表示覆蓋網(wǎng)絡(luò)結(jié)構(gòu)與底層物理網(wǎng)絡(luò)結(jié)構(gòu)越匹配，路由效率越高。從圖6可看出，在不同的節(jié)點規(guī)模和不同的網(wǎng)絡(luò)模型中，TCIM的LS均小于對比方法。尤其是Top-Down模型中，TCIM的性能不僅優(yōu)于對比方法，也優(yōu)于Waxman模型和BA模型。在Top-Down模型中，處于同一個AS內(nèi)的節(jié)點具有較低的時延，處于不同AS間的節(jié)點具有較大的時延，在時延上的顯著差異有利于節(jié)點位置的區(qū)分，有利于相近節(jié)點的匯聚，因而時延伸縮比減少。

LS可以較好地反映覆蓋網(wǎng)絡(luò)與底層物理網(wǎng)絡(luò)的匹配程度。筆者在文獻(xiàn)[2]中，對高精度節(jié)點加入算法進(jìn)行了研究。本文的仿真結(jié)果表明，高精度節(jié)點加入算法對時延指標(biāo)仍然適用，利用時延作為節(jié)點間距離關(guān)系的度量指標(biāo)所構(gòu)造的樹結(jié)構(gòu)覆蓋網(wǎng)絡(luò)，依然可以較好地與底層物理網(wǎng)絡(luò)匹配。

2)拓?fù)淦ヅ錅?zhǔn)確度。

本文評估了BA模型下不同的N_initial和N_detect對拓?fù)淦ヅ錅?zhǔn)確度的影響，統(tǒng)計不同的N_initial和N_detect參數(shù)下GTMR和LNA值的變化。分別統(tǒng)計了高精度和低復(fù)雜度節(jié)點加入方法混合以及全部使用高精度節(jié)點加入方法時生成樹的GTMR和LNA值，統(tǒng)計結(jié)果如圖7所示。

圖6 3種拓?fù)淠Ｐ拖碌臅r延伸縮比的比較

圖7 BA模型下的高精度和低復(fù)雜度算法拓?fù)淦ヅ錅?zhǔn)確度比較

在圖7(a)中，當(dāng)N_detect=0時，表示只采用高精度節(jié)點加入方法。從圖7(a)可看出，在不同的N_initial條件下，使用低復(fù)雜度方法均使拓?fù)淦ヅ錅?zhǔn)確度下降。當(dāng)N_detect從4增至32時，GTMR和LNA的值幾乎無明顯變化。因而折衷考慮拓?fù)淦ヅ錅?zhǔn)確度和節(jié)點加入代價，推薦N_detect的設(shè)置為4。從圖7(b)可以看出，GTMR和LNA都隨著N_initial的增大而增大，意味著使用高精度節(jié)點加入方法加入的節(jié)點越多，生成的樹結(jié)構(gòu)與底層物理網(wǎng)絡(luò)匹配程度越高。

綜上，可通過折衷考慮拓?fù)渚S護(hù)代價和拓?fù)浣Y(jié)構(gòu)匹配的準(zhǔn)確度需求，合理設(shè)置N_initial值和N_detect值構(gòu)建樹形覆蓋網(wǎng)絡(luò)滿足應(yīng)用需求。

3)生成樹深度。

圖8所示為采用時延作為度量指標(biāo)生成的樹的深度與物理網(wǎng)絡(luò)(圖中用Graph表示)直徑(最大跳數(shù))以及Landmark+Anysee生成的樹結(jié)構(gòu)深度的比較。樹結(jié)構(gòu)的深度對覆蓋網(wǎng)絡(luò)中節(jié)點間的路由時延有影響。從圖8可看出，TCIM生成樹深度與物理網(wǎng)絡(luò)直徑呈正相關(guān)趨勢，尤其是Top-Down模型中，正相關(guān)趨勢表現(xiàn)顯著。這也從側(cè)面反映出TCIM生成樹的拓?fù)淦ヅ涮匦??；谧铋L前綴匹配方法的Anysee，其樹深度受節(jié)點編碼長度的影響，當(dāng)樹深度增加到編碼長度時不再變化。

圖8 3種拓?fù)淠Ｐ拖律蓸渖疃缺容^

4)歸一化拓?fù)渚S護(hù)代價。

圖9所示為不同網(wǎng)絡(luò)規(guī)模和不同的拓?fù)淠Ｐ拖?，TCIM和對比方法的歸一化拓?fù)渚S護(hù)代價。從圖9中可看出，TCIM在Waxman模型和Top-Down模型中節(jié)點加入代價小于Pan方法。

圖9 3種拓?fù)淠Ｐ拖碌臍w一化拓?fù)渚S護(hù)代價比較

在Landmark+Anysee方法中，界標(biāo)節(jié)點個數(shù)為常數(shù)，因而其維護(hù)代價不受節(jié)點規(guī)模的影響。TCIM隨著節(jié)點規(guī)模的增大，樹結(jié)構(gòu)深度增加，導(dǎo)致所需測量的鄰居節(jié)點個數(shù)增加，因而產(chǎn)生的消息數(shù)目增大,導(dǎo)致維護(hù)代價增大。Pan方法基于DHT算法實現(xiàn)，節(jié)點加入時存在多跳且需與鄰居節(jié)點作比較，因而維護(hù)代價也隨節(jié)點規(guī)模增大而增大。

本文進(jìn)一步統(tǒng)計了不同節(jié)點規(guī)模下，使用高精度節(jié)點加入方法時動態(tài)根節(jié)點的切換次數(shù)，即循環(huán)迭代次數(shù)，結(jié)果如圖10所示。從圖10可看出，動態(tài)根節(jié)點的變化次數(shù)隨著節(jié)點規(guī)模的增大而增大；且在BA模型下動態(tài)根節(jié)點的次數(shù)最少，節(jié)點規(guī)模100～6400范圍內(nèi)，迭代次數(shù)平均為2.75～4.25次。

圖10 3種拓?fù)淠Ｐ拖耇CIM的循環(huán)迭代次數(shù)

4 討 論

對于不完全可測網(wǎng)絡(luò)，根據(jù)其信息缺失程度或信息可測量程度也有所區(qū)別。對于一個網(wǎng)絡(luò)，只要存在某2個節(jié)點之間的網(wǎng)絡(luò)狀態(tài)屬性值不可測量或無法獲取，該網(wǎng)絡(luò)即屬于不完全可測的范疇。根據(jù)不完全可測網(wǎng)絡(luò)中狀態(tài)屬性可測量的比例，不完全可測網(wǎng)絡(luò)也可不同。通常獲取全局信息較困難且測量代價過高，因而現(xiàn)有的若干基于網(wǎng)絡(luò)測量的覆蓋網(wǎng)絡(luò)構(gòu)造方法[2,4,6,24]多采用局部測量的方法，盡可能以最小的測量代價完成節(jié)點加入。雖然所得到的網(wǎng)絡(luò)狀態(tài)信息也是不完全的，但局部測量方法更傾向于狀態(tài)信息雖然可測，但不全測。

5 結(jié)束語

本文針對基于測量的覆蓋網(wǎng)絡(luò)構(gòu)建方法中的不完全可測問題，提出了一種用于不完全可測網(wǎng)絡(luò)的樹形覆蓋網(wǎng)絡(luò)構(gòu)造方法TCIM。TCIM由高精度節(jié)點加入算法和低復(fù)雜度節(jié)點加入算法組成。高精度節(jié)點加入方法根據(jù)節(jié)點間時延測量結(jié)果構(gòu)建時延三角形，再根據(jù)三角形的邊長關(guān)系分為3種情況處理，最終把節(jié)點加入到覆蓋網(wǎng)絡(luò)合適的位置。低復(fù)雜度節(jié)點加入方法根據(jù)節(jié)點規(guī)模和網(wǎng)絡(luò)狀態(tài)自適應(yīng)地選擇常數(shù)個節(jié)點進(jìn)行測量。其中高精度節(jié)點加入算法用于小規(guī)?；蜢o態(tài)/低動態(tài)性條件下的節(jié)點加入；低復(fù)雜度節(jié)點加入方法可用于大規(guī)模、高動態(tài)以及網(wǎng)絡(luò)不完全可測條件下節(jié)點的加入。

仿真結(jié)果表明，TCIM生成的樹結(jié)構(gòu)在不同的網(wǎng)絡(luò)拓?fù)淠Ｐ拖戮扇〉幂^小的時延伸縮比(LS)，在Waxman模型和BA模型下有較小的拓?fù)渚S護(hù)代價。本文對比了不同的低復(fù)雜度算法節(jié)點規(guī)模啟動閾值N_initial和低復(fù)雜度算法探測個數(shù)N_detect對生成樹拓?fù)浣Y(jié)構(gòu)的影響，得到結(jié)論是：N_initial越高生成樹的拓?fù)淦ヅ涑潭仍礁?；N_detect的推薦設(shè)置為4，當(dāng)N_detect大于4時，即便增加測量個數(shù)對拓?fù)浣Y(jié)構(gòu)的準(zhǔn)確度影響較小。為滿足不同應(yīng)用對構(gòu)建覆蓋網(wǎng)絡(luò)的不同需求，應(yīng)合理地設(shè)置TCIM中N_initial值和N_detect值構(gòu)建樹形覆蓋網(wǎng)絡(luò)，折衷地考慮拓?fù)渚S護(hù)代價和拓?fù)浣Y(jié)構(gòu)匹配的準(zhǔn)確度需求。