Boaz Patt-Shamir and **Will Rosenbaum**

Tel Aviv University

- Background
- Statement of Results
- A Few Details
- Upper Bounds
- Lower Bounds

**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

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

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

**Question** What is the best a *local* algorithm can do?

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

**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

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

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

- $L(i) > L(i+1)$, or
- $L(i) = L(i+1)$ and $L(i)$ is
*odd*

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

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$

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

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

- In first $n$ rounds, inject $n$ packets into buffer $1$.
- Simulate $A$ for $t = n/4$ steps with no injections.
- Take $I$ to be the half of the network with larger total load.
- In $t$ rounds, inject $t$ packets in middle node of $I$.
- 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$.

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!!)

- "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?