Binary Exponential Backoff Algorithmus

Markus Gast #2061916
Lesenswert?
• ▲
▼ 
Hallo zusammen,

ich bin auf der Suche nach einen Algorithmus zum Berechnen des 
Mediumzugriffzeitpunkt gemäß dem Binary Exponential Backoff-Verfahren.
Wenn der Algorithmus bereits in C-Code verfasst wäre, hätte ich 
natürlich auch nichts dagegen einzuwenden. ;)

Bis jetzt habe ich noch nichts gefunden. Nicht einmal die Wiki gibt groß 
was her...

Viele Grüße
Markus
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Karl H. #2061930
Lesenswert?
• ▲
▼ 
Markus schrieb:

> Bis jetzt habe ich noch nichts gefunden. Nicht einmal die Wiki gibt groß
> was her...

Das hier?

1
Der Binary Exponential Backoff ist ein Stauauflösungsmechanismus im

2
Ethernet nach IEEE 802.3. Wird von Stationen im Ethernet eine Kollision

3
erkannt, beenden diese Stationen ihre Sendung und versuchen sofort oder

4
nach einer Slot-Time von 51,2 µs (entspricht 512 Bit, gilt nur für 10/100

5
MBit/s Ethernet, 4,096 µs und 4096 Bit bei 1 GBit/s) erneut ihre Sendung

6
über das Ethernet zu übertragen. Dabei kann es erneut zu einer Kollision

7
kommen, wenn beide Stationen zufällig die gleiche Wahl treffen. Beim

8
nächsten Versuch wird nun jede der beiden Stationen wieder per

9
Zufallsentscheidung einen neuen Starttermin auswählen, diesmal aber aus

10
vier Möglichkeiten: 0, 1, 2 oder 3 Slot-Times, also 22. Bei einer erneuten

11
Kollision sind es dann 2^3 = 8 Möglichkeiten, dann 16, 32, 64, 128, 256, 512

12
und schließlich 1024. 1024 (210) stellt auch die Maximalgrenze der

13
Möglichkeiten dar (truncated). Nach insgesamt 16 erfolglosen

14
Übertragungsversuchen mit Kollision wird mit einer Fehlermeldung des

15
Ethernet-Controllers abgebrochen.


Scheint mir (wie die meisten Dinge mit großem Namen) nicht all zu schwer 
zu sein.

1
   tryToSend();

2


3
   if( Collision() ) {

4
     WaitTime = 1;

5
     do {

6
       wait( 51.2 * rand() % WaitTime );

7
       tryToSend();

8
       WaitTime *= 2;

9
     } while( Collision() %% WaitTime < 2048 );

10


11
     if( Collision() )

12
       BailOutWithError();

13
   }


So ungefähr.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
doch gast Gast #2062190
Lesenswert?
• ▲
▼ 
Kai S. schrieb:
> doch gast schrieb:
>> @Karl Heinz
>>> } while( Collision() %% WaitTime < 2048 );
>> Gibt es einen %%-Operator in C oder hast du dich schlichtweg vertippt?
>
> Nein, '%%' gibt es nicht. Sollte offensichtlich '&&' sein.
Na klar, da hätte ich jetzt selbst drauf kommen können, die Tasten 
liegen direkt nebeneinander und '&&' macht deutlich mehr Sinn als '%'...

Danke.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt. Bitte hier nur auf die ursprüngliche Frage antworten, für neue Fragen einen neuen Beitrag erstellen.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.