Dynamic scheduling with reconfiguration delays
We consider scheduling in networks with interference constraints and reconfiguration delays, which may be incurred when one service schedule is dropped and a distinct service schedule is adopted. Reconfiguration delays occur in a variety of communication settings, such as satellite, optical, or dela...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103519 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826204395180654592 |
|---|---|
| author | Celik, G. Borst, S. C. Whiting, P. A. Modiano, Eytan H. |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Celik, G. Borst, S. C. Whiting, P. A. Modiano, Eytan H. |
| author_sort | Celik, G. |
| collection | MIT |
| description | We consider scheduling in networks with interference constraints and reconfiguration delays, which may be incurred when one service schedule is dropped and a distinct service schedule is adopted. Reconfiguration delays occur in a variety of communication settings, such as satellite, optical, or delay-tolerant networks. In the absence of reconfiguration delays it is well known that the celebrated Max-Weight scheduling algorithm guarantees throughput optimality without requiring any knowledge of arrival rates. As we will show, however, the Max-Weight algorithm may fail to achieve throughput optimality in case of nonzero reconfiguration delays. Motivated by the latter issue, we propose a class of adaptive scheduling algorithms which persist with the current schedule until a certain stopping criterion is reached, before switching to the next schedule. While earlier proposed Variable Frame-Based Max-Weight (VFMW) policies belong to this class, we also present Switching-Curve-Based (SCB) policies that are more adaptive to bursts in arrivals. We develop novel Lyapunov drift techniques to prove that this class of algorithms under certain conditions achieves throughput optimality by dynamically adapting the durations of the interswitching intervals. Numerical results demonstrate that these algorithms significantly outperform the ordinary Max-Weight algorithm, and that SCB policies yield a better delay performance than VFMW policies. |
| first_indexed | 2024-09-23T12:54:24Z |
| format | Article |
| id | mit-1721.1/103519 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:54:24Z |
| publishDate | 2016 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1035192022-09-28T10:49:15Z Dynamic scheduling with reconfiguration delays Celik, G. Borst, S. C. Whiting, P. A. Modiano, Eytan H. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Modiano, Eytan H. Celik, G. We consider scheduling in networks with interference constraints and reconfiguration delays, which may be incurred when one service schedule is dropped and a distinct service schedule is adopted. Reconfiguration delays occur in a variety of communication settings, such as satellite, optical, or delay-tolerant networks. In the absence of reconfiguration delays it is well known that the celebrated Max-Weight scheduling algorithm guarantees throughput optimality without requiring any knowledge of arrival rates. As we will show, however, the Max-Weight algorithm may fail to achieve throughput optimality in case of nonzero reconfiguration delays. Motivated by the latter issue, we propose a class of adaptive scheduling algorithms which persist with the current schedule until a certain stopping criterion is reached, before switching to the next schedule. While earlier proposed Variable Frame-Based Max-Weight (VFMW) policies belong to this class, we also present Switching-Curve-Based (SCB) policies that are more adaptive to bursts in arrivals. We develop novel Lyapunov drift techniques to prove that this class of algorithms under certain conditions achieves throughput optimality by dynamically adapting the durations of the interswitching intervals. Numerical results demonstrate that these algorithms significantly outperform the ordinary Max-Weight algorithm, and that SCB policies yield a better delay performance than VFMW policies. 2016-07-01T21:52:21Z 2017-03-01T16:14:48Z 2016-01 2014-11 2016-05-23T12:16:05Z Article http://purl.org/eprint/type/JournalArticle 0257-0130 1572-9443 http://hdl.handle.net/1721.1/103519 Celik, G., S. C. Borst, P. A. Whiting, and E. Modiano. “Dynamic Scheduling with Reconfiguration Delays.” Queueing Systems 83, no. 1–2 (January 23, 2016): 87–129. https://orcid.org/0000-0001-8238-8130 en http://dx.doi.org/10.1007/s11134-016-9471-4 Queueing Systems Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Science+Business Media New York application/pdf Springer US Springer US |
| spellingShingle | Celik, G. Borst, S. C. Whiting, P. A. Modiano, Eytan H. Dynamic scheduling with reconfiguration delays |
| title | Dynamic scheduling with reconfiguration delays |
| title_full | Dynamic scheduling with reconfiguration delays |
| title_fullStr | Dynamic scheduling with reconfiguration delays |
| title_full_unstemmed | Dynamic scheduling with reconfiguration delays |
| title_short | Dynamic scheduling with reconfiguration delays |
| title_sort | dynamic scheduling with reconfiguration delays |
| url | http://hdl.handle.net/1721.1/103519 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT celikg dynamicschedulingwithreconfigurationdelays AT borstsc dynamicschedulingwithreconfigurationdelays AT whitingpa dynamicschedulingwithreconfigurationdelays AT modianoeytanh dynamicschedulingwithreconfigurationdelays |