Border Gateway Protocol Versão 4 constitui o protocolo de roteamento exterior utilizado atualmente na Internet. BGP-4 é essencialmente um algoritmo vetor-distância (vector-distance), mas com várias características que lembram uma operação estado de enlace (link-state).

BGP executa roteamento inter-domínios em redes TCP/IP (Transmission Control Protocol/ Internet Protocol), e conforme [3], efetua intercâmbio de informações entre diversos SA (sistemas autônomos) e tornou-se o sucessor natural do EGP (Exterior Gateway Protocol), atacando suas deficiências.

Outro uso do BGP é a quebra de uma grande rede em pequenos pedaços. Por exemplo, uma empresa com presença em cada continente deve considerar o uso de BGP entre os continentes. Se esta empresa está usando OSPF por exemplo, pode ser melhor tornar cada continente um AS (autonomous system), e falar BGP entre eles como uma clara separação entre os continentes.

1.2 PADRONIZAÇÃO DO BGP

RFC 1771 A Border Gateway Protocol 4 (BGP-4)

RFC 1772 Application of the Border Gateway Protocol

RFC 1773 Experience with the BGP-4 protocol

RFC 1774 BGP-4 Protocol Analysis

RFC 1965 Autonomous System Confederations for BGP

RFC 1966 BGP Route Reflection

RFC 1997 BGP Communities Attribute

RFC 1998 BGP Community Attribute in Multi-home Routing

RFC 1657 The BGP MIB

RFC 1654 descreve a primeira especificação do BGP versão 4, enquanto as RFCs 1105, 1163 e 1267 descrevem as versões anteriores ao BGP-4.

Conforme [7] BGP-4 é uma extensão do BGP-3 , que fornece suporte à agregação e redução de endereços baseado na arquitetura de roteamento CIDR (Classless Inter-Domain Routing).

Em [9], versão chamada de BGP-4 extendida que será usada no backbone da denominada Internet do futuro, o 6bone.

1.3 CONCEITOS BÁSICOS

I Sistemas Autônomos

Uma definição clássica de sistema autônomo traduzido de [7] é um conjunto de roteadores sob uma única administração técnica, que usa um protocolo interno (interior gateway protocol) para rotear pacotes dentro de um SA e um protocolo externo (exterior gateway protocol) para rotear pacotes para outros SA`s.

Mas muitos SAs podem possuir IGPs diferentes, bem como adotar diversas métricas dentro do mesmo sistema autônomo. Portanto, a utilização do termo sistema autônomo designa aqui o fato que, mesmo com múltiplos IGPs e métricas, a administração de um SA aparenta a outro SA ter um único plano de rota e apresenta um quadro consistente de que o destino é encontrado através dele.

II Algorítmo Vetor-distância

Algoritmos de roteamento vetor-distância (vector-distance ou Bellamn-Ford) mantêm, em cada roteador, uma tabela informando a melhor distância conhecida e que rota utilizar para chegar até o roteador. Alguns exemplos de protocolos que utilizam o vetor-distância são: protocolo RIP, versões antigas de DECnet e IPX (da Novell). A AppleTalk e roteadores Cisco utilizam versões melhoradas do algoritmo vetor-distância.

Neste tipo de algoritmo, cada roteador mantém uma entrada na tabela indexada para cada roteador na subrede. Esta entrada contém duas partes: a rota de saída preferida para aquele destino e tempo ou distância estimada. A métrica utilizada pode ser de número de saltos (hops), atraso, número total de pacotes na fila de cada caminho, etc.

III Algoritmo Estado de Enlace

A idéia por trás do algoritmo link-state ou estado de enlace é simples e pode ser apresentada em cinco partes:

Descobrir seus vizinhos e aprender sobre seus endereços de rede;
Medir o atraso ou o custo para cada um dos seus vizinhos;
Construir um pacote contendo tudo que acabou de aprender;
Mandar este pacote a todos os outros roteadores;
Computar o caminho mais curto para cada roteador.

O algorítmo link-state é utilizado em diversos tipos de protocolos. O procololo OSPF, cuja utilização cresce constantemente na Internet, utiliza algoritmo link-state. Protocolo IS-IS (Intermediate System-Intermediate System), projetado pela DECnet e adotado pela ISO, para ser empregado em seu protocolo de rede não-orientado à conexão CNLP (CoNnectionLess Protocol) e que está sendo utilizado em inúmeros backbones Internet e em sistemas digitais celulares como CDPD. Roteamento de pacotes IPX da Novell também usa uma variante do IS-IS.

IV Protocolo eBGP x iBGP

Parafraseando [3] são chamados vizinhos (neighbors) os sistemas BGP (roteadores) que possuem sessões BGP estabelecidas entre eles. Então, os roteadores de borda são neighbors? Sim. Porém, quando uma importância política é a eles atribuída, a forma correta de chamá-los é de peers, enquanto que os neighbors são quaisquer vizinhos BGP. Os roteadores adjacentes nem sempre são vizinhos [1].

Existem outras situações em que os vizinhos BGP não são, obrigatoriamente, os roteadores entre ASs e sim roteadores do mesmo AS [3]. Neste caso as sessões estabelecidas entre eles acontece internamente ao SA. O que permite isso é o iBGP ou internal BGP, que permite a troca de rotas no mesmo SA. De forma análoga, a troca de rotas entre SAs é feita pelo eBGP (exterior BGP).

Um importante conceito do iBGP é que os neighbors não têm a obrigação de estar diretamente conectados através de uma linha serial ou via interface Ethernet, por exemplo. Os peers por outro lado não podem estar conectados de outra forma que não seja a direta, seja link serial ou interface Ethernet.

O protocolo de roteamento usado pelos exterior neighbors é o Exterior Gateway Protocol ou simplesmente EGP [RFC 904]. É ele que permite o anúncio das rotas para as redes internas do AS para o núcleo (core) da Internet.

Com o tempo, o EGP apresentou diversas limitações técnicas [3] e potenciais problemas para ser usado na Internet. Apesar das tentativas para produzir novas versões (EGP2 e EGP3) do protocolo, os projetistas não obtiveram sucesso por haver a necessidade de muitas alterações fundamentais na estrutura do mesmo.

O algoritmo do eBGP trabalha, basicamente, anunciando todas rotas que conhece, enquanto o do iBGP faz o possível para não anunciar rotas. Assim, para fazer o iBGP funcionar adequadamente dentro de um AS é necessário estabelecer sessões BGP entre todos os roteadores que "falam" iBGP (ver Figura 7), formando uma "malha completa" (full mesh) de sessões iBGP dentro do AS.

Os protocolos de roteamento internos mais conhecidos são: OSPF, iBGP, IS-IS, RIP, RIPv2.

1.4 Endereço Agregado

O protocolo IP tem sido largamente utilizado por mais de uma década. Apesar de estar funcionando muito bem, dois problemas surgiram: a exaustão dos endereços IP e a explosão das tabelas de roteamento. Uma das alternativas a este problema é a agregação de endereços , conhecida como CIDR (Classless Inter-Domain Routing). A idéia básica do CIDR consiste em alocar o restante das redes classe C em blocos de tamanho variável.

Do ponto de vista de roteadores, o espaço de endereçamento IP é uma hierarquia de dois níveis, com número de rede e número de máquinas. Em [8] roteadores não precisam conhecer sobre todas as máquinas, mas eles têm de saber sobre todas as redes.

Apesar da implementação deste meio milhão de entradas ser factível, ela apresenta uma série de desvantagens: é caro manter tabelas deste tamanho em memórias estáticas RAM; a complexidade do gerenciamento aumenta muito mais do que o crescimento do número de entradas; além disso, muitos algoritmos de roteamento exigem que cada roteador transmita a sua janela periodicamente: quanto maior a tabela, maior é a probabilidade de que haja um erro na transmisão ocasionando instabilidade nestes mesmos algoritmos de roteamento.

A idéia básica do plano é alocar um ou mais blocos de rede classe C para cada provedor de serviço da rede. Para toda organização que se conecte à Internet via provedor, são alocados subconjuntos de endereços deste provedor.

Hipoteticamente, suponha que um provedor A tenha 2048 redes classe C que começam com 192.24.0.0 e terminam com 192.31.255.0. Seja ainda um cliente C que deseja menos do que 2048 endereços. Então será alocado os endereços 192.24.0.0 a 192.24.7.0.

Esta subalocação hierárquica de endereços implica que clientes com subconjunto de endereços de um provedor terão, obrigatoriamente, sua informação roteada pela infra-estrutura do roteador.

Duas observações devem ser feitas para esta alocação hierárquica:

Espera-se que seja mais fácil para pequenos provedores obterem endereços junto â autoridade central do que clientes individuais (cujo número cresce monotonicamente)
Este médoto é escalável e delegável, características desejáveis por causa da alta taxa de crescimento da Internet.

V Exemplo de funcionamento CIDR

Pela política CIDR, o mundo foi dividido em quatro zonas:

Endereços 194.0.0.0 a 195.255.255.255 Europa
Endereços 198.0.0.0 a 199.255.255.255 América do Norte
Endereços 200.0.0.0 a 201.255.255.255 América do Sol
Endereços 202.0.0.0 a 203.255.255.255 Ásia e Pacífico

Para este exemplo considere que:

a Universidade de Cambridge precisa de 2048 endereços e foram alocados para ela os endereços de 194.24.0.0 a 194.24.7.255
a Universidade de Oxford precisa de 4096 endereços, sendo alocados os endereços de 194.24.16.0 a 194.24.31.255
a Universidade de Edinburgh precisa de 1096 endereços e foram alocados os endereços de 194.24.8.0 a 194.24.11.255

Se forem estes os únicos sites existentes na Europa, os roteadores europeus ficariam com a seguinte tabela dos endereços acima:

             Endereço                                                   Máscara

11000010 00011000 00000000 00000000 11111111 11111111 11111000 00000000

11000010 00011000 00010000 00000000 11111111 11111111 11110000 00000000

11000010 00011000 00001000 00000000 11111111 11111111 11111100 00000000

Suponha que um pacote está sendo enviado para o endereço 192.24.17.4 (que em binário é 11000010 00011000 00010001 00000100) Inicialmente, este valor sofre uma operação de AND booleano com a máscara da primeira entrada (resultado 11000010 00011000 00010000 00000000), que não é igual ao primeiro endereço.

Desta forma, o endereço sofre novamente uma operação de AND booleano com a máscara da próxima entrada (resultado 11000010 00011000 00010000 00000000), que é o mesmo valor do endereço da segunda entrada da tabela. Logo, este pacote é enviado para a segunda entrada.

2 FUNCIONAMENTO DO BGP

Executa-se BGP sobre um protocolo de transporte confiável, que implementa fragmentação, retransmissão, sequenciamento e confirmação de pacotes. BGP provê mecanismos de autenticação que são utilizados com quaisquer outros mecanismos da camada de transporte.

BGP utiliza TCP como protocolo de transporte. TCP, além de preencher os parâmetros acima, está virtualmente implementado em todos os hosts comerciais. BGP utiliza a porta 179 para estabelecer suas conexões.

O funcionamento básico segue resumidamente [3]:

Para o estabelecimento de uma sessão BGP entre neighbors ou peers, basicamente, os seguintes passos são executados:

É estabelecida a conexão TCP entre os dois roteadores que trocam mensagens de abertura da sessão e negociam os parâmetros de operação;
O primeiro fluxo de dados transmitido é a tabela de rotas BGP completa. Posteriores atualizações nesta tabela são feitas, incrementalmente, à medida que as mudanças ocorrerem;
Como não há a atualização completa da tabela após a primeira, o roteador mantém a informação da versão da tabela que todos os seus peers possuem, enquanto durar a sessão entre eles. Se esta for interrompida por qualquer motivo, o processo é iniciado novamente a partir do primeiro passo;
Mensagens de keepalive são enviadas periodicamente para manter a sessão aberta;
Mensagens de aviso são enviadas quando ocorrem erros ou outras situações especiais;

Caso uma conexão verifique um erro, uma mensagem é enviada e a conexão fechada, encerrando a sessão

2.1 Rotas

No protocolo BGP, rotas são definidas como sendo a unidade de informação que ajusta uma destinação com atributos de caminho para aquele destino.

As rotas são anunciadas entre elementos BGP através de mensagens UPDATE e são armazenadas em banco de informações de roteamento (Routing Information Base-RIB).

Quando um elemento BGP resolve anunciar uma rota, ele deve adicionar ou modificar os atributos do caminho para aquela rota antes de anunciá-la. Também há mecanismos para avisar que uma rota não está mais disponível:

Através do campo WITHDRAWN ROUTES da mensagem UPDATE;
Através de uma rota de substituição;
Quando a conexão é desfeita, que implicitamente remove todas as rotas que passam pelo BGP remoto.

2.2 Banco de Informações de Roteamento

Conforme [6] o banco de Informações de roteamento, do inglês “Routing Information Base” (RIB) é composto de três tabelas:

a) Adj-RIBs-In

Armazena rotas cuja informação foi aprendida através de mensagens UPDATE. Seu conteúdo representa rotas disponíveis que são entrada para o processo de decisão.

b) Loc-RIB

Contém a informação de roteamento local que o sistema BGP local selecionou aplicando suas políticas locais â informação contida em Adj-RIBs-In.

c) Adj-RIBs-Out

Armazena informação que o sistema BGP selecionou para enviar a seus pares. A informação de roteamento armazenada em Adj-RIBs-Out será informada pelo sistema BGP local através de mensagens UPDATES.

Resumidamente, Adj-RIBs-In contém informação não processada enviada ao sistema BGP local por seus pares; Loc-RIB contém rotas que foram selecionadas pelo processo de decisão do sistema; Adj-RIBs-Out organiza as rotas que devem ser anunciados a seus pares específicos.

2.3 Processo de Decisão

Através da aplicação de políticas, o processo de decisão seleciona as rotas que devem ser anunciadas. Tais políticas contemplam métricas definidas pelo Sistema Autônomo. A saída deste processo é um conjunto de rotas a serem anunciadas a sistemas BGP vizinhos (e que estão armazenadas em Adj-RIBs-Out).

O Processo de Decisão é formalizado por uma função que toma o atributo de uma dada rota como argumento e devolve um número não negativo, denotando o grau de preferência desta rota.

O Processo de Decisão opera em rotas contidas em cada Adj-RIBs-In, e é responsável por:

ü selecionar as rotas a serem anunciadas para sistemas BGP do Sistema Autônomo;

ü selecionar as rotas a serem anunciadas a sistemas BGP localizados em SAs vizinhos;

ü agregação de rotas e redução de informação.

O Processo de Decisão possui três fases:

Fase 1 calcula o grau de preferência de cada rota recebida e anuncia para o sistema autônomo local as rotas com o maior grau de preferência para cada destino;
Fase 2 é responsável pela escolha da melhor rota de todas aquelas disponíveis para cada destino e por instalar as escolhidas na tabela Loc-RIB;
Fase 3 é responsável por dissiminar cada rota em Loc-RIB para cada vizinho do SA. Otimizações (agregação e redução de informação) podem ser feitas nesta fase.

2.4 Atributos do BGP

Atributos do BGP são um conjunto de parâmetros usados para controlar informações específicas relativas a rotas, como informação sobre o caminho (path), grau de preferência da rota, o valor do next-hop da rota e informações sobre agregação. Estes parâmetros são usados pelo algoritmo do BGP como elementos para decisão da escolha das rotas e para decisão sobre filtragem de rotas. Alguns dos atributos do BGP são:

AS_path
Next hop
Local preference
Multi-Exit Discriminator (MED)
Origin
Atomic Aggregator
Agregator
Community
Weight

3 Formato das Mensagens

As mensagens, enviadas sobre uma conexão de transporte confiável, só são processadas após serem inteiramente recebidas. O tamanho máximo da mensagem é de 4096 octetos e o mínimo de 19 (cabeçalho sem dados). Conforme [6] segue o formato do cabeçalho e de cada mensagem.

3.1 Formato dos cabeçalhos das mensagens

Marker:

Serve para verificar a autenticidade da mensagem recebida e caso haja perda de sincronismo entre os roteadores vizinhos. Caso a mensagem do tipo OPEN não possuir informação de autenticação, os bits dos 16 octetos devem ser preenchidos com 1.

Length:

indica o comprimento total da mensagem em octetos

Type:

informa o tipo da mensagem especificado na RFC 1771

1. OPEN

2. UPDATE

3. KEEPALIVE

4. NOTIFICATION

3.2 Formato da Mensagem OPEN

( 2 octetos)

Version:

indica a versão do protocolo (versão corrente é 4).

My Automous System:

indica o número do Sistema Autônomo emissor.

Hold Time:

indica o número de segundos que o transmissor propõe como tempo de espera. Este tempo estabelece o intervalo máximo de segundos que pode decorrer entre o recebimento de sucessivos KEEPALIVE e/ou UPDATE pelo emissor. Ao receber uma mensagem OPEN, um elemento BGP deve calcular o valor do Hold Time, utilizando o menor valor entre seu tempo de espera configurado e o recebido.

BGP Identifier:

Identificação do BGP, é o seu número IP.

Optional Parameter Length:

indica o tamanho total do campo Optional Parameter sempre formado pela tripla:

Parameter Type:

tipo de parâmetro individual.

Parameter Length:

comprimento deste parâmetro individual.

Parameter Value:

campo de tamanho variável que contém os dados do parâmetro.

Está definido o parâmetro opcional Authentication Information, com os campos:

Authentication Code:

indica o mecanismo de autenticação a ser usado.

Authentication Data:

dados dos mecanismos de autenticação.

3.3 Formato da Mensagem UPDATE

Unfeasible Routes Length:

Indica o tamanho do campo Withdrawn Routes. Um valor 0 indica que nenhuma rota será cancelada.

Withdrawn Routes:

Contém uma lista de prefixos de endereços IP para as rotas que serão retiradas de serviço. Cada prefixo IP está codificado segunda a dupla:

Length:

Indica o tamanho em bits do prefixo do endereço IP.

Prefix:

Contém os prefixos IP.

Total Path Attribute Length:

Indica o comprimento total do campo Path Attributes em octetos.

Path Attributes:

Cada atributo é composto pela tripla: Attribute Type, Attribute Length, Attribute Value

Attribute Type: são 16 bits, com o seguinte significado:

bit 0 (mais significativo):

1 se o atributo for opcional;

0 se for bem conhecido.

bit 1:

1 se o atributo for transitivo;

0 caso contrário. Para atributos bem conhecidos, deve ser 1.

bit 2:

1 se a informação contida no atributo opcional transitivo é parcial;

0 se for completa.

Obs.: Para atributos bem conhecidos ou para atributos opcionais não-transitivos, deve ser 0.

bit 3:

0 se Attribute Length ocupar um octeto;

1 se ocupar dois octetos.

bits 4 a 7:

não usados: devem ser ignorados.

bits 8 a 15:

contém o código de tipo de atributo, cujos valores podem ser:

ORIGIN (valor 1):

atributo obrigatório que define a origem da informação de rota. Seus valores podem ser:

0 à IGP: informação interior do Sistema Autônomo

1 à EGP

2 à Incompleto: nenhum dos dois anteriores

AS_PATH (valor 2):

atributo obrigatório que é composto por uma seqüência de segmentos de rotas. Cada segmento é composto por: Path Segment Type, Path Segment Length, Path Segment Value.

Path Segment Type: (um octeto)

Pode conter dois valores:

AS_SET (valor 1):

conjunto desordenado de SAs.

AS_SEQUENCE (valor 2):

conjunto ordenado de SAs.

Path Segment Length: (um octeto)

Indica o número de SAs do próximo campo.

Path Segment Value:

contém um ou mais números de Sistemas Autônomos, codificado cada um em dois octetos

NEXT_HOP (valor 3):

campo obrigatório que indica o endereço IP do roteador para onde devem ser enviados dados das destinações listadas no campo Network Layer Reachability.

MULT_EXIT_DISC (valor 4):

campo opcional de 4 octetos, é utilizado pelo Processo de Decisão para definir entre múltiplos pontos de saída para um Sistema Autônomo vizinho.

LOCAL_PREF (valor 5):

campo de 4 octetos, informa outros sistemas BGP de seu próprio Sistema Autônomo do grau de preferência das por uma rota anunciada.

ATOMIC_AGGREGATE (valor 6)

campo de tamanho 0, informa a outro sistema BGP que o sistema local selecionou uma rota menos específica sem selecionar uma rota mais específica incluída nela.

AGGREGATOR (valor 7)

parâmetro opcional transitivo, contém o último número de SA (2 octetos) seguido do endereço IP do sistema BGP, que juntos formam a rota agregada.

Network Layer Reachability Information:

Lista de endereços IP, que é codificada como segue:

Length:

Indica o tamanho em bits do prefixo do endereço IP (1 octeto).

Prefix:

Contém os prefixos IP.

3.4 Formato da Mensagem KEEPALIVE

Mensagens KEEPALIVE são mensagens trocadas periodicamente com o propósito de verificar se a comunicação entre os vizinhos está ativa. A mensagem consiste de apenas um cabeçalho de mensagem e tem comprimento de 19 octetos.

3.5 Formato da Mensagem NOTIFICATION

Error Code

indica o tipo da mensagem NOTIFICATION:

Código de Erro                 Nome Simbólico

1                                Message Header Error

2                                OPEN Message Error

3                                UPDATE Message Error

4                                Hold Timer Expired

5                                Finite State Machine Error

            6                                Cease

Error Subcode:

provê informação mais específica sobre a natureza do erro reportado. Se nenhum Error Subcode apropriado for definido, o campo apresenta valor 0.

Message Header Error subcodes:

                               1  - Connection Not Synchronized.

                               2  - Bad Message Length.

                               3  - Bad Message Type.

         OPEN Message Error subcodes:

                               1  - Unsupported Version Number.

                               2  - Bad Peer AS.

                               3  - Bad BGP Identifier.

                               4  - Unsupported Optional Parameter.

                               5  - Authentication Failure.

                               6  - Unacceptable Hold Time.

         UPDATE Message Error subcodes:

                               1 - Malformed Attribute List.

                               2 - Unrecognized Well-known Attribute.

                               3 - Missing Well-known Attribute.

                               4 - Attribute Flags Error.

                               5 - Attribute Length Error.

                               6 - Invalid ORIGIN Attribute

                               7 - AS Routing Loop.

                               8 - Invalid NEXT_HOP Attribute.

                               9 - Optional Attribute Error.

                              10 - Invalid Network Field.

                              11 - Malformed AS_PATH.

Data:

Campo de tamanho variável utilizado para diagnosticar a razão da mensagem, cujo valor depende dos dois códigos anteriores.

4 CONCLUSÃO

O que aconteceria se uma grande empresa estivesse conectado à Internet através de um provedor que não “falasse” BGP:

- deveria ser criada uma rota default entre a empresa e o provedor e todos os pacotes não-locais sairiam pela interface especificada pela rota;

- e o provedor provavelmente teria de configurar rotas estáticas até a empresa e redistribuir estas rotas estáticas através do IGP e configurar estaticamente o BGP.

Resumidamente o provedor teria que anunciar estaticamente ao mundo estas rotas e estaticamente roteá-las dentro da sua rede através de linhas privadas. E se a empresa estivesse usando endereços agregados não seria anunciado ao mundo, apenas dentro da rede do provedor.

Através do protocolo BGP que o usuário se comunica com o resto do mundo e parafraseando Douglas E. Comer [2]: “BGP é a cola que mantém a Internet unida e permite a interconexão universal”.

5 REFERÊNCIAS BIBLIOGRÁFICAS

[1] Tanenbaum A . - Redes de Computadores – Tradução da 3^a Edição – Campus, 1997

[2] Internetworking with TCP/IP - Principles, Protocols and Architecture
Douglas E. Comer, 3^rd Edition, 1995, Prentice Hall

[3] Moura, Alex Soares - O Protocolo BGP4 (Parte 1), RNP News Generation, Vol.3/No.2, Julho 2000

[4] Moura, Alex Soares - O Protocolo BGP4 (Parte 2), RNP News Generation, Vol.3/No.3, Julho 2000

[5] Moura, Alex Soares - O Protocolo BGP4 (Parte 3), RNP News Generation, Vol.3/No.4, Agosto 2000

[6] T.J. Watson - RFC 1771 - A Border Gateway Protocol 4 (BGP-4), March 1995

[7] Y. Rekhter, T.J. Watson, P. Gross - RFC 1772 - Application of the Border Gateway Protocol in the Internet - March 1995