满足能力约束和QoS约束的应用层任意源多播方法

摘要

本发明涉及一种满足能力约束和QoS约束的应用层任意源多播方法，建立在随机覆盖网及一个非DHT(distributed hash table)环的基础上，满足能力约束、动态成员等分布式应用需求，具有完全分布的特点，可以在Internet范围内扩展。不需要额外的维护，使其很适合具有多个潜在数据源的多播应用；具有较好的跳数复杂性和通信复杂性，节点的多播覆盖率高；具有节点能力约束性能，具有满足动态QoS约束的性能；本发明结构简单，易于实现。

说明书

技术领域

本发明涉及一种计算机网络技术，特别涉及一种覆盖网络多播方法。

背景技术

多播技术是一种针对多点传输和多方协作应用的组通信模型。相比单播通信，它能节省大量的网络通信资源，并提高通信效率，为数据的多点并发传输提供了有效途径。早期人们致力于IP多播的研究，然而由于多方面的原因，IP多播技术并未能得到广泛的应用。于是，人们提出了覆盖多播的概念，希望直接在应用层提供多播服务。

许多文献从不同角度对覆盖多播进行了研究。但现存系统尚不能对需要进行任意源多播且多播组中结点能力不同、组成员动态变化的应用提供有效支持。

近年来提出的许多覆盖多播系统都面向单数据源设计，致力于优化单个源的多播树，它们适合于分发视频或软件，但并不适合诸如分布式游戏、电信会议、虚拟教室等多源多播应用。为每个可能的源建立相应的多播树的代价高昂，而用单个多播树服务于多源同样问题很多，这使其不能简单扩展到任意源多播系统中。

为管理动态多播组并确保可扩展性，已存在其他一些在P2P覆盖网上实现多播的方法，如：Bayeux，Borg分别是基于Tapestry，Pastry等覆盖拓扑结构而实现的。但是以上系统均假设每个结点具有相同数量的子结点。而事实上，多播组中结点在体现结点能力的上载带宽、内存、CPU等方面各不相同。给通信组中每个中间结点指定相同数量子结点的策略显然不够优化：如果子结点数量设置太大，低能力结点将过载，这将导致整个会话速率下降；如果子结点数量太少，则高能力的结点将不能被充分利用。

现有对满足QoS约束的多播应用的研究多数都致力于构造一棵以单个数据源为根的满足约束的最优多播树，而这并不适合满足QoS约束的任意源的多播应用，并且单个满足约束的最优树不能适应不同应用的QoS要求。

综上所述，目前覆盖多播的研究主要集中处理的问题是如何在现有网络条件下构建一个支持单源多播的高效的数据转发结构，对多源多播的应用情形很少讨论。

发明内容

本发明是针对上述现有技术中存在的缺陷，提出了一种满足能力约束和QoS约束的应用层任意源多播方法，该方法适合具有结点能力约束性能的任意源的多播应用，同时满足动态成员等分布式应用需求，具有完全分布的特点，可以在Internet范围内扩展。它将任意源的多播信息传送到所有结点的期望跳数小，一个多播信息在传输过程中的信息拷贝份数少。同时，它还可以使组成员满足不同数据源发起的不同多播应用的QoS要求。结构简单、维护量小。

本发明的技术方案为：一种满足能力约束和QoS约束的应用层任意源多播方法，所述方法为网络信息的多播过程，首先一个多播信息进入随机转发阶段，从任一源结点随机发往多播组中λn个结点，λ＝Θ(1/log_cn)，n为多播组结点个数，所述结点称之为随机阶段结点；然后多播传送进入环形转发阶段，每个随机阶段结点并行启动一段环形段的传送，将信息顺序发给邻近的节点，直到信息到达一个已接收到该信息的结点为止，每个源结点的多播过程都可自然形成一棵多播树T＝(V_T，E_T)，其中$V_T\subseteq V,$$E_T\subseteq E,$V是结点的集合，表示端系统，E为边的集合，表示端系统间的逻辑信道，一棵多播树T中，是否向结点v转发信息可以增加下列约束以满足QoS要求：

(1)带宽约束：bw_T(v)≥B

(2)延时约束：delay_T(v)≤D

(3)成树次序约束：bw_T(u)≥bw_T(v)，v∈Childof(u)

(4)处理能力约束：capB(v)≥usedB(v)，usedB(v)＝∑_{i∈Childof(v)}bw(i)

其中bw_T(v)、delay_T(v)分别为v当前的带宽和延时，capB(v)为该结点的转发能力带宽，最小带宽约束B，最大延时约束D。

所述随机转发阶段结点的个数在整个多播组结点集合中的覆盖率λ＝Θ(1/log_cn)时，多播的跳数复杂性为0(log_cn)；通信复杂性为n+0(n/log_cn)。

本发明的有益效果在于：本发明满足能力约束和QoS约束的应用层任意源多播方法，解决了许多面向单个数据源设计的多播树不能简单扩展到任意源多播系统中的问题，提出了隐式多播树的概念，不需要额外的对多播树的维护，使其很适合具有多个潜在数据源的多播应用；具有较好的跳数复杂性和通信复杂性，结点的多播覆盖率高；具有结点能力约束性能，具有满足动态QoS约束的性能；本发明结构简单，易于实现。

附图说明

图1是本发明由随机覆盖网和非DHT环所组成的覆盖网络的说明示意图；

图2是本发明两阶段多播算法示意图；

图3是本发明考虑QoS约束时的覆盖网络模型；

图4是本发明结点的邻居结点数对QoS多播性能影响的示意图；

图5是本发明QoS约束多播算法执行过程中多播树生成过程的示意图。

具体实施方式

一个多播信息表示为M(k，id)，其中，M是信息；k是TTL属性，其初始值为K；id是一个全网唯一的标识符，它由源ID(如IP地址)和一个顺序号组成。传递一个多播信息，源结点s首先将M(k，id)发送给c_s个随机邻居。而每个被选中的随机邻居或非DHT环上后继结点将根据算法继续转发，直至满足终止条件，该算法描述如下。显然，该算法计算复杂度为0(c_x)，与泛洪算法具相同的计算复杂度。

/*当结点x接受到多播信息M(k，id)时，将执行以下算法过程*/

/*阶段1*/

   (1)if k＞0 and x尚未向随机邻居发送标识为id的多播信息M then

   (2)   选择c_x个随机邻居

   (3)      for每一个选中的邻居y do

   (4)         发送M(k-1，id)给y

   (5)   if x尚未向successor(x)发送标识为id的多播信息M then

   (6)      发送M(0，id)给successor(x)

            /*successor(x)为结点x在环中的的后继结点*/

   /*阶段2*/

   (7)else if k＝0 and x尚未向successor(x)发送标识为id的多播信息M

then

   (8)发送M(0，id)给successor(x)

   (9)else

(10)丢弃该多播信息

为避免结点对同样信息过量的重复接收，本发明的设计原则是让随机阶段中信息只传递到结点集N中的少量结点上。通过利用随机阶段结点将非DHT环划分为段，这样在环行转发阶段，多播信息在各段并行地以环形方式被转发到段中所有其他结点上。通过证明可以得出：当随机阶段结点的覆盖率λ＝Θ(1/log_cn)时，多播的跳数复杂性为0(log_cn)；通信复杂性为n+0(n/log_cn)。

为了说明本发明的多播方法具有满足QoS约束的特性，我们需定义满足QoS约束的网络模型。针对一个具有N个结点的多播组G，用一个完全有向图来描述G的Overlay网络模型G＝(V，E)，其中V是结点的集合，表示端系统，E为边的集合，表示端系统间的逻辑信道。

对任意结点$\forall v\in V,$定义bw_T(v)、delay_T(v)分别为v当前的带宽和延时，定义capB(v)为该结点的转发能力带宽。对任意有向边e(u，v)∈E，定义其权值为结点u到结点v的单播时延delay(u，v)。

