On Combination Networks with Cache-aided Relays and Users

Kai Wan, Daniela Tuninetti, Pablo Piantanida, Mingyue Ji

Abstract

Caching is an efficient way to reduce peak hour network traffic congestion by storing some contents at the user's cache without knowledge of later demands. Coded caching strategy was originally proposed by Maddah-Ali and Niesen to give an additional coded caching gain compared the conventional uncoded scheme. Under practical consideration, the caching model was recently considered in relay network, in particular the combination network, where the central server communicates with $K=\binom{H}{r}$ users (each is with a cache of $M$ files) through $H$ immediate relays, and each user is connected to a different $r-$subsets of relays. Several inner bounds and outer bounds were proposed for combination networks with end-user-caches. This paper extends the recent work by the authors on centralized combination networks with end-user caches to a more general setting, where both relays and users have caches. In contrast to the existing schemes in which the packets transmitted from the server are independent of the cached contents of relays, we propose a novel caching scheme by creating an additional coded caching gain to the transmitted load from the server with the help of the cached contents in relays. We also show that the proposed scheme outperforms the state-of-the-art approaches.

Introduction

As mobile data demand continues to grow, network congestion during peak hours has become a critical bottleneck for service providers. Caching—storing popular content closer to the user during off-peak hours—is a standard solution to mitigate this. Traditional caching is often "uncoded," simply storing raw file fragments. However, coded caching strategies can provide significant additional gains by enabling multicasting opportunities that satisfy multiple users with a single transmission.

This research focuses on Combination Networks, a hierarchical topology where a central server reaches users through a layer of intermediate relays. This model effectively mimics real-world structures like macro base stations communicating with small cells, which then serve end-users.

The Combination Network Model

In the studied model, a server containing $N$ files (each of size $B$ bits) connects to $H$ relays. There are $K = \binom{H}{r}$ users, where each user is connected to a unique subset of $r$ relays. Crucially, both the relays and the users are equipped with caches. The goal is to coordinate the content stored in these caches to minimize the "max-link load"—the maximum amount of data any single link must carry during peak hours.

Figure 1: Topology of a combination network with $H$ relays and $K$ users, where both layers possess local caches.

Previous research often treated relay and user caches as separate problems. This paper addresses the challenge of how to coordinate these layers to minimize backhaul traffic from the server to the relays.

Proposed Methodology: Asymmetric Coded Placement

The authors propose a novel scheme based on Asymmetric Coded Placement, which operates in two distinct phases:

  1. Placement Phase (Off-peak): Files are partitioned into fragments and encoded using Maximum Distance Separable (MDS) codes. Unlike previous schemes, the placement is "asymmetric," meaning the amount of data cached depends on the specific connectivity of the relays and users. The relay cache is designed to complement the user caches rather than act as simple pass-through storage.
  2. Delivery Phase (Peak-hour): When users request files, delivery occurs in three steps:
  3. Relay-to-User: Relays send bits they already have directly to their connected users.
  4. Side Information: Relays send specific bits that act as "keys" to help users decode future messages.
  5. Server-to-Relay (Multicasting): The server sends XORed (coded) messages. Because users have "side information" from their own caches and the relay caches, a single transmission from the server can satisfy multiple users simultaneously.

By treating the relay's cache as an extension of the user's memory, the server can "mask" data in a multicast transmission, knowing the relay can help the user unmask it later.

Key Results and Performance

The proposed scheme was evaluated using mathematical proofs and numerical simulations, comparing it against the previous state-of-the-art (Zewail and Yener, 2017). The results demonstrate a significant reduction in the server-to-relay load, which is often the most expensive "backhaul" part of a network.

Figure 2: Comparison of max link-load between the proposed scheme and the state-of-the-art across varying user cache sizes (Mu).

As shown in Figure 2, the proposed scheme achieves a lower server-to-relay load across the entire range of cache sizes. While there is a slight tradeoff—reducing the backhaul load can marginally increase the load from relays to users—the overall efficiency gain is substantial. In specific configurations (e.g., 5 relays and 10 users), the server-to-relay load was found to be less than half of previous best-known methods. Furthermore, the authors provide a mathematical proof (Theorem 1) establishing that their scheme's max-link load is never larger than the current state-of-the-art.

Conclusion and Future Work

By strategically coordinating cache content across both relays and users, this work provides a more efficient way to manage traffic in hierarchical networks. The primary limitation of the current model is its reliance on the highly symmetric "combination network" structure and centralized coordination. Future research will explore decentralized caching, where nodes cache content independently, and adapt these coded strategies for more irregular, dynamic real-world network topologies.

Summary updated

Abstract

Caching is an efficient way to reduce peak hour network traffic congestion by storing some contents at the user's cache without knowledge of later demands. Coded caching strategy was originally proposed by Maddah-Ali and Niesen to give an additional coded caching gain compared the conventional uncoded scheme. Under practical consideration, the caching model was recently considered in relay network, in particular the combination network, where the central server communicates with $K=\binom{H}{r}$ users (each is with a cache of $M$ files) through $H$ immediate relays, and each user is connected to a different $r-$subsets of relays. Several inner bounds and outer bounds were proposed for combination networks with end-user-caches. This paper extends the recent work by the authors on centralized combination networks with end-user caches to a more general setting, where both relays and users have caches. In contrast to the existing schemes in which the packets transmitted from the server are independent of the cached contents of relays, we propose a novel caching scheme by creating an additional coded caching gain to the transmitted load from the server with the help of the cached contents in relays. We also show that the proposed scheme outperforms the state-of-the-art approaches.
BibTeX
@inproceedings{wan2018combination,
  author = {Kai Wan and Daniela Tuninetti and Pablo Piantanida and Mingyue Ji},
  title = {{On Combination Networks with Cache-aided Relays and Users}},
  booktitle = {WSA},
  year = {2018},
  url = {https://openreview.net/forum?id=qen1pAndOW5},
}
Figure