Curso de Redes de Computadores - angel.acmesecurity.orgadriano/redes/2011/net-adr-2011... · Executar algoritmos e protocolos de roteamento • RIP, OSPF, BGP, dentre outros

UNESP - IBILCE - SJRP - Curso de Redes de Computadores Capítulo 4

Prof. Dr. Adriano Mauro Cansian 1

unesp - IBILCE - SJRP

1

Curso de Redes de Computadores

Adriano Mauro Cansian

[email protected]

Capítulo 4

Camada de Rede


2

Capítulo 4: Camada de Rede

Metas:   Entender os princípios

em que se fundamentam os serviços de rede:   Roteamento

•  seleção de caminhos.

  Escalabilidade.

  Implementação na Internet.

Veremos:   Serviços da camada de rede.   Princípio de roteamento.   Roteamento hierárquico.

  AS

  Endereços IP.   Protocolos de roteamento da

Internet.   Dentro de um domínio.   Entre domínios

  Como funciona um roteador.




3

Funções da camada de rede (1)

 Prover transporte de pacotes fim-a-fim.   Ligar hosts com hosts.

•  (Lembrar do exemplo dos primos que moram em casas em estados diferentes e querem trocar cartas entre si).

 Exigências que devem ser atendidas:   Suportar pilhas de protocolos inferiores diferentes.

  Admitir camadas inferiores heterogêneas.

  Admitir organização em múltiplos domínios.

 Requisitos ainda em desenvolvimento:   Qualidade de serviço (QoS).

  Mobilidade total (roteamento wireless).


4

Funções da camada de rede (2)   Missão: Transportar pacotes do

host emissor ao receptor.

  Protocolo da camada de rede: presente em hosts e routers.

Três funções importantes:

  Determinação do caminho: rota seguida por pacotes da origem ao destino. Algoritmos de roteamento.

  Comutação: mover pacotes dentro do roteador, da entrada até a saída apropriada.

  Estabelecimento da chamada: algumas arquiteturas de rede requerem determinar o caminho antes de enviar os dados.

rede

enlace física

rede

enlace física

rede

enlace física

rede

enlace física

rede

enlace física

rede

enlace física

rede

enlace física

rede

enlace física

aplicação transporte

rede enlace física


rede enlace física

Note que os roteadores intermediários não

precisam das camadas superiores da pilha TCP/IP

Não acontece na Internet




Funções da camada de rede (3) • Como já dito: transportar pacotes

entre hosts (origem-destino).

• No lado transmissor: encapsula os segmentos em datagramas.

• No lado receptor: entrega os segmentos à camada de transporte (desencapsula).

• Roteador examina campos de cabeçalho em todos os datagramas IP que passam por ele. • É “stateless”.


Funções-chave da camada de rede:

 Roteamento:   Determinar a rota a ser seguida pelos pacotes.

 Comutação ou repasse:   Mover pacotes dentro do roteador, da entrada para a

saída apropriada.

 Algoritmos de roteamento - analogia:   Roteamento: processo de planejar a viagem para

saber qual caminho seguir.

  Comutação: processo de passar por um único cruzamento.




Interação entre roteamento e comutação (repasse)


8

Modelo de serviço de rede

  O modelo de serviço de rede define as características da transmissão de dados fim-a-fim, entre uma borda da rede e a outra borda.

  Ou seja, entre os sistemas emissor e receptor.

? ? ?

Circuito virtual ou

Datagrama?

A abstração mais importante provida

pela camada de rede:




9

Introdução à comutação (1)

 Comutação de circuitos:   Paradigma: o sistema telefônico que usa circuito

dedicado fim-a-fim.

 Comutação de pacotes:   Paradigma: sistema de correios, onde a

correspondência é re-roteada em vários pontos.  Comparando os serviços na camada de rede e de

transporte:   Rede: entre dois hosts.   Transporte: entre dois processos (fim a fim).


10

Circuitos virtuais

  Caminho origem-destino se comporta como um circuito telefônico.   Em termos de desempenho.

  Há o estabelecimento de cada chamada antes do envio dos dados.

  Cada pacote tem identidade de CV.   E não endereços origem/destino.

  Cada comutador mantém uma tabela do estado dos circuitos.

  Após a utilização, o CV deve ser desfeito.




11

Circuitos virtuais: protocolos de sinalização

  Usados para estabelecer, manter ou destruir C.V.

  Exemplos: ATM, frame-relay e X.25.   Pergunta: é possível montar uma camada de rede sobre

outra camada de rede ?


rede enlace física


rede enlace física

1. inicia chamada 2. chegada de chamada 3. chamada aceita 4. conexão completa

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


12

Rede de datagramas: o modelo da Internet

  Não requer estabelecimento de chamada na camada de rede

  Não guarda estado sobre transmissões.

  Não existe o conceito de “conexão” na camada de rede.

  Pacotes são roteados usando endereços de destino.   “Carimbar” o pacote com endereço, e enviar.

  Dois pacotes podem seguir caminhos diferentes até destino.


rede enlace física


rede enlace física

1. envia dados 2. recebe dados




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

Considerando o espaço de endereçamento no IPv4 (atual) existem 4 bilhões de entradas possíveis

Tabela de comutação ou repasse


Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 Qualquer outro 3

11001000 00010111 00011000 10101010

Exemplos

11001000 00010111 00010110 10100001 Qual interface?

Qual interface?

Decisão de repasse




11001000 00010111 00011000 10101010 !

Exemplos

11001000 00010111 00010110 10100001 ! Qual interface?

Qual interface?

Decisão de repasse

Regra do maior prefixo: o prefixo mais longo na tabela de roteamento tem precedência na decisão.

1

0

Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 Qualquer outro 3


O que há dentro do roteador ?

Visão geral da arquitetura de um roteador

16




17

Visão Geral de Arquitetura de Roteadores   Duas funções fudamentais de roteadores:

  Executar algoritmos e protocolos de roteamento •  RIP, OSPF, BGP, dentre outros.

  Repassar(*) datagramas da interface de entrada para a saída.

(*) Repassar = Comutar


18

Funções da Porta de Entrada

Comutação descentralizada:   Verifica o destino do datagrama, e procura

qual porta de saída, usando tabela de rotas na memória da porta de entrada.

  Meta: fazer processamento da porta de entrada na ‘velocidade da linha’.

  Formação de Filas: acontece 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: Exemplo: Ethernet

(veremos no capítulo 5)




Estruturas de comutação

19

Dentro do roteador existe uma das 3 estruturas principais de comutação:


20

Três tipos de matriz de comutação serão vistas em seguida




21

Comutação via Memória   Presentes nos roteadores da primeira geração:   Pacote é copiado para a memória pelo processador do sistema ocorre um gargalo: processamento único.

  Depois é lido para fazer o repasse.

  A velocidade limitada pela largura de banda da memória.   2 travessias do barramento por datagrama (entra e sai na memória).

Porta de Entrada

Porta de Saída

Memória

Barramento do Sistema Roteadores atuais / modernos:

  Colocam processador da porta de entrada:

  Consulta tabela e copia para a memória.


22

Comutação via Barramento

  Datagrama viaja 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 a 10 Gbps são comuns.   Velocidade suficiente para roteadores de acesso e

corporativos (mas não de backbone).




23

Comutação cross-bar (Rede ou matriz de Interconexão)

  Supera limitações dos barramentos.   Matrizes de interconexão desenvolvidas

inicialmente para interligar processadores num multiprocessador (Redes Banyan).

  Consiste de 2n barramentos, conectando n portas de entrada com n portas de saída.

  Portas podem “conversar” ao mesmo tempo na matriz.

  Taxas atuais variam de 100 a 200 Gbps pela rede de interconexão.   Indicado para roteadores de backbone.


