Kyriakos Kritikos
email: kritikos@ics.forth.gr

Dimitris Plexousakis

Towards Combined Functional and Non-Functional Semantic Service Discovery

Keywords: service, discovery, matchmaking, semantics, ontology, performance, evaluation, functional, non-functional, QoS, architecture

Service-orientation is increasingly adopted by application and service developers, leading to a plethora of services becoming increasingly available. To enable constructing applications from such services, respective service description and discovery must be supported by considering both functional and non-functional aspects as they play a significant role in the service management lifecycle. However, research in service discovery has mainly focused on one aspect and not both of them. As such, this paper investigates the issues involved in considering both functional and non-functional aspects in service discovery. In particular, it proposes different ways via which aspect-specific algorithms can be combined to generate a complete service discovery system. It also proposes a specific unified service discovery architecture. Finally, it evaluates the proposed algorithms' performance to give valuable insights to the reader.

Introduction

Nowadays, modern applications and business processes adopt service-orientation due to the many advantages it delivers, including loose coupling, re-usability, increased performance and cost reduction. To construct such applications, the services from which they are built need to be described appropriately, discovered and finally composed. Concerning service discovery, the state-of-the-art can be split into approaches that either focus on functional or non-functional aspects.

Functional service discovery work [START_REF] Klusch | Semantic Web Service Coordination[END_REF] matches user's functional requirements by exploiting various types of techniques from information retrieval and the semantic web [START_REF] Klusch | OWLS-MX: A hybrid Semantic Web service matchmaker for OWL-S services[END_REF]16]. Functional requirements and capabilities are mainly described via service IO while some work [START_REF] Klein | Coupled Signature and Specification Matching for Automatic Service Binding[END_REF] covers behavioral aspects via service preconditions and effects which are however not available in real service advertisements. Most work nowadays exploits semantic techniques to exhibit better accuracy levels and other techniques to achieve performance speedup. However, the discovery accuracy is imperfect due to non-consideration of behavioural aspects.

Non-functional service discovery work [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] can be split into three main categories. Ontology-based approaches [START_REF] Zhou | DAML-QoS Ontology for Web Services[END_REF] employ subsumption techniques to infer the matching between ontology-based non-functional service descriptions but are suitable for unary-constrained specifications. Constraint-based approaches [START_REF] Cortés | Improving the Automatic Procurement of Web Services Using Constraint Programming[END_REF] exploit n-ary specifications as models, including quality terms drawn from common vocabularies, and particular metrics which involve solving one or more constraint (combined) models to infer the matchmaking. Mixed approaches [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] combine the best of both worlds by exploiting ontology-based specifications to cover the non-functional semantics and align the quality terms involved as well as the metrics in the previous approach type to perform the service matchmaking.

While each aspect is more or less well covered in literature, very few approaches [START_REF] Benaboud | Agents and owl-s based semantic web service discovery with user preference support[END_REF][START_REF] Jiang | An Approach to Integrated Semantic Service Discovery[END_REF] deal with both aspects concurrently. Such approaches, however, do not adopt the best possible algorithm for each aspect, do not capture service semantics, and do not have a suitable performance and accuracy level. Moreover, they have not explored the possible ways the two different types of matching can be best combined to infer the best possible one. In fact, most of these approaches employ a simplistic approach to account for non-functional user requirements and preferences which will never be adopted by respective practitioners.

As such, this paper first proposes a unified architecture explicating how different-aspect algorithms can be integrated to support a complete service discovery process by also accommodating for semantics capturing. Then, the paper proposes different combinations of aspect-specific algorithms attempting to accelerate the overall matching performance by not compromising discovery accuracy. Some combinations might be naturally applied and easily realised while others attempt to intelligently organise the service advertisement space to reduce the matchmaking time. These combined algorithms are finally evaluated by a semi-randomised framework according to their performance so as to provide particular insights on which is the preferred one in different circumstances.

The rest of the paper is structured as follows. Section 2 reviews the related work. Section 3 presents the unified architecture. Section 4 analyses the proposed combined algorithms. Section 5 presents the performance evaluation results. Finally, Section 6 concludes the paper and draws directions for further research.

Related Work

As we focus on combined service discovery, we only consider combined approaches. For aspect-based discovery analysis, the reader can refer to [START_REF] Klusch | Semantic Web Service Coordination[END_REF] and [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF].

QoS Ranking. By reviewing related work, it seems that most approaches [START_REF] Lemos | Adding Non-functional Preferences to Service Discovery[END_REF][START_REF] Makris | Efficient and Adaptive Discovery Techniques of Web Services Handling Large Data Sets[END_REF][START_REF] Mokhtar | EASY: Efficient semAntic Service discoverY in pervasive computing environments with QoS and context support[END_REF] first functionally match the service request and then rank the respective matches based on the user's non-functional preferences. Non-functional ranking usually relies on considering utility functions that depend on the respective quality term monotonicity while the overall rank is produced via a weighted sum of the application of the utility functions over the match's promised quality term values. Based on the above, it seems that all such approaches neglect the fact that a user may pose non-functional requirements which must be respected such that the functional matches are further filtered before they are ranked.

The approach in [START_REF] Mokhtar | EASY: Efficient semAntic Service discoverY in pervasive computing environments with QoS and context support[END_REF] caters for ontology encoding and fast reasoning issues. It attempts to smartly organise the functional advertisement space by exploiting two advertisement relations that seem to map to well-known functional degrees of match. However, the second relation seems not to be suitable based on the formal notion of subsumption. After cleverly matching a request, the functional matches produced are just ranked based on their non-functional degree of match.

The sequential approach in [START_REF] Makris | Efficient and Adaptive Discovery Techniques of Web Services Handling Large Data Sets[END_REF] starts by discovering services that functionally match the request and have an appropriate distance from the user to minimise network latency. Then, the expected execution time of each matched service is computed based on performance ratings which is finally exploited to rank the matched services and select the top one for dynamic adaptation reasons.

QoS Threshold-Based Filtering. A small improvement over the previous category comes via threshold-based filtering of functional matches [START_REF] Jiang | An Approach to Integrated Semantic Service Discovery[END_REF][START_REF] Pathak | URBE: Web Service Retrieval Based on Similarity Evaluation[END_REF]. However, it is questionnable whether a simple threshold can be enough to respect the semantics of all non-functional requirements posed. It rather seems as a trial-and-error approach towards attempting not to overwhelm users with irrelevant results not satisfying their non-functional requirements. What makes the approach in [START_REF] Jiang | An Approach to Integrated Semantic Service Discovery[END_REF] more interesting with respect to the rest in this category is that it attempts to enable a unified semantic service description and considers various types of information to infer the ranking, including QoS, business policies and context.

Combined. [START_REF] Benaboud | Agents and owl-s based semantic web service discovery with user preference support[END_REF] proposes a sequential combined algorithm coupled with service ranking based on non-functional preferences. This algorithm actually resembles SeqOnTheFly (see Section 4) as it attempts to match on the fly each functional result with the user's non-functional requirements. However, this work is not assorted with specification validation mechanisms and does not employ specification alignment, thus relying on a common quality term vocabulary. It does not also check how sequential matching can be enhanced for better performance.

In [START_REF] Charrad | A Semantic and QoS-aware Broker for Service Discovery[END_REF], a three step discovery process is proposed. First, functional matching is performed by exploiting subsumption hierarchy and predicate-based inferencing. Second, functional matches are clustered based on QoS via the average linkage clustering and squared Euclidian distance metrics. Third, the best cluster's matches are ranked based on each match's distance from the cluster centroid. This approach is regarded as combined as it performs a kind of filtering on the functional match space. However, it is questionnable whether such a filtering is suitable if we also consider performance aspects. In addition, semantics for QoS terms are neglected. Functional matching seems also to be wrongly performed.

Architecture

Figure 1 depicts the architecture of a complete and unified service discovery system by also showing the interactions between the respective components and their ordering in terms of basic discovery system operations. The architecture comprises 10 main components: 2 constitute entry points, 4 map to the main discovery logic and 4 relate to the respective individual and combined registries. Front-end is the first entry point, a web-based UI interacting with a human user, either a service provider or requester. It visualises information assisting the respective interaction, such as forms to specify functional and non-functional requests or to enable providers to upload, register or update service descriptions.

The REST-API is a service-based component enabling programmatic interaction with automated agents acting on behalf of users. It exposes the functionality expected in a service discovery system, like registering, updating and matching service specifications. It also offers utilities that validate the specifications before being registered. Service provider-related functionalities are only available to registered users, while discovery ones are publicly available with additional features only offered to registered users, like the ability to retrieve all matchmaking results and provide customised algorithms for service selection.

Once one operation starts execution, the respective specifications are passed to Specification Processor which loads and processes them to check their syntactic and semantic validity as well as to align them if they refer to equivalent but differently described terms. Constraint-based consistency is also checked for non-functional specifications. In case of a validation error, an error message is relayed to the user. Otherwise, operation passes to the core discovery component, the Compositor. Specification alignment is performed by consulting a Term and Ontology Store which includes a common set of basic terms via which alignment can be rapidly performed (see [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]) as well as the domain ontologies encountered.

Compositor realises the composition logic with respect to the individual aspect-specific algorithms exploited. It also guarantees the consistency of the information being registered in these algorithms. This is achieved via the Combined Registry storing the mappings between functional and non-functional specifications of service providers. This integration approach enables decoupling the aspect-specific discovery functionality and independence from any service specification language. Language adoption is coupled with selecting an aspect-specific algorithm. As such, we cater for using either unified or aspect-specific service description languages. In case the latter language type is used, consistency is maintained via the entries of the Combined Registry. We aim at semantic languages for which any service profile kind is identified via a URI. This enables using only semantic algorithms but leads to increased discovery accuracy.

The Compositor implements the combined service matching logic with respect to the main algorithms proposed (see Section 4). It also guarantees the transactionality of service (de-)registration and update operations. This means that if an operation fails when executed via a specific aspect-specific sub-system, and is successful with respect to the other sub-system, we have to roll-back to the previous state before operation execution. The latter maps, e.g., to deregistering a functional service specification if its non-functional counterpart fails to be registered. This transactionality type is enabled by realistically assuming that each respective aspect-specific sub-system provides aspect-specific operations that return either boolean values indicating the operation outcome (e.g., non-registration as functional service specification already exists) or exceptions when errors occur. The respective suite of functionally-equivalent service operations is obviously already available in each aspect-specific system.

Each aspect-specific sub-system should provide an entry point via which aspect-specific interactions can be performed (either a programmatic REST-API or a specific component). For the two main aspects, we name the respective components as Functional Service Discovery and Non-Functional Service Discovery. We do not unveil their structure as it can be specific to the sub-system selected. We just unveil that each sub-system logically has a (functional / non-functional) store in which aspect-specific service specifications are stored.

Concerning implementation details, all system code was realised in Java as it is the main implementation language for almost all matchmakers. Front-End implementation is on-going while the REST-API was realised via Jersey. The Specification Processor exploits different loading and validation techniques. The Pellet reasoner [START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF] is exploited for ontology-based loading and consistency checking. The Ibex (www.ibex-lib.org) finite constraint and Choco (http: //www.choco-solver.org/) constraint programming solvers are exploited for constraint-based consistency checking. The Combined Registry is a serialisable Java object which exposes different methods related to manipulating aspectspecific specifications (e.g., registering a functional and non-functional service URI pair or an additional non-functional profile for an existing service).

Alive Matchmaker [START_REF] Cliffe | Service Matchmaking Framework[END_REF] was selected as a state-of-the-art functional matching sub-system which exhibits high performance levels due to applying smart structures via which the matching of semantic I/O concepts can be performed while also catering for domain ontology evolution. The Unary algorithm of the discovery system in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] was selected for hybrid non-functional service matching as it is scalable, exhibits high performance levels and has perfect accuracy.

Algorithm Analysis

Combining aspect-oriented matching algorithms was explored under different criteria. The first one concerns the expected way to combine two functionalities, where two possible ways exist: (a) each functionality is performed in sequence or (b) both functionalities are executed in parallel and their results are integrated.

Concerning (a), we chose to execute first the functional discovery algorithm as this more naturally depicts the process executed by humans who first seek to satisfy their functional requirements and then the non-functional ones. Functional service discovery can also be considered more restrictive than non-functional one. This can be due to the fact that when performing non-functional matching, domain-independent metrics are usually considered leading to obtaining many functionally irrelevant results out of the respective domain scope. As such, when no results are discovered in the first discovery form, there is no reason to continue with the non-functional one spending unnecessary resources.

Solution (b) attempts to execute the aspect-specific discovery algorithms in parallel to save time. Compared to the first approach, it may spend more resources but it will be surely faster, provided that when one aspect-based discovery algorithm ends earlier with not result, we can stop the other one.

The second criterion explored exploiting different structures to smartly organise the service advertisement space to speed-up service matching. By relying on the approach in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF], we have considered combined subsumes relations between different service discovery offers (where a discovery offer maps to one functional and non-functional offer pair for one service) enabling us to not browse the whole advertisement space but stop at certain places without requiring to go down in respective subsumes branches. Figure 2 depicts the notion of a subsumes service advertisement hierarchy via a small forest of 4 offers. Offer O 1 subsumes offers O 11 and O 12 for different reasons. Offer O 11 is subsumed due to its functional part (its non-functional part is equivalent) while offer O 12 is subsumed due to its non-functional part (its functional part is equivalent). Offer O 2 is not related to the tree's offers as it possesses an unrelated functional part. This also highlights the definition of the combined subsumes relation: comb subsumes (S 1 , S 2 ) ≡ f unc subsumes (S 1 , S 2 ) ∧ nonf unc subsumes (S 1 , S 2 ) By exploiting this subsumption relation, we speed up the service matching process. For example, assume that request R is issued. We will first compare it with offer O 1 . If R subsumes O 1 , it also subsumes its descendants. As such, we do not have to go deeper into the respective tree. However, we need to also check other trees in the forest which could be partially related to each other. There are two relation kinds to be exploited: subsumes and the opposite one, subsumedBy. Based on the empirical evaluation in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF], the first relation is more suited when more than 30 percent of the offers match a request. Otherwise, the second relation is more suitable. By combining functional and non-functional service matching, we expect that the percentage of matched offers can be lower than in the case of aspect-specific matching. In this way, it might be preferrable to exploit the subsumedBy relation in the end, especially for a highly populated service registry spanning multiple domains as each request is expected to be specific to just one domain and thus lead to matching of a quite low offer percentage. Fig. 2: The subsumption forest with request R subsuming a root tree node

In the sequel, a small section is first provided explaining the main symbols and assumptions made. The next four subsections shortly analyse the proposed algorithms' functionality for service registration and discovery by also providing a respective complexity analysis. Other operation types (e.g., deletion and updating) are not considered as they tend to map either to similar actions as in case of registration (i.e., deletion) or to a two actions sequence (i.e., updating by combining deletion and insertion). Finally, the last section discusses the expected performance of the proposed algorithms based on the complexity analysis.

Symbols & Assumptions

We assume that one functional and non-functional comprise the service request. We also assume that S service offers have been registered. This means that around S 3 functional offers are to be registered in a functional matchmaker and S non-functional offers in the non-functional one as each functional offer is expected to be accompanied by 3 non-functional offers for the same service, mapping to gold, silver and bronze classes of customers. Functional offer preprocessing takes O (1) while for a non-functional offer takes O (2M + M * T z ), where the first part maps to the offer's consistency checking and the second to its alignment; M represents the number of the offer's quality terms. The latter can be reduced to O (M * T z ) constituting the total pre-processing time. Finally, we assume that each non-functional offer comprises at most 2M constraints mapping to the upper and lower bounds given for each quality term.

Sequential Algorithm

Analysis Matchmaking. We propose two main algorithm variations named as: Sequential and SeqOnTheFly. The first version first performs functional service discovery; then it fetches the respective non-functional offers from the functional results, registers them to the non-functional matchmaker and matches them with the non-functional request part. Finally, it returns back the ending results to the user and clears the non-functional matchmaker. On the other hand, the second version checks on the fly whether the non-functional offers mapping to the matched functional ones are subsumed by the request's non-functional part. We expect that the first version is more suitable when non-functional offers are great in number as the total registration time will be compensated by the fast matching via the matchmaker's smart structures. Otherwise, the second version should be preferred. Section 5 will explore which is the amount of non-functional offers that represents the break point between choosing one over the other version.

Registration. Both algorithm versions follow the same registration process by registering the functional offer in the functional matchmaker and inserting the respective combined entry in the Combined Registry. Non-functional-based registration is not needed due to the way the non-functional matchmaker is exploited. The pre-requisite processing step for specifications controls their validity and transactionally rolls back the combined registration, if needed.

Complexity analysis

Matchmaking. We rely on the complexity analysis of the aspect-specific matchmakers and on the fact that the request validity has to be checked. Pre-processing as already stated takes O (M * T Z ).

The functional matching part [START_REF] Cliffe | Service Matchmaking Framework[END_REF] For normal non-functional matching, in the worst case, covering both registration and matching of non-functional offers, the time will be O

(M * (M F O + 2 * log M F O )).
For on the fly non-functional matching, O (2M * M F O ) time is needed as we must check each constraint of a non-functional offer with the request nonfunctional part's respective constraint. Thus, in the end, the matchmaking time for Sequential will be O

(R O * S * R AO + (M * (M F O + 2 * log M F O )) + M * T Z ).
If we consider that M is small and cannot go beyond 10 quality terms and that S is much bigger than M F O , the complexity formula can be reduced to:

O (R O * S * R AO + T Z ).
For SeqOnTheFly, the matching time will be

O (R O * S * R AO + (2M * M F O ) + M * T Z ) which can be similarly reduced to O (R O * S * R AO + T Z ).
Thus, in the end, the matching complexity for both algorithm versions coincides.

Registration. One functional and its respective 3 non-functional offers are to be registered. Thus, we need to pre-process 4 specifications and only register via the functional matchmaker the functional offer. Pre-processing takes again O (M * T Z ) as in matchmaking. Functional registration takes O (S C ) as in the worst case is dominated by the time needed to infer the subsumption hierarchy of the domain ontology mapping to the service I/O, where S C represents this time for an ontology of C concepts. Thus, registration time for both algorithm versions will be O (T Z + S C ).

Parallel Algorithm

Analysis Matchmaking is performed, after user request is pre-processed and aligned, by exploiting in parallel the functional and non-functional matchmakers and then concatenating their results. The exploitation of the Combined Registry to map functional matches to their non-functional counter-parts (which can be 3 times their number) guarantees the concatenation of the same type of objects.

For registration, we register in parallel the functional offer and non-functional part in the functional and non-functional matchmakers, respectively. The respective consistency is achieved by informing the Combined Registry.

Time Complexity Analysis Matchmaking. Pre-processing as in the previous algorithm takes O (M * T Z ). Functional matching, as already stated, takes O (R O * S * R AO ). Non-functional matching takes O (M * (S + log S )). Concatenating the different result types takes: O (M F O ). In the end, the total matchmaking time will be:

O (max (R O * S * R AO , M * (S + log S )) + M F O + M * T Z )
which can be further reduced to: O (S + T Z ).

Registration. Functional registration takes O (S C ) as indicated in the previous algorithm. Non-functional registration takes O (M * log S ). Thus, total registration time will be O (max (S C , M * (log S + T Z ))) which can be reduced to O (max (S C , log S + T Z )).

Subsumes Algorithm

Analysis Matchmaking. It is recursively performed [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]. The offer is matched with each root node. If it subsumes the node, it also subsumes its children. As such, we just consider this node and its descendants as matches. Otherwise, we must descend this hierarchy recursively to find respective matching nodes. All matching results for each root node search (including recursive calls) are finally collected to be returned to the user.

Registration. It is recursively performed [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]. First, each root node is checked with the offer to be matched. If the offer is equivalent to the node, it is entered into the node's represented offers and registration ends. If the offer subsumes the node, it becomes its parent. If the root node subsumes the offer, the same checking is performed recursively at the node's children. When at the root node's subsumption hierarchy the offer is subsumed by one node but does not subsume its children, the offer is entered as a child of this parent node.

Complexity Analysis Matchmaking. 3 cases hold [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]. In the worst case, we perform functional and non-functional subsumption checking for all forest nodes. In functional subsumption checking, we expand each output concept of the functional offer with respect to its ancestor concepts in O (1) step and check if each output concept of the functional request is inside one of the expanded lists. This takes O (R O * S O ) for each functional offer. For non-functional subsumption checking, we chech if each offer constraint is more restrictive that the respective demand constraint. This takes O (2 * M ) as for each offer constraint, we immediately find the request counter part. So, individual subsumption checking takes O (R O * S O + 2M ). By visiting all S nodes and accounting processing time, total matching time is:

O (S * (R O * S O + 2M ) + M * T Z ).
As both R O and R O tend to be small and M is less than 10, this reduces to just O (S + T Z ).

In the best case, only the sole root node is matched (forest reduced to a tree) which takes O (S + T Z ). In the average case, we expect that the tree is more or less balanced, a percentage of P nodes is subsumed and there is always a pair of parent-child offers. In this case, total matching will taje: O S * 1 -P 2 + T Z . Registration. Three cases are also considered. For all cases, we need to do preprocessing but also account for ontology subsumption-based structure updating. This maps to O (S C + T Z ). In the best case, the first root node compared with the new offer is equivalent to it. This ends up doing two comparisons (one for node-to-offer subsumption and one for offer-to-node subsumption) and translates to O (2 * (S * (R O * S O ) + 2M )). Thus, in total, the time will be O (S C + T Z ).

In the worst case, we have a single tree and the offer has to be inserted in the rightmost leaf. This maps to performing twice the subsumption checking over all tree nodes which will map to O (S + S C + T Z ) in the end.

In the average case, we will have B balanced trees and the offer has to be inserted in the middle of the median tree. This will map to S+B 2 2B subsumption checks which will then map in the end to a total time of:

O S+B 2 2B + S C + T Z

SubsumedBy Algorithm

Analysis subsumedBy is opposite to subsumes. We organise the offer hierarchy in this way to cater for the case that a very small offer number matches a request to be placed in the hierarchy's leaves (as subsumption maps to something more restricted or specific so less matches means more restricted matches).

Matchmaking. It is performed by matching the request with the root nodes based on the subsumes relation. If there is no match, there is no need to go down the root node's hierarchy (as either there is no relation at all or the request is subsumedBy the root node). Otherwise, we include the root node in the final matches and visit its children recursively. All matching results from each (recursive) root node search are finally collected and returned to the user.

Registration. It is symmetric to Subsumes. We check first the root nodes. An offer equivalent to a root node is included in the offers represented by the node and registration ends. If the offer is subsumed by this node, it becomes the node's parent. If it subsumes the node, we go recursively to the node children.

The offer finally becomes a child of a root node descendant or a forest root (in case it is unrelated to any root node or subsumed by one or more root nodes).

Complexity analysis

Matchmaking. The same complexity as in Subsumes holds for the best and worst cases. The sole exception is the conditions mapping to these cases. In the best case, the sole root node is not subsumed by the request. In the worst case, all non-subsumed nodes by the request lie in the forest leaves and do not represent more than one offer. In average, the same assumptions hold as in Subsumes. This, however, maps to matching the request with O S * P +1 2 nodes which finally maps to the total matching time of: O S * P +1 2 + T Z Registration. This process is identical to that of Subsumes concerning the best and worst cases, so the respective time complexity is the same. The same holds for the conditions mapping to worst, best and average cases.

Discussion

Concerning matchmaking, based on the time complexity analysis, it seems that in the worst case the Parallel algorithm is the best followed by Sequential and then the subsumes-based algorithms. However, in the average case, if there is some kind of subsumption hierarchy between the different nodes, it might be the case that the subsumes-based algorithms have the best possible performance and the best algorithm can depend on the percentage of offers being matched.

Concerning registration time, the performance order seems to be clearer as the Parallel algorithm must have the best performance followed by the sequential and then the subsumes-based algorithms. So, there is a clear winner plus a performance trade-off between matchmaking and registration for the second place where different algorithms are nominated as best for different operations.

Evaluation

The evaluation was performed via the experimental framework in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF], covering the non-functional aspect and being able to generate in a controlled manner both randomised and real non-functional service specifications, as well as the OWL-STC framework, covering the functional aspect with real or realistic functional service specifications along with ways to measure functional discovery accuracy. The main goal was to evaluate the algorithms' average matchmaking and registration performance. Accuracy is neglected due to the following reasons: (a) non-functional matchmakers have perfect accuracy [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]; (b) accuracy results will be identical to those of the functional matchmaker exploited that have already been reported. The target is to discover those circumstances that the selection of a specific algorithm from those proposed is recommended. We also consider the AliveMM functional matchmaker so that we are enabled to compare the overall matchmaking time with respect to the functional part and unveil the degree in which the latter influences the former.

In the sequel, we explicate the way the sole experiment was conducted based on the experimental framework and then discuss the experiment results.

Experiment Set-Up and Control

Unified Framework Features. By combining aspect-specific experimental frameworks, we generate an overall framework with the capabilities to create in a controlled manner both functional and non-functional specifications. Functional specifications can either rely on the OWLSTC collection, to be as realistic as possible, or can be produced randomly [START_REF] Kritikos | Task model-driven realization of interactive application functionality through services[END_REF] via a domain ontology's concepts combined to produce the service I/O. Non-functional specifications rely on the WS-Dream [START_REF] Zhang | WSPred: A Time-Aware Personalized QoS Prediction Framework for Web Services[END_REF] and QWS [START_REF] Al-Masri | Investigating web services on the world wide web[END_REF] datasets or on generating randomised unary specifications that can include integer or real-valued metrics of different types and semantics. In the experiment conducted, we relied on OWLSTC and the randomised generation of non-functional specifications. Our choice for the nonfunctional aspect relates to the fact that the WS-Dream dataset is big but quite limited in the metric number while QWS is smaller. However, we desire to generate a much greater non-functional offer set with an increased metric number such that respective requests can also match a particular offer percentage.

Offer Generation. For each functional service offer, three non-functional offers were generated in a controlled manner. This resulted in generating around 3150 service offers (functional and non-functional pairs) provided that OWL-STC contains around 1050 functional service specifications. This also supports our main real-world assumption that each service can be associated to three non-functional offers catering for gold, silver and bronze customer classes. The offer number considered in each experiment step depended on a specific configuration parameter given as input to the specification generator. For instance, if this number is 100, we randomly take 100 functional offers from OWLSTC and couple each to 3 non-functional offers randomly generated such that the next non-functional offer has an increased performance and price with respect to the previous one to map to the different customer classes.

Experiment Set-Up. The experiment was conducted in a Windows 7 SSDbased machine with 2GHz dual-core CPU and 6 GB of RAM. It included conducting a set of steps in which one configuration parameter varied (the offer number) according to a specific range (50 to 1050 with an increase step of 200 for the functional offers). Each step was executed 30 times to produce the respective average matchmaking and registration time values of the considered algorithms such that any possible interference at the OS level is diminished.

Experiment Results

Figure 3 depicts the experiment results for matchmaking and registration time.

Concerning matchmaking time, the best algorithm is Parallel. The order for the rest is not stable. Initially, the sequential algorithms are better than the subsumes; this is reversed when the functional offer number is equal or above 650. This means that beyond a specific offer number, the offer hierarchy becomes more structured such that matching time can be really saved via a subsumes-based approach. This matches exactly our expectations for the subsumes algorithms. The partial order between the sequential algorithms is also unstable. Initially, as the number of non-functional offers to filter is small, SeqOnTheFly is slightly faster. However, beyond 650 functional offers, this is reversed as it becomes better to employ a non-functional matchmaker to register and match the non-functional offers rather than employ pair-wise non-functional filtering.

The subsumes algorithms are equivalent apart from the initial step where probably the matched offer number is quite small thus favouring SubsumedBy. This needs further investigation as we need to discover circumstances that one algorithm prevails over the other to assist practitioners in their selection.

The results produced validate the complexity analysis (especially with respect to the algorithm order) due also to corresponding OWLSTC features. In particular, a more or less stable algorithm performance is seen due to the small matched offer percentage and the small output parameter number per service. This leads to a more or less stable matching performance for the functional matchmaker as depicted in the results. Moreover, while the number of non-functional offers to be matched is greater in each step, the scalable non-functional matchmaker used enabled to reach almost equivalent performance levels. So, these matchmakers combination also leads to a stable matching performance.

Non-functional matching time takes more with respect to functional one. This is proven by comparing the functional matchmaker and Parallel algorithm performance. Thus, non-functional matching has still space for further optimisation. This also indicates that it is always proper for a sequential matchmaker to first filter based on the functional aspect and then the non-functional one. This is an interesting result to be accounted by researchers and practitioners.

Concerning registration time, the best algorithm is again Parallel followed by the sequential ones. The difference between these algorithms is small but is big with respect to the subsumes ones. The complexity analysis also validated this. This means that probably the subsumes algorithms should not be used in cases when a high offer number is constantly registered or updated. However, it can also be acceptable in the rest of the cases. So, the use of these algorithms depends on the registry provider's preferences and constraints especially with respect to the main requirements of its clients, i.e., service providers and requesters.

No ordering between sequential and between subsumes algorithms can be inferred from the results. This is natural as the sequential algorithms rely on the same registration process. For the subsumes algorithms, by also relying on the matchmaking results, it seems that the structures produced are more or less similar, leading to almost the same registration time.

To conclude, we stress that the Parallel algorithm seems to be the best for both matchmaking and registration so it is undoubtly recommended as the ideal algorithm for service registry realisation. In case that a different algorithm is needed or preferred, then the recommendation will be towards the subsumes algorithms despite the fact that their behavior with respect to registration is the worst. However, for highly dynamic environments, it seems that the best choice will be the sequential algorithms as an alternative to Parallel due to their capability to also deal with the dynamicity in service updating.

Conclusions and Future Work

This paper has presented four algorithms which attempt to combine in a different way the facilities of functional and non-functional state-of-the-art service discovery algorithms. We believe that this investigation is genuine and really assists practitioners in choosing the algorithm that best matches their current situation. The respective algorithm evaluation has unveiled the circumstances in which each algorithm prevails based on performance aspects. Apart from these 4 novel algorithms proposed, we have also implemented an unified service discovery architecture covering both the functional and non-functional aspects. Such an architecture comprises components that not only perform core service discovery tasks but also specification validation and alignment. It also includes components that enable both a visual and a programmatic interaction with a human or software agents, respectively. The algorithm combination is performed such that transactionality of offer registration and updating is achieved.

Concerning future work, the following directions will be pursued. First, more thorough validation of the proposed algorithms to produce even more interesting performance insights. Second, completing the development of the service discovery architecture. Third, extending functional matching towards covering the service functional behaviour to further increase discovery accuracy in case respective formal service descriptions are in place. Finally, integrating the service discovery system in an existing service composition framework to enable a faster and more accurate service composition process.

Fig. 1 :

 1 Fig. 1: The architecture of the unified service discovery system

  requires O R O * S 3 * R AO + M F O * I M ean S , where R O , R AO represent the number of input and acceptable inputs of the request, respectively, S 3 represents the number of functional service offers registered, M F O the number of matched services based on their output and I M mean F O the mean number of inputs of each matched service. The latter can be reduced to O (R O * S * R AO ) as S 3 is expected to be much bigger than M F O and I M ean S could be at most 3. Non-functional matching time depends on the combined algorithm version. For each version, we assume that O (k * M F O ) non-functional offers must be matched, k non-functional offers for each functional match, based on our assumption for the mapping between functional and non-functional offers.

Fig. 3 :

 3 Fig. 3: Fig. (a) shows the experiment service matchmaking results while Fig. (b) the service registration ones

Acknowledgments This research has received funding from the European Community's Framework Programme for Research and Innovation HORIZON 2020 (ICT-07-2014) under grant agreement number 644690 (CloudSocket).


Javid Taheri
email: javid.taheri@kau.se

Albert Y Zomaya
email: albert.zomaya@sydney.edu.au

Andreas Kassler
email: andreas.kassler@kau.se

vmBBThrPred: A Black-Box Throughput Predictor for Virtual Machines in Cloud Environments

Keywords: Performance Prediction and Modeling, Throughput Degradation, Cloud Infrastructure

In today's ever computerized society, Cloud Data Centers are packed with numerous online services to promptly respond to users and provide services on demand. In such complex environments, guaranteeing throughput of Virtual Machines (VMs) is crucial to minimize performance degradation for all applications. vmBBThrPred, our novel approach in this work, is an application-oblivious approach to predict performance of virtualized applications based on only basic Hypervisor level metrics. vmBBThrPred is different from other approaches in the literature that usually either inject monitoring codes to VMs or use peripheral devices to directly report their actual throughput. vmBBThrPred, instead, uses sensitivity values of VMs to cloud resources (CPU, Mem, and Disk) to predict their throughput under various working scenarios (free or under contention); sensitivity values are calculated by vmBBProfiler that also uses only Hypervisor level metrics. We used a variety of resource intensive benchmarks to gauge efficiency of our approach in our VMware-vSphere based private cloud. Results proved accuracy of 95% (on average) for predicting throughput of 12 benchmarks over 1200 hours of operation.

Introduction

The demand for cloud computing has been constantly increasing during recent years. Nowadays, Virtualized Data Centers (vDCs) accommodate thousands of Physical Machines (PMs) to host millions of Virtual Machines (VMs) and fulfill today's large-scale web applications and cloud services. Many organizations even deploy their own private clouds to better manage their computing infrastructure [START_REF] Banga | Resource containers: a new facility for resource management in server systems[END_REF]. In fact, it is shown that more than 75% of current enterprise workloads are currently running on virtualized environments [START_REF] Hui | Where does the power go in a computer system: Experimental analysis and implications[END_REF]. Despite massive capital investments (tens to hundreds of millions of dollars) however, their resource utilization rarely exceeds 20% of their full capacity [START_REF] Hui | Where does the power go in a computer system: Experimental analysis and implications[END_REF][START_REF] Mars | Bubble-up: increasing utilization in modern warehouse scale computers via sensible co-locations[END_REF]. This is because, alongside its many benefits, sharing PMs also leads to performance degradation Fig. 1: Relative performance of eight applications when co-located with a Mem+Disk (unzipping large files) intensive application of sensitive co-located VMs and could undesirably reduce their quality of service (QoS) [START_REF] Lingjia | The impact of memory subsystem resource sharing on datacenter applications[END_REF]. Figure 1 shows relative throughput (with regard to their isolated run) of eight high resource demanding VMs when co-located with a background VM running a high Memory+Disk intensive application (unzipping large files). All VMs had 2vCPU, 2GB of RAM, and 20GB of Disk. For each test, VMs were pinned on the same set of CPUs/Cores and placed on the same disk to compete for CPU cycles, conflict on L1/L2/L3 memory caches, and interfere with each others' disk access. As it can be inferred Figure 1, despite being classified as resource demanding, five of these applications (eg, apache) could be safely co-located with the background resource intensive application (Mem+Disk)assuming that performance degradation of up to 10% is allowed. Nevertheless, a conservative view would separate/isolate all VMs to allocate them on separate PMs. This simple example shows/motivates that understanding, measuring, and predicting performance degradation is essential to identify VMs that can be safely co-located with minimum interference to each other. It also motivates the importance of designing effective affinity rules to guarantee optimal placement of VMs, and consequently maximize the overall performance of vDCs. This work is a major step to predict throughput, and consequently performance degradation of general purpose applications/VMs through profiling a variety of benchmarks under different working scenarios and resource limitations. Such profiles are then used to predict throughput of a VM only based on the amount of resources (CPU, Mem, and Disk) it is consuming as seen by the Hypervisor. We used 12 well-known benchmarks with different resource usage signatures (CPU/Mem/Disk intensive and various combinations of them) to run on three different PMs. Results were collected and used to model throughput, and consequently performance degradation. We finally aligned our results with actual throughput of these benchmarks to show the accuracy of our approach: VM Black-Box Throughput Predictor (vmBBThrPred).

Our contribution in this work can be highlighted as: unlike all available similar approaches, (1) vmBBThrPred uses only Hypervisor level metrics to predict throughput and performance degradation of a VM. No code/agent is required to be developed, installed, and/or executed inside VMs; (2) vmBBThrPred provides a systematic approach to formulate throughput of VMs; (3) vmBBThrPred uses a wider range of benchmarks (from pure CPU/Mem/Disk intensive benchmarks to various combination of CPU+Mem+Disk intensive ones) to produce such formulas; and (4) vmBBThrPred produces a polynomial formula for each application/VM so that its throughput can be directly and dynamically (online) calculated according to its current CPU, Mem, and Disk utilization.

The remainder of this paper is structured as follows. Section 2 reviews the related work. Section 3 explains the architecture of vmBBThrPred and elaborates on its components. Section 4 demonstrates vmBBThrPred's step-by-step procedures. Section 5 lays out our experimental setup. Results are discussed and analyzed in Section 6, followed by Conclusion in Section 7.

Related Work

The ever increasing popularity of virtualization [START_REF] Kundu | Application performance modeling in a virtualized environment[END_REF] in vDCs is probably one of the most significant paradigm shifts in the IT industry. Through virtualization, PM resources are partitioned for VMs to run services. Running a highly efficient vDC is however not a trivial task. Firstly, vDCs are envisaged to run several VMs on each PM assuming proper partitioning of its resources. Although resources like CPU and Network seem to be fairly partition-able, Mem and Disk are proven to be much more cumbersome. Secondly, vDCs need to provide accurate/online operational information to both administrators and users so that functionality of deployed services can be monitored, controlled, and ensured at all times. This requires identifying under-performing VMs -those who suffer the most because of co-location-immediately, effectively, and dynamically. This also demands the ability of vDC management systems to accurately -at least within acceptable margins-predict the performance of different VMs in various working scenarios; ie, isolated or co-located as well as under or free of resource contentions. This concern, in particular, seems to be more important than the other two because it could directly lead to further optimizations of the whole system as well as significant increase of the productivity of vDCs.

To date, many approaches are proposed to measure throughput, and consequently performance degradation of VMs in vDCs; they can be categorized into the following two main themes.

High-level (SLA) based measurements: Approaches in this group use high-level metrics to measure actual throughout of an application/VM (eg, the number of transactions a SQL server responds to per second) in its current situation. They all rely on developing tailor-made foreign agents/codes for each application, installing them in VMs, and giving them enough system privileges to collect and send out performance data.

Xu et al [START_REF] Xu | Autonomic resource management in virtualized data centers using fuzzy logic-based approaches[END_REF] proposed two Fuzzy based systems (global and local) to monitor resource utilization of workloads in VMs. The local system is an SLA sensor that is injected into a VM to directly compare its performance with the desired SLA, and request or relinquish resources (eg, CPU share) if required. The global controller receives all local requests and decides what VM should get more resources in cases of contention. Tested for CPU-intensive workloads, their selflearning fuzzy systems could efficiently tune itself to demand for "just right" amount of resources. Their approach however assumed that high-level SLAs (eg, http requests per second) can be accurately defined and measured per application/VM. Rao et al [START_REF] Rao | Vconf: a reinforcement learning approach to virtual machines auto-configuration[END_REF] proposed VCONF, an auto-configuration RL-based agent, to automatically adjust CPU and Memory shares of VMs to avoid performance degradation. They, too, used direct application measurements to generate efficient polices for their Xen based environment. Watson et al [START_REF] Watson | Probabilistic performance modeling of virtualized resource allocation[END_REF] used probabilistic performance modeling to control system utilization and response time of 3-tier applications such as RUBiS. They showed that CPU allocation of VMs are enough to control high level SLAs such as response time of applications. Caglar et al [START_REF] Caglar | Towards a performance interference-aware virtual machine placement strategy for supporting soft real-time applications in the cloud[END_REF] proposed hALT, an online algorithm that uses Artificial Neural Networks (ANNs) to link CPU and Memory utilization of CPU intensive applications/tasks in Google trace data to performance degradation of VMs. They used another ANN to recommend migration of VMs to assure QoS for Google services. For real deployments, they still need an agent to report "performance" of an application/VM to feed and train their ANNs. Bartolini et al [START_REF] Bartolinibartolini | Automated fine-grained cpu provisioning for virtual machines[END_REF] proposed AutoPro to take a user-defined metric and adjust VMs' resources to close the gap between their desired performances and their current ones. AutoPro uses a PI controller to asymptotically close this gap and can work with any metric -such as frame/s, MB/s, etc.-as long as developers can provide it.

Approaches in this group are generally more accurate than others because they use direct measurements/feedback from applications inside VMs. Their usage however could be very limited, because (1) they all rely on an inside tailormade agent to report the exact throughput of an application/VM, and (2) their focus is mostly to improve performance of VMs rather than modeling throughput of applications/VMs according to their resource utilization.

Low-level (resource) measurements: Approaches in this group use lowlevel metrics (eg, CPU utilization) to predict throughput (eg, the response time of a web-server) of an application/VM in its current situation. They too rely on developing tailor-made foreign agents/codes for each application/VM, installing them in the VM, and giving them enough system privileges to collect and send out performance data.

Q-cloud [START_REF] Nathuji | Q-clouds: managing performance interference effects for qos-aware clouds[END_REF] uses a feedback-agent inside each VM to report its CPU utilization. They used five CPU intensive application from SPECjbb [1] and showed that there are direct relations between the amount of CPU a VM uses with its actual throughput. Using a MIMO linear model, authors then model interference of CPU intensive applications and feedback "root" in Hyper-V to adjust CPU allocations of VMs to improve their performances. Du et al [START_REF] Du | Performance profiling of virtual machines[END_REF] proposed two profiling agents to collect guest-wide and system-wide performance metrics for developers so that they can accurately collect information about their products in KVM-based virtualized environments. They did not use any specific benchmark, but simple programs to engage different parts of a system.

Approaches in this group generally predict throughput of an application/VM in relation to its resource utilization, although mostly to avoid performance degradations rather than modeling and predicting throughput. Also, although these approaches can be easily modified to use Hypervisor level metrics -instead of reports from their inside agents-to predict applications' throughout, their focus on only CPU or Disk intensive applications makes them non-generalizable.

After close examination of many techniques presented to date, we have noticed the following shortcomings. Firstly, many techniques require an agent/code to be injected to a VM to report either its throughput or its performance data. The need to have access to VMs and permission to run tailor-made foreign codes is neither acceptable not practical in most general cases. Secondly, many techniques aim to predict throughput of an application only to avoid contention by using/controlling one resource type (CPU, Mem, or Disk). Finally, most approaches target known applications that do not have multidimensional resource demands: they are pure CPU, Mem, or Disk intensive.

To address these shortcomings, we designed vmBBThrPred to directly model and formulate throughput of an unknown application/VM according to its resource usages. vmBBThrPred is an application-agnostic non-intrusive approach that does not require access to the VM to run foreign agents/codes: it only uses Hypervisor level metrics to systematically relate multidimensional resource usage of a VM to its actual throughput, and consequently performance degradation for various working scenarios (free or under resource contention).

Architecture of vmBBThrPred

The key idea of vmBBThrPred is to use the sensitivity values of an application to model/formulate its throughout. vmBBProfiler, our systematic sensitivity analysis approach in [START_REF] Taheri | vmbbprofiler: A black-box profiling approach to quantify sensitivity of virtual machines to shared cloud resources[END_REF], was designed to pressure an unknown VM to work under different working scenarios and reveal its sensitivity to each resource type. vmBBProfiler calculates three sensitivity values (∈ [0, 1]) upon profiling a VM: Sen c , Sen m , and Sen d to respectively reflect sensitivity of a VM to its CPU, Mem, and Disk. For example, Sen c =1 implies that the profiled VM significantly changes its behavior, and consequently its throughput when it suffers to access CPU. Sen c =0 implies that throughput of the profiled VM is insensitive to its CPU share; eg, when the VM is running a Disk intensive application. Other values of Sec c/m/d reflect other levels of sensitivity: the larger the Sec c/m/d the more sensitivity to a resource type. vmBBProfiler is also application-oblivious and uses no internal information about the nature of the applications running inside the VM when profiling it; Figure 2 shows the architecture of both vmBBProfiler and vmBBThrPred and how they are related to each other. All components of vmBBProfiler and vmBBThrPred are totally separate and performing nonredundant procedures; both are run outside the VM and are currently implemented using PowerShell [START_REF]Microsoft powershell[END_REF] and PowerCLI [4] scripts for Windows-7 and above.

vmBBProfiler:

