{'fraction_non_alphanumeric': 0.038273093883088985, 'fraction_numerical': 0.008159650246862398, 'mean_word_length': 4.050152264940997, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RetroRenting: An Online Policy for Service Caching at the Edge

The rapid proliferation of shared edge computing platforms has enabled application service providers to deploy a wide variety of services with stringent latency and high bandwidth requirements. A key advantage of these platforms is that they provide pay-as-you-go flexibility by charging clients in proportion to their resource usage through short-term contracts. This affords the client significant cost-saving opportunities, by dynamically deciding when to host its service on the platform, depending on the changing intensity of requests. A natural policy for our setting is the Time-To-Live (TTL) policy. We show that TTL performs poorly both in the adversarial arrival setting, i.e., in terms of the competitive ratio, and for i.i.d. stochastic arrivals with low arrival rates, irrespective of the value of the TTL timer. We propose an online policy called RetroRenting (RR) and show that in the class of deterministic online policies, RR is order-optimal with respect to the competitive ratio. In addition, we provide performance guarantees for RR for i.i.d. stochastic arrival processes coupled with negatively associated rent cost sequences and prove that it compares well with the optimal online policy. Further, we conduct simulations using both synthetic and real world traces to compare the performance of RR with the optimal offline and online policies. The simulations show that the performance of RR is near optimal for all settings considered. Our results illustrate the universality of RR.


I. INTRODUCTION
Widespread adoption of smartphones and other handheld devices over the last decade has been accompanied with the development of a wide variety of mobile applications providing a plethora of services. 1 These applications often rely on cloud computing platforms [2] to enable the delivery of high-quality performance anytime, anywhere to resourceconstrained mobile devices. However, the last few years have seen the emergence of applications based on machine learning, computer vision, augmented/virtual reality (AR/VR) etc. which are pushing the limits of what cloud computing platforms can reliably support in terms of the required latency and bandwidth. This is largely due to the significant distance between the end user and the cloud server, which has led the academia and the industry to propose a new paradigm called edge computing [3] whose basic tenet is to bring storage and computing infrastructure closer to the end users. This can help enable applications with ultra-small network latency and/or very high bandwidth requirements, which cannot be reliably supported by the backhaul connection. As a concrete example, consider a user in a wildlife sanctuary, capturing the scene around her live on a mobile device, which relays the image/video to an edge server. Using its much higher computational and storage capabilities, an application on the 1 A preliminary version of this work appeared in WiOpt 2020 [1]. edge server can continually detect species of plants, animals, birds and relay this information back to the end user device where it can be overlaid onto the live stream to provide a much richer viewing experience. Broader applications of edge computing include industrial robotics/drone automation, AR/VR-based infotainment and gaming, autonomous driving and the Internet of Things (IoT). While there are now several industry offerings of dedicated edge computing platforms, e.g., Amazon Web Services [4] and Microsoft Azure [5], there have also been proposals to augment cellular base stations [6] and WiFi access points [7] so that they can act as edge servers.
As discussed in [8], a typical system with edge-computation capabilities has the followings stakeholders: (i) application providers who provide a service to the end-user, (ii) access providers who rent out edge resources to the application providers to host their services to serve their customers, and (iii) Internet service providers (ISPs) who provide the backbone network service to the application providers. The focus of this work is on the algorithmic task for an application provider of determining when to rent edge resources and how to use the backbone network to best serve their customers while minimizing the cost of service. Although we study this problem from a perspective of a specific application provider, the effect of the presence of other application providers who might be simultaneously interested in using the resources offered by the access providers is captured through the timevarying nature of the cost of renting edge resources. More specifically, we consider the setting where the access provider periodically revises the cost of renting edge resources, potentially based on the current demand, and the application provider decides if they wish to rent edge resources at the quoted cost.
In this work, we say that a service is hosted at an edge server, if all the data and code needed to run the service has been downloaded from a remote/back-end server (possibly in the cloud) and hosted on the edge server. Thus the edge server can handle service requests on its own without requiring to communicate with the back-end server using the backbone network. Edge servers are often limited in computational capability as compared to cloud servers [9], and hence there might be a limit on the number of parallel requests they can serve for the hosted service. An application provider can avail this ability to host on the edge server in return of a potentially time-varying cost in proportion to the amount of resources used and/or the duration of rental. Since computing platforms usually provide pay-as-you-go flexibility [10], the client can dynamically decide when to host or evict the service at the edge, depending on the varying number of arriving service requests. The application provider needs to design an efficient service hosting policy which can help minimize the overall cost of deploying the service.
Each time a service request arrives at the edge server and the service is not hosted on it, there are two options: (a) request forwarding which simply forwards the service request to the back-end server, which then carries out all the relevant computation for addressing the request; and (b) service download which downloads all the data and code needed for running the service from the back-end server and hosts it at the edge. The cost for these two actions is different, depending for example on the amount of network bandwidth needed or the latency incurred for each of them. Motivated by empirical evidence [3], [11], a natural assumption is that the cost of forwarding a single request to the back-end server is lower than the cost of downloading the entire service to host it on the edge server [12].
Our goal in this work is to design online service hosting policies for the application provider which aim to minimize the total cost it incurs for serving requests, which is a combination of the request forwarding cost, the service download cost and the edge server rental cost. We consider two classes of request arrival processes: (i) adversarial arrivals: the request sequence is arbitrary and the performance of any online policy is measured by its competitive ratio, which provides a worstcase guarantee on its performance for any request arrival sequence in comparison to the optimal offline policy, which has knowledge of the entire arrival sequence a-priori. (ii) i.i.d. stochastic arrivals: requests are generated according to an i.i.d. stochastic process and we compare the expected cost of a proposed policy with that of the optimal online policy which does not have knowledge of sample path of future arrivals, but can exploit the statistics of the stochastic process to make service hosting decisions.

A. Our Contributions
A natural policy for our setup is the Time-To-Live (TTL) policy [13], which is popular in the content caching literature. Under the TTL policy, each "miss" triggers a download of the service to the edge server where it is then retained for some fixed amount of time. We show that TTL performs poorly both in terms of the competitive ratio for arbitrary arrivals and for i.i.d. stochastic arrivals with low arrival rates, irrespective of the value of the TTL timer. Given the limitations of TTL, we propose an online policy called RetroRenting (RR) which uses the history of request arrivals and the history of rent costs to decide when to host or evict the service at the edge server. Under the adversarial request setting, we show that RR is order-optimal with respect to the competitive ratio in the class of deterministic online policies. In addition, we also provide performance guarantees for RR under i.i.d. request arrivals and negatively associated rent costs and prove that it compares very well with the optimal online policy in this setting. In addition to our analytical results, we conduct simulations using both synthetic and real world traces to compare the performance of RR with the optimal offline and online policies. Our simulations show that the performance of RR is near optimal for all settings considered. These results combined illustrate the universality of RR.

B. Related Work
Mobile applications have increasingly become more and more demanding in terms of their bandwidth and latency requirements. This, along with the advent of new time-critical applications such as the Internet of Things (IoT), AR/VR and autonomous driving has necessitated the migration of a part of the storage and computing capabilities from remote servers to the edge of the network. See [14]- [16] for a survey of various edge computing architectures and proposed applications. The emergence of such edge computing platforms [14]- [16] has been accompanied with various academic works which model and analyse the performance of such systems. We briefly discuss some of the relevant works in the literature.
One approach towards designing efficient edge computing systems is to formulate the design problem as a large one-shot static optimization problem which aims to minimize the cost of operating the edge computing platform [6], [9], [17]- [19]. [17] considers such a problem in a heterogeneous setting where different edge nodes have different storage or computation capabilities and various services have different requirements. The goal is to find the optimal service placement scheme subject to the various constraints. The authors show that the problem is in general NP-hard and propose constant factor approximation algorithms. A similar problem is considered in [18] which looks at the setting where an edge server is assisting a mobile unit in executing a collection of computation tasks. The question of which services to cache at the edge and which computation tasks to offload are formulated as a mixed integer non-linear optimization problem and the authors design a reduced-complexity alternative minimization based iterative algorithm for solving the problem. Similar problems have also been considered in [6], [9], [19]. Our work differs from this line of work in that we are interested in designing online algorithms which adapt their service placement decisions over time depending on the varying number of requests.
One approach to modeling time-varying requests is to use a stochastic model as done in [20]- [22] which assumes that requests follow a Poisson process and then attempts to minimize the computation latency in the system by optimizing the service hosting and task offloading decisions. [21] considers a setting where the underlying distribution for the request process is a-priori unknown and uses the framework of Contextual Combinatorial Multiarmed Bandits to learn the demand patterns over time and make appropriate decisions. Finally, [22] considers a Markovian model for user mobility and uses a Markov Decision Process (MDP) framework to decide when and which services to migrate between different edge servers as the users move around. Our work differs from these works in that in addition to stochastic request models, we also focus on the case of arbitrary request arrival processes and provide 'worst-case' guarantees on the performance of our proposed schemes instead of 'average' performance guarantees. This can be vital in scenarios where the arrival patterns change frequently over time, making it difficult to predict demand or model it well as a stochastic process.
The work closest to ours is [12] which considers an edge server with limited memory K units which can be used at zero cost and an arbitrary request process for a catalogue of services. This work studies the design of service caching policies which minimize the cost incurred by the edge server for deploying the various services. The authors propose an online algorithm called ReD/LeD and prove that the competitive ratio of the proposed scheme is at most 10K. Unlike [12], we study the problem from the perspective of an application provider and design cost-efficient service hosting policies which dynamically decide when to cache or evict the service at the edge. In addition to worst-case performance guarantees, we provide average performance guarantees of our proposed policy.
Online algorithms have been studied for a wide variety of computational problems [23]. In particular, [24] studies a general compute system for the processing of a sequence of tasks, each of which requires the system to be in a certain state for execution. There is a cost metric governing the penalty for moving the system from one state to the other, and the goal is to design online schemes which have a good competitive ratio with respect to the offline optimal. While the setting in [24] is similar to our work, the assumptions made there on the cost metrics are not satisfied for our problem and hence their results are not applicable.
Other relevant works on exploiting edge resources for service include [25] in which the focus is on the problem of characterizing the benefits of sharing resources for service caching on the edge server with multiple network providers. In [26], the focus is on decision pro-active service caching to serve users with high-mobility. Further, [8], [27] focus on economic aspects of edge caching involving interactions between different stakeholders using game-theoretic tools. In [28], the authors characterize the benefits of cooperation between edge servers and propose a deep reinforcement based algorithm for effective cooperation.
Finally, as mentioned before, the problem of service caching does resemble the content caching problem but with some key differences. Content caching has a rich history, see for example [29]- [34]. A popular class of online caching policies is the Time-To-Live (TTL) policy [13], which downloads a content to the cache upon a cache miss and then retains it there for a certain fixed amount of time. In this work, we consider a variant of the TTL policy for service caching and demonstrate that it performs poorly in several cases.

A. Network Model
We study a system consisting of a back-end server and an edge server in proximity to the end-user. The back-end server always stores the service. The service can be hosted on the edge server by paying a rental cost. On paying this cost, requests can be served at edge free of cost, subject to an upper limit on the number of concurrent requests of our service being served at the edge. In addition, requests can be served by the back-end server at a non-zero cost. The back-end server can serve all the requests that are routed to it.

B. Arrival Process and rent costs
We consider a time-slotted system and consider both adversarial and stochastic settings. In the adversarial setting, we make no assumptions on the arrival sequence and rent cost sequence. In the stochastic setting, we make the following assumption.
Assumption 1: (i.i.d. stochastic arrivals and negatively associated rent costs) The number of requests arriving in a timeslot is independent and identically distributed across timeslots. More specifically, let X t be the number of requests arriving in time-slot t. Then, for all t, The amount of rent costs to be paid for storage in each time-slot are random and negatively associated across timeslots [35], for example i.i.d sequence rent costs across time slots is special case of negative associated random sequence. Let R t be the rent cost per time-slot, {R t } t≥1 is the sequence of negatively associated random variables and c = E[R t ].

C. Sequence of Events in a Time-slot
The following sequence of events occurs in each timeslot. We first have request arrivals. If the service is hosted on the edge server, requests are served locally subject to the constraints on the allocated computation power of the edge server, else requests are forwarded to the back-end server. After that, we know the amount of rent cost in the immediate next time-slot. The system then makes a hosting decision (fetch/evict/no change).

D. Cost Model and Constraints
Our cost model builds on the model proposed in [1], [12] and extends it to the setting where edge resources can be rented in a dynamic manner by paying a potentially time-varying rent cost. For a given policy P, the total cost incurred in time-slot t, denoted by C P t , is the sum of the following three costs. -Service cost (C P S,t ): Each request forwarded to the backend server is served at the cost of one unit.
-Fetch cost (C P F,t ): On each fetch of the service from the back-end server to host on the edge-server, a fetch cost of M (> 1) units is incurred.
-Rent cost (C P R,t ): A rent cost of c t units is incurred to host the service on the edge server for a time-slot. Here, c t lies in [c min , c max ] with c min > 0. Remark 1: We model the rent cost as a time-varying quantity as it might depend on various factors including the overall demand for edge resources across various services that are potentially interested in renting. The time-varying nature of the rent cost is the key difference between this work and the model considered in its preliminary version in [1].
Since the edge server offers a limited computation power per service, the number of requests that can be served by the edge server in a time-slot is limited to κ ∈ Z + , where Z + is the set of all positive integers. Let r t be an indicator of the event that the service is hosted on the edge server during time-slot t. It follows that

Remark 2:
We limit our discussion to the case where the rent cost c t ≤ M + κ because, for c t > M + κ, it is optimal to forward all requests to the back-end server, irrespective of the value of M and the arrival sequence.

E. Algorithmic Challenge
The algorithmic challenge is to design a policy which decides when to host the service on edge server. Policies can be divided into the following two classes. We design an online policy which makes decisions based on the request arrivals, rent costs thus far and the various costs and constraints, the fetch cost (M ), and the edge server constraint (κ).

F. Metric and Goal
The optimal offline and online policies serve as benchmarks to evaluate the performance of the proposed policy. We use different cost metrics for the adversarial and stochastic request arrival settings.
1) Adversarial setting: For the adversarial setting, we compare the performance of a policy P with the performance of the optimal offline policy (OPT-OFF). The goal is to design a policy P which minimizes the competitive ratio ρ P defined as where A is the set of all possible finite request arrival sequences, R is the set of all possible finite rent cost sequences, C P (a, b), C OPT-OFF (a, b) are the overall costs of service for the request arrival sequence a and rent cost sequence b under online policy P and the optimal offline policy respectively.
2) i.i.d. stochastic arrivals and negatively associated rent costs : For i.i.d. stochastic arrivals and negatively associated rent costs (Assumption 1), we compare the performance of a policy P with the performance of the optimal online policy (OPT-ON). The goal is to minimize σ P T , defined as the ratio of the expected cost incurred by policy P in T time-slots to that of the optimal online policy in the same time interval. Formally, where C P t is as defined in (1).

