The effciency of multicast
Piet Van Mieghem · Cambridge University Press eBooks · 2006
The effciency or gain of multicast in terms of network resources is compared to unicast. Specifically, we concentrate on a one-to-many communication, where a source sends a same message to m different, uniformly distributed destinations along the shortest path. In unicast, this message is sent m times from the source to each destination. Hence, unicast uses on average f N ( m ) = mE [ H N ] link-traversals or hops, where E [ H N ] is the average number of hops to a uniform location in the graph with N nodes. One of the main properties of multicast is that it economizes on the number of linktraversals: the message is only copied at each branch point of the multicast tree to the m destinations. Let us denote by H N ( m ) the number of links in the shortest path tree (SPT) to m uniformly chosen nodes. If we define the multicast gain g N ( m ) = E [ H N ( m )] as the average number of hops in the SPT rooted at a source to m randomly chosen distinct destinations, then g N ( m ) ≤ f N ( m ). The purpose here is to quantify the multicast gain g N ( m ). We present general results valid for all graphs and more explicit results valid for the random graph G P ( N ) and for the k -ary tree. The analysis presented here may be valuable to derive a business model for multicast: “How many customers m are needed to make the use of multicast for a service provider profitable?” Two modeling assumptions are made. First, the multicast process is assumed to deliver packets along the shortest path from a source to each of the m destinations.