Information flow decomposition for network coding

We propose a method to identify structural properties of multicast network configurations, by decomposing networks into regions through which the same information flows. This decomposition allows us to show that very different networks are equivalent from a coding point of view, and offers a means to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent tasks: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive the smallest code alphabet size sufficient to code any network configuration with two sources as a function of the number of receivers in the network. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose deterministic algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes that can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.     

Unachievability of network coding capacity

The coding capacity of a network is the supremum of ratios k/n, for which there exists a fractional (k,n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding capacity is referred to as routing capacity in the case when only routing is allowed. A network is said to achieve its capacity if there is some fractional (k,n) solution for which k/n equals the capacity. The routing capacity is known to be achievable for arbitrary networks. We give an example of a network whose coding capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.     

A Constant Bound on Throughput Improvement of Multicast Network Coding in Undirected Networks

Recent research in network coding shows that, joint consideration of both coding and routing strategies may lead to higher information transmission rates than routing only. A fundamental question in the field of network coding is: how large can the throughput improvement due to network coding be? In this paper, we prove that in undirected networks, the ratio of achievable multicast throughput with network coding to that without network coding is bounded by a constant ratio of $2$, i.e., network coding can at most double the throughput. This result holds for any undirected network topology, any link capacity configuration, any multicast group size, and any source information rate. This constant bound $2$ represents the tightest bound that has been proved so far in general undirected settings, and is to be contrasted with the unbounded potential of network coding in improving multicast throughput in directed networks.      

Increasing the network performance using multi-path routing mechanism with load balance

Research on multi-path routing protocols to provide improved throughput and route resilience as compared with single-path routing has been explored in details in the context of wired networks. However, multi-path routing mechanisms have not been explored thoroughly in the domain of ad hoc networks. In this paper, we propose a new routing protocol which increases the network throughput. The protocol is a multi-path routing protocol with a load balance policy. The simulations show a significant improvement in terms of connection throughput and end-to-end delay, when compared to single-path routing. The second significant contribution of this paper is a theoretical analysis allowing to compare reactive single-path and multi-path routing with load balance mechanisms in ad hoc networks, in terms of overheads, traffic distribution and connection throughput. The results reveal that multi-path routing (using a load balance policy) provides better performance than reactive single-path routing in terms of congestion and connection throughput, provided that the average route length is smaller than certain upper bounds which are derived and depend on parameters specific to the network. These upper bounds are very crucial because they can be taken into account as constraints in the route discovery mechanism so that the multi-path routing protocol is guaranteed to lead to an increase performance than a simple single-path one. Also, our analysis provide some insight into choosing the right trade-off between increased overheads and better performance. We show in particular that for certain networks, a multi-path routing strategy is not worth considering.     

Optimized multipath network coding in lossy wireless networks

Network coding has been a prominent approach to a series of problems that used to be considered intractable with traditional transmission paradigms. Recent work on network coding includes a substantial number of optimization based protocols, but mostly for wireline multicast networks. In this paper, we consider maximizing the benefits of network coding for unicast sessions in lossy wireless environments. We propose Optimized Multipath Network Coding (OMNC), a rate control protocol that dramatically improves the throughput of lossy wireless networks. OMNC employs multiple paths to push coded packets to the destination, and uses the broadcast MAC to deliver packets between neighboring nodes. The coding and broadcast rate is allocated to transmitters by a distributed optimization algorithm that maximizes the advantage of network coding while avoiding congestion. With extensive experiments on an emulation testbed, we find that OMNC achieves more than two-fold throughput increase on average compared to traditional best path routing, and significant improvement over existing multipath routing protocols with network coding. The performance improvement is notable not only for one unicast session, but also when multiple concurrent unicast sessions coexist in the network.     

Network routing capacity

We define the routing capacity of a network to be the supremum of all possible fractional message throughputs achievable by routing. We prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every rational number in (0, 1] is the routing capacity of some solvable network. We also determine the routing capacity for various example networks. Finally, we discuss the extension of routing capacity to fractional coding solutions and show that the coding capacity of a network is independent of the alphabet used.     

Star-Structure Network Coding for Multiple Unicast Sessions in Wireless Mesh Networks

In this paper, first, we propose Star-NC, a new network coding (NC) scheme for multiple unicast sessions in an n-input n-output star structure. Then, we evaluate the network throughput of this coding scheme in wireless mesh network over the traditional non-NC transmission. Our scheme benefits from the proximity of all the nodes around the relay node and employs a more general form of overhearing different from other schemes such as COPE. We found that the gain of our NC scheme depends on both the star size and the routing pattern of the unicast transmissions. Based on this, we identify both the situations which the maximum gain is achievable and a lower bound for the expected value of the gain in the case of random routing pattern. Next, we propose an analytical framework for studying throughput gain of our Star-NC scheme in general wireless network topologies. Our theoretical formulation via linear programming provides a method for finding source-destination routes and utilizing the best choices of our NC scheme to maximize the throughput. Finally, we evaluate our model for various networks, traffic models and routing strategies over coding-oblivious routing. We also compare the throughput gain of our scheme with COPE-type NC scheme. We show that Star-NC exploits new coding opportunities different from COPE-type NC and thus can be used with or without this scheme. The results show that Star-NC has often better performance than COPE for a directional traffic model which is a typical model in wireless mesh networks. Moreover, we found that, joint Star and COPE-type NC has better throughput performance than each of Star or COPE alone.     

Bounds on the throughput gain of network coding in unicast and multicast wireless networks

Gupta and Kumar established that the per node throughput of ad hoc networks with multi-pair unicast traffic scales with an increasing number of nodes n as lambda(n) = ominus(1/radic(n log n)), thus indicating that performance does not scale well. However, Gupta and Kumar did not consider network coding and wireless broadcasting, which recent works suggest have the potential to significantly improve throughput. Here, we establish bounds on the improvement provided by such techniques. For random networks of any dimension under either the protocol or physical model that were introduced by Gupta and Kumar, we show that network coding and broadcasting lead to at most a constant factor improvement in per node throughput. For the protocol model, we provide bounds on this factor. We also establish bounds on the throughput benefit of network coding and broadcasting for multiple source multicast in random networks. Finally, for an arbitrary network deployment, we show that the coding benefit ratio is at most O(log n) for both the protocol and physical communication models. These results give guidance on the application space of network coding, and, more generally, indicate the difficulty in improving the scaling behavior of wireless networks without modification of the physical layer.     

Network Lifetime Maximization for Estimation in Multihop Wireless Sensor Networks

We consider the distributed estimation by a network consisting of a fusion center and a set of sensor nodes, where the goal is to maximize the network lifetime, defined as the estimation task cycles accomplished before the network becomes nonfunctional. In energy-limited wireless sensor networks, both local quantization and multihop transmission are essential to save transmission energy and thus prolong the network lifetime. The network lifetime optimization problem includes three components: i) optimizing source coding at each sensor node, ii) optimizing source throughput of each sensor node, and iii) optimizing multihop routing path. Fortunately, source coding optimization can be decoupled from source throughput and multihop routing path optimization, and is solved by introducing a concept of equivalent 1-bit MSE function. Based on the optimal source coding, the source throughput and multihop routing path optimization is formulated as a linear programming (LP) problem, which suggests a new notion of character-based routing. The proposed algorithm is optimal and the simulation results show that a significant gain is achieved by the proposed algorithm compared with heuristic methods.     

