Network-Coding Solutions for Minimal Combination Networks and Their Sub-Networks

Han Cai, Johan Chrisnata, Tuvi Etzion, Moshe Schwartz, Antonia Wachter-ZehIEEE Trans. Information Theory 2020 · OpenReview

TL;DR

This paper investigates the "gap" between scalar and vector linear network coding solutions for minimal multicast networks, particularly focusing on combination networks. The authors introduce Kneser networks as a key tool to achieve the maximum possible gap for networks with two source messages and demonstrate that this gap exists for networks with more source messages as well. They also establish an upper bound on this gap for full combination networks, showing it's significantly smaller than for their sub-networks.

What Problem Does This Paper Address?

Network coding aims to improve the efficiency and reliability of data transmission in networks. A crucial aspect is finding the smallest alphabet size (field size) required for a network to have a linear coding solution. This paper focuses on the difference between the alphabet size needed for a scalar linear solution (where coefficients and messages are scalars) and a vector linear solution (where coefficients are matrices and messages are vectors). This difference is termed the "gap."

The paper specifically targets minimal multicast networks. These are networks where removing any single link breaks the ability of all receivers to get all messages. Minimal networks are desirable because they use the fewest resources. The authors are interested in understanding the gap in these minimal networks, particularly within the well-studied family of "combination networks" and their sub-networks. They aim to find the maximum possible gap and to understand when this gap is significant, especially for networks with a small number of source messages (like two), where previous work had shown no gap or only small gaps.

Methods

The paper employs several key techniques:

  • Graph Theory and Network Modeling: Networks are represented as directed acyclic graphs. Concepts like cuts, in-degrees, and graph homomorphisms are fundamental.
  • Linear Algebra over Finite Fields: The core of network coding relies on linear algebra over finite fields (denoted $\mathbb{F}_q$). Vector spaces, subspaces, and their dimensions are central to defining solutions.
  • Gaussian Coefficients: These are used to count the number of subspaces of a given dimension over a finite field, playing a role in determining solution sizes.
  • q-Kneser Graphs: A novel construction, the "skeleton" of a network, is used to map network properties to graph properties. The paper extensively uses the q-analog of Kneser graphs ($qK_{n:m}$), which are graphs whose vertices are subspaces of a vector space, and edges connect subspaces with specific intersection properties.
  • Graph Homomorphisms: These are used to relate the solvability of networks to the existence of colorings of related graphs. A homomorphism from a network's skeleton to a q-Kneser graph implies the existence of a vector linear solution.
  • MDS Codes: The paper leverages results from coding theory, specifically MDS (Maximum Distance Separable) codes, to bound the parameters of linear solutions for combination networks.
  • Combinatorial Constructions: New network structures, termed "Kneser networks," are introduced and analyzed. These are designed to exhibit large gaps.

Datasets

Not discussed in the paper. The paper deals with theoretical network structures and their properties, not empirical evaluation on datasets.

Key Insights and Ideas

  • The Gap is Achievable in Minimal Networks: The paper demonstrates that a significant gap between scalar and vector linear solutions can exist in minimal multicast networks, even with just two source messages. This is a key finding, as previous work often required more messages or non-minimal networks for substantial gaps.
  • Kneser Networks as Gap Maximizers: The newly defined "Kneser networks" are shown to achieve the maximum possible gap for minimal networks with two source messages. This highlights their importance as extremal examples.
  • Skeletonization Unifies Analysis: The concept of "skeletonizing" a network (mapping it to a graph based on its structure) provides a powerful tool to connect network coding properties to graph properties, particularly q-Kneser graphs. This allows for a more unified theoretical analysis.
  • Sub-networks Drive the Gap: The study of sub-networks of combination networks (Kneser networks) is shown to be sufficient for understanding the maximum gap in minimal multicast networks with two source messages. This suggests that the complexity of the gap often arises from specific structural components rather than the full network.
  • Full Combination Networks Have Small Gaps: In contrast to their sub-networks, full minimal combination networks exhibit very small gaps, often close to zero. This implies that while specific configurations can create challenges for scalar solutions, the overall structure of full combination networks is relatively efficient for both scalar and vector solutions.

Key Results

  • Maximum Gap for h=2: For minimal multicast networks with two source messages ($h=2$), the paper finds the maximum possible gap and constructs Kneser networks that achieve this maximum gap with equality. The gap is shown to be at least $\psi(q^t + q^{t-1} - 1) - q^t$, where $\psi$ is the "prime ceiling" function.
  • Gap for h>2: The paper proves that Kneser networks with three or more source messages ($h \ge 3$) also exhibit a gap, though the analysis becomes more complex.
  • Upper Bound on Gap for Full Combination Networks: An upper bound on the gap for full minimal combination networks ($N_{h,r,h}$) is established, showing it's at most $h-2$ plus a term related to prime gaps, and is often close to zero. This contrasts sharply with the gaps found in their sub-networks.
  • Minimality and Gap: The paper suggests that minimality of a network plays a role in limiting the gap, though a formal proof for $h \ge 3$ is left as future work.

Limitations and Future Work

  • Gap for $h \ge 3$ in Full Networks: While the paper shows a gap exists for Kneser networks with $h \ge 3$, it doesn't provide an upper bound for the gap in full combination networks with $h \ge 3$. This is an open question.
  • Minimality vs. Network Structure: The paper raises the question of whether the gap is primarily driven by the minimality of the network or by its specific structure (like being a sub-network of a combination network). This distinction is still an open area of research.
  • Non-linear vs. Linear Solutions: The paper focuses on linear solutions. The gap between non-linear and linear solutions for multicast networks remains an open and challenging problem.
  • Generalization of q-Kneser Graphs: The paper uses a specific generalization of q-Kneser graphs for hypergraphs. Further exploration of these structures and their relation to network coding could be fruitful.
  • Optimality of Gap for $h \ge 3$: While a gap is shown for $h \ge 3$, its optimality (i.e., whether it's the maximum possible gap) is not fully established for all cases.

Summary updated

Abstract

Minimal multicast networks are fascinating and efficient combinatorial objects, where the removal of a single link makes it impossible for all receivers to obtain all messages. We study the structure of such networks, and prove some constraints on their possible solutions. We then focus on the combination network, which is one of the simplest and most insightful network in network-coding theory. Of particular interest are minimal combination networks. We study the gap in alphabet size between vector-linear and scalar-linear network-coding solutions for such minimal combination networks and some of their sub-networks. For minimal multicast networks with two source messages we find the maximum possible gap. We define and study sub-networks of the combination network, which we call Kneser networks, and prove that they attain the upper bound on the gap with equality. We also prove that the study of this gap may be limited to the study of sub-networks of minimal combination networks, by using graph homomorphisms connected with the q -analog of Kneser graphs. Additionally, we prove a gap for minimal multicast networks with three or more source messages by studying Kneser networks. Finally, an upper bound on the gap for full minimal combination networks shows nearly no gap, or none in some cases. This is obtained using an MDS-like bound for subspaces over a finite field.
BibTeX
@article{cai2020network,
  author = {Han Cai and Johan Chrisnata and Tuvi Etzion and Moshe Schwartz and Antonia Wachter-Zeh},
  title = {{Network-Coding Solutions for Minimal Combination Networks and Their Sub-Networks}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=1xMXzb0WYtD},
}
Figure