Search

We consider the coded caching problem with an additional privacy constraint that a user should not get any information about the demands of the other users. We first show that a demand-private scheme for $N$ files and $K$ users can be obtained from a non-private scheme that serves only a subset of the demands for the $N$ files and $NK$ users problem. We further use this fact to construct a demand-private scheme for $N$ files and $K$ users from a particular known non-private scheme for $N$ files and $NK-K+1$ users. It is then demonstrated that, the memory-rate pair $(M,\min \{N,K\}(1-M/N))$ , which is achievable for non-private schemes with uncoded transmissions, is also achievable under demand privacy. We further propose a scheme that improves on these ideas by removing some redundant transmissions. The memory-rate trade-off achieved using our schemes is shown to be within a multiplicative factor of 3 from the optimal when $K < N$ and of 8 when $N \leq K$. Finally, we give the exact memory-rate trade-off for demand-private coded caching problems with $N\geq K=2$. [ABSTRACT FROM AUTHOR]

Caching is a technique that alleviates networks during peak hours by transmitting partial information before a request for any is made. In a lossy setting of Gaussian databases, we study a single-user model in which good caching strategies minimize the data still needed on average once the user requests a file. The encoder decides on a caching strategy by weighing the benefit from two key parameters: the prior preference for a file and the correlation among the files. Considering uniform prior preference but correlated files, caching becomes an application of Wyner’s common information and Watanabe’s total correlation. We show this case triggers a split: caching Gaussian sources is a non-convex optimization problem unless one spends enough rate to cache all the common information between files. Combining both correlation and user preference we explicitly characterize the full trade-off when the encoder uses Gaussian codebooks in a database of two files: we show that as the size of the cache increases, the encoder should change strategy and increasingly prioritize user preference over correlation. In this specific case we also address the loss in performance incurred if the encoder has no knowledge of the user’s preference and show that this loss is bounded. [ABSTRACT FROM AUTHOR]

This paper studies the fundamental limits of content delivery in a cache-aided broadcast network for correlated content generated by a discrete memoryless source with arbitrary joint distribution. Each receiver is equipped with a cache of equal capacity, and the requested files are delivered over a shared error-free broadcast link. A class of achievable correlation-aware schemes based on a two-step source coding approach is proposed. Library files are first compressed, and then cached and delivered using a combination of multiple-request caching schemes that are agnostic to the content correlations. The first step uses Gray-Wyner source coding to represent the library via private descriptions and descriptions that are common to more than one file. The second step then becomes a multiple-request caching problem, where the demand structure is dictated by the configuration of the compressed library, and it is interesting in its own right. The performance of the proposed two-step scheme is evaluated by comparing its achievable rate with a lower bound on the optimal peak and average rate-memory trade-offs in a two-file multiple-receiver network, and in a three-file two-receiver network. Specifically, in a network with two files and two receivers, the achievable rate matches the lower bound for a significant memory regime and it is within half of the conditional entropy of files for all other memory values. In the three-file two-receiver network, the two-step strategy achieves the lower bound for large cache capacities, and it is within half of the joint entropy of two of the sources conditioned on the third one for all other cache sizes. [ABSTRACT FROM AUTHOR]

We consider the problem of private information retrieval (PIR) of a single message out of $K$ messages from $N$ replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size $M$ possesses side information in the form of full messages that are partially known to the databases. In this model, the user and the databases engage in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user downloads desired information. In the prefetching phase, the user receives $m_{n}$ full messages from the $n$ th database, under the cache memory size constraint $\sum _{n=1}^{N} m_{n} \leq M$. In the retrieval phase, the user wishes to retrieve a message (which is not present in its memory) such that no individual database learns anything about the identity of the desired message. In addition, the identities of the side information messages that the user did not prefetch from a database must remain private against that database. Since the side information provided by each database in the prefetching phase is known by the providing database and the side information must be kept private against the remaining databases, we coin this model as partially known private side information. We characterize the capacity of the PIR with partially known private side information to be $C=\left ({1+\frac {1}{N}+\cdots +\frac {1}{N^{K-M-1}}}\right)^{-1}=\frac {1-\frac {1}{N}}{1-\left({\frac {1}{N}}\right)^{K-M}}$. Interestingly, this result is the same if none of the databases knows any of the prefetched side information, i.e., when the side information is obtained externally, a problem posed by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases. [ABSTRACT FROM AUTHOR]

