-In this paper, we suggest an approach aimed at maximising the “global utility” (i.e., QoS) perceived into a large-scale federated computing infrastructures. Our approach computes the node and starts a procedure for the formation of coalitions between them. In particular, it is based on a trust model that allows actors to quantify the trustworthiness of their peers, and on a decentralised procedure that allows the Computing Federation to optimise the QoS. We define the generic SLAbased federated architecture, that is the global QoS offered by the federation, and we describe the theoretical foundation on which our proposal is based. Finally, we illustrate the experimental results which prove that the Global Capital of the Computing Federation improves.
In the last few years, the increasing complexity of grid tasks has brought a remarkable change in the grid infrastructure. In particular, the grid computing paradigm has evolved from the Virtual Organisations (VO) to the federated grid architectures, in which grid brokers and grid institutions share resources among different grid infrastructures thus resulting in a more flexible approach.
Indeed, as grid clients send requests composed by complex requirements, they will relay on the collaboration between grid VOs, which are able to provide specialised resources to the result of the expected computation. Therefore, the main objective is represented by the need of achieving high efficiency in allocating federated resources.
This scenario produces competition among computing
nodes, which want to improve performances provided to their
clients [
In the literature, past proposals present strategies for resource allocation, without to consider trust issues. For this reasons, we present a trust-based approach aiming at maximising the QoS perceived within the grid federation.
Our solution is based on the use of software agents [
In particular, we propose an algorithm for agent Friendship and Group Formation (FGF) to maximise the “global utility” also said Global Capital, of the whole federation. This trust model combines some measures of reliability and reputation to obtain a unique synthetic trust measure.
The plan of the paper is as follows. In Section II, we survey the related work of the recent literature Section III describe the software agent used for the formation of nodes. Section IV introduces the trust model, while in Section V we propose the FGF algorithm for forming friendships and groups. Section VI shows a few experiments to prove the effectiveness of our approach. Finally, in Section VII, we draw our conclusions.
In this section, we survey the literature related to the issue of partner/node selection in the context of self-interested agents and grid systems and focus on the principal metrics proposed to deal with the the problem addressed in this work.
Various types of evaluation metrics were proposed to select
appropriate partners, for example by exploiting local decision
and models [
In this context, the concept of belief can be considered as a
situational awareness, and its modification can require to select
the most appropriate providers for information. To achieve this
aim, the authors suggest the use of social control [
In the information exchange domain, research on belief
revision also involves how to select appropriate
information providers. Belief is, in general, a situational awareness,
and research investigating belief revision in multi-agent
systems [
To solve coalition formation issues among self-interested
agents, negotiation mechanisms (requiring peer-to-peer
communications) can be used to find the best candidates to
join with. The Contract Net Protocol (CNP) [
Coalition formation seeks to partition the agents in a system
into groups which maximise the utility of the group or the
individual agent. The partitioning of the agents is usually
modelled as a characteristic function game and involves three
activities [
Recently, some proposals adopted trust in competitive agent
systems [
In the literature, some works deal with the scheduling
problem on large-scale grids [
In this work, we focus on inter-site groups formation based on trust and resource availability. For this reason, we define that a federated node can be a grid computing element, a grid site or, for instance, a part of a cloud site. Let the federation F consisting of N nodes, we define the set of all heterogeneous resources available on F , as a finite number of R incremental sets of resources, where the R-th set (i.e. the last) includes all the resources available on F . Also, the generic service, requiring for its execution the r-th set of resources, will be identified by sr.
We assume that when the user uj receives a service sr by the node ni (with 1 r R), it has to pay a fee p to the provider ni, whose amount is based on the consumed set of resources and on the waited quality of the provided service. This shows that the context of the proposed federation is “competitive”. Let A be the set of the node agents, each generic agent ai 2 A is associated with the node ni 2 F and denoted by a “skill” mapping i(r) 2 [0; 1] R. In detail, i(r) = 1 means the maximum quality in providing a service which requires the specific set r of resources and, vice versa, for i(r) = 0. Each time a service sr is provided by the agent ai (i.e. the node ni) to the user uj , a feedback f 2 [0; 1] R is returned by uj to ai, where f = 1 means that uj has perceived the maximum level of satisfaction for sr and, vice versa, for f = 0.
Moreover, we assume that each agent ai maintains a set Fi of friend agents, such that Fi A, and a set of groups Gi = fgi1 ; : : : ; gik g where [ gil A. For each service 1<l<k sr, the agent ai can require the support of another node nj (i.e. agent aj ). If aj collaborates with ai by providing the required set of resources and it is a friend of ai or it belongs to the same group of ai, this help is provided for free; otherwise, a fee ps has to be payed from ai to aj after such a support has been provided.
To select the best agents to collaborate for the service sr, the agent ai can require a recommendation recj (r) about the skill j (r) of aj for a given service sr to an agent ak. If ak accepts and it is a friend of ai or it belongs to the same group with ai, this recommendation will be provided for free; otherwise, a price pr has to be payed from ai to ak after the recommendation has been provided.
However, the final choice is performed by the agent ai based on the trust model described in Section IV. In the proposed scenario, we assume that the names of agents, groups and agents belonging to each group have to be appropriately registered in a Directory Facilitator (DF ), published across the different nodes.
In our scenario, let the agent ai, we define, for each set of resources r, two sets: P Ci r that stores the preferred contributors agents contacted in the past to obtain r and P R r that contains the preferred recommenders agents for a
i suggestion referred to r. In particular, P C r assumes the X
i highest trust values T (r) and a trust value greater than the threshold T min. P R r assumes the Y highest honesty values
i O(r) and a honesty value greater than the threshold O min.
To maximise the performance of the services provided by the generic agent ai, its own sets Fi (friends) and g 2 Gi (groups) should only include the agents belonging to P Ci r and P Rir for all the set of resources: [ r2R
P Ci r [ P Rir = Fi [ [ g g2Gi
(1) [ g
The presence of competitive agents also implies that pos- P Air = P Ci r [ P Rir AGi = sible misbehaviours due to malicious agents might happen. g2Gi To this reason, each agent ai maintains a triple of values < REL; O; REP > ranging in [0; 1] 2 R (called respectively [ P Air = Fi [ AGi (2) Reliability, Honesty and Reputation) for each agent aj which r2R ai interacted in the past. The reliability RELij (r) of aj in providing a set r of resources, represents how much ai trusts When some agents belong to the set [ P Air but not to aj in its capability to provide resources for a service sr. r2R Furthermore, once ai received a feedback f for a service sr, Fi [ AGi, there is a loss of performance in providing services if aj has contributed to the service Sr, f will include a share when one of those agents are selected. In particular, we define tfoj its cfondtureibutotioanj. t.haTthuwsillifbaei acssoimgnpeledtetloy idteplerogpaoterdtioanjalilny fcoormapnosaegdenbtyi tawofacctoomr,pcoanlelendts,LoLsi(sT )ofaPnedrfLori(mO)a,ncdee,fiinnedturans providing sr then the feedback f will be totally referred follows: to aj , i.e. fj = f = fj . More formally, the reliability is RELi;j (r) = 1l mX=l1 fjm for l 6= 0 and RELi;j (r) = REL Li(T ) = Pj2 Sr2R PkCSi rr2RFiPSCAiGri FTii;Sj(rA G)ik Ti;altj (r ) for l = 0, where REL is cold start value if there were no previous interactions between ai and other agents. and
The honesty Oi;j (r) of aj in giving a recommendation to (bamiyi.eenr.a,edvpieOnrreagis;gjesi(nnortgm)seat=hlloett1shhoeevmXreds=raiaf1glflejernrreetescnlijmcaienb(ribpl)ierttoywvoiefdfexinnmthgt(ehrae)ajgsf)eee.etnIdtrtbaiaosjcfkicrnsoemsaronepucdurocttmehedes- cLoi(nwOtrh)ieb=ruetoPrrsj2(irseSstphr2.eRprrPekesRfSoeiurrrrr2ecFdRei PrSseeRcAtsoGimriinmewOFnhidii;Secjr(h)rAaaG)gjeikinstOaai;napdltrjea(flretrjr)eids associated recommendation received by ai for some s agents the agent in Fi [ AGi having the best trust (resp. honesty) suggested by aj . If ai has not interacted with other agent, value on r . If aj is a preferred contributor or recommender Oi;j (r) = O, where O is cold start value. agent on more resources sets, r will be the set having the
The reputation REPi;j (r), represents how much, in average, highest trust (honesty) value, then the factor Li(T ) (resp. Li(O)) the agents interrogated by ai provided an estimated value is obtained by computing the average of all these contributions. of capability of aj – in terms of performance referred to In case some agents belong to the set Fi [ AGi but not to the resource set of aj l– which is close to the measured the set [ P Air, we call Additional Cost the ratio of agents value. REPi;j (r) = 1l mX=1 recjm(r) im(r) is the mean of all that wilrl2bRe never contacted by ai to obtain help for free: tahneotrheecro magmenetndaajtioonns arerceesivoeudrcebyseat srpeacnidficwaegiegnhtteadi,baybothuet Ci = k Fi S AGi Sr2R P Air k honesty of the recommenders. If l = 0, REPi;j (r) = REP . k Fi S AGi k
The value of trust is denoted by Ti;j (r) = i RELi;j (r) + We also define the “disadvantage” Di of ai, as the average (1 i) REPj (r), where 2 [0; 1] R weights the relevance of the sum of the factors Li(T ), Li(O) and Ci. Finally, we define assigned by ai to the reliability with respect to the reputation. the Global Capital (GC), by taking into account the whole federation F , as the mean value of all the contributions (1 Di) provided by each agent ai:
GC = kAk
Now, we introduce the Friendship and Group Formation (FGF) algorithm to minimise the disadvantage Di. For each epoch T (i.e., the time occurring between two consecutive epochs), some preferred agents provide to join with the set Fi [ AGi to replace those agents provided of the worst trust or honesty values. The FGF algorithm consists of two parts: the (First Task) is periodically executed by each agent ai to obtain the friendship or the membership in a group of those agents belonging to the set [ P Air but not yet belonging
r2R to the set Fi [ AGi. The (Second Task) is composed of a set of subtasks to handle the requests of friendship of the other agents and those of joining sent by the other agents to the groups with which ai is joined or is a leader (administrator).
First Task. It consists of the following sequence of steps: 1) First, it computes the sets Fi [ AGi, and [ P Air. 2) A friendship request is sent by ai to eachr2aRgent aj 2
[ P Air Fi [ AGi . 3) Thr2eRagent aj is added to Fi if it accepts the friendship
request. 4) If the request is refused, then ai executes the steps: a) ai requires the set Gj of all the groups having aj as a
DF member. b) ai computes the disadvantage Di for each group g 2
Gj . c) ai sends a joining request to all the group g 2 Gj such
that Di < Di. d) If g accepts then this group is added to Gi, otherwise
aj is added to the set Ci. 5) If Ci is not empty, then a call for a new group is sent to all the agents belonging to it by ai. If some agents agree, a new group is formed and registered into the DF. 6) When an agent aj is added to the set Fi, then the worst friend agent ak will be removed from Fi. More in detail, the agent ak is selected as follows: aj 2 P Cir, then the agent ak 62 [ P Air having the worst trust
r2R value i;k(r) is selected; if aj 2 P Rir, then the agent ak 62 [ P Air having the worst honesty value i;k(r)
r2R is selected.
Second Task. It consists of three subtasks: friendship request, membership request and a call for a new group. When aj sends a friendship request arrives to ai, ai computes a new value for the disadvantage Di by adding aj to Fi and, at the same time, it removes an agent ak as described in the First Task. Recall that ai will accept the request coming from aj only if Di Di. When aj sends to the administrator Ag of a group g receives the membership request, then Ag asks for a vote (positive or negative) to all the agents belonging to g. In particular, each agent ak will send a consensus only if the insertion of aj in its same group g will not increase its disadvantage Dk. A call for a new group is sent from an agent aj and it is accepted by ai only if the insertion of aj in the set Fi [ AGi does not increase its disadvantage Di.
The simulation campaign is conducted on a federation of 1000 nodes. We suppose that the nodes show different behaviours in terms of reliability. Recall that the trust model presented in Section IV provides a single value for measuring the reliability of a federated node. For this reason, we simulate an overall index of reliability for each node, which is intended as the final performance, in terms of overall QoS, of the node which provided the service.
In particular, we calculate the nodes reliability by generating
different values for the feedbacks by sampling from a normal
distribution with different mean and standard deviation. We
split the nodes into three groups based on their performances,
i.e. high (H.P.), medium (M.P.) and low (L.P.). Each category
has different values of and . We also suppose that the
number of services per step and the number of
recommendations are independent events. Then, we generate feedbacks
and recommendations by means of the Poisson distribution
with parameter = 50 (mean) for the feedbacks and = 20
for the recommendations. We generate an initial network
of agents/nodes by setting the degree of the nodes (i.e. its
probability distribution) being compliant to a power function
P (x) = Cx , where = 2:5 [
Now, we show some experiments aimed at confirming that the execution of the FGF algorithm will give a contribution by lowering the Disadvantage D.
Recall that the collaborators for services were selected on the basis of the trust system, as described in Section IV. The Figures 1a-1b supply the median, quartiles and outliers of D for a set of simulations for which we set min = min = 0:2, i.e. the minimum value of trust and honesty to select the sets P C and P R, as previously discussed in Section V. While Figure 1a summaries the results for X = Y = 10, Figure 1b refers to X = Y = 40, where X and Y are the maximum size of the sets P C (Preferred Contributors) and P R (Preferred Recommenders). We see that the median value of the disadvantage has a downward trend. Moreover, as the sets P C and P R grow in size from X = Y = 10 (Figure 1a) to X = Y = 40 (Figure 1b), the median assumes lower values very quickly, which is the expected behaviour.
Results shown in Figures 1c and 1d report the median value of the Disadvantage D, for X and Y ranging from 10 to 40 by steps of 10. Moreover, in Figure 1c we set min = min = 0:2, while in Figure 1d we set min = min = 0:5. By comparing data of the two figures, we can observe that the more selective is the parameter min (resp. min), which is the minimum value of trust (resp. honesty) to put a node 0.3 0.25 into the set PC (resp. PR), the greater will be, in average, the disadvantage. campaign.
In this paper we presented an agent based model aimed at optimising the global QoS provided in a Federation of computing infrastructures. In this scenario, the nodes are supported by software agents that manage friendships and group memberships. In particular, we introduced the following concepts: (i) computational resource sets that support tasks in the federation, (ii) agent aggregation (i.e. friendships and group memberships) as basis of collaboration among federated nodes, (iii) the nodes are supported by a trust model that compute a unique synthetic trust measure.
We propose the algorithm called FGF that supports the federated nodes to select their partners (friends and group memberships) for improving the global QoS. For this reason, the algorithm exploits trust information to calculate two measures: the (i) disadvantage (D) and the (ii) Global Capital (GC).
We presented a few experiments which allowed us to prove that the Global Capital (which reflect the global QoS) of the Global Federation is effectively improved. In our ongoing research, we plan to compare the performance of the FGF algorithm with other similar approaches which are based on aggregations and trust information.