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

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, 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. Since the computational complexity of the optimal algorithm for solving the optimal selective frame discard problem is prohibitively high in general, we also develop several efficient heuristic algorithms for selective frame discard. These algorithms are evaluated using JPEG video traces.