Roteamento

O roteamento é a determinação da rota que um pacote deve seguir, de roteador em roteador, para se deslocar de Lisboa a Sidney (p.e.). Como veremos é um processo complexo, com muitos algoritmos possíveis, que teremos que entender para podermos perceber como funciona no conjunto. Para apoio gráfico àquilo de que vamos falar vamos utilizar a Figura 1. Para que possa estar sempre presente durante a análise deverá clicar ou tocar na mesma para a poder abrir noutra janela.

Definições e Referências Genéricas

O custo de um enlace é o peso que é atribuído a esse enlace no peso total da rota. O custo de uma rota é a soma dos custos de todos os enlaces da rota.

Salto é como se designa o percurso entre dois roteadores. O tráfego na Internet é feito Salto a Salto, isto é, de roteador em roteador durante todo o percurso desde a origem até ao destino.

O maior objetivo do roteamento é manter os roteadores informados de qual a melhor rota para chegar a qualquer local, aquela com menor custo e qual é o próximo roteador de salto nesse caminho, para que o pacote possa ser enviado para ele. A Internet é uma rede dinâmica, isto é, há uma permanente mudança de endereços de hospedeiros, novos hospedeiros a chegar, roteadores que vão abaixo, roteadores que reaparecem, novos roteadores, etc. Isto significa que o conhecimento que o roteamento pretende dar aos roteadores sobre o melhor caminho para qualquer lugar tem que ser permanentemente recalculado e atualizado.

Gateway é o nome do roteador de E/S de qualquer sub rede. É a porta da nossa casa.

Um Sistema Autónomo (SA) é composto por um conjunto de roteadores que estão sob o mesmo controlo administrativo e técnico e que usam o mesmo protocolo.

Vamos considerar o espaço da Internet dividido em SA com um número de referência à frente. Aliás, esta é a representação normal para SA, ou seja, todos os SA têm um número à frente, que lhes dá um ID exclusivo – SAn.

Excluímos desta obrigatoriedade as sub-redes stub, isto é, as sub-redes onde o tráfego que entra se destina a elas e o tráfego que sai provêm delas. Estas estão excluídas desta exigência de terem uma ID exclusivo. Podemos considerar que as sub-redes representadas na figura com letras minúsculas são redes stub, pertencentes a pequenas organizações ou a pequenos ISP (Internet Service Provider), ficando fora da referência e numeração SA.

Vamos considerar dois tipos de roteamento:

• O IGP (Interior Gateway Protocols) ou Protocolos de Roteadores Internos, onde são usados essencialmente dois protocolos:
  • o RIP (Routing Information Protocol) ou protocolo de informação de roteamento e
  • o OSPF (Open Shortest Path First).
• O BGP (Border Gateway Protocol) ou Protocolo de Roteador de Borda.

Roteamento Intra-SA

Refere-se este capítulo ao roteamento dentro dos Sistemas Autónomos, onde se inserem o RIP e o OSPF.

RIP (Routing Information Protocol)

Para mais fácil leitura vamos incluir uma ampliação da Área 1 do SA4 que vai ser de seguida analisada, através da Figura 1a.

Vamos começar por mencionar que o custo de um enlace corresponde ao peso que lhe é atribuído e que o peso total de um percurso é a soma do peso de todos os enlaces desse percurso.

O RIP é um protocolo de vetor de distâncias DV (Distance Vector) que usa contagem de saltos como valor de custo. Para isso é atribuído o valor 1 ao peso de todos os enlaces.

Portanto o melhor percurso (o de menor custo) é aquele que tiver menos saltos. Salto é o percurso entre dois roteadores.

Cada roteador mantém uma tabela de roteamento, a tabela RIP. Nessa tabela constam todas as sub-redes atingíveis, com referência em cada caso de qual é próximo roteador de salto para essa sub-rede e do número de saltos (vetor de distâncias) até chegar a essa rede, incluindo o salto para o roteador de entrada (Gateway) dessa sub-rede.

Vejamos como é a tabela RIP do roteador D da Área 1 do SA4 para as diversas sub-redes que pode atingir, na Figura 2.

Para esta tabela pressupôs-se que as sub-redes em letras minúsculas são atingidas a partir do roteador mais próximo com um único salto e que a ligação entre os roteadores I e H, por ter um traço interrompido, terá a existência de um número indefinido de roteadores pelo caminho.

As tabelas RIP, que existem em cada roteador da rede são transmitidas em intervalos de 30 segundos a cada um dos seus vizinhos. Passados 6 períodos sem transmissão, os vizinhos  assumem que o roteador em questão está em baixo.

Admitamos que havia um problema no enlace físico (interface ou conector) que liga os roteadores D e G. Então o RIP vai encontrar caminho alternativo, através do conhecimento que tem das tabelas dos vizinhos. Caso o número de saltos fosse por exemplo de 5 entre I e H então a tabela RIP do roteador D ficaria como na Figura 3.

Admitamos ainda que o valor de 5 saltos entre I e H se devia ao facto de um dos roteadores intermédios, por ser um sistema final se encontrava desligado. Entretanto voltou a conectar-se à rede e, por esse motivo, o número de saltos entre I e H passou de 5 para  2. Como H soube disso através da tabela RIP dos seus vizinhos, recalculou a sua tabela RIP. Da mesma forma fez o D, pelo conhecimento da tabela RIP do H. Assim, a tabela RIP de D passaria a ter o aspeto da Figura 4.

E quando o enlace afetado entre D e G voltasse a funcionar a Tabela RIP de D voltaria a ser a da Figura 2.

Estas alterações podem suceder de 30 em 30 segundos, razão pela qual por vezes dois pacotes do mesmo ficheiro seguem caminhos tão diferentes para chegar ao seu destino.

Num protocolo DV, cada vez que um nó deteta alterações do vetor de distâncias, desde que o valor mínimo do caminho para qualquer rede seja alterado comunica-o ao seu vizinho e assim sucessivamente.

Mas, o protocolo RIP aceita um limite máximo de 15 saltos, uma limitação que restringe a sua utilização a SA de pequena dimensão.

Por essa razão foi concebido o protocolo OSPF, sucessor do RIP, embora o RIP ainda continue a ser muito utilizado. No caso contemplado na Figura 1, devido à dimensão de SA considerada, o protocolo usado foi o OSPF.

OSPF (Open Shortest Path First)

O Open (este open vem de open source) Shortest Path First, foi concebido com o fim de ser o sucessor do RIP. Como tal, não é difícil entender que tenha grandes avanços tecnológicos em relação a este.

O OSPF é um protocolo de estado de enlace LS (Link State).

Neste tipo de protocolo, uma vez que cada nó conhece a identificação e peso de cada enlace que a ele liga, envia um broadcast para todos os nós da rede sobre o estado do seu enlace. Dessa forma é possível a qualquer nó da rede construir o mapa da topologia da rede com identificação e peso de todos os nós e links. Cada nó (roteador) mantém uma cópia da Base de Dados representativa do LS (LSDB – Link State Data Base) de toda a rede do SA ou de uma sua Área.

Esta base que contém a total composição da sub-rede do SA ou de uma sua Área, tem em cada entrada um identificador da Interface, um identificador do link e um custo.

De seguida, cada nó aplica o algoritmo SPF (de Dijkstra) que descreve  a forma como um nó, segundo o Sr Dijkstra,  calcula o mais curto caminho para todos os outros nós na rede e constrói uma tabela com esses valores, considerando-se a si como raiz da tabela.

O OSPF permite um sistema hierarquizado dentro do mesmo SA. Na Figura 1, vê-se como foi implementada essa hierarquização dentro dos SA. Foram criadas 3 Áreas independentes em que o roteamento intra-área envolve só os roteadores que estão dentro dessa área. Cada área é identificada por um número de 32 bits, normalmente expresso sob a forma decimal separada por pontos, tal como o IPv4, mas sem que possa haver qualquer confusão entre os dois.

A existência destas áreas autónomas obriga à existência de roteadores de borda de área ( D, E, F, V, W, X, Y, Z respetivamente para as Áreas 1, 2, 3, 4, 5, 6, 7, 8 da SA4) que, em conjunto com outros roteadores (C e B), efetuam o roteamento inter-áreas dentro do mesmo SA4. Este conjunto de roteadores constitui a área de Backbone do SA4, à qual se deve acrescer o roteador de borda do SA4 (A). Resumindo, o backbone do SA4, representado pela zona a sombreado castanho na Figura 1, é composto pelos roteadores A, B, C, D, E, F, V, W, X, Y, Z.

Vamos lá arranjar uma historieta para melhor ilustrar isto em termos práticos. Uma vez mais o condutor do tal carrinho. Desta vez traz um pacote de um cliente do ISP FRANCOM para uma empresa de Mafra, cliente do ISP PORCOM.

• Pelo caminho encontra um sinaleiro que lhe indica o caminho para outro sinaleiro que conhece todos os clientes PORCOM (o roteador de borda do SA).
• Por sua vez, este indica ao motorista a estrada para o sinaleiro que conhece os clientes LISCOM, um concessionário da PORCOM que serve os clientes PORCOM do distrito de Lisboa (roteador de área).
• Este último já conhece todo o caminho para o tal cliente de Mafra, mas como o caminho é confuso, passando por uma enorme quantidade de cruzamentos, envia-o através dos seus amigos sinaleiros que o vão levar até Mafra, sinaleiro após sinaleiro.

Evidentemente, a representação de 3 áreas é mesmo só exemplificativa. Serão certamente muitas mais.

No OSPF o administrador da rede pode atribuir pesos a cada enlace, podendo os seus pesos ser influenciados pela largura de banda do enlace (quanto menos largura mais peso), pela disponibilidade do enlace, pela distância expressa pelo RTT (Round Trip Time), pela fiabilidade do enlace e outras.

Quando um administrador pretende que um pacote siga um caminho específico mais preferido por ele, basta-lhe atribuir maiores pesos aos outros caminhos.

Assim, podem existir caminhos mais longos (em termos de roteadores atravessados) com custos mais baixos e o caminho que tiver o custo mais baixo é sempre o escolhido.

O OSPF permite o load balancing (distribuição de carga) do tráfego por caminhos com igual custo. Não tem que ser  obrigatoriamente escolhido um caminho concreto como no RIP. Em cada momento, cada roteador dirige o seu tráfego para qualquer dos nós que levam ao mesmo destino com o mesmo custo.

O OSPF introduziu segurança nas mensagens de estado de enlaces trocadas entre os roteadores, como forma de evitar que falsos pacotes de roteamento pudessem ser enviados, permitindo que somente os roteadores autorizados possam comunicar uns com os outros.

Para este fim os roteadores são préconfigurados com uma chave secreta compartilhada e são incluídos nos pacotes que os roteadores trocam entre si resumos das mensagens construídos com essa chave, permitindo assim ao destinatário confirmar a autenticidade do remetente.

O OSPF suporta CIDR e portanto endereços com máscaras de rede de comprimento variável.

Vamos agora começar a viajar fora dos SA. Mas não sem antes referirmos que lá vamos analisar o protocolo BGP cuja versão iBGP é usada ainda no roteamento Intra SA, mas somente nas zonas de Backbone dos SA. Entenderemos isto melhor já de seguida no caso de estudo.

Roteamento Inter-SA

A Hierarquia dos ISP

Os ISP (Internet Service Provider) estão divididos em níveis hierárquicos. Os ISP de acesso, normalmente abaixo de 3 níveis de ISP, tanto podem ser redes empresariais, campus universitários ou ISP que fazem exclusivamente serviço direto aos clientes finais e são servidos pelos ISP de níveis superiores. Este acesso a clientes finais também pode ser feito diretamente por ISP de níveis superiores.

