On Combination Networks with Cache-aided Relays and Users

Kai Wan, Daniela Tuninetti, Pablo Piantanida, Mingyue Ji

TL;DR

This paper introduces a novel coded caching scheme for "combination networks"—hierarchical networks where a central server reaches users through a layer of intermediate relays. By strategically placing content in both relay and user caches and treating relay data as "side information" for the users, the authors significantly reduce the peak-hour traffic load from the server to the relays, outperforming previous state-of-the-art methods.

What Problem Does This Paper Address?

As mobile data demand skyrockets, network congestion during peak hours becomes a major bottleneck. Caching—storing popular content closer to the user during off-peak hours—is a standard solution. However, traditional caching is often "uncoded," meaning we just store raw file fragments.

The authors focus on Combination Networks, a specific topology where a server connects to $H$ relays, and each user is connected to a unique subset of $r$ relays. This model mimics real-world hierarchical structures like macro base stations communicating with small cells, which then serve end-users.

The core challenge is: how do we coordinate the cache content across both relays and users to minimize the "max-link load" (the maximum amount of data any single link must carry)? Previous research often treated relay caches and user caches as separate problems or ignored the potential for relay caches to help users decode complex, multicasted messages from the server.

Methods

The authors propose a scheme based on Asymmetric Coded Placement. Their approach breaks down into two phases:

  1. Placement Phase (Off-peak): Files are partitioned into fragments and encoded using Maximum Distance Separable (MDS) codes. These fragments are strategically distributed. Crucially, the placement is "asymmetric"—the amount of data cached depends on the specific connectivity of the relays and users. Unlike previous schemes, the relay cache isn't just a "pass-through" storage; it is designed to complement what the users are holding.
  2. Delivery Phase (Peak-hour): When users request files, the delivery happens 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.

This coordination creates a higher coded caching gain, meaning the server has to send fewer total bits to satisfy everyone's demands.

Datasets

As a theoretical paper in information theory and communications, this work does not use empirical datasets. Instead, the authors evaluate their scheme using:

  • Mathematical Proofs: To establish bounds on network load.
  • Numerical Simulations: Comparing the derived load equations of their scheme against the previous state-of-the-art (specifically the Zewail and Yener scheme from 2017) across various cache sizes ($M$).

Key Insights and Ideas

  • Relays as Side Information: The "Aha!" moment is treating the relay's cache as an extension of the user's memory. Even if a user hasn't cached a piece of a file, if their connected relay has it, the server can use that fact to "mask" other data in a multicast transmission, knowing the relay can help the user unmask it later.
  • Exploiting Topology: The scheme leverages the "combination" nature of the network. Since users share relays in specific patterns, the authors can design MDS codes that ensure the right "side information" is available at the right relays to maximize multicasting opportunities.
  • The Backhaul Tradeoff: The results show a tradeoff. By reducing the load from the server to the relays (often the most expensive "backhaul" part of a network), they might slightly increase the load from relays to users. In many modern wireless systems, the backhaul is the tighter bottleneck, making this a very favorable trade.

Key Results

  • Superior Efficiency: In specific examples (e.g., a network with 5 relays and 10 users), the proposed scheme achieved a server-to-relay load that was less than half of the previous best-known scheme.
  • Theorem 1: The authors mathematically prove that their scheme's max-link load is never larger than the current state-of-the-art, making it a strictly better or equal solution across all parameters.
  • Numerical Gains: Figure 2 in the paper illustrates that as user memory increases, the gap between the proposed scheme and existing ones widens, demonstrating better scalability.

Limitations and Future Work

  • Symmetry Assumptions: The "combination network" is a highly symmetric model. Real-world networks are often irregular and dynamic, which might make the precise MDS code coordination more difficult.
  • Centralized Coordination: The scheme assumes a centralized server knows the exact network topology and user demands to plan the placement. The authors mention that extending this to decentralized caching (where users/relays cache content independently) is a logical next step.
  • Complexity: Coded caching, especially with MDS codes and XORing, adds computational overhead to the nodes. The paper focuses on the transmission load but doesn't deeply explore the processing costs at the relays and handsets.

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 = 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},
}

Loading related content...

Figure