Degraded K-user broadcast channels (BCs) are studied when the receivers are facilitated with cache memories. Lower and upper bounds are derived on the capacity-memory tradeoff, i.e., on the largest rate of reliable communication over the BC as a function of the receivers’ cache sizes, and the bounds are shown to match for interesting special cases. The lower bounds are achieved by two new coding schemes that benefit from nonuniform cache assignments. Lower and upper bounds are also established on the global capacity-memory tradeoff, i.e., on the largest capacity-memory tradeoff that can be attained by optimizing the receivers’ cache sizes subject to a total cache memory budget. The bounds coincide when the total cache memory budget is sufficiently small or sufficiently large, where the thresholds depend on the BC statistics. For small cache memories, it is optimal to assign all the cache memory to the weakest receiver. In this regime, the global capacity-memory tradeoff grows by the total cache memory budget divided by the number of files in the system. In other words, a perfect global caching gain is achievable in this regime and the performance corresponds to a system where all the cache contents in the network are available to all receivers. For large cache memories, it is optimal to assign a positive cache memory to every receiver, such that the weaker receivers are assigned larger cache memories compared to the stronger receivers. In this regime, the growth rate of the global capacity-memory tradeoff is further divided by the number of users, which corresponds to a local caching gain. It is observed numerically that a uniform assignment of the total cache memory is suboptimal in all regimes, unless the BC is completely symmetric. For erasure BCs, this claim is proved analytically in the regime of small cache sizes. [ABSTRACT FROM AUTHOR]

This paper derives upper and lower bounds on the secrecy capacity-memory tradeoff of a wiretap erasure broadcast channel (BC) with ${\mathsf{K}}_{w} $ weak receivers and ${\mathsf {K}}_{s} $ strong receivers, where weak receivers and strong receivers have the same erasure probabilities and cache sizes, respectively. The lower bounds are achieved by the schemes that meticulously combine joint cache-channel coding with wiretap coding and key-aided one-time pads. The presented upper bound holds more generally for arbitrary degraded BCs and arbitrary cache sizes. When only weak receivers have cache memories, upper and lower bounds coincide for small and large cache memories, thus providing the exact secrecy capacity-memory tradeoff for this setup. The derived bounds further allow us to conclude that the secrecy capacity is positive even when the eavesdropper is stronger than all the legitimate receivers with cache memories. Moreover, they show that the secrecy capacity-memory tradeoff can be significantly smaller than its non-secure counterpart, but it grows much faster when cache memories are small. This paper also presents a lower bound on the global secrecy capacity-memory tradeoff where one is allowed to optimize the cache assignment subject to a total cache budget. It is close to the best known lower bound without secrecy constraint. For small total cache budget, the global secrecy capacity-memory tradeoff is achieved by assigning all the available cache memory uniformly over all the receivers if the eavesdropper is stronger than all the legitimate receivers, and it is achieved by assigning the cache memory uniformly only over the weak receivers if the eavesdropper is weaker than the strong receivers. [ABSTRACT FROM AUTHOR]

We consider the problem of private information retrieval (PIR) from $N$ non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction $r$ from each of the $K$ stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate $D^{*}(r)$ the optimal download cost normalized with the message size as a function of $K$ , $N$ , and $r$. For a fixed $K$ and $N$ , we develop an inner bound (converse bound) for the $D^{*}(r)$ curve. The inner bound is a piece-wise linear function in $r$ that consists of $K$ line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve $K-1$ non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate the one-side information equation. We obtain an outer bound (achievability) for any caching ratio by memory sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in $r$ that consists of $K$ line segments. The inner and the outer bounds match in general for the cases of very low-caching ratio and very high-caching ratio. As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for $K=3$. For general $K$ , $N$ , and $r$ , we show that the largest gap between the achievability and the converse bounds is 1/6. Our results show that the download cost can be reduced beyond memory sharing if the databases are unaware of the cached content. [ABSTRACT FROM AUTHOR]

