SDN驱动的网络流量负载均衡路由优化算法

闵晓飞, 李 靖, 张朝辉

(西安电子科技大学数学与统计学院, 陕西 西安 710126)

0 引 言

5G网络是新一代移动通信网络,其主要目标是在提升网络数据流传输效率的同时优化网络资源分配效率、减少网络运营支出成本(operating expenditure, OPEX)等[1]。5G网络主要由3部分组成:无线接入网(radio access network, RAN)、核心网(core network, CN)以及软件定义网络(software-defined networking, SDN)[2]。作为5G通信网络拓扑系统的重要组成部分,SDN分离了网络的数据层和控制层[3-8],使得跨异构设备和网络去配置服务质量(quality of service, QoS)变得可行,并且可以通过控制网络中的流量负载机制完成不同网络资源的分配优化,实现了从设备可编程到网络可编程的转变,为研发网络新应用和未来互联网技术提供了一种新的解决方案。

传统的网络资源分配问题大多侧重于任务卸载和网络开销之间的权衡,以保证网络QoS或最小化网络开销为目标[9-10]。文献[11]针对用户资源申请与网络可用资源最优配置问题,建立了基于SDN的资源分配多目标优化模型,满足了不同用户的QoS需求。文献[12]提出了一种SDN控制器上的强化学习方案,旨在最小化网络链路的最大利用率,从而减少网络服务中断干扰。文献[13]提出了一种基于接收器的拥塞控制方案—RecFlow,该方案利用OpenFlow提供的路径可见性来解决数据中心传输问题。文献[14]通过评估SDN,利用散列函数来调度数据流,对拥塞较少的路径进行优先排序,优化了数据传输效率。

文献[15]提出了一种基于SDN的复杂多路径数据传输优化策略—HiQoS,该策略通过改进Dijkstra算法优化了数据多路径转发效率。文献[16]利用类似的方法,选择具有最大带宽和可用性的路径,提出了一种自适应多路径供应方案。在文献[17]中,Al-Najjar等初步探讨了在静态链路情况下如何更好地使用SDN控制多宿主终端主机中的网络流。文献[18]采用不同的流量负载均衡算法进一步在动态链路容量的网络场景中扩展了这一贡献。

现代优化算法是一种操作性强且优化率高的求解方式,近年来在网络资源分配问题中被广泛应用。在文献[19]中,Zhang等提出了一种基于模糊逻辑的资源分配(fuzzy logic-based resource allocation, FUZZRA)算法,该算法能够充分利用物理层资源,在不造成明显干扰的情况下最大限度地重复利用有限的资源。文献[20]提出了一种基于最小代价路径的交换机迁移算法,根据流量负载预测矩阵确定迁出控制器和目标控制器集合。

文献[21]基于SDN集中管理和控制的特点,在网络正常运行情况下,结合遗传算法中交叉和变异的思想,使用改进的粒子群优化算法合理优化网络资源分配;对于流量过载的紧急情况,提出了一种基于软件定义广域网(software defined wide area network, SD-WAN)的定期调度方法,以解决通信中的“潮汐效应”问题。此外,还有很多算法将遗传算法和其他智能优化算法进行了融合,详见文献[22-24],这些算法都取得了非常优异的效果。

SDN控制的QoS感知多路径传输控制协议 (multipath transmission control protocol, MPTCP)问题是资源分配中常见的目标优化问题。文献[25]设计了一种名为延迟均衡快速(delay-equalized FAST, DEFT)的MPTCP拥塞控制算法,该算法包括一种适用于5G网络的窗口控制方案和延迟均衡方案,在吞吐量和端到端延迟方面具备非常优越的性能。Wang等[26]探索了在虚拟网络中调度MPTCP流的多路径转发问题。但是,MPTCP将一个流拆分为多个子流转发到多个路径中,这对于移动用户而言处理起来很复杂。

