Teleinformática e Redes 1 - Convergência de Redes - Parte 1 - Políticas de Enfileiramento e Qualidade de Serviço

Prévia do material em texto

Convergência de 
Redes
Parte 1 - Políticas de 
Enfileiramento e Qualidade 
de Serviço
Profa. Priscila Solís Barreto
2
Motivação: Gerenciamento de 
Tráfego e de Recursos
 recursos compartilhados 
estatísticamente
 Sobrecarga causa congestionamento
 Pacote atrsado ou descartado 
 Desempenho da aplicação 
prejudicado
 Local vrs. Grande rede
 Temporal vrs. persistente
 Desafío:
 alta utilização de recursos
 Alto desempenho da aplicação
� 
Demandai� (t) > Recurso(t)
3
Enfoques para o 
gerenciamento de recursos 
 Aumentar recursos
 Instalar novos enlaces, roteadoes mais rápidos
 Planejamento de capacidade, provisionamento, 
engenharia de tráfego
 Acontecem em escalas maiores de tempo
 Reducir ou atrasar a demanda 
 Enfoque reativo: fazer com que todos reduzam a 
demanda
 Enfoque da reserva: alguns pedidos serão 
rejeitados pela rede
� 
Demandai� (t) > Recurso(t)
4
O Controle de 
Congestionamento na Internet
 Solução end-system-only 
(TCP)
 Dinamicamente se estima 
o estado da rede
 Perda de pacotes indica 
congestionamento
 Se reduz a taxa de 
transmissão na presença 
de congestionamento
 Roteadores ? Função 
mínima 
TCP
TCP
TCP
Controle 
Escala de tempo
Meses
Capacidade de 
planejamento
RTT (ms)
Feedback 
Control
5
Mais idéias sobre 
gerenciamento de tráfego 
 Melhorar o TCP
 Permanecer com uma arquitetura end-point only 
 Melhorar roteadores para ajudar o TCP 
 Random Early Discard 
 Melhorar roteadores para controlar o tráfego 
 Limitação da taxa
 Enfileiramento justo 
 Prover QoS ao limitar o congestionamento 
6
Mecanismos do Roteador
 Gerenciamento do Buffer : quando e que pacote 
descartar ? 
 Escalonamento: que pacote transmitir logo 
enseguida?
1
2
Scheduler
flow 1
flow 2
flow n
Classifier
Buffer 
gerenciamento
Os planos de Dados e Controle 
do Roteador
7
Switching
Fabric
Processor
Line card
Line card
Line card
Line card
Line card
Line card
data plane
control plane
8
Visão Geral
 Gerenciamento de Filas e RED
 Para que o QOS?
 Príncipios de QOS
 Introdução a políticas de Escalonamento
 Serviços Integrados
9
Políticas de Enfileiramento
 Cada roteador deve implementar alguma 
disciplina de enfileiramento
 O enfileiramento aloca ambos a largura de 
banda e o espaço de buffer:
 largura de banda: qual pacote trasmitir
 Espaço de buffer: qual pacote descartar
 O enfileiramento também afeta a latência
10
Enfileiramento Típico da 
Internet 
 FIFO + drop-tail
 Opção mais simples 
 Usado amplamento na Internet
 FIFO (first-in-first-out) 
 Implica em uma única classe de tráfego
 Drop-tail
 Pacotes que chegam são descartados quando a fila está cheia, 
independentemente da importança do fluxo
 Distinção importante:
 FIFO: disciplina de escalonamento
 Drop-tail: política de descarte 
11
Problemas no FIFO + Drop-tail
 Deixa a responsabilidade do 
congestionamente para as bordas (e.g., 
TCP)
 Não faz separação entre fluxos diferentes
 Sem policiamento: mandar mas pacotes na 
lógica de receber mais serviços
 Sincronização: hosts finais reagem aos 
mesmos eventos
FIFO e Drop-Tail
 Acesso à largura de banda
 Pacotes são somente diferenciados quando 
chegam
 Acesso ao espaço de buffer
 Se a fila está chéia, descartar o próximo pacote
12
✗
13
Problemas
 Filas chéias
 Os roteadores são forçados a ter grandes filas 
para manter altas utilizações
 TCP detecta congestionamento pela perda
 Força a rede a ter filas longas en steady-state
 Problema de Lock-out
 Os roteadores Drop-tail tratam o tráfego bursty 
