Ring versus tree embedding for real-time group multicast

In general topology networks, routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in a route length of O(log n) links, being n the number of nodes in the network. Routing from one node to another over a ring embedded in the network would result in route length of O(n) links. However, in group (many-to-many) multicast, the overall number of links traversed by each packet, i.e., the networks elements on which resources must be possibly reserved, is typically O(N) for both tree and ring embedding, where N is the size of the group. This paper focuses on the tree versus ring embedding for real-time group multicast in which all packets should reach all other nodes in the group with a bounded end-to-end delay. In this work, real-time properties are guaranteed by the deployment of time driven priority in network nodes. In order to have a better understanding of the non-trivial problem of ring versus tree embedding, we consider the following group multicast scenarios: (i) static-fixed subset of active nodes, (ii) dynamic-fixed number of active nodes (i.e., the identity of active nodes is changing over time, but its size remains constant), and (iii) adaptive the number and identity of active nodes change over time. Tree and ring embedding are compared using the following metrics: (i) end-to-end delay bound, (ii) overall bandwidth allocated to the multicast group, and (iii) signaling overhead for sharing of the resources allocated to the group. The results are interesting and counter-intuitive, since, as shown, embedding a tree is not always the best strategy. In particular, dynamic and adaptive multicast on a tree requires a protocol for updating state information and coordinates the operation of the group. Such a protocol is not required on the ring where the circular topology, and implicit token passing mechanisms are sufficient. Moreover, the bandwidth allocation on the ring for the three multicast scenarios is O(N); while on a general tree it is O(N) for the static multicast scenario and O(N²) for the dynamic and adaptive multicast scenarios