Algoritmo serve para alguma coisa? OSPF e Algoritmo de Dijkstra
Tags: algorithms, networking, beginners, ospf
Published: 2023-12-22 11:15:41

Quando começamos os estudos na área de computação é comum ouvirmos a importância de estudar lógica e algoritmos. É mais comum ainda que à primeira vista esse estudo seja frustrante e pareça muito abstrato e afastado do nosso imediato.

Por isso, trago um exemplo de protocolo de roteamento baseado no algoritmo de Edsger Dijkstra, cientista da computação holandês, [em artigo inicialmente publicado em 1959](https://gdz.sub.uni-goettingen.de/id/PPN362160546_0001?tify=%7B%22view%22:%22info%22,%22pages%22:%5B273%5D%7D).


#### :hash: Uma pequena introdução

Sabemos que a internet é uma rede de redes interconectadas e entre os muitos equipamentos necessários para viabilizar essas conexões estão os roteadores. Essa grande rede de redes pode ser dividida em **Sistemas Autônomos** (_Autonomous Systems_, AS), que de acordo com a [RFC 2328](https://www.ietf.org/rfc/rfc2328.txt) são "um grupo de roteadores trocando informações de roteamento por meio do mesmo protocolo".

Para garantir que um AS possa se comunicar com outros ASs existe o _Border Gateway Protocol_ (BGP), um protocolo de "borda", uma espécie de [correio da internet](https://www.cloudflare.com/pt-br/learning/security/glossary/what-is-bgp/).

Entre os protocolos internos ao AS (_Interior Gateway Protocol_, IGP) está o OSPF ou _Open Shortest Path First_. Em tradução livre, menor rota aberta primeiro. É ele que vamos estudar aqui.

#### :hash: O que é um grafo?

Um grafo é uma estrutura, uma forma de modelar relações entre entidades ou eventos. É formado por vértices (ou nós) ligados por arestas. Os nós ligados são chamados de adjacências ou vizinhos.  

A partir desse grafo tirado [do artigo de Krushna Prasad Sahoo](https://medium.com/@kp-the-great/how-ospf-protocol-implements-dijkstra-algorithm-53c390199ee8) (que vai bem mais fundo na utilização do algoritmo pelo OSPF) podemos começar a entender como tudo funciona.




![um grafo orientado e dirigido de 7 vértices de cores diferentes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sz7bh6do9a3bcipp5pgj.jpg)





#### :hash: Algoritmo de Dijkstra

O algoritmo basicamente calcula a menor distância entre o nó de origem e todos os outros nós do grafo, atribuindo um valor para cada aresta segundo uma métrica (caracterizando um grafo valorado e dirigido). Isso é feito por meio de iterações até que todos os nós sejam analisados e a menor distância encontrada.

Por exemplo, no grafo acima o nó de origem é **0** e o custo de ir de **0** a **1** é 2 e de **0** a **2** é 6. Para chegarmos ao nó **3** temos as opções da rota **0** -> **1** -> **3** (custo total 7) ou **0** -> **2** -> **3** (custo total 14). Fica evidente que a melhor rota é a primeira. Simplificadamente, é esse o cálculo realizado pelo algoritmo. 

Mais concretamente: no primeiro estágio do processo cada nó (geralmente um roteador) do Sistema Autônomo usa o Algoritmo de Dijkstra para elaborar a própria rota mais curta (_shortest path_) para os nós seguintes. Isso será feito sucessivamente até que se encontre a melhor rota a ser percorrida pelos pacotes até seu destino. Repito: o algoritmo em si é mais complicado e o OSPF funciona de forma mais complexa e conta com mais de uma versão. Para uma visão mais profunda recomenda-se as RFCs.


#### :hash: Como é definido o custo?




> custo = largura de banda de referência/largura da banda (em bps)

Quanto maior a largura da banda menor o custo.

É a partir desse cálculo que os roteadores distribuem o tráfego. Por exemplo, se o custo for igual em todos os caminhos (considerando que sejam rotas internas, de mesmo tipo) o tráfego será igualmente dividido entre todos.

Calculado o custo, usando seu próprio _link state database_ cada roteador armazena sua própria tabela de roteamento e a sincroniza com a de seu vizinho por meio do _Database Exchange Process_. Para otimizar ainda mais o processo o OSPF permite a criação de _áreas_: agrupamentos de redes com topologia interna oculta ao resto do AS. Assim é possível diminuir o tráfego e aumentar o desempenho. Os roteadores possuem um database para cada área que estiverem conectados; portanto, roteadores de borda (conectados a mais de uma área) possuem mais de uma tabela.

#### :hash: Outras características do OSPF

- desenvolvido para funcionar especialmente com TCP/IP e suporta IPv4 e IPv6, além de CIDR

- é um protocolo dinâmico: a comunicação frequente entre nós permite detecção de qualquer alteração na topologia da rede e consequente novo cálculo das rotas

- possibilita flexibilidade nas sub-redes, pois permite a utilização do VLSM (Máscara de Sub-rede de Tamanho Variável)

- possui autenticação com senha ou chave criptografada no cabeçalho dos pacotes, evitando que roteadores desconhecidos acessem a rede


Como pudemos ver o OSPF é um protocolo importante e abrangente e tem no Algoritmo de Dijkstra um de seus pilares. Outros equipamentos usam outros algoritmos para funcionarem, então mesmo que pareçam muito abstratos é importante conhecê-los para termos uma visão melhor sobre nosso objeto de estudo seja ele qual for.