Automatic network load balancing using self-replicating resources

• US 20030167295A1
• Filed: 03/01/2002
• Published: 09/04/2003
• Est. Priority Date: 03/01/2002
• Status: Abandoned Application

• Current Assignee: Verity Incorporated (Healthstream Incorporated)
• Original Assignee: Verity Incorporated (Healthstream Incorporated)
• Inventors: Choo, Kiam
• Application Number:
  US10/087,055
• Publication Number:
  US 20030167295A1
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/4868 with creation or replication
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

The present invention provides a method, system and computer program to balance the computational and network load in networked computers using self-replicating programs, referred to as symbionts. The method presented here reduces hotspots by encapsulating a resource in a symbiont, and having a user access that symbiont through programs that host symbionts, referred to as hosts. When a host accesses a symbiont, it may replicate a copy of that symbiont resource on itself or may be redirected to some other replicate of the same symbiont. The host then offers the replicated resource on the network to alleviate the load experienced by the original symbiont'"'"'s computer. If the load on a symbiont falls below a threshold, it is removed from the host on which it was hosted.

Claims

1. A method for serving requests for resources by applications running on a computer, the computer being part of a network of computers, each computer on said network comprising a host program, each said host program comprising a symbiont, each said symbiont encapsulating one data processing resource, said method comprising the steps of:

a. said host receiving a request for said resource from an application running on said host'"'"'s computer;

b. said host contacting said symbiont that encapsulates said resource; and

c. said symbiont either serving said request, or redirecting it to another replicate of itself, or replicating itself onto said host.

2. The method according to claim 1, wherein said host provides information relating to said symbionts available on said network to applications running on said host'"'"'s computer.

3. The method according to claim 1, wherein said host provides information relating to said symbionts available on said host'"'"'s computer to said network.

4. The method according to claim 1, wherein various replicates of said symbiont is connected together, to support a measure of communication among said replicates.

5. The method according to claim 4, wherein said various replicates of said symbiont are connected together in a multiply connected ring.

6. The method according to claim 1 or claim 4, wherein said step of said symbiont either serving said request, or redirecting it to another replicate of itself, or replicating itself onto said host, said step further comprising the steps of:

a. determining load on said symbiont, if load on said symbiont is less than its threshold, I_max, said symbiont serving said request;

b. determining load on said symbiont, if load on said symbiont is more than its threshold, I_max, and if load on all said connected replicates of said symbiont, is also more than their threshold, t, said symbiont replicating itself on said host;

c. determining load on said symbiont, if load on said symbiont is more than its threshold, I_max, and if said host has been redirected more than a predetermined number of times, said symbiont replicating itself on said host; and

d. determining load on said symbiont, if load on said symbiont is more than its threshold, I_max, and if at least one of said connected replicates of said symbiont, has a load less than their threshold, t, one of said connected replicates with load less than its threshold serving said request.

7. The method according to claim 6, wherein said threshold, I_max, of said symbiont, evolves with time according to some probabilistic measure.

8. The method according to claim 6, wherein said threshold, t, of said replicate of said symbiont is less than said threshold, I_max of said symbiont.

9. The method according to claim 6, wherein said threshold, t, of said replicate of said symbiont, evolves with time according to some probabilistic measure.

10. The method according to claim 6, wherein said step of one of said connected replicates with load less than its threshold serving said request, further comprises said replicate with least load serving said request.

11. The method according to claim 6, wherein said step of one of said connected replicates with load less than its threshold serving said request, further comprises said replicate closest to said host serving said request.

12. A system for serving requests for resources by applications running on a computer, the computer being part of a network of computers, each computer on said network comprising a host program, each said host comprising a symbiont, each said symbiont encapsulating one data processing resource, said system comprising:

a. means for said host receiving a request for said resource from an application running on said host'"'"'s computer;

b. means for said host contacting said symbiont that encapsulates said resource; and

c. means for said symbiont handling said request.

13. The system according to claim 12, wherein said host provides information relating to said symbionts available on said network to applications running on said host'"'"'s computer.

14. The system according to claim 12, wherein said host provides information relating to said symbionts available on said host'"'"'s computer to said network.

15. The system according to claim 12, wherein said various replicates of said symbiont are connected together, to support some measure of communication among said replicates.

16. The system according to claim 15, wherein said various replicates of said symbiont are connected together in a multiply connected ring.

17. The system according to claim 12 or claim 15, wherein said means for said symbiont handling said request, further comprises:

a. means for said symbiont serving said request,

b. means for said symbiont replicating itself on said host,

c. means for one of said connected replicates with load less than its threshold serving said request.

18. The system according to claim 17, wherein said means for one of said connected replicates with load less than its threshold serving said request, further comprises means for said replicate with least load serving said request.

19. The system according to claim 17, wherein said means for one of said connected replicates with load less than its threshold serving said request, further comprises means for said replicate closest to said host serving said request.

20. A method for managing hosts and symbionts in a network of computers, each computer on said network comprising a host program, each said host program comprising a symbiont, each said symbiont encapsulating one data processing resource, said method comprising the steps of:

a. initializing a set of hosts and symbionts on said network;

b. adding a new symbiont for an existing resource to said network, whenever there is a need for one;

c. adding a new symbiont for a new resource to said network whenever said new resource is to be added; and

