# The Space Requirement of Local Forwarding on Acyclic Networks

## 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)
• efficiency is size of buffers required to deliver all packets without overflows

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

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

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

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

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