Search

In complex network environments, there always exist heterogeneous devices with different computational powers. In this work, we propose a novel scalable random linear network coding (RLNC) framework based on embedded fields, so as to endow heterogeneous receivers with different decoding capabilities. In this framework, the source linearly combines the original packets over embedded fields based on a precoding matrix and then encodes the precoded packets over GF(2) before transmission to the network. After justifying the arithmetic compatibility over different finite fields in the encoding process, we derive a sufficient and necessary condition for decodability over different fields. Moreover, we theoretically study the construction of an optimal precoding matrix in terms of decodability. The numerical analysis in classical wireless broadcast networks illustrates that the proposed scalable RLNC not only guarantees a better decoding compatibility over different fields compared with classical RLNC over a single field, but also outperforms Fulcrum RLNC in terms of a better decoding performance over GF(2). Moreover, we take the sparsity of the received binary coding vector into consideration, and demonstrate that for a large enough batch size, this sparsity does not affect the completion delay performance much in a wireless broadcast network. [ABSTRACT FROM AUTHOR]

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, and with local encoding kernels chosen from cyclic permutation matrices. When $L$ is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF($2^{L-1}$) induces an $L$ -dimensional circular-shift linear solution at rate $(L-1)/L$. In this paper, we prove that for arbitrary odd $L$ , every scalar linear solution over GF($2^{m_{L}}$), where $m_{L}$ refers to the multiplicative order of 2 modulo $L$ , can induce an $L$ -dimensional circular-shift linear solution at a certain rate. Based on the generalized connection, we further prove that for such $L$ with $m_{L}$ beyond a threshold, every multicast network has an $L$ -dimensional circular-shift linear solution at rate $\phi (L)/L$ , where $\phi (L)$ is the Euler’s totient function of $L$. An efficient algorithm for constructing such a solution is designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable. [ABSTRACT FROM AUTHOR]

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations consist of only circular-shifts and bit-wise additions. Formulated as a special vector linear code over GF(2), an $L$ -dimensional circular-shift linear code of degree $\delta $ restricts its local encoding kernels to be the summation of at most $\delta $ cyclic permutation matrices of size $L$. We show that on a general network, for a certain block length $L$ , every scalar linear solution over GF($2^{L-1}$) can induce an $L$ -dimensional circular-shift linear solution with 1-bit redundancy per-edge transmission. Consequently, specific to a multicast network, such a circular-shift linear solution of an arbitrary degree $\delta $ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of $\delta $. By further proving that circular-shift LNC is insufficient to achieve the exact capacity of certain multicast networks, we show the optimality of the efficiently constructed circular-shift linear solution in the sense that its 1-bit redundancy is inevitable. Finally, both theoretical and numerical analysis imply that with increasing $L$ , a randomly constructed circular-shift linear code has linear solvability behavior comparable to a randomly constructed permutation-based linear code, but has shorter overheads. [ABSTRACT FROM AUTHOR]

The multiple-unicast conjecture in network coding states that for multiple unicast sessions in an undirected network, network coding has no advantage over routing in improving the throughput or saving bandwidth. In this paper, we propose a reduction method to study the multiple-unicast conjecture, and prove the conjecture for a new class of networks that are characterized by relations between cut-sets and source-receiver paths. This class subsumes all the known types of networks with non-zero max-flow min-cut gaps but zero coding advantage. Combining this result with a computer-aided search, we derive as a corollary that network coding is unnecessary in networks with up to six coding nodes. We also prove the multiple-unicast conjecture for almost all unit-link-length networks with up to three sessions and seven nodes. [ABSTRACT FROM AUTHOR]

Space Information Flow (SIF) is a new promising research area that studies network coding in geometric space, such as Euclidean space. The design of algorithms that compute the optimal SIF solutions remains one of the key open problems in SIF. This work proposes the first exact SIF algorithm and a heuristic SIF algorithm that compute min-cost multicast network coding for N (N ≥ 3) given terminal nodes in 2-D Euclidean space. Furthermore, we find that the Butterfly network in Euclidean space is the second example besides the Pentagram network where SIF is strictly better than Euclidean Steiner minimal tree. The exact algorithm design is based on two key techniques: Delaunay triangulation and linear programming. Delaunay triangulation technique helps to find practically good candidate relay nodes, after which a min-cost multicast linear programming model is solved over the terminal nodes and the candidate relay nodes, to compute the optimal multicast network topology, including the optimal relay nodes selected by linear programming from all the candidate relay nodes and the flow rates on the connection links. The heuristic algorithm design is also based on Delaunay triangulation and linear programming techniques. The exact algorithm can achieve the optimal SIF solution with an exponential computational complexity, while the heuristic algorithm can achieve the sub-optimal SIF solution with a polynomial computational complexity. We prove the correctness of the exact SIF algorithm. The simulation results show the effectiveness of the heuristic SIF algorithm. [ABSTRACT FROM AUTHOR]

