Distributed Scheduling for Low-delay and Loss-Resilient Media Streaming with Network Coding

This thesis is focused on media streaming in cooperative networks with Network Coding. Network Coding has attracted a lot of interest recently due to its potential to maximize the network throughput in multicast communications. In a typical media streaming network using Network Coding, the source peer divides the media content into independently decodable chunks of data called generations. A generation may correspond to some frames or group of pictures in the media sequence ans is associated to a playback deadline. The source further divides each generation into $k$ symbols of the same size and transmits random linear combinations thereof to the network nodes. The network nodes transmit random linear combinations of the received packets and, once a node has collected enough linearly independent packets, it solves the corresponding system of equations and recovers the message. In general for a node to decode a generation, it is usually necessary to receive $k' > k$ packets that leads to an \emph{overhead}overhead of $\frac{k'}{k}$. Studies have shown that in order to explore the advantages of Network Coding, a random-push mechanism is beneficial with a random network topology. The random-push mechanism is explained as follows. Whenever a transmission opportunity arises for a network node, the node transmits a linear combination of a random subset of the received packets to a randomly drawn node in the network, where the network nodes are arranged in an unstructured overlay of peer nodes. %Despite its simplicity, the random-push scheme has demonstrated to be effective to reduce the initial buffering time and increase the useful network throughput. Moreover, arranging the peer nodes in a randomly connected overlay drastically reduces the need of coordination among the peers and increases the robustness against peer churning. Although Network Coding has shown to provide several benefits for media streaming in cooperative networks, the coding operations at the network nodes may introduce a delay that is detrimental for low-delay communications. In particular, in such media streaming systems the recipient nodes usually store some generations in their buffer before playback. Using low-delay communication means to reduce the buffering time of the nodes, which consequently requires a reduction in the value of $k$. On the other hand reducing $k$, leads to an increased overhead $\frac{k'}{k}$, thus requiring more bandwidth to decode the generations. Moreover, since each generation is associated to a playback deadline, the performance of such systems is also affected by the packet scheduling mechanism used to disseminate the media contents. In general the packet scheduling mechanism selects and transmits packets that belong to a particular generation to selected recipient nodes. The thesis first covers a feasibility evaluation of Network Coding for low-delay streaming towards video-conferencing applications using a random-push scheduling mechanism. The evaluation study consist of a number of experiments that have been performed using a P2P streaming protocol over a testbed and on a setup of real Internet nodes (PlanetLab network). The results of the study are reported in terms of media quality achieved by the recipient node in a variety of network configurations and parameters such as network sizes, buffering times and packet loss rates. Network Coding has also been opted with media compression techniques that provide graceful quality degradation in case of packet losses or inadequate bandwidth availability. Such compression techniques usually fragment a single high-quality media-stream to n substreams in order to cope with with the fluttering of the bandwidth available in the network. Typically the susbtreams are formed by arranging the media content in classes of different importance having unequal error protection (such as H.264/Scalable Video Coding), or in classes of equal importance having equal error protection (such as Multiple Description Coding). With the reception of each additional susbtream the quality of the media stream increases gracefully. In a media streaming context, such techniques help to guarantee that all the nodes are able to receive at least a lower quality version of the media stream when the bandwidth available in the network is scarce. This, however, requires the development of an efficient scheduling mechanism that is effective in providing a graceful quality degradation by using the compression techniques. Since in this case the packet scheduling mechanism must not only select the recipient node and the packets belonging to a specific generation but also the susbtream to which a generation is associated. This thesis later focuses on packet scheduling policies for media streaming with Network Coding that can improve the performance of the system in terms of media quality but with lower bandwidth requirements than the random-push scheduling mechanism. In particular, a mathematical optimization model for the packet scheduling policy is proposed that takes into account the decoding status of the nodes in the network and the heterogeneous network conditions. The packet scheduling optimization framework targets media content dissemination based on Network Coding using single stream media and also layered stream media such as H.264/SVC, and MDC. In order to work out the optimization problem, two algorithms have been proposed that solve the problem in linear time. The proposed algorithms have been implemented in a local testbed and in a real P2P streaming application. Finally the thesis evaluates the performance of the proposed algorithms and compares it with the performance of a reference random-push scheduling mechanism. The evaluation study consists of extensive experiments performed in a simulation, a real P2P streaming application and on the PlanetLab network using a variety of network configurations and different parameters.