Method and apparatus for web farm traffic control

• US 7,356,592 B2
• Filed: 01/24/2002
• Issued: 04/08/2008
• Est. Priority Date: 01/24/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wolf, Joel L., Yu, Philip S.
• Primary Examiner(s): Caldwell; Andrew
• Assistant Examiner(s): Meucci; Michael D.
• Application Number:
  US10/057,516
• Publication Number:
  US 20030140143A1
• Time in Patent Office: 2,266 Days
• Field of Search: 709/225, 709/226, 709/241, 709/229, 718/105
• US Class Current: 709/226
• 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 comprising:

providing a web farm comprising a plurality of different websites and a plurality of web servers, wherein each website is assigned to a set of one or more of the web servers;

receiving a customer request for accessing a target website of the web farm;

categorizing the received customer request for the target website as either (i) a shareable customer request which can be processed by a server assigned to another website of the web farm or (ii) an unshareable customer request which can not be processed by a server assigned to another website in the web farm;

if the received customer request for the target website is categorized as a sharable customer request, routing the customer request to a server assigned to another website which can process the received customer request;

if the received customer request for the target website is categorized as an unshareable customer request, routing the customer request to a server specifically assigned to the target website for processing, and

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, wherein,

said Goal procedure is effected by minimizing an objective function measuring expected response time as a function of customer request arrival rate subject to a plurality of constraints including a maximum load due to a plurality of public requests for the target website on the server and a plurality of private requests for the target website on the server.

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

$\sum _{}^{}$

j = 1 N ⁢

R j ⁢

( ∑

i = 1 M ⁢

( x i , j + y i , j ) )

subject to the plurality of constraints

Σ

(x_i,j+y_i,j)ε

{0, . . . , L_j},

$\begin{array}{c}\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>x_{i,j}=c_i,\\ x_{i,j}=0<br><br><br><br>\mathrm{if}<br><br><br><br>a_{i,j}=0,\\ \underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>y_{i,j}=d_i,\mathrm{and}\\ y_{i,j}=0<br><br><br><br>\mathrm{if}<br><br><br><br>b_{i,j}=0,\end{array}$

where M is the number of websites, N is the number of servers, R_j is the expected response time as a function of customer arrival rate at server j, x_i,j is a decision variable representing the number of shareable requests for website i that might be handled by server j, y_i,j is a decision variable representing the hypothetical number of unshareable requests for website i that might be handled by server j, L_j is the maximum acceptable load for server j, c_i is the current number of shareable customer requests from website i, d_i is the current number of unshareable requests from website i, a_i,j is an index indicating if shareable requests from website i may be routed to server j, and b_i,j is an index indicating if unshareable requests from website i may be routed to server j.

3. The method of claim 2 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.

4. 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.

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

6. The method of claim 1 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.

7. The method of claim 6 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 {dot over (L)}_j to minimize the function

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>{\stackrel{.}{R}}_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\right)$

subject to plurality of constraints;

$<br><br>\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>,{\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><br><br>\mathrm{if}<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><br><br>\mathrm{if}<br><br><br><br>b_{i,j}=0,$

where {dot over (x)}_i,j is a decision variable representing a 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 a number of unshareable requests for website i that might be handled by server j, ċ

_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.

8. 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, said method steps comprising:

receiving a customer request for accessing a target website of a web farm having a plurality of different websites and a plurality of web servers, wherein each website is assigned to a set of one or more of the web servers;

categorizing the received customer request for the target website as either (i) a shareable customer request which can be processed by a server assigned to another website of the web farm or (ii) an unshareable customer request which can not be processed by a server assigned to another website in the web farm;

if the received customer request for the target website is categorized as a sharable customer request, routing the received customer request to a server assigned to another website which is can process the received customer request;

if the received customer request for the target website is categorized as an unshareable customer request, routing the received customer request to a server specifically assigned to the target website for processing; and

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, wherein,

said Goal procedure is effected by minimizing an objective function measuring expected response time as a function of customer request arrival rate subject to a plurality of constraints including a maximum load due to a plurality of public requests for the target website on the server and a plurality of private requests for the target website on the server.

9. The program storage device of claim 8 wherein said Goal procedure is effected by minimizing the objective function

$\sum _{}^{}$

j = 1 N ⁢

R j ⁢

( ∑

i = 1 M ⁢

( x i , j + y i , j ) )

subject to the plurality of constraints

Σ

(x_i,j+y_i,j)ε

{0, . . . , L_j},

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>x_{i,j}=c_i,<br><br>x_{i,j}=0<br><br><br><br>\mathrm{if}<br><br><br><br>a_{i,j}=0,<br><br>\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>y_{i,j}=d_i,\mathrm{and}$ $y_{i,j}=0<br><br><br><br>\mathrm{if}<br><br><br><br>b_{i,j}=0,$

where M is the number of websites, N is the number of servers, R_j is the expected response time as a function of customer arrival rate at server j, x_i,j is a decision variable representing a number of shareable requests for website i that might be handled by server j, y_i,j is a decision variable representing a number of unshareable requests for website i that might be handled by server j, L_j is the maximum acceptable load for server j, c_i is the current number of shareable customer requests from website i, d_i is the current number of unshareable requests from website i, a_i,j is an index indicating if shareable requests from website i may be routed to server j, and b_i,j is an index indicating if unshareable requests from website i may be routed to server j.

10. The program storage device of claim 9 further comprising instructions for:

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><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><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.

11. The program storage device of claim 8 further comprising instructions for performing a Static procedure, said Static procedure comprising assigning specific said websites to specific said servers.

12. The program storage device of claim 11 wherein said Static procedure assigns said websites to specific servers based upon forecasted demand for shareable and unsharable customer requests from each said website.

13. The program storage device of claim 8 further comprising instructions for performing 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.

14. The program storage device of claim 13 further comprising instructions for:

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><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><br><br>{\stackrel{.}{R}}_j<br><br>\left(\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\right)$

subject to the plurality of constraints;

$\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br><br><br>\left({\stackrel{.}{x}}_{i,j}+{\stackrel{.}{y}}_{i,j}\right)\in <br><br>\left\{0,<br><br>\mathrm{\dots <br><br>}<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>,<br><br>{\stackrel{.}{x}}_{i,j}=0<br><br><br><br>\mathrm{if}<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>,<br><br>\mathrm{and}$ ${\stackrel{.}{y}}_{i,j}=0<br><br><br><br>\mathrm{if}<br><br><br><br>b_{i,j}=0,$

where {dot over (x)}_i,j is a decision variable representing a 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 number of unshareable requests for website i that might be handled by server j, ċ

_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.

15. A web farm, comprising:

a plurality of web sites each having one or more servers assigned thereto;

means for receiving customer requests from said plurality of websites;

means for processing said customer requests to produce responses;

means for transmitting said responses to said customers;

means for categorizing said customer requests received from said plurality of websites into a plurality of categories, said categories comprising shareable customer requests which can be processed by servers of different websites and unshareable customer requests which can not be processed by servers of different websites;

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;

dispatching said next customer request to said optimal serve;

receiving said customer requests into a queue;

monitoring said customer requests in said queue;

monitoring customer requests currently being processed by said servers;

defining, for each server, a convex increasing function and a revised acceptable load limit; and

invoking said Goal procedure to utilize said convex increasing function and revised acceptable load limit to minimize an objective function measuring expected response time as a function of customer request arrival rate subject to a plurality of constraints including a maximum load for each server due to a number of shareable requests in the queue for said website and a number of unshareable requests for said website.