Coded Caching

Cadami offers a software implementation of Coded Caching for commercial applications. Coded Caching uses a combination of caches at the receivers and coded broadcast transmission. The following example illustrates an application.

A video-on-demand service offers a library containing a yellow, an orange, and a blue video. The three users request videos represented by the colors of their screens. Each user has one video in his cache (colored file in the top
row of their user’s cloud) and is missing the other two videos
(gray files in the top row of the user’s cloud). Conventional unicast streaming without caches at the users has to transmit three videos. With caches at the users, the amount of data to transmit is reduced by the cache hit rate. In our example, user 3 has a cache hit for the orange video. Instead of three, only two videos are transmitted. For the remaining two users the cache is missed and thus provides no benefit.

We can further exploit the caches at the users by coding and broadcast transmission. Upon receiving the requests for the yellow and blue video, the server combines both and serves them with one coded broadcast transmission. The server combines the yellow video and the blue video by applying a bit-wise XOR operation to generate a green file X = A ⊕ B. File X has the same size as A and B and not the size of A plus the size of B. The server broadcasts the green file X to both users in a single transmission. The yellow user feeds both its received file X and the blue video from its cache into the decoder. The decoder returns the requested yellow file A by computing B ⊕ X = B ⊕ (A ⊕ B) = A. Similarly, the blue user computes A ⊕ X = A ⊕ (A ⊕ B) = B from its received file X and the yellow video A from its cache. By Coded Caching both users to retrieve their desired content from a single broadcast stream. For this example, we require the transmission of one file, while conventional caching requires two files, and streaming without caches three files.

Generalization

The example illustrates how the combination of caching, broadcast transmission, and coding can save a significant amount of resources for video-on-demand delivery. Coded Caching generalizes these gains to general libraries, user populations, and arbitrary user requests. The video files in the library are chopped up into sufficiently small pieces. Each user stores its unique systematic selection of pieces of each file. The design of the cache is vital for achieving gains in resource reduction. For example, consider a system with five files (A yellow, B blue, C orange, D gray, E red) and four users (left-to-right: S, T, U, V ) where each user stores 50% of each file, as shown in the figure.

As soon as every user requests a file as indicated by the colors of the device screens, that is S → A, T → B, U → C, V → D, only the missing parts of the requested files need to be transmitted. Additionally, the server can code together 3 missing parts in each transmission. That is, it transmits

X1 = A2 ⊕ C3 ⊕ D6
X2 = A4 ⊕ B6 ⊕ C1
X3 = A5 ⊕ B3 ⊕ D1
X4 = B2 ⊕ C5 ⊕ D4

using four broadcast transmissions. For example, user S decodes its missing file part A2 from the received X1 and C1 and D3 from the cache as A2 = X1 ⊕ C3 ⊕ D6. With Coded Caching, we require the transmission of four pieces, while conventional caching requires 12 pieces, and streaming without caches 24 pieces. One can verify, that any user request can be satisfied by transmitting four pieces.

In case you want to learn more about the theory of Coded Caching, we recommend “Fundamental Limits of Caching” by Mohammad Ali Maddah-Ali and Urs Niesen. If you would like an analysis if your application can benefit from Coded Caching, contact us at sales@cadami.net or use the form: