Ferkans — Interactive Telecom Tutor

What If $t$ Is Not an Integer?

The base MAN scheme requires $t = K M/N$ to be an integer — because subsets have integer cardinalities. But in practice $M$ might fall anywhere in $[0, N]$ , so $t$ can be any real number in $[0, K]$ .

The elegant fix is memory sharing — a convex combination of two integer-valued schemes. The overall achievable region is the lower convex envelope of the integer points $(M_i, R_i)$ for $i = 0, 1, \ldots, K$ , and memory sharing achieves every point on this envelope by time-sharing between two adjacent integer operating points.

Theorem: Achievable Region of the MAN Scheme

For any $M \in [0, N]$ , the worst-case rate achievable by the MAN scheme with memory sharing equals the lower convex envelope of the $K+1$ integer- $t$ points: $R_{\text{MAN}}(M) \;=\; \mathrm{conv}\bigl\{(iN/K,\; (K-i)/(i+1)) : i = 0, 1, \ldots, K\bigr\}.$ This envelope is a continuous, decreasing, piecewise-linear function of $M$ .

Proof

Construction: partition into two sub-files

Given target $M \in (iN/K, (i+1)N/K)$ , let $\alpha \in [0, 1]$ satisfy $M = \alpha \cdot iN/K + (1-\alpha) \cdot (i+1)N/K$ . Solve: $\alpha = (i+1) - KM/N$ . Note $\alpha \in [0, 1]$ is well-defined.

Split each file

Split $W_n = (W_n^A, W_n^B)$ where $W_n^A$ has size $\alpha F$ bits, $W_n^B$ has size $(1-\alpha) F$ bits. Run MAN with $t = i$ on $\{W_n^A\}$ and MAN with $t = i+1$ on $\{W_n^B\}$ independently.

Verify cache budget

The $t = i$ scheme uses per-user cache $\alpha \cdot (i/K) F$ bits per file; the $t = i+1$ scheme uses $(1-\alpha) \cdot ((i+1)/K) F$ bits per file. Summing over $N$ files: $\text{Per-user cache} \;=\; N \cdot F \cdot [\alpha i/K + (1-\alpha)(i+1)/K] \;=\; MF.$ ✓

Compute the combined rate

Delivery messages for the two sub-libraries are independent (different bits, separate XORs). Rate: $R \;=\; \alpha \cdot \frac{K-i}{i+1} + (1-\alpha) \cdot \frac{K-(i+1)}{(i+1)+1}$ which is the convex combination claimed.

Lower convex envelope

Varying $\alpha$ over $[0, 1]$ traces out the line segment between the two integer points in the $(M, R)$ plane. The union over all $i$ gives the lower envelope — a piecewise-linear curve. $\blacksquare$

Example: Memory Sharing at $M = 0.5 N/K$ (Fractional $t$ )

Let $K = 4$ , $N = 8$ , $M = 1$ (so $t = KM/N = 0.5$ , not integer). Find the rate achievable by memory-sharing between the $t = 0$ and $t = 1$ schemes.

Solution

Identify integer operating points

$t = 0$ : $M_0 = 0$ , $R_0 = K/(0+1) = 4$ .
$t = 1$ : $M_1 = N/K = 2$ , $R_1 = (K-1)/2 = 1.5$ .

Set up the convex combination

$M = \alpha M_0 + (1-\alpha) M_1 = (1-\alpha) \cdot 2$ . For $M = 1$ : $\alpha = 0.5$ .

Compute the shared rate

$R = 0.5 \cdot 4 + 0.5 \cdot 1.5 = 2.0 + 0.75 = 2.75$ files.

Compare to a hypothetical non-integer $t$

If we naively plug $t = 0.5$ into $R = (K-t)/(t+1) = 3.5/1.5 \approx 2.33$ . This is strictly less than the memory-shared 2.75. The reason: the naive formula is the continuous interpolation assuming fractional subsets exist, which they do not. The envelope is slightly above the continuous curve. This is why the MAN scheme upper bound curve (in our plots) is piecewise-linear, not smooth.

The Envelope Is Not the Continuous Curve

A common minor error: the continuous curve $R(M) = K(1-M/N)/(1+KM/N)$ is below the memory-shared (piecewise-linear) envelope everywhere except at the integer- $t$ points. The continuous formula is the "asymptotic" rate assuming integer $t$ , not a rate that memory sharing achieves.

When we later visualize "the MAN upper bound," we usually mean the piecewise-linear envelope — or, in scaling analyses where $K \to \infty$ at fixed $M/N$ , the two coincide and the distinction vanishes.

Common Mistake: Memory Sharing Cannot Recover the Continuous Formula

Mistake:

Claiming $R = K(1-M/N)/(1+KM/N)$ is always achievable, for any real $M$ .

Correction:

The formula is exactly achievable only when $t = KM/N$ is a non-negative integer. For general $M$ , the best you can do with memory sharing is the lower convex envelope of the integer- $t$ points, which is slightly above the continuous curve. In practice for large $K$ , the difference is a few percent at most — small enough that papers often quote the continuous formula as "the MAN rate" without comment. Be aware of this subtlety when computing rates for small $K$ .

Subpacketization Growth — The Elephant in the Room

The MAN scheme requires each file to be partitioned into $\binom{K}{t}$ subfiles — exponential in $K$ for fixed memory ratio. This is the single largest practical obstacle to deploying the scheme at scale. The dashed Stirling bound $2^{K h_b(\mu)}$ illustrates the exponential growth. Chapter 14 introduces PDAs and graph-coloring schemes that recover the caching gain with polynomial subpacketization.

Parameters

Memory ratio M/N0.25

Max K60

🚨Critical Engineering Note

Subpacketization Is the Main Practical Bottleneck

For $K = 50$ users and $\mu = 0.2$ (so $t = 10$ ), subpacketization is $\binom{50}{10} \approx 10^{10}$ . A 4 GB video file must be split into 10 billion pieces of 0.4 bytes each — obviously infeasible. For $K = 100$ , $\mu = 0.1$ , we would need $\binom{100}{10} \approx 1.7 \times 10^{13}$ pieces.

Consequences and mitigations:

Grouping: Split the $K$ users into groups of size $K_g = 30\text{–}50$ and run MAN within each group, losing the cross-group coded multicast gain. 3GPP uses this implicitly in multicast configurations.
PDAs: Placement Delivery Arrays (Yan et al. 2017) achieve polynomial subpacketization with a sub-optimal but still significant coded gain.
Graph coloring delivery (Ch 14): CommIT's polynomial- subpacketization schemes trade a constant-factor gain loss for polynomial $F$ .

Practical Constraints

•
MAN requires F ≥ \binom{K}{t}; typical video files have F ≈ 10^9 bits
•
Feasibility: \binom{K}{t} ≤ F/(few bits), so K ≤ 30 for realistic t and F
•
Any finite packet header is a fixed cost per subfile; shrinks useful payload to zero at high K

Memory Sharing for Non-Integer ttt

What If ttt Is Not an Integer?

Definition: Memory Sharing