III. MAIN RESULTS AND DISCUSSION
In this section, we state and discuss our main results. We provide outlines of the proofs in Section V and the details of the proofs are discussed in Section VI.

A. Our Policy: RetroRenting (RR)
A policy determines when to fetch and host the service and when to evict the service from the edge. The RR policy makes these decisions in each time-slot by evaluating if it made the right decision in hindsight. We first provide an overview of the RR policy.
To fetch: Let the service not be hosted at the beginning of time-slot t and t evict < t be the time when the service was most recently evicted by RR. The RR policy searches for a time-slot τ such that t evict < τ < t, and the total cost incurred is lower if the service is fetched in time-slot τ − 1 and hosted during time-slots τ to t than if the service is not hosted during time-slots τ to t. If there exists such a time τ , the RR policy fetches the service in time-slot t.
To evict: Let the service be hosted at the edge at the beginning of time-slot t and t fetch < t be the time when the service was most recently fetched by RR. The RR policy searches for a time-slot τ such that t evict < τ < t, and the total cost incurred is lower if the service is not hosted at the edge during time-slots τ to t and fetched in time-slot t than if the service is hosted at the edge during time-slots τ to t. If there exists such a time τ , the RR policy evicts the service in time-slot t.
Refer to Algorithm 1 for a formal definition of the RR policy. The notation used in Algorithm 1 is summarized in Table I.
Remark 3: Note that in time-slot t, the computation and storage complexities of the RR policy scale as O(t) (if either t fetch = 0 or t evict = 0). This is indeed a limitation of the RR policy since, in the worst case, the computational and storage complexities increase linearly with time. An efficient implementation of RR is presented in the Appendix. The key idea behind this implementation is, in each time-slot we compute a metric that captures the trend of difference between cost of forwarding and cost of renting. Decisions on when to rent   edge resources can be made solely based on this metric. This approach is inspired from [36]. Computational and storage complexities of this implementation do not scale with time, thus alleviating the need for the RR u policy proposed in [1].

