With Great Speed Come Small Buffers
SpaceBandwidth Tradeoffs for Routing
Avery Miller
University of Manitoba
Boaz PattShamir
Tel Aviv University
Will Rosenbaum
Max Planck Institute for Informatics
Model
 $G = (V, E)$ a network (directed graph)
 packets arrive in network with prescribed route from source to destination
 each (out) edge represents a buffer
 packets arrive in discrete rounds
 each edge can forward one packet per round
Goal. Forward packets using minimum buffer size.
We Consider
 $G$ is a directed path with $n$ nodes

packet injections $(\rho, \sigma)$bounded:
 in any $T$ consecutive rounds, at most $\rho \cdot T + \sigma$ packets injected needing to cross any one edge
 e.g., $(\rho, \sigma) = (1, 0) \implies$ all packets injected in a round have edge disjoint routes
 may have a designated set of $d$ allowed destinations
Previous Results
Multiple Destinations:
 $O(n + \sigma)$ buffer space for DAGs [Adler & Rosén, 2002]
 $\Omega(d)$ buffer space necessary for $\rho > 1/2$ with $d$ destinations (path) [PS & R, 2017]
 $\Omega(\rho^2 n)$ buffer space for greedy protocols [Rosén & Scalosub 2011]
Single Destination Trees:
 $\Theta(\rho + \sigma)$ buffer space, centralized [M & PS, 2016]
 $\Theta(\log n + \sigma)$ buffer space, local [Dobrev et al., PS & R, 2017]
 $\Theta\left(\frac 1 D \log n + \sigma\right)$ buffer space, $D$local [PS & R 2019]
Questions
 Is it possible to achieve $O(d + \sigma)$ buffer space with $d$ destinations for any $\rho \leq 1$?
 What happens when $\rho \leq 1/2$? Can the $\Omega(\rho^2 n)$ lower bound be broken for nongreedy protocols?
Main Results
Theorem 1. Buffer space $d + \sigma + 1$ is sufficient for all $(\rho, \sigma)$ injection patterns ($\rho \leq 1$) with $d$ destinations.
Theorem 2. If $\rho \leq 1/k$ ($k$ positive integer), then $k \cdot n^{1/k} + \sigma + 1$ buffer space is sufficeint for any number of destinations.
Theorem 3. If $\rho > 1 / (k+1)$, then $\Omega\left(\frac 1 k n^{1/k}\right)$ buffer space is necessary.
 lower bound holds even for offline algorithms
Optimal Buffer Size vs Rate Tradeoff
IV. $d$Destination Algorithm
Warmup: Single Destination
PeaktoSink (PTS) Forwarding:
 call a buffer bad if it contains at least $2$ packets
 a packet is bad if it is stored in position $\geq 2$
 $v$ is leftmost bad buffer
 activate $v$ and all $u$ to the right of $v$
 all active (nonempty) buffers forward a packet
Analysis of PTS Forwarding
Observation. A forwarding step of PTS strictly reduces the number of bad packets needing to cross each active buffer.
 adversary can inject at most $1$ packet each round without expending "burst budget"
 define excess $\xi^t(v)$ to be amount of burst budget used up to round $t$
 observation $\implies$ the number of bad packets behind $v$ is at most $\xi^t(v)$ after forwarding
 $\xi^t(v) \leq \sigma \implies$ every buffer has load at most $2 + \sigma$
Parallel PeaktoSink (PPTS)
Idea. For $d$ destinations, treat each destination as a separate instance of PTS.
 $w_1, w_2, \ldots, w_d$ are destinations from left to right
 partition each buffer into $d$ pseudobuffers according to packet destination
 activate pseudobuffers according to PTS rule for each destination
 priority to rightmost activated pseudobuffer in $v$, even if right pseudobuffer is empty
PPTS Analysis
Analysis of PPTS is similar to PTS:
 in a forwarding step, for each $v$, the number of bad packets needing to cross $v$ strictly decreases
 therefore, the number of bad packets needing to cross any $v$ is at most the excess, $\xi^t(v) \leq \sigma$
 each buffer can have at most $d$ nonbad packets
 total number of packets in any buffer is at most $d + \sigma + 1$
V. Hierarchical Algorithm
Hierarchical Network Partition
For fixed positive integer $k$:
 form $k$ levels
 $j$th level consists of $n^{(k  j) / k}$ disjoint intervals of length $n^{j/k}$
 each interval in level $j \geq 1$ has $n^{1/k}$ intermediate destinations leading to lower levels
Routing on Hierarchical Network
Each packet $p$ is stored in highest level with an intermediate destination before $p$'s destination
Forwarding on Hierarchical Network
Idea. For each level $\ell$, simulate PPTS on all level $\ell$ intervals in parallel.
 each level $\ell$ interal has $d = n^{1/k}$ intermediate destinations
 perform PPTS step on each level in decreasing roundrobin manner
 on average $\rho \cdot k \leq 1$ packets arrive every $k$ rounds
$\implies$ injection rate into a level is $\leq 1$ per $k$round phase
Forwarding on Hierarchical Network
Complication. Pushing packets to lower levels may introduce new bad packets.
 algorithm preempts such packet deliveries
 activate pseudobuffers at lower levels, if available bandwidth
 each phase the number of bad packets needing to cross each edge decreases
Analysis of Hierarchical Algorithm
 in a phase, number of new injections needing $v$ is at most $1 + $ change in excess
 because $k \cdot \rho \leq 1$
 each phase ($k$ rounds), number of bad packets needing to cross each edge decreases
 number of bad packets is at most excess after forwarding
 total number of bad packets needing to cross any edge is at most
$$
k \cdot n^{1/k} + \sigma + 1
$$
Open Questions
Question 1. Can our algorithms be made local?
 for single destination, $O(\log n)$ buffer space suffices
 open even for $2$ destinations!
Question 2. Can our algorithms be generalized to more network topologies?
 $d$ destination algorithm generalizes to directed trees
 hierarchical algorithm unknown even for directed trees!