| 网站首页| |招标公告| |采购公告| |资讯中心| |采购机构| |项目中心| |供应商库| |会员中心| |招标助手| |专家库 |
基于局部性的最少链接算法及其实现原理

来源:中国政府采购招标网 时间:2008/9/22
在负载均衡产品的调度器(Load Balancer)的实现技术中,IP负载均衡技术是效率最高的。这里我们将要介绍的LBLC和LBLCR就是实现IP负载均衡技术的两种方式。

  基于局部性的最少链接调度算法

  这里讲的LBLC,即基于局部性的最少链接调度(Locality-Based Least Connections Scheduling)算法就是针对请求报文的目标IP地址的负载均衡调度。

  这种算法的前提假设是:任意一台服务器都可以处理任一请求。算法的设计目标是在服务器的负载基本平衡情况下,将相同目标IP地址的请求调度到同一台服务器,来提高各台服务器的访问局部性和主存Cache命中率,从而整个集群系统的处理能力。

  LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器超载且有其它服务器处于其一半的工作负载,则用”最少链接”的原则选出一个可用的服务器,将请求发送到该服务器。

  由于在Cache集群中客户请求报文的目标IP地址是变化的,所以此种均衡算法主要应用在Cache集群系统中。

  最少连接数调度算法流程

  假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,

  C(Si)表示服务器Si的当前连接数。ServerNode[dest_ip]是一个关联变量,表示目标IP地址所对应的服务器结点,一般来说它是通过Hash表实现的。WLC(S)表示在集合S中的加权最小连接服务器,即前面的加权最小连接调度。Now为当前系统时间。

      if (ServerNode[dest_ip] is NULL) then { 
  n = WLC(S); 
  if (n is NULL) then return NULL; 
  ServerNode[dest_ip].server = n; 
  } else { 
  n = ServerNode[dest_ip].server; 
  if ((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; 
  ServerNode[dest_ip].server = n; 
  } 
  } 
  ServerNode[dest_ip].lastuse = Now; 
  return n; 


  带复制的基于局部性最少链接调度(LBLCR)

  LBLCR,即Locality-Based Least Connections Scheduling with Replication,也就是带复制的基于局部性最少链接调度。LBLCR算法也是针对目标IP地址的负载均衡,也是主要用于Cache集群系统。

  它与LBLC算法基本相同,唯一的不同之处是它要维护从一个目标IP地址到一个服务器组的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。

  LBLC算法的主要缺点是:对于一个“热门”站点的服务请求,一台Cache服务器可能会忙不过来处理这些请求。这时,LBLC调度算法会从所有的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“热门”站点到这台Cache服务器,很快这台Cache服务器也会超载,就会重复上述过程选出新的Cache服务器。这样,可能会导致该“热门”站点的映像会出现在所有的Cache服务器上,降低了Cache服务器的使用效率。

[打印本页] [关闭窗口]

| 关于我们 | 广告服务 | 展会推荐 | 网站导航 | 友情链接 | 自助友情链接 | 机构文件 | 汇款帐号 | 网站律师 | 联系我们 |
中国政府采购招标网©2000-2023 本站网络实名/中文域名:"中国政府采购招标网.中文网 政府采购网.中文网 招标网.中文网"
本网站域名:www.chinabidding.org.cn 中国政府采购招标网 京ICP备2021005469  京公网安备11010602005260
技术支持:北京中政发科学技术研究中心 政府采购信息服务:政采标讯科技(北京)有限公司 All rights reserved
网站管理:政府采购招标中心 联系电话:010-68282024 83684022 传真:010-83684022 更多联系电话...
标讯接收邮箱:service@gov-cg.org.cn 供应商邮箱:zfcgzb@gov-cg.org.cn