Conventional, query-independent routing algorithms always
route a set of queries in the same order as they arrive at the system. In other words,
they process the input queue according to a first-come-first-served policy. A typical
example is the FCFFS (???First-Come-First-Free-Server???) strategy that assumes
a multiprogramming level of one and routes each query to the first free server in a
round-robin fashion.
240 R?¶hm
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
Carey, Livny, and Lu (1985) and Carey and Lu (1986) addressed the problem of
dynamically assigning queries to sites in a distributed (shared-nothing) database
system with full replication. They presented two query-dependent algorithms that
are based on a classification of queries according to their I/O and CPU demands:
BNQRD (???Balance the Number of Queries by Resource Demands???) routes queries
to the site with the smallest number of queries of the same type (i.e., I/O-bound or
CPU-bound), while LERT (???Least Estimated Response Time???) uses the I/O and
CPU demand information to route a query to the site with the least estimated response
time. In a simulation study, BNQRD improved waiting times of queries by
around 10% compared to a simple balancing strategy (BNQ??”???Balance the Number
of Queries???), while the LERT algorithm performed only a bit better than BNQRD
in most cases.
Pages:
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453