www.mikrocontroller.net

Forum: Compiler & IDEs Binary Exponential Backoff Algorithmus


Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus schrieb:

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

Das hier?
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 (entspricht 512 Bit, gilt nur für 10/100
MBit/s Ethernet, 4,096 µs und 4096 Bit bei 1 GBit/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. Beim
nächsten Versuch wird nun jede der beiden Stationen wieder per
Zufallsentscheidung einen neuen Starttermin auswählen, diesmal aber aus
vier Möglichkeiten: 0, 1, 2 oder 3 Slot-Times, also 22. Bei einer erneuten
Kollision sind es dann 2^3 = 8 Möglichkeiten, dann 16, 32, 64, 128, 256, 512
und schließlich 1024. 1024 (210) stellt auch die Maximalgrenze der
Möglichkeiten dar (truncated). Nach insgesamt 16 erfolglosen
Übertragungsversuchen mit Kollision wird mit einer Fehlermeldung des
Ethernet-Controllers abgebrochen.

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

   tryToSend();

   if( Collision() ) {
     WaitTime = 1;
     do {
       wait( 51.2 * rand() % WaitTime );
       tryToSend();
       WaitTime *= 2;
     } while( Collision() %% WaitTime < 2048 );

     if( Collision() )
       BailOutWithError();
   }


So ungefähr.

Autor: Markus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, diese Backoffzeit meine ich...
Verstehen tue ich die 10 Codezeilen dennoch nicht.
Das andere Problem. Ich habe keine rand(om) bei meinem MSP430 muss meine 
Zufallszahlen irgendwie anderster generieren...

Autor: doch gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Karl Heinz
> } while( Collision() %% WaitTime < 2048 );
Gibt es einen %%-Operator in C oder hast du dich schlichtweg vertippt?

Autor: Kai S. (zigzeg)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: doch gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du die wenigen Codezeilen schon nicht verstehst, was willst du dann 
mit dem Algorithmus machen? ;-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
doch gast schrieb:
> @Karl Heinz
>> } while( Collision() %% WaitTime < 2048 );
> Gibt es einen %%-Operator in C oder hast du dich schlichtweg vertippt?

schlichtweg vertippt. War noch früh am Morgen :-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus schrieb:

> Das andere Problem. Ich habe keine rand(om) bei meinem MSP430 muss meine
> Zufallszahlen irgendwie anderster generieren...

Ja, das versteh ich. Eine freie Implementierung für rand() zu finden, 
ist ja auch Raketentechnik.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
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.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.