On scheduling atomic and composite continuous media objects

In multiuser multimedia information systems (e.g., movie-on-demand, digital-editing), scheduling the retrievals of continuous media objects becomes a challenging task. This is because of both intra and inter lobject time dependencies. Intraobject time dependency refers to the real-time display requirement of a continuous media object. Interobject time dependency is the temporal relationships defined among multiple continuous media objects. In order to compose tailored multimedia presentations, a user might define complex time dependencies among multiple continuous media objects with various lengths and display bandwidths. Scheduling the retrieval tasks corresponding to the components of such a presentation in order to respect both inter and intra task time dependencies is the focus of this study. To tackle this task scheduling problem (CRS), we start with a simpler scheduling problem (ARS) where there is no inter task time dependency (e.g., movie-on-demand). Next, we investigate an augmented version of ARS (termed ARS⁺) where requests reserve displays in advance (e.g., reservation-based movie-on-demand). Finally, we extend our techniques proposed for ARS and ARS⁺ to address the CRS problem. We also provide formal definition of these scheduling problems and proof of their NP-hardness     

Design of Multi-User Editing Servers for Continuous Media

Based on a fifteen month investigation of a post production facilities for both the entertainment industry and broadcasters, we identified a number of challenges with the design and implementation of a server in support of multiple editing stations. These include, how to: share the same content among multiple editors, support continuous display of the edited content for each editor, support complex editing operations, compute the set of changes (deltas) proposed by an editor, compare the deltas proposed by multiple editors, etc. It is beyond the focus of this paper to report on each challenge and its related solutions. Instead, we focus on one challenge, namely how to support continuous display of the edited content for each editors, and techniques for physical organization of data to address this challenge.     

Disk scheduling in video editing systems

Modern video servers support both video-on-demand and nonlinear editing applications. Video-on-demand servers enable the user to view video clips or movies from a video database, while nonlinear editing systems enable the user to manipulate the content of the video database. Applications such as video and news editing systems require that the underlying storage server be able to concurrently record live broadcast information, modify prerecorded data, and broadcast an authored presentation. A multimedia storage server that efficiently supports such a diverse group of activities constitutes the focus of this study. A novel real-time disk scheduling algorithm is presented that treats both read and write requests in a homogeneous manner in order to ensure that their deadlines are met. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines; otherwise, they are considered lost. Since the data to be written into disk is stored in main memory buffers, write requests can be postponed until critical read requests are processed. However, write requests still have to be processed within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory write buffers. The new algorithm schedules both read and write requests appropriately, to minimize the amount of disk reads that do not meet their presentation deadlines, and to avoid indefinite postponement and large buffer sizes in the case of disk writes. Simulation results demonstrate that the proposed algorithm offers low violations of read deadlines, reduces waiting time for lower priority disk requests, and improves the throughput of the storage server by enhancing the utilization of available disk bandwidth     

Controlled Buffer Sharing in Continuous Media Servers

Continuous media servers manage delay sensitive data such as audio and video clips. Once a server initiates the display of a clip on behalf of a client, it must deliver the data to the client in a manner that prevents data starvation. Otherwise, its display may suffer from disruptions and delays, termed hiccups. A hiccup-free display is important to a number of applications such as video-on-demand for entertainment, distance learning, news dissemination, etc. Buffer sharing enables a server to trade memory for disk bandwidth to service multiple clients by sharing data in memory, using a single disk stream. However, an uncontrolled buffer sharing scheme may reduce system performance.This paper presents Controlled Buffer Sharing (CBS) as a novel framework that facilitates sharing and supports both a hiccup-free display and VCR operations. It includes a configuration planner and a buffer pool management technique (applied at run time). CBS trades memory for disk bandwidth in order to meet the performance objectives of an application and minimize cost per stream. It uses bridging and merges two displays referencing the same clip when they are d _t blocks apart. One insight of this framework is that d _t is determined by market forces (cost of memory and disk bandwidth) and is independent of a clip's frequency of access. We use both analytical and simulation models to quantify the characteristics of CBS.     

Continuous display of presentations sharing clips

