一种覆盖网络环境下的多播路由树前向式重构恢复方法

摘要

本发明涉及网络通信技术领域，尤其涉及一种覆盖网络环境下的多播路由树前向式重构恢复方法。本发明提供的方法是一种在覆盖网络中，通过节点备份保护机制重构恢复失效多播树通信路由的容灾机制，针对前向式覆盖多播路由树恢复方法中依赖备份所导致的恢复效率低的问题，在全局搜索备份父节点策略中，引入了目标节点与备份节点之间的备份有效性的检测方法，限制备份父节点与受保护的目标节点之间存在依赖关系的情况，从而提高失效覆盖网络多播路由树恢复的成功概率。本发明能够在降低很小幅度的恢复时间效率的情况，较大幅度的提升恢复成功率，有利于构建具有可靠自恢复能力的覆盖网络多播树。

权利要求

1.一种覆盖网络环境下的多播路由树前向式重构恢复方法，其特征在于，包括以下步骤：

1)多播树生成过程中备份父节点的预计算步骤，该步骤包括以下子步骤：①新节点N加入多播树T时，首先向多播树的根节点R发送join请求；

②根节点R会向节点N返回路由表RT和备份父节点列表PPL，RT记录了任意树节点I，I∈T的状态信息，PPL表记录了所有可用备选父节点K，K∈T的信息；

③节点N向RT中所有可用度＞1的节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用度＞1的节点的RTT值；

④N选择其中节点P为其多播树上的父节点，其中RTT(N，P)与T(P)的延迟时间总和为所有返回ACK消息节点中的最小值；

⑤RT表中D(P)＝D(P)-1

⑥节点N向PPL表中所有可用备选父节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用备选父节点的RTT值；

⑦首先选择具有最小RTT值的备份父节点，检测其有效性，判断是否是节点P，如果是则按照RTT值从小到大的顺序选择下一个备份父节点进行检测，如果不是则继续；

⑧设N选择了节点V为备份父节点，则在PPL表中BD(V)＝BD(V)-1，如果BD(V)＝0，则将节点V从PPL表中移除；

2)多播树调整过程中备份父节点的预计算步骤，该步骤进一步包括以下子步骤：①设节点N重新计算其备份父节点，首先向多播树的根节点R发送request请求；

②根节点R会向节点N返回备份父节点列表PPL；

③节点N向PPL表中所有可用备选父节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用备选父节点的RTT值；

④节点N依照RTT值从小到大的顺序依次检测备份父节点是否符合要求；

⑤设节点N选择了节点V为待选备份父节点，N向V发送check消息；

⑥V接到check消息后向其父节点转发check消息，如果N接到check消息，则检测未通过，表明V与N存在依赖关系，V不能成为N的备份父节点，回到步骤④；如果N没有接到check消息，则沿组播路径继续向上级父节点转发check消息，并检测N是否接受到check消息，如果收到则检测不通过，回到步骤④，否则直到根节点R收到check消息；

⑦V接到check消息后还要向V的备份父节点转发check消息，如果N接到check消息，则表明V与N存在依赖关系，V不能成为N的备份父节点，回到步骤④；

⑧V的备份父节点接到check消息后，如果依赖关系检测通过的话，则沿组播路径继续向上级父节点转发check消息，并检测N是否接受到check消息，如果收到则检测不通过，回到步骤④，否则直到根节点R收到check消息；

⑨节点N选择RTT值最小，且检测通过的节点为其新的备份父节点，其在PPL表中的BD值减1，如果其BD值为0，则将该节点从PPL表中移除；

3)异常情况下多播路由树快速恢复过程步骤，该步骤进一步包括以下子步骤：①当多播路由树某节点p退出群组后，由其子节点c1，c2，c3……发起重构恢复操作；

②子节点ci向其备份父节点vi发送挂载请求connect消息；

③如果vi同意其挂载请求，则回复ok消息，否则发送refuse消息；

④收到ok消息的子节点vi，则开始建立多播会话，结束重建过程；

⑤收到refuse消息的子节点，则重新向根节点R发送join消息，请求重新加入多播群组，此时按照新节点加入多播树的流程执行。

