{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T21:00:59Z","timestamp":1763499659440,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T00:00:00Z","timestamp":1614902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2021,3,5]]},"abstract":"<jats:p>We consider a distributed server system consisting of a large number of servers, each with limited capacity on multiple resources (CPU, memory, disk, etc.). Jobs with different rewards arrive over time and require certain amounts of resources for the duration of their service. When a job arrives, the system must decide whether to admit it or reject it, and if admitted, in which server to schedule the job. The objective is to maximize the expected total reward received by the system. This problem is motivated by control of cloud computing clusters, in which, jobs are requests for Virtual Machines or Containers that reserve resources for various services, and rewards represent service priority of requests or price paid per time unit of service by clients. We study this problem in an asymptotic regime where the number of servers and jobs' arrival rates scale by a factor L, as L becomes large. We propose a resource reservation policy that asymptotically achieves at least 1\/2, and under certain monotone property on jobs' rewards and resources, at least 11\/4 of the optimal expected reward. The policy automatically scales the number of VM slots for each job type as the demand changes, and decides in which servers the slots should be created in advance, without the knowledge of traffic rates. It effectively tracks a low-complexity greedy packing of existing jobs in the system while maintaining only a small number, g(L) = w(logL), of reserved VM slots for high priority jobs that pack well.<\/jats:p>","DOI":"10.1145\/3453953.3453958","type":"journal-article","created":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T04:12:32Z","timestamp":1615003952000},"page":"27-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Theory of Auto-Scaling for Resource Reservation in Cloud Services"],"prefix":"10.1145","volume":"48","author":[{"given":"Konstantinos","family":"Psychas","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javad","family":"Ghaderi","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"AWS","author":"Amazon","year":"2019","unstructured":"Amazon AWS 2019 . Amazon Web Services (AWS). https:\/\/aws.amazon.com\/ Amazon AWS 2019. Amazon Web Services (AWS). https:\/\/aws.amazon.com\/"},{"key":"e_1_2_1_2_1","unstructured":"AWS container 2019. Amazon AWS Containers. https:\/\/aws.amazon.com\/ containers\/  AWS container 2019. Amazon AWS Containers. https:\/\/aws.amazon.com\/ containers\/"},{"key":"e_1_2_1_3_1","volume-title":"SLA","author":"AWS","year":"2019","unstructured":"AWS SLA 2019 . Amazon AWS Service Level Agreements (SLAs). \/\/https:\/\/aws. amazon.com\/legal\/service-level-agreements\/ AWS SLA 2019. Amazon AWS Service Level Agreements (SLAs). \/\/https:\/\/aws. amazon.com\/legal\/service-level-agreements\/"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/1428107"},{"volume-title":"Probability and measure","author":"Billingsley Patrick","key":"e_1_2_1_5_1","unstructured":"Patrick Billingsley . 2008. Probability and measure . John Wiley & Sons . Patrick Billingsley. 2008. Probability and measure. John Wiley & Sons."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2012.05.012"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2667522.2667543"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2017.02.022"},{"key":"e_1_2_1_9_1","unstructured":"Google Cloud 2019. Google cloud computing services. https:\/\/cloud.google.com\/  Google Cloud 2019. Google cloud computing services. https:\/\/cloud.google.com\/"},{"key":"e_1_2_1_10_1","unstructured":"Google Kubernetes 2019. Kubernetes at Google Cloud. https:\/\/https:\/\/cloud. google.com\/kubernetes\/  Google Kubernetes 2019. Kubernetes at Google Cloud. https:\/\/https:\/\/cloud. google.com\/kubernetes\/"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2018.2830793"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2012.52"},{"key":"e_1_2_1_13_1","volume-title":"Large loss networks. Stochastic Processes and their Applications 53, 2","author":"Hunt PJ","year":"1994","unstructured":"PJ Hunt and TG Kurtz . 1994. Large loss networks. Stochastic Processes and their Applications 53, 2 ( 1994 ), 363--378. PJ Hunt and TG Kurtz. 1994. Large loss networks. Stochastic Processes and their Applications 53, 2 (1994), 363--378."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1043862424"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2013.73"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-016-9488-8"},{"volume-title":"Knapsack problems","author":"Kellerer Hans","key":"e_1_2_1_17_1","unstructured":"Hans Kellerer , Ulrich Pferschy , and David Pisinger . 2004. Multidimensional knapsack problems . In Knapsack problems . Springer , 235--283. Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Multidimensional knapsack problems. In Knapsack problems. Springer, 235--283."},{"key":"e_1_2_1_18_1","volume-title":"Loss networks. The annals of applied probability","author":"Kelly Frank P","year":"1991","unstructured":"Frank P Kelly . 1991. Loss networks. The annals of applied probability ( 1991 ), 319--378. Frank P Kelly. 1991. Loss networks. The annals of applied probability (1991), 319--378."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195815"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.08.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/GRID.2010.5697966"},{"key":"e_1_2_1_22_1","unstructured":"Microsoft Azure 2019. Microsoft cloud computing service. https:\/\/azure.microsoft. com\/  Microsoft Azure 2019. Microsoft cloud computing service. https:\/\/azure.microsoft. com\/"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.008"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154493"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2863647"},{"key":"e_1_2_1_26_1","volume-title":"A Theory of Auto-Scaling for Resource Reservation in Cloud Services. arXiv preprint arXiv:2005.13744","author":"Psychas Konstantinos","year":"2020","unstructured":"Konstantinos Psychas and Javad Ghaderi . 2020. A Theory of Auto-Scaling for Resource Reservation in Cloud Services. arXiv preprint arXiv:2005.13744 ( 2020 ). Konstantinos Psychas and Javad Ghaderi. 2020. A Theory of Auto-Scaling for Resource Reservation in Cloud Services. arXiv preprint arXiv:2005.13744 (2020)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3148149"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2014.24"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD.2011.42"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.148"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/apr.2016.79"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-014-9414-x"},{"key":"e_1_2_1_33_1","volume-title":"Blocking when service is required from several facilities simultaneously. AT&T technical journal 64, 8","author":"Whitt Ward","year":"1985","unstructured":"Ward Whitt . 1985. Blocking when service is required from several facilities simultaneously. AT&T technical journal 64, 8 ( 1985 ), 1807--1856. Ward Whitt. 1985. Blocking when service is required from several facilities simultaneously. AT&T technical journal 64, 8 (1985), 1807--1856."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745849"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453958","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453953.3453958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:51Z","timestamp":1750193271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453953.3453958"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,5]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3,5]]}},"alternative-id":["10.1145\/3453953.3453958"],"URL":"https:\/\/doi.org\/10.1145\/3453953.3453958","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2021,3,5]]},"assertion":[{"value":"2021-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}