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 Convolutional Neural Network (CNN) 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.

Unsupervised Learning-based Solver

GaeClusteringSolver

Documentation

class virne.solver.learning.GaeClusteringSolver(controller, recorder, counter, logger, num_features=1, num_clusters=4, **kwargs)

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)

return a node from one cluste

solve(instance) → Solution

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, logger, config, **kwargs)

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

solve(instance)

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, logger, config, **kwargs)

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)

Update values of the node’s all predecessors using reward

best_child(node, is_exploration)

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)

Expand a node with random choice policy

search(node)

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)

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)

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

solve(instance)

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, logger, config, **kwargs)

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

PgCnnSolver

Documentation

class virne.solver.learning.PgCnnSolver(controller, recorder, counter, logger, config, **kwargs)

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, logger, config, **kwargs)

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.