B. Performance guarantees for RR
1) Adversarial setting: Our first theorem characterizes the performance of RR in the adversarial setting.
Theorem 1: Let ρ RR be the competitive ratio of RR. Then, Since this result holds for all finite request arrival sequences and fine rent cost sequences, Theorem 1 provides a worst-case guarantee on the performance of the RR policy as compared to that of the optimal offline policy. Recall that unlike the RR policy, the optimal offline policy knows the entire arrival sequence and the entire rent cost sequence a-priori.
The competitive ratio of RR improves as the fetch cost (M ) increases, however, it increases linearly with κ. Our next result shows that the competitive ratio of any deterministic online policy increases linearly with κ.
Theorem 2: Let P be any deterministic online policy and let ρ P be the competitive ratio of this policy. Then, From Theorems 1 and 2, we conclude that the RR policy is order optimal with respect to the edge server computation constraint (κ) for the setting considered. This is one of the key results of this work. While Theorem 1 gives a worstcase guarantee on the performance of the RR policy, in our subsequent analytical and simulation results, we observe that for the request sequences considered, the performance of the RR policy is significantly closer to that of the offline optimal policy than the bound in Theorem 1 suggests.
2) Stochastic arrivals: Next we characterize the performance of the RR policy for i.i.d. stochastic arrivals and negatively associated rent cost sequence (Assumption 1, Section II). Recall that, under Assumption 1, in each time-slot, the number of request arrivals is x with probability p x for x = 0, 1, · · · . Our next lemma characterizes the difference between the expected cost incurred in a time-slot by our policies and the optimal online policy.
Then, under Assumption 1, -Case µ > c: -Case µ < c: We thus conclude that for t large enough, the difference between the cost incurred by RR and the optimal online policy in time-slot t, decays exponentially with M and |µ − c|.
Recall the definition of σ P T given in (3). -Case µ > c: For the function f defined in Lemma 1, -Case µ < c: For the function g defined in Lemma 1,

