IEEE TRANSACTIONS ON SOFTWARE ENGINEERING. VOL. 14, NO. 9, SEPTEMBER 1988
`
`Dynamic Transaction Routing in Distributed Database
`Systems
`
`1307
`
`this paper, we investigate dynamic transaction routing
`Abstract-In
`strategies for locally distributed database systems in which the data-
`base is partitioned and distributed among multiple transaction pro-
`cessing systems, and the incoming transactions are routed by a com-
`mon front-end processor. In this environment, if a transaction issues
`a database request referencing a nonlocal database partition, the re-
`quest has to be shipped to the system owning the referenced partition
`for processing. Various dynamic strategies are studied. Their perfor-
`mance is compared with that of the optimal static strategy. A new class
`of dynamic transaction routing strategies which take into account rout-
`ing history and minimize the estimated response time of incoming
`transactions is proposed and found to provide a substantial improve-
`ment over the optimal static strategy. The robustness of the strategies
`is further studied through sensitivity analysis over various transaction
`loads, communication overheads and database reference distributions.
`
`Index Terms-Distributed database systems, load balancing, perfor-
`mance analysis, queueing models, transaction routing strategy.
`
`I. INTRODUCTION
`HEN processing power is distributed over multiple
`computer systems, load sharing is critical in achiev-
`ing higher aggregate throughput and better response time.
`To attain appropriate sharing, arriving tasks are allocated
`according to some strategy. Strategies are static in nature
`if allocation decisions are based solely on the static char-
`acteristics of arriving tasks and the processing systems.
`Other strategies, in which allocation decisions depend
`upon not only the static characteristics but also the current
`system state, are referred to as dynamic.
`Numerous load sharing strategies, both static and dy-
`namic, have been studied for different types of distributed
`systems. Queueing network analysis, mathematical pro-
`gramming, and other techniques can be used to obtain
`performance estimates and then to derive optimal static
`strategies; for example, the optimal deterministic alloca-
`tion of tasks in [16], [17], and optimal probabilistic as-
`signments in [12], [18]. On the other hand, certain opti-
`malities
`in
`the dynamic approach have also been
`discovered. For instance, the send-to-shortest queue strat-
`egy is found to be the best for the case of Poisson arrivals
`and identical exponential servers [20] and the round-robin
`
`Manuscript received March 17, 1986; revised March 24, 1987.
`P. S . Yu is with IBM Thomas J . Watson Research Center, Yorktown
`Heights, NY 10598.
`S. Balsam0 is with the Dipartimento di Informatica, University of Pisa,
`Pisa, Italy.
`Y. H. Lee is with the Department of Computer and Information Sci-
`ences, University of Florida, Gainesville, FL 3261 1.
`IEEE Log Number 8822454.
`
`strategy becomes optimal when the queue length at each
`server cannot be observed, provided that all servers have
`the same initial state [IO]. A survey on load sharing strat-
`egies in distributed systems can be found in [ 191. For other
`more complex cases, like heterogeneous servers, multiple
`classes of tasks and different arrival and service time dis-
`tributions, simulations have been adopted to study the
`performance of various strategies [I], [4], [61. In [SI, [91,
`it has been demonstrated that a simple probe limit scheme
`based on queue length threshold is quite effective to im-
`prove performance.
`In these previous studies, it is assumed that incoming
`tasks can be serviced completely at any processing sys-
`tem. This implies that either all tasks are purely compu-
`tational or requested resources, e.g. database or files, are
`shared or replicated among all processing systems. Now,
`consider a locally distributed database environment’ as
`shown in Fig. 1. The database is partitioned among the
`various processing systems, and the arriving transactions
`are routed to one of the processing systems by a common
`front-end system. If a transaction issues a database re-
`quest referencing a remote database partition, the request
`has to be shipped to the system owning the referenced
`partition for processing. This is referred to as a remote
`database request. Thus, a new dimension, the reference
`pattern or the reference locality, has to be considered in
`load sharing strategies.
`The reference pattern of database requests not only
`causes frequent load fluctuation but also complicates rout-
`ing decision making. When the database is partitioned,
`the processing associated with each transaction can be di-
`vided into two categories. The first category denoted as
`routing dependent processing, is to be executed at the pro-
`cessing system to which a transaction is routed. The ap-
`plication process belongs to this category. The other is
`partition dependent processing, which is a service request
`against a particular database partition, e.g., the database
`requests, and can only be executed at the processing sys-
`tem owning the partition. To balance the loads among
`processing systems, only the routing dependent process-
`ing can be used as leverage. In addition, different trans-
`action routing schemes affect the number of remote data-
`base requests and, thus, incur different communication
`loads which are critical to performance. This is in sharp
`
`‘By locally we mean so close together that communication delay is neg-
`ligible, e.g., the entire system is located in the same machine room.
`0098-5589/88/0900-1307$01 .OO 0 1988 IEEE
`
`Petitioner Microsoft Corporation - Ex. 1047, p. 1
`
`

`
`1308
`
`lEEE TRANSACTIONS ON SOFTWARE ENGlNEERlNG. VOL. 14, NO. 9, SEPTEMBER 1988
`
`sumed to be handled by the processing system p,. The
`processor speeds and the I/O access speeds at different
`processing systems are assumed to be identical.
`Transactions submitted by users enter the system
`through the front-end system where transactions get for-
`matted and are routed to one of the processing systems.
`After a transaction processing is completed, output mes-
`sages will be mapped into the user's screen format and
`delivered back to the user via the front-end system. A load
`sharing strategy is employed at the front-end system to
`determine the assignment of an incoming transaction to a
`processing system.
`At the assigned processing system, a transaction in-
`vokes an application process which may issue a number
`of database requests. The application process of a trans-
`action will be executed completely at the assigned pro-
`cessing system, whereas database requests will be exe-
`cuted at the processing systems owning the database
`partitions. During the execution of database request, U0
`device will be accessed if the required data is not in the
`main memory of the processing system. The flow of trans-
`action processing is shown in Fig. 2, where a transaction
`will be completed after several iterations of application
`processing segments and database requests. Transactions,
`then, can be characterized into different classes by 1) the
`processing service demand of each application processing
`segment, 2) the number and reference distribution of da-
`tabase requests, and 3) the processing and I/O service de-
`mands of each database request. For simplicity, we as-
`sume that
`these service demands are exponentially
`distributed. Also, at the end of each application process-
`ing segment, fixed probabilities of issuing a database re-
`quest to a particular database or terminating the transac-
`tion processing are assumed for each class.
`Based on the sequence of transaction processing, we
`construct the model of transaction processing as shown in
`Fig. 3. Let there be K transaction classes in the system
`and let txk denote a class k transaction, k = 1, -
`* , K.
`For the kth class, transactions arrive according to a time-
`invariant Poisson process with rate hk. The mean pro-
`cessing service demands of an application processing seg-
`ment and a database request of txk are ak and bk, respec-
`tively. Both ak and bk can be estimated by measuring the
`pathlengths of application processing and database re-
`quest. For each database requests issued by t&, we as-
`sume that, an I/O device will be accessed with a fixed
`probability pi', and the service time of each I/O access is
`exponentially distributed with mean dk. When the exe-
`cution of an application processing segment is completed,
`transaction txk may issue a database request to database
`DB, with probability Pk, or may terminate with probabil-
`ity P k O . The Pk, is referred to as the database request prob-
`ability of transaction k to DB,. Thus, the total processing
`load of incoming transactions per unit of time to the whole
`system becomes
`
`K
`
`.
`
`
`
`Fig. 1 . The configuration of a locally distributed database system.
`
`contrast with the case of homogeneous system without re-
`mote requests between processing systems.
`In this paper, different dynamic strategies for transac-
`tion routing in a locally distributed database environment
`are studied. The major concerns of designing a dynamic
`strategy are 1) what information is crucial to decision
`making and what is the overhead of collecting the infor-
`mation, and 2) how to use the available information to
`make the routing decisions. We propose a class of dy-
`namic strategies which can provide superior performance
`as compared to the optimal static routing scheme, yet re-
`quire little effort to maintain the dynamic information.
`These strategies are based on routing history of currently
`active transactions along with transaction characteristics,
`and attempt to minimize the estimated response time of
`an incoming transaction. Also considered is a class of
`strategies based on instantaneous queue length informa-
`tion. Well known strategies such as joining the shortest
`queue belong to this class. This class of strategies can be
`costly to implement as frequent message exchanges are
`required to update the queue length information.
`In the next section, the models of locally distributed
`database environment and transactions are described. In
`Section 111, various transaction routing strategies are dis-
`cussed. Section IV presents simulation results on re-
`sponse time under different routing strategies. Detailed
`sensitivity analyses are also provided. We summarize the
`results in Section V.
`11. MODEL DESCRIPTION
`We consider a locally distributed transaction processing
`system as shown in Fig. 1. The system consists of N
`transaction processing systems and a front-end system,
`connected by an interconnection network. The transaction
`processing systems execute transaction application pro-
`cesses and handle database requests. The whole database
`is partitioned into N databases which are denoted as DB,,
`. . . , DB,, where DB, is attached to the transaction pro-
`cessing system PI. All database requests to DB, are as-
`
`Petitioner Microsoft Corporation - Ex. 1047, p. 2
`
`

