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 Algoritmose 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 enlace congestionado, 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 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37