Remark 4:
The bounds obtained in Lemma 1 and Theorem 3 hold for all i.i.d. stochastic arrival processes and negatively associated rent costs. We note that the bounds worsen as κ increases. This is a consequence of using Hoeffding's inequality to bound the probability of certain events. It is important to note that significantly tighter bounds can be obtained for specific i.i.d. processes by using the Chernoff bound instead of Hoeffding's inequality. In the next section, via simulations, we show that the performance of RR does not worsen as κ increases. We thus conclude that the deterioration of the performance guarantees with increase in κ is a consequence of the analytical tools used and not fundamental to RR. Note that for µ = c the performance of RR is same as that of optimal online policy.
We use Theorem 3 to conclude that for T large enough, the bound on the ratio of the expected cost incurred by RR in T time-slots to that of the optimal online policy (OPT-ON) in the same time interval decays as M increases.
Often, policies designed with the objective of minimizing the competitive ratio tend to perform poorly on average in typical stochastic settings. Similarly, polices designed for specific stochastic arrival processes can have poor competitive ratios if they perform poorly for certain 'corner case' arrival sequences. The performance guarantees for RR obtained in this section show that RR performs well in both the adversarial and the i.i.d. stochastic settings. This is a noteworthy feature of the RR policy.

C. Performance of TTL
In this section, we focus on the TTL policy which is widely used and studied in the classical caching literature. TTL serves as a benchmark to compare the performance of RR.
The TTL policy fetches and hosts the service whenever there is a miss, i.e., the service is requested but is not hosted on the edge server. There is a timer associated with the fetch, which is set to a fixed value (L) right after the service is fetched. If the service is not requested before the timer expires, the service is evicted from the host. If a request arrives while the service the hosted, the timer is reset to its initial value of L. Refer to Algorithm 2 for a formal definition. Our next result provides a lower bound on the competitive ratio of the TTL policy.
Theorem 4: Let ρ TTL be the competitive ratio of the TTL policy with TTL value L as defined in (2). Then, The key takeaway from Theorem 4 is that unlike the RR policy, the performance of the TTL policy deteriorates as the fetch cost (M ) increases. This is a consequence of the fact that the TTL policy fetches and hosts the service on a miss irrespective of the value of M , whereas for high values of M , RR and the optimal offline policy might choose not to fetch the service at all. Note that the performance of both RR and TTL deteriorates with increase in κ.
Next, we characterize the performance of TTL for i.i.d. stochastic arrivals and negatively associated rent costs.
For t > 1, min{t − 1, L} ≥ 1, and therefore, We thus conclude that for low arrivals rates, the difference between the cost incurred by TTL and the optimal online policy in time-slot t, increases with M and c − µ. This illustrates the limitations of TTL for the stochastic setting with low arrival rates. The sub-optimality of TTL is a consequence of the fact that the TTL policy fetches and hosts the service on a miss irrespective of the value of M and µ, whereas for high values of M and low values of µ, RR and the optimal online policy choose not to fetch the service at all.
Recall the definition of σ P T given in (3). If µ < c, From Theorem 5, we conclude that for low request arrival rates (µ < c), the performance of TTL deteriorates with increases in M . Contrary to this, the performance of RR approaches the performance of the optimal online policy as M increases (Theorem 3). We thus conclude that for low arrival rates and high fetch cost, TTL is sub-optimal.
TTL policies perform well in content caching, where on a miss, the requested content is fetched from the back-end server by all policies including TTL. However, as discussed above, on a miss in our setting, there are two options: (a) request forwarding which forwards the request to the back-end server for service; and (b) service fetch which fetches all the data and code needed for running the service from the back-end server and hosts it on the edge server. The cost for these two actions is different. By definition, TTL always takes the second option, whereas, for low request arrival rates and high fetch cost, RR, and the optimal online and offline policies use the first option. This explains the poor performance of TTL for our setting.

IV. SIMULATION RESULTS
In this section, we compare the performance of various policies via simulations. From our analytical results, we know that the Fixed TTL policy performs poorly for our setting. Therefore, we compare our policy with an online variant of the TTL policy proposed in [13]. The simulation parameters for each set of simulation are provided in the figure caption.

A. Stochastic Arrivals and Stochastic Rent Costs
For the first set of simulations, we consider stochastic arrival and rent processes, and use an i.i.d. Bernoulli sequence for determining the arrivals in each slot. We model the timevarying rent cost sequence using the Auto-Regressive Moving-Average (ARMA) model [37] and to choose the model's hyperparameters, we fit it to real-world spot prices of spare server capacity in the AWS cloud as given in [38]. We collect the chronological spot prices data for the instance 'm4.large' in the Central Canada region and employed the grid search method [39] on this data to estimate the hyperparameters of the ARMA model that minimize the mean square error. Finally, we add a constant shift to make sure that all cost values are positive and do a normalization to get a desired average cost value.
We compare the performance of RR, TTL online, and the optimal offline policy. In addition to these, we plot the lower bound on the cost incurred by any online policy ( Lemma 14). Each data-point in the plots is averaged over 10000 time-slots. In Figures 1-3, we consider Bernoulli request arrivals with parameter p, i.e., X t = 1 with probability p and X t = 0 otherwise. Recall that κ ≥ 1 and µ = E[min{X t , κ}]. Since X t ≤ 1 in this case, therefore, µ = p. We compare the performance of RR with the optimal offline and TTL online policies.

1) i.i.d. Bernoulli Arrivals:
The performance of the RR policy is quite close to that of the optimal online policy for all parameter values considered. The performance gap between the optimal offline policy and the RR policy is small compared to the bound on competitive ratio obtained in Theorem 1. We see that the gap between the performance of the RR and optimal online policy increases as M and/or |µ − c| decrease. This can be explained as follows. If µ < c, the optimal online policy does not fetch/store the service and forwards all the requests to the back-end server. However, for small values of c − µ, and M , the condition the RR policy checks to fetch and host the service (Step 8 in Algorithm 1) is not very unlikely. This leads to multiple fetch-store-evict cycles and therefore a higher cost than the optimal online policy. As M and/or c − µ increase, this event becomes less probable. The case when µ > c can be argued along similar lines. Figure 4, we consider the case where the arrival process is Poisson with parameter λ. We vary κ. We see that the performance of all policies improves with increase in κ. The performance of RR is very close that of the optimal offline policy and the lower bound on online policies.

B. Trace-driven Simulations
For the next set of simulations, we use trace-data obtained from a Google Cluster [40] for the arrival process. We use a time-slot duration small enough to ensure that there is at most one request in a time-slot. This trace-data has requests for four types of jobs/services identified as "Job 0", "Job 1", "Job 2", and "Job 3". In this section, we present results for "Job 0" (Figures 5, 9, 13 ), "Job 1" (Figures 6, 10, 14), "Job 2" (Figures 7 and 11), and "Job 3" (Figures 8, 12). In Figures  5-12, we use the rent cost c t to be constant across timeslots. Whereas in Figures 13, 14 we use time-varying rent cost obtained from real world data. Specifically, we use the time-varying spot prices of spare server capacity in the AWS cloud as given in [38]. This data [38] consists of details like current spot price for different instances for different regions. We use the spot price details of Canada region for one instance 'm4.large'. We normalise this data by dividing each entry by average value of spot prices. So the empirical of new cost cost data is equal to one.
We compare the performance of RR with the optimal offline policy and TTL online. The performance of TTL online is the worst among these polices, and the performance gap between TTL online and RR is significant.

A. Proof Outline for Theorem 1
We divide time into frames such that Frame i for i ∈ Z + starts when OPT-OFF downloads the service for the i th time. We refer to the time interval before the beginning of the first frame as Frame 0. Note that by definition, in all frames, except maybe the last frame, there is exactly one eviction by OPT-OFF.
We use the properties of RR and OPT-OFF to show that each frame in which OPT-OFF evicts the service has the following structure ( Figure 15): -RR fetches and evicts the service exactly once each.
-RR does not host the service at the beginning of the frame. -The fetch by RR in Frame i is before OPT-OFF evicts the service in Frame i. -The eviction by RR in Frame i is after OPT-OFF evicts the service in Frame i. We note that both RR and OPT-OFF fetch exactly once in a frame and therefore, the fetch cost under RR and OPT-OFF is identical for both policies. We divide Frame i into four sub-frames defined as follows.
i.a: OPT-OFF hosts the service, while RR does not.
i.b: OPT-OFF and RR both host the service.
i.c: OPT-OFF does not host the service while RR does.
i.d: OPT-OFF and RR both don't host the service. The service and rent costs are identical for OPT-OFF and RR in Sub-frame i.b and Sub-frame i.d.
We show that the difference between the service and rent costs incurred by RR and OPT-OFF in Sub-frame i.a and Subframe i.c is upper bounded by M + κ − c min and M + c max respectively.
We use the two previous steps to show that the cumulative difference in service and rent costs under RR and OPT-OFF in a frame is upper bounded by 2M + κ + c max − c min . Since the fetch cost under RR and OPT-OFF in a frame is equal, we have that the total cost incurred by RR and OPT-OFF in We show that once fetched, OPT-OFF hosts the service for at least M κ−cmin time-slots (Lemma 5). We thus conclude that the total cost incurred by OPT-OFF in a frame is lower bounded by M + Mcmin κ−cmin . We use this to upper bound the ratio of the cost incurred by RR and cost incurred by OPT-OFF in the frame.
The cost incurred by RR and OPT-OFF in Frame 0 is equal. We then focus on the last frame. If OPT-OFF does evict the service in the last frame, the analysis is identical to that of the previous frame. Else, we upper bound the ratio of the cost incurred by RR and cost incurred by OPT-OFF in the frame.
The final result then follows from stitching together the results obtained for individual frames.

