Extending greedy multicast routing to delay sensitive applications

For multicasting applications which need large amounts of data, it is important to minimize the total amount of resources consumed on the multicast tree. The greedy multicasting algorithm was proposed by Imase and Waxman as a solution to this problem for the case where receivers can join the multicast group in a dynamic fashion. The greedy algorithm is simple to implement, and is known to be much better than shortest path based strategies such as DVMRP, CBT, and PIM in the worst case. We give both theoretical and simulation results demonstrating that the greedy multicast routing algorithm proposed by Imase and Waxman is much superior to shortest path based strategies even in realistic scenarios and not just for worst case inputs. However, the greedy algorithm does not work well for delay sensitive applications, and does not do a good job of handling deletions from the multicast group. We show how the greedy algorithm can be modified to handle deletions. We also adapt the greedy algorithm for delay sensitive applications. Our adapted algorithm is simple and efficient to implement, and, unlike previous work, gives worst case guarantees for both the delay encountered by each receiver as well as the total cost of the multicast tree. We give extensive simulation results comparing our algorithm with the greedy algorithm as well as with shortest path based strategies. We also describe our experience with implementing the greedy algorithm in an application-switched multicasting system.

Duke Scholars

Author Kamesh Munagala Computer Science