Method and apparatus for guaranteeing data transfer rates and delays in data packet networks using logarithmic calendar queues

• US 6,396,843 B1
• Filed: 10/30/1998
• Issued: 05/28/2002
• Est. Priority Date: 10/30/1998
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Agere Systems Guardian Corp. (Broadcom, Inc.)
• Inventors: Chiussi, Fabio Massimo, Kneuer, Joseph George, Francini, Andrea
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/182,884
• Time in Patent Office: 1,306 Days
• Field of Search: 370/395,389,412,414-418,422,468
• US Class Current: 370/418
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9031 Wraparound memory, e.g. overrun or underrun detection

Abstract

The total implementation complexity of packet schedulers which aim at approximating the Generalized Processor Sharing (GPS) policy is the combination of the complexity of their system-potential function and the complexity involved in sorting the timestamps in order to select the packet with minimum timestamp for transmission. Given that several scheduling algorithms which use a system-potential function of O(1) complexity have been introduced (among them, the Minimum-Delay Self-Clocked Fair Queuing (MD-SCFQ) algorithm achieves optimal delay and excellent fairness properties), the major contribution to the total complexity comes from the task of sorting the timestamps every time a packet is transmitted or received, which is common to all GPS-related schedulers. A method and an apparatus, called the Logarithmic Calendar Queue (LCQ), is disclosed which can achieve a dramatic reduction of the implementation complexity of sorting the timestamps in a GPS-related scheduler, at the cost of very small and controllable degradation of the guaranteed delay bounds. This is achieved by using a plurality of calendar subqueues, each subqueue associated with different granularity for the representation of timestamp values.

Claims

1. A method of servicing, at a predetermined service rate, a plurality of queues containing data packets, each of said queues being associated with respective connections, said connections traversing an associated communication switch, each of said connections being allocated a respective data transfer rate, said method comprising the steps of:

responsive to receiving a plurality of data packets via a plurality of data links identifying for each received data packet the respective one of said connections and identifying the associated one of said queues;

storing each of the received data packets in one of said plurality of queues;

associating a timestamp with each connection whose associated queue has at least one data packet waiting therein, in which said connection is identified as a backlogged connection, and generating a timestamp associated with each connection each time a new data packet reaches the head of the associated queue;

storing in memory the timestamps associated with respective ones of the backlogged connections;

sorting the timestamps using a plurality of calendar subqueues, each of said calendar subqueues being associated with a respective specified granularity and comprising a plurality of bins, each of said bins being associated with an interval of values of timestamps according to the respective granularity of the calendar subqueue, and each of said bins comprising a queue of connections whose respective timestamps have values within the interval associated with the bin;

selecting for each backlogged connection one of the said calendar subqueues and one of the bins in the selected calendar subqueue according to the value of the associated timestamp each time a new data packet reaches the head of the associated queue of the corresponding connection;

appending said backlogged connection to the queue of connections in the selected bin in the selected calendar subqueue;

generating a value for the system potential according to a predetermined function, and identifying the bin in each calendar subqueue associated with the value of the system potential;

identifying, for each of the calendar subqueues, the first non-empty bin whose minimum associated timestamp value is not smaller than the minimum timestamp value associated with the bin associated with the value of system potential in said calendar subqueue;

determining for each of the identified non-empty bins the connection at the head of the corresponding queue of connections, and identifying the value of the timestamp associated with said connection;

selecting the minimum value of the identified timestamps, removing a data packet from the head of that one of the queues associated with the connection corresponding to said minimum value, and transmitting the removed data packet to an output;

wherein the subqueue to which the backlogged connection is appended is selected as the subqueue associated with the smallest granularity for which the granularity times the number of bins decremented by one is larger than the difference between the value of the timestamp associated with the backlogged connection and the value of the system potential;

wherein the bin in the selected subqueue to which the backlogged connection is appended is selected as the one associated with the result of the modulo operation between the value of the timestamp and the granularity times the number of bins, in which said result is then divided by the granularity.

2. The method of claim 1, wherein the value of the system potential used to compute the timestamps is associated with each backlogged connection.

3. The method of claim 1, where the backlogged connection is appended at the head of the queue associated with the selected bin.

4. The method of claim 1, where the backlogged connection is appended at the tail of the queue associated with the selected bin.

5. The method of claim 1, in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as a maximum value between a previous value of the timestamp assigned to the connection and a current value of the system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet is not backlogged before the packet reaches the head of the associated queue,

and in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as the previous value of the timestamp assigned to the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet is backlogged before the packet reaches the head of the associated queue.

6. The method of claim 1, further comprising the step of providing that the granularity of the plurality of calendar subqueues increases by a predefined factor for each of the calendar subqueues.

7. The method of claim 6, wherein the value of the system potential is used to compute the timestamps associated with each backlogged connection.

8. The method of claim 6, where the backlogged connection is appended at the head of the queue associated with the selected bin.

9. The method of claim 6, where the backlogged connection is appended at the tail of the queue associated with the selected bin.

10. The method of claim 6, in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as a maximum value between a previous value of the timestamp assigned to the connection and a current value of the system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet is not backlogged before the packet reaches the head of the associated queue,

and in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as the previous value of the timestamp assigned to the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet is backlogged before the packet reaches the head of the associated queue.

11. The method of claim 1, in which the granularity of the first calendar subqueue of the plurality of calendar subqueues is equal to one timeslot.

12. The method of claim 11, wherein the value of the system potential is used to compute the timestamps associated with each backlogged connection.

13. The method of claim 11, where the backlogged connection is appended at the head of the queue associated with the selected bin.

14. The method of claim 11, where the backlogged connection is appended at the tail of the queue associated with the selected bin.