B. Proof Outline for Theorem 2
We divide the class of deterministic online policies into two sub-classes. Any policy in the first sub-class hosts the service during the first time-slot. All other polices are in the second sub-class.
For each policy in either sub-class, we construct a specific arrival sequence, a specific rent cost sequence and compute the

C. Proof Outline for Theorem 3
We first characterize a lower bound on the cost per time-slot incurred by any online policy (Lemma 14).
Next, we focus on the case where µ > c. We upper bound the probability of the service not being hosted during timeslot t under RR using Hoeffding's inequality [41]. The result then follows by the fact that conditioned on the service being hosted in time-slot t, the expected total cost incurred by RR is We then consider the case where µ < c. We upper bound the probability of the service being hosted or being fetched in time-slot t under RR using Hoeffding's inequality [41]. The result then follows by the fact that conditioned on the service not being hosted and not being fetched in time-slot t, the expected total cost incurred by RR is at most E[X t ] and is upper bounded by M + c + E[X t ] otherwise.

D. Proof Outline for Theorem 4
Depending on the value of the system parameters (M , c min , c max , κ), we construct specific arrival sequences, rent cost sequences and compute the ratio of the cost incurred by TTL and OPT-OFF for these sequences. By definition, this ratio serves as a lower bound on the competitive ratio of TTL in each case.

E. Proof Outline for Theorem 5
Under the TTL policy with TTL value L, the service is hosted during a given time-slot if and only if it is requested at least once in the L previous time-slots. We compute the probability of the event G defined as the event that the service is requested at least once in the L previous time-slots. We compute the conditional expected cost incurred by the TTL policy in time-slot conditioned on G and G c to obtain the result.

A. Proof of Theorem 1
The notation used in this subsection is given in Table II. We use the following lemmas to prove Theorem 1.   The next lemma provides a lower bound on the duration for which OPT-OFF hosts the service once it is fetched. Our next lemma characterizes a necessary condition for RR to fetch the service. Proof: Since n l=n−τ +1 x l ≤ τ κ, τ min κ ≥ τ min c min + M , and the result follows. The next lemma gives an upper bound on the number of requests that can be served by the edge server (subject to its computation power constraints) in a time-interval such that RR does not host the service during the time-interval and fetches it in the last time-slot of the time-interval.
Lemma 7: Let r RR (n − 1) = 1, r RR (t) = 0 for n ≤ t ≤ m and r RR (m + 1) = 1. Then for any n ≤ n ′ < m, Proof: Given r RR (m) = 0 and r RR (m + 1) = 1, then for any n ≤ n ′ < m, Thus proving the result. Consider the event where both RR and OPT-OFF have hosted the service in a particular time-slot. The next lemma states that given this, OPT-OFF evicts the service before RR.
Proof: We prove this by contradiction. Let ∃ m < m such that r RR ( m + 1) = 0. Then, from Algorithm 1, there exists an

