Upload
lehuong
View
226
Download
0
Embed Size (px)
Citation preview
4: Camada de Rede 4a-1
Capítulo 4: Camada de Rede
� 4. 1 Introdução� 4.2 Redes de circuito Virtual e redes datagrama� 4.3 O que tem dentro de um roteador;� 4.4 IP: Protocolo Internet(IP)
� Formato do Datagrama � Endereçamento IPv4 a� ICMP� IPv6
� 4.5 Algoritmos de Roteamento na Internet
4: Camada de Rede 4a-2
Camada de redeDinâmica:� Transporta segmento do SF
transmissor até o SF receptor; � No lado do transmissor encapsula
segmentos dentro de datagramas;� No lado do receptor, entrega
segmentos para camada detransporte;
Observações:� O protocolo da camada de rede é
implementada em todos os SF eroteadores;
� Roteador examina campos docabeçalho de todo o datagrama IP;
applicationtransportnetworkdata linkphysical
applicationtransportnetworkdata linkphysical
networkdata linkphysical network
data linkphysical
networkdata linkphysical
networkdata linkphysical
networkdata linkphysical
networkdata linkphysical
networkdata linkphysical
networkdata linkphysical
networkdata linkphysical
networkdata linkphysicalnetwork
data linkphysical
4: Camada de Rede 4a-3
As duas Funções principais da camada de rede
� Comutação: mover pacotes dentro do roteador da entrada àsaída apropriada;
� Com base em:Tabela de comutação e datagrama;
� Roteamento: rota seguida por pacotes da origem ao destino.Algoritmos de roteamento;
� Em algumas arquiteturas...� estabelecimento da chamada: algumas arquiteturas de rede
requerem determinar o caminho antes de enviar os dados.
4: Camada de Rede 4a-4
1
23
0111
Valor no cabeçalhodo pacote que chega
routing algorithm
local forwarding tableheader value output link
0100010101111001
3221
Interação entre roteamento e comutação
4: Camada de Rede 4a-5
Serviços que poderiam seroferecido pela camada de rede
Ordem da transmissão?Integridade?Transmissão com taxa mínima?Entrega?Entrega em tempo máximo?Privacidade?
4: Camada de Rede 4a-6
Modelo de serviço da redeP: Qual é o modelo de serviço para o “canal” que
transporta pacotes do remetente ao receptor?
Serviço individual pordatagramas:
� Entrega garantida;� Entrega garantida com
limite de tempo( emmenos que 40 msec deatraso).
Serviço para um fluxo dedatagramas:
� Entrega datagrama na-ordem de geração;
� Garantia mínima debanda para o fluxo;
� Restrição na variaçãodo atraso.
4: Camada de Rede 4a-7
Instanciação: serviço já visto na CR
Arquiteturade Rede
Internet
ATM
ATM
ATM
Modelo deserviço
melhoresforçoCBR
VBR
ABR
Banda
nenhuma
taxaconstantetaxagarantidamínimagarantida
Perdas
não
sim
sim
não
Ordem
não
sim
sim
sim
Tempo
não
sim
sim
não
Informa s/congestion.?
não (inferidovia perdas)semcongestion.semcongestion.sim
Garantias ?
4: Camada de Rede 4a-8
Capítulo 4: Camada de Rede
� 4. 1 Introdução� 4.2 Redes de circuito Virtual e redes datagrama� 4.3 O que tem dentro de um roteador;� 4.4 IP: Protocolo Internet(IP)
� Formato do Datagrama � Endereçamento IPv4 a� ICMP� IPv6
4: Camada de Rede 4a-9
Camada de Rede: Serviço orientadoe não-orientado a conexão� Similar ao serviço da camada de
transporte, mas:� serviço: sistema final-a-sistema final� sem escolha: a rede fornece um ou outro� implementação: no interior da rede
� Rede de datagrama fornece serviço não-orientado a conexão;
� Rede de Circuito virtuais fornece serviçoorientado a conexão;
4: Camada de Rede 4a-10
Circuitos virtuais
� estabelecimento de cada chamada antes do envio dos dados� cada pacote tem ident. de CV (e não endereços origem/dest)� cada roteador no caminho da-origem-ao-destino mantém “estado”
para cada conexão que o atravessa � conexão da camada de transporte só envolve os 2 sistemas terminais
� recursos de enlace, roteador (banda, buffers) podem ser alocadosao CV
� para permitir desempenho como de um circuito
“caminho da-origem-ao-destino se comporta como umcircuito telefônico em termos de”
� desempenho� ações da rede ao longo do caminho
4: Camada de Rede 4a-11
Implementação de CV
� Um CV consiste de:1. Caminho da fonte para destino;2. Número CV, um número para cada enlace ao longo
do caminho;3. Entradas nas tabelas de comutação dos roteadores
ao longo do caminho.� Pacote que pertence a um CV leva o número
CV (ao invés do endereço destino)� Número CV pode mudar a cada enlace.
� Novo número CV obtido da tabela de comutação
4: Camada de Rede 4a-12
Tabela Comutação12 22 32
1 23
Número CV
Númerointerface
Interface entrada # do CV entrada Interface saída # CV de saida
1 12 3 222 63 1 18 3 7 2 171 97 3 87… … … …
Tabela de comutação doroteador:
Roteadores mantém informação sobre estado da conexão
4: Camada de Rede 4a-13
Circuitos virtuais: protocolos de sinalização� usados para estabelecer, manter, remover CV� usados em ATM, frame-relay, X.25� não usados na Internet de hoje
aplicaçãotransporte
redeenlacefísica
aplicaçãotransporte
redeenlacefísica
1. inicia chamada 2. chegada de chamada3. chamada aceita4. conexão completa
5. começa fluxo de dados 6. dados recebidos
4: Camada de Rede 4a-14
Rede de datagramas: o modelo da Internet � não requer estabelecimento de chamada na camada de rede� roteadores: não guardam estado sobre conexões fim a fim
� não existe o conceito de “conexão” na camada de rede� pacotes são roteados usando endereços de destino
� pacotes entre o mesmo par origem-destino podem seguircaminhos diferentes
aplicaçãotransporte
redeenlacefísica
aplicaçãotransporte
redeenlacefísica
1. envia dados 2. recebe dados
4: Camada de Rede 4a-15
Tabela Comutação
Destination Address Range Link Interface
11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111
11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111
otherwise 3
4 bilhões de possíveis entradas
4: Camada de Rede 4a-16
Casando o “prefixo mais longo”
Pref ix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3
DA: 11001000 00010111 00011000 10101010
Exemplos
DA: 11001000 00010111 00010110 10100001
Qual interface?
DA: 11101000 00010111 00011000 10101010
4: Camada de Rede 4a-17
Rede de datagramas ou CVs: por quê?Internet� troca de dados entre
computadores� serviço “elástico”, sem reqs.
temporais estritos� sistemas terminais “inteligentes”
(computadores)� podem se adaptar, exercer
controle, recuperar de erros� núcleo da rede simples,
complexidade na “borda”� muitos tipos de enlaces
� características diferentes� serviço uniforme difícil
ATM� evoluiu da telefonia� conversação humana:
� temporização estrita,requisitos deconfiabilidade
� requer serviçogarantido
� sistemas terminais “burros”� telefones� complexidade dentro da
rede
4: Camada de Rede 4a-18
Capítulo 4: Camada de Rede
� 4. 1 Introdução� 4.2 Redes de circuito Virtual e redes datagrama� 4.3 O que tem dentro de um roteador;� 4.4 IP: Protocolo Internet(IP)
� Formato do Datagrama � Endereçamento IPv4 a� ICMP� IPv6
� 4.5 Algoritmos de Roteamento na Internet
4: Camada de Rede 4a-19
Arquitetura de um Roteador
4: Camada de Rede 4a-20
Funções da Porta de Entrada
Comutação descentralizada: � dado o dest do datagrama, procura porta
de saída usando tab. de rotas na memóriada porta de entrada
� meta: completar processamento da portade entrada na ‘velocidade da linha’
� filas: se datagramas chegam mais rápidoque taxa de re-envio para matriz decomutação
Camada f’ísica:recepção de bits
Camada de enlace:p.ex., Ethernetveja capítulo 5
4: Camada de Rede 4a-21
Filas na Porta de Entrada� Se matriz de comutação for mais lenta do que a soma
das portas de entrada juntas -> pode haver filas nasportas de entrada
� Bloqueio cabeça-de-fila (Head-of-the-Line - HOL): datagrama na cabeça da fila impede outros na mesmafila de avançarem
� retardo de enfileiramento e perdas devido aotransbordo do buffer de entrada!
4: Camada de Rede 4a-22
Três tipos de matriz de comutação
4: Camada de Rede 4a-23
Comutação via MemóriaRoteadores da primeira geração:� pacote copiado pelo processador (único) do sistema� velocidade limitada pela largura de banda damemória (2 travessias do barramento por datagrama)
Porta de Entrada
Porta deSaída
Memória
Barramento do Sistema
Roteadores modernos:� processador da porta de entrada consulta tabela,copia para a memória
� Cisco Catalyst 8500
4: Camada de Rede 4a-24
Comutação via Barramento
� Move datagrama da memória da portade entrada à memória da porta de saídavia um barramento compartilhado
� contenção pelo barramento: taxa decomutação limitada pela largura debanda do barramento
� Barramento de 1 Gbps, Cisco 1900:velocidade suficiente para roteadoresde acesso e corporativos (mas nãoregionais ou de backbone)
4: Camada de Rede 4a-25
Comutação via uma Rede deInterconexão� supera limitações de banda dos barramentos� 2n Barramentos que conectam n portas de entrada
e saída� O comutador fecha o cruzamento para transferir
de uma porta de entrada para a porta de saída; � Cisco 12000: comuta N Gbps pela rede de
interconexão.
4: Camada de Rede 4a-26
Porta de Saída
� Buffers necessários quando datagramas chegam damatriz de comutação mais rapidamente que a taxa detransmissão
� Disciplina de escalonamento escolhe um dosdatagramas enfileirados para transmissão
4: Camada de Rede 4a-27
Filas na Porta de Saída
� usa buffers quando taxa de chegada através docomutador excede taxa de transmissão de saída
� enfileiramento (retardo), e perdas devidas aotransbordo do buffer da porta de saída!
4: Camada de Rede 4a-28
Capítulo 4: Camada de Rede
� 4. 1 Introdução� 4.2 Redes de circuito Virtual e redes datagrama� 4.3 O que tem dentro de um roteador;� 4.4 IP: Protocolo Internet(IP)
� Formato do Datagrama � Endereçamento IPv4 a� ICMP� IPv6
4: Camada de Rede 4a-29
A Camada de Rede na Internet
Tabela de com.
Funções da camada de rede em estações, roteadores:
Protocolos de rot.•seleção de rotas•RIP, OSPF, BGP
protocolo IP •convenções de endereços•formato do datagrama•convenções de manuseio do pct
protocolo ICMP•relata erros•“sinalização” de roteadores
Camada de transporte: TCP, UDP
Camada de enlace
Camada física
Camadade rede
4: Camada de Rede 4a-30
Formato do datagrama IP
ver comprimento
32 bits
dados (comprimento variável,
tipicamente um segmento TCP ou UDP)
ident. 16-bitschecksum Internet
sobre-vida TTL
endereço IP de origem 32 bits
número da versão do protocolo IP comprimento do
cabeçalho (bytes)
número máximode enlaces restantes
(decrementado a cada roteador)
parafragmentação/remontagem
comprimento total do datagrama(bytes)
protocolo da camadasuperior ao qual
entregar os dados
comp.cab
tipo deserviço
“tipo” dos dados (DS) bitsinício do
fragmentocamadasuperior
endereço IP de destino 32 bits
Opções (se tiver) p.ex. registrar rotaseguida, especificarlista de roteadoresa visitar.
Qual o overheadcom TCP?
� 20 bytes de TCP� 20 bytes de IP� = 40 bytes +
overhead aplic.
4: Camada de Rede 4a-31
IP: Fragmentação & RemontagemID=x
início=0
bit_frag=0
compr=4000
ID=x
início=0
bit_frag=1
compr=1500
ID=x
início=1480
bit_frag=1
compr=1500
ID=x
início=2960
bit_frag=0
compr=1040
um datagrama grande viravários datagramas menores
Exemplo� Datagrama com
4000 bytes� MTU = 1500 bytes
4: Camada de Rede 4a-32
Capítulo 4: Camada de Rede
� 4. 1 Introdução� 4.2 Redes de circuito Virtual e redes datagrama� 4.3 O que tem dentro de um roteador;� 4.4 IP: Protocolo Internet(IP)
� Formato do Datagrama � Endereçamento IPv4� ICMP� IPv6
4: Camada de Rede 4a-33
Endereçamento IP: introdução� endereço IP: ident. de
32-bits para interface de estação, roteador
� interface: conexãoentre estação,roteador e enlacefísico
� roteador típico temmúltiplas interfaces
� estação pode termúltiplas interfaces
� endereço IP associado àinterface, não à estaçãoou roteador
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
223.1.1.1 = 11011111 00000001 00000001 00000001
223 1 11
4: Camada de Rede 4a-34
Endereçamento IP� endereço IP:
� parte de rede (bits demais alta ordem)
� parte de estação (bits demais baixa ordem)
� O que é uma rede IP? (daperspectiva do endereço IP)
� interfaces de dispositivoscom a mesma parte derede nos seus endereçosIP
� podem alcançar um aooutro sem passar por umroteador
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
Esta rede consiste de 3 redes IP(para endereços IP começando com223, os primeiros 24 bits são aparte de rede)
LAN
4: Camada de Rede 4a-35
Endereçamento IPComo achar as redes?� Desacoplar cada
interface do seuroteador, ou estação;
� criar “ilhas” de redesisoladas;
223.1.1.1
223.1.1.3
223.1.1.4
223.1.2.2223.1.2.1
223.1.2.6
223.1.3.2223.1.3.1
223.1.3.27
223.1.7.0
223.1.7.1223.1.8.0223.1.8.1
223.1.9.1
223.1.9.2
Sistema interligadoconsistindo de
??? redes
4: Camada de Rede 4a-36
Endereços IP
0rede estação
10 rede estação
110 rede estação
A
B
C
classe1.0.0.0 to127.255.255.255128.0.0.0 to191.255.255.255192.0.0.0 to223.255.255.255
32 bits
dada a noção de “rede”, vamos reexaminar endereços IP:endereçamento “baseado em classes”:
4: Camada de Rede 4a-37
parte deestação
Endereçamento IP: CIDR� Endereçamento baseado em classes:
� uso ineficiente e esgotamento do espaço de endereços� p.ex., rede da classe B aloca endereços para 65K estações,
mesmo se houver apenas 2K estações nessa rede
� CIDR: Classless InterDomain Routing� parte de rede do endereço de comprimento arbitrário� formato de endereço: a.b.c.d/x, onde x é no. de bits na
parte de rede do endereço
11001000 00010111 00010000 00000000
partede rede
200.23.16.0/23
4: Camada de Rede 4a-38
IP: Fragmentação & Remontagem� cada enlace de rede tem MTU
(max.transmission unit) - maiortamanho possível de quadroneste enlace.
� tipos diferentes de enlacetêm MTUs diferentes
� datagrama IP muito grandedividido (“fragmentado”)dentro da rede
� um datagrama vira váriosdatagramas
� “remontado” apenas nodestino final
� bits do cabeçalho IPusados para identificar,ordenar fragmentosrelacionados
fragmentação: entrada: um datagrama
grandesaída: 3 datagramas
menores
remontagem
4: Camada de Rede 4a-39
Endereços IP: como conseguir um?
� DHCP: Dynamic Host Configuration Protocol: obtémendereço dinamicamente: “plug-and-play”
� estação difunde mensagem “DHCP discover”� servidor DHCP responde com “DHCP offer” � estação solicita endereço IP: “DHCP request”� servidor DHCP envia endereço: “DHCP ack”
4: Camada de Rede 4a-40
DHCP: cenário cliente-servidor
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
BE
servidor DHCP
Cliente DHCP que chega necessita de um endereço nesta rede
4: Camada de Rede 4a-41
DHCP: implementa DORAServidor DHCP : 223.1.2.5 Cliente que chega
tempo
DHCP discover
src : 0.0.0.0, 68 dest.: 255.255.255.255,67yiaddr: 0.0.0.0transaction ID: 654
DHCP offer
src: 223.1.2.5, 67 dest: 255.255.255.255, 68yiaddrr: 223.1.2.4transaction ID: 654Lifetime: 3600 secs
DHCP request
src: 0.0.0.0, 68 dest:: 255.255.255.255, 67yiaddrr: 223.1.2.4transaction ID: 655Lifetime: 3600 secs
DHCP ACK
src: 223.1.2.5, 67 dest: 255.255.255.255, 68yiaddrr: 223.1.2.4transaction ID: 655Lifetime: 3600 secs
4: Camada de Rede 4a-42
Servidores DHCP: Porque elespodem tornar a sua rede inviável� Pesquise sobre esse tema e traga uma
explicação de 1 página, manuscrita. � Aqueles que tiverem a sua resposta aceita
receberão um ponto na última prova.
4: Camada de Rede 4a-43
Endereços IP: como conseguir um?
Rede (parte de rede):� conseguir alocação a partir do espaço de
endereços do seu provedor IPBloco do 11001000 00010111 00010000 00000000 200.23.16.0/20 provedorOrganização 0 11001000 00010111 00010000 00000000 200.23.16.0/23
Organização 1 11001000 00010111 00010010 00000000 200.23.18.0/23
Organização 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. ….
Organização 7 11001000 00010111 00011110 00000000 200.23.30.0/23
4: Camada de Rede 4a-44
Endereçamento IP: a última palavra...
P: Como um provedor IP consegue um bloco deendereços?
R: ICANN: Internet Corporation for Assigned Names and Numbers
� aloca endereços� gerencia DNS� aloca nomes de domínio, resolve disputas (no Brasil, estas funções foram delegadas ao
Registro nacional, e comandado pelo ComitêGestor Internet BR)
4: Camada de Rede 4a-45
Enviando um datagrama da origem ao destino
datagrama IP:
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
BE
camposmisc
end. IPorigem
end. IP dest dados
� datagrama permaneceinalterado, enquanto passada origem ao destino
� campos de endereços deinteresse aqui
rede dest. próx. rot. Nenlaces
223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2
tabela de rotas em A
4: Camada de Rede 4a-46
Enviando um datagrama da origem ao destino
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
BE
Supondo um datagrama IPoriginado em A, eendereçado a B:
� procura endereço de rede de B� descobre que B é da mesma
rede que A� camada de enlace remeterá
datagrama diretamente para Bnum quadro da camada deenlace
� B e A estão diretamenteligados
rede dest. próx. rot. Nenlaces
223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2
camposmisc. 223.1.1.1 223.1.1.3dados
4: Camada de Rede 4a-47
Enviando um datagrama da origem ao destino
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
BE
rede dest. próx. rot. Nenlaces
223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2
OrigemA, destino E:� procura endereço de rede de E� É em uma rede diferente
� A, E não ligados diretamente� tabela de rotas: próximo
roteador na rota para E é223.1.1.4
� camada de enlace enviadatagrama ao roteador 223.1.1.4num quadro da camada de enlace
� datagrama chega a 223.1.1.4 � continua…
camposdiv. 223.1.1.1 223.1.2.2 dados
4: Camada de Rede 4a-48
Enviando um datagrama da origem ao destino
223.1.1.1
223.1.1.2
223.1.1.3
223.1.1.4 223.1.2.9
223.1.2.2
223.1.2.1
223.1.3.2223.1.3.1
223.1.3.27
A
BE
Chegando a 223.1.1.4,destinado a 223.1.2.2
� procura endereço de rede de E� E fica na mesma rede que a
interface 223.1.2.9 do roteador� roteador, E estão
diretamente ligados� camada de enlace envia
datagrama p/ 223.1.2.2 dentrode quadro de camada de enlacevia interface 223.1.2.9
� datagrama chega a 223.1.2.2!!! (oba!)
camposdiv. 223.1.1.1 223.1.2.2 dados dest. rot. Nenl. interface
223.1.1 - 1 223.1.1.4 223.1.2 - 1 223.1.2.9
223.1.3 - 1 223.1.3.27
rede próx.
4: Camada de Rede 4a-49
Qual o tamanho da Internet?
� Endereçáveis: 4.294.967.296,00� Com a divisão por classe:
� A: 2.113.928.964,00� B: 1.073.709.056,00� C: 534.773.760,00
4: Camada de Rede 4a-50
Quantos estão de fato ativos
4: Camada de Rede 4a-51
NAT: Network Address Translation
10.0.0.1
10.0.0.2
10.0.0.3
10.0.0.4
138.76.29.7
Rede local(e.g., home network)
10.0.0/24
Restante darede
Datagramas com origem oudestino nesta rede tem endereço10.0.0/24 para fonte, e dedestino o usual
Todos os datagramas saindo da redelocal tem o mesmo endereço NATIP: 138.76.29.7, diferentes númerosde portas fontes
4: Camada de Rede 4a-52
NAT: Network Address Translation
� Motivação: rede local usa apenas um endereço IP:� Não há necessidade de alocar faixas de endereços de
um ISP apenas um endereço IP é usado para todos os
dispositivos� Permite mudar o endereço dos dispositivos internos
sem necessitar notificar o mundo externo;� Permite a mudança de ISPs sem necessitar mudar os
endereços dos dispositivos internos da rede local� Dispositivos internos a rede, não são visíveis nem
endereçaveis pelo mundo externo (melhorasegurança);
4: Camada de Rede 4a-53
NAT: Network Address TranslationImplementação: roteador NAT deve;
� Datagramas que saem: trocar (endereço IP fonte,porta #) de cada datagrama de saída para (endereçoNAT IP, nova porta #). . . clientes/servidores remotos irão responder
usando (endereço NAT IP, nova porta #) comoendereço destino.
� guardar (na tabela de tradução de endereços NAT):os pares de tradução de endereços (endereço IPfonte, porta #) para (endereços NAT IP, nova porta#)
� Datagramas que chegam: trocar (endereço NAT IP,nova porta #) no campo de destino de cada datagramaque chega com o correspondente (endereço IP fonte,porta #) armazenado na tabela NAT
4: Camada de Rede 4a-54
NAT: Network Address Translation
10.0.0.1
10.0.0.2
10.0.0.3
S: 10.0.0.1, 3345D: 128.119.40.186, 80
110.0.0.4
138.76.29.7
1: host 10.0.0.1 envia datagrama para 128.119.40.186, 80
Tabela de tradução NAT WAN addr LAN addr
138.76.29.7, 5001 10.0.0.1, 3345…… ……
S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4
S: 138.76.29.7, 5001D: 128.119.40.186, 802
2: roteador NAT muda o endereço de origem10.0.0.1, 3345 de10.0.0.1, 3345 para138.76.29.7, 5001,e atualiza a tabela
S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3
3: resposta chega no endereço de destino: 138.76.29.7, 5001
4: roteador NAT muda o endereço de destino de 138.76.29.7, 5001 para 10.0.0.1, 3345
4: Camada de Rede 4a-55
NAT: Network Address Translation
� Campo de porta de 16-bit : � 60,000 conexões simultâneas com um único
endereço de rede;� NAT é controverso:
� Roteadores devem fazer processamentos até nomáximo a camada 3;
� Viola o “conceito fim-a-fim”• A possibilidade de suporte a NAT deve ser levado em
consideração pelos desenvolvedores de aplicações;� O problema de diminuição do número de
endereços deveria ser tratada por IPv6;
4: Camada de Rede 4a-56
Passando pelo NAT � cliente quer se conectar ao
servidor que tem endereço10.0.0.1
� O endereço doservidor(10.0.0.1) é válido naLAN (cliente Não pode usarcomo endereço de destino)
� Somente o endereço NATtedé visível: 138.76.29.7
� Solução 1: configurarestaticamente o NAT pararepassar requisições deconexão de uma dada portapara o servidor
� e.g., (123.76.29.7, port 2500)sempre repassa para 10.0.0.1porta 25000
10.0.0.1
10.0.0.4
NAT router
138.76.29.7
Cliente ?
4: Camada de Rede 4a-57
Passando pelo NAT � solução 2: Protocolo Universal
Plug and Play (UPnP) InternetGateway Device (IGD). PermiteSF NATted: Encontrar um endereço IP
público (138.76.29.7) Adcionar/remover
mapeamento de porta (comlease times)
i.e., automatiza a soluçãoestática de mapeamento deporta
10.0.0.1
10.0.0.4
NAT router
138.76.29.7
IGD
4: Camada de Rede 4a-58
Passando pelo NAT� solução 3: relaying (usado pelo Skype)
� Cliente NATed estabelece uma conexão com o relay� Cliente externo conecta-se com o relay� Relay conecta pacotes entre as conexões
138.76.29.7Cliente
10.0.0.1
NAT router
1. conexão parao relay iniciadapelo SF NATted
2. conexão parao relay iniciadapelo cliente
3. relaying estabelecido
4: Camada de Rede 4a-59
Capítulo 4: Camada de Rede
� 4. 1 Introdução� 4.2 Redes de circuito Virtual e redes datagrama� 4.3 O que tem dentro de um roteador;� 4.4 IP: Protocolo Internet(IP)
� Formato do Datagrama � Endereçamento IPv4 a� ICMP� IPv6
� 4.5 Algoritmos de Roteamento na Internet
4: Camada de Rede 4a-60
ICMP: Internet Control Message Protocol
� usado por estações,roteadores para comunicarinformação s/ camada de rede
� relatar erros: estação,rede, porta, protocoloinalcançáveis
� pedido/resposta de eco(usado por ping)
� camada de rede “acima de” IP:� msgs ICMP transportadas
em datagramas IP� mensagem ICMP: tipo, código,
o cabeçalho e os primeiros 8bytes do datagrama IP quecausou o erro
Tipo Código descrição0 0 resposta de eco (ping)3 0 rede dest. inalcançável3 1 estação dest inalcançável3 2 protocolo dest inalcançável3 3 porta dest inalcançável3 6 rede dest desconhecida3 7 estação dest desconhecida4 0 abaixar fonte (controle de
congestionamento - ñ usado)8 0 pedido eco (ping)9 0 anúncio de rota10 0 descobrir roteador11 0 TTL (sobrevida) expirada12 0 erro de cabeçalho IP
4: Camada de Rede 4a-61
Traceroute e ICMP� Fonte envia uma serie de
segmentos UDP para dest� Prim. tem TTL =1� Segundo tem TTL=2, etc.� Num. Porta improvável
� Qdo nth datagrama chegaao nth roteador:
� Roteador descarta datagr. � E envia para a fonte uma
mensagem ICMP (tipo 11,código 0)
� Mensagem inclui nome doroteador & endereço IP
� Quando a mensagem ICMPchega, a fonte calcula RTT
� Traceroute faz 3x aoperação
Critério de parada� Segmento UDP
eventualmente chega no SFdestino
� Destino retorna uma msgICMP “host unreachable”packet (tipo 3, cod. 3)
� Quando a fonte recebeessa Msg ICMP, para.
4: Camada de Rede 4a-62
Onde fica o ICMP
4: Camada de Rede 4a-63
Exemplo de uso traceroute
4: Camada de Rede 4a-64
IPv6� Motivação Inicial: Espaço de endereçametno
de 32 bits estava para ser alocado porcompleto.
� Motivação adcional:� Formato do cabeçalho ajuda na velocidade de
processamento/Comutação� Cabeçalho mudou para facilitar QoS
Formato do datagrama IPv6:• Cabeçalho de tamanho fixo 40 bytes• Não permite fragmentação
4: Camada de Rede 4a-65
Cabeçalho do Ipv6(Cont.)Pri identifica prioridade entre datagramas no fluxoFlow Label: identica datagramas em um “fluxo.” (conceito de“fluxo” não claramente definido).Next header: identica o protocolo da camada superior(UDP,TCP)
4: Camada de Rede 4a-66
Outras mudanças em relaçãoao IPv4� Checksum: removido para reduzir tempo de
processamento em cada salto� Options: possível, mas fora do cabeçalho,
indicado pelo campo “Next Header”� ICMPv6: nova versão do ICMP
� Tipos novos de mensagens, e.g. “Packet Too Big”� Funções para gerenciamento de transmissão em
grupo
4: Camada de Rede 4a-67
Transição do IPv4 para IPv6
� Nem todos os roteadores podem seratualizados simultaneamente� Sem a possibilidade de “flag days”� Como a rede poderia operar com um mix de
roteadores IPv4 e IPv6? � Tunneling: IPv6 transportado com carga nos
datagrama IPv4 ao longo de uma rotaadministrada por roteadores IPv4
4: Camada de Rede 4a-68
TunnelingA B E F
IPv6 IPv6 IPv6 IPv6
tunelIdeia:
ImplementadoA B E F
IPv6 IPv6 IPv6 IPv6IPv4 IPv4
4: Camada de Rede 4a-69
TunnelingA B E F
IPv6 IPv6 IPv6 IPv6
tunelIdeia:
Implementado:A B E F
IPv6 IPv6 IPv6 IPv6
C D
IPv4 IPv4
Flow: XSrc: ADest: F
data
Flow: XSrc: ADest: F
data
Flow: XSrc: ADest: F
data
Src:BDest: E
Flow: XSrc: ADest: F
data
Src:BDest: E
A-para-B:IPv6
E-para-F:IPv6B-para-C:
IPv6 dentroIPv4
B-para-C:IPv6 dentro
IPv4
4: Camada de Rede 4a-70
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distancia� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-71
1
23
0111
Valor no cab. dopacote que chega
Algo. de Roteamento
Tab. De repasseValor Head Link Saida
0100010101111001
3221
A interação entre roteamento ecomutação
4: Camada de Rede 4a-72
u
yx
wv
z2
21
3
1
1
2
53
5
Grafo: G = (N,E)
N = conjunto de roteadores = { u, v, w, x, y, z }
E = conj. de enlaces ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
A malha de roteadores comoum Grafo
4: Camada de Rede 4a-73
Grafo: Custos
u
yx
wv
z2
21
3
1
1
2
53
5 • c(x,x’) = custo do enlace (x,x’)
- e.g., c(w,z) = 5
• custo poder ser sempre 1, ou inversamente relacionado à banda,ou relacionado ao congestionamento
Custo de um caminho (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Questão: Qual é o caminho de Menor custo entre u e z ?
Algoritmo de Roteamento: algoritmo que encontra o caminho De menor custo.
4: Camada de Rede 4a-74
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distancia� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-75
Classificação para algoritmo deRoteamentoUsa informação Global ou
decentralizada?Global:� Todos os roteadores têm
topologia completa, info decusto do custo do enlace
� Algoritmos “estado do enlace” Decentralizado: � Roteadores sabem sobre os
vizinhos conectadosfisicamente, custo do enlacepara os vizinhos
� Processo iterativo decomputação, troca de infoentre os vizinhos
� Algoritmos “vetor distância”
Estático e dinâmico?Estático: � Rotas mudam lentamente
com o tempoDinâmico: � Rotas mudam mais
rapidamente� Atualização
periódicas� Em resposta a
mudanças no custo doenlace
4: Camada de Rede 4a-76
Algoritmo roteamento baseado emestado do enlaceAlgoritmo de Dijkstra� Conhece topologia da rede,
custo do enlaçe de todos osnós
� Obtido via “broadcast doestado do enlace”
� Todos os vértices tem amesma info
� Computa os caminhos de menorcusto de um vértice (fonte) atodos os demais vértices
� entrada tabela decomutação para o vértice
� iterações: após k iterações,descobre o caminho de menorcusto para k destinos
Notação:� c(x,y): custo do enlace do
vértice x para y; = ∞ senão forem vizinhos diretos
� D(v): valor atual do custodo caminho do verticefonte até o vértice v
� p(v): vértice predecessordo vértice v no caminho
� N': conjunto de vérticescujo o menor custo já sesabe em definitivo
4: Camada de Rede 4a-77
Algoritmo de Dijkstra1 Inicialização: 2 N' = {u} 3 para todos nós v 4 se v adjacente a u 5 então D(v) = c(u,v) 6 Senão D(v) = ∞ 7 8 Faça 9 encontre w fora de N' tal que D(w) seja mínimo 10 adcione w em N' 11 atualize D(v) para todo v adjacente a w e fora de N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* */ 14 Até que todos os nós em N'
4: Camada de Rede 4a-78
Algoritmo de Dijkstra: exemplo
Passo012345
N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)
u
yx
wv
z2
21
3
1
1
2
53
5
4: Camada de Rede 4a-79
Algoritmo de Dijkstra: exemplo
Passo012345
N'u
uxuxy
uxyvuxyvw
uxyvwz
D(v),p(v)2,u2,u2,u
D(w),p(w)5,u4,x3,y3,y
D(x),p(x)1,u
D(y),p(y)∞
2,x
D(z),p(z)∞ ∞
4,y4,y4,y
u
yx
wv
z2
21
3
1
1
2
53
5
4: Camada de Rede 4a-80
Algoritmo de Dijkstra: exemplo(2)
u
yx
wv
z
Arvore menor caminho a partir de u:
vxywz
(u,v)(u,x)(u,x)(u,x)(u,x)
Destino enlace
Tabela de comutação resultante em u:
4: Camada de Rede 4a-81
Algoritmo de Dijkstra, discursãoComplexidade do Algoritmo: n vértices� Cada iteração: precisa verificar todos vértices, w,
que não estão em N� n(n+1)/2 comparações: O(n2)� Implementação mais eficiente é possível: O(nlogn)
4: Camada de Rede 4a-82
Algoritmo de Dijkstra, discursão
Possíveis oscilações:� e.g., custo do enlace =
quantidade de tráfegotransferidoA
D
CB
1 1+e
e0
e1 1
0 0A
D
CB
2+e 0
001+e 1
AD
CB
0 2+e
1+e10 0
AD
CB
2+e 0
e01+e 1
initialização … recomputarotas
… recomputa … recomputa
AD
CB
0 0
00
e1 1
0 0
4: Camada de Rede 4a-83
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distância� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-84
Algoritmo vetor distância
Equação de Bellman-Ford
dx(y) := caminho de menor custo de x para yentão
dx(y) = min {c(x,v) + dv(y) }
onde min é tomado entre todos os vizinhos vde x
v
4: Camada de Rede 4a-85
Exemplo do Bellman-Ford
u
yx
wv
z2
21
3
1
1
2
53
5 Claramente, dv(z) = 5, dx(z) = 3, dw(z) = 3
du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4
Vértice que atinge o mínimo é o próximoSalto no caminho mais curto ➜ tabela de comutação
Equação B-F define:
4: Camada de Rede 4a-86
Algoritmo Vetor distância
� Dx(y) = estima o menor custo de x para y� Vértice x conhece o custo de cada vizinho
v: c(x,v)� Vértice x mantém o vetor distância Dx =
[Dx(y): y є N ]� Vértice x também mantém o vetor distância
dos seus vizinhos� Para cada vizinho v, x mantém
Dv = [Dv(y): y є N ]
4: Camada de Rede 4a-87
Algoritmo Vetor distância (4)
Idéia básica: � De tempo-em-tempo, cada vértice envia seu
próprio vetor distância para os vizinhos� Assincrona� Quando um vértice x recebe um novo DV estimado
de um vizinho, ele atualiza o seu próprio DV usandoequação de B-F:
Dx(y) ← minv{c(x,v) + Dv(y)} para cada vértice y ∊ N
� Em condição mínimas, e normais, Dx(y) convergepara o menor custo de fato dx(y)
4: Camada de Rede 4a-88
Algoritmo Vetor distância(5)
Iterativo, assincrono:cada iteração local causadapor:
� Mudança no custo local doenlace
� Mensagem de atualizaçãodo DV
Distribuído:� Cada vértice notifica os
vizinho somente quandoocorre mudança no seu DV
� Vizinhos então notificamseus vizinhos senecessário
espera por (mudança nocusto local ou msg dovizinho)
recomputa estima
se DV para qualquer dest
mudou, notifica vizinhos
Cada vértice:
4: Camada de Rede 4a-89
x y zxyz
0 2 7∞ ∞ ∞∞ ∞ ∞
de
Custo para
dede
x y zxyz
de
Custo para
x y zxyz
∞ ∞
∞ ∞ ∞
Custo para
x y zxyz
∞ ∞ ∞7 1 0
Custo para
∞2 0 1
∞ ∞ ∞
tempo
x z12
7
y
Tabela nó x
Tabela nó y
Tabela nó z
x y zxyz
deCusto para
x y zxyz
de
Custo para
x y zxyz
de
Custo para
x y zxyz
de
Custo para
x y zxyz
deCusto para
4: Camada de Rede 4a-90
x y zxyz
0 2 7∞ ∞ ∞∞ ∞ ∞
de
Custo para
dede
x y zxyz
0
de
Custo para
x y zxyz
∞ ∞
∞ ∞ ∞
Custo para
x y zxyz
∞ ∞ ∞7 1 0
Custo para
∞2 0 1
∞ ∞ ∞
2 0 17 1 0
tempo
x z12
7
y
Tabela nó x
Tabela nó y
Tabela nó z
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3
32
4: Camada de Rede 4a-91
x y zxyz
0 2 7∞ ∞ ∞∞ ∞ ∞
de
Custo para
dede
x y zxyz
0 2 3
de
Custo parax y z
xyz
0 2 3
de
Custo para
x y zxyz
∞ ∞
∞ ∞ ∞
Custo parax y z
xyz
0 2 7
deCusto para
x y zxyz
0 2 3
de
Custo para
x y zxyz
0 2 3
deCusto para
x y zxyz
0 2 7
de
Custo parax y z
xyz
∞ ∞ ∞7 1 0
Custo para
∞2 0 1
∞ ∞ ∞
2 0 17 1 0
2 0 17 1 0
2 0 13 1 0
2 0 13 1 0
2 0 1
3 1 02 0 1
3 1 0
time
x z12
7
y
Tabela nó x
Tabela nó y
Tabela nó z
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3
4: Camada de Rede 4a-92
Vetor distância: Mudanças no custo doenlaceMudança no custo do enlace:� Nó detecta mudança no custo do
enlace local� Atualiza info de roteamento,
recalcula o vetor distância� se mudança em DV, notifica vizinhos
“noticiaboa viajarápido”
x z14
50
y1
No tempo t0, y detecta mudança no custo do enlace, atualiza o DV, e informa seus vizinhos.
No tempo t1, z recebe a atualização de y e atualiza sua tabela. Ele computa um novo menor custo de x e envia-o para seus vizinhos DV.
No tempo t2, y recebe atualizações de z e atualiza sua tabela. O menor custo de y não mudam e assim y não envia nem uma mensagem para z.
4: Camada de Rede 4a-93
Vetor distância: Mudanças no custo doenlace
x z14
50
y60
4: Camada de Rede 4a-94
Vetor distância: Mudanças no custo doenlace
Mudança no custo do enlace:� Boas notícias chegam rápido� Notícias ruins vão mais devagar
– problema da “contageminfinita”!
� 44 iterações antes do algoritmose estabilizar
Envenenamento reverso: � Se Z está na rota de Y para X :
� Z informa a Y que sua (Z)distância para X é infinita(assim Y não irá rotear para Xvia Z)
� O problema serácompletamente resolvido?
x z14
50
y60
4: Camada de Rede 4a-95
Comparação entre DV e LS
Complexidade Mensagens� LS: cada n vértices, E enlaces,
O(nE) msgs são enviadas � DV: troca somente entre
vizinhos� Convergência em tempo varia
Velocidade de convergência� LS: Algoritmo O(n2) requer
O(nE) msgs� Por haver as ocilações
� DV: Convergência varia no tempo� Roteamento pode entrar em
loop� Problema da contagem
infinita
Robustez: O que acontecese o roteador passa aNão funcionar?
LS: � Vértice pode publicar
custo do enlace incorreto� Cada vértice computa
apenas a sua tabelaDV:
� Vértice DV pode publicarcusto incorreto docaminho
� Cada tabela no vértice éusada por outros
• Propaga erro pela rede
4: Camada de Rede 4a-96
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distância� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-97
Roteamento Hierárquico
escala: com 200 milhõesdestinos:
� Não há como armazenartodos os destinos nastabelas de roteamento!
� A troca de Tabela deroteamento podesobrecarregar os enlaçes!
Autonomia administrativas� Internet = rede de redes� Cada administrador pode
querer controlar oroteamento de sua rede
Os estudos sobre roteamento até então -idealização
� Todos os roteadores são identicos� Rede é “plana”… não é verdade na prática
4: Camada de Rede 4a-98
Roteamento Hierárquico
� Agrega roteadores emuma região, “sistemasautonomos” (AS)
� Roteadores em ummesmo AS rodam omesmo procotolo deroteamento
� Roteamento “intra-AS” � Roteamento em
diferentes AS podemrodar diferentesprotocolos deroteamento intra-AS
Roteador Gateway� Enlace direto para
roteador em outro AS
4: Camada de Rede 4a-99
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
Intra-ASAlgoritmo Roteamento
Inter-ASAlgoritmo Roteamento
RepasseTabela
3c
ASes Interconectados
� Tabelas de comutaçãoatualizadas por ambos osalgoritmos de roteamento:intra- e inter-AS
� Conjuntos de entradasintra-AS para destinosinternos
� Conjuntos de entradasinter-AS & intra-Aspara destinos externos
4: Camada de Rede 4a-100
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
3c
Tarefas Inter-AS� Suponha Roteador em
AS1 receba datagramadestinado para umponto fora de AS1:� Roteador deve
repassar pacotespara o roteadorborda, mais qualdeles?
AS1 deve:1. Aprender quais
destinos sãoalcançáveis através doAS2, e quais sãoatravés do AS3
2. Propagar a info dealcançabilidade paratodos os roteadoresem AS1
Traballho do roteamentointer-AS!
4: Camada de Rede 4a-101
Exemplo: configuração da tabela de repasse noroteador 1d
� Suponha AS1 aprende (via protocolo inter-AS) que asubrede x é alcançável via AS3 (borda 1c) mas não viaAS2.
� Protocolo inter-AS propaga a info de alcançabilidadepara todos os roteadores internos.
� Roteador 1d determina da informação de roteamento dointra-AS que sua interface I está no caminho de menorcusto para 1c.� Insere a entrada (x,I) na tabela de roteamento
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
3cx…
4: Camada de Rede 4a-102
Exemplo: Escolhendo entre múltiplos ASes
� Agora suponha AS1 saiba atravês do protocolointer-AS que a subrede x é alcançável a partir deAS3 e de AS2.
� Para configurar tabela de repasse, roteador 1d devedeterminar através de que roteador de borda eledeve repassar o pacotes para o destino x. � Essa também é a tarefa do procotolo de
roteamento inter-AS!
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
3cx… …
4: Camada de Rede 4a-103
Aprende pelo protocolo Inter-AS que a
Subrede x é alcançávelVia múltiplos
roteadores
Usa info roteamentodo procotocolo intra-AS para determinar
custos dos caminhosde menor custo para
cada roteador
Roteamento Hotpotato:
Escolhe o roteadorde borda que tem o
menor entre osmenos custos
Determine da tabela de Comutação a
interface I que levaO gateway de menor custo
Entre com (x,I) naTabela de comutação
Exemplo: Escolhendo entre múltiplos ASes
� Roteamento hot potato: envia pacotes através doroteador mais próximos entre os dois em questão.
4: Camada de Rede 4a-104
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distância� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-105
Roteamento Intra-AS
� Também conhecido como Interior GatewayProtocols (IGP)
� Os procotocolos mais comuns para roteamentoIntra-AS:
� RIP: Routing Information Protocol
� OSPF: Open Shortest Path First
� IGRP: Interior Gateway Routing Protocol(Proprietário da Cisco)
4: Camada de Rede 4a-106
Roteamento Intra-AS
� Também conhecido como Interior GatewayProtocols (IGP)
� Os procotocolos mais comuns para roteamentoIntra-AS:
� RIP: Routing Information Protocol
� OSPF: Open Shortest Path First
� IGRP: Interior Gateway Routing Protocol(Proprietário da Cisco)
4: Camada de Rede 4a-107
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distância� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-108
RIP ( Routing Information Protocol)
� Algoritmo vetor distância� Incluído na distribuição BSD-UNIX em 1982� Métrica distância: # de saltos(max = 15 saltos)
DC
BA
u vw
x
yz
Destino saltos u 1 v 2 w 2 x 3 y 3 z 2
Do roteador A para subredes:
4: Camada de Rede 4a-109
Propaganda RIP
� Vetores distância: trocas entre vizinhos acada 30 seg via Response Message (tambémchamado propaganda)
� Cada propaganda: lista até 25 destino desubredes dentro do AS
4: Camada de Rede 4a-110
RIP: Exemplo
Rede destino Prox. Roteador Nro. saltos p/ dest. w A 2
y B 2 z B 7
x -- 1…. …. ....
w x y
z
A
C
D B
Tabela roteamento/comutação em D
4: Camada de Rede 4a-111
RIP: Exemplo
Rede destino Prox roteador Nro de saltos dest. w A 2
y B 2 z B A 7 5
x -- 1…. …. ....
Tabela Roteamento/comutação em D
w x y
z
A
C
D B
Dest prox saltos w - 1 x - 1 z C 4 …. … ...
Propagandade A para D
4: Camada de Rede 4a-112
RIP: Falha/Recuperação em EnlaceSe não se escuta propaganda por 180 seg -->
vizinho/enlace é declarado morto� Rota via vizinho é invalidada� Nova propaganda enviada para vizinhos� Vizinhos a seu tempo enviam novas propagandas (se
tabela mudar)� Info de Falha enlace é propagado rapidamente(?)
para toda a rede� Envenenamento reverso usando para evitar loops
ping-pong (distância infinita = 16 hops)
4: Camada de Rede 4a-113
Processando Tabela RIP
� Tabelas de roteamento do RIP gerida por umprocesso da camada de aplicação route-d (daemon)
� Propaganda enviada em pacotes UDP, repetidoperiodicamente
físicaenlace
Rede comutação (IP) tabela
Transprt (UDP)
routed
físicaenlace
rede (IP)
Transprt (UDP)
routed
comutaçãotabela
4: Camada de Rede 4a-114
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distância� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-115
Posicionando o OSPF
4: Camada de Rede 4a-116
OSPF (Open Shortest Path First)� “aberto”: disponível publicamente (RFC 2328)� Usa algoritmo Estado Enlace
� Disseminação pacotes Estado Enlace� Mapa topologia em cada nó� Computação rotas usando algoritmo Dijkstra
� Propaganda é repassada para todo AS (via inundação)
4: Camada de Rede 4a-117
Formato Geral de uma mensagemOSPF
4: Camada de Rede 4a-118
Cabeçalho da mensagem OSPF
4: Camada de Rede 4a-119
OSPF: Mensagem de Hello
4: Camada de Rede 4a-120
Descobrindo vizinhos
4: Camada de Rede 4a-121
Características “avançadas” OSPF
� segurança: todas mensagens OSPF autenticada (paraprevinir intrusão)
� múltiplos caminhos como mesmo-custo são permitidos� Para cada enlaçe, múltiplas métricas de custo para
diferentes TOS (e.g., enlace satelite define “baixo”para melhor esforço; alto para tempo real)
� OSPF hieráquica em grandes domínios.
4: Camada de Rede 4a-122
OSPF Hierárquico� Hierarquica em duas-camadas: area local, backbone.
� Propaganda do estado do enlace somente na area� Cada nó tem a topologia detalhada da area; conheçe
somente direção (menor caminho) para redes emoutras areas.
� Roteadores de borda da area: “resume” distância pararedes em sua própria area, faz propaganda paraoutros roteadores de borda de area.
� Roteadores backbone: executa roteamento OSPFlimitado ao backbone.
� Roteadores de borda: conectado a outros AS’s.
4: Camada de Rede 4a-123
OSPF Hierárquico
4: Camada de Rede 4a-124
Capitulo 4: Camada Rede
� 4. 1 Introdução� 4.2 Redes circuito
Virtual e datagrama� 4.3 O que tem em um
roteador� 4.4 IP: Protocolo
Internet� Formato do Datagram� Endereçamento IPv4� ICMP� IPv6
� 4.5 Algoritmos deroteamento
� Estado do Enlace� Vetor Distância� Roteamento Hierárquico
� 4.6 Roteamento naInternet
� RIP� OSPF� BGP
� 4.7 roteamentoBroadcast e multicast
4: Camada de Rede 4a-125
Roteamento inter-AS na Internet:BGP� BGP (Border Gateway Protocol): padrão de
fato� BGP prover a cada AS uma maneira de:
1. Obter informação de alcançabilidade de umasubrede a partir de ASs vizinhos.
2. Propaga informação de alcançabilidade paratodos os roteadores internos a um AS.
3. Determina rotas “boas” para subredes baseadona informação de alcançabilidade e a políticado AS.
� Permite subrede anunciar sua existênciapara o restante da Internet: “Estou aqui”
4: Camada de Rede 4a-126
O Básicão do BGP� Pares de roteadores (pares BGP) trocam info de
roteamento em conexões TCP semi-permanentes: sessão BGP� Sessões BGP não precisam corresponder a
conexões físicas.� Quando AS2 anuncia um pré-fixo para AS1:
� AS2 compromete-se a repassar datagramas paraaquele pré-fixo.
� AS2 pode agregar prefixos em sua propaganda• Exemplo!!!
3b
1d
3a
1c2aAS3
AS1
AS21a
2c
2b
1b
3ceBGP sessão
iBGP sessão
4: Camada de Rede 4a-127
Distribuindo info alcançabilidade� Usando sessão eBGP entre 3a e 1c, AS3 envia pré-fixo
como info de alcançabilidade para AS1.� 1c pode então usar iBGP para distribuir nova info de
pré-fixo para todos os roteadores no AS1� 1b pode então anunciar novamente nova info de
alcançabilidade para AS2 sobre sessão eBGP 1b-para-2a
� Quando roteador aprende sobre o novo pré-fixo, elecria uma entrada para o pré-fixo em sua tabela decomutação.
3b
1d
3a
1c2aAS3
AS1
AS21a
2c
2b
1b
3ceBGP sessão
iBGP sessão
4: Camada de Rede 4a-128
Atributos de caminhos & rotasBGP� Pré-fixo anunciado inclue atributos BGP.
� pré-fixo + atributos = “rota”� Dois atributos importantes:
� AS-PATH: contém ASs por onde o anuncio do pré-fixo passou: ex, AS 67, AS 17
� NEXT-HOP: indica roteador específico interno aoAS para próximo salto no AS. (pode ser multíplosenlaces do AS corrente para próximo hop-AS)
� Quando roteador de borda recebe um anunciode rota, usa política importa paraaceitar/declinar.
4: Camada de Rede 4a-129
Seleção rota BGP
� Roteadores podem aprender sobre mais deuma rota para o mesmo pré-fixo. Roteadordeve selecionar rota.
� Regras para eliminação:1. Atributo valor local de preferência.2. O menor AS-PATH 3. Roteador NEXT-HOP mais próximo:
roteamento hot potato4. Critérios adcionais
4: Camada de Rede 4a-130
Mensagens BGP
� Troca d Mensagens BGP usando TCP.� Mensagens BGP:
� OPEN: abre uma conexão TCP para o par eautêntica transmissor
� UPDATE: anuncia novo caminho(ou remove antigo)� KEEPALIVE conexão mantiva ativa mesmo na
ausencia de UPDATES; também quer ACKs OPEN� NOTIFICATION: reporta erros em mensagen
anterior; também usada para fechar conexão
4: Camada de Rede 4a-131
Politica de roteamento BGP
� A,B,C são redes provedoras� X,W,Y são clientes (das redes provedoras)� X é dual-homed: conectado para duas redes
� X não deseja rotear de B para C� .. assim X não irá anunciar para B uma rota para C
A
B
C
W X
Y
legenda:
cliente rede:
provedor rede
4: Camada de Rede 4a-132
Politica roteamento BGP (2)
� A anuncia caminho AW para B� B anuncia caminho BAW para X � B deve anunciar caminho BAW para C?
� Não! B não tem ganho para roteamento CBAW umavez que nem W nem C são clientes de B
� B quer forçar C rotear para w via A� B quer rotear somente de/para seus clientes!
A
B
C
W X
Y
legenda:
cliente rede:
provedora rede
4: Camada de Rede 4a-133
Porque o roteamento Intra- e Inter-AS édiferente? Politica: � Inter-AS: adminstrador deseja controlar como o seu
tráfego é roteado, que rotas este deve seguir narede.
� Intra-AS: único administrador, assim não precisa depoliticas
Escala:� Roteamento hierárquico economiza tamanho da tabela,
reduz tráfego de atualizaçãoPerformance: � Intra-AS: foca na performance� Inter-AS: politica pode dominar performance