  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.
