Placement Delivery Arrays from Combinations of Strong Edge Colorings

Jerod Michel, Qi Wang

Abstract

It has recently been pointed out that placement delivery arrays (PDAs) are equivalent to strong edge colorings of bipartite graphs. In this paper, we consider various methods of combining two or more strong edge colorings of bipartite graphs to obtain new ones, and therefore new PDAs. Combining PDAs in certain ways also gives a framework for obtaining PDAs with more robust and flexible parameters. We investigate how the parameters of certain strong edge colorings change after being combined with others and find that subpacketization levels can often be significantly improved.

The Coded Caching Challenge

In modern wireless networking, high-definition video streaming and large-scale data transfers often lead to severe network congestion. Centralized coded caching is a promising strategy to alleviate this issue. The process occurs in two phases:

  1. Placement Phase: During off-peak hours, a central server "pushes" parts of popular files into the local caches of users.
  2. Delivery Phase: When users request specific files, the server broadcasts XOR-coded signals. Because of the clever placement phase, multiple users can use these broadcast signals to recover their requested data simultaneously, significantly reducing the load on the shared link.
Figure 1: The centralized coded caching system model, featuring a server with $N$ files, a shared link, and $K$ users with local caches of size $M$.

The Subpacketization Bottleneck

While theoretically sound, coded caching faces a major practical hurdle: subpacketization ($F$). To generate effective XOR codes, files must be partitioned into numerous small packets. In early models, the required number of packets grew exponentially with the number of users ($K$). For a system with 100 users, the subpacketization level could become astronomically large, making the scheme impossible to implement on real hardware. This paper focuses on designing Placement Delivery Arrays (PDAs)—the mathematical blueprints for these schemes—that minimize $F$ while maintaining efficient transmission rates.

Bridging Caching and Graph Theory

The core insight of this research is the formal equivalence between PDAs and strong edge colorings of bipartite graphs. In this mapping, one set of vertices represents file packets, the other set represents users, and the "colors" assigned to edges represent the specific time slots used for transmission in the delivery phase.

Figure 2: An example of a strong edge coloring in a bipartite graph, illustrating how transmission slots (colors) are assigned to user-packet pairs.

By viewing the problem through the lens of graph theory, researchers can apply established combinatorial techniques to optimize network performance.

Methods for Generating Efficient PDAs

The authors introduce three primary methods for constructing new, more efficient PDAs by combining existing ones:

  1. Direct Combination: Merging PDAs that share transmission slots to create larger, more robust systems.
  2. Tensor-like Products: By "multiplying" smaller, well-understood caching schemes using the tensor product of bipartite graphs, the authors can build large systems where the number of packets grows much more slowly than the number of users.
  3. Strong-like Products: This sophisticated approach utilizes cycle graphs ($C_m$) and graph orientations to support more users while keeping the transmission rate low.

Key Results and Impact

The paper demonstrates that these graph-based combinations lead to massive reductions in system complexity. For example, in a system with 182 users, the authors' method reduced the required subpacketization from 101,147 packets to just 3,003 packets—a 33x improvement.

Furthermore, using tensor products for a system of 784 users, the subpacketization level was slashed from approximately 2.6 million to just 5,215, while simultaneously improving transmission efficiency (reducing the rate $R$ from 39.5 to 16). These results suggest that the subpacketization level can grow sub-exponentially, making coded caching viable for large-scale deployments.

Conclusion and Future Work

By leveraging the equivalence between PDAs and strong edge colorings, this work provides a powerful framework for designing practical coded caching schemes. While the mathematical descriptions of these combined graphs can become complex, the resulting reductions in subpacketization are a critical step toward implementing coded caching in real-world wireless networks. Future research will focus on identifying the optimal "seed" graphs for these combinations and addressing the computational overhead of XOR decoding on mobile devices.

Summary updated

Abstract

It has recently been pointed out in both of the works [C. Shanguan, Y. Zhang, and G. Ge, {\em IEEE Trans. Inform. Theory}, 64(8):5755-5766 (2018)] and [Q. Yan, X. Tang, Q. Chen, and M. Cheng, {\em IEEE Commun. Lett.}, 22(2):236-239 (2018)] that placement delivery arrays (PDAs), as coined in [Q. Yan, M. Cheng, X. Tang, and Q. Chen, {\em IEEE Trans. Inform. Theory}, 63(9):5821-5833 (2017)], are equivalent to strong edge colorings of bipartite graphs. In this paper we consider various methods of combining two or more strong edge colorings of bipartite graphs to obtain new ones, and therefore new PDAs. Combining PDAs in certain ways also gives a framework for obtaining PDAs with more robust and flexible parameters. We investigate how the parameters of certain strong edge colorings change after being combined with others and, after comparing the parameters of the resulting PDAs with those of the initial ones, find that subpacketization levels thusly can often be improved.
BibTeX
@article{michel2020placement,
  author = {Jerod Michel and Qi Wang},
  title = {{Placement Delivery Arrays from Combinations of Strong Edge Colorings}},
  journal = {IEEE Trans. Communications},
  year = {2020},
  url = {https://openreview.net/forum?id=s4FbY2XNltH},
}
Figure