ACM SIGMOD Anthology TODS dblp.uni-trier.de

On Robust Transaction Routing and Load Sharing.

Philip S. Yu, Avraham Leff, Yann-Hang Lee: On Robust Transaction Routing and Load Sharing. ACM Trans. Database Syst. 16(3): 476-512(1991)
@article{DBLP:journals/tods/YuLL91,
  author    = {Philip S. Yu and
               Avraham Leff and
               Yann-Hang Lee},
  title     = {On Robust Transaction Routing and Load Sharing},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {3},
  year      = {1991},
  pages     = {476-512},
  ee        = {http://doi.acm.org/10.1145/111197.111210, db/journals/tods/YuLL91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we examine the issue of robust transaction routing in a locally distributed database environment where transaction characteristics such as reference locality imply that certain processing systems can be identified as being more suitable than others for a given transaction class. A response time based routing strategy can strike a balance between indiscriminate sharing of the load and routing based only on transaction affinity. Since response time estimates depend on workload and system parameters that may not be readily available, it is important to examine the robustness of routing decisions to information accuracy. We find that a strategy which strictly tries to minimize the response time of incoming transactions is sensitive to the accuracy of certain parameter values. On the other hand, naive strategies, that simply ignore the parameters in making routing decisions, have even worse performance. Three alternative strategies are therefore examined: threshold, incriminatory, and adaptive. Instead of just optimizing an incoming transaction's response time, the first two strategies pursue a strategy that is somewhat more oriented towards global optimization. This is achieved by being more restrictive on either the condition or the candidate for balancing the load. The third strategy, while trying to minimize the response time of individual incoming transactions, employes a feedback process to adaptively adjust future response time estimates. It monitors the discrepancy between the actual and estimated response times and introduces a correction factor based on regression analysis. All three strategies are shown to be robust with respect to the accuracy of workload and system parameters used in the response time estimation.

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2430 KB]

References

[1]
Ashok K. Agrawala, Satish K. Tripathi, Glenn Ricart: Adaptive Routing Using a Virtual Waiting Time Technique. IEEE Trans. Software Eng. 8(1): 76-81(1982) BibTeX
[2]
Yonathan Bard: A Model of Shared DASD and Multipathing. Commun. ACM 23(10): 564-572(1980) BibTeX
[3]
Joel F. Bartlett: A NonStop Kernel. SOSP 1981: 22-19 BibTeX
[4]
Andrea J. Borr: Transaction Monitoring in ENCOMPASS: Reliable Distributed Transaction Processing. VLDB 1981: 155-165 BibTeX
[5]
Michael J. Carey, Miron Livny, Hongjun Lu: Dynamic Task Allocation in a Distributed Database System. ICDCS 1985: 282-291 BibTeX
[6]
Michael J. Carey, Hongjun Lu: Load Balancing in a Locally Distributed Database System. SIGMOD Conference 1986: 108-119 BibTeX
[7]
...
[8]
...
[9]
Douglas W. Cornell, Daniel M. Dias, Philip S. Yu: Analysis of Multi-System Function Request Shipping. ICDE 1986: 282-291 BibTeX
[10]
...
[11]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 BibTeX
[12]
Derek L. Eager, Edward D. Lazowska, John Zahorjan: A Comparison of Receiver-Initiated and Sender-Initiated Adaptive Load Sharing. Perform. Eval. 6(1): 53-68(1986) BibTeX
[13]
Derek L. Eager, Edward D. Lazowska, John Zahorjan: Adaptive Load Sharing in Homogeneous Distributed Systems. IEEE Trans. Software Eng. 12(5): 662-675(1986) BibTeX
[14]
...
[15]
...
[16]
Stephen S. Lavenberg: A Perspective on Queueing Models of Computer Performance. Perform. Eval. 10(1): 53-76(1989) BibTeX
[17]
...
[18]
...
[19]
Lionel M. Ni, Kai Hwang: Optimal Load Balancing in a Multiple Processor System with Many Job Classes. IEEE Trans. Software Eng. 11(5): 491-496(1985) BibTeX
[20]
Spiridon Pulidas, Donald F. Towsley, John A. Stankovic: Imbedding Gradient Estimators in Load Balancing Algorithms. ICDCS 1988: 482-490 BibTeX
[21]
Martin Reiser, Stephen S. Lavenberg: Mean-Value Analysis of Closed Multichain Queuing Networks. J. ACM 27(2): 313-322(1980) BibTeX
[22]
...
[23]
Michael Stonebraker: The Case for Shared Nothing. IEEE Database Eng. Bull. 9(1): 4-9(1986) BibTeX
[24]
...
[25]
Asser N. Tantawi, Donald F. Towsley: Optimal Static Load Balancing in Distributed Computer Systems. J. ACM 32(2): 445-465(1985) BibTeX
[26]
Yung-Terng Wang, Robert J. T. Morris: Load Sharing in Distributed Systems. IEEE Trans. Computers 34(3): 204-217(1985) BibTeX
[27]
...
[28]
...
[29]
Philip S. Yu, Simonetta Balsamo, Yann-Hang Lee: Dynamic Transaction Routing in Distributed Database Systems. IEEE Trans. Software Eng. 14(9): 1307-1318(1988) BibTeX
[30]
Philip S. Yu, Douglas W. Cornell, Daniel M. Dias, Alexander Thomasian: Performance Comparison of IO Shipping and Database Call Shipping: Schemes in Multisystem Partitioned Databases. Perform. Eval. 10(1): 15-33(1989) BibTeX
[31]
...
[32]
Songnian Zhou: A Trace-Driven Simulation Study of Dynamic Load Balancing. IEEE Trans. Software Eng. 14(9): 1327-1341(1988) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:11 2008