Locality-Based Least-Connection with Replication Scheduling - Revision history

Wensong at 12:48, 10 December 2005

2005-12-10T12:48:44Z

Wensong at 07:15, 7 August 2005

2005-08-07T07:15:30Z

Wensong at 04:23, 7 August 2005

2005-08-07T04:23:58Z

Wensong at 10:45, 20 July 2005

2005-07-20T10:45:53Z

New page

The locality-based least-connection with replication scheduling algorithm is also for destination IP load balancing. It is usually used in cache cluster. It differs from the LBLC scheduling as follows: the load balancer maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.

[[Category:Job Scheduling Algorithms]]

← Older revision		Revision as of 12:48, 10 December 2005
Line 1:		Line 1:
−	The locality-based least-connection with replication (LBLCR) scheduling algorithm is also for destination IP load balancing. It only differs from the [[Locality-Based Least-Connection Scheduling\|locality-based least-connection (LBLC) scheduling]] as follows: the load balancer maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.	+	The locality-based least-connection with replication (LBLCR) scheduling algorithm is also for destination IP [[load balancing]]. It only differs from the [[Locality-Based Least-Connection Scheduling\|locality-based least-connection (LBLC) scheduling]] as follows: the [[load balancer]] maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.

	The pseudo code of locality-based least-connection with replication scheduling algorithm is as follows:		The pseudo code of locality-based least-connection with replication scheduling algorithm is as follows:

@@ Line 37: / Line 37: @@
   return n;
-The locality-based least-connection with replication (LBLCR) scheduling algorithm is usually used in cache cluster.
+Furthermore, we do garbage collection on the map ServerSet[dest_ip] periodically, in order to collect stale entries. Stale entries is those that have not been used for the specified time, such as 24 hours by default.
 [[Category:Job Scheduling Algorithms]]

← Older revision		Revision as of 04:23, 7 August 2005
Line 1:		Line 1:
−	The locality-based least-connection with replication scheduling algorithm is also for destination IP load balancing. It ~~is usually used in cache cluster. It~~ differs from the LBLC scheduling as follows: the load balancer maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.	+	The locality-based least-connection with replication (LBLCR) scheduling algorithm is also for destination IP load balancing. It only differs from the [[Locality-Based Least-Connection Scheduling\|locality-based least-connection (LBLC) scheduling]] as follows: the load balancer maintains mappings from a target to a set of server nodes that can serve the target. Requests for a target are assigned to the least-connection node in the target's server set. If all the node in the server set are over loaded, it picks up a least-connection node in the cluster and adds it in the sever set for the target. If the server set has not been modified for the specified time, the most loaded node is removed from the server set, in order to avoid high degree of replication.
		+
		+	The pseudo code of locality-based least-connection with replication scheduling algorithm is as follows:
		+	Supposing there is a server set S = {S0, S1, ..., Sn-1},
		+	W(Si) is the weight of server Si;
		+	C(Si) is the current connection number of server Si;
		+	ServerSet[dest_ip] is a map from destination IP address to server set;
		+	WLC(S) is the server of [[Weighted Least-Connection Scheduling\|weighted least connection]] in the server set S;
		+	WGC(S) is the server of weighted greatest connections in the server set S;
		+	Now is the current system time;
		+	ServerSet[dest_ip].lastmod is the last modified time of server set for destination IP;
		+	T is the specified time for adjust server set.
		+
		+	if (ServerSet[dest_ip] is NULL) then {
		+	n = WLC(S);
		+	if (n is NULL) then return NULL;
		+	add n into ServerSet[dest_ip];
		+	} else {
		+	n = WLC(ServerSet[dest_ip]);
		+	if ((n is NULL) OR
		+	(n is dead) OR
		+	(C(n) > W(n) AND
		+	there is a node m with C(m) < W(m)/2))) then {
		+	n = WLC(S);
		+	if (n is NULL) then return NULL;
		+	add n into ServerSet[dest_ip];
		+	} else
		+	if (\|ServerSet[dest_ip]\| > 1 AND
		+	Now - ServerSet[dest_ip].lastmod > T) then {
		+	m = WGC(ServerSet[dest_ip]);
		+	remove m from ServerSet[dest_ip];
		+	}
		+	}
		+	ServerSet[dest_ip].lastuse = Now;
		+	if (ServerSet[dest_ip] changed) then
		+	ServerSet[dest_ip].lastmod = Now;
		+	return n;
		+
		+	The locality-based least-connection with replication (LBLCR) scheduling algorithm is usually used in cache cluster.

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