Method and apparatus for high-speed generation of a priority metric for queues

• US 20030055938A1
• Filed: 08/13/2002
• Published: 03/20/2003
• Est. Priority Date: 02/28/2000
• Status: Abandoned Application

• Current Assignee: Teracross Limited
• Original Assignee: Teracross Limited
• Inventors: Barzilai, Ehud
• Application Number:
  US10/203,719
• Publication Number:
  US 20030055938A1
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/562 Attaching a time tag to queues
• CPC Class Codes: H04L 47/566 Deadline varies as a function of time spent in the queue

Abstract

A method and apparatus for establishing queue priorities for selecting one queue from at least two queues each containing items to be serviced, wherein a metric is determined for each queue by estimating the aggregate waiting time associated with all of the items in the respective queue, and the estimated aggregate waiting time is used to form a priority metric.

Claims

1. A method for establishing queue priorities for selecting one queue from at least two queues each containing items to be serviced, said method comprising the steps of:

(a) determining for each queue a metric by estimating the aggregate waiting time associated with all of the items in the respective queue, and

(b) using the estimated aggregate waiting time to form a priority metric.

2. The method according to claim 1, wherein each queue is dedicated for a respective Quality of Service (QoS) and step (b) includes:

i) combining the estimated aggregate waiting time with a parameter determined by the QoS for which the queue is dedicated.

3. The method according to claim 1 or 2, wherein at least one of said queues is served by a multi-item server adapted to service, concurrently or serially, a batch containing more than one item and the priority metric is calculated only at the beginning or end of each batch.

4. The method according to any one of the preceding claims, wherein an inter-arrival time Δ

t of items at each of said queues is assumed to be locally stationary in order to facilitate the calculation of the aggregate waiting time.

5. The method according to claim 4, wherein the aggregate waiting time is calculated as:

6. The method according to claim 5, further including the steps of assuming that n>

>

k>

>

1 and calculating;

7. The method according to any one the preceding claims, further including:

applying a companding function to the value obtained as queue priority, in order to limit the dynamic range of the priority values generated.

8. Use of the method according to any one the preceding claims for establishing queue priorities in a communication network switch.

9. An apparatus for establishing queue priorities for selecting one queue from at least two queues each containing items to be serviced, said apparatus comprising:

a computer for determining for each queue an estimated aggregate waiting time (EAWT) associated with all of the items in the respective queue, and using the estimated aggregate waiting time to form a priority metric.

10. The apparatus according to claim 9, wherein each queue is dedicated for a respective Quality of Service (QoS) and the computer is adapted to combine the estimated aggregate waiting time with a parameter determined by the QoS for which the queue is dedicated.

11. The apparatus according to claim 9 or 10, wherein at least one of said queues is served by a multi-item server adapted to service, concurrently or serially, a batch containing more than one item and the priority metric is calculated only at the beginning or end of each batch.

12. The apparatus according to any one of claims 9 to 11, wherein an inter-arrival time Δ

t of items at each of said queues is assumed to be locally stationary.

13. The apparatus according to claim 12, wherein the computer calculates the aggregate waiting time as:

14. The apparatus according to claim 13, where it is assumed that n>

>

k>

>

1 and the computer is adapted to calculate;

15. The apparatus according to any one claims 9 to 14, wherein the computer is further adapted to apply a companding function to the value obtained to limit a dynamic range of the priority values generated.

16. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for establishing a queue priority for selecting one queue from at least two queues each containing items to be serviced, said method comprising the steps of:

(a) determining for each queue an estimated aggregate waiting time (EAWT) associated with all of the items in the respective queue, and

(b) using the estimated aggregate waiting time to form a priority metric.

17. A computer program product comprising a computer useable medium having computer readable program code embodied therein for establishing a queue priority for selecting one queue from at least two queues each containing items to be serviced, said computer program product comprising:

computer readable program code for causing the computer to determine for each queue an estimated aggregate waiting time (EAWT) associated with all of the items in the respective queue, and

computer readable program code for causing the computer to use the estimated aggregate waiting time to form a priority metric.