Computer Science – Networking and Internet Architecture
Scientific paper
2007-02-27
Random Structures and Algorithms, 35(2):194-215, September 2009
Computer Science
Networking and Internet Architecture
Scientific paper
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.
Guillemin Fabrice
Robert Philippe
No associations
LandOfFree
Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-206792