A New Approach to Capacity Scaling Augmented with Unreliable Machine Learning Predictions

References

• [1] Albers S, Fujiwara H (2007) Energy-efficient algorithms for flow time minimization. ACM Trans. Algorithms 3(4):49.Crossref, Google Scholar
• [2] Albers S, Müller F, Schmelzer S (2014) Speed scaling on parallel processors. Algorithmica 68(2):404–425.Crossref, Google Scholar
• [3] Anderson C, Karlin AR (1996) Two adaptive hybrid cache coherency protocols. Proc. Second Internat. Sympos. High-Performance Comput. Architecture (IEEE, Piscataway, NJ), 303–313.Google Scholar
• [4] Antoniadis A, Coester C, Elias M, Polak A, Simon B (2020) Online metric algorithms with untrusted predictions. Internat. Conf. Machine Learn. (PMLR), 345–355.Google Scholar
• [5] Ata B, Shneorson S (2006) Dynamic control of an M/M/1 service system with adjustable arrival and service rates. Management Sci. 52(11):1778–1791.Link, Google Scholar
• [6] Augustine J, Irani S, Swamy C (2004) Optimal power-down strategies. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 530–539.Google Scholar
• [7] Azar Y, Bartal Y, Feuerstein E, Fiat A, Leonardi S, Rosén A (1999) On capital investment. Algorithmica 25(1):22–36.Crossref, Google Scholar
• [8] Bamas E, Maggiori A, Rohwedder L, Svensson O (2020) Learning augmented energy minimization via speed scaling. Preprint, submitted October 22, https://arxiv.org/abs/2010.11629.Google Scholar
• [9] Bansal N, Chan HL, Pruhs K (2013) Speed scaling with an arbitrary power function. ACM Trans. Algorithms 9(2):1–14.Google Scholar
• [10] Barbu V, Precupanu T (2012) Convexity and Optimization in Banach Spaces (Springer Science & Business Media, New York).Crossref, Google Scholar
• [11] Barroso LA, Hölzle U (2007) The case for energy-proportional computing. Computer 40(12):33–37.Crossref, Google Scholar
• [12] Bodik P (2010) Automating datacenter operations using machine learning. PhD thesis, University of California, Berkeley, CA.Google Scholar
• [13] Boyar J, Favrholdt LM, Kudahl C, Larsen KS, Mikkelsen JW (2017) Online algorithms with advice: A survey. ACM Comput. Surveys 50(2):19.Google Scholar
• [14] Cortez E, Bonde A, Muzio A, Russinovich M, Fontoura M, Bianchini R (2017) Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. Proc. 26th Sympos. Operating Systems Principles, 153–167.Google Scholar
• [15] Damaschke P (2003) Nearly optimal strategies for special cases of on-line capital investment. Theoret. Comput. Sci. 302(1–3):35–44.Crossref, Google Scholar
• [16] Dayarathna M, Wen Y, Fan R (2015) Data center energy consumption modeling: A survey. IEEE Comm. Surveys Tutorials 18(1):732–794.Crossref, Google Scholar
• [17] Doytchinov B, Lehoczky J, Shreve S (2001) Real-time queues in heavy traffic with earliest-deadline-first queue discipline. Ann. Appl. Probab. 11(2):332–378.Crossref, Google Scholar
• [18] Facebook (2014) Making Facebook’s software infrastructure more energy efficient with Autoscale. Accessed February 1, 2021, https://engineering.fb.com/production-engineering/making-facebook-s-software-infrastructure-more-energy-efficient-with-autoscale/.Google Scholar
• [19] Galloway J, Smith K, Carver J (2012) An empirical study of power aware load balancing in local cloud architectures. 2012 Ninth Internat. Conf. Inform. Tech. New Generations (IEEE, Piscataway, NJ), 232–236.Google Scholar
• [20] Gandhi A, Doroudi S, Harchol-Balter M, Scheller-Wolf A (2013) Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward. Proc. ACM SIGMETRICS/Internat. Conf. Measurement Model. Comput. Systems (ACM, New York), 153–166.Google Scholar
• [21] Gandhi A, Dube P, Karve A, Kochut A, Zhang L (2014) Adaptive, model-driven autoscaling for cloud applications. 11th Internat. Conf. Autonomic Comput. (ICAC 14), 57–64.Google Scholar
• [22] Gandhi A, Gupta V, Harchol-Balter M, Kozuch MA (2010) Optimality analysis of energy-performance trade-off for server farm management. Performance Evaluation 67(11):1155–1171.Crossref, Google Scholar
• [23] Gandhi A, Harchol-Balter M, Raghunathan R, Kozuch MA (2012) Autoscale: Dynamic, robust capacity management for multi-tier data centers. ACM Trans. Comput. Systems 30(4):14.Crossref, Google Scholar
• [24] Gao J (2014) Machine learning applications for data center optimization. Working paper, Google Research, New York.Google Scholar
• [25] Goldman SA, Parwatikar J, Suri S (2000) Online scheduling with hard deadlines. J. Algorithms 34(2):370–389.Crossref, Google Scholar
• [26] Google (2016) Data centers get fit on efficiency. Accessed February 1, 2021, https://blog.google/outreach-initiatives/environment/data-centers-get-fit-on-efficiency/.Google Scholar
• [27] Hsu CY, Indyk P, Katabi D, Vakilian A (2019) Learning-based frequency estimation algorithms. Internat. Conf. Learn. Representations.Google Scholar
• [28] Irani S, Shukla S, Gupta R (2002) Competitive analysis of dynamic power management strategies for systems with multiple power saving states. Proc. 2002 Design Automation Test Europe Conf. Exhibition (IEEE, Piscataway, NJ), 117–123.Google Scholar
• [29] Jones N (2018) How to stop data centres from gobbling up the world’s electricity. Nature (September 12), Accessed February 1, 2021, https://www.nature.com/articles/d41586-018-06610-y.Google Scholar
• [30] Karlin AR, Kenyon C, Randall D (2001) Dynamic TCP acknowledgment and other stories about e/(e − 1). Proc. thirty-third annual ACM sympos. Theory comput. (ACM, New York), 502–509.Google Scholar
• [31] Karlin AR, Manasse MS, Rudolph L, Sleator DD (1988) Competitive snoopy caching. Algorithmica 3(1–4):79–119.Crossref, Google Scholar
• [32] Khanafer A, Kodialam M, Puttaswamy KP (2013) The constrained ski-rental problem and its application to online cloud cost optimization. 2013 Proc. IEEE INFOCOM (IEEE, Piscataway, NJ), 1492–1500.Google Scholar
• [33] Kumar R, Purohit M, Schild A, Svitkina Z, Vee E (2018) Semi-online bipartite matching. Preprint, submitted December 1, https://arxiv.org/abs/1812.00134v1.Google Scholar
• [34] Lassettre E, Coleman DW, Diao Y, Froehlich S, Hellerstein JL, Hsiung L, Mummert T, et al. (2003) Dynamic surge protection: An approach to handling unexpected workload surges with resource actions that have lead times. Internat. Workshop Distributed Systems Oper. Management (Springer), 82–92.Google Scholar
• [35] Lee R, Hajiesmaili MH, Li J (2019) Learning-assisted competitive algorithms for peak-aware energy scheduling. Preprint, submitted November 18, https://arxiv.org/abs/1911.07972.Google Scholar
• [36] Lin M, Wierman A, Andrew LL, Thereska E (2012) Dynamic right-sizing for power-proportional data centers. IEEE/ACM Trans. Networking 21(5):1378–1391.Crossref, Google Scholar
• [37] Lu T, Chen M, Andrew LL (2012) Simple and effective dynamic provisioning for power-proportional data centers. IEEE Trans. Parallel Distributed Systems 24(6):1161–1171.Crossref, Google Scholar
• [38] Lykouris T, Vassilvtiskii S (2021) Competitive caching with machine learned advice. J. ACM 68(4):1–25.Google Scholar
• [39] Maccio VJ, Down DG (2015) On optimal policies for energy-aware servers. Performance Evaluation 90:36–52.Crossref, Google Scholar
• [40] Mahdian M, Nazerzadeh H, Saberi A (2012) Online optimization with uncertain information. ACM Trans. Algorithms 8(1):2.Crossref, Google Scholar
• [41] Manmeet S, Maninder S, Sanmeet K (2019) TI-2016 DNS dataset. IEEE DataPort. Accessed January 4, 2021, https://ieee-dataport.org/documents/ti-2016-dns-dataset.Google Scholar
• [42] Mazzucco M, Dyachuk D (2012) Optimizing cloud providers revenues via energy efficient server allocation. Sustainable Comput. Informatics Systems 2(1):1–12.Crossref, Google Scholar
• [43] Mitzenmacher M (2018) A model for learned bloom filters and optimizing by sandwiching. 32nd Conf. Neural Inform. Processing Systems 31 (NeurIPS 2018), 464–473.Google Scholar
• [44] Mitzenmacher M (2019a) Scheduling with predictions and the price of misprediction. Preprint, submitted May 23, https://arxiv.org/abs/1902.00732.Google Scholar
• [45] Mitzenmacher M (2019b) The supermarket model with known and predicted service times. Preprint, submitted May 23, https://arxiv.org/abs/1905.12155v1.Google Scholar
• [46] Mukherjee D, Stolyar A (2019) Join idle queue with service elasticity: Large-scale asymptotics of a nonmonotone system. Stochastic Systems 9(4):338–358.Link, Google Scholar
• [47] Mukherjee D, Dhara S, Borst SC, van Leeuwaarden JSH (2017) Optimal service elasticity in large-scale distributed systems. Proc. ACM Measurement Anal. Comput. Systems 1(1):1–28.Google Scholar
• [48] Netflix (2013) Scryer: Netflix’s predictive auto scaling engine. Accessed February 1, 2021, https://netflixtechblog.com/scryer-netflixs-predictive-auto-scaling-engine-a3f8fc922270.Google Scholar
• [49] Purohit M, Svitkina Z, Kumar R (2018) Improving online algorithms via ml predictions. Adv. Neural Inform. Processing Systems 31 (NeurIPS 2018), 9661–9670.Google Scholar
• [50] Qi J, Du J, Siniscalchi SM, Ma X, Lee CH (2020) On mean absolute error for deep neural network based vector-to-vector regression. IEEE Signal Processing Lett. 27:1485–1489.Crossref, Google Scholar
• [51] Rong H, Zhang H, Xiao S, Li C, Hu C (2016) Optimizing energy consumption for data centers. Renewable Sustainable Energy Rev. 58(C):674–691.Crossref, Google Scholar
• [52] Rzadca K, Findeisen P, Swiderski J, Zych P, Broniek P, Kusmierek J, Nowak P, et al. (2020) Autopilot: Workload autoscaling at Google. Proc. Fifteenth Eur. Conf. Comput. Systems, 1–16.Google Scholar
• [53] Shehabi A, Smith S, Sartor D, Brown R, Herrlin M, Koomey J, Masanet E, Horner N, Azevedo I, Lintner W (2016) United States data center energy usage report. Technical report, Lawrence Berkeley National Laboratory, Berkeley, CA.Google Scholar
• [54] Sverdlik Y (2020) How Zoom, Netflix, and Dropbox are staying online during the pandemic. Accessed February 1, 2021, https://www.datacenterknowledge.com/uptime/how-zoom-netflix-and-dropbox-are-staying-online-during-pandemic.Google Scholar
• [55] Tirmazi M, Barker A, Deng N, Haque ME, Qin ZG, Hand S, Harchol-Balter M, Wilkes J (2020) Borg: The next generation. Proc. Fifteenth Eur. Conf. Comput. Systems, 1–14.Google Scholar
• [56] Urgaonkar B, Shenoy P, Chandra A, Goyal P (2005) Dynamic provisioning of multi-tier internet applications. Second Internat. Conf. Autonomic Comput. (ICAC’05) (IEEE, Piscataway, NJ), 217–228.Google Scholar
• [57] Wierman A, Andrew LL, Tang A (2009) Power-aware speed scaling in processor sharing systems. 2009 Proc. IEEE INFOCOM (IEEE, Piscataway, NJ), 2007–2015.Google Scholar