Research On Multicast Tree Generating Algorithms

With the developing of the technology of network, transmitting of information will deal with not only the point to point way but also the ones, which will be much of the video frequency and sound frequency, such as meeting television. Multicast is becoming a key requirement of network supporting multimedia applications. After briefly introduce the different criteria, and some algorithms, we give two algorithms on the problem of multipoint connections. The first algorithms is based on MPH (Minimum Path Cost Heuristic). We modify the method of subpath adding to the existed subtree for MPH(Minimum Path Cost Heuristic). Thus we get SMPH(Semi-Minimum Path Cost l-leuristic). The shortest distance between a point and the Multicast Steiner Tree is the shortest distance between the point and die points of the Multicast Steiner Tree .When every time we fly to find the point with shortest distance to the Multicast Steiner Tree, we need a lot of comparations. In this paper we improved this aspect, we introduce a concept of semi-shortest way and semi-shortest distance that is the shortest way to the point of the Multicast Steiner Tree. Thus we only need to note do length of the semi-shortest way distance of every unadded point to the Multicast Steiner Tree. After we add a point to the Multicast Steiner Tree each time, we can renew the information of the points by comparing it with the distance of the point to every unadd points, and get the shortest one . Apparently it greatly deduce the times of compare, thus improve the efficiency of the algorithms, at mine time we get a similar result with MPH(impmve 2.45% on average). The second is based on pile. We build the points into a pile, each time add the top point of the pile to the Steiner Tree, and adjust distance beten the children of the root point and the Steiner Tree. With the random graph mode, the simulation shows dial 5MPH can compute faster with relatively space increasing; and die new algorithms is faster with relatively smaller costincreasing. CQmpadng with other MST(Mullicast Steiner heuristics, the two algorithms is much faster, At last we give an algorithms of revolve which only use addition and move bit.