弹性光传输基础设施上动态透明虚拟网络嵌入

2014-06-28徐浩煜汪亮友朱祖

中兴通讯技术 2014年3期

徐浩煜　汪亮友　朱祖

摘要：提出了一个新的动态透明的虚拟网络嵌入（VNE）算法。该算法基于弹性光传输基础设施，同时考虑节点映射和链路映射，用于光正交频分复用（O-OFDM）的网络虚拟化。对每一个虚拟光网络（VON）的请求，该算法首先根据各光纤链路的频谱使用将底层光网络转化成一个分层辅助图，然后在该辅助图的单层上应用一个考虑了所有底层节点的本地信息的节点映射完成链接映射。仿真结果表明，该算法考虑了O-OFDM网络的独特性，并且由于算法提供较低的VON阻塞概率，优于直接应用VNE的参考算法。实际拓扑结构的仿真结果也表明，嵌入的底层路径的平均距离很好地被控制在O-OFDM信号的典型传输范围内。

关键词：光网络的虚拟化；动态透明的虚拟网络嵌入；光正交频分复用

近期网络应用的蓬勃发展刺激了高弹性和可扩展网络技术的研究和开发。因此，网络虚拟化正在成为未来互联网一个可行的解决方案，并开始吸引越来越多的研究兴趣[1]。同时，由于光纤带宽巨大，网络运营商一直依靠光纤技术来扩展他们的网络，其网络的带宽需求呈指数上升趋势。在光纤网络中用于物理数据的传输，光正交频分复用（O-OFDM）技术由于它的弹性特性，最近被视为波分复用（WDM）技术强有力的替代者[2]。在基于O-OFDM技术的网络中，带宽粒度在几吉赫兹甚至更少的情况下，频谱资源是基于连续的子载波时隙分配的。因此，带宽可变的O-OFDM转发器可以分配刚好够用数量的子载波时隙为连接请求提供服务，并达到子波长的粒度。为此，基于O-OFDM的弹性光网络被认为是用作网络虚拟化的潜在物理基础设施[3-4]，特别是对于高度分布式和数据密集型应用，例如拍比特级网格计算[5]。

光网络的虚拟化是在底层（或物理）光网络上提供多个虚拟光网络（VON）用于共享计算资源和带宽资源[3，6]。虚拟光网络由虚拟节点（VN）和连接节点的虚拟光链路（VOL）构成。基础设施通过使用一个被称为虚拟网络嵌入（VNE）的程序来服务虚拟光网络（VON），VNE中，对于每个虚拟光网络的请求，通过节点映射和链路映射在底层网络分配必要的资源。通常情况下，我们可以将VNE分为静态和动态两类。对于静态VNE，所有的虚拟光网络请求是已知的，并且基础设备提供商可以优化请求服务的顺序以提高底层资源的利用效率；对于动态VNE，在动态的网络环境考虑如何服务时间变化的虚拟光网络请求。由于虚拟光网络请求不是已知的，可以随时到来和离开，所以动态VNE需要更复杂的算法来最小化虚拟光网络的阻塞概率。

以前在光网络上VNE的工作大多数是对基础设施使用时分复用（TDM）技术，如SONET或SDH[7]或使用波分复用（WDM）[8-11]技术。在文献[7]中，作者在多个域的SDH网络上研究动态VNE，并提出了一个有效服务虚拟光网络请求的调度方案。基于所有的底层节点都配备了足够的波长转换器的假设，在文献[8]中一个混合整型线性规划（MILP）模型被提出并用于解决波分复用网络上的静态VNE。通过将（物理层损伤PLI）考虑在内，在文献[9]中作者提出了一个用于波分复用网络的动态感知损伤的VNE算法。接着在文献[10]中他们扩展了研究，同时考虑单行速率和混合线路速率的波分复用网络。在文献[11]中，Pages等人在波分复用网络上为透明和不透明的VNE建立了整型线性规划（ILP）模型，并提出一种启发式的透明方案。由于他们没有解决虚拟光网络的节点映射，所以在文献[9-11]中的研究仅仅解决了VNE的部分问题。

最近，在基于O-OFDM的弹性光传输基础设施上的网络虚拟化开始吸引人们研究的兴趣。它的工作原理和关键技术在文献[3-4]中进行了综述，这些综述指出O-OFDM转发器的操作需要虚拟光链路运行在频谱域中连续的子载波时隙。因此，在O-OFDM网络上的VNE有附加的约束，而且开发用于波分复用或2/3层网络虚拟化的算法并不直接适用。在文献[12]中，Pages等人建立了用于O-OFDM网络上静态不透明的VNE的ILP模型。然而，虚拟光网络的节点映射仍然被忽略了。

