More Web Proxy on the site http://driver.im/

research-article

Public Access

Controlling the Variability of Capacity Allocations Using Service Deferrals

Authors:

Andres Ferragut,

Fernando Paganini,

Adam WiermanAuthors Info & Claims

ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Volume 2, Issue 3

Article No.: 15, Pages 1 - 27

https://doi.org/10.1145/3086506

Published: 08 August 2017 Publication History

Abstract

Ensuring predictability is a crucial goal for service systems. Traditionally, research has focused on designing systems that ensure predictable performance for service requests. Motivated by applications in cloud computing and electricity markets, this article focuses on a different form of predictability: predictable allocations of service capacity. The focus of the article is a new model where service capacity can be scaled dynamically and service deferrals (subject to deadline constraints) can be used to control the variability of the active service capacity. Four natural policies for the joint problem of scheduling and managing the active service capacity are considered. For each, the variability of service capacity and the likelihood of deadline misses are derived. Further, the paper illustrates how pricing can be used to provide incentives for jobs to reveal deadlines and thus enable the possibility of service deferral in systems where the flexibility of jobs is not known to the system a priori.

References

[1]

Muhammad A. Adnan and Rajesh K. Gupta. 2014. Workload shaping to mitigate variability in renewable power use by data centers. In Proceedings of the IEEE 7th International Conference on Cloud Computing. 96--103.

Digital Library

[2]

Muhammad A. Adnan, Ryo Sugihara, and Rajesh K. Gupta. 2012. Energy efficient geographical load balancing via dynamic deferral of workload. In Proceedings of the IEEE 5th International Conference on Cloud Computing (CLOUD’12). 188--195.

Digital Library

[3]

Philipp Afèche and Haim Mendelson. 2004. Pricing and priority auctions in queueing systems with a generalized delay cost structure. Manage. Sci. 50, 7 (2004), 869--882.

Digital Library

[4]

Phlippe Afèche and J. Michael Pavlin. 2016. Optimal price/lead-time menus for queues with customer choice: Segmentation, pooling, and strategic delay. Management Science 62, 8 (2016), 2412--2436.

[5]

Mustafa Akan, Baris Ata, and Tava Olsen. 2012. Congestion-based lead-time quotation for heterogenous customers with convex-concave delay costs: Optimality of a cost-balancing policy based on convex hull functions. Operat. Res. 60, 6 (2012), 1505--1519.

Digital Library

[6]

François Baccelli and Bartlomiej Błaszczyszyn. 2009. Stochastic Geometry and Wireless Networks, Volume I—Theory. Now Publishers.

Digital Library

[7]

Partha P. Bhattacharya and Anthony Ephremides. 1989. Optimal scheduling with strict deadlines. IEEE Trans. Automat. Control 34, 7 (1989), 721--728.

[8]

Federico Bliman, Andres Ferragut, and Fernando Paganini. 2015. Controlling aggregates of deferrable loads for power system regulation. In Proceedings of the 2015 American Control Conference, Chicago, IL.

[9]

Sem Borst, Onno Boxma, and Predrag Jelenkovic. 2000. Asymptotic behavior of generalized processor sharing with long-tailed traffic sources. In Proceedings of the IEEE/Infocom 2000, Vol. 2. IEEE, 912--921.

[10]

Onno Boxma and Bert Zwart. 2007. Tails in scheduling. ACM SIGMETRICS Perform. Eval. Rev. 34, 4 (2007), 13--20.

Digital Library

[11]

Sabri Çelik and Constantinos Maglaras. 2008. Dynamic pricing and lead-time quotation for a multiclass make-to-order queue. Manage. Sci. 54, 6 (2008), 1132--1146.

Digital Library

[12]

Niangjun Chen, Lingwen Gan, Steven H. Low, and Adam Wierman. 2014. Distributional analysis for model predictive deferrable load control. In Proceedings of the IEEE 53rd Annual Conference on Decision and Control.

[13]

Jeffrey Dean and Luiz André Barroso. 2013. The tail at scale. Commun. ACM 56, 2 (2013), 74--80.

Digital Library

[14]

Andres Ferragut and Fernando Paganini. 2015. Queueing analysis of service deferrals for load management in power systems. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control and Computing.

Digital Library