Minimum-energy multicast in mobile ad hoc networks using network coding

The minimum energy required to transmit one bit of information through a network characterizes the most economical way to communicate in a network. In this paper, we show that, under a layered model of wireless networks, the minimum energy-per-bit for multicasting in a mobile ad hoc network can be found by a linear program; the minimum energy-per-bit can be attained by performing network coding. Compared with conventional routing solutions, network coding not only allows a potentially lower energy-per-bit to be achieved, but also enables the optimal solution to be found in polynomial time, in sharp contrast with the NP-hardness of constructing the minimum-energy multicast tree as the optimal routing solution. We further show that the minimum energy multicast formulation is equivalent to a cost minimization with linear edge-based pricing, where the edge prices are the energy-per-bits of the corresponding physical broadcast links. This paper also investigates minimum energy multicasting with routing. Due to the linearity of the pricing scheme, the minimum energy-per-bit for routing is achievable by using a single distribution tree. A characterization of the admissible rate region for routing with a single tree is presented. The minimum energy-per-bit for multicasting with routing is found by an integer linear program. We show that the relaxation of this integer linear program, studied earlier in the Steiner tree literature, can now be interpreted as the optimization for minimum energy multicasting with network coding. In short, this paper presents a unifying study of minimum energy multicasting with network coding and routing.     

BanyanNet-a bidirectional equivalent of ShuffleNet

A multihop, wavelength division multiplex (WDM) based network, BanyanNet, is proposed for the realization of terabit lightwave networks, BanyanNet can he considered as a the bidirectional equivalent of the popular ShuffleNet. Exploiting its representation, we developed a fast, decentralized, bidirectional routing algorithm for BanyanNet. The performance of BanyanNet is compared to that of the ShuffleNet and bilayered ShuffleNet. For N=p^m×k networks, the p=2 BanyanNet provides better performance in channel efficiency, total and user throughput than the corresponding ShuffleNet, and offers more flexible network configurations than the bilayered and p=4 ShuffleNet     

Multihour engineering and traffic routing optimization in hierarchical telephone networks

Classical hierarchical routing in telephone networks is extended to a wider class called out-of-chain routing in such a way that some useful properties of hierarchical routing are retained. This new routing pattern offers more potential paths than the fixed hierarchical one and can be introduced as a dynamic routing where the fixed alternate sequences change at some predetermined instants during the day. The effect of this new routing pattern on the network performances is examined. The main topic of this paper is to present heuristic methods used to optimise such routings in large networks. We show on artificial networks that the throughput of a given network can be significantly improved by suitable routing choices. We demonstrate that the integration of routing changes within a multihour dimensioning process is possible but the lack of realistic data does not permit at this time to quantify the value of routing optimization on real networks.     

Network-coding-based scheduling and routing schemes for service-oriented wireless mesh networks - [Service-oriented broadband wireless network architecture]

Service-oriented wireless mesh networks have recently been receiving intensive attention as a pivotal component to implement the concept of ubiquitous computing due to their easy and cost-effective deployment. To deliver a variety of services to subscriber stations, a large volume of traffic is exchanged via mesh routers in the mesh backbone network. One of the critical problems in service-oriented wireless mesh networks is to improve the network throughput. Wireless network coding is a key technology to improve network throughput in multihop wireless networks since it can exploit not only the broadcast nature of the wireless channel, but also the native physical-layer coding ability by mixing simultaneously arriving radio waves at relay nodes. We first analyze the throughput improvement obtained by wireless network coding schemes in wireless mesh networks. Then we develop a heuristic joint link scheduling, channel assignment, and routing algorithm that can improve the network throughput for service-oriented wireless mesh networks. Our extensive simulations show that wireless network coding schemes can improve network throughput by 34 percent.     

Video-aware opportunistic network coding over wireless networks

In this paper, we study video streaming over wireless networks with network coding capabilities. We build upon recent work, which demonstrated that network coding can increase throughput over a broadcast medium, by mixing packets from different flows into a single packet, thus increasing the information content per transmission. Our key insight is that, when the transmitted flows are video streams, network codes should be selected so as to maximize not only the network throughput but also the video quality. We propose video-aware opportunistic network coding schemes that take into account both the decodability of network codes by several receivers and the importance and deadlines of video packets. Simulation results show that our schemes significantly improve both video quality and throughput. This work is a first step towards content-aware network coding.     

Channel Adaptive Shortest Path Routing for Ad Hoc Networks

1　IntroductionAdhocnetworksareformedwithoutrequiringthepreexistinginfrastructureorcentralizedadminis tration ,incontrasttocellularnetworks.Asidefromtheoriginalmilitaryapplication ,ithasapplicationinpublicsafetyandcommercialareas,butadaptiveprotocolsarerequiredinorderforthemtodoso .Twoimportantcharacteristicsofacommunicationlinkinadhocnetworksareitsunreliabilityanditsvariability .Thelinksinsuchanetworkareunreli ablebecauseoffading ,interference,noise,andper hapsthefailureofthetransmittingorrec…     

Scaling Laws for Dense Gaussian Sensor Networks and the Order Optimality of Separation

We investigate the optimal performance of dense sensor networks by studying the joint source-channel coding problem. There are N uniformly spaced sensor nodes sampling noiselessly a one-dimensional spatial random process over an interval [0, U₀]. The overall goal of the sensor network is for the sensor nodes to code and transmit the measurement samples to a collector node over a cooperative multiple-access channel with noisy feedback, and for the collector node to reconstruct the entire random process with minimum expected distortion. We provide separation-based lower and upper bounds for the minimum achievable expected distortion when the underlying random process is Gaussian. When the Gaussian random process satisfies some general conditions, such as the eigenvalues of its Karhunen-Loeve expansion decrease roughly inverse polynomially in order x, i.e., the kth eigenvalue is roughly k^-x, we evaluate the lower and upper bounds explicitly, and show that they are of the same order for a wide range of power constraints. Thus, for these random processes, under these power constraints, we show that the minimum achievable expected distortion decreases as (log NP(N)^1-x, where P(N) is the sum power constraint on the sensor nodes. Further, we show that the achievability scheme that achieves the lower bound on the distortion is a separation-based scheme that is composed of multiterminal rate-distortion coding and amplify-and-forward channel coding. Therefore, we conclude that separation is order-optimal for the dense Gaussian sensor network scenario under consideration, when the underlying random process satisfies some general conditions.     

The encoding complexity of network coding

In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network G. The nodes of the multicast network can be broadly categorized into two groups. The first group includes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h/sup 3/k/sup 2/. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h/sup 3/k/sup 2/. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require /spl Omega/(h/sup 2/k) encoding nodes. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. We prove that the number of encoding nodes is bounded by (2B+1)h/sup 3/k/sup 2/, where B is the minimum size of a feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an /spl Nscr/P-hard problem.     

On Broadcast Stability of Queue-Based Dynamic Network Coding Over Erasure Channels

The transmission of packets is considered from one source to multiple receivers over single-hop erasure channels. The objective is to evaluate the stability properties of different transmission schemes with and without network coding. First, the throughput limitation of retransmission schemes is discussed and the stability benefits are shown for randomly coded transmissions, which, however, need not optimize the stable throughput for finite coding field size and finite packet block size. Next, a dynamic scheme is introduced for distributing packets among virtual queues depending on the channel feedback and performing linear network coding based on the instantaneous queue contents. The difference of the maximum stable throughput from the min-cut rate is bounded as function of the order of erasure probabilities depending on the complexity allowed for network coding and queue management. This queue-based network coding scheme can asymptotically optimize the stable throughput to the max-flow min-cut bound, as the erasure probabilities go to zero. This is realized for a finite coding field size without accumulating packet blocks at the source to start network coding. The comparison of random and queue-based dynamic network coding with plain retransmissions opens up new questions regarding the tradeoffs of stable throughput, packet delay, overhead, and complexity.      

Efficient Broadcasting Using Network Coding

We consider the problem of broadcasting in an ad hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless networks since it directly affects battery life and thus network lifetime. We prove that applying ideas from network coding allows to realize significant benefits in terms of energy efficiency for the problem of broadcasting, and propose very simple algorithms that allow to realize these benefits in practice. In particular, our theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. We calculate this factor exactly for some canonical configurations. We then show that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network coding can offer improvements of a factor of , where is the number of nodes in the network. We use the insights gained from the theoretical analysis to propose low-complexity distributed algorithms for realistic wireless ad hoc scenarios, discuss a number of practical considerations, and evaluate our algorithms through packet level simulation.     

A Cross-Layer Optimization Framework for Multihop Multicast in Wireless Mesh Networks

The optimal and distributed provisioning of high throughput in mesh networks is known as a fundamental but hard problem. The situation is exacerbated in a wireless setting due to the interference among local wireless transmissions. In this paper, we propose a cross-layer optimization framework for throughput maximization in wireless mesh networks, in which the data routing problem and the wireless medium contention problem are jointly optimized for multihop multicast. We show that the throughput maximization problem can be decomposed into two subproblems: a data routing subproblem at the network layer, and a power control subproblem at the physical layer with a set of Lagrangian dual variables coordinating interlayer coupling. Various effective solutions are discussed for each subproblem. We emphasize the network coding technique for multicast routing and a game theoretic method for interference management, for which efficient and distributed solutions are derived and illustrated. Finally, we show that the proposed framework can be extended to take into account physical-layer wireless multicast in mesh networks