Simulated annealing algorithm for virtual network reconfiguration

Network virtualization has evoked interest among researchers as a promising solution for developing flexible and manageable architectures for future Internet. One of the major challenges in network virtualization is the efficient allocation of substrate resources to the Virtual Networks (VNs) - a problem known as Virtual Network Embedding (VNE). Most of the past research on VNE has been focused on algorithms to allocate resources to VNs. The problem of reconfiguration, however, is relatively less explored. In this paper, we propose a simulated annealing algorithm for reconfiguring the VNs in order to balance the load across the substrate network, thereby reducing the peak node and link load on the substrate network. Through extensive simulations we evaluate the proposed reconfiguration algorithm and show that after reconfiguration there is a 20% reduction in maximum link load and 5% reduction in maximum node load. The average link load is reduced by 50% and the fraction of links having a load above 50% is reduced from 66% to 14%. We also show that periodic reconfiguration leads to a significant improvement in the acceptance ratio of VN requests.