CN108880895B - 基于用户流传输开销优化的sdn联合路由选择及网络功能部署方法 - Google Patents

Abstract

本发明涉及一种基于用户流传输开销优化的SDN联合路由选择及网络功能部署方法，属于移动通信技术领域。该方法包括：S1：建模用户流业务需求特性；S2：建模用户流链路选择及网络功能部署变量；S3：建模用户流传输开销；S4：建模用户流传输所需总时延；S5：建模用户流传输所需总能耗；S6：建模路由选择及网络功能部署限制条件；S7：基于用户流传输开销最小化，确定联合路由选择及网络功能部署策略。本发明能够保证用户流的有效传输和服务质量，满足用户流网络应用的需求，通过优化确定路由选择及网络功能部署策略实现用户流传输开销最小化。

Description

基于用户流传输开销优化的SDN联合路由选择及网络功能部 署方法

技术领域

本发明属于移动通信技术领域，涉及一种基于用户流传输开销优化的SDN联合路由选择及网络功能部署方法。

背景技术

软件定义网络(Software Defined Network,SDN)是由斯坦福大学于2009提出的一种新兴的基于软件的网络架构与技术，其主要特点是控制平面与数据平面分离，逻辑上集中化控制网络以及通过软件编程实现灵活高效的网络管理与运行维护。

SDN中，控制平面的控制器可获取网络全局视图，负责集中化的管理和控制，数据平面的转发设备(如交换机)执行从控制器侧接收的网络策略。SDN网络架构可有效隔离流量、区分服务链及便于服务质量(Quality of Service,QoS)管理，从而能够较好地解决传统移动网络成本高、不够灵活、QoS难以有效管理等问题，然而，SDN架构的集中式网络控制、控制与数据平面分离、资源切片等特性给网络管理机制特别是路由选择机制带来新的问题及挑战。

随着用户多样性服务需求的快速增长，传统的专用硬件设备成本高、操作复杂性高以及不够灵活等特性对网络功能的部署提出了要求。为了有助于灵活的、成本有效的网络功能部署，研究人员提出了网络功能虚拟化(Network Function Virtualization，NFV)技术，以实现基于软件的网络功能的灵活配置。SDN与NFV技术的整合有望提供灵活的网络功能实现和有效的流量管理，然而，多样化SDN网络应用及复杂NFV功能部署对网络管理技术，特别是数据流路由传输及网络功能部署问题提出困难及挑战。

文献[M.Huang,W.Liang,Z.Xu and S.Guo,Efficient algorithms forthroughput maximization in software-defined networks with consolidatedmiddleboxes,IEEE Transactions on Network and Service Management,2017]提出了一种启发式算法实现网络性能与网络功能部署策略的运行时间之间的权衡，以最大化网络吞吐量，但该算法未考虑最佳的路由选择策略。文献[T.W.Kuo,B.H.Liou,K.C.J.Lin andM.J.Tsai,Deploying chains of virtual network functions:On the relationbetween link and server usage,Communications(INFOCOM),2016]考虑沿数据流传输路径调用虚拟网络功能，提出联合虚拟网络功能部署及路径选择的算法以实现网络吞吐量最大化，但该算法未考虑用户流的有效传输以及有效的路由选择策略设计。

综上所述，SDN的网络环境中如何综合考虑用户的业务需求、链路容量及QoS保障等特性，实现联合路由选择及网络功能部署策略，从而降低网络时延和能耗、提高传输安全性能以及实现用户流有效传输成为亟待解决的问题。

发明内容

有鉴于此，本发明的目的在于提供一种基于用户流传输开销优化的SDN联合路由选择及网络功能部署方法，实现联合路由选择及网络功能部署策略。

为达到上述目的，本发明提供如下技术方案：

一种基于用户流传输开销优化的SDN联合路由选择及网络功能部署方法，在该方法中，针对一个控制器和多个交换机组成的软件定义网络(Software-DefinedNetworking，SDN)场景，设每个交换机均附着一个网络功能虚拟化(Network FunctionVirtualization，NFV)服务器，支持以软件实现特定网络功能，在满足用户流业务需求特性条件下，建模用户流传输开销为优化目标，实现联合路由选择及网络功能部署策略；该方法具体包括以下步骤：

S1：建模用户流业务需求特性；

S2：建模用户流链路选择及网络功能部署变量；

S3：建模用户流传输开销；

S4：建模用户流传输所需总时延；

S5：建模用户流传输所需总能耗；

S6：建模路由选择及网络功能部署限制条件；

S7：基于用户流传输开销最小化，确定联合路由选择及网络功能部署策略。

