Implemented Algorithms#

Virne has implemented the following heuristic-based and learning-based algorithms:

Simple Baseline Solvers#

Name	Command	Mapping
Random Rank	`random_rank`	`two-stage`
Random Joint Place and Route	`random_joint_pr`	`joint_pr`
Random Rank Breath First Search	`random_bfs_trials`	`bfs_trials`
Order Rank	`order_rank`	`two-stage`
Order Joint Place and Route	`order_joint_pr`	`joint_pr`
Order Rank Breath First Search	`order_bfs_trials`	`bfs_trials`
First Fit Decreasing Rank	`ffd_rank`	`two-stage`
First Fit Decreasing Joint Place and Route	`ffd_joint_pr`	`joint_pr`
First Fit Decreasing Rank Breath First Search	`ffd_bfs_trials`	`bfs_trials`

Name	Command	Type	Mapping	Title	Publication	Year	Note
PG-CNN2	`pg_cnn2`	`learning`	`two-stage`	A Virtual Network EmbeddingAlgorithm Based On Double-LayerReinforcement Learning	The Computer Journal	2022
A3C-G3C-Seq2Seq*	`a3c_gcn_seq2seq`	`learning`	`joint_pr`	DRL-SFCP: Adaptive Service Function Chains Placement with Deep Reinforcement Learning	ICC	2021
PG-CNN-QoS	`pg_cnn_qos`	`learning`	`two-stage`	Resource Management and Security Scheme of ICPSs and IoT Based on VNE Algorithm	IoTJ	2021
PG-Seq2Seq	`pg_seq2seq`	`learning`	`joint_pr`	A Continuous-Decision Virtual Network Embedding Scheme Relying on Reinforcement Learning	TNSM	2020
GAE-Clustering	`gae_clustering`	`learning`	`bfs_trials`	Accelerating Virtual Network Embedding with Graph Neural Networks	CNSM	2020	Clustering
PG-MLP	`pg_mlp`	`learning`	`joint_pr`	NFVdeep: adaptive online service function chain deployment with deep reinforcement learning.	IWQOS	2019
Hopfield-Network	`hopfield_network`	`learning`	`two-stage`	NeuroViNE: A Neural Preprocessor for Your Virtual Network Embedding Algorithm	INFOCOM	2018	Subgraph Extraction
PG-CNN	`pg_cnn`	`learning`	`two-stage`	A Novel Reinforcement Learning Algorithm for Virtual Network Embedding	Neurocomputing	2018
MCTS	`mcts`	`learning`	`two-stage`	Virtual Network Embedding via Monte Carlo Tree Search	TCYB	2018	MultiThreading Support

* means that the algorithm only supports chain-shape virtual networks embedding

Name	Command	Type	Mapping	Title	Publication	Year	Note
NodeRanking-MetaHeuristic	`_`	`meta-heuristics`	`joint`	Virtual network embedding through topology awareness and optimization	CN	2012	MultiThreading Support
Genetic-Algorithm	`ga`	`meta-heuristics`	`two-stage`	Virtual network embedding based on modified genetic algorithm	Peer-to-Peer Networking and Applications	2019	MultiThreading Support
Tabu-Search	`ts`	`meta-heuristics`	`joint`	Virtual network forwarding graph embedding based on Tabu Search	WCSP	2017	MultiThreading Support
ParticleSwarmOptimization	`pso`	`meta-heuristics`	`two-stage`	Energy-Aware Virtual Network Embedding	TON	2014	MultiThreading Support
Ant-Colony-Optimization	`aco`	`meta-heuristics`	`joint`	Link mapping-oriented ant colony system for virtual network embedding	CEC	2017	MultiThreading Support
AntColony-Optimization	`aco`	`meta-heuristics`	`joint`	VNE-AC: Virtual Network Embedding Algorithm Based on Ant Colony Metaheuristic	ICC	2011	MultiThreading Support
Simulated-Annealing	`sa`	`meta-heuristics`	`two-stage`	FELL: A Flexible Virtual Network Embedding Algorithm with Guaranteed Load Balancing	ICC	2011	MultiThreading Support

Other Related Papers

Particle Swarm Optimization
- Xiang Cheng et al. “Virtual network embedding through topology awareness and optimization”. CN, 2012.
- An Song et al. “A Constructive Particle Swarm Optimizer for Virtual Network Embedding”. TNSE, 2020.
Genetic Algorithm
- Liu Boyang et al. “Virtual Network Embedding Based on Hybrid Adaptive Genetic Algorithm” In ICCC, 2019.
- Khoa T.D. Nguyen et al. “An Intelligent Parallel Algorithm for Online Virtual Network Embedding”. In CITS, 2019.
- Khoa Nguyen et al. “Efficient Virtual Network Embedding with Node Ranking and Intelligent Link Mapping”. In CloudNet, 2020.
- Khoa Nguyen et al. “Joint Node-Link Algorithm for Embedding Virtual Networks with Conciliation Strategy”. In GLOBECOM, 2021.
Ant Colony Optimization
- N/A

Name	Command	Type	Mapping	Title	Publication	Year
PL (Priority of Location)	`pl_rank`	`heuristics`	`two-stage`	Efficient Virtual Network Embedding of Cloud-Based Data Center Networks into Optical Networks	TPDS	2021
NRM (Node Resource Management)	`nrm_rank`	`heuristics`	`two-stage`	Virtual Network Embedding Based on Computing, Network, and Storage Resource Constraints	IoTJ	2018
GRC (Global resource capacity)	`grc_rank`	`heuristics`	`two-stage`	Toward Profit-Seeking Virtual Network Embedding Algorithm via Global Resource Capacity	INFOCOM	2014
RW-MaxMatch (NodeRank)	`rw_rank`	`heuristics`	`two-stage`	Virtual Network Embedding Through Topology-Aware Node Ranking	ACM SIGCOMM Computer Communication Review	2011
RW-BFS (NodeRank)	`rw_rank_bfs`	`heuristics`	`bfs_trials`	Virtual Network Embedding Through Topology-Aware Node Ranking	ACM SIGCOMM Computer Communication Review	2011

Name	Command	Type	Mapping	Title	Publication	Year
MIP (Mixed-Integer Programming)	`mip`	`exact`	`joint`	ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping	TON	2012
D-Rounding (Deterministic Rounding)	`d_rounding`	`exact`	`joint`	ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping	TON	2012
R-Rounding (Random Rounding)	`r_rounding`	`exact`	`joint`	ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping	TON	2012