Resilient-IP (funded by EuroFGI)

Optimisation of Intra-Domain Routing for Resilient IP Networks (Resilient-IP)

Summary

The objective of the project are the development, improvement, and comparison of algorithms to optimize link cost settings in IP networks to achieve resiliency after rerouting. The methods comprise heuristic approaches and exact solutions. The first half of the project is devoted to the optimization of IP routing in failure-free networks. The administrative link weights in IP networks are adjusted in such a way that the maximum utilization of all links is as low as possible and that all shortst paths with regard to the link weights are unique, i.e., there is only a single shortest path for every source-destination pair. Three different approaches are compared: branch and cut (BC), constraint programming (CP), and hill hopping (HH). BC and CP are exact methods while HH is a heuristic algorithm.

The second half of the project focuses on MPLS fast reroute. MPLS fast reroute has two options. The facility backup establishes a bypass for all link or node failures and all connections facing this failure are protected by these backups. In contrast, the one-to-one backup establishes for each label switched path (LSP) a direct detour from potential points of local repair to the LSP egress router. Therefore, the one-to-one backup comes with significantly more configuration overhead. The path layout of primary and backup paths can be chosen explicitly or they can be determined by IP routing. In this project, we compute explicit routes using mathematical optimization methods on the one hand and tweak IP routing by heuristc algorithms on the other hand such that the maximum utilization is as low as possible in all considered failure scenarios, e.g. all single link or node failures. The comparison of both approaches quantifies the cost of a simple network management using only IP routing for the setup of the backup paths.

back to NGN group