2014/12/31 by Mostafa Dehghan, Anand Seetharam, Dehghan, Mostafa +13
Computer Science · #Caching and Content Delivery #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.1501.00216
openalex publication_date 2014/12/31 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We investigate the problem of optimal request routing and content caching in\na heterogeneous network supporting in-network content caching with the goal of\nminimizing average content access delay. Here, content can either be accessed\ndirectly from a back-end server (where content resides permanently) or be\nobtained from one of multiple in-network caches. To access a piece of content,\na user must decide whether to route its request to a cache or to the back-end\nserver. Additionally, caches must decide which content to cache. We investigate\nthe problem complexity of two problem formulations, where the direct path to\nthe back-end server is modeled as i) a congestion-sensitive or ii) a\ncongestion-insensitive path, reflecting whether or not the delay of the\nuncached path to the back-end server depends on the user request load,\nrespectively. We show that the problem is NP-complete in both cases. We prove\nthat under the congestion-insensitive model the problem can be solved optimally\nin polynomial time if each piece of content is requested by only one user, or\nwhen there are at most two caches in the network. We also identify a structural\nproperty of the user-cache graph that potentially makes the problem\nNP-complete. For the congestion-sensitive model, we prove that the problem\nremains NP-complete even if there is only one cache in the network and each\ncontent is requested by only one user. We show that approximate solutions can\nbe found for both models within a (1-1/e) factor of the optimal solution, and\ndemonstrate a greedy algorithm that is found to be within 1% of optimal for\nsmall problem sizes. Through trace-driven simulations we evaluate the\nperformance of our greedy algorithms, which show up to a 50% reduction in\naverage delay over solutions based on LRU content caching.\n