Dynamic Feedback Load Balancing Scheduling - Revision history

Wensong: /* Examples */

2006-08-23T23:32:14Z

‎Examples

Wensong: /* Introduction */

2006-05-28T14:27:30Z

‎Introduction

Wensong: /* Conclusion */

2006-02-25T11:58:52Z

‎Conclusion

Wensong: /* Weight Computation */

2006-02-25T11:51:29Z

‎Weight Computation

Wensong: /* Examples */

2006-02-25T11:49:09Z

‎Examples

Wensong: /* Weight Computation */

2006-02-25T11:45:08Z

‎Weight Computation

Wensong: /* Weight Computation */

2006-02-25T11:37:09Z

‎Weight Computation

Wensong: /* Weight Computation */

2006-02-25T11:06:08Z

‎Weight Computation

Wensong: /* Aggregate Load */

2006-02-25T04:55:35Z

‎Aggregate Load

Wensong: /* Aggregate Load */

2006-02-25T04:11:39Z

‎Aggregate Load

← Older revision		Revision as of 23:32, 23 August 2006
Line 70:		Line 70:

	The server weight adjustion range is [DEFAULT_WEIGHTi, DEFAULT_WEIGHTi * 10], A is DEFAULT_WEIGHTi /2, the threshold of weight adjustion is DEFAULT_WEIGHTi /4. [[Piranha]] processes query server load, compute and adjust server weight every 20 seconds.		The server weight adjustion range is [DEFAULT_WEIGHTi, DEFAULT_WEIGHTi * 10], A is DEFAULT_WEIGHTi /2, the threshold of weight adjustion is DEFAULT_WEIGHTi /4. [[Piranha]] processes query server load, compute and adjust server weight every 20 seconds.
		+
		+	The other real example used in a production environment on JANET web cache cluster is at http://archive.linuxvirtualserver.org/html/lvs-users/2000-02/msg00064.html

	== Conclusion ==		== Conclusion ==

@@ Line 3: / Line 3: @@
 Dynamic feedback load balancing scheduling algorithm considers the real-time loading and response time of each backend server, and adjusts the percentage of forwarded requests among the servers, in order to avoid some servers that may be overloaded still receive a lot of requests. This algorithm can help improve throughput of the whole system.
-The working environment of this algorithm is illustrated in the following figure, there is a Monitor Daemon running on the [[load balancer]], which is to monitor the availability and load information of each server. The Monitor Daemon can compute an aggregated load value based on all the load information for each server, and calculate a new server weight according to the aggregated load value. If the difference of new server weight and old server weight is more than the threshold, the Monitor Daemon adjusts the server weight with the new one in the IPVS inside the kernel. Usually, [[Weighted Round-Robin Scheduling|weighted round-robin scheduling]] or [[Weighted Least-Connection Scheduling|weighted least-connection scheduling]] is used for connection scheduling, because server weight can be adjusted in the weighted algorithms.
+The working environment of this algorithm is illustrated in the following figure, there is a Monitor Daemon running on the [[load balancer]], which is to monitor the availability and load information of each server. The Monitor Daemon can compute an aggregated load value based on all the load information for each server, and calculate a new server weight according to the aggregated load value. If the difference of new server weight and old server weight is more than the threshold, the Monitor Daemon adjusts the server weight with the new one in the [[IPVS]] inside the kernel. Usually, [[Weighted Round-Robin Scheduling|weighted round-robin scheduling]] or [[Weighted Least-Connection Scheduling|weighted least-connection scheduling]] is used for connection scheduling, because server weight can be adjusted in the weighted algorithms.
 [[Image:Load-manager.jpg|center]]

← Older revision		Revision as of 11:58, 25 February 2006
Line 73:		Line 73:
	== Conclusion ==		== Conclusion ==

		+	Since service time of each request varies a lot, the connection scheduling algorithm inside the kernel may cause skew among the servers. Therefore, an dynamic feedback load balancing algorithm is introduced, it combines the weighted connection scheduling algorithms inside the kernel, takes advantage of dynamic feedback load information from servers, and adjusts server weight to control the percentage of request received among servers. The dynamic feedback load balancing algorithm can help avoid load imbalance among servers, improve system utilization, and increase system throughput.

	[[Category:Job Scheduling Algorithms]]		[[Category:Job Scheduling Algorithms]]

