1. O QUE É ROTEAMENTO?

Roteamento é o processo de reencaminhamento de mensagens nas redes de comutação. A maioria dos dispositivos de roteamento é capaz de descobrir rotas na inter-rede e armazenar as informações de rota em tabelas de roteamento.

As tabelas de roteamento não armazenam apenas informações de caminho. Elas também armazenam estimativas do tempo gasto para enviar uma mensagem em uma determinada rota. Essa estimativa de tempo é conhecida como custo de um determinado caminho. Existem vários métodos para estimar os custos de roteamento, entre eles podemos citar:

• Contagem de saltos (hop count): descreve o número de Roteadores que uma mensagem deve atravessar antes de chegar ao seu destino. Se, supostamente, todos os saltos gastam o mesmo tempo, o melhor caminho é aquele que possui a menor contagem de saltos.
• Contagem de tiques: é uma estimativa de tempo real, em que um tique é uma unidade de tempo definida pela implementação do roteamento.
• Gasto relativo: é qualquer medida de custo (incluindo o custo monetário) definida para usar um determinado Link.

1.1. Seleção Estática

A seleção estática de rota se caracteriza por usar caminhos programadas pelo administrador de rede. É um tanto custosa, pois o administrador deve preencher manualmente a tabela de roteamento do Roteador.

Além disso, sistemas estáticos não funcionam bem em ambientes de rápido crescimento ou constantes mudanças, visto que a medida que a topologia da rede muda, todos os Roteadores da rede deverão ter suas tabelas manualmente atualizadas.

Erros na configuração das tabelas de roteamento estático são difíceis de se detectar e corrigir, pois não se sabe se o erro está no Link ou se as tabelas foram configuradas incorretamente.

Uma característica importante: sempre que for necessário enviar um pacote para um determinado Roteador, será usado o mesmo caminho. Portanto, se por acaso o Link utilizado para alcançar o Roteador estiver inoperante, o pacote não conseguirá chegar ao seu destino.
 
 

1.2. Seleção Dinâmica

Em um ambiente dinâmico, os Roteadores comunicam-se trocando informações de roteamento. Com os algoritmos dinâmicos os Roteadores incorporam dinamicamente mudanças na rede acrescentando ou apagando entradas de suas tabelas de roteamento.

A seleção dinâmica de rota usa as informações de custo do roteamento para selecionar o caminho com melhor relação custo/benefício para o envio de um determinado pacote. Como as condições da rede mudam e isso se reflete nas tabelas de roteamento, o Roteador pode selecionar caminhos diferentes para manter os custos baixos.

Todos os Roteadores usam alguma forma de medir qual é o melhor caminho a ser escolhido. Esta escolha se baseia no número de Roteadores que o datagrama terá que atravessar (hop count), atrasos de transmissão, capacidade das linhas e distâncias definidas administrativamente.

Existem dois algoritmos de roteamento dinâmico que são mais usados. O Vetor Distância (Distance Vector) e o Estado de Enlace (Link State). A partir de agora veremos como cada um deles funciona e quais as suas principais características.
 
 

2. ALGORITMO VETOR DISTÂNCIA

A técnica Vetor Distância é bastante simples, tendo em vista que ela é baseada na "distância" entre dois pontos. Esta distância refere-se ao número de Roteadores existentes no caminho utilizado.

Denominamos de hop (salto) a passagem de um datagrama por cada Roteador, portanto a distância entre um ponto e outro é medido em hops.

Periodicamente, os Roteadores enviam cópias de suas tabelas de roteamento para todos os Roteadores que possam alcançar diretamente (Broadcast). Quando um Roteador recebe uma tabela de roteamento proveniente de outro, este verifica se existem rotas mais curtas que as suas ou inexistentes em sua tabela, atualizando então a mesma.

O algoritmo Vetor Distância é um algoritmo eficiente, mas pode ser igualmente ineficiente. Como as alterações devem passar pela rede de Roteador para Roteador, pode ser que demore para uma alteração tornar-se conhecida por todos os Roteadores da rede. O que pode causar erros de roteamento (ou Loops de roteamento) e gerar a Contagem para o Infinito (Counting to Infinity). A Contagem para o Infinito será discutida mais adiante e trata-se de um problema que pode ser solucionado facilmente.

Além disso, os freqüentes Broadcasts de informações de roteamento produzem altos níveis de tráfego na rede, podendo prejudicar o desempenho em redes maiores.

O algoritmo Vetor Distância é implementado pelo protocolo RIP, ou seja, o RIP é um protocolo pertencente à família do algoritmos Vetor Distância. O protocolo RIP e suas características não será apresentado aqui por não pertencer ao escopo desse trabalho.
 
 

2.1. Tabelas de Roteamento

As tabelas de roteamento são compostas basicamente por três campos: o Endereço destino, o Link usado para alcançar esse destino e o seu respectivo Custo. Veja abaixo:
 
 

Para cada endereço de destino haverá uma única entrada na tabela de roteamento do Roteador, ou seja, o número médio de registros da tabela é equivalente ao número médio de Roteadores presentes na mesma sub-rede.
 
 

