Binary Exponential Backoff Algorithmus

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.

   tryToSend();

   if( Collision() ) {

     WaitTime = 1;

     do {

       wait( 51.2 * rand() % WaitTime );

       tryToSend();

       WaitTime *= 2;

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

     if( Collision() )

       BailOutWithError();

   }