组播路由综合优化及其算法

路由优化是组播通信的一个关键问题，它的目标是将低路由费用。论文中首次提出了组播路由费用综合优化的思想，即组播路由的网络费用和目的地费用同时得到优化：优化网络费用以降低路由消耗的网络资源；优化目的地费用以减少源到目的地的平均时延。并提出了一种组播路由综合优化算法，该算法的时间复杂性低，实现简单，还可以分布式实现。

Integrated Optimization of Multicast Routing and Its Algorithm

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 or destination cost. 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 optimization of destination cost yet. In this paper, a concept of integrate optimization of multicast routing is put forward, in which both network cost and destination cost are optimized in a certain degree. Optimization of the network cost can reduce network resources consumed by communication, while optimization of the destination cost can reduce average delay from source to receivers. An algorithm is also put forward, which can accomplish integrated optimization of multicast routing. There was never an algorithm that had the same performance before. An attenuation method is applied to this algorithm. An attenuation parameter is set in the algorithm, which can adjust optimization level between optimization of network cost and optimization of destination cost. 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.