Apparatus and method for controlling data flow in a network switch

• US 7,065,050 B1
• Filed: 06/23/2000
• Issued: 06/20/2006
• Est. Priority Date: 07/08/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Herbst, Joseph
• Primary Examiner(s): LEE, CHI HO A
• Application Number:
  US09/599,544
• Time in Patent Office: 2,188 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/236.1, 370/236.2, 370/351, 370/412
• US Class Current: 370/235
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/827 : Aggregation of resource allocation or reservation requests
• CPC Class Codes: H04L 49/102 : using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/103 : using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/109 : Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: H04L 49/25 : Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3072 : Packet splitting
• CPC Class Codes: H04L 49/3081 : ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/309 : Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 : for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/352 : Gigabit ethernet switching [GBPS]
• CPC Class Codes: H04L 49/45 : Arrangements for providing or supporting expansion
• CPC Class Codes: H04L 49/555 : Error detection
• CPC Class Codes: H04L 49/606 : Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/901 : using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9063 : Intermediate storage in different physical parts of a node or terminal
• CPC Class Codes: H04L 49/9073 : Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 49/9094 : Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/14 : Multichannel or multilink protocols
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 : Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/323 : in the physical layer [OSI layer 1]
• CPC Class Codes: H04L 69/329 : in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections

Abstract

A method and apparatus for controlling data flow in a network switch, wherein the method includes the steps of determining if a quantity of queued data for a port has exceeded a first predetermined threshold, disabling a data flow to the port if the quantity of queued data is determined to have exceeded the first predetermined threshold, and re-enabling the data flow to the port upon satisfying a predetermined spatial requirement and a predetermined temporal requirement. The apparatus includes at least one queue in connection with the at least one data port interface for receiving data transmitted to the at least one data port interface, and a memory management unit in connection with the at least one queue. The memory management unit operates to disable a data flow to a queue when a level of data in the queue reaches a predetermined threshold, and thereafter re-enables data flow to the queue when the level of data in the queue reaches a second predetermined threshold and a predetermined amount of time has passed.

Claims

1. A method for controlling data flow inside a network switch, said method comprising the steps of:

determining if a quantity of queued data for a port, of a plurality of ports of the network switch, has exceeded a first predetermined threshold;

disabling, within the network switch, a data flow to the port from other ports of the plurality of ports if the quantity of queued data is determined to have exceeded the first predetermined threshold; and

re-enabling the data flow to the port from the other ports of the plurality of ports when the port satisfies a predetermined spatial requirement and a predetermined temporal requirement;

wherein the predefined temporal requirement is met when a timer, set during the disabling step, has exceeded a predetermined amount of time.

2. A method for controlling data flow in a network switch as recited in claim 1, wherein the re-enabling data flow step further comprises the steps of:

determining if the quantity of queued data for the port is less than a second predetermined threshold;

determining if a predetermined amount of time has passed, if it is determined that the quantity of queued data for the port is less than the second predetermined threshold; and

re-enabling the data flow if the quantity of queued data for the port is less than the second predetermined threshold and the predetermined amount of time has passed.

3. A method for controlling data flow in a network switch as recited in claim 1, wherein the first predetermined threshold further comprises a high water mark for the port.

4. A method for controlling data flow in a network switch as recited in claim 1, wherein the second predetermined threshold further comprises a low water mark for the port.

5. A method for controlling data flow in a network switch, said method comprising the steps of:

defining a preferred operational range for a port, of a plurality of ports of the network switch;

defining a quasi-congested operational range for the port;

defining a congested operational range for the port;

disabling, within the network switch, a data flow to the port from other ports of the plurality of ports when the port approaches the congested operational range; and

re-enabling the port for receipt of data from other ports of the plurality of ports when the port reaches the preferred operational range and satisfies a predetermined temporal requirement;

wherein the predefined temporal requirement is met when a timer, set during the disabling step, has exceeded a predetermined amount of time.

6. The method for controlling data flow in a port of a network switch as recited in claim 5, wherein the step of defining a preferred operational range further comprises defining the preferred operational range as the range below a predetermined low water mark for the port.

7. The method for controlling data flow in a port of a network switch as recited in claim 5, wherein the step of defining a congested operational range further comprises defining the congested operational range as the range above a predetermined high water mark for the port.

8. The method for controlling data flow in a port of a network switch as recited in claim 5, wherein the step of defining a quasi-congested range further comprises defining the quasi-congested range as the range between a low water mark and a high water mark.

