46
Redes de Computadores I - Princípios de Roteamento por Helcio Wagner da Silva

Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

  • Upload
    dothien

  • View
    231

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Redes de Computadores I- Princípios de Roteamento

por

Helcio Wagner da Silva

Page 2: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Classificação dos Algoritmos

• Globais x Descentralizados– Globais

• Algoritmo considera com dados de cálculo aconectividade entre todos os nós e todos os custos dosenlaces

• Também chamados de algoritmos de estado de enlace,ou LS (Link State)

– Descentralizados• Nenhum nó tem informação completa sobre os custos

de todos os enlaces da rede

• Também chamados de algoritmos de vetor dedistâncias, ou DV (Distance Vector)

2

Page 3: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Classificação dos Algoritmos

• Roteamento estático x roteamento dinâmico

– Roteamento estático

• As rotas mudam muito lentamente ao longo dotempo, muitas vezes por intervenção humana

– Roteamento dinâmico

• As rotas mudam à medida em que mudam as cargasde tráfego ou a topologia da rede

3

Page 4: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Classificação dos Algoritmos

• Sensíveis à carga x insensíveis à carga

– Sensíveis à carga

• Custo de um enlace varia dinamicamente pra refletirseu nível de congestionamento

• Se houver um enlace com alto custo, o algoritmotenderá a escolher rotas que o evitem

– Insensíveis à carga

• Custo de um enlace não reflete explicitamente seunível de congestionamento

4

Page 5: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmos LS

• Estado global é conhecido pela difusão dedatagramas de estado de enlace

• Algoritmo de Dijkstra

– Menor custo entre origem (u) e destino (v)

u p(v) vD(v)

D(v): custo do caminho de menor custo entre u e v p(v): vizinho de v ao longo do caminho de menor custoN’: subconjunto de nós ao longo do caminho entre u e v 5

Page 6: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo LS

INICIALIZAÇÃON’ = {u}para todos os nós v

se v for um vizinho de uentão D(v) = c(u,v)senão D(v) = ∞

LAÇOencontre w não em N’, tal que D(w) é um mínimoadicione w a N’atualize D(v) para cada vizinho v de w e não em N’:

D(v) = min(D(v), D(w) + c(w,v))/* o novo custo para v é o antigo custo para v ouo custo do menor caminho conhecido até w mais

o custo de w a v */ATÉ N = N’

6

Page 7: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo LS

u

v

x y

w

z

5

2

2

1

1

3

3

1

5

2

7

Page 8: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo LS

Etapa N’ D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)

0 u 2,u 5,u 1,u ∞ ∞

1 ux 2,u 4,x 2,x ∞

2 uxy 2,u 3,y 4,y

3 uxyv 3,y 4,y

4 uxyvw 4,y

5 uxyvwz

8

Page 9: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Oscilações com Roteamento de LS

• Roteamento inicial

z

w

y

x

1 1

e

e

0

1

0

0

1 + e

9

Page 10: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Oscilações com Roteamento de LS

• x e y detectam melhor caminho até w emsentido horário

z

w

y

x

1 1

e

0

1

2 + e

0

1 + e

0

10

Page 11: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Oscilações com Roteamento de LS

• x, y e z detectam melhor caminho até w emsentido anti-horário

z

w

y

x

1 1

e

1 + e

0

0

1

0

2 + e

11

Page 12: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Oscilações com Roteamento de LS

• x, y e z detectam melhor caminho até w emsentido horário

z

w

y

x

1 1

e

0

1

2 + e

0

1 + e

0

12

Page 13: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Oscilações com Roteamento de LS

• Sugestões para se evitar a oscilação

1. Fazer com que os custos independessem daquantidade de tráfego carregada

• Inaceitável, já que um dos objetivos do roteamento ése evitar enlaces congestionados

2. Assegurar que os roteadores não executem oalgoritmo LS ao mesmo tempo

• Roteadores tendem a se auto-sincronizar

3. Variar aleatoriamente o instante em que osroteadores enviem anúncios de enlaces

13

Page 14: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo DV

• Distribuído

– Cada nó recebe informações de um ou mais vizinhos,realiza cálculos e, depender dos resultados, os distribuiaos seus vizinhos

• Iterativo

– Processo continua até que mais nenhuma informação sejatrocada entre vizinhos

• Assíncrono

– Não requer que todos os nós o executemsimultaneamente

14

Page 15: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo DV

• Cada nó x mantém os seguintes dados:

– Para cada vizinho v, o custo c(x,v) de x até v

– O vetor de distâncias de x, i.e., Dx = [Dx(y) | y emN]

– Os vetores de distâncias de seus vizinhos, i.e., Dv =[Dv(y) | y em N] para cada vizinho v de x

15

Page 16: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo DV

INICIALIZAÇÃO:para todos os destinos y em N:

Dx(y) = c(x,y) /* se y não é um vizinho, então c(x,y) = ∞para cada vizinho w

Dw(y) = ∞ para todos os destinos y em Npara cada vizinho w

envia um vetor de distâncias Dx = [Dx(y) | y em N] para wLAÇO

ESPERE (até que ocorra uma mudança no custo do enlace ao vizinho wou até a recepção de um vetor de distâncias do vizinho w)

para cada y em N:Dx(y) = minv[c(x,v) + Dv(y)]

SE Dx(y) mudou para algum destino y ENTÃO envia um vetor de distâncias Dx = [Dx(y) | y em N]

para todos os vizinhosPARA SEMPRE

16

Page 17: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo DV

x

y

z

2 1

7

17

Page 18: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Algoritmo DV

x y z

x 0 2 7y ∞ ∞ ∞z ∞ ∞ ∞

x y z

x ∞ ∞ ∞y 2 0 1z ∞ ∞ ∞

x y z

x ∞ ∞ ∞y ∞ ∞ ∞z 7 1 0

De

Custo até

Custo até

De

De

Custo até

x

y

z

x y z

x 0 2 3y 2 0 1z 7 1 0

x y z

x 0 2 7y 2 0 1z 7 1 0

x y z

x 0 2 7y 2 0 1z 3 1 0

De

Custo até

Custo até

De

De

Custo até

x

y

z

x y z

x 0 2 3y 2 0 1z 3 1 0

x y z

x 0 2 3y 2 0 1z 3 1 0

x y z

x 0 2 3y 2 0 1z 3 1 0

De

Custo até

Custo até

De

De

Custo até

x

y

z

18

Page 19: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

19

Mudança: Custo do Enlace Diminuiu

X

Y

Z

41

50

1

x y z

x 0 4 5y 4 0 1z 5 1 0

x y z

x 0 4 5y 4 0 1z 5 1 0

x y z

x 0 4 5y 4 0 1z 5 1 0

De

Custo até

Custo até

De

De

Custo até

x

y

z

x y z

x 0 4 5y 4 0 1z 5 1 0

x y z

x 0 4 5y 1 0 1z 5 1 0

x y z

x 0 4 5y 4 0 1z 5 1 0

De

Custo até

Custo até

De

De

Custo até

x

y

z

Page 20: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

20

Mudança: Custo do Enlace Diminuiu

x y z

x 0 4 5y 4 0 1z 5 1 0

x y z

x 0 4 5y 1 0 1z 5 1 0

x y z

x 0 4 5y 4 0 1z 5 1 0

Custo até

Custo até

x

y

z

x y z

x 0 4 5y 1 0 1z 5 1 0

x y z

x 0 4 5y 1 0 1z 5 1 0

x y z

x 0 4 5y 1 0 1z 2 1 0

Custo até

Custo até

x

y

z

x y z

x 0 4 5y 1 0 1z 2 1 0

x y z

x 0 4 5y 1 0 1z 2 1 0

x y z

x 0 4 5y 1 0 1z 2 1 0

Custo até

Custo até

x

y

z

Custo até Custo até Custo até

De De De

De

DeDeDe

De De

Page 21: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

21

Mudança: Custo do Enlace Aumentou

X

Y

Z

41

50

60

x y z

y 4 0 1z 5 1 0

x y z

y 4 0 1z 5 1 0

Custo até

De

De

Custo até

y

z

x y z

y 6 0 1z 5 1 0

x y z

y 4 0 1z 5 1 0

Custo até

De

De

Custo até

y

z

Datagrama é transmitido...

... e ricocheteado!

Page 22: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

22

Mudança: Custo do Enlace Aumentou

x y z

y 6 0 1z 5 1 0

x y z

y 4 0 1z 5 1 0

Custo até

De

De

Custo até

y

z

x y z

y 6 0 1z 5 1 0

x y z

y 6 0 1z 7 1 0

Custo até

De

De

Custo até

y

z

x y z

y 8 0 1z 7 1 0

x y z

y 6 0 1z 7 1 0

Custo até

De

De

Custo até

y

z

x y z

y 51 0 1z 50 1 0

Custo atéy

x y z

y 51 0 1z 50 1 0

Custo atéy

...

... De

De

Page 23: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

23

Mudança: Custo do Enlace Aumentou

X

Y

Z

4

9999

10000

Refaça o problema anterior supondo os custos e a mudança ao lado.

Saiba porque esse problema é tambémchamado de problema de contagem

ao infinito.

1

Page 24: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

24

Reversão Envenenada

X

Y

Z

41

50

60

Rota de Z até X passa por Y.

DZ(X) =

x y z

y 4 0 1z 1 0

x y z

y 4 0 1z 5 1 0

Custo até

De

De

Custo até

y

z

x y z

y 60 0 1z 1 0

x y z

y 4 0 1z 5 1 0

Custo até

De

De

Custo até

y

z

Page 25: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

25

Reversão Envenenada

x y z

y 60 0 1z 1 0

x y z

y 4 0 1z 5 1 0

Custo até

De

De

Custo até

y

z

x y z

y 60 0 1z 1 0

x y z

y 60 0 1z 50 1 0

Custo até

De

De

Custo até

y

z

x y z

y 51 0 1z 50 1 0

x y z

y 60 0 1z 50 1 0

Custo até

De

De

Custo até

y

z

x y z

y 51 0 1z 50 1 0

x y z

y 0 1z 50 1 0

Custo até

De

De

Custo até

y

z

Deixa de envenenar, pois a rota Z → X não passa mais por Y

Envenena, pois a rota Y → X passa agora por Z

Page 26: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

26

Comparação entre Algoritmos

PARÂMETRO ESTADO DE ENLACE VETOR DE DISTÂNCIAS

Complexidade das Mensagens

• Mensagens trocadas entre todos os nós

•Alterações de custo propagadasindiscriminadamente

• Mensagens trocadas apenas entre vizinhos

• Alterações de custo propagadas apenas se alteram

caminho mais curto

Convergência Completamente previsível

• Pode ser lenta (contagem até o infinito)

• Pode haver laços de roteamento.

Robustez

• Nós podem anunciar incorretamente caminhos de

menor custo para seus vizinhos• Cálculo isolado das rotas

proporciona maior robustez

• Nós podem anunciar incorretamente caminhos de menor custo para quaisquer

destinos• Cálculo distribuído de rotas traduz-se em menor robustez

Page 27: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Roteamento Hierárquico

• Motivos

– Escalabilidade

• Um algoritmo (LS ou DV) sendo executado por todos osroteadores de uma malha extensa demoraria aconvergir

– Autonomia administrativa

• As empresas normalmente não desejam expor aopúblico externo como a sua malha de roteadores estáconfigurada, por motivos de segurança

27

Page 28: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Sistemas Autônomos (SAs)

28

1c

1a 1b

1d

3c

3b

3a

2c

2a 2b

SA1

SA3

SA2

Roteadores de borda

Page 29: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Protocolos de Roteamento

• Protocolos de roteamento intra-SA

– Executados no âmbito de um SA específico

– Exemplos

• RIP

• OSPF

• Protocolo de roteamento inter-SA

– Executado em todos os SAs

– Exemplo

• BGP

29

Page 30: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Protocolos de Roteamento

30

1c

1a 1b

1dSA1

Protocolo Inter-SA

Tabelade

Roteamento

Protocolo Intra-SA

Page 31: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

RIP

• RIP ↔ Routing Information Protocol

– RIPv1: RFC 1058

– RIPv2 (compatível com a v1): RFC 1723

• Implementa um algoritmo DV

• RIPv1 atribui a todo enlace um custo de 1

– Roteamento reduz-se à resolução do problema decontagem mínima de saltos

31

Page 32: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

RIP

• Custo máximo é limitado a 15

– RIP limita-se a SAs que têm menos de 15 saltos dediâmetro

32

A B

DC

u v

w

x

yz

Destino Saltos

u 1

v 2

w 2

x 3

y 3

z 2

Page 33: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

RIP

• Tabelas de roteamento são trocadas a cada 30segundos em anúncios RIP

• Cada anúncio contém

– Uma tabela de até 25 sub-redes

– As distâncias entre o remetente e cada umadessas sub-redes

33

Page 34: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

RIP

34

A B XDw x y

z

C

Destino Próximo Roteador Saltos

w A 2

y B 2

z B 7

x - 1

... ... ...

Tabela de roteamento de D

Page 35: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

RIP

35

A B XDw x y

z

C

Destino Próximo Roteador Saltos

w A 2

y B 2

z B A 7 5

x - 1

... ... ...

Tabela de roteamento de D (corrigida)

Destino Próximo Roteador Saltos

z C 4

w - 1

x - 1

... ... ...

Anúncio de A

Anúncio de A

Page 36: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

RIP

• Se um roteador não recebe nada de seu vizinhoem 180 segundos

1. O vizinho será considerado inatingível

2. O roteador modifica sua tabela de roteamento ea difunde aos demais vizinhos

• Um roteador pode solicitar informações sobreo seu vizinho usando mensagens de solicitaçãoRIP

• O RIP é um protocolo de aplicação36

Page 37: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Transporte(UDP)

Rede (IP)

RIP

37

Tabela deRoteamento

Enlace

Físico

routed

Transporte(UDP)

Rede (IP)

Tabela deRoteamento

Enlace

Físico

routed

520

Page 38: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

OSPF

• OSPF ↔ Open Shortest Path First

– RFC 2178 (OSPF v2)

• Implementa um algoritmo LS (Dijkstra)

• Custos dos enlaces configurados peloadministrador, podendo ser

– Todos iguais a 1

• Roteamento de salto mínimo

– Inversamente proporcionais às capacidades dosenlaces

38

Page 39: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

OSPF

• Estados de enlaces são transmitidosperiodicamente a cada 30 minutos

39

IP

OSPF Mensagem OSPF..

...encapsulado porum datagrama IP

Protocolo de Nível Superior = 89 (OSPF)

Nível de Rede

Page 40: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

Configuração de um AS OSPF

40

X

XX

XX X

X

XX

X

X

X

X

X

X

Backbone

Área 1Área 2

Área 3

Roteador de borda

Roteador de backbone

Roteador deBorda de área

Roteador interno

Page 41: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

BGP

• BGP ↔ Border Gateway Protocol

– RFC 1771 (BGP4)

• Objetivos

1. Obter de SAs vizinhos informações deatingibilidade de sub-redes

2. Propagar a informação de atingibilidade a todosos roteadores internos ao SA

3. Determinar rotas “boas” para sub-redes combase na informação de atingibilidade e napolítica do SA 41

Page 42: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

BGP

42

1c

1a 1b

1d

3c

3b

3a

2c

2a 2b

SA1

SA3

SA2

Sessão iBGPSessão eBGP

Conexões TCPSemi-permanentes

(porta 179)

Page 43: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

BGP – Políticas de Roteamento

• Como impedir que x repasse tráfego entre B e C ? 43

w x

y

A

B

C

Page 44: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

BGP – Políticas de Roteamento

44

w x

y

A

B

C

• É só impedir que x anuncie a rota xCy a B!

Anúncio da Rota xCy

Page 45: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

BGP – Políticas de Roteamento

45

w x

y

A

B

C

Anúncio da Rota BAw

Anúncio da Rota Aw

Anúncio da Rota BAw

• Qual a conseqüência de se enviar o anúncioBAw a C ?

Page 46: Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento estático x roteamento dinâmico –Roteamento estático •As rotas mudam muito

BGP – Políticas de Roteamento

46

w x

y

A

B

C

Anúncio da Rota BAw

Anúncio da Rota Aw

Anúncio da Rota BAw

• B rotearia um tráfego que não teria origemnem destino em seus clientes