一种基于OpenFlow网络的QoS管理方法
一种基于OpenFlow网络的QoS管理方法
【技术领域】
[0001 ] 本发明属于化enFlow网络管理领域，具体设及一种基于化enFlow网络的QoS管理 方法。
【背景技术】
[0002] 2009年，斯坦福大学提出了软件定义网络（Software Defined化twork，SDN)，SDN 将网络的数据层与控制层分离，为解决当前网络的QoS管理问题提供了新的方法，本发明W 软件定义网络为基础进行QoS管理方法研究。OpenFlow网络诞生于斯坦福大学。最初引进 化enFlow网络的目的是为了方便的运行一些新的实验性的网络协议，其核屯、思想是将网络 节点的控制平面与数据平面分离，在传统的网络中路由器既做转发操作，又做路由决策工 作，而在化enFlow网络中，OpenFlow交换机按照流表对数据进行转发，而化enFlow控制器负 责流表的产生，可W说传统的网络做路由决策等方法时是分布式的，而化enFlow网络则是 集中式的。在传统网络中要增加新的协议则需要对网络的核屯、路由器进行硬件升级，而在 化enFlow网络中只需对软件进行修改即可。OpenFlow网络有助于新的网络协议的研究因为 研究人员只需编写软件就可W直接测试新协议的性能，若化enFlow网络能够普及也会使网 络通信的基础设施费用大幅下降，因为W前网络要想升级需要更换硬件，而化enFlow网络 升级只需要更新软件，不仅可W降低硬件设备的更换速度，还会引入新的软件公司参与竞 争进一步降低价格。
【发明内容】
[0003] 本发明的目的在于提供一种基于化enFlow网络的QoS管理方法。
[0004] 本发明的目的是运样实现的：
[0005] (1)在数据层上进行数据分类:区分服务模型将IP包头中的8位服务类型字段重新 定义为区分服务字段DS，区分不同业务，表示不同的优先级;EF代表加速转发;AF代表保证 转发;BE代表尽力而为；
[0006] (2)在数据层上进行PQ队列调度与DR郎λ列调度相结合的队列调度：
[0007] 用双层队列进行调度，第一层队列为PQ队列，运个队列里分两个优先级，把EF流定 为高优先级，其余流定为低优先级，当EF流发送完后，发送其余的流，其余的流发送采用DRR 队列调度算法；当正在发送非EF数据包时，EF数据包到来，则发送完当前数据包后对DRR运 行状态保存，然后开始发送EF数据包，直至EF队列为空，然后接着运行DRR调度算法；
[000引EF类业务被设为高优先级，EF类业务主要是指VOIP业务，W及网络协议控制报文； [0009] (3)在数据层上进行队列管理：
[0010]采用WR抓算法来进行队列管理，在交换机的每个出端口，汇集6个等待发送的队 列，分别是EF数据队列，AF1数据队列，AF2数据队列，AF3数据队列，AF4数据队列，邸数据队 列，为运6个队列分别设置自己的丢包长度下限，丢包长度上限，基准丢包率，分别记为 1111叫1，111曰义91，口3;计算出每个队列的平均长度，记为曰乂旨91.对于6。队列其四个数据分别表 示为EF_minql、EF_maxql、EF_ps和EF_avgl;
[0011] 当一个数据包到来，先被分类，然后被送到对应的出端口，如果被分为EF类，则如 果EF_avgl小于等于EF_minql则运个包可W进入EF队列排队，若EF_avgl大于EF_maxql则会 对运个包进行丢弃处理;若EF_avgl在EF_minql与EF_maxql之间则其W-定概率被丢弃；
[0012] 具体概率为6。_98*化。_日￥旨]_斗。_111；[叫1)/化。_1]1日义91斗。_111；[叫1);
[0013] 平均队列长度计算方法为：
[0014] Avgql = last_avgql>Kl-x)+巧ql;
[001引其中last_avgql表示W前他的平均队列长度，ql表示当前队列长度，χ=1/2η，η为 可配置的参数取大于1的整数；
[0016] (4)在控制层上根据数据流的类型和网络当前状况进行首次路由：控制器每隔一 段时间Τ就向化enFlow交换机发送Read-state请求统计报文，获知交换机统计项里的流接 收字节数，计算一个流的速度选用的是所有交换机上的信息，在每一段链路上一个流的速 度用它的领接交换机进行计算，通过控制器求出当时AF1，AF2，AF3，AF4，肥，EF流的平均速 度，在控制器计算出一个路由后同时把运个流所在类的平均速度加到运个流所经过的每条 链路上，作为链路流量的修正值；
[0017] 把第η次计算出的EF流的平均速度记为f (η)，第η次统计时网络当前EF流的平均速 度记为ν(η)，则迭代公式为：
[0018] f (η) = Af (η-1) + (1-λ)ν(η)，η〉= 2,且ν(η) >0即当前网络存在EF流；
[0019] f(n)=f(n-l)，η〉= 2,且ν(η)=0即当前网络不存在EF流；
[0020] 其中1 >λ>〇，f (1)为对EF流速度的估计值，每个EF流的速度用它接触到的第一个 化enFlow交换机上的统计信息求得；
[0021] (5)在控制层上进行路由迁移：
[0022] (5.1)求出网络中从一点到另一点的所有路径，并按路径长度递增存储;求出网络 中从一点A到另一点B的所有路径；
[0023] (5.2)根据当前网络的所有流需求，求出其所有可能有的路径组合；
[0024] (5.3)计算出每种组合的网络链路利用率最大值，找出所有组合中最大链路利用 率最小的，如果链路利用率最小的有多种方案，则在它们中选取总cost值最小的，如果满足 上述条件的组合有多个，则在其中随机选取一个当做重路由方案。
[0025] 本发明的有益效果在于:本发明通过业务的类别、链路利用率、流的速度，为链路 赋予权值，完成路由算法的改进;利用软件定义网络集中控制的特性，提出了一种路由迁移 算法，并对路由迁移的时机选择做了优化。
【附图说明】
[0026] 图1第一次实验平均速度变化图；
[0027] 图2第二次实验平均速度变化图；
[002引图3第Ξ次实验平均速度变化图；
[0029] 图4前两次实验EF流速度变化图；
[0030] 图5第Ξ次实验EF流速度变化图；
[0031] 图6数据包处理流程图。
【具体实施方式】
[0032] 下面结合附图对本发明做进一步描述。
[0033] 本发明从数据层和控制层对网络的QoS(服务质量)管理策略进行研究。QoS管理策 略在数据层的研究主要包括流分类、队列管理和队列调度Ξ部分。控制层管理策略的研究 是本发明的重点，控制层QoS技术的研究主要有W下两点：（1)通过业务的类别、链路利用 率、流的速度，为链路赋予权值，完成路由算法的改进。（2)利用软件定义网络集中控制的特 性，提出了一种路由迁移算法，并对路由迁移的时机选择做了优化。本发明通过搭建软件定 义网络实验平台对本发明中的QoS管理策略进行了模拟实验，分别证明了（ 1)本发明中的整 套QoS管理策略是有效的，即数据层管理策略是有效的，控制层管理策略也是有效的（2)本 发明中的路由策略较其余已有的软件定义网络上的路由策略有优势。
[0034] 本发明中的QoS策略设及数据层及控制层。首先在数据层上进行数据分类、队列调 度，和队列管理。在控制层上根据数据流的类型和网络当前状况进行首次路由，及再次路由 (路由迁移）。最终实现QoS管理的目的。OpenFlow网络的核屯、思想是将网络节点的控制平面 与数据平面分离，在传统的网络中路由器既做转发操作，又做路由决策工作
[0035] 在数据层上进行数据分类:区分服务模型将IP包头中的8位服务类型字段，重新定 义为区分服务字段，用来区分不同业务，表示不同的优先级。
[0036] 用双层队列进行调度，第一层队列为PQ队列，运个 队列里分两个优先级，把EF流定 为局优先级，其余流定为低优先级，只有当EF流发送完后，才开始发送其余的流。
[0037] 当出队列达到指定长度时就开始对到来数据进行丢弃，丢弃的概率与当前队列的 长度正相关，此算法能解决TCP的全局同步问题，但算法进行丢包时并没有考虑到不同业务 的优先级，所W后来思科公司提出了加权随机早期检测算法，此算法考虑了不同业务的优 先级，当网络发生拥塞，或快要发生拥塞时优先丢弃优先级低的数据包。
[0038] 当选择最短路径作为路由时，最短路径会使网络整体链路利用率增加的最少，即 其消耗的网络资源最少，从而使将来的流的需求更容易得到满足。假如选择一条链路代价 总和最小的路作为路由则对运条流的服务质量最有保证。
[0039] 在尝试进行路径迁移时，先找到网络中链路利用率最高的链路，找到经过运条链 路的流量最大的k个流，依次进行尝试，尝试方法为再次运行路由算法，如果迁移后能降低 网络的最高链路利用率则进行迁移，然后退出迁移算法，若不能则继续对其余的属于前k的 流进行尝试，直到其中一个成功或所有都失败，算法结束。
[0040] 本发明基于软件定义网络，从数据层和控制层对当前网络的QoS问题提供了一套 管理方法。具体步骤包括：
[0041] (1)在数据层上进行数据分类:区分服务模型将IP包头中的8位服务类型字段重新 定义为区分服务字段DS，用来区分不同业务，表示不同的优先级。虽然服务类型字段字段有 8位，但目前只用到了前6位，从理论上说前六位不同则服务优先级不同，运个值越大对应的 服务优先级也越高。国际互联网工程任务组已经定义了 3种大的服务类别。分别是EF(加速 转发)适用于对QoS要求特别高的业务，主要是低延迟，低丢包。AF(保证转发)适用于对QoS 要求稍低的业务，AF又分为四个不同级别。BE(尽力而为)适用于对QoS没有要求的业务，不 同的应用种类需要网络提供不同的服务质量。
[0042] (2)在数据层上进行队列调度:首先介绍两种常用队列调度算法。
[0043] WRR加权循环调度算法可W为不同类数据提供不同的优先级服务，但是WRR算法是 基于数据包的，如果不同类数据的平均数据包大小差别较大的话则WRR算法会变得偏向于 平均数据包大的队列。使得平均数据包大的业务占优势。
[0044] DRR差额循环队列调度算法，是对WRR调度算法的改进，将WRR中的数据包个数，变 为字节数，为每个队列维护一个权值Q(Q为定值），和一个差额D。算法最初运行时需设置每 个队列的Q值，并将每个队列的D值变为0。在每一轮调度中，一个队列需发送尽量多的的数 据包，且发送的字节数少于等于Q+D，并保证按序发送，若发送了 N个数据包，则需满足Q+D大 于等于运N个数据包长度，且运N个数据包长度加上运个队列下一个要发送的数据包长度需 大于Q+D，发送完毕后，若队列为空则把D值设置为0,不为空则D = Q+D-sencLsend为运个队 列运一轮发送的字节数。DRR算法可W为不同业务，提供更为精准的优先级服务。
[0045] 本发明选取一种PQ队列调度与DR郎人列调度相结合的方法。
[0046] 即用双层队列进行调度，第一层队列为PQ队列，运个队列里分两个优先级，把EF流 定为高优先级，其余流定为低优先级，只有当EF流发送完后，才开始发送其余的流，其余的 流发送采用DR郎人列调度算法。当正在发送非EF数据包时，EF数据包到来，则发送完当前数 据包后对DRR运行状态保存，然后开始发送EF数据包，直至EF队列为空，然后接着运行DRR调 度算法(有点像中断的处理过程，但比中断效率高）。
[0047] 之所W在运里选取PQ队列调度与DR郎λ列调度相结合的方法，主要是为了吸取PQ 算法可W保证高优先级业务低时延的优点，和DRR算法较为精准的区分服务特性，但又同时 擬弃了PQ算法的缺点，低优先级的业务可能会被饿死(长期得不到调度）dEF类业务被设为 高优先级，EF类业务主要是指VOIP业务，W及网络协议控制报文(在本发明中归为EF类，实 际上其优先级比EF类高），对于VOIP业务如果延迟能控制在50msW内，则网络电话就能取得 较好的通话质量，会使更多的人选用网络电话，运样就可W降低人们的通信费用。对于本发 明所采用的双层队列调度算法，则能充分降低VOIP业务的延迟，可W说明的是运种低延迟， 是单独使用DRR算法所达不到的，因为在DRR算法中不论给EF流配置多大权重，当他下次发 送时都必须等待其余所有的数据流都发送一遍，但在运种双层的队列调度算法中当EF流到 达时，他最多只等待发送一个数据包的时间，同时由于EF数据流本身流量并不大，而且只为 EF数据流配置了高优先级，则不会出现低优先级业务饿死现象。
[0048] (3)在数据层上进行队列管理：列管理的初衷是，网络中的数据流量很大，超出了 网络的能力时则必须对一部分数据进行丢弃，最原始的方法是当发送队列到达一定长度时 再来的数据包就会直接被丢弃，但我们知道网络中很多数据是用的是TCP传输，如果当队列 满时对所有来的数据都丢弃的话，则很有可能会丢弃一些不同的TCP连接上的数据，会使运 些TCP连接同时调整自己的发送速度，发送窗口减半或变为1，同时启动拥塞避免算法或慢 开始算法，造成TCP的全局同步，则网络流量会迅速下降，运样网络得不到充分利用，而后它 们又会在某个时刻同时达到速度的高峰，则又会出现尾丢弃，如此反复循环，最终导致网络 资源得不到充分利用。
[0049] 后来就出现了 R抓随机早期检测算法，当出队列达到一定长度时就开始W-定概 率对到来数据进行丢弃，丢弃的概率与当前队列的长度正相关，此算法能解决TCP的全局同 步问题，但Rm)算法进行丢包时并没有考虑到不同业务的优先级，所W后来思科公司提出了 WRm)加权随机早期检测算法，此算法考虑了不同业务的优先级，当网络发生拥塞，或快要发 生拥塞时优先丢弃优先级低的数据包。
[0050] 本发明采用WR抓算法来进行队列管理，下面对本发明采用的WR抓算法进行讲解。 在交换机的每个出端日，会汇集6个等待发送的队列，分别是EF数据队列，AF1数据队列，AF2 数据队列，AF3数据队列，AF4数据队列，BE数据队列，为运6个队列分别设置自己的丢包长度 下限，丢包长度上限，基准丢包率，分别记为1111叫1，111曰《91，93。还需要计算出每个队列的平 均长度，记为日￥旨91.对于6。队列其四个数据分别表示为6。_111；[叫1、6。_1]1日义91、6。_93和6尸_ avgl，其余表示方法类似。
[0051] 当一个数据包到来，会先被分类，然后被送到对应的出端口，假设它被分为EF类， 则如果EF_avgl小于等于EF_minql则运个包可W进入EF队列排队，若EF_avgl大于EF_maxql 则会对运个包进行丢弃处理。若EF_avgl在EF_minql与EF_maxql之间则其W-定概率被丢 弃。
[0052] 具体概率为6。_98*化。_日￥旨]_斗。_111；[叫1)/化。_1]1日义91斗。_111；[叫1)。
[0053] 对于其余类流处理方法类似，只需把上述中的EF换为对应值即可。运里之所W采 用平均队列长度，而不是当前队列长度主要是为了应对突发的流量，比如一个数据流上一 秒到来了很多数据，而下一秒数据很少，则采用当前队列长度很有可能会对它到来的第一 批数据进行不正确丢弃，而采用平均队列长度则可W避免运一现象。
[0054] 平均队列长度计算方法为：
[0055] Avgql=last_avgql*(l-x)+x*ql〇
[0056] 其中last_avgql表示W前他的平均队列长度，ql表示当前队列长度，χ=1/2η，η为 可配置的参数取大于1的整数，η越大则当前队列长度的权重越小，平均队列长度变化越平 滑。
[0057] (4)在控制层上根据数据流的类型和网络当前状况进行首次路由：控制器每隔一 段时间就向化enFlow交换机发送Read-s化te请求统计报文，获知交换机统计项里的流接收 字节数，但计算一个流的速度选用的是所 有交换机上的信息，而不仅仅是运个流进入 化enFlow网络的第一个交换机上的信息，在每一段链路上一个流的速度用它的领接交换机 进行计算，可W通过控制器求出当时AF1，AF2，AF3，AF4，BE，EF流的平均速度，在控制器计算 出一个路由后同时把运个流所在类的平均速度加到运个流所经过的每条链路上，作为链路 流量的修正值。流平均速度的计算在下文讲解。
[0058] 至于Dstream的计算，则可W采用运类流的平均速度来对当前流的速度进行估计。在 运里之所W用平均速度而不是实际速度对链路流量进行修正，是由于在计算路由时运条流 刚到达化enFlow网络，是不知道它的实际速度的（如果做协议扩展则可W获得流的速度，但 需要发送方配合，但实际情况是大多数发送方是不配合的，所W只能用平均速度估计）。
[0059] 链路流量1(a)的计算与Dstream的计算都设及到流平均速度的计算，下面WEF流为 例对流平均速度的计算进行说明。
[0060] 把第η次计算出的EF流的平均速度记为f (η )，第η次统计时网络当前EF流的平均速 度记为ν(η)，则迭代公式为：
[0061 ] f (η) = Af (η-1) + (1-λ)ν(η)(η〉= 2,且 ν(η)>0即当前网络存在EF流）（1)
[0062] f (η) =f (η-1)(η〉= 2,且ν(η) =0即当前网络不存在EF流）（2)
[0063] 其中1>λ>〇，?·(1)为事先设置好的对EF流速度的估计值，每个EF流的速度用它接 触到的第一个化enFlow交换机上的统计信息求得，其余流的平均速度计算方法类似。
[0064] (5)在控制层上进行路由迁移:在流量工程里很多路由算法都是W使网络的最大 链路利用率最低作为其优化目标，但是传统网络里由于其分布式特性导致运个目标无法实 现，但运个目标在化enF 1OW网络里是可W实现的。
[0065] 为了使网络的最大链路利用率最低，可W枚举所有路由方法的组合，从中选择使 网络最大链路利用率最低的，若有多个最低的组合方法，则在其中选择消耗网络总资源最 少的方法(cost最小），为了实现运个思想提出W下步骤。
[0066] 第一步，求出网络中从一点到另一点的所有路径(不含环），并按路径长度递增存 储。求出网络中从一点（记为点A)到另一点（记为点B)的所有路径:一种方法是把整个网络 看做一个图，其中交换机(在传统网络中是路由器，在化enFlow网络中是交换机)是图的顶 点，实际链路为图的边。从A点进行深度优先遍历，遍历的过程中需要保证当前路径里不含 重复点，每当遍历到点B，就找到了一条从A至化的不含环路径，当遍历结束便可求出A至化的 所有路径。
[0067] 第二步，根据当前网络的所有流需求，求出其所有可能有的路径组合。当前网络有 两个流请求，流1从点A进入网络其目标节点为点B，流2从点C进入网络其目标节点为点D，其 中A至化有5条路径，C到D有8条路径，则所有的路由组合一共为40 (5*8)种。
[0068] 第Ξ步，计算出每种组合的网络链路利用率最大值，找出所有组合中最大链路利 用率最小的，如果链路利用率最小的有多种方案，则在它们中选取总cost值最小的，如果满 足上述条件的组合有多个，则在其中随机选取一个当做重路由方案。
[0069] 按组合的方案进行路由，并假定丢包率为0,且链路带宽无上限，计算出每条链路 上的理论流量(可能超过链路带宽），后由理论流量除W链路容量，为运条链路的利用率，在 所有链路的利用率中选取最大值就为运种组合的链路利用率最大值。
[0070] 本发明的目的是为了证明本发明中提出的QoS管理方法，相对于其它的QoS管理方 法具有优势，但由于QoS管理中的数据层算法有很多参数:队列管理算法有很多参数，队列 调度算法也有很多参数。而大多数文章的作者并未在其文章中说明其参数应该如何选取， 因此如果比较整套QoS解决方案则非常困难。本章会做两个实验，第一个实验的目的是证明 整个QoS方法的有效性，第二个实验的目的是证明本发明中的路由算法较其余的一些 化enFlow网络下的路由算法有优势。
[0071] 1、有效性验证实验需要进行Ξ次实验，第一次实验没有采用QoS管理方法，第二次 实验只采用本发明中的数据层处理方案，第Ξ次实验采用本发明中的整套QoS解决方案。
[0072] 第一次实验为化en vSwitch交换机配置FIFO队列调度方法，对所有到来的数据包 采用先来先服务，当网络拥塞时采用尾丢弃方法，为N0X控制器配置最短路径算法，让其为 所有数据包选择最短路径。
[0073] 第二次实验为EF数据流配置PQ优先队列，对其余流配置DR郎人列，即用PQ与DRR双 层队列调度方法其中AF4的Q值设置为5000，AF3的Q值设置为4000，AF2的Q值设置为3000， AF1的Q值设置为2000，BE的Q值设置为1000(Q值为DRR中的参数），队列管理采用WRED加权随 机早期检测算法。为N0X控制器配置最短路径算法，让其为所有数据包选择最短路径。
[0074] 第Ξ次实验为EF数据流配置PQ优先队列，对其余流配置DR郎人列，即用PQ与DRR双 层队列调度方法其中AF4的Q值设置为5000，AF3的Q值设置为4000，AF2的Q值设置为3000， AF1的Q值设置为2000，BE的Q值设置为1000(Q值为DRR中的参数），队列管理采用WRED加权随 机早期检测算法。为NOX控制器配置本发明中的SIWLU化路由算法W及邸VRA路由迁移算法。
[0075] Ξ次实验发包流程为：（实验一共运行45秒）
[0076] (1)第0秒模拟接收端对模拟发送端进行FTP下载请求。（FTP服务器设置的最大下 载速度为0.5MB/S)
[0077] (2)第8秒模拟发送端发送1个速度约为IMB/s每秒的udp数据流。
[0078] (3)第17秒模拟发送端发送1个速度约为IMB/s每秒的udp数据流。
[0079] (4)第28秒模拟发送端开始向模拟接收端发送码率为3500肺PS(大约0.427M/S)的 高清实时视频流传输层协议为udp。
[0080] (5)第40秒模拟发送端开始向模拟接受端发送码率为90肺S(大约O.OllM/s)的高 音质实时音频流，传输层协议为udp。
[0081] 实验结果:采用最短路径的路由结果即实验1，2的路由结果如表1所示：
[0082] 表1最短路径算法路由结果
[0083]
[0084] 采用本发明中的路由算法的路由结果，即实验3,4的路由结果如表2所示：
[0085] 表2本发明路由算法结果
[0086]
[0087] 在图1，4，5中里红色的点表示FTP流的速度，绿色的星号点表示第一个BE流的速 度，黑色的加号点表示实时视频的速度，蓝色的圆点表示第二个BE流的速度。
[0088] 在Ξ个图里红色的点表示FTP流的速度，绿色的星号点表示第一个邸流的速度，黑 色的加号点表示实时视频的速度，蓝色的圆点表示第二个BE流的速度。
[0089] 在实验一与实验二中由于第二个BE流的速度与第一个BE流的速度非常接近，如果 都在一个图里画出则会使数据叠加在一起导致图看不清。W上所有的点表示的不是那一时 刻的瞬时速度而是那一秒的平均速度，比如表示0到1秒的平均速度的点的横坐标为0.5。
[0090] 由于EF音频数据流的速度和W上运些不在一个数量级故单独画出。图4和图5表示 EF音频流的速度，其中第一次实验和第二次实验的的数据放在图4中，第Ξ次的实验数据放 在图5中，由于第二次实验和第Ξ次两次实验测得的EF数据流速度相差很小如果将运两次 的结果放在同一张图中则会导致两种数据叠加在一起导致无法辨别，因此将其放在两个图 中，其中图4中的黑色加号表示第一次实验中的EF数据流速度，图4中的绿色星号表示第二 次实验中的EF数据流速度，图5中的红色点表示第Ξ次实验中的EF数据流速度。[0091] 第二次实验数据与第一次实验数据对比发现，加入了数据层控制后能有效控制BE 流的速度降低其对网络的影响，并能为视频音频运种高优先级数据提供较好的服务，实验 二与实验Ξ对比发现加入了控制层后，网络的流量分布可W变得更均匀，从而能提升整个 网络的吞吐量，能进一步提升网络对高优先级业务的服务。通过实验证明运个QoS管理系统 是有效的。
[0092] 2、路由性能测试中，路由算法(含迁移部分)将会和其余的Ξ种化enFlow网络下的 路由算法进行对比，运Ξ种方法分别是13年陈志钢在其QoS系统中采用的WLU化方法，W及 13年Karl M，Gruen J，Herfet T等人提出的KGH路由方法W及最常用的最短路径算法。
[0093] WUJLL算法中有一个参数λ，经过实验发现λ值越小时，其性能越优，但当λ小到一定 程度时其值就开始对实验结果不造成影响（本部分的拓扑非常容易导致最短路径负载过 重，故λ越小越好)故为了使WUJ化算法发挥其最大潜力将其λ值取为0.01(在本实验中其能 取得运个算法的最优结果）。
[0094] 由于运个实验是比较路由算法，故在数据层并没有配置本发明中的队列管理与队 列调度算法，故本发明中参与比较的算法为IWL化L初次路由算法与邸VRA再次路由算法。
[0095] IWLU化中δ选择0.5，β选择2.5。邸VRA路径迁移中的参数t选择15s。
[0096] 由于KGH算法与WLU化算法中只有两类数据包，故为方便起见，实验中一共发送两 类数据包，分别是视频音频数据包(AF4流或EF流)和普通业务数据包(AF1流或肥流），通过 让其分别使用不同范围的端口，来让控制器区分其所属的类型。
[0097] 由于KGH算法只针对多媒体数据进行路由，并没有说明对非多媒体数据该如何进 行路由，故为了与其对比，与其比较两次，第一次两种数据包都发送，将KGH算法进行扩展， 为非多媒体数据选择最短路径，为多媒体数据按照原本的KGH算法选择路径。第二次实验， 网络中只发送多媒体数据包。
[0098] 实验结果:第一次两种数据包都发送的实验结果如表3所示：
[0099] 表3两种数据包都有实验结果
[0100]
[0101 ]只发送视频音频数据流实验结果如表4所示：
[0102] 表4只发送EF数据流实验结果
[0103]
[0104] 为了更好的区分四种算法的性能，实验过程中流量较大，且很多时候网络无法满 足所有流的流量需求，故四种算法在实验中丢包率都较高。
[0105] 经过实验对比发现本发明中的路由算法在丢包率，W及充分利用网络资源方面较 其余Ξ种算法有优势。
[0106] 下面对实验结果进行分析，经过实验观察发现最短路径算法在本发明的拓扑结构 中非常容易导致最短路径过载，造成在本实验中其性能非常差。WUJLL算法对链路利用率的 代价估计是线性的，故也容易发生链路过载;而KGH算法过载前与过载后链路权重只是变为 2倍，故WUJLL算法和K細算法并未对链路权重做出合理地估计，此外它们路由计算好后就不 再改变没有迁移模块，致使未充分发挥出化enFlow网络集中控制的优势。
【主权项】
1. 一种基于OpenFlow网络的QoS管理方法，其特征在于，包括如下步骤： (1) 在数据层上进行数据分类：区分服务模型将IP包头中的8位服务类型字段重新定义 为区分服务字段DS，区分不同业务，表示不同的优先级;EF代表加速转发;AF代表保证转发； BE代表尽力而为； (2) 在数据层上进行PQ队列调度与DRR队列调度相结合的队列调度： 用双层队列进行调度，第一层队列为PQ队列，这个队列里分两个优先级，把EF流定为高 优先级，其余流定为低优先级，当EF流发送完后，发送其余的流，其余的流发送采用DRR队列 调度算法；当正在发送非EF数据包时，EF数据包到来，则发送完当前数据包后对DRR运行状 态保存，然后开始发送EF数据包，直至EF队列为空，然后接着运行DRR调度算法； EF类业务被设为高优先级，EF类业务主要是指VOIP业务，以及网络协议控制报文； (3) 在数据层上进行队列管理： 采用WRED算法来进行队列管理，在交换机的每个出端口，汇集6个等待发送的队列，分 别是EF数据队列，AF1数据队列，AF2数据队列，AF3数据队列，AF4数据队列，BE数据队列，为 这6个队列分别设置自己的丢包长度下限，丢包长度上限，基准丢包率，分别记为minql， maxq1，ps;计算出每个队列的平均长度，记为avgq1.对于EF队列其四个数据分别表示为EF_ minql、EF_maxql、EF_ps和EF_avgl; 当一个数据包到来，先被分类，然后被送到对应的出端口，如果被分为EF类，则如果EF_avgl小于等于EF_minql则这个包可以进入EF队列排队，若EF_avgl大于EF_maxql则会对这 个包进行丢弃处理;若EF_avgl在EF_minql与EF_maxql之间则其以一定概率被丢弃； 具体概率为￡?_卩8*化?_&￥814?_111；[叫1)/化?_1]1&叉914?_111；[叫1); 平均队列长度计算方法为： Avgql=last_avgql*(l_x)+x*ql; 其中last_aVgql表示以前他的平均队列长度，ql表示当前队列长度，x=l/2n，n为可配 置的参数取大于1的整数； (4) 在控制层上根据数据流的类型和网络当前状况进行首次路由：控制器每隔一段时 间Τ就向OpenFlow交换机发送Read-state请求统计报文，获知交换机统计项里的流接收字 节数，计算一个流的速度选用的是所有交换机上的信息，在每一段链路上一个流的速度用 它的领接交换机进行计算，通过控制器求出当时AF1，AF2，AF3，AF4，BE，EF流的平均速度，在 控制器计算出一个路由后同时把这个流所在类的平均速度加到这个流所经过的每条链路 上，作为链路流量的修正值； 把第η次计算出的EF流的平均速度记为f(η)，第η次统计时网络当前EF流的平均速度记 为ν(η)，则迭代公式为： ?·(η)=λ?·(η-1) + (1-λ)ν(η)，η> = 2,且ν(η)>0即当前网络存在EF流； f(n)=f(n-l)，η> = 2,且ν(η)=0即当前网络不存在EF流； 其中l>A>〇，f(l)为对EF流速度的估计值，每个EF流的速度用它接触到的第一个OpenFlow交换机上的统计信息求得； (5) 在控制层上进行路由迀移： (5.1)求出网络中从一点到另一点的所有路径，并按路径长度递增存储;求出网络中从 一点A到另一点B的所有路径； (5.2) 根据当前网络的所有流需求，求出其所有可能有的路径组合； (5.3) 计算出每种组合的网络链路利用率最大值，找出所有组合中最大链路利用率最 小的，如果链路利用率最小的有多种方案，则在它们中选取总cost值最小的，如果满足上述 条件的组合有多个，则在其中随机选取一个当做重路由方案。
【专利摘要】本发明属于OpenFlow网络管理领域，具体涉及一种基于OpenFlow网络的QoS管理方法。本发明包括：在数据层上进行数据分类；在数据层上进行PQ队列调度与DRR队列调度相结合的队列调度；在数据层上进行队列管理；在控制层上根据数据流的类型和网络当前状况进行首次路由；在控制层上进行路由迁移。本发明通过业务的类别、链路利用率、流的速度，为链路赋予权值，完成路由算法的改进；利用软件定义网络集中控制的特性，提出了一种路由迁移算法，并对路由迁移的时机选择做了优化。
【IPC分类】H04L12/729, H04L12/815, H04L12/865, H04L12/851
【公开号】CN105490962
【申请号】CN201510884120
【发明人】孙建国, 李博权, 李守政, 张立国, 杨俊超
【申请人】哈尔滨工程大学
【公开日】2016年4月13日
【申请日】2015年12月4日
【技术领域】
[0001 ] 本发明属于化enFlow网络管理领域，具体设及一种基于化enFlow网络的QoS管理 方法。
【背景技术】
[0002] 2009年，斯坦福大学提出了软件定义网络（Software Defined化twork，SDN)，SDN 将网络的数据层与控制层分离，为解决当前网络的QoS管理问题提供了新的方法，本发明W 软件定义网络为基础进行QoS管理方法研究。OpenFlow网络诞生于斯坦福大学。最初引进 化enFlow网络的目的是为了方便的运行一些新的实验性的网络协议，其核屯、思想是将网络 节点的控制平面与数据平面分离，在传统的网络中路由器既做转发操作，又做路由决策工 作，而在化enFlow网络中，OpenFlow交换机按照流表对数据进行转发，而化enFlow控制器负 责流表的产生，可W说传统的网络做路由决策等方法时是分布式的，而化enFlow网络则是 集中式的。在传统网络中要增加新的协议则需要对网络的核屯、路由器进行硬件升级，而在 化enFlow网络中只需对软件进行修改即可。OpenFlow网络有助于新的网络协议的研究因为 研究人员只需编写软件就可W直接测试新协议的性能，若化enFlow网络能够普及也会使网 络通信的基础设施费用大幅下降，因为W前网络要想升级需要更换硬件，而化enFlow网络 升级只需要更新软件，不仅可W降低硬件设备的更换速度，还会引入新的软件公司参与竞 争进一步降低价格。
【发明内容】
[0003] 本发明的目的在于提供一种基于化enFlow网络的QoS管理方法。
[0004] 本发明的目的是运样实现的：
[0005] (1)在数据层上进行数据分类:区分服务模型将IP包头中的8位服务类型字段重新 定义为区分服务字段DS，区分不同业务，表示不同的优先级;EF代表加速转发;AF代表保证 转发;BE代表尽力而为；
[0006] (2)在数据层上进行PQ队列调度与DR郎λ列调度相结合的队列调度：
[0007] 用双层队列进行调度，第一层队列为PQ队列，运个队列里分两个优先级，把EF流定 为高优先级，其余流定为低优先级，当EF流发送完后，发送其余的流，其余的流发送采用DRR 队列调度算法；当正在发送非EF数据包时，EF数据包到来，则发送完当前数据包后对DRR运 行状态保存，然后开始发送EF数据包，直至EF队列为空，然后接着运行DRR调度算法；
[000引EF类业务被设为高优先级，EF类业务主要是指VOIP业务，W及网络协议控制报文； [0009] (3)在数据层上进行队列管理：
[0010]采用WR抓算法来进行队列管理，在交换机的每个出端口，汇集6个等待发送的队 列，分别是EF数据队列，AF1数据队列，AF2数据队列，AF3数据队列，AF4数据队列，邸数据队 列，为运6个队列分别设置自己的丢包长度下限，丢包长度上限，基准丢包率，分别记为 1111叫1，111曰义91，口3;计算出每个队列的平均长度，记为曰乂旨91.对于6。队列其四个数据分别表 示为EF_minql、EF_maxql、EF_ps和EF_avgl;
[0011] 当一个数据包到来，先被分类，然后被送到对应的出端口，如果被分为EF类，则如 果EF_avgl小于等于EF_minql则运个包可W进入EF队列排队，若EF_avgl大于EF_maxql则会 对运个包进行丢弃处理;若EF_avgl在EF_minql与EF_maxql之间则其W-定概率被丢弃；
[0012] 具体概率为6。_98*化。_日￥旨]_斗。_111；[叫1)/化。_1]1日义91斗。_111；[叫1);
[0013] 平均队列长度计算方法为：
[0014] Avgql = last_avgql>Kl-x)+巧ql;
[001引其中last_avgql表示W前他的平均队列长度，ql表示当前队列长度，χ=1/2η，η为 可配置的参数取大于1的整数；
[0016] (4)在控制层上根据数据流的类型和网络当前状况进行首次路由：控制器每隔一 段时间Τ就向化enFlow交换机发送Read-state请求统计报文，获知交换机统计项里的流接 收字节数，计算一个流的速度选用的是所有交换机上的信息，在每一段链路上一个流的速 度用它的领接交换机进行计算，通过控制器求出当时AF1，AF2，AF3，AF4，肥，EF流的平均速 度，在控制器计算出一个路由后同时把运个流所在类的平均速度加到运个流所经过的每条 链路上，作为链路流量的修正值；
[0017] 把第η次计算出的EF流的平均速度记为f (η)，第η次统计时网络当前EF流的平均速 度记为ν(η)，则迭代公式为：
[0018] f (η) = Af (η-1) + (1-λ)ν(η)，η〉= 2,且ν(η) >0即当前网络存在EF流；
[0019] f(n)=f(n-l)，η〉= 2,且ν(η)=0即当前网络不存在EF流；
[0020] 其中1 >λ>〇，f (1)为对EF流速度的估计值，每个EF流的速度用它接触到的第一个 化enFlow交换机上的统计信息求得；
[0021] (5)在控制层上进行路由迁移：
[0022] (5.1)求出网络中从一点到另一点的所有路径，并按路径长度递增存储;求出网络 中从一点A到另一点B的所有路径；
[0023] (5.2)根据当前网络的所有流需求，求出其所有可能有的路径组合；
[0024] (5.3)计算出每种组合的网络链路利用率最大值，找出所有组合中最大链路利用 率最小的，如果链路利用率最小的有多种方案，则在它们中选取总cost值最小的，如果满足 上述条件的组合有多个，则在其中随机选取一个当做重路由方案。
[0025] 本发明的有益效果在于:本发明通过业务的类别、链路利用率、流的速度，为链路 赋予权值，完成路由算法的改进;利用软件定义网络集中控制的特性，提出了一种路由迁移 算法，并对路由迁移的时机选择做了优化。
【附图说明】
[0026] 图1第一次实验平均速度变化图；
[0027] 图2第二次实验平均速度变化图；
[002引图3第Ξ次实验平均速度变化图；
[0029] 图4前两次实验EF流速度变化图；
[0030] 图5第Ξ次实验EF流速度变化图；
[0031] 图6数据包处理流程图。
【具体实施方式】
[0032] 下面结合附图对本发明做进一步描述。
[0033] 本发明从数据层和控制层对网络的QoS(服务质量)管理策略进行研究。QoS管理策 略在数据层的研究主要包括流分类、队列管理和队列调度Ξ部分。控制层管理策略的研究 是本发明的重点，控制层QoS技术的研究主要有W下两点：（1)通过业务的类别、链路利用 率、流的速度，为链路赋予权值，完成路由算法的改进。（2)利用软件定义网络集中控制的特 性，提出了一种路由迁移算法，并对路由迁移的时机选择做了优化。本发明通过搭建软件定 义网络实验平台对本发明中的QoS管理策略进行了模拟实验，分别证明了（ 1)本发明中的整 套QoS管理策略是有效的，即数据层管理策略是有效的，控制层管理策略也是有效的（2)本 发明中的路由策略较其余已有的软件定义网络上的路由策略有优势。
[0034] 本发明中的QoS策略设及数据层及控制层。首先在数据层上进行数据分类、队列调 度，和队列管理。在控制层上根据数据流的类型和网络当前状况进行首次路由，及再次路由 (路由迁移）。最终实现QoS管理的目的。OpenFlow网络的核屯、思想是将网络节点的控制平面 与数据平面分离，在传统的网络中路由器既做转发操作，又做路由决策工作
[0035] 在数据层上进行数据分类:区分服务模型将IP包头中的8位服务类型字段，重新定 义为区分服务字段，用来区分不同业务，表示不同的优先级。
[0036] 用双层队列进行调度，第一层队列为PQ队列，运个 队列里分两个优先级，把EF流定 为局优先级，其余流定为低优先级，只有当EF流发送完后，才开始发送其余的流。
[0037] 当出队列达到指定长度时就开始对到来数据进行丢弃，丢弃的概率与当前队列的 长度正相关，此算法能解决TCP的全局同步问题，但算法进行丢包时并没有考虑到不同业务 的优先级，所W后来思科公司提出了加权随机早期检测算法，此算法考虑了不同业务的优 先级，当网络发生拥塞，或快要发生拥塞时优先丢弃优先级低的数据包。
[0038] 当选择最短路径作为路由时，最短路径会使网络整体链路利用率增加的最少，即 其消耗的网络资源最少，从而使将来的流的需求更容易得到满足。假如选择一条链路代价 总和最小的路作为路由则对运条流的服务质量最有保证。
[0039] 在尝试进行路径迁移时，先找到网络中链路利用率最高的链路，找到经过运条链 路的流量最大的k个流，依次进行尝试，尝试方法为再次运行路由算法，如果迁移后能降低 网络的最高链路利用率则进行迁移，然后退出迁移算法，若不能则继续对其余的属于前k的 流进行尝试，直到其中一个成功或所有都失败，算法结束。
[0040] 本发明基于软件定义网络，从数据层和控制层对当前网络的QoS问题提供了一套 管理方法。具体步骤包括：
[0041] (1)在数据层上进行数据分类:区分服务模型将IP包头中的8位服务类型字段重新 定义为区分服务字段DS，用来区分不同业务，表示不同的优先级。虽然服务类型字段字段有 8位，但目前只用到了前6位，从理论上说前六位不同则服务优先级不同，运个值越大对应的 服务优先级也越高。国际互联网工程任务组已经定义了 3种大的服务类别。分别是EF(加速 转发)适用于对QoS要求特别高的业务，主要是低延迟，低丢包。AF(保证转发)适用于对QoS 要求稍低的业务，AF又分为四个不同级别。BE(尽力而为)适用于对QoS没有要求的业务，不 同的应用种类需要网络提供不同的服务质量。
[0042] (2)在数据层上进行队列调度:首先介绍两种常用队列调度算法。
[0043] WRR加权循环调度算法可W为不同类数据提供不同的优先级服务，但是WRR算法是 基于数据包的，如果不同类数据的平均数据包大小差别较大的话则WRR算法会变得偏向于 平均数据包大的队列。使得平均数据包大的业务占优势。
[0044] DRR差额循环队列调度算法，是对WRR调度算法的改进，将WRR中的数据包个数，变 为字节数，为每个队列维护一个权值Q(Q为定值），和一个差额D。算法最初运行时需设置每 个队列的Q值，并将每个队列的D值变为0。在每一轮调度中，一个队列需发送尽量多的的数 据包，且发送的字节数少于等于Q+D，并保证按序发送，若发送了 N个数据包，则需满足Q+D大 于等于运N个数据包长度，且运N个数据包长度加上运个队列下一个要发送的数据包长度需 大于Q+D，发送完毕后，若队列为空则把D值设置为0,不为空则D = Q+D-sencLsend为运个队 列运一轮发送的字节数。DRR算法可W为不同业务，提供更为精准的优先级服务。
[0045] 本发明选取一种PQ队列调度与DR郎人列调度相结合的方法。
[0046] 即用双层队列进行调度，第一层队列为PQ队列，运个队列里分两个优先级，把EF流 定为高优先级，其余流定为低优先级，只有当EF流发送完后，才开始发送其余的流，其余的 流发送采用DR郎人列调度算法。当正在发送非EF数据包时，EF数据包到来，则发送完当前数 据包后对DRR运行状态保存，然后开始发送EF数据包，直至EF队列为空，然后接着运行DRR调 度算法(有点像中断的处理过程，但比中断效率高）。
[0047] 之所W在运里选取PQ队列调度与DR郎λ列调度相结合的方法，主要是为了吸取PQ 算法可W保证高优先级业务低时延的优点，和DRR算法较为精准的区分服务特性，但又同时 擬弃了PQ算法的缺点，低优先级的业务可能会被饿死(长期得不到调度）dEF类业务被设为 高优先级，EF类业务主要是指VOIP业务，W及网络协议控制报文(在本发明中归为EF类，实 际上其优先级比EF类高），对于VOIP业务如果延迟能控制在50msW内，则网络电话就能取得 较好的通话质量，会使更多的人选用网络电话，运样就可W降低人们的通信费用。对于本发 明所采用的双层队列调度算法，则能充分降低VOIP业务的延迟，可W说明的是运种低延迟， 是单独使用DRR算法所达不到的，因为在DRR算法中不论给EF流配置多大权重，当他下次发 送时都必须等待其余所有的数据流都发送一遍，但在运种双层的队列调度算法中当EF流到 达时，他最多只等待发送一个数据包的时间，同时由于EF数据流本身流量并不大，而且只为 EF数据流配置了高优先级，则不会出现低优先级业务饿死现象。
[0048] (3)在数据层上进行队列管理：列管理的初衷是，网络中的数据流量很大，超出了 网络的能力时则必须对一部分数据进行丢弃，最原始的方法是当发送队列到达一定长度时 再来的数据包就会直接被丢弃，但我们知道网络中很多数据是用的是TCP传输，如果当队列 满时对所有来的数据都丢弃的话，则很有可能会丢弃一些不同的TCP连接上的数据，会使运 些TCP连接同时调整自己的发送速度，发送窗口减半或变为1，同时启动拥塞避免算法或慢 开始算法，造成TCP的全局同步，则网络流量会迅速下降，运样网络得不到充分利用，而后它 们又会在某个时刻同时达到速度的高峰，则又会出现尾丢弃，如此反复循环，最终导致网络 资源得不到充分利用。
[0049] 后来就出现了 R抓随机早期检测算法，当出队列达到一定长度时就开始W-定概 率对到来数据进行丢弃，丢弃的概率与当前队列的长度正相关，此算法能解决TCP的全局同 步问题，但Rm)算法进行丢包时并没有考虑到不同业务的优先级，所W后来思科公司提出了 WRm)加权随机早期检测算法，此算法考虑了不同业务的优先级，当网络发生拥塞，或快要发 生拥塞时优先丢弃优先级低的数据包。
[0050] 本发明采用WR抓算法来进行队列管理，下面对本发明采用的WR抓算法进行讲解。 在交换机的每个出端日，会汇集6个等待发送的队列，分别是EF数据队列，AF1数据队列，AF2 数据队列，AF3数据队列，AF4数据队列，BE数据队列，为运6个队列分别设置自己的丢包长度 下限，丢包长度上限，基准丢包率，分别记为1111叫1，111曰《91，93。还需要计算出每个队列的平 均长度，记为日￥旨91.对于6。队列其四个数据分别表示为6。_111；[叫1、6。_1]1日义91、6。_93和6尸_ avgl，其余表示方法类似。
[0051] 当一个数据包到来，会先被分类，然后被送到对应的出端口，假设它被分为EF类， 则如果EF_avgl小于等于EF_minql则运个包可W进入EF队列排队，若EF_avgl大于EF_maxql 则会对运个包进行丢弃处理。若EF_avgl在EF_minql与EF_maxql之间则其W-定概率被丢 弃。
[0052] 具体概率为6。_98*化。_日￥旨]_斗。_111；[叫1)/化。_1]1日义91斗。_111；[叫1)。
[0053] 对于其余类流处理方法类似，只需把上述中的EF换为对应值即可。运里之所W采 用平均队列长度，而不是当前队列长度主要是为了应对突发的流量，比如一个数据流上一 秒到来了很多数据，而下一秒数据很少，则采用当前队列长度很有可能会对它到来的第一 批数据进行不正确丢弃，而采用平均队列长度则可W避免运一现象。
[0054] 平均队列长度计算方法为：
[0055] Avgql=last_avgql*(l-x)+x*ql〇
[0056] 其中last_avgql表示W前他的平均队列长度，ql表示当前队列长度，χ=1/2η，η为 可配置的参数取大于1的整数，η越大则当前队列长度的权重越小，平均队列长度变化越平 滑。
[0057] (4)在控制层上根据数据流的类型和网络当前状况进行首次路由：控制器每隔一 段时间就向化enFlow交换机发送Read-s化te请求统计报文，获知交换机统计项里的流接收 字节数，但计算一个流的速度选用的是所 有交换机上的信息，而不仅仅是运个流进入 化enFlow网络的第一个交换机上的信息，在每一段链路上一个流的速度用它的领接交换机 进行计算，可W通过控制器求出当时AF1，AF2，AF3，AF4，BE，EF流的平均速度，在控制器计算 出一个路由后同时把运个流所在类的平均速度加到运个流所经过的每条链路上，作为链路 流量的修正值。流平均速度的计算在下文讲解。
[0058] 至于Dstream的计算，则可W采用运类流的平均速度来对当前流的速度进行估计。在 运里之所W用平均速度而不是实际速度对链路流量进行修正，是由于在计算路由时运条流 刚到达化enFlow网络，是不知道它的实际速度的（如果做协议扩展则可W获得流的速度，但 需要发送方配合，但实际情况是大多数发送方是不配合的，所W只能用平均速度估计）。
[0059] 链路流量1(a)的计算与Dstream的计算都设及到流平均速度的计算，下面WEF流为 例对流平均速度的计算进行说明。
[0060] 把第η次计算出的EF流的平均速度记为f (η )，第η次统计时网络当前EF流的平均速 度记为ν(η)，则迭代公式为：
[0061 ] f (η) = Af (η-1) + (1-λ)ν(η)(η〉= 2,且 ν(η)>0即当前网络存在EF流）（1)
[0062] f (η) =f (η-1)(η〉= 2,且ν(η) =0即当前网络不存在EF流）（2)
[0063] 其中1>λ>〇，?·(1)为事先设置好的对EF流速度的估计值，每个EF流的速度用它接 触到的第一个化enFlow交换机上的统计信息求得，其余流的平均速度计算方法类似。
[0064] (5)在控制层上进行路由迁移:在流量工程里很多路由算法都是W使网络的最大 链路利用率最低作为其优化目标，但是传统网络里由于其分布式特性导致运个目标无法实 现，但运个目标在化enF 1OW网络里是可W实现的。
[0065] 为了使网络的最大链路利用率最低，可W枚举所有路由方法的组合，从中选择使 网络最大链路利用率最低的，若有多个最低的组合方法，则在其中选择消耗网络总资源最 少的方法(cost最小），为了实现运个思想提出W下步骤。
[0066] 第一步，求出网络中从一点到另一点的所有路径(不含环），并按路径长度递增存 储。求出网络中从一点（记为点A)到另一点（记为点B)的所有路径:一种方法是把整个网络 看做一个图，其中交换机(在传统网络中是路由器，在化enFlow网络中是交换机)是图的顶 点，实际链路为图的边。从A点进行深度优先遍历，遍历的过程中需要保证当前路径里不含 重复点，每当遍历到点B，就找到了一条从A至化的不含环路径，当遍历结束便可求出A至化的 所有路径。
[0067] 第二步，根据当前网络的所有流需求，求出其所有可能有的路径组合。当前网络有 两个流请求，流1从点A进入网络其目标节点为点B，流2从点C进入网络其目标节点为点D，其 中A至化有5条路径，C到D有8条路径，则所有的路由组合一共为40 (5*8)种。
[0068] 第Ξ步，计算出每种组合的网络链路利用率最大值，找出所有组合中最大链路利 用率最小的，如果链路利用率最小的有多种方案，则在它们中选取总cost值最小的，如果满 足上述条件的组合有多个，则在其中随机选取一个当做重路由方案。
[0069] 按组合的方案进行路由，并假定丢包率为0,且链路带宽无上限，计算出每条链路 上的理论流量(可能超过链路带宽），后由理论流量除W链路容量，为运条链路的利用率，在 所有链路的利用率中选取最大值就为运种组合的链路利用率最大值。
[0070] 本发明的目的是为了证明本发明中提出的QoS管理方法，相对于其它的QoS管理方 法具有优势，但由于QoS管理中的数据层算法有很多参数:队列管理算法有很多参数，队列 调度算法也有很多参数。而大多数文章的作者并未在其文章中说明其参数应该如何选取， 因此如果比较整套QoS解决方案则非常困难。本章会做两个实验，第一个实验的目的是证明 整个QoS方法的有效性，第二个实验的目的是证明本发明中的路由算法较其余的一些 化enFlow网络下的路由算法有优势。
[0071] 1、有效性验证实验需要进行Ξ次实验，第一次实验没有采用QoS管理方法，第二次 实验只采用本发明中的数据层处理方案，第Ξ次实验采用本发明中的整套QoS解决方案。
[0072] 第一次实验为化en vSwitch交换机配置FIFO队列调度方法，对所有到来的数据包 采用先来先服务，当网络拥塞时采用尾丢弃方法，为N0X控制器配置最短路径算法，让其为 所有数据包选择最短路径。
[0073] 第二次实验为EF数据流配置PQ优先队列，对其余流配置DR郎人列，即用PQ与DRR双 层队列调度方法其中AF4的Q值设置为5000，AF3的Q值设置为4000，AF2的Q值设置为3000， AF1的Q值设置为2000，BE的Q值设置为1000(Q值为DRR中的参数），队列管理采用WRED加权随 机早期检测算法。为N0X控制器配置最短路径算法，让其为所有数据包选择最短路径。
[0074] 第Ξ次实验为EF数据流配置PQ优先队列，对其余流配置DR郎人列，即用PQ与DRR双 层队列调度方法其中AF4的Q值设置为5000，AF3的Q值设置为4000，AF2的Q值设置为3000， AF1的Q值设置为2000，BE的Q值设置为1000(Q值为DRR中的参数），队列管理采用WRED加权随 机早期检测算法。为NOX控制器配置本发明中的SIWLU化路由算法W及邸VRA路由迁移算法。
[0075] Ξ次实验发包流程为：（实验一共运行45秒）
[0076] (1)第0秒模拟接收端对模拟发送端进行FTP下载请求。（FTP服务器设置的最大下 载速度为0.5MB/S)
[0077] (2)第8秒模拟发送端发送1个速度约为IMB/s每秒的udp数据流。
[0078] (3)第17秒模拟发送端发送1个速度约为IMB/s每秒的udp数据流。
[0079] (4)第28秒模拟发送端开始向模拟接收端发送码率为3500肺PS(大约0.427M/S)的 高清实时视频流传输层协议为udp。
[0080] (5)第40秒模拟发送端开始向模拟接受端发送码率为90肺S(大约O.OllM/s)的高 音质实时音频流，传输层协议为udp。
[0081] 实验结果:采用最短路径的路由结果即实验1，2的路由结果如表1所示：
[0082] 表1最短路径算法路由结果
[0083]
[0084] 采用本发明中的路由算法的路由结果，即实验3,4的路由结果如表2所示：
[0085] 表2本发明路由算法结果
[0086]
[0087] 在图1，4，5中里红色的点表示FTP流的速度，绿色的星号点表示第一个BE流的速 度，黑色的加号点表示实时视频的速度，蓝色的圆点表示第二个BE流的速度。
[0088] 在Ξ个图里红色的点表示FTP流的速度，绿色的星号点表示第一个邸流的速度，黑 色的加号点表示实时视频的速度，蓝色的圆点表示第二个BE流的速度。
[0089] 在实验一与实验二中由于第二个BE流的速度与第一个BE流的速度非常接近，如果 都在一个图里画出则会使数据叠加在一起导致图看不清。W上所有的点表示的不是那一时 刻的瞬时速度而是那一秒的平均速度，比如表示0到1秒的平均速度的点的横坐标为0.5。
[0090] 由于EF音频数据流的速度和W上运些不在一个数量级故单独画出。图4和图5表示 EF音频流的速度，其中第一次实验和第二次实验的的数据放在图4中，第Ξ次的实验数据放 在图5中，由于第二次实验和第Ξ次两次实验测得的EF数据流速度相差很小如果将运两次 的结果放在同一张图中则会导致两种数据叠加在一起导致无法辨别，因此将其放在两个图 中，其中图4中的黑色加号表示第一次实验中的EF数据流速度，图4中的绿色星号表示第二 次实验中的EF数据流速度，图5中的红色点表示第Ξ次实验中的EF数据流速度。[0091] 第二次实验数据与第一次实验数据对比发现，加入了数据层控制后能有效控制BE 流的速度降低其对网络的影响，并能为视频音频运种高优先级数据提供较好的服务，实验 二与实验Ξ对比发现加入了控制层后，网络的流量分布可W变得更均匀，从而能提升整个 网络的吞吐量，能进一步提升网络对高优先级业务的服务。通过实验证明运个QoS管理系统 是有效的。
[0092] 2、路由性能测试中，路由算法(含迁移部分)将会和其余的Ξ种化enFlow网络下的 路由算法进行对比，运Ξ种方法分别是13年陈志钢在其QoS系统中采用的WLU化方法，W及 13年Karl M，Gruen J，Herfet T等人提出的KGH路由方法W及最常用的最短路径算法。
[0093] WUJLL算法中有一个参数λ，经过实验发现λ值越小时，其性能越优，但当λ小到一定 程度时其值就开始对实验结果不造成影响（本部分的拓扑非常容易导致最短路径负载过 重，故λ越小越好)故为了使WUJ化算法发挥其最大潜力将其λ值取为0.01(在本实验中其能 取得运个算法的最优结果）。
[0094] 由于运个实验是比较路由算法，故在数据层并没有配置本发明中的队列管理与队 列调度算法，故本发明中参与比较的算法为IWL化L初次路由算法与邸VRA再次路由算法。
[0095] IWLU化中δ选择0.5，β选择2.5。邸VRA路径迁移中的参数t选择15s。
[0096] 由于KGH算法与WLU化算法中只有两类数据包，故为方便起见，实验中一共发送两 类数据包，分别是视频音频数据包(AF4流或EF流)和普通业务数据包(AF1流或肥流），通过 让其分别使用不同范围的端口，来让控制器区分其所属的类型。
[0097] 由于KGH算法只针对多媒体数据进行路由，并没有说明对非多媒体数据该如何进 行路由，故为了与其对比，与其比较两次，第一次两种数据包都发送，将KGH算法进行扩展， 为非多媒体数据选择最短路径，为多媒体数据按照原本的KGH算法选择路径。第二次实验， 网络中只发送多媒体数据包。
[0098] 实验结果:第一次两种数据包都发送的实验结果如表3所示：
[0099] 表3两种数据包都有实验结果
[0100]
[0101 ]只发送视频音频数据流实验结果如表4所示：
[0102] 表4只发送EF数据流实验结果
[0103]
[0104] 为了更好的区分四种算法的性能，实验过程中流量较大，且很多时候网络无法满 足所有流的流量需求，故四种算法在实验中丢包率都较高。
[0105] 经过实验对比发现本发明中的路由算法在丢包率，W及充分利用网络资源方面较 其余Ξ种算法有优势。
[0106] 下面对实验结果进行分析，经过实验观察发现最短路径算法在本发明的拓扑结构 中非常容易导致最短路径过载，造成在本实验中其性能非常差。WUJLL算法对链路利用率的 代价估计是线性的，故也容易发生链路过载;而KGH算法过载前与过载后链路权重只是变为 2倍，故WUJLL算法和K細算法并未对链路权重做出合理地估计，此外它们路由计算好后就不 再改变没有迁移模块，致使未充分发挥出化enFlow网络集中控制的优势。
【主权项】
1. 一种基于OpenFlow网络的QoS管理方法，其特征在于，包括如下步骤： (1) 在数据层上进行数据分类：区分服务模型将IP包头中的8位服务类型字段重新定义 为区分服务字段DS，区分不同业务，表示不同的优先级;EF代表加速转发;AF代表保证转发； BE代表尽力而为； (2) 在数据层上进行PQ队列调度与DRR队列调度相结合的队列调度： 用双层队列进行调度，第一层队列为PQ队列，这个队列里分两个优先级，把EF流定为高 优先级，其余流定为低优先级，当EF流发送完后，发送其余的流，其余的流发送采用DRR队列 调度算法；当正在发送非EF数据包时，EF数据包到来，则发送完当前数据包后对DRR运行状 态保存，然后开始发送EF数据包，直至EF队列为空，然后接着运行DRR调度算法； EF类业务被设为高优先级，EF类业务主要是指VOIP业务，以及网络协议控制报文； (3) 在数据层上进行队列管理： 采用WRED算法来进行队列管理，在交换机的每个出端口，汇集6个等待发送的队列，分 别是EF数据队列，AF1数据队列，AF2数据队列，AF3数据队列，AF4数据队列，BE数据队列，为 这6个队列分别设置自己的丢包长度下限，丢包长度上限，基准丢包率，分别记为minql， maxq1，ps;计算出每个队列的平均长度，记为avgq1.对于EF队列其四个数据分别表示为EF_ minql、EF_maxql、EF_ps和EF_avgl; 当一个数据包到来，先被分类，然后被送到对应的出端口，如果被分为EF类，则如果EF_avgl小于等于EF_minql则这个包可以进入EF队列排队，若EF_avgl大于EF_maxql则会对这 个包进行丢弃处理;若EF_avgl在EF_minql与EF_maxql之间则其以一定概率被丢弃； 具体概率为￡?_卩8*化?_&￥814?_111；[叫1)/化?_1]1&叉914?_111；[叫1); 平均队列长度计算方法为： Avgql=last_avgql*(l_x)+x*ql; 其中last_aVgql表示以前他的平均队列长度，ql表示当前队列长度，x=l/2n，n为可配 置的参数取大于1的整数； (4) 在控制层上根据数据流的类型和网络当前状况进行首次路由：控制器每隔一段时 间Τ就向OpenFlow交换机发送Read-state请求统计报文，获知交换机统计项里的流接收字 节数，计算一个流的速度选用的是所有交换机上的信息，在每一段链路上一个流的速度用 它的领接交换机进行计算，通过控制器求出当时AF1，AF2，AF3，AF4，BE，EF流的平均速度，在 控制器计算出一个路由后同时把这个流所在类的平均速度加到这个流所经过的每条链路 上，作为链路流量的修正值； 把第η次计算出的EF流的平均速度记为f(η)，第η次统计时网络当前EF流的平均速度记 为ν(η)，则迭代公式为： ?·(η)=λ?·(η-1) + (1-λ)ν(η)，η> = 2,且ν(η)>0即当前网络存在EF流； f(n)=f(n-l)，η> = 2,且ν(η)=0即当前网络不存在EF流； 其中l>A>〇，f(l)为对EF流速度的估计值，每个EF流的速度用它接触到的第一个OpenFlow交换机上的统计信息求得； (5) 在控制层上进行路由迀移： (5.1)求出网络中从一点到另一点的所有路径，并按路径长度递增存储;求出网络中从 一点A到另一点B的所有路径； (5.2) 根据当前网络的所有流需求，求出其所有可能有的路径组合； (5.3) 计算出每种组合的网络链路利用率最大值，找出所有组合中最大链路利用率最 小的，如果链路利用率最小的有多种方案，则在它们中选取总cost值最小的，如果满足上述 条件的组合有多个，则在其中随机选取一个当做重路由方案。
【专利摘要】本发明属于OpenFlow网络管理领域，具体涉及一种基于OpenFlow网络的QoS管理方法。本发明包括：在数据层上进行数据分类；在数据层上进行PQ队列调度与DRR队列调度相结合的队列调度；在数据层上进行队列管理；在控制层上根据数据流的类型和网络当前状况进行首次路由；在控制层上进行路由迁移。本发明通过业务的类别、链路利用率、流的速度，为链路赋予权值，完成路由算法的改进；利用软件定义网络集中控制的特性，提出了一种路由迁移算法，并对路由迁移的时机选择做了优化。
【IPC分类】H04L12/729, H04L12/815, H04L12/865, H04L12/851
【公开号】CN105490962
【申请号】CN201510884120
【发明人】孙建国, 李博权, 李守政, 张立国, 杨俊超
【申请人】哈尔滨工程大学
【公开日】2016年4月13日
【申请日】2015年12月4日
最新回复(0)