面向海量业务场景的网络智能流量调度算法研究

杜林峰,崔金鹏,章小宁

(电子科技大学 信息与通信工程学院,成都 611731)

0 引 言

现在互联网已与社会各个领域深度融合,随着生产、教育、医疗等领域的发展及其互联网应用规模的扩张,大量新兴业务开始涌现。这些新兴业务(例如VR/AR、车联网、基因工程等应用)不仅数据量大,而且对时延和丢包率要求较高[1]。图1为VR/AR应用场景。从图1可以看出,设备需要将传感器、摄像头采集到的信息与云端进行交互,并对场景进行更新。由于传输的数据量巨大,需要超高速带宽在短时间内完成,速率达到1 Gbit/s[2]。同时为了保证用户良好的沉浸式体验,网络时延往往要求降低到5 ms以下,网络丢包率需求达到10-6以下。为了保障网络的服务质量(quality of service,QoS),满足不断增长的流量需求,网络运营商可以通过增加路由器和链路的数量来提高网络性能,但这将产生巨大的经济成本。而良好的流量调度策略可以直接缓解网络拥塞,实现业务流的高效传输。因此,研究一种海量业务场景下的流量调度算法实现网络负载均衡具有重要意义。

图1 AR/VR应用场景Fig.1 AR/VR application scenarios

在海量业务场景下进行流量调度存在诸多挑战。第一,海量业务流的并行传输导致较高的网络时延。在VR/AR、车联网等应用场景下,网络需要并行传输海量的业务流,但由于网络资源有限,采用传统的路由协议往往需要较长时间才能完成传输任务。第二,海量突发业务造成网络拥塞。当网络中出现大量突发业务时,由于链路带宽资源有限,极易造成网络拥塞,网络QoS将显著下降[3]。目前,传统IP网络流量调度方法大多基于OSPF路由协议,其通过配置路由参数来确定业务的路由信息,从而实现业务流的路由优化,达到负载均衡[4]。但在新兴业务应用场景下,由于业务量大,基于OSPF的路由方法容易出现转发时延长,链路拥塞等问题,无法满足网络QoS需求。文献[5]提出一种基于最短路的QoS路由算法,根据链路代价为业务流选择满足带宽约束的路由方案,但该方法计算效率较低,在海量业务场景下难以达到理想效果。文献[6]提出了一种基于负载均衡的多路径路由算法,该算法实时计算业务流所有可转发的路径集合,然后从中选择链路负载最小的路径,但由于需要计算业务流所有转发路径,在大规模网络场景中时间成本过高。

近年来,机器学习在图像识别、自然语言处理、自动驾驶等领域迅速发展,受到了学术界和工业界的广泛关注[7]。许多学者开始尝试使用机器学习算法来解决海量业务场景下的网络流量调度问题。文献[8]提出了一种基于监督学习的路由框架,该框架将业务流特征和链路利用率作为深度神经网络输入,并为每条链路输出一个值,最后根据输出生成路径。实验证明该方法能够有效缓解网络拥塞,但由于只训练一个包含所有源、目的节点对的模型,在网络规模较大时,神经网络难以拟合。文献[9]将历史业务量矩阵作为强化学习模型输入,预测未来的网络流量,并通过调整链路权值来进行路由配置,实现负载均衡,但需要评估基于历史业务量矩阵训练的神经网络,迭代次数达到了上万次,模型训练时间过长,这在业务高动态变化的网络场景下并不适用。文献[10]提出了一种基于循环图神经网络的RouteNet解决方案。该方案以邻接矩阵、链路容量、备选路由等信息为输入,对网络的时延、丢包率等参数进行预测,最终根据预测值选择最优路由方案。在路由规划过程中,当网络拓扑变化太大时,模型往往需要重新训练,但由于RouteNet中嵌套了循环神经网络,重新训练的时间太长,无法满足网络高QoS需求。

针对上述方案存在的问题,本文以最小化最大链路利用率为目标,提出了一种基于机器学习的网络智能流量调度算法。该算法以业务量矩阵[11]、网络拓扑、业务QoS要求(带宽,端到端时延)为约束,运用启发式算法计算所有节点对在当前网络状态下的最优路由方案,生成标签数据库;采用BP神经网络模型[12]作为学习机制,根据网络状态和流量调度方案的映射关系离线训练网络智能流量调度模型;在网络运行阶段,当业务流到达时,控制器根据当前网络状态采用网络智能流量调度模型实时对业务流进行调度。考虑到如果采用单个模型对网络所有业务流进行调度,将导致流量调度决策时间过长,本文为网络中所有存在非零业务量需求的节点对分别训练一个网络智能流量调度模型,对业务流进行并行调度。在实验部分,为还原海量网络数据并发传输场景,本文通过流量回放的方法,回放11.5万条互联网的真实新兴业务流(AR/VR、车联网等)。

