2.4 覆蓋網絡研究現狀

近年來覆蓋網絡技術得到了深入研究和廣泛應用。這些研究成果更多地集中于覆蓋網絡本身，過度依賴于覆蓋節點，缺乏對互聯網基礎設施的感知，導致覆蓋網絡不能發揮最佳性能。感知互聯網絡基礎設施是指在構建針對具體應用的覆蓋網絡（如路由覆蓋網絡、多播覆蓋網等）時，充分考慮底層物理網絡對覆蓋網絡性能的影響因素，盡可能獲得諸如物理網絡的局部拓撲結構、節點和鏈路狀態等信息；利用這些信息指導選擇鄰居覆蓋節點的過程，選擇更合理的覆蓋路由，滿足具體應用的需求，如覆蓋網絡中端到端的時延最小。在已有的研究成果中，只有少數在構建覆蓋網絡時考慮了互聯網基礎設施的感知問題，且僅局限于物理拓撲意識（Topology Awareness）[50][51][52][53]，具體地講，是在建立覆蓋網絡拓撲時考慮覆蓋網絡拓撲與物理網絡的相關性[54][55][56]。

下面按照網絡功能，詳細介紹與本文研究內容緊密相關的幾個方面的研究動態，包括覆蓋網絡拓撲構建、覆蓋網絡路由和覆蓋網絡多播，具體包括感知與非感知兩種思路。最后闡述了覆蓋網絡對互聯網基礎設施相關信息的感知方式。

2.4.1 覆蓋網拓撲構建

不同的拓撲模型決定了覆蓋網具有的不同的性能，覆蓋網拓撲直接影響網絡的可擴展性、可靠性、安全性、故障的恢復性和傳輸負載分布情況。構建覆蓋網絡拓撲的關鍵是覆蓋節點的選擇以及這些節點間的連接方式。通常情況下，針對不同的應用需求，可靈活地構建相應的覆蓋網絡拓撲，即覆蓋網絡拓撲是面向應用的。根據具體的應用需求，覆蓋網絡拓撲研究可以分為以下幾類。

1．服務于路由的覆蓋網拓撲

路由覆蓋網絡拓撲是服務于覆蓋路由的拓撲，是以覆蓋路由為手段，以提升網絡傳輸性能或提供新型網絡服務模式為目的建立起來的覆蓋網拓撲。與IP路由不同的是，覆蓋路由主要依靠服務器或主機節點在覆蓋網層或應用層實現數據的轉發。位于覆蓋網絡中的服務器或主機節點被稱為覆蓋節點。路由覆蓋網是用來彌補原有IP路由協議的不足，提升互聯網絡端到端的傳輸性能和連通性，提高網絡資源的利用率，特別是增強網絡的可靠性和彈性（resiliency）。在路由覆蓋網絡中，覆蓋網絡拓撲和路由協議的性能直接影響覆蓋網絡的恢復能力和彈性。當收到一個需要覆蓋路由的報文時，覆蓋節點首先解析報文并獲得目的地址信息（不是IP報文的目的地址），然后根據預先設定的覆蓋路由算法計算下一跳覆蓋節點的IP地址，且更新原來的目標IP地址，最后通過物理層網絡發往新的方向。

構建覆蓋網絡拓撲時，物理鏈路的失效恢復能力是需要考慮的一個重要因素。當物理網絡出現鏈路故障時，源節點尋找最佳覆蓋路徑，避開失效鏈路，將受影響的數據快速路由到目的節點。是否可以有效地避開失效鏈路，快速實現數據的再傳輸的兩個重要因素是覆蓋網路由的有效性和路由性能。覆蓋網路由的有效性依賴于覆蓋網絡拓撲，例如，全網狀拓撲可以提供更多的路由選擇，但其可擴展性比較差。覆蓋網路由的性能，即路由質量，是由路徑的差異度（Path Diversity）決定的。路徑的差異度也是衡量覆蓋網絡拓撲對失效鏈路的恢復能力的重要指標。路徑差異度是指兩條路徑之間共享鏈路的數目，共享鏈路越少，差異度越大，則由共享鏈路失效引發的同步故障發生的幾率越小。在覆蓋網絡中，共享覆蓋鏈路則必定共享構成這條覆蓋鏈路的物理路徑，因此覆蓋網絡中兩條覆蓋路徑之間的差異度是兩條覆蓋路徑共享的覆蓋鏈路的條數。當覆蓋網傳輸大規模數據時，會導致共享的物理路徑的負載增大，當負載達到一定程度時會出現擁塞。兩條或多條覆蓋網路徑共享的覆蓋鏈路數越少，表明這個覆蓋網絡的拓撲性能越好。當然，邏輯上完全獨立的兩條覆蓋網路徑，在物理網絡中可能共享了物理鏈路和物理節點，如圖2-6所示。共享的物理鏈路或物理節點出現故障時，必然導致相應的覆蓋路徑故障。綜上所述，研究覆蓋網絡拓撲，就是設計一個具有合理的可用覆蓋路徑且路徑差異度盡量少的拓撲。

根據是否具有物理拓撲意識，覆蓋網絡拓撲可以分為具有拓撲意識的覆蓋網絡和無拓撲意識的覆蓋網絡。文獻[19]研究了具有物理拓撲意識的覆蓋網節點選擇方法。該文獻中，覆蓋網絡拓撲與物理拓撲間的相關性通過路徑差異度來衡量。路徑差異度被定義為連接源節點與目的節點的覆蓋網絡路徑與物理路徑上重疊的節點數。根據路徑差異度的相似程度，作者將全部覆蓋網絡節點聚為幾個不同的簇，并從每個簇中隨機選擇一個節點作為覆蓋網節點。該算法雖然在選擇覆蓋網絡節點時充分考慮了節點間的相關性，但如何合理確定簇的個數，是一個較為復雜的問題。類似的方法也出現在文獻[57]和[58]中。在文獻[57]中，作者利用物理拓撲意識來選擇備份覆蓋路徑，使備份路徑與默認的物理路徑之間具有最小的相關性。在文獻[58]中，作者描述了一個“裝箱機制”（binning scheme），首先假設一部分節點為基準點（landmark），然后根據ping命令測試其他節點到基準點的距離（這里指的是時延），將距離相近的點分配到同一個箱中。該算法假設，處于不同箱中的節點的相關性較小，通過這些節點的路徑的差異度較大。在一定程度上，與隨機選取覆蓋網節點相比較，通過這種裝箱機制選擇覆蓋網節點，構建的覆蓋網拓撲具有較好的性能。文獻[59]綜合節點相關性和鏈路相關性，研究了基于物理拓撲意識的覆蓋網拓撲構建機制。該文獻中，作者為構建路由覆蓋網拓撲提出3個基于圖論的指標：特征路徑長度（Characteristic Path Length, CPL）、平均割集規模（Average Cut Size）和節點度的加權和（Weighted Node Degree Sum），分別考慮了鏈路相關性、節點相關性、節點的容量等因素。一些啟發式算法被用于建立覆蓋網絡拓撲。例如，文獻[60]提出兩種啟發式算法：拓撲意識的K最小共享鏈路生成樹（Topology-aware K Minimum joint-Spanning Tress, TKMST）和拓撲意識的K隨機連接網（Topology-aware K Random Connection, KRC）。雖然TKMST和KRC都具有物理拓撲感知能力，但兩者針對每個節點設置了度約束條件。眾所周知，具有度約束的最小生成樹問題是一個NP難問題，其計算復雜度是O（|Vu|3），其中|Vu|表示物理網絡的節點數。文獻[61]也提出具有流量感知能力的啟發式覆蓋網絡拓撲構建算法，但假設流經每個節點的流量是一個定值，不能真實地反映網絡的現狀。

RON[23]是第一個研究路由覆蓋網絡實現機制的算法，屬于非拓撲意識的覆蓋網絡構建算法。RON應用全網狀結構（Full Mesh, FM）連接所有的覆蓋網節點。全網狀結構使得RON可以快速檢測路由的失效情況，并選擇最佳的替代覆蓋網絡路徑。當物理網絡的鏈路出現故障時，源節點探測每一個覆蓋網節點，選擇一個時延最小（或者帶寬最大）的節點作為中繼節點，形成一跳覆蓋網路由路徑，完成數據的傳輸。然而，正是由于全網狀結構，RON用于檢測和維護覆蓋網絡拓撲的代價是O（N2），其中，N是系統中覆蓋網絡節點數，這嚴重影響了RON的可擴展性。實驗表明當覆蓋網絡的節點數大于50時，RON的性能急劇下降。針對RON的可擴展性問題，文獻[62]提出了改進的算法，即在節點度約束的條件下，節點間進行隨機連接建立覆蓋網絡拓撲，但這些改進算法所選擇的路由路徑往往并非最佳路徑。

根據連接方式的不同，覆蓋網絡拓撲分為網狀結構、樹狀結構，以及混合結構3種類型。RON是典型的網狀結構，由于全網狀連接，可擴展性是RON的最大問題。文獻[63]提出了K最小生成樹（K Minimum Spanning Tree, KMST）結構覆蓋網絡拓撲，確保任何兩個覆蓋節點之間存在K條覆蓋路徑。KMST僅保證了覆蓋層路徑之間的差異度，而未考慮物理層路徑的差異度，即不具有互聯網基礎設施感知能力。文獻[60]提出一種混合結構覆蓋網絡拓撲構建算法（Mesh-Tree, MT）。MT在構造最小生成樹的基礎上，在物理拓撲中具有祖孫關系、叔侄關系的節點間增加覆蓋鏈路。混合結構增強了覆蓋網絡的魯棒性和可靠性。在可擴展性方面，KMST和MT優于RON的全網狀結構。由于這些算法專注于覆蓋節點間的連接關系，忽略了節點的選擇對于覆蓋網絡拓撲的重要性。

網狀、樹狀和混合結構的覆蓋網絡拓撲的一個共同的特性是：三者均提供選擇覆蓋網路由的平臺，即當系統需要覆蓋路由時，基于某個平臺，從已有的覆蓋節點和覆蓋鏈路中選擇一條性能最佳的覆蓋路由。因此，網狀、樹狀和混合結構覆蓋網絡拓撲屬于相對固定的、預設的拓撲，提供的路由屬于備份路由。這些拓撲需要定期地探測和維護節點的可用性和鏈路的可達性。一跳覆蓋網源路由（Single One-hop Source Routing, SOSR）[24]不需要維護拓撲，僅在需要路由時探測少數節點，選擇最佳的路徑。所謂的“一跳源路由”是指路由路徑中只需一個中繼節點的源路由機制。研究表明許多高效的覆蓋路由僅通過一個中間覆蓋節點便可以完成，不需要多跳覆蓋路由[24]。SOSR的路由機制非常簡單：當源節點需要發送數據時，它從覆蓋節點中隨機選擇K個節點作為中繼節點，形成K條一跳覆蓋路徑；通過在每條覆蓋路徑上發送探測包，選擇一條時延最小的路徑作為最終的路由路徑，如圖2-7所示。實驗結果表明K=4時便可以得到很好的路由效果[24]。

2．服務于QoS的覆蓋網拓撲

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

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

構建服務覆蓋網絡是一種利益相關的投資行為。對于服務提供商而言，其目標是在滿足用戶需求的前提下，達到收益最大化。如圖2-9所示，服務覆蓋網絡依賴于OSP、ISPs和終端用戶三者間的利益關系：從滿足QoS需求的角度看，SON保障端到端的QoS，同時確保覆蓋鏈路的帶寬；從收益的角度看，OSP需要從服務用戶得到收益且支付購買帶寬的費用。由于需要權衡經濟代價與QoS性能之間的關系，構建SON是一個復雜且具有挑戰性的任務。因此，通常將服務覆蓋網絡拓撲的構建問題抽象為一個數學模型，得到滿足帶寬（或時延）需求的最小代價解。

文獻[39]首先提出了服務覆蓋網絡的概念，該文獻中，作者通過分析影響服務覆蓋網絡拓撲的各種因素，如SLA、QoS、流量分布和帶寬等，提出服務覆蓋網絡結構及概念，但沒有涉及具體的拓撲設計問題。針對影響覆蓋網絡拓撲的因素，已有的研究從各個角度對SON進行了深入研究。文獻[64]研究了在同時滿足帶寬和時延QoS需求的情況下，服務覆蓋網絡的拓撲構建問題。類似的研究還有文獻[65]，作者將服務覆蓋網絡拓撲建造問題抽象成為一個多目標優化問題，使得網絡的傳輸代價和鏈路的時延最小，并設計一個啟發式算法進行求解。文獻[66]研究了在確保帶寬的前提下，服務節點ON的數量和合理放置問題，達到最小化服務提供商的運營成本的目的。在此基礎上，文獻[67]進一步研究了服務節點ON的部署問題，以及確保QoS需求時最小的帶寬開銷，設計了混合線性規劃算法。文獻[40]在構建覆蓋網拓撲時不僅考慮ONs間的傳輸鏈路，而且考慮了建立終端節點ESs與ONs節點間的接入鏈路的代價。

為了提高服務覆蓋網絡的可擴展性，文獻[68]和[69]分別研究了不同AS間ONs的連接問題，旨在建立大規模服務覆蓋網絡，滿足終端用戶的QoS需求。作者從數學角度證明了該問題是一個NP難問題，并提出了多個啟發式算法進行求解。針對同樣的問題，QRON[25]以滿足端到端時延和拓撲的可擴展為研究目標，提出了層次化拓撲構建算法，引入了Overlay Brokers（OBs）的概念。OBs的作用等同于ONs，每個自治系統（AS）至少包括一個OBs。在同一AS內部，ONs間連接形成全網狀結構，而AS間通過至少一條隧道連接。QRON提出了兩種鏈路代價算法，分別為改進的最短路徑（Modified Shortest-Distance Path, MSDP）算法和成比例的帶寬最小路徑（Proportional Bandwidth Shortest Path, PBSP）算法，旨在通過平衡OBs之間的數據流量和覆蓋鏈路來尋求一條較優的覆蓋路徑。

文獻[70]研究了覆蓋網拓撲構建的動態經濟模型。在該模型中，為了使服務提供商OSP的收益最大化，根據承載的業務流量的需求變化動態調整所租用的鏈路帶寬。按照文獻[70]的研究思路，文獻[71]研究了動態流量的測量與評估方法，為構建服務覆蓋網絡拓撲提供理論依據。為了適應動態流量的需求，文獻[41]研究了服務覆蓋網絡拓撲的動態再配置策略，以最小化傳輸數據的代價和再配置覆蓋網絡的代價為目標，設計了最優化算法。文獻[72]提出了多平面架構的下一代服務覆蓋網絡模型NGSON，目的是解決不同業務功能的覆蓋網絡如何相互合作，共享資源的問題，為構建在同一基礎設施上的多個覆蓋網絡的建設提供了思路。

2.4.2 覆蓋網路由

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

文獻[23]最早提出了彈性覆蓋網絡RON（Resilient Overlay Network）的概念，研究了覆蓋網路由的可行性和路由機制。RON采用全連接覆蓋網拓撲，周期性地測量覆蓋節點之間虛擬鏈路的性能（如時延），及時發現故障，以探測得到的節點間的性能參數作為選擇最佳覆蓋路由的依據。繼RON之后，已有關于覆蓋路由的研究主要集中在提高覆蓋路由性能、可擴展性，以及減少負載等幾個方面。

1．覆蓋路由的性能

覆蓋路由可以彌補IP路由的不足，改善端到端的傳輸性能，即通過覆蓋網絡為默認的IP路徑提供備份路徑。當IP路徑出現鏈路斷裂或擁塞等故障時，應用覆蓋網絡所提供的備份路徑繞過故障點傳輸數據。因此，覆蓋路由的好壞取決于備份路徑的選擇。備份路徑的選擇需考慮兩個方面的因素：拓撲意識和時延或帶寬[76]。對于一跳覆蓋路由，選擇備份路徑就是選擇構成一跳覆蓋路徑的中繼節點。

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

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

除了時延外，鏈路帶寬也是選擇覆蓋路徑的標準之一。文獻[25]和[80]使用了可用帶寬作為評價指標來選擇覆蓋路徑，使其滿足QoS需求。然而，可用帶寬很難被精確測量，常常應用估計的方法得到其近似值。

2．可擴展性

路由覆蓋網絡的可擴展性是由網絡的維護代價（Overhead）決定的，維護代價越高，其可擴展性越低。覆蓋網絡的維護代價由鏈路探測代價、狀態發布代價和路由計算代價三部分構成。通常情況下，構建路由覆蓋網絡拓撲時忽略路由計算代價。

（1）鏈路探測代價：通過ping或traceroute方式，覆蓋網絡中每個節點周期性地向相鄰節點發送探測包，獲得鏈路的狀態參數（如可達性、時延或帶寬），建立自己的鏈路狀態表（Link State Table, LST）。

（2）狀態發布代價：每個覆蓋網絡節點周期性地廣播自己的鏈路狀態表，且收到其他節點的鏈路狀態表，完善自己的狀態表并作為路由計算的依據。

（3）路由計算代價：根據用戶的需求和鏈路所承載的當前流量，計算最佳路由。

解決覆蓋網絡的可擴展性問題，首先要從拓撲結構入手。根據拓撲層次結構的不同，覆蓋網絡拓撲分為扁平式、層次式和一跳覆蓋網絡。對于扁平結構覆蓋網絡，最具有代表性的是RON全網狀結構。在RON中，由于每個節點都知道其他n-1個節點的連接狀態，所以RON可以找到最佳的覆蓋路由。然而，RON的監測與維護代價嚴重影響它的性能優勢。因此，一些改進算法著重研究如何減少RON的監測和維護代價。已有的解決方法可以歸納為3種類型：構建半網狀或樹狀覆蓋拓撲、增大監測的周期，以及減少監測的節點數。文獻[62]和[63]分別研究了半網狀和樹狀覆蓋拓撲，它們的原理通過減少覆蓋節點的連接度來降低覆蓋網的監測和維護代價。然而，研究表明，在半網狀和樹狀拓撲結構中，30%具有低時延和低丟包率的路徑沒有被包括在覆蓋路徑中[81]。文獻[81]也研究了增大監測周期對覆蓋網絡性能的影響，表明監測周期每增大一倍，監測流量減少一半，但會得到10%～30%的無效或陳舊的路由信息。鑒于前兩者的不足，大量的研究集中于通過減少監測的節點數提高覆蓋網絡的可擴展性。文獻[82]～文獻[84]應用Grid Quorum[85]機制將覆蓋網監測和維護代價從O（n2）降低至O（n1.5）。在文獻[86]中，作者應用Grid Quorum系統[85]，選擇多個匯聚節點分布式匯總節點間的鏈路狀態信息，將監測和維護覆蓋網絡的代價從O（n1.5）降低到O，雖然性能得到了一定的提高，但帶來多個匯聚節點間信息同步的問題。文獻[87]提出了一個基于斷層掃描（Tomography-based）的覆蓋網絡監測系統TOM，有選擇地監測K條覆蓋路徑。通過對這K條路徑的監測結果推測出其他路徑的狀態，從而將監測代價降低到O（nlogn）。

層次式覆蓋網絡拓撲通過分層監測鏈路狀態、集中匯總的方式提高其可擴展性。層次式的思想類似于OSPF協議，每個節點僅監測和維護所屬區域的鏈路狀態信息，大大降低了維護的代價。最具有代表性的層次式路由覆蓋網絡是QRON。在QRON中，根據節點間鏈路的時延，將相似的節點組織成一個類，類內形成全網狀連接。對于多個類，依據類間的相似性再進行聚類，這樣形成一個多層結構的拓撲，如圖2-11所示。鏈路狀態信息僅在類內被廣播，類間的信息傳遞通過網關節點完成。實驗結果表明，層次式結構改進了網絡的可擴展性，降低了監測和維護的代價。

第3種改善路由覆蓋網絡可擴展性的方法是一跳覆蓋路由，即僅通過一個中繼覆蓋節點完成數據的傳輸。此方法關鍵在中繼節點的選取。例如，文獻[87]應用Grid Quorum[85]機制優選中繼節點，降低因鏈路狀態廣播帶來的代價。文獻[19]和[24]對此也有深入研究，具體內容在“覆蓋網絡的性能”中有詳細討論，在此不再贅述。

2.4.3 覆蓋網多播

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

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

根據構造方式的不同，覆蓋網多播可以分為網狀優先（Mesh-first）、樹狀優先（Tree-first）和層次狀（Hierarchical Topology）三類。按協議和算法的控制方式，還可以分為集中式和分布式兩種。集中式方法由一個匯聚節點（Rendezvous Point, RP）負責覆蓋網多播狀態信息收集和路由計算；而在分布式方法中，狀態信息探測與更新和路由計算由各端系統節點負責。

1．網狀優先覆蓋網多播

網狀優先方式是將終端節點連接形成一個網狀的拓撲結構（Mesh），即控制拓撲；然后根據具體的多播業務需求構建基于Mesh的多播樹，即數據傳輸拓撲。控制拓撲負責在所有組成員之間建立拓撲圖，周期性地在節點之間交換狀態信息，維護和更新控制拓撲狀態，增強整個系統的健壯性和可靠性。由于需要周期性地優化控制拓撲，加重了系統的負載，所以可擴展性差是網狀優先多播拓撲的缺陷。數據拓撲則是基于控制拓撲的生成樹，通常情況下，以每個數據源為根構造一棵基于控制拓撲的生成樹。由于數據拓撲是直接從控制拓撲得到的，因此，控制拓撲（即網狀拓撲）的構造直接影響數據傳輸的質量。

Narada協議[21]是最早提出的基于網狀優先的覆蓋網多播路由協議之一，是一種集中式路由控制協議。在該協議中，所有組成員節點將構成一個虛擬Mesh控制拓撲。Narada通過匯聚節點收集成員之間的信息構建Mesh結構。在控制Mesh拓撲上，Narada運行類似于DVMRP的距離向量協議使每個成員得到整個網絡的路由信息，以每個數據源為根，綜合時延和帶寬兩個參數構造一棵生成樹。由于每個成員需周期性地同其他成員交換狀態信息，產生了大量的維護開銷，導致可擴展性差，因此只適用于小規模組播應用。

Scattercast[92]也是一種網狀優先的覆蓋網多播系統，是基于代理服務器（Proxy-based）的多播模式，即在代理服務器之間建立多播路由。Scattercast的拓撲結構類似于Narada，但在組成員發現方面，Scattercast采用分布式方法，沒有匯聚節點，而是采用類似Gossip[93]協議模式，成員之間隨機地進行報文交互，相互獲得對方的信息。其次，Scattercast以時延為參數，構造具有度約束的多播樹。由于運行類似Gossip協議的信息交互算法，產生大量的冗余數據包，使得Scattercast的可擴展性受到一定的影響。

為了提高覆蓋網多播的可擴展性和可靠性，文獻[94]提出了一種特殊的網狀覆蓋網多播算法FaReCast：一種基于森林的M2M（Multiple parents To Multiple Children）覆蓋網單源多播。FaReCast在基本的最短路徑樹的基礎上，增加節點的父節點且連接其兄弟節點，構成森林結構，即每個節點有多個父節點和多個孩子節點，提高多播轉發的可靠性。同時，在數據分發的過程中，FaReCast采用多路徑多方向傳輸方式，增加數據轉發的效率，減少時延消耗。由于FaReCast采用的是森林結構，其維護代價小于Mesh-first拓撲，因此，在一定程度上改善了可擴展性。

另外，還有一類特殊的網狀覆蓋網多播協議，它們在結構化的P2P網狀結構之上構建多播樹，其代表協議有：基于CAN[95]的CAN-Multicast[96]、基于Pastry[97]的Scribe[98]和基于Tapestry[99]的Bayeux[100]等。CAN-Multicast將多播拓撲構造成CAN結構，使用flood方法在CAN內轉發多播數據，可以減少節點維護狀態信息的代價，提高數據傳輸的可靠性，但產生了大量的冗余報文。Scribe是應用覆蓋網多播來傳輸大規模事件的通知系統，它的覆蓋網多播拓撲建立在Pastry之上，采取分布式策略為每個多播組分配一個ID標識且建立一棵共享樹，通過ID匹配的方式進行數據轉發。由于Pastry具有負載均衡的優點，Scribe有較好的可擴展性，但維護共享樹使得Scribe的復雜性增加。Bayeux的拓撲依賴于P2P系統Tapestry，每個節點維護自己獨立的路由表，通過與鄰居節點ID匹配的方法進行逐跳路由。依據Tapestry的結構特性，需要將多播樹的狀態信息保存在“中間節點”上，這限制了Bayeux的可擴展性。

2．樹狀優先覆蓋網多播

樹狀優先是將終端節點直接連接形成一棵多播樹，而不依賴于Mesh拓撲。樹狀優先覆蓋網多播拓撲維護代價低，每個源到接收終端都有一條最短的路徑，非常適合大規模數據的快速分發[21][34][101][102]。在樹狀優先結構中，每兩個組成員之間只有一條覆蓋路徑，不必考慮環路，因此在此結構中組播路由算法比較簡單。樹狀優先可以分為有源樹和共享樹。有源樹是指每個多播源獨立建立以自己為根的最短路徑樹（Shortest Path Tree, SPT），適合于單源多播。有源樹需要為每個數據源構造一棵樹，維護大量的狀態信息，開銷較大。共享樹是以一個公共的匯聚節點為根建立的最小生成樹（Minimum Spanning Tree, MST），常用于多源多播。在共享樹中，數據源首先將數據包發送給匯聚點，匯聚點負責依據共享樹將數據轉發給接收者；一旦共享樹構建好，所有源都沿此樹傳送數據，不必為每個數據源計算路由路徑。因此，共享樹建樹代價較有源樹小，但對于不同的數據源，路由路徑不是最優的，通信效率差。

Yoid[103]是基于Tree-first的共享樹覆蓋網多播路由協議，它采用有度約束的方式在組成員節點之間建立多播轉發樹。Yoid也是一種集中式控制方式多播樹。在Yoid中，匯聚節點不僅負責維護節點間的鏈路狀態，為每個新加入節點提供必要的信息，還維護一個獨立于多播樹的Mesh結構，用于避免或加速修復因節點失效或離開而造成的多播樹分裂，提高路由的魯棒性。與Yoid類似，ALMI[104]也是基于Tree-first的采用集中控制的覆蓋網多播路由協議。該協議通過一個會話控制器（SC）管理組成員的加入和離開。與Yoid不同的是，ALMI的匯聚節點SC不采取主動探測的機制維護多播拓撲，而是每個組成員節點監測自己到鄰居節點的狀態信息，向SC報告。ALMI以最小化鏈路的時延代價為目標建立多播共享樹。Overcast[105]是基于Tree-first結構的覆蓋網多播協議，主要服務于內容分發網（CDN），它以帶寬最大化為目標在代理服務器之間（Proxy-based）建立有源多播樹。Overcast采用分布式策略動態優化多播樹，適用于大規模多播應用。

雖然樹狀優先覆蓋網多播具有較好的可擴展性，可用于大規模數據分發，但也存在一些設計缺陷，最典型的是：

（1）節點的扇出（fan-out），隨著非葉子節點出度的增加，其數據分發性能呈對數級下降趨勢。

（2）對單點故障（single-point failure）非常敏感[106][107][108][109]。

針對節點的扇出對樹狀優先覆蓋多播網性能的影響，文獻[110]提出了分層有度約束的覆蓋網多播協議LDCOM。該協議將多播樹狀結構分為兩層：核心樹和擴展樹，構成核心樹的節點由具有雙向交互通信能力的節點組成。以度為約束條件構造核心樹，使得時延最小化。而擴展樹中的節點則負責單向多播數據傳輸，且沒有時延約束條件的限制，提高了整體的可擴展性。關于雙向交互式多播通信，文獻[111]也進行了深入研究，在滿足帶寬約束的條件下，以最小化網絡端到端時延為目標，作者設計了啟發式算法求得近似解。

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

3．層次狀覆蓋網多播

層次狀覆蓋網多播是為了滿足大規模數據分發的要求，減少多播拓撲維護代價而設計的多播結構，其中最具有代表性的是NICE[121]和ZigZag[122]協議。NICE和ZigZag都使用了分層（Hierarchical）和分簇（Clustering）的思路，即將整個多播樹分成幾個層次（自下至上為0層、1層等），每層組成員分成多個簇，每個節點都屬于第0層。從底層開始，選出一個節點作為leader，參與上一層簇的構造，直到得到最高層的leader為止。當新節點到來時，從最高層開始，找到距離最近的leader并插入第0層。每個簇內部構造以leader為中心的星型結構，如圖2-13所示。NICE和ZigZag的區別在于，在NICE中，每個leader是下一層選舉產生；而ZigZag則采用外領導節點作為下一層的父節點。由于ZigZag有效避免了因leader失效造成的路由分裂問題，其可靠性優于NICE。

4．其他覆蓋網多播協議

TAG[123]利用IP網絡拓撲信息輔助構造多播樹，使覆蓋網多播路由盡可能與物理網絡路由相一致，提高路由性能。MSDOM/MMDOM[124][125]研究了節點的處理時延對于覆蓋網多播的影響，其作者指出多播源節點或中繼節點需同時復制多個副本并發送出去，因此與多播數據的傳輸時延相比較，處理時延顯得格外重要，而處理時延正比于節點的度，直接影響覆蓋網多播的性能。MSDOM/MMDOM以最小化覆蓋多播網的平均時延和最小化網絡的最大時延為目標，提出了構造覆蓋網多播的算法，并求得近似解。

HMTP[126]和CoreCast[127]研究了IP多播與覆蓋網多播相結合來解決IP多播存在“小島”的問題。“小島”問題是由于目前IP多播只部署在域內，而沒有擴展到域間而形成的。文獻[126]和[127]研究了在域內仍是IP多播，而域間使用覆蓋網多播進行連接的情況，是一種混合方案，不受網絡條件的限制，且充分利用IP多播效率高的優點，應用覆蓋網多播彌補了IP多播可擴展性差的缺陷。HMTP側重于多播樹的構造，而CoreCast應用位置與標識分離協議（LISP）構造域間多播連接，提高可擴展性。在CoreCast研究成果的基礎上，LCast[128]引入軟件定義的思想使得覆蓋網多播系統具有再配置功能，提高系統的靈活性。

2.4.4 覆蓋網感知方式

覆蓋網絡對于互聯網基礎設施的感知大致可以分為兩種方式：主動探測式和合作交互式。

1．主動探測式

覆蓋節點根據某種度量標準主動推測節點間的物理鄰近關系，用于覆蓋鏈路的建立和覆蓋路由的決策。這種方式由覆蓋網絡層主動獨立完成，物理網絡感知不到這一選擇或決策過程的存在。這種方式中度量標準可以分為3種類型：基于時延或跳數、基于IP地址和基于節點的網絡坐標。

（1）基于時延或跳數：覆蓋網絡系統運用ping或traceroute協議主動探測覆蓋節點間的往返時間（Round Trip Time, RTT）或IP路徑的跳數。例如，文獻[129]通過測量節點間的時延和跳數對BitTorrent系統內的節點進行聚類，建立層次狀覆蓋拓撲，使得節點盡可能在同一類內進行數據的傳輸。

（2）基于IP地址：這種類型利用了IP地址的層次結構特性，即一個IP地址是由網絡地址和主機地址兩部分組成。在選擇鄰近節點，或在CDN網絡中選擇內容服務器時，分析IP地址結構，選擇位于同一子網內的節點作為鄰居節點[130]或內容服務器[131]。

（3）基于節點的網絡坐標：為每個覆蓋節點建立一個網絡坐標，節點間的鄰近關系通過計算節點間坐標距離得到，文獻[132]屬于該種類型。

2．合作交互式

這是一種覆蓋網絡與物理網絡相互合作的模式，在物理網絡中部署一個實體服務器（entity），收集物理網絡拓撲及其狀態信息；覆蓋網絡系統根據需要從實體服務器中取得相關信息。例如，德國電信實驗室提出的Oracle[133]系統就是通過部署實體服務器，對每個覆蓋節點的鄰居節點按照其物理拓撲的位置遠近進行排序，幫助P2P客戶端選擇較優的節點。SIS[134]通過部署實體服務器為覆蓋網絡層提供動態的物理拓撲和狀態信息。此外，合作交互式為覆蓋網絡層提供的信息還可以考慮路徑代價、ISP策略等因素，例如，美國耶魯大學網絡系統實驗室提出的P4P[135]系統。

上述研究成果在考慮互聯網基礎設施對覆蓋網絡的影響時，主要側重于覆蓋網路徑與物理路徑之間的相關性，對如何考慮物理網絡中部分關鍵節點對覆蓋網絡拓撲構造、路由和數據分發的影響；如何建立具有節點鄰近意識的覆蓋網絡，減少端到端的時延等問題的研究不夠深入。研究表明，物理網絡中的部分節點頻繁出現在IP層最短路由路徑中，對于最優路徑的選擇起著重要的作用[7]。本文正是根據這一特性，借鑒已有的研究成果對覆蓋網絡的拓撲構建、多路徑路由以及多播等相關問題進行了深入研究。