Fila justa - Fair queuing

O enfileiramento justo é uma família de algoritmos de escalonamento usados ​​em alguns escalonadores de processo e rede . O algoritmo é projetado para obter justiça quando um recurso limitado é compartilhado, por exemplo, para evitar que fluxos com grandes pacotes ou processos que geram pequenos trabalhos consumam mais rendimento ou tempo de CPU do que outros fluxos ou processos.

O enfileiramento justo é implementado em alguns switches e roteadores de rede avançados .

História

O termo fila justa foi cunhado por John Nagle em 1985 ao propor o agendamento round-robin no gateway entre uma rede local e a Internet para reduzir a interrupção da rede por hosts mal-comportados.

Uma versão ponderada por byte foi proposta por Alan Demers, Srinivasan Keshav e Scott Shenker em 1989, e foi baseada no algoritmo de enfileiramento justo Nagle anterior. O algoritmo de enfileiramento justo ponderado por byte visa simular uma multiplexação bit por bit, computando a data de partida teórica para cada pacote.

O conceito foi desenvolvido em filas justas ponderadas e no conceito mais geral de modelagem de tráfego , em que as prioridades das filas são controladas dinamicamente para atingir a qualidade de fluxo desejada dos objetivos de serviço ou acelerar alguns fluxos.

Princípio

O enfileiramento justo usa uma fila por fluxo de pacote e os atende em rotação, de modo que cada fluxo possa "obter uma fração igual dos recursos".

A vantagem sobre o convencional primeiro a entrar primeiro a sair (FIFO) ou enfileiramento de prioridade é que um fluxo de alta taxa de dados, consistindo em grandes pacotes ou muitos pacotes de dados, não pode ocupar mais do que seu quinhão da capacidade do link.

O enfileiramento justo é usado em roteadores, switches e multiplexadores estatísticos que encaminham pacotes de um buffer . O buffer funciona como um sistema de enfileiramento, onde os pacotes de dados são armazenados temporariamente até serem transmitidos.

Com uma taxa de dados de ligação de R , em qualquer momento dado o N fluxos de dados activa (aqueles com filas não vazios) são limpos cada um com uma velocidade média de dados de R / N . Em um curto intervalo de tempo, a taxa de dados pode oscilar em torno desse valor, uma vez que os pacotes são entregues sequencialmente por sua vez.

Justiça

No contexto de agendamento de rede, justiça tem várias definições. O artigo de Nagel usa o agendamento round-robin de pacotes, o que é justo em termos de número de pacotes, mas não no uso de largura de banda quando os pacotes têm tamanhos variados. Várias noções formais de medida de justiça foram definidas, incluindo justiça máxima-mínima , justiça de pior caso e índice de justiça .

Generalização para compartilhamento ponderado

A ideia inicial dá a cada fluxo a mesma taxa. Uma extensão natural consiste em permitir que o usuário especifique a porção da largura de banda alocada para cada fluxo levando a uma fila ponderada justa e ao compartilhamento generalizado do processador .

Um algoritmo de enfileiramento justo ponderado em bytes

Este algoritmo tenta emular a justiça do compartilhamento round-robin bit a bit de recursos de link entre fluxos concorrentes. Fluxos baseados em pacotes, entretanto, devem ser transmitidos em pacotes e em seqüência. O algoritmo de enfileiramento justo ponderado em bytes seleciona a ordem de transmissão para os pacotes, modelando o tempo de término de cada pacote como se eles pudessem ser transmitidos round robin bit a bit. O pacote com o tempo de término mais cedo de acordo com esta modelagem é o próximo selecionado para transmissão.

A complexidade do algoritmo é O (log (n)) , onde n é o número de filas / fluxos.

Detalhes do algoritmo

A modelagem do tempo de término real, embora viável, é computacionalmente intensiva. O modelo precisa ser substancialmente recomputado toda vez que um pacote é selecionado para transmissão e toda vez que um novo pacote chega a qualquer fila.

Para reduzir a carga computacional, o conceito de tempo virtual é introduzido. O tempo de término de cada pacote é calculado nesta escala de tempo virtual monotonicamente crescente. Embora o tempo virtual não modele com precisão os pacotes de tempo que completam suas transmissões, ele modela com precisão a ordem em que as transmissões devem ocorrer para atender aos objetivos do modelo completo. Usando o tempo virtual, é desnecessário recalcular o tempo de término para pacotes anteriormente enfileirados. Embora o tempo de término, em termos absolutos, para pacotes existentes seja potencialmente afetado por novas chegadas, o tempo de término na linha do tempo virtual permanece inalterado - a linha do tempo virtual se distorce em relação ao tempo real para acomodar qualquer nova transmissão.

