Open AccessExhaustive Search for Optimal Offline Spectrum Assignment in Elastic Optical Networks
Author(s) -
Iyad Katib
Publication year - 2020
Publication title -
international journal of computers, communications and control
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.422
H-Index - 33
eISSN - 1841-9844
pISSN - 1841-9836
DOI - 10.15837/ijccc.2020.5.3933
Subject(s) - solver , heuristic , computer science , spectrum (functional analysis) , algorithm , running time , null move heuristic , mathematical optimization , mathematics , artificial intelligence , physics , quantum mechanics , programming language
Heuristic-based approaches are widely deployed in solving Spectrum Assignment problem. This causes the results to be unreliable in some test cases when the results are very far from the lowerbound. This paper presents an exhaustive search approach that starts with an initial seed of a solution achieved by a heuristic-based algorithm called “Longest First Fit” (LFF) and tries all possible permutations starting from this initial seed. The algorithm skips some branches and all its descendant permutations if it meets certain criteria that guarantees that those permutations will not lead to a better result. The experimental results show that the new algorithm has succeeded in achieving the lower-bound in 93% of the randomly generated test cases while the heuristic solver LFF can achieve 65%. The algorithm achieves these results in a reasonable running time of less than 10 seconds.