机器学习在SDN路由优化中的应用研究综述

王桂芝1 吕光宏1 贾吾财1 贾创辉1 张建申2

1(四川大学计算机学院 成都 610065) 2(7584部队 广西桂林 541001)

摘 要 随着网络技术的迅速发展和新型应用的不断出现,网络数据的急剧增加导致网络管理变得极其复杂.传统网络中的设备多种多样,配置复杂,难于管理,而软件定义网络(software defined networking, SDN)这种新型网络架构的出现给网络管理带来了曙光,该架构摆脱了硬件设备对网络的限制,使网络具有灵活、可编程性等优点.一个好的路由机制影响着整个网络的性能,软件定义网络的集中控制特性给机器学习在路由机制方面的应用带来了新的研究方向.首先论述了SDN路由优化的现状,然后从监督学习和强化学习2个方面概述了近年来机器学习在SDN路由方面的研究,最后为了满足不同应用的服务质量(quality of service, QoS)以及不同用户的体验质量(quality of experience, QoE),提出了数据驱动认知路由的发展趋势.通过赋予网络节点感知、记忆、查找、决策、推理、解释等认知行为,加快寻路过程,优化路由选择,完善网络管理.

关键词 软件定义网络;监督学习;强化学习;路由优化;服务质量;体验质量;数据驱动;认知

随着网络规模的增大和新型网络应用的不断出现,网络流量呈指数级增长,给网络带来了负载不均衡、带宽消耗严重等一系列问题.单纯的扩容提速,不仅成本高,而且由于缺少系统性的流量管理机制,网络资源利用率低.此外,许多应用程序不仅需要带宽,还需要保证服务质量(quality of service, QoS),如端到端时延、抖动、丢包率等.因此根据网络的状态和需求找到一种实时的自适应的可定制路由是提高网络资源和服务质量的关键性因素.

在传统网络中,控制和转发紧耦合的网络架构与“尽力而为”的服务模式,需要在每个节点上执行特定的路由协议和算法以此来找到源到目的地的最佳路径.正是因为这个分布式体系,使得每个节点只有部分视图,导致很多全局性策略难以实施[1],所以很难进行智能路由.而软件定义网络作为一种新的网络体系架构,通过将控制平面与数据平面分离,提供了灵活高效的网络控制,简化了网络管理过程,使管理员可以通过网络编程的方法定义和控制网络,降低了为数据流提供路由优化服务的难度[2].

近年来,随着人工智能的迅速发展,机器学习在数据处理、分类、智能决策等方面皆取得非常不错的进展,受到了学术界的广泛关注[3].许多研究者开始尝试通过使用机器学习算法来解决路由优化问题.一方面,机器学习可以通过训练快速地计算出接近最优解的路由解决方案;另一方面,机器学习算法不需要精确的底层网络数学模型[4].目前用于解决路由优化问题的机器学习算法主要分为2类:监督学习和强化学习.

现如今,云计算大数据迅速发展,数据中心业务流量极速上升,具有规模大、种类多、速度快和价值密度低等特征的大数据推动了数据驱动的发展,同时也给网络带来巨大的传输压力[5].数据是广泛可用的,它不仅是需要分析和处理的内容,也是一种基础资源.我们需要根据需求从数据中提取有用的知识,使网络节点具有认知能力,可以感知当前环境,并对感知内容进行分析,自动化作出路由决策,实现数据驱动认知路由的功能.

1 SDN相关介绍

软件定义网络(software defined networking, SDN)是由美国斯坦福大学Cleanslate研究组提出的一种新型网络架构[6],其基本思想就是将报文转发所涉及到的复杂逻辑控制从交换机/路由器等设备中分离出来,用软件编程的方式实现对网络的控制管理,从而达到自由操控流量的目的.而OpenFlow技术实现了控制平面与转发平面功能的解耦,由集中控制器向交换设备下发转发规则,使得控制器与交换设备可以相互分离独立发展[6].

典型的SDN架构从上到下包含3层,分别是应用层、控制层、基础设施层,如图1所示.应用层包含流量工程、网络监测、故障恢复、网络虚拟化等网络应用程序,用户可以通过北向接口从控制平面获取全局网络视图,然后根据该信息编写网络策略对网络事件进行处理;控制层指逻辑集中的控制器,负责维护全网视图,通过南向接口对数据平面的设备进行集中控制,完成网络流量的分配;基础设施层由交换机等网络设备组成,提供数据转发的能力[7].

Fig. 1 SDN framework
图1 SDN架构

SDN的架构决定了SDN的三大特性:控制平面与数据平面分离、集中控制、可编程性.传统的网络体系结构不够灵活,无法获得网络拓扑信息,且需要不同的协议来满足不同的场景需求.随着网络的发展,网络中的协议也越来越多,配置管理也变得越来越复杂[8].而SDN通过控制器就可以获取到网络拓扑的全局信息,实现了对网络的集中控制,降低了网络节点获取相邻网络节点信息的通信开销以及对网络资源的占用率.同时SDN的可编程性,使得网络通过软件编程的方法,实现对网络的灵活控制,确保资源的优化分配.可以说SDN的出现给传统的网络路由算法带来了新的机遇和挑战.

2 SDN路由机制

传统的路由技术可看作是一种P2P架构,通过建立一张路由表,在路由器与路由器之间运行路由协议,相互交换路由信息从而达到路由共享.而在SDN中,只需要在控制器与交换机之间直接运行南向协议,由控制器统一计算转发规则再下发给交换机.下发有主动和被动2种模式,主动模式是指数据包到达交换机之前就进行流表设置,而被动模式指当新流到达时,发现没有与之匹配的流表项,便将其送至控制器处理,可看作是一种C/S模式.根据是否是多路径路由将SDN路由机制分为2类[9]

1) 最短路径路由

