QoS-Aware Virtual Network Embedding

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. 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