本文考虑了带有时变虚拟光网络请求的O-OFDM网络，并提出一个动态透明的包含节点映射和链路映射的VNE算法。类似于波分复用网络上透明的VNE中的链路映射[11]情景，为了确保透光性的端到端的链接可以在虚拟光网络中任意两个虚拟节点间部署，在虚拟光网络中我们需要给每个虚拟光链路分配相同的子载波时隙。对每个虚拟光网络请求，该算法首先根据各个光纤链路的频谱使用将底层光网络转化为一个分层辅助图，然后应用一个新的考虑了所有底层节点的本地信息的节点映射方法，并且通过在该辅助图的单层执行最短路径路由完成链接映射。据我们所知，同时包括链路映射和节点映射，以解决弹性光传输基础设施上动态透明的VNE，这是首次提出。

1 虚拟网络嵌入问题描述

1.1 虚拟网络嵌入模型

一个透明VNE的例子如图1所示。图1包括底层光网络、虚拟光网络请求和映射结果。

（1）底层光网络

一个底层光网络可以建模成一个无向图，记为GS（VS， ES），其中VS是底层节点的集合，ES是底层光纤链路的集合。每个属于节点集合VS的节点vS都有一个相应可用的计算能力[csvs]，即该节点的计算能力。对于每个属于链路集合ES的链路eS，我们定义一个包含B个比特的比特掩码[bses]，其中B是一个光纤链路可以容纳子载波时隙的最大数量。当[bses][ j]=1时，表示链路eS上第j个时隙被占用，否则[bses][j]=0。图1（a）显示一个底层网络的形象的例子，底层节点的计算能力标记在矩形内，各个光纤链路的举行条描绘了它的频谱使用情况。

（2）虚拟光网络请求

一个虚拟光网络请求（VON）可以被建模成一个无向图G r（V r， E r ）。我们用符号[crvr]来表示在虚拟光网络请求中各个虚拟节点v r∈V r的计算能力需求。每个虚拟光链路（VOL）er∈ E r的带宽要求被定义为nr，是我们需要分配给它的连续时隙的数量。图1（b）显示一个虚拟光网络请求，计算能力要求标记与图1（a）相似，同时每个虚拟光链路的数量表示带宽要求nr。注意，一个虚拟光网络中所有的虚拟光链路的nr是相同的，这是对称网络中的常识。

1.2 虚拟网络嵌入程序

当虚拟光网络（VON）请求到达时，动态透明VNE算法试图执行以下两个操作：

（1）将虚拟节点分配给有足够计算资源的底层节点（即节点映射）。

（2）选择底层光纤链路来实现虚拟光链路，并在选定的节点上分配足够的子载波时隙以满足带宽需求（即，链路映射）。如果两个操作都成功，虚拟光网络的请求被置备（Provisioned）；否则将被阻止。

节点映射和链路映射细节如下：

（1）节点映射

1.3 虚拟网络嵌入目标

动态透明VNE算法的目标是最小化虚拟光网络请求的阻塞概率。这里，阻塞概率是指在特定时间周期内在多个到达节点上阻塞的请求数量与总的请求数量的比值。实际上，有两种可降低阻塞性能的惩罚因子（Penalty Factors）。

（1）惩罚因子Ⅰ：映射的底层节点或链路没有足够的资源。

（2）惩罚因子Ⅱ：映射的底层节点和链路有足够的资源，但是映射链路上的可用时隙不能满足频谱分配的约束。

这两种惩罚因子可以指导我们设计高效的动态透明VNE算法，见算法1。

2 动态透明虚拟

网络嵌入算法

在本部分，我们提出一个有效的算法来解决弹性光传输基础设施上的动态透明VNE。为了减轻惩罚因子Ⅰ，我们设计一个贪婪节点映射来考虑所有底层节点的本地信息。同时为了减轻惩罚因子Ⅱ，我们应用分层辅助图的方法在频谱分配约束下优化链路映射。我们称该算法为VNE-LINM-LAGLM，这是“带有基于节点映射的本地信息和基于链路映射的分层辅助图的VNE”的缩写。算法阐释了VNE-LINM-LAGLM的总体程序，其中node（·）函数返回图中的节点数量，|·|返回集合中元素的数目。

2.1 分层辅助图

在算法2中，18行描述了如何将底层网络转化成辅助图的一层的程序。具体而言，算法检查nr个连续时隙构成的频谱块在每个光纤链路是否可用。如果是，则该链路插入到辅助图的第i层，其中i是子载波时隙的起始索引号。在检查完所有的光纤链路后，该算法在构造层中搜索连通子图，并且根据它们的节点数目进行排序。一个连通子图是一个子图，在子图中任意两个节点通过路径连接，并且在超图中连接到没有额外的节点[14]。

2.2 节点映射和链路映射

算法2说明辅助图的构造层中的节点映射和链路映射的详细程序。

底层节点vs的本地信息包括其可用的计算能力[csvs]和节点度[dsvs]。注意到节点度[dsvs]源自所构造的分层图的单层，但不是来自原先的底层网络。我们定义第i层上一个底层节点的本地信息为公式（3）：

[ hsvs=csvsdsvs] （3）

其中，[dsvs]表示所构造的分层图的第i层的节点vs的节点度。直观地，更大的值[ hsvs]意味着节点vs有更大的嵌入潜力。

3 虚拟网络嵌入

算法性能评估

3.1 仿真配置

我们采用仿真来评估该算法，仿真实验使用两个底层网络拓扑，一个有14个节点和23个链路的实际的DT（Deutsche Telecom）[13]拓扑结构，另一个是由50个节点和141链路构成的大型随机生成的拓扑结构。随机生成的拓扑是由GT-ITM工具生成的[15]。我们设置每个节点的初始计算能力为200 units，并在底层网络的各个光纤链路分配200子载波时隙。虚拟光网络（VON）请求的到来遵循泊松（Poisson）流量模型，同时虚拟光网络的拓扑也是使用GT-ITM工具随机生成的。

为了评估该算法的性能，我们设计了两个参考算法。第一个参考算法借鉴了通常用于2/3层网络虚拟化计算动态VNE中本地信息的方法。具体而言，底层节点的本地信息是通过在所有的事件链路上它可用的计算能力与总的可用带宽（例如，未使用的子载波时隙的总数）的乘积计算的[16]。节点映射是基于它本地信息，链路映射使用最短路径路由和首次适应频谱分配直接将虚拟光链路嵌入到底层网络，没有构造分层的辅助图。我们称这个参考算法为“无分层链路映射的VNE参考”或VNE-REF-NLLM。基本上，VNE-REF-NLLM算法仿真我们直接应用开发用于2/3层网络虚拟化的VNE算法到我们案例的情况。第二个参考算法使用和第一个相同的方法计算本地信息，但是为链路映射构造了分层辅助图。我们称之为“分层链路映射的VNE参考”或VNE-REF-LLM。VNE-REF-LLM算法仿真我们认为在链路映射阶段O-OFDM物理层的独特性，但是仍然直接应用开发用于2/3层网络虚拟化的节点映射方案的情况。

3.2 DT拓扑仿真

使用DT拓扑仿真，一次虚拟光网络请求中的虚拟节点的数量是随机地从3和4中选取，并且每对节点以0.5的概率连接。每个虚拟节点的计算能力需求[crvr]是均匀分布在1～10 units之间，而每个虚拟光链路的带宽要求nr是随机地从1～10个时隙中选取。

使用DT拓扑的仿真结果如图2所示。图2（a）表明，VNE-LINM-LAGLM算法提供了3个算法中最低的阻塞概率。我们还观察到算法VNE-REF_LLM的阻塞概率仅稍低于VNE-REF_NLLM算法的阻塞概率。这个观察结果反映，本地信息计算方案通过分层方法将链路映射约束考虑在内，因为节点映射可能为弹性光传输基础设施上动态透明的VNE带来更低的阻塞概率。正如以前的工作[4，9]中解释的，物理层损伤（PLI）可以明显地影响光网络虚拟化的质量。因此，理想的是，为了减少的信号质量下降，我们以尽可能短的距离将虚拟光链路嵌入到底层路径。图2（b）比较了3个VNE算法底层路径的平均距离。可以看出，VNE-LINM-LAGLM算法趋向于以最短底层路径嵌入虚拟光链路来应对所有流量负载VNE-REF-NLLM和VNE-REF-LLM的平均距离分别为73%和68%）。算法VNE-LINM-LAGLM中平均路径距离大约313 km，这比500 Gb/s使用QPSK调制的O-OFDM超信道信号的典型传输距离要小得多[17]。

3.3 大型随机拓扑仿真

对于DT拓扑的规模，我们很难去仿真超过4个虚拟节点的虚拟光节点请求。为了进一步研究VNE-LINM-LAGLM算法的性能，我们在一个由50个节点组成的随机底层拓扑上仿真。

我们假设光纤链路的长度是相同的，都为50 km。一次虚拟光节点请求中的虚拟节点的数量随机地从2～10中选取，并且每对节点以0.5的概率连接。计算能力需求[crvr]是均匀分布在1～20 units之间，而每个虚拟光链路的带宽要求nr是随机地从1～20个时隙中选取。

使用随机拓扑仿真的结果如图3所示。图3（a）表明，VNE-LINM-LAGLM算法仍然达到最低的阻塞概率。在图3（b）中，有趣的是，观察到算法VNE-LINM-LAGLM中平均路径距离要比从算法VNE-REF-NLLM的平均路径距离要长，而且，它们不再是最短的。我们相信这种现象可作如下解释。与那些使用DT拓扑的比较，本次仿真平均生成更多的虚拟节点和虚拟光链路的虚拟光网络请求。因为在链路映射前它不执行频谱连续性检查，所以在本次仿真情景中，VNE-REF-NLLM算法在长的底层路径嵌入虚拟光链路有困难。通过阻塞概率验证的基本原理如图3（a）刻画，VNE-REF-LLM算法比VNE-REF-NLLM算法达到较大的阻塞性能增益。

4 结束语

我们提出了一个新的动态透明VNE算法，它同时考虑了节点映射和链路映射，用于弹性光传输基础设施上O-OFDM的网络虚拟化。仿真结果表明，该算法考虑了O-OFDM网络的独特性，优于两个直接应用用于2/3层或波分复用网络虚拟化的VNE方案的参考算法。

参考文献

[1] CHOWDHURY N， BOUTABA R. A survey of network virtualization [J]. Comput. Netw.， 2010，54（5）： 862-876.

[2] ARMSTRONG J. OFDM for optical communications [J]. Lightw. Technol.， 2009，27（3）：189-204.

[3] NEJABATI R， ESCALONA E， PENG S， et al. Optical network virtualization [C]// Proceedings of the ONDM， 2011， 2：1-5.

[4] JINNO M. Virtualization in optical networks： from elastic networking level to sliceable equipment level [C]// Proceedings of the COIN 2012， 3：61-62.

[5] ZERVAS G. Phosphorus grid-enabled GMPLS control plane （G2MPLS）： architectures， services， and interfaces [J]. IEEE Commun. Mag.， 2008，46（6）： 128-137.

[6] FIGUEROLA S， LEMAY M. Infrastructure services for optical networks [J]. Opt. Commun. Netw.， 2009，1（2）： 247-257.

[7] WANG Y. Virtual optical network services across multiple domains for grid applications [J]. IEEE Commun. Mag.， 2011，49（5）： 92-101.

[8] ZHANG S， SHI L， VADREVU C S K， et al. Network virtualization over WDM networks [C]// Proceedings of the ANTS11， 2011： 1-3.

[9] PENG S. An impairment-aware virtual optical network composition echanism for future internet [C]// Proceedings of the ECOC 2011， 2011，9：1-3.

[10] PENG S， NEJABATI R， AZODOLMOLKY S. Virtual optical network composition over single-line-rate and mixed-line-rate WDM optical networks [C]// Proceedings of the OFC 2012， 2012，3： 1-3.

[11] PAGES A， PERELLO J， SPADARO S， et al. Strategies for virtual optical network allocation [J]. IEEE Commun. Lett.， 2012，2： 268-271.

[12] PAGES A. Optimal allocation of virtual optical networks for the future internet [C]// Proceedings of the ONDM 2012， 2012，4： 1-6.

[13] GONG L， ZHOU X， LU W， et al. A two-population based evolutionary approach for optimizing routing， modulation and spectrum assignments （RMSA） in O-OFDM networks [J]. IEEE Commun. Lett.， 2012，16（9）： 1520-1523.

[14] Connected component （graph theory） [EB/OL]. （2014-02-11）. http：//en.wikipedia.org/wiki/Connected_component_（graph_theory）.

[15] ZEGURA E， CALVERT K， BHATTACHARJEE S. How to model an internetwork [C]// Proceedings of the INFOCOM 1996， 1996，5： 594-602.

[16] YU M. Rethinking virtual network embedding ： Substrate support for path splitting and migration [J]. SIGCOMM Comput. Commun. Rev.， 2008，28，（2）： 17-29.

[17] KLEKAMP A， DISCHLER R， BUCHALI F. Transmission reach of optical OFDM superchannels with 10-600 Gb/s for transparent bit-rate adaptive networks [C]// Proceedings of the ECOC11， 2011： 1-3.