通过提高网络流量迁移效率来完成资源分配优化也是常见的研究手段。文献[27]提出了一种基于模糊多目标粒子群算法的动态切换迁移策略,该方案综合考虑了网络流量迁移的OPEX、效率与均衡性,但算法的运算量和数据的存储量都很大,鲁棒性较低。为了解决控制层的流量负载均衡问题,Kim等[28]提出了一种递进和声搜索(progre-ssive-harmony search, P-HS)启发式算法,该算法有效解决了分布式SDN环境中的资源动态控制、供应问题,最大程度减少了交换机与控制器之间的通信时延。

文献[29]从用户和网络运营商的角度探讨了执行计划(execution plans, EPs)的有效实施,并针对流量分配过程制定了3种不同的启发式算法。此外,还提出了评估标准,以研究链路带宽和运营商成本约束下EPs的效率。文献[30]提出了一种用于支持SDN的边缘网络中动态任务调度和分配的深度强化学习方法,实现了网络低延迟,同时节省了能耗。文献[31]提出了一种端到端服务链编排系统,该系统可以基于网络的当前负载迅速调整已建立的服务链路径,以解决可靠性问题。

随着5G时代的到来,组网规模和用户数量急剧增加,这就导致部署网络功能设备的开销越来越大,同时也出现了5G网络底层设备运行管理困难、失效率高等问题。Bagaa等引入QoS感知的网络配置和多路径转发协议,通过考虑用户的移动环境以及QoS需求提出了一种启发式路径重计算(heuristic paths re-computation, HPR)算法[2]。该算法在满足合理计算时间的前提下,降低了网络OPEX,使得运营商在支持SDN的网络中,能够在考虑移动性的情况下有效地分配网络资源、减少甚至消除过度供应。然而,文献[2]并没有考虑网络整体流量负载均衡和资源利用率联合的问题,无法直接用于新的5G虚拟网络范式。

为了在满足用户多样性服务需求的同时确保网络QoS,本文提出了两种由SDN驱动的路由优化算法:负载均衡广度优先搜索(load balancing scheme with breadth-first-search, LBB)路径优化算法以及基于深度优先搜索的迭代深度搜索(iterative deepening search with depth-first-search, IDDFS)路径优化算法。LBB算法首先将用户接入的所有eNodeB节点看作一个超级源节点并进行数据的接入,在保证满足用户服务请求的同时满足网络QoS,然后在传统广度优先搜索(breadth-first-search, BFS)算法的基础上设定了一个动态流量负载均衡控制阈值。当网络检测到链路流量负载均衡参数超过实时动态流量阈值时,再次优化路径分配,在保证OPEX的同时提高了网络资源的利用率。而IDDFS算法在每次数据传输路径搜索中对搜索深度进行限制,在当前限制的深度下以最大带宽优先搜索目标节点,如果搜索不到目标节点,则增加深度重新进行搜索,直至找到目标节点。

IDDFS算法通过迭代去找寻可行解,如果在寻路的两点之间不存在可行解,算法在搜索最优路径时会没有方向地一直增加深度,陷入循环,影响算法执行效率。而在LBB算法中,一旦搜索不到目标节点,算法会立即终止此次搜索,不再进行迭代,保证算法后续的运行,在满足合理计算时间的前提下实现负载均衡;而相较于LBB算法,IDDFS算法在保证负载均衡的同时有效地缩减了空间开销。

1 网络模型与系统建模

1.1 网络模型

本文将5G网络抽象为一个带权有向图G(V,E,W),其中E代表网络中边的集合,W表示带宽集合,V=C∪O∪R∪S代表网络中节点的集合,C、O、R、S分别代表用户集、开放式虚拟交换机(open virtual switch,OVS)的集合、建立的超级源节点以及超级汇点(终端服务器)。E中边(u,v)的权值wu,v代表节点u和节点v之间的带宽容量。详细的符号对照表如表1所示。

表1 符号对照表

