Noções de Algoritmos e Protocolos de Roteamento

Prévia do material em texto

Redes de Computadores
REDES DE COMPUTADORES
Aula 8
NOÇÕES DE ALGORITMOS E
PROTOCOLOS DE ROTEAMENTO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 2
• Identificar o funcionamento do serviço de roteamento; 
• Comparar protocolos de roteamento estático e dinâmico; 
• Diferenciar os tipos de protocolos de roteamento dinâmico; 
• Interpretar como um pacote é transmitido, entre origem e 
destino, através das redes de computadores.
OBJETIVOS
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 3
ROTEAMENTO
• As mensagens produzidas na camada de aplicação são 
passadas para a camada de transporte que as encapsula em 
segmentos.
• Em seguida é necessário que haja algum protocolo capaz 
de endereçar cada segmento.
• Nas camadas inferiores, rede e enlace, os segmentos são 
encapsulados, em pacotes e quadros.
• A existência de duas camadas que endereçam conteúdos é 
um dos fatores que permitem a comunicação de dados 
entre redes heterogêneas. 
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 4
ROTEAMENTO
• A camada de redes produz pacotes que se mantém íntegros 
até o destino final.
• O quadro se mantém apenas dentro do domínio de 
broadcast.
• Um pacote é endereçado a outra rede é entregue ao 
roteador para que seja comutado de forma adequada. É 
fundamental entender que o pacote é retirado do quadro 
inicial e são montados diversos quadros diferentes ao longo 
do percurso, até seu destino final.
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 5
ROTEAMENTO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 6
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 7
• Nosso foco de estudo é compreender como o roteador 
transfere os pacotes entre a origem e o destino.
• Através dos percurso o pacote passa por alguns roteadores 
e cada um realiza a comutação entre os canais baseado no 
endereço de destino definido no cabeçalho.
ROTEAMENTO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 8
FUNCIONAMENTO DO ROTEADOR – FASES
RECEBIMENTO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 9
FUNCIONAMENTO DO ROTEADOR – FASES
DESMONTAGEM DO QUADRO DE ENTRADA
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 10
FUNCIONAMENTO DO ROTEADOR – FASES
COMPARAÇÃO DA TABELA COM ENDEREÇO DO 
PACOTE
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 11
FUNCIONAMENTO DO ROTEADOR – FASES
DECISÃO DA PORTA DE SAÍDA - REPASSE
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 12
FUNCIONAMENTO DO ROTEADOR – FASES
NOVO ENLACE NA PORTA SELECIONADA
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 13
ROTEAMENTO 
COMO DECIDIR O CAMINHO?
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 14
• O endereço de destino recebido da origem diz ao roteador 
para onde o tráfego vai. 
• É necessário definir a direção, ou seja, qual aporta de 
saída deve ser escolhida. 
• O melhor caminho ao destino é determinado para que o 
roteador possa ser eficaz no encaminhamento dos 
pacotes. 
• Todos os roteadores possuem informações que definem 
suas decisões.
ROTEAMENTO 
COMO DECIDIR O CAMINHO?
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 15
• Todos os roteadores possuem tabelas associando suas 
portas com as redes que estejam conectadas.
• Exemplo:
– Eth0 – 10.0.0.0/24
– Eth1 – 192.168.0.0/24
– Ser0 – 200.20.0.0/16
– Ser1 - *.*.*.*
ROTEAMENTO 
COMO DECIDIR O CAMINHO?
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 16
• Normalmente um “bom caminho” é aquele que tem o 
“menor custo”. Por exemplo, dado que a rede de origem 
172.20.0.0/23 (X) deseja transmitir pacotes para a rede 
destino 172.30.0.0/23 (Y), existem muitos caminhos entre 
as duas redes e cada caminho tem um custo. Um ou mais 
destes caminhos podem ser um caminho de menor custo. 
O QUE É UM BOM CAMINHO
Normalmente, os custos 
relacionados a um caminho 
são representados pelo 
tamanho físico do enlace, a 
velocidade ou o custo 
associados a este enlace.
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 17
• Segundo Kurose, os algoritmos de roteamento podem ser 
classificados de três maneiras:
– Algoritmo de roteamento global ou descentralizado;
– Algoritmo de roteamento estáticos ou dinâmico;
– Algoritmo de roteamento sensível à carga ou insensível 
á carga;
ALGORITMOS DE ROTEAMENTO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 18
• Em algoritmos de roteamento estático, as rotas mudam 
muito lentamente o longo do tempo, muitas vezes como 
resultado de intervenção humana através da configuração 
manual de uma rota. 
• Neste tipo de algoritmo todos os computadores ou 
roteadores na rede tomam suas próprias decisões de 
roteamento seguindo um protocolo formal de roteamento. 
• Em MANs e WANs as tabelas de roteamento para cada 
roteador é desenvolvida individualmente pelo seu 
administrador de rede.
ROTEAMENTO ESTÁTICO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 19
• Os algoritmos de roteamento dinâmico mudam os caminhos 
de roteamento à medida que mudam as cargas dos tráfegos 
ou a topologia de rede. 
• Um algoritmo dinâmico permanece ativo como reação 
direta à mudança de topologia de rede ou de custos dos 
enlaces. 
• Ao mesmo tempo em que são mais sensíveis às mudanças 
na rede, os algoritmos dinâmicos também são mais 
suscetíveis a problemas como loops de roteamento e 
oscilação de rotas. 
ALGORITMO DE ROTEAMENTO DINÂMICO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 20
• Os algoritmos de roteamento global calculam o caminho de 
menor custo entre a origem e um destino usando o 
conhecimento completo e global sobre a rede. 
• Isso exige que o algoritmo obtenha essas informações, de 
algum modo, antes de realmente realizar o cálculo. 
• Estes tipos de algoritmos são frequentemente denominados 
de algoritmos de estado de enlace (link-state – LS) 
ALGORITMOS DE ROTEAMENTO DINÂMICOS
ALGORITMO GLOBAL OU CENTRALIZADO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 21
• No algoritmo de roteamento descentralizado, o cálculo do 
caminho de menor custo é realizado de modo interativo e 
distribuído. Nenhum nó tem informação completa sobre os custos 
de todos os enlaces da rede. Em vez disso, cada nó começa 
sabendo apenas os custos dos enlaces diretamente ligados a ele. 
• Então por meio de um processo iterativo de cálculo e de troca de 
informações com seus nós, cada um nó gradualmente calcula o 
caminho de menor custo até um destino ou um conjunto de 
destinos. 
• Um exemplo de algoritmo de roteamento descentralizado é o 
algoritmo de vetor de distâncias (distance-vector algorithm – DV) 
ALGORITMOS DE ROTEAMENTO DINÂMICOS
ALGORITMO DESCENTRALIZADO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 22
• Os algoritmos de roteamento sensíveis à carga os custos de 
enlace variam dinamicamente para refletir o nível corrente 
de congestionamento no enlace subjacente. Caso haja um 
alto custo associado ao enlacecongestionado, o algoritmo 
tenderá a escolher rotas que evitem esse enlace 
congestionado. 
• Já os algoritmos de roteamento insensíveis à carga, 
atualmente utilizado na internet (RIP, OSPF e BGP) não 
levam em consideração o custo, pois o custo de um enlace 
não reflete explicitamente seu nível de congestionamento 
corrente. 
ALGORITMOS DE ROTEAMENTO DINÂMICOS
ALGORTIMOS SENSÍVEIS À CARGA
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 23
• Um protocolo de roteamento é um protocolo utilizado para 
trocar informações entre computadores, de modo a 
permitir que eles montem e mantenham suas tabelas de 
roteamento. 
• Quando novos caminhos são acrescentados ou quando os 
caminhos estão obstruídos e não podem ser utilizados são 
enviados mensagens entre computadores utilizando o 
protocolo de roteamento.
PROTOCOLOS DE ROTEAMENTO
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 24
• A Internet, na prática não é constituída de um conjunto 
homogêneo de roteadores, todos rodando o mesmo 
algoritmo de roteamento. Ela é constituída de várias redes 
interconectadas, onde cada organização pode executar o 
algoritmo de roteamento que desejar ou ainda, ocultar do 
público externo aspectos internos de rede da organização. 
• Como forma de minimizar a complexidade da gestão 
administrativa e de autonomia destas redes, os roteadores 
foram agrupados formando um sistema autônomos (AS) 
com cada AS consistindo de um grupo de roteadores sob o 
mesmo controle administrativo, isto é , operado pelo 
mesmo ISP ou pertencente a uma mesma rede corporativa. 
ROTEAMENTO NA INTERNET
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 25
• Em um Sistema Autônomo (AS) o algoritmo de roteamento 
que roda dentro do AS é denominado protocolo de 
roteamento intra-AS e ao conectarmos vários ASs entre si, 
um ou mais roteadores em um As terá a tarefa adicional de 
ficar responsável por transmitir pacotes a destinos 
externos ao AS. 
• Este roteadores são denominados de roteadores de borda 
(gateway routers). 
ROTEAMENTO NA INTERNET
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 26
• Um outro ponto a observarmos é que ao ligarmos vários AS 
entre si, será necessário obter informações sobre as 
condições de alcance dos AS vizinhos e propagar estas 
informações entre todos os roteadores internos ao As. 
• Estas ações são realizadas através do protocolo de 
roteamento inter-AS. Desta forma para que dois AS 
troquem informações é necessário que ambos executem o 
mesmo protocolo de roteamento Inter-AS. 
ROTEAMENTO NA INTERNET
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 27
• Em um Sistema Autônomo (AS), o algoritmo de 
roteamento, que roda dentro do AS, é denominado 
protocolo de roteamento intra-AS e, ao conectarmos vários 
ASs entre si, um ou mais roteadores em um As terá a tarefa 
adicional de ficar responsável por transmitir pacotes a 
destinos externos ao AS. 
SISTEMA AUTÔNOMO
Este roteadores são 
denominados de 
roteadores de borda 
(gateway routers). 
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 28
• Um protocolo de roteamento intra-AS é usado para 
determinar como é executado o roteamento dentro de um 
sistema Autônomo (AS).
• Os protocolos de roteamento intra-AS são também 
conhecidos como protocolos de roteadores internos (IGP)
PROTOCOLOS DE ROTEAMENTO INTRA-AS
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 29
• protocolo de roteamento dinâmico que utiliza algoritmo de 
vetor de distância. Geralmente é utilizado em redes 
menores
PROTOCOLOS DE ROTEAMENTO INTRA-AS
RIP (ROUTING INFORMATION PROTOCOL)
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 30
• Protocolo de roteamento dinâmico que utiliza algoritmo de 
estado de enlace. Geralmente é utilizado na internet. É 
mais eficiente que o RIP.
PROTOCOLOS DE ROTEAMENTO INTRA-AS
OSPF (OPEN SHORTEST PATH FIRST)
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 31
• protocolo de roteamento dinâmico que utiliza algoritmo de 
estado de enlace. Geralmente é utilizado em redes de 
grande porte
PROTOCOLOS DE ROTEAMENTO INTRA-AS
IS-IS (INTERMEDIATE SYSTEM TO INTERMEDIATE
SYSTEM)
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 32
• Protocolo de roteamento dinâmico que utiliza algoritmo de 
estado de enlace. Foi desenvolvido pela Cisco
PROTOCOLOS DE ROTEAMENTO INTRA-AS
EIGRP (ENHANCED INTERIOR GATEWAY ROUTING
PROTOCOL) 
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 33
• O protocolo de roteamento inter-AS é responsável pela 
determinação dos caminhos entre origem e destino que 
abrangem vários ASs. Atualmente o protocolo utilizado na 
Internet é o BGP (Border Gateway Protocol). 
• O BGP é um protocolo de roteamento dinâmico que utiliza 
vetor à distância, para trocar informações de roteamento 
entre os sistemas autônomos. 
PROTOCOLO DE ROTEAMENTO INTER-AS
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 34
• Ao configurar os hosts de uma rede é necessário definir:
– Endereço IP
– Máscara de sub-rede e 
– Gateway
• Mas o que é um gateway?
• Podemos resumir dizendo que gateway é o endereço da 
porta do roteador.
GATEWAY
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 35
• A definição do endereço do gateway serve para que o 
protocolo arp possa preencher o campo MAC de destino, 
baseado no IP de destino.
• Para pacotes direcionados a outras redes o arp utiliza o 
MAC do gateway.
• Não confundir com o endereço do pacote que não é 
modificado.
• Um host pode ser configurado com mais de um gateway: 
um padrão (default) e outros para associar a outros 
roteadores ligados à rede
GATEWAY
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 36
• Em redes que utilizam endereços privados (10.*, 172.16. 
até 172.31 e 192.168.* os pacotes não são admitidos na 
internet.
• Neste caso é necessário que os endereços de origem dos 
pacotes sejam substituídos por endereços válidos.
• O protocolo NAT, habilitado no roteador, substitui o 
endereço de todos os pacotes de saída pelo seu próprio 
endereço da porta de saída.
NAT – NETWORK ADDRESS TRANSLATOR
Redes de ComputadoresRedes de Computadores
Aula 8 – Noções de Algoritmos e Protocolos de Roteamento - 37
Nesta aula você:
• Identificou o funcionamento do serviço de roteamento;
• Comparou os protocolos de roteamento estático e 
dinâmico;
• Aprendeu diferenciar os tipos de protocolos de roteamento 
dinâmico;
• Aprendeu ainterpretar como um pacote é transmitido, 
entre origem e destino, através das redes de 
computadores.
RESUMO DA AULA 8