[15]

Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. 2005. Online convex optimization in the bandit setting: Gradient descent without a gradient. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 385--394.

Digital Library

[16]

Hans C. Gromoll and Łukasz Kruk. 2007. Heavy traffic limit for a processor sharing queue with soft deadlines. Ann. Appl. Probabil. 17, 3 (2007), 1049--1101.

[17]

Mor Harchol-Balter. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press.

Digital Library

[18]

Refael Hassin. 2016. Rational Queueing. CRC Press.

[19]

Refael Hassin and Moshe Haviv. 2003. To Queue or not to Queue: Equilibrium Behavior in Queueing Systems. Vol. 59. Springer Science 8 Business Media.

[20]

J. Hong, X. Tan, and D. Towsley. 1989. A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system. IEEE Trans. Comput. 38 (1989), 1736--1744.

Digital Library

[21]

Jack Kiefer and Jacob Wolfowitz. 1952. Stochastic estimation of the maximum of a regression function. The Ann. Math. Stat. 23, 3 (1952), 462--466.

[22]

Leonard Kleinrock. 1975. Queueing Systems, Volume I: Theory. Wiley Interscience.

[23]

John P. Lehoczky. 1997. Real-time queueing network theory. In Proceedings of the 18th IEEE Real-Time Systems Symposium. 58--67.

Digital Library

[24]

Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. 2013. Dynamic right-sizing for power-proportional data centers. IEEE/ACM Trans. Network. 21, 5 (2013), 1378--1391.

Digital Library

[25]

Zhenhua Liu, Minghong Lin, Adam Wierman, Steven H. Low, and Lachlan L. H. Andrew. 2011. Geographical load balancing with renewables. ACM SIGMETRICS Perform. Eval. Rev. 39, 3 (2011), 62--66.

Digital Library

[26]

Constantinos Maglaras and Jan A. Van Mieghem. 2005. Queueing systems with leadtime constraints: A fluid-model approach for admission and sequencing control. Eur. J. Operat. Res. 167, 1 (2005), 179--207.

[27]

Michel Mandjes and Bert Zwart. 2006. Large deviations of sojourn times in processor sharing queues. Queueing Syst. 52, 4 (2006), 237--250.

Digital Library

[28]

Haim Mendelson and Seungjin Whang. 1990. Optimal incentive-compatible priority pricing for the M/M/1 queue. Operat. Res. 38, 5 (1990), 870--883.

Digital Library

[29]

A. Nayyar, J. Taylor, A. Subramanian, K. Poolla, and P. Varaiya. 2013. Aggregate flexibility of a collection of loads. In Proceedings of the 52nd IEEE Conference on Decision and Control.

[30]

Misja Nuyens, Adam Wierman, and Bert Zwart. 2008. Preventing large sojourn times using SMART scheduling. Operat. Res. 56, 1 (2008), 88--101.

Digital Library

[31]

Michael Pinedo. 1983. Stochastic scheduling with release dates and due dates. Operat. Res. 31, 3 (1983), 559--572.

Digital Library

[32]

Erica Plambeck, Sunil Kumar, and Michael J. Harrison. 2001. A multiclass queue in heavy traffic with throughput time constraints: Asymptotically optimal dynamic controls. Queueing Syst. 39, 1 (2001), 23--54.

Digital Library

[33]

Casey Quinn, Daniel Zimmerle, and Thomas H. Bradley. 2010. The effect of communication architecture on the availability, reliability, and economics of plug-in hybrid electric vehicle-to-grid ancillary services. J. Power Sources 195, 5 (2010), 1500--1509.

[34]

Philippe Robert. 2003. Stochastic Networks and Queues. Springer.

[35]

Eric Sortomme and Mohamed A. El-Sharkawi. 2012. Optimal scheduling of vehicle-to-grid energy and ancillary services. IEEE Trans. Smart Grid 3, 1 (2012), 351--359.

[36]

A. Subramanian, M. J. Garcia, D. S. Callaway, K. Poolla, and P. Varaiya. 2013. Real-time scheduling of distributed resources. IEEE Trans. Smart Grid 4 (2013), 2122--2130.

[37]

Jasna Tomić and Willett Kempton. 2007. Using fleets of electric-drive vehicles for grid support. J. Power Sources 168, 2 (2007), 459--468.

