Mechanisms for Internet Routing: A Study

Aditya Akella, Shuchi Chawla, Srinivasan Seshan2002 · DOI

TL;DR

This paper tackles the problem of routing in the internet from a game-theoretic perspective, aiming to design routing schemes that ensure good network performance despite selfish user behavior. They extend existing models of Nash equilibria to more realistic scenarios and propose a mechanism that can lead to socially optimal routing, even in the presence of greedy agents.

What Problem Does This Paper Address?

The internet's routing mechanisms are designed to handle traffic from many independent users, each acting in their own self-interest to minimize their latency. This "selfish routing" can lead to suboptimal overall network performance, a phenomenon known as "anarchy." While game theory has been used to analyze this, existing models often simplify the internet's complexity (e.g., using linear latency functions or assuming perfectly divisible flows). This paper aims to bridge this gap by:

  1. Extending existing Nash equilibrium models: They analyze scenarios with non-linear latency functions and consider different agent behaviors (e.g., packet-level vs. flow-level agents).
  2. Designing practical routing mechanisms: The goal is not to price network usage but to guide selfish agents towards actions that benefit the entire network, leading to a more efficient and robust internet.

Methods

The authors employ a two-pronged approach:

  1. Revisiting and extending Nash equilibrium models: They analyze the "price of anarchy" – the ratio of the worst-case Nash equilibrium cost to the optimal social cost. This involves:
  2. Modeling agents: They consider three types of agents: individual packets, single-unit flows, and flows with mixed strategies.
  3. Modeling social cost: They define social cost as either the average latency across all links or the maximum latency across all links.
  4. Analyzing latency functions: They move beyond linear latency functions to include polynomial functions, which better approximate real-world internet link behavior.
  5. Designing routing mechanisms: Based on their analysis of Nash equilibria, they propose a mechanism to achieve social optimum. This mechanism involves setting "shadow prices" on links, which are derived from the gradient of the link's latency function. They argue that this mechanism can be implemented in a distributed manner using existing internet protocols like TCP's Congestion Notification bit.

Datasets

Not discussed in the paper. The authors mention collecting traces from Akamai to study flow arrival patterns for future work, but no datasets were used for evaluation in this paper.

Key Insights and Ideas

  • Anarchy can be arbitrarily bad: For certain network configurations and latency functions, the performance of selfish routing (Nash equilibrium) can be significantly worse than the optimal, socially desirable routing.
  • Non-linear latencies matter: Moving beyond linear latency functions reveals more nuanced behaviors and challenges in achieving social optimum.
  • A distributed mechanism is feasible: The proposed "shadow pricing" mechanism can be implemented using existing internet infrastructure, making it a practical solution.
  • Short-lived flows can stabilize the system: The presence of many short-lived, selfish flows can help the network converge to a stable, near-optimal state, even in the presence of longer-lived flows.

Key Results

  • They analyze the "price of anarchy" for various scenarios, showing that for linear latency functions and pure strategies, the Nash cost is at most 4/3 times the optimal cost for average latency. For maximum latency, the ratio can be up to log m for m links.
  • They demonstrate that for certain scenarios (e.g., minimizing maximum latency with pure strategies), Nash equilibrium and social optimum can be the same.
  • They propose a mechanism that, under certain conditions (e.g., splitable flows or high granularity of flows), provably leads to social optimum. They argue this condition holds for the internet.

Limitations and Future Work

  • Rigorous proof for unsplitable flows: While they argue intuitively that their mechanism works for unsplitable flows (common in the internet), a formal proof is lacking.
  • Mixed strategies for maximum latency: They were unable to design a suitable mechanism for minimizing expected maximum latency when agents are free to use mixed strategies.
  • Practical implementation details: Further work is needed to determine optimal update intervals for shadow prices, the applicability to backbone vs. peering networks, and how to handle the interaction between short-lived and long-lived flows.
  • Empirical validation: They plan to collect real-world traces and use network simulators to test their assumptions and the performance of their proposed routing scheme.
  • Quality of Service: Future work includes extending the mechanism to provide different levels of service based on pricing.

Summary updated

Abstract

In this paper, we address the issue of Routing in the Internet from a Game Theoretic perspective. We adopt a two-pronged strategy: firstly, we revisit two `classic' models of the Nash equilibria of a network of selfish flows in the Internet and extend their results for Nash equilibria to what we believe are more realistic settings (for example, we present results for non-linear latency functions). Secondly, we apply our results, as well as the `classic' results, for Nash equilibria to designing Routing schemes for networks. The goal of such schemes is not to price network usage but rather to ensure sound overall network performance in the presence of greedy behavior of the participating flows. Finally, we show how our results can be employed to build a Wide-Area routing scheme.
BibTeX
@misc{akella2002mechanisms,
  author = {Aditya Akella and Shuchi Chawla and Srinivasan Seshan},
  title = {{Mechanisms for Internet Routing: A Study}},
  year = {2002},
  doi = {10.21236/ada461171},
}
Figure