Paper Info
Title
Multicast Routing with Delay and Delay Variation Constraints for Collaborative Applications on Overlay Networks
Abstract
Computer supported collaborative applications on overlay networks are gaining popularity among users who are geographically dispersed. Examples of these kinds of applications include video-conferencing, distributed database replication, and online games. This type of application requires a multicasting subnetwork, using which messages should arrive at the destinations within a specified delay bound. These applications also require that destinations receive the message from the source at approximately the same time. The problem of finding a multicasting subnetwork with delay and delay-variation bound has been proved to be an NP Complete problem in the literature and heuristics have been proposed for this problem. In this paper, we provide an efficient heuristic to obtain a multicast subnetwork on an overlay network, given a source and a set of destinations that is within a specified maximum delay and a specified maximum variation in the delays from a source to the destinations. The time-complexity of our algorithm is O(|E| + nk \log(|E|/n) + m^{2}k), where n and |E| are the number of nodes and edges in the network, respectively, k is the number of shortest paths determined, and m is the number of destinations. We have shown that our algorithm is significantly better in terms of time-complexity than existing algorithms for the same problem. Our extensive empirical studies indicate that our heuristic uses significantly less runtime in comparison with the best-known heuristics while achieving the tightest delay variation for a given end-to-end delay bound.
Year
DOI
Venue
2007
10.1109/TPDS.2007.45
IEEE Trans. Parallel Distrib. Syst.
Keywords
Field
DocType
specified delay,multicast subnetwork,specified maximum delay,overlay networks,np complete problem,collaborative applications,multicast routing,overlay network,multicasting subnetwork,tightest delay variation,efficient heuristic,specified maximum variation,delay variation constraints,best-known heuristics,groupware,end to end delay,distributed database,routing,application software,distributed databases,computer networks,collaboration,protocols,communication complexity,games,computer applications,shortest path,time complexity,empirical study,video conferencing,internet
Heuristic,Shortest path problem,Computer science,Computer network,Communication complexity,Heuristics,Multicast,Distributed database,Subnetwork,Overlay network,Distributed computing
Journal
Volume
Issue
ISSN
18
3
1045-9219
Citations 
PageRank 
References 
22
1.06
21
Authors
3
Name
Order
Citations
PageRank
Shankar M. Banik1558.42
Sridhar Radhakrishnan234143.65
Chandra N. Sekharan310512.77