期刊
COMPUTER JOURNAL
卷 60, 期 3, 页码 287-307出版社
OXFORD UNIV PRESS
DOI: 10.1093/comjnl/bxw063
关键词
graph pattern matching; cloud computing; virtual network mapping
类别
资金
- ERC [652976]
- 973 Program [2014CB340302, 2012CB316200, 2014CB340300]
- NSFC [61133002, 61421003, 61322207]
- EPSRC [EP/J015377/1, EP/M025268/1]
- Shenzhen Peacock Program [1105100030834361]
- Guangdong Innovative Research Team Program [2011D005]
- Beijing Advanced Innovation Center for Big Data and Brain Computing (BDBC)
- Shenzhen Science and Technology Fund [JCYJ20150529164656096]
- Guangdong Applied RD Program [2015B010131006]
- NSF III [1302212]
- Special Funds of Beijing Municipal Science & Technology Commission
- EPSRC [EP/J015377/1, EP/M025268/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/J015377/1, EP/M025268/1] Funding Source: researchfish
Virtual network mapping (VNM) is to build a network on demand by deploying virtual machines in a substrate network, subject to constraints on capacity, bandwidth and latency. It is critical to data centers for coping with dynamic cloud workloads. This paper shows that VNM can be approached by graph pattern matching, a well-studied database topic. (i) We propose to model a virtual network request as a graph pattern carrying various constraints, and treat a substrate network as a graph in which nodes and edges bear attributes specifying their capacity. (ii) We show that a variety of mapping requirements can be expressed in this model, such as virtual machine placement, network embedding and priority mapping. (iii) In this model, we formulate VNM and its optimization problem with a mapping cost function. We establish complexity bounds of these problems for various mapping constraints, ranging from polynomial time to NP-complete. For intractable problems, we show that their optimization problems are approximation-hard, i.e. NPO-complete in general and APX-hard even for special cases. (iv) We also develop heuristic algorithms for priority mapping, an intractable problem. (v) We experimentally verify that our algorithms are efficient and are able to find high-quality mappings, using real-life and synthetic data.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据