A thesis on virtual network embedding with genetic algorithms

Recently I finished my master thesis which is a study on the problem of virtual network embedding (VNE). It concerns the virtualization of network resources and topologies so as to create a fully functional virtual network embedded in a detacenter, instead of using a physical stand alone network. There are many advantages in this approach as it is much easier to update and maintain virtual devices and links instead of physical ones.

There are many ways to map virtual on physical resources, a relatively small virtual topology may be embedded in many ways in the physical network of a datacenter. The problem of VNE concerns the finding of the ideal mapping so that virtualized network will have the optimal performance.

It is a hard problem to solve so traditional analytical methods are inefficient for its solution. Artificial intelligence methods provide in such cases good and efficient solutions. In the thesis I developed a genetic algorithm that approaches the problem as an optimization problem and provides good practical solutions. 

My thesis is written in Greek and is accessible in the repository of the Hellenic Open University.  A direct download of the paper is possible in this link.

A Fibonacci complexity class

While working on a project that will come out soon, I developed an algorithm with strange asymptotic behavior. In one of the functions of the algorithm there was an arithmetic progression that had to be computed. It was not a big deal as it concerned small sets of numbers each time, at least that's what I thought.

So instead of using the formula of arithmetic progression, I just put a recursive function for it. Something like

int d = 1000;
public void progression(a){
    while(d>0){
         progression(a+1);
    }
    d--;

}
progression(0);

Where d was proportional to the input.

It worked fine, but it was slower than it should be. The reason was that the progression was computed quite a lot of times and eventually such a simple function was a huge computation burden. I was really surprised to discover that the asymptotic behavior of the algorithm could be described by the Fibonacci sequence.
So that, given n input the complexity of the algorithm was O(f(n)∙c), where f(n) is the n-th member of the Fibonacci sequence and c is constant.
After replacing the function with the formula of arithmetic progression the complexity became polynomial, thankfully. 

There are two remarks about all these.

An innocent, simple and naive function may become a problem. We have to be careful on how many times this function will be executed.

Although the first edition of the algorithm was not optimal, there comes the question. Could we define a Fibonacci complexity class? Perhaps even find problems in this class.