Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem
The Routing and Spectrum Assignment (RSA) problem is NP-Hard so searching the entire problem space is not applicable. Many decomposition algorithms rely on reducing the search space in the routing space and applying heuristics algorithm in the spectrum assignment sub-problem. This is not necessarily...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2020-06-01
|
| Series: | Ain Shams Engineering Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2090447919301443 |
| _version_ | 1818733277498834944 |
|---|---|
| author | Mahmoud Fayez Iyad Katib George N. Rouskas Tarek F. Gharib Heba Khaleed Hossam M. Faheem |
| author_facet | Mahmoud Fayez Iyad Katib George N. Rouskas Tarek F. Gharib Heba Khaleed Hossam M. Faheem |
| author_sort | Mahmoud Fayez |
| collection | DOAJ |
| description | The Routing and Spectrum Assignment (RSA) problem is NP-Hard so searching the entire problem space is not applicable. Many decomposition algorithms rely on reducing the search space in the routing space and applying heuristics algorithm in the spectrum assignment sub-problem. This is not necessarily a right solution as the ignored routing tables may lead to a better solution when they are used later as input to the Spectrum Assignment sub-problem. In this paper, we develop a new recursive decomposition approach for the RSA problem in optical networks. At the core of our approach is a new recursive branch and-bound procedure for carrying out an exhaustive search of the routing space in a scalable manner. This recursion effectively decouples the routing from the spectrum assignment part of the problem. Sequential generation of the full set of routing tables requires huge memory and very large processing time. Alternatively, our approach deploys multi-core architectures to generate the routing tables in parallel using OpenMP. Experimental results indicate that our recursive algorithm is quite efficient in searching the entire routing space for topologies representing large-scale wide area networks. Importantly, the decomposition may be more generally applied to any network design problem whose solution involves a search over both a routing and a resource allocation space. The main contributions for this paper are that we are able to generate all the search space in parallel in less than 1 min for 32-nodes network. Secondly, we are able to investigate all the routing tables, eliminate most of the search space, and select the promising routing tables that are proven to lead to a better solution in the Spectrum Assignment Sub-Problem |
| first_indexed | 2024-12-17T23:46:55Z |
| format | Article |
| id | doaj.art-e3649854e24d4ed2b395f693e27084d3 |
| institution | Directory Open Access Journal |
| issn | 2090-4479 |
| language | English |
| last_indexed | 2024-12-17T23:46:55Z |
| publishDate | 2020-06-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Ain Shams Engineering Journal |
| spelling | doaj.art-e3649854e24d4ed2b395f693e27084d32022-12-21T21:28:18ZengElsevierAin Shams Engineering Journal2090-44792020-06-01112273280Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problemMahmoud Fayez0Iyad Katib1George N. Rouskas2Tarek F. Gharib3Heba Khaleed4Hossam M. Faheem5Ain Shams University, EgyptKing Abulaziz Universtiy, Saudi ArabiaNC State University, United StatesAin Shams University, EgyptAin Shams University, EgyptAin Shams University, Egypt; Corresponding author.The Routing and Spectrum Assignment (RSA) problem is NP-Hard so searching the entire problem space is not applicable. Many decomposition algorithms rely on reducing the search space in the routing space and applying heuristics algorithm in the spectrum assignment sub-problem. This is not necessarily a right solution as the ignored routing tables may lead to a better solution when they are used later as input to the Spectrum Assignment sub-problem. In this paper, we develop a new recursive decomposition approach for the RSA problem in optical networks. At the core of our approach is a new recursive branch and-bound procedure for carrying out an exhaustive search of the routing space in a scalable manner. This recursion effectively decouples the routing from the spectrum assignment part of the problem. Sequential generation of the full set of routing tables requires huge memory and very large processing time. Alternatively, our approach deploys multi-core architectures to generate the routing tables in parallel using OpenMP. Experimental results indicate that our recursive algorithm is quite efficient in searching the entire routing space for topologies representing large-scale wide area networks. Importantly, the decomposition may be more generally applied to any network design problem whose solution involves a search over both a routing and a resource allocation space. The main contributions for this paper are that we are able to generate all the search space in parallel in less than 1 min for 32-nodes network. Secondly, we are able to investigate all the routing tables, eliminate most of the search space, and select the promising routing tables that are proven to lead to a better solution in the Spectrum Assignment Sub-Problemhttp://www.sciencedirect.com/science/article/pii/S2090447919301443RSAExhaustive routing searchRSA decomposition |
| spellingShingle | Mahmoud Fayez Iyad Katib George N. Rouskas Tarek F. Gharib Heba Khaleed Hossam M. Faheem Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem Ain Shams Engineering Journal RSA Exhaustive routing search RSA decomposition |
| title | Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem |
| title_full | Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem |
| title_fullStr | Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem |
| title_full_unstemmed | Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem |
| title_short | Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem |
| title_sort | recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem |
| topic | RSA Exhaustive routing search RSA decomposition |
| url | http://www.sciencedirect.com/science/article/pii/S2090447919301443 |
| work_keys_str_mv | AT mahmoudfayez recursivealgorithmforselectingoptimumroutingtablestosolveofflineroutingandspectrumassignmentproblem AT iyadkatib recursivealgorithmforselectingoptimumroutingtablestosolveofflineroutingandspectrumassignmentproblem AT georgenrouskas recursivealgorithmforselectingoptimumroutingtablestosolveofflineroutingandspectrumassignmentproblem AT tarekfgharib recursivealgorithmforselectingoptimumroutingtablestosolveofflineroutingandspectrumassignmentproblem AT hebakhaleed recursivealgorithmforselectingoptimumroutingtablestosolveofflineroutingandspectrumassignmentproblem AT hossammfaheem recursivealgorithmforselectingoptimumroutingtablestosolveofflineroutingandspectrumassignmentproblem |