Method and apparatus for web farm traffic control

• US 20030140143A1
• Filed: 01/24/2002
• Published: 07/24/2003
• Est. Priority Date: 01/24/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wolf, Joel L., Yu, Philip S.
• Granted Patent: US 7,356,592 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• 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/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Disclosed is a method for controlling a web farm having a plurality of websites and servers, the method comprising categorizing customer requests received from said websites into a plurality of categories, said categories comprising a shareable customer requests and unshareable customer requests, routing said shareable customer requests such that any of said servers may process shareable customer requests received from different said websites, and routing said unshareable customer requests from specific said websites only to specific servers to which said specific websites have been assigned.

Claims

1. A method for controlling a web farm having a plurality of websites and servers, the method comprising:

categorizing customer requests received from said websites into a plurality of categories, said categories comprising a shareable customer requests and unshareable customer requests;

routing said shareable customer requests such that any of said servers may process shareable customer requests received from different said websites; and

routing said unshareable customer requests from specific said websites only to specific servers to which said specific websites have been assigned.

2. The method of claim 1 further comprising a Goal procedure, said Goal procedure comprising determining, for each said customer request, an optimal server from among said servers to which each said customer request is to be assigned so as to minimize an average customer response time at any given moment, given said assignment of said websites to said servers and a current customer request load.

3. The method of claim 2 wherein said Goal procedure is effected by minimizing the function

4. The method of claim 3 further comprising

creating and maintaining a directed graph, said directed graph comprising a dummy node and a plurality of server nodes, each said server node corresponding to one of said servers;

designating one of said sever nodes a winning node for which the expression

$R_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\left(x_{i,j}+y_{i,j}+1\right)\right)-R_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\left(x_{i,j}+y_{i,j}\right)\right)$

is minimal; and

choosing a shortest directed path from said dummy node to said winning node.

5. The method of claim 1 further comprising a Static procedure, said Static procedure comprising assigning specific said websites to specific said servers for the purposes of processing unsharable customer requests.

6. The method of claim 5 wherein said Static procedure assigns said websites to specific servers based upon forecasted demand for shareable and unsharable customer requests from each said website.

7. The method of claim 2 further comprising a Dynamic procedure, said Dynamic procedure comprising:

examining the next customer request;

invoking said Goal procedure in order to determine which server is the optimal server to currently process said next customer request; and

dispatching said next customer request to said optimal server.

8. The method of claim 7 further comprising:

receiving said customer requests into a queue; and

wherein said Dynamic procedure further comprises;

monitoring said customer requests in said queue;

monitoring customer requests currently being processed by said servers;

defining, for each j^th server, a function {dot over (R)}_j(z) by setting

{dot over (R)}_j(z)=R_j(z+Σ

({umlaut over (c)}_i,j+{umlaut over (d)}_i,j));

defining, for each j^th server, a revised acceptable load limit {dot over (L)}_j by setting

${\stackrel{.}{L}}_j=L_j-\underset{i-1}{\overset{M}{\sum <br><br>}}<br><br>\left({\stackrel{\mathrm{¨<br><br>}}{c}}_{i,j}+{\stackrel{\mathrm{¨<br><br>}}{d}}_{i,j}\right);<br><br>\mathrm{and}$

invoking said Goal procedure to utilize said {dot over (R)}_j(z) function and revised acceptable load limit L to minimize the function

$\text{\hspace{1em}<br><br>}<br><br>\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>{\stackrel{.}{R}}_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\right)<br><br>\text{\hspace{1em}<br><br>}$$\mathrm{subject}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{constraints}$$\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\stackrel{.}{L}}_j\right\},<br><br>\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>{\stackrel{.}{x}}_{i,j}={\stackrel{.}{c}}_i,<br><br>{\stackrel{.}{x}}_{i,j}=0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_{i,j}=0,<br><br>\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>{\stackrel{.}{y}}_{i,j}={\stackrel{.}{d}}_i,\mathrm{and}$${\stackrel{.}{y}}_{i,j}=0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>b_{i,j}=0,$

where {dot over (x)}_i,j is a decision variable representing the hypothetical number of shareable requests in the queue for website i that might be handled by server j, {dot over (y)}_i,j is a decision variable representing the hypothetical number of unshareable requests for website i that might be handled by server j, {dot over (c)}_i is the current number of shareable customer requests in the queue from website i, {dot over (d)}_i is the current number of unshareable requests in the queue from website i, {umlaut over (c)}_i is the current number of shareable customer requests from website i currently being processed in one of the servers, and {umlaut over (d)}_i is the current number of unshareable requests from website i currently being processed in one of the servers.

9. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for controlling a web farm having a plurality of websites and servers, said method steps comprising:

categorizing customer requests received from said websites into a plurality of categories, said categories comprising a shareable customer requests and unshareable customer requests;

