We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users accessing content from a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to each of its associated caches. We develop a model that captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multi-path routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization as a non-convex, non-linear mixed-integer program. We prove that it is NP-hard under both multicast/unicast modes-even when the caches have a large capacity and storage costs are linear-and develop greedy algorithms that have provable performance bounds for the case of uncapacitated caches. Finally, we propose heuristics with low computational complexity for the capacitated cache case as well as for the case of convex storage costs. Systematic evaluations based on real-world data demonstrate the effectiveness of our approach, compared to the existing caching schemes.

We consider the problem of proactive (i.e. predictive) content caching that is aware of the costs of retention of the content in the cache. Prior work on caching (whether proactive or reactive) does not explicitly take into account the storage cost due to the duration of time for which a content is cached. This new problem, which we call retention aware caching, is motivated by two recent technological developments that are described in the paper: cloud storage rental costs and flash memory damage. We consider a hierarchical network consisting of a server connected to a number of cache-enabled nodes, located either at the edge of a network (e.g. base stations) or in the core of a data center. There are two types of network costs: storage cost at the caches and download cost from the server. We formulate the problem of proactive retention aware data caching (PRAC), which minimizes the total cost subject to the node capacity constraints. We first prove that PRAC is NP-Hard in general and then analyze PRAC for two cases: (1) linear storage cost, (2) convex storage cost. We show that PRAC admits efficient polynomial time algorithms when the storage cost is linear in retention times and caches have a large capacity. Furthermore, we derive bounds on the performance of PRAC for the case when the storage cost is a practically motivated convex function. Numerical evaluations demonstrate that PRAC outperforms other state-of-the-art caching policies for a wide range of parameters of interest.

We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users connected to a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access transmissions costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to its associated caches. We develop a model that captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multipath routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization (PRRO) as a non-convex, non-linear mixed-integer program. We prove that it is NP-Hard under both multicast/unicast modes, even when the caches have a large capacity, and develop a greedy algorithm that has provable performance bounds. Finally, we propose a heuristic for the capacitated cache case that has low computational complexity. Systematic evaluations including real data sets demonstrate the effectiveness of our approach, compared to the existing caching schemes.

Caches in Content-Centric Networks (CCN) are increasingly adopting flash memory based storage. The current flash cache technology stores all files with the largest possible “expiry date,” i.e., the files are written in the memory so that they are retained for as long as possible. This, however, does not leverage the CCN data characteristics where content is typically short-lived and has a distinct popularity profile. Writing files in a cache using the longest retention time damages the memory device thus reducing its lifetime. However, writing using a small retention time can increase the content retrieval delay, since, at the time a file is requested, the file may already have been expired from the memory. This motivates us to consider a joint optimization wherein we obtain optimal policies for jointly minimizing the content retrieval delay (which is a network-centric objective) and the flash damage (which is a device-centric objective). Caching decisions now not only involve what to cache but also for how long to cache each file. We design provably optimal policies and numerically compare them against prior policies.

Caches in Content-Centric Networks (CCN) are increasingly adopting flash memory based storage owing to its efficiency. The current flash cache technology stores all files with the largest possible "expiry date," i.e., the files are written in the memory so that they are retained for as long as possible. This, however, does not suit the CCN data characteristics where contents are typically short-lived and have a distinct popularity profile. Writing files in cache using the longest retention time damages the flash memory thus reducing the flash lifetime. However, writing using a small retention time can increase the content retrieval delay, since, at the time a file is requested, the file may already have been expired from the memory. This motivates us to propose a joint optimization wherein we obtain optimal policies for jointly minimizing the content retrieval delay (which is a network-centric objective) and the flash damage (which is a device centric objective). Caching decisions now not only involve what to cache and where to cache but also for how long is each file cached. The optimality of our policies are shown analytically, and are compared against prior policies using simulations.

Much work has been done on understanding and predicting human mobility in time. In this work, we are interested in obtaining a set of users who are spatio-temporally most similar to a query user. We propose an efficient way of user data representation called Spatio-Temporal Signatures to keep track of complete record of user movement. We define a measure called Spatio-Temporal similarity for comparing a given pair of users. Although computing exact pairwise Spatio-Temporal similarities between query user with all users is inefficient, we show that with our hybrid pruning scheme the most similar users can be obtained in logarithmic time with in a (1+\epsilon) factor approximation of the optimal. We are developing a framework to test our models against a real dataset of urban users.

In-network function computation (INFC) is becoming an essential aspect of large database systems where the data is distributed over the network. Such situations arise often in resource constrained wireless sensor network making them a natural candidate for INFC. We study the problem of maximizing the rate of INFC in wireless networks. In this paper, we develop a functional flow model for INFC when the function computation sequence is represented by a directed acyclic graph. We propose a linear program formulation to maximize the rate of INFC over all possible embeddings. We also formulate a mixed integer linear program (MILP) for maximizing the rate of computation for a single embedding on a capacity constrained wireless network. The MILP for finding the single embedding that yields maximum rate turns out to be NP hard; we develop a heuristic to solve this problem by formulating a linear program. We provide numerical results to illustrate the performance of these formulations.