Virne: A Benchmark of NFV-RA

Documentation | Citations | SDN-NFV Papers

---

Virne is a simulator designed to address resource allocation problems in network virtualization. This category of problems is often referred to by various names, including:

• Virtual Network Embedding (VNE)
• Virtual Network Function Placement (VNF Placement)
• Service Function Chain Deployment (SFC Deployment)
• Network Slicing

The main goal of Virne is to provide a unified and flexible framework for solving these problems. Its main characteristics are as follows.

• Rich Implementations: Provide 20+ solvers, including exact, heuristic, meta-heuristic, and machine learning-based algorithms.
• Extensible Development: Provide a variety of network topologies, network attributes, and RL environments, which can be easily extended.
• Light-Weight: Implement concisely with less necessary dependencies, and can be extended easily for specific algorithms.

Virne is still under development. If you have any questions, please open a new issue or contact me via email (wtfly2018@gmail.com)

• Completing the documentation
• Implementing more VNE algorithms

Citations

✨ If you find Virne helpful to your research, please feel free to cite our related papers❤️

[IJCAI, 2024] FlagVNE (paper & code)

@INPROCEEDINGS{ijcai-2024-flagvne,
  title={FlagVNE: A Flexible and Generalizable Reinforcement Learning Framework for Network Resource Allocation},
  author={Wang, Tianfu and Fan, Qilin and Wang, Chao and Ding, Leilei and Yuan, Nicholas Jing and Xiong, Hui},
  booktitle={Proceedings of the 33rd International Joint Conference on Artificial Intelligence},
  year={2024},
}

[TSC, 2023] HRL-ACRA (paper & code)

@ARTICLE{tfwang-tsc-2023-hrl-acra,
  author={Wang, Tianfu and Shen, Li and Fan, Qilin and Xu, Tong and Liu, Tongliang and Xiong, Hui},
  journal={IEEE Transactions on Services Computing},
  title={Joint Admission Control and Resource Allocation of Virtual Network Embedding Via Hierarchical Deep Reinforcement Learning},
  volume={17},
  number={03},
  pages={1001--1015},
  year={2024},
  doi={10.1109/TSC.2023.3326539}
}

[ICC, 2021] DRL-SFCP (paper & code)

@INPROCEEDINGS{tfwang-icc-2021-drl-sfcp,
  author={Wang, Tianfu and Fan, Qilin and Li, Xiuhua and Zhang, Xu and Xiong, Qingyu and Fu, Shu and Gao, Min},
  booktitle={ICC 2021 - IEEE International Conference on Communications}, 
  title={DRL-SFCP: Adaptive Service Function Chains Placement with Deep Reinforcement Learning}, 
  year={2021},
  pages={1-6},
  doi={10.1109/ICC42927.2021.9500964}
}

Table of Contents

• Quick Start
  • Installation
    • Install with pip
    • Install with script
  • Minimal Example
• Supported Features
• Implemented Algorithms
  • Exact Algorithms
  • Heuristic Algorithms
  • Meta-Heuristic Algorithms
  • Learning-Based Algorithms

Quick Start

Installation

Install with pip

pip install virne

Install with script

# only cpu
bash install.sh -c 0

# use cuda (optional version: 10.2, 11.3)
bash install.sh -c 11.3

Minimal Example

from virne.base import BasicScenario
from virne import Config, REGISTRY, Generator, update_simulation_setting


def run(config):
    print(f"\n{'-' * 20}    Start     {'-' * 20}\n")
    # Load solver info: environment and solver class
    solver_info = REGISTRY.get(config.solver_name)
    Env, Solver = solver_info['env'], solver_info['solver']
    print(f'Use {config.solver_name} Solver (Type = {solver_info["type"]})...\n')

    scenario = BasicScenario.from_config(Env, Solver, config)
    scenario.run()

    print(f"\n{'-' * 20}   Complete   {'-' * 20}\n")


if __name__ == '__main__':
    config = Config(
        solver_name='nrm_rank',
        # p_net_setting_path='customized_p_net_setting_file_path',
        # v_sim_setting_path='customized_v_sim_setting_file_path',
    )
    Generator.generate_dataset(config, p_net=False, v_nets=False, save=False)
    run(config)

Supported Features

• Diverse Network Topologies for Simulation

  • Simple Network Structures: e.g. Star for Centralized Network, Path for Chain-style Network, etc.
  • Random Network Topologies: e.g. Waxman Graph, Edge Probabilistic Connection Graph, etc.
  • Real-world Network Topologies: e.g. Abilene, Geant, etc.

• Multiple level Attributes for QoS:

  • Graph Level: e.g. the global requirements of user service requests, etc.
  • Node level: e.g. computing resource, server position, energy consumption, etc.
  • Link level: e.g. bandwidth resource, communication delay, etc.

• Unified Reinforcement Learning Interface for Extension

  • Provide serval RL Environments in gym.Env-style.
  • Implement the many RL training algorithms, including MCTS, PPO, A2C, etc.
  • Support the integration of RL algorithms from other libraries.

• Various Simulation Scenarios

  • Admission control: Early Reject some not cost-effective service requests.
  • Cloud-Edge: Heteregenous infrastructure with different QoS provision.
  • Time window: Globally process the a batch service requests in a time window.

• Predefined QoS Awarenesses (Additional Constraints/ Objectives)

  • Position (Node level)
  • Latency (Graph, Node and Link level)
  • Security (Graph, Node and Link level)
  • Congestion (Graph, Node and Link level)
  • Energy (Graph, Node and Link level)
  • Reliability (Graph, Node and Link level)
  • Dynamic (Graph, Node and Link level)
  • Parallelization
  • Privacy

Implemented Algorithms

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

Mapping Strategies

• Two-Stage
  • In this fromework, the VNE solving process are composed of Node mapping and Edge Mapping.
  • Firstly, the node mapping solution is generate with node mapping algorithm, i.e., Node Ranking
  • Secondly, the BFS algorithm is employed to route the physical link pairs obtained from the node mapping solution.
• Joint Place and Route
  • The solution of node mapping consists of a sequential placement decision.
  • Simultaneously, the available physical link pairs are routed by BFS algorithm.
• BFS Trails
  • Based on breadth-first search, it expands the search space by exploiting the awareness of restarts.

Learning-based Solvers

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

Meta-heuristics Solvers

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

Heuristics-based Solvers

Name	Command	Type	Mapping	Title	Publication	Year	Note
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

Exact Solvers

Name	Command	Type	Mapping	Title	Publication	Year	Note
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

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

To-do List

Environment Modeling

• ADD Scenario Window Batch Processing
• ADD Environment Check Attributes of p_net and v_net
• ADD Environment Latency Constraint
• ADD Controller Check graph constraints
• ADD Controller Multi-commodity flow
• ADD Environment QoS level Constraints
• ADD Recorder Count partial solutions' information
• ADD Enironment Early rejection (Admission control)
• ADD Environment Multi-Resources Attributes
• ADD Environment Position Constraint
• ADD Recorder Count Running physical network nodes

Algorithm Implementations

Name	Command	Type	Mapping	Title	Publication	Year	Note
PG-Conv-QoS-Security	pg_cnn_qs	learning	joint	VNE Solution for Network Differentiated QoS and Security Requirements: From the Perspective of Deep Reinforcement Learning	arXiv		Security
DDPG-Attention*	ddpg_attention	learning	joint	A-DDPG: Attention Mechanism-based Deep Reinforcement Learning for NFV	IWQOS	2021
MUVINE	mu	learning	joint	MUVINE: Multi-stage Virtual Network Embedding in Cloud Data Centers using Reinforcement Learning based Predictions	JSAC	2020	Admission Control
TD	td	learning	two-stage	VNE-TD: A virtual network embedding algorithm based on temporal-difference learning	CN	2019
RNN	rnn	learning	two-stage	Boost Online Virtual Network Embedding: Using Neural Networks for Admission Control	CNSM	2016	Admission Control