目前主流的SDN控制器如POX,Ryu等皆提供了完整的数据转发模块,采用的基本都是最短路径Dijkstra算法.Dijkstra算法每次都会找出一条源到目的节点的最短路径,然而所有数据包的转发如果只依赖于最短路径,虽然方法简单,但是数据流很容易因为具有相同目的地址而选择同一转发路径,这将会降低链路利用率,容易导致网络拥塞,且不能很好地满足带宽、时延、抖动和可靠性等方面的要求[10].

2) 多路径路由

多路径路由是根据网络流量分布和业务流量需求,选择满足约束条件的多条候选路径,并在这些路径中均衡通信流量,从而提高网络的可靠性和吞吐量,降低网络拥塞,减少传输时延[9,11].QoS技术的出现旨在解决网络拥塞问题,保证网络可以根据业务的不同需求合理地分配和调度资源,为不同的数据流提供不同的服务质量.文献[12]提出了一种基于SDN的多路径路由系统HiQoS.通过修改Dijkstra算法,控制器计算出满足QoS约束的多条路径,并使用Hash表来保存,然后定时更新这些路径的链路状态.当需要为业务流选择路径时,控制器根据带宽使用情况和队列状态等为其选择一条最优路径.孔祥彬等人[13]提出一种基于Dijkstra算法的QoS路由算法,为业务流选择满足带宽约束的路由.这些研究大多是基于Dijkstra算法或对其进行改进,目的是计算出从源节点到目的节点的最短路径,计算效率低,不适合大型网络环境.文献[14]提出了一种基于SDN负载均衡的多路径路由算法.控制器收集每一条链路的流量负载信息,当新流到达时,控制器计算所有可以转发该流的路径,通过比较路径的链路负载选出一条最小负载的路径.该算法需要考虑该流的所有转发路径,在拓扑复杂的网络中,计算量过于庞大.

如果将SDN路由视为一项决策任务,那么在网络中找到最理想的控制策略是最关键的问题.今天大多数采用白盒方法来解决这个问题[15].随着网络规模的扩大和网络应用数量的快速增长,当前的网络已经变得高度动态、复杂、分散和定制化.在应用这些传统的白盒算法时,也面临着一些挑战.具体来说,白盒方法通常需要对底层网络进行假设和简化,然而,这种理想化的模型在处理真实复杂的网络环境时往往会遇到困难.此外,白盒方法在不同的场景和应用程序下具有较差的可伸缩性[16].

Fig. 2 KDN framework
图2 知识定义网络架构

由于机器学习在机器人控制、自动驾驶汽车等相关应用的成功,Mestres等人[17]提出了一种基于机器学习(machine learning, ML)的网络控制方法,这种新的范式被称为知识定义网络(knowledge defined networking, KDN).该范式将SDN、网络分析(network analytics, NA)和人工智能(artificial intelligence, AI)结合起来,促进了人工智能在计算机网络中的操作和管理[18].其框架如图2所示,知识平面通过控制和管理平面收集丰富的网络视图,然后利用机器学习将其转化成知识,并根据这些知识进行自动化决策.在路由优化决策中,我们的目标是利用这些知识赋予每个节点感知、询问、学习、推理和反馈等认知行为,使他们可以实时、在线地做出自适应路由决策,以达到最优网络性能[19].

3 基于监督学习的SDN路由优化

监督学习[20]是一种标签学习技术,通过给定数据及标签建立系统模型,找到输入输出的映射关系,训练完成后,当输入新的数据后,得到预期结果.监督学习通常被用来做分类和回归任务,常见的算法有K-最近邻算法、决策树、随机森林、神经网络、支持向量机(support vector machine, SVM)等.

监督学习通过学习解决各种网络应用问题,如资源分配、Web服务、路由选择等.Valadarsky等人[21]提出了利用监督学习模型预测未来的流量需求,然后为该需求计算最佳路由策略.此外,也有利用监督学习模型直接学习路径的研究[22].在文献[22]中,作者提出了一种采用GPU驱动的软件定义路由器(SDRs)来执行深度学习技术,通过使用监督的深度信念架构(DBA)[23],以边缘路由器的流量模式作为输入,网络中的每个节点都会针对其发送流量的每个可能目的地训练不同的模型,以此来估计下一跳.研究表明:该架构在网络吞吐量和平均时延方面都优于传统的开放式最短路径优先(open shortest path first, OSPF).

启发式算法,包括蚁群优化算法、模拟退火算法、遗传算法等可以有效管理流量,是解决动态路由优化问题的常用方法.这些算法可以有效减少端对端时延,减轻网络负载以及防止数据的丢失,但这是要建立在牺牲带宽为前提下且计算复杂度较高、计算时间开销大,导致其不能实时计算出最优路径[24].目前很多研究将监督学习算法和启发式算法相结合,以网络状态、流量矩阵作为输入,通过启发式算法计算出的相应路由策略作为输出进行训练神经网络,得到一个训练模型.当新流到达时,通过训练模型输出合适的路由路径.

文献[24]将启发式算法融入到监督学习中,提出了一种基于监督学习的动态路由框架,目的是获取满足QoS要求的最优路径.该框架如图3主要包含启发式算法层和机器学习层,将启发式算法层的输入(全局网络状态)和输出(最优路径)作为机器学习的数据集,然后在动态路由过程中,机器学习模型可以根据输入的网络状态快速计算出最优路径.实验表明:该方法计算效率高,且具有更好的网络性能.

Fig. 3 Dynamic routing framework based on machine learning
图3 基于机器学习的动态路由框架

