Maury Bramson - Instability of LIFO Queueing Networks and “Classical Queueing Networks"
|Starts:||15:00 11 May 2022|
|Ends:||16:00 11 May 2022|
|What is it:||Seminar|
|Organiser:||Department of Mathematics|
Maury Bramson (University of Minnesota) will speak in the Probability seminar.
Under the last-in, first-out (LIFO) discipline, jobs arriving later at a class always receive priority of service over earlier arrivals at any class belonging to the same station. The LIFO discipline is one of the four classical disciplines, the others being first-in, first-out (FIFO), processor sharing (PS), and infinite server (IS). When customers arriving from outside the network do so according to independent Poisson streams and appropriate conditions are placed on the service distributions of customers, well-known theory states that such subcritical queueing networks are stable (positive recurrent), with equilibria that can be explicitly written in a simple explicit form.
These results strongly influenced the development of queueing theory, and it was assumed nice stability behavior would continue to hold if Poisson input were generalized to renewal input and service distributions were generalized. It was with considerable surprise that counterexamples were found for subcritical FIFO queueing networks. However, stability is easy to show for IS queueing networks and almost complete results are known for PS queueing networks. Moreover, when the mean service times of FIFO queueing networks are all the same, subcritical FIFO queueing networks are also stable.
Since the FIFO discipline is homogeneous, but not symmetric, whereas IS, PS, and LIFO are all both, it seemed natural that subcritical LIFO queueing networks would also always be stable. Here, we present a family of unstable subcritical LIFO queueing networks. By modifying this family, one also obtains unstable subcritical LIFO queueing networks whose mean service times are all the same. These examples therefore cast doubt on the existence of a general theory for the stability of either symmetric or homogeneous queueing networks.
Travel and Contact Information