The key idea in vmBBProfiler is to identify how a VM behaves under resource contention. Its architecture relies on two components (Figure 2): vmProfiler and vmDataAnalyser. The vmProfiler, in turn, consists of two parts: vmLimiter and vmDataCollector to respectively command a Hypervisor, through VMware-vCenter [5] in our case, to impose resource limits to a VM, and collect/record its behavior under the imposed limits. vmProfiler aims to emulate contention through limitation. That is, instead of challenging a VM to compete with other co-located VMs to access/use resources (CPU, Mem, and/or Disk), the vmLimiter limits resource usage of the VM so that it reveals its behavior under hypothetical contentions. We showed in [START_REF] Taheri | vmbbprofiler: A black-box profiling approach to quantify sensitivity of virtual machines to shared cloud resources[END_REF] that although resource starvation under "contention" and "limitation" are different, they always lead to very similar performance degradation (less than 5% different on average). cpu/mem/diskLimit ∈ [0, 1] sets the percentage of CPU/Mem/Disk that the VM can use. For example, if a VM has two 2.4GHz vCPUs, cpuLimit=0.25 would limit CPU usage of this VM to 0.25 × 2 × 2.4 = 1.2GHz. After imposing a set of limits to resources, vmDataCollector is then launched to collect/record performance of the VM through polling several Hypervisor level metrics; it only polls VM metrics (eg, CPU utilization) that are already collected by the Hypervisor: it neither demands nor needs any specific metric from the VM itself.

Table 1 shows a sample profiling table upon completion of vmBBProfiler; this table will be refereed to as "ProfTable" for the rest of this article. In this table, cpuLimit ∈ {c 1 , c 2 , . . . , c nc }, memLimit ∈ {m 1 , m 2 , . . . , m nm }, and diskLimit ∈ {d 1 , d 2 , . . . , d nd } produce a total number of nc × nm × nd profiling scenarios. metricX is the average of the X-th Hypervisor metrics (eg, disk.read.average(KBps)) during the imposed limitation scenario. It is worth noting that each metric is a series of values during the profiling phase (eg. 15 values for 5 minutes of profiling in [START_REF] Taheri | vmbbprofiler: A black-box profiling approach to quantify sensitivity of virtual machines to shared cloud resources[END_REF]), however because they showed to have negligible standard deviation, their average values proved to be accurate enough to be used in vmBBThrPred.

Upon profiling behavior of a VM under several limitation profiles, vmData-Analyser is invoked to analyze the profiled data and calculate sensitivity of the VM to its CPU, Memory, and Disk allowances; they are respectively named Sen

1 c1 m1 d1 • • • 2 c1 m1 d2 • • • • • • • • • • • • • • • • • • nc × nm × nd cnc mnm dnd • • •
Sen m , and Sen d . For example, it would suggest that the application in the VM, which is assumed responsible for its resource demands, would always stay more sensitive to its CPU allocation than to its Memory bandwidth. As a result, it speculates that performance of this VM, for example, would be degraded more if its CPU-share -as opposed to its Memory share-is halved.

vmBBThrPred: After profiling a VM using vmBBProfiler, vmBBThrPred is launched to use its sensitivity values and predict its throughput under any working scenario, even those that have not been observed in Table 1. vmBBThrPred consists of two parts: vmModeler and vmPredictor. vmModeler uses Sen c/m/d values (calculated and provided by vmBBProfiler) to produce a polynomial model to relate resource utilization of a VM to its throughput; vmPredictor connects directly to VMware-vCenter [5], dynamically (online) polls CPU, Mem, and Disk utilization of a VM, and uses the produced formula to predict throughout (Thr) and performance degradation (PD=1-Thr) of the VM at its current working condition.

Procedures of vmBBThrPred

The first step before delving into the procedures of vmBBThrPred is to select several Hypervisor metrics that can directly or indirectly relate to the actual throughout of an application/VM. Here, because vmBBThrPred is designed to be application-oblivious, we define the term "throughput" as a normalized value (∈ [0, 1]) where Thr=1 always reflect the maximum performance of a VM. Similarly, "performance degradation" (PD) is defined as (1-Thr) to reflect the amount of degradation a VM encounters in its current working situation. For the apache server (2vCPUs, 2GB of RAM, and 20GB) in our experimental setup (Section 5) for example, we observed the maximum response rate of 10900 'requests per second', when the VM hosting the apache server was run in an isolated environment. After migrating the VM to a contention environment, its respond rate was reduced to 4045. In this case, the respond rate of 10900 and 4045 would map to Thr=1.00 (PD=0.00) and Thr=4045/10900=0.37 (PD=0.63), respectively.

Identify Relevant Hypervisor Metrics

We performed a series of engineered experiments to find Hypervisor metrics that have significant correlations with the actual throughput of different appli- To this end, we used four benchmarks (out of the total 12 for this article) with different resource utilization behavior from the Phoronix Test Suite [START_REF]Phoronix test suite[END_REF] to identify correlated metrics. They were 'apache' to represent CPU intensive (H/-/-), 'blogbench' to represent Memory intensive (-/H/L), 'aio-stress' to represent Disk intensive (-/-/H), and 'unpack-linux' to represent CPU+Mem+Disk intensive (L/L/L) applications/VMs. We tested each benchmark on three different PMs (Table 2) for 64 different contention scenarios (Table 1). Actual throughput values of these runs (provided by the Phoronix at the end of each run) are statistically correlated with 134 metrics provided by our VMware-vSphere [START_REF]Vmware-vsphere[END_REF] private cloud to identify the most significant/influential ones. Table 3 lists five metrics with the highest correlation to the actual throughput for each benchmark.

As it can be seen, for one-resource-intensive benchmarks (Table 3a-c), throughput of apache, blogbench, and aio-stress is highly correlated with CPU, Mem, and Disk, respectively. For the unpack-linux with multi-resource-intensive nature however, metrics for all three resource types are listed. To compile a list of metrics to cover all cases, we averaged correlation values for all four benchmarks and build Table 4. Based on this table, we chose the cpu.usage.average(%), mem.usage.average(%), and disk.usage.average(KBps) as the three most correlated metrics to actual throughput of general purpose/unknown applications/VMs. In Section 3, we will show that throughout, and consequently performance degradation of all sorts of applications with various utilization patterns can be accurately (≈ 90-95%) predicted using these selected metrics.

Blind Prediction

After selecting three of the most correlated Hypervisor metrics to actual throughput of applications/VMs, we performed another set of statistical analysis to discover the actual relation (formula) between the selected metrics and throughput values. To this end, we observed that there is a significant alignment between sensitivity values computed by vmBBProfiler and calculated correlation values. Figure 3 aligns "Correlation to Throughput" with "Sensitivity" values calculated by vmBBProfiler for all benchmarks in such alignments with the "ideal" line, which represent a perfect alignment, in these sub-figures motivates us to believe/hypothesize that the actual throughput of applications/VMs can be accurately predicted using their sensitivity values instead of their correlation values. To mathematically formulate this, we designed the following formula to predict "throughput" of a VM using only its current normalized CPU, Mem, and Disk utilization values.

Thr(C,M,D)= C×Sen c +M ×Sen m +D×Sen d Sen c +Sen m +Sen d

(1)

In this formula, C, M, and D are respectively the proportional of CPU, Mem, and Disk utilization of a VM with respect to their counterpart values in an isolated run. For example, assume a VM with sensitivity values of Sen c =1.00, Sen m =0.05, and Sen d =0.03 uses 80% of its CPU, occupies 22% of its Mem, performs 25KBps of Disk activity, and responds to 200 requests per second when it is run in a contention free environment (isolated run). Also assume its hosting VM is migrated to a PM where utilization of its resources are reduced to 45% of CPU, 10% of Mem, and 8KBps of Disk because of contention. According to Eqn. 1, its throughout, in this case, is predicted to be 55% of its maximum throughout (200) in the isolated run; ie:

Thr= 45% 80% ×1.00+ 10% 22% ×0.05+ 8KBps 25KBps ×0.03 1.00+0.05+0.03 × 200 = 0.55 × 200
The rationale behind this formula is based on our direct observations across months of profiling. To explain it, assume CPU-usage of a CPU intensive ap- plication (such as an apache server) is 90% and it responds to 10000 requests per seconds. Now assume that its CPU-usage is reduce to 30% because of contention. The general sense, also confirmed by direct measurements, dictates that the VM should respond to one-third of 10000; ie 30/90×10000=3333. For more complicated cases where a VM is sensitive to more than one resource, assume a Mem+Disk application (such as blogbench) is using 10% of CPU, 70% of Mem, and perform 17000KBps on Disk to conduct 100'000 blog activities in a contention free environment. Now assume this VM is migrated to another PM and its resource usages are reduced to 9% of CPU, 63% of Mem, and 8500KBps because of contention. In this case, although its Mem-and disk-usage are respectively reduce by 10% and 50%, its final throughput will not reduce by max(10%,50%)=50%. This is because a VM's throughput is actually reduced based on its nature and in proportion to how sensitive it is to each of its resources. For blogbench in this example with Sen c =0.00, Sen m =0.75, and Sen d =0.20, we observed (measured) the final throughput of 83'460 that is very close to 82'000 that Eqn 1 predicts as: Thr= In Section 5 we will show that using sensitivity values to weight average usage proportion of resources leads to accurate blind prediction of throughput for all benchmarks we used in this work.

