The Beacon Number Problem in a Fully Distributed Topology Discovery Service

In grid computing the need for collecting information about both distributed computational resources and network topology and performance is constantly growing. Several tools are currently under development to provide such information. They are based either on a centralized or a distributed architecture. Distributed tools are commonly based on IP-level application- oriented network metrology. The measurements are done by means of beacons running in some network nodes (e.g., grid hosts) and collecting the required information. However, the number of utilized beacons might heavily impact the final result, i.e. the discovered topology and the collected performance information. In this study a model is developed to estimate the percentage of discovered links provided that a specific number of beacons is placed in the network. The model is developed for Erdos-Renyi (ER) graph network models but it can be applied also to other networks. Numerical evaluation shows that the model closely approximate the percentage of discovered links obtained through simulation for ER networks. For other theoretical and real networks the model overestimates the percentage of discovered links. However experimental results show that for networks with realistic average nodal degree the overestimate is less than 20%.