# Online Partial Service Hosting at the Edge

V S Ch Lakshmi Narayana  Department of Electrical Engineering, IIT Bombay
<EMAIL_ADDRESS>,  Mohit Agarwala  Department of Electrical
Engineering, IIT Bombay<EMAIL_ADDRESS>,  R Sri Prakash  Department
of Electrical Engineering, IIT Bombay<EMAIL_ADDRESS>,  Nikhil
Karamchandani  Department of Electrical Engineering, IIT Bombay
<EMAIL_ADDRESS>and  Sharayu Moharir  Department of Electrical
Engineering, IIT Bombay<EMAIL_ADDRESS>
###### Abstract.

We consider the problem of service hosting where an application provider can
dynamically rent edge computing resources and serve user requests from the
edge to deliver a better quality of service. A key novelty of this work is
that we allow the service to be hosted partially at the edge which enables a
fraction of the user query to be served by the edge. We model the total cost
for (partially) hosting a service at the edge as a combination of the latency
in serving requests, the bandwidth consumption, and the time-varying cost for
renting edge resources. We propose an online policy called
$\alpha$-RetroRenting ($\alpha$-RR) which dynamically determines the fraction
of the service to be hosted at the edge in any time-slot, based on the history
of the request arrivals and the rent cost sequence. As our main result, we
derive an upper bound on $\alpha$-RR’s competitive ratio with respect to the
offline optimal policy that knows the entire request arrival and rent cost
sequence in advance. In addition, we provide performance guarantees for our
policy in the setting where the request arrival process is stochastic. We
conduct extensive numerical evaluations to compare the performance of
$\alpha$-RR with various benchmarks for synthetic and trace-based request
arrival and rent cost processes, and find several parameter regimes where
$\alpha$-RR’s ability to store the service partially greatly improves cost-
efficiency.

##  1\. Introduction

The emergence of services based on machine learning, computer vision, and
augmented/virtual reality (AR/VR) for resource-constrained handheld devices is
testing the limits of what traditional cloud-computing platforms can reliably
support in terms of the required latency and bandwidth. This has led to the
advent of edge computing wherein application providers can dynamically rent
storage/computing resources much closer to the end-users via short-term rent
contracts, and has also spurred a lot of academic research into the design and
implementation of cost-efficient dynamic algorithms for offloading computation
tasks (Zhao et al., 2018; Xia et al., 2020; Yang et al., 2015).

With respect to the prior work on service hosting, the key novelty of this
work is the option to partially host the service at the edge. We say that a
service is partially hosted when a fraction of the database and code of the
service is hosted at the edge. The partially hosted service can be used to
compute parts of the answers to user queries and deliver to the user with low
latency. The rest of the answer is computed and delivered from the cloud at
higher latency. Partial hosting requires lower edge resources than completely
hosting the service at the edge and therefore can potentially lead to a
reduction in the cost incurred for renting edge resources. To understand the
potential benefits of partial hosting for existing services, we use a GPS
trajectory dataset (Zheng et al., 2008, 2009, 2010) collected as a part of the
Geolife Project by Microsoft Research Asia to characterize the fraction of
requests that can be served at the edge as a function of the fraction of the
service hosted at the edge. The details of this dataset and our inferences
from it are discussed in the simulations section.

We consider two models of serving requests when the service is partially
hosted at the edge. In the first model, the service can be partitioned in a
way such that each partition can generate a partial response to a user’s
query/request and this partial response is of independent value to the user.
For instance, for a navigation service like Google Maps, one part of the
service could compute the possible routes between a source-destination pair,
and the other part could compute the travel time for these routes based on
current traffic patterns. Another example is online writing assistant services
like Grammarly where one part of the service spellchecks and the other part
checks grammar. One more example is a news website that uses the edge to
deliver the text corresponding to news articles at low latency to the user and
fetches the images/videos embedded in the article from the cloud at high
latency. In such cases, under partial hosting, the user can start reading
while the images/videos load from the cloud servers. When the service is
partially hosted, we assume that the fraction of the response to any user
query served by the edge is a non-decreasing function of the fraction of the
service stored.

In the second model, if a service is partially hosted at the edge, some of the
requests can be served by the edge, while the others have to be served by the
cloud servers. The fraction of requests that can be served at the edge is an
increasing function of the fraction of service hosted at the edge. For
example, for a service like Google Translate, under partial hosting, the edge
can be equipped to handle translation requests for some language pairs, while
the rest have to be served by the cloud servers.

###  1.1. Main Contributions

In this work, we restrict the discussion to the setting which allows one
partial hosting level $\alpha$, apart from the option of not hosting and
complete hosting of the service. We model the total cost for (partially)
hosting a service at the edge as a combination of the latency in serving
requests, the bandwidth consumption, and the time-varying cost for renting
edge resources which is assumed to scale linearly with the fraction of the
service cached. The broad goal in this work is to design cost-efficient
schemes which dynamically decide when and what fraction of the service to host
at the edge. The main contributions of our work are as follows.

  1. –

We propose an online policy called $\alpha$-RetroRenting ($\alpha$-RR) which
dynamically determines the fraction of the service to be hosted at the edge in
any time-slot, based on the history of the request arrivals and the rent cost
sequence.

  2. –

We compare the performance of $\alpha$-RR with the offline optimal policy
which knows the entire request arrival and rent cost sequence in advance. We
characterize conditions under which $\alpha$-RR is optimal and show that in
the worst-case, $\alpha$-RR is $6$-optimal.

  3. –

In the setting where request arrivals are i.i.d. stochastic, we provide
performance guarantees for $\alpha$-RR and compare its performance to that of
the optimal online policy.

  4. –

We characterize conditions under which the offline optimal policy and
$\alpha$-RR do not use partial hosting. This result can be used by service
designers as a guideline on how to partition their service so that partial
hosting can be used effectively to improve the performance of the system.

  5. –

We characterize a fundamental limit on the performance of any online
deterministic policy, which helps benchmark the performance of the $\alpha$-RR
scheme proposed in this work.

  6. –

Finally, we conduct extensive numerical evaluations to compare the performance
of $\alpha$-RR with various policies including those that do not use partial
hosting for synthetic and trace-based request arrival and rent cost processes.
We find that there are several parameter regimes where $\alpha$-RR outperforms
other baselines and the ability to store the service partially can greatly
improve cost-efficiency.

###  1.2. Related Work

With applications based on the Internet of Things, AR/VR, and large-scale
machine learning becoming more mainstream, various edge computing platforms
and architectures have been developed (Puliafito et al., 2019; Mao et al.,
2017; Mach and Becvar, 2017) which can reliably support the stringent latency
and bandwidth requirements. There has also been a large amount of academic
research on such systems, amongst which that focusing on the design and
analysis of efficient task offloading algorithms is the most relevant to our
work and we discuss some of it below.

The broad setting where our work is placed is when there are one or more edge
servers which assist clients in carrying out computation tasks and the goal is
to determine which tasks to offload to the edge server(s) so that the overall
cost is minimized. One approach towards the design of such schemes is to
formulate the problem as a large-scale one-shot optimization problem (Pasteris
et al., 2019; Bi et al., 2020; Chen and Xu, 2017; Tran et al., 2019; Yang et
al., 2015; Xu et al., 2020; Ascigil et al., 2021). While solving the problem
exactly turns out to be NP-hard in several instances, efficient heuristics are
presented. Recently, (Ascigil et al., 2021) studied the impact of
decentralization on the performance of such task offloading schemes. Finally,
(Yan et al., 2021) used a game-theoretic approach to study the problem by
considering a two-stage interactive game between an edge server and the users,
wherein the server announces prices for hosting various services in the first
stage and each user independently makes its offloading decision in the second
round. Our work differs from this line of work in that we design online
algorithms which adapt their service placement decisions dynamically over time
depending on the varying number of requests and rental costs.

Several works consider stochastic models for incorporating time-varying
requests (Xu et al., 2018; Chen and Xu, 2019; Wang et al., 2015; He et al.,
[n.d.]; Xiong et al., [n.d.]), using frameworks such as Markov Decision
Processes (MDPs), Reinforcement Learning and Multi-Armed Bandits to address
scenarios where system parameters such as service popularity or task request
rates are unknown. On the other hand, we 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 key distinguishing feature of our work with respect to almost all the
literature is that we allow partial service hosting at the edge which allows
part of the query response to be provided at low latency by the edge server
and the rest at higher latency by the back-end cloud server. As we will see
later, this can potentially lead to significant cost benefits for the
application provider. While (Prakash et al., 2020) also considered partial
service hosting, its focus was on stochastic request processes and expected
cost, whereas we consider the ‘adversarial’ setting with worst-case cost
guarantees. In (Narayana et al., 2021a), the possible hosting options are
limited to either fully hosting the service at the edge or not hosting it at
the edge at all. In this work, we generalize this setting to include a third
intermediate/partial hosting level. The details are discussed in the next
section. This key difference necessitates new algorithm design and performance
analysis.

In (Zhao et al., 2018), the authors consider a system with multiple services
and an edge server with limited capacity, and proposed an online scheme named
ReD/LeD for deciding which services to host on the edge at each time whose
performance is characterized in terms of the competitive ratio with respect to
an oracle which knows the entire request sequence in advance. The competitive
ratio analysis was recently extended to a system with multiple connected
caches in (Tan et al., 2021). Unlike (Zhao et al., 2018; Tan et al., 2021) and
other works mentioned above which optimize the system from the perspective of
the access providers which rent out edge computing resources, we study the
problem from the perspective of an application provider which provides a
service to the end users. Other works which have studied service hosting at
the edge from this perspective include (Lakshmi Narayana et al., 2020; Prakash
et al., 2020; Xia et al., 2020) where the goal is to minimize the cost
incurred by the application provider while serving the user requests. Although
we study the 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 potentially limited edge resources
offered by the access providers is captured through the time-varying nature of
the cost of renting edge resources.

While the problem of service hosting does resemble the long-studied content
caching problem (Borst et al., 2010; Tan and Massoulié, 2012; Wolman et al.,
1999; Breslau et al., 1999; Sleator and Tarjan, 1985; Belady, 1966), there are
important differences. In particular, unlike the content caching problem,
whenever a user request cannot be served at the edge there is an option to
either simply forward that request or download the entire service at higher
cost. This fundamentally changes the problem and in fact, prior work (Zhao et
al., 2018; Lakshmi Narayana et al., 2020) has demonstrated the sub-optimal
performance for service hosting of several popular schemes which work well in
the traditional content caching setting. Finally, we would like to point out
that partial storage of files has been studied in the context of traditional
content caching (Borst et al., 2010; Hefeeda and Saleh, 2008). Here, the
fraction of query served varies linearly with the fraction of the file stored,
whereas the dependence can be more varied for the service caching problem
studied in this work. We indeed observe such behavior for a shortest path
query system we design using data from a GPS trajectory dataset (Zheng et al.,
2008, 2009, 2010). Details can be found in the simulations section.

##  2\. System Setup

###  2.1. Network Model

We study a system consisting of one or more cloud servers and an edge server
in proximity to the customers/users of a service. The cloud servers always
host the service and can serve all requests that are routed to them. In
addition, the service can also be hosted at the edge server to serve user
requests by paying a rent cost for using edge resources. We allow for partial
hosting at the edge, i.e., only a part of the service can be hosted at the
edge. Details of how requests are served when only a part of the service is
hosted at the edge are discussed in subsequent sections.

###  2.2. Request Arrivals

We consider a time-slotted system with two different arrival patterns viz.,
adversarial and stochastic request arrivals. Let $x_{t}$ denote the number of
request arrivals in a time-slot $t$. For our analytical results for
adversarial arrivals, we make the following assumptions on the arrival
sequence.

###### Assumption 1.

At most one request arrives in each time-slot, i.e., $x_{t}\in\\{0,1\\}$.

Further, for our analytical results for stochastic arrivals, we make the
following additional assumption.

###### Assumption 2.

Request arrivals are i.i.d. across time-slots.

###### Remark 1.

Our results can be extended to the setting considered in (Lakshmi Narayana et
al., 2020) with potentially multiple request arrivals in a time-slot and an
upper bound on the number of requests that can be served at the edge in a
time-slot. In simulations, we consider different cases where the request
arrival process is Adversarial, Poisson, and Markovian.

###  2.3. Renting Edge Resources

Edge resources can be rented from a third party edge resource provider by
paying a rent cost. The rent cost for a time-slot is determined and advertised
by the third party provider. Let $c_{t}$ denote the cost of hosting the entire
service at the edge in time-slot $t$. If the service is partially hosted at
the edge in a time-slot, the rent cost is scaled proportional to the fraction
of service hosted at the edge. For our analytical results, we make the
following assumptions on the rent cost sequence.

###### Assumption 3.

$0<c_{\text{min}}\leq c_{t}\leq c_{\text{max}}$.

###### Remark 2.

The time-varying nature of the rent cost captures the effect of the presence
of multiple customers of the third-party edge resource provider and the
potential fluctuation in the overall demand for the edge resources.

###  2.4. Partial Service Hosting

As discussed above, we allow the service to be partially hosted at the edge.
Let $r_{t}$ denote the fraction of service hosted at the edge in time-slot
$t$. Recall that in this work, we restrict the discussion to the setting which
allows three hosting levels. Formally, we make the following assumption.

###### Assumption 4.

In addition to the option of hosting the entire service at the edge as in
(Zhao et al., 2018; Lakshmi Narayana et al., 2020), in this work,
$\alpha\in(0,1)$ fraction of the service can also be hosted at the edge. It
follows that $r_{t}=\\{0,\alpha,1\\}$, where $r_{t}=0$ denotes that the
service is not hosted at the edge in time-slot $t$.

We consider the following two service models when the service is partially
hosted at the edge.

###### Model 1 (Partial Service at the Edge).

When the service is partially hosted at the edge, an incoming request can be
partially served by the edge servers, i.e., a part of the answer to the user’s
query can be computed at the edge. We focus on services where this partial
answer is of independent interest to the user. Thus, the part of the answer
computed at the edge can be communicated to the user with low latency due to
the proximity of the user to the edge servers. The answer to the rest of the
query is computed at the cloud and delivered to the user at high latency.

###### Model 2 (i.i.d. Randomized Service at the Edge).

When the service is partially hosted at the edge, each arriving request can be
served at the edge with a probability which is a non-decreasing function of
the fraction of service hosted; else the request is served by the cloud
servers.

###  2.5. Sequence of Events in a Time-slot

In each time-slot, we first have potential request arrivals. These requests
are then served by the edge/cloud servers. The third-party edge resource
provider then announces the rent cost the for next time-slot. Following this,
our system determines the fraction of service to be hosted at the edge in the
next time-slot.

###  2.6. Cost Model

We build on the models used in (Lakshmi Narayana et al., 2020; Zhao et al.,
2018) when the requests are adversarial and consider three categories of
costs. For a given hosting policy $\mathcal{P}$, the total cost incurred in
time-slot $t$, denoted by $C_{t}^{\mathcal{P}}$, is the sum of the three
costs.

  1. –

_Fetch cost $(C_{F,t}^{\mathcal{P}})$_: This is the cost incurred to fetch the
service (code and databases/libraries) from the cloud server(s) to host on the
edge server. On each fetch of $\Delta_{t}=(r_{t+1}-r_{t})^{+}$ fraction the
service from the cloud server(s) to host on the edge-server, a fetch cost of
$\Delta_{t}M$ units is incurred, where $\Delta_{t}\in\\{1,\alpha,1-\alpha\\}$.

  2. –

_Rent cost $(C_{R,t}^{\mathcal{P}})$_: This is the cost incurred to rent edge
resources to host the service. A rent cost of $c_{t}r_{t}$ units is incurred
to host $r_{t}$ fraction of the service on the edge server in time-slot $t$.

  3. –

_Service cost $(C_{S,t}^{\mathcal{P}})$_: This is the cost incurred per
request for using the cloud servers.

Under Model 1, since only that part of the request which cannot be served at
the edge is forwarded to the cloud servers, this cost is a decreasing function
of the fraction of service hosted at the edge in that time-slot. Let
$g(r_{t})$ denote the cost incurred per request in time-slot $t$. We assume
that

$\displaystyle g(r_{t})=\begin{cases}1&r_{t}=0\\\
g(\alpha)\in(0,1)&r_{t}=\alpha\\\ 0&r_{t}=1.\\\ \end{cases}$

Under Model 2, when the entire service is hosted at the edge, each incoming
request can be served at no cost. When the service is not hosted at the edge,
each incoming request is forwarded to the cloud server which serves it at a
cost of one unit per request. We now discuss the case when the service is
partially hosted at the edge under Model 2. Let $X_{t}$ be the number of
requests received in a time-slot. Recall that $r_{t}$ denotes the fraction of
service hosted on the edge server during time-slot $t$. When $r_{t}=\alpha$,
each incoming request can be served at the edge with zero cost with
probability $(1-g(\alpha))$ and has to be forwarded to the cloud otherwise. It
follows that each arriving request incurs a cost of one unit with probability
$g(\alpha)$ and zero units with probability $1-g(\alpha)$. Formally, for
$r_{t}=\alpha$ and $X_{t}>0$, the service cost for each request is given by,

$\displaystyle S_{t}^{i}$ $\displaystyle=\begin{cases*}1&\text{ with
probability $g(\alpha)$ }\\\ 0&\text{ with probability $1-g(\alpha)$. }\\\
\end{cases*}$

for $i\in\\{1,\ldots,X_{t}\\}.$ Let $S_{t}$ denote the total service cost in a
time-slot $t$ when $r_{t}=\alpha$ and $X_{t}>0$. Thus

$S_{t}=\displaystyle\sum_{i=1}^{X_{t}}S_{t}^{i}.$

It follows that

