Dynamic scheduling with reconfiguration delays

G. Celik (), S. C. Borst (), P. A. Whiting () and E. Modiano ()
Additional contact information
G. Celik: MIT
S. C. Borst: Bell Labs
P. A. Whiting: Macquarie University
E. Modiano: MIT

Queueing Systems: Theory and Applications, 2016, vol. 83, issue 1, No 5, 87-129

Abstract: Abstract 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.

Keywords: Max-Weight algorithm; Scheduling; Reconfiguration; Switching delay; Stability; Throughput optimality; Primary: 68M20 (Performance evaluation; queueing; scheduling), Secondary: 60K25 (Queueing theory), 90B18 (Communication networks), 90B22 (Queues and service) (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-016-9471-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:83:y:2016:i:1:d:10.1007_s11134-016-9471-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-016-9471-4

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().