Abstract
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.
Introduction
As cloud infrastructure becomes the backbone of modern internet services, tenants increasingly demand predictable performance and high availability. This has led to the adoption of the "Virtual Cluster" (VC) abstraction, which guarantees a specific number of Virtual Machines (VMs) and a per-VM network bandwidth guarantee (the hose model). However, physical machine (PM) failures remain a constant threat to Service Level Agreements (SLAs). Traditional fault-tolerance methods often rely on disjointed provisioning—placing primary VMs first and then seeking backups—which leads to significant resource waste.
This paper addresses the Survivable Virtual Cluster Embedding Problem (SVCEP) by proposing a joint optimization framework. By considering primary and backup placements simultaneously, cloud providers can guarantee 100% recovery from any single PM failure while using the absolute minimum number of extra server slots.
Methodology
The authors model the data center as a tree-structured network and introduce two algorithmic solutions:
- Optimal Algorithm (OPT): A bottom-up dynamic programming (DP) approach. It computes the minimum total VMs needed in each subtree to guarantee $n_0$ working VMs during normal operation and $n_1$ working VMs during any single-PM failure. It runs in pseudo-polynomial time ($O(|V| \cdot N^6)$).
- Efficient Heuristic (HEU): To handle large-scale requests, the HEU algorithm treats survivability as an "augmented" request. It iteratively attempts to embed $N + N'$ VMs using standard algorithms, stopping at the lowest $N'$ that ensures no single PM holds more than $N'$ VMs. This reduces complexity to $O(N \cdot |V| \log |V|)$.
Key Insights: Joint Optimization
The core advantage of this approach is that joint optimization significantly outperforms traditional "shadowing" (1:1 backup ratio). By sharing backup capacity across the cluster, the system can achieve full survivability with far fewer resources.
As illustrated in Figure 4, while a standard 8-VM request might be doubled to 16 VMs in a shadow model, the optimal survivable embedding (d) requires only 11 total VMs to guarantee recovery from any single PM failure.
Evaluation and Results
The algorithms were evaluated using a custom C++ simulator on a 4-layer 8-ary tree topology. The results highlight a dramatic improvement in resource efficiency and acceptance ratios compared to the Shadow-based solution (SBS).
As shown in Figure 6, the SBS baseline consistently consumes 2x the requested VMs. In contrast, both OPT and HEU maintain a consumption ratio between 1.1 and 1.3. This efficiency allows the data center to accept significantly more tenant requests over time. While OPT provides the theoretical floor for resource usage, the HEU algorithm proved to be several orders of magnitude faster (running in milliseconds), making it the practical choice for real-time cloud management systems.
Conclusion and Future Work
Jointly optimizing primary and backup embeddings allows cloud providers to offer robust survivability guarantees without the prohibitive costs of traditional redundancy. While this work focuses on single PM failures in tree-like topologies, future research will explore extending these DP models to handle multiple simultaneous failures and more complex, non-tree data center architectures.
Summary updated