Variable frame based Max-Weight algorithms for networks with switchover delay
This paper considers the scheduling problem for networks with interference constraints and switchover delays, where it takes a nonzero time to reconfigure each service schedule. Switchover delay occurs in many telecommunication applications such as satellite, optical or delay tolerant networks (DTNs...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81421 https://orcid.org/0000-0001-8238-8130 |
| _version_ | 1826214075355365376 |
|---|---|
| author | Celik, Guner Dincer Borst, S. Whiting, P. 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, Guner Dincer Borst, S. Whiting, P. Modiano, Eytan H. |
| author_sort | Celik, Guner Dincer |
| collection | MIT |
| description | This paper considers the scheduling problem for networks with interference constraints and switchover delays, where it takes a nonzero time to reconfigure each service schedule. Switchover delay occurs in many telecommunication applications such as satellite, optical or delay tolerant networks (DTNs). Under zero switchover delay it is well known that the Max-Weight algorithm is throughput-optimal without requiring knowledge of the arrival rates. However, we show that this property of Max-Weight no longer holds when there is a nonzero switchover delay. We propose a class of variable frame based Max-Weight (VFMW) algorithms which employ the Max-Weight schedule corresponding to the beginning of the frame during an interval of duration dependent on the queue sizes. The VFMW algorithms dynamically adapt the frame sizes to the stochastic arrivals and provide throughput-optimality without requiring knowledge of the arrival rates. Numerical results regarding the application of the VFMW algorithms to DTN and optical networks demonstrate a good delay performance. |
| first_indexed | 2024-09-23T15:59:24Z |
| format | Article |
| id | mit-1721.1/81421 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:59:24Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/814212022-10-02T05:34:25Z Variable frame based Max-Weight algorithms for networks with switchover delay Celik, Guner Dincer Borst, S. Whiting, P. Modiano, Eytan H. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Celik, Guner Dincer Modiano, Eytan H. This paper considers the scheduling problem for networks with interference constraints and switchover delays, where it takes a nonzero time to reconfigure each service schedule. Switchover delay occurs in many telecommunication applications such as satellite, optical or delay tolerant networks (DTNs). Under zero switchover delay it is well known that the Max-Weight algorithm is throughput-optimal without requiring knowledge of the arrival rates. However, we show that this property of Max-Weight no longer holds when there is a nonzero switchover delay. We propose a class of variable frame based Max-Weight (VFMW) algorithms which employ the Max-Weight schedule corresponding to the beginning of the frame during an interval of duration dependent on the queue sizes. The VFMW algorithms dynamically adapt the frame sizes to the stochastic arrivals and provide throughput-optimality without requiring knowledge of the arrival rates. Numerical results regarding the application of the VFMW algorithms to DTN and optical networks demonstrate a good delay performance. National Science Foundation (U.S.) (NSF grant CNS-0626781) National Science Foundation (U.S.) (NSF grant CNS-0915988) United States. Army Research Office (ARO Muri grant number W911NF-08-1-0238) 2013-10-17T20:31:28Z 2013-10-17T20:31:28Z 2011-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-4577-0596-0 978-1-4577-0594-6 2157-8095 http://hdl.handle.net/1721.1/81421 Celik, G., S. Borst, P. Whiting, and E. Modiano. “Variable frame based Max-Weight algorithms for networks with switchover delay.” In 2011 IEEE International Symposium on Information Theory Proceedings, July 31 2011-Aug. 5 2011, St. Petersburg, pp. 2537-2541. Institute of Electrical and Electronics Engineers, 2011. https://orcid.org/0000-0001-8238-8130 en_US http://dx.doi.org/10.1109/ISIT.2011.6034025 2011 IEEE International Symposium on Information Theory Proceedings Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers MIT web domain |
| spellingShingle | Celik, Guner Dincer Borst, S. Whiting, P. Modiano, Eytan H. Variable frame based Max-Weight algorithms for networks with switchover delay |
| title | Variable frame based Max-Weight algorithms for networks with switchover delay |
| title_full | Variable frame based Max-Weight algorithms for networks with switchover delay |
| title_fullStr | Variable frame based Max-Weight algorithms for networks with switchover delay |
| title_full_unstemmed | Variable frame based Max-Weight algorithms for networks with switchover delay |
| title_short | Variable frame based Max-Weight algorithms for networks with switchover delay |
| title_sort | variable frame based max weight algorithms for networks with switchover delay |
| url | http://hdl.handle.net/1721.1/81421 https://orcid.org/0000-0001-8238-8130 |
| work_keys_str_mv | AT celikgunerdincer variableframebasedmaxweightalgorithmsfornetworkswithswitchoverdelay AT borsts variableframebasedmaxweightalgorithmsfornetworkswithswitchoverdelay AT whitingp variableframebasedmaxweightalgorithmsfornetworkswithswitchoverdelay AT modianoeytanh variableframebasedmaxweightalgorithmsfornetworkswithswitchoverdelay |