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

原文发布于微信公众号 - SDNLAB(SDNLAB)

原文发表时间:2016-10-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏贾志刚-OpenCV学堂

Windows系统如何安装Tensorflow Object Detection API

TensorFlow™ 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edg...

16910
来自专栏瓜大三哥

VS2详细设计(二)

DVIIN1_CLK为输入视频源的随路时钟,用于检测分辨率的时钟,行分辨率的检测从视频源的数据有效信号DVIIN1_DE的上升沿开始计数,直到DVIIN1_DE...

12130
来自专栏AI科技大本营的专栏

学术 | DeepMind最新研究:使用更简单的环境就能检测AI是否安全

随着人工智能系统在现实生活中变得通用和实用,确保系统的安全运行变得越来越重要。迄今为止,大部分技术人工智能安全研究都集中在,对不安全行为的性质和原因的理论学习上...

28850
来自专栏机器之心

资源 | Facebook开源人工智能框架ParlAI:可轻松训练评估对话模型

选自GitHub 机器之心编译 参与:吴攀、晏奇 Facebook 近日在 GitHub 上开源了一个可用于在多种开放可用的对话数据集上训练和评估人工智能模型...

35680
来自专栏AI研习社

谷歌发布 TensorFlow 1.5,全面支持动态图机制和 TensorFlow Lite

AI 研习社消息,日前,谷歌发布 TensorFlow 1.5,TensorFlow 又一次迎来更新。 在此前的版本中,TensorFlow 迎来三大重大变化:...

30840
来自专栏量子位

腾讯开源智能运维项目,用机器学习减少人为失误

继开源800万中文词的NLP数据集之后,腾讯又开源了一个智能运维学件平台Metis,主要面向运维工程师。

16920
来自专栏携程技术中心

干货 | 机器学习算法线上部署方法

作者简介 潘鹏举,携程酒店研发 BI 经理,负责酒店服务相关的业务建模工作,主要研究方向是用机器学习实现业务流程自动化、系统智能化、效率最优化,专注于算法实践和...

1.1K60
来自专栏吉浦迅科技

【入门篇】Jetson TX2深度学习Inference初体验

前面如果已经在Jetson TX2安装好JetPack和Caffe(【入门篇】一个小白在Jetson TX2上安装caffe的踩坑之旅 ),我们接下来可以尝试在...

1.3K80
来自专栏ATYUN订阅号

别再用pip了,用conda安装Tensorflow可使性能速度提升8倍

别再用pip安装Tensorflow了,改用conda吧,它是一个跨平台运行的开源软件包和环境管理系统。因此它适用于Mac,Windows和Linux。如果你还...

7.7K30
来自专栏机器之心

学界 | 中科院计算所开源Easy Machine Learning:让机器学习应用开发简单快捷

选自Github 机器之心编译 今日,中科院计算所研究员徐君在微博上宣布「中科院计算所开源了 Easy Machine Learning 系统,其通过交互式图...

34450

扫码关注云+社区

领取腾讯云代金券