Caching in Combination Networks: A Novel Delivery by Leveraging the Network Topology

Kai Wan, Mingyue Ji, Pablo Piantanida, Daniela TuninettiarXiv 2018 · OpenReview

Abstract

Maddah-Ali and Niesen (MAN) in 2014 surprisingly showed that it is possible to serve an arbitrarily large number of cache-equipped users with a constant number of transmissions by using coded caching in shared-link broadcast networks. This paper studies the tradeoff between the user's cache size and the file download time for combination networks, where users with caches communicate with the servers through intermediate relays. Motivated by the so-called separation approach, it is assumed that placement and multicast message generation are done according to the MAN original scheme and regardless of the network topology. The main contribution of this paper is the design of a novel two-phase delivery scheme that, accounting to the network topology, outperforms schemes available in the literature. The key idea is to create additional (compared to MAN) multicasting opportunities: in the first phase coded messages are sent with the goal of increasing the amount of 'side information' at the users, which is then leveraged during the second phase. The download time with the novel scheme is shown to be proportional to 1/H (with H being the number or relays) and to be order optimal under the constraint of uncoded placement for some parameter regimes.

Introduction

Modern network traffic management increasingly relies on caching to mitigate congestion. By storing popular content at user devices during off-peak hours, the load on the network during peak times can be significantly reduced. The seminal work by Maddah-Ali and Niesen (MAN) introduced "coded caching," demonstrating that XORed combinations of files can serve multiple users simultaneously, achieving a "multicasting gain" that scales with the total cache size in the network. However, the original MAN scheme assumes a simple shared-link broadcast channel. Real-world architectures often involve intermediate nodes, necessitating a study of more complex topologies.

System Model

This paper focuses on Combination Networks, a symmetric topology where a central server connects to $H$ relays, and each user connects to a unique subset of $r$ relays. Each of the $K$ users is equipped with a cache of size $M$ bits. The goal is to minimize the max-link load, defined as the maximum number of bits transmitted over any link in the network, normalized by the file size $B$.

Combination network topology featuring a central server, $H$ intermediate relays, and $K$ cache-equipped users.

The challenge in these networks is that, unlike a broadcast channel, not every relay can reach every user. A "topology-oblivious" approach would fail to fully exploit the available connectivity.

Proposed Two-Phase Delivery Scheme

The authors propose a "separation approach," maintaining the standard MAN uncoded placement but redesigning the delivery phase into two distinct stages:

  1. Phase 1: Side Information Generation. The server transmits MAN-style multicast messages to relays that can reach the highest number of users. While some users receive their requested data, others receive messages they do not currently need. These "unintended" messages serve as valuable side information for the next phase.
  2. Phase 2: Topology-Aware Delivery. The server generates new linear combinations (network coding) of the MAN messages, specifically designed to exploit the side information distributed in Phase 1. This phase leverages the fact that users are connected to multiple relays, creating new multicasting opportunities that were previously unavailable.

An Improved Delivery Scheme is also introduced, which further optimizes these linear combinations to ensure that a single relay transmission can satisfy as many users as possible simultaneously.

Performance Results

The proposed scheme is evaluated through both mathematical proofs of order optimality and numerical simulations. The authors prove that their scheme is optimal within a factor of $1 + t/r$ (where $t$ is a cache-related parameter) under the constraint of uncoded placement.

Comparison of the maximum link-load across different delivery schemes as a function of cache size $M$.

Numerical results demonstrate significant gains over existing benchmarks. For instance, in a network with 6 relays and 15 users, the proposed scheme achieves a max link-load of approximately 0.29, outperforming previous state-of-the-art methods which achieved 0.375. As shown in Figure 2, the "Improved scheme" consistently provides a lower max link-load across various cache sizes $M$, particularly in the small-cache regime. Furthermore, the download time scales as $1/H$, indicating excellent scalability as the number of relays increases.

Conclusion

By treating network topology as a resource rather than a constraint, this work provides a novel framework for coded caching in relay networks. The two-phase delivery strategy effectively "primes" users with side information, unlocking greater multicasting gains. While the current results assume symmetric combination networks and uncoded placement, they lay the groundwork for future explorations into asymmetric topologies and coded placement strategies.

Summary updated

Abstract

Maddah-Ali and Niesen (MAN) in 2014 surprisingly showed that it is possible to serve an arbitrarily large number of cache-equipped users with a constant number of transmissions by using coded caching in shared-link broadcast networks. This paper studies the tradeoff between the user's cache size and the file download time for combination networks, where users with caches communicate with the servers through intermediate relays. Motivated by the so-called separation approach, it is assumed that placement and multicast message generation are done according to the MAN original scheme and regardless of the network topology. The main contribution of this paper is the design of a novel two-phase delivery scheme that, accounting to the network topology, outperforms schemes available in the literature. The key idea is to create additional (compared to MAN) multicasting opportunities: in the first phase coded messages are sent with the goal of increasing the amount of `side information' at the users, which is then leveraged during the second phase. The download time with the novel scheme is shown to be proportional to 1=H (with H being the number or relays) and to be order optimal under the constraint of uncoded placement for some parameter regimes.
BibTeX
@misc{wan2018caching,
  author = {Kai Wan and Mingyue Ji and Pablo Piantanida and Daniela Tuninetti},
  title = {{Caching in Combination Networks: A Novel Delivery by Leveraging the Network Topology}},
  year = {2018},
  eprint = {1802.10479},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.10479},
}
Figure