Azzouni等人提出[25]基于深度神经网络的软件定义网络的NeuRoute动态路由框架同样也运用了启发式算法.该框架主要由流量矩阵估计器(TME)、流量矩阵预测(TMP)、流量路由单元(TRU)组成.首先TME通过OpenMeasure框架[26]使用连续的在线学习技术自适应推理和测量流量矩阵,然后TMP使用长短期记忆递归神经网络(LSTM-RNN)对TME产生的流量矩阵进行训练来预测未来网络流量矩阵,最后TRU将预测的流量矩阵和当前的网络状态作为输入,通过启发式计算出来的相应路径作为输出,训练前馈神经网络模型.在新流到达前,该训练模型计算出最优路由路径,然后TRU将选择的路径发送给控制器,控制器安装流表项.当新流到达时,转发规则已安装,交换机直接转发数据包,大大减少了网络时延.

研究表明:将启发式算法和监督学习算法结合对SDN路由优化具有一定优势,其运行时间远小于启发式算法,而网络时延、抖动等性能与利用启发式路由的结果相似.可见,利用监督学习进行路由优化是一种有效的方案.但是启发式算法被定义为NP问题,在利用启发式算法获取标签的过程具有较高的复杂度,且在网络管理过程中不能灵活地调整运维策略.文献[23]提出了一种基于监督学习的路由框架,该框架允许使用深度学习模型替换启发式方法,将流特征和当前的网络状态作为深度神经网络的输入,为每条链路输出一个值,最后再将其转换成路径.实验证明该方法实现了最大链路利用率.

在SDN中,控制器对交换机进行集中控制并下发决策.通常来说,SDN也像传统网络一样为一对源到目标节点分配路径.但如果让网络具有应用感知和多路径分组转发,那么这2个特性可用于对不同输入应用程序进行分类并根据其类别分配不同的路径,这将增加用户的体验质量(quality of experi-ence, QoE).文献[27]提出了一种融合机器学习和软件定义网络的基于应用识别和路径状态感知的多路径包转发机制,该机制首先利用SVM算法[28]对控制器捕获的流特征进行优先级划分,不同的应用流具有不同的优先级;同时利用YKSP算法[29]找到源到目的地的k条路径;最后控制器通过可用带宽和延迟等参数评估每个可能的路径特征,并根据它们所属类的优先级为流分配路径.这个方法为具有QoS需求的数据中心网络、电信数据网、校园网等大规模网络环境带来了一定好处.

表1对基于监督学习的SDN路由优化方法进行了总结,可以看出监督学习作为一种标签学习技术,特别是神经网络,在SDN路由优化方面发挥着巨大的作用.但它的缺点也是不容忽视的.无论是使用启发式算法的输入输出作为训练集还是对流量进行提前的感知预测分类,在训练过程中都需要获取大量的标签数据进行训练,这将导致一个很高的计算复杂度.所以,我们的研究重心应该是让流量具有自我感知特性,尽量不使用标签,让网络通过对历史数据的自主学习实现智能路由.

Table 1 SDN Routing Optimization Method Based on Supervised Learning
表1 基于监督学习的SDN路由优化方法

ReferenceMethodSummaryRef [21]Deep Neural NetworkUsing a supervised learning model to predict future traffic demand and then calculating the opti-mal routing strategyRef [22]Deep Belief NetworkProposing a supervised deep learning system to directly calculate paths using traffic patternsRef [24]Neural NetworkCombining heuristics and supervised learning with dynamic routing to quickly calculate optimal routing pathsRef [25]Neural NetworkProposing a ML-based dynamic routing framework called NeuRoute, which predicts the future traffic matrix through LSTM-RNN and combines heuristic algorithms to calculate the forwarding path in real timeRef [23]Deep Neural Networkproposing a routing framework instead of heuristic algorithm to obtain the best routing decision by training deep neural networksRef [27]SVMProposing a multi-path packet forwarding mechanism based on application recognition and path state awareness, using SVM to prioritize flow characteristics, and finally assigning paths based on priority

4 基于强化学习的SDN路由优化

Fig. 4 Reinforcement learning mechanism
图4 强化学习机制

强化学习(reinforcement learning, RL)[30]是目前人工智能最流行的一种学习方法.在一定环境状态下,通过代理与环境的交互,采取行动来获得最大的累积奖励,从而不断强化自己的决策能力.图4展示了常见的强化学习机制.首先环境给代理一个观测值及状态state,代理接收到状态后做出一个动作action,环境接收到动作后给予代理一定奖励并给出一个新的状态.其目的是从自己的经验中学习以使自己的奖励最大化.典型的强化学习算法有Q-Learning[31],它是通过对Q值的学习来更新存储状态、动作、奖励的表.

将SDN路由优化看成一个决策问题,运用强化学习方法进行路由优化.网络即为学习环境,将网络拓扑、流量矩阵等视为状态,改变链路权重视为动作,运维策略如QoS服务质量等作为奖励,不断训练,得到一个模型.当新流到达时,可以快速计算出合适的路由路径,使网络性能最优.

Lin等人[32]在Kandoo[33]和Xbar[34]架构基础上,提出了一种符合OpenFlow协议的多层分布式控制架构.如图5所示,该架构主要由超控制器、主控制器、从控制器和OpenFlow交换机4个部分组成.交换机负责数据的收集和转发,从控制器将交换机收集的网络状态发送给主控制器,主控制器负责对每个传入的流进行路径计算,唯一的超控制器控制全局网络状态.在此架构基础上提出了基于强化学习的QoS动态路由算法(QoSaware adaptive routing, QAR),该算法将softmax作为动作选择策略,状态-行动-回馈-状态-行动(state-action-reward-state-action, SARSA)作为Q值更新函数:

Qt+1(st,at)Qt(st,at)+
α[Rt+γQt(st+1,at+1)-Qt(st,at)],

其中,α∈[0,1]表示学习效率,决定有多少误差需要被学习;γ∈[0,1]表示对未来奖励的衰减值;Rt表示在时刻t的QoS感知奖励.根据采取行动的成本、传输时延、排队时延和可用带宽计算出一种实时的自适应QoS路由决策,实现了控制负载的共享,减少了信令时延.实验表明QAR相比于Q-Learning方法,性能更优且具有较快的收敛性.

Fig. 5 Distributed hierarchy construction
图5 分布式层次结构

因为SDN网络是一个复杂的连续时间系统,对数据流的细粒度进行管控,所以维护网络状态、动作、奖励信息的Q表会占用大量的存储空间,并随着Q表的不断增大,查表问题将是一个不容忽视的问题.为了解决这个问题,Sendra等人[35]提出了以神经网络代替Q表的学习过程,采用深度Q网络(deep Q network, DQN)的方法来进行智能路由,根据最佳网络状态和运维管理策略选择最佳数据传输路径.该方法降低了损失率和时延,提供了一个更好的QoS.然而DQN不能实时收敛,因为对SDN网络的操控是一个连续控制的问题,而DQN只适用于低维离散空间的控制和优化[36].

传统的强化学习基于表的方法记录状态、动作的奖励,对最优行为策略的收敛率低,且不能解决高维状态和动作空间的问题.而深度强化学习(deep reinforcement learning, DRL)[37]将深度神经网络和强化学习结合,利用深度神经网络逼近值函数,使用强化学习的方法进行更新,自动从高维数据中提取低维特征,有效地压缩网络状态空间,从而使RL能够解决以前在处理高维度状态和运动空间时难以解决的大规模网络决策问题[16].

文献[38]首次提出了用自动化DRL代理提供路由配置.该研究可以自适应网络流量状况,通过DRL代理在单个步骤中提出最优的路由决策,实现了对网络的实时控制,克服了优化和启发过程中迭代步骤的繁琐.其中DRL代理是一种确定性策略梯度算法,通过状态、动作和奖励的更新与环境进行交互,状态即为流量矩阵,动作为改变链路权重,奖励为网络时延,其目的就是通过状态S到动作A的映射得到最优行为策略,从而最大化奖励,即最小化时延.

Fig. 6 DROM framework
图6 DROM框架

和文献[38]类似,Yu等人[39]提出了一种基于机器学习的SDN网络框架,该框架主要用一种深度强化学习算法——深度确定性策略梯度(deep deterministic policy gradient, DDPG)[40]来优化SDN网络路由,在此基础上提出了一种路由优化机制DROM,其架构如图6所示.DROM通过SDN控制器对网络进行分析和测量来获取全局网络状态,并确定一个最优行为,即一组链路权重,通过最大化奖励,不断更新链路权重集,SDN控制器也不断生成新的规则来建立新的路径.以此类推,不断迭代优化,直到获得最优解.其中奖励可以是单个参数如时延、吞吐量,也可以是包含多个参数的综合策略:

Rij=R(ij|st,at)=
-h(at)+αdelayij+βBWij+γlossij+θTPij.

该式表示在状态st、动作at下的奖励,包含成本、时延、带宽、损失率、吞吐量等性能,其中h表示执行操作的成本,α,β,γ,θ∈[0,1]为可调参数,由运维策略决定.实验表明:DROM实现了在连续时间内对网络进行全局、实时、自定义的智能控制和管理,具有良好的收敛性和有效性.

由于流量具有周期性和相关性等特征,文献[41]提出将循环神经网络(recurrent neural network, RNN)作为输入神经网络,将之前所学状态描述联系起来一起学习,以得到一种更准确的结论.在RNN的基础上,结合DDPG,自动生成用于流量工程的策略.与最短路径相比,减少了网络的平均传输时延,但强化学习代理无法达到稳定,会引起流量的抖动,且不能迅速收敛.

此外,当前的研究大多使用模拟仿真的方法来评估网络性能,并未部署到实际的SDN网络中,未涉及如主机、交换机流表、SDN控制器等特定元素.近期,Witanto等研究者[42]从SDN本身的系统架构及流处理过程出发,提出了利用DDPG实现流量监控和路由的SDN应用方案.该方案主要由流量监控和路由2个模块构成,流量监控模块定期监控流量,统计并保存每个端口接收和发送的字节信息,用于训练神经网络生成流表项;路由模块通过深度强化学习代理根据交换机的端口利用率,生成图的边缘区权值,最大化奖励以使丢包率达到最小.然后控制器通过计算交换机之间最短路径,生成流表项发送给相关交换机,更新流表项.该研究只提供了一个思路,目的是实现一个管理系统,既可以检测设备之间的连接丢失情况,又可以路由网络流量使数据包丢包数最少.

将深度学习和强化学习结合来解决SDN路由问题,是目前一种比较普遍的方式,具有3方面优势:

1) DRL算法是一种黑盒方法.在设计动作空间和奖励时,DRL代理只需要设置不同的网络决策任务和优化目标,无需精确可解的数学模型.而传统的白盒方法要求对基础网络进行假设和简化来建立问题的数学模型并针对优化问题进行求解.

2) DRL可以处理复杂的状态空间,如AlphaGo[43],与传统的强化学习相比具有一定优势.

3) DRL可以实时处理高度动态的时变环境.当网络状态更改时,DRL代理不需要再次收敛.训练好DRL代理后,通过矩阵乘法一步就可以计算出近似最优解;相反,启发式算法需要采取许多步骤才能收敛得到新结果,这将导致较高的计算时间成本[44].

在表2中,我们对基于强化学习的SDN路由优化方法进行了小结,可以看出强化学习作为一门自学习技术,特别是深度强化学习,在SDN路由决策方面发挥着巨大的作用.但在强化学习智能体训练收敛之前,训练开销较大.随着网络规模的增大,网络中的服务和应用将变得越来越多,每当出现新的服务时,需要重新训练收敛,这将限制了智能体优化路由的灵活性和可扩展性[44].

Table 2 SDN Routing Optimization Methods Based on Reinforcement Learning
表2 基于强化学习的SDN路由优化方法

