Network Coding encourages information coding across a communication network. While the necessity, benefit and complexity of network coding are sensitive to the underlying graph structure of a network, existing theory on network coding often treats the network topology as a black box, focusing on algebraic or information theoretic aspects of the problem. This work aims at an in-depth examination of the relation between algebraic coding and network topologies. We mathematically establish a series of results along the direction of: if network coding is necessary beneficial, or if a particular finite field is required for coding, then the network must have a corresponding hidden structure embedded in its underlying topology, and such embedding is computationally efficient to verify. Specifically, we first formulate a meta-conjecture, the NC-Minor Conjecture, that articulates such a connection between graph theory and network coding, in the language of graph minors. We next prove that the NC-Minor Conjecture is almost equivalent to the Hadwiger Conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of @math , @math , @math , and @math minors, for networks requiring @math , @math , @math and @math , respectively. We finally prove that network coding can make a difference from routing only if the network contains a @math minor, and this minor containment result is tight. Practical implications of the above results are discussed.
Two concurrent work also examine the connection between algebraic coding and network topologies. (1) Ebrahimi and Fragouli @cite_18 investigate such a connection using an algebraic approach. Based on the algebraic framework due to Koetter and M 'edard @cite_23 , they scrutinize the network polynomial that is used for multicast code assignment. The goal is to understand what structures in the network lead to which type of monomials in the network polynomial, and hence to bound the necessary field size by bounding the highest degree of the monomials. (2) Xiahou @cite_11 investigate such a connection using a graph coloring approach, in planar and pseudo planar networks, and special types of planar networks where all relays or all terminals appear on a common face. Their work is complementary to ours in that they design efficient network code assignment algorithms over small fields, while our work proves the sufficiency of small fields in more general types of networks.
@cite_18 @cite_23 @cite_11
2102620382 2138928022
It is well known that transfer polynomials play an important role in the network code design problem. In this paper we provide a graph theoretical description of the terms of such polynomials. We consider acyclic networks with arbitrary number of receivers and min-cut h between each source-receiver pair. We show that the associated polynomial can be described in terms of certain subgraphs of the network.1 We take a new look at the issue of network capacity. It is shown that network coding is an essential ingredient in achieving the capacity of a network. Building on recent work by (see Proc. 2001 IEEE Int. Symp. Information Theory, p.102), who examined the network capacity of multicast networks, we extend the network coding framework to arbitrary networks and robust networking. For networks which are restricted to using linear network codes, we find necessary and sufficient conditions for the feasibility of any given set of connections over a given network. We also consider the problem of network recovery for nonergodic link failures. For the multicast setup we prove that there exist coding strategies that provide maximally robust networks and that do not require adaptation of the network interior to the failure pattern in question. The results are derived for both delay-free networks and networks with delays.