Databases were introduced to remove redundancy from conventional file systems and encouragesharing, which resulted in update anomalies when information was modified. With presentations (movies) sharing clips (sequence of frames), continuous display becomes challenging as well. Continuous display requires the system to retrieve the information with no disruptions or delays (hiccups) once a display is initiated. To ensure a continuous display using a multi-disk hardware platform, a video object is striped into subobjects. The system enforces a regular schedule on retrieval of each subobject by controlling the placement of the subobjects across the disks. Now if different presentations share subobjects, each presentation will enforce its own restrictions on the placement of the data, resulting in an irregular schedule. We investigate approaches to render a schedule regular for two alternative display paradigms: Demand and Data driven.     

An experimental object-based sharing system for networked databases

An approach and mechanism for the transparent sharing of objects in an environment of interconnected (networked), autonomous database systems is presented. An experimental prototype system has been designed and implemented, and an analysis of its performance conducted. Previous approaches to sharing in this environment typically rely on the use of a global, integrated conceptual database schema; users and applications must pose queries at this new level of abstraction to access remote information. By contrast, our approach provides a mechanism that allows users to import remote objects directly into their local database transparently; access to remote objects is virtually the same as access to local objects. The experimental prototype system that has been designed and implemented is based on the Iris and Omega object-based database management systems; this system supports the sharing of data and meta-data objects (information units) as well as units of behavior. The results of experiments conducted to evaluate the performance of our mechanism demonstrate the feasibility of database transparent object sharing in a federated environment, and provide insight into the performance overhead and tradeoffs involved. Edited by Georges Gardarin. Received October 29, 1992 / Revised May 4, 1994 / Accepted March 1, 1995     

Continuous retrieval of multimedia data using parallelism

Most implementations of workstation-based multimedia information systems cannot support a continuous display of high resolution audio and video data and suffer from frequent disruptions and delays termed hiccups. This is due to the low I/O bandwidth of the current disk technology, the high bandwidth requirement of multimedia objects, and the large size of these objects, which requires them to be almost always disk resident. A parallel multimedia information system and the key technical ideas that enable it to support a real-time display of multimedia objects are described. In this system, a multimedia object across several disk drives is declustered, enabling the system to utilize the aggregate bandwidth of multiple disks to retrieve an object in real-time. Then, the workload of an application is distributed evenly across the disk drives to maximize the processing capability of the system. To support simultaneous display of several multimedia objects for different users, two alternative approaches are described. The first approach multitasks a disk drive among several requests while the second replicates the data and dedicates resources to each individual request. The trade-offs associated with each approach are investigated using a simulation model     

Static Replication Strategies for Content Availability in Vehicular Ad-hoc Networks

This study investigates replication strategies for reducing latency to desired content in a vehicular peer-to-peer network. We provide a general constrained optimization formulation for efficient replication and study it via analysis and simulations employing a discrete random walk mobility model for the vehicles. Our solution space comprises of a family of popularity based replication schemes each characterized by an exponent n. We find that the optimal replication exponent depends significantly on factors such as the total system storage, data item size, and vehicle trip duration. With small data items and long client trip durations, n ∼ 0.5 i.e., a square-root replication scheme provides the lowest aggregate latency across all data item requests. However, for short trip durations, n moves toward 1, making a linear replication scheme more favorable. For larger data items and long client trip durations, we find that the optimal replication exponent is below 0.5. Finally, for these larger data items, if the client trip duration is short, the optimal replication exponent is found to be a function of the total storage in the system. Subsequently, the above observations are validated with two real data sets: one based on a city map with freeway traffic information and the other employing encounter traces from a bus network.     

Placement of continuous media in wireless peer-to-peer networks

This paper investigates a novel streaming architecture consisting of home-to-home online (H2O) devices that collaborate with one another to provide on-demand access to large repositories of continuous media such as audio and video clips. An H2O device is configured with a high bandwidth wireless communication component, a powerful processor, and gigabytes of storage. A key challenge of this environment is how to place data across H2O devices in order to enhance startup latency, defined as the delay observed from when a user requests a clip, to the onset of its display. Our primary contribution is a novel replication technique that enhances startup latency, while minimizing the total storage space required from an environment consisting of N H2O devices. This technique is based on the following intuition: The first few blocks of a clip are required more urgently than its last few blocks, and should be replicated more frequently in order to minimize startup latency. We develop analytical models to quantify the number of replicas required for each block. In addition, we describe two alternative distributed implementation of our replication strategy. When compared with full replication, our technique provides on average greater than 97% (i.e., several orders of magnitude) savings in storage space, while ensuring zero startup latency and a hiccup-free reception.