ReferenceLearning ModelSummaryRef [32]SARSAUsing RL to obtain QoS dynamic routing based on a multilayer distributed control architectureRef [35]DQNUsing DQN method to select the optimal forwarding paths to provide a better QoS Ref [38]DRLUsing automated DRL to get optimal routing decisions to minimize network delayRef [39]DDPGUsing DDPG model to optimize routing and determine the optimal behavior to minimize delayRef [42]DDPGProposing a SDN application scheme using DDPG to implement traffic monitoring and routing,which can obtain the optimal forwarding path and minimize the packet loss rate

5 总结与未来展望

5.1 总 结

本文通过从监督学习和强化学习2个方面论述了机器学习在路由优化中的应用研究进展,并对其算法优缺点进行小结,如表3所示.由表3得出结论:通过对强化学习相关算法的不断改进,实时地、自适应地进行路由决策,在优化网络运维管理过程中,强化学习是一种非常有效的方法.与传统的算法相比,无论从SDN路由机制的有效性还是网络运行时延吞吐量等相关性能方面都有不可替代的优势;与监督学习相比,强化学习不仅不需要标签训练数据,同时还可以根据网络管理需求,灵活地调整优化目标.后期我们应该将研究重点放在强化学习在路由优化方面的应用上.

5.2 未来展望

目前,寻找一种自适应的实时路由策略将成为互联网的研究热点之一,还有很多问题需要我们深入研究,下面对其未来研究重点和发展趋势进行探讨.

Table 3 Performance Analysis of ML Algorithm in SDN Routing Optimization
表3 SDN路由优化中的ML算法的性能分析

AlgorithmReferenceAdvantageDisadvantageAnalysisNNRef [24-25]① Be able to train high-dimensional datasets;② Be able to approximate an arbitrary function;③ Once trained,prediction is fast.① Due to the need for tuning a large number of parameters, the calculation is expensive;② Black box process, the output results are difficult to interpret;③ There are few theoretical guidelines for setting the optimal NN structure such as the number of layers and nodes.DNNRef [21,23]① Be able to train high-dimensional datasets;② Be able to provide better performance.① Require a lot of computational resources;② Training is expensive.RNNRef [26,41]① Have long-term and short-term memory.① When the input sequence time is too long, there are gradient disappearance and gradient explosion problems.SVMRef [27]① Be able to solve high-dimensional problems;② Work well on both linearly separable and non-linearly separable datasets.① Hard to train large datasets because the calculation complexity is high;② Hard to solve multi-classification problems with SVM.① Need tag data;② Use heuristic algorithms as datasets to train ML models with high computational complexity;③ Perceive and classify the traffic in advance and calculate the forwarding path in real time, which can reduce network delay, improve throughput and improve network performance.RLRef [32,35]① Work well without precise and solvable mathematical models;② Once trained, decision making is fast.① Low convergence rate for optimal behavior strategies;② Hard to solve the problem of high-dimensional state and action space.DRLRef [38-39,42]① Be able to solve the problem of high-dimensional state and action space;② Once trained, decision making is fast.① Need a lot of computational resources to train the model;② Training is expensive.① No tag data required;② According to network requirements,adjust goals flexibly;③ Implement global, real-time, custom intelligent control and management to the network;④ Have good convergence and effectiveness.

1) 数据驱动认知路由

数据驱动网络(data-driven networking, DDN)[45]集成了过去的知识,可以更快、更高效地计算网络算法.它的主要作用是计算和处理大量可用的数据.

在基于DDN的控制循环中,通过实时收集的数据自动调整驱动算法,进行自动化决策.数据驱动的方法促进了有趣且快速的启发式,其性能可能优于现有的优化或近似算法.更重要的是,数据驱动的方法适应并优化了网络的实际状态,以网络观察数据为主要特征,而不是针对某些假设的最坏情况的网络状态[45-46].

随着互联网的飞速发展,网络业务需求不断增加,网络规模不断扩大,网络结构、网络管理、调度诊断等问题变得更加复杂,用户对网络的要求也越来越高,需要网络具有自适应、自管理、自学习和推理等功能,即具备认知功能[47].文献[48]在网络中引入知识平面,使网络可以通过认知技术,在复杂、不一致、动态和不断发展的环境中有效执行并评估和改进自身的性能.与此同时,基于数据驱动的人工智能近年来取得一定进步,由于在网络中积累了大量的数据,我们可以通过这些数据,再应用机器学习进行大量的训练,将数据转换成知识,在复杂不确定的环境中做出路由决策和优化.我们的目标是建立新一代网络,这个网络可以驱动自己的部署和配置,可以诊断自己的问题,并就如何解决问题做出合理的决定.如果成功,将大大简化日常网络管理任务.

2) 基于迁移学习的路由优化

迁移学习[49]的任务是从一个环境中学习知识和经验,并应用到新的任务中.换言之,迁移学习的目的就是从一个或多个源任务中抽取知识、经验,然后运用到目标领域中去.在大数据时代,每天都会产生大量的数据,如何合理地利用这些数据是迁移学习需要解决的问题.在SDN路由优化中,通过强化学习技术得到自适应路由路径,在训练收敛之前训练开销很大,且当新的应用服务出现时需要重新训练,这无疑对计算机网络性能带来一定弊端.如果将之前训练好的路由优化策略模型迁移到新的网络环境中,然后利用少量的数据进行训练即可快速收敛,这样当出现新的服务时也不用重头进行训练收敛,减少了训练开销.

3) QoE感知路由

目前,QoS是最广泛使用的服务度量标准,其评价指标主要包括丢包率、时延、抖动和吞吐量等.这些指标通常被网络运营商用来评估网络性能.根据1~4节对机器学习在SDN路由方面的研究调研,我们发现大多数研究都是以QoS为优化目标寻找一条合适的路由路径,以达到最小时延、丢包率等性能.但是从整个生态平衡的角度来看,不管是运营商还是整个生产链,再到最后的互联网公司都需要和用户打交道,他们都有共同的目标,就是为了更好的用户体验以及用户满意度.QoE[50-51]是用户对服务满意度的主观度量标准.典型的QoE度量有平均意见得分(mean opinion score, MOS),可以由真实用户根据主观评分确定,也可以根据对交付的商品(例如音频、视频或文件)的属性进行客观测量来预测.MOS将QoE的主观感受分为优、良、中、次、劣5个级别[52].由于QoE值一般以线性方式依赖于多个QoS指标[53],网络指标(如数据包丢失)会根据服务类型的不同影响此类服务的QoE,因此我们可以通过发现QoS参数和QoE值之间的相关定量性来实时获取QoE值.

文献[54]设计了一种基于蚁群优化的启发式算法,以QoE为中心路由,根据流量和网络需求为不同的多媒体服务类型及其流计算最佳可用路径,以使用户QoE最大化.受此启发,我们可以根据历史数据学习QoS参数和QoE值之间的关系,对QoE进行预测.利用机器学习对SDN路由进行优化,以QoE为目标,对网络进行灵活的配置,实现QoE感知路由,最大化网络性能和用户满意度.

6 结束语

对SDN路由功能的优化是时代发展的必然产物,也是用户对网络性能稳定性的一种要求.通过对网络路由的不断优化,提高对网络资源的利用率,保证网络信息的服务质量,不断优化计算机网络性能,从而为更多的网络用户带来更好的体验.

参考文献

[1] Liu Jiamei, Xu Qiaozhi. Machine learning in software defined network[C] //Proc of the 3rd IEEE Information Technology, Networking, Electronic and Automation Control Conf (ITNEC). Piscataway, NJ: IEEE, 2019: 1114-1120

[2] Zuo Qingyun, Chen Ming, Zhao Guangsong, et al. Research on OpenFlow-based SDN technologies[J]. Journal of Software, 2013, 24(5): 1078-1097 (in Chinese)

(左青云, 陈鸣, 赵广松, 等. 基于OpenFlow的SDN技术研究[J]. 软件学报, 2013, 24(5): 1078-1097)

[3] Mohammed M, Khan M, Bashier E. Machine Learning: Algorithms and Applications[M]. Boca Raton, FL: CRC Press, 2016

[4] Xie Junfeng, Yu F R, Huang Tao, et al. A survey of machine learning techniques applied to software defined networking (SDN): Research issues and challenges[J]. IEEE Communications Surveys & Tutorials, 2019, 21(1): 393-430

[5] Meng Xiaofeng, Ci Xiang. Big data management: Concepts,techniques and challenges[J]. Journal of Computer Research and Development, 2013, 50(1): 146-169 (in Chinese)

(孟小峰, 慈祥. 大数据管理: 概念、技术与挑战[J]. 计算机研究与发展, 2013, 50(1): 146-169)

[6] Zhang Shunmiao, Zou Fumin. Survey on software defined network research[J].Application Research of Computers, 2013, 30(8): 2246-2251 (in Chinese)

(张顺淼, 邹复民. 软件定义网络研究综述[J]. 计算机应用研究, 2013, 30(8): 2246-2251)

[7] Zhang Shaojun, Lan Julong, Hu Yuxiang. Survey on scalability of control plane in software-defined networking[J]. Journal of Software, 2018, 29(1): 160-175 (in Chinese)

(张少军, 兰巨龙, 胡宇翔, 等. 软件定义网络控制平面可扩展性研究进展[J]. 软件学报, 2018, 29(1): 160-175)

[8] Gao Cong. Research on optimization of routing algorithm in SDN architecture[D]. Xi’an: Xidian University, 2018 (in Chinese)

(高聪. SDN架构下路由算法的优化研究[D]. 西安: 西安电子科技大学, 2018)

[9] Zhu Shangming. Multipath QoS routing schemes for end-to-end networks[D]. Shanghai: East China University of Science and Technology, 2007 (in Chinese)

(朱尚明. 端到端网络的多路径QoS路由机制研究[D]. 上海: 华东理工大学, 2007)

[10] Wu Yan. Research on intelligent SDN routing optimization technology based on traffic classification[D]. Hangzhou: Zhejiang Gongshang University, 2019 (in Chinese)

(吴艳. 基于流量分类的智能SDN路由优化技术研究[D]. 杭州: 浙江工商大学, 2019)

[11] Okumus I T, Mantar H A, Hwang J, et al. Inter-domain QoS routing on diffserv networks: A region-based approach[J]. Computer Communications, 2005, 28(2): 174-188

[12] Yan Jinyao, Zhang Hailong, Shuai Qianjun, et al. HiQoS: An SDN-based multipath QoS solution[J]. China Communications, 2015, 12(5): 123-133

[13] Kong Xiangbin, Shen Subin, Li Li. A QoS routing scheme based on software-defined networking[J]. Computer Technology and Development, 2018, 28(2): 102-106 (in Chinese)

(孔祥彬, 沈苏彬, 李莉. 一种基于SDN网络的QoS路由选择方案[J]. 计算机技术与发展, 2018, 28(2): 102-106)

[14] Nong Huangwu, Huang Chuanhe, Huang Xiaopeng. SDN-based multipath routing algorithm for fat-tree data center networks[J]. Computer Science, 2016, 43(6): 32-34 (in Chinese)

(农黄武, 黄传河, 黄晓鹏. 基于SDN的胖树数据中心网络的多路径路由算法[J]. 计算机科学, 2016, 43(6): 32-34)

[15] Egilmez H E, Dane S T, Bagci K T, et al. OpenQoS: An OpenFlow controller design for multimedia delivery with end-to-end quality of service over software-defined networks[C] //Proc of the 2012 Asia Pacific Signal and Information Processing Association Annual Summit and Conf. Piscataway, NJ: IEEE, 2012: 1-8

