Adriano Mauro Cansian adriano@acmesecurityadriano/aulas/... · unesp - IBILCE - SJRP 2 Capítulo 4: Camada de Rede Metas: q Entender os princípios em que se fundamentam os serviços

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: q  Entender os princípios

em que se fundamentam os serviços de rede: §  Roteamento §  Escalabilidade. §  Implementação na

Internet.

Veremos: q  Serviços da camada de rede. q  Como funciona um roteador. q  Endereços IP. q  Princípio de roteamento. q  Roteamento hierárquico.

§  AS

q  Protocolos de roteamento da Internet. §  Dentro de um domínio. §  Entre domínios


3

Funções da camada de rede (1) q 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. –  Analogia com o correio e carteiro que roteia as cartas

q 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.

•  Ligação de redes com redes •  “inter-net” = Internetworking .


4

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

host emissor ao receptor. q  Protocolo da camada de rede:

presente em hosts e routers. Três funções importantes: q  Determinação do caminho: rota

seguida por pacotes da origem ao destino. q  Usa algoritmos de roteamento.

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

q  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, ainda que elas sejam implementadas para prover serviços

de acesso ao roteador

Não acontece na Internet


Funções da camada de rede (3) •  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.

• Toma decisões de roteamento. • É “stateless”.


Funções-chave da camada de rede: q Roteamento:

§  Determinar a rota a ser seguida pelos pacotes.

q Comutação ou repasse: §  Mover pacotes dentro do roteador, da

entrada para a saída apropriada.

q Algoritmos de roteamento - analogia: §  Roteamento: processo de planejar a

viagem para saber qual caminho seguir. §  Comutação: processo de passar por um

único cruzamento.


7

Rede de datagramas: o modelo da Internet

q  Não requer estabelecimento de chamada na camada de rede q  Não guarda estado sobre transmissões.

§  Não existe o conceito de “conexão” na camada de rede. q  Pacotes são roteados usando endereços de destino.

§  Cada camada de rede vai “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 até 0 11001000 00010111 00010111 11111111----------------------------------------------------------------------------------------------------- 11001000 00010111 00011000 00000000 até 1 11001000 00010111 00011000 11111111 ----------------------------------------------------------------------------------------------------- 11001000 00010111 00011001 00000000 até 2 11001000 00010111 00011111 11111111 ----------------------------------------------------------------------------------------------------- QUALQUER OUTRO 3

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

Tabela de comutação ou repasse


Destination Address Range Link Interface 200 16 0

11001000 00010000 00000000 200 23 23 255 0

11001000 00010111 00010111 11111111----------------------------------------------------------------------------------------------------- 200 23 24 0

11001000 00010111 00011000 00000000 200 23 24 255 1

11001000 00010111 00011000 11111111 ----------------------------------------------------------------------------------------------------- 200 23 25 0

11001000 00010111 00011001 00000000 200 23 31 255 2

11001000 00010111 00011111 11111111 ----------------------------------------------------------------------------------------------------- caso contrário 3

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

200 23 24 170 11001000 00010111 00011000 10101010

Exemplos

200 23 22 161 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


Como funciona um roteador ?

Visão geral da arquitetura de um roteador

12


13

Visão Geral de Arquitetura de Roteadores q  Roteadores possuem 2 funções fundamentais:

§  Executar algoritmos e protocolos de roteamento. •  Principalmente RIP, OSPF e BGP. Mas há outros.

§  Repassar(*) datagramas da interface de entrada para a saída. •  Por intermédio da malha (ou matriz) de comutação (switch fabric).

(*) Repassar = Comutar.


14

Funções da Porta de Entrada

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

qual porta de saída. §  Usa tabela de rotas na memória da porta de entrada.

q  Tenta fazer o processamento da porta de entrada na “velocidade da linha”.

q  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: Fast ethernet


15

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

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


16

Comutação via Memória q  Presentes nos roteadores da primeira geração. q  Pacote é copiado para a memória pelo processador do sistema.

§  Ocorre um gargalo devido ao processamento único.

