Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse
We consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a fam...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Mathematical Statistics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73473 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811082440077213696 |
|---|---|
| author | Shah, Devavrat Wischik, Damon |
| 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 Wischik, Damon |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | We consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a family of scheduling policies, related to the maximum-weight policy of Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936–1948], for single-hop and multihop networks. We specify a fluid model and show that fluid-scaled performance processes can be approximated by fluid model solutions. We study the behavior of fluid model solutions under critical load, and characterize invariant states as those states which solve a certain network-wide optimization problem. We use fluid model results to prove multiplicative state space collapse. A notable feature of our results is that they do not assume complete resource pooling. |
| first_indexed | 2024-09-23T12:03:27Z |
| format | Article |
| id | mit-1721.1/73473 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:03:27Z |
| publishDate | 2012 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/734732022-10-01T07:51:28Z Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse Shah, Devavrat Wischik, Damon Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat We consider a queueing network in which there are constraints on which queues may be served simultaneously; such networks may be used to model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time. We consider a family of scheduling policies, related to the maximum-weight policy of Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936–1948], for single-hop and multihop networks. We specify a fluid model and show that fluid-scaled performance processes can be approximated by fluid model solutions. We study the behavior of fluid model solutions under critical load, and characterize invariant states as those states which solve a certain network-wide optimization problem. We use fluid model results to prove multiplicative state space collapse. A notable feature of our results is that they do not assume complete resource pooling. National Science Foundation (U.S.) (CAREER CNS-0546590) 2012-09-28T15:23:22Z 2012-09-28T15:23:22Z 2012 2011-01 Article http://purl.org/eprint/type/JournalArticle 1050-5164 http://hdl.handle.net/1721.1/73473 Shah, Devavrat, and Damon Wischik. “Switched Networks with Maximum Weight Policies: Fluid Approximation and Multiplicative State Space Collapse.” The Annals of Applied Probability 22.1 (2012): 70–127. 2012 © Institute of Mathematical Statistics https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1214/11-aap759 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 Institute of Mathematical Statistics |
| spellingShingle | Shah, Devavrat Wischik, Damon Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse |
| title | Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse |
| title_full | Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse |
| title_fullStr | Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse |
| title_full_unstemmed | Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse |
| title_short | Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse |
| title_sort | switched networks with maximum weight policies fluid approximation and multiplicative state space collapse |
| url | http://hdl.handle.net/1721.1/73473 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT shahdevavrat switchednetworkswithmaximumweightpoliciesfluidapproximationandmultiplicativestatespacecollapse AT wischikdamon switchednetworkswithmaximumweightpoliciesfluidapproximationandmultiplicativestatespacecollapse |