/algorithms

Set of algorithm dealing with the problems of VNF placement, SFC/VNF-FG placement and chaining, VNF scaling....

Primary LanguageJava

Algorithms

This guide describes a set of algorithm dealing with the problems of VNF placement, SFC/VNF-FG placement and chaining, VNF scaling.... Then we describe the inputs and output of these algorithms.

Authors:

Copyright (C) Marouane Mechteri

Contents

Placement algorithm

The objective of these optimization algorithms is to place VMs or VNFs intelligently in underlying NFVIs and to steer traffic flows across the VNFs while using efficiently the infrastructure resources.

These algorithms are:

Folders Algorithms Publications
SFC_placement_DP_algos Dynamic Programming algorithms 1
SFC_placement_Eigen_algo An Eigendecomposition-based algorithm 2
SFC_placement_MCTS_algo An algorithm based on Monte Carlo Tree Search (MCTS) 3
SFC_placement_ILP_algo An Integer Linear Programming (ILP) model 4
SFC_placement_Greedy_algo A Greedy algorithm 5
  1. A Dynamic Programming algorithm: A Dynamic Programming Algorithm for Joint VNF Placement and Chaining
  2. An Eigendecomposition-based algorithm: A Scalable Algorithm for the Placement of Service Function Chains
  3. An algorithm based on the Monte Carlo Tree Search (MCTS): An Efficient Algorithm for Virtual Network Function Placement and Chaining
  4. An Integer Linear Programming (ILP) model: A green VNFs placement and chaining algorithm , A Green VNF-FG Embedding Algorithm
  5. A Greedy algorithm: VNF Placement and Chaining in Distributed Cloud

Inputs and Output of the placement algorithms

The inputs of each placement algorithm are:

  • The client request is modeled by a graph composed by a set of virtual nodes representing VNF and a set of virtual links connecting them. instanceIG3-0 is an example of a request composed by 3 VNFs and 2 links and representing a service chain:

    Number of Servers
3 1 1
Nodes
0 0 2 3 1 0
1 1 2 3 1 0
2 2 2 3 1 0
EDGES
0 1 100
1 2 100

  • The substrate graph is modeled also by a graph. instanceRG15-0 is an example of a substrate infrastructure.

The output of the algorithms is a file containing the mapping result of the client request on the substrate infrastructure. The file name of the algorithm output has this format:

SolutionMappingALGO-SUBSTRATE_FILE_NAME-REQUEST_FILE_NAME.

For example, when executing the dynamic programming algorithm the output file name is SolutionMappingDP-instanceRG13-0-instanceIG3-0.