Campus Units

Electrical and Computer Engineering, Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

7-2017

Journal or Book Title

IEEE Transactions on Information Theory

Volume

63

Issue

7

First Page

4388

Last Page

4413

DOI

10.1109/TIT.2017.2705166

Abstract

Caching is often used in content delivery networks as a mechanism for reducing network traffic. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server were considered. Prior results in this area demonstrate that carefully designing the placement of content in the caches and designing appropriate coded delivery signals from the server allow for a system where the delivery rates can be significantly smaller than conventional schemes. However, matching upper and lower bounds on the transmission rate have not yet been obtained. In this paper, we derive tighter lower bounds on the coded caching rate than were known previously. We demonstrate that this problem can equivalently be posed as a combinatorial problem of optimally labeling the leaves of a directed tree. Our proposed labeling algorithm allows for significantly improved lower bounds on the coded caching rate. Furthermore, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound for general values of the problem parameters. This allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound.

Comments

This is a manuscript of an article published as Ghasemi, Hooshang, and Aditya Ramamoorthy. "Improved lower bounds for coded caching." IEEE Transactions on Information Theory 63, no. 7 (2017): 4388-4413. DOI: 10.1109/TIT.2017.2705166. Posted with permission.

Rights

Copyright 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Copyright Owner

IEEE

Language

en

File Format

application/pdf

Published Version

Share

COinS