The cost incurred by OPT-OFF in the interval
Consider an alternative policy η for which r η (t) = 0 for m − τ + 1 ≤ t ≤ m, r η ( m + 1) = 1, and r η (t) = r * (t) c l which is negative by our assumption. This contradicts the definition of the OPT-OFF policy, thus proving the result.
Consider the case where both RR and OPT-OFF have hosted the service in a particular time-slot. From the previous lemma, we know that, OPT-OFF evicts the service before RR. The next lemma gives a lower bound on the number of requests that can be served by the edge server (subject to its computation power constraints) in the interval which starts when OPT-OFF evicts the service from the edge server and ends when RR evicts the service from the edge server.
Lemma 9: Let r * (n − 1) = 1, r * (n) = 0, r RR (t) = 1 for n−1 ≤ t ≤ m and r RR (m+1) = 0.Then for any n ≤ n ′ < m, Proof: Given r RR (m) = 1 and r RR (m + 1) = 0, then for any n ≤ n ′ < m, Thus proving the result. Our next result states that RR does not fetch the service in the interval between an eviction and the subsequent fetch by OPT-OFF.
Proof: We prove this by contradiction. Let RR fetch the service in time-slot t where n ≤ t ≤ m − 1.
Then from Algorithm 1, there exists an integer τ > 0 such that t − τ ≥ n and t l=t−τ +1 x l ≥ t l=t−τ +1 c l + M. If this condition is true, by Lemma 4, OPT-OFF would have fetched the service at least once in the interval t − τ + 1 and t for all n ≤ t ≤ m − 1. Hence RR does not fetch the service between n and m − 1.
The next lemma states that in the interval between a fetch and the subsequent eviction by OPT-OFF, RR hosts the service for at least one time-slot.
Proof: We prove this by contradiction. Let r RR (t) = 0 for all n ≤ t ≤ m. Then by the definition of the RR policy, t l=t−τ +1 x l < t l=t−τ +1 c l + M for any τ > 0 and τ ≤ t− n+ 1. If both RR and OPT-OFF host the service in a particular time-slot, from Lemma 8, we know that OPT-OFF evicts the service before RR. The next lemma states that RR evicts the service before the next time OPT-OFF fetches it.
Proof: We prove this by contradiction. Assume that RR does not evict the service in any time slot t for all n ≤ t ≤ m.
Then from the definition of the RR policy, t l=t−τ +1 c l for all τ such that 0 < τ ≤ t − n + 1. Given this, it follows that OPT-OFF will not evict the service at the end of time-slot n − 1. This contradicts our assumption. By Lemma 10, RR does not fetch the service in the interval between an eviction and the subsequent fetch by OPT-OFF. Therefore, r RR (m + 1) = 0.
To compare the costs incurred by RR and OPT-OFF we divide time into frames [1, where t i − 1 is the time-slot in which OPT-OFF fetches the service for the i th time for i ∈ {1, 2, · · · }. Our next result characterizes the sequence of events that occur in any such frame.
Lemma 13: Consider the interval [t i , t i+1 − 1] such that OPT-OFF fetches the service at the end of time-slot t i − 1 and fetches it again the end of time-slot t i+1 − 1. By definition, there exists τ ∈ [t i , t i+1 − 2] such that OPT-OFF evicts the service in time-slot τ . RR fetches and evicts the service exactly once each in [t 1 , t 2 − 1]. The fetch by RR is in time-slot t RR f such that t 1 ≤ t RR f ≤ τ and the eviction by RR is in time-slot t RR e such that τ < t RR e < t 2 ( Figure 16).
OPT-OFF RR Fig. 16: Illustration of Lemma 13 showing download and eviction by OPT-OFF and RR in the i th frame. Downward arrows represent fetches, upward arrows indicate evictions. Black and red arrows correspond to the OPT-OFF and RR policy respectively. The two bars below the timeline indicate the state of the edge server under OPT-OFF and RR. The solid black and solid red portions represent the intervals during with OPT-OFF and RR host the service on the edge server respectively Proof: Without loss of generality, we prove the result for i = 1. Since r * (t 1 − 1) = 0, r * (t) = 1 for t 1 ≤ t ≤ τ and r * (τ ) = 0 then by Lemma 11, r RR (t RR f ) = 1 for some t 1 < t RR f ≤ τ. In addition, by Lemma 12, r RR (t 1 ) = 0. Therefore, RR fetches the service at least once in the interval [t 1 , t 2 − 1].
By Lemma 8, if t RR This completes the characterization for Frame 1 to k − 1.
We now focus on Frame k, which is the last frame. There are two possible cases, one where OPT-OFF evicts the service in Frame k, in which case the analysis for Frame k is identical to that of Frame 1, and the other when OPT-OFF does not evict the service in Frame k. We now focus on the latter.
Given that OPT-OFF downloads the service in time-slot t k − 1, there exists m > t k such that From (5) and (7), Stitching together the results obtained for all frames, the result follows.

B. Proof of Theorem 2
Proof: Let P be a given deterministic online policy and C P (a, b) be the cost incurred by this policy for the request sequence a and rent cost sequence b.
We first focus on the case where P does not host the service during the first time-slot.
We define t (1) fetch ≥ 1 as the first time the policy P fetches the service when there are κ request arrivals each in the first t (1) fetch time-slots. Since P is an online deterministic policy, the value of t (1) fetch can be computed a-priori. Consider the arrival process a with κ request arrivals each in the first t  . Therefore, Next, we focus on the case where P hosts the service during the first time-slot. We define t (1) evict ≥ 1 as the first time the policy P evicts the service when there are no request arrivals each in the first t (1) evict time-slots. Since P is an online deterministic policy, the value of t (1) evict can be computed apriori.
Consider the arrival process a with no request arrivals each in the first t

C. Proof of Theorem 3
We use the following lemmas to prove Theorem 3.
Proof: If the service is hosted at the edge in timeslot t, the expected cost incurred is at least If the service is not hosted at the edge server, the expected cost incurred is at least ν. This proves the result.
Lemma 15: Let X t be the number of requests arriving in time-slot t, X t = min{X t , κ} and µ = E[X t ]. Let R t be the rent cost per time-slot, {R t } t≥1 is the sequence of negatively associated random variables and Proof: Using i.i.d. condition of {X t } t≥1 and negatively associativity of {R t } t≥1 , it follows that for s > Then the result follows by Hoeffding's inequality [35], [41].
Proof of Lemma 1: We first consider the case when µ > c. We define the following events , and therefore, Using (9) and the union bound, By Lemma 15, By (10) and (11), Consider the event G = E c ∩ F and the following three cases. Case 1: The service is hosted at the edge during time-slot t − λM µ−c : Conditioned on E c , by the properties of the RR policy, the service is not evicted from the edge server in timeslots t − λM µ−c to t − 1. It follows that in this case, the service is hosted at the edge server during time-slot t.
Case 2: The service is not hosted at the edge during timeslot t − λM µ−c and is fetched in time-slotτ such that t − λM µ−c + 1 ≤τ ≤ t − 2: Conditioned on E c , by the properties of the RR policy, the service is not evicted from the edge server in time-slotsτ + 1 to t − 1. It follows that in this case, the service is hosted at the edge during time-slot t.
Case 3: The service is not hosted at the edge during time-slot t− λM µ−c and is not fetched in time-slots t− λM µ−c +1 to t−2: In this case, in time-slot t − 1, t evict ≤ t − λM µ−c . Conditioned on F , by the properties of the RR policy, condition in Step 8 in Algorithm 1 is satisfied for τ = t − λM µ−c . It follows that in this case, the service is fetched in time-slot t − 1 and therefore, the service is hosted at the edge during time-slot t.
We thus conclude that conditioned on G = E c ∩ F , the service is hosted at the edge during time-slot t. We now compute the expected cost incurred by the RR policy. By definition, We optimize over λ > 1 to get the tightest possible bound. By Lemma 14 and (13), we have the result for RR.
Next, we consider the case when µ < c. We define the following events By Lemma 15, it follows that P(F t1,t2 ) , and therefore, Using (14) and the union bound, P(F t ) and P(F t−1 ) are upper bounded by By Lemma 15, By (15) and (16), Consider the event G = F c t ∩F c t−1 ∩E and the following three cases.
Case 1: The service is not hosted at the edge during timeslot t − λM c−µ : Conditioned on F c , by the properties of the RR policy, the service is not fetched in time-slots t − λM c−µ to t − 1. It follows that in this case, the service is not hosted at the edge during time-slot t.
Case 2: The service is hosted at the edge during time-slot t− λM c−µ and is evicted in time-slotτ such that t− λM c−µ +1 ≤ τ ≤ t − 2: Conditioned on F c , by the properties of the RR policy, the service is not fetched in time-slotsτ + 1 to t − 1. It follows that in this case, the service is not hosted at the edge during time-slot t.
Case 3: The service is hosted at the edge during time-slot t− λM c−µ and is not evicted in time-slots t− λM c−µ +1 to t−2: In this case, in time-slot t − 1, t evict ≤ t − λM c−µ . Conditioned on E, by the properties of the RR policy, condition in Step 16 in Algorithm 1 is satisfied for τ = t − λM µ−c . It follows that in this case, the service is evicted in time-slot t − 1 and therefore, the service is not hosted at the edge in time-slot t.
We thus conclude that conditioned on F c t−1 ∩ E, the service is not hosted at the edge during time-slot t. In addition, conditioned on F c t , the service is not fetched in time-slot t. We now compute the expected cost incurred by the RR policy. By definition, We optimize over λ > 1 to get the tightest possible bound. By Lemma 14 and (18), we have the result for RR. Proof of Theorem 3: Follows by Lemma 14,(13), (18), the definition of σ P in (3), and the fact that the cost incurred in a time-slot by any policy is upper bounded by M + c + ν.

D. Proof of Theorem 4
Proof: Throughout this proof we consider a renting cost sequence where the cost of renting is c max in each time-slot.
Consider the case where κ < M + c max . For this setting we construct a request sequence where a request arrives in the first time-slot and no requests arrive thereafter. OPT-OFF does not fetch the service and the total cost of service per request for this request sequence under OPT-OFF is one unit. Let C TTL be the cost of service per request for this request sequence under TTL. TTL fetches the service on a request arrival and stores it on local edge server for L time slots. Thus the cost of service incurred by TTL per request is C TTL = 1+M +Lc max . Therefore, ρ TTL ≥ 1 + M + Lc max .
Next, we consider the case where κ ≥ M + c max and Lc max > M . For this setting we construct a request sequence where κ requests arrive in the first time-slot and no requests arrive thereafter. In this case, C TTL = κ+Lc max +M . Consider an alternative policy which fetches the service before the first time-slot and hosts it for one time-slot. The total cost of service for this policy is M + c max . It follows that ρ TTL ≥ κ + M + Lc max M + c max .
Next, we consider the case where κ ≥ M + c max and Lc max ≤ M . For this setting we construct a request sequence where κ requests arrive in time-slots 1, L + 2, 2L + 3, · · · , (u − 1)L + u and no requests arrive in the remaining time-slots. In this case, C TTL = u(κ + Lc max + M ). Consider an alternative policy which fetches the service before the first time-slot and hosts it till time-slot (u − 1)L + u. The total cost of service for this policy is M + ((u − 1)L + u)c max . It follows that ρ TTL ≥ sup u≥1 u(κ + Lc max + M ) M + ((u − 1)L + u)c max = κ + Lc max + M Lc max + c max .
The result follows from the three cases.

E. Proof of Theorem 5
Proof of Lemma 2: We compute the expectation of the cost incurred by the TTL policy in time-slot t. Let G be the event that there are no arrivals in time-slots max{t − L, 1} to t − 1. Under Assumption 1, P(G) = p min{L,t−1} 0 . For the TTL policy, conditioned on G, the service is not hosted at the beginning of time-slot t and all requests received in time-slot t are forwarded to the back-end server. In addition, the service is fetched if at least one request is received in time-slot t. It follows that E[C TTL t ] = M (1 − p 0 ) + ν. If the service is hosted at the edge in time-slot t, the TTL policy pays a rent cost of R t and up to κ results are served at the edge. The remaining requests are forwarded to the backend server. It follows that Proof of Theorem 5: Follows by Lemma 2 and the fact that the cost per time-slot incurred by the optimal online policy is at most ν.

VII. CONCLUSIONS AND FUTURE WORK
In this work, we focus on designing online strategies for service hosting on edge computing platforms. We show that the widely used and studied TTL policies do not perform well in this setting. This is because, on a miss, TTL fetches the data and code needed to run the service and hosts it on the edge server, whereas, for low request arrival rates and/or high fetch cost, it is more efficient to forward all requests to the back-end server.
In addition, we propose an online policy named RR. Via analysis for adversarial and stochastic settings and simulations for synthetic and trace-based arrivals, rent costs, we show that RR performs well for a wide array of request arrival processes and rent cost sequences.