进一步，所述步骤S1具体包括：令用户流集合F＝{f₁,f₂,...,f_L}，其中，f_l表示第l个用户流，1≤l≤L，L表示用户流数目；T_l和

分别表示f_l的流量需求和最小速率需求；设各用户流自源点至目的点传输时需要经过一系列网络功能处理，令Ψ表示网络中需要部署的功能集合，Ψ_l表示f_l需求的网络功能集合，

其中，ψ_m,l表示 f_l所需的第m个网络功能，1≤m≤M_l，M_l为f_l所需的网络功能数目，令ψ_m,l所需计算能力为F_m,l；设用户流经不同网络功能处理将改变用户流传输流量大小，令δ_m,l∈(-1,1]为f_l经过功能ψ_m,l处理流量变化因子。

进一步，所述步骤S2具体包括：令V_i表示第i个交换机，1≤i≤N，其中，N为交换机的数目；令Z_i,j表示交换机V_i和交换机V_j之间的链路，1≤i,j≤N，i≠j；令

表示f_l的链路选择标识，

表示f_l的第k跳选择链路Z_i,j进行数据传输，否则，

K_l为f_l传输路径的总跳数；令

表示f_l的网络功能部署标识，

表示f_l的第k跳选择交换机V_i部署网络功能ψ_m,l，否则，

进一步，所述步骤S3具体包括：所述用户流传输开销为所有用户流的开销之和，即U＝D^tot+λE^tot，其中，D^tot和E^tot分别表示所有用户流传输的总时延和总能耗，λ为权重因子。

进一步，所述步骤S4具体包括：所述用户流传输所需总时延为所有用户流传输的时延之和，即

其中，D_l表示f_l传输的时延，建模为

其中，

表示f_l在链路Z_i,j上的传输时延，

表示f_l在交换机V_i处的排队时延，

表示f_l在交换机V_i处执行网络功能ψ_m,l所需处理时延。

进一步，所述f_l在链路Z_i,j上的传输时延建模为

其中，

表示f_l的第k跳离开交换机V_i后的流量大小，其计算公式为

表示f_l所分配链路速率资源标识，R_i,j表示链路Z_i,j的传输速率；

所述f_l在交换机V_i处的排队时延的计算方法为：设SDN交换机处的用户流处理遵循M/M/1排队模型，根据公式

计算f_l在交换机V_i处的排队时延，其中，μ_i和λ_i分别表示交换机V_i处的业务服务率和到达率，β_i,l∈(0,1]表示交换机V_i为f_l所分配处理资源标识；

所述f_l在交换机V_i处执行网络功能ψ_m,l所需处理时延的计算方法为：

其中，η_i,m,l∈(0,1]表示交换机V_i处附着的NFV服务器为f_l所需网络功能ψ_m,l分配的计算资源标识，C_m,l表示ψ_m,l所需求的计算资源量，F_i ^max表示交换机V_i附着的服务器的计算能力。

进一步，所述步骤S5具体包括：所述用户流传输所需总能耗为所有用户流传输的能耗之和，即

其中，E_l表示f_l传输的能耗，建模为

其中，E_i,j表示在链路Z_i,j上传输单位比特流的能耗，

表示f_l所需的网络功能ψ_m,l在交换机V_i处执行的能耗。

进一步，所述链路Z_i,j上传输单位比特流的能耗的计算公式为：

其中，

表示交换机V_i出端口存储且发送单位比特流的能耗，计算公式为

其中，

表示交换机V_i出端口达到最大传输速率时端口的能耗，

表示交换机V_i出端口速率，

表示交换机V_i端口速率转换为能耗的权值函数， p(r)＝0.00062r+0.38；

表示交换机V_j入端口接收且存储单位比特流的能耗，计算公式为

其中，

表示交换机V_i入端口达到最大传输速率时端口的能耗，

表示交换机V_i入端口速率；

表示交换机V_j处理单位比特流的能耗，计算公式为

其中，

表示交换机V_j匹配单位比特数据流的能耗，

表示交换机V_j匹配单位比特数据流结束后采取动作的能耗，φ_j表示交换机V_j的存储容量；

所述f_l所需的网络功能ψ_m,l在交换机V_i处执行的能耗的计算公式为

其中，

表示交换机V_i附着的服务器的基础能耗，

表示交换机V_i附着的服务器的峰值能耗，F_i ^max为交换机V_i附着的服务器的计算能力，F_m,l表示ψ_m,l所需计算能力。

进一步，所述步骤S6具体包括：

所述路由选择限制条件建模为：若V_i＝S_l，则

若V_j＝D_l，则

V_j≠{S_l,D_l}，其中，S_l和D_l分别为f_l的源交换机和目的交换机；

所述容量限制条件建模为：

所述速率限制条件建模为：

若α_i,j,l＞0，则

所述网络功能部署限制条件建模为：

所述资源分配限制条件建模为：

进一步，所述步骤S7具体包括：在满足路由选择及网络功能部署限制条件下，以用户流传输开销最小化为目标，优化确定路由选择及网络功能部署策略，即

其中，

分别表示f_l传输时的最优路由选择策略，

表示f_l传输时交换机处的最优网络功能部署策略，

表示f_l在链路Z_i,j的最优速率资源分配策略，

表示f_l在交换机V_i处的最优处理资源分配策略，

表示交换机V_i附着的服务器处的最优计算资源分配策略， U(·)表示用户流传输开销。

本发明的有益效果在于：本发明能够保证用户流的有效传输和服务质量，满足用户流网络应用的需求，达到路由选择及网络功能部署最优，实现用户流传输开销最小化。

附图说明

为了使本发明的目的、技术方案和有益效果更加清楚，本发明提供如下附图进行说明：

图1为支持网络功能部署的网络场景示意图；

图2为本发明所述方法的流程示意图。

具体实施方式

下面将结合附图，对本发明的优选实施例进行详细的描述。

图1为支持网络功能部署的网络场景示意图，如图1所示，该网络中存在一个控制器和多个交换机，每个交换机均可附着一个NFV服务器，支持以软件实现的特定网络功能。令用户流集合为F，F＝{f₁,f₂,...,f_L}，其中，f_l表示第l个用户流，1≤l≤L，L表示用户流数目，且令f_l的源交换机和目的交换机分别为S_l和D_l。根据用户流的网络应用需求，每个用户流进行端到端传输时，需要经过一系列网络功能处理，且不同的网络功能处理将改变用户流传输流量大小。建模用户流传输开销为所有用户流传输的开销之和，基于用户流传输开销最小化实现联合路由选择及网络功能部署最优策略。

图2为本发明所述方法的流程示意图，如图2所示，本发明所述方法具体包括以下步骤：

1)建模用户流业务需求特性；

建模用户流业务需求特性，具体为：令用户流集合F＝{f₁,f₂,...,f_L}，其中，f_l表示第l个用户流，1≤l≤L，L表示用户流数目；T_l和

分别表示f_l的流量需求和最小速率需求；设各用户流自源点至目的点传输时需要经过一系列网络功能处理，令Ψ表示网络中需要部署的功能集合，Ψ_l表示f_l需求的网络功能集合，

其中，ψ_m,l表示f_l所需的第m个网络功能，1≤m≤M_l，M_l为f_l所需的网络功能数目，令ψ_m,l所需计算能力为F_m,l；设用户流经不同网络功能处理将改变用户流传输流量大小，令δ_m,l∈(-1,1]为f_l经过功能ψ_m,l处理流量变化因子。

2)建模用户流链路选择及网络功能部署变量；

建模用户流链路选择及网络功能部署变量，具体为：令V_i表示第i个交换机，1≤i≤N，其中，N为交换机的数目；令Z_i,j表示交换机V_i和交换机V_j之间的链路，1≤i,j≤N，i≠j；令

表示f_l的链路选择标识，

表示f_l的第k跳选择链路Z_i,j进行数据传输，否则，

K_l为f_l传输路径的总跳数；令

表示f_l的网络功能部署标识，

表示f_l的第k跳选择交换机V_i部署网络功能ψ_m,l，否则，

3)建模用户流传输开销；

建模用户流传输开销为所有用户流的开销之和，即U＝D^tot+λE^tot，其中，D^tot和E^tot分别表示所有用户流传输的总时延和总能耗，λ为权重因子。

4)建模用户流传输所需总时延；

建模用户流传输所需总时延为所有用户流传输的时延之和，即

其中，D_l表示f_l传输的时延，建模为

其中，

表示f_l在链路Z_i,j上的传输时延，

表示f_l在交换机V_i处的排队时延，

表示f_l在交换机V_i处执行网络功能ψ_m,l所需处理时延。根据公式

计算f_l在链路Z_i,j上的传输时延，其中，

表示f_l的第k跳离开交换机V_i后的流量大小，其计算公式为

表示f_l所分配链路速率资源标识，R_i,j表示链路Z_i,j的传输速率。假设SDN交换机处的用户流处理遵循M/M/1排队模型，根据公式

计算f_l在交换机V_i处的排队时延，其中，μ_i和λ_i分别表示交换机V_i处的业务服务率和到达率，β_i,l∈(0,1]表示交换机V_i为f_l所分配处理资源标识。f_l在交换机V_i处执行网络功能ψ_m,l所需处理时延的计算方法为

其中，η_i,m,l∈(0,1]表示交换机V_i处附着的NFV服务器为f_l所需网络功能ψ_m,l分配的计算资源标识，C_m,l表示ψ_m,l所需求的计算资源量，F_i ^max表示交换机V_i附着的服务器的计算能力。

5)建模用户流传输所需总能耗；

建模用户流传输所需总能耗为所有用户流传输的能耗之和，即

其中，E_l表示f_l传输的能耗，建模为

其中，E_i,j表示在链路Z_i,j上传输单位比特流的能耗，

表示f_l所需的网络功能ψ_m,l在交换机V_i处执行的能耗。根据公式

计算链路Z_i,j上传输单位比特流的能耗，其中

表示交换机V_i出端口存储且发送单位比特流的能耗，计算公式为

其中，

表示交换机V_i出端口达到最大传输速率时端口的能耗，

表示交换机V_i出端口速率，

表示交换机V_i端口速率转换为能耗的权值函数， p(r)＝0.00062r+0.38；

表示交换机V_j入端口接收且存储单位比特流的能耗，计算公式为

其中，

表示交换机V_i入端口达到最大传输速率时端口的能耗，

表示交换机V_i入端口速率；

表示交换机V_j处理单位比特流的能耗，计算公式为

其中，

表示交换机V_j匹配单位比特数据流的能耗，

表示交换机V_j匹配单位比特数据流结束后采取动作的能耗，φ_j表示交换机V_j的存储容量。f_l所需的网络功能ψ_m,l在交换机V_i处执行的能耗的计算公式为

其中，

表示交换机V_i附着的服务器的基础能耗，

表示交换机V_i附着的服务器的峰值能耗，F_i ^max为交换机V_i附着的服务器的计算能力，F_m,l表示ψ_m,l所需计算能力。

6)建模路由选择及网络功能部署限制条件；

建模路由选择及网络功能部署限制条件，其中，路由选择限制条件建模为：若V_i＝S_l，则

若V_j＝D_l，则

V_j≠{S_l,D_l}，其中，S_l和D_l分别为f_l的源交换机和目的交换机；

所述容量限制条件建模为：

所述速率限制条件建模为：

若α_i,j,l＞0，则

所述网络功能部署限制条件建模为：

所述资源分配限制条件建模为：

7)基于用户流传输开销最小化，确定联合路由选择及网络功能部署策略；

基于用户流传输开销最小化确定路由选择及网络功能部署策略：在满足路由选择及网络功能部署限制条件下，以用户流传输开销最小化为目标，优化确定路由选择及网络功能部署策略，即

其中，

分别表示f_l传输时的最优路由选择策略，

表示f_l传输时交换机处的最优网络功能部署策略，

表示f_l在链路Z_i,j的最优速率资源分配策略，

表示f_l在交换机V_i处的最优处理资源分配策略，

表示交换机V_i附着的服务器处的最优计算资源分配策略， U(·)表示用户流传输开销。

最后说明的是，以上优选实施例仅用以说明本发明的技术方案而非限制，尽管通过上述优选实施例已经对本发明进行了详细的描述，但本领域技术人员应当理解，可以在形式上和细节上对其作出各种各样的改变，而不偏离本发明权利要求书所限定的范围。

Claims (1)

1.一种基于用户流传输开销优化的SDN联合路由选择及网络功能部署方法，其特征在于，该方法具体包括以下步骤：

S1：建模用户流业务需求特性，具体包括：令用户流集合F＝{f₁,f₂,...,f_L}，其中，f_l表示第l个用户流，1≤l≤L，L表示用户流数目；T_l和

分别表示f_l的流量需求和最小速率需求；设各用户流自源点至目的点传输时需要经过一系列网络功能处理，令Ψ表示网络中需要部署的功能集合，Ψ_l表示f_l需求的网络功能集合，

其中，ψ_m,l表示f_l所需的第m个网络功能，1≤m≤M_l，M_l为f_l所需的网络功能数目，令ψ_m,l所需计算能力为F_m,l；设用户流经不同网络功能处理将改变用户流传输流量大小，令δ_m,l∈(-1,1]为f_l经过功能ψ_m,l处理流量变化因子；

S2：建模用户流链路选择及网络功能部署变量，具体包括：令V_i表示第i个交换机，1≤i≤N，其中，N为交换机的数目；令Z_i,j表示交换机V_i和交换机V_j之间的链路，1≤i,j≤N，i≠j；令

