FELL: A flexible virtual network embedding algorithm with guaranteed load balancing

Network virtualization has emerged as the most promising approach to overcome the current ossification of the Internet. A key problem in it is how to efficiently and effectively make use of the substrate network resources by embedding multiple virtual networks with various constraints. Due to its NP-hardness, many heuristic approaches have been proposed. However, most of them simplify the problem by relaxing some constraints, resulting in their designs in conflict with practical limitations. Furthermore, some other important design issues, like load balancing and the response time requirements of different applications, have been usually ignored as well. In this paper, we propose FELL, a Flexible virtual network Embedding algorithm with guaranteed Load baLancing for the general problem. Based on simulated annealing, FELL can flexibly control the tradeoff between results accuracy and running time to meet various requirements of different applications by changing parameters. Load balancing enables substrate network to avoid resource fragmentation and further increases the profit of infrastructure providers. A novel cost criterion that reflects the impact of distribution of allocated resources for an embedding is designed to conduct embedding process to guarantee it. The splittable flow is supported to obtain better resource utilization by making use of small pieces of available bandwidth. We also design some key functions including generating initial and neighbor solutions. The effectiveness of our algorithm is finally validated by our simulations.