摘要：本研究在K短路径理论的思想指导下，结合现有的映射运算方法，对链路映射过程进行改进，算法经过反复的K路径搜索， 寻求能够满足虚链路带宽的最佳途径，从而大大提高虚链路的有效映射率。与此同时，实验在节点映射过程中，利用虚拟网映射的特点，探索出了物理节点可重复映射的映射算法。
　　关键词：K短路径；虚拟网；映射算法
　　1 虚拟网模型以及相关问题
　　1.1虚拟网的网络模型
　　虚拟网模型可以用GV=（VV，EV），每个物理节点vv∈VV都与相应的资源需求C（vv），代表在节点处需要的物理资源。与此相同，每条物理链路ev∈EV，也对应着一个资源需求W（ev）。位于图一的右半部分代表的是一个物理网实例，节点周围的数值代表此节点的计算力资源C（VS），标注在链路上的数值表示该链路的宽带W（es），图片左边代表2个虚拟网的具体请求实例。
　　1.2映射过程的描述与计算
　　2 物理节点可重复的虚拟网映射算法
　　2.1 基于K短路径的映射算法
　　算法一：假定K=1，VA = φ；根据上述公式对AR（vs）进行运算，并在其最大值的节点处加入VA；一招虚拟网节点数目n，在集合Vs -VA中对前n-1小的π（v）进行计算，并把节点v 加入到对应的VA；按照AR对VA中的节点進行排序；对Vv按照节点度数排序。最后按照顺序映射VA和Vv中的节点；在物理网中寻找符合带宽要求的递增K 短路径，进行虚链路映射。
　　3实验结果以及分析
　　实验发现K短路径策略和节点反复映射策略呗可以有效提高虚拟网的映射效率，特别是在虚拟网资源需求相对较小、节点规模适中以及链路高度密集的情况下，节点重复映射策略更能发挥其巨大优势。
　　4 结语
　　随着网络信息化水平的不断发展，虚拟化技术在解决互联网“骨化”方面发挥着越来越重要的作用，鉴于虚拟网映射在网络虚拟化过程中的基础作用，本文在传统算法的基础上结合K短路径思想，对链路映射过程进行改进，确保链路映射的成功率，从而达到降低映射时间和节约物理网映射成本，从而为更多虚拟网映射创造条件的目的。
　　参考资料
　　[1] 姜明，王保进，吴春明，孔祥庆，闵啸，张旻. 网络虚拟化与虚拟网映射算法研究[J]. 电子学报. 2011（06）
　　[2] 李文，吴春明，陈健，平玲娣. 物理节点可重复映射的虚拟网映射算法[J]. 电子与信息学报. 2011（04）
　　[4] 齐宁，王保进，汪斌强，张栋. 均衡虚拟网构建算法研究[J]. 电子与信息学报. 2011（06）
　　[5] 张顺利，邱雪松，潘亚莲，孟洛明. 网络虚拟化环境下基于预测的资源重配置算法[J]. 通信学报. 2011（07）
　　[4] 吕博，杨帆，王振凯，陈建亚，刘韵洁. 一种基于区域划分的虚拟网映射新算法[J]. 电子与信息学报. 2011（10）