Decentralized Self-Adaptation Mechanism for Service Based Applications in Cloud using Spectral Clustering

E Nisha

SCAD Engineering College, Cheranmahadevi

ABSTRACT:

Cloud computing, with its promise of (almost) unlimited computation, storage and bandwidth, is increasingly becoming the infrastructure of choice for many organizations. As cloud offerings mature, service-based applications need to dynamically recompose themselves, to self-adapt to changing QoS requirements. In this paper, we present a decentralized mechanism for such self-adaptation, using natural language processing. We use a continuous double-auction to allow applications to decide which services to choose, amongst the many on offer. The proposed scheme exploits concepts derived from graph partitioning, and groups together tasks so as to 1) minimize the time overlapping of the tasks assigned to a given resource and 2) maximize the time overlapping among tasks assigned to different resources. The partitioning is performed using a spectral clustering methodology through normalized cuts. Experimental results show that the proposed algorithm outperforms other scheduling algorithms for different values of the granularity and the load of the task requests.

KEYWORDS: Self-Adaptation; Market-Based; Multi-Agent Systems; Spectral Clustering

Copy the following to cite this article: Nisha E. Decentralized Self-Adaptation Mechanism for Service Based Applications in Cloud using Spectral Clustering. Orient. J. Comp. Sci. and Technol;7(1)

Copy the following to cite this URL: Nisha E. Decentralized Self-Adaptation Mechanism for Service Based Applications in Cloud using Spectral Clustering. Orient. J. Comp. Sci. and Technol;7(1). Available from: http://computerscijournal.org/?p=742

INTRODUCTION

Self-adaptation, as a concept, has been around for many years, in several domains like biology, chemistry, logistics, economics etc. Self-adaptivity in computer-based systems is relatively newer. Some of the first references to self-adaptive software systems are from [41], [35], [34] and [31] (where they are referred to, as autonomic systems). By self-adaptivity in software systems, we mean software that monitors itself and the operating environment, and takes appropriate actions when circumstances change. In web-applications, service-oriented architecture has often been used as a mechanism for achieving self-adaptivity [19]. Web-services allow for dynamic composition, which enables applications to switch services, without going offline. A common instance of using web-services dynamically, is applications living on the cloud, asking for computing power and bandwidth to be scaled up or down, depending on demand. However, one of the cloud’s major selling points, operational flexibility is of little use, if applications (or organizations) have to indicate at sign-up time, the kind of services that they intend to use. On Amazon, for instance, a customer specifies during sign up whether she wants a Hi-CPU instance or a Standard On-Demand instance or a Hi- Memory instance. This assumes that an application is able to forecast its demand for computing and storage resources accurately.

OUR APPROACH

We would like to create a mechanism that allows multiple applications, constructed across a federation of clouds, to self-adapt. We chose a market-based approach to self-adaptation, not only because it is decentralized, but also due to its easy applicability to the problem domain. Services in the cloud aremoving from a fixed-price package to a more flexible, auction-based approach [29]. This enables a self-adaptive application to change the QoS exhibited, by switching to a different ConcreteService.

2.1 Market-Based Control

Market-Based Control (MBC) essentially involves modeling the system as a marketplace, where self-interested agents use economic strategies to compete for resources. Self-interested competition, along with well-designed utility functions, allow for a decentralized means of decision making. These agents, via their competitive need to get resources, perform a parallel search through the space of decision points. MBC has been used in several contexts, as a mechanism for computing a good solution in a decentralized manner. 

2.2 Auctions

Auctions, specifically Double Auctions (DA), have increasingly been studied in Computer Science, as a mechanism of resource allocation. Daniel Friedman [22] reports on experiments where traders even with imperfect information, consistently achieve highly efficient allocations

and prices. The rise of electronic commerce naturally creates a space for efficient exchange of goods, and services. There has been much work on the design space of market-institutions [51], [39], bidding strategies [17], [43], agent-based implementations of traders [30], [26], [27], [40], etc. Gupta et al [24] argue that network management, specifically for QoS issues, must be done using pricing and market dynamics. According to them, the flexibility offered by pricing mechanisms offers benefits of decentralization of control, dynamic load management and effective allocation of priority to different QoS attributes. The continuous-time variant of a DA, called Continuous Double Auction (CDA), is used in stock-markets and commodity exchanges around the world [32]. In a CDA, the market clears continuously.

2.3 Spectral Clustering Algorithm

We refer to our proposed task allocation scheme as the Spectral Clustering Scheduling (abbreviated SCS) algorithm. An advantage of the SCS algorithm is that it can be used in two different ways. The first is to efficiently schedule tasks on a given number of resources so as to minimize the task time requirement violations. The second is to find the number of resources or virtual machines required to serve the tasks with a given level of task time violations (or with no violations). The latter approach is particularly helpful in a cloud computing environment, where a resource  provider should be able to estimate the service-level agreement (SLA) offered to its users for a given number of virtual machines (resources) used.

2.3.1 General Scheduling Algorithms

When the tasks’ QoS requirements are given in the form of task deadlines, the most well-known scheduling algorithm is the Earliest Deadline First (EDF) [8]. Another approach is the Slack Time algorithm, also referred to as Least Laxity First (LLF) [9], where the tasks are selected for execution in order of nondecreasing slack time, defined as the difference between the task’s relative deadline and its remaining computational time. A framework for providing hard deadline guarantees in a grid environment, by controlling the rate and burstiness with which users submit jobs to resources, is proposed in [10]. In the case where the infrastructure consist of a cluster of servers, several schedulers have been developed, including Maui [11], the portable batch system (PBS) [12], and the load sharing facility (LSF) [13]. Most of the scheduling algorithms proposed so far for grids provide a best effort (nonguaranteed) service to the submitted tasks [14] and try to optimize a single or multiple metric(s) of interest (for example, task delay, probability to miss a deadline, etc.). Scheduling algorithms also exist that take into account the users’ QoS requirements (delay, required number of CPUs, etc.) and try to serve them in the best possible way [15]. Fairness in grid scheduling has been considered in [16], [17], where the proposed algorithms allow for the “fair” sharing of deadlines’ violations among all users. Genetic algorithms have also been widely used for solving NP-complete scheduling problems; see, for example, the works of [18], [19], [20], [21]. Reservation

2.3.2 Interval Scheduling

Our work relates to a particular flavor of the scheduling problem, which is called the interval scheduling problem, also known as fixed job scheduling [33]. In interval scheduling, a list of tasks is given as a set of requested time intervals and the scheduler decides if it can accept or not a task, and, in the second case, assign it to some resource. There are several variants of the problem: One variant assumes an unrestricted number of resources and the objective is to find a minimum cost schedule that does not reject any tasks [34]. . Another variant assumes a fixed number of resources and a predefined profit associated with the successful execution of each task. The objective is to find a maximum-profit schedule in which some, but not necessarily all, of the tasks are assigned to the resources [3].

The third case refers to a variant of the aforementioned problems where each task has a set of possible starting times, instead of a single starting time [35]. . Finally, in the online interval scheduling problem tasks are generated one by one and the scheduler has to make a decision for each task before a new task arrives. The objective is to maximize the total length of the intervals assigned to tasks, while ensuring that no pair of tasks assigned to the same resource overlap in time [36]. In [33], the interested reader can find a survey of the interval scheduling literature. In the current paper, we focus on the second type of interval scheduling algorithms. This variant of the problem can be modeled using a min-cost flow formulation. In the case that all jobs have unit weight, greedy algorithms are proposed in [38], [39] for estimating the maximum number of jobs that can be served. Heuristic and exact algorithms have been proposed in [40] for the case where each job can be executed only on a given subset of machines. The interval scheduling problem can also be formulated using interval graphs. A node in the interval graph corresponds to a task and there is an edge between nodes whose task intervals overlap. Hence, the basic interval scheduling problem is in fact a coloring problem of the  interval graph (see [41]). Interval graph scheduling can also be formulated as a graph partitioning problem, where the interval graph is partitioned so as to satisfy a multiobjective criterion. Graph partitioning is a kind of task clustering. Task clustering has been used in the literature for task scheduling in grids. Examples can be found in, where two task routing policies (one static and one adaptive) and six task scheduling policies are examined. Methods with similar goals include workflow allocation, mixed local, and global scheduling.

3 EVALUATION

3.1 The Current Scenario

The current form of service-selection is provider-driven. That is, in all commercial clouds, the cloud provider uses a posted-offer mechanism. A posted-offer is a form of market where the supplier posts a certain price on a takeit- or-leave-it basis. Thus, on Amazon’s elastic cloud compute (EC2), there are several services that are functionally identical, but priced differently. This price differentiation exists due to different QoS being exhibited by these services.

In our case, graph partitioning is performed based on spectral clustering through the use of normalized cuts. The normalized cuts method has advantages over the traditional min-cut methods, as it does not favor the creation of small clusters. To handle this issue, traditional graph partitioning methods, like geometric and multilevel graph partitioning, impose balancing criteria. However, predefining the partition size may be in conflict with the actual data statistics (in our case, the requested start and finish times), where sometimes unbalanced partitions are more appropriate. The use of normalized cuts resolves this issue, by automatically estimating the partition size with respect to the diversity of the tasks’ duration within each partition.

3.2 Qualitative Criteria

Thus, clobmas must fulfill the following criteria:

1. Allows customers like BizInt to create adaptive applications
2. Generates a higher utilization of services than the posted-offer model currently followed (for Sky-Compute)

3.3 Quantitative Criteria

Since, SkyCompute is an ultra-large collection of services, clobmas must be able to scale to large numbers of applications and ConcreteServices. Since there is no public data about the kinds of workflows hosted on commercial clouds, and their corresponding service choices, we made assumptions about the variables involved in dynamic service composition. We make these assumptions based on conversations with performance consultants at Capacitas Inc., and numbers gleaned from the literature review.

4 RELATED WORK

4.1 Self-Adaptation

Applications that use dynamic service composition should be able to continuously monitor their current QoS levels and make adjustments when either the demand for QoS changes or the cost constraint changes. The application should thus be able to respond to both internal as well as external stimuli, to trigger a change in its constituent web-services. This change needs to be both timely, as well as correct, i.e., the new set of services should not violate any of the application’s QoS constraints, and the change should happen as fast as possible.

Self-Adaptation in software systems is the achievement of a stable, desirable configuration, in the presence of varying stimuli. These stimuli may be environmental (in the form of workload, failure of external components, etc.) or internal (failure of internal components, changed target states, etc.).

There are two approaches to self-adaptation: centralized and de-centralized. In a centralized self-adaptive system, the analysis and planning part are concentrated in one entity. This form of self-adaptation has the advantage of cohesiveness and low communication overhead as compared to a decentralized mechanism. The analysis and the plan can be communicated to the effectors, and feedback from obeying the plan is communicated back through the monitors (or sensors). Rainbow [14] and The Autonomic Manager [28] are classic examples of centralized selfadaptation. Decentralized self-adaptation, on the other hand, distributes the analysis, planning or the feedback mechanism amongst different parts of the adapting system. This automatically implies a communication overhead, since all constituent parts must coordinate their actions. 

4.2 Spectral Clustering

4.2.1 Computational Complexity

The SCS scheduling algorithm consists of two main steps: 1) the eigenvalue decomposition optimization algorithm and 2) the clustering algorithm (k-means in our case). The fastest implementation for the eigenvalue decomposition problem is though the Lanczos method whose complexity is O(MN²_T), where M is the number of eigenvalues that have to be computed (equal to the number of processors), N is the number of tasks, and the number of iterations of the algorithm. In our case, takes small values (around 20-40), compared to M and particularly N. However, for low granularity values, M is several times smaller than N, making the complexity to be of order N² in that case in practice. The clustering step of the SCS algorithm is implemented using the k-means method, which has complexity O(N²_T) in our case. We present experiments regarding the computational complexity performance of the SCS algorithm, which is compared to that of other scheduling methods. The experiments have been carried out for three examined traces at different granularities values on an Intel Core2 Duo 3.00 GHz. It is clear that as the granularity increases the execution time of the scheduler decreases, since fewer tasks are encountered. Although SCS presents the worst execution time performance, the actual runtime is not so critical even for low granularities values.

CONCLUSION AND FUTURE WORK

Cloud-based service-oriented applications have the potential to self-adapt their QoS, depending on demand. Using a market-based mechanism maps nicely to the real-world situation of unpredictable change of QoS requirements, costs involved in adaptation and adaptation by competing applications. As the number of possible concrete services increase, the scalability of the self-adaptive mechanism becomes important. We see that the market-based mechanism consists of simple agents, is able to adapt well and yet scales linearly to the number of concrete services. We also see that it is robust in the presence of differences in demand and supply of QoS. Applications implemented as an ASN can thus scale and adapt to the changing business requirements of QoS. We have not modelled complex seller-side behaviour. Specifically, actions like deliberate violation of QoS to free up resources for making Asks with higher prices or mis-reporting of QoS available. Mechanisms like penalties and reputation management can be used to prevent seller agents from behaving dishonestly. The proposed spectral clustering scheduling scheme aims at maximizing processor utilization efficiency, while simultaneously minimizing the tasks’ QoS degradation. Task QoS is specified through the requested start and finish times, while QoS degradation is expressed through a time deviation metric D. Resource assignment is viewed as a normalized cuts spectral graph partitioning problem. The algorithm defines a nonoverlapping measure between tasks, and then uses a matrix representation, the notion of generalized eigenvalues, and the Ky-Fan theorem to perform scheduling (graph partitioning) in the relaxed continuous space. The solution of the continuous relaxation is then rounded to a discrete solution.

REFERENCES

1. Do slas really matter? 1-year case study.
2. Mohammad Alrifai, Dimitrios Skoutas, and Thomas Risse. Selecting skyline services for QoS-based web service composition. Proceedings of the 19th international conference on World wide web – WWW ’10, page 11, 2010.
   CrossRef
3. Danilo Ardagna and Barbara Pernici. Global and local qos constraints guarantee in web service selection. pages 805–806, 2005.
   CrossRef
4. Luciano Baresi, Sam Guinea, and Giordano Tamburrelli. Towards decentralized self-adaptive component-based systems. Proceedings of the 2008 international workshop on Software engineering for adaptive and self-managing systems – SEAMS ’08, page 57, 2008.
   CrossRef
5. B. Benatallah, M. Dumas, Q.Z. Sheng, and a.H.H. Ngu. Declarative composition and peer-to-peer provisioning of dynamic Web services. Proceedings 18th International Conference on Data Engineering, pages 297–308, 2002.
   CrossRef
6. J.P. Brans and Ph. Vincke. A preference ranking organization method: The promethee method for multiple criteria decisionmaking. Management Science, 31(6):647–656, June 1985.
   CrossRef
7. Ivan Breskovic, Christian Haas, Simon Caton, and Ivona Brandic. Towards self-awareness in cloud markets: A monitoring methodology. pages 81 –88, dec. 2011.
8. R Buyya and S Pandey. Cloudbus toolkit for market-oriented cloud computing. In Proceedings First International Conference, CloudCom 2009, pages 22–44, 2009.
   CrossRef
9. Rajkumar Buyya, Chee Shin Yeo, and Srikumar Venugopal. Market-Oriented Cloud Computing: Vision, Hype, and Reality for Delivering IT Services as Computing Utilities. 2008 10^th IEEE International Conference on High Performance Computing and Communications, pages 5–13, September 2008.
10. Gerardo Canfora, Massimiliano Di Penta, Raffaele Esposito, and Maria Luisa Villani. An approach for QoS-aware service composition based on genetic algorithms. Proceedings of the 2005 conference on Genetic and evolutionary computation – GECCO ’05, page 1069, 2005.
    CrossRef
11. Jorge Cardoso, Amit Sheth, and John Miller. Workflow quality of service. Technical report, University of Georgia, Athens, Georgia, USA, March 2002.
    CrossRef
12. Jorge Cardoso, Amit Sheth, John Miller, Jonathan Arnold, and Krys Kochut. Quality of service for workflows and web service processes. Web Semantics: Science, Services and Agents on the World Wide Web, 1(3):281–308, April 2004.
13. B Cheng, R De Lemos, Holger Giese, and Paola Inverardi. Software engineering for self-adaptive systems: A research roadmap. Software Engineering, pages 1–26, 2009.
14. Shang-Wen Cheng, David Garlan, and Bradley Schmerl. Architecture-based self-adaptation in the presence of multiple objectives. Proceedings of the 2006 international workshop on Selfadaptation and self-managing systems – SEAMS ’06, page 2, 2006.
    CrossRef
15. SW Cheng and David Garlan. Making self-adaptation an engineering reality. Self-star Properties in Complex Information Systems: Conceptual and Practical Foundations, 3460:158–173, 2005.
16. Scott H. Clearwater, Rick Costanza, Mike Dixon, and Brian Schroeder. Saving energy using market-based control. pages 253– 273, 1996.
    CrossRef
17. D Cliff. Simple bargaining agents for decentralized market-based control. HP Laboratories Technical Report, 1998.
18. Giovanna Di Marzo Serugendo, Marie-Pierre Gleizes, and Anthony Karageorgos. Self-organization in multi-agent systems. The Knowledge Engineering Review, 20(02):165–189, June 2005.
19. Elisabetta DiNitto, Carlo Ghezzi, Andreas Metzger, Mike Papazoglou, and Klaus Pohl. A journey to highly dynamic, selfadaptive service-based applications. Automated Software Engineering, 15(3-4):313–341, September 2008.
    CrossRef
20. Leticia Duboc, David Rosenblum, and Tony Wicks. A framework for characterization and analysis of software system scalability. Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering – ESEC-FSE ’07, page 375, 2007.
    CrossRef
21. Torsten Eymann, Michael Reinicke, Oscar Ardaiz, Pau Artigas, Luis D´ıaz de Cerio, Felix Freitag, Roc Messeguer, Leandro Navarro, Dolors Royo, and Kana Sanjeevan. Decentralized vs. centralized economic coordination of resource allocation in grids. In European Across Grids Conference, volume 2970 of Lecture Notes in Computer Science, pages 9–16. Springer, 2003.
22. Daniel Freidman. The double auction market institution: A survey. 1993.
23. Dhananjay K. Gode and Shyam Sunder. Allocative efficiency of markets with zero-intelligence traders: Market as a partial substitute for individual rationality. The Journal of Political Economy, 101(1):119–137, 1993.
    CrossRef
24. Alok Gupta and DO Stahl. The economics of network management. Communications of the ACM, 42(9):57–63, 1999.
    CrossRef
25. Kieran Harty and David Cheriton. A market approach to operating system memory allocation. pages 126–155, 1996.
    CrossRef
26. Minghua He and Nicholas R. Jennings. Southamptontac: An adaptive autonomous trading agent. ACM Trans. Internet Technol., 3:218–235, August 2003.
    CrossRef
27. Minghua He, N.R. Jennings, and Ho-Fung Leung. On agentmediated electronic commerce. Knowledge and Data Engineering, IEEE Transactions on, 15(4):985 – 1003, july-aug. 2003.
28. BM. An architectural blueprint for autonomic computing. June 2006.
29. Amazon Inc. Amazon spot-instances. December 2009. http://aws.amazon.com/ec2/spot-instances/.
30. Nick Jennings. Automated haggling: building artificial negotiators. pages 1–1, 2000.
31. Jeffrey O. Kephart and David M. Chess. The vision of autonomic computing. Computer, 36(1):41–50, January 2003.
    CrossRef
32. Paul Klemperer. Auction theory: A guide to the literature. JOURNAL OF ECONOMIC SURVEYS, 13(3), 1999.
    CrossRef
33. Arthur Koestler. The ghost in the machine. 1989. ISBN 0-14- 019192-5.
34. MM Kokar and K Baclawski. Control theory-based foundations of self-controlling software. Self-Adaptive Software and their Applications, IEEE Intelligent Systems, 1999.
    CrossRef
35. Robert Laddaga. Creating robust software through selfadaptation. IEEE Intelligent Systems, 14:26–29, May 1999.
    CrossRef
36. Makoto Matsumoto and Takuji Nishimura. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul., 8:3–30, January 1998.
    CrossRef
37. Anton Michlmayr, Florian Rosenberg, Philipp Leitner, and Schahram Dustdar. Comprehensive qos monitoring of web services and event-based sla violation detection. pages 1–6, 2009.
    CrossRef
38. Vivek Nallur and Rami Bahsoon. Design of a Market-Based Mechanism for Quality Attribute Tradeoff of Services in the Cloud . In Proceedings of the 25th Symposium of Applied Computing(ACM SAC). ACM, 2010.
39. Jinzhong Niu, Kai Cai, Simon Parsons, Enrico Gerding, and Peter McBurney. Characterizing effective auction mechanisms: insights from the 2007 tac market design competition. pages 1079–1086, 2008.
40. Jinzhong Niu, Kai Cai, Simon Parsons, Peter McBurney, and Enrico Gerding. What the 2007 tac market design game tells us about effective auction mechanisms. Autonomous Agents and Multi-Agent Systems, 21:172–203, 2010. 10.1007/s10458-009-9110-0.
    CrossRef

---

This work is licensed under a Creative Commons Attribution 4.0 International License.