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.
#️⃣ 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 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.
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.
#️⃣ 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 (que vai bem mais fundo na utilização do algoritmo pelo OSPF) podemos começar a entender como tudo funciona.
#️⃣ 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.
#️⃣ 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.
#️⃣ 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.
Top comments (0)