With Great Speed Come Small Buffers

Space-Bandwidth Tradeoffs for Routing

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

Optimal Buffer Size vs Rate Tradeoff

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 Illustration

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!

Thank You!