Queuing delay limiter

#This invention relates to methods and devices for dealing with slow processing times in systems with input queues.

#Input queues are used to buffer transactions that one or more transaction processors cannot immediately service. The initiator of the transaction may expect a response from the processor within a maximum amount of time called a timeout period. If the processing rate of the processor(s) is at times too slow to keep up with the flow of transactions, a response to a transaction may be sent to the initiator after the timeout period. After the timeout period, the initiator may no longer expect a response from the transaction request and receipt of a response may cause the system to crash. Even when the initiator has prepared for the possibility of such delayed responses, these delayed responses can lead to degraded system performance.

#In an embodiment of the invention, a method for reducing the incidence of stale transactions in a queuing system is provided. Deviations from a maximum expected processing time (“MEPT”) for processing a transaction are summed and compared to a threshold time. When the sum of deviations exceeds the threshold time, a response such as discarding transaction request in an input queue is initiated.

#The foregoing features of the invention will be more readily understood by reference to the following detailed description, taken with reference to the accompanying drawings, in which:

#FIG. 1 is a block diagram for a queuing system according to an embodiment of the invention;

#FIG. 2 is a flow chart illustrating a method of identifying stale transactions in a queueing system according to an embodiment of the invention; and

#An embodiment of the present invention facilitates dealing with situations where transaction processors in a system with an input queue cannot keep up with the flow of incoming transactions. Deviations from a maximum expected processing time (“MEPT”) for processing a transaction are summed and compared to a threshold time. When the sum of deviations exceeds the threshold time, remedial procedures begin. Such remedial procedures may include discarding transactions in the input queue. In this way, the receipt by an initiator of a delayed response to a requested transaction may be eliminated or reduced in frequency.

#FIG. 1 shows a queuing system 10 according to an embodiment of the invention. A number of initiators 20 send transaction requests to one or more transaction processors 60. The transactions may be communicated to the processors over a network 30 that contains intervening queues 35. The transactions enter an input queue 40 that can buffer a number of transactions 50. When a processor 60 becomes idle, the processor services the transaction at the head of the queue 40. A transaction response 70 may be returned to the initiator 20 in an output stream 80.

#In a first embodiment of the invention, a method is provided for identifying stale transactions in the queues, 35 and 40, of the system 10. As shown in FIG. 2, the method begins 100 with a transaction loaded on an input queue 40. The deviation, both positive and negative, of the processing time 110 from the MEPT for each transaction is calculated and summed. In this description and in any appended claims, “processing time” will mean the time measured from the start of processing of the transaction by any processor to the time processing is finished and the response to the initiator, if any, is placed on an output stream 80. When the sum of the deviations exceeds a threshold time 130, the system generates 140 a signal. In other embodiments of the invention, other methods of determining that the processing time for transactions has been delayed above a threshold may used. For example, without limitation, the processing time for each transaction may be summed and the result then compared with a threshold equal to the product of the MEPT and the number of transactions processed. Alternatively, the processing time for each transaction may be divided by the MEPT and the quotients may then be summed. The sum may then be compared to the number of transactions processed. All such methods are within the scope of the present invention.