The Space Requirement of Local Forwarding on Acyclic Networks

Boaz Patt-Shamir and Will Rosenbaum

Tel Aviv University

Overview

  1. Packet Forwarding on a Path
  2. Odd-Even Downhill (OED) Forwarding
  3. Generalizations:
    • Adversarial Queuing Thoery
    • OED on Trees
    • Lower Bounds

Introduction

General Question: How do we efficiently move stuff from one place to another?

  • Network is a path of $n$ vertices
  • Motion in synchronous rounds:
    1. adversary injects a single packet
    2. each node may forward a single packet
  • Packet is delivered when it is forwarded by right-most node

Goal: Minimize the maximum load of any buffer in the network.

That is, we consider space complexity.

Greedy Forwarding

Every nonempty buffer forwards a packet to the right.

Worst case buffer size is \(\Omega(n)\).

Downhill/Slide Forwarding

Buffer $i$ forwards to $i+1$ if $ L(i) > L(i+1)$

Worst case buffer size is $\Omega(n)$.

Global Forwarding

Injection at $i$, all nonempty buffers $j \geq i$ forward

Worst case buffer size is $O(1)$. (Miller & Patt-Shamir, 2016)

Local Forwarding

  • Global forwarding can have great performance...
  • ...but it requires instantaneous coordination!

Question: What is the best performance we can achieve if forwarding is local?

  • Forwarding rule for \(i\) depends only on loads of \(i\) and \(i\)s neighbors.

Previously: All local algorithms we found had worst case loads of size $\Omega(n)$.

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

Main Results for OED

Theorem 1. The worst case buffer load for OED forwarding is $\Theta(\log n)$.

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

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 $\implies$ Theorem 1

Let $m$ be the maximal load. For $j \leq m$, $I_j$ is maximal interval with $L(i) \geq j$. Observe:

  • $I_m \subseteq I_{m-1} \subseteq \cdots \subseteq I_1$

  • Lemma implies \[ 2 |I_{m}| \leq |I_{m-1}| + |I_{m}| \leq |I_{m - 2}| \]

    \[ \begin{align*} &\vdots\\ 2 |I_2| + 2 |I_4| + \cdots + &2 |I_{m-2}| + 2 |I_m| \leq |I_{0}| = n \end{align*} \]

By induction $2 \cdot 3^{m/2} |I_m| \leq n$

Since $|I_m| \geq 1$, we get $m = O(\log n)$.

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$.

More General Lower Bounds

Theorem 3. Even if we assume:

  • packets can be sent right or left,
  • each edge can forward arbitrarily many packets (still only 1 injection per round),
  • each packet can be delivered to either the right or left end of the network,
  • each node sees the state of nodes up to distance $d$ for any fixed constant $d$,

then there exists an adversary $P$ that inflicts loads of size \[ \Omega\left(\frac{\log n}{\log \log n}\right)\,. \]

Can OED be generalized to a broader class of networks?

Computational Model

Adversarial Queuing Theory (BKRS 96)

  1. Network is a directed graph $G = (V, E)$.
  2. Each edge $e \in E$ has a capacity $C(e)$
  3. Each packet $p$ is injected with a specified path from source to destination
  4. Adversary is $(\rho, \sigma)$-bounded if for all $r < s \in \mathbf{N}$ and $e \in E$, the number of packets injected at times $t = r, \ldots, s-1$ whose path contains $e$ is at most \[ \rho (s - r) + \sigma \]

Note. The adversary from first half of talk was $(1,0)$-bounded.

Single Destination Trees

  1. $G = (V, E)$ is a rooted tree
  2. All packets have root as destination
  3. WLOG tree has single edge to root
  4. Total number of packets injected into network satisfy $(\rho, \sigma)$ bound
  5. Assume every edge has capacity $C(e) = 1$ and rate $\rho \leq 1$.

OED on Single Destination Trees

Suppose $v \in V$ has children $u_1, \ldots, u_k$

Each round, do the following:

  1. $u = \mathrm{argmax} \{L(u_1), L(u_2), \ldots, L(u_k)\}$
  2. Apply odd-even rule to edge $(u, v)$:
    • $u$ forwards to $v \iff$ $L(u) > L(v)$ or $L(u) = L(v)$ and $L(u)$ is odd

Tree OED Demo

Tree OED Performance

Theorem 4. Let $G = (V, E)$ be a single destination tree of depth $D$ with unit capacity edges. Then for any $(\rho, \sigma)$-bounded advsary $P$ with $\rho \leq 1$, OED forwarding achieves maximum loads of size $O(\sigma + \log D)$

Proof idea. Plateau of height $j$ is a maximal connected component of edges $(u, v)$ with $L(u) \geq j$.

Lemma 4. Let $F$ be the forest of plateaus of height $j$ for $j$ even, and $D$ the depth of $F$. Then there are at most $D + \sigma$ packets at height $\geq j + 1$.

Lemma 4 $\implies$ Theorem 4 (c.f. proof of Theorem 1)

Further Generalization?

Question. Can some variant of OED forwarding acheive similar performance in more general networks? Multiple destinations? DAGs?

Theorem 5. No. Let $\mathcal{F}$ be the family of multiple destination paths or single source, single destination DAGs. Then for every $\rho > 1/2$, $\sigma \geq 1$, and every forwarding algorithm $A$ (possibly offline or global), there exists a $(\rho, \sigma)$-bounded injection pattern $P$ which inflicts loads of size $\Omega(n)$.

General Path Adversary

$G = $ path of length $n$, vertices labeled $1, \ldots, n$ left to right

For $i = 1, 2, \ldots, n/2$ do:

  • in $n - i$ rounds, inject
    1. $\rho(n - i)$ packets at $1$ with destination $n - i$
    2. $\rho(n - i)$ packets at $n - i$ with destination $n$

No matter how packets are forwarded, some buffer has load $\Omega(n)$.

Similar idea works for DAGs

Optimal Forwarding on DAGS

Theorem 6 (Adler & Rosén, 2002). On DAGs greedy routing with "longest in system" scheduling achieves maximum buffer loads (and latency) $O(n)$.

Theorem 5 + Theorem 6 show greedy is optimal even for offline global forwarding!

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)$ $\Theta(1)$ [2]
General DAGs $\Theta(n)$ [1] $\Theta(n)$ $\Theta(n)$

[1] Adler & Rosén, 2002

[2] Miller & Patt-Shamir, 2016

Ongoing Work and Open Problems

  • General uniform capacities on SD Trees (PODC 2017+)
  • ``Nearly Local'' forwarding (Patt-Shamir & R—, 2017+)
  • Non-uniform capacities (open)
  • Are these schemes practical? (open)

Thank You!