Automatic load balancing in switch fabrics

• US 20020186656A1
• Filed: 12/11/2001
• Published: 12/12/2002
• Est. Priority Date: 05/07/2001
• Status: Active Grant

• Current Assignee: Microsemi Storage Solutions, Inc (Microchip Technology Incorporated)
• Original Assignee: Vitesse Semiconductor Sales Corp. (Microchip Technology Incorporated)
• Inventors: Vu, Chuong D.
• Granted Patent: US 7,161,901 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 49/1576 Crossbar or matrix
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element

Abstract

A load balancing system and method for network nodes is provided. The load balancing system includes crossbar devices, queues to receive data and a load balancer. The load balancer determines the amount of data in each of the queues and sends data to specific crossbar devices based on the amount of data in each queue. The queues include a high priority queue and a number of non-high priority queues.

Claims

1. A load balancing system for network nodes, the load balancing system comprising:

a plurality of crossbar devices;

a plurality of queues configured to receive data; and

a load balancer coupled to the plurality of queues and configured to determine an amount of data in each of the plurality of queues and to send the data to specific ones of the plurality of crossbar devices based on the amount of data in each queue.

2. The load balancing system of claim 1 wherein the plurality of queues comprises a high priority queue and a plurality of non-high priority queues.

3. The load balancing system of claim 2 wherein the load balancer sends data to specific crossbar devices of the plurality of crossbar devices based on an amount of data in the high priority queue relative to an amount of data in each of the plurality of non-high priority queues.

4. The load balancing system of claim 2 wherein the load balancer sends data to specific crossbar devices in a order that is based on one of the amount of data in the high priority queue and an amount of data in each of the plurality of non-high priority queues.

5. The load balancing system of claim 2 wherein the load balancer sends data to specific crossbar devices of the plurality of crossbar devices based on an amount of data in each of the plurality of non-high priority queues relative to an amount of data in the high priority queue.

6. The load balancing system of claim 2 wherein the load balancer sends data to specific crossbar devices in a order based on one of an amount of data in the high priority queue and an amount of data in each of the plurality of non-high priority queues.

7. The load balancing system of claim 1 further comprising a capacity indicator identifying the amount of data in each queue.

8. The load balancing system of claim 7 wherein the load balancer is configured to determine the amount data in each queue based on examining the capacity indicator and to transmit data to the plurality of crossbar devices in a predetermined order based on the examination of the capacity indicator.

9. The load balancing system of claim 7 wherein the capacity indicator further indicates an occupancy level based on the amount of data in each queue.

10. The load balancing system of claim 9 wherein load balancer is configured to transmit data to the plurality of crossbar devices in a predetermined order based on various occupancy levels of each queue as indicated by the capacity indicator.

11. The load balancing system of claim 10 wherein the occupancy levels are high, medium, low and empty.

12. The load balancing system of claim 1 wherein each of the queues are divided into a plurality of portions having a corresponding portion indicator for each portion of the queues to identify that data are in a corresponding portion of a queue.

13. The load balancing system of claim 12 wherein the portion indicators are modifiable to indicate various occupancy levels in the queue.

14. The load balancing system of claim 12 wherein the load balancer is configured to transmit data from the plurality of queues to the plurality of crossbar devices in a predetermined order based on the portion indicators.

15. The load balancing system of claim 2 wherein each of the queues are divided into a first portion, a second portion and a third portion.

16. The load balancing system of claim 15 wherein the data received are placed first in the first portion, when the first portion is full, the received data are placed in the second portion and, when the second portion is full, the received data are placed the third portion of the queue.

17. The load balancing system of claim 15 wherein the load balancer, upon determining that data are in the third portion of the queue of the high priority queue, causes the data in the high priority queue to be transmitted to all the plurality of crossbar devices that are available.

18. The load balancing system of claim 15 wherein the load balancer, upon determining that data are in the first portion of the queue of the high priority queue, causes the data in the third portion of the non-high priority queues to be transmitted to all the plurality of crossbar devices that are available.

19. The load balancing system of claim 15 wherein the load balancer, upon determining that data are only in the non-high priority queues, causes the data in the non-high priority queues to be transmitted to all the plurality of crossbar devices that are available.

20. The load balancing system of claim 15 wherein the load balancer, upon determining that data are only in the high priority queues, causes the data in the high priority queues to be transmitted to all the plurality of crossbar devices that are available.

21. The load balancing system of claim 15 wherein the load balancer, upon determining that data are in one of the first and second portions of the queue of the high priority queue, causes the data in the non-high priority queues to be transmitted to particular predetermined crossbar devices that are available and causes the data in the high priority queue to be transmitted to remaining crossbar devices from the plurality of crossbar devices that are available.

22. The load balancing system of claim 15 further comprising:

a first indicator identifying that data are in the first portion of a queue;

a second indicator identifying that data are in the second portion of a queue; and

a third indicator identifies that data are in the third portion of a queue.

23. The load balancing system of claim 15 wherein the load balancer, upon determining that the third indicator identifies that data are in the third portion of the queue of the high priority queue, causes the data in the non-high priority queues to be transmitted to all the plurality of crossbar devices that are available.

24. The load balancing system of claim 1 wherein the load balancer is configured to detect inoperable crossbar devices.

25. The load balancing system of claim 24 wherein the load balancer in detecting inoperable devices comprises sending a message to the plurality of crossbar devices and receiving a response sent from each of the plurality of crossbar devices that are operating.

26. The load balancing system of claim 24 wherein the load balancer in detecting inoperable devices comprises sending a message to the plurality of crossbar devices and determining if a response sent from each of the plurality of crossbar devices that are operating based on a predetermined time frame.

27. The load balancing system of claim 24 wherein the load balancer is configured to detect additional crossbar devices added to the plurality of crossbar devices.

28. The load balancing system of claim 27 wherein the load balancer in detecting additional crossbar devices comprises sending a data to at least one predetermined location and receiving a response sent from each of the additional crossbar devices that are added.

29. The load balancing system of claim 27 wherein the load balancer in detecting additional crossbar devices comprises receiving a data sent from each of the additional crossbar devices that are added.

30. The load balancing system of claim 25 wherein the predetermined location is an offset from one of the plurality of crossbar devices.

31. The load balancing system of claim 1 further comprising a processor coupled to the load balancer.

32. A load balancing method comprising:

receiving a plurality of data;

storing the plurality of data in a plurality of queues, each data of the plurality of data being placed in a specific queue of the plurality of queues based on a priority associated with each data;

determining occupancy levels in each of the plurality of queues; and

transmitting the data to a plurality of crossbar devices based on the determined occupancy levels in each queue.

33. The load balancing method of claim 32 wherein the plurality of queues comprises a high priority queue and a plurality of non-high priority queues.

34. The load balancing method of claim 33 wherein the occupancy levels in each queue are based on an amount of data in the high priority queue and an amount of data in each of the plurality of non-high priority queues.

35. The load balancing method of claim 33 wherein transmitting the data, the data are transmitted to specific crossbar devices in an order that is based on an occupancy level of the high priority queue and an occupancy level in each of the plurality of non-high priority queues.

36. The load balancing method of claim 32 further comprising dividing the queues into a plurality of portions having a corresponding portion indicator for each portion of the queues to identify that data are in a corresponding portion of a queue.

37. The load balancing method of claim 32 further comprising modifying the portion indicators to indicate various occupancy levels in the queue.

38. The load balancing method of claim 32 wherein transmitting the data, the data are transmitted to specific crossbar devices in an order based on the portion indicators.

39. The load balancing method of claim 33 further comprising:

dividing each of the queues into a first portion, a second portion and a third portion; and

determining if data are in the first, second and third portions of the plurality of queues.

40. The load balancing method of claim 39 wherein the transmitting of the data further comprises transmitting the data in the high priority queue to all the plurality of crossbar devices, upon determining that data are in the third portion of the queue of the high priority queue.

41. The load balancing method of claim 39 wherein the transmitting of the data further comprises transmitting the data in the third portion of the non-high priority queues to all the plurality of crossbar devices, upon determining that data are in the first portion of the queue of the high priority queue.

42. The load balancing method of claim 39 wherein the transmitting of the data further comprises transmitting the data in the non-high priority queues to all the plurality of crossbar devices, upon determining that data are only in the non-high priority queues.

43. The load balancing method of claim 39 wherein the transmitting of the data further comprises transmitting the data in the high priority queues to all the plurality of crossbar devices, upon determining that data are only in the high priority queues.

44. The load balancing method of claim 39 wherein the transmitting of the data further comprises transmitting the data in the non-high priority queues to particular predetermined crossbar devices and transmitting the data in the high priority queue to remaining crossbar devices from the plurality of crossbar devices, upon determining that data are in one of the first and second portions of the queue of the high priority queue.

45. The load balancing method of claim 32 further comprising detecting one of inoperable crossbar devices and operable crossbar devices and transmitting data to the crossbar devices based on the detecting of one of inoperable crossbar devices and operable crossbar devices.

46. The load balancing method of claim 32 further comprising detecting an operational condition of each of the plurality of crossbar devices and transmitting data to the crossbar devices based on the operational condition detected.

47. The load balancing method of claim 32 further comprising detecting additional crossbar devices added to the plurality of crossbar devices and transmitting the data to the detected additional crossbar devices.

48. A load balancing system comprising:

switching element means;

first holding means for receiving and storing high priority data;

second holding means for receiving and storing non-high priority data; and

balancing means for determining an occupancy level of the first and second storing means and sending data to specific switching element means based on the determined occupancy level of the first storing means in relation to the determined occupancy level of the second storing means.