106
reads

Ying-Chao Hung

2011-11-25
12:50:00 - 14:30:00

400-1 , Mathematics Research Center Building (ori. New Math. Bldg.)

In this talk we introduce a fundamental routing problem in data networks. The goal is to construct the optimal strategy of selecting the network downlinks to transmit the data so that the long-run data loss rate can be minimized. Such a problem can be simply modeled as a “multi-armed bandit problem” that already has a wide range of applications in clinical trials, on-line industrial experimentations, etc. We examine this bandit problem from a Bayesian perspective: Assume the unknown Bernoulli parameters (e.g., the data loss rate for each link) are independent observations from a common distribution F, and the objective is then to provide strategies of selecting arms at each decision epoch so that the expected long run failure rate is minimized (i.e., as the number of trials goes to infinity). When the common distribution F is known, we prove that three strategies proposed by Berry et al. (1997) minimize the expected long run failure rate. When F is unknown, we propose a new strategy and prove that it is asymptotically optimal. Numerical results from computer simulations are also provided to evaluate the performance of the proposed strategies.