q  Depois o pacote é lido na memória para fazer o repasse. q  A velocidade é limitada pela largura de banda da memória.

§  Duas travessias do barramento por cada datagrama (entrada e saída na memória).

Porta de Entrada Porta de

Saída Memória

Barramento do Sistema Roteadores atuais / modernos: q  Colocam processador da porta de entrada:

q  Consulta tabela e copia para a memória.


17

Comutação via Barramento

q  Datagrama viaja da memória da porta de entrada à memória da porta de saída. §  Por intermédio de um barramento compartilhado.

q  Contenção pelo barramento: §  Taxa de comutação limitada pela largura de banda do barramento.

§  Datagramas competem pelo uso do barramento.

q  Barramento de 1 a 100 Gbps são comuns. §  Velocidade suficiente para roteadores de acesso e corporativos (mas

não de backbone).


18

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

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

inicialmente para interligar processadores num multiprocessador (Redes Banyan).

q  Consiste de 2 x N barramentos, conectando N portas de entrada com N portas de saída.

q  Portas podem “conversar” ao mesmo tempo na matriz. §  Taxas atuais variam de 200 Gbps a 1 Tbps

§  Já existem roteadores de 100 Tbps.

§  Indicado para roteadores de backbone.


Comutação cross-bar

19

Portas podem “conversar” ao mesmo tempo na matriz.


20

Porta de Saída

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

q  Eventualmente há disciplina de escalonamento: escolha

dos datagramas enfileirados para transmissão.

§  Pode haver usar o campo TOS no header do datagrama IP.

§  (será discutido mais adiante).


21

Filas e perdas na Porta de Saída q  Quando taxa de chegada através do comutador

excede taxa de transmissão de saída: §  Utiliza-se buffer para armazenamento temporário.

q  Ocorre enfileiramento (atraso) e eventualmente perdas (drop) devido ao transbordamento do buffer da porta de saída.


22

Bloqueio Head-of-Line (HOL) q  Se matriz de comutação é mais lenta do que a soma das

portas de entrada juntas → pode haver filas nas portas de entrada.

q  Bloqueio HOL: datagrama na cabeça da fila impede outros na mesma fila de avançarem. §  Acontecem atrasos de enfileiramento e perdas, devido ao

transbordamento do buffer de entrada.


Bloqueio HOL

23

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

24


A Camada de Rede na Internet

25

Tabela de rotas

Protocolos de roteamento•  Escolha de caminhos

•  RIP, OSPF, BGP

Protocolo IP •  Endereçamento. •  Formato dos datagramas. •  Tratamento de pacotes.

Protocolo ICMP •  Aviso de erros e testes. •  Sinalização de rotas.

***** Camada de Transporte *****

***** Camada de enlace (datalink) *****

***** Camada física *****

Ca

ma

da

de

re

de


Datagrama IP

Especificações do Protocolo

26


27

Formato do datagrama IP (1)

ver comprimento

32 bits

dados (comprimento variável,

tipicamente um segmento TCP ou UDP)

ident. 16-bits

checksum Internet

TTL

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

protocol

endereço IP de destino 32 bits

Opções (se houver) Exemplo: temporizador, Registro de rota seguida, especificar caminho, etc... Na prática: NUNCA USADO.

Checksum envolve apenas verificação do cabeçalho

(não dos dados).


28


29


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

•  Versão: o primeiro campo do cabeçalho de um datagrama IPv4 é o campo de versão, com 4 bits.

•  IHL: o segundo campo, de quatro bits, é o Comprimento do Cabeçalho ou IHL (Internet Header Length) contendo o número de palavras de 32 bits no cabeçalho IPv4.

•  Um cabeçalho mínimo tem vinte bytes de comprimento, logo o valor mínimo em decimal no campo IHL é 5 (5 x 32 bits = 20 bytes).

•  Tamanho total: campo de 16 bits define o tamanho TOTAL do datagrama (cabeçalho + dados), em bytes.

•  O valor do campo tamanho mínimo é de 20 bytes. •  Então, o tamanho máximo possível é 65.536 bytes (64 Kbytes).


30



Identification


Fragment offset

Header checksum

Source address

Destination address


D F

M F

32 Bits

•  Protocolo: com 8 bits define o código decimal do protocolo que o IP está carregando no campo de dados. A IANA - Internet Assigned Numbers Authority mantém a lista com os números de protocolos.

•  Os protocolos comuns e os seus valores decimais incluem o ICMP (1), o TCP (6) e o UDP (17). Ver http://www.iana.org/assignments/protocol-numbers.

•  TTL (Time To Live): evita que os datagramas persistam numa rede (por exemplo, evitando loopings de roteamento). É setado na origem.

•  Historicamente o campo TTL limitaria a vida de um datagrama em segundos, mas tornou-se num campo de contagem de nós caminhados (chamado de hop count).

•  Roteador onde um datagrama atravessa decrementa o campo TTL em 1. •  Quando o campo TTL chega a zero, o pacote não é enviado e deve ser descartado.

Datagrama ICMP de erro (ICMP 11 – Time Exceeded) é enviado de volta ao emissor


MTU e adaptação a redes diferentes

31

Internet

SLIP : 256

PPP : 1500

Ethernet : 1500

ADSL: 512


32

IP: Fragmentação & Remontagem (1)

Rede 3MTU=1.500

Rede 1MTU = 1.500

Rede 2MTU=620

Host A

Host BRouter 1 Router 2

?

?

? •  Um datagrama pode passar por muitos tipos de redes físicas

diferentes, à medida que se move dentro das interligações das redes, até alcançar seu destino final.

•  Como a rede define um tamanho de datagrama que se encaixe no frame?

•  Como a rede trata datagramas maiores do que sua camada de enlace pode suportar?

?


33

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

(Maximum Transmission Unit) - maior tamanho possível de FRAME neste enlace. §  Tipos diferentes de enlace têm MTUs

diferentes.

q  Quando há um datagrama IP muito grande a ser enviado numa rede que não o comporta: ele é 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


34

IP: Fragmentação & Remontagem (3) Campos do Protocolo IP utilizados


Identification


Fragment offset

Header checksum

Source address

Destination address


D F

M F

32 Bits

IDENTIFICATION (16 bits) à Contém um inteiro que identifica o datagrama. Todo gateway que fragmenta o datagrama, copia o IDENT em cada um dos fragmentos.

FLAGS à Controla a fragmentação : Do Not fragment (DF) ou More Fragments (MF).

FRAGMENT OFFSET (13 bits) à Especifica a que ponto do datagrama atual o fragmento pertence (offset). É UM DECIMAL EM BYTES QUE SEMPRE representa o deslocamento daquele fragmento, a partir do 1o. Bit. Sempre deve ser múltiplo de 8.


35


q O IP representa o deslocamento de dados em múltiplo de 8 bytes. §  Portanto, o tamanho do fragmento será sempre o

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 são obrigados aceitar e remontar,

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


36


ID =x

início =0

bit_frag =0

compr =4000

ID =x

início =0

bit_frag =1

compr =1500

ID =x

início =185

bit_frag =1

compr =1500

ID =x

início =370

bit_frag =0

compr =1040

um datagrama grande fragmentado em vários datagramas menores

•  1480 ÷ 8 = 185 •  2960 ÷ 8 = 370 •  1500 total = 1480 dados + 20 bytes header

Início em 2960 bytes

Início em 1480 bytes

Início em 0 bytes


37

Controle IP – Fragmentação

Identifica o datagrama Indicando que existe

mais fragmentos Indica a posição do

fragmento em relação ao datagrama


38


Indicando que não há mais fragmentos,

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


39


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


ICMP

40


ICMP – Internet Control Message Protocol

q Parte da camada IP. q 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 (ping) e testes.

q 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

Mensagem ICMP


Formato da Mensagem ICMP

43

tipo código checksum 0 7 8 15 16 31

parâmetros

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

informação


ICMP Message Types type Description 0 Echo Reply Echo Reply 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

q 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


46

Endereçamento IP


47

Endereçamento IP q Endereço IP: 32 bits, divididos em dois campos:

•  IDent. de rede (network number).

•  IDent. do host (host number).

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

xxx . yyy . zzz . kkk

223 . 1 . 1 . 1

11011111 00000001 00000001 00000001

q  Grupo decimal é conhecido como um “octeto”.

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

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


Endereço IP – notação decimal

48

10000000 00001010 00000010 00011110

2726252423222120 2726252423222120 2726252423222120 2726252423222120

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

128.10.2.30 notação decimal pontuada

notação binária

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


Exemplos:

49


Exemplos:

50


Endereços de host e de rede

51

Identificador da rede

Identificador do host

Endereço IP de 32 bits

REDE 1

internet

REDE 2 REDE 4

REDE 3

hosts com o mesmo identificador de rede.

hosts com identificadores

de rede distintos.

host


52

Endereçamento hosts e redes (1)

q  Interface: conexão entre estação, roteador e enlace físico. §  Roteador típico tem

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


53


q  Endereço IP: §  Uma parte de rede.

•  (bits de mais alta ordem).

§  Uma parte de host. •  (bits de mais baixa ordem).

q  Uma rede IP: §  Conjunto de Interfaces de

dispositivos com o mesmo campo 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 parte da rede consiste de 3 interfaces IP com os endereços IP começando com 223.1.3.

•  Os primeiros 24 bits são o campo de rede.

LAN



54

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

•  Este conjunto de redes consiste numa rede com 3 redes, cujos os endereços IP começam com 223.1.

•  Sub-redes de uma rede maior.

LAN Internet



55

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


Identificando Rede e Host

q PERGUNTA: como identificar qual é a parte

do endereço IP que corresponde à parte de

REDE e qual corresponde à parte de

HOST?

56


Denominação de “classes” (atenção: em desuso)

57


58

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)


59

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


60

Classes de redes (4)

Classe Formato do Endereço Organização da Rede Intervalo dos

endereços da classe A 0 Identificador

da RedeIdentificador doHost

7 bits 24 bits

127 redes com até 16.777.216 hosts.

de 1.0.0.0 até 127.255.255.255.

B 10 Identificadorda Rede

Identificador doHost

14 bits 16 bits

16.384 redes com até 65.535 hosts.

de 128.0.0.0 até 191.255.255.255.

C 110 Identificadorda Rede

Identificador doHost

21 bits 8 bits

2.097.152 redes com até 254 hosts.

de 192.0.0.0 até 223.255.255.255.


61

parte do host

Endereçamento IP: CIDR

q CIDR: Classless InterDomain Routing §  Parte de rede do endereço de comprimento arbitrário.

§  Formato de endereço: a.b.c.d/x

§  /x é número de bits no campo de rede do endereço.

11001000 00010111 00010000 00000000

parte de rede

200.23.16.0/23


62

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/16 Refere-se à rede 137.4.*.*

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


63

Endereços reservados de REDE e BROADCAST (2)

Endereços de broadcast q  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, os bits de host são ajustados para 1.

q  Exemplos: O endereço 15.255.255.255/8

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


64

Subneting e subnetmask (1)

q  “Subnetar”: subdividir um conjunto de endereços IP para criar redes menores, ou seja, subredes.

q  Máscaras de sub-rede (subnetmasking) são usadas para indicar a subdivisão de redes.

q  A máscara de sub-rede diz para um roteador ou software específico quantos bits dos campos de rede e de host devem ser considerados para uma determinada rede. §  Como vimos na notação CIDR, a “ / ” indica a máscara aplicada.

§  Exemplo: 200.23.16.0/23



65

•  Exemplo: divisão de uma rede /24 em redes menores. •  Os 8 bits de host estão sendo subdivididos para criar subredes

menores: no exemplo usando 3 bits para redes e 5 bits para hosts. •  Passa a existir a possibilidade de 8 subredes para serem usadas e a

máscara de subrede interna passa a ser / 27.


66

Subneting e subnetmask (3) Funcionamento e obtenção da máscara: q 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.

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


67

