Lancaster University is investigating the design of a scalable hierarchical video storage architecture, which can support the replay of tens of simultaneous video and audio streams to clients distributed around the campus and wide area. The project aims to address the bandwidth problems of single node video servers, by providing multiple storage instances with streams load balances across the instances. Two differing methods of load balancing have been investigated: file replication; and node striping. To reduce the overhead of file replication redundancy and to minimize the reliability problems of simple node striping, a two level distribution hierarchy consisting of domains is introduced. A domain consists of a collection of storage nodes distributed over a LAN, using node striping, where the overall reliability of the network is high. Between domains, file replication is used, with file interests (popularity) and network link capabilities being used to control overall file replication and placing. Such a hierarchy is highly scalable, enabling a VoD system to be scaled over both the local and wide area. The approach is investigated through simulation and an implementation.

CD-ROMs have proliferated as a distribution media for desktop machines for a large variety of multimedia applications (targeted for a single-user environment) like encyclopedias, magazines and games. With CD-ROM capacities up to 3 GB being available in the near future, they will form an integral part of Video on Demand (VoD) servers to store full-length movies and multimedia. In the first section of this paper we look at issues related to the single- user desktop environment. Since these multimedia applications are highly interactive in nature, we take a pragmatic approach, and have made a detailed study of the multimedia application behavior in terms of the I/O request patterns generated to the CD-ROM subsystem by tracing these patterns. We discuss prefetch buffer design and seek time characteristics in the context of the analysis of these traces. We also propose an adaptive main-memory hosted cache that receives caching hints from the application to reduce the latency when the user moves from one node of the hyper graph to another. In the second section we look at the use of CD-ROM in a VoD server and discuss the problem of scheduling multiple request streams and buffer management in this scenario. We adapt the C-SCAN (Circular SCAN) algorithm to suit the CD-ROM drive characteristics and prove that it is optimal in terms of buffer size management. We provide computationally inexpensive relations by which this algorithm can be implemented. We then propose an admission control algorithm which admits new request streams without disrupting the continuity of playback of the previous request streams. The algorithm also supports operations such as fast forward and replay. Finally, we discuss the problem of optimal placement of MPEG streams on CD-ROMs in the third section.

Video servers aimed at the home market must deliver very large files at a low cost. The video files must be shared and reused to contain costs. The nature of videos, however, demand a low jitter (late block delivery) rate. Normal systems tolerate disk queues and deliver, typically, smaller objects in a less predictable manner. This paper explores in a multi disk, stripped, environment whether block placement, interdisk permuation, replication and compression impacts the rate of jitter in a multiuser setting with different assumptions as to the pattern of use. Correspondingly, the number of supportable users for a given level of quality (jitters per hour per user) is addressed. Block allocation is the term used to describe the placement of video blocks on selected disk(s).

Today's interactive television systems are using proprietary communication protocols and interchange formats. To provide inter-operability at the application level the next generation of interactive television system will be based on standardized communication protocols, monomedia and multimedia formats. This paper presents the Globally Accessible Services (GLASS) system which is a prototype interactive television system based on the Multimedia and Hypermedia Expert Group (MHEG) standard. After a brief introduction to MHEG as the multimedia interchange format between application server and set-top box in interactive television systems, the GLASS clients and servers are described, and an example scenario for navigation in the GLASS system is provided.

Active networks allows users to inject customized programs into the nodes of the network. In this paper, we describe our vision of an active network architecture, outline our approach to its design, and survey the technologies that can be brought to bear on its implementation. In the course of this presentation we identify a number of research questions to be addressed and propose that the research community mount a joint effort to develop and deploy a wide area ActiveNet.

Current wireless network systems (e.g. metropolitan cellular) are constrained by fixed bandwidth allocations and support only a narrow range of services (voice and low bit-rate data). To overcome these constraints and advance the state of the art in wireless multimedia communications, we are developing variable-rate video and speech compression algorithms, and wireless node architectures that will enable peer-to-peer multimedia networking even with very low bandwidth. To support this objective, each wireless node must support new applications (for multimedia), advances in networking and source coding to support multimedia under limited bandwidth conditions (wireless), advances in physical layer design to support robust, low power, high packet throughput links, low power DSP for multimedia compression, and an architectural strategy to integrate these components into an efficient node. The algorithms and architectures to support this functionality are presented here, together with some preliminary results on network performance.

Wireless data services, other than those for electronic mail or paging, have thus far been more promising than successful. We believe that future mobile information systems must be built upon heterogeneous wireless overlay networks, extending traditional wired and internetworked processing `islands' to hosts on the move over coverage areas ranging from in-room, in- building, campus, metropolitan, and wide-areas. Unfortunately, network planners continue to think in terms of homogeneous wireless communications systems and technologies. In this paper, we describe a new wireless data networking architecture that integrates diverse wireless technologies into a seamless internetwork. In addition, we describe the applications support services needed to make it possible for applications to continue to operate as mobile hosts roam across such networks. The architecture described herein is being implemented in a testbed at the University of California, Berkeley under joint government/industry sponsorship.

Anytime anywhere wireless access to databases, such as medical and inventory records, can simplify workflow management in a business, and reduce or even eliminate the cost of moving paper documents. Moreover, continual progress in wireless access technology promises to provide per-user bandwidths of the order of a few Mbps, at least in indoor environments. When combined with the emerging high-speed integrated service wired networks, it enables ubiquitous and tetherless access to and processing of multimedia information by mobile users. To leverage on this synergy an indoor wireless network based on room-sized cells and multimedia mobile end-points is being developed at AT&T Bell Laboratories. This research network, called SWAN (Seamless Wireless ATM Networking), allows users carrying multimedia end-points such as PDAs, laptops, and portable multimedia terminals, to seamlessly roam while accessing multimedia data streams from the wired backbone network. A distinguishing feature of the SWAN network is its use of end-to-end ATM connectivity as opposed to the connectionless mobile-IP connectivity used by present day wireless data LANs. This choice allows the wireless resource in a cell to be intelligently allocated amongst various ATM virtual circuits according to their quality of service requirements. But an efficient implementation of ATM in a wireless environment requires a proper mobile network architecture. In particular, the wireless link and medium-access layers need to be cognizant of the ATM traffic, while the ATM layers need to be cognizant of the mobility enabled by the wireless layers. This paper presents an overview of SWAN's network architecture, briefly discusses the issues in making ATM mobile and wireless, and describes initial multimedia applications for SWAN.

We propose a multiple-delivery transport service tailored for graphics and video transported over connections with wireless access. This service operates at the interface between the transport and application layers, balancing the subjective delay and image quality objectives of the application with the low reliability and limited bandwidth of the wireless link. While techniques like forward-error correction, interleaving and retransmission improve reliability over wireless links, they also increase latency substantially when bandwidth is limited. Certain forms of interactive multimedia datatypes can benefit from an initial delivery of a corrupt packet to lower the perceptual latency, as long as reliable delivery occurs eventually. Multiple delivery of successively refined versions of the received packet, terminating when a sufficiently reliable version arrives, exploits the redundancy inherently required to improve reliability without a traffic penalty. Modifications to acknowledgment-repeat-request (ARQ) methods to implement this transport service are proposed, which we term `leaky ARQ'. For the specific case of pixel-coded window-based text/graphics, we describe additional functions needed to more effectively support urgent delivery and asymptotic reliability. X server emulation suggests that users will accept a multi-second delay between a (possibly corrupt) packet and the ultimate reliably-delivered version. The relaxed delay for reliable delivery can be exploited for traffic capacity improvement using scheduling of retransmissions.

Today the idea and the mechanisms of MultiMedia Mail (MMM), the transmission of multimedia information like images, audio and video objects etc. as an extension to email, and the related problems and solution concepts are very well known. The idea of Computational or Active Mail (AM) has existed since 1976; transfer programs embedded in standard mail which automatically execute at the receivers site, bringing mail to life. The integration of both mechanisms (MMM and AM) leads to the concept of Active MultiMedia mail. The object of ACTIVEM³ is the development and implementation of a system for the realization of Active MultiMedia Mail and a Composing Tool as an easy to use interactive authoring environment. This paper introduces the basic ideas. The results of the proposed concept are presented through a realized prototype.

