Optimization of IP networks with fast reroute mechanisms

Abstract

This dissertation studies strategies for assigning costs to the interfaces of routers inside an IP network to potentiate the use of Loop-Free Alternates (LFA). LFA is a fast reroute mechanism that has been recently deployed in commercial routers. This mechanism allows routers to forward traffic through alternative paths right after the detection of a network failure, avoiding a higher loss of packets during the network’s recovery process. The problem is that this mechanism does not usually provide coverage to all possible failures. Moreover, repair paths may lead to congestion and even forwarding loops. An application was developed that, given a network topology and its supporting traffic matrix, allows to find IGP costs that improve the network performance when employing this mechanism. The implemented strategies try to minimize situations where the use of repair paths leads to micro-loops or link overloads, thus preserving the quality of the service. The computational results show that it is possible to minimize the effects of a failure through an intelligent choice of costs. It is also possible to conclude that, for the majority of cases, increasing the LFA coverage of a network is not the best strategy. Depending on the available resources, it becomes often necessary to sacrifice this coverage to obtain better performance levels.

Esta dissertação estuda estratégias para a atribuição de custos IGP às interfaces dos routers de uma rede IP de forma a potenciar o uso de Loop-Free Alternates (LFA), um mecanismo de reencaminhamento rápido que tem sido recentemente implementado em routers comerciais. Este mecanismo permite que os routers reencaminhem tráfego por rotas alternativas assim que uma falha de rede é detetada, evitando uma maior perda de pacotes durante o período de recuperação da rede. O problema é que este mecanismo geralmente não oferece cobertura para todas as falhas possíveis. Além disso, as rotas de restauro podem causar congestão na rede e até mesmo ciclos de encaminhamento. Foi então desenvolvida uma aplicação que, dada uma topologia de rede e respetiva matriz de tráfego, permite determinar custos que melhorem o desempenho da rede quando emprega este mecanismo. As estratégias implementadas procuram minimizar situações em que o uso das rotas de restauro provoca ciclos de encaminhamento ou sobrecarga das ligações, preservando desta forma a qualidade da maior parte do serviço. Os resultados obtidos mostram que é possível minimizar os efeitos de uma falha através de uma escolha inteligente dos custos. Também é possível concluir que, na grande maioria dos casos, aumentar de forma cega a cobertura da rede através de Loop-Free Alternates não é a melhor estratégia. Dependendo dos recursos disponíveis, torna-se muitas vezes necessário sacrificar essa cobertura para obter melhores níveis globais de desempenho.