一种基于SDN的服务定制网络资源自适应分配方法

摘要

本发明公开了一种基于SDN的服务定制网络资源自适应分配技术，设计了基于SDN的服务定制网络资源分配机制的系统框架，主要包括拓扑管理、资源监测、服务定制和路由管理模块，并详细说明了各个模块的功能。针对网络状态动态变化的特点，设计了自适应机制，根据检测到的网络资源状况进行自适应调整，以提高网络资源利用率并适应用户更细粒度的需求情形，提高网络资源利用率，改善体验质量，实现整个网络的优化。本发明方法能够降低丢包率，提高带宽利用率，减少时间开销，提高网络资源利用率。

权利要求

1.一种基于SDN的服务定制网络资源自适应分配方法，其特征在于：包括系统框架、资源分配问题模型、服务定制机制以及基于改进蚁群算法的资源分配机制；

所述系统框架的建立、资源分配问题模型的建立、服务定制的设计以及基于改进蚁群算法的资源分配机制设计步骤包括：

步骤1基于SDN的服务定制网络资源自适应分配技术设计的系统模型，包括网络测量、拓扑管理、资源请求以及资源分配模块；

步骤2对网络资源分配问题进行建模，包括网络模型、请求资源模型、服务定制模型以及资源分配模型；

步骤3对服务定制方法进行设计，包括获取用户需求、用户需求分析以及服务定制资源；

步骤4对传统的蚁群算法进行改进，设计出一种改进蚁群算法的资源分配方法；

所述步骤2的具体步骤包括：

步骤2.1将网络表示为一个有向连接图G＝(V，E)，由基础设备和链路组成，所有的顶点集合V＝H∪S由主机集合H＝{h1，h2，h3，...hn}和交换机集合S＝{s1，s2，s3，...sn}组成；

步骤2.2交换机节点模型为S＝{id，Tcapi，Ptapi，Ftapi，linkset，level}，其中id表示交换机的唯一标识；每个交换机si∈S维护一个基于TCAM的流表FlowTab，FlowTab中可存储规则数目为Tcapi，FlowTab由高级策略规则表Ptapi＝{rp1，rp2，rp3，...rpm}和转发规则表Ftapi＝{rf1，rf2，rf3，...rfm}组成，Ptapi和Ftapi分别表示策略规则表和转发规则表的大小；

linkset表示该节点到下个节点的集合，level表示交换机在拓扑中的层次；为了避免交换机规则空间被100％全部利用，分别用式(1)和(2)表示分配高级策略规则空间和转发规则空间的大小，其中portion表示交换机流规则空间可以分配给高级策略空间的比例，THRTCAM表示交换机规则空间的最大利用率；

Ftapi＝Tcapi×THRTCAM×portion          (1)Fcapi＝Tcapi×THRTCAM×(1‑portion)        (2)步骤2.3用Flow表示数据流类，存储数据流的相关信息，每个数据流描述为Flow＝(Fid，Fips，Fipd，Fports，Fportd，Frate，Ftime，Fpath，edgeset，T)；其中，Fid用以标识一个数据流，Fips和Fipd分别代表它的源IP地址和目的IP地址，Fports和Fportd分别代表它的源端口地址和目的端口地址，Frate表示数据流的速率，Ftime表示当前的时间戳，Fpath表示数据流经过的一系列交换机节点的有序序列，edgeset表示边的集合，T表示更新时间间隔，T的取值与网络状态相关，网络正常情况下，其值为固定值，当网络中出现突发状况时，立即更新；

步骤2.4对延迟、抖动以及丢包率这三个因素进行归一化处理，使其化为量纲可比较的数据；

(1)延迟：对延迟进行归一化计算如式(3)所示：Delayi，j＝(delayi，j‑delaymin)/(delaymax‑delaymin)       (3)其中，Delayi，j表示节点i与节点j之间归一化后的延迟值，delayi，j表示节点i与节点j之间的实际时延，在整个网络拓扑图中，delaymax和delaymin分别表示所有链路中延迟的最大值、最小值；

(2)抖动：对抖动进行归一化计算如式(4)所示：Jitteri，j＝(jitteri，j‑jittermin)/(jittermax‑jittermin)        (4)其中，Jitteri，j表示节点i与节点j之间归一化后的抖动值，jitteri，j表示节点i与节点j之间的实际抖动，在整个网络拓扑图中，jittermax和jittermin分别表示所有链路中抖动的最大值、最小值；

(3)丢包率：对丢包率进行归一化计算如式(5)所示：LossRatei，j＝(lossratei，j‑lossratemin)/(lossratemax‑lossratemin)     (5)其中，LossRatei，j表示节点i与节点j之间归一化后的丢包率值，lossratei，j表示节点i与节点j之间的实际丢包率，在整个网络拓扑图中，lossratemax和lossratemin分别表示所有链路中丢包率的最大值、最小值；

步骤2.5对用户请求资源进行建模，每一个用户需求可以用一个五元组表示，Uid是该用户的唯一标识，Udes表示最终目的，Ubw表示带宽，Ust表示开始时间，Uft表示结束时间；

步骤2.6当用户在特定时间段内需要网络资源时，用户将资源请求发送给控制器；每个定制服务可以使用相互独立的物理资源，网络中可以同时存在多个定制服务，然后把用户网络请求生成定制服务；对于任何r∈rsd的路由可以定义为：fc(r)＝∑(i，j)∈rcij             (6)fd(r)＝∑(i，j)∈rdij               (7)其中，rsd表示路由，cij表示代价，dij代表时延，fc(r)表示总代价，fd(r)表示总时延，cij＝βgij+(1‑β)pij，β值可变，pij表示丢包率，gij表示带宽利用率，代价cij最终表示为：cij＝βgij+(1‑β)pij             (8)步骤2.7资源分配流的建立过程包括：首先将第一个发送的数据包发送给控制器进行处理，同时控制器需要每隔2s查询网络链路状态信息，为了实现基于SDN的服务定制网络资源自适应分配方法，控制器需要进行流量监测以及收集网络资源状态信息数据。

2.根据权利要求1所述的一种基于SDN的服务定制网络资源自适应分配方法，其特征在于：所述步骤1中的基于SDN的服务定制网络资源自适应分配技术设计的系统模型包括网络测量、拓扑管理、资源请求以及资源分配模块；

所述步骤1的具体步骤包括：

步骤1.1拓扑管理，为了能够实时获得网络拓扑信息，SDN中的控制器需要周期性的收集全局网络拓扑信息，然后为应用规划出一条合理的路径；

步骤1.2资源监测，SDN控制器中的资源监测模块不仅能够监测链路的延迟、丢包率QoS信息以及网络剩余有限资源的信息，还可以测量出交换机设备的流统计信息；其负责收集和维护有关网络当前状态的信息；除了目前已经在OpenFlow控制器上实现的拓扑发现功能之外，还使用流统计信息收集功能扩充了网络测量模块；

步骤1.3服务定制，服务定制模块利用控制器中拓扑管理模块与网络测量模块提供的信息，然后为不同服务质量等级下的应用计算出满足其服务需求的多条路径，并从中选择一条最优路径用于数据流转发，最后将剩余的其它路径的信息存储到文件中，以保证路由的可靠性与容错性；

步骤1.4路由管理，路由管理模块采用数据流不分割的思想，即属于相同流的数据分组在相同的路径上传输；然后根据网络拓扑的情况为目的主机绑定合适的路径，决定数据分组从入口交换机到出口交换机在网络上传输的路径。

3.根据权利要求1所述的一种基于SDN的服务定制网络资源自适应分配方法，其特征在于：所述步骤3的具体步骤包括：

步骤3.1构建用户文档，在服务定制模块中我们将用户的需求描述为用户文档；在具体的执行过程中，系统要对各种不同类型用户的实际需求进行有效的采集，并构建用户文档，可以通过在建立连接之前提交用户文档来减少控制开销，以保证网络资源利用率的最大化；

步骤3.2对所有可能影响用户体验的需求进行分析，依据不同的通信特征实现对用户请求的分类，然后对其进行深入地分析、整理和统计，进而有效地获取各个不同类型通信的需求；

步骤3.3根据用户的实际需要，系统进行合理地配置，以保证提供完善的网络服务；对于每一种服务，将每一种服务对应的属性予以定义，并将其划分成多种服务等级；

步骤3.4根据用户需求提供相应的资源分配方案，系统输入：服务期望的网络时间、网络位置、需要的设备数量、网络吞吐量和设备的期望速率根据网络需求调用事先定义好的解决方案模板提供定制化的网络资源分配。

4.根据权利要求1所述的一种基于SDN的服务定制网络资源自适应分配方法，其特征在于：所述步骤4的具体步骤包括：

步骤4.1改进的蚁群算法首先对相关的参数进行初始化操作，包括设置时间和迭代次数，根据公式(11)进行更新，否则将继续路径的搜索直到输出最优路径；

步骤4.2通过实现蚂蚁路径的选择进行合理的资源分配，以提高网络资源利用率；

步骤4.3在资源分配算法中网络可以用G＝(V，E)表示，其中V＝(v1，v2，v3，...vn)表示网络中的所有节点，E＝(e1，e2，e3，...em)表示两个节点之间物理链路组成的集合；n表示节点的数量，m表示链路的数量； 表示链路成本， 表示链路时延，C(p)表示链路总成本，D(p)表示链路总时延；

在下列公式中，λ表示拉格朗日乘子，Cλ(p)表示成本代价和时延的聚合代价，Δdelay表*

示时延限制，p表示资源分配的最优路径，Pst表示源节点到目的节点的路径；

*

p＝min{C(p)|D(p)≤Δdelay}，p∈Pst          (11)表示(vi，vj)的链路使用率，α表示链路使用率的权重；

步骤4.4首先进行相关参数的初始化，在寻找链路拥塞较低路径的同时需要满足时延要求，计算出最优路径进行数据传输，然后根据用户需求提供相应的资源分配方案，系统输入服务期望的网络时间和网络位置，需要的设备数量、网络吞吐量、设备的期望速率根据网络需求调用事先定义好的解决方案模板提供定制化的网络资源分配。

说明书

一种基于SDN的服务定制网络资源自适应分配方法

技术领域

[0001] 本发明属于通信技术领域，一种基于SDN的服务定制网络资源自适应分配方法主要涉及资源检测、服务定制和路由管理方法。

背景技术

[0002] 随着互联网规模的飞速增长以及互联网应用的多样化，现有网络也逐步显现出了各种问题，比如缺乏对业务提供差异化服务的能力、网络中存在大量的冗余传输以及缺乏
对网络数据的感知和应用能力。针对当前互联网中存在的问题，提出了一种具有差异化服
务能力的未来网络体系架构—服务定制网络。服务定制网络基于软件定义网络设计，继承
了其数据控制分离以及网络可编程的主要特点，并针对当前互联网中的问题，增加了网络
虚拟化能力以及内容智能调度能力。

[0003] 服务定制网络资源自适应分配技术因网络中的应用类型日益丰富，不同的应用不仅具有独特的特征流，而且具有不同的服务需求所提出，资源分配主要是对网络流量的测
量、调度和管理，并设计合理的路由机制来指导网络流量转发，以提高网络资源的利用率，
进而更好地满足网络流量的服务质量需求。面向频繁变化的网络状态和网络资源供给情
况，针对用户多样化的需求情形，改进了蚁群算法开展服务定制来适应用户更细粒度的需
求情形，提高资源的利用率并提高用户体验质量，设计了一种基于SDN的服务定制网络资源
自适应分配方法。

发明内容

[0004] 本发明的目的是基于SDN技术，利用SDN集中控制和具有全局可观性的优势，根据用户多样化的需求，为不同的应用提供更好的QoS保证，设计一种网络资源自适应分配机
制，进行个性化服务定制。

[0005] 本发明的技术方案是：一种基于SDN的服务定制网络资源自适应分配方法，包括系统框架、资源分配问题模型、服务定制机制以及基于改进蚁群算法的资源分配机制，其主要
步骤包括：

[0006] 步骤1设计基于SDN的服务定制网络资源自适应分配系统模型，包括网络测量、拓扑管理、资源请求以及资源分配模块；

[0007] 步骤2对网络资源分配问题进行建模，包括网络模型、请求资源模型、服务定制模型以及资源分配模型；

[0008] 步骤3对服务定制方法进行设计，包括获取用户需求、用户需求分析以及服务定制资源；

[0009] 步骤4对传统的蚁群算法进行改进，设计出一种改进蚁群算法的资源分配方法；

[0010] 基于SDN的服务定制网络资源自适应分配方法的研究思路如下：首先基于SDN思想，利用OpenFlow技术，通过使用OpenFlow控制器，来收集网络中的所有拓扑信息，并经过
OpenFlow协议与OpenFlow交换机进行通信，然后通过控制器向交换机下发消息，交换机可
以根据接收的数据流的特性进行路由转发。在SDN网络中将控制平面与数据平面进行分离
解耦，在一个基于OpenFlow的SDN网络中，一台控制器控制多台OpenFlow交换机，控制器根
据链路层发现协议LLDP收集控制器与交换机以及交换机与交换机之间的链路信息，控制器
进而通过控制OpenFlow交换机实现对整个网络的管理控制。当有新的数据包到达时，交换
机执行流表字段匹配、数据流转发等操作。在本专利设计的基于SDN的服务定制网络资源自
适应分配方法中，当新的业务数据包到达时，进行业务识别并进行服务定制，对最高优先级
的业务使用QoS路由算法路由，对其他优先级业务，使用Dijkstra算法路由寻找最短路径，
针对网络状态动态变化的特点，设计了自适应机制，根据检测到的网络资源状况进行自适
应调整，以提高资源利用率并适应用户更细粒度的需求情形，提高网络资源的利用率，改善
体验质量，实现整个网络系统的优化。交换机发送数据包，并接收来自控制器下发的数据
包。控制器和交换机必须通过安全通道进行通信，而且进行通信的数据包必须按照
OpenFlow协议规定的格式执行。流表是数据转发的依据，流表由控制器下发给交换机。将其
封装成Packet in数据包，转发给控制器，由SDN控制器决定应该如何处理，并下发相应流
表；

[0011] 所述步骤1的具体步骤包括：

[0012] 步骤1.1拓扑管理，为了能够实时获得网络拓扑信息，SDN中的控制器需要周期性的收集全局网络拓扑信息，然后为应用规划出一条合理的路径。其主要流程如下：

[0013] (1)交换机通过电信号连接到控制器，此时控制器知道有交换机接入，但是不知道这些交换机之间是如何连接的；

[0014] (2)控制器采用OpenFlow协议中的Packet‑Out消息，将带有协议的报文封装到Packet‑Out消息中并分别发送给与控制器连接的全部交换机。所有的交换机收到Packet‑
Out消息后，将执行Packet‑Out中包含的LLDP报文指令；

[0015] (3)当与之相连的交换机收到封装LLDP协议的消息时，相连的交换机利用OpenFlow协议中的Packet‑In消息，将带有协议的报文封装到Packet‑In消息中并向上发送
给控制器；

[0016] (4)当控制器收到所有交换机发送的带有LLDP协议的Packet‑In消息后，从Packet‑In消息中提取信息然后得知交换机之间的连接关系，进而获取全局网络拓扑图的
信息。

[0017] 步骤1.2资源监测，SDN控制器中的资源监测模块不仅能够监测链路的延迟、丢包率等QoS信息以及网络剩余有限资源的信息，而且还可以测量出交换机设备的流统计信息。
其负责收集和维护有关网络当前状态的信息。除了目前已经在OpenFlow控制器上实现的拓
扑发现功能之外，本专利还使用流统计信息收集功能扩充了网络测量模块。

[0018] 步骤1.3服务定制，服务定制模块利用控制器中拓扑管理模块与网络测量模块提供的信息，然后为不同服务质量等级下的应用计算出满足其服务需求的多条路径，并从中
选择一条最优路径用于数据流转发，最后将剩余的其它路径的信息存储到文件中，以保证
路由的可靠性与容错性。

[0019] 步骤1.4路由管理，路由管理模块采用数据流不分割的思想，即属于相同流的数据分组在相同的路径上传输。然后根据网络拓扑的情况为目的主机绑定合适的路径，决定数
据分组从入口交换机到出口交换机在网络上传输的路径。

[0020] 所述步骤2的具体步骤包括：

[0021] 步骤2.1将网络表示为一个有向连接图G＝(V，E)，由基础设备和链路组成，所有的顶点集合V＝H∪S由主机集合H＝{h1，h2，h3，...hn}和交换机集合S＝{s1，s2，s3，...sn}组成；

[0022] 步骤2.2交换机节点模型为S＝{id，Tcapi，Ptapi，Ftapi，linkset，level}，其中id表示交换机的唯一标识。每个交换机si∈S维护一个基于TCAM‑的流表FlowTab，FlowTab中
可存储规则数目为Tcapi，FlowTab由高级策略规则表Ptapi＝{rp1，rp2，rp3，...rpm}和转发规
则表Ftapi＝{rf1，rf2，rf3，...rfm}组成，Ptapi和Ftapi分别表示策略规则表和转发规则表的
大小。linkset表示该节点到下个节点的集合，level表示交换机在拓扑中的层次。为了避免
交换机规则空间被100％全部利用，分别用式(1)和(2)表示分配高级策略规则空间和转发
规则空间的大小，其中portion表示交换机流规则空间可以分配给高级策略空间的比例，
THRTCAM表示交换机规则空间的最大利用率；

