Method and apparatus for automatic load-balancing on multisegment devices

• US 7,085,234 B2
• Filed: 01/08/2002
• Issued: 08/01/2006
• Est. Priority Date: 10/24/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: McGuire, Robert M., Faulk, Robert L. Jr., Kimball, Karen E.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US10/038,579
• Publication Number:
  US 20020126622A1
• Time in Patent Office: 1,666 Days
• Field of Search: 370/229, 370/230, 370/231, 370/235, 370/236, 370/252, 370/253, 370/389, 370/400, 370/401, 370/407, 370/408, 370/425, 370/428, 370/463, 370/465, 370/468, 709/223, 709/224, 709/225, 709/226, 709/232, 709/234, 709/235, 709/250, 718/105
• US Class Current: 370/235
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0863 by rolling back to previous configuration versions
• CPC Class Codes: H04L 41/0886 Fully automatic configuration
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• 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/13 in a LAN segment, e.g. ring or bus
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

Automatic load-balancing provides a decision-making process that includes intelligent automatic detection of when a given load-balancing activation currently would not be beneficial, thereby keeping the user'"'"'s network from being unnecessarily disturbed when no real benefit would be gained; a process to undo a prior load-balancing that can be activated when users have accidentally selected a feature which could substantially change their network configurations; and an extensive intelligent port-distribution algorithm that improves the network load by moving the right ports to new segments.

Claims

1. An automatic load-balancing apparatus for a segmented electronic network, comprising:

an intelligent port-distribution mechanism that moves ports to new segments to accomplish load-balancing; and

a detector that determines when load-balancing would not be beneficial by weighing potential benefit of an action against its consequences.

2. The apparatus of claim 1, said detector inhibiting load-balancing when a current load distribution is acceptable or when current network resource impact is so low that no real problems exist.

3. The apparatus of claim 2, wherein said detector makes an intelligent decision for a user while preventing needless network disruption.

4. The apparatus of claim 1, further comprising:

means for determining which ports are to be moved.

5. The apparatus of claim 1, wherein said apparatus is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

6. The apparatus of claim 1, wherein said apparatus is adapted for operation with an external packet-forwarding device.

7. The apparatus of claim 1, wherein said apparatus is adapted for operation without special knowledge by a user of said apparatus, the apparatus environment, or electronic networks in general.

8. The apparatus of claim 1, wherein at least a portion of said mechanism is adapted to reside remote from said apparatus within said network at a management location.

9. An automatic load-balancing apparatus for a segmented electronic network, comprising:

an intelligent port-distribution mechanism that moves ports to new segments to accomplish load-balancing while minimizing the unnecessary moving of ports by keeping as many ports as possible on previous segments; and

an undo mechanism for undoing a prior load-balancing.

10. The apparatus of claim 9, wherein said undo mechanism takes information stored during a prior load-balancing activation and uses it to return ports to a previous configuration.

11. The apparatus of claim 10, wherein no action is taken by said undo mechanism on devices that were not known at the time of said prior load-balancing.

12. The apparatus of claim 10, wherein said undo mechanism provides one or more levels of undo.

13. The apparatus of claim 10, further comprising:

a detector for intelligent automatic determination of when a given load-balancing activation currently would not be beneficial.

14. The apparatus of claim 13, said detector inhibiting load-balancing when a current load distribution is acceptable or when current network resource impact is so low that no real problems exist.

15. The apparatus of claim 14, wherein said detector weighs potential benefit of an action against its consequences, and makes an intelligent decision for a user while preventing needless network disruption.

16. The apparatus of claim 9, further comprising:

means for determining which ports are to be moved.

17. The apparatus of claim 9, wherein said apparatus is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

18. The apparatus of claim 9, wherein said apparatus is adapted for operation with an external packet-forwarding device.

19. The apparatus of claim 9, wherein said apparatus is adapted for operation without special knowledge by a user of said apparatus, the apparatus environment, or electronic networks in general.

20. The apparatus of claim 9, wherein at least a portion of said mechanism is adapted to reside remote from said apparatus within said network at a management location.

21. An automatic load-balancing apparatus for a segmented electronic network, comprising:

an intelligent port-distribution mechanism that moves ports to new segments to accomplish load-balancing, wherein the mechanism weighs potential benefit of an action against its consequences.

22. The apparatus of claim 21, wherein said mechanism first collects a snapshot of information about all network ports to be considered for redistribution.

23. The apparatus of claim 22, wherein said snapshot further comprises any of the following:

a management repeater port identification value;

a management repeater previous segment identification value; and

an amount of port network resource impact since power-up or last load-balancing activation.

24. The apparatus of claim 22, wherein said mechanism makes an intelligent decision for a user while preventing needless network disruption.

25. The apparatus of claim 22, wherein said mechanism keeps as many ports as possible on a previous segment while still obtaining a good overall load-distribution.

26. The apparatus of claim 22, wherein said mechanism detects when further changes in port-to-segment assignments is not of benefit.

27. The apparatus of claim 22, wherein said mechanism finds a replacement port-segment assignment in range of, and uses in place of, a pairing that would be chosen by a basic “

bin-packing”

selection criteria for port-segment assignment.

28. The apparatus of claim 27, wherein an assignment is in range when an alternate port or alternate segment has a current decision-trigger value that is a deviation value distance from a candidate port or target segment value.

29. The apparatus of claim 28, wherein said deviation value comprises one or more of the following:

a fixed value;

a fixed percentage;

a candidate port percentage of total decision criteria value on all segments;

an individual port decision criteria value;

or

a segment total assigned decision criteria value.

30. The apparatus of claim 21, further comprising:

means for determining which ports are to be moved.

31. The apparatus of claim 21, wherein said apparatus is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

32. The apparatus of claim 21, wherein said apparatus is adapted for operation with an external packet-forwarding device.

33. The apparatus of claim 21, wherein said apparatus is adapted for operation without special knowledge by a user of said apparatus, the apparatus environment, or electronic networks in general.

34. The apparatus of claim 21, wherein at least a portion of said mechanism is adapted to reside remote from said apparatus within said network at a management location.

35. An automatic load-balancing method for a segmented electronic network, comprising the steps of:

providing an intelligent port-distribution mechanism that moves ports to new segments to accomplish load-balancing; and

determining when load-balancing would not be beneficial by weighing potential benefit of an action against its consequences.

36. The method of claim 35, further comprising the step of:

inhibiting load-balancing when a current load distribution is acceptable or when current network resource impact is so low that no real problems exist.

37. The method of claim 36, further comprising

making an intelligent decision for a user while preventing needless network disruption.

38. The method of claim 35, further comprising the step of:

determining which ports are to be moved.

39. The method of claim 35, wherein said method is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

40. The method of claim 35, wherein said method is adapted for operation with an external packet-forwarding device.

41. The method of claim 35, wherein said method is adapted for operation without special knowledge by a user of said method, the method environment, or electronic networks in general.

42. The method of claim 35, wherein at least a portion of said mechanism is adapted to reside remote from devices upon which said method operates within said network at a management location.

43. An automatic load-balancing method for a segmented electronic network, comprising the steps of:

providing an intelligent port-distribution mechanism that moves ports to new segments to accomplish load-balancing while minimizing the unnecessary moving of ports by keeping as many ports as possible on previous segments; and

providing a mechanism for undoing a prior load-balancing.

44. The method of claim 43, further comprising the steps of:

taking information stored during a prior load-balancing activation; and

using such information to return ports to a previous configuration.

45. The method of claim 44, wherein no action is taken by said undo mechanism on devices that were not known at the time of said prior load-balancing.

46. The method of claim 44, wherein said undo mechanism provides one or more levels of undo.

47. The method of claim 44, further comprising the step of:

determining when a given load-balancing activation currently would not be beneficial.

48. The method of claim 47, further comprising the step of:

inhibiting load-balancing when a current load distribution is acceptable or when current network resource impact is so low that no real problems exist.

49. The method of claim 48, further comprising the steps of:

weighing potential benefit of an action against its consequences; and

making an intelligent decision for a user while preventing needless network disruption.

50. The method of claim 43, further comprising the step of:

determining which ports are to be moved.

51. The method of claim 43, wherein said method is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

52. The method of claim 43, wherein said method is adapted for operation with an external packet-forwarding device.

53. The method of claim 43, wherein said method is adapted for operation without special knowledge by a user of said method, the method environment, or electronic networks in general.

54. The method of claim 43, wherein at least a portion of said mechanism is adapted to reside remote from devices upon which said method operates within said network at a management location.

55. An automatic load-balancing method for a segmented electronic network, comprising the steps of:

providing an intelligent port-distribution mechanism; and

moving, using the port-distribution mechanism, ports to new segments to accomplish load-balancing, wherein the mechanism weighs potential benefit of an action against its consequences.

56. The method of claim 55, further comprising the step of:

collecting a snapshot of information about all network ports to be considered for redistribution.

57. The method of claim 56, wherein said snapshot comprises any of the following:

a management repeater port identification value;

a management repeater previous segment identification value; and

an amount of port network resource impact since power-up or last load-balancing activation.

58. The method of claim 55, further comprising

making an intelligent decision for a user while preventing needless network disruption.

59. The method of claim 55, further comprising the step of:

keeping as many ports as possible on a previous segment while still obtaining a good overall load-distribution.

60. The method of claim 55, further comprising the step of:

detecting when further changes in port-to-segment assignments is not of benefit.

61. The method of claim 55, further comprising the step of:

finding a replacement port-segment assignment in range of, and using in place of, a pairing arising from basic selection criteria for port-segment assignment.

62. The method of claim 61, further comprising the step of:

determining that an assignment is in range when an alternate port or alternate segment has a current decision-trigger value that is a deviation-value distance from a candidate port or target segment value.

63. The method of claim 62, wherein said deviation-value comprises one or more of the following:

a fixed value;

a fixed percentage;

a candidate port percentage of total decision criteria value on all segments;

an individual port decision criteria value;

or

a segment total assigned decision criteria value.

64. The method of claim 55, further comprising the step of:

determining which ports are to be moved.

65. The method of claim 55, wherein said method is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

66. The method of claim 55, wherein said method is adapted for operation with an external packet-forwarding device.

67. The method of claim 55, wherein said method is adapted for operation without special knowledge by a user of said method, the method environment, or electronic networks in general.

68. The method of claim 55, wherein at least a portion of said mechanism is adapted to reside remote from devices upon which said method operates within said network at a management location.

69. An intelligent port-distribution method that moves ports to new segments to accomplish load-balancing in a segmented electronic network, comprising the steps of:

collecting a snapshot of information about all network ports to be considered for redistribution;

sorting said ports in descending order of network resource impact value;

finding the next candidate port which is the next port among said sorted ports that has not already been assigned;

sorting segments in ascending order of current total of network resource impact of all ports placed on them;

finding the first segment with a least current network resource impact total that is fully qualified as the target segment for a candidate port;

checking if said candidate port was previously on the target segment and, if so,

assigning said candidate port back to that same segment; and

processing any further ports.

70. The method of claim 69, further comprising the steps of:

checking whether a candidate port decision criteria value is below a predetermined low threshold value and, if so,

checking whether a total network resource impact of all remaining unplaced ports that previously were on said candidate port'"'"'s same segment is below a maximum acceptable contribution level threshold and, if so, then

determining that further changes in port-to-segment assignments is not of sufficient benefit;

assigning said candidate port and all of said other ports back to that previous segment; and

continuing processing said ports on other segments and, if not,

continuing processing said candidate port.

71. The method of claim 70, further comprising the steps of:

checking whether an alternate segment exists for said candidate port and, if the segment that said candidate port was previously on is fully qualified with regard to said candidate port and is in range of said target segment, then determining that an alternate segment exists;

assigning said candidate port to said alternate segment;

processing any further ports; and

using said target segment if no exception is true.

72. The method of claim 71, further comprising the steps of:

looking for an alternate port to assign to said target segment in place of said candidate port;

proceeding in order through said list of sorted ports;

checking whether there is a port that is not already placed, but that is in range, and that previously resided on said target segment, which can be used as an alternate port, and for which said target segment is fully qualified for placement and, if an alternate port exists within range;

assigning said port to said target segment instead of said candidate port; and

processing any further ports, and if no alternate port exists within range,

assigning said candidate port to said target segment; and

processing any further ports.

73. The method of claim 69, further comprising the step of:

determining which ports are to be moved.

74. The method of claim 69, wherein said method is adapted for operation with a packet-forwarding device without requiring an interface to internal packet-forwarding support hardware.

75. The method of claim 69, wherein said method is adapted for operation with an external packet-forwarding device.

76. The method of claim 69, wherein said method is adapted for operation without special knowledge by a user of said method, the method environment, or electronic networks in general.

77. The method of claim 69, wherein at least a portion of said mechanism is adapted to reside remote from devices upon which said method operates within said network at a management location.

78. A method for moving ports to new segments in a network for load balancing, comprising:

collecting information about the ports and segments in the network, the information including network resource impact value; and

assigning ports to new segments based on the information while minimizing the unnecessary moving of ports by keeping as many ports as possible on previous segments.

79. The method of claim 78, wherein collecting information about the ports and segments includes collecting network resource impact values for the ports.

80. The method of claim 78, wherein collecting information about the ports and segments includes collecting total network resource impact values for segments.

81. The method of claim 78, wherein assigning ports to new segments includes assigning ports based on past history of the ports.

82. The method of claim 78, further comprising:

determining which of the ports are to be moved.

83. The method of claim 78, further comprising:

determining when load balancing would not be beneficial.

84. The method of claim 78, further comprising:

undoing a previous assignment of the ports to new segments.