cross-bar

24

Portas podem “conversar” ao mesmo tempo na matriz.




25

Porta de Saída

  Buffers necessários quando datagramas chegam da matriz de comutação mais rápido do que a taxa de transmissão do enlace.

  Eventualmente há disciplina de escalonamento: escolha dos datagramas enfileirados para transmissão.   TOS no datagrama IP (será discutido mais adiante).


26

Filas na Porta de Saída

  Usa buffers quando taxa de chegada através do comutador excede taxa de transmissão de saída.

  Ocorre enfileiramento (atraso) e perdas devido ao transbordo do buffer da porta de saída.




27

Filas na Porta de Entrada: Bloqueio Head-of-Line (HOL)

  Se matriz de comutação é mais lenta do que a soma das portas de entrada juntas → pode haver filas nas portas de entrada.

  Bloqueio HOL: datagrama na cabeça da fila impede outros na mesma fila de avançarem.

  Acontecem retardo de enfileiramento e perdas devido ao transbordo do buffer de entrada!


Bloqueio HOL

28

1

2

A

B

1 – Pacote vermelho está sendo enviado para porta A. 2 – Pacote vermelho também quer ir para A, mas esta impedido até que 1 termine. 2 – Pacote verde quer ir para B que está livre, mas está impedido até que o pacote vermelho da sua frente seja enviado.




A Camada de Rede na Internet

29


A Camada de Rede na Internet

30

Tabela de rotas

Prot. de roteamento •  Escolha de caminhos

•  RIP, OSPF, BGP

Protocolo IP •  Endereçamento

•  Formato dos datagramas •  Tratamento de pacotes

Protocolo ICMP •  Aviso de erros

•  Sinalização de rotas

Camada de Transporte: TCP, UDP

Camada de enlace (datalink)

Camada física

Cam

ada

de

rede




31

Endereçamento IP


32

Endereçamento IP (1)

 Um endereço IP consiste de 32 bits, divididos em dois campos:

•  Número de rede (network number).

•  Número do host (host number).

 Ou três campos... (subneting ou sub-redes) •  Número de rede (network number).

•  Número de sub-rede (subnet number).

•  Número de host (host number).




33


  Os endereços IP são escritos em notação decimal:

xxx . yyy . zzz . kkk

223 . 1 . 1 . 1

11011111 00000001 00000001 00000001

  Grupo decimal (entre os pontos decimais) é conhecido como um “octeto”

  é o decimal equivalente aos 8 bits do endereço binário.

  “Endereço de 4 Octetos” (4 quatro grupos de 8 bits).

  Exemplos:

•  68.18.1.36 o número decimal 68 representa o campo de rede do endereço.

•  137.4.80.1 o número decimal 137.4 representa o campo de rede do endereço.

(alguns endereços são reservados. Serão tratados mais adiante).


Endereço IP – notação decimal

34

10000000 00001010 00000010 00011110

2726252423222120 2726252423222120 2726252423222120 2726252423222120

27=128 23+21=10 21=2 24+23+22+21=30

128.10.2.30notação decimalpontuada

notaçãobinária




Endereços de host e de rede

35

Identificador darede

Identificador dohost

Endereço IP de 32 bits

REDE

internet

REDE REDE

REDE

hosts com omesmoidentificador derede.

hosts comidentificadores

de rededistintos.

host


36


  Endereço IP: identificador de 32-bits para interface de estação ou 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, e 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.2 223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 1 1




37


  Endereço IP:   Uma parte de rede

•  (bits de mais alta ordem).

  Uma parte de estação •  (bits de mais baixa ordem).

  O quê é uma rede 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.2 223.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


38


Como achar as redes?   Dissociar 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.2 223.1.2.1

223.1.2.6

223.1.3.2 223.1.3.1

223.1.3.27

223.1.1.2

223.1.7.0

223.1.7.1 223.1.8.0 223.1.8.1

223.1.9.1

223.1.9.2

Sistema interligado consistindo de

seis redes




39

Classes de redes (1)

0 rede estação

10 rede estação

110 rede estação

1110 endereço multiponto

A

B

C

D

classe 1.0.0.0 to 127.255.255.255 128.0.0.0 to 191.255.255.255 192.0.0.0 to 223.255.255.255 224.0.0.0 to 239.255.255.255

32 bits

Dada a noção de “rede”, vamos examinar endereços IP: Endereçamento “baseado em classes”: denominação antiga (em desuso) aqui só por motivos didáticos / históricos.


40

Classes de redes (2) 32 Bits

Range of host addresses

1.0.0.0 to 127.255.255.255

128.0.0.0 to 191.255.255.255

192.0.0.0 to 223.255.255.255

224.0.0.0 to 239.255.255.255

240.0.0.0 to 247.255.255.255

Class

0 Network Host

10 Network Host

110 Network Host

1110 Multicast address

11110 Reserved for future use

A

B

C

D

E

Para um endereço classe A o primeiro bit é sempre 0 28-1 redes

Para um endereço classe B os dois primeiros bits são 10 216-2 redes

Para um endereço classe C os três primeiros bits são 110 224-3 redes

Endereçamento “baseado em classes”: denominação antiga (em desuso). Consta aqui só por motivos didáticos / históricos.




41

Classes de redes (3)   Endereços Classe A ( “/8”)

  Atribui 8 bits para o campo de rede e um total de 24 bits para o restante do endereço.

  Esta classe pode endereçar quase 17 milhões de diferentes nós em uma rede. Um endereço classe A é usado para redes muito grandes.

  Endereços Classe B ( “/16”)

  Um endereço classe B atribui 16 bits para o campo de rede e um total de 16 bits para o restante do endereço.

  Isto permite endereçar cerca de 65.000 diferentes nós em uma rede.

  Endereços Classe C ( “/24”)

  Um endereço classe C atribui 24 bits para o campo de rede e 8 bits para o resto do endereço.

  Isto permite endereçar 254 diferentes nós na rede.

Endereçamento “baseado em classes”: denominação antiga (em desuso). Consta aqui só por motivos didáticos / históricos.


42

parte de estação

Endereçamento IP: CIDR

 Endereçamento baseado em classes:   Uso ineficiente e esgotamento do espaço de endereços.

  Exemplo: rede da classe B aloca endereços para 65.000 estações, mesmo se houver apenas 2.000 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 é número de bits na parte de rede do endereço.

11001000 00010111 00010000 00000000

parte de rede

200.23.16.0/23




43

Endereços reservados de REDE e BROADCAST (1)

Endereços de REDE:

•  Para se referir a uma rede os bits do campo de host são colocado como 0.

  O endereço /16 identificado como 137.4.0.0 refere-se à rede 137.4. *.*

  O endereço /24 identificado como 200.17.28.0 refere-se à rede 200.17.28.*


44

Endereços reservados de REDE e BROADCAST (2)

Endereços de broadcast   Um endereço que se refere a todos os hosts em uma rede é

um endereço de broadcast.

•  Para se referir a todos os nós de uma rede em particular, os bits de host são ajustados para 1.

  Exemplos:

–  O endereço 15.255.255.255 refere-se a todos os nós da rede 15. /8 .

–  O endereço 200.17.28.255 refere-se a todos os nós da rede 200.17.28 / 24




45

Subneting e subnetmask (1)

Máscaras de sub-rede (subnetmasking):

 Máscara de sub-rede → diz para um roteador ou software específico o comprimento dos campos de rede e de host.

 Os administradores podem definir o campo de subnetmask de modo a dividir uma rede em sub-redes menores, de acordo com a conveniência necessária.

 O “/” indica a máscara aplicada.



46




47


Funcionamento e obtenção da máscara:  A parte do endereço IP correspondente à

identificação do host (ou seja, o hostid) é dividida:

•  Um bit ligado (1) indicará que aquele bit deverá ser interpretado como parte do número de sub-rede.

•  Um bit desligado (0) indicará que aquele bit deverá ser interpretado como parte do número de identificação de hostid.

  Em seguida cada grupo de 8 bits é convertido para seu decimal equivalente, indicando a subnetmask.


48





49


200.17.28.66/26

IP Address subnetmask Hostid Binário End. Sub-rede Interpretação

200.17.28.66 255.255.255.192 66 = 01000010

(1ª rede, host 2)

200.17.28.64

(01000000)

Host 2 (000010) nasubrede 200.17.28.64

200.17.28.135 255.255.255.192 135 = 10000111

(2ª rede, host 7)

200.17.28.128(10000000)

Host 7 (000111) nasubrede200.17.28.128

200.17.28.135/26


50





Subnetmask: tabelinha

51


Endereços reservados

 Ou endereços privados (categoria 1)  1 REDE /8:

  10.0.0.0 a 10.255.255.255

 16 REDES /16:   172.16.0.0 a 172.31.255.255

 256 REDES /24:   192.168.0.0 a 192.168.255.255

52




Endereços reservados

  Não podem ser atribuídos a nenhuma estação:   127.0.0.1:

•  Endereço de Loopack

  nnn.nnn.nnn.255: •  BroadCast : todos os bits de host ajustados para 1. •  n.n.n.255 – Ex: BroadCast para rede /24

•  n.n.255.255 – Ex: BroadCast para rede /16

•  n.255.255.255 – Ex: BroadCast para rede /8

  nnn.nnn.nnn.000: •  Network: todos os bits de host ajustados para 0. •  n.n.n.0 – Ex: End. Rede para rede /24

•  n.n.0.0 – Ex: End. Rede para rede /16

•  n.0.0.0 – Ex: End. Rede para rede /8   0.0.0.0:

•  Endereço de Inicialização (DHCP)

53


54

Divisão de endereços IP: Como subdividir uma rede (parte do endereço de rede):   Alocação a partir do espaço de endereços do provedor IP.

  Provedor pode subdividir sua alocação: digamos que ele tem um “/20”, então pode entregar “/23” aos seus clientes:

Bloco do 11001000 00010111 00010000 00000000 200.23.16.0/20 provedor Organizaçã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




55

Endereçamento hierárquico: agregação de rotas

“Mande-me qualquer coisa com endereços que começam com 200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Provedor A

Organização 0

Organização N7 Internet

Organização N1

Provedor B “Mande-me qualquer coisa com endereços que começam com 199.31.0.0/16”

200.23.20.0/23 Organização N2

. . .

. . .

Endereçamento hierárquico permite anunciar eficientemente informação sobre rotas:

199.31….. /16

Mega-empresa A


56

Endereçamento hierárquico: rotas mais específicas • Organização 1 precisou mudar de provedor ou emoresa, mas precisa levar os Ips:

• Provedor B agora anuncia uma nova rota mais específica para a Organização 1.

“mande-me qq coisa com endereços que começam com 200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Provedor A

Organização 0

Organização 7 Internet

Organização 1

Provedor B “mande-me qq coisa com endereços que começam com 199.31.0.0/16 ou 200.23.18.0/23”

200.23.20.0/23 Organização 2

. . .

. . .

199.31….. /16 Mega-empresa A




57

Endereçamento hierárquico: rotas mais específicas

“mande-me qq coisa com endereços que começam com 200.23.16.0/20”

200.23.16.0/23

200.23.18.0/23

200.23.30.0/23

Provedor A

Organização 0

Organização 7 Internet

Organização 1

Provedor B “mande-me qq coisa com endereços que começam com 199.31.0.0/16 ou 200.23.18.0/23”

200.23.20.0/23 Organização 2

. . .

. . .

Quando outros roteadores virem o anúncio dos blocos de endereço 200.23.16.0/20 e 200.23.18.0/23 e quiserem rotear para um endereço no bloco 200.23.18.0/23 eles vão usar a regra de ajuste ao prefixo mais longo e rotear em direção endereço de rede maior (mais específico) que casa com o endereço de destino.

199.31….. /16 Mega-empresa A


58

Endereçamento IP - Governança

Como um provedor IP consegue um bloco de endereços?

ICANN: Internet Corporation for Assigned

