IEEE TRANSACtIONS ON SOFTWARE ENOINEEEINO VOL 14 NO
`
`SEPTEMBER
`
`1988
`
`1307
`
`Dynamic Transaction Routing in Distributed Database
`Systems
`
`PHILIP
`
`YU SENIOR MEMBER IEEE SIMONETTA
`
`BALSAMO AND YANN-HANO LEE MEMBER IEEE
`
`transaction
`
`if
`
`Abstracttn this paper we investigate dynamic
`routing
`distributed database systems in which the data
`for locally
`strategies
`base is partitioned and distributed among multiple transaction pro
`transactions
`corn
`are routed by
`cessing systems and the incoming
`mnn front-end processor In this environment
`transaction
`issues
`database partition the re
`nonlocal
`database request
`referenciisg
`quest has to be shipped to the system owning the referenced partition
`strategies are studied Their perfor
`for processing Various dynamic
`mance is compared with that of the optimal static strategy
`new class
`rooting strategies which take into account rout
`of dynamic transaction
`ing history and minimize the estimated
`incoming
`response time of
`improve
`is proposed and found to provide
`substantial
`the optimal static strategy The robustness of the strategies
`ment over
`is further studied through sensitivity analysis over various transaction
`overheads and database reference distributions
`loads communication
`
`transactions
`
`database systems load balancing perfor
`index TermsDistributed
`mance analysis queaeing models transaction routing strategy
`
`INTRODUCTION
`HEN processing power is distributed over multiple
`in achiev
`computer systems toad sharing is critical
`throughput and better response time
`ing higher aggregate
`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
`in which allocation
`Other strategies
`decisions depend
`
`upon not only the static characteristics but also the current
`system state are referred to as dynamic
`both static and dy
`Numerous load sharing strategies
`namic have been studied for different
`types of distributed
`systems Queueing network analysis mathematical pro
`can be used to obtain
`gramming and other techniques
`performance estimates and then to derive optimal
`strategies for example the optimal deterministic alloca
`and optimal probabilistic as
`tion of tasks in
`On the other hand certain opti
`appmach
`have
`been
`dynamic
`malities
`in the
`also
`discovered For instance the send-to-shortest queue strat
`egy is found to be the best for the case of Poisson arrivals
`and the round-robin
`and identical exponential servers
`
`signments in
`
`static
`
`received March 17 1986 revised March 24 1987
`Manuscript
`Yu is with tBM Thomas
`Watson Research Center Yorktown
`Heights NY 10598
`Balssmo is with the Dipartimento
`
`di tnformatics University of Pisa
`
`Pisa Italy
`It
`Lee
`is with the Depanment of Computer
`eaces University of Florida Gainesville FL 32611
`IEEE Log Number 8822454
`
`and Information
`
`Sci
`
`strategy becomes optimal when the queue length at each
`server cannot be observed provided that all servers have
`the same initial
`survey on load sharing strat
`state
`egies in distributed systems can be found in
`For other
`more complex cases like heterogeneous
`servers multiple
`classes of tasks and different arrival and service time dis
`
`tributions simulations have been adopted
`performance of various strategies
`simple pmbe limit scheme
`it has been demonstrated that
`based on queue length threshold is quite effective to im
`prove performance
`
`to study
`
`the
`
`In
`
`is assumed that
`
`In these previous studies it
`incoming
`tasks can be serviced completely at any processing sys
`tasks are purely compu
`tem This implies that either all
`resources e.g database or files are
`tational or requested
`shared or replicated among all processing systems Now
`locally distributed database environmentt
`consider
`as
`shown in Fig
`The database is partitioned among the
`various processing systems and the arriving transactions
`common
`are routed to one of the processing systems by
`database re
`front-end system If
`transaction issues
`remote database partition the request
`referencing
`quest
`has to be shipped
`to the system owning the referenced
`partition for processing This is
`remote
`referred to as
`new dimension the reference
`database request Thus
`locality has to be considered in
`
`pattern or the reference
`load sharing strategies
`The
`pattern of database
`not only
`reference
`requests
`load fluctuation but also complicates mut
`causes frequent
`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
`transaction is routed The ap
`cessing system to which
`The other is
`plication process belongs to this category
`processing which is
`partition dependent
`service request
`particular database partition e.g the database
`against
`requests and can only be executed
`the processing sys
`at
`tem owning the partition To balance
`the loads among
`processing systems only the routing dependent
`process
`trans
`ing can be used as leverage In addition different
`the number of remote data
`action routing schemes affect
`base requests and thus incur different
`loads which are critical
`to performance
`
`communication
`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 .00
`
`1988 IEEE
`
`Petitioner IBM – Ex. 1047, p. 1
`
`

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

