Coordinated queuing between upstream and downstream queues in a network device

• US 8,576,863 B2
• Filed: 01/25/2011
• Issued: 11/05/2013
• Est. Priority Date: 10/09/2007
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ma, Qingming, Su, Jiaxiang
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): KAMARA, MOHAMED A
• Application Number:
  US13/013,258
• Publication Number:
  US 20110122887A1
• Time in Patent Office: 1,015 Days
• Field of Search: 370411-413, 370/232, 370/252, 370414-418
• US Class Current: 370/413
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 47/6275 based on priority
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A system determines a scheduling value based on a current length of a downstream queue in a network device. The system sends the scheduling value from the downstream queue to an upstream queue and schedules dequeuing of one or more data units, destined for the downstream queue, from the upstream queue based on the scheduling value.

Claims

1. A device comprising:

a first upstream queue to queue a first data unit and a second data unit;

a first downstream queue; and

a scheduler to;

determine a first scheduling value, associated with the first downstream queue, based on;

a first priority value associated with the first downstream queue,

a maximum size of the first downstream queue, and

a fill level of the first downstream queue prior to the first upstream queue dequeuing the first data unit or the second data unit,

cause, based on the first scheduling value, the first data unit to be transferred from the first upstream queue to the first downstream queue via an interconnect,

the first downstream queue buffering the first data unit for transmission toward a destination,

determine an updated first scheduling value based on;

the first priority value associated with the first downstream queue,

the maximum size of the first downstream queue, and

an updated fill level of the first downstream queue after the first downstream queue buffers the first data unit and prior to the transmission of the first data unit toward the destination, and cause

the second data unit to be transferred, via the interconnect, from the first upstream queue to the first downstream queue when a difference between the updated first scheduling value and the first scheduling value is greater than a particular threshold, or

the second data unit to be transferred, via the interconnect, from the first upstream queue to the first downstream queue, when;

the difference between the updated first scheduling value and the first scheduling value is not greater than the particular threshold, and

a last notification, associated with the first downstream queue receiving data, is not associated with a timeout.

2. The device of claim 1, further comprising:

a second upstream queue to queue a third data unit,

where the scheduler is further to;

cause, based on the first scheduling value, the third data unit to be transferred, via the interconnect, from the second upstream queue to the first downstream queue, and

where the updated fill level of the first downstream queue is further based on the first downstream queue buffering the third data unit.

3. The device of claim 1, further comprising:

a second downstream queue,

where the scheduler is further to;

determine a second scheduling value based on;

a priority value associated with the second downstream queue,

a maximum size of the second downstream queue, and

a fill level of the second downstream queue prior to the first upstream queue dequeuing the first data unit, and

where the scheduler, when causing the first data unit to be transferred, is further to;

determine to transfer the first data unit to the first downstream queue and not to the second downstream queue based on the first scheduling value and the second scheduling value.

4. The device of claim 1, where:

the first upstream queue is associated with an ingress card, and

the first downstream queue is associated with an egress card.

5. The device of claim 1, where the scheduler is further to:

monitor the fill level associated with the first downstream queue, and

determine the updated fill level of the first downstream queue based on monitoring the fill level.

6. The device of claim 3, where the second scheduling value is associated with a particular value when the fill level of the second downstream queue indicates that the second downstream queue is substantially full, and

where the scheduler, when determining to transfer the first data unit to the first downstream queue and not to the second downstream queue, is further to:

bypass the second downstream queue based on determining that the second scheduling value is associated with the particular value.

7. The device of claim 3, where the scheduler, when determining to transfer the first data unit to the first downstream queue and not the second downstream queue, is further to:

compare the first scheduling value and the second scheduling value, and

determine, based on comparing the first scheduling value and the second scheduling value, that the second downstream queue is more full than the first downstream queue.

8. A method comprising:

determining, by a network device, a first scheduling value, associated with a first downstream queue, based on;

a first priority value associated with the first downstream queue,

a maximum size of the first downstream queue, and

a fill level of the first downstream queue prior to a first upstream queue dequeuing a first data unit;

causing, by the network device and based on the first scheduling value, the first data unit to be transferred from the first upstream queue to the first downstream queue via an interconnect,

the first downstream queue buffering the first data unit for transmission toward a destination;

determining, by the network device, an updated first scheduling value based on;

the first priority value associated with the first downstream queue,

the maximum size of the first downstream queue, and

an updated fill level of the first downstream queue after the first downstream queue buffers the first data unit and prior to the transmission of the first data unit toward the destination; and

causing, by the network device, a second data unit enqueued in the first upstream queue to be transferred, via the interconnect, from the first upstream queue to the first downstream queue when;

