Găleată cu scurgeri

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Analogia cu găleți scurgeri

Cupa cu scurgeri este un algoritm utilizat în rețelele de calculatoare cu comutare de pachete și în rețelele de telecomunicații . Poate fi folosit pentru a verifica dacă transmisiile de date de pachete , [1] sunt bine delimitate în lățime de bandă și debit. Poate fi folosit și ca programator de rețea . Algoritmul bucket leaky poate fi în cele din urmă folosit ca un contor , de exemplu pentru a detecta când rata medie sau de vârf a anumitor procese stocastice depășește limitele prestabilite.

Operațiune

Algoritmul găleții care se scurge se bazează pe (și își ia numele din) analogia unei găleți cu o gaură în fund, prin care orice cantitate de apă conținută va curge întotdeauna cu aceeași viteză, cu excepția cazului în care (sau până) găleata este gol. Dacă apa se adaugă prea repede, aceasta va depăși capacitatea găleată în volum și revărsare.

Acest mecanism stabilește o limită medie de transmisie prin orificiul din partea de jos, dar marchează, de asemenea, o limită la transmisia de vârf prin capacitatea maximă a cupei.

Două metode diferite de aplicare a analogiei cu găuri scurse sunt descrise în literatură , [2] [3] [4] [5], fiecare dintre ele fiind adesea descrisă fără a menționa cealaltă. Acest lucru a dus la o mulțime de confuzie cu privire la ceea ce este algoritmul corect și care sunt proprietățile sale.

Într-o versiune, bucket-ul este reprezentat de un contor sau de o variabilă generică și este separat de fluxul de trafic și de planificarea evenimentelor. [2] [4] [5] De fapt, este utilizat doar pentru a verifica dacă traficul sau evenimentele respectă limitele predefinite: contorul este incrementat pentru fiecare pachet care ajunge și scade constant. În consecință, valoarea contorului la sosirea unui pachet indică conformitatea acestuia cu limitele de bandă sau de rafală. Prin urmare, în această versiune, cupa cu scurgeri este utilizată în esență ca instrument de măsurare.

În a doua versiune, bucket-ul este reprezentat de o coadă FCFS într-un flux de trafic. [3] Coada este utilizată pentru a controla direct acest flux: pachetele sunt plasate în coadă de îndată ce sosesc și sunt eliminate cu o rată constantă. În consecință, viteza la care coada este servită controlează în mod direct progresul transmisiei, în așa fel încât să impună conformitatea mai degrabă decât să o controleze și unde coada este servită la o rată fixă ​​(și unde pachetele sunt la fel lungime), fluxul de trafic rezultat este neapărat lipsit de jitter sau vârfuri excesiv de mari.

Bucet-ul cu scurgeri ca o coadă poate fi, prin urmare, văzut ca un caz particular de cupă token . [6] Implementarea compartimentului cu scurgeri ca o coadă nu utilizează resursele curente ale rețelei în mod eficient. De fapt, deoarece transmite pachete doar la intervale fixe, vor exista mai multe cazuri în care volumul de trafic va fi foarte scăzut și porțiuni mari din resursele rețelei (lățimea de bandă în special) nu vor fi utilizate. Prin urmare, nu există niciun mecanism în implementarea cupei scurgeri ca o coadă care să permită fluxuri de rafală unice până la viteza maximă permisă, în așa fel încât să se consume mai multe resurse de rețea atunci când nu ar exista conflicte.

Găleată cu scurgeri ca metru

Jonathan S. Turner este creditat [7] ca creatorul algoritmului cu găuri scurgeri. El la descris inițial după cum urmează: "Un contor, asociat fiecărui utilizator care transmite, care este incrementat de fiecare dată când utilizatorul trimite un pachet și este decrementat periodic. Dacă contorul depășește un prag pe măsură ce este incrementat, rețeaua aruncă pachetul. L "utilizatorul specifică rata la care contorul este decrementat (ceea ce duce la o lățime medie de bandă) și valoarea pragului (pentru a măsura rafala )". [2]

O versiune substanțial echivalentă a acestui algoritm este Generic Cell Rate Algorithm , descris de UIT-T în Recomandarea I.371 [5] și în specificația UNI a Forumului ATM . [4]

