Cost Minimization for Dynamic Multicast without Rerouting

*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)

*RIEC, Graduate School of Information Sciences, Tohoku University
2-1-1, Katahira, Aoba-ku, Sendai. Japan 980-8577

Abstract
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.

Table of Contents

1. Introduction

With the recent advancement in computer, high speed transmission and switching technology, it is now feasible to provide multimedia, multiparty communication services. Multicast can be defined loosely as the ability to logically connect a subset of hosts in a network. A packet switched network is said to provide a multicast service if it can deliver copies of a packet to a set of destinations simultaneously. These messages may originate at one or more source sites and the recipient processes may run on one or more sites. A multicast protocol is responsible for delivery of messages to appropriate processes or hosts.
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.
Outline of paper: In Section 2 , we define the dynamic multicast routing problem and discuss some related works in dynamic multicast routing, specially of those algorithms, we have implemented for comparison. Our proposal, a modification of greedy algorithm to minimize the total Steiner tree cost for the whole duration of a session in Section 3. In Section 4, simulation results are shown comparing with Greedy, Naive and KMB algorithm. Concluding remarks and scope of further works are in Section 5.

2. Dynamic Multicast Routing

Here network is considered as an undirected graph. The graph is defined as G = (V,E,w), where V = {v1,v2,..vn} is the set of vertices in G, E is the set of edges in graph G. S is a subset of vertices of V. The Steiner tree problem is to find a tree of G that spans S with minimal total distance of its edges. In computer networks the vertices are considered as nodes and the edges as transmission links.
In the dynamic version of the multipoint problem we start with a network and consider a sequence of requests ri where each ri is a pair (v,t), where v is a member of V, the node to be added, and t is the duration of time for which connection is requested. The problem is to connect the new nodes to the multicast tree satisfying the bandwidth constraint [kadaba].
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.

Fig.1

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 network service provider, can estimate more accurately the demand for network resources, and thereby design a scheme that will scale well for large conference and yet provide very fast set-up. Thus the quality of network routing can significantly improve.

3. Proposed Idea

3.1 Assumptions

  • Every node has multicast capability with unlimited degree.
  • A participation request is always accompanied with the duration of connection. It is reasonable in situations where cost is involved with the duration of participation.
  • We consider only one group among more than one possible groups in the whole network.
  • We also assume that, except the single source node others are only receiver or destination nodes.
  • The routing algorithm is considered source based.
  • Clock is considered as globally synchronized.

    3.2 Addition of New Nodes

    The session will begin only with the source node. Connection request from destination node z comes to source node s in the form Req[z, T_ter], where T_ter is the termination time. The earliest arrived node will be he first to join the source node, by the shortest path (Dijkstra) to form the initial multicast tree. With every link we associate a pair (w,tag), where w is the weight and tag is a time stamp. This tag represents till what time the link will have to be connected to the multicast tree.
    The departure time of the joining node will be the tag for all the links from source to the newly joined node. This tag represent the remaining time of the links forming path from source to the requested node. The tag for links not in the multicast tree are set to zero.
    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' tag. Weight will be calculated for every link. The weight of the link is a variable, that changes according to the termination time of the new node.
    Link-cost Calculation: Suppose link e with actual cost C_e connects node u and v. If T_new is the new node's termination time and T_l is the termination tag of the link between (u,v), the link cost:
  • between two nodes u and v, forming a link, which is outside the running multicast tree: C_e × T_new.
  • between two node, forming a link of running multicast tree, with T_new > T_l: C_e × T_new - T_l.
  • between two nodes, forming a link of running multicast tree, but T_new < T_l: considered as zero.
    Once route is found, all intermediate links with less termination time stamps than T_new would be updated to T_new.
    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.

    3.3 Deletion of Nodes

    When the remaining time of a node in the tag-table become zero, or in other word, when the departure time of a node will be equal to the current global time, that node is supposed to leave the group. The deletion is initiated by deletion request from the receiving node.
    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.

    3.4 Discussion of the Algorithm

    In our proposed centralized algorithm, complete network topology information must be available at the source node running the algorithm. The departure time of the participating nodes are required, for recalculation of network links. As we are trying to optimize the tree cost for a dynamic multicast routing, we refer to the algorithm as optimum dynamic multicast tree (ODMT) routing.
    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.

    3.5 Computational Complexity

    Every time a shortest route for new destination node has to be searched if it is not already included in the existing multicast tree. In worst case we have to calculate the link-cost E times, where E is the number of links, which is α × V. Here, α is the degree of the network, and is 4 in our simulations and V is the number of nodes in the network. We are using Dijkstra to find shortest path. So the total running time per call request will be O(V^2+E)= O(V^2). So, the running time of our algorithm per call request in worst case will be O(E) + O(V^2) = O(α V) + O(V^2), i.e O(V) + O(V^2) = O(V^2).

    4. Simulation and Analysis

    4.1 Network Model

    Random graphs were generated with their connectivity characteristics approximated to those observed in real networks.
    The network model to be considered are as in [ waxman], where graphs are constructed by distributing n nodes across a Cartesian coordinate grid. Edges were added to the graph by considering all possible pairs (u,v) of nodes and using probability function, which exponentially decreased with the increase of distance between two nodes. The detail could be found in [waxman].

    4.2 Random Arrival and Departure Time

  • Case I: After leaving the session once, that participants will not join the session again. The duration of staying time is more or less same for all the participants. It is considered having a Gaussian distribution, over the average with small variation. This is to emulate the situation where a participant remains connected only the portion, he/she is interested in and those portions are of similar duration.
  • Case II: The option of joining the group more than once, i.e. after leaving the session a node can join the multicast group later again, was considered.
    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.

    4.3 Simulation Consideration

    For comparison of the effectiveness of our algorithm we implemented the following methods in addition to the proposed ODMT algorithm. Greedy algorithm, Naive algorithm and KMB algorithm.
    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 C using a practical algorithm, and the same cost is C_k using KMB (with rerouting), then the cost inefficiency of that algorithm is defined as C/C_k. The simulation results and their analysis are shown in section 4.4 .

    4.4 Simulation Results

    Simulation programs were written in C and were run on a SUN SPARC workstation under SOLARIS operating system. Multiple simulations were performed and the results are shown in the following figures. Every data shown here is an average of running the simulation 100 times, by changing the arrival-departure time and with different networks.
    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 Case I and Case II , mentioned in section 4.2. The cumulative cost, as time passes is also calculated. The aim of our algorithm is to minimize the total cost of the tree for the whole session, and from cumulative cost it is clear how the different algorithms perform with respect to cost minimization for the whole duration of a session.



    Fig.2 (Cost per instant time) & Fig.3 (Cumulative cost)- Case I



    Fig.4 (Cost per instant time) & Fig.5 (Cumulative cost) - Case II

    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. Case I, when destination nodes are not allowed to rejoin the session once they leave it and, Case II , when they are allowed to rejoin the session after leaving it. The simulation results are shown in the following figures (Fig.6 to Fig.9).


    Fig.6 (Case I) & Fig.7 (Case II) Mean Inefficiency for 40 nodes network



    Fig.8 (Case I) & Fig.9 (Case II) Mean Inefficiency for 60 nodes network

    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.10 Average hop length for 60 nodes network

    4.5 Analysis of the Results

    The performance of the algorithms, i.e. the cost of the entire tree, depends upon the arrival and departure time of the nodes and how long they are attached to the group. It has been found that ODMT is on an average better than Greedy and Naive and slightly worse than KMB.
    Fig.2 shows the situation of Case I, when participants are not allowed to join, once they leave the session. The cost of the tree after reaching its peak, when the number of participants are highest, gradually decreases. Initially Greedy algorithm was performing better than Naive. Though in the later half, when the participants are mostly leaving, the Greedy produces a much costlier tree, due to the existence of many Steiner nodes in the tree. From Fig.3 where the cumulative cost has shown for that period, it becomes clear.
    In next two figures, when participants are allowed to rejoin again, (Case II ) after leaving the session, the cost remain almost same after reaching its peak (Fig.4), as number of participants remain almost same till the very end of the session. Thus, the cumulative cost in this occasion (Fig.5), is linearly increasing. On both the cases, our algorithm (ODMT) performed better than other two algorithms, and marginally worse than optimum heuristic KMB algorithm, in spite of KMB uses rerouting.
    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.

    5. Conclusion

    In this paper we presented an efficient algorithm for dynamic multicast routing that biases toward existing routes with higher departure time. The actual thought behind our algorithm is to increase the probability of creating leaf node in the multicast tree, so that when a node's departure time will arrive, it may leave instead of staying in the multicast tree as Steiner node. Our aim here is to minimize the overall cost of the tree and minimize the number of hops from source to destination to benefit applications such as video conferencing, where the primary concern is to keep costs down over the entire transmission session and a shorter hop-length is always desirable for any real-time application.
    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.

    References

    1. Paul C.Huang, Y.Tanaka. "Multicast Routing Based on Predicted Traffic Statistics" IEICE Trans. Communication Vol. E77-B, No.10, October, 1994
    2. Berman M. Waxman, "Routing of Multiple Connections,"IEEE Journal on Selected Areas in Communications. Vol.6, No.9, 1988
    3. B.Rajagopalan. "Reliablity and Scaling Issues in multicast communication" In proc. ACM SIGCOM, Baltimore. Oct.1992.
    4. James Kadirire. "Minimizing Packet Copies in Multicast Routing by Exploiting Geographic Spread" ACM SIGCOM CCR. Vol 24, No.3, July 1994
    5. Bharath-Kumar and Jeffrey M.Jaffe. "Routing to Multiple Destination in Computer Network". IEEE Transaction on Communications . Vol,.COM-31, No.3. 1983
    6. F.K.Hwang and D.S.Richards. "Steiner Tree Problems. Networks. Vol.22, No.1, January 1992.
    7. 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.
    8. 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.
    9. L.Kou, G.Markowsky and L.Berman. "A Fast Algorithm Steiner Trees." Acta Informatica. Vol.15, No.11, 1981.
    10. 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.
    11. Matthew Doar and Ian Leslie. "How Bad is Naive Multicast Routing?" Proc. of IEEE INFOCOM, San Francisco, CA April, 1993.
    12. 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.
    13. Debasish Chakraborty, G.Chakraborty, C.Pornavali and N.Shiratori . "Optimal Routing for Dynamic Multipoint Connection". will appear in Eurpean Trans. on Telecommunication
    14. 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.
    15. R.Guerin, A.Orda and D.Williams. "QoS Routing Mechanism and OSPF Extensions". In Internet Draft. 1006.