Optimizing IGP Link Costs for Improving IP-Level Resilience

Optimizing IGP Link Costs for Improving IP-level  Resilience

Recently, major vendors have introduced new router platforms to the market  that support fast IP-level failure protection out of the box.  The  implementations are based on the IP Fast ReRoute–Loop Free Alternates  (LFA) standard. LFA is simple, unobtrusive, and easily deployable. This  simplicity, however, comes at a severe price, in that LFA usually cannot  protect all possible failure scenarios.  In this paper, we give new graph  theoretical tools for analyzing LFA failure case coverage and we seek ways  for improvement. In particular, we investigate how to optimize IGP link  costs to maximize the number of protected failure scenarios, we show that  this problem is NP-complete even in a very restricted formulation, and we  give exact and approximate algorithms to solve it. Our simulation studies show that a deliberate selection of IGP costs can bring many networks close to complete LFA-based protection.

Ezen kutatási eredményeimet konzulensemmel és társszerzőkkel benyújtottam a DRCN 2011 konferenciára, ahol Best Paper díjra jelölték (a konferencia ideje: 2011. okt. 10-12).

Továbbá készülőben van egy angol nyelvű Híradástechnika cikk (Rétvári Gáborral és Nagy Máté doktoranduszjelölttel közösen), mely egy kombinált metrikával működő algoritmusról is, ami a fent említettet és egy már korábban publikált módszert ötvöz, mely így együttesen még jobban és költséghatékonyabban tudja növelni az LFA lefedettséget a hálózatokban.

 

Levente Csikor, Ph.D. Student, BME, TMIT, csikor@tmit.bme.hu

A teljes kutatásibeszámoló letölthető innen (PDF)

2011. július 19.