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.

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 work, 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 the two known types of networks with non-zero max-flow min-cut gaps. Further combing this result with a computer-aided search, we derive as a corollary that network coding is unnecessary in networks with up to 6 nodes. We also prove the multiple-unicast conjecture for almost all unit-link-length networks with up to 3 sessions and 7 nodes.

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 (singlesource) multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' qL. 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 pL 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 someq'L, 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.

This work studies how to minimize communication cost for placing Virtual Machines (VMs) in a modular data center. We consider a number of cooperative VMs implementing the same job, with known inter-VM communication patterns. The modular data center has a two-layer network structure, where computing pods constitute basic building blocks and are connected by a core network. At the core network layer, we design spectral clustering algorithms to partition VMs into computing pods, minimizing inter-pod communication cost. We then further apply an SDP relaxation approach to decide the VM placement within each computing pod, targeting both load balancing among physical servers and inter-server communication cost minimization. Extensive simulations are conducted to validate the efficacy of the proposed hierarchical VM placement scheme.

In the literature of network coding, 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). A scalar linear code over GF(q) is simply a vector linear code of dimension 1 over GF(q), and a general network has a scalar linear solution over GF(qL) only if it has a vector linear solution of dimension L over GF(q). Though vector LNC is more powerful in enabling a higher coding diversity, this work will present explicit multicast networks, for the first time in the literature, 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 q'L. This reveals the fact that although vector LNC can outperform scalar LNC in terms of yielding a solution for a general network, scalar LNC can also outperform vector LNC of dimension larger than 1 in terms of using a smaller alphabet to yield a solution for a multicast network.

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 ω ≥ 3, there is a multicast network with source outdegree ω 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) that q > 5 is a Mersenne prime plus 1, which can be extremely large; 3) a multicast network linearly solvable over GF(qm1) and over GF(qm2) is not necessarily linearly solvable over GF(qm1+m2); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size qminfor a linear solution over GF(qmin) is lower bounded by O(√|T|), but not every larger field than GF(qmin) 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.

Distributed storage systems provide large-scale reliable data storage services by spreading redundancy across a large group of storage nodes. In such big systems, node failures take place on a regular basis. When a node fails or leaves the system, to maintain the same level of redundancy, it is expected to regenerate the redundant data at a replacement node as soon as possible. Previous studies aim to minimize the network traffic in the regeneration process, but in practical networks, where link capacities vary in a wide range, minimizing network traffic does not always mean minimizing regeneration time. Considering the heterogeneous link capacities, Li et al. proposed a tree-structured regeneration scheme, called RCTREE, to bypass the low-capacitated link encountered in direct transmissions. However, we find that RCTREE may rapidly lose data integrity after several regenerations. In this paper, we reconsider the problem of minimizing regeneration time in networks with heterogeneous link capacities. We derive the minimum amount of data to be transmitted through each link to preserve data integrity. We prove that building an optimal regeneration tree is NP-complete and propose a heuristic algorithm for a near-optimal solution. We further introduce a flexible regeneration scheme, which allows providers to generate different amount of coded data. Simulation results show that the flexible tree-structured regeneration scheme can reduce the regeneration time significantly.

Network coding encourages the mixing of information flows at intermediate nodes of a network for enhanced network capacity, especially for one-to-many multicast applications. A fundamental problem in multicast network coding is to construct a feasible solution such that encoding and decoding are performed over a finite field of size as small as possible. Coding operations over very small finite fields (e.g., F2) enable low computational complexity in theory and ease of implementation in practice. In this work, we propose a new approach based on matroid theory to study multicast network coding and its minimum field size requirements. Applying this new approach that translates multicast networks into matroids, we derive the first upper-bounds on the field size requirement based on the number of relay nodes in the network, and make new progresses along the direction of proving that coding over very small fields (F2and F3) suffices for multicast network coding in planar networks.

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 work, 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. Specifically, we prove by construction that: (i) For every source dimension no smaller than 3, there is a multicast network linearly solvable over GF(7) but not over GF(8), and there is another multicast network linearly solvable over GF(16) but not over GF(17); (ii) There is a multicast network linearly solvable over GF(5) but not over such GF(q) that q > 5 is a Mersenne prime plus 1, which can be extremely large.

