Redes de Computadores I - Princípios de Roteamento · Classificação dos Algoritmos •Roteamento...

Redes de Computadores I- Princípios de Roteamento

por

Helcio Wagner da Silva

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

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

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

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

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

Algoritmo LS

u

v

x y

w

z

5

2

2

1

1

3

3

1

5

2

7

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

Oscilações com Roteamento de LS

• Roteamento inicial

z

w

y

x

1 1

e

e

0

1

0

0

1 + e

9

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

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

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

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

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

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

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

Algoritmo DV

x

y

z

2 1

7

17

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

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

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

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!

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

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

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

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

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

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

Sistemas Autônomos (SAs)

28

1c

1a 1b

1d

3c

3b

3a

2c

2a 2b

SA1

SA3

SA2

Roteadores de borda

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

Protocolos de Roteamento

30

1c

1a 1b

1dSA1

Protocolo Inter-SA

Tabelade

Roteamento

Protocolo Intra-SA

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

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

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

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

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

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

Transporte(UDP)

Rede (IP)

RIP

37

Tabela deRoteamento

Enlace

Físico

routed

Transporte(UDP)

Rede (IP)

Tabela deRoteamento

Enlace

Físico

routed

520

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

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

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

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

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)

BGP – Políticas de Roteamento

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

w x

y

A

B

C

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

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 ?

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