routing said shareable customer requests such that any of said servers may process shareable customer requests received from different said websites; and

routing said unshareable customer requests from specific said websites only to specific servers to which said specific websites have been assigned.

10. The apparatus of claim 9 further comprising a Goal procedure, said Goal procedure comprising determining, for each said customer request, an optimal server from among said servers to which each said customer request is to be assigned so as to minimize an average customer response time at any given moment, given said assignment of said websites to said servers and a current customer request load.

11. The apparatus of claim 10 wherein said Goal procedure is effected by minimizing the function

12. The apparatus of claim 11 further comprising

creating and maintaining a directed graph, said directed graph comprising a dummy node and a plurality of server nodes, each said server node corresponding to one of said servers;

designating one of said sever nodes a winning node for which the expression

$R_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(x_{i,j}+y_{i,j}+1\right)\right)-R_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(x_{i,j}+y_{i,j}\right)\right)$

is minimal; and

choosing a shortest directed path from said dummy node to said winning node.

13. The apparatus of claim 9 further comprising a Static procedure, said Static procedure comprising assigning specific said websites to specific said servers.

14. The apparatus of claim 13 wherein said Static procedure assigns said websites to specific servers based upon forecasted demand for shareable and unsharable customer requests from each said website.

15. The apparatus of claim 10 further comprising a Dynamic procedure, said Dynamic procedure comprising:

examining the next customer request;

invoking said Goal procedure in order to determine which server is the optimal server to currently process said next customer request; and

dispatching said next customer request to said optimal server.

16. The apparatus of claim 15 further comprising:

receiving said customer requests into a queue; and

wherein said Dynamic procedure further comprises;

monitoring said customer requests in said queue;

monitoring customer requests currently being processed by said servers;

defining, for each j^th server, a function {dot over (R)}_j(z) by setting

{dot over (R)}_j(z)=R_j(z+Σ

({umlaut over (c)}_i,j+{umlaut over (d)}_i,j));

defining, for each j^th server, a revised acceptable load limit {dot over (L)}_j by setting

${\stackrel{.}{L}}_j=L_j-\underset{i-1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\stackrel{\mathrm{¨<br><br>}}{c}}_{i,j}+{\stackrel{\mathrm{¨<br><br>}}{d}}_{i,j}\right);<br><br>\mathrm{and}$

invoking said Goal procedure to utilize said {dot over (R)}_j(z) function and revised acceptable load limit {dot over (L)}_j to minimize the function

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\stackrel{.}{R}}_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\right)$$\text{subject <br><br> <br><br>to <br><br> <br><br>the <br><br> <br><br>constraints;<br><br>}$$\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\in <br><br>\left\{0,\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\stackrel{.}{L}}_j\right\},<br><br>\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>{\stackrel{.}{x}}_{i,j}=\stackrel{.}{c_i}<br><br>\text{\hspace{1em}<br><br>},<br><br>{\stackrel{.}{x}}_{i,j}=0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_{i,j}=0,<br><br>\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>{\stackrel{.}{y}}_{i,j}=\stackrel{.}{d_i}<br><br>\text{\hspace{1em}<br><br>},\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$${\stackrel{.}{y}}_{i,j}=0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>b_{i,j}=0,$

where {dot over (x)}_i,j is a decision variable representing the hypothetical number of shareable requests in the queue for website i that might be handled by server j, {dot over (y)}_i,j is a decision variable representing the hypothetical number of unshareable requests for website i that might be handled by server j, {dot over (c)}_i is the current number of shareable customer requests in the queue from website i, {dot over (d)}_i is the current number of unshareable requests in the queue from website i, {umlaut over (c)}_i is the current number of shareable customer requests from website i currently being processed in one of the servers, and {umlaut over (d)}_i is the current number of unshareable requests from website i currently being processed in one of the servers.

17. A web farm, comprising:

means for receiving customer requests from customer;

means for processing said customer requests to produce responses;

means for transmitting said responses to said customers;

means for categorizing said customer requests into shareable customer requests and unshareable customer requests;

a network dispatcher comprising means for executing a Goal procedure, a Static procedure, and a Dynamic procedure;

said Goal procedure comprising determining, for each said customer request, an optimal server from among said servers to which each said customer request is to be assigned so as to minimize an average customer response time at any given moment, given said assignment of said websites to said servers and a current customer request load, wherein said shareable customer requests may be assigned to any said server and wherein said unshareable customer requests may only be assigned to specific servers depending on which said website said unshareable customer request originated;

said Static procedure comprising assigning specific said websites to specific said servers; and

said Dynamic procedure comprising;

examining the next customer request;

invoking said Goal procedure in order to determine which server is the optimal server to currently process said next customer request; and

dispatching said next customer request to said optimal server.