|
Hello,
On Tue, 6 May 2003, Marko Buuri wrote:
> Hello,
>
> I would like to suggest a new load balancing algorithm for discussion and
> consideration.
>
> LVS's existing greedy "Weighted Least Connected" algorithm goes for an
> example of an individually optimizing strategy. It selects the server for
> every job so that the response time for that particular job will be
> optimized. But studies about load balancing on distributed systems establish
> that individually optimizing load balancing strategies are less than optimal
> on large systems. This is a problem that socially optimizing policies don't
> share. Their strategy can sacrifice the response time for one job in favor
> of the ones that follow. In other words, these algoritms will optimize
> system performance, not response times for individual jobs.
>
> "Weighted Least Connected" algorithm calls for one change: the servers with
> no currently open jobs should be selected first no matter their weight. This
> will minimize the idle time on all servers, and therefore will lead to
> better overall system throughput.
>
> An example where this matters is where an empty server with weight of 1 has
> no jobs (1/1) is compared to a server with weight of 3 and 1 jobs (2/3).
> With the plain "Weighted Least Connected", the latter server is selected as
> 2/3 is less than 1. With the new algorithm, the former server is selected
> and it makes sense from system performance point of view.
>
In the WLC algorithm, a new incoming job will not be counted in the
comparison of jobs/weight. So, in your example, the former server has the
value (0/1) and the latter one has the value (1/3), then the former server
is selected for the new job.
So, in the WLC algorithm, a server with no jobs will always be selected
first if the others have jobs.
> Many studies about these algorithms are available. In those, "Weighted Least
> Connected" is known as Shorted Expected Delay (SED) and the latter as Never
> Queue (NQ).
>
I don't know whether your "Never Queue" scheme will consider the server
weights or not. If not, it is probably similar to the Least-Connection
Scheduling.
Regards,
Wensong
|