vmModeler Procedures

Algorithm 1 shows procedural steps of modeling, and consequently deriving a formula to relate throughput of an application/VM to its CPU, Mem, and Disk utilization. Modeling can be performed in two modes: Blind or Assisted. In the Blind mode, it is assumed that vmBBThrPred has no knowledge of the application inside a VM, and it purely relies on the sensitivity values reported by vmBBProfiler (Sen c/m/d ) to predict throughput of the VM under different working scenarios. In the Assisted mode, it is assumes that there exists a "known" measurement/metric that could directly or indirectly reflect the actual performance of a VM. For example, the amount of network traffic for an apache server or the amount of IOPs (i/o operation per second) for an ftp server can both indirectly reflect performance of these servers. The Assisted mode is to address the current theme of using internal and/or external measurements to predict throughput, and consequently performance degradation of a VM in its current working condition. We included this mode only to show that not only vmBBThrPred can be easily adopted/employed by current systems, but also its bundling with vmBBProfiler yields more than 95% accuracy in predicting throughout of any application with any resource sensitivity. Similar to vmBBProfiler [START_REF] Taheri | vmbbprofiler: A black-box profiling approach to quantify sensitivity of virtual machines to shared cloud resources[END_REF], vmModeler also uses the normalized values of C, M, and D to propose a polynomial function with prototype

Thr(C,M,D) = x 1 C + x 2 M + x 3 D + x 4 CM + x 5 CD + x 6 MD + x 7 CMD + x 8 (2)
where C, M, and D are the current values of cpu.usage.average(%) divided by 100, mem.usage.average(%) divided by 100, and disk.usage.average(KBps) divided by 50000 (the maximum read/write speed for our testing environment), respectively.

