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.     

Constructing a video server with tertiary storage: Practice and experience

Handling a tertiary storage device, such as an optical disk library, in the framework of a disk-based stream service model, requires a sophisticated streaming model for the server, and it should consider the device-specific performance characteristics of tertiary storage. This paper discusses the design and implementation of a video server which uses tertiary storage as a source of media archiving. We have carefully designed the streaming mechanism for a server whose key functionalities include stream scheduling, disk caching and admission control. The stream scheduling model incorporates the tertiary media staging into a disk-based scheduling process, and also enhances the utilization of tertiary device bandwidth. The disk caching mechanism manages the limited capacity of the hard disk efficiently to guarantee the availability of media segments on the hard disk. The admission controller provides an adequate mechanism which decides upon the admission of a new request based on the current resource availability of the server. The proposed system has been implemented on a general-purpose operating system and it is fully operational. The design principles of the server are validated with real experiments, and the performance characteristics are analyzed. The results guide us on how servers with tertiary storage should be deployed effectively in a real environment. RID="*" ID="*" e-mail: hjcha@cs.yonsei.ac.kr     

Issues in the design of a storage server for video-on-demand

We examine issues related to the design of a storage server for video-on-demand (VOD) applications. The storage medium considered is magnetic disks or arrays of disks. We investigate disk scheduling policies, buffer management policies and I/O bus protocol issues. We derive the number of sessions that can be supported from a single disk or an array of disks and determine the amount of buffering required to support a given number of users. Furthermore, we propose a scheduling mechanism for disk accesses that significantly lowers the buffer-size requirements in the case of disk arrays. The buffer size required under the proposed scheme is independent of the number of disks in the array. This property allows for striping video content over a large number of disks to achieve higher concurrency in access to a particular video object. This enables the server to satisfy hundreds of independent requests to the same video object or to hundreds of different objects while storing only one copy of each video object. The reliability implications of striping content over a large number of disks are addressed and two solutions are proposed. Finally, we examine various policies for dealing with disk thermal calibration and the placement of videos on disks and disk arrays.     

Design and analysis of a video-on-demand server

The availability of high-speed networks, fast computers and improved storage technology is stimulating interest in the development of video on-demand services that provide facilities similar to a video cassette player (VCP). In this paper, we present a design of a video-on-demand (VOD) server, capable of supporting a large number of video requests with complete functionality of a remote control (as used in VCPs), for each request. In the proposed design, we have used an interleaved storage method with constrained allocation of video and audio blocks on the disk to provide continuous retrieval. Our storage scheme interleaves a movie with itself (while satisfying the constraints on video and audio block allocation. This approach minimizes the starting delay and the buffer requirement at the user end, while ensuring a jitter-free display for every request. In order to minimize the starting delay and to support more non-concurrent requests, we have proposed the use of multiple disks for the same movie. Since a disk needs to hold only one movie, an array of inexpensive disks can be used, which reduces the overall cost of the proposed system. A scheme supported by our disk storage method to provide all the functions of a remote control such as “fast-forwarding”, “rewinding” (with play “on” or “off”), “pause” and “play” has also been discussed. This scheme handles a user request independent of others and satisfies it without degrading the quality of service to other users. The server design presented in this paper achieves the multiple goals of high disk utilization, global buffer optimization, cost-effectiveness and high-quality service to the users.     

Using rotational mirrored declustering for replica placement in a disk-array-based video server

In a video-on-demand (VOD) environment, disk arrays are often used to support the disk bandwidth requirement. This can pose serious problems on available disk bandwidth upon disk failure. In this paper, we explore the approach of replicating frequently accessed movies to provide high data bandwidth and fault tolerance required in a disk-array-based video server. An isochronous continuous video stream imposes different requirements from a random access pattern on databases or files. Explicitly, we propose a new replica placement method, called rotational mirrored declustering (RMD), to support high data availability for disk arrays in a VOD environment. In essence, RMD is similar to the conventional mirrored declustering in that replicas are stored in different disk arrays. However, it is different from the latter in that the replica placements in different disk arrays under RMD are properly rotated. Combining the merits of prior chained and mirrored declustering methods, RMD is particularly suitable for storing multiple movie copies to support VOD applications. To assess the performance of RMD, we conduct a series of experiments by emulating the storage and delivery of movies in a VOD system. Our results show that RMD consistently outperforms the conventional methods in terms of load-balancing and fault-tolerance capability after disk failure, and is deemed a viable approach to supporting replica placement in a disk-array-based video server.     

An Internet-based negotiation server for e-commerce

This paper describes the design and implementation of a replicable, Internet-based negotiation server for conducting bargaining-type negotiations between enterprises involved in e-commerce and e-business. Enterprises can be buyers and sellers of products/services or participants of a complex supply chain engaged in purchasing, planning, and scheduling. Multiple copies of our server can be installed to complement the services of Web servers. Each enterprise can install or select a trusted negotiation server to represent his/her interests. Web-based GUI tools are used during the build-time registration process to specify the requirements, constraints, and rules that represent negotiation policies and strategies, preference scoring of different data conditions, and aggregation methods for deriving a global cost-benefit score for the item(s) under negotiation. The registration information is used by the negotiation servers to automatically conduct bargaining type negotiations on behalf of their clients. In this paper, we present the architecture of our implementation as well as a framework for automated negotiations, and describe a number of communication primitives which are used in the underlying negotiation protocol. A constraint satisfaction processor (CSP) is used to evaluate a negotiation proposal or counterproposal against the registered requirements and constraints of a client company. In case of a constraint violation, an event is posted to trigger the execution of negotiation strategic rules, which either automatically relax the violated constraint, ask for human intervention, invoke an application, or perform other remedial operations. An Event-Trigger-Rule (ETR) server is used to manage events, triggers, and rules. Negotiation strategic rules can be added or modified at run-time. A cost-benefit analysis component is used to perform quantitative analysis of alternatives. The use of negotiation servers to conduct automated negotiation has been demonstrated in the context of an integrated supply chain scenario. Received: 30 October 2000 / Accepted: 12 January 2001 Published online: 2 August 2001     

Disk placement for arbitrary-rate playback in an interactive video server

Multimedia data, especially continuous media including video and audio objects, represent a rich and natural stimulus for humans, but require large amount of storage capacity and real-time processing. In this paper, we describe how to organize video data efficiently on multiple disks in order to support arbitrary-rate playback requested by different users independently. Our approach is to segment and decluster video objects and to place the segments in multiple disks using a restricted round-robin scheme, called prime round-robin (PRR). Its placement scheme provides uniform load balance of disks for arbitrary retrieval rate as well as normal playback, since it eliminates hot spots. Moreover, it does not require any additional disk bandwidth to support VCR-like operations such as fast-forward and rewind. We have studied the various effects of placement and retrieval schemes in a storage server by simulation. The results show that PRR offers even disk accesses, and the failure in reading segment by deadline occurs only at the beginning of new operations. In addition, the number of users admitted is not decreased, regardless of arbitrary-rate playback requests.     

Advanced data processing in KRISYS: modeling concepts, implementation techniques, and client/server issues

The increasing power of modern computers is steadily opening up new application domains for advanced data processing such as engineering and knowledge-based applications. To meet their requirements, concepts for advanced data management have been investigated during the last decade, especially in the field of object orientation. Over the last couple of years, the database group at the University of Kaiserslautern has been developing such an advanced database system, the KRISYS prototype. In this article, we report on the results and experiences obtained in the course of this project. The primary objective for the first version of KRISYS was to provide semantic features, such as an expressive data model, a set-oriented query language, deductive as well as active capabilities. The first KRISYS prototype became completely operational in 1989. To evaluate its features and to stabilize its functionality, we started to develop several applications with the system. These experiences marked the starting point for an overall redesign of KRISYS. Major goals were to tune KRISYS and its query-processing facilities to a suitable client/server environment, as well as to provide elaborate mechanisms for consistency control comprising semantic integrity constraints, multi-user synchronization, and failure recovery. The essential aspects of the resulting client/server architecture are embodied by the client-side data management needed to effectively support advanced applications and to gain the required system performance for interactive work. The project stages of KRISYS properly reflect the essential developments that have taken place in the research on advanced database systems over the last years. Hence, the subsequent discussions will bring up a number of important aspects with regard to advanced data processing that are of significant general importance, as well as of general applicability to database systems. Received June 18, 1996 / Accepted November 11, 1997     

Constant time permutation: an efficient block allocation strategy for variable-bit-rate continuous media data

To provide high accessibility of continuous-media (CM) data, CM servers generally stripe data across multiple disks. Currently, the most widely used striping scheme for CM data is round-robin permutation (RRP). Unfortunately, when RRP is applied to variable-bit-rate (VBR) CM data, load imbalance across multiple disks occurs, thereby reducing overall system performance. In this paper, the performance of a VBR CM server with RRP is analyzed. In addition, we propose an efficient striping scheme called constant time permutation (CTP), which takes the VBR characteristic into account and obtains a more balanced load than RRP. Analytic models of both RRP and CTP are presented, and the models are verified via trace-driven simulations. Analysis and simulation results show that CTP can substantially increase the number of clients supported, though it might introduce a few seconds/minutes of initial delay. Received June 9, 1998 / Accepted January 21, 1999     

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.     

Energy-performance trade-offs for spatial access methods on memory-resident data

The proliferation of mobile and pervasive computing devices has brought energy constraints into the limelight. Energy-conscious design is important at all levels of system architecture, and the software has a key role to play in conserving battery energy on these devices. With the increasing popularity of spatial database applications, and their anticipated deployment on mobile devices (such as road atlases and GPS-based applications), it is critical to examine the energy implications of spatial data storage and access methods for memory resident datasets. While there has been extensive prior research on spatial access methods on resource-rich environments, this is, perhaps, the first study to examine their suitability for resource-constrained environments. Using a detailed cycle-accurate energy estimation framework and four different datasets, this paper examines the pros and cons of three previously proposed spatial indexing alternatives from both the energy and performance angles. Specifically, the Quadtree, Packed R-tree, and Buddy-Tree structures are evaluated and compared with a brute-force approach that does not use an index. The results show that there are both performance and energy trade-offs between the indexing schemes for the different queries. The nature of the query also plays an important role in determining the energy-performance trade-offs. Further, technological trends and architectural enhancements are influencing factors on the relative behavior of the index structures. The work in the query has a bearing on how and where (on a mobile client or/and on a server) it should be performed for performance and energy savings. The results from this study will be beneficial for the design and implementation of embedded spatial databases, accelerating their deployment on numerous mobile devices. Received: November 11, 2001 / Accepted: March 12, 2002 Published online: November 14, 2002 This paper is a significantly extended version of preliminary work that appeared in the Proceedings of the Very Large Databases (VLDB) 2001 Conference. The extensions include (i) a comparison of indexing alternatives carrying out the operations in a brute-force manner; (ii) observations showing that datasets do play a role in power consumption; (iii) architectural solutions to address the cache and memory hotspots for energy; and (iv) benefits when off-loading the work to a server over a wireless medium compared to doing everything on the handheld device.     

Implementing the CORBA GIOP in a high-performance object request broker environment

The success of the Object Management Group's General Inter-ORB Protocol (GIOP) is leading to the desire to deploy GIOP in an ever-wider range of application areas, many of which are significantly more demanding than traditional areas in terms of performance. The well-known performance limitations of present day GIOP-based object request brokers (ORBs) are therefore increasingly being seen as a problem. To help address this problem, this paper discusses a GIOP implementation which has high performance and quality of service support as explicit goals. The implementation, which is embedded in a research ORB called Gopi, is modular and extensible in nature and includes novel optimization techniques which should be separately portable to other ORB environments. This paper focuses on the message protocol aspects of Gopi's GIOP implementation; higher layer issues such as marshalling and operation demultiplexing are not covered in detail. Figures are provided which position Gopi's GIOP performance against comparable ORBs. The paper also discusses some of the design decisions that have been made in the development of the GIOP protocol in the light of our implementation experience. Received: May 2000 / Accepted: December 2000     

An experimental evaluation of OCR text representations for learning document classifiers

In the literature, many feature types are proposed for document classification. However, an extensive and systematic evaluation of the various approaches has not yet been done. In particular, evaluations on OCR documents are very rare. In this paper we investigate seven text representations based on n-grams and single words. We compare their effectiveness in classifying OCR texts and the corresponding correct ASCII texts in two domains: business letters and abstracts of technical reports. Our results indicate that the use of n-grams is an attractive technique which can even compare to techniques relying on a morphological analysis. This holds for OCR texts as well as for correct ASCII texts. Received February 17, 1998 / Revised April 8, 1998     

On periodic resource scheduling for continuous-media databases

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

ScholOnto: an ontology-based digital library server for research documents and discourse

The internet is rapidly becoming the first place for researchers to publish documents, but at present they receive little support in searching, tracking, analysing or debating concepts in a literature from scholarly perspectives. This paper describes the design rationale and implementation of ScholOnto, an ontology-based digital library server to support scholarly interpretation and discourse. It enables researchers to describe and debate via a semantic network the contributions a document makes, and its relationship to the literature. The paper discusses the computational services that an ontology-based server supports, alternative user interfaces to support interaction with a large semantic network, usability issues associated with knowledge formalisation, new work practices that could emerge, and related work. Published online: 22 September 2000     

An experimental analysis of digital video library servers

Much work on video servers has concentrated on movies on demand, in which a relatively small number of titles are viewed and users are given basic VCR-style controls. This paper concentrates on analyzing video server performance for non-linear access applications. In particular, we study two non-linear video applications: video libraries, in which users select from a large collection of videos and may be interested in viewing only a small part of the title; and video walk-throughs, in which users can move through an image-mapped representation of a space. We present a characterization of the workloads of these applications. Our simulation studies show that video server architectures developed for movies on demand can be adapted to video library usage, though caching is less effective and the server can support a smaller user population for non-linear video applications. We also show that video walk-throughs require extremely large amounts of RAM buffering to provide adequate performance for even a small number of users.     

Empirical evaluation of a calibration chart detector

In this paper, we systematically assess the performance of an automatic calibration chart detector. Through simulation we establish the optimal set of control parameters and the rate of successful detection as a function of pose. We validate the simulation results on real images taken from a camera mounted on a robot arm. The results confirm the utility of such simulation studies. The feedback obtained suggested a number of modifications for the chart detection system, which led to a significant improvement in performance. In particular, the chart design was changed to accommodate wider range and better stability in detection. Received: 16 December 1999 / Accepted: 15 October 2000     

Real-time CAM-based Hough transform algorithm and its performance evaluation

Abstract. This paper proposes a highly parallel Hough transform algorithm for real-time straight-line extraction and its hardware implementation on a content-addressable memory (CAM). To achieve high-speed processing, incrementation for voting, which composes the Hough transform, and calculations for coordinate updating are carried out for the every scan line, not every edge pixel, and extracting maxima in Hough space is executed by parallel comparing. Moreover, variously weighted voting achieves more accurate line extraction in spite of the quantization error and noise in the image space. In the implementation, the CAM acts as a PE (processing-element) array that effectively performs highly parallel processing for the Hough transform and also as a memory for two-dimensional Hough space, and both voting and peak extraction are directly executed by the CAM. Evaluations of CAM hardware size, processing time and the accuracy of line extraction show that a real-time and high-resolution Hough transform for a 256256 picture can be achieved using a single CAM chip with current VLSI technology. This CAM-based Hough transform algorithm promises to be an important step towards the realization of a real-time and compact image-understanding system. Received: 15 August 1998 / Accepted: 15 March 2000