Optimal Routing for Delay-Sensitive Traffic in Overlay Networks

Rahul Singh, Eytan Modiano

Abstract

We design dynamic routing policies for an overlay network which meet delay requirements of real-time traffic being served on top of an underlying legacy network, where the overlay nodes do not know the underlay characteristics. We pose the problem as a constrained MDP, and show that when the underlay implements static policies such as FIFO with randomized routing, then a decentralized policy, that can be computed efficiently in a distributed fashion, is optimal. Our algorithm utilizes multi-timescale stochastic approximation techniques, and its convergence relies on the fact that the recursions asymptotically track a nonlinear differential equation, namely the replicator equation. Extensive simulations show that the proposed policy indeed outperforms the existing policies.
BibTeX
@misc{singh2017optimal,
  author = {Rahul Singh and Eytan Modiano},
  title = {{Optimal Routing for Delay-Sensitive Traffic in Overlay Networks}},
  year = {2017},
  eprint = {1703.07419},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1703.07419},
}

Loading related content...

Figure