With Great Speed Come Small Buffers

Avery Miller
University of Manitoba

Boaz Patt-Shamir
Tel Aviv University

Will Rosenbaum
Max Planck Institute for Informatics

I. Model and Problem

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

II. Previous Results

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

1. Is it possible to achieve $O(d + \sigma)$ buffer space with $d$ destinations for any $\rho \leq 1$?
2. What happens when $\rho \leq 1/2$? Can the $\Omega(\rho^2 n)$ lower bound be broken for non-greedy protocols?

III. Main Results

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

IV. $d$-Destination Algorithm

Warm-up: Single Destination

Peak-to-Sink (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 left-most 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 Peak-to-Sink (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$ pseudo-buffers according to packet destination
• activate pseudo-buffers according to PTS rule for each destination
• priority to right-most activated pseudo-buffer in $v$, even if right pseudo-buffer 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$ non-bad 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 round-robin 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 pseudo-buffers 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$$

VI. Open Questions

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!