In network multimedia applications, such as multiparty teleconferencing, users often need to send the same information to several other users. To manage such one-to- many or many-to-many communication efficiently in wide-area internetworks, it is imperative to support and perform multicast routing. Multicast routing sends a single copy of a message from a source to multiple receivers over a communication link that is shared by the paths to the receivers. Loop-freedom is a specially important consideration in multicasting. Because applications using multicasting tend to be multimedia and bandwidth intensive, and loops in multicast routing duplicates looping packets. We present a new multicast routing protocol, called multicast internet protocol (MIP), which offers a simple and flexible approach to constructing both group-shared and shortest-paths multicast trees. MIP can be sender-initiated or receiver-initiated or both; therefore, it can be tailored to the particular nature of the an application's group dynamics and size. MIP is independent of the underlying unicast routing algorithms used. MIP is robust and adapts under dynamic network conditions to maintain loop-free multicast routing. Under stable network conditions, MIP has no maintenance or control message overhead.

This paper proposes a new ATM multicast scheme within the framework of an Active Multicast Service Architecture (AMSA) that supports user customization of multicast service. The customization is achieved by injecting and invoking user specific programs to shared network resources such as routers and switches. The multicast scheme also allows dynamic joining and/or leaving of members of different capabilities and quality of service requirements. A prototype of the multicast scheme was developed to verify the major functions of the AMSA and to demonstrate the feasibility of customizing network services within the active service architectural framework. The prototype supports QOS negotiation, non-uniform links QOS, resource reservation and filter program injection. The development platform sued consists of virtual ATM switches inter- connected via a real FORE ATM switch. The data links between these virtual switches are AAL-5 virtual circuits that enable actual QOS reservation. The signaling of the virtual switches is implemented via CORBA links connecting the CORBA daemons residing in the virtual switches. Experimental results show that the prototype of ATM multicast scheme is efficient and flexible in satisfying the requirements of heterogeneous users.

Many of multimedia applications in distributed systems should transmit continuous audio/video across networks when clients request. Typically, messages for continuous media in packet-switched networks are split into periodic, different sized packets with deadlines. Since clients request different types services, traffic streams are heterogeneous. Furthermore, since the continuity of continuous media should be preserved, non-preemptive scheduling is preferred in multimedia communications. In this paper, we present a new non-preemptive scheduling algorithm which guarantees the timely delivery of more sets of messages for continuous media on a communication link connected to packet-switched networks. It schedules messages by using a heuristic based on the earliest deadline first (EDF) policy. It can always find a feasible schedule for messages which are schedulable by the EDF algorithm. We also present admission control given as sufficient conditions for a set of messages to be schedulable by our scheduling algorithm for controlling the traffic load on a link. If a new request and the previous messages satisfy these conditions, it accepts the new request. The accepted message transmission is done like the circuit-switched transmission non-preemptively. Finally, we show the improvements in performance of our scheduling algorithm by simulation results.

The Group Allocation Multiple Access (GAMA) protocol for scheduling real-time and datagram traffic in a single- channel, single-hop, packet-radio network is specified and analyzed. By maintaining a dynamically-sized cycle that changes in length depending on the amount of network traffic, GAMA is able to provide bandwidth guarantees to the members of its 'transmission group', member stations are able to transmit real-time data at a specified rate. Each cycle contains a contention period and a group-transmission period; a station with data to send competes for the right to be added to the transmission group by successfully completing an RTS/CTS message exchange during the contention period.Once a station is a member of the transmission group, it is able to transmit a collision-free data packet during each cycle. As long as a station has data to send, it maintains its position in the group. This can be viewed as either allowing stations to 'share the floor' in an organized manner, or as establishing frames that are not synchronized on a slot-basis and vary their length dynamically based on demand. The throughput and average delay of GAMA are presented and analyzed.

Messages in multimedia systems possess distinct characteristics: they exhibit strong correlations, restrictions and degrees of freedom in end-user utilization patterns. In this work, we introduce application's sense of 'correctness' in the transmission, processing and optimization of multimedia messages. We formalize relations between messages in terms of application defined concepts. Resultant formalization has led to message reduction rules, MR, that are hierarchically organized as system independent and system dependent reduction rules. The optimization concepts developed, have ben experimented within our testbed, MMTP. Our performance studies on navigation class applications have revealed significant improvements: the end user response time has been reduced by several orders of magnitude. The delay variation has been decreased significantly, providing a more predictable service. The throughput has been increased by a factor of four. The server and network load has been reduced considerably. In our experiments, we have found inclusion rules to be very effective to reduce the maximum delay, the composition rules to boost the throughput, and caching schemes to reduce the server and network load.

