Tight bounds for the performance of Longest In System on DAGs

We show that the protocol Longest In System, when applied to directed acyclic graphs, uses buffers of only linear size (in the length of the longest path in the network). Furthermore, we show that any packet incurs only linear delay as well. These are, to the best of our knowledge, the first deterministic polynomial bounds on queue sizes and packet delays in the framework of adversarial queuing theory (other than on trees and the cycle). Furthermore these results separate Longest In System from other common universally stable protocols for which there exist exponential lower bounds that are obtained on DAGs. Our upper bounds are complemented by matching linear lower bounds on buffer sizes and packet delays.