Distributed request routing

• US 20060047751A1
• Filed: 06/25/2004
• Published: 03/02/2006
• Est. Priority Date: 06/25/2004
• Status: Active Grant

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson), Toyota Motor Corporation
• Original Assignee: Toyota Motor Corporation
• Inventors: Chen, Chung-Min, Pang, Marcus, Chen, Wai, Ling, Yibei, Cai, Shengwei
• Granted Patent: US 7,620,687 B2
• Time in Patent Office: Days
• US Class Current: 709/205
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A plurality of servers for processing client requests forward the requests among themselves to achieve a balanced load. When a server initially receives a client request, it randomly selects another of the plurality of servers, referred to as a first-chance server, and forwards the request to this server. Upon receiving the request, the first-chance server determines if it is overloaded and if not, processes the request. However, if overloaded, the first-chance server compares its load to the load of one or more predetermined next-neighbor servers. If the next-neighbor server(s) are more loaded than the first-chance server, the first-chance server processes the request. Otherwise, the first-chance server forwards the request to the least loaded next-neighbor server. The next-neighbor receiving the request either processes it directly, or alternatively, based on its current load and that of its next-neighbor server(s), forwards the request to another next-neighbor server for processing.

Claims

1. A method for processing requests such that request processing is load-distributed among a plurality of servers, the method comprising the steps of:

receiving a request at a first server, the request being forwarded at random to the first server by any of the plurality of servers,

if overloaded, comparing a current load of the first server to the current load of a second of the servers wherein the second server is predetermined to the first server, and

if the load of the first server exceeds the load of the second server, forwarding the request to the second server for processing.

2. The method of claim 1 further comprising the step of processing the request if the load of the first server is less than or comparable to the load of the second server.

3. The method of claim 1 further comprising, prior to said comparing step, the step of comparing the current load of the first server to an overload constant to determine if the first server is overloaded.

4. The method of claim 1 further comprising the step of processing the request if not overloaded.

5. The method of claim 1 wherein said first server forwards the request to the second server through the forwarding server from which the request was received.

6. The method of claim 1 further comprising, prior to said receive step, the step of receiving a message from the second server wherein the current load of the second server is piggybacked on the message.

7. The method of claim 1 wherein the plurality of servers are peers within a peer-to-peer network.

8. The method of claim 1 further comprising the steps of:

if the load of the second server exceeds the load of the first server, comparing the current load of the first server to the current load of a third of the servers wherein the third server is predetermined to the first server, and forwarding the request to the third server for processing if the load of the first server exceeds the load of the third server.

9. The method of claim 8 further comprising the step of processing the request if the load of the first server is less than or comparable to the loads of the second and third servers.

10. A method for processing requests such that request processing is load-distributed among a plurality of servers, the method comprising the steps of:

receiving a request at a first-chance server, the request being forwarded at random to the first-chance server by any of the plurality of servers,

if not overloaded, processing the request,

if overloaded, comparing the first-chance server'"'"'s current load to a current load of at least two other servers wherein the at least two other servers are predetermined to the first-chance server, and

if the load of the first-chance server exceeds the load of any of the at least two other servers, forwarding the request to one of the at least two other servers for processing.

11. The method of claim 10 wherein the first-chance server determines if it is overloaded by comparing its current load to an over-load constant

12. The method of claim 10 further comprising the step of processing the request if the first-chance server is overloaded and the load of the first-chance server is comparable to or less than the load of the at least two other servers.

13. The method of claim 10 further comprising the step of receiving messages from the at least two other servers wherein the current loads of the at least two other servers are piggybacked on the messages.

14. A method for processing client requests such that the request processing is load distributed among a plurality of servers, said method comprising the steps of:

receiving a client request at a first server,

randomly selecting a second server from the plurality of servers and forwarding the client request from the first server to the second server,

if the second server is overloaded, comparing the second server'"'"'s current load to a current load of a first neighbor server wherein the first neighbor server is predetermined to the second server, and

if the load of the second server exceeds the load of the first neighbor server, forwarding the client request to the first neighbor server and the first neighbor server processing the client request.

15. The method of claim 14 wherein if the first-chance server is not overloaded, the first-chance server processing the request.

16. The method of claim 14 wherein each of the plurality of servers has a unique predetermined neighbor server.

17. The method of claim 14 wherein said processing step by the first neighbor server further comprising the steps of:

if the first neighbor server is overloaded, comparing the first neighbor server'"'"'s current load to a current load of a second neighbor server, and

if the load of the first neighbor server exceeds the load of the second neighbor server, forwarding the client request to the second neighbor server and the second neighbor server processing the client request.

18. The method of claim 14 wherein if the second server is overloaded and the load of the first neighbor server exceeds the load of the first-chance server, the method further comprising the steps of:

comparing the second server'"'"'s current load to a current load of a second neighbor server wherein the second neighbor server is predetermined to the second server, and

forwarding the client request to the second neighbor server if the load of the second server exceeds the load of the second neighbor server and the second neighbor server processing the client request.