Latency minimization through optimal data placement in fog networks

Nowadays, fog networks (FNs) distribute services to fog servers so that they are spatially closer to end-users and thus provide high availability and low data access delay, i.e. better usage experience. Given the different data demands of users and limited storage capacity of fog servers in FNs, it is nontrivial to optimally store data. Specifically, in this chapter, we discuss multiple data placement with budget problem (MDBP), whose objective is to minimize the overall data access latency for all data requests within a given total budget. We start with a case in which data replication is not considered. In this case, we propose a min-cost flow transformation for the MDBP to calculate the optimal data placement strategy. We further propose an efficient local information collection scheme to reduce the time complexity in the tree topology. In a general case with data replication, we prove that the MDBP is nondeterministic polynomial-time (NP)-complete. In the line topology, we can use dynamic programming to solve the single data request scenario. We also apply a novel rounding algorithm that incurs an approximation ratio of 10 in terms of the overall latency in the general case. We validate the proposed algorithms by using the PlanetLab trace, proving that they significantly improve the performance.