A unified framework for virtual network embedding.
Project description
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.
Release History
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
v0.4
Construct the documentation, refactor the stucture, add comments and fix the bug about RNN-based VNE solverv0.3
Refactor the stucture and release several algorithms (including exact, heuristic, meta-heuristic, and learning-based methods)v0.2
Release one Model-base RL (MCTS) approach and one Model-free RL (PG-CNN) algorithmv0.1
Release the implementation of environment and some heuristics-based solvers for VNE problem
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
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
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.
Implemented Algorithms
Virne has implemented the following heuristic-based and learning-based algorithms:
Learning-based Solvers
*
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 |
Quick Start
The structure of this framework are still optimized steadily. We will construct the first version of the document as soon as possible until stability is ensured.
Installation
Complete installation
# only cpu
bash install.sh -c 0
# use cuda (optional version: 10.2, 11.3)
bash install.sh -c 11.3
Selective installation
Necessary
pip install networkx numpy pandas ortools matplotlib pyyaml
Expansion
# for deep learning
# use cuda
conda install pytorch torchvision torchaudio cudatoolkit=11.3 -c pytorch
# only cpu
conda install pytorch torchvision torchaudio -c pytorch
# for reinforcement learning
pip install gym==0.19.0 stable_baselines3 sb3_contrib
# for graph neural network
conda install pyg -c pyg -c conda-forge
# install the lastest scipy
pip install --force-reinstall scipy
Minimal Example
import os
from config import get_config, show_config, save_config, load_config
from data import Generator
from base import BasicScenario
from solver import REGISTRY
# 1. Get Config
# The key settings are controlled with config.py
# while other advanced settings are listed in settings/*.yaml
config = get_config()
# generate p_net and v_net dataset
Generator.generate_dataset(config)
# 2. Generate Dataset
# Although we do not generate a static dataset,
# the environment will automatically produce a random dataset.
p_net, v_net_simulator = Generator.generate_dataset(
config,
p_net=False,
v_nets=False,
save=False) # Here, no dataset will be generated and saved.
# 3. Start to Run
# A scenario with an environment and a solver will be create following provided config.
# The interaction between the environment and the solver will happen in this scenario.
print(f"\n{'-' * 20} Start {'-' * 20}\n")
# load Env and Solver
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')
# create scenario with Env and Solver
scenario = BasicScenario.from_config(Env, Solver, config)
scenario.run()
print(f"\n{'-' * 20} Complete {'-' * 20}\n")
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
- ...
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.