-The value of commercial Service-Based Applications (SBAs) will depend not only on their functionality, but also on the value of their non-functional properties, known as QoS attributes, that are not tied to a specific functionality, but rather to its delivery features. QoS values may vary according to the provision strategies of providers as well as users' requirements expressed as global constraints on the SBA QoS. Automatic negotiation is a viable approach to drive QoS-aware selection of services for SBAs, but its adoption may result computationally expensive due to the communication overhead among the involved negotiators, so limiting its application to real service-based scenarios. In this paper, an empirical evaluation of the impact of negotiation communication costs occurred when composing services to deliver a QoS-aware SBA is carried out, in order to estimate the advantages and disadvantages of negotiation in a market of services, and to identify negotiation parameters settings for which communication costs can be compensated by an increased probability for the negotiation to succeed.
The increased popularity of the
Service-OrientedComputing (SOC) paradigm [
In a previous paper [
The negotiation protocol is designed as a one-to-many-tomany iterative protocol since the service consumer negotiates at the same time with the different providers of each functionality required in the SBA, as well as with the providers of the different functionalities required in the SBA in a coordinated way. In fact, when dealing with end-to-end QoS requirements typical of SBAs, the QoS values of each functionality are not independent from one another, but it is necessary to find a set of interrelated QoS values. So, the negotiation process may require several iterations to successfully end, becoming computationally expensive in terms of the involved communication costs.
In this paper we propose an experimental evaluation of the proposed negotiation mechanism in terms of its computational costs due to the communication overhead coming from the possibility to negotiate with all the available providers during each iteration of the negotiation. The aim of the evaluation is to compare the cost of negotiation with respect to the potential benefit of having a success at the end of the process, and to evaluate the pros and cons in negotiating with all available providers until the negotiation ends.
The paper is organized as follows. In Section II some works related to service composition are reported; Section III describes the main features of the negotiation mechanism adopted in the present work; in Section IV the rationale of the experiments set to evaluate the cost of the negotiation protocol is reported, together with the decision making mechanisms adopted by the service compositor and the service providers during the negotiation. Then the experiments carried out, and the evaluation of the obtained results are described and discussed in Subsections IV-B, and IV-C. Finally, Section V reports some conclusions and planned future works.
Service composition allows to aggregate autonomous and independently developed services in order to build added value applications (SBAs). With the pervasive growth of available services, it is widely recognized that multiple services providing the same functionality may be available, but they may differ in their non-functional features, usually known as Quality of Service, such as cost, execution time, and so on. In this context, users will require SBAs specifying their own preferences/constraints on the global QoS values of the application, so it becomes crucial to select the appropriate component services, i.e., services whose QoS attribute values, once aggregated, meet users’ preferences/constraints.
Several research efforts addressed this challenge proposing
approaches that mainly apply static methods to find the set
of services whose QoS values meet the global constraints set
by the users. Some works propose algorithms to select service
implementations relying on the optimization of a weighted sum
of global QoS parameters as in [
In dynamic markets where service provision is regulated by demand and supply mechanisms, it is likely that different users may have different QoS requirements for the same (from a functional point of view) application, as well as QoS attribute values for the same service may change in time according to dynamic circumstances affecting service provision strategies. In this context, it becomes crucial to provide service-oriented infrastructures with mechanisms enabling the selection of services with suitable QoS attribute values so that QoS requirements can be satisfied when forming new added-value applications through service composition. Such mechanisms should allow to manage the dynamic nature of both QoS values, and QoS requirements. Negotiation has gained more and more attention in SOC applications as a viable approach to drive the selection of suitable component services. It allows to address the dynamic nature of both the provided and required QoS since the offered QoS value of single services may change as soon as new offers and counteroffers are exchanged.
Practical negotiation mechanisms for B2B applications
must be computationally efficient [
Most approaches, that use negotiation mechanisms to
select services according to their QoS values, usually apply
negotiation for each required service independently from the
others relying on bilateral one-to-one negotiation mechanisms
[
III.
In this work we adopt the iterated negotiation mechanism
proposed in [
In the proposed approach a Service Compositor (SC), acting on behalf of a service consumer, issues an SBA request represented by a Directed Acyclic Graph, referred to as an Abstract Workflow (AW), specifying the functionality of each service component (AW nodes referred to as Abstract Services ASs), and their functional dependence constraints (AW arcs), together with the value(s) of the end-to-end QoS requirements the user wants the application to provide. It is assumed that for each AS a set of Concrete Services (CSs) are available on the market, each one provided by a specific Service Provider (SP) with QoS attributes whose values are set by the corresponding SP dynamically. The protocol allows only the SPs to formulate new offers, and only the SC to evaluate them. The rationale of this choice is twofold: on one hand it makes it possible to simulate what happens in a real market of services where an SC does not have enough information on the SPs strategies to formulate counteroffers; on the other hand it takes into account that the offers for a single functionality cannot be evaluated independently from the ones received for the other functionalities. So, it is necessary to design a negotiation mechanism that allows both to negotiate with the SPs providing services for each required functionality in the AW, but at the same time to evaluate the aggregated QoS value of the received offers for all the required functionality in the AW during the negotiation. Indeed, the SC is not able to make single counter-proposals with respect to each received offer, because the change of a value of a particular QoS can impact the others QoS attributes of the same service, as well as the constraints to be fulfilled by the QoSs of the other services. In other words, negotiating over the attributes of the single AS cannot be done independently from each other.
Since SC does not provide counteroffers the negotiation
could be model as simply an auction mechanism as in [
This is why an hybrid negotiation approach was used, where an auction-like protocol models the bidding of single component services, but without relying on a specific auction mechanism to allow SPs to adopt their own private strategies when bidding, and also to change them if required by the market trends.
In [
We evaluate experimentally the efficiency of the negotiation mechanism with respect to two performance measures: negotiation outcome (i.e., utility of the solution and/or the negotiation success rate), and communication complexity (i.e., the number of exchanged messages), by varying the parameters affecting the OMM protocol that are the number of allowed negotiation rounds, and the number of SPs involved in the interaction. A. Compositor and Providers Utility Functions and Strategies
Here, we briefly describe the decision making algorithm
for the SC evaluation of proposals, and the strategies adopted
by SPs to generate an offer, as proposed in [
Following the approach formulated in [
USC (oi;j ) = maxk(pricei;k)
pricei;j Pim=1(maxk(pricei;k) mink(pricei;k)) (1) where i identifies one of the m ASs and the j identifies one of the n SPs. Once the most promising offer for each AS is selected according to Eq. 1, we modeled the global requirements satisfaction problem in terms of SC’s global utility. This utility is related to the distance between the QoS preferences, expressed at the time the request is issued, and the aggregated QoS values obtained by combining the the best selected offers. It is normalized so that it is 1 in case the requirements are met, and in [0; 1] otherwise. The SC’s utility is expressed as follows:
USC = 81 > < >:1 if
Pm
i=1 pricei;s < reqP rice Pim=1 pricei;s reqP rice reqP rice otherwise (2) where, pricei;s is the price offered for the ith AS by the selected sth SP, Pm
i=1 pricei;s is the aggregated value for the price, and reqP rice is the user requested price.
On the contrary, SPs apply their own strategies to formulate
their offers. These strategies are modeled as a set of functions
that are both time and resource dependent [
The configurations considered for the experiments set five different deadlines at 1, 10, 20, 30 and 40 rounds, and for each deadline the number of SPs at 2, 4, 8, 16. Let us highlight that for a deadline of 1 round, the protocol is based on m concurrent ContractNet Protocols (CNET). We also considered a configuration where the negotiation occurs only with one SP for each AS, that is the best SP, in terms of USC (ox), according to the offers received at round 1. In this case the deadline varies from 10 to 40 rounds.
In the configurations there are 5 ASs, AS1, AS2, AS3, AS4, AS5, with a computational costs decreasing from AS1 to AS5. The user requested price is 1500$ (reqP rice). For each AS a default price bestP ricei is set, and the corresponding SPs will send as initial offer a price randomly extracted in the neighborhood of bestP ricei [bestP ricei 5% bestP ricei; bestP ricei]. This is because, even though the market price of services corresponding to the same AS is the same, to model a real market of services the variability of the first offered price is introduced. In the experiments, the market prices for the ASs are: bestP rice1 = 540$; bestP rice2 = 468$; bestP rice3 = 351$; bestP rice4 = 270$; bestP rice5 = 216$. The value randomly varies for each SP in the range [0.0, 0.5], so including the possibility that SPs with the maximum computational load are not willing to concede.
In all the experiments 100 tests were performed for each of the described configurations.
In Figure 2 the percentage of negotiation successes varying the number of rounds and the number of SPs (from 2 to 16) for each AS is plotted. In Table I the same percentage is plotted, varying the number of rounds, but in the case of negotiation with only the “best” SP for each AS. As expected, for a deadline of 1 round (simple CNET protocol) we have 100% of failures since the specific settings of the tests require a negotiation phase to find a solution. In Table I the results show that selecting the best SP at round 1 does not reduce the negotiation cost. In fact, only the 12% of success rate is obtained with 30 or 40 rounds of negotiation allowed, so the computational cost of the negotiation is not compensated by an high rate of success. A better trend is obtained by adding another provider for each AS (as shown in Figure 2). In fact, in this case, with 30 or 40 rounds of negotiation allowed, 50% of successes are obtained. Scaling up the number of SPs from 4 to 16 the success rate increases from 90% to 100% just after 10 rounds. These results support the choice to negotiate with all the available SPs, as proposed by the OMM protocol, since the cost of negotiation is partially compensated by an increase in the negotiation success rate.
In order to evaluate the computational cost of the OMM protocol, also the number of exchanged messages are considered. At each negotiation round the SC sends m n cfps, receives at the most m n possible offers, and it sends back at most m n accept and/or reject messages. This means that for each round the cost of communication in terms of exchanged messages is 3 n m. The numbers of messages are reported in Table II for all the experimental configurations.
A comparative evaluation of Table II and Figure 2 is shown in Figure 3 that provides information on the tradeoff between communication costs and success rate. In particular from configurations with 2400 exchanged messages to configurations with 9600 no variation in success rate is obtained (that is stable at 100%). This means that from 2400 onward there is only a communication overhead without any gain in the success rate. A first conclusion of this evaluation is that negotiating with 16 SPs for each AS with respect to negotiating with 8 SPs will not change the success rate, but it will only require more exchanged messages. So, in this case, selecting a subset of available providers reduces the cost of communication without affecting the success rate. Moreover, as already showed in Figure 2.b, such selection cannot be made only evaluating current offers because promising providers may change their concession strategy during the interaction. However, a bigger number of SPs, as shown in the following figures will provide a quicker achievement of the agreement, so reducing the negotiation length. Such evaluation of the number of exchanged messages with respect to the success rate shows that, in the case of a relevant number of available providers, long negotiation mechanisms are not necessary. So, in the following experimets only negotiation deadlines smaller than 40 rounds will be considered.
In Figure 4 the variation of the SC’s global utility is reported at different negotiation rounds varying the number of available SPs and the deadline of the negotiation. In particular, on the left cases leading to success are considered varying the number of SPs for each AS from 2 to 16, and the deadline from 10 to 30 rounds. On the right cases leading to a failure are considered with the same deadlines as before, but varying the number of SPs for each AS from 2 to 4 since by increasing the number of SPs only successes are obtained from the round 10th onward. Let us note that the success is obtained as soon as the SC’s utility becomes equal to 1, and it is reached in a less number of rounds by increasing the number of SPs for each AS. In case of failure, the SC’s utility varies very little by increasing the number of the negotiation rounds, so making proceeding with negotiation expensive without any benefit.
In Table III the SC’s utility variation in case of failure is reported in order to allow the SC to dynamically stop the negotiation according to its trend, i.e., according to whether and in which measure its utility is varying. The variation is calculated as a difference between the value of the SC’s utility respectively at rounds 10 and 20 (for the first column), at rounds 20 and 30 (for the second column), at rounds 30 and 40 (for the third column). The variation is evaluated varying the number of SPs (2 and 4). The average SC’s utility variation, and the corresponding standard deviation are also reported. As shown in Table III, in the configurations with the number of SPs equal to 2 and 4, by increasing the number of rounds the SC’s utility variation is less than 1% after 20 rounds, so indicating that keeping on negotiating is not likely to lead to a success.
Software agent negotiation is considered a promising approach for modeling the interactions between a service consumer and service providers when composing QoS-aware Service Based Applications. It is well recognized that the provision of such applications will be regulated by an agreement between the application consumer and the providers of the component services stating agreed terms and conditions related to both functional and non-functional application features. In particular, the negotiation mechanism is suitable to model the interactions occurring among consumers and providers when services are provided according to market-based mechanisms and when dynamic features, like QoS ones, have to be considered.
Nevertheless, automated negotiation did not succeed in real service-oriented market scenarios since it is computationally expensive in terms of the involved decision making mechanisms, and the communication overhead deriving from the complexity of the communication patterns.
In this work, an evaluation of the cost of the negotiation
mechanism proposed in [
The experiments were carried out for different configurations obtained by varying the two parameters affecting the cost of communication that are the number of involved negotiators, i.e., the number of SPs, and the number of negotiation rounds determining the length of the negotiation. The results showed that the increase in communication costs due to the possibility of negotiating with all the SPs instead of just one for each service type, is partially compensated by the fact that by increasing the number of SPs the success rate of the negotiation increases. In fact, in the case the best SP is selected to continue the negotiation, a 100% failure is obtained also by increasing the length of the negotiation. This is because in a market of services, that is dynamic by nature, it is not possible to assume that a promising provider will keep on sending promising offers, because a less promising provider may change its strategy in the meantime according to market trends and/or market strategies that are tied also to the specific service or quality attribute. So, the choice of negotiating with all the SPs is supported by the obtained results. Furthermore, in most configurations, the overhead due to the communication cost is partially compensated by a decrease in the negotiation length, i.e its overall computational cost.
In some cases the negotiation progress in terms of the distance between the requested QoS and the QoS obtained at each negotiation round shows that it is not worth to proceed with the negotiation after a certain number of rounds since no gain is obtained in the success rate. This means that in these cases the negotiation can be stopped without any loss in terms of consumer’s utility, so limiting the cost of negotiation in terms of its length. Of course, these results are related to the considered configurations, and also to the specific strategies adopted for the SPs.
We plan to extend the proposed negotiation mechanism by including the possibility for the SPs to change their strategies on fly, and to carry out more experiments by considering different set of strategies to evaluate the negotiation cost in different experimental settings.
The research leading to these results has received funding from the EU FP7-ICT-2012-8 under the MIDAS Project (Model and Inference Driven - Automated testing of Services architectures), Grant Agreement no. 318786, and the Italian Ministry of University and Research and EU under the PON OR.C.HE.S.T.R.A. project (ORganization of Cultural HEritage for Smart Tourism and Real-time Accessibility).