18632465
Automatic Recovery from Disk Failure in Continuous-Media Servers
Continuous-media (CM) servers have been around for some years. Apart from server capacity, another important issue in the deployment of CM servers is reliability. This study investigates rebuild algorithms for automatically rebuilding data stored in a failed disk into a spare disk. Specifically, a block-based rebuild algorithm is studied with the rebuild time and buffer requirement modeled. A buffer-sharing scheme is then proposed to eliminate the additional buffers needed by the rebuild process. To further improve rebuild performance, a track-based rebuild algorithm that rebuilds lost data in tracks is proposed and analyzed. Results show that track-based rebuild, while it substantially outperforms block-based rebuild, requires significantly more buffers (17-135 percent more) even with buffer sharing. To tackle this problem, a novel pipelined rebuild algorithm is proposed to take advantage of the sequential property of track retrievals to pipeline the reading and writing processes. This pipelined rebuild algorithm achieves the same rebuild performance as track-based rebuild, but reduces the extra buffer requirement to insignificant levels (0.7-1.9 percent). Numerical results computed using models of five commercial disk drives demonstrate that automatic rebuild of a failed disk can be done in a reasonable amount of time, even at relatively high server utilization (e.g., less than 1.5 hours at 90 percent utilization).
9924413
On a unified architecture for video-on-demand services
Current video-on-demand (VoD)) systems can be classified into two categories: 1) true-Voll) (TVoD) and 2) near-VoD (NVod)). TVoD systems allocate a dedicated channel for every user to achieve short response times so that the user can select what video to play, when to play it, and perform interactive VCR-like controls at will. By contrast, NVoD systems transmit videos repeatedly over multiple broadcast or multicast channels to enable multiple users to share a single video channel so that system cost can be substantially reduced. The tradeoffs are limited video selections, fixed playback schedule, and limited or no interactive control. TVoD systems can be considered as one extreme where service quality is maximized, while NVoD systems can be considered as the other extreme where system cost is minimized. This paper proposes a novel architecture called Unified VoD) (UVoD) that can be configured to achieve cost-performance tradeoff anywhere between the two extremes (i.e., TVoD and NVoD). Assuming that a video client can concurrently receive two video channels and has local buffers for caching a portion of the video data, the proposed UVoD architecture can achieve significant performance gains (e.g., 400% more capacity for a 500-channel system) over TVoD under the same latency constraint. This paper presents the UVoD architecture, establishes a performance model, and analyzes UVoD's performance via numerical and simulation results.
7513516
A monotonic-decreasing rate scheduler for variable-bit-rate video streaming
Variable-bit-rate (VBR) encoded videos can provide a more consistent visual quality than constant-bit-rate (CBR) encoded videos. However, the long-range bit-rate variations in VBR videos make it difficult to efficiently provide quality-of-service control in a video-on-demand system. Existing scheduling algorithms such as Optimal Smoothing, which requires both downward and upward bandwidth reallocations to adapt to the video bit-rate variations, simply cannot guarantee video delivery in networks with mixed video and data traffic. This study tackles this limitation by investigating a new scheduling algorithm with monotonic-decreasing rate allocations for scheduling video data transmissions. By eliminating upward bandwidth reallocations, the proposed scheduler can guarantee video delivery even in the presence of other data traffic in the same network. Moreover, results show that the proposed scheduler can achieve such performance guarantee without tradeoff in performance or resource requirements. This work presents this new monotonic-decreasing rate scheduler, analyzes its fundamental properties, and evaluates its performance using a large number of real-world VBR video traces (274 DVD movies) in extensive trace-driven simulations.
2177844
Design, performance analysis, and implementation of a super-scalar video-on-demand system
Despite the availability of video-on-demand (VoD) services in a number of cities around the world, large-scale deployment of VoD services in a metropolitan area is still economically impractical. This study presents a novel super-scalar architecture for building very large-scale and efficient VoD systems. The proposed architecture combines the use of static multicast, dynamic multicast, and intelligent client-side caching to vastly reduce server and network resource requirement. Moreover, in sharp contrast to conventional VoD systems where the system cost increases at least linearly with the system scale, the proposed architecture becomes more efficient as the system scales up and can ultimately be scaled up to serve any number of users while still keeping the startup latency short. This paper presents this new architecture, proposes methods to support interactive playback controls without the need for additional server or client resources, and derives an approximate performance model to relate the startup latency with other system parameters. The performance model is validated using simulation and the architecture is evaluated under various system settings. Lastly, a system implementation is presented and benchmarking results obtained to further verify the architecture, the performance model, and the simulation results.
52853952
Adaptive acknowledgment scheme for efficient error control in ATM clustering system
An ATM clustering system is a kind of workstation clusters over an ATM network. Such a system can be used as a distributed database server which requires reliable data delivery. This paper proposes an error recovery scheme at the transport layer for reliable data transfers with high throughput in the ATM clustering system. For such data transfers, acknowledgments are sent periodically as well as at the detection of packet losses. To be efficient the periods of acknowledgments for the scheme are adaptively varied depending on,whether current transfer is either in error-free phase or in an error recovery phase. The design and performance evaluation of the error recovery scheme is presented with a set of parameter values to achieve the best performance. The results show that the proposed scheme operates correctly and efficiently for the ATM clustering system. The throughput performance of the proposed scheme is superior to the SSCOP (service specific connection oriented protocol) regardless of packet loss rates.
2077132
Continuous query processing in data streams using duality of data and queries
Recent data stream systems such as TelegraphCQ have employed the well-known property of duality between data and queries. In these systems, query processing methods are classified into two dual categories -- data-initiative and query-initiative -- depending on whether query processing is initiated by selecting a data element or a query. Although the duality property has been widely recognized, previous data stream systems do not fully take advantages of this property since they use the two dual methods independently: data-initiative methods only for continuous queries and query-initiative methods only for ad-hoc queries. We contend that continuous query processing can be better optimized by adopting an approach that integrates the two dual methods. Our primary contribution is based on the observation that spatial join is a powerful tool for achieving this objective. In this paper, we first present a new viewpoint of transforming the continuous query processing problem to a multi-dimensional spatial join problem. We then present a continuous query processing algorithm based on spatial join, which we name Spatial Join CQ. This algorithm processes continuous queries by finding the pairs of overlapping regions from a set of data elements and a set of queries, both defined as regions in the multi-dimensional space. The algorithm achieves the advantages of the two dual methods simultaneously. Experimental results show that the proposed algorithm outperforms earlier algorithms by up to 36 times for simple selection continuous queries and by up to 7 times for sliding window join queries.
17546848
Analysis of Fuzzy Operators for High Quality Information Retrieval
Kim, M.H., J.H. Lee and Y.J. Lee, Analysis of fuzzy operators for high quality information retrieval. Information Processing Letters 46 (1993) 251-256. It has been argued that the conventional fuzzy set model based on the MIN and MAX operators is not appropriate for a model of information retrieval systems due to the properties of the MIN and MAX operators adverse to retrieval effectiveness. In this paper we investigate the behavioral aspects of various fuzzy operators and address the properties which are important in achieving high quality document rankings. We then present the fuzzy set model based on positively compensatory operators, which provides higher retrieval effectiveness than the conventional fuzzy set model. It is also described that the behavior of the proposed fuzzy set model almost coincides with that of the extended boolean model.
207320410
On fast supervised learning for normal mixture models with missing information
It is an important research issue to deal with mixture models when missing values occur in the data. In this paper, computational strategies using auxiliary indicator matrices are introduced for efficiently handling mixtures of multivariate normal distributions when the data are missing at random and have an arbitrary missing data pattern, meaning that missing data can occur anywhere. We develop a novel EM algorithm that can dramatically save computation time and be exploited in many applications, such as density estimation, supervised clustering and prediction of missing values. In the aspect of multiple imputations for missing data, we also offer a data augmentation scheme using the Gibbs sampler. Our proposed methodologies are illustrated through some real data sets with varying proportions of missing values.
45872187
Parallel Programming with Polaris
Parallel programming tools are limited, making effective parallel programming difficult and cumbersome. Compilers that translate conventional sequential programs into parallel form would liberate programmers from the complexities of explicit, machine oriented parallel programming. The paper discusses parallel programming with Polaris, an experimental translator of conventional Fortran programs that target machines such as the Cray T3D.