Names and Numbers (http://www.icann.org)

  Aloca endereços.

  Gerencia DNS.

  Aloca nomes de domínio e resolve disputas.   No Brasil, estas funções foram delegadas ao Registro Nacional

(http://registro.br), sediado na FAPESP (SP), e comandado pelo Comitê Gestor Internet BR (CG-Br)




Encaminhamento de datagramas

59


60

Envio de datagramas

 Para transferir um datagrama o emissor:

1.  Encapsula o datagrama num quadro da camada de enlace,

2. Mapeia o endereço IP de destino em um endereço físico e,

3.  Para entrega-lo, usa o hardware da rede local.   Camada Datalink (MAC).




61

Encaminhamento direto

 Emissor: (1.) extrai a parte da rede do endereço IP de destino, e (2.) compara à parte de rede de seu próprio endereço.   Se houver correspondência, significa que o

datagrama pode ser enviado diretamente.

 Encaminhamento direto é sempre o passo final de qualquer transmissão de datagrama.   Sempre o roteador final se conectará diretamente

à mesma rede física do destino.

  Chamado de “último passo da rota” (last hop).


62

Encaminhamento indireto

 Quando um host deseja enviar algo para outro host encapsula o datagrama, e o envia ao roteador mais próximo (gateway de saída).

 O datagrama passa de roteador a roteador, até chegar a um que possa entrega-lo diretamente.

 Quando um frame chega no roteador o software do roteador extrai o datagrama encapsulado, e seleciona o próximo roteador ao longo do caminho em direção ao destino.




63

rede dest. próx. rot. N enlaces

223.1.1 1 223.1.2 223.1.1.4 2 223.1.3 223.1.1.4 2

Enviando um datagrama da origem ao destino (1)

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.2 223.1.3.1

223.1.3.27

A

B E

Campos misc

end. IP origem

end. IP dest dados

  Datagrama permanece inalterado, enquanto passa da origem ao destino.

tabela de rotas em A


64


223.1.1 1 223.1.2 223.1.1.4 2 223.1.3 223.1.1.4 2

Seja um datagrama IP originando em A, e endereçado a B:

  A procura endereço de rede de B.

  A descobre que B é da mesma rede que A (usando o prefixo do endereço).

  Camada de enlace de A envia o datagrama diretamente para B num frame da rede local.

  B e A são chamados de “diretamente conectados”.


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.2 223.1.3.1

223.1.3.27

A

B E

campos misc 223.1.1.1 223.1.1.3 dados




65


223.1.1 1 223.1.2 223.1.1.4 2 223.1.3 223.1.1.4 2

Seja origem A, destino E:   Procura endereço de rede de E.

  E está numa rede diferente   A e E não diretamente conectados.

  Tabela de rotas: próximo roteador na rota para E é 223.1.1.4 .

  Camada de enlace envia datagrama ao roteador 223.1.1.4 num frame da camada de enlace.

  Datagrama chega a 223.1.1.4

  e então segue…


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.2 223.1.3.1

223.1.3.27

A

B E

campos misc 223.1.1.1 223.1.2.2 dados


66

dest. rot. N enl. interface

223.1.1 - 1 223.1.1.4 223.1.2 - 1 223.1.2.9

223.1.3 - 1 223.1.3.27

rede próx.

Chegando a 223.1.1.4, destinado a 223.1.2.2

  Procura endereço de rede de E.

  E fica na mesma rede que a interface

223.1.2.9 do roteador.   Roteador e E estão diretamente

conectados.

  Camada de enlace envia datagrama para 223.1.2.2 dentro de frame de camada de enlace via interface 223.1.2.9

  Datagrama chega a 223.1.2.2


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.2 223.1.3.1

223.1.3.27

A

B E

Campos misc 223.1.1.1 223.1.2.2 dados




Datagrama IP

Especificações do Protocolo

67


68

Formato do datagrama IP (1)

Version IHL Type of service Total length

Identification

Time to live Protocol

Fragment offset

Header checksum

Source address

Destination address

Options (0 or more words)

D F

M F

32 Bits




69


ver comprimento

32 bits

dados (comprimento variável,

tipicamente um segmento TCP ou UDP)

ident. 16-bits

checksum Internet

sobre- vida

endereço IP de origem 32 bits

número da versão do protocolo IP

comprimento do cabeçalho em

palavras de 32 bits

TTL - Time to Live. número máximo

de enlaces restantes

(decrementado a cada roteador)

para fragmentação e remontagem

comprimento total do datagrama (em bytes)

protocolo da camada superior ao qual

entregar os dados

comp. cab

tipo de serviço

“tipo” dos dados (TOS)

bits início do fragmento

camada superior

endereço IP de destino 32 bits

Opções (se houver) p.ex. temporizador, registrar rota seguida, especificar lista de roteadores a visitar.


Adaptação a redes diferentes

70

Internet

SLIP : 256

PPP : 1500

Ethernet : 1500

ADSL: 512




71

MTU e Fragmentação

Rede 3MTU=1.500

Rede 1MTU = 1.500

Rede 2MTU=620

Host A

Host BRouter 1 Router 2

?

?

?

Um datagrama pode trafegar em muitos tipos de redes físicas à medida que se move dentro da interligação das redes até

alcançar seu destino final Como escolher um tamanho de datagrama que se encaixe no frame ?

?


72


Version IHL Type of service Total length

Identification

Time to live Protocol

Fragment offset

Header checksum

Source address

Destination address

Options (0 or more words)

D F

M F

32 Bits




73

IP: Fragmentação & Remontagem (1)   Cada enlace de rede tem uma

MTU (Maximum 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 se transforma em vários datagramas.

  São “remontados” apenas no destino final.

  Bits do cabeçalho IP são usados para identificar, ordenar fragmentos relacionados.

Fragmentação: entrada: um datagrama

grande saída: 3 datagramas

menores

remontagem


74

IP: Fragmentação & Remontagem (2)

 O IP representa o deslocamento de dados em múltiplo de 8 bytes

  Portanto, o tamanho do fragmento precisa ser um maior múltiplo de 8 possível para aquela rede.

•  Roteadores precisam aceitar datagramas até o máximo de MTUs das redes às quais se conectam. •  Hosts e roteadores devem aceitar e remontar, se

necessário, datagramas de no mínimo 576 octetos.




75


Cabeçalho do datagrama Dados 1600 octetos

Dados 2600 octetos

Dados 3

Cabeçalho do fragemento 1 Dados 1

Dados 2Cabeçalho do fragmento 2

Cabeçalho do fragmento 3

Dados 3200 octetos

Fragmento 1 (offset 0)

Fragmento 2 (offset 600)

Fragmento 3 (offset 1.200)

(a)

(b)

Fragmentos e offset : (a) Um datagrama original, levando 1.400 octetos de dados. (b) Os três fragmentos para a MTU de rede 620. Os cabeçalhos 1 e 2 possuem o conjunto de bits de “mais

fragmentos” ajustados para um. Os deslocamentos (offset) mostrados são octetos decimais; devem ser divididos por 8 para atingir o valor armazenado nos cabeçalhos do fragmento


76


ID =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 vira vários datagramas menores




77

Controle IP – Fragmentação

Identifica o datagrama Indicando que existe

mais fragmentos Indica a posição do

fragmento em relação ao datagrama


78


Indicando que não há mais fragmentos,

deste datagrama e a sua posição no datagrama final




79


Identificação do datagrama 0x749b indica o mesmo

datagrama

Indica se existe mais fragmentos para o datagrama 0x749b Indica a posição do

fragmento no datagrama 0x749b


datagramas com origem ou destino nesta rede possuem endereço

10.0.0/24 para origem, destino (usualmente)

todos os datagramas que saem da rede local possuem o mesmo e único endereço IP do NAT de origem:

138.76.29.7, números diferentes de portas de

origem.

NAT: Network Address Translation (1)

10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

rede local (ex.: rede doméstica)

10.0.0/24

restante da Internet

NAT





 Motivação: redes locais podem utilizar apenas um endereço IP:

 Não é preciso alocar uma gama de endereços do ISP: apenas um endereço IP é usado para todos os dispositivo

•  Podem-se alterar os endereços dos dispositivos na rede local sem precisar notificar o mundo exterior.

•  Pode-se mudar de ISP sem alterar os endereços dos dispositivos na rede local.

•  Dispositivos da rede local não são explicitamente endereçáveis ou visíveis pelo mundo exterior (um adicional de segurança ?).


Implementação: o roteador NAT deve:  Datagramas que saem:

  Substituir (endereço IP de origem interno, porta #) para (endereço IP válido do NAT, nova porta #).

 . . . Hosts remotos respondem usando (endereço IP do NAT, nova porta #) como endereço de destino.   Armazena na tabela de tradução do NAT: cada (endereço IP de origem interno, porta #) com o par de tradução (endereço IP do NAT, nova porta #).   Datagramas que chegam:

  substituir (endereço IP do NAT, nova porta #) nos campos de destino de cada datagrama pelos correspondentes (endereço IP de origem, porta #) armazenados da tabela NAT.





1: hospedeiro 10.0.0.1 envia datagrama

para 128.119.40, 80 2: roteador NAT substitui end. origem

do datagram de 10.0.0.1, 3345 para 138.76.29.7, 5001, atualiza a tabela

3: resposta chega endereço de destino: 138.76.29.7, 5001

4: roteador NAT substitui o endereço de destino do datagrama de 138.76.29.7, 5001 para 10.0.0.1, 3345




 • Campo número de porta com 16 bits:   60.000 conexões simultâneas com um único

endereço de LAN.

 • NAT é controverso:   Roteador: deveria processar só até a layer 3.

  Violação do argumento fim-a-fim (P2P).

  A escassez de endereços deveria ser para IPv6.

  Violação do esquema cálculo do checksum do IP.

  Algumas aplicações não funcionam com NAT




ICMP – Internet Control Message Protocol

 Parte da camada IP.

 Mecanismo de “baixo nível” para influenciar o comportamento do TCP e do UDP.   Diversas mensagens de controle, tais como:

•  Informar hosts sobre melhor rota ao destino; •  Informar problemas com uma rota;

•  Finalizar uma sessão devido a problemas na rede;

•  Relatar erros: estação, rede, porta, protocolo inatingíveis;

•  Pedido e resposta de eco e testes.

 Usado em ferramentas vitais de administração e monitoramento ping e traceroute.


ICMP

IP header (20 byte) ICMP message

Carga /conteúdo: depende do tipo e código

8-bit type 8-bit code 16-bit checksum

IP datagram




Formato da Mensagem ICMP

87

tipo código checksum

0 7 8 15 16 31

parâmetros

...................

informação


ICMP Message Types type Description

0 Echo Reply Echo Query

3 Destination Unreachable Error

4 Source Quench Error

5 Redirect Error

8 Echo Request Echo Query

9 Router Advertisement Query

10 Router Solicitation Query

11 Time Exceeded Error

12 Parameter Problem Query

13 Timestamp Request Query

14 Timestamp Reply Query

17 Address Mask Request Query

18 Address Mask Reply Reply

code Description 0 Network Unreachable 1 Host Unreachable 2 Protocol Unreachable 3 Port Unreachable 4 Fragmentation Needed and DF set 5 Source Route Failed 6 Destination Network Unknown 7 Destination Host Unknown 8 Source Host Isolated 9 Network Administratively Prohibited 10 Destination Host Administratively

Prohibited 11 Network Unreachable For TOS 12 Host Unreachable For TOS 13 Communication Administratively

Prohibited 14 Host Precedence Violation 15 Precedence Cutoff in Effect




Exemplo: ICMP Echo Request and Reply

 ICMP echo mensagem para enviar e receber pacotes específicos de “echo” entre 2 hosts

Echo data (variable length)

Type(0 or 8) Code(0)

identifier

checksum

sequence number


  O transmissor envia uma série de segmentos UDP para o destino. •  O 1o possui TTL = 1   O 2o possui TTL = 2   etc...   Usa No de porta de destino improvável (exemplo 30000)

Quando o datagrama n chega ao roteador n: • O roteador descarta o datagrama. • E envia à origem uma mensagem ICMP (type 11, code 0) • A mensagem inclui o nome do roteador e o endereço IP

• Quando a mensagem ICMP volta, a origem calcula o RTT. • O traceroute faz isso três vezes.

  Critério de interrupção: • O segmento UDP finalmente chega ao hospedeiro de destino •  O destino retorna o pacote ICMP “port unreachable”

•  (type 3, code 3)

• A origem interrompe quando recebe essa mensagem ICMP.

Traceroute e ICMP




  O transmissor envia uma série de segmentos UDP para o destino. •  O 1o possui TTL = 1   O 2o possui TTL = 2   etc...   Usa No de porta de destino improvável (exemplo 30000)

Quando o datagrama n chega ao roteador n: • O roteador descarta o datagrama. • E envia à origem uma mensagem ICMP (type 11, code 0) • A mensagem inclui o nome do roteador e o endereço IP

• Quando a mensagem ICMP volta, a origem calcula o RTT. • O traceroute faz isso três vezes.

  Critério de interrupção: • O segmento UDP finalmente chega ao hospedeiro de destino •  O destino retorna o pacote ICMP “port unreachable”

•  (type 3, code 3)

• A origem interrompe quando recebe essa mensagem ICMP.

Traceroute e ICMP


92

Interconexão de redes e roteamento




93

O problema de inter-redes (1)

 Internet = INTERNETworking   Interconexão de redes.

 Comunicação fim-a-fim sobre redes:   Em escala arbitrariamente grande.

•  Deve ser possível escalar.

  Heterogêneas. •  Diversos protocolos de enlace.

  Organizadas como federação domínios. •  Cada instituição é “dona” de uma parte da rede.


94

O problema de inter-redes (2)

  Serviços incompatíveis   Há muita variação entre os serviços de recuperação de erros,

relatórios de status, gerência de conexões, etc...

  Configurações incompatíveis   Exemplo: um domínio (A) limite pacotes a 1KB, enquanto (B)

permite 64 KB. Um pacote de (B) não consegue atravessar (A) inteiro.

  Temporização, fluxo de controle, roteamento, políticas, segurança, etc...

  Arquiteturas incompatíveis   Exemplo: SNA e DNA, IP e X.25

  Não sempre óbvio quais camadas devem ser interligadas e como.

  Mudanças rápidas em custo e desempenho   Custo de interconexão > banda.   Custo de complexidade >> equipamentos > banda.




95

Elementos de Interconexão em várias camadas:

 Repetidores na camada física (layer1).

 “Hubs” (*), pontes (bridges) e switches na camada de acesso ao meio (layer2).

 Roteadores na camada de rede (layer3).

 Gateways de aplicação (“layer 7”).

(*) Atenção: “hub” é um termo muito genérico... atenção à observação do professor...


96

Meta: determinar melhor caminho (seqüência de roteadores) pela rede, desde a origem ao destino.

protocolo de roteamento

Roteamento

Abstração de grafo para algoritmos de roteamento:

  Nós do grafo são roteadores.

  Arestas do grafo são os enlaces físicos.

  Custos do enlace: retardo, financeiro, risco, ou congestionamento.

A

E D

C B

F 2

2 1

3

1

1 2

5 3

5

  Caminho “melhor”:   Tipicamente significa

caminho de menor custo.

  Outras definições são possíveis.




Grafo: G = (N,E)

N = conjunto de roteadores = { u, v, w, x, y, z }

E = conjunto de links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z), (u,w) }

•  A abstração de grafo é útil em outros contextos de rede. •  Exemplo: P2P, em que N é o conjunto de peers e E é o conjunto de conexões TCP

Abstração em grafo


Custo do 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, ou melhor caminho possível.

Abstração do gráfico: custo

• c(x,x’) = custo do link (x,x’) • Ex: c(w, z) = 5

•  Exemplo de custo: pode ser sempre o mesmo, relativo à distância, ou então inversamente relacionado à largura de banda ou ao congestionamento.




99

Uma introdução aos algoritmos de roteamento


Tipos de algoritmos de roteamento

 Duas classificações principais.

  Quanto ao tipo da informação.

  Quanto à mudança das rotas.

 Veremos em seguida...

100




101

Classificação de Algoritmos de Roteamento (1)

Classificação 1:

Informação global ou descentralizada ? Global:

  Todos roteadores têm informações completas de topologia, distância e custos dos enlaces.

  Algoritmos de “estado de enlaces” (link state - LS).

Descentralizada:

  Roteador conhece vizinhos diretos, e custos até eles.

  Processo iterativo de cálculo, e troca de informações com vizinhos.

  Algoritmos de “vetor de distâncias” (distance vector - DV).


102

Classificação de Algoritmos de Roteamento (2)

Classificação 2: Estático ou dinâmico? Estático:

  Usado quando as rotas mudam lentamente ou raramente.   Tipicamente para sistemas de borda (edge routers) ou

que possuem um ou poucos links de entrada/saída.

Dinâmico:

  Usado quando as rotas mudam mais rapidamente.   Tipicamente para sistemas de núcleo (core routers),

com vários links e várias conexões.

  Atualização periódica automática. •  em resposta a mudanças nos custos, ou disponibilidade ou estado

(link down ou up) dos enlaces.




Algoritmos de roteamento

Introdução aos algoritmos mais usados

103


Algoritmos de roteamento

 Veremos dois algoritmos principais:   Link State e Distance Vector.

 Link state:   Informação Global.

  Algoritmo de Dijskstra

 Distance vector:   Informação Descentralizada

  Equação de Bellman-Ford.

104




105

Roteamento Link-state

Usa o Algoritmo de Dijkstra para calcular melhor caminho.   Premissa: Topologia da rede e custo de todos os enlaces

são conhecidos por todos os nós.   Implementado via “link state broadcast”.   Todos os nós têm a mesma informação.   Todos os nós têm uma visão igual e completa

da rede.   Calcula caminhos de menor custo de uma origem para

todos os outros nós destinos.   Fornece uma tabela de roteamento para aquele nó (origem).

  Convergência: após k iterações, conhece o caminho de menor custo para todos os k nós de destino.


106

Notação do algoritmo de Dijkstra

 C(i,j): custo do enlace do nó i até o nó j.   Custo é infinito se não houver ligação entre i e j.

 D(v): menor custo atual entre a origem e o destino V, até a presente iteração do algoritmo.

 p(v): Predecessor de v nó anterior (vizinho) a v ao longo do caminho de menor custo atual da origem até o destno v.   Exemplo: p(A) Lê-se: “predecessor de A” ou “passando por”.

 N’: subconjunto de nós vai formando o conj. de menor custo.   v pertence a N’ se o caminho de menor custo entre a fonte e v for

inequivocamente conhecido.




Algoritmo de Dijsktra em palavras:

 Para um determinado nó:   Iniciar só com o custo dos valores dos vizinhos diretos.

 Ir anexando, um a um, cada nó do conjunto.   Cada vez que anexar um novo nó ao conjunto, calcular

os menores caminhos conhecidos para o nó sob análise, até cada destino.

  Ou seja, cada vez que eu adiciono um nó w ao conjunto, devo obter D(v) para cada v vizinho de w, desta forma:

  D(v) = min{ D(v), D(w) + c(w,v) } •  novo custo para v é ou o velho custo para v, ou o menor

custo de caminho conhecido para w (antecessor de v) mais o custo de w a v.

107


108

Algoritmo de Dijsktra’s 1 Inicialização: 2 N’ = {u} 3 para todos os nós v 4 se v for um vizinho de u 5 então D(v) = c(u,v) 6 senão D(v) = infinito 7 8 Loop para cada nó 9 Ache w não pertencente a N’, tal que D(w) é um mínimo. 10 Adicione w a N’. 11 Atualize D(v) para cada v vizinho de w, e ainda não pertencente a N’: 12  D(v) = min{ D(v), D(w) + c(w,v) } 13  13 /* novo custo para v é: ou o velho custo para v, ou o menor 14 custo de caminho conhecido para w, mais o custo de w a v */ 15 até que todos os nós estejam em N.




109

Exemplo: Rodando o Algoritmo de Dijkstra’s para o nó A:

Passo 0 1 2 3 4 5

início N’ A

AD ADE

ADEB ADEBC

ADEBCF

D(B),p(B) 2,A 2,A 2,A

D(C),p(C) 5,A 4,D 3,E 3,E

D(D),p(D) 1,A

D(E),p(E) infinito

2,D

D(F),p(F) infinito infinito

4,E 4,E 4,E

•  Calculando os caminhos de menor custo de A até todos os destinos possíveis.

•  Lembrando: p(x) predecessor de x ao longo do caminho de menor custo atual.

• Cada linha da tabela fornece os valores das variáveis do algoritmo ao final da iteração.

A

E D

C B

F 2

2 1

3

1

1 2

5 3

5


110

Exemplo: Algoritmo de Dijkstra’s

Passo 0 1 2 3 4 5

início N A

AD ADE

ADEB ADEBC

ADEBCF

D(B),p(B) 2,A 2,A 2,A

D(C),p(C) 5,A 4,D 3,E 3,E

D(D),p(D) 1,A

D(E),p(E) infinito

2,D


4,E 4,E 4,E

A

E D

C B

F

2 2

1 3

1

1

2

5 3

5 E isso continua…

(aqui está apenas para o menor custo de “A”

até cada destino)




111

Exemplo: Algoritmo de Dijkstra’s

Passo 0 1 2 3 4 5

início N A

AD ADE

ADEB ADEBC

ADEBCF

D(B),p(B) 2,A 2,A 2,A

D(C),p(C) 5,A 4,D 3,E 3,E

D(D),p(D) 1,A

D(E),p(E) infinito

2,D


4,E 4,E 4,E

A

E D

C B

F

2 2

1 3

1

1

2

5 3

5 Menor custo de A até C é 3 e passa

por E.

Depois sabe-se qual o menor custo de A até E e por onde ele

passa... etc...


Resultado da tabela de repasse em A:

112

A

E D

C B

F

2

1

1

1

2

Destino: Link:

B (A,B)

C (A,D)

D (A,D)

E (A,D)

F (A,D)

Caminhos de menor custo resultantes, e a tabela de repasse para o nó A.

Exercício: obter as tabelas para todos os nós




113

Discussão do Algoritmo de Dijkstra Complexidade do Algoritmo: N nós   Cada iteração: precisa verificar todos os nós w, que

não estão em N.   N*(N+1)/2 comparações Ordem de (N**2):

Oscilações possíveis:   Total de tráfego transportado in/out (diferentes).

  Para este curso vamos assumir que os custos são os mesmos em ambos os sentidos (são simétricos).

A D

C

B 2+e 0

e 0 1+e 1

Custos assimétricos tornam o problema bem mais complicado não serão considerados aqui.


114

Roteamento Distance Vector (1)

 Enquanto o LS usa informação global, o DV é iterativo, assíncrono e distribuído.

Iterativo:   Continua até que os nós não troquem mais informações.

  Self-terminating não há sinal de parada.

Assíncrono:   Os nós não precisam trocar informações

simultaneamente! Distribuído:   Cada nó se comunica apenas com os seus vizinhos,

diretamente conectados.




Roteamento Distance Vector (2)

 Equação de Bellman-Ford (B-F) define:

dx(y) menor custo do caminho de x até y

Então:

dx(y) = minv {c(x,v) + dv(y) }

Onde min é calculado sobre todos os vizinhos v de x.


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

O nó que atinge o mínimo é o próximo salto no caminho mais curto da origem até o destino até ➜ resulta na tabela de roteamento.

Calculando o menor caminho de u até z com a

equação B-F diz que:

Roteamento Distance Vector (3) Vemos que:

dv(z) = 5 dx(z) = 3 dw(z) = 3




O que é o Vetor de Distâncias

 Dx = [ Dx(y): y em N ]

 Vetor de distâncias do nó x é um conjunto.

 É um conjunto contendo todas as estimativas de custos de x até todos os outros nós y em N.

117


O que cada nó mantém:

 Cada nó x mantém os seguintes dados de roteamento:

1.  O custo c(x,v) até cada vizinho v, diretamente conectado.

2.  O vetor de distâncias dele (nó x), contendo a estimativa dos custos de x até todos os destinos y em N.

3.  Os vetores de distâncias de seus vizinhos para cada vizinho v de x: Dv = [ Dv(y): y em N ].

118




Ideia básica:

  Cada nó envia periodicamente o seu de vetor de distância aos seus vizinhos.

  Ou seja, quais os custos ele tem até os destinos para os quais ele conhece.

  Quando o nó x recebe nova estimativa do vizinho, ele atualiza sua tabela usando a equação B-F:

Dx(y) = minv{c(x,v) + Dv(y)} para cada nó y ∊ N.

• Em condições normais, a estimativa Dx(y) converge para o menor custo atua.

Algoritmo Distance Vector


120

Roteamento Vetor-Distância: Resumo Iterativo, assíncrono: cada

iteração local é causada por:

  Mudança de custo dos enlaces locais.

  Mensagem do vizinho: seu caminho de menor custo para o destino mudou.

Distribuído:   Cada nó notifica seus

vizinhos apenas quando seu menor custo para algum destino mudar:   Vizinhos notificam seus

vizinhos, e assim por diante…

espera por mudança no custo dos enlaces locais, ou mensagem do vizinho.

recalcula tabela de distâncias.

se o caminho de menor custo para algum destino mudou, notifica vizinhos.

Cada nó:




121


122

X Z 1 2

7

Y

Exemplo: algoritmo vetor-distância (1/3)

DA(B,C)=C(A,C) + minw{DC(B,w)}

DX(Z,Y)=C(X,Y) + minw{DY(Z,w)}

= 2 + min {DY(Z,X)} = 2 + inf

{DY(Z,Y)} = 2 + loop

{DY(Z,Z)} = 2 + 1

= 2 + min {inf, loop,1} = 3

fórmula

Atualizando custo de X até Z passando por Y




123

X Z 1 2

7

Y

D (Y,Z) X

c(X,Z) + min {D (Y,w)} w= = 7+1 = 8

Z

Exemplo: algoritmo vetor-distância (2/3)

Atualizando custo de X até Y passando por Z


124

Exemplo: algoritmo vetor-distância(3/3)

X Z 1 2

7

Y

Custo para Y não mudou.

Custo para Z

Mudou. Avisa !




125

Exemplo de Tabela de Distância

A

E D

C B 7

8 1

2

1

2

D (C,D) E

c(E,D) + min {D (C,w)} D w =

= 2+2 = 4

D (A,D) E

c(E,D) + min {D (A,w)} D w =

= 2+3 = 5

D (A,B) E

c(E,B) + min {D (A,w)} B w =

= 8+6 = 14

DX(Y,Z) = c(X,Z) + minw{ DZ (Y,w) }

Custo de E até A dado que o primeiro passo ao longo do caminho é D: é o custo

de ir de E até D, mais qualquer que seja o custo mínimo de ir de D até A.

Note que o caminho

menor de D até A é 3 e esta rota passa

novamente por E !

Por que não é 15 ??


126

Exemplo de Tabela de Distância

A

E D

C B 7

8 1

2

1

2 D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

E custo via nó vizinho

dest

ino

D (C,D) E

c(E,D) + min {D (C,w)} D w =

= 2+2 = 4

D (A,D) E

c(E,D) + min {D (A,w)} D w =

= 2+3 = 5

D (A,B) E

c(E,B) + min {D (A,w)} B w =

= 8+6 = 14




127

A tabela de distâncias gera a tabela de roteamento

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

E custo através de

dest

ino

A

B

C

D

A,1

D,5

D,4

D,2

Enlace de saída, custo

dest

ino

Tabela de distância Tabela de Roteamento


128

A tabela de distâncias gera a tabela de roteamento

A

B

C

D

A,1

D,5

D,4

D,2

Enlace de saída,custo

dest

ino

Tabela de distância Tabela de Roteamento

Tabela de roteamento de E

Melhor rota de E para A é através de A, com custo 1

Melhor rota de E para B é através de D, com custo 5

Melhor rota de E para C é através de D, com custo 4

Melhor rota de E para D é através de D, com custo 4




Boas notícias viajam depressa: mudança nos custos do enlace.  Mudanças no custo do enlace:

  c(x,y) muda de 4 para 1.

  Nó y detecta mudança no custo do enlace local.

  Atualiza informações de roteamento, e recalcula o vetor de distância.

  Menor custo mudou avisa vizinhos.


Boas notícias viajam depressa

  No tempo t0 y detecta a mudança no custo do enlace, atualiza seu DV e informa seus vizinhos.

  No tempo t1 z recebe a atualização de y e atualiza sua tabela.   Custo c(z,x) mudou de 5 para 2.

  Avisa seu novo vetor aos vizinhos, com seu menor custo.

  No tempo t2 y recebe a atualização de z e atualiza sua tabela de distância.   O menor custo de y não muda.

  Então y não envia nenhuma mensagem para z.

  Só 2 iterações necessárias para o DV alcançar o estado de inatividade boas notícias viajam depressa.

130




 Mudanças no custo do enlace:   c(x,y) muda de 4 para 60.

  Nó y detecta mudança no custo do enlace local.

  Atualiza informações de roteamento, e recalcula o vetor de distância.

  Dy(x) = min { c(y,x) + Dx(x) , c(y,z) + Dz(x) }

  = min { 60 + 0 , 1 + 5} = 6

Más notícias viajam devagar: mudança nos custos do enlace.

Custo até z até x em y ainda está errado!


Porque o erro:

 Únicas informações que y possui:   Que seu custo direto até x agora é 60.

  E z disse a y que pode chegar a x com custo 5.

 Em seguida no instante t1 temos um looping de roteamento.

132




Más notícias viajam devagar

 Assim que y tenha calculado um novo custo mínimo até x:   y informa z este novo vetor de distâncias.

 Algum tempo depois de t1 ocorre que z recebe o novo vetor de y.   Indica que o custo mínimo de y até x é 6.

 z sabe que pode chegar até y com custo 1.   Dz(x) = min { c(z,x) + Dx(x) , c(z,y) + Dy(x) }

  = min { 50 + 0 , 1 + 6} = 7

 Este processo continua... Até estabilizar. 133


Problema de Contagem ao Infinito

Mudanças no custo do enlace:

 Neste exemplo: 44 iterações antes de o algoritmo estabilizar.

 O que aconteceria se c(y,x) tivesse mudado para 10.000 e o custo c(z,x) fosse 9.999 ?

  Más notícias viajam devagar: problema da “contagem ao infinito”.




Poisoned reverse

 Solução para o problema de contagem ao infinito: reverso envenenado.

 Se a rota de Z a X passa por Y Z anuncia a Y que seu custo de rota para X é infinito.   No exemplo: Z anuncia para Y que Dz(X) = ∞, mesmo

que Z saiba que, no momento, Dz(x)=5.

 Z “mente” para Y enquanto sua rota para X estiver passando por Y.   Enquanto Y acreditar que Z não tem rota até X, o nó Y

nunca vai tentar usar uma rota para X através de Z.   Pergunta: isso resolve todos os problemas de contagem ao infinito ?

135


Roteamento hierárquico

Autonomous Systems

136




137

Roteamento Hierárquico

Escala: 50 milhões de destinos.

  Não é possível armazenar todos os destinos numa única tabela de rotas.

  As mudanças na tabela de rotas poderiam congestionar os enlaces.

Autonomia Administrativa   Internet = rede de redes.

  Cada administração de rede pode querer controlar o roteamento na sua própria rede.

Problemas do mundo real:   Roteadores não são todos idênticos.

  Na prática redes não são “planas”.


138

Roteamento Hierárquico

  Agrega roteadores em regiões:   “Sistemas autônomos” ou

“Autonomous System” (AS).

  Roteadores dentro do mesmo AS rodam o mesmo protocolo de roteamento:   Protocolo de roteamento

Intra-AS.   Roteadores em diferentes

AS podem rodar protocolos de roteamento diferentes.

  Fronteira de um AS.   Rodam protocolos de

roteamento Intra-AS com os outros roteadores do AS.

  Também responsáveis por enviar mensagens para fora do AS .   Rodam protocolo de

roteamento inter-AS com outros roteadores.

Roteadores de borda




139

Roteamento Intra-AS e Inter-AS

a

b

b

a a C

A

B d

c b

c

Organização A

Organização B

Organização C


140


a

b

b

a a C

A

B d

A.a A.c

C.b B.a

c b

c

Roteadores de Borda: • Realizam roteamento inter-AS entre instituições diferentes.

• Realizam roteamento intra-AS com outros roteadores dentro do mesmo AS.

AS B

AS A

AS C




141


Roteamento inter-AS e intra-AS no roteador A.c

Camada de rede

Camada de enlace Camada fisica

a

b

b

a a C

A

B d

A.a A.c

C.b B.a

c b

c


142


Host h2

a

b

b

a a C

A

B d c

A.a A.c

C.b B.a

c b

Host h1

Roteamento Intra-AS: dentro do AS “A” (interior gateways)

Roteamento Intra-AS, dentro do AS “B”

Roteamento Inter-AS entre os AS’s “A” e “B” (exterior gateways)

Nós voltaremos a discutir protocolos de roteamento Inter-AS e Intra-AS mais

adiante…




Roteamento Intra-AS

Interior Gateway Protocols (IGP)

143


144

Roteamento Intra-AS   Também conhecido como:

  Interior Gateway Protocols (IGP).

  ou protocolos de roteamento interno.   Os IGPs mais comuns são:

  RIP: Routing Information Protocol

  OSPF: Open Shortest Path First

  IGRP: Interior Gateway Routing Protocol (proprietário da Cisco)




145

RIP (Routing Information Protocol) (1)

  Algoritmo vetor de distâncias (distance vector).   Incluído na distribuição de BSD-UNIX desde1982.

  Métrica de distância: número de enlaces   Máximo = 15 enlaces.

  Vetores de distâncias: mensagem a cada 30 segundos.   Também chamada de anúncio.

  Cada anúncio: pode definir rotas para até 25 redes destino.


146


 Periodicamente cada roteador envia uma cópia de sua tabela de roteamento para qualquer outro roteador que ele consiga acessar diretamente (outro roteador que está no extremo de alguma interface sua).

Roteador Roteador J Roteador K Roteador

Anúncio




147


  Quando um anúncio chega ao roteador K vindo do roteador J, então K examina os destinos conhecidos, e a distância até cada um destes destinos. Algumas situações podem ocorrer: •  Se J souber de um caminho mais curto para chegar ao

destino, ou •  Se J listar um destino que não conste da tabela de K, ou •  Se K estiver no momento roteando para um destino através de

J e a distância de J até aquele destino mudar,   ..então K substitui a sua entrada na tabela.

Roteador Roteador J Roteador K Roteador

Anúncio


148


Tabela de K Atualização de JDestino Distância Rota Destino DistânciaRede 1 0 Direta Rede 1 2Rede 2 0 Direta ! Rede 4 3Rede 4 8 Roteador L Rede 17 6Rede 17 5 Roteador M ! Rede 21 4Rede 24 6 Roteador J Rede 24 5Rede 30 2 Roteador Q Rede 30 10Rede 42 2 Roteador J ! Rede 42 3

À esquerda: uma tabela de roteamento existente num roteador K. À direita: uma mensagem de atualização recebida de J. As entradas marcadas com “” serão usadas para atualizar as entradas existentes, ou acrescentar novas entradas, na tabela de K.

Note que se J informar uma distância N, então uma entrada atualizada em K terá uma distância N+1 a distância para acessar o destino a partir de J, mais a distância para acessar J.




149

RIP: Recuperação de falhas   Se não for recebido anúncio novo durante 180 seg →

vizinho/enlace são declarados mortos.

  Rotas via vizinho são invalidadas.

  Novos anúncios são enviados aos vizinhos.

  Na sua vez, os vizinhos publicam novos anúncios, se foram alteradas as suas tabelas.

  Informação sobre falha do enlace rapidamente propaga para a rede inteira.


150

RIP: Recuperação de falhas - Exercício  Exercício: já vimos uma técnica para evitar rotas

cíclicas (looping) e contagem ao infinito com algoritmos Distance Vector, chamada de poisoned reverse. Pesquise e estude as seguintes técnicas de recuperação ou mitigação de rotas cíclicas:   Envenenamento de rotas (Route Poisoning).

  Estreitamento de horizontes (Split Horizon).

  Tempo de Espera (Holddown Timers).

  Atualizações Imediatas (Triggered Updates).




151

OSPF (Open Shortest Path First)   “Open” (aberto) publicamente disponível   Usa algoritmo do Estado de Enlaces - EE (Link State)

  Disseminação de pacotes de EE.

  Mapa da topologia presente em cada nó.

  Cálculo de rotas usando o algoritmo de Dijkstra.

  Anúncio de OSPF inclui uma entrada por roteador vizinho.

  Anúncios disseminados para AS inteiro

  Via inundação – flooding.


152

OSPF: características “avançadas” (não presentes em RIP)   Segurança: todas mensagens OSPF são autenticadas para

(tentar) impedir intrusão maliciosa.

  Usa conexões TCP.

  Caminhos Múltiplos com custos iguais permitidos.   (o RIP permite e aceita apenas uma rota quando custos iguais).

  Para cada enlace, múltiplas métricas de custo para TOS diferentes   Exemplo: custo de enlace de satélite definido como “baixo” para

melhor esforço, e “alto” para aplicação de tempo real.

  OSPF pode ser hierárquico em domínios grandes.




153

OSPF Hierárquico


154

IGRP (Interior Gateway Routing Protocol)

  Proprietário da CISCO.   Sucessor do RIP (final dos anos 80).

  Usa Vetor de Distâncias assim como RIP.

  Diversas métricas de custo:   Atraso, largura de banda, confiabilidade, carga, etc...

  Usa TCP para trocar mudanças de rotas.

  Roteamento via Distributed Updating Algorithm (DUAL) baseado em computação difusa.




Roteamento Inter-AS

Exterior Gateway Protocols (EGP)

155


156

Roteamento Inter-AS




157

Roteamento inter-SA na Internet: BGP

  BGP (Border Gateway Protocol) o padrão de fato   Protocolo Vetor de Caminhos:

  Semelhante ao protocolo de Vetor de Distâncias (DV).

  Cada Border Gateway (roteador de fronteira) difunde aos vizinhos (pares) o caminho inteiro (isto é, seqüência de ASs) ao destino.

  Por exemplo: roteador de fronteira X pode enviar seu caminho ao destino Z:

Path (X,Z) = X,Y1,Y2,Y3,…,Z


158

Roteamento inter-SA na Internet: BGP

  Suposição:   roteador X envia seu caminho para roteador para W.

  W pode ou não selecionar o caminho oferecido por X

  razões de custo, políticas (não rotear via o AS de um concorrente), evitar looping, dentre ouros motivos.

  Se W seleciona caminho até Z anunciado por X, então:

Caminho (W,Z) = W, Caminho (X,Z)

  Note que X pode controlar o tráfego de chegada através do controle dos seus anúncios de rotas aos seus pares.   Por exemplo: se não quero receber tráfego para Z:

•  Não anuncia rotas para Z.




159

Por que há diferenças entre roteamento Intra e Inter-AS?

Políticas:   Inter-AS administração quer controle sobre como tráfego roteado,

quem transita através da sua rede.

  Intra-AS administração é única, portanto são desnecessárias decisões políticas.

Escalabilidade:   Roteamento hierárquico economiza tamanho de tabela de rotas, reduz

tráfego de atualização

Desempenho:   Intra-AS: pode focar em desempenho.

  Inter-AS: políticas podem ser mais importantes do que desempenho.


160

Final da Camada de Rede

Vimos neste capítulo:   Serviços da camada de

rede.

  Roteamento e Roteador.

  Endereços IP.

  Fragmentação e MTU.

  Sub-redes e máscaras.

  Princípio de roteamento: seleção de caminhos.

  Algoritmos de roteamento.   Link state e distance

vector.

  Roteamento hierárquico.

  Sistemas Autônomos.

  Protocolos de roteamento da Internet.

Documents

Curso de Redes de Computadores - angel.acmesecurity.orgadriano/redes/2011/net-adr-2011... · Executar algoritmos e protocolos de roteamento • RIP, OSPF, BGP, dentre outros