muito mal
 O tráfego se sincroniza facilmente  permite que 
poucos fluxos monopolizem o espaço da fila
14
Gerenciamento de Fila Ativa
 Projeto de fila de gerenciamento ativa para 
controle de congestionamento
 Porque?
 O roteador tem uma visão unificada do 
comportamento de enfileiramento
 Os roteadores percebem a ocupação atual da fila 
(conseguem distinguir atraso de fila de atraso de 
propagação)
 Os roteadores podem decidir sobre 
congestionamento temporal, com base na carga 
de trabalho
15
Objetivos do Projeto
 Mantar o throughput alto e o atraso baixo
 alta potência(throughput/atraso)
 Acomodar explosões
 Tamanho da fila deve refletir a habilidade de 
aceitar bursts em vez de aceitar bursts para 
enfileiramento steady-state
 Melhorar o desempenho do TCP com 
mudanças mínimas de hardware
Política de Enfileiramento : 
Fair Queuing (FQ)
 Mantém uma fila separada por fluxo
 Garante que nenhum fluxo consuma mais de 1/n
 Variação: weighted fair queuing (WFQ)
 Se todos os pacotes tivessem o mesmo tamanho seria 
muito fácil
 Se os recursos tem intervalos ociosos, também seria fácil
16
Round
Robin
Service
Enlace de Saída
Fluxo 1
Fluxo 2
Fluxo 3
Fluxo 4
Conceitos do Fair Queuing
 Acompanhar quanto tempo cada fluxo tem 
usado o enlace
 Computar o tempo usado se transmite o seguinte 
pacote
 Mandar o pacote do fluxo que tem o menor 
uso, se quer transmitir o seguinte pacote
 Porque não o fluxo somente com o menor uso?
 Por que o próximo pacote pode ser grande !
17
Algoritmo FQ
 Assumir um clock tick por bit, então tempo tx ~ tamanho
Tempo final Fi = max (Fi-1, Tempo de chegada Ai ) + 
Tamanho Pi
 Calcular o tempo estimado Fi para todos os pacotes nas 
filas 
 Transmitir enseguida o pacote com o Fi mais baixo
18
Algoritmo FQ (2)
 Problema: Não são considerados os pacotes em tx
 Resultado: fluxos inativos (Ai > Fi-1) são penalizados
 O algoritmo padrão não considera a história
 Cada fluxo recebe justiça em relação aos pacotes na fila
19
Algoritmo FQ (3)
 Enfoque : dar mais prontidão aos fluxos com 
utilização histórica menor de largura de banda
 Bid Bi = max (Fi-1, Ai – δ) + Pi
 Intuição: com δ grandes, as decisões de escalonamento 
calculadas pelo último tempo tx Fi-1 mais frequentemente, dando 
preferência aos fluxos mais lentos
 FQ alcança uma justiça max-min 
 Primeira prioridade: maximizar a taxa mínima dos fluxos 
ativos
 Segunda prioridade : maximiar a seguinte taxa mínima, etc. 
20
Usos do (W)FQ
 Escalabilidade
 O número de filas deve ser igual ao número de 
fluxos
 (W)FQ pode ser para classes de tráfego, não 
somento fluxos
 Usar os bits TOS do IP para marcar a importança
 Parte da arquitetura de Serviços Diferenciados 
(DS) para QoS 
21
22
Política de Descarte : 
Problema de Lock-out
 Descarte Aleatório
 pacote que chega quando a fila está chéia causa 
um pacote aleatório de ser descartado
 Descarte frontal 
 Na fila chéia, descartar pacote na cabeça da fila
 O descarte da fila e o descarte frontal 
resolvem o problema de lock-out mas não o 
problema de filas chéias
Perdas Explosivas no 
Enfileiramento Drop-Tail
 O TCP depende na perda de pacotes 
 A perda de pacotes é um indicador de congestionamento
 E o TCP leva a rede à perda pelo incremento aditivos da 
taxa
 O Enfileiramento Drop-tail leva a perdas explosivas 
 Se o enlace está congestionado, muitos pacotes encontram 
a fila chéia
 Então se perde o sincronismo :
 Muitos fluxos perdem um ou mais pacotes
 Como resposta, muitos fluxos dividem a taxa de envio pela 
metade 
23
Feedback Lento no Drop Tail
 O Feedback chega quando o buffer está 
