On the Regret of Online Edge Service Hosting ¹¹footnotemark: 1

Software as a Service (SaaS) instances like online navigation platforms, Video-on-Demand services, etc., have stringent latency constraints in order to provide a good quality of experience to their customers. While most SaaSs use cloud resources, low latency necessitates the use of storage/computational resources at the edge, i.e., close to the end-user. A service is said to be hosted at the edge if the code and databases needed to serve user queries are stored on the edge servers and requests can be served at the edge. In this work, the service can also be partially hosted at the edge, in which case, customers’ requests can be partially served at the edge [1, 2]. For instance, consider a SaaS application which provides access to news articles on demand. A typical news article includes some text, some images and possibly some embedded videos. One way to partially host such a service is to store the text corresponding to the news articles at the edge and store the images/videos in the cloud. Each user request will then be served partially by the edge.

We consider the setting where third-party resources can be rented via short-term contracts to host the service, and the edge hosting status of the SaaS can be dynamically changed over time. If the service is not hosted at the edge, it can be fetched from the cloud servers by incurring a fetch cost. The performance of a hosting policy is a function of the rent cost, the fetch cost, and the quality of experience of the users. We refer to the algorithmic challenge of determining what fraction of the service to host at the edge over time as the service hosting problem. Note that we study the service hosting problem from the perspective of a specific SaaS provider which can rent third-party edge resources to improve their customers’ quality of experience by reducing the latency of their service.

Novel online service hosting policies with provable performance guarantees have been proposed in [3, 4]. The metric of interest in [3, 4] is the competitive ratio, defined as the ratio of the cost incurred by an online policy to the cost incurred by an optimal offline policy for the same request arrival sequence. Since the competitive ratio is multiplicative by definition, the absolute value of the difference in the cost incurred by an online policy and the optimal policy can be large even though the competitive ratio of the online policy is close to one. This motivates studying the performance of candidate policies in terms of regret, defined as the difference in the cost incurred by the policy and the optimal policy. Regret is a widely used metric in online learning [5], including recently for the caching problem [6, 7], which is closely related to the service hosting problem. In this work, one of our goals is to design hosting policies with provable guarantees in terms of the regret. Another key dimension in the performance guarantees of online policies is the assumption made on the request arrival process. Commonly studied settings include the stochastic setting and the adversarial setting, and we provide performance guarantees for both settings.

We consider a system consisting of a back-end server and an edge-server to serve customers of a service. The back-end server always hosts the service and can serve any requests that are routed to it. In this work, we allow the service to be partially hosted at the edge-server. When the service is partially hosted at the edge, requests are partially served at the edge and partially at the back-end server. Further, the fraction of service hosted at the edge can be changed over time. If the service is not hosted or partially hosted at the edge, parts of the service can be fetched from the back-end server to host at the edge.

Sequence of events in each time-slot: We consider a time-slotted system. In each time-slot, we first make the service hosting decision for that time-slot. Following this, requests may arrive and are served at the edge and/or the back-end server.

Request arrivals: We consider two types of arrival processes in this paper.

• -

  Stochastic arrivals: In this case, request arrivals are i.i.d. across time-slots with mean $\mu$.

• -

  Adversarial arrivals: In this case, the request arrival sequence is generated by an oblivious adversary²²2 The entire request sequence is assumed to be fixed apriori..

Let $r_{t}$ denote the number of request arrivals in time-slot $t$. We consider bounded requests, specifically, $0\leq r_{t}\leq\kappa$, and let $R_{t}=\sum_{i=1}^{t}r_{i}$ denote the cumulative requests observed by the end of time-slot $t$. In both cases, we assume that there are at most $\kappa$ arrivals per slot.

Costs: We model three types of costs.

1. -

   Rent cost ($\mathcal{C}^{\mathcal{P}}_{R,t}$): The system incurs a cost of $c$ units per time-slot to host the entire service at the edge. For hosting $f$ fraction of service, the system incurs a cost of $cf$ units per time-slot.

2. -

   Service cost ($\mathcal{C}^{\mathcal{P}}_{S,t}$): This is the cost incurred to use the back-end server to serve (parts of) requests. If $f$ fraction of service is hosted at the edge, the system incurs a service cost of $g(f)$ units per request, where $g(f)$ is a decreasing function of $f$. We fix $g(0)=1$, i.e., service cost is one unit when the service is not hosted at the edge.

3. -

   Fetch cost ($\mathcal{C}^{\mathcal{P}}_{F,t}$): The system incurs a cost of $M>1$ units for each fetch of the entire service from the back-end server to host on the edge-server. For fetching $f$ fraction of service, the system incurs a cost of $Mf$ units.