@@ Line 51: / Line 51: @@
 The Monitor Daemon does the following things periodially, if the server DEFAULT_WEIGHTi isn't zero, queries all server load metrics, and calculates the aggregate load of this server '''AGGREGATELOADi'''. The following formular is used to calculate the aggregate load:
 <center>
-<math>w_i = \begin{cases} w_i + A * \sqrt[3]{1 - AGGREGATELOAD_i} & w_i \ne 1 \\
+<math>w_i = \begin{cases} w_i + A * \sqrt[3]{1 - AGGREGATELOAD_i} & AGGREGATELOAD_i \ne 1 \\
-w_i & w_i = 1 \end{cases}
+w_i & AGGREGATELOAD_i = 1 \end{cases}
 </math>
 </center>

@@ Line 51: / Line 51: @@
 The Monitor Daemon does the following things periodially, if the server DEFAULT_WEIGHTi isn't zero, queries all server load metrics, and calculates the aggregate load of this server '''AGGREGATELOADi'''. The following formular is used to calculate the aggregate load:
 <center>
-<math>w_i = \begin{cases} w_i + A * \sqrt[3]{1 - AGGREGATELOAD_i} & AGGREGATELOAD_i \ne 1 \\
+<math>w_i = \begin{cases} w_i + A * \sqrt[3]{1 - AGGREGATELOAD_i} & w_i \ne 1 \\
-w_i & AGGREGATELOAD_i = 1 \end{cases}
+w_i & w_i = 1 \end{cases}
 </math>
 </center>
@@ Line 62: / Line 62: @@
 == Examples ==
 == Conclusion ==

← Older revision		Revision as of 11:37, 25 February 2006
Line 50:		Line 50:

	The Monitor Daemon does the following things periodially, if the server DEFAULT_WEIGHTi isn't zero, queries all server load metrics, and calculates the aggregate load of this server '''AGGREGATELOADi'''. The following formular is used to calculate the aggregate load:		The Monitor Daemon does the following things periodially, if the server DEFAULT_WEIGHTi isn't zero, queries all server load metrics, and calculates the aggregate load of this server '''AGGREGATELOADi'''. The following formular is used to calculate the aggregate load:
		+	<center>
		+	<math>w_i = \begin{cases} w_i + A * \sqrt[3]{1 - AGGREGATELOAD_i} & w_i \ne 1 \\
		+	w_i & w_i = 1 \end{cases}
		+	</math>
		+	</center>
		+
		+	in which，1 is the system utilization that we want to achieve, A is an tunable coefficient (its default value is 5). When the aggregate load is 1, the server weight will remain the same; when the aggregate load is larger than 1, the server weight be adjusted to a smaller value; when the aggregate load is less than 1, the server weight be adjusted to a larger value. If the new server weight is out of the range (0, DEFAULT_WEIGHTi * SCALE], weight will not be adjusted.
		+
		+	In real application system, if each server weight is less than its DEFAULT_WEIGHTi, it means that the whole cluster system is overloaded, there is a need to add new servers to take over some load; if each server weight is near DEFAULT_WEIGHTi * SCALE, it means that the whole system is under light load.

	== Examples ==		== Examples ==

← Older revision		Revision as of 11:06, 25 February 2006
Line 47:		Line 47:
	== Weight Computation ==		== Weight Computation ==

		+	When a server is added into cluster system, system administrator can assign the server an initial weight '''DEFAULT_WEIGHTi''', which is an indicator of the server processing capacity. The Monitor Daemon can use DEFAULT_WEIGHTi as reference in adjusting weight over time. In order to prevent server weight from turning into a huge number, we can set weight adjustion range (0, DEFAULT_WEIGHTi * SCALE], in which SCALE can be tuned, its initial value can be 10.
		+
		+	The Monitor Daemon does the following things periodially, if the server DEFAULT_WEIGHTi isn't zero, queries all server load metrics, and calculates the aggregate load of this server '''AGGREGATELOADi'''. The following formular is used to calculate the aggregate load:

	== Examples ==		== Examples ==

@@ Line 32: / Line 32: @@
 The server metric records all kinds of server load information, such as current server CPU usage '''LOADi''', current disk usage '''DISKi''', current memory usage '''MEMORYi''' and current process number '''PROCESSi'''. There are two ways to get those information. One is that all the servers run SNMP（Simple Network Management Protocol） service and the Monitor Daemon running on the load balancer use SNMP to query those information at servers, the other is to run agent at servers to collect load information, and the agents report the information to the Monitor Daemon on the load balancer.
-The reponse metric is the response time of server processing request, which can reflect
+The reponse metric is the response time of server processing request, which can reflect the length of request waiting queue and the processing time of requests. The Monitor Daemon on the load balancer can work as client to access servie and measure response time. For example, the Monitor Daemon can send "GET /" HTTP request to web server, and record the response time '''RESPONSEi''' of server processing this request. If there is no response from server in the specified time interval, the Monitor Daemon can consider that server is temporarily unavailable now, and set the weight of this server zero.
 == Weight Computation ==

← Older revision		Revision as of 04:11, 25 February 2006
Line 31:		Line 31:

	The server metric records all kinds of server load information, such as current server CPU usage '''LOADi''', current disk usage '''DISKi''', current memory usage '''MEMORYi''' and current process number '''PROCESSi'''. There are two ways to get those information. One is that all the servers run SNMP（Simple Network Management Protocol） service and the Monitor Daemon running on the load balancer use SNMP to query those information at servers, the other is to run agent at servers to collect load information, and the agents report the information to the Monitor Daemon on the load balancer.		The server metric records all kinds of server load information, such as current server CPU usage '''LOADi''', current disk usage '''DISKi''', current memory usage '''MEMORYi''' and current process number '''PROCESSi'''. There are two ways to get those information. One is that all the servers run SNMP（Simple Network Management Protocol） service and the Monitor Daemon running on the load balancer use SNMP to query those information at servers, the other is to run agent at servers to collect load information, and the agents report the information to the Monitor Daemon on the load balancer.
		+
		+	The reponse metric is the response time of server processing request, which can reflect

	== Weight Computation ==		== Weight Computation ==