Network coding achieves optimal throughput in multicast networks. However, throughput optimality relies on the network nodes or routers to code correctly. A Byzantine node may introduce junk packets in the network (thus polluting downstream packets and causing the sinks to receive the wrong data) or may choose coding coecients
@cite_27 have pioneered the field of network coding. They showed the value of coding at routers and provided theoretical bounds on the capacity of such networks. Works such as those of @cite_13 , @cite_22 , and @cite_19 show that, for multicast traffic, linear codes achieve maximum throughput, while coding and decoding can be done in polynomial time. @cite_23 show that random network coding can also achieve maximum network capacity. Network coding has been shown to improve throughput in a variety of networks: wireless @cite_14 , peer-to-peer content distribution @cite_2 , energy @cite_10 , distributed storage @cite_29 , and others.
@cite_14 @cite_22 @cite_10 @cite_29 @cite_19 @cite_27 @cite_23 @cite_2 @cite_13
2119407552 2048235391 2119772493 2152664953
We consider the problem of achieving capacity through network coding when some of the nodes act covertly as Byzantine adversaries. For several case-study networks, we investigate rates of reliable communication through network coding and upper bounds on capacity. We show that linear codes are inadequate in general, and a slight augmentation of the class of linear codes can increase throughput. Furthermore, we show that even this nonlinear augmentation may not be enough to achieve capacity. We introduce a new class of codes known as bounded-linear that make use of distributions defined over bounded sets of integers subject to linear constraints using real arithmetic. We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching 1 with the code length. We also demonstrate that random linear coding performs compression when necessary in a network, generalizing error exponents for linear Slepian-Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks With the constraints of network topologies and link capacities, achieving the optimal end-to-end throughput in data networks has been known as a fundamental but computationally hard problem. In this paper, we seek efficient solutions to the problem of achieving optimal throughput in data networks, with single or multiple unicast, multicast and broadcast sessions. Although previous approaches lead to solving NP-complete problems, we show the surprising result that, facilitated by the recent advances of network coding, computing the strategies to achieve the optimal end-to-end throughput can be performed in polynomial time. This result holds for one or more communication sessions, as well as in the overlay network model. Supported by empirical studies, we present the surprising observation that in most topologies, applying network coding may not improve the achievable optimal throughput; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality. Network coding shows that the data rate can be increased if information is allowed to be encoded in the network nodes. The recent work of S.-Y.R. (see IEEE Trans. Inform. Theory, vol.49, no.2, p.371-81, 2003) and R. Koetter and M. Medard (see Proc. INFOCOM, 2002) shows that linear network coding is sufficient for a single source multicast network. The restrictiveness of the use of linear code is still an unknown in the general multisource multicast network. We characterize the achievable information rate region for a single source node multi-source multicast network with two sinks. We further show that linear coding is sufficient for achieving the maximum network capacity.