Ferkans — Interactive Telecom Tutor

Asymptotic Theory Meets Finite File Sizes

The MAN rate formula $R^*(M) = K(1-\mu)/(1+K\mu)$ is an asymptotic result, proven as file size $F \to \infty$ . For finite $F$ :

Subpacketization overhead. Each file must be split into $\binom{K}{t}$ subfiles; indexing and header per subfile consume space.
Error probability. Practical codes have non-zero decoding error; the rate achievable at error $\varepsilon$ exceeds the asymptotic limit.
Quantization and rounding. For non-integer $t$ , practical schemes round to nearest integer $t$ ; rounding increases rate.

The finite-blocklength (FB) regime is where theory meets practice. Understanding FB penalties is critical for realistic deployment assessments.

Theorem: Finite-Blocklength Rate Penalty

For coded caching with file size $F$ bits, cache size $M$ , $K$ users, and target error probability $\varepsilon$ , the achievable rate is bounded by $R_{F}(M, \varepsilon) \;\leq\; R^*_\infty(M) \cdot \left(1 + \mathcal{O}\!\left(\sqrt{\binom{K}{t}/F}\right) + \mathcal{O}\!\left(\sqrt{\log(1/\varepsilon)/F}\right)\right).$ Penalties vanish as $F \to \infty$ . For $F$ comparable to $\binom{K}{t}$ or smaller: significant penalty.

Two penalties: subpacketization $(1/\sqrt{F/\binom{K}{t}})$ and error-probability $(1/\sqrt{F})$ . Both scale as inverse square root of $F$ — standard finite-blocklength behavior.

Proof

Subpacketization penalty

$\binom{K}{t}$ subfiles, each of size $F/\binom{K}{t}$ . Header per subfile: $O(\log \binom{K}{t})$ . Total overhead: $O(\log \binom{K}{t} \binom{K}{t}/F)$ .

Error probability penalty

For target $\varepsilon$ : add $\sqrt{V \cdot \log(1/\varepsilon) / F}$ where $V$ is a channel dispersion constant.

Combined

Sum as dominant term: penalty $\sim \sqrt{\binom{K}{t}/F}$ when $\binom{K}{t}$ is small. When $\binom{K}{t}$ is large: subpacketization dominates. $\blacksquare$

Finite-Blocklength Rate Penalty vs File Size

Achievable rate vs file size. Penalty significant for small $F$ , asymptotically zero for large $F$ . Crossover at $F \approx \binom{K}{t}$ in bits.

Parameters

Users K10

Practical Consequences of Finite Blocklength

The finite-blocklength analysis has concrete implications:

Small files don't benefit much. A 10 KB web asset has $F = 8 \times 10^4$ bits. For $K = 50$ , $t = 10$ : $\binom{50}{10} \approx 10^{10}$ — the subpacketization requirement dwarfs $F$ . No coded gain possible.
Large files benefit. A 1 GB video chunk: $F = 8 \times 10^9$ . Same $\binom{K}{t}$ : plenty of room. Full gain achievable.
Trade off $K$ for $F$ . If file size is fixed, increasing $K$ drives $\binom{K}{t}$ up, consuming file budget. Hence the emphasis on small $K$ in practice.
PDAs (Ch 14) ease this. Polynomial-subpacketization schemes make $\binom{K}{t}$ $\to K^c$ for small $c$ . Reduces FB penalty for small files.

Deployment guidance: apply coded caching to videos (large files), not tiny web assets.

Example: Video vs Web: FB Analysis

Compare FB penalties for $K = 30$ , $\mu = 0.2$ : (i) video chunks (5 MB each), (ii) web assets (10 KB each).

Solution

Parameters

$t = K\mu = 6$ . $\binom{30}{6} = 593775$ subfiles.

Video chunks

$F = 5$ MB $= 4 \times 10^7$ bits. Per-subfile: $4 \times 10^7 / 6 \times 10^5 \approx 67$ bits. Too small — FB penalty severe.

Chunked differently

Reduce $K$ to 10: $\binom{10}{2} = 45$ subfiles. Per-subfile: $4 \times 10^7 / 45 \approx 10^6$ bits. Workable.

Web assets

$F = 10$ KB $= 8 \times 10^4$ bits. Per-subfile: $\sim 0.1$ bit. No coded gain possible.

Conclusion

Video at practical $K \leq 20$ : good. Web at any $K$ : bad. Explains why production video CDNs are coded-caching candidates; web asset CDNs are not.

,

Theorem: PDA Reduces Finite-Blocklength Penalty

For a Placement Delivery Array (PDA) scheme with subpacketization $O(K^c)$ for constant $c$ , the finite-blocklength penalty is reduced to $\mathcal{O}(\sqrt{K^c/F})$ — polynomial in $K$ rather than exponential.

PDAs avoid $\binom{K}{t}$ subpacketization in exchange for a slightly reduced multicasting gain. The net effect on FB performance is dramatic for practical $K \geq 20$ .

Proof

PDA subpacketization

Graph-coloring-based delivery gives $O(K^c)$ subfiles instead of $\binom{K}{t}$ .

FB scaling

Subpacketization penalty: $O(\sqrt{K^c/F})$ . Polynomial decay; practically feasible for all meaningful $F, K$ .

Rate cost

PDA rate slightly worse than MAN's (factor 2 in worst case). Tradeoff: rate vs subpacketization.

Combined

At fixed $F$ : PDA achieves a usable rate; MAN fails to achieve its theoretical rate due to FB. PDAs practically "win" for deployable sizes.

Common Mistake: Asymptotic Rate Is Not Practically Achievable Below Threshold

Mistake:

Using the MAN asymptotic rate as the benchmark for practical performance without checking $F \gg \binom{K}{t}$ .

Correction:

The MAN formula is an upper bound on practically achievable rate in the finite-blocklength regime. For small $F$ or large $K$ , the achievable rate can be significantly higher than MAN's asymptotic value.

Always check: is $F \gg \binom{K}{t}$ ? If yes, MAN is approached. If no, use finite-blocklength analysis or PDA-based schemes.

Key Takeaway

Finite-blocklength penalties matter in practice. For small files or large $K$ , MAN's asymptotic gain is not achievable. PDA schemes (Ch 14) mitigate this. Video (large files) is the practical sweet spot; web assets (small files) are not. Fully characterizing the FB coded-caching capacity is an open problem with practical importance.

Finite-Blocklength Coded Caching

Asymptotic Theory Meets Finite File Sizes

Theorem: Finite-Blocklength Rate Penalty

Subpacketization penalty

Error probability penalty

Combined

Finite-Blocklength Rate Penalty vs File Size

Parameters

Practical Consequences of Finite Blocklength

Example: Video vs Web: FB Analysis

Parameters

Video chunks

Chunked differently

Web assets

Conclusion

Theorem: PDA Reduces Finite-Blocklength Penalty

PDA subpacketization

FB scaling

Rate cost

Combined

Common Mistake: Asymptotic Rate Is Not Practically Achievable Below Threshold

Key Takeaway