ONOS：负载均衡路由算法及应用开发（一）

一、应用介绍

当新流量发起时，本应用将为其选择一条路由路径，这条路径具有全局负载均衡意义上的最小权值(Weight/Cost)。
本应用即将开源在笔者的Github【https://github.com/MaoJianwei/ONOS_LoadBalance_Routing_Forward】
本系列文章后续也将同步在笔者的博客Blog【http://maojianwei.github.io/】

为负载均衡举一个简单的例子，在一个三节点的环形网络中，Host2想要访问Host1，此时网络中已经有了一些背景流量，三条线路目前的负载分别是800M、600M、400M，那么考虑到600M和400M构成的路径的负载更小(600M)，我们将为Host2的这次访问选择这条绕远的路径。下图是笔者在与ONOS Community Mail-List【https://groups.google.com/a/onosproject.org/forum/#!forum/onos-discuss】交流时使用的一张图。

本应用的负载均衡算法主要考虑的是路径带宽的负载均衡。路径的带宽权值跟组成路径的每一条线路的带宽权值息息相关。一条线路的带宽权值可分为两种：一种是线路的剩余带宽，另一种是线路的剩余带宽比，也即剩余带宽占总带宽的比重。相应地，一条路径的带宽权值也就对应着各条线路剩余带宽的最小值，和各条线路剩余带宽比的最小值。笔者认为从均衡负载的角度看，以后者作为路径的带宽权值更为合适。

考虑这样一种情况，虽然它在现网中可能比较少见？两点间有A、B两条路径，但是A路径的工作带宽比B路径的大，假设A为400G，B为350G，若以剩余带宽为权值，那么最开始的50G流量将完全经由A路径，而B路径完全空闲。回到实验室中的常见场景，A路径可能是光纤10G，B路径可能是双绞线1G，在相差一个数量级的背景下，大多数时间里流量将全部经由A路径，而B路径将可能持续空闲。因此，若以剩余带宽为度量，容易导致网络流量只覆盖高速链路，而低速链路基本空闲的情况。

由此本应用将使用剩余带宽比作为带宽权值的标准，计算公式如下：
Weight = LinkRestBandwidth ÷ LinkLineSpeed × 100

此外，ONOS现有的路由算法和权重计算工具类中，默认以更小的权值代表更优的链路，因此本应用作为部署在ONOS的应用之一，对上述权值做了个转化，同样以最小权值为最优，最终的公式如下：
Weight = 100 - ( LinkRestBandwidth ÷ LinkLineSpeed × 100 )

二、算法及ONOS实现相关

本应用的工作主要划分为四大部分：探路、算权值、选路和铺路。其中选路部分又可划分为优选和选定两个部分。前三大部分属于负载均衡算法的范围。在算法的运作过程中，我们的路径结果集将历经逐步的筛选：

可选路由路径→→优选路由路径→→最优路由路径

下面笔者为大家一一讲解各个部分：

1.探路

开始的开始，我们以全网拓扑图作为输入参数，启动算法。拓扑图是一个图的数据结构，本应用将源主机作为起点，目标主机作为终点，采用递归的方式，进行DFS深度优先搜索，并以遍历完整个拓扑图为目标。

经历每一个节点时，将该节点和经过的链路进行记录，递归返回时则移除。当发现到达目标主机时，将此时记录的所有节点和链路信息整合成一条可选路由路径，记录入结果集。期间若发现到达之前经历过的节点，则判定形成了路由环路，向上进行回溯。
最终，我们将得到多条从源主机到目的主机的无环通路，将其称之为可选路由路径。

2.算权值

我们将为每一条可选路由路径计算带宽权值。首先，计算路径上的每一条链路的权值。我们需要获取链路当前的工作速率，还要获取链路当前的流量速率，通过上文所述的公式进行权值的计算：

Weight = 100 - ( LinkRestBandwidth ÷ LinkLineSpeed × 100 )

其次，选择路径上所有链路的权值的最大值，作为该路径的带宽权值。因为各条链路的负载不同，根据木桶效应，具有最大负载的链路将成为整条路径的短板。

三、选路

3.1 优选

我们通过比较各条路径的带宽权值，从中选出一组具有较小权值的路径，作为优选路由路径。这组路径中至少有一条路径的权值为所有可选路由路径的权值中的最小值。其余优选路由路径的权值与该路径的权值做差后，差值在预设的容限范围内。

这里笔者要插播介绍一下容限范围的意义和作用。
容限范围的意义在于，容忍由于收集不同链路、不同设备的工作参数和统计信息时，由于有周期间隔存在而导致的部分信息更新不及时的问题；容忍由于底层设备在统计上出现的微小正负偏差而造成的数据误差问题。这两点属于测量中的系统误差，应当采取一定的方法进行容忍。

此外，通过先选出一组负载相近的路径，能够给我们提供应用更多路由策略的可能。如下文本算法选路部分中的“选定”步骤，就是一个例子。

容限比例的最佳选取方案应是按不同的链路工作速率进行区分和选取，同时还要考虑实际设备在测量时的偏差范围和测量周期间隔的长短。下表1给出了两组工作速率在不同容限比例下的容限带宽范围，在设备测量精度和测量间隔允许的情况下，选择越小的容限比例能得到越精确的负载均衡效果。表中突出部分为在一般情况下可选用的粗略的容限参考值。希望有现网实践经验的前辈们和朋友们能多多指教，我渴望能收获工程实践中的点滴经验，非常感谢 

3.2 选定

经过优选的步骤，我们已经得到了具有负载均衡意义的路由路径了。此时，我们可以应用其他的路由策略进行进一步的选路。这一步即是对选路结果的优化，也是引入多种路由策略进行共同决策的方法。

在本应用中，采用的选定策略是简单的最少跳数策略。在优选路由路径中选择第一条具有最少跳数的路径作为算法最终选定的最优路由路径。负载均衡算法到此也就完成了它的使命。

四、铺路

在ONOS中，网元设备间的链路被抽象为Link，而设备到终端主机的链路被抽象为EdgeLink。在我们能够获取到的拓扑图中，是不包含最后一公里EdgeLink的。因此，需要在整条路径结果中加上一前一后两个EdgeLink，构成完整的路径，再将路径决策下发到网络中：
SourceEdgeLink→→Links→→DestinationEdgeLink

ONOS：负载均衡路由算法及应用开发（一）