基于虚拟软件的网络流量调度数学模型仿真

孙晓磊,孔德志*,张焕生,赵男男

(1. 河北水利电力学院,河北 沧州 061000;2. 广东海洋大学计算机科学与工程学院,广东 阳江 529500)

1 引言

目前,网络业务数量与带宽需求随着网络应用的高速发展呈不断增长趋势,无形中提高了对网络业务承载力与转发能力的要求,为防止发生网络拥塞、提升网络性能,网络流量调度是网络性能优化的关键[1]。对于不同类型网络的服务质量,目前网络流量调度方法还不能满足其需求,原因是该方法的网络服务能力路由具有局限性[2]。

如何提升网络流量调度效果,提高网络利用率,节省网络能源消耗,使运营成本降低,是中外学者一直研究的课题[3]。如吴博等人提出的基于动态DCVS的网络流量调度模型[4],该模型可使网络性能得到提高,但其计算复杂,导致流量调度实时性差;又如王耀民等人提出的基于斐波那契树优化算法的网络流量调度模型[5],虽可使交换机的利用率得到提高,实现网络节能,但其无法形成全局最优的调度方案。

软件定义网络(Software Defined Network,SDN)是一种基于应用、调控、转发的新型网络结构体系[6],其作为虚拟机的一种嵌入式软件的网架结构体系,通过调控解藕设备与转发功能集中网络逻辑、开放可编程接口获得。SDN的核心是调控器,可以调控网络里的全部逻辑,整体管理网络,为确保不同网络应用的服务质量需求,SDN网络需找到数据转发最佳的下一跳,找到数据的前提是需依据所有网络拓扑与状态信息搜索。本文利用SDN获得节能网络流量调度功能,研究基于虚拟软件的网络流量调度数学模型仿真,减少网络拥塞,提高网络流量调度效果。

2 网络流量调度数学模型

本文采用以下符号构建该数学模型:网络用G(V,L)描述,其中,数据链路集合与链路分别用L与l描述,cl为l的容量。交换机的节点集合用V描述;随意一个交换机的节点用v描述,链路集合用Lv描述,且该链路连接交换机v。

全部保持工作状态的交换机与l在网络里的能源消耗是网络的总能源消耗[7],用COSTl描述随意l两个交换机端口的能源消耗,交换机机架与线卡的能源消耗用COSTv描述。

以符合数据流f∈F路由为基础,保证网络能源消耗总量最低为目标,完成节能流量调度。

网络流量调度的优化数学模型是

(1)

s.t.

(2)

(3)

(4)

x(P)≥0∀P

(5)

表示网络总能源消耗的优化目标函数用式(1)表示;l容量限制约束条件为式(2),随意活跃l的总容量需大于其承载的数据流总宽带。流量守恒约束条件为式(3)。当v分别仅有流出与流入数据流时,v分别是f的源节点与目的节点。否则,v的流入与流出数据流相同。用λ描述流量放大倍数。式(4)与式(5)为λ的约束条件,全部使用链路l传输流量的路径为式(4),且传输流量总和≦链路容量cl。式(5)为路径上的流量不能小于0。路径P上的流量用x(P)描述;一条从源节点到目的节点路径上的边l满足∀l∈L,用l*描述SDN转发设备之间的链路,且l*∈L区分原有链路l。

3 基于虚拟软件的网络流量调度算法EMV-SDN

EMV-SDN是基于SDN改进的多层虚拟拓扑流量调度算法,可采用EMV-SDN对上述数学模型进行求解,切割网络拓扑结构为包含多层虚拟子拓扑的虚拟结构。首先仅打开第一层虚拟拓扑,下一层虚拟拓扑启动与否受最大链路使用率影响[8],采用改进贪婪算法在已打开的虚拟拓扑结构里通过路径求解完成数据流调度。为达成节约网络能耗的目标,结合实际情况,可将已经打开的下一层虚拟拓扑进行关闭[9]。

3.1 EMV-SDN算法描述

