Successive Refinement + Coded Caching

Why Successive Refinement Matters for Caching

Successive refinement (SR) encodes video as a base layer plus enhancement layers. Each layer is individually decodable; layers combine for higher quality. SR matters for caching for two reasons:

  1. Storage efficiency. Cache can store base layer of many videos; enhance on demand from server. Tradeoff: more video coverage vs per-video quality.
  2. Delivery efficiency. When users request the same video at different qualities, a base layer multicast serves all; only differential enhancements need per-user delivery.

The joint problem of SR + coded caching yields richer achievable regions than either alone. This section develops the formal theory.

Definition:

Successive Refinement Placement

SR placement strategy allocates cache fraction Ξ±β„“\alpha_\ell to layer β„“\ell, with βˆ‘β„“Ξ±β„“β‰€1\sum_\ell \alpha_\ell \leq 1. Each layer uses MAN placement with effective memory Ξ±β„“M\alpha_\ell M.

Design choice: how to split cache across layers. Options:

  • Equal split: Ξ±β„“=1/L\alpha_\ell = 1/L. Uniform quality across videos.
  • Base-heavy: Most cache for base layer. Wide coverage, low quality.
  • Top-heavy: Most cache for top layer. Narrow coverage, high quality.
  • Optimal: Driven by demand profile and QoE metric.

The split interacts with demand: if most users request HD, store more HD-layer content. The optimization is a convex program over Ξ±\boldsymbol{\alpha} once the demand distribution is known.

Theorem: Optimal Cache Allocation Across SR Layers

For multi-rate coded caching with layer bitrates {bβ„“}\{b_\ell\} and demand profile pβ„“=Pr⁑[userΒ requestsΒ level ≀ℓ]p_\ell = \Pr[\text{user requests level } \leq \ell], the optimal cache split maximizing expected QoE (under a concave QoE function of quality) is Ξ±β„“βˆ—β€…β€Š=β€…β€Špβ„“β‹…bβ„“βˆ‘β„“β€²pβ„“β€²β‹…bβ„“β€².\alpha_\ell^* \;=\; \frac{p_\ell \cdot b_\ell}{\sum_{\ell'} p_{\ell'} \cdot b_{\ell'}}. The split is weighted by popularity and bitrate.

Layers with higher popularity and higher bitrate deserve more cache. The formula is effectively "cache in proportion to expected delivery demand at each layer."

Proof
Setup

Maximize Ep[QoE(q)]\mathbb{E}_p[\text{QoE}(q)] subject to βˆ‘β„“Ξ±β„“β‰€1\sum_\ell \alpha_\ell \leq 1. QoE at level β„“\ell proportional to MAN gain at β„“\ell, which depends on Ξ±β„“M/bβ„“\alpha_\ell M / b_\ell.

Lagrangian

Apply Lagrange with multiplier Ξ»\lambda on the budget. KKT conditions yield: βˆ‚QoE/βˆ‚Ξ±β„“=Ξ»β‹…bβ„“\partial \text{QoE}/\partial \alpha_\ell = \lambda \cdot b_\ell.

Solution

Ξ±β„“βˆpβ„“β‹…bβ„“\alpha_\ell \propto p_\ell \cdot b_\ell, normalized to sum 1. β– \blacksquare

Why Convexity Matters for QoE

The QoE function is concave in quality: a unit of quality at low resolution (SD β†’ HD) is worth more than a unit at high (4K β†’ 8K). This concavity means the optimization above is a standard convex program β€” tractable and uniquely solvable.

Convexity has a design implication: the optimal split favors diminishing returns. Cache everyone's base layer (big gain) before boosting individual users' top layer (small gain). This matches the fairness intuition: a 50% QoE improvement for many users dominates a 5% improvement for a few.

Chunk-Level Placement Delivery Rate

Delivery rate vs fraction of video chunks cached per user. Coded and uncoded compared. Coded achieves MAN gain even at chunk granularity.

Parameters
20
300

Example: SR Cache Allocation for Netflix-Like Service

A streaming service has L=3L = 3 quality levels. Observed demand: 20% SD (1 Mbps), 50% HD (3 Mbps), 30% 4K (10 Mbps). Per-user cache: M=30M = 30 Mbps-seconds. Determine optimal cache split.

Solution
Weights $p_\ell b_\ell$

SD: 0.2β‹…1=0.20.2 \cdot 1 = 0.2. HD: 0.5β‹…3=1.50.5 \cdot 3 = 1.5. 4K: 0.3β‹…10=30.3 \cdot 10 = 3. Total: 4.74.7.

Optimal split

Ξ±SD=0.04\alpha_\text{SD} = 0.04, Ξ±HD=0.32\alpha_\text{HD} = 0.32, Ξ±4K=0.64\alpha_\text{4K} = 0.64.

Cache allocation

Ξ±β‹…M\alpha \cdot M: SD =1.2= 1.2 Mbps-sec; HD =9.6= 9.6; 4K =19.2= 19.2.

Operational meaning

Most cache devoted to 4K content (heavy bitrate). Only small allocation for SD. Matches intuition: 4K requests are scarce per-user but heavy in bits.

πŸŽ“CommIT Contribution(2020)

Multi-Rate Coded Caching for Successively-Refinable Content

J. Zhang, M. Moharrami, G. Caire β€” IEEE Transactions on Information Theory

The CommIT group's key contribution to video coded caching:

  1. Multi-rate framework. Extends MAN to successively- refinable content with LL quality layers.
  2. Achievable rate. R=bmax⁑RMANR = b_{\max} R_\text{MAN} per demand profile β€” preserving the 1+KΞΌ1+K\mu coded multicasting gain at each quality level.
  3. Optimal cache split. Closed-form solution proportional to pβ„“bβ„“p_\ell b_\ell weights.
  4. QoE optimization. Integrates rate-distortion with user-facing QoE metrics.

This work bridges the rate-distortion / source-coding perspective (classical Gaussian successive refinement) with the multi-user multicasting perspective (MAN). It is the canonical reference for video coded caching in the post-2020 literature.

videosuccessive-refinementcommitView Paper β†’

Common Mistake: Successive Refinement Is Not Universal

Mistake:

Applying SR analysis to any video encoder.

Correction:

Classical SR (Equitz-Cover) holds for Gaussian and some other sources. Real video encoders (H.264, HEVC) are only approximately successively refinable β€” there's a penalty from inter-layer prediction gaps.

In practice: SVC (H.264) incurs ∼10%\sim 10\% overhead vs single-layer encoding; HEVC SHVC ∼5%\sim 5\%. These are small but not zero. Analyses assuming exact SR should be interpreted as upper bounds.

Key Takeaway

Successive refinement + coded caching achieves bmax⁑⋅RMANb_{\max} \cdot R_\text{MAN} rate. Optimal cache allocation across layers is Ξ±β„“βˆ—βˆpβ„“bβ„“\alpha_\ell^* \propto p_\ell b_\ell. The convex optimization integrates rate-distortion and multicasting. CommIT Zhang- Moharrami-Caire 2020 is the foundational reference.

Video as Successively-Refinable ContentQuality-of-Experience and Chunked Delivery