基于最小节点负载优先的逻辑承载网构建方法

李志敏 ，汤创为 ，谭敏生 ，王 舒 ，周 欢

LI Zhimin1，2,TANG Chuangwei1,TAN Minsheng1,WANG Shu1,ZHOU Huan1

1.南华大学 计算机科学与技术学院，湖南 衡阳 421001

2.湖南机电职业技术学院 信息工程学院，长沙 410151

1.School of Computer Science and Technology,University of South China,Hengyang,Hunan 421001,China

2.Shool of Information Technology,Hunan Mechanical&Eelectrical Polytechnic,Changsha 410151,China

1 引言

近年来，网络技术取得了飞速发展，服务能力比以前有了很大提高。现有网络采用面向业务支撑的体系架构，用户业务和网络提供的服务是紧耦合关系。当用户出现了新的业务需求，或者对原有业务的需求提高时，就需要对网络进行改造，而这种改造通常都是从增加链路带宽、提高节点处理速度、增加协议的复杂度等方面展开，难以满足特性差异日益扩大的用户业务承载需求[1]。一体化逻辑承载网是一种面向服务提供的新型网络技术体系，它根据网络服务提供能力和用户的业务需求及业务特性，以可重构路由交换平台为物理基础。这种定制网络的服务提供方式能够更好地满足用户多样化的业务需求，是将来网络技术发展的趋势[2]。

构建逻辑承载网的关键是对链路带宽、节点端口等公共资源进行分配，如何在资源有限的情况下有效地构建功能可升级重组，性能可编程分配，管理可分层配置的逻辑承载网，是一体化网络研究的热点问题[3]。文献[4]研究了低成本的虚拟网构建问题，提出了基于收益的启发式算法的虚拟网构建方法。文献[5]利用混合整数规划，针对不同的应用场景，提出了确定型虚拟网映射算法（D-ViNE）及随机虚拟网映射算法（R-ViNE）。文献[6]认为底层物理网络中的一条虚拟链路可以由多个分割的物理路径组成，提出了基于多商品流问题，并采用启发式算法进行路径集构建。文献[7]采用子图同构判定技术，综合考虑构建过程中的节点映射和链路映射，将节点和链路映射同时进行。文献[8]通过基于流量均衡并采用子图分割以及节点优化策略来实现虚拟网的拓扑设计。

上述虚拟网的构建方法，没有考虑底层物理网络的整体均衡性，一方面容易导致物理网络上发生拥塞或者出现节点负载过重的问题，尤其是在最短路径上，从而降低网络传输性能；另一方面，由于后续建网的关键路径很可能被占用，导致其构建成功率大大下降。针对上述构建方法的不足，本文在节点虚拟网构建算法中将多源多汇问题简化为多个单源单汇问题进行求解，在构建逻辑承载网时充分考虑底层物理网络的均衡性，提出最小节点负载优先映射策略（MinNLP），在此基础上通过实验从构建成功率、节点资源利用率、节点负载标准差三方面来验证MinNLP的优越性。

2 逻辑承载网模型分析

将逻辑承载网构建需求用无向图Gu=(Nu，Eu，Ru)表示，其中Nu和Eu代表逻辑承载网中虚节点和虚边的集合，它们分别是Np和Ep的子集，逻辑承载网构建请求通常包含对物理节点和边的限制条件，用Ru表示这些约束条件。

逻辑承载网厚茧问题在图论上的描述就是从Gu到Gp子集的一个满足Gu中约束条件Ru的映射，表示如下[9]：

其中 Ns⊂Np，Es⊂Ep，Cs代表构建逻辑承载网的物理网络服务能力。

节点映射：

链路映射：

将逻辑承载网的构建转化为单源单汇问题求解，构建需求就可以分解为虚节点需求和虚链路需求，由三元组 (s，t，d)表示，其中 s、t为源目节点，d 为带宽需求，这样分解后，逻辑承载网的构建问题简化为逐一求解元需求的过程[10]。

3 最小节点负载优先映射策略

节点负载是底层物理节点的负担，不同的承载网构建算法可能导致不同的节点负载。能够获得负载较均衡的映射算法可以实现资源更有效的利用，而均衡性较差的算法可能使得某些节点负载很轻，某些节点负载很重，这样很有可能会因为某些重要节点的资源不够而拒绝请求[11]。

