Space-Optimal Packet Routing on Trees*

Boaz Patt-Shamir
Tel Aviv University

Will Rosenbaum
Max Planck Institute for Informatics

* - For this talk, trees = paths!


  1. Model and Problem Definition
  2. Previous Approaches and Results
  3. New Results
  4. Future Work

1. Model and Problem Definition

Simplest Routing Problem Imaginable

  • Network is a path* of buffers
  • All packets have same destination (right endpoint)
  • System is synchronous
  • Each round, each buffer can forward up to $c\, (= 1)$ packets

* - more generally, a tree

Adversarial Packet Injections

  • Each round, packets arrive in the network
  • In any $t$ consective rounds, at most $\rho \cdot t + \sigma$ packets arrive
    • $\rho \leq c$ is the asymptotic rate
    • $\sigma \geq 0$ is the burstiness
  • Such an injection pattern is $(\rho, \sigma)$-bounded

Note: $(1,0)$-bounded $\implies$ at most one packet injected per round

Main Question

What is the minimum buffer space required per node in order to deliver all packets for any $(\rho, \sigma)$-bounded injection pattern?

2. Previous Approaches and Results

Greedy Forwarding

Every nonempty buffer forwards a packet to the right.

Worst case buffer size is \(\Theta(n)\).

Centralized Forwarding

Injection at $i$, all nonempty buffers $j \geq i$ forward

Worst case buffer size is $O(1)$. (Miller & Patt-Shamir, 2016)

Odd Even Downhill (OED)

$i$ forwards if $L(i) > L(i+1)$, or $L(i) = L(i+1)$ and $L(i)$ is odd

Worst case buffer size is $O(\log n)$. (PR & DLNO, 2017)

Lower Bounds

Theorem [PR, DLNO 2017]. Any protocol where the action of each node $v$ depends only on the current state of nodes up to distance $d$ from $v$ requires buffers of size $$ \Omega\left(\frac{\log n}{d}\right) $$ in the worst case.

Question. Is this this this lower bound optimal?

3. New Results

Main Result

The lower bound of the previous theorem is tight!

Theorem. For every $d \in O(\log n)$ there exists a $d$-local protocol $A$ that for any $(\rho, \sigma)$-bounded injection pattern, $A$ delivers all packets and requires buffers of size $$ O\left(\frac{\log n}{d} + \sigma \right). $$

  • A protocol is $d$-local if the actions of each node $v$ depend only on the current state of nodes up to distance $d$ from $v$.
  • Taking $d = \log n$, this algorithm matches the performance of the best centralized algorithm.

Algorithm Overview

  1. Partition network into clusters of size $O(d)$
  2. Define virtual load of a cluster to be number of packets "owned" by the cluster
    • initial ownership assigned at time of injection
  3. Perform virtual forwarding according to OED rule
    • virtual forwarding only changes ownership of packets
  4. Physically forward packets
    • only packets owned by next cluster are forwarded to next cluster
    • balance loads within clusters

Algorithm in Pictures

Dashed line threshold $\sim (\log n) / d$

Analysis Idea

  • Define a load threshold $$ \theta \sim \frac{\log n}{d} $$
  • Call a packet bad if its position in a buffer is $\geq \theta$
  • Algorithm prioritizes forwarding bad packets to "good" positions
  • After forwarding $\leq \sigma$ bad packets in network
  • So: max load is $\leq \theta + \sigma$

4. Future Work

Simplifying the Algorithm

Currently: too much bookkeeping!

  • Can a simpler algorithm work?
  • Can the algorithm be stateless?
    • no virtual loads
    • no packet ownership

Generalizing the Algorithm

Can algorithm be generalized to broader family of topologies?

Impediment: worst-case lower bounds!

The following topologies have $\Omega(n)$ worst-case loads for all protocols:

  • path with arbitrary source/destination
  • single source, single destination DAGs
  • $2 \times n$ grid with single destination

Generalizing the Algorithm

Non-greedy protocols may give good performance in practice even on more general topologies

Preliminary empirical results for "diamond" topology

Thank You!