Space-Optimal Packet Routing on Trees
Boaz Patt-Shamir, Will Rosenbaum · 2019
We consider packet forwarding on a tree with all packets destined for the root, assuming each link may forward at most c ≥ 1 packets each time step. We use the Adversarial Queuing Theory injection model, where a (ρ, σ)-adversary may inject at most σ + ρ · t packets into the network at arbitrary locations during any time interval of length t. The goal is to find a forwarding protocol that minimizes the maximal buffer space required to avoid overflows against a (ρ, σ)-adversary with ρ ≤ c. We consider protocols from the locality viewpoint. A protocol is called d-local if the actions of a node depend only on the current state of nodes at distance at most d. A D-local protocol, where D is the network diameter, is called centralized. It is known that buffers of size Θ(σ + ρ) are necessary and sufficient for centralized protocols. The buffer requirement of O(1)-local protocols was recently proved to be Θ(ρ log D+σ). In this paper, for any d ≥ 2, we describe a d-local algorithm whose buffer space requirement is O (⌈log D/d⌉ ρ + σ). This result is tight, up d to constant factors. In particular, it implies that O(log D) locality is sufficient to achieve the best worst-case performance possible even for centralized algorithms. We also give evidence suggesting that the buffer requirement of a local algorithm designed for trees is good also when the routes do not constitute a single-destination tree.