Browse Prior Art Database

FMRT: An Efficient Transaction Routing And Load Sharing Algorithm

IP.com Disclosure Number: IPCOM000120112D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 6 page(s) / 230K

Publishing Venue

IBM

Related People

Lee, YH: AUTHOR [+2]

Abstract

An efficient transaction routing strategy, FMRT (Fast MRT), in a locally distributed database environment is proposed in this article. The transactions in this environment have reference localities which imply that certain processing systems can be identified as being more preferred than others. Response time based routing strategies can strike a balance between sharing the load and capturing the transaction affinity to the heterogeneous processing systems. Since response time estimates involve either iterative MVA algorithm or approximations, efficient algorithms are needed for practical implementations.

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

FMRT: An Efficient Transaction Routing And Load Sharing Algorithm

      An efficient transaction routing strategy, FMRT (Fast
MRT), in a locally distributed database environment is proposed in
this article.  The transactions in this environment have reference
localities which imply that certain processing systems can be
identified as being more preferred than others.  Response time based
routing strategies can strike a balance between sharing the load and
capturing the transaction affinity to the heterogeneous processing
systems.  Since response time estimates involve either iterative MVA
algorithm or approximations, efficient algorithms are needed for
practical implementations.

      Dynamic transaction routing strategies for this environment
have been studied in (*).  The major issues considered in designing a
dynamic strategy include (1) what information is crucial to decision
making, and (2) how to use easily collectable and maintainable
information to make the routing decisions.  A class of dynamic
strategies based on an attempt to minimize each incoming
transaction's response time, referred to as the MRT strategy, was
proposed and studied.  MRT uses information readily available at the
front-end system, such as the previous routing decisions for
transactions currently in the complex, in a steady-state estimation
of queue length and response time for each possible routing.  It has
been demonstrated that system performance can be greatly improved if
this concept of minimizing the response time of incoming transactions
is used.  The same concept can be applied to a shared database or
replicated database environment.  In fact, the MRT strategy uses
transaction response time as an integrated measure that reflects the
impact of system load and transaction affinity.  When making routing
decisions, this measure is much more general than CPU utilization and
is the very factor that we need to optimize.
Background
The System Model

      The system to be considered consists of N transaction
processing systems. Pi where i = 1,2,...,N, and a front-end system,
connected by a high-speed interconnect.  There is a partitioned
database that consists of DB1,...,DBN, where DBi is attached to the
processing system, Pi .  All database requests to DBi are assumed to
be handled by the processing system Pi .  The processor speed of Pi
is denoted as mi . Also, we assume that the process sharing
scheduling is used in each transaction processing system.

      Let there by K transaction classes in the system and let txk
denote a class k transaction, k = 1,...,K.  For the k-th class,
transactions arrive according to a time-invariant Poisson process
with rate gk .  The mean processing service demands of the
application processing segment and database requests of txk are ak
and bk, respectively.  Both ak and bk can be estimated by measuring
the path lengths of application processing segments and database
requests.  For each database...