Queue scheduling mechanism in a data packet transmission system

• US 20030118044A1
• Filed: 11/21/2002
• Published: 06/26/2003
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Wind, Daniel, Blanc, Alain, Gallezot, Rene, Le Maut, Francois
• Granted Patent: US 7,385,993 B2
• Time in Patent Office: Days
• US Class Current: 370/414
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/39 Credit based
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/626 channel conditions

Abstract

A queue scheduling mechanism in a data packet transmission system, the data packet transmission system including a transmission device for transmitting data packets, a reception device for receiving the data packets, a set of queue devices respectively associated with a set of priorities each defined by a priority rank for storing each data packet transmitted by the transmission device into the queue device corresponding to its priority rank and a queue scheduler for reading, at each packet cycle, a packet in one of the queue devices determined by a normal priority preemption algorithm. The queue scheduling mechanism includes a credit device that provides, at each packet cycle, a value N defining the priority rank to be read by the queue scheduler from the queue device corresponding to the priority N instead of the queue device determined by the normal priority preemption algorithm. The queue scheduling mechanism further includes an exhaustive priority register that registers the value of at least one exhaustive priority rank to be read by the queue scheduler from the queue device corresponding to the exhaustive priority rank rather than from the queue device corresponding to the priority N.

Claims

1. A queue scheduling mechanism in a data packet transmission system, the data packet transmission system including a transmission device for transmitting data packets, a reception device for receiving said data packets, a set of queue devices respectively associated with a set of priorities each defined by a priority rank for storing each data packet transmitted by said transmission device into the queue device corresponding to its priority rank, a queue scheduler for reading, at each packet cycle, a packet in one of said queue devices, said queue scheduling mechanism comprising:

a credit device that provides at each packet cycle a value N defining the priority rank to be read by said queue scheduler from the queue device corresponding to the priority N instead of the queue device determined by a normal priority preemption algorithm; and

an exhaustive priority register that registers the value of at least one exhaustive priority rank to be read by said queue scheduler from the queue device corresponding to said exhaustive priority rank rather than from the queue device corresponding to said priority N.

2. The queue scheduling mechanism according to claim 1, wherein said credit device includes a credit table storing at each address a value N equal to one of said priority ranks, the address to be read by said queue scheduler for determining said priority N being incremented at each packet cycle.

3. The queue scheduling mechanism according to claim 2, wherein a data packet is read by said queue scheduler from said queue device corresponding to said exhaustive priority rank only if an active GRANT signal from said reception device is received by said queue scheduler.

4. The queue scheduling mechanism according to claim 3, wherein said GRANT signal depends upon the filling level of a receiving queue device in said reception device into which the data packets read from said queue devices are stored.

5. The queue scheduling mechanism according to claim 4, wherein a data packet is read from the queue device determined by said priority N when there is no data packet available in the queue device corresponding to said exhaustive priority.

6. The queue scheduling mechanism according to claim 4, wherein a data packet is read from the queue device determined by said normal priority preemption algorithm when there is no data packet available in neither the queue device corresponding to said exhaustive priority rank nor in the queue device corresponding to said priority N.

7. The queue scheduling mechanism according to claim 6, wherein the number of locations of said credit table containing each value N is defined according to a predetermined percentage of occurrences with respect to the values of the other priority ranks.

8. The queue scheduling mechanism according to claim 7, wherein a number of locations in said credit table contain no value meaning that the priority rank to be considered is the highest priority rank.

9. The queue scheduling mechanism according to claim 1 being used in a switch engine of a switching node within a network wherein said transmission device is an input adapter and said reception device is an output adapter.