Encodings of Multicast Trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2004

Encodings of Multicast Trees

Résumé

In this paper, we present efficient ways of encoding multicast trees. Multicast tree encodings provide a convenient way of performing stateless and explicit multicast routing in networks and overlays. We show the correspondence of multicast trees to theoretical tree data structures and give lower bounds on the number of bits needed to represent multicast trees. Our encodings can be used to represent multicast trees using both node identifiers and link indexes and are based on balanced parentheses representation of tree data structures. These encodings are almost space optimal and can be read and processed efficiently. We evaluate the length of these encodings on multicast trees in generated and real topologies.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5442.pdf (297.22 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00070565 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070565 , version 1

Citer

Vijay Arya, Thierry Turletti, Shivkumar Kalyanaraman. Encodings of Multicast Trees. [Research Report] RR-5442, INRIA. 2004, pp.21. ⟨inria-00070565⟩
46 Consultations
216 Téléchargements

Partager

Gmail Facebook X LinkedIn More