Upload
dothien
View
231
Download
0
Embed Size (px)
Citation preview
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