Output queue latency behavior for input queue based device

• US 10,122,645 B2
• Filed: 12/07/2012
• Issued: 11/06/2018
• Est. Priority Date: 12/07/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Acharya, Dipankar Bhatt, Morandin, Guglielmo, Pan, Rong, Piglione, Chiara, Suzuki, Hiroshi
• Primary Examiner(s): Moore, Ian N
• Assistant Examiner(s): Van Roie, Justin T
• Application Number:
  US13/708,640
• Publication Number:
  US 20140161135A1
• Time in Patent Office: 2,160 Days
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

In one implementation, an input queue switch provides latency fairness across multiple input ports and multiple output ports. In one embodiment, each input port maintains a virtual output queue for each associate output port. The virtual output queues across multiple inputs are aggregated for each specific output port. The sum of the lengths of the virtual output queues is compared to a threshold, and based on the comparison, feedback may be generated to control the operation of the input port for subsequent packets. The feedback may instruct the input port to stop buffering or drop packets destined for the output port with the sum of the lengths of the virtual output queues associated to the specific output port that exceeds the threshold. In another embodiment, each packet has an arrival timestamp, and a virtual output queue having the oldest timestamp is selected first to dequeue.

Claims

1. A method comprising:

receiving a virtual output queue length value from each virtual output queue at each of a plurality of input ports coupled to an output port, wherein the output port includes an output queue having a size less than a size of each virtual output queue such that packet flow control is not performed at the output queue;

calculating, by a controller, an aggregate queue length value for the output port as a sum of each virtual output queue length value from each of the plurality of input ports, the aggregate queue length value representing an amount of data across the plurality of input ports and destined for the output port;

generating a feedback drop instruction for at least one of the plurality of input ports based on the aggregate queue length value for the output port;

instructing, in response to the feedback drop instruction, the at least one of the plurality of input ports to drop packets based on the aggregate queue length value wherein packets are dropped rather than delayed.

2. The method of claim 1, wherein a difference between a first latency of a first packet received at a first input port of the plurality of input ports and a second latency of a second packet received at a second input port of the plurality of input ports is within a predetermined range.

3. The method of claim 1, wherein the output port is an egress port of an input queue switch.

18. The method of claim 1, further comprising:

monitoring an occupancy of each virtual output queue at each of the plurality of input ports; and

setting a draining rate for each virtual output queue at each of the plurality of input ports according to the occupancy of the corresponding virtual output queue.

19. The method of claim 18, wherein the draining rate is set according to a decaying average function based on the occupancy and at least one past occupancy for the corresponding virtual output queue.

4. A network device comprising:

a communication interface of an output port, the communication interface configured to receive a virtual output queue length value from each virtual output queue at each of a plurality of input ports coupled to the output port, wherein the output port includes an output queue having a size less than a size of each virtual output queue such that packet flow control is not performed at the output queue; and

a controller configured to calculate an aggregate queue length value for the output port as a sum of each virtual output queue length value from each of the plurality of input ports and compare the aggregate queue length value to a predetermined threshold, the aggregate queue length value representing an amount of data of all of the plurality of input ports and destined for the output port;

wherein feedback is provided to the plurality of input ports according to a result of the comparison,

wherein the controller is configured to generate a tail drop message if the aggregate queue length value exceeds the predetermined threshold, wherein the tail drop message instructs the plurality of input ports to stop buffering subsequent packets associated with the output port and start dropping subsequent packets associated with the output port.

5. The network device of claim 4, wherein the controller is configured to monitor an occupancy of each virtual output queue at each of the plurality of input ports and set a draining rate for each virtual output queue at each of the plurality of input ports according to the occupancy of the corresponding virtual output queue,

wherein the draining rate is set according to a decaying average function based on the occupancy and at least one past occupancy for the corresponding virtual output queue.

6. The network device of claim 4, wherein the controller is configured to determine a draining rate for each of the plurality of input ports according to a current queue length value for each of the plurality of input ports.

7. The network device of claim 4, wherein a difference between a first latency of a first packet received at a first input port of the plurality of input ports and a second latency of a second packet received at a second input port of the plurality of input ports is within a predetermined range.

