changeVnfMapping() when to force delay refreshing

[MartinPJorge]

Currently we force the refreshing of the overall mapping delay in line https://github.com/MartinPJorge/vnfs-mapping/commit/2aa185fd59e11e0918c7f4714b6b6f3dc804472b#diff-1472a8ea1ca72cf39c743574138b7f0fL203

      B      E -- G
   /     \  /
A         D
   \     /  \
     C       F

The problem is to decide when this refreshing must be forced. One may think that if the VNF is a final one, then refresh must not be enforced. And it only must be enforced when it has after VNFs.

But that is not ok, because if F has the highest delay, and the new mapping of E makes G have less delay than F, then the overall delay is updated to be less than it should be.

[MartinPJorge]

An idea that came up was the following:

The refreshing must not be forced if the VNF that is remapped is within a final branch. But that is not correct, since the branch where the VNF is in, can be the one that induces the maximum delay to the NS chain. Then, if the new VNF mapping reduces the delay in the final branch where it is, the NS delay won't be refreshed, since we didn't force it, and the newer delay is less than the previous one (newDelay < delay).

[MartinPJorge]

The solution is:

• Store branchHeads list in the NS class.
• The NS class can have a dictionary of branchHeads with its delay.
• When a VNF is remapped, perform DFS on next VNFs. When a branchHead VNF is reached, it does the following:

  
  maxDelay = currVNFNewDelay
  for headVNF in branchHeads:
  if headVNF != currVNF and headVNFDelay > currVNFDelay:
  maxDelay = headVNFDelay

self.__mappingDelay = maxDelay # Set the NS chain delay

[MartinPJorge]

Commit d0a9d34c7360e4975c68c2cb6bc5c96c798b3ad2 implements this idea. It solves:

• Proper calculation of overall delay.
• Tabu search test work (1 iteration over the whole NS chain).