Muriel Médard, Massachusetts Institute of Technology – June 2012


Title: Coding for Efficient Local Caches
Abstract: Network coding is different from that of transcoding or source coding. Network coding may be applied on top of the transcoding or source coding that may be executed at the source or server. Transcoding or source coding are often used to tailor content, e.g. video, for the application of interest and/or the network environment. For example, it may be desirable to generate HD video for users with high speed connections while SD video for users with limited access to the network. Once these videos are generated, it is the task of the storage and the transport network to deliver the given video. Network coding facilitates the process of storing and transporting the video, but does not need to affect or modify the underlying content being delivered.

To return to the previous example, in the current solution, the cache essentially has to store the entire file in order to be effective in reducing the load on the transport network even by 10%. With coding, the cache may store 10% of the content; however, the content stored will be coded. As a result, the coded data may be used to recover any of the 10% of the undelivered content; the cache is able to supplement effectively the 10% deficit in the transport network with a storage size commensurate the deficit. Thus, with a coded cache with only 10% of the content, the end-­‐user observes a network with 100% of the required bandwidth while actually only having access to 90% of it. The benefit of network coding become further pronounced in more complex storage networks.

An important feature of network coding is that not all storage units need to store coded data in order to be effective. It is sufficient to have only one of multiple caches store coded data; the other cache may store uncoded data. The use of systematic codes, i.e. use uncoded data and coded data together, has been shown to reduce decoding delay, decoding complexity. Furthermore, the advantage of a “systematic storage” may be for incremental deployment of coded caches; as this method allows coded caches to complement existing caches.