表示f_l的链路选择标识，

表示f_l的第k跳选择链路Z_i,j进行数据传输，否则，

1≤k≤K_l，K_l为f_l传输路径的总跳数；令

表示f_l的网络功能部署标识，

表示f_l的第k跳选择交换机V_i部署网络功能ψ_m,l，否则，

S3：建模用户流传输开销，具体包括：所述用户流传输开销为所有用户流的开销之和，即U＝D^tot+λE^tot，其中，D^tot和E^tot分别表示所有用户流传输的总时延和总能耗，λ为权重因子；

S4：建模用户流传输所需总时延，具体包括：所述用户流传输所需总时延为所有用户流传输的时延之和，即

其中，D_l表示f_l传输的时延，建模为

其中，

表示f_l在链路Z_i,j上的传输时延，

表示f_l在交换机V_i处的排队时延，

表示f_l在交换机V_i处执行网络功能ψ_m,l所需处理时延；

所述f_l在链路Z_i,j上的传输时延建模为

α_i,j,l＞0，其中，

表示f_l的第k跳离开交换机V_i后的流量大小，其计算公式为

α_i,j,l∈(0,1]表示f_l所分配链路速率资源标识，R_i,j表示链路Z_i,j的传输速率；

所述f_l在交换机V_i处的排队时延的计算方法为：设SDN交换机处的用户流处理遵循M/M/1排队模型，根据公式

β_i,l＞0计算f_l在交换机V_i处的排队时延，其中，μ_i和λ_i分别表示交换机V_i处的业务服务率和到达率，β_i,l∈(0,1]表示交换机V_i为f_l所分配处理资源标识；

所述f_l在交换机V_i处执行网络功能ψ_m,l所需处理时延的计算方法为：

η_i,m,l＞0，其中，η_i,m,l∈(0,1]表示交换机V_i处附着的NFV服务器为f_l所需网络功能ψ_m,l分配的计算资源标识，C_m,l表示ψ_m,l所需求的计算资源量，F_i ^max表示交换机V_i附着的服务器的计算能力；

S5：建模用户流传输所需总能耗，具体包括：所述用户流传输所需总能耗为所有用户流传输的能耗之和，即

其中，E_l表示f_l传输的能耗，建模为

其中，E_i,j表示在链路Z_i,j上传输单位比特流的能耗，

表示f_l所需的网络功能ψ_m,l在交换机V_i处执行的能耗；

所述链路Z_i,j上传输单位比特流的能耗的计算公式为：

其中，

表示交换机V_i出端口存储且发送单位比特流的能耗，计算公式为

其中，

表示交换机V_i出端口达到最大传输速率时端口的能耗，

表示交换机V_i出端口速率，

表示交换机V_i端口速率转换为能耗的权值函数；

表示交换机V_j入端口接收且存储单位比特流的能耗，计算公式为

其中，

表示交换机V_i入端口达到最大传输速率时端口的能耗，

表示交换机V_i入端口速率；

表示交换机V_j处理单位比特流的能耗，计算公式为

其中，

表示交换机V_j匹配单位比特数据流的能耗，

表示交换机V_j匹配单位比特数据流结束后采取动作的能耗，φ_j表示交换机V_j的存储容量；

所述f_l所需的网络功能ψ_m,l在交换机V_i处执行的能耗的计算公式为

其中，

表示交换机V_i附着的服务器的基础能耗，

表示交换机V_i附着的服务器的峰值能耗，F_i ^max表示交换机V_i附着的服务器的计算能力，F_m,l表示ψ_m,l所需计算能力；

S6：建模路由选择及网络功能部署限制条件；具体包括：

所述路由选择限制条件建模为：若V_i＝S_l，则

若V_j＝D_l，则

其中，S_l和D_l分别为f_l的源交换机和目的交换机；

容量限制条件建模为：

速率限制条件建模为：

若α_i,j,l＞0，则

所述网络功能部署限制条件建模为：

资源分配限制条件建模为：

S7：在满足路由选择及网络功能部署限制条件下，以用户流传输开销最小化为目标，优化确定路由选择及网络功能部署策略，即

其中，

分别表示f_l传输时的最优路由选择策略，

表示f_l传输时交换机处的最优网络功能部署策略，

表示f_l在链路Z_i,j的最优速率资源分配策略，

表示f_l在交换机V_i处的最优处理资源分配策略，

表示交换机V_i附着的服务器处的最优计算资源分配策略，U(·)表示用户流传输开销。

Images