Browse Prior Art Database

Adaptive Load Sharing Strategy

IP.com Disclosure Number: IPCOM000101178D
Original Publication Date: 1990-Jul-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 4 page(s) / 176K

Publishing Venue

IBM

Related People

Yu, PS: AUTHOR

Abstract

A strategy is described that addresses the effect of information lags on load sharing in a distributed database environment. It explicitly takes the information obsolescence into account when making routing decisions and weights older information less heavily than more up- to-date information. Databases are partitioned across multiple sites and transactions can be executed at any site where, for non-local database access, database call needs to be shipped to the remote site owning the database. This is referred to as remote database call. Because dynamic state information is not immediately available to the various sites, decisions which are naively made based on the obsolete information that is currently available will be non-optimal.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 35% of the total text.

Adaptive Load Sharing Strategy

       A strategy is described that addresses the effect of
information lags on load sharing in a distributed database
environment.  It explicitly takes the information obsolescence into
account when making routing decisions and weights older information
less heavily than more up- to-date information.  Databases are
partitioned across multiple sites and transactions can be executed at
any site where, for non-local database access, database call needs to
be shipped to the remote site owning the database.  This is referred
to as remote database call.  Because dynamic state information is not
immediately available to the various sites, decisions which are
naively made based on the obsolete information that is currently
available will be non-optimal.  In this environment sites must solve
the problem of whether to select alternative sites to process
incoming transactions, given that the information on which the
decision is based exhibits varying degrees of obsolescence.  We
present an adaptive strategy that explicitly takes the obsolescence
into account when making routing decisions, and weights older
information less heavily than more up-to-date information.

      The proposed Adaptive strategy consists of three steps. In the
first, each site estimates the response time of incoming
transactions.  Then, as transactions are processed and leave the
system, sites track the transaction's actual response time, and
record its critical characteristics with respect to the factors
discussed above.  This enables the system to monitor how well actual
response time conforms to the estimate.  Finally, the system
adaptively adjusts future estimates by periodically recalculating
coefficients that are used to weight the factors in response time
estimation.

      Assume that there are K classes of transactions.  Let Rai
represent the actual response time of the i-th class k transaction,
Rei its estimated response time similar to that under the minimum
response time (MRT) strategy in (1) Xki =1 if a remote routing
decision is taken for that transaction (0, otherwise); and let Tki be
the difference between the current time and the time of the last
information update from the site to which the transaction is routed.
It seems reasonable that a transaction's response time, when routed
to a specific site, will depend on (a) the MRT estimate which
considers a transaction's database-site reference locality and
short-term load at the destination site, (b) whether the site is the
transaction's preferred site, which is the site resulting in the
smallest number of ADAPTIVE LOAD SHARING remote calls, and (c) the
age of the information used in the MRT estimate.  We know that the
MRT estimate corresponds closely to actual transaction response time
(under perfect information assumptions).  We introduce the "preferred
site" factor because if the MRT estimate is at all inaccurate it
makes sense to err on the side of caution...