Efficient Search Algorithms in the Presence of Measurement Uncertainty

In this work, we study the problem of efficient resource selection in real-time distributed systems. Specifically, we 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." We parameterize the problem based on the number of available targets, the number of "good" targets, and various network characteristics. We introduce a framework called spatial slow start (SSS) for searching the target space. SSS can be considered as a parameterized tree search with an interesting twist: apart from the target search space, the rate of probing per target is also manipulated at each step. A detailed simulation study provides insight on what SSS choices are significant under different network conditions. The simulation study also establishes that previously proposed techniques, namely, a random selection (RAND) algorithm that does not do any probing, and a "quick probe and select the best" (QPS) technique work well, but only in some situations. Based on these insights, we present an adaptive SSS algorithm that not only guides the search process according to its measurements of various system parameters, but also changes its search parameters in response to the quality of the measurements themselves. This new adaptive SSS algorithm performs as well as RAND and QPS in situations where RAND and QPS are efficient, and outperforms them in other cases.