As storage systems grow in size, device failures happen more frequently than ever before. Given the commodity nature of hard drives employed, a storage system needs to tolerate a certain number of disk failures while maintaining data integrity, and to recover lost data with minimal interference to normal disk I/O operations. RAID-6, which can tolerate up to two disk failures with the minimum redundancy, is becoming widespread. However, traditional RAID-6 codes suffer from high disk I/O overhead during recovery. In this paper, we propose a new family of RAID-6 codes, the Minimum Disk I/O Repairable (MDR) codes, which achieve the optimal disk I/O overhead for single failure recoveries. Moreover, we show that MDR codes can be encoded with the minimum number of bit-wise XOR operations. Simulation results show that MDR codes help to save about half of disk read operations than traditional RAID-6 codes, and thus can reduce the recovery time by up to 40%.

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.

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 K4, K5, K6, and KO(q/log q) minors, for networks that require F3, F4, F5, and Fqto 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 K4minor, and this minor containment result is tight. Practical implications of the above results are discussed.

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 K4, K5, K6, and KO(q/ log q)minors, for networks requiring F3, F4, F5and Fq, respectively. We finally prove that network coding can make a difference from routing only if the network contains a K4minor, and this minor containment result is tight. Practical implications of the above results are discussed.

Matroidal networks play a fundamental role in proving theoretical results on the limits of network coding. This can be explained by the underlying connections between network coding and matroid theory, both of which build upon the fundamental concept of independence. Two existing methods are known in the network coding literature for constructing networks from a matroid. The method due to Dougherty et al. [5] is high in time complexity but can create relatively simple network structures from a given matroid. Another method due to El Rouayheb et al. [3] is low in time complexity, but results in rather complex network structures. This work studies the design of matroidal networks from uniform matroids, targetting both low time complexity and minimum network sizes. Our construction is based on the new technique of dependence deduction, which may serve as a promising direction for constructing general matroidal networks. Some of our constructions lead to new networks for understanding network coding in terms of base field requirement.

IEEE 802.16j has introduced the concept of WiMAX mesh network model, which adds a special type of nodes called Relay Stations (RSs) for Subscriber Stations (SSs). With the help of RSs, a WiMAX mesh network is able to provide larger wireless coverage, higher network capacity and Non-Line-OfSight (NLOS) communications. In this paper, we propose a novel strategy which named Dual-Path Relay Placement (DPRP) to improve the efficiency of relay station placement in WiMAX mesh networks. DPRP is a more reliable model that takes users Spectrum Efficiency into account and thus can achieve efficient spatial reuse by two independent parallel transmission paths.If the distance between Subscriber Station and Base Station is constant, the SS's Spectrum Efficiency has a big influence on the number of relays required by the SS. For a given attenuation coefficient, DPRP needs less RSs than Single-Path Relay Placement (SPRP) when the SS's Spectrum Efficiency exceeds a certain threshold. The analysis proves that the higher the Spectrum Efficiency is, the greater the difference is between the relay's number of two models. If the new model is integrated with the SPRP model, the total number of RSs required per cell will decrease a lot.

Network coding is a technique that allows information flows to be encoded while routed across a data network. It was shown that network coding helps increase the throughput and reduce the cost of data transmission, especially for one-to-many multicast applications. An important direction in network coding research 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 of coding advantage: directed networks and undirected networks. The study of coding advantage in this work further focuses on two types of parameterized networks, including bidirected networks and hyper-networks, which generalizes the directed and the undirected network models, respectively. With proper parameter setting, more realistic modeling of networks in practice can be achieved. We prove upper-bounds and lower-bounds on the coding advantage for multicast in these models. Some of our bounds are new and unknown before, some improve upon previously proven bounds, and some answer open questions in the literature.

Space information flow is a new field of research recently proposed by Li and Wu [1], [2]. It studies the transmission of information in a geometric space, where information flows can be routed along any trajectories, and can be encoded wherever they meet. The goal is to satisfy given end-to-end unicast/multicast throughput demands, while minimizing a natural bandwidth-distance sum-product (network volume). Space information flow models the design of a blueprint for a minimum-cost network. We study the multicast version of the space information flow problem, in Euclidean spaces. We present a simple example that demonstrates the design of an information network is indeed different from that of a transportation network. We discuss properties of optimal multicast network embedding, prove that network coding does not make a difference in the basic case of 1-to-2 multicast, and prove upper-bounds on the number of relay nodes required in an optimal acyclic multicast network.

Nowadays, the real practice of network coding in wireline networks is focused on the P2P overlay networks. Although it can help to utilize network resources more efficiently, P2P network coding does not exhibit benefits in terms of the maximum throughput. Our work aims to implement network coding at the IP layer, which is an idea not fundamentally new, but with little real practice because of the enormous difficulties involved. In this paper we propose CODED IP, a protocol framework that plugs network coding into the current IP stack. Experiments on a 22-node testbed show that CODED IP provides multicast traffic with not only a significantly higher throughput than overlay network coding and naive IP multicast, but also a more balanced load distribution as compared with overlay network coding.