completamente chéio 
 … even though the buffer has been filling for a while
 Ainda, o buffer chéido aumenta o RTT
 …fazendo a deteção ainda mais lenta 
 Pode ser melhor ter um feedback mais rápido
24
25
Problemadas Filas Chéias
 Descartar pacotes antes da fila ficar 
chéia (early drop)
 Intuição: notificar aos emissores de 
‘congestionamento incipiente’:
 Exemplo: early random drop (ERD):
 Se qlen > nível de descarte, descartar cada novo 
pacote com probabilidade fixa de p
26
Random Early Detection (RED)
 Detectar congestionamento incipiente
 Assumir que hosts respondem aos pacotes 
perdidos
 Evitar sincronização de janelas
 Marcar pacotes aleatoriamente
 Evitar bias contra tráfego explosivo
Random Early Detection (RED)
 Idéia Básica do RED
 O roteador percebe que a fila está ficando chéia
 …e aleatóriamente descarta pacotes para sinalizar 
congestionamento
 Probabilidade de descarte de pacote
 A probabilidade aumenta conforme o tamanho da fila aumenta
 Também a probabilidade de descarte pode ser uma função do 
tamanho médio da fila e o tempo desde o último descarte
27Average Queue Length
D
ro
p
P
ro
ba
bi
lit
y
0 
 
 
 
 
1
28
Algoritmo RED
 Manter o calculo do tamanho médio da fila
 Se avg < minth fazer nada 
 Baixo enfileiramento, mandar os pacotes
 Se avg > maxth, descartar pacote
 Proteção de fontes mal comportadas
 Caso contrário, marcar o pacote com um 
valor proporcional ao tamanho da fila
 Notifica às fontes de um congestionamento 
incipiente
 CMU, 2005-11 29
Operação do RED
Min threshMax thresh
Average fila Length
minth maxth
maxP
1.0
Avg fila length
P(drop)
Propriedades do RED
 Descartar pacotes antes de ter a fila chéia
 Na esperança de reduzir as taxas de alguns fluxos
 Descartar pacotes na proporção da taxa de 
cada fluxo
 Fluxos com taxas altas têm mais pacotes
 … e uma maior chance de serem selecionados
 Os descartes são espaçados no tempo
 Que deve ajudar a desincronizar os emissores TCP
 Tolerancia à explosividade do tráfego
 Baseando as decisões no tamanho médio da fila
Problemas com o RED
 Difícil ajuste dos parâmetros
 Quando começar a descartar pacotes?
 Em quanto deve se incrementar a probabilidade de 
perdas?
 Em que intervalo de tempo deve-se medir o tamanho 
da fila?
 RED tem uma implementação mista na prática
 Sem bons parâmetros, não funciona 
 Na comunidade de pesquisa existem 
várias variantes…… 
31
Feedback: Desde a perda à 
notificação
 Descarte adiantado de pacotes
 Bom: da um feedback rápido
 Ruim: o pacote deve ser descartado para dar 
feedback
 Explicit Congestion Notification (ECN)
 O roteador marca o pacote com um bit ECN
 O host emissor o interpreta como um sinal de 
congestionamento
32
33
Explicit congestionamento Notification (ECN)
 [ Floyd and Ramakrishnan 98]
 Mecanismo tradicional
 pacote descartado como sinal implícito de 
congestionamento para sistemas finais
 TCP ficara mais lento 
 Funciona bem para transmissão de dados em massa
 Não funciona bem para aplicações sensiveis ao atraso
 áudio, WEB, telnet
 Explicit Congestion Notification (ECN)
 Usa dois bits no header IP 
 ECN-Capable Transport (ECT) bit (colocado pelo 
emissor)r
 Congestion Experienced (CE) bit (colocado pelo 
roteador) 
34
Controle de 
Congestionamento - Resumo
 Arquitetura : sistemas finais detectam o 
congestionamento e abaixam velocidade
 Ponto de ínicio: 
 Ínicio lento/evitar congestionamento
 pacote descartado detectado pelo retransmission 
timeout (RTO) como sinal de congestionamento
 Retransmissão rápida/ rápida recuperação
 pacote descartado detectado por 3 acks duplicados
 Suporte do roteador
 RED: sinalização temprana
 ECN: sinalização explícita
35
Visão Geral
 Gerenciamento de Filas & RED
 Para que o QoS?
 Príncipios de QoS
 Introdução a políticas de Escalonamento
 Serviços Integrados
36
Motivação
 Hoje em dia a Internet fornece de forma nativa 
