The Space Requirement of Local Forwarding on Acyclic Networks

Boaz Patt-Shamir and Will Rosenbaum

Tel Aviv University

Overview

  1. Background
  2. Statement of Results
  3. A Few Details
    • Upper Bounds
    • Lower Bounds

Background

General Question: How do we efficiently move packets from source to destination in a network?

For this talk

  • network is rooted tree (more generally, a DAG)
  • packets all have same destination (root)
  • packets injected adversarially
  • efficiency is size of buffers required to deliver all packets without overflows

Adversarial Model

If we don't restrict injection patterns, buffers may grow arbitrarily large!

Adversarial Queuing Theory model

  • Injection/forwarding in synchronous rounds
  • Each edge forwards at most $c$ packets in a round
  • Each packet is injected with a specified route to its destination
  • $(\rho, \sigma)$-bounded: in any $t$ consecutive time steps, no more than $\rho t + \sigma$ injected packets must cross any edge

For $(\rho, \sigma) = (1, 0)$, in each round routes of injected packets must be disjoint

A Few Previous Results

  1. If $G$ is a DAG, then buffers of size $O(n)$ are sufficient [Alder & Rosen, 2002]
    • greedy protocol, LIS scheduling
  2. If $G$ is a single destination tree, then buffers of size $O(\rho + \sigma)$ are necessary and sufficient [Miller & Patt-Shamir, 2016]
    • centralized protocol
  3. Any greedy protocol requires buffers of size $\Omega(n)$ (above two papers)

Question What is the best a local algorithm can do?

Our Main Results (1/2)

Theorem 1. Let $G = (V, E)$ be a single destination tree of depth $D$ with edge capacities $c$. There exists a $2$-local algorithm that requires buffer size $O(\sigma + \rho \log D)$ against any $(\rho, \sigma)$ adversary for $\rho \leq c$.

Theorem 2. Any $O(1)$-local algorithm requires buffers of size $\Omega(\sigma + \rho \log D)$ against some $(\rho, \sigma)$ adversary.

Our Main Results (2/2)

Theorem 3. For the families of multiple destination paths and single source/single destination DAGs, for every $\rho > \frac 1 2$, there exists a $(\rho, \sigma)$ adversary that requires buffers of size $\Omega(n)$ against all (centralized, offline) protocols.

Theorem 4. For $\rho = c$, sublinear loads and finite delay$^*$ cannot be simultaneously acheived. For $\rho < c$, the algorithm of Theorem 1 has maximum delay $O\left(\frac{D}{c - \rho}\right)$.

* - delay is the maximum number of steps between when a packet is injected and when it is delivered

For the Rest of the Talk

  • Network is directed path of length $n$ with ids $1$ through $n$, left to right
  • All capacities are $1$
  • $(\rho, \sigma) = (1, 0)$
    • Adversary injects 1 packet per round
  • $L(i)$ denotes the load of buffer $i$

Odd Even Downhill (OED)

Buffer $i$ forwards to $i+1$ if:

  1. $L(i) > L(i+1)$, or
  2. $L(i) = L(i+1)$ and $L(i)$ is odd

Proof of Theorem 1

  • Bound maximum number of packets in the network by $n$.
  • The height of a packet is one plus the number of packets beneath it in its buffer.
  • During the execution, consider plateaus of consecutive nodes with $L(i) \geq j$.

Lemma 1. Let $\ell$ be the total length of plateaus of minimum height $j$ with $j$ even. Then there are at most $\ell$ packets at height at least $j + 1$.

Lemma 1 Illustration

Lemma 1. Let $\ell$ be the total length of plateaus of minimum height $j$ with $j$ even. Then there are at most $\ell$ packets at height at least $j + 1$.

Lemma 1 Proof Ideas

Lemma 1. Let $\ell$ be the total length of plateaus of minimum height $j$ with $j$ even. Then there are at most $\ell$ packets at height at least $j + 1$.

Consider a single plateau $P$ of height $j$ with $j$ even, $L_P$ is number of packets above $P$:

  • $L_P$ can only increase because of injections
  • $P$ erodes from the right each round
  • Rightmost packet above $P$ moves right each round
  • $L_P$ cannot increase if rightmost packet above $P$ is at right boundary of $P$

Even Level Plateau Dynamics

Lemma 1 $\implies$ Theorem 1

Lemma 1. Let $\ell$ be the total length of plateaus of minimum height $j$ with $j$ even. Then there are at most $\ell$ packets at height at least $j + 1$.

Proof of Theorem 1. Exercise.

Lower Bounds

Theorem 2. Any local forwarding procedure has worst-case buffer loads of size $\Omega(\log n)$.

Proof idea. Define an injection pattern $P$ that inflicts $\Omega(\log n)$ loads against any local forwarding algorithm $A$.

  1. In first $n$ rounds, inject $n$ packets into buffer $1$.
  2. Simulate $A$ for $t = n/4$ steps with no injections.
  3. Take $I$ to be the half of the network with larger total load.
  4. In $t$ rounds, inject $t$ packets in middle node of $I$.
  5. Recurse on I, repeating 2–5.

Adversary Illustration (Greedy Forwarding)

Claim. In each iteration, the average load of $I$ increases by at least $1/4$.

  • In $n/4$ steps, at most $n/4$ packets leave the network, so simulated average load decreases by at most $1/4$.
  • By choice of $I$, simulated average load of $I$ is at least $\alpha - 1/4.$
  • Locality of $A \implies$ simulated and true behavior (with injections) are same on boundary of $I$.
  • $|I| / 2$ packets injected into $I$, so true average load is at least $\alpha - 1/4 + 1/2$.

Claim $\implies$ Lemma. After $\log n$ iterations, $I$ has length $1$ and load $\geq (1/4)\log n$.

Summary of Results

Space requirement of local forwarding on acyclic networks:

Topology/Locality greedy local global
SD Trees $\Theta(n)$ [1,2] $\Theta(\log n)$[3] $\Theta(1)$ [2]
General DAGs $\Theta(n)$ [1] $\Theta(n)$ $\Theta(n)$

[1] Adler & Rosén, 2002

[2] Miller & Patt-Shamir, 2016

[3] Dobrev et al., SPAA 2017 (Optimal Local Buffer Management... Talk today at 16:49!!)

Ongoing Work and Open Problems

  • "Nearly Local" forwarding (Patt-Shamir & R—, 2017+)
    • Locality $d$ only needs buffers of size $O\left(\sigma + \rho + \rho \frac{\log D}{d}\right)$?!
  • Empircal performance of OED (Patt-Shamir, Rechter, R—, 2017+)
    • How does "typical" performance of OED compare to simpler algorithms?
    • Generalizations of OED to more general topologies
  • OED with non-uniform timing?

Thank You!