Scheduling Problems in Next Generation Computing Networks

Abstract

With the development of the novel Internet of Things (IoT) ecosystem, the digital support required by emerging applications is a highly growing area of concern. The current network paradigm, cloud computing, is proving unable to adequately support the ever increasing computational and storage needs of the billions of edge devices in use. In recent years, several solutions have been put forward including two complementary computing paradigms: Multi-access Edge Computing (MEC) and fog computing. MEC and fog computing are both considered augments to cloud computing since they both conceptualize supplementary server layers to existing networks.

This thesis addresses the emerging challenge of efficient task scheduling in both MEC and fog computing. Since traditional mathematical programming models are proven to be very difficult to solve optimally at large dimensions, another approach is needed to satisfy the time-sensitive needs of the dynamic environments of both MEC and fog computing. In this thesis, we propose several heuristics that are designed to provide good solutions while maintaining low complexity guarantees.

The first problem examined in this thesis is how to fully utilize parked vehicles (PVs) as computational resources in vehicular networks under the MEC framework. We formulate a multi-objective task offloading problem that minimizes both task delay and wireless channel load. Then, a stable matching based heuristic is proposed and evaluated at various configurations of the vehicular environment.

The second problem that we examine in thesis is how to fairly allocate resources in fog computing. Fairness in resource allocation is a highly desired quality because it not only increases the quality of service (QoS) for users but also maximizes the resource utilization in the system. This thesis adopts the Dominant Resource Fairness (DRF) scheme and applies it to a multi-resource, multi-server, and heterogeneous task environment. Furthermore, four different types of tasks are considered: ordered/unordered, splittable/unsplittable. Finally, three different low complexity heuristics are proposed to maximize fairness between users under the DRF scheme.