Agentbased load control strategies

The goal of the agent-based load control strategies is to allocate resources to the arriving user service requests in an optimal way. There are three classes of agents that carry out the tasks necessary to allocate IN resources in this optimal way:

• QUANTIFIER agents that monitor and predict the load and performance of SCP processors (and possibly other IN resources) and report this information to the other agents;

• DISTRIBUTOR agents that maintain an overview of the load and resource status in the entire network and can play a controlling and supervisory role in resource allocation;

• ALLOCATOR agents that are associated with SSPs. They form a view of the load situation in the network and the possibility of resource overload, based on their own predictive algorithms and information received from the other agents. If these agents perceive a danger of overload of resources, they throttle service requests on a priority basis.

The allocation of the processing capacity of a number of SCPs between requests for a number of IN service types can be controlled by strategies using the agents: QUANTIFIERS, DISTRIBUTORS, and ALLOCATORS. A simple network containing SSPs and

(Q Quantifier A Allocator (D Distributor

Figure 1.1

Agent-based load control strategy.

(Q Quantifier A Allocator (D Distributor

Figure 1.1

Agent-based load control strategy.

SCPs, each supporting all service types, is shown in Figure 1.1 and is used to describe agent-based load control strategies.

Computational markets, as applied to resource allocation problems, are generally implementations of the General Equilibrium Theory, developed in the field of microeconomics, whereby agents in the market set prices and create bids for resources, on the basis of demand-and-supply functions. Once equilibrium has been computed from the bids of all the agents, the resources are allocated in accordance with the bids and the equilibrium prices. The search for the market equilibrium can be implemented so that the customer and producer submit bids to an auctioneer. From these bids, the auctioneer updates its information and requests new bids in an iterative fashion. Once the market equilibrium has been found, the allocation of goods is performed in accordance with the bids and market prices.

In the market strategy, load control is carried out by means of tokens, which are sold by MB-QUANTIFIER agents (MB indicates that the agent implements part of a market-based strategy) of providers (SCP) and bought by MB-ALLOCATOR agents of customers (SSP). The amount of tokens sold by an SCP controls the load offered to it, and the amount of tokens bought by an SSP determines how many IN service requests it can accept. Trading of tokens in an auction is carried out so that the common benefit is maximized.

All SSPs contain a number of pools and tokens, one for each SCP and service class pairing. Each time an SSP feeds an SCP with a service request, one token is removed from the relevant pool. An empty pool indicates that the associated SCP cannot accept more requests of that type from the SSP. Tokens are periodically assigned to pools by an MB-DISTRIBUTOR, which uses an auction algorithm to calculate token allocations. Auctions are centrally implemented by an MB-DISTRIBUTOR using bids received in the form of messages every interval from all the MB-ALLOCATORS and MB-QUANTIFIERS in the network.

MB-QUANTIFIER bids consist of the unclaimed processing capability for the coming interval and the processing requirements for each service class. MB-ALLOCATOR bids consist of the number of expected IN service requests over the next interval for each service class. These values are set to the numbers that arrived in the previous interval as they are assumed to be reasonably accurate estimates.

The objective of the auction process is to maximize expected network profit over the next interval by maximizing the increase in expected marginal utility, measured as marginal gain over cost, for every token issued. The expected marginal gain associated with allocating an additional token to an MB-ALLOCATOR is defined as the profit associated with consuming it times the probability that it will be consumed over the auction interval. The expected marginal cost associated with issuing a token from an MB-QUANTIFIER is defined as the ratio between the processing time consumed and the remaining processing time. On the basis of these values, the MB-DISTRIBUTOR implements a maximization algorithm that is iterated to allocate all the available tokens. Tokens are typically allocated to MB-ALLOCATORS with higher bids (i.e., those that expect greater number of requests for service sessions that result in high profits) in preference to those with lower bids.

The operation of the auction algorithm in which there is only one service class supported by the network is shown in Figure 1.2. In the first step, that is, Bid Submission, MB-QUANTIFIERS and MB-ALLOCATORS submit their bids to the MB-DISTRIBUTOR, which then executes the second step, that is, Auction Process. In this figure, dark circles represent tokens, whereas light circles represent token requests; the auction algorithm assigns tokens to token requests. Once the auction is completed, in the third step the

values of token assignments are reported to the MB-ALLOCATORS, which use them to admit service requests in the next time period.

The result of the auction process is that tokens are allocated to balance the arriving traffic load across all SCPs, subject to maximizing the overall network profit.

The following load control strategy is based on Ant Colony Optimization, which is the application of approaches based on the behavior of real ant colonies to optimization problems. The operation of ant-based IN load control strategy is shown in Figure 1.3.

At intervals of length T, a mobile agent AB-ANT, where AB indicates ant-based strategy, is generated for every service type at every SSP in the network and sent to a selected SCP. Each SSP maintains pheromone tables for each service type, which contain entries for all the SCPs in the network. These entries are the normalized probabilities, Pi for choosing SCPi as the destination for an AB-ANT. The destination SCP of an ABANT is selected using the information in the pheromone table following either the normal scheme or the exploration scheme. The scheme used is selected at random, but with the probability of using the normal scheme much higher than the exploration scheme.

In the normal scheme, the SCP is selected randomly, the probability of picking SCPi being the probability Pi indicated in the pheromone table. In the exploration scheme, the SCP is also selected randomly, and the probabilities of selecting all the SCPs are equal. The purpose of the exploration scheme is to introduce an element of noise into the system so that more performant SCPs can be found.

AB-ANTS travel to the designated SCP, where they interact with the local AB-QUANTIFIER agent and then return to their originating SSP. They also keep track of the time they have spent traversing the network. AB-ANTS arriving at the SCP request information from the AB-QUANTIFIER on the currently expected average processing

Figure 1.3 Ant-based IN load control strategy.

times for the service type of interest. Processing times reported are the processing time for the initial message of the service session and the sum of the processing times for all other messages. The separation between the processing times for the initial and subsequent messages is used to highlight the importance of the time spent processing the initial message, by which time the service user would not have received any response from the network. Reported processing times include those incurred in accessing information from databases, which may be held in SDPs in other parts of the network.

Upon return to the SSP, the AB-ANT passes its gathered information to the AB-ALLOCATOR, which then updates the pheromone table entries for its service type, using the following formula.

1 + Ap where i indicates the visited SCP, and Pi is the probability of choosing SCPi. The probability Pj of choosing SCPj is


where a,b,c,d, and e are constants; t1 is time-elapsed traveling SSP ^ SCP; t2 is expected mean SCP processing time for initial message; t3 is expected mean SCP processing time for subsequent messages; t4 is time-elapsed traveling SCP ^ SSP.

The values of a, b, c, and d represent the relative importance the AB-ALLOCATOR gives to each of the four measurements. Requests for service are routed to the SCP that has the current highest priority value in the service's pheromone table. Figure 1.3 illustrates that in normal load conditions the operation of the strategy will mean that SCPs with closer proximity to a source are more likely to be chosen as the destination for service requests, the reason being that the delays AB-ANTS experience in traveling to and from them are lower than for other SCPs.

0 0

Post a comment