基于可用带宽满足时延和时延差别约束的实时多播路由算法

Real-time Multicast Routing Algorithms Based on Available Bandwidth andBounds of Delay and Delay Variation

实时多播路由中具有可加性的代价 (Cost)不能确切反映网络本质特性 ,尤其不能反映路径带宽的凹性(Concave) .已有基于代价的算法不能很好适应多播应用 ,需要新的模型和算法 .本文采用可用带宽代替代价作为主要度量 ,并满足实时多播中二个重要约束度量 :时延和时延差别 .同时基于此三个度量 ,本文提出二种新的具有多项式复杂性的实时多播路由算法并比较其性能 .新算法通过分析得到每路径时延和二约束之间的关系 ,有效降低涉及时延和时延差别此类问题的复杂性 .新算法采用度量反映实时多播本质特性而具有实际推广性 .

Novel models and algorithms for real-time multicast routing should be presented because the additive metric of cost cannot manifest the essential characteristics of real-world network, especially for the concave bandwidth. This paper substitutes available bandwidth for cost as the primary metric and considers the other two significant constraints in real-time multicast: delay and delay variation. Based on these three metrics in the mean time, two novel real-time multicast routing algorithms with polynomial time complexity are proposed. The comparison of performance between these two algorithms is given as well. The novel algorithms effectively reduce the complexity of those algorithms related to delay and delay variation by analyzing and obtaining the relationship between per path delay and two tolerances. Accounting for adopting practical metrics, the novel algorithms are quote worthy to be recommended.