Load balancing method in a communication network

• US 7,062,556 B1
• Filed: 11/22/1999
• Issued: 06/13/2006
• Est. Priority Date: 11/22/1999
• Status: Expired due to Fees

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Fleming, Philip J., Chen, David T.
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Shingles, Kristie D.
• Application Number:
  US09/447,400
• Time in Patent Office: 2,395 Days
• Field of Search: 709/200, 709/201, 709/203, 709/223, 709/226, 709/228, 709/229
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources

Abstract

A communication system network (500) having a plurality of servers (502-1 through N), each having a load level based on serving a number of clients (501-1 through M), a method includes grouping plurality of servers (502-1 through N) into a plurality of server groups G0 through Gk (503-0 through k) respectively having load levels progressively from a least amount of load level to a most amount of load level, calculating a plurality of time periods T1 through Tk corresponding to the server groups G1 through Gk, assigning load to a server selected from the servers in the server group G0 from an initial time until expiration of the time period T1, after expiration of each of the time periods T1 through Tk measured from the initial time, load assignment takes place by assigning load to a server selected from the servers in the server groups from G0 and and at least one other server group, in server groups G1 through Gk, corresponding to an expiring time period.

Claims

1. In a communication system network having a plurality of servers, each of said plurality of servers having a load level based on serving a number of clients in said communication system network, a method comprising the steps of:

grouping said plurality of servers into a plurality of server groups G0 through Gk, wherein said server groups G0 through Gk respectively have load levels from progressively a least amount of load level to a most amount of load level;

calculating a plurality of time periods T1 through Tk corresponding to said server groups G1 trough Gk;

assigning load to a server selected from servers in said server group G0 from an initial time until expiration of said time period T1;

determining a plurality of other groups of servers, wherein each group of servers of said plurality of other groups of servers comprises said group of servers that includes said server group G0 and further comprises at least one other server group selected from said server groups G1 through Gk; and

assigning load, after expiration of each of said the periods T1 through Tk measured from said initial time, to a server selected from a group of servers of the plurality of other groups of servers, wherein each group of servers of said other groups of servers corresponds to an expiring time period.

2. The method as recited in claim 1 wherein said plurality of time periods T1 through Tk each is based on a difference between load levels of at least two server groups in said plurality of server groups G0 through Gk.

3. The method as recited in claim 1 further comprising the step of:

receiving an update of load level of at least one of said plurality of servers in said plurality of server groups G0 through Gk;

repeating said grouping to produce a new plurality of server groups G0 through Gk based on said update of load level;

repeating said calculating said plurality of time periods to produce a new plurality of time periods T1 through Tk corresponding to said new plurality of server groups G0 through Gk;

resetting said initial time to a reset initial time, and assigning load to a server selected from servers in said new server group G0 from said reset initial time until expiration of said new time period T1;

assigning load, after expiration of each of said new time periods T1 through Tk measured from said reset initial time, to a server selected from servers in a combination of servers including said new server group G0 and at least one other server group, in said new server groups G1 through Gk, corresponding to an expiring time period.

4. The method as recited in claim 1 wherein said grouping of said plurality of server groups G0 through Gk is based on similarity of load levels among said plurality of servers.

5. The method as recited in claim 1 wherein at least one load assignment in said assigning load to a server in said server group G0 and said assigning load to a server selected from a group of servers of the plurality of other groups of servers is performed according to a round robin selection method.

6. The method as recited in claim 1 wherein at least one load assignment in said assigning load to a server in said server group G0 and said assigning load to a server selected from a group of servers of the plurality of other groups of servers is performed according to a random selection method.

7. The method as recited in claim 1 wherein each of said plurality of time periods T1 through Tk is based on load levels of at least two server groups selected from said plurality of server groups G0 through Gk, a request arrival rate and a server service rate.

8. The method as recited in claim 7 wherein said request arrival rate is substituted for an average request arrival rate of said plurality of servers.

9. The method as recited in claim 7 wherein said request arrival rate is substituted for an average request arrival rate of a combination of servers of said plurality of servers.

10. The method as recited in claim 7 wherein said server service rate is substituted for an average service rate of said plurality of servers.

11. The method as recited in claim 7 wherein said server service rate is substituted for an average service rate of a combination of servers of said plurality of servers.

12. In a communication system network having a plurality of servers, each of said plurality of servers having a load level based on serving a number of clients in said communication system network, a method comprising the steps of:

grouping said plurality of servers into a plurality of server groups G0 through G2, wherein server groups G0 through G2 respectively have load levels progressively from a least amount of load level to a most amount of load level;

calculating time periods T1 and T2, wherein said time period T2 is longer than said time period T1;

assigning load to a server selected from a group of servers comprising said server group G0 from an initial time until expiration of said time period T1;

determining another group of servers comprising said group of servers that includes said server group G0 and further comprising said serve group G1;

assigning load to a server selected from said another group of servers after expiration of said time period T1;

determining yet another group of servers comprising said group of servers that includes said another group of servers and further comprising said server group G2; and

assigning load to a server selected from said yet another group of servers after expiration of said time period T2.

13. In a communication system network having a plurality of servers, each of said plurality of servers having a load level based on serving a number of clients in said communication system network, a method comprising the steps of:

grouping said plurality of servers into a plurality of server groups G0 through Gk, wherein said server groups G0 through Gk respectively have load levels progressively from a least amount of load level to a most amount of load level;

calculating a plurality of time periods T1 through Tk;

assigning load to a server selected from servers in said server group G0 from an initial time until expiration of said time period T1;

determining a plurality of other groups of servers, wherein each group of servers of said plurality of other groups of servers comprises said group of servers that includes said server group G0 and further comprises at least one other server group selected from said server groups G1 through Gk; and

assigning load, after expiration of each of said time periods T1 through Tk measured from said initial time, to a server selected from a group of servers of the plurality of other groups of servers.