[0023] Ftapi＝Tcapi×THRTCAM×portion                   (1)

[0024] Fcapi＝Tcapi×THRTCAM×(1‑portion)              (2)

[0025] 步骤2.3用Flow表示数据流类，存储数据流的相关信息，每个数据流描述为Flow＝(Fid，Fips，Fipd，Fports，Fportd，Frate，Ftime，Fpath，edgeset，T)。其中，Fid用以标识一个数据
流，Fips和Fipd分别代表它的源IP地址和目的IP地址，Fports和Fportd分别代表它的源端口
地址和目的端口地址，Frate表示数据流的速率，Ftime表示当前的时间戳，Fpath表示数据流经
过的一系列交换机节点的有序序列，edgeset表示边的集合，T表示更新时间间隔，T的取值
与网络状态相关，网络正常情况下，其值为固定值，当网络中出现突发状况时，立即更新；

[0026] 步骤2.4对延迟、抖动以及丢包率这三个因素进行归一化处理，使其化为量纲可比较的数据。

[0027] (1)延迟：对延迟进行归一化计算如式(3)所示：

[0028] Delayi，j＝(delayi，j‑delaymin)/(delaymax‑delaymin)      (3)

[0029] 其中，Delayi，j表示节点i与节点j之间归一化后的延迟值，delayi，j表示节点i与节点j之间的实际时延，在整个网络拓扑图中，delaymax和delaymin分别表示所有链路中延迟的
最大值、最小值。

[0030] (2)抖动：对抖动进行归一化计算如式(4)所示：

[0031] Jitteri，j＝(jitteri，j‑jittermin)/(jittermax‑jittermin)     (4)

[0032] 其中，Jitteri，j表示节点i与节点j之间归一化后的抖动值，jitteri，j表示节点i与节点j之间的实际抖动，在整个网络拓扑图中，jittermax和jittermin分别表示所有链路中抖
动的最大值、最小值。

[0033] (3)丢包率：对丢包率进行归一化计算如式(5)所示：

[0034] LossRatei，j＝(lossratei，j‑lossratemin)/(lossratemax‑lossratemin)    (5)

[0035] 其中，LossRatei，j表示节点i与节点j之间归一化后的丢包率值，lossratei，j表示节点i与节点j之间的实际丢包率，在整个网络拓扑图中，lossratemax和lossratemin分别表
示所有链路中丢包率的最大值、最小值。

[0036] 步骤2.5对用户请求资源进行建模，每一个用户需求可以用一个五元组表示，Uid是该用户的唯一标识，Udes表示最终目的，Ubw表示带宽，Ust表示开始时
间，Uft表示结束时间；

[0037] 步骤2.6当用户在特定时间段内需要网络资源时，用户将资源请求发送给控制器。每个定制服务可以使用相互独立的物理资源，网络中可以同时存在多个定制服务，然后为
用户网络请求生成定制服务。对于任何r∈rsd的路由可以定义为：

[0038] fc(r)＝∑(i，j)∈rcij                             (6)

[0039] fd(r)＝∑(i，j)∈rdij                            (7)

[0040] 其中，rsd表示路由，cij表示代价，dij代表时延，fc(r)表示总代价，fd(r)表示总时延，cij＝βgij+(1‑β)pij，β值可变，pij表示丢包率，gij表示带宽利用率，代价cij最终表示为：

[0041] cij＝βgij+(1‑β)pij    (8)

[0042] 步骤2.7资源分配流的建立过程包括：首先将第一个发送的数据包发送给控制器进行处理，同时控制器需要每隔2s查询网络链路状态信息，为了实现基于SDN的服务定制网
络资源自适应分配方法，控制器需要进行流量监测以及收集网络资源状态信息等数据。

[0043] 所述步骤3的具体步骤包括：

[0044] 步骤3.1构建用户文档，在服务定制模块中我们将用户的需求描述为用户文档。在具体的执行过程中，系统要对各种不同类型用户的实际需求进行有效的采集，并构建用户
文档，可以通过在建立连接之前提交用户文档来减少控制开销，以保证网络资源利用率的
最大化；

[0045] 步骤3.2对所有可能影响用户体验的需求进行分析，依据不同的通信特征实现对用户请求的分类，然后对其进行深入地分析、整理和统计，进而有效地获取各个不同类型通
信的需求；

[0046] 步骤3.3根据用户的实际需要，系统进行合理地配置，以保证提供完善的网络服务。对于每一种服务，将每一种服务对应的属性予以定义，并将其划分成多种服务等级；

[0047] 步骤3.4根据用户需求提供相应的资源分配方案，系统输入：服务期望的网络时间、网络位置、需要的设备数量、网络吞吐量和设备的期望速率根据网络需求调用事先定义
好的解决方案模板提供定制化的网络资源分配；

[0048] 所述步骤4的具体步骤包括：

[0049] 步骤4.1改进的蚁群算法首先对相关的参数进行初始化操作，包括设置时间和迭代次数，根据公式(11)进行更新，否则将继续路径的搜索直到输出最优路径。

[0050] 步骤4.2通过实现蚂蚁路径的选择进行合理的资源分配，以提高网络资源利用率。

[0051] 步骤4.3在资源分配算法中网络可以用G＝(V，E)表示，其中V＝(v1，v2，v3，...vn)表示网络中的所有节点，E＝(e1，e2，e3，...em)表示两个节点之间物理链路组成的集合。n表
示节点的数量，m表示链路的数量。 表示链路成本， 表示链路时延，C(p)表示链路总
成本，D(p)表示链路总时延，则有：

[0052]

[0053]

[0054] 在下列公式中，λ表示拉格朗日乘子，Cλ(p)表示成本代价和时延的聚合代价，*
Δdelay表示时延限制，p表示资源分配的最优路径，Pst表示源节点到目的节点的路径。

