Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Multicast Routing
Multicast Tree
Online Algorithm
Simultaneous Approximation
steiner tree
Shortest Path Tree
Adaptive Algorithm
Greedy Algorithm
Shortest Path
Related Publications
(3)
Efficient Computation of Delaysensitive Routes from One Source to All Destinations
Costsensitive analysis of communication protocols
Dynamic Steiner Tree Problem
Subscribe
Academic
Publications
Extending Greedy Multicast Routing to Delay Sensitive Applications
Extending Greedy Multicast Routing to Delay Sensitive Applications,10.1007/s0045300101227,Algorithmica,Ashish Goel,Kamesh Munagala
Edit
Extending Greedy Multicast Routing to Delay Sensitive Applications
(
Citations: 13
)
BibTex

RIS

RefWorks
Download
Ashish Goel
,
Kamesh Munagala
Abstract. 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 applicationswitched multicasting system.
Journal:
Algorithmica
, vol. 33, no. 3, pp. 335352, 2002
DOI:
10.1007/s0045300101227
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
link.springer.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(10)
...In the other hand, in [
7
, 11], the model with allowed changes is considered...
...In [
7
], the aim is to minimize simultaneously the weight of the current tree and the length from a particular node to all the other ones of the tree...
...Note that in [
7
, 9, 11], only the number of elementary changes is taken into account to measure the level of damage due to the allowed changes in the current tree...
...We x a "relative budget", called quality constraint, on the average distance and we propose an algorithm minimizing simultaneously the average number of elementary changes per stage (as in [
7
, 9, 11]) and the number of critical stages necessary to guarantee this budget constraint at each stage...
Nicolas Thibault
,
et al.
An Optimal Rebuilding Strategy for an Incremental Tree Problem
...delay [
8
, 9] can also be an interesting option to pursue as further research goal...
Debasish Chakraborty
,
et al.
A Distributed Routing Method for Dynamic Multicasting
...The tree has . The random graph and the mesh each have [
19
]...
Hongsuda Tangmunarunkit
,
et al.
Network topology generators: degreebased vs. structural
...Perhaps proving that there is more to this technology than the hype surrounding it would suggest, several research groups have recently designed a variety of peertopeer systems: systems that provide infrastructure for flexibly evolving the Internet [3][4], and systems for largescale network storage [5], anonymous publishing [6], and applicationlevel multicast [7][8][
9
]...
Hui Zhang
,
et al.
Using the smallworld model to improve freenet performance
...The tree has . The random graph and the mesh each have [
15
]...
Hongsuda Tangmunarunkit
,
et al.
Network topologies, power laws, and hierarchy
References
(7)
Balancing Minimum Spanning Trees and ShortestPath Trees
(
Citations: 73
)
Samir Khuller
,
Balaji Raghavachari
,
Neal E. Young
Journal:
Algorithmica
, vol. 14, no. 4, pp. 305321, 1995
The PIM architecture for widearea multicast routing
(
Citations: 584
)
Stephen E. Deering
,
Deborah L. Estrin
,
Dino Farinacci
,
Van Jacobson
,
ChingGung Liu
,
Liming Wei
Journal:
IEEE/ACM Transactions on Networking  TON
, vol. 4, no. 2, pp. 153162, 1996
Multicast routing for multimedia communication
(
Citations: 423
)
Vachaspathi P. Kompella
,
Joseph C. Pasquale
,
George C. Polyzos
Journal:
IEEE/ACM Transactions on Networking  TON
, vol. 1, no. 3, pp. 286292, 1993
How Bad is Naïve Multicast Routing?
(
Citations: 226
)
Matthew Doar
,
Ian M. Leslie
Conference:
IEEE INFOCOM  INFOCOM
, pp. 8289, 1993
OnLine Steine Trees in the Euclidean Plane
(
Citations: 28
)
Noga Alon
,
Yossi Azar
Journal:
Discrete & Computational Geometry  DCG
, vol. 10, pp. 113121, 1993
Sort by:
Citations
(13)
An Optimal Rebuilding Strategy for an Incremental Tree Problem
(
Citations: 1
)
Nicolas Thibault
,
Christian Laforest
Journal:
Journal of Interconnection Networks  JOIN
, vol. 8, no. 1, pp. 7599, 2007
An Optimal Rebuilding Strategy for a Decremental Tree Problem
(
Citations: 4
)
Nicolas Thibault
,
Christian Laforest
Conference:
Colloquium on Structural Information & Communication Complexity  SIROCCO
, pp. 157170, 2006
A Distributed Routing Method for Dynamic Multicasting
(
Citations: 1
)
Debasish Chakraborty
,
Salahuddin Muhammad Salim Zabir
,
Apichet Chayabejara
,
Goutam Chakraborty
Journal:
Telecommunication Systems  TELSYS
, vol. 25, no. 34, pp. 299315, 2004
Network topology generators: degreebased vs. structural
(
Citations: 273
)
Hongsuda Tangmunarunkit
,
Ramesh Govindan
,
Sugih Jamin
,
Scott Shenker
,
Walter Willinger
Conference:
ACM SIGCOMM Conference  SIGCOMM
, pp. 147159, 2002
Using the smallworld model to improve freenet performance
(
Citations: 125
)
Hui Zhang
,
Ashish Goel
,
Ramesh Govindan
Journal:
Computer Communication Review  CCR
, vol. 32, no. 1, pp. 7979, 2002