Formulation

1. An NP-hard combinatorial optimization problem

2. Two subproblems: node mapping and link mapping

3. Various evaluation metrics:

The objective of Virtual Network Embedding (VNE) is to map the virtual nodes and links onto the substrate network while satisfying various constraints, such as resource availability, capacity, and latency requirements. VNE can be divided into two subproblems: node mapping and link mapping.

Node Mapping

The node mapping problem aims to map the virtual nodes to the substrate nodes while ensuring that the resources required by the virtual nodes are available on the substrate nodes. The objective is to minimize the overall resource consumption of the substrate nodes, while satisfying constraints such as bandwidth, delay, and node capacity.

Constraints

• Node Resource constraints: the capacity of the physical node must be greater than or equal to the total resource requirements of the mapped virtual nodes.

• One-to-one mapping constraints: Each virtual node should be mapped to exactly one substrate node.

• Connectivity constraints: the mapping should preserve the connectivity of the virtual network, i.e., if there is a virtual link between two virtual nodes, the corresponding physical nodes should be connected by a physical link.

Link Mapping

The link mapping problem aims to map the virtual links to the substrate links while ensuring that the required bandwidth of the virtual links is available on the substrate links. The objective is to minimize the overall cost of the substrate links, while satisfying constraints such as bandwidth, delay, and node capacity.

Constraints

• Link resource constraint: The sum of the bandwidth requirements of the virtual links mapped to a physical link cannot exceed its capacity.

• Link-to-path mapping constraint: Each virtual link can only be mapped to a path consisting of physical links.

• Path length constraint: The length of the path used to map a virtual link cannot exceed a predefined maximum value, resulting from the QoS requirements (e.g., delay).

Evaluation Metric

The evaluation of Virtual Network Embedding (VNE) algorithms is crucial for measuring their performance and comparing their results. Evaluation metrics aim to capture different aspects of the embedding process, such as resource utilization, link mapping efficiency, or service quality. In general, there are several evaluation metrics that are commonly used to assess the performance of VNE algorithms.

• Acceptance Ratio: The acceptance ratio is a metric that evaluates the number of VN requests that are successfully embedded in the SN. It is calculated as the ratio of the number of successful embeddings to the total number of embedding requests. A higher acceptance ratio indicates a better embedding performance.

• Revenue-to-cost: Revenue-to-cost measures the revenue generated by embedding virtual networks against the cost incurred in embedding them. The revenue is usually derived from the services offered by the virtual networks, while the cost includes the resources consumed during embedding, such as the bandwidth usage and energy consumption. R/C is a crucial metric for service providers, as it helps them optimize their resource utilization and improve their profitability. The higher the R/C ratio, the better the profitability of the service provider.

• Cost: The embedding cost is the primary metric for evaluating the VNE problem. It represents the amount of resources used to embed a virtual network (VN) in the substrate network (SN). The embedding cost can be measured by adding up the cost of embedding individual virtual nodes and links and can be expressed in terms of computational resources, bandwidth, or any other resource that is being utilized in the embedding process. A lower embedding cost indicates a better embedding performance.

• Revenue: Revenue is a metric used to evaluate the business aspect of the VNE problem. It represents the revenue generated by the virtual network provider (VNP) by embedding the VN in the SN. The revenue can be calculated by taking into account the amount of resources used to embed the VN, the number of requests, and the revenue generated per request. A higher revenue indicates a better embedding performance from a business perspective.

• Profit: Profit is another metric used to evaluate the business aspect of the VNE problem. It represents the profit generated by the VNP by embedding the VN in the SN, which is calculated by subtracting the embedding cost from the revenue. A higher profit indicates a better embedding performance from a business perspective.

• Resource Utilization: Resource utilization measures how effectively the resources in the substrate network are being used. It can be measured by the percentage of resources utilized in the SN after embedding the VN. A higher resource utilization indicates a better embedding performance, as the resources are being utilized efficiently.

• Delay: Delay is a metric that evaluates the end-to-end delay in the VN after it is embedded in the SN. It can be measured by the average delay experienced by the packets in the VN or the maximum delay experienced by any packet in the VN. A lower delay indicates a better embedding performance.

• Throughput: Throughput is a metric that evaluates the amount of data that can be transmitted through the VN after it is embedded in the SN. It can be measured by the average throughput of the packets in the VN or the maximum throughput of any packet in the VN. A higher throughput indicates a better embedding performance.

These evaluation metrics are used to measure the performance of VNE algorithms and compare them with each other. However, the choice of evaluation metrics depends on the specific requirements and objectives of the VNE problem.