a difference between the updated first scheduling value and the first scheduling value is greater than a particular threshold;

or

the difference between the updated first scheduling value and the first scheduling value is not greater than the particular threshold, and a last notification, associated with the first downstream queue receiving data, is not associated with a timeout.

9. The method of claim 8, further comprising:

causing, based on the first scheduling value, a third data unit, enqueued at a second upstream queue, to be transferred from the second upstream queue to the first downstream queue,

the updated fill level of the first downstream queue being further based on the first downstream queue buffering the third data unit.

10. The method of claim 8, further comprising:

determining a second scheduling value, associated with a second downstream queue, based on;

a priority value associated with the second downstream queue,

a maximum size of the second downstream queue, and

a fill level of the second downstream queue prior to the first upstream queue dequeuing the first data unit, and

where causing the first data unit to be transferred further includes;

determining to transfer the first data unit to the first downstream queue and not to the second downstream queue based on the first scheduling value and the second scheduling value.

11. The method of claim 10, where the second scheduling value is associated with a particular value when the fill level of the second downstream queue indicates that the second downstream queue is substantially full, and

where determining to transfer the first data unit to the first downstream queue and not to the second downstream queue includes:

bypassing the second downstream queue based on determining that the second scheduling value is associated with the particular value.

12. The method of claim 10, where the first scheduling value is associated with a particular value when the fill level of the first downstream queue indicates that the first downstream queue is substantially empty, and

where determining to transfer the first data unit to the first downstream queue and not to the second downstream queue includes:

transferring the first data unit to the first downstream queue based on determining that the first scheduling value is associated with the particular value.

13. The method of claim 10, where determining to transfer the first data unit to the first downstream queue and not to the second downstream queue includes:

comparing the first scheduling value and the second scheduling value, and

determining, based on comparing the first scheduling value and the second scheduling value, that the second downstream queue is more full than the first downstream queue.

14. The method of claim 8, where:

the first upstream queue is associated with an ingress card, and

the first downstream queue is associated with an egress card.

15. A non-transitory computer-readable medium to store instructions, the instructions comprising:

one or more instructions that, when executed by one or more devices, cause the one or more devices to;

determine a first scheduling value, associated with a first downstream queue, based on;

a first priority value associated with the first downstream queue,

a maximum size of the first downstream queue, and

a fill level of the first downstream queue prior to a first upstream queue dequeuing a first data unit;

cause, based on the first scheduling value, the first data unit to be transferred from the first upstream queue to the first downstream queue via an interconnect,

the first downstream queue buffering the first data unit for transmission toward a destination;

determine an updated first scheduling value based on;

the first priority value associated with the first downstream queue,

the maximum size of the first downstream queue, and

an updated fill level of the first downstream queue after the first downstream queue buffers the first data unit and prior to the transmission of the first data unit toward the destination; and

cause a second data unit enqueued in the first upstream queue to be transferred, via the interconnect, from the first upstream queue to the first downstream queue when;

a difference between the updated first scheduling value and the first scheduling value is greater than a particular threshold;

or

the difference between the updated first scheduling value and the first scheduling value is not greater than the particular threshold, and a last notification, associated with the first downstream queue receiving data, is not associated with a timeout.

16. The non-transitory computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions to;

cause, based on the first scheduling value, a third data unit, enqueued at a second upstream queue, to be transferred from the second upstream queue to the first downstream queue,

where the updated fill level of the first downstream queue is further based on the first downstream queue buffering the third data unit.

17. The non-transitory computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions to;

determine a second scheduling value, associated with a second downstream queue, based on;

a priority value associated with the second downstream queue,

a maximum size of the second downstream queue, and

a fill level of the second downstream queue prior to the first upstream queue dequeuing the first data unit, and

where the one or more instructions to cause the first data unit to be transferred further include;

one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue based on the first scheduling value and the second scheduling value.

18. The non-transitory computer-readable medium of claim 17, where the second scheduling value is associated with a particular value when the fill level of the second downstream queue indicates that the second downstream queue is substantially full, and

where the one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue include:

one or more instructions to bypass the second downstream queue based on determining that the second scheduling value is associated with the particular value.

19. The non-transitory computer-readable medium of claim 17, where the first scheduling value is associated with a particular value when the fill level of the first downstream queue indicates that the first downstream queue is substantially empty, and

where the one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue include:

one or more instructions to transfer the first data unit to the first downstream queue based on determining that the first scheduling value is associated with the particular value.

20. The non-transitory computer-readable medium of claim 17, where the one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue include:

one or more instructions to;

compare the first scheduling value and the second scheduling value, and

determine, based on comparing the first scheduling value and the second scheduling value, that the second downstream queue is more full than the first downstream queue.