research-article

Optimal Capacity Provisioning for Online Job Allocation With Hard Allocation Ratio Requirement

Authors:

Han DengAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 26, Issue 2

Pages 724 - 736

https://doi.org/10.1109/TNET.2018.2794394

Published: 01 April 2018 Publication History

Abstract

The problem of allocating jobs to appropriate servers in cloud computing is studied in this paper. We consider that the jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. In order to meet the hard allocation ratio requirement in the presence of unknown arrival patterns, one can increase the capacity of servers by expanding the size of data centers. We then aim to find the minimum capacity needed to meet a given allocation ratio requirement. We study this problem for both systems with persistent jobs, such as video streaming, and systems with dynamic jobs, such as database queries. For both systems, we propose online job allocation policies with low complexity. For systems with persistent jobs, we prove that our policies can achieve a given hard allocation ratio requirement with the least capacity. For systems with dynamic jobs, the capacity needed for our policies to achieve the hard allocation ratio requirement is close to a theoretical lower bound. Two other popular policies are studied, and we demonstrate that they need at least an order higher capacity to meet the same hard allocation ratio requirement. Simulation results demonstrate that our policies remain far superior than the other two even, when the jobs arrive according to some random process.

References

[1]

H. Deng and I.-H. Hou, "Online job allocation with hard allocation ratio requirement," in Proc. IEEE INFOCOM 35th Annu., IEEE Int. Conf. Comput. Commun., Apr. 2016, pp. 1-9.

[2]

H. Yu, D. Zheng, B. Y. Zhao, and W. Zheng, "Understanding user behavior in large-scale video-on-demand systems," in Proc. 1st ACM SIGOPS/EuroSys Eur. Conf. Comput. Syst. (EuroSys), 2006, pp. 333-344.

Digital Library

[3]

S. Acharya, B. P. Smith, and P. Parnes, "Characterizing user access to videos on the World Wide Web," in Proc. IS&T/SPIE Conf. Multimedia Comput. Netw., 1999, pp. 130-141.

[4]

C. Huang, J. Li, and K. W. Ross, "Can Internet video-on-demand be profitable?" ACM SIGCOMM Comput. Commun. Rev., vol. 37, no. 4, pp. 133-144, 2007.

Digital Library

[5]

X. Cheng, C. Dale, and J. Liu, "Statistics and social network of YouTube videos," in Proc. 16th Int. Workshop Quality Service (IWQoS), Jun. 2008, pp. 229-238.

[6]

G. Chatzopoulou, C. Sheng, and M. Faloutsos, "A first step towards understanding popularity in YouTube," in Proc. IEEE Conf. Comput. Commun. Workshop, Mar. 2010, pp. 1-6.

[7]

R. M. Karp, U. V. Vazirani, and V. V. Vazirani, "An optimal algorithm for on-line bipartite matching," in Proc. 22nd Annu. ACM Symp. Theory Comput. (STOC), 1990, pp. 352-358.

Digital Library

[8]

S. Moharir and S. Sanghavi, "Online load balancing and correlated randomness," in Proc. 50th Annu. Allerton Conf. Commun., Control, Comput. (Allerton), Oct. 2012, pp. 746-753.

[9]

D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization (Athena Scientific Series in Optimization and Neural Computation). Belmont, MA, USA: Athena Scientific, 1997.

Digital Library

[10]

W. Wang, K. Zhu, L. Ying, J. Tan, and L. Zhang, "MapTask scheduling in mapreduce with data locality: Throughput and heavy-traffic optimality," IEEE/ACM Trans. Netw., vol. 24, no. 1, pp. 190-203, Feb. 2016.

Digital Library

[11]

M. Isard et al., "Quincy: Fair scheduling for distributed computing clusters," in Proc. ACM SIGOPS 22nd Symp. Operat. Syst. Principles, 2009, pp. 261-276.

Digital Library

[12]

G. Goel and A. Mehta, "Online budgeted matching in random input models with applications to adwords," in Proc. 9th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2008, pp. 982-991.

Digital Library

[13]

C. Karande, A. Mehta, and P. Tripathi, "Online bipartite matching with unknown distributions," in Proc. 43rd Annu. ACM Symp. Theory Comput., 2011, pp. 587-596.

Digital Library

[14]

J. Feldman, A. Mehta, V. Mirrokni, and S. Muthukrishnan, "Online stochastic matching: Beating 1-1/e," in Proc. 50th Annu. IEEE Symp. Found. Comput. Sci. (FOCS), Oct. 2009, pp. 117-126.

Digital Library

[15]

B. Kalyanasundaram and K. R. Pruhs, "An optimal deterministic algorithm for online b-matching," Theor. Comput. Sci., vol. 233, no. 1, pp. 319-325, 2000.

Digital Library

[16]

A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani, "AdWords and generalized on-line matching," in Proc. 46th Annu. IEEE Symp. Found. Comput. Sci. (FOCS), Oct. 2005, pp. 264-273.

Digital Library

[17]

X. Cheng, C. Dale, and J. Liu, "Statistics and social network of YouTube videos," in Proc. 16th Int. Workshop Quality Service (IWQoS), Jun. 2008, pp. 229-238.

[18]