`
`YU et U / . : DYNAMIC TRANSACTION ROUTING
`
`1309
`
`applleation
`proceasing
`
`opplicotlon
`procesaing
`
`appilcation
`procnalng
`
`Input
`formatting
`
`datobora
`dotobase
`roqueat
`requeat
`to DBI
`to DBI
`(without IO access)
`(wlth IO aceera)
`Fig. 2 . The sequence of transaction processing.
`
`output
`for mottlng
`
`0: opplicotion process
`I: locol dotobose requests
`ov: communication overhead
`r: receiving service and
`remote database requests
`
`P1 - DE1
`
`f
`
`application
`processing
`
`I
`
`-1
`
`formatting
`
`Fig. 3 . Model of transaction processing.
`
`Among this total processing load, there is a portion as-
`sociated with the processing of database requests. We de-
`note the processing load of database requests per unit time
`at Pi as follows:
`
`Notice that S and Sp only depend upon the characteris-
`tics of transactions and are independent of the transaction
`routing decisions. When a database request is issued, it
`must be shipped from processing system PI to PJ if a trans-
`action being executed at PI issues a database request to
`OBJ, where i # j . After the request gets processed, the
`result will be sent back. Both P, and PJ have to perform
`sending and receiving services. The service demands of
`sending and receiving a database request or the results of
`a request are referred to as communication overhead and
`are assumed to be exponentially distributed with mean c.
`The system model is illustrated in Fig. 4. A single
`server processor sharing queue is used to model the pro-
`cessor at each processing system. On the other hand, the
`I/O subsystem of each processing system is modeled as
`an infinite server queue. This is to correspond a global or
`aggregate representation of a more complex U 0 subsys-
`tem. Note that this choice is mainly to simplify the model.
`Extensions to capture I/O contention can be done by ex-
`plicitly considering data allocations and multiple disk
`servers.
`
`~T
`
`. . . . . . . . . . . . . .. . .
`submodel for
`database requests (I k r)
`Fig. 4. Model for locally distributed database system.
`
`In the model, the transmission delay of shipping data-
`base requests in the network is assumed negligible. This
`assumption while reasonable in a locally distributed sys-
`tem, would not be in a geographically distributed system.
`The other simplification in the model is that the overhead
`or the delay due to data conflict and two-phase commit-
`ment is not included. It would be otherwise necessary to
`define a more complicate model than the one presented
`here. In addition, as shown in [21], the routing decisions
`to minimize transaction response times under the optimal
`static routing strategy are not affected whether lock con-
`tention is considered.
`
`111. DYNAMIC TRANSACTION ROUTING STRATEGIES
`We now consider different dynamic transaction routing
`strategies which can be employed at the front-end system.
`As pointed out before, the two major concerns are what
`information to maintain and how to make a routing deci-
`sion based on the available information. To decide on the
`dynamic information, we need to understand which infor-
`mation can be easily maintained at the front-end, and yet
`provide valuable insight for making the routing decisions.
`One class of strategies proposed are based on routing his-
`tory of active transactions along with some static profile
`on transaction characteristics. Here, active transactions
`denote the transactions currently under (or waiting) exe-
`cution in the processing system. This class of strategies
`incurs little overhead, as routing history can be main-
`tained easily in the front-end system. The essential issue
`is to estimate load conditions of the processing systems
`and then make a good routing decision based on this es-
`timate. Different alternatives have been explored, and
`
`Petitioner Microsoft Corporation - Ex. 1047, p. 3
`
`

`
`1310
`
`IEEE TRANSACTIONS ON SOFTWARE ENGINEERING. VOL. 14, NO. 9. SEPTEMBER 1988
`
`some of them lead to very robust performance as shown
`in the next section.
`The other class of strategies considered is based on in-
`stantaneous queue length information of each processing
`system. The queue length of PI is referred to the number
`of tasks being executed at processing system P I , where a
`task is either application processing, database request
`processing or communication overhead * The instanta-
`neous queue lengths are costly to collect, as frequent mes-
`sage exchanges between the front-end system and the pro-
`cessing systems would be required. Surprisingly, we find
`that even ignoring the overhead of collecting the state in-
`formation, the latter class of strategies leads to inferior
`performance compared to the former.
`
`A. Strategies Based on Routing Histoly
`Consider a set of dynamic strategies where the routing
`decision process is based on routing history of active
`transactions along with transaction characteristics. These
`strategies, first, estimate the response time of an incoming
`transaction given that the transaction is routed to the pro-
`cessing system p,. Then the incoming transaction is routed
`to the processing system PI which provides the minimum
`expected response time.
`The routing history of active transactions is maintained
`by the front-end system in a routing history table. Each
`time a transaction txk is routed to P I , the entry in the kth
`row and the ith column of the routing history table is in-
`cremented by one to reflect the new arrival and its routing.
`Furthermore, when a transaction is completed and an out-
`put message is returned to the user through the front-end,
`the entry in the corresponding row and column of the table
`is decremented by one to reflect the departure. Note that
`there is a negligible overhead to maintain the table in the
`front-end system and requires no communications of in-
`stantaneous state information from the processing sys-
`tems.
`Next the issue of estimating the response time is con-
`sidered. The expected response time of an incoming
`transaction depends upon the transient behavior of the
`system and the future arrivals. For efficient implementa-
`tion at the front-end, a steady-state analysis is applied to
`estimate the mean response time using transaction char-
`acteristics and mean queue length at each processing sys-
`tem. From the derivation in the Appendix, the expected
`response time for a transaction txk routed to PI is given as
`
`j # i
`
`(3.1)
`where Li is the mean queue length of Pi and L = ( L l ,
`
`'Note that the number of tasks receiving IO services at system i is not
`included in the queue length.
`
`. * , L N ) . Note that although quite a few parameters ap-
`.
`pears in the above formulas, they are derived from either
`system parameters ( c and p ) , or workload parameters (ak,
`bk, dk, pio, and pkJ) which are provided from the static
`transaction profile. We now present three different ways
`to estimate L, based on routing history.
`I ) Service Time Based Strategy: Consider the moment
`that a new transaction arrives. Let mkl be the number of
`class k transactions assigned to the processing system P I ,
`and not yet completed, i.e., [ m k l ] constructs the routing
`history table. Let probk ( i , j ) denote the probability that
`a class k transaction assigned to processing system P, is
`waiting for or receiving processing service at P, . Hence,
`we can express the expected queue length LJ of P, as
`N
`K
`
`
`(3.2)
`
`for; = 1, . . . , N . Assuming that the fraction of time
`that a type k transaction is either 1) waiting or receiving
`processing service at Pi, or 2) receiving I/O service, is
`proportional to the corresponding service time, one can
`approximate the unknown probabilities in (3.2) as follows
`
`where the normalizing constant Cki is given by
`N
`N
`
`-
`
`/
`
`
`
`\
`
`Notice that the probabilities probk ( i , j ) are normalized
`by assuming that the transactions assigned to Pi receive
`either processing or I/O service.
`= (mki: k = 1 , * . . , K ; i = 1 ,
`Hence, given
`. . . , N ) and the approximate probabilities probk ( i, j )
`based on the service time proportions, one c a 3 derive es-
`timates from (3.2) of the mean queue length L . Each in-
`coming transactionds then routed to the processing system
`Pi such that Rki( L ) = min, 5 j 5
`{ Rkj( L ) }. In sum-
`mary, this strategy uses service times to estimate mean
`queue length and selects the processing system which pro-
`vides minimum response time to route an incoming trans-
`action. We shall call it MRT.ST strategy. The informa-
`tion needed in MRT. ST includes the routing history table
`m and a static profile on transaction characteristics { ak,
`b k , c, P k O , Pki,
`2) Residence Time Based Strategy: The residence time
`based strategy, which will be called MRT.RT, is different
`from MRT.ST only in the computation of probabilities
`probk(i, j ). With MRT.RT strategy, the probability
`prob,(i, j ) is proportional to the residence time at the
`
`1
`
`Petitioner Microsoft Corporation - Ex. 1047, p. 4
`
`

`
`YU et al.: DYNAMIC TRANSACTION ROUTING
`
`131 1
`
`, N . Combining (3.1) and (3.6), the ex-
`for i = 1 ,
`pected response time, for a class k transaction assigned to
`Pi, can be written as
`
`9
`
`(3.7)
`On the other hand each processor utilization is given by
`N
`i
`
`K
`.
`r
`r
`
`
`j # i
`
`(3.8)
`
`,'
`
`processing system PJ, instead of the service time. An it-
`erative approach based on the MVA equations [ 131 is ap-
`plied in order to derke the probability probk (i, j ) and the
`mean queue length L .
`The residence time Tk (i, j ) in PJ of a transaction of
`class k initially assigned to PI can be written as
`Tk(i, j ) = &(i, j ) ( N k ( i , j ) + 1)
`(3.4)
`where Nk (i, j ) is the mean number of tasks that a type k
`transaction assigned to P, finds in PJ , and Sk( i, j ) is its
`total service time at PJ . Values of Sk ( i , j ) can be simply
`derived from the service times expressed in (a.3) of the
`Appendix. Nk (i, j ) can be approximated by Nk( i , j ) =
`LJ - probk (i, j ) which is similar to the well known Bard-
`Shweitzer's algorithm [2], [15]. Thus, the probability
`probk (i, j ) which is proportional to the residence time
`Tk ( i , j ) is given as
`I p k i ( b k + ')PkJ]'
`+ J =
`1
`probk(i,j) = (bk + c)pkj(Lj - p r & ( i , j ) + 1 ) -
`j # i
`Pckr
`Note that the only unknown quantity in (3.8) is the prob-
`ability distribution pki of routing an arriving transaction of
`type k to processing element Pi. Since, in such a model,
`the routing probability distribution corresponds to frac-
`tions of transactions assigned to each P i , one can intro-
`duce the following approximation
`
`Uk + bkpk, + C
`
`pkJ
`
`J = I
`I + '
`
`( 3 . 5 )
`
`(Li - probk(i, i) + I ) - 1
`P cki
`where the normalizing constant Ck, is given by
`(LI - probk(i, i) + 1 )
`ck, = - ak + bkpk, -k C
`P
`I [
`l N
`+ -
`(bk + c ) p k j ( ~ j - p r o b k ( i , j ) + 1)
`p J=l
`J f l
`
`+ Pl'dk e P k j .
`
`J f
`
`l
`
`
`
`N
`
`j = 1
`
`Hence, given a system state 6 , the mean queue lengths
`are computed by iterating (3.5) and (3.2), starting with
`zero values for both queue lengths LJ and probabilities
`* . , N . The
`p r o b k ( i , j ) , f o r k = 1 , *
`, K, i , j = 1 ,
`MRT.RT strategy uses the same static and state-depen-
`dent information as the MRT.ST strategy. The iteration
`between (3.5) and (3.2) should not impose any substantial
`overhead during decision making.
`3) Utilization Bused Strategy: The Utilization Based
`Strategy routes each arriving transaction to the processing
`element that offers the minimum response time computed
`by using an approximation of server utilizations. (The
`strategy is simply called MRT.UT.) The approximation
`of server utilizations is based on the number mkl in the
`routing history table.
`Let pI denote the utilization of the processing element
`P I . Since each PI has a fixed service capacity and uses the
`processor sharing discipline, one can write
`
`L, = -
`1 - PI
`
`PI
`
`(3.6)
`
`e mkj
`
`(3.9)
`
`j = I
`In other words, the MRT.UT approximates the steady-
`state utilization pi by assuming a routing probability at the
`front-end and by setting it proportional to number of ac-
`tive transactions in the system.
`Hence, given a routing history table G = ( ml I ,
`,
`m,,), estimates of utilizations can be computed by (3.8)
`and (3.9), and then, by (3.7) estimates of the expected
`response time can be derived. MRT.UT strategy routes
`each arrivi-l transaction to the precessing system Pi such
`that Rki( L ) = min, s j 5 N {Rkj( L ) } . This strategy is
`based on state-dependent information i?z and static infor-
`mation {L, ak, bk, P ~ O , P k i , P ; k = 1 , *
`* , K ; i = 1,
`, N } .
`
`*
`
`*
`
`*
`
`a
`
`
`
`B. Strategies Based on Instantaneous Queue Length
`We now consider a class of strategies based on the in-
`stantaneous queue length at each processing systems. Two
`different approaches of making routing decisions are con-
`sidered. The first approach selects the processing system
`which minimizes the estimated response time as before,
`and the second one selects the system with minimal queue
`length. Although the overhead to maintain instantaneous
`queue length can be quite costly, in the following analysis
`we shall ignore this overhead, as the objective is to un-
`derstand, in the presence of remote calls, whether instan-
`taneous queue length can provide more robust estimate on
`the load condition.
`
`Petitioner Microsoft Corporation - Ex. 1047, p. 5
`
`

`
`1312
`
`IEEE TRANSACTIONS ON SOFTWARE ENGINEERING. VOL 14, NO. 9. SEPTEMBER 1988
`
`*
`
`1) Minimum Response Time: Let ?? = ( n , ,
`> nN)
`where n, is the instantaneous queue length of the process-
`. .
`, N . Assume that the
`ing system P I , for i = 1, 2,
`instantaneous queue IengLh Z is available to the front-
`end. We then estimate L by ??, i.e., the expected re-
`sponse time is estimated by Rr,( s ) . Thus, this strategy
`requires state information Z and static information { a r ,
`br , c, pko, pL,, p }. We refer to this strategy as MRT.IQL
`for minimum response time based on instantaneous queue
`length. Note that in the presence of remote database calls,
`the instantaneous queue length may not be representative
`of the mean queue length.
`2) Minimum Instantaneous Queue Length: The mini-
`mum instantaneous queue length strategy (denoted as
`MQL) routes each arriving transaction to the processing
`system that has the least number of tasks being executed.
`The minimum queue length strategy selects the processor
`{ n, } . If the minimum
`element PI such that n, = min, <,
`is not unique, a processing system, among the ones that
`achieve the minimum, is randomly chosen. This strategy
`is only based on the state information ?? and does not
`require any static information.
`The minimum instantaneous queue length strategy, also
`known as the send-to-shortest queue policy, is optimal for
`a system with identical exponential queues, a single Pois-
`son arriving transaction stream and where each transac-
`tion can be executed completely on any processor. For
`more complex systems with multiple classes and/or trans-
`actions with distributed processing requirement, the min-
`imum queue length strategy is not in general optimal.
`
`IV. SIMULATION STUDY A N D PERFORMANCE
`COMPARISONS
`In the following, we use simulation to investigate the
`effectiveness of the proposed dynamic routing strategies.
`Mean transaction response time is the main concern and
`is used to indicate system performance under the different
`load sharing strategies. To compare the performance of
`the strategies given in Section 111, we also consider the
`optimal static load sharing strategy under which an in-
`coming transaction is routed to a processing system ac-
`cording to a predefined routing probability. The optimal
`static load sharing strategy takes account of all static in-
`formation, i.e., { hk, ak, bk, c, pko, pki, p } , to determine
`the routing probabilities such that the mean transaction
`response time is minimized. The details of solving this
`optimization problem have been given in [21], where a
`simplex reflection method is used to find the optimal rout-
`ing probabilities.
`
`A. Description of the Simulations
`In order to evaluate dynamic load sharing strategies, we
`simulated the model for the locally distributed database
`system illustrated in Fig. 4. The simulation was imple-
`mented using RESQ [ 141. The routing decision is imple-
`mented as a separate function and is invoked upon a trans-
`action arrival at the front-end system. In addition, for all
`
`simulation runs, 95 percent confidence level estimates
`were obtained. The simulations were run until the relative
`width of the confidence interval (width divided by mid-
`point) was less than 0.1.
`In the experiments reported in the following, we as-
`sume that there are three transaction processing systems
`( N = 3 ) and three transaction classes ( K = 3 ) . Based on
`data from some IBM IMS systems [ 7 ] , [22], the average
`number of database requests per transaction is set to 15
`for all transaction classes, i.e., pro = 0.0625 for k = 1,
`2, 3. The matrices 1 /( 1 - p r o ) [ p r r ] , which indicate the
`distribution of database requests, are given in Table I to
`reflect low, middle, and high localities of database re-
`quests.
`To study the impact of processing load on database re-
`quests and request shippings, various system parameters
`are assigned with the following values. We assume that
`the processor speed is 7.5 MIPS and regard ah + br as a
`unit of service demand for all k . The mean service time
`of this unit is assumed to be 0.004 second (equivalently,
`30K instructions in pathlength). The service demand of
`shipping a request, c, is defined in terms of this unit. The
`IO access time, dk, and the probability of having IO ac-
`cess pio are assumed to be 40 ms and 0.7 for all transac-
`tion classes, respectively. Also, we denote the ratio of bk
`to ak + bk as rk, which represents the complexity of da-
`tabase requests.
`The load of a processing system could be due to the
`services of transaction application processing, database
`request processing, and communication overhead pro-
`cessing. Let p,, = S / N p , where S is given in Section 11,
`which indicates the average processing utilization per sys-
`tem due to application processing and database requests,
`and is independent of the routing decisions. By changing
`the arrival rates hk, we can study the transaction response
`times under different p,,. The load of a processing system
`PI due to processing database requests, denoted by ,oh( i ) ,
`is routing independent and is equal to Sf/p, where Sf is
`given in Section 11. By changing the arrival rates subject
`to a fixed pp, we can vary the relative value of the ph ( i )
`which represent the partition depending processing utili-
`zations.
`B. Performance Comparisons
`First, we study the effectiveness of routing strategies
`under different processing loads p,,. The incoming trans-
`actions are assumed to have middle locality in regard to
`the distribution of database requests, and rr = 0.3 for all
`transaction classes. The partition dependent load on each
`processing
`system
`is assumed
`to be equal,
`i.e.,
`p h ( I ) : p h ( 2 ) : p h ( 3 ) = 1 : 1 : 1 . Figs. 5 and 6 show the
`transaction response times versus p,, for c = 0.05 and c
`= 0.25 (1.5K and 7.5K instructions in terms of path-
`length), respectively.
`When the communication overhead of shipping remote
`requests is low, all dynamic load sharing strategies have
`better performance than the optimal static strategy. When
`the communication overhead is high, the optimal static
`
`Petitioner Microsoft Corporation - Ex. 1047, p. 6
`
`

`
`YU 1’1 (11.: DYNAMIC TRANSACTION ROUTING
`
`TABLE I
`THE DISTRIBUTION OF DATABASE REQUESTS USED I N EXPERIMENTS
`
`
`
`~
`
`1313
`
`h t a h a ~ c
`
`l o w locality
`3
`
`2
`
`1
`
`I
`
`i n i d d l c locality
`1
`
`I
`
`2
`
`9ign locality
`
`I
`
`2
`
`3
`
`3
`
`Tx t y p e I
`Tx type 2
`Tx t y p e 3
`
`0.65 0 . 2 0 0.15
`0 . 1 7 0 . 5 2 0.31
`0 . 2 1 0 . 2 1 0 . 5 8
`
`0.15 0.11 0 . 1 4
`0 . 0 7 0 . 8 2 0.11
`0 . 1 1 0 . 0 6 0 . 8 3
`
`0.90 0.10 0 . 0
`0 . 0 7 0 . 8 7 0.06
`0 . 1 1 0.03 0 . 8 6
`
`strategy becomes better than the MRT.UT, MQL, and
`MRT.IQL strategies. Over all strategies considered,
`MRT.ST and MRT.RT strategies yield the best perfor-
`mance. Neither of these two strategies needs instanta-
`neous state information. By maintain a routing history ta-
`ble in the front-end system, both strategies can be
`implemented easily.
`In Fig. 5(c), the mean communication load at each pro-
`cessing system versus the processing load is plotted under
`the strategies studied. The communication load at each
`processing system is due to the service of remote request
`shipping and can reflect the number of remote database
`requests. The optimal static strategy leads to the smallest
`communication load. This implies that most transactions
`are routed to the preferred processing system which owns
`the database partition referenced by the majority of their
`database requests. In general, except for MRT. UT, the
`communication loads under the other five strategies are
`increased either linearly or concavely. When the process-
`ing load is 0.81, the communication load introduced un-
`der the MRT.UT makes the system saturated. This seems
`to suggest that the system under MRT.UT tends to be
`unstable once the processing load is high.
`Both the MQL and MRT.IQL strategies use instanta-
`neous queue lengths to make transaction rout