RANDOMIZED SCHEDULING ALGORITHM FOR QUEUEING NETWORKS

Cited 28 time in webofscience Cited 0 time in scopus
  • Hit : 17
  • Download : 3
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.
Publisher
INST MATHEMATICAL STATISTICS
Issue Date
2012-02
Language
English
Article Type
Article
Citation

ANNALS OF APPLIED PROBABILITY, v.22, no.1, pp.128 - 171

ISSN
1050-5164
DOI
10.1214/11-AAP763
URI
http://hdl.handle.net/10203/255361
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
000301211200004.pdf(398.88 kB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 28 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0