Network switch load balancing

• US 6,788,692 B1
• Filed: 06/01/1999
• Issued: 09/07/2004
• Est. Priority Date: 05/03/1999
• Status: Expired due to Term

• Current Assignee: Ciena Corporation
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Boudreau, Daniel, Farrell, Bernard, OʼHara, John T., Hannigan, Kerry M., Philippou, James A., Mamros, Shawn, Borden, J. Martin
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US09/323,676
• Time in Patent Office: 1,925 Days
• Field of Search: 370/351, 370/389, 370/400, 370/479, 370/235, 370/354, 370/355, 370/222, 370/228, 370/404, 370/231, 709/105, 709/102, 709/203, 709/224, 709/244, 709/235
• US Class Current: 370/400
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/825 Involving tunnels, e.g. MPLS

Abstract

The present invention is a method and apparatus to balance load in a cluster of switches in a network. The switches include a local switch and one or more remote switches. Messages containing load information of the switches are exchanged among the switches. One of the switches is selected to respond to a connection request to the local switch based on a metric.

Claims

1. A method to balance load in a cluster of switches in a network, the switches including a local switch and one or more remote switches, the method comprising:

exchanging messages among the switches, the messages including an advertise message sent at a refresh interval, the advertise message containing load information of the switches including at least one of a version number, a message type, the refresh interval, an authentication method, a source address, a public address, a checksum, a processor idle time, a free connection, and an authentication data, the exchanging the messages comprising;

receiving the advertise message from a source switch, the advertise message containing the load information of the source switch including a switch attribute, the receiving an advertise message comprising;

listening on a broadcast port, and

processing the advertise message to extract the switch attribute, and storing the switch attribute in a peer table; and

selecting one of the switches in response to a connection request to the local switch based on a metric;

wherein processing the advertise message comprises;

validating the checksum;

authenticating the advertise message using the authentication method and the authentication data;

validating the source address;

validating at least one of the version number, the message type, and the refresh interval;

setting a time-to-live (TTL) value using a predetermined maximum TTL value; and

extracting the switch attribute.

2. The method of claim 1 wherein the switch attribute includes at least one of a state, the TTL value, the processor idle time, and the free connection.

3. The method of claim 2 wherein the free connection includes a number of available sessions corresponding to a connection priority.

4. The method of claim 1 wherein exchanging the messages comprises:

selecting a destination switch from a peer table;

determining the load information of a source switch; and

sending an advertise message from the source switch to the selected destination switch, the advertise message containing the load information.

5. The method of claim 4 wherein the peer table contains a switch attribute of the destination switch.

6. The method of claim 5 wherein the switch attribute includes at least one of a state, a time-to-live (TTL) value, a processor idle time, and a free connection.

7. The method of claim 6 wherein the free connection includes a number of available sessions corresponding to a connection priority.

8. The method of claim 7 wherein selecting a destination switch comprises:

selecting the destination switch if the state of the destination switch indicates the destination switch is in a normal state.

9. The method of claim 8 wherein determining the load information comprises:

determining the processor idle time of the source switch; and

determining the free connection of the source switch.

10. The method of claim 9 wherein determining the load information further comprises:

determining the authentication data of the source switch; and

computing the checksum of the authentication data.

11. The method of claim 9 wherein determining the processor idle time comprises:

obtaining samples of task idle times based on a probabilistic distribution; and

estimating an average of the samples of task idle times based on an autoregressive moving average model, the average corresponding to the processor idle time.

12. The method of claim 11 wherein the probabilistic distribution is a Poisson distribution.

13. The method of claim 11 wherein the autoregressive moving average model is an exponentially weighted moving average.

14. The method of claim 6 further comprises:

updating the TTL value of the destination switch.

15. The method of claim 1 wherein selecting one of the switches comprises:

computing the metric using the free connection and a percentage of the processor idle time for each switch, the free connection including a number of available sessions corresponding to a connection priority of the connection request.

16. The method of claim 15 wherein the selected one of the switches corresponds to a best metric of the computed metrics of the switches.

17. The method of claim 16 wherein the best metric is determined based on at least one of a predetermined local threshold, a redirection overhead, and a remote information reliability.

18. The method of claim 17 further comprises:

accepting the connection request by the local switch if the metric of the local switch exceeds the predetermined local threshold.

19. The method of claim 18 further comprises:

adjusting the metric of the one or more remote switches based on at least one of the redirection overhead and the remote information reliability;

redirecting the connection request to one of the one or more remote switches if the adjusted metric of the one of the one or more remote switches is the highest metric and higher than the metric of the local switch; and

accepting the connection request by the local switch if the metric of the local switch is higher than the highest adjusted metric of the one or more remote switches.

23. The computer program product of claim 1 wherein computer readable program code for exchanging messages comprises:

computer readable program code for selecting a destination switch from a peer table;

computer readable program code for determining the load information of a source switch; and

computer readable program code for sending an advertise message from the source switch to the selected destination switch, the advertise message containing the load information.

24. The computer program product of claim 23 wherein the peer table contains a switch attribute of the destination switch.

25.The computer program product of claim 24 wherein the switch attribute includes at least one of a state, a time-to-live (TTL), value, a processor idle time, and a free connection.

51. The apparatus of claim 1 wherein a switch selector comprises:

a metric generator to compute the metric using the free connection and a percentage of the processor idle time for each switch, the free connection including a number of available sessions corresponding to a connection priority of the connection request, the metric generator generating a local metric corresponding to the local switch and one or more remote metrics corresponding to the one or more remote switches.

20. A computer program product comprising:

a computer usable medium having computer program code embodied therein to balance load in a cluster of switches in a network, the switches including a local switch and one or more remote switches, the computer program product having;

computer readable program code for exchanging messages among the switches, the messages including an advertise message sent at a refresh interval, the advertise message containing load information of the switches including at least one of a version number, a message type, the refresh interval, an authentication method, a source address, a public address, a checksum, a processor idle time, a free connection, and an authentication data, the computer readable program code for exchanging messages comprising;

computer readable program code for receiving the advertise message from a source switch, the advertise message containing the load information of the source switch including a switch attribute, the computer readable program code for receiving the advertise message comprising;

computer readable program code for listening on a broadcast port,

computer readable program code for processing the advertise message to extract the switch attribute, and

computer readable program code for storing the switch attribute in a peer table; and

computer readable program code for selecting one of the switches in response to a connection request to the local switch based on a metric;

wherein the computer readable program code for processing the advertise message comprises;

computer readable program code for validating the checksum;

computer readable program code for authenticating the advertise message using the authentication method and the authentication data;

computer readable program code for validating the source address;

computer readable program code for validating at least one of the version number, the message type, and the refresh interval;

computer readable program code for setting a time-to-live (TTL) value using a predetermined maximum TTL value; and

computer readable program code for extracting the switch attribute.

21. The computer program product of claim 20 wherein the switch attribute includes at least one of a state, the TTL value, the processor idle time, and the free connection.

22. The computer program product of claim 21 wherein the free connection includes a number of available sessions corresponding to a connection priority.

33. The computer program product of claim 20 wherein the computer readable program code for selecting one of the switches comprises:

computer readable program code for computing the metric using the free connection and a percentage of the processor idle time for each switch, the free connection including a number of available sessions corresponding to a connection priority of the connection request.

25. The computer program product of claim 25 wherein the free connection includes a number of available sessions corresponding to a connection priority.

32. The computer program product of claim 25 further comprises:

computer readable program code for updating the TTL value of the destination switch.

26. The computer program product of claim 26 wherein the computer readable program code for selecting the destination switch comprises:

computer readable program code for selecting the destination switch if the state of the destination switch indicates the destination switch is in a normal state.

27. The computer program product of claim 27 wherein the computer readable program code for determining the load information comprises:

computer readable program code for determining the processor idle time of the source switch; and

computer readable program code for determining the free connection of the source switch.

28. The computer program product of claim 28 wherein the computer readable program code for determining the load information further comprises:

computer readable program code for determining the authentication data of the source switch; and

computer readable program code for computing the checksum of the authentication data.

29. The computer program product of claim 28 wherein the computer readable program code for determining the processor idle time comprises:

computer readable program code for obtaining samples of task idle times based on a probabilistic distribution; and

computer readable program code for estimating an average of the samples of task idle times based on an autoregressive moving average model, the average corresponding to the processor idle time.

30. The computer program product of claim 30 wherein the probabilistic distribution is a Poisson distribution.

31. The computer program product of claim 30 wherein the autoregressive moving average model is an exponentially weighted moving average.

34. The computer program product of claim 34 wherein the selected one of the switches corresponds to a best metric of the computed metrics of the switches.

35. A computer data signal embodied in a carrier wave comprising:

a load balancing code segment to balance load in a cluster of switches in a network, the switches including a local switch and one or more remote switches, the load balancing code segment having;

a message exchange code segment for exchanging messages among the switches, the messages including an advertise message sent at a refresh interval, the advertise message containing load information of the switches including at least one of a version number, a message type, the refresh interval, an authentication method, a source address, a public address, a checksum, a processor idle time, a free connection, and an authentication data, the message exchange code segment comprising;

a receive code segment for receiving the advertise message from a source switch, the advertise message containing the load information of the source switch, including a switch attribute, the receive code segment comprising;

a listening code segment for listening on a broadcast port, and

a processing code segment for processing the advertise message to extract the switch attribute, and

a store code segment for storing the switch attribute in a peer table; and

a switch selecting code segment for selecting one of the switches in response to a connection request to the local switch based on a metric;

wherein the processing code segment comprises;

a first validation code segment for validating the checksum;

a first authentication code segment for authenticating the advertise message using the authentication method and the authentication data;

a second validation code segment for validating the source address;

a third validation code segment for validating at least one of the version number, the message type, and the refresh interval;

a setting code segment for setting a time-to-live (TTL) value using a predetermined maximum TTL value; and

an extracting code segment for extracting the switch attribute.

36. The computer data signal of claim 36 wherein the switch attribute includes at least one of a state, the TTL value, the processor idle time, and the free connection.

38. The computer data signal of claim 36 wherein the message exchange code segment comprises:

a peer code segment for selecting a destination switch from a peer table;

a load code segment for determining the load information of a source switch; and

a sender code segment for sending an advertise message from the source switch to the selected destination switch, the advertise message containing the load information.

49. The computer data signal of claim 36 wherein the switch selecting code segment comprises:

a metric code segment for computing the metric using the free connection and a percentage of the processor idle time for each switch, the free connection including a number of available sessions corresponding to a connection priority of the connection request.

37. The computer data signal of claim 37 wherein the free connection includes a number of available sessions corresponding to a connection priority.

39. The computer data signal of claim 39 wherein the peer table contains a switch attribute of the destination switch.

40. The computer data signal of claim 40 wherein the switch attribute includes at least one of a state, a time-to-live (TTL) value, a processor idle time, and a free connection.

41. The computer data signal of claim 41 wherein the free connection includes a number of available sessions corresponding to a connection priority.

48. The computer data signal of claim 41 further comprises:

an update code segment for updating the TTL value of the destination switch.

42. The computer data signal of claim 42 wherein the peer code segment comprises:

a destination code segment for selecting the destination switch if the state of the destination switch indicates the destination switch is in a normal state.

43. The computer data signal of claim 43 wherein the load code segment comprises:

an idle code segment for determining the processor idle time of the source switch; and

a connection code segment for determining the free connection of the source switch.

44. The computer data signal of claim 44 wherein the load code segment further comprises:

a second authentication code segment for determining the authentication data of the source switch; and

a checksum code segment for computing the checksum of the authentication data.

45. The computer data signal of claim 44 wherein the idle code segment comprises:

a sampling code segment for obtaining samples of task idle times based on a probabilistic distribution; and

an averaging code segment for estimating an average of the samples of task idle times based on an autoregressive moving average model, the average corresponding to the processor idle time.

46. The computer data signal of claim 46 wherein the probabilistic distribution is a Poisson distribution.

47. The computer data signal of claim 46 wherein the autoregressive moving average model is an exponentially weighted moving average.

50. The computer data signal of claim 50 wherein the selected one of the switches corresponds to a best metric of the computed metrics of the switches.

52. The apparatus of claim 52 wherein the selected one of the switches corresponds to a best metric of the computed metrics of the switches.

53. The apparatus of claim 53 wherein the best metric is determined based on at least one of a predetermined local threshold, a redirection overhead, and a remote information reliability.

54. The apparatus of claim 54 further comprises:

a local comparator to compare the metric of the local switch and the predetermined local threshold, the local comparator generating a local result.

