How do we efficiently move stuff from one place to another in a network?
modelled by Adversarial Queueing Theory (AQT)
introduced by Borodin et al. JACM, 2001
efficiency (primarily) measured by buffer space usage
The Network
A graph $G = (V, E)$
Packets
A path in $G$ from source to destination
Execution in Synchronous Rounds
Each round consists of:
injection step: packets are injected into the network
forwarding step: each buffer forwards a packet (or not)
Congestion
Parameterization
Injection patterns parameterized by (average) edge utilization
number of packets needing to cross each edge $e$ over any time interval can only exceed the edge’s capacity by a fixed amount
AQT Injection pattern is arbitrary (adversarial), up to satisfying edge capacity constraints
Questions.
For a given forwarding protocol, how much buffer space is required per edge to store packets en route to their destinations?
What protocol achieves optimal buffer space usage?
The Single-Destination Path
A humble network topology
For now:
all packets share a common destination (right endpoint)
exactly one packet per round is injected
only uncertainty is where the packet is injected
Question. What is a natural protocol for this scenario?
Greedy Forwarding
Protocol: If a buffer stores a packet, it forwards a packet
Worst-case buffer space usage is $\Theta(n)$ ($n$ = network length).
Downhill Forwarding
Protocol: Buffer $i$ forwards to $i+1$ if $L(i) > L(i+1)$
Worst case buffer size is $\Omega(n)$.
Centralized Forwarding
Protocol: If a packet is injected into buffer $i$, all buffers $j \geq i$ forward
Worst case buffer size is $2$.
Local Protocols
Problem. Centralized forwarding requires instantaneous coordination across the entire network!
What can we say about protocols based on their locality?
Greedy is $0$-local (buffer space $\Theta(n)$)
Downhill is $1$-local
buffer $i$’s actions depend only on the state of $i$ and $i+1$
Centralized is $n$-local (buffer space $\Theta(1)$)
Question. Can any $O(1)$-local protocol achieve worst-case buffer space $o(n)$?
A Local Protocol
Odd-even Downhill (OED): buffer $i$ forwards iff:
$L(i) > L(i+1)$, or
$L(i) = L(i+1)$ and $L(i)$ is odd
Main Results, OED
Theorem 1. The worst case buffer space usage of OED is $O(\log n)$.
Theorem 2. Any $O(1)$-local protocol has worst case buffer space usage $\Omega(\log n)$
$\Omega((\log n) / \log \log n)$ holds even if edges have infinite capacity and adversary injects only a single packet each round
Upper Bound Idea
Invariant. For any plateau of even height, the number of packets above the plateau is at most the width of the plateau.
Local Lower Bounds
Idea.
Consider injecting packets in the center of an interval of length $\ell$
For a $1$-local protocol, $\ell/2$ rounds must pass before interval endpoints can respond to injections
In $\ell/2$ rounds, the average load in some sub-interval can be increased by $1/4$
Recurse $\Theta(\log n)$ times on sub-intervals
Space-Locality Tradeoffs
Question. What can be said about $d$-local protocols
A more careful analysis of the lower bound construction gives:
Theorem 2’. Any $d$-local protocol has worst case buffer space usage $\Omega(1 + \frac{1}{d}(\log n))$
Question. Is space $O(1 + \frac{1}{d}(\log n))$ achievable by a $d$-local protocol?
Theorem 3. Yes!
A Semi-Local Algorithm
High level idea
Partition network into $n/d$ intervals
Treat each interval as a single “meta” node
load of meta node $\approx$ sum of buffer loads
Simulate OED between meta nodes
Perform centralized load-balancing within each meta-node
Result, Restated
Theorem 3’. There is a $d$-local protocol for the single destination path that achieves worst-case buffer space usage of $O(1 + \frac 1 d \log n)$
Consequence. Taking $d = \log n$, the buffer space usage is $O(1)$.
$\implies (\log n)$-locality is sufficient to achieve the best possible (asymptotic) buffer space usage of any centralized protocol.
Fewer Restrictions?
Admittedly, the single destination path is a very restricted (if fundamental) scenario. What can be said about more general topologies?
Modest Generalization. All results listed so far can be extended to single destination trees.
Theorem 4 (letdown). Any (centralized, offline) protocol for the path with arbitrary destinations requires $\Omega(n)$ buffer space.
path with $k$ destinations requires buffer space $\Omega(k)$
$\Omega(n)$ bound for DAGs with a single source/destination
greedy forward with longest-in-system priority give $O(n)$ buffer space (Adler and Rosén, 2001)
Lower Bound for Paths
$\ldots$
Observation
The $\Omega(n)$ lower bound fails if either:
the algorithm can forward 2 packets per round, or
the adversary only injects one packet every second round
Question. What is the best achievable space complexity when the edge capacity significantly exceeds the injection rate?
Prelude: Path with $k$ Destinations
Lemma. There is a (centralized) protocol that achieves buffer space usage $O(k)$ for the path with $k$ destinations.
Protocol Idea.
partition packets by destination
apply centralized $O(1)$ space protocol for each packet class
under forwarding contention, packets with right-most destination have priority
Bandwidth Doubling
Suppose:
2 packets can be forwarded each round, or
packets injected only every second round
Question. Can we achieve $o(n)$ space complexity on the path with arbitrary destinations?
Theorem 5. Yes!
Hierarchical Decomposition
Idea. Let $k = \sqrt{n}$, and decompose the network into $k + 1$ paths, each with $k$ destinations
top path has length $n$, $k$ destinations
bottom (disjoint) paths have length $k$
Decomposed Routes
Algorithm
apply $k$ destination algorithm (using $O(k)$ space) to each part of the decomposed network in parallel
only contention is between top path and bottom paths
$\implies$ each buffer only needs to forward two packets each round
Conclusion. If capacity is 2 or injection rate is $\leq 1/2$, $O(\sqrt{n})$ buffer space is sufficient!
Space-Bandwidth Tradeoffs
The construction from before generalizes!
Theorem 5’. For the path with arbitrary destinations, if the adversary injects packets at a rate $\rho$ satisfying $\frac{1}{k+1} < \rho \leq \frac 1 k$ then buffer space $O(k n^{1/k})$ is sufficient.
Theorem 6. Under the hypotheses of Theorem 5’, $\Omega(\frac 1 k n^{1/k})$ space is necessary for any (centralized, offline) protocol.
Buffer Space vs Injection Rate
Open Questions
Local protocols for the path with $k$ destinations
embarrassingly open: $k = 2$
Space-bandwidth trade-offs for trees
Tight bounds for graphs with cycles
What can we say about space complexity for general graphs?
