Renting Edge Computing
Resources for Service Hosting

Aadesh Madnaik
Sharayu Moharir
Nikhil Karamchandani

A. Madnaik et al.

Indian Institute of Technology Bombay, Mumbai, India

We consider the setting where a service is hosted on a third-party edge server deployed close to the users and a cloud server at a greater distance from the users. Due to the proximity of the edge servers to the users, requests can be served at the edge with low latency. However, as the computation resources at the edge are limited, some requests must be routed to the cloud for service and incur high latency. The system's overall performance depends on the rent cost incurred to use the edge server, the latency experienced by the users, and the cost incurred to change the amount of edge computation resources rented over time. The algorithmic challenge is to determine the amount of edge computation power to rent over time. We propose a deterministic online policy and characterize its performance for adversarial and stochastic i.i.d. request arrival processes. We also characterize a fundamental bound on the performance of any deterministic online policy. Further, we compare the performance of our policy with suitably modified versions of existing policies to conclude that our policy is robust to temporal changes in the intensity of request arrivals.

§ INTRODUCTION

§ SETTING

§ POLICIES

§ MAIN RESULTS AND DISCUSSION

§ SIMULATIONS

§ PROOF OUTLINES

In this section we outline the proofs of the results discussed in Section <ref>. The proof details are discussed in the Appendix.

§.§ Proof Outline for Theorem <ref> (a)

The time axis is partitioned into `frames'. Frame $i$ for $i \in \mathbb{Z}^+$ begins when OPT-OFF switches the state of the edge-server for the $2i^{\text{th}}$ time. The time interval before the first frame is denoted as Frame 0.

in 0,0.3,0.6,...,7.2
[] (,0) –  (+0.3,0);
[gray] (,-1mm) – (,1mm);

[<->,color=black] (0.15,14mm) –
node[above=0mm,pos=0.5]$i.a$ (2.25,14mm);
[<->,color=black] (2.25,14mm) –
node[above=0mm,pos=0.5]$i.b$ (4.05,14mm);
[<->,color=black] (4.05,14mm) –
node[above=0mm,pos=0.5]$i.c$ (5.55,14mm);
[<->,color=black] (5.55,14mm) –
node[above=0mm,pos=0.5]$i.d$ (6.75,14mm);

in 0.15,2.25,4.05,5.55,6.75
[gray] (,12mm) – (,16mm);

[gray] (7.2,-1mm) – (7.2,1mm);
[-latex] (0.15,10mm) – node[above=5mm] (0.15,0mm);
[-latex] (6.75,10mm) – node[above=5mm] (6.75,0mm);
[-latex] (4.05,0mm) – node[above=5mm] (4.05,10mm);
[-latex,color=red] (2.25,10mm) – node[above=5mm] (2.25,0mm);
[-latex,color=red] (5.55,0mm) – node[above=5mm] (5.55,10mm);

[<->,color=black] (0.3,-2mm) – node[below=0mm,pos=0.5]Frame
$i$ (6.9,-2mm);

[black] (0.3,-1mm) – (0.3,-3mm);
[black] (6.9,-1mm) – (6.9,-3mm);

[] at (7.75,-0.85) OPT-OFF;

[fill=black!] (0.25,-1) rectangle (4.15,-0.7);
[fill=white!40] (4.15,-1) rectangle (6.85,-0.7);
[] at (7.45,-1.4) BLTN;
[fill=white!40] (0.25,-1.5) rectangle (2.4,-1.2);
[fill=red!] (2.4,-1.5) rectangle (5.7,-1.2);
[fill=white!40] (5.7,-1.5) rectangle (6.85,-1.2);

Figure representing
switching by OPT-OFF and BLTN in the $i^{\text{th}}$ frame.

In figure <ref>, the downward arrows represent switches to state $S_H$, upward arrows indicate switches to state $S_L$.
We designate red and black arrows to the BLTN and OPT-OFF policies respectively.
The state of the system under policies OPT-OFF and BLTN have been indicated using the two bars below the time axis. The solid red and solid black portions represent the
intervals during which BLTN and OPT-OFF host the service in state $S_H$ respectively.

We use the properties of BLTN and OPT-OFF to show that each frame has the following structure (Figure <ref>):

– BLTN switches state back and forth exactly once.

– BLTN starts in state $S_L$.

– The switch to $S_H$ by BLTN in Frame $i$ is before OPT-OFF switches to state $S_L$ in Frame $i$.

– The switch to $S_L$ by BLTN in Frame $i$ is after OPT-OFF switches to $S_L$ in Frame $i$.

We note that both BLTN and OPT-OFF switch exactly once back and forth in a frame and therefore, the total switch cost under BLTN and OPT-OFF is identical for both policies.

From Lemma 5 of the Appendix, we have that after switching to state $S_H$, OPT-OFF hosts the service for at least $\frac{W}{\Delta \kappa-\Delta c}$ time-slots. Similarly, after switching to $S_L$, OPT-OFF hosts the service for at least $\frac{W}{\Delta c}$ (Lemma 6) time-slots.

Across subframes $i.b$ and $i.d$, the rent and service costs are the same for both the policies. However, the differences between the cumulative service and rent costs incurred by BLTN and OPT-OFF in subframes $i.a$ and $i.c$ are capped by $W + \Delta \kappa - \Delta c$ and $W + \Delta c$ respectively. Also, the total switch cost under both policies in a frame is the same. Using these results, we have that the total cost incurred by BLTN and OPT-OFF in a frame differs by at most $2W + \Delta \kappa$.

In case of the last frame, if OPT-OFF switches the service, the analysis is the same as that of the previous frame. Otherwise, we bound the ratio of the cost incurred by BLTN and cost incurred by OPT-OFF in the frame.

Combining the results for individual frames obtained earlier, the final result follows.

§.§ Proof Outline for Theorem <ref> (b)

All deterministic online policies can be partitioned into two subsets.
A policy that hosts the service in $S_H$ during the first time-slot is in the first subset. All other polices are in the second subset.

In either of the subset, for each policy we construct an arrival sequence and calculate the ratio of the cost of the deterministic online policy and an alternative policy. Following from the definition, this quantity is a lower-bound on the competitive ratio of the deterministic policy.

§.§ Proof Outline for Theorem <ref>

Through Lemma 15 of the Appendix, we identify a lower bound on the cost per time-slot incurred by any online policy.

First, we consider the case where $\Delta \mu > \Delta c$. Through Hoeffding's inequality [12], we upper bound the probability of the state being $S_L$ during time-slot $t$ under BLTN. Conditioned on being in state $S_H$ and not switching to $S_L$ in time-slot $t$, the expected cumulative cost incurred by BLTN  is at the most $c_H+\mathbb{E}[X_t - \min\{X_t, \kappa_H\}]$ and is upper bounded by $W + c_L + \mathbb{E}[X_t - \min\{X_t, \kappa_L\}]$ otherwise. The result follows.

Next, we consider the case where $\Delta \mu < \Delta c$. We upper bound the probability of the service being hosted in state $S_H$ in time-slot $t$ under BLTN through Hoeffding's inequality  [12].
Similarly, the result then follows by the fact that the expected total cost incurred by BLTN is no more than $c_L + \mathbb{E}[X_t - \min\{X_t, \kappa_L\}]$ and at the most $W + c_H + \mathbb{E}[X_t - \min\{X_t, \kappa_H\}]$ otherwise, conditioned on being in state $S_L$ and not switched to $S_H$ in time-slot $t$.

§ CONCLUSION

[1]
Abbas, N., Zhang, Y., Taherkordi, A., Skeie, T.: Mobile edge computing: A
survey. IEEE Internet of Things Journal  5(1),  450–465 (2018).

[2]
Ascigil, O., Tasiopoulos, A., Phan, T.K., Sourlas, V., Psaras, I., Pavlou, G.:
Resource provisioning and allocation in function-as-a-service edge-clouds.
IEEE Transactions on Services Computing  (2021)

[3]
AWS:  (2022), <https://aws.amazon.com>

[4]
Belady, L.A.: A study of replacement algorithms for a virtual-storage computer.
IBM Systems journal  5(2),  78–101 (1966)

[5]
Bhattacharjee, R., Banerjee, S., Sinha, A.: Fundamental limits on the regret of
online network-caching. Proceedings of the ACM on Measurement and Analysis of
Computing Systems  4(2),  1–31 (2020)

[6]
Bi, S., Huang, L., Zhang, Y.J.A.: Joint optimization of service caching
placement and computation offloading in mobile edge computing system. arXiv
preprint arXiv:1906.00711  (2019)

[7]
Borst, S., Gupta, V., Walid, A.: Distributed caching algorithms for content
distribution networks. In: 2010 Proceedings IEEE INFOCOM. pp. 1–9. IEEE

[8]
Chen, L., Xu, J.: Collaborative service caching for edge computing in dense
small cell networks. arXiv preprint arXiv:1709.08662  (2017)

[9]
Chen, L., Xu, J.: Budget-constrained edge service provisioning with demand
estimation via bandit learning. arXiv preprint arXiv:1903.09080  (2019)

[10]
Choi, H., Yu, H., Lee, E.: Latency-classification-based deadline-aware task
offloading algorithm in mobile edge computing environments. Applied Sciences
9(21),  4696 (2019)

[11]
Gilbert, E.N.: Capacity of a burst-noise channel. The Bell System Technical
Journal  39(5),  1253–1265 (1960).

[12]
Hoeffding, W.: Probability inequalities for sums of bounded random variables.
In: The Collected Works of Wassily Hoeffding, pp. 409–426. Springer (1994)

[13]
IBM:  (2022), <https://www.ibm.com/cloud/edge-computing>

[14]
Infrastructure, O.C.:  (2022),

[15]
Jiang, C., Gao, L., Wang, T., Luo, J., Hou, F.: On economic viability of mobile
edge caching. In: ICC 2020-2020 IEEE International Conference on
Communications (ICC). pp. 1–6. IEEE (2020)

[16]
Luo, Q., Hu, S., Li, C., Li, G., Shi, W.: Resource scheduling in edge
computing: A survey. IEEE Communications Surveys & Tutorials
23(4),  2131–2165 (2021). 10.1109/COMST.2021.3106401

[17]
Miao, Y., Hao, Y., Chen, M., Gharavi, H., Hwang, K.: Intelligent task caching
in edge cloud via bandit learning. IEEE Transactions on Network Science and
Engineering  8(1),  625–637 (2020)

[18]
Mouradian, C., Naboulsi, D., Yangui, S., Glitho, R.H., Morrow, M.J., Polakos,
P.A.: A comprehensive survey on fog computing: State-of-the-art and research
challenges. IEEE Communications Surveys & Tutorials  20(1),
416–464 (2017)

[19]
Mukhopadhyay, S., Sinha, A.: Online caching with optimal switching regret. In:
2021 IEEE International Symposium on Information Theory (ISIT). pp.
1546–1551. IEEE (2021)

[20]
Narayana, V.C.L., Agarwala, M., Karamchandani, N., Moharir, S.: Online partial
service hosting at the edge. In: 2021 International Conference on Computer
Communications and Networks (ICCCN). pp. 1–9. IEEE (2021)

[21]
Narayana, V.C.L., Moharir, S., Karamchandani, N.: On renting edge resources for
service hosting. ACM Transactions on Modeling and Performance Evaluation of
Computing Systems  6(2),  1–30 (2021)

[22]
Prakash, R.S., Karamchandani, N., Kavitha, V., Moharir, S.: Partial service
caching at the edge. In: 2020 18th International Symposium on Modeling and
Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT). pp. 1–8. IEEE

[23]
Puliafito, C., Mingozzi, E., Longo, F., Puliafito, A., Rana, O.: Fog computing
for the internet of things: A survey. ACM Trans. Internet Technol.
19(2),  18:1–18:41 (Apr 2019). 10.1145/3301443,

[24]
Satyanarayanan, M.: The emergence of edge computing. Computer  50(1),
30–39 (2017)

[25]
Shi, W., Cao, J., Zhang, Q., Li, Y., Xu, L.: Edge computing: Vision and
challenges. IEEE Internet of Things Journal  3(5),  637–646 (2016).

[26]
Tran, T.X., Chan, K., Pompili, D.: 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).
pp. 1–9. IEEE (2019)

[27]
Wang, S., Urgaonkar, R., Zafer, M., He, T., Chan, K., Leung, K.K.: Dynamic
service migration in mobile edge computing based on markov decision process.
IEEE/ACM Transactions on Networking  27(3),  1272–1288 (2019).

[28]
Yan, J., Bi, S., Duan, L., Zhang, Y.J.A.: Pricing-driven service caching and
task offloading in mobile edge computing. IEEE Transactions on Wireless
Communications  (2021)

[29]
Zeng, F., Chen, Y., Yao, L., Wu, J.: A novel reputation incentive mechanism and
game theory analysis for service caching in software-defined vehicle edge
computing. Peer-to-Peer Networking and Applications pp. 1–15 (2020)

[30]
Zhang, M., Zheng, Z., Shroff, N.B.: An online algorithm for power-proportional
data centers with switching cost. In: 2018 IEEE Conference on Decision and
Control (CDC). pp. 6025–6032 (2018). 10.1109/CDC.2018.8619443

[31]
Zhao, T., Hou, I.H., Wang, S., Chan, K.: Red/led: An asymptotically optimal and
scalable online algorithm for service caching at the edge. IEEE Journal on
Selected Areas in Communications  36(8),  1857–1870 (2018)

§ APPENDIX