网络拓扑示意图如图1所示,假设每个用户c与网络接入通信节点eNodeB间的通信方式是无线(虚线)的;不同OVS之间的通信是有线(实线)的;对于用户和服务器之间的通信方式,客户端和接入点eNodeB之间的第一跳是无线接口,而通向服务器的其余网络链路是有线的。

图1 网络拓扑示意图Fig.1 Network topology skematic diagram

1.2 问题的数学建模

(1)

(2)

(3)

∀i∈C∪O,∀j∈η(i)∩(O∪S):

Ti,j≤wi,j×xi,j

(4)

(5)

式(2)表示每个用户只能连接到一个相应的OVS来接收和传输数据流量;式(3)表示链路中每一跳转发的数据流量等于用户申请的数据流量,并且输入流量等于输出流量;式(4)表示实际转发的流量不能超过两个节点之间的链路带宽上限;式(5)表示客户端和服务器之间的数据传输路径不存在任何环路。

由于上述的数学模型是一个NP难问题,因此本文将通过两个近似优化算法LBB以及IDDFS对该模型进行求解。

2 LBB优化算法

文献[2]基于Dijkstra算法提出了改进的HPR算法,在较短的时间内实现了用户和服务器之间的最优路径分配。然而该算法一旦选择了接入点,数据传输路径会一直被使用到与该接入点相连的链路带宽不满足用户申请的带宽要求时才停止,导致网络中的其他节点一直处于休眠状态,造成了休眠状态节点资源的浪费,降低了资源分配效率。

为了避免局部流量负载过大,同时提高节点资源利用率,并且尽可能地减少网络OPEX,LBB算法在实现过程中加入了一个动态流量负载均衡阈值,具体路径优化过程如算法1所示。

算法 1 LBB算法输入:G(V,E,W),C,S输出:Φ,Pc,sBegin(1) Φ=ϕ(2) For c∈C V1=V E1=E(3) For o∈η(c)∩O If wc,o<λt V1=V1o End if End for(4) For(u,v)∈E1If wu,v<λt E1=E1(u,v)End ifEnd for(5) While true do If ∃o∈O∩V1-{c}∧|η(o)|≤1 V1=V1o Else Break End ifEnd while(6) MATOLIST(V1,E1)BFS(R,S,V1,E1,W)Source=R(7) If c==1 Pc,s= BFS(R,S,V1,E1,W) ElseWhile Source !=S If σ<φ Source=Next Pc,s=Pc,s∪Source Else E1wSource,next BFS(Source,S,V1,E1,W) Φ=Φ∪(Pc,s∩O) End if End while End if(8) For(u,v)∈Pc,s wu,v=wu,v-λt End for End forEnd

定义流量负载均衡参数公式

(6)

根据实验,本文选取流量负载均衡参数的中位数φ为动态流量负载均衡控制阈值。算法开始时,初始化Φ为空集,然后执行一个循环,以计算并存储用户和终端服务器之间的数据传输路径。在算法内部循环中,为了避免路径拓扑中的V和E在计算新路径时被覆盖而丢失路径信息,将两个临时变量集合V1和E1分别初始化为V和E。算法1中的步骤(3)～步骤(5)移除了不满足转发条件的链路和节点。

接下来,步骤(6)和步骤(7)执行寻找用户c和终端服务器S之间的路径进程,从超级源点R进行BFS,若此时是第一个用户,则直接存储其路径,否则将Source记作接入点;如果Source到下一个节点的链路流量负载参数小于φ,则把下一个节点标记为Source,否则暂时屏蔽此路径;从Source重新进行BFS,直至搜索到S,则输出最终使用的OVS集合,并更新权值进行下一轮搜索。