1 负载均衡流量调度问题描述

以最小化最大链路利用率为优化目标的流量调度问题称为负载均衡问题[13]。给定网络拓扑G(V,E),V表示网络中所有节点的集合,|V|=N,共有N个节点,其中仅有D个节点对存在非零业务量需求;E表示网络中所有链路的集合,|E|=L,共有L条链路。节点用符号v(v∈{1,2,…,N})表示,链路用符号e(e∈{1,2,…,L})表示。给定业务量矩阵TM,其中TM为一个N行N列的矩阵,第i行j列代表节点i到节点j的业务量需求。仅考虑D个有非零业务量需求的节点对,每个节点对之间的业务量需求用符号d(d∈1,2,…,D})表示。主要参数如表1所示。

对于每一个业务量需求d,需要计算出该业务量需求下源节点i到目的节点j的所有路径集合Pi,j。根据实际需求,从所有路径集合Pi,j中选择出K条路径组成备选路径集合。在单个业务流不可再分的应用场景下,节点i到节点j的业务量需求d只能选择备选路径集合中的一条路径来放置流量,因此满足约束条件

(1)

(1)式中:Pd为备选路径集合;xd,p为一个二维变量,当业务量需求d选择Pd中的路径p来放置流量时取1,否则取0。

对于网络拓扑中所有链路,使用符号δe,d,p表示链路e是否属于业务量需求d下选择的备选路径p,该符号满足约束条件

(2)

同时,由于网络拓扑中经过链路e的流量之和不能超过该链路的链路容量,因此变量xd,p还应满足约束条件

(3)

(3)式中:hd表示业务量需求d的需求量;ce表示链路e的链路容量。

用z表示网络拓扑的最大链路利用率,定义为

(4)

网络拓扑中所有链路的链路利用率都应当不超过最大链路利用率,因此满足约束条件

(5)

本文的目标是在流量调度过程中最小化最大链路利用率,优化问题可表示为

minz

s.t. (1), (3), (4), (5), (6)

表1 主要参数Tab.1 Main parameters

2 网络智能流量调度算法方案

网络流量调度方案的最优解可以通过求解流量调度整数线性规划模型(integer linear program,ILP)得到。最优解为某个网络状态下各节点对业务路由的最优路径。但随着网络规模的增大,该问题的求解难度指数增加,无法在合理的时间内求出最优解。比较常用的解决方案是设计一种优化同一目标函数的启发式方法,得到流量调度方案的次优解,以此逼近最优解的性能。但其在网络时延需求较高的业务场景下并不适用,由于业务需求动态变化,为了使网络不断地根据次优解进行路由,算法必须重复运行,这将占用大量的计算资源,且无法保证路由决策的实时性需求。因此,本文设计通过神经网络模型学习启发式算法求解的次优解方案,采用神经网络模型替代启发式算法进行路由决策,以此逼近最优解性能,并在短时间内实现路由决策。

网络智能流量调度算法的总体框架如图2所示。网络总体架构采用软件定义网络(software defined network,SDN)架构。SDN将网络层的数据转发与控制解耦,控制平面由控制器进行网络状态感知与路由计算,数据平面由网络节点(例如虚拟交换机)实现数据转发,控制平面与数据平面之间通过OpenFlow协议进行数据交互[14]。网络中每个非零业务量需求的节点对都由控制器维护一个网络智能流量调度模型,用于该节点对业务的路由决策。网络控制器实时接收更新的网络状态(例如业务量矩阵、链路剩余带宽、业务端到端时延等),并调用每个节点对的网络智能流量调度模型生成该节点对流量调度的最优路径。随后控制器将所有节点对的路由方案以流表项的形式下发并注册到所有网络节点中,每个节点可以根据注册的流表项直接进行数据转发,最终实现全局流量调度。

图2 网络智能流量调度算法总体架构Fig.2 Overall architecture of network intelligent traffic scheduling algorithm