(1) $\displaystyle C_{t}^{\mathcal{P}}$
$\displaystyle=C_{F,t}^{\mathcal{P}}+C_{R,t}^{\mathcal{P}}+C_{S,t}^{\mathcal{P}},$
$\displaystyle\text{where, }C_{F,t}^{\mathcal{P}}$
$\displaystyle=\begin{cases*}M&\text{ if $r_{t}=0$ and $r_{t+1}=1$ }\\\ \alpha
M&\text{ if $r_{t}=0$ and $r_{t+1}=\alpha$ }\\\ (1-\alpha)M&\text{ if
$r_{t}=\alpha$ and $r_{t+1}=1$ }\\\ 0&\text{ otherwise.}\end{cases*}$
$\displaystyle C_{R,t}^{\mathcal{P}}$
$\displaystyle=\begin{cases*}c_{t}&\text{ if $r_{t}=1$ }\\\ c_{t}\alpha&\text{
if $r_{t}=\alpha$ }\\\ 0&\text{ otherwise.}\end{cases*}$
$\displaystyle\text{For Model \ref{model:partial}: }C_{S,t}^{\mathcal{P}}$
$\displaystyle=\begin{cases*}0&\text{ if $r_{t}=1$ }\\\ g(\alpha)x_{t}&\text{
if $r_{t}=\alpha$ }\\\ x_{t}&\text{ otherwise.}\end{cases*}$
$\displaystyle\text{For Model \ref{model:random}: }C_{S,t}^{\mathcal{P}}$
$\displaystyle=\begin{cases*}0&\text{ if $r_{t}=1$ }\\\ S_{t}&\text{ if
$X_{t}>0$ and $r_{t}=\alpha$}\\\ X_{t}&\text{ otherwise.}\end{cases*}$

Typically, the amount of data (code and databases/libraries) needed to host
the service at the edge is much larger than the amount of data delivered to a
user in response to a request. Motivated by this, we make the following
assumption, also made in (Lakshmi Narayana et al., 2020; Zhao et al., 2018).

###### Assumption 5.

The cost of fetching the service is more than the cost incurred to use the
cloud servers to answer a request, i.e., $M>1$.

###  2.7. Algorithmic Challenge

The algorithmic challenge is to design a policy determines the fraction of
service hosted at the edge in each time-slot. Hosting policies can be divided
into the following two classes.

###### Definition 0.

(Types of Hosting Policies)

  1. –

_Offline Policies_ : A policy in this class knows the entire request arrival
sequence and rent cost sequence a priori.

  2. –

_Online Policies_ : A policy in this class does not have knowledge of future
arrivals and rent cost sequence.

We design an online policy which makes hosting decisions based on the request
arrivals, rent costs thus far, intermediate hosting level ($\alpha$) and the
various costs, i.e., the rent cost $(c_{t})$ in a time-slot $t$, the fetch
cost $(M)$, and the forwarding cost $g(\alpha)$.

###  2.8. Metric and Goal

  1. –

In the adversarial setting, the optimal offline policy ($\alpha$-OPT) serves
as a benchmark to evaluate the performance any online policy $\mathcal{P}$.
The goal is to design an online policy $\mathcal{P}$ which minimizes the
competitive ratio $\rho^{\mathcal{P}}$ defined as

(2)
$\rho^{\mathcal{P}}=\sup_{a\in\mathcal{A},d\in\mathcal{R}}\frac{C^{\mathcal{P}}(a,d)}{C^{\text{$\alpha$-OPT}}(a,d)},$

where $\mathcal{A}$, $\mathcal{R}$ are the set of all possible finite request
arrival sequences and the set of all possible rent cost sequences
respectively. $C^{\mathcal{P}}(a,d)$, $C^{\text{$\alpha$-OPT}}(a,d)$ are the
overall costs of service for the request arrival sequence $a$, the rent cost
sequence $d$ under online policy $\mathcal{P}$ and the optimal offline policy
respectively.

  2. –

In the stochastic setting, we compare the performance of a policy
$\mathcal{P}$ with the performance of the optimal online policy ($\alpha$-OPT-
ON).

The goal is to minimize $\sigma^{\mathcal{P}}_{T}$, defined as the ratio of
the expected cost incurred by policy $\mathcal{P}$ in $T$ time-slots to that
of the optimal online policy in the same time interval. Formally,

(3)
$\sigma^{\mathcal{P}}(T)=\frac{\mathbb{E}\bigg{[}\displaystyle\sum_{t=1}^{T}C_{t}^{\mathcal{P}}\bigg{]}}{\mathbb{E}\bigg{[}\displaystyle\sum_{t=1}^{T}C_{t}^{\alpha\text{-OPT-
ON}}\bigg{]}},$

where $C_{t}^{\mathcal{P}}$ is as defined in (1).

##  3\. Our Hosting Policy

In this section, we present our online edge hosting policy called
$\alpha$-RetroRenting. The high-level idea behind the policy is to evaluate if
the current hosting status under $\alpha$-RetroRenting is optimal in hindsight
given the knowledge of the request arrival/rent cost process up to the current
time. If not, $\alpha$-RetroRenting changes the hosting status. A formal
definition is given in Algorithm 1 and a detailed description of the policy is
as follows.

1 Input: Fetch cost $M$, partial hosting level $\alpha$, latency cost under
partial hosting $g(\alpha)$, rent cost sequence $\\{c_{l}\\}_{l\geq 0}^{t}$,
request arrival sequence $\\{x_{l}\\}_{l\geq 0}^{t}$

2 Output: service hosting strategy $r_{t+1}$, $t>0$

3 Initialize: $r_{1}=t_{\text{recent}}=0$

4 for  _each time-slot $t$_ do

5 $I_{t}=(M$, $g(\alpha)$, $t$, $t_{\text{recent}}$, $\\{c_{l}\\}_{l\geq
t_{\text{recent}}}^{t}$, $\\{x_{l}\\}_{l\geq t_{\text{recent}}}^{t})$

6
$R_{0}^{(\tau_{0})}=[\underbrace{r_{t},r_{t},\ldots,r_{t}}_{\tau_{0}-t_{\text{recent}}},\underbrace{0,0,\ldots,0}_{t-\tau_{0}}]$

7
$R_{\alpha}^{(\tau_{\alpha})}=[\underbrace{r_{t},r_{t},\ldots,r_{t}}_{\tau_{\alpha}-t_{\text{recent}}},\underbrace{\alpha,\alpha,\ldots,\alpha}_{t-\tau_{\alpha}}]$

8
$R_{1}^{(\tau_{1})}=[\underbrace{r_{t},r_{t},\ldots,r_{t}}_{\tau_{1}-t_{\text{recent}}},\underbrace{1,1,\ldots,1}_{t-\tau_{1}}]$

9
$\text{minCost}(0)=\displaystyle\min_{\tau_{0}\in(t_{\text{recent}},t)}\textnormal{{totalCost}}(R_{0}^{(\tau_{0})},I_{t})$

10
$\text{minCost}(\alpha)=\displaystyle\min_{\tau_{\alpha}\in(t_{\text{recent}},t)}\textnormal{{totalCost}}(R_{\alpha}^{(\tau_{\alpha})},I_{t})$

11
$\text{minCost}(1)=\displaystyle\min_{\tau_{1}\in(t_{\text{recent}},t)}\textnormal{{totalCost}}(R_{1}^{(\tau_{1})},I_{t})$

12 $r_{t+1}=\displaystyle\arg\min_{i\in\\{0,\alpha,1\\}}\text{minCost}(i)$

13 if  _$r_{t+1}\neq r_{t}$_ then

14 $t_{\text{recent}}=t$

15 end if

16

17 end for

18Function  _totalCost(_$R,I_{t}$_)_:

19 $g(0)=1$, $g(1)=0$;

20 cost = $R(1)\times c_{1}+x_{1}\times g(R(1))$;

21 for  _$j\leftarrow 2$ to $t-t_{\text{recent}}$ _ do

22 cost = cost $+R(j)\times c_{j}+x_{j}\times g(R(j))$

23 $+M\times\left|R(j)-R(j-1)\right|$;

24

25 end for

26 return cost;

27 end

Algorithm 1 $\alpha$-RetroRenting ($\alpha$-RR)

In each time-slot, $\alpha$-RetroRenting focuses on the time-frame starting
from the most recent time-slot in which the hosting status was changed under
$\alpha$-RetroRenting ($t_{\text{recent}}$) to the current time-slot ($t$). It
follows that the hosting status under $\alpha$-RetroRenting is constant in
this time-frame.

$\alpha$-RetroRenting then considers two alternative hosting strategies in
which the hosting status is changed to one of the other two hosting levels at
some point in the time-frame and remains unchanged thereafter. Lines 6-8 in
Algorithm 1 represent these two alternative hosting strategies in addition to
the hosting status under $\alpha$-RetroRenting.

In Lines 9-11, $\alpha$-RetroRenting computes the lowest possible total cost
(fetch cost + rent cost + latency cost) incurred in the time-frame under each
one of the three candidate hosting strategies by optimizing the time at which
the hosting status is changed in the time-frame. The function totalCost (Lines
17-25) is used to compute the total cost incurred for specific hosting,
request arrival, and rent cost sequences.

Following this, in Line 12, $\alpha$-RetroRenting sets the value of the
hosting level for the next time-slot ($r_{t+1}$) to the hosting level at time
$t$ in the hosting strategy which has the least cost among the three
candidates.

###### Remark 3.

While the computation/storage complexity of $\alpha$-RetroRenting as presented
in Algorithm 1 can scale with time, using techniques proposed in (Lu et al.,
2012) and used in (Narayana et al., 2021a), both the computation/storage
complexity of $\alpha$-RetroRenting can be reduced to $O(1)$. We omit the
details due to lack of space.

##  4\. Analytical Results: Adversarial Setting

In this section, we state and discuss our analytical results. The proofs of
there results are discussed in Section 9.

Our first result characterizes sufficient conditions under which the optimal
offline policy ($\alpha$-OPT) and our policy $\alpha$-RR do not partially host
the service at the edge.

###### Theorem 1.

Consider a system satisfying Assumptions 1-5 and Model 1. Let
$r^{*}_{\tilde{t}}$ and $r^{\alpha\text{-RR}}_{\tilde{t}}$ be the fraction of
service hosted on the edge in time-slot $t$ under $\alpha$-OPT and
$\alpha\text{-RR}$ respectively.

  1. (a)

If $\alpha+g(\alpha)\geq 1$ and $r^{*}_{\tilde{t}}\neq\alpha$,
$r^{*}_{t}\neq\alpha$, for all $t>\tilde{t}$

  2. (b)

If $\alpha+g(\alpha)\geq 1$, $r^{\alpha\text{-RR}}_{t}\neq\alpha$, for all
$t>0$.

We thus conclude that if $\alpha+g(\alpha)\geq 1$, if the service is either
fully hosted or not hosted at the edge in a time-slot, the offline optimal
policy does not use partial hosting in all subsequent time-slots. In addition,
for $\alpha+g(\alpha)\geq 1$, our policy $\alpha$-RR never uses partial
hosting.

The condition $\alpha+g(\alpha)\geq 1$ imposes an upper bound on the
difference between the service cost when the service is not hosted at the edge
(one unit) and the service cost under partial hosting ($g(\alpha)$ units). The
take-away from the result is that if the reduction in service cost due to
partial hosting is less than the fraction of service hosted under partial
hosting, the offline optimal policy and our policy make limited use of partial
hosting.

Our next result provides performance guarantees for $\alpha$-RR.

###### Theorem 2.

Let $\rho^{\alpha\text{-RR}}$ be the competitive ratio of $\alpha$-RR policy
as defined in (2). Under Assumptions 1-5 and under Model 1,

  1. (a)

if $\alpha c_{\text{min}}+g(\alpha)\geq 1$ and $c_{\text{min}}\geq 1$ then
$\rho^{\alpha\text{-RR}}=1,$

  2. (b)

if $c_{\text{min}}<1$ or $\alpha c_{\text{min}}+g(\alpha)<1$, then

$\rho^{\alpha\text{-RR}}\leq
4+\dfrac{1}{M}+\max\left\\{\dfrac{1}{M},\dfrac{1-g(\alpha)}{M\alpha}\right\\}.$

This result characterizes sufficient conditions under which $\alpha$-RR is
optimal, i.e., its performance matches that of the offline optimal policy
which knows the entire request arrivals/rent cost sequences a priori. In
addition, it provides an upper bound on the cost incurred in the worst-case.

Recall that the cost of fetching $x\in\\{\alpha,1\\}$ fraction of the service
is $Mx$. Also, the service cost of using the the cloud servers to serve the
part of the request corresponding to $x\in\\{\alpha,1\\}$ fraction of the
service is $1-g(x)$, where, by definition, $g(1)=0$. Typically, the
answers/responses to user queries are significantly shorter than the code and
database/libraries used to compute these answers. Motivated by this, we
consider the following.

###### Assumption 6.

For a given value of $x\in\\{\alpha,1\\}$, the cost of fetching that fraction
of the service (given by $Mx$) is more than service cost of using the the
cloud servers to serve the part of the request corresponding to $x$ (given by
$1-g(x)$). It follows that,

$M>\max\left\\{1,\dfrac{1-g(\alpha)}{\alpha}\right\\}.$

The following result provides the universal upper bound on the worst case
performance of $\alpha$-RR under Assumptions 1-6.

###### Corollary 3.

Let $\rho^{\alpha\text{-RR}}$ be the competitive ratio of $\alpha$-RR policy
as defined in (2). Under Assumptions 1-6 and under Model 1, if
$c_{\text{min}}<1$ or $\alpha c_{\text{min}}+g(\alpha)<1$, then
$\rho^{\alpha\text{-RR}}\leq 6.$

Our next result characterizes a fundamental limit on the performance of any
deterministic online policy.

###### Theorem 4.

Consider a system satisfying Assumptions 1-5 and Model 1. Let $\mathcal{P}$ be
any deterministic online policy and let

$f(u,v)=1+\frac{(uM+uc_{\text{min}}+g(u))(1-vc_{\text{min}}-g(v))}{vM}.$

(a) If $c_{\text{min}}<1$ and $\alpha c_{\text{min}}+g(\alpha)<1$,

$\displaystyle\rho^{\mathcal{P}}\geq$
$\displaystyle\min\left\\{\min_{(u=v)\in\\{\alpha,1\\}}f(u,v),\min_{u\in\\{\alpha,1\\}}\frac{1}{uc_{\text{min}}+g(u)}\right\\}>1.$

(b) If $c_{\text{min}}<1$ and $\alpha c_{\text{min}}+g(\alpha)\geq 1$,

$\displaystyle\rho^{\mathcal{P}}\geq$
$\displaystyle\min\left\\{\min_{u\in\\{\alpha,1\\}}f(u,1),\frac{1}{c_{\text{min}}}\right\\}>1.$

(c) If $c_{\text{min}}\geq 1$ and $\alpha c_{\text{min}}+g(\alpha)<1$,

$\displaystyle\rho^{\mathcal{P}}\geq$
$\displaystyle\min\left\\{\min_{u\in\\{\alpha,1\\}}f(u,\alpha),\frac{1}{\alpha
c_{\text{min}}+g(\alpha)}\right\\}>1.$

From Theorems 2 and 4, we conclude that if $\alpha
c_{\text{min}}+g(\alpha)\geq 1$ and $c_{\text{min}}\geq 1$, $\alpha$-RR
performs as well as the offline optimal policy and if $c_{\text{min}}<1$
and/or $\alpha c_{\text{min}}+g(\alpha)<1$, no deterministic online policy can
match the performance of the offline optimal policy. That is, if
$c_{\text{min}}<1$ and/or $\alpha c_{\text{min}}+g(\alpha)<1$ no deterministic
online policy can have a competitive ratio equal to one whereas in this case
the competitive ratio of $\alpha$-RR is is uniformly bounded by six
independent of various system parameters.

##  5\. Analytical Results: Stochastic Setting

In this section, we characterize the performance of $\alpha$-RetroRenting
($\alpha$-RR) for stochastic request arrivals and rent cost process. Our
analytical results hold under the following assumptions of the request arrival
and rent cost processes.

###### Assumption 7 (Request arrivals and rent cost).

  1. –

The request arrival process $X_{t}$, $t=1,2,\cdots$ is i.i.d. across time with
$X_{t}\sim\text{Ber}(p)$.

  2. –

The rent cost process $Z_{t}$, $t=1,2,\cdots$ is negatively associated (Wajc,
2017) with mean $c$ where $c\in[c_{\text{min}},c_{\text{max}}]$. Note that the
case where $Z_{t}$ is i.i.d. across time is a special case of negative
association.

We first define three functions $f(),q(),$ and $h()$ which are used in our
main result. These functions contain the terms which are obtained by using
Hoeffding’s inequality to bound the probability of certain events. We
introduce these functions to represent the final result in a compact form.

The function $f(\lambda,M,p,c,\alpha,g(\alpha))$ is defined as follows:

$\displaystyle f(\lambda,M,p,c,\alpha,g(\alpha))=$
$\displaystyle\max\\{M+p,M+c\\}\Bigg{[}\frac{\lambda\widetilde{M}_{f}\delta_{A}^{f}\exp\left(-2(\frac{M}{c_{\text{max}}}+1)\frac{(p(1-g(\alpha))-\alpha
c)^{2}}{(1+\alpha c_{\text{max}}-\alpha
c_{\text{min}})^{2}}\right)}{1-\exp\left(-2\frac{(p(1-g(\alpha))-\alpha
c)^{2}}{(1+\alpha c_{\text{max}}-\alpha c_{\text{min}})^{2}}\right)}+$
$\displaystyle\frac{\lambda\widetilde{M}_{f}\delta_{B}^{f}\exp\left(-2(\frac{(1-\alpha)M}{1-(1-\alpha)c_{\text{min}}}+1)\frac{((1-\alpha)c-pg(\alpha))^{2}}{(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right)}{1-\exp\left(-2\frac{((1-\alpha)c-pg(\alpha))^{2}}{(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right)}+$
$\displaystyle\exp\left(\frac{-2(\lambda-1)^{2}M^{2}(1-\alpha)^{2}}{\lambda\widetilde{M}(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right)+\exp\left(\frac{-2(\lambda-1)^{2}M^{2}\alpha^{2}}{\lambda\widetilde{M}(1+\alpha(c_{\text{max}}-c_{\text{min}}))^{2}}\right)\Bigg{]},$

where

$\widetilde{M}_{f}=\max\Bigg{\\{}\left\lceil\frac{M\alpha}{p(1-g(\alpha))-\alpha
c}\right\rceil,\left\lceil\frac{M(1-\alpha)}{(1-\alpha)c-pg(\alpha)}\right\rceil\Bigg{\\}},$
$\delta_{A}^{f}=\exp\left(\frac{-4(p(1-g(\alpha))-\alpha c))\alpha
M}{(1+\alpha c_{\text{max}}-\alpha c_{\text{min}})^{2}}\right),$

and

$\delta_{B}^{f}=\exp\left(\frac{-4((1-\alpha)c-pg(\alpha)))(1-\alpha)M}{(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right).$

The function $q(\lambda,M,p,c,\alpha,g(\alpha))$ is defined as follows:

$\displaystyle q(\lambda,M,p,c,\alpha,g(\alpha))=$ $\displaystyle\max\\{\alpha
M+\alpha
c+g(\alpha)p,M+c\\}\Bigg{[}\frac{\delta_{A}^{q}\lambda\widetilde{M}_{q}\exp\left(-2(\frac{M}{c_{\text{max}}}+1)\frac{(p-c)^{2}}{(1+c_{\text{max}}-\alpha
c_{\text{min}})^{2}}\right)}{1-\exp\left(-2\frac{(p-c)^{2}}{(1+c_{\text{max}}-c_{\text{min}})^{2}}\right)}+$
$\displaystyle\frac{\delta_{B}^{q}\lambda\widetilde{M}_{q}\exp\left(-2(\frac{M}{c_{\text{max}}}+1)\frac{(pg(\alpha)-(1-\alpha)c)^{2}}{(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right)}{1-\exp\left(-2\frac{(pg(\alpha)-(1-\alpha)c)^{2}}{(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right)}+$
$\displaystyle\exp\left(\frac{-2(\lambda-1)^{2}M^{2}(1-\alpha)^{2}}{\lambda\widetilde{M}_{q}(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right)+\exp\left(\frac{-2(\lambda-1)^{2}M^{2}\alpha^{2}}{\lambda\widetilde{M}_{q}(1+\alpha(c_{\text{max}}-c_{\text{min}}))^{2}}\right)\Bigg{]},$

where

$\widetilde{M}_{q}=\max\Bigg{\\{}\frac{M}{p-c},\left\lceil\frac{M(1-\alpha)}{pg(\alpha)-(1-\alpha)c}\right\rceil\Bigg{\\}},$
$\delta_{A}^{q}=\exp\left(\frac{-4(p-c)\alpha
M}{(1+c_{\text{max}}-c_{\text{min}})^{2}}\right),$
$\delta_{B}^{q}=\exp\left(\frac{-4(pg(\alpha)-(1-\alpha)c))(1-\alpha)M}{(1+(1-\alpha)(c_{\text{max}}-c_{\text{min}}))^{2}}\right),$

The function $h(\lambda,M,p,c,\alpha,g(\alpha))$ is defined as follows:

$\displaystyle h(\lambda,M,p,c,\alpha,g(\alpha))=$ $\displaystyle\max\\{\alpha
M+\alpha
c+g(\alpha)p,M+p\\}\Bigg{[}\frac{2\lambda\widetilde{M}_{h}\delta_{A}^{h}\exp\left(-2(\frac{M}{1-c_{\text{min}}}+1)\frac{(c-p)^{2}}{(1+c_{\text{max}}-\alpha
c_{\text{min}})^{2}}\right)}{1-\exp\left(-2\frac{(c-p)^{2}}{(1+c_{\text{max}}-c_{\text{min}})^{2}}\right)}+$
$\displaystyle\frac{2\lambda\widetilde{M}_{h}\delta_{B}^{h}\exp\left(-2(\frac{\alpha
M}{1-g(\alpha)-\alpha c_{\text{min}}}+1)\frac{((\alpha
c-p(1-g(\alpha)))^{2}}{(1+\alpha(c_{\text{max}}-c_{\text{min}}))^{2}}\right)}{1-\exp\left(-2\frac{(\alpha
c-p(1-g(\alpha)))^{2}}{(1+\alpha(c_{\text{max}}-c_{\text{min}}))^{2}}\right)}+$
$\displaystyle\exp\left(\frac{-2(\lambda-1)^{2}M^{2}\alpha^{2}}{\lambda\widetilde{M}_{h}(1+\alpha(c_{\text{max}}-c_{\text{min}}))^{2}}\right)+\exp\left(\frac{-2(\lambda-1)^{2}M^{2}}{\lambda\widetilde{M}_{h}(1+(c_{\text{max}}-c_{\text{min}}))^{2}}\right)\Bigg{]},$

where

$\widetilde{M}_{h}=\max\Bigg{\\{}\frac{M}{c-p},\left\lceil\frac{M\alpha}{\alpha
c-p(1-g(\alpha))}\right\rceil\Bigg{\\}},$
$\delta_{A}^{h}=\exp\left(\frac{-4(c-p)\alpha
M}{(1+c_{\text{max}}-c_{\text{min}})^{2}}\right),$
$\delta_{B}^{h}=\exp\left(\frac{-4(\alpha c-p(1-g(\alpha))\alpha
M}{(1+\alpha(c_{\text{max}}-c_{\text{min}}))^{2}}\right).$

###### Remark 4.

Note that the functions $f(),q(),$ and $h()$ contain terms which are products
of linearly increasing functions of $M$ and exponentially decaying functions
of $M$. It follows that as $M$ increases, $f(),q(),$ and $h()$ tend to zero.

Our next theorem characterizes the performance of $\alpha$-RR in terms of our
performance metric defined in (3).

###### Theorem 1.

Under Assumption 7 and under Model 2,

  * –

Case $\frac{\alpha c}{1-g(\alpha)}<p<\frac{(1-\alpha)c}{g(\alpha)}$:

$\displaystyle\sigma^{\alpha-\text{RR}}(T)\leq
1+\min_{\lambda>1}\frac{f(\lambda,M,p,c,\alpha,g(\alpha))}{\alpha
c+g(\alpha)p}$

  * –

Case $p>\max\\{c,\frac{(1-\alpha)c}{g(\alpha)}\\}$:

$\displaystyle\sigma^{\alpha-\text{RR}}(T)\leq
1+\min_{\lambda>1}\frac{q(\lambda,M,p,c,\alpha,g(\alpha))}{M+c}$

  * –

Case $p<\min\\{c,\frac{\alpha c}{1-g(\alpha)}\\}$:

$\displaystyle\sigma^{\alpha-\text{RR}}(T)\leq
1+\min_{\lambda>1}\frac{h(\lambda,M,p,c,\alpha,g(\alpha))}{c}$

###### Remark 5.

We thus conclude that the the cost incurred by $\alpha$-RR approaches the cost
incurred by the online optimal policy $\alpha$-OPT-ON as $M$ increases.

##  6\. Simulation Results: Model 1

In this section, we present our simulation results for Model 1. In addition to
plotting the performance of $\alpha$-OPT, $\alpha$-RetroRenting, and the lower
bound on the performance of any online policy ($\alpha$-LB), we also simulate
two policies which do not use partial hosting. We refer to the the offline
optimal policy without partial hosting as OPT. The other policy called
RetroRenting (RR) was proposed in (Narayana et al., 2021a). RR works on the
same principle as that of $\alpha$-RetroRenting without using partial hosting.
We also plot the lower bound on the performance of any online policy which is
not allowed to partially host the service (LB). The parameters used for each
data point in a plot are given in the figure caption. Although our analysis
for Model 1 holds under Assumption 1 and for adversarial arrival processes, in
this section, we consider more general arrival processes with more than one
request per time-slot. We also consider the setting where request arrivals are
stochastic.

###  6.1. Synthetic Request Arrivals and Rent Costs

The first set of results use synthetic request arrival and rent cost
sequences. Unless stated otherwise, the request arrival process is i.i.d.
Bernoulli with parameter $p$. We model the time-varying rent cost sequence
using the Autoregressive moving-average (ARMA) model (Box et al., 2011),
specifically, ARMA(4,2). To choose the parameters of the model, we fit the
model to real world price data obtained from (Visser, 2017), which provides
region-wise prices of unused EC2 capacity in the Amazon Web Services (AWS)
cloud.

Figure 1. Total cost per time slot as a function of $\alpha+g(\alpha)$ for
$M=10$, $c=0.35$, $p=0.35$, and $\alpha=0.4$

Figure 2. Number of time-slots per hosting state under $\alpha$-RR as function
of $\alpha+g(\alpha)$ for $M=10$, $c=0.35$, $p=0.35$, and $\alpha=0.4$

Figure 3. Total cost per time slot as a function of fetch cost ($M$) for the
case when $\alpha+g(\alpha)<1$. Here $c=0.35$, $\alpha=0.239$,
$g(\alpha)=0.380$ and $p=0.42$

Figure 4. Total cost per time slot as a function of fetch cost ($M$) for the
case when $\alpha+g(\alpha)\geq 1$. Here $c=0.35$, $\alpha=0.5$,
$g(\alpha)=0.7$ and $p=0.42$

Figure 5. Total cost per time slot as a function of request arrival
probability ($p$) for the case when $\alpha+g(\alpha)<1$. Here $c=0.35$,
$M=10$, $\alpha=0.239$, $g(\alpha)=0.38$

Figure 6. Total cost per time slot as a function of request arrival
probability ($p$) for the case when $\alpha+g(\alpha)\geq 1$. Here $c=0.35$,
$M=10$, $\alpha=0.5$, $g(\alpha)=0.7$

Figure 7. Total cost per time slot as a function of fetch cost ($M$) for the
case when $\alpha=0.3$, $g(\alpha)=0.4$, $\alpha_{1}=0.4$,
$g(\alpha_{1})=0.3$, $\alpha_{2}=0.5$, $g(\alpha_{2})=0.15$ and $c=0.5$

Figure 8. Hosting Status over time for different policies for the case when
$\alpha=0.3$, $g(\alpha)=0.4$, $\alpha_{1}=0.4$, $g(\alpha_{1})=0.3$,
$\alpha_{2}=0.5$, $g(\alpha_{2})=0.15$ and $c=0.5$

In Figure 2, we plot the total cost per time-slot incurred by various policies
as a function of $\alpha+g(\alpha)$. We see that the performance gap between
policies that are allowed to use partial hosting
($\alpha$-RetroRenting/$\alpha$-OPT/$\alpha$-LB) and their counterparts that
are not allowed to use partial hosting (RetroRenting/OPT/LB) is significant
for $\alpha+g(\alpha)<1$ and vanishes for $\alpha+g(\alpha)\geq 1$.

In Figure 2, we illustrate the number of time-slots for which the
$\alpha$-RetroRenting uses the three possible hosting levels as a function of
$\alpha+g(\alpha)$ over a time-horizon of 10000 time-slots. As expected,
$\alpha$-RetroRenting does not use partial hosting for $\alpha+g(\alpha)\geq
1$.

In Figures 4, 4, 6, and 6, we plot the total cost per time-slot incurred by
various policies as a function of the fetch cost $M$ and request arrival
probability $p$, for two cases, namely, $\alpha+g(\alpha)<1$ and
$\alpha+g(\alpha)\geq 1$. We observe a performance gap between policies that
are allowed to use partial hosting
($\alpha$-RetroRenting/$\alpha$-OPT/$\alpha$-LB) and their counterparts that
are not allowed to use partial hosting (RetroRenting/OPT/LB) only if
$\alpha+g(\alpha)<1$.

In the next set of results presented in Figures 8 and 8, we compare the
performance of RR and $\alpha$-RetroRenting with a third policy call
multiple–RR which works on the same principle as
$\alpha$-RetroRenting/RetroRenting and is allowed to use two additional
intermediate hosting levels ($\alpha$, $\alpha_{1}$, $\alpha_{2}$). For this
set of results, we use the Gilbert-Elliot model (Liu and Zhao, 2010) for the
request arrival process. The parameters of the model are as shown in Figure
16. The request arrival process is Bernoulli(0.9) when the Markov chain is in
state 0, and Bernoulli(0.1) otherwise.

01$0.01$$0.99$$0.99$$0.01$ Figure 9. The Gilbert-Elliot model

In Figure 8, we see that the additional intermediate hosting options available
to multiple–RR brings down the cost incurred. In Figure 8, we plot the hosting
status $r_{t}$ for the three different policies as a function of time.

###  6.2. Trace-driven Simulations

Figure 10. Total cost per time slot for as a function of fetch cost ($M$) for
the case when $\alpha+g(\alpha)<1$. Here $c=0.135$, $\alpha=0.239$,
$g(\alpha)=0.38$

Figure 11. Total cost per time slot for as a function of fetch cost ($M$) for
the case when $\alpha+g(\alpha)\geq 1$. Here $c=0.135$, $\alpha=0.5$,
$g(\alpha)=0.7$

For the next set of results, For the next set of results, we use trace-data
obtained from a Google Cluster (Hellerstein, 2010) for the arrival process and
time-varying spot prices of spare server capacity in the AWS cloud as given in
(Visser, 2017) as the rent cost.

In Figures 11 and 11, we plot the total cost per time-slot incurred by various
policies as a function of the fetch cost $M$ for the case when
$\alpha+g(\alpha)<1$ and $\alpha+g(\alpha)\geq 1$ respectively. As expected,
we observe a performance gap between policies that are allowed to use partial
hosting ($\alpha$-RetroRenting/$\alpha$-OPT) and their counterparts that are
not allowed to use partial hosting (RetroRenting/OPT) only in the first case.

##  7\. Simulation Results: Model 2

In this section, we present our simulation results for Model $2$. In addition
to $\alpha$-RR, we also simulate a policy called RetroRenting (RR) which was
proposed in (Narayana et al., 2021a) and does not use partial hosting. RR
works on the same principles as that of $\alpha$-RR without using partial
hosting. Although our analysis for Model 2 holds under Assumption 1 and
stochastic arrivals, in this section, we consider more general arrival
processes with more than one request per time-slot. We also use trace-based
arrivals to compare the performance of various policies.

###  7.1. Synthetic Request Arrivals and Rent Costs

We consider two types of synthetic request arrivals, namely, Poisson and
Markovian. We model the time-varying rent cost sequence for both kinds of
arrivals using the Autoregressive moving-average (ARMA) model (Box et al.,
2011), specifically ARMA(4,2) with expected rent cost in a slot given as $c$.
To choose the parameters of the model, we fit the model using the process
described in (Lakshmi Narayana et al., 2021) to real world price data obtained
from (Visser, 2017), which provides region-wise prices of unused EC2 capacity
in the Amazon Web Services (AWS) cloud.

####  7.1.1. Poisson Request Arrivals

The first set of results are for i.i.d. Poisson request arrivals with
parameter $\lambda$ over 10,000 time slots. We use synthetic values for the
available partial storage size $\alpha$ and corresponding forwarding cost
$g(\alpha)$ for this first set of simulations, as given in the figure
captions. In addition to $\alpha$-RR and RR, we also plot the lower bound on
the performance of any deterministic online policy ($\alpha$-LB) and a lower
bound on the performance of any deterministic online policy which is not
allowed to partially host the service (LB). The expressions for these lower
bounds can be found in (Narayana et al., 2021b, Lemma 14) and Lemma 1 in the
appendix respectively.

Figure 12. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $c=4.5$, $\alpha=0.30$,
$g(\alpha)=0.50$, and $\lambda=2$

Figure 13. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $c=4.5$, $\alpha=0.30$,
$g(\alpha)=0.50$, and $\lambda=4$

Figure 14. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $c=4.5$, $\alpha=0.30$,
$g(\alpha)=0.50$, and $\lambda=8$

Figure 15. Histogram of hosting status & total cost per time slot as a
function of rent cost ($c$) for the case $M=40$, $\alpha=0.30$,
$g(\alpha)=0.50$, and $\lambda=4$

In Figures 13-15, we first plot the histogram of hosting status and then the
total cost per time slot under the two policies as a function of the fetch
cost ($M$), for different values of request arrival intensity ($\lambda$).

From the first two plots of Figure 13, we observe that RR does not host the
service at all, while $\alpha$-RR also does the same except when $M$ is very
small when it uses partial storage, albeit very rarely. Both policies lean
towards not hosting the service as the average number of arrivals per time-
slot $\lambda$ is smaller than the average rent cost $c$ here, and thus it is
cost effective to serve requests via the cloud instead of incurring rent cost.
Here, the lower bounds of online policies, namely, LB and $\alpha$-LB,
coincide with each other. Also, as $M$ increases, the performance of RR and
$\alpha$-RR approaches the lower bound. In Figure 13, we note that the average
number of requests and average rent cost is comparable, and here $\alpha$-RR
hosts $\alpha$ fraction of the service at all times while RR hosts the entire
service. We note that $\alpha$-RR outperforms RR for smaller values of $M$,
while they have similar costs for larger values of $M$. Figure 15 considers a
larger value of $\lambda$ where hosting the entire service is optimal, and
here both the policies host the entire service at all times for all values of
$M$ considered.

In Figure 15, we first plot the histogram of hosting status and then the total
cost per time slot under the two policies as a function of the rent cost
($c$), for a fixed value of request arrival intensity ($\lambda$). From the
first two plots in Figure 15, we observe that for low values of $c$,
$\alpha$-RR and RR host the entire service in all time-slots. For $3\leq c\leq
7$, $\alpha$-RR hosts $\alpha$ fraction of the service for most of the time.
For higher values of the rent cost ($c\geq 8$), $\alpha$-RR and RR both do not
host the service. We note that $\alpha$-RR outperforms RR for values of $c$
close to average arrival rate ($\lambda$) and the performance of $\alpha$-RR
and RR is comparable for low and large $c$. This is also consistent with what
we observe in Figures 13-15.

####  7.1.2. Markovian Request Arrivals

HL${P}_{H\rightarrow L}$$(1-{P}_{H\rightarrow L})$$(1-{P}_{L\rightarrow
H})$${P}_{L\rightarrow H}$ Figure 16. The Gilbert-Elliot model

For the next set of results, we use the Gilbert-Elliot model (Liu and Zhao,
2010) for the request arrival process. The parameters of the model are as
shown in Figure 16. The request arrival process is Poisson(200) when the
Markov chain is in high state (H), and Poisson(10) in the low state (L). The
values of partial storage $\alpha$ and forwarding cost $g(\alpha)$ used here
are chosen based on a curve derived from a real dataset (see Figure 24);
details are presented in Section 7.2. From Figure 24, we see when
$\alpha=0.16$, forward cost $g(0.16)$ is $0.76$ which is the minimum
$\alpha+g(\alpha)$ pair among all pairs.

In the following series of experiments, we vary the transition probabilities
for the request arrival process and compare the performance of various
policies. We also compare the performance of RR and $\alpha$-RR with two other
policies that know the statistics of the request arrivals and the expected
rent cost $c$.

The first policy, referred to as the MDP policy, formulates the hosting
problem as a Markov Decision Process. The second policy called Arrival Based
Caching (ABC) proposed in (Prakash et al., 2020) makes hosting decisions based
only on the request arrival rate in the current time-slot and the statistics
of the arrival process.

Figure 17. Histogram of hosting status & total cost per time slot as a
function of rent cost ($c$) for the case when $\alpha=0.16$, $g(\alpha)=0.76$,
$\alpha_{1}=1$, $g(\alpha_{1})=0.6$, $M=50$ and ${P}_{H\rightarrow L}=0.4$,
${P}_{L\rightarrow H}=0.4$

Figure 18. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $\alpha=0.16$,
$g(\alpha)=0.76$, $\alpha_{1}=1$, $g(\alpha_{1})=0.6$, $c=20$, and
${P}_{H\rightarrow L}=0.4$, ${P}_{L\rightarrow H}=0.4$

In the first three plots in Figure 18, we plot the histogram of the hosting
status under the three policies as a function of the rent cost $c$. Here, the
average number of requests per time slot is $105$ and transition probability
${P}_{H\rightarrow L}$ is same as ${P}_{L\rightarrow H}$ which is $0.4$. We
observe that for low values of rent cost ($c\leq 20$), MDP hosts the entire
service in all time-slots. For higher values of rent cost $20<c\leq 150$, MDP
hosts $\alpha$ fraction of the service in all time-slots. For $160\leq c\leq
170$, MDP varies between hosting $\alpha$ fraction of the service and not
hosting the service. For even higher values of rent cost ($c>170$), MDP does
not host the service. These trends are explained by the fact that as the
expected rent cost $c$ increases, the cost incurred by serving requests via
the cloud becomes lower than the cost of renting edge resources to host the
service at the edge. The hosting status under $\alpha$-RR has a similar trend;
however, the range of values of rent cost over which $\alpha$-RR hosts at
least a part of the service is larger than MDP. RR hosts the entire service
for low values of rent cost and does not host the service when rent cost $c$
is above a threshold, $c=80$. For intermediate values of rent cost, it varies
between hosting the entire service and not hosting the service. As a
consequence of the hosting status under the three policies, the total cost
incurred under all three policies is very close for very low and very high
values of rent cost. For rent costs, $c<180$, $\alpha$-RR outperforms RR and
RR outperforms $\alpha$-RR for rent cost $c$ in the range $[180,310]$.

Similarly, in the first three plots in Figure 18, we plot the histogram of
hosting status under the three policies as a function of the fetch cost $M$.
We observe that for most values of fetch cost $M$, MDP hosts $\alpha$ fraction
of the service in all time-slots. Under $\alpha$-RR the hosting status varies
between $\alpha$ fraction of the service and the entire service. We observe
that $\alpha$-RR outperforms RR for low values of $M$ and their performance
converges as $M$ increases.

Figure 19. Histogram of hosting status & total cost per time slot as a
function of rent cost ($c$) for the case when $\alpha=0.16$, $g(\alpha)=0.76$,
$\alpha_{1}=1$, $g(\alpha_{1})=0.6$, $M=50$ and ${P}_{H\rightarrow L}=0.2$,
${P}_{L\rightarrow H}=0.1$

Figure 20. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $\alpha=0.16$,
$g(\alpha)=0.76$, $\alpha_{1}=1$, $g(\alpha_{1})=0.6$, $c=20$, and
${P}_{H\rightarrow L}=0.2$, ${P}_{L\rightarrow H}=0.1$

Unlike Figures 18 and 18, we next consider lower values of transition
probabilities for the request arrival process, and again compare the
performance of the three policies as a function of the rent cost $c$. For
Figures 20 and 20, the average number of requests per time slot is $73.33$ and
transition probability ${P}_{H\rightarrow L}$ is $0.2$ whereas
${P}_{L\rightarrow H}$ is $0.1$. From Figure 20, we observe that $\alpha$-RR
outperforms RR for most values of $c$. For very high values of $c$, the total
cost incurred under all policies is close. We thus note that even though that
MDP and ABC know the statistics of the arrival process while $\alpha$-RR does
not have that information, the performance of $\alpha$-RR is comparable with
MDP and ABC. We note a similar trend in Figure 20, with RR performing poorly
for all values of $M$ considered.

Figure 21. Histogram of hosting status & total cost per time slot as a
function of rent cost ($c$) for the case when $\alpha=0.16$, $g(\alpha)=0.76$,
$\alpha_{1}=1$, $g(\alpha_{1})=0.6$, $M=50$ and ${P}_{H\rightarrow L}=0.8$,
${P}_{L\rightarrow H}=0.1$

Figure 22. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $\alpha=0.16$,
$g(\alpha)=0.76$, $\alpha_{1}=1$, $g(\alpha_{1})=0.6$, $c=20$, and
${P}_{H\rightarrow L}=0.8$, ${P}_{L\rightarrow H}=0.1$

In the last set of Figures 22 and 22, we consider a request arrival process
with very asymmetric transition probabilities. The average number of requests
per time slot is $31.11$ and transition probability ${P}_{H\rightarrow L}$ is
$0.8$ whereas ${P}_{L\rightarrow H}$ is $0.1$. Here, the underlying Markov
chain spends most of its time in the low state. Similar to previous
experiments, from Figure 22, we conclude that for low values of rent cost $c$,
$\alpha$-RR outperforms RR. For intermediate values of $c$, RR performs better
than $\alpha$-RR and for high values of $c$, the total cost incurred under all
policies is close. For the same request arrival process, we plot the total
cost vs $M$ in Figure 22, and find that $\alpha$-RR outperforms RR for all
values of $M$ considered.

###  7.2. Simulations on GPS Trajectory Dataset

In the next set of simulations, we use a real dataset to construct the
forwarding cost function $g(\cdot)$ for a shortest path query system. In
particular, we use a GPS trajectory dataset (Zheng et al., 2008)(Zheng et al.,
2009)(Zheng et al., 2010) collected as a part of the Geolife Project by
Microsoft Research Asia. This dataset contains 17,621 cab trajectories from
Beijing, China, compiled over five years from 2007-12. Using this data, we
model a service which when queried with a source-destination pair, returns the
shortest path corresponding to that input. As before the goal is to host this
service in the most cost-efficient way. Next, we describe how the edge cache
size is measured and our algorithm to decide what goes in the cache.

The complete library at the server is considered to be of size $N\times P$
where $N$ is the total number of queries and $P$ is the total number of nodes
in the shortest path corresponding to all $N$ queries. We host a fraction of
this dataset in our locally available cache to assist with answering future
queries. The cache size is measured by the total number of nodes stored across
all the cached trajectories.

We extract each trajectory’s start and end locations as the source and
destination nodes of the shortest path query, respectively. So each query is a
request to the system which returns the shortest distance from source to
destination. To find the trajectory between each source-destination pair, we
used Road Network data(Thomsen et al., 2012) of Beijing city. Using Dijkstra’s
shortest path algorithm(Borodin et al., 1992), we generated a sequence of
nodes corresponding to the shortest path for each query.

We use the query data from the first three years of the GPS trajectory dataset
(Zheng et al., 2008)(Zheng et al., 2009)(Zheng et al., 2010) to decide which
paths should be hosted at the edge, given a certain cache size. We use a
greedy strategy, namely the fractional knapsack(Black et al., 1998) algorithm,
and to enable this we sort all the paths according to their ‘normalized hit
rate’. For any path hosted at the edge, we assume that it will result in a
‘hit’ whenever a query has both its source and destination nodes on the path.
Then, the normalized hit rate for a path is defined as the ratio of the number
of hits to the total count of nodes forming that path. A path with high
normalized hit rate can serve more queries per unit used cache size, if hosted
at the edge. Finally, given any cache size, the fractional knapsack algorithm
chooses to greedily host paths with the highest normalized hit rates.

Next, for any given cache size and the corresponding subset of paths hosted at
the edge as describe above, we use the query data of the fourth year from the
GPS trajectory dataset to estimate the fraction of queries that can be
answered at the edge. Figure 24 plots the fraction of test queries served by
the edge cache vs the available cache size. Here, we represent the cache size
as a fraction, defined as the ratio of the number of nodes corresponding to
the cached paths and the total number of nodes involved in all paths that
appear in the first three years of the GPS trajectory dataset. For any
fraction $\alpha$, the value on the curve111Note that the fraction of queries
answered is less than $1$ even when the cache size is large enough to store
all the paths. This is because the cache content is decided based on queries
from the first three years, whereas the fraction of queries answered is
decided based on the data from the fourth year wherein new paths were queried
whose source-destination pairs did not lie on any of the previously seen
paths. is used as a proxy for $1-g(\alpha)$. More details about the above
procedure are available in (Gps, [n.d.]).

Figure 23. Percentage of queries answered by the fraction of cache stored at
the edge

Figure 24. Total cost of all requests as a function of cache stored when
$c=0.4$

We now compare the performance of RR and $\alpha$-RR policies on the queries
from the fourth year of the GPS trajectory dataset. In Figure 24, we plot the
total cost of all requests as a function of cache capacity $\alpha$ with
$c=0.4$. We observe that the cost for $\alpha$-RR is minimum when $\alpha$ is
0.5. We use this cache size and rent cost $c=0.4$ in Figure 25, where we plot
the total cost per time slot as a function of fetch cost ($M$). We observe
that $\alpha$-RR performs much better than RR, thus highlighting the potential
cost benefits that can be derived by efficiently utilizing partial storage.
Moreover, it even outperforms offline optimal policy without partial storage
(OPT).

Figure 25. Histogram of hosting status & total cost per time slot as a
function of fetch cost ($M$) for the case when $\alpha=0.5$ and $c=0.4$

##  8\. Conclusions

We consider the algorithmic challenge of dynamic service hosting on third-
party edge computing platforms in the setting where the service can also be
partially hosted. We show that the benefits of partial hosting are limited if
reduction in latency cost at the intermediate hosting level is not more than
fraction of service hosted. We propose an online policy named $\alpha-$RR and
provide performance guarantees for both adversarial and stochastic request
arrival models. In addition, via simulations for synthetic and trace-based
arrivals, we show that $\alpha-$RR performs well for a wide array of request
arrival processes and rent cost sequences. The benefits of using more than
three levels of service hosting is an open problem.

## References

  * (1)
  * Gps ([n.d.]) [n.d.].  https://github.com/mohit-iitb/mapDataCaching
  * Ascigil et al. (2021) Onur Ascigil, Argyrios Tasiopoulos, Truong Khoa Phan, Vasilis Sourlas, Ioannis Psaras, and George Pavlou. 2021.  Resource Provisioning and Allocation in Function-as-a-Service Edge-Clouds.  _IEEE Transactions on Services Computing_ (2021), 1–1.  https://doi.org/10.1109/TSC.2021.3052139
  * Belady (1966) Laszlo A. Belady. 1966\.  A study of replacement algorithms for a virtual-storage computer.  _IBM Systems journal_ 5, 2 (1966), 78–101.
  * Bi et al. (2020) S. Bi, L. Huang, and Y. A. Zhang. 2020.  Joint Optimization of Service Caching Placement and Computation Offloading in Mobile Edge Computing Systems.  _IEEE Transactions on Wireless Communications_ 19, 7 (2020), 4947–4963.  https://doi.org/10.1109/TWC.2020.2988386
  * Black et al. (1998) Paul E Black et al. 1998\.  Dictionary of Algorithms and data structures.  (1998).
  * Borodin et al. (1992) Allan Borodin, Nathan Linial, and Michael E. Saks. 1992\.  An Optimal On-Line Algorithm for Metrical Task System.  _J. ACM_ 39, 4 (Oct. 1992), 745–763.  https://doi.org/10.1145/146585.146588
  * Borst et al. (2010) Sem Borst, Varun Gupta, and Anwar Walid. 2010.  Distributed caching algorithms for content distribution networks. In _2010 Proceedings IEEE INFOCOM_. IEEE, 1–9.
  * Box et al. (2011) George EP Box, Gwilym M Jenkins, and Gregory C Reinsel. 2011\.  _Time series analysis: forecasting and control_. Vol. 734.  John Wiley & Sons.
  * Breslau et al. (1999) Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. 1999.  Web caching and Zipf-like distributions: Evidence and implications. In _IEEE INFOCOM’99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No. 99CH36320)_ , Vol. 1. IEEE, 126–134.
  * Chen and Xu (2017) Lixing Chen and Jie Xu. 2017.  Collaborative service caching for edge computing in dense small cell networks.  _arXiv preprint arXiv:1709.08662_ (2017).
  * Chen and Xu (2019) Lixing Chen and Jie Xu. 2019.  Budget-constrained Edge Service Provisioning with Demand Estimation via Bandit Learning.  _arXiv preprint arXiv:1903.09080_ (2019).
  * He et al. ([n.d.]) Wen He, Dazhi He, Yihang Huang, Yizhe Zhang, Yin Xu, Guan Yun-feng, and Wenjun Zhang. [n.d.].  Bandit Learning-based Service Placement and Resource Allocation for Mobile Edge Computing. In _2020 IEEE 31st Annual International Symposium on Personal, Indoor and Mobile Radio Communications_. IEEE, 1–6.
  * Hefeeda and Saleh (2008) Mohamed Hefeeda and Osama Saleh. 2008.  Traffic modeling and proportional partial caching for peer-to-peer systems.  _IEEE/ACM Transactions on Networking_ 16, 6 (2008), 1447–1460.
  * Hellerstein (2010) Joseph L. Hellerstein. 2010\.  Google Cluster Data: Google AI blog.
  * Hoeffding (1994) Wassily Hoeffding. 1994\.  Probability inequalities for sums of bounded random variables.  In _The Collected Works of Wassily Hoeffding_. Springer, 409–426.
  * Lakshmi Narayana et al. (2021) V S Ch Lakshmi Narayana, Mohit Agarwala, Nikhil Karamchandani, and Sharayu Moharir. 2021.  Online Partial Service Hosting at the Edge.  _arXiv e-prints_ , Article arXiv:2103.00555 (Feb. 2021), arXiv:2103.00555 pages.  arXiv:2103.00555 [cs.NI]
  * Lakshmi Narayana et al. (2020) V. S. Ch. Lakshmi Narayana, S. Moharir, and N. Karamchandani. 2020\.  RetroRenting: An Online Policy for Service Caching at the Edge. In _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. 1–8.
  * Liu and Zhao (2010) Keqin Liu and Qing Zhao. 2010.  Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access.  _IEEE Transactions on Information Theory_ 56, 11 (2010), 5547–5567.
  * Lu et al. (2012) Lian Lu, Jinlong Tu, Chi-Kin Chau, Minghua Chen, and Xiaojun Lin. 2012.  Online Energy Generation Scheduling for Microgrids with Intermittent Energy Sources and Co-Generation.  arXiv:1211.4473
  * Mach and Becvar (2017) Pavel Mach and Zdenek Becvar. 2017.  Mobile edge computing: A survey on architecture and computation offloading.  _IEEE Communications Surveys & Tutorials_ 19, 3 (2017), 1628–1656.
  * Mao et al. (2017) Yuyi Mao, Changsheng You, Jun Zhang, Kaibin Huang, and Khaled B Letaief. 2017.  A survey on mobile edge computing: The communication perspective.  _IEEE Communications Surveys & Tutorials_ 19, 4 (2017), 2322–2358.
  * Narayana et al. (2021a) VS Ch Lakshmi Narayana, Sharayu Moharir, and Nikhil Karamchandani. 2021a.  On Renting Edge Resources for Service Hosting.  _ACM Transactions on Modeling and Performance Evaluation of Computing Systems_ 6, 2 (2021), 1–30.
  * Narayana et al. (2021b) V.S. Ch Lakshmi Narayana, Sharayu Moharir, and Nikhil Karamchandani. 2021b.  On Renting Edge Resources for Service Hosting.  6, 2 (2021).  https://doi.org/10.1145/3478433
  * Pasteris et al. (2019) Stephen Pasteris, Shiqiang Wang, Mark Herbster, and Ting He. 2019\.  Service placement with provable guarantees in heterogeneous edge computing systems. In _IEEE INFOCOM 2019-IEEE Conference on Computer Communications_. IEEE, 514–522.
  * Prakash et al. (2020) R. S. Prakash, N. Karamchandani, V. Kavitha, and S. Moharir. 2020.  Partial Service Caching at the Edge. In _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. 1–8.
  * Prakash et al. (2020) Rudrabhotla Sri Prakash, Nikhil Karamchandani, Veeraruna Kavitha, and Sharayu Moharir. 2020.  Partial Service Caching at the Edge. In _2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)_. 1–8.
  * Puliafito et al. (2019) Carlo Puliafito, Enzo Mingozzi, Francesco Longo, Antonio Puliafito, and Omer Rana. 2019\.  Fog Computing for the Internet of Things: A Survey.  _ACM Trans. Internet Technol._ 19, 2, Article 18 (April 2019), 41 pages.  https://doi.org/10.1145/3301443
  * Sleator and Tarjan (1985) Daniel D Sleator and Robert E Tarjan. 1985.  Amortized efficiency of list update and paging rules.  _Commun. ACM_ 28, 2 (1985), 202–208.
  * Tan and Massoulié (2012) Bo Tan and Laurent Massoulié. 2012.  Optimal content placement for peer-to-peer video-on-demand systems.  _IEEE/ACM transactions on networking_ 21, 2 (2012), 566–579.
  * Tan et al. (2021) Haisheng Tan, Shaofeng H-C Jiang, Zhenhua Han, and Mingxia Li. 2021\.  Asymptotically Optimal Online Caching on Multiple Caches With Relaying and Bypassing.  _IEEE/ACM Transactions on Networking_ (2021).
  * Thomsen et al. (2012) Jeppe Rishede Thomsen, Man Lung Yiu, and Christian S. Jensen. 2012\.  Effective Caching of Shortest Paths for Location-Based Services. In _Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data_ (Scottsdale, Arizona, USA) _(SIGMOD ’12)_. Association for Computing Machinery, New York, NY, USA, 313–324.  https://doi.org/10.1145/2213836.2213872
  * Tran et al. (2019) Tuyen X Tran, Kevin Chan, and Dario Pompili. 2019.  COSTA: Cost-aware Service Caching and Task Offloading Assignment in Mobile-Edge Computing. In _2019 16th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)_. IEEE, 1–9.
  * Visser (2017) Benji Visser. 2017\.  https://www.kaggle.com/noqcks/aws-spot-pricing-market
  * Wajc (2017) David Wajc. 2017\.  Negative association: definition, properties, and applications.  _Manuscript, available from https://goo. gl/j2ekqM_ (2017).
  * Wang et al. (2015) Shiqiang Wang, Rahul Urgaonkar, Murtaza Zafer, Ting He, Kevin Chan, and Kin K Leung. 2015\.  Dynamic service migration in mobile edge-clouds. In _2015 IFIP Networking Conference (IFIP Networking)_. IEEE, 1–9.
  * Wolman et al. (1999) Alec Wolman, Geoffrey M. Voelker, Nitin Sharma, Neal Cardwell, Anna Karlin, and Henry M. Levy. 1999\.  On the Scale and Performance of Cooperative Web Proxy Caching. In _Proc. ACM SOSP_. 16–31.
  * Xia et al. (2020) Xiaoyu Xia, Feifei Chen, Qiang He, John Grundy, Mohamed Abdelrazek, and Hai Jin. 2020\.  Online collaborative data caching in edge computing.  _IEEE Transactions on Parallel and Distributed Systems_ 32, 2 (2020), 281–294.
  * Xiong et al. ([n.d.]) Guojun Xiong, Rahul Singh, and Jian Li. [n.d.].  Learning Augmented Index Policy for Optimal Service Placement at the Network Edge.  _arXiv preprint arXiv:2101.03641_ ([n. d.]).
  * Xu et al. (2018) Jie Xu, Lixing Chen, and Pan Zhou. 2018.  Joint service caching and task offloading for mobile edge computing in dense networks. In _IEEE INFOCOM 2018-IEEE Conference on Computer Communications_. IEEE, 207–215.
  * Xu et al. (2020) Zichuan Xu, Lizhen Zhou, Sid Chi-Kin Chau, Weifa Liang, Qiufen Xia, and Pan Zhou. 2020\.  Collaborate or separate? Distributed service caching in mobile edge clouds. In _IEEE INFOCOM 2020-IEEE Conference on Computer Communications_. IEEE, 2066–2075.
  * Yan et al. (2021) Jia Yan, Suzhi Bi, Lingjie Duan, and Ying-Jun Angela Zhang. 2021.  Pricing-Driven Service Caching and Task Offloading in Mobile Edge Computing.  _IEEE Transactions on Wireless Communications_ 20, 7 (2021), 4495–4512.  https://doi.org/10.1109/TWC.2021.3059692
  * Yang et al. (2015) Lei Yang, Jiannong Cao, Guanqing Liang, and Xu Han. 2015\.  Cost aware service placement and load dispatching in mobile cloud systems.  _IEEE Trans. Comput._ 65, 5 (2015), 1440–1452.
  * Zhao et al. (2018) Tao Zhao, I-Hong Hou, Shiqiang Wang, and Kevin Chan. 2018\.  ReD/LeD: An asymptotically optimal and scalable online algorithm for service caching at the edge.  _IEEE Journal on Selected Areas in Communications_ 36, 8 (2018), 1857–1870.
  * Zheng et al. (2008) Yu Zheng, Quannan Li, Yukun Chen, Xing Xie, and Wei-Ying Ma. 2008.  Understanding mobility based on GPS data. In _Proceedings of the 10th international conference on Ubiquitous computing_. 312–321.
  * Zheng et al. (2010) Yu Zheng, Xing Xie, Wei-Ying Ma, et al. 2010\.  Geolife: A collaborative social networking service among user, location and trajectory.  _IEEE Data Eng. Bull._ 33, 2 (2010), 32–39.
  * Zheng et al. (2009) Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. 2009\.  Mining interesting locations and travel sequences from GPS trajectories. In _Proceedings of the 18th international conference on World wide web_. 791–800.

##  9\. Appendix A

In this section, we discuss the proofs of the results presented in Section 4.
Note that we use Model 1 to prove results in this section.

###  9.1. Proof of Theorem 1

We use the following lemmas about the offline optimal policy $\alpha$-OPT to
prove our results.

The first lemma characterizes sufficient conditions on the various costs and
arrival/rent costs processes over a time interval in which the hosting status
goes from $a$ to $a+b$ and then returns to $a$ for $(a,b)=(0,\alpha)$,
$(a,b)=(0,1)$, and $(a,b)=(\alpha,1-\alpha)$.

###### Lemma 0.

Let $r^{*}_{t}$ denote the hosting state under $\alpha$-OPT policy in time-
slot $t$. If $r_{n-1}^{*}=a$, $r_{t}^{*}=a+b$ for $n\leq t\leq m$ and
$r_{m+1}^{*}=a$, then for $(a,b)=(0,\alpha)$, $(a,b)=(0,1)$, and
$(a,b)=(\alpha,1-\alpha)$,

$(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}\geq
bM+b\displaystyle\sum_{l=n}^{m}c_{l}.$

###### Proof.

If $r_{n-1}^{*}=a$, $r_{t}^{*}=a+b$ for $n\leq t\leq m$ and $r_{m+1}^{*}=a$,
then the cost incurred by $\alpha$-OPT in $n\leq t\leq m$ is
$C^{\alpha-\text{OPT}}=bM+(a+b)\displaystyle\sum_{l=n}^{m}c_{l}+g(a+b)\displaystyle\sum_{l=n}^{m}x_{l}.$
We prove the result by contradiction. Let us assume that
$(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}<bM+b\displaystyle\sum_{l=n}^{m}c_{l}.$

We construct another policy $\eta$ which behaves same as $\alpha$-OPT except
that $r^{\eta}_{t}=a$ for $n\leq t\leq m.$ The total cost incurred by $\eta$
in $n\leq t\leq m$ is
$C^{\eta}=a\displaystyle\sum_{l=n}^{m}c_{l}+g(a)\displaystyle\sum_{l=n}^{m}x_{l}.$
It follows that
$C^{\eta}-C^{\alpha-\text{OPT}}=(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}-bM-b\displaystyle\sum_{l=n}^{m}c_{l},$
which is negative by our assumption. This contradicts the definition of the
$\alpha$-OPT policy, thus proving the result. ∎

The next lemma characterizes a sufficient condition on the various costs and
arrival/rent costs processes over an interval of time which ensures that the
hosting status under $\alpha$-OPT does not remain static in that interval.

###### Lemma 0.

Let $r^{*}_{t}$ denote the hosting state under the offline optimal policy in
time-slot $t$. If $r_{n-1}^{*}=a$, and
$(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}\geq
bM+b\displaystyle\sum_{l=n}^{m}c_{l},$ then for $(a,b)=(0,\alpha)$,
$(a,b)=(0,1)$ or $(a,b)=(\alpha,1-\alpha)$, $r^{*}_{\tau}\neq a$ for at least
one value of $\tau$ such that $n\leq\tau\leq m.$

###### Proof.

We prove Lemma 2 by contradiction. Let us assume that $r^{*}_{\tau}=a$ during
$n\leq\tau\leq m$. So the cost incurred by $\alpha$-OPT in $n\leq t\leq m$ is
$C^{\alpha-\text{OPT}}=a\displaystyle\sum_{l=n}^{m}c_{l}+g(a)\displaystyle\sum_{l=n}^{m}x_{l}.$

We construct another policy $\eta$ which behaves same as $\alpha$-OPT except
that $r^{\eta}_{t}=a+b$ for $n\leq t\leq m.$. The total cost incurred by
$\eta$ in $n\leq t\leq m$ is
$C^{\eta}=Mb+(a+b)\displaystyle\sum_{l=n}^{m}c_{l}+g(a+b)\displaystyle\sum_{l=n}^{m}x_{l}.$
It follows that
$C^{\eta}-C^{\alpha-\text{OPT}}=bM+b\displaystyle\sum_{l=n}^{m}c_{l}-(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l},$
which is negative. Hence there exists at least one policy $\eta$ which
performs better than $\alpha$-OPT. This contradicts the definition of the
$\alpha$-OPT policy, thus proving the result. ∎

The following lemma characterizes sufficient conditions under which
$\alpha$-OPT never fetches specific parts of the service.

###### Lemma 0.

If $bc_{\text{min}}+g(b)\geq 1$ for $b\in\\{\alpha,1\\}$ then $\alpha$-OPT
does not fetch $b$ fraction of the service. Similarly, if $\alpha
c_{\text{min}}+g(\alpha)\leq c_{\text{min}}$ then $\alpha$-OPT does not fetch
$(1-\alpha)$ fraction of the service.

###### Proof.

We prove this by contradiction. When $bc_{\text{min}}+g(b)\geq 1$, assume that
$\alpha$-OPT fetches $b$ fraction of service for $b\in\\{\alpha,1\\}$ at the
end of time-slot $n$ and hosts till the time-slot $m$. The cost under
$\alpha$-OPT during the time $(n,m]$ is
$C^{\alpha-\text{OPT}}=bM+g(b)\displaystyle\sum_{l=n+1}^{m}x_{l}+b\displaystyle\sum_{l=n+1}^{m}c_{l}$.

We construct another policy $\eta$ which behaves same as $\alpha$-OPT except
that during $(n,m]$, the policy $\eta$ forwards all incoming requests. The
cost under $\eta$ during the time $(n,m]$ is
$C^{\eta}=\displaystyle\sum_{l=n+1}^{m}x_{l}$. The difference
$C^{\eta}-C^{\alpha-\text{OPT}}$ is negative since $bc_{\text{min}}+g(b)\geq
1$. Which is a contradiction.

Now consider the other case $\alpha c_{\text{min}}+g(\alpha)\leq
c_{\text{min}}$. Let $r^{*}_{t}$ denote the hosting state under $\alpha$-OPT
in a time-slot $t$. If $r^{*}_{n}=\alpha$, assume that $\alpha$-OPT fetches
remaining $(1-\alpha)$ fraction of service for at the end of time-slot $n$ and
hosts till the time-slot $m$. The cost under $\alpha$-OPT during the time
$(n,m]$ is
$C^{\alpha-\text{OPT}}=(1-\alpha)M+\displaystyle\sum_{l=n+1}^{m}c_{l}$.

We construct another policy $\eta$ which behaves same as $\alpha$-OPT except
that during $(n,m]$, the policy $\eta$ hosts only $\alpha$ fractions of the
service. The cost under $\eta$ during the time $(n,m]$ is
$C^{\eta}=g(\alpha)\displaystyle\sum_{l=n+1}^{m}x_{l}+\alpha\displaystyle\sum_{l=n+1}^{m}c_{l}$.
The difference $C^{\eta}-C^{\alpha-\text{OPT}}$ is negative since $\alpha
c_{\text{min}}+g(\alpha)\leq c_{\text{min}}$. Which is a contradiction. ∎

The next lemma characterizes a lower limit on the number of time-slots for
which under $\alpha$-OPT, the hosting status remains unchanged following a
service fetch.

###### Lemma 0.

For $(a,b)=(0,\alpha)$ or $(a,b)=(0,1)$ or $(a,b)=(\alpha,1-\alpha)$ and
$(a+b)c_{\text{min}}+g(a+b)<1$, once $\alpha$-OPT fetches
$b\in\\{1,\alpha,1-\alpha\\}$ fraction of the service, the hosting status
remains unchanged for the next $\frac{bM}{g(a)-g(a+b)-bc_{\text{min}}}$ time-
slots.

###### Proof.

Suppose $\alpha$-OPT fetches $b$ fraction of the service at the end of the
$(n-1)^{\text{th}}$ time-slot and evicts it at the end of time-slot $m>n$.
From Lemma 1, $(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}\geq
bM+b\displaystyle\sum_{l=n}^{m}c_{l}.$ Since
$\displaystyle\sum_{l=n}^{m}x_{l}\leq(m-n+1)$ and
$\displaystyle\sum_{l=n}^{m}c_{l}\geq(m-n+1)c_{\text{min}}$ ,
$(g(a)-g(a+b))(m-n+1)\geq Mb+b(m-n+1)c_{\text{min}}$, i.e,
$(m-n+1)\geq\frac{bM}{g(a)-g(a+b)-bc_{\text{min}}}.$ This proves the result. ∎

###### Proof of Theorem 1.

We first focus on the offline optimal policy and prove the result by
contradiction. We start with $r^{*}_{n-1}=0$ and $r^{*}_{n}=\alpha$. Hence
from Lemma 1, for some $m>n$

(4)
$\displaystyle(1-g(\alpha))\displaystyle\sum_{l=n}^{m}x_{l}\geq\alpha\displaystyle\sum_{l=n}^{m}c_{l}+\alpha
M.$

Since $\alpha>1-g(\alpha)$, from (4) we have
$\displaystyle\sum_{l=n}^{m}x_{l}\geq\displaystyle\sum_{l=n}^{m}c_{l}+M$. We
construct a policy $\eta$ which behaves same as $\alpha$-OPT except that
$r^{\eta}_{n}=1$ for $n\leq t\leq m.$ The total cost incurred by $\eta$ in
$n\leq t\leq m$ is $C^{\eta}(n,m)=M+\displaystyle\sum_{l=n}^{m}c_{l}.$ Where
as the total cost incurred by $\alpha$-OPT in $n\leq t\leq m$ is
$C^{\text{$\alpha$-OPT}}(n,m)=\alpha\displaystyle\sum_{l=n}^{m}c_{l}+\alpha
M+g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}$. It follows that

$\displaystyle C^{\eta}(n,m)-C^{\text{$\alpha$-OPT}}(n,m)$
$\displaystyle=(1-\alpha)M+(1-\alpha)\displaystyle\sum_{l=n}^{m}c_{l}-g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}$
$\displaystyle<g(\alpha)(\displaystyle\sum_{l=n}^{m}c_{l}+M-\displaystyle\sum_{l=n}^{m}x_{l})<0.$

This shows that fetching and hosting $\alpha$ fraction of service is costlier
compared to fetching and renting the entire service during the period $[n,m]$.

Along similar lines we prove that the other case
$r^{*}_{n-1}=1,r^{*}_{t}=\alpha$ for $n\leq t\leq m$ is not possible under
$\alpha$-OPT when $\alpha+g(\alpha)\geq 1.$

We now focus on the $\alpha$-RR policy and prove the result by contradiction.
Let $r^{\alpha\text{-RR}}_{\tilde{t}}=0$ and $r^{\alpha\text{-RR}}_{t}=\alpha$
for some $t>\tilde{t}$. Hence from Algorithm 1, for some
$\tau_{\alpha}\in(\tilde{t},t)$

(5)
$(1-g(\alpha))\displaystyle\sum_{l=\tau_{\alpha}}^{t}x_{l}\geq\alpha\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+\alpha
M.$

Since $\alpha\geq 1-g(\alpha)$, from (5) we have
$\displaystyle\sum_{l=\tau_{\alpha}}^{t}x_{l}\geq\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+M$.
In addition,

$\displaystyle\alpha M$
$\displaystyle+\alpha\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+g(\alpha)\displaystyle\sum_{l=\tau_{\alpha}}^{t}x_{l}$
$\displaystyle\geq\alpha
M+\alpha\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+(1-\alpha)\displaystyle\sum_{l=\tau_{\alpha}}^{t}x_{l}$
$\displaystyle\geq\alpha
M+\alpha\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+(1-\alpha)\left(\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+M\right)$
$\displaystyle\geq\displaystyle\sum_{l=\tau_{\alpha}}^{t}c_{l}+M.$

The last inequality implies that the cost of fetching and hosting $\alpha$
fraction of service incurs more cost than that of fetching and renting the
entire service during the period $(\tau_{\alpha},t]$. Therefore
$r^{\alpha\text{-RR}}_{t}\neq\alpha$.

Along similar lines we prove that the other case,
$r^{\alpha\text{-RR}}_{\tilde{t}}=1,r^{\alpha\text{-RR}}_{t}=\alpha$ for any
$t>\tilde{t}$, is not possible $\alpha\text{-RR}$ when $\alpha+g(\alpha)\geq
1.$

∎

###  9.2. Proof of Theorem 2

We first focus on the first part of the theorem.

###### Proof of Theorem 2(a).

We first focus on the case when $c_{\text{min}}\geq 1$ and $r_{t}=0$ for some
$t$ under $\alpha$-RR. In this case,

$\text{totalCost}(R_{0}^{(\tau_{0})},I_{t})<\text{totalCost}(R_{1}^{(\tau_{1})},I_{t})\
\forall\tau_{1}\in(t_{\text{recent}},t).$

Therefore, under $\alpha$-RR, $r_{t+1}\neq 1$.

When $\alpha c_{\text{min}}+g(\alpha)\geq 1$ and $r_{t}=0$ for some $t$ under
$\alpha$-RR,

$\text{totalCost}(R_{0}^{(\tau_{0})},I_{t})<\text{totalCost}(R_{\alpha}^{(\tau_{\alpha})},I_{t})\
\forall\tau_{\alpha}\in(t_{\text{recent}},t).$

Therefore, under $\alpha$-RR, $r_{t+1}\neq\alpha$.

Since $r_{0}=0$ under $\alpha$-RR, it follows that, $\alpha$-RR does not fetch
the service if $\alpha c_{\text{min}}+g(\alpha)\geq 1$ and $c_{\text{min}}\geq
1$. Also from Lemma 3, it follows that the $\alpha$-OPT does not fetch any
fraction of the service when $\alpha c_{\text{min}}+g(\alpha)\geq 1$ and
$c_{\text{min}}\geq 1$. Thus the performance of $\alpha$-RR is same as that of
$\alpha$-OPT when $\alpha c_{\text{min}}+g(\alpha)\geq 1$ and
$c_{\text{min}}\geq 1$.

∎

We now focus on the second part of Theorem 2. We use the following lemmas
about $\alpha$-RR to prove our results.

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r^{\alpha\text{-RR}}_{t}=a$ and
$r^{\alpha\text{-RR}}_{t+1}=b$, then for $(a,b)=(0,\alpha)$, $(a,b)=(0,1)$ or
$(a,b)=(\alpha,1-\alpha)$, by the definition of the $\alpha\text{-RR}$ policy,
$\exists\tau_{a+b}<n$ such that

$\text{totalCost}(R_{a}^{(\tau_{a})},I_{t})>\text{totalCost}(R_{a+b}^{(\tau_{a+b})},I_{t})\
\forall\tau_{a}\in(t_{\text{recent}},t].$

Then,

$(t-\tau_{a+b})\geq\frac{bM}{g(a)-g(a+b)-bc_{\text{min}}}.$

###### Proof.

Since $\displaystyle\sum_{l=n-\tau+1}^{n}x_{l}\leq\tau,$ and
$\displaystyle\sum_{l=n-\tau+1}^{n}c_{l}\geq\tau c_{\text{min}},$ the results
follow. ∎

The next lemma characterizes sufficient conditions on the various costs and
arrival/rent costs processes over a time interval in which the hosting status
goes from $a$ to $a+b$ and then returns to $a$ for $(a,b)=(0,\alpha)$,
$(a,b)=(0,1)$, and $(a,b)=(\alpha,1-\alpha)$.

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r^{\alpha\text{-RR}}_{n-1}=a+b$,
$r^{\alpha\text{-RR}}_{t}=a$ for $n\leq t\leq m$ and
$r^{\alpha\text{-RR}}_{m+1}=a+b$ then for $(a,b)=(0,\alpha)$, $(a,b)=(0,1)$ or
$(a,b)=(\alpha,1-\alpha)$,

$(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}<b\displaystyle\sum_{l=n}^{m-1}c_{l}+Mb+(g(a)-g(a+b)).$

###### Proof.

Given $r^{\alpha\text{-RR}}_{m}=a$ and $r^{\alpha\text{-RR}}_{m+1}=a+b.$ So
from Algorithm 1, we have that
$\text{totalCost}(R_{a}^{n},I_{m})\geq\text{totalCost}(R_{a+b}^{(\tau_{a+b})},I_{m})\
\text{ for }\tau_{a+b}\in[n,m]$ and hence
$\text{totalCost}(R_{a}^{n},I_{m-1})<\text{totalCost}(R_{a+b}^{n},I_{m-1})$.
Which implies
$g(a)\displaystyle\sum_{l=n}^{m-1}x_{l}+a\displaystyle\sum_{l=n}^{m-1}c_{l}<g(a+b)\displaystyle\sum_{l=n}^{m-1}x_{l}+(a+b)\displaystyle\sum_{l=n}^{m-1}c_{l}+bM$.
By definition,

$\displaystyle\displaystyle\sum_{l=n}^{m}x_{l}=\left(\displaystyle\sum_{l=n}^{m-1}x_{l}\right)+x_{m}$
$\displaystyle(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m-1}x_{l}<b(\displaystyle\sum_{l=n}^{m}c_{l}+M)+(g(a)-g(a+b))$
$\displaystyle<b\displaystyle\sum_{l=n}^{m-1}c_{l}+Mb+(g(a)-g(a+b)).$

Thus proving the result. ∎

The next lemma characterizes sufficient conditions on the various costs and
arrival/rent costs processes over a time interval in which the hosting status
goes from $a+b$ to $a$ and then returns to $a+b$ for $(a,b)=(0,\alpha)$,
$(a,b)=(0,1)$ or $(a,b)=(\alpha,1-\alpha)$.

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r_{n-1}^{*}=a+b,r^{*}_{n}=a,r^{\alpha\text{-RR}}_{t}=a+b$
for $n\leq t\leq m$ and $r^{\alpha\text{-RR}}_{m+1}=a.$ then for
$(a,b)=(0,\alpha)$, $(a,b)=(0,1)$ or $(a,b)=(\alpha,1-\alpha)$,

$(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}\geq
b\displaystyle\sum_{l=n}^{m-1}c_{l}-Mb.$

###### Proof.

Given $r^{\alpha\text{-RR}}_{m}=a+b$ and $r^{\alpha\text{-RR}}_{m+1}=a.$ So
from Algorithm 1, we have
$\text{totalCost}(R_{a+b}^{n},I_{m})>\text{totalCost}(R_{a}^{(\tau_{a})},I_{m})$
for $\tau_{a}\in[n,m]$ and hence
$\text{totalCost}(R_{a}^{n},I_{m-1})\geq\text{totalCost}(R_{a+b}^{n},I_{m-1})$.
Which implies
$g(a)\displaystyle\sum_{l=n}^{m-1}x_{l}+a\displaystyle\sum_{l=n}^{m-1}c_{l}+Mb\geq
g(a+b)\displaystyle\sum_{l=n}^{m-1}x_{l}+(a+b)\displaystyle\sum_{l=n}^{m-1}c_{l}$.
By definition,

$\displaystyle\displaystyle\sum_{l=n}^{m}x_{l}$
$\displaystyle=\left(\displaystyle\sum_{l=n}^{m-1}x_{l}\right)+x_{m}$
$\displaystyle(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m}x_{l}$
$\displaystyle\geq b\displaystyle\sum_{l=n}^{m-1}c_{l}-M+0$ $\displaystyle\geq
b\displaystyle\sum_{l=n}^{m-1}x_{l}-Mb.$

Thus proving the result. ∎

The next lemma characterizes upper limit on the past time from which
$\alpha$-RR compares costs to make a fetching decision.

###### Lemma 0.

Let $r^{*}_{t}$, $r^{\alpha\text{-RR}}_{t}$ denote the hosting states under
$\alpha$-OPT, $\alpha$-RR policies respectively in time-slot $t$. If
$r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}\neq r^{*}_{n}$, then
$\alpha\text{-RR}$ checks back only till time-slot $n$ to make a fetching
decision.

###### Proof.

We prove this result by contradiction. Suppose
$r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}=a$, $r^{*}_{n}=a+b$ and let
$r^{\alpha\text{-RR}}_{m_{1}}=a+b$ at some $m_{1}\in[n+1,m]$ for
$(a,b)=(0,\alpha)$, $(a,b)=(0,1)$, and $(a,b)=(\alpha,1-\alpha)$. This implies
there exists an $n_{1}<m_{1}$ such that
$\text{totalCost}(R_{a}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{a+b}^{n_{1}},I_{m_{1}}).$
That is $(g(a)-g(a+b))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}\geq
b\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+bM$. If $n_{1}<n$ then we have
$(g(a)-g(a+b))\displaystyle\sum_{l=n}^{m_{1}}x_{l}<b\displaystyle\sum_{l=n}^{m_{1}}c_{l}+bM$
that implies
$(g(a)-g(a+b))\displaystyle\sum_{l=n_{1}}^{n-1}x_{l}>b\displaystyle\sum_{l=n_{1}}^{n-1}c_{l}$.
We construct another policy $\eta$ which is same as $\alpha$-OPT except that
$r^{\eta}_{t}=a+b$ during $n_{1}\leq t<n$. The total cost incurred by $\eta$
in $n_{1}\leq t<n$ is
$C^{\eta}=bM+b\displaystyle\sum_{l=n_{1}}^{n}c_{l}+g(a+b)\displaystyle\sum_{l=n_{1}}^{n}x_{l}.$
The total cost incurred by $\alpha$-OPT in $n_{1}\leq t<n$ is
$C^{\alpha\text{-OPT}}=bM+g(a)\displaystyle\sum_{l=n_{1}}^{n-1}x_{l}+(a+b)c_{n}+g(a+b)x_{n}.$
The difference
$C^{\eta}-C^{\alpha\text{-OPT}}=b\displaystyle\sum_{l=n_{1}}^{n-1}c_{l}-(g(a)-g(a+b))\displaystyle\sum_{l=n_{1}}^{n-1}x_{l}$,
is negative.

Thus the result follows. ∎

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}=\alpha$,
$r_{t}^{*}=1$ for $n\leq t\leq m$, and $r_{m+1}^{*}\neq 1$ then
$\alpha\text{-RR}$ fetches $(1-\alpha)$ fraction of service at some time-slot
in $[n+1,m]$. After fetching $(1-\alpha)$ fraction of service,
$\alpha\text{-RR}$ does not evict any fraction of service till the end of
time-slot $m.$

###### Proof.

Since $r^{*}_{n-1}=\alpha$, $r_{t}^{*}=1$ for $n\leq t\leq m$, and
$r_{m+1}^{*}\neq 1$, the total cost incurred by $\alpha$-OPT in $n\leq t\leq
m$ is $C^{\alpha\text{-OPT}}=\displaystyle\sum_{l=n}^{m}c_{l}+(1-\alpha)M.$
Assume that $\alpha\text{-RR}$ evicts $\alpha$ fraction of service at
$m_{1}\in[n+1,m]$. Therefore there exists $n<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})$.
Which implies $(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M<\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$ and hence
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M<\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$
when $\alpha+g(\alpha)<1$. We construct another policy $\eta$ which is same
$\alpha$-OPT except that $r^{\eta}_{t}=0$ during $n_{1}\leq t\leq m_{1}$. The
total cost incurred by $\eta$ in $n\leq t\leq m$ is
$C^{\eta}=(1-\alpha)M+\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M+\displaystyle\sum_{l=m_{1}+1}^{m-1}c_{l}.$
The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M-\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$,
is negative. Therefore our assumption that $\alpha\text{-RR}$ evicts $\alpha$
fraction of service during $[n+1,m]$ is false.

Assume that $\alpha\text{-RR}$ does not fetch remaining $(1-\alpha)$ fraction
of service at any time-slot during $[n+1,m].$ Therefore for any $n<n_{1}<m$,
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m})<\text{totalCost}(R_{1}^{n_{1}},I_{m})$.
Which implies
$g(\alpha)\displaystyle\sum_{l=n_{1}}^{m}x_{l}<(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m}c_{l}+M(1-\alpha)$
for any $n_{1}\in(n,m)$. We construct another policy $\eta$ which is same
$\alpha$-OPT except that $r^{\eta}_{t}=\alpha$ during $n\leq t\leq m$. The
total cost incurred by $\eta$ in $n\leq t\leq m$ is
$C^{\eta}=\alpha\displaystyle\sum_{l=n}^{m}c_{l}+g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}.$
The difference
$C^{\eta}-C^{\alpha\text{-OPT}}=g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}-(1-\alpha)M-(1-\alpha)\displaystyle\sum_{l=n}^{m}c_{l}$,
is negative. So our assumption is false.

Assume that after fetching $(1-\alpha)$ fraction of service at
$\widetilde{n}\in[n+1,m]$, $\alpha\text{-RR}$ evicts full service at
$m_{1}\in[\widetilde{n}+1,m]$. Therefore there exists
$\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$.
Which means
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M<\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$.
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=0$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred by
$\eta$ in $n\leq t\leq m$ is
$C^{\eta}=M(1-\alpha)+\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M+\displaystyle\sum_{l=m_{1}+1}^{m}c_{l}.$
The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M-\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$,
is negative. So our assumption is false.

Assume that after fetching $(1-\alpha)$ fraction of service at
$\widetilde{n}\in[n+1,m]$, $\alpha\text{-RR}$ evicts $(1-\alpha)$ service at
$m_{1}\in[\widetilde{n}+1,m]$. Therefore there exists
$\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$.
Which implies
$g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+(1-\alpha)M<(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$.
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=\alpha$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred
by $\eta$ in $n\leq t\leq m$ is
$C^{\eta}=M(1-\alpha)+\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+M(1-\alpha)+\displaystyle\sum_{l=m_{1}+1}^{m}c_{l}.$
The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M(1-\alpha)-(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$,
is negative. So our assumption is false. This proves the result. ∎

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}=1$,
$r_{t}^{*}=\alpha$ for $n\leq t\leq m$, and $r_{m+1}^{*}=1$ then
$\alpha\text{-RR}$ evicts $(1-\alpha)$ fraction of service at some time-slot
in $[n+1,m]$. After evicting $(1-\alpha)$ fraction of service,
$\alpha\text{-RR}$ does not evict $\alpha$ fraction of service or does not
fetch $(1-\alpha)$ fraction of service till the end of time-slot $m.$

###### Proof.

Since $r_{n-1}^{*}=1$, $r_{t}^{*}=\alpha$ for $n\leq t\leq m$, and
$r_{m+1}^{*}\neq\alpha$ the total cost incurred by $\alpha$-OPT in $n\leq
t\leq m$ is
$C^{\alpha\text{-OPT}}=g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}+\alpha\displaystyle\sum_{l=n}^{m}c_{l}.$
Assume that $\alpha\text{-RR}$ evicts full service at $m_{1}\in[n+1,m]$.
Therefore there exists $n_{1}\in(n,m_{1}]$ such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$
and
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})$.
Which implies
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M<\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$
and $(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M<\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$. We construct another policy
$\eta$ which is same $\alpha$-OPT except that $r^{\eta}_{t}=0$ during
$n_{1}\leq t\leq m_{1}$. The total cost incurred by $\eta$ in $n\leq t\leq m$
is
$C^{\eta}=\alpha\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+g(\alpha)\displaystyle\sum_{l=n}^{n_{1}-1}x_{l}+\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M+\alpha\displaystyle\sum_{l=m_{1}+1}^{m}c_{l}+g(\alpha)\displaystyle\sum_{l=m_{1}+1}^{m}x_{l}.$
The difference
$C^{\eta}-C^{\alpha\text{-OPT}}=(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M-\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$, is negative. So our
assumption is false.

Assume that $\alpha\text{-RR}$ does not evict $(1-\alpha)$ fraction of service
at any time-slot in $[n+1,m]$. Therefore for any $n_{1}\in(n,m]$,
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m})\geq\text{totalCost}(R_{1}^{n_{1}},I_{m})$.
Which implies
$g(\alpha)\displaystyle\sum_{l=n_{1}}^{m}x_{l}+(1-\alpha)M\geq(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m}c_{l}$.
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=1$ during $n\leq t\leq m$. The total cost incurred by $\eta$ in
$n\leq t\leq m$ is $C^{\eta}=\displaystyle\sum_{l=n}^{m}c_{l}.$ When
$r_{m+1}^{*}=1$, the difference
$C^{\eta}-C^{\alpha-\text{OPT}}=(1-\alpha)\displaystyle\sum_{l=n}^{m}c_{l}-g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}-(1-\alpha)M$,
is negative. So our assumption is false.

