HA-VNF

HA-VNF is a software to design networks and perform an automatic and reliable placement of Virtual Network Functions.

Requirements

HA-VNF requires:

• Java 8
• python 2.7
• python PuLP library

Instructions

The ZIP file contains the Java GUI to design the network, the Python algorithms to optimize the placement, this README file, and an example of a network that can be opened from our tool.

HA-VNF.jar and the algorithms folder must be placed in the same directory to run the automatic placement:

parent_folder
|  
|---algorithms/  
|---HA-VNF.jar  
|---README.md  
|---network

Run the HA-VNF.jar file to run the tool:
$> java -jar HA-VNF.jar

Optimization algorithms

The optimization algorithms run independently from the Java GUI. We deliver 5 optimization algorithms:

• best fit: implementation of the greedy heuristic best fit for the Bin Packing Problem (BPP) that iteratively assigns each requests to the server minimizing the remaining residual computing resources;
• worst fit: implementation of the greedy heuristic worst fit for the Bin Packing Problem (BPP) that iteratively assigns each requests to the server maximizing the remaining residual computing resources;
• first fit: implementation of the greedy heuristic first fit for the Bin Packing Problem (BPP) that iteratively assigns each requests to the first available server;
• best availability: variant of the greedy heuristics for the Bin Packing Problem (BPP) that iteratively assigns each requests to the server with highest availability;
• variable neighborhood search: metaheuristic that implements local search algorithms and iteratively switches between neighborhoods.

Each heuristic is packed in a single Python file:

• best fit -> bestfit_heuristic.pyo;
• worst fit -> worstfit_heuristic.pyo;
• first fit -> random_heuristic.pyo;
• best availability -> greedy_heuristic.pyo;
• variable neighborhood search -> vns_heuristic.pyo.

To run an algorithm:

$> python -O algorithm_file.pyo input_file.ampl.dat split protection objective output_file.ampl.out

where

• algorithm_file.pyo is the name of the file with the desired algorithm;
• input_file.ampl.dat is the path to the input file in AMPL format (extension ampl.dat is mandatory);
• split is a boolean True or False saying if demands can be split (not supported by the tool, only by the optimiaztion algorithms);
• protection is a boolean True or False saying if protection is enabled and slaves are placed or not;
• objective is the type of the objective function used during the optimization phase and can be either Penalty or Availability;
• output_file.ampl.out is the path to the output file that will contain the result of the optimization algorithm in AMPL format (extension ampl.out is not mandatory).

Examples:

$> python -O vns_heuristic.pyo input.ampl.dat False True Availability output.out

Run the variable neighborhood search algorithm over a network contained in input.ampl.dat maximizing the availability and saving the results in output.out.

$> python -O greedy_heuristic.pyo input.ampl.dat False False Penalty output.out

Run the greedy algorithm with a best availability policy over a network contained in input.ampl.dat minimizing the penalty, without placing slaves, and saving the results in output.out.

Input format

The input file is a text file in AMPL format containing all the informations about the components of the infrastructure (computing resources, link connections, availabilities, ...).

An input file starts with the declaration of the number of components in the infrastructure:

param REQUESTS := 5;
param SERVERS := 3;
param CLUSTERS := 3;
param RESOURCES := 1;
param FUNCTIONS := 3;
param ACCESS_POINTS := 2;

Where

• REQUESTS is the number of the client requests;
• SERVERS is the number of servers (a server is component with computing resources that can run a VNF);
• CLUSTERS is the number of clusters (not supported by the tool which considers each server as a single cluster);
• RESOURCES is the number of types of computing resources of each server (CPU, RAM, ...). Our tool considers a single resource;
• FUNCTIONS is the number of VNF types;
• ACCESS_POINTS is the number of access points of our infrastructure.

Then a parameter sets the desired SLA of the infrastructure.
param SLA := 0.999990;
When the objective of the optimization is to minimize the penalty, a penalty is paid for each request that does not met SLA.

The parameter availability_f is the vector of the VNF availabilities, that is the probability that the software implementing a VNF will not crash due to software bugs:

param availability_f{F};  
param availability_f :=
1 0.999990
2 0.999990
3 0.999990
;

Parameter availability_s is the vector of the availabilities of the servers:

param availability_s{S};  
param availability_s :=
1 0.999900
2 0.999500
3 0.999000
;

Parameter availability_c is the probability that a cluster is accessible. In our Java tool each server corresponds to a single cluster, but in general a cluster may contain many servers.

param availability_c{C};  
param availability_c :=
1 0.997505
2 0.998000
3 0.999000
;

Parameter availability_link_cc and availability_link_ac are matrices of links availabilities: the former declares the availabilities of links connecting clusters to clusters, while the latter declares the availabilities of links between access points and clusters:

param availability_link_cc{C,C};  
param availability_link_cc : 1 2 3 :=
1 1.0 0.998708424146 0.999382879775
2 0.998708424146 1.0 0.999030657717
3 0.999382879775 0.999030657717 1.0
;  

param availability_link_ac{A,C};  
param availability_link_ac : 1 2 3 :=
1 0.999075820271 0.99899928098 0.999149014679
2 0.999427250961 0.999251508336 0.998967231901
;

Parameters penalty_r and function_r define the penalty paid when a request does not meet the SLA value and the VNF type required by a request, respectively.

param penalty_r{R};  
param function_r{R};  
param : penalty_r function_r :=
1 10.000000 2
2 10.000000 1
3 100.000000 3
4 30.000000 1
5 1.000000 2
;

Parameter apoints is a matrix having a 1 if a request can use an access point. Each request may use several access points.

param apoints{R,A};
param apoints : 1 2 :=
1 1 1
2 0 1
3 1 0
4 1 0
5 0 1
;

Param d is the demand of computing resources required by each request:

param d{R,K};  
param d : 1 :=
1 5.000000
2 9.000000
3 3.000000
4 10.000000
5 5.000000
;

Param q is the matrix declaring the amount of computing resources of each server:

param q{S,K};
param q : 1 :=
1 122.000000
2 91.000000
3 113.000000
;

Finally, parameter server_cluster associates servers to clusters:

param server_cluster{S};
param server_cluster :=
1 1 
2 2 
3 3 
;