Complexity-adaptive random network coding for peer-to-peer video streaming

We present a novel architecture for complexity-adaptive Random Network Coding (RNC) and its application to Peer-to-Peer (P2P) video streaming. Network coding enables the design of simple and effective P2P video distribution systems, however it relies on computationally intensive packet coding operations that may exceed the computational capabilities of power constrained devices. It is hence desirable that the complexity of network coding can be adjusted at every node according to its computational capabilities, so that different classes of nodes can coexist in the network. To this end, we model the computational complexity of network coding as the sum of a packet decoding cost, which is centrally minimized at the encoder, and a packet recoding cost, which is locally controlled by each node. Efficient network coding is achieved exploiting the packet decoding process as a packet pre-recoding stage, hence increasing the chance that transmitted packets are innovative without increasing the recoding cost. Experiments in a P2P video streaming framework show that the proposed design enables the nodes of the network to operate at a wide range of computational complexity levels, while a higher number of low complexity nodes are able to join the network and experience high-quality video.