Qualitative properties of α-weighted scheduling policies
We consider a switched network, a fairly general constrained queueing network model that has been used successfully to model the detailed packet-level dynamics in communication networks, such as input-queued switches and wireless networks. The main operational issue in this model is that of dec...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62864 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1811086814742577152 |
|---|---|
| author | Shah, Devavrat Zhong, Yuan Tsitsiklis, John N |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Zhong, Yuan Tsitsiklis, John N |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | We consider a switched network, a fairly general constrained
queueing network model that has been used successfully to
model the detailed packet-level dynamics in communication
networks, such as input-queued switches and wireless networks.
The main operational issue in this model is that
of deciding which queues to serve, subject to certain constraints.
In this paper, we study qualitative performance
properties of the well known α-weighted [alpha weighted] scheduling policies.
The stability, in the sense of positive recurrence, of these
policies has been well understood. We establish exponential
upper bounds on the tail of the steady-state distribution of
the backlog. Along the way, we prove finiteness of the expected
steady-state backlog when α < 1 [alpha < 1], a property that
was known only for α ≥ 1 [alpha ≥ 1]. Finally, we analyze the excursions
of the maximum backlog over a finite time horizon for
α ≥ 1 [alpha ≥ 1]. As a consequence, for α ≥ 1 [alpha ≥ 1], we establish the full
state space collapse property [17, 18]. |
| first_indexed | 2024-09-23T13:35:06Z |
| format | Article |
| id | mit-1721.1/62864 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:35:06Z |
| publishDate | 2011 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/628642023-03-01T02:14:40Z Qualitative properties of α-weighted scheduling policies Qualitative properties of α-weighted [alpha weighted] scheduling policies Shah, Devavrat Zhong, Yuan Tsitsiklis, John N Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Operations Research Center Tsitsiklis, John N. Shah, Devavrat Tsitsiklis, John N. Zhong, Yuan We consider a switched network, a fairly general constrained queueing network model that has been used successfully to model the detailed packet-level dynamics in communication networks, such as input-queued switches and wireless networks. The main operational issue in this model is that of deciding which queues to serve, subject to certain constraints. In this paper, we study qualitative performance properties of the well known α-weighted [alpha weighted] scheduling policies. The stability, in the sense of positive recurrence, of these policies has been well understood. We establish exponential upper bounds on the tail of the steady-state distribution of the backlog. Along the way, we prove finiteness of the expected steady-state backlog when α < 1 [alpha < 1], a property that was known only for α ≥ 1 [alpha ≥ 1]. Finally, we analyze the excursions of the maximum backlog over a finite time horizon for α ≥ 1 [alpha ≥ 1]. As a consequence, for α ≥ 1 [alpha ≥ 1], we establish the full state space collapse property [17, 18]. National Science Foundation (U.S.) (Project CCF 0728554) 2011-05-20T21:24:35Z 2011-05-20T21:24:35Z 2010-06 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/62864 Shah, Devavrat, John N. Tsitsiklis, and Yuan Zhong. “Qualitative properties of α-weighted scheduling policies.” ACM SIGMETRICS Performance Evaluation Review 38.1 (2010) : 239. Copyright 2010 ACM https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1145/1811039.1811067 International Conference on Measurement and Modeling of Computer Systems (2010). ACM SIGMETRICS Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Shah, Devavrat Zhong, Yuan Tsitsiklis, John N Qualitative properties of α-weighted scheduling policies |
| title | Qualitative properties of α-weighted scheduling policies |
| title_full | Qualitative properties of α-weighted scheduling policies |
| title_fullStr | Qualitative properties of α-weighted scheduling policies |
| title_full_unstemmed | Qualitative properties of α-weighted scheduling policies |
| title_short | Qualitative properties of α-weighted scheduling policies |
| title_sort | qualitative properties of α weighted scheduling policies |
| url | http://hdl.handle.net/1721.1/62864 https://orcid.org/0000-0003-0737-3259 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT shahdevavrat qualitativepropertiesofaweightedschedulingpolicies AT zhongyuan qualitativepropertiesofaweightedschedulingpolicies AT tsitsiklisjohnn qualitativepropertiesofaweightedschedulingpolicies AT shahdevavrat qualitativepropertiesofaweightedalphaweightedschedulingpolicies AT zhongyuan qualitativepropertiesofaweightedalphaweightedschedulingpolicies AT tsitsiklisjohnn qualitativepropertiesofaweightedalphaweightedschedulingpolicies |