Redes Cap5
Redes Cap5
controle
Algorítmo
de roteamento
plano de
controle
plano de
dados
valores do cabeçalho
no pacote que chega
0111 1
2
3
em roteadores plano de
dados
CA
CA CA CA CA
values in arriving
packet header
0111 1
2
3
congestionado”
aplicação
●
roteamento: um desafio de rede “top-10”! transporte
rede
enterprise enlace
network física
graph: G = (N,E)
N: conjunto de roteadores = { u, v, w, x, y, z }
E: conjunto de enlaces ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
5
3 O nó que tem o menor custo
v w 5
2 conhecido para u e que não
u 2 1 z está em N’ é o nó x.
3
1 2
x 1
y
5
O nó que tem o menor
3
v w 5 custo conhecido para u e
2
que não está em N’ é o nó v.
u 2 1 z
3
1 2
x 1
y
5
3 Passo 3
v w 5
2 u → x → y → w → z : custo 8
u 2 1 z
3
1 2
x 1
y
5
3 O nó que tem o menor custo
v w 5
2 conhecido para u e que não
u 2 1 z está em N’ é o nó w.
3
1 2
x 1
y
5
Passo 4
3
v w 5 u → x → y → w → z : custo 8
2
u 2 1 z
3
1 2
x 1
y
5
O nó que tem o menor
3 caminho para u e que não
v w 5
2 está em N’ é o nó z.
u 2 1 z
3
1 2
x 1
y
3,v
2) Qual é a distância mais curta até o nó v e qual nó é seu antecessor? Escreva sua
resposta como n,p
1,u
3) Qual é a distância mais curta até o nó z e qual nó é seu antecessor? Escreva sua
resposta como n,p
6,w
1) Para o link X, qual é o custo associado a esse link? Se a resposta não puder ser
determinada com base nas informações, responda com 'n/a'
Xé3
2) Para o link Y, qual é o custo associado a esse link? Se a resposta não puder ser
determinada com base nas informações, responda com 'n/a'
n/a
Equação Bellman-Ford
Seja Dx(y): custo do caminho de menor custo de x para y.
Then:
Dx(y) = minv { cx,v + Dv(y) }
Ideia chave:
●
de tempos em tempos, cada nó envia sua própria estimativa do vetor de distância
aos vizinhos
quando x recebe uma nova estimativa de DV de qualquer vizinho, ele atualiza seu
próprio DV usando a equação B-F:
Dx(y) ← minv{cx,v + Dv(y)} para cada nó y∊N
sob condições naturais menores, a estimativa Dx(y) converge para o menor custo
real dx(y)
Fonte: [Link]
●
se o DV mudar, notifique os vizinhos
●
t0: y detecta alterações no custo do enlace, atualiza seu DV e informa
seus vizinhos.
“boas
notícias ●
t1: z recebe atualização de y, atualiza seu DV, calcula o novo menor
viajam custo para x, envia seu DV para seus vizinhos.
ligeiro” ●
t2: y recebe a atualização de z, atualiza seu DV. os custos mínimos de
y não mudam, então y não envia uma mensagem para z.
(u,v,w,x,y) = (0,1,6,3,10)
(u,v,w,x,y) = (∞,5,0,3,∞)
Exemplo de SA
Fonte: [Link]
Fonte: [Link]
ip
Fonte: [Link]
search=[Link]
Fonte: [Link]
roteamento
3c 2c
intra-AS3a roteamento
3b 2aintra-AS
2b
1c
roteamento
AS3
1a intra-AS 1b AS2
1d
AS1
3c
3a other
2c
3b 2a networks
2b
1c
AS3
other 1a 1b AS2
networks
1d
AS1
roteamento
3c
roteamento
intra-AS
3a inter-AS roteamento
2c
3b 2a intra-AS
2b
1c
roteamento
AS3
1a intra-AS 1b AS2
1d
AS1
2b
2a 2c
∂
1b 3b
2d
1a 1c ∂
3a 3c
AS 2
1d 3d
AS 1 Conectividade eBGP AS 3
Conectividade lógica iBGP
quando o gateway AS3 3a anuncia o caminho AS3,X para o gateway AS2 2c:
●
AS3 promete ao AS2 que encaminhará datagramas para X
AS 3 3b
AS 1 1b 3a 3c
1a 1c AS 2 3d X
2b
1d Anúncio BGP:
2a 2c
AS3, X
2d
2d
O roteador AS2 2c recebe anúncio de caminho AS3,X (via eBGP) do roteador AS3 3a
baseado na política AS2, o roteador AS2 2c aceita o caminho AS3,X, propaga-se
(via iBGP)
com base na política AS2, o roteador AS2 2a anuncia (via eBGP) o caminho AS2,
AS3, X para o roteador AS1 1c
2024.2 – Redes de Computadores 69 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Anúncio de caminho BGP: vários caminhos
AS 3 3b
AS 1 1b AS3,X 3a 3c
AS3,X
AS3,X
1a 1c AS 2 3d X
2b
AS3,X
1d AS3, X
AS2,AS3,X 2a 2c
2d
O ISP deseja apenas rotear o tráfego de/para as redes de seus clientes (não deseja
transportar tráfego de trânsito entre outros ISPs – uma política típica do “mundo real”)
A anuncia o caminho Aw para B e para C
B opta por não anunciar BAw para C!
●
B não obtém “receita” pelo roteamento CBAw, uma vez que nenhum dos C, A, w
são clientes de B
●
C não aprende sobre o caminho CBAw
C irá rotear CAw (sem usar B) para chegar a w
2024.2 – Redes de Computadores 71 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Qual a diferença entre roteamento intra e
inter-AS
política:
●
inter-AS: o administrador deseja controlar como seu tráfego é roteado, quem
roteia através de sua rede
●
intra-AS: administrador único, portanto a política é menos problemática
escala:
●
o roteamento hierárquico economiza tamanho da tabela e reduz o tráfego de
atualização
desempenho:
●
intra-AS: pode focar no desempenho
●
inter-AS: a política domina o desempenho
Algorítmo
roteamento
plano de
controle
plano de
dados
valores do cabeçalho
no pacote que chega
0111 1
CA = Controle + Ação
2
3
Controlador Remoto
plano de
controle
plano de
dados
CA
CA CA CA CA
valores do cabeçalho
no pacote que chega
0111 1
2 CA = Controle + Ação
3
u 2
3
1 z
1
2
x 1 y
Os pesos dos links são apenas “botões” de controle: não há muito controle!
2024.2 – Redes de Computadores 77 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Engenharia de tráfego: difícil com roteamento
tradicional
5
3
2 v w 5
u 2
3
1 z
1
2
x 1 y
u 2
3
1 z
1
2
x 1 y
plano
●
tabela de fluxo (encaminhamento) API sentido norte controle
calculada, instalada sob supervisão do
controlador Controlador SDN
(SO de rede)
●
API para controle de switch baseado em
tabela (por exemplo, OpenFlow)
API sentido sul
➢
define o que é controlável e o que não é
●
protocolo para comunicação com o Plano
dado
controlador (por exemplo, OpenFlow)
Switches controladas SDN
Plano
dado
4 5
network
graph
RESTful
API
… intent 5 o aplicativo de roteamento de estado
3 … de link interage com o componente
statistics flow tables de computação de tabela de fluxo no
Link-state info host info … switch info
controlador SDN, que calcula as
2 novas tabelas de fluxo necessárias
OpenFlow … SNMP
6 controlador usa OpenFlow para
6
instalar novas tabelas em switches
1 que precisam de atualização
s2
s1
s4
s3
2024.2 – Redes de Computadores 84 Profa. Morganna Diniz - BSI/EIA/UNIRIO
SDN e o futuro dos protocolos de rede
tradicionais
Tabelas de encaminhamento computadas por SDN versus roteador-computador:
➢ apenas um exemplo de computação logicamente centralizada versus computação
por protocolo
pode-se imaginar o controle de congestionamento computado por SDN:
➢ o controlador define as taxas do remetente com base nos níveis de
congestionamento relatados
●
O ICMP fornece um mecanismo padronizado para que os dispositivos
de rede comuniquem informações vitais, como conectividade e status
da rede.
●
Todos os dispositivos conectados à rede, incluindo roteadores e
dispositivos do endpoint, podem processar mensagens ICMP.
●
O ICMP foi adaptado para funcionar com IPv4 e IPv6.
●
Os utilitários traceroute e ping usam o ICMP
●
Quando um dispositivo de rede envia uma mensagem ICMP, ele a empacota em um
datagrama IP. Encaminhe-o para o endereço de destino especificado mencionado no
cabeçalho IP.
●
Ao receber uma mensagem ICMP, um dispositivo de rede a descompacta do
datagrama IP. Em seguida, verifica os campos de tipo e código no cabeçalho ICMP.
Com base nestes valores, diferentes ações ou respostas podem ser desencadeadas.
3 probes 3 probes
3 probes
dispositivo gerenciado
dispositivo gerenciado
Fonte: [Link]