Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


To be a better coder

Valiant Load-Balancing学习

  第一次接触Valiant Load-Balancing (VLB)的时候,对这个意思揣摩了半天,难道是『英勇的负载均衡』?Oh, no...后来才知道,是一个名叫Valiant推出的Load-Balancing方案。本文主要介绍了以下五点内容:

  1. 传统网络状况
  2. VLB的算法思想
  3. VLB的扩展,应对不同容量的链路
  4. VLB如何应对链路断开情况
  5. 两个VLB网络之间如何连接

1.传统网络的不足

  目前的网络流量很难估计和预测,充满了不确定性,这就导致了网络很容易拥塞。举个例子,比如不同数据中心流量传输,可能存在部分链路网络拥塞导致丢包,而部分链路仍然未满载(满流);也可能在平时的时候链路都未满载,而在高峰期就拥塞。所以链路的设计就不断的扩大链路的容量,以满足高峰期流量,降低丢包率,而这种方式的弊端是成本越来越高,且链路空闲导致带宽浪费。

2.VLB

  VLB由Valiant于1982年提出[1],并拥有多种改进版本。它的主要思想是:随机负载均衡、去中心化和两步骤路由。以下是一个简单的VLB网络。
  假设一个内部网络有N个结点,每个结点的容量为r:这意味着出入流量的上限都是r,结点之间的边容量为2r/N,结点之间构成全连通拓扑,我们用flow代表一条流量,如下图所示。
VLB_simple

N个结点构成一个内部网络,每当一条flow进入该网络的第一个结点后,都会被等价分流到N个结点上去,然后再从不同结点发往终点(假设终点也在网络内部)。那么,经历的总跳数为2跳,第一跳为分流到不同结点,第二跳到达终点结点。这意味着N个结点平均分担流量压力,如果第一跳结点就是终点或起点,那么该结点经历一跳。尽管点容量为r,但边容量只要2r/N就能满足要求。
  VLB网络的优点在于负载均衡,缺点在于本来一跳就可以的路径变成了两跳,增加了时延。

3.复杂链路的VLB

  第二节中的VLB应对的是边容量、点容量一致的约束情况,倘若这些都不一致,那么如果做均衡负载就成为问题了,一个直观的感受是边容量大的情况下负载的流量多一些,反之则少一些。
  遵从第二节中的约定,我们还有一些其余的约定:假设是一个的矩阵,其中代表从结点i发往j的流量,假设结点i的容量为(出和入分别都是),则有如下公式:



不失一般性,我们对进行从大到小排序,并让R成为它们之和:,让成为ij之间的边容量大小。
  解决复杂链路网络的一个最简单的模型是:根据边容量大小进行按比例分配流量,比如,结点i收到流量大小为,我们做归一化处理后,推出
  我们可以进一步迭代该模型,让外部因素决定流量的分配:引入了负载均衡因子:,对于所有的i以及。流量的入结点可以根据负载均衡因子进行流量分配:结点i得到了的流量。这个模型还可以继续迭代,我们甚至可以让流量自己决定如何进行流量分配。
  到现在为止,我们已经知道了边容量的大小,这个大小直接和链路费用挂钩,我们需要让这个边容量在满足条件的状况下取到最小,根据以上推导,则有:

那么结点i互连边的容量之和为:

那么全网互连边的容量之和为:

求解的最小化问题变成了求解的最大化问题。根据数论推导,只要在最大的时候,让即可,即。然而,这样做是解决了最优化问题,但仅仅有一个结点被分配了流量,其余都闲置,导致链路未被均衡流量且无法容错(一旦结点坏死,全网都瘫痪了)。
  因此,作者又提出比负载均衡因子更为科学的network fanout,其定义如下:,它衡量了运送流量与自身容量的关系。为了负载均衡,我们让各个结点的fanout的最大值最小,即:所有结点的fanout接近相等。


是关于的增函数,所以容量越大的结点应该传送更多的流量。论文[2]中说明结点互连总容量不要超过倍的最小互连总容量,这样不但负载均衡,而且非常有效。

4.VLB容错

  一个健壮的网络应用具有一定的容错能力,应对网络预期和不预期的干扰。VLB的容错相比较别的容错方案具有以下几个有点:

  1. 所有网络内结点互联的变都会被用到,并且负载均衡。而别的大部分容错方案都是指定链路空闲,以应对不正常的情况。
  2. 因为所有链路都被使用,所以没有必要在失败的情况下建立新链路。
  3. 为了防止k条路径同时断开,只要让边容量提升k/N即可。
  4. 支持多路径断开。

  关于VLB的具体容错推导可以参考[2]。文中举出一个例子:在50个结点的互联网络中,要想应对5条链路的同时断开,只要使得边的容量有11%的提升空间即可。

5.VLB网络间的互联

  VLB中关于互联网络的处理引入了一个新的变量:互联负载均衡因子:,代表互联网络中的流量比例,,代表互联总容量约束,那么结点i(假设左右都为同一个编号i)的互联容量为
VLB_peer   如上图所示,正常情况下,流量在两个网络中流动会导致在每个网络都运行两跳,比如从Network 1中的结点1到Network 2中的结点N。首先在Network 1中做一次负载均衡,1分散到1-N,然后通过互联的2,3,4流入Network 2,同样在2中通过2,3,4分散到1-N,然后再到N。
  如果具有额外的需求,那么导致网络内互联的容量上升。比如我们在Network 1中,从结点1的流量进入不再经过1-N均分,而是直接到达边界点2,3,4。那么1-2,1-3,1-4间的容量就需要变大,否则无法满足要求。
  在实际情况中,一个比较好的方案就是每个结点与边界点互联,边界点拥有更大的吞吐量。这样做的好处是减少了边的数目,降低了全网拓扑复杂度,虽然网络内互联的容量上升了。

说明

转载请注明出处:
http://vinllen.com/valiant-load-balancing/

参考

[1] Valiant L G. A scheme for fast parallel communication[J]. SIAM journal on computing, 1982, 11(2): 350-361.
[2] Zhang-Shen R, McKeown N. Designing a predictable internet backbone with valiant load-balancing[M]//Quality of Service–IWQoS 2005. Springer Berlin Heidelberg, 2005: 178-192.


About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus