Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms

Abstract : We consider in this paper the problem of discovering, via a traceroute algorithm, the topology of a network, whose graph is spanned by an infinite branching process. A subset of nodes is selected according to some criterion. As a measure of efficiency of the algorithm, the Steiner distance of the selected nodes, i.e. the size of the spanning sub-tree of these nodes, is investigated. For the selection of nodes, two criteria are considered: A node is randomly selected with a probability, which is either independent of the depth of the node (uniform model) or else in the depth biased model, is exponentially decaying with respect to its depth. The limiting behavior the size of the discovered subtree is investigated for both models.
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00133676
Contributeur : Philippe Robert <>
Soumis le : vendredi 6 juin 2008 - 12:09:40
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : mardi 21 septembre 2010 - 16:26:19

Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

  •  tree.pdf Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00133676, version 2
  • ARXIV : cs/0702156

Collections

Citation

Fabrice Guillemin, Philippe Robert. Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms. Preprint. 2008. 〈inria-00133676v2〉

Partager

Métriques

Consultations de la notice

232

Téléchargements de fichiers

169