Was ist ein Binärer exponentieller Backoff-Algorithmus?
Lerne für das Fach Rechnernetze und verstehe nicht ganz wie ich anhand eines Wahrscheinlichkeitsbaum diese Aufgabe darstellen muss. Bitte um Erklärung der gestellten Aufgabe:
Zwei CSMA / CD Stationen konkurrieren nach der Übertragung eines Rahmens um die Benutzung des Kanals und verwenden dazu den binären exponentiellen Backoff-Algorithmus. a) Wie hoch ist die Wahrscheinlichkeit, dass die Konkurrenz in Runde n endet? Hinweis: Verwenden Sie einen Wahrscheinlichkeitsbaum, tragen Sie die Runden 1,2,3,4,5 dort ein, berechnen die Wahrscheinlichkeiten und verallgemeinern Sie dann die Ausführungen. b) Wie hoch ist die mittlere Anzahl der Runden in der Konkurrenzperiode?
2 Antworten
http://www.rvs.uni-bielefeld.de/~mblume/seminar/ss97/ethernet/backof.html
1. Runde: 2^1 verschiedene Wartezeiten
2. Runde: 2^2 verschiedene Wartezeiten
...
k. Runde: 2^k verschiedene Wartezeiten
...
10. Runde: 2^10 verschiedene Wartezeiten
11.-15. Runde: 2^10 verschiedene Wartezeiten (hier wird nicht mehr erhöht)
16. Runde: Abbruch des Übertragungsversuches
Das sollte für den Baum ausreichen.
Zu a): Vermutlich soll extrapoliert werden, als würde das Verfahren nach Runde 10 analog fortgesetzt - es lässt sich dann leichter berechnen.
Zu b): Übliche Berechnung eines Erwartungswertes
Der "Binary Exponential Backoff" ist ein Stauauflösungsmechanismus im Ethernet nach IEEE 802.3. Wird von Stationen im Ethernet eine Kollision erkannt, beenden diese Stationen ihre Sendung und versuchen sofort oder nach einer Slot-Time von 51,2 µs erneut ihre Sendung über das Ethernet zu übertragen. Dabei kann es erneut zu einer Kollision kommen, wenn beide Stationen zufällig die gleiche Wahl treffen.
Quelle: https://de.wikipedia.org/wiki/Binary_Exponential_Backoff