Cloud service negotiation framework for real-time E-commerce application using game theory decision system

2.1 Negotiation framework

To negotiate with a physical resource of different cloud infrastructure, a resource negotiator addressed as future work for integrating into a real cloud test bed [9]. Current negotiation models support only time and price-based negotiation without any decision-making model [10]. In order to support negotiation with advanced reservation, Current Price and Timeslot Negotiation (CPTN) is proposed using alternating offer protocol, decision-making model and trade-off algorithm to increase total utility and negotiation speed, and reduces computational load [11]. The decision-making algorithm and new policies are required for complex and advanced resource allocation in a time-critical application to overcome the existing best effort policy [12]. This multilateral negotiation framework in the cloud market consists of multiple one-to-many negotiations, which identify the best fit of user requirement [13]. For successful negotiation to take place between provider and consumer, a negotiation framework and protocol has to define and bargaining solutions are to be optimized [14].

2.2 Negotiation protocols

A conversation protocol between the parties can be either bilateral or multilateral. The bilateral protocol used in one-to-one negotiation model, and multilateral protocol used in case of one-to-many, many-to-one and many-to-many negotiation models [15]. None of them addressed the negotiation specific protocol, architecture and comparison of its requirement elaborately [16]. The framework developed using the Contract Net Protocol (CNP) makes effective web service negotiation between the insurance and repair companies. The CNP specifies the communication and control for problem-solving in the distributed nodes using resource allocation and effective selection of tasks respectively [17].

In the cloud, dynamic resource allocation uses automated negotiation, which extends the Alternate Offer Protocol (AOP) for supporting bilateral negotiation [18]. In the multi-agent system, an Alternate Offer Protocol extended for improving the efficiency of protocol concerning the percentage of failure, length of bargaining, computation cost, participation rate and fairness. As a test bed, agent-based simulation is used for protocol design and “Pareto Optimum” is suggested as a favorable solution for selecting payoff [19]. Logic-based alternate offer protocol introduced to handle this conflicting information with a suitable agreement where each agent knows its utility function [20]. In the agent-based electronic market, fuzzy multi-agent negotiation proposed with two types of agents where the agents employ time, resource and behavior dependent tactics [21].

2.3 Negotiation solutions

According to negotiation theory, approaches are classified into axiomatic, structural, strategic, procession, behavioral and integrative approaches [22]. The ultimate goal of SLA negotiation is to get a better payoff for both negotiating parties. In the context of game theory, bargaining solutions can be obtained through an axiomatic or strategic approach.

Nash bargaining solution (NBS): Concept of two-person bargaining problem was first introduced by John Nash to establish agreement from the set of possible outcomes obtained from the player’s co-operation [23]. To provide the unique solution to the above problem, Nash proposed the following axioms: Pareto optimality, Symmetry, Invariant concerning Affine Transformations of Utility, and Independence of Irrelevant Alternatives, which describes the behavior of each player [24].

Kalai-Smorodinsky bargaining solution (KSBS): Kalai and Smorodinsky proposed a new solution for bargaining problem that is entirely different from Nash bargaining solution with a limited set of axioms such as Pareto optimality, Symmetry and Invariant. To overcome the difficulty addressed in the paper [25], and to avoid the criticism of the fourth axiom an alternative axiom called Monotonicity is proposed in addition to the above three axioms. The extension of KSBS is proposed where the single-valued solution is identified in the large domain and two axiomatic characterizations such as crucial axiom and three weaker axioms including monotonicity are also presented on the subset of the domain [26].

Egalitarian bargaining solution (EBS): The egalitarian bargaining solution is a third solution introduced by Ehud Kalai for awarding equal gain to both the parties. This solution follows the axiom of Monotonicity and Independence of Irrelevant Alternatives by dropping the condition of scale invariance. An ‘n’ person egalitarian solution is the only bargaining solution presented in the existing research work [27], which is characterized using the symmetric decomposition. The axiomatic approach of bargaining should satisfy the list of properties (Pareto optimality) which requires the available set as comprehensive [28]. Finally, the Table 1 comparison will show the actual difference between the existing and proposed negotiation techniques.

An SLA in the multiplayer bargaining game G is represented as septuplet (P, ρ, U, X, δ, φ, η).

PY = {SCA, TBA_q, SPA_q} is a set of players in the bargaining game where (q = 1, 2,.., n).

ρ = {ρ₁, ρ₂,.., ρ _α , ρ_α +1,.., ρ_m} be the P (ρ^P) or CP (ρ^CP) consist of set of functional parameters ρ₁, ρ₂,.., ρ _α and non-functional parameters {ρ_α +1,.., ρ_m} of the service. U = {U_SCA, U_SPA} is the payoff or utility value in the perspective of SC and SP. X = {x₁,x₂,.., x_n} is the set of negotiable parameters of ρ where X is the proper subset of ρ and n <m.

δ = {δ_i, δ_k} is the responsibility of the negotiation parties where δ_i specifies the conditions on ρ that SCA promised to satisfy and δ_k specifies the conditions on X that SPA promised to satisfy.

φ = {ψ_i, φ_i} is the set of reservation value for the SCA and SPA respectively. Here ψ_i be the upper threshold value that SCA wish to pay and φ_i be the lower threshold value that SPA prepares to accept.

η = {η₁, η₂,..,η_n} is the set of negotiation constraints present in the ρ.

The above multiplayer bargaining game G is modeled using the follows assumptions: (a) All the SPAs are independent and do not cooperate, (b) Both SPAs and SCA are selfish and aim to maximize their revenue, (c) The behavior of the SPA and SCA are determined by the utility function.

3.2 Utility function

The total utility function represents the level of satisfaction for the Negotiation Party (NP) concerning negotiable attributes (X) of the ρ^P or ρ^CP. A utility function estimated for a single and multi-attribute by modeling in two-dimensional spaces as linear and monotone. In the proposed research work, multi-attribute utility function of proposal and counter-proposal is estimated in the perspective of NP, that is, either SCA or SPA which may give different preferences over the utility value U_NP(x_i) and weight W(x_i) of each attribute x_i. The total utility function of the negotiable parameters (X ∈ ρ^P or ρ^CP) of negotiation party U · t NP ( X ) computed as shown in the Equation (3). U · t NP ( X ) = ∑ W ( xi ) * U NP ( x i ) i = 1 , 2 , . . , m(3)

Here the total weight of the attribute should be equal to one i.e. [W(x₁)+ W(x₂)+...+W(x_n)] = 1 and the utility value should be ranges from zero to one i.e. U_NP(x_i) ∈ (0,1). The utility value ‘0’ denotes dissatisfaction and ‘1’ denotes full satisfaction of NP.

In this research work, time-slot, cost, policy, license, device and region scalability are the negotiation attributes considered as SLA parameters or attributes. The utility value of the attribute xi may be high in the perspective of SPA, low in the perspective of SCA and sometimes vice versa. This is because, higher the price will give high utility value for the SPA, lower utility value for SCA, and average utility value for both the parties. Table 2 shows the utility value of negotiable attributes represented in the perspective of both SPA (U _SPA ) and SCA (U _SCA ).

The negotiation strategy tells the process, how the SCA, TBA and SPA negotiate among themselves using the standard protocol and algorithms. In the proposed ADSLANF, a bilateral negotiation is used between the SCA and TBA, and a multilateral (multiple bilateral) negotiation is used between the TBA and SPA. An alternate offer protocol is used for making communication among the parties, which constitutes the negotiation operation. Initially, the ρ^P and the corresponding ρ^CP is generated by SCA in the first round of the negotiation process. This process must iterate until the negotiating parties agree. In this research work, concession and trade-off algorithms are extended with multi-attribute in the SCA and SPA end respectively. The SCA exploits the concession-making algorithm for generating ρ^P by conceding their previous proposal by giving enough discounts on the total utility of the possible proposal. In the opponent side, SPA exploits the trade-off making algorithm for generating ρ^CP by altering the utility of the entire negotiable attribute without making much change in the total utility value of CP.

The SCA exploits Algorithm 1 for handling communication with the TBA and initiates the negotiation process by sending initiate(Negotiation) messages to the broker who in turn responds with the Negotiation ID. Then the Proposal is submitted to the broker and the consumer waits for the reply(Accepted ∥ Rejected ∥ Counter Proposal) message. In case of Accepted reply, SCA will send confirm(Accepted ∥ Rejected) message to the broker and wait for the notification(Accepted ∥ Rejected) message. In case of a Rejected reply, SCA will send confirm(Rejected) message. However, for the reply of Counter Proposal, SCA will checks whether the negotiable parameters p_i value ≤ upper thresholds ψ_i, if yes then it send the confirm(Accepted) message otherwise modifies the Proposal for resubmission and waits for the reply(Accepted ∥ Rejected ∥ Counter Proposal) message.

Algorithm 1 Service Consumer Negotiation Algorithm

In the sense of notification(Rejected) message, the user will not sign the agreement and stop the negotiation process. In case of notification(Accepted) message, the user will send the signed agreement by slaReplay(Document) message and wait for the broker to receive the slaCommit(Document) message.

A Third party broker is an intermediate who uses the Broker Negotiation Algorithm as shown in Algorithm 2 for making communication with service consumers and service providers. As an initial process, the broker will forward the initiate(Negotiation) message to the set of service providers SPA_q and receive the Negotiation ID as a response. Next process, forward the submit(Proposal) message and receives the reply(Accepted ∥ Rejected ∥ Counter Proposal) message from SPA_q. Then forward reply(Accepted) message to SCA for the single Accepted reply, or in case of more than one Accepted reply forward the reply(Accepted) message of best SPA_q who is having less distance. In the case of Counter Proposal reply, the utility function of all the SPA_q is computed and then forward the reply(Counter Proposal) message of the service provider who is having maximum utility value. Otherwise forwards the message as the same in case of the Rejected reply. If all the received replies are Rejected one, then TBA_q decides to send a modify(Proposal) message to SC. On behalf of SC, it just forward the confirm(Accepted || Rejected) message. After receiving the notification message from SPA_q, it forwards the notify(Accepted) message and stops the negotiation for the notify(Rejected) message. As a final process, it forwards the slaReplay (Document) and slaCommit(Document) message from SC and SPA_q respectively.

Algorithm 2 Broker Negotiation Algorithm

The service provider exploits the Service Provider Negotiation Algorithm as shown in Algorithm 3 for making communication with the TBA_q. As the first process, SPA_q receives the request and sends back the Negotiation ID as a response. Then receives the Proposal message and check whether the negotiable parameters p_k value ≥ φ_i, if yes send the reply(Accepted) message otherwise check whether the negotiable parameters p_k value < φ_i, if yes send the Rejected reply else it reply with the Counter Proposal message. Next process, SPA_q receives the confirmation from TBA_q, then it responds with notify(Accepted) message in case of confirm(Accepted) message and responds with notify(Rejected) message in case of confirm(Rejected) message. Finally, concerning Accepted notification, it waits for the slaReplay(Document) message to send back the slaCommit(Document).

Algorithm 3 Service Provider Negotiation Algorithm

The process of generating proposal and counterproposal using the concession and trade-off making algorithms may lead to an increase in the TNT between the SCA and SPA. This situation arises due to the incompatible generation of P such that it leads to generating multiple CPs without letting to the acceptance of either party. In order to avoid the increase in TNT, the number of iterations involved during the negotiation process is fixed randomly (say 5 or 10). During these negotiation rounds, there is the possibility that the negotiation parties may or may not lead to the acceptance of a proposal or counter-proposal. Therefore, to provide an acceptable and feasible solution a broker uses a decision-making model before reaching the final round of the negotiation process. Moreover, it is tough to select the optimal solution (P with high utility) from the list of CP given by the service providers. A novel decision-making model is represented in the following section using the game theory approach.

3.4 Decision-making model

Central part of the negotiation framework is the decision-making model which helps to find the feasible and acceptable solution for the number of counter proposals generated by each SP. Finally, the TB will choose the optimal solution among the feasible solutions obtained from different SP and suggest that solution as the best offer for signing the agreement. The SC can accept the best offer or select any other offer from the remaining feasible solutions of remaining SP. The negotiation and optimal selection process can be modeled as the bargaining game with one SCA, ‘n’ SPA and a TB with ‘n’ number of agents such as TBA. Since there is no direct negotiation between the parties (SCA and SPA), the proposal and counter-proposal are sent through an intermediate TBA. In this scenario, a bargaining game is considered as a pair of ‘n’ two-player non-zero sum game, i.e., ‘n’ number of one-to-one negotiation between the players. Here the many one-to-one negotiations represent the communication between TBA with SPA. Since TBA is negotiating on behalf of SCA, the mathematical model is derived accordingly.

Let ‘u’ be the utility value of the SCA generated by the TBA_i (i = 1, 2,.., n), ‘v’ be the utility value of SPA_i (i = 1, 2,.., n) and c(S) be the solution point in the set S which is convex, compact and includes the origin. Corollary 1 is developed using the three Utility Theories (1, 2, and 3) [23].

Utility Theory 1: If x is the point in S, i.e., there exists another point y in S with the property u(y) >u(x) and v(y) >v(x), then x ¬ = c(S).

Utility Theory 2: If the set T contains the set S and c(T) is in S, then c(T) = c(S).

Utility Theory 3: If S is symmetric, u and v display this, then c(S) is a point of the form (a, a), that is, a point on the line u = v.

Corollary 1: If the utility pair (u_i, v_i) is a feasible solution to the game G which is symmetrical in the line u = v. Then the optimal solution to the G is derived from the Nash equilibrium solution. This means that the optimal solution is a point p_i with the utility value (u_i, v_i) = (1,1) for the players which gives the maximum and equal utility to both players.

Proof: Let us plot the utility of the CPs generated by multiple SPAs by taking u ( U · SCA t ) along X-axis and v ( U · SPA t ) along Y-axis. Now draw the tangent in the first quadrant with the angle of 45⁰ (say it is the line u = v). To select the optimal solution, randomly choose some points (say p₁, p₂, p₃, p₄, p₅, p₆...p_n) in the line u = v as shown in Fig. 2.

OPEN IN VIEWER

Fig. 2

Optimal solution in the utility pair (u,v).

First, plot the point p₁ as (u₁,v₁) which is the utility pair of first two players i.e. the utility value of SC negotiated by TBA₁ and the utility value of SP₁ negotiated by the SPA₁. For example, give the minimum utility value to both the players, which satisfies the Nash equilibrium solution. Since the utility value ranges from 0 to 1, here 0 is assigned to be the minimum utility value for both the players.

p 1 = ( u 1 , v 1 ) = ( 0 , 0 )(4)

Similarly, plot the point p₂, p₃, p₄, p₅, p₆... p_n for the other set of players with their corresponding next higher utility value such as (u₂,v₂), (u₃,v₃), (u₄,v₄), (u₅,v₅), (u₆,v₆)... (u_n,v_n) where (u_n,v_n) is the maximum utility value of the players. p 2 = ( u 2 , v 2 ) = ( 0.1 , 0.1 )(5)p 3 = ( u 3 , v 3 ) = ( 0.3 , 0.3 )(6)p 4 = ( u 4 , v 4 ) = ( 0.5 , 0.5 )(7)p 5 = ( u 5 , v 5 ) = ( 0.7 , 0.7 )(8)p 6 = ( u 6 , v 6 ) = ( 0.9 , 0.9 )(9)p n = ( u n , v n ) = ( 1 , 1 )(10)

Hence from the above Equations (4), (5), (6), (7), (8), (9) and (10) it is clear that the optimal solution to i^th pair of ‘n’ two player game with the utility range 0 to 1 is determined as shown in Equation (11). p i = ( u i , v i ) = ( 1 , 1 )(11)