US5475813A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Routing transactions in the presence of failing servers
Assignee: International Business Machines Corp
•
Filing: 1994-07-18
•
Granted: 1995-12-12
•
Expires: 2014-07-18
Abstract
Abstract Failures are detected in servers of a transaction processing system, and transactions are routed to less failure prone servers in the system. Servers in the transaction processing system which are faulty for some transaction classes but good for others are detected, and such servers are used in a judicious manner to maximize the throughput and minimize the response time of the system. Error prone servers are occasionally probed to determine if they have improved in terms of their error characteristics. The mechanism implemented consists of three elements. The first is the selection of a routing algorithm based on the state of the transaction processing system. Second, transactions are used to probe systems considered too faulty for use in order to determine if they have improved in terms of their failure characteristics. Finally, soft ABENDs are detected. The algorithm for transaction routing to detect and control the problem of failing servers in a transaction processing system consists of two parts: The first part routes transactions to servers based on the length of the server queues, the response time of the transactions (i.e., queuing delay plus processing delay), and the perceived failure rate. The second part of the algorithm ensures that error prone servers are not completely ignored. Occasional transactions are used to probe servers in order to determine if they have improved in terms of their error characteristics.
Inventors
- 👤 Randall A. Cieslak
- 👤 Donald F. Ferguson
- 👤 Jakka Sairamesh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 18:06
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/142
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
148 words
A method for routing transactions in a transaction processing system in which servers can fail comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class waiting at the server; routing transactions to servers that have failure rates below a predetermined threshold; and if multiple servers satisfy the predetermined threshold, then choosing a server using statistical data about transaction arrival rates, response times, failure probabilities, and queue lengths of transactions per class at the servers.
Claim 2
Independent Claim
148 words
A method for routing transactions in a transaction processing system in which servers can fail comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class waiting at the server; routing transactions to servers that have failure rates below a predetermined threshold; and if multiple servers satisfy the predetermined threshold, then choosing a server using statistical data about transaction arrival rates, response times, failure probabilities, and queue lengths of transactions per class at the servers.
Claim 3
Independent Claim
138 words
A method for routing transactions in a transaction processing system in which servers can fail comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class waiting at the server; routing transactions to servers that have failure rates below a predetermined threshold; and detecting a decrease in a failure rate of servers that are ignored in the routing step because they were considered too faulty.
Claim 4
Independent Claim
138 words
A method for routing transactions in a transaction processing system in which servers can fail comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class waiting at the server; routing transactions to servers that have failure rates below a predetermined threshold; and detecting a decrease in a failure rate of servers that are ignored in the routing step because they were considered too faulty.
Claim 5
Dependent Claim
44 words
The method recited in claim 2 further comprising the step of detecting the presence of soft abnormal endings of transactions at each server, a soft abnormal ending occurring when a server returns a code that indicates success for a transaction that has actually failed.
Claim 6
Dependent Claim
39 words
The method recited in claim 3 wherein said step of detecting the presence of soft abnormal endings of transactions is performed by the step of comparing response times of transactions to statistical data of response times for successful transactions.
Claim 7
Dependent Claim
17 words
The method recited in claim 4 wherein the statistical data is a histogram of observed response times.
Claim 8
Dependent Claim
56 words
The method recited in claim 4 further comprising the steps of: setting a threshold p and defining v to be p times the number of observations used to make the histogram; and identifying a transaction with a response time that falls into a histogram bin that has less than v elements as a soft abnormal ending.
Claim 9
Independent Claim
127 words
A method for routing transactions in a transaction processing system in which servers can fail comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class wailing at the server; routing transactions to servers that have failure rates below a predetermined threshold; and monitoring H(i,j), the number of class i transactions at server j.
Claim 10
Independent Claim
127 words
A method for routing transactions in a transaction processing system in which servers can fail comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class wailing at the server; routing transactions to servers that have failure rates below a predetermined threshold; and monitoring H(i,j), the number of class i transactions at server j.
Claim 11
Dependent Claim
181 words
Method for routing transactions in a transaction processing system in which servers can fail and wherein transactions of a certain class are not currently being routed to one or more servers because of a high failure rate, comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class waiting at the server; routing transactions to servers that have failure rates below a predetermined threshold; sending a limited number of transactions to said one or more servers; and determining if a failure rate of said one or more servers has decreased based on a return of a code indicating a success or failure of transactions sent to the systems.
Claim 12
Dependent Claim
181 words
Method for routing transactions in a transaction processing system in which servers can fail and wherein transactions of a certain class are not currently being routed to one or more servers because of a high failure rate, comprising the steps of: estimating a probability of a transaction failure for each server and each transaction class; estimating an arrival rate of each transaction class at each router and at each server; determining a queue length of transactions of each class waiting at each server; determining failure probabilities for each server in the transaction processing system based on the estimates of a probability of a transaction failure and the arrival rate for each transaction class and a number of transactions of each class waiting at the server; routing transactions to servers that have failure rates below a predetermined threshold; sending a limited number of transactions to said one or more servers; and determining if a failure rate of said one or more servers has decreased based on a return of a code indicating a success or failure of transactions sent to the systems.
Claim 13
Dependent Claim
90 words
The method recited in claim 8 where in the step of determining if a failure rate has decreased comprises the steps of: waiting for a specified number of transaction completions to occur; recomputing a transaction failure rate for said one or more servers assuming that a transaction has completed successfully, even though no transaction has actually been routed to said one or more servers; and as an estimated failure probability decreases, sending a transaction to said one or more servers to test of said one or more servers has improved.
References Cited (Backward Citations)
US4616359A
Cited
US4881261A
Cited
US5031089A
Cited
US5095421A
Cited
US5185780A
Cited
US5291550A
Cited
US5317562A
Cited
US5224099A
Cited
US5313454A
Cited
US5267235A
Cited
US5335224A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-12-11 | 1999-06-12 | 1999-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-12-11 | 2003-06-12 | 2003-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-12-11 | 2007-06-12 | 2007-12-12 | $7700.00 | Window Closed / Lapsed |