Os ISP de 1º nível, são os SA que constituem a camada de backbone da Internet. São em pequeno número, na ordem das dezenas, têm cobertura internacional, cada um deles está diretamente ligado a todos os outros, cada um está ligado a muitos ISP do 2º nível.

Extraordinariamente estes ISP podem servir clientes ao nível de organizações governamentais ou empresas de muito grande dimensão.

Os ISP de 2º nível usam os serviços dos de nível 1, estando ligados a um ou mais desses, podendo mesmo alguns ISP de nível 2 estar ligados entre si. Prestam serviços aos ISP de 3º nível, aos ISP de acesso ou mesmo diretamente a clientes finais. Para isso podem subdividir-se em áreas autónomas dentro de um mesmo SA.

A figura 1 representa como ISP de 1º nível aqueles que só prestam serviços de backbone, com espaços totalmente a castanho. Todos os ISP de 2º nível, independentemente do facto de poderem estar ligados entre eles, também estão ligados a um ou mais ISP de 1º nível.

Os ISP de 2º nível, representados com espaços a Cinza, dividem os seus serviços por áreas autónomas, representadas por espaços com cores diversas, criando uma área de backbone do SA com sombreado castanho dentro do espaço cinza que representa esse ISP.

Essas áreas atuam como se de ISP de 3º nível se tratassem, embora sejam parte integrante do ISP de 2º nível, provendo serviços aos ISP de acesso, representados pelas letras minúsculas.

Para que fique claro o que é um ISP, imaginem o vosso provedor de Internet. Se for uma grande empresa (Vodafone, NOS, MEO p.e.) pode ser um dos que acabámos de descrever. Se for uma pequena empresa pode ser um ISP de acesso.

Qualquer um deles fornece serviços de acesso à Internet a nível nacional, regional, local e mesmo direto a utilizadores finais.

No caso dos utilizadores finais que usam serviços DSL (Digital Subscriber Line), cabo ou fibra ótica, o aparelho que colocam na nossa casa não é mais do que um roteador com NAT, que converte a rede dos computadores que lhe liguemos, numa rede privada ligada por um switch à interface que tem para o interior. Tem outra interface para o exterior, à qual é atribuído um endereço público por DHCP pelo ISP contratado. Esse roteador também fornece os endereços à rede interna por DHCP.

O endereço da interface desse roteador para o lado da rede privada, por exemplo 198.162.1.1 , que dá acesso ao roteador e à sua interface para a Internet, é a porta dos nossos computadores para a rede pública, aquilo a que se chama Gateway.

BGP (Border Gateway Protocol)

Para um utilizador conectado a um ISP de acesso poder encontrar um servidor num Serviço Autónomo distinto desse, algures no Mundo, precisa de utilizar roteadores que comunicam por BGP. É através deste protocolo que os diferentes SA se dão a conhecer uns aos outros.

O BGP estabelece conexões TCP semipermanentes entre os pares BGP. Essas conexões, conforme se podem ver na Figura 1, podem ser:

• IBGP (Internal Border Gateway Protocol) quando são internas a uma SA, entre diversas Áreas mas sempre em zonas de backbone. como se podem ver em todas as linhas a azul.
• EBGP (External Border Gateway Protocol) quando são externas a qualquer SA, ligando portanto dois roteadores de borda de SA, como se podem ver em todas as linhas a vermelho.

Conexões semipermanentes?

As conexões deviam ser permanentes, mas entre as mensagens que os roteadores trocam de acordo com o protocolo, uma delas é a mensagem KeepAlive, que repetem por um período de tempo acordado. Na falta de tal mensagem a conexão é encerrada.

Os outros tipos de mensagens que trocam são:

• Abertura, que estabelece uma conexão TCP com o seu par definido.
• Atualização, que envia ao seu par informando sobre atualização de rotas de que foi informado.
• Notificação, que envia quando é detetado qualquer erro ou quando um tempo se esgota, informando que passa ao estado de ocioso e porquê.

