When streaming packetized media data over a lossy packet network, it is desirable to use transmission strategies that minimize the expected distortion subject to a constraint on the expected transmission rate. Because the computation of such optimal strategies is usually an intractable problem, fast heuristic techniques are often used. We first show that when the graph that gives the decoding dependencies between the data packets is reducible to a tree, optimal transmission strategies can be efficiently computed with dynamic programming algorithms. The proposed algorithms are much faster than other exact algorithms developed for arbitrary dependency graphs. They are slower than previous heuristic techniques but can provide much better solutions. We also show how to apply our algorithms to find high-quality approximate solutions when the dependency graph is not tree reducible. To validate our approach, we run simulations for MPEG1 and H.264 video data. We first consider a simulated packet erasure channel. Then we implement a real video streaming system and provide experimental results for an Internet connection.

Finding adequate packet transmission strategies for media streaming systems is a challenging algorithmic task. Recently, we proposed an efficient dynamic programming algorithm for streams in which the dependencies between packets, such as those prescribed between video frames by video codecs, can be modeled with a tree. In this contribution, we propose a heuristic algorithm for arbitrary dependency graphs. This algorithm consists of first transforming the dependency graph into a tree by adding dependencies, and then applying the dynamic programming algorithm on the tree thus obtained. The algorithm is both simple and efficient, as shown by experimental results on video sequences

This research is motivated by the needs of robust streaming of vector graphics contents over the Internet, wireless and other lossy networks. We present a multiple description coding (MDC) technique for error resilient compression and transmission of 2D vector graphics contents. An object is coded into two or more so-called co-descriptors, which are transmitted in separate data packets and generally via different network routes from a server to a client. Each co-descriptor can autonomously provide an approximation of the input object, and it can collaborate with other co-descriptors, if also available at the decoder, to refine the approximation

A list Viterbi algorithm (LVA) finds the n most likely paths in a trellis diagram of a convolutional code. One of the most efficient LVAs is the tree-trellis algorithm of Soong and Huang. We propose a new implementation of this algorithm. Instead of storing the candidate paths in a single list sorted according to the metrics of the paths, we show that it is computationally more efficient to use several unsorted lists, where all paths of the same list have the same metric. For an arbitrary integer bit metric, both the time and space complexity of our implementation are linear in n. Experimental results for a binary symmetric channel and an additive white Gaussian noise channel show that our implementation is much faster than all previous LVAs.

We consider the problem of rate-distortion optimized streaming of packetized multimedia data over a single quality-of-service network using feedback and retransmissions. For a single data unit, we prove that the problem is NP-hard and provide efficient branch and bound algorithms that are much faster than the previously best solution based on dynamic programming. For a group of interdependent data units, we show how to compute optimal solutions with branch and bound algorithms. The branch and bound algorithms for a group of data units are much slower than the current state of the art, a heuristic technique known as sensitivity adaptation. However, in many real-world situations, they provide a significantly better rate-distortion performance.

We propose a dynamic programming algorithm for finding optimal transmission policies for a single packet in rate-distortion optimized media streaming. The algorithm relies on an optimality assumption holding in particular when both the forward and round trip times have exponential distributions. In the other cases, we use the assumption as a heuristic principle. Simulations show that for realistic channel models, the algorithm provides optimal solutions and can be significantly faster than the previous fastest exact algorithm. The proposed algorithm can be used as a preprocessing step for streaming mutually dependent packets.

We consider the problem of rate-distortion optimal streaming of packetized media with sender-driven transmission over a single-QoS network using feedback and retransmissions. For a single data unit, we prove that the problem is NP-hard and provide efficient branch and bound algorithms that are in practice much faster than the best known solution. For a group of interdependent data units, we show how to compute optimal solutions with branch and bound algorithms. The branch and bound algorithms for a group of data units are slower than the current state of the art, the heuristic sensitivity adaptation algorithm, but provide a significantly better rate-distortion performance in many real-world situations.

A list Viterbi algorithm (LVA) finds the n best paths in a trellis. We propose a new implementation of the tree-trellis LVA. Instead of storing all paths in a single sorted list, we show that it is more efficient to use several lists, where all paths of the same list have the same metric. For an integer metric, both the time and space complexity of our implementation are linear in n. Experimental results show that our implementation is much faster than all previous LVAs. This allows us to consider a large number of paths in acceptable time, which significantly improves the performance of a popular progressive source-channel coding system that protects embedded data with a concatenation of an outer error detecting code and an inner error correcting convolutional code.