Flow based congestion control

• US 7,212,534 B2
• Filed: 06/18/2002
• Issued: 05/01/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
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): JAIN, RAJ K
• Application Number:
  US10/173,421
• Publication Number:
  US 20030016628A1
• Time in Patent Office: 1,778 Days
• Field of Search: None
• US Class Current: 370/395.2
• 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 for selectively controlling the flow of data through a network device having a plurality of ports, with each port of said plurality of ports having a plurality of priority queues, comprising:

detecting congestion at at least one priority queue of said plurality of priority queues;

sending a virtual channel message to other network devices connected to said network device causing data destined for said one priority queue to be halted;

waiting for the congestion at the at least one priority queue to abate; and

sending a virtual channel resume message to the other network devices;

wherein said step of sending a virtual channel message to other network devices comprises sending a bitmap showing congestion states of the priority queues.

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

3. The method according to claim 2, wherein said predetermined value is a backpressure limit threshold for said one priority queue.

4. The method according to claim 1, further comprising negotiating a virtual channel between said network devices and the other network devices prior to the step of detecting congestion at at least one priority queue.

5. The method according to claim 1, wherein said congestion states bitmap is a combination of a port bitmap and a priority bitmap.

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

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

8. The method according to claim 1, wherein said step of detecting congestion at at least one priority queue comprises detecting congestion at the at least one priority queue of an ingress port of said plurality of ports.

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

10. The method according to claim 1, wherein said step of detecting congestion at at least one priority queue comprises detecting congestion at at least one priority queue of an egress port of said plurality of ports.

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

12. The method according to claim 11, wherein a flow identification corresponding to one of said flow identification queues is calculated once congestion is detected on the egress port.

13. The method according to claim 10, further comprising sending internal messages to all of said plurality of ports indicating congestion at said at least one priority queue after the step of detecting congestion at at least one priority queue.

14. The method according to claim 13, further comprising sending out virtual channel messages indicating congestion by said all of said plurality of ports.

15. A method for selectively controlling the flow of data in a network device comprising:

receiving a virtual channel message indicating congestion at at least one priority queue of a port of a remote network device;

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

waiting for the congestion at the at least one priority queue to abate; and

sending data destined for said at least one priority queue to said network device;

wherein said step of receiving a virtual channel message from the remote network device comprises receiving a bitmap showing congestion states of all priority queues of the remote network device.

16. The method according to claim 15, wherein said step of waiting for the congestion at the at least one priority queue to abate comprises awaiting a resume virtual channel message from said remote network device.

17. The method according to claim 15, wherein said step of waiting for the congestion at the at least one priority queue to abate comprises monitoring a pause timer, which is started upon receipt of said virtual channel message and carrying out said step of sending data destined for said at least one priority queue once said pause timer reaches a certain value.

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

19. The method according to claim 15, wherein said at least one priority queue corresponds to at least one flow identification queue.

20. The method according to claim 19, wherein a flow identification of said at least one flow identification queue is determined through negotiations between said network device and the remote network device.

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

22. The method according to claim 15, further comprising sending internal messages to all ports of said network device indicating congestion at said at least one priority queue after the step of receiving a virtual channel message.

23. The method according to claim 22, further comprising sending out virtual channel messages indicating congestion by said all ports of said network device.

24. A network device for selectively controlling the flow of data through the network device comprising:

a plurality of ports, with each port of said plurality of ports having a plurality of priority queues means for detecting congestion at at least one priority queue of said plurality of priority queues;

means for sending and receiving a virtual channel message indicating congestion at said at least one priority queue or other priority queue of other network devices connected to said network device;

means for selectively sending data destined for said at least one priority queue or other priority queue based on said virtual channel message; and

means for sending and receiving a virtual channel resume message;

wherein said means for sending and receiving a virtual channel message comprises means for sending and receiving a bitmap showing congestion states of the priority queues.

25. The network device according to claim 24, wherein said means for detecting congestion at at least one priority queue comprises means for determining that said congestion is occurring when a number of packets received at the at least one priority queue exceeds a predetermined value.

26. The network device according to claim 25, wherein said predetermined value is a backpressure limit threshold for said one priority queue.

27. The network device according to claim 24, wherein said congestion states bitmap is a combination of a port bitmap and a priority bitmap.

28. The network device according to claim 24, wherein said plurality of priority queues correspond to a plurality of flow identification queues of data.

29. The network device according to claim 28, wherein flow identifications of said flow identification queues are determined by negotiation means exchanging data between said network device and the other network devices.

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

31. The network device according to claim 24, wherein said means for detecting congestion at at least one priority queue comprises means for detecting congestion at the at least one priority queue of an ingress port of said plurality of ports.

32. The network device according to claim 31, wherein a priority queue memory for each of said plurality of priority queues is set by a backpressure limit threshold.

33. The network device according to claim 24, wherein said means for detecting congestion at one priority queue comprises means for detecting congestion at the at least one priority queue of an egress port of said plurality of ports.

34. The network device according to claim 33, wherein said plurality of priority queues correspond to a plurality of flow identification queues of data.

35. The network device according to claim 34, further comprising calculation means for calculating a flow identification corresponding to one of said flow identification queues once congestion is detected on the egress port.

36. The network device according to claim 33, further comprising means for sending internal messages to all of said plurality of ports indicating congestion at said at least one priority queue when said means for detecting congestion at at least one priority queue detects congestion.

37. The network device according to claim 36, wherein said means for sending and receiving the virtual channel message is configured to send the virtual channel message to other network devices based on internal messages sent by said means for sending internal messages.