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.

Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
Arizona State University
United States
Zip Code