由于控制器与网络节点间采用OpenFlow协议进行通信,在同一网络状态下,控制器只需进行一次路由计算。当最优路由方案集合以流表项形式下发至所有网络节点后,网络节点仅需周期性地向控制器发送链路负载状态信息,直到出现新的节点业务转发需求。文献[15]表明这并不会使网络负载发生显著变化,协议开销可以忽略不计。因此,通过这种方式能够有效节约网络资源,降低网络负载。

网络智能流量调度算法共包括2个阶段:训练阶段和预测阶段。训练阶段在实际业务路由开始前完成,运用启发式算法求解每个业务量矩阵对应的最优路径方案,使用业务量矩阵与最优路径方案组成的标签数据库训练每个节点对的BP神经网络模型,保存模型以在预测阶段执行。预测阶段即实际应用阶段。在预测阶段,当控制器检测到新的数据包时,将解析该数据包,读取源节点和目的节点编号、转发带宽需求等,随后发送给相应节点对的BP神经网络模型,得到该数据包的最优转发路径。由于只需通过训练好的BP神经网络模型进行路由决策,无须执行大量的计算,因此算法能够有效满足海量网络业务的实时性需求,解决传统路由策略计算成本及时间成本过高的问题。

3 网络智能流量调度模型设计

3.1 模型输入输出设计

业务量矩阵代表网络中所有源、目的节点对之间的业务量需求,例如业务量矩阵的第i行第j列代表节点i到节点j的业务量需求。准确及时的业务量矩阵能够有效反映网络状态,因此采用业务量矩阵作为神经网络模型的输入。为了简化神经网络输入结构,将业务量矩阵展开为向量形式。

考虑到网络高动态变化的特点,为了实现路由决策的高效性,神经网络模型直接以当前业务的最优转发路径作为输出。在预测阶段开始前,利用K最短路径算法[16]为每一个非零业务量需求的节点对求解出K条不同的无环备选路径,而最优路径将从这K条备选路径中选择。为了简化神经网络输出结构,将二进制标签作为模型输出。例如当K=5时,模型输出000代表选择第1条备选路径作为最优路径,输出001代表选择第2条备选路径,以此类推,输入输出特征如图3所示。综上所述,本文采用M维向量x,N维向量y分别表示神经网络的输入输出,向量x表示为

x=(x1,x2,…,xM-1,xM)

(7)

(7)式中:xi代表网络控制器上一时刻测算的第i个节点对之间的业务量需求。向量y表示为

y=(y1,y2,…,yN-1,yN)

(8)

(8)式中:yi∈{0,1}代表最优路径的选择情况。

图3 模型输入输出特征Fig.3 Features of model’s input and output

3.2 神经网络模型设计

BP神经网络是深度学习模型中最常见和有效的神经网络模型,是一种通过误差逆向传播训练的多层前馈网络,具有较强的非线性映射与泛化能力。在网络路由决策领域,BP神经网络可以通过监督学习的方式有效学习网络路由预测的特征,在一些应用场景下,BP神经网络与整数线性规划中求解最优解的方法性能相近,且性能显著优于最短路等常见路由算法[17],是启发式路由算法的一种有效替代方案。本文选择BP神经网络来完成网络路由计算任务,图4为BP神经网络具体结构。BP神经网络共包含L层:输入层x,输出层y,以及(L-2)层隐藏层。输入层x的神经元个数由业务量矩阵的维数决定,例如业务量矩阵为N维,输入就由N个神经元组成,每个神经元的输入为相应节点对的业务带宽需求。输出层y包含M个神经元,神经元个数M由该节点对的备选路径个数K决定,要求M=[lbK]。两层之间的神经元通过加权连接,但是同一层的神经元无连接,同时每一个神经元都有一个加权偏置。隐藏层和输出层分别采用Relu函数和Sigmoid函数作为激活函数。

BP神经网络采用反向传播算法进行训练,将输入量xi与权值wi的乘积与一个给定的阈值bi做差,此值通过传递函数f得到输出值yi,同时比较网络的输出值与期望值的误差,通过误差的反向传播,利用梯度下降法不断调整和修改网络各层之间的链接权值和阈值,从而使输出结果更加接近真实值,同时收敛到预设的目标误差函数值。通过反向传播算法改变权重系数,初始权重由网络随机赋值,然后根据网络迭代结果调整直到满足目标误差。当所有参数的变化值都小于迭代阈值或达到最大迭代次数时,模型训练完成。

