Efficient search algorithms in the presence of measurement uncertainty

Bengi Karacali, Mark Karol, P. Krishnan, Beilei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationICC 2008 - IEEE International Conference on Communications, Proceedings
Pages360-365
Number of pages6
DOIs
StatePublished - 2008
EventIEEE International Conference on Communications, ICC 2008 - Beijing, China
Duration: 19 May 200823 May 2008

Publication series

NameIEEE International Conference on Communications
ISSN (Print)0536-1486

Conference

ConferenceIEEE International Conference on Communications, ICC 2008
Country/TerritoryChina
CityBeijing
Period19/05/0823/05/08

Fingerprint

Dive into the research topics of 'Efficient search algorithms in the presence of measurement uncertainty'. Together they form a unique fingerprint.

Cite this