Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States

Details Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States

2012-01-24

arxiv.org/abs/1201.4906v1

Computer Science

Networking and Internet Architecture

10 pages, 1 figure

Scientific paper

We consider the adaptive shortest-path routing problem in wireless networks under unknown and stochastically varying link states. In this problem, we aim to optimize the quality of communication between a source and a destination through adaptive path selection. Due to the randomness and uncertainties in the network dynamics, the quality of each link varies over time according to a stochastic process with unknown distributions. After a path is selected for communication, the aggregated quality of all links on this path (e.g., total path delay) is observed. The quality of each individual link is not observable. We formulate this problem as a multi-armed bandit with dependent arms. We show that by exploiting arm dependencies, a regret polynomial with network size can be achieved while maintaining the optimal logarithmic order with time. This is in sharp contrast with the exponential regret order with network size offered by a direct application of the classic MAB policies that ignore arm dependencies. Furthermore, our results are obtained under a general model of link-quality distributions (including heavy-tailed distributions) and find applications in cognitive radio and ad hoc networks with unknown and dynamic communication environments.

Affiliated with

Also associated with

No associations

Rating

Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-106485