Load balancing in a multiple network environment

• US 5,983,281 A
• Filed: 04/24/1997
• Issued: 11/09/1999
• Est. Priority Date: 04/24/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Norton, Carolyn Haibt, Vashaw, Barton Clark, Ogle, David Mark, Tracey, Karen Marie
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Winder, Patrice L.
• Application Number:
  US08/847,416
• Time in Patent Office: 929 Days
• Field of Search: 709/238, 709/239, 709/240, 709/241, 709/243, 709/244, 709/249, 395/200.56, 395/200.68, 395/200.69, 395/200.7, 395/200.71, 395/675, 370/220, 370/219, 370/400, 370/401
• US Class Current: 709/249
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1036 Load balancing of requests to servers for services different from user content provisioning, e.g. load balancing across domain name servers

Abstract

Methods, systems and computer program products are provided which dynamically balance the load between gateways which provide access between a first computer network and a second computer network. This load balancing includes receiving at a gateway a communication to be transmitted to a second computer network from a source device on the first computer network. The gateway determines, preferably based on an address contained in the communication, through which of the gateways the communication is to be transmitted and then either transmits the communication to the second network or over the first network to the determined gateway. A redirect message may then be sent to the source device to direct subsequent messages to the proper gateway. The gateway determination may be made by dividing a resource identifier into subgroups, summing the subgroups and then dividing the sum by the number of parallel gateways. The remainder may then be used as a gateway identifier.

Claims

1. A method of dynamically balancing a load between a plurality of gateways which provide access between a first computer network and a second computer network, the method comprising:

receiving at a first of the plurality of gateways a communication from a source device on the first computer network, wherein the communication is to be transmitted to the second computer network;

determining through which of the plurality of gateways the communication is to be transmitted to the second computer network so as to balance the load between the plurality of gateways based upon a resource identifier associated with the source device received in the communication from the source device;

transmitting the communication to the second computer network if said determining step determines that the first gateway is to transmit the communication to the second computer network;

transmitting the communication from the first of the plurality of gateways over the first computer network to the one of the plurality of gateways which said determining step determines the communication is to be transmitted if said determining step determines that a gateway other than the first gateway is to transmit the communication to the second computer network.

2. The method according to claim 1 wherein the first computer network is a local area network.

3. The method according to claim 1 wherein the first computer network is a wide area network.

4. The method according to claim 1, further comprising the step of:

transmitting a redirect communication to the source device identifying the one of the plurality of gateways determined by said determining step if said determining step determines that a gateway other than the first gateway is to transmit the communication to the second computer network.

5. The method according to claim 1 wherein said transmitting a redirect communication step comprises the step of transmitting an Internet Control Message Protocol (ICMP) redirect message to the source device.

6. A method of dynamically balancing a load between a plurality of gateways which provide access between a first computer network and a second computer network, the method comprising:

receiving at a first of the plurality of gateways a communication from a source device on the first computer network, wherein the communication is to be transmitted to the second computer network;

determining through which of the plurality of gateways the communication is to be transmitted to the second computer network;

transmitting the communication to the second computer network if said determining step determines that the first gateway is to transmit the communication to the second computer network; and

transmitting the communication over the first computer network to the one of the plurality of gateways which said determining step determines the communication is to be transmitted if said determining step determines that a gateway other than the first gateway is to transmit the communication to the second computer network; and

wherein said determining step comprises the steps of;

splitting a resource identifier of the communication having a plurality of bits into sub-groups of bits based upon the number gateways interconnecting the first computer network and the second computer network;

summing the sub-groups of bits to provide an allocation sum;

dividing the allocation sum by the number of gateways interconnecting the first computer network and the second computer network; and

allocating messages to the plurality of gateways based upon the remainder of said dividing step.

7. The method of claim 6, wherein the resource identifier is a source address of communications received from the first computer network and a destination address for communications received from the second computer network.

8. The method of claim 6, further comprising the step of assigning a unique allocation identifier to each of the plurality of gateways and wherein said step of allocating messages comprises the step of allocating messages to the plurality of gateways based upon the allocation identifier of a gateway and the remainder of said dividing step.

9. The method according to claim 8, wherein said assigning step comprises assigning as the allocation identifier a numeric identifier of between 0 and n=1 where n is the number of gateways interconnecting the first computer network and the second computer network;

and

wherein said allocating step comprises the step of allocating messages to the gateway having an allocation identifier equal to the remainder of said dividing step.

10. The method according to claim 6, wherein said splitting step comprises the step of splitting the resource identifier into sub-groups wherein each sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

11. The method according to claim 6, wherein said splitting step comprises the step of splitting the resource identifier into sub-groups wherein at least one sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

12. The method according to claim 6, further comprising the step of masking the resource identifier prior to said splitting step.

13. A method of allocating network resources among a plurality of gateways interconnecting a first computer network and a second computer network, the method comprising the steps of:

splitting a resource identifier having a plurality of bits into sub-groups of bits based upon the number gateways interconnecting the first computer network and the second computer network;

summing the sub-groups of bits to provide an allocation sum;

dividing the allocation sum by the number of gateways interconnecting the first computer network and the second computer network; and

allocating resources to the plurality of gateways based upon the remainder of said dividing step.

14. The method of claim 13, further comprising the step of assigning a unique allocation identifier to each of the plurality of gateways and wherein said step of allocating resources comprises the step of allocating resources to the plurality of gateways based upon the allocation identifier of a gateway and the remainder of said dividing step.

15. The method according to claim 14, wherein said assigning step comprises assigning as the allocation identifier a numeric identifier of between 0 and n-1 where n is the number of gateways interconnecting the first computer network and the second computer network;

and

wherein said allocating step comprises the step of allocating resources to the gateway having an allocation identifier equal to the remainder of said dividing step.

16. The method according to claim 13, wherein said splitting step comprises the step of splitting the address into sub-groups wherein each sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

17. The method according to claim 13, wherein said splitting step comprises the step of splitting the address into sub-groups wherein at least one sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

18. The method according to claim 13, further comprising the step of masking the resource identifier prior to said splitting step.

19. A system for dynamically balancing a load between a plurality of gateways which provide access between a first computer network and a second computer network, the system comprising:

means for receiving at a first of the plurality of gateways a communication from a source device on the first computer network, wherein the communication is to be transmitted to the second computer network;

means for determining through which of the plurality of gateways the communication is to be transmitted to the second computer network so as to balance the load between the plurality of gateways based upon a resource identifier associated with the source device received in the communication from the source device;

means for transmitting the communication to the second computer network if said means for determining determines that the first gateway is to transmit the communication to the second computer network; and

means for transmitting the communication from the first of the plurality of gateways over the first computer network to the one of the plurality of gateways which said means for determining determines the communication is to be transmitted if said means for determining determines that a gateway other than the first gateway is to transmit the communication to the second computer network.

20. The system according to claim 19 wherein the first computer network is a local area network.

21. The system according to claim 19 wherein the first computer network is a wide area network.

22. The system according to claim 19, further comprising:

means for transmitting a redirect communication to the source device identifying the one of the plurality of gateways determined by said means for determining if said means for determining determines that a gateway other than the first gateway is to transmit the communication to the second computer network.

23. The system according to claim 19 wherein said means for transmitting a redirect communication comprises means for transmitting an Internet Control Message Protocol (ICMP) redirect message to the source device.

24. A system for dynamically balancing a load between a plurality of gateways which provide access between a first computer network and a second computer network, the system comprising:

means for receiving at a first of the plurality of gateways a communication from a source device on the first computer network, wherein the communication is to be transmitted to the second computer network;

means for determining through which of the plurality of gateways the communication is to be transmitted to the second computer network;

means for transmitting the communication to the second computer network if said means for determining determines that the first gateway is to transmit the communication to the second computer network; and

means for transmitting the communication over the first computer network to the one of the plurality of gateways which said means for determining determines the communication is to be transmitted if said means for determining determines that a gateway other than the first gateway is to transmit the communication to the second computer network; and

wherein said means for determining comprises;

means for splitting a resource identifier of the communication having a plurality of bits into sub-groups of bits based upon the number gateways interconnecting the first computer network and the second computer network;

means for summing the sub-groups of bits to provide an allocation sum;

means for dividing the allocation sum by the number of gateways interconnecting the first computer network and the second computer network; and

means for allocating messages to the plurality of gateways based upon the remainder of said means for dividing.

25. The system of claim 24, wherein the resource identifier is a source address of communications received from the first computer network and a destination address for communications received from the second computer network.

26. The system according to claim 24, further comprising means for assigning a unique allocation identifier to each of the plurality of gateways and wherein said means for allocating messages comprises means for allocating messages to the plurality of gateways based upon the allocation identifier of a gateway and the remainder of said means for dividing.

27. The system according to claim 26, wherein said means for assigning comprises means for assigning as the allocation identifier a numeric identifier of between 0 and n-1 where n is the number of gateways interconnecting the first computer network and the second computer network;

and

wherein said means for allocating comprises means for allocating messages to the gateway having an allocation identifier equal to the remainder of said means for dividing.

28. The system according to claim 24, wherein said means for splitting comprises means for splitting the resource identifier into sub-groups wherein each sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

29. The system according to claim 24, wherein said means for splitting comprises means for splitting the resource identifier into sub-groups wherein at least one sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

30. The system according to claim 24, further comprising means for masking the address prior to said splitting step.

31. A system for allocating network resources among a plurality of gateways interconnecting a first computer network and a second computer network, the system comprising:

means for splitting a resource identifier having a plurality of bits into sub-groups of bits based upon the number gateways interconnecting the first computer network and the second computer network;

means for summing the sub-groups of bits to provide an allocation sum;

means for dividing the allocation sum by the number of gateways interconnecting the first computer network and the second computer network; and

means for allocating resources to the plurality of gateways based upon a remainder of said means for dividing.

32. The system according to claim 31, further comprising means for assigning a unique allocation identifier to each of the plurality of gateways and wherein said means for allocating resources comprises means for allocating resources to the plurality of gateways based upon the allocation identifier of a gateway and the remainder of said means for dividing.

33. The system according to claim 32, wherein said means for assigning comprises means for assigning as the allocation identifier a numeric identifier of between 0 and n-1 where n is the number of gateways interconnecting the first computer network and the second computer network;

and

wherein said means for allocating comprises means for allocating resources to the gateway having an allocation identifier equal to the remainder of said means for dividing.

34. The system according to claim 31, wherein said means for splitting comprises means for splitting the address into sub-groups wherein each sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

35. The system according to claim 31, wherein said means for splitting comprises means for splitting the address into sub-groups wherein at least one sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

36. The system according to claim 31, further comprising means for masking the resource identifier prior to said splitting step.

37. A computer program product for dynamically balancing a load between a plurality of gateways which provide access between a first computer network and a second computer network, the computer program product comprising:

a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer-readable program code means for receiving at a first of the plurality of gateways a communication from a source device on the first computer network, wherein the communication is to be transmitted to the second computer network;

computer-readable program code means for determining through which of the plurality of gateways the communication is to be transmitted to the second computer network so as to balance the load between the plurality of gateways based upon a resource identifier associated with the source device received in the communication from the source device;

computer-readable program code means for transmitting the communication to the second computer network if said computer-readable program code means for determining determines that the first gateway is to transmit the communication to the second computer network; and

computer-readable program code means for transmitting the communication from the first of the plurality of gateways over the first computer network to the one of the plurality of gateways which said computer-readable program code means for determining determines the communication is to be transmitted.

38. The computer program product according to claim 37, further comprising:

computer-readable program code means for transmitting a redirect communication to the source device identifying the one of the plurality of gateways determined by said means for determining if said computer-readable program code means for determining determines that a gateway other than the first gateway is to transmit the communication to the second computer network.

39. The computer program product according to claim 37 wherein said computer-readable program code means for transmitting a redirect communication comprises computer-readable program code means for transmitting an Internet Control Message Protocol (ICMP) redirect message to the source device.

40. A computer program product for dynamically balancing a load between a plurality of gateways which provide access between a first computer network and a second computer network, the computer program product comprising:

a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer-readable pro-gram code means for receiving at a first of the plurality of gateways a communication from a source device on the first computer network, wherein the communication is to be transmitted to the second computer network;

computer-readable program code means for determining through which of the plurality of gateways the communication is to be transmitted to the second computer network;

computer-readable program code means for transmitting the communication to the second computer network if said computer-readable program code means for determining determines that the first gateway is to transmit the communication to the second computer network; and

computer-readable program code means for transmitting the communication over the first computer network to the one of the plurality of gateways which said computer-readable program code means for determining determines the communication is to be transmitted; and

wherein said computer-readable program code means for determining comprises;

computer-readable program code means for splitting a resource identifier of the communication having a plurality of bits into sub-groups of bits based upon the number gateways interconnecting the first computer network and the second computer network;

computer-readable program code means for summing the sub-groups of bits to provide an allocation sum;

computer-readable program code means for dividing the allocation sum by the number of gateways interconnecting the first computer network and the second computer network; and

computer-readable program code means for allocating messages to the plurality of gateways based upon the remainder of said computer-readable program code means for dividing.

41. The computer program product of claim 40, wherein the resource identifier is a source address of communications received from the first computer network and a destination address for communications received from the second computer network.

42. The computer program product according to claim 40, further comprising computer-readable program code means for assigning a unique allocation identifier to each of the plurality of gateways and wherein said computer-readable program code means for allocating messages comprises computer-readable program code means for allocating messages to the plurality of gateways based upon the allocation identifier of a gateway and the remainder of said computer-readable program code means for dividing.

43. The computer program product according to claim 42, wherein said computer-readable program code means for assigning comprises computer-readable program code means for assigning as the allocation identifier a numeric identifier of between 0 and n-1 where n is the number of gateways interconnecting the first computer network and the second computer network;

and

wherein said computer-readable program code means for allocating comprises computer-readable program code means for allocating messages to the gateway having an allocation identifier equal to the remainder of said computer-readable program code means for dividing.

44. The computer program product according to claim 40, wherein said computer-readable program code means for splitting comprises computer-readable program code means for splitting the resource identifier into sub-groups wherein each sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

45. The computer program product according to claim 40, wherein said computer-readable program code means for splitting comprises computer-readable program code means for splitting the resource identifier into sub-groups wherein at least one sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

46. The computer program product according to claim 40, further comprising computer-readable program code means for masking the address prior to said splitting step.

47. A computer program product for allocating network resources among a plurality of gateways interconnecting a first computer network and a second computer network, the computer program product comprising:

a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer-readable program code means for splitting a resource identifier having a plurality of bits into sub-groups of bits based upon the number gateways interconnecting the first computer network and the second computer network;

computer-readable program code means for summing the sub-groups of bits to provide an allocation sum;

computer-readable program code means for dividing the allocation sum by the number of gateways interconnecting the first computer network and the second computer network; and

computer-readable program code means for allocating resources to the plurality of gateways based upon a remainder of said computer-readable program code means for dividing.

48. The computer program product according to claim 47, further comprising computer-readable program code means for assigning a unique allocation identifier to each of the plurality of gateways and wherein said computer-readable program code means for allocating resources comprises computer-readable program code means for allocating resources to the plurality of gateways based upon the allocation identifier of a gateway and the remainder of said computer-readable program code means for dividing.

49. The computer program product according to claim 48, wherein said computer-readable program code means for assigning comprises computer-readable program code means for assigning as the allocation identifier a numeric identifier of between 0 and n-1 where n is the number of gateways interconnecting the first computer network and the second computer network;

and

wherein said computer-readable program code means for allocating comprises computer-readable program code means for allocating resources to the gateway having an allocation identifier equal to the remainder of said computer-readable program code means for dividing.

50. The computer program product according to claim 47, wherein said computer-readable program code means for splitting comprises computer-readable program code means for splitting the address into sub-groups wherein each sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

51. The computer program product according to claim 47, wherein said computer-readable program code means for splitting comprises computer-readable program code means for splitting the address into sub-groups wherein at least one sub-group includes k bits where k is the lowest power to which 2 may be raised to result in a value equal to or greater than the number of gateways interconnecting the first computer network and the second computer network.

52. The computer program product according to claim 47, further comprising computer-readable program code means for masking the resource identifier prior to said splitting step.