The recent advances in multimedia systems, together with the advent of high speed networks, paved the way to a new generation of applications. In particular, the authoring environments have found in multimedia the means of increasing the richness of information contained in electronic documents. With the evolution of new computer systems that can handle multimedia information, time-based data can be integrated in electronic documents taking into account their temporal dimension. In such documents, temporal dependencies between the different media objects define a temporal structure within the document. This structure is the basic support for the representation of dependencies between data such as audio, video and virtual images. Furthermore, it allows the scheduling of presentation actions during the document presentation. The presentation of multimedia documents is dynamic and the positioning of objects in time together with their duration have to be specified. To achieve this operation efficiently, a high level temporal representation is needed which allows the author to specify all the temporal dependencies between multimedia objects. In this paper, we propose an interval-based temporal model and constraints which provide a basis for the management of the consistency of multimedia documents. We propose an efficient algorithm allowing the detection of a wide range of inconsistencies. The emphasis in the design of these algorithms is put on the handling of both the flexibility of temporal specifications and the indeterministic behaviour of some media objects. Furthermore, we use the logical organization of the document in nested entities to enhance the performance of the methods used for detecting inconsistencies. The aim of our approach is to fulfill the following requirements . Structured modelling: The document content is defined by a hierarchy of nested components where leaves are basic media objects and nodes composite objects. . Incremental manipulation of the document: This means that the author adds one constraint at a time, retaining all previously introduced relations as the current state of the document. • Consistency checking: For every specification introduced by the author, the system checks if there exists a solution to the set of constraints, otherwise an error is reported to the author. • Integration of the different dimensions of multimedia documents: In our model, we focus on four dimensions of the document (logical, temporal, spatial and hyperlink). These dimensions are closely related and have to be considered simultaneously as they may interfere. In this paper, we will focus on the temporal and logical dimensions of the document but we will describe briefly how this fits with the spatial one. . Automatic production of temporal layout: The author specifies relations using a high-level language to describe the document temporal layout, and does not have to explicitly set the low-level synchronization dates. In section 2, we present our model of document composition showing the logical, spatial, and temporal dimensions. In section 3, we describe how we can create and manipulate the internal representation of the multimedia document in the form of constraint networks. In section 4, a consistency checking algorithm is proposed, followed by a discussion. Finally, in section 5, we conclude our work and give some future directions.

We investigate the benefits of using a partially-ordered/partially-reliable (PO/PR) transport service for multimedia document retrieval over the Internet by implementing a prototype system. We introduce PMSL, a document specification language combining aspects of Little and Ghafoor's OCPN with features for graceful degradation. We then show that for retrieval of PMSL documents, our PO/PR transport protocol (POCv2) provides several benefits over traditional protocols such as TCP or UDP. First, POCv2 provides mechanisms to achieve the reliability and order requirements of individual multimedia objects as specified by a document author. Second, when network conditions are poor (e.g., high loss rates), POCv2 provides for graceful degradation. Finally, POCv2 simplifies application development by providing appropriate mechanisms for synchronization.

The University of Leeds Virtual Science Park (VSP) is an example of a virtual working system for supporting the provision of a number of services, including virtual consultancy, workbased learning, consortium building and access to information. This paper presents a new architecture based on event mechanisms. The extensions fall into 3 areas: provision of timely, up-to-date information based on users' interests; integration with existing information sources; and chance interaction. The main problems addressed are facilities for keeping the VSP information up to date and keeping users notified of relevant changes to the data. Integration with existing data sources is also key to the provision of an information space capable of supporting VSP services. We describe an event mechanism to support information location, information monitoring, chance interaction and integration with existing information sources. The system will be used in a VSP Workbased learning project for supplying multimedia information and collaboration facilities to remote students to support distance learning. A World Wide Web gateway has also been developed to provide wide scale access to the VSP.

A project to investigate the feasibility of delivering on-demand distance education to the desktop, known as the Asynchronous Distance Education ProjecT (ADEPT), is presently being carried out. A set of Stanford engineering classes is digitized on PC, Macintosh, and UNIX platforms, and is made available on servers. Students on campus and in industry may then access class material on these servers via local and metropolitan area networks. Students can download class video and audio, encoded in QuickTime^TM and Show-Me TV^TM formats, via file-transfer protocol or the World Wide Web. Alternatively, they may stream a vector-quantized version of the class directly from a server for real-time playback. Students may also download Postscript^TM and Adobe Acrobat^TM versions of class notes. Off-campus students may connect to ADEPT servers via the internet, the Silicon Valley Test Track (SVTT), or the Bay-Area Gigabit Network (BAGNet). The SVTT and BAGNet are high-speed metropolitan-area networks, spanning the Bay Area, which provide IP access over asynchronous transfer mode (ATM). Student interaction is encouraged through news groups, electronic mailing lists, and an ADEPT home page. Issues related to having multiple platforms and interoperability are examined in this paper. The ramifications of providing a reliable service are discussed. System performance and the parameters that affect it are then described. Finally, future work on expanding ATM access, real-time delivery of classes, and enhanced student interaction is described.

We report our work on FDDI based networks for multimedia applications. It lifts previous research limitations and shows a systematic way for bounding message delays at the application level. The synchronous server is designed to control application admissions and properly multiplex messages from multiple applications on one node. We consider an integrated system including both the sender and receiver hosts, and the network. A set of constraints are proposed for controlling application admissions and guaranteeing the normal operation of the integrated system so that the total message delays can be bounded.

