Return to search

Analysis of beacon triangulation in random graphs

Our research focusses on the problem of finding nearby peers in the Internet.
We focus on one particular approach, Beacon Triangulation that is widely used to
solve the peer-finding problem. Beacon Triangulation is based on relative distances
of nodes to some special nodes called beacons. The scheme gives an error when a
new node that wishes to join the network has the same relative distance to two or
more nodes. One of the reasons for the error is that two or more nodes have the
same distance vectors. As a part of our research work, we derive the conditions to
ensure the uniqueness of distance vectors in any network given the shortest path
distribution of nodes in that network. We verify our analytical results for G(n, p)
graphs and the Internet. We also derive other conditions under which the error in the
Beacon Triangulation scheme reduces to zero. We compare the Beacon Triangulation
scheme to another well-known distance estimation scheme known as Global Network
Positioning (GNP).

Identiferoai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/1447
Date17 February 2005
CreatorsKakarlapudi, Geetha
ContributorsLoguinov, Dmitri
PublisherTexas A&M University
Source SetsTexas A and M University
Languageen_US
Detected LanguageEnglish
TypeBook, Thesis, Electronic Thesis, text
Format438110 bytes, electronic, application/pdf, born digital

Page generated in 0.002 seconds