We consider a basic caching system, where a single server with a database of $N$ files (e.g., movies) is connected to a set of $K$ users through a shared bottleneck link. Each user has a local cache memory with a size of $M$ files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of 2.00884 for both the peak rate and the average rate (under uniform file popularity), improving the state of the arts that are within a factor of 4 and 4.7, respectively. Moreover, in a practically important case where the number of files ($N$) is large, we exactly characterize the tradeoff for systems with no more than five users and characterize the tradeoff within a factor of 2 otherwise. To establish these results, we develop two new converse bounds that improve over the state of the art. [ABSTRACT FROM AUTHOR]

Improved lower bounds are derived on the average and worst case rate-memory tradeoffs of the Maddah-Ali and Niesen-coded caching scenario. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is shown to be less than 2.315 in the worst case scenario and 2.507 in the average-case scenario. [ABSTRACT FROM AUTHOR]

An erasure broadcast network is considered with two disjoint sets of receivers: a set of weak receivers with all-equal erasure probabilities and equal cache sizes and a set of strong receivers with all-equal erasure probabilities and no cache memories. Lower and upper bounds are presented on the capacity-memory tradeoff of this network (the largest rate at which messages can be reliably communicated for given cache sizes). The lower bound is achieved by means of a joint cache-channel coding scheme and significantly improves over traditional schemes based on the separate cache-channel coding. In particular, it is shown that the joint cache-channel coding offers new global caching gains that scale with the number of strong receivers in the network. The upper bound uses bounding techniques from degraded broadcast channels and introduces an averaging argument to capture the fact that the contents of the cache memories are designed before knowing users’ demands. The derived upper bound is valid for all stochastically degraded broadcast channels. The lower and upper bounds match for a single weak receiver (and any number of strong receivers) when the cache size does not exceed a certain threshold. Improved bounds are presented for the special case of a single weak and a single strong receiver with two files and the bounds are shown to match over a large range of cache sizes. [ABSTRACT FROM AUTHOR]

We consider a wireless device-to-device caching network where n nodes are placed on a regular grid of area A\left ({n}\right) . Each node caches L_{C}F$ (coded) bits from a library of size LF$ bits, where L$ is the number of files and F ). Moreover, we propose a cache-induced hierarchical cooperation scheme and associated cache content placement optimization algorithm to achieve the optimal per-node capacity scaling law. When the path loss exponent $\alpha <3$ , the optimal per-node capacity scaling law achieved by the cache-induced hierarchical cooperation can be significantly better than that achieved by the existing state-of-the-art schemes. To the best of our knowledge, this is the first work that completely characterizes the per-node capacity scaling law for wireless caching networks under the physical model and Zipf distribution with an arbitrary skewness parameter $\tau $ . While scaling law analysis yields clean results, it may not accurately reflect the throughput performance of a large network with a finite number of nodes. Therefore, we also analyze the throughput of the proposed cache-induced hierarchical cooperation for networks of practical size. The analysis and simulations verify that cache-induced hierarchical cooperation can also achieve a large throughput gain over the cache-assisted multihop scheme for networks of practical size. [ABSTRACT FROM PUBLISHER]

