Exponenciális visszalépés

Az informatikában az exponenciális visszalépés (angolul exponential backoff) olyan algoritmus, amely egy folyamat erőforrásfelhasználását egy exponenciális függvény szerint csökkenti, amíg az el nem éri az elfogadható mértéket.

Egyik leggyakoribb alkalmazása a hálózatok tervezésénél a torlódáselkerülésre használt kettes exponenciális visszalépés protokoll (binary exponential back-off algorithm). Például egy LAN egy ütközési tartományában lévő számítógépek adni próbálnak a csatornán, majd ütközés esetén egy adott tartományból választanak egy véletlen időtartamot és ennek lejárta előtt nem próbálkoznak újra adással. Amennyiben újabb ütközés van, a véletlen várakozási idők meghatározására használt tartományt minden alkalommal megduplázzák.

Például az Ethernet protokoll esetében a visszalépési időt véletlenszerűen választják a:

$[0,1,2^{m-1}]\times t_{av}$

tartományból, ahol $t_{av}$ az alap várakozási idő: Ethernet esetén 51,2 μs, Fast Ethernetnél, 5,12 μs és $m=min(10,n)$, ahol $n$ az ütközések száma. Mivel a várakozási idő várható értéke 10 ütközés után már nem növekszik, ezt a változatot csonkolt bináris exponenciális visszalépés algoritmusnak (truncated binary exponential backoff) nevezik.

Források

• Seok-Kyu Kweon, Kang G. Shin: Statistical Real-Time Communication over Ethernet (PDF), acm.org