No BGP os destinos anunciados não são de hospedeiros mas prefixos CIDRizados. Cada prefixo representa uma sub-rede ou um conjunto de sub-redes que podem ser atingidas pelo roteador que anuncia esses prefixos.

Mas, em todos os cabeçalhos que vimos até agora não havia espaço para endereços CIDRizados, isto é, endereços de rede, portanto com máscara de rede junto?

E na realidade não há. Este tipo de endereços é o próprio roteador que constrói e adiciona à sua tabela de roteamento. E constrói a tabela de acordo com as informações que vai recebendo e que propaga.

Mas, na tabela de roteamento que vimos não havia também espaço para tal?

Da maneira que a apresentámos não. Relembremos como era na na Figura 2 em cima, em que:

• ID da sub-rede é o seu endereço CIDR,
• Próximo salto é a identificação do próximo roteador e
• Custo é o peso desse enlace.

Agora vejamos a mesma tabela escrita de outra maneira, já legível para o computador, na Figura 2 em baixo, em que:

• Rede de destino e Máscara de rede descrevem o ID de rede. O endereço 185.35.192.0 com a máscara 255.255.192.0 significam o mesmo que 185.35.192.0/18.
• Gateway significa o mesmo que próximo salto, isto é, contém o endereço da interface do próximo roteador a atingir.
• Interface indica o ID da interface local que se deve usar para atingir o Gateway. Como se sabe, por cada Saída/Entrada do roteador existe uma interface com uma identificação específica.
• Custo indica o custo associado ao uso da rota indicada. Métrica é outro termo que lhe pode estar associado pelo facto de o administrador de rede o utilizar para encaminhamentos preferenciais seus que nada têm a ver com o custo do enlace.

Afinal, os componentes da primeira tabela precisam da decomposição na segunda para poderem funcionar. A esta tabela podem ainda acrescentar-se informações como o AS-PATH (adiante veremos o que é), e outros.

Quando um roteador ou hospedeiro com capacidade de roteamento é ligado à rede são-lhe transmitidas pelos vizinhos as respetivas tabelas de roteamento, indicando-se cada um como próximo salto para as rotas da sua tabela. Em BGP só são transmitidas atualizações de tabelas entre roteadores e as transmissões que concernem as tabelas só são efetuadas quando há necessidade disso. A verificação da ligação em relação aos vizinhos é feita por qualquer roteador através da mensagem keepAlive, de que já falámos atrás.

O endereçamento CIDR dá aos roteadores a capacidade de agregação de rotas, isto é, dado um conjunto de rotas que repitam sempre os mesmo bits iniciais o roteador pode agregar todas essas rotas numa só que apresente o endereço considerando só os bits que se repetem e com a máscara devida.

Se através de um roteador forem atingíveis as redes 188.72.(192, 200, 208, 216, 224, 232, 240, 248).0/21 ele procede de imediato à agregação de rotas e regista na tabela para aquela rota 188.72.192.0/18.

Aproveitamos para realçar outra propriedade do endereçamento CIDR. Suponhamos que uma daquelas rotas anunciadas atrás, por exemplo o 188.72.216.0/21 não fazia parte do conjunto de redes atingíveis por aquela rota.

Então, o roteador já não podia fazer a agregação!

Conclusão precipitada. Podia fazê-lo à mesma, porque a rota para o 188.172.216.0/ 21 apareceria anunciada noutra rota e uma das propriedades do BGP sobre endereçamento CIDR é que opta sempre pela rota em que o número de bits coincidentes é maior. Neste caso, apesar de também ser anunciado pelo primeiro, como tem um anúncio mais específico, opta por esse.

Vamos lá ver então se entendemos como é que um roteador BGP na Internet consegue ter conhecimento de todas as rotas possíveis e todos os destinos existentes. Facilmente se entende que, se não fosse o CIDR isto daria uma tabela gigantesca. Mas mesmo assim, o número de entradas numa tabela de roteamento era em 2010 superior a 300.000.