Delivering presentations from multimedia servers

Most multimedia servers reported in the literature are designed to serve multiple and independent video/audio streams. We think that, in future, multimedia servers will also serve complete presentations. Multimedia presentations provide unique opportunities to develop algorithms for buffer management and admission control, as execution-time consumption requirements of presentations are known a priori. In this paper, we examine presentations in three different domains (heavyweight, middleweight, and lightweight) and provide buffer management and admission control algorithms for the three domains. We propose two improvements (flattening and dynamic-adjustments) on the schedules created for the heavyweight presentations. Results from a simulation environment are presented. Received June 9, 1998 / Accepted October 13, 1998     

An algebra for creating and querying multimedia presentations

Over the last few years, there has been a tremendous increase in the number of interactive multimedia presentations prepared by different individuals and organizations. In this paper, we present an algebra for creating and querying interactive multimedia presentation databases. This algebra operates on trees whose branches reflect different possible playouts of a set of presentations. The algebra not only extends all the classical relational operators to such databases, but also introduces a variety of novel operators for combining multiple presentations. As our algebra supports merging parts or all of existing presentations, this algebra can also be used as an authoring tool for creating multimedia presentations. We prove a host of equivalence results for queries in this algebra, which may be used to build query optimizers for interactive presentation databases.     

Retrieval in multimedia presentations

In this paper we discuss issues concerning the consistent retrieval of parts of multimedia presentations from multimedia repositories. We introduce a class of multimedia presentations made of independent and synchronized media and discuss retrieval requirements of presentation fragments. Then we discuss a retrieval model capable of reconstructing the fragments of a presentation from the atomic components returned by the execution of queries to multimedia presentation repositories. The retrieval model is based on an automaton that formally describes the presentation states entered by the events that trigger media playback. Retrieving a consistent fragment corresponds to building a new presentation with all the media related to the retrieved ones, with their original structural and synchronization relationships.     

Dynamic playout scheduling algorithms for continuous multimedia streams

In this paper, we investigate a playout scheduling framework for supporting the continuous and synchronized presentations of multimedia streams in a distributed multimedia presentation system. We assume a situation in which the server and network transmissions provide sufficient support for the delivery of media objects. In this context, major issues regarding the enforcement of the smooth presentation of multimedia streams at client sites must be addressed to deal with rate variance of stream presentations and delay variance of networks. We develop various playout-scheduling algorithms that are adaptable to quality-of-service parameters. The proposed algorithms permit the local adjustment of unsynchronized presentations by gradually accelerating or retarding presentation components, rather than abruptly skipping or pausing the presentation materials. A comprehensive experimental analysis of the proposed algorithms demonstrates that our algorithms can effectively avoid playout gaps (or hiccups) in the presentations. This scheduling framework can be readily used to support customized multimedia presentations.     

Presentations for databases in multimedia environments

The problem of presenting database query results has not been investigated sufficiently. This work proposes an approach to identify effective presentations for the results of database queries. This will be done by considering different kinds of information, such as user goals, the characteristics of the data to be presented, and the relationships among them. Our approach is based on the definition of composition operations which, on the basis of elementary presentation types, allow us to obtain designs of complex final presentations. Some effectiveness criteria are considered in order to identify those presentations which best match the user's goals and cognitive abilities. We consider multimedia environments at both the data and presentation level.     

Increasing multimedia system throughput with consumption-based buffer management

In a multimedia server, multiple media streams are generally serviced in a cyclic fashion. Due to non-uniform playback rates and asynchronous arrivals of queries, there tends to be spare disk bandwidth in each service cycle. In this paper, we study the issue of dynamically using spare disk bandwidth and buffer to maximize the system throughput of a multimedia server. We introduce the concept of minimizing buffer consumption as the criterion to select an appropriate media stream to utilize the spare system resources. Buffer consumption measures not only the amount of buffer but also the amount of time such buffer space is occupied (i.e., the space-time product). Different alternatives to utilizing spare disk bandwidth are examined, including different rate-adjustable retrievals of an already activated stream and prefetching the next waiting stream. For rate-adjustable retrievals, we study buffer consumption-based and remaining-time-based criteria for selecting an active stream to increase retrievals. Simulations are conducted to evaluate and compare different cases. The results show that (1) minimizing buffer consumption is the right criterion for maximizing the system throughput with spare disk bandwidth; (2) in general, prefetching a waiting stream incurs more buffer consumption, and thus is less effective than rate-adjustable retrieval of active streams in maximizing the system throughput; and (3) the advantage of rate-adjustable retrieval over prefetching is especially significant when service cycle time is small.     

Failure recovery algorithms for multimedia servers

In this paper, we present two novel disk failure recovery methods that utilize the inherent characteristics of video streams for efficient recovery. Whereas the first method exploits the inherent redundancy in video streams (rather than error-correcting codes) to approximately reconstruct data stored on failed disks, the second method exploits the sequentiality of video playback to reduce the overhead of online failure recovery in conventional RAID arrays. For the former approach, we present loss-resilient versions of JPEG and MPEG compression algorithms. We present an inherently redundant array of disks (IRAD) architecture that combines these loss-resilient compression algorithms with techniques for efficient placement of video streams on disk arrays to ensure that on-the-fly recovery does not impose any additional load on the array. Together, they enhance the scalability of multimedia servers by (1) integrating the recovery process with the decompression of video streams, and thereby distributing the reconstruction process across the clients; and (2) supporting graceful degradation in the quality of recovered images with increase in the number of disk failures. We present analytical and experimental results to show that both schemes significantly reduce the failure recovery overhead in a multimedia server.     

Design and evaluation of a multimedia storage server for mixed traffic

The relative simplicity of access to digital communications nowadays and the simultaneous increase in the available bandwidth are leading to the definition of new telematic services, mainly oriented towards multimedia applications and interactivity with the user. In the near future, a decisive role will be played in this scenario by the providers of interactive multimedia services of the on-demand type, which will guarantee the end user a high degree of flexibility, speed and efficiency. In this paper, some of the technical aspects regarding these service providers are dealt with, paying particular attention to the problems of storing information and managing service requests. More specifically, the paper presents and evaluates a new storage technique based on the use of disk array technology, which can manage both typical multimedia connections and traditional requests. The proposed architecture is based on the joint use of the partial dynamic declustering and the information dispersal algorithm, which are employed for the allocation and retrieval of the data stored on the disk array. We also define efficient strategies for request management in such a way as to meet the time constraints imposed by multimedia sessions and guarantee good response times for the rest of the traffic. The system proposed is then analyzed using a simulation approach.     

A buffer-inventory-based dynamic scheduling algorithm for multimedia-on-demand servers

We present a producer-consumer model of multimedia-on-demand (MOD) servers. The producer retrieves media data from a disk and places it into a set of buffers, while the consumer sends out the data in the buffers to the users. We develop for the producer a buffer-inventory-based dynamic scheduling (BIDS) algorithm that guarantees non-zero inventory and non-overflow of data in the buffers to meet the continuity requirement and no-loss of data for each media stream. The algorithm can deal with heterogeneous me dia streams as well as the transient circumstances upon service completions and arrivals of new requests. To smooth out the impact of bursty data of variable-bit-rate media streams and therefore increase the maximum admissible load of requests, we also introduce into the scheduling scheme a time-scale-dependent peak consumption rate and a virtual cycle time. Based on BIDS, an effective admission control mechanism can be easily established by checking two simple conditions respectively on the overall system load and buffer size. Our algorithm is very easy to implement. Experiments carried out with an actual disk system and real video stream data verify that it is more robust compared to static scheduling algorithms previously proposed in the literature, especially when handling variable-bit-rate media streams.     

Dynamic end-to-end QoS management middleware for distributed multimedia systems

In this paper, we present a separable, reusable middleware solution that provides coordinated, end-to-end QoS management over any type of service component, and can use existing (legacy) QoS management solutions (by using wrappers) in a distributed multimedia system. Our middleware solution incorporates strategic and tactical QoS managers, and supports protocols and messages between tactical managers and managed application components, and between QoS managers in the management hierarchy. Strategic QoS managers take a global view of QoS provided by a set of application components within the manager's policy domain. Tactical QoS managers provide local control over application components. We introduce the concept of QoS policy domains to scope the authority of a strategic QoS manager. We describe how the management hierarchy is dynamically configured and reconfigured based on runtime needs of the application.     

Spatio-temporal effects of multimedia objects storage and delivery for video-on-demand systems

