Application Component Placement in NFV-based Hybrid Cloud/Fog Systems with Mobile Fog Nodes

Fog computing reduces the latency induced by distant clouds by enabling the deployment of some application components at the edge of the network, on fog nodes, while keeping others in the cloud. Application components can be implemented as Virtual Network Functions (VNFs) and their execution sequences can be modeled by a combination of sub-structures like sequence, parallel, selection, and loops. Efficient placement algorithms are required to map the application components onto the infrastructure nodes. Current solutions do not consider the mobility of fog nodes, a phenomenon which may happen in real systems. In this paper, we use the random waypoint mobility model for fog nodes to calculate the expected makespan and application execution cost. We then model the problem as an Integer Linear Programming (ILP) formulation which minimizes an aggregated weighted function of the makespan and cost. We propose a Tabu Search-based Component Placement (TSCP) algorithm to find sub-optimal placements. The results show that the proposed algorithm improves the makespan and the application execution cost.