论文部分内容阅读
多播技术已有广泛的应用。对于实时性要求高的多播应用,多播路由必须保证服务质量。为此,本文研究保证服务质量的多播路由问题,并提出三个多播源路由算法以保证服务质量。 多播路由问题实质上就是构建覆盖源端和接收端,并满足应用服务质量要求的路由树的问题。构建代价最小且保证服务质量的多播路由树问题是NP难的。目前已出现了很多启发式多播路由算法,有的算法可以构建低代价的多播树,但是时间复杂度很高,对于大规模的网络来说,应用价值不大;有的算法具有较低的时间复杂度,但是,构建的多播树代价不甚理想。本文在研究已有算法的基础上,提出新的多播路由算法,试图在算法的有效性与算法的时间复杂度之间取得平衡。 首先,本文有效地分析了经典的时延约束多播路由算法—KPP算法,并提出了一个改进的KPP算法。新算法在构造多播树过程中,考虑到了KPP算法未考虑的转发节点加入带来的影响,并通过路径的动态选择来消除此影响;同时,使用两个策略对多播树进行优化,得到低代价的多播树。实验表明,新算法构造的多播树与KPP算法构造的多播树相比,代价低9%到10%。 其次,在多播路由中,使用的链路共享程度越高越能节约网络资源。基于对链路共享重要性的理解,本文提出了链路可共享性的新概念,链路可共享性是对链路共享程度的定量。同时,基于链路可共享性,提出了一个快速有效的时延约束多播路由算法SBMR。实验表明,SBMR算法构建的多播树有72%比KPP算法构建的多播树更优,代价降低13%,启用的链路数减少9%,而且CPU时间减少15%。与DCSP算法相比,SBMR算法以增加28%的CPU时间为代价,构建的82%的多播树比DCSP算法更优,代价降低15%,而且启用的链路数减少11%,达到了更好的链路共享。 最后,考虑到时延抖动是服务质量的重要因素,本文提出满足时延和时延抖动约束的多播路由算法EDDVCMR。EDDVCMR算法首先对Dijkstra最短路径算法进行扩展,使得扩展后的Dijkstra算法不仅可以找到多播源到各接收端的时延最小路径,还可以找到时延介于某一区间段的路径;然后,从找到的若干路径中抽取一组满足时延抖动约束的路径,从而组建一棵满足时延和时延抖动约束的多播树。实验表明,EDDVCMR算法与DVMA算法相比,有高出7%的求解成功率,同时,执行的CPU时间减少36%。