Camada de Rede

23 de junho de 2015

A Internet

Figura: A Internet e uma colecao interconectada de muitas redes(Tanembaum 5ed. Fig. 5-45)

2/52

Camada de Rede segundo o OSI

I Objetivo: prover funcionalidades para modos de transmissaocom e sem conexao para entidades da camada de transporte

I Estabelecer, manter e terminar conexoes entre sistemasabertos (isto e, redes)

I Promover troca de unidades de dados de servicos de redes:pacotes

I Manter enderecamento entre hosts de redes distintas

I Qualidade de servico

3/52

Servicos providos a camada de transporte

I Servicos devem ser independentes da tecnologia do roteador

I Transporte deve desconhecer o numero, tipo e topologia daredes

I Enderecos de rede deve ser disponibilizados a camada detransporte de maneira uniforme, independente do tipo de rede

4/52

Funcoes da Camada de Rede

I Roteamento e repasse de pacotes

I Multiplexacao de conexoes de rede em um mesmo enlace dedados

I Deteccao e recuperacao de erros

I Sequenciamento de pacotes e controle de fluxo

I Selecao de servicos

I Gerenciamento da camada de rede

I Mapeamento de enderecos e transmissoes da camada deenlace em enderecos e transmissoes da camada de rede

5/52

Roteamento e repasse

I Conexoes de rede sao providas por entidades de rede emsistemas OSI e por sistemas abertos intermediarios queproveem o servico de repasse (forwarding)

I Sistemas abertos intermediarios podem usarI conexoes intermediarias de rede;I transmissao por conexoes de enlace eI meios fısicos distintos

I O caminho de repasses (rota) e importante para acomunicacao resultante

I caminho pode considerar a qualidade de transmissao, custofinanceiro e outros

6/52

Transmissao com e sem conexao

Funcao Com conexao Sem conexaoConfiguracaodo caminho

sim desnecessario

Enderecamento numero VC end. destinoInformacaode estado

manutencao de circuitos sem info. de transmissoes

Roteamento criar circuito pacotes sao independentesQualidade deservico

sim difıcil

Controle decongestiona-mento

sim difıcil

Efeito de fa-lhas

circuitos falham datagrama perdido

I Com conexoes ou Rede de Circuitos Virtuais: X.25, FrameRelay, ATM, MPLS

I Sem conexoes ou Rede de Datagramas: IP

7/52

Redes de Circuitos Virtuais vs. Rede de Datagramas

I Tempo de configuracao de circuito vs. Tempo deprocessamento por pacote

I Tamanho do endereco de circuito vs. tamanho do endereco dehost

I Garantia de qualidade vs. melhor esforco

I Uso de longa duracao vs. uso imediato e curto

I Falhas em circuitos catastroficas vs. perda de poucos pacotes

8/52

Circuitos virtuais (CV)

I Caminho da origem aodestino comporta-se comoum circuito

I Cada parte do caminhovirtual (CV) e reservadacom antecipacao

I Uso de id do circuito em vezde endereco destino

I Recursos alocados =teoricamente mais previsıvel

I Roteadores precisam manterinformacoes sobre circuito

Tabela de circuitos de um roteadorEntrada CV in Saıda CV out

1 12 2 222 63 1 183 7 2 171 97 3 87

9/52

Redes de datagramas

I Em vez de reserva de recursos, polıtica do melhor esforcoI Em vez de id CV, usa endereco finalI Pacotes podem usar diferentes caminhos

A

B

C

D

E F

4

13

2

PPPLAN

A p/ 1,2,3Dest. RotaA –B BC CD BE CF C

A p/ 4Dest. RotaA –B BC CD BE BF B

CDest. RotaA AB AC –D EE EF E

EDest. RotaA CB DC CD DE –F F

10/52

Embate Circuitos vs. Datagramas

I Circuitos (telefonia): X.25, Frame Relay, ATM

I Datagramas (Arpanet): Internet Protocol (IP)I Decada de 1990: embate entre ATM vs. IP

I Bellheads (ITU) vs. Netheads (IETF)I Bellheads: telefoniaI Netheads: InternetI http:

//archive.wired.com/wired/archive/4.10/atm_pr.html

I Fracasso do ATM em manter QoS em ambientes reais

I Domınio do IP

I Porem, atual crescimento de tecnologias orientadas a conexao:MPLS e VLAN

11/52

ATM vs. IP

I EnderecamentoI Celulas ATM tem o id do circuito virtual e nao endereco final

I CobrancaI ATM: possıvel cobrar pelo uso de diferentes caminhosI IP: e mais facil cobrar uma tarifa fixa