所解决的问题是在这样的一个网络中，对任意多播源结点s，都可以找到一棵多播树T＝(V_T，E_T)，其中$V_T\subseteq V,$$E_T\subseteq E.$使T满足最小带宽约束B，最大延时约束D。同时，考虑多播树中从根结点到子结点的路径带宽单调递减，多播树T还需满足成树次序约束。最后，结点的转发能力带宽是决定该结点在多播树T上具有多少个子结点的因素之一。因此，QoS多播路由问题就是寻找一棵多播树T，使其满足下列约束：

(1)带宽约束：bw_T(v)≥B

(2)延时约束：delay_T(v)≤D

(3)成树次序约束：bw_T(u)≥bw_T(v)，v∈Childof(u)

(4)处理能力约束：capB(v)≥usedB(v)，usedB(v)＝∑_{i∈Childof(v)}bw(i)

如图1所示在随机覆盖网和非DHT环所组成的覆盖网络中，采用本发明所提供的多播方法，同样能满足以上QoS多播约束条件。结点可通过动态的调整来适应不同多播源结点发起的多播应用的QoS约束条件。而结点动态调整所引起的多播树的维护代价，可通过限制每个结点的邻居结点数而大大降低。

为达到这个目标，需针对每个多播组建立一个覆盖网，这样，可以将多播问题转化为在覆盖网范围内的广播问题。针对一个具有n个结点的多播组G，每个结点x∈G能力为c_x，它是x向其转发多播信息的直接子结点的最大个数。而c_x将与x的上载带宽相适应。直观地，当x有大的上载带宽时，它就能在多播树中支持更多的直接子结点。本发明所讨论的覆盖网由两部分组成：其中一部分结点间以随机形式相连，仍是一种树形结构；另一部分是一个非DHT环，它与所有结点以环状方式相连。在非DHT环中，一个结点并不具有一个特定位置，而是可以在环中任意一个位置，环的维护量小。每个结点把其在环中的下一个结点作为其邻居之一，称为后继结点。一个新结点x的加入，首先要知道一个已存在的结点y。x通知y将自己作为y的后继结点，而将y原先的后继结点作为x的后继结点。除了有后继结点作为邻居以外，x还将从结点集中随机选取c_x或更多结点作为邻居。

在此覆盖网络的基础上，本发明提供了一种多播方案，其设计的主要目标是一个多播例程：(1)它能将一个信息从任一源结点发往每一个结点；(2)跳数复杂性是0(log_cn)；(3)通信复杂性为n+0(n/log_cn)；(4)无须创造并维护显示覆盖多播树。主要思路是执行两阶段多播：第一阶段(随机转发阶段)实行随机分布式传送；而第二阶段(环行转发阶段)实行分段环行传送。所定义的每个源的隐式多播树建立在已存在的覆盖网结构中，避免了在覆盖网上的多播树维护问题。这些隐式树大致均衡并且受能力限制，它们针对的每个源都不一样，并且将结点负荷开销分散到尽可能多的覆盖连接上。

随机阶段：源结点将信息通过随机邻居向其他结点发送，这部分传递控制在K跳之内。该阶段将信息传递到结点集的一个子集上，该子集结点随机分布于网络上，并被称为随机阶段结点。如图2(a)、(b)中给出了示例。假设K＝2，源结点s能力是3，结点i，j，l能力分别是2，2和3。这样，在随机阶段，信息被发送到树结构的10个结点上。

环行阶段：每个随机阶段结点将信息发送给其“邻居”，洪泛会造成一些结点收到该信息的多个拷贝，为避免这个问题，本文使用了非DHT环。利用随机阶段结点将环划分成段。如图2(c)所示，每个随机阶段结点负责一个邻近段，它将信息发送给其后继结点，信息进而又被发送给后者的后继结点，…，直到信息到达一个已接收到该信息的结点为止。

