陈 晨，郑 烇，王志臻，田洪亮

(1. 中国科学技术大学 信息科学技术学院，安徽 合肥 230027； 2. 中兴通讯股份有限公司，广东 深圳 518057)

0 引言

随着网络技术的发展，为了解决当前互联网“僵化”问题，研究者提出了网络虚拟化技术，它可以为用户提供多样化服务[1-2]，也是构建新一代网络体系架构的重要支撑[3]。虚拟网络映射是实现网络虚拟化的关键环节，其目的是在满足虚拟网络请求(Virtual Network Request, VN请求)的前提下，将虚拟网络以最小化成本映射到物理网络上，实现网络资源的高效利用[4]。

虚拟网络映射问题包括节点映射和链路映射两个问题，一般在节点映射阶段采用启发式算法，然后在确定源和目的节点的基础上，将链路映射转化为最小费用流问题，采用最短路径算法完成映射。根据两个问题是否独立进行，可将虚拟网络映射分为同阶段映射和两阶段映射[5]。同阶段映射中，在映射虚拟节点的同时考虑链路映射，如D-ViNE算法[6]和vnmFlib算法[7]。两阶段映射中，节点映射和链路映射独立进行，先映射节点后映射链路，如NA-PVNM算法[8]。

在已有的研究中，VN请求大都是对节点计算资源和链路带宽资源的需求。本文研究的是将含有文件需求的VN请求映射到有存储的物理网络上，VN请求不仅包括以上的需求，还包括对节点存储资源的需求。因为物理节点上可能存在请求文件的存储，所以当请求命中时，该节点流向下游的流量减少。该情况可以转化为节点的损耗问题，即广义最小费用流问题[9]。本文提出了一种基于节点连通性和广义网络单纯形法的虚拟网络映射算法——S-VNM算法，在节点映射阶段综合考虑节点位置和链路映射的映射成本两个因素，从而减小搜索空间，降低映射成本。……