NeTS: Small: Spectrum Symmetry-Free Optical Network Design

Planning, deploying, and engineering the networks that make up the Internet infrastructure involves complex problems referred to generically as “network design” problems. Effective and efficient solutions to network design problems are crucial to the operation and economics of the Internet and its ability to support critical and reliable communication services. This is especially true for optical networks that form the foundation of the global network infrastructure. This project develops new capabilities for the design and operation of optical networks that underlie ubiquitous Internet connectivity. Its framework makes it possible to leverage existing high performance computing resources to tackle Internet-scale network design problems. Therefore, the project produces research results that will enable a wide range of 21st century science, education, and commercial applications through the design of networks that are better optimized for user and application requirements and are less expensive to build, engineer, and operate. Earlier algorithmic methods for tackling optical network design problems have two crucial limitations. The first relates to spectrum symmetry, i.e., the fact that wavelengths and spectrum slots are interchangeable. Symmetry is particularly challenging for conventional Integer Linear Programming formulations as they encompass an exponential number of symmetric yet equivalent solutions. The second challenge is that network design algorithms have not been developed with parallelism in mind, hence they cannot take advantage of abundant and readily available High Performance Computing or cloud resources to speed up the execution time for large problem instances via multi-threading. This project’s symmetry-free model for spectrum assignment in general topology networks enables, for the first time, the design of a new breed of optimal algorithms that altogether sidestep spectrum symmetry, i.e., eliminate symmetric solutions from consideration. Moreover, parallelism is inherent in this model as the new, smaller solution space may be naturally decomposed into independent subsets. Accordingly, new algorithms are developed to readily admit multithreaded implementations and may be tailored to the computing environment at hand. This work makes contributions that lead to a paradigm shift in how we think about network design problems and develops solutions to tackle them in an efficient and scalable manner. Both computational and architectural approaches that are employed are applicable to a wide range of problems. An important outcome of this research is to lower the barrier to fully exploring the solution space and in implementing and deploying innovative designs. This work will enable large-scale networking to flourish, and indeed, it is required for its sustainability. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.