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:
r : 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:
r : 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
Random Heuristic Algorithm
Input:
r : 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
procedure Solution (r, available-candidates)
solution_path = null
for each d in r.demands
valid_cands = evaluate_constraints (d, available-candidates[d], solution_path)
solution_path[d] = random candidate from valid_cands
return solution_path