*Debasish CHAKRABORTY (
deba@shiratori.riec.tohoku.ac.jp),

Goutam CHAKRABORTY(
goutam@soft.iwate-pu.ac.jp)

Iwate Prefectural University. Dept of Sofware and Information Science.

Iwate Ken. Takizawa mura Azasugo 152-52. Japan 020-1073.

Chotipat PORNAVALAI(
chotipat@it.kmitl.ac.th)

Faculty of Information Technology King Mongkut's Institute of
Technology Ladkrabang.

Ladkrabang, Bangkok 10520 Thailand.

*Norio
SHIRATORI (
norio@shiratori.riec.tohoku.ac.jp)

2-1-1, Katahira, Aoba-ku, Sendai. Japan 980-8577

With the increasing popularity, multimedia multiparty conference is becoming an essential part of today's communication. In multicast communication the packets are delivered from a single source to multiple destinations.

In dynamic multicasting, destination nodes are joining and leaving the group during the communication period. Without any rerouting the multicast-tree may grow too large. A rerouting can produce an optimal cost tree, but is undesirable as it would cause disruption in transmission of continuous media.

Considering the increasing popularity of advance resource reservation, where it is possible to estimate the users' duration of staying time, we proposed a centralized heuristic approach for dynamic multicast routing. The motivation is to minimize the total cost of Steiner tree for the whole duration of a session without rerouting.

Efficiency of our algorithm over Greedy and Naive algorithm is shown with various simulations. Comparison with optimal heuristic algorithm, where rerouting is also allowed, is done.

Keywords:Dynamic Multicast Routing, Advance Resource Reservation, Cost Minimization.

- 1. Introduction
- 2. Dynamic Multicast Routing
- 3. Proposed Idea
- 4. Simulation and Analysis
- 5. Conclusion
- References

Dynamic multicast groups promise to be a powerful tool that can help ease the design and implementation of many distributed algorithms and there is a need to develop efficient dynamic multipoint algorithms which enable hosts to join and leave a group at any time during the lifetime of the session. Some frequently cited examples include video or teleconferencing, distributed data base, mass mailing and video-on-demand services [huang][ raja]. One of the important optimization criterion for these services is the minimization of the hop-length which in turn ensures minimizing the use of network resources. This also ensures low end-to-end delay important for successful transmission of continuous media.

Routing is one of the most important aspects of computer networks. The optimization criterion for a multicast routing algorithm can be classified into two general categories [kadaba] [zhu]. One is the shortest path tree (SPT), which minimizes the cost from source to each destination. Another optimization goal is to minimize the overall cost of the multicast tree, where some of the vertices included in the final solution may not be members of the destination node and they are called Steiner nodes. The problem is known as NP-complete in most general case. Hwang [ hwang ] provides a survey of both exact and heuristic solutions. Steiner tree heuristics, though providing near optimal solutions are sometimes too difficult to implement in practical protocol or computationally too intensive. Most of the proposed heuristics for the Steiner tree require global network information and can be quite complex relative to SPT schemes [ kompella ]

In the past few years, multicast routing has seen widespread use in those networks that support it. As expected, using multicast technology in place of multiple unicast streams improves the quality of existing applications as well as efficient use of network resources. In case of video-conferencing, this may result in a higher frame rate or improved conference control. In other cases, such applications as distributed virtual reality or multi-user scientific visualization are impossible to build without multicast support due to the sheer volume of data that needs to be transmitted. Depending on the application multicast group can be either (i) static - once set-up, remain unmodified until they are discarded or torn down. (ii) dynamic - destinations join and leave the session independently. This dynamic multicast can again be classified into two. One, where advance information about the whole session and participation time for individual is available and the other, where no such information is available.

One of the basic problem with the popularly used Greedy algorithm [waxman] for dynamic multicast routing is that, it doesn't consider the duration for which a node is connected in the multicast group. So, the route which is optimal at a particular time may become non-optimal after some time. Many nodes still participating in the session are connected through nodes, already left the session, but have to stay as Steiner nodes. This makes the total tree cost high, though the number of multicast members may have reduced. This also increase the hop length from source to destination. Optimal or near optimal tree can be produced by total re-routing [kou]. Kadirire [kadirire] proposed a partial re-routing procedure. But both will cause re-ordering and thus synchronization problem. Doar and Leslie [doar] proposed a Naive approach to join the new node to the source with the shortest path every time, which produces high tree cost. This problem can be solved when advance information about the joining and leaving of participants are available, at least if it is possible to know the duration at the time of joining. As the duration involves cost, the participants are expected to be more careful about requesting for exact duration.

