Method and apparatus for balancing the process load on network servers according to network and serve based policies

• US 6,185,619 B1
• Filed: 11/07/1997
• Issued: 02/06/2001
• Est. Priority Date: 12/09/1996
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.), Raytheon BBN Technologies Corp. (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Original Assignee: Genuity Inc. (Lumen Technologies, Inc.), GTE Service Corporation (Verizon Communications Inc.)
• Inventors: Brittain, Jason Alan, Oppleman, Victor Joseph, Pettingell, Brian Everett, Lippard, James Joseph, Vandeventer, Ian Burke, Watson, Brett Dean, Hotz, Steven Michael, Mc Carthy, Nils Herbert, Joffe, Rodney Lance, Dykes, Barry A.
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US08/965,848
• Time in Patent Office: 1,187 Days
• Field of Search: 395/200.68, 395/675, 395/200.53, 395/200.62, 395/200.8, 709/225, 709/226, 709/229, 709/250, 709/232, 709/220, 709/223
• US Class Current: 709/229
• CPC Class Codes: G06F 9/505 considering the load
• 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/101 based on network conditions

Abstract

According to the present invention, a method and system provides the ability to assign requests for data objects made by clients among multiple network servers. The invention provides a distributed computing system and methods to assign user requests to replicated servers contained by the distributed computing system in a manner that attempts to meet the goals of a particular routing policy. Policies may include minimizing the amount of time for the request to be completed.

Claims

1. A system for routing requests for data objects from a plurality of clients comprising:

a plurality of content servers configured to serve said data objects;

a director component for routing said requests for data objects, said director component further comprising;

a server selection component configured to select a content server from said plurality of content servers based upon a policy;

an identification component configured to identify a plurality of routes from a requesting client to said content server;

a determination component configured to determine a time to traverse each of said plurality of routes; and

a route selection component configured to;

select a route from said requesting client to said content server having the shortest time to traverse; and

identify one of a plurality of IP addresses associated with said content server that directs content to the requesting client, from the content server, along the selected route.

2. The system of claim 1 wherein said director component includes

an answer component for answering a request for a data object with a response that redirects a request from one of said plurality of clients to said selected content server along said route.

3. The system of claim 2 wherein said answer component includes a redirection component that uses an HTTP redirect response.

4. The system of claim 1 wherein said determination component includes a measurement component that measures the time to traverse said route using an ICMP echo reply.

5. The system of claim 1 wherein said server selection component includes:

a determination component configured to determine the number of open TCP connections for each content server in said plurality of content servers; and

a selection component configured to select a content server having the least number of open TCP connections.

6. The system of claim 1 wherein said server selection component includes:

a determination component configured to determine the amount of available free RAM for each content server in said plurality of content servers; and

a selection component configured to select a content server having the largest amount of available free RAM.

7. The system of claim 1 wherein said server selection component includes:

a determination component configured to determine the amount of available free SWAP for each content server in said plurality of content servers; and

a selection component configured to select a content server having the largest amount of available free SWAP.

8. The system of claim 1 wherein said server selection component includes:

a determination component configured to determine the amount of CPU idle time for each content server in said plurality of content servers; and

a selection component capable of selecting the content server having the highest amount of CPU idle time.

9. A method for routing requests for data objects from a plurality of clients comprising the steps of:

receiving a request for a data object from one of said plurality of clients;

providing a plurality of content servers capable of serving data objects, wherein each of said plurality of content servers are comprised of a plurality of IP addresses that each route data objects from said content servers along a different path;

determining a best server from said plurality of content servers according to a policy;

identifying a plurality of routes from said client to said best server;

determining a time to traverse each of said plurality of routes;

selecting one of said routes having the shortest time to traverse; and

informing said client of one of said plurality of IP addresses associated with the best server that directs content to the client, from the best server, along said route.

10. The method of claim 9 wherein said informing a particular client further comprises:

answering a request for a data object with a response that causes said particular client to redirect said request to said best server.

11. The method of claim 10 wherein said response that redirects uses an HTTP redirect response.

12. The method of claim 9 wherein determining said best server according to said policy further comprises selecting a least loaded content server from said plurality of content servers.

13. The method of claim 12 wherein determining said best server further comprises:

determining the number of open TCP connections for each content server in said plurality of content servers; and

selecting as the least loaded content server the content server having the least number of open TCP connections.

14. The method of claim 12 wherein determining a best server further comprises:

determining the amount of available free RAM for each content server in said plurality of content servers; and

selecting as the least loaded content server the content server having the largest amount of available free RAM.

15. The method of claim 12 wherein determining said best server further comprises:

determining the amount of available free SWAP for each content server in said plurality of content servers; and

selecting as the least loaded content server the content server having the largest amount of available free SWAP.

16. The method of claim 12 wherein determining said best server further comprises:

determining the amount of CPU idle time for each content server in said plurality of content servers; and

selecting as the least loaded content server the content server having the highest amount of CPU idle time.

17. The method of claim 9 wherein said time to traverse is determined by measuring the time associated with an ICMP echo reply made over said route.

18. A method for routing information from a plurality of clients comprising the steps of:

receiving a request for a data object from one of a plurality of clients;

determining a best server from said plurality of content servers according to a policy associated with a packet networking environment;

determining one of a plurality of routes from said requesting client to said best server, said route having the shortest time to traverse; and

relaying said request back to said client, wherein said request is comprised of one of a plurality of IP addresses associated with said best server that directs content corresponding to the clients request to the client along said route.

19. The method of claim 18 wherein said relaying information from a particular client further comprises:

forwarding said information to said best server using network layer protocols.

20. The method of claim 18 wherein determining a best server further comprises selecting a least loaded content server from said plurality of content servers.

21. The method of claim 18 wherein said determining a route further comprises:

identifying a plurality of routes from said requesting client to said best server;

determining a time to traverse each of said plurality of routes; and

selecting one of said plurality of routes having the shortest time to traverse said route.

22. The method of claim 21 wherein said time to traverse is determined by an ICMP echo reply.

23. The method of claim 18 wherein determining a best server further comprises:

determining the number of open TCP connections for each content server in said plurality of content servers; and

selecting as the best server the content server having the least number of open TCP connections.

24. The method of claim 18 wherein determining a best server further comprises:

determining the amount of available free RAM for each content server in said plurality of content servers; and

selecting as the best server the content server having the largest amount of available free RAM.

25. The method of claim 18 wherein determining a best server further comprises:

determining the amount of available free SWAP for each content server in said plurality of content servers; and

selecting as the best server the content server having the largest amount of available free SWAP.

26. The method of claim 18 wherein determining a best server further comprises:

determining the amount of CPU idle time for each content server in said plurality of content servers; and

selecting as the best server the content server having the highest amount of CPU idle time.

27. A system for routing requests for data objects from a plurality of clients comprising:

plurality of content servers that serve said data objects, each of said plurality of content servers comprising a plurality of IP addresses; and

a director component that identifies a least loaded server based upon a policy that;

selects said least loaded server from one of said plurality of servers;

selects one of a plurality of routes from a requesting client to said least loaded server, wherein said route has the shortest time to traverse; and

identifies an IP address associated with the least loaded server that directs content to the client along said route.

28. The system of claim 27 wherein said director component further includes:

a selection component capable of selecting a server from said plurality of servers based upon said policy; and

an answer component capable of answering a request for a data object by indicating to one of said plurality of clients to redirect the request to said server selected by said selection component.

29. A method of routing requests for data objects from a plurality of clients

comprising the steps of:

providing a plurality of content servers that serve said data objects; and

routing said requests for data objects back to a requesting client for subsequent transmission to one of said plurality of servers, wherein each of said requests is comprised of one of a plurality of IP addresses associated with said content server that directs content corresponding to the client'"'"'s request from said content server along a route having the shortest time to traverse.