SING: Efficient Survivable Routing in Next Generation Networks

本研究涉及设计和分析下一代网络中可生存路由的高效算法。目前在这方面的研究要么是基于启发式的，缺乏性能保证，要么是计算量大，缺乏可扩展性。PI专注于在一类非常重要的网络拓扑中进行有效的可生存路由，这类网络拓扑称为最小隔离故障免疫网络。在这样的网络中，将设计有效的算法来实现可生存的路由。这一变革性的研究将为下一代网络中的可生存路径选择提供坚实的理论基础。本研究的智力价值在于以组合优化和算法为研究工具，探索下一代网络中可生存路径选择研究的新维度。研究将向以下方向扩展可生存网络中的知识前沿：(1)将基于启发式或基于整数线性规划的网状网络中可生存光路由算法改进为用于最小隔离免疫网络中可生存光路路由的多项式时间最优算法；(2)将基于启发式的服务质量感知冗余树方案扩展到具有可证明良好性能的服务质量感知冗余树方案；(3)将基于启发式的双重失败保护扩展到保证的双重失败保护。就更广泛的影响而言，这项研究将导致(I)将研究整合到本科生和研究生，特别是来自代表性不足群体的学生的教育经验中；(Ii)统一具有共同数学基础的看似不同的学科；(Iii)通过在高质量的会议和期刊上发表和发表研究成果来传播研究成果。

This research involves the design and analysis of efficient algorithms for survivable routing in next generation networks. Current research in this area are either heuristic based that lacks performance guarantee, or computationally intensive that lacks scalability. The PI concentrates on efficient survivable routing in a very important class of network topologies known as minimum isolated failure immune networks. Efficient algorithms will be designed for survivable routing in such networks. This transformative research will provide a solid theoretical foundation for survivable routing in next generation networks.The INTELLECTUAL MERIT of this research lies in exploring a new dimension of research in survivable routing in next generation networks, using combinatorial optimization and algorithms as tools of investigation.The research will extend the frontiers of knowledge in survivable networks in the following directions: (1) improving heuristic based or integer linear programming based algorithms for survivable lightpath routing in mesh network to polynomial time optimal algorithms for survivable lightpath routing in minimum isolated failure immune networks; (2) extending heuristic based QoS-aware redundant tree schemes to QoS-aware redundant tree schemes with provably good performance; (3) extending heuristic based double-failure protection to guaranteed double-failure protection.In terms of BROADER IMPACTS, this research will lead to (i) integration of research into educational experiences of students at the undergraduate and graduate levels, especially students from underrepresented groups;(ii) unification of seemingly diverse disciplines which have common underlying mathematical foundation; (iii) dissemination of research results through presentation and publication in high-quality conferences and journals.