M. Cha, H. Kwak, P. Rodriguez, Y.-Y. Ahn, and S. Moon, "Analyzing the video popularity characteristics of large-scale user generated content systems," IEEE/ACM Trans. Netw., vol. 17, no. 5, pp. 1357-1370, Oct. 2009.

Digital Library

[19]

N. Littlestone and M. K. Warmuth, "The weighted majority algorithm," Inf. Comput., vol. 108, no. 2, pp. 212-261, 1994.

Digital Library

[20]

A. DeSantis, G. Markowsky, and M. N. Wegman, "Learning probabilistic prediction functions," in Proc. 29th Annu. Symp. Found. Comput. Sci., Oct. 1988, pp. 110-119.

Digital Library

[21]

N. Littlestone, "Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm," Mach. Learn., vol. 2, no. 4, pp. 285-318, Apr. 1988.

[22]

N. Littlestone, "Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow," in Proc. 4th Annu. Workshop Comput. Learn. Theory (COLT), 1991, pp. 147-156.

Digital Library

[23]

R. Armstrong, D. Freitag, T. Joachims, and T. Mitchell, Webwatcher: A Learning Apprentice for the World Wide Web. Washington, DC, USA: AAAI Press, 1995, pp. 6-12.

[24]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games. New York, NY, USA: Cambridge Univ. Press, 2006.

Digital Library

[25]

M. Hutter, "On the foundations of universal sequence prediction," in Proc. Int. Conf. Theory Appl. Models Comput., 2006, pp. 408-420.

Digital Library

[26]

S. Moharir, S. Sanghavi, and S. Shakkottai, "Online load balancing under graph constraints," IEEE/ACM Trans. Netw., vol. 24, no. 3, pp. 1690-1703, Jun. 2016.

Digital Library

[27]

C.-Y. Koo, T.-W. Lam, T.-W. Ngan, K. Sadakane, and K.-K. To, "On-line scheduling with tight deadlines," Theor. Comput. Sci., vol. 295, no. 1, pp. 251-261, 2003.

[28]

C. Dürr, Ł. Jez, and K. T. Nguyen, Online Scheduling of Bounded Length Jobs to Maximize Throughput. Berlin, Germany: Springer, 2010, pp. 116-127. [Online]. Available:

Digital Library

[29]

L. Liu et al., "Preemptive hadoop jobs scheduling under a deadline," in Proc. 8th Int. Conf. Semantics, Knowl. Grids (SKG), Oct. 2012, pp. 72-79.

Digital Library

[30]

Z. I. A. Khalib, B. R. Ahmad, and O. B. L. Ong, "High deadline meeting rate of non-preemptive dynamic soft real time scheduling algorithm," in Proc. IEEE Int. Conf. Control Syst. Comput. Eng. (ICCSCE), Nov. 2012, pp. 296-301.

[31]

M. Babaioff et al., "ERA: A framework for economic resource allocation for the cloud," in Proc. 26th Int. Conf. World Wide Web Companion, 2017, pp. 635-642.

Digital Library

[32]

B. Hindman et al., "Mesos: A platform for fine-grained resource sharing in the data center," in Proc. NSDI, 2011, pp. 295-308.

Digital Library

[33]

M. Zaharia et al., "Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling," in Proc. 5th Eur. Conf. Comput. Syst., 2010, pp. 265-278.

Digital Library

Cited By

Lin QMo YSu JChen M(2022)Competitive Online Optimization with Multiple InventoriesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35309026:2(1-28)Online publication date: 6-Jun-2022
https://dl.acm.org/doi/10.1145/3530902
Deng HZhao THou I(2019)Online Routing and Scheduling With Capacity Redundancy for Timely Delivery Guarantees in Multihop NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2019.291739327:3(1258-1271)Online publication date: 15-Jul-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2917393

Optimal Capacity Provisioning for Online Job Allocation With Hard Allocation Ratio Requirement
1. General and reference
  1. Cross-computing tools and techniques
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Online job allocation with hard allocation ratio requirement
IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications
The problem of allocating jobs to appropriate servers in cloud computing is studied in this paper. We consider that jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. In order to meet ...
Adaptive job scheduling via predictive job resource allocation
JSSPP'06: Proceedings of the 12th international conference on Job scheduling strategies for parallel processing

Standard job scheduling uses static job sizes which lacks flexibility regarding changing load in the system and fragmentation handling. Adaptive resource allocation is known to provide the flexibility needed to obtain better response times under such ...
Convex resource allocation for minimizing the makespan in a single machine with job release dates

We consider the problem of scheduling jobs on a single machine where job-processing times are controllable through the allocation of a common limited resource. The release dates are known and the job-processing time is described by a convex decreasing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 26, Issue 2

April 2018

377 pages

ISSN:1063-6692

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 01 April 2018

Published in TON Volume 26, Issue 2

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
48
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lin QMo YSu JChen M(2022)Competitive Online Optimization with Multiple InventoriesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35309026:2(1-28)Online publication date: 6-Jun-2022
https://dl.acm.org/doi/10.1145/3530902
Deng HZhao THou I(2019)Online Routing and Scheduling With Capacity Redundancy for Timely Delivery Guarantees in Multihop NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2019.291739327:3(1258-1271)Online publication date: 15-Jul-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2917393

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents