Bounds for two static optimization problems on routing and spectrum allocation of anycasting

• Published in: Optical switching and networking 2019-01, Vol.31, p.144-161
• Main Authors: Miyagawa, Yasutaka, Watanabe, Yosuke, Shigeno, Maiko, Ishii, Kiyo, Takefusa, Atsuko, Yoshise, Akiko
• Format: Article
• Language: English
• Subjects: Anycast; Elastic optical network; Greedy algorithm; Integer linear programming
• ISSN: 1573-4277; 1872-9770
• DOI: 10.1016/j.osn.2018.10.008

Elastic optical networks with optical-orthogonal frequency division multiplexing have been addressed enthusiastically for communication networks in the last decade because they result in high bandwidth efficiency. Routing and spectrum allocation (RSA) problems need to be solved when we transmit demands in an elastic optical network. This research deals with static RSA models for anycast transmission, which is one-to-one-of-many transmission in inter-datacenter networks. Two static RSA optimization models are considered. One minimizes the maximum number of spectrum slots needed to allocate given demands. The other maximizes the traffic volume of demands served under a given spectrum slot number. For both models, lower and upper bounds are developed in order to obtain exact optimal solutions. One-side bounds of the problems are evaluated by relaxing spectrum continuity constraints. For the other side bounds, several greedy algorithms are investigated. We conducted computational experiments to confirm whether relaxation problems can give tight bounds and to determine greedy algorithmic behaviors by using each of route selection criterion and each of demand ordering policies. The results show that the solutions obtained by relaxing spectrum continuity constraints are almost optimal. They also indicate that exact optimal solutions are obtained efficiently by using these bounds.