Method of load balancing traffic among routers in a data transmission system

• US 7,260,647 B2
• Filed: 03/26/2003
• Issued: 08/21/2007
• Est. Priority Date: 03/28/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Soler, Catherine, Espieu, Jean-Pierre, Kah, Fabrice, Lund, Arnaud
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): WANG, LIANG CHE A
• Application Number:
  US10/397,777
• Publication Number:
  US 20030200333A1
• Time in Patent Office: 1,609 Days
• Field of Search: 709/238, 709/239, 709/240, 709/241
• US Class Current: 709/240
• 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 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources

Abstract

A method for load balancing traffic among routers in a data transmission system that includes a network, a set of routers, and a plurality of groups of servers. Each group of servers transfers its flow of data to the network through a first router, the address of which is assigned by a routing protocol. The load on the first router is compared periodically with a predetermined high threshold. If the load exceeds the high threshold, the priority of the first router is lowered in order to transfer the flow of data to a second router. If the load on the first router is subsequently found to be less that a predetermined low threshold, the priority of the first router is increased in order to transfer the flow of data from the second router back to the first router.

Claims

1. An automatic method of load balancing traffic among routers in a data transmission system that includes a network, a set of routers, and a plurality of groups of servers, wherein each group of servers transfers its flow of data to the network through a first router the address of which is assigned to said group of servers by a routing protocol, said method comprising the steps of:

periodically finding a load and a variable state on the first router;

comparing the load on the first router to a predetermined high threshold;

if the load on the first router exceeds the predetermined high threshold, assigning to the first router a new priority and a new variable state, wherein the new variable state identifies whether the flow of data has been previously transferred from the first router, so that the flow of data from at least one group of servers transfers from the first router to a second router based on the new variable state; and

if the load on the first router is less than a predetermined low threshold, and if the new variable state indicates that the flow of data from the group of servers has been transferred from the first router to the second router, increasing the priority of the first router to transfer the flow of data from the second router back to the first router.

2. The method of claim 1, wherein the routers all have different priorities, and the priority of the second router is the highest priority of the different priorities that is lower than the priority of the first router.

3. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for load balancing traffic among routers in a data transmission system that includes a network, a set of routers, and a plurality of groups of servers, wherein each group of servers transfers its flow of data to the network through a first router the address of which is assigned to said group of servers by a routing protocol, said method steps comprising:

periodically finding a load and a variable state on the first router;

comparing the load on the first router to a predetermined high threshold;

if the load on the first router exceeds the predetermined high threshold, assigning to the first router a new priority and a new variable state, wherein the new variable state identifies whether the flow of data has been previously transferred from the first router, so that the flow of data from at least one group of servers transfers from the first router to a second router based on the new variable; and

if the load on the first router is less than a predetermined low threshold, and if the new variable state indicates that the flow of data from the group of servers has been transferred from the first router to the second router, increasing the priority of the first router to transfer the flow of data from the second router back to the first router.

4. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for load balancing traffic among routers in a data transmission system that includes a network, a set of routers, and a plurality of groups of servers, wherein each group of servers transfers its flow of data to the network through a first router the address of which is assigned to said group of servers by a routing protocol, said method steps comprising:

periodically finding a load on the first router;

comparing the load on the first router to a predetermined high threshold;

if the load on the first router exceeds the predetermined high threshold, assigning to the first router a new priority and a new variable state, wherein the new variable state identifies whether the flow of data has been previously transferred from the first router, so that the flow of data from at least one group of servers transfers from the first router to a second router based on the new variable, state; and

if the load on the first router is less than a predetermined low threshold, and if the new variable state indicates that the flow of data from the group of servers has been transferred from the first router to the second router, increasing the priority of the first router to transfer the flow of data from the second router back to the first router.