Lehrstuhl für Informatik III

IP-Resilience (funded by DFG)

Optimization of Standard and Fast Mechanisms for IP-(Re)routing (IP-FAST-RESILIENCE)



Prof. Dr.-Ing. Phuoc Tran-Gia,

Dr. Michael Menth

Researchers Rüdiger Martin
Funded period

December 2005 - November 2007,

September 2008 - August 2009


IP networks have the self-healing property. Their routing re-converges after a network failure by exchanging link state advertisements (LSAs) such that all but the failed nodes can be reached after a while if a working path still exists. This self-healing property was the main motivation for the DARPA (Defense Advanced Research Projects Agency) when designing the Internet and made the Internet an enormous success over the last 30 years. IP re-convergence is a very simple and robust mechanism. However, the disadvantage of such a method is obvious: it is slow. In particular, the interval to exchange the LSA updates cannot be reduced to arbitrarily small values for stability reasons and the computation of the shortest paths that are needed to construct the routing tables based on the new LSAs requires a substantial amount of time. This time overhead is tolerable for elastic traffic but not for real-time or even high-precision telematic or tele-surgery applications. Currently, standardization organizations like the IETF discuss IP Fast Reroute (IP-FRR) mechanisms to overcome the problems involved in long routing re-convergence while not abandoning the IP routing concept. These mechanisms make dimensioning of new networks and configuration of existing networks more complex and arise the following research issues:

  • How much capacity is required in the network to survive a given set of network element failures the network should be protected against without traffic loss (dimensioning)?
  • How much traffic can be carried over a given network without traffic loss for a given set of network failures (configuration)?
  • How severe is the impact of unprotected network element failures?

Obviously, the answers to these questions depend on the specific rerouting approach. In this project, we analyze IP-FRR algorithms currently under discussion in the international research community with respect to these issues. As stability is a crucial aspect of such algorithms, stability aspects are our main focus. We suggest extensions or improvements where possible and we plan to develop new methods if required.