Caching and Coded Multicasting: Multiple Groupcast Index Coding

Abstract

The capacity of caching networks has received considerable attention in the past few years. A particularly studied setting is the case of a single server (e.g., a base station) and multiple users, each of which caches segments of files in a finite library. Each user requests one (whole) file in the library and the server sends a common coded multicast message to satisfy all users at once. The problem consists of finding the smallest possible codeword length to satisfy such requests. In this paper we consider the generalization to the case where each user places $L\ge 1$ requests. The obvious naive scheme consists of applying $L$ times the order-optimal scheme for a single request, obtaining a linear in $L$ scaling of the multicast codeword length. We propose a new achievable scheme based on multiple groupcast index coding that achieves a significant gain over the naive scheme. Furthermore, through an information theoretic converse we find that the proposed scheme is approximately optimal within a constant factor of (at most) $18$.

5 pages, 1 figure, to appear in GlobalSIP14, Dec. 2014

References in corpus (3)

• Fundamental Limits of Distributed Caching in D2D Wireless Networks
• The Throughput-Outage Tradeoff of Wireless One-Hop Caching Networks
• Local Graph Coloring and Index Coding

Cited by in corpus (10)

• Order-Optimal Rate of Caching and Coded Multicasting with Random Demands
• Wireless Multihop Device-to-Device Caching Networks
• Information Theoretic Caching: The Multi-User Case
• Coded Caching with Distributed Storage
• On the Optimality of Uncoded Cache Placement
• Joint Fronthaul Multicast and Cooperative Beamforming for Cache-Enabled Cloud-Based Small Cell Networks: An MDS Codes-Aided Approach
• Efficient File Delivery for Coded Prefetching in Shared Cache Networks with Multiple Requests Per User
• An Efficient Multiple-Groupcast Coded Multicasting Scheme for Finite Fractional Caching
• Decentralized Caching Schemes and Performance Limits in Two-layer Networks
• Efficient Scheduling and Power Allocation for D2D-assisted Wireless Caching Networks