2.4 覆蓋網(wǎng)絡(luò)研究現(xiàn)狀

近年來(lái)覆蓋網(wǎng)絡(luò)技術(shù)得到了深入研究和廣泛應(yīng)用。這些研究成果更多地集中于覆蓋網(wǎng)絡(luò)本身，過(guò)度依賴于覆蓋節(jié)點(diǎn)，缺乏對(duì)互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的感知，導(dǎo)致覆蓋網(wǎng)絡(luò)不能發(fā)揮最佳性能。感知互聯(lián)網(wǎng)絡(luò)基礎(chǔ)設(shè)施是指在構(gòu)建針對(duì)具體應(yīng)用的覆蓋網(wǎng)絡(luò)（如路由覆蓋網(wǎng)絡(luò)、多播覆蓋網(wǎng)等）時(shí)，充分考慮底層物理網(wǎng)絡(luò)對(duì)覆蓋網(wǎng)絡(luò)性能的影響因素，盡可能獲得諸如物理網(wǎng)絡(luò)的局部拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)和鏈路狀態(tài)等信息；利用這些信息指導(dǎo)選擇鄰居覆蓋節(jié)點(diǎn)的過(guò)程，選擇更合理的覆蓋路由，滿足具體應(yīng)用的需求，如覆蓋網(wǎng)絡(luò)中端到端的時(shí)延最小。在已有的研究成果中，只有少數(shù)在構(gòu)建覆蓋網(wǎng)絡(luò)時(shí)考慮了互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的感知問(wèn)題，且僅局限于物理拓?fù)湟庾R(shí)（Topology Awareness）[50][51][52][53]，具體地講，是在建立覆蓋網(wǎng)絡(luò)拓?fù)鋾r(shí)考慮覆蓋網(wǎng)絡(luò)拓?fù)渑c物理網(wǎng)絡(luò)的相關(guān)性[54][55][56]。

下面按照網(wǎng)絡(luò)功能，詳細(xì)介紹與本文研究?jī)?nèi)容緊密相關(guān)的幾個(gè)方面的研究動(dòng)態(tài)，包括覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建、覆蓋網(wǎng)絡(luò)路由和覆蓋網(wǎng)絡(luò)多播，具體包括感知與非感知兩種思路。最后闡述了覆蓋網(wǎng)絡(luò)對(duì)互聯(lián)網(wǎng)基礎(chǔ)設(shè)施相關(guān)信息的感知方式。

2.4.1 覆蓋網(wǎng)拓?fù)錁?gòu)建

不同的拓?fù)淠Ｐ蜎Q定了覆蓋網(wǎng)具有的不同的性能，覆蓋網(wǎng)拓?fù)渲苯佑绊懢W(wǎng)絡(luò)的可擴(kuò)展性、可靠性、安全性、故障的恢復(fù)性和傳輸負(fù)載分布情況。構(gòu)建覆蓋網(wǎng)絡(luò)拓?fù)涞年P(guān)鍵是覆蓋節(jié)點(diǎn)的選擇以及這些節(jié)點(diǎn)間的連接方式。通常情況下，針對(duì)不同的應(yīng)用需求，可靈活地構(gòu)建相應(yīng)的覆蓋網(wǎng)絡(luò)拓?fù)洌锤采w網(wǎng)絡(luò)拓?fù)涫敲嫦驊?yīng)用的。根據(jù)具體的應(yīng)用需求，覆蓋網(wǎng)絡(luò)拓?fù)溲芯靠梢苑譃橐韵聨最悺?/p>

1．服務(wù)于路由的覆蓋網(wǎng)拓?fù)?/p>

路由覆蓋網(wǎng)絡(luò)拓?fù)涫欠?wù)于覆蓋路由的拓?fù)洌且愿采w路由為手段，以提升網(wǎng)絡(luò)傳輸性能或提供新型網(wǎng)絡(luò)服務(wù)模式為目的建立起來(lái)的覆蓋網(wǎng)拓?fù)洹ＥcIP路由不同的是，覆蓋路由主要依靠服務(wù)器或主機(jī)節(jié)點(diǎn)在覆蓋網(wǎng)層或應(yīng)用層實(shí)現(xiàn)數(shù)據(jù)的轉(zhuǎn)發(fā)。位于覆蓋網(wǎng)絡(luò)中的服務(wù)器或主機(jī)節(jié)點(diǎn)被稱為覆蓋節(jié)點(diǎn)。路由覆蓋網(wǎng)是用來(lái)彌補(bǔ)原有IP路由協(xié)議的不足，提升互聯(lián)網(wǎng)絡(luò)端到端的傳輸性能和連通性，提高網(wǎng)絡(luò)資源的利用率，特別是增強(qiáng)網(wǎng)絡(luò)的可靠性和彈性（resiliency）。在路由覆蓋網(wǎng)絡(luò)中，覆蓋網(wǎng)絡(luò)拓?fù)浜吐酚蓞f(xié)議的性能直接影響覆蓋網(wǎng)絡(luò)的恢復(fù)能力和彈性。當(dāng)收到一個(gè)需要覆蓋路由的報(bào)文時(shí)，覆蓋節(jié)點(diǎn)首先解析報(bào)文并獲得目的地址信息（不是IP報(bào)文的目的地址），然后根據(jù)預(yù)先設(shè)定的覆蓋路由算法計(jì)算下一跳覆蓋節(jié)點(diǎn)的IP地址，且更新原來(lái)的目標(biāo)IP地址，最后通過(guò)物理層網(wǎng)絡(luò)發(fā)往新的方向。

構(gòu)建覆蓋網(wǎng)絡(luò)拓?fù)鋾r(shí)，物理鏈路的失效恢復(fù)能力是需要考慮的一個(gè)重要因素。當(dāng)物理網(wǎng)絡(luò)出現(xiàn)鏈路故障時(shí)，源節(jié)點(diǎn)尋找最佳覆蓋路徑，避開(kāi)失效鏈路，將受影響的數(shù)據(jù)快速路由到目的節(jié)點(diǎn)。是否可以有效地避開(kāi)失效鏈路，快速實(shí)現(xiàn)數(shù)據(jù)的再傳輸?shù)膬蓚€(gè)重要因素是覆蓋網(wǎng)路由的有效性和路由性能。覆蓋網(wǎng)路由的有效性依賴于覆蓋網(wǎng)絡(luò)拓?fù)洌纾W(wǎng)狀拓?fù)淇梢蕴峁└嗟穆酚蛇x擇，但其可擴(kuò)展性比較差。覆蓋網(wǎng)路由的性能，即路由質(zhì)量，是由路徑的差異度（Path Diversity）決定的。路徑的差異度也是衡量覆蓋網(wǎng)絡(luò)拓?fù)鋵?duì)失效鏈路的恢復(fù)能力的重要指標(biāo)。路徑差異度是指兩條路徑之間共享鏈路的數(shù)目，共享鏈路越少，差異度越大，則由共享鏈路失效引發(fā)的同步故障發(fā)生的幾率越小。在覆蓋網(wǎng)絡(luò)中，共享覆蓋鏈路則必定共享構(gòu)成這條覆蓋鏈路的物理路徑，因此覆蓋網(wǎng)絡(luò)中兩條覆蓋路徑之間的差異度是兩條覆蓋路徑共享的覆蓋鏈路的條數(shù)。當(dāng)覆蓋網(wǎng)傳輸大規(guī)模數(shù)據(jù)時(shí)，會(huì)導(dǎo)致共享的物理路徑的負(fù)載增大，當(dāng)負(fù)載達(dá)到一定程度時(shí)會(huì)出現(xiàn)擁塞。兩條或多條覆蓋網(wǎng)路徑共享的覆蓋鏈路數(shù)越少，表明這個(gè)覆蓋網(wǎng)絡(luò)的拓?fù)湫阅茉胶谩．?dāng)然，邏輯上完全獨(dú)立的兩條覆蓋網(wǎng)路徑，在物理網(wǎng)絡(luò)中可能共享了物理鏈路和物理節(jié)點(diǎn)，如圖2-6所示。共享的物理鏈路或物理節(jié)點(diǎn)出現(xiàn)故障時(shí)，必然導(dǎo)致相應(yīng)的覆蓋路徑故障。綜上所述，研究覆蓋網(wǎng)絡(luò)拓?fù)洌褪窃O(shè)計(jì)一個(gè)具有合理的可用覆蓋路徑且路徑差異度盡量少的拓?fù)洹?/p>

