Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

MRT Routing Algorithm for FCFS Scheduling Discipline

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

Publishing Venue

IBM

Related People

Yu, PS: AUTHOR

Abstract

In this article, a computationally efficient transaction routing algorithm is proposed for the case of FCFS discipline at the database server. The MRT algorithm in (*) assumes that the processing systems are with processor sharing service discipline. This assumption implies a product form solution of the model. However, a processor sharing scheduling has an additional cost of switching tasks. It is often that a first-come, first-serve scheme is adopted. Here we investigate an approach which minimizes the estimated response time of an incoming transaction for the FCFS discipline. Background

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

MRT Routing Algorithm for FCFS Scheduling Discipline

      In this article, a computationally efficient transaction
routing algorithm is proposed for the case of FCFS discipline at the
database server.  The MRT algorithm in (*) assumes that the
processing systems are with processor sharing service discipline.
This assumption implies a product form solution of the model.
However, a processor sharing scheduling has an additional cost of
switching tasks.  It is often that a first-come, first-serve scheme
is adopted.  Here we investigate an approach which minimizes the
estimated response time of an incoming transaction for the FCFS
discipline.
Background

      The system to be considered consists of N transaction
processing systems Pi where 1 = 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 FCFS scheduling is used
in each transaction processing system.

      Let there be 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 g k .  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 pathlengths of application processing segments and database
requests.  For each database request issued by txk IO
we assume that an I/O device will be accessed with a fixed
probability pk, and that the mean service time of each I/O access is
dk .  When the execution of an application processing segment is
completed, transaction txk may issue a database request to the
database partition DBi with probability pki or may terminate with
probability pko .
             1
The matrix ---------(pki) shows the distribution of database
           1 - pko
calls issued by txk and is referred to as the reference locality
distribution.  For a given transaction txk, we call the processing
system Pi gets preferred system, if Pi gets a majority of the
database calls.

      Note that in database systems like IMS or DB2*, each
transaction message has an identifier, referred to here as the
transaction class, that indicates which application program to
invoke.  For pre-canned transactions, the execution behavior of each
transaction class can be obtained through trace analysis.  In IMS,
the DL/I trace can provide information on each DL/I call issued by a
transaction.  The average number of accesses to each database can be
obtained for each transaction class.  Based on the database
partitioning, we can then obtain the average number of accesses to
each processing system and thus i...