Exponential backoff

Laatst moest ik voor een klant een stukje software ontwikkelen waarmee via het lichtnet met een aantal apparaten gecommuniceerd moest worden. Een netwerk via het lichtnet dus.

Gelukkig is tegenwoordig de hardware hiervoor goed genoeg om dit (relatief) betrouwbaar te kunnen doen. Uiteraard moet er voldoende robuustheid in je protocol zitten zodat foute pakketten opgevangen kunnen worden. Maar daarvoor zijn voldoende protocollen beschikbaar om dat goed te kunnen doen. In dit geval paste er geen vanwege licentie technische redenen, dus heb ik uit mijn bibliotheek een passend protocol gehaald

Een nieuwe uitdaging was het feit dat alle apparaten elkaars pakketten ontvangen. En dus ook elkaars pakketten kunnen verstoren. Eigenlijk net als bij Ethernet. Helaas kun je bij powerline communicatie geen carrier detect implementeren, maar het protocol Carrier Sense Multiple Access (CSMA) kun je zonder meer gebruiken. Dit protocol maakt gebruik van het zogenaamde 'exponential backoff' algoritme. Dit algoritme werkt op basis van hertransmissies van hetzelfde pakket totdat er geen botsing meer plaats vindt. Nu kun je natuurlijk een Token Ring achtig systeem bedenken waarbij de zender pas mag gaan zenden dat als hij een speciaal token heeft afgevangen. Een globale lock zeg maar. Nu is dat niet alleen ongelooflijk inefficiënt maar de implementatie wordt er ook ingewikkelder van. En als het snel af moet is dat niet echt een optie. Exponential backoff dus.

Het idee is dat elke zender gewoon gaat zenden wanneer nodig. Als het pakket niet is aangekomen zend het opnieuw. Je hogere protocol moet dus wel een mogelijkheid hebben om te detecteren of het commando is verwerkt. Maar in een simpel command response systeem is dat makkelijk te realiseren: een simpele ACK met een timeout als NAK voldoet al. Als iedere zender zomaar gaat zenden moet er een soort van willekeur in je retry zitten; anders zou het fout blijven gaan na de eerste botsing. Een standaard Mersenne Twister pseudo-random generator is voldoende. Door verder de backoff nog exponentieel te maken verruim je de netwerk capaciteit en door de backoff niet oneindig op te laten lopen heb je een basis voor een solide communicatie over publieke spreek kanalen.

Nu alleen nog bedenken hoe ik een twitter toepassing hiervoor kan bedenken.

/*!
 * \brief     Retransmission delays are computed using the Truncated Binary
 *            Exponential Backoff algorithm: [0, 1 or 2] ^ retry-1
 *
 * \param   anCount [in] current try count.
 *
 * \return  Time to wait for next retransmit.
 */
int ResendTime( int anCount )
{
    long nTime = 0;

    if ( anCount <= 1 )
    {
        nTime = 0;
    }
    else if ( anCount <= 8 )
    {
        /* Up to 8 retransmissions allows approx. 2^8 = 256 nodes on this network. */
        nTime = Sys_Random( 2 );
        while (anCount > 2)
        {
            nTime *= nTime;
            anCount--;
        }
    }
    else
    {
        /* We've passed the truncate point. Now just backoff */
        nTime = Sys_Random( 64 );
    }

    return (nTime);
}