说明书

一种覆盖网络环境下的多播路由树前向式重构恢复方法

技术领域

[0001] 本发明涉及网络通信技术领域，尤其涉及一种覆盖网络环境下的多播路由树前向式重构恢复方法。

背景技术

[0002] 多播(Multicast，又称为组播)技术是一种可控制的单点对多点的数据路由传输技术，数据源发送一个数据拷贝，报文在网络传输过程中可根据需要自动复制，转发给多个接收者。

[0003] 覆盖网络是一种以提供服务为目的铺设在应用层的虚拟网络，其核心思想就是由端系统(主机)而不是核心路由器来实现通信的所有功能。与IP网络相比，其最大的优势在于无需改变下层网络基础设施，易于部署。

[0004] 在覆盖网络环境下，多播路由的目标是为了寻找最优路径以进行信息共享和分发，提高网络资源利用率及服务质量。其中多播树路由技术是覆盖多播路由研究方向的重要分支，其基本原理是在覆盖网络环境下，依据应用提出的QoS优化目标(一般包括节点度、传输代价、路径延迟等)，将参与多播会话的节点陆续加入通信群组，形成以源节点为根的树状分发网络，每个节点既充当接收端也充当转发的服务端，这样就能够大大节省带宽，提高网络资源的利用率。然而目前的覆盖网络多播树路由技术对于承载大规模多媒体群组通信应用来说，在效率和稳定性方面仍存在一些问题，其大规模应用面临着局部灾难导致整体分发质量下降的问题。

[0005] 端主机由于业务的需要或故障突发随时可能退出群组，如果退出的节点是参与分发的节点则会直接造成下游所有节点正常通信的中断。然而对于对传输可靠性要求高的多媒体流业务来说，无论是传输质量的下降还是连接中断异常都会极大影响其分发质量，因此如何提高覆盖多播路由的容灾容错能力，使其能够应对各种复杂环境变化引发的服务异常，是覆盖多播树路由技术应用的重要挑战之一。

[0006] 覆盖多播树重构算法主要研究多播树在发生服务通信中断的情况下，如何通过路由重建快速恢复服务的技术。目前，树重构算法主要分为前向式和后向式两种。前向式树重构(参见文献1)是在树异常发生之前就进行预测，并提前制定备份路由策略，在灾难发生之前快速调整。后向式树重构则是在灾难发生时，临时进行树填补。两者相比较，前向式能够在灾难发生时快速调整，甚至可消除灾难，比后向式反应时间迅速，但是前向式树重构需要预先进行备份查找和建立一些备份信息，给树带来额外的开销。因此，人们在前向式树重构算法研究中，希望达到代价与性能的双赢。

[0007] 覆盖多播树重构路由算法研究中常用的前向式算法(参见文献2)通过备份父节点选择模型提供了一种预计算保护策略，该模型的原理为每个子节点在多播树内预先选出能保证最快恢复的备份父节点，一旦某个节点发生故障，退出多播树，其子节点可直接连接备份父节点，从而快速恢复树路由。但是目前的备份节点选择模型(参见文献3)未考虑备份父节点与受保护的目标节点之间可能存在的依赖备份关系，即备份父节点与目标节点存在通信依赖关系，或备份父节点反而受到目标节点及其子节点的备份保护，这种情况会直接导致备份恢复失败，使在树节点失效概率高的情况下，恢复成功率大大降低，如附图1-2所示，图1中D、E之间存在互为备份父节点的关系，一旦A、B节点同时失效，则D接入E，E接入D，出现以D、E为根的子树均与原多播树分离的情况；同样的道理，图2中，D以E为备份父节点，而E以D的子节点H为备份父节点，一旦A、B同时失效，则D接入E，E接入H，仍然出现以D、E为根的子树均与原多播树分离的情况，从而导致备份恢复失败。

[0008] 文献1：Kusumoto T，Kunichika Y，Katto J，Okubo S，“Tree-Based application layer multicast using proactive route maintenance and its implementation”，In：Proceedings of the ACM P2PMMS，Singapore，2005：pp.49-58.

