Exponenciální ustoupení - Exponential backoff

Exponenciální ustoupení je algoritmus který používá zpětná vazba multiplikativně snížit rychlost nějakého procesu, aby se postupně našla přijatelná rychlost.

Algoritmus binární exponenciální zpětné vazby

V různých počítačové sítě, binární exponenciální ustoupení nebo zkrácený binární exponenciální zpětný posun odkazuje na algoritmus slouží k opakování mezery retransmise stejného bloku data, často vyhněte se přetížení sítě.

Příkladem je opakovaný přenos rámy v nosič snímá vícenásobný přístup s vyhýbáním se kolizím (CSMA / CA) a Carrier Sensation Multiple Access with Collision Detection (CSMA / CD), kde je tento algoritmus součástí přístup ke kanálu metoda používaná k odesílání dat v těchto sítích. v Ethernet sítí se algoritmus běžně používá k plánování opakovaných přenosů po kolizích. Opakovaný přenos je zpožděn o částku čas odvozeno z slot time (například čas potřebný k odeslání 512 bitů; tj. 512 bitové časy ) a počet pokusů o opakovaný přenos.

Po C kolize, náhodný počet časů slotů mezi 0 a 2^C − 1 je vybrán. Po první kolizi bude každý odesílatel čekat 0 nebo 1 slotové časy. Po druhé kolizi budou odesílatelé čekat kdekoli od 0 do 3 slotů (včetně ). Po třetí kolizi budou odesílatelé čekat kdekoli od 0 do 7 časů slotů (včetně) atd. Jak se zvyšuje počet pokusů o opakovaný přenos, zvyšuje se počet možností zpoždění exponenciálně roste.

„Zkrácený“ jednoduše znamená, že po určitém počtu nárůstů se umocňování zastaví; tj. časový limit retransmise dosáhne stropu a poté se dále nezvyšuje. Například pokud je strop nastaven na i = 10 (jak je to v IEEE 802.3 Standard CSMA / CD^[1]), pak je maximální zpoždění 1023 slotových časů. To je užitečné, protože tato zpoždění způsobí, že se srazí i další vysílající stanice. Existuje možnost, že na rušné síti mohou být stovky lidí zachyceny v jedné kolizní sadě.^[2]

Příklad exponenciálního zpětného algoritmu

Tento příklad pochází z Ethernet protokol,^[3] kde odesílající hostitel je schopen vědět, kdy došlo ke kolizi (tj. jiný hostitel se pokusil o přenos), když odesílá rámec. Pokud by se oba hostitelé pokusili znovu vyslat, jakmile dojde ke kolizi, došlo by k další kolizi - a vzor by pokračoval navždy. Hostitelé musí zvolit náhodnou hodnotu v přijatelném rozsahu, aby zajistili, že k této situaci nedojde. Použije se proto exponenciální zpětný algoritmus. Jako příklad se zde používá hodnota „51,2 μs“, protože se jedná o čas slotu pro ethernetovou linku 10 Mbit / s (viz Slot time ). V praxi by však 51,2 μs mohlo být nahrazeno jakoukoli kladnou hodnotou.

1. Když dojde ke kolizi poprvé, pošlete „rušivý signál“, abyste zabránili odesílání dalších dat.
2. Znovu odešlete snímek po 0 sekundách nebo 51,2 μs, které byly vybrány náhodně.
3. Pokud se to nepodaří, odešlete snímek znovu po 0 s, 51,2 μs, 102,4 μs nebo 153,6 μs.
4. Pokud to stále nefunguje, odešlete snímek znovu po k · 51,2 μs, kde k je náhodné celé číslo mezi 0 a 2³ − 1.
5. Obecně platí, že po Cth neúspěšný pokus, znovu odeslat snímek po k · 51,2 μs, kde k je náhodné celé číslo mezi 0 a 2^C − 1.

Očekávaná zpětná vazba

Vzhledem k rovnoměrné rozdělení návratových časů, očekávaný backoff time je průměr z možností. To je po C kolize, počet zpětných slotů je v [0, 1, ..., N], kde N = 2^C − 1 a očekávaná doba zpětného chodu (ve slotech) je

${ displaystyle { frac {1} {N + 1}} součet _ {i = 0} ^ {N} i.}$

Například očekávaný čas vypnutí pro třetí (C = 3) kolize, dalo by se nejprve vypočítat maximální čas zpětného chodu, N:

${ displaystyle N = 2 ^ {c} -1}$

${ displaystyle N = 2 ^ {3} -1 = 8-1}$

${ displaystyle N = 7,}$

a poté vypočítat průměr možností zpětného času:

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

což je například E (3) = 3,5 slotu.

Viz také

• Teorie řízení

Reference

• Tento článek zahrnujepublic domain materiál z Obecná správa služeb dokument: „Federální norma 1037C“.