图2分别给出了HPR算法和LBB算法实现过程的网络拓扑示例。假设一个移动网络由4个eNodeB、1组编号为1到8的OVS节点和2个服务器(Sever)组成。网络初始配置如图2(a)、图2(d)所示,删除所有已用资源得到当前拓扑图G,其中不满足用户申请带宽要求的链路用红色表示。如图2(b)所示,在HPR算法中,当用户1申请接入网络时,由于此时没有接入点eNodeB,则按照定义的权值使用Dijkstra算法进行寻路,得到最终路径上使用的虚拟节点是OVS 1和OVS 4,将OVS 1选为接入点。如图2(c)所示,当用户2接入网络时,由于此时基站eNodeB1和OVS 1之间的带宽仍然满足条件,因此仍然选择OVS 1作为接入点,继续使用Dijkstra算法进行寻路,最终激活了OVS 1、OVS 4,以进行数据传输。

图2 HPR算法和LBB算法拓扑示例Fig.2 Topology examples of HPR algorithm and LBB algorithm

LBB算法在保证网络QoS的前提下将所有的eNodeB节点映射为一个超级源点,对接入节点的资源进行统一分配控制,超级源点可以动态地选择与OVS 1、OVS 2、OVS 3建立数据传输链路。在图2(e)中,当用户1申请接入网络时,选择OVS 1作为接入点直接进行BFS,此时网络激活OVS 1和OVS 4。如图2(f)所示,当用户2申请接入网络时,仍然选择OVS 1作为接入点。当选取OVS 4作为下一个节点时,监测到流量负载参数大于实时动态阈值φ,则回溯到OVS 1,从OVS 1重新进行BFS搜索到OVS 7,激活了OVS 1、 OVS 4、OVS 7,以进行数据传输。

3 IDDFS优化算法

LBB算法旨在通过链路动态控制阈值和搜索回溯的方法优化路径配置,使网络链路流量处于均衡的状态。在BFS实现的过程中,每一步都需要存储当前节点所连接的所有节点以及路径信息。然而,随着网络拓扑规模的扩大,这会造成非常大的空间开销,这种以空间换取时间的方法会影响算法的有效性。为了降低算法的空间开销,进一步提出了一种IDDFS优化算法。在IDDFS算法中,每次搜索都对搜索深度进行限制,并在搜索过程中选择可用带宽最大的链路,如果在当前限制深度下搜索不到目标节点,则增加一层深度重新进行搜索,直至找到目标节点。由于搜索深度是从小到大递增的,因此可以保证所得解深度最小,且缩减了空间开销。

IDDFS算法的具体路径优化过程如算法2所示,初始化后与算法1相同,执行步骤(3)～步骤(5),对虚拟网络拓扑进行优化处理。在步骤(6)中,从给定的最小深度mindepth开始,按照带宽大小进行深度优先搜索,如找到目标节点(即服务器S),则输出搜索路径,否则加一跳深度继续搜索下一层,直至搜索到S。

End if End for(4) For(u,v)∈E1If wu,v<λt E1=E1(u,v) End if End for(5) While true do If ∃o∈O∩V1-{c}∧|η(o)|≤1 V1=V1o Else Break End if End while(6) For(i=mindepth;; i++) Pc,s= DFS(R,S,V1,E1,W) If Pc,s[last]==S Break End if End for

图3给出了LBB算法和IDDFS算法的网络拓扑实现过程示例图。如图3(a)所示,在LBB算法中,当用户1申请接入10 Mbps的带宽时,直接进行BFS搜索。在搜索过程中,OVS 1、OVS 2、OVS 3、OVS 4、OVS 5、OVS 7、OVS 6、OVS 9按层次存储在堆栈中。最后,激活的节点是OVS 1、OVS 4。而在IDDFS算法中,每次搜索之前都会设置一个最小搜索深度。如在图3(c)中,如果设置最小搜索深度为2,选择OVS 1和OVS 7存储在堆栈中,但是不能找到目标结点(即服务器节点 9),则需要将最小搜索深度增加1,再次进行DFS搜索,此时存储的虚拟节点为OVS 1、OVS 7、OVS 9,最终激活了OVS 1、OVS 7进行数据传输。虽然两个算法激活的OVS数量都是两个,但IDDFS算法在寻路过程中需要的堆栈存储空间比LBB算法少得多。

图3 LBB算法和IDDFS算法拓扑示例Fig.3 Topology examples of LBB algorithm and IDDFS algorithm

4 仿真实验

为了验证所提算法的有效性,本文通过多次重复实验,将LBB算法、IDDFS算法、HPR算法与经典的Dijkstra算法从激活的OVS数与网络吞吐量两个指标进行仿真比较。网络吞吐量的计算方式为WC×h,其中WC为接入用户申请的带宽,h为最终选择路径的跳数。实验的仿真环境为Win10 64位系统、CPU处理器Intel Core i5-4300U 2.50 GHz,内存4.00 GB,仿真软件Matlab2020b、Visual Studio 2022。具体实验方案为:① 固定OVS个数,改变接入用户的数量;② 固定用户数,改变网络中OVS的数量。

4.1 动态流量负载均衡控制阈值对资源利用率的影响

在第2节中,本文给出了流量负载均衡参数σ(t)的定义,其代表第t个用户接入网络时活跃链路利用率的标准差。σ(t)值越小,代表网络负载越均衡;反之,其值越大,表示链路负载差别越大,即负载不均衡。在LBB算法中,本文通过实验验证了阈值为中位数时算法性能最优。如图4所示,该实验给出了接入用户个数从10到100时不同阈值对LBB算法性能的影响。

图4 不同阈值对LBB算法的影响Fig.4 Impact of different thresholds on LBB algorithm

在仿真实验中,固定网络中的OVS数量为25,网络拓扑中的链路带宽上限在[100,180]Mb区间服从随机分布,接入带宽区间为[10,30]M。实验模拟了多个用户申请不同接入带宽大小时资源利用率在两种不同阈值下的性能对比:① 选用每个用户接入时当前负载均衡参数σ(t)为阈值;② 将σ(t)与前(t-1)个负载均衡参数放在一起,取中位数φ作为阈值。

由图4可以看出,当接入用户数从10增加到100时,选择中位数φ作为动态流量负载均衡控制阈值时算法优于选择σ(t)作为阈值时激活的OVS数,平均OVS利用率分别为31.4%和25.5%,前者平均利用率高出后者约6%。因此,本文选择中位数φ作为动态流量负载均衡控制阈值。

4.2 固定OVS个数及改变接入用户数对不同解决方案的影响

图5给出了接入用户个数从10到100对HPR算法、LBB算法、IDDFS算法以及Dijkstra算法性能的影响。在仿真实验中,固定网络中的OVS数量为25,网络拓扑中的链路带宽上限在[100,180]Mb区间服从随机分布,接入带宽区间为[10,30]Mb,实验模拟了多个用户申请不同大小的接入带宽时的性能。

图5 接入用户数对不同解决方案的影响Fig.5 Impact of number of clients on different solutions

从图5(a)可以看出,随着接入用户数量从10增加至100,Dijkstra算法激活的OVS数量从2增加至18,HPR算法从2增加至16,LBB算法从6增加至22,而IDDFS算法从7增加至23。LBB算法以及IDDFS算法的OVS使用数量始终多于HPR算法和Dijkstra算法,这是因为Dijkstra算法基于贪心思想在每次寻路时永远选择跳数最少的链路,而HPR算法则是倾向于复用已经激活的链路和OVS。一旦选择了接入点eNodeB,数据传输路径会一直被使用直至与该接入点相连的链路带宽不满足用户申请的带宽要求,才会重新配置网络,而LBB算法和IDDFS算法则是根据链路带宽的负载能力去进行路径选择,有效地提高了节点资源的利用率。在接入用户数量为70时,IDDFS算法首先进入稳定状态,此时不需要激活新的OVS。而当用户数大于80时,拓扑中的活跃链路带宽接近上限,此时IDDFS算法会选择新的OVS进行深度优先搜索,进一步优化了节点资源利用率。

