Como a marcação probabilística é realizada com a detecção precoce aleatória?

7

Atualmente, estou estudando para o meu exame de redes de computadores.

Não consigo entender o seguinte.

Quando o atual comprimento médio da fila está entre um min_threshold e um max_threshold, o algoritmo Random Early Detection marca cada pacote que recebe com uma probabilidade (para descartar ou notificação explícita de congestionamento).

Entendo que cada pacote é marcado quando o AQL é maior que max_threshold (ou seja, p é 1), mas não posso entender no primeiro caso como é usada a probabilidade calculada para decidir se um pacote será marcado ou não.

Por exemplo, se p_b é calculado em 0,7 para um pacote, isso significa que o pacote não será marcado?

Para referência, aqui está o algoritmo RED em pseudocódigo, conforme proposto pela primeira vez em http://www.cs.princeton.edu/courses/archive/fall06/cos561/papers/red.pdf :

Initialization:
avg ← 0
count ← −1

for each packet arrival calculate the new average queue size avg: 
    if the queue is nonempty
        avg ← (1 − w_q)*avg + w_q*q     
    else
        m← f(time−q time) 
        avg←(1−w )^m*avgq 

    if min_th ≤ avg < max_th
        increment count

        calculate probability pa:
            pb ← maxp(avg − minth)/(maxth − minth) pa ←pb/(1−count·pb)
        with probability pa:
            mark the arriving packet count ← 0

    else if maxth ≤ avg
        mark the arriving packet count ← 0
    else count ← −1

when queue becomes empty
q_time ← time
Riccardo Angius
fonte

Respostas:

6

Pense no RED como uma curva arbitrária em um sistema de coordenadas.

Y é a probabilidade de queda X é o quanto você está congestionado (por exemplo, como os buffers de saída completos)

O operador pode adicionar 5 pontos lá

  1. X = 40%, Y = 0%
  2. X = 50%, Y = 5%
  3. X = 60%, Y = 20%
  4. X = 70%, Y = 40%
  5. X = 90%, Y = 100%

Em seguida, você desenharia linhas para os pontos para formar a curva, para obter Y exato (probabilidade de queda) para cada X (demanda / congestionamento).

A implementação exata de como produzir um número aleatório para a porcentagem não é muito interessante; pode ser que você faça um número aleatório de 1 a 100 e, se Y == 5, para os números aleatórios 1 a 5 você soltar, por 6 a 100 você não derrube.

WRED é exatamente o mesmo, existem apenas curvas diferentes para diferentes classes de QoS.

Esta pode não ser a resposta acadêmica que você esperaria, e também não posso recomendar livros muito acadêmicos para QoS. A QoS é muito específica de implementação. TM (Gerenciador de Tráfego) são as peças mais complexas do roteador moderno.

ytti
fonte
Ele não precisava ser acadêmico, eu tinha todos os detalhes no livro do professor, mas, por mais desinteressante, estava faltando aquela peça para visualizar de maneira abrangente como tudo funciona. Muito obrigado.
Riccardo Angius