图1为EMV-SDN流程,虚拟软件的网络拓扑与f作为输入,f的路由与已打开的一层或多层虚拟拓扑为输出。对于f的调度,基于f路由产生流表项下发交换机,由SDN调控器对其进行调度。

图1 节能网络流量调度算法过程

该方法具体过程为:

过程1:原始化。

1)随意选择两个服务器节点间K-最短路径的运算过程是通过设置虚拟软件的网络拓扑完成。

2)把虚拟软件里的网络拓扑生成多层虚拟拓扑。

3)将虚拟软件的第一层虚拟拓扑打开,其余层拓扑关闭。

用f描述新抵达的数据流,对f实施以下过程。

过程2:求解μ值,该值为最大链路使用率,求该值的前提是通过sflow软件采集目前打开的虚拟拓扑链路使用状况,且sflow软件来自于SDN调控器。

过程3:预打开虚拟软件的下一层虚拟拓扑的前提是μ值大于阈值1[10],即将其中的交换机唤醒,但不改变该层的链路状态[11]。该过程不仅能够节能,还能对突发数据流进行迅速地响应及调度,使平均网络时延的情况得到降低。若μ小于阈值1,转至过程5。

过程4:打开并使用下一层虚拟拓扑的前提是μ值大于阈值2,即使该层中里的链路唤醒并保持其活跃。若μ小于阈值2,转至过程5。

过程5:运算路由可采用改进贪心算法实现。

过程6:路由数据流通过选中路径完成。

过程7:求解μ值,求解该值的前提是将sflow收集链路状态进行调配使用[12]。

过程8:将下一层虚拟拓扑中的交换机与链路进行休眠,该操作的前提是已打开过下一层拓扑,且μ小于阈值1,持续时间大于T。该操作可防止交换机与链路产生网络动荡,其产生动荡的原因是频繁进行打开/休眠操作,使数据中心网络实现节能[13,14]。

过程9:若没有完成网络流量调度,则转至过程2;反之,节能流量调度算法EMV-SDN结束。

3.2 基于优先级队列管理的流量调度控制

为防止流量调度拥塞,利用引入优先级概念的队列管理算法(Priority RED,PRED)进行网络流量调度控制。进入/离开缓存区的顺序问题不存在于网络流量调度的单队列中而是存在于多队列中[15],该问题可通过网络流量调度“实时优先级”概念得到解决。

为使掉包率下降,需确保网络流量调度的多个队列的平均队列长度在缓存区最小,获得该最小长度的条件是到达分组中的队列可在实时优先级中优先进入。

设置有Qa,Qb,Qc三个网络流量调度队列在缓存区,如图2所示,Hin-a、Hin-b与Hin-c分别为网络流量调度队列进入缓存区的优先级,Hout-a、Hin-b与Hin-c分别为网络流量调度队列离开缓存区的优先级,并假定在刚进入网络时,原始网络流量调度队列优先级Hin-a

图2 队列长度变化

设置Qavga、Qavgb、Qavgc分别为Qa、Qb、Qc的平均队列长度,常数为K。若有分组到达缓存区,输入及输出网络流量调度队列的实时优先级公式分别为

Hin-i=K/Qavgi,i=1,2,…n

(6)

由式(6)可看出,Hin-i和Qavgi成反比例,若Qavgi值越大,则代表此时刻该网络流量调度队列含有越多的分组数目,Hin-i值越小。

为确保Qavga、Qavgb、Qavgc值相对最短,需将到来的分组放进网络流量调度队列长度最小的队列里,该过程可依据运算出的Hin-a、Hin-b与Hin-c值,重新排序进入缓存区网络流量调度队列的优先级。

Hout-i=A*Qavgi,i=1,2,…n

(7)

式中,A>1。Hout-i与Qavgi成反比例,Qavgi值越大,Hout-i值越大。为确保网络流量调度队列里较长的队列数据先离开缓存区,需重新排序Hout-a、Hin-b与Hin-c。

为防止网络出现拥塞,需要对网络流量进行调度,该调度手段可依据优先丢弃优先级高的分组数据,由网络节点对其进行调度。

