Abstract: Bridging virtualized environments with physical environments, virtual network plays an important role in Cloud Computing infrastructures. How to allocate physical resources for virtual nodes/links to construct virtual network is known as Virtual Network Embedding (VNE) problem. It is a crucial issue that draws wide attention. This paper surveys existing VNE methods and algorithms and how they work under different application scenarios. First, a survey of different VNE objective metrics is presented; then several VNE algorithms are presented and categorized; finally, the performance of different VNE solutions are compared and discussed.
Introduction to the VNE Problem
In modern cloud computing, virtualization extends beyond individual servers to encompass entire network topologies. When a tenant requests a virtual network (VN), the provider must map virtual nodes and links onto the underlying physical substrate network. This process, known as Virtual Network Embedding (VNE), is a critical NP-hard challenge. The complexity arises because even if node placement is determined, finding optimal paths for links remains computationally intensive. Providers must balance conflicting objectives: maximizing revenue by accepting more requests while minimizing operational costs and avoiding resource bottlenecks.
Methodologies in Virtual Network Embedding
Research over the last decade has produced a variety of heuristic and approximate algorithms to tackle VNE. These are generally categorized by their mapping strategies:
- Coordinated vs. Two-Stage Mapping: Early approaches mapped nodes first, followed by links. Modern "coordinated" algorithms, such as ViNEYard, optimize both simultaneously to achieve better global resource utilization.
- Node Importance and Topology-Awareness: Algorithms like RW-MM utilize Markov Random Walks or topology-aware ranking to identify critical physical nodes. Prioritizing these nodes for high-demand virtual requests helps maintain long-term network health.
- Path Splitting (PS): This technique allows a single virtual link to be split across multiple physical paths. By utilizing small "fragments" of bandwidth that would otherwise be wasted, path splitting significantly increases the acceptance ratio of VN requests.
Performance Insights and Key Results
The survey identifies several critical factors that influence VNE performance. One major insight is that Topology Matters; a node's value is defined not just by its local capacity (e.g., CPU) but by its connectivity within the substrate. Furthermore, periodic Virtual Node Migration can serve to "defragment" the physical network, creating space for new requests.
In terms of link mapping, the consensus among researchers is a clear hierarchy of performance: ORSTA > TA > ORS > R-ViNE > PS&M > PS > MCF > NCM > SP. Notably, Multi-Commodity Flow (MCF) based mapping consistently outperforms Shortest Path (SP) approaches because it considers the network state holistically rather than as isolated paths.
Future Directions
Despite significant progress, several challenges remain for VNE research:
- Wireless Virtualization: Current models largely assume stable, wired connections, failing to account for the dynamic interference and mobility inherent in wireless environments.
- Multi-Domain VNE: There is a growing need for algorithms that can embed virtual networks spanning multiple, independently managed cloud providers.
- Application-Awareness: Future solutions should distinguish between computation-intensive and communication-intensive workloads to optimize placement more effectively based on specific application needs.
Summary updated