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.