I SobrecargaI ATM: se algum host no CV falha, conexao e perdidaI IP: se um roteador sofre sobrecarga, e facil usar outro

I Planejamento e aproveitamentoI ATM: melhor planejamento, oferecimento de garantiasI IP: melhor uso dos recursos, melhor esforco

I Uso da redeI ATM: proporcionalidade de largura de bandaI IP: fila simples (FIFO)

I DesempenhoI ATM: cam. fısica +rapida pois +simples: 5+48 = 53 bytesI Pacote IP: de 20+ 12/65516 = ate 65536 bytes

I IP RSVP (protocolo de transporte para reserva de recursos)

12/52

Repasse e roteamento

I Repasse e o envio para aproxima rede

I Roteamento envolve opreenchimento de tabelapara escolha de qual e amelhor proxima rede parachegar ao destino final

I RIP, OSPF, BGP

tabela de repasse localcabecalho dopacote

enlacesaıda

0100 30101 20111 21001 1

1

2

3

13/52

Roteamento

I Comutacao rapida de pacotesI Arquitetura de comutacao e escalonamento

I Roteamento em broadcast

I Roteamento em redes de dadosI Requisitos

I Corretude e SimplicidadeI Robustez

I Execucao por longo tempo, mesmo se houver falhas

I EstabilidadeI Escolha rapida de rotas que nao mudam com frequencia

I Equidade (fairness)I Exemplo: reduzir atraso medio de pacotes

I EficienciaI Exemplo: maximizar transmissao de saıda

14/52

Algoritmos de roteamento

I Algoritmos nao-adaptativosI Rotas calculadas com antecipacaoI Nao responde a falhas

I Algoritmos adaptativosI Rotas sao redefinidas de acordo com o uso da redeI Redefinicao periodica ou de acordo com mudancas na topologia

15/52

Tipos de roteamento

I Um sistema autonomo e uma colecao de redes sob umaadministracao centralizada

I Roteamento dentro de um sistema autonomo “interiorgateway routing protocol”

I Routing Information Protocol (baseado em vetor de distancias)I Open Shortest Path First (baseado no estado de enlaces)

I Roteamento entres sistemas autonomosI Border Gateway Protocol

16/52

Princıpio da otimalidade de Bellman

I Se J esta no caminho otimo entre I e K, entao o caminhoentre J e K e parte do caminho entre I e K

B

A

F

D EC

J

N

O

IH

G

L

M

K

(a)

B

A

F

D E

C

J

N

O

IH

G

L

M

K

(b)

Figura: Uma rede e uma arvore de caminhos otimos a partir do roteadorB (sink tree).

17/52

Algoritmo de menor caminho

I Menor caminhoI Numero de “hops”, isto e, transicoes entre roteadoresI Distancia geograficaI E outros...

I Algoritmos de menor caminhoI Adaptacao do Algoritmo de Dijkstra com min-heap:

O(|V | log |V |)I Uso da min-heap para avaliar distancias a vertices

I Conhecimento global da rede

18/52

Roteamento por uma tecnica local: flooding

I Nao e possıvel obter conhecimento global da redeinstantaneamente

I Pacote de entrada e repassado a toda linha de saıda, excetopor onde veio

I Cada pacote tem um contador de “idade” no cabecalhoI Contador e inicializado com valor do comprimento do caminho

ate destinoI Contador e decrementado a cada hopI Se contador=0, descartar pacote

I Se caminho nao e conhecido, inicializacao no pior caso e igualao diametro da rede

I Roteador podem manter em uma tabela para evitar re-repasses

I Possıvel manter um limiar k que indica que todos os pacotesate k foram repassados

I Baixa configuracao, sempre encontra menor caminho e semprepacote chega a todos na rede

19/52

Roteamento por vetor de distancias

I Tambem conhecido comoI Algoritmo de roteamento Bellman-Ford distribuıdoI Algoritmo de roteamento da ARPANET ate 1979I Internet: RIP e famılia

I FuncionamentoI Cada roteador mantem um vetor com distancias a cada destino

da redeI A cada T segundos, roteador troca com cada vizinho uma lista

dos atrasos estimados para cada destino

20/52

A B C D

EF

G H

IJ K L

P/ABCDEFGHIJKL

A0

1225401423181721092429

I243618270720312000112233

H203119083019060014072209

K212836242240311922100009

J Linha08 A20 A28 I20 H17 I30 I18 H12 H10 I00 –06 K15 K

JAe

08

JIe

10

JHe

12

JKe

06

Vetores recebidos de vizinhos de J

Nova tabela de J

T (J,X ) =min{T (J,V )+T (V ,X )}

21/52

Problema da contagem para o infinito

I Convergencia e o ponto de definicao das melhores rotasI Roteamento por vetores de distancias tem convergencia lenta

I Resposta rapida as boas notıciasI Resposta lenta as mas notıcias

Calculo de distancia para A:

A B C D E

∞ ∞ ∞ ∞ Entra na rede

1 ∞ ∞ ∞ 1 troca

1 2 ∞ ∞ 2 trocas

1 2 3 ∞ 3 trocas

1 2 3 4 Converge

A B C D E

1 2 3 4 “A” falha

3 2 3 4 1 depois

3 4 3 4 2 depois

5 4 5 4 3 depois

5 6 5 6 Continua...

22/52

Roteamento pelo estado do enlace

I Em ingles, link state routingI Variantes atuais:

I DECnet/OSI Intermediate System-Intermediate System (IS-IS)I IEFT Open Shortest Path First (OSPF), baseado no IS-IS

I Cinco partes:

1. Descobrir seus vizinhos e aprender seus enderecos de rede2. Atribuir a distancia (metrica de custo) para cada vizinho3. Construir pacote para contar o que aprendeu4. Enviar esse pacote e receber pacotes similares de outros

roteadores5. Computar o caminho mais curto para cada outro roteador

I Cada roteador tem informacao completa da topologia, entaousar algoritmo de menores distancias de Dijkstra

23/52

Aprendizado de vizinhos e atribuicao de distancia

I Envio de pacote especial HELLO

I Vizinhos respondem com o seu proprio nome (deve ser unico)I Atribuir distancias

I Em LAN: distancia inversamente proporcional a largura debanda

I Em WAN: usar o atraso obtido com o tempo de viagem de idae volta

A

B

C

D E

F

G I

H

LAN

24/52

Construcao de pacote para contar o que aprendeu

I Pacotes de estado de enlaceI Contem:

I Identidade do transmissorI Numero de sequencia de 32 bitsI Idade (tempo de vida)I Lista de vizinhos

I Construcao periodica ou quando algo importante da redemuda

A

B C

D

FE

4

2

3

7

8

5

1

6

ASeq.

Idade

B 4

E 5

BSeq.

Idade

A 4

C 2

F 6

25/52

Distribuicao de pacotes de estado de enlace

I Funcionamento basico: floodingI Guarda pacotes recebidos em uma tabelaI Decrementa tempo de vida de pacotes periodicamenteI Descarta pacotes ja vistos (pela seq.) ou tempo 0I Ao receber novo pacote, espera por novos pacotes antes de

repassarI Par de flags por enlace (no exemplo, para A, C e F)

I Flags de envio: envio de pacote por aliI Flags de reconhecimento: reconhecimento por aliI Pacote vindo por A, e enviado para C e F e reconhecido em A

Fonte Seq. Idade A C F A C FA 21 60 0 1 1 1 0 0F 21 60 1 1 0 0 0 1E 21 59 0 1 0 1 0 1C 20 60 1 0 1 0 1 0D 21 59 1 0 0 0 1 1

Tabela: Buffer de pacotes para o roteador B. 26/52

A

B C

D

FE

4

2

3

7

8

5

1

6

BSeq.

Idade

A 4

C 2

F 6

Roteador B Envio ACKFonte Seq. Idade A C F A C F

A 21 60 0 1 1 1 0 0F 21 60 1 1 0 0 0 1E 21 59 0 1 0 1 0 1C 20 60 1 0 1 0 1 0D 21 59 1 0 0 0 1 1

I Se pacote chega de E por A e F , deve ser repassado para CI Se pacote para C chega de F antes de ser repassado, tabela e

alterada para ACK para F e nao enviar para F27/52

Computacao de novas rotas

I Esperar a tabela de pacotes de estado de enlace completar

I Usar algoritmo de menor caminho de Djkstra em cadaroteador

I Saıda do Djkstra indica o caminho para cada destino

28/52

Detalhes sobre roteamento por estado de enlace

I Uso de memoria e proporcional ao numero de destinos

I Custo computacional Djkstra para pesos positivosO((E + V ) logV ), onde E e o numero de enlaces e V onumero de destinos

I Base do IS-IS e OSPF

I Dependem de hardware confiavel

I Intolerante a falhas

29/52

Roteamento hierarquico

I Redes grandes tem muitos roteadores/destinosI Falta memoriaI Uso excessivo de CPU

I Delimitacao de regioes

Region 1 Region 2

Region 3 Region 5Region 4

1B

1A

1C

2A 2B

2C

5B 5C5A

5E5D

2D

4A

4B 4C

3A

3B

1B 1

1C 1

1B 2

1B 3

1B 3

1B 4

1C 3

1C 2

1C 3

1C 4

1C 4

1C 4

1C 5

1B 5

1C 6

1C 5

– –1A

1C

2A

2B

2C

2D

3A

3B

4A

4B

4C

5A

5B

5C

5D

5E

1B

Line HopsDest.

Full table for 1A

1A

1C

2

3

4

5

1B

Line HopsDest.

Hierarchical table for 1A

1B 1

1C 1

1B 2

1C 2

1C 3

1C 4

– –

Figure 5-14. Hierarchical routing.

30/52

Roteamento broadcast

I BroacastI Envio de pacote para todos os destinos

I TecnicasI Um pacote para cada destinoI FloodI Repasse pelo caminho reverso (reverse path forwarding)

I Somente aceita repasse se caminho e aquele que costuma virpacotes

I Arvore geradoraI Evita loops mas exige informacao global

31/52

Roteamento multicast

I MulticastI Envio de pacote para grupos de destinos (jogos, vıdeos)

I Criacao de grupos: uso de enderecos multicastI Transmissao pode depender da densidade do grupo

I Grupo e denso se muitos destino estao na mesma regiao darede

I Grupo nao e denso se destinos estao em regioes distintas

I TransmissaoI Broadcast com arvore geradora com podaI Quando roteador receber pacote multicast, mas nenhum de

seus hosts tiver interesse, envia pacote de podaI Necessario armazenamento de 1 arvore por grupo multicast

32/52

Exemplo multicast

I Multicast via UDPI Enderecos multicast estao entre 224.0.0.0 e 239.255.255.255

I Reservados: de 224.0.0.0 ate 224.0.0.255 (Local NetworkControl Block)

I Locais: de 239.0.0.1 ate 239.255.255.255

I Usaremos 239.0.0.1 para endereco do grupo

I Porta 6000

33/52

Roteamento para hosts moveis

I Um host movel pode estar em diferentes lugares emmomentos distintos

I Para enviar pacote e necessario primeiro descobrir onde hostesta

I Nao e possıvel atualizar topologia toda vez que um host semove

I Objetivo: manter endereco de rede enquanto camadasinferiores mudam

I Suposicao simplificadora:I Cada host tem uma localidade de origem fixaI Sempre e possıvel enviar pacotes para essa localidadeI Um agente home atende pelo host na localidade de origemI Agente home repassa pacote para a localidade atual do host

movel

34/52

Roteamento para hosts moveis

TransmissorAgente noenderecohome

Dispositivo movel1:

avisa

ende

reco

atua

l

2: envia para endereco home

3:tu

nel

para

ende

reco

atua

l

4:responde

aotransm

issor

5:tunel para

enderecoatual

1. Enviar endereco atual para agente home

2. Fazer tunel para cuidador do endereco

3. No tunel a transmissao pode ser direta35/52

Comutacao rapida de pacotes

Pacoteschegando

Mecanismode

roteamento

Comutador

Escalonador

Pacotesredirecionados

I Um comutador de pacotes consiste deI Mecanismo de roteamento / tabela de consultaI Um escalonador/planejador de comutacoesI Malha de comutacao/switch (circuito de chaveamento)

I Mecanismo de roteamento consulta por endereco no pacotena tabela de roteamento e determina qual porta de saıdaenviar o pacote

I O pacote e marcado com uma tag indicando numero da portade saıda

I Roteador usa a tag para enviar o pacote na porta de saıda certa

36/52

Primeira geracao de roteadores

I Computador com multiplas interfaces de rede (line cards)I Usa Buffers de entrada e saıda para cada interfaceI CPU alterna atencao entre as interfaces e processa os pacotesI Desempenho e limitado pelo CPU e pela comunicacao entre

interfaces e CPUI Exemplos

I Pontes (bridges) Ethernet (camadas fısicas e enlace)I Junta dois segmentos de rede em uma so

37/52

Segunda geracao de roteadores

I As interfaces (line cards) fazem boa parte do processamentoI Consulta em tabela de roteamentoI Buffer de pacotesI Envio de pacotes para a porta apropriada

I Uso de barramento para comunicacao com CPU

I Vantagens: remocao de gargalos de CPU e memoria principal

I Desvantagem: desempenho limitado pela velocidade dobarramento

I ExemploI Roteador Cisco 7500 series (1984-1995)

38/52

Terceira geracao de roteadores

I Substituicao de barramentopor malha deroteamento/rede deinterconexao (circuitodedicado)

