PaperlayerView exact revision on arXiv

Source-linked AI summary

Designing and Embedding Reliable Virtual Infrastructures

Wai-Leong Yeow, Cédric Westphal, Ulaş C. Kozat

arXiv:1005.5367v1cs.NI

TL;DR

Shared virtual infrastructures need reliability guarantees without excessive backup provisioning because physical failures can affect multiple virtual entities and trigger further failures. The paper introduces Opportunistic Redundancy Pooling and joint node-link resource allocation to share backups and embed them efficiently. It reports significant resource conservation and improved VInf acceptance rates, while identifying complexity and flexibility trade-offs in extended pooling schemes.

  • Problem

    The paper addresses how to allocate minimal physical compute and bandwidth resources for virtual infrastructures while guaranteeing reliability through redundant nodes and links.

  • Method

    The paper introduces Opportunistic Redundancy Pooling and statically allocates primary and redundant compute and bandwidth while overlapping redundant-link reservations across failure scenarios.

  • Results

    Sharing backups can reduce fault-tolerance resource provisioning by at most 50% for two VInfs, while the combined mechanisms conserve resources and improve VInf acceptance rates.

  • Takeaways & Limitations

    Pooling redundant nodes across VInfs and allocating redundant links jointly can reduce the physical footprint of reliability mechanisms while preserving reliability guarantees.

  • Takeaways & Limitations

    The paper excludes extended pooling cases because they may reduce flexibility, provide marginal gains, and require costly reliability reevaluation.

Abstract

from arXiv · show

In a virtualized infrastructure where physical resources are shared, a single physical server failure will terminate several virtual servers and crippling the virtual infrastructures which contained those virtual servers. In the worst case, more failures may cascade from overloading the remaining servers. To guarantee some level of reliability, each virtual infrastructure, at instantiation, should be augmented with backup virtual nodes and links that have sufficient capacities. This ensures that, when physical failures occur, sufficient computing resources are available and the virtual network topology is preserved. However, in doing so, the utilization of the physical infrastructure may be greatly reduced. This can be circumvented if backup resources are pooled and shared across multiple virtual infrastructures, and intelligently embedded in the physical infrastructure. These techniques can reduce the physical footprint of virtual backups while guaranteeing reliability.

1 Introduction

The paper addresses reliability in shared, dynamically changing virtualized infrastructures by introducing pooled virtual backups and joint node-link redundancy. It also proposes static physical resource allocation to reduce redundancy overhead while preserving reliability.

  • Motivation: Virtualization makes a single physical server or link failure affect multiple shared virtualized entities.The paper motivates stronger fault tolerance than systems that merely tolerate restart or partial job loss.
  • Contribution: The paper proposes Opportunistic Redundancy Pooling (ORP), which shares backup resources across multiple virtual infrastructures.ORP targets an n:k redundancy architecture in which k redundant resources can back up any of n primary resources.
  • Contribution: Sharing backups can achieve k′ = max(k1, k2) for two VInfs with the same reliability levels, reducing provisioned fault-tolerance resources by at most 50%.The result is presented as a motivating example for pooling backup nodes.
  • Contribution: ORP combines redundant nodes with links so a redundant node can replace a failed node while retaining guaranteed connectivity and bandwidth.The mechanism also avoids connecting VInfs to more redundant nodes than necessary.
  • Contribution: The paper statically allocates compute and bandwidth for primary and redundant VInfs while overlapping redundant-link bandwidth where possible.The allocation uses existing redundant nodes and the output of ORP to reduce resources assigned to redundancy.
  • Scope: System health monitoring, protocol design, recovery procedures, and timing issues are outside the paper’s scope.The paper focuses on resource allocation for reliable virtual infrastructure embedding.

2 Problem Statement

The paper formulates reliable virtual infrastructure embedding as allocating minimal physical compute and network resources while meeting a reliability guarantee. Virtual nodes require backups capable of assuming failed nodes’ execution and neighbor bandwidth demands.

  • Infrastructure model: A physical infrastructure is modeled as an undirected graph whose nodes provide computational capacity Γµ and whose links provide bandwidth capacity Λµν.These capacities define the physical resources available for embedding.
  • Infrastructure model: A VInf is modeled as an undirected graph with node computation requirements γu and link bandwidth requirements λuv.The virtual graph represents a resource lease request.
  • Reliability requirements: A backup node must provide at least the failed critical node’s computation and bandwidth requirements to its neighbors.The conditions are γb ≥ γc and λbu ≥ λcu for each neighbor u of c.
  • Problem formulation: The problem is to allocate as few physical resources as possible for a VInf while achieving reliability of at least r.The allocation includes redundancy for the virtual infrastructure.

