Retard exponentiel - Exponential backoff

Le backoff exponentiel est un algorithme qui utilise la rétroaction pour diminuer de manière multiplicative le taux de certains processus, afin de trouver progressivement un taux acceptable.

Algorithme de backoff exponentiel binaire

Dans une variété de réseaux informatiques , le backoff exponentiel binaire ou le backoff exponentiel binaire tronqué fait référence à un algorithme utilisé pour espacer les retransmissions répétées du même bloc de données , souvent pour éviter la congestion du réseau .

Des exemples sont la retransmission de trames dans les réseaux à accès multiple avec détection de porteuse avec évitement des collisions (CSMA/CA) et à accès multiple avec détection de porteuse avec détection de collision (CSMA/CD), où cet algorithme fait partie de la méthode d' accès au canal utilisée pour envoyer des données sur ces réseaux. réseaux. Dans les réseaux Ethernet , l'algorithme est couramment utilisé pour planifier les retransmissions après des collisions. La retransmission est retardée d'une quantité de temps dérivée du créneau horaire (par exemple, le temps qu'il faut pour envoyer 512 bits, c'est-à-dire 512 bits-temps ) et du nombre de tentatives de retransmission.

Après c collisions, un nombre aléatoire de slots compris entre 0 et 2 ^c − 1 est choisi. Après la première collision, chaque expéditeur attendra 0 ou 1 créneau horaire. Après la deuxième collision, les expéditeurs attendront entre 0 et 3 créneaux horaires ( inclus ). Après la troisième collision, les expéditeurs attendront entre 0 et 7 créneaux horaires (inclus), et ainsi de suite. Au fur et à mesure que le nombre de tentatives de retransmission augmente, le nombre de possibilités de retard augmente de façon exponentielle .

Le « tronqué » signifie simplement qu'après un certain nombre d'augmentations, l'exponentiation s'arrête ; c'est-à-dire que la temporisation de retransmission atteint un plafond, et ensuite n'augmente plus. Par exemple, si le plafond est fixé à i = 10 (comme c'est le cas dans la norme IEEE 802.3 CSMA/CD), le délai maximum est de 1023 créneaux horaires. Ceci est utile car ces retards provoquent également des collisions avec d'autres stations qui envoient. Il est possible que, sur un réseau occupé, des centaines de personnes soient prises dans un seul ensemble de collisions.

Lorsque l'évitement des collisions n'est pas un objectif, une version plus simple du ralentissement exponentiel peut être utilisée pour simplement éviter la congestion du réseau. Dans cette version de l'algorithme, la retransmission est retardée d'un temps prédéterminé (non aléatoire). Par exemple, dans le protocole SIP sur un transport non fiable (comme UDP ), le client retransmet les demandes à un intervalle qui commence à T1 secondes (généralement 500 ms, ce qui est l'estimation du temps aller-retour ) et double après chaque retransmission jusqu'à ce qu'il atteint T2 secondes (qui est par défaut à 4 s). Il en résulte des intervalles de retransmission de 500 ms, 1 s, 2 s, 4 s, 4 s, 4 s, etc.

Exemple d'algorithme de backoff exponentiel

Cet exemple provient du protocole Ethernet , où un hôte expéditeur est capable de savoir quand une collision s'est produite (c'est-à-dire qu'un autre hôte a essayé de transmettre), quand il envoie une trame. Si les deux hôtes tentaient de retransmettre dès qu'une collision se produisait, il y aurait encore une autre collision - et le schéma continuerait pour toujours. Les hôtes doivent choisir une valeur aléatoire dans une plage acceptable pour s'assurer que cette situation ne se produise pas. Un algorithme de backoff exponentiel est donc utilisé. La valeur '51,2 s' est utilisée ici à titre d'exemple car il s'agit du slot time pour une ligne Ethernet 10 Mbit/s (voir Slot time ). Cependant, 51,2 µs pourraient être remplacés par n'importe quelle valeur positive, en pratique.

1. Lorsqu'une collision se produit pour la première fois, envoyez un "signal de brouillage" pour empêcher l'envoi de données supplémentaires.
2. Renvoyez une trame après 0 seconde ou 51,2 s, choisie au hasard.
3. Si cela échoue, renvoyez la trame après 0 s, 51,2 s, 102,4 s ou 153,6 s.
4. Si cela ne fonctionne toujours pas, renvoyez la trame après k · 51,2 s , où k est un entier aléatoire compris entre 0 et 2 ³ − 1 .
5. En général, après la c ième tentative infructueuse, renvoyez la trame après k · 51,2 s , où k est un entier aléatoire compris entre 0 et 2 ^c − 1 .

Retrait attendu

Étant donné une distribution uniforme des temps d' attente , le temps d' attente attendu est la moyenne des possibilités. C'est-à-dire qu'après c collisions, le nombre de créneaux d'attente est dans [0, 1, ..., N ] , où N = 2 ^c − 1 et le temps d'attente attendu (en créneaux) est

${\displaystyle {\frac {1}{N+1}}\sum _{i=0}^{N}i.}$

Par exemple, le temps d'attente prévu pour la troisième collision ( c = 3 ), on pourrait d'abord calculer le temps d'attente maximum, N :

${\style d'affichage N=2^{c}-1}$

${\style d'affichage N=2^{3}-1=8-1}$

${\style d'affichage N=7,}$

puis calculez la moyenne des possibilités de temps d'attente :

${\displaystyle \operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}} {\frac {N(N+1)}{2}}={\frac {N}{2}}={\frac {2}{c}-1}{2}}}$.

qui est, pour l'exemple, E(3) = 3,5 slots.

Voir également

• Théorie du contrôle

Les références

•  Cet article incorpore  du matériel du domaine public du document de la General Services Administration : "Federal Standard 1037C" .