2.2. Partida Fria (Cold Start)

Durante o processo de inicialização e construção das tabelas ocorre o que chamamos de "partida fria". Suponha que todos os Roteadores de uma determinada rede sejam ligados ao mesmo tempo. Nesse momento, cada Roteador requer um conhecimento mínimo e permanente de cada um dos nós aos quais ele está conectado diretamente, simplesmente para que ele possa lembrar o endereço desses nós e possa identificar os Links aos quais eles estão conectados. Isto é caracterizado como "conhecimento local", ou seja, os nós sabem as suas condições locais, mas ignoram a topologia global da rede. Um Roteador não sabe quantos outros nós existem. Nessa condição inicial, a tabela de roteamento está na sua forma esquelética. Ela contém somente uma entrada, para o próprio Roteador.

A partir daí os Roteadores enviarão seu vetor de distância para todos os seus vizinhos, através do Broadcast das informações de suas tabelas. Conseqüentemente, em um dado momento, todos os nós terão suas tabelas com as informações de roteamento preenchidas e saberão chegar a qualquer Roteador presente na sub-rede.
 
 

2.3. Contagem para o Infinito

Considere a seguinte sub-rede:
 
 

Agora vamos supor que as tabelas de roteamento estejam no seguinte estado:
 
 

Como podemos observar na Figura 3, as tabelas estão corretas e o algoritmo funciona perfeitamente quando um pacote chega a um Roteador e este deve repassar o pacote para outro. Mas, considere agora que, por algum motivo, o Link 2 não está mais funcionando. Veja a Figura 4. Quando B detectar que o Link 2 não está mais respondendo, vai assumir que a distância para alcançar C é infinita, atualizando assim a sua tabela:
 
 

Nesse momento, B deve realizar o Broadcast de sua tabela de roteamento para avisar aos outros nós da rede, nesse caso o nó A, que eles devem atualizar suas tabelas também. Mas, vamos imaginar que antes disso, B recebeu uma tabela de roteamento vinda de A. Ao analisar as informações contidas no vetor de distância de A, B vai descobrir que A sabe chegar a C pelo Link 1 com um custo 2. Como 2+1 é menor que Infinito, a tabela de B ficará da seguinte forma:
 
 

Veja que nesse caso temos um Loop de roteamento. Pois se um pacote chegar ao Roteador A com destino C, A o enviará pelo Link 1. Da mesma forma, se um pacote chegar a B com destino C, B o enviará pelo Link 1. O pacote ficará transitando entre A e B até que seu "tempo de vida" se esgote.

Suponhamos que B envie seu vetor de distância a A. Quando A receber, vai atualizar a informação sobre como alcançar C, pois B está informando a A que o custo que ele tinha para alcançar C, que antes era 1, agora é 3. Note então que a tabela de A ficará da seguinte forma:
 
 

Após a atualização, A sabe chegar a C através do Link 1 com um custo 4. Sendo que antes era 2.

Se continuar havendo o Broadcast de informações entre A e B, dessa forma ambos irão sempre incrementar o custo para chegar a C de 2 unidades. Gerando assim o que chamamos de "contagem para o infinito". Para interromper essa contagem é necessário criar uma convenção estabelecendo o que é infinito. Pode ser um número relativamente grande, maior que o tamanho do mais longo caminho possível na sub-rede. Quando a distância ou custo tiver alcançado esse valor, a entrada na tabela de roteamento é alterada para Infinito e conseqüentemente o endereço de destino se torna inacessível.
 
 

3. ALGORITMO ESTADO DE ENLACE

Uma das premissas básicas do algoritmo Link State, também conhecido como Shortest Path First (SPF), define que todos os Gateways participantes da estrutura Core da Internet conheçam toda a topologia da rede e não parte dela como ocorre em algoritmos Vetor Distância. Na verdade cada Roteador envolvido deve ter um mapa com todos os demais Roteadores da rede e as respectivas redes conectadas.

As redes são consideradas Links ponto a ponto, onde um Roteador alcança outro diretamente. Nesta técnica não são trocadas informações sobre distâncias mas sobre o Status ou estado de cada Link. Portanto, um Roteador tem por função testar o estado de cada Link com quem mantenha ligação direta e após isto enviar periodicamente o resultado para os demais Roteadores. Para testar o estado de um Roteador vizinho um Roteador envia periodicamente mensagens para reconhecer se o vizinho está "vivo" e "alcançável".

Quando um Roteador recebe uma resposta, ele considera o Link entre os envolvidos com Status "Up", caso contrário considera o mesmo "Down". Para informar aos demais Roteadores da rede quanto ao estado dos Links, cada Roteador envia periodicamente uma mensagem que lista todos os Status correspondentes a cada Link com os quais tem ligação direta. Estas mensagens de Status não especificam rotas ideais, apenas apontam o estado de cada Link. Cada Roteador que recebe mensagens de Status é responsável pela propagação das mesmas na rede. Ao receber uma mensagem de Status de Link, além de providenciar a propagação da mesma, cada Roteador efetua a atualização de sua tabela de Status.

O processamento da escolha da melhor rota é efetuado em cada Roteador utilizando um algoritmo denominado Dijkstra que efetua a computação do caminho mais curto para todos os destinos possíveis a partir de determinada fonte, usando sempre os Links com Status "Up" e buscando o caminho mais curto (menor número de Roteadores e Links considerando as velocidades dos mesmos).

O algoritmo aparentemente dificulta mudanças na topologia da rede, pois a cada alteração, todos os mapas devem ser atualizados; porém, o Roteador se torna independente de Roteadores intermediários para o cálculo de rotas, uma vez que já possui toda a topologia da rede.

Depois que os Roteadores tiverem trocado as informações de roteamento sobre a rede, eles só enviarão o Broadcast de mensagens quando houver alguma mudança. Lembrando que as mensagens a serem trocadas entre os Roteadores são menores porque transmitem apenas o estado de enlace, isto é, o tamanho é proporcional ao numero médio de Roteadores aos quais cada Roteador está conectado diretamente. Assim sendo, este algoritmo se adapta melhor em redes extensas.

Roteadores em mal funcionamento são facilmente detectáveis, já que todos devem manter uma base de dados idêntica. Bastando então verificar a consistência das tabelas de um Roteador em relação à base de dados de outro.

Um dos únicos pontos negativos desse algoritmo é que requer grande quantidade de memória, já que cada Roteador deve manter atualizada uma base de dados contendo toda a topologia da rede. E requer também um maior tempo de processamento (CPU), para efetuar o cálculo da menor rota. Portanto, são necessárias máquinas mais sofisticadas e velozes, o que encarece a implementação a sua implementação.

O algoritmo Estado de Enlace é implementado pelo protocolo OSPF (Open Shortest Path First).
 
 

3.1. A Tabela de Roteamento

A base de dados no algoritmo Estado de Enlace é composta basicamente pelo endereço de Origem, o endereço de Destino, o Link que une esses dois endereços e seu respectivo Custo, além de um Número de seqüência que serve para distinguir uma informação antiga de uma mais recente. Veja um exemplo da tabela de roteamento para o caso da Figura 2:
 
 

3.2. O Protocolo Flooding

O propósito de um protocolo de roteamento é adaptar as rotas às mudanças constantes da rede. Isso pode ser feito somente se as bases de dados forem atualizadas logo após uma mudança ocorra no estado de um Link. O algoritmo Estado de Enlace utiliza o Flooding para realizar essa tarefa.

Um Roteador envia as informações para todos os Links aos quais está conectado diretamente para informar as modificações detectadas e, quando outro Roteador recebe essas informações, ele deve prosseguir da seguinte forma segundo o algoritmo de Flooding:

1. Receber a mensagem. Analisar o registro na tabela de roteamento;
2. Se o registro ainda não está presente na sua tabela, adiciona à mesma e então faz o Broadcast da mensagem;
3. Senão, se o número de seqüência na base de dados é menor que o número de seqüência da mensagem, substitui o registro pelo novo valor e faz o Broadcast da mensagem;
4. Senão, se o número de seqüência contido na tabela é maior, transmite o valor que está na base de dados em uma nova mensagem através do Link de onde a mensagem anterior veio;
5. Senão, se os números são iguais, não faz nada.

3.3. Suporte a Múltiplas Métricas

A precisão da computação no algoritmo Estado de Enlace faz com que seja possível o suporte a várias métricas paralelamente. Portanto, na hora de executar o cálculo do caminho mínimo, o algoritmo pode ainda considerar várias características dos Links, entre elas podemos citar:

• A largura da banda;
• O atraso de transmissão;
• O custo.

4. CONCLUSÃO

Conforme pudemos observar, o algoritmo Vetor Distância é fácil e funciona eficientemente apenas em redes de pequena proporção. Pois, devido às demoras nas atualizações e aos erros de roteamento causados por informações incorretas, podem ocorrer Loops de roteamento. Se as modificações na topologia da rede forem constantes, vimos também que os Broadcasts das tabelas de roteamento de todos os Roteadores podem saturar os meios de transmissão. Por fim, é um algoritmo simples, mas não é indicado para operar em redes de grande mutabilidade e de volume maior.

O algoritmo Estado de Enlace é mais complexo, porém se adapta melhor às grandes redes. É mais seguro, pois mantém toda a topologia da rede armazenada em cada Roteador. Sendo assim, menores são as chances de ocorrerem falhas ou erros de roteamento. Possui a vantagem de trocar apenas informações sobre o estado de cada Link. Dessa forma, não sobrecarrega tanto o meio com informações sobre o Status de cada Link. Além de transmitir somente quando o estado de um Link é modificado.

Apesar da implementação do Estado de Enlace ser mais custosa, esse algoritmo se mostra mais eficiente que o Vetor Distância.
 
 
 
 

5. BIBLIOGRAFIA

HUITEMA, Christian. Routing in the Internet. Prentice - Hall, 1995.