3 Reliability

The paper defines reliability as the probability that critical VInf nodes remain operational despite failures, then analyzes redundancy and failover configurations under independent and cascading failure models. It emphasizes that backup requirements depend on failure behavior, physical placement, and the chosen failover configuration.

  • Reliability definition: Reliability is the probability that critical VInf nodes remain operational over possible node failures, distinct from availability.Availability instead concerns uptime relative to uptime plus downtime.
  • Reliability definition: For n critical nodes and k backups, the reliability condition requires Pr(k out of n + k virtual nodes fail) < 1 −r.This includes simultaneous failures of critical and backup nodes.
  • Failover configuration: Active/Active keeps all nodes online and relies on load redistribution, requiring homogeneous nodes and easily distributable load.An external load balancer distributes load across available nodes.
  • Failover configuration: Active/Passive keeps redundant nodes idle until failures occur, and capable backups can reduce the required number below n.The configuration supports heterogeneous nodes, unlike Active/Active, but heterogeneous backups need all critical VM images on disk.
  • Failover configuration: Active/Active uses the minimum number of redundant nodes, while Active/Passive can match it when every backup can assume any n critical-node operations.The equivalence follows because Active/Active can shift load to the n critical nodes and leave backups idle.
  • Failover configuration: Active/Passive is used for the remainder of the paper because heterogeneous VMs can be supported and redundant nodes can be pooled across VInfs.Hot spares require synchronization, memory, and network bandwidth for state updates.
  • Failure modeling: Physical placement and failure models determine redundant-node requirements, motivating constraints that separate mapped physical nodes to avoid correlated failures.The constraints make virtual-node failure rates directly derive from their mapped physical nodes.
  • Failure modeling: Independent failures use a binomial term based on homogeneous physical-node failure probability p, while cascading models require distributions of total failures.The paper discusses load-based, tree-based, and degree-based cascade models and searches for k in O(n^2 log n).

4 Redundancy pooling: quantization gains

Pooling backup nodes exploits sub-linear redundancy requirements to reduce computational resources, but arbitrary pooling can shift costs to redundant links and synchronization. Opportunistic Redundancy Pooling (ORP) uses excess reliability from discrete backup-allocation steps to avoid those overheads while supporting flexible sharing.

  • Pooling motivation: Active/Passive redundant nodes can be shared across VInfs because they remain idle, reducing redundant resources in the physical infrastructure.This sharing is unavailable in Active/Active configurations, where virtual nodes must remain running.
  • Arbitrary pooling: For p = 0.01, two VInfs with 100 critical nodes each reduce their combined backups from 16 to 11 through pooling, saving 31.25% of redundant computational resources.The benefit follows the sub-linear relationship between critical nodes and required backups.
  • Arbitrary pooling: For large VInfs, pooling benefits diminish because the required backup count becomes linear in the number of critical nodes.The theorem establishes that the backup count no longer decreases through sharing as the infrastructure size grows.
  • Arbitrary pooling: Arbitrary pooling has three tradeoff regions: both VInfs may need more backups, neither may need more, or only one may need more.These regions compare pooled k′ with each individual requirement k1 and k2.
  • Arbitrary pooling: The ideal no-tradeoff region halves total backups without increasing redundant links or synchronization overhead, but it is small and limited to small n.In other regions, computational savings can require additional redundant bandwidth and hot-standby synchronization.
  • Opportunistic Redundancy Pooling: ORP pools discrete excess reliability rather than arbitrarily combining requirements, avoiding additional bandwidth and synchronization overhead while accommodating different reliability guarantees.A VInf can reuse another VInf’s excess reliability when backup requirements remain constant across a range of critical-node counts.
  • Opportunistic Redundancy Pooling: ORP can conserve up to 50% of backup nodes and supports adding or removing VInfs without disturbing the other pooled infrastructures.When the central VInf is removed, other VInfs reclaim their backup nodes for reuse with incoming VInfs.
  • Scope: The paper does not study deeper or multi-parent pooling because it may reduce dynamic flexibility, provide marginal gains, and require costly reliability reevaluation.These constraints define the scope of the proposed pooling extensions.

5 Preserving Virtual Infrastructure

The paper preserves a virtual infrastructure during failures by ensuring backup nodes retain guaranteed connectivity to critical-node neighbors, avoiding recovery-time swapping. Its redundant-link design adds connectivity systematically, while physical embedding reduces bandwidth reservations because redundant links are not simultaneously active.

  • Preserving topology: Backup nodes must have guaranteed bandwidth to every neighbor of each critical node so the virtual infrastructure topology remains preserved after failures.This requirement translates topology preservation into connectivity and bandwidth guarantees for backup nodes.
  • Minimum redundant links: Minimum-link constructions can preserve graph isomorphism without preserving node identities, potentially requiring VM swaps during recovery.Such rearrangement can delay recovery or require additional resources.
  • Redundant-link construction: The paper adds links from every backup node to critical-node neighbors and interconnects backup nodes when critical nodes may be adjacent and fail simultaneously.The backup-node interconnection set can be omitted when no links exist between critical nodes.
  • Redundant-link construction: Adding the redundant-link set avoids swapping or rearrangement during recovery and does not affect other VInfs sharing the same backup nodes.This design trades additional redundant resources for direct recovery without node reassignment.
  • Physical embedding: Although the redundant-link set can contain O(nk+k^2) links, physical bandwidth can be lower because at most the links needed for simultaneous failures are active.The required reservation depends on backup placement and on how redundant links overlap physically.

6 Resource Allocation: a mixed integer programming problem

The paper formulates reliable virtual-infrastructure embedding as an adapted multi-commodity flow problem with binary node-mapping variables, redundancy-aware flows, and constraints for capacity, location, and reuse. The mixed-integer objective minimizes allocated compute and bandwidth resources while supporting pooled backups and overlapping redundant links.

  • Model formulation: The allocation model jointly embeds virtual nodes and links by adapting a multi-commodity flow formulation with constraints that minimize bandwidth on redundant links.Virtual links and redundancy flows are represented as flows between mapped virtual nodes, while mapping variables determine physical placements.
  • Mapping constraints: Binary mapping variables ensure each virtual node is hosted exactly once while each physical node hosts at most one virtual node.Existing backup-node reuse can be enforced by fixing the corresponding mapping variables.
  • Placement constraints: The formulation supports location exclusion, preference, separation, compute capacities, and reuse of existing pooled backup nodes.Exclusion prevents pooled backups from sharing locations with existing VInfs, while other constraints encode placement preferences and failure separation.
  • Redundancy flows: Four flow categories represent ordinary virtual links, backup-to-neighbor recovery paths, aggregate redundant-node flows, and backup-to-backup links.L1 bandwidth depends on the recovered critical node and can overlap across failure scenarios; L2 flows connect backup nodes.
  • Capacity constraints: The model reserves physical-link capacity using the maximum bandwidth across failure scenarios involving at most k failed critical nodes.This captures overlapping redundant links but causes exponential constraint growth as k increases.
  • Optimization: The resulting mixed-integer program is NP-hard, so relaxing binary mapping variables provides an approximate embedding before resolving link assignments with fixed virtual-node locations.The objective weights compute nodes and physical links to minimize resource usage and can use unit weights for load balancing over time.

7 Evaluation

The evaluation compares pooled redundancy, unshared redundancy, and no redundancy across simulations and reliability or bandwidth settings. Pooling admits more and larger VInfs while using resources more efficiently than unshared redundancy, though reliability incurs acceptance losses relative to the no-redundancy baseline.

  • Single-instance evaluation: At 99.99% reliability and 35-unit maximum virtual-link bandwidth, shared redundancy admits more VInfs than unshared redundancy despite lower CPU utilization.The single-instance evaluation tracks acceptance, admitted VInfs, bandwidth, and CPU utilization over time.
  • Bandwidth utilization: Shared redundancy does not use more bandwidth than unshared redundancy despite admitting more VInfs, and later simulations show lower bandwidth utilization.Pooling offsets the higher bandwidth dedicated to redundancy by admitting more critical-node VInfs.
  • Overall comparison: Across 10 simulation runs, sharing redundancies yields higher acceptance and VInf occupancy than unshared redundancy while using fewer backup nodes.The shared case reuses pooled backups, whereas noshare has the lowest acceptance rate and occupancy.
  • Admission behavior: Unshared redundancy expands VInfs into larger resource requests, causing more rejections of larger, higher-bandwidth, or higher-reliability VInfs.The resulting inefficiency favors smaller VInfs, especially those without critical nodes.
  • Reliability cost: Relative to no redundancy, reliability provisioning reduces admitted VInfs by at most 20%, while the largest acceptance-rate drop is 51% with sharing and 41% with unshared redundancy.The reported comparison also gives a 65% baseline acceptance-rate figure for the no-redundancy case.

8 Related Work

