Rede de Computadores II
Rede de Computadores II
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 1
Rede de Computadores II
Roteamento
Determinar o melhor caminho a ser tomado da origem
até o destino.
Se utiliza do endereço de destino para determinar a
melhor rota.
Roteador default, é o roteador ligado diretamente ao
host (roteador do primeiro salto);
Caminho de menor custo, é o caminho cuja soma do
custo dos enlaces que ele percorre apresentam o menor
valor;
Caminho mais curto, o caminho com o menor número
de saltos (roteadores);
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 2
Rede de Computadores II
Tipos de Algoritmos de Roteamento
Global



Calcula o caminho de menor custo entre uma fonte e um destino
usando conhecimento completo e global sobre a rede;
Também denominado algoritmo de estado de enlace (Link State –
LS);
Tem de possuir informações completas sobre a conectividade e o custo
dos enlaces;
Descentralizado




O cálculo é realizado de forma distribuída e iterativa;
Não se tem conhecimento dos custos de todos enlaces da rede;
Baseia-se na troca de informações com o nó vizinho para cálculo da
rota;
Também denominado algoritmo de vetor de distâncias (DistanceVector algorithm – DV).
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 3
Rede de Computadores II
Tipos de Algoritmos de Roteamento
Algoritmos de Roteamento Estáticos


Tabelas fixas;
Alteradas de forma manual com pouca frequência;
Algoritmos de Roteamento Dinâmicos

As rotas são alteradas à medida que mudam as
cargas de tráfego ou a topologia da rede;
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 4
Rede de Computadores II
Congestionamento
Congestionamento, ocorre quando há mais
pacotes a serem transmitidos do que a rede
pode suportar.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 5
Rede de Computadores II
10 Mbits/s
Ethernet
A
B
1.5 Mbits/s
fila de pacotes
esperando pelo
enlace de saída
45 Mbits/s
D
Prof. Fábio Nelson
C
multiplexação estatística
CECOMP
Colegiado de Engenharia de Computação
E
Slide 6
Rede de Computadores II
Congestionamento
Causas...

link, roteadores, gargalos...
O Aumento de buffers resolve?
O controle de fluxo se baseia no tráfego ponto
a ponto entre um determinado transmissor e um
determinado receptor e exige alguma forma de
retroalimentação (feedback).
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 7
Rede de Computadores II
Controle de Congestionamento X
Controle de Fluxo
Controle de Congestionamento

Questão que envolve o comportamento dos terminais
e roteadores da rede, com o objetivo de garantir que
a rede seja capaz de dar conta do tráfego gerado.
Controle de Fluxo

Questão que envolve apenas tráfego ponto-a-ponto,
entre um emissor e um receptor, com o objetivo de
garantir que o emissor não gere dados a uma taxa
que o receptor não é capaz de consumir.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 8
Rede de Computadores II
Principios de Controle de
Congestionamento
Loops Abertos (prevenção)

Tentam resolver o problema com um bom projeto,
para, a princípio, garantir que nunca ocorrerão.
decidir quando aceitar novo tráfego
decidir quando descartar pacotes e quais pacotes
descartar
tomar decisões de escalonamento em vários pontos da
rede
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 9
Rede de Computadores II
Principios de Controle de
Congestionamento
Loops Fechados (detecção e correção)

Acontece em três fases:
Monitoramento do sistema;
Envio de informações;
Ajuste da operação do sistema para corrigir o
problema.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 10
Rede de Computadores II
Loops Fechados
Várias unidades métricas podem ser usadas
para monitorar a sub-rede quanto à ocorrência
de congestionamentos.





Percentual de pacotes descartados nos buffers
Tamanho médio das filas dos buffers
Número de pacotes retransmitidos por timeout
Atraso médio dos pacotes
Desvio padrão de atraso dos pacotes
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 11
Rede de Computadores II
A segunda etapa do loop de retroalimentação é
transferir informações sobre o congestionamento
do ponto em que o fenômeno é detectado para o
ponto em que algo pode ser feito em relação a
ele.

Pode ocorrer o aumento de carga no momento em que
é necessária a sua diminuição!
Outra abordagem é fazer com que os hosts e
roteadores enviem pacotes de sondagem, para
averiguar a existência de congestionamento.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 12
Rede de Computadores II
Políticas de Prevenção de
Congestionamento
Transporte






Política de
retransmissão
Política de cache fora
de ordem
Política de de
confirmação
Política de controle de
fluxo
Determinação de
timeout
CECOMP
Prof. Fábio Nelson
Rede


Política de descarte
de pacotes
Algoritmo de
roteamento
Gerenciamento da
duração do pacote
Enlace de dados
Política de
retransmissão
 Política de cache fora
de ordem
Slide 13
Colegiado de Engenharia de Computação
 Política de

Rede de Computadores II
Controle de Congestionamento
Cada roteador pode monitorar facilmente a
utilização de suas linhas de saída e de outros
recursos.
Cada roteador pode manter uma variável u,
para cada enlace, refletindo o percentual de
utilização desse enlace.
Se o valor de u passar um limite estabelecido
(threshold), o enlace entra em estado de alerta
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 14
Rede de Computadores II
bit de Advertência
Seta um bit especial no cabeçalho da
mensagem.
No receptor, a entidade de transporte copia o bit
no ACK enviado de volta para o emissor .
Problema dessa estratégia

Tempo necessário para a informação retornar ao
emissor.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 15
Rede de Computadores II
Pacotes Reguladores
O roteador envia um pacote regulador (choke
packet) diretamente ao host de origem,
informando o destino encontrado no pacote.
O pacote é rotulado (bit no cabeçalho) para não
gerar mais pacotes desse tipo no caminho de
volta.
O emissor reduz a taxa de envio de pacotes
para esse destino até as condições melhorarem
Uma variação é usar outros sinais (ao invés do
percentual de utilização do enlace): tamanho da
Prof.fila
Fábiodo
Nelson
Slide 16
buffer ou utilização do buffer.
CECOMP
Colegiado de Engenharia de Computação
Rede de Computadores II
Pacotes Reguladores hop a hop
O pacote regulador passa a ter efeito em todo o
hop que ele passa, aumentando o tamanho dos
buffers nesses hops.
Alívio mais imediato do ponto de
congestionamento.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 17
Rede de Computadores II
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 18
Rede de Computadores II
Escoamento de Carga
Um roteador “inundado”, escolhe os pacotes
que irá redirecionar.
A decisão sobre quais pacotes descartar pode
depender da aplicação:



em aplicações de transferência de arquivos, um
pacote velho é mais importante que um pacote novo
em aplicações de áudio e vídeo, um pacote novo é
mais importante que um pacote velho
em aplicações de transferência de documentos com
imagens e texto, perder uma linha de pixels de uma
figura é melhor que perder uma linha de texto
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 19
Rede de Computadores II
Detecção Aleatória Prematura
RED – Random Early Detection
Descarte antecipado de pacotes


Tratar o problema de congestionamento assim que
ele apresentar sinais, descartando pacotes antes que
o espaço do buffer fique saturado.
Leva em conta o fato de ser aplicado em redes
cabeadas, onde a perda de pacotes acontece
principalmente devido ao estouro dos buffers, ao
invés de erros de transmissão, e a resposta
normalmente é reduzir a taxa de envio.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 20
Rede de Computadores II
Detecção Aleatória Prematura
A idéia de antecipar o descarte de pacotes é ter
tempo para a ação causar efeito a tempo de
resolver o problema.
Mas, como avisar o emissor que o seu pacote
foi descartado?


Uma forma é enviar um pacote regulador de alerta.
Uma alternativa é descartar o pacote e não avisar.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 21
Rede de Computadores II
Controle de Flutuação (jitter)
Para aplicações de áudio e vídeo não faz muito
diferença se o atraso no tempo de entrega dos
pacotes é de 10mseg ou 20mseg, desde que o
trânsito seja constante.
A variação, ou desvio padrão, no tempo de
entrega dos pacotes é chamada de flutuação
(jitter).
Valores altos de jitter (ex. variações entre
10mseg e 20mseg) ocasionam perda da
qualidade da informação recebida.
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 22
Rede de Computadores II
Jitter == lag
Prof. Fábio Nelson
CECOMP
Colegiado de Engenharia de Computação
Slide 23
Rede de Computadores II
Controle de Flutuação (jitter)
Quando um pacote chega no roteador, o seu
tempo é verificado e o pacote é rotulado se ele
está adiantado ou atrasado em relação ao
tempo previsto.
O roteador da prioridade para os pacotes
atrasados e posterga a transmissão de pacotes
adiantados.
Em aplicações de vídeo sob demanda, o jitter
pode ser eliminado colocando os dados em um
buffer no receptor e repassando-os em seguida
Prof. Fábio Nelson
Slide 24
para a aplicação.
CECOMP
Colegiado de Engenharia de Computação