Adaptive Probabilistic Flooding for Multipath Routing

Christophe Betoule, Thomas Bonald, Remi Clavier, Dario Rossi, Giuseppe Rossini, Gilles Thouénon

TL;DR

This paper introduces Adaptive Probabilistic Flooding, a distributed algorithm designed to discover multiple paths between network nodes while avoiding the "broadcast storm" of traditional flooding. By using a simple probabilistic backoff mechanism, the approach achieves near-optimal multipath discovery with message overhead that scales linearly with network size, making it a viable "plug-and-play" control plane for power-efficient source routing.

What Problem Does This Paper Address?

Modern Internet routing relies heavily on IP address lookups, which consume significant power as routing tables grow. A potential solution is to move toward level-2 (Ethernet-like) architectures using source routing, where the path information is stored in the packet header rather than in the routers' memory.

However, source routing requires an efficient way for nodes to discover these paths. Traditional path discovery relies on flooding—broadcasting a discovery message to all neighbors. While effective at finding the shortest path, pure flooding is notoriously unscalable because the number of messages explodes exponentially. Existing alternatives for finding multiple paths (for redundancy and load balancing) are often too complex, centralized, or require routers to maintain extensive state information. The authors aim to find a middle ground: a distributed, scalable, and simple algorithm for multipath discovery.

Methods

The authors propose a novel level-2 architecture where core nodes maintain no routing tables. Instead, they use Adaptive Probabilistic Flooding:

  1. Source Routing: The source node inserts a stack of labels into the packet header. Each relay node simply "pops" the top label and forwards the packet accordingly.
  2. The Discovery Algorithm: To find paths, a source node periodically sends an advertisement message.
  3. Probabilistic Backoff: When a relay node $i$ receives a discovery message from source $s$, it doesn't just flood it every time. Instead, it forwards the message with a probability $P$ defined by: $$P = \beta^{n_{i,s}}$$ Where $\beta$ is a fixed backoff parameter (between 0 and 1) and $n_{i,s}$ is a counter of how many times node $i$ has already received a discovery message from source $s$ during the current discovery phase.

  4. Path Selection: The first message to arrive typically represents the shortest path (the "primary" path). Subsequent messages, which arrive with decreasing probability, allow the node to learn "secondary" paths that are ideally disjoint from the primary one to ensure resilience.

Datasets

The researchers evaluated their algorithm using the Omnet++ discrete event simulator across four distinct network topologies:

  • Tiger2: A hierarchical metro network (22 nodes).
  • Geant: A European research aggregation network (22 nodes).
  • Abilene: A high-performance backbone core network (11 nodes).
  • Random: A set of 50 synthetic random graphs (22 nodes each) used to ensure the results weren't specific to one topology.

Key Insights and Ideas

  • Linear Scalability: Unlike pure flooding, which is exponential, the authors prove analytically that their method's overhead is $O(N)$—meaning it scales linearly with the number of nodes.
  • Self-Termination: The probabilistic decay ($P = \beta^n$) acts as a natural "auto-terminating" mechanism. It doesn't require perfectly tuned Time-To-Live (TTL) values, which are often difficult to set in dynamic networks.
  • The "Aha" Moment on $\beta$: The algorithm is surprisingly robust to the choice of the backoff parameter $\beta$. As long as $\beta$ is reasonably high (around 0.7 to 0.8), the network consistently finds high-quality secondary paths without a massive surge in control messages.
  • Minimal State: Routers only need to store a small counter per source node ($O(N)$ state), which is far less demanding than maintaining full routing tables.

Key Results

  • Overhead Control: Simulations confirmed the analytical upper bound for message overhead. For a typical network, the number of discovery messages remains in the low hundreds, even for high values of $\beta$.
  • Connectivity: The primary (shortest) path is always found. Secondary paths are discovered with >90% probability once $\beta \ge 0.7$.
  • Path Quality: The discovered secondary paths are highly effective for resilience. Even in the worst-case scenarios, the secondary paths shared only about 1.5 nodes on average with the primary path, providing excellent diversity for fault tolerance.
  • Optimality: At $\beta = 0.8$, the algorithm finds the "optimal" secondary path (the shortest path among those with minimum overlap) in nearly all tested topologies.

Limitations and Future Work

The authors acknowledge a few areas for further development:

  • Static Assumptions: The current evaluation assumes homogeneous link delays and no link failures during the discovery process itself.
  • State Reduction: While $O(N)$ state is better than traditional routing, the authors suggest that by staggering advertisement periods, they might be able to reduce the required state to $O(1)$ (constant state) per router.
  • Dynamic Traffic: Future work will look at how the algorithm performs under heterogeneous delays and active traffic surges.

Summary updated

Abstract

In this work, we develop a distributed source routing algorithm for topology discovery, suitable for ISP transport networks, that is however inspired by opportunistic algorithms used in ad hoc wireless networks. We propose a plug-and-play control plane, able to find multiple paths toward the same destination, and introduce a novel algorithm, called adaptive probabilistic flooding, to achieve this goal. By keeping a small amount of state in routers taking part in the discovery process, our technique significantly limits the amount of control messages exchanged with flooding - and, at the same time, it only minimally affects the quality of the discovered multiple path with respect to the optimal solution. Simple analytical bounds, confirmed by results gathered with extensive simulation on several topologies (up to 10,000 nodes), show our approach to be of high practical interest.
BibTeX
@inproceedings{betoule2012adaptive,
  author = {Christophe Betoule and Thomas Bonald and Remi Clavier and Dario Rossi and Giuseppe Rossini and Gilles Thouénon},
  title = {{Adaptive Probabilistic Flooding for Multipath Routing}},
  booktitle = {NTMS},
  year = {2012},
  doi = {10.1109/ntms.2012.6208696},
}
Figure