根據(jù)是否具有物理拓?fù)湟庾R(shí)，覆蓋網(wǎng)絡(luò)拓?fù)淇梢苑譃榫哂型負(fù)湟庾R(shí)的覆蓋網(wǎng)絡(luò)和無(wú)拓?fù)湟庾R(shí)的覆蓋網(wǎng)絡(luò)。文獻(xiàn)[19]研究了具有物理拓?fù)湟庾R(shí)的覆蓋網(wǎng)節(jié)點(diǎn)選擇方法。該文獻(xiàn)中，覆蓋網(wǎng)絡(luò)拓?fù)渑c物理拓?fù)溟g的相關(guān)性通過(guò)路徑差異度來(lái)衡量。路徑差異度被定義為連接源節(jié)點(diǎn)與目的節(jié)點(diǎn)的覆蓋網(wǎng)絡(luò)路徑與物理路徑上重疊的節(jié)點(diǎn)數(shù)。根據(jù)路徑差異度的相似程度，作者將全部覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)聚為幾個(gè)不同的簇，并從每個(gè)簇中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為覆蓋網(wǎng)節(jié)點(diǎn)。該算法雖然在選擇覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)充分考慮了節(jié)點(diǎn)間的相關(guān)性，但如何合理確定簇的個(gè)數(shù)，是一個(gè)較為復(fù)雜的問(wèn)題。類似的方法也出現(xiàn)在文獻(xiàn)[57]和[58]中。在文獻(xiàn)[57]中，作者利用物理拓?fù)湟庾R(shí)來(lái)選擇備份覆蓋路徑，使備份路徑與默認(rèn)的物理路徑之間具有最小的相關(guān)性。在文獻(xiàn)[58]中，作者描述了一個(gè)“裝箱機(jī)制”（binning scheme），首先假設(shè)一部分節(jié)點(diǎn)為基準(zhǔn)點(diǎn)（landmark），然后根據(jù)ping命令測(cè)試其他節(jié)點(diǎn)到基準(zhǔn)點(diǎn)的距離（這里指的是時(shí)延），將距離相近的點(diǎn)分配到同一個(gè)箱中。該算法假設(shè)，處于不同箱中的節(jié)點(diǎn)的相關(guān)性較小，通過(guò)這些節(jié)點(diǎn)的路徑的差異度較大。在一定程度上，與隨機(jī)選取覆蓋網(wǎng)節(jié)點(diǎn)相比較，通過(guò)這種裝箱機(jī)制選擇覆蓋網(wǎng)節(jié)點(diǎn)，構(gòu)建的覆蓋網(wǎng)拓?fù)渚哂休^好的性能。文獻(xiàn)[59]綜合節(jié)點(diǎn)相關(guān)性和鏈路相關(guān)性，研究了基于物理拓?fù)湟庾R(shí)的覆蓋網(wǎng)拓?fù)錁?gòu)建機(jī)制。該文獻(xiàn)中，作者為構(gòu)建路由覆蓋網(wǎng)拓?fù)涮岢?個(gè)基于圖論的指標(biāo)：特征路徑長(zhǎng)度（Characteristic Path Length, CPL）、平均割集規(guī)模（Average Cut Size）和節(jié)點(diǎn)度的加權(quán)和（Weighted Node Degree Sum），分別考慮了鏈路相關(guān)性、節(jié)點(diǎn)相關(guān)性、節(jié)點(diǎn)的容量等因素。一些啟發(fā)式算法被用于建立覆蓋網(wǎng)絡(luò)拓?fù)洹＠纾墨I(xiàn)[60]提出兩種啟發(fā)式算法：拓?fù)湟庾R(shí)的K最小共享鏈路生成樹(shù)（Topology-aware K Minimum joint-Spanning Tress, TKMST）和拓?fù)湟庾R(shí)的K隨機(jī)連接網(wǎng)（Topology-aware K Random Connection, KRC）。雖然TKMST和KRC都具有物理拓?fù)涓兄芰Γ珒烧哚槍?duì)每個(gè)節(jié)點(diǎn)設(shè)置了度約束條件。眾所周知，具有度約束的最小生成樹(shù)問(wèn)題是一個(gè)NP難問(wèn)題，其計(jì)算復(fù)雜度是O（|Vu|3），其中|Vu|表示物理網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。文獻(xiàn)[61]也提出具有流量感知能力的啟發(fā)式覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法，但假設(shè)流經(jīng)每個(gè)節(jié)點(diǎn)的流量是一個(gè)定值，不能真實(shí)地反映網(wǎng)絡(luò)的現(xiàn)狀。

RON[23]是第一個(gè)研究路由覆蓋網(wǎng)絡(luò)實(shí)現(xiàn)機(jī)制的算法，屬于非拓?fù)湟庾R(shí)的覆蓋網(wǎng)絡(luò)構(gòu)建算法。RON應(yīng)用全網(wǎng)狀結(jié)構(gòu)（Full Mesh, FM）連接所有的覆蓋網(wǎng)節(jié)點(diǎn)。全網(wǎng)狀結(jié)構(gòu)使得RON可以快速檢測(cè)路由的失效情況，并選擇最佳的替代覆蓋網(wǎng)絡(luò)路徑。當(dāng)物理網(wǎng)絡(luò)的鏈路出現(xiàn)故障時(shí)，源節(jié)點(diǎn)探測(cè)每一個(gè)覆蓋網(wǎng)節(jié)點(diǎn)，選擇一個(gè)時(shí)延最小（或者帶寬最大）的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，形成一跳覆蓋網(wǎng)路由路徑，完成數(shù)據(jù)的傳輸。然而，正是由于全網(wǎng)狀結(jié)構(gòu)，RON用于檢測(cè)和維護(hù)覆蓋網(wǎng)絡(luò)拓?fù)涞拇鷥r(jià)是O（N2），其中，N是系統(tǒng)中覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，這嚴(yán)重影響了RON的可擴(kuò)展性。實(shí)驗(yàn)表明當(dāng)覆蓋網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)大于50時(shí)，RON的性能急劇下降。針對(duì)RON的可擴(kuò)展性問(wèn)題，文獻(xiàn)[62]提出了改進(jìn)的算法，即在節(jié)點(diǎn)度約束的條件下，節(jié)點(diǎn)間進(jìn)行隨機(jī)連接建立覆蓋網(wǎng)絡(luò)拓?fù)洌@些改進(jìn)算法所選擇的路由路徑往往并非最佳路徑。

根據(jù)連接方式的不同，覆蓋網(wǎng)絡(luò)拓?fù)浞譃榫W(wǎng)狀結(jié)構(gòu)、樹(shù)狀結(jié)構(gòu)，以及混合結(jié)構(gòu)3種類型。RON是典型的網(wǎng)狀結(jié)構(gòu)，由于全網(wǎng)狀連接，可擴(kuò)展性是RON的最大問(wèn)題。文獻(xiàn)[63]提出了K最小生成樹(shù)（K Minimum Spanning Tree, KMST）結(jié)構(gòu)覆蓋網(wǎng)絡(luò)拓?fù)洌_保任何兩個(gè)覆蓋節(jié)點(diǎn)之間存在K條覆蓋路徑。KMST僅保證了覆蓋層路徑之間的差異度，而未考慮物理層路徑的差異度，即不具有互聯(lián)網(wǎng)基礎(chǔ)設(shè)施感知能力。文獻(xiàn)[60]提出一種混合結(jié)構(gòu)覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法（Mesh-Tree, MT）。MT在構(gòu)造最小生成樹(shù)的基礎(chǔ)上，在物理拓?fù)渲芯哂凶鎸O關(guān)系、叔侄關(guān)系的節(jié)點(diǎn)間增加覆蓋鏈路。混合結(jié)構(gòu)增強(qiáng)了覆蓋網(wǎng)絡(luò)的魯棒性和可靠性。在可擴(kuò)展性方面，KMST和MT優(yōu)于RON的全網(wǎng)狀結(jié)構(gòu)。由于這些算法專注于覆蓋節(jié)點(diǎn)間的連接關(guān)系，忽略了節(jié)點(diǎn)的選擇對(duì)于覆蓋網(wǎng)絡(luò)拓?fù)涞闹匾浴?/p>

網(wǎng)狀、樹(shù)狀和混合結(jié)構(gòu)的覆蓋網(wǎng)絡(luò)拓?fù)涞囊粋€(gè)共同的特性是：三者均提供選擇覆蓋網(wǎng)路由的平臺(tái)，即當(dāng)系統(tǒng)需要覆蓋路由時(shí)，基于某個(gè)平臺(tái)，從已有的覆蓋節(jié)點(diǎn)和覆蓋鏈路中選擇一條性能最佳的覆蓋路由。因此，網(wǎng)狀、樹(shù)狀和混合結(jié)構(gòu)覆蓋網(wǎng)絡(luò)拓?fù)鋵儆谙鄬?duì)固定的、預(yù)設(shè)的拓?fù)洌峁┑穆酚蓪儆趥浞萋酚伞＿@些拓?fù)湫枰ㄆ诘靥綔y(cè)和維護(hù)節(jié)點(diǎn)的可用性和鏈路的可達(dá)性。一跳覆蓋網(wǎng)源路由（Single One-hop Source Routing, SOSR）[24]不需要維護(hù)拓?fù)洌瑑H在需要路由時(shí)探測(cè)少數(shù)節(jié)點(diǎn)，選擇最佳的路徑。所謂的“一跳源路由”是指路由路徑中只需一個(gè)中繼節(jié)點(diǎn)的源路由機(jī)制。研究表明許多高效的覆蓋路由僅通過(guò)一個(gè)中間覆蓋節(jié)點(diǎn)便可以完成，不需要多跳覆蓋路由[24]。SOSR的路由機(jī)制非常簡(jiǎn)單：當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)時(shí)，它從覆蓋節(jié)點(diǎn)中隨機(jī)選擇K個(gè)節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，形成K條一跳覆蓋路徑；通過(guò)在每條覆蓋路徑上發(fā)送探測(cè)包，選擇一條時(shí)延最小的路徑作為最終的路由路徑，如圖2-7所示。實(shí)驗(yàn)結(jié)果表明K=4時(shí)便可以得到很好的路由效果[24]。

2．服務(wù)于QoS的覆蓋網(wǎng)拓?fù)?/p>

提供QoS的覆蓋網(wǎng)絡(luò)又稱為服務(wù)覆蓋網(wǎng)絡(luò)（SON），這一名稱源自文獻(xiàn)[39]。通常情況下，服務(wù)覆蓋網(wǎng)絡(luò)位于傳輸層和應(yīng)用層之間，由服務(wù)提供商（第三方）負(fù)責(zé)組建、維護(hù)以及向上層用戶提供增質(zhì)服務(wù)，確保用戶的QoS需求。服務(wù)提供商（OSP）與基礎(chǔ)設(shè)施提供商（ISP）簽訂服務(wù)等級(jí)協(xié)議（SLA），并購(gòu)買相應(yīng)節(jié)點(diǎn)間的帶寬，為上層應(yīng)用提供QoS保障。除了QoS外，服務(wù)覆蓋網(wǎng)絡(luò)還可以提供彈性路由、內(nèi)容分發(fā)以及安全方面的保障。通常情況下，服務(wù)覆蓋網(wǎng)絡(luò)由相對(duì)固定的服務(wù)器節(jié)點(diǎn)組成。為了滿足帶寬、時(shí)延、吞吐量和丟包率等QoS需求，節(jié)點(diǎn)之間建立邏輯鏈路且通過(guò)隧道機(jī)制實(shí)現(xiàn)數(shù)據(jù)的傳輸。

如圖2-8所示，服務(wù)覆蓋網(wǎng)絡(luò)由覆蓋節(jié)點(diǎn)（Overlay Nodes, ONs）和端系統(tǒng)節(jié)點(diǎn)（End Systems, ESs）組成。ONs位于一個(gè)或多個(gè)AS中，且由OSP組織和管理。為了改善服務(wù)覆蓋網(wǎng)絡(luò)的可擴(kuò)展性和容錯(cuò)性，在一個(gè)AS內(nèi)部部署多個(gè)ONs。ONs之間的覆蓋鏈路被稱為傳輸鏈路（Transport Links）, ESs與ONs之間的鏈路被稱為接入鏈路（Access Links）。構(gòu)建一個(gè)性能較好的服務(wù)覆蓋網(wǎng)絡(luò)，需要考慮ONs的數(shù)量與位置以及節(jié)點(diǎn)間接入鏈路和傳輸鏈路的問(wèn)題。

構(gòu)建服務(wù)覆蓋網(wǎng)絡(luò)是一種利益相關(guān)的投資行為。對(duì)于服務(wù)提供商而言，其目標(biāo)是在滿足用戶需求的前提下，達(dá)到收益最大化。如圖2-9所示，服務(wù)覆蓋網(wǎng)絡(luò)依賴于OSP、ISPs和終端用戶三者間的利益關(guān)系：從滿足QoS需求的角度看，SON保障端到端的QoS，同時(shí)確保覆蓋鏈路的帶寬；從收益的角度看，OSP需要從服務(wù)用戶得到收益且支付購(gòu)買帶寬的費(fèi)用。由于需要權(quán)衡經(jīng)濟(jì)代價(jià)與QoS性能之間的關(guān)系，構(gòu)建SON是一個(gè)復(fù)雜且具有挑戰(zhàn)性的任務(wù)。因此，通常將服務(wù)覆蓋網(wǎng)絡(luò)拓?fù)涞臉?gòu)建問(wèn)題抽象為一個(gè)數(shù)學(xué)模型，得到滿足帶寬（或時(shí)延）需求的最小代價(jià)解。

文獻(xiàn)[39]首先提出了服務(wù)覆蓋網(wǎng)絡(luò)的概念，該文獻(xiàn)中，作者通過(guò)分析影響服務(wù)覆蓋網(wǎng)絡(luò)拓?fù)涞母鞣N因素，如SLA、QoS、流量分布和帶寬等，提出服務(wù)覆蓋網(wǎng)絡(luò)結(jié)構(gòu)及概念，但沒(méi)有涉及具體的拓?fù)湓O(shè)計(jì)問(wèn)題。針對(duì)影響覆蓋網(wǎng)絡(luò)拓?fù)涞囊蛩兀延械难芯繌母鱾€(gè)角度對(duì)SON進(jìn)行了深入研究。文獻(xiàn)[64]研究了在同時(shí)滿足帶寬和時(shí)延QoS需求的情況下，服務(wù)覆蓋網(wǎng)絡(luò)的拓?fù)錁?gòu)建問(wèn)題。類似的研究還有文獻(xiàn)[65]，作者將服務(wù)覆蓋網(wǎng)絡(luò)拓?fù)浣ㄔ靻?wèn)題抽象成為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，使得網(wǎng)絡(luò)的傳輸代價(jià)和鏈路的時(shí)延最小，并設(shè)計(jì)一個(gè)啟發(fā)式算法進(jìn)行求解。文獻(xiàn)[66]研究了在確保帶寬的前提下，服務(wù)節(jié)點(diǎn)ON的數(shù)量和合理放置問(wèn)題，達(dá)到最小化服務(wù)提供商的運(yùn)營(yíng)成本的目的。在此基礎(chǔ)上，文獻(xiàn)[67]進(jìn)一步研究了服務(wù)節(jié)點(diǎn)ON的部署問(wèn)題，以及確保QoS需求時(shí)最小的帶寬開(kāi)銷，設(shè)計(jì)了混合線性規(guī)劃算法。文獻(xiàn)[40]在構(gòu)建覆蓋網(wǎng)拓?fù)鋾r(shí)不僅考慮ONs間的傳輸鏈路，而且考慮了建立終端節(jié)點(diǎn)ESs與ONs節(jié)點(diǎn)間的接入鏈路的代價(jià)。

為了提高服務(wù)覆蓋網(wǎng)絡(luò)的可擴(kuò)展性，文獻(xiàn)[68]和[69]分別研究了不同AS間ONs的連接問(wèn)題，旨在建立大規(guī)模服務(wù)覆蓋網(wǎng)絡(luò)，滿足終端用戶的QoS需求。作者從數(shù)學(xué)角度證明了該問(wèn)題是一個(gè)NP難問(wèn)題，并提出了多個(gè)啟發(fā)式算法進(jìn)行求解。針對(duì)同樣的問(wèn)題，QRON[25]以滿足端到端時(shí)延和拓?fù)涞目蓴U(kuò)展為研究目標(biāo)，提出了層次化拓?fù)錁?gòu)建算法，引入了Overlay Brokers（OBs）的概念。OBs的作用等同于ONs，每個(gè)自治系統(tǒng)（AS）至少包括一個(gè)OBs。在同一AS內(nèi)部，ONs間連接形成全網(wǎng)狀結(jié)構(gòu)，而AS間通過(guò)至少一條隧道連接。QRON提出了兩種鏈路代價(jià)算法，分別為改進(jìn)的最短路徑（Modified Shortest-Distance Path, MSDP）算法和成比例的帶寬最小路徑（Proportional Bandwidth Shortest Path, PBSP）算法，旨在通過(guò)平衡OBs之間的數(shù)據(jù)流量和覆蓋鏈路來(lái)尋求一條較優(yōu)的覆蓋路徑。

文獻(xiàn)[70]研究了覆蓋網(wǎng)拓?fù)錁?gòu)建的動(dòng)態(tài)經(jīng)濟(jì)模型。在該模型中，為了使服務(wù)提供商O(píng)SP的收益最大化，根據(jù)承載的業(yè)務(wù)流量的需求變化動(dòng)態(tài)調(diào)整所租用的鏈路帶寬。按照文獻(xiàn)[70]的研究思路，文獻(xiàn)[71]研究了動(dòng)態(tài)流量的測(cè)量與評(píng)估方法，為構(gòu)建服務(wù)覆蓋網(wǎng)絡(luò)拓?fù)涮峁├碚撘罁?jù)。為了適應(yīng)動(dòng)態(tài)流量的需求，文獻(xiàn)[41]研究了服務(wù)覆蓋網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)再配置策略，以最小化傳輸數(shù)據(jù)的代價(jià)和再配置覆蓋網(wǎng)絡(luò)的代價(jià)為目標(biāo)，設(shè)計(jì)了最優(yōu)化算法。文獻(xiàn)[72]提出了多平面架構(gòu)的下一代服務(wù)覆蓋網(wǎng)絡(luò)模型NGSON，目的是解決不同業(yè)務(wù)功能的覆蓋網(wǎng)絡(luò)如何相互合作，共享資源的問(wèn)題，為構(gòu)建在同一基礎(chǔ)設(shè)施上的多個(gè)覆蓋網(wǎng)絡(luò)的建設(shè)提供了思路。

2.4.2 覆蓋網(wǎng)路由

路由問(wèn)題是覆蓋網(wǎng)絡(luò)研究的關(guān)鍵問(wèn)題之一。圖2-10表示了覆蓋網(wǎng)路由的基本原理。圖中A、B、C是覆蓋網(wǎng)節(jié)點(diǎn)，當(dāng)IP路徑AB發(fā)生故障或者擁塞時(shí)，選擇節(jié)點(diǎn)C為中繼節(jié)點(diǎn)，經(jīng)過(guò)路徑AC和CB，與B進(jìn)行通信，從而繞過(guò)原來(lái)的故障路徑。當(dāng)然，覆蓋路徑的中繼節(jié)點(diǎn)可以不止一個(gè)，即為多跳覆蓋網(wǎng)路由。覆蓋網(wǎng)路由的理論依據(jù)是互聯(lián)網(wǎng)中數(shù)據(jù)傳輸存在三角不等關(guān)系（Triangle Inequality Violations, TIV）[73][74][75]，即RTT（A, B）＞RTT（A, C）+RTT（C, B），其中RTT（X, Y）是指節(jié)點(diǎn)X和Y之間的往返時(shí)延。覆蓋網(wǎng)路由具有很大的靈活性，不僅可以改善IP網(wǎng)絡(luò)的性能，提供端到端的QoS保障，而且可以提供各種新型應(yīng)用。覆蓋網(wǎng)絡(luò)可以改善互聯(lián)網(wǎng)的路由性能，即提供彈性路由，其目的是實(shí)現(xiàn)路徑故障的快速檢測(cè)和恢復(fù)，或通過(guò)覆蓋節(jié)點(diǎn)繞過(guò)擁塞路徑，提高互聯(lián)網(wǎng)端到端的時(shí)延。覆蓋路由的性能依賴于覆蓋路徑的選擇，路由覆蓋網(wǎng)的可擴(kuò)展性，以及探測(cè)、計(jì)算和維護(hù)覆蓋鏈路的代價(jià)等。

文獻(xiàn)[23]最早提出了彈性覆蓋網(wǎng)絡(luò)RON（Resilient Overlay Network）的概念，研究了覆蓋網(wǎng)路由的可行性和路由機(jī)制。RON采用全連接覆蓋網(wǎng)拓?fù)洌芷谛缘販y(cè)量覆蓋節(jié)點(diǎn)之間虛擬鏈路的性能（如時(shí)延），及時(shí)發(fā)現(xiàn)故障，以探測(cè)得到的節(jié)點(diǎn)間的性能參數(shù)作為選擇最佳覆蓋路由的依據(jù)。繼RON之后，已有關(guān)于覆蓋路由的研究主要集中在提高覆蓋路由性能、可擴(kuò)展性，以及減少負(fù)載等幾個(gè)方面。

1．覆蓋路由的性能

覆蓋路由可以彌補(bǔ)IP路由的不足，改善端到端的傳輸性能，即通過(guò)覆蓋網(wǎng)絡(luò)為默認(rèn)的IP路徑提供備份路徑。當(dāng)IP路徑出現(xiàn)鏈路斷裂或擁塞等故障時(shí)，應(yīng)用覆蓋網(wǎng)絡(luò)所提供的備份路徑繞過(guò)故障點(diǎn)傳輸數(shù)據(jù)。因此，覆蓋路由的好壞取決于備份路徑的選擇。備份路徑的選擇需考慮兩個(gè)方面的因素：拓?fù)湟庾R(shí)和時(shí)延或帶寬[76]。對(duì)于一跳覆蓋路由，選擇備份路徑就是選擇構(gòu)成一跳覆蓋路徑的中繼節(jié)點(diǎn)。

文獻(xiàn)[19]分別研究了一跳和多跳覆蓋網(wǎng)路由路徑的選擇問(wèn)題。作者提出基于測(cè)量的啟發(fā)式算法優(yōu)選覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)，使得覆蓋路徑與物理路徑的差異度達(dá)到最小。算法的基本思想是：借鑒概率統(tǒng)計(jì)中求兩變量的相關(guān)系數(shù)的方法求經(jīng)過(guò)某節(jié)點(diǎn)的兩條路徑的相關(guān)性，并將相關(guān)性近似的節(jié)點(diǎn)聚為一類。在選擇覆蓋網(wǎng)絡(luò)路徑時(shí)，從不同聚類中選擇覆蓋節(jié)點(diǎn)，得到的路徑之間的差異度較大。針對(duì)類似的問(wèn)題，文獻(xiàn)[77]研究了覆蓋節(jié)點(diǎn)放置問(wèn)題，旨在改進(jìn)IP路由的可靠性，以及減少端到端的往返時(shí)延。作者應(yīng)用啟發(fā)式算法漸增式地增加覆蓋節(jié)點(diǎn)，使得路徑間的鏈路重疊率最小。不同于文獻(xiàn)[19]，在文獻(xiàn)[77]中，作者不僅考慮覆蓋路徑與物理路徑間的鏈路重疊率，也考慮不同的覆蓋路徑間的鏈路重疊率。文獻(xiàn)[78]應(yīng)用條件概率的思想研究覆蓋網(wǎng)絡(luò)中繼節(jié)點(diǎn)的選擇問(wèn)題，即選擇備份路徑時(shí)，優(yōu)先選擇失效概率較小的節(jié)點(diǎn)作為覆蓋路徑的中繼節(jié)點(diǎn)。該算法假設(shè)系統(tǒng)中所有鏈路的失效概率是已知條件，顯然這是不符合實(shí)際的。

其他一些研究則側(cè)重于覆蓋路由的時(shí)延問(wèn)題，即選擇傳輸時(shí)延最小的路徑作為覆蓋路徑。文獻(xiàn)[7]通過(guò)實(shí)測(cè)數(shù)據(jù)分析物理網(wǎng)絡(luò)中頻繁出現(xiàn)在端到端最短路徑中的節(jié)點(diǎn)，試圖找出包含這些節(jié)點(diǎn)且滿足覆蓋路由需求的最小集合。該文獻(xiàn)中，作者提出一個(gè)近似算法（Approximation Algorithm）——MIN-ORRA，且應(yīng)用Local-Ration理論[79]求解。不同于文獻(xiàn)[7]，文獻(xiàn)[17]定義頻繁出現(xiàn)在端到端最短路徑中的節(jié)點(diǎn)為超節(jié)點(diǎn)，應(yīng)用實(shí)測(cè)的方法得到這些超節(jié)點(diǎn)，且周期性更新，因此代價(jià)較大。

除了時(shí)延外，鏈路帶寬也是選擇覆蓋路徑的標(biāo)準(zhǔn)之一。文獻(xiàn)[25]和[80]使用了可用帶寬作為評(píng)價(jià)指標(biāo)來(lái)選擇覆蓋路徑，使其滿足QoS需求。然而，可用帶寬很難被精確測(cè)量，常常應(yīng)用估計(jì)的方法得到其近似值。

2．可擴(kuò)展性

路由覆蓋網(wǎng)絡(luò)的可擴(kuò)展性是由網(wǎng)絡(luò)的維護(hù)代價(jià)（Overhead）決定的，維護(hù)代價(jià)越高，其可擴(kuò)展性越低。覆蓋網(wǎng)絡(luò)的維護(hù)代價(jià)由鏈路探測(cè)代價(jià)、狀態(tài)發(fā)布代價(jià)和路由計(jì)算代價(jià)三部分構(gòu)成。通常情況下，構(gòu)建路由覆蓋網(wǎng)絡(luò)拓?fù)鋾r(shí)忽略路由計(jì)算代價(jià)。

（1）鏈路探測(cè)代價(jià)：通過(guò)ping或traceroute方式，覆蓋網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)周期性地向相鄰節(jié)點(diǎn)發(fā)送探測(cè)包，獲得鏈路的狀態(tài)參數(shù)（如可達(dá)性、時(shí)延或帶寬），建立自己的鏈路狀態(tài)表（Link State Table, LST）。

（2）狀態(tài)發(fā)布代價(jià)：每個(gè)覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)周期性地廣播自己的鏈路狀態(tài)表，且收到其他節(jié)點(diǎn)的鏈路狀態(tài)表，完善自己的狀態(tài)表并作為路由計(jì)算的依據(jù)。

（3）路由計(jì)算代價(jià)：根據(jù)用戶的需求和鏈路所承載的當(dāng)前流量，計(jì)算最佳路由。

解決覆蓋網(wǎng)絡(luò)的可擴(kuò)展性問(wèn)題，首先要從拓?fù)浣Y(jié)構(gòu)入手。根據(jù)拓?fù)鋵哟谓Y(jié)構(gòu)的不同，覆蓋網(wǎng)絡(luò)拓?fù)浞譃楸馄绞健哟问胶鸵惶采w網(wǎng)絡(luò)。對(duì)于扁平結(jié)構(gòu)覆蓋網(wǎng)絡(luò)，最具有代表性的是RON全網(wǎng)狀結(jié)構(gòu)。在RON中，由于每個(gè)節(jié)點(diǎn)都知道其他n-1個(gè)節(jié)點(diǎn)的連接狀態(tài)，所以RON可以找到最佳的覆蓋路由。然而，RON的監(jiān)測(cè)與維護(hù)代價(jià)嚴(yán)重影響它的性能優(yōu)勢(shì)。因此，一些改進(jìn)算法著重研究如何減少RON的監(jiān)測(cè)和維護(hù)代價(jià)。已有的解決方法可以歸納為3種類型：構(gòu)建半網(wǎng)狀或樹(shù)狀覆蓋拓?fù)洹⒃龃蟊O(jiān)測(cè)的周期，以及減少監(jiān)測(cè)的節(jié)點(diǎn)數(shù)。文獻(xiàn)[62]和[63]分別研究了半網(wǎng)狀和樹(shù)狀覆蓋拓?fù)洌鼈兊脑硗ㄟ^(guò)減少覆蓋節(jié)點(diǎn)的連接度來(lái)降低覆蓋網(wǎng)的監(jiān)測(cè)和維護(hù)代價(jià)。然而，研究表明，在半網(wǎng)狀和樹(shù)狀拓?fù)浣Y(jié)構(gòu)中，30%具有低時(shí)延和低丟包率的路徑?jīng)]有被包括在覆蓋路徑中[81]。文獻(xiàn)[81]也研究了增大監(jiān)測(cè)周期對(duì)覆蓋網(wǎng)絡(luò)性能的影響，表明監(jiān)測(cè)周期每增大一倍，監(jiān)測(cè)流量減少一半，但會(huì)得到10%～30%的無(wú)效或陳舊的路由信息。鑒于前兩者的不足，大量的研究集中于通過(guò)減少監(jiān)測(cè)的節(jié)點(diǎn)數(shù)提高覆蓋網(wǎng)絡(luò)的可擴(kuò)展性。文獻(xiàn)[82]～文獻(xiàn)[84]應(yīng)用Grid Quorum[85]機(jī)制將覆蓋網(wǎng)監(jiān)測(cè)和維護(hù)代價(jià)從O（n2）降低至O（n1.5）。在文獻(xiàn)[86]中，作者應(yīng)用Grid Quorum系統(tǒng)[85]，選擇多個(gè)匯聚節(jié)點(diǎn)分布式匯總節(jié)點(diǎn)間的鏈路狀態(tài)信息，將監(jiān)測(cè)和維護(hù)覆蓋網(wǎng)絡(luò)的代價(jià)從O（n1.5）降低到O，雖然性能得到了一定的提高，但帶來(lái)多個(gè)匯聚節(jié)點(diǎn)間信息同步的問(wèn)題。文獻(xiàn)[87]提出了一個(gè)基于斷層掃描（Tomography-based）的覆蓋網(wǎng)絡(luò)監(jiān)測(cè)系統(tǒng)TOM，有選擇地監(jiān)測(cè)K條覆蓋路徑。通過(guò)對(duì)這K條路徑的監(jiān)測(cè)結(jié)果推測(cè)出其他路徑的狀態(tài)，從而將監(jiān)測(cè)代價(jià)降低到O（nlogn）。

層次式覆蓋網(wǎng)絡(luò)拓?fù)渫ㄟ^(guò)分層監(jiān)測(cè)鏈路狀態(tài)、集中匯總的方式提高其可擴(kuò)展性。層次式的思想類似于OSPF協(xié)議，每個(gè)節(jié)點(diǎn)僅監(jiān)測(cè)和維護(hù)所屬區(qū)域的鏈路狀態(tài)信息，大大降低了維護(hù)的代價(jià)。最具有代表性的層次式路由覆蓋網(wǎng)絡(luò)是QRON。在QRON中，根據(jù)節(jié)點(diǎn)間鏈路的時(shí)延，將相似的節(jié)點(diǎn)組織成一個(gè)類，類內(nèi)形成全網(wǎng)狀連接。對(duì)于多個(gè)類，依據(jù)類間的相似性再進(jìn)行聚類，這樣形成一個(gè)多層結(jié)構(gòu)的拓?fù)洌鐖D2-11所示。鏈路狀態(tài)信息僅在類內(nèi)被廣播，類間的信息傳遞通過(guò)網(wǎng)關(guān)節(jié)點(diǎn)完成。實(shí)驗(yàn)結(jié)果表明，層次式結(jié)構(gòu)改進(jìn)了網(wǎng)絡(luò)的可擴(kuò)展性，降低了監(jiān)測(cè)和維護(hù)的代價(jià)。

第3種改善路由覆蓋網(wǎng)絡(luò)可擴(kuò)展性的方法是一跳覆蓋路由，即僅通過(guò)一個(gè)中繼覆蓋節(jié)點(diǎn)完成數(shù)據(jù)的傳輸。此方法關(guān)鍵在中繼節(jié)點(diǎn)的選取。例如，文獻(xiàn)[87]應(yīng)用Grid Quorum[85]機(jī)制優(yōu)選中繼節(jié)點(diǎn)，降低因鏈路狀態(tài)廣播帶來(lái)的代價(jià)。文獻(xiàn)[19]和[24]對(duì)此也有深入研究，具體內(nèi)容在“覆蓋網(wǎng)絡(luò)的性能”中有詳細(xì)討論，在此不再贅述。

2.4.3 覆蓋網(wǎng)多播

多播（Multicast）又稱為組播，是一種一對(duì)多或多對(duì)多的數(shù)據(jù)傳輸模式，它通過(guò)數(shù)據(jù)包復(fù)制將信息同時(shí)發(fā)送給多個(gè)接收者，具有效率高、可擴(kuò)展性好的特點(diǎn)。利用多播進(jìn)行數(shù)據(jù)傳輸可以降低網(wǎng)絡(luò)的負(fù)載，節(jié)省大量的網(wǎng)絡(luò)資源，提供有效的網(wǎng)絡(luò)通信服務(wù)。然而，由于互聯(lián)網(wǎng)僵化的體系結(jié)構(gòu)，IP多播技術(shù)雖然非常成熟，但其可擴(kuò)展性差，難以大規(guī)模部署[21]。首先，在IP多播中，每個(gè)路由器需要為所有多播組保存狀態(tài)，這違反了IP層“無(wú)狀態(tài)”結(jié)構(gòu)原則的設(shè)計(jì)初衷，增加了IP協(xié)議的復(fù)雜性；其次，由于IP協(xié)議提供“盡力而為”的服務(wù)，在IP多播環(huán)境下提供可靠性、擁塞控制、流量控制和安全等服務(wù)比在單播環(huán)境下要復(fù)雜得多；最后，由于在IP網(wǎng)絡(luò)中各ISP之間的商業(yè)利益關(guān)系，在域間部署IP多播受到了極大的阻礙[88][89][90]。因此，今天IP多播僅應(yīng)用在域內(nèi)環(huán)境中，無(wú)法滿足大量新型應(yīng)用的需求[91]，如多媒體會(huì)議、視頻點(diǎn)播、遠(yuǎn)程教育、在線游戲、網(wǎng)絡(luò)廣播、大規(guī)模數(shù)據(jù)分發(fā)等。

