TY - JOUR
T1 - Delay-Optimal Scheduling for Two-Hop Relay Networks with Randomly Varying Connectivity
T2 - Join the Shortest Queue-Longest Connected Queue Policy
AU - Baek, Seung Jun
AU - Park, Joon Sang
N1 - Funding Information:
This work is supported in part by National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (NRF-2016R1A2B1014934) and by Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (no. B0126-17-1046) and in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2016R1D1A1B03930393).
Funding Information:
Thisworkissupported in partby National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (NRF-2016R1A2B1014934) and by Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (no. B0126-17-1046) and in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2016R1D1A1B03930393).
Publisher Copyright:
© 2017 Seung Jun Baek and Joon-Sang Park.
PY - 2017
Y1 - 2017
N2 - We consider a scheduling problem for a two-hop queueing network where the queues have randomly varying connectivity. Customers arrive at the source queue and are later routed to multiple relay queues. A relay queue can be served only if it is in connected state, and the state changes randomly over time. The source queue and relay queues are served in a time-sharing manner; that is, only one customer can be served at any instant. We propose Join the Shortest Queue-Longest Connected Queue (JSQ-LCQ) policy as follows: (1) if there exist nonempty relay queues in connected state, serve the longest queue among them; (2) if there are no relay queues to serve, route a customer from the source queue to the shortest relay queue. For symmetric systems in which the connectivity has symmetric statistics across the relay queues, we show that JSQ-LCQ is strongly optimal, that is, minimizes the delay in the stochastic ordering sense. We use stochastic coupling and show that the systems under coupling exist in two distinct phases, due to dynamic interactions among source and relay queues. By careful construction of coupling in both phases, we establish the stochastic dominance in delay between JSQ-LCQ and any arbitrary policy.
AB - We consider a scheduling problem for a two-hop queueing network where the queues have randomly varying connectivity. Customers arrive at the source queue and are later routed to multiple relay queues. A relay queue can be served only if it is in connected state, and the state changes randomly over time. The source queue and relay queues are served in a time-sharing manner; that is, only one customer can be served at any instant. We propose Join the Shortest Queue-Longest Connected Queue (JSQ-LCQ) policy as follows: (1) if there exist nonempty relay queues in connected state, serve the longest queue among them; (2) if there are no relay queues to serve, route a customer from the source queue to the shortest relay queue. For symmetric systems in which the connectivity has symmetric statistics across the relay queues, we show that JSQ-LCQ is strongly optimal, that is, minimizes the delay in the stochastic ordering sense. We use stochastic coupling and show that the systems under coupling exist in two distinct phases, due to dynamic interactions among source and relay queues. By careful construction of coupling in both phases, we establish the stochastic dominance in delay between JSQ-LCQ and any arbitrary policy.
UR - http://www.scopus.com/inward/record.url?scp=85038972024&partnerID=8YFLogxK
U2 - 10.1155/2017/4362652
DO - 10.1155/2017/4362652
M3 - Article
AN - SCOPUS:85038972024
SN - 1024-123X
VL - 2017
JO - Mathematical Problems in Engineering
JF - Mathematical Problems in Engineering
M1 - 4362652
ER -