Design and performance analysis of multimedia document retrieval strategies for networked Video-on-Reservation systems

Abstract

Video-on-Reservation (VOR) systems serve as an attractive service providing scheme for multimedia network based services. As opposed to on-demand systems, in VOR, requests arrive in advance to their viewing times so that the network resources can be better utilized by carefully scheduling the resources. In this paper, we address the problem of optimizing the per user service cost and maximizing the number of requests that can be served by VOR systems. In order to provide a guaranteed QoS, generation of multicast trees with end-to-end delay constraints is recommended to minimize the costs. Since such an issue has been proved to be NP-complete, we propose two efficient and practically realizable heuristic algorithms, referred to as Source-Based Stream Scheduling (SBS) algorithm and Destination-Based Stream Scheduling (DBS) algorithm to solve the problem in polynomial time. Both SBS and DBS algorithms judiciously combine the concept of multicast routing and network caching, so that the copies of Multimedia Documents (MMDs) can be dynamically cached in the network. To analyze the trade-off between caching cost and transmission cost, we present a mathematical model and show that service cost can be minimized by adjusting offset time according to the network characteristics. When network resources (cache space and link bandwidth) are constraints, acceptance ratio can be improved significantly by combining video partitioning with SBS or DBS. We analyze and quantify the performance under several influencing parameters such as link availability, cache capacity and MMD availability. Our simulation results conclusively show that all the proposed algorithms can reduce the service cost, balance the network load and achieve a high acceptance ratio. © 2005 Elsevier B.V. All rights reserved.