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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)造方法有著廣泛的用途，在P2P[9-11]、無(wú)線自組織網(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ò)解決方案變得熱門(mén)。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ù)浜团渲锚?dú)立于物理網(wǎng)絡(luò)拓?fù)洹?/p>

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

覆蓋網(wǎng)絡(luò)技術(shù)也被用作網(wǎng)絡(luò)疊加層以增加網(wǎng)絡(luò)彈性和恢復(fù)力。文獻(xiàn)[21]提出了一種通過(guò)“路由拐點(diǎn)”集合形成覆蓋網(wǎng)絡(luò)的方法，并利用該覆蓋網(wǎng)絡(luò)選擇2個(gè)數(shù)據(jù)中心之間最適合底層流量QoS需求的路徑。文獻(xiàn)[22]提出了一種彈性覆蓋網(wǎng)絡(luò)(Resilient Overlay Networks， RON)，在該網(wǎng)絡(luò)中通過(guò)主動(dòng)測(cè)量技術(shù)探測(cè)覆蓋網(wǎng)絡(luò)中節(jié)點(diǎn)間的鏈路狀態(tài)，并基于測(cè)量結(jié)果構(gòu)建覆蓋網(wǎng)絡(luò)。在該方法中，在構(gòu)建彈性覆蓋網(wǎng)絡(luò)時(shí)需考慮底層網(wǎng)絡(luò)的結(jié)構(gòu)。主動(dòng)測(cè)量能夠幫助覆蓋網(wǎng)絡(luò)快速地對(duì)故障做出反應(yīng)，以便及時(shí)對(duì)網(wǎng)絡(luò)狀態(tài)進(jìn)行調(diào)整，提高網(wǎng)絡(luò)的彈性。文獻(xiàn)[23]提出了一種基于并行化蟻群算法的網(wǎng)絡(luò)測(cè)量方法，解決網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)的自動(dòng)選取問(wèn)題。該方法對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，使其適用于網(wǎng)絡(luò)測(cè)量中測(cè)量節(jié)點(diǎn)的選取。其次，該文中設(shè)計(jì)并實(shí)現(xiàn)了蟻群算法的并行化框架，所提出的并行化蟻群算法不僅能滿(mǎn)足網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選取的要求，同時(shí)相比于非并行化算法具有更快的收斂速度，更適用于大規(guī)模網(wǎng)絡(luò)測(cè)量。文獻(xiàn)[24]提出了一種與網(wǎng)絡(luò)操作無(wú)關(guān)的關(guān)鍵任務(wù)彈性覆蓋網(wǎng)絡(luò)(Resilient Overlay for Mission Critical Applications, ROMCA)。該方法使用中央目錄服務(wù)器存儲(chǔ)節(jié)點(diǎn)拓?fù)湫畔⒁院?jiǎn)化節(jié)點(diǎn)發(fā)現(xiàn)過(guò)程，使用分布式的路由協(xié)議構(gòu)建不同的覆蓋網(wǎng)絡(luò)之間的路由，并使用基于ICMP的traceroute定期測(cè)量實(shí)現(xiàn)多路徑路由，實(shí)現(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è)計(jì)中，對(duì)每個(gè)主題構(gòu)建子覆蓋網(wǎng)絡(luò)樹(shù)結(jié)構(gòu)。TCO中的節(jié)點(diǎn)是所有對(duì)相同主題感興趣的用戶(hù)節(jié)點(diǎn)。為使構(gòu)建覆蓋拓?fù)溆幸嬗诘讓佑嗛?分布系統(tǒng)網(wǎng)絡(luò)流量的最小化，在構(gòu)建覆蓋網(wǎng)絡(luò)時(shí)捕獲底層網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)間的物理位置，基于一些網(wǎng)絡(luò)級(jí)度量指標(biāo)來(lái)測(cè)量節(jié)點(diǎn)距離并作為T(mén)CO構(gòu)建的權(quán)值。

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

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

2.1 TCIM算法

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

圖1 TCIM算法流程圖

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

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

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

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

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

圖2 時(shí)延三角形示意圖

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置

參數(shù)名稱(chēng)設(shè)置節(jié)點(diǎn)規(guī)模N100,200,400,800,1600,3200,6400節(jié)點(diǎn)最小度m2節(jié)點(diǎn)帶寬范圍(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é)點(diǎn)準(zhǔn)確率(LNA)2個(gè)指標(biāo)，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上描述覆蓋網(wǎng)絡(luò)與物理網(wǎng)絡(luò)的匹配程度。GTMR表示在實(shí)際的物理網(wǎng)絡(luò)中直接相連的2個(gè)點(diǎn)，根據(jù)節(jié)點(diǎn)加入算法加入樹(shù)形拓?fù)浣Y(jié)構(gòu)后2個(gè)節(jié)點(diǎn)仍然保持連接關(guān)系的鏈路數(shù)占整個(gè)樹(shù)形邏輯鏈路總數(shù)的百分比。LNA表示覆蓋網(wǎng)絡(luò)中單個(gè)節(jié)點(diǎn)1-hop鄰居節(jié)點(diǎn)與其在物理網(wǎng)絡(luò)中1-hop鄰居節(jié)點(diǎn)之間匹配的比例。用節(jié)點(diǎn)加入過(guò)程中產(chǎn)生的消息數(shù)目作為拓?fù)渚S護(hù)代價(jià)。

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

3)生成樹(shù)深度。

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

圖8 3種拓?fù)淠Ｐ拖律蓸?shù)深度比較

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

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

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

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

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

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

4 討 論

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

5 結(jié)束語(yǔ)

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

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