<title>Minimizing start-up latency in scalable continuous media servers</title>

Shahram Ghandeharizadeh, Seon Ho Kim, Weifeng Shi, Roger ZimmermannProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 1997 · DOI

TL;DR

This paper tackles the challenge of minimizing startup latency in scalable continuous media servers, which is crucial for applications like video-on-demand. The authors introduce and analyze two novel techniques, request migration and object replication, demonstrating through analytical models and experimental evaluation that both significantly reduce startup latency, with replication proving to be more effective.

What Problem Does This Paper Address?

Continuous media servers, like those used for streaming audio and video, need to handle a large number of simultaneous users while ensuring a smooth playback experience. A key metric for user experience is "startup latency" – the time a user waits before playback begins. Traditional scalable server designs often use techniques like "striping" to distribute data across multiple disks, which increases the server's overall throughput (number of simultaneous displays). However, this striping, especially with a simple round-robin data placement, can paradoxically increase startup latency. This is because a request might have to wait for data blocks to be sequentially retrieved from different disks, leading to delays. This paper aims to solve this problem by proposing and evaluating methods to actively reduce this startup latency, making media streaming more responsive, especially for applications with short content or demanding features like fast-forward.

Methods

The paper proposes two primary techniques to minimize startup latency:

  • Request Migration: This technique involves dynamically moving active requests from "busy" groups of servers (where all time slots are occupied) to "idle" groups (with available time slots). The idea is to rebalance the load across server groups, preventing a single group from becoming a bottleneck and thus reducing the waiting time for future requests. The authors develop analytical models to quantify the impact of migration on latency and the required buffer increases.
  • Object Replication: This approach involves creating multiple copies of media objects (e.g., video clips) and strategically placing them across different disk clusters. When a user requests an object, the system can check multiple locations simultaneously, increasing the probability of finding an available slot quickly. The paper discusses how to determine the optimal number of replicas and their placement to maximize the benefit. Analytical models are developed to estimate the expected latency reduction based on the number of replicas.

Both techniques are presented as orthogonal, meaning they can potentially be used in conjunction. The authors also develop analytical models based on queuing theory to predict the expected startup latency under various conditions and then validate these models with experimental results.

Datasets

The paper does not explicitly mention using pre-existing datasets for training. Instead, it uses characteristics of real-world media content for its experimental setup:

  • CD Audio Clip Characteristics: Data on clip length and access frequency was derived from a WWW page ranking popular songs.
  • Skewed Distribution (Exponential): A synthetic distribution was used to model access frequencies, mimicking real-world scenarios where a few items are accessed much more frequently than others.

The experiments were conducted on a system called "Mitra," which is described as a scalable client-server solution. The paper does not introduce a new benchmark dataset but rather uses these characteristics to configure and evaluate their proposed techniques.

Key Insights and Ideas

  • Striping's Double-Edged Sword: While striping is essential for scalability and throughput, its simple round-robin placement can be detrimental to startup latency. This highlights a fundamental trade-off in designing high-performance media servers.
  • Replication Outperforms Migration: The experimental results consistently show that object replication is more effective than request migration in reducing startup latency, especially under high system load.
  • The Power of Proactive Placement: Replication's success stems from its proactive nature – anticipating potential bottlenecks by distributing data. Migration, while useful, is a reactive measure.
  • Latency Reduction is Crucial for Advanced Features: Minimizing startup latency isn't just about user convenience; it's a prerequisite for implementing advanced VCR-like functionalities (fast-forward, rewind) that require rapid switching between playback states.
  • Space-Latency Trade-off: Replication's effectiveness is directly tied to the amount of storage space allocated for secondary copies. There's a clear trade-off, and an optimal point exists where replication becomes superior to migration.

Key Results

  • Significant Latency Reduction: Both request migration and object replication were shown to significantly reduce average startup latency compared to a standard striping approach.
  • Replication's Superiority: Under high system utilization (97.6%), replication achieved a 62.9% reduction in startup latency, while migration achieved a 10.6% reduction.
  • Impact of System Load: The benefits of both techniques were more pronounced under high system load, where the probability of experiencing long startup delays increases.
  • Replication's Minimum Latency: With sufficient space, replication can reduce the average startup latency to approximately 0.743 seconds, which is close to the theoretical minimum for the system's cycle-based approach.
  • Analytical Models Validate Experiments: The analytical models developed by the authors closely predicted the experimental results, validating their theoretical framework.

Limitations and Future Work

Limitations:

  • Replication Space Constraint: The effectiveness of replication is limited by the available disk space for storing secondary copies.
  • Migration Buffer Overhead: Request migration can increase memory requirements due to the need for additional buffers to manage data ahead of display.
  • Rejection at High Load: At very high system utilization (97.6%), the system still rejected approximately 5% of requests, indicating that even with these optimizations, extreme loads can degrade service quality.

Future Work:

  • Tertiary Storage Integration: Extend replication techniques to incorporate tertiary storage devices, considering how accessing primary copies from slower storage impacts performance.
  • Online Replication Algorithms: Develop dynamic, online algorithms that can automatically detect "hot" (frequently accessed) objects and create secondary copies, and conversely, identify "cold" objects and delete their replicas to optimize storage.
  • Further VCR Functionality Support: Explore how these latency reduction techniques can fully enable complex VCR operations.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ghandeharizadeh1997lt,
  author = {Shahram Ghandeharizadeh and Seon Ho Kim and Weifeng Shi and Roger Zimmermann},
  title = {{\<title\>Minimizing start-up latency in scalable continuous media servers\</title\>}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {1997},
  doi = {10.1117/12.264288},
}
Figure