Research

Raptor Network Coding for Video Streaming in Overlay Networks

The last decade has witnessed the rapid development of novel overlay network architectures such as peer-to-peer or wireless mesh networks that offer source and path diversity to data delivery applications. Network diversity permits to augment the quality of service for multimedia streaming applications, with increased throughput and improved resilience to failures. We propose a scheme that builds on Raptor codes and network coding in order to improve the system throughput while preserving the linear decoding times of Raptor codes. In addition, our scheme does not demand significant bandwidth to be spent for transmitting the network coding overheads. Our hybrid scheme is appropriate for real-time video streaming applications since it improves significantly the video quality and offers close to linear decoding times at the clients. We study the rate allocation problem for determining the optimal source rate, the design of the degree distribution function of the Raptor codes at the servers such that the received packets to follow linear decoding times and the case of multiple sources that simultaneously use the overlay network.

1. N. Thomos and P. Frossard, “Network Coding of Rateless Video in Streaming overlays“, IEEE Trans. on Circuits and Systems for Video Technology, Vol. 20, No. 12, pp. 1834-1847, Dec. 2010.

2. N. Thomos, and P. Frossard, “Degree Distribution Optimization in Raptor Network Coding,” in Proc. of Int. Symp. On Information Theory, ISIT’11, St. Petersburg, Russia, Aug. 2011.

3. J. Saltarin, N. Thomos, E. Bourstoulatze, and P. Frossard, “P2P Video Streaming with Inter-session Network Coding,” in Proc. of Workshop on Streaming and Media Communication, StreamComm’11 (in conjunction with ICME’11), Barcelona, Spain, July 2011.

4. N. Thomos and P. Frossard, “Collaborative Video Streaming with Raptor Network Coding“, in Proc. of 10th Int. Conf. on Multimedia & Expo, ICME’08, Hannover, Germany, June 2008.

5. N. Thomos and P. Frossard, “Raptor Network Video Coding“, in Proc. of 1st ACM Int. Workshop on Mobile video (in conjunction with ACM Multimedia’07), Augsburg, Germany, Sep. 2007.