uma única classe de serviço “best-effort”
 Sem garantias sobre a entrega
 No projeto da Internet, a maioria das aplicação 
são elásticas 
 Toleram atrasos e perdas
 Se adaptam ao congestionamento
 Hoje, muitas aplicações de tempo real são 
inelásticas
37
Por que um modelo de 
serviço?
 Qual é o objetivo básico de um projeto de 
rede ? 
 Maximizar a largura de banda total? Minimizar a 
latência?
 Maximizar a satisfação do usuário – a utilidade 
total dada aos usuários
 Como se relacionam utilidade vrs. Largura de 
banda ?
 A forma depende na aplicação
 Deve ser uma função não decrescente
38
Forma das Curvas de Utilidade
BW
U Elástica
BW
U Tempo Real
BW
U Adaptativa a Taxa/Atraso
39
Curva de Utilidade – Tráfego 
Elástico
largura de banda
U Elástico
A mesma alocação de largura de 
banda maximiza a utilidade total?
40
Controle de Admissão
 Se U(largura de banda) é 
concava 
  aplicações elásticas
 Utilidade incremental é 
decrescente quando se aumenta 
a largura de banda
 É sempre vantajoso ter mais 
fluxos com baixa largura de 
banda
 Sem necessidade de controle de 
admissão
 Por isso a Internet funciona!
BW
U Elastic
41
Curvas de Utilidade – Tráfego 
Inelástico
BW
U Hard real-time
BW
U Adaptativo ao atraso
Alocação de banda igual 
maximiza a utilidade total?
42
Aplicações Inelásticas 
 Aplicações de média contínua
 Límites inferiores e superiores em desempenho 
aceitável.
 BW abaixo da qual vídeo e áudio não são intelegíveis
 Telefones IP, teleconferência com alto atraso (200 - 
300ms) afetam a interação humana
 Algumas vezes chamados ‘tolerantes a tempo real’ , 
desde que possam se adaptar ao desempenho da 
rede
 Aplicações Hard real-time
 Requerem límites fortes de desempenho
 Ex: aplicações de controle 
43
Controle de Admissão
 If U é convexa aplicações 
inelásticas
 U(número de fluxos) não é mais 
crescente monotona
 Precisa controle de admissão para 
maximizar a utilidade total
 Controle de Admissão  
decidir quando adicionar mais 
pessoas pode reduzir a utilidade 
total
 Basicamente evitar sobrecarga
BW
U Delay-adaptive
44
Visão Geral 
 Gerenciamento de Filas e RED
 Para que o QOS?
 Príncipios de QOS
 Introdução a políticas de Escalonamento
 Serviços Integrados
45
Melhorando o QoS em Redes IP
 Vários grupos do IETF trabalham em propostas para 
fornecer melhor controle de QoS em redes IP, i.e., ir 
além do BE para garantir QoS
 Alguns trabalhos incluem RSVP, Differentiated Services 
eIntegrated Services
 Um modelo simples para compartilhamento e estudos 
de congestionamento :
46
Princípios de Garantia de QoS
 Consideremos uma aplicação VoIP a 1Mbps e uma 
aplicação FTP compartilhando um enlace a 1.5 Mbps. 
 Explosões do FTP podem congestionar o roteador e causar perda 
de pacotes
 O óbvio e dar prioridade ao VoIP sobre o FTP
 PRINCÍPIO 1: Marcar pacotes para que o roteador 
ditingua entre diferentes classes; novas políticas no 
roteador para tratar os pacotes marcados
e.g. MPLS, Diffserv,RSVP
47
Príncipios para Garantias de 
QoS
 Aplicações mal comportadas (áudio envia pacotes a taxas 
mais altas que o assumido 1Mbps); 
 PRINCÍPIO 2: prover proteção (isolamento) para uma 
classe das outras classes
 Requerer mecanismos de policiamento para garantir que 
as fontes se aderem aos requerimentos de largura de 
banda; marcação e policiamento deve ser feito nas bordas 
:
e.g. WFQ
48
 Alternativa para marcação e policiamento: alocar uma 
porção de largura de banda para cada fluxo de aplicação; 
pode levar ao uso ineficiênte se alguns fluxos não usam 
esta alocação
 PRINCÍPIO 3: Ao prover o isolamento, é desejável usar 
os recursos da forma mais eficiênte possível
Príncipiospara Garantias de 
QoS
49
 Não pode se suportar tráfego acima da capacidade do 
enlace
 PRINCÍPIO 4: É necessário usar um processo de 
controle de admissão; o fluxo da aplicação flow 
declara suas necessidades e a rede o pode bloquear 
se não pode satisfaze-las
Príncipios para Garantias de 
QoS
50
Resumo
Exemplos de QoS de Rede
 QoS para serviço de rede : 
 Throughput – Número de bits por segundo
 100 Mbps (Ethernet throughput) – nível1
 10 Mbps (WiFi throughput) – nível 2
 128 kbps (ISDN throughput) – nível 3
 Tempo de estabelecimento de conexão – quanto leva 
se conectar entre emissor e receptor
 50 ms, 10 ms, …
 Atraso fim-a-fim– intervalo de tempo desde que o 
pacote é enviado (no emissor) até que é recebido no 
receptor (Treceive – Tsend) 
 80 ms, 100 ms, 160 ms
Requerimento das Aplicações
Como colocar estes dados de forma mais objetiva?
Modelo em Camadas para o 
QoS
QoE
QoS
Parâmetros das Aplicações 
Parâmetros QoS do Sistema 
CS 414 - Spring 2011
Parâmetros QoS de Rede
Classes de QoS
 Classe de Serviços Garantidos
 As garantias de QoS são fornecidas com base 
em parâmetros determinísticos e estatísticos de 
QoS
 Classe de Serviços Predictivos
 O valor do parâmetro de QoS é estimado no 
comportamento passado da aplicação 
 Classe de Serviço Melhor Esforço
 Não existem garantias (somente parciais)
Classes de QoS
A classe de QoS determina: (a) confiabilidade do QoS oferecido (b) utilização de 
recursos 
• Único valor: QoS1 – média (QoSave), valor 
contratual, valor de limiar, valor de objetivo
• Throughput – 10 Mbps
• Valor Duplo: <QoS1, QoS2> com
 QoS1 – valor requerido; QoS2 – valor desejado
 <QoSavg,QoSpeak>; <QoSmin, QoSmax>
• Throughput - <8,12> Mbps
CS 414 - Spring 2011
Parâmetros Determinísticos de 
QoS
Valores Determinísticos de 
QoS
 Terna de valores <QoS1, QoS2, QoS3>
 QoS1 – melhor valor
 QoS2 – valor médio
 QoS3 – pior valor
 Exemplo:
 <QoSpeak, QoSavg, QoSmin>, em que QoS é largura 
de banda 
 Throughput <12, 10, 8> Mbps
QoS Garantido
 Fornecer garantias 100% para valores QoS (hard 
guarantees) ou muito próximas a 100% (soft 
guarantees)
 O calculo corrente de QoS e alocação de recursos são 
baseadas em : 
1. Limites superiores para cargas de trabalho necessários
2. Piores casos sobre o comportamento do sistema 
1. Vantagens: as garantias de QoS são satisfeitas ainda 
no pior caso
2. Desvantgem: sobre-alocação de recursos, rejeição 
exagerada de requesições
Parâmetros Predictivos de QoS 
 Utilizam-se valores de QoS (QoS1, ..QoSi) e 
se computa a média 
 QoSbound intervalo em K>i é QoSK = 1/i*∑jQoSj
 Utilizam-se valores de QoS (QoS1, , QoSi) e 
se computa o valor máximo
 QoSK = max j=1,…i (QoSj)
 Utilizam-se valores QoS (QoS1, , QoSi) e se 
computa o valor mínimo 
 QoSK = min j=1,…i (QoSj)
QoS Melhor Esforço
 Sem límites de QoS (ou límites fracos)
 Vantagens: as capacidades dos recursos 
podem ser estatísticamente multiplexadas e 
mais requisições são atendidas
 Desvantagens: violações de QoS frequentes 
(em relação às necessidades da aplicação).
Relação entre QoS e os Recursos
CS 414 - Spring 2011
Translation, Scaling, 
Negotiation 
Reservation
Admission 
Scheduling, Rate Control
Flow Control, Congestion Control, 
Adaptation 
Resumo 
 O QoS – é um conceito importante, ainda 
mais em sistemas multimídia
 Existem vários tipos de parâmetros de QoS
 Existe uma relação importante entre o QoS e 
os recursos
 Deve-se compreender melhor o conjunto de 
operações sobre o QoS e seu impacto no 
gerenciamento de recursos