4 训练数据生成设计

网络智能流量调度模型的训练流程如图5所示。网络控制器首先从网络中采集非对称业务量矩阵,随后采用K最短路径算法计算每个节点对的备选路径集合,求解不同业务量矩阵下每个节点对的最优路径组成标签数据库,以训练该节点对的神经网络模型。

在求解出每个节点对的备选路径集合后,本文对网络中所有非零流量业务逐个进行最优路径计算,每计算一条流量业务d就把该业务的占用带宽即需求量hd,加到所经过链路的流量之和上,以此产生对后续业务计算路径时的影响。在流量放置过程中,若当前业务流量使得最大链路利用率z大于预设值zmax,说明此时网络出现拥塞,当前业务放置顺序并不是最优顺序。因此将拥塞链路上的业务流量取出重新计算并部署,直到网络中的最大链路利用率降低到预设值以下。在流量业务放置过程中,始终受到(1)式、(3)式的条件约束,即业务量需求d只能选择Pd中的一条路径来放置流量,网络拓扑中经过链路e的流量之和不能超过该链路的链路容量ce。训练数据生成算法如算法1所示。

图4 神经网络结构Fig.4 Neural network architecture

算法1训练数据生成算法

1)初始化网络中所有链路的流量之和为0,对D条流量业务进行排序,令i=1。

2)将第i条业务放置到网络拓扑中,即从备选路径集合Pd中取出备选路径p,将该业务的占用带宽加到路径p所经过链路的流量之和上,计算当前网络的最大链路利用率z;比较所有备选路径的z值,选择最小值所对应的备选路径作为该业务的路由方案。

3)检查当前网络的最大链路利用率z是否超过预设值zmax。若超过,执行步骤4);否则执行步骤6)。

4)将已放入的后N(N>0)条业务从网络中取出,并将这N条业务的需求量从所经过链路的流量之和中减去。

5)将取出的N条业务重新排序,并按当前顺序再次放入网络后,执行步骤3)。

6)如果i≤D,令i=i+1,执行步骤2),否则输出所有流量业务的路由方案,算法结束。

图5 网络智能流量调度模型训练流程Fig.5 Training process of network intelligent traffic scheduling model

当从网络中实时采集业务量矩阵之后,运用训练数据生成算法可以很快求解出每个业务流的路由方案。将每个业务流的路由方案用最优路径标签表示,本文实验中备选路径集合包含5条路径,标签采用3位二进制数,即第1条备选路径表示为000,第2条备选路径表示为001,以此类推。这样每个业务量矩阵在每个非零流量业务需求的节点对上都有一个最优路径标签与之对应。当N个业务量矩阵的路由策略计算完毕,对于每个非零业务量需求的节点对就产生了N条训练数据。带标签的训练数据库如图6所示。

训练数据的质量对于模型表现至关重要,本文对生成的训练数据库进行复查评估。对于某个采集的业务量矩阵,当前网络状态下所有存在流量需求的节点对从各自的训练数据库中取出对应的标签数据,并按照路径标签代表的最优路径进行业务路由。当网络中的最大链路利用率大于预设值zmax时,则判定该业务量矩阵对应的标签数据不合格,并从训练数据库中剔除。重复以上过程,直到训练数据库中所有训练数据都经过复查评估。通过这种方式,能够有效提高训练数据的准确性。

图6 带标签的训练数据库Fig.6 Tagged training database

5 实验结果及分析

为了验证网络智能流量调度算法在海量业务场景下的算法性能,将该算法与最短路径算法、邻域搜索算法在负载均衡、平均时延和最大丢包率等方面进行实验对比分析。

本文基于虚拟云环境与OVS搭建的全站式网络模拟环境进行实验分析。该网络环境具有完备的网络配置、管理和GUI平台,网络拓扑如图7所示。网络共有100个节点、566条链路,其中114个节点对存在非零业务量需求。为了保证网络环境中的流量真实可信,本文采用了流量回放的方法,即通过回放115K条互联网开源业务流(视频、AR/VR、车联网流量等)来还原真实的海量新兴业务场景。实验中链路带宽设定为100 Mbit/s,采用ONOS作为SDN网络的控制器[18],分别运行启发式算法和网络智能流量调度算法。在运行网络智能流量调度算法时,将K值设定为5,即每个业务的备选路径集合包含5条路径。ONOS每20 s采集一次节点对的业务流组成全局业务量矩阵,使用训练数据生成算法得到10万条标签数据,训练集和测试集比例为0.9∶0.1。神经网络采用5层BP神经网络模型,使用Adam优化器进行参数训练,共训练114个网络智能流量调度模型。

