Load Balancing

This scenario shows how, under certain conditions, a price mechanism can be used to distribute service load between multiple providers of the same service. Specifically, consider the case where we want to balance the service load between several high-school science QPAs running on separate machines. Each QPA provides the same service, in this case, exactly the same service since each one is just a spawned copy of the same code. We simplified this scenario in a number of ways, assuming that all sites provide free access, and all queries are the same.

In designing the QPAs, we assume they were competitive, and bid their marginal cost, namely what it would cost them to provide another unit of their product. This pricing policy directly reflects the cost to the system of using the input resources to provide this service. QPAs use computational and network resources to produce query planning service. Since these resources get congested as the load on a machine or network gets heavier, the marginal cost of adding another query will increase with the number of queries currently being processed. We modeled this technology in the QPAs using a quadratic cost function:


eqnarray106

Each additional query the QPA produces is priced at its marginal cost. Note that this cost function does not represent any real computer load model, but it does capture the basic notion of using a congested resource. The parameters A and B can be set to reflect relative differences between QPA technologies. For example, a QPA with A,B=1 could be thought of as running on a faster machine than a QPA with A,B=2.

All sellers, or QPAs, make a offers based on their current marginal cost. Buyers, or UIAs, are assumed to want to purchase the query planning service immediately upon bidding. Query planning services are traded in an auction which matches the current lowest price seller with an incoming buyer, as long as the buyer's bid is above that price. Note that because of the way the agents have been designed, we know that this auction is incentive compatible for buyers, i.e., their best bidding strategy is to bid their true value for query planning services. This is because the QPAs who would normally have an incentive to try and strategize about bid amounts, have been engineered to be competitivegif. Once a transaction occurs between a given seller and buyer, both offers are removed from the standing offer list. The QPA recomputes its marginal cost based on having an additional query to process and submits a new, higher, sell offer to the auction.

To see how this results in query load balancing, let's consider what happens where there are two QPAs, (QPA-1 and QPA-2). Given the same initial query load, the sell offers for each agent will be the same, and the first buyer will be matched up arbitrarily with one of them, say QPA-1. At this point, the query load for QPA-1 will rise, causing its marginal cost to rise, and it will submit a new offer at a higher price than before. The next incoming buyer will be matched with the current lowest price seller, QPA-2. QPA-2 now makes its new higher sell offer to reflect its increased load. Assuming that QPA-1 and QPA-2's previous queries are still being processed, both agents are again offering query planning service at the same, although higher, price. If one of QPA-1's queries finishes, then it sends in a new lower offer, and will be matched up to the next incoming buyer. Given a steady load of user queries, this system appears to settle down to an equilibrium price, although we have not done any formal analysis of these results. Notice that the dynamic addition or deletion of an agent does not affect the long-term running of the load balancing mechanism. For example, if any one of the agents were to die, it would only affect the queries that they were processing at that time. Future query planning requests would be matched with the remaining QPAs still participating in the auction. Similarly, spawning a new QPA means that it can start making offers to the query planning auction immediately.

Similar situations where this mechanism would be useful are in the provision of basic library services, which outside agents may not be interested in supplying. By making the agents competitive, UMDL can assure that the system costs are accounted for, that users get a low price, and agent designs are kept simple. Another example is distributing the access load to collections for which the library has a site license. Even though the site license may allow unlimited access, there are still associated network and compute costs, and for popular collections we may want to create mirror sites and distribute the load across them. A consistently high price of access may indicate when a given collection should be mirrored.


Jose M. Vidal
jmvidal@umich.edu
Tue Sep 30 14:35:40 EDT 1997