Output Queue Latency Behavior For Input Queue Based Device

• US 20140161135A1
• Filed: 12/07/2012
• Published: 06/12/2014
• 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
• Granted Patent: US 10,122,645 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• 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 of a plurality of input ports coupled to an output port;

calculating, by a controller, an aggregate queue length value for the output port as a sum of the virtual output queue length values from the plurality of input ports; and

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

2. The method of claim 1, further comprising:

comparing, by the controller, the aggregate queue length value to a predetermined threshold, wherein the feedback message is a tail drop message that instructs the at least one of the plurality of input ports to stop buffering subsequent packets associated with the output port.

3. The method of claim 2, wherein the tail drop message instructs at least one of the plurality of input ports to drop the subsequent packets.

4. The method of claim 1, further comprising:

accessing the aggregate queue length value from the feedback message; and

comparing the aggregate queue length value to a predetermined threshold.

5. The method of claim 1, further comprising:

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

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

6. 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.

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

8. 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 of a plurality of input ports coupled to the output port; and

a controller configured to calculate an aggregate queue length value for the output port as a sum of the virtual output queue length value from each of the plurality of input ports and compare the aggregate queue length value to a predetermined threshold, wherein feedback is provided to the plurality of input ports according to a result of the comparison.

9. The network device of claim 8, wherein the controller is configured to generate a tail drop message if the aggregate queue value exceeds the predetermined threshold, wherein the tail drop message instructs at least one of the plurality of input ports to stop buffering subsequent packets associated with the output port.

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

11. The network device of claim 8, wherein the draining rate is set according to a decaying average function based on the occupancy and at least one past occupancy for each of the plurality of output ports.

12. The network device of claim 8, 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.

13. The network device of claim 8, 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.

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

15. The network device of claim 8, wherein the feedback instructs at least one of the plurality of input ports to drop subsequent packets.

16. A non-transitory computer readable medium containing instructions that when executed are configured to:

calculate an aggregate queue length value for a 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;

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.

17. The non-transitory computer readable medium of claim 16, wherein when the difference between the aggregate queue length value and the predetermined queue length value exceeds a high threshold, the message includes a packet drop command.

18. The non-transitory computer readable medium of claim 16, wherein when the difference between the aggregate queue length value and the predetermined queue length value exceeds a low threshold, the message includes a congestion warning.

19. The non-transitory computer readable medium of claim 16, wherein when the difference between the aggregate queue length value and the predetermined queue length value exceeds a high threshold, the message includes a packet drop command, and when the difference between the aggregate queue length value and the predetermined queue length value exceeds a low threshold, the message includes a congestion warning, wherein the high threshold is greater than the low threshold.

20. A method comprising:

receiving a plurality of incoming packets at virtual output queues, wherein each of the virtual output queues is associated with a specific output port;

applying a timestamp to each of the incoming packets;

comparing timestamps to identify an oldest timestamp among the virtual output queues for the specific output port;

selecting one of the virtual output queues based on the oldest timestamp; and

forwarding data from the selected virtual output queue to the specific output port.