{'fraction_non_alphanumeric': 0.047925568318443294, 'fraction_numerical': 0.012799881619591957, 'mean_word_length': 4.117758424839076, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A TTL-based Approach for Content Placement in Edge Networks

Edge networks are promising to provide better services to users by provisioning computing and storage resources at the edge of networks. However, due to the uncertainty and diversity of user interests, content popularity, distributed network structure, cache sizes, it is challenging to decide where to place the content, and how long it should be cached. In this paper, we study the utility optimization of content placement at edge networks through timer-based (TTL) policies. We propose provably optimal distributed algorithms that operate at each network cache to maximize the overall network utility. Our TTL-based optimization model provides theoretical answers to how long each content must be cached, and where it should be placed in the edge network. Extensive evaluations show that our algorithm significantly outperforms path replication with conventional caching algorithms over some network topologies.


INTRODUCTION
Content distribution has become a dominant application in today's Internet. Much of these contents are delivered by Content Distribution Networks (CDNs), which are provided by Akamai, Amazon etc * Authors with equal contribution [23]. There usually exists a stringent requirement on the latency between service provider and end users for these applications. CDNs use a large network of caches to deliver content from a location closer to the end users. If the user's requests are served by the cache (i.e., cache hit), the user experiences a faster response time. This also reduces the bandwidth requirements at the central content repository. Content distribution also plays a significant role in sensor networks, where a large amount of contents need to be efficiently processed and stored.
With the aggressive increase in Internet traffic over past years [7], CDNs need to host contents from thousands of regions belonging to web sites of thousands of content providers. Furthermore, each content provider may host a large variety of contents, including videos, music, images and webs. Such an increasing diversity in content services requires CDNs to provide different quality of service to varying content classes and applications with different access characteristics and performance requirements. Significant economic benefits and important technical gains have been observed with the deployment of service differentiation [13]. While a rich literature has studied the design of fair and efficient caching algorithms for content distribution, little work has paid attention to the provision of multi-level services in cache networks.
Managing cache networks requires policies to route the endusers' requests to the local distributed caches, as well as caching algorithms to ensure availability of requested content in the caches. In general, there are two models for studying the performance of caching algorithms. One is caching eviction policy, since the cache size is usually much smaller than the total amount of content, some contents need to be evicted if the requested content is not in the cache (i.e., cache miss). Some well known content eviction policies are Least-Recently-Used (LRU) [18], Least-Frequently-Used (LFU) [8], First In First Out (FIFO), and RANDOM [8]. Exact analysis of these algorithms has proven to be difficult, even under most simple Independence Reference Model (IRM) [8], where the request generation process assumes independent between different contents. The strongly coupled nature of these eviction algorithms makes implementation of differential services challenging.
Another class of caching eviction policies are timer-based, i.e., Time-To-Live (TTL) [6,11,16]. Under TTL caches, each content is associated with a timer upon request and evicted from the cache on timer expiry, independent of other contents. In this case, the analysis of these policies is simple since the eviction of contents are decoupled from each other. The accuracy of these analyses has been theoretically justified under IRM [11] and stationary requests [22], and numerically verified under renewal processes [17].
Most results in the literature are obtained as a result of analyzing a single cache. When a cache network is considered, independence across different caches is usually assumed. Again, it is hard to analyze most conventional caching algorithms, such as LRU, FIFO and RANDOM, but some accurate results for TTL caches are available [4,16]. However, it has been observed [26] that performance gains can be obtained from algorithms if decision-making is coupled at different caches.
In this paper, we consider a TTL cache network. Any node in the network can generate a request for a content, which is forwarded along a fixed path towards the server. The forwarding stops upon a cache hit, i.e., the requested content is found in a node on the path. When such a cache hit occurs, the content is associated with a timer and sent over the reverse path to the node initializing the request. This raises the following questions: First, under limited cache capacity, what content should be cached to enhance performance, e.g., with respect to (w.r.t.) hit probability? Second, presuming a content is to be cached, when should it be cached? Finally, as decision-making is coupled at different caches, upon a cache hit at one node, should the content also be cached at some other node? If so, where should the content be cached in the network? Answering these questions in an affirmative way can provide new insights in cache network design; however, it may also increase the complexity and hardness of the analysis.
Our goal is to provide thorough and rigorous answers to these three questions: What, when and where to cache? To that end, we consider moving the content one cache up if there is a cache hit on it and pushing the content one cache down once its timer expires in the cache hierarchy, since the recently evicted content may still be in demand. This leads to the "Move Copy Down with Push" (MCDP) policy. While pushing the copy down may improve the system performance, it induces more operation cost in the system. We can also consider another policy "Move Copy Down" (MCD) under which content is evicted upon timer expiry. These will be described in detail in Section 3.
We first focus on a linear cache network. In a linear cache network, all requests are made at one node, and if the content is not present in the network, served at the other end. We first consider a utility-driven caching framework, where each content is associated with a utility and content is managed with a timer whose duration is set to maximize the aggregate utility for all contents over the cache network. Building on MCDP and MCD models, we formulate the optimal TTL policy as a non-convex optimization problem in Section 4.3. A first contribution of this paper is to show that this non-convex problem can be transformed into a convex one by change of variables. We further develop online algorithms for content management over linear cache networks, and show that this algorithm converges to the optimal solution through Lyapunov functions.
Utilities characterize user satisfaction and provide an implicit notion of fairness. However, since we consider cache network, content management also induces costs, such as search cost for finding the requested content on the path, fetching cost to serve the content to the user that requested it, and moving cost upon cache hit or miss due to caching policy. We fully characterize these costs and formulate a cost minimization problem in Section 4.4.
Next, informed by our results for linear cache networks, we consider general cache networks. In a general cache network, requests for content can be made at any node and content servers can reside at any node. Requests are propagated along a fixed path from end user to a server. In Section 5.2, we assume that the content requested along different paths are distinct. In this case, we can simply extend our results from Section 4.3, since the general network can be treated as a union of different paths. The more interesting case where common content is requested along different paths is considered in Section 5.3. This introduces non-convex constraints so that the utility maximization problem is non-convex. We show that although the original problem is non-convex, the duality gap is zero. Based on this, we design a distributed iterative primal-dual algorithm for content management in the general cache network.
In Section 6, we include some generalizations. In Section 6.1, we discuss how our framework can be directly mapped to content distributions in CDNs, ICNs/CCNs etc. In Section 6.2, we discuss how our framework can be generalized to a considerably different scenario where contents are generated from disparate and dispersed sources such as sensors, users and devices. The distributed infrastructure of a typical service (e.g., wireless sensor networks) has a tree-structured model. The sensors generate, process and send content to other nodes in the network. Each node can store or process (e.g., compress) the content further but typically has limited resources (e.g., node energy, bandwidth). This results in the need for efficient content (data) analytics. We discuss how to generalize our optimization framework to consider content caching and compression in a wireless sensor network (WSN) in Section 6.2. We capture the satisfaction and fairness of a cache hit through utility function, and characterize the content compression and communication over the WSN through cost function. We investigate the tradeoff among caching, compression and communication through an optimization framework, which turns out to be a non-convex problem. We show that it can be equivalently transformed into a convex optimization problem. Numerical results are given on how to optimize the performance.
Conclusions are given in Section 7. Some additional discussions and proofs are provided in Appendix 8.

RELATED WORK
There is a rich literature on the design, modeling and analysis of cache networks, including TTL caches [4,15,16,33], optimal caching [19] and routing policies [20]. In particular, Rodriguez et al. [33] analyzed the advantage of pushing content upstream, Berger et al. [4] characterized the exactness of TTL policy in a hierarchical topology. A unified approach to study and compare different caching policies is given in [17] and an optimal placement problem under a heavy-tailed demand has been explored in [14].
Dehghan et al. [10] as well as Abedini and Shakkottai [1] studied joint routing and content placement with a focus on a bipartite, single-hop setting. Both showed that minimizing single-hop routing cost can be reduced to solving a linear program. Ioannidis and Yeh [20] studied the same problem under a more general setting for arbitrary topologies.
An adaptive caching policy for a cache network was proposed in [19], where each node makes a decision on which item to cache and evict. An integer programming problem was formulated by characterizing the content transfer costs. Both centralized and complex distributed algorithms were designed with performance guarantees. This work complements our work, as we consider TTL cache and control the optimal cache parameters through timers to maximize the sum of utilities over all contents across the network. However, [19] proposed only approximate algorithms while our timer-based models enable us to design optimal solutions since content occupancy can be modeled as a real variable (e.g. a probability). This allows us to change the workload in the network in a natural way.
Closer to our work, a utility maximization problem for a single cache was considered under IRM [9] and stationary requests [2], while [14] maximized the hit probabilities under heavy-tailed demands over a single cache. None of these approaches generalizes to cache networks, which leads to non-convex formulations (See Section 4.2, Section 5.3, Section 6.2.5, Section 6.2.6); addressing this lack of convexity in its full generality, for arbitrary network topologies, overlapping paths and request arrival rates, is one of our technical contributions.

TECHNICAL PRELIMINARIES
We consider a cache network, represented by a graph G = (V , E). We assume a library of n unique contents, denoted as D = {d 1 , · · · , d n } with |D | = n. Each node can store a finite number of contents, B v is the cache capacity at node v ∈ V . The network serves content requests routed over the graph G. A request is determined by the item requested by the user and the path that the request follows; this will be described in detail in Section 3.2.1. We assume that the request processes for distinct contents are described by independent Poisson processes with arrival rate λ i for content i ∈ D. Denote Λ = n i=1 λ i . Then the popularity (request probability) of content i satisfies [3]

TTL Policy for Individual Caches
Consider the cache at node j, each content i is associated with a timer T i j under TTL cache policy. While we focus on node j, we omit the subscript .j . Consider the event when content i is requested. There are two cases: (i) if content i is not in the cache, content i is inserted into the cache and its timer is set to T i ; (ii) if content i is in the cache, its timer is reset to T i . The timer decreases at a constant rate and the content is evicted once its timer expires.

Replication Strategy for Cache Networks
In a cache network, upon a cache hit, we need to specify how content is replicated along the reverse path towards the user that sent the request.
3.2.1 Content Request. The network serves requests for contents in D routed over the graph G. Any node in the network can generate a request for a content, which is forwarded along a fixed and unique path from the user towards a terminal node that is connected to a server that always contains the content. Note that the request need not reach the end of the path, it stops upon hitting a cache that stores the content. At that point, the requested content is propagated over the path in the reverse direction to the node that requested it.
To be more specific, a request (v, i, p) is determined by the node, v, that generated the request, the requested content, i, and the path, p, that the request is routed. We denote a path p of length We assume that path p is loop-free and the terminal node v 1p is the only node on path p that access the server for content i.

Replication Strategy.
We consider TTL cache policies at every node in the cache network G with deterministic timers independent for each content. Suppose content i is requested and routed along path p. There are two cases: (i) content i is not in any cache along path p, in which case content i is fetched from the server and inserted into the first cache (denoted by cache 1) 1 on the path. Its timer is set to T i1 ; (ii) if content i is in cache l along path p, we consider the following strategies [33] • Move Copy Down (MCD): content i is moved to cache l + 1 preceding cache l in which i is found, and the timer at cache l + 1 is set to T i(l +1) . Content i is discarded once the timer expires; • Move Copy Down with Push (MCDP): MCDP behaves the same as MCD upon a cache hit. However, if the timer T il expires, content i is pushed one cache back to cache l − 1 and the timer is set to T i(l −1) .

Utility Function
Utility functions capture the satisfaction perceived by a user after being served a content. We associate each content i ∈ D with a utility function U i : [0, 1] → R that is a function of hit probability h i . U i (·) is assumed to be increasing, continuously differentiable, and strictly concave. In particular, for our numerical studies, we focus on the widely used β-fair utility functions [35] given by where w i > 0 denotes a weight associated with content i.

LINEAR CACHE NETWORK
We begin with a linear cache network, i.e., there is a single path between the user and the server, composed of |p| = L caches labeled 1, · · · , L. A content enters the cache network via cache 1, and is promoted to a higher index cache whenever a cache hit occurs. In the following, we consider the MCDP and MCD replication strategies when each cache operates with a TTL policy.

Stationary Behaviors
Remark 1. [18] considered two caching policies LRU(m) and h-LRU. Though the policies differ from MCDP and MCD, respectively, the stationary analyses are similar. We present our results here for completeness, which will be used subsequently in the paper.

MCDP.
Requests for content i arrive according to a Poisson process with rate λ i . As described earlier, under TTL, content i spends a deterministic time in a cache if it is not requested, independent of all other contents. We denote the timer as T il for content i in cache l on the path p, where l ∈ {1, · · · , |p|}.
Denote by t i k the k-th time that content i is either requested or the timer expires. For simplicity, we assume that content is in cache 0 (i.e., server) when it is not in the cache network. We can then define a discrete time Markov chain (DTMC) {X i k } k ≥0 with |p| + 1 states, where X i k is the cache index that content i is in at time t i k . The event that the time between two requests for content i exceeds T il occurs with probability e −λ i T il ; consequently we obtain the transition probability matrix of {X i k } k ≥0 and compute the stationary distribution. We relegate the details to Appendix 8.1.1. The timer-average probability that content i is in cache l ∈ {1, · · · , |p|} is where h il is also the hit probability for content i at cache l .

MCD.
Again, under TTL, content i spends a deterministic time T il in cache l if it is not requested, independent of all other contents. We define a DTMC {Y i k } k ≥0 by observing the system at the time that content i is requested. Similar to MCDP, if content i is not in the cache network, it is in cache 0; thus we still have |p| + 1 states. If Y i k = l, then the next request for content i comes within time T il with probability 1 − e −λ i T il , and Y i k +1 = l + 1, otherwise Y i k +1 = 0 due to the MCD policy. We can obtain the transition probability matrix of {Y i k } k ≥0 and compute the stationary distribution, details are available in Appendix 8.1.2.
By PASTA property [29], we immediately have that the stationary probability that content i is in cache l ∈ {1, · · · , |p|} is given as

From Timer to Hit Probability
We consider a TTL cache network where requests for different contents are independent of each other and each content i is associated with a timer T il at each cache l ∈ {1, · · · , |p|} on the path. Denote T i = (T i1 , · · · ,T i |p | ) and T = (T 1 , · · · ,T n ). From (3) and (4), the overall utility in the linear network is given as where 0 < ψ ≤ 1 is a discount factor capturing the utility degradation along the request's routing direction. Since each cache is finite in size, there is a capacity constraint as follows Therefore, the optimal TTL policy for content placement in the linear network should solve the following optimization problem in terms of (T 1 , · · · ,T n ) : where h il (T ) are given in (3) and (4) for MCDP and MCD, respectively. However, (7) is a non-convex optimization with a non-linear constraint. Our objective is to characterize the optimal timers for different contents across the network. To that end, it is helpful to express (7) in terms of hit probabilities. In the following, we will discuss how to change the variables from timer to hit probability for MCDP and MCD, respectively.

MCDP.
Since 0 ≤ T il ≤ ∞, it is easy to check that 0 ≤ h il ≤ 1 for l ∈ {1, · · · , |p|} from (3a) and (3b). Furthermore, it is clear that there exists a mapping between (h i1 , · · · , h i |p | ) and (T i1 , · · · ,T i |p | ). By simple algebra, we can take the logarithm to obtain Note that must hold during the operation, which is always true given the caching policy we consider here.

MCD.
Similarly, from (4a) and (4b), we simply check that there exists a mapping between (h i1 , · · · , h i |p | ) and (T i1 , · · · ,T i |p | ). Since T il ≥ 0, by (4a), we have By simple algebra, we can take the logarithm to obtain must hold during the operation, which is always true given the caching policy we consider here.

Maximizing Overall Utilities
With the change of variables discussed in Section 4.2, we can reformulate (7) for MCDP and MCD, respectively. (8) and (9), the optimization problem (7) under MCDP becomes

MCDP. Given
where (13b) is the cache capacity constraint and (13c) is due to the variable exchanges under MCDP as discussed in (9). Proposition 1. Since the feasible sets are convex and the objective function is strictly concave and continuous, the optimization problem defined in (13) under MCDP has a unique global optimum. (10), (11) and (12), the optimization problem (7) under MCD becomes

MCD. Given
where (14b) is the cache capacity constraint, (14c) and (14d) are due to the variable exchanges under MCD as discussed in (10) and (12).
Since the feasible sets are convex and the objective function is strictly concave and continuous, the optimization problem defined in (14) under MCD has a unique global optimum.

Online Algorithm.
In Sections 4.3.1 and 4.3.2, we formulated convex utility maximization problems with a fixed cache size. However, system parameters (e.g. cache size and request processes) can change over time, so it is not feasible to solve the optimization offline and implement the optimal strategy. Thus, we need to design online algorithms to implement the optimal strategy and adapt to the changes in the presence of limited information. In the following, we develop such an algorithm for MCDP. A similar algorithm exists for MCD and is omitted here due to space constraints. Primal Algorithm: We aim to design an algorithm based on the optimization problem in (13), which is the primal formulation. Denote We first define the following objective function where C l (·) andC i (·) are convex and non-decreasing penalty functions denoting the cost for violating corresponding constraints (13b) and (13c). Therefore, it is clear that Z (·) is strictly concave. Hence, a natural way to obtain the maximal value of (15) is to use the standard gradient ascent algorithm to move the variable h il for i ∈ D and l ∈ {1, · · · , |p|} in the direction of the gradient, given as where U ′ i (·), C ′ l (·) andC ′ i (·) denote the partial derivative w.r.t. h il . Since h il indicates the probability that content i is in cache l, then i ∈D h il is the expected number of contents currently in cache l, denoted as B curr,l . Therefore, the primal algorithm for MCDP is given by , l = 1; where ζ il ≥ 0 is the step-size parameter, and k is the iteration number incremented upon each request arrival.
Theorem 4.1. The primal algorithm given in (17) converges to the optimal solution given sufficient small step-size parameter ζ il .
Proof. Since U i (·) is strictly concave, C l (·) andC i (·) are convex, then (15) is strictly concave, hence there exists a unique maximizer. Denote it as h * . Define the following function

Model Validations and Insights.
In this section, we validate our analytical results with simulations for MCDP. We consider a linear three-node cache network with cache capacities B l = 30, l = 1, 2, 3. The total number of unique contents considered in the system is n = 100. We consider the Zipf popularity distribution with parameter α = 0.8. W.l.o.g., we consider a log utility function, and discount factor ψ = 0.6. W.l.o.g., we assume that requests arrive according to a Poisson process with aggregate request rate Λ = 1.
We first solve the optimization problem (13) using a Matlab routine fmincon. Then we implement our primal algorithm given in (17), where we take the following penalty functions [35] From Figure 1, we observe that our algorithm yields the exact optimal and empirical hit probabilities under MCDP. Figure 2 shows the probability density for the number of contents in the cache network 2 . As expected, the density is concentrated around their corresponding cache sizes.
We further characterize the impact of the discount factor ψ on performance. We consider different values of ψ . Figure 3 shows the result for ψ = 0.1. We observe that as ψ decreases, if a cache hit occurs in a lower index cache, the most popular contents are likely to be cached in higher index cache (i.e., cache 3) and least popular contents are likely to be cached in lower index cache (cache 1). This provides significant insights on the design of hierarchical caches, since in a linear cache network, a content enters the network via the first cache, and only advances to higher index cache upon a cache hit, then under a stationary request process (e.g., Poisson process), only popular contents will be promoted to higher index cache, which is consistent with what we observe in Figure 3. A similar phenomenon has been observed in [18,27] through numerical studies, while we characterize this through utility optimization. Second, we see that as ψ increases, the performance difference between different caches are decreasing, and they become identical when ψ = 1. This is because as ψ increases, the performance degradation for cache hits on a lower index cache decreases and there is no difference between them when ψ = 1. Due to space constraints, the results for ψ = 0.4, 0.6, 1 are given in Appendix 8.2.

Minimizing Overall Costs
In Section 4.3, we focused on maximizing the sum of utilities across all contents over the cache network, which captures user satisfactions. However, communication costs for content transfers across the network are also critical in many network applications. This cost includes (i) the search cost for finding the requested content in the network; (ii) the fetching cost to serve the content to the user; and (iii) the moving cost for cache inner management due to a cache hit or miss.

Search and Fetching
Cost. Requests from user are sent along a path until it hits a cache that stores the requested content. We define search cost (fetching cost) as the cost for finding (serving) the requested content in the cache network (to the user). Consider the cost as a function c s (·) (c f (·)) of the hit probabilities. Then the expected search cost across the network is given as Similarly for fetching cost F MCD and F MCDP with function c f (·).

Moving
Cost. Under TTL, upon a cache hit, the content either moves to a higher index cache or stays in the current one, and upon a cache miss, the content either moves to a lower index cache (MCDP) or is discarded from the network (MCD). We define moving cost as the cost due to cache management upon a cache hit or miss. Consider the cost as a function c m (·) of the hit probabilities. MCD: Under MCD, since the content is discarded from the network once its timer expires, moving costs are only incurred at each cache hit. To that end, the requested content either moves to a higher index cache if it was in cache l ∈ {1, · · · , |p| − 1} or stays in the same cache if it was in cache |p|. Then the expected moving cost across the network for MCD is given as MCDP: Under MCDP, besides moving the requested content to a higher index cache upon a cache hit, each content also moves to a lower index cache when its timer expires. Thus, we also need to capture moving costs due to timer expiry. We characterize them in terms of timers, i.e.,

Optimization.
Our goal is to determine optimal timer values at each cache in a linear cache network so that the total costs are minimized. To that end, we formulate the following optimization problem for MCDP L-C-MCDP: min S MCDP + F MCDP + M MCDP (22a) Constraints in (13).
A similar optimization problem can be formulated for MCD and is omitted here due to space constraints. Remark 3. As discussed in Remark 2, we cannot express moving cost of MCDP (21) in terms of hit probabilities, hence, we are not able to transform the optimization problem (22) for MCDP into a convex one through a change of variables as we did in Section 4.3. Solving the non-convex optimization (22) is a subject of future work. However, we note that moving costs of MCD (20) are simply a function of hit probabilities and the corresponding optimization problem is convex so long as the cost functions are convex.

GENERAL CACHE NETWORKS
In Section 4, we considered linear cache networks and characterized the optimal TTL policy for content when coupled with MCDP and MCD. We will use these results and insights to extend this to general cache networks in this section.

Contents, Servers and Requests
Consider the general cache network described in Section 3. Denote by P the set of all requests, and P i be the set of requests for content i. Suppose a cache node v in G serves two requests (v 1 , i 1 , p 1 ) and (v 2 , i 2 , p 2 ), then there are two cases: (i) non-common requested content, i.e., i 1 i 2 ; and (ii) common requested content, i.e., i 1 = i 2 .

Non-common Requested Content
We first consider the case that each node serves requests for different contents from each request (v, i, p) passing through it. Since there is no coupling between different requests (v, i, p), we can directly generalize the results for linear cache networks in Section 4. Hence, given the utility maximization formulation in (13), we can directly formulate the optimization problem for MCDP as where (23b) is the cache capacity constraint and (23c) follows the discussion for MCDP in (9).
Proposition 3. Since the feasible sets are convex and the objective function is strictly concave and continuous, the optimization problem defined in (23) under MCDP has a unique global optimum.
We can similarly formulate a utility maximization optimization problem for MCD for a general cache network. We relegate this to Appendix 8.5.1.

Model Validations and Insights.
We consider a seven-node binary tree network, shown in Figure 4 with node set {1, · · · , 7}.

Common Requested Contents
Now consider the case where different users share the same content, e.g., there are two requests (v 1 , i, p 1 ) and (v 2 , i, p 2 ). Suppose that cache l is on both paths p 1 and p 2 , where v 1 and v 2 request the same content i. If we cache separate copies on each path, results from the previous section apply. However, maintaining redundant copies in the same cache decreases efficiency. A simple way to deal with that is to only cache one copy of content i at l to serve both requests from v 1 and v 2 . Though this reduces redundancy, it complicates the optimization problem.
In the following, we formulate a utility maximization problem for MCDP with TTL caches, where all users share the same requested contents D. G-U-MCDP: where (24b) ensures that only one copy of content i ∈ D is cached at node j for all paths p that pass through node j. This is because i j ) is the overall hit probability of content i at node j over all paths. (24c) is the cache capacity constraint and (24d) is the constraint from MCDP TTL cache policy as discussed in Section 4.2.
Example 5.1. Consider two requests (v 1 , i, p 1 ) and (v 2 , i, p 2 ) with paths p 1 and p 2 which intersect at node j. Denote the corresponding path perspective hit probability as h i j , respectively. Then the term inside the outer summation of (24b) becomes 1 − (1 − h i j ), i.e., the hit probability of content i in node j.
Remark 4. Note that we assume independence between different requests (v, i, p) in (24), e.g., in Example 5.1, if the insertion of content i in node j is caused by request (v 1 , i, p 1 ), when the request (v 2 , i, p 2 ) comes, it is not counted as a cache hit from its perspective. Our framework still holds if we follow the logical TTL MCDP on linear cache networks. However, in that case, the utilities will be higher than the one we consider here.
Similarly, we can formulate a utility maximization optimization problem for MCD. This is relegated to Appendix 8.5.2. Proposition 4. Since the feasible sets are non-convex, the optimization problem defined in (24) under MCDP is a non-convex optimization problem.
In the following, we develop an optimization framework that can identify the non-convexity issue in this optimization problem and then solve it in a distributed way. To this end, we first introduce the Lagrangian function where the Lagrangian multipliers (price vector and price matrix) are ν = (ν j ) j ∈V , and µ = (µ ip ) i ∈D,p ∈ P .
The dual function d(ν, µ) is always convex in (ν, µ) regardless of the concavity of the optimization problem (24) [5]. Therefore, it is always possible to iteratively solve the dual problem using where γ l and η ip are the step sizes, and ∂L(ν,µ) ∂ν l and ∂L(ν,µ) ∂µ ip are the partial derivative of L(ν, µ) w.r.t. ν l and µ ip , respectively, satisfyting Sufficient and necessary conditions for the uniqueness of ν, µ are given in [25]. The convergence of the primal-dual algorithm consisting of (28) and (29) is guaranteed if the original optimization problem is convex. However, our problem is not convex. Nevertheless, in the following, we show that the duality gap is zero, hence (28) and (29) converge to the globally optimal solution. To begin with, we introduce the following results Theorem 5.2. [36] (Sufficient Condition). If the price based function h * (ν, µ) is continuous at one or more of the optimal lagrange multiplier vectors ν * and µ * , then the iterative algorithm consisting of (28) and (29) converges to the globally optimal solution. Theorem 5.3. [36] If at least one constraint of (24) is active at the optimal solution, the condition in Theorem 5.2 is also a necessary condition.
Hence, if we can show the continuity of h * (ν, µ) and the activity of the constraints of (24), then given Theorems 5.2 and 5.3, the duality gap is zero, i.e., (28) and (29) converge to the globally optimal solution.
Take the derivative of L(h, ν, µ) w.r.t. h (p) il for i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i , we have Setting (31) equal to zero, we obtain Consider the log utility function U ip (h il . Hence, from (32), we have Lemma 5.4. Constraints (24b) and (24c) cannot be both non-active, i.e., at least one of them is active.
Theorem 5.5. The hit probability h (p) il given in (33) is continuous in ν l and µ ip for all i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i in the feasible region R.
For case (i), we have which is clearly continuous in ν l , for all i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i .
Similarly for case (ii), we have which is also clearly continuous in µ ip , for all i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i . For case (iii), from (33), it is obvious that h il is is continuous in ν l and µ ip for all i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i .

Therefore, we know that h (p)
il is is continuous in ν l and µ ip for all i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i . □ Therefore, the primal-dual algorithm consisting of (28) and (29) converges to the globally optimal solution. Algorithm 1 summarizes the details of this algorithm.

Algorithm 1 Primal-Dual Algorithm
Input: ∀ν 0 , µ 0 ∈ R and h 0 Output: The optimal hit probabilities h Step il [t + 1] for i ∈ D, l ∈ {1, · · · , |p|} and p ∈ P i through (33); Second, update ν l [t + 1] and µ ip [t + 1] through (29) given h[t + 1], ν [t] and µ[t] for l ∈ V , i ∈ D and p ∈ P i 5.3.1 Model Validations and Insights. We evaluate the performance of Algorithm 1 on a seven-node binary tree cache network, shown in Figure 4. We assume that there are totally 30 unique contents in the system requested from four paths. The cache size is given as B v = 10 for v = 1, · · · , 7. We consider a log utility function and the popularity distribution over these contents is Zipf with parameter 0.8. W.l.o.g., the aggregate request arrival rate is 1. The discount factor ψ = 0.6.
We solve the optimization problem in (24) using a Matlab routine fmincon. Then we implement our primal-dual algorithm given in Algorithm 1. The result for path p 4 is presented in Figure 7. We observe that our algorithm yields the exact optimal hit probabilities under MCDP. Similar results hold for other three paths and hence are omitted here.

APPLICATIONS
The problem we considered so far is directly motived by and naturally captures many important realistic networking applications. These include the Web [6], the domain name system (DNS) [24,30], content distribution networks (CDNs) [28,34], information and content-centric networks (ICNs/CCNs) [21], named data networks (NDNs) [21], wireless sensor networks (WSNs) [12,31,32], and so on. In particular, we consider content distribution and WSNs in this section. These present hard problems: highly diverse traffic with different content types, such as videos, music and images, require CDNs to cache and deliver content using a shared distributed cache server infrastructure so as to obtain economic benefits; limited energy supply requires WSNs to efficiently store, process and transmit content. Our timer-based model with simple cache capacity and content processing energy constraints enable us to provide optimal and distributed algorithms for these applications.

Content Distribution
Content distribution is a dominant application in today's Internet.
Caches are widely used in networks to improve performance by storing information locally. For example, in modern CDNs with hierarchical topologies, requests for content can be served by intermediate caches placed at the edge server that acts as a designated source in the domain. Similarly, in ICNs and NDNs, named data are stored at designated servers. Requests for named data are routed to the server, which can be stored at intermediate routers to serve future requests. Both settings directly map to the problem we study here (Section 5.3).
Here we consider a general network topology with overlapping paths and common contents requested along different paths. Similar to (24) and Algorithm 1, a non-convex optimization problem can be formulated and a primal-dual algorithm can be designed, respectively. Due to space constraints, we omit the details. Instead, we show the performance of this general network.
We consider a two-dimensional square grid with 16 nodes, denoted as G = (V , E). We assume that there is a library of |D| = 30 unique contents. Each node has access to a subset of contents in the library. We assign a weight to each edge in E selected uniformly from the interval [1,20]. Next, we generate a set of requests in G as follows. To ensure that paths overlap, we randomly select a subset V ⊂ V with |Ṽ | = 12 nodes to generate requests. Each node inṼ can generate requests for contents in D following a Zipf distribution with parameter α = 0.8. Requests are then routed over the shortest path between the requesting node inṼ and the node in V that caches the content. Again, we assume that the aggregate request rate at each node inṼ is 1. Due to space constraints, we only present the performance of one particular path p = {3, 4, 8}, where node 3 initializes the requests and node 8 is the designated node that has access to the requested contents. Again, we observe that our algorithm yields the exact optimal hit probabilities under MCDP.

Wireless Sensor Networks
Another particular example of modern systems where caches are inherently integral components are wireless sensor networks (WSNs). Consider a WSN with a large number of sensors that can generate enormous amounts of content to serve the end users. On one hand, caches have been deployed in WSNs to reduce the latency. On the other hand, content compression has been widely used in WSNs to eliminate redundant information, which in turn improves caching efficiency.
In this section, we consider a general WSN and show how the cache network models discussed in Sections 4 and 5 can be applied to the WSN with content compression.
6.2.1 Caching and Compression. Again, we represent the network as a directed graph G = (V , E). For simplicity, we consider a tree-structured WSN, as shown in Figure 9. Each node is associated with a cache that is capable of storing a constant amount of content. Denote B v as the cache capacity at node v ∈ V . Let K ⊂ V be the set of leaf nodes with |K | = K . Furthermore, we assume that each node j that receives the content from leaf node k can compress it with a reduction ratio 3 δ k j , where 0 < δ k j ≤ 1, ∀k, j.

Content Generation and Requests.
We assume that leaf node k ∈ K continuously generates content, which will be active for a time interval W and requested by users outside the network. If there is no request for these content in that time interval, the generated content becomes inactive and discarded from the system. The generated content is compressed and cached along the path between the leaf node and the sink node when a request is made for the active content. Denote the path as p k = (1, · · · , |p k |) between leaf node k and the sink node. Since we consider a tree-structured network, the total number of paths is |K | = K, hence, w.l.o.g., K is also used to denote the set of all paths. Here, we consider the MCDP and MCD with TTL caching policy.
In WSN, each sensor (leaf node) generates a sequence of content that users are interested in. Different sensors may generate different types of contents, i.e., there is no common contents sharing between different sensors. Hence, the cache performance analysis in WSN can be mapped to the problem we considered in Section 5.2.
W.l.o.g., we consider a particular leaf node k and the content that is active and requested by the users. For simplicity, we drop the superscript .k and denote the path as p = (1, · · · , |p|), where cache |p| is the sink node that serves the requests and cache 1 is the leaf node that generates the content. Let the set of contents generated by leaf node k be D (p) and the request arrivals for D (p) follow a Poisson process with rate λ i for i ∈ D (p) .
Let h i j be the hit probability and the TTL timer associated with content i ∈ D (p) at node j ∈ {1, · · · , |p|}, respectively. Denote h for i ∈ D (p) and p ∈ K.

Utilities.
Following a similar argument with Section 5.2, the overall utilities for content i along path p is given as where the utilities not only capture the hit probabilities but also characterize the content quality degradation due to compression along the path.

Costs.
We consider the costs, e.g. delay, of routing the content along the path, which includes the cost to forward content to the node that caches it, the cost to search for the content along the path, and the cost to fetch the cached content to the users that sent the requests. Again, we assume that the per hop cost to transfer (search) the content along the path is a function c f (·) (c s (·)) of hit probabilities and compression ratios. Forwarding Costs: Suppose a cache hit for content i occurs on node j ∈ {1, · · · , |p|}, then the total cost to forward content i along p is given as Search Costs: Given a cache hit for content i on node j ∈ {1, · · · , |p|}, the total cost to search for content i along p is given as Fetching Costs: Upon a cache hit for content i on node j ∈ {1, · · · , |p|}, the total cost to fetch content i along p is given as 6.2.5 Optimization Formulation. Our objective is to determine a feasible TTL policy and compression ratio for content management in a tree-structured WSN to maximize the difference between utilities and costs, i.e., Hence, the optimal TTL policy and compression ratio for MCDP should solve the following optimization problem: where I(l, p) is the index of node j on path p and constraint (41c) ensures that the content will not be over compressed since the available energy O (p) is limited for path p, and c c (·) is the per unit energy consumption function for compression. Similarly, we can formulate an optimization problem for MCD. We relegate this formulation to Appendix 8.5.3.
It is easy to check that (41) is a non-convex problem. In the following, we transform it into a convex one through Boyd's method (Section 4.5 [5]). Delta node 4(Numerical) node 6(Numerical) node 7(Numerical) Figure 12: Compression ratio of MCDP under a seven-node WSN.
6.2.6 Convex Transformation. First, we define two new sets of variables for i ∈ D (p) , l ∈ {1, · · · , |p|} and p ∈ K as follows: and denote σ Then the objective function (40) can be transformed into Similarly, we can transform the constraints. Then we obtain the following transformed optimization problem WSN-T-MCDP: where I(l, p) is the index of node j on path p.
Theorem 6.1. The transformed optimization problems in (44) is convex σ and τ , when we consider the β-utility function with β ≥ 1 and increasing convex cost functions c f (·), c s (·) and c c (·). It can be easily checked that the objective function satisfies the second order condition [5] for σ and τ when the utility and cost functions satisfy the conditions. We omit the details due to space constraints. Proof. This is clear from the way we convexified the problem. □ 6.2.7 Online Algorithm. Following a similar argument in Section 4.3.3, we can also design online algorithms for the optimization problem (44). Due to space constraints, we omit the details and characterize its performance numerically in Section 6.2.8.

Model Validations and Insights.
First, we consider a binary tree network with seven nodes as shown in Figure 13, where K = {1, 2, 3, 4}. There are 4 leaf nodes, each is connected to 30 sensors. We assume that each sensor continuously generates content which are active for 1 unit time for simplicity. Hence the paths are p 1 = {1, 5, 7}, p 2 = {2, 5, 7}, p 3 = {3, 6, 7} and p 4 = {4, 6, 7}. Also let B v = 6 for all leaf nodes v ∈ {1, · · · , 4}, and B v = 10 for nodes v = 5, 6, 7. Furthermore, for each leaf node, users' interest in (requests to) the the content gathered from its sensors follows a Zipf distribution with parameters α 1 = 0.2, α 2 = 0.4, α 3 = 0.6 and α 4 = 0.8, respectively. For simplicity, we consider linear cost functions with coefficients 0.003 for c f (·) and c s (·), and 1 for c c (·). The total energy constraint is set O = 40 for all paths. We consider the log utility function U (k ) i is the request arrival rate for content i from sensor k. W.l.o.g., we assume the total arrival rate at each leaf node is 1, hence λ (k ) i equals to the content popularity.
The results for path p 4 are shown in Figures 10, 11 and 12. Again, we observe that our algorithm yields the exact optimal and empirical hit probabilities under MCDP for seven-node WSN. The density of number of content in the network concentrates around their corresponding cache sizes. Furthermore, we notice that the compression ratio δ at node 4 is much smaller than the ratios at nodes 6 and 7. This captures the tradeoff between the costs of compression, communication and caching in our optimization framework. Similar observations can be made for the other three request paths and hence are omitted here.

CONCLUSION
We constructed optimal timer-based TTL polices for arbitrary network topologies through a unified optimization approach. We formulated a general utility maximization framework, which is nonconvex in general. We identified the non-convexity issue and proposed efficient distributed algorithm to solve it. We proved that the distributed algorithms converge to the globally optimal solutions. We showed the efficiency of these algorithms through numerical studies. We also introduced the generalization of our approach to different applications including CDNs and WSNs. Tradeoff among caching, compression and communication was characterized through our optimization framework by incorporating utilities of hit probability and costs of compression and communication.

APPENDIX 8.1 Stationary Behaviors of MCDP and MCD
8.1.1 MCDP. Under IRM model, the request for content i arrives according a Poisson process with rate λ i . As discussed earlier, for TTL caches, content i spends a deterministic time in a cache if it is not requested, which is independent of all other contents. We denote the timer as T il for content i in cache l on the path p, where l ∈ {1, · · · , |p|}.
Denote t i k as the k-th time that content i is either requested or moved from one cache to another. For simplicity, we assume that content is in cache 0 (i.e., server) if it is not in the cache network. Then we can define a discrete time Markov chain (DTMC) {X i k } k ≥0 with |p| + 1 states, where X i k is the cache index that content i is in at time t i k . Since the event that the time between two requests for content i exceeds T il happens with probability e −λ i T il , then the transition matrix of {X i k } k ≥0 is given as Let (π i0 , · · · , π i |p | ) be the stationary distribution for P MCDP i , we have Then the average time that content i spends in cache l ∈ {1, · · · , |p|} can be computed as and Given (46) and (47), the timer-average probability that content i is in cache l ∈ {1, · · · , |p|} is where h il is also the hit probability for content i at cache l .

MCD.
Again, for TTL caches, content i spends a deterministic time T il in cache l if it is not requested, which is independent of all other contents.
We define a DTMC {Y i k } k ≥0 by observing the system at the time that content i is requested. Similarly, if content i is not in the cache network, then it is in cache 0, thus we still have |p| + 1 states. If Y i k = l, then the next request for content i comes within time T il with probability 1 − e −λ i T il , thus we have Y i k +1 = l + 1, otherwise Y i k +1 = 0 due to the MCD policy. Therefore, the transition matrix of {Y i k } k ≥0 is given as Let (π i0 , · · · ,π i |p | ) be the stationary distribution for P MCD i , then we havẽ By PASTA property [29], we immediately have that the stationary probability that content i is in cache l ∈ {1, · · · , |p|} is given as h il =π il , l = 0, 1, · · · , |p|, whereπ il are given in (49).

Minimizing Overall Costs
In Section 4.3, we aim to maximize overall utilities across all contents over the cache network, which captures the user satisfactions. However, the communication costs for content transfers across the network is also critical in many network applications. This cost includes (i) the searching cost for finding the requested content in the network; (ii) the fetching cost to serve the content to the user; and (iii) the moving cost for cache inner management due to a cache hit or miss. In the following, we first characterize these costs for MCDP and MCD, respectively. Then we formulate a minimization optimization problem to characterize the optimal TTL policy for content placement in linear cache network.

Search Cost.
Requests from user are sent along a path until it hits a cache that stores the requested content. We define the searching cost as the cost for finding the requested content in the cache network. Consider the cost as a function c s (·) of the hit probabilities. Then the expected searching cost across the network is given as Hit probability node 1 (Numerical) node 2 (Numerical) node 3 (Numerical) Figure 16: ψ = 1.

Fetching
Cost. Upon a cache hit, the requested content will be sent to the user along the reverse direction of the path. We define the fetching cost as the costing of fetching the content to serve the user who sent the request. Consider the cost as a function c f (·) of the hit probabilities. Then the expected fetching cost across the network is given as

Moving Cost.
Under TTL cache, upon a cache hit, the content either moves to a higher index cache or stays in the current one, and upon a cache miss, the content either moves to a lower index cache (MCDP) or is discarded from the network (MCD). We define the moving cost as the cost due to caching management upon a cache hit or miss. Consider the cost as a function c m (·) of the hit probabilities. MCD: Under MCD, since the content is discarded from the network once its timer expires, the moving cost is caused by a cache hit. To that end, the requested content either moves to a higher index cache if it was in cache l ∈ {1, · · · , |p| − 1} or stays in the same cache if it was in cache |p|. Then the expected moving cost across the network for MCD is given as MCDP: Under MCDP, besides moving the requested content to a higher index cache upon a cache hit, each content also moves to a lower index cache if its timer expires. Thus, we also need to characterize the moving cost due to timer expiry.
In Section 4.1.2, we characterize the stationary behavior of MCDP. Recall that in (47), we have shown the average time content i ∈ D spends in cache l ∈ {1, · · · , |p|} satisfies However, they cannot be directly applied to computed the moving cost due to time expiry, since we need to consider the average time interval that content i is not in the current cache upon next request, i.e., E[t i k+1 − t i k |X i k = l, X i k +1 l] for l ∈ {1, · · · , |p|}.
In the following, we characterize E[t i k +1 − t i k |X i k = l, X i k +1 l] by considering three cases: Case 1: When content i is in cache l = 1. In this case, content i is discarded from the network (we say it moves to cache 0) once the timer expires, hence there is no moving cost due to time expiry, which occurs with probability e −λ i T i 1 . Upon a cache hit, content i is moved to a higher index cache 2, which occurs with probability 1 − e −λ i T i 1 . Therefore, the corresponding average time interval is given as Case 2: When content i is in cache l = |p|. In this case, content i stays in cache |p| upon a cache hit, hence there is no moving cost due to cache hit, which occurs with probability 1 − e −λ i T i |p | . Once the timer expires, which happens with probability e −λ i T i |p | , content i moves to a lower index cache |p| − 1, the corresponding average time interval is given as Case 3: When content i is in cache l ∈ {2, · · · , |p| − 1}. In this case, content i moves to a higher index cache upon a cache hit and moves to a lower index cache if timer expires. Hence, we have