It has been recognized that an effective support for multimedia applications must provide Quality of Service (QoS) guarantees. Current methods propose to provide such QoS guarantees through coordinated network resource reservations. In our approach, we extend this idea providing system-wide QoS guarantees that consider the data manipulation and transformations needed in the intermediate and end sites of the network. Given a user's QoS requirements, multisegment virtual channels are established with the necessary communication and computation resources reserved for the timely, synchronized, and reliable delivery of the different datatypes. Such data originate in several distributed data repositories, are transformed at intermediate service stations into suitable formats for transportation and presentation, and are delivered to a viewing unit. In this paper, we first review NETWORLD, an architecture that provides such QoS guarantees and an interface for the specification and negotiation of user-level QoS requirements. Our user interface supports both expert and non- expert modes. We then describe how to map user-level QoS requirements into low-level system parameters, leading into a contract between the application and the network. The mapping considers various characteristics of the architectures (such as the hardware and software available at each source, destination, or intermediate site) as well as cost constraints.

The Communications Resource Manager (CRM) provides communications at a specified Quality of Service (QoS) for networked multimedia workstations in an environment where the network and workstation resources are changing. The CRM enables a consistent application interface and manages all workstation communications resources. It established network connections on behalf of applications, monitors their progress and notifies applications when network QoS events take place. Applications can then modify their behavior (compression rate, number of simultaneous media, media type) to cope with the change. The CRM provides mechanisms to negotiate at call setup time the level of multimedia support provided. If optimal resources are not available, call quality degradation paths allow call establishment at the highest QoS possible. Call admission based on on-going network performance monitoring and application performance feedback from the CRM can be used to prevent further QoS degradation by refusing to attempt connections when insufficient resources are available. The CRM enables existing multimedia workstations to communicate in an environment with known QoS. The CRM flows naturally into emerging QoS techniques for end-to-end ATM services. Because the CRM operates at the application level it is also applicable to the ATM interconnection of LANs whereas current ATM Forum proposals are not.

The preservation of QoS for multimedia traffic through a data network is a difficult problem. We focus our attention on video frame rate and study its influence on speech perception. When sound and picture are discrepant (e.g., acoustic `ba' combined with visual `ga'), subjects perceive a different sound (such as `da'). This phenomenon is known as the McGurk effect. In this paper, the influence of degraded video frame rate on speech perception was studied. It was shown that when frame rate decreases, correct hearing is improved for discrepant stimuli and is degraded for congruent (voice and picture are the same) stimuli. Furthermore, we studied the case where lip closure was always captured by the synchronization of sampling time and lip position. In this case, frame rate has little effect on mishearing for congruent stimuli. For discrepant stimuli, mishearing is decreased with degraded frame rate. These results indicate that stiff motion of lips resulting from low frame rate cannot give enough labial information for speech perception. In addition, the effect of delaying the picture to correct for low frame rate was studied. The results, however, were not as definitive as expected because of compound effects related to the synchronization of sound and picture.

In recent years, wavelet transforms have been successfully applied to image and video compression. In a distributed, multimedia computing environment, compressed video and image files need to be transmitted to users for real-time replay. Because the network is subject to packet losses, the image packetization scheme should take packet losses into account in their design. In this paper, we present an error concealment algorithm for wavelet-based compressed images over packet-switched networks. Two different packetization schemes, called the intrablock-oriented and interblock-oriented schemes, in conjunction with wavelet coding, are presented. In our approach, adjacent wavelet coefficients are scattered into different packets, so that any packet contains encoded wavelet coefficients at different resolution layers. When a packet is lost due to network congestion or transmission errors, a lost wavelet coefficient is estimated by the receiver through a linear interpolation of its adjacent ones. Our approach is evaluated under two different packet loss models with various packet loss probabilities through simulations driven by actual video sequences.

This paper describes the design of and implementation of Presentation Processing Engines (PPEs) that provide flexible control over QoS to manage heterogeneity in networks, end- systems and compression formats. Development of PPEs is facilitated by a framework that provides the modular architecture, data types, and transformations common to most codecs, filters, transcoders, etc. to facilitate the implementation of emerging compression standards and their integration into media processing applications. By allowing fine-grained composition of compression and image processing modules, the framework facilitates the development of extensible presentation processing engines that can be dynamically configured to adapt to changes in resource availability and user preferences.