Poliția rutieră și conturarea traficului
Poliția rutieră : gremlinul verifică dacă găleată este plină și deschide ușa capcană aruncând pachetul. În dreapta sunt reprezentate pachetele care nu sunt conforme cu viteza permisă.
Formarea traficului : gremlinul verifică dacă cupa este plină și trage ușa în sus pentru a bloca traficul. În stânga sunt reprezentate orice pachete aruncate din cauza depășirii cozii .

Comentând descrierea algoritmului Forum ITU-T / ATM, David E. McDysan și Darrel L. Spohn introduc figura fictivă a unui gremlin . [6] Acest gremlin inspectează nivelul apei în găleată și, atunci când nivelul apei depășește limita prestabilită, poate acționa în conformitate cu două moduri de operare :

  • Poliția rutieră : gremlinul verifică dacă nivelul apei a depășit limita, în consecință deschide o ușă capcană și aruncă pachetul.
  • Formarea traficului : gremlinul verifică dacă nivelul apei a depășit limita, ridicând în consecință o ușă pentru a bloca temporar fluxul pachetelor până când nivelul apei revine sub limita permisă.

Diferența dintre cei doi algoritmi constă în faptul că cel al lui Turner se referă, fără îndoială, la poliția rutieră , în timp ce cea a Forumului ITU-T / ATM este aplicabilă atât poliției traficului, cât și formării traficului . De asemenea, Turner nu afirmă că contorul ar trebui să fie incrementat numai atunci când pachetul este conform, care este atunci când incrementarea nu ar determina depășirea limitei. Pentru a reconcilia descrierea lui Turner cu cea a Forumului ITU-T / ATM, ar fi necesar să se schimbe partea în care Turner afirmă „Dacă contorul depășește un prag în timp ce este incrementat, rețeaua aruncă pachetul” în „Dacă contorul, fiind incrementat, ar depăși pragul, rețeaua aruncă pachetul și contorul nu este incrementat.

Comparație cu cupa token

Pictogramă lupă mgx2.svg Același subiect în detaliu: găleată de token .
Secțiunea goală
Această secțiune despre informatică este încă goală . Ajută-ne să-l scriem!

Notă

  1. ^ În gestionarea concretă a traficului, bucketul cu scurgeri este aplicat în mod normal în PDU-urile celui de-al doilea strat al stivei ISO / OSI ( stratul de legătură de date ), deci s-ar putea argumenta că vorbim despre „pachete” și nu „cadre”. ( rame ). Cu toate acestea, termenul "pachet", pe lângă referirea la stratul de rețea PDU, este, de asemenea, utilizat în literatură pentru a se referi la un set generic de date. Acest lucru nu înseamnă că acest algoritm poate fi implementat numai în stratul de legătură de date .
  2. ^ a b c Turner, J., Noi direcții în comunicații (sau în ce direcție către era informațională?) . Revista de comunicații, IEEE 24 (10): 8-15. ISSN 0163-6804, 1986.
  3. ^ a b Andrew S. Tanenbaum, Rețele de calculatoare, ediția a patra , ISBN 0-13-166836-6 , Prentice Hall PTR, 2003., pagina 401.
  4. ^ a b c ATM Forum, User Network Interface (UNI), v. 3.1, ISBN 0-13-393828-X , Prentice Hall PTR, 1995.
  5. ^ a b c UIT-T, Controlul traficului și controlul congestiei în ISDN B , Recomandarea I.371, Uniunea Internațională a Telecomunicațiilor, 2004, Anexa A, pagina 87.
  6. ^ a b McDysan, David E. și Spohn, Darrel L., ATM: Theory and Application , ISBN 0-07-060362-6 , seria McGraw-Hill on communications computer, 1995, paginile 358-9.
  7. ^ Andrew S. Tanenbaum, Rețele de calculatoare, ediția a patra , ISBN 0-13-166836-6 , Prentice Hall PTR, 2003, pagina 400.

Elemente conexe

Alte proiecte

Adus de la „ https://it.wikipedia.org/w/index.php?title=Leaky_bucket&oldid=106710649 ”