Search

Memory maximum-distance-separable (mMDS) sliding window codes are a type of erasure codes with high erasure-correction capability and low decoding delay. In this paper, we study two types of systematic mMDS sliding window codes over erasure channels, i.e., scalar codes defined over a finite field $GF(2^{L})$ , and vector codes defined over a vector space $GF(2)^{L}$. We first devise an efficient heuristic algorithm to produce an mMDS sliding window scalar code over relatively small $GF(2^{L})$. Then, we investigate a special class of mMDS sliding window vector codes whose encoding/decoding are achieved by basic circular-shift and bit-wise XOR operations, and propose a general method to generate such mMDS vector codes. Our complexity analysis shows that the proposed vector codes yield much lower encoding/decoding complexity than the scalar codes. The theoretical and numerical results also demonstrate that mMDS sliding window codes dominate MDS block codes in terms of decoding delay and erasure-correction capability. [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]

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]

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]

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 in-network information mixing for enhanced network capacity. An important open problem in network coding, the multiple-unicast network coding (MUNC) conjecture, claims that network coding is equivalent to routing for multiple unicast sessions in an undirected network. Simple and intuitive as it appears, the MUNC conjecture has remained open for a decade. This work studies a special case of MUNC, where intra-session connections are "better" than inter-session connections. In the cost domain, we prove that if each source is closer to its own receiver than to other receivers, then network coding is equivalent to routing. In the throughput domain, an intuitive dual statement is that if each source has a larger max-flow to its own receiver than to other receivers, then network coding is equivalent to routing. We prove that this statement is equivalent to the original MUNC conjecture. An interesting consequence is that an equivalence between the two seemingly dual statements studied in this work, if true, would imply the original MUNC conjecture. [ABSTRACT FROM PUBLISHER]

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]

We refer to network coding schemes in which information flows propagate along a combination network topology as combination network coding (CNC). CNC and its variations are the first network coding schemes studied in the literature, and so far still represent arguably the most important class of known structures where network coding is nontrivial. Our main goal in this paper is to seek a thorough understanding on the advantage of CNC in undirected networks, by proving a tight bound on its potential both in improving multicast throughput (the coding advantage) and in reducing multicast cost under a linear link flow cost model (the cost advantage). We prepare three results towards this goal. First, we show that the cost advantage of CNC is upper-bounded by 9\over 8 under the uniform link cost setting. Second, we show that achieving a larger cost advantage is impossible by considering an arbitrary instead of uniform link cost configuration. Third, we show that in a given network topology, for any form of network coding, the coding advantage under arbitrary link capacity configurations is always upper-bounded by the cost advantage under arbitrary link cost configurations. Combining the three results together, we conclude that the potential for CNC to improve throughput and to reduce routing cost are both upper-bounded by a factor of 9\over 8. The bound is tight since it is achieved in specific networks. This result can be viewed as a natural step towards improving the bound of 2 proved for the coding advantage of general multicast network coding. [ABSTRACT FROM AUTHOR]