跨域逻辑承载网映射方法研究

张旻，吴春明，王滨，姜明

（1. 杭州电子科技大学 计算机学院，浙江 杭州 310018；2. 浙江大学 计算机科学与技术学院，浙江 杭州 310027）

1 引言

随着互联网业务类型的不断丰富，网络规模的不断扩大，促使网络技术需要不断地进行革新，以适应用户业务和网络规模快速发展的需求。然而，仅仅依靠拓展链路传输带宽，提高节点处理速度等方法，不仅难以满足特性差异日益扩大的用户业务承载需求，而且面对大量差异化用户业务的规模化应用，网络无法适应的问题日趋凸现。针对上述问题，文献[1,2]以用户业务需求为驱动，提出了面向服务提供的可重构柔性承载网络(UCN, universal carrying network)技术体系，基于可重构路由交换平台，通过构建可重构逻辑承载网(LCN, logical carrying network)的形式，快速、灵活和高效地为用户业务提供多样化的网络服务。

LCN映射是构建可重构逻辑承载网的核心过程，也就是根据用户业务承载需求(如LCN的拓扑、带宽等)，为每条逻辑链路选择适当的物理网络路径，并为其分配资源。LCN映射问题从理论和应用上来说都是一个非常具有挑战性的问题,主要原因在于：一方面，LCN构建需求的多样性、物理网络资源的有限性、LCN构建请求是动态到达且不可预知的；另一方面，LCN映射既要满足用户业务需求，也要高效地利用物理网络资源，以期在资源有限的物理网络上能够构建尽可能多的逻辑承载网，实现物理网络提供商利益的最大化。

目前，国内外研究人员对LCN映射或虚拟网[3,4]映射问题做了诸多有益的探索，取得了一定的成果。王浩学等[2]设计了一种基于资源均衡的LCN映射算法，比较了分别采用基于负载均衡的映射算法和不支持负载均衡的映射算法时 LCN构建成功的概率。齐宁等[5]讨论了映射策略的若干重要原则，并在此基础上提出了带迁移同时考虑网络均衡的映射方法。李文等[6]结合K短路径的思想，寻找满足逻辑链路带宽需求的物理路径。Cheng Xiang等[7]运用马尔科夫随机漫步模型把网络资源与网络拓扑相结合对网络节点排序，基于节点排序结果进行虚拟网映射，该方法突破了传统映射过程只考虑网络资源的思想，提高了映射效率。W. Szeto[8]基于多商品流问题中的最大并行流问题（maximum-concurrent flow problem）在物理网络中每个边缘节点对之间进行资源的预分配，采用线性规划的方法来进行求解。当一个新的虚拟网构建需求到达后，在预分配资源中对虚拟网所需资源进行实际分配。Minlan Yu等[9]提出了多径映射的思想，通过将虚拟链路映射到多条物理路径上，以提高物理网络的负载均衡和资源可利用率，并基于多商品流问题来进行建模求解。Jens Lischka等[10]提出通过子图同构检测和回溯的方法来将虚节点和虚链路同步映射到物理网络中，以提高虚拟网构建成功的概率。针对虚节点映射的位置要求，N. M. Mosharaf等[11]提出通过在底层物理网络上设立虚拟的元节点和元边来扩展物理网络，从而将一个虚节点映射位置不确定问题转化为确定性问题，再通过混合整数规划的方法来进行建模求解。

上述提出的一些映射算法都属于集中式的解决方案，即需要获取整个物理网络的拓扑、带宽资源等信息。然而，在实际中，物理网络分成了多个自治域，由不同的基础设施提供商(InP, infrastructure provider)管理，而每个InP往往不愿提供其物理网络拓扑、资源等相关信息。因此，目前的这些映射算法无法对跨域的LCN进行映射。尽管文献[12]和文献[13]分别提出了一种分布式和跨域映射方案，但文献[12]中的分布式算法还是要求网络中的每个结点通过通信协议获取整个网络拓扑等信息，而文献[13]提出的是一种启发式跨域映射方案，没有从数学模型上考虑网络资源优化和映射代价。基于上述原因，如何有效地对跨域 LCN进行映射仍是具有重要研究意义和挑战的工作。

针对跨域LCN映射问题，本文将物理网络分为2层视图，低层视图即各个域的物理网络拓扑，而高层视图是由路径矢量构成的网络拓扑。在此基础上，本文以最小映射代价为目标，提出了一个新颖的分层优化模型，并运用最优化理论中的原始分解方法，将该模型分解为2个子问题，其中一个子问题涉及各个域的物理网络信息，从而可以由各个域独立求解，而另一问题与路径矢量网络有关，可在路径矢量网络上作优化。最终，基于跨域LCN映射分层模型的分解，本文提出了一个跨域LCN映射算法，实验表明该算法可以快速收敛，并与其他跨域映射方案相比，具有更好的性能。

