Efficient selective frame discard algorithms for stored video delivery across resource constrained networks

Zhi Li Zhang, Srihari Nelakuditi, Rahul Aggarwal, Rose P. Tsang

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


Video delivery from a server to a client across a network is an important component of many multimedia applications. While delivering a video stream across a resource constrained network, loss of frames may be unavoidable. Under such circumstances, it is desirable to find a server transmission schedule that can efficiently utilize the network resources while maximizing the perceived quality-of-service (QoS) at the client. To address this issue, in this paper we introduce the notion of selective frame discard at the server and formulate the optimal selective frame discard problem using a QoS-based cost function. Given network bandwidth and client buffer constraints, we develop an O(N log N) algorithm to find the minimum number of frames that must be discarded in order to meet these constraints. The correctness of the algorithm is also formally established. We present a dynamic programming based algorithm for solving the problem of optimal selective frame discard. Since the computational complexity of the optimal algorithm is prohibitively high in general, we also develop several efficient heuristic algorithms for selective frame discard. These algorithms are evaluated using JPEG and MPEG video traces.

Original languageEnglish (US)
Article number90226
Pages (from-to)255-273
Number of pages19
JournalReal-Time Imaging
Issue number3
StatePublished - 2001

Bibliographical note

Funding Information:
This work was supported in part by a University of Minnesota Graduate School Grant-in-Aid grant, NSF CAREER Award grant NCR-9734428, NSF grant ANIR-9903228, and by US Department of Energy grant DE-ACO4-94-AL85000. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or US Department of Energy. We are grateful for the generous support of these funding agencies. We would also like to thank the anonymous reviewers for their insightful comments and suggestions.


Dive into the research topics of 'Efficient selective frame discard algorithms for stored video delivery across resource constrained networks'. Together they form a unique fingerprint.

Cite this