Achieving Optimized Embedding of Virtual Networks by Incremental Evolution

Finding a configuration to embed a virtual network in a substrate network is a well-known problem. The increased complexity of networks and the agility required for their adaptation to dynamic demands have raised the importance of the embedding problem. In this paper we propose an algorithm that resolves the problem between three to six times faster than previous work. By theoretical analysis we demonstrate formally that using a genetic algorithm reduces the upper boundary of the problem to a lower order of complexity than it was previously envisioned. We exploit this finding to design our algorithm as a customized genetic algorithm and a particular heuristic to achieve its improvement. Our algorithm also uses a specific strategy to carefully choose the configurations from the search space to be analyzed. It is based on the concept of checking the heuristic function while constructing each configuration. In addition, our algorithm minimizes the difference between the current configuration and the new configuration. The result is that the virtual network evolves iteratively towards its optimum configuration. We validate our findings by executing a proof-of-concept implementation of our algorithm and comparing its performance with previous work.