覆蓋網(wǎng)多播又稱為應(yīng)用層多播（Application Layer Multicast, ALM），可以彌補(bǔ)IP多播的不足，作為IP多播的一種有效的替代方式受到了廣泛的關(guān)注[21][35]。覆蓋網(wǎng)多播工作在應(yīng)用層，參與節(jié)點(diǎn)是終端用戶或服務(wù)器，統(tǒng)稱為終端節(jié)點(diǎn)。為了實(shí)現(xiàn)數(shù)據(jù)的分發(fā)，終端節(jié)點(diǎn)被組織成覆蓋網(wǎng)拓?fù)洌ǔ闃?shù)狀或網(wǎng)狀結(jié)構(gòu)。在多播拓?fù)渲校織l覆蓋鏈路對(duì)應(yīng)IP網(wǎng)絡(luò)的一條單播路徑，在該單播路徑中通過(guò)單播隧道機(jī)制實(shí)現(xiàn)跳到跳的數(shù)據(jù)傳輸。與IP多播不同，覆蓋網(wǎng)多播中由終端節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的復(fù)制和轉(zhuǎn)發(fā)。單播、IP多播和覆蓋網(wǎng)多播三者之間的關(guān)系如圖2-12所示，其中R1和R2是路由器，A、B、C和D是終端節(jié)點(diǎn)，圖中鏈路上的數(shù)字表示鏈路代價(jià)，比如傳輸時(shí)延。A是源主機(jī)，把數(shù)據(jù)發(fā)送給所有其他主機(jī)。圖2-12（b）表示通過(guò)單播方式進(jìn)行數(shù)據(jù)的傳輸，這種方式存在較多的冗余數(shù)據(jù)。圖2-12（c）是IP多播的情況，使用具有多播功能的路由器R1和R2實(shí)現(xiàn)了數(shù)據(jù)的復(fù)制和轉(zhuǎn)發(fā)，避免了數(shù)據(jù)的冗余傳輸。圖2-12（d）表示了覆蓋網(wǎng)多播，根據(jù)鏈路的代價(jià)，以A為源點(diǎn)構(gòu)建了覆蓋網(wǎng)多播樹(shù)，其中的數(shù)據(jù)復(fù)制與轉(zhuǎn)發(fā)完全由終端節(jié)點(diǎn)完成，不需要對(duì)原有路由器進(jìn)行改造。從圖2-12可以看出，相對(duì)于單播方式，覆蓋網(wǎng)多播減少了冗余數(shù)據(jù)的傳輸；同時(shí)，覆蓋網(wǎng)多播的效率雖然低于IP多播，但其無(wú)須改造物理網(wǎng)絡(luò)，結(jié)構(gòu)靈活，方便部署。

根據(jù)構(gòu)造方式的不同，覆蓋網(wǎng)多播可以分為網(wǎng)狀優(yōu)先（Mesh-first）、樹(shù)狀優(yōu)先（Tree-first）和層次狀（Hierarchical Topology）三類。按協(xié)議和算法的控制方式，還可以分為集中式和分布式兩種。集中式方法由一個(gè)匯聚節(jié)點(diǎn)（Rendezvous Point, RP）負(fù)責(zé)覆蓋網(wǎng)多播狀態(tài)信息收集和路由計(jì)算；而在分布式方法中，狀態(tài)信息探測(cè)與更新和路由計(jì)算由各端系統(tǒng)節(jié)點(diǎn)負(fù)責(zé)。

1．網(wǎng)狀優(yōu)先覆蓋網(wǎng)多播

網(wǎng)狀優(yōu)先方式是將終端節(jié)點(diǎn)連接形成一個(gè)網(wǎng)狀的拓?fù)浣Y(jié)構(gòu)（Mesh），即控制拓?fù)洌蝗缓蟾鶕?jù)具體的多播業(yè)務(wù)需求構(gòu)建基于Mesh的多播樹(shù)，即數(shù)據(jù)傳輸拓?fù)洹？刂仆負(fù)湄?fù)責(zé)在所有組成員之間建立拓?fù)鋱D，周期性地在節(jié)點(diǎn)之間交換狀態(tài)信息，維護(hù)和更新控制拓?fù)錉顟B(tài)，增強(qiáng)整個(gè)系統(tǒng)的健壯性和可靠性。由于需要周期性地優(yōu)化控制拓?fù)洌又亓讼到y(tǒng)的負(fù)載，所以可擴(kuò)展性差是網(wǎng)狀優(yōu)先多播拓?fù)涞娜毕荨?shù)據(jù)拓?fù)鋭t是基于控制拓?fù)涞纳蓸?shù)，通常情況下，以每個(gè)數(shù)據(jù)源為根構(gòu)造一棵基于控制拓?fù)涞纳蓸?shù)。由于數(shù)據(jù)拓?fù)涫侵苯訌目刂仆負(fù)涞玫降模虼耍刂仆負(fù)洌淳W(wǎng)狀拓?fù)洌┑臉?gòu)造直接影響數(shù)據(jù)傳輸?shù)馁|(zhì)量。

Narada協(xié)議[21]是最早提出的基于網(wǎng)狀優(yōu)先的覆蓋網(wǎng)多播路由協(xié)議之一，是一種集中式路由控制協(xié)議。在該協(xié)議中，所有組成員節(jié)點(diǎn)將構(gòu)成一個(gè)虛擬Mesh控制拓?fù)洹arada通過(guò)匯聚節(jié)點(diǎn)收集成員之間的信息構(gòu)建Mesh結(jié)構(gòu)。在控制Mesh拓?fù)渖希琋arada運(yùn)行類似于DVMRP的距離向量協(xié)議使每個(gè)成員得到整個(gè)網(wǎng)絡(luò)的路由信息，以每個(gè)數(shù)據(jù)源為根，綜合時(shí)延和帶寬兩個(gè)參數(shù)構(gòu)造一棵生成樹(shù)。由于每個(gè)成員需周期性地同其他成員交換狀態(tài)信息，產(chǎn)生了大量的維護(hù)開(kāi)銷，導(dǎo)致可擴(kuò)展性差，因此只適用于小規(guī)模組播應(yīng)用。

Scattercast[92]也是一種網(wǎng)狀優(yōu)先的覆蓋網(wǎng)多播系統(tǒng)，是基于代理服務(wù)器（Proxy-based）的多播模式，即在代理服務(wù)器之間建立多播路由。Scattercast的拓?fù)浣Y(jié)構(gòu)類似于Narada，但在組成員發(fā)現(xiàn)方面，Scattercast采用分布式方法，沒(méi)有匯聚節(jié)點(diǎn)，而是采用類似Gossip[93]協(xié)議模式，成員之間隨機(jī)地進(jìn)行報(bào)文交互，相互獲得對(duì)方的信息。其次，Scattercast以時(shí)延為參數(shù)，構(gòu)造具有度約束的多播樹(shù)。由于運(yùn)行類似Gossip協(xié)議的信息交互算法，產(chǎn)生大量的冗余數(shù)據(jù)包，使得Scattercast的可擴(kuò)展性受到一定的影響。

為了提高覆蓋網(wǎng)多播的可擴(kuò)展性和可靠性，文獻(xiàn)[94]提出了一種特殊的網(wǎng)狀覆蓋網(wǎng)多播算法FaReCast：一種基于森林的M2M（Multiple parents To Multiple Children）覆蓋網(wǎng)單源多播。FaReCast在基本的最短路徑樹(shù)的基礎(chǔ)上，增加節(jié)點(diǎn)的父節(jié)點(diǎn)且連接其兄弟節(jié)點(diǎn)，構(gòu)成森林結(jié)構(gòu)，即每個(gè)節(jié)點(diǎn)有多個(gè)父節(jié)點(diǎn)和多個(gè)孩子節(jié)點(diǎn)，提高多播轉(zhuǎn)發(fā)的可靠性。同時(shí)，在數(shù)據(jù)分發(fā)的過(guò)程中，F(xiàn)aReCast采用多路徑多方向傳輸方式，增加數(shù)據(jù)轉(zhuǎn)發(fā)的效率，減少時(shí)延消耗。由于FaReCast采用的是森林結(jié)構(gòu)，其維護(hù)代價(jià)小于Mesh-first拓?fù)洌虼耍谝欢ǔ潭壬细纳屏丝蓴U(kuò)展性。

另外，還有一類特殊的網(wǎng)狀覆蓋網(wǎng)多播協(xié)議，它們?cè)诮Y(jié)構(gòu)化的P2P網(wǎng)狀結(jié)構(gòu)之上構(gòu)建多播樹(shù)，其代表協(xié)議有：基于CAN[95]的CAN-Multicast[96]、基于Pastry[97]的Scribe[98]和基于Tapestry[99]的Bayeux[100]等。CAN-Multicast將多播拓?fù)錁?gòu)造成CAN結(jié)構(gòu)，使用flood方法在CAN內(nèi)轉(zhuǎn)發(fā)多播數(shù)據(jù)，可以減少節(jié)點(diǎn)維護(hù)狀態(tài)信息的代價(jià)，提高數(shù)據(jù)傳輸?shù)目煽啃裕a(chǎn)生了大量的冗余報(bào)文。Scribe是應(yīng)用覆蓋網(wǎng)多播來(lái)傳輸大規(guī)模事件的通知系統(tǒng)，它的覆蓋網(wǎng)多播拓?fù)浣⒃赑astry之上，采取分布式策略為每個(gè)多播組分配一個(gè)ID標(biāo)識(shí)且建立一棵共享樹(shù)，通過(guò)ID匹配的方式進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。由于Pastry具有負(fù)載均衡的優(yōu)點(diǎn)，Scribe有較好的可擴(kuò)展性，但維護(hù)共享樹(shù)使得Scribe的復(fù)雜性增加。Bayeux的拓?fù)湟蕾囉赑2P系統(tǒng)Tapestry，每個(gè)節(jié)點(diǎn)維護(hù)自己獨(dú)立的路由表，通過(guò)與鄰居節(jié)點(diǎn)ID匹配的方法進(jìn)行逐跳路由。依據(jù)Tapestry的結(jié)構(gòu)特性，需要將多播樹(shù)的狀態(tài)信息保存在“中間節(jié)點(diǎn)”上，這限制了Bayeux的可擴(kuò)展性。

