Eksponentiaalinen suljinnopeus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. syyskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Eksponentiaalinen backoff on algoritmi , joka käyttää palautetta pienentääkseen moninkertaisesti jonkin prosessin taajuutta löytääkseen asteittain hyväksyttävän taajuuden.

Binäärinen eksponentiaalinen suljin / Typistetty eksponentiaalinen suljin

Monissa tietokoneverkoissa termi binaarinen eksponentiaalinen peruutus tai katkaistu binaarinen eksponentiaalinen peruutus viittaa algoritmiin, jolla vähennetään saman tietolohkon toistuvia lähetyksiä, usein osana toimenpiteitä verkon ruuhkautumisen välttämiseksi.

Esimerkkejä ovat datakehysten uudelleenlähetys kantoaallon mukaisessa monipääsyssä törmäyksenestoverkoissa (CSMA/CA) ja kantoaallon tunnistuksen mukaisissa monipääsyissä törmäyksen havaitsemisverkoissa (CSMA/CD), joissa tämä algoritmi on osa kanavan käyttömenetelmää, jota käytetään tietojen lähettämiseen. näitä verkkoja. Ethernet - verkoissa tätä algoritmia käytetään tyypillisesti ajoittamaan uudelleenlähetykset törmäysten jälkeen. Uudelleenlähetys viivästyy tietyn ajan riippuen väliajasta ja uudelleenlähetysyritysten määrästä.

C törmäyksen jälkeen valitaan satunnainen määrä aikaväliä välillä 0 ja 2 s −1. Ensimmäisen törmäyksen jälkeen jokainen lähettäjä odottaa 0 tai 1 väliajan. Toisen törmäyksen jälkeen lähettäjät odottavat missä tahansa 0–3 väliaikaa mukaan lukien. Kolmannen törmäyksen jälkeen lähettäjät odottavat missä tahansa 0 - 7 väliaikaa, mukaan lukien jne. Kun uudelleenlähetysyritysten määrä kasvaa, viivevaihtoehtojen määrä kasvaa eksponentiaalisesti.

Sana "katkaistu" tarkoittaa, että tietyn lisäysmäärän jälkeen eksponentiaalinen kasvu pysähtyy, eli uudelleenlähetyksen aikakatkaisu saavuttaa katon, jonka jälkeen se ei enää kasva. Jos esimerkiksi katto on asetettu arvoon i = 10 (kuten IEEE 802.3 CSMA/CD [1] -standardissa ), maksimiviive on 1023 aikaväliä.

Koska nämä viiveet aiheuttavat törmäyksiä muiden tietoja lähettävien asemien kanssa, on mahdollista, että kiireisessä verkossa satoja ihmisiä joutuu yhteen törmäyssarjaan. Tällaisen mahdollisuuden olemassaolon vuoksi prosessi päättyy 16 lähetysyrityksen jälkeen.

Esimerkki eksponentiaalisesta soak-algoritmista

Tämä esimerkki on otettu Ethernet -protokollan kuvauksesta [2] , jossa lähettäjällä on mahdollisuus tietää kehyksen lähetyshetkellä, että törmäys on tapahtunut (eli toinen isäntä yritti lähettää dataa). Jos molemmat isännät yrittäisivät lähettää tiedot uudelleen heti törmäyksen tapahtuessa, tapahtuisi seuraava törmäys, ja tämä järjestys jatkuisi ikuisesti. Isäntien on valittava satunnainen arvo hyväksyttävällä alueella varmistaakseen, että tällaista tilannetta ei tapahdu, joten käytetään eksponentiaalista soak-algoritmia. Tässä käytetään esimerkkinä lukua 51,2 µs, mutta tämä on aikaväliaika 10 Mbit/s Ethernet-linkille (katso Slot time ). Mutta käytännössä 51,2 µs voidaan korvata millä tahansa muulla positiivisella arvolla.

Kun ensimmäinen törmäys tapahtuu, lähetä "ruuhkasignaali" estääksesi lisätietojen lähettämisen.
Lähetä kehys uudelleen satunnaisesti valitun 0 tai 51,2 µs:n viiveen jälkeen.
Jos lähetys epäonnistuu, lähetä kehys uudelleen 0, 51,2 µs, 102,4 µs tai 153,6 µs viiveen jälkeen.
Jos tämä epäonnistuu, lähetä kehys uudelleen k · 51,2 µs:n viiveen jälkeen, missä k on satunnainen kokonaisluku välillä 0 ja 2 3 −1.
Yleensä c :nnen epäonnistuneen lähetyksen jälkeen lähetä kehys uudelleen k · 51,2 µs:n viiveen jälkeen, missä k on satunnainen kokonaisluku välillä 0 ja 2 s −1.

Odotettu altistuminen

Jos annetaan tasainen liotusaikojen jakautuminen, pitoajan odotus on kaikkien mahdollisten arvojen keskiarvo. Toisin sanoen c törmäyksen jälkeen pitovälien lukumäärä on välillä [0, 1, …, N ], jossa N = 2 s −1, ja odotettu pitoaika (raoissa) on

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

Esimerkiksi odotettu suljinaika kolmannessa ( c = 3) törmäyksessä voidaan ensin laskea suurimmalle suljinajalle N :

N=2^{c}-1

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

N = 7

... ja laske sitten kaikkien altistumisvaihtoehtojen keskiarvo:

\operaattorinimi {E}(c)={\frac {1}{N+1}}\sum _{{i=0}}^{{N}}i

\operaattorinimi {E}(3)={\frac {1}{7+1}}\sum _{{i=0}}^{{7}}i={\frac {1}{8}}( 0+1+2+3+4+5+6+7)={\frac {28}{8))

\operaattorinimi {E}(3)=3.5

… saa 3,5 odotetun liotusrakojen lukumäärän kolmen törmäyksen jälkeen.

Yllä oleva johtaminen on suurelta osin tarpeeton, kun ymmärrät, että peräkkäisten kokonaislukujen keskiarvo on yhtä suuri kuin joukon pienimmän ja suurimman luvun keskiarvo. Tämä tarkoittaa, että peräkkäisten kokonaislukujen joukon A keskiarvo a 0 , a 1 , a 2 , … a m on yksinkertaisesti arvon a 0 ja a m tai ( a 0 + a m )/2 keskiarvo.

Sovellettaessa yllä olevaa odotetun altistusajan löytämisen ongelmaa kaava on yksinkertaistettu:

\operaattorinimi {E}(c)={\frac {2^{c}-1}{2}}

... tai tietyssä tapauksessa tulkitaan puoleksi suurimmasta mahdollisesta viiveajasta.

Huomaa myös, että loppusumma on kolmion muotoinen luku , kuten yhtä suuri kuin…

{\frac {(2^{c}-1)2^{c}}{2}}={\frac {N(N+1)}{2}}

…joka kumoaa summan ylittävällä nimittäjällä, jättäen vain…

{\frac {N}{2}}={\frac {2^{c}-1}{2}}

Linkit

↑ IEEE -standardi 802.3-2008 . IEEE. Haettu: 22.9.2010.
↑ Computer Networks , Peterson ja Davie