55. The apparatus of claim 55 further comprises:

one or more metric adjusters coupled to the metric calculator to adjust the metric of the one or more remote switches based on at least one of the redirection overhead and the remote information reliability;

a first metric comparator coupled to the one or more metric adjusters to compare the adjusted metrics of the one of the one or more remote switches, the metric comparator generating a highest adjusted metric from the adjusted metrics;

a second metric comparator coupled to the first metric comparator and the metric calculator to compare the highest adjusted metric and the local metric, the second metric comparator generating a remote result; and

a decision logic coupled to the local comparator and the metric comparator to generate a decision based on the local and remote results, the decision accepting the connection request by the local switch if the local metric is higher than the local threshold or is higher than the highest adjusted metric.

56. A system comprising:

a processor; and

a memory coupled to the processor, the memory including program code to balance load in a cluster of switches including a local switch and at least one remote switch, the program code, when executed by the processor, causing the processor to;

exchange messages among the switches, the messages including an advertise message sent at a refresh interval, the advertise message containing load information of the switches, including at least one of a version number, a message type, the refresh interval, an authentication apparatus, a source address, a public address, a checksum, a processor idle time, a free connection, and an authentication data, the program code causing the processor to exchange messages comprising program code causing the processor to receive the advertise message from a source switch, the advertise message containing the load information of the source switch including a switch attribute; and

program code causing the processor to store the switch attribute in a peer table, the program code causing the processor to receive comprising program code causing the processor to listen on a broadcast port, and process the advertise message to extract the switch attribute; and

select one of the switches in response to a connection request to the local switch based on a metric;

wherein the program code causing the processor to select one of the switches comprises program code causing the processor to validate the checksum, authenticate the advertise message using the authentication method and the authentication data, validate the source address, validate at least one of the version number, the message type, and the refresh interval, set a time-to-live (TTL) value using a predetermined maximum TTL value, and extract the switch attribute.

57. A system comprising:

a plurality of switches including a local switch and a remote switch; and

a load balancer coupled to the plurality of switches, the load balancer including;

a message exchanger to exchange messages including an advertise message sent at a refresh interval, the advertise message containing load information among the plurality of switches including at least one of a version number, a message type, the refresh interval, an authentication apparatus, a source address, a public address, a checksum, a processor idle time, a free connection, and an authentication data, the message exchanger comprising;

a receiver to receive the advertise message from a source switch, the advertise message containing the load information of the source switch including a switch attribute, the receiver comprising a listener to listen on a broadcast port, and a message processor to process the advertise message to extract the switch attribute, and a peer table coupled to the receiver to store the switch attribute; and

a switch selector coupled to the message exchanger to select one of the plurality of switches in response to a connection request to the local switch based on a metric;

wherein the message processor comprises a first validator to validate the checksum, a first authenticator to authenticate the advertise message using the authentication method and the authentication data, a second validator to validate the source address, a third validator to validate at least one of the version number, the message type, and the refresh interval, a setter to set a time-to-live (TTL) value using a predetermined maximum TTL value, and an attribute extractor to extract the switch attribute.

58. An apparatus to balance load in a cluster of switches in a network, the switches including a local switch and one or more remote switches, the apparatus comprising:

a message exchanger to exchange messages among the switches, the messages including an advertise message sent at a refresh interval, the advertise message containing load information of the switches including at least one of a version number, a message type, the refresh interval, an authentication apparatus, a source address, a public address, a checksum, a processor idle time, a free connection, and an authentication data, the message exchanger comprising;

a receiver to receive the advertise message from a source switch, the advertise message containing the load information of the source switch including a switch attribute, the receiver comprising a listener to listen on a broadcast port, and a message processor to process the advertise message to extract the switch attribute, and a peer table coupled to the receiver to store the switch attribute; and

a switch selector coupled to the message exchanger to select one of the switches in response to a connection request to the local switch based on a metric;

wherein the message processor comprises a first validator to validate the checksum, a first authenticator to authenticate the advertise message using the authentication method and the authentication data, a second validator to validate the source address, a third validator to validate at least one of the version number, the message type, and the refresh interval, a setter to set a time-to-live (TTL) value using a predetermined maximum TTL value, and an attribute extractor to extract the switch attribute.