The Space Requirement of Local Forwarding on Acyclic Networks
Boaz Patt-Shamir, Will Rosenbaum · 2017
We consider packet forwarding in acyclic networks with bounded adversarial packet injections. We focus on the model of adversarial queuing theory, where each packet is injected into the network with a prescribed path to its destination, and both the long-range average rate and the short-range burst size are bounded. Each edge has an associated buffer that stores packets while they wait to cross the edge. Our goal is to minimize the buffer space required to avoid overflows.