Flow based congestion control

• US 20070171914A1
• Filed: 03/27/2007
• Published: 07/26/2007
• Est. Priority Date: 07/23/2001
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kalkunte, Mohan, Ambe, Shekhar, Kadambi, Shiri, Relan, Sandeep
• Granted Patent: US 7,684,330 B2
• Time in Patent Office: Days
• US Class Current: 370/395.200
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/266 Stopping or restarting the source, e.g. X-on or X-off
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• 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/33 using forward notification
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6205 Arrangements for avoiding head of line blocking
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/50 : Overload detection or protection within a single switching element
• CPC Class Codes: H04L 49/508 : Head of Line Blocking Avoidance
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: Y02D 30/50 : in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method for selectively controlling the flow of data through a network device is discussed. The network device has a plurality of ports, with each port of the plurality of ports having a plurality of priority queues. Congestion at one priority queue of the plurality of priority queues is detected and a virtual channel message is sent to other network devices connected to the network device causing data destined for the one priority queue to be halted. After the congestion at the one priority queue has abated, a virtual channel resume message is sent to the other network devices.

Claims

1. A method to selectively control the flow of data through a network device having ports, with each port includes priority queues, the method comprising:

detecting congestion at a priority queue;

sending a message including a bitmap showing congestion states of the priority queues to other network devices connected to the network device causing data destined for the priority queue to be halted; and

sending a resume message to the other network devices when congestion is clear.

2. The method according to claim 1, wherein the detecting of the congestion comprises determining that the congestion is occurring when a number of packets received at the priority queue exceeds a threshold value.

3. The method according to claim 1, further comprising:

negotiating a virtual channel between the network devices and the other network devices prior to the detecting of the congestion.

4. The method according to claim 1, wherein the bitmap is a combination of a port bitmap and a priority bitmap.

5. The method according to claim 1, wherein the priority queues correspond to a plurality of flow identification queues of data.

6. The method according to claim 5, wherein the flow identification queues are implemented as a link list with the network device and each one of the other network devices.

7. The method according to claim 1, wherein the detecting of the congestion comprises detecting congestion at the priority queue of an ingress port of the ports.

8. The method according to claim 7, wherein a priority queue memory for each of the priority queues is set by a backpressure limit threshold.

9. The method according to claim 1, wherein the detecting of the congestion comprises detecting congestion at the priority queue of an egress port of the ports.

10. The method according to claim 9, wherein the priority queues correspond to a plurality of flow identification queues of data.

11. The method according to claim 10, further comprising:

calculating a flow identification corresponding to one of the flow identification queues once congestion is detected on the egress port.

12. The method according to claim 9, further comprising:

sending internal messages to all of the ports indicating congestion at the priority queue after the detecting of the congestion at the priority queue.

13. A method to selectively control a flow of data in a network device comprising:

receiving a message indicating congestion at a priority queue of a port of a remote network device and a bitmap showing congestion states of all priority queues of the remote network device;

halting transfer of data destined for the priority queue from the network device; and

sending data destined for the priority queue to the network device when congestion is resolved.

14. The method according to claim 13, further comprising:

starting a pause timer upon receipt of the virtual channel message, wherein the data is sent to the priority queue once the pause timer reaches a certain value.

15. The method according to claim 13, wherein the congestion states bitmap is a combination of a port bitmap and a priority bitmap.

16. The method according to claim 13, wherein the priority queue corresponds to at least one flow identification queue.

17. The method according to claim 16, wherein a flow identification of the flow identification queue is determined through negotiations between the network device and the remote network device.

18. The method according to claim 16, wherein the at least one flow identification queue is implemented as a link list with the network device and the remote network devices.

19. The method according to claim 13, further comprising:

sending internal messages to all ports of the network device indicating congestion at the at least one priority queue after the receiving of the message.

20. The method according to claim 19, further comprising:

sending out virtual channel messages indicating congestion by the all ports of the network device.

21. A network device to selectively control the flow of data through a network device having ports, with each port includes priority queues, the network device comprising:

a detecting unit configured to detect congestion at a priority queue;

a sending unit configured to send a message including a bitmap showing congestion states of the priority queues to other network devices connected to the network device causing data destined for the priority queue to be halted; and

a resuming unit configured to send a resume message to the other network devices when congestion is clear.

22. The network device according to claim 21, wherein the detecting unit is configured to determine that the congestion is occurring when a number of packets received at the priority queue exceeds a threshold value.

23. The network device according to claim 21, further comprising:

a negotiating unit configured to negotiate a virtual channel between the network devices and the other network devices prior to the detecting of the congestion.

24. The network device according to claim 21, wherein the bitmap is a combination of a port bitmap and a priority bitmap.

25. The network device according to claim 21, wherein the priority queues correspond to a plurality of flow identification queues of data.

26. The network device according to claim 25, wherein the flow identification queues are implemented as a link list with the network device and each one of the other network devices.

27. The network device according to claim 21, wherein the detecting unit is further configured to detect congestion at the priority queue of an ingress port of the ports.

28. The network device according to claim 27, wherein a priority queue memory for each of the priority queues is set by a backpressure limit threshold.

29. The network device according to claim 21, wherein the detecting unit is further configured to detect congestion at the priority queue of an egress port of the ports.

30. The network device according to claim 29, wherein the priority queues correspond to a plurality of flow identification queues of data.

31. The network device according to claim 30, further comprising:

a calculating unit configured to calculate a flow identification corresponding to one of the flow identification queues once congestion is detected on the egress port.

32. The network device according to claim 29, further comprising:

a sending unit configured to send internal messages to all of the ports indicating congestion at the priority queue after the detecting unit detects the congestion at the priority queue.

33. A network device to selectively control a flow of data in a network device comprising:

a receiving unit configured to receive a message indicating congestion at a priority queue of a port of a remote network device and a bitmap showing congestion states of all priority queues of the remote network device;

a processing unit configured to halt transfer of data destined for the priority queue from the network device; and

a sending unit configured to send data destined for the priority queue to the network device when congestion is resolved.

34. The network device according to claim 33, further comprising:

a pause timer configured to start upon receipt of the virtual channel message, wherein the sending unit sends the data to the priority queue once the pause timer reaches a certain value.

35. The network device according to claim 33, wherein the congestion states bitmap is a combination of a port bitmap and a priority bitmap.

36. The network device according to claim 33, wherein the priority queue corresponds to at least one flow identification queue.

37. The network device according to claim 36, wherein a flow identification of the flow identification queue is determined through negotiations between the network device and the remote network device.

38. The network device according to claim 36, wherein the at least one flow identification queue is implemented as a link list with the network device and the remote network devices.

39. The network device according to claim 33, further comprising:

a sending unit configured to send internal messages to all ports of the network device indicating congestion at the at least one priority queue after the receiving of the message.

40. The network device according to claim 39, further comprising:

a sending unit configured to send out virtual channel messages indicating congestion by the all ports of the network device.