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...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-03-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/21/3/324 |
| _version_ | 1811306565636980736 |
|---|---|
| author | Giuseppe Vettigli Mingyue Ji Karthikeyan Shanmugam Jaime Llorca Antonia M. Tulino Giuseppe Caire |
| author_facet | Giuseppe Vettigli Mingyue Ji Karthikeyan Shanmugam Jaime Llorca Antonia M. Tulino Giuseppe Caire |
| author_sort | Giuseppe Vettigli |
| collection | DOAJ |
| 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 <i>local graph coloring</i>, 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. |
| first_indexed | 2024-04-13T08:47:41Z |
| format | Article |
| id | doaj.art-527c3c1055214149b8d3c5d6acb810e1 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-13T08:47:41Z |
| publishDate | 2019-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-527c3c1055214149b8d3c5d6acb810e12022-12-22T02:53:36ZengMDPI AGEntropy1099-43002019-03-0121332410.3390/e21030324e21030324Efficient Algorithms for Coded Multicasting in Heterogeneous Caching NetworksGiuseppe Vettigli0Mingyue Ji1Karthikeyan Shanmugam2Jaime Llorca3Antonia M. Tulino4Giuseppe Caire5Department of Electrical Engineering and Information Technology (DIETI), Universitá di Napoli Federico II, 80138 Napoli, ItalyDepartment of Electrical and Computer Engineering (ECE), University of Utah, Salt Lake City, UT 84112, USAIBM Research, New York, NY 10598, USADepartment of Math and Algorithms, Nokia Bell Labs, Murray Hill, NJ 07738, USADepartment of Electrical Engineering and Information Technology (DIETI), Universitá di Napoli Federico II, 80138 Napoli, ItalyFaculty of Electrical Engineering and Computer Science (EECS), Technical University of Berlin, 10587 Berlin, GermanyCoded 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 <i>local graph coloring</i>, 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.https://www.mdpi.com/1099-4300/21/3/324caching networksrandom fractional cachingcoded cachingcoded multicastingindex codingfinite-length analysisgraph coloringapproximation algorithms |
| spellingShingle | Giuseppe Vettigli Mingyue Ji Karthikeyan Shanmugam Jaime Llorca Antonia M. Tulino Giuseppe Caire Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks Entropy caching networks random fractional caching coded caching coded multicasting index coding finite-length analysis graph coloring approximation algorithms |
| 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 | caching networks random fractional caching coded caching coded multicasting index coding finite-length analysis graph coloring approximation algorithms |
| url | https://www.mdpi.com/1099-4300/21/3/324 |
| work_keys_str_mv | AT giuseppevettigli efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks AT mingyueji efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks AT karthikeyanshanmugam efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks AT jaimellorca efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks AT antoniamtulino efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks AT giuseppecaire efficientalgorithmsforcodedmulticastinginheterogeneouscachingnetworks |