Heuristic Solver

OrderRankSolver(controller, recorder, ...)	A node ranking-based solver that use the order of nodes in the graph as the rank.
RandomRankSolver(controller, recorder, ...)	A node ranking-based solver that randomly rank the nodes.
FFDRankSolver(controller, recorder, counter, ...)	A node ranking-based solver that use the First Fit Decreasing (FFD) metric to rank the nodes.
GRCRankSolver(controller, recorder, counter, ...)	A node ranking-based solver that use the Global Resource Capacity (GRC) metric to rank the nodes.
RandomWalkRankSolver(controller, recorder, ...)	A node ranking-based solver that use the random walk (RW) algorithm to rank the nodes.
NRMRankSolver(controller, recorder, counter, ...)	A node ranking-based solver that use the Network Resource Metric (NRM) metric to rank the nodes.
PLRankSolver(controller, recorder, counter, ...)	A node ranking-based solver that use the node proximity sensing and path comprehensive evaluation algorithm to rank the nodes.
OrderRankBfsSolver(controller, recorder, ...)	A BFS-based Node Rank solver that ranks nodes by their order in the graph.
RandomWalkRankBfsSolver(controller, ...)	A BFS-based Node Rank solver that ranks nodes with random walk algorithm.
RandomRankBfsSolver(controller, recorder, ...)	A BFS-based Node Rank solver that ranks nodes randomly.

Two-stage Mapping Node Ranking-based Solver

OrderRankSolver

Documentation

class virne.solver.heuristic.OrderRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that use the order of nodes in the graph as the rank.

- solve

solve the problem instance.

- node_mapping

place virtual nodes onto appropriate physical nodes.

- link_mapping

route virtual links onto appropriate physical paths.

RandomRankSolver

Documentation

class virne.solver.heuristic.RandomRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that randomly rank the nodes.

FFDRankSolver

Documentation

class virne.solver.heuristic.FFDRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that use the First Fit Decreasing (FFD) metric to rank the nodes.

GRCRankSolver

Documentation

class virne.solver.heuristic.GRCRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that use the Global Resource Capacity (GRC) metric to rank the nodes.

References

• • Gong et al. “Toward Profit-Seeking Virtual Network Embedding solver via Global Resource Capacity”. In INFOCOM, 2014.

Variables:

• sigma (-) – the sigma parameter in the GRC metric.

• d (-) – the d parameter in the GRC metric.

RandomWalkRankSolver

Documentation

class virne.solver.heuristic.RandomWalkRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that use the random walk (RW) algorithm to rank the nodes.

References

• Cheng et al. “Virtual Network Embedding Through Topology-Aware Node Ranking”. In SIGCOMM, 2011.

Variables:

• sigma – The probability of teleporting to a random node.

• p_J_u – The probability of jumping to a random neighbor of u.

• p_F_u – The probability of following a random neighbor of u.

NRMRankSolver

Documentation

class virne.solver.heuristic.NRMRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that use the Network Resource Metric (NRM) metric to rank the nodes.

References

• Zhang et al. “Toward Profit-Seeking Virtual Network Embedding solver via Global ResVirtual Network Embedding Based on Computing, Network, and Storage Resource Constraintsource Capacity”. IoTJ, 2018.

PLRankSolver

Documentation

class virne.solver.heuristic.PLRankSolver(controller: Controller, recorder: Recorder, counter: Recorder, **kwargs)

A node ranking-based solver that use the node proximity sensing and path comprehensive evaluation algorithm to rank the nodes.

References

• Fan et al. “Efficient Virtual Network Embedding of Cloud-Based Data Center Networks into Optical Networks”. TPDS, 2021.

node_mapping(v_net, p_net, solution)

Attempt to accommodate VNF in appropriate physical node.

BFS-based Mapping Node Ranking-based Solver

OrderRankBfsSolver

Documentation

class virne.solver.heuristic.OrderRankBfsSolver(controller: Controller, recorder: Recorder, counter: Counter, **kwargs)

A BFS-based Node Rank solver that ranks nodes by their order in the graph.

solve(instance: dict) → 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)

RandomRankBfsSolver

Documentation

class virne.solver.heuristic.RandomRankBfsSolver(controller: Controller, recorder: Recorder, counter: Counter, **kwargs)

A BFS-based Node Rank solver that ranks nodes randomly.

solve(instance: dict) → 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)

RandomWalkRankBfsSolver

Documentation

class virne.solver.heuristic.RandomWalkRankBfsSolver(controller: Controller, recorder: Recorder, counter: Counter, **kwargs)

A BFS-based Node Rank solver that ranks nodes with random walk algorithm.

References

• Cheng et al. “Virtual Network Embedding Through Topology-Aware Node Ranking”. In SIGCOMM, 2011.

solve(instance: dict) → 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)