[16] Yao Haipeng, Mai Tianle, Xu Xiaobin, et al. NetworkAI: An intelligent network architecture for self-learning control strategies in software defined networks[J]. IEEE Internet of Things Journal, 2018, 5(6): 4319-4327

[17] Mestres A, Rodriguez-Natal A, Carner J, et al. Knowledge-defined networking[J]. SIGCOMM Computer Communications Review, 2017, 47(3): 2-10

[18] Mestres A, Alarcón E, Ji Yusheng et al. Understanding the modeling of computer network delays using neural networks[C] //Proc of the 2018 Workshop on Big Data Analytics and Machine Learning for Data Communication Networks. New York: ACM, 2018: 46-52

[19] Xie Xiaoming, Wang Xingwen, Wen Zhankao, et al. A QoS routing protocol for cognitive networks[J]. Chinese Journal of Computers, 2013, 36(9): 1807-1815 (in Chinese)

(谢小民, 王兴伟, 温占考, 等. 一种面向认知网络的QoS路由协议[J]. 计算机学报, 2013, 36(9): 1807-1815)

[20] Kotsiantis S B. Supervised machine learning: A review of classification techniques[C] //Proc of the 2007 Conf on Emerging Artificial Intelligence Applications in Computer Engineering: Real Word AI Systems with Applications in eHealth, HCI, Information Retrieval and Pervasive Technologies. Amsterdam, the Netherlands: IOS Press, 2007: 3-24

[21] Valadarsky A, Schapira M, Shahaf D, et al. Learning to route[C] //Proc of the 16th ACM Workshop on Hot Topics in Networks. New York: ACM, 2017: 185-191

[22] Mao Bomin, Fadlullah Z M, Tang Fengxiao, et al. Routing or computing? The paradigm shift towards intelligent computer network packet transmission based on deep learning[J]. IEEE Transactions on Computers, 2017, 66(11): 1946-1960

[23] Reis J, Rocha M, Phan T K, et al. Deep neural networks for network routing[C] //Proc of 2019 Int Joint Conf on Neural Networks (IJCNN). Piscataway, NJ: IEEE, 2019: 1-8

[24] Li Yanjun, Li Xiaobo, Osamu Y. Traffic engineering framework with machine learning based meta-layer in software-defined networks[C] //Proc of the 4th IEEE Int Conf on Network Infrastructure and Digital Content. Piscataway, NJ: IEEE, 2014: 121-125

[25] Azzouni A, Boutaba R, Pujolle G. NeuRoute: Predictive dynamic routing for software-defined networks[C] //Proc of the 13th Int Conf on Network and Service Management (CNSM). Piscataway, NJ: IEEE, 2017: 1-6

[26] Liu Chang, Malboubi A, Chuah C. OpenMeasure: Adaptive flow measurement & Inference with online learning in SDN[C] //Proc of 2016 IEEE Conf on Computer Communications Workshops (INFOCOM WKSHPS). Piscataway, NJ: IEEE, 2016: 47-52

[27] Thomas V P S, Prasad S S, Kataoka K. AMPF: Application-aware multipath packet forwarding using machine learning and SDN[J]. ArXiv, 2016,abs/1606.05743, 2016

[28] Kim H, Claffy K C, Fomenkov M, et al. Internet traffic classification demystified: Myths, caveats, and the best practices[C] //Proc of ACM Conf on Emerging Network Experiment & Technology. New York: ACM, 2008: 1-12

[29] Jin Y Y. Finding the k shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716

[30] Sutton R S, Barto A G. Reinforcement Learning: An Introduction[M]. Cambridge, MA: MIT Press, 1998

[31] Watkins C, Christopher J, Dayan P. Q-learning[J]. Machine Learning, 1992, 8(3/4): 279-292

[32] Lin S, Akyildiz I F, Wang Pu, et al. QoS-Aware adaptive routing in multi-layer hierarchical software defined networks: A reinforcement learning approach[C] //Proc of 2016 IEEE Int Conf on Services Computing (SCC). Piscataway, NJ: IEEE, 2016: 25-33

[33] Yeganeh S H, Ganjali Y. Kandoo: A framework for efficient and scalable offloading of control applications[C] //Proc of the 1st Workshop on Hot Topics in Software Defined Networks. New York: ACM, 2012: 19-24

[34] McCauley J, Panda A, Casado M, et al. Extending SDN to large-scale networks[J]. ONS, 2013, 58(2): 50-51

[35] Sendra S, Rego A, Lloret J, et al. Including artificial intelligence in a routing protocol using Software Defined Networks[C] //Proc of 2017 IEEE Int Conf on Communications Workshops (ICC Workshops). Piscataway, NJ: IEEE, 2017: 670-674

[36] Xu Zhiyuan, Tang Jian, Meng Jingsong, et al. Experience-driven Networking: A deep reinforcement learning based approach[C] //Proc of IEEE Conf on Computer Communications(IEEE INFOCOM 2018). Piscataway, NJ: IEEE, 2018: 1871-1879

[37] Hajlaoui R, Guyennet H, Moulahi T. A survey on heuristic-based routing methods in vehicular ad-hoc network: Technical challenges and future trends[J]. IEEE Sensors Journal, 2016, 16(17): 6782-6792

[38] Stampa G, Arias M, Sanchez-Charles D, et al. A deep-reinforcement learning approach for software-defined networking routing optimization[J].ArXiv, 2017, abs/1709.07080, 2017

[39] Yu Changhe, LanJulong, Guo Zehua, et al. DROM: Optimizing the routing in software-defined networks with deep reinforcement learning[J]. IEEE Access, 2018, 6: 64533-64539

[40] Lillicrap T, Hunt J, Pritzel A, et al. Continuous control with deep reinforcement learning[J]. CoRR, 2015,abs/1509.02971, 2015