As the number of video streams to be supported by a digital video delivery system (DVDS) increases, an improved understanding of the necessity for reliable and cost-efficient support for a considerable number of video streams (in the magnitude of tens of thousands), and the dependency largely on software capabilities emerges. Even in the presence of an optimal hardware configuration, or model, and associated costs, using software to exploit the underlying hardware capabilities is of paramount importance. Although a number of DVDSs have become operational, their ability to deliver the required services mainly depends on the small number of streams supported and the hardware trade-offs. It is imperative that current software developments account for the eventual scalability of the number of video streams without commensurate increase in hardware. In this paper, we present strategies for the management of video streams in order to maintain and satisfy their space and time requirements. We use a DVDS architectural model with functionally dichotomized nodes: a single-node partition is responsible for data retrieval, while the remaining partition of nodes accepts user requests, determines object locations, and routes requests through the network that connects both partitions. We present a detailed analysis of the issues related to queuing I/O requests and data buffering. The discussion includes the requirements for arranging and scheduling I/O requests and data buffers, with the objective of guaranteeing the required data availability rates for continuous media display.     

{\cal SMDP}: minimizing buffer requirements for continuous media servers

Excessive buffer requirement to handle continuous-media playbacks is an impediment to cost- effective provisioning for on-line video retrieval. Given the skewed distribution of video popularity, it is expected that often there are concurrent playbacks of the same video file within a short time interval. This creates an opportunity to batch multiple requests and to service them with a single stream from the disk without violating the on-demand constraint. However, there is a need to keep data in memory between successive uses to do this. This leads to a buffer space trade-off between servicing a request in memory mode vs. servicing it in disk-mode. In this work, we develop a novel algorithm to minimize the buffer requirement to support a set of concurrent playbacks. One of the beauties of the proposed scheme is that it enables the server to dynamically adapt to the changing workload while minimizing the total buffer space requirement. Our algorithm makes a significant contribution in decreasing the total buffer requirement, especially when the user access pattern is biased in favor of a small set of files. The idea of the proposed scheme is modeled in detail using an analytical formulation, and optimality of the algorithm is proved. An analytical framework is developed so that the proposed scheme can be used in combination with various existing disk-scheduling strategies. Our simulation results confirm that under certain circumstances, it is much more resource efficient to support some of the playbacks in memory mode and subsequently the proposed scheme enables the server to minimize the overall buffer space requirement.     

MING-I: a distributed interactive multimedia document development mechanism

The next generation of interactive multimedia documents can contain both static media, e.g., text, graph, image, and continuous media, e.g., audio and video, and can provide user interactions in distributed environments. However, the temporal information of multimedia documents cannot be described using traditional document structures, e.g., Open Document Architecture (ODA) and Standard Generalized Mark-up Language (SGML); the continuous transmission of media units also raises some new synchronization problems, which have not been met before, for processing user interactions. Thus, developing a distributed interactive multimedia document system should resolve the issues of document model, presentation control architecture, and control scheme. In this paper, we (i) propose a new multimedia document model that contains the logical structure, the layout structure, and the temporal structure to formally describe multimedia documents, and (ii) point out main interaction-based synchronization problems, and propose a control architecture and a token-based control scheme to solve these interaction-based synchronization problems. Based on the proposed document model, control architecture, and control scheme, a distributed interactive multimedia document development mechanism, which is called MING-I, is developed on SUN workstations.     

Conferencing and collaborative computing

As integrated services have become available to the desktop, users have embraced new modes of interaction, such as multimedia conferencing and collaborative computing. In this paper, we provide a survey of past and present research that has influenced this application area, and describe research directions for the future.     

Scheduling and data layout policies for a near-line multimedia storage architecture

Recent advances in computer technologies have made it feasible to provide multimedia services, such as news distribution and entertainment, via high-bandwidth networks. The storage and retrieval of large multimedia objects (e.g., video) becomes a major design issue of the multimedia information system. While most other works on multimedia storage servers assume an on-line disk storage system, we consider a two-tier storage architecture with a robotic tape library as the vast near-line storage and an on-line disk system as the front-line storage. Magnetic tapes are cheaper, more robust, and have a larger capacity; hence, they are more cost effective for large scale storage systems (e.g., video-on-demand (VOD) systems may store tens of thousands of videos). We study in detail the design issues of the tape subsystem and propose some novel tape-scheduling algorithms which give faster response and require less disk buffer space. We also study the disk-striping policy and the data layout on the tape cartridge in order to fully utilize the throughput of the robotic tape system and to minimize the on-line disk storage space.     

