A Distributed Algorithm for Throughput Optimal Routing in Overlay Networks

Anurag Rai, Rahul Singh, Eytan Modiano2019 · DOI

TL;DR

This paper introduces the Optimal Overlay Routing Policy (OORP), a novel distributed algorithm designed to maximize throughput in overlay networks built atop legacy underlay networks with fixed routing. OORP overcomes limitations of previous approaches by effectively utilizing underlay queue information, even when this information is not directly available, to achieve near-optimal performance.

What Problem Does This Paper Address?

Modern networks often consist of a dynamic overlay layer built on top of a static, legacy underlay infrastructure. While overlay nodes can implement sophisticated routing policies, the underlay's fixed, often unknown, routing paths can limit the overall achievable throughput. Existing optimal routing algorithms, like backpressure, often struggle in this heterogeneous environment. Specifically, the Overlay Backpressure Policy (OBP) proposed in prior work was found to be suboptimal because it didn't accurately account for congestion within the underlay. This paper tackles the challenge of designing a throughput-optimal routing algorithm for overlay networks that can operate effectively despite the underlay's limitations and lack of direct visibility into its internal state.

Methods

The core of the proposed solution is the Optimal Overlay Routing Policy (OORP). OORP is derived using a classical dual subgradient descent method, a technique commonly used for optimization problems. A key innovation is that OORP can be implemented in a distributed manner, meaning each overlay node can make routing decisions independently.

The algorithm's optimality hinges on utilizing information about the underlay queue lengths. However, a significant practical challenge is that overlay nodes typically do not have direct access to underlay queue lengths. To address this, the paper proposes two methods for estimating underlay queue lengths:

  1. Delay-based estimation: This method uses the time it takes for packets to traverse a tunnel as an indirect measure of congestion.
  2. Priority probe approach: This involves sending special, high-priority "probe" packets through tunnels to gather queue length information.

The paper also presents a centralized solution as a theoretical benchmark before developing the distributed OORP.

Datasets

Not discussed in the paper. The paper relies on simulations using constructed network topologies to evaluate the proposed algorithms.

Key Insights and Ideas

  • Underlay queue information is crucial for optimal overlay routing: Simply relying on overlay-level queue backlogs is insufficient. Understanding underlay congestion is key to avoiding suboptimal routing decisions.
  • OBP's suboptimality stems from ignoring underlay congestion: The counterexample demonstrates how OBP can lead to instability when overlapping tunnels cause cascading congestion in the underlay, a problem it fails to predict.
  • Dual subgradient descent provides a powerful framework: This mathematical tool allows for the derivation of a throughput-optimal policy that can be implemented distributively.
  • Queue lengths as a proxy for dual variables: The paper cleverly shows that underlay queue lengths can serve as practical approximations for the dual variables needed in the optimization, even if they are not perfect.
  • Estimating underlay congestion is feasible and effective: The proposed estimation techniques, particularly the priority probe approach, allow OORP to achieve near-optimal performance without direct access to underlay queue data.

Key Results

  • OORP is throughput optimal: The paper proves that OORP is throughput optimal for overlay networks built on universally stable underlay networks.
  • Counterexample to OBP: The paper provides a concrete network scenario where the Overlay Backpressure Policy (OBP) becomes unstable, demonstrating its suboptimality.
  • OORP outperforms OBP: Simulations show OORP achieving significantly better throughput than OBP, especially under higher loads and in congested scenarios.
  • Effective queue length estimation: The priority probe approach for estimating underlay queue lengths allows OORP to achieve performance very close to using actual queue lengths, outperforming simpler delay-based estimation methods.
  • Robustness to background traffic: OORP remains effective even when the underlay carries background traffic, demonstrating its practical applicability.

Limitations and Future Work

  • Underlay knowledge limitations: While OORP can estimate underlay congestion, it still relies on some assumptions about the underlay (e.g., work-conserving forwarding). Direct knowledge of underlay queue lengths would theoretically lead to perfect optimality.
  • Estimation accuracy: While the priority probe approach is effective, its performance can be impacted by the chosen probing interval (T). The delay-based estimation method can be arbitrarily inaccurate in certain scenarios.
  • Future work: The authors suggest exploring better methods for estimating underlay congestion with minimal underlay support and reducing packet delays within the network. They also mention the potential for extending OORP to handle scenarios where underlay sources and destinations are involved.

Summary updated

Abstract

We address the problem of optimal routing in overlay networks. An overlay network is constructed by adding new overlay nodes on top of a legacy network. The overlay nodes are capable of implementing any dynamic routing policy, however, the legacy underlay has a fixed, single path routing scheme and uses a simple work-conserving forwarding policy. Moreover, the underlay routes are pre-determined and unknown to the overlay network. The overlay network can increase the achievable throughput of the legacy network by using multiple routes, which consist of direct routes and indirect routes through other overlay nodes. We develop an optimal dynamic routing algorithm for such overlay networks called the Optimal Overlay Routing Policy (OORP). OORP is derived using the classical dual subgradient descent method, and it can be implemented in a distributed manner. We show that the queue-lengths can be used as a substitute for the dual variables in the algorithm. However, the underlay queue-lengths are unknown to the overlay, so we propose two regression based schemes that learn simplified models of the backlog in the underlay using historical data and use them to estimate the queue-lengths in real time. Simulation results show that near-optimal performance can be achieved without any knowledge of the underlay.
BibTeX
@misc{rai2019distributed,
  author = {Anurag Rai and Rahul Singh and Eytan Modiano},
  title = {{A Distributed Algorithm for Throughput Optimal Routing in Overlay Networks}},
  year = {2019},
  doi = {10.23919/ifipnetworking.2019.8816834},
}
Figure