Hardness of Virtual Network Embedding with Replica Selection

Efficient embedding virtual clusters in physical network is a challenging problem. In this paper we consider a scenario where physical network has a structure of a balanced tree. This assumption is justified by many real- world implementations of datacenters. We consider an extension to virtual cluster embedding by introducing replication among data chunks. In many real-world applications, data is stored in distributed and redundant way. This assumption introduces additional hardness in deciding what replica to process. By reduction from classical NP-complete problem of Boolean Satisfia- bility, we show limits of optimality of embedding. Our result holds even in trees of edge height bounded by three. Also, we show that limiting repli- cation factor to two replicas per chunk type does not make the problem simpler.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-01-29

• Fields of study

  Computer Science

• Identifiers
  arXiv 1501.07379
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• ElasticSwitch: practical work-conserving bandwidth guarantees for cloud computing

  2013cited by this paper
• Virtual Network Embedding: A Survey

  2013cited by this paper
• What we talk about when we talk about cloud network performance

  2012influential reference
• Shark: SQL and rich analytics at scale

  2012cited by this paper
• NoDB: efficient query execution on raw data files

  2012cited by this paper
• FairCloud: sharing the network in cloud computing

  2012cited by this paper
• The only constant is change: incorporating time-varying network reservations in data centers

  2012influential reference
• Gatekeeper: Supporting Bandwidth Guarantees for Multi-tenant Datacenter Networks

  2011cited by this paper
• Towards predictable datacenter networks

  2011influential reference
• Managing data transfers in computer clusters with orchestra

  2011cited by this paper
• Seawall: Performance Isolation for Cloud Datacenter Networks

  2010cited by this paper
• A survey of network virtualization

  2010cited by this paper
• SecondNet: a data center network virtualization architecture with bandwidth guarantees

  2010cited by this paper
• VL2: a scalable and flexible data center network

  2009cited by this paper
• A scalable, commodity data center network architecture

  2008cited by this paper
• MapReduce: simplified data processing on large clusters

  2008influential reference
• Cloud control with distributed rate limiting

  2007cited by this paper

• No citing papers are available for this paper.