COORDINATED QUEUING BETWEEN UPSTREAM AND DOWNSTREAM QUEUES IN A NETWORK DEVICE

• US 20110122887A1
• Filed: 01/25/2011
• Published: 05/26/2011
• Est. Priority Date: 10/09/2007
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: MA, Qingming, SU, Jiaxiang
• Granted Patent: US 8,576,863 B2
• Time in Patent Office: Days
• 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-24. -24. (canceled)

25. A non-transitory computer-readable medium to store instructions executable on a network device, the instructions including:

one or more instructions to assign weights, respectively, to a plurality of downstream queues included in the network device;

one or more instructions to calculate ratios, respectively, for the plurality of downstream queues, where each of the ratios is calculated based on comparing a current fill level of a respective one of the plurality of downstream queues to a maximum size of the respective one of the plurality of downstream queues;

one or more instructions to determine scheduling values, respectively, for the plurality of downstream queues, based on the assigned weights and the calculated ratios; and

one or more instructions to schedule transmissions between an upstream queue, included in the network device, and the plurality of downstream queues based on the determined scheduling values.

26. The non-transitory computer-readable medium of claim 25, where the plurality of downstream queue are associated with an egress card of the network device, and where the upstream queue is associated with an ingress card of the network device.

27. The non-transitory computer-readable medium of claim 26, where a interconnect couples the ingress and egress cards, and where the one or more instructions to schedule the transmissions is further to schedule, based on the determined scheduling values, the transmission through the interconnect.

28. The non-transitory computer-readable medium of claim 26, where the one or more instructions to determine the scheduling values are executed by the egress card, and where the one or more instructions to schedule the transmissions are executed by the ingress card.

29. The non-transitory computer-readable medium of claim 25, where the one or more instructions to determine the scheduling values include:

one or more instructions to assign, as one of the scheduling values, a particular number to a full downstream queue of the downstream queues, and where one or more instructions to schedule transmissions include;

one or more instructions to bypass the full downstream queue based on assignment of the particular number to the full downstream queue.

30. The non-transitory computer-readable medium of claim 25, where the one or more instructions to determine the scheduling values include:

one or more instructions to assign, as one of the scheduling values, a particular number to an empty downstream queue of the downstream queues, and where one or more instructions to schedule transmissions include;

one or more instructions to prioritize the empty downstream queue based on assignment of the particular number to the empty downstream queue.

31. The non-transitory computer-readable medium of claim 25, where the network device includes a plurality of upstream queues,

where the one or more instructions to assign the weights, respectively, to the plurality of downstream queues further include:

one or more instructions to assign, to each of the plurality of upstream queues, a different weight associated with each of the plurality of downstream queues.

32. A method implemented in a network device, the method comprising:

determining, by a downstream device in the network device, a scheduling value based on a current length of an associated downstream queue, a maximum size of the downstream queue, and a priority value associated with the downstream queue, where the priority value is associated with an ordering, of the downstream queue, to receive data, relative to other downstream queues included in the network device;

sending, from the downstream device to an upstream device in the network device, the scheduling value; and

scheduling, by the upstream device, dequeuing of one or more data units, destined for the downstream queue, from an associated upstream queue based on the scheduling value.

33. The method of claim 32, where the downstream queue is associated with an egress card of the network device, and where the upstream queue is associated with an ingress card of the network device.

34. The method of claim 32, where the scheduling value approaches a first value when the downstream queue approaches a full state.

35. The method of claim 34, where scheduling the dequeuing of the one or more data units includes:

delaying the dequeuing of the one or more data units to the downstream queue when the scheduling value approaches the first value.

36. The method of claim 34, where the scheduling value approaches a second value as the downstream queue approaches an empty state.

37. The method of claim 36, where scheduling the dequeuing of the one or more data units includes:

prioritizing, relative to the other downstream queues in the network device, the dequeuing of the one or more data units to the downstream queue when the scheduling value approaches the second value.

38. A device, comprising:

a first upstream queue to;

queue a first data unit, and

dequeue, based on a first scheduling value, the queued first data unit to a interconnect in the network device;

a first downstream queue to;

receive the first data unit from the interconnect,

buffer the received first data unit, and

forward the buffered first data unit toward a destination; and

a scheduler to;

determine the first scheduling value based on;

a first priority value, where the first priority value is 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.

39. The device of claim 38, further comprising:

a second upstream queue to;

queue a second data unit,

receive, from the scheduler, the first scheduling value, and

dequeue, based on the received first scheduling value, the queued second data unit to the interconnect.

40. The device of claim 38, where the scheduler is further to 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, where the updated fill level is determined after the first downstream queue buffers the first data unit and prior to the first downstream queue forwarding the buffered first data unit toward a destination, and where the first upstream queue is further to;

queue a second data unit, and

dequeue, based on the updated first scheduling value, the queued second data unit to the interconnect.

41. The device of claim 40, where the first upstream queue, when dequeuing the queued second data unit based on the updated first scheduling value, is further to:

dequeue, based on the first scheduling value, the queued second data unit to the interconnect when a difference between first scheduling value and the updated first scheduling value is less than a particular threshold number.

dequeue, based on the updated first scheduling value, the queued second data unit to the interconnect when the difference between first scheduling value and the updated first scheduling value is greater than the particular threshold number.

42. The device of claim 38, further comprising:

a second downstream queue,

where the scheduler is further to;

determine a second scheduling value based on at least;

a second priority value, where the second priority value is 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 first upstream queue, when dequeuing the queued first data unit, is further to;

dequeue, via the interconnect, the queued first data unit to one of the first downstream queue or the second downstream queue, based on the first scheduling value and the second scheduling value.

43. The device of claim 38, further comprising:

an ingress card associated with the first upstream queue, and

an egress card associated with the first downstream queue.

44. The device of claim 38, where the scheduler is further to:

receive the fill level associated with the first downstream queue.