9. The method for controlling data flow in a port of a network switch as recited in claim 5, wherein the step of disabling data flow to the port when the port approaches the congested operational range further comprises the steps of:

determining if the port is operating in the congested operational range for the port; and

disabling data flow to the port if it is determined that the port is operating in the congested operational range for the port.

10. A method for controlling data flow in a network switch, said method comprising the steps of:

defining a preferred operational range for a port, of a plurality of ports of the network switch;

defining a quasi-congested operational range for the port;

defining a congested operational range for the port;

disabling, within the network switch, a data flow to the port from other ports of the plurality of ports when the port approaches the congested operational range; and

re-enabling the port for receipt of data from other ports of the plurality of ports when the port reaches the preferred operational range and satisfies a predetermined temporal requirement;

wherein the step of re-enabling data flow to the port when the port reaches the preferred operational range further comprises the steps of;

determining if the port is operating in the preferred operational range for the port;

determining if a predetermined amount of time has expired; and

re-enabling data flow to the port if it is determined that the port is operating in the preferred operational range for the port and the predetermined amount of time has expired; and

wherein the step of determining if a predetermined amount of time has expired further comprises the steps of;

defining a predetermined amount of time;

starting a timer when the port enters the preferred operational range; and

determining if the timer has exceeded the predetermined amount of time.

11. A method for controlling data flow in a network switch, said method comprising the steps of:

monitoring a quantity of data queued to be transmitted by a port of a plurality of ports of the network switch;

determining if the quantity of data queued has exceeded a high water mark;

disabling, within the network switch, a data flow into a port queue from other ports of the plurality of ports if the quantity of data queued is determined to have exceeded the high water mark;

determining if the quantity of data queued has fallen below a low water mark;

determining if a predetermined amount of time has passed, if the quantity of data queued has fallen below the low water mark; and

re-enabling data flow into the queue from the other ports of the plurality of ports, if it is determined that the quantity of data has fallen below the low water mark and the predetermined amount of time has passed;

wherein the step of determining if the predetermined amount of time has passed comprises setting a timer and determining when the timer has exceeded the predetermined amount of time.

12. An apparatus for controlling data flow in a network switch, said apparatus comprising:

means for determining if a quantity of queued data for a port, of a plurality of ports of the network switch, has exceeded a first predetermined threshold;

means for disabling, within the network switch, a data flow to the port from other ports of the plurality of ports if the quantity of queued data is determined to have exceeded the first predetermined threshold; and

means for re-enabling the data flow to the port from the other ports of the plurality of ports when the port satisfies a predetermined spatial requirement and a predetermined temporal requirement;

wherein means for disabling is configured to determine that the predefined temporal requirement is met when a timer has exceeded a predetermined amount of time.

13. An apparatus for controlling data flow in a network switch as recited in claim 12, wherein said means for determining further comprises a memory management unit.

14. An apparatus for controlling data flow in a network switch as recited in claim 12, wherein said means for determining further comprises a status location budget manager.

15. An apparatus for controlling data flow in a network switch as recited in claim 12, wherein said means for disabling data flow further comprises a status location budget manager.

16. An apparatus for controlling data flow in a network switch as recited in claim 12, wherein said means for re-enabling data flow further comprises a status location budget manager.

17. An apparatus for controlling data flow in a network switch as recited in claim 12, wherein said first predetermined threshold further comprises a high water mark.

18. An apparatus for controlling data flow in a network switch as recited in claim 12, wherein said predetermined spatial requirement further comprises a low water mark.

19. An network switch comprising:

at least one data port interface connected to at least one port, in communication with a plurality of port interfaces of the network switch;

at least one queue in connection with the at least one data port interface for receiving data transmitted to the at least one data port interface from the plurality of port interfaces; and

a memory management unit in connection with the at least one queue,

wherein the memory management unit disables, within the network switch, a data flow to a queue from the plurality of port interfaces when a level of data in the queue reaches a predetermined threshold, and thereafter re-enables data flow to the queue from the plurality of port interfaces when the level of data in the queue reaches a second predetermined threshold and a predetermined amount of time has passed;

wherein the memory management unit is configured to determine that the predetermined amount of time has passed when a timer has exceeded the predetermined amount of time.

20. A network switch as recited in claim 19, wherein said first predetermined threshold further comprises a high water mark.

21. A network switch as recited in claim 19, wherein said second predetermined threshold further comprises a low water mark.

22. A network switch as recited in claim 19, wherein said memory management unit further comprises a status location budget manager.