Scheduling Algorithms for Wireless Networks and Cloud Computing Platforms

Abstract

This thesis focuses on designing scheduling algorithms for wireless communication networks, FMCW radar networks, and cloud computing platforms. In each case, the algorithms aim at efficient utilization of resources, e.g., frequency, power, storage etc. In the first work, we propose a class of binary queue length information based max-weight scheduling algorithms for wireless networks. In these algorithms, the scheduler, in addition to channel states, only needs to know when a link’s queue length crosses a prescribed threshold. We show that these algorithms are throughput optimal. Further, we incorporate time-since-last service (TSLS) information to improve delay and service regularity of the scheduling algorithms while ensuring throughput optimality. Finally, we suggest amendments to the proposed algorithms to facilitate distributed, CSMA-like, implementation in a restricted class of wireless networks. In the second work, we consider a cellular downlink in which the base stations (BSs) can be switched on and off dynamically. We also consider two costs (i) BS running cost (ii) BS switching (ON to OFF or OFF to ON) cost and propose cost-optimal BS switching and rate allocation policies that are also throughput optimal. The proposed policies use the drift-plus-penalty framework. In these, the scheduler first takes BS switching decision based on channel state statistics and queue-lengths and then selects a rate vector depending on channel realization of the BSs that are ON. We subsequently combine these policies with an algorithm that learns the channel statistics using explore-exploit technique. In the third work, we study medium access in FMCW radar networks. In particular, we propose and analyze slotted ALOHA and CSMA protocols to mitigate narrowband interference. We define a notion of throughput to quantify the performance of the proposed protocols. In the case of ALOHA, we analyse interference probability and throughput as functions of the system parameters. We define a medium sensing procedure, referred to as clear channel assessment (CCA), as a part of the proposed CSMA, and also define CCA success and failure events. We study, CCA success probability, interference probability, and throughput as functions of the system parameters. Finally, we propose job scheduling algorithms to minimize job migration and server running costs in cloud computing platforms offering Infrastructure as a Service. We first consider algorithms that assume knowledge of job-size on arrival of jobs. We characterize the optimal cost subject to system stability. We develop a drift-plus-penalty framework based algorithm that can achieve optimal cost arbitrarily closely. We then relax the job-size knowledge assumption and give an algorithm that only uses readily offered service to the jobs and still gives order-wise identical cost as the job size based algorithm.