基于最小生成树和贪婪算法的动态时延约束的多播路由的方法

摘要

本发明公开了一种基于最小生成树和贪婪算法的动态时延约束的多播路由方法：当网络节点v在动态多播树T上，则将网络节点v标记为多播成员；当网络节点v不在动态多播树T上，计算最小生成树路径、最小费用路径和最小时延路径到已有的多播树的费用，取其中满足时延要求且增加费用最小的一条连到已有的多播树，从而使网络节点v加到动态多播树T上，在将网络节点v标记为多播成员；当网络节点v要离开动态多播树T时，采用贪婪算法使节点v离开动态多播树T。该方法的执行时间与经典的最小路径费用算法MPH相当。DGA的费用比MPH算法高4％－5％左右，因此它是一种低复杂度的时延约束的低费用多播路由方法，在多播节点密度较大时显示了优越性，且它的平均无效度在其他情况下也在可接受的范围之内。

主权项

1、一种基于最小生成树和贪婪算法的动态时延约束的多播路由方法，它包括网络节点v，动态多播树T；其特征是：当网络节点v在动态多播树T上，则将网络节点v标记为多播成员；当网络节点v不在动态多播树T上，计算最小生成树路径、最小费用路径和最小时延路径到已有的多播树的费用，取其中满足时延要求且增加费用最小的一条连到已有的多播树，从而使网络节点v加到动态多播树T上，在将网络节点v标记为多播成员；当网络节点v要离开动态多播树T时，采用贪婪算法使节点v离开动态多播树T。