O tempo de término virtual para um pacote recém-enfileirado é dado pela soma do tempo de início virtual mais o tamanho do pacote. O tempo de início virtual é o máximo entre o tempo de término virtual anterior da mesma fila e o instante atual.

Com um tempo de término virtual de todos os pacotes candidatos (ou seja, os pacotes no início de todas as filas de fluxo não vazias) calculado, o enfileiramento justo compara o tempo de término virtual e seleciona o mínimo. O pacote com o tempo mínimo de finalização virtual é transmitido.

Pseudo-código

Shared variables
    const N             // Nb of queues 
    queues[1..N]        // queues
    lastVirFinish[1..N] // last virtual finish instant

receive(packet)
     queueNum := chooseQueue(packet)
     queues[queueNum].enqueue(packet)
     updateTime(packet, queueNum)

updateTime(packet, queueNum)
    // virStart is the virtual start of service
    virStart := max(now(), lastVirFinish[queueNum])
    packet.virFinish := packet.size + virStart
    lastVirFinish[queueNum] := packet.virFinish

send()
     queueNum := selectQueue()
     packet := queues[queueNum].dequeue()
     return packet

selectQueue()
     it := 1
     minVirFinish = 
     while it ≤ N do
         queue := queues[it]
         if not queue.empty and queue.head.virFinish < minVirFinish then
             minVirFinish = queue.head.virFinish
             queueNum := it 
         it := it + 1
     return queueNum

A função receive () é executada toda vez que um pacote é recebido, e send () é executada toda vez que um pacote a ser enviado deve ser selecionado, ou seja , quando o link está ocioso e as filas não estão vazias. Este pseudocódigo assume que existe uma função now () que retorna o tempo virtual atual e uma função chooseQueue () que seleciona a fila onde o pacote está enfileirado.

A função selectQueue () seleciona a fila com o tempo de término virtual mínimo. Por uma questão de legibilidade, o pseudocódigo apresentado aqui faz uma pesquisa linear. Mas a manutenção de uma lista ordenada pode ser implementada em tempo logarítmico, levando a uma complexidade O (log (n)) , mas com um código mais complexo.

Veja também

Referências

  1. ^ a b John Nagle: "On packet switches with infinite storage," RFC 970, IETF , December 1985.
  2. ^ a b c Nagle, JB (1987). "On Packet Switches com Infinite Storage". IEEE Transactions on Communications . 35 (4): 435–438. CiteSeerX  10.1.1.649.5380 . doi : 10.1109 / TCOM.1987.1096782 .
  3. ^ Phillip Gross (janeiro de 1986), Proceedings of the 16-17 janeiro 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF) , IETF , pp. 5, 98 , recuperado 2015-03-04 , Nagle apresentou seu "enfileiramento justo" esquema, no qual os gateways mantêm filas separadas para cada host de envio. Dessa forma, os hosts com implementações patológicas não podem usurpar mais do que seu quinhão dos recursos do gateway. Isso provocou uma discussão animada e interessada.
  4. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). “Análise e simulação de um algoritmo de enfileiramento justo”. Revisão da comunicação do computador ACM SIGCOMM . 19 (4): 1–12. doi : 10.1145 / 75247.75248 .
  5. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Análise e simulação de um algoritmo de enfileiramento justo" (PDF) . Internetworking: Pesquisa e Experiência . 1 : 3-26.
  6. ^ Bennett, JCR; Hui Zhang (1996). "WF / sup 2 / Q: Pior caso Fair Weighted Fair Queuing". Proceedings of IEEE INFOCOM '96. Conferência sobre Comunicações por Computador . 1 . p. 120. doi : 10.1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.
  7. ^ Ito, Y .; Tasaka, S .; Ishibashi, Y. (2002). "Fila round robin com peso variável para roteadores IP principais". Procedimentos da Conferência da Conferência Internacional de Desempenho, Computação e Comunicações da IEEE (Cat. No.02CH37326) . p. 159. doi : 10.1109 / IPCCC.2002.995147 . ISBN 978-0-7803-7371-6.