📘 Tutorial 9: Video Streaming, Adaptive Streaming, and CDNs

COMP347 (Revision 10) | TrustOpen University

📑 Table of Contents

Learning Objectives
Overview
1. Video Fundamentals and Rate–Distortion Theory
2. Adaptive Bitrate Streaming – Formal Models
3. DASH and HLS – Technical Architecture
4. Adaptive Bitrate Algorithms (Throughput, Buffer, MPC)
5. Content Delivery Networks – Routing and Caching
6. Cache Replacement Policies and CDN Performance
7. Low‑Latency Streaming and CMAF
8. Video Codecs and Compression Efficiency
Quiz
Exercises
Homework
Summary

🎯 Learning Objectives

Upon completion of this expanded tutorial, students will be able to:

Formally describe the relationship between bitrate, quality, and compression using rate–distortion theory.
Explain the end‑to‑end architecture of DASH, including MPD structure, segment templates, and the role of HTTP.
Analyse adaptive bitrate algorithms (throughput‑based, buffer‑based, and model predictive control) and their trade‑offs.
Compare CDN routing mechanisms (Anycast, DNS‑based) and caching strategies (consistent hashing, CARP).
Evaluate cache replacement policies (LRU, LFU, GreedyDual) for video workloads.
Explain the operation of low‑latency streaming using CMAF and chunked encoding.

🔭 Overview

Video streaming now dominates Internet traffic, requiring sophisticated technologies to deliver high quality at scale. This tutorial provides a university‑level, mathematically‑grounded examination of adaptive streaming and content distribution networks.

We begin with the fundamentals of video compression, introducing rate–distortion theory to formalise the trade‑off between bitrate and quality. We then dissect adaptive streaming architectures, focusing on DASH and HLS, and explore the MPD/manifest formats. The core of the tutorial covers adaptive bitrate algorithms—from simple throughput‑based switching to model predictive control (MPC)—and analyses their behaviour under varying network conditions. We then shift to CDNs, examining routing with consistent hashing, cache replacement policies (LRU, LFU, GreedyDual), and the impact of edge computing. Finally, we discuss low‑latency extensions (LL‑HLS, LL‑DASH, CMAF) and the evolving landscape of video codecs (H.264, H.265, VP9, AV1).

1. Video Fundamentals and Rate–Distortion Theory

1.1 Video Encoding and Quality Metrics

Resolution: number of pixels (e.g., 1920×1080).
Frame rate: frames per second (fps).
Bitrate: data rate (bps).
Quality metrics: PSNR (Peak Signal‑to‑Noise Ratio), SSIM (Structural Similarity Index), VMAF (Video Multi‑Method Assessment Fusion). VMAF is a perceptual metric correlated with human opinion scores.

1.2 Rate–Distortion Theory

Rate–distortion theory (Shannon) describes the fundamental trade‑off between the bitrate $ R $ and the distortion $ D $ of a compressed signal. For a Gaussian source, the rate–distortion function is:

$ R(D) = \frac{1}{2} \log_2 \left( \frac{\sigma^2}{D} \right) $

where $ \sigma^2 $ is the variance of the source. In practice, video encoders approximate the optimal curve. The R‑D curve allows a streaming client to select the bitrate that maximises quality under bandwidth constraints.

2. Adaptive Bitrate Streaming – Formal Models

2.1 Segment‑Based Streaming

The video is divided into small segments (2–10 seconds). Each segment is encoded at multiple bitrates (the "bitrate ladder"). The client selects the appropriate bitrate for each segment based on network conditions.

2.2 Buffer Model

Let $ B(t) $ be the buffer occupancy at time $ t $. The dynamics are:

$ B(t+1) = \max(0, B(t) + \text{download_rate}(t) - \text{playback_rate}(t)) $

The client aims to keep $ B(t) $ between a low threshold (to avoid rebuffering) and a high threshold (to avoid unnecessary memory usage). The optimal bitrate selection problem can be formulated as a Markov Decision Process (MDP) or a Model Predictive Control (MPC) problem.

3. DASH and HLS – Technical Architecture

3.1 DASH MPD Structure

The Media Presentation Description (MPD) is an XML document that describes:

Periods: contiguous time intervals.
Adaptation Sets: groups of representations (e.g., video, audio).
Representations: specific bitrates, resolutions, codecs.
Segments: URLs or templates for fetching segment data.

The MPD includes SegmentTemplate for dynamic URLs (e.g., video-$Number$.m4s) and SegmentList for explicit URLs.

3.2 HLS Playlist Structure

HLS uses a master playlist (.m3u8) that lists variant streams (bitrates). Each variant points to a media playlist that lists the segment URIs. HLS supports #EXT‑X‑DISCONTINUITY for codec/format changes and #EXT‑X‑KEY for encryption.

3.3 HTTP/2 Server Push for Streaming

Server push can push the next segment or the manifest to the client, reducing round‑trips. However, it is often suboptimal for video because the client may have already cached the segment or may prefer a different bitrate. HTTP/3's QUIC streams provide a more efficient way to request multiple segments concurrently.

4. Adaptive Bitrate Algorithms (Throughput, Buffer, MPC)

4.1 Throughput‑Based (Rate‑Adaptive)

Measure download speed of previous segments.
Select the highest bitrate below the measured throughput.
Problem: oscillates under variable network conditions (e.g., when throughput fluctuates).
Improvement: use a moving average or exponential smoothing (e.g., α = 0.3) to reduce noise.

4.2 Buffer‑Based (BBA)

Select bitrate based on buffer occupancy.
If buffer is high, switch up; if buffer is low, switch down.
Advantage: smooth, no throughput estimation needed.
Drawback: may underutilise bandwidth when buffer is high but bandwidth is high.

4.3 Model Predictive Control (MPC)

Uses a model of network throughput (e.g., Markov chain) and buffer dynamics.
Optimises a cost function over a horizon $ T $ (e.g., maximise quality, minimise rebuffering).
More complex but achieves near‑optimal performance.

5. Content Delivery Networks – Routing and Caching

5.1 CDN Routing Mechanisms

Anycast: BGP routes the client to the nearest edge (IP‑level). Simple and fast, but limited control.
DNS‑based: the authoritative DNS returns the edge IP based on the client's resolver location (or subnet). More granular (load, health), but subject to DNS caching.
HTTP‑based redirection: origin redirects the client to a specific edge URL (e.g., via 302). Fine‑grained but adds latency.

5.2 Consistent Hashing for Edge Routing

CDNs use consistent hashing to map a resource (URL) to a set of edge nodes. When a node is added or removed, only a fraction of keys are remapped ($ O(1/N) $), minimising cache invalidation. This is crucial for large‑scale cache clusters.

6. Cache Replacement Policies and CDN Performance

6.1 LRU (Least Recently Used)

Evicts the least recently accessed object. Works well for locality‑of‑reference workloads but may perform poorly for video workloads with sequential access (a long video segment may evict a popular short clip).

6.2 LFU (Least Frequently Used)

Evicts the least frequently accessed object. Better for popular content, but suffers from "cache pollution" by old, once‑popular content.

6.3 GreedyDual (GD) and GreedyDual‑Size (GDS)

GD uses a key value = cost + age, where age increases over time. This balances recency and frequency. GDS incorporates the object size to maximise byte‑hit ratio (evict large, less popular objects first).

6.4 Cache Hit Ratio and Performance

For a CDN, the byte hit ratio (fraction of bytes served from cache) determines the origin load and latency. Typical hit ratios for video streaming are 80–95%, depending on popularity distribution (Zipf) and cache size.

7. Low‑Latency Streaming and CMAF

7.1 Low‑Latency Extensions

LL‑HLS: uses #EXT‑X‑PART for partial segments (chunks) and #EXT‑X‑PRELOAD‑HINT to preload.
LL‑DASH: uses ServiceDescription with Latency and Production descriptors, and supports SegmentTimeline with fine‑grained updates.

