作者：郑晓敏
1 引言
软件定义网络(software defined networking，SDN)技术具有控制与传输分离、集中式控制和软件可定义的特征，能够克服IP承载网结构僵化问题，便于在IP承载网中快速开发并部署新型业务，并能为不同业务定义网络控制与管理策略，应用SDN技术的软件定义承载网(carrier-SDN)成为目前国内外研究的重点。carrier-SDN中针对不同业务定义的网络控制与管理策略之间不能相互冲突，需应用网络虚拟化技术实例化相互隔离的虚拟网络，在虚拟网络上部署新业务，并面向业务个性化需求开发控制与管理策略[31，应用网络虚拟化技术实现虚拟网络资源分配的虚拟网络映射算法成为carrier-SDN研究的重点。
虚拟网络映射算法将虚拟节点和虚拟链路分别映射在carrier-SDN的物理节点和由物理链路连接构成的物理路径上，在物理节点和物理路径上预留计算资源和带宽资源，实例化虚拟网络。由于carrier-SDN中上层IP交换网络承载在下层光传输网络上，因此首先需建立carrier-SDN的多层网络模型。针对虚拟网络映射算法，提出以占用网络资源最小为优化目标，当网络负载较小时具有较好性能，但当负载增加时，物理网络中会出现瓶颈的节点和链路，造成算法性能急剧下降。因此，以负载均衡为优化目标的映射算法能够在网络负载较高时获得较好性能。参考文献中的LB-ILP-VNE算法提出应用整数线性规划解决负载均衡虚拟网络映射问题，虽然能够获得确定的最优解，但是算法复杂度较高。参考文献中的LB-G-VNE
算法应用贪婪算法求解，虽然算法运行时间短，但是所求解会随着网络状态变化，影响算法性能。考虑到粒子群优化算法能够在解空间多个域中同时展开搜索，具有简单、高效的特征，参考文献中的LB-DPSO-VNE算法提出应用粒子群算法，虽然算法性能较好，但是大量的集合运算会造成算法运行时间过长。
基于此，本文提出carrier-SDN中基于负载均衡的虚拟网络资源分配算法。首先，建立carrier-SDN多层网络模型，反映carrier-SDN上层IP交换网络与下层光传输网络间的映射关系：其次，根据映射算法的特点，提出一种粒子群算法的二值化方法．保证每个粒子中1的个数始终一致，反映虚拟网络请求中虚拟节点个数保持不变的特征；最后，以负载均衡为优化目标，应用二值粒子群算法求解虚拟节点映射的解，应用Dijkstra算法构建carrier-SDN路径集合，确定承载虚拟链路的传输路径，实例化虚拟网络请求。
2 carrier-SDN多层网络模型
carrier-SDN包含IP交换网和光传输网络，IP交换网承载在光传输网络中，虚拟网络请求被接纳在IP交换网上，且用户连接到IP交换网中，carrier-SDN被抽象为多层网络模型，如图1所示。
carrier-SDN底层网络记为O_substrate，上层网络记为P_suibstrate，底层网络中包含的节点和链路分别记为O_node和O_tin,k．上层网络中包含的节点和链路分别记为P_n,ode和P_link。
上层网络中相邻交换机之间的路径包括多条传输路径，是一组传输路径的集合，表示为{P_lin,k(iJ)}，其中，ij为链路集合中所有链路的端点，P_lin,k表示{P_lin,k(i,j))集合中的任意一条传输链路。由于上层中的链路承载在光传输网络中由光传输链路相互连接构成的光传输路径上，将光传输路径表示为
由于下层光传输网络每次为在其上建立的路径分配一个波长，此时上层IP交换网络的链路带宽也是一个波长，即：Vi,j，k，Bdw(P_lin,k :)=wcwele，z,gth，上层交换机i、j之间建立了一条传输路径。如果任意P_linkkij上的剩余资源较多，能够满足虚拟网络请求的带宽，则在上层网络中为虚拟链路计算一条传输路径，将虚拟链路承载在这条传输路径上，即:
3 carrier-SDN中基于负载均衡的虚拟网络资源分配算法
3.1 carrier-SDN资源分配机制
carrier-SDN资源分配机制流程描述如下。
步骤1 当carrier-SDN上没有承载任何虚拟网络请求时，其IP交换网络中没有传输链路。
步骤2 当虚拟网络请求到达carrier-SDN时，应用虚拟网络映射算法确定承载虚拟节点的IP交换网络中交换机的位置，并为虚拟节点分配计算资源。
步骤3根据虚拟节点映射方案，在carrier-SDN的IP交换网中计算连接交换机的路径。
·如果在IP交换网上能够计算出传输路径，则将虚拟 链路承载在P-path上。
·如果IP交换网上没有满足虚拟链路带宽请求的路径，在下层光传输网络中计算一条光传输路径，并在IP交换网中建立直连链路，为该直连路径分配一个波长作为传输带宽,O-path中包含的O_pathp上相应地减去一个波长，再将虚拟链路承载在直连链路上。
步骤4当虚拟网络请求离开网络时，释放虚拟节点、虚拟链路占用的计算资源和带宽资源。
步骤5如果carrier-SDN上层IP交换网中任何一条传输链路没有承载虚拟链路，则拆除分组交换网中的链路，释放承载该IP交换网链路的波长到光传输网络中对应的路径上。
3.2虚拟网络映射算法建模
虚拟网络映射算法需要满足资源约束、二值约束条件。资源约束是服务器上的剩余计算资源需满足虚拟节点请求的计算资源，carrier-SDN传输路径链路上的剩余带宽资源需满足虚拟链路请求的带宽资源。
其中，u和(u，u)指虚拟节点标号和虚拟链路，Nv和Lv指虚拟网络请求的虚拟节点集合和虚拟链路集合。i和(i,j)指carrier-SDN中的节点标号和传输链路，Ns和Ls指carrier-SDN上层IP交换网的交换机集合和链路集合。虚拟节点u映射在连接到carrier-SDN的服务器i上时xui为1，否则为O。com(u)指虚拟节点M请求的计算资源，com(i)指服务器i上的剩余计算资源。虚拟链路(u,v)映射在carrier-SDN传输链路(i,j)上时fwij为1，否则为O。bw(u，v)指虚拟链路(u，v)请求的带宽资源，bw(i,j)指传输链路(i,j)的剩余带宽资源。
二值约束：虚拟节点只能映射在服务器上；虚拟链路只能映射在物理链路上；同一个虚拟网络中的虚拟节点不能同时映射在同一个服务器上；一个虚拟节点只能映射在一个服务器上。计算式表示如下：
3.3负载均衡虚拟网络映射算法
3.3.1目标函数
基于负载均衡的虚拟网络映射算法的目标函数用carrier-SDN上连接的服务器剩余计算资源和carrier-SDN链路剩余带宽资源的最小标准方差表示二其中.SN表示服务器总个数，N表示链路总个数。
3.3.2应用二值粒子群优化的负载均衡虚拟网络映射算法
本文算法将虚拟网络映射问题分解为虚拟节点映射和虚拟链路映射，应用二值粒子群优化算法求解虚拟节点映射方案，再在应用Dijkstra算法构建的路径集合Ps中选择carrier-SDN路径，承载虚拟链路。
(1)应用二值粒子群优化的负载均衡虚拟节点映射算法建模
粒子群算法中，每个粒子为一个向量Xk，表示一个可能的最优解，在求解虚拟节点映射方案时，xk,ui表示第k个解中，将虚拟节点u映射到服务器上，其适应度函数定义为服务器剩余计算资源的标准方差。
此时，粒子为VNxSN维，粒子总数为K个，ptk,ui为粒子进化过程中的最优位置,pg,。为所有粒子进化过程中的最优位置，
为粒子的速度，每个粒子按照如下计算式进化并更新位置。
其中，k为自然数，且1≤k≤K;w为惯性参数，取实数；CI、C2为加速因子，取实数；r1、r2为服从(0，1)均匀分布的随机数；wmax、wmin为惯性参数的最大值和最小值；iter为算法当前迭代次数。
Xk,ui的二值化方法如下。
初始化：u=l，i=1；对所有u、i，计算：
(2)应用二值粒子群优化的虚拟节点映射算法虚拟节点映射算法的详细流程描述如下。
步骤1 设定粒子数为50，最大迭代次数为500。
步骤2初始化粒子的初始位置{xok,ui}和
黝初始速度，以适应度函数计算本地最优粒子{pOk,ui）和全局最优粒子{pOg,ui}。
步骤3在粒子进化的第t代，基于式(9)刷新粒子速度utk,ui，并应用粒子二值化方法，确定粒子位置X。根据适应度函数计算本地最优粒子和全局最优粒子，并令t=t+1。
步骤4如果t<迭代次数上限ite rmax，转至步骤3，否则转至步骤5。
步骤5基于负载均衡的虚拟节点映射算法的解为ptg,ui集合。
(3)虚拟链路映射
在虚拟节点映射方案确定后，在承载虚拟节点的交换机对之间，以虚拟链路请求带宽资源为约束条件，应用Dijkstra算法构建传输路径集合，以carrier-SDN链路的剩余带宽资源的标准方差最小为目标，选取传输路径，并将虚拟链路映射在carrier-SDN上。
在构建carrier-SDN路径时，应用基于负载均衡的Dijkstra算法，计算传输路径集合Ps，Ps={P_path。
步骤1 定义carrier-SDN中网络节点之间有连接链路时，节点之间的距离，否则定义。
属于集合P的网络节点i，使得{P）={p}U{i}。如果{P}中包含了carrier-SDN中所有网络节点，停止遍历，否则转至步骤4。
步骤4对有所有不属于{P）的网络节点j，定义Dj=min{Dj，dji,+Di}，更新Dj后返回步骤3。
记录计算所得的任意服务器之间的路径，作为carrier-SDN路径集合Ps中的元素。
如果carrier-SDN传输路径集合构建失败，则虚拟链路映射失败，对应的虚拟网络请求被阻塞。当且仅当虚拟链路映射成功后，为虚拟节点和虚拟链路分配请求的计算资源和带宽资源。
4 仿真与性能分析
4.1 仿真环境
设定carrier-SDN底层光传输网包括100个交换节点，节点间的连接概率为0.1。相连的交换节点间配置32根光纤，每个光纤包含16个波长，每波长包括5 Gbit/s传输带宽。上层分组交换网包含100个交换节点，与光传输网的交换节点对应。配置100个与carrier-SDN连接的服务器，与分组交换网的交换节点一一相连，每个服务器的计算资源总量设为2 500。虚拟网络请求的虚拟节点数和虚拟链路跳数服从(1，10)的均匀分布，节点和链路分别请求的计算和带宽资源皆服从均值为500、方差为0.5的正态分布，带宽资源单位为Mbit/s。设定虚拟网络请求间隔时间服从参数为1的泊松分布，通过修改成功映射的虚拟网络请求持续时间服从的参数，模拟网络负载。针对每一个确定的网络负载，模拟产生10 000个虚拟网络请求。
仿真过程中，将所提算法记为LB-PSO-VNE，并与参考文献中的算法进行比较，从虚拟网络负载均衡、请求接受率、收益代价比、网络收益几个方面进行对比分析。
4.2性能分析
图2为LB-PSO-VNE算法与对比算法关于负载均衡的对比曲线。
从图2可以看出，LB-PSO-VNE算法中carrier-SDN链路带宽剩余资源的标准方差和连接到carrier-SDN的服务器的剩余计算资源的标准方差比其他对比算法更小，这是因为本文算法能够在虚拟网络映射的解空间中获得更优解，保证链路剩余带宽和服务器剩余计算资源分布得更均匀。由于carrier-SDN中的链路条数远远大于服务器的个数，在构建carrier-SDN路径集合时，一些链路并不能被充分利用，使得各算法对应的链路剩余带宽的标准方差大于服务器上剩余计算资源的标准方差。
图3为算法关于虚拟网络请求接受率的对比曲线。虚拟网络请求接受率定义为成功映射的虚拟网络个数与虚拟网络请求总数的比值。
从图3可以看出，在负载确定的条件下，本文算法能够保证carrier-SDN中的带宽资源和服务器上的计算资源分布更均匀，虚拟网络的请求接受率更高。使用粒子群算法获得虚拟节点映射的全局最优解，剩余计算资源分布更均匀，并采用链路剩余带宽最大来构建carrier-SDN路径，剩余带宽资源分布更为均衡。当网络负载增加时，可用资源减少，无法满足虚拟网络请求的概率增加，请求接受率下降。
图4为算法关于收益代价比的对比曲线。收益代价比定义为被成功映射的虚拟网络请求资源总量与carrier-SDN为映射的虚拟网络分配的网络资源总量的比值。
从图4可以看出．LB-PSO-VNE算法为了使连接到carrier-SDN的服务器上的剩余资源分布得更加均匀，虚拟节点映射将较为分散，使得连接虚拟节点的虚拟链路计算的物理路径平均跳数反而较大，且该算法会使链路剩余带宽和服务器剩余计算资源的分布更为均匀，最终使得其收益代价比较小。
图5所示为算法关于网络收益的对比曲线。网络收益定义为成功映射在carrier-SDN上的虚拟网络分配的网络资源总和。因计算资源与带宽资源量纲不同，故为二者设定不同的加权系数a和β。
从图5可以看出，随着网络负载的增加，网络收益递增。当网络负载大于0.8时，carrier-SDN中出现节点和链路碎片，请求接受率下降，网络收益增速下降。在相同网络负载下，本文算法的虚拟网络请求接受率较高，对应网络收益更高。由于carrier-SDN链路条数远大于服务器个数，且承载虚拟链路的物理路径由多条链路互联组成，使得带宽资源对网络收益影响较大，更大的带宽资源权重将获得更高网络收益。
5 结束语
本文提出carrier-SDN中基于负载均衡的虚拟网络资源分配算法。首先，建立carrier-SDN多层网络模型；其次，根据carrier-SDN上层IP交换网络与下层光传输网络之间的映射关系建立资源分配机制，并建立算法模型；最后，详细描述了负载均衡虚拟网络映射算法。算法中，首先定义了负载均衡的优化目标；其次，应用二值粒子群优化算法求解虚拟节点映射方案；最后，以剩余带宽最大为约束，应用负载均衡Dijkstra算法建立备选的传输路径集合，并选择合适路径承载虚拟链路。仿真结果表明，该算法在网络负载较高时，能实现较佳的网络负载均衡，具有较好的虚拟网络请求接受率和网络收益，运行效率较高。
6摘要：
在具有集中式控制特点的carrier-SDN（软件定义承载网）中应用网络虚拟化技术为虚拟网络分配资源，实现承载网资源分配是解决承载网结构僵化的重要途径。提出camer-SDN中基于负载均衡的虚拟网络资源分配算法。首先，建立camer-SDN多层模型；其次，根据虚拟网络映射算法的特点，二值化粒子群优化算法；最后，以负载均衡为优化目标，求解虚拟网络映射问题。仿真结果表明，与已有方法相比，所提算法在虚拟网络负载均衡性、请求接受率和网络收益方面性能优越。
