Ferkans — Interactive Telecom Tutor

Why This Particular Placement?

The MAN placement is a combinatorial design: each subfile goes to exactly $t$ caches, chosen by the identity of the subset $\mathcal{S}$ . One could imagine many other placements (random, content-aware, hierarchical) but the MAN choice is special for a precise reason: it is the unique (up to symmetries) uncoded placement that equalizes, across users, the number of subfiles held by every pair. This symmetry is what makes the delivery phase so clean.

A designer could complain that the placement is rigid — it must be exactly right for the delivery to work. Chapters 14 and 18 show alternative placements (PDAs, multi-access, decentralized) that relax this rigidity at the cost of different tradeoffs.

MAN Placement Algorithm

Complexity: Storage per user:

|\mathcal{Z}_k| = N \cdot \binom{K-1}{t-1}

subfiles, each of size

F/\binom{K}{t}

bits. Total:

MF

bits. ✓ Off-peak bandwidth:

KM F

bits (every subfile transmitted to the

t

users that cache it).

Input: Library

\{W_1, \ldots, W_N\}

with each

W_n \in \mathbb{F}_2^F

; parameters

K, t

with

t = KM/N \in \{0, 1, \ldots, K\}

.

Output: Caches

\mathcal{Z}_1, \ldots, \mathcal{Z}_K

.

1. Compute

F_{\text{sub}} \leftarrow F / \binom{K}{t}

. // subfile size in bits

2. for each file

W_n

,

n = 1, \ldots, N

do

3.

\quad

Partition

W_n

into

\binom{K}{t}

equal-sized blocks,

4.

\quad

labeled

W_{n,\mathcal{S}}

for each

\mathcal{S} \subseteq [K]

with

|\mathcal{S}| = t

.

5. end for

6. for

k = 1

to

K

do

7.

\quad \mathcal{Z}_k \leftarrow \{\, W_{n,\mathcal{S}} : n \in [N],\; \mathcal{S} \ni k,\; |\mathcal{S}| = t \,\}

8. end for

9. return

(\mathcal{Z}_1, \ldots, \mathcal{Z}_K)

.

Theorem: Cache Size Consistency

Under MAN placement, each user $k$ caches exactly $M \cdot F$ bits, i.e., $M$ files' worth of content, as required.

Proof

Count subfiles per cache

User $k$ caches subfile $W_{n,\mathcal{S}}$ iff $k \in \mathcal{S}$ . The number of $t$ -subsets of $[K]$ containing $k$ is $\binom{K-1}{t-1}$ . Summing over $n \in [N]$ : $|\mathcal{Z}_{k}| \;=\; N \cdot \binom{K-1}{t-1} \text{ subfiles}.$

Convert to bits

Each subfile has size $F/\binom{K}{t}$ bits, so $|\mathcal{Z}_{k}| \cdot \frac{F}{\binom{K}{t}} \;=\; N \cdot \frac{\binom{K-1}{t-1}}{\binom{K}{t}} \cdot F \;=\; N \cdot \frac{t}{K} \cdot F \;=\; MF,$ using the identity $\binom{K-1}{t-1}/\binom{K}{t} = t/K$ and the definition $t = KM/N$ . $\blacksquare$

The Symmetry That Matters

Two critical symmetries of the MAN placement:

Subfile-level symmetry. Every subfile $W_{n,\mathcal{S}}$ is cached by exactly $t$ users. This is visible in the placement heatmap as row-wise balance.

User-level symmetry. Every user caches exactly $\binom{K-1}{t-1}$ subfiles per file. This is the column-wise balance.

Together, these two symmetries imply that for every pair $(k, \mathcal{S})$ with $k \notin \mathcal{S}$ and $|\mathcal{S}| = t$ , user $k$ does not have subfile $W_{n,\mathcal{S}}$ . When user $k$ requests file $W_{d_k}$ , the missing subfiles it needs are exactly those indexed by $t$ -subsets that do not contain $k$ . There are $\binom{K-1}{t}$ such subsets. This count will reappear in the delivery analysis.

Example: Example Cache Contents: $K = 4$ , $t = 2$

For $K = 4$ users and $t = 2$ (implying $M/N = 1/2$ ), enumerate user 1's cache contents for each of $N$ files.

Solution

List 2-subsets containing user 1

2-subsets of $\{1,2,3,4\}$ containing 1: $\{1,2\}, \{1,3\}, \{1,4\}$ — three subsets, matching $\binom{K-1}{t-1} = \binom{3}{1} = 3$ .

User 1's cache per file

For each $n \in [N]$ , user 1 stores $W_{n,\{1,2\}}, W_{n,\{1,3\}}, W_{n,\{1,4\}}$ . Three subfiles per file, each of size $F/\binom{4}{2} = F/6$ bits.

Total cache size

$3N \cdot F/6 = NF/2 = MF$ ( $M = N/2$ ). ✓

Missing subfiles per file

Total subfiles per file: $\binom{4}{2} = 6$ . User 1 has 3, is missing 3: $W_{n,\{2,3\}}, W_{n,\{2,4\}}, W_{n,\{3,4\}}$ — all 2-subsets not containing 1. Count: $\binom{K-1}{t} = \binom{3}{2} = 3$ . ✓

Key Takeaway

User $k$ 's cache content is uniform over its support, because the subfiles are mutually independent (different files are independent, same-file different-subfile are too under our assumption $\mathrm{H}(W_n) = F$ ). Hence $\mathrm{H}(\mathcal{Z}_{k}) = MF$ bits exactly — the cache budget is fully used with no slack.

🔧Engineering Note

The Off-Peak Cost of Placement

A subtle point in the placement analysis: the MAN scheme requires the server to transmit every subfile $W_{n,\mathcal{S}}$ to each of the $t$ users in $\mathcal{S}$ . Total off-peak traffic: $\text{Placement bits} \;=\; N \cdot \binom{K}{t} \cdot t \cdot \frac{F}{\binom{K}{t}} \;=\; N t F \;=\; KMF.$ That is, one full library's worth for each user — the cache is entirely populated, as it must be.

In real CDN deployments the placement is done over a long period (days) and the delivery savings amortize over many delivery rounds. The economic argument for coded caching depends on the ratio of these two time scales.

Practical Constraints

•
Placement cost: $KMF$ bits per library refresh
•
Delivery cost per round: $K(1-M/N)/(1+KM/N) \cdot F$ bits
•
Break-even: ratio of peak rounds to library refresh frequency must be large

Common Mistake: All Caches Are Identical in Structure, Different in Content

Mistake:

Saying 'all users cache the same subfiles' because the scheme is symmetric.

Correction:

The structure is identical — every user caches subfiles whose index sets contain that user, and every user caches the same number $(N \binom{K-1}{t-1})$ of subfiles. But the specific subfiles differ: user 1 caches $W_{n,\{1,2\}}$ ; user 2 caches $W_{n,\{1,2\}}$ as well (since $2 \in \{1,2\}$ ); user 3 does not cache $W_{n,\{1,2\}}$ . The combinatorial interleaving of caches is what lets the delivery XOR messages work.

Placement Phase: Combinatorial Subfile Assignment