一种虚拟路由器资源映射算法研究

计算机工程与科学

一种虚拟路由器资源映射算法研究

曹杨，王宝生，张晓哲

（国防科学技术大学计算机学院,湖南长沙 410073）

收稿日期:2015-07-31 修回日期:2015-10-10 出版日期:2016-10-25 发布日期:2016-10-25
基金资助:
国家重大基础研究（973计划）可重构信息通信基础网络模拟仿真实验平台、XXX接入认证和授权协议标准研究

A virtual router resource mapping algorithm

CAO Yang，WANG Baosheng，ZHANG Xiaozhe

（College of Computer,National University of Defense Technology,Changsha 410073,China）

Received:2015-07-31 Revised:2015-10-10 Online:2016-10-25 Published:2016-10-25

摘要/Abstract

摘要：

网络虚拟化技术的提出，为解决互联网“僵化”问题找到了新的思路，受到广泛的关注。在虚拟路由器平台中，若干台互联的网络服务器资源组成了底层物理网络，通过虚拟网络映射技术，将物理网络资源有效地映射到虚拟网络设备上，组成多个虚拟网络，满足用户对网络的多样化需求。虚拟路由器资源映射问题是虚拟网络映射问题的基础，虚拟路由器实例与物理资源的映射方法决定了虚拟网络平台资源的利用率和虚拟网络系统的性能。针对虚拟路由器平台资源分配的问题，提出了物理网络资源模型和虚拟路由器资源请求模型，设计了一种启发式虚拟路由资源分配算法，并对算法的复杂性和优化目标进行了分析。

关键词: 网络虚拟化, 网络资源模型, 虚拟路由器资源请求模型, 启发式资源分配算法

Abstract:

Network virtualization technology has attracted many attentions since it was proposed to provide a method to solve the ossification of Internet structure. On the platform of virtual routers, many servers connect with each other as a physical network. Mapping physical network resources to virtual network devices through the virtual network mapping technology can form many virtual networks and meet various needs of users. The resource allocation of virtual routers is a fundamental issue of network virtualization. The utilization rate of virtual network resources and the performance of the system are largely defined by the mapping method between virtual routers instances and physical resources. Aiming at the problem of resource allocation in the virtual router system, we design a physical network resource model and a virtual router resource quest model. We also propose a heuristic algorithm to solve the resource allocation problem, and then analyze the complexity of the algorithm and the utilization of physical resources.

Key words: network virtualization, network resource model, virtual router resource quest model, heuristic resource allocation algorithm

曹杨，王宝生，张晓哲. 一种虚拟路由器资源映射算法研究[J]. 计算机工程与科学.

CAO Yang，WANG Baosheng，ZHANG Xiaozhe. A virtual router resource mapping algorithm[J]. Computer Engineering & Science.

参考文献

［1］Anderson T, Peterson L. Overcoming the Internet impasse through virtualization ［J］.IEEE Computer Magazine,2005,38(4):3441.

［2］Liu Guangyuan,Su Sen.Less stringent reliable virtual network mapping algorithm for substrate single node failure ［J］.Journal of Electronics & Information Technology,2013,35（11）:26442649.（in Chinese）

［3］Zuo Cheng,Yu Hongfang.Reliabilityaware virtual data center embedding algorithm［J］.Journal of Computer Applications,2015,35（2）:299304.（in Chinese）

［4］Xu Qian.Research on node importance based virtual network mapping algorithm ［D］.Hefei:Anhui University,2014.（in Chinese）

［5］Wang Zhiming,Wang Binqiang,Wang Baojin.Virtual network reliable mapping scheme based on topology impact degree and backtracking migration ［J］.Journal of Electronics ＆ Information Technology, 2012,34（12）:28982904.（in Chinese）

［6］Chen Chunkai. Research on topology awarebased virtual network mapping in cloud computing environment［J］.Computer Application and Software,2014
,31（12）:156160.（in Chinese）

［7］Shachnai H,Tamir T,Yehezkely O.Approximation schemes for packing with item fragmentation ［J］.Theory of Computing Systems，2008,43(1):8198.

［8］Coffman E G, Garey M R,Johnson D S.Approximation algorithms for bin packing:A survey［M］∥Hochbaum D S,editor,Approximation Algorithms for NPHard Problems.
Boston:PWS Publishing,1997:4693.

附中文参考文献：

［2］刘光远,苏森.面向底层单节点失效的轻量级可靠虚拟网络映射算法［J］.电子与信息学报,2013,35（11）:26442649.

［3］左成，虞红芳.可靠性感知下的虚拟数据中心映射算法［J］.计算机应用,2015,35（2）:299304.

［4］许倩.基于节点重要性虚拟网络映射算法研究［D］.合肥：安徽大学,2014.

［5］王志明,汪斌强,王保进.基于拓扑影响度和回溯迁移的虚拟网可靠性映射方案［J］.电子与信息学报,2012,34（12）:28982904.

［6］陈春凯.云计算环境下基于拓扑感知的虚拟网络映射研究［J］.计算机应用与软件,2014,31（12）:156160.