In the dynamic version of the multipoint problem we start with a network and consider a sequence of requests

In Fig 1, we have shown an example of multicast tree at four instants of time. The left four are situations where the Greedy algorithm is used and the rest are while the Naive algorithm is running. In Greedy algorithm, all the existing multicast nodes are considered as virtual source node. So, the new node will join the nearest existing multicast node with the shortest path. In Naive algorithm, every new node joins the source node with the shortest path, without considering the existing multicast tree. It clearly shows that for Greedy algorithm [waxman], the number of nodes staying in the connection as Steiner nodes (shown with light circles) are higher than that of Naive algorithm approach [doar]. In the long run it increases the cost of the tree as well as the hop length of connections to nodes joining at later stages of the session. On the other hand, as the Naive algorithm does not consider the existing tree at all, the total cost is much higher. So, the individual participants connection time is important and has been considered in our algorithm to construct multicast tree to minimize the total tree cost for dynamic multicast.

The ability to reserve real-time connections in advance is essential in all multi-party applications, to guarantee required resources. Advance resource reservation is gaining popularity due to its various advantages [gupta]. On the other hand

The departure time of the joining node will be the tag for all the links from source to the newly joined node. This

When the next new node sends connection request to the source node, the different link costs of the network, both in the existing multicast tree and outside of it, will be calculated according to the new node's remaining time with respect to the existing links'

Once route is found, all intermediate links with less termination time stamps than

As the bottleneck bandwidth of a path should satisfy the required bandwidth for an application, the links that does not satisfy the bandwidth constraint will be neglected while searching a route to add a new participants.

As the tag-table has been updating after each modification, it will be easier to mark the branches which will be deleted, when a multicast node will leave the session.

After the node will be deleted from the spanning tree, the corresponding time-tags for those links will also be erased from the tag-table and will get its initial value, i.e. zero.

We have used Dijkstra's shortest path algorithm to find the route from source to destination. This algorithm has been already in use in Internet routing protocol, such as OSPF [orda].

Without rerouting, it is not possible to create an optimal Steiner tree for dynamic multicast. So, with our algorithm we may not always produce a perfect optimum tree, but it certainly produces less costly tree than Greedy or Naive on average and without rerouting, still comparable to KMB, where total rerouting has been used.

Our algorithm also helps to minimize the number of hops. The reason is, in Greedy algorithm existing tree cost is considered as zero. So, a new node will always try to connect to the nearest node in the existing multicast tree, though that may be far form the source node. This is true specially for those nodes joining the multicast session later in the stage.

The network model to be considered are as in [ waxman], where graphs are constructed by distributing

The source node is connected from the beginning to the end of the session for all occasions. The number of destinations is a proper subset of the total number of nodes.

The Greedy [waxman] and Naive [ doar] are already briefly discussed in section 2 . Both these two algorithms don't use rerouting, as is desired in multimedia connection. The KMB [kou ] heuristic, is the best known heuristic to find the optimum Steiner tree. We implemented KMB to find the multicast trees as and when a new node is connected or a connected node is departed. KMB generates near optimum tree, for every new situations with new set of destination nodes. Thus, it is undesirable to use in practice, because of the rerouting problem. In spite of this, we implemented KMB to find the near optimum cost.

Thus if during a whole multicast session, the total cost of connection from source to different destination is

Tree cost of a whole session has been calculated for every instant of time from beginning of the session till end of it, for both

Inefficiency with respect to optimum KMB tree as defined in section 4.3 has been calculated for various sizes of random networks. The maximum number of destination nodes that can be present at any time is gradually increased. The number of destination nodes of course changes dynamically during the session.

While calculating the cost inefficiency of the different practical algorithms (e.g. Greedy, Naive or ODMT), where rerouting is not used, we set the cost obtained by KMB at 1. (In [waxman], it is found that the mean inefficiency of KMB is between 1 to 1.05 compare to optimal Steiner tree).

For calculating cost inefficiency of Greedy, Naive and ODMT with respect to KMB, we did experiment with 40 and 60 nodes network. The number of destinations at any time during the whole session is increased in steps of 10% of the total number of nodes. Two different situations are considered.

Fig.10, shows the average hop distance from source to destination for every dynamically joining nodes, averaged over the whole duration of the session. The total number of nodes here is 60. We took the average of different sets of arrival and departure time. The result shows that our algorithm performs much better than the Greedy algorithm. If we consider a uniform delay for each hop, we can say that the average delay per destination will be much lower with our algorithm compared to Greedy algorithm.

Fig.2 shows the situation of

In next two figures, when participants are allowed to rejoin again, (

The Naive out perform our algorithm in case of hop count. That is obvious as in Naive algorithm nodes join the source without considering about the existing multicast tree. On the other hand, the total tree cost is considerably higher compared to the other two dynamic algorithms discussed here.

The cost inefficiency of our algorithm, though varies depending on the total number of network nodes and duration of destination nodes and total nodes, it performs better than other two dynamic multicast routing (without rerouting) and sometimes perform close to KMB.

Experiencing with different batch of arrival and departure time as well as network with varying number of total destination nodes, it has been seen that our algorithm produce less costlier Steiner tree considering the whole duration of session time. We have also shown that source to destination hop length is less in our algorithm compared to Greedy algorithm.

We assume a globally synchronized clock for the timing issue in our algorithm. The amount of out-of-synchronization time can be neglected, as it is much smaller compared to the whole session time or the time duration for which individual participant is connected.

Additional goals for future work include, experimenting the performance of our algorithm while applying in actual multicast application and develop a distributed algorithm for dynamic multicasting. Considering other QoS constraints in dynamic multicast while minimizing cost is the area where we are interested to extend this work. While every joining and leaving information are available a-priori, a better multicast tree is possible. We are also working to find a practical algorithm for such a situation.

- Paul C.Huang, Y.Tanaka. "Multicast Routing
Based on Predicted Traffic Statistics"
*IEICE Trans. Communication*Vol. E77-B, No.10, October, 1994 - Berman M. Waxman, "Routing of Multiple
Connections,"
*IEEE Journal on Selected Areas in Communications.*Vol.6, No.9, 1988 - B.Rajagopalan. "Reliablity and Scaling Issues
in multicast communication"
*In proc. ACM SIGCOM, Baltimore.*Oct.1992. - James Kadirire. "Minimizing Packet Copies
in Multicast Routing by Exploiting Geographic Spread"
*ACM SIGCOM CCR.*Vol 24, No.3, July 1994 - Bharath-Kumar and Jeffrey M.Jaffe.
"Routing to Multiple Destination in Computer Network".
*IEEE Transaction on Communications*. Vol,.COM-31, No.3. 1983 - F.K.Hwang and D.S.Richards.
"Steiner Tree Problems.
*Networks.*Vol.22, No.1, January 1992. - Q.Zhu, M.Parsa and J.J.Garcia-Luna-Aceves.
"A Source Based Algorithm for Delay-constrained Minimum-cost multicasting".
*In Proc. IEEE INFOCOM, Boston*April 1995. - V.P.Kompella, J.C.Pasquale and G.C.Plyzos.
"Multicast Routing for Multimedia Communication."
*In IEEE/ACM Trans. Networking*Vol.1, No.3, June. 1993. - L.Kou, G.Markowsky and L.Berman.
"A Fast Algorithm Steiner Trees."
*Acta Informatica.*Vol.15, No.11, 1981. - Goutam Chakraborty, C.Pornavalai, D.Chakraborty and
N.Shiratori. "Routing in Multimedia Communication"
*Proc. of International Conference on Computers and Devices for Communication (CODEC-98)*December, 1998. - Matthew Doar and Ian Leslie. "How Bad is Naive Multicast
Routing?"
*Proc. of IEEE INFOCOM, San Francisco, CA*April, 1993. - Amit Gupta. "Improved Performance for Multi-party
Communication through Advance Resource Reservation."
*Precdings of Sizthe International Workshop on Network and Operation System Support for Distributed Audio and Video.*April 1996. - Debasish Chakraborty, G.Chakraborty, C.Pornavali and
N.Shiratori . "Optimal Routing for Dynamic Multipoint Connection".
*will appear in Eurpean Trans. on Telecommunication* - Debasish Chakraborty, G.Chakraborty, C.Pornavali and
N.Shiratori . "An Efficient Routing to Minimize the Cost for
Dynamic Multicasting".
*Asia-Pacific Conf. on Circuit and Systems.*November 1998. - R.Guerin, A.Orda and D.Williams.
"QoS Routing Mechanism and OSPF Extensions". In
*Internet Draft.*1006.