Subneting e subnetmask (4) Considere os 8 bits identificadores de host num endereço de uma rede /24.

Se quisermos dividir uma rede /24 em 4 subredes ! vamos utilizar 2 bits para identificar a subrede e 6 bits para identificar os hosts.

Máscara resultante = /26 ou 255.255.255.192 Rede (decimal) subnet subnet host host host host host host

255.255.255. 1 1 0 0 0 0 0 0

Binário 11000000 = 192

Resulta na subnetmask ! 255.255.255.192

Esta divisão permite, na prática, utilizar 2 sub-redes de 64 hosts, pois as subredes que começam com 00 e 11 são reservadas e não podem ser utilizadas ! isso ocorre devido à identificação dos endereços de rede (all-0s, ou seja todos os endereços de host com bit 0) e endereço de broadcast (all-1s, ou seja todos os endereços de host com bit 1)


68


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


69

Subneting e subnetmask (6) Se quisermos dividir uma rede /24 em 16 subredes ! vamos utilizar 4 bits para identificar a subrede e 4 bits para identificar os hosts.

Máscara resultante = /28 Isso nos dá a possibilidade de 16 sub-redes de 16 hosts, das quais 14 sub-redes podem ser usadas ! novamente se “perdem” as subredes que começam com 0000 e 1111 (all-zero e all-one).

Cálculo da máscara:

Rede (decimal) subnet subnet subnet subnet host host host host

255.255.255. 1 1 1 1 0 0 0 0

Binário 11110000 = 240

Resulta na subnetmask ! 255.255.255.240


Outra maneira de obter o endereço da subrede: bitwise AND

70


Outra maneira de obter o endereço da subrede: bitwise AND

71


Endereços reservados (1)

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

§  10.0.0.0 a 10.255.255.255

q 16 REDES /16: §  172.16.0.0 a 172.31.255.255

q 256 REDES /24: §  192.168.0.0 a 192.168.255.255

q Também chamados de: §  Endereços não roteáveis ou redes não roteáveis.

•  Usados para redes locais.

72


Endereços reservados (2)

q  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 – Exemplo: End. BroadCast para rede /24 •  n.n.255.255 – Exemplo: End. BroadCast para rede /16 •  n.255.255.255 – Exemplo: End. BroadCast para rede /8

§  nnn.nnn.nnn.000: •  Network: todos os bits de host ajustados para 0. •  n.n.n.0 – Exemplo: End. Rede para rede /24 •  n.n.0.0 – Exemplo: End. Rede para rede /16 •  n.0.0.0 – Exemplo: End. Rede para rede /8

§  0.0.0.0: •  Endereço de Inicialização (DHCP)

73


Subdivisão de redes e roteamento

Regra do prefixo mais longo

74


75

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

q  Alocação a partir do espaço de endereços do provedor IP. q  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


76

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

“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 informação sobre rotas de forma eficiente e sumarizada

199.31….. /16

Mega-empresa A


77

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

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

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

200.23.20.0/23 Organização 2

. . .

. . .

199.31….. /16 Mega-empresa A

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

“Mande-me qualquer coisa com endereços que começam com

199.31.0.0/16 ou 200.23.18.0/23”


78

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


79

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

80


81

Envio de datagramas Para transferir um datagrama o emissor:

1. Mapeia o endereço IP de destino em um endereço físico (endereço MAC)

2. Encapsula o datagrama num frame da camada de enlace, e...

3. Usa a rede local para entregar ao destino §  Camada Datalink (ou camada “MAC”).


82

Encaminhamento direto q  Emissor:

1.  extrai a parte da rede do endereço IP de destino, e

2.  compara com a parte de rede de seu próprio endereço. §  Se houver correspondência, significa que o datagrama

pode ser enviado diretamente, na mesma rede.

q  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).


83

Encaminhamento indireto

q  Destino não está na mesma rede física do emissor.

q  Encapsula o datagrama, e o envia ao roteador mais próximo (gateway de saída).

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

q  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.


Como saber se é encaminhamento direto ou indireto?

84


85

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

q Datagrama IP permanece inalterado, enquanto passa da origem ao destino.

•  IP destino não muda

tabela de rotas em A


86

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 Seja um datagrama IP originando

em A, e endereçado a B: q  A procura endereço de rede de B.

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

q  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


87

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

Seja origem A, destino E: q  Procura endereço de rede de E. q  E está numa rede diferente

§  A e E não diretamente conectados. q  Tabela de rotas: próximo roteador na

rota para E é 223.1.1.4 . q  Camada de enlace envia datagrama

ao roteador 223.1.1.4 num frame da camada de enlace.

q  Datagrama chega a 223.1.1.4 q  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


88

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

q  Procura endereço de rede de E. q  E fica na mesma rede que a interface

223.1.2.9 do roteador. §  Roteador e E estão diretamente

conectados. q  Camada de enlace envia datagrama

para 223.1.2.2 dentro de frame de camada de enlace via interface 223.1.2.9

q  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


NAT: Network Address Translation

89


NAT: Network Address Translation (1)

q  Propósito: Fazer com que redes locais possam utilizar apenas um endereço IP de entrada e saída.

q  Não é preciso alocar uma gama de endereços do ISP.

q  Motivação:

§  Esgotamento dos endereços IPv4.

§  Permitir alterar os endereços dos dispositivos na rede local sem precisar notificar o mundo exterior.

§  Mudar de ISP sem alterar os endereços 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 ?).


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.


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


1: host 10.0.0.1 Porta 3345

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



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

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

q  . . . Hosts remotos respondem usando (endereço IP do NAT, nova porta #) como endereço de destino. q  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 #). q  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.




q Campo número de porta com 16 bits: §  Aproximadamente 65.000 conexões

simultâneas com um único endereço IP.

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

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

§  A escassez de endereços: usar IPv6.

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

§  Algumas aplicações não funcionam com NAT.


95

Interconexão de redes e roteamento


96

O problema de inter-redes

q Internet = INTERNETworking §  Interconexão de redes.

q Comunicação fim-a-fim sobre redes: §  Com 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.


97

Elementos de Interconexão em várias camadas:

q  Repetidores na camada física (layer1).

q  Switches na camada de acesso ao meio (layer2).

q  Roteadores na camada de rede (layer3).

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


98

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:

q  Nós do grafo são roteadores. q  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

q  Caminho “melhor”: §  Tipicamente significa

caminho de menor custo.

§  Geralmente caminho MAIS CURTO.

§  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) }

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(a,a’) = custo do link (a,a’) • 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.


Tipos de algoritmos de roteamento

q Duas classificações principais.

§  Quanto ao tipo da informação.

§  Quanto à mudança das rotas.

q Veremos em seguida... §  Classificação 1: Informação global ou

descentralizada?

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

101


102

Classificação 1: Informação global ou descentralizada ?

q  Global: Todos roteadores têm informações completas de topologia, distância e custos de todos os enlaces. §  Algoritmos de “estado de enlaces” (link state - LS).

q  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).


103

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

q  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.

q  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

104


Algoritmos de roteamento

q Dois algoritmos principais: §  Link State e Distance Vector.

q  Link state: §  Informação Global. §  Algoritmo de Dijskstra

q  Distance vector: §  Informação Descentralizada §  Equação de Bellman-Ford.

105


Link State

106


107

Roteamento Link-state q  Usa o Algoritmo de Dijkstra para calcular melhor

caminho. q  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. q  Calcula caminhos de menor custo de uma origem para

todos os outros nós destinos. §  Fornece uma tabela de roteamento a partir daquele nó

(origem).


108

Notação do algoritmo de Dijkstra (1)

q 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.

q Dx(v): menor custo atual entre a origem

x e o destino V (até a presente iteração do

algoritmo).


109

Notação do algoritmo de Dijkstra (2)

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

q  N’: subconjunto de nós à irá formar o conjunto de menor custo. §  v pertence a N’ se o caminho de menor custo entre a

origem e v for inequivocamente conhecido.


Algoritmo de Dijsktra em palavras:

q Para um determinado nó: §  Iniciar só com o custo dos valores dos vizinhos

diretos.

q  Ir anexando cada nó do conjunto, um a um. §  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).

Como veremos em seguida à

110


Algoritmo de Dijsktra em palavras:

q Dx(v) = min{ Dx (v), Dx (w) + c(w,v) }

novo custo de x até v é: o velho custo para v, ou o menor custo de caminho conhecido para w (antecessor de v) mais o custo de w a v.

111

A

E D

C B

F 2

2 1

3

1

1

2

5 3

5


Exemplo para o novo custo de A até C após entrar D no conjunto de caminhos possíveis:

Dx (v) = min{ Dx (v), Dx (w) + c(w,v) }

DA(C) = min{ DA (C), DA (D) + c(D,C) }

DA(C) = min{ 5, 1 + 3} = min{ 5, 4 } = 4

112

A

E D

C B

F 2

2 1

3

1

1

2

5 3

5

w

v


113

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


114

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)


115

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:

116

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


117

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.


118

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

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

Oscilações possíveis: q  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.


Distance Vector

119


120

Roteamento Distance Vector (1) Enquanto o LS usa informação global, o DV é

iterativo, assíncrono e distribuído. q  Iterativo:

§  Continua até que os nós não troquem mais informações. §  Self-terminating à não há sinal de parada.

q Assíncrono: §  Nós não precisam trocar informações simultaneamente!

q  Distribuído: §  Cada nó se comunica apenas com os seus vizinhos,

diretamente conectados.


Roteamento Distance Vector (2)

q 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.


Roteamento Distance Vector (4)

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

dx(y) = minv {c(x,v) + dv(y) } Onde min é calculado sobre todos os vizinhos v de x.

q  Se após transitarmos de x para v, tomarmos o caminho de menor custo de v até y, o custo do caminho será c(x,v) + dv(y).

q  Como devemos começar viajando até algum vizinho v, o menor custo de x até y é o mínimo do conjunto dos c(x,v) + dv(y), calculados para todos os vizinhos v.


Roteamento Distance Vector (5) q  Se após transitarmos de x para v, tomarmos o caminho

de menor custo de v até y, o custo do caminho será c(x,v) + dv(y).

q  Como devemos começar viajando até algum vizinho v, o menor custo de x até y é o mínimo do conjunto dos c(x,v) + dv(y), calculados para todos os vizinhos v.

A

E D

C B

F 2

2 1

3

1

1 2

5 3

5

x

v y


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:

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

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

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

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

125


O que cada nó mantém:

Cada nó x mantém os seguintes dados:

1. Para cada vizinho v à o custo c(x,v) dele x até cada vizinho diretamente conectado, v.

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

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

126


q  Cada nó envia periodicamente o seu de vetor de distância a cada um dos seus vizinhos.

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

q  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.

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

Algoritmo Distance Vector – ideia básica


128

Roteamento Vetor-Distância: Resumo q  Iterativo, assíncrono: cada iteração local

é causada por:

q  Mudança de custo dos enlaces locais.

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

Distribuído:

q  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ó:


129


130

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


131

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


132

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

X Z 1 2

7

Y

Custo para Y não mudou.

Custo para Z

Mudou. Avisa !


133

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 ??


134

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


135

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 de

stin

o

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


136

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 de

stin

o

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. q 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

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

q  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.

q  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.

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

138


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

q Ú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.

q Em seguida no instante t1 temos um looping de roteamento.

140


Más notícias viajam devagar

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

q 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.

q 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

q Este processo continua... Até estabilizar. 141


Problema de Contagem ao Infinito

Mudanças no custo do enlace: q Neste exemplo: 44 iterações antes de o

algoritmo estabilizar. q 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 q Solução para o problema de contagem ao

infinito: reverso envenenado. q 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.

q 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. q  Pergunta: isso resolve todos os problemas de contagem ao infinito ?

143


Roteamento hierárquico

Autonomous Systems

144


145

Roteamento Hierárquico

Escala: 50 milhões de destinos.

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

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

Autonomia Administrativa q  Internet = rede de redes. q  Cada administração de rede

pode querer controlar o roteamento na sua própria rede.

Problemas do mundo real: q  Roteadores não são todos idênticos. q  Na prática redes não são “planas”.


146

Roteamento Hierárquico q  Agrega roteadores em

regiões: §  “Sistemas autônomos” ou

“Autonomous System” (AS). q  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.

q  Fronteira de um AS. q  Rodam protocolos de

roteamento Intra-AS com os outros roteadores do AS.

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

roteamento inter-AS com outros roteadores.

Roteadores de borda


147

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


148


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


149


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


150


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)

151


152

Roteamento Intra-AS q  Também conhecido como:

§  Interior Gateway Protocols (IGP). §  ou protocolos de roteamento interno.

q  Os IGPs mais comuns são:

§  RIP: Routing Information Protocol

§  OSPF: Open Shortest Path First

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


153

RIP (Routing Information Protocol) (1) q  Algoritmo vetor de distâncias (distance vector). q  Incluído na distribuição de BSD-UNIX desde1982. q  Métrica de distância: número de enlaces

§  Máximo = 15 enlaces.

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

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


154

RIP (Routing Information Protocol) (2)

q 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


155

RIP (Routing Information Protocol) (3)

q  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, q  ..então K substitui a sua entrada na tabela.

Roteador Roteador J Roteador K Roteador

Anúncio


156

RIP (Routing Information Protocol) (4) Tabela de K Atualização de J

Destino 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.


157

RIP: Recuperação de falhas q  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.


158

RIP: Recuperação de falhas - Exercício q 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).


159

OSPF (Open Shortest Path First) q  “Open” (aberto) à publicamente disponível q  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.

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

q  Anúncios disseminados para AS inteiro q  Via inundação – flooding.


160

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

(tentar) impedir intrusão maliciosa. q  Usa conexões TCP. q  Caminhos Múltiplos com custos iguais permitidos.

§  (o RIP permite e aceita apenas uma rota quando custos iguais).

q  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.

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


161

OSPF Hierárquico


162

IGRP (Interior Gateway Routing Protocol)

q  Proprietário da CISCO. q  Sucessor do RIP (final dos anos 80). q  Usa Vetor de Distâncias à assim como RIP. q  Diversas métricas de custo:

§  Atraso, largura de banda, confiabilidade, carga, etc...

q  Usa TCP para trocar mudanças de rotas. q  Roteamento via Distributed Updating Algorithm

(DUAL) baseado em computação difusa.


Roteamento Inter-AS

Exterior Gateway Protocols (EGP)

163


164

Roteamento Inter-AS


165

Roteamento inter-SA na Internet: BGP

q  BGP (Border Gateway Protocol) à o padrão de fato q  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


166

Roteamento inter-SA na Internet: BGP q  Suposição:

§  roteador X envia seu caminho para roteador para W.

q  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. q  Se W seleciona caminho até Z anunciado por X, então:

Caminho (W,Z) = W, Caminho (X,Z) q  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.


167

Por que há diferenças entre roteamento Intra e Inter-AS? Políticas: q  Inter-AS à administração quer controle sobre como tráfego roteado,

quem transita através da sua rede. q  Intra-AS à administração é única, portanto são desnecessárias

decisões políticas.

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

tráfego de atualização

Desempenho: q  Intra-AS: pode focar em desempenho. q  Inter-AS: políticas podem ser mais importantes do que desempenho.


168

Final da Camada de Rede

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

rede. q  Roteamento e Roteador. q  Endereços IP. q  Fragmentação e MTU. q  Sub-redes e máscaras. q  Princípio de roteamento:

seleção de caminhos.

q  Algoritmos de roteamento. §  Link state e distance

vector.

q  Roteamento hierárquico. q  Sistemas Autônomos. q  Protocolos de

roteamento da Internet.

Documents

Adriano Mauro Cansian adriano@acmesecurityadriano/aulas/... · unesp - IBILCE - SJRP 2 Capítulo 4: Camada de Rede Metas: q Entender os princípios em que se fundamentam os serviços