We investigate the problem of optimal channel protection of multiple-description coded (MDC) multimedia contents at a wireless access point (WAP). For each MDC packet, the WAP has the option to protect and broadcast the packet using one of the available channel coders, or to drop the packet altogether. For a fixed FEC-based MDC, we show how this optimization can be approximated by a convex optimization problem with linear constraints, and thus, can be solved efficiently. We verify the validity of our results through ex- tensive simulations of a wireless image streaming application that employs multiple turbo channel coders, where we report gains of more than 2.50 dB PSNR in average reconstruction quality at receivers. We also devise an iterative algorithm for joint optimization of the channel code rate assignment and the design of the MDC. Our simulations show further gains of up to 5.40 dB in average PSNR when this joint optimization is employed.

We investigate the max-norm (L∞) properties of multiresolution scalar quantizers (MRSQ). The multiresolution requirement imposes nontrivial constraints on the maximum distortion at each level of the quantizer. To quantify these constraints, we define the overall multiresolutionL∞distortion of an MRSQ to be a weighted sum ofL∞distortions over all refinement levels of the MRSQ. We then seek MRSQ constructions that minimize this average-max distortion measure. An interesting relationship between this problem and the structure of Huffman code trees is established. Lower bounds for the average-max distortion are derived based on this relationship. The derivation of these lower bounds also lead to efficient dynamic programming heuristic solutions.

Given a fixed network of routers, a set of multicast sources and their corresponding receivers, we investigate the problem of constructing multicast sessions that maximize the multicast throughput of all sessions under fairness constraints. It is known that for problems with only one source node, heuristic algorithms based on packing maximum-rate Steiner trees may achieve throughput close to network capacity for some networks of interest. In almost all practical applications, however, multiple multicast sessions must be concurrently supported by the same network. We find that greedy strategies such as maximum-rate Steiner tree packing fail to perform well in dense problems, where the number of sources are large. We then propose a heuristic round-robin algorithm, called Cooperative Shortest Path Tree Packing Algorithm (CSPT), that performs uniformly well in the whole spectrum of problems from sparse to dense. Simulations on random networks show up to 5 times increase in throughput when compared to conventional methods in which there is only one tree per multicast session, and on average achieving 92% of the network capacity, when network coding is allowed. Finally, we show how CSPT can be implemented, with relative ease, on top of the current standard IP protocols.

This paper is an enquiry into the interaction between multiple description coding (MDC) and network routing. We are mainly concerned with rate-distortion optimized network flow of a multiple description (MD) source from multiple servers to multiple sinks. We aim at maximizing a collective metric of the quality of source reconstruction at all sinks, by optimally routing the MD source streams from the server nodes to the sinks. This problem turns out to be very different from conventional maximum network flow. The objective function involves not only the flow volume but also the diversity of the flow contents (i.e., distinction of descriptions), hence, the term rainbow network flow (RNF). For a general network topology, a general fidelity function, and an arbitrary distribution of MDC descriptions on the servers, we prove the RNF problem to be Max-SNP-hard. However, the problem becomes tractable in many practical scenarios, such as when MDC is balanced with descriptions of the same length and importance, when all source nodes have the complete set of MDC descriptions, and when the network topology is a tree or has only one sink. Polynomial-time RNF algorithms are developed for these cases.

Network information multicast has been considered extensively, either as a routing problem or more recently in the context of network coding. Most of the Internet bandwidth, however, is consumed by multimedia contents that are amenable to lossy reconstruction. In this paper, we investigate the following fundamental question: How does one communicate a media content from nodes (servers) that observe/supply the content to a set of sink nodes (clients) to realize the best possible reconstruction of the content in a rate-distortion sense? While this problem remains essentially open, this paper takes the first step by exploring the intricate entanglement of source coding and network communication, within an optimization framework. In particular, we investigate the joint optimization of network communication strategies (e.g., routing or network coding) and common source coding schemes (e.g., progressive coding or more general multiple description coding). We formulate several such problems for which we are able to develop efficient polynomial time solutions. In particular, we consider layered multicast of progressively encoded source code streams using network coding and optimal routing of balanced multiple description codes. Finally, the improvement in the overall quality of source reconstruction by using the proposed schemes is verified through simulations.

