INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL Online ISSN 1841-9844, ISSN-L 1841-9836, Volume: 15, Issue: 5, Month: October, Year: 2020 Article Number: 3933, https://doi.org/10.15837/ijccc.2020.5.3933 CCC Publications Exhaustive Search for Optimal Offline Spectrum Assignment in Elastic Optical Networks I. Katib Iyad Katib Department of Computer Science King Abdulaziz University, KSA Jeddah P.O. Box : 80200 iakatib@kau.edu.sa Abstract Heuristic-based approaches are widely deployed in solving Spectrum Assignment problem. This causes the results to be unreliable in some test cases when the results are very far from the lower- bound. This paper presents an exhaustive search approach that starts with an initial seed of a solution achieved by a heuristic-based algorithm called “Longest First Fit” (LFF) and tries all possible permutations starting from this initial seed. The algorithm skips some branches and all its descendant permutations if it meets certain criteria that guarantees that those permutations will not lead to a better result. The experimental results show that the new algorithm has succeeded in achieving the lower-bound in 93% of the randomly generated test cases while the heuristic solver LFF can achieve 65%. The algorithm achieves these results in a reasonable running time of less than 10 seconds. Keywords: Elastic Optical Network (EON), exhaustive search, Spectrum Assignment (SA), Routing and Spectrum Assignment(RSA). 1 Introduction Elastic Optical Network (EON) is one of the most challenging networks to manage. It has a huge number of resources that needs to be optimally managed. Efficient routing, modulation, and spectrum allocation techniques should be developed to exploit the huge potential of EON to optimally utilize of the optical fiber bandwidth [6]. The Spectrum Assignment (SA) is one of the challenges that affect a successful EON implementation. This is since spectrum assignment may cause fragmentation over time which in turn results in denial of new traffic requests. This happens when there is no sufficient continuous, and contiguous frequency slots available that meets the EON criteria which basically has three conditions discussed in [6]. Suitable number of frequency slots should be assigned to a traffic demand going from source s to destination d in an elastic optical network. Frequency slots should be proportional to the bit rate of the traffic demand and the total distance that will be traveled as this will affect the deployed modulation technique. Those slots must be contiguous and the same frequency slots must be allocated https://doi.org/10.15837/ijccc.2020.5.3933 2 on all the links that will carry this traffic demand. This is because the traffic will be optically routed using Wavelength Selective Switching (WSS) and Reconfigurable Optical Add/Drop Multiplexing (ROADM). There is no Electrical to Optical (E2O) conversion in the intermediate network nodes. The Routing and Spectrum Assignmen (RSA) problem has many characteristics that makes it very difficult to be solved, most of the work presented target partial problem of the general RSA problem. Either they target static traffic demands or dynamic, also different modulation techniques or fixed modulation technique those factors affects the complexity of the RSA problem. There are many trials to solve the spectrum assignment problem and all of them are using heuristics algorithms as per the survey papers [9, 15]. In literature, the SA problem is defined in many forms either as Integer Linear Programming (ILP) which targets the RSA problem as in [1, 10, 12, 13, 17] or as a special case of the task scheduling problem on multiprocessor systems as in [3, 4]. These problem formulations are not suitable for a scalable exhaustive search that finds the optimal solution for the SA problem. This paper uses a new formulation that will lead to the use of the branch and bound algorithm to find the optimal solution in a scalable manner. The rest of this paper is organized as follows: Section II provides a new description to the problem. Section III will present some related work. Section IV presents the exhaustive search algorithm and how it can use the branch and bound algorithm. Section V presents the results and the success rate of the branch and bound approach to find the optimal allocation. Finally, section VI provides the concluding remarks. 2 Problem definition Offline Spectrum Assignment problem in EON assumes that all traffic demands in the network is already known where all the traffic demands are represented as bit rate. the route which will be used to carry each traffic demand is fixed by using the shortest path algorithm as the routing problem is not investigated in this paper. Given that the route for each traffic demand is defined and the bit rate is known then we can choose the most suitable modulation technique to fulfil this traffic demand. This leads to convert the unit of the traffic demand matrix from bit rate unit to number of frequency slots matrix which allows the traffic demand matrix to be translated from bit rate to frequency slots. This assumption allows us to only focus on the spectrum assignment problem and isolate it from any other part of the EON problems. The SA problem is defined as a set of traffic demands T where each traffic demand ti,j is a binary vector of the links of the traffic path pi,j and each link in the path has the same number of frequency slots F Si,j. This is shown in (1), (2), and (3) T = {ti,j : where i 6= j and traf f ic source is i and destination is j ∀i, j ∈ N} (1) Pi,j = [pk : where pk = 1 if link k will be included in path f rom i to j ∀k ∈ L] (2) ti,j = F Si,j ∗ Pi,j (3) The goals of SA and RSA are overlapped in many cases but not necessarily give the same results. The RSA goal is to minimize the number of used frequency slots regardless of fragmentation [10], [7], [11]. On the other hand, the SA goal is to maximize the number of contiguous free frequency slots on all links i.e.; same frequency slot must be free on all links to form a contiguous free spectrum on all links to avail the acceptance of new traffic in the future [4], [3], [16]. This work will focus on the concept of maximizing the number of free FS on all the links. To achieve this goal, the FS allocation matrix will be defined as in (4). Initially the matrix will be set to a zero matrix and the final goal it to fulfill all traffic demands while keeping the rightmost columns zeros. Fayez et. al. showed in [3] that the lower-bound which ignores any fragmentation can be calculated in linear time, however the lower-bound is not an achievable goal as in many cases as we cannot avoid fragmentation. The make-span which allocates actual FSs to each traffic demand after considering all EON constraints cannot be less than the lower-bound. The goal of this problem is to find the lowest possible make-span in a specific time interval. https://doi.org/10.15837/ijccc.2020.5.3933 3 S = [Si,j : Si,j = { 0 slot j on link i is free k if traffic k will be carried on this link where i ∈ L and j ∈ F Scount] (4) 3 Related work Integer Linear Programming (ILP) models are widely deployed in finding exact solution for SA. However, those solutions face sever difficulties to scale to real problems of commercial networks. Heuristic-based approaches are investigated and applied to large networks. In fact, most heuristic al- gorithms did not provide enough information to justify the accuracy of the solution [8]. Prominently, such heuristic-based solutions are usually exceptional designs that are well customized to the problem under investigation. Although it may be possible to adjust such approaches to other problem alterna- tives, both the initial design and the amendments require expertise not only in networking and theory of graphs but in several domains such as operations research, mathematical programming, and discrete optimization. Consequently, currently available approaches require substantial amount of computing resources and investment in human expertise. This in turn restricts the ability to explore the impact of the decisions of design to predict demands and both capital and operational cost estimates. Ramamurthy et. al in [14] tried fixed routing table to avoid solving the RSA problem and focus only on Spectrum Assignment. In this work, they showed that another alternative routing table would yield better results. They computed the fixed routing table based on Dijkstra’s shortest path algorithm [2]. The presented spectrum assignment algorithms presented in [14] is heuristic-based which has very low complexity. The static RSA problem with estimated traffic has been solved as an ILP problem using heuristic- based approach by Klinkowski et al. [10]. Characterizing the performance of the proposed approach was very difficult. It does not scale to other problem variants [5]. Four different SA techniques for the path network have been proposed by S. Talebi et al. [16]. This research has succeeded to achieved some progress in heuristic-based algorithms however impractical path network topology was selected as a case study which in turn has led to an easy to solve problem. 4 Methodology An example of how permutations of the traffic demands affect the make-span of the algorithm will be discussed to illustrate the main idea of the algorithm. Table 1 shows an example of 4 traffic demands 1; the characteristics of each traffic demand are shown in Table 2. The lower-bound is the maximum number of non-zero count on each row in matrix defined in (4). Table 1 shows 6 FS found in link/row 2, 5, 6, and 7. The traffic demands are fulfilled based on their index and this caused the make-span (max non-zero FS index) to be 8 FS. So, the make-span is 33.3% away from the lower- bound. Another permutation that is shown in Table 3 and resulted in the allocation that is shown in Table 4 indicates that the make-span equals to lower-bound which mandates that the search should be stopped as we found one permutation that will yield the best achievable goal if possible. The main idea of the algorithm is that we need to start with initial traffic demands table that is sorted based on a sorting function that will increase the possibility of hitting the target make-span in minimal number of permutations. The algorithm starts sorting the traffic demands based on longest first, this means traffic demands that requires more frequency slots will be processed first. This would cause any fragmentations at the beginning of the recursive function to affect the make-span and make it bigger than the lower-bound. This would cause the recursive function to exit this permutation and all its descendants and start another permutation that begins with different combination. The Recursive Spectrum Assignment Permutation RSAP algorithm is shown in Algorithm 1. It assumes the traffic demands array is already sorted based on longest first sorting function. The recursive function calls itself multiple times to try to fit one more traffic request into the frequency slots matrix. To avoid saturating the 1color coded and numbered for b/w printout https://doi.org/10.15837/ijccc.2020.5.3933 4 Table 1: Example of 4 Traffic demands after being allocated to the required Frequency Slots (FSs) Links FS1 FS2 FS3 FS4 FS5 FS6 FS7 FS8 FS9 FS10 1 1 1 0 0 0 0 0 0 0 0 2 1 1 3 3 3 3 0 0 0 0 3 2 2 2 2 0 0 0 0 0 0 4 0 0 0 0 0 0 4 4 0 0 5 2 2 2 2 0 0 4 4 0 0 6 0 0 3 3 3 3 4 4 0 0 7 0 0 3 3 3 3 4 4 0 0 Table 2: Example traffic demands permutation 1 Traffic Demand Links to pass through Number of FS required 1 1,2 2 2 3,5 4 3 2,6,7 4 4 4,5,6,7 2 Table 3: Example traffic demands permutation 2 Traffic Demand Links to pass through Number of FS required 3 1,2 2 2 3,5 4 1 2,6,7 4 4 4,5,6,7 2 Table 4: Example of 4 traffic demands after being allocated to the required frequency slots (FS) with another permutation Links FS1 FS2 FS3 FS4 FS5 FS6 FS7 FS8 FS9 FS10 1 0 0 0 0 3 3 0 0 0 0 2 1 1 1 1 3 3 0 0 0 0 3 2 2 2 2 0 0 0 0 0 0 4 0 0 0 0 4 4 0 0 0 0 5 2 2 2 2 4 4 0 0 0 0 6 1 1 1 1 4 4 0 0 0 0 7 1 1 1 1 4 4 0 0 0 0 matrix, the number of columns in the matrix is equal to the make-span of the best know heuristics algorithm in the literature [3]. If the matrix gets saturated, then the recursive function will roll back and try another permutation as shown in Algorithm 1 lines 13 and 14. Once all traffic requests are allocated the make span of this permutation is compared with the lower bound. If RSAP succeed to find make span equals to the lower bound, then the recursive function exits as shown in Algorithm 1 lines 2-7. The worst-case scenario is that RSAP finds the best possible solution, but it is not equal to the lower-bound, this means the RSAP will keep evaluating other permutations in hope of reaching the lower-bound. This would cause the running time of the algorithm to be O(N)=N!*L ; as it will evaluate all possible permutations and each one would require processing L links to mark the traffic demand as fulfilled then mark it again as unfulfilled to roll back to try another permutation. 5 Results The RSAP algorithm is evaluated against NSFNet 14-node topology shown in Figure 1 with simulation of traffic matrix having 3 different probability distributions which are: https://doi.org/10.15837/ijccc.2020.5.3933 5 Algorithm 1 Recursive Spectrum Assignment Permutations RSAP(T, FS, Depth, LB, Makespan) Require: T : sorted array of traffic demands Require: F S: Matrix of free slots on each link Require: Depth: Number of fulfilled demands Require: LB: Lower bound Require: M akespan: the make span of the fulfilled demands till now 1: Begin 2: if |T| = Depth then . FS is a complete permutation 3: if Makespan = LB then 4: FS2 = FS 5: end if 6: Return 7: end if 8: for t in T do 9: if t is fulfilled Continue 10: Frequency = AllocateFS(t, FS) 11: MarkFulfilled(t) 12: RSAP(T, FS, Depth+1, LB, max(Makespan, Frequency)) 13: DeallocateFS(t, FS) 14: MarkUnfulfilled(t) 15: end for 16: End 0 1 2 3 5 4 6 7 8 9 10 13 11 12 Figure 1: The 14-node NSFNet topology 1. Uniform: equal probability is assumed to the selected five bit rates 10; 40; 100; 400; 1000. 2. Skewed low: lower bit rates are given higher probability to be selected. The five bit rates 10; 40; 100; 400; 1000 are selected with probability 0:30; 0:25; 0:20; 0:15, and 0:10, respectively. 3. Skewed high: higher probability is given to higher bit rates. The bit rates 10; 40; 100; 400; 1000 are selected with probability 0:10; 0:15; 0:20; 0:25, and 0:30, respectively. Finally, each traffic demand’s bit rate is translated to corresponding frequency slots as per 5 which assumes the modulation technique to be QPSK as it supports the longest possible distance. As shown in Table 6, RSAP was able to reach the lower-bound in more trials than the LFF algorithm. However, some trials did not converge in a reasonable time which caused the average wall time for RSAP to be higher than the LFF. LFF finishes in less than 0.1 second on the other hand RSAP hit the wall time of 10 seconds in 23 trials out of 300, because it did not reach the lower-bound; this does not necessarily mean it failed to find a good make span but it was mandatory to keep searching in the remaining permutations. In all the trials RSAP either found the same make span as LFF or found a better one. The 23 trials that hit the wall time of 10 seconds were inspected with https://doi.org/10.15837/ijccc.2020.5.3933 6 Table 5: Bit rate conversion table Bit rate FS Count 10 1 40 1 100 2 400 8 1000 20 Table 6: Comparison of results with LFF Probability Distribution RSAP Success Rate LFF Success Rate RSAP Avg. Time (Sec.) LFF Avg. Time (Sec.) Normal 93% 55% 0.8 < 0.1 High Skew 91% 61% 1.03 < 0.1 Low Skew 93% 81% 0.77 < 0.1 larger wall time of 2 hours and 4 hours and the make span did not change. Which means the wall time of 10 seconds were enough to prove that those trails will not converge using the proposed algorithm. 6 Conclusion This paper has presented a new algorithm that starts with initial sorted traffic demands. This has helped the recursive function to converge in more than 90% of the trials in less than 10 seconds (wall time). This means that the lower-bound was achieved. The remaining 10% is still a challenge whether it has a solution equivalent to the lower-bound or not. Those trials can be investigated with different sorting functions. The main advantage of this approach is that it preserves at least the same level of accuracy achieved by heuristic-based approaches or better for those test cases that did not converge. Moreover, the convergence rate is much higher that the heuristic-based approaches. Even though 90% of problem instances were solved, this paper shows a potential in the future to find an optimal solution for the unsolved problem instances. Acknowledgement Computation for the work described in this paper was supported by King Abdulaziz University’s High Performance Computing Center (Aziz Supercomputer) (http://hpc.kau.edu.sa). Conflict of interest The author declare no conflict of interest. References [1] Chen, H.; Zhao, Y.; Zhang, J.; Wang, W.; Zhu, R. (2017). Static routing and spectrum assignment for deadline-driven bulk-data transfer in elastic optical networks. IEEE Access, 5, 13645–13653, 2017. [2] Dijkstra, E. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, Springer, 1(1), 269–271, 1959. [3] Fayez, M.; Katib, I.; Rouskas, G.; Faheem, H. (2016). Scheduling-Inspired Spectrum Assignment Algorithms for Mesh Elastic Optical Networks. Advances In Computer Communications And Networks: From Green, Mobile, Pervasive Networking To Big Data Computing, River Publishers, 225, 2016. https://doi.org/10.15837/ijccc.2020.5.3933 7 [4] Fayez, M.; Katib, I.; Rouskas, G.; Faheem, H. (2015). Spectrum Assignment in Mesh Elastic Op- tical Networks. Proceedings Of The 24th International Conference On Computer Communications And Networks (ICCCN), 2015. [5] Fayez, M.; Katib, I.; Rouskas, G.; Gharib, T.; Khaleed, H.; Faheem, H. (2019). Recursive al- gorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem. Ain Shams Engineering Journal, Elsevier, 2019. [6] Gerstel, O.; Jinno, M.; Lord, A.; Yoo, S. (2012). Elastic optical networking: a new dawn for the optical layer? Communications Magazine, IEEE, 50(2), s12—-s20, 2012. [7] Goscien, R.; Walkowiak, K.; Klinkowski, M. (2015). Tabu search algorithm for routing, modula- tion and spectrum allocation in elastic optical network with anycast and unicast traffic. Computer Networks, 79, 148–165, 2015. [8] Jaumard, B.; Daryalal, M. (2017). Efficient spectrum utilization in large scale RWA problems. IEEE/ACM Transactions On Networking (TON), IEEE Press, 25(2), 1263–1278, 2017. [9] Klinkowski, M.; Lechowicz, P.; Walkowiak, K. (2018). Survey of resource allocation schemes and algorithms in spectrally-spatially flexible optical networking. Optical Switching And Networking, Elsevier, 27, 58–78, 2018. [10] Klinkowski, M.; Walkowiak, K. (2011). Routing and spectrum assignment in spectrum sliced elastic optical path network. IEEE Communications Letters, 15(8), 884–886, 2011. [11] Klinkowski, M.; Zotkiewicz, M.; Walkowiak, K.; Ruiz, M.; Velasco, L.; (2016). Solving large instances of the RSA problem in flexgrid elastic optical networks. IEEE/OSA Journal Of Optical Communications And Networking, IEEE, 8(5), 320–330, 2016. [12] Ma, S.; Wang, Y.; Guo, B.; Chen, X.; Li, J.; Chen, Z.; He, Y. (2013). A fairness-aware dynamic spectrum allocation scheme in elastic optical networks. Optoelectronics And Communications Conference And Photonics In Switching, 6, 2013. [13] Perelló, J.; Spadaro, S. (2012). Lightpath fragmentation for efficient spectrum utilization in dy- namic elastic optical networks. 2012 16th International Conference On Optical Network Design And Modelling (ONDM), 1–6, 2012. [14] Ramamurthy, R.; Mukherjee, B. (2002). Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks. IEEE/ACM Transactions On Networking, IEEE, 10(3), 351– 367, 2002. [15] Talebi, S.; Alam, F.; Katib, I.; Khamis, M.; Salama, R.; Rouskas, G. (2014). Spectrum man- agement techniques for elastic optical networks: A survey. Optical Switching And Networking, Elsevier, 13, 34–48, 2014. [16] Talebi, S.; Bampis, E.; Lucarelli, G.; Katib, I.; Rouskas, G. (2014). Spectrum assignment in optical networks: A multiprocessor scheduling perspective. IEEE/OSA Journal Of Optical Com- munications And Networking, 6(8), 754–763, 2014. [17] Wu, J.; Subramaniam, S.; Hasegawa, H. (2019). Efficient dynamic routing and spectrum assign- ment for multifiber elastic optical networks. IEEE/OSA Journal Of Optical Communications And Networking, IEEE, 11(5), 190–201, 2019. https://doi.org/10.15837/ijccc.2020.5.3933 8 Copyright c©2020 by the authors. Licensee Agora University, Oradea, Romania. This is an open access article distributed under the terms and conditions of the Creative Commons Attribution-NonCommercial 4.0 International License. Journal’s webpage: http://univagora.ro/jour/index.php/ijccc/ This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE). https://publicationethics.org/members/international-journal-computers-communications-and-control Cite this paper as: Iyad Katib (2020). Exhaustive Search for Optimal Offline Spectrum Assignment in Elastic Optical Networks, International Journal of Computers Communications & Control, 15(5), 3933, 2020. https://doi.org/10.15837/ijccc.2020.5.3933