Methods and apparatus for flow-controllable multi-staged queues

• US 8,218,442 B2
• Filed: 09/30/2008
• Issued: 07/10/2012
• Est. Priority Date: 09/11/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Godbole, Avanindra, Sindhu, Pradeep, Frailong, Jean-Marc
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Loo, Juvena
• Application Number:
  US12/242,230
• Publication Number:
  US 20100061239A1
• Time in Patent Office: 1,379 Days
• Field of Search: 370411-417, 370/395.71, 370229-235
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/266 Stopping or restarting the source, e.g. X-on or X-off
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

In one embodiment, a method includes sending a first flow control signal to a first stage of transmit queues when a receive queue is in a congestion state. The method also includes sending a second flow control signal to a second stage of transmit queues different from the first stage of transmit queues when the receive queue is in the congestion state.

Claims

1. An apparatus implemented in at least one of a memory device or a processing device, comprising:

a first flow control module configured to send a first flow control signal based on data flow within a first flow control loop including a physical link, a first stage of queues, and a second stage of queues disposed within a transmission path between the physical link and the first stage of queues;

a second flow control module configured to define a second flow control signal based on data flow within a second flow control loop including the second stage of queues and excluding the first stage of queues; and

a third flow control module configured to define a third flow control signal based on data flow associated with a third flow control loop including the physical link, the third flow control loop excluding the first stage of queues and the second stage of queues.

2. The apparatus of claim 1, wherein the second flow control loop is a priority-based flow control loop.

9. The apparatus of claim 1, wherein:

the first flow control signal includes an identifier of a transmit queue from the first stage of queues and a suspension time value associated with the identifier of the transmit queue, and

the suspension time value being based on a first request to suspend transmission at a receive queue from the first stage of queues and a second request to suspend transmission at the receive queue.

10. The apparatus of claim 1, wherein:

the first flow control signal includes an identifier of a transmit queue from the first stage of queues and a suspension time value associated with the identifier of the transmit queue,

the suspension time value being based on a first request to suspend transmission at a receive queue from the first stage of queues and a second request suspend transmission at the receive queue, and

the suspension time is an average of a time period associated with the first request and a time period associated with the second request.

11. The apparatus of claim 1, wherein:

the first flow control signal includes an identifier of a transmit queue from the first stage of queues and a suspension time value associated with the identifier of the transmit queue,

the suspension time value being based on a first request to suspend transmission at a receive queue from the first stage of queues and a second request to suspend transmission at the receive queue, and

the suspension time value is a time period associated with the first request when the time period associated with the first request is greater than a time period associated with the second request.

12. The apparatus of claim 1, wherein:

the first flow control signal includes an identifier of a transmit queue from the first stage of queues and a suspension time value associated with the identifier,

the suspension time value being based on a first request to suspend transmission at a receive queue from the first stage of queues and a second request suspend transmission at the receive queue, and

the first flow control module configured to delay defining the first flow control signal for a wait time period, the first request and the second request being within the wait time period.

13. The apparatus of claim 1, wherein the first stage of queues including a transmit queue at a first interface card and a transmit queue at a second interface card that fan into the second stage of queues.

14. The apparatus of claim 1, wherein the first flow control signal includes a layer-2 flow control packet, the first flow control module being associated with a layer-2 device.

3. A method, comprising:

defining a first flow control signal for a first stage of transmit queues based on a congestion state of a receive queue at a first time;

sending the first flow control signal to the first stage of transmit queues when the receive queue is in the congestion state at the first time;

defining a second flow control signal for a second stage of transmit queues based on the congestion state of the receive queue at a second time; and

sending the second flow control signal to a second stage of transmit queues different from the first stage of transmit queues when the receive queue is in the congestion state at the second time;

defining a third flow control signal for a physical link based on the congestion state of the receive queue at a third time; and

sending the third flow control signal to the physical link different from the second stage of transmit queues and from the first stage of transmit queues when the receive queue is in the congestion state at the third time, the first stage of transmit queues includes a first plurality of transmit queues that fan into a queue included in the second stage of transmit queues, at least one transmit queue from the first plurality of transmit queues being at a first interface card, at least one transmit queue from the first plurality of transmit queues being at a second interface card.

4. The method of claim 3, wherein the first stage of transmit queues includes a second plurality of transmit queues that fan into a plurality of transmit queues included in the second stage of transmit queues, at least one transmit queue from the second plurality of transmit queues being at the first interface card, at least one transmit queue from the second plurality of transmit queues being at the second interface card.

5. The method of claim 3, wherein the second flow control signal is defined based on a priority associated with a portion of the second stage of transmit queues.

6. The method of claim 3, wherein the second time is different than the first time.

7. The method of claim 3, wherein the first time corresponds to the second time.

8. The method of claim 3, wherein the sending the first flow control signal and the sending the second flow control signal are triggered in response to the receive queue changing from an available state to the congestion state at the first time and the congestion state at the second time.

15. An apparatus implemented in at least one of a memory device or a processing device, comprising:

a first stage of transmit queues including a transmit queue at a first interface card and a transmit queue at a second interface card;

a second stage of transmit queues, the transmit queue at the first interface card and the transmit queue at the second interface card being fanned into the second stage of transmit queues; and

a control module modifying flow control for the first stage of transmit queues when a first flow control signal is received, the first flow control signal being associated with a first flow control loop including a physical link, the first stage of transmit queues and the second stage of transmit queues,

the control module modifying flow control for the second stage of transmit queues when a second flow control signal is received, the second flow control signal being associated with a second flow control loop including the second stage of transmit queues and excluding the first stage of transmit queues,

the control module modifying flow control for a physical link when a third flow control signal is received the third flow control signal being associated with a third flow control loop including the physical link and excluding the first stage of transmit queues and the second stage of transmit queues.

16. The apparatus of claim 15, wherein the control module modifies flow control for the physical link when a third flow control signal is received, the third flow control signal is associated with the physical link and excluding the first stage of transmit queues and the second stage of transmit queues.

17. The apparatus of claim 15, wherein the first flow control signal is based on a layer-2 protocol.