Cargando…

Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks

Coded multicasting has been shown to be a promising approach to significantly improve the performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be pa...

Descripción completa

Detalles Bibliográficos
Autores principales: Vettigli, Giuseppe, Ji, Mingyue, Shanmugam, Karthikeyan, Llorca, Jaime, Tulino, Antonia M., Caire, Giuseppe
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2019
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7514808/
https://www.ncbi.nlm.nih.gov/pubmed/33267038
http://dx.doi.org/10.3390/e21030324
_version_ 1783586673844551680
author Vettigli, Giuseppe
Ji, Mingyue
Shanmugam, Karthikeyan
Llorca, Jaime
Tulino, Antonia M.
Caire, Giuseppe
author_facet Vettigli, Giuseppe
Ji, Mingyue
Shanmugam, Karthikeyan
Llorca, Jaime
Tulino, Antonia M.
Caire, Giuseppe
author_sort Vettigli, Giuseppe
collection PubMed
description Coded multicasting has been shown to be a promising approach to significantly improve the performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be partitioned into several packets that grows exponentially with the number of caches, leading to codes of exponential complexity that jeopardize their promising performance benefits. In this paper, we address this crucial performance-complexity tradeoff in a heterogeneous caching network setting, where edge caches with possibly different storage capacity collect multiple content requests that may follow distinct demand distributions. We extend the asymptotic (in the number of packets per file) analysis of shared link caching networks to heterogeneous network settings, and present novel coded multicast schemes, based on local graph coloring, that exhibit polynomial-time complexity in all the system parameters, while preserving the asymptotically proven multiplicative caching gain even for finite file packetization. We further demonstrate that the packetization order (the number of packets each file is split into) can be traded-off with the number of requests collected by each cache, while preserving the same multiplicative caching gain. Simulation results confirm the superiority of the proposed schemes and illustrate the interesting request aggregation vs. packetization order tradeoff within several practical settings. Our results provide a compelling step towards the practical achievability of the promising multiplicative caching gain in next generation access networks.
format Online
Article
Text
id pubmed-7514808
institution National Center for Biotechnology Information
language English
publishDate 2019
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-75148082020-11-09 Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks Vettigli, Giuseppe Ji, Mingyue Shanmugam, Karthikeyan Llorca, Jaime Tulino, Antonia M. Caire, Giuseppe Entropy (Basel) Article Coded multicasting has been shown to be a promising approach to significantly improve the performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal performance require content items to be partitioned into several packets that grows exponentially with the number of caches, leading to codes of exponential complexity that jeopardize their promising performance benefits. In this paper, we address this crucial performance-complexity tradeoff in a heterogeneous caching network setting, where edge caches with possibly different storage capacity collect multiple content requests that may follow distinct demand distributions. We extend the asymptotic (in the number of packets per file) analysis of shared link caching networks to heterogeneous network settings, and present novel coded multicast schemes, based on local graph coloring, that exhibit polynomial-time complexity in all the system parameters, while preserving the asymptotically proven multiplicative caching gain even for finite file packetization. We further demonstrate that the packetization order (the number of packets each file is split into) can be traded-off with the number of requests collected by each cache, while preserving the same multiplicative caching gain. Simulation results confirm the superiority of the proposed schemes and illustrate the interesting request aggregation vs. packetization order tradeoff within several practical settings. Our results provide a compelling step towards the practical achievability of the promising multiplicative caching gain in next generation access networks. MDPI 2019-03-25 /pmc/articles/PMC7514808/ /pubmed/33267038 http://dx.doi.org/10.3390/e21030324 Text en © 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Vettigli, Giuseppe
Ji, Mingyue
Shanmugam, Karthikeyan
Llorca, Jaime
Tulino, Antonia M.
Caire, Giuseppe
Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks
title Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks
title_full Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks
title_fullStr Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks
title_full_unstemmed Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks
title_short Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks
title_sort efficient algorithms for coded multicasting in heterogeneous caching networks
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7514808/
https://www.ncbi.nlm.nih.gov/pubmed/33267038
http://dx.doi.org/10.3390/e21030324
work_keys_str_mv AT vettigligiuseppe efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks
AT jimingyue efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks
AT shanmugamkarthikeyan efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks
AT llorcajaime efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks
AT tulinoantoniam efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks
AT cairegiuseppe efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks