Prevenção e Controlo de
Congestão
Sistemas Telemáticos
Licenciatura em Engenharia de Sistemas e
Informática
Departamento de Informática
Universidade do Minho
Materias utilizados

Internet Congestion Control with Active Queue
Management (AQM),
Seungwan Ryu
([email protected])
Sumário




Introdução
Controlo de Congestão no TCP
Gestão Activa de Filas
Notificação Explícita de Congestão
Congestão (1)

As redes de comutação de pacotes têm
recursos limitados



Largura de banda das linhas que interligam os
encaminhadores
Comprimento finito das filas em que são
armazenados os pacotes à espera de transmissão
Os recursos da rede devem ser partilhados
entre as diversas conexões suportadas
Congestão(2)

Quando muitos pacotes têm que ser
enviados através da mesma linha



As filas ultrapassam o seu limite máximo
Alguns pacotes são descartados
Se o descarte é muito frequente...a
rede fica congestionada
Congestão(3)

Transformou-se num problema sério


Aumento da utilidade e uso das redes de
computadores
Mistura de diferentes tecnologias

Exemplo: Pares entraçados e fibras ópticas


Fibras permitem grandes larguras de banda
Desadaptação entre diferentes débitos
O que é a congestão?

O que é a congestão ?


A necessidade agregada de largura de banda
excede a capacidade disponibilizada pela linha.
O que acontece ?

Degragação de desempenho
•
•
•
•
Perdas múltiplas de pacotes
Baixa utilização da ligação
Tempos de atraso altos
Colapso de congestão
Métricas de detecção

Podem ser usadas vários métricas para
detectar se uma rede está congestionada






Percentagem de pacotes descartados por falta de
espaço de armazenamento
Tamanho médio das filas
Número de pacotes que disparam o temporizador
e são retransmitidos
Tempo médio de atraso dos pacotes
Desvio padrão para o atraso dos pacotes
Em qualquer dos casos o aumento nos
números significa aumento da congestão
As razões da congestão

Inundação de tráfego destinado à mesma
linha de saída





As filas enchem e os pacotes são descartados
O problema pode não ser resolvido única e
simplesmente com aumento de memória
Processadores lentos ou software de
encaminhamento pouco eficiente.
Desadaptação entre partes do sistema (várias
linhas rápidas e uma lenta)
A congestão tem tendência a alimentar-se a
si própria e piorar a situação.
Congestão vs. Controlo de Fluxo



O controlo de congestão têm que se certificar
que a rede é capaz de transportar o tráfego
A congestão é um problema global, envolve
todos os sistemas finais e encaminhadores
O controlo de fluxo lida com tráfego ponto-aponto entre uma fonte e um destino (por
exemplo um supercomputador a descarregar
para um PC através duma fibra)
Congestão



As redes mais modernas têm que ter algum
mecanismo para controlar a congestão
Essas técnicas estão estreitamente relacionadas
com a forma como os recursos limitados são
alocados às várias conexões activas na rede
Dois paradigmas alternativos:


Alocação de Recursos em tempo de estabelecimento
de conexão como forma de prevenir a congestão
A fonte detectar a congestão e a ajudar na sua
redução ou eliminação quando ela ocorre.
Congestão

Uma alternativa é a rede ter um papel activo na alocação
de recursos




Embora isto possa evitar a congestão, a conexão pode ser
rejeitada se houver recursos disponíveis insuficientes
É contudo uma tarefa difícil uma vez que essas alocações devem
ocorrer em todos os encaminhadores e linhas da rede.
Adicionalmente, esta abordagem pode potenciar a sub-utilização
dos recursos que são limitados.
Outra alternativa é permitir às fontes enviarem os dados
que quiserem para rede, e forcá-la a recuperar de
situações de congestão.

Uma abordagem mais simples, mas a congestão pode demorar
algum tempo a ser dissipada (com a perda de pacotes a
persistir).
Fluxos numa rede não
orientada à conexão



O conceito de fluxo é essencial para o
processo de alocação de recursos
É feita pela rede uma expedição
independente de cada datagrama entre e
endereço IP fonte e o IP destino.
Contudo, na prática, é suposto que uma
sequência de pacotes siga a mesma rota na
rede entre a fonte e o IP destino

Esta sequência de pacotes constitui um fluxo
Fluxos numa rede não
orientada à conexão


Na prática o fluxo não é estabelecido
Geralmente um encaminhador reconhece os
fluxos pela análise de cadeia de pacotes que
passam por ele.


Basta analisar a fonte e o destino dos pacotes IP
O encaminhador pode manter informação a
respeito de cada fluxo que passa por ele para
efeitos de alocação de recursos

Chamada muitas vezes informação de estado ligeira
(soft state)
Mecanismos de alocação de recursos


Existem inúmeras formas das redes
realizarem na prática as operações de
alocação de recursos
Contudo, iremos analisar três critérios de
classificação para os mecanismos de alocação
de recursos



Centrado no encaminhador ou no sistema final
Baseado em reserva ou em realimentação
Baseado em janela ou em débito
Centrado na rede ou na fonte


As fontes IP e os os encaminhadores estão
envolvidos na alocação de recursos
Classificação que localiza as responsabilidades

Centrado na rede:




Encaminhadores têm a a responsabilidade de decidir quando
os pacotes são expedidos ou descartados;
Informam as fontes IP de quanta informação estão autorizados
a enviar
As fontes devem respeitar estas mensagens de conselho
Centrado na fonte:


Fontes monitorizam a rede e ajustam o seu comportamento em
conformidade
Encaminhadores sob congestão descartam os pacotes
Reserva vs realimentação

Numa abordagem baseada em reserva:



A fonte requisita explicitamente recursos (buffer e/ou
capacidade nas linhas) dos encaminhadores (portanto
centrado na rede) quando o fluxo é estabelecido
Cada encaminhador aloca os recursos requisitados, se isso não
ultrapassar a sua capacidade limitada.
Numa abordagem baseada em realimentação


Não há o processo de reserva
As fontes IP ajustam o seu débito de acordo com a informação
de realimentação, que pode ser:

Explícita: Mensagens de Controlo de Congestão (centrada na

Implicita: Como resultado da medição do comportamento da
rede)
rede (centrada na fonte)
Baseada em janela ou débito


Como é que o nó fonte IP é informado da
quantidade dos dados que pode enviar?
Este critério classifica os mecanismos de
controlo de congestão na forma de relato
usado para indicar à fonte quantos dados
pode enviar


Como um tamanho de janela aconselhada pelos
encaminhadores usados por um fluxo.
Como um débito (i.e. Entidades por unidade de
tempo que a fonte pode transmitir para a rede).
Avaliação da alocação de
recursos


Um mecanismo de alocação de recursos pode
ser avaliado em termos tanto da sua eficácia
como equidade(fairness).
A eficácia pode ser avaliada com:
(Average) T hroughput
Power 
with typically  1
(Average) Delay

Throughput e atraso são parâmetros que
competem – forçar mais dados para a rede
aumenta o tamanho das filas e portanto aumenta
o atraso
Equidade da alocação de recursos

A equidade dum algoritmo de alocação
de recursos é uma quantidade mais
difícil de medir.


Para uma dada linha entre dois
encaminhadores, há maior equidade
quando todos fluxos recebem uma parte
equitativa da largura de banda?
Uma métrica comum para a equidade é
o índice de Jain.
Índice de equidade de Jain

Para um dado conjunto de fluxos x1, x2,
…. xN, o índice de equidade é dado por:
 N 
  xi 
f x1 , x 2 ,....x N    i 1N 
n  x i2
2
i 1

O índice de equidade varia entre 0 e 1
(1 é o maior valor)
Prevenção e Controlo de Congestão

Duas abordagens para lidar com a congestão

Controlo de Congestão (Reactiva)
• Actua depois da rede estar sobrecarregada

Prevenção de Congestão (Proactiva)
• Actua antes da rede estar sobrecarregada
Algoritmos de Controlo de Congestão


São conhecidos muitos algoritmos de controlo
de congestão
Foi desenvolvida uma taxonomia para os
organizar


A taxonomia começa por dividí-los em algoritmos
em anel aberto e em anel fechado
As soluções em anel aberto são divididas entre
aquelas que actuam na fonte e as que actuam no
destino
Categorias em anel fechado

Divididas em duas sub-categorias

Realimentação explícita


São enviados pacotes de aviso dos pontos de
congestão para a fonte
Realimentação implícita

As fontes deduzem a existência de congestão
pelas suas próprias observações
Controlo de Congestão
Controlo de congestão
Em anel aberto
 usado principalmente em
redes de comutação de circuitos
(GMPLS)
Controlo de Realimentação
implícito
Em anel fechado
 usado principalmente em redes de comutação de
pacotes
 usa informação de realimentação: global & local
 End-to-end congestion control
 Exemplos:
TCP Tahoe, TCP Reno, TCP Vegas, etc.
Controlo de realimentação explícito
 controlo de congestão assistido pela rede
 Exemplos:
IBM SNA, DECbit, ATM ABR, ICMP source
quench, RED, ECN
Políticas que afectam a congestão
Camada
Transporte
Rede
Ligação Lógica
Políticas
 Política de retransmissões
 Política de caching de pacotes fora de
ordem
 Política de confirmação de recepção
 Política de controlo de fluxo
 Determinação de tempo de disparo de
temporizadores
 CV e datagramas no interior da rede
 Política de gestão de filas e
escalonamento
 Política de descarte de pacotes
 Protocolo de encaminhamento
 Gestão de tempos de vida dos pacotes
 Política de retransmissões
 Política de caching de pacotes fora de
ordem
 Política de confirmação de recepção
 Política de controlo de fluxo
Anel Aberto: Calibração de Tráfego
Traffic shaping




Uma das principais causas de congestão é a o
tráfego são as rajadas (bursty) de tráfego.
A calibração de tráfego é um método em anel
aberto que tenta gerir a congestão forçando
que os pacotes sejam transmitidos a um
débito previsível
O seu objectivo é regular o débito médio (e
rajada) na transmissão dos dados
Quando se estabelece a ligação a calibração é
acordada entre o utilizador e o transportador.
Algoritmo do balde vazante
Leaky Bucket Algorithm



O que se pretende é disponibilizar um
fluxo consistente e regular de tráfego
Imagine um balde com um buraco em
baixo ou uma torneira com o fluxo de
saída é constante, independente da
água que entra ou que existe.
É essa a ideia de suporte a este
algoritmo
Algoritmo do Balde vazante
O fluxo de saída tem um
débito constante , quando
há agua no balde e é zero
qunado o balde está vazio
Algoritmo do Balde vazante
Concretização




Um balde vazante não é mais que um sistema
de fila com um único servidor com um tempo
de serviço constante
Os pacotes podem chegar a qualquer
instante, mas o host só está autorizado a
colocar um pacote na rede por cada tique do
relógio.
Se os pacotes forem de diferentes tamanhos
é melhor usar um número fixo de bytes por
tique em vez de um pacote.
Quando a fila enche, os novos pacotes são
descartados
Algoritmo do Balde com Créditos
Token Bucket Algorithm





O balde vazante força um padrão de saída
rígido
O algoritmo do balde com créditos permite
acelerações na saída quando chegam muitos
pacotes (rajadas)
Aqui cada balde mantém créditos que são
gerados por um relógio à velocidade de um
crédito em cada T segundos
Para transmitir precisa de um crédito
Os hosts que ficam períodos em silêncio,
podem enviar rajadas mais tarde.
Realimentação Implícita vs Explícita

Controlo de Congestão com Realimentação
Implícita


A rede descarta pacotes quando a congestão
ocorre
A fonte infere a congestão implicitamente
• Disparo de temporizadores, confirmações duplicadas, etc.


Examplo: Controlo de Congestão fim-a-fim do TCP
Fácil de concretizar mas imprecisa
• Concretizada apenas na camada de transporte (TCP)
Realimentação Implícita vs Explícita

Controlo de Congestão com realimentação
explícita

O encaminhador indica explicitamente a congestão
às fontes




Marcação de pacotes
Exemplos: DECbit, ECN, etc.
Disponibiliza informação mais precisa às fontes
Mais complicado de concretizar
• É preciso mudar algoritmos dos elementos da rede e de
das fontes
• É necessária a cooperação entre as fontes e os
componentes da rede
Controlo de Congestão no TCP

Ideia




Assumir rede melhor- esforço (encaminhadores
FIFO ou FQ) em que cada fonte determina a
capacidade da rede por si só
Usa realimentação implícita
As confirmações fazem aumentar as transmissões
(auto-relógio)
Desafio


Determinar em primeiro lugar a capacidade
disponível
Ajuste a mudanças na capacidade disponível
Controlo de Congestão no TCP

Usa controlo de congestão fim-a-fim

Usa realimentação implícita
• i.e., time-out, ACKs triplos duplicados, etc.

Usa controlo de fluxo baseado em janela
• cwnd = min (pipe size, rwnd)
• Auto-relógio (self-clocking)
• Arranque lento e prevenção de congestão

Exemplos:
• TCP Tahoe, TCP Reno, TCP Vegas, etc.
Controlo de Congestão no TCP

cwnd
W*
Arranque lento e prevenção de congestão
Arranque
lento
Prevenção de Congestão
W
4
W+1
W*/2
2
1
RTT
RTT
Time
Arranque lento no TCP

Quando pensamos num algoritmo de controlo
de fluxo baseado em janela deslizante


Isto funciona bem para dois computadores
ligados à mesma LAN…


Assumimos que a fonte pode enviar segmentos
até ao tamanho da janela
mas pode causar problemas se houver
encaminhadores e linhas mais lentas no percusros
entre os dois
O TCP precisa de suportar um algoritmo
chamado de arranque lento…
Arranque lento no TCP




O arranque lento adiciona uma outra janela
para a emissor TCP: a janela de congestão
Quando se estabelece uma nova conexão, a
janela de congestão é inicializada a 1
segmento.
Cada vez que se recebe uma confirmação, a
janela de congestão é aumentada de 1
O emissor pode enviar até um número de
segmentos que é o mínimo entre a janela de
congestão e a janela de controlo de fluxo
Arranque lento no TCP
tempo 0
tempo 1
tempo 2
tempo 3
1
tempo 4
1
1
tempo 5
1
1
tempo 6
1
1
tempo 7
1
Arranque lento no TCP
tempo 8
tempo 9
tempo 10
tempo 11
tempo 12
2
3
tempo 13
2
2
tempo 14
3
2
2
tempo 15
3
2
2
tempo 16
3
2
tempo 17
3
4
3
5
4
3
3
Arranque lento no TCP
tempo 18
tempo 19
6
5
7
6
tempo 23
5
4
4
5
7
6
5
4
7
tempo 21
4
tempo 25
tempo 26
7
4
5
2
tempo 27
6
9
6
6
5
6
7
8
tempo 24 5
tempo 20
tempo 22
4
7
8
7
10
9
11
10
8
7
9
8
Arranque lento no TCP
12
tempo 28
11
10
9
8
13
tempo 29
12
11
8
14
tempo 30
13
8
15
tempo 31
8
9
9
12
9
14
10
11
10
13
10
12
11
Arranque lento no TCP


A janela de congestão é o controlo de fluxo
imposto pelo emissor, enquanto a outra
janela é o controlo de fluxo do receptor
A capacidade da Internet pode ser atingida a
qualquer instante, e um encaminhador
intermediário começar a decartar pacotes…


Isso indica ao emissor que a janela de congestão
está muito grande
Que tamanho deve ter a janela?


No exemplo apresentdo a janela atingiu os 8
segmentos.
A capacidade do pipe ou o produto atraso e
largura de banda pode ser dada por


capacidade(bits) = largura de banda (bps) x
tempo-de-ida-e-volta(seg)
Exemplos


T1 (1.54mbps), através dos EUA (60ms RTT) dá
11,580bytes (max tamanho de janela TCP é 64K)
T3 (45mbps), dá 337,500bytes!!
Controlo de Congestão no TCP

“probing” da largura de
banda utilizável:



Idealmente: transmitiro
mais rápido possível
(Congwin o maior
possível) sem perdas
Aumentar Congwin até
haver perdas l(congestão)
Perdas: diminuir a
Congwin, e então
recomeçar o probing
(aumento) novamente.

Duas “fases”



Arranque lento
Prevenção de congestão
Variáveis importantes:


Congwin
threshold: define a
fronteira entre as duas
fases
Controlo de Congestão no TCP
Prevenção de Congestão
/*arranque lento terminado*/
/* Congwin > threshold */
Until (loss event) {
every w segments ACKed:
Congwin++
}
threshold = Congwin/2
Congwin = 1
Executar arranque lento
Controlo de Congestão no TCP

TCP Tahoe


Usa arranque lento/prevenção da congestão
Uma melhoria: rápida retransmissão



Detectar pacotes (segmentos) descartados por três ACKs
duplicados
W = W/2, e começa a prevenção da congestão
TCP Reno (recuperação rápida)

Depois de receber três ACKs duplicados




ssthresh = W/2, e retransmitir pacotes em falta
W = ssthresh +3
Depois de receber a confirmação (ACK): W = ssthresh
Permitir ao tamanho da janela crescer depressa para manter
cheio o pipeline
Controlo de Congestão no TCP
TCP SACK (Selected Acknowledgement)


O emissor TCP (Thaoe) pode apenas saber duma
única perda por tempo-de-ida-e-volta ( RTT)
A opção SACK disponibiliza uma melhor recuperação
de uma situação de múltiplas perdas



O emissor pode transmitir todos os pacotes perdidos
Mas esses pacotes podem já ter sido recebidod
Operação



Adicionar a opção SACK ao cabeçalho TCP
O receptor envia um SACK ao emissor para o informar da
recepção do pacote
Então, o emissor pode retransmitir apenas o pacote em falta
Gestão Activa de Filas
Active Queue Management (AQM)

Degradação de desempenho no Controlo de
Congestão do TCP




Múltiplas perdas de pacotes
Baixa utilização das linhas
Colapso de congestão
O papel dos encaminhadores torna-se
importante


Controlo eficiente da congestão nas redes
Alocação apropriada da largura de banda
Técnicas de Gestão de Filas


Um dos aspectos mais básicos da
alocação de recursos é como os pacotes
são colocados nas filas quando
aguardam a sua transmissão
As duas técnicas mais comuns são:


Filas FIFO
Filas com Equidade (Fair queuing)
Filas FIFO






Tem uma capacidade finita de armazenar pacotes
Os pacotes são armazenados pela ordem de chegada
O pacote no topo da fila é transmitido pela linha
Uma fila FIFO introduz alguma latência (atraso) já
que os pacotes esperam na fila até a sua transmissão
Com a fila cheia, um pacote que chega é descartado
A FIFO é uma disciplina de serviço da fila enquanto o
descarte da cauda é uma política de descarte
Filas FIFO com Prioridade


Uma ligeira variação das filas FIFO básicas
Cada encaminhador mantém múltiplas filas FIFO




Cada fila tem pacotes com uma certa prioridade
Os pacotes são enviados por ordem de prioridade
É um ligeiro melhoramento do conceito melhor esforço
da Internet.
Uma geração não controlada de pacotes de alta
prioridade pode tornar esta abordagem não usável

É necessário um mecanismo para controlar os pacotes com alta
prioridade enviada por cada fonte.
Filas FIFO: Comentários


As filas FIFO colocam todo ênfase do controlo de
congestão nos sistemas finais (fonte e destino)
Adicionalmente não diferenciam o tráfego com
base em fluxos

É bastante provável que um sistema final não adira
(incompreensão ou desobediência) aos pedidos para
reduzir o seu fluxo


Desta forma pode apoderar-se de grandes quantidades dos
recursos FIFO
Uma solução mais equitativa seria os encaminhadores
terem uma FIFO para fluxo

Não aderência a pedidos só afecta o próprio fluxo
Filas com Equidade
Fair Queuing (FQ)


Num sistema FQ, o encaminhador mantém uma
FIFO por cada fluxo.
As FIFOs são servidas de forma circular (roundrobin)


Quando a fila dum fluxo fica cheia, qualquer pacote
posterior é descartado (até que a fila se reduza).
O FQ não é por si só um algoritmo de controlo de
congestão, simplesmente segrega os fluxos


Não diz nada à fonte para reduzir o seu fluxo
Precisa de ser combinado com um algoritmo de
controlo de congestão fim-a-fim
Filas Equitativas: Problemas

A abordagem FQ básica ignora o impacto do
tamanho dos pacotes na fila


Um fluxo com pacotes grandes obtém um maior
número de recursos que outro com pacotes curtos
Um algoritmo FQ mais justo deveria
considerar o tamanho dos pacotes

Um abordagem ideal (mas obviamente
impraticável) seria servir cada FIFO na base do
bit.
Filas Equitativas:Concretização



Considere um encaminhador com n fluxos activos
O encaminhador concretiza um relógio que se incrementa cada
vez que são transmitidos n bits
Qunado o pacote i (num fluxo particular) chega ao
encaminhador é etiquetado com uma estampilha temporal com
um valor (Fi) , igual à soma seguinte:
Fi  maxFi1 , Ai   Pi



Fi : Tempo em que se finaliza a transmissão do pacote i
Ai: Tempo de chegada do pacote i ao encaminhador
Pi : O tamanho do pacote i (em bits)
Filas Equitativas:Concretização


Quando uma linha de saída fica inactiva, o próximo
pacote a ser transmitido é com a menor estampilha
temporal (valor Fi)
Desta forma, para um pacote permanecer numa FIFO
durante um certo tempo, a linha de saída não pode
estar jnactiva durante esse tempo.


Este característica é chamada conservação do trabalho
Algumas das características mais importantes da
técnica de conservação são:


Cada fluxo tem garantido pelo menos 1/n of da LB de saída
Se a largura de banda dum fluxo é usada por outros (se as
FIFOs não estiverem vazias)
Filas Equitativas Ponderadas
Weighted Fair Queuing (WFQ)


A WFQ permite ser associado um peso a cada
fila
Isto resulta a alocação aos diferentes fluxos
proporções maiores ou mais pequenas da
largura de banda da linha de saída (que o 1/n
da FQ)


Considere 3 fluxos ( 1, 2 e 3) respectivamente –
que recebem 1/6, 1/3e 1/2 da LB da linha saída
Em termos práticos, este processo pode ser
concretizado usando os pesos para o desiquilíbrio
do valor Pi usado para calcular Fi
Filas Equitativas Ponderadas
Weighted Fair Queuing (WFQ)

Os pesos dos valores para o WFQ usado
no encaminhador podem ser


Configurados manualmente (não é prático)
Inicializados pela fonte do fluxo com
alguma forma de sinalização

É um tipo de alocação baseada em reserva mas
é imprecisa

A proporção da LB atribuída a cada fluxo depende do
número de fluxos activos no encaminhador.
Gestão Activa de Filas

Problemas com os algoritmos convencionais
dos encaminhadores


Usam uma gestão de filas FIFO com descarte dos
pacotes na cauda (Tail Drop- TD)
Dois problemas com a descarte na cauda:



Um pequeno número de fluxos monopolizam a capacidade
do buffer
A fila está sempre cheia (atrasos altos na fila)
Solução possível: Gestão activa de filas

Definição: Um grupo de mecanismos de gestão de
filas FIFO para suportar o controlo de congestão
fim-a-fim na Internet
Gestão Activa de Filas

Objectivos

Reduzir o tamanho médio da fila:


Reduzir perda de pacotes:


Uma mais eficiente alocação de recursos
Métodos:



Diminuir o atraso fim-a-fim
Descartar pacotes antes do buffer ficar cheio
Usar uma ponderação exponensial do tamanho
médio da fila como indicador de congestão
Exemplos: RED, BLUE, ARED, SRED, FRED,….
Gestão Activa de Filas
Random Early Detection (RED)

Usa um algoritmo de rede para detectar
congestão incipiente

Objectivos da concepção:
•
•
•
•

Minimizar perda de pacotes e atraso na fila
Evitar sincronização global
Manter uma utilização alta da linha
Remover desiquilíbrios gerados por fontes em rajada
(bursty source )
Métodos utilizados
• Descarte aleatório de pacotes
• Manter um tamanho médio de fila
Gestão Activa de Filas: RED
avgQ  (1  WQ )avgQ  WQQ
P
0


avgQ  minth
Pd   pmax
maxth  minth

1

avgQ  minth
minth  avgQ  maxth
maxth  avgQ
1
0 < Wq < 1 (0.002)
maxp
minth
maxth
K
Gestão Activa de Filas: RED
Detalhes do RED

A notificação é implícita

Basta descartar o pacote



TCP dispara o temporizador
Pacote poderia ser marcado explicitamente
Descarte antecipado de pacotes

Em vez de de esperar que a fila encha descarta-se
os pacotes com probablilidade p uma vez
antingido determinado valor de limiar
Gestão Activa de Filas: RED
Detalhes do RED

Dois valores de corte na fila
if AvgLen <= MinThreshold then
colocar o pacote na fila
if MinThreshold < AvgLen < MaxThreshold
then
calcular a probabilidade P
descartar pacote chegado com
probablilidade P
if ManThreshold <= AvgLen then
descartar pacote
Gestão Activa de Filas: RED
Afinação do RED

Probablilidade de descarte de um pacote
dum dado fluxo


MaxP é colocada em 0.02


é aproximadamente proporcional à % de largura
de banda usada pelo fluxo.
Quando o tamanho médio da fila está a meio dos
dois valores de corte é descartado um pacote em
cada 50.
Se houver rajadas de tráfego

O MinThreshold deve ser suficientemte grande
para manter a utilização da linha a um nível
aceitável.
Gestão Activa de Filas: RED
Afinação do RED (cont.)

A diferença entre os dois valores de
corte deve ser suficientemente grande

É razoável colocar
MaxThreshold = 2* MinThreshold
Gestão Activa de Filas:

Algoritmo

Conceito



Perda de pacotes
 if (now - last_update >freeze_t)
 Pm = pm + d1
 last_update = now
Linha inactiva
 if (now - last_update >freeze_t)
 Pm = pm - d2
 last_update = now
Para eliminar problemas do RED






BLUE
Ajuste de parâmetros
Flutuação do tamanho da fila
Desliga o controlo de congestão
do tamanho da fila
Usa só as perdas e a inactividade
como eventos indicadores
Mantém uma única probablidade
de descarte, pm
Problema

Não consegue evitar algum grau
de múltiplas perdas de pacotes
e/ou baixa utilização da linha
Gestão Activa de Filas: SRED

Algoritmo

O iésimo pacote chegado é comparado
com um seleccionado aleatóriamente da
lista






Acerto = 1, se forem do mesmo fluxo
Acerto = 0, se não
p(i) =frequência de acerto =(1-)p(i-1)
+Acerto
p(i)-1: estimador de # de fluxos activos
Probablidade de descarte de pacotes
Pzap  Psred * min(1,
psred
 pmax

 (1 / 4) pmax

0

1
)
(256 P(i))2
(1 / 3) B  q  B
(1 / 6) B  q  (1 / 3) B
q  (1 / 6) B

Conceito



Estabilizar a ocupação da fila
Usar o tamanho actual da fila
Penalizar fluxos mal
comportados
Problemas



P(i)-1 não é um bom estimador
para tráfego heterogéneop
Ajuste de parâmetros: Psred,
Pzap, etc.
Estabiliza a ocupação da fila
quando o tráfego é alto.
(E quando a carga é baixa ?)
Gestão Activa de Filas: ARED

Adaptar a agressividade do RED consoante a
mudança da carga de tráfego


Adaptar maxp baseado no comportamento da fila
Operação



Aumentar maxp quando avgQ ultrapassa maxth
Diminuir maxp quando avgQ é inferior a minth
Congelar maxp após mudança para prevenir oscilações
Gestão Activa de Filas: RIO
RIO (RED in and out)


Separar fluxos em duas classes: Dentro e Fora do perfil
de serviço
O encaminhador mantém duas estatísticas diferentes
para cada perfil de serviço


Parâmetros e tamanho médio das filas diferentes
Quando congestionado aplica políticas de controlo
diferentes para cada classe
p
1
Pmax_OUT
Pmax_IN
Minth_OUT Maxth_OUT
= Minth_IN
Maxth_IN
avg
Gestão Activa de Filas: Problemas
existentes

Problemas com proposta existentes



Incompabitilidade entre o comportamento
microscópico e macroscópico das filas
Insensibilidade à mudança do tráfego de entrada
Problemas de configuração


Definição dos valores dos parâmetros
Razões:



Média do tamanho das filas
Uso de indicador de congestão não apropriado
Uso de função de controlo não apropriada
Notificação Explícita da Congestão
Explicit Congestion Notification (ECN)

Indicação actual da congestão



Usa o descarte de pacotes para indicar a
congestão
A fonte infere a congestão implicitamente
ECN




Obter menos perdas de pacotes e melhor
desempenho
Marcar em vez de descartar pacotes
É preciso a cooperação entre as fontes e a rede
São necessários 2 bits no cabeçalho IP: ECT-bit,
CE-bit
Notificação Explícita da Congestão
ECT
Cabeçalho IP
CE
1
ECT
0
CE
1
1
1
Cabeçalho TCP
0
0
CWR
CWR
2
1
ECN-Echo
Cabeçalho TCP
3
1
CWR
Fonte
4
Encaminhador
Destino
Cabeçalho do
ACK TCP
Sumário
pl(t)
xi(t)
TCP:
 Reno
 Vegas
AQM:
 DropTail
 RED
 RIO