基于成本约束的虚拟网映射策略及竞争分析

余建军; 吴春明

doi:10.3969/j.issn.1000-0801.2016.02.007

您当前的位置：

首页 >

文章列表页 >

基于成本约束的虚拟网映射策略及竞争分析

研究与开发 | 更新时间：2024-06-05

- 基于成本约束的虚拟网映射策略及竞争分析
- Virtual network mapping strategy and competitive analysis based on cost constraint
- 电信科学 2016年32卷第2期页码：47-54
- 作者机构：
  
  1. 衢州职业技术学院，浙江衢州 324000
  2. 浙江大学计算机科学与技术学院，浙江杭州 310027
- 作者简介：
  
  [ "余建军（1969-），男，衢州职业技术学院信息工程学院院长、教授，主要研究方向为算法设计与分析、网络虚拟化、光网络、无线传感器网络等。" ]
  [ "吴春明（1967-），男，博士，浙江大学教授、博士生导师，主要研究方向为互联网体系结构、可重构网络、软件定义网络、网络虚拟化和网络安全技术等。" ]
- 基金信息：
  
  浙江省自然科学基金资助项目;Zhejiang Provincial Natural Science Foundation of China(LY14F020010);国家自然科学基金资助项目;The National Natural Science Foundation of China(61379118);国家高技术研究发展计划（“863”计划）基金资助项目;The National High Technology Research and Development Program of China（863 Program）(2015AA016103)
- DOI：10.3969/j.issn.1000-0801.2016.02.007
  中图分类号： TP393
- 网络出版日期：2016-02，
  
  纸质出版日期：2016-02-15
- 稿件说明：
移动端阅览
余建军, 吴春明. 基于成本约束的虚拟网映射策略及竞争分析[J]. 电信科学, 2016,32(2):47-54.

Jianjun YU, Chunming WU. Virtual network mapping strategy and competitive analysis based on cost constraint[J]. Telecommunication science, 2016, 32(2): 47-54.
余建军, 吴春明. 基于成本约束的虚拟网映射策略及竞争分析[J]. 电信科学, 2016,32(2):47-54. DOI： 10.3969/j.issn.1000-0801.2016.02.007.

Jianjun YU, Chunming WU. Virtual network mapping strategy and competitive analysis based on cost constraint[J]. Telecommunication science, 2016, 32(2): 47-54. DOI： 10.3969/j.issn.1000-0801.2016.02.007.

摘要

为实现物理网提供商长期收益的最大化，单个虚拟网的映射成本和接入控制策略最为关键，但在之前的研究中，资源价格定义不能反映资源供求关系，不利于物理网资源的有效利用，且接入控制策略没有综合考虑成本和收益的关系。为此，首先基于凸二次规划松弛方法，设计以映射成本最小化为目标的单虚拟网映射方案求解的近似算法；然后，针对动态到达的单虚拟网构建请求，基于影子价格的物理网资源定价策略，用上述近似算法求出映射方案，并基于映射成本约束的虚拟网接入控制策略，完成竞争算法设计，并给出算法的竞争比分析。实验表明，所提方法能使物理网资源得到有效利用，进而提高虚拟网构建请求的接受率和物理网提供商的长期收益。

Abstract

The approximation algorithm of single virtual network mapping solution aimed to minimize the mapping cost based on convex quadratic programming relaxation was designed. Then aiming for dynamic arrival construction request of the single virtual network，the mapping scheme was achieved based on physical network resource pricing strategy by shadow price，applying above-mentioned approximation algorithm. And then completed the competitive algorithm design based on virtual network admission control strategy by mapping cost constraint and provided the competitive analysis of this algorithm. Experiment results show that the proposed algorithm increases the effective utilization of physical network resources，hence it can improve the virtual network construction request acceptance ratio and the long-term profit of physical network service provider.

关键词

Keywords

references

FISCHER A ， BOTERO J F ， BECK M T ， et al . Virtual network embedding：a survey [J ] . IEEE Communications Surveys and Tutorials ， 2013 ， 15 （ 4 ）： 1888 - 1906 .

YU M ， YI Y ， REXFORD J ， et al . Rethinking virtual network embedding：substrate support for path splitting and migration [J ] . ACM SIGCOMM on Computer Communication Review ， 2008 ， 38 （ 2 ）： 17 - 29 .

EVEN G ， MEDINA M ， SCHAFFRATH G ， et al . Competitive and deterministic embeddings of virtual networks [J ] . Theoretical Computer Science ， 2013 （ 496 ）： 184 - 194 .

李文，吴春明，陈健，等 . 物理节点可重复映射的虚拟网映射算法 [J ] . 电子与信息学报， 2011 ， 33 （ 4 ）： 908 - 914 .

LI W ， WU C M ， CHEN J ， et al . Virtual network mapping algorithm with repeatable mapping over substrate nodes [J ] . Journal of Electronics＆Information Technology ， 2011 ， 33 （ 4 ）： 908 - 914 .

余建军，吴春明 . 支持接入控制的虚拟网映射近似算法 [J ] . 电子与信息学报， 2014 ， 36 （ 5 ）： 1235 - 1241 .

YU J J ， WU C M . Virtual network mapping approximation algorithm with admission control [J ] . Journal of Electronics ＆Information Technology ， 2014 ， 36 （ 5 ）： 1235 - 1241 .

CHOWDHURY M ， RAHMAN M R ， BOUTABA R ， . ViNEYard：virtual network embedding algorithms with coordinated node and link mapping [J ] . IEEE/ACM Transactions on Networking ， 2012 ， 20 （ 1 ）： 206 - 219 .

李小玲，郭长国，李小勇，等 . 一种基于约束优化的虚拟网络映射方法 [J ] . 计算机研究与发展， 2012 ， 48 （ 9 ）： 1601 - 1610 .

LI X L ， GUO C G ， LI X Y ， et al . A constraint optimization based mapping method for virtual network [J ] . Journal of Computer Research and Development ， 2012 ， 48 （ 9 ）： 1601 - 1610 .

NONDE L ， EL-GORASHI T E H ， ELMIRGHANI J M H . Energy efficient virtual network embedding for cloud networks [J ] . Journal of Lightwave Technology ， 2014 ， 33 （ 9 ）： 1 .

JENS L ， HOLGER K ， YU F R . A virtual network mapping algorithm based on subgraph isomorphism detection [C ] // The 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures ， August 17 ， 2009 ， Barcelona，Spain . New York ： ACM Press ， 2009 ： 81 - 88 .

HU Q ， WANG Y ， CAO X . Resolve the virtual network embedding problem：a column generation approach [C ] // The IEEE Conference on Computer Communications ， April 14 - 19 ， 2013 ， Turin，Italy . New Jersey ： IEEE Press ， 2013 ： 410 - 414 .

BOTERO J F ， HESSELBACH X ， DUELLI M ， et al . Energy efficient virtual network embedding [J ] . IEEE Communications Letters ， 2012 ， 16 （ 5 ）： 756 - 759 .

ZHAO J Z ， SUBRAMANIAM S ， BRANDT-PEARCE M . Virtual topology mapping in elastic optical [C ] // The IEEE International Conference on Communications（ICC）， June 9 - 13 ， 2013 ， Budapest，Hungary . New Jersey ： IEEE Press ， 2013 ： 3904 - 3908 .

李铭夫，毕经平，李忠诚 . 资源调度等待开销感知的虚拟机整合 [J ] . 软件学报， 2014 ， 25 （ 7 ）： 1388 - 1402 .

LI M F ， BI J P ， LI Z C ， . Resource-scheduling-waiting-aware virtual machine consolidation [J ] . Journal of Software ， 2014 ， 25 （ 7 ）： 1388 - 1401 .

余恕莲，吴革 . 企业成本理论与方法研究 [M ] . 北京：中国社会科学出版社， 2010 ： 32 - 44 .

YU S L ， WU G . A Study on Enterprise Cost Theory and Its Methods [M ] . Beijing ： China Social Sciences Press ， 2010 ： 32 - 44 .

KLEINBERG J M . Approximation Algorithms for Disjoint Paths Problems [M ] . Cambridge：Massachusetts Institute of Technology ， 1996 ： 11 - 12 .

KUSIAK A ， FINKE G . Selection of process plans in automated manufacturing systems [J ] . IEEE Journal of Robotics and Automation ， 1988 ， 4 （ 4 ）： 397 - 402 .

岑燕斌，韦煜，罗会亮 . 快速判断一类实对称矩阵正定的极大极小元方法 [J ] . 北京交通大学学报， 2011 ， 35 （ 6 ）： 140 - 143 .

CEN Y B ， WEI Y ， LUO H L . Max and mini-elements method：a rapid determination of one class rear symmetric positive definite matrices [J ] . Journal of Beijing Jiaotong University ， 2011 ， 35 （ 6 ）： 140 - 143 .

MONTEIRO R D C ， ADLERIRO I . Interior path following primal-dual algorithms [J ] . Mathematical Programming ， 1989 ， 44 （ 1 ）： 43 - 66 .

浏览量

475

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据