Using Collective Intelligence to Route Internet Traffic

David H. Wolpert, Kagan Tumer, Jeremy FrankNeurIPS 1998

Introduction

This paper introduces the COllective INtelligence (COIN) framework for designing distributed reinforcement learning agents that work together to optimize a global goal without centralized control. By applying this framework to internet traffic routing, the authors demonstrate that agents using a "Wonderful Life Utility" reward can outperform traditional shortest-path algorithms—even when the COIN agents have significantly less information about the network.

The Routing Problem

In large-scale distributed systems like the internet, routing is a massive challenge. Traditional approaches often rely on Shortest Path Algorithms (SPAs). The fundamental flaw with SPAs is that they are "greedy." Every router attempts to send its packets along the quickest path for that specific packet.

This leads to a classic "tragedy of the commons": when every router greedily picks the same optimal path, that path becomes congested, and the overall network performance (global utility) plummets. While centralized control could theoretically solve this, it is impossible to implement at the scale and speed of the modern internet. The core challenge is determining how to reward individual routers so that their selfish pursuit of a "local" reward naturally results in the best possible "global" outcome.

The COIN Framework

To address this, the authors propose the COIN framework, viewing the system as a recurrent neural network of "neurons," where each neuron is an independent Reinforcement Learning (RL) agent.

  • Microlearners vs. Macrolearners: Each router (neuron) utilizes a microlearner (an RL algorithm) trying to maximize its local utility. A macrolearner periodically updates those local utility functions to ensure they stay aligned with the global goal.
  • The Wonderful Life Utility (WLU): To prevent agents from working at cross-purposes, the authors use a specific mathematical reward function called the WLU. The WLU for a specific subworld (a group of neurons) is calculated as the difference between the Global Utility with the subworld present and the Global Utility if the subworld's states were set to zero. Essentially, it asks: "How much better is the network because this specific group of routers is doing what it's doing?"
  • Factored Systems: The authors prove that if a system is "subworld-factored"—meaning an increase in local utility always implies an increase in global utility—the agents will naturally converge toward a Nash equilibrium representing a near-optimal global state.

Experimental Setup

The study evaluates the algorithms using two simulated network topologies, designated as Network A and Network B.

Network Topologies A and B

These are small-to-medium-scale synthetic network architectures designed with specific bottlenecks (notably at "Router 2") to test how different algorithms handle congestion. The algorithms were evaluated under three different traffic loads: Light, Medium, and Heavy. Specific nodes were designated as sources and ultimate destinations to create realistic flow patterns.

Results and Insights

The authors compared three routing approaches: a Full Knowledge SPA (FK SPA), a Full Knowledge COIN (FK COIN), and a Memory-Based COIN (MB COIN).

  • The Gold Standard: The FK COIN achieved the theoretical optimum performance across the tests.
  • The SPA Gap: The FK SPA performed 12.5% ± 3% worse than the optimum, representing the performance ceiling for any traditional RL-based shortest-path algorithm.
  • The COIN Advantage: Surprisingly, even with limited, local-only information, the MB COIN was 36% ± 8% closer to the optimum than the FK SPA. This suggests that the incentive structure (the reward function) is far more critical than the amount of data available to the agent.
Total Delay per Packet over Time

Visualizations of the "Total Delay" over time highlight the stability of the COIN approach. The COIN agents settled into an efficient solution much more rapidly and with significantly less oscillation than the greedy SPA approach, which struggled with continuous congestion and rerouting cycles. Furthermore, the WLU demonstrated "Dynamics Independence," meaning it doesn't require the agent to know the underlying physics or dynamics of the system—only the current global utility and its own contribution.

Limitations and Future Work

While promising, the study acknowledges several limitations:

  • Scale: The networks used (Network A and B) are relatively small. The theories need further testing on larger, industrial-scale event-driven simulators.
  • Macrolearning: The current paper focused primarily on setting the local utilities. Future work should explore automated, run-time modification of these utility functions to further improve the system's alignment.
  • Constraint-Alignment: The theory works best when neurons in different subworlds don't interfere with each other directly. In real-world routing, this alignment isn't always perfect, and more research is needed to understand how COINs handle highly "frustrated" or messy systems.

Summary updated

BibTeX
@inproceedings{wolpert1998using,
  author = {David H. Wolpert and Kagan Tumer and Jeremy Frank},
  title = {{Using Collective Intelligence to Route Internet Traffic}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
}
Figure