Convergência, no BGP

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 o fato histórico de que 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 White^White, 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.

Figura 1. Ilustração do problema da convergência no BGP^White

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 Occam^Occam. É 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 escolha^Cisco. 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 converge.

Epílogo

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.

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.

Follow @juliaobraga