Integer Programming, Constraint Programming, and Metaheuristic Approaches for Static Optimization of Anycast Flows in Elastic Optical Networks

摘要

Elastic optical network (EON) is a novel optical technology introduced recently to provide flexible and multi-bitrate data transmission in the optical layer. Since many new network services including cloud computing and content delivery networks are provisioned with the use of specialized data centers located in different network nodes, in place of one-to-one unicast transmission, the anycast transmission defined as one-to-one-of-many gains much popularity as a quite simple way to improve network performance. Therefore, this article focuses on modeling and static optimization of anycast flows in EONs. In particular, a NP-hard Routing and Spectrum Allocation for Restoration of Any-cast Flows (RSA/RAF) problem is formulated. Next, various optimization approaches are proposed to solve this problem, namely, integer linear programming (ILP) using branch and bound algorithm, constraint programming (CP), and various heuristic approaches. Extensive numerical experiments are run to evaluate and compare all proposed methods. The main conclusion is that in some cases the CP approach is more efficient than the ILP modeling. Moreover, the results show that the SA algorithm significantly outperforms other heuristic methods.