15. The method of claim 11, in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as a maximum value between a previous value of the timestamp assigned to the connection and a current value of the system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet is not backlogged before the packet reaches the head of the associated queue,

and in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as the previous value of the timestamp assigned to the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet is backlogged before the packet reaches the head of the associated queue.

16. An apparatus for servicing, at a predetermined service rate, a plurality of queues containing data packets, each of said queues being associated with respective connections, said connections traversing an associated communication switch, each of said connections being allocated a respective data transfer rate, said apparatus comprising:

memory forming the plurality of queues associated with respective ones of said connections,

a receiver for receiving a plurality of data packets via a plurality of data links, for identifying for each received data packet the respective one of said connections, and identifying the associated one of said queues, and for storing each of the received data packets in its respective identified queue,

a first controller for associating a timestamp with each connection whose associated queue has at least one data packet waiting therein, in which said connection is identified as a backlogged connection, and generating a timestamp associated with each connection each time a new data packet reaches the head of the associated queue,

a sorter for sorting the timestamps using a plurality of calendar subqueues, each of said calendar subqueues being associated with a respective specified granularity and comprising a plurality of bins, each of said bins being associated with an interval of values of timestamps according to the respective granularity of the calendar subqueue, and each of said bins comprising a queue of connections whose respective timestamps have values within the interval associated with the bin,

a first selector for selecting for each backlogged connection one of the said calendar subqueues and one of the bins in the selected calendar subqueue according to the value of the associated timestamp each time a new data packet reaches the head of the associated queue of the corresponding connection, and for appending said backlogged connection to the queue of connections in the selected bin in the selected calendar subqueue,

a second controller generating a value for the system potential according to a predetermined function, and for identifying the bin in each calendar subqueue associated with the value of the system potential,

a second selector for identifying, for each of the calendar subqueues, the first non-empty bin whose minimum associated timestamp value is not smaller than the minimum timestamp value associated with the bin associated with the value of system potential in said calendar subqueue, for determining for each of the identified non-empty bins the connection at the head of the corresponding queue of connections, and for identifying the value of the timestamp associated with said connection,

a third selector for selecting the minimum value of the identified timestamps, and

a transmitter for removing a data packet from the head of that one of the queues associated with the connection corresponding to said minimum value, and transmitting the removed data packet to an output;

said first selector selecting the subqueue as the subqueue associated with the smallest granularity for which the granularity times the number of bins decremented by one is larger than the difference between the value of the timestamp associated with the backlogged connection and the value of the system potential;

and selecting the bin in the selected subqueue as the one associated with the result of the modulo operation between the value of the timestamp and the granularity times the number of bins, in which said result is then divided by the granularity.

17. The apparatus of claim 16, wherein the value of the system potential is used to compute the timestamps associated with each backlogged connection.

18. The apparatus of claim 16, wherein the backlogged connection is appended at the head of the queue associated with the selected bin.

19. The apparatus of claim 16, wherein the backlogged connection is appended at the tail of the queue associated with the selected bin.

20. The apparatus of claim 16, wherein the first controller further includes apparatus operative when the connection associated with the data packet is not backlogged before the packet reaches the head of the associated queue for then generating the timestamp associated with the backlogged connection, each time a new data packet reaches the head of the associated queue, as a maximum value between a previous value of the timestamp assigned to the connection and a current value of the system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server,

operative when the connection associated with the data packet is backlogged before the packet reaches the head of the associated queue for then generating the timestamp associated with a backlogged connection, each time a new data packet reaches the head of the associated queue, as the previous value of the timestamp assigned to the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server.

21. The apparatus of claim 16, further comprising the step of providing that the granularity of the plurality of calendar subqueues increases by a predefined factor for each of the calendar subqueues.

22. The apparatus of claim 21, wherein the value of the system potential is used to compute the timestamps associated with each backlogged connection.

23. The apparatus of claim 21, wherein the backlogged connection is appended at the head of the queue associated with the selected bin.

24. The apparatus of claim 21, wherein the backlogged connection is appended at the tail of the queue associated with the selected bin.

25. The apparatus of claim 21, wherein the first controller further includes apparatus operative when the connection associated with the data packet is not backlogged before the packet reaches the head of the associated queue for then generating the timestamp associated with the backlogged connection, each time a new data packet reaches the head of the associated queue, as a maximum value between a previous value of the timestamp assigned to the connection and a current value of the system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server,

operative when the connection associated with the data packet is backlogged before the packet reaches the head of the associated queue for then generating the timestamp associated with a backlogged connection, each time a new data packet reaches the head of the associated queue, as the previous value of the timestamp assigned to the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server.

26. The apparatus of claim 16, in which the granularity of the first calendar subqueue of the plurality of calendar subqueues is equal to one timeslot.

27. The apparatus of claim 26, wherein the value of the system potential is used to compute the timestamps associated with each backlogged connection.

28. The apparatus of claim 26, wherein the backlogged connection is appended at the head of the queue associated with the selected bin.

29. The apparatus of claim 26, wherein the backlogged connection is appended at the tail of the queue associated with the selected bin.

30. The apparatus of claim 26, wherein the first controller further includes apparatus operative when the connection associated with the data packet is not backlogged before the packet reaches the head of the associated queue for then generating the timestamp associated with the backlogged connection, each time a new data packet reaches the head of the associated queue, as a maximum value between a previous value of the timestamp assigned to the connection and a current value of the system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server,

operative when the connection associated with the data packet is backlogged before the packet reaches the head of the associated queue for then generating the timestamp associated with a backlogged connection, each time a new data packet reaches the head of the associated queue, as the previous value of the timestamp assigned to the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server.