丢弃优先级的概念由TCRED(Three Color RED)算法提出,网络里的业务流在优先级的基础上分为“Green,Yellow,Red”三种颜色,HRe d>HYellow>HGreen为该三种颜色的丢弃优先级排列顺序。运算Green,Yellow,Red三种颜色队列长度及掉包率,需采用同一组参数调控该三种颜色的分组,且其参数为maxth、minth、maxp、Wq。其中,式(8)、式(9)、式(10)为低优先级分组平均队长,且该队长包含在高丢弃优先级分组的平均队列长度中。

用QGreen、QYellow、QRe d分别描述G、Y、R分组本身的瞬间队列长度,求出QR、QY、QR的值,这些值分别描述G、Y、R基于优先级分组的瞬时队列长度。

4 实验对象

为验证本文模型的调度性能,采用mininet网络仿真软件进行仿真,其中全部OpenFlow交换机均有50个端口,设置所有链路带宽为120Mbit/s。

当缓存区大小固定时,设从100至200为Green分组、Yellow分组、Red分组的三组队列长度最大阈值(maxth)的变化区域,最大阈值的二分之一是其最小阈值(minth),验证网络流量调度过程中,调度队列长度阈值对本文模型中三种分组队列长度与掉包率的影响,结果如图2与图3所示。

图3 掉包率变化

由图2可看出,三组颜色的队列长度随着队列长度阈值的增加而增高,当阈值分别为100与200时,Red分组的队列长度的最低值与最高值分别为110与170,Green分组的队列长度的最低值与最高值分别为20与49。

由图3可看出,三组颜色的掉包率随着队列长度阈值的增加而呈不断上升趋势,当阈值为200时,Red与Green分组的掉包率的最高值分别为0.098与0.028,但其均小于0.10,在满足网络稳定性范围之内,。

由图2及图3的仿真可得出结论,当缓存区大小固定时,队列长度、掉包率随着队列长度阈值的增加而逐渐增大,使SDN调控器的可靠性与灵活性得到最大化的提高,同时使链路使用率也得到相应的提高,本文模型可通过增大队列长度阈值提升网络流量的调度性能。

数据流的目的节点可通过随机模式、间隔模式进行确定。其中,随机模式为主机j接收主机i随机发送的数据,且该数据以同一概率q发送;间隔模式为主机(i+x)mod n接收主机发送的数据,网络里主机的总数量用n描述。

实验选择300GB、600GB、900GB的网络流量,验证在该两种模式下,不同网络流量对本文模型网络流量调度能源消耗的影响,结果如图4与图5所示。

图4 随机模式(0.5)下网络流量调度能源消耗比例

图5 交错模式下的能源消耗比例

由图4可以看出,在随机模式下,随着网络流量的增加,本文模型的调度能源消耗比例呈小幅增长趋势。当网络流量为300GB与600GB时,本文模型的调度能源最高消耗比例分别为54%与60%,其能源消耗比例仅差6%,三种网络流量下的最低调度能源消耗比例为21%。

由图5可以看出,在交错模式下,本文模型的调度能源消耗比例依旧随着网络流量的增加而呈小幅增长趋势。当网络流量为300GB与600GB时,本文模型的调度能源最高消耗比例分别为50%与53%,其能源消耗比例仅相差3%,三种网络流量下的最低能源消耗比例只为19%。

结合图4与图5所得数据可知,本文模型的调度能源消耗受网络流量的影响较小,调度所消耗能源少,本文模型具有很好的网络流量调度节能效果。

5 结论

本文提出基于虚拟软件的网络流量调度数学模型仿真,经实验表明,当缓存区大小固定时,随着队列长度阈值的增加,队列长度、掉包率逐渐增大,最大化的提高SDN调控器的可靠性与灵活性,同时提高链路使用率,增大队列长度阈值可提升本文模型网络流量的调度性能;在随机与交错模式下,当网络流量为300GB与600GB时,其调度能源消耗比例相差值分别为6%与3%,且三种网络流量下的最低调度能源消耗比例仅为19%,说明本文模型的调度能源消耗几乎不受网络流量的影响,且消耗能源少,本文模型节能效果好。