2 逻辑承载网映射问题描述

LCN构建是根据用户业务的需求及物理网络当前的资源状况，通过映射算法在构建需求与网络资源之间进行匹配，以获得最优的网络资源分配方案。下面对LCN映射问题进行数学描述。

物理网络可以抽象表示为G(V,E)，其中，V表示物理节点的集合，E表示物理链路的集合。本文将考虑LCN的拓扑和逻辑链路带宽需求，LCN构建需求表示为｛Gv( Vv, Ev),D｝ ，其中，Gv( Vv, Ev)表示LCN的拓扑， Vv和 Ev分别表示LCN节点和逻辑链路的集合，为逻辑链路带宽需求的集合。进一步可以用一个三元组(s,t,d)表示承载网逻辑链路的带宽需求，其中，s和t表示承载网逻辑链路的2个端点，LCN构建需求也可表达为三元组的集合，即{(si, ti, di)|1 ≤ i≤m}，m为待构建的承载网中逻辑链路的个数。

对于LCN映射问题，可描述为将逻辑链路映射到某条物理路径，记作path(s,t)= Mlink(e)，其中，path(s, t)表示s至t所经过的物理链路，Mlink(·)表示逻辑链路到物理路径的映射关系。这时，LCN映射可以看作是在 G(V, E)中构建一个子图G′( V′, E ′)，这个子图应当满足承载网构建需求，而构建子图 G ′( V′, E ′)的目标是使构建费用最小化，即：

其中，w表示链路e单位带宽的代价，x(e)表示在链路e上所需的带宽。

3 跨域逻辑承载网映射算法

3.1 跨域映射分层优化模型

假设将物理网络G(V,E)划分为N个域，其拓扑图分别记为 Gi( Vi, Ei)，1≤i≤N，Vi为域i中节点集合， Vib为域i中边界节点集合(将连接2个不同域的链路的两端称为边界节点，连接2个不同域的链路称为边界链路)， Ei为域i中链路集合。我们将从分层的角度考虑底层物理网络在不同层次的视图。高层次视图，也称为路径矢量网络，记为Gl( Vl, El)。路径矢量网络中的链路(路径矢量)对应于底层物理网络的路径或边界链路，例如，图1中路径矢量网络的链路 ( b1, b3)和(b3, b5)分别对应于底层物理网中 b1与 b3间的路径和边界链路 (b3, b5)。路径矢量网络的节点集合 Vl由所有域的边界节点组成，链路集合 El由对应于底层物理网络中每个域边界节点之间的路径或边界链路的路径矢量组成。低层次视图，也就是每个域的物理拓扑子图。图 1给出了一个物理网络的2层视图，其中，图1(b)和图 1(c)分别是物理网络(图 1(a))的高层次视图和低层次视图。

图1 物理网络的2层视图

基于物理网络分层结构，采用多商品流数学模型，本文可以建立以下跨域 LCN映射的分层线性规划(LCN_HLP, logical carrying network hierarchical linear program)模型。对于一个 LCN构建请求可分解为域内逻辑链路集合和域间逻辑链路集合域内逻辑链路的映射可以采用文献[9]的方法解决，为此，下面分层线性规划模型是针对域间逻辑链路映射的建模。另外，由于的is或it可能不是边界节点，此时，路径矢量网络还要包含该节点到其域内边界节点的路径矢量。

1) 输入

跨域LCN构建请求：

边界链路集合：bE表示所有边界链路。

物理链路剩余带宽：uvr表示物理链路的剩余带宽。

2) 变量

① 高层次视图约束条件

② 低层次视图约束条件

③ 其他约束条件

LCN_HLP模型解释如下。

1) 式(2)为数学规划的目标函数，目标是使构建的逻辑承载网的代价最小化。式中由各域预先计算得到，本文采用的计算方法是：先通过网络最大流计算出节点u和v之间的最大流，并计算得到最大流的代价，从而可以计算出u和v间的平均代价。设uvλ和分别表示由最大流算法计算得到的节点u和v之间的最大流及经过物理链路的流量，则

2) 式(3)、式(4)是高层次视图中多商品流模型的约束条件，其中构建带宽需求 di作为多商品流模型中的商品需求， yuv作为容量限制。式(5)、式(6)是低层次视图中多商品流模型的约束条件，其中yuv作为商品需求，物理链路剩余带宽 ruv作为容量限制。