Operational rate-distortion (RD) functions of most natural images, when compressed with state-of-the-art wavelet coders, exhibit a power-law behavior D alpha R(-gamma) at moderately high rates, with gamma being a constant depending on the input image, deviating from the well-known exponential form of the RD function D alpha 2(-xiR) for bandlimited stationary processes. This paper explains this intriguing observation by investigating theoretical and operational RD behavior of natural images. We take as our source model the fractional Brownian motion (fBm), which is often used to model nonstationary behaviors in natural images. We first establish that the theoretical RD function of the fBm process (both in 1-D and 2-D) indeed follows a power law. Then we derive operational RD function of the fBm process when wavelet encoded based on water-filling principle. Interestingly, both the operational and theoretical RD functions behave as D alpha R(-gamma). For natural images, the values of gamma are found to be distributed around 1. These results lend an information theoretical support to the merit of multiresolution wavelet compression of self-similar processes and, in particular, natural images that can be modelled by such processes. They may also prove useful in predicting performance of RD optimized image coders.

We are interested in how to best communicate a real valued source to a number of destinations (sinks) over a network with capacity constraints in a collective fidelity metric over all the sinks, a problem which we call joint network-source coding. It is demonstrated that multiple description codes in conjunction with proper diversity routing provide a powerful solution to joint network-source coding. A systematic optimization approach is proposed. It consists of optimizing the network routing given a multiple description code and designing optimal multiple description code for the corresponding optimized routes.

Given some of the recent advances in distributed hash table (DHT) based peer-to-peer (P2P) systems we ask the following questions: are there applications where unstructured queries are still necessary (i.e., the underlying queries do not efficiently map onto any structured framework), and are there unstructured P2P systems that can deliver the high bandwidth and computing performance necessary to support such applications. Toward this end, we consider an image search application which supports queries based on image similarity metrics, such as color histogram intersection, and discuss why in this setting, standard DHT approaches are not directly applicable. We then study the feasibility of implementing such an image search system on two different unstructured P2P systems: power-law topology with percolation search, and an optimized super-node topology using structured broadcasts. We examine the average and maximum values for node bandwidth, storage and processing requirements in the percolation and super-node models, and show that current high-end computers and high-speed links have sufficient resources to enable deployments of large-scale complex image search systems

In packet switched networks receivers can get packets of a multiple description code (MDC) from different sources for enhanced QoS and robust transmission. The quality achieved by a decoder increases in the number of distinct rather than the total number of packets received. This property makes the problems of optimizing network flows and transmission strategies for MDC, called rainbow network problems, very different from those of conventional network flow and management. Two interesting problems: rainbow network flow and rainbow multicast, are formulated and treated. The rainbow network flow problem of maximizing the number of distinct packets received, constrained by edge capacities, is shown to be NP-hard in multisource-multisink setting. But it can be reduced to conventional maximum network flow problem in the case of single sink, hence becomes solvable in polynomial time. Rainbow multicast problem is about coordinating multiple servers for minimum expected distortion at one or a set of clients. Although being seemingly intractable in general, some variants of the problem have analytical solutions

We consider the problem of design and analysis of optimal L/sub /spl infin// (minmax) multiresolution scalar quantizers (MRSQ). The overall multiresolution L/sub /spl infin// distortion of an MRSQ is denned to be a weighted sum of L/sub /spl infin// distortions over all refinement levels of the MRSQ. The weight for a refinement level usually denotes the probability that the MRSQ will operate at that level (rate). An interesting relation of the problem to the design of optimal binary prefix codes under a code cell contiguity constraint is established: Lower bounds for the overall multiresolution L/sub /spl infin// distortion are derived based on this relation. Provably optimal as well as fast, near optimal algorithms are also developed for practically interesting scenarios. Furthermore, the performance penalty incurred by making a scalable quantizer embedded (progressively refinable) is analyzed. It is shown that constraining the quantizers to be embedded would on average increase the L/sub /spl infin// quantization error by at least 44%.

Self-similar stochastic processes are stochastic counterparts of deterministic fractals. Fractional Brownian motion (fBm) is a self-similar nonstationary Gaussian process originally proposed to model power-law behavior of power spectrum of long-range dependant (LRD) natural processes. Multiscale nature of wavelets make them natural candidates for analysis and synthesis of fractional Brownian motions. Despite wavelet compression being the method of choice for image compression, the performance of wavelet compression schemes are investigated for compressing fractional Brownian motions. Theoretical rate-distortion function of fBm is explicitly derived.

Many multimedia streaming applications have to buffer a number of different source streams for playback of a single multimedia composition. Multiple buffers (one for each stream) have to be deployed at the decoder to make continuous, almost real-time, playback of the multimedia content possible. We propose a novel implementation of two buffers in one array that efficiently reduces the overall memory dedicated to buffering by allowing for a common space where data for both buffers can be stored. An algorithm for finding optimal parameters of the shared buffer and calculating the reduction in the buffer size by buffer sharing is proposed. This involves finding level sets of solutions to some well studied 2D partial differential equations of mathematical physics with simple boundary conditions.

Consider the problem of broadcasting an i.i.d. source sequence X = {X/sub i/} /sub i=1//sup N/ (possibly N /spl rarr/ /spl infin/) to n listeners over a discrete broadcast channel, consisting of n channels with capacities C/sub 1/ = C/sub max/ /spl ges/ C/sub 2/ /spl ges/.../spl ges/ C/sub n/ = C/sub min/. Let the tuple D = (D/sub 1/, D/sub 2/,...,D/sub n/) represent the average distortion in reconstructing sources at the n listeners. The problem of characterizing all achievable tuples D is still open for a general case. For a fairly general class of discrete channels, we prove the achievability of the tuple n(/spl rho//sub 1/,/spl rho//sub 2/,...,/spl rho//sub n/) = (D/sub X/(/spl rho//sub 1/C/sub 1/ /spl zeta/), D/sub X/(/spl rho//sub 2/C/sub 2/ - /spl zeta/),...,D/sub X/(/spl rho//sub n/C/sub n/ - /spl zeta/)), provided that /spl lambda//sub i/ = (/spl rho//sub i/C/sub i/ - /spl rho//sub i/+/sub 1/C/sub i+1/)/C/sub i/ > 0, for 1 /spl les/ i /spl les/ n $1, /spl lambda//sub n/ = /spl rho//sub n/ and /spl Sigma//sub i=1//sup n-1/ /spl lambda//sub i/ /spl les/ 1, where D/sub X/ (R) is the distortion rate function of X. The penalty term /spl zeta/ = 1/2 for a general source with real alphabets and is /spl zeta/ = 0 if X is progressively refinable. The factor 00, we find examples of channels for which /sup 3/(2/3+/spl delta/,2/3+/spl delta/,2/3+ /spl delta/) is not achievable.

We introduce a scalable searching protocol for locating and retrieving content in random networks with power-law (PL) and heavy-tailed degree distributions. The proposed algorithm is capable of finding any content in the network with probability one in time O(logN), with a total traffic that provably scales sub-linearly with the network size, N. Unlike other proposed solutions, there is no need to assume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. The scaling behavior of the size of the giant connected component of a random graph with heavy tailed degree distributions under bond percolation is at the heart of our results. The percolation search algorithm can be directly applied to make unstructured peer-to-peer (P2P) networks, such as Gnutella, Limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and scale-free network structures), scalable. For example, simulations of the protocol on the limewire crawl number 5 network, consisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%.

In recent literature a powerful multiple description product coding scheme for protection of progressively encoded source streams has been devised that disperses information evenly between all description packets. Also, techniques were proposed to protect these packets equally by an optimal channel coder (found by exhaustive search). The contribution of this paper is to show that equal protection of all descriptions is suboptimal when the channel varies with time despite the fact that all descriptions have equal importance. We propose a theoretical framework for computing the globally optimal channel protection assignment for a given set of available channel coders under some idealized assumptions. For more practical scenarios we propose an optimized uneven packet protection scheme that outperforms equal protection schemes in terms of the expected distortion of received sources. Simulations of an image transmission system that resembles a 3G high bitrate link is provided where our unequal protection scheme improves the average PSNR of the received images by more than 1.3dB.