Buscar

Aula11 - Camada de Rede Roteamento

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 71 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 71 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 71 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Camada de Rede: Roteamento
Prof. Me. Anderson Bessa da Costa
���1
Roteiro
• Introdução 
• Tabela de Roteamento	
• Roteamento Estático	
• Roteamento Dinâmico	
• IPv6
Roteamento
• É o processo de escolha entre vários caminhos possíveis 
de se enviar uma mensagem. O nó de processamento 
que faz essa escolha é chamado de Roteador;	
• O roteamento pode ser dividido em duas categorias:	
• roteamento direto	
• roteamento indireto: estático e dinâmico
Roteamento
• Tem que ser configurado em todas estações de rede quem é o seu roteador;	
• Ao receber um pacote, o roteador verifica se o pacote tem como destino 
uma estação das suas redes locais (redes que está ligado fisicamente), caso 
seja, ele o entrega diretamente para a estação de destino, caso contrário, ele 
repassa o pacote para um próximo roteador. A decisão para qual roteador o 
pacote deve ser passado é tomada com base na tabela de rotas.
Roteamento
• Processo de roteamento
Nível De Rede
• Roteamento:	
• escolha do melhor caminho entre 2 nós, passando pelos elementos de interconexão 
de redes (roteadores)	
• métodos: 
• roteamento estático ou rota fixa 
• mais simples	
• tabelas estáticas	
• roteamento dinâmico ou encaminhamento adaptivo 
• tabelas dinâmicas de acordo com a carga da rede = retardo sofrido em um 
determinado caminho	
!
• critérios para escolha do melhor caminho:	
• menor número de saltos (hop count)	
• menor distância em metros	
• menor retardo de transferência
Roteiro
• Introdução	
• Tabela de Roteamento 
• Roteamento Estático	
• Roteamento Dinâmico	
• IPv6
Tabela De Roteamento
• Funções	
• armazenar informações sobre possíveis destinos e 
como enviar datagramas aos mesmos	
• consultar para decidir como enviar o datagrama	
• as entradas da tabela fornecem informações sobre 
roteamento para redes físicas
Tabelas De Roteamento
Tabela De Roteamento
Tabela De Roteamento
Tabela De Roteamento
• Representação de Rotas	
• rede diretamente conectada	
• S: máscara da rede ou sub-rede	
• N: endereço da rede ou sub-rede	
• host individual:	
• S: 255.255.255.255	
• N: endereço de host	
• rota default:	
• S: 0.0.0.0	
• N: 0.0.0.0
Roteiro
• Introdução	
• Tabela de Roteamento	
• Roteamento Estático 
• Roteamento Dinâmico	
• IPv6
Roteamento Estático
Roteamento Estático Exercício
Máscara de 
Rede	
 Rede Rota
0.0.0.0 0.0.0.0 10.10.10.1Estações da Rede A
Estações da Rede B
Máscara de 
Rede	
 Rede Rota
255.255.255.0 10.10.10.0 20.20.20.1
0.0.0.0 0.0.0.0 20.20.20.2
Estações da Rede C
Máscara de 
Rede	
 Rede Rota
255.255.255.0 10.10.10.0 30.30.30.2
255.255.255.0 20.20.20.0 30.30.30.2
255.255.255.0 40.40.40.0 30.30.30.1
0.0.0.0 0.0.0.0 30.30.30.3
Estações da Rede D
Máscara de 
Rede	
 Rede Rota
0.0.0.0 0.0.0.0 40.40.40.1
Estações da Rede R1
Máscara de 
Rede	
 Rede Rota
0.0.0.0 0.0.0.0 20.20.20.2
Estações da Rede R2
Máscara de 
Rede	
 Rede Rota
255.255.255.0 10.10.10.0 20.20.20.1
255.255.255.0 40.40.40.0 30.30.30.1
0.0.0.0 0.0.0.0 30.30.30.3
Estações da Rede R3
Máscara de 
Rede	
 Rede Rota
255.255.255.0 10.10.10.0 30.30.30.2
255.255.255.0 20.20.20.0 30.30.30.2
0.0.0.0 0.0.0.0 30.30.30.3
Estações da Rede R4
Máscara de 
Rede	
 Rede Rota
