Search

High capacity storage systems distribute less across several storage devices (nodes) and apply an erasure code to meet availability and reliability requirements.Since devices can lose network connectivity or fail permanently, a dynamic repair mechanism must be put in place. In such cases a new recovery node gets connected to a given subset of the operating nodes and receives a part of the stored data. The objective of this paper is to investigate data survival for Random Linear Network Coding (RLNC) as a function of topology and communication overhead, dened by the number of connections and the number of transmitted packets to the recovery node, respectively. The paper includes two main contributions. First, a sufficient set of conditions for quasi-infinite longevity of the stored data is derived. Second,a comparison using experimental results shows that RLNC can be up to 50% more effective than traditional erasure codes like Reed-Solomon.

Random Linear Network Coding (RLNC) theoretical results typically assume that packets have equal sizes while in reality, data traffic presents a random packet size distribution. Conventional wisdom considers zero-padding of original packets as a viable alternative, but its effect can reduce the efficiency of RLNC or other erasure coding techniques. Our goal is to characterize the overhead generated by this zero-padding under real-traffic traces. These include TCP and UDP traces from traffic at core routers from CAIDA and a collection of video traces for different codecs and video resolution compiled by Arizona State University. Our numerical results show the dependence of the zero-padding overhead with the number of packets combined in a generation using RLNC. Surprisingly, medium and large TCP generations are strongly affected with more than 100% of padding overhead. Although all video traces are affected, our results show that higher resolution video has a lower overhead, due in part to the fact that most of the transmitted data packets are of the maximum size of packet in the network.

State-of-the-art Network coding based routing protocols exploit the link quality information to compute the transmission rate in the intermediate nodes. However, the link quality discovery protocols are usually inaccurate, and introduce overhead in wireless mesh networks. In this paper, we present an adaptive approach for opportunistic routing which, adapts the threshold for activating the helper node based on the previous transmitted packets status in the next hop. Our simulation results show that this adaptive approach performs as well as the same approach with prior and perfect knowledge of the channel states. Furthermore, measurements using our Raspberry Pi testbed demonstrate that our adaptive approach outperforms the previous mechanism in real channel conditions, with only 1% overhead due to linearly dependent coded packets compared to the 11% overhead of the standard PlayNCool approach.

We study the problem of minimizing the cost of packet transmission from a source to two receivers with the help of a relay and using network coding in wireless mesh networks consisting of many active neighbours sharing the same channel. The cost minimization problem is modeled as a Markov Decision Process (MDP) and analysed under different network conditions. Two simple heuristics are proposed to estimate the appropriate time for activating the relay to provide close-to-optimal performance. Our numerical results show that a judicious network coding enabled relay can bring up to 2.9x gains in the presence of active neighbours compared to multicasting directly from the source. We further show that in scenarios which the links between relay and destinations are not better than the links between source and destinations, a relay can still provide up to 1.7x gain.

Network coding has its roots in information theory where it was initially proposed as a way to improve a two-node communication using a (broadcasting) relay. For this theoretical construct, a satellite communications system was proposed as an illustrative example, where the relay node would be a satellite covering the two nodes. The benefits in terms of throughput, resilience, and flexibility of network coding are quite relevant for wireless networks in general, and for satellite systems in particular. This chapter presents some of the basics in network coding, as well as an overview of specific scenarios where network coding provides a significant improvement compared to existing solutions, for example, in broadcast and multicast satellite networks, hybrid satellite-terrestrial networks, and broadband multibeam satellites. The chapter also compares coding perspectives and revisits the layered networking paradigm, before drawing conclusions and identifying promising developments in this topic.

This article addresses a fundamental resource allocation problem that arises in monitoring applications: given the locations of the motes, the amount of data that needs to be transferred from each mote to the base station, and an Unmanned Vehicle (UV), find (i) a communication network among the motes, (ii) a subset of motes, referred to as cluster-heads, that act as relays between the motes and the UV, and (iii) a path for the UV such that each mote uses the communication network to transmit its data to one of the cluster-heads, each of the cluster-heads is visited by the UV, and the sum of communication costs involved in transmitting the data from the motes to the cluster-heads and the travel costs of the UV is a minimum. This problem is a generalization of a single Traveling Salesman Problem (TSP) and is NP-Hard. This article presents a rounding algorithm and heuristics to solve the problem. Computational results show that the rounding algorithm performed the best for the tested instances with up to 50 motes and produce solutions that are on an average within 5% of the optimum time relatively fast.

A protocol for use in wireless mesh networks (PlayNCool) uses helper nodes to improve data flow in the network. The protocol is compatible with traditional mesh network routing algorithms. Techniques, systems, devices, and circuits for implementing the protocol are described.

This paper seeks to understand and characterize policies that exploit multiple available technologies and/or het- erogeneous communication routes simultaneously with the goal of improving throughput and energy performance or economi- cal costs. Such policies may be instrumental towards allowing improved services to mobile devices in converged networks. We present an optimization framework and a set of allocation policies to provide efficient, channel-aware load allocation for multi- homed devices under different cost criteria. Network coding is used as a key enabler of these techniques as coding across packets requires less coordination, simpler and less frequent feedback mechanisms, and higher resiliency to changes in the transmission channel. Our formulation incorporates bursty erasure channels, multiple simultaneous communication routes, and different chan- nel coding and modulations available to each technology as part of the resource allocation optimization. Numerical results are pro- vided showing that dynamic allocation policies are instrumental to improving resource efficiency by reducing energy consumption and/or channel utilization. The energy gains of our proposed policies outperform the best fixed network coding multi-homing policies by a factor of 2 in some scenarios.

This paper presents a detailed performance evaluationof inter-session network coding in wireless meshed networksin terms of throughput and energy consumption. A full analyticalmodel is given for three different communication approaches forthe bidirectional cross topology using an IEEE 802.11 mediumaccess. One of the three approaches is pure relaying, while theother two approaches are using network coding with and withoutoverhearing of other flows. The main outcome of the paper isthat network coding without and with overhearing can increasethe throughput by the factor of two and four, respectively, forhigh load scenarios. Furthermore we show that the energy/bitratio is decreased by the use of network coding approaches,underlining that the added complexity of network coding paysoff when considering the overall system.

Low latency and high reliability is a critical characteristics of many wireless use cases, such as real–time video surveillance. In a dense network the best way to resolve such problems is by utilizing the fastest and most reliable connection to the destination. Classical solutions, such as Reed–Solomon codes, increase the reliability, but also introduce additional coding delays at the relays. This paper describes the reduction of the packet delay achievable by network coding through a series of network nodes. Our metric captures the elapsed time between (network) encoding RTP frames and complete decoding of the packets on the receiver side while playing out the video recording contained in the payload. Our solutions are implemented and evaluated on serially connected Raspberry Pi devices and a network (de)coding enabled software running on a regular PC. We find that the recoding relays work at least as well as the systematic approach to network coding. In all cases network coding outperformed schemes employing the classical forward error correcting Reed–Solomon codes. This low per–packet delay and the inherent reliability of our schemes make these solutions particularly suitable for real–time multimedia delivery in contrast to other classical and network coding strategies.

Random linear network coding (RLNC) has been shown to provide increased throughput, security and robustness for the transmission of data through the network. Most of the analysis and the demonstrators have focused on the study of data packets with the same size (number of bytes). This constitutes a best case scenario as coded packets will incur little overhead to handle such packets. However, packet lengths are quite heterogeneous in real networks, which can cause a high overhead or, alternatively, a high delay in the transmission of data packets. As we show, this can have a severe effect on a variety of applications. This paper proposes a series of mechanisms to manage heterogeneous packet lengths and analyzes the induced overhead of those mechanisms using real packet length distributions provided by CAIDA and own measurements using video content. Our results show that an appropriate packetization of the data packets can reduce the overhead from over 100% (zero-padding packets) to below 5% for CAIDA packet distributions and that the right choice of parameters can reduce the overhead to less than 10% in the case of video data.

Cloud and distributed storage applications require processing of large fragments of data. This poses memory, delay, and processing speed challenges for systems using erasure codes to reduce the cost of storage and/or increase the reliability of the system. To address these, this paper proposes and deploys designs that exploit current multi-threading capabilities of microprocessors to accelerate the encoding and decoding process of erasure codes, focusing on the case of Random Linear Network Coding (RLNC). More specifically, we propose a strategy for parallel computation based on splitting symbols into significantly smaller fragments and reordering data to speed up computation and decreasing the potential for thread blocking. We implement the strategy in C++ and carry out benchmark experiments and compare them with the single threaded state-of-the-art block RLNC encoders. We show a reduction of processing time by a factor of three by using our strategies for files of 32 MB or more as well as reducing memory usage drastically in the system. We also show that our approach provides a better scaling than the single-threaded option when increasing the number of fragments that a file is broken into. In other words, distributed storage systems can split files or data into a larger number of fragments without experiencing a speed penalty.

A wireless network protocol (CORE) and related methods, systems, and circuits are disclosed that are capable of enhancing network performance. The protocol uses random linear network coding (RLNC) for intra-session coding in the network, while allowing nodes in the network to set up inter-session coding regions where flows intersect. Within the inter-session coding regions, combinations of coded packets associated with different unicast sessions are permitted. However, packets associated with multiple different unicast sessions are not allowed to be transmitted outside of the coding regions.

This work proposes a new protocol applying on–the–fly random linear network coding in wireless mesh net-works. The protocol provides increased reliability, low delay,and high throughput to the upper layers, while being obliviousto their specific requirements. This seemingly conflicting goalsare achieved by design, using an on–the–fly network codingstrategy. Our protocol also exploits relay nodes to increasethe overall performance of individual links. Since our protocolnaturally masks random packet losses from the upper layers, itmakes it particularly suitable for enhancing TCP’s performancein wireless mesh networks, where packet losses are typicallyinterpreted as a sign of congestion by TCP’s congestion controlalgorithms, thus crippling TCP’s throughput. To investigate thegains and downsides of our protocol, we implement it as aconfigurable proof-of-concept application, which is deployed andevaluated in a real test bed with Raspberry Pi devices. We showthat order of magnitude gains in throughput over plain TCP arepossible with moderate losses and up to two fold improvementin per packet delay in our results.

A method, apparatus and computer program product for utilizing network coding for multi-resolution multicast is presented. A network source partitions source content into a base layer and one or more refinement layers. The network source receives a respective one or more push-back messages from one or more network destination receivers, the push-back messages identifying the one or more refinement layers suited for each one of the one or more network destination receivers. The network source computes a network code involving the base layer and the one or more refinement layers for at least one of the one or more network destination receivers, and transmits the network code to the one or more network destination receivers in accordance with the push-back messages.

Tunable sparse network coding (TSNC) constitutes a promising concept for trading off computational complexity and delay performance. This paper advocates for the use of judicious feedback as a key not only to make TSNC practical, but also to deliver a highly consistent and controlled delay performance to end devices. We propose and analyze a TSNC design that can be incorporated into both unicast and multicast data flows. An implementation of our approach is carried out in C++ and compared to random linear network coding (RLNC) and sparse versions of RLNC implemented in the fastest network coding library to date. Our measurements show that the processing speed of our TSNC mechanism can be increased by four-fold compared to an optimized RLNC implementation and with a minimal penalty on delay performance. Finally, we show that even a limited number of feedback packets (< 6 per generation) can result in a radical improvement of the complexity-delay trade-off.

This paper demonstrates the quick prototyping capabilities of the Python-Kodo library for network coding based performance evaluation and investigates the problem of data redundancy in a network coded wireless mesh with opportunistic overhearing. By means of several wireless meshed architectures simulated on the constructed test-bed, the advantage of network coding over state of the art routing schemes and the challenges of this new technology are shown. By providing maximum control of the network coding parameters and the simulation environment to the user, the test-bed facilitates quick construction of simulation setups on top of it. The paper highlights the problem of redundant transmission of data by the overhearing nodes in a wireless mesh and by means of three simple simulation setups that are built on top of the test-bed, the paper provides a brief insight into the selection of appropriate relays. Finally, various sending policies that can be employed by the nodes in order to improve the overall transmission efficiency in a dynamic wireless mesh network are discussed and their performance is analysed on the constructed simulation setup.

Video surveillance and similar real-time applications on wireless networks require increased reliability and high performance of the underlying transmission layer. Classical solutions, such as Reed-Solomon codes, increase the reliability, but typically have the negative side-effect of additional overall delays due to processing overheads. This paper describes the delay reduction achieved through online network coding approaches with a limit on the number of packets to be mixed before decoding and a systematic encoding structure. We use the inorder per packet delay as our key performance metric. This metric captures the elapsed time between (network) encoding RTP packets and completely decoding the packets in-order on the receiver side. Our solutions are implemented and evaluated on a point-to-point link between a Raspberry Pi device and a network (de)coding enabled software running on a regular PC. We find that our sliding window approach (more feedback) outperforms all other tested mechanisms in terms of per-+packet delay including the Reed-Solomon encoding employing the systematic approach, a random linear network coding approach, and our proposed on-the-fly network coding approach (which relies on less feedback).We show gains in order of magnitudes between our sliding window and the other approaches when we manage the redundancy transmission adaptively. This low per-packet delay and the inherent reliability of our schemes make these solutions particularly suitable for real-time multimedia delivery in contrast to other classical and network coding strategies.