To calculate x 1 . . . x 8 , we use ProfTable (Table 1) generated during calculation of Sen c/m/d by vmBBProfiler. In this table, for nc=nm=nd =4 (where c x =m x =d x =x × 0.25, ProfTable would have 64 rows. Using these 64 runs, we define:

A=        C 1 M 1 D 1 (C 1 M 1 ) (C 1 D 1 ) (M 1 D 1 ) (C 1 M 1 D 1 )
       (3)
X=    x 1 . . . x 8    Y1=      C 1 C 64 Sen c + M 1 M 64 Sen m + D 1 D 64
Sen d

Sen c +Sen m +Sen d . . . . . .

T64 T64    (4)
In Eqn 3, normalized values of C, M, and D for the k-th run in ProfTable are used to fill the k-th row of matrix A. In Eqn 4, each element/row of vector Y1 is the weighted average of relative CPU, Mem, and Disk utilization of the k-th run with respect to the 64-th run (the run with no limitation and maximum performance). Vector Y2, only for the assisted mode, records the relative performance value of an indirect-metric that can be used to directly or indirectly reflect the performance of a VM; it is assumed that T64 reflects the maximum throughput/performance. For example, we used disk.usage.average(KBps) (T64=46000KBps) as the indirect-metric for aio-stress in our experimental setup (more information in Section 5). Using linear regression, the optimal value of X can be calculated as:

A 64×8 × X 8×1 = Y 64×1 =⇒ X = (A T A) -1 A T Y (5)
Algorithm 1 Algorithm for vmModeler in both modes For Y←Y1, the X calculated using Eqn 5 yields ThrB (B for Blind) in Eqn 2; Y←Y2 yields ThrA (A for assisted) in Eqn 2.

In Algorithm 1, operations 2-3 initialize three matrices; operation 4 calculates and builds ThrB; operation 5 builds ThrA. Note that computing ThrB and ThrA are independent of each other; therefore if no "indirect-metric" could be identified to calculate ThrA, vmModeler can still build ThrB. In Section 5 we will show that ThrA is, as expected, more accurate (≈96%) than ThrB (≈90%) for all cases/benchmarks.

Experimental Results

To validate our proposed vmBBThrPred, we ran about 1200 hours (50 days) of actual running and profiling benchmarks on our private cloud in the School of Information Technologies at the University of Sydney. We used three different PMs (Table 2) and profiled 12 different benchmarks (Table 5), varying from pure CPU/Mem/Disk intensive to various combination of CPU+Mem+Disk ones.

Benchmark Selection: We used the Phoronix Test Suite [START_REF]Phoronix test suite[END_REF] (one of the most comprehensive testing and benchmarking platform) to evaluate performance and accuracy of vmBBThrPred. Table 5 lists the 12 benchmarks (out of 168 available ones in v5.2.1) we used for our experiments. We deliberately picked benchmarks with different intensities of resource usage profile of CPU, Mem, and Disk to cover realistic applications. In this table 'H', 'L', and '-' respectively mean High, Low, and Negligible resource utilization. From the 12 benchmarks in Table 5, eight run CPU intensive, four run Memory intensive, and five run Disk intensive processes.

Experimental Results: Table 5 shows experimental results of using our approach (vmBBThrPred) to derive polynomial formulas for the selected 12 benchmarks. There are three rows for each benchmark: one row for each PM in Table 2. As it was explained in Section 4, vmBBThrPred can work in two modes: Blind and Assisted. ThrB is built purely based on Sen c/m/d and the ProfTable (Table 1); ThrA additionally uses the mentioned indirect-metric in Table 5.

Discussion and Analysis

We highlight the most stimulating conclusions from Table 5 in this section.

Accuracy of vmBBThrPred

Table 5 shows different prediction accuracy for different benchmarks: ranging from 76%-99% for the Blind (ThrB) and 94%-100% for the Assisted (ThrA) mode. For CPU intensive applications (marked as (*/-/-)), the accuracy of vmBBThrPred were significantly high (>94%). Accuracy of ThrA/B for disk intensive applications ((-/L/L) and (-/*/H)) were also noticeably high with the minimum accuracy of 82% and 94% for ThrB and ThrA, respectively. Memory intensive applications (-/H/L) proved to be much more cumbersome than the other two. In this case, vmBBThrPred accuracy dropped as low as 76% and 90% for the Blind and Assisted modes, respectively. This is well aligned with other experiments in the literature that identify Memory Caches (L1/L2/L3) as one of the most influential components in virtualized environments. It is also well aligned with Table 4 in which Memory bandwidth showed less correlation with throughput as compared with CPU and Disk.

Transferability of Results

Table 5 shows a variety of formulas for different benchmarks on different PMs. Nevertheless, in most cases the formula was almost identical across PMs. For CPU intensive applications, (*/-/-), ThrA/B are almost identical across PMs. Disk intensive applications, (-/L/L) and (-/*/H), have also led to similar formulas. Throughput of memory intensive applications however, (-/H/*) and (-/L/*), could not be modeled using similar formulas; they also varied across PMs. This could be related to the internal nature of CPU structure and the size of caches in these PMs. As it can be observed in Table 2, these PMs have different cache sizes. The AMD machine for example has the largest cache size; we believe this is why it has the most straight forward formula for all cases. For example, ThrA/B formulas for blogbench with the highest sensitivity to memory is calculated as a function of 'M', while on the other two PMs they are related to 'C' and 'D' too. This also confirms that the cache size/structure is very important for virtualized environments.

Indirect Metrics

Table 5 also shows the indirect-metric we used for each benchmark to build its ThrA formulas to achieve slightly better (5%-10% more) accuracy than ThrB. This proves that having "known" metrics to directly or indirectly measure performance of applications could in fact lead to more accurate results. Nevertheless, we argue that selecting the right "indirect metric" could not be very easy sometimes because not but we also need to make sure that the chosen metric has a linear relation with the actual throughput of the application/VM. In fact, selecting a wrong metric could lead to meaningless formulas, such as selecting a disk related metric (eg, disk.usage.average(KBps)) for a CPU-intensive applications (eg, apache).

Conclusion

In this work, we presented vmBBThrPred to predict throughput, and consequently the performance degradation of general purpose applications/VMs based on their CPU, Mem, and Disk utilization as seen by the Hypervisor, and the sensitivity values calculated for them by vmBBProfiler. vmBBThrPred can work in two modes: Blind and Assisted. In the Blind mode, it uses only the Hypervisor level metrics to derive a polynomial formula in which normalized CPU, Mem, and Disk utilization values of working VMs can be dynamically (online) plugged in to predict the immediate throughput of each VM. For the Assisted mode, an indirect-metric could be nominated by the user so that vmBBThrPred can derive more accurate formulas. vmBBThrPred was implemented our VMware-vSphere based private cloud and proved its efficiency across 1200 hours of empirical studies. Using 12 well known benchmarks to cover all sorts of possible applications, it managed to successfully build accurate formulas (90% for Blind and 95% for Assisted on average) for a various range of applications with different resource intensity usage profiles. vmBBThrPred is the first Black-Box throughput predictor, to the best of our knowledge, that uses only basic Hypervisor level metrics for its very systematic calculations.

Fig. 2 :

 2 Fig. 2: Architecture of vmBBProfiler and vmBBThrPred

Fig. 3 :

 3 Fig. 3: Point-by-point alignment of "Correlation to Throughout" with "Sensitivity" values

9 10

 9 ×0.00+ 63 70 ×0.75+ 8500 17000 ×0.20 0.00+0.75+0.20 × 100000 = 0.82 × 100000

Table 1 :

 1 vmBBProfiler output table (ProfTable) after profiling a VM

	Scenario #	cpuLimit memLimit diskLimit (metric1, metric2, . . . , metricK)

c ,

Table 2 :

 2 Characteristics of Used Physical Machines Note that the actual throughput of applications/VMs is not accessible/measurable for general purpose VMs -because of the need to install/inject monitoring codes. However, we could have access to these values because the Phoronix Test Suits[START_REF]Phoronix test suite[END_REF] that we used in this article actually provides such detailed values at the end of its runs. It is worth noting that we used such detailed values only to identify (reverse-engineer) relative Hypervisor metrics; general use cases of vmBBThrPred does not require actual throughput measurements.

	PM Name CPU Family	# Cores (Speed) Memory Cache (L1/L2/L3)
	AMD	AMD Opteron 6282 SE 64 (2.599GHz) 256GB (768KB/16MB/16MB)
	DELL	Intel i7-3770	8 (3.40Ghz)	16GB (256KB/1MB/8MB)
	SGI	Intel Xeon(R) E5420	8 (2.493GHz)	32GB (256KB/12MB/-)
	cations.

Table 3 :

 3 Table 5 on all PMs in Table 2. Comparing Five most correlated Hypervisor metrics for the selected benchmarks

	(a) apache		(b) blogbench
	Metric Name	Correlation	Metric Name	Correlation
	cpu.run.summation(millisecond)	0.99	mem.active.average(KB)	0.69
	cpu.usage.average(%)	0.99	mem.usage.average(%)	0.69
	cpu.ready.summation(millisecond)	0.99	mem.granted.average(KB)	0.68
	cpu.demand.average(MHz)	0.99	mem.activewrite.average(KB)	0.67
	cpu.overlap.summation(millisecond)	0.98	mem.entitlement.average(KB)	0.65
	(c) aio-stress		(d) unpack-linux
	Metric Name	Correlation	Metric Name	Correlation
	virtualdisk.write.average(KBps)	0.99	disk.usage.average(KBps)	0.94
	datastore.write.average(KBps)	0.98	virtualdisk.mediumseeks.latest(number) 0.90
	disk.usage.average(KBps)	0.98	cpu.used.summation(millisecond)	0.89
	virtualdisk.mediumseeks.latest(number) 0.98	cpu.usage.average(%)	0.88
	disk.numberwrite.summation(number)	0.97	mem.usage.average(%)	0.79

Table 4 :

 4 Six most correlated Hypervisor metrics for all benchmarks

	Metric Name	Correlation
	disk.numberwrite.summation(number)	0.87
	disk.usage.average(KBps)	0.85
	cpu.usage.average(%)	0.77
	cpu.used.summation(millisecond)	0.77
	mem.usage.average(%)	0.61
	mem.latency.average(%)	0.55

  C 64 M 64 D 64 (C 64 M 64 ) (C 64 D 64 ) (M 64 D 64 (C 64 M 64 D 64 ) 1

								1
	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .

Table 5 :

 5 Results for using vmBBThrPred on the selected benchmarks

	Benchmark PM Sen c / Sen m / Sen d	formula	ThrB(C,M,D)	acc. formula	ThrA(C,M,D)	acc. indirect-metric
	apache (H/-/-)	AMD 0.95 / 0.00 / 0.00 (1.02)C DELL 0.97 / 0.00 / 0.00 (1.02)C SGI 0.97 / 0.03 / 0.00 (0.99)C		95% (1.03)C-0.05 97% (0.94)C+0.06 96% (1.00)C+0.04		98% cpu.latency. 98% average(%) 98%
	john-the-ripper (H/-/-)	AMD 0.93 / 0.00 / 0.00 (1.18)C DELL 0.96 / 0.00 / 0.00 (1.09)C+0.01 SGI 0.96 / 0.00 / 0.00 (1.17)C	95% (1.14)C+0.04 95% (1.06)C+0.08 91% (1.11)C+0.13		95% cpu.latency. 97% average(%) 95%
	n-queens (H/-/-)	AMD 0.95 / 0.00 / 0.00 (1.02)C DELL 0.97 / 0.00 / 0.00 (1.01)C SGI 0.97 / 0.00 / 0.00 (1.02)C		97% (1.07)C-0.05 99% (1.02)C 99% (1.03)C		99% cpu.idle.sum 100% mation(msec) 100%
	build-apache (H/-/-)	AMD 0.94 / 0.00 / 0.00 (1.13)C+0.01 DELL 0.96 / 0.00 / 0.00 (1.05)C SGI 0.96 / 0.04 / 0.00 (1.10)C+0.01	97% (1.19)C-0.03 99% (1.07)C-0.01 98% (1.16)C-0.01		97% cpu.latency. 99% average(%) 99%
	build-php (H/-/-)	AMD 0.95 / 0.02 / 0.00 (1.01)C DELL 0.96 / 0.00 / 0.00 (1.04)C SGI 0.97 / 0.07 / 0.00 (0.96)C+0.01	98% (1.02)C-0.01 98% (1.03)C+0.02 95% (1.00)C+0.03		98% cpu.latency. 98% average(%) 98%
	dcraw (L/-/-)	AMD 0.54 / 0.00 / 0.00 (2.10)C DELL 0.55 / 0.00 / 0.00 (2.16)C+0.02 SGI 0.48 / 0.04 / 0.00 (2.01)C	98% (2.38)C-0.11 98% (2.26)C-0.02 94% (2.24)C-0.03		99% cpu.idle.sum 98% mation(msec) 98%
	x264 (L/-/-)	AMD 0.33 / 0.01 / 0.00 (1.28)C DELL 0.39 / 0.00 / 0.00 (1.27)C SGI 0.41 / 0.02 / 0.00 (1.28)C		96% (1.32)C-0.06 95% (1.34)C-0.08 98% (1.30)C-0.02		97% cpu.latency. 98% average(%) 98%
	unpack-linux (L/L/L)	AMD 0.19 / 0.10 / 0.40 (1.59)C+(1.61)D-(1.14)CD-0.07 95% (1.76)C+(4.91)D-(6.04)CD-0.53 DELL 0.21 / 0.09 / 0.25 (1.36)D+0.01 95% (1.60)D-0.07 SGI 0.18 / 0.09 / 0.35 (0.91)C+(1.09)D-(0.18)CD-0.01 94% -(0.58)C-(0.26)D+(5.04)CD+0.33 95% 98% 96%	disk.numwrite. summation
	blogbench (-/H/L)	AMD 0.09 / 0.74 / 0.16 (0.93)M DELL 0.00 / 0.75 / 0.20 (0.20)M+(0.64)D+(0.16)MD+0.37 76% -(0.89)M+(0.40)D+(0.34)MD+0.98 90% 77% (0.60)M+0.41 90% mem.latency. average(%) SGI 0.11 / 0.81 / 0.18 (0.15)C+(0.93)M-(0.03)CM 84% (0.46)C+(0.20)M+(0.06)CM+0.28 91%
	bork (-/L/L)	AMD 0.00 / 0.47 / 0.18 (0.75)M+(0.26)D+(0.05)MD+0.02 84% -(0.03)M+(0.94)D+(0.11)MD DELL 0.00 / 0.45 / 0.09 (0.80)M+(0.39)D-(0.10)MD 82% (0.03)M+(1.14)D-(0.03)MD+0.05 98% 99% mem.activewri te.average(KB) SGI 0.00 / 0.53 / 0.20 (0.82)M+(0.43)D-(0.15)MD 83% (0.04)M+(1.24)D-(0.08)MD-0.01 97%
	compress-gzip (-/L/H)	AMD 0.00 / 0.00 / 0.55 (1.37)D+0.07 DELL 0.00 / 0.00 / 0.45 (0.48)M+(0.52)D+(0.22)MD+0.11 87% (0.16)M+(1.01)D+(0.42)MD 94% (0.85)D+0.40 SGI 0.00 / 0.00 / 0.47 (0.51)M+(0.48)D+(0.25)MD+0.09 83% (0.10)M+(1.08)D+(0.40)MD	97% 94% 95%	disk.numwrite. summation
	aio-stress (-/-/H)	AMD 0.00 / 0.31 / 0.84 (0.60)M+(0.68)D-(0.02)MD DELL 0.00 / 0.32 / 0.91 (0.40)M+(0.95)D-(0.11)MD-0.01 96% (0.13)M+(1.22)D-(0.06)MD-0.05 90% (1.10)D+(0.33)MD SGI 0.00 / 0.30 / 0.80 (1.00)M+(0.75)D-(0.19)MD-0.02 86% -(0.05)M+(2.01)D+(0.75)MD+0.02 99% 99% disk.maxtotal 98% latency.latest