计算机通信网组播路由算法的研究

【作者】 黄勇；

【导师】 莫松海；

【作者基本信息】 中国人民解放军国防科学技术大学 ， 系统工程， 2002， 硕士

【摘要】 近年来出现的多媒体通信与分布式环境下协同工作促使系统设计者们为这些应用提供相应的通信支持。在这种环境下普遍采用的一种方式是组播通信(一对多或者多对多)。路由是组播通信中的关键问题之一。组播路由优化的目标是在满足时延约束的条件下网络代价最小化，在一般的情况下，这是一个NP完全问题。目前存在的启发式算法一般时间复杂度比较高，而简单容易且利于分布式实现的算法还处于研究之中。到目前为止，还没有出现好的算法能合理地平衡网络代价与网络时延。在本论文中，一个组播路由综合优化的概念被提出，这使得网络代价与时延都能在某种程度上获得优化。优化网络代价将减少通信过程消耗的网络资源，而优化网络时延将减少从源点到目的节点的时间。具体提出了一个链路选择函数，使用这个选择函数的算法能够在组播通信中实现综合优化，而以前没有出现过类似的算法。算法中设置有一个可调参数，能够调节网络代价与网络时延之间的优化程度。此算法已在许多随机网络模型上进行了模拟实验，证明它具有好的性能。这个算法时间复杂度低，容易分布式实现。更多还原

【Abstract】 The recent emergence of multimedia communication and collaborative work in distributed environments provides an incentive to system designers to include communication support for these applications. A prevalent pattern in such environments is multicast (one-to-many or many-to-many) communication. Routing is one of the key problems to multicast communication. The objective of multicast routing optimization is to minimize the network cost with delay constrained. Finding a multicast routing tree with minimized network cost is known to be an NP-Complete problem in the most general case. The existing heuristics have high time complexity. The heuristics with simple, easy and distributed implementations are under research. Up to now, there is no balanced method between optimization of network cost and delay yet. In this paper, a concept of intergate optimization of multicast routing is put forward,in which both network cost and delay are optimized in a certain degree. Optimization of the network cost can reduce network resources consumed by communication, while optimization of the delay can reduce the delay from source to receivers. An edge selection function is also put forward,which can accomplish integrated optimization of multicast routing. There was never an algorithm that had the same performance before. An parameter is set in the algorithm, which can adjust optimization level between optimization of network cost and optimization of network delay. The algorithm is simulated in many random network models,and is proved that it has better performance than existing heuristics. This algorithm has low time complexity,and can also be implemented easily and in distributed fashion.更多还原