虚拟网络映射问题研究综述程祥，张忠宝，苏森，杨放春（北京邮电大学网络与交换技术国家重点实验室，北京100876）摘要：对虚拟网络映射问题的相关研究工作进行了充分调研，对现有的研究成果进行了深入分析，并且指出了已有研究工作中关键技术的优缺点。最后讨论了可以进一步研究的方向，为虚拟网络映射问题的研究提供参考。关键词：网络虚拟化；虚拟网络映射；高效；可靠：TP393文献标识码：A：1000-436X(2011)10-0143-09SurveyofvirtualnetworkembeddingproblemCHENGXiang,ZHANGZhong-bao,SUSen,YANGFang-chun(StateKeyLabofNetworkingandSwitching,Bei激ngUniversityofPostsandTelecommunications,Bei激ng100876,China)Abstract:Relatedresearchworkofvirtualnetworks(VN)embeddingwassurveyed,andbothoftheadvantagesanddis-advantagesinthekeytechnologiesofrelatedresearchworkwereanalyzed.ThepossiblefutureresearchdirectionswerealsodiscussedasreferencesfortheresearchofVNembeddingproblem.Keywords:networkvirtualization;virtualnetworkembedding;efficiency;reliability近年来网络虚拟化技术受到了工业界和学术界的广泛关注。网络虚拟化技术允许在共享的底层物理网络基础设施之上共存多重异构的虚拟网络。每一个虚拟网络是底层网络的一份资源片，它由虚拟节点（例如，虚拟路由器）和虚拟链路组成。此外，利用底层网络的可编程能力，虚拟网络可以在一个选定的拓扑结构中运行IP或非IP协议[3]。因此，网络虚拟化技术使在不影响现有网络的前提下部署新的网络架构、协议以及应用成为可能，从而有效地支持网络技术的创新。它不仅提供了一条由当前互联网向未来网络演进的可行途径，而且是未来互联网应具备的关键特性之一[4]。1引言互联网已成为支撑现代社会经济发展、社会进步和科技创新的重要信息基础设施，它的成功正深刻地改变着人们生产、生活和学习的方式。然而，当今以“尽力而为”作为服务模型的互联网在安全性、移动性和服务质量等方面均面临着严峻的技术挑战。由于互联网的巨大成功以及多重利益相关者在目标和策略方面的不同，应对上述挑战时多以修补的方式进行解决，这种思路严重阻碍了创新型的网络架构与技术的产生、部署和评估，从而很难在根本上解决当前互联网本身固有的问题[1,2]。收稿日期：2010-12-06；修回日期：2011-05-26基金项目：国家自然科学基金资助项目（61170274）；国家重点基础研究发展计划（“973”计划）基金资助项目（2011CB302506）；新一代宽带无线移动通信网工信部国家科技重大专项（2011ZX03002-001-01）；国家自然科学基金委创新研究群体基金资助项目（60821001）FoundationItems:TheNationalNaturalScienceFoundationofChina(61170274);TheNationalBasicResearchProgramofChina(973Program)(2011CB302506);ImportantNationalScienceTechnologySpecificProjects:Next-GenerationBroadbandWirelessMobileCommunicationsNetwork(2011ZX03002-001-01);InnovativeResearchGroupsoftheNationalNaturalScienceFoundationof·144·通信学报第32卷在网络虚拟化环境中，基础设施提供商管理运营底层网络，服务提供商可以向基础设施提供商租赁网络资源并创建虚拟网络，以提供个性化的端到端网络服务[5]。为服务提供商的带有节点和链路资源约束条件的虚拟网络请求分配基础设施提供商的底层网络资源的问题称为虚拟网络映射（嵌入、指派）问题。虚拟网络映射问题是NP难问题，即使在所有的虚拟节点已被映射后，映射带有带宽资源约束的虚拟链路仍然是NP难的。虚拟网络映射问题是网络虚拟化技术面临的主要挑战之一[6]，已经成为该研究领域的热点问题，受到了学者们的普遍关注。本文将对虚拟网络映射问题的相关研究工作进行深入分析，同时指出其优缺点，并对未来可能的研究方向进行探讨，为虚拟网络映射问题的研究提供参考。本文第2节对虚拟网络映射问题进行了描述并给出了其主要评价指标；第3节对现有的研究工作进行深入分析，并指出了其优缺点；第4节针对现有虚拟网络映射问题研究工作中的不足，探讨可以进一步研究的方向；第5节是结束语。2虚拟网络映...