FenixEdu™

Dissertação

Correctness and Evaluation of a Loop Free Routing Protocol of the Internet EVALUATED

Detalhes: O Enhanced Interior Gateway Routing Protocol (EIGRP) é amplamente utilizado em redes empresariais. Tal como o Border Gateway Protocol (BGP), o EIGRP é um protocolo de vetorização mas seleciona caminhos de acordo com uma métrica composta que combina capacidade e atraso, enquanto promete o encaminhamento sem ciclos de pacotes de dados durante períodos transitórios. Surpreendentemente, as propriedades de correção do EIGRP nunca foram demonstradas rigorosamente, e a sua complexidade em redes realistas ainda não foi estudada. Nesta dissertação, colocamos o funcionamento do EIGRP sob uma estrutura algébrica que modela métricas arbitrárias, resultando no EIGRP-generalizado (gEIGRP). Identificamos condições que garantem o correcto comportamento do gEIGRP e apresentamos uma prova de correção por asserções baseada num invariante, derivamos propriedades de segurança e uma propriedade de animação. Mostramos que existem métricas para as quais o BGP atinge um estado estável enquanto o gEIGRP bloqueia. Avaliamos ainda as complexidades de tempo e mensagens do gEIGRP em redes realistas. Concluímos que quando a rede fica disconexa, o gEIGRP converge mais rapidamente do que o BGP. Contrariamente, quando a rede permanece conexa apesar de alterações na sua topologia, o BGP converge mais rapidamente do que o gEIGRP, por vezes por um fator de quatro. Por último, constatamos que, embora o gEIGRP nunca prenda pacotes de dados em ciclos de expedição, perde conectividade por períodos mais longos do que o BGP após falhas de ligação. Os resultados apresentados nesta dissertação oferecem uma nova perspectiva sobre o funcionamento do EIGRP e, acreditamos, informam o desenho de novos protocolos.
Keywords: Protocolos de Encaminhamento, Computações Difusas, Correção de Protocolos, Métodos de Asserção, Invariante, Simulação de Protocolos

Discussão: novembro 16, 2022, 11:0