Skip to Main content Skip to Navigation

Performance Metrics for Multicast Flows on Random Trees

Bartlomiej Blaszczyszyn 1 Konstantin Tchoumatchenko
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : We consider a flow of data packets from one source to many destinations in a communication network represented by a random oriented tree. The multicast mode is characterized by the ability of some tree vertices to replicate the received packets in a way which depends on the number of destinations downstream. We are interested in the cost of packet delivery and in several performance metrics associated with multicast flows on Galton--Watson trees and trees generated by point aggregates of a Poisson process. Such stochastic settings are intended to represent tree-shapes arising in the Internet and in some ad hoc networks. The main result, in the branching process case, is a functional equation for the p.g.f. of the flow volume; we provide conditions for the existence and uniqueness of a solution and a method to compute it using Picard iterations. In the point process case, we use the stochastic comparison technique developed in percolation theory for Boolean models to provide bounds on the introduced cost functions. We use these results to derive a number of characteristics of these random trees and discuss applications to analytical evaluation of costs and loads induced on a network by a multicast session.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:04:01 PM
Last modification on : Tuesday, September 22, 2020 - 3:57:53 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:58:10 PM


  • HAL Id : inria-00072200, version 1



Bartlomiej Blaszczyszyn, Konstantin Tchoumatchenko. Performance Metrics for Multicast Flows on Random Trees. [Research Report] RR-4388, INRIA. 2002. ⟨inria-00072200⟩



Record views


Files downloads