Network coding permits to deploy distributed packet delivery algorithms that locally adapt to the network availability in media streaming applications. However, it may also increase delay and computational complexity if it is not implemented efficiently. We address here the effective placement of a limited number of nodes that implement randomized network coding in overlay networks, so that the goodput is kept high while the delay for decoding stays small in streaming applications. We first estimate the decoding delay at each client, which depends on the innovative rate in the network. This estimation permits to identify the nodes that have to perform coding in order to reduce the decoding delay. We then propose two iterative algorithms for selecting the nodes that should perform network coding. The first algorithm relies on the knowledge of the full network statistics. The second algorithm uses only local network statistics at each node. Simulation results show that large performance gains can be achieved with the selection of only a few network coding nodes. Moreover, the second algorithm performs very closely to the central estimation strategy, which demonstrates that the network coding nodes can be selected efficiently with help of a distributed innovative flow rate estimation solution. Our solution provides large gains in terms of throughput, delay, and video quality in realistic overlay networks when compared to methods that employ traditional streaming strategies as well as random network coding nodes selection algorithms.
While the previous work mostly consider that the network is fully known at a central node, a decentralized algorithm for minimizing the number of network coding packets flowing in a network has been presented in @cite_11 . It also addresses the design capacity approaching network codes that minimize the set of network coding nodes. However, this algorithm does not provide any guarantee that the minimum set of network coding nodes can always be determined. While @cite_11 consider capacity approaching codes without delay constraints, we rather use well performing network codes and consider the available resources in the network in order to select a set of network coding nodes, such that the overall delay is kept small in multimedia applications. The choice of randomized network codes is mostly geared towards the implementation of practical distributed systems where large benefits are expected by the proper choice of a limited number of network coding nodes.
@cite_11
1997825969
We give an information flow interpretation for multicasting using network coding. This generalizes the fluid model used to represent flows to a single receiver. Using the generalized model, we present a decentralized algorithm to minimize the number of packets that undergo network coding. We also propose a decentralized algorithm to construct capacity achieving multicast codes when the processing at some nodes is restricted to routing. The proposed algorithms can be coupled with existing decentralized schemes to achieve minimum cost multicast