Por José Wemerson Farias Lima

A Internet é uma coleção de redes interconectadas por meio de roteadores organizados de forma hierárquica. Alguns desses são utilizados apenas para trocar dados entre grupos de redes controlados pela mesma autoridade administrativa, enquanto outros fazem também a comunicação entre essas autoridades. A entidade que controla e administra um grupo de redes e roteadores é chamada de Sistema Autônomo - SA.

Um dos trabalhos cruciais da rede, devido ao grande tráfego de dados, é o encaminhamento de pacotes, ou seja, o envio de pacotes. Esse trabalho exige um bom algoritmo não só para calcular a melhor rota, mas também para lidar com fatores como congestionamento em redes e informações sensíveis ao tempo.

O processo de seleção de caminhos para o envio de dados entre pontos distintos dentro de um SA, ou entre diversos AS’s, é conhecido como roteamento. Os dados podem ser roteados de uma fonte até o destino por meio de uma série de roteadores e entre múltiplos AS’s. O principal modelo de roteamento utilizado é o do hop-by-hop, no qual cada roteador que recebe um pacote de dados verifica o endereço de destino desse pacote, determina o endereço do próximo roteador em direção ao destino e entrega o pacote para esse roteador. Esse processo se repete até a entrega do pacote ao seu destinatário.

Para determinar o endereço do próximo roteador em direção ao destino final, um roteador efetua uma consulta à sua tabela de roteamento. As tabelas de roteamento associam o endereço de cada destino ao endereço do próximo hop. Essas tabelas são montadas de acordo com as informações da topologia da rede conhecidas em cada roteador.

Foi o pioneiro da programação, Edsger W. Dijkstra, quem notou que para ver através da complexidade é necessário engenhosidade, e o algoritmo que leva seu nome segue como uma das coisas mais engenhosas na informática. A favor da simplicidade e elegância na matemática, ele acreditava que todo problema complicado tinha uma parte acessível, uma entrada, e a matemática era uma ferramenta a ser usada para encontrá-la e explorá-la com objetivo de resolver o problema.

“Para uma demonstração feita para pessoas não ligadas à informática, o problema tem que ser descrito de forma que não-matemáticos possam compreender.” (Dijkstra). Então, para explicar às pessoas o algoritmo que desenvolveu, Dijkstra propôs encontrar a distância mais curta entre duas cidades na Holanda utilizando seu algoritmo. É este algoritmo que possibilita o Google Maps calcular o menor trajeto entre dois pontos, de forma que nem precisamos pensar no quão complexa pode ser esta tarefa.

Utilizando esses conhecimentos para gerir o fluxo de dados na internet, cada aresta em que os dados vão percorrer deve possuir uma métrica para que o algoritmo possa encontrar um caminho onde a soma dos pesos das arestas seja a mais baixa entre todos os caminhos possíveis entre os pontos. Esses pesos podem ser qualquer valor de parâmetro, como congestionamento, taxa de perda ou velocidade.

Após a definição dos custos, são levantados os valores dos vizinhos do nó inicial. Se o ponto final for um vizinho, o custo do enlace até o destino é o valor entre os nós, caso contrário, o custo do enlace é considerado como infinito.

Com o valor de custo definido como infinito, o vizinho de menor valor passa a ser considerado como ponto inicial e os seus vizinhos são analisados iniciando um loop que verificará todos os vértices até que sejam levantados os caminhos de custos mais baixos.

Porém, o algoritmo que encontra o caminho de menor custo pode apresentar problemas caso alguma aresta esteja interrompendo o fluxo de dados, não restando outra alternativa para escoá-los pela rede. Para esse problema, o chinês Jin Y. Yen desenvolveu um algoritmo que tem como função encontrar os k-menores caminhos. Assim, caso algum nó da rede esteja danificado, outro caminho poderá ser selecionado sem que a transmissão dos dados seja prejudicada.

O algoritmo de Yen funciona de forma semelhante ao de Dijsktra, mas esse faz com que cada nó seguinte seja um novo nó raiz e a partir dele deve-se encontrar um menor caminho até o destino final. Então, para uma rede com ponto inicial em “s” e ponto final em “t”, as k-menores rotas são apresentadas na Figura 2.

É possível perceber a importância que deve ser dada ao cálculo de rotas, já que quando as rotas de uma rede são bem definidas e administradas, a chance de sucesso no bom funcionamento é significativamente maior. Devido ao fato que certos protocolos apresentam uma rápida atualização nas suas tabelas de roteamento, os mesmos terão facilidade em se adequar às mudanças que podem ocorrer na topologia da rede, ocasionadas por algum problema em uma via de acesso de dados ou roteador.

À medida que a internet cresce, faz-se necessário o uso de ferramentas ainda mais poderosas para manter a qualidade e a velocidade do serviço, e a base para tais ferramentas é a matemática. Mas, na informática os números sozinhos não conseguem expor diretamente o que ocorre, e, por isso, é necessário uma interpretação por meio de algoritmos, que desvendem a complexidade dos problemas.

Referências: 

CISCO. EIGRP Stub Routing. CISCO, 2011. ISSN ISBN. Disponível em: http://www.cisco.com/en/US/docs/ios/12_0s/feature/guide/eigrpstb.html. Acesso em: 20 de Março de 2016.

KUROSE, J.F e ROSS, K.W.Computer Networking third edition a top-down approach featuring the Internet, 3 ed, São Paulo: Pearson Addison Wesley, 2006.

PISARUK, Fábio.K-menores caminhos. São Paulo, 2009.

VOIGT, Danilo. Tutoriais Banda Larga.Disponível em: http://www.teleco.com.br/tutoriais/tutorialredeipec1. Acesso em: 20 de Março de 2016.