Capítulo 4: Camada de RedeEndereçamento IPv4 a ICMP IPv6 4.5 Algoritmos de Roteamento na Internet 4: Camada de Rede 4a-2 Camada de rede Dinâmica: Transporta segmento do SF transmissor

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


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 linkphysicalnetwork

data linkphysical


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.


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


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?


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.


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 ?






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;


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


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


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


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


redeenlacefísica

1. inicia chamada 2. chegada de chamada3. chamada aceita4. conexão completa

5. começa fluxo de dados 6. dados recebidos


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


redeenlacefísica


redeenlacefísica

1. envia dados 2. recebe dados


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


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







Arquitetura de um Roteador


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


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!


Três tipos de matriz de comutação


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


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)


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.


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


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!






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


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.


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




➼ Formato do Datagrama ➼ Endereçamento IPv4➼ ICMP➼ IPv6


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


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


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


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”:


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


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


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”


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


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


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


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)


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


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


Quantos estão de fato ativos


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



➘ 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);


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



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



➘ 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;


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 ?


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


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







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


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.


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


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


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


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


TunnelingA B E F

IPv6 IPv6 IPv6 IPv6

tunelIdeia:

Physical view:A B E F

IPv6 IPv6 IPv6 IPv6IPv4 IPv4


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


data


data

Src:BDest: E


data

Src:BDest: E

A-para-B:IPv6

E-para-F:IPv6B-para-C:

IPv6 dentroIPv4

B-para-C:IPv6 dentro

IPv4


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


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


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


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.








➼ Estado do Enlace➼ Vetor Distancia➼ Roteamento Hierárquico





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


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


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'


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


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:


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)


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








➼ Estado do Enlace➼ Vetor Distância➼ Roteamento Hierárquico





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


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:


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 ]


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)


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:


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


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


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.


Vetor distância: Mudanças no custo do enlace

x z14

50

y60


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


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













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


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


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


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!













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)













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:


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


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


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


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)


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


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.













Posicionando o OSPF


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)


Formato Geral de uma mensagem OSPF


Cabeçalho da mensagem OSPF


OSPF: Mensagem de Hello


Descobrindo vizinhos


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.


OSPF Hierárquico













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


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


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


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!













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”


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


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


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.


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


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


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


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


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

Documents

Capítulo 4: Camada de RedeEndereçamento IPv4 a ICMP IPv6 4.5 Algoritmos de Roteamento na Internet 4: Camada de Rede 4a-2 Camada de rede Dinâmica: Transporta segmento do SF transmissor