View
2
Download
0
Category
Preview:
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 de transporte;
Observações:➘ O protocolo da camada de rede é
implementada em todos os SF e roteadores;
➘ Roteador examina campos do cabeç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 ser oferecido 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 por datagramas:
➘ Entrega garantida;➘ Entrega garantida com
limite de tempo( em menos que 40 msec de atraso).
Serviço para um fluxo de datagramas:
➘ Entrega datagrama na-ordem de geração;
➘ Garantia mínima de banda para o fluxo;
➘ Restrição de mudanças no espaçamento entre pacotes.
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 orientado e 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ço orientado 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 alocados ao CV
➼ para permitir desempenho como de um circuito
“caminho da-origem-ao-destino se comporta como um circuito 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 seguir caminhos 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”
Prefi x 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-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ória da porta de entrada
➘ meta: completar processamento da porta de entrada na ‘velocidade da linha’
➘ filas: se datagramas chegam mais rápido que taxa de re-envio para matriz de comutaçã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 nas portas de entrada
➘ Bloqueio cabeça-de-fila (Head-of-the-Line - HOL): datagrama na cabeça da fila impede outros na mesma fila de avançarem
➘ retardo de enfileiramento e perdas devido ao transbordo 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 da memó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 porta de entrada à memória da porta de saída via um barramento compartilhado
➘ contenção pelo barramento: taxa de comutação limitada pela largura de banda do barramento
➘ Barramento de 1 Gbps, Cisco 1900: velocidade suficiente para roteadores de acesso e corporativos (mas não regionais ou de backbone)
4: Camada de Rede 4a-25
Comutação via uma Rede de Interconexã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 da matriz de comutação mais rapidamente que a taxa de transmissão
➘ Disciplina de escalonamento escolhe um dos datagramas enfileirados para transmissão
4: Camada de Rede 4a-27
Filas na Porta de Saída
➘ usa buffers quando taxa de chegada através do comutador excede taxa de transmissão de saída
➘ enfileiramento (retardo), e perdas devidas ao transbordo 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 overhead com 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ão entre estação, roteador e enlace físico
➼ roteador típico tem múltiplas interfaces
➼ estação pode ter múltiplas interfaces
➼ endereço IP associado à interface, não à estação ou 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 de mais alta ordem)
➼ parte de estação (bits de mais baixa ordem)
➘ O que é uma rede IP? (da perspectiva do endereço IP)
➼ interfaces de dispositivos com a mesma parte de rede nos seus endereços IP
➼ podem alcançar um ao outro sem passar por um 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
Esta rede consiste de 3 redes IP(para endereços IP começando com 223, os primeiros 24 bits são a parte de rede)
LAN
4: Camada de Rede 4a-35
Endereçamento IPComo achar as redes?➘ Desacoplar cada
interface do seu roteador, ou estação;
➘ criar “ilhas” de redes isoladas;
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) - maior tamanho possível de quadro neste enlace.
➼ tipos diferentes de enlace têm MTUs diferentes
➘ datagrama IP muito grande dividido (“fragmentado”) dentro da rede
➼ um datagrama vira vários datagramas
➼ “remontado” apenas no destino final
➼ bits do cabeçalho IP usados para identificar, ordenar fragmentos relacionados
fragmentação: entrada: um datagrama
grandesaída: 3 datagramas
menores
remontagem
4: Camada de Rede 4a-39
Endereços IP: como conseguir um?
Estações (parte de estação):➘ codificado pelo administrador num arquivo
➼ Windows: control-panel->network->configuration->tcp/ip->properties
➼ Linux/ubuntu: /etc/network/interfaces➘ DHCP: Dynamic Host Configuration Protocol: obtém
endereç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: cenário cliente-servidorServidor 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
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-43
Endereçamento IP: a última palavra...
P: Como um provedor IP consegue um bloco de endereç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-44
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 permanece inalterado, enquanto passa da origem ao destino
➘ campos de endereços de interesse 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-48
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-49
Quantos estão de fato ativos
4: Camada de Rede 4a-50
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 ou destino nesta rede tem endereço 10.0.0/24 para fonte, e de destino o usual
Todos os datagramas saindo da rede local tem o mesmo endereço NAT IP: 138.76.29.7, diferentes números de portas fontes
4: Camada de Rede 4a-51
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 (melhora segurança);
4: Camada de Rede 4a-52
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ço NAT IP, nova porta #). . . clientes/servidores remotos irão responder
usando (endereço NAT IP, nova porta #) como endereço destino.
➼ guardar (na tabela de tradução de endereços NAT): os pares de tradução de endereços (endereço IP fonte, porta #) para (endereços NAT IP, nova porta #)
➼ Datagramas que chegam: trocar (endereço NAT IP, nova porta #) no campo de destino de cada datagrama que chega com o correspondente (endereço IP fonte, porta #) armazenado na tabela NAT
4: Camada de Rede 4a-53
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-54
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é no má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-55
Passando pelo NAT ➘ cliente quer se conectar ao
servidor que tem endereço 10.0.0.1
➼ O endereço do servidor(10.0.0.1) é válido na LAN (cliente Não pode usar como endereço de destino)
➼ Somente o endereço NATted é visível: 138.76.29.7
➘ Solução 1: configurar estaticamente o NAT para repassar requisições de conexão de uma dada porta para o servidor
➼ e.g., (123.76.29.7, port 2500) sempre repassa para 10.0.0.1 porta 25000
10.0.0.1
10.0.0.4
NAT router
138.76.29.7
Cliente ?
4: Camada de Rede 4a-56
Passando pelo NAT ➘ solução 2: Protocolo Universal
Plug and Play (UPnP) Internet Gateway Device (IGD). Permite SF NATted: Encontrar um endereço IP
público (138.76.29.7) Adcionar/remover
mapeamento de porta (com lease times)
i.e., automatiza a solução estática de mapeamento de porta
10.0.0.1
10.0.0.4
NAT router
138.76.29.7
IGD
4: Camada de Rede 4a-57
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 para o relay iniciadapelo SF NATted
2. conexão para o relay iniciada pelo cliente
3. relaying estabelecido
4: Camada de Rede 4a-58
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-59
ICMP: Internet Control Message Protocol
➘ usado por estações, roteadores para comunicar informação s/ camada de rede
➼ relatar erros: estação, rede, porta, protocolo inalcançá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
nos primeiros 8 bytes do datagrama IP causando 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-60
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 chega ao nth roteador:
➼ Roteador descarta datagr. ➼ E envia para a fonte uma
mensagem ICMP (tipo 11, código 0)
➼ Mensagem inclui nome do roteador & endereço IP
➘ Quando a mensagem ICMP chega, a fonte calcula RTT
➘ Traceroute faz 3x a operação
Critério de parada➘ Segmento UDP
eventualmente chega no SF destino
➘ Destino retorna uma msg ICMP “host unreachable” packet (tipo 3, cod. 3)
➘ Quando a fonte recebe essa Msg ICMP, para.
4: Camada de Rede 4a-61
IPv6➘ Motivação Inicial: Espaço de
endereçametno de 32 bits estava para ser alocado por completo.
➘ 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-62
Cabeçalho do Ipv6(Cont.)Pri identica prioridade entre datagramas no fluxoFlow Label: identica datagramas em um “fluxo.” (conceito de“fluxo” não claramente definido).Next header: identica a camada de cima
4: Camada de Rede 4a-63
Outras mudanças em relação ao 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-64
Transição do IPv4 para IPv6
➘ Nem todos os roteadores podem ser atualizados 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 rota administrada por roteadores IPv4
4: Camada de Rede 4a-65
TunnelingA B E F
IPv6 IPv6 IPv6 IPv6
tunelIdeia:
Physical view:A B E F
IPv6 IPv6 IPv6 IPv6IPv4 IPv4
4: Camada de Rede 4a-66
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-67
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 de roteamento
➼ Estado do Enlace➼ Vetor Distancia➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-68
1
23
0111
value in arrivingpacket’s header
routing algorithm
local forwarding tableheader value output link
0100010101111001
3221
A interação entre roteamento e comutação
4: Camada de Rede 4a-69
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 como um Grafo
4: Camada de Rede 4a-70
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-71
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 de roteamento
➼ Estado do Enlace➼ Vetor Distancia➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-72
Classificação para algoritmo de RoteamentoUsa informação Global ou
decentralizada?Global:➘ Todos os roteadores têm topologia
completa, info de custo do custo do enlace
➘ Algoritmos “estado do enlace” Decentralizado: ➘ Roteadores sabem sobre os
vizinhos conectados fisicamente, custo do enlace para os vizinhos
➘ Processo iterativo de computação, troca de info entre 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 do enlace
4: Camada de Rede 4a-73
Algoritmo roteamento baseado em estado do enlaceAlgoritmo de Dijkstra➘ Conhece topologia da rede, custo
do enlaçe de todos os nós➼ Obtido via “broadcast do
estado do enlace” ➼ Todos os vértices tem a
mesma info➘ Computa os caminhos de menor
custo de um vértice (fonte) a todos os demais nós
➼ entrada tabela de comutação para o vértice
➘ iterações: após k iterações, descobre o caminho de menor custo para k destinos
Notação:➘ c(x,y): custo do enlace do
vértice x para y; = ∞ se nào forem vizinhos diretos
➘ D(v): valor atual do custo do caminho do vertice fonte até o vértice v
➘ p(v): vértice predecessor do vértice v no caminho
➘ N': conjunto de vértices cujo o menor custo já se sabe em definitivo
4: Camada de Rede 4a-74
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-75
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-76
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-77
Algoritmo de Dijkstra, discursãoComplexidade do Algoritmo: n vértices➘ Cada iteração: precisa verificar todos vértices, w,
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-78
Algoritmo de Dijkstra, discursão
Possíveis oscilações:➘e.g., custo do enlace = quantidade de tráfego transferido
AD
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-79
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-80
Algoritmo vetor distância
Equação de Bellman-Ford(programação dinâmica)Definadx(y) := caminho de menor custo de x para y
então
dx(y) = min {c(x,v) + dv(y) }
onde min é tomado entre todos os vizinhos v de x
v
4: Camada de Rede 4a-81
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-82
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-83
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 usando equaçã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) converge para o menor custo de fato dx(y)
4: Camada de Rede 4a-84
Algoritmo Vetor distância(5)
Iterativo, assincrono: cada iteração local causada por:
➘ Mudança no custo local do enlace
➘ Mensagem de atualização do DV
Distribuído:➘ Cada vértice notifica os
vizinho somente quando ocorre mudança no seu DV
➼ Vizinhos então notificam seus vizinhos se necessário
espera por (mudança no custo local ou msg do vizinho)
recomputa estima
se DV para qualquer dest
mudou, notifica vizinhos
Cada vértice:
4: Camada de Rede 4a-85
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-86
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-87
Vetor distância: Mudanças no custo do enlaceMudanç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-88
Vetor distância: Mudanças no custo do enlace
x z14
50
y60
4: Camada de Rede 4a-89
Vetor distância: Mudanças no custo do enlace
Mudança no custo do enlace:❒ Boas notícias chegam rápido❒ Notícias ruins vão mais devagar –
problema da “contagem infinita”!❒ 44 iterações antes do algoritmo se
estabilizarEnvenenamento 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 X via Z)
❒ O problema será completamente resolvido?
x z14
50
y60
4: Camada de Rede 4a-90
Comparação entre DV e LSComplexidade 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 acontece se o roteador passa a Não funcionar?
LS: ➼ Vértice pode publicar custo
do enlace incorreto➼ Cada vértice computa apenas
a sua tabelaDV:
➼ Vértice DV pode publicar custo incorreto do caminho
➼ Cada tabela no vértice é usada por outros
• Propaga erro pela rede
4: Camada de Rede 4a-91
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-92
Roteamento Hierárquico
escala: com 200 milhões destinos:
➘ Não há como armazenar todos os destinos nas tabelas de roteamento!
➘ A troca de Tabela de roteamento pode sobrecarregar os enlaçes!
Autonomia administrativas➘ Internet = rede de redes➘ Cada administrador pode
querer controlar o roteamento 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-93
Roteamento Hierárquico➘ Agrega roteadores em
uma região, “sistemas autonomos” (AS)
➘ Roteadores em um mesmo AS rodam o mesmo procotolo de roteamento
➼ Roteamento “intra-AS” ➼ Roteamento em diferentes
AS podem rodar diferentes protocolos de roteamento intra-AS
Roteador Gateway➘ Enlace direto para
roteador em outro AS
4: Camada de Rede 4a-94
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
Intra-ASAlgoritmo Roteamento
Inter-ASAlgoritmo Roteamento
RepasseTabela
3c
ASes Interconectados
➘ Tabelas de comutação atualizadas por ambos os algoritmos de roteamento: intra- e inter-AS
➼ Conjuntos de entradas intra-AS para destinos internos
➼ Conjuntos de entradas inter-AS & intra-As para destinos externos
4: Camada de Rede 4a-95
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
3c
Tarefas Inter-AS➘ Suponha Roteador em
AS1 receba datagrama destinado para um ponto fora de AS1:➼ Roteador deve
repassar pacotes para o roteador borda, mais qual deles?
AS1 deve:1. Aprender quais
destinos são alcançáveis através do AS2, e quais são através do AS3
2. Propagar a info de alcançabilidade para todos os roteadores em AS1
Traballho do roteamento inter-AS!
4: Camada de Rede 4a-99
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-100
Roteamento Intra-AS
➘ Também conhecido como Interior Gateway Protocols (IGP)
➘ Os procotocolos mais comuns para roteamento Intra-AS:
➼ RIP: Routing Information Protocol➼ OSPF: Open Shortest Path First➼ IGRP: Interior Gateway Routing
Protocol (Proprietário da Cisco)
4: Camada de Rede 4a-101
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-102
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-103
Propaganda RIP
➘ Vetores distância: trocas entre vizinhos a cada 30 seg via Response Message (também chamado propaganda)
➘ Cada propaganda: lista até 25 destino de subredes dentro do AS
4: Camada de Rede 4a-104
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-105
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-106
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-107
Processando Tabela RIP
➘ Tabelas de roteamento do RIP gerida por um processo da camada de aplicação route-d (daemon)
➘ Propaganda enviada em pacotes UDP, repetido periodicamente
físicaenlace
Rede comutação (IP) tabela
Transprt (UDP)
routed
físicaenlace
rede (IP)
Transprt (UDP)
routed
comutaçãotabela
4: Camada de Rede 4a-108
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 em outras areas.
➘ Roteadores de borda da area: “resume” distância para redes em sua própria area, faz propaganda para outros roteadores de borda de area.
➘ Roteadores backbone: executa roteamento OSPF limitado ao backbone.
➘ Roteadores de borda: conectado a outros AS’s.
4: Camada de Rede 4a-109
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-110
Posicionando o OSPF
4: Camada de Rede 4a-111
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-112
Formato Geral de uma mensagem OSPF
4: Camada de Rede 4a-113
Cabeçalho da mensagem OSPF
4: Camada de Rede 4a-114
OSPF: Mensagem de Hello
4: Camada de Rede 4a-115
Descobrindo vizinhos
4: Camada de Rede 4a-116
Características “avançadas” OSPF
➘ segurança: todas mensagens OSPF autenticada (para previnir 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-117
OSPF Hierárquico
4: Camada de Rede 4a-118
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-119
Roteamento Hierárquico
escala: com 200 milhões destinos:
➘ Não há como armazenar todos os destinos nas tabelas de roteamento!
➘ A troca de Tabela de roteamento pode sobrecarregar os enlaçes!
Autonomia administrativas➘ Internet = rede de redes➘ Cada administrador pode
querer controlar o roteamento 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-120
Roteamento Hierárquico➘ Agrega roteadores em
uma região, “sistemas autonomos” (AS)
➘ Roteadores em um mesmo AS rodam o mesmo procotolo de roteamento
➼ Roteamento “intra-AS” ➼ Roteamento em diferentes
AS podem rodar diferentes protocolos de roteamento intra-AS
Roteador Gateway➘ Enlace direto para
roteador em outro AS
4: Camada de Rede 4a-121
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
Intra-ASAlgoritmo Roteamento
Inter-ASAlgoritmo Roteamento
RepasseTabela
3c
ASes Interconectados
➘ Tabelas de comutação atualizadas por ambos os algoritmos de roteamento: intra- e inter-AS
➼ Conjuntos de entradas intra-AS para destinos internos
➼ Conjuntos de entradas inter-AS & intra-As para destinos externos
4: Camada de Rede 4a-122
3b
1d
3a
1c2aAS3
AS1AS2
1a
2c2b
1b
3c
Tarefas Inter-AS➘ Suponha Roteador em
AS1 receba datagrama destinado para um ponto fora de AS1:➼ Roteador deve
repassar pacotes para o roteador borda, mais qual deles?
AS1 deve:1. Aprender quais
destinos são alcançáveis através do AS2, e quais são através do AS3
2. Propagar a info de alcançabilidade para todos os roteadores em AS1
Traballho do roteamento inter-AS!
4: Camada de Rede 4a-123
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 de roteamento
➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico
➘ 4.6 Roteamento na Internet
➼ RIP➼ OSPF➼ BGP
➘ 4.7 roteamento Broadcast e multicast
4: Camada de Rede 4a-124
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 uma subrede a partir de ASs vizinhos.
2. Propaga informação de alcançabilidade para todos os roteadores internos a um AS.
3. Determina rotas “boas” para subredes baseado na informação de alcançabilidade e a política do AS.
❒ Permite subrede anunciar sua existência para o restante da Internet: “Estou aqui”
4: Camada de Rede 4a-125
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 rem rapassar datagramas para aquele 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-126
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, ele cria uma
entrada para o pré-fixo em sua tabela de comutação.
3b
1d
3a
1c2aAS3
AS1
AS21a
2c
2b
1b
3ceBGP sessão
iBGP sessão
4: Camada de Rede 4a-127
Atributos de caminhos & rotas BGP➘ 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 ao AS para próximo salto no AS. (pode ser multíplos enlaces do AS corrente para próximo hop-AS)
➘ Quando roteador de borda recebe um anuncio de rota, usa política importa para aceitar/declinar.
4: Camada de Rede 4a-128
Seleção rota BGP
❒ Roteadores podem aprender sobre mais de uma rota para o mesmo pré-fixo. Roteador deve 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-129
Mensagens BGP
➘ Troca d Mensagens BGP usando TCP.➘ Mensagens BGP:
➼ OPEN: abre uma conexão TCP para o par e autê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-130
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-131
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 uma vez 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-132
Porque o roteamento Intra- e Inter-AS é diferente? Politica: ➘ Inter-AS: adminstrador deseja controlar como o seu tráfego
é roteador, que rotas este deve seguir na rede. ➘ Intra-AS: único administrador, assim não precisa de politicasEscala:➘ Roteamento hierárquico economiza tamanho da tabela, reduz
atualização de tráfegoPerformance: ➘ Intra-AS: foca na performance➘ Inter-AS: politica pode dominar performance
Recommended