3 常用负载均衡算法

影响负载均衡的因素有三个，分别是算法、网络拓扑以及负载均衡的粒度[5]，下文对负载均衡算法进行研究。负载均衡算法包括两种：静态负载均衡和动态负载均衡。

3.1 静态负载均衡算法

静态负载均衡不管各个成员服务器运行时刻的负载情况，而只是根据预先设定的分配方案对用户的请求进行分配。轮叫调度算法（Round Robin）也是一种比较常见的静态算法，即把客户请求依次分派给各个成员服务器，例如，把第i个请求分配给服务器Sk，k = i mod N。该算法的优点是其简洁性，无需记录当前所有连接的状态，是一种无状态调度。轮叫调度算法假设所有服务器处理性能均相同，相对简单，但是不适用于服务器组中处理性能不一的情况，而且当请求服务时间变化较大时，容易导致服务器间的负载不平衡[6]。对于异构系统，也可以采用上述类似的按处理能力比例分配的处理方法[7]。

3.2 动态负载均衡算法

由于影响客户访问频率的因素很多，且难以预测，因此静态调度往往不能令人满意。此时可以根据各个服务器上任务执行实际状态的变化，随时动态地调整任务分配，使用系统状态信息进行负载调整。目前已提出了很多动态算法，如Pick-K算法，Basic LI和Aggressive LI算法[8]，Pick-KX算法[9]等。

3.2.1 典型动态负载分配算法所遵循的策略

1) 启动策略

发送者启动：该算法由发送者触发负载分配。当系统中的某个处理机结点的负载W(i)>W1*，即为重载结点，称该结点为发送者。它主动寻找一个负载轻的处理机结点来接收自己的一部分负载。显然当整个系统的平均负载为轻载时，发送者能够容易找到负载的接收者，因此系统比较稳定。但当其为重载时，该系统中的大部分处理机结点的负载都处于重载，所以很难找到负载轻的处理机结点，反而使发送者结点的负载更加恶化，严重影响系统性能。

接收者启动：该算法是由接收者触发负载分配。当系统中的某个处理机结点的负载W(i)<W2*，轻载时，即称该结点为接收者。它必须主动寻找发送者，以便接收一部分负载。当整个系统的平均负载处于重载时，接收者可以容易地找到一个发送者，这种情况下，它优于发送者启动算法。接收者启动算法的主要缺点是，当系统整体负载相对较少时，过多的任务请求占用了带宽，延迟了重服务器的任务执行。

对称启动：对称启动算法是结合了接收者启动算法和发送者启动算法两者的优点。当整个系统平均负载处于轻载时，用发送者启动算法，负载重的处理机结点很容易找到可以接收其负载的处理机结点；当处于重载时，使用接收者启动算法较合适，此时负载较轻的处理机结点很容易找到负载重的处理机结点，以便接收一部分负载，这样该算法就避免了接收者和发送者启动算法的缺点。

自适应算法：自适应算法中，每台处理机结点利用查询过程中搜集的信息，将所有的处理机结点分为发送、接收和中立者(重载、轻载和适载)，并用3张表(发送、接收和中立者表)[11]分别记录这些结点的处理机名。当处理机结点为发送者时，启动发送者算法，当处理机结点为接收者时，启动接收者算法。自适应算法的优点是：查询时查询结点和被查询结点均能更新自己的3张表，真实地记录系统中所有处理机结点的状态信息。每个结点可以根据自身的3张表选择合适的处理机结点发送或接收负载。显然，当系统重载时，由于处理机结点的接收者表多为空，从而抑制发送者启动算法部分，由接收者启动算法进行负载分配；系统轻载时，由于处理机结点发送者表多数为空，从而抑制接收者启动算法部分，由发送者启动算法进行负载分配。其缺点是：系统中的每台处理机结点均保存3张表，浪费存储空间。在该算法中主要的开销在于一个处理机结点对另一个处理机结点的查询。由于在表中选择处理机是随机的，而且这3个表保存的是整个系统的处理机结点的信息，所以在表中不但不能很快选择到合适的处理机结点，使系统资源不能被充分利用，而且还会干扰其它正在运行中的处理机结点，随着其结点的增多，系统的额外开销将会越来越多[10]。

2) 转移策略