A proxy architecture for collaborative media streaming

Streaming media from the Internet is a successful application for end-users. With the upcoming success of mobile devices and home networking environments, cooperation among users will become more important in the future. To achieve such cooperation, explicit middleware standards have been defined. On the other hand, Internet conferencing applications do not handle collaborative streaming sessions with individual control for each user. We propose a new concept for cooperation exemplary for collaborative media streaming using IETF multimedia session control protocols together with a proxy architecture. This concept enables both synchronization among clients and flexible control to individual users.     

Adaptive multimedia synchronization in a teleconference system

In this paper, we present an adaptive buffering scheme for implementing intra-stream and inter-stream synchronization in real-time multimedia applications. The essence of the proposed scheme is to dynamically enforce equalized delays to incoming media streams, in order to piece-wise smooth the network delay variations and to synchronize the streams at the sink. An adaptive control mechanism based on an event-counting algorithm is employed to calibrate the PlayOut Clocks (POCs), which manages the presentations of multimedia data. The algorithm does not rely on globally synchronized clock and makes minimal assumption on underlying network delay distribution. Also, the user defined quality of service (QoS) specifications can be directly incorporated into the design parameters of the synchronization algorithm. The proposed synchronization scheme has been experimentally implemented in a teleconference system which consists of separately controllable audio, video, and data channels. The modular structure of the synchronization control provides the flexibility to maintain an arbitrary synchronization group in conjunction with a distributed conference management scheme. This paper also shows the experimental results of the test implementation and the suitability of the proposed scheme with respect to the multimedia traffic across an FDDI/Ethernet network.     

Context-aware Retrieval: Exploring a New Environment for Information Retrieval and Information Filtering

The opportunities for context-aware computing are fast expanding. Computing systems can be made aware of their environment by monitoring attributes such as their current location, the current time, the weather, or nearby equipment and users. Context-aware computing often involves retrieval of information: it introduces a new aspect to technologies for information delivery; currently these technologies are based mainly on contemporary approaches to information retrieval and information filtering. In this paper, we consider how the closely related, but distinct, topics of information retrieval and information filtering relate to context-aware retrieval. Our thesis is that context-aware retrieval is as yet a sparsely researched and sparsely understood area, and we aim in this paper to make a start towards remedying this.     

Advances in fractal compression for multimedia applications

Fractal image compression is a promising new technology but is not without problems. Most critically, fast encoding is required for it to find wide use in multimedia applications. This is now within reach: recent methods are five orders of magnitude faster than early attempts. Beginning with the basic ideas and problems, this paper explains how to accelerate fractal image compression.     

On periodic resource scheduling for continuous-media databases

The Enhanced Pay-Per-View (EPPV) model for providing continuous-media services associates with each continuous-media clip a display frequency that depends on the clip's popularity. The aim is to increase the number of clients that can be serviced concurrently beyond the capacity limitations of available resources, while guaranteeing a constraint on the response time. This is achieved by sharing periodic continuous-media streams among multiple clients. The EPPV model offers a number of advantages over other data-sharing schemes (e.g., batching), which make it more attractive to large-scale service providers. In this paper, we provide a comprehensive study of the resource-scheduling problems associated with supporting EPPV for continuous-media clips with (possibly) different display rates, frequencies, and lengths. Our main objective is to maximize the amount of disk bandwidth that is effectively scheduled under the given data layout and storage constraints. Our formulation gives rise to -hard combinatorial optimization problems that fall within the realm of hard real-time scheduling theory. Given the intractability of the problems, we propose novel heuristic solutions with polynomial-time complexity. We also present preliminary experimental results for the average case behavior of the proposed scheduling schemes and examine how they compare to each other under different workloads. A major contribution of our work is the introduction of a robust scheduling framework that, we believe, can provide solutions for a variety of realistic EPPV resource-scheduling scenarios, as well as any scheduling problem involving regular, periodic use of a shared resource. Based on this framework, we propose various interesting research directions for extending the results presented in this paper. Received June 9, 1998 / Accepted October 13, 1998