Basic Limits on Protocol Information in Slotted Communication Networks

The authors investigate the amount of protocol information required for a communication network to meet an average delay constraint for the delivery of messages that arrive according to a Bernoulli random process. They obtain a lower bound on this overhead as a function of the arrival rate and average delay. Their model is a discrete-time analog of the Poisson arrival process considered by Gallager, and they show that in the limit as slot duration goes to zero, Gallager's bound is recovered.