Uma grande conquista que a informática deu ao longo do tempo foi o melhoramento no conhecimento de rotas. Se analisarmos o contexto histórico, veremos que essa evolução contribuiu para o que chamamos de grande rede, a internet.

O rotamento tem por objetivo determinar caminhos a serem seguidos, em posse disso há uma necessidade de conhecimento da topologia da rede e como estão definidos os dispositivos que possam interligá-los, portanto é importante lembrar que o conceito de roteamento é diferente de roteador, que é um nome que se dá a um equipamento responsável por dar acesso a redes diferentes. Com o auxílio da teoria dos grafos, os roteamentos são capazes de solucionar alguns problemas relacionados ao conhecimento da topologia da rede, que por sua vez consiste em encontrar o melhor caminho a se percorrer.

As rotas usam um critério intuitivo de buscar a rota com menor número de nós, embora nem sempre o menor caminho possua melhor desempenho, velocidade ou menor custo. Então surge um conceito de menor custo, esse é o valor numérico associado a um enlace que demarca velocidade de atraso, portanto, se os custos de todos os nós de uma rede tivessem o mesmo valor, prevaleceria a rotas com menor número de nós. Para saber esse valor de cada custo é preciso criar uma tabela de roteamento, pois ela é fundamental no procedimento de escolhas de rotas. Essa tabela é fundamental pois na hora de receber um datagrama o nó verifica para quem é destinado, consultando na tabela criada.

O conhecimento dessa tabela se dá por meio de algorítimos de roteamento, cabe a eles definirem entre vários caminhos o de menor custo. Esses algorítimos ao longo do tempo foram sendo aprimorados para suprirem necessidades que foram surgindo.

Basicamente podemos citar dois tipos de algorítimo.

Algorítimos de roteamento

• Link state (LS) - Determina o melhor caminho entre a fonte e o destino a partir do conhecimento completo da topologia da rede.
• Distance Vector (DV) - Conhecimento parcial da topologia da rede, que consiste em conhecer somente os vizinhos da rede.

Naturalmente percebe-se que o algorítimo (DV) antecede o algorítimo (LS), que por sua vez foi criado para solucionar problemas de falhas de limitação do diâmetro da rede, consumo de banda feito pela inundação de pacotes e contagem para o infinito, que era um dos problemas mais graves. Através da construção de uma matriz de conectividade, todos os nós de uma rede são capazes de conhecer a topologia da rede como um todo e o custo associado a todos os enlaces, onde cada nó é responsável por conhecer o custo de enlace até seus vizinhos e divulgá-los para a rede como um todo. Em posse dessas informações, cada nó processa um algorítimo de menor caminho.

A identificação dos vizinhos é feita por meio de um envio de pacote "Hello" para cada enlace no momento em que um nó é iniciado, em resposta os nós intermediários enviam uma resposta com o endereço da rede. Após descobertos os vizinhos é necessário estimar o custo do enlace, no qual um pacote "echo" é enviado para os mesmos nós que foram identificados, que respondem eventualmente. Neste processo é medido o tempo de ida e volta (Round Trip Time - RTT) e calculado tempo médio, sendo somado os tempos e divido por dois, isso é basicamente uma combinação de atraso e a capacidade de transmissão do enlace. Após esse processo a tabela contendo os vizinhos e o custo para cada nó são enviados para toda a rede por inundação ou mecanismos de difusão (brodcast) ou multidifusão (multcast).

Esses pacotes são numerados sequencialmente para a evitar a duplicidade, onde a cada nova divulgação o nó receptor compara o número de sequência, se for superior descarta o antigo. A cada inicialização de cada nó essa sequência é zerada, o que causa problemas de transmissão.

Para solucioná-lo foi criado o tempo de vida de cada pacote. Um protocolo que utiliza o Link State é o OSPF (Open Shortest Path First), que atualmente tem sido preferencialmente utilizado em redes baseadas em TCP/IP. Ele oferece como métricas de custo, bem como distância, custo, banda e se preocupa com a segurança, garantindo que os pacotes não sejam forjados ou adulterados.

Outras preocupação do LS é o controle do crescimentos de nós na rede, por esse fato classifica-se os roteamentos hierárquicos, que são divididos em áreas de juridição ou região. Um bom exemplo desse no Brasil é o tráfego internacional que entra e sai em São Paulo e Rio de Janeiro, e todos os nós intermediários detém esse conhecimento.