On deciding stability of multiclass queueing networks under buffer priority scheduling policies
One of the basic properties of a queueing network is stability. Roughly speaking, it is the property that the total number of jobs in the network remains bounded as a function of time. One of the key questions related to the stability issue is how to determine the exact conditions under which a give...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Mathematical Statistics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/64941 https://orcid.org/0000-0001-8898-8778 |
| _version_ | 1826206331132968960 |
|---|---|
| author | Gamarnik, David Katz, Dmitriy |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Gamarnik, David Katz, Dmitriy |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | One of the basic properties of a queueing network is stability. Roughly speaking, it is the property that the total number of jobs in the network remains bounded as a function of time. One of the key questions related to the stability issue is how to determine the exact conditions under which a given queueing network operating under a given scheduling policy remains stable. While there was much initial progress in addressing this question, most of the results obtained were partial at best and so the complete characterization of stable queueing networks is still lacking.
In this paper, we resolve this open problem, albeit in a somewhat unexpected way. We show that characterizing stable queueing networks is an algorithmically undecidable problem for the case of nonpreemptive static buffer priority scheduling policies and deterministic interarrival and service times. Thus, no constructive characterization of stable queueing networks operating under this class of policies is possible. The result is established for queueing networks with finite and infinite buffer sizes and possibly zero service times, although we conjecture that it also holds in the case of models with only infinite buffers and nonzero service times. Our approach extends an earlier related work [Math. Oper. Res. 27 (2002) 272–293] and uses the so-called counter machine device as a reduction tool. |
| first_indexed | 2024-09-23T13:27:48Z |
| format | Article |
| id | mit-1721.1/64941 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:27:48Z |
| publishDate | 2011 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/649412022-09-28T14:24:45Z On deciding stability of multiclass queueing networks under buffer priority scheduling policies Gamarnik, David Katz, Dmitriy Sloan School of Management Gamarnik, David Gamarnik, David Katz, Dmitriy One of the basic properties of a queueing network is stability. Roughly speaking, it is the property that the total number of jobs in the network remains bounded as a function of time. One of the key questions related to the stability issue is how to determine the exact conditions under which a given queueing network operating under a given scheduling policy remains stable. While there was much initial progress in addressing this question, most of the results obtained were partial at best and so the complete characterization of stable queueing networks is still lacking. In this paper, we resolve this open problem, albeit in a somewhat unexpected way. We show that characterizing stable queueing networks is an algorithmically undecidable problem for the case of nonpreemptive static buffer priority scheduling policies and deterministic interarrival and service times. Thus, no constructive characterization of stable queueing networks operating under this class of policies is possible. The result is established for queueing networks with finite and infinite buffer sizes and possibly zero service times, although we conjecture that it also holds in the case of models with only infinite buffers and nonzero service times. Our approach extends an earlier related work [Math. Oper. Res. 27 (2002) 272–293] and uses the so-called counter machine device as a reduction tool. National Science Foundation (U.S.) (Grant CMMI-0726733) 2011-07-20T20:18:34Z 2011-07-20T20:18:34Z 2009-10 2009-01 Article http://purl.org/eprint/type/JournalArticle 1050-5164 http://hdl.handle.net/1721.1/64941 Gamarnik, David, and Dmitriy Katz. “On Deciding Stability of Multiclass Queueing Networks Under Buffer Priority Scheduling Policies.” The Annals of Applied Probability 19.5 (2009) : 2008-2037. 2009 © Institute of Mathematical Statistics. https://orcid.org/0000-0001-8898-8778 en_US http://dx.doi.org/10.1214/09-aap597 Annals of Applied Probability Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Mathematical Statistics Project Euclid |
| spellingShingle | Gamarnik, David Katz, Dmitriy On deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| title | On deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| title_full | On deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| title_fullStr | On deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| title_full_unstemmed | On deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| title_short | On deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| title_sort | on deciding stability of multiclass queueing networks under buffer priority scheduling policies |
| url | http://hdl.handle.net/1721.1/64941 https://orcid.org/0000-0001-8898-8778 |
| work_keys_str_mv | AT gamarnikdavid ondecidingstabilityofmulticlassqueueingnetworksunderbufferpriorityschedulingpolicies AT katzdmitriy ondecidingstabilityofmulticlassqueueingnetworksunderbufferpriorityschedulingpolicies |