TY - GEN
T1 - Efficient search algorithms in the presence of measurement uncertainty
AU - Karacali, Bengi
AU - Karol, Mark
AU - Krishnan, P.
AU - Zhan, Beilei
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=51249111071&partnerID=8YFLogxK
U2 - 10.1109/ICC.2008.74
DO - 10.1109/ICC.2008.74
M3 - Conference contribution
AN - SCOPUS:51249111071
SN - 9781424420742
T3 - IEEE International Conference on Communications
SP - 360
EP - 365
BT - ICC 2008 - IEEE International Conference on Communications, Proceedings
T2 - IEEE International Conference on Communications, ICC 2008
Y2 - 19 May 2008 through 23 May 2008
ER -