3) 为了后面描述方便，本文采用粗体字和大写字母表示向量和矩阵，式(3)、式(4)可以用矩阵表示为Bf≤y,Afi=di,1≤i≤m，其中，fi表示变量所构成的向量，di表示LCN需求向量，y表示变量yuv所构成的向量同样地，式(5)、式(6)可以用表示为及

图4(a)和图4(b)分别逆变器桥臂上的主开关器件S1和S2进行状态切换过程中承受的电压uS1和uS2及所流经的电流iS1和iS2的实验波形，能看出S1和S2在开通过程中完成了零电压软开通动作，在关断过程中完成了零电压软关断动作.图4(c)和图4(d)分别为逆变器辅助开关Sa1和Sa4切换时端电压uSa1和uSa4及所流经的电流iSa1和iSa4的实验波形，可看出Sa1和Sa4在开通过程中分别完成了零电压软开通动作和零电流软开通动作，在关断过程中分别完成了零电压软关断动作和零电流软关断动作.

3.2 模型求解及映射算法设计

基于原始分解方法[14]，LCN_HLP问题可以分解为2个最优子问题。当y固定时，子问题1可以表示为

约束条件：

子问题1可以看作是LCN构建请求在路径矢量网络中的映射问题，该模型是一个线性规划问题，可以通过单纯形方法或内点法进行求解。

子问题2目标是更新变量向量y，表示为

约束条件：

其中， z*(y)是给定y时，子问题1的最优目标值。定理1 设Θ表示可使线性规划式(10)～式(13)

具有可行解的y的集合。对于y∈Θ，z*(y)是凸函数。证明 根据凸函数的定义，要证明 z*(y)是凸的，只需验证：对给定的若，则

因为式(11)～式(13)及式(10)都是线性的，很容易直接验证z*(y) 是凸函数。

尽管函数z*(y)是凸的，但是不可微的。次梯度方法是求解子问题 2的一个简便方法。设向量为子问题1中式(11)对应的对偶变量，其可作为z*(y)的次梯度，并由对偶理论可知由此，可以采用公式nθ←-yyq更新向量y，其中，nθ是第n步的步大小，其可以通过下式计算[15]：

如果更新后的y不满足式(15)～式(17)，需要修正y以保证满足物理网络链路的剩余带宽限制。显然，修正y可以分解到各个域完成，即第i域修正

通过上述分析，可以设计算法对LCN_HLP模型进行求解，该算法包括2部分：全局逻辑承载网映射算法(GLCNMA, global logical carry network mapping algorithm)和局部逻辑承载网映射算法(LLCNMA, local logical carry network mapping algorithm)。GLCNMA其主要过程是求解子问题1和更新变量uvy。LLCNMA将在各域中运行，其将修正uvy，以保证满足物理网络链路约束条件。值得一提的是，由于GLCNMA仅需要路径矢量网络的拓扑信息，LLCNMA在各域中运行，只需各域的网络拓扑信息，因此，本文提出的跨域 LCN映射算法可以在无法获得底层物理网络全局拓扑的情况下，通过GLCNMA和LLCNMA的相互协作共同完成跨域映射。

图2具体描述了GLCNMA的基本过程。Step1)给出算法的初始值，Step3)中采用次梯度方法更新变量uvy，其中，是子问题 1中式(11)对应的对偶变量，若那么设由于uvt可能不满足物理网络链路的剩余带宽约束条件，Step4)～Step5)把uvt发送给各域的LLCNMA，通过LLCNMA修正后返回得到满足物理网络链路的剩余带宽约束条件的uvy值。Step6)针对更新后的uvy 求解子问题 1。Step3)～Step6)经过K次迭代得到LCN在路径矢量网络中的最优映射结果，该结果通过Step8)发送给各域，由各域的LLCNMA计算出LCN在物理网络上的最终映射结果。

图2 GLCNMA算法流程

图3描述了在第i域中运行的LLCNMA算法。LLCNMA包括3部分：1)初始化，uvy看作是路径矢量网络中节点u与v间分配的带宽容量，本文采用文献[16]的最大最小公平多商品流算法为所有公平分配带宽；2)修正以满足物理网络链路的剩余带宽约束条件[17]；3)路径映射。采用最小代价多商品流模型将路径矢量网络的链路映射到物理网络上。

图3 LLCNMA算法流程

定理 2 如果次梯度更新步长足够小，则本文提出的跨域 LCN映射算法可以收敛到最优解附近一个很小的区域内。

证明 由线性规划对偶理论可得子问题1的对偶问题，其表达式为

约束条件：

其中，向量 ,q p分别为子问题 1中式(11)和式(12)对应的对偶变量。

因为z*(y) 表示给定y时子问题 1的最优目标值，从而可知

并且由于z*(y) 是最优值，因此

进一步由式(19)和式(20)可得：

由次梯度定义[18]， q*是 y = y*时 z*(y)的次梯度，也就是向量q作为子问题 1中式(11)对应的对偶变量，其值可作为 z*(y)的次梯度。

因为跨域 LCN映射算法采用次梯度方法[18]更新向量y，而文献[18]已证明了当次梯度更新步长足够小时，次梯度算法可以收敛到最优值。因此，跨域 LCN映射算法可以收敛到最优解附近一个很小的区域内。

4 仿真实验

本节仿真实验的目的包括2个方面：一是验证本文提出的跨域映射算法的收敛性以及在大规模网络环境下算法的运行速度；二是在动态网络环境下，即LCN构建请求随机到达及LCN随机拆除情况下，验证算法性能，包括LCN请求接受率和LCN构建平均收益。

实验中物理拓扑采用BRITE工具[19]随机生成，并利用MATLAB工具实现算法。

4.1 算法的收敛性

随机生成分为10个域的物理网络，其中每个域包括50个节点，物理网络的链路带宽容量服从100～120间的均匀分布。随机生成跨域LCN构建请求，LCN的拓扑包含 30条逻辑链路，逻辑节点随机分布在各域，带宽需求为90。通过图4可以看到算法在40次迭代后便可收敛于LCN_HLP模型的最优值；尽管 LCN_HLP模型的最优解与全局集中式映射算法最优值[9]之间存在偏差，但小于3%。

显然，映射算法的运行速度与迭代次数有关，迭代次数越多，运行时间越长。算法需要在最优性和运行时间(即迭代次数)之间平衡，从图 4中可以看出，迭代 15次时，算法得到的解与最优值间的偏差小于 4%，因此，在后面动态环境下实验中，将算法的迭代次数设为15。

图4 算法收敛性

4.2 算法的运行时间

图5给出了不同物理网络大小下的算法运行时间。在实验中，随机产生 6个物理网络，每个物理网络都分为10个域，而每个物理网络域的节点数从50～100间增加。物理网络的链路带宽容量服从100～120间的均匀分布。随机生成跨域LCN构建请求，LCN的拓扑包含30条逻辑链路，逻辑节点随机分布在各域，带宽需求为90。实验测试了迭代次数分别为0,5,10,15时算法的运行时间，并与全局集中式映射算法[9]进行了比较。从图5中可知，全局集中式映射算法随着物理网络规模的增大，其运行时间也迅速增加，而本文跨域映射算法的运行时间缓慢增加。其主要原因是：①LLCNMA在各域中并行运行；②GLCNMA算法的运行时间主要在求解子问题1，而子问题1的复杂度与路径矢量网络大小有关，但路径矢量网络与物理网络相比，规模更小。

图5 算法运行时间

4.3 算法的动态性能

在这个实验中，本文评估在动态环境下算法的LCN请求接受率和LCN构建平均收益，并与文献[13]中的PolyViNE算法进行比较。实验中的所有仿真都执行3 000个时间单位，以获得稳定的性能测试结果。性能测试指标定义如下：

仿真实验所采用的网络随机生成分为10个域的物理网络，其中每个域包括50个节点，物理链路的带宽服从100～120间的均匀分布。随机生成LCN构建请求，LCN的逻辑链路带宽服从20～30间的均匀分布，LCN请求到达间隔时间和LCN生命周期均服从Poisson分布。通过图6和图7可以看到，本文的算法在接受率和平均收益上明显优于基于单径启发式搜索的PolyViNE算法，授受率提高了近10%，平均收益提高了大约20%。其原因在于：PolyViNE算法将LCN的每条逻辑链路映射到物理网络的单个路径上，而物理网络随着构建的LCN的增多，有些关键链路上的资源不足，导致在单个路径上无法完成逻辑链路映射。本文算法允许逻辑链路映射到物理网络的多条路径上，在资源不足时，会将LCN链路带宽需求分割到多条路径，从而提高了接受率和平均收益。

图6 LCN请求接受率

图7 LCN构建平均收益

5 结束语

LCN映射算法是实现可重构逻辑承载网的关键技术，而目前提出资源优化映射算法在无法获取整个物理网络拓扑信息的情况下，难以对跨域的LCN进行映射。为了解决大规模网络环境中跨域LCN的映射问题，本文以最小映射代价为目标，提出了一个分层线性规划模型，并基于模型的原始分解，设计了一个跨域LCN映射算法。基于MATLAB的仿真实验分析本文跨域映射算法的性能，实验表明该算法可以快速收敛到最优值，当迭代次数选择15时，可以较好地达到最优性与运行时间的折中;与现有的跨域映射方案相比，本文算法的构建请求接受率和平均收益分别提高了近10%和20%，具有更好的性能。

[1] 汪斌强, 邬江兴. 下一代互联网的发展趋势及相应对策分析[J]. 信息工程大学学报, 2009, 10(1):1-10.WANG B Q, WU J X. Development trends and associated countermeasures analysis for NGN[J]. Journal of Information Engineering University , 2009, 10(1):1-10.

[2] 王浩学, 汪斌强, 于婧等. 一体化承载网络体系架构研究[J]. 计算机学报, 2009,32(3): 371-376.WANG H X, WANG B Q, YU J, et al. Research on architecture of universal carrying network[J]. Chinese Journal of Computers, 2009,32(3): 371-376.

[3] ANDERSON T, PETERSON L, SHENKER S. Overcoming the internet impasse through virtualization[J]. Journal Computer, 2005, 38(4):34-41.

[4] FEAMSTER L, GAO L, REXFORD J. How to lease the internet inyour spare time[J]. ACM SIGCOMM Computer Communications Review, 2007, 37(1): 61-64.

[5] 齐宁, 汪斌强, 郭佳. 逻辑承载网构建方法的研究[J]. 计算机学报,2010,33(9): 1533-1540.QI N, WANG B Q, GUO J. Research on construction methods of logical carrying network[J]. Chinese Journal of Computers，2010,33(9):1533-1540.

[6] 李文, 吴春明, 陈健等. 物理节点可重复映射的虚拟网映射算法[J].电子与信息学报,2011,33(4):908-914.LI W, WU C M, CHEN J, et al. Virtual network mapping algorithm with repeatable mapping over substrate nodes[J]. Journal of Electronics ＆ Information Technology, 2011,33(4):908-914.

[7] CHENG X, SU S, ZHANG Z, et al. Virtual network embedding through topology-aware node ranking[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(2):39-47.

[8] SZETO W, IRAPI Y, BOUTABA R. A multi-commodity flow based approach to virtual network resource allocation[A]. Proc of the IEEE GLOBECOM[C]. San Francisco, USA, 2003.3004-3008.

[9] YU M, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29.

[10] LISCHKA J, KARL H. A virtual network mapping algorithm based on subgraph isomorphism detection[A]. Proc of the ACM SIGCOMM[C].Barcelona ,Spain, 2009.81-88.

[11] MOSHARAF N M, CHOWDHURY K. Virtual network embedding with coordinated node and link mapping[A]. Proc of the IEEE INFOCOM[C]. Rio de Janeiro, Brazil, 2009. 783-791.

[12] HOUIDI I, LOUATI W. A distributed virtual network mapping algorithm[A]. Proc of the IEEE ICC[C]. Beijing, China, 2008. 5634-5640.

[13] CHOWDHURY M, SAMUEL F, BOUTABA R. PolyViNE: policy-based virtual network embedding across multiple domains[A].Proc of the Second ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures[C]. New Delhi, India,2010. 49-56.

[14] CHIANG M, LOW S, CALDERBANK A. Layering as optimization decomposition: a mathematical theory of network architectures[J].Proceedings of the IEEE, 2007, 95(1): 255-312.

[15] BARAHONA F, ANBIL R. The volume algorithm: producing primal solutions with a subgradient method[J]. Math Program, 2000,87:385-399.

[16] ALLALOUF M, SHAVITT Y. Centralized and distributed algorithms for routing and weighted max-min fair bandwidth allocation[J]. Networking, IEEE/ACM Transactions on, 2008, 16(5): 1015-1024.

[17] HE J, SHEN R, LI Y, et al. DaVinci: dynamically adaptive virtual networks for a customized internet[A]. Proc of the 2008 ACM CoNEXT Conference[C]. Madrid, Spain, 2008.1-12.

[18] FREUND R. Subgradient Optimization, Generalized, Programming,and Nonconvex Duality[R]. MIT, 2004.

[19] MEDINA A, LAKHINA A, MATTA I. BRITE: an approach to universal topology generation[A]. Proc of Ninth International Symposium on Modeling, Analysis and Simulaion of Computer and Telecommunication Systems[C]. Ohio, USA, 2001.346-353.