基于拉格朗日松弛法的受限低代价组播路由算法

摘要

目前Internet中现有的传输模式仍为单一的尽力而为(best-effort)型服务，无法满足飞速发展的多媒体应用和用户对网络传输质量的更高要求。在这种情况下，以提高网络资源的利用率、为用户提供更高服务质量为目标的QoS控制技术应运而生，QoS组播路由技术则是网络多媒体信息传输的关键技术之一。 组播是将单一的数据拷贝从源节点传送到多个目的节点的网络通信方式。实现组播通信的方法一般是建立网络的组播树，而QoS组播路由算法就是建立一棵性能良好的满足服务质量要求的组播树。因此，建立性能良好的组播树的QoS组播路由算法就成了本文研究的重点。 本文首先分析了组播技术的基础理论，随后介绍了拉格朗日松弛算法的基本原理。通过对现有的几种典型的受QoS限制的组播路由算法分析后，指出了它们存在的不足，并提出了一种基于拉格朗日松弛法的受限低代价组播路由算法LR-DLMR。该算法具有以下主要特点： (1)算法并未对原网络拓扑图创建封闭图，从而有效利用了链路中间节点信息，也避免了封闭图对原图的多播不可达的问题； (2)算法具有比较强的扩展性，为了便于和其它延迟受限的组播路由算法进行性能对比，算法仅将延迟限制条件吸收到线性函数中进行拉格朗日松弛，同样对于带宽，丢包率等限制条件也可以吸收到线性函数中进行求解； (3)算法的效率取决于所采用的最小代价组播树生成算法，这点保证了该算法具有长远的生命力，只要有新的更优的最小代价组播树生成算法的诞生，就可以套用到该算法中进一步求解满足延迟限制条件的组播树； (4)算法具有可调节性，可以根据用户需求给算法设定松弛次数，要求在限定的次数内返回一棵组播树；也可以设定一个大于零的误差参数ε，要求在前后求得组播树代价差值只要小于该参数，算法就返回一棵组播树。 通过严格的理论分析，对LR-DLMR算法的正确性进行了证明，并且推理出算法的最坏时间复杂度仅为O(P(M+3/2)n<'2>-pm<'2>n)，n为网络的节点数，m为目的节点数，p为松弛次数。最后，本文通过仿真实验的结果分析表明：LR-DLMR算法在代价性能上优于KPP算法，接近目前代价性能最优的BSMA算法；在运行时间性能上本算法快速有效，和KPP算法相似，远远优于BSMA算法；以及算法所具有的一些特点都表明了LR-DLMR算法有较高的实用价值。

目录

文摘

英文文摘

学位论文独创性声明及学位论文授权使用声明

第一章绪论

1.1组播的产生背景

1.2网络通信方式

1.3组播的发展简介

1.4组播的优点

1.5组播的应用

1.6本文的主要工作和组织结构

第二章组播技术基础

2.1组播地址

2.2组播树

2.3组播转发

2.4组播路由协议

2.5 Internet组管理协议

2.6本章小结

第三章拉格朗日松弛算法原理

3.1引言

3.2基于规划论的松弛方法

3.3拉格朗日松弛方法

3.4拉格朗日松弛算法

3.5本章小结

第四章典型的组播路由算法

4.1引言

4.2 QoS的一般性描述

4.3无QoS限制的组播路由算法

4.4受QoS限制的组播路由算法

4.5本章小结

第五章基于拉格朗日松弛法的受限低代价组播路由算法

5.1引言

5.2受限组播的网络模型

5.3组播网络模型的拉格朗日松弛

5.4 LR-DLMR算法具体描述

5.5 LR-DLMR算法分析

5.6 LR-DLMR算法特点

5.7本章小结

第六章仿真实验与分析

第七章总结与展望

7.1全文总结

7.2研究展望

参考文献

附录随机网络拓扑生成伪代码

致谢

攻读硕士学位期间参加的科研项目及发表的论文