[0009] 文 献 2：Zongming Fei，and Mengkun Yang，“A Proactive Tree Recovery Mechanism for Resilient Overlay Network”，IEEE/ACM Transactions on Networking，Vol.15，No.1，February 2007：173-186.

[0010] 文献3：Jin-Han Jeon，Seung-chul Son，Ji-Seung Nam，“Overlay multicast tree recovery scheme using a proactive approach”，Computer Communications，Vol.31，2008：pp.3163-3168.

发明内容

[0011] 针对上述存在的技术问题，本发明的目的是提供一种覆盖网络环境下的多播路由树前向式重构恢复方法，该方法引入目标节点与备份节点之间的备份有效性检测方法，可解决现有备份节点选择模型存在的依赖备份问题，提高多播树的恢复成功率。

[0012] 为达到上述目的，本发明采用如下的技术方案：

[0013] 1)多播树生成过程中备份父节点的预计算步骤，该步骤包括以下子步骤：

[0014] ①新节点N加入多播树T时，首先向多播树的根节点R发送join请求；

[0015] ②根节点R会向节点N返回路由表RT和备份父节点列表PPL，RT记录了任意树节点I，I∈T的状态信息，PPL表记录了所有可用备选父节点K，K∈T的信息；

[0016] ③节点N向RT中所有可用度＞1的节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用度＞1的节点的RTT值；

[0017] ④N选择其中节点P为其多播树上的父节点，其中RTT(N，P)与T(P)的延迟时间总和为所有返回ACK消息节点中的最小值；

[0018] ⑤RT表中D(P)＝D(P)-1

[0019] ⑥节点N向PPL表中所有可用备选父节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用备选父节点的RTT值；

[0020] ⑦首先选择具有最小RTT值的备份父节点，检测其有效性，判断是否是节点P，如果是则按照RTT值从小到大的顺序选择下一个备份父节点进行检测，如果不是则继续；

[0021] ⑧设N选择了节点V为备份父节点，则在PPL表中BD(V)＝BD(V)-1，如果BD(V)＝0，则将节点V从PPL表中移除；

[0022] 2)多播树调整过程中备份父节点的预计算步骤，该步骤进一步包括以下子步骤：

[0023] ①设节点N重新计算其备份父节点，首先向多播树的根节点R发送request请求；

[0024] ②根节点R会向节点N返回备份父节点列表PPL；

[0025] ③节点N向PPL表中所有可用备选父节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用备选父节点的RTT值；

[0026] ④节点N依照RTT值从小到大的顺序依次检测备份父节点是否符合要求；

[0027] ⑤设节点N选择了节点V为待选备份父节点，N向V发送check消息；

[0028] ⑥V接到check消息后向其父节点转发check消息，如果N接到check消息，则检测未通过，表明V与N存在依赖关系，V不能成为N的备份父节点，回到步骤④；如果N没有接到check消息，则沿组播路径继续向上级父节点转发check消息，并检测N是否接受到check消息，如果收到则检测不通过，回到步骤④，否则直到根节点R收到check消息；

[0029] ⑦V接到check消息后还要向V的备份父节点转发check消息，如果N接到check消息，则表明V与N存在依赖关系，V不能成为N的备份父节点，回到步骤④；

[0030] ⑧V的备份父节点接到check消息后，如果依赖关系检测通过的话，则沿组播路径继续向上级父节点转发check消息，并检测N是否接受到check消息，如果收到则检测不通过，回到步骤④，否则直到根节点R收到check消息；

[0031] ⑨节点N选择RTT值最小，且检测通过的节点为其新的备份父节点，其在PPL表中的BD值减1，如果其BD值为0，则将该节点从PPL表中移除；

[0032] 3)异常情况下多播路由树快速恢复过程步骤，该步骤进一步包括以下子步骤：

[0033] ①当多播路由树某节点p退出群组后，由其子节点c1，c2，c3……发起重构恢复操作；

[0034] ②子节点ci向其备份父节点vi发送挂载请求connect消息；