采用最短路径算法、邻域搜索算法与网络智能流量调度算法进行实验对比分析。最短路径算法通过构造最短路径树,按非降次序逐条构造从起始节点到各个节点的最短路径。邻域搜索算法以初始节点为起点,每次迭代选择邻域中链路剩余带宽最大的链路组成路径,直至到达目的节点。

图7 网络拓扑Fig.7 Network topology

本文选取3个性能参数来评估算法性能:①最大链路利用率:网络中所有链路的最大带宽利用率;②平均时延:数据包在节点对之间转发所耗费的平均时间;③最大丢包率:转发过程中所丢失数据包占所发送数据组的最大比率。

图8为实验环境下运行最短路算法、邻域搜索算法及网络智能流量调度算法后网络最大链路利用率情况对比。运行最短路算法时,网络最大链路利用率最低为79%,最高为100%,这是由于在最短路算法中每个源、目的节点对间的业务流都走路由跳数最少的路径,而拓扑中的某些链路总属于最短路的一部分,许多业务流都会使用此类链路,这将导致此类链路的链路利用率很高,其余很多链路空闲。运行邻域搜索算法时,网络最大链路利用率最低为83%,最高为100%,原因在于邻域搜索算法每次都选择邻域中剩余带宽最大的链路,这可能导致最后生成的路径跳数较多,跳数多意味着一个业务流占用了更多链路的带宽资源,所以无法达到较好的负载均衡效果。而运行网络智能流量调度算法时,网络最大链路利用率最低为59%,最高为71%,网络链路利用率得到明显优化。因此,网络智能流量调度算法在海量业务场景下性能优于最短路径算法以及邻域搜索算法。

为了更清晰地展示网络智能流量调度算法的性能提升效果,图9给出了算法相比于最短路算法、邻域搜索算法在最大链路利用率方面的性能提升。从图9可以看出,大多数情况下网络智能流量调度算法得到的最大链路利用率都优于最短路算法和邻域搜索算法,这说明算法在海量业务场景下能够有效缓解网络拥塞。

图8 最大链路利用率Fig.8 Comparison of maximum link utilization

图9 最大链路利用率性能对比Fig.9 Performance improvement ratio of maximum link utilization

在最大链路利用率得到优化的同时,网络的时延与丢包率也得到了明显改善。图10为3种算法平均时延的情况对比,图11为最大时延的情况对比。由图10—图11可见,运行网络智能流量调度算法时,网络平均时延都保持在1 ms以下,最大时延都保持在30 ms以下;而最短路算法和邻域搜索算法的平均时延往往超过10 ms,最大值达到35 ms;最大时延超过110 ms,最大值达到190 ms。网络智能流量调度算法可以大大降低网络时延,避免数据包转发耗时过高的问题。

图10 平均时延对比Fig.10 Comparison of average delay

图11 最大时延对比Fig.11 Comparison of maximum delay

图12为3种路由算法最大丢包率的情况对比,运行最短路算法和邻域搜索算法时,每个时刻网络的最大丢包率都超过60%,甚至达到95%,此时网络中的某些链路已经严重拥塞,大量网络数据包无法转发到目的节点。而运行网络智能流量调度算法时,网络链路的最大丢包率保持在7%以下,算法能够有效降低网络丢包率,保障数据包的有效传输。

综上,网络智能流量调度算法能够根据实时业务量矩阵合理规划流量调度策略,相比于最短路算法,能够有效降低网络最大链路利用率、平均时延和最大丢包率,实现负载均衡。通过3种算法的实现效果对比可知,网络智能流量调度算法能够有效避免网络中出现拥塞链路,确保数据的有效传输。

6 结束语

本文对海量业务场景下的流量调度算法展开研究,提出了一种基于深度学习的网络智能流量调度算法。本文对负载均衡流量调度问题进行建模,设计智能流量调度算法的总体架构,利用启发式算法生成训练数据集,训练网络智能流量调度模型对业务流进行实时调度。在实验平台上对所提算法进行的性能测试结果表明,所提算法相比于传统启发式路由策略具有更好的网络优化性能,能够有效缓解网络拥塞。

图12 最大丢包率对比Fig.12 Comparison of maximum packet loss rates