In this paper, we present the currently achieved results of our research goal: building an easy to use and powerful multimedia documents authoring environment, which provides high level of expressiveness and open document format. These results are concerned with both the time representation and the time management in our authoring system Madeus. In the first part of the paper, we describe the requirements that must be provided by a time representation of multimedia documents, the choice we made and a comparison with other existing approaches. In the second part, we describe the presentation layer of our system, and how it handles services such as dynamic formatting, temporal access control operations and hyperlinks.

One of the key aspects of videos is the temporal relationship between video frames. In this paper we propose a tree-based model for specifying the temporal semantics of video data. We present a unique way of integrating our video model into an object database management system which has rich multimedia temporal operations. We further show how temporal histories are used to model video data, explore the video object base using object-oriented techniques. Such a seamless integration gives a uniform interface to end users. The integrated video object base management systems supports a broad range of temporal queries.

We present an analysis of the arrival process for world-wide web (WWW) request traffic at the hypertext transfer protocol (HTTP) level. Examination of three separate HTTP traffic datasets shows that the arrival process of HTTP request packets is not Poisson and does not appear to be tending towards Poisson as the number of aggregated traffic sources increase. Based on statistical comparison with common probability distributions we postulate a model for HTTP request traffic with lognormally distributed interarrival times and an invariant shape parameter of 1.0. However, a simulation study indicates that the estimate of response time performance for a WWW proxy server is insensitive to the choice of our model of lognormally distributed HTTP request interarrival times in place of the Poisson arrival process assumption.

Video servers must use large disk arrays to provide the huge amount of storage capacity and bandwidth needed. As the number of disk drives increases, the probability of a video server failure increases too. We propose a redundancy scheme that uses both RAID 5 techniques and mirroring to make a video server tolerant against all single disk failures. Our approach provides a unified framework for the use of RAID 5 and mirroring to achieve fault tolerance at the lowest additional cost possible, while guaranteeing 100 percent service availability even when operating with a failed disk.

Incorporating scalability into the storage of multimedia should be a fundamental design issue that will enable the storage services of today to scale to meet the throughput and storage requirements of future multimedia applications. In this paper we address the issues of storage scalability in relation to the real-time, storage capacity and throughput requirements of multimedia data types and the effect these demands have on the level of scalability required. We describe a multimedia storage architecture that exhibits a high degree of scalability by exploiting the scalable properties of fast packet switched networks such as ATM. Storage scalability is achieved through the dynamic replication of both storage servers and data objects. This is performed within our ATM networking environment in order to support the continually changing requirements of heterogeneous end-systems and also as a means of providing efficient load balancing and real-time resource expandability. By utilizing scalable compression technologies, the typical overhead incurred when copying between storage servers can be reduced to minimum. A key feature of our storage architecture centers around storing continuous media files as a number of compressed components that can be relocated and recombined at optimal locations within the distributed environment, using mixing agents; enabling efficient use of dynamically changing server, network and clients resources.

In this paper, we will address the problem of designing an interactive video server employing multiprocessors. An interactive video server needs to provide quick response to user's requests. When the video stream is a sequence of short video clips and if the order in which these clips are played out is determined by the user, the video clips need to be started up fairly quickly to give an impression of seamless or near-seamless delivery. We will address this problem of providing quick turnaround response to user's requests while guaranteeing smooth play out of already scheduled streams.

In a scalable server that supports the retrieval and display of continuous media, both the number of simultaneous displays and the expected startup latency of a display increases as a function of additional disk bandwidth. Based on a striping technique and around-robin placement of data, this paper describes object replication and request migration as two alternative techniques to minimize startup latency. In addition to developing analytical models for these two techniques, we report on their implementation using a scalable server. The results obtained from both the analytical models and the experimental system demonstrate the effectiveness of the proposed techniques.

In this paper, we consider the placement of scalable video data on single and multiple disks for storage and real-time retrieval. For the single disk case, we extend the principle of constant frame grouping form CBR to VBR scalable video data. When the number of admitted users exceeds the server capacity, the rate of data sent to each user is reduced to relieve the disk system overload, offering a graceful degradation in comparison with nonscalable data. We examine the qualities of video reconstructions obtained from a real disk video server and find the scalable video more visually appealing. For the multiple disk scenario, we prove that periodic interlacing results in lower system delay than striping in a video server using round-robin scheduling. We verify the results through detailed simulation of a four- disk array.

Many current distributed multimedia applications such as video on demand (VOD) are designed, implemented and used on top of general purpose OS and network platforms. Within this 'best-effort' environment, applications must use adaptive synchronization protocols and balance non-deterministic behavior of the underlying OS/network subsystem to achieve user acceptance for lip synchronization of the audio-visual information. We have designed, implemented and validated an adaptive synchronization scheme integrating adaptive services and synchronization protocols to provide lip synchronization within a VOD system. Our results indicate that most of the synchronization skew values are in the user desirable range of ms and that the remaining skew values are in the user acceptable range of ms.

The need for multimedia systems for industrial surveillance is rising in various industrial fields, such as plant monitoring, control systems, and security systems. In this paper, we concentrate on video information, which it is thought will be effective in surveillance support. We describe the development of our 'media controller' as a platform for this multimedia system. A media controller individually records large capacity video data continuously with a camera, and provides video data according to the scene, time and QoS demanded by the surveillance center in real time. With the media controller, we can easily give facility surveillance applications new advanced functions. For example, the media controller can be connected to the plant facility alarms and provide video data before and after an alarm as soon as the alarm is activated. Moreover is does not fail to capture data even if many alarms occur in a short time. We propose a mechanism to manage video data which consists of a continuous recording, event recordings, event recordings which are connected to the alarm events, and along duration timelapse recording.

The design and performance of the Berkeley Continuous Media Toolkit (CMT) is described. CMT provides a programming environment for rapid development of continuous media applications. CMT overhead is measured in the context of a simple video playback application and is found to be only a few milliseconds per frame played. As a demonstration of CMT as a research infrastructure, an experiment comparing adaptive frame rate control policies is described.

We describe anew framework for resource allocation that unifies the well-known proportional share and resource reservation policies. Each client is characterized by two parameters: a weight that represents the rate at which the client 'pays' for the resource, and a share that represents the fraction of the resource that the client should receive. A fixed rate corresponds to a proportional share allocation, while a fixed share corresponds to a reservation. Furthermore, rates and shares are duals of each other. Once one parameters is fixed the other becomes fixed as well. If a client asks for a fixed share then the level of competition for the resource determines the rate at which it has to pay, while if the rate is fixed, level of competition determines the service time the clients should receive. To implement this framework we use a new proportional share algorithm, called earliest eligible virtual deadline first, that achieves optical accuracy in the rates at which process execute. This makes it possible to provide support for highly predictable, real-time services. As a proof of concept we have implemented a prototype of a CPU scheduler under the FreeBSD operating system. The experimental results show that our scheduler achieves the goal of providing integrated support for batch and real-time applications.

Disruptions and delays in the retrieval of continuous motion video data streams from storage devices are unacceptable for video-on-demand (VOD) service. Concurrent VOD services require careful scheduling of accesses to the storage device in real-time. In this paper, we propose a dynamic approach to schedule the retrieval of motion ideo data in interactive VOD servers. Most of the previous VOD scheduling approaches use fixed disk read sizes and pre-determined reading orders. Run-time information is seldom used to fully exploit the potential capacity of the system. To maximize throughput, our approach relaxes admission control by observing run-time information. To improve performance under heavy transients, we introduce mechanisms to dynamically control the read sizes of disk accesses, to pipeline admission of new streams with departure of ongoing streams, and to safely deviate from seek-reducing service sequence to provide early initial service. Most important of all, our scheduler is designed to reduce start-up delay significantly. When the demand on real-time services decreases, our scheduler is also highly efficient in redirecting disk bandwidth to service sporadic requests. We evaluate our technique by comparing its performance with two static seek-reducing techniques via thorough experiments under different buffer capacities and load settings. Results of experiments show our technique's significant improvements in real-time service throughput, initial response time, and sporadic service throughput.