Assume that after evicting $(1-\alpha)$ fraction of service at
$\widetilde{n}\in[n+1,m]$, $\alpha\text{-RR}$ evicts $\alpha$ fraction of
service at $m_{1}\in[\widetilde{n}+1,m]$. Therefore there exists
$\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})$.
Which implies $(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M<\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$. We construct another policy
$\eta$ which is same $\alpha$-OPT except that $r^{\eta}_{t}=0$ during
$n_{1}\leq t\leq m_{1}$. The total cost incurred by $\eta$ in $n\leq t\leq m$
is
$C^{\eta}=\alpha\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+g(\alpha)\displaystyle\sum_{l=n}^{n_{1}-1}x_{l}+\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha\displaystyle\sum_{l=m_{1}+1}^{m}c_{l}+g(\alpha)\displaystyle\sum_{l=m_{1}+1}^{m}x_{l}+\alpha
M.$ The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M-\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$, is negative. So our
assumption is false.

Assume that after evicting $(1-\alpha)$ fraction of service at
$\widetilde{n}\in[n+1,m]$, $\alpha\text{-RR}$ fetches $(1-\alpha)$ fraction of
service at $m_{1}\in[\widetilde{n}+1,m]$. Therefore there exists
$\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$.
Which implies
$g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}\geq(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+(1-\alpha)M$.
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=1$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred by
$\eta$ in $n\leq t\leq m$ is
$C^{\eta}=\alpha\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+g(\alpha)\displaystyle\sum_{l=n}^{n_{1}-1}x_{l}+(1-\alpha)M+\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+\alpha\displaystyle\sum_{l=m_{1}+1}^{m}c_{l}+g(\alpha)\displaystyle\sum_{l=m_{1}+1}^{m}x_{l}.$
The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+(1-\alpha)M-g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}$,
is negative. So our assumption is false. This proves the result. ∎

###### Lemma 0.

Let $r^{*}_{t}$ and $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under
$\alpha$-OPT and $\alpha$-RR respectively in time-slot $t$. If
$r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}=1$, $r_{t}^{*}=0$ for $n\leq t\leq m$,
and $r_{m+1}^{*}\neq 0$ then $\alpha\text{-RR}$ evicts full service at some
time-slot in $[n+1,m]$. After evicting full service, $\alpha\text{-RR}$ does
not fetch any fraction of service till the end of time-slot $m.$

###### Proof.

Since $r_{n-1}^{*}=1$, $r_{t}^{*}=0$ for $n\leq t\leq m$, and $r_{m+1}^{*}\neq
0$, the total cost incurred by $\alpha$-OPT in $n\leq t\leq m$ is
$C^{\alpha\text{-OPT}}=\displaystyle\sum_{l=n}^{m}x_{l}.$

Assume that $\alpha\text{-RR}$ does not evict full service at any
$m_{1}\in[n+1,m]$. Therefore for any $n\leq n_{1}<m_{1}\leq m$,
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$
and
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})$.
Which implies
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M\geq\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$
and $\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M\geq
g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+(1-\alpha)M\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$.
Suppose $r_{m+1}^{*}=1$, we construct another policy $\eta$ which is same
$\alpha$-OPT except that $r^{\eta}_{t}=1$ during $n\leq t\leq m$. When , the
total cost incurred by $\eta$ in $n\leq t\leq m+1$ is
$C^{\eta}=\displaystyle\sum_{l=n}^{m+1}c_{l}.$ In this case the difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\displaystyle\sum_{l=n}^{m}c_{l}-\displaystyle\sum_{l=n}^{m}x_{l}-M$,
is negative. So our assumption is false. Therefore, $\alpha\text{-RR}$ evicts
full service at some time-slot in $[n+1,m]$. Suppose $r_{m+1}^{*}=\alpha$, we
construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=\alpha$ during $n\leq t\leq m$. When , the total cost incurred
by $\eta$ in $n\leq t\leq m+1$ is
$C^{\eta}=\alpha\displaystyle\sum_{l=n}^{m+1}c_{l}+g(\alpha)x_{l}.$ In this
case the difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\alpha\displaystyle\sum_{l=n}^{m}c_{l}-(1-g(\alpha))\displaystyle\sum_{l=n}^{m}x_{l}-\alpha
M$, is negative.

Assume that after evicting full service at $\widetilde{n}\in[n+1,m]$,
$\alpha\text{-RR}$ fetches $\alpha$ fraction of service at
$m_{1}\in[\widetilde{n}+1,m]$. Therefore there exists
$\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})$.
Which implies

$(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}\geq\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+\alpha
M$.We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=\alpha$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred
by $\eta$ in $n\leq t\leq m$ is
$C^{\eta}=\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M+\displaystyle\sum_{l=m_{1}+1}^{m}x_{l}.$ The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\alpha
M+\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}-(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}$,
is negative. So our assumption is false.

Assume that after evicting full service at $\widetilde{n}\in[n+1,m]$,
$\alpha\text{-RR}$ fetches full service at $m_{1}\in[\widetilde{n}+1,m]$.
Therefore there exists $\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$.Which
implies
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}\geq\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+M$.
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=1$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred by
$\eta$ in $n\leq t\leq m$ is
$C^{\eta}=\displaystyle\sum_{l=n}^{n_{1}-1}x_{l}+M+\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+\displaystyle\sum_{l=m_{1}+1}^{m}x_{l}.$
The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=M+\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}-\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}$
is negative. So our assumption is false.

This proves the result. ∎

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}=0$, $r_{t}^{*}=1$
for $n\leq t\leq m$, and $r_{m+1}^{*}\neq 1$ then $\alpha\text{-RR}$ fetches
full service at some time-slot in $[n+1,m]$. After fetching full service,
$\alpha\text{-RR}$ does not evict any fraction of service till the end of
time-slot $m.$

###### Proof.

Since $r_{n-1}^{*}=0$, $r_{t}^{*}=1$ for $n\leq t\leq m$, and $r_{m+1}^{*}\neq
1$, the total cost incurred by $\alpha$-OPT in $n\leq t\leq m$ is
$C^{\alpha-\text{OPT}}(n,m)=M+\displaystyle\sum_{l=n}^{m}c_{l}.$

If $\alpha+g(\alpha)\geq 1$ then by Theorem 1, RR will not fetch $\alpha$
fraction of service, so we focus on the case when $\alpha+g(\alpha)<1$. Assume
that $\alpha\text{-RR}$ does not fetch any service during $[n+1,m]$. Therefore
for any $n_{1}\in[n+1,m]$,
$\text{totalCost}(R_{0}^{n_{1}},I_{m})<\text{totalCost}(R_{1}^{n_{1}},I_{m})$.
Which implies

$\displaystyle\sum_{l=n_{1}}^{m}x_{l}<\displaystyle\sum_{l=n_{1}}^{m}c_{l}+M.$
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=0$ during $n\leq t\leq m$. The total cost incurred by $\eta$ in
$n\leq t\leq m$ is $C^{\eta}=\displaystyle\sum_{l=n}^{m}x_{l}.$ The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\displaystyle\sum_{l=n}^{m}x_{l}-\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}-M$
is negative. So our assumption is false.

If $\alpha\text{-RR}$ fetches $\alpha$ fraction of service at any
$\widetilde{n}\in[n+1,m)$, assume that it evicts the service at
$m_{1}\in[\widetilde{n}+1,m]$. Therefore there exists
$\widetilde{n}<n_{1}<m_{1}$ such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})$.
Which implies $(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+\alpha
M<\alpha\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$. Using $\alpha<1-g(\alpha)$
we get
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M<\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=0$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred by
$\eta$ in $n_{1}\leq t\leq m_{1}$ is
$C^{\eta}=\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M.$ The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}+M-\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}$,
is negative. So our assumption is false.

When $\alpha\text{-RR}$ fetches $\alpha$ fraction of service at any
$\widetilde{n}\in[n+1,m)$, assume that $\alpha\text{-RR}$ does not fetch
remaining $(1-\alpha)$ fraction of service at any
$m_{1}\in[\widetilde{n}+1,m]$. Therefore for any $n<n_{1}<m_{1}$,
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})<\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$.
$g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}<(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+M(1-\alpha).$
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=\alpha$ during $n\leq t\leq m$. The total cost incurred by
$\eta$ in $n\leq t\leq m$ is $C^{\eta}=\alpha
M+g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}+\displaystyle\sum_{l=n}^{m}c_{l}.$
The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=g(\alpha)\displaystyle\sum_{l=n}^{m_{1}}x_{l}-\displaystyle\sum_{l=n}^{m_{1}}c_{l}-(1-\alpha)M$
is negative. So our assumption is false. Therefore $\alpha\text{-RR}$ fetches
full service at some time-slot in $[n+1,m]$.

Using Lemma 9, we conclude that when $r_{t}^{*}=r^{\alpha\text{-RR}}_{t}=1$
for $t\leq m$ then $\alpha\text{-RR}$ does not evict any fraction of service
till the time-slot $m.$ ∎

###### Lemma 0.

Let $r^{\alpha\text{-RR}}_{t}$ denote the hosting status under $\alpha$-RR in
time-slot $t$. If $r_{n-1}^{*}=r^{\alpha\text{-RR}}_{n-1}=0$,
$r_{t}^{*}=\alpha$ for $n\leq t\leq m$, and $r_{m+1}^{*}\neq\alpha$ then
$\alpha\text{-RR}$ fetches $\alpha$ fraction of service at some time-slot in
$[n+1,m]$. After fetching $\alpha$ fraction of service,$\alpha\text{-RR}$ does
not evict $\alpha$ fraction of service or does not fetch $(1-\alpha)$ fraction
of service till the end of time-slot $m.$

###### Proof.

Since $r_{n-1}^{*}=0$, $r_{t}^{*}=\alpha$ for $n\leq t\leq m$, and
$r_{m+1}^{*}\neq\alpha$, the total cost incurred by $\alpha$-OPT in $n\leq
t\leq m$ is $C^{\alpha-\text{OPT}}(n,m)=\alpha
M+g(\alpha)\displaystyle\sum_{l=n}^{m}x_{l}+\alpha\displaystyle\sum_{l=n}^{m}c_{l}.$
Assume that $\alpha\text{-RR}$ fetches full service at $m_{1}\in[n+1,m]$.
Therefore there exists $n<n_{1}<m_{1}$, such that
$\text{totalCost}(R_{0}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$
and
$\text{totalCost}(R_{\alpha}^{n_{1}},I_{m_{1}})\geq\text{totalCost}(R_{1}^{n_{1}},I_{m_{1}})$.
Which implies
$\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}\geq\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+M$
and
$g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}\geq(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+(1-\alpha)M.$
We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=1$ during $n_{1}\leq t\leq m_{1}$. The total cost incurred by
$\eta$ in $n\leq t\leq m$ is $C^{\eta}=\alpha
M+g(\alpha)\displaystyle\sum_{l=n}^{n_{1}-1}x_{l}+\alpha\displaystyle\sum_{l=n}^{n_{1}-1}c_{l}+(1-\alpha)M+\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+g(\alpha)\displaystyle\sum_{l=m_{1}+1}^{m}x_{l}+\alpha\displaystyle\sum_{l=m_{1}+1}^{m}c_{l}.$
The difference
$C^{\eta}-C^{\alpha\text{-OPT}}=(1-\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}c_{l}+(1-\alpha)M-g(\alpha)\displaystyle\sum_{l=n_{1}}^{m_{1}}x_{l}$
is negative. So our assumption is false.

Assume that $\alpha\text{-RR}$ does not fetch $\alpha$ fraction of service at
any time-slot in $[n+1,m]$. Therefore for any $n_{1}\in[n+1,m]$,
$\text{totalCost}(R_{0}^{n_{1}},I_{m})<\text{totalCost}(R_{\alpha}^{n_{1}},I_{m})$.
Which implies
$(1-g(\alpha))\displaystyle\sum_{l=n_{1}}^{m}x_{l}<\alpha\displaystyle\sum_{l=n_{1}}^{m}c_{l}+\alpha
M.$ We construct another policy $\eta$ which is same $\alpha$-OPT except that
$r^{\eta}_{t}=0$ during $n\leq t\leq m$. The total cost incurred by $\eta$ in
$n\leq t\leq m$ is $C^{\eta}=\displaystyle\sum_{l=n}^{m}x_{l}.$ The difference
$C^{\eta}-C^{\alpha-\text{OPT}}=(1-g(\alpha))\displaystyle\sum_{l=n}^{m}x_{l}-\alpha\displaystyle\sum_{l=n}^{m}c_{l}-M\alpha$
is negative. So our assumption is false. Therefore $\alpha\text{-RR}$ fetches
$\alpha$ fraction of service at some time-slot in $[n+1,m]$. Using Lemma , we
conclude that when $r_{t}^{*}=r^{\alpha\text{-RR}}_{t}=\alpha$ for $t\leq m$
then $\alpha\text{-RR}$ does not evict $\alpha$ fraction of service or does
not fetch $(1-\alpha)$ fraction of service till the end of time-slot $m.$ ∎

We provide a proof of Theorem 2(b). To compare the costs incurred by
$\alpha$-RR and $\alpha$-OPT we divide time into frames $[1,t_{1}-1]$,
$[t_{1},t_{2}-1],[t_{2},t_{3}-1],\ldots,$ where $t_{j}-1$ is the time-slot in
which $\alpha$-OPT downloads a fraction of or full service for the
$j^{\text{th}}$ time for $j\in\\{1,2,\ldots\\}.$ We have three types of
frames.

  1. 1.

Type-1 frame: It starts when $\alpha$-OPT fetches the entire service. By Lemma
3, Type-1 frames exist only if $c_{\text{min}}<1$.

  2. 2.

Type-$\alpha$ frame: It starts when $\alpha$-OPT fetches $\alpha$ fraction of
the service. By Lemma 3, Type-$\alpha$ frames exist only if $\alpha
c_{\text{min}}+g(\alpha)<1$.

  3. 3.

Type-$(1-\alpha)$ frame: It starts when $\alpha$-OPT fetches $(1-\alpha)$
fraction of the service. By Lemma 3, Type-$(1-\alpha)$ frames exist only if
$c_{\text{min}}<\alpha c_{\text{min}}+g(\alpha)$.

Refer to Figure 26 for an illustration of the frame.  Note that the main
difference between the proof techniques in this work and in (Narayana et al.,
2021a) is that in this work we have three different types of frames possible
whereas in (Narayana et al., 2021a) there is a possibility of only one frame.
We first focus on the Type-$(1-\alpha)$ frame. By Lemma 9, $\alpha$-RR fetches
$(1-\alpha)$ fraction of service at sometime
$t_{f}^{\alpha\text{-RR}}\in[t_{1},\tau]$, and by Lemma 10, $\alpha$-RR evicts
$(1-\alpha)$ fraction of service at sometime
$t_{e}^{\alpha\text{-RR}}\geq\tau$. Both $\alpha$-OPT and $\alpha$-RR makes
one fetch in this frame. Hence the difference in the fetch costs is zero. We
now focus on the service and rent cost incurred by the two policies.

  * –

Let $\tau_{1}=t_{f}^{\alpha\text{-RR}}-t_{1}.$ Since $\alpha\text{-RR}$ does
not fetch $(1-\alpha)$ fraction of the service in
$[t_{1},t_{f}^{\alpha\text{-RR}}]$, the cost incurred in
$[t_{1},t_{f}^{\alpha\text{-RR}}]$ by $\alpha\text{-RR}$ is
$g(\alpha)\displaystyle\sum_{l=t_{1}}^{t_{f}^{\alpha\text{-RR}}}x_{l}+\alpha\displaystyle\sum_{l=t_{1}}^{t_{f}^{\alpha\text{-RR}}}c_{l}.$
$\alpha$-OPT fetches full service in $[t_{1},t_{f}^{\alpha\text{-RR}}]$ hence
the cost incurred in $[t_{1},t_{f}^{\alpha\text{-RR}}]$ by $\alpha$-OPT is
$\displaystyle\sum_{l=t_{1}}^{t_{f}^{\alpha\text{-RR}}}c_{l}.$ By Lemma 6,

$g(\alpha)\displaystyle\sum_{l=t_{1}}^{t_{f}^{\alpha\text{-RR}}}x_{l}<(1-\alpha)\displaystyle\sum_{l=t_{1}}^{t_{f}^{\alpha\text{-RR}}-1}c_{l}+M(1-\alpha)+g(\alpha).$

Hence difference in the service and rent cost incurred by $\alpha\text{-RR}$
and $\alpha$-OPT in $[t_{1},t_{f}^{\alpha\text{-RR}}]$ is at most
$(M-c_{\text{min}})(1-\alpha)+g(\alpha).$

  * –

The service and rent cost incurred by $\alpha$-OPT and $\alpha\text{-RR}$ in
$[t_{f}^{\alpha\text{-RR}}+1,\tau]$ are equal.

  * –

Let $\tau_{2}=t_{e}^{\alpha\text{-RR}}-\tau$. The cost incurred by
$\alpha$-OPT in $[\tau+1,t_{e}^{\alpha\text{-RR}}]$ is
$g(\alpha)\displaystyle\sum_{l=\tau}^{t_{e}^{\alpha\text{-RR}}}x_{l}+\alpha\displaystyle\sum_{l=\tau}^{t_{e}^{\alpha\text{-RR}}}c_{l}$
The cost incurred by $\alpha\text{-RR}$ in $[\tau+1,t_{e}^{\alpha\text{-RR}}]$
is $\displaystyle\sum_{l=\tau}^{t_{e}^{\alpha\text{-RR}}}c_{l}$. By Lemma 7,

$g(\alpha)\displaystyle\sum_{l=\tau}^{t_{e}^{\alpha\text{-RR}}}x_{l}\geq(1-\alpha)\displaystyle\sum_{l=\tau}^{t_{e}^{\alpha\text{-RR}}-1}c_{l}-M(1-\alpha).$

Hence difference in the service and rent cost incurred by $\alpha\text{-RR}$
and $\alpha$-OPT in $[t_{1},t_{f}^{\alpha\text{-RR}}]$ is at most
$(M+c_{\text{max}})(1-\alpha).$

  * –

The service and rent cost incurred by $\alpha$-OPT and $\alpha\text{-RR}$ in
$[t_{e}^{\alpha\text{-RR}}+1,t_{2}-1]$ are equal.

We therefore have that,

$\displaystyle SC_{1-\alpha}^{\alpha\text{-RR}}(j)$ $\displaystyle-
SC_{1-\alpha}^{\text{$\alpha$-OPT}}(j)\leq(2M+c_{\text{max}}-c_{\text{min}})(1-\alpha)+g(\alpha)$
$\displaystyle\leq 2M(1-\alpha)+(M+1)(1-\alpha)+(1-\alpha)$ (6)
$\displaystyle\leq 3M(1-\alpha)+2(1-\alpha).$

By Lemma 4, once $\alpha$-OPT downloads $(1-\alpha)$ fraction of the service,
it will not evict for at least
$\frac{(1-\alpha)M}{g(\alpha)-(1-\alpha)c_{\text{min}}}$ slots. Therefore,

$\displaystyle
SC_{1-\alpha}^{\text{$\alpha$-OPT}}(j)\geq(1-\alpha)M+(1-\alpha)c_{\text{min}}\frac{(1-\alpha)M}{g(\alpha)-(1-\alpha)c_{\text{min}}}$
(7) $\displaystyle\implies
M(1-\alpha)\leq\frac{g(\alpha)-(1-\alpha)c_{\text{min}}}{g(\alpha)}C^{\text{$\alpha$-OPT}}(j).$

From (6) and (7),

$\displaystyle SC_{1-\alpha}^{\alpha\text{-RR}}(j)$
$\displaystyle\leq\left(4+\frac{2}{M}-\frac{(1-\alpha)c_{\text{min}}}{g(\alpha)}(2+\frac{1}{M})\right)SC_{1-\alpha}^{\text{$\alpha$-OPT}}(j)$
(8)
$\displaystyle<\left(4+\frac{2}{M}\right)SC_{1-\alpha}^{\text{$\alpha$-OPT}}(j).$

Hence we conclude that in every Type-$(1-\alpha)$ frame, $\alpha\text{-RR}$ is
(4+$\frac{2}{M}$)-optimal.

IIIIIIIVType-$(1-\alpha)$ frame$\alpha$-OPT$\alpha$-RR Figure 26. Illustration
showing a fetch and eviction by $\alpha$-OPT and $\alpha$-RR in a
Type-$(1-\alpha)$ frame. Downward arrows represent fetches, upward arrows
indicate evictions. Black and blue arrows correspond to the $\alpha$-OPT and
$\alpha$-RR policies respectively. The two bars below the time-line indicate
the state of the system under $\alpha$-OPT and $\alpha$-RR. The solid black
and solid blue portions represent the intervals during with $\alpha$-OPT and
$\alpha$-RR host the service respectively.

Now we consider any Type-$\alpha$ frame that is when a frame starts with
$\alpha$ download of service by $\alpha$-OPT. This frame may contains many
sub-frames of Type-$(1-\alpha)$. We refer to them as Type-$(1-\alpha)$ sub-
frames. Let the number of such sub-frames be $N_{1-\alpha}$. We divide the
cost incurred $\alpha$-OPT in this frame into two parts

  * –

$SC^{\text{$\alpha$-OPT}}_{\alpha}(i)$\- Cost incurred by $\alpha$-OPT in the
frame $i$ except in the region during Type-$(1-\alpha)$ sub-frames in it.

  * –

$SC^{\text{$\alpha$-OPT}_{j}}_{1-\alpha}(i)$\- Cost incurred by $\alpha$-OPT
in the $j^{\text{th}}$ Type-$(1-\alpha)$ sub-frame in Type-$\alpha$ frame $i$.

Therefore,

$C^{\text{$\alpha$-OPT}}(i)=SC^{\text{$\alpha$-OPT}}_{\alpha}(i)+\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\text{$\alpha$-OPT}_{j}}_{1-\alpha}(i).$

Similarly, We divide the cost incurred $\alpha\text{-RR}$ in this frame into
two parts

  * –

$SC^{\alpha\text{-RR}}_{\alpha}(i)$\- Cost incurred by $\alpha\text{-RR}$ in
frame $i$ except in the region during Type-$(1-\alpha)$ sub-frames in it.

  * –

$SC^{\alpha\text{-RR}_{j}}_{1-\alpha}(i)$\- Cost incurred by
$\alpha\text{-RR}$ in the $j^{\text{th}}$ Type-$(1-\alpha)$ sub-frame in frame
$i$.

Therefore,

$C^{\alpha\text{-RR}}(i)=SC^{\alpha\text{-RR}}_{\alpha}(i)+\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\alpha\text{-RR}_{j}}_{1-\alpha}(i).$

By Lemmas 5, 8 and 13, $\alpha\text{-RR}$ downloads only $\alpha$ fraction of
service at least after $\frac{\alpha M}{1-g(\alpha)-\alpha c_{\text{min}}}$
time-slots from the beginning of the frame. So we can write

$\displaystyle SC^{\text{$\alpha$-OPT}}_{\alpha}(i)\geq\alpha M+\alpha
c_{\text{min}}\frac{\alpha M}{1-g(\alpha)-\alpha c_{\text{min}}}$ (9)
$\displaystyle\implies M\alpha\leq\frac{1-g(\alpha)-\alpha
c_{\text{min}}}{1-g(\alpha)}SC^{\text{$\alpha$-OPT}}_{\alpha}(i).$

By using Lemmas 6 and 7, we get

$\displaystyle SC^{\alpha\text{-RR}}_{\alpha}(i)-$ $\displaystyle
SC^{\text{$\alpha$-OPT}}_{\alpha}(i)$ $\displaystyle\leq
2M\alpha+1-g(\alpha)+\alpha(c_{\text{max}}-c_{\text{min}})$ (10)
$\displaystyle\leq 3M\alpha+1-g(\alpha)+\alpha.$

Using inequalities 8, 9 and 10 we write,

$\displaystyle C^{\alpha\text{-RR}}(i)-$ $\displaystyle
C^{\alpha\text{-OPT}}(i)$
$\displaystyle\leq\left(3+\dfrac{1}{M}+\dfrac{1-g(\alpha)}{M\alpha}\right)SC^{\alpha-\text{OPT}}_{\alpha}(i)$
$\displaystyle\hskip
80.00012pt+(3+\frac{2}{M})\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\alpha-\text{OPT}_{j}}_{1-\alpha}(i)$
(11) $\displaystyle C^{\alpha\text{-RR}}(i)$
$\displaystyle\leq\left(4+\frac{1}{M}+\max\left\\{\dfrac{1}{M},\dfrac{1-g(\alpha)}{M\alpha}\right\\}\right)C^{\alpha\text{-OPT}}(i).$

Hence we conclude that in every Type-$\alpha$ frame $\alpha\text{-RR}$ is
$\left(4+\frac{1}{M}+\max\left\\{\dfrac{1}{M},\dfrac{1-g(\alpha)}{M\alpha}\right\\}\right)$-optimal.

Now we consider any Type-$1$ frame that is when a frame starts with full
download of service by $\alpha$-OPT. This frame may contains an eviction of
$(1-\alpha)$ fraction of service by $\alpha$-OPT followed by many sub-frames
which start with the download of $(1-\alpha)$ fraction of service by
$\alpha$-OPT. Let the number of such sub-frames be $N_{1-\alpha}$. We divide
the cost incurred $\alpha$-OPT in this frame into two parts

  * –

$SC^{\text{$\alpha$-OPT}_{j}}_{1-\alpha}(i)$\- Cost incurred by $\alpha$-OPT
in the $j^{\text{th}}$ Type-$(1-\alpha)$ sub-frame in frame $i$.

  * –

$SC^{\text{$\alpha$-OPT}}_{1}(i)$\- Cost incurred by $\alpha$-OPT in frame $i$
except in the region during $N_{1-\alpha}$ Type-$(1-\alpha)$ sub-frames.

Therefore,

$\displaystyle C^{\text{$\alpha$-OPT}}(i)$
$\displaystyle=SC^{\text{$\alpha$-OPT}}_{1}(i)+\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\text{$\alpha$-OPT}_{j}}_{1-\alpha}(i).$

Similarly, We divide the cost incurred $\alpha\text{-RR}$ in this frame into
two parts

  * –

$SC^{\alpha\text{-RR}_{j}}_{1-\alpha}(i)$\- Cost incurred by
$\alpha\text{-RR}$ in the $j^{\text{th}}$ $(1-\alpha)$\- sub-frame in frame
$i$.

  * –

$SC^{\alpha\text{-RR}}_{1}(i)$\- Cost incurred by $\alpha\text{-RR}$ in frame
$i$ except in the region during $N_{1-\alpha}$ sub-frames.

Therefore,

$C^{\alpha\text{-RR}}(i)=SC^{\alpha\text{-RR}}_{1}(i)+\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\alpha\text{-RR}_{j}}_{1-\alpha}(i).$

By Lemmas 5, 8 and 13, $\alpha\text{-RR}$ downloads full service at least
after $\frac{M}{1-c_{\text{min}}}$ time-slots from the beginning of the frame
$i$. So we can write

$\displaystyle SC^{\text{$\alpha$-OPT}}_{1}(i)\geq
M+c_{\text{min}}\frac{M}{1-c_{\text{min}}}$ (12) $\displaystyle\implies
M\leq(1-c_{\text{min}})SC^{\text{$\alpha$-OPT}}_{1}(i).$

Note that the last eviction by $\alpha$-OPT in frame $i$ is either eviction of
$\alpha$ fraction of service or eviction of full service. In either case the
difference $SC^{\alpha\text{-RR}}_{1}(i)-SC^{\text{$\alpha$-OPT}}_{1}(i)$ is
at most $2M+c_{\text{max}}-c_{\text{min}}+1$. This can be verified by applying
Lemmas 6 and 7 to the above two cases separately.

By Lemma 7 and inequality 12 we write,

$\displaystyle C^{\alpha\text{-RR}}(i)$
$\displaystyle-C^{\text{$\alpha$-OPT}}(i)\leq
2M+c_{\text{max}}-c_{\text{min}}+1$ $\displaystyle\hskip
56.9055pt+(3+\frac{2}{M})\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\text{$\alpha$-OPT}_{j}}_{1-\alpha}(i)$
$\displaystyle<(3+\frac{2}{M})SC^{\text{$\alpha$-OPT}}_{1}(i)+(3+\frac{2}{M})\displaystyle\sum_{j=1}^{N_{1-\alpha}}SC^{\text{$\alpha$-OPT}_{j}}_{1-\alpha}(i)$
(13) $\displaystyle C^{\alpha\text{-RR}}(i)$
$\displaystyle\leq(4+\frac{2}{M})C^{\text{$\alpha$-OPT}}(i).$

Hence we conclude that in every Type-1 frame, $\alpha\text{-RR}$ is
$(4+\frac{2}{M})$-optimal.

We then stitch results across frames to prove the result.

###  9.3. Proof of Theorem 4

We provide a sketch of the proof. Let $\mathcal{P}$ be any deterministic
online policy and $r_{t}\in\\{0,\alpha$,1} denote the hosting status under
$\mathcal{P}$ in a time-slot $t$. If under $\mathcal{P}$, $r_{0}=0$, consider
the arrival sequence with an arrival in each time-slot until $\mathcal{P}$
fetches the service (entire or partial) and no arrivals thereafter. If
$\mathcal{P}$ fetches entire service after $\tau$ time-slots then the cost
under $\mathcal{P}$ for this request sequence is,
$C^{\mathcal{P}}\geq\tau+M+c_{\text{min}}$. By Lemma 4, the cost under
$\alpha$-OPT for this request sequence is,

$\displaystyle C^{\alpha\text{-OPT}}=\begin{cases}\tau&\text{ if
}\tau\leq\frac{M}{1-c_{\text{min}}},\\\ M+\tau c_{\text{min}}&\text{ otherwise
}.\end{cases}$

For $M(1-c_{\text{min}})>c_{\text{min}}^{2}$, the ratio
$\frac{C_{\mathcal{P}}}{C_{\text{OPT}}}$ is minimum at
$\tau=\frac{M}{1-c_{\text{min}}}$. For $M(1-c_{\text{min}})\leq
c_{\text{min}}^{2}$, the ratio
$\dfrac{C^{\mathcal{P}}}{C^{\alpha-\text{OPT}}}$ is minimum when $\tau$ is
very large.

Let $\overline{\mathcal{P}}$ be any deterministic online policy and
$\overline{r}_{t}\in\\{0,\alpha$,1} denote the hosting status under
$\overline{\mathcal{P}}$ in a time-slot $t$. If under
$\overline{\mathcal{P}}$, $\overline{r}_{0}=1$, consider the arrival sequence
with no arrival in each time-slot until $\overline{\mathcal{P}}$ evicts the
full service. Then the arrival sequence changes in such a way that there is an
arrival in each time-slot. If $\overline{\mathcal{P}}$ evicts entire service
after $\overline{\tau}$ time-slots then the cost under
$\overline{\mathcal{P}}$ for this request sequence is,
$C_{\overline{\mathcal{P}}}\geq\overline{\tau}c_{\text{min}}+M+C^{\mathcal{P}}$.
Then the ratio

$\displaystyle\dfrac{C^{\overline{\mathcal{P}}}}{C^{\alpha-\text{OPT}}}\geq\dfrac{\overline{\tau}c_{\text{min}}+M}{C^{\alpha-\text{OPT}}}+\dfrac{C^{\mathcal{P}}}{C^{\alpha-\text{OPT}}}.$

Other cases can be proved along similar lines.

##  10\. Appendix B

In this section, we discuss the proofs of the results presented in Section 5.
We use the following lemmas to prove Theorem 1. Note that we use Model 2 to
prove results in this section.

###### Lemma 0.

Let $X_{t}$ is an indicator of request arriving in time-slot $t$,
$p=\mathbb{E}[X_{t}]$, Let $Z_{t}$ be the rent cost per time-slot,
$\\{Z_{t}\\}_{t\geq 1}$ is the sequence of negatively associated random
variables and $c=\mathbb{E}[Z_{t}]$. Under Assumption 7, let
$\mathbb{E}[C_{t}^{\alpha-\text{OPT-ON}}]$ be the cost per time-slot incurred
by the $\alpha-$OPT-ON policy. Then,

$\displaystyle\mathbb{E}[C_{t}^{\alpha-\text{OPT-ON}}]\geq\min\\{c,\alpha
c+g(\alpha)p,p\\}.$

###### Proof.

If full service is hosted at the edge in time-slot $t$, the expected cost
incurred is at least $\mathbb{E}[Z_{t}]$ = $c$. If $\alpha$ fraction of
service is hosted at the edge in time-slot $t$, the expected cost incurred is
at least $\mathbb{E}[\alpha Z_{t}+g(\alpha)X_{t}]$ = $\alpha c+g(\alpha)p$. If
the service is not hosted at the edge server, the expected cost incurred is at
least $p$. This proves the result. ∎

###### Lemma 0.

Let $X_{t}$ is an indicator of request arriving in time-slot $t$,
$p=\mathbb{E}[X_{t}]$. Let $Z_{t}$ be the rent cost per time-slot,
$\\{Z_{t}\\}_{t\geq 1}$ is the sequence of negatively associated random
variables and $c=\mathbb{E}[Z_{t}]$. For each of these combinations
$(a,B)=(1,1)$, $(a,B)=(\alpha,1-S_{l})$, $(a,B)=(1-\alpha,S_{l})$, define
$b=\mathbb{E}[B]$, $Y_{l}=BX_{l}-aZ_{l}$, and
$Y=\sum\limits_{l=t-\tau+1}^{t}Y_{l}$ then $Y$ satisfies,

for $((ac-bp)\tau+aM)>0$,,

$\displaystyle\mathbb{P}\left(Y\geq aM\right)$
$\displaystyle\leq\exp\left(-2\frac{((ac-
bp)\tau+aM)^{2}}{\tau(b+ac_{\text{max}}-ac_{\text{min}})^{2}}\right),$

and for $(bp-ac)\tau+aM>0$,

$\displaystyle\mathbb{P}\left(Y\leq a\tau c-aM\right)$
$\displaystyle\leq\exp\left(-2\frac{((bp-
ac)\tau+aM)^{2}}{\tau(b+ac_{\text{max}}-ac_{\text{min}})^{2}}\right).$

###### Proof.

Using total expectation rule we have,

$\displaystyle\mathbb{E}[X_{l}S_{l}]$
$\displaystyle=\mathbb{E}[X_{l}S_{l}|X_{l}=1]p+\mathbb{E}[X_{l}S_{l}|X_{l}=0](1-p)=pg(\alpha).$

Using i.i.d. condition of $\\{X_{t}\\}_{t\geq 1}$ and negatively associativity
of $\\{Z_{t}\\}_{t\geq 1}$, it follows that for $s>0$,
$\mathbb{E}[\exp(sY)]\leq\prod\limits_{l=t-\tau+1}^{t}\mathbb{E}[\exp(sY_{l})]$.
Moreover, $Y_{l}\in[-ac_{\text{max}},1-ac_{\text{min}}]$. Then the result
follows by Hoeffding’s inequality (Hoeffding, 1994; Wajc, 2017). ∎

###### Lemma 0.

Let
$\Lambda_{t}^{\mathcal{P}}=\mathbb{E}[C_{t}^{\mathcal{P}}-C_{t}^{\alpha-\text{OPT-
ON}}]$. Under Assumption 7,

  * –

Case $\frac{\alpha c}{1-g(\alpha)}<p<\frac{(1-\alpha)c}{g(\alpha)}$:

$\displaystyle\Lambda_{t}^{\alpha-\text{RR}}$
$\displaystyle\leq\min_{\lambda:\lambda>1\text{ and
}t>\lambda\widetilde{M}_{f}}f(\lambda,M,p,c,\alpha,g(\alpha)).$

  * –

Case $p>\max\\{c,\frac{(1-\alpha)c}{g(\alpha)}\\}$:

$\displaystyle\Lambda_{t}^{\alpha-\text{RR}}$
$\displaystyle\leq\min_{\lambda:\lambda>1\text{ and
}t>\lambda\widetilde{M}_{q}}q(\lambda,M,p,c,\alpha,g(\alpha)).$

  * –

Case $p<\min\\{c,\frac{\alpha c}{1-g(\alpha)}\\}$:

$\displaystyle\Lambda_{t}^{\alpha-\text{RR}}$
$\displaystyle\leq\min_{\lambda:\lambda>1\text{ and
}t>\lambda\widetilde{M}_{h}}h(\lambda,M,p,c,\alpha,g(\alpha)).$

###  10.1. Proof of Theorem 1

###### Proof.

Case 1: When $\frac{\alpha c}{1-g(\alpha)}<p<\frac{(1-\alpha)c}{g(\alpha)}$.
Let
$\widetilde{M_{f}}=\max\Bigg{\\{}\left\lceil\frac{M\alpha}{p(1-g(\alpha))-\alpha