Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms - Archive ouverte HAL Access content directly
Other Publications Year : 2008

Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms

(1) , (2)
1
2
Fabrice Guillemin

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.
Fichier principal
Vignette du fichier
main.pdf (249.09 Ko) Télécharger le fichier
Vignette du fichier
tree.pdf (31.89 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00133676 , version 1 (27-02-2007)
inria-00133676 , version 2 (06-06-2008)

Identifiers

Cite

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

Collections

INRIA INRIA2
92 View
245 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More