baseline-algorithms

Baseline algorithms for coordination of service mesh consisting of multiple microservices. Includes Non-RL algorithms (Random Schedule, Shortest Path, & Load Balance).

Project structure

• src/algorithms: Random Schedule, Shortest Path and Load Balance algorithm implementation.

Algorithms

Random Schedule

• Places all VNFs on all nodes of the networks
• Creates random schedules for each source node, each SFC, each SF , each destination node
• All the schedules for an SF sum-up to 1

Load Balance algorithm

Always returns equal distribution for all nodes having capacities and SFs. Places all SFs on all nodes having some capacity.

Shortest Path algorithm

Based on network topology, SFC, and ingress nodes, calculates for each ingress node:

• Puts 1st VNF on ingress, 2nd VNF on closest neighbor, 3rd VNF again on closest neighbor of 2nd VNF and so on.
• Stores placement of VNFs and avoids placing 2 VNFs on the same node as long as possible. If all nodes are filled, continue placing a 2nd VNF on all nodes, but avoid placing 3 VNFs and so on.
• Avoids nodes without any capacity at all (but ignores current utilization).

Installation

Create a venv

Recommended for development: Clone and install coord-sim and common-utils locally first in the same venv before running the installation of the adapter in the editable mode: pip install -e baseline-algorithms

On your local machine:

# create venv once
python3.6 -m venv ./venv
# activate the venv (always)
source venv/bin/activate

Install dependencies from the main directory of the repo

pip install -r requirements.txt

This also installs the required coord-sim simulator and common-utils package.

Usage

How to run the Random Schedule algorithm against the Simulator

rs -n "res/networks/triangle.graphml" -sf "res/service_functions/abc.yaml" -c "res/config/sim_config.yaml" -i 1000

For more information look at the README of the Random Schedule.

How to run the Load Balance algorithm against the Simulator

lb -n "res/networks/triangle.graphml" -sf "res/service_functions/abc.yaml" -c "res/config/sim_config.yaml" -i 1000

How to run the Load Balance algorithm against the Simulator

sp -n "res/networks/triangle.graphml" -sf "res/service_functions/abc.yaml" -c "res/config/sim_config.yaml" -i 1000

Using the parallel script to run multiple experiments:

There is script provided in the scripts folder that utilizes the GNU Parallel utility to run multiple experiments at the same time to speed up the process. It can run one algorithm at a time, so you need to choose the algo you wanna run at the beginning of the file.

From scripts directory configure the following files:

• network_files: 1 network file location per line
• config_files: 1 simulator config. file location per line
• service_files: 1 SFC file location per line
• 30seeds: 1 seed per run of the simulator. By default using 30 seeds. Add/Remove as per requirement

From the main directory (where the README.md file is) using a Terminal run:

bash scripts/run_parallel

Acknowledgement

This project has received funding from German Federal Ministry of Education and Research (BMBF) through Software Campus grant 01IS17046 (RealVNF).