Vetor de distância
Segundo Kurose (2009, p276), o algoritmo de vetor de distância é
iterativo, assíncrono e distribuído. É distribuído porque cada nó recebe alguma
informação de um ou mais vizinhos diretamente ligados a ele, realiza cálculos
e, em seguida, distribui os resultados de seus cálculos para seus vizinhos. É
iterativo porque esse processo continua até que mais nenhuma informação
seja trocada entre vizinhos, e é assíncrono porque não requer que todos os nós
rodem simultaneamente.
O algoritmo de vetor de distância trabalha com uma tabela (ou vetor) que
fornece informações com a melhor distância entre destino e remetente,
determinando qual é o melhor caminho para que um pacote percorra. Suas
tabelas vão sendo atualizadas pela troca de informação dos roteadores
vizinhos, este processo é chamado de routing by rumour, pois este roteador
recebe essa atualização e apenas a aceita, não realizando uma verificação da
informação.
Os protocolos que utilizam dessa tecnologia tem como a principal
característica a quantidade de saltos (nós) para chegar a determinado host ou
rede, independente se a velocidade ou estado dos caminhos até lá forem
piores, pois ele prioriza o valor do menor salto até este host ou rede.
Algoritmos de vetor de distância recebe outros nomes, entre os mais
comuns o algoritmo de roteamento distribuído de Bellman-Ford, nome dos seus
criadores (Bellman, Ford e Fulkerson). Esse algoritmo foi o original da
ARPANET, também utilizado na internet, com o nome de RIP.
Os protocolos do vetor de distância funcionam melhor em situações nas
quais:
• A rede é simples e fixa e não requer um design hierárquico especial.
• Os administradores não têm conhecimentos suficientes para configurar e
solucionar os problemas dos protocolos link-state.
• Redes de tipos específicos, como redes hub-and-spoke, estão sendo
implementadas.
• Os tempos de convergência inesperada em uma rede não são uma
preocupação.
Os principais protocolos IGP, em vetor de distância são:
RIP (Routing Information Protocol), que foi um dos primeiros protocolos de
roteamento internos da internet, e utiliza saltos como métrica para analisar o
custo, a cada enlace, o custo é 1, definindo assim a melhor rota para uma rede
remota. Caso o RIP se deparar com mais de um link, com a mesma quantidade
de saltos, ele executa automaticamente o round-robin load balance, que
distribuí a carga alternadamente entre os link de igual custo. Ele pode realizar
este balanceamento para até 6 links com o mesmo custo. Sua distância
administrativa é 120, e seu tempo de mensagem de atualização é feita de 30
em 30 segundos, e caso algum roteador não responda, essa rota se tornará
inativa.
Segundo Andreoli, cada mensagem de atualização possui as seguintes
informações:
• Endereço de destino da rede/host;
• Endereço IP do gateway que está enviando a mensagem;
• A métrica atual, que por ser única, indica o número de hops para a
rede/host destino.
Características do protocolo RIP são, segundo Filippetti (2008a, p258/259):
• Envia a tabela de roteamento completa para todas as interfaces a cada
30 segundos;
• Utiliza apenas a contagem de hops como métrica;
• Limita a contagem máxima de hops a 15, ou seja, não é viável em redes
de grande porte ou com muitos routers.
• O RIP versão 1 utiliza roteamento classfull, ou seja, todos os dispositivos
conectados à rede devem estar sob a mesma máscara de rede.
O protocolo RIP possui temporizadores, que regulam sua performance,
como destaca Filippetti (2008a, p259).
• Route Update Timer: Estabelece um intervalo (geralmente 30 segundos)
entre as atualizações regulares, nas quais os routers enviam uma cópia
completa de suas tabelas de roteamento para todos os routers vizinhos;
• Route Invalid Timer: Determina a quantidade de tempos que deve correr
(normalmente 180 segundos) antes de um router determinar que uma
rota tornou-se inválida. Essa conclusão será atingida se não ocorrerem
updates sobre uma determinada rota até o fim desse período;
• Route Holddown Timer: Informa aos routers para “reter”, por um período
especifico de tempo (180 segundos, normalmente), quaisquer mudanças
que possam vir a afetar rotas recém-desativadas. Isso previne rotas
inoperantes de serem prematuramente restauradas nas tabelas de
outros routers;
• Route Flush Timer: Estabelece o tempo (normalmente 240 segundos)
entre uma rota tornar-se inválida e sua remoção da tabela de
roteamento. Antes de eliminar uma rota de sua tabela de roteamento, o
router avisa os routers vizinhos que determinada rota encontra-se
inativa. O valor do Invalid Timer deve ser sempre menor que o Flush
Timer. Isso assegura ao router tempo suficiente para atualizar os routers
vizinhos sobre a rota invalida, antes que sai tabela de roteamento seja
atualizada.
A segunda versão do protocolo RIP continua nas mesmas características da
versão 1, porem, na segunda versão sua imagem é melhorada, para ser
utilizada em redes de grande porte. Além disso, a segunda versão dá suporte a
VLSM, ou seja, propaga as informações de máscara de rede em suas
atualizações. A tabela a seguir mostra as diferenças entre as versões.
Tabela 2 - Comparação entre versões do Protocolo RIP.
Fonte: Filippetti (2008a, p263)
IGRP (Interior Gateway Protocol), é um protocolo proprietário da Cisco
Systems Inc., criado na década de 80. Ele veio na tentativa de suprir os erros
do o protocolo RIP, convergindo mais rapidamente e evitando loops de
roteamento, além disso, não possui limitação de saltos entre roteadores. Seu
tempo de atualização é de 90 segundos. A Cisco descontinuou esse protocolo
a partir do IOS 12.2 (13) e 12.2 (R1s4) S.
Seus objetivos destacados, segundo Reis (2003), são:
• Estabelecer roteamento numa grande e complexa rede de
computadores;
• Fornecer uma resposta rápida na troca de topologia de rede;
• Dividir o tráfego entre várias rotas paralelas;
• Capaz de manipular múltiplos tipos de serviços com um simples conjunto de informações;
Para Filippetti (2008a, p264), o IGRP emprega temporizadores diferentes
aos empregados no RIP, que são:
• Route Update Timer: Estabelece um intervalo (default = 90 segundos)
entre as atualizações regulares, nas quais os routers enviam uma cópia
completa de suas tabelas de roteamento para todos os routers vizinhos;
• Route Invalid Timer: Determina a quantidade de tempo que deve correr
(default = 3 x Update Timer) antes de um router determinar que rota
tornou-se invalida;
• Holddown Timers: Especifica o período de holddown (default = 3 x
Update Timer + 10 segundos);
• Route Flush Timer: Estabelece tempo (default = 7 x Update Timer) entre
uma rota tornar-se invalida e sua remoção da tabela de roteamento. Antes de eliminar uma rota de sua tabela de roteamento, o router avisa
aos routers vizinhos que determinada rota encontra-se inativa. O valor
do Invalid Timer deve ser sempre menor que o do Flush Timer. Isso
assegura ao router tempo suficiente para atualizar os routers vizinhos
sobre a rota invalida antes que sua tabela de roteamento seja
atualizada.
Além disso, Filippetti (2008a, p264) ainda destaca suas características,
que são:
• Proprietário da Cisco (apenas routers Cisco podem utilizar IGRP);
• Contagem máximas de saltos = 255, com default em 100 (útil em redes
de grande porte);
• Utiliza largura de banda (bandwidth) e atraso de linha (delay of the line)
como métricas default (composite metric);
• Permite que outras métricas como reliability, load e maximum transmit
unit (MTU) sejam utilizados.
O protocolo IGRP pode balancear carga, porém, conseguem balancear
entre quatro links desiguais, utilizando a largura de banda (bandwidth) para
verificar como a carga será distribuída.
EIRGP (Enhanced IGRP), é um aprimoramento do protocolo IRGP, criado em
1992, que combina protocolos de vetor de distância com os mais modernos
algoritmos de estados de enlace (link-state). Utiliza algoritmo de atualização
por difusão, chamado de DUAL, seleciona os caminhos mais eficientes (sem
loop) e rotas mais adequadas para inserção na tabela de sucessores baseados em sucessores adequados. Um sucessor adequado é um roteador vizinho usado para o envio de pacotes, que tem o menor custo até o destino com a garantia de que não faz parte de um loop (Ferreira, 2002).
Para Andreoli, as principais melhorias dessa nova versão são:
• Neighbor discovery/recovery: Apesar de utilizar os mesmos recursos do IGRP, no caso o algoritmo de vetor distância para o cálculo dos
melhores caminhos, o EIGRP utiliza procedimentos semelhantes a
protocolos tipo estado de enlace para comunicação e propagação de
rotas a seus vizinhos. Esse mecanismo baseia-se na utilização de
mensagens de “Hello” com seus vizinhos afim de saber quais os
vizinhos disponíveis para troca de rotas. No caso das atualizações, ao
contrário do IGRP, são feitas atualizações parciais, não enviando mais
toda a tabela de rotas periodicamente. Tais atualizações são feitas
quando a métrica para determinada rede é modificada e somente
divulgada aos roteadores que necessitam de tal informação.
• Protocolo de transporte confiável - RTP: Forma de transporte que
garante a entrega ordenada de pacotes do protocolo de roteamento.
• Máquina de estados DUAL: Utilizada para o processamento de todas as
rotas da tabela. Aplica informações de distância para selecionar de
forma eficiente e livre de loops as melhoras rotas para serem incluídas
na tabela de roteamento. Quando houver uma mudança na topologia, a
DUAL é avalia se existe um sucessor possível. Caso não haja, mas
existem vizinhos anunciado o destino, é feita novamente a
recomputação. Como resultado desse funcionamento, ocorre uma
melhora na a rota será recomputada.
• Suporte a VLSM (Variable-lenght Subnet Mask): Ao contrário dos
protocolos RIP e IGRP, o EIGRP carrega a informação de máscara de
rotas, permitindo o suporte a VLSM, que já é uma prática utilizada na
maioria das grandes redes. Pode atuar na sumarização de rotas.
Segundo Neumann (2010), algumas características do EIGRP são:
• Rápida convergência
• Suporta VLSM
• Updates parcial conserva a largura de banda
• Suporta vários protocolos de camada de rede, IP, IPX, AppleTalk
• Suporte para autenticação
• Sumarização de rotas automática
• Utiliza multicast utilizando o endereço 224.0.0.10
Além disso, ele complementa, definindo as tabelas do EIGRP:
• Neighbor Table: essa tabela mantêm informações sobre os routers
vizinhos ela é através de mensagens hello.
• Topology Table: contém informações de roteamento para escolha do
melhor caminho livre do loop
• Routing table: Armazena as rotas que estão em uso no momento.
E define os tipos de pacotes, que são:
• Hello: Utilizado para identificar neighbors e manter relação de
vizinhança.
• Update: Envia as informações de roteamento.
• Query: Pedido de informações de rota especifica.
• Reply: Responde a uma consulta.
• ACK: Confirmação.
Para Filippetti (2008a, p280), as principais vantagens para se adotar o
protocolo EIGRP, são:
• Suporta múltiplos protocolos de camada 3 (IP, IPX, AppleTalk), enquanto
o OSPF suporta apenas IP;
• É um protocolo classless, portanto suporta VLSM e CIDR;
• Suporta sumarização e redes não-contíguas;
• É eficiente em sua operação, sendo sua convergência substancialmente
mais rápida que a de outros protocolos (inclusive o OSPF);
• Utiliza o algoritmo DUAL (Diffusion Update Algorithm), que inibe a
formação de loops e é bastante eficiente.
Apesar de encontrarmos em muitas literaturas dizendo que o EIGRP é
proprietário, a Cisco anunciou recentemente que o protocolo está sendo
liberado para o IETF (o que garante que a Cisco ainda mantenha controle
sobre o protocolo), além disso, Wolfz destaca a importância oportuna da
liberação do protocolo neste momento: o esgotamento do protocolo IPv4 está
obrigando todos a migrar para o IPv6, e o protocolo EIGRP pode ser um
diferencial em relação ao OSPF, pois já há suporte ao IPv6.
Link State
Este algoritmo também é encontrado como algoritmo de Dijkstra, que é o
nome do seu inventor. Este algoritmo tem como principal objetivo calcular o
estado que se encontra o link, abordando características como banda, delay,
confiabilidade e o trafego atual do link.
Uma vantagem significativa dos protocolos que utilizam essa tecnologia
é que suas atualizações são incrementais, isto é, enviam apenas informações
que são novas por multicast, diferente do que faz a tecnologia de vetor de
distância, que envia toda a tabela, significando uma maior agilidade e grande economia de largura de banda, além do mais, este protocolo já foi criado pensando em redes de grande porte, portanto, suas propagações não são via broadcast, mas via multicast, visando que apenas roteadores que estejam utilizando o mesmo protocolo recebam as atualizações necessárias.
Segundo Tanenbaum e Wetherall (2011, p234), a ideia por trás do
roteamento de estado de enlace é simples e pode ser estabelecida em cinco
partes. Cada roteador deve fazer o seguinte:
1. Descobrir seus vizinhos e aprender seus endereços de rede;
2. Medir a distância ou o custo ate cada um de seus vizinhos;
3. Criar um pacote que informe tudo o que ele acabou de aprender;
4. Enviar esse pacote e receber pacotes de todos os outros roteadores;
5. Calcular o caminho mais curto ate cada um dos outros roteadores.
A tabela a seguir faz uma breve comparação entre os protocolos RIP (v1 e
v2), IGRP e OSPF.
Tabela 3 - Comparação entre os protocolos.
Fonte: Filippetti (2008a, p269/270).
*Redes descontíguas são duas ou mais sub-redes de uma rede classfull,
conectadas entre si através de uma rede classfull diferente.
*IGRP usa uma composição de métricas, entre elas largura de banda, delay
(essas duas sendo as defaults), load, reliability, entre outras.
E protocolos Link-State, que são:
OSPF (Open Shortest Path First), foi construído em 1988 e padronizado em 1990, muito parecido como seu sucessor protocolo RIP, que utiliza o algoritmo de Dijkstra, porem possui características mais avançadas, pois ao passar dos anos 80, o protocolo RIP mostrou-se cada vez menos capaz de atender redes de grande porte e heterogêneas, como enviar dados apenas quando há alguma alteração de rotas.
OSPF envia avisos sobre o estado do enlace (conhecidos como LSA - Link State Advertisements), para os outros roteadores vizinhos conectados na
sua área hierárquica. Esse protocolo armazena informações sobre o estado do link, ele também utiliza algoritmos que calculam a menor rota para cada nó.
Para Andreoli, o funcionamento do algoritmo SPF é dividido em 3 partes
principais, que são:
• Cada roteador envia LSAs caso ocorram mudanças na topologia de
redes conectadas a este;
• São feitas comparações entre as adjacências de cada roteador, afim de
encontrar rapidamente falhas em links;
• A partir dos LSAs, cada roteador terá o banco de dados topológico de
sua área, sendo possível calcular a árvores de caminhos mais curtos
para cada destino, formando assim a tabela de rotas que será utilizada.
Essa tecnologia já fora criado visando oferecer soluções para redes
grandes pois ele não opera com propagação via broadcast, mas via multicast, ou seja, apenas roteadores que estão utilizando esse protocolo irão receber as mensagens e atualizações. Outra vantagem dessa tecnologia é que apenas as atualizações são enviadas para os demais roteadores, não enviando a tabela toda, garantindo velocidade, agilidade e maior disponibilidade de largura de banda para a rede. Além disso, o protocolo OSPF prove hierarquização de uma rede, subdividindo áreas. O ABR (Area Border Router), fica encarregado dessa subdivisão.
Os principais conceitos de áreas em OSPF são, segundo Filippetti (2008a, p268):
• A área 0 (zero) sempre deve existir em redes com mais de uma área.
Essa área, em uma rede OSPF, é conhecida como backbone área;
• Todas as outras áreas devem se conectar a área 0. Essa regra deve
sempre ser obedecida, ou a rede OSPF não funcionará a contento;
• Para interconectar uma área que não está diretamente conectada à área 0, deve-se usar o artificio dos “virtual-links”, que nada mais são do que
túneis, para “enganar” o protocolo e fazê-lo pensar que a área em questão encontra-se diretamente conectada à área 0. Mesmo isso sendo
possível, é uma solução pobre e deve ser usada apenas coo uma
medida temporária para remediar o problema, nunca como uma solução
definitiva;
• Como os routers pertencentes à área 0 (backbone) normalmente terão
um processamento mais elevado, é sensato que os routers escolhidos
para fazer parte dessa área tenham porte e capacidade adequados.
IS-IS (Intermediate System-to-intermediate System), protocolo desenvolvido pela ISO/OSI, podendo ser mapeado diretamente nas camadas do modelo OSI. Existem muitas semelhanças do IS-IS para o OSPF, pois ambos são protocolos Link State, além de serem classless e hierárquicos.
Apesar de
possuir características parecidas, possui algumas diferenças, como Filippetti
(2008b) as descreve como principais:
• O modo de manipular os pacotes de atualização entre OSPF e IS-IS;
Enquanto no OSPF é apenas um tipo de pacote “hello” é definido, nas
redes IS-IS os routers possuem 2 tipos de pacotes “hello”, os de Nível 1
e Nível 2.
• Os tipos de routers no IS-IS define tipos de roteadores que podem, até
certo ponto, ser mapeados para os tipos de routers definidos em redes
OSPF.
O protocolo ISIS define basicamente 3 tipos de routers: Level 1 (L1), Level
2(L2), e L1/L2. Routers L1 são definidos em uma única área, e podem ser
mapeados para o “Area Router” do OSPF. Estes routers conectam-se à outras
áreas ISIS via routers L1/L2, análogos aos ABRs (Area Border Routers) de
redes OSPF. Routers L1 usam os routers L1/L2 router como “default gateway” para alcançar redes pertencentes à outras áreas, da mesma forma que um Area Router, no OSPF, usa o ABR. (Filippetti, 2008b).
Protocolos EGP
Protocolos EGP (Exterior Gateway Protocols) para Andreoli, são grupos
de protocolos utilizados para a comunicação inter-AS, ou seja, usado para a
comunicação entre roteadores que se encontram em diferentes sistemas
autônomos. Os protocolos deste tipo garantem que todos os sistemas
autônomos pela Internet mantenham informações consistentes para garantir o funcionamento do roteamento global.
Afonso (2011) afirma que este tipo de roteamento é considerado basicamente de coleções de prefixos CIDR (Classless Inter Domain Routing), identificados pelo número de um Sistema Autônomo.
Um exemplo de protocolo deste tipo seria o:
BGP (Border Gateway Protocol) é um protocolo de roteamento dinâmico que tem a utilização para comunicação entre domínios. Este protocolo prove o melhor caminho de uma comunicação na internet, observando que na internet não um controle efetivo nas alterações de rotas, e foi projetado para evitar loops de roteamento.
O protocolo BGP é considerado um protocolo path-vector, muito
semelhantes com os protocolos distance-vector, pois eles trocam informações
com os vizinhos mais próximos para obter as melhores rotas, enquanto isso, no path-vector, os vizinhos relatam que o caminho inteiro até cada destino,
tornando vantajoso, podendo ajudar a evitar loops de roteamento em que
roteadores fiquem enviando e recebendo um pacote porque cada um pensa
que o outro está mais próximo do destino. Além disso, empresas tendo em
mãos os números das SAs permitem que elas tomem decisões políticas, como
“Não quero que meus dados atravessem a rede de meu competidor"
(Matthews, 2006, p137).
Segundo Filippetti (2008c), o protocolo BGP-4 assume que o roteamento
interno do AS é feito através de um sistema IGP (Interior Gateway Protocol) de roteamento interno. Este pode ser um protocolo de roteamento como o RIP, OSPF, IGRP, EIGRP; ou até mesmo através de rotas estáticas. O BGP
constrói um gráfico dos ASs, usando as informações trocadas pelos “vizinhos
BGP” (BGP neighbors), que são compostas dos números identificadores dos
ASs, os ASN. A conexão entre ASs forma um “caminho” (path), e a coleção
desses caminhos acaba formando uma rota composta pelos números dos ASs
que devem ser percorridos até se chegar a um determinado AS destino.
Além disso, ele acrescenta que para o estabelecimento de uma sessão
BGP entre neighbors (vizinhos) ou peers (pares), basicamente, os seguintes
passos são executados:
• É estabelecida a conexão TCP entre os dois roteadores que trocam
mensagens de abertura da sessão e negociam os parâmetros de
operação;
• O primeiro fluxo de dados transmitido é a tabela de rotas BGP completa.
Posteriores atualizações nesta tabela são feitas, incrementalmente, à
medida que as mudanças ocorrerem;
• Como não há a atualização completa da tabela após a primeira, o
roteador mantém a informação da versão da tabela que todos os seus
peers possuem, enquanto durar a sessão entre eles. Se esta for
interrompida por qualquer motivo, o processo é iniciado novamente a
partir do primeiro passo;
• Mensagens de keepalive são enviadas periodicamente para manter a
sessão aberta;
• Mensagens de aviso são enviadas quando ocorrem erros ou outras
situações especiais;
• Caso uma conexão verifique um erro, uma mensagem é enviada e a
conexão fechada, encerrando a sessão.
Bibliografia
Kurose, James F. Redes de Computadores e a Internet: uma abordagem
top-down. 5a Ed. São Paulo: Addison Wesley, 2010.
Matthews, Leanna. Rede de Computadores: Protocolos de Internet em
Ação. 2a Ed. Rio de Janeiro: LTC, 2006.
Sousa, Lindeberg Barros de. Redes de Computadores: Dados, Voz e Imagem. 8a Ed. São Paulo: Érica, 1999.
Tanenbaum, Andrew; Wetheral, David. Redes de Computadores. 5a Ed. São Paulo: Pearson Prentice Hall, 2011.
Trabalho sobre os “Protocolos de Redes”, apresentado a Faculdade de Informática
de Presidente Prudente, no Curso de Redes de Computadores, na Universidade do
Oeste Paulista, na matéria Roteamento, do 5o Termo, como parte dos estudos da disciplina.
Autor:
Felippe de Abreu
Orientador:
Marcelo
Correia dos Santos
