Valiant Load-Balancing学习

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

传统网络状况
VLB的算法思想
VLB的扩展，应对不同容量的链路
VLB如何应对链路断开情况
两个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应对的是边容量、点容量一致的约束情况，倘若这些都不一致，那么如果做均衡负载就成为问题了，一个直观的感受是边容量大的情况下负载的流量多一些，反之则少一些。
遵从第二节中的约定，我们还有一些其余的约定：假设 $\Lambda=\{\lambda_{ij}\}$ 是一个 $N \times N$ 的矩阵，其中 $\lambda_{ij}$ 代表从结点i发往j的流量，假设结点i的容量为 $r_{i}$ （出和入分别都是 $r_{i}$ ），则有如下公式：

${\sum_j \lambda_{ij} \le r_i,\forall i}$
${\sum_j \lambda_{ji} \le r_i,\forall i}$
不失一般性，我们对 $r_i$ 进行从大到小排序，并让R成为它们之和： $R=\sum_{i=1}^{N}r_i$ ，让 $C_{ij}$ 成为i与j之间的边容量大小。
解决复杂链路网络的一个最简单的模型是：根据边容量大小进行按比例分配流量，比如，结点i收到流量大小为 $r_{i}/R$ ，我们做归一化处理后，推出 $C_{ij}=2r_ir_j/R$ 。
我们可以进一步迭代该模型，让外部因素决定流量的分配：引入了负载均衡因子： $p_i$ ，对于所有的i， $p_i \ge 0$ 以及 $\sum_{i=1}^Np_i=1$ 。流量的入结点可以根据负载均衡因子进行流量分配：结点i得到了 $p_i$ 的流量。这个模型还可以继续迭代，我们甚至可以让流量自己决定如何进行流量分配。
到现在为止，我们已经知道了边容量的大小 $C_{ij}$ ，这个大小直接和链路费用挂钩，我们需要让这个边容量在满足条件的状况下取到最小，根据以上推导，则有：
$C_{ij}=r_ip_j+r_jp_i$
那么结点i互连边的容量之和为： $l_i=\sum_{j:j \neq i}C_{ij}=r_i+Rp_i-2r_ip_i$
那么全网互连边的容量之和为： $L=\sum_{i=1}^Nl_i=\sum_{i,j:j \neq i}C_{ij}=2(R-\sum_ir_ip_i)$
求解 $L$ 的最小化问题变成了求解 $\sum_ir_ip_i$ 的最大化问题。根据数论推导，只要在 $r_i$ 最大的时候，让 $p_i=1$ 即可，即 $p_1=1,p_i=0 \forall i \ge 2$ 。然而，这样做是解决了最优化问题，但仅仅有一个结点被分配了流量，其余都闲置，导致链路未被均衡流量且无法容错（一旦结点坏死，全网都瘫痪了）。
因此，作者又提出比负载均衡因子更为科学的network fanout，其定义如下： $f_i=l_i/r_i$ ，它衡量了运送流量与自身容量的关系。为了负载均衡，我们让各个结点的fanout的最大值最小，即：所有结点的fanout接近相等。
$p_i=\frac{\frac{r_i}{R-2r_i}}{\sum_k{\frac{r_k}{R-2r_k}}},i=1,2,...,N$
$f_i=1+\frac{1}{\sum_j{\frac{r_j}{R-2r_j}}},\forall i$
$p_i \propto \frac{r_i}{R-2r_i}$ 且 $p_i$ 是关于 $r_i$ 的增函数，所以容量越大的结点应该传送更多的流量。论文[2]中说明结点互连总容量不要超过 $\frac{1}{2}(\sqrt 2+1)$ 倍的最小互连总容量，这样不但负载均衡，而且非常有效。

4.VLB容错

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

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

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

5.VLB网络间的互联

VLB中关于互联网络的处理引入了一个新的变量：互联负载均衡因子： $q_i,i=1,2,...,N$ ，代表互联网络中的流量比例， $R_p$ ，代表互联总容量约束，那么结点i（假设左右都为同一个编号i）的互联容量为 $R_pq_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.

Your browser is out-of-date!

Vinllen Chen