Random Early Detection

14.5. Random Early Detection (RED)

Essa seção é pensada como uma introdução ao enfileiramento em redes de backbone, que frequentemente envolvem mais de 100 Megabit de banda, que requer uma abordagem diferente do que a de seu modem ADSL de casa.

O comportamento normal em filas de roteador na Internet é chamado tail-drop. O tail-drop funciona enfileirando até certa quantidade, então começa a descartar todo o tráfego que exceder (spills over) o limite. Isso é bastante injusto, e também leva a sincronização de retransmissão. Quando a sincronização de retransmissão ocorre, a rajada repentina de descartes a partir de um roteador que alcançou sua capacidade provocará uma rajada de retransmissões atrasada, o que transbordará o roteador congestionado novamente.

Da Wikipedia http://en.wikipedia.org/wiki/Tail_drop:

Tail Drop, ou Drop Tail, é um algoritmo de gerenciamento de fila usado nos roteadores da Internet para decidir quando descartar pacotes. Em contaste com os algoritmos mais complexos como o RED e WRED, no Tail Drop todo o tráfego não é diferenciado. Cada pacote é tratado de modo idêntico. Com o Tail Drop, quando a fila enche até a sua capacidade máxima, os pacotes novos que chegam são descartados até a fila ficar suficientemente livre para aceitar tráfego entrante.

O nome advém do efeito do policiamento sobre os datagramas entrantes. Uma vez uma fila tenha ficado cheia, o roteador começa a descartar todos os datagramas adicionais, e conseqüentemente começar a descartar o rabo da seqüência de datagramas. A perda de datagramas faz que o transmissor TCP entre em slow-start, o que reduz a taxa de transmissão na sessão TCP até que o transmissor comece a receber ACK´s novamente e aumente a sua janela de congestionamento. Um problema mais severo ocorre quando datagramas de múltiplas conexões TCP são descartados, causando sincronização global, ou seja, todos os transmissores TCP envolvidos entram em slow-start. Isso acontece porque, em vez de descartar vários segmentos de uma conexão, o roteador tenderia a descartar um segmento de cada conexão.

A fim de lidar com o transiente de congestionamento nos links, roteadores do backbone freqüentemente implementam grandes filas. Infelizmente, ao tempo que essas filas são boas para taxa de transmissão, por outro lado podem aumentar de forma substancial a latência e pode se comportar causando rajadas muito fortes durante o congestionamento nas conexões TCP.

Esses problemas com o tail-drop está se tornando uma dor de cabeça enorme na Internet devido ao uso de aplicações exigentes da rede estar aumentando. O Kernel Linux oferece-nos o RED, que é a contração para Random Early Detect – Detecção Randômica Antecipada –, também chamado de Random Early Drop – Descarte Randômico Antecipado –, porque é assim como ele funciona.

O RED não é a cura total para tudo, aplicações que falha na implementação de backoff exponencial ainda possuem uma distribuição não justo da banda, no entanto, com o RED elas não causam tanto dano à taxa de transmissão e latência das outras conexões.

O RED estatisticamente descarta pacotes dos fluxos antes deles alcançarem seu limite rígido. Isso provoca a um link do backbone congestionado ficar lento mais suavemente, e evita sincronização de retransmissão. Isso também ajuda ao TCP encontrar a sua velocidade ‘justa’ mais rápida permitindo que alguns pacotes sejam descartados rapidamente mantendo o tamanho baixo da fila e latência sob controle. A probabilidade de um pacote ser descartado de uma conexão particular é proporcional ao seu uso de largura de banda e não o número de pacotes que ele transmite.

O RED é uma boa fila para backbones, onde você não tem a complexidade da monitoração de estado por sessão necessária pelo enfileiramento justo.

A fim de usar o RED, você precisa decidir sobre três parâmetros: Min, Max e burst. Min define o tamanho de fila mínimo em bytes antes de começar a descartar, Max é um mínimo soft sobre o qual o algoritmo tentará ficar, e burst define o número máximo de pacotes que pode ‘burst through’.

Você deve definir o valor min calculando que latência de enfileiramento base mais alta aceitável que você deseja, e multiplicá-la por sua largura de banda. Por exemplo, no meu link ISDN 64kbit/s, eu posso desejar uma latência de enfileiramento base de 200ms assim eu defino em 1600 bytes. Definir min muito pequeno degradará a taxa de transmissão e muito grande degradará a latência. Definição de um min pequeno não é uma troca pela redução do MTU em um link lento para melhorar a resposta interativa.

Você deve tornar max pelo menos duas vezes o valor de min para evitar sincronização. Em links lentos com pequeno Min´s pode ser esperto para tornar max talvez quatro ou mais vezes maior do que min.

O parâmetro burst controla como o algoritmo RED responde a rajadas. O parâmetro burst precisa ser definido maior do que min/avpkt. Experimentalmente, eu encontrei (min+min+max)/(3*avpkt) para funcionar ok.

Adicionalmente, você precisa definir limit e avpkt. O parâmetro limit é um valor seguro, depois existirá limit bytes na fila, RED ‘entra’ em tail-drop. Eu tipicamente defino limit em oito vezes o valor de max. O parâmetro avpkt deve ser seu tamanho médio de pacote. 1000 funcionam OK em links Internet de lata velocidade com MTU de 1500 bytes.

Leia o artigo sobre Enfileiramento RED de autoria de Sally Floyd e de Van Jacobson para informações técnicas.

14.6. Generic Random Early Detection

Não é sabido muito coisa sobre o GRED. Ele parece com RED com várias filas internas, em que a fila interna é escolhida baseada no campo tcindex do DiffServ. De acordo com uma apresentação aqui, ele possui as habilidades do ‘Distributed Weighted RED’ da Cisco, bem como do RIO do Dave Clark.

Cada fila virtual pode ter especificado seus próprios Parâmetros Drop.

CORRIJAM-ME: Jamal ou Werner nos ensine mais a respeito.

14.7. Emulação VC/ATM

Isso é esforço principal inteiramente de Werner Almesberger para permitir você construir Circuitos Virtuais sobre os soquetes TCP/IP. Um Circuito Virtual é um conceito da teoria da rede ATM.

Para mais informação, veja o site ATM sobre o Linux.

14.8. Weighted Round Robin (WRR)

Essa qdisc não é incluída nos kernels padrão, mas pode ser baixada daqui. Atualmente a qdisc é testada somente com os kernels Linux 2.2, mas provavelmente funcionará com os kernels 2.4/2.5 também.

A qdisc WRR distribui largura de banda entre suas classes usando o esquema cíclico ponderado. Isto é, igual ao CBQ que contém classes em que qdiscs arbitrárias podem ser plugadas. Todas as classes que tenham demanda suficiente ganharão largura de banda proporcional aos pesos associados com as classes. Os pesos podem ser definidos manualmente usando programa tc. Mas eles podem também ser feitos automaticamente decrementado pra classes que transferem muitos dados.

A qdisc possui um classificador embutido que atribui pacotes chegando de ou enviado para diferentes máquinas para diferentes classes. Tanto o endereço MAC quanto o IP e tanto os endereços origem quanto destino pode ser usado. Contudo, o endereço MAC pode ser usado somente quando a máquina Linux está agindo como uma ponte Ethernet. As classes são automaticamente atribuídas nas maquinas baseados nos pacotes observados.

A qdisc pode ser bastante útil em sites como de dormitórios de estudantes onde muitos indivíduos não relacionados compartilham conexão Internet. Um conjunto de scripts define um comportamento relevante quando um site é uma parte central da distribuição WRR.

Capítulo 15 CookBook (Receitas de Bolo)...

Autores Originais dos textos:

Bert Hubert (Netherlabs BV)
bert.hubert@netherlabs.nl

Thomas Graf (Autor de Seção)
tgraf@suug.ch

Gregory Maxwell (Autor de Seção)
greg@linuxpower.cx

Remco van Mook (Autor de Seção)
remco@virtu.nl

Martijn van Oosterhout (Autor de Seção)
kleptog@cupid.suninternet.com

Paul B Schroeder (Autor de Seção)
paulsch@us.ibm.com

Jasper Spaans (Autor de Seção)
jasper@spaans.ds9a.nl

Pedro Larroy (Autor de Seção)
piotr@member.fsf.org