两个阶段的信息传送仍然是在一个树结构中，如图2(d)所示，由于树本身遵从底层覆盖网结构，因而不需要额外的维护。环行阶段的分段环行传送保证每个结点只接受到一个信息拷贝。如果K值足够小，随机阶段中的邻居的随机分布会使得信息传送给不同的随机结点的可能性很大，结点接受多于一个拷贝的概率会很小，这也有助于减少通信复杂性。如果K值足够大，会使得更多的随机阶段结点将环划分为小的段，这将有助于在环行阶段减少跳数复杂性。因此，考虑可否选择一个合适的K值，以使跳数复杂性达到优化的0(log_cn)，而且通信复杂性接近n。

经过严格的证明我们得出：当随机阶段结点的覆盖率λ＝Θ(1/log_cn)时，多播的跳数复杂性达到0(log_cn)；通信复杂性达到n+0(n/log_cn)。而K可由公式K＝log_c(λn(c-1)+1)-1计算得出。

考虑到由于K可能不是一个整数，源结点可能通过发送或来初始化基本算法，导致随机阶段树的规模不是λn，从而使算法结果不准确。为了保持树规模在λn左右，随机阶段树应当控制在第0级～第级，只不过第级只有部分结点有多播信息到达。即每个结点按概率p被传送，p可计算得出

这样，源结点s将增加了一个域p的发出，当一个结点x收到一个信息M(0，p，id)时，它将按概率p将该信息转发给其c个随机邻居。改进算法描述如下：

/*当结点x接受到多播信息M(k，p，id)时，将执行以下算法过程*/

/*阶段1*/

(1)if k＞0 and x尚未向随机邻居发送标识为id的多播信息M then

(2)       选择c_x个随机邻居

(3)       for每一个选中的邻居y do

(4)          发送M(k-1，p，id)给y

(5)       if x尚未向successor(x)发送标识为id的多播信息M then

(6)           发送M(0，0，id)给successor(x)

          /*successor(x)为结点x在环中的的后继结点*/

(7)else if k＝0 and p＞0 and x尚未向随机邻居发送标识为id的多播信

息M then

(8)  选择c_x个随机邻居

     for每一个选中的邻居y do

        以概率p选择将M(0，0，id)发送给y

(11)if x尚未向successor(x)发送标识为id的多播信息M then

(12)   发送M(0，0，id)给successor(x)

/*阶段2*/

(13)else if k＝0 and x尚未向successor(x)发送标识为id的多播信息

M then

(14)   发送M(0，0，id)给successor(x)

(15)else

(16)   丢弃该多播信息

在多播会话的过程中，结点可通过判断其邻居结点是否满足QoS约束条件来决定是否向其转发信息。如结点v的邻居结点w，以v作上游结点时可满足上述QoS多播模型中的约束条件(1)-(4)，v则将w作为其下游结点，向其发送信息；如不满足条件，v将不向其发送信息，w将有可能成为其他结点的下游结点。若结点w在一定的时间内未收到多播信息，则运行加入算法，为其重新寻找满足条件的父结点。

为了使每个结点的邻居结点更容易满足QoS约束，而避免结点重新加入的情况频繁发生，结点需限制自己的邻居结点数。如前所述，结点v的转发能力带宽为capB(v)，多播应用的最小带宽约束为B，则结点v的邻居结点数目最多为capB(v)/B。如图4(a)，此时每个邻居结点的平均带宽都为最小约束带宽B，由约束条件可知，该结点和其所有邻居结点均不能再接纳其他结点作为子结点，系统的可扩展性差；而实际中给每个邻居结点分配的带宽不尽相同，若使邻居结点满足最小带宽需求B，其分配带宽往往大于B，这样某些结点就不能作为多播树中v的子结点，需要重新为其寻找父结点，增加了维护代价。因此，需要考虑提高每个邻居结点的平均带宽，即减少v的邻居结点数，当邻居结点的带宽提高到v的分配带宽和转发能力带宽的较小值时达到最大，此时的子结点数为1，如图4(b)所示，v和其邻居结点都具有最大的剩余转发带宽，能容纳更多的结点，但结点的延时太大，很容易不满足延时约束。因此，考虑定义一个参数α，结点的转发能力带宽为cap时，每个结点具有α(cap/B)个邻居结点。实验证明可通过调整α值，使系统的接纳能力强，多播传送时系统的维护代价小。

