In this paper, we introduce construction techniques for network coding in bidirectional networks with arbitrary transmission delays. These coding schemes reduce the number of transmissions and achieve the optimal rate...
详细信息
In this paper, we introduce construction techniques for network coding in bidirectional networks with arbitrary transmission delays. These coding schemes reduce the number of transmissions and achieve the optimal rate region in the corresponding broadcast model for both multiple unicast and multicast cases with up to three users, under the equal rate constraint. The coding schemes are presented in two phases;first, coding schemes for line, star and line-star topologies with arbitrary transmission delays are provided and second, any general topology with multiple bidirectional unicast and multicast sessions is shown to be decomposable into these canonical topologies to reduce the number of transmissions. As a result, the coding schemes developed for the line, star, and line-star topologies serve as building blocks for the construction of more general coding schemes for all networks. The proposed schemes are proved to be real time in the sense that they achieve the minimum decoding delay. With a negligible size header, these coding schemes are shown to be applicable to unsynchronized networks, i.e., networks with arbitrary transmission delays. Finally, we demonstrate the applicability of these schemes by extensive simulations. The implementation of such coding schemes on a wireless network with arbitrary transmission delays can improve performance and power efficiency.
In recent literature, network coding has emerged as a promising information theoretic approach to improve the performance of both peer-to-peer (P2P) and wireless networks. It has been widely accepted and acknowledged ...
详细信息
In recent literature, network coding has emerged as a promising information theoretic approach to improve the performance of both peer-to-peer (P2P) and wireless networks. It has been widely accepted and acknowledged that network coding can theoretically improve network throughput of multicast sessions in directed acyclic graphs, achieving their cut-set capacity bounds. Recent studies have also supported the claim that network coding is beneficial for large-scale P2P content distribution, as it solves the problem of locating the last missing blocks to complete the download. We seek to perform a reality check of using network coding for P2P live multimedia streaming. We start with the following critical question: How helpful is network coding in P2P streaming? To address this question, we first implement the decoding process using Gauss-Jordan elimination, such that it can be performed while coded blocks are progressively received. We then implement a realistic testbed, called Lava, with actual network traffic to meticulously evaluate the benefits and tradeoffs involved in using network coding in P2P streaming. We present the architectural design challenges in implementing network coding for the purpose of streaming, along with a pull-based P2P live streaming protocol in our comparison studies. Our experimental results show that network coding makes it possible to perform streaming with a finer granularity, which reduces the redundancy of bandwidth usage, improves resilience to network dynamics, and is most instrumental when the bandwidth supply barely meets the streaming demand.
The usage of network coding technology in the network can effectively improve the network performance in many aspects, such as delay, energy consumption, and throughput. Considering that multiple data streams can be e...
详细信息
The usage of network coding technology in the network can effectively improve the network performance in many aspects, such as delay, energy consumption, and throughput. Considering that multiple data streams can be encoded together, the network node forwards the data packet to reduce the transmission times of the encoded data packet in the wireless network. In particular, a measurement standard based on the number of pre-coding transmissions is proposed with the help of network coding and multiplexing technology. First, the opportunistic routing strategy between multiple data streams of network coding is applied to optimize the forwarding and transmission mode of data storage, which can effectively reduce the transmission of data packets. Second, the concept of coding is introduced into the relay nodes in the network, and the data distribution strategy is used to reduce the number of data packet transmissions in the network. Finally, a measurement standard for the number of pre-coding transmissions is designed for the resource allocation path in wireless multi-hop networks. The experimental results show that the strategy proposed in this paper can achieve a lower transmission delay compared with the single-path transmission strategies and the multi-path data distribution strategies without considering network coding.
In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both a...
详细信息
In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both are correlated. Moreover, nodes' availability and connectivity is dynamic-a scenario typical for wireless networks. Our contribution is twofold. First, although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static networks. In an information spreading scheme, however, nodes may communicate by continuously exchanging packets according to some underlying communication model. The main figure of merit is the stopping time-the time required until nodes can successfully decode. While information spreading schemes, such as gossip, are practical, distributed, and scalable, they have only been studied for uncorrelated data. We close this gap by providing techniques to analyze network-coded information spreading in dynamic networks with correlated data. Second, we give a clean framework for oblivious dynamic network models that in particular applies to a multitude of wireless network and communication scenarios. We specify a general setting for the data model and give tight bounds on the stopping times of network-coded protocols in this wide range of settings. En route, we analyze the capacities seen by nodes under a network-coded information spreading protocol, a previously unexplored question. We conclude with extensive simulations, clearly validating the key trends and phenomena predicted in the analysis.
To apply network coding for quantum computation, we study the distributed implementation of unitary operations over all separated input and output nodes of quantum networks. We consider networks where quantum communic...
详细信息
To apply network coding for quantum computation, we study the distributed implementation of unitary operations over all separated input and output nodes of quantum networks. We consider networks where quantum communication between nodes is restricted to sending a qubit, but classical communication is unrestricted. We analyze which N-qubit unitary operations are implementable over cluster networks by investigating transformations of a given cluster network into quantum circuits. We show that any two-qubit unitary operation is implementable over the butterfly network and the grail network, which are fundamental primitive networks for classical network coding. We also analyze probabilistic implementations of unitary operations over cluster networks.
The problem of serving multicast flows in a crossbar switch is considered. Intraflow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is...
详细信息
The problem of serving multicast flows in a crossbar switch is considered. Intraflow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout-splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph, where the imperfection ratio measures a certain graph theoretic property of the given graph. When applied to K x N switches with unicasts and broadcasts only, this gives a bound of min (2K-1/K, 2N/N+1) on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region.
Today's mobile video streaming performance on wireless networks is choppy due to the unpredictable wireless errors and mobility. In this Letter, we propose a practical online scheduling algorithm for mobile video ...
详细信息
Today's mobile video streaming performance on wireless networks is choppy due to the unpredictable wireless errors and mobility. In this Letter, we propose a practical online scheduling algorithm for mobile video streaming to multiple users with network coding capabilities. Implementation and analysis results show that our scheme closely approximates the optimal solution both mobile video quality and throughput.
This paper serves as a tutorial lecture on the use of network coding to provide resource efficient and agile proactive protection. network coding, which was introduced in Ahlswede et al. (2000) [1], allows intermediat...
详细信息
This paper serves as a tutorial lecture on the use of network coding to provide resource efficient and agile proactive protection. network coding, which was introduced in Ahlswede et al. (2000) [1], allows intermediate network nodes to form linear combinations of packets received on different input links. The use of network coding results in capacity enhancement. This capacity enhancement is used to provide protection channels which are used to carry combinations of redundant data, and are solved by the receivers in order to recover data lost due to network failures. The paper starts by addressing network coding-based protection of bidirectional unicast connections, and explains the use of p-Cycles to carry linear combinations of the redundant data units. The paper also discusses an earlier protection strategy which is based on diversity coding, in which the linear combinations are formed at special nodes, including sources, and is used to protect unidirectional connections. A generalized network coding-based protection which uses a tree to carry the linear combinations will be presented. Protection of multicast connections using network coding is also explained. (C) 2013 Elsevier B.V. All rights reserved.
Wireless network coding is a useful technology that can increase the total throughput of wireless networks. There are, however, few works focusing on wireless network coding over fading channels, which is an important...
详细信息
Wireless network coding is a useful technology that can increase the total throughput of wireless networks. There are, however, few works focusing on wireless network coding over fading channels, which is an important characteristic of many real wireless channels and may result in performance degradation. To investigate the fading channel's impact on network coding, based on the constant transmission power scheme and the channel inversion-transmission scheme, we analyze network throughput over Rayleigh fading channels. It is shown that, when the difference between average channel gains over two broadcasting channels is very large, the throughput of network coding greatly decreases, and the advantage of network coding almost disappears. To address this issue and to maximize the throughput of network coding over fading channels, we formulate the fading compensation for network coding as optimization problems and present the optimal transmission data rate and transmission power level of the relay node. Furthermore, to consider the realization problem of network coding over fading channels, including unbalanced traffic load and asynchronization of packet arrivals, we present two opportunistic optimal network coding (OONC) schemes. Performance evaluation has shown that the proposed opportunistic schemes perform well in various scenarios.
Energy efficient broadcast is indispensable for many applications in wireless ad hoc networks. It has been proved that network coding has great potential to improve performance in terms of energy consumption in wirele...
详细信息
Energy efficient broadcast is indispensable for many applications in wireless ad hoc networks. It has been proved that network coding has great potential to improve performance in terms of energy consumption in wireless ad hoc networks. However, the power of network coding depends on the availability of coding opportunities, which in turns depends on how routing paths are established. It is thus beneficial to establish paths in such a way that more coding opportunities are created. By combining network coding and connected dominating set (CDS), we explore energy minimal broadcast protocols in wireless ad hoc networks. The rationale behind this combination is that CDS provides better chances for data flows to intersect, which means more coding opportunities. We design a scheme, named NCDS, that uses network coding over connected dominating set, to reduce energy consumption. Analysis and experimental results show that NCDS outperforms broadcast algorithms that use CDS or network coding alone.
暂无评论