Efficient Search Algorithms in the Presence of Measurement Uncertainty

In this paper, the authors study the problem of efficient resource selection in real-time distributed systems. Specifically, they study how a client in the presence of measurement uncertainty can rapidly select a resource (target) that exhibits good network connectivity. The problem has many applications, including peer selection in P2P systems, server/gateway selection in IP Telephony, and overlay routing. A probing-based search strategy is complicated by the potentially large number of targets and the inherent uncertainty in measurement results due to, for instance, small measurement sample sizes and other forms of "Noise." They parameterize the problem based on the number of available targets, the number of "Good" targets, and various network characteristics.