`
`YU et
`
`DYNAMIC TRANSACTION
`
`ROUTING
`
`1309
`
`application
`processing
`
`application
`processing
`
`appilcatlon
`procnsleg
`
`Input
`formatting
`
`database
`
`e.qu.s1
`to DB1
`tO access
`
`wt$t
`
`database
`
`request
`
`to D81
`access
`eIthout
`
`Fig
`
`The sequence
`
`of
`
`transaction processing
`
`I.nd
`
`otpt
`
`formatting
`
`bpplication
`
`5rOceSS
`
`local dolvbose requests
`ov communication overhead
`
`receiving service and
`
`remote database requests
`
`eabrnvdel
`fvr
`dotohose requests Cl
`
`ri
`
`Fig
`
`Model
`
`for locally distributed database
`
`system
`
`end
`
`Fig
`
`Model of transaction processing
`
`portion as
`Among this total processing load there is
`sociated with the processing of database requests We de
`note the processing load of database requests per unit time
`as follows
`
`at
`
`XkPk1bk
`
`ki
`
`Pko
`
`if
`
`trans
`
`to
`
`and Sb only depend upon the characteris
`Notice that
`tics of transactions and are independent of the transaction
`routing decisions When
`is issued it
`database request
`must be shipped from processing system P1 to
`database
`action being executed
`issues
`at P1
`request
`After the request gets processed the
`DB3 where
`result will be sent back Both
`and P3 have to perform
`and receiving services The service
`demands of
`sending
`database request or the results of
`sending and receiving
`request are referred to as communication overhead
`and
`are assumed to be exponentially distributed with mean
`The system model
`is illustrated in Fig
`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
`global or
`representation of more complex I/O subsys
`aggregate
`tem Note that this choice is mainly to simplify the model
`Extensions to capture I/O contention can be done by ex
`and multiple disk
`considering data allocations
`
`plicitly
`
`servers
`
`the transmission delay of shipping data
`In the model
`in the network is assumed negligible This
`base requests
`assumption while reasonable
`locally distributed sys
`in
`tem would not be in
`geographically distributed system
`The other simplification in the model
`the overhead
`is that
`or the delay due to data conflict and two-phase commit
`It would be otherwise necessary
`ment is not included
`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
`
`define
`
`to
`
`III 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
`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
`ate 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
`can be main
`overhead as
`incurs little
`routing history
`tained easily in the front-end system The essential
`issue
`is to estimate load conditions of the processing systems
`and then make
`good routing decision based on this es
`timate Different alternatives
`have
`been explored and
`
`Petitioner IBM – Ex. 1047, p. 3
`
`

`
`1310
`
`IEEE TRANSACTIONS
`
`ON SOFTWARE ENGINEERING VOL
`
`NO
`
`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
`is referred to the number
`of tasks being executed
`at processing system
`database
`processing
`task
`is either application
`request
`The
`overhead
`processing or communication
`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
`
`where
`
`Strategies Based on Routing History
`
`Consider
`
`set of dynamic strategies where the routing
`is based on routing history of active
`decision process
`transactions along with transaction characteristics
`These
`strategies first estimate the response time of an incoming
`the transaction is routed to the pro
`transaction given that
`Then the incoming transaction is routed
`cessing system
`to the processing system P1 which provides the minimum
`expected response time
`The routing history of active transactions is maintained
`routing history table Each
`by the front-end system in
`time
`the entry in the kth
`is routed to
`transaction tXk
`row and the ith column of the routing history table is in
`by one to reflect the new arrival and its routing
`cremented
`Furthermore when
`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
`to maintain the table in the
`negligible overhead
`in
`front-end system and requires no communications of
`from the processing sys
`stantaneous
`state information
`tems
`Next
`
`there is
`
`sidered
`
`the issue of estimating the response time is con
`The
`time of an incoming
`expected
`response
`the transient behavior of
`the
`
`upon
`transaction depends
`system and the future arrivals For efficient
`the front-end
`tion at
`steady-state analysis is applied to
`time using transaction char
`estimate the mean response
`acteristics and mean queue length at each processing sys
`tem From the derivation in the Appendix the expected
`response time for
`transaction 8k routed to
`is given as
`
`implementa
`
`L1
`
`P80
`
`bkpkl
`
`P81
`
`L1
`
`1b8
`
`cpkj pdk
`
`101
`
`11
`
`where L1 is the mean queue length of P1 and
`
`3.1
`L1
`
`2Note
`
`the number of tasks
`that
`included in the queue
`
`length
`
`receiving 10 services at system is not
`
`Lv Note that although quite
`few parameters ap
`pears in the above formulas they are derived from either
`or workload parameters ak
`and
`system parameters
`bk dk
`and P81 which are provided from the static
`transaction profile We now present
`three different ways
`based on routing history
`to estimate
`Service Time Based Strategy Consider the moment
`new transaction arrives Let mkl be the number of
`transactions assigned to the processing system
`i.e Em81 constructs
`and not yet completed
`the routing
`history table Let prob8
`denote the probability
`class
`transaction assigned
`to processing system
`at P1 Hence
`waiting for or receiving processing service
`we can express the expected queue length L1 of P1 as
`
`that
`
`is
`
`that
`
`class
`
`iI kI ink probki
`
`3.2
`
`time
`
`for
`
`that
`
`type
`
`Assuming that the fraction of
`transaction is either
`
`at
`
`or
`
`waiting or receiving
`receiving I/O service is
`processing service
`time one can
`to the corresponding service
`proportional
`in 3.2 as follows
`approximate the unknown probabilities
`
`probsij
`
`b8 cpe
`
`10Ck
`
`prob8i
`
`h8p81
`
`3.3
`
`where the normalizing constant C8 is given by
`c8j a8 bkpk
`
`P81
`
`jI
`jNi
`
`j-l
`11
`
`PkJ
`
`Notice that
`
`are normalized
`
`to
`
`receive
`
`the probabilities probk
`the transactions assigned
`by assuming that
`either processing or I/O service
`mk
`Hence given
`and the approximate probabilities prob8i
`based on the service time proportions one can derive es
`timates from 3.2 of the mean queue length
`Each in
`coming transaction is then routed to the processing system
`P1 such that R91L min115 R81L 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
`static profile on transaction characteristics ak
`ii and
`Pko PkI
`The residence time
`Residence Time Based Strategy
`based strategy which will be called MRT.RT is different
`from MRT.ST only in the computation of probabilities
`With MRT.RT
`prob8i
`the probability
`strategy
`prob8i
`to the residence
`time at
`
`bk
`
`10
`
`is proportional
`
`the
`
`Petitioner IBM – Ex. 1047, p. 4
`
`

`
`YU rg a/
`
`DYNAMIC TRANSACTION
`
`ROIl
`
`rING
`
`1311
`
`in
`
`of
`
`transaction of
`P1
`can be written as
`
`instead of the service time An it
`processing system
`based on the MVA equations
`is ap
`erative approach
`plied in order to derive the probability probk
`and the
`mean queue length
`time Tki
`The residence
`to
`initially assigned
`
`class
`
`Tij SkijNkij
`
`3.4
`
`type
`
`is its
`
`where Nki
`is the mean number of tasks that
`finds in P1 and Sk
`transaction assigned
`to
`can be simply
`total service time at P3 Values of Sk
`in a.3 of the
`derived from the service
`times expressed
`can be approximated by Nki
`Appendix Nki
`L1 probtij which is similar to the well known Bard
`Thus the probability
`Shweitzers
`algorithm
`which is proportional
`to the residence
`time
`is given as
`
`probk
`
`Ti
`
`probkij
`
`bk
`
`cpkJ
`
`probkij
`
`prohki
`
`Lak
`
`bkpk CPkf
`
`L1
`
`probki
`
`3.5
`
`Combining 3.1 and 3.6 the ex
`for
`pected response time for
`transaction assigned to
`can be written as
`
`class
`
`Rk
`
`at
`
`Pki
`
`1I
`ji
`
`i-i
`iNi
`
`p1
`
`cpkj
`
`dk
`
`3.7
`On the other hand each processor utilization is given by
`
`XkI
`kI /.LPto
`
`PkJ at
`
`bkpk
`
`Pt
`
`iI
`
`Pklbk
`
`cPkj
`
`3.8
`
`Note that
`
`type
`
`the only unknown quantity in 3.8 is the prob
`ability distribution ji of routing an arriving transaction of
`Since in such model
`to processing element
`corresponds to frac
`to each
`one can intro
`
`distribution
`the routing probability
`tions of transactions assigned
`duce the following approximation
`
`where the normalizing constant Ck is given by
`
`mk
`
`Pki
`
`3.9
`
`--
`
`PkJLi
`
`probki
`
`jNi
`
`cpkfLj probij
`
`jkj-I
`ii
`
`JO
`Pt
`
`Pkj
`
`zero values
`
`the mean queue lengths
`Hence given
`system state iii
`by iterating 3.5 and 3.2 starting with
`are computed
`for both queue lengths L1 and probabilities
`probij fork
`The
`jj
`MRT.RT
`strategy uses the same static and state-depen
`information as the MRT.ST strategy The iteration
`dent
`between 3.5 and 3.2 should not
`impose any substantial
`overhead during decision making
`Utilization Based Strategy
`routes each arriving transaction to the processing
`Strategy
`element that offers the minimum response time computed
`by using an approximation of server utilizations The
`strategy is simply called MRT.UT The approximation
`is based on the number
`of server utilizations
`fl1 in the
`
`The Utilization Based
`
`routing history table
`Let p1 denote the utilization of the processing element
`Since each
`and uses the
`has
`fixed service capacity
`processor sharing discipline one can write
`
`In other words the MRT.UT
`approximates the steady-
`by assuming
`routing probability at the
`state utilization
`to number of ac
`front-end and by setting it proportional
`tive transactions in the system
`m11
`Hence given
`routing history table
`KN estimates of utilizations can be computed by 3.8
`and 3.9 and then by 3.7 estimates of the expected
`time can be derived MRT.UT
`strategy routes
`response
`transaction to the processing system P1 such
`each arrival
`min1.jv Rb 1. This strategy is
`that
`information
`based on state-dependent
`at bk Pto Pu
`mation
`
`and static infor
`
`Strategies Based on Instantaneous Queue Length
`
`We now consider
`class of strategies based on the in
`systems Two
`queue length at each processing
`stantaneous
`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
`to maintain instantaneous
`length Although the overhead
`queue length can be quite costly in the following analysis
`ignore this overhead as the objective is to un
`we shall
`derstand in the presence of remote calls whether instan
`taneous queue length can provide more robust estimate on
`the load condition
`
`Petitioner IBM – Ex. 1047, p. 5
`
`

