基于多项服务质量的组播路由算法
发布时间:2007/8/29 0:00:00 访问次数:452
摘 要： 多点组播是指一个源点传送信息到多个目的节点，它是网络支持多媒体业务的关键技术之一。以服务质量（QoS）指标中的带宽和时延为优化选路准则，提出了一种受限的组播路由算法，仿真结果证明了该算法的有效性。
关键词： 网络 组播 路由
通信网络在进入90年代后，向着综合业务的方向发展。在传统的数据网络中，路由所需考虑的仅是可连接性[1]，路由算法在寻找最优（短）路径时采用单一的指标，如跳数或时延。新出现的多媒体通信带来了多点组播的需求，即未来的计算机网络应该能够提供例如电视会议、视频点播等具有点对多点的业务要求。而这种网络应该支持范围广泛的服务质量（QoS）需求，确定路由需要相当复杂的模型来描述网络，即路由的优化指标要包括时延、带宽、丢失率等。
近年来，各国学者开始在这方面探索，提出了一些快速有效的算法。如：基于最短路径的Dijkstra算法[2]，即计算源点到各目的点的最短路径；另一类是求最小网络代价（NC）的应用斯坦利（Steiner）树路由算法[3]，即计算组播树（Multicast tree)，使其在任意一对源和目的节点之间都存在通路，并使其代价（cost）最小。
本文使用改进的受限Steiner树路由算法，构造树型路由结构来实现多点通信（Multicast或MC)。这是由于基于树实现有效ＭＣ路由具有以下两个优点：（１）分组以并行方式沿着树枝发送到不同的信宿；（２）网络中需要传送的复制分组最小，而且分组的复制只是在树叉处进行。在QoS的参数中，本文选取最小化占用链路总带宽和满足端到端的时延限制为优化准则。
１ 受限组播路由的算法
１．１ 网络模型
一个网络可以表示为图G（V，E）；其中Ｖ是顶点的集合，包括ｎ个顶点；Ｅ是边的集合，包括ｍ条边。每条边ｅ∈E具有两个参数：C（e）和D（e），C（e）是边e上的正实数代价函数，D（e）是e上的正整数时延函数。在给定信源Ｓ和信宿集合Ｄ条件下，给定允许延迟极限Δ，构造根为Ｓ，覆盖所有信宿节点的受限Steiner树，满足条件，树上路径（i，j）的延迟小于Δ，即：如果P（i,j）是树上从i到j的路径，那么对D满足：
１．２ 算法实现机理
由于网络中的Steiner问题属于图论中的ＮＰ完备问题[4]，即，一般地说，最优算法无法在多项式时间内完成。因此，用启发式算法可降低算法难度，而在性能上逼近理论算法。由于构造最小生成树（MST）相对简单，因此常用的是MST启发式算法。
本文通过改进Prim算法[2]来求解MST问题。Prim算法的基本思想为：假定G＝（V，E）是连通图，T是G上MST中边的集合。算法从U＝{S}（S为源点），T＝Φ开始，重复执行下列操作：在所有u∈Uｖ∈{V－U}的边（u,v)∈E中找一条权值最小的边（u0,v0)并入集合Ｔ，同时u0并入U，直到U＝V为止，则T为G的MST。
改进算法的基本思想是：首先利用Dijkstra第k最短路径算法，计算从源节点到目的节点以时延为优化准则的路径，并将所求的路径中最大的时延与Δ比较，若该值比Δ大则表明限制条件太苛刻，可令Δ等于该值。然后以cost最小为首要优化目标，用Prim算法求出图G的MST树。用Prim算法每生成一条边（i,j）时，就计算由Ｓ到该边的累计时延,若≤Δ，则用Prim算法继续寻找下一条边。否则令该边对应的cost(i,j)为∞，并且将j(i∈U,j∈{V－U}仍保留在原来集合中。当用Prim算法完成一次全局搜索后，再对那些仍保留在Ｖ－Ｕ集合中的点重新进行全局搜索（除开前次让cost(i,j)为∞的ｉ点外），寻找符合时延条件的新边。当U中已包含全部组播目标节点Di后，算法结束。
摘 要： 多点组播是指一个源点传送信息到多个目的节点，它是网络支持多媒体业务的关键技术之一。以服务质量（QoS）指标中的带宽和时延为优化选路准则，提出了一种受限的组播路由算法，仿真结果证明了该算法的有效性。
关键词： 网络 组播 路由
通信网络在进入90年代后，向着综合业务的方向发展。在传统的数据网络中，路由所需考虑的仅是可连接性[1]，路由算法在寻找最优（短）路径时采用单一的指标，如跳数或时延。新出现的多媒体通信带来了多点组播的需求，即未来的计算机网络应该能够提供例如电视会议、视频点播等具有点对多点的业务要求。而这种网络应该支持范围广泛的服务质量（QoS）需求，确定路由需要相当复杂的模型来描述网络，即路由的优化指标要包括时延、带宽、丢失率等。
近年来，各国学者开始在这方面探索，提出了一些快速有效的算法。如：基于最短路径的Dijkstra算法[2]，即计算源点到各目的点的最短路径；另一类是求最小网络代价（NC）的应用斯坦利（Steiner）树路由算法[3]，即计算组播树（Multicast tree)，使其在任意一对源和目的节点之间都存在通路，并使其代价（cost）最小。
本文使用改进的受限Steiner树路由算法，构造树型路由结构来实现多点通信（Multicast或MC)。这是由于基于树实现有效ＭＣ路由具有以下两个优点：（１）分组以并行方式沿着树枝发送到不同的信宿；（２）网络中需要传送的复制分组最小，而且分组的复制只是在树叉处进行。在QoS的参数中，本文选取最小化占用链路总带宽和满足端到端的时延限制为优化准则。
１ 受限组播路由的算法
１．１ 网络模型
一个网络可以表示为图G（V，E）；其中Ｖ是顶点的集合，包括ｎ个顶点；Ｅ是边的集合，包括ｍ条边。每条边ｅ∈E具有两个参数：C（e）和D（e），C（e）是边e上的正实数代价函数，D（e）是e上的正整数时延函数。在给定信源Ｓ和信宿集合Ｄ条件下，给定允许延迟极限Δ，构造根为Ｓ，覆盖所有信宿节点的受限Steiner树，满足条件，树上路径（i，j）的延迟小于Δ，即：如果P（i,j）是树上从i到j的路径，那么对D满足：
１．２ 算法实现机理
由于网络中的Steiner问题属于图论中的ＮＰ完备问题[4]，即，一般地说，最优算法无法在多项式时间内完成。因此，用启发式算法可降低算法难度，而在性能上逼近理论算法。由于构造最小生成树（MST）相对简单，因此常用的是MST启发式算法。
本文通过改进Prim算法[2]来求解MST问题。Prim算法的基本思想为：假定G＝（V，E）是连通图，T是G上MST中边的集合。算法从U＝{S}（S为源点），T＝Φ开始，重复执行下列操作：在所有u∈Uｖ∈{V－U}的边（u,v)∈E中找一条权值最小的边（u0,v0)并入集合Ｔ，同时u0并入U，直到U＝V为止，则T为G的MST。
改进算法的基本思想是：首先利用Dijkstra第k最短路径算法，计算从源节点到目的节点以时延为优化准则的路径，并将所求的路径中最大的时延与Δ比较，若该值比Δ大则表明限制条件太苛刻，可令Δ等于该值。然后以cost最小为首要优化目标，用Prim算法求出图G的MST树。用Prim算法每生成一条边（i,j）时，就计算由Ｓ到该边的累计时延,若≤Δ，则用Prim算法继续寻找下一条边。否则令该边对应的cost(i,j)为∞，并且将j(i∈U,j∈{V－U}仍保留在原来集合中。当用Prim算法完成一次全局搜索后，再对那些仍保留在Ｖ－Ｕ集合中的点重新进行全局搜索（除开前次让cost(i,j)为∞的ｉ点外），寻找符合时延条件的新边。当U中已包含全部组播目标节点Di后，算法结束。
相关技术资料- 5-21带控制引脚锂电保护芯片 SC5617E
- 5-21全新互连技术—NVLink Fusion
- 5-21最新一代GB300 AI系统技术参数设计
- 5-21Data Center Building Block Soluti
- 5-21新品4U前端I/O NVIDIA HGX™B200 8
- 5-21DLC-2第二代直接液冷技术（Direct Liqu
- 5-20最新一代低功耗无线射频芯片OM6629系列方案
- 5-20新一代 Zen 6 EPYC 处理器 Venice
- 5-20Immortalis-G925 GPU工作原理
- 5-20Hopper架构H20芯片应用前景分析
- 5-20传感器、芯片和算力平台、通信模块、执行机构名词解释
- 5-20Automatic Emergency Braking自动紧急制动
- 相关IC型号
公网安备44030402000607
