=Paper=
{{Paper
|id=Vol-1099/paper2
|storemode=property
|title=Evaluating Negotiation Cost for QoS-aware Service Composition
|pdfUrl=https://ceur-ws.org/Vol-1099/paper2.pdf
|volume=Vol-1099
|dblpUrl=https://dblp.org/rec/conf/aiia/NapoliNR13
}}
==Evaluating Negotiation Cost for QoS-aware Service Composition==
https://ceur-ws.org/Vol-1099/paper2.pdf
Evaluating Negotiation Cost for
QoS-aware Service Composition
Claudia Di Napoli Dario Di Nocera* Silvia Rossi
Istituto di Cibernetica “E. Caianiello” Dipartimento di Matematica e Applicazioni, Dipartimento di Ingegneria Elettrica
C.N.R., Via Campi Flegrei 34, 80078 Università degli Studi di Napoli e Tecnologie dell’Informazione,
Pozzuoli, Napoli, Italy “Federico II”, via Cintia MSA, Università degli Studi di Napoli
c.dinapoli@cib.na.cnr.it 80126 Napoli, Italy “Federico II”, via Claudio 21,
dario.dinocera@unina.it 80125 Napoli, Italy
silvia.rossi@unina.it
Abstract—The value of commercial Service-Based Applica- consumer to select the suitable services to compose QoS-
tions (SBAs) will depend not only on their functionality, but also aware SBAs. The approach allows for the selection of ser-
on the value of their non-functional properties, known as QoS vices according to the values of their quality attributes that,
attributes, that are not tied to a specific functionality, but rather once aggregated, have to meet end-to-end user QoS con-
to its delivery features. QoS values may vary according to the straints/preferences. The negotiation-based mechanism allows
provision strategies of providers as well as users’ requirements
expressed as global constraints on the SBA QoS. Automatic
to take into account the variability of service QoS attribute
negotiation is a viable approach to drive QoS-aware selection values typical of the future market of services since service
of services for SBAs, but its adoption may result computationally providers may change these values during the negotiation
expensive due to the communication overhead among the involved according to their own provision strategies, and market trends.
negotiators, so limiting its application to real service-based
scenarios. In this paper, an empirical evaluation of the impact
The negotiation protocol is designed as a one-to-many-to-
of negotiation communication costs occurred when composing
services to deliver a QoS-aware SBA is carried out, in order many iterative protocol since the service consumer negotiates
to estimate the advantages and disadvantages of negotiation in at the same time with the different providers of each function-
a market of services, and to identify negotiation parameters ality required in the SBA, as well as with the providers of the
settings for which communication costs can be compensated by different functionalities required in the SBA in a coordinated
an increased probability for the negotiation to succeed. way. In fact, when dealing with end-to-end QoS requirements
typical of SBAs, the QoS values of each functionality are
I. I NTRODUCTION not independent from one another, but it is necessary to
find a set of interrelated QoS values. So, the negotiation
The increased popularity of the Service-Oriented- process may require several iterations to successfully end,
Computing (SOC) paradigm [1] is enhancing the development becoming computationally expensive in terms of the involved
of Service Based Applications (SBAs) that are distributed communication costs.
applications obtained by combining existing services in a
loosely coupled manner that collectively fulfill a requested
task. Services are independent and autonomous entities In this paper we propose an experimental evaluation of the
provided by different service providers to be consumed by proposed negotiation mechanism in terms of its computational
users requesting a given application. Users do not need to be costs due to the communication overhead coming from the
aware of the actual composition as long as the functional and possibility to negotiate with all the available providers during
non-functional requirements are satisfied [2]. The consumption each iteration of the negotiation. The aim of the evaluation is
of these services is commonly governed by an agreement to compare the cost of negotiation with respect to the potential
among providers and consumers, known as Service Level benefit of having a success at the end of the process, and to
Agreement (SLA), which regulates terms and conditions of evaluate the pros and cons in negotiating with all available
service provision [3]. Agreements on service provisioning providers until the negotiation ends.
may include not only the provider’s commitment to execute
a given task (coming from functional requirements), but they The paper is organized as follows. In Section II some
also include terms about performance levels (or quality levels) works related to service composition are reported; Section
of services [4] (coming from non-functional requirements). III describes the main features of the negotiation mechanism
Service non-functional requirements refer to service attributes adopted in the present work; in Section IV the rationale of the
known as Quality of Service (QoS) attributes that play an experiments set to evaluate the cost of the negotiation protocol
important role in service selection. is reported, together with the decision making mechanisms
adopted by the service compositor and the service providers
In a previous paper [5] we proposed a market-based ne-
during the negotiation. Then the experiments carried out,
gotiation mechanism among service providers and a service
and the evaluation of the obtained results are described and
* Ph.D. scholarship funded by Media Motive S.r.l, POR Campania FSE discussed in Subsections IV-B, and IV-C. Finally, Section V
2007-2013. reports some conclusions and planned future works.
II. R ELATED W ORKS AND BACKGROUND negotiation for each required service independently from the
others relying on bilateral one-to-one negotiation mechanisms
Service composition allows to aggregate autonomous and [4], [12]. Attempts to propose a coordinated negotiation with
independently developed services in order to build added all the providers of the different required services in a com-
value applications (SBAs). With the pervasive growth of avail- position have been proposed as in [2], but they introduce a
able services, it is widely recognized that multiple services Negotiation Coordinator that instructs the negotiation of the
providing the same functionality may be available, but they single component services by decomposing end-to-end QoS
may differ in their non-functional features, usually known into local QoS requirements, so making the negotiation process
as Quality of Service, such as cost, execution time, and so computationally heavier from the point of view both of the
on. In this context, users will require SBAs specifying their involved negotiators, and of the necessary decision making
own preferences/constraints on the global QoS values of the mechanisms.
application, so it becomes crucial to select the appropriate
component services, i.e., services whose QoS attribute values,
once aggregated, meet users’ preferences/constraints. III. O NE - TO -M ANY- TO -M ANY N EGOTIATION P ROTOCOL
Several research efforts addressed this challenge proposing In this work we adopt the iterated negotiation mechanism
approaches that mainly apply static methods to find the set proposed in [5], starting from the assumption that SLAs for
of services whose QoS values meet the global constraints set QoS-aware SBAs have to be set by coordinating the single
by the users. Some works propose algorithms to select service agreements of each component service.
implementations relying on the optimization of a weighted sum In the proposed approach a Service Compositor (SC),
of global QoS parameters as in [6] by using integer linear acting on behalf of a service consumer, issues an SBA request
programming methods. In [7] local constraints are included represented by a Directed Acyclic Graph, referred to as an
in the linear programming model used to satisfy global QoS Abstract Workflow (AW), specifying the functionality of each
constraints. In [8] Mixed Integer Programming is used to service component (AW nodes referred to as Abstract Services
find the optimal decomposition of global QoS constraints into ASs), and their functional dependence constraints (AW arcs),
local constraints so that the best services satisfying the local together with the value(s) of the end-to-end QoS requirements
constraints can be found. Typically, these works rely on static the user wants the application to provide. It is assumed that for
approaches assuming that QoS values of each service are pre- each AS a set of Concrete Services (CSs) are available on the
defined by providers and do not change during the selection market, each one provided by a specific Service Provider (SP)
process. with QoS attributes whose values are set by the corresponding
In dynamic markets where service provision is regulated SP dynamically. The protocol allows only the SPs to formulate
by demand and supply mechanisms, it is likely that different new offers, and only the SC to evaluate them. The rationale
users may have different QoS requirements for the same (from of this choice is twofold: on one hand it makes it possible to
a functional point of view) application, as well as QoS attribute simulate what happens in a real market of services where an
values for the same service may change in time according to SC does not have enough information on the SPs strategies
dynamic circumstances affecting service provision strategies. to formulate counteroffers; on the other hand it takes into
In this context, it becomes crucial to provide service-oriented account that the offers for a single functionality cannot be
infrastructures with mechanisms enabling the selection of evaluated independently from the ones received for the other
services with suitable QoS attribute values so that QoS re- functionalities. So, it is necessary to design a negotiation
quirements can be satisfied when forming new added-value mechanism that allows both to negotiate with the SPs providing
applications through service composition. Such mechanisms services for each required functionality in the AW, but at
should allow to manage the dynamic nature of both QoS the same time to evaluate the aggregated QoS value of the
values, and QoS requirements. Negotiation has gained more received offers for all the required functionality in the AW
and more attention in SOC applications as a viable approach to during the negotiation. Indeed, the SC is not able to make
drive the selection of suitable component services. It allows to single counter-proposals with respect to each received offer,
address the dynamic nature of both the provided and required because the change of a value of a particular QoS can impact
QoS since the offered QoS value of single services may change the others QoS attributes of the same service, as well as the
as soon as new offers and counteroffers are exchanged. constraints to be fulfilled by the QoSs of the other services. In
other words, negotiating over the attributes of the single AS
Practical negotiation mechanisms for B2B applications cannot be done independently from each other.
must be computationally efficient [9]. This implies that the
interaction rules have to guarantee the quick end of the process Since SC does not provide counteroffers the negotiation
and that agents behaviors and negotiation strategies should be could be model as simply an auction mechanism as in [13].
developed based on the assumption of bounded rather than However, in order to model a real market of services, it cannot
perfect rationality [10]. One of the common requirements for be assumed that all providers, providing different functional-
a negotiation protocol is the monotonicity of the utilities of ities, follow the same rules when bidding (such as Vickrey,
the offers as in [11]. This allows to guarantee the end of the English, and so on), as it happens in auctions mechanisms.
process without a deadline: either an agreement is reached In fact, rules may vary according to the type of provided
(sooner or later), or a conflict is reached in the case all agents service (i.e., its functionality), and above all according to the
stop to concede in utility. trends of the market that may vary quickly, and not in the
same way for all the QoS attributes. With auction mechanisms,
Most approaches, that use negotiation mechanisms to se- each bidder may have its own strategy, but once the type of
lect services according to their QoS values, usually apply auction is decided, then all bidders know the rules and they
have to stick to them until the auction ends. Moreover, a simple new m∗n cfps. If the QoS values of the received offers, once
auction mechanism cannot be used in our setting because of the aggregated meet the user request, it accepts the offers sent by
interdependence among the QoS attributes of the component the corresponding SPs (sending m accept proposals and
services. In fact, it would not be possible to award an auction m ∗ n − m reject proposals). If the deadline is reached
winner without evaluating the offers for a given AS with without a success, the negotiation ends.
respect to the ones received for the other ASs in the AW.
We argue that these solutions do not model what happens in IV. E VALUATING THE N EGOTIATION C OST
real markets of services where predefined bidding mechanisms
cannot be assumed and fixed for all the service types and We evaluate experimentally the efficiency of the negotiation
for all the considered QoS attributes. Therefore, traditional mechanism with respect to two performance measures: negoti-
methods with the protocols and strategies hard-coded in the ation outcome (i.e., utility of the solution and/or the negotiation
agents would not work in real market of services that are open success rate), and communication complexity (i.e., the number
systems. of exchanged messages), by varying the parameters affecting
the OMM protocol that are the number of allowed negotiation
This is why an hybrid negotiation approach was used, rounds, and the number of SPs involved in the interaction.
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 A. Compositor and Providers Utility Functions and Strategies
when bidding, and also to change them if required by the Here, we briefly describe the decision making algorithm
market trends. for the SC evaluation of proposals, and the strategies adopted
by SPs to generate an offer, as proposed in [5], considering
the case of a single additive QoS parameter (the parameter
considered here is the “price”).
Following the approach formulated in [8], the SC first
evaluates the utility of the offer provided by the jth SP for
the ith AS, with respect to both the other offers for the
same AS (local evaluation), and to the entire workflow (global
evaluation):
maxk (pricei,k ) − pricei,j
USC (oi,j ) = Pm (1)
i=1 (maxk (pricei,k ) − mink (pricei,k ))
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
Figure 1. The negotiation protocol.
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:
In [5], we presented a one-to-many-to-many protocol
(OMM) for the dynamic selection of services, based on the
FIPA Contract Net Iterated Protocol [14], [15] (ICNET), one of Pm
the most used protocols for negotiating SLAs [4]. As described 1
if i=1 pricei,s < reqP rice
in Figure 1, the negotiation occurs between the SC, that is the USC = (2)
1 − m
P
initiator of the negotiation, and the SPs available for each AS i=1 pricei,s −reqP rice
reqP rice otherwise
of the AW, and it may be iterated for a variable number of times
until a deadline is reached or the negotiation is successful. The where, pricei,s Pis the price offered for the ith AS by the
deadline is the number of allowed rounds. The SC prepares m m
selected sth SP, i=1 pricei,s is the aggregated value for the
call for proposals (cfps), one for each AS in the AW and, price, and reqP rice is the user requested price.
assuming that there are n SPs for each of the m AS, it sends
m ∗ n cfps at each negotiation round. After waiting for the On the contrary, SPs apply their own strategies to formulate
time set to receive offers, if there are not offers for each AS their offers. These strategies are modeled as a set of functions
in the AW, the SC rejects the received proposals (reject that are both time and resource dependent [16], and they take
proposal) since it is not possible to find a CS corresponding into account both the computational load of the provider,
to each AS. Otherwise, it evaluates the received offers, and, if and the computational cost of the provided service. The
the QoS value obtained by aggregating the received offers does computational load of the provider accounts for the number
not meet the user request, it starts another negotiation round of requests it agreed to fulfill, i.e., the amount of service
sending m ∗ n reject proposals, and, at the same time, implementations it will deliver, while the computational cost
of the service represents a measure of the complexity of the
provided service, i.e., the more complex the service is the
higher its expected cost is. SPs strategies to concede in utility
are modeled as Gaussian distributions [5]. The mean value of
the distribution maxU is the best offer the SP may propose
in terms of its own utility and as such it has the highest
probability to be selected. The standard deviation σ represents
the attitude of the SP to concede during negotiation and it
varies from SP to SP providing the same AS, so that the
lower the SP’s computational load is, the more it is available
to concede in utility and the lower its reservation value is. The
best offer maxU is the same for all SPs of the same AS. This
assumption models a scenario where services providing the
same functionality have the same “market price” corresponding Figure 2. Success rate varying the number of rounds and the number of SPs
to the maximum utility for the SP providing that service. for each AS.
At each negotiation round, the SP generates, following its
provision strategy, a new value of utility corresponding to a 16) for each AS is plotted. In Table I the same percentage
new offer to be sent to the SC by comparing the new offer with is plotted, varying the number of rounds, but in the case of
the previously generated one to decide whether to submit it or negotiation with only the “best” SP for each AS. As expected,
not. This is a variation of the standard negotiation mechanisms for a deadline of 1 round (simple CNET protocol) we have
where the utility of a new generated offer is compared with 100% of failures since the specific settings of the tests require
the last one generated by the other negotiation partner. a negotiation phase to find a solution. In Table I the results
show that selecting the best SP at round 1 does not reduce
B. Experimental Settings the negotiation cost. In fact, only the 12% of success rate is
obtained with 30 or 40 rounds of negotiation allowed, so the
The configurations considered for the experiments set five computational cost of the negotiation is not compensated by
different deadlines at 1, 10, 20, 30 and 40 rounds, and for each an high rate of success. A better trend is obtained by adding
deadline the number of SPs at 2, 4, 8, 16. Let us highlight another provider for each AS (as shown in Figure 2). In fact,
that for a deadline of 1 round, the protocol is based on m in this case, with 30 or 40 rounds of negotiation allowed, 50%
concurrent ContractNet Protocols (CNET). We also considered of successes are obtained. Scaling up the number of SPs from
a configuration where the negotiation occurs only with one SP 4 to 16 the success rate increases from 90% to 100% just after
for each AS, that is the best SP, in terms of USC (ox ), according 10 rounds. These results support the choice to negotiate with
to the offers received at round 1. In this case the deadline varies all the available SPs, as proposed by the OMM protocol, since
from 10 to 40 rounds. the cost of negotiation is partially compensated by an increase
In the configurations there are 5 ASs, AS1 , AS2 , AS3 , in the negotiation success rate.
AS4 , AS5 , with a computational costs decreasing from AS1
Table II. N UMBER OF MESSAGES VARYING THE NUMBER OF SP S AND
to AS5 . The user requested price is 1500$ (reqP rice). For THE DEADLINE .
each AS a default price bestP ricei is set, and the corre-
# SPs
sponding SPs will send as initial offer a price randomly 1 2 4 8 16
extracted in the neighborhood of bestP ricei [bestP ricei − 1 15 30 60 120 240
# rounds
5%∗bestP ricei , bestP ricei ]. This is because, even though the 10 150 300 600 1200 2400
20 300 600 1200 2400 4800
market price of services corresponding to the same AS is the 30 450 900 1800 3600 7200
same, to model a real market of services the variability of the 40 600 1200 2400 4800 9600
first offered price is introduced. In the experiments, the market
prices for the ASs are: bestP rice1 = 540$, bestP rice2 = In order to evaluate the computational cost of the OMM
468$, bestP rice3 = 351$, bestP rice4 = 270$, bestP rice5 = protocol, also the number of exchanged messages are consid-
216$. The σ value randomly varies for each SP in the range ered. At each negotiation round the SC sends m ∗ n cfps,
[0.0, 0.5], so including the possibility that SPs with the receives at the most m ∗ n possible offers, and it sends back at
maximum computational load are not willing to concede. most m ∗ n accept and/or reject messages. This means that for
each round the cost of communication in terms of exchanged
C. Evaluation of Results messages is 3 ∗ n ∗ m. The numbers of messages are reported
in Table II for all the experimental configurations.
In all the experiments 100 tests were performed for each
of the described configurations. A comparative evaluation of Table II and Figure 2 is
shown in Figure 3 that provides information on the trade-
Table I. S UCCESS RATE VARYING THE NUMBER OF ROUNDS WITH off between communication costs and success rate. In par-
ONLY THE “ BEST ” SP FOR EACH AS. ticular from configurations with 2400 exchanged messages
Rounds 10 20 30 40 to configurations with 9600 no variation in success rate is
1SP for AS 1% 6% 12% 12% obtained (that is stable at 100%). This means that from 2400
onward there is only a communication overhead without any
In Figure 2 the percentage of negotiation successes varying gain in the success rate. A first conclusion of this evaluation
the number of rounds and the number of SPs (from 2 to is that negotiating with 16 SPs for each AS with respect to
Figure 4. The SC’s utility for different configurations in case of tests that led to a success (on the left) or to failure (on the right).
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.
Figure 3. Success rate evaluated with respect to the number of messages.
Table III. SC’ S UTILITY VARIATION IN CASE OF FAILURES .
Round Range
10/20 20/30 30/40
negotiating with 8 SPs will not change the success rate, but it
#SPs
2 0,0223 0,0082 0,0042
will only require more exchanged messages. So, in this case, 4 0,0221 0,0043 0,0083
selecting a subset of available providers reduces the cost of Average 0,0222 0,0063 0,0062
STD 0,0002 0,0028 0,0029
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. In Table III the SC’s utility variation in case of failure
However, a bigger number of SPs, as shown in the following is reported in order to allow the SC to dynamically stop the
figures will provide a quicker achievement of the agreement, negotiation according to its trend, i.e., according to whether
so reducing the negotiation length. Such evaluation of the and in which measure its utility is varying. The variation is
number of exchanged messages with respect to the success calculated as a difference between the value of the SC’s utility
rate shows that, in the case of a relevant number of available respectively at rounds 10 and 20 (for the first column), at
providers, long negotiation mechanisms are not necessary. So, rounds 20 and 30 (for the second column), at rounds 30 and 40
in the following experimets only negotiation deadlines smaller (for the third column). The variation is evaluated varying the
than 40 rounds will be considered. number of SPs (2 and 4). The average SC’s utility variation,
and the corresponding standard deviation are also reported. As
In Figure 4 the variation of the SC’s global utility is shown in Table III, in the configurations with the number of
reported at different negotiation rounds varying the number of SPs equal to 2 and 4, by increasing the number of rounds
available SPs and the deadline of the negotiation. In particular, the SC’s utility variation is less than 1% after 20 rounds, so
on the left cases leading to success are considered varying the indicating that keeping on negotiating is not likely to lead to
number of SPs for each AS from 2 to 16, and the deadline a success.
V. C ONCLUSIONS AND F UTURE W ORKS different set of strategies to evaluate the negotiation cost in
different experimental settings.
Software agent negotiation is considered a promising
approach for modeling the interactions between a service
ACKNOWLEDGEMENTS
consumer and service providers when composing QoS-aware
Service Based Applications. It is well recognized that the pro- The research leading to these results has received fund-
vision of such applications will be regulated by an agreement ing from the EU FP7-ICT-2012-8 under the MIDAS Project
between the application consumer and the providers of the (Model and Inference Driven - Automated testing of Services
component services stating agreed terms and conditions related architectures), Grant Agreement no. 318786, and the Italian
to both functional and non-functional application features. In Ministry of University and Research and EU under the PON
particular, the negotiation mechanism is suitable to model the OR.C.HE.S.T.R.A. project (ORganization of Cultural HEritage
interactions occurring among consumers and providers when for Smart Tourism and Real-time Accessibility).
services are provided according to market-based mechanisms
and when dynamic features, like QoS ones, have to be con- R EFERENCES
sidered.
[1] M. Papazoglou, P. Traverso, S. Dustdar, and F. Leymann, “Service-
Nevertheless, automated negotiation did not succeed in real oriented computing: State of the art and research challenges,” IEEE
Computer, vol. 40, no. 11, pp. 38–45, 2007.
service-oriented market scenarios since it is computationally
[2] J. Yan, R. Kowalczyk, J. Lin, M. B. Chhetri, S. K. Goh, and J. Zhang,
expensive in terms of the involved decision making mech- “Autonomous service level agreement negotiation for service composi-
anisms, and the communication overhead deriving from the tion provision,” Future Generation Computer Systems, vol. 23, no. 6,
complexity of the communication patterns. pp. 748 – 759, 2007.
[3] A. Keller and H. Ludwig, “The wsla framework: Specifying and
In this work, an evaluation of the cost of the negotiation monitoring service level agreements for web services,” J. Network
mechanism proposed in [5] is carried out with the aim to System Management, vol. 11, no. 1, pp. 57–81, 2003.
extract useful information to limit the length of the negotiation [4] S. Paurobally, V. Tamma, and M. Wooldrdige, “A framework for web
and also its communication overhead. service negotiation,” ACM Trans. Auton. Adapt. Syst., vol. 2, no. 4, Nov.
2007.
The experiments were carried out for different configura- [5] C. Napoli, P. Pisa, and S. Rossi, “Towards a dynamic negotiation mecha-
tions obtained by varying the two parameters affecting the cost nism for qos-aware service markets,” in Trends in Practical Applications
of communication that are the number of involved negotiators, of Agents and Multiagent Systems, ser. Advances in Intelligent Systems
and Computing. Springer International Publishing, 2013, vol. 221, pp.
i.e., the number of SPs, and the number of negotiation rounds 9–16.
determining the length of the negotiation. The results showed [6] L. Zeng, B. Benatallah, A. H. Ngu, M. Dumas, J. Kalagnanam, and
that the increase in communication costs due to the possibility H. Chang, “Qos-aware middleware for web services composition,” IEEE
of negotiating with all the SPs instead of just one for each Transactions on Software Engineering, vol. 30, no. 5, pp. 311–327, may
service type, is partially compensated by the fact that by 2004.
increasing the number of SPs the success rate of the negotiation [7] D. Ardagna and B. Pernici, “Adaptive service composition in flexible
increases. In fact, in the case the best SP is selected to processes,” IEEE Trans. on Software Eng., vol. 33, no. 6, pp. 369–384,
2007.
continue the negotiation, a 100% failure is obtained also by
[8] M. Alrifai and T. Risse, “Combining global optimization with local
increasing the length of the negotiation. This is because in selection for efficient qos-aware service composition,” in Proceedings
a market of services, that is dynamic by nature, it is not of the 18th Int. Conf. on World Wide Web, ser. WWW ’09. New York,
possible to assume that a promising provider will keep on NY, USA: ACM, 2009, pp. 881–890.
sending promising offers, because a less promising provider [9] R. Y. K. Lau, “Towards a web services and intelligent agents-based
may change its strategy in the meantime according to market negotiation system for b2b ecommerce,” Electronic Commerce Research
trends and/or market strategies that are tied also to the specific and Applications, vol. 6, no. 3, pp. 260–273, 2007.
service or quality attribute. So, the choice of negotiating with [10] A. Lomuscio, M. Wooldridge, and N. Jennings, “A classification
scheme for negotiation in electronic commerce,” Group Decision and
all the SPs is supported by the obtained results. Furthermore, Negotiation, vol. 12, no. 1, pp. 31–56, 2003.
in most configurations, the overhead due to the communication
[11] G. Zlotkin and J. S. Rosenschein, “Mechanism design for automated
cost is partially compensated by a decrease in the negotiation negotiation, and its application to task oriented domains,” Artif. Intell.,
length, i.e its overall computational cost. vol. 86, no. 2, pp. 195–244, 1996.
[12] F. Siala and K. Ghedira, “A multi-agent selection of web service
In some cases the negotiation progress in terms of the providers driven by composite qos,” in Proc. of 2011 IEEE Symposium
distance between the requested QoS and the QoS obtained at on Computers and Communications (ISCC). IEEE, 2011, pp. 55–60.
each negotiation round shows that it is not worth to proceed [13] P. R. Wurman, M. P. Wellman, and W. E. Walsh, “The michigan internet
with the negotiation after a certain number of rounds since no auctionbot: a configurable auction server for human and software
gain is obtained in the success rate. This means that in these agents,” in Proceedings of the second international conference on
Autonomous agents, ser. AGENTS ’98. New York, NY, USA: ACM,
cases the negotiation can be stopped without any loss in terms 1998, pp. 301–308.
of consumer’s utility, so limiting the cost of negotiation in
[14] R. G. Smith, “The contract net protocol: High–level communication and
terms of its length. Of course, these results are related to the control in a distributed problem solver,” IEEE Trans. on Computers,
considered configurations, and also to the specific strategies vol. 29, no. 12, pp. 1104–1113, 1980.
adopted for the SPs. [15] “Fipa iterated contract net interaction protocol specification.”
[16] P. Faratin, C. Sierra, and N. R. Jennings, “Negotiation Decision Func-
We plan to extend the proposed negotiation mechanism by tions for Autonomous Agents,” Robotics and Autonomous Systems,
including the possibility for the SPs to change their strategies vol. 24, pp. 3–4, 1998.
on fly, and to carry out more experiments by considering