定义1（节点强度SN）节点上承载的LCN资源之和与该节点拥有的资源的比值。

在虚拟网的研究中，多采用节点承载的虚拟网个数来描述节点的负载强度，因为虚拟网节点主要是服务器，节点的资源主要是内存、CPU等。一体化逻辑承载网络的节点资源主要是可重构的路由交换平台，节点的处理能力受到内存、CPU和节点交换带宽等影响，本文采用归一化的处理方式，只考虑内存使用情况反映节点负载，因此：

HNi表示第i个逻辑承载网占用某个节点的资源量，HNall表示该节点总的资源量，k为所承载的LCN的个数。

定义2（节点资源剩余量RN）在某时刻节点经过一系列的映射后还剩余的资源：

其中，HNi表示第i个逻辑承载网所花费的节点资源，而HNall为总的节点资源。

那么基于节点负载的构建策略思想就是在每次节点映射时选择负载较小且满足需求的物理节点进行映射。当有多个节点的负载强度相同时，就用节点资源剩余量为辅助标准[12]。

如图1所示，物理节点a、b、c的资源总量分别为80、60、40。在 T0 时刻，节点a、b、c的负载强度和剩余资源分别是25%（60），16.7%（50），12.5%（35）。 T1时刻，虚拟节点4（VN-4）到达，资源需求为5，此时节点c具有最小节点负载，且 Rn-c＞5，所以VN-4映射到节点c，映射后各节点负载强度和剩余资源分别为25%（60），16.7%（50），25%（30）。 T2时刻，虚拟节点5（VN-5）到达，资源需求为10，此时a和c的负载强度相同，但是Rn-a大于 Rn-c且大于10，所以VN-5映射到节点a，映射后各节点负载强度和剩余资源分别为37.5%（50），16.7%（50），25%（30）。 T3时刻，虚拟节点6（VN-6）到达，资源需求为20，此时节点b具有最小节点负载，且Rn-b＞10，所以VN-6映射到节点b，映射后各节点负载强度和剩余资源分别为37.5%（50），35%（30），25%（30）。

最小节点负载优先映射策略的目标是在节点映射时实现底层物理节点的负载均衡，通过综合考虑节点负载和节点剩余可用资源，提高资源利用率。

图1 最小节点负载优先的映射策略原理

最小节点负载优先映射策略的核心思想描述如下：

（1）将虚拟节点(Vnode)按申请资源大小排序。

（2）判断Vnode是否有剩余，若无剩余跳至步骤（5）。

（3）若Vnode有剩余，选择申请资源最多的Vnode映射到具有最小负载强度且相对剩余资源较多物理节点(Snode)。

（4）若找不到满足资源需求的Snode，则将该LCN请求送入等待队列或拒接请求，若能找到映射节点则跳到步骤（2）。

（5）节点映射成功，等待执行链路映射。

4 最小节点负载优先的逻辑承载网构建方法

在底层物理资源有限的条件下，考虑对LCN的构建请求执行接入控制，借鉴最小节点负载优先的思想，采用周期性的LCN映射处理方式来考虑LCN的映射处理问题。将LCN的到达过程看成是排队系统，LCN请求实时到达，以时间窗LCN映射的时间单位，对一个时间窗内到达的LCN构建请求进行收集，在一个时间窗内进行一次映射。如图2所示，LCN在时间窗模式下映射的方法是：

（1）释放上个时间窗内离开的LCN请求占用的资源，包括到达服务时间和主动拒绝的请求。

（2）统计本时间窗内LCN构建请求，包括新到达的请求和上个时间窗内为映射成功重新排队的请求。

（3）将LCN构建请求按实际收益多少降序排序，然后按收益大小映射到物理网络。如果该LCN映射成功，更新物理网络底层资源状态；如果映射失败，则将该请求放入等待队列，等待下一个时间窗来映射，对每个LCN请求允许重新映射的最大请求次数Max-Mapping预先设置，超过最大请求次数将不再送入等待队列，该LCN构建请求被拒绝。该映射方法能够保证LCN的实时处理，并且能够通过调节入口参数实现LCN准入机制的调节。在单位时间窗内，基于最小节点负载优先的逻辑承载网构建的核心算法描述如下：

图2 时间窗模式下LCN映射架构图

Sort（LCN）表示对单位时间窗内已有或新加入的LCN构建请求按收益排序；NumLCN为LCN构建数目；NumLCN_max为单位时间窗允许构建的最大值；Wait（NextLCN）表示等待下一个时间窗对LCN的映射；Resolve（LCN_max）为对最大收益的LCN进行分解；(s′=＞s，d′=＞d＜—MLS)表示采用最小节点负载优先策略（MinNLP）对 s、d进行节点映射；(Jump≤Rjump＜—KSP)表示采用K短路径优先（KSP K Shortest Path）的链路映射算法[13]进行链路映射，并且满足约束条件Jump≤Rjump；JoinWait（LCN）代表LCN加入等待队列；s′∈Gs，d′∈Gs，w(s′，d′)＞ 0，Rjump≥ 1。

5 实验及分析

5.1 仿真实验平台

本文使用Java语言设计仿真器来评估算法性能。该仿真器能够产生承载网请求，并将请求转化为单源单汇形式。请求队列管理器主要负责请求队列和时间窗的管理，资源状态管理器主要动态跟踪物理资源的变化情况，请求映射管理器负责承载网的映射，是仿真器的核心，通过给定的算法将逻辑承载网映射到底层物理网中，同时展现映射结果，输出各种实验数据（图3）。

图3 仿真器架构图

5.2 参数设置

给定20个节点的物理网络，节点资源在20到30之间随机分布，每条物理链路带宽资源在8到12个单位随机分布；每个LCN的节点数在3到5之间，节点需求资源在4到6之间，带宽资源请求在1到3之间随机分布。每个LCN的生命周期为一个时间窗，时间窗大小设置为60 s，前5个时间窗内LCN请求数在4到6之间均匀到达，后5个时间窗LCN请求数在15到18之间均匀到达，实验一共模拟10个时间窗，并进行10组实验，统计每次实验结果，取其平均值。

用下面两种LCN构建方法进行仿真实验：

（1）G-SP方法。基于贪心K短路径思想构建，其中节点映射采用贪心（Greedy）算法[14]，链路采用K短路径算法（K Shortest Path）映射。

（2）MinNLP-LLB方法。基于最小节点负载优先K短路径思想构建，节点采用最小节点负载优先（Minimum Node Lode Priority，MinNLP）算法，链路采用链路负载均衡策略映射LLB（Link Lode Balance）[15]。

5.3 构建成功率

图4 MinNLP-LLB与G-SP构建成功率对比曲线

构建成功率是指单位时间内LCN构建成功的个数与总的申请数的比值。由图4可以看出，在第一个时间窗内，节点和链路基本处于空闲状态，底层物理资源相对较多，两种方法的构建成功率都接近100%。在第二个时间窗内，由于第一个时间窗构建的LCN还未离去，占用的资源还没有释放，因此两者的构建成功率出现了小幅度下降。第二个时间窗到第五个时间窗，随着原来存在的LCN达到生存时间，网络资源不断被释放，构建成功率达到一种统计上的稳定状态，此时Min-LLB优势初步显示出来。第六个时间窗开始，由于大幅度增加了每个时间窗内LCN的请求个数，相对可用资源减少，两种方法的构建成功率出现了大幅度下降，第六个时间窗两种方法的构建成功率只有50.7%和36.3%。第七个时间窗开始到实验结束，构建成功率达到一种统计上的稳定状态，两者的构建成功率在46.5%和35.5%左右。从两个时间段的差异可以看出，在底层物理资源数不变而LCN请求数量大增的情况下，MinNLP-LLB方法的优势非常明显，构建成功率比G-SP方法高出近11个百分点。

5.4 资源利用率

单位时间窗构建LCN所花费资源与物理网总资源的比值。图5横坐标表示运行的时间窗，纵坐标表示LCN的资源利用率。在第一个时间窗到第五个时间窗内，由于实验设定的LCN的生存时间为一个时间窗，某个时间窗结束时，上一个时间窗生成的LCN也达到离开时间，对整个物理网而言承载的LCN数量较少，大部分资源处于空闲状态，因此该阶段两种方法节点资源利用率相近且处于较低的水平，MinNLP-LLB的优势不明显。到第六个时间窗，LCN的请求数量大增，虽然两种方法的构建成功率下降了，但是整个物理网承载的LCN增加。由于MinNLP-LLB方法在资源分配过程中考虑了实时负载情况，因此利用该方法构建时，在单位时间LCN请求增多的情况下，节点资源利用率达到了77.9%，远高于G-SP方法的63.7%。

图5 MinNLP-LLB与G-SP节点资源利用率对比曲线

5.5 链路均衡度

为了更详细描述资源在物理网络中的使用情况，还需要考虑每个局部的情况，主要考虑局部资源使用率和整个网络资源使用率的差异，即链路均衡度：

其中SLi(t)表示第t次抽样时节点i的负载强度表示第t次抽样时节点平均负载强度，其中e表示节点的总个数，其值越小，链路负载就更加平衡，说明网络处于均衡使用的一种状态。

从图6可看出，在每个时间窗内，用MinNLP-LLB构建方法的链路均衡度均小于G-SP方法，说明链路负载越均衡，瓶颈节点的出现几率就越小。

图6 MinNLP-LLB与G-SP链路均衡度对比曲线

在底层物理资源充足，而请求构建的逻辑承载网较少时，MinNLP-LLB方法与G-SP方法的构建成功率基本相同，但MinNLP-LLB方法比G-SP的休眠率低13个百分点左右，表明MinNLP-LLB方法使用相对较多的物理节点，网络拓扑相对复杂。但在映射后期，映射请求逐渐增多，MinNLP-LLB方法更大幅度地提高构建成功率、资源利用率和链路均衡度，更适合用来构建逻辑承载网。

6 结束语

作为下一代网络关键技术的一体化逻辑承载网络技术已逐渐成为研究热点。本文分析了承载网的数学模型，提出了最小节点负载优先映射策略，在此基础上给出了基于最小节点负载优先映射策略的逻辑承载网构建方法，并通过实验从三个方面验证了MinNLP-LLB的优越性。

逻辑承载网的构建方法还有很多问题有待进一步研究与探索，本文只是针对如何使得物理网更均衡映射进行研究，除此之外，用户业务聚类、安全架构、适合大规模组网的构建算法，是下一步研究的重点。

[1]张伟，吴春明，姜明，等.一体化承载网络的互斥问题研究[J].计算机应用研究，2010，27（3）：1148-1150.

[2]汪斌强，邬江兴.下一代互联网的发展趋势及相应对策分析[J].信息工程大学学报，2009，10（1）：1-6.

[3]张宏科.“一体化可信网络于普适服务体系基础研究”项目计划任务书[R].北京：北京交通大学，2007.

[4]Lu J，Turner J.Efficient mapping of virtual networks onto a shared substrate，Technical Report WUCSE-2006-35[R].Washington University，2006.

[5]Mosharaf N M，Raihan R M，Raouf B.Virtual network embedding with coordinated node and link mapping[C]//Proceedings of the 28th Coference on Computer Communications.Riode Janeiro，USA：IEEE，2009：783-791.

[6]Yu Minlan，Yi Yung，Rexford J，et al.Rethinking virtual network embedding：substrate support for path splitting andmigration[C]//Proceedingof ACM SIGCOMM on Computer Communication，Seattle，WA，USA，2008：17-29.

[7]Jens L，Holger K.A virtual network mapping algorithm based on subgraph is omorphism detection[C]//Proceeding of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures，Barcelona，Spain，2009：81-88.

[8]Zhu Y，Ammar M.Algorithms for assigning substrate network resources to virtual network components[C]//Proceedings of IEEE INFOCOM，Barcelona，Catalunya，Spain，2006：1-12.

[9]齐宁，汪斌强，郭佳.逻辑承载网构建方法的研究[J].计算机学报，2010，9（15）：1536-1537.

[10]张旻，吴春明，王滨，等.跨域逻辑承载网映射方法研究[J].通信学报，2012，33（8）：200-208.

[11]张栋.基于可重构柔性网络的逻辑承载网构建理论与方法[D].杭州：浙江大学，2010.

[12]Cui Y，Wu J P.Research on Internetwork QoS routing algorithms：a surevey[J].Journal of Software，2002，13（11）：2065-2075.

[13]齐宁.基于网络生存性可重构服务承载网构建算法研究[D].郑州：解放军信息工程大学，2011.

[14]李文，吴春明，陈健，等.物理节点可重复映射的虚拟网映射算法[J].电子与信息学报，2011，33（4）：908-914.

[15]王海英，张建忠.多链路管理中的负载均衡策略[J].南开大学学报：自然科学版，2004（4）：59-63.