论文部分内容阅读
随着计算机技术、网络技术的快速发展,网络应用已从简单的信息交流发展到远程教学、视频点播、网络会议、数据分发和网络游戏等,这些应用不仅要求网络支持多播服务,而且对服务质量(QoS)提出了更高的要求。实现多播通信的关键是多播路由算法的实现,其实质就是构建一棵覆盖源端和接收端,并满足应用服务质量要求的多播树。实时多播通信中,为保证信息适时的传到每个接收端,需限制端到端时延;同时,为保证每个用户都能同时收到信息,需限制端到端时延抖动。因此,对时延和时延抖动受限的多播路由算法研究不仅可以保证用户的服务质量,而且对推动实时多媒体应用的发展具有重要意义。因此,本论文针对时延和时延抖动问题,提出了两个启发式算法。首先,针对时延约束多播路由问题DCLC,提出了一个时延约束Steiner树算法DBLC。该算法基于MPH算法思想,每个目的节点通过到已构建多播树最小代价路径加入该多播树;若时延不满足要求,则运用本章改进的P(s,t,△)算法加入多播树,从而产生一个满足时延约束的最小代价多播树。对该算法正确性和性能特点进行了理论分析,并通过仿真实验证明:DBLC算法生成的多播树在保证时延要求下,与同类算法相比,具有较好的代价性能和较低的复杂度。其次,针对时延和时延抖动约束多播路由问题DVBMT,提出了一个时延及时延抖动约束的Steiner树算法DVMC。通过实例分析DVBMT问题模型中时延和时延抖动这两个约束条件是冲突的,并得出每路径时延与这两个约束条件的关系。DVMC算法源于DVMA算法中k条最短路径思想,采用类似贪婪算法思想,将每路径时延最大值作为当前构建的多播树时延上限,利用基于每路径时延最大值和代价的链路选择函数进行路径的选择,从而生成一棵满足时延和时延抖动约束的最小代价多播树。对该算法的正确性和性能特点进行了理论分析,并通过仿真实验证明:DVMC算法在生成树代价、成功率和计算时间方面都有明显的优势。