[38]

Luis M. Vaquero, Luis Rodero-Merino, and Rajkumar Buyya. 2011. Dynamically scaling applications in the cloud. ACM SIGCOMM Comput. Commun. Rev. 41, 1 (2011), 45--52.

Digital Library

[39]

Adam Wierman and Bert Zwart. 2012. Is tail-optimal scheduling possible? Operat. Res. 60, 5 (2012), 1249--1257.

Digital Library

[40]

Stan Zachary. 2007. A note on insensitivity in stochastic networks. J. Appl. Probabil. 44 (2007), 238--248.

[41]

Qian Zhu and Gagan Agrawal. 2010. Resource provisioning with budget constraints for adaptive applications in cloud environments. In Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. ACM, 304--307.

Digital Library

Cited By

Nakahira YFerragut AWierman A(2023)Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline SchedulerOperations Research10.1287/opre.2021.223271:2(433-470)Online publication date: Mar-2023
https://doi.org/10.1287/opre.2021.2232
Nakahira YFerragut AWierman A(2019)Minimal-Variance Distributed Deadline Scheduling in a Stationary EnvironmentACM SIGMETRICS Performance Evaluation Review10.1145/3308897.330892546:3(56-61)Online publication date: 25-Jan-2019
https://dl.acm.org/doi/10.1145/3308897.3308925
Nakahira YFerragut AWierman A(2019)Minimal-variance distributed scheduling under strict demands and deadlinesACM SIGMETRICS Performance Evaluation Review10.1145/3305218.330522446:2(12-14)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3305218.3305224

Index Terms

Controlling the Variability of Capacity Allocations Using Service Deferrals

Recommendations

Registry and Discovery of Services with Variability Based on 2-Level UDDI
ISPAW '11: Proceedings of the 2011 IEEE Ninth International Symposium on Parallel and Distributed Processing with Applications Workshops

Through the introduction of SOA(Service Oriented Architecture), enterprises have recently had the benefit of legacy software reuse, heterogeneous environment integration, and ROI(Return On Investment) maximization. SOA consists of a service client, ...
Modeling and managing variability in process-based service compositions
ICSOC'11: Proceedings of the 9th international conference on Service-Oriented Computing

Variability in process-based service compositions needs to be explicitly modeled and managed in order to facilitate service/process customization and increase reuse in service/process development. While related work has been able to capture variability ...
Managing service variability: state of the art and open issues
VaMoS '11: Proceedings of the 5th International Workshop on Variability Modeling of Software-Intensive Systems

In addition to inherited characteristics from software variability, service variability exposes two distinct characteristics that impose certain challenges in variability management. These characteristics are: i) Different types of variability and their ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Performance Evaluation of Computing Systems

ACM Transactions on Modeling and Performance Evaluation of Computing Systems Volume 2, Issue 3

September 2017

135 pages

ISSN:2376-3639

EISSN:2376-3647

DOI:10.1145/3119902

Editors:
Sem Borst
Nokia Bell Labs / Eindhoven University of Technology, Netherlands
,
Carey Williamson
University of Calgary, Canada

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 August 2017

Accepted: 01 April 2017

Received: 01 November 2016

Published in TOMPECS Volume 2, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

IADB—Ministerio de Industria y Eneríga—Uruguay ATN/KF 13883 UR (Component 3)
NSF/DHS/DOT/NASA/NIH Cyber-Physical Systems Program
NSF
ANII—Uruguay

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
169
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)3

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nakahira YFerragut AWierman A(2023)Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline SchedulerOperations Research10.1287/opre.2021.223271:2(433-470)Online publication date: Mar-2023
https://doi.org/10.1287/opre.2021.2232
Nakahira YFerragut AWierman A(2019)Minimal-Variance Distributed Deadline Scheduling in a Stationary EnvironmentACM SIGMETRICS Performance Evaluation Review10.1145/3308897.330892546:3(56-61)Online publication date: 25-Jan-2019
https://dl.acm.org/doi/10.1145/3308897.3308925
Nakahira YFerragut AWierman A(2019)Minimal-variance distributed scheduling under strict demands and deadlinesACM SIGMETRICS Performance Evaluation Review10.1145/3305218.330522446:2(12-14)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3305218.3305224

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents