# The Space Requirement of Local Forwarding on Acyclic Networks

## Overview

1. Packet Forwarding on a Path
2. Odd-Even Downhill (OED) Forwarding
3. Generalizations:
• 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.

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

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)\,.$

## Computational Model

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

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