Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Virtual Network Embedding: Paths and Cycles
63
0
0.0
(
0
)
Added by
Haitao Wu
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Network virtualization provides a promising solution to overcome the ossification of current networks, allowing multiple Virtual Network Requests (VNRs) embedded on a common infrastructure. The major challenge in network virtualization is the Virtual Network Embedding (VNE) problem, which is to embed VNRs onto a shared substrate network and known to be $mathcal{NP}$-hard. The topological heterogeneity of VNRs is one important factor hampering the performance of the VNE. However, in many specialized applications and infrastructures, VNRs are of some common structural features $textit{e.g.}$, paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications and infrastructures by taking into accounting topological characteristics. Besides, paths and cycles are two of the most fundamental topologies that all network structures consist of. Exploiting the characteristics of path and cycle embeddings is vital to tackle the general VNE problem. In this paper, we investigated the path and cycle embedding problems. For path embedding, we proved its $mathcal{NP}$-hardness and inapproximability. Then, by utilizing Multiple Knapsack Problem (MKP) and Multi-Dimensional Knapsack Problem (MDKP), we proposed an efficient and effective MKP-MDKP-based algorithm. For cycle embedding, we proposed a Weighted Directed Auxiliary Graph (WDAG) to develop a polynomial-time algorithm to determine the least-resource-consuming embedding. Numerical results showed our customized algorithms can boost the acceptance ratio and revenue compared to generic embedding algorithms in the literature.
rate research
Read More
Virtualization facilitates heterogeneous cloud applications to share the same physical infrastructure with admirable flexibility, while resource efficiency and survivability are critical concerns for virtual network embedding (VNE). As more and more internet applications migrate to the cloud, the resource efficiency and the survivability of VNs, such as single link failure or large-scale disaster survivability, have become crucial issues. Separating the VNE problem into node and link mapping sub-problems without coordination might cause a high embedding cost. This dissertation presents two independent approaches to solve the aforementioned challenges. First, we study two-stage coordinated survivable VNE (SVNE) problem and propose an adaptive path splitting based SVNE (APSS) scheme. We first develop a concise anchor node strategy to restrict the solution space of the candidate substrate nodes, which coordinates node mapping with link mapping to limit the distance spans of the virtual links. Then, we employ an adaptive path splitting policy to provide full protection against single-link failures with partial backup resource, and design an agile frequency slot windows choosing mechanism to mitigate the spectrum fragmentation for link resource efficiency. Simulation results demonstrate that the proposed APSS scheme can achieve satisfactory performance in terms of spectrum utilization and blocking ratio. Second, we propose a synchronous evacuation strategy for VNs with dual virtual machines (VMs) inside a disaster risk zone (DRZ), which suffer higher risks than the VNs with single. The evacuation strategy exploits post-copy technique to sustain the online service alive and enhances synchronous VM migrations to shorten the dual-VM evacuation time. Numerical results show that the proposed strategy can outperform the best-effort scheme in terms of average and total evacuation times of dual-VMs.
It is well-known that cloud application performance critically depends on the network. Accordingly, new abstractions for cloud applications are proposed which extend the performance isolation guarantees to the network. The most common abstraction is the Virtual Cluster V C(n, b): the n virtual machines of a customer are connected to a virtual switch at bandwidth b. However, today, not much is known about how to efficiently embed and price virtual clusters. This paper makes two contributions. (1) We present an algorithm called Tetris that efficiently embeds virtual clusters arriving in an online fashion, by jointly optimizing the node and link resources. We show that this algorithm allows to multiplex more virtual clusters over the same physical infrastructure compared to existing algorithms, hence improving the provider profit. (2) We present the first demand-specific pricing model called DSP for virtual clusters. Our pricing model is fair in the sense that a customer only needs to pay for what he or she asked. Moreover, it features other desirable properties, such as price independence from mapping locations.
A virtual network (VN) contains a collection of virtual nodes and links assigned to underlying physical resources in a network substrate. VN migration is the process of remapping a VNs logical topology to a new set of physical resources to provide failure recovery, energy savings, or defense against attack. Providing VN migration that is transparent to running applications is a significant challenge. Efficient migration mechanisms are highly dependent on the technology deployed in the physical substrate. Prior work has considered migration in data centers and in the PlanetLab infrastructure. However, there has been little effort targeting an SDN-enabled wide-area networking environment - an important building block of future networking infrastructure. In this work, we are interested in the design, implementation and evaluation of VN migration in GENI as a working example of such a future network. We identify and propose techniques to address key challenges: the dynamic allocation of resources during migration, managing hosts connected to the VN, and flow table migration sequences to minimize packet loss. We find that GENIs virtualization architecture makes transparent and efficient migration challenging. We suggest alternatives that might be adopted in GENI and are worthy of adoption by virtual network providers to facilitate migration.
Cloud computing has emerged as a powerful and elastic platform for internet service hosting, yet it also draws concerns of the unpredictable performance of cloud-based services due to network congestion. To offer predictable performance, the virtual cluster abstraction of cloud services has been proposed, which enables allocation and performance isolation regarding both computing resources and network bandwidth in a simplified virtual network model. One issue arisen in virtual cluster allocation is the survivability of tenant services against physical failures. Existing works have studied virtual cluster backup provisioning with fixed primary embeddings, but have not considered the impact of primary embeddings on backup resource consumption. To address this issue, in this paper we study how to embed virtual clusters survivably in the cloud data center, by jointly optimizing primary and backup embeddings of the virtual clusters. We formally define the survivable virtual cluster embedding problem. We then propose a novel algorithm, which computes the most resource-efficient embedding given a tenant request. Since the optimal algorithm has high time complexity, we further propose a faster heuristic algorithm, which is several orders faster than the optimal solution, yet able to achieve similar performance. Besides theoretical analysis, we evaluate our algorithms via extensive simulations.
The SDN and NFV paradigms enable novel network services which can be realized and embedded in a flexible and rapid manner. For example, SDN can be used to flexibly steer traffic from a source to a destination through a sequence of virtualized middleboxes, in order to realize so-called service chains. The service chain embedding problem consists of three tasks: admission control, finding suitable locations to allocate the virtualized middleboxes and computing corresponding routing paths. This paper considers the offline batch embedding of multiple service chains. Concretely, we consider the objectives of maximizing the profit by embedding an optimal subset of requests or minimizing the costs when all requests need to be embedded. Interestingly, while the service chain embedding problem has recently received much attention, so far, only non- polynomial time algorithms (based on integer programming) as well as heuristics (which do not provide any formal guarantees) are known. This paper presents the first polynomial time service chain approximation algorithms both for the case with admission and without admission control. Our algorithm is based on a novel extension of the classic linear programming and randomized rounding technique, which may be of independent interest. In particular, we show that our approach can also be extended to more complex service graphs, containing cycles or sub-chains, hence also providing new insights into the classic virtual network embedding problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
