Algoritm de retrocedare exponențială binară

Această intrare sau secțiune despre subiectul teoriilor informatice nu citează sursele necesare sau cei prezenți sunt insuficienți . Comentariu : Această intrare lipsește complet de surse Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

În telecomunicații, algoritmul exponențial de retragere este un algoritm utilizat în protocolul de acces multiplu CSMA / CD pentru a decide timpul de preluare a transmisiei pe un mediu partajat de una sau mai multe stații de transmisie ( gazde ) odată ce a fost detectată o coliziune. Algoritmul este aplicat la primirea secvenței de blocare care definește mesajul de întrerupere a transmisiei de pachete.

După cum se știe, Ethernet folosește protocolul CSMA / CD , adică canalul pe care sunt transmise cadrele este partajat de mai multe stații ( acces multiplu ) care pot vedea când canalul este liber sau nu (detectarea operatorului sau Carrier Sense ) și pentru a detecta coliziuni ( Collision Detection ). Principala caracteristică a protocolului CSMA / CD este că, odată detectată o coliziune, așteaptă un interval aleatoriu înainte de retransmisia, acest interval este calculat de fiecare dată de algoritmul de retrocedare exponențială .

Algoritmul

1. Timpul este calculat ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">T.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">p</span></span>}}}${\ displaystyle T_ {p}} cel mai rău caz propagare dus-întors (2τ).
2. Pentru prima coliziune, cele două gazde implicate în eroarea de transmisie aleg în mod aleatoriu între 0 și 1. Gazda care alege 0 nu retransmite, în timp ce gazda care alege 1 retransmite.
3. Dacă ambele gazde aleg același număr, are loc o nouă coliziune și apoi împarte timpul în intervale ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">P.</span></span>}}${\ displaystyle P} că ultima ${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">T.</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">p</span></span>}}}${\ displaystyle T_ {p}} .
4. La prima coliziune (cu ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">1</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\le </span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">the</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\le </span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">10</span></span>}}${\ displaystyle 1 \ leq i \ leq 10} ):
   1. alegi la întâmplare un număr ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}}${\ displaystyle N} , astfel încât {\ displaystyle 0 \ leq N <2 ^ {i} -1} .
   2. aştepta ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\cdot </span></span>\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">P.</span></span>}}${\ displaystyle N \ cdot P} intervale înainte de a reîncerca transmisia.
5. Pentru încercările ulterioare, i rămâne constant la 10.
6. Dacă vă aflați în ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">16</span></span>}}${\ displaystyle 16} -a coliziune se comunică o eroare în transmisie.

Toate transmisiile se fac la intervale de 2τ ( întârziere dus-întors).

După cum se poate vedea din algoritm, ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}}${\ displaystyle N} crește exponențial cu numărul de coliziuni care au avut loc, acest lucru garantează că timpul de retransmisie este minim dacă există puține stații de coliziune și că este foarte mare dacă există multe coliziuni, adică sunt multe stații care transmit. Alegerea exponentului maxim 16 ( limita de back-off ) a fost făcută prin studierea timpului pe care un cadru îl poate lua pentru a se propaga într-un cablu de lungime maximă și deciderea unei perioade de așteptare rezonabile înainte de a comunica o eroare de rețea.

Algoritmul pseudo-cod

 dacă încercare = 1 // prima încercare de a retransmite cadrul
atunci
   max: = 2
in caz contrar
   dacă încercați <backoff_limit
   apoi max: = max x2
așteptați (2t x aleatoriu (0, max-1))

Portal telematic : accesați intrări Wikipedia care vorbesc despre rețele, telecomunicații și protocoale de rețea