虚拟网络映射问题是网络虚拟化研究中的核心问题之一, 其主要目标是将虚拟网络请求高效地映射到底层物理网络上.针对面向多拓扑类型请求的虚拟网络映射问题进行研究, 提出了节点连通性模型和通用底层物理网络节点评价模型用以判断节点映射的优先次序, 在此基础上设计了一种复合型虚拟网络映射算法, 在映射过程中通过识别虚拟网络请求的拓扑特征调用相应的映射子算法完成网络映射.仿真结果表明, 该复合型映射算法获得了较高的虚拟网络请求接受率和网络收益开销比, 整体上提高了虚拟网络映射性能.
As a core issue of network virtualization, virtual network embedding/mapping problem focus on allocate the virtual network requests onto the shared substrate network. Focusing on the virtual network embedding problem with multi-topology virtual network request, a node connectivity model and general substrate node measurement was proposed to rank the nodes in network. On the basic of node ranking, a new complex algorithm with topology recognition has been proposed, including several sub-algorithm for specific topology feature. The simulation results show that the complex algorithm improve the performance of embedding by increasing both the acceptance ratio of requests and revenue/cost ratio.
虚拟网络映射问题是网络虚拟化研究的关键内容之一，它的主要研究目标是在满足虚拟网络请求中节点和链路资源需求的同时，尽可能高效地将虚拟网络请求映射到底层物理网络设施上，并获得尽可能多的虚拟网络业务收益.
由于虚拟网络请求中虚拟节点和虚拟链路资源需求的约束，虚拟网络映射问题已被证明是一个NP-hard问题[1-4].因此，研究者主要通过设计启发式算法来解决该问题[2-9].受谷歌搜索引擎PageRank算法的启发，Cheng等[5-6]提出了利用基于节点间连接的马尔可夫随机漫步模型对网络中的节点进行重要性排序，优先映射与其他节点关联较多的节点，但是并未考虑节点间链路的带宽资源. Wang等[7]首次将接近中心性的概念引入虚拟网络映射问题，并基于不同的接近中心性模型提出了2种虚拟网络映射算法.以上的研究工作中，虚拟网络请求的拓扑结构都是随机生成的.然而，在实际的商业系统中，服务提供商经常会构建各类特定拓扑类型的虚拟网络请求以部署相应的网络服务.例如，视频会议系统通常采用星形拓扑，而组播系统则多采用树形拓扑结构.当虚拟网络请求到达时，基础服务商可以轻易获得虚拟网络请求的拓扑特征.因此，基于虚拟网络请求的不同拓扑特征提出对应算法，将可能实现更优的虚拟网络映射方案.
针对面向多拓扑类型的虚拟网络请求，笔者提出一种复合型虚拟网络映射算法.该算法包括4个子算法，分别对应处理树形拓扑、星形拓扑、环形拓扑以及随机拓扑的虚拟网络请求.当一个虚拟网络请求到达时，复合型算法首先识别其拓扑特征，然后调用相应的子算法进行映射处理.仿真结果表明，提出的复合型虚拟网络映射算法在多拓扑环境中提高了虚拟网络请求接受率和网络收益开销比，整体上显著提高了虚拟网络映射性能.
1 网络模型与问题研究1.1 网络模型采用文献[4-7]中的网络模型，物理网络由一个加权无向图Gs=(Ns, Es, Cs, Bs)表示，其中Ns为底层网络中的物理节点集合，Es为底层网络中的链路集合，Cs为物理节点的CPU资源，Bs为物理链路的带宽资源.
虚拟网络请求同样表示为一个加权无向图Gv=(Nv, Ev, Cv, Bv)，其中Nv为虚拟网络请求中的节点集合，Ev为虚拟网络请求中的链路集合，Cv为请求中节点所需的CPU资源，Bv为请求中所需的链路带宽资源.
1.2 优化目标与文献[2-4]类似，将一个虚拟网络请求成功映射后的收益定义为
|
(1) |
其中：CBW为虚拟链路ev所需的带宽资源，CCPU为虚拟节点nv所需的CPU资源.
一个虚拟网络被成功映射的开销需要根据它所实际占用的物理CPU资源和链路带宽资源计算，映射开销定义为
|
(2) |
其中：h(ev)为虚拟链路ev所映射到的物理路径的跳数.值得注意的是，所映射的物理路径上经过的中间节点的转发CPU消耗由带宽资源和跳数体现.
物理网络收益开销比用来衡量虚拟网络映射算法的效率，它定义为
|
(3) |
所提出的面向多拓扑类型请求的虚拟网络映射算法是一个复合型2部式映射算法，包括节点映射和链路映射2部分.为了在系统中实现接入控制功能，在算法中采用文献[4]所使用的时间窗口模型进行映射，按照一定的时间窗对虚拟网络请求进行映射处理.当一个虚拟网络请求到达系统时，复合型算法首先识别请求的拓扑特征并调用相应的子映射算法进行节点映射，然后使用kth最短路径算法进行虚拟链路映射[3].提出的映射算法的整体框架如下：
1. 将虚拟网络请求按照其收益依次递减排序
2. for队列中的虚拟网络请求依次do
3. 识别虚拟网络请求的拓扑特征并调用相应的子算法进行节点映射
4. if失败
5. return节点映射失败
6. end if
7. for请求中的每条虚拟链路do
8. 使用kth最短路径算法搜寻物理路径
9. if找到符合条件的物理路径
10. 将虚拟链路映射到所选物理路径
11. return映射成功
12. else
13. return映射失败
14. end for
15. end for
2.2 通用底层物理网络节点评价模型已有的研究[1-5]通过计算物理节点本地资源CL来衡量待选物理节点的优先次序，CL具体定义为
|
(4) |
其中：CCPU(n)为节点n的CPU资源，L(n)为与节点n直接相连的链路集合，CBW(l)为链路l的带宽资源.
为了更加合理地衡量节点间的连接关系，首先设计了物理拓扑中节点间连通性计算模型Ccon，不同于已有研究仅通过节点间最短路径跳数判断节点间的连接关系，该模型基于节点间路径距离和可用带宽资源共同计算节点间连接性，具体定义为
|
(5) |
其中：Path(ni, nj)为节点ni和nj之间的路径集合，Cdis(p)和CBW(p)分别为路径p的跳数和可用带宽资源.若ni和nj为同一节点，则Ccon(ni, nj)值为0.获得最大Ccon(ni, nj)值的路径将作为节点ni和nj之间的最短参考路径，并用以表征节点ni和nj的连通性.
在以上工作的基础之上，设计的通用底层物理网络节点评价模型Nsubstrate具体定义为
|
(6) |
其中：CL(ns)为底层物理节点ns的本地资源，N(ns)为除ns之外其他物理节点的集合，CCPU(ni)和Ccon(ns, ni)分别为节点ni的CPU资源及其同ns之间的连通性.这样，具有较高本地物理资源且更容易同其他节点建立连接以承载虚拟链路的物理节点将获得更高的Nsubstrate值，并将被优先选择进行虚拟节点的映射.值得注意的是，所提出的节点连通性和通用底层物理网络节点评价模型，其核心思想是根据网络中节点CPU资源、节点间路径长度以及链路带宽等拓扑属性对节点优先次序的判断，将模型中可用物理资源替换为相应的虚拟网络资源需求同样适用于虚拟网络请求的相关处理.
2.3 星形拓扑子算法在星形拓扑的虚拟网络请求中，所有的通信流量均要经过中心节点，因此中心节点应作为最重要的节点首先映射.剩余的边缘节点根据其与中心节点间虚拟链路的带宽需求按递减次序依次进行映射.
在映射过程中，首先为中心节点选择获得最大Nsubstrate值(见式(6))的物理节点作为承载节点进行映射.然后，针对虚拟边缘节点，将剩余物理节点按照其本地物理资源和与中心节点承载节点间的连通性进行排序，具体定义为
|
(7) |
其中：nj为虚拟网络请求中中心节点的物理承载节点，Ccon(ni, nj)为物理节点ni和nj之间的连通性，CL(ni)为物理节点ni的本地资源.在依次映射虚拟网络请求中边缘节点的过程中，容易与中心节点承载节点建立连接的物理节点将获得较高的Rstar值，并被优先选择.
2.4 树形拓扑子算法根据树形拓扑虚拟网络请求这种分层式的拓扑结构，应该优先映射较高层次的虚拟节点.对于同一层次内的虚拟节点，根据其各自子节点的情况定义了节点排序模型Rvtree进行排序并依次映射，具体定义为
|
(8) |
其中：Nchild(nv)为树形拓扑中虚拟节点nv的子节点集合.
在映射过程中，首先为层级最高的根节点选择获得最大Nsubstrate值(见式(6))的物理节点作为承载节点进行映射.然后，针对其他虚拟节点，将其他剩余物理节点在2.2节所提出的通用评价模型的基础上进行排序.树形拓扑请求条件下，物理节点排序模型Rtrees的具体定义为
|
(9) |
值得一提的是，通过定义变量k来强调正在映射的虚拟节点与其父节点之间的连接关系，当物理节点ni已被选为映射节点的父节点的承载节点时k取值为1，否则为0.
2.5 环形拓扑子算法根据环形拓扑类型虚拟网络请求的拓扑特征，所有虚拟节点应该按照其本地资源需求CL(见式(4))依次进行映射.
在2.2节所提出的通用评价模型的基础上，针对环形拓扑类型的虚拟网络请求，将物理节点排序模型Rrings定义为
|
(10) |
类似于2.4节中的树形拓扑子算法，本节通过定义变量m来强调正在映射的虚拟节点与其邻居节点的连接关系，当物理节点ni已被选为映射节点的邻居节点的承载节点时m取值为1，否则为0.
2.6 随机拓扑子算法如果到达的虚拟网络请求不符合以上3种拓扑类型，随机拓扑子算法将作为默认算法完成请求映射过程.由于不确定虚拟网络请求的拓扑结构，按照2.2节提出的通用节点评价模型Nsubstrate计算相应的虚拟资源，将请求中的虚拟节点进行排序并依次映射.底层物理节点的排序模型定义为
|
(11) |
其中：通过定义变量x来强调正在映射的虚拟节点与已完成映射的虚拟节点之间的连接关系，当物理节点ni已被选为某个虚拟节点的承载节点时，x取值为1，否则为0.
3 性能评估与分析3.1 仿真环境设置基于文献[4]给出的虚拟网络映射仿真环境进一步完善拓展，进行仿真实验.物理网络拓扑采用GT-ITM工具生成.物理网络包括100个节点和500条链路，节点的CPU和链路带宽均以50~100的均匀分布随机产生.每个虚拟网络请求中的节点个数按2~10均匀分布.每100个时间单位内到达的虚拟网络请求服从均值为5的泊松分布，所有虚拟网络的服务时间服从均值为1 000个时间单位的指数分布.虚拟网络请求中虚拟节点的CPU需求服从0~50的均匀分布，虚拟链路的带宽需求服从0~bmax 的均匀分布.设定bmax 从10增大到90以验证映射算法在不同带宽资源需求条件下的整体表现，每种条件下实验运行5万个时间单位并取平均值作为数据结果.根据虚拟网络请求的生存时间，实验运行1万个时间单位后将达到稳定状态，因此50 000个时间单位的运行时间将保证所取得的数据为稳定状态下的实验结果.
为了衡量映射算法的整体表现，从虚拟网络请求接受率、网络收益开销比2个方面对表 1中的4种虚拟网络映射算法进行了对比分析.
|
表 1 算法比较 |
1) 星形拓扑虚拟网络请求
仿真中所有到达的虚拟网络请求按照星形拓扑生成.星形拓扑虚拟网络请求接受率如图 1所示.Complex算法平均接受率为0.825 8，相对于RW算法(平均值0.780 8)，提高了约5.8%；相对于IC算法(平均值0.788 8)，提高了约4.7%；相对于Greedy算法(平均值0.751 7)，提高了约9.9%.由此可见，所提出的复合型算法根据星形拓扑的拓扑特征进行节点映射，有助于后续虚拟链路的成功映射，从而提高了虚拟网络请求被成功映射的几率.
|
图 1 星形拓扑虚拟网络请求接受率 |
星形拓扑虚拟网络请求网络收益开销比如图 2所示. Complex算法平均收益开销比为0.744 9，相对于RW算法(平均值0.676 1)，提高了约10.2%；相对于IC算法(平均值0.666 5)，提高了约11.8%；相对于Greedy算法(平均值0.547 5)，提高了约36.1%.
|
图 2 星形拓扑虚拟网络请求网络收益开销比 |
2) 树形拓扑虚拟网络请求
仿真中所有到达的虚拟网络请求按照树形拓扑生成.树形拓扑虚拟网络请求接受率如图 3所示. Complex算法平均接受率为0.842 0，相对于RW算法(平均值0.779 9)，提高了约8.0%；相对于IC算法(平均值0.753 9)，提高了约11.7%；相对于Greedy算法(平均值0.650 9)，提高了约29.3%.
|
图 3 树形拓扑虚拟网络请求接受率 |
树形拓扑虚拟网络请求网络收益开销比如图 4所示. Complex算法平均收益开销比为0.791 6，相对于RW算法(平均值0.732 8)，提高了约8.0%；相对于IC算法(平均值0.719 3)，提高了约10.1%；相对于Greedy算法(平均值0.675 9)，提高了约17.1%.
|
图 4 树形拓扑虚拟网络请求网络收益开销比 |
3) 环形拓扑虚拟网络请求
仿真中所有到达的虚拟网络请求按照环形拓扑生成.环形拓扑虚拟网络请求接受率如图 5所示. Complex算法平均接受率为0.833 8，相对于RW算法(平均值0.807 3)，提高了约3.3%；相对于IC算法(平均值0.784 6)，提高了约6.3%；相对于Greedy算法(平均值0.728 4)，提高了约14.5%.
|
图 5 环形拓扑虚拟网络请求接受率 |
环形拓扑虚拟网络请求网络收益开销比如图 6所示. Complex算法平均收益开销比为0.738 2，相对于RW算法(平均值0.693 9)，提高了约6.4%；相对于IC算法(平均值0.661 5)，提高了约11.6%；相对于Greedy算法(平均值0.586 7)，提高了约25.8%.
|
图 6 环形拓扑虚拟网络请求网络收益开销比 |
4) 随机拓扑虚拟网络请求
仿真中所有到达的虚拟网络请求的拓扑均随机生成，虚拟节点间相互连接的概率为0.5.随机拓扑虚拟网络请求接受率如图 7所示. Complex算法平均接受率为0.838 2，相对于RW算法(平均值0.787 3)，提高了约6.5%；相对于IC算法(平均值0.770 1)，提高了约8.8%；相对于Greedy算法(平均值0.719 9)，提高了约16.4%.
|
图 7 随机拓扑虚拟网络请求接受率 |
随机拓扑虚拟网络请求网络收益开销比如图 8所示. Complex算法平均收益开销比为0.743 8，相对于RW算法(平均值0.695 6)，提高了约6.9%；相对于IC算法(平均值0.681 5)，提高了约9.1%；相对于Greedy算法(平均值0.589 6)，提高了约26.2%.
|
图 8 随机拓扑虚拟网络请求网络收益开销比 |
虚拟网络映射问题是网络虚拟化研究的核心内容之一.由于实际商业系统中基础设施服务商可以轻易获得虚拟网络请求的拓扑特征信息，提出了一种面向多拓扑类型请求的虚拟网络映射算法.该算法包括4个子算法，分别对应星形拓扑、树形拓扑、环形拓扑以及随机拓扑类型虚拟网络映射请求的映射处理.当虚拟网络请求到达后，复合型算法首先识别其拓扑特征，并调用相应的子算法进行映射.仿真结果表明，所提出的复合型算法增加了虚拟网络请求接受率和网络收益开销比，整体提高了虚拟网络映射的性能表现.
现有研究的拓扑类型仍比较有限，下一步将针对更多的拓扑结构提出相应的映射算法，并在链路映射阶段的优化问题上进行进一步深入研究.
| [1] | Ricci R, Alfeld C, Lepreau J. A solver for the network testbed mapping problem[J].ACM SIGCOMM Computer Communication Review, 2003, 33(2): 65–81. doi: 10.1145/956981 |
| [2] | Zhu Yong, Ammar M H. Algorithms for assigning substrate network resources to virtual network components[C]//Proc. IEEE INFOCOM. Barcelona, Spain: IEEE, 2006: 1-12. |
| [3] | Fan Jingliang, Ammar M H. Dynamic topology configuration in service overlay networks: a study of reconfiguration policies[C]//Proc. IEEE INFOCOM. Barcelona, Spain: IEEE, 2006: 1-12. |
| [4] | Yu Minlan, Yi Yung, 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. doi: 10.1145/1355734 |
| [5] | Cheng Xiang, Su Sen, Zhang Zhongbao, et al. Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review, 2011, 41(2): 38–47. doi: 10.1145/1971162 |
| [6] | Cheng Xiang, Su Sen, Zhang Zhongbao, et al. Virtual network embedding through topology awareness and optimization[J].Computer Networks, 2012, 56(6): 1797–1813. doi: 10.1016/j.comnet.2012.01.022 |
| [7] | Wang Zihou, Han Yanni, Lin Tao, et al. Virtual network embedding by exploiting topological information[C]//Proc IEEE GLOBECOM. Anaheim, CA: IEEE, 2012: 2603-2608. |
| [8] |
刘光远, 苏森. 面向底层单节点失效的轻量级可靠虚拟网络映射算法[J]. 电子与信息学报, 2013, 35(11): 2644–2649.
Liu Guangyuan, Su Sen. Less stringent reliable virtual network mapping algorithm for substrate single node failure[J].Journal of Electronics and Information Technology, 2013, 35(11): 2644–2649. |
| [9] |
王颖, 熊文成, 李文璟. 基于最大独立链路集的随机虚拟网络映射算法[J]. 北京邮电大学学报, 2014, 37(S1): 8–11.
Wang Ying, Xiong Wencheng, Li Wenjing. Random virtual network embedding algorithm based on maximum independent link set[J].Journal of Beijing University of Posts and Telecommunications, 2014, 37(S1): 8–11. |