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.
Introduction and Problem Statement
Modern internet services such as live streaming, online gaming, and high-frequency financial trading are extremely sensitive to end-to-end delay. These services often operate as overlay networks—logical networks built on top of existing "legacy" underlay infrastructures (like the standard Internet) that they do not directly control.
This architecture presents two primary challenges for routing: an Information Gap, where overlay nodes lack knowledge of the underlay's topology, link capacities, or internal routing schemes; and Congestion Awareness, where traditional throughput-focused protocols may select high-capacity paths that suffer from massive queuing delays. The goal is to develop a decentralized routing algorithm that can "learn" optimal paths in an online fashion while keeping total network delay below a specific target.
The Price-based Overlay Controller (POC)
To address these challenges, the authors introduce the Price-based Overlay Controller (POC). This decentralized routing algorithm combines Q-learning with evolutionary game theory to achieve optimal delay performance without requiring global network knowledge. The POC is structured as a three-layer adaptive controller operating on distinct timescales:
- The Routing Layer (Fastest): Each source node employs Q-learning to determine a routing policy. Rather than simply seeking the shortest path, it minimizes a "holding cost" derived from dynamic link prices.
- The Price Controller (Medium): Utilizing stochastic gradient descent, this layer adjusts link prices ($\lambda$). If a link's average queue exceeds its assigned budget, the price increases, signaling the routing layer to divert traffic elsewhere.
- The Threshold Tuner (Slowest): This novel component uses the Replicator Equation from evolutionary game theory to adaptively distribute a total delay budget ($B$) across links. It effectively "evolves" the budget toward links that are most critical or congested, signaling hidden underlay characteristics back to the overlay.
By operating these layers at different speeds, the system ensures that routing policies stabilize before prices change, and prices stabilize before the global budget is redistributed.
Key Insights and Results
The authors prove that despite nodes only having access to local queue data and link prices, the resulting decentralized policy is mathematically optimal for global delay constraints. By applying Little’s Law, the abstract goal of minimizing end-to-end delay is transformed into the measurable objective of maintaining low average queue lengths.
In extensive simulations, the POC demonstrated significant performance gains:
- Superior Delay Performance: The POC achieved a 40% reduction in delay compared to the Overlay Back Pressure (OBP) algorithm while maintaining the same throughput (37 units vs. 62.7 units).
- Scalability: By integrating Neural Networks (Deep Q-Learning) for function approximation, the POC successfully handled larger network topologies (up to 12 nodes) without succumbing to the "curse of dimensionality."
- Robustness: The system remained stable and met delay bounds even as traffic arrival rates increased or followed complex, non-i.i.d. Markovian patterns.
Limitations and Future Outlook
While the POC offers a robust framework for delay-sensitive routing, its effectiveness depends on the achievability of the user-defined delay bound ($B$). If $B$ is set below the physical capacity of the underlay, the algorithm cannot meet the constraint. Future research may focus on automatically estimating the "best possible" delay bound. Additionally, while the current proof assumes simple underlay policies like FIFO, extending the framework to interact with more complex, dynamic underlay scheduling remains an open area of study.
Summary updated