8. The network device of claim 4, wherein the network device is an input queue switch without output queuing in excess of a threshold amount.

9. The network device of claim 4, wherein the plurality of input ports is arranged on a first chip and the output port is arranged on a second chip.

12. The network device of claim 4, wherein the controller is configured to set the draining rate for each of the plurality of input ports according to a latency parameter.

10. A non-transitory computer readable medium containing instructions that when executed by a computer processor cause the computer processor to:

calculate an aggregate queue length value for an output port as a sum of a plurality of virtual output queue length values, wherein each of the virtual output queue length values is associated with one of a plurality of input ports, wherein the output port includes an output queue having a size less than a size of each virtual output queue at each of the plurality of input ports such that packet flow control is not performed at the output queue;

calculate a difference between the aggregate queue length value and a predetermined queue length value; and

generate a message based on the difference between the aggregate queue length value and the predetermined queue length value,

wherein when the difference between the aggregate queue length value and the predetermined queue length value exceeds a first threshold, the message includes a congestion warning, and

wherein when the difference between the aggregate queue length value and the predetermined queue length value exceeds a second threshold, the message includes a packet drop command,

wherein the second threshold is greater than the first threshold,

wherein the second threshold is triggered after the first threshold.

13. The non-transitory computer readable medium of claim 10, wherein the instructions further cause the computer processor to:

monitor an occupancy of a first virtual output queue at one of the plurality of input ports; and

set a draining rate for the first virtual output queue based on the occupancy of the first virtual output queue and based on a latency parameter.

15. The non-transitory computer readable medium of claim 10, wherein a first network device comprises the output port and the plurality of input ports and the message including the congestion warning is for a second network device.

11. A method comprising:

receiving a virtual output queue length value from each virtual output queue at each of a plurality of input ports coupled to an output port, wherein the output port includes an output queue having a size less than a size of each virtual output queue such that packet flow control is not performed at the output queue;

calculating, by a controller, an aggregate queue length value for the output port as a sum of each virtual output queue length value from each of the plurality of input ports, the aggregate queue length value representing an amount of data across the plurality of input ports and destined for the output port;

generating a feedback message for at least one of the plurality of input ports including the aggregate queue length value; and

comparing, by the controller, the aggregate queue length value to a first threshold and a second threshold, wherein the second threshold is greater than the first threshold,

wherein the feedback message instructs the at least one of the plurality of input ports to stop buffering subsequent packets associated with the output port when the aggregate queue length value exceeds the second threshold, and

wherein the feedback message includes a congestion warning when the aggregate queue length value is between the first threshold and the second threshold.

14. The method of claim 11, further comprising:

monitoring an occupancy of a first virtual output queue at the at least one of the plurality of input ports; and

setting a draining rate for the first virtual output queue based on the occupancy of the first virtual output queue and based on a latency parameter.

16. The method of claim 11, wherein a first network device comprises the output port and the plurality of input ports and the message including the congestion warning is for a second network device.

17. A non-transitory computer readable medium containing instructions that when executed by a computer processor cause the computer processor to:

receive a virtual output queue length value from each virtual output queue at each of a plurality of input ports coupled to an output port, wherein the output port includes an output queue having a size less than a size of each virtual output queue such that packet flow control is not performed at the output queue;

calculate an aggregate queue length value for the output port as a sum of each virtual output queue length value from each of the plurality of input ports, the aggregate queue length value representing an amount of data across the plurality of input ports and destined for the output port;

generate a feedback drop instruction for at least one of the plurality of input ports based on the aggregate queue length value for the output port;

instruct, in response to the feedback drop instruction, the at least one of the plurality of input ports to drop packets based on the aggregate queue length value wherein packets are dropped rather than delayed.

20. The non-transitory computer readable medium of claim 17, wherein the instructions further cause the computer processor to:

monitor an occupancy of each virtual output queue at each of the plurality of input ports; and

set a draining rate for each virtual output queue at each of the plurality of input ports according to the occupancy of the corresponding virtual output queue.