`
`IEEE TRANSACTIONS
`
`ON SOFTWARE ENGINEERING \OL
`
`14 NO
`
`SEPTEMBER
`
`1988
`
`1312
`
`where
`
`n1
`Minimum Response Time Let
`is the instantaneous
`queue length of the process
`Assume that
`the
`
`for
`
`ing system
`
`instantaneous
`queue length 7f
`is available to the front-
`end We then estimate
`i.e the expected
`re
`by
`Thus this strategy
`sponse time is estimated by RkI
`and static
`requires state information
`information
`Pko p8 p. We refer to this strategy as MRT.IQL
`bk
`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
`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
`n3 If the minimum
`mm1 .j
`element
`such that
`processing system among the ones that
`is not unique
`achieve the minimum is randomly chosen This strategy
`and does not
`is only based on the state information
`require any static information
`The minimum instantaneous
`queue length strategy also
`known as the send-to-shortest queue policy is optimal
`for
`single Pois
`system with identical exponential queues
`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
`the min
`actions with distributed processing requirement
`imum queue length strategy is not
`in general optimal
`
`IV Sisiuro STUDY
`AND PERFORMANCE
`COMPARISONS
`
`confidence
`simulation runs 95 percent
`level estimates
`were obtained The simulations were run until
`interval width divided by mid
`width of
`the confidence
`
`the relative
`
`point was less than
`In the experiments reported in the following we as
`sume that
`there are three transaction processing systems
`and three transaction classes
`Based on
`data from some IBM IMS systems
`the average
`number of database requests
`transaction is set
`to 15
`per
`transaction classes i.e P80
`0.0625 fork
`for all
`Pro pi1 which indicate the
`The matrices
`distribution of database requests are given in Table Ito
`low middle and high localities of database
`re
`reflect
`
`quests
`T0 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 a8
`as
`demand
`The mean service time
`unit of service
`for all
`is assumed to be 0.004 second equivalently
`of this unit
`30K instructions in pathlength The service
`demand of
`is defined in terms of this unit The
`shipping
`request
`10 access time d8 and the probability of having 10 ac
`are assumed to be 40 ms and 0.7 for all
`transac
`cess
`tion classes respectively Also we denote the ratio of b8
`the complexity of da
`bk as rk which represents
`to a8
`tabase requests
`The load of
`be due to the
`processing system could
`services of transaction application processing
`database
`and communication
`overhead pro
`request processing
`S/Np where
`cessing Let
`is given in Section II
`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
`rates X8 we can study the transaction response
`the arrival
`times under different ps The load of
`processing system
`due to processing database requests denoted by p5i
`and is equal
`to Sr/.8 where
`is routing independent
`given in Section II By changing
`the arrival
`rates subject
`fixed p8 we can vary the relative value of the phi
`to
`which represent
`the partition depending
`processing utili
`zations
`
`is
`
`Performance Comparisons
`
`First we study the effectiveness
`of
`routing strategies
`The incoming trans
`under different processing loads
`are assumed to have middle locality in regard to
`actions
`the distribution of database requests and r8
`0.3 for all
`transaction classes The partition dependent
`load on each
`i.e
`assumed
`be
`processing
`system is
`to
`equal
`p5lp52p83
`111 Figs
`show the
`times versus p1
`transaction response
`0.25 1.5K and 7.5K instructions
`length respectively
`When the communication overhead of shipping remote
`is low all dynamic load sharing strategies have
`requests
`better performance than the optimal static strategy When
`the communication overhead
`is high the optimal
`static
`
`for
`
`0.05 and
`in terms of path-
`
`and
`
`In the following we use simulation to investigate the
`of the proposed dynamic routing strategies
`effectiveness
`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
`III we also consider the
`given in Section
`the strategies
`load sharing strategy under which an in
`optimal
`processing system ac
`routed to
`coming transaction is
`predefined routing probability The optimal
`cording to
`in
`static load sharing strategy takes account of all static
`formation i.e X8 a8 b8
`Pko P81 JL
`to determine
`the mean transaction
`such that
`the routing probabilities
`time is minimized The details of solving this
`where
`problem have been given
`optimization
`in
`simplex reflection method is used to find the optimal
`
`static
`
`response
`
`rout
`
`ing probabilities
`
`Description of the Simulations
`
`In order to evaluate dynamic load sharing strategies we
`simulated the model
`for the locally distributed database
`The simulation was imple
`system illustrated in Fig
`mented using RESQ
`The routing decision is imple
`mented as
`separate function and is invoked upon
`trans
`action arrival at the front-end system In addition for all
`
`Petitioner IBM – Ex. 1047, p. 6
`
`

`
`YU ei
`
`fli
`
`DYNAMIC TRANSACTION
`
`ROrTING
`
`1313
`
`TABLE
`THE DI5TRIBU ION OF DA AUASE REQUEsTs UsED IN EXPFRIMFNTS
`
`In
`
`ty
`
`idd ft
`
`ly
`
`ih ln
`
`1y
`
`t3h.e
`
`0.75 0.1
`0.20
`0.65
`0.7 0.50
`0.07 0.82
`0.31
`ic t4peD0l
`0.21 0.58J 0.11 0.06
`
`0.15
`
`type
`
`114
`
`0.1
`
`0.83
`
`10 0.0
`
`0.90
`0.07 o.8i
`0.11
`
`0.03
`
`0.06
`0.86
`
`implemented easily
`
`than the MRT.UT MQL and
`strategy becomes better
`MRT.EQL
`strategies Over all
`strategies considered
`MRT.ST and MRT.RT
`strategies yield the best perfor
`mance Neither of these two strategies needs instanta
`routing history ta
`neous state information By maintain
`strategies can be
`system both
`front-end
`ble in the
`In Fig 5c the mean communication load at each pro
`cessing system versus the processing load is plotted under
`The communication
`load at each
`studied
`the strategies
`processing system is due to the service of remote request
`the number of remote database
`shipping and can reflect
`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
`for MRT.UT the
`database
`except
`requests fri general
`loads under the other five strategies are
`communication
`increased either linearly or concavely When the process
`ing load is 0.81 the communication load introduced un
`the MRT.UT makes the system saturated This seems
`der
`the system under MRT.UT
`tends to be
`to suggest
`unstable once the processing load is high
`Both the MQL and MRT IQL strategies use instanta
`neous queue lengths to make
`transaction routing deci
`sions The instantaneous
`queue length may fluctuate fre
`quently due to the issuing of remote database requests As
`the decision processes using MQL and
`consequence
`MRT.IQL observe more instances where the system has
`load than under the other strategies Thus de
`unbalanced
`cision making tends to balance the loads regardless of in
`remote database requests When the
`troducing additional
`is high these additional
`communication overhead
`remote
`lead to an increase of system utilization
`time Both the MQL and
`and
`response
`transaction
`MRT.IQL strategies end up with inferior performance
`compared
`to the optimal static strategy
`With the same setups as the above experiments we in
`the performance of load sharing strategies under
`unbalanced pbi Figs 6a and 6b show the transac
`strategies when
`time
`under different
`response
`p5lp2pb3 0.511 In general
`the results
`as shown in Figs 5a and 5b
`have the same tendency
`at P1
`Since the underlying load due to database requests
`i.e p0
`is small all strategies tend to route more
`transactions to P1 and thus introduce more remote ship
`than under the case with balanced P8i The in
`pings
`crease in response time is more vivid when
`0.25
`
`that
`
`database requests
`
`vestigate
`
`tion
`
`Sensitivity Analyses
`
`it has been shown that both MRT.ST
`and
`In Figs
`and MRT.RT are superior to other load sharing strategies
`We shall proceed further
`to investigate the robustness of
`on var
`these two strategies through sensitivity analyses
`ious system and workload parameters Specifically we
`overhead distribution
`of database
`vary communication
`requests degree of balancing on partition dependent
`and service demand of database requests
`The rela
`Sensitivity to Communication Overhead
`transaction response time and commu
`tionship between
`is illustrated in Fig
`nication overhead
`where simula
`tion results for various communication
`overheads
`presented for MRT.ST MRT.RT and the optimal
`static
`strategies Two groups of curves are shown one is for
`0.71 The response
`0.57 the other
`is for
`times
`increase more than linearly in the second group which is
`under higher processing load Fig
`shows
`the increase
`in mean communication
`load at each processing system
`when the communication overhead of shipping database
`requests and results becomes
`large
`the mean communication
`It can be observed
`that
`
`load
`
`are
`
`under
`static strategy is less than that under
`the optimal
`MRT.ST or MRT.RT The larger shipping loads under
`MRT.ST and MRT.RT indicate that more transactions are
`
`load
`
`the
`
`to
`
`nonpreferred processing system to eliminate
`routed to
`in com
`temporary load unbalance Despite the increase
`munication load the dynamic routing strategy balances
`the loads among processing systems eliminates possible
`bottlenecks and thus reduces the response time The other
`the number of non-
`interesting observation in Fig is that
`preferred routings under MRT.RT is greater than that un
`der MRT.ST In contrast
`to MRT.ST the MRT.RTs ap
`Thus
`queue