Monday, 8 September 2014
Sunday, 7 September 2014
Friday, 5 September 2014
Algoritmos de Roteamento - Vetor de distância e Estado de Enlace
ALGORITMOS DE ROTEAMENTO
CURIOSIDADE
Um algoritmo de roteamento é a parte do software da camada de rede responsável pela decisão sobre a linha de saída a ser utilizada na transmissão do pacote de entrada. Se a sub-rede fazer uso de datagramas, a decisão deverá ser tomada mais uma vez para cada pacote de dados que é recebido, pois a rota mais indicada pode ter sido alterada desde o último pacote (TANEMBAUM, 2003).
Portanto a finalidade de um algoritmo de roteamento é simples: dado um conjunto de roteadores conectados por enlaces, um algoritmo descore um 'bom' caminho entre o roteador de fonte e o roteador de destino. Normalmente um 'bom' caminho é aquele que tem o 'menor custo' (KUROSE; ROSS, 2009. P. 372).
A tabela de roteamento do gateway é atualizada a partir da execução do seu respectivo algoritmo. Os dois principais são: Vetor de Distância (Vector-Distance) e Estado-de-Enlace (Link-State).
VETOR DE DISTÂNCIA
Os protocolos de roteamento de vetor de distância funcionam com base nas seguintes características:
- enviam cópias da tabela de roteamento, periodicamente, aos seus vizinhos diretamente conectados; toda tabela de roteamento é enviada nessas atualizações periódicas, e não somente em algumas rotas;
- o roteador tem uma visão limitada da rede onde ele "enxerga" somente os vizinhos diretamente conectados e não a rede como um todo;
- analogia com placas de trânsito, onde o caminho (vetor) é determinado em cada ponto (distância) por meio das informações das placas em uma estrada. Cada roteador sabe o próximo salto (roteador) para uma determinada rede e não o caminho completo;
- utiliza o algoritmo de Bellman-Ford.
CURIOSIDADE
Os protocolos de vetor de distância podem ser entendidos como um roteamento por "rumor" ou "boatos", onde as informações de outras redes são aprendidas com base nas informações de vizinhos.
Os protocolos de vetor de distância estão sujeitos a loops de roteamento, justamente pelo fato de as redes serem aprendidas por meio de informações de vizinhos. Nem sempre estas informações refletem a realidade, ou seja, elas podem estar desatualizadas. Para prevenir estes loops de roteamentos, os protocolos de vetor de distância utilizam técnicas de inibição de loops. Veja as técnicas a seguir.
- Contagem até o infinito - limite de saltos que um pacote poderá percorrer antes de ser descartado. Isso evita que o pacote circule indefinidamente formando um loop.
- Split Horizon - previne que o roteador envie atualização sobre uma rota na interface a qual ele aprendeu sobre aquele destino.
- Route Poisoning - anuncia rotas com métrica infinita para uma rota com falha. Métrica infinita é um valor maior do que o permitido pelo protocolo de roteamento.
- Atualizações acionadas/disparadas - atualizações de roteamento são enviadas no momento em que ocorre uma alteração na tabela de roteamento (e não durante o ciclo de atualização do protocolo).
- Holddown - quando ocorre uma falha na rede, um temporizador é iniciado e novas atualizações (com métricas piores vindas de outro roteador) não são aceitas.
Os protocolos de vetor de distância utilizam estas técnicas para prevenir que ocorram loops, mas, mesmo assim, devido ao processo lento de convergência de protocolos e vetor de distância, pode haver ocorrência de loops (ainda que raras).
ESTADO DE ENLACE
Os protocolos de roteamento de estado de enlace funcionam com base nas seguintes características:
- enviam atualizações de roteamento somente quando ocorrem alterações na topologia, ou seja, quando há uma mudança no estado de enlace (link);
- cada roteador tem conhecimento da rede como um todo, ou seja, possui uma tabela topológica com rotas para todas as redes dentro de sistema autônomo;
- convergência inicial mais lenta, ou seja, como cada roteador precisa calcular as rotas para todas as redes dentro do AS, a convergência inicial é mais demorada e consome mais recursos do roteador. Após a primeira convergência, as demais alterações de topologia terão uma convergência muito mais rápida e, portanto, menos suscetível a loops de roteamento;
- analogia com mapas rodoviários, ou seja, cada roteador possui todo o itinerário até a rede de destino. Diferentemente dos protocolos de vetor de distância, que só sabem como chegar até o próximo salto (roteador), os protocolos de estado de enlace têm conhecimento de toda a rede do sistema autônomo da qual ele faz parte;
- utiliza o algoritmo de Dijkstra.
Podemos observar que os protocolos de estado de enlace são mais robustos e menos suscetíveis a loops de roteamento. Isso faz com que os protocolos de roteamento de estado de enlace utilizem uma grande quantidade de recursos do roteador, principalmente, processamento e memória.
REFERÊNCIAS
Livro SÉRIE TECNOLOGIA DA INFORMAÇÃO - HARDWARE INTERCONEXÃO DE REDES (páginas 74,75 e 76.)
Protocolo RIP
RIP (Routing Information Protocol ), Trata-se de um protocolo de tipo vector distância, o que quer dizer que cada switch se comunica com os outros roteadores a distância que os separa, assim quando o switch recebe uma mensagem ele incrementa esta distância e comunica a mensagem aos roteadores diretamente acessíveis, armazenando o endereço seguinte na tabela de encaminhamento de modo que o número de saltos para atingir uma rede seja mínima. contudo este protocolo tem em conta apenas a distância entre dois dispositivos próximo a ele , tendo um número máximo de 15 saltos, no decimo sexto salto para evitar a rotatividade entre os roteadores (loop) o roteador descarta o pacote.
Imagem de rotatividade
Nessa imagem o roteador 5 que se comunicar com o roteador 1 porem o link que conectava o roteador 1 ao 2 caiu ,então o roteador 2 não conhece a rota até roteador 1,quando o roteador 2 recebe o pacote ,ele encaminha pro próximo pro roteador 4,que encaminha pro próximo e assim forma um circulo vicioso, pra evitar esse circulo de saltos, no decimo sexto salto o roteador descarta.
Roteamento Hierárquico
Roteamento Hierárquico
Com o crescimento das redes, consequentemente cresceram também as tabelas dos roteadores, não apenas em quantidade de armazenamento mas também em capacidade de processamento a forma para resolver essa questão foi a criação do roteamento hierárquico.
Roteamento hierárquico são vários roteadores com sistemas autônomos executando o mesmo algoritmo que possui duas tabelas de roteamento, a tabela intra-AS (responsável pelo roteamento entre as AS ) e a tabela inter-AS (responsável pelo roteamento entre as AS) determinando rotas gerando a tabela do roteador, dividindo o problema em varias partes menores .
Sistemas autônomos é um grupo de redes e roteadores controlados por uma única autoridade administrativa. Os roteadores nesse sistema seguem as mesmas ''regras'' de roteamento, onde os protocolos de roteamentos são classificados de acordo com sua atuação.
imagem de Roteamento Hierárquico
Bibliografia :
Subscribe to:
Posts (Atom)