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

摘要

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

主权项

一种覆盖网络环境下的多播路由树前向式重构恢复方法，其特征在于，包括以下步骤：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消息，请求重新加入多播群组，此时按照新节点加入多播树的流程执行。