Abstract
To handle user requests coming from all over the world, online services need to schedule resources to fulfill the corresponding stochastic demands for various resources in geo-distributed data centers. In order to make full use of the advantages of cloud resources and tap the potential of private infrastructure, the optimal schedule plan should consider the heterogeneity of different kinds of data centers. It results in a highly complex non-linear programming problem. To find efficient solutions, we introduce a related and simple problem to quickly obtain a feasible solution close to optimal one, and then leverage a differential evolution process with special steps to solve it quickly. By testing the algorithm using simulated and realistic data, we find that our algorithm outperforms the existing algorithms and can increase the revenue by more than 34%.
Similar content being viewed by others
Data Availability
The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.
References
Google Cloud home page. https://cloud.google.com (2018)
Amazon EC2 home page. http://aws.amazon.com/ec2 (2018)
Microsoft Azure home page. http://azure.microsoft.com (2018)
Rochman, Y., Levy, H., Brosh, E.: Resource placement and assignment in distributed network topologies. In: Proceedings of IEEE INFOCOM, pp 1914–1922 (2013)
Rochman, Y., Levy, H., Brosh, E.: Efficient resource placement in cloud computing and network applications. ACM Sigmetrics Performance Evaluation Review 42(2), 49 (2014)
Wei, W., Zhang, Y., Liu, Y., Qin, Z.: FRP: a fast resource placement algorithm in distributed cloud computing platform. Concurrency and Computation: Practice and Experience 28(5), 1399 (2015)
Aliyun pricing page. https://www.alibabacloud.com/zh/product/ecs#pricing (2018)
Amazon EC2 pricing page. https://aws.amazon.com/ec2/pricing/ (2018)
Microsoft Azure pricing page. https://azure.microsoft.com/en-us/pricing/calculator/ (2018)
Zhang, G., Zhu, X., Bao, W., Yan, H., Tan, D.: Local storage based consolidation with resource demand prediction and live migration in clouds. IEEE Access 6(1), 26854 (2018)
Farahnakian, F., Pahikkala, T., Liljeberg, P., Plosila, J., Hieu, N.T., Tenhunen, H.: Energy-aware VM consolidation in cloud data centers using utilization prediction model. IEEE Transactions on Cloud Computing 7(2), 524 (2019)
Homsi, S., Liu, S., Chaparro-Baquero, G., Ou, B., Ren, S., Quan, G.: Workload consolidation for cloud data centers with guaranteed QoS using request reneging. IEEE Transactions on Parallel & Distributed Systems 28(7), 2103 (2017)
Xiao, X., Zheng, W., Xia, Y., Sun, X., Peng, Q., Guo, Y.: A workload-aware VM consolidation method based on coalitional game for energy-saving in cloud. IEEE Access 7 (1), 80421 (2019)
Sharma, Y., Si, W., Sun, D., Javadi, B.: Failure-aware energy-efficient VM consolidation in cloud computing systems. Futur. Gener. Comput. Syst. 94(5), 620 (2019)
Chunlin, L., Jianhang, T., Youlong, L.: Hybrid cloud adaptive scheduling strategy for heterogeneous workloads. Journal of Grid Computing 17(1), 1 (2019)
Zhang, Y., Cheng, X., Chen, L., Shen, H.: Energy-efficient tasks scheduling heuristics with multi-constraints in virtualized clouds. Journal of Grid Computing 16(3), 459 (2018)
Aazam, M., Huh, E.N., St-Hilaire, M.: Towards media inter-cloud standardization – evaluating impact of cloud storage heterogeneity,. Journal of Grid Computing 16(3), 425 (2018)
Moreno-Vozmediano, R., Montero, R.S., Huedo, E., Llorente, I.M.: Implementation and provisioning of federated networks in hybrid clouds. Journal of Grid Computing 15(2), 141 (2017)
Han, H., Wen, Y., Chua, T.S., Jian, H., Zhu, W., Li, X.: Joint content replication and request routing for social video distribution over cloud CDN: a community clustering method. IEEE Transactions on Circuits & Systems for Video Technology 26(7), 1320 (2016)
He, Q., Liu, J., Wang, C., Bo, L.: Coping with heterogeneous video contributors and viewers in crowdsourced live streaming: a cloud-based approach. IEEE Transactions on Multimedia 18(5), 916 (2016)
Wei, W., Yang, L., Zhang, Y.: TRLMS: two-stage resource scheduling algorithm for cloud based live media streaming system. IEICE Trans. Inf. Syst. 97(7), 1731 (2014)
Das, S., Mullick, S.S., Suganthan, P.N.: Recent advances in differential evolution - an updated survey. Swarm & Evolutionary Computation 27(1), 1 (2016)
Wu, G., Pedrycz, W., Suganthan, P.N., Mallipeddi, R.: A variable reduction strategy for evolutionary algorithms handling equality constraints. Appl. Soft Comput. 37(1), 774 (2015)
Gao, W., Yen, G.G., Liu, S.: A dual-population differential evolution with coevolution for constrained optimization. IEEE Transactions on Cybernetics 45(5), 1094 (2015)
Ross, S.M.: Introduction to Probability Models. Academic Press (2006)
Tan, B, Massoulie, L.: Optimal content placement for peer-to-peer video-on-demand systems. IEEE/ACM Transactions on Networking 21(2), 566 (2013)
Storn, R., Price, K.: Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization 11(4), 341 (1997)
Das, S., Suganthan, P.N.: Differential evolution: a survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation 15(1), 4 (2011)
Aliyun home page. http://www.aliyun.com (2018)
The 150 Largest Cities in the World. http://www.worldatlas.com/citypops.htm (2017)
Live Streaming Sessions Dataset. http://dash.ipv6.enstb.fr/dataset/live-sessions/ (2014)
Google Cloud pricing page. https://cloud.google.com/compute/pricing (2018)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
National Natural and Science Foundation of China (61702162, 62006071, 61772173, 61973104, U1604151, 61803146), the Key Laboratory of Grain Information Processing and Control (Henan University of Technology), the Ministry of Education (KFJJ-2016-104), Science and technology project of science and technology department of Henan province (No.202102210148), Cultivation Programme for Young Backbone Teachers in Henan University of Technology (2012012), Young Backbone Teacher Training Program of Henan Higher Education (2018GGJS066), Plan For Scientific Innovation Talent of Henan University of Technology (2018RCJH07, 2018QNJH26), Doctor Foundation of Henan University of Technology (2017025), Natural Science Foundation of the Henan Province (152102210068), National Key Research and Development Program of China (2017YFD0401001), Program for Science and Technology Innovation Talents in Universities of Henan Province (19HASTIT027), Key Science and Technology Research Project of Education Department Henan Province (18A520026).
Appendix
Appendix
1.1 Proof of Lemma 1
Proof
The local optimal condition is that the marginal revenue of unit cost equals for each resource in each region. Given \({\lim _{ {{\varDelta }^{r}_{a}} \to +0 }}({({\varsigma ^{r}_{a}})}^{-1}({c^{r}_{a}}+{{\varDelta }^{r}_{a}}) - {f}^{r}_{a}({c^{r}_{a}})) = {{\varDelta }^{r}_{a}}\hat {f^{\prime }}^{r}_{a}({c^{r}_{a}})\), then the increase revenue when \({c^{r}_{a}}\) increased to \({c^{r}_{a}}+{{\varDelta }^{r}_{a}}\) can be:
Where \(\mathcal {U}^{r} = {\sum }_{r=1}^{\mathcal {R}{{({\varsigma ^{r}_{a}})}^{-1}({c^{r}_{a}})}}\) in (2) (i.e., the reduction form of (1)), so the marginal revenue relates to both \({c^{r}_{a}}\) and \(c^{r}_{a^{\prime }} (a^{\prime } \neq a)\), and does not necessarily monotonically change according to \({c^{r}_{a}}\). There may be different cases of \({c^{r}_{a}} (1 \le r \le \mathcal {R}, 1 \le a \le \mathcal {A})\) that can get equal marginal revenue, so there will be multiple local optimal conditions for (??).
□
1.2 Proof of Lemma 3
Proof
Suppose Θ is the optimal solution to the all-resource problem in (??), but Θr is not the optimal solution to problem in (??). By replacing Θr to better \({\varTheta ^{r}}^{\prime }\), the new solution \(\varTheta ^{\prime }\) is a better solution than Θ, which contradicts with the premise that Θ is the optimal solution. □
1.3 Proof of Lemma 2
Proof
It is clear that if \({\mathcal {U}^{r}}^{\prime } < \mathcal {U}^{r}\) their maximal revenues \(\psi ^{r}({\mathcal {U}^{r}}^{\prime }) < \psi ^{r}(\mathcal {U}^{r})\). So for the solution vector ζr to (??), if it has \({\sum }_{a=1}^{\mathcal {A}}{ {{\varsigma ^{r}_{a}}} ({\zeta ^{r}_{a}}) } = \mathcal {C}^{r}\), then ζr is also a solution (not necessarily optimal) to (??), so it has \(\psi ^{r}(\mathcal {C}^{r}) > \psi ^{r}(\mathcal {U}^{r})\). Based on the above information, if the optimal solution of (??) has \({\sum }_{a=1}^{\mathcal {A}}{ \hat {{\varsigma ^{r}_{a}}}({c^{r}_{a}} ) } < \mathcal {U}^{r}\), the maximal revenue will be no more than \(\psi ^{r}(\mathcal {U}^{r})\), which contradicts with \(\psi ^{r}(\mathcal {C}^{r}) > \psi ^{r}(\mathcal {U}^{r})\) (\(\psi ^{r}(\mathcal {C}^{r})\) is the maximal revenue of (??)). The lemma is proved. □
1.4 Proof of Lemma 4
Proof
If CDF \({\mathscr{H}}^{r}_{(a,k)}(\cdot )\) is monotonically increasing, then the marginal revenue for each (a,r) \({\mu ^{r}_{a}}({\zeta ^{r}_{a}}) = {\sum }_{k=1}^{K}{ {\mathscr{H}}^{r}_{(a,k)}({\zeta ^{r}_{a}})}\) is monotonically decreasing. According to nonlinear optimization theory, the global optimal condition is that the marginal revenue equals with each other, i.e., \({\mu ^{r}_{a}}({\zeta ^{r}_{a}})\) is equal for each a. The lemma is proved. □
1.5 Proof of Lemma 5
Proof
Let divide all a s into two sets Φ1 and Φ2, where \(c^{r}_{a^{\prime }} >= \overline {{c^{r}_{a^{\prime }}}}\) for \({a^{\prime }} \in \varPhi _{1}\) and \(c^{r}_{a^{\prime \prime }} < \overline {c^{r}_{a^{\prime \prime }}}\) for \({a^{\prime \prime }} \in \varPhi _{2}\). Then according to Definition 1, it has \(\widetilde {c^{r}_{a^{\prime }}} <= c^{r}_{a^{\prime }} \quad \forall {a^{\prime }} \in \varPhi _{1} \) and \(\widetilde {c^{r}_{a^{\prime \prime }}} > c^{r}_{a^{\prime \prime }} \quad \forall {a^{\prime \prime }} \in \varPhi _{2}\). Let \(\overline {{p^{r}_{a}}}\) as the price at \(\overline {{c^{r}_{a}}}\) as, the average prices can be calculated as:
It is clear that \(\widetilde {p^{r}_{a^{\prime }}} \ge p^{r}_{a^{\prime }}\) and \(\widetilde {p^{r}_{a^{\prime \prime }}} \le p^{r}_{a^{\prime \prime }}\). The amount constraint of the near-optimal solution \(\overline {\mathcal {U}^{r}} \ge {\sum }_{a=1}^{J}{{\zeta ^{r}_{a}} } \) since cr is below the lower bound, and it has:
Then, we can obtain \({\sum }_{a=1}^{\mathcal {A}}{({c^{r}_{a}} - \overline {{c^{r}_{a}}} ) / {p^{r}_{a}} } \le 0\), denote \(\overline {\varphi ^{r}}= {\overline {{c^{r}_{1}}}, \overline {{c^{r}_{2}}}, ..., \overline {c^{r}_{\mathcal {A}}}}\), for its reflection point \(\widetilde {{\varphi ^{r}}}= {\widetilde {{c^{r}_{1}}}, \widetilde {{c^{r}_{2}}}, ..., \widetilde {c^{r}_{\mathcal {A}}}}\), it has:
□
Rights and permissions
About this article
Cite this article
Wei, W., Wang, Q., Xu, H. et al. Highly Complex Resource Scheduling for Stochastic Demands in Heterogeneous Clouds. J Grid Computing 19, 12 (2021). https://doi.org/10.1007/s10723-021-09555-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10723-021-09555-1