Multicast ABR and Coded Caching

In this article, we give a brief overview about two media content distribution protocols that rely on multicasting: Multicast ABR (MABR) and Coded Caching. While MABR will be the standard technology for bandwidth-efficient livestreaming over multicast networks, Coded Caching can offer similar benefits for video-on-demand traffic.

MABR stands for Multicast Adaptive BitRate, hence it combines two major technologies in content distribution that have so far rarely be used jointly: multicasting and adaptive bitrate video transmission.

With adaptive streaming (such as HLS or DASH), video clients adapt their requested video bitrate (and hence quality) to the bandwidth offered by the communication channel. Because it relies on HTTP, it integrates extremely well into the architecture of the web. For broadcast communication channels and popular live streams, individual (unicast) transmission does not scale well. MABR combines those advantages of adaptive streaming with the efficiency of multicast transmission for live streams: It integrates well into the web architecture, but transmits each pieve of content only once per link. Compared to unicast, this can be tremendously more efficient.

Multicasting and video-on-demand? Coded Caching

The bandwidth savings with Multicast ABR are intuitive for live video. But can multicasting reduce the network load of individual video-on-demand services? The two apparent ideas are:

  • Pre-caching of popular content via multicast  
  • Bundling of simultaneous requests in a multicast data carousel

Coded Caching is the most efficient combination of both, caches at the receivers and coded multicast transmission. A tutorial on Coded Caching technology is available at https://cadami.net/coded-caching-blog/

Coded caching and Multicast ABR share the same architecture: Content Origin, Multicast Server, IP Multicast Network, Multicast Client, Video Clients. To upgrade MulticastABR deployments to video-on-demand by Coded Caching, we need additional components: 

  • storage at the client
  • computational power to encode/decode the data stream

The content origin and the Coded Caching server can be the same node, co-located, or separated. The same applies to the Coded Caching Client and the video client, such as a set-top box. Coded Caching can be used across all network hierarchies and supports all kinds of multicast networks, such as operator networks, broadband, satellite, or cellular (FeMBMS) networks.

Potential gains are illustrated in the following case study.

Case Study – CDN Origin Server and Edge Nodes

Coded Caching is the optimal tradeoff between storage size at the client and traffic emitted by the server. What does this mean? Let us illustrate this with an example scenario with the following parameters: 

  • C=50 Clients,
  • F=200 titles in the video-on-demand library, 
  • and a request probability, such that a request of the most popular file is n times more likely than a request for the n-th most popular file. 

Coded Caching outperforms popularity caching on the full trade-off curve. We highlight one operation point: Coded Caching reduces traffic by 66% by storing the equivalent of 5 titles only. As a comparison, caching the five most popular titles creates twice as much server traffic. Coded caching is exceptionally efficient with storage – to reduce traffic to the same level, popularity caching needs five times the storage.

Coded Caching benefits both the popular content and long-tail content. For each content title, Cadami’s Coded Caching algorithm selects a fraction of the title stored in the client cache. This fraction depends on the content’s popularity, and the so-called Coded Caching gain G. The server emits 1/G of the unicast traffic, and the storage size for this title on every client is a fraction of (G-1)/C of the file, where C is the number of clients. Conventional caching is G=∞, with the title stored completely and no traffic. G=1 implies no storage but 100% traffic when downloading the title. Let us explore a detailed breakdown of the highlighted operation point:

Coded Caching Gain321Total
Files (ranked by popularity)12-5051-152153-200200
Cache Storage per File100%4%2%0%
Total Storage in Files11.962.0405
Total Traffic (vs. No Caching)019.6%9.4%4.7%33.7%

Coded Caching is the extension to video-on-demand services for Multicast ABR

Coded Caching converts network traffic generated by video-on-demand services to multicast. Coded caching and MulticastABR share a similar architecture. Coded Caching presents itself as an intuitive extension from linear live TV to video-on-demand services for MulticastABR. Coded Caching has proven itself in 300+ commercial deployments for video distribution in aircraft. Implementations are available for various operating systems, for example, Linux and Android, and hosting options, such as running servers in the cloud and clients on embedded hardware. Cadami is looking for partnerships with organizations engaged in Multicast ABR standardization and commercialization to discuss options for integration of Coded Caching. If you are interested in learning more about Coded Caching and engaging in a conversation, please get in touch.

plot comparing the performance of legacy multicast to Cadami's rapid multicast.

Cadami’s Rapid Multicast – 100x Legacy WiFi Multicast Performance

The general belief is that WiFi isn’t well suited for high-bandwidth multicast applications. This is wrong: Reliable WiFi multicast at rates similar to unicast is possible for 1000+ receivers. We demonstrated 220 Mbps multicast throughput and >150 receivers in lab conditions. 

WiFi Multicast is challenging, because 

  • of low and non-adaptive data rates, 
  • it is unreliable (no link-layer ACKs).

Multicast-to-Unicast conversion is an option – until too many receivers enter your network and exceed its capacity. Configuring a higher modulation and coding scheme (MCS) for multicast improves the data rate, but does not achieve the same data rates as unicast, because frame aggregation was missing – until now.

We modified the Linux WiFi and networking stack at the accesspoint to support frame aggregation (A-MPDU) for multicast traffic and the adaptive selection of the MCS for on a per-packet basis. The following WiFi frames capture, inspected with Wireshark shows a multicast transmission with MCS index 5 and A-MPDU enabled.  

Measurements of multicast throughput in our lab show that without frame aggregation, multicast has a large gap to the theoretical rates, while rapid multicast achieves >80% the nominal rates, which is unicast performance.

plot comparing the performance of legacy multicast to Cadami's rapid multicast.

With the low and non-adaptive data rates challenge solved, we observe packet loss in the low one-digit percentage. We use application layer forward error-correcting codes to conceal packet loss and run reliable multicast services. Our rapid multicast technology is not bound to a specific coding scheme or implementation. We recommend the Kodo Library by Steinwurf. For two specific applications that benefit from rapid multicast, Cadami and Steinwurf offer joint solutions:

Our rapid multicast modifications do not require changes at the WiFi clients and are compatible with the most popular mobile devices, such as the iPhone or the Samsung Galaxy Series. Rapid multicast is available preinstalled on hardware, or can be integrated with existing WiFi products. If you are interested, please contact sales@cadami.net or use the form.

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: