Latency minimization through optimal data placement in fog networks

Ning Wang, Jie Wu

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationFog Computing
Subtitle of host publicationTheory and Practice
Number of pages23
ISBN (Electronic)9781119551713
ISBN (Print)9781119551690
StatePublished - Apr 25 2020

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'Latency minimization through optimal data placement in fog networks'. Together they form a unique fingerprint.

Cite this