Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: added initial pseudo-code for algorithms

This page provides the pseudo-implementation of three optimization heuristics for the homing and allocation service. The main idea is to incrementally explore the set of candidates (see incremental algorithm), and decouple this logic from any optimization heuristic such that any heuristic can be plugged in.



Incremental Algorithm

Input:

: instance of a homing request consisting of demands (VNFs), constraint(s), objective function(s), and set of initial candidates for each demand.

p : instance of a heuristic algorithm (e.g., best-fit, exhaustive)

step : incremental step (candidate subset) size

tol_thresh : local solution tolerance threshold

procedure FindSolution (r, p, step, tol_thresh)

RankCandidates(r)

best = null

tolerance = 0

Start with empty available-candidates set for each of the demands

while True do

if stopping_criteria then

break

for each d in r.demands do

increment available-candidates[d] by step

sol = p.solution(r, available-candidates)

if sol = null then

step = step * 2

continue

step = original size

if first solution or sol is better than best then

best = sol

tolerance = 0

else

tolerance ++

return best


Backtracking Best-fit (BACBF) Algorithm

Input:

: instance of a homing request consisting of demands (VNFs), constraint(s), objective function(s), and set of initial candidates for each demand.

available-candidates : list of available candidates to be evaluated for each of the demands in r

solution_path: currently assigned candidates for demands

procedure Solution (r, available-candidates, solution_path)

if r.demands is empty then

return solution_path

d = r.demands.pop()

valid_cands = evaluate_constraints (d, available-candidates[d], solution_path)

sorted_cands = r.obj_func.compute(valid_cands)

A:

best_candidate = sorted_candidates.pop()

if best_candidate is null then

// backtrack: force previous demand to select different candidate

r.demands.add(d)

return null

solution_path[d] = best_candidate

solution = Solution(r, available-candidates, solution_path)

if solution is null then

remove best_candidate from candidate lists

else

return solution

go to A