Trabalho AV1 Protocolos de Roteamento

Prévia do material em texto

Trabalho AV1 Protocolos de Roteamento
 de MarcosSousaFerre | trabalhosfeitos.com
 Centro Universitário Estácio do Ceará - FIC
ALGORITMOS DE ROTEAMENTO
Professor Andrey
Fortaleza
2014
Marcos Sousa Ferreira
ALGORITMOS DE ROTEAMENTO
Trabalho Parcial da Disciplina de
Protocolos de Roteamento do curso de
Graduação Tecnológica em Redes de
Computadores,
que
conceitua,
fundamenta e exemplifica aplicações dos
algoritmos de roteamento.
Fortaleza
2014
SUMÁRIO
1
INTRODUÇÃO
01
2
PROTOCOLOS DE ROTEAMENTO
01
3
ALGORITMO DE ROTEAMENTO
02
4
ALGORITMO VETOR DISTANCIA
02
5
ALGORITMO ESTADO ENLACE
03
6
ALGORITMO DE ROTEAMENTO HIERARQUICO
04
7
CENÁRIO PRÁTICO(ROTEAMENTO HIERARQUICO)
06
Introdução
A principal função da camada de rede é rotear pacotes da máquina de
origem até a máquina de destino. Nas sub-redes, em grande maioria, os pacotes
necessitam de vários hops(saltos) para completar o trajeto. Os algoritmos
responsáveis por determinar as rotas e as estruturas de dados que eles utilizam
constituem um dos elementos mais importantes do projeto da camada de rede.1
Protocolos de Roteamento
O roteador em uma rede geograficamente distribuída é um dos principais
dispositivos responsáveis pelo sucesso do ambiente. Roteadores são os
dispositivos responsáveis pelo recebimento e redirecionamento dos pacotes na
rede. A decisão de redirecionamento é usualmente baseada na topologia e nas
condições de contorno do ambiente.
Visando uma eficiência no redirecionamento dos pacotes em uma
determinanda rede, os roteadores trocam entre si, através de protocolos de
roteamento, informações sobre o ambientede rede.
A Classificação dos protocolos de roteamento é feita de acordo com as
diferentes abordagens adotadas pelos algoritmos de roteamento, que são:
- Protocolos de roteamento adaptativos: onde as decisões
tomadas constituem um reflexo de carga da rede e de possíveis trocas
na topologia de rede.
- Protocolos de roteamento não-adaptativos(estáticos): onde não
considera em suas decisões medidas(ou estimativas de trafego) e a
topologia de rede.
As tabelas de roteamento são classificadas em Estáticas e Dinamicas.
- Tabelas Estáticas: Rotas diretas, todas as informações de rotas são
inseridas manualmente na tabela.
- Tabelas Dinamicas: São montadas e atualizadas constantemente,
visando possibilitar as interligações entre roteadores de forma
continua.
Protocolos que usam tabelas dinâmicas, dois parâmetros são essenciais
para o estabelecimento de roteamento: Conectividade e Custo.
1
TANEMBAUM, 2003, 2 KUROSE ; ROSS, 2009, 3 http://www.eurecom.fr/~camara/dissertacao/node36.html
1
Algoritmo de Roteamento
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.2
Portanto a finalidade de um algoritmo de roteamento é simples: dado um
conjunto de roteadores conectados por enlaces, uma algoritmo descore um ‘bom’
caminho entre oroteador de fonte e o roteador de destino. Normalmente um ‘bom’
caminho é aquele que tem o ‘menor custo.2
Em um algoritmo de roteamento, certas propriedades são desejáveis como
correção, simplicidade, robustez, estabilidade, equidade e otimização. Desses
termos, talvez o que merece uma explicação mais detalhada é robustez. Uma vez
que uma rede de porte considerável utiliza algoritmos de roteamento, espera-se
que ela funcione continuamente durante anos sem apresentar problemas.
Entretanto, durante esse período, haverá falhas de hardware e software de
diversos tipos. Os dispositivos finais, os intermediários e os links iram apresentar
falhas e, assim, a topologia terá mudanças inúmeras vezes.1
O que se espera do algoritmo de roteamento é que ele deve ser capaz de
aceitar as alterações na topologia e no tráfego sem exigir que todas as tarefas de
todos os hosts sejam interrompidas e que a rede seja reinicializada sempre que
algum roteador apresentar falhas.
Algoritmo Vetor de Distância
O algoritmo de vetor de distância DV – distance vector - é interativo,
assíncrono e distribuído. É distribuído porque cada nó recebe alguma informação
com respeito a um ou mais vizinhos diretamente conectados, faz cálculos e, após,
distribui os resultados de seus cálculos para seus vizinhos. O interativo vem da
troca de dados constante, até que não seja mais possível realizar tal troca. E
assíncrono porque não requer que todos os nós rodem.2
Os algoritmos de roteamento, que usam vetor de distância, operam de forma
que cada roteador mantenhauma tabela (isto é, um vetor), que fornece a melhor
distância conhecida até o destino, e também indica qual linha deve ser utilizada
para a transmissão. Tais tabelas são atualizadas através da troca de informações
com os vizinhos. Esse algoritmo pode ser conhecido também como Bellman-Ford
1
TANEMBAUM, 2003, 2 KUROSE ; ROSS, 2009, 3 http://www.eurecom.fr/~camara/dissertacao/node36.html
2
(algoritmo recebe esse nome pelo seu em homenagem aos seus pesquisadores,
Bellman, 1957 e Ford em 1962).1
No roteamento de vetor de distância, cada roteador mantém uma tabela de
roteamento indexada por cada roteador da sub-rede, e contém a entrada para cada
um de tais roteadores. A entrada possui duas partes: a linha de saída a ser usada
e uma estimativa do tempo ou da distância até o ponto final. Duas unidades
métricas podem ser usadas: o número de hops ou o tempo em [ms].1
Algoritmo Estado de Enlace
O algoritmo de estado de enlace possui o conhecimento de topologia da
rede e todos os custos de enlaces. Isso é possível com a transmissão de pacotes
por cada um dos nós para todos os outros. Com isso é que se chega ao custo de
cada link.2
Torna-se possível o referido acima através de transmissão broadcasting de
estado de enlace.
“O resultado da transmissão broadcasting dos nós é que todos os nós tem
uma visão idêntica e completa da rede (KUROSE ; ROSS, 2009, p. 278).”
O algoritmo de roteamento de estado de enlace é conhecido como Dijkstra,
o nome do seu idealizador. Outro algoritmo que guarda relação muito próxima com
ele é o Prim.1
TANEMBAUM, 2003, 2 KUROSE ; ROSS, 2009, 3 http://www.eurecom.fr/~camara/dissertacao/node36.html
3
“A ideia por trás do roteamento por estado de enlace é simples e pode ser
estabelecida como cinco partes. Cada roteador deve fazer o seguinte
(TANEMBAUM, 2003, p. 383)”.





Descobrir seus vizinhos e aprender seus endereços de rede;
Medir o roteador ou custo até cada um de seus vizinhos;
Criar um pacote que informe tudo o que ele acabou de aprender;
Enviar esse pacote a todos os outros roteadores;
Calcular o caminho mais curto até cada um dos outros roteadores.
Roteamento Hierárquico
A grande desvantagem dos algoritmos baseados em Link State, tanto em
redes móveis como em redes fixas, é que o cálculo do menor caminho exige que
se tenha um mapa de toda a rede. Esta característica pode exceder a capacidade
dos nodos de menor capacidade em grandes redes. Com o aumento das tabelas,
não só mais memória é necessária, mas também maior poder de processamento e
maior banda de rede.
A principal meta dos algoritmos hierárquicos é diminuir o tamanho das
tabelas de rotas. A idéia é dividir a rede em regiões (ou domínios), onde cada
roteador conhece tudo sobrea sua região, mas nada sobre a estrutura interna de
1
TANEMBAUM, 2003, 2 KUROSE ; ROSS, 2009, 3 http://www.eurecom.fr/~camara/dissertacao/node36.html
4
outras regiões. Esta idéia, como já foi mencionado, é o princípio do Zone Routing
Protocol (ZRP) for Ad Hoc Networks, um dos protocolos mais escalares para
MANETs.
Em todas as regiões existe pelo menos um nodoresponsável por fazer o
roteamento para fora da região. Este nodo é conhecido por todos os outros e se
algum nodo precisar enviar pacotes para fora da região, eles são enviados para o
nodo responsável pelo roteamento inter-domínios. Podem ser usados protocolos
diferentes neste roteamento, já que não é necessário que seja o mesmo usado no
roteamento intra-domínio.
Para redes grandes, como a Internet por exemplo, dois níveis hierárquicos
podem ser insuficientes. Pode ser necessário agrupar regiões em clusters,
os clusters em zonas, zonas em grupos e só então, atribuir um nome para este
agrupamento.
O roteamento hierárquico reduz significativamente o tamanho das tabelas de
roteamento e a necessidade de poder computacional dos roteadores. Mas existe
um custo associado a esta vantagem, que é o aumento do tamanho dos caminhos,
este é um custo aceitável já que o número ótimo de níveis para uma rede
com N nodos é de lnN, exigindo um total de e lnN entradas na tabela de roteamento.
Esta abordagem de roteamento, em particular, não pode ser aplicada
diretamente às redes ad hoc. Não existe uma forma de separar os nodos por região,
já que eles são móveis e não estão necessariamente sempre na mesma região,
mas o conceito é muito útil e interessante. 3
1
TANEMBAUM, 2003, 2 KUROSE ; ROSS, 2009, 3 http://www.eurecom.fr/~camara/dissertacao/node36.html
5
Cenário Prático (Roteamento Hierarquico)
Cenário Prático utilizando protocolo OSPF.
1
TANEMBAUM, 2003, 2 KUROSE ; ROSS, 2009, 3 http://www.eurecom.fr/~camara/dissertacao/node36.html
6