Protocolos de Routing I

Todos os protocolos de routing realizam as mesmas funções básicas. Eles determinam a rota preferida para cada destino e distribuem informações de routing entre os sistemas da rede, permitindo interação entre routers. A principal diferença entre os protocolos de routing é como os protocolos realizam estas funções, em particular como decidem qual é a melhor rota. Como a trasmissão de dados nem sempre decorre sem problemas (por exemplo, mal funcionamento na camada de aplicação, impedindo uma mensagem chegue ao destino), os routers e os protocolos de routing divulgam as condições de erro, mas não tentam solucioná-las (responsabilidade dos protocolos das camadas superiores).
Algumas das características que diferenciam os protocolos de encaminhamento são:

1. Convergência: quando a topologia de uma rede muda graças a crescimento, a reconfiguração ou a falha, a base de conhecimento da topologia da rede, representada pelas tabelas de routing nos routers, deve também mudar para se adaptar à nova topologia. Esta adaptação ou convergência deve ser tão rápida quanto possível, para reduzir o período de instabilidade de uma rede.
2. Overhead: o processo de encaminhamento não deve consumir recursos excessivos para atingir seus objectivos. A necessidade de propagar-se as informações de routing entre os routers de maneira rápida e eficiente deve considerar a banda adicional dos enlaces de comunicação utilizada para tal, bem como a complexidade dos algoritmos envolvidos deve considerar a capacidade de processamento dos routers que será desviada do tratamento dos pacotes para a implementação destes algoritmos.
3. Cálculo das métricas: a métrica de um determinado caminho para o envio de pacotes através de uma rede é a medida da qualidade deste caminho, sendo que quanto menor a métrica de um caminho, melhor ele é. Os algoritmos de routing calculam a métrica baseando-se numa única característica de um caminho ou combinando várias características, como:

• Capacidade de tráfego de um enlace (ou banda disponível);

• Atrasos envolvidos no enlace, que podem ser influenciados pela banda disponível ou por possíveis congestionamentos no mesmo;

• Confiabilidade, referente à taxa de erros presente no enlace;

• Carga, que demonstra a ocupação do enlace;

• Hop count, ou o número de routers pelos quais um pacote passa até chegar ao destino.

A implementação de um protocolo de routing envolve a execução de um algoritmo para a determinação das rotas para envio de pacotes. Estes algoritmos podem ser classificados em dois tipos principais:

• distance-vector

Os algoritmos distance-vector mantém uma base de dados de informação de topologia que permite a determinação da direção (vector) e distância para qualquer enlace na rede. Tais algoritmos não permitem a um router conhecer a exacta topologia de uma inter-rede, pois armazenam nas tabelas de rotas somente a informação da sua porta ou do router (direção) para o qual o pacote deve ser enviado e da distância (métrica) que o mesmo deve percorrer até o destino. As actualizações de rotas destes algoritmos envolvem o envio da tabela de rotas inteira de um router para os routers vizinhos, e são executadas periodicamente ou toda vez que for detectada uma mudança na topologia da rede. Quando um router recebe uma actualização de um router vizinho, ele verifica se esta actualização envolve informação de uma melhor rota para alguma das redes por ele conhecidas. Caso positivo, ele actualiza sua própria tabela de rotas.

• link-state

Os algoritmos link-state (também conhecidos como shortest-path-first) mantêm uma base de dados complexa com informações de todos os routers e como eles se interconectam. Estas informações permitem a recriação exacta da topologia da inter-rede. As actualizações de rotas destes algoritmos num router envolvem o envio para seus routers vizinhos de mensagens chamadas LSP (link state packets) que descrevem o estado corrente de todos os enlaces aos quais ele está conectado. Os routers vizinhos, por sua vez, armazenam estas informações numa base de dados de estado de conexões e repassam estes LSP para todos os seus vizinhos, e assim sucessivamente. Desta forma, todos routers da inter-rede recebem o original ou uma cópia do LSP enviado por qualquer outro router. Cada vez que um LSP causa uma mudança na base de dados de estado de conexão de um router, o algoritmo recalcula os melhores caminhos e actualiza a tabela de rotas desse router.