Sylvia Ratnasamy and Steven McCanne

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-1019
October 1998

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-1019.pdf

The efficacy of end-to-end multicast transport protocols depends critically upon their ability to scale efficiently to a large number of receivers. Several research multicast protocols attempt to achieve this high scalability by identifying sets of co-located receivers in order to enhance loss recovery, congestion control and so forth. A number of these schemes could be enhanced and simplified by some level of explicit knowledge of the topology of the multicast distribution tree, the value of the bottleneck bandwidth along the path between the source and each individual receiver and the approximate location of the bottlenecks in the tree. In this paper, we explore the problem of inferring the internal structure of a multicast distribution tree using only observations made at the end hosts. By noting correlations of loss patterns across the receiver set and by measuring how the network perturbs the fine-grained timing structure of the packets sent from the source, we can determine both the underyling multicast tree structure as well as the bottleneck bandwidths. Our simulations show that the algorithm is robust and appears to converge to the correct tree with high probability.

BibTeX citation:

@techreport{Ratnasamy:CSD-98-1019,
    Author = {Ratnasamy, Sylvia and McCanne, Steven},
    Title = {Inference of Multicast Routing Trees and Bottleneck Bandwidths using End-to-end Measurements},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1998},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/6408.html},
    Number = {UCB/CSD-98-1019},
    Abstract = {The efficacy of end-to-end multicast transport protocols depends critically upon their ability to scale efficiently to a large number of receivers. Several research multicast protocols attempt to achieve this high scalability by identifying sets of co-located receivers in order to enhance loss recovery, congestion control and so forth. A number of these schemes could be enhanced and simplified by some level of explicit knowledge of the topology of the multicast distribution tree, the value of the bottleneck bandwidth along the path between the source and each individual receiver and the approximate location of the bottlenecks in the tree. In this paper, we explore the problem of inferring the internal structure of a multicast distribution tree using only observations made at the end hosts. By noting correlations of loss patterns across the receiver set and by measuring how the network perturbs the fine-grained timing structure of the packets sent from the source, we can determine both the underyling multicast tree structure as well as the bottleneck bandwidths. Our simulations show that the algorithm is robust and appears to converge to the correct tree with high probability.}
}

EndNote citation:

%0 Report
%A Ratnasamy, Sylvia
%A McCanne, Steven
%T Inference of Multicast Routing Trees and Bottleneck Bandwidths using End-to-end Measurements
%I EECS Department, University of California, Berkeley
%D 1998
%@ UCB/CSD-98-1019
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/6408.html
%F Ratnasamy:CSD-98-1019