Let $\rho_{t}^{\mathcal{P}}$ denote the edge hosting status of the service in time slot $t$ under policy $\mathcal{P}$. We consider the setting where $\rho_{t}^{\mathcal{P}}\in\{\alpha_{1},\alpha_{2},\cdots,\alpha_{K-1},\alpha_{K}\}$ and $\rho_{t}^{\mathcal{P}}=\alpha_{i}$ implies that $\alpha_{i}$ fraction of the service is hosted at the edge-server in time-slot $t$. Note that $\alpha_{i}\in[0,1]$ and in particular we consider $\alpha_{1}=0$, $\alpha_{K}=1$ and $\alpha_{i}<\alpha_{j}$ for $i<j$. It follows that $\rho_{t}^{\mathcal{P}}=1$ implies that the entire service is hosted at the edge in time-slot $t$, and $\rho_{t}^{\mathcal{P}}=0$ implies that the service is not hosted at the edge in time-slot $t$.

We make some assumptions about the various system parameters.

This assumption is motivated by the fact that if $\kappa<c$, it is strictly sub-optimal to host the entire service at the edge, irrespective of the number of arrivals in a time-slot.

In [1, 2], it is shown that the benefits of partial hosting are limited to the setting where $\alpha_{i}+g(\alpha_{i})\leq 1$. Motivated by this, we consider the case where $\alpha_{i}+g(\alpha_{i})\leq 1$ for all candidate values of $\alpha_{i}$.

Assumption 3 follows from Assumptions 1 and 2

This assumption eliminates degenerate cases where there are no request arrivals in the time-horizon of interest.

The total cost incurred in time-slot $t$ by policy $\mathcal{P}$, denoted by $\mathcal{C}^{\mathcal{P}}_{t}(r_{t})$, is the sum of the rent, service, and fetch costs. It follows that,

Let $r=\{r_{t}\}_{t\geq 1}$ denote the request arrival sequence and $\mathcal{C}^{\mathcal{P}}(T,r)$ denote the cumulative cost incurred by policy $\mathcal{P}$ in time-slots 1 to $T$. It follows that,

Performance metrics: We consider two performance metrics, namely regret and competitive ratio.

For i.i.d. stochastic arrivals, the regret of a policy $\mathcal{P}$, denoted by $\mathcal{R}^{\mathcal{P}}_{S}(T)$, is defined as the difference in the total expected cost incurred by the policy and the oracle static hosting policy. The oracle static hosting policy makes a hosting decision at $t=1$ using the knowledge of the statistics of the request arrival process but not the entire sample-path. For ease of notation, we define $\mu={\mathbb{E}}[r_{t}]$, $\mu_{i}=c\alpha_{i}+g(\alpha_{i})\mu$. It follows that the expected cost incurred by the optimal static hosting policy in time-slots 1 to $T$ is $\min_{i}\{c\alpha_{i}T+g(\alpha_{i})\mu T+M\alpha_{i}\}$, and therefore,

where ${\mathbb{E}}_{\mathcal{P},r}$ represents the expectation over the randomization in policy $\mathcal{P}$ and the request arrival sequences $r$.

For i.i.d. stochastic arrivals, the competitive ratio of a policy $\mathcal{P}$, denoted by $\sigma^{\mathcal{P}}_{S}(T)$, is defined as the ratio of the expected total cost incurred by the policy and expected total cost incurred by the optimal static hosting policy as discussed above. It follows that,

For adversarial arrivals, the regret of a policy $\mathcal{P}$, denoted by $\mathcal{R}^{\mathcal{P}}_{A}(T)$, is defined as the worst case difference in the total expected cost incurred by the policy and the optimal static hosting policy. The expectation is taken over the randomization in policy $\mathcal{P}$. It follows that for any request sequence $r$, the total cost incurred by the optimal static hosting policy in time-slots 1 to $T$ is $\min_{i}\{c\alpha_{i}T+g(\alpha_{i})R_{T}+M\alpha_{i}\}$, and therefore,

We have the following relation between the regret induced by a policy under i.i.d stochastic arrivals and adversarial arrivals.

The proof can be found in Section 7.

For adversarial arrivals, the competitive ratio of a policy $\mathcal{P}$, denoted by $\sigma^{\mathcal{P}}_{A}(T)$, is defined as the worst case ratio of the expected total cost incurred by the policy and the cost incurred by the offline optimal policy. The optimal offline policy can change the hosting status over time using the knowledge of the entire request process a priori. Let the cost incurred by the optimal offline hosting policy in time-slots 1 to $T$ be denoted by $\mathcal{C}^{\text{OFF-OPT}}(T,r)$. It follows that,