2．樹(shù)狀優(yōu)先覆蓋網(wǎng)多播

樹(shù)狀優(yōu)先是將終端節(jié)點(diǎn)直接連接形成一棵多播樹(shù)，而不依賴于Mesh拓?fù)洹?shù)狀優(yōu)先覆蓋網(wǎng)多播拓?fù)渚S護(hù)代價(jià)低，每個(gè)源到接收終端都有一條最短的路徑，非常適合大規(guī)模數(shù)據(jù)的快速分發(fā)[21][34][101][102]。在樹(shù)狀優(yōu)先結(jié)構(gòu)中，每?jī)蓚€(gè)組成員之間只有一條覆蓋路徑，不必考慮環(huán)路，因此在此結(jié)構(gòu)中組播路由算法比較簡(jiǎn)單。樹(shù)狀優(yōu)先可以分為有源樹(shù)和共享樹(shù)。有源樹(shù)是指每個(gè)多播源獨(dú)立建立以自己為根的最短路徑樹(shù)（Shortest Path Tree, SPT），適合于單源多播。有源樹(shù)需要為每個(gè)數(shù)據(jù)源構(gòu)造一棵樹(shù)，維護(hù)大量的狀態(tài)信息，開(kāi)銷較大。共享樹(shù)是以一個(gè)公共的匯聚節(jié)點(diǎn)為根建立的最小生成樹(shù)（Minimum Spanning Tree, MST），常用于多源多播。在共享樹(shù)中，數(shù)據(jù)源首先將數(shù)據(jù)包發(fā)送給匯聚點(diǎn)，匯聚點(diǎn)負(fù)責(zé)依據(jù)共享樹(shù)將數(shù)據(jù)轉(zhuǎn)發(fā)給接收者；一旦共享樹(shù)構(gòu)建好，所有源都沿此樹(shù)傳送數(shù)據(jù)，不必為每個(gè)數(shù)據(jù)源計(jì)算路由路徑。因此，共享樹(shù)建樹(shù)代價(jià)較有源樹(shù)小，但對(duì)于不同的數(shù)據(jù)源，路由路徑不是最優(yōu)的，通信效率差。

Yoid[103]是基于Tree-first的共享樹(shù)覆蓋網(wǎng)多播路由協(xié)議，它采用有度約束的方式在組成員節(jié)點(diǎn)之間建立多播轉(zhuǎn)發(fā)樹(shù)。Yoid也是一種集中式控制方式多播樹(shù)。在Yoid中，匯聚節(jié)點(diǎn)不僅負(fù)責(zé)維護(hù)節(jié)點(diǎn)間的鏈路狀態(tài)，為每個(gè)新加入節(jié)點(diǎn)提供必要的信息，還維護(hù)一個(gè)獨(dú)立于多播樹(shù)的Mesh結(jié)構(gòu)，用于避免或加速修復(fù)因節(jié)點(diǎn)失效或離開(kāi)而造成的多播樹(shù)分裂，提高路由的魯棒性。與Yoid類似，ALMI[104]也是基于Tree-first的采用集中控制的覆蓋網(wǎng)多播路由協(xié)議。該協(xié)議通過(guò)一個(gè)會(huì)話控制器（SC）管理組成員的加入和離開(kāi)。與Yoid不同的是，ALMI的匯聚節(jié)點(diǎn)SC不采取主動(dòng)探測(cè)的機(jī)制維護(hù)多播拓?fù)洌敲總€(gè)組成員節(jié)點(diǎn)監(jiān)測(cè)自己到鄰居節(jié)點(diǎn)的狀態(tài)信息，向SC報(bào)告。ALMI以最小化鏈路的時(shí)延代價(jià)為目標(biāo)建立多播共享樹(shù)。Overcast[105]是基于Tree-first結(jié)構(gòu)的覆蓋網(wǎng)多播協(xié)議，主要服務(wù)于內(nèi)容分發(fā)網(wǎng)（CDN），它以帶寬最大化為目標(biāo)在代理服務(wù)器之間（Proxy-based）建立有源多播樹(shù)。Overcast采用分布式策略動(dòng)態(tài)優(yōu)化多播樹(shù)，適用于大規(guī)模多播應(yīng)用。

雖然樹(shù)狀優(yōu)先覆蓋網(wǎng)多播具有較好的可擴(kuò)展性，可用于大規(guī)模數(shù)據(jù)分發(fā)，但也存在一些設(shè)計(jì)缺陷，最典型的是：

（1）節(jié)點(diǎn)的扇出（fan-out），隨著非葉子節(jié)點(diǎn)出度的增加，其數(shù)據(jù)分發(fā)性能呈對(duì)數(shù)級(jí)下降趨勢(shì)。

（2）對(duì)單點(diǎn)故障（single-point failure）非常敏感[106][107][108][109]。

針對(duì)節(jié)點(diǎn)的扇出對(duì)樹(shù)狀優(yōu)先覆蓋多播網(wǎng)性能的影響，文獻(xiàn)[110]提出了分層有度約束的覆蓋網(wǎng)多播協(xié)議LDCOM。該協(xié)議將多播樹(shù)狀結(jié)構(gòu)分為兩層：核心樹(shù)和擴(kuò)展樹(shù)，構(gòu)成核心樹(shù)的節(jié)點(diǎn)由具有雙向交互通信能力的節(jié)點(diǎn)組成。以度為約束條件構(gòu)造核心樹(shù)，使得時(shí)延最小化。而擴(kuò)展樹(shù)中的節(jié)點(diǎn)則負(fù)責(zé)單向多播數(shù)據(jù)傳輸，且沒(méi)有時(shí)延約束條件的限制，提高了整體的可擴(kuò)展性。關(guān)于雙向交互式多播通信，文獻(xiàn)[111]也進(jìn)行了深入研究，在滿足帶寬約束的條件下，以最小化網(wǎng)絡(luò)端到端時(shí)延為目標(biāo)，作者設(shè)計(jì)了啟發(fā)式算法求得近似解。

對(duì)于單點(diǎn)故障，常用兩種方法進(jìn)行恢復(fù)：被動(dòng)式（Reactive Approaches）方法和主動(dòng)式（Proactive Approaches）方法。被動(dòng)式方法是在節(jié)點(diǎn)發(fā)生故障后，立即采用即時(shí)檢測(cè)和重構(gòu)樹(shù)的方法進(jìn)行恢復(fù)，通常情況下，用樹(shù)中其他節(jié)點(diǎn)取代出現(xiàn)故障的節(jié)點(diǎn)[109][112][113]。被動(dòng)式方法重構(gòu)時(shí)間長(zhǎng)，時(shí)間開(kāi)銷較大，在重構(gòu)過(guò)程中多播應(yīng)用會(huì)被中斷。主動(dòng)式方法采用備份路由的方法，事先為每個(gè)可能出現(xiàn)故障的節(jié)點(diǎn)設(shè)置一個(gè)備份節(jié)點(diǎn)，一旦原節(jié)點(diǎn)出現(xiàn)故障，立即將它的子樹(shù)連接到備份節(jié)點(diǎn)。主動(dòng)方式使得多播樹(shù)的重構(gòu)過(guò)程平滑且快速[114][115][116][117][118][119]，然而，維護(hù)備份路由需要較大的開(kāi)銷。文獻(xiàn)[120]提出了成員關(guān)系持續(xù)意識(shí)的覆蓋網(wǎng)多播算法MDA-ALM，解決單點(diǎn)故障的問(wèn)題，減少重構(gòu)多播樹(shù)帶來(lái)的巨大開(kāi)銷。MDA-ALM要求每個(gè)新加入的節(jié)點(diǎn)聲明自己的“成員關(guān)系持續(xù)時(shí)間”，將成員關(guān)系持續(xù)時(shí)間長(zhǎng)的節(jié)點(diǎn)放置在樹(shù)的中間，而持續(xù)時(shí)間小的節(jié)點(diǎn)則布置在樹(shù)的下方或葉子節(jié)點(diǎn)。雖然MDA-ALM減少了單點(diǎn)故障對(duì)多播樹(shù)的影響，但它建立在節(jié)點(diǎn)的誠(chéng)信與合作的基礎(chǔ)上，如果節(jié)點(diǎn)是自私的，則嚴(yán)重影響MDA-ALM的性能。

3．層次狀覆蓋網(wǎng)多播

層次狀覆蓋網(wǎng)多播是為了滿足大規(guī)模數(shù)據(jù)分發(fā)的要求，減少多播拓?fù)渚S護(hù)代價(jià)而設(shè)計(jì)的多播結(jié)構(gòu)，其中最具有代表性的是NICE[121]和ZigZag[122]協(xié)議。NICE和ZigZag都使用了分層（Hierarchical）和分簇（Clustering）的思路，即將整個(gè)多播樹(shù)分成幾個(gè)層次（自下至上為0層、1層等），每層組成員分成多個(gè)簇，每個(gè)節(jié)點(diǎn)都屬于第0層。從底層開(kāi)始，選出一個(gè)節(jié)點(diǎn)作為leader，參與上一層簇的構(gòu)造，直到得到最高層的leader為止。當(dāng)新節(jié)點(diǎn)到來(lái)時(shí)，從最高層開(kāi)始，找到距離最近的leader并插入第0層。每個(gè)簇內(nèi)部構(gòu)造以leader為中心的星型結(jié)構(gòu)，如圖2-13所示。NICE和ZigZag的區(qū)別在于，在NICE中，每個(gè)leader是下一層選舉產(chǎn)生；而ZigZag則采用外領(lǐng)導(dǎo)節(jié)點(diǎn)作為下一層的父節(jié)點(diǎn)。由于ZigZag有效避免了因leader失效造成的路由分裂問(wèn)題，其可靠性優(yōu)于NICE。

4．其他覆蓋網(wǎng)多播協(xié)議

TAG[123]利用IP網(wǎng)絡(luò)拓?fù)湫畔⑤o助構(gòu)造多播樹(shù)，使覆蓋網(wǎng)多播路由盡可能與物理網(wǎng)絡(luò)路由相一致，提高路由性能。MSDOM/MMDOM[124][125]研究了節(jié)點(diǎn)的處理時(shí)延對(duì)于覆蓋網(wǎng)多播的影響，其作者指出多播源節(jié)點(diǎn)或中繼節(jié)點(diǎn)需同時(shí)復(fù)制多個(gè)副本并發(fā)送出去，因此與多播數(shù)據(jù)的傳輸時(shí)延相比較，處理時(shí)延顯得格外重要，而處理時(shí)延正比于節(jié)點(diǎn)的度，直接影響覆蓋網(wǎng)多播的性能。MSDOM/MMDOM以最小化覆蓋多播網(wǎng)的平均時(shí)延和最小化網(wǎng)絡(luò)的最大時(shí)延為目標(biāo)，提出了構(gòu)造覆蓋網(wǎng)多播的算法，并求得近似解。

HMTP[126]和CoreCast[127]研究了IP多播與覆蓋網(wǎng)多播相結(jié)合來(lái)解決IP多播存在“小島”的問(wèn)題。“小島”問(wèn)題是由于目前IP多播只部署在域內(nèi)，而沒(méi)有擴(kuò)展到域間而形成的。文獻(xiàn)[126]和[127]研究了在域內(nèi)仍是IP多播，而域間使用覆蓋網(wǎng)多播進(jìn)行連接的情況，是一種混合方案，不受網(wǎng)絡(luò)條件的限制，且充分利用IP多播效率高的優(yōu)點(diǎn)，應(yīng)用覆蓋網(wǎng)多播彌補(bǔ)了IP多播可擴(kuò)展性差的缺陷。HMTP側(cè)重于多播樹(shù)的構(gòu)造，而CoreCast應(yīng)用位置與標(biāo)識(shí)分離協(xié)議（LISP）構(gòu)造域間多播連接，提高可擴(kuò)展性。在CoreCast研究成果的基礎(chǔ)上，LCast[128]引入軟件定義的思想使得覆蓋網(wǎng)多播系統(tǒng)具有再配置功能，提高系統(tǒng)的靈活性。

2.4.4 覆蓋網(wǎng)感知方式

覆蓋網(wǎng)絡(luò)對(duì)于互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的感知大致可以分為兩種方式：主動(dòng)探測(cè)式和合作交互式。

1．主動(dòng)探測(cè)式

覆蓋節(jié)點(diǎn)根據(jù)某種度量標(biāo)準(zhǔn)主動(dòng)推測(cè)節(jié)點(diǎn)間的物理鄰近關(guān)系，用于覆蓋鏈路的建立和覆蓋路由的決策。這種方式由覆蓋網(wǎng)絡(luò)層主動(dòng)獨(dú)立完成，物理網(wǎng)絡(luò)感知不到這一選擇或決策過(guò)程的存在。這種方式中度量標(biāo)準(zhǔn)可以分為3種類型：基于時(shí)延或跳數(shù)、基于IP地址和基于節(jié)點(diǎn)的網(wǎng)絡(luò)坐標(biāo)。

（1）基于時(shí)延或跳數(shù)：覆蓋網(wǎng)絡(luò)系統(tǒng)運(yùn)用ping或traceroute協(xié)議主動(dòng)探測(cè)覆蓋節(jié)點(diǎn)間的往返時(shí)間（Round Trip Time, RTT）或IP路徑的跳數(shù)。例如，文獻(xiàn)[129]通過(guò)測(cè)量節(jié)點(diǎn)間的時(shí)延和跳數(shù)對(duì)BitTorrent系統(tǒng)內(nèi)的節(jié)點(diǎn)進(jìn)行聚類，建立層次狀覆蓋拓?fù)洌沟霉?jié)點(diǎn)盡可能在同一類內(nèi)進(jìn)行數(shù)據(jù)的傳輸。

（2）基于IP地址：這種類型利用了IP地址的層次結(jié)構(gòu)特性，即一個(gè)IP地址是由網(wǎng)絡(luò)地址和主機(jī)地址兩部分組成。在選擇鄰近節(jié)點(diǎn)，或在CDN網(wǎng)絡(luò)中選擇內(nèi)容服務(wù)器時(shí)，分析IP地址結(jié)構(gòu)，選擇位于同一子網(wǎng)內(nèi)的節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)[130]或內(nèi)容服務(wù)器[131]。

（3）基于節(jié)點(diǎn)的網(wǎng)絡(luò)坐標(biāo)：為每個(gè)覆蓋節(jié)點(diǎn)建立一個(gè)網(wǎng)絡(luò)坐標(biāo)，節(jié)點(diǎn)間的鄰近關(guān)系通過(guò)計(jì)算節(jié)點(diǎn)間坐標(biāo)距離得到，文獻(xiàn)[132]屬于該種類型。

2．合作交互式

這是一種覆蓋網(wǎng)絡(luò)與物理網(wǎng)絡(luò)相互合作的模式，在物理網(wǎng)絡(luò)中部署一個(gè)實(shí)體服務(wù)器（entity），收集物理網(wǎng)絡(luò)拓?fù)浼捌錉顟B(tài)信息；覆蓋網(wǎng)絡(luò)系統(tǒng)根據(jù)需要從實(shí)體服務(wù)器中取得相關(guān)信息。例如，德國(guó)電信實(shí)驗(yàn)室提出的Oracle[133]系統(tǒng)就是通過(guò)部署實(shí)體服務(wù)器，對(duì)每個(gè)覆蓋節(jié)點(diǎn)的鄰居節(jié)點(diǎn)按照其物理拓?fù)涞奈恢眠h(yuǎn)近進(jìn)行排序，幫助P2P客戶端選擇較優(yōu)的節(jié)點(diǎn)。SIS[134]通過(guò)部署實(shí)體服務(wù)器為覆蓋網(wǎng)絡(luò)層提供動(dòng)態(tài)的物理拓?fù)浜蜖顟B(tài)信息。此外，合作交互式為覆蓋網(wǎng)絡(luò)層提供的信息還可以考慮路徑代價(jià)、ISP策略等因素，例如，美國(guó)耶魯大學(xué)網(wǎng)絡(luò)系統(tǒng)實(shí)驗(yàn)室提出的P4P[135]系統(tǒng)。

上述研究成果在考慮互聯(lián)網(wǎng)基礎(chǔ)設(shè)施對(duì)覆蓋網(wǎng)絡(luò)的影響時(shí)，主要側(cè)重于覆蓋網(wǎng)路徑與物理路徑之間的相關(guān)性，對(duì)如何考慮物理網(wǎng)絡(luò)中部分關(guān)鍵節(jié)點(diǎn)對(duì)覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)造、路由和數(shù)據(jù)分發(fā)的影響；如何建立具有節(jié)點(diǎn)鄰近意識(shí)的覆蓋網(wǎng)絡(luò)，減少端到端的時(shí)延等問(wèn)題的研究不夠深入。研究表明，物理網(wǎng)絡(luò)中的部分節(jié)點(diǎn)頻繁出現(xiàn)在IP層最短路由路徑中，對(duì)于最優(yōu)路徑的選擇起著重要的作用[7]。本文正是根據(jù)這一特性，借鑒已有的研究成果對(duì)覆蓋網(wǎng)絡(luò)的拓?fù)錁?gòu)建、多路徑路由以及多播等相關(guān)問(wèn)題進(jìn)行了深入研究。