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.     

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.     

Transformation and exchange of multimedia objects in distributed multimedia systems

One of the challenges in the design of a distributed multimedia system is devising suitable specification models for various schemas in different levels of the system. Another important research issue is the integration and synchronization of heterogeneous multimedia objects. In this paper, we present our models for multimedia schemas and transformation algorithms. They transform high-level multimedia objects into schemas that can be used to support the presentation and communication of the multimedia objects. A key module in the system is the Object Exchange Manager (OEM). In this paper, we present the design and implementation of the OEM module, and discuss in detail the interaction between the OEM and other modules in a distributed multimedia system.     

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.     

A synchronization algorithm for distributed multimedia environments

Network synchronization plays a significant role in transmitting multimedia objects over computer networks. Even packets from a single channel must be synchronized due to the problems in a packet switching environment, such as network jitter, frequency, and time offsets. We present an algorithm that determines the set of packets generated periodically by various participants arriving at a node. The basic advantage of the proposed algorithm is that the receiver estimates the reference times (expected arrival times of the packets) and achieves synchronization, without knowledge of the packet delays. The accuracy is improved and the complexity is reduced by predicting the time/frequency offsets between the clocks at the source and the mixer. The error is calculated by the Chernoff bound, demonstrated by simulation, and shown to be acceptable in practical applications.     

Merging video streams in a multimedia storage server: complexity and heuristics

Due to recent advances in network, storage and data compression technologies, video-on-demand (VOD) service has become economically feasible. It is a challenging task to design a video storage server that can efficiently service a large number of concurrent requests on demand. One approach to accomplishing this task is to reduce the I/O demand to the VOD server through data- and resource-sharing techniques. One form of data sharing is the stream-merging approach proposed in [5]. In this paper, we formalize a static version of the stream-merging problem, derive an upper bound on the I/O demand of static stream merging, and propose efficient heuristic algorithms for both static and dynamic versions of the stream-merging problem.     

Analysis,management and indexing of distributed multimedia performances based on audience feedback

Interactive performance systems allow multiple, networked users to take part in a performance either as players or audience members and influence the performance's development in real time. Among the most prominent research issues concerning the development of these systems are the provision of effective interaction capabilities and adequate means of expression to the audience. This article describes a set of methods for the detection, analysis, synchronization and rendering of audience behavior in real-time during such an event. Furthermore, it describes ways in which audience feedback is utilized to dynamically index the contents of a performance so as to embed this event in large-scale multimedia services. All these methods have been applied in the creation of MISSION, a multi-user game involving both players and audience. This article presents and analyzes the design of the system and the results of user trials with it.     

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.     

Quality-of-service adaptation in distributed multimedia applications

High-speed networks and powerful end-systems enable new types of applications, such as video-on-demand and teleconferencing. Such applications are very demanding on quality of service (QoS) because of the isochronous nature of the media they are using. To support these applications, QoS guarantees are required. However, even with service guarantees, violations may occur because of resources shortage, e.g., network congestion. In this paper we propose new adaptation approaches, which allow the system to recover automatically, if possible, from QoS violations (1) by identifying a new configuration of system components that might support the initially agreed QoS and by performing a user-transparent transition from the original configuration to the new one, (2) by redistributing the levels of QoS that should be supported, in the future, by the components, or (3) by redistributing the levels of QoS that should be supported immediately to meet end-to-end requirements based on the principle that (local) QoS violation at one component may be recovered immediately by the other components participating in the support of the requested service. The proposed approaches, together with suitable negotiation mechanisms, allow us (1) to reduce the probability of QoS violations which may be noticed by the user, and thus, to increase the user confidence in the service provider, and (2) to improve the utilization of the system resources, and thus to increase the system availability.     

Packet audio playout delay adjustment: performance bounds and algorithms

In packet audio applications, packets are buffered at a receiving site and their playout delayed in order to compensate for variable network delays. In this paper, we consider the problem of adaptively adjusting the playout delay in order to keep this delay as small as possible, while at the same time avoiding excessive “loss” due to the arrival of packets at the receiver after their playout time has already passed. The contributions of this paper are twofold. First, given a trace of packet audio receptions at a receiver, we present efficient algorithms for computing a bound on the achievable performance of any playout delay adjustment algorithm. More precisely, we compute upper and lower bounds (which are shown to be tight for the range of loss and delay values of interest) on the optimum (minimum) average playout delay for a given number of packet losses (due to late arrivals) at the receiver for that trace. Second, we present a new adaptive delay adjustment algorithm that tracks the network delay of recently received packets and efficiently maintains delay percentile information. This information, together with a “delay spike” detection algorithm based on (but extending) our earlier work, is used to dynamically adjust talkspurt playout delay. We show that this algorithm outperforms existing delay adjustment algorithms over a number of measured audio delay traces and performs close to the theoretical optimum over a range of parameter values of interest.     

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.     

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.     

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.     

Synchronization support and group-membership services for reliable distributed multimedia applications

We describe a collection of algorithms designed to support reliable synchronization and group membership services for distributed multimedia applications. In particular, we consider those applications that require interactivity, isochronous rendering of multimedia data, and high reliability. We show that the algorithms we propose (i) provide reliable support for the synchronization of multimedia data streams, despite the occurrence of possible communication failures, (ii) maintain a consistent view of the relative group membership of all the nonfaulty application components, (iii) guarantee time-bounded delay of component failure detection and join, and (iv) meet effectively possible scalability requirements of the applications.     

Tertiary storage in multimedia systems: staging or direct access?

Multimedia applications that are required to manipulate large collections of objects are becoming increasingly common. Moreover, the size of multimedia objects, which are already huge, are getting even bigger as the resolution of output devices improve. As a result, many multimedia storage systems are not likely to be able to keep all of their objects disk-resident. Instead, a majority of the less popular objects have to be off-loaded to tertiary storage to keep costs down. The speed at which objects can be accessed from tertiary storage is thus an important consideration. In this paper, we propose an adaptive data retrieval algorithm that employs a combination of staging and direct access in servicing tertiary storage retrieval requests. At retrieval time, an object that resides in tertiary storage can either be staged to and then played back from disks, or the object can be accessed directly from the tertiary drives. We show that a simplistic policy that adheres strictly to staging or direct access does not exploit the full retrieval capacity of both the tertiary library and the secondary storage. To overcome the problem, we propose a data retrieval algorithm that dynamically chooses between staging and direct access, based on the relative load on the tertiary versus secondary devices. A series of simulation experiments confirms that the algorithm achieves good access times over a wide range of workloads and resource configurations. Moreover, the algorithm is very responsive to changing load conditions.     

Efficient admission control algorithms for multimedia servers

In this paper, we have proposed efficient admission control algorithms for multimedia storage servers that are providers of variable-bit-rate media streams. The proposed schemes are based on a slicing technique and use aggressive methods for admission control. We have developed two types of admission control schemes: Future-Max (FM) and Interval Estimation (IE). The FM algorithm uses the maximum bandwidth requirement of the future to estimate the bandwidth requirement. The IE algorithm defines a class of admission control schemes that use a combination of the maximum and average bandwidths within each interval to estimate the bandwidth requirement of the interval. The performance evaluations done through simulations show that the server utilization is improved by using the FM and IE algorithms. Furthermore, the quality of service is also improved by using the FM and IE algorithms. Several results depicting the trade-off between the implementation complexity, the desired accuracy, the number of accepted requests, and the quality of service are presented.     

A data model and a query languagefor multimedia documents databases

A multimedia application involves information that may be in a form of video, images, audio, text and graphics, need to be stored, retrieved and manipulated in large databases. In this paper, we propose an object-oriented database schema that supports multimedia documents and their temporal, spatial and logical structures. We present a document example and show how the schema can adress all the structures described. We also present a multimedia query specification language that can be used to describe a multimedia content portion to be retrieved from the database. The language provides means by which the user can specify the information on the media as well as the temoral and spatial relationships among these media.     

HeiRAT - Quality-of-service management for distributed multimedia systems

Multimedia systems must be able to support a certain quality of service (QoS) to satisfy the stringent real-time performance requirements of their applications. HeiRAT, the Heidelberg Resource Administration Technique, is a comprehensive QoS management system that was designed and implemented in connection with a distributed multimedia platform for networked PCs and workstations. HeiRAT includes techniques for QoS negotiation, QoS calculation, resource reservation, and resource scheduling for local and network resources.     

Synchronization of distributed multimedia systems with user interactions

Without user interactions, multimedia presentations are just fancy slide shows with sound and video supports. User interactions by themselves do not change the temporal relationships among multimedia objects, such as texts, graphics, images, audio, and video, but affect the playback schedules. In this paper, we propose a synchronization mechanism to guarantee the quality of multimedia presentation with user interactions. In our protocol, each presentation site requests media transmission from the required media servers at certain time intervals prior to the playback deadlines, where these time intervals are the response times to cover possible experienced end-to-end delays and packet losses, and waits for an initial setup time to ensure intermedia synchronization before starting the presentation. Users may interact with the presentation. This synchronization mechanism solves the problems incurred by user interactions by determining the new presentation scenario produced by the interactive operation, calculating the corresponding setup time, and then rendering the new playback and retrieval schedules.     

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.