Feedback Increases the Capacity of Queues

In their 'Bits Through Queues' paper, Anantharam and Verdu showed that, under FIFO service policy, feedback does not increase the capacity of a queue when the service time is exponentially distributed. Whether this negative and surprising result-since the channel has memory-holds for other combinations of service policies and service times ever since has remained an open question. This paper first provides a sufficient condition on the service time distribution for feedback to increase capacity under First-In-First-Out service policy. Underlying this condition is a notion of weak feedback wherein instead of the queue departure times the transmitter is informed about the instants when packets start to be served. Service times that satisfy this condition include a uniformly distributed service time for the continuous-time model and a binary service time for the discrete-time model. Second, a sufficient condition is given under which feedback does not increase capacity. This condition is satisfied, for instance, by queues with Last-Come- First-Served service policies and bounded service times.