QoS-Aware Virtual Network Embedding

✍ Scribed by Chunxiao Jiang; Peiying Zhang

• Publisher: Springer Nature
• Year: 2022
• Tongue: English
• Leaves: 395
• Category: Library

✦ Synopsis

As an important future network architecture, virtual network architecture has received extensive attention. Virtual network embedding (VNE) is one of the core services of network virtualization (NV). It provides solutions for various network applications from the perspective of virtual network resource allocation. The Internet aims to provide global users with comprehensive coverage. The network function requests of hundreds of millions of end users have brought great pressure to the underlying network architecture. VNE algorithm can provide effective support for the reasonable and efficient allocation of network resources, so as to alleviate the pressure off the Internet. At present, a distinctive feature of the Internet environment is that the quality of service (QoS) requirements of users are differentiated. Different regions, different times, and different users have different network function requirements. Therefore, network resources need to be reasonably allocated according to users' QoS requirements to avoid the waste of network resources. In this book, based on the analysis of the principle of VNE algorithm, we provide a VNE scheme for users with differentiated QoS requirements. We summarize the common user requirements into four categories: security awareness, service awareness, energy awareness, and load balance, and then introduce the specific implementation methods of various differentiated QoS algorithms. This book provides a variety of VNE solutions, including VNE algorithms for single physical domain, VNE algorithms for across multiple physical domains, VNE algorithms based on heuristic method, and VNE algorithms based on machine learning method.

✦ Table of Contents

Foreword
Preface
Contents
Part I Introduction
1 Introduction
1.1 Virtual Network Embedding
1.2 Differentiated QoS Requirements
1.3 Organization Structure
Part II Security-Aware Virtual Network Embedding Algorithm
2 Introduction of Security Requirements in VNE
3 Security Aware Virtual Network Embedding Algorithm Using Information Entropy TOPSIS
3.1 Introduction
3.2 Related Works
3.2.1 Traditional Virtual Network Embedding Algorithms
3.2.2 Security Risk in Network Virtualization
3.2.3 Security Aware Virtual Network Embedding Algorithms
3.3 Network Model and Problem Statement
3.3.1 Security Constraint
3.3.2 Network Model
3.3.2.1 Substrate Network
3.3.2.2 Virtual Network Request
3.3.3 Security Virtual Network Embedding Problem
3.3.4 The Formulations
3.3.5 Objectives
3.4 The Node Ranking Method using Information Entropy TOPSIS
3.4.1 The Metrics of Node Importance
3.4.2 The Information Entropy TOPSIS
3.4.3 An Example for Information Entropy TOPSIS
3.5 Heuristic Algorithm Design
3.5.1 Node Mapping Algorithm
3.5.2 Link Mapping Algorithm
3.5.3 Time Complexity Analysis
3.6 Experimental Results and Analysis
3.6.1 Experiment Settings
3.6.2 Results and Discussion
3.7 Conclusions and Future Work
References
4 Security Aware Virtual Network Embedding Algorithm Based on Reinforcement Learning
4.1 Introduction
4.2 Related Work
4.2.1 Virtual Network Embedding Related Algorithms
4.2.2 Security Aware Virtual Network Embedding Algorithms
4.2.3 Machine Learning-Based Virtual Network Embedding Algorithms
4.3 Network Models and Evaluation Indicators
4.3.1 Network Models
4.3.2 Evaluation Indicators
4.4 Introduction of Reinforcement Learning Algorithm Based on Policy Network
4.4.1 Extraction of Substrate Node Attributes
4.4.2 Policy Network
4.4.3 Training and Testing
4.4.4 Algorithm Complexity Analysis
4.5 Experimental Setup and Result Analysis
4.5.1 Experimental Setup
4.5.2 Training Results and Analysis
4.5.3 Test Results and Analysis
4.6 Conclusions and Future Work
References
5 VNE Solution for Network Differentiated QoS and Security Requirements from the Perspective of Deep Reinforcement Learning
5.1 Introduction
5.2 Related Work
5.2.1 VNE Algorithms Based on Differentiated QoS
5.2.2 VNE Algorithms Based on Security
5.3 Description and Model Establishment of VNE Problem with Differentiated QoS and Security
5.3.1 Description of VNE Problem with Differentiated QoS and Security
5.3.2 Network Models
5.3.3 Constraints
5.3.4 Evaluating Indicators
5.3.5 An Example
5.4 Implementation of VNE Algorithm Based on Differentiated QoS and Security Requirements
5.4.1 The Framework of VNE Algorithm Based on DRL
5.4.2 Network Feature Extraction
5.4.3 Policy Network Construction
5.4.4 Training and Testing
5.5 Experimental Setup and Result Analysis
5.5.1 Experimental Setup
5.5.2 Results and Analysis
5.5.2.1 Training Results and Analysis
5.5.2.2 Test Results and Analysis
5.6 Conclusion
References
6 Resource Management and Security Scheme of ICPSs and IoT Based on VNE Algorithm
6.1 Introduction
6.2 Related Work
6.2.1 Heuristic VNE Algorithm with Resource Constraints
6.2.2 Embedded Algorithm of Virtual Network Based on Intelligent Learning
6.3 VNE Related Problem Description
6.3.1 Network Model
6.3.2 VNE Problem Description
6.3.3 Evaluating Indicator
6.4 Algorithm Implementation
6.4.1 Attribute Extraction and Feature Matrix
6.4.2 Policy Network
6.4.3 Training and Testing
6.5 Numerical Results and Analysis
6.5.1 Experimental Environment Setting
6.5.2 Training Results
6.5.3 Test Results
6.6 Conclusion
References
Part III Service-Aware Virtual Network Embedding Algorithm
7 Description of Service-Aware Requirements in VNE
8 Virtual Network Embedding Based on Modified Genetic Algorithm
8.1 Introduction
8.2 Related Works
8.2.1 Static Virtual Network Embedding Approaches
8.2.2 Dynamic Virtual Network Embedding Approaches
8.3 Network Model and Problem Statement
8.3.1 Substrate Network Model
8.3.2 Virtual Network Model
8.3.3 Virtual Network Embedding Problem
8.3.4 Performance Evaluation Metrics
8.4 Virtual Network Embedding Algorithm Based on Modified Genetic Algorithm
8.4.1 Chromosome Encoding
8.4.2 Population Initialization
8.4.3 Crossover Operation
8.4.4 Mutation Operation
8.4.5 Feasibility Checking
8.4.6 Selection Operation
8.4.7 Improvement Operation
8.4.8 Fitness Function
8.4.9 The Proposed Algorithm
8.4.10 Time Complexity Analysis
8.5 Performance Evaluation and Analysis
8.5.1 Experimental Environment Setting
8.5.2 Experimental Results and Analysis
8.6 Conclusion
References
9 VNE-HPSO Virtual Network Embedding Algorithm Based on Hybrid Particle Swarm Optimization
9.1 Introduction
9.2 Related Works
9.2.1 The Distributed Embedding Algorithm
9.2.2 The Centralized Embedding Algorithm
9.3 Problem Statement and Network Model
9.3.1 Substrate Network Model
9.3.2 Virtual Network Request Model
9.3.3 Virtual Network Embedding Problem Statement
9.3.4 Virtual Network Embedding Evaluation Index
9.4 VNE Model
9.5 Algorithm Implementation
9.5.1 PSO Algorithm Theory Basis
9.5.2 Redefinition of Related Parameters
9.5.3 SA Algorithm
9.5.4 The Allocation Strategy of Particle Initialization
9.5.5 VNE-HPSO Algorithm
9.5.6 Time Complexities Analysis
9.6 Simulation Experiments and Analysis
9.6.1 Experimental Environment and Parameter Settings
9.6.2 Experimental Analysis
9.7 Conclusion
References
10 Topology Based Reliable Virtual Network Embedding from a QoE Perspective
10.1 Introduction
10.2 Related Works
10.2.1 Related Works with Maximum Revenue or Minimum Cost Objective
10.2.2 Related Works with Minimum Energy Consumption Objective
10.2.3 Related Works with Reliability Optimization Objective
10.2.4 Related Works with Survivable Optimization Objective
10.3 Network Model and Virtual Network Embedding Description
10.3.1 Substrate Network Infrastructure
10.3.2 Virtual Network Request
10.3.3 Virtual Network Embedding Problem Description
10.3.4 Objectives
10.4 Topology Based Node Reliability Ranking
10.4.1 Motivation
10.4.2 An Example to Illustrate the Motivation
10.4.3 The Metric of Node Reliability
10.4.4 The Metric of Node Ranking
10.5 Reliable Virtual Network Embedding Algorithm
10.5.1 The RRW-MaxMatch Algorithm
10.5.2 The RDCC-VNE Algorithm
10.6 Simulation Results and Analysis
10.6.1 Simulation Experimental Setting
10.6.2 Experimental Results and Analysis
10.7 Conclusion
References
11 DSCD Delay Sensitive Cross-Domain Virtual Network Embedding Algorithm
11.1 Introduction
11.2 Related Works
11.2.1 The Distributed MVNE Algorithms
11.2.2 The Centralized MVNE Algorithms
11.3 Network Model and Problem Statement
11.3.1 Virtual Network Request Model
11.3.2 Substrate Network Model
11.3.3 Virtual Network Embedding Model
11.3.4 Optimization Objectives
11.4 The Embedding Steps of DSCD-VNE Algorithm
11.5 Delay Sensitive Cross-Domain Virtual Network Embedding Algorithm
11.5.1 Candidate Substrate Node Selection Algorithm
11.5.2 Link Mapping Algorithm Using Path Splitting Mechanism
11.5.3 Link Mapping Algorithm Using K-shortest Path Algorithm
11.5.4 DSCD-VNE Algorithm
11.5.5 Time Complexities Analysis
11.6 Simulation Experiments and Analysis
11.6.1 Experimental Environment Settings
11.6.2 Experimental Results and Analysis
11.7 Conclusion
References
12 A Multi-Domain Virtual Network Embedding Algorithm with Delay Prediction
12.1 Introduction
12.2 Related Works
12.2.1 The Distributed VNE Algorithms
12.2.2 The Centralized VNE Algorithms
12.3 Network Model and Problem Statement
12.3.1 Virtual Network Model
12.3.2 Substrate Network Model
12.3.3 Virtual Network Embedding Problem Description
12.3.4 Objectives
12.4 Design of Virtual Network Mapping Algorithm
12.4.1 Divide Virtual Network Requests into Subgraphs
12.4.2 Selection of Candidate Nodes
12.4.3 Upload Resource Information
12.4.4 Pre-mapping of Virtual Network Requests
12.4.5 Substrate Network Mapping
12.5 Implementation of Algorithm
12.5.1 Candidate Physical Nodes Selection Algorithm
12.5.2 PSO Algorithm
12.5.3 Virtual Network Pre-mapping Algorithm
12.5.4 Substrate Network Mapping Algorithm
12.5.5 Time Complexity Analysis
12.6 Simulation Experiment and Analysis
12.6.1 Experimental Environment Settings
12.6.2 Experimental Results and Analysis
12.7 Conclusion
References
Part IV Energy-Aware Virtual Network Embedding Algorithm
13 Description of Energy Consumption Requirements in VNE
14 Multi-Objective Enhanced Particle Swarm Optimization in Virtual Network Embedding
14.1 Introduction
14.2 Related Works
14.3 The Description of Network Model and Performance Metrics
14.3.1 The Introduction of Network Model
14.3.2 The Performance Metrics
14.3.2.1 Revenue
14.3.2.2 Energy Cost
14.4 Proposed Solution
14.4.1 Particle Swarm Optimization Basics
14.4.2 Discrete PSO for VNE Problems
14.4.3 Aggregation Strategy for Fitness Function
14.4.4 Niche PSO
14.4.5 Description of Niche PSO
14.5 Performance Evaluation
14.5.1 Evaluation Settings
14.5.2 Experimental Results
14.6 Conclusion
References
15 Incorporating Energy and Load Balance into Virtual Network Embedding Process
15.1 Introduction
15.2 Related Works
15.2.1 Energy-Aware VNE Algorithms
15.2.2 Load Balance Aware VNE Algorithms
15.3 System Model and Problem Statement
15.3.1 Network Model
15.3.1.1 Substrate Network Model
15.3.1.2 Virtual Network Model
15.3.2 Virtual Network Embedding Problem
15.3.3 Objectives
15.3.4 Node and Link Energy Formulation
15.3.4.1 Node Energy Consumption
15.3.4.2 Link Energy Consumption
15.3.5 Load Balance Formulation
15.4 The Proposed Algorithm
15.4.1 Comprehensive Node Ranking Method
15.4.2 Improved Differentiated Pricing Strategy
15.4.3 E-LB-VNE Algorithm
15.5 Evaluation Results
15.5.1 Simulation Settings
15.5.2 Simulation Results
15.6 Conclusion
References
16 IoV Scenario Implementation of a Bandwidth Aware Algorithm in Wireless Network Communication Mode
16.1 Introduction
16.1.1 Contributions
16.1.2 Organization
16.2 Related Work
16.2.1 Centralized Multi-Domain VNE Algorithm
16.2.2 Distributed Multi-Domain VNE Algorithm
16.3 Problem Specification
16.3.1 Description of the Basic Problem of Multi-Domain VNE
16.3.2 Selection of Candidate Nodes
16.4 Network Models and Evaluation Indicators
16.4.1 Underlying Network Model
16.4.2 Virtual Network Model
16.4.3 VNR Model
16.4.4 The Objective Function
16.4.5 The Evaluation Index
16.5 Algorithm Description and Implementation
16.5.1 Algorithm Description
16.5.2 Algorithm Implementation
16.5.3 Algorithm Complexity
16.6 Performance Evaluation
16.6.1 Experiment Environment and Parameter Setting
16.6.2 Experimental Results and Analysis
16.7 Conclusion
References
Part V Load Balance Virtual Network Embedding Algorithm
17 Description of Load Balance in VNE
18 A Multi-Domain VNE Algorithm Based on Load Balancing in the IoT Networks
18.1 Introduction
18.2 Related Work
18.2.1 Optimal Algorithms
18.2.2 Heuristic Algorithms
18.3 Network Model and Problem Statement
18.3.1 Substrate Network and Virtual Network Model
18.3.2 Virtual Network Embedding Problem Description
18.3.3 Objectives and Evaluation Index
18.4 Strategy Model and Innovation Motivations
18.4.1 Dynamic Crossover Probability
18.4.2 Link Load Balancing Strategy
18.4.3 Gene Selection Strategy
18.5 Heuristic Algorithm Design
18.5.1 Node Mapping Algorithm
18.5.2 Link Mapping Algorithm
18.6 Performance Evaluation
18.6.1 Environment Settings
18.6.2 Algorithm Parameters
18.6.3 Evaluation Results
18.7 Conclusion
References
19 Virtual Network Embedding Based on Computing, Network, and Storage Resource Constraints
19.1 Introduction
19.2 Network Model and Problem Statement
19.2.1 Substrate Network
19.2.2 Virtual Network
19.2.3 The Metric of Substrate Network Resource
19.2.4 Virtual Network Embedding Problem
19.2.5 Objectives
19.3 Mixed Integer Programming Formulation for VNE
19.4 Heuristic Algorithm Design
19.4.1 Two Node Ranking Measurements
19.4.2 NRM-VNE Method
19.4.3 RCR-VNE Method
19.5 Performance Evaluation
19.5.1 Simulation Environment Settings
19.5.2 Performance Evaluation Results
19.6 Conclusions
References
20 Virtual Network Embedding Using Node Multiple Metrics Based on Simplified ELECTRE Method
20.1 Introduction
20.2 Related Works
20.2.1 Optimal Algorithms
20.2.2 Heuristic Algorithms
20.2.3 Meta-Heuristic Algorithms
20.3 Network Model and Problem Statement
20.3.1 Substrate Network Model
20.3.2 Virtual Network Model
20.3.3 Virtual Network Embedding Problem Description
20.3.4 Objectives
20.4 The Evaluation Metrics of Node Ranking Based on Multiple Attributes
20.4.1 Motivations
20.4.2 The Evaluation Metric of Node Ranking Analysis
20.4.3 Simplified ELECTRE Algorithm
20.4.4 An Example for Simplified ELECTRE
20.5 Heuristic Algorithm Design
20.5.1 Node Mapping Algorithm
20.5.2 Link Mapping Algorithm
20.5.3 Time Complexity Analysis
20.6 Performance Evaluation
20.6.1 Environment Settings
20.6.2 Evaluation Results
20.7 Conclusions
References
21 VNE Strategy Based on Chaotic Hybrid Flower Pollination Algorithm Considering Multi-Criteria Decision Making
21.1 Introduction
21.2 Related Work
21.2.1 Meta-Heuristic Algorithms
21.2.2 VNE Strategies
21.3 Network Model and Problem Statement
21.3.1 Substrate Network and Virtual Network Model
21.3.2 Virtual Network Embedding Problem Description
21.3.3 Objectives and Evaluation Index
21.4 Strategy Model and Innovation Motivations
21.4.1 Life Cycle Mechanism
21.4.2 Chaos Strategy
21.4.3 Self-Pollination Strategy
21.4.4 BP Neural Network
21.5 Heuristic Algorithm Design
21.5.1 Node Mapping Algorithm
21.5.2 Link Mapping Algorithm
21.6 Performance Evaluation
21.6.1 Environment Settings and Algorithm Parameters
21.6.2 Evaluation Results
21.7 Conclusion
References
Part VI Conclusion
22 Conclusion