Boaz Patt-Shamir and Will Rosenbaum
Tel Aviv University
General Question: How do we efficiently move stuff from one place to another?
Goal: Minimize the maximum load of any buffer in the network.
That is, we consider space complexity.
Every nonempty buffer forwards a packet to the right.
Worst case buffer size is \(\Omega(n)\).
Buffer $i$ forwards to $i+1$ if $ L(i) > L(i+1)$
Worst case buffer size is $\Omega(n)$.
Injection at $i$, all nonempty buffers $j \geq i$ forward
Worst case buffer size is $O(1)$. (Miller & Patt-Shamir, 2016)
Question: What is the best performance we can achieve if forwarding is local?
Previously: All local algorithms we found had worst case loads of size $\Omega(n)$.
Buffer $i$ forwards to $i+1$ if:
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)$.
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. 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$.
Let $m$ be the maximal load. For $j \leq m$, $I_j$ is maximal interval with $L(i) \geq j$. Observe:
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)$.
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$.
Claim. In each iteration, the average load of $I$ increases by at least $1/4$.
Claim $\implies$ Lemma. After $\log n$ iterations, $I$ has length $1$ and load $\geq (1/4)\log n$.
Theorem 3. Even if we assume:
then there exists an adversary $P$ that inflicts loads of size \[ \Omega\left(\frac{\log n}{\log \log n}\right)\,. \]
Adversarial Queuing Theory (BKRS 96)
Note. The adversary from first half of talk was $(1,0)$-bounded.
Suppose $v \in V$ has children $u_1, \ldots, u_k$
Each round, do the following:
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)
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:
No matter how packets are forwarded, some buffer has load $\Omega(n)$.
Similar idea works for 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!
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