A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> 3) FOG/EDGE COMPUTING <s> We consider a content delivery architecture based on geographically dispersed groups of "last-mile" CDN servers, e.g., set-top boxes located within users' homes. These servers may belong to administratively separate domains, such as multiple ISPs. We propose a set of scalable, adaptive mechanisms to jointly manage content replication and request routing within this architecture. Relying on primal-dual methods and fluid-limit techniques, we formally prove the optimality of our design. We further evaluate its performance on both synthetic and trace-driven simulations, based on real BitTorrent traces, and observe a reduction of network costs by more than 50% over traditional mechanisms such as LRU/LFU with closest request routing. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> 3) FOG/EDGE COMPUTING <s> The tremendous growth in the use of the World Wide Web and the expansion of Video On Demand and IPTV services increase the bandwidth demands, enforcing the creation of congestion in Internet's links and the experience of big delays to the users. Replicating content at caches which are close to the users can improve the access time for them and reduce the network bandwidth usage as well. In this work, we focus on hierarchical cache topologies, as IPTV networks tend to have a mostly hierarchical tree structure, making the content placement problem in them a topic of major importance. The problem is NP-Complete in it's general form. In this paper, we make the simplifying assumption that the size of each object is equal to one. Under that assumption we show that certain instances of the content placement problem are of polynomial complexity, while we provide an algorithm for their solution. Besides, we extend the proposed algorithm to handle the general case of arbitrary object sizes. Simulation experiments for typical popularity distributions depict the performance distance between the optimal solution and some low complexity heuristic algorithms that are commonly applied nowadays. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> 3) FOG/EDGE COMPUTING <s> We investigate the problem of optimal request routing and content caching in a heterogeneous network supporting in-network content caching with the goal of minimizing average content access delay. Here, content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access a piece of content, a user must decide whether to route its request to a cache or to the back-end server. Additionally, caches must decide which content to cache. We investigate the problem complexity of two problem formulations, where the direct path to the back-end server is modeled as i) a congestion-sensitive or ii) a congestion-insensitive path, reflecting whether or not the delay of the uncached path to the back-end server depends on the user request load, respectively. We show that the problem is NP-complete in both cases. We prove that under the congestion-insensitive model the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify a structural property of the user-cache graph that potentially makes the problem NP-complete. For the congestion-sensitive model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both models within a (1 − 1/e) factor of the optimal solution, and demonstrate a greedy algorithm that is found to be within 1% of optimal for small problem sizes. Through trace-driven simulations we evaluate the performance of our greedy algorithms, which show up to a 50% reduction in average delay over solutions based on LRU content caching. <s> BIB003
There is a growing interest in scrutinizing content placement by using smaller, non-traditional surrogate servers, such as cellular-base stations and set-top-boxes ( BIB001 , BIB002 ). This area of fog/edge computing in CDN requires research in content delivery techniques across heterogeneous networks, such as cellular/CDN, cloud/cellular edge, etc. BIB003 .