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.