Distributed congestion avoidance in a network switching system

• US 20070248009A1
• Filed: 12/15/2006
• Published: 10/25/2007
• Est. Priority Date: 04/24/2006
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Petersen, Brian A.
• Granted Patent: US 7,733,781 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways

Abstract

According to an example embodiment, a total offered traffic load for a shared resource within a network switching system may be determined, the total offered traffic load may include, for example, a sum of offered traffic loads from one or more active virtual output queues (VOQs) of the network switching system. A capacity of the shared resource within the network switching system may be determined. A transmission rate from one or more of the active VOQs over the shared resource may be adjusted such that the total traffic load from the active VOQs does not exceed the capacity of the shared resource.

Claims

1. A network switching system comprising:

a plurality of ingress devices, each of the ingress devices including a plurality of ports and a plurality of traffic queues to store traffic to be transmitted via one or more shared resources to an egress device of the network switching system;

one or more of the ingress devices configured to exchange traffic queue state information with one or more other ingress devices within the network switching system, one or more of the ingress devices also configured to adjust a transmitted traffic load from one or more of the traffic queues based on the queue state information received from other ingress devices.

2. The network switching system of claim 1 wherein each ingress device operates as an ingress device and an egress device, depending on a direction of traffic transmission.

3. The network switching system of claim 1 wherein the traffic queues comprise virtual output queues.

4. The network switching system of claim 1 and further comprising one or more intermediary devices coupled between the ingress and egress devices, where each ingress or egress device may operate as an ingress device or an egress device depending on traffic direction.

5. The network switching system of claim 4 wherein the intermediary devices comprise one or more of a switch fabric device, a shared memory switch and/or a cross bar switch.

6. The network switching system of claim 1 wherein one or more of the ingress devices are configured to:

determine a total offered traffic load for a shared resource within the network switching system, the total offered traffic load including a sum of offered traffic loads from one or more active traffic queues of the network switching system;

determine a capacity of the shared resource within the network switching system;

adjust a transmission rate from one or more of the active traffic queues over the shared resource such that the total traffic load from the active traffic queues does not exceed the capacity of the shared resource.

7. The network switching system of claim 6 wherein each of the traffic queues comprises a virtual output queue (VOQ), and wherein one or more of the ingress devices being configured to determine a total offered traffic load comprises one or more of the ingress devices being configured to:

exchange queue state messages between network devices of the network switching system to allow one or more of the network devices to determine active and non-active VOQs, each VOQ associated with a destination, and wherein a path from an ingress network device to an egress network device within the network switching system includes one or more resources or segments that may be shared among the VOQs.

8. The network switching system of claim 6 wherein each of the traffic queues comprises a virtual output queue (VOQ), and wherein one or more of the ingress devices being configured to determine a capacity of the shared resource comprises one or more of the ingress devices being configured to:

determine a destination associated with each VOQ;

determine resources for a path between an ingress device and a destination for each VOQ;

determine a resource that is shared among a plurality of the VOQs; and

determine a traffic capacity of the shared resource.

9. The network switching system of claim 6 wherein each of the traffic queues comprises a virtual output queue (VOQ), and wherein one or more of the ingress devices being configured to adjust a transmission rate comprises one or more of the ingress devices being configured to:

adjust a transmission rate from each the VOQs that use the shared resource to be approximately 1/Nth of the capacity of the shared resource based on N active VOQs offering traffic load over the shared resource, the shared resource including a path segment between a VOQ and a destination of the network switching system, the destination including one of an egress network device, an egress port, or a virtual port on an egress network device.

10. A network switching system comprising:

a plurality of network devices;

each network device including a plurality of virtual output queues (VOQs) for storing traffic to be forwarded to a destination;

at least one intermediary device coupled between the network devices;

one or more of the ingress devices being configured to receive queue state messages indicating a state of the VOQs of one or more of the other network devices of the network switching system; and

wherein one or more of the network devices being configured to adjust a transmission rate from the VOQs based on the received queue state information received from one or more other ingress devices.

11. A method comprising:

determining a total offered traffic load for a shared resource within a network switching system, the total offered traffic load including a sum of offered traffic loads from one or more active virtual output queues (VOQs) of the network switching system;

determining a capacity of the shared resource within the network switching system;

adjusting a transmission rate from one or more of the active VOQs over the shared resource such that the total traffic load from the active VOQs does not exceed the capacity of the shared resource.

12. The method of claim 11 wherein the determining a total offered traffic load comprises:

each of a plurality of ingress devices of the network switching system reporting a state of one or more of its VOQs such that one or more ingress devices of the network switching system obtains a global view of a demand or total offered traffic load upon one or more shared resources of the network switching system.

13. The method of claim 12 wherein the ingress devices reporting states of one or more of its VOQs comprises an ingress device sending a queue state message indicating an empty/non-empty status for one or more VOQs.

14. The method of claim 12 wherein the ingress devices reporting states of one or more of its VOQs comprises an ingress device sending a queue state message indicating a level of fullness for one or more VOQs.

15. The method of claim 11 wherein the determining a total offered traffic load comprises:

exchanging queue state messages between network devices of the network switching system to allow one or more of the network devices to determine active and non-active virtual output queues (VOQs), each VOQ associated with a destination, and wherein a path from an ingress network device to an egress network device within the network switching system includes one or more resources or segments that may be shared among the VOQs.

17. The method of claim 11 wherein the adjusting comprises:

adjusting a transmission rate from each of the VOQs that use the shared resource to be approximately a fair share of the capacity of the shared resource based on a number of active VOQs offering traffic load over the shared resource and the capacity of the shared resource, the shared resource including a path segment within a switch fabric of the network switching system.

18. The method of claim 11 wherein the adjusting comprises:

adjusting a transmission rate from each the VOQs to provide an uneven or weighted allocation of bandwidth among the VOQs.

16. The method of claim 111 wherein the determining a capacity of the shared resource within a network switching system comprises:

determining a destination associated with each VOQ;

determining resources for a path between an ingress device and a destination for each VOQ;

determining a resource that is shared among a plurality of the VOQs; and

determining a bit rate capacity of the shared resource.