Wie wird die probabilistische Markierung mit der zufälligen Früherkennung durchgeführt?

7

Ich studiere derzeit für meine Prüfung zu Computernetzwerken.

Ich kann meinen Kopf nicht um Folgendes wickeln.

Wenn die aktuelle durchschnittliche Warteschlangenlänge zwischen einem min_threshold und einem max_threshold liegt, markiert der Algorithmus für die zufällige Früherkennung jedes empfangene Paket mit einer Wahrscheinlichkeit (zum Löschen oder zur expliziten Überlastungsbenachrichtigung).

Ich verstehe, dass jedes Paket markiert ist, wenn der AQL größer als max_threshold ist (dh p ist 1), aber ich kann im ersteren Fall nicht verstehen, wie die berechnete Wahrscheinlichkeit verwendet wird, um zu entscheiden, ob ein Paket markiert wird oder nicht.

Wenn beispielsweise p_b für ein Paket mit 0,7 berechnet wird, bedeutet dies, dass das Paket überhaupt nicht markiert wird?

Als Referenz dient hier der ROTE Algorithmus im Pseudocode, wie er zuerst unter http://www.cs.princeton.edu/courses/archive/fall06/cos561/papers/red.pdf vorgeschlagen wurde :

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
quelle

Antworten:

6

Stellen Sie sich ROT als eine beliebige Kurve in einem Koordinatensystem vor.

Y ist die Wahrscheinlichkeit eines Abfalls. X ist, wie überlastet Sie sind (zum Beispiel, wie voll die Austrittspuffer sind).

Der Bediener könnte dort 5 Punkte hinzufügen

  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%

Dann würden Sie Linien zu den Punkten zeichnen, um die Kurve zu bilden, um für jedes X (Nachfrage / Überlastung) genaues Y (Abfallwahrscheinlichkeit) zu erhalten.

Die genaue Implementierung, wie Zufallszahlen in Prozent erzeugt werden, ist nicht sehr interessant. Es kann sein, dass Sie Zufallszahlen von 1 bis 100 eingeben und wenn Y == 5, dann fallen Sie für Zufallszahlen von 1 bis 5 für 6 bis 100 Lass dich nicht fallen.

WRED ist genau das gleiche, es gibt nur verschiedene Kurven für verschiedene QoS-Klassen.

Dies ist möglicherweise nicht die akademische Antwort, die Sie sich erhoffen, und ich kann auch kein sehr akademisches Buch für QoS empfehlen. QoS ist sehr sehr implementierungsspezifisch. TM (Traffic Manager) sind die komplexesten Teile eines modernen Routers.

ytti
quelle
Es musste überhaupt nicht akademisch sein, ich hatte alle Details im Buch des Professors, aber so uninteressant ich auch war, ich vermisste dieses Stück, um umfassend zu visualisieren, wie das Ganze funktioniert. Vielen Dank.
Riccardo Angius