Resource Allocation Strategies in Highly Distributed and Heterogeneous Computing Systems

The spread of IoT devices has led to the design of new extensions of cloud computing, such as fog computing, providing IoT applications with reduced latency, location-awareness and mobility support. The term cloud-to-things continuum in this context refers to the fact that the computation is no longer confined to a few data centers but workloads can be displaced from the central cloud to the edge of network involving multiple infrastructure owners and several devices with different computational characteristics. This heterogeneity impacts the capability of the infrastructure owner of satisfying the QoS requirements of clients. Consequently, solving the placement and orchestration problems among the cloud-to-things continuum becomes key to ensure the profitability for the involved stakeholders. This thesis focuses on the algorithmic solutions for the problem of placement and the orchestration of microservice-based applications in such a distributed and heterogeneous context. On one hand, the placement problem involves the design of efficient solutions for the deployment of applications on a fog infrastructure, a type of problem which typically is NP-hard, even assuming a complete knowledge of applications' requirements and resource availability. In this thesis, the focus is on the design of approximated solutions for the NP-hard problems behind such resource allocation tasks. The orchestration of fog applications, on the other hand, deals with the maintenance of applications' QoS requirements under partial information about applications requests arrivals. For each applications' module, orchestration algorithms involve the decision of deployment either in fog or in cloud as the applications requests vary over time. In order to deal with this problem, we developed solutions based on stochastic optimisation techniques. The proposed methods outperform standard cloud-native solutions and suggest new approaches for inter-operability between different fog regions. Additionally, numerical results confirm the scalability properties of all the proposed solutions and their efficiency in terms of infrastructure owner's costs, for the placement side, and in terms applications' QoS, for the orchestration part.