[0055] p*＝min{C(p)|D(p)≤Δdelay，p∈Pst    (11)

[0056]

[0057]

[0058] 表示(vi，vj)的链路使用率，α表示链路使用率的权重。

[0059]

[0060] 步骤4.4首先进行相关参数的初始化，在寻找链路拥塞较低路径的同时需要满足时延要求，计算出最优路径进行数据传输，然后根据用户需求提供相应的资源分配方案，系
统输入服务期望的网络时间和网络位置，需要的设备数量、网络吞吐量、设备的期望速率等
根据网络需求调用事先定义好的解决方案模板提供定制化的网络资源分配。

[0061] 本发明的主要有益效果是：

[0062] 可以降低丢包率、提高带宽利用率、减少时间开销以及提高网络资源利用率。同时还可以进行个性化服务定制，在面向频繁变化的网络状态和网络资源供给的情况下，针对
用户多样化的需求情形，同构改进蚁群算法开展服务定制来适应用户更细粒度的需求情
形，提高网络资源利用率，改善体验质量。

附图说明

[0063] 图1为基于SDN的服务定制网络资源自适应分配方法系统模型图。

[0064] 图2为链路测量示意图。

[0065] 图3为数据分组转发流程图。

[0066] 图4为资源分配流程。

[0067] 图5基于SDN服务定制网络资源分配系统框架图。

[0068] 图6为应用编号与名称图。

[0069] 图7为丢包率对比图。

[0070] 图8为带宽利用率对比图。

[0071] 图9为时间开销对比图。

具体实施方式

[0072] 本发明提出了一种基于SDN的服务定制网络资源自适应分配方法。该方法基于SDN思想，然后利用OpenFlow技术，通过使用OpenFlow控制器收集网络中所有的拓扑信息。通过
使用OpenFlow协议与OpenFlow交换机进行通信，控制器向交换机下发信息，交换机可以根
据所接收数据流的特性进行路由转发。本专利提出的基于SDN的服务定制网络资源自适应
分配技术，当新的业务数据包到达时，通过对业务进行识别然后进行服务定制，对最高优先
级的业务使用QoS路由算法路由，对其他优先级的业务使用Dijkstra算法路由寻找最短路
径。针对网络状态动态变化的特点，设计了自适应机制，根据监测到的网络资源状况进行自
适应调整，以提高资源利用率并满足用户更细粒度的需求情形，改善体验质量，实现整个网
络系统的优化。交换机发送数据包，并接收来自控制器下发的数据包。控制器和交换机必须
通过安全通道进行通信，而且进行通信的数据包必须按照OpenFlow协议规定的格式执行。
流表由控制器下发给交换机，是数据转发的依据。将流表封装成Packet_in数据包转发给控
制器，由SDN控制器决定应该如何处理，然后下发相应的流表。以下详细说明本发明方法涉
及的关键步骤。

[0073] 基于SDN的服务定制网络资源自适应分配方法包括以下几方面的内容：

[0074] 1.系统模型

[0075] 请参阅图1所示的基于SDN的服务定制网络资源自适应分配方法系统模型图，主要包括以下步骤：

[0076] 1.1拓扑管理

[0077] 为了能够实时的获得网络拓扑信息，SDN控制器需要周期性的收集全局网络拓扑信息，从而为应用规划出一条合理的路径。控制器为了获得数据层的全局网络拓扑信息，利
用OpenFlow和LLDP(LinkLayer Discovery Protocol)两种协议来进行协助。其主要的工作
流程如下：

[0078] (1)交换机通过电信号连接到控制器，此时控制器知道有交换机接入，但是不知道这些交换机之间是如何连接的；

[0079] (2)控制器采用OpenFlow协议中的Packet‑Out消息，将带有协议的报文封装到Packet‑Out消息中并分别发送给与控制器连接的全部交换机。所有的交换机收到Packet‑
Out消息后，将执行Packet‑Out中包含的LLDP报文指令；

[0080] (3)当与之相连的交换机收到封装LLDP协议的消息时，相连的交换机利用OpenFlow协议中的Packet‑In消息，将带有协议的报文封装到Packet‑In消息中并向上发送
给控制器；

[0081] (4)当控制器收到所有交换机发送的带有LLDP协议的Packet‑In消息后，从Packet‑In消息中提取信息然后得知交换机之间的连接关系，进而获取全局网络拓扑图的
信息。

[0082] 控制器根据链路层发现协议LLDP收集信息，通过拓扑管理模块，控制器可以通过控制OpenFlow交换机实现对整个网络的管理控制。节点资源是节点所能提供的CPU和内存，
链路资源指的是网络中的链路所能够提供的带宽资源。

[0083] 1.2资源监测

[0084] SDN控制器中的资源监测模块不仅能够监测链路的延迟、丢包率等QoS信息以及网络剩余有限资源的信息，而且还可以测量出设备的流统计信息。其负责收集和维护有关网
络当前状态的信息。除了目前已经在OpenFlow控制器上实现的拓扑发现功能之外，本专利
还使用流统计信息收集功能扩充了该模块。如图2所示，计算交换机1与交换机2之间的链路
时延：

[0085] (1)Controller向交换机1下发Packet‑Out报文此时的时间为t1，然后交换机1将Packet‑Out报文发送到交换机2；交换机2转发到controller，controller收到Packet‑In消
息后，记录接收到该消息的时间t2；

[0086] (2)根据得到的t1和t2相减，得到Controller发送给交换机1后转发交换机2最后返回给控制器消息传递的总时间t2‑t1；

[0087] (3)记录Controller和交换机1之间的RTT1，Controller与交换机2之间的RTT2；

[0088] (4)根据以上信息，可以得到交换机1和交换机2之间的链路时延用公式(1)表示：

[0089]

[0090] 计算交换机1和交换机2之间的链路当前流量带宽，包含端口号、接收的报文个数、发送的报文个数、接收的字节数、发送的字节数以及统计时间。计算链路带宽的吞吐量，在
t1时刻，端口发送为Tx1，端口接收为Rx1；在t2时刻，端口发送为Tx2，端口接收为Rx2，如公式
(2)所示：

[0091]

[0092] 那么端口剩余资源，即可用带宽值，设链路带宽的容量为MaxBandwidth1，2，具体计算如公式(3)所示：

[0093] AvailableBandwidth1，2＝MaxBandwidth1，2‑CurrentBandwidth1，2    (3)

[0094] 设β表示链路使用率，链路使用率反映了网络业务数据流传输的拥塞程度，链路使用率越高，说明链路的拥塞程度越高。使用公式(4)来计算链路使用率：

[0095] β＝CurrentBandwidth1，2/MaxBandwidth1，2    (4)

[0096] 如果链路使用率过高，当超过一定值会出现拥塞，设上限值为βhigh，如果链路使用率过低，当低于一定值时会出现大量空闲，设下限值为βlow。

[0097] 1.3服务定制

[0098] 服务定制模块利用控制器中拓扑管理模块与网络测量模块提供的信息，为不同QoS等级下的应用计算出满足其服务需求的多条路径，然后从中选择一条最优路径用于数
据流转发，将剩余的其他路径信息存储到文件中，以保证路由的可靠性与容错性；

[0099] 为了更好地进行服务定制资源分配，本专利设计了一种基于SDN的服务定制网络资源自适应分配方法，整个方法的大致流程如图3所示：

[0100] (1)交换机从输入端口接收到达的数据分组；

[0101] (2)OF switch将收到的数据分组与流表中的流规则进行匹配；

[0102] (3)如果数据分组匹配失败，将Packet‑In消息向上发送给控制器；

[0103] (4)控制器中的控制消息管理模块从Packet‑In中携带的数据分组的头部字段中分析识别需求；

[0104] (5)根据应用的QoS需求将应用映射到不同的QoS等级；

[0105] (6)路径计算模块为具有不同类别的QoS的应用计算出最优的路径，并将感知结果与选择的最优路径信息发送到控制器中的控制消息管理模块；

[0106] (7)控制消息管理模块根据感知结果和路径计算模块计算出的最优路径构建Flow‑Mod消息并发送至交换机；

[0107] (8)交换机根据Flow‑Mod消息安装流规则；

[0108] (9)交换机根据流规则将数据分组发送到最佳路径的相应输出端口的输出缓冲区中，进行数据分组的转发；

[0109] 若最优路径中的链路发生了故障或拥塞，应用会向控制器发送相应的请求消息，控制器接收到请求信息后为该应用选择剩下路径中的最优路径并下发给交换机，交换机将
会迅速切换到这条新路径上以继续为应用转发数据分组；否则，持续在最优的路径上进行
转发。

[0110] 1.4路由管理

[0111] 路由管理模块采用数据流不分割的思想，即属于相同流的数据分组在相同的路径上传输。根据网络拓扑的情况，为目的主机绑定合适的路径，决定数据分组从入口交换机到
出口交换机在网络上传输的路径。

[0112] 首先基于栈结构根据深度优先遍历算法，以拓扑管理模块中创建的邻接矩阵AM为输入，找出有向图G＝(V，E憖中从ingress到egress之间的所有路径P＝{p1，p2，...pn}，主要
思想是从初始点开始遍历其邻接节点a00，再遍历a00的邻接节点a10，直到遍历到终点时表明
找到一条路径。主要包括以下步骤：

[0113] (1)以ingress为初始点，做入栈操作，并标记为已访问；

[0114] (2)根据邻接矩阵AM，查找top_node是否存在没有入栈且非空的邻接点adjvex_node；

[0115] (3)如果存在，将adjvex_node入栈，标记为已访问，并置adjvex_node为top_node；

[0116] (4)如果不存在，清空top_node访问过的节点集，弹出top_node；

[0117] (5)如果top_node为终点，则找到ingress与egress之间的一条路径，记录该路径中经过的节点，弹出top_node，标记为未访问；

[0118] (6)重复执行(2)‑(5)，直到栈为空，遍历完成，找到所有路径。

[0119] 2.资源分配问题

[0120] 2.1网络模型

[0121] SDN网络拓扑由控制器和交换机组成，对于到达交换机的未知数据流，需要控制器的参与，然后由控制器对该流量制定转发策略，交换机根据制定的流表规则进行转发。网络
可以抽象成一个连通图G＝(V，E)，其中V＝(v1，v2，v3，...vn)是节点集，代表网络中的节点，
由基础设备和链路组成，所有的顶点集合V＝H∪S包括两部分，由主机集合H＝{h1，h2，
h3，...hn}和交换机集合S＝{s1，s2s3，..sn}组成。

[0122] 2.1.1网络拓扑模型

[0123] 将网络表示为一个有向连接图G＝(V，E)，由基础设备和链路组成，所有的顶点集合V＝H∪S包括两部分，由主机集合H＝{h1，h2，h3，...hn}和交换机集合S＝{s1，s2，s3，...sn}
组成。其中E＝(e1，e2，e3，...emx是链路集，表示两个节点之间的连接。链路表示为边集合E
＝Esh∪Ess也包括两部分，其中Esh＝{eij，i∈S，j∈H}表示交换机与主机之间的通信链路，其
中Ess＝{ekl，k，l∈S}表示交换机之间的通信链路，Maxndegree和Avgndegree分别表示拓扑最大
节点度数和平均节点度数，Type＝{distributed，centralized}表示网络拓扑的类型，A＝
{aij，i，j≤Nswitch}表示拓扑的邻接矩阵，如式(5)所示：

[0124]

[0125] 2.1.2节点模型

[0126] 交换机节点模型为S＝{id，Tcapi，Ptapi，Ftapi，linkset，level}，其中id表示交换机的唯一标识。每个交换机si∈S维护一个基于TCAM的流表FlowTab，FlowTab中可存储规则
数目为Tcapi，FlowTab由高级策略规则表Ptapi＝{rp1，rp2，rp3，...rpm}和转发规则表Ftapi＝
{rf1，rf2，rf3，...rfmm}组成，Ptapi和Ftapi分别表示策略规则表和转发规则表的大小。
linkset表示该节点到下个节点的集合，level表示交换机在拓扑中的层次。

[0127] 2.1.3数据流模型

[0128] 用Flow表示数据流类，存储数据流的相关信息，每个数据流描述为Flow＝(Fid，Fips，Fipd，Fports，Fportd，Frate，Ftime，Fpath，edgeset，T)。其中，Fid用以标识一个数据流，
Fips和Fipd分别代表它的源IP地址和目的IP地址，Fports和Fportd分别代表它的源端口地
址和目的端口地址，Frate表示数据流的速率，Ftime表示当前的时间戳，Fpath表示数据流经过
的一系列交换机节点的有序序列，edgeset表示边的集合，T表示更新时间间隔，T的取值与
网络状态相关，网络正常情况下，其值为固定值，当网络中出现突发状况时，立即更新；

[0129] 2.1.4链路模型

[0130] 链路使用单双工的方式，将网络中的真实链路逻辑抽象为一条有向边，用edge＝(eid，es，et，eps，ept)表示。其中eid标识边，es标识出节点，et标识入节点，eps标识出端口，ept
标识入端口。路径表示为R(loc，pkt)＝{s1，s2，s3，...sn}，其中loc表示出口交换机的出端
口，s1，s2s3，...sn表示该数据分组在网络中经过的交换机集合。

[0131] 为了满足多方面的服务需求，本专利考虑在多约束条件下为应用计算QoS路由，考虑的约束条件主要来源于QoS参数指标，计算多约束条件QoS路由是一个多目标优化问题，
属于NP‑hard问题，本专利利用加权评估函数将多目标转换为单目标模型，在考虑延迟、抖
动和丢包率的因素下，使用一组加权系数将多约束条件转化为一个单目标函数，进而构成
一个新的路由度量值。为了在多因素影响下求取最小值，将多约束多目标转换为单目标函
数的计算如公式(6)所示

[0132] min f(i，j)＝min(α×Delayi，j+β×Jitteri，j+γ×LossRatei，j)     (6)

[0133] 其中，i，j表示网络中相邻的两个节点，Delayi，j表示节点i与j之间相连链路的时延、Jitteri，j表示节点i与j之间相连链路的抖动，LossRatei，j表示节点i与j之间相连链路
的丢包率，α，β，γ为权重，且α+β+γ＝1。

[0134] 延迟的量纲为秒或者毫秒，抖动的量纲为秒或者毫秒，丢包率没有量纲，这三个因素不是同一个量纲级别，没有可比较性，因此，需要对这三个因素进行归一化处理，使其变
成无量纲可比较的数据。

[0135] (1)延迟：对延迟进行归一化计算如公式(7)所示：

[0136] Delayi，j＝(delayi，j‑delaymin)/(delaymax‑delaymin)    (7)

[0137] 其中，Delayi，j表示节点i与节点j之间归一化后的延迟值，delayi，j表示节点i与节点j之间的实际时延，在整个网络拓扑图中，delaymax表示所有链路中延迟的最大值，
delaymin表示所有链路中延迟的最小值。

[0138] (2)抖动：对抖动进行归一化计算如公式(8)所示：

[0139] Jitteri，j＝(jitteri，j‑jittermin)/(jittermax‑jittermin)    (8)

[0140] 其中，Jitteri，j表示节点i与节点j之间归一化后的抖动值，jitteri，j表示节点i与节点j之间的实际抖动，在整个网络拓扑图中，jittermax表示所有链路中抖动的最大值，
jittermin表示所有链路中抖动的最小值。

[0141] (3)丢包率：对丢包率进行归一化计算如公式(9)所示：

[0142] LossRatei，j＝(lossratei，j‑lossratemin)/(lossratemax‑lossratemin)   (9)

[0143] 其中，LossRatei，j表示节点i与节点j之间归一化后的丢包率值，lossratei，j表示节点i与节点j之间的实际丢包率，在整个网络拓扑图中，lossratemax表示所有链路中丢包
率的最大值，lossratemin表示所有链路中丢包率的最小值。

[0144] 2.2请求资源模型

[0145] 每一个用户需求可以用一个五元组表示，Uid是该用户的唯一标识，Udes表示最终目的，Ubw表示带宽，Ust表示开始时间，Uft表示结束时间。Flow表示数据
流类，存储数据流的相关信息，每个数据流(Fid，Fs，Fd，Fu，Fbytes，Ft， Fm，Fvp，Fep，T)，Fid用
来标识一个数据流，T为更新时间间隔，T的取值与网络状态相关，网络正常情况下，其值为
固定值(2s)，当网络中出现突发状况时，立即更新。

[0146] 2.3服务定制模型

[0147] 当用户在特定时间段内需要网络资源时，用户将资源请求发送给控制器。每个定制服务可以使用相互独立的物理资源，网络中可以同时存在多个定制服务，然后把用户网
络请求生成定制服务。

[0148] 将网络描述为有向图C＝(V，E)，其中V代表图中顶点的集合，用于描述网络中的Openflow交换机或主机，E代表网络中边的集合，描述连接各个网络设备的链路，每条边(i，
j)∈E，表示从节点i到节点j之间的链路，S代表发送端，D代表接收端，rsd表示路由，rij代表
路径。对于任何r∈rsd的路由可以定义为：

[0149] fc(r)＝∑(i，j)∈rcij                            (10)

[0150] fd(r)＝∑(i，j)∈rdij                            (11)

[0151] 其中，rsd表示路由，cij表示代价，dij代表时延，fc(r)表示总代价，fd(r)表示总时延，cij＝βgij+(1‑β)pij，β值可变，pij表示丢包率，gij表示带宽利用率，代价cij最终表示为：

[0152] cij＝βgij+(1‑β)pij    (12)

[0153] 2.4资源分配模型

[0154] 资源分配流的建立过程包括：首先将第一个发送的数据包发送给控制器进行处理，同时控制器需要每隔2s查询网络链路状态信息，为了实现基于SDN的服务定制网络资源
自适应分配方法，控制器需要进行流量监测以及收集网络资源状态信息等数据。收集控制
器与交换机以及交换机与交换机之间的链路信息。资源分配模块借助网络拓扑模块可以获
得网络拓扑，从请求资源模块中获得请求资源信息。基于SDN服务定制网络资源分配系统框
架如图5所示。

[0155] 3.服务定制机制

[0156] 3.1获取用户需求

[0157] 本专利将用户的需求描述为用户文档，在具体的执行过程中，系统不仅要对各种不同类型用户的实际需求进行有效的采集，并构建用户文档，还可以通过在建立连接之前
提交用户文档来减少控制开销，以保证网络资源利用效率的最大化。

[0158] 3.2用户需求分析

[0159] 在服务定制模块中，对所有可能影响用户体验的需求进行分析。根据不同的通信特征实现对用户请求的分类，然后对其进行深入地分析、整理和统计，进而有效获取各个不
同类型的通信需求。根据用户的实际需要，系统进行合理地配置，以保证提供完善的网络服
务。

[0160] 3.2服务定制资源

[0161] 在服务定制过程中，用户需要将需求等信息提交到服务定制模块的后台服务器，网络服务提供商需要提供与当前网络环境状态相关的信息到服务定制模块的后台服务器，
服务器根据其汇总的需求与环境信息，进行用户与网络服务提供商的供需匹配。在用户与
网络服务提供商匹配的过程中，应考虑的因素主要包括用户需求与网络服务提供商供给之
间的匹配，网络服务提供商所能提供的服务质量和网络环境的当前状态。最终能够保证网
络资源利用率的最大化。

[0162] 根据用户需求提供相应的资源分配方案，系统输入：服务期望的网络时间、网络位置，需要的设备数量、网络吞吐量和设备的期望速率等根据网络需求调用事先定义好的解
决方案模板提供定制化的网络资源分配。

[0163] 4.基于改进蚁群算法的资源分配机制

[0164] 基于改进蚁群算法的资源分配机制需要计算出最优路径进行数据传输，可以下达最为准确的指令来进行网络调配，大幅提升网络整体的效率。

[0165] 4.1蚁群算法

[0166] 参考蚁群算法，和我们的资源分配方案进行类比，在资源分配的整个过程中，只考虑资源本身，如同蚂蚁寻找食物，其中用户需求的源节点可以被看成蚂蚁的巢穴，数据包可
以被看成食物碎屑，资源提供节点可以被看成食物源。

[0167] 4.2资源分配算法

[0168] 网络可以用G＝(V，E)表示，其中V＝(v1，v2，v3，...vn)代表网络中的所有节点，E＝(e1，e2，e3，...em)表示两个节点之间的物理链路组成的集合。n和m分别表示节点和链路的
数量。 表示链路成本， 表示链路时延，C(p)表示链路总成本，D(p)表示链路总时延。

[0169]

[0170]

[0171] 在下列公式中，λ表示拉格朗日乘子，Cλ(p)表示成本代价和时延的聚合代价，*
Δdelay表示时延限制，p表示资源分配的最优路径，Pst表示源节点到目的节点的路径。

[0172] p*＝min{C(p)|D(p)≤Δdelay}，p∈Pst    (15)

[0173]

[0174]

[0175] 表示(vi，vj)的链路使用率，α表示链路使用率的权重。

[0176]

[0177] 4.3资源分配整体流程

[0178] 根据用户需求提供相应的资源分配方案，系统输入的服务期望的网络时间和网络位置，需要的设备数量、网络吞吐量以及设备的期望速率根据网络需求调用事先定义好的
解决方案模板，提供定制化的网络资源分配。

[0179] 请参阅图4所示的资源分配流程图，首先获取用户需求，然后对不同种类的业务需求进行区分，优化网络的性能。在服务定制模块中，对所有可能影响用户体验的需求进行分
析。根据不同的通信特征实现对用户请求的分类，然后对其进行深入地分析、整理和统计，
进而有效地获取各个不同类型通信的需求。在服务定制过程中，用户需要将需求信息提交
到服务定制模块的后台服务器，网络服务提供商需要提供当前网络的环境状态相关信息到
服务定制模块的后台服务器，服务器根据其汇总的需求与环境信息，进行用户与网络服务
提供商的供需匹配。

[0180] 根据用户需求提供相应的资源分配方案，系统输入的服务期望的网络时间以及网络位置，需要设备数量，网络吞吐量，设备的期望速率等根据网络需求调用事先定义好的解
决方案模板，提供定制化的网络资源分配。

[0181] 5.用例评价

[0182] 本专利在第二代中国教育和科研计算机网(CERNET2)上进行了测试实验。通过文本数据形成十种业务的需求用例，且不同类型的业务对基础的服务质量性能指标的需求各
不相同，且不同应用类型的指标各不相同。这十种应用的应用场景、应用类型、带宽要求各
有不同，应用的编号和名称如图6所示。

[0183] 5.1评价指标

[0184] 本专利采用了网络中普遍使用的三种性能评价指标，包括：丢包率、带宽资源利用率以及时间开销。

[0185] 此三个指标中丢包率和时间开销越小、带宽利用率越大，性能越好。

[0186] 5.2评价结果

[0187] 本专利在第二代中国教育和科研计算机网(CERNET2)上，选用传统的网络资源分配方案即Dijkstra算法作为基准算法(用D机制表示)，与我们提出的基于SDN的服务定制网
络资源自适应分配方法(用S机制表示)进行性能对比。分别从丢包率、带宽利用率和时间开
销三个方面，进行相应指标的性能对比，测试结果请参阅图7、图8、图9方法测试结果。

[0188] 本发明在丢包率、带宽利用率和时间开销方面都较优于目前传统的网络资源分配方案，说明了本发明在综合性能上的有益效果。