On Equivalence Between Network Topologies

Michelle Effros, Tracey Ho, Shirin Jalali

Abstract

One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy.

Introduction

Determining the capacity region of a complex network—the maximum set of data rates that can be reliably transmitted—is a notoriously difficult open problem in network information theory. While tools like Linear Programming (LP) outer bounds exist, their complexity grows exponentially with the number of links. For networks larger than a few nodes, standard software like ITIP or XITIP often fails to provide results. This paper addresses this scalability gap by introducing a hierarchical method to simplify complex network topologies into smaller, more manageable versions.

Hierarchical Simplification

The core of the proposed method is the systematic replacement of intricate subnetworks with simpler "equivalent" or "bounding" models. This allows researchers to calculate the capacity of large networks that were previously computationally inaccessible.

A complex network structure with multiple intermediate nodes and links.

The approach relies on several key operations:

  1. Bounding Models: An "upper bounding model" is a simpler structure capable of implementing any function the original subnetwork could. Conversely, a "lower bounding model" is one whose functions can all be implemented by the original.
  2. Equivalence: If a simplified model acts as both an upper and a lower bound, it is considered "equivalent," meaning the reduction in nodes and links does not change the theoretical capacity.
  3. The Y-Network: A significant portion of the analysis focuses on the "Y-network"—a structure with two sources, one relay, and one sink. The authors prove that many overlapping or generalized Y-shaped structures can be collapsed into a single, simple Y-network.
The simplified Y-network model.

Key Insights and Theoretical Results

The paper provides several surprising insights into network simplification:

  • Lossless Simplification: Certain families of network structures can be simplified with zero loss in accuracy. For instance, Lemma 1 demonstrates that if the capacities of two overlapping Y-networks maintain specific rational ratios, they are perfectly equivalent to a single, larger Y-network.
  • Bounded Impact of Small Links: Theorem 1 proves that removing a link with capacity $\epsilon$ from a network with a "super-source" (a node connected to all sources) changes the capacity region by at most $\epsilon$. This justifies "pruning" low-capacity links to simplify analysis.
  • The Difference Factor ($\Delta$): To quantify the gap between upper and lower bounds when perfect equivalence is impossible, the authors introduce a metric $\Delta$. They show that even in complex cases, they can often find bounds with a worst-case difference factor of 0.5, providing a guaranteed level of accuracy.

Conclusion and Future Work

While this hierarchical approach offers a powerful tool for network analysis, it currently has limitations. The primary results assume the network is a Directed Acyclic Graph (DAG), as cycles introduce significant complexity regarding delay. Furthermore, the focus is on "noiseless bit-pipes" (links with fixed capacity). Future research is needed to extend these simplification tools to noisy networks involving broadcast, multiple access, and interference links, as well as to decentralized networks where a "super-source" may not exist.

Summary updated

Abstract

One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy.
BibTeX
@inproceedings{effros2010equivalence,
  author = {Michelle Effros and Tracey Ho and Shirin Jalali},
  title = {{On Equivalence Between Network Topologies}},
  booktitle = {Allerton},
  year = {2010},
  doi = {10.1109/allerton.2010.5706933},
}
Figure