Forum: Compiler & IDEs Binary Exponential Backoff Algorithmus


von Markus (Gast)


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

von Karl H. (kbuchegg)


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.

von Markus (Gast)


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...

von doch gast (Gast)


Lesenswert?

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

von Kai S. (zigzeg)


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.

von doch gast (Gast)


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.

von Simon K. (simon) Benutzerseite


Lesenswert?

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

von Karl H. (kbuchegg)


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 :-)

von Karl H. (kbuchegg)


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.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.