I Desempenho depende damalha de roteamento, masalivia gargalo debarramentos comuns

I Redes BanyaI Cisco 12000: comutacao

em 60Gbps

39/52

Multilayer Switch Cisco 6509: barramento compartilhado epor malha

Figura: ”Cisco 6509”by MrChrome (talk) (Uploads) - Own work by the original uploader. Licensed underCreative Commons Attribution 3.0 via Wikimedia Commons -http://commons.wikimedia.org/wiki/File:Cisco_6509.JPG#mediaviewer/File:Cisco_6509.JPG

40/52

Exemplo de roteador: Cisco 3745

41/52

Controle de congestionamento

I Pacotes demais na rede causam atrasos e perdasI Em colapso, pacotes podem

I perder utilidadeI ser retransmitidosI ser descartados

Inıcio docongestionamento

Colapso

Desejavel

Ideal

Carga oferecida(pacotes/segundo)

Car

gatr

ansm

itid

au

til

(pac

otes

/seg

un

do)

Capacidadeda rede

(0,0)

42/52

Controle de congestionamento

I Evitar congestionamento quando possıvel

I Roteadores com pouca memoria ou lentos podem causarcongestionamento

I Muita memoria em roteador lento pode causar colapso da rede

I Se uma parte da rede esta congestionada, rotas alternativaspodem ser afetadas

I Um bom controle de fluxo entre hosts e importante paraevitar congestionamento

I Um host de 100Gbps deve controlar envio para um host de1Gbps

I Solucao para controle de congestionamento e de fluxoI Contratar mais linhas de transmissaoI Ligar novos roteadoresI Fazer hosts irem mais devagar (pedir ou obrigar)I Planejar para trafego periodicoI Controle de admissao para trafego em circuitos

43/52

Abordagens para controle de congestionamento

1. Provisionamento de redesI planejamento e insercao de equipamentos sob demandaI administracao ao longo de meses

2. Roteamento adaptavel ao trafegoI caminhos podem mudar de acordo necessidade de clientes

3. Controle de admissaoI novas conexoes podem ser recusadas

4. Regulacao de trafego (traffic throttling)I Controle de quanto e quando hosts podem transmitirI Aviso de congestionamento eminente

5. Descarte de cargaI Descarte de pacotes mais novos (vinho) ou mais velhos (leite)

44/52

Traffic throttling : Explicit Congestion Notification (ECN)

I Notificacao explıcita de congestionamento

I Quando receptor percebe congestionamento, avisa transmissor

I Usado na Internet

I Dois bits do cabecalho IP para indicar congestionamento

I Roteador congestionado marca pacote

I Receptor avisa transmissor do congestionamento

I Alternativa: choke packet

Host Host

PacoteRoteadorcongestionado

Pacotemarcado

Noti�cação explícita de congestionamento

Sinal de congestionamento

45/52

Descarte de pacotes (load shedding)

I Para transmissao de arquivos: descarte dos mais recentes

I Para transmissao multimıdia: descarte dos mais velhos

I Marcacao de importancia/tipo do pacote

I Descarta de pacotes de acordo com a classe de importancia

I Opcao: descarte aleatorio

46/52

Qualidade de servico e Traffic Shaping

Aplicacao Largura de banda Latencia Jitter PerdaEmail Baixa Baixa Baixa MediaWeb Media Media Baixa Media

Terminal remoto Baixa Media Media MediaVideoconferencia Alta Alta Alta Alta

Tabela: Exigencia de QoS. Jitter: desvio padrao do tempo de entrega.

I Traffic shaping: modulacao do trafegoI Algoritmo do balde com furo: taxa de saıda constante maxima

(furo no balde)I Balde representa buffer, se pacote nao cabe no balde e

descartadoI Opcao: so enviar quando balde chegar em um determinado

nıvelI Possıvel fazer de acordo com aplicacao (exemplo BitTorrent)

I Balde sem furo: sem limite explıcito de taxa de saıda maximaI Deteccao de traffic shaping:

http://broadband.mpi-sws.org/transparency/bttest.php

47/52

Roteamento e camada de rede na Internet

I Internet Protocol v4 e v6I Roteamento hierarquico em dois nıveis

I Open Shortest Path First (OSPF): Intra routingI Usa estado de enlaces

I Routing Information Protocol (RIP): Intra routingI Usa vetor de distancias

I Border Gateway Protocol (BGP): InternetworkingI Roteamento entre sistemas autonomosI Variante de vetor de distancias

I Network Address Translation

I Gerenciamento da camada de rede com ICMP

48/52