255.255.255.0 10.10.10.0 30.30.30.2
255.255.255.0 20.20.20.0 30.30.30.2
255.255.255.0 40.40.40.0 30.30.30.1
0.0.0.0 0.0.0.0 200.Y.X.Z
Definindo Rotas Para As 
Estações Das Redes A, B, C & D
• As definições das rotas abaixo seguem a sintaxe de 
comandos de rotas do sistema operacional Linux	
!
• Definindo as rotas para as estações de rede A	
• route add -net 0.0.0.0 net mask 0.0.0.0 gw 10.10.10.1	
• Definindo as rotas paras as estações da rede B	
• route add -net 10.10.10.0 net mask 255.255.255.0 
gw 20.20.20.1	
• route add -net 0.0.0.0 netmask 0.0.0.0 gw 20.20.20.2
Rotas Para As Estações Da Rede 
A - Outra Solução
• Substituindo a rota:	
• route add -net 0.0.0.0 netmask 0.0.0.0 gw 10.10.10.1	
• Por:	
• route add -net 20.20.20.0 netmask 255.255.255.0 gw 10.10.10.1	
• route add -net 30.30.30.0 netmask 255.255.255.0 gw 10.10.10.1	
• route add -net 40.40.40.0 netmask 255.255.255.0 gw 10.10.10.1	
• Qual é o problema com as rotas acima???	
• Acesso a internet?	
• Solução:	
• route add -net 200.1.1.0 netmask 255.255.255.0 gw 10.10.10.1	
• route add -net 200.2.1.0 netmask 255.255.255.0 gw 10.10.10.1	
• route add -net … (adicionar uma rota para todas as redes da Internet)
Definindo As Demais Rotas
Definindo As Rotas Para Os 
Roteadores Linux
Definindo As Rotas Para Os 
Roteadores Linux
Testando A Comunicação Entre 
As Máquinas Da Rede
• ping 10.10.10.2	
• ping 20.20.20.3	
• ping 30.30.30.3	
• ping 40.40.40.2	
• ping 200.200.1.x	
• traceroute 10.10.10.2	
• traceroute 20.20.20.3	
• traceroute 40.40.40.2
Encaminhamento De Um 
Pacote Ip
Roteiro
• Introdução	
• Tabela de Roteamento	
• Roteamento Estático	
• Roteamento Dinâmico 
• IPv6
Roteamento Dinâmico
• Encaminhamento (forwarding) versus roteamento	
• encaminhamento: selecionar uma porta de saída com baseio 
endereço destino e tabela de roteamento	
• roteamento: processo pelo qual a tabela de roteamento é 
montada	
• Para isso a rede deve ser vista como um grafo
Roteamento
• Problema:	
• encontrar caminhos de menor custo entre dois nós do grafo	
• Fatores Relevantes:	
• estáticos: topologia de rede	
• dinâmicos: carga em cada canal e cada nó
Estrutura Da Internet
• A Internet é estruturada na forma de sistemas 
autônomos:
Sistema Autônomo (Autonomous 
System - As)
• Uma AS é uma rede que divulga seus endereços para outras redes da Internet	
• Propriedades do AS:	
• Possui os seus próprios IP’s	
• Seus endereços são independentes do provedor de acesso	
• Pode conectar-se a vários provedores simultaneamente
Exemplo De As
• Bloco de endereços do AS:	
• 200.17.0.0/16 (255.255.0.0)	
• 200.17.0.0 ao 200.17.255.255
Roteiro
• Introdução	
• Tabela de Roteamento	
• Roteamento Estático	
• Roteamento Dinâmico 
• IPv6
Propagação De Rota
• Autonomous System (AS)	
• corresponde a um domínio administrativo	
• tem controle absoluto sobre caminhos internos	
• exemplos: rede de universidade, empresa, backbone	
• atribui a cada AS um número de 16 bits	
• Hierarquia de propagação de rota em dois níveis	
• protocolo de gateway interior (Interior Gateway Protocol - IGP)	
• roteamento no interior do AS. Cada AS seleciona o seu	
• protocolo de gateway exterior (Exterior Gateway Protocol - EGP)	
• roteamento entre ASs é definida por um protocolo padrão 
comum a toda internet
Roteadores Na Internet
• Os roteadores da Internet são de dois tipos:	
• Exterior Gateways	
• troca informações com roteadores pertencentes a outros AS	
• equipamento muito caro, com alta capacidade de memória	
• Interior Gateways	
• troca informações apenas no interior do seu AS	
• roteador comum
Egp E Igp
Protocolos De Gateway Interior 
Populares
• RIP: Route Information Protocol	
• desenvolvido para XNS (rede da Xerox)	
• distribuído com o Unix	
• algoritmo por vetor de distância (distance vector)	
• baseado na contagem de roteadores (hop-count)	
• OSPF: Open Shortest Path First	
• padrão recente da Internet	
• usa algoritmo de estado de enlace (link-state)	
• admite balanceamento de carga	
• aceita autenticação de roteadores	
• utilizado em redes grandes e muito grandes (mais de 50 redes)	
• atualiza rotas de maneiramais eficiente que o RIP
Vetor De Distância (Distance 
Vector) - Rip
• Cada nó mantém um conjunto de tuplas	
• (destino, custo, proxSalto)	
• Vizinhos conectados diretamente trocam atualizações	
• periodicamente (na ordem de vários segundos)	
• sempre que a tabela mudar (atualização disparada - triggered update)	
• Cada atualização é uma lista de pares:	
• (Destino, Custo)	
• Atualiza a tabela local se receber uma rota “melhor"	
• menor custo	
• atualização vindo do nó já escolhido como próximo salto	
• Atualiza rotas existentes; exclui se esgotar o tempo
Exemplo De Aplicação
Operação Sob Falhas
• Exemplo 1	
• F detecta que enlace G falhou	
• F define distância para G como infinito e envia atualizações 
para A	
• A define distância para G como infinito, pois atualmente usa 
F para chegar a G	
• A recebe atualização periódica de C com caminho de 2 
saltos para G	
• A define distância para G como 3 e envia atualização para F	
• F decide que pode alcançar G em 4 saltos via A
Loops De Roteamento
• Exemplo 2	
• enlace de A para E falha	
• A anuncia distância de infinito para E	
• B e C anunciam uma distância de 2 para E	
• B decide que pode alcançar E via C em 3 saltos; e avisa 
A	
• A decide que pode alcançar E via B em 4 saltos; e avisa 
C	
• C decide que pode alcançar E em 5 saltos …	
• LOOP de roteamento
Heurísticas De Quebra De Loop
• Definir infinito como 16	
• problema se a rede for grande e realmente 
precisar de mais de 16 saltos	
• Horizonte Dividido (split horizon)	
• não envia atualização para vizinhos dos quais ele 
aprendeu a tal rota	
• ex.: em B, a rota (E, 2, A). B não inclui rota E em 
atualização para A
Ospf
• OSPF: Open Shortest Path First	
• protocolo do tipo IGP	
• específico para redes IP	
• RIP funciona para outros protocolos, por exemplo, IPX	
• ao contrário do que o nome sugere, o algoritmo trabalha com o 
melhor caminho ao invés do primeiro	
• características do OSPF	
• leva em conta o campo TOS (Type Of Service) do IP	
• permite balanceamento de carga	
• permite a divisão da rede em áreas	
• os roteadores trocam mensagens autenticadas	
• flexibilidade na criação de rotas (máscara de subrede viável)
• Estratégia	
• envia para todos os nós (não apenas vizinhos) 
informações sobre enlaces conectados diretamente 
(não a tabela de roteamento inteira)	
• Link State Packet (LSP)	
• identificador do nó que criou o pacote LSP	
• custo do enlace para cada vizinho conectado 
diretamente	
• número de sequência (SEQNO)	
• tempo de vida (TTL) para este pacote
Estado Do Enlace (Link State) 
Ospf
Estado Do Enlace
• Inundação confiável (reliable flooding)	
• armazena LSP mais recente de cada nó	
• encaminha LSP a todos os nós, menos aquele que enviou	
• envio aos vizinhos confiável: confirmações e 
retransmissões	
• gera novo LSP periodicamente	
• incrementa SEQNO	
• inicia SEQNO em 0 quando reinicializar	
• decrementa TTL de cada LSP armazenado	
• descarta quando TTL = 0
Cálculo De Rota
• Algoritmo do caminho mínimo de Dijkstra	
• Considere que	
• N indica conjunto de nós no gráfico	
• I(i, j) indica custo não negativo (peso) para a borda (i, j)	
• s indica esse nó	
• m indica o conjunto de nós incorporados até aqui	
• os demais, com distâncias não menores que os anteriores (N-M)	
• O(n) indica custo do caminho de s para o nó n	
!
• A cada passo, identifique os vizinhos de nós em M que não estão em M	
• Para esses nós, determine aquele de menor distância até a raiz	
• acrescente esse nó a M e repita até que N = M
Cálculo De Rota
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Estado Do Enlace
Métricas Usadas Para O 
Roteamento
• Protocolos de roteamento simples (RIP)	
• contagem de links/roteadores no caminho	
• Métrica ARPANET original	
• mede número de pacotes enfileirados em cada enlace	
• não leva em conta latência ou largura de banda	
• Nova métrica ARPANET	
• marca cada pacote que chega com sua hora de chegada (AT)	
• registra hora de saíra (DT)	
• quando chega ACK em nível de enlace, calcula	
• Retardo = (DT - AT) + Transmissão + Latência	
• se timeout, reinicia DT para hora de saída, para retransmissão	
• custo do enlace = retardo médio por algum período de tempo	
• Ajuste fino	
• intervalo dinâmico limitado	
• substitui Retardo por utilização do enlace
Egp: Exterior Gateway Protocol
• Visão Geral	
• criado para a Internet estruturada em árvore	
• preocupa-se com alcance, e não rotas mínimas	
• Mensagens do protocolo	
• aquisição de vizinhos: um roteador solicita que outro seja 
seu par; pares trocam informações de alcance	
• alcance do vizinho: um roteador testa periodicamente se 
outro ainda pode ser alcançado; troca mensagens HELLO/
ACK; usa uma regra de k-dentre-n	
• atualizações de roteamento: pares trocam periodicamente 
suas tabelas de roteamento (vetor-distância)
Egp
Bgp-4: Border Gateway Protocol
• Substitui o EGP	
• só tratava estruturas em árvore (Internet antiga)	
• Protocolo para controle de alcance (reachability) entre AS	
• focado em determinar pelo menos um caminho (pode não 
ser ótimo)
Bgp-4: Border Gateway Protocol
• Cada AS tem:	
• um ou mais roteadores de borda	
• um porta-voz BGP (speaker BGP) que anuncia:	
• redes locais internas ao AS	
• outras redes alcançáveis (somente AS de trânsito)	
• oferece informações de caminhos conhecidos	
• porta-voz pode também revogar caminhos previamente anunciados
Bgp
Bgp-4: Border Gateway Protocol
• Mensagens usadas pelos speakers:	
• aquisição de vizinhos: roteadores se reconhecem e 
trocam informações	
• alcance dos vizinhos: roteador testa se pares são 
alcançáveis (HELLO/ACK, k-em-n respostas)	
• atualizações de rotas: pares periodicamente 
trocam tabelas (a la distance-vector)	
• informação sobre o caminho também é trocada 
(evita loops)
Bgp-4: Border Gateway Protocol
• Diferencia vários tipos de AS	
• AS stub: tem uma única conexão com outro AS	
• transporta apenas tráfego local	
• AS multihomed: tem conexões com mais de um SA	
• recusa-se a transportar tráfego de trânsito	
• AS de trânsito (transit AS): tem conexões com vários AS	
• transporta tráfego de trânsito e local
Exemplo De Bgp
• Speaker para AS2 anuncie alcance para P e Q	
• redes 128.96, 192.4.153, 192.4.32 e 192.4.3, podem ser alcançadas 
diretamente para AS2	
!
!
!
!
!
!
!
• Speaker do backbone anuncie os caminhos	
• redes 128.96, 192.4.153, 192.4.32, e 192.4.3 pode ser alcançada ao longo 
do caminho (AS1, AS2)	
• Speaker pode cancelar caminhos previamente anunciados
Roteiro
• Introdução	
• Tabela de Roteamento	
• Roteamento Estático	
• Roteamento Dinâmico	
• IPv6

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes