Reducing Scenarios For Cost Optimzation Of Resource Provisioning In Cloud Computing

Reducing Scenarios For Cost Optimzation Of Resource Provisioning In Cloud Computing

Dr. V. Venkatesa Kumar

Asst.Professor Department of Computer Science and

Engineering

Anna University, Regional Centre, Coimbatore Coimbatore -641301

C. Kalpana

PG Scholar

Department of Computer Science and

Engineering

Anna University, Regional Center, Coimbatore Coimbatore-641301

Abstract

The Cloud Computing provides the computing resources to the Cloud users as service via the Internet. A resource provisioning method is vital to provide Cloud users, a set of computing resources for processing the tasks and to store the data in Cloud Computing. The Cloud provider may provide two types of provisioning schemes for computing resources namely Advance reservation and On-Demand schemes to the Cloud users. A Multistage Stochastic Programming model which considers a set of scenarios (Price and Demand Uncertainty) is used for the Resource Provisioning for reservation schemes in Cloud Computing. The optimization under uncertainty deals with a huge set of scenarios for real time problems. A huge set of scenarios consideration leads to consumption of time and computational complexity. To address this problem, a Scenario Reduction Technique is applied to reduce the number of scenarios and provides a lesser set of Scenarios. This Reduction Technique finds out a subset of the primary scenario set and probabilities are assigned to the condensed set of the scenarios. The scenario tree generation algorithm consecutively decreases the number of nodes of the each scenario by altering the tree model and by wrapping the alike scenarios.

Keywords Resource Provisioning, Scenario reduction, Scenario Tree, Cloud Computing, Stochastic Programming model.

1. INTRODUCTION

The Cloud computing is the emerging trend in Parallel and Distributed Computing paradigm, which provides a shared set of computing resources (e.g., Network, Storage, Software, and Applications) to the user as a service using the Internet. A resource provisioning methodology is essential in Cloud Computing to provide Cloud users, a set of computing resources for processing the tasks and storing the data. Cloud providers can provide two types of provisioning schemes, they are Advanced reservation and On-Demand schemes. When compared to the On-Demand scheme, Advanced reservation scheme is much lower in price.

With Advance reservation scheme, the Cloud users reserve the resource in advance. As a consequence, the Shortage provisioning issue may arise when the reserved

resources are not able to satisfy the demand. Even though this issue can be resolved by provisioning required resources using Pay-per-use scheme(On-Demand), high prices will be acquired due to the high price of the the Pay-per- use scheme. Another issue called Excess provisioning may arise , if the reserved resources become excess than the actual need in which only a partial resource set will be used.

It is essential to decrease the total cost of the provisioning of resources for the Cloud users by minimizing the Pay-per- use price and Excess Provisioning price. Minimizing both Shortage provisioning and Excess provisioning issues under demand and price uncertainty in Cloud Computing requires a resource provisioning approach for the Cloud users. An optimal resource provision algorithm is used to minimize the overall cost of the resource provisioning. An Optimal decision can be made, by considering the demand uncertainty from the Cloud user and price uncertainty from

the Cloud supplier to regulate the exchange between On- Demand price and Excess provisioning price. Therefore, Optimization models used for resource provisioning employ scenarios to deal with uncertainty [demand and price]. The optimal decision is achieved from optimal resource provision algorithm is based on the Stochastic Integer Programming model. The Stochastic Programming deals with a set of scenarios. Individual scenario relates to a particular result of the random measure. The uncertainties considered for resource provisioning in the Cloud are demand and price.

The scenarios and their related probabilities gives an approximation of the probability distribution.

The optimal decision is achieved from optimal resource provision algorithm is based on the Stochastic Integer Programming model. The Stochastic Programming deals with a set of scenarios. A distinct grouping of the values of the uncertain parameters yields a specific scenario. So the individual scenario relates to a particular result of the random measure. In optimization model, many numbers of uncertain parameters are to be considered which gives a predetermined set of scenarios. It increases the size of the optimization problem, which is very complex to solve. So an Approximation approach including a lesser number of

resource reservation system provides functions like allocation of reservation, analysis of demand and price optimization. It also presents reservation schemes like standard reservation based, flexible reservation based on discounted price, particular reservation based on best price[7].

The Stochastic programming model considers many numbers of scenarios for optimization problem. This leads to time complexity and computational complexity. So to reduce the number of scenarios, the Scenario Reduction technique is used. It uses backward type and forward type algorithms to make a reduced set of scenarios and assigns modified probability to them. Scenario tree construction is also represented [2].

1. SCENARIO REDUCTION TECHNIQUE

   There are many methods are available for reducing the primary scenario set and to create a scenario tree.

   Notations

   scenarios is used. The scenario reduction technique

   , t, 1 1

   where t =1,.., T Stochastic

   proposed , identifies a subset of scenarios from the primary scenario group.

   The scenarios into mutually dependent decision making approaches are that the process is deterministic in nature at the initial phase. In further phases, the random value at any point is independent of the subsequent understanding. A unique model of limited scenario set is required, that is, a tree model. A scenario tree may be modeled by a predetermined set of nodes. It begins with the parent node at the initial phase and further it branches into nodes at the subsequent phase. Every node has a distinct ancestor node but probably many descendant nodes. Until the nodes of the last phase the branching carry on.

   Sampling method (e.g.,Monte Carlo sampling) is used to choose a subset of samples from a large set of statistical samples to approximate the uniqueness of the entire set. Hence this sampling method is used to construct scenarios.

   This paper is structured as follows :

   The Scenario Reduction algorithms namely Simultenous backward reduction algorithm and Fast forward selection algorithm are proposed for Reducing scenarios.

   Scenario tree generation for representing the finite set of scenarios is proposed.

   2. RELATED WORKS

   A best algorithm for resource provisioning in cloud computing is provided. This provides which resources which can be used in many numbers of stages. The demand and cost uncertainty are considered to maintain the exchange between pay-per-use plan and Excess provisioning cost [1].

   A reservation method is proposed which manages the assignment of services to satisfy needs of the users and improves collaboration among the users. A Dynamic

   , t

   processes with argument set

   {1,.,T}

   a, b Scenarios

   a, fb Probabilities of scenarios

   E, F Probability distribution of

   1. The number of Scenarios in the primary scenario set

   2. set of deleted scenarios

   #S The number of deleted scenarios

   r= R – # S The number of scenarios that exist in reduced set

   Reduction tolerance

   D ( a, b) Distance between the scenario

   A pre-determined set of scenarios with their probabilities

   K

   Step (iv)

   Repeat with step (i) until the defined number of the

   ea,

   a1

   ea gives the probability distribution E of the n-

   scenarios are deleted.

   dimensional stochastic process (considering demand and price uncertainity).The Scenario Reduction techniques designed in [2] finds out a reduced scenario set and allocates modified probabilities to the reduced scenario set in which the related new probability value F is the nearest to the initial value E. Kantorovich distance is used for the Resource provisioning in Cloud.

   The two scenario distance D is calculated as,

   x

2. RESULTS AND DISCUSSIONS

   1. Simulation Tool

      The CloudSim tool is used to implement the simulation in Cloud computing. For attaching a job to a selected Virtual machine bindcloudletToVM() is used.

      D ( a,

      b)=

      1

      a,- b ,

      with respect to , where

   2. Experimental Results

   The proposed work reduces the time when compared to the existing work. The Figure 3 shows that the comparison

   x = 1,….T.

   The probability tb (conserved scenario) is calculated as

   fb = eb + ea

   aS (b)

   The above equation gives the modified probability of the reduced set scenario which is equal to the sum of its initial probability. A probability value of zero to be considered for all dropped scenarios.

   3.1 Scenario Reduction Algorithms

   The algorithm reduces the primary scenario set to a smaller scenario set. For scenario reduction two algorithm from[2] are applied.

   3.1.1 Algorithm 1

   The algorithm 1 lessens the large number of scenarios by deleting the single scenario at each step recursively and subsequently modifies the probabilities of remaining scenarios until a defined number of scenarios is left.

   Step (i)

   Determine the Scenario to be removed: Calculate

   min i belongs to 1,…,R ei min b i D ( a, b) and removes the scenario i* where i* {1,..,R}.

   Step (ii)

   Reduce the count of the scenarios by one.

   Step (iii)

   Add the probability of the deleted scenario with the probability of the scenario that is closest to the the deleting scenario probability.

   between the Computational time with out applying Scenario Reductio Technique and with Scenario Reduction Technique.

   Handling with a large set of Scenarios is time consuming one, so applying reduction algorithm large number of Scenario gets reduced and only lesser number of scenarios are considered. Thus proposed Scenario Reduction algorithm reduces the Computational time by lessens the number of scenarios.

   Figure.3

   Comparison of the Computation time between Existing system and with scenario reduction.

   The The Figure 4 shows that the comparison between the Memory usage without applying Scenario Reductio Technique and with Scenario Reduction Technique. The proposed work reduces the memory by reducing the number of scenarios. The number of intial Scenarios are high in mumber. Reducing Scenarios leads to a Reduced set of preserved Scenarios. Thus the memory is also reduced considerably by applying Scenario Reduction technique.

   Figure. 4

   Comparison of the memory usage between Existing system and with scenario reduction

   The Figure 5 shows that the Accuracy of the optimal value of the resource provisioning with the scenario reduction. The proposed work results in the best estimation of the optimal result of the optimization system with a reduced set of scenarios. With the reduced a set of scenario the proposed work still achieves the best optimized results.

   Figure.5

   Accuracy of the optimal value of the resource provisioning in cloud computing with and without scenario reduction