d. deleting said symbiont from said network of computers whenever certain conditions are met.

21. The method according to claim 20, wherein said host provides information relating to said symbionts available on said network to applications running on said host'"'"'s computer.

22. The method according to claim 20, wherein said host provides information relating to said symbionts available on said host'"'"'s computer to said network.

23. The method according to claim 20, wherein various replicates of said symbiont are connected together, to support some measure of communication among said replicates.

24. The method according to claim 23, wherein said various replicates of said symbiont are connected together in a multiply connected ring.

25. The method according to claim 20, wherein said initializing step further comprises the steps of:

a. initializing a host on each computer of said network;

b. encapsulating said resources that are to be initialized in one said symbiont each;

c. marking original copy of each of said symbiont encapsulating said resource, as immortal so that they are always present in said network; and

d. initializing said symbionts on computers in said network, wherein said symbiont runs in said host.

26. The method according to claim 25, wherein a symbiont run in said host.

27. The method according to claim 20 or claim 23, wherein said step of adding a new symbiont for an existing resource to said network, whenever there is a need for one, further comprises the steps of:

a. determining load on said symbiont, if load on said symbiont is more than its threshold, I_max, and if load on all said connected replicates of said symbiont, is also more than their threshold, t, said symbiont replicating itself on said host;

b. determining load on said symbiont, if load on said symbiont is more than its threshold, I_max, and if said host has been redirected more than a predetermined number of times, said symbiont replicating itself on said host; and

c. determining load on said symbiont, in either case, connecting said new symbiont to other said symbionts of said existing resource.

28. The method according to claim 27, wherein said threshold, I_max, of said symbiont, evolves with time according to some probabilistic measure.

29. The method according to claim 27, wherein said threshold, t, of said replicate of said symbiont is less than said threshold, I_max of said symbiont.

30. The method according to claim 27, wherein said threshold, t, of said replicate of said symbiont, evolves with time according to some probabilistic measure.

31. The method according to claim 20, wherein said step of adding a new symbiont for a new resource to said network whenever a new resource is to be added, further comprises the steps of:

a. encapsulating said new resource to be initialized in a new symbiont;

b. marking original copy of said new symbiont encapsulating said new resource, as immortal so that it is always present in said network; and

c. initializing said new symbiont on a computer in said network, wherein said new symbiont runs in said host.

32. The method according to claim 20, wherein said step of deleting said symbiont from said network of computers whenever certain conditions are met, further comprises the steps of:

a. said symbionts checking their loads at regular time intervals; and

b. said symbionts dying if their load is less than a threshold, I_min.

33. The method according to claim 32, wherein said time intervals evolve with time.

34. The method according to claim 32, wherein said threshold, I_min, evolves with time.

35. The method according to claim 32, wherein said symbionts marked immortal are never deleted from said network.

36. A system for managing hosts and symbionts in a network of computers, each computer on said network comprising a host, each said host comprising a symbiont, each said symbiont encapsulating one data processing resource, said system comprising:

a. means for initializing a set of hosts and symbionts on said network;

b. means for adding a new symbiont for an existing resource to said network;

c. means for adding a new symbiont for a new resource to said network; and

d. means for deleting said symbiont from said network of computers.

37. The system according to claim 36, wherein said host provides information relating to said symbionts available on said network to applications running on said host'"'"'s computer.

38. The system according to claim 36, wherein said host provides information relating to said symbionts available on said host'"'"'s computer to said network.

39. The system according to claim 36, wherein various replicates of said symbiont are connected together, to support some measure of communication among said replicates.

40. The system according to claim 39, wherein said various replicates of said symbiont are connected together in a multiply connected ring.

41. The system according to claim 36, wherein said initializing means further comprises:

a. means for initializing a host on each computer of said network;

b. means for encapsulating said resources that are to be initialized in one said symbiont each;

c. means for marking original copy of each of said symbiont encapsulating said resource, as immortal so that they are always present in said network; and

d. means for initializing said symbionts on computers in said network, wherein said symbiont runs in said host.

42. The system according to claim 41, wherein zero or more symbionts run in said host.

43. The system according to claim 36 or claim 39, wherein said means for adding a new symbiont for an existing resource to said network, whenever there is a need for one, further comprises:

a. means for said symbiont replicating itself on said host as a new symbiont; and

b. means for connecting said new symbiont to other said symbionts of said existing resource.

44. The system according to claim 36, wherein said means for adding a new symbiont for a new resource to said network whenever a new resource is to be added, further comprises:

a. means for encapsulating said new resource to be initialized in a new symbiont;

b. means for marking original copy of said new symbiont encapsulating said new resource, as immortal so that it is always present in said network; and

c. means for initializing said new symbiont on a computer in said network, wherein said new symbiont runs in said host.

45. The system according to claim 36, wherein said means for deleting said symbiont from said network of computers whenever certain conditions are met, further comprises:

a. means for said symbionts checking their loads at regular time intervals; and

b. means for said symbionts dying if their load is less than a threshold, I_min.

46. The system according to claim 45, wherein said time intervals evolve with time.

47. The system according to claim 45, wherein said threshold, I_min, evolves with time.

48. The system according to claim 45, wherein said symbionts marked immortal are never deleted from said network.