{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:45Z","timestamp":1750309125400,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T00:00:00Z","timestamp":1698192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SERB MATRICS"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>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 that 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 \u03b1-RetroRenting (\u03b1-RR) that 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 \u03b1-RR\u2019s 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 \u03b1-RR with various benchmarks for synthetic and trace-based request arrival and rent cost processes and find several parameter regimes where \u03b1-RR\u2019s ability to store the service partially greatly improves cost-efficiency.<\/jats:p>","DOI":"10.1145\/3616866","type":"journal-article","created":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T14:39:53Z","timestamp":1692801593000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Partial Service Hosting at the Edge"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1067-4610","authenticated-orcid":false,"given":"V. S. Ch Lakshmi Narayana","family":"Borusu","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8823-5810","authenticated-orcid":false,"given":"Mohit","family":"Agarwala","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7761-4877","authenticated-orcid":false,"given":"Sri Prakash","family":"R","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7233-0717","authenticated-orcid":false,"given":"Nikhil","family":"Karamchandani","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9393-9276","authenticated-orcid":false,"given":"Sharayu","family":"Moharir","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, IIT Bombay"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,25]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"2021. Retrieved from https:\/\/github.com\/mohit-iitb\/mapDataCaching"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2021.3052139"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2020.2988386"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.IR.8318"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_3_3_8_2","first-page":"1","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201910)","author":"Borst Sem","year":"2010","unstructured":"Sem Borst, Varun Gupta, and Anwar Walid. 2010. Distributed caching algorithms for content distribution networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201910). IEEE, 1\u20139."},{"key":"e_1_3_3_9_2","volume-title":"Time Series Analysis: Forecasting and Control","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."},{"key":"e_1_3_3_10_2","first-page":"126","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201999)","volume":"1","author":"Breslau Lee","year":"1999","unstructured":"Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. 1999. Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201999), Vol. 1. IEEE, 126\u2013134."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2019.2945956"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2019.2933781"},{"key":"e_1_3_3_13_2","first-page":"1","volume-title":"Proceedings of the IEEE 31st Annual International Symposium on Personal, Indoor and Mobile Radio Communications","author":"He Wen","unstructured":"Wen He, Dazhi He, Yihang Huang, Yizhe Zhang, Yin Xu, Guan Yun-feng, and Wenjun Zhang. 2020. Bandit learning-based service placement and resource allocation for mobile edge computing. In Proceedings of the IEEE 31st Annual International Symposium on Personal, Indoor and Mobile Radio Communications. IEEE, 1\u20136."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.918081"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"V S Ch Lakshmi Narayana Mohit Agarwala Nikhil Karamchandani and Sharayu Moharir. 2021. Online partial service hosting at the edge. arXiv:2103.00555. Retrieved from https:\/\/arxiv.org\/abs\/2103.00555","DOI":"10.1109\/ICCCN52240.2021.9522218"},{"key":"e_1_3_3_16_2","first-page":"1","volume-title":"Proceedings of the 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT\u201920)","author":"Narayana V. S. Ch. Lakshmi","year":"2020","unstructured":"V. S. Ch. Lakshmi Narayana, S. Moharir, and N. Karamchandani. 2020. RetroRenting: An online policy for service caching at the edge. In Proceedings of the 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT\u201920). 1\u20138."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2068950"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2494232.2465551"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2682318"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2017.2745201"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3478433"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCN52240.2021.9522218"},{"key":"e_1_3_3_23_2","first-page":"514","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201919)","author":"Pasteris Stephen","year":"2019","unstructured":"Stephen Pasteris, Shiqiang Wang, Mark Herbster, and Ting He. 2019. Service placement with provable guarantees in heterogeneous edge computing systems. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201919). IEEE, 514\u2013522."},{"key":"e_1_3_3_24_2","first-page":"1","volume-title":"Proceedings of the 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT\u201920)","author":"Prakash Rudrabhotla Sri","year":"2020","unstructured":"Rudrabhotla Sri Prakash, Nikhil Karamchandani, Veeraruna Kavitha, and Sharayu Moharir. 2020. Partial service caching at the edge. In Proceedings of the 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT\u201920). 1\u20138."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3301443"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"issue":"2","key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/TNET.2012.2208199","article-title":"Optimal content placement for peer-to-peer video-on-demand systems","volume":"21","author":"Tan Bo","year":"2012","unstructured":"Bo Tan and Laurent Massouli\u00e9. 2012. Optimal content placement for peer-to-peer video-on-demand systems. IEEE\/ACM Trans. Netw. 21, 2 (2012), 566\u2013579.","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"e_1_3_3_28_2","article-title":"Asymptotically optimal online caching on multiple caches with relaying and bypassing","author":"Tan Haisheng","year":"2021","unstructured":"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 Trans. Netw. (2021).","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213872"},{"key":"e_1_3_3_30_2","unstructured":"Benji Visser. 2017. Retrieved from https:\/\/www.kaggle.com\/noqcks\/aws-spot-pricing-market"},{"key":"e_1_3_3_31_2","article-title":"Negative Association: Definition, Properties, and Applications","author":"Wajc David","year":"2017","unstructured":"David Wajc. 2017. Negative Association: Definition, Properties, and Applications. Retrieved from https:\/\/goo.gl\/j2ekqM","journal-title":"Retrieved from"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/IFIPNetworking.2015.7145316"},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/319151.319153","volume-title":"Proceedings of the ACM Symposium on Operating Systems Principles (SOSP\u201999)","author":"Wolman Alec","year":"1999","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 Symposium on Operating Systems Principles (SOSP\u201999). 16\u201331."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.3016344"},{"key":"e_1_3_3_35_2","article-title":"Learning augmented index policy for optimal service placement at the network edge","author":"Xiong Guojun","unstructured":"Guojun Xiong, Rahul Singh, and Jian Li. 2021. Learning augmented index policy for optimal service placement at the network edge. arXiv:2101.03641. Retrieved from https:\/\/arxiv.org\/abs\/2101.03641","journal-title":"arXiv:2101.03641"},{"key":"e_1_3_3_36_2","first-page":"207","volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOSOM\u201918)","author":"Xu Jie","year":"2018","unstructured":"Jie Xu, Lixing Chen, and Pan Zhou. 2018. Joint service caching and task offloading for mobile edge computing in dense networks. In Proceedings of the IEEE International Conference on Computer Communications (INFOSOM\u201918). IEEE, 207\u2013215."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2021.3059692"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2435781"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2018.2844919"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1409635.1409677"},{"issue":"2","key":"e_1_3_3_41_2","first-page":"32","article-title":"Geolife: A collaborative social networking service among user, location and trajectory.","volume":"33","author":"Zheng Yu","year":"2010","unstructured":"Yu Zheng, Xing Xie, Wei-Ying Ma, et\u00a0al. 2010. Geolife: A collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33, 2 (2010), 32\u201339.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526816"}],"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\/3616866","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3616866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:49:13Z","timestamp":1750286953000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3616866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,25]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3616866"],"URL":"https:\/\/doi.org\/10.1145\/3616866","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2023,10,25]]},"assertion":[{"value":"2022-01-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}