virne 0.5.0

A unified framework for virtual network embedding.

Virne |

Documentation | SDN-NFV Papers | License

---

Virne is a simulator for resource allocation problems in network virtualization, mainly for virtual network embedding (VNE). It also is adaptable to VNE's variants, such as service function chain deployment (SFC Deployment), network slicing, etc. Specifically, it provides a unified interface for various VNE algorithms, and provides a variety of network topologies, network attributes, and RL environments.

Its main characteristics are as follows.

• Rich Implementations: Provide 20+ solvers, including exact, heuristic, meta-heuristic, and 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 ([e-mail])

• Completing the documentation
• Implementing more VNE algorithms

Citation

Please cite our papers if you use Virne in your research.

Our Related Papers

[ICC, 2021] DRL-SFCP

@INPROCEEDINGS{tfw-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},
  volume={},
  number={},
  pages={1-6},
  doi={10.1109/ICC42927.2021.9500964}
}

[TSC, Reviewing] HRL-ACRA

Table of Contents

• Quick Start
  • Installation
    • Install with pip
    • Install with script
  • Minimal Example
• VNE Problem
• 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)

VNE Problem

Brife Defination

Main Objectives

• Acceptance rate

$$ \text{Acceptance Rate} = \cfrac{\sum_{t=0}^{t=T} \text{Number}(VNR_{accept})}{\sum_{t=0}^{t=T} \text{Number}(VNR_{reject})} $$

• Long-term revenue

$$ \text{Long-term Revenue} = \sum_{n_v \in N_v}{Revenue(n_v)} + \sum_{e_v \in E_v}{Revenue(e_v)} $$

• Revenue-to-cost Ratio

$$ \text{Long-term Revenue} = \cfrac{\text{Long-term Revenue}}{\text{Long-term Cost}} $$

• Running Time

$$ \text{Running Time} = \frac{\text{Time consumption of solving }N\text{ instances}}{N} $$

• Load Balancing

• Latency Garentee

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

Mapping Strategy

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

Supported Features

• Adaptation to VNE Variants
  • Service Function Chain Deployment (SFC Deployment)
  • Network Slicing
• Diverse Network Topologies
  • Star Graph: Data Center Network
  • 2D-grid Graph: Grid Network
  • Waxman Graph: General Network
  • Path Graph: Chain-style Network
  • Edge Probabilistic Connection Graph
  • Customlized Topology
• Graph/ Node / Link-level Attributes:
  • For resources/ constraints/ QoS
  • Graph Level: e.g. the global requirements of virtual network
  • Node level: e.g. Node resource, node position
  • Link level: e.g. Link resource, link latency
• Multiple RL Environments
  • Provide serval RL Environments in gym.Env-style
• Various Simulation Scenarios
  • Admission control: Reject Early some not cost-effective virtual networks
  • Time window: Developping

Implemented Algorithms

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

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

Module Testing

config

• config

data

• data.attribute
• data.network
• data.physical_network
• data.virtual_network
• data.v_net_simulator

solver

• base.recorder
• base.controller
• base.enviroment
• solver.rank.node_rank
• solver.rank.link_rank
• solver.heuristic
• solver.learning.mcts
• ...