Virtual Functions Placement with Time Constraints in Fog Computing: a Matching Theory Perspective

This paper proposes two virtual function (VFs) placement approaches in a Fog domain. The considered solutions formulate a matching game with externalities, aiming at minimizing both the worst application completion time and the number of applications in outage, i.e., the number of applications with an overall completion time greater than a given deadline. The first proposed matching game is established between the VFs set and the Fog Nodes (FNs) set by taking into account the ordered sequence of services (i.e., chain) requested by each application. Conversely, the second proposed method overlooks the applications service chain structure in formulating the VF placement problem, with the aim at lowering the computation complexity without loosing the performance. Furthermore, in order to complete our analysis, the stability of the reached matchings has been theoretically proved for both the proposed solutions. Finally, performance comparisons of the proposed MT approaches with different alternatives are provided to highlight the superior performance of the proposed methods.