|
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.
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).
Thanks for reading,
Marko Buuri
Description of the WLC scheduling:
http://www.linuxvirtualserver.org/docs/scheduling.html
|