[0035] ③如果vi同意其挂载请求，则回复ok消息，否则发送refuse消息；

[0036] ④收到ok消息的子节点vi，则开始建立多播会话，结束重建过程；

[0037] ⑤收到refuse消息的子节点，则重新向根节点R发送join消息，请求重新加入多播群组，此时按照新节点加入多播树的流程执行。

[0038] 本发明具有以下优点和积极效果：

[0039] 1)本发明将有助于多媒体群组通信应用中的服务中断恢复策略，适用于解决大规模网络直播服务应用中的容灾恢复问题；

[0040] 2)本发明相比文献3的方法，能够在降低很小幅度的恢复时间效率的情况，较大幅度的提升恢复成功率，有利于构建具有可靠自恢复能力的覆盖网络多播树。

附图说明

[0041] 图1是目标节点与其备份父节点存在依赖关系导致恢复失败示意图。

[0042] 图2是目标节点与其备份父节点存在依赖关系导致恢复失败示意图。

[0043] 图3是覆盖多播路由树生成过程中的备份父节点预计算过程的流程图。

[0044] 图4是覆盖多播路由树调整过程中的备份父节点预计算过程流程图。

具体实施方式

[0045] 本发明提供的覆盖网络环境下的多播路由树前向式重构恢复方法，将有助于多媒体群组通信应用中的服务中断恢复策略，适用于解决大规模网络直播服务应用中的容灾恢复问题。

[0046] 在目前的网络通信服务众，多媒体群组通信应用通常是大规模的、持续的向各个成员分发多媒体数据，然而由于各种客观因素造成成员节点异常退出多播组、局部链路发生故障或者质量下滑，导致一部分成员不能继续正常的接收服务。例如在观看大型奥运网络直播时，观众连接的某个直播接入点停止服务时，观众不得不手动重新选择其他直播接入点等待缓冲，而往往因此错过了精彩瞬间，观众容忍这种故障是很脆弱的。

[0047] 本发明提供的前向式重构恢复方法能够预先为每个下游接入点提供预留备份接入点，一旦上游接入点停止服务，下游接入点能够快速启动备份接入，从而使得观众在观看大型奥运网络直播时感觉不到服务中断带来的缓冲等待。

[0048] 下面首先介绍基于本发明的定义和理论：

[0049] 定义1节点服务度和备份度：

[0050] 设定Degree(n)代表节点n在一个多播会话T中的节点度，表示节点n可用于分发的孩子节点数目的最大值。每个节点的节点度有服务度D(n)和备份度BD(n)。备份度用于预留备份路由或替代路由，服务度表示可服务的孩子节点数目。节点n的服务度和备份度应小于或等于Degree(n)，其间产生的差值则是备份度，即Degree(n)＝D(n)+BD(n)，其中D(n)代表节点n的服务度，BD(n)代表n的备份度。

[0051] 定义2多播树路由RT表：记录了多播树的分发路由信息，具体如下：

[0052]数据项 数据项定义描述
Node id 节点的唯一标识
A(id) 该节点的网络地址
D(id) 该节点的服务可用度
T(id) 根节点到该节点的分发延时
Parent(id) 该节点的父节点id

[0053] 定义3多播树可用备份父节点PPL表：记录了多播树的分发路由信息，具体如下：

[0054]数据项 数据项定义描述
Node id 节点的唯一标识
A(id) 该节点的网络地址
BD(id) 该节点的备份可用度

[0055] 本发明提供一种覆盖网络环境下的多播路由树前向式重构恢复方法，具体包括以下步骤，如图3、4所示：

[0056] 1、多播树生成过程中备份父节点的预计算步骤：在前向式覆盖多播树的构建过程，针对每一个新加入多播树的节点都需要计算出其父节点，包括以下步骤：

[0057] 1)新节点N加入多播树T时，首先向多播树的根节点R发送join请求；

[0058] 2)根节点R会向节点N返回RT(RoutingTable，路由表)和PPL(Potential Parent List，备份父节点列表)，RT记录了任意树节点I，I∈T的状态信息(地址A(I)、可用度D(I)、R到该节点的分发延时T(I))，PPL表记录了所有可用备选父节点K，K∈T的信息(地址A(K)，备份度BD(K))；

[0059] 3)节点N向RT中所有可用度＞1的节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用度＞1的节点的RTT(Round Trip Time)值；

[0060] 4)N选择其中节点P为其多播树上的父节点，其中RTT(N，P)与T(P)的延迟时间总和为所有返回ACK消息节点中的最小值；

[0061] 5)RT表中D(P)＝D(P)-1

[0062] 6)节点N向PPL表中所有可用备选父节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用备选父节点的RTT(Round Trip Time)值；

[0063] 7)首先选择具有最小RTT值的备份父节点，检测其有效性，判断是否是节点P，如果是则按照RTT值从小到大的顺序选择下一个备份父节点进行检测，如果不是则继续；

[0064] 8)设N选择了节点V为备份父节点，则在PPL表中BD(V)＝BD(V)-1，如果BD(V)＝0，则将节点V从PPL表中移除；

[0065] 2、多播树调整过程中备份父节点的预计算步骤：由于覆盖多播树在会话周期内会因为节点的加入退出而造成树形态的变化，因此在多播树发生重构调整后，部分的树节点是需要重新计算其备份父节点的，但这时必需要检测节点N和备份父节点间是否存在循环依赖备份情况，以免出现无效备份，包括以下子步骤：

[0066] 1)设节点N重新计算其备份父节点，首先向多播树的根节点R发送request请求；

[0067] 2)根节点R会向节点N返回PPL(Potential Parent List，备份父节点列表)；

[0068] 3)节点N向PPL表中所有可用备选父节点发送Ping消息，这些节点接到Ping消息后将返回ACK消息，节点N根据ACK中返回的时戳信息，计算出节点N到每个可用备选父节点的RTT(Round Trip Time)值；

[0069] 4)节点N依照RTT值从小到大的顺序依次检测备份父节点是否符合要求；

[0070] 5)设节点N选择了节点V为待选备份父节点，N向V发送check消息；

[0071] 6)V接到check消息后向其父节点转发check消息，如果N接到check消息，则检测未通过，表明V与N存在依赖关系，V不能成为N的备份父节点，回到步骤4；如果N没有接到check消息，则沿组播路径继续向上级父节点转发check消息，并检测N是否接受到check消息，如果收到则检测不通过，回到步骤4，否则直到根节点R收到check消息；

[0072] 7)V接到check消息后还要向V的备份父节点转发check消息，如果N接到check消息，则表明V与N存在依赖关系，V不能成为N的备份父节点，回到步骤4；

[0073] 8)V的备份父节点接到check消息后，如果依赖关系检测通过的话，则沿组播路径继续向上级父节点转发check消息，并检测N是否接受到check消息，如果收到则检测不通过，回到步骤4，否则直到根节点R收到check消息；

[0074] 9)节点N选择RTT值最小，且检测通过的节点为其新的备份父节点，其在PPL表中的BD值减1，如果其BD值为0，则将该节点从PPL表中移除；

[0075] 3、异常情况下多播路由树快速恢复过程步骤：根据以上备份父节点的预计算方法，可保证当异常情况下多播树节点退出群组后，多播树能够迅速恢复被影响的通信，包括以下子步骤：

[0076] 1)当多播路由树某节点p退出群组后，由其子节点c1，c2，c3……发起重构恢复操作；

[0077] 2)子节点ci向其备份父节点vi发送挂载请求connect消息；

[0078] 3)如果vi同意其挂载请求，则回复ok消息，否则发送refuse消息；

[0079] 4)收到ok消息的子节点vi，则开始建立多播会话，结束重建过程；

[0080] 5)收到refuse消息的子节点，则重新向根节点R发送join消息，请求重新加入多播群组，此时按照新节点加入多播树的流程执行。

[0081] 以上实施例仅供说明本发明之用，而非对本发明的限制，有关技术领域的技术人员，在不脱离本发明的精神和范围的情况下，还可以作出各种变换或变型，因此所有等同的技术方案，都落入本发明的保护范围。