面向MSVMT问题的两阶段分布式应用层组播方法

摘要

本发明涉及面向MSVMT问题的两阶段分布式应用层组播方法。采用保持负载平衡的节点加入方法，采用能选择综合权衡延迟和出度的PPAF启发式，采用基于三角法则的主干拓扑构建方法的树优先分布式应用层组播构建方法。

主权项

1、面向MSVMT问题的两阶段分布式应用层组播方法，其特征在于该方法包括如下三个分布式步骤：1)节点加入：分为两个阶段，即对应视频直播开始之前的初始构建阶段ICP(Initial Construction Phase)和开始之后的正式构建阶段FCP(FormalConstruction Phase)；a)ICP阶段：把在视频直播开始之前请求加入覆盖网络的节点合理地组织起来；i)初始主干拓扑构建子阶段：请求节点首先获取可选节点集合，这通过借助RP即RendezvousPoint方法来获取一个固定大小的可选节点集合实现，这个集合中的节点已经加入到组播树中，之后不断利用绝对三角法则寻找前后向邻居节点，最终形成以源节点为中心的类似星型的有向图的主干拓扑；ii)初始数据传输拓扑构建子阶段：在视频直播即将开始之前的某时刻t，源节点启动初始数据传输拓扑构建子阶段，开始从以源节点为根节点的组播树上由上至下地选择基于PPAF启发式最优、且满足MSVMT问题约束条件的子节点加入到组播树中；b)FCP阶段：在视频直播开始之后，请求节点一旦找到一个符合相对三角法则的邻居节点，就执行加入操作，同时加入到主干拓扑和数据传输拓扑中；i)请求节点首先获取可选节点集合，可同样借助RP方法，并能够通过Gossip协议获得更多邻居节点加入到可选节点集合，之后，请求节点不断在可选节点集合中寻找符合相对三角法则的邻居节点，一旦找到一个邻居节点，就准备加入到覆盖网络中；ii)请求节点基于相对三角法则中它与找到的邻居节点的前后向邻居关系，并基于PPAF启发式的最优选择，决定请求节点加入到主干拓扑和数据传输拓扑的方式；2)节点自优化：请求节点加入到组播树后，不断根据相对三角法则寻找可选前向节点，找到一定数量的可选前向节点后，如果到其中某个节点的PPAF值大于到当前父节点的PPAF值且满足MSVMT问题的约束，就进行父节点替换操作；3)节点退出：分别处理节点主动退出和异常退出的情况；a)主动退出：发送退出消息给父节点，发送重选父节点消息给它的每个儿子节点，退出组播树；b)异常退出：所有的父子节点间会采用心跳协议(heart-beating)，当任何儿子节点察觉到父节点失效时，会重新执行节点加入操作，当父节点察觉到某子节点失效时，它把该子节点从子节点集合中删除。