SING: Efficient Survivable Routing in Next Generation Networks

这项研究涉及下一代网络中的生存路由的有效算法的设计和分析。目前这方面的研究要么是启发式的，缺乏性能保证，或计算密集，缺乏可扩展性。PI集中在一个非常重要的一类网络拓扑称为最小孤立故障免疫网络的高效生存路由。有效的算法将被设计在这样的网络中的生存路由。本论文的创新性研究将为下一代网络中的可生存路由提供坚实的理论基础，其学术价值在于以组合优化和算法为研究工具，探索了下一代网络中可生存路由研究的一个新维度，并将在以下几个方面拓展可生存路由的知识前沿：（1）将基于启发式或整数线性规划的网状网络生存性光路路由算法改进为最小孤立故障免疫网络生存性光路路由的多项式时间最优算法，（2）将基于启发式的QoS冗余树方案扩展为性能良好的QoS冗余树方案;（3）将基于启发式的双故障保护扩展到保证的双故障保护，在更广泛的意义上，这项研究将导致（i）将研究整合到本科生和研究生的教育经验中，特别是来自代表性不足的群体的学生;（ii）将表面上不同的学科统一起来，这些学科具有共同的数学基础; ㈢通过在高质量的会议和期刊上介绍和发表来传播研究成果。

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.