Large number of queues in tandem: scaling properties under back-pressure algorithm (Q632216)

Stability of a tandem network with \(N\) queues and with Poisson input with rate \(\lambda\) at queue 1 is considered under a back-pressure (BP) algorithm: the queue \(n\) is blocked unless the queue \(n+1\) is smaller. It is known that this policy ensures maximum possible network throughput. It is shown that, as \(N\to \infty\), the queues remain (stochastically) bounded provided \(\lambda<1/4\), while they grow to infinity, otherwise. The problem is reduced to studying an infinite tandem network. A technique from interacting particle systems and a connection with a totally asymmetric simple excursion process (TASEP) are used.