Unlike video-on-demand servers, non-linear editing systems enable the user to manipulate the content of the video database. Applications such as news editing systems require that the underlying storage server be able to concurrently record live broadcast information, modify pre-recorded 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. Our contribution is a novel real-time disk scheduling algorithm that treats both read and write requests in a homogeneous manner in order to ensure that their deadlines are met. Simulation results demonstrate that the proposed algorithm offers low violations of read deadlines, reduces buffer requirements, and improves the throughput of the storage server by enhancing the utilization of available disk bandwidth.

With video services featuring in future broadband applications, efficient video server architectures are required. Previous work has shown the efficacy of using large disk arrays for the provision of video to a substantial audience. Recent papers have proposed call- admission control schemes for video servers which utilize the statistics of compressed video and the characteristics of the disk drives themselves. To date, however, the issue of load-balancing has not been addressed. In this paper we supplement prior efforts with the development of a predictive call-admission control scheme which uses the largely deterministic nature of disk array operation to maintain a well-balanced load which in turn reduces the variation of the delay experienced by new requests. We provide detailed results comparing our scheme to others in the literature and show that the predictive scheme gives considerable improvement in terms of both admission delay and interactivity delay.

This paper describes a server selection mechanism for connection oriented services based on passive probing. The criterion of selection is the quality of service expected from each server, expressed as a function of availability and response time. Measures from previous connections to servers made by local clients are used to continuously update a QoS database which the prediction algorithm uses to compute the response time expected in subsequent connections. The forecasting approach is mainly based on prior measurements of TCP connection establishment time. The maximum segment size in a connection is also considered. The proposed metric is compared with other ones normally used to measure network proximity. Results show that the proposed server selection mechanism achieves a reduction of response time of over 50 percent compared with a random selection mechanism.

Embedding information into multimedia data, also called watermarking, is a topic that has gained increased attention recently. For practical applications like authentication and labeling in pay-per-view television broad-casting, watermarking of video, and especially of already encoded video, is interesting. We present a scheme for robust watermarking of MPEG-2 encoded video. The watermark is embedded into the MPEG-2 bitstream, and can be retrieved from the decoded video. The scheme is robust and of much lower complexity that a complete decoding process followed by watermarking in the pixel domain and re-encoding. Although an existing MPEG-2 bitstream is partly altered, the scheme avoids drift by adding a drift compensation signal. The scheme has been implemented and the results confirm that a roust watermark can be embedded into MPEG encoded video which can be used to securely transmit arbitrary binary information at a data rate of several bytes/second. The scheme is also applicable to other hybrid coding schemes like MPEG-1, H.261 and H.263.

A pure 'technological' solution to network quality problems is incomplete since any benefits from new technologies are offset by the demand from exponentially growing electronic commerce ad data-intensive applications. SInce an economic paradigm is implicit in electronic commerce, we propose a 'market-system' approach to improve quality of service. Quality of service for digital products takes on a different meaning since users view quality of service differently and value information differently. We propose a framework for electronic commerce that is based on an economic paradigm and mass-customization, and works as a wide-area distributed management system. In our framework, surrogate-servers act as intermediaries between information provides and end- users, and arrange for consistent and predictable information delivery through 'digital contracts.' These contracts are negotiated and priced based on economic principles. Surrogate servers pre-fetched, through replication, information from many different servers and consolidate based on demand expectations. In order to recognize users' requirements and process requests accordingly, real-time databases are central to our framework. We also propose that multimedia information be separated into slowly changing and rapidly changing data streams to improve response time requirements. Surrogate- servers perform the tasks of integration of these data streams that is transparent to end-users.

The rapidly increasing number of tools available on the internet is changing the way people view software systems. People are now used to downloading plug in helper tools in order to decode and display different types of media within web browsers. The ease with which this can now be done is a far cry from the days, quite recently, when data had to be manually processed by a number of obviously independent software packages. Using the tools available to simply decode and display new data formats in only one way in which such software can be used, one could even consider a web browser as just another tool. Compete new applications could be constructed by selecting a suitable range of tools and supplying minimal glue software. This paper describes, as an example of this approach, a collaborative application supporting synchronous audio-visual communication and collaborative web browsing. The system develop is designed to make use of a wide range of freely available tools with no modification of existing web servers or clients. Alternative implementation strategies are discussed, followed by a detailed description of the approach chosen for this implementation. A technique allowing small to medium sized groups World Wide Web users to be tracked and their location to be presented to people with similar interests is then explained, followed by details of a mechanism allowing the information gained about such groups to be shared among arbitrary of similar groups.

The WWWinda Orchestrator is a simple but powerful tool for coordinating distributed Java applets. Loosely derived from the Linda programming language developed by David Gelernter and Nicholas Carriero of Yale, WWWinda implements a distributed shared object space called TupleSpace where applets can post, read, or permanently store arbitrary Java objects. In this manner, applets can easily share information without being aware of the underlying communication mechanisms. WWWinda is a very useful for orchestrating flocks of distributed Java applets. Coordination event scan be posted to WWWinda TupleSpace and used to orchestrate the actions of remote applets. Applets can easily share information via the TupleSpace. The technology combines several functions in one simple metaphor: distributed web objects, remote messaging between applets, distributed synchronization mechanisms, object- oriented database, and a distributed event signaling mechanisms. WWWinda can be used a s platform for implementing shared VRML environments, shared groupware environments, controlling remote devices such as cameras, distributed Karaoke, distributed gaming, and shared audio and video experiences.

The effectiveness of collaborative multimedia systems depends on the regulation of access to their shared resources, such as continuous media or instruments used concurrently by multiple parties. Existing applications use only simple protocols to mediate such resource contention. Their cooperative rules follow a strict agenda and are largely application-specific. The inherent problem of floor control lacks a systematic methodology. This paper presents a general model on floor control for correct, scalable, fine-grained and fair resource sharing that integrates user interaction with network conditions, and adaptation to various media types. The motion of turn-taking known from psycholinguistics in studies on discourse structure is adapted for this framework. Viewed as a computational analogy to speech communication, online collaboration revolves around dynamically allocated access permissions called floors. The control semantics of floors derives from concurrently control methodology. An explicit specification and verification of a novel distributed Floor Control Protocol are presented. Hosts assume sharing roles that allow for efficient dissemination of control information, agreeing on a floor holder which is granted mutually exclusive access to a resource. Performance analytic aspects of floor control protocols are also briefly discussed.

Bandwidth smoothing techniques for the delivery of compressed prerecorded video have been shown effective in removing the burstiness required for the continuous playback of stored video. Given a fixed client-side buffer, several bandwidth smoothing algorithms have been introduced that are provably optimal under certain constraints. These algorithms, however, may be too aggressive in the amount of data that they prefetch, making it more difficult to support VCR functions that are required for interactive video-on- demand systems. In this paper, we introduce a rate- constrained bandwidth smoothing algorithm for the delivery of stored video that, given a fixed maximum bandwidth rate minimizes both the smoothing buffer requirements as well as the buffer residency requirements. By minimizing the buffer residency times, the clients and servers can remain more tightly coupled making VCR functions easier to support. A comparison between the rate-constrained bandwidth smoothing algorithm and other bandwidth smoothing algorithms is presented using a compressed full-length movie.

As distributed multimedia applications are starting to be offered as services in enterprise and residential cable networks, there is a growing interest in platforms that provide a standard framework for the development and deployment of these applications. Key issues in platform design are service diversity, service portability and interoperability of user terminal equipment. We propose a platform architecture for the provision of multimedia communication services which logically separates application processing from media processing. Applications are installed in application pools from where they control a set of communicating multimedia terminals. Application-specific intelligence is downloaded into the terminals in the from of Tcl/Tk or Java scripts that generate graphical user interfaces, control media processing components, and communicate with the application in the pool. The platform architecture is based on CORBA and is defined as an extensible set of IDL interfaces for control and stream interfaces for multimedia communication. The platform architecture is based on CORBA and is defined as an extensible set of IDL interfaces for control and stream interfaces for multimedia communication. The platform supports applications development with high-level programming interfaces.

Asynchronous transfer mode (ATM) network is one the most promising networks which are scalable in turn of bandwidth and distance. Moreover, bandwidth reservation and quality of service guarantees make ATM attractive to deliver multimedia information in real-time. Existing protocol suites fail to give access to those characteristics. therefore, applications demand an ATM application programming interface (API) forum has produced a semantics document which is independent of system platforms. This paper covers a special syntax mapping of the ATM API services on top of X/open transport interface (XTI) which is able to give applications access directly to the special quality and traffic services of an ATM network. A particular realization of the API on XTI environment is proposed and implemented on the MacOS networking platform. It provides a flexible and modular design of the ATM networking.