First-fit allocation of queues: Tight probabilistic bounds on wasted space (Q756295)

Consider an M/M/1-queueing system with either first-in-first-out (FIFO) or processor sharing (PC) service discipline. Assume the waiting room is arranged as a linear array of cells such that each customer can occupy one cell. Upon arrival a customer is placed into the first empty cell. He leaves it as soon as his service is completed. The ``wasted space'' is defined to be the number of empty cells in the set of cells until the occupied one with the highest number. Consider the steady state in heavy traffic (traffic intensity \(=\) 1-1/n, \(n\in N\) large). The authors show that the expected wasted space is O(\(\sqrt{n})\) in the FIFO-case and O(\(\sqrt{n \log n})\) in the PC-case. They furthermore derive results on the tails of the distribution of wasted space.