We consider a basic cache network, in which a single server is connected to multiple users via a shared bottleneck link. The server has a database of files (content). Each user has an isolated memory that can be used to cache content in a prefetching phase. In a following delivery phase, each user requests a file from the database, and the server needs to deliver users’ demands as efficiently as possible by taking into account their cache contents. We focus on an important and commonly used class of prefetching schemes, where the caches are filled with uncoded data. We provide the exact characterization of the rate-memory tradeoff for this problem, by deriving both the minimum average rate (for a uniform file popularity) and the minimum peak rate required on the bottleneck link for a given cache size available at each user. In particular, we propose a novel caching scheme, which strictly improves the state of the art by exploiting commonality among user demands. We then demonstrate the exact optimality of our proposed scheme through a matching converse, by dividing the set of all demands into types, and showing that the placement phase in the proposed caching scheme is universally optimal for all types. Using these techniques, we also fully characterize the rate-memory tradeoff for a decentralized setting, in which users fill out their cache content without any coordination. [ABSTRACT FROM AUTHOR]

A fog-aided wireless network architecture is studied in which edge nodes (ENs), such as base stations, are connected to a cloud processor via dedicated fronthaul links while also being endowed with caches. Cloud processing enables the centralized implementation of cooperative transmission strategies at the ENs, albeit at the cost of an increased latency due to fronthaul transfer. In contrast, the proactive caching of popular content at the ENs allows for the low-latency delivery of the cached files, but with generally limited opportunities for cooperative transmission among the ENs. The interplay between cloud processing and edge caching is addressed from an information-theoretic viewpoint by investigating the fundamental limits of a high signal-to-noise-ratio metric, termed normalized delivery time (NDT), which captures the worst case coding latency for delivering any requested content to the users. The NDT is defined under the assumptions of either serial or pipelined fronthaul-edge transmission, and is studied as a function of fronthaul and cache capacity constraints. Placement and delivery strategies across both fronthaul and wireless, or edge, segments are proposed with the aim of minimizing the NDT. Information-theoretic lower bounds on the NDT are also derived. Achievability arguments and lower bounds are leveraged to characterize the minimal NDT in a number of important special cases, including systems with no caching capabilities, as well as to prove that the proposed schemes achieve optimality within a constant multiplicative factor of 2 for all values of the problem parameters. [ABSTRACT FROM PUBLISHER]

We consider a system, comprising a library of N files (e.g., movies) and a wireless network with a K_{T} transmitters, each equipped with a local cache of size of M_{T} files and a KR receivers, each equipped with a local cache of size of MR files. Each receiver will ask for one of the $N$ files in the library, which needs to be delivered. The objective is to design the cache placement (without prior knowledge of receivers’ future requests) and the communication scheme to maximize the throughput of the delivery. In this setting, we show that the sum degrees-of-freedom (sum-DoF) of $\min \left \{{\frac {K_{T} M_{T}+K_{R} M_{R}}{N},K_{R}}\right \}$ is achievable, and this is within a factor of 2 of the optimum, under uncoded prefetching and one-shot linear delivery schemes. This result shows that (i) the one-shot sum-DoF scales linearly with the aggregate cache size in the network (i.e., the cumulative memory available at all nodes), (ii) the transmitters’ caches and receivers’ caches contribute equally in the one-shot sum-DoF, and (iii) caching can offer a throughput gain that scales linearly with the size of the network. To prove the result, we propose an achievable scheme that exploits the redundancy of the content at transmitter’s caches to cooperatively zero-force some outgoing interference, and availability of the unintended content at the receiver’s caches to cancel (subtract) some of the incoming interference. We develop a particular pattern for cache placement that maximizes the overall gains of cache-aided transmit and receive interference cancellations. For the converse, we present an integer optimization problem which minimizes the number of communication blocks needed to deliver any set of requested files to the receivers. We then provide a lower bound on the value of this optimization problem, hence leading to an upper bound on the linear one-shot sum-DoF of the network, which is within a factor of 2 of the achievable sum-DoF. [ABSTRACT FROM AUTHOR]

We consider a wireless device-to-device network, where $n$ nodes are uniformly distributed at random over the network area. We let each node caches M$ files from a library of size m\geq M$ . Each node in the network requests a file from the library independently at random, according to a popularity distribution, and is served by other nodes having the requested file in their local cache via (possibly) multihop transmissions. Under the classical “protocol model” of wireless networks, we characterize the optimal per-node capacity scaling law for a broad class of heavy-tailed popularity distributions, including Zipf distributions with exponent less than one. In the parameter regime of interest, i.e., m=o(nM) for heavy-tailed popularity distributions. This scaling is constant with $n$ , thus yielding throughput scalability with the network size. Furthermore, the multihop capacity scaling can be significantly better than for the case of single-hop caching networks, for which the per-node capacity is $\Theta (M/m)$ . The multihop capacity scaling law can be further improved for a Zipf distribution with exponent larger than some threshold > 1, by using a decentralized random caching uniformly across a subset of most popular files in the library. Namely, ignoring a subset of less popular files (i.e., effectively reducing the size of the library) can significantly improve the throughput scaling while guaranteeing that all nodes will be served with high probability as $n$ increases. [ABSTRACT FROM PUBLISHER]

We consider a network consisting of a file server connected through a shared link to a number of users, each equipped with a cache. Knowing the popularity distribution of the files, the goal is to optimally populate the caches, such as to minimize the expected load of the shared link. For a single cache, it is well known that storing the most popular files is optimal in this setting. However, we show here that this is no longer the case for multiple caches. Indeed, caching only the most popular files can be highly suboptimal. Instead, a fundamentally different approach is needed, in which the cache contents are used as side information for coded communication over the shared link. We propose such a coded caching scheme and prove that it is close to optimal. [ABSTRACT FROM AUTHOR]

We study a noiseless broadcast link serving K users whose requests arise from a library of N files. Every user is equipped with a cache of size M files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most N/M file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file F scales to infinity. The asymptotic coding gain obtained is roughly t=KM/N . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets F is a function of the system parameters . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of ({4}/{3})g is at least O(({g}/{K})(N/M)^{g-1})$ . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters. [ABSTRACT FROM AUTHOR]

caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to locally deliver the part of the content, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider, in this paper, a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both the layers can simultaneously operate at approximately the minimum rate. [ABSTRACT FROM AUTHOR]

Video on-demand streaming from Internet-based servers is becoming one of the most important services offered by wireless networks today. In order to improve the area spectral efficiency of video transmission in cellular systems, small cells heterogeneous architectures (e.g., femtocells, WiFi off-loading) are being proposed, such that video traffic to nomadic users can be handled by short-range links to the nearest small cell access points (referred to as “helpers”). As the helper deployment density increases, the backhaul capacity becomes the system bottleneck. In order to alleviate such bottleneck we propose a system where helpers with low-rate backhaul but high storage capacity cache popular video files. Files not available from helpers are transmitted by the cellular base station. We analyze the optimum way of assigning files to the helpers, in order to minimize the expected downloading time for files. We distinguish between the uncoded case (where only complete files are stored) and the coded case, where segments of Fountain-encoded versions of the video files are stored at helpers. We show that the uncoded optimum file assignment is NP-hard, and develop a greedy strategy that is provably within a factor 2 of the optimum. Further, for a special case we provide an efficient algorithm achieving a provably better approximation ratio of 1-\left (1-1/d \right)^d, where d is the maximum number of helpers a user can be connected to. We also show that the coded optimum cache assignment problem is convex that can be further reduced to a linear program. We present numerical results comparing the proposed schemes. [ABSTRACT FROM PUBLISHER]

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. The network performance is described by the 2^n\times n-dimensional caching capacity region of the wireless network. We provide an inner bound on this caching capacity region, and, in the high path-loss regime, a matching (in the scaling sense) outer bound. For large path-loss exponent, this provides an information-theoretic scaling characterization of the entire caching capacity region. The proposed communication scheme achieving the inner bound shows that the problems of cache selection and channel coding can be solved separately without loss of order-optimality. On the other hand, our results show that the common architecture of nearest-neighbor cache selection can be arbitrarily bad, implying that cache selection and load balancing need to be performed jointly. [ABSTRACT FROM PUBLISHER]