Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency

References

• Abernethy J, Bartlett PL, Rakhlin A, Tewari A (2008) Optimal strategies and minimax lower bounds for online convex games. Accessed May 1, 2018, https://repository.upenn.edu/statistics_papers/164.Google Scholar
• Albers S (2003) Online algorithms: a survey. Math. Programming 97(1-2):3–26.Crossref, Google Scholar
• Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1):121–164.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2 (Siam, Philadelphia).Crossref, Google Scholar
• Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bubeck S, Cesa-Bianchi N, et al. (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations Trends® in Machine Learn. 5(1):1–122.Google Scholar
• Buchbinder N, Naor JS (2009) The Design of Competitive Online Algorithms via a Primal-Dual Approach (Now Publishers, Inc., Hanover, MA).Crossref, Google Scholar
• Cohen MC, Keller PW, Mirrokni V, Zadimoghaddam M (2019) Overcommitment in cloud services: Bin packing with chance constraints. Management Sci. 65(7):2947–3448.Google Scholar
• Curino C, Difallah DE, Douglas C, Krishnan S, Ramakrishnan R, Rao S (2014) Reservation-based scheduling: If you’re late don’t blame us! Proc. ACM Symposium Cloud Comput. (ACM), 1–14.Google Scholar
• Dabbagh M, Hamdaoui B, Guizani M, Rayes A (2015) Efficient datacenter resource utilization through cloud resource overcommitment. 2015 IEEE Conf. Comput. Comm. Workshops (INFOCOM WKSHPS) (IEEE), 330–335.Google Scholar
• Feller W (1957) An Introduction to Probability Theory and Its Applications (John Wiley & Sons, New York).Google Scholar
• Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. System Sci. 55(1):119–139.Crossref, Google Scholar
• Gera A, Xia CH (2011) Learning curves and stochastic models for pricing and provisioning cloud computing services. Service Sci. 3(1):99–109.Link, Google Scholar
• Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. NSDI 11:24.Google Scholar
• Gordon A, Hines M, Da Silva D, Ben-Yehuda M, Silva M, Lizarraga G (2011) Ginkgo: Automated, application-driven memory overcommitment for cloud computing. ASPLOS RESoLVE Workshop, 1–6.Google Scholar
• Grandl R, Chowdhury M, Akella A, Ananthanarayanan G (2016) Altruistic scheduling in multi-resource clusters. OSDI, 65–80.Google Scholar
• Hall EC, Willett RM (2015) Online convex optimization in dynamic environments. IEEE J. Sel. Top. Signal Process. 9(4):647–662.Crossref, Google Scholar
• Hazan E (2019) Introduction to online convex optimization. Preprint, submitted September 7, https://arxiv.org/abs/1909.05207Google Scholar
• Hindman B, Konwinski A, Zaharia M, Ghodsi A, Joseph AD, Katz RH, Shenker S, Stoica I (2011) Mesos: A platform for fine-grained resource sharing in the data center. NSDI 11:22.Google Scholar
• Jyothi SA, Curino C, Menache I, Narayanamurthy SM, Tumanov A, Yaniv J, Mavlyutov R, et al. (2016) Morpheus: Toward automated slos for enterprise clusters. OSDI, 117–134.Google Scholar
• Li Cp, Neely MJ (2009) Energy-optimal scheduling with dynamic channel acquisition in wireless downlinks. IEEE Trans. Mobile Comput. 9(4):527–539.Google Scholar
• Macías M, Guitart J (2011) A genetic model for pricing in cloud computing markets. Proc. 2011 ACM Symposium Appl. Comput. (ACM), 113–118.Google Scholar
• Maguluri ST, Srikant R (2014) Scheduling jobs with unknown duration in clouds. IEEE/ACM Trans. Networking 22(6):1938–1951.Crossref, Google Scholar
• Maguluri ST, Srikant R, Ying L (2012) Stochastic models of load balancing and scheduling in cloud computing clusters. Proc. IEEE INFOCOM (IEEE), 702–710.Crossref, Google Scholar
• Maguluri ST, Srikant R, Ying L (2014) Heavy traffic optimal resource allocation algorithms for cloud computing clusters. Performance Evaluation 81:20–39.Crossref, Google Scholar
• Menache I, Singh M (2015) Online caching with convex costs. Proc. 27th ACM Symposium Parallelism Algorithms Architectures (ACM), 46–54.Google Scholar
• Mohri M, Rostamizadeh A, Talwalkar A (2018) Foundations of Machine Learning (MIT Press, Cambridge, MA).Google Scholar
• Mokhtari A, Shahrampour S, Jadbabaie A, Ribeiro A (2016) Online optimiziation in dynamic environments: improved regret rates for strongly convex problems. Decision Control (CDC), 2016 IEEE 55th Conf., (IEEE) 7195–7201.Google Scholar
• Narasayya V, Das S, Syamala M, Chandramouli B, Chaudhuri S (2013) SQLVM: performance isolation in multi-tenant relational database-as-a-service. 6th Biennial Conf. Innovative Data Systems Res.Google Scholar
• Narasayya V, Menache I, Singh M, Li F, Syamala M, Chaudhuri S (2015) Sharing buffer pool memory in multi-tenant relational database-as-a-service. Proc. VLDB Endowment 8(7):726–737.Crossref, Google Scholar
• Neely MJ (2007) Optimal energy and delay tradeoffs for multiuser wireless downlinks. IEEE Trans. Inform. Theory 53(9):3095–3113.Crossref, Google Scholar
• Neely MJ (2008) Order optimal delay for opportunistic scheduling in multi-user wireless uplinks and downlinks. IEEE/ACM Trans. Networking 16(5):1188–1199.Crossref, Google Scholar
• Passacantando M, Ardagna D, Savi A (2016) Service provisioning problem in cloud and multi-cloud systems. INFORMS J. Comput. 28(2):265–277.Link, Google Scholar
• Plotkin SA, Shmoys DB, Tardos É (1995) Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2):257–301.Link, Google Scholar
• Rasley J, Karanasos K, Kandula S, Fonseca R, Vojnovic M, Rao S (2016) Efficient queue management for cluster scheduling. Proc. Eleventh Eur. Conf. Comput. Systems (ACM), 36.Google Scholar
• Shalev-Shwartz S (2012) Online learning and online convex optimization. Foundations Trends® Machine Learn. 4(2):107–194.Crossref, Google Scholar
• Sharma B, Thulasiram RK, Thulasiraman P, Garg SK, Buyya R (2012) Pricing cloud compute commodities: A novel financial economic model. Proc. 2012 12th IEEE/ACM Internat. Symposium Cluster, Cloud Grid Comput. (ccgrid 2012) (IEEE Computer Society), 451–457.Google Scholar
• Shirani-Mehr H, Caire G, Neely MJ (2010) Mimo downlink scheduling with non-perfect channel state knowledge. IEEE Trans. Comm. 58(7):2055–2066.Crossref, Google Scholar
• Srikant R, Ying L (2013) Communication networks: an optimization, control, and stochastic networks perspective (Cambridge University Press, Cambridge, MA).Crossref, Google Scholar
• Tassiulas L, Ephremides A (1990) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. 29th IEEE Conf. Decision Control (IEEE), 2130–2132.Google Scholar
• Tassiulas L, Ephremides A (1993) Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Inform. Theory 39(2):466–478.Crossref, Google Scholar
• Vavilapalli VK, Murthy AC, Douglas C, Agarwal S, Konar M, Evans R, Graves T, et al. (2013) Apache hadoop yarn: Yet another resource negotiator. Proc. 4th Annual Symposium Cloud Comput. (ACM), 5.Google Scholar
• Zaharia M, Borthakur D, Sen Sarma J, Elmeleegy K, Shenker S, Stoica I (2010) Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling. Proc. 5th Eur. Conf. Comput. Systems (ACM), 265–278.Google Scholar
• Zhang L, Yang T, Yi J, Rong J, Zhou ZH (2017) Improved dynamic regret for non-degenerate functions. Neural Information Processing Systems.Google Scholar
• Zinkevich M (2003) Online convex programming and generalized infinitesimal gradient ascent. Proc. 20th Internat. Conf. Machine Learn. (ICML-03), 928–936.Google Scholar