TopRank-Based Delivery Rate Optimization for Coded Caching under Non-Uniform Demands

This paper proposes a TopRank-based coded caching strategy that optimizes delivery rates under non-uniform, unknown file demands by ranking files based on request count differences rather than estimating exact popularities, thereby achieving superior performance and sublinear regret in scenarios with limited users, small cache capacities, or noisy observation data.

The Gist

Imagine you run a massive digital library (the Server) that serves thousands of books (the Files) to a group of readers (the Users).

The problem is that your library has a limited amount of space in the "reading nooks" (the Caches) right next to each reader. You can't put every book in every nook. You want to put the most popular books in the nooks so that when a reader asks for them, they get them instantly without clogging up the main hallway (the Network).

However, there's a catch: You don't know which books are popular yet. You have to learn by watching what people ask for.

The Old Way: "Guessing the Exact Numbers"

Previous methods tried to be like a super-precise statistician. They would count every single request, calculate the exact percentage of popularity for every book, and then draw a strict line: "If a book is requested more than 5.3% of the time, it goes in the nook. If it's 5.2%, it stays on the shelf."

Why this failed:

1. Small Groups: If you only have a few readers, your statistics are shaky. You might think a book is popular just because two people asked for it by chance.
2. Fake Noise: If a hacker or a bot sends fake requests for obscure books, the statistician gets confused and thinks those boring books are hits.
3. Too Slow: It takes a long time to get those percentages accurate enough to draw the line.

The New Way: "The Top-Rank Sorting Game"

The authors of this paper propose a smarter, more flexible approach. Instead of trying to calculate the exact popularity percentage, they just want to know who is beating whom.

Think of it like a Tournament Bracket or a Leaderboard:

• We don't care if Book A is 10% popular and Book B is 9%.
• We just care that Book A is clearly more popular than Book B.

How it works (The "Peeling" Method):

1. The Tournament: Every time a request comes in, the system compares books. If Book A gets requested significantly more often than Book B, the system puts a checkmark next to A saying, "A is definitely above B."
2. The Groups: Once the system has enough evidence, it sorts the books into "layers" or "partitions."
   • Layer 1: The undisputed champions (the most popular).
   • Layer 2: The runners-up.
   • Layer 3: The rest.
3. The Decision: The system looks at the top layers. It asks, "If we fill the nooks with the books in Layer 1 and Layer 2, will that save us the most traffic?" It picks the best cut-off point based on recent history.

Why is this better? (The Analogies)

1. The "Fake News" Defense
Imagine a bot tries to make a boring book look popular by requesting it 100 times in a row.

• Old Method: The statistician panics. "Wow, 100 requests! That's a hit! Let's put it in the nook!" (Disaster).
• New Method: The system looks at the whole picture. "Okay, this book got 100 requests, but the real popular books got 1,000 requests each. This bot-book is still at the bottom of the leaderboard. Ignore it." The system is robust against noise because it focuses on relative ranking, not absolute numbers.

2. The "Small Crowd" Advantage
Imagine you only have 5 readers.

• Old Method: With so few data points, the "5.3% line" is impossible to calculate accurately. You might leave the best book on the shelf.
• New Method: You don't need a percentage. You just need to see that Book A is requested more than Book B. Even with 5 people, if Book A is asked for 3 times and Book B is asked for 0, the ranking is clear. The system works great even with small data.

3. The "Good Enough" Philosophy
The authors realized you don't need to know if the 7th most popular book is exactly the 7th. You just need to make sure it's in the "Popular Group" along with the top 6.

• Analogy: Imagine you are packing a suitcase for a trip. You don't need to know the exact weight of your socks to decide to pack them. You just need to know they are "essential." If you pack the top 10 essential items, you're good, even if you accidentally swapped the 7th and 8th item. The system allows for this flexibility, making it faster and more accurate.

The Result

By using this "Top-Rank" approach (inspired by how Netflix or Spotify recommend things), the system:

• Learns faster.
• Ignores fake requests and bots.
• Works perfectly even when there are very few users or very little storage space.

In short: Stop trying to measure the exact height of every person in a crowd. Just figure out who is taller than whom, and put the tallest people in the front row. That's what this paper does for internet data.

Technical Summary

Here is a detailed technical summary of the paper "TopRank-Based Delivery Rate Optimization for Coded Caching under Non-Uniform Demands."

1. Problem Statement

The paper addresses the coded caching problem in a network consisting of one server and $K$ users, where the server holds $N$ files of equal size. The core challenge lies in the non-uniform popularity of these files (some are requested much more frequently than others) and the fact that this popularity distribution is initially unknown.

The system operates in two phases:

1. Placement Phase: During low-traffic periods, the server fills user caches (size $M$) based on estimated file popularities.
2. Delivery Phase: Users request files. The server broadcasts a signal to satisfy all requests. The goal is to minimize the total transmission rate ($R_{total}$).

Limitations of Existing Approaches:
Previous methods (e.g., [8]) attempt to accurately estimate the exact popularity probability ($p_i$) of every file. They then partition files into "popular" and "unpopular" groups based on a threshold. The authors identify three critical failure modes in these estimation-based approaches:

• Small Sample Size: With few users or requests, popularity estimates are inaccurate, leading to long learning times.
• Threshold Failure: If the cache size ($M$) or number of users ($K$) is small, the calculated popularity threshold may exceed the actual popularity of all files, resulting in no files being cached.
• Noise Sensitivity: The algorithms are easily misled by "exploratory" requests (users checking all files) or malicious/fake requests (bots), which distort the estimated distribution.

2. Methodology: TopRank-Based Policy

The authors propose a novel algorithm inspired by Learning-to-Rank and Multi-Armed Bandit literature (specifically referencing [13]). Instead of estimating absolute popularity values, the method focuses on relative ranking and partitioning.

Core Concept: Relative Ranking via Concentration Inequalities

• Binary Relation ($G$): The algorithm maintains a binary relation $G$ that records pairwise comparisons between files (e.g., File $i$ is more popular than File $j$).
• Peeling Partitioning: Files are grouped into partitions ($P_{t1}, P_{t2}, \dots$) based on the accumulated evidence.
  • Files with no evidence of being less popular than others are placed in the first partition (most popular).
  • The process repeats ("peeling") for the remaining files.
• Decision Threshold: The algorithm uses concentration inequalities to determine when the difference in request counts ($C_{ti} - C_{tj}$) is statistically significant enough to establish a ranking.
  • A threshold is defined: $S_{tij} \geq \sqrt{2V_{tij} \log(\frac{c}{\delta}\sqrt{V_{tij}})}$.
  • To handle cases where multiple requests occur per round ($C_{ti} \in [0, K]$), the round is subdivided into $\theta_t$ smaller stages to ensure the statistical conditions hold.

Popular Group Selection (Two Methods)

Once files are partitioned, the algorithm must decide how many top partitions constitute the "Popular Group" to be cached. Two history-based strategies are proposed:

1. Method 1 (Aggregated History): Assumes the requests from the last $H$ rounds occurred simultaneously. It calculates the network rate for this aggregated set and selects the grouping that minimizes the rate.
2. Method 2 (Frequency-Based): Calculates the optimal grouping for each of the last $H$ rounds individually. The grouping that appears most frequently as optimal across these rounds is selected for the next round.

3. Key Contributions

• Shift from Estimation to Ranking: The paper argues that precise estimation of file popularity is unnecessary. It is sufficient to correctly partition files into "popular" and "non-popular" groups. This provides flexibility; a file can be slightly misranked (e.g., estimated 10th instead of 7th) but still correctly included in the popular set.
• Robustness to Noise: By relying on relative differences and concentration inequalities, the proposed policy is robust against exploratory requests and malicious attacks that distort absolute popularity counts.
• Sublinear Regret: The authors prove that their policy achieves sublinear regret, meaning the performance gap between their policy and an optimal "oracle" (which knows true popularities) diminishes over time.
• Handling Small Networks: The method specifically outperforms existing algorithms in scenarios with small user counts, limited cache sizes, or high file counts where traditional thresholding fails.

4. Experimental Results

The authors evaluated their policy (OPM1 and OPM2) against the state-of-the-art method from [8] (labeled NSK) using the Movielens 1M dataset.

• Scenarios Tested:
  • Standard: 50 users, no attacks.
  • Adversarial/Exploratory: 100 users, with periodic "attacks" where all files are requested (simulating initial exploration or bot traffic).
• Findings:
  • Performance: The proposed methods significantly outperformed NSK, particularly in the adversarial scenario. NSK's regret grew linearly (indicating failure to learn), while the proposed methods achieved sublinear regret.
  • Method Comparison: Method 2 generally yielded lower regret than Method 1 but required higher computational effort.
  • Parameter Sensitivity:
    • $\delta$ (Confidence Parameter): Larger $\delta$ values allow for faster initial grouping and lower early regret by reducing sensitivity to noise. However, excessively large $\delta$ leads to irreversible errors. Smaller $\delta$ provides higher accuracy over time.
    • History Length ($H$): Using the entire history leads to error accumulation; a finite $H$ is optimal.

5. Significance

This work represents a paradigm shift in coded caching optimization under uncertainty. By moving away from the computationally expensive and noise-sensitive task of estimating probabilities to the more robust task of learning relative orders, the authors provide a solution that is:

1. Practical: It functions effectively even when the network is small or the data is "dirty" (contaminated by fake requests).
2. Theoretically Sound: It guarantees sublinear regret, ensuring long-term optimality.
3. Applicable: The approach is highly relevant for modern content delivery networks (CDNs) and streaming services where file popularity is volatile and user behavior can be unpredictable or malicious.

In summary, the paper demonstrates that ranking files relative to one another is a more efficient and robust strategy for coded caching than attempting to calculate their exact popularity distributions, especially in dynamic and potentially adversarial network environments.