Rede de Computadores
MATA59 - Redes de
ComputadoresI
Universidade Federal da Bahia
Instituto de Matemática
Departamento de Ciência da Computação
Rede de Computadores
CAMADA DE REDE
Rede de Computadores
CAMADA DE REDE
Rede de Computadores
Camada de Rede
• Serviços da Camada de Rede oferecidos a camada
de transporte:
• serviço orientado a conexão
• serviço não orientado a conexão
• serviço confiável
• serviço não confiável
• Normalmente, serviços orientados a conexão
possuem confiabilidade
4
Rede de Computadores
Camada de Rede
• Serviços da Camada de Rede:
• conexão (orientado ou não)
• roteamento
• controle de congestionamento
• No serviço com conexão estabelece-se circuito
virtual
• O circuito virtual determina o roteamento uma
única vez para a conexão
• No serviço sem conexão as rotas podem se alterar
5
Rede de Computadores
Camada de Rede
• No serviço sem conexão cada pacote é roteado de
forma independente dos demais
• No serviço com conexão se estabelece a rota para
todos os pacotes da conexão, podendo-se reservar
banda para a conexão
6
Rede de Computadores
Roteamento
7
Rede de Computadores
Roteamento
• Propriedades:
• Correção
• Simplicidade
• Robustez
• Estabilidade
• Otimização
8
Rede de Computadores
Roteamento
• Tabela de Roteamento:
• Armazenam as rotas escolhidas
• Manualmente: inicialização do SO do roteador
• Dinamicamente: tempo de execução
• Algoritmo de Roteamento: Definem as regras e a
lógica seguida para escolha da rota
• Protocolo de Rotemamento:
• responsáveis pela divulgação de rotas e
atualização das tabelas de roteamento
• Implementam um ou mais algoritmos
9
Rede de Computadores
Roteamento Métricas
10
Rede de Computadores
Roteamento
• Métricas de roteamento:
• Largura de banda
• Tipo de carga
• Distância entre roteadores
• Congestionamento
• Número de hops
• Atraso
• Função de custo
11
Rede de Computadores
Roteamento
• Tipos: Estáticos e Dinâmicos
• Estático:
 Normalmente configurado manualmente
 A tabela de roteamento é estática
 As rotas não se alteram dinamicamente de acordo
com as alterações da topologia da rede
 Custo manutenção cresce de acordo com a
complexidade e tamanho da rede
 Sujeito a falhas de configuração
12
Rede de Computadores
Roteamento Estático
13
Rede de Computadores
Roteamento
• Tipos: Estáticos e Dinâmicos
• Dinâmico:
 Divulgação e alteração das tabelas de
roteamento de forma dinâmica
 Sem intervenção constante do administrador
 Alteração das tabelas dinamicamente de acordo
com a alteração da topologia da rede
 Adaptativo
 Melhora o tempo de manutenção das tabelas em
grandes redes
 Mas também está sujeito a falhas
14
Rede de Computadores
Roteamento Dinâmico
15
Rede de Computadores
Roteamento Direto
• Origem e Destino na mesma rede
10.35.143.10
Tabela de Roteamento
Destino
10.35.143.0
.......
Gateway
10.35.143.10
.......
10.35.143.0
Switch
10.35.143.15
• Várias topologias
– Lembrar que equipamentos de nível 2 não tratam endereço
de rede
16
Rede de Computadores
Roteamento Indireto
• Origem e Destino estão em redes diferentes
Tabela de Roteamento
Destino
10.35.143.10
10.35.143.0
0.0.0.0
Gateway
10.35.144.15
10.35.143.10
10.35.143.1
10.35.143.1
10.35.144.1
Router
10.35.143.0
10.35.144.0
Tabela de Roteamento
Destino
10.35.143.0
10.35.144.0
.......
17
Gateway
10.35.143.1
10.35.144.1
.......
Tabela de Roteamento
Destino
10.35.144.0
0.0.0.0
Gateway
10.35.144.15
10.35.144.1
Rede de Computadores
Roteamento
• Tipos de Protocolos de Roteamento:
• Não Adaptativos – Estáticos
• Algoritmo de Dijikstra
• Algoritmo de Inundação ( Flooding )
• Adaptativos - Dinâmicos
• Algotítmo de Distância Vetorial (Bellman-Ford)
• Algoritmo do Estado de Enlace (Short Path First)
18
Rede de Computadores
Algorítmo de Inundação
• Roteador envia pacotes para todas as suas
interfaces, exceto para aquela em que chegou
• Inunda a rede
• O pacote sempre alcança o destino
• Tráfego desnecessário
19
Rede de Computadores
Roteamento pelo Caminho mais Curto Algoritmo de Dijikstra
• Modelagem de Grafo:
• Arcos são linhas de comunicação (enlaces)
• Nós são roteadores
• Rotas são caminhos entre nós de um grafo
• Cada arco tem um peso indicando o custo do
enlace
20
Rede de Computadores
Algoritmo de Dijikstra
• Cada nó é rotulado por sua distância ao nó de
origem ao logo do menor caminho até então
• inicialmente todos os nós são rotulados com
infinito
• cada interação analisa-se a vizinhança do nó ativo
e escolhe-se o novo nó ativo
• Inicialmente os rótulos (labels) são provisórios,
quando se descobre que o label representa o menor
caminho possível ele se torna permanente
21
Rede de Computadores
Algoritmo de Dijikstra
10
B
C
4
4
2
6
A
D
F
22
12
8
7
8
E
2
G
Rede de Computadores
Roteamento Vetor Distância ( Roteamento
com Distância Vetorial ) Ex.: RIP
23
Rede de Computadores
Roteamento Vetor Distância ( Roteamento
com Distância Vetorial ) Ex.: RIP
É um algoritmo simples
– Um roteador mantém uma lista de todos as rotas
conhecidas em uma tabela
– Cada roteador divulga para os seus vizinhos as
rotas que conhece
– Cada roteador selecionas dentre as rotas
conhecidas e as divulgadas os melhores caminhos
24
Rede de Computadores
Vetor-Distância - Métrica
• A escolha do melhor caminho é baseada na
comparação da métrica do enlace
– Normalmente: Melhor = menor caminho
• A métrica é o custo de envio em um enlace
• Pode ser diferentes informações
–
–
–
–
25
Taxa de transmissão em bps
Vazão
Atraso
Número de saltos (no. de hops) (+ usado)
Rede de Computadores
Vetor-Distância – Métrica – Saltos
26
Rede de Computadores
Vetor-Distância - Procedimento
1. Quando o roteador executa o “boot” ele armazena na tabela
informações sobre cada uma das redes que estão
diretamente conectada a ele. Cada entrada na tabela indica
uma rede destino, o gateway para a rede e a sua métrica.
2. Periodicamente cada roteador envia uma cópia da sua tabela
para qualquer outro roteador que seja diretamente
alcançável.
3. Cada roteador que recebe uma cópia da tabela, verifica as
rotas divulgadas e suas métricas. O roteador soma à métrica
divulgada o custo do enlace entre ele e o roteador que fez a
divulgação. Após, compara cada uma das entradas da tabela
divulgada com as da sua tabela de roteamento. Rotas novas
são adicionadas, rotas existentes são selecionadas pela sua
métrica.
27
Rede de Computadores
Vetor-Distância - Procedimneto
3.1 Se a rota já existe na tabela e a métrica calculada é menor
do que a da rota conhecida, então remove a entrada anterior
e adiciona a nova rota divulgada.
3.2 Se a rota já existe na tabela e a métrica calculada é igual a
da rota conhecida, então não altera a entrada.
3.3. Se a rota já existe na tabela e a métrica divulgada é maior
do que a da rota conhecida, então verifica se o gateway para
esta rota é o mesmo que está fazendo nova divulgação
3.3.1 Se o gateway é o mesmo então altera a métrica para
esta rota
3.3.2 Se o gateway não é o mesmo não altera a rota
28
conhecida
Rede de Computadores
Distância Vetorial - Convergência
• Processamento rápido do algoritmo
• Convergência lenta
• ex: D demora para perceber queda do enlace
A
29
B
C
D
Rede de Computadores
Distância Vetorial - Convergência Lenta
Router 1
<R1,0>
Router 2
Router 3
<R2,0>
<R1,1>
<R3,0>
<R2,1>
<R1,2>
<R2,1>
<R1,0>
<R3,1>
<R2,0>
<R1,1>
<R4,0>
<R3,1>
<R2,2>
<R1,3>
Continua o processo ....
30
Router 4
Rede de Computadores
Distância Vetorial - Convergência Lenta
Router 1
<R1,0>
Router 2
Router 4
<R2,0>
<R1,3>
<R2,0>
<R3,1>
<R2,0>
<R1,5>
31
Router 3
<R3,0>
<R2,1>
<R1,4>
A rota somente será
Considerada infinita quando a
métrica atingir 16.
<R3,0>
<R2,1>
<R1,6>
Rede de Computadores
Distância Vetorial - Convergência Lenta - Soluções
• Split Horizon
– A informação de roteamento não deve ser
divulgada para a máquina que a originou
• Hold-Down
– Previne que mensagens de atualização
restabeleçam precipitadamente uma rota que caiu.
32
Rede de Computadores
Roteamento por Estado de Enlace – Ex.: OSPF
33
Rede de Computadores
Roteamento por Estado de Enlace – Ex.: OSPF
Cada roteador tem tarefas divididas em 5 partes:
1. Descobrir seus vizinhos e aprender seus endereços de rede
2. Medir o retardo ou custo até cada uma dos seus vizinhos
3. Criar um pacote que informe tudo que aprendeu ao seus
vizinhos
4. Enviar este pacote a todos os outros roteadores
5. Calcular o caminho mais curto até cada um dos outros
roteadores
34
Rede de Computadores
Estado do Enlace
• Baseado no conceito de mapas distribuídos
– todos os roteadores do mapa tem uma cópia
• O conteúdo das mensagens de atualização são as
ligações de um roteador a seus vizinhos, a
identificação do enlace e o custo.
• As informações divulgadas são acrescentadas ao
mapa de quem as recebe
• Caso, haja alterações do mapa devido a
divulgação as rotas são recalculadas.
35
Rede de Computadores
Estado do Enlace - Mapa
• Exemplo
A
1
3
B
2
C
4
5
D
E
6
De
A
A
B
B
B
C
C
D
D
E
E
E
Para
B
D
A
C
E
B
E
A
E
C
B
D
Enlace
1
3
1
2
4
2
5
3
6
5
4
6
• Cada registro é divulgado pelo roteador
“responsável”
36
Métrica
1
1
1
1
1
1
1
1
1
1
1
1
Rede de Computadores
Estado do Enlace – Inundação (Flooding)
A
1
3
B
2
C
Falha de comunicação
4
5
D
E
6
• A e B detectam a falha
• A e B alteram os registros na base de dados pelos
quais são responsáveis
• A gera atualização para D e B para C e E
• C, D e E irão desencadear novas atualizações
37
Rede de Computadores
Estado do Enlace – Inundação (Flooding)
• D enviará para E, C enviará para E e E enviará para
CeB
• Loop?
– Prevenção do loop é feita pela utilização de um número
de seqüência no pacote de atualização
• Algoritmo
Recebe mensagem
Seleciona registro na base
38
se o registro não está presente
então adiciona e envia uma mensagem em broadcast para os
vizinhos, exceto pelo enlace pelo qual foi recebida
Rede de Computadores
Estado do Enlace – Inundação (Flooding)
39
senão
se o número de seqüência da entrada na base < o número de
seqüência da mensagem
então atualiza e gera broadcast
senão
se número da base > o número de seqüência da
mensagem
então
gera uma nova divulgação
atualiza o número de seqüência da mensagem
envia a mensagem para interface pela qual foi
recebida
senão
se os números de seqüência são iguais não faz nada.
Rede de Computadores
Estado de enlace – Atualização - Exemplo
• Mensagem de A
– From A, to B, link 1,
distance = infinite,
number = 2.
• Mensagem de B
– From B to A, link 1,
distance = infinite,
number = 2
40
Tabela Final
De
A
A
B
B
B
C
C
D
D
E
E
E
Para
B
D
A
C
E
B
E
A
E
C
B
D
Enlace
1
3
1
2
4
2
5
3
6
5
4
6
Métrica
inf
1
inf
1
1
1
1
1
1
1
1
1
Seq.
2
1
2
1
1
1
1
1
1
1
1
1
Rede de Computadores
Estado do enlace – Atualização – Exemplo - Falha
A
1
3
B
2
Falha de comunicação
C
4
5
D
E
• Duas versões do mapa
Mapa 1 -BCE
Mapa 1 - AD
41
A B 1 inf
B A 1 inf
D E 1 inf
2
2
2
A B 1 inf
B A 1 inf
E D 1 inf
2
2
2
Rede de Computadores
Estado do enlace – Atualização - Exemplo
A
3
1
B
2
Falha de comunicação
C
4
5
D
E
• Mapa BCE sofrerá atualizações que não serão
refletidas no AD Mapa 1 -BCE
A B
B A
B C
C B
E D
42
1
1
2
2
1
inf
inf
inf
inf
inf
2
2
2
2
2
Rede de Computadores
Estado do enlace – Atualização – Exemplo - Restabelecimento
• Ao restabelecer a comunicação entre AD e BCE é
necessário que ocorra um processo de sincronização
• Pelo processo normal leva muito tempo para
convergir
• Sincronização - “data base description packets”
– 1.ª fase: nodo distribui o seu mapa
– 2.ª fase: solicita aos vizinhos os “registros interessantes”
– 3.ª fase: flooding
43
Rede de Computadores
Estado do Enlace - Problemas - No. de Sequência.
• Quando um roteador cai e volta rapidamente
– não terá sido retirado dos mapas dos outros hosts
– irá realizar o flooding com seu número de seqüência
incial
– esse número será mais antigo (menor) que os mantidos
nos mapas dos vizinhos
– então para acelerar a convergência, ele deve aceitar o
número de seqüência que os outros irão lhe enviar,
incrementá-lo e imediatamente retransmitir seus registros
com o novo número.
44
Rede de Computadores
Roteamento Hierarquico
• Regiões de roteamento
• Informações de rotas internas a região não se
propagam fora dela
• Rotas padrão
45
Rede de Computadores
Roteamento por Difusão ( Broadcasting )
• Envio de pacotes a todos os destinos
simultaneamente
• Pode usar o algoritmo que envia um pacote
específico para cada destino
• Pode usar o algoritmo de Inundação
• Pode usar o algoritmo de Roteamento para vários
destinos
• Pode usar o algoritmo de Árvore Invertida
46
Rede de Computadores
Roteamento por Multidifusão ( Multicasting )
• Envio de pacotes para Grupos
• Pode usar o algoritmo que envia um pacote específico
para cada membro do grupo ( poucos participantes )
• Pode usar o algoritmo de Inundação ( grupo com
muitos membros, próximo do total )
• Pode usar o algoritmo de Roteamento por
Multidifuão ( uma árvore invertida para cada grupo )
47
Rede de Computadores
Controle de Congestionamento
• Loop aberto: controle de tráfego de quem envia
para a rede, evitando o congestionamento
• Loop fechado: controle de tráfego no roteador,
tratando o congestionamento existente
• Caso a rede adote circuito virtual, estabelece-se
bandas de uso, assim há uma visão da banda total
da rede e evitando-se o congestionamento
48
Rede de Computadores
Controle de Congestionamento
• Loop Aberto:
• Algoritmo do Balde Furado: Limita a
informação que pode ser enfileirada para
transmissão de dados. Modela um buffer de
transmissão finito e taxa limite de transmissão
de mensagens provenientes do balde
• Algoritmo do Balde Furado de Tokens: cria
permissões (tokens) de envio de N bits a cada
intervalo de tempo. A mensagem tem de
utilizar os tokens, limita o tráfego, mas permite
rajadas
49
Rede de Computadores
Algoritmo de Balde Furado
50
Rede de Computadores
Algoritmo de Balde Furado
51
Rede de Computadores
Algoritmo Balde Furado- Tokens
52
Rede de Computadores
Algoritmo Balde Furado
53
Rede de Computadores
Controle de Congestionamento
• Loop Fechado:
• Rede com conexão: proíbe o estabelecimento
de novos circuitos virtuais e renegocia banda
dos existentes
• Rede sem conexão: descarte do pacote gera
pacote regulador informando roteadores do
congestionamento, estes aplicam alguma
técnica de controle com Loop Aberto
• Escoamento de carga: último recurso, descarta
todos os pacotes ou os de menor prioridade
54