时延受限组播路由算法的研究

摘要

随着互联网技术的迅速发展,视频点播、远程会议、在线教育和网络游戏等实时多媒体服务运用的越来越广泛,人们对网络应用的服务质量(Quality of Services,QoS)要求也随之增高。为了满足实时多媒体服务的需要,组播技术得到广泛应用。组播技术将数据从一个或多个节点同时向多个目的节点发送,该技术在一定程度上解决了实时多媒体业务对网络通信中时延、代价、带宽等QoS服务质量要求造成的瓶颈问题。
　　受限的组播路由问题是组播路由中一个关键问题,而时延受限组播路由问题又是受限组播路由问题中一个重要课题,时延受限组播路由问题就是在时延限制的前提下找到一个总代价最小的组播路由,该问题是NP-Complete问题,一般用启发式算法解决。针对单源的时延受限组播路由问题,提出了一种动态时延受限组播路由启发式算法。该算法分为静态和动态两部分,将时延受限组播路由算法中初始状态组播树的构建和节点动态变化后组播树更新两阶段综合考虑,减少了构建组播树的总时间。该算法不仅能解决静态时延受限组播路由问题,还能解决动态的时延受限组播路由问题。
　　本文的主要工作包括:
　　①组播的研究背景、国内外现状、原理、相关协议和算法分类的介绍;
　　②介绍无约束组播路由问题中重要解决方法之一的Steiner树问题和对几种典型启发式算法分析比较;
　　③介绍时延受限组播路由问题数学模型、常见定义,对常见静态时延受限组播路由算法和动态时延受限组播路由算法进行分析比较,阐述两类算法之间关系;
　　④由静态时延受限组播路由算法和动态时延受限组播路由算法的关系,提出一种时延受限组播路由启发式算法 KNDMR。该算法包括静态和动态两部分,静态部分实质上是一种新的静态时延受限组播路由算法,用于在初始阶段构建符合时延限制的组播树,该部分改进已有链路选择优化函数,并首次提出关键次数概念;动态部分在静态部分组播树基础上,处理组播成员动态变化时组播树更新问题,动态部分重点提出对组播树转发节点退出情况的处理,通过共用关键节点的关键次数减少构建组播树的时间。仿真实验结果显示该算法在组播树代价不增加的前提下,构建组播树所需时间比其它动态算法要少,适用于较大型的实际网络。