Optimal Sampling Strategies for Minimum Latency Routing with Imperfect Link State
Saikat Guha, Don Towsley, Prithwish Basu, Timothy Freeman, Dmitriy Katz, Robert E. Hancock, Jim Kurose · 2012
Abstract—Since dynamic wireless networks evolve over time, optimal routing computations need to be performed frequently on time-varying network topologies. However, it is often infeasible or expensive to gather the current state of links for the entire network all the time. We provide a thorough analytical charac-terization of the effect of various link-state sampling strategies operating under a limited sampling budget on the performance of the minimum-latency routing policy in a special class of dynamic networks. We show that for a two-state Markov link-dynamics model parameterized by probabilities p, q, if links are more likely to turn on than off at each time instant (p> q), a “depth-first” sampling strategy is optimal, whereas a “breadth-first ” sampling strategy is optimal if links are more likely to turn off than on (p < q)—under the Cut Through (CuT) latency model, i.e., when the packet-forwarding latency is negligible compared to the time scale of the link dynamics. We precisely characterize the optimal-latency spatial-sampling schedules for one-shot interrogation. We also present numerical simulation results on comparing various spatio-temporal sampling schedules under an overall sampling rate constraint, and initial results on comparisons of optimal schedules under a Store-and-Advance (SoA) packet-forwarding latency model. I.