为此，每个结点需维护α(cap/B)个随机邻居，在向其邻居结点发送信息前，需判断其是否可满足QoS约束条件。满足QoS约束的改进算法如下：

同样，一个多播信息表示为M(k，id)，其中，M是信息；k是TTL属性，其初始值为K；id是一个全网唯一的标识符，它由源ID(如IP地址)和一个顺序号组成。

/*阶段1：多播信息传送*/

/*当结点x接受到多播信息M时，将执行以下算法*/

(1)if k＞0 and x尚未向随机邻居发送标识为id的多播信息M then

(2)        选择α(cap(x)/B)个随机邻居

(3)        for每一个选中的邻居y do

          /*这里，capB(x)-usedB(x)为x的剩余转发能力带宽；B为

          多播最小带宽约束；delay(x)+delay(x，y)为y的延时参数；

          delay为多播最大延时约束*/

(4)      if(capB(x)-usedB(x))＞B and(delay(x)+delay(x，y))＜delay

then

(5)               为y分配带宽，发送M(k-1，id)给y

               /*y获得当前的带宽、延时等QoS参数信息*/

(6)                y.flag＝true

                 /*flag为true表示y已收到多播信息*/

(7)          if x尚未向successor(x)发送标识为id的多播信息M then

(8)              if   (capB(x)-usedB(x))＞B and (delay(x)+delay(x，

successor(x)))＜delay then

(9)             发送M(0，id)给successor(x)

(10)else if k＝0 and x尚未向successor(x)发送标识为id的多播信息M

then

(11)    if(capB(x)-usedB(x))＞B and(delay(x)+delay(x，successor

(x)))＜delay then

(12)            发送M(0，id)给successor(x)

(13)else

(14)       丢弃该多播信息

/*阶段2：对一定时间内未收到多播信息的结点执行加入算法重新寻找上游

结点*/

(15)for每一个flag为false的结点v do

      /*flag为false表示结点v未收到多播信息*/

(16)     v执行加入算法加入多播树

以图3的网络模型为例，图5(a)为不同源结点生成的多播树。图5(b)所示若结点2的邻居结点3或4带宽分配过大导致2的剩余转发带宽不能满足另一个邻居结点的带宽需求时，该结点还会成为另一个结点的下游结点。

在多播会话的过程中，当新结点欲加入多播组时，它将向多播源结点发送请求报文。源结点收到请求报文后，向组成员多播查询信息，查询满足条件的结点，这些结点将组成候选父结点集合发送给新结点。满足候选父结点的条件如下：(1)为了使新加入的结点满足最小带宽约束，父结点的剩余转发带宽须大于多播应用的最小约束带宽B。(2)因为结点的转发能力带宽cap是动态变化的，结点的邻居结点数有可能会小于α(cap/B)。为了使网络中的结点均保持α(cap/B)个邻居结点，新结点加入时应首先选择当前邻居结点小于α(cap/B)的结点作为父结点。新结点在收到候选父结点集合后则逐个探测与它们之间的QoS参数，选择满足带宽约束和延时约束，且单播时延最小的结点作为其父结点。选择了父结点后，则向其发送加入报文Join。父结点在收到加入报文后，将新结点加入邻居结点列表，并向新结点发送回应报文JoinAck。若多播组中找不到合适的父结点，新结点会收到FailAck报文，表示加入失败。在找到了父结点后，为新结点分配带宽，若其还未获得邻居结点，则会请求一个多播源结点帮助以找到自己的α(cap/B)个随机邻居。

分析和实验证明，在结点转发能力带宽较小的情况下，调整α的值能大大减少flag为false的结点数，使多播信息的传送在第一阶段已基本完成，维护代价小。而在结点的转发能力带宽较大的情况下，flag为flase的结点数目基本为零。