For a (single-source) multicast network, the size of a base field is the most known and studied algebraic identity that is involved in characterizing its linear solvability over the base field. In this paper, we design a new class \mathcal N of multicast networks and obtain an explicit formula for the linear solvability of these networks, which involves the associated coset numbers of a multiplicative subgroup in a base field. The concise formula turns out to be the first that matches the topological structure of a multicast network and algebraic identities of a field other than size. It further facilitates us to unveil infinitely many new multicast networks linearly solvable over GF( q ) but not over GF( q' ) with q < q' , based on a subgroup order criterion. In particular: 1) for every k\geq 2 ) but not over GF( 2^{2k+1} ) and 2) for arbitrary distinct primes p and p' , there are infinitely many k and k' ) but not over GF( p'^k' ) with p^k < p'^k' . [ABSTRACT FROM PUBLISHER]

Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L -dimensional vector of data symbols over a base field GF( q ). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (single-source) multicast networks that are vector linearly solvable of dimension L over GF( q . This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes p^{L} with respect to an arbitrary prime p$ . On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L$ over GF(2) but have scalar linear solutions over GF( q'$ ) for some , where $q'$ can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension $L$ does not necessarily have a vector linear solution of dimension $L' > L$ . [ABSTRACT FROM AUTHOR]

In an acyclic multicast network, it is well known that a linear network coding solution over GF( q ) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF( q ) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every \omega \geq 3 , there is a multicast network with source outdegree \omega linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF( q ) and over GF( q^m2 ) is not necessarily linearly solvable over GF( q^{m1 + m2} ); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size q_{\mathrm{ min}} for a linear solution over GF( q_{\mathrm{ min}} ) is lower bounded by \Theta (\sqrt T) , but not every larger field than GF( q\mathrm{ min} ) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network. [ABSTRACT FROM AUTHOR]

Cooperative communication is starting to attract substantial research attention in quantum information theory. However, given a specific network, it is still unknown whether quantum cooperative communication can be successfully performed. In this paper, we investigate network coding for quantum cooperative multicast (QCM) over the classic butterfly network. A very reasonable definition of QCM is first introduced. It not only perfectly focuses on the basic idea of quantum cooperative communication, but also wonderfully reflects the characteristic of classical multicast over a specific network structure. Next, we design QCM protocol for two-level systems and generalize the protocol into d-dimensional Hilbert space. It is shown that our protocols have significant advantages in terms of resource cost and compatibility with classical multicast. Besides, the success probability, which only depends on the coefficients of the initial quantum states, is carefully analyzed. In particular if the source nodes choose the quantum equatorial states, success probability can reach 1. [ABSTRACT FROM AUTHOR]

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 paper 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 for multicasting two information flows is almost equivalent to the Hadwiger conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of \(K_{4}\) , \(K_{5}\) , \(K_{6}\) , and \(K_{O(q/\log {q})}\) minors, for networks that require \(\mathbb {F}_{3}\) , \(\mathbb {F}_{4}\) , \(\mathbb {F}_{5}\) , and \(\mathbb {F}_{q}\) to multicast two flows, respectively. We finally prove that, for the general case of multicasting arbitrary number of flows, network coding can make a difference from routing only if the network contains a \(K_{4}\) minor, and this minor containment result is tight. Practical implications of the above results are discussed. [ABSTRACT FROM AUTHOR]

The multiple-unicast network coding conjecture states that for multiple unicast sessions in an undirected network, network coding is equivalent to routing. Simple and intuitive as it appears, the conjecture has remained open since its proposal in 2004, and is now a well-known unsolved problem in the field of network coding. Based on a recently proposed tool of space information flow, we present a geometric framework for analyzing the multiple-unicast conjecture. The framework consists of four major steps, in which the conjecture is transformed from its throughput version to cost version, from the graph domain to the space domain, and then from high dimension to 1-D, where it is to be eventually proved. We apply the geometric framework to derive unified proofs to known results of the conjecture, as well as new results previously unknown. A possible proof to the conjecture based on this framework is outlined. [ABSTRACT FROM AUTHOR]

Network coding encourages information flow mixing in a network. It helps increase the throughput and reduce the cost of data transmission, especially for one-to-many multicast applications. An interesting problem is to understand and quantify the coding advantage and cost advantage, i.e., the potential benefits of network coding, as compared to routing, in terms of increasing throughput and reducing transmission cost, respectively. Two classic network models were considered in previous studies: directed networks and undirected networks. This work further focuses on two types of parameterized networks, including bidirected networks and hyper-networks, generalizing the directed and the undirected network models, respectively. We prove upper- and lower-bounds on multicast coding advantage and cost advantage in these models. [ABSTRACT FROM PUBLISHER]