Scheduling Using Interactive Optimization Oracles for Constrained Queueing Networks

Tonghoon Suk () and Jinwoo Shin ()
Additional contact information
Tonghoon Suk: IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
Jinwoo Shin: School of Electrical Engineering, Korea Advanced Institute of Science and Technology, Seoul, Republic of Korea

Mathematics of Operations Research, 2017, vol. 42, issue 3, 723-744

Abstract: Ever since Tassiulas and Ephremides in 1992 proposed the maximum weight scheduling algorithm of throughput optimality for constrained queueing networks that arise in the context of communication networks, extensive efforts have been devoted to resolving its most important drawback: high complexity. This paper proposes a generic framework for designing throughput-optimal and low-complexity scheduling algorithms for constrained queueing networks. Under our framework, a scheduling algorithm updates current schedules by interacting with a given oracle system that generates an approximate solution to a related optimization task. One can use our framework to design a variety of scheduling algorithms by choosing an oracle system such as random 7524 Markov chain, belief propagation, and primal-dual methods. The complexity of the resulting scheduling algorithm is determined by the number of operations required for an oracle to process a single query, which is typically small. We provide sufficient conditions for throughput optimality of the scheduling algorithm, in general, constrained queueing network models. The linear time algorithm of Tassiulas in 1998 and the random access algorithm of Shah and Shin in 2012 correspond to special cases of our framework using random search and Markov chain oracles, respectively. Our generic framework, however, provides a unified proof with milder assumptions.

Keywords: network control algorithms; network stability (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0824 (application/pdf)

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:inm:ormoor:v:42:y:2017:i:3:p:723-744

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().