(function(i,s,o,g,r,a,m){i[‘GoogleAnalyticsObject’]=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,’script’,’//www.google-analytics.com/analytics.js’,’ga’); ga(‘create’, ‘UA-42427834-1’, ‘epfl.ch’); ga(‘send’, ‘pageview’);

UEP Network Coding for Distributed Delivery of Prioritized Video

Overlay networks offer the possibility of employing basic processing operations at intermediate network nodes, in addition to providing increased path or source diversity. These important properties can contribute to improved delivery performance. For example, the nodes can perform simple coding operations on packets before transmission in order to increase the goodput. This concept is known as network coding and it has gone a long way from a purely analytical technique to an approach applicable to data dissemination in the Internet at present.  We address the problem of prioritized media streaming in overlay networks, where network coding operations are specifically designed to cope with media packets of unequal importance. We build on the results of randomized network coding (RNC)  for the construction of a distributed streaming solution that improves the robustness to erasures without the need for centralized control. We propose a receiver-driven prioritized network coding strategy where the receiving peers request packets from classes with varying importance. Packet classes can be constructed by considering the unequal contribution of the various video packets to the overall quality of the presentation or simply from the arrangement of data in scalable video streams. We examine the case both networks with helper nodes as well as networks where all the nodes are clients. Recently, we extended our framework to consider the case of free viewpoint applications, where images are captured by an array of cameras.

/* Style Definitions */ table.MsoNormalTable {mso-style-name:”Table Normal”; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:””; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:Cambria; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin;}

1. N. Thomos, J. Chakareski and P. Frossard, “Prioritized Distributed Video Delivery with Randomized Network Coding“, IEEE Trans. on Multimedia, Vol. 13, No. 4, pp. 776-787, Aug. 2011.

2. E. Kurdoglu, N. Thomos, and P. Frossard, “Scalable Video Dissemination with Prioritized Network Coding,” in Proc. of Workshop on Streaming and Media Communication, StreamComm’11 (in conjunction with ICME’11), Barcelona, Spain, July 2011.

3. N. Thomos, J. Chakareski and P. Frossard, “Randomized Network Coding for UEP Video Delivery in Overlay Networks“, in Proc. of 11th Int. Conf. on Multimedia & Expo, ICME’09, New York, NYC, USA, June 2009.

4. L. Toni, N. Thomos, and P. Frossard, “Interactive Free Viewpoint Video Streaming Using Prioritized Network Coding,” in Proc. of IEEE Multimedia Signal Processing Conference, MMSP’13, Pula, Italy, Oct. 2013.

Selective Placement of Network Coding Nodes in Streaming Overlays

Network coding systems still face important issues in practical systems due to the decoding delays imposed by successive network coding operations. This delay as well as the computational overhead in the system grow with the number of network coding nodes. It becomes therefore important to select efficiently the subset of nodes that perform network coding in order to control delay and complexity and still exploit efficiently the diversity in the network. We discuss solutions for the selective placement of a few network coding nodes in order to reduce the delay for video delivery. We propose semi-distributed and centralized algorithms that iteratively choose the store and forward nodes to be turned into network coding nodes for improving the system performance until the predefined number of network coding nodes has been reached. In addition, we pose the problem from a game theoretic perspective to provide a fully distributed algorithm.

/* Style Definitions */ table.MsoNormalTable {mso-style-name:”Table Normal”; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:””; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:Cambria; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin;}

/* Style Definitions */ table.MsoNormalTable {mso-style-name:”Table Normal”; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:””; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:Cambria; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin;}

1. N. Cleju, N. Thomos and P. Frossard, ” Selection of Network Coding Nodes for Minimal Playback Delay in Streaming Overlays“, IEEE Trans. on Multimedia, Vol. 13, No. 5, pp. 1103-1115, Nov. 2011.

2. N. Cleju, N. Thomos and P. Frossard, “Network Coding Node Placement for Delay Minimization in Streaming Overlays“, in Proc. of Int. Conf. on Communications, ICC’10, Cape Town, South Africa, May 2010.

3. N. Thomos, H. Park, E. Kurdoglu, and P. Frossard, “NC Node Selection Game in Collaborative Streaming Systems,” in Proc. of Int. Conf.  on Acoustics, Speech, and Signal Processing, ICASSP’10, Dallas, Texas, USA, Mar. 2010.

Approximate Decoding of Network Coded Correlated Sources

Most of the network coding research so far has focused either on theoretical aspects of network coding such as achievable capacity and coding gain, or on its practical aspects such as robustness and increased throughput when the number of innovative packets is sufficient for perfect decoding. However, it generally does not consider the problematic cases where the clients receive an insufficient number of innovative packets for perfect decoding due to losses or timing constraints for example. Motivated by this important problem, we study the approximate reconstruction of network coded correlated sources. To this end, we propose the use of similarity index in order to set the most similar data equal and permit approximate source reconstruction with gaussian elimination. Besides that, we model the source dependencies by means of a factor graph and employ a pairwise source relationship model. We then propose an iterative decoding algorithm based on belief propagation that efficiently exploits the data correlation and provides approximate reconstruction of the sources.

/* Style Definitions */ table.MsoNormalTable {mso-style-name:”Table Normal”; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:””; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:Cambria; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin;}

1. H. Park, N. Thomos, and P. Frossard, “Approximate Decoding Approaches for Network Coded Correlated Data“, Elsevier Signal Processing, Vol. 93, No. 1, pp. 109-123, Jan. 2013.

2. E. Bourtsoulatze, N. Thomos, and P. Frossard, “Correlated-aware Reconstruction of Network Coded Sources,” in Proc. of Int. Symp. on Network Coding, NETCOD’12, Boston, MA, USA, June 2012.

3. H. Park, N. Thomos, and P. Frossard, “Transmission of Correlated Information Sources with Network Coding,” in Proc. of European Signal Processing Conference, EUSIPCO’10, Aalborg, Denmark, Aug. 2010.

Decoding Delay Minimization in Inter-session Network Coding

In generic communication scenarios, multiple sources may attempt to simultaneously use the same overlay network. Time sharing or optimal bandwidth allocation of the overlapping paths can be considered in order to make effective use of shared resources. However, these techniques cannot be easily deployed and are not effective in large networks. Alternatively, data from different sources can be combined in network nodes with so-called inter-session network coding algorithms. We study the delay minimization problem of an overlay network where nodes employ inter-session network coding. Delay minimization over the clients population is critical for delay sensitive applications such as video streaming. We provide a generic and constructive framework for the problem of inter-session network coding in wireline networks assuming centralized control. Then, we examine distributed solutions. To this aim, a rate allocation problem is solved by every peer, which seeks the rates that minimize the average decoding delay for its children and for itself. To solve this non-convex optimization problem, we introduce the concept of equivalent packet flows, which permits to estimate the expected number of packets that every peer needs to collect for decoding. We then decompose our original rate allocation problem into a set of convex subproblems, which are eventually combined to obtain an approximate solution to the delay minimization problem.

/* Style Definitions */ table.MsoNormalTable {mso-style-name:”Table Normal”; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:””; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:Cambria; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin;}

1. E. Bourtsoulatze, N. Thomos, and P. Frossard, “Distributed Rate Allocation in Inter-Session Network Coding,” available at http://arxiv.org/abs/1212.5032, Dec. 2012.

2. E. Bourtsoulatze, N. Thomos, and P. Frossard, “Decoding Delay Minimization in Inter-Session Network Coding,” available at http://arxiv.org/abs/1211.0951, Nov. 2012.

3. E. Bourtsoulatze, N. Thomos, and P. Frossard, “Distributed Rate Allocation With Intersession Network Coding,” in Proc. of Int. Packet Video Workshop, PV’12, May 2012.

Toward one Symbol Network Coding Vectors

Randomized network coding (RNC) is pretty simple and does not require coordination between network nodes, which has made it popular in practical systems. It however requires each packet to be augmented with a network coding header that contains information about the coding operations in the network. In order to keep the size of the network coding header reasonable, the network coding operations are limited to groups of packets sharing similar decoding deadlines. These groups of packets are known as generations. To further reduce the network coding overhead, we propose a design that shortens the employed network coding vectors of RNC schemes by imposing a specific design of the generator matrices. Our work is influenced by Rateless codes  where a seed of a pseudo-random generator is used to determine which source symbols have been combined for the generation of a rateless encoded symbol.

1. N. Thomos and P. Frossard, “Toward one Symbol Network Coding Vectors“, IEEE Communications Letters, Vol. 16, No. 11, pp. 1860-1863, Nov. 2012.