{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T15:26:55Z","timestamp":1759073215079,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001843","name":"SERB","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>The rapid proliferation of shared edge computing platforms has enabled application service providers to deploy a wide variety of services with stringent latency and high bandwidth requirements. A key advantage of these platforms is that they provide pay-as-you-go flexibility by charging clients in proportion to their resource usage through short-term contracts. This affords the client significant cost-saving opportunities by dynamically deciding when to host its service on the platform, depending on the changing intensity of requests. A natural policy for our setting is the Time-To-Live (TTL) policy. We show that TTL performs poorly both in the adversarial arrival setting, i.e., in terms of the competitive ratio, and for i.i.d. stochastic arrivals with low arrival rates, irrespective of the value of the TTL timer. We propose an online policy called RetroRenting (RR) and characterize its performance in terms of the competitive ratio. Our results show that RR overcomes the limitations of TTL. In addition, we provide performance guarantees for RR for i.i.d. stochastic arrival processes coupled with negatively associated rent cost sequences and prove that it compares well with the optimal online policy. Further, we conduct simulations using both synthetic and real-world traces to compare the performance of RR with the optimal offline and online policies. The simulations show that the performance of RR is near optimal for all settings considered. Our results illustrate the universality of RR.<\/jats:p>","DOI":"10.1145\/3478433","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T00:41:47Z","timestamp":1633394507000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["On Renting Edge Resources for Service Hosting"],"prefix":"10.1145","volume":"6","author":[{"given":"V.S. Ch Lakshmi","family":"Narayana","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharayu","family":"Moharir","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Karamchandani","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2021.3052139"},{"key":"e_1_2_1_2_1","unstructured":"AWS. 2020. https:\/\/aws.amazon.com.  AWS. 2020. https:\/\/aws.amazon.com."},{"key":"e_1_2_1_3_1","unstructured":"Azure. 2020. https:\/\/azure.microsoft.com.  Azure. 2020. https:\/\/azure.microsoft.com."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_5_1","volume-title":"Joint optimization of service caching placement and computation offloading in mobile edge computing system. arXiv preprint arXiv:1906.00711","author":"Bi Suzhi","year":"2019","unstructured":"Suzhi Bi , Liang Huang , and Ying-Jun Angela Zhang . 2019. Joint optimization of service caching placement and computation offloading in mobile edge computing system. arXiv preprint arXiv:1906.00711 ( 2019 ). Suzhi Bi, Liang Huang, and Ying-Jun Angela Zhang. 2019. Joint optimization of service caching placement and computation offloading in mobile edge computing system. arXiv preprint arXiv:1906.00711 (2019)."},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_6_1","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5461964"},{"key":"e_1_2_1_9_1","volume-title":"Reinsel","author":"Box George E.P.","year":"2011","unstructured":"George E.P. Box , Gwilym M. Jenkins , and Gregory C . Reinsel . 2011 . Time Series Analysis: Forecasting and Control. Vol. 734 . John Wiley & Sons . George E.P. Box, Gwilym M. Jenkins, and Gregory C. Reinsel. 2011. Time Series Analysis: Forecasting and Control. Vol. 734. John Wiley & Sons."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1999.749260"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737546"},{"key":"e_1_2_1_12_1","volume-title":"Collaborative service caching for edge computing in dense small cell networks. arXiv preprint arXiv:1709.08662","author":"Chen Lixing","year":"2017","unstructured":"Lixing Chen and Jie Xu. 2017. Collaborative service caching for edge computing in dense small cell networks. arXiv preprint arXiv:1709.08662 ( 2017 ). Lixing Chen and Jie Xu. 2017. Collaborative service caching for edge computing in dense small cell networks. arXiv preprint arXiv:1709.08662 (2017)."},{"key":"e_1_2_1_13_1","volume-title":"Budget-constrained edge service provisioning with demand estimation via bandit learning. arXiv preprint arXiv:1903.09080","author":"Chen Lixing","year":"2019","unstructured":"Lixing Chen and Jie Xu. 2019. Budget-constrained edge service provisioning with demand estimation via bandit learning. arXiv preprint arXiv:1903.09080 ( 2019 ). Lixing Chen and Jie Xu. 2019. Budget-constrained edge service provisioning with demand estimation via bandit learning. arXiv preprint arXiv:1903.09080 (2019)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3390\/app9214696"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2012.05.023"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132211.3134453"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2020.3022692"},{"key":"e_1_2_1_18_1","unstructured":"Joseph L. Hellerstein. 2010. Google Cluster Data: Google AI blog.  Joseph L. Hellerstein. 2010. Google Cluster Data: Google AI blog."},{"volume-title":"The Collected Works of Wassily Hoeffding","author":"Hoeffding Wassily","key":"e_1_2_1_19_1","unstructured":"Wassily Hoeffding . 1994. Probability inequalities for sums of bounded random variables . In The Collected Works of Wassily Hoeffding . Springer , 409\u2013426. Wassily Hoeffding. 1994. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding. Springer, 409\u2013426."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC40277.2020.9149120"},{"key":"e_1_2_1_21_1","unstructured":"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  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"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/comst.2017.2682318"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2745201"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2020.3047417"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2771153"},{"key":"e_1_2_1_26_1","volume-title":"2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT\u201920)","author":"Ch Lakshmi Narayana V. S.","year":"2020","unstructured":"V. S. Ch Lakshmi Narayana , Sharayu Moharir , and Nikhil 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\u201920) . IEEE, 1\u20138. V. S. Ch Lakshmi Narayana, Sharayu Moharir, and Nikhil 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\u201920). IEEE, 1\u20138."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737449"},{"key":"e_1_2_1_28_1","article-title":"Fog computing for the internet of things: A survey","volume":"19","author":"Puliafito Carlo","year":"2019","unstructured":"Carlo Puliafito , Enzo Mingozzi , Francesco Longo , Antonio Puliafito , and Omer Rana . 2019 . Fog computing for the internet of things: A survey . ACM Transactions on Internet Technologies 19 , 2, Article 18 (April 2019), 41 pages. https:\/\/doi.org\/10.1145\/3301443 10.1145\/3301443 Carlo Puliafito, Enzo Mingozzi, Francesco Longo, Antonio Puliafito, and Omer Rana. 2019. Fog computing for the internet of things: A survey. ACM Transactions on Internet Technologies 19, 2, Article 18 (April 2019), 41 pages. https:\/\/doi.org\/10.1145\/3301443","journal-title":"ACM Transactions on Internet Technologies"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.07.069"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2017.9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2208199"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAHCN.2019.8824854"},{"key":"e_1_2_1_34_1","unstructured":"Benji Visser. 2017. AWS Spot Pricing Market Dataset. https:\/\/www.kaggle.com\/noqcks\/aws-spot-pricing-market.  Benji Visser. 2017. AWS Spot Pricing Market Dataset. https:\/\/www.kaggle.com\/noqcks\/aws-spot-pricing-market."},{"key":"e_1_2_1_35_1","unstructured":"David Wajc. 2017. Negative association: Definition properties and applications. Manuscript available from https:\/\/goo. gl\/j2ekqM. (2017).  David Wajc. 2017. Negative association: Definition properties and applications. Manuscript available from https:\/\/goo. gl\/j2ekqM. (2017)."},{"volume-title":"2015 IFIP Networking Conference (IFIP Networking\u201915)","author":"Wang Shiqiang","key":"e_1_2_1_36_1","unstructured":"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\u201915) . IEEE, 1\u20139. 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\u201915). IEEE, 1\u20139."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.3390\/s20030610"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2645892.2645901"},{"volume-title":"Proceedings of the ACM SOSP. 16\u201331","author":"Wolman Alec","key":"e_1_2_1_39_1","unstructured":"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 Proceedings of the ACM SOSP. 16\u201331 . 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 Proceedings of the ACM SOSP. 16\u201331."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485977"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM41043.2020.9155365"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2021.3059692"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2435781"},{"key":"e_1_2_1_44_1","first-page":"1","article-title":"A novel reputation incentive mechanism and game theory analysis for service caching in software-defined vehicle edge computing","volume":"8","author":"Zeng Feng","year":"2020","unstructured":"Feng Zeng , Yaojia Chen , Lan Yao , and Jinsong Wu . 2020 . A novel reputation incentive mechanism and game theory analysis for service caching in software-defined vehicle edge computing . Peer-to-Peer Networking and Applications 8 (2020), 1 \u2013 15 . Feng Zeng, Yaojia Chen, Lan Yao, and Jinsong Wu. 2020. A novel reputation incentive mechanism and game theory analysis for service caching in software-defined vehicle edge computing. Peer-to-Peer Networking and Applications 8 (2020), 1\u201315.","journal-title":"Peer-to-Peer Networking and Applications"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3010329"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2018.2844919"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478433","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3478433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:11:48Z","timestamp":1750191108000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3478433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3478433"],"URL":"https:\/\/doi.org\/10.1145\/3478433","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}