There is now a huge variety of multimedia applications, network technologies and end-system architectures. Within this new and challenging environment, the importance of Quality of Service (QoS) mechanisms to allocate and monitor system resources has been recognized. A key goal of our research is how to manage the QoS requirements of heterogeneous receivers in applications that depend on multipeer communications. This paper presents results of our recent work on QoS filter mechanisms that operate on compressed video and audio streams. These filter mechanisms adapt the QoS of continuous media streams allowing diverse qualities of media to be delivered to a number of receivers in the same multipeer dissemination tree. The paper focuses particularly on filter operations applied to bandwidth-demanding video services in order to allow low capability clients, primarily connected via mobile and other low-bandwidth links, to participate in these dissemination services. This is performed without detriment to existing high capability clients. The results presented show the feasibility of providing individual QoS to individual clients.

A new progressive image transmission technique using adaptive block truncation coding is introduced in this paper. The adaptive block truncation coding was proposed as a non- transform coding mode for edge blocks in digital video sequences. By adapting more sophisticated just-noticeable-difference model of the human visual system, we can get an improved adaptive block truncation coding than the original work. With this improvement, we propose a progressive transport format of the adaptive block truncation coding so that we can reconstruct images in 3-pass coarse-to-fine manner. Simulation results on the adaptive block truncation coding is compared to those of JPEG and GIF. Through the transmission test via a World Wide Web browser, we can confirm the proposed transport format reduces bandwidth usage.

While client/server document imaging systems have matured considerably, fully satisfactory mechanisms for distributing and providing interactive access to document images over the World-Wide Web have not yet emerged. The interface functionality of most scanned document viewers and browsers is primitive compared to what is available for revisable-form electronic documents. Common image viewers provide only scrolling within a page, change of magnification and jumping to the next/previous page. By contrast, electronic document browsers often provide content-based operations such as string search with highlighting of search hits, up-down-next-previous navigation through logical structure trees, and hypertext links from indexes and tables of contents to body text. Recently, there have been a number of efforts aimed at enlivening imaged documents by providing more content-based interfaces. Examples include Adobe Capture, Dienst, Xerox's DocuWeb, and the UC Berkeley multivalent document browser. This paper reviews some of the methods currently used for transmitting and browsing page images of documents on the Internet and presents a design for adding some desirable features to future document image browsers.

This paper discusses the personalization of online newspapers based on our experience with the Krakatoa Chronicle, an interactive, personalized, newspaper on the World Wide Web. The personalization of newspapers involves both social and technical issues. In social terms, it is important that users can control the extent of personalization, because newspapers are not only a means to get personally interesting articles but also a way to get information you are not explicitly looking for. In technical terms, the manner in which the user's interest is measured, and the strategy used to personalize the presentation are important. The Krakatoa Chronicle's approach to solving these problems is by sending over an interaction agent (in Java) from the web server side to the web-client, to manage the layout, interactions with the user, and provide feedback about user actions. In our system, the newspaper has a similar appearance to everyday printed ones, with multiple columns. The user has various interaction techniques to read articles, and has easy control over layout parameters including how personal the contents should be. The system can get the user's interest without requiring the user to do anything other than just read articles. The Krakatoa Chronicle will serve as a good testbed to learn how people would like to have their newspapers personalized.

This paper examines the data distribution issue of multiparty videoconferencing over the IP Internet. IP multicast, which supports efficient one-to-many communications, is envisaged to provide data transports for this type of applications. While different videoconferencing scenarios require different delay requirements ranging from several hundred milliseconds to a few seconds, existing multicast routing protocols provide only one route, which may either fall short of the requirement or provide more than what is needed thereby wasting network resources. We present a new protocol named Core Group Based Tree, which has the dynamic feature of splitting and merging multicast trees in response to the distribution of participants' locations and the delay requirements of the multicast application. A modified version of the Core Based Tree protocol, this new protocol inherits CBT's scalability and simple system design but has an improved delay performance. Our simulation results show significant improvements over CBT on both the maximum delay and the average delay performances.

Continuous media, such as audio and video, are quickly becoming an integral part of distributed computing environments. A shortcoming of such environments is their lack of support for continuous flows of information. What is missing is the notion of an on-going communication activity with an associated quality of service. This paper describes a model for integrating multimedia flows into a distributed computing system. The model permits explicit bindings to be established between type-checked stream interfaces. The stream binding is represented in the computational model as a first-class object which encapsulates configuration rules and QoS attributes. An operational interface supplied by the binding object allows other objects within the system to manage the binding, to renegotiate QoS parameters, to control the flows across the binding, and to register interest in stream events such as flow reports and communication errors. The in-band stream interface is an abstract C++ wrapper around transport mechanisms that include intra-host IPC and network transport protocols such as TCP and XTP. A prototype implementation of this model is described using the Common Object Request Broker Architecture. The implementation environment comprises a local area ATM network with directly attached multimedia peripherals and general purpose workstations.

Video servers need to assign a fixed set of resources to each video stream in order to guarantee on-time delivery of the video data. If a server has insufficient resources to guarantee the delivery, it must reject the stream request rather than slowing down all existing streams. Large scale video servers are being built as clusters of smaller components, so as to be economical, scalable, and highly available. This paper uses a blocking model developed for telephone systems to evaluate video server cluster topologies. The goal is to achieve high utilization of the components and low per-stream cost combined with low blocking probability and high user satisfaction. The analysis shows substantial economies of scale achieved by larger server images. Simple distributed server architectures can result in partitioning of resources with low achievable resource utilization. By comparing achievable resource utilization of partitioned and monolithic servers, we quantify the cost of partitioning. Next, we present an architecture for a distributed server system that avoids resource partitioning and results in highly efficient server clusters. Finally, we show how, in these server clusters, further optimizations can be achieved through caching and batching of video streams.

The emerging `information super-highway' and accelerating improvements in computer and mass storage technologies will soon make multimedia services, such as video-on-demand (VOD), a reality. Since a media server will be required to move a large amount of data over distribution networks, its I/O subsystem design is critical to its success. In this paper, we explore a new technology, Fiber Channel, as a storage interface for video servers. Specifically, we study Fiber Channel loop topology that attaches multiple disk drives to a server host. In order to compare the performance of the new Fiber Channel interface with existing parallel SCSI, we built a video server simulator that simulates the behavior of both interfaces. The results show that with the same number of disks and the same system configurations, one Fiber Channel loop can achieve 50% higher performance (measured by the number of concurrent streams supported by the server) than four fast/wide SCSI channels. Our results show that Fiber Channel is attractive as a video/media server I/O interface. We also analyze the buffer size requirements and I/O transfer size for various configurations.

This paper presents an analytical framework for evaluating and optimizing routing and path establishment strategies for multimedia communication in an integrated services network. Based on a given routing strategy, we show how to determine the probability of success for the establishment phase by using a stochastic knapsack approximation. Our method can be used to optimize the assignment routing paths in a manner which maximizes the probability of the network being able to support multimedia connection requests. This is done through the use of a new cost function called the marginal blocking cost of a link.

In a video server environment, some video objects (e.g., movies) are very large and are read sequentially. Hence it is not economical to cache the entire object. However, caching random fractions of a multimedia object is not beneficial. Therefore, traditional cache management policies such as LRU are not effective. The sequential access of pages can be exploited by caching only the intervals between two successive streams on the same object, i.e., by retaining the pages brought in by a stream for reuse by a closely following stream and subsequently discarding them. In contrast to the movie-on-demand workload, an interactive workload is composed of many short video clips (e.g., shopping). Hence, concurrent access to the same video chip will be infrequent and interval caching policy will not be effective. In this paper, we propose a Generalized Interval Caching policy that caches both short video objects as well as intervals or fractions of large video objects. To study the efficacy of the GIC policy, we also propose a model for mixed short interactive and long video workloads. The proposed policy is shown to effectively reduce disk overload and hence to increase the capacity of the video server.

Using packet networks to transport multimedia introduces delay variations within and across streams, necessitating synchronization at the receiver. This requires stream data to be buffered prior to presentation, which also increases its total end to end delay. Concord recognizes that applications may wish to influence the underlying synchronization policy in terms of its effect on quality of service. It provides a single framework for synchronization within and across streams and employs an application specific tradeoff between packet losses, delay and inter- stream skew. We present a new predictive approach for synchronization and a selection of results from an extensive evaluation of Concord for use in the Internet. A trace driven simulator is used, allowing a direct comparison with alternative approaches. We demonstrate that Concord can operate with lower maximum delay and less variation in total end to end delay, which in turn can allow receiver buffer requirements to be reduced.

We examine the impact on optimal data placement schemes for random retrieval due to a new trend in disk technology, namely zoned magnetic disks, which record data with a constant linear density and have a constant angular velocity. This modifies the optimal data placement that minimizes response time, since now the data transfer time varies with block placement whereas the transfer time and cylinder capacity was constant for traditional magnetic disks. We focus on the optimal placement of video objects stored in multimedia servers that consist of fixed-size blocks of constant-bit-rate encoded data or varying-size blocks of variable-bit-rate encoded data. The differences in popularity and access rates among these objects allow minimization of seek times by varying the data placement. We describe an optimal placement of fixed-size blocks on zoned disks that minimizes response time. Video objects are accessed by streams that playout the blocks at a given rate, requiring disk access by a deadline in order to avoid glitches in playout. For the placement of varying-size blocks on zoned disks, we study a scheme that minimizes the probability that a block access misses its deadline. This is done by adjusting the value representing the popularity of blocks to take into account both block size and the relative importance of seek time and transfer time using a weighting factor. We quantify the improvements in disk throughput for a given block-deadline miss probability.

This paper describes the design and implementation of a file server for variable bit rate continuous media. Most continuous media file servers have been designed for constant bit rate streams. We address the problem of building a server where each stream may have a different bit rate and, more importantly, where the bit rate within a single stream may vary considerably. Such servers will become increasingly more important because of Variable Bit Rate compression standards such as is possible with MPEG-2.

In this paper we compare techniques for storage and real-time retrieval of Variable Bit Rate (VBR) video data for multiple simultaneous users. The motivation for considering VBR is that video results in inherently time varying data, and as such, with the same average bit rate, higher quality can be achieved with VBR than with Constant Bit Rate (CBR). We propose and compare the following three classes of VBR data placement and retrieval techniques: Constant Time Length (CTL) places and retrieves data in blocks corresponding to equal playback durations, Constant Data Length (CDL) places and retrieves constant-sized data blocks, and a hybrid solution uses CDL placement but retrieves a variable number of blocks in each service round. We have found that CTL data placement has much lower buffer requirements than CDL but suffers from fragmentation during video editing. We show hybrid placement to have both advantages of high efficiency and low fragmentation. We also address the issue of admission control policies by comparing statistical and deterministic techniques. `Statistical' admission control uses statistics of the stored data to ensure that the probability of `overload' does not exceed a prespecified threshold. `Deterministic' control uses the actual stored video bit traces to regulate the number of admitted users. We consider two types of deterministic admission control: data-limit and ideal deterministic. Data-limit admission control admits users based on precomputing the total amount of data requested by all users in future service rounds. In contrast, ideal deterministic admission control not only precomputes the total amount of data requested, but also assumes we have control of data placement at the disk sector level in order to precompute the future seek and rotation times. We provide a cost/benefit analysis of the above placement/retrieval/admission control techniques and conclude that CTL and hybrid placement/retrieval techniques can reduce the total system cost by up to a factor of 3 in comparison with the strategy of padding the VBR video trace to achieve a constant data rate. For read-only systems, CTL has the lowest cost per user. For writable systems, the hybrid technique achieves a good compromise between low cost and low fragmentation. We find that all forms of deterministic admission control can outperform statistical, but the greatest gain comes from using ideal deterministic admission control. We note, however, that this admission control may be difficult to implement on standard disk controllers. Finally, we have implemented a full disk model simulator that operates 1000 times faster than the real-time disk. Results using the simulator are very close to those measured on the real disk, making the simulator useful for future experiments.

A number of applications require audio and video data. Access to such data requires continuous real-time stream flow during playback (recording). This requires scheduling access to storage devices for such data. The high volume of such streams, especially video, makes it necessary to store them using compression schemes like JPEG and MPEG. However, doing so introduces playback data rate variability which in turn leads to poor storage system utilization if playback guarantees are to be maintained. Not all applications require perfect playback, and some tardiness and discontinuity during playback, within limits of acceptable Quality of Service (QoS), is tolerated. In this paper we briefly describe solutions to two problems that arise in scheduling the retrieval of compressed streams from secondary storage. Firstly, we propose QBSCAN, a scheme which reserves I/O bandwidth based on statistical estimates of playback rate in order to improve utilization. This is achieved by incorporating the QoS which comprises the playback rate (in frames per second), the maximum (consecutive) skipped frames, and the mean time between frame skips. Secondly, we develop storage techniques specifically designed for MPEG video, to be used in conjunction with QBSCAN, that allows robust playback. This is a problem because MPEG encoding introduces inter frame dependencies which make it hard to drop frames arbitrarily. Thus, the objectives of QBSCAN are to maximize the storage system utilization, and minimize buffer requirement, while providing the needed QoS despite data rate variability and dependency. Simulation studies are used to validate the efficacy of the proposed techniques.

We present a multimedia server comprising of multiple stream controllers connected to a host (work station) I/O bus. Each stream controller manages an array of disks in which multimedia data is stored in format of network packets. When the host instructs the stream controller to deliver a multimedia file to a client, the stream controller retrieves the network packets of that file, completes the missing header/trailer fields, and forwards these packets to the network interface directly, avoiding any further involvement of the host. To avoid interference on the disks, data is interleaved across all disks connected to a stream controller in fixed play back time units. This helps reduce the jitter in the response time of the disks, and therefore, the size of the buffers needed to maintain interruption free delivery. Metadata is stored with the network packets of a video/multimedia file to enable the stream controller to autonomously fetch a complete multimedia/video file without host intervention. In a departure from traditional RAID, the stream controller simultaneously issues a set of read commands periodically, one for each active multimedia stream. Each reach command retrieves a full interleave unit from a single disk, and the set of simultaneously issued read commands are distributed across all disks.

In designing operating system support for distributed multimedia, we target three areas for improvement: reduced copying, reduced reliance on explicit kernel/user interactions, and provision of rate-based flow control. Towards these goals, we propose an architecture that includes the concept of I/O efficient buffers for reduced copying, the concept of fast system calls for low latency network access, and the concept of kernel threads for flow control. Also included is a concept called direct media streaming which is suitable for applications that require limited user processing of media data. These concepts have been implemented as an extension of SunOS 5.3 (the operating system component of Solaris 2.3). We report some experimental results on the performance of our current system.

In conventional network processing models, a number of data-copies are needed for applications to receive data from network interfaces. This causes major overhead and becomes a serious limitation in distributed multimedia applications. Therefore, several mechanisms have been proposed for reducing the number of data-copies. We emphasize that the Single Virtual address Space (SVS) OS introduces a new buffering mechanisms for this purpose. In this paper, we describe our SVS OS, which we call `Cubix (CUBe of 2-byte unIX)', with a new Access Control List protection mechanism and a new buffering mechanism, which we call `Cstreams (Continuous streams)', based on it. We emphasize that our proposed Cstreams realizes a single data-copy network architecture.

