Home > BGP, Peering, Protocolos, TCP/IP > Convergência, no BGP

Convergência, no BGP

20/01/2011 Leave a comment Go to comments

Introdução

Convergência é um problema relacionado com o tempo em que toda uma rede se estabiliza após a ocorrência de um evento qualquer. Rede no contexto desse artigo é, a Internet.

Sabemos que logo na infância da Internet, ela foi dividida em sub-redes não isoladas, cada uma identificada e denominada Sistema Autônomo (AS, de Autonomous System). O objetivo foi o de facilitar a entrega de pacotes ou o roteamento dos pacotes da origem para o destino. Pouco tempo depois, foi criado um protocolo, conhecido por todos nós, o BGP (Border Gateway Protocol) com o objetivo de facilitar o mecanismo de roteamento entre os ASes (nos livrar do processo manual de estabelecer as rotas estáticas. O BGP, em sua versão original mostrou-se frágil diante da velocidade do crescimento da a Internet e antes dela se tornar de uso geral ou “comercial” (em 1993), já havia uma nova versão do BGP na praça: o BGP-4. Interessante lembrar, um fato histórico: o AS veio antes do BGP!

O BGP-4, apesar de ser um protocolo robusto começou a apresentar algumas deficiências de origem. Uma delas, impossível de solucionar sem alterações radicais é a sua estratégia de roteamento: hop-by-hop. De uma forma simples, no BGP, um parceiro (“peer”) só sabe o que acontece na Internet através de seus vizinhos imediatos. Parceiro nesse caso é um AS e, tambem, os vizinhos o são. Vamos imaginar o tamanho da Internet e, por razões de simplicidade, usar a Figura 1 para modelar a Internet. A Figura 1 foi retirada do artigo de Russ WhiteWhite, escrito em 2005, com o objetivo de propor uma solução para a questão do tempo de convergência do BGP-4 sob a ótica da estratégia hop-by-hop.

Exemplo de convegência no BGP

Figura 1. Ilustração do problema da convergência no BGPWhite

O problema da convergência

Na figura de Russ White os números dentro dos círculos representam ASes, de 1 a 12. A figura representa uma pequena rede de 12 ASes deve ser extrapolada para a Internet, com mais de 35.000 ASes (isto é, nós como os da pequena figura). A escolha da figura do trabalho de Russ White é simplesmente uma aplicação da navalha de OccamOccam. É de uma genialidade e simplicidade sem igual.

Na figura, vamos supor que o AS12 anuncia o bloco 10.1.1.0/24. Se AS12 anuncia esse bloco, ele é o único na rede que sabe como atingí-lo. Assim, o AS1 para enviar um pacote para um IP do bloco 10.1.1.0/24, o caminho deve seguir a direção do AS12. Vamos supor que AS1 atinja o bloco, com o menor caminho [AS6, AS12]. Muito embora, na tabela de roteamento de AS1, esteja a informação de que ele poderia enviar pelo caminho [AS2, AS9, AS12], por exemplo. A escolha pode não ser pelo menor caminho. Há vários parâmetros que podem afetar a escolhaCisco. Lembramos que caminho é o mesmo que ASPath, no BGP.

Eis um problema de convergência: suponha que o AS12 pare de anunciar o bloco 10.1.1.0/24, subitamente. Como AS12 era o único que sabia onde chegar aos IPs do bloco fatídico, o que ocorre com as informações na tabela de roteamento de AS1? Ops! O que acontece na Internet, quando ocorre uma falha dessa natureza?

Analisando o problema da convergência

Na tabela que segue, vamos exibir o caminho escolhido (escolha arbritrária!), por cada AS para chegar ao bloco 10.1.1.0/24:

AS Caminho
AS1 [AS6, AS12]
AS2 [AS9, AS12]
AS3 [AS7, AS10, AS12]
AS4 [AS5, AS8, AS11, AS12]
AS5 [AS8, AS11, AS12]
AS6 [AS12]
AS7 [AS10, AS12]
AS8 [AS11, AS12]
AS9 [AS12]
AS10 [AS12]
AS11 [AS12]

Vamos supor que AS12 não saiba mais como chegar ao bloco 10.1.1.0/24. O AS12 envia uma mensagem BGP para todos seus vizinhos, AS6, AS9, AS10 e AS11 retirarem o referido anúncio. Esses vizinhos, imeditatamente avisam seus respectivos vizinhos para retirarem o anúncio do bloco 10.1.1.0/24. No mesmo momento, recebem essa mensagem: AS1, AS2, AS7 e AS8. Então, AS1, ao receber seu primeiro pedido de retirada do bloco, analisa sua tabela de rotas locais e procura pelo próximo melhor caminho. Como ele não recebeu ainda nenhuma mensagem de retirada do AS2, ele muda a tabela para o outro caminho, digamos [AS3, AS7, AS10, AS12] e continua a enviar pacotes para o bloco 10.1.1.0/24.

Nesse momento, AS2, AS7 e AS8 enviam mensagens de retirada para seus parceiros vizinhos: AS1, AS3 e AS5. AS1 recebe uma nova mensagem de retirada e procura outra rota continuando a enviar tráfego para o bloco 10.1.1.0/24, pois ele tem uma outra rota, [AS3, AS7, AS12] já que seu vizinho AS3 não lhe disse nada.

Na sequência, AS3 e AS5 pedem a retirada a seus vizinhos, AS1 e AS4. E, AS1, novamente altera sua tabela, descobrindo outro caminho, [AS4,AS5,AS8,AS11,AS12] e encaminha pacotes para o bloco 10.1.1.0/24, sem saber que AS4 acabou de receber a mensagem de retirada.

Finalmente, AS4 envia a mensagem de retirada a AS1 que agora remove a última informação sobre como chegar ao bloco 10.1.1.0/24. Então para de encaminhar pacotes para esse bloco. Finalmente! Nesse ponto, a pequena rede converge. Ops! Queríamos dizer, a Internet, presumivelmente, converge.

Conclusões e Atualizações

Assim funciona o esquema da convergência do BGP. De tempos em tempos aparecem recomendações para alterações no BGP que são aceitas e virão na próxima versão. Como por exemplo, a sugestão que motiva o artigo de Russ White, onde ele recomendou que quando o AS1 recebesse a primeira mensagem de retirada, do seu vizinho AS6, ele pesquisaria toda a sua tabela de rotas, localmente e retiraria as referências ao bloco 10.1.1.0/24, evitando tráfego inútil.

Algum tempo depois de escrito esse pequeno artigo, encontrei uma referência bem mais completa na Internet Lapukhov, que recomendo aos interessados.

Em 14/02/2011, Vasco Asturiano fez um experimento e exibiu alguns gráficos relacionados com a convergência do BGP quando se anunciava e retirava o anúncio de um prefixo Asturiano. Muito interessante o artigo, onde ele conclui que é mais fácil (~rápido), para o BGP, a convergência quando se anuncia um prefixo, do que a convergência quando se retira o anúncio de um prefixo.

Em 19/07/2013, Randy Busch escreveu um curto e-mail na lista, com algumas frase interessantes, entre as quais: “global bgp never converges (and how would you know if it did?)“. Lembrando-me deste artigo e a última frase no final da seção anterior, onde dizia que a “…a Internet, presumivelmente, converge” escrevi um e-mail para Randy dizendo-lhe que achei muito interessante a sua frase. Gentilmente, ele retornou-me com a indicação do artigo [Roughan, Willinger, Maennel, Perouli & Bush]. É um texto imperdível! Com uma imensa referência, cito abaixo o último parágrafo, com a promessa de brevemente fazer uma resenha aqui no blogue:

The lessons of this paper will hopefully form a checklist for any student or new researcher in this area that will enable them to avoid the pitfalls which have reduced the value of some past research. Simply stated, to ensure value of future research in this area, any work on the structure and evolution of the Internet’s Autonomous System has to account for the economic, technological, and social forces that shape this critical element of the Internet.

Referências

White, Russ, Graph Overlays on Path Vector: A Possible Next Step in BGP, The Internet Protocol Journal, Volume 8, Number 2, Junho 2005. Disponível em http://www.cisco.com/web/about/ac123/ac147/archived_issues/ipj_8-2/graph_overlays.html. Acessado em: 20/01/2011.

Wikipedia, Navalha de Occam. Disponível em http://pt.wikipedia.org/wiki/Navalha_de_Occam. Acessado em: 20/01/2011.

Cisco, BGP Best Path Selection Algorithm. Disponível em: http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094431.shtml#bestpath. Acessado em: 27/01/2011.

Petr Lapukhov, Understanding BGP Convergence. Disponível em: http://blog.ine.com/2010/11/22/understanding-bgp-convergence/. Acessado em: 27/01/2011.

Vasco Asturiano, The Shape of a BGP Update. Disponível em: http://labs.ripe.net/Members/vastur/the-shape-of-a-bgp-update. Acessado em: 14/02/2011.

Matthew Roughan, Walter Willinger, Olaf Maennel, Debbie Perouli, and Randy Bush. 10 Lessons from 10 Years of Measuring and Modeling the Internet’s Autonomous Systems. IEEE Journal on Selected Areas in Communications, Vol. 29, No. 9, October 2011.

Categories: BGP, Peering, Protocolos, TCP/IP