Abstract
The tradeoff between the user's memory size and the worst-case download time in the (H, r, M, N) combination network is studied, where a central server communicates with K users through H immediate relays, and each user has local cache of size M files and is connected to a different subset of r relays. The main contribution of this paper is the design of a coded caching scheme with asymmetric coded placement by leveraging coordination among the relays, which was not exploited in past work. Mathematical analysis and numerical results show that the proposed schemes outperform existing schemes.
Introduction
In modern content delivery networks, caching is a critical strategy for mitigating peak-hour traffic congestion. By pre-storing popular content in local user caches during off-peak periods (the placement phase), the server can significantly reduce the delivery load when requests are made (the delivery phase). This paper investigates a specific architecture known as the combination network, where a central server reaches users through a layer of intermediate relays.
Network Model and Problem Formulation
The system considers a central server containing $N$ files, each of size $B$ bits. There are $H$ intermediate relays and $K$ users. Each user is equipped with a local cache of size $M$ files and is connected to a unique subset of $r$ relays. This topology is illustrated in Figure 1.
The primary challenge in such networks is maximizing "multicasting opportunities"—the ability of a single transmission to satisfy multiple users simultaneously. Traditional symmetric caching schemes often fail to exploit the specific connectivity between users and relays, leading to sub-optimal delivery rates.
Proposed Methodology: Asymmetric Coded Placement
The authors propose a novel two-phase scheme that moves away from traditional symmetric data placement:
- Asymmetric Coded Placement: Instead of uniform file splitting, the scheme utilizes Maximum Distance Separable (MDS) codes to pre-code files. Crucially, the placement is asymmetric: subfiles are stored in user caches only if those users share a common relay connection. This ensures that the cached content is structurally aligned with the network's physical topology.
- Coordinated Delivery: During the delivery phase, the server transmits coded messages to the relays. Because the placement phase was topology-aware, relays can coordinate their transmissions. Each relay sends linear combinations of subfiles that are useful to multiple connected users, thereby maximizing the coded caching gain ($g$).
The mathematical framework employs the inclusion-exclusion principle to precisely determine the number of deliverable subfiles based on the network parameters $H$ and $r$.
Performance Evaluation
The proposed scheme (Theorem 1) was evaluated against existing state-of-the-art methods, including schemes by Maddah-Ali & Niesen [2] and Zewail & Yener [8, 9].
As shown in Figure 2, the proposed scheme (blue circles) consistently outperforms the benchmark [8] for small to medium cache sizes ($M$), where the ratio $R[Th. 1]/R([8])$ is less than 1. For very large cache sizes, a previously developed scheme [9] (red stars) remains superior. Notably, for certain high-memory regimes, the proposed scheme approaches the information-theoretic outer bound, indicating near-optimal performance.
Conclusion
This work demonstrates that "topology matters" in structured relay networks. By implementing asymmetric coded placement, the proposed scheme effectively exploits relay coordination to reduce the maximum link load. Future work aims to develop a unified hybrid scheme that combines the strengths of this approach with existing methods for large-memory regimes to provide a universal solution for combination networks.
Summary updated