Learning-based Solver#

GaeClusteringSolver(controller, recorder, ...)

A unsupervised learning solver that uses Graph Auto-Encoder (GAE) to cluster the physical nodes.

HopfieldNetworkSolver(controller, recorder, ...)

An Unsupervised Learning-based solver that uses Hopfield Network to construct the subgraph.

MctsSolver(controller, recorder, counter, ...)

A Reinforcement Learning-based solver for VNE that uses Monte Carlo Tree Search (MCTS) algorithm.

PgMlpSolver(controller, recorder, counter, ...)

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Multilayer Perceptron (MLP) as the neural network model.

PgCnnSolver(controller, recorder, counter, ...)

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Convolutional Neural Network (CNN) as the neural network model.

PgCnn2Solver(controller, recorder, counter, ...)

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Convolutional Neural Network (CNN) as the neural network model.

PgSeq2SeqSolver(controller, recorder, ...)

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Sequence-to-Sequence (Seq2Seq) as the neural network model.

A3CGcnSeq2SeqSolver(controller, recorder, ...)

A Reinforcement Learning-based solver that uses Advantage Actor-Critic (A3C) as the training algorithm, and Graph Convolutional Network (GCN) and Sequence-to-Sequence (Seq2Seq) as the neural network model.

Unsupervised Learning-based Solver#

GaeClusteringSolver#

Documentation

class virne.solver.learning.GaeClusteringSolver(controller, recorder, counter, num_features=1, num_clusters=4, **kwargs)[source]#

A unsupervised learning solver that uses Graph Auto-Encoder (GAE) to cluster the physical nodes.

References

  • Farzad Habibi et al. “Accelerating Virtual Network Embedding with Graph Neural Networks”. In CNSM, 2020.

Variables:

  • num_features (int) – The number of features of the physical nodes.

  • num_clusters (int) – The number of clusters.

  • argva (ARGVA) – The auto-encoder model.

  • discriminator_optimizer (torch.optim) – The optimizer for the discriminator.

  • argva_optimizer (torch.optim) – The optimizer for the auto-encoder.

  • pretrain_max_epochs (int) – The maximum number of epochs for pre-training.

  • fine_tune_max_epochs (int) – The maximum number of epochs for fine-tuning.

  • max_num_attempts (int) – The maximum number of attempts to find a good clustering.

  • num_arrived_v_nets (int) – The number of virtual networks that have arrived.

sample_from_p_net(cluster_index, cluster_id)[source]#

return a node from one cluste

solve(instance) → Solution[source]#

Solves the problem instance, and returns the solution.

Parameters:

instance (dict) – The problem instance to solve.

Returns:

The solution to the problem instance.

Return type:

Solution (Solution)

HopfieldNetworkSolver#

Documentation

class virne.solver.learning.HopfieldNetworkSolver(controller, recorder, counter, **kwargs)[source]#

An Unsupervised Learning-based solver that uses Hopfield Network to construct the subgraph.

solve(instance)[source]#

Solves the problem instance, and returns the solution.

Parameters:

instance (dict) – The problem instance to solve.

Returns:

The solution to the problem instance.

Return type:

Solution (Solution)

Reinfocement Learning-based Solver#

MctsSolver#

Documentation

class virne.solver.learning.MctsSolver(controller, recorder, counter, **kwargs)[source]#

A Reinforcement Learning-based solver for VNE that uses Monte Carlo Tree Search (MCTS) algorithm.

References

  • Soroush Haeri et al. “Virtual Network Embedding via Monte Carlo Tree Search”. TCYB, 2018.

Variables:

  • computation_budget – the number of times to run the search algorithm

  • exploration_constant – the exploration constant in the UCB1 formula

backpropagate(node, reward)[source]#

Update values of the node’s all predecessors using reward

best_child(node, is_exploration)[source]#

Use the UCB algorithm to blance the exploration and exploitation Return the node with highest value (When inference phase, directly use greedy stratagy)

expand(node)[source]#

Expand a node with random choice policy

search(node)[source]#

Monte Carlo Tree Search

Starting from a root node, find one subnode with highest exploitation value based on the exploration experience

  1. Selection
    Select one worth node to explore. There are three types nodes:

    1. Never visited (2) Uncompleted expanded (3) Completed expanded

  2. Expansion

    Add statistic information to selected node

  3. Simulation

    Get the final reward estimating the quality of visited nodes.

  4. Backpropagation

    Update the exploitation value of visited nodes using the obtained reward

Inference: Selected the subnode with highest exploitation value

select_and_expand(node)[source]#

Based on exploration / exploitation algorithm, get the bast node to expand

  1. Preferentially, select one node never visited (if there are multiple nodes, random select one)

  2. Otherwise, select one node with highest UCB value (exploration / exploitation)

simulate(node)[source]#

Use the random policy to expand the node, and return the final reward

solve(instance)[source]#

Solves the problem instance, and returns the solution.

Parameters:

instance (dict) – The problem instance to solve.

Returns:

The solution to the problem instance.

Return type:

Solution (Solution)

PgMlpSolver#

Documentation

class virne.solver.learning.PgMlpSolver(controller, recorder, counter, **kwargs)[source]#

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Multilayer Perceptron (MLP) as the neural network model.

preprocess_batch_obs(obs_batch)[source]#

Preprocess the observation to adapte to batch mode.

PgCnnSolver#

Documentation

class virne.solver.learning.PgCnnSolver(controller, recorder, counter, **kwargs)[source]#

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Convolutional Neural Network (CNN) as the neural network model.

PgCnn2Solver#

Documentation

class virne.solver.learning.PgCnn2Solver(controller, recorder, counter, **kwargs)[source]#

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Convolutional Neural Network (CNN) as the neural network model. Additionally, more graph features are used as the input of the CNN.

PgSeq2SeqSolver#

Documentation

class virne.solver.learning.PgSeq2SeqSolver(controller, recorder, counter, **kwargs)[source]#

A Reinforcement Learning-based solver that uses Policy Gradient (PG) as the training algorithm and Sequence-to-Sequence (Seq2Seq) as the neural network model.

solve(instance)[source]#

Solves the problem instance, and returns the solution.

Parameters:

instance (dict) – The problem instance to solve.

Returns:

The solution to the problem instance.

Return type:

Solution (Solution)

A3CGcnSeq2SeqSolver#

Documentation

class virne.solver.learning.A3CGcnSeq2SeqSolver(controller, recorder, counter, **kwargs)[source]#

A Reinforcement Learning-based solver that uses Advantage Actor-Critic (A3C) as the training algorithm, and Graph Convolutional Network (GCN) and Sequence-to-Sequence (Seq2Seq) as the neural network model.

References

  • Tianfu Wang, et al. “DRL-SFCP: Adaptive Service Function Chains Placement with Deep Reinforcement Learning”. In ICC, 2021.

solve(instance)[source]#

Solves the problem instance, and returns the solution.

Parameters:

instance (dict) – The problem instance to solve.

Returns:

The solution to the problem instance.

Return type:

Solution (Solution)