3. CONCLUSION

In Cloud Computing, the resource provisioning mechanism uses Stochastic Programming model. These models considers many number of scenarios which leads to time and computational. So in this work, the Scenario Reduction algorithm is applied to reduce the number of scenarios which reduces the time and computational complexities. The results shows that the proposed work reduces the computational time, memory usage of the

optimization problem for resource provisioning in Cloud Computing. The optimized result of the optimized model after the reduction of set of scenarios is also highly accurate.

REFERENCES

1. Chaisiri, S.; Bu-Sung Lee; Niyato, D, Optimization of Resource Provisioning Cost in Cloud Computing, , IEEE Transactions on Services Computing Volume: 5 , Issue: 2 April-June 2012.

2. H. Heitsch and W. Ro¨misch, Scenario Reduction Algorithms in Stochastic Programming,J.Computational Optimization and Applications, vol. 24, pp. 187-206, 2003

3. H. Niederreiter, Random Number Generation and Quasi- Monte Carlo Methods, SIAM, Philadelphia, 1992.

4. C. Lemieux, Monte Carlo and Quasi-Monte Carlo Sampling , Springer, 2009.

5. J. Dick and F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, 2010 (to appear).

6. H. Sloan and S. Joe, Lattice Methods for Multiple Integration, Clarendon Press, Oxford 1994.

7. K. Miyashita, K. Masuda, and F. Higashitani,CoordinatingService Allocation through Flexible Reservation,IEEE Trans.Services Computing, vol. 1, no. 2, pp. 117-128, Apr.-June 2008.

8. M. Sobol, Multidimensional Quadrature Formulas and Haar Functions, Nauka, Moscow,1969 (in Russian).

9. M. G¨otz, Discrepancy and the error in integration, Monatshefte f¨ur Mathematik 136 (2002),99-121.

10. H. Sloan and H. Wo´zniakowski, When are Quasi Monte Carlo algorithms efficient for highdimensional integration, Journal of Complexity 14 (1998), 133.

11. F. Y. Kuo and I. H. Sloan, Lifting the curse of dimensionality, Notices of the AMS 52 (2005),13201328.

12. B. Owen, Multidimensional variation for Quasi-Monte Carlo, in J. Fan, G. Li (Eds.), International Conference on Statistics, World Scientific Publ., 2005, 4974.

13. X. Wang and K.-T. Fang, The effective dimension and Quasi-Monte Carlo integration, Journal of Complexity 19 (2003), 101124.

14. F.V. Louveaux, Stochastic Integer Programming, Handbooks in OR & MS, vol. 10, pp. 213-266, 2003.

15. G. Juve and E. Deelman, Resource Provisioning Options for Large-Scale Scientific Workflows, Proc. IEEE Fourth Intl Conf. e-Science, 2008.

16. Z. Huang, C. He, and J. Wu, On-Demand Service in Grid: Architecture Design, and Implementation, Proc. 11th Intl Conf. Parallel and Distributed Systems (ICPADS 05), 2005.

17. Y. Jie, Q. Jie, and L. Ying, A Profile-Based Approach to Just-in- Time Scalability for Cloud Applications, Proc. IEEE Intl Conf. Cloud Computing (CLOUD 09), 2009.

18. F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, H. Wo´zniakowski: On decomposition of multivariate functions, Mathematics of Computation 79 (2010), 953966.

19. M. Griebel, F. Y. Kuo, I. H. Sloan, The smoothing effect of the ANOVA decomposition, Journal of Complexity 2010 (in press).

20. H. Sloan, F. Y. Kuo and S. Joe, On the step-by-step construction of Quasi-Monte Carlo integration rules

that achieve strong tractability error bounds in weighted Sobolev spaces, Mathematics of Computation 71 (2002), 1609-1640.