7.2 CMAF (Common Media Application Format)

CMAF (ISO/IEC 23000‑19) is a container format that allows a single set of media segments to be used for both DASH and HLS. It uses fragmented MP4 (fMP4) with a single metadata track, reducing storage and encoding complexity. It also enables chunked encoding where segments are encoded and delivered in small parts to reduce latency to < 5 seconds.

8. Video Codecs and Compression Efficiency

8.1 Codec Evolution

Codec	Year	Relative Efficiency (vs H.264)	Use Case
H.264 (AVC)	2003	Baseline (1×)	Widely supported
H.265 (HEVC)	2013	~50% better	4K, UHD
VP9	2013	~40–50% better	YouTube, WebM
AV1	2018	~30–40% better than HEVC	Emerging, royalty‑free

8.2 Compression Techniques

Intra‑frame prediction: spatial redundancy (I‑frames).
Inter‑frame prediction: temporal redundancy (P‑frames, B‑frames).
Transform coding: DCT, quantisation.
Entropy coding: CABAC (Context‑Adaptive Binary Arithmetic Coding) in H.264/HEVC.

📝 Quiz: Tutorial 9

Q1: What is the fundamental trade‑off described by rate–distortion theory?

Answer

The trade‑off between bitrate (compression) and distortion (quality loss).

Q2: In the buffer model, what causes the buffer occupancy to increase?

Answer

The download rate exceeding the playback rate.

Q3: What is the purpose of the MPD in DASH?

Answer

It describes the available representations (bitrates, resolutions), segments, and their URLs.

Q4: What is the main drawback of a throughput‑based adaptive bitrate algorithm?

Answer

It can oscillate when throughput fluctuates, causing frequent bitrate switches.

Q5: What is the difference between Anycast and DNS‑based CDN routing?

Answer

Anycast uses BGP to route to the nearest edge IP; DNS‑based routing returns different IPs based on the client's resolver location.

Q6: What is consistent hashing used for in CDNs?

Answer

To map resources to edge nodes with minimal remapping when nodes are added or removed.

Q7: Which cache replacement policy is most suitable for video streaming workloads?

Answer

GreedyDual‑Size (GDS) is often best as it balances recency, frequency, and object size.

Q8: What is the CMAF format used for?

Answer

It provides a common container for DASH and HLS, enabling low‑latency streaming with chunked encoding.

Q9: Which codec offers the best compression efficiency among the commonly used ones?

Answer

AV1 offers about 30–40% better compression than HEVC.

Q10: What is the purpose of B‑frames (bi‑directional predicted frames) in video coding?

Answer

They use both past and future frames for prediction, improving compression efficiency.

Q11: What is the typical latency target for low‑latency streaming?

Answer

Less than 5 seconds, with some implementations achieving 1–2 seconds.

Q12: What is the role of the EXT‑X‑PART tag in LL‑HLS?

Answer

It specifies a partial segment (chunk) that can be delivered before the full segment is complete, reducing latency.

✏️ Exercises: Tutorial 9

Exercise 1 – Buffer Dynamics

A client has a buffer of 10 seconds. It downloads at 5 Mbps and plays at 2 Mbps. What is the net buffer change per second?

Sample Solution

Net change = download rate – playback rate = 5 – 2 = 3 Mbps. In terms of seconds of content, it downloads 5/2 = 2.5 seconds of content per second of real time, so buffer increases by 1.5 seconds per second.

Exercise 2 – MPD Interpretation

Given a DASH MPD with representations of 500k, 1500k, 4000k, and measured throughput of 3.2 Mbps. Which representation should be selected if using throughput‑based algorithm with 20% safety margin?

Sample Solution

Available throughput = 3.2 Mbps. With 20% margin, use 80%: 3.2 * 0.8 = 2.56 Mbps. Select the highest representation below 2.56 Mbps → 1500k (1.5 Mbps).

Exercise 3 – CDN Cache Hit Ratio

A CDN has a hit ratio of 85%. The average response time for a hit is 5 ms, for a miss is 150 ms. What is the average response time?

Sample Solution

Average = 0.85 * 5 + 0.15 * 150 = 4.25 + 22.5 = 26.75 ms.

Exercise 4 – Codec Comparison

If H.264 requires 6 Mbps for a certain quality, estimate the bitrate required for HEVC and AV1 for the same quality.

Sample Solution

HEVC ~50% better → 3 Mbps. AV1 ~30–40% better than HEVC → roughly 2–2.1 Mbps.

Exercise 5 – MPC Formulation

Define a simple cost function for MPC that trades off quality and rebuffering.

Sample Solution

Minimise $ J = \sum_{t=1}^{T} ( -Q_t + \lambda \cdot \text{rebuf}_t ) $, where $ Q_t $ is the quality level (e.g., bitrate) and $ \text{rebuf}_t $ is a binary indicator of rebuffering, and $ \lambda $ is a penalty weight.

Exercise 6 – Consistent Hashing

Explain how consistent hashing minimises cache invalidation when a node is added or removed.

Sample Solution

In consistent hashing, both keys and nodes are mapped to a circle. Each key is assigned to the first node clockwise. When a node is removed, only keys in its range are remapped to the next node; with $ N $ nodes, only $ 1/N $ of keys are affected.

📚 Homework: Tutorial 9

Homework 1 – DASH Client Implementation

Implement a simple DASH client in Python using a library like `dash` or `requests`. Simulate a variable bandwidth (e.g., using `tc` on Linux) and evaluate the adaptation performance.

Guidance

Measure rebuffering ratio, average bitrate, and quality switches.

Homework 2 – CDN Cost‑Benefit Analysis

Perform a cost‑benefit analysis for a video‑on‑demand service with 1 million daily users. Compare the cost of serving directly from origin (with 95th percentile bandwidth) vs using a CDN (with per‑GB pricing and cache hit ratio of 90%).

Guidance

Use realistic pricing (e.g., AWS CloudFront vs EC2 data transfer).

Homework 3 – Codec Performance Evaluation

Encode a short video (e.g., 10 seconds) using H.264, HEVC, and AV1 at multiple bitrates. Compare the VMAF scores and encoding times. Write a report on the trade‑offs.

Guidance

Use FFmpeg with appropriate codec libraries (x264, x265, libaom‑av1).

Homework 4 – Cache Replacement Policy Simulation

Simulate LRU, LFU, and GreedyDual‑Size on a trace of video requests (you can generate a Zipf distribution). Compare the byte hit ratios for different cache sizes.

Guidance

Use Python; object sizes can be drawn from a log‑normal distribution.

Homework 5 – Low‑Latency Streaming Protocol Design

Design a low‑latency streaming system for a live e‑sports event. Describe the encoding pipeline, segment duration, CDN strategy, and the client‑side buffering logic to achieve a latency of < 2 seconds.

Guidance

Use CMAF with chunked encoding, HTTP/3, and a CDN with edge computing for manifest updates.

📌 Summary

This expanded tutorial has provided a rigorous, university‑level examination of video streaming and CDNs. Key takeaways:

Rate–distortion theory formalises the trade‑off between bitrate and quality, guiding encoding decisions.
Adaptive bitrate streaming uses segment‑based delivery with client‑side algorithms (throughput, buffer, MPC) to optimise quality under variable network conditions.
DASH and HLS are the dominant adaptive streaming protocols, with MPD and playlist structures for describing media.
CDNs use routing (Anycast, DNS, consistent hashing) and caching (LRU, LFU, GreedyDual) to reduce latency and origin load.
Low‑latency extensions (LL‑HLS, LL‑DASH, CMAF) enable near‑real‑time streaming for live events.
Codec evolution (H.264 → HEVC → AV1) continues to improve compression efficiency, reducing bandwidth requirements.

Understanding these technologies is essential for building and optimising large‑scale media delivery systems.