从图5(b)可以看出,IDDFS算法的网络吞吐率最高。尤其在接入用户数超过70时,IDDFS的网络吞吐量优化率更高,这说明在大规模通信网络中,IDDFS算法具有更好的QoS。另外从图5可以看出,随着接入用户数的增加,Dijkstra算法的网络吞吐量近似线性增加,这是因为在寻路过程中,Dijkstra算法选择跳数最少的路径,而这样的路径在拓扑中存在多条。对比图5(a)可以看到,虽然Dijkstra算法激活的OVS数比HPR算法多,但是其吞吐量却是最低的,即便激活了新的OVS,Dijkstra算法在后续中继节点的选择中依然倾向于那些已经激活且可以实现更小跳数的OVS,而LBB算法和IDDFS算法则通过及时激活其余休眠OVS,有效解决了前期用户占用带宽以及网络带宽占用率倾斜所导致的流量负载不均衡问题,避免了节点资源的浪费。

4.3 固定用户数及改变网络中的OVS数量对不同解决方案的影响

图6给出了不同OVS数量对4种算法性能的影响。在图6(a)和图6(b)中,网络拓扑中的接入用户数固定为25;在图6(c)和图6(d)中,网络拓扑中的接入用户数固定为50。

图6 不同的OVS数量对不同解决方案的影响Fig.6 Impact of number of OVSs on different solutions

由图6(a)可以看出,当固定用户数量为25时,随着OVS数量的增多,Dijkstra算法激活的OVS数从8增加至18,HPR算法从7增加至16,LBB算法也从8增加至18,IDDFS算法从10增加至20。

从图6(b)可以看出,当OVS数量超过30时,其网络吞吐量增加速率达到最快,此时吞吐量增加率达到33.7%。LBB算法和IDDFS算法在OVS使用数以及网络吞吐量两项关键性能指标上均明显优于HPR算法和Dijkstra算法,这是因为HPR算法优先选择其先前已经激活的OVS构建数据通信路径,Dijkstra算法则是优先选择跳数最少的链路,造成了许多可用链路的浪费。这两种算法都容易造成部分路径的拥塞,从而导致数据的损失。LBB算法和IDDFS算法通过将网络中的数据流量均匀地分配到网络中的其他链路,有效地减少了路径拥塞的概率,提高了网络的吞吐量。

从图6(c)可以看出,当固定的用户数量为50时,Dijkstra算法激活的OVS数从7增加至18,HPR算法从7增加至16,LBB算法从10增加至23,IDDFS算法从15增加至35,IDDFS算法的资源利用率最大。

从图6(d)可以看出,Dijkstra算法的网络吞吐量从400 Mb增加至1 250 Mb,HPR算法的网络吞吐量从580 Mb增加至1 530 Mb,LBB算法的网络吞吐量从810 Mb增加至2 570 Mb,IDDFS算法的网络吞吐量从1 230 Mb增加至3 580 Mb。

表2给出了接入用户数为25时网络中OVS的平均使用数、最大利用率和平均利用率;表3给出了接入用户数为50时网络中OVS的平均使用数、最大利用率和平均利用率。图6以及表2、表3反映了当网络规模增大(当接入用户数从25增加至50)时,IDDFS算法的资源利用率以及网络吞吐量相较于其余3种算法的优化效果更加明显,IDDFS算法更适用于大规模通信网络的数据传输。

表2 OVS激活情况(接入用户25个)

表3 OVS激活情况(接入用户50个)

5 结 论

本文针对5G网络中支持SDN架构的资源分配优化问题,利用SDN架构的特点及优势,考虑网络流量负载均衡,改进了HPR算法。其中,LBB算法通过对虚拟网络设置动态流量负载均衡控制阈值的方式实时优化了网络链路的拓扑结构,而IDDFS算法通过限制每次搜索的深度,减少甚至避免了不必要的搜索,缩减了空间开销。LBB算法和IDDFS算法充分考虑了流量负载均衡问题,提升了网络路径的传输效率以及网络总吞吐量,提高了网络资源利用率,优化了网络资源配置效率。仿真结果验证了本文所提两种算法在数据转发方面的优异性能。