Related work addresses network and node fault tolerance through redundant topologies, data-center design, virtual-machine duplication, migration, and snapshots. These approaches generally do not jointly solve customizable reliability guarantees with resource-aware embedding of reliable virtual infrastructures.

  • Data-center systems: Data-center fault-tolerance designs provide reliability for the whole data center through excess nodes and links rather than customized guarantees for embedded VInfs.Their organized redundancy is not tailored to individual virtual infrastructures.
  • Virtualization-level approaches: Shadow VNets, virtual-router migration, and hypervisor-level duplication address monitoring, migration, or software-failure tolerance but do not provide the paper’s resource-allocation treatment.Slices colocated on one physical node remain exposed to physical-node failures.
  • Snapshot recovery: Snapshot-based methods recover virtual infrastructures from replicated or erasure-coded storage, but sufficient physical recovery resources and automatic restoration remain unresolved.These approaches take static snapshots without synchronization.
  • Topology-based fault tolerance: Redundant-topology methods optimize additional links or bandwidth for fault tolerance but primarily target stateless multiprocessor systems.Node failures in those systems can be handled through migration or rotation among remaining nodes.
  • Virtual-network embedding: The paper formulates reliable virtual-network embedding with node and link redundancy, using path splitting to distribute flows across multiple routes.Path splitting provides resilience to link failures within the multi-commodity-flow formulation.

9 Conclusion

The paper combines redundancy pooling with redundancy-aware physical allocation to conserve resources and improve acceptance rates for reliable virtual infrastructures.

  • Conclusion: Pooling redundant nodes across VInfs and allocating redundant links using maximum bandwidth over failure scenarios significantly conserves resources and improves VInf acceptance rates.The allocation uses a linear program adapted from the multi-commodity flow problem and supports independent and cascading failures.

Appendix A Backups for cascading failure models

The required number of backup nodes depends on the virtual infrastructure’s failure model. For a target reliability r, the failure distribution f(x) is used to search for the minimum backup count k.

  • Backup-node requirements are determined by the virtual infrastructure’s failure model.
  • The method computes failed-node distributions for three cascading-failure models and searches iteratively for the minimum k satisfying reliability target r.

A.1 Load-based Model

The load-based model represents cascading failures through node loads, disturbances, thresholds, and redistributed load. Its resulting failure distribution supports computing the backups required for reliability r.

  • The load-based model starts with n identical nodes whose loads are uniformly distributed between Lmin and Lmax, each having failure threshold Lfail.
  • After disturbance D, each round records failures Mi and increases every surviving node’s load by MiP until failures stop.
  • The model’s failed-node distribution is used to compute the number of backups required to guarantee reliability r.

A.2 Tree-based Model

The tree-based model uses a continuous-time Markov chain to represent cascading failures across node categories and operating environments. Its steady-state probabilities are aggregated into a failure distribution for shared redundancy calculations.

  • The tree-based model is a CTMC in which category-i failures cause category-j failures at rate φij.
  • Each state records the operating environment and the number of failed nodes in each category, with transitions governed by loading, failure, and repair rates.
  • The model is adapted by removing category redundancies, restricting each category’s maximum to one node, and selecting a repair rate that describes MTTR.
  • The probability of x failed nodes is obtained by summing steady-state probabilities over CTMC states whose numeric elements sum to x.
  • The generator matrix Q is built from cascading failure trees and transition rates, after which π is solved from πT Q = 0 and πT (1, . . . , 1) = 1 using Singular Value Decomposition.

A.3 Degree-based Model

The degree-based model propagates failures according to neighbor-failure thresholds and analyzes when cascades become network-wide. A worst-case distribution yields a conservative backup bound, while binary search efficiently finds k.

  • A.3 Degree-based Model: In the degree-based model, a node fails when the fraction of failed neighbors exceeds its threshold φ, and failures propagate until no surviving node meets that condition.
  • A.3 Degree-based Model: The model studies the probability that an initial failure triggers a network-wide cascade, including the case where all n nodes fail.
  • A.3 Degree-based Model: Because fDEGREE(x) is unknown for x < n, the method uses a worst-case distribution concentrated on x = n −1 and x = n.
  • A.3 Degree-based Model: This worst-case bound never yields fewer than n −1 backups, although Monte Carlo simulation could provide a tighter k when cascading-failure probability is high.
  • A.4 Numerical method for k: Reliability increases monotonically with k, so binary search finds the smallest backup count meeting target r within the worst-case bound.
  • A.4 Numerical method for k: O(n^2 log n) is the time complexity for computing k with the numerical procedure.
Loading 1005.5367v1…