Periodic broadcast and patching services: implementation, measurement, and analysis in an internet streaming video testbed

Michael K. Bradshaw, Bing Wang, Lixin Gao, James F. Kurose, Prashant J. Shenoy, Donald F. Towsley, Subhabrata SenACM Multimedia 2001 · DOI

TL;DR

This paper presents the design, implementation, and analysis of a streaming video testbed that supports periodic broadcast and patching. The authors demonstrate that their system can handle high client request rates and network loads, while also highlighting the critical role of application-level caching, particularly with LFU policies, in reducing server overhead and improving performance.

What Problem Does This Paper Address?

Delivering high-quality streaming video over the internet presents significant challenges due to the substantial server and network resources required. Traditional unicast streaming struggles to scale efficiently for a large number of clients. To address this, researchers have proposed techniques like periodic broadcast and patching, which leverage multicast and client buffering to reduce load and guarantee bounded startup latency. However, much of the prior work focused on theoretical algorithms and simulations, often abstracting away practical implementation issues like signaling overhead, OS interactions, and real-world network dynamics. This paper aims to bridge this gap by building and evaluating a practical testbed to understand the real-world performance and challenges of these advanced streaming techniques.

Methods

The core of this work is the development of a flexible streaming video testbed comprising a Linux-based application-level video server and both Linux and Windows clients. The server architecture is divided into a Server Control Engine (SCE) for handling client requests and generating schedules, and a Server Data Engine (SDE) for retrieving and transmitting video data.

Key methodological aspects include:

  • Periodic Broadcast: Implemented using the GDB segmentation scheme, where videos are divided into segments broadcast repeatedly on different multicast addresses. Segment lengths are varied to explore trade-offs between startup latency and bandwidth.
  • Patching: Implemented using a threshold-based controlled multicast scheme. The first client receives a full stream, while subsequent clients arriving within a threshold time receive only the missing data via unicast, reducing server load.
  • Application-Level Caching: The server employs an application-level cache above the OS's built-in caching. The paper investigates the impact of different caching policies, specifically Least Recently Used (LRU) and Least Frequently Used (LFU), on server read load.
  • Measurement and Analysis: The testbed allows for detailed measurement of various performance metrics, including server read load (SRL), server network throughput (SNT), deadline conformance percentage (DCP), client frame interarrival time (CFIT), and reception schedule latency (RSL).

Datasets

The paper uses sample videos for experiments, specifically:

  • Blade1 (MPEG-1): 12 minutes, 30 fps.
  • Blade2 (MPEG-1): 15 minutes, 30 fps.
  • Demo (MPEG-2): 2.7 minutes, 30 fps.

These videos are described by their format, length, frame rate, bandwidth, file size, and number of RTP packets. The paper also defines different "GDB segmentation schemes" (e.g., 3-GDB, 10-GDB, 30-GDB) for the Blade2 video, which vary the lengths of the initial segments and thus the number of segments and multicast addresses used. No new benchmarks were introduced; rather, the existing videos were used to evaluate the implemented algorithms.

Key Insights and Ideas

  • Practicality of Periodic Broadcast and Patching: The testbed demonstrates that these advanced streaming techniques are not just theoretical constructs but can be implemented and function effectively in a real-world environment, supporting high client loads and bandwidth demands.
  • The Crucial Role of Application-Level Caching: The paper strongly emphasizes that application-level caching is vital for reducing the load on the underlying server operating system and its disks. Without it, the OS can become overloaded as the number of concurrent streams increases.
  • LFU Outperforms LRU: The Least Frequently Used (LFU) caching policy consistently outperforms the more standard Least Recently Used (LRU) policy, especially for periodic broadcast and patching. LFU significantly reduces the server read load, offering smoother performance gains as cache size increases.
  • LFU's Optimality: The paper presents a theorem suggesting LFU is an optimal caching policy for these specific streaming schemes under certain conditions, minimizing average server read load.
  • Startup Latency vs. Performance Trade-offs: The choice of initial segment length in periodic broadcast affects client startup latency but also influences server read load, highlighting a design trade-off.
  • Synchronization Can Cause Bursty Traffic: A key finding is that when multiple periodic broadcast streams have their schedules synchronized, it can lead to significant bursts of network traffic. Staggering schedules can smooth this out, reducing the need for provisioning high peak throughput.
  • Startup Delay of 1.5 Seconds is Sufficient: For loaded LAN environments, an initial client startup delay of less than 1.5 seconds is shown to be adequate for handling signaling and absorbing jitter, enabling continuous playback.

Key Results

  • Server Throughput: The server can handle a client request rate of 600 requests per minute for periodic broadcast, returning schedule information and missing very few data transmission deadlines.
  • Network Utilization: Under patching, the server can nearly saturate a 100Mbps network link with patched-in clients while still meeting deadlines.
  • Server Read Load Reduction: Application-level caching, particularly with LFU, dramatically reduces the server read load. For example, with 48MB of cache per video, the expected SRL for patching drops from 18.7Mbps to 11Mbps.
  • Deadline Conformance: The system consistently achieves a Deadline Conformance Percentage (DCP) of over 99% across various scenarios, indicating reliable data delivery.
  • Client Frame Interarrival Time (CFIT): CFITs are generally within acceptable ranges, with variations explained by traffic load. For instance, 10-GDB and 30-GDB schemes show slightly higher variance than 3-GDB due to heavier network traffic.
  • Startup Latency: A startup delay of less than 1.5 seconds is sufficient for clients to receive all frames before playback.

Limitations and Future Work

  • Linux as Non-Real-Time OS: The authors acknowledge that running on a non-real-time OS like Linux can lead to timing irregularities, though their SDE implementation largely mitigates this.
  • Homogeneous Video Population: Experiments often used multiple copies of the same video to explore system overheads under a homogeneous load. Future work could explore mixed video types.
  • Network Bottleneck: For patching, the 100Mbps Ethernet link was identified as a bottleneck, suggesting that performance could be further improved with higher bandwidth networks.
  • Future Work: The authors are developing a network proxy server testbed to explore proxy-based techniques for efficient, high-quality streaming video delivery over best-effort IP networks. They also suggest that careful consideration of caching schemes and buffer sizes is crucial for optimizing the crossover point between periodic broadcast and patching performance.

Summary updated

BibTeX
@inproceedings{bradshaw2001periodic,
  author = {Michael K. Bradshaw and Bing Wang and Lixin Gao and James F. Kurose and Prashant J. Shenoy and Donald F. Towsley and Subhabrata Sen},
  title = {{Periodic broadcast and patching services: implementation, measurement, and analysis in an internet streaming video testbed}},
  booktitle = {ACM Multimedia},
  year = {2001},
  doi = {10.1145/500141.500184},
}
Figure