Due to statistical multiplexing in ATM networks, a large number of cells may be lost during the periods of network congestion. It is a common perception that feedback congestion control mechanisms do not work well for delay sensitive applications such as video transfer. The proposed approaches to avoid congestion in video applications are mainly based on constant bit-rate transmission. However, these schemes impose a delay in the order of a frame time. Besides, the network utilization is reduced since bandwidth allocation at peak rate is necessary. Variable bit rate (VBR) coding of video signals is more efficient both in terms of coding delay and bandwidth utilization. In this paper, we demonstrate that using credit-based flow control together with a selective cell discarding mechanism, VBR video signals coded according to the MPEG standard can be statistically multiplexed with a very high efficiency. Both cell delay and cell loss guarantees can be made while achieving a high network utilization. A throughput of up to 83 percent has been achieved with a cell loss rate of under 10^-5 and maximum end-to-end cell queuing delay of 15 milliseconds in the statistical multiplexing scenarios under consideration. Since credit-based flow control works well for data applications, its successful deployment for video applications will pave the way for an integrated congestion control protocol.

The World Wide Web (WWW) is becoming increasingly important for business, education, and entertainment. Popular web browsers make access to Internet information resources relatively easy for novice users. Simply by clicking on a link, a new page of information replaces the current one on the screen. Unfortunately however, after following a number of links, people can have difficulty remembering where they've been and navigating links they have followed. As one's collection of web pages grows and as more information of interest populates the web, effective navigation becomes an issue of fundamental importance. We are developing a prototype zooming browser to explore alternative mechanisms for navigating the WWW. Instead of having a single page visible at a time, multiple pages and the links between them are depicted on a large zoomable information surface. Pages are scaled so that the page in focus is clearly readable with connected pages shown at smaller scales to provide context. As a link is followed the new page becomes the focus and existing pages are dynamically repositioned and scaled. Layout changes are animated so that the focus page moves smoothly to the center of the display surface while contextual information provided by linked pages scales down. While our browser supports multiscale representations of existing HTML pages, we have also extended HTML to support multiscale layout within a page. This extension, Multi-Scale Markup Language, is at an early stage of development. It currently supports inclusion within a page of variable-sized dynamic objects, graphics, and other interface mechanisms from our underlying Pad++ substrate. This provides sophisticated client- side interactions, permits annotations to be added to pages, and allows page constituents to be used as independent graphical objects. In this paper, we describe our prototype web browser and authoring facilities. We show how simple extensions to HTML can support sophisticated client-side interactions. Finally, we discuss the results of preliminary user-interface testing and evaluation.