[41] Sun P, Li Junfei, Lan Julong, et al. RNN deep reinforcement learning for routing optimization[C] //Proc of the 4th IEEE Int Conf on Computer and Communications (ICCC). Piscataway, NJ: IEEE, 2018: 285-289

[42] Witanto J N, Lim H. Software-defined networking application with deep deterministic policy gradient[C] //Proc of the 11th Int Conf on Computer Modeling and Simulation. New York: ACM, 2019: 176-179

[43] Silver D, Huang A, Maddison C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489

[44] Lan Julong, Yu Changhe, Hu Yuxiang, et al. A SDN routing optimization mechanism based on deep reinforcement learning[J]. Journal of Electronics and Information Technology, 2019, 41(11): 2669-2674 (in Chinese)

(兰巨龙, 于倡和, 胡宇翔, 等. 基于深度增强学习的软件定义网络路由优化机制[J]. 电子与信息学报, 2019, 41(11): 2669-2674)

[45] Jiang J, Sekar V, Stoica I, et al. Unleashing the potential of data-driven networking[C] //Proc of Int Conf on Communication Systems and Networks. Berlin: Springer, 2017: 110-126

[46] Kellerer W, Kalmbach P, Blenk A, et al. Adaptable and data-driven softwarized networks: Review, opportunities, and challenges[J]. Proceedings of the IEEE, 2019, 107(4): 711-731

[47] Cao Jian, Wang Xingwei, Zhang Jinhong, et al. A data driven cognitive routing protocol for information-centric networking[J]. Journal of Computer Research and Development, 2015, 52(4): 798-805 (in Chinese)

(曹健, 王兴伟, 张金宏, 等. 数据驱动的信息中心网络认知路由协议[J]. 计算机研究与发展, 2015, 52(4): 798-805)

[48] Clark D D, Partridge C, Ramming J C, et al. A knowledge plane for the Internet[C] //Proc of the 2003 Conf on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2003: 3-10

[49] Pan S J, Yang Qiang. A survey on transfer learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(10): 1345-1359

[50] Abar T, Letaifa A B, Asmi S E. Machine learning based QoE prediction in SDN networks[C] //Proc of the 13th Int Wireless Communications and Mobile Computing Conf (IWCMC). Piscataway, NJ: IEEE, 2017: 1395-1400

[51] Letaifa A B. Adaptive QoE monitoring architecture in SDN networks: Video streaming services case[C] //Proc of the 13th Int Wireless Communications and Mobile Computing Conf (IWCMC). Piscataway, NJ: IEEE, 2017: 1383-1388

[52] Lin Chuang, Hu Jie, Kong Xiangzhen. Survey on models and evaluation of quality of experience[J]. Chinese Journal of Computers, 2012, 35(1): 1-15 (in Chinese)

(林闯, 胡杰, 孔祥震. 用户体验质量(QoE)的模型与评价方法综述[J]. 计算机学报, 2012, 35(1): 1-15)

[53] Fiedler M, Hossfeld T, Tran-Gia P. A generic quantitative relationship between quality of experience and quality of service[J]. IEEE Network, 2010, 24(2): 36-41

[54] Dobrijevic O, Santl M, Matijasevic M. Ant colony optimization for QoE-centric flow routing in software-defined networks[C] //Proc of the 11th Int Conf on Network and Service Management (CNSM). Piscataway, NJ: IEEE, 2015: 274-278

A Review on the Application of Machine Learning in SDN Routing Optimization

Wang Guizhi1, Lü Guanghong1, Jia Wucai1, Jia Chuanghui1, and Zhang Jianshen2

1(College of Computer Science, Sichuan University, Chengdu 610065) 2(Unit 7584, Guilin, Guangxi 541001)

Abstract With the rapid development of network technology and the continuous emergence of new applications, the sharp increase in network data makes network management extremely complicated. Devices in traditional networks are diverse, complex in configuration, and difficult to manage, but the appearance of a new network architecture, such as software defined networking (SDN), brings dawn to network management, which gets rid of the limitation of hardware equipment to the network, and makes the network have the advantages of flexibility, programmability and so on. A good routing mechanism affects the performance of the whole network, the centralized control characteristics of SDN bring new research directions to the application of machine learning in routing mechanisms. First this paper discusses the current status of SDN routing optimization, and then summarizes the research on machine learning in SDN routing in recent years from the aspects of supervised learning and reinforcement learning. Finally, in order to meet the QoS (quality of service) of different applications and QoE (quality of experience) of different users, this paper puts forward the development trend of the data driven cognitive route. Giving the network nodes with cognitive behaviors such as perception, memory, search, decision-making, reasoning, explanation and so on, can speed up the path-finding process, optimize the route selection and improve the network management.

Key words software defined networking (SDN); supervised learning; reinforcement learning; routing optimization; quality of service (QoS); quality of experience (QoE); data driven; cognitive

(lghong@scu.edu.cn)

中图法分类号 TP393

收稿日期2019-12-08;

修回日期:2020-02-21

基金项目国家自然科学基金项目(61373091)

This work was supported by the National Natural Science Foundation of China (61373091).

通信作者王桂芝(1552782252@qq.com)

Wang Guizhi, born in 1996. Master. Student member of CCF. Her main research interests include software defined network and machine learning.

Lü Guanghong, born in 1963. PhD, professor. His main research interests include software defined network, cloud computing, data center network and wireless network, etc.

Jia Wucai, born in 1996. Master. Student member of CCF. Her main research interests include software defined network and deep learning. (910091702@qq.com)

Jia Chuanghui, born in 1987. Master. His main research interests include SDN and deep learning. (huanghui1987@163.com)

Zhang Jianshen, born in 1988. Bachelor, assistant engineer. His main research interests include computer network, artificial intelligence and digital communication. (594926581@qq.com)