Edinburgh Research Explorer

Virtual Network Mapping: A Graph Pattern Matching Approach

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dx.doi.org/10.1007/978-3-319-20424-6_6
Original languageEnglish
Title of host publicationData Science
Subtitle of host publication30th British International Conference on Databases, BICOD 2015, Edinburgh, UK, July 6-8, 2015, Proceedings
EditorsSebastian Maneth
PublisherSpringer International Publishing
Pages49-61
Number of pages13
ISBN (Electronic)978-3-319-20424-6
ISBN (Print)978-3-319-20423-9
DOIs
Publication statusPublished - 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume9147
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Abstract

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. (1) 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. (2) We show that a variety of mapping requirements can be expressed in this model, such as virtual machine placement, network embedding and priority mapping. (3) 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 PTIME to NP-complete. For intractable optimization problems, we further show that these problems are approximation-hard, i.e., NPO-complete in general and APX-hard even for special cases.

Download statistics

No data available

ID: 19939357