Instability of FIFO Queueing Networks with Quick Service Times

Abstract

A class of open first-in, first-out queueing networks is examined. Customers arrive according to a rate-1 Poisson process and wait at queues along their prescribed routes for exponential holding times, after which they exit from the system. Such a network can be chosen so that the sum of the mean service times at each queue is as small as desired. It is shown here that these networks are nevertheless unstable. Each such network will possess two customer types, which proceed along nearly parallel routes. Queues are visited sequentially, with each consisting of one relatively slow step and then several quick steps.