Goal: The goal is to design online hosting policies with provable performance guarantees with respect to regret and competitive ratio.

Notations: We define some notations which will be used in the rest of this paper. Let $\bm{s}=[0,\alpha_{2},\alpha_{3},\cdots,1]^{\prime}$, $\bm{f}=[1,g(\alpha_{2}),g(\alpha_{3}),\cdots,0]^{\prime}$, and $\bm{\rho}_{t}^{\mathcal{P}}\in\mathcal{X}$, where $\mathcal{X}$ is the collection of all possible one hot vectors in $\{0,1\}^{K}$ and thus $|\mathcal{X}|=K$. The position of 1 in the one hot vector $\bm{\rho}_{t}^{\mathcal{P}}$ represents the level of service hosted at the edge in slot $t$, that is $\rho_{t}^{\mathcal{P}}=\langle\bm{\rho}_{t}^{\mathcal{P}},\mathbf{s}\rangle$. The total cost in slot $t$ as given in (1) can be rewritten using the above notations as follows,

where $\bm{\theta}_{t}=c\bm{s}+r_{t}\bm{f}$.

For ease of notation, for stochastic arrivals we define $\mu={\mathbb{E}}[r_{t}]$, $\mu_{i}=c\alpha_{i}+g(\alpha_{i})\mu$, $\Delta_{ij}=\mu_{i}-\mu_{j}$, $i^{\star}=\operatorname*{arg\,min}_{i}\mu_{i}$ , $\Delta_{i}=\mu_{i}-\mu_{i^{\star}}$, $\Delta_{\text{min}}=\min_{i}\Delta_{i}$, $\Delta_{\text{max}}=\max_{i}\Delta_{i}$.

We summarize important notations used in this paper in Table 1.

Our Policy: Our policy called Wait then Follow the Perturbed Leader (W-FTPL), is a variant of the popular FTPL policy. A formal definition of FTPL is given in Algorithm 1. FTPL is a randomized policy and is known to perform well for the traditional caching problem, in fact achieving order-wise optimal regret for adversarial arrivals [7]. Under FTPL, in any time slot $t$, for each $i$, FTPL considers the cumulative cost that would have been incurred had the system used $\alpha_{i}$ hosting fraction in the entire duration $[1,t-1]$, and then perturbs this by an appropriately scaled version of a sample of a standard Gaussian random variable. FTPL then hosts the fraction of service for which the perturbed cost is minimum in that slot.

We propose a policy called Wait then Follow The Perturbed Leader (W-FTPL). The key idea behind the W-FTPL policy is to not host the service for an initial wait period. This is to reduce the number of fetches made initially when the estimate of the arrivals is noisy. The duration of this wait period is not fixed apriori and is a function of the arrival pattern seen till that time. Following the wait period, W-FTPL mimics the FTPL policy. Refer to Algorithm 2 for a formal definition of W-FTPL. Let $T_{s}$ be the time slot, after which W-FTPL starts acting as FTPL. Formally we define $T_{s}=\min\{t:t<\frac{(\max_{i\neq j}(\Theta_{t+1,i}-\Theta_{t+1,j}))^{2}}{\kappa^{2}\beta(\log M)^{1+\delta}}\}$, where $\beta>1$, $\delta>0$ are constants.

Retro-Renting (RR) [3]: The RR policy is a deterministic hosting policy, and it either hosts the complete service or hosts nothing in a slot. The key idea behind this policy is to use recent arrival patterns to make hosting decisions. We refer the reader to Algorithm 1 in [3] for a formal definition of the RR policy. The performance of RR with respect to the competitive ratio was analyzed in [3].

$\alpha-$RR [2] is a variant of RR where one partial level of hosting the service is allowed. The formal definition of $\alpha-$RR, borrowed from [2, Algorithm 1] is given in Algorithm 3. Similar to RR, the key idea behind $\alpha-$RR policy is to check whether the current hosting status is optimal in the hindsight using recent arrival patterns to make hosting decisions. $\alpha-$RR checks the optimal offline policy cost for the recent request arrivals and chooses the fraction of service with the minimum cost. For $\rho_{t}^{\mathcal{P}}\in\{0,1\}$, $\alpha-$RR behaves as RR [2]. Therefore we refer $\alpha-$RR as RR in this paper.

In this section, we state and discuss our key results.

In this section, we compare RR, FTPL and W-FTPL policies via simulations using synthetic request sequences, as well as real trace data from [24]. In all our simulations, we consider $\eta_{t}=0.1\sqrt{t}$ for FTPL and W-FTPL, and $\beta=6$ for W-FTPL.