Randomized Scheduling Algorithm for Queueing Networks
There has recently been considerable interest in design of low-complexity, myopic, distributed and stable scheduling algorithms for constrained queueing network models that arise in the context of emerging communication networks. Here we consider two representative models. One, a queueing network mo...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Mathematical Statistics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72602 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1811091345360551936 |
|---|---|
| author | Shah, Devavrat Shin, Jinwoo |
| 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 Shin, Jinwoo |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | There has recently been considerable interest in design of low-complexity, myopic, distributed and stable scheduling algorithms for constrained queueing network models that arise in the context of emerging communication networks. Here we consider two representative models. One, a queueing network model that captures randomly varying number of packets in the queues present at a collection of wireless nodes communicating through a shared medium. Two, a buffered circuit switched network model for an optical core of future internet to capture the randomness in calls or flows present in the network. The maximum weight scheduling algorithm proposed by Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936–1948], leads to a myopic and stable algorithm for the packet-level wireless network model. But computationally it is expensive (NP-hard) and centralized. It is not applicable to the buffered circuit switched network due to the requirement of nonpreemption of the calls in the service. As the main contribution of this paper, we present a stable scheduling algorithm for both of these models. The algorithm is myopic, distributed and performs few logical operations at each node per unit time. |
| first_indexed | 2024-09-23T15:01:01Z |
| format | Article |
| id | mit-1721.1/72602 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:01:01Z |
| publishDate | 2012 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/726022022-09-29T12:04:49Z Randomized Scheduling Algorithm for Queueing Networks Shah, Devavrat Shin, Jinwoo Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat Shah, Devavrat Shin, Jinwoo There has recently been considerable interest in design of low-complexity, myopic, distributed and stable scheduling algorithms for constrained queueing network models that arise in the context of emerging communication networks. Here we consider two representative models. One, a queueing network model that captures randomly varying number of packets in the queues present at a collection of wireless nodes communicating through a shared medium. Two, a buffered circuit switched network model for an optical core of future internet to capture the randomness in calls or flows present in the network. The maximum weight scheduling algorithm proposed by Tassiulas and Ephremides [IEEE Trans. Automat. Control 37 (1992) 1936–1948], leads to a myopic and stable algorithm for the packet-level wireless network model. But computationally it is expensive (NP-hard) and centralized. It is not applicable to the buffered circuit switched network due to the requirement of nonpreemption of the calls in the service. As the main contribution of this paper, we present a stable scheduling algorithm for both of these models. The algorithm is myopic, distributed and performs few logical operations at each node per unit time. National Science Foundation (U.S.). Project (CNS 0546590) National Science Foundation (U.S.). Project (TF 0728554) United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program United States. Air Force Office of Scientific Research (Complex networks project) 2012-09-10T19:09:26Z 2012-09-10T19:09:26Z 2012 2011-01 Article http://purl.org/eprint/type/JournalArticle 1050-5164 http://hdl.handle.net/1721.1/72602 Shah, Devavrat, and Jinwoo Shin. “Randomized Scheduling Algorithm for Queueing Networks.” The Annals of Applied Probability 22.1 (2012): 128–171. https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1214/11-aap763 Annals of Applied Probability Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Mathematical Statistics arXiv |
| spellingShingle | Shah, Devavrat Shin, Jinwoo Randomized Scheduling Algorithm for Queueing Networks |
| title | Randomized Scheduling Algorithm for Queueing Networks |
| title_full | Randomized Scheduling Algorithm for Queueing Networks |
| title_fullStr | Randomized Scheduling Algorithm for Queueing Networks |
| title_full_unstemmed | Randomized Scheduling Algorithm for Queueing Networks |
| title_short | Randomized Scheduling Algorithm for Queueing Networks |
| title_sort | randomized scheduling algorithm for queueing networks |
| url | http://hdl.handle.net/1721.1/72602 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT shahdevavrat randomizedschedulingalgorithmforqueueingnetworks AT shinjinwoo randomizedschedulingalgorithmforqueueingnetworks |