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]。本文正是根据这一特性，借鉴已有的研究成果对覆盖网络的拓扑构建、多路径路由以及多播等相关问题进行了深入研究。