Evaluări Privind Întârzierea Si Lungimea Cozilor în Comutatoarele cu Siruri pe Intrare

Universitatea “Politehnica” din București

Facultatea de Electronică, Telecomunicații și Tehnologia Informației

Evaluări privind întârzierea și lungimea cozilor în comutatoarele cu șiruri pe intrare

Proiect de diplomă

prezentat ca cerință parțială pentru obținerea titlului de

Inginer în domeniul Electronică și Telecomunicații

programul de studii de licență Rețele și Software de

Telecomunicații

Conducător științific Absolvent

Conf. Dr. Ing. Lucian IOAN Georgiana Carmen ONOFREI

2016

Formular inscriere – anexa 1 scanat

Declaratie onestitate – anexa 5 scanat

Cuprins

Capitol 1 – Cunoștințe generale privind comutatoarele de celule cu șiruri pe intrare

Capitol 1.1 – Arhitecturile comutatoarelor cu șiruri pe intrare

Capitol 2 – Performanțele comutatoarelor cu șiruri pe intrare

Capitol 3 – Modelare matematică

Capitol 3.1 – Metodologia analizei

Capitol 3.2 – Limite cu privire la întârzierea medie și dimensiunea cozii

Capitol 4 – Programe de calcul și reprezentare grafică

Capitol 4.1 – Descriere funcții

Capitol 4.2 – Modul de utilizare

Capitol 5 – Simularea comutatoarelor cu șiruri la intrare

Capitol 5.1 – Descriere program

Capitol 5.2 – Mod de utilizare

Capitol 6 – Rezumate teoretice și experimentale . Interpretări și concluzii

Capitol 7 – Bibliografie

Listă acronime

ATM – ASYNCHRONOUS TRANSFER MODE

CIOQ – Combinated Input Oputput Queues

CM-SA – Cell-mode Schedulling Algorithm

DTMC –

FIFO – First In First Out

HoL – Head Of Line

IQ – Input Queue

MWM – Maximum Weight Matching

OCF – Oldest cell first

OQ – Oupput queue

QoS – Quality of Service

VOQ – Virtual Output Queue

Introducere

Capitol 1 – Cunoștințe generale privind comutatoarele de celule cu șiruri pe intrare

În rețelele ATM informația este transportată prin intermediul unor formațiuni binare, numită celulă cu o lungime fixă de 53 de octeți , având o structura precizată de 5 octeți ca antet, folosit pentru îndrumarea celulei , și restul de 48 de octeți care conțin sarcina utilă. În nodurile ATM îndrumarea se face în consecință la nivel de celulă într-un interval de timp prestabilit , numit time slot , sau doar slot , adică se execută o comutare de celule.

Există câteva implementări de switch-uri IQ, fie prototip ,fie comercial. Probabil cel mai faimos comutator prototip de celule IQ este Tiny Tera, implementat la Universitatea Stanford în cooperare cu Texas Instruments .Cea mai recentă versiune de Tiny Tera poate ajunge la o lățime de bandă totală de 1 Tbps.

O arhitectură similară este pusă în aplicare în recenta linie de Routere Cisco Gigabit, seria Cisco 12000, care adoptă o rețea de comutatoare IQ de bază , care ajunge la o lățime de bandă totală egal cu 60 Gbps. Alte exemple de rețele comerciale de comutare IQ sunt switch-urile Lucent Cajun și switch-ul Yago PowerCast.

Un comutator este în principiu alcătuit din interfețele de intrare, rețeaua de comutare , sau switching fabric, și interfețele de ieșire.

Rețeaua de comutare, este o topologie în care nodurile de rețea se conectează unele cu altele prin intermediul uneia sau mai multor rețele de comutare.

Un comutator cu șiruri pe intrare este arătat în figura următoare :

Figura 1 . Comutator cu șiruri pe intrare

Comutatoarele cu șiruri pe intrare (IQ) au fost studiate în amănunt abia recent. Principala problemă în switch-urile cu șiruri pe intrare se referă la programarea acestora.

Decizia programării devine relativ ușoară pentru celule comparativ cu lungimea variabilă a pachetelor deoarece programarea trebuie să se facă la un interval fix de celule în timp. În traficul real trebuie realizată împărțirea pachetelor variabile în celule, la partea de intrare a comutatorului și apoi re-asamblarea acestor celulele în pachete pe partea de ieșire a acestora. Dezavantajele acestei abordări a comutatoarelor de celule sunt următoarele: (a) lățimea de bandă este pierdută în timp ce divizarea unui pachet poate genera celule incomplete, și (b) probleme legate de segmentări suplimentare și reasamblarea celulelor în pachete.

Două criterii importante de proiectare pentru arhitecturi de comutare sunt: (a) capacitatea de producție a sistemului, și (b) întârzierea medie. Printre diferite arhitecturi de comutatoare cu șiruri pe intrare (IQ) arhitectura comutatoarelor a fost foarte atractivă din cauza cerințelor sale scăzute de lățime de bandă de memorie în comparație cu alte arhitecturi cunoscute. Constrângerile crossbar ale unui comutator IQ necesită programarea pachetelor pentru a fi transferate între intrări și ieșiri. Transferul și întârzierea în comutatoarele IQ sunt puternic dependente de această decizie de planificare. În trecut au existat

o mulțime de cercetări efectuate pentru a proiecta algoritmi buni de planificare pentru switch-uri IQ. În aceste studii există o presupunere implicită că switch-ul funcționează cu celule de dimensiuni fixe. În alte cuvinte, se presupune că ori de câte ori sosește un pachet în sistem, acesta este împărțit în celule de dimensiuni egale, și după ce se face comutarea, celulele sunt reasamblate în forma pachetului inițial înainte de a părăsi sistemul.

Natural există o oarecare similitudine între programarea bazată pe pachete și cea bazată pe celule. Pentru programarea comutatoarelor pe bază de celule este cunoscut faptul că algoritmul MWM este stabil pentru orice tip de trafic admisibil.

Cuplajul de pondere maximă MWM (Maximum Weight Matching) realizează maximizarea ponderii totală a legăturilor efectuate într-un graf bipartit. Un exemplu de aplicare a cuplajului MWM este următorul :

Cereri Conexiuni MWM

Figura 2 . Cuplaj MWM

În arhitectura comutatoarelor de pachete cu șiruri la ieșire (OQ) , pachetele care sosesc de la liniile de intrare nu sunt așezare în coada de așteptare la interfeța de intrare; mai degrabă, ele trec de rețeaua de comutare, și se alătură unei cozi aflate pe interfața de ieșire a switch-ului înainte de a fi transmise la următorul nod (a se vedea figura 3.a.). Pentru a evita coliziunea în cadrul rețelei de comutare sau în accesul la coada de ieșire, este necesar ca viteza internă a unui comutator OQ, precum și rata de acces a memoriei la fiecare interfață de ieșire, să fie egală cu suma tuturor ratelor de la liniile de intrare (de exemplu, ele trebuie să fie egală cu lățimea de bandă agregată a comutatorului ).

Dimpotrivă, în arhitectura comutatoarelor cu șiruri pe intrare (IQ) , pachetele care sosesc din liniile de intrare intră în coada de așteptare la interfața de intrare . Ele sunt apoi extrase din cozile de intrare pentru a traversa rețeaua de comutare și a fi transmite la nodul următor, conform unui algoritm care evită coliziunea atât în cadrul rețelei de comutare cât și la interfețele de intrare și de ieșire (nu mai mult de un pachet poate fi extras la un moment dat din fiecare intrare și poate ajunge la o ieșire). Rețineți că punerea în aplicare a acestui algoritm necesită coordonare între interfețe de intrare, prin urmare schimb de informații de control, care poate lupta fie cu datele utilizatorului pentru a avea acces la materialul de comutare, fie pentru a folosi o cale separată de date.

Viteza internă a unui comutator IQ nu trebuie să fie mai mare decât cea mai mare rată pe linie (vezi fig. 3.b), incrementate posibil pentru a justifica header-ele în plus ale pachetelor adăugate pe plan intern în switch.

Din această descriere preliminară a abordărilor comutatoarelor IQ și OQ, este imediat evident că programarea inteligentă a pachetelor în comutatoarele cu șiruri pe intrare compensează pentru lipsa vitezei pe plan intern în comutatoarele cu șiruri pe ieșire.

Dacă sunt utilizate cozile de pachete FIFO (primul sosit este primul ieșit), arhitecturile comutatoarelor IQ suferă de fenomenul de blocare la cap de linie (HoL), care limitează în mod sever performanța acestora.

S-a dovedit printr-o analiză asimptotică că în cazul existenței unui trafic uniform între sursă și destinație , blocarea HoL limitează capacitatea maximă a switch-urilor IQ cu un număr mare de linii de intrare / ieșire alese în mod arbitrar la 2 = 0.586. Acest rezultat este destul de dezamăgitor, mai ales având în vedere că, fără orice fel de coliziune în comutator (cu excepția evidentă a necesității de a stoca un pachet de la comutatorul de intrare și ieșire), de exemplu, prin respingerea pachetelor care nu pot fi comutate imediat, limita crește la 0,632 . Fenomenul de blocare HoL poate fi evitat cu structuri mai complexe la cozile de intrare, de exemplu, separarea (fie la nivel logic sau fizic) la fiecare intrare cozile de pachete care sunt adresate la diferite ieșiri (vezi Fig. 3.c).

O serie de algoritmi noi pentru arhitecturi de comutatoare IQ au apărut recent în literatura de specialitate, cu scopul de a elimina blocarea HoL, cu minim de complexitate.

Figura 3

Capitol 1.1 Arhitecturile comutatoarelor cu șiruri pe intrare

Considerăm arhitecturile comutatoarelor IQ cu operațiuni sincrone, unde avem slot de timp, și în cazul în care unitățile de date de dimensiuni fixe sunt transferate în fiecare slot de la interfețe de intrare catre interfețele de ieșire.

Împrumutând din jargonul ATM, celula termenul va fi folosit pentru a ne referi la unitățile de date, dar contextul în care ne considerăm nu este restricționat pentru ATM. Avem in atentia noastră retelele de comutatie fara memorie , și la un control al conflictelor în accesarea retelei de comutare realizata in întregime de algoritmul de planificare.

Pentru funcționarea arhitecturii comutatoarelor IQ , celule de intrare trebuie să fie stocate în memoria disponibilă la interfețele de intrare; situația de interfețe de intrare trebuie apoi comunicată unui controler al switchului care execută un algoritm de planificare pentru a decide care celulele trebuie să fie transferate de la intrări la ieșiri.

Astfel, elemente cheie ale arhitecturii comutatoarelor de celule cu siruri pe intrare (IQ) sunt

1. organizarea cozii de intrare

2.Algoritmul de planificare

3.sistemul de control al comutatorului

A. Organizarea cozii de intrare

Organizarea cozii de intrare este crucială pentru a depăși fenomenul de blocare HoL : cu o singură coadă FIFO , la fiecare intrare , se poate întâmpla ca nici un pachet sa nu poata fi transmis de la o intrare din cauza primului pachet din FIFO , chiar și atunci când alte pachete care ar putea fi transmise fără probleme se afla în spatele aceleiasi cozi .

O organizare frecventa a cozii este obtinuta direct din observarea faptului ca blocarea HoL se realizeaza din cauza imposibilitatii de a extrage dintr-o coada FIFO un pachet care nu este primul la rand in coada. Cu n coadă n – ferestre de asteptare , de asemenea, numite si asteptare bypass , în cazul în care pachetul de la inceputul cozii nu poate fi transferat la ieșirea careia este destinat din cauza controversei careia e supus ,al doilea pachet este luat in considerare , până la poziția n a cozii .

Performanța comutatoarelor cu siruri pe intrare care adopta aceasta organizare a cozilor creste odata cu n ; o analiză aproximativă arată faptul că o vizibilitate completă asupra cozilor de intrare este necesara pentru a se atinge debitul optim al comutatorului . Din acest motiv, unele propuneri recente de arhitectura a comutatoarelor de celule cu siruri pe intrare IQ adopta o organizare a cozii cu separarea completă a celulelor la fiecare intrare îndreptate spre iesiri diferite . Această organizare a cozii poarta numele de siruri virtuale pe iesire, VOQ. Arhitecturile comutatoarelor cu siruri pe intrare IQ cu N linii de intrari/ iesiri si siruri virtuale de iesire presupun N cozi la fiecare intrare, deci in total numar de cozi , fiecare sticand celulele care merg de la o intrare catre o iesire ( vezi Fig . 1.c ) .

B. Algoritmul de planificare

Termenul de algoritm de planificare în arhitecturile comutatoarelor IQ de celule ne putem referi la două tipuri diferite de programari :

1 . programarea comutare de matrice , care decide care interfața de intrare este activată pentru a transmite printre cei care au nevoie pentru a transfera celule pentru o interfață de ieșire specifica , si astfel se evită blocarea și rezolva dispută în reteaua de comutare ;

2 . programare pentru nivelul fluxului , care decide care fluxuri de celule trebuie să fie servit in conformitate cu cerințele Quality of Service ( QoS ) . De fapt ,utilizarea tradițională a algoritmului de planificare in comutatoarele cu siruri pe iesire se referă la programarea in functie de nivelul fluxului , cum ar fi versiuni diferite ale algoritmilor de așteptare corecte , în timp ce în comutatoarele cu siruri pe intrare se refera la programarea comutarii de matrici, avand in vedere ca cercetarea despre programarea in functie de nivelul fluxului a inceput abia recent.

În literatura de specialitate algoritmii de programare in comutatoarele cu celule cu siruri pe intrare sunt descris ca fiind solutii ale problemei de conexiune in graful bipartit.

Exemple de graf bipartit si cuplaje asociate :

Cereri Cuplajul 1 Cuplajul 2 Cuplajul 3

Un algoritm de programare trebuie sa raspunda la urmatoarele cerinte :

Eficienta – Adica sa conduca la obtinerea unei productivitati ridicate si a unei intarzieri mici , acestea trecandu-se de fapt printr-un numar cat mai mare de celule transferate in fiecare slot ;

Echitate intre noduri (fairness)- pentru a impiedica infometarea (starvation) oricarui VOQ;

Stabilitate – ocuparea medie a fiecarui VOQ trebuie sa ramana finita pentru orice moedel de trafic ;

Complexitate redusa de implementare – pentru a evita timpi mari de programare , care la randul lor conduc la limitarea vitezei de operare a structurii de comutatie.

C. Schema de control a comutatorului

Cu termenul de sistemul de control al comutatorului ne referim la: a) structura controlerului care execută programarea algoritmului ; b) informația de control folosita în executarea algoritmului de programare; c) calea de date și protocolul utilizat pentru schimbul informatiilor de comandă.

Algoritmul de programare poate fi executat fie printr-un controler centralizat , sau executate într-o manieră distribuită peste interfetele liniilor de intrare. Când controlerul este centralizat, este necesar

sa se transfere de la interfețele de intrare la controler centralizat informația starilor pe care operatorul le utilizează pentru executarea algoritmului de programare. Rezultatul programarii trebuie sa fie apoi

returnat la interfețe de intrare.

Când controlerul este în schimb distribuit peste interfețele liniei,

este necesar să se transfere de la fiecare interfață catre toți ceilalți informația care este necesara pentru executarea algoritmului de programare la fiecare interfață. Informația si /sau calculul

cerute de fiecare controler distribuit poate fi mai mică decât informația și / sau calculul cerută de controlerul centralizat.

Algoritmii de planificare pot fi intrinsec centralizati sau distribuiti, în sensul că ele au fost concepute inițial fie pentru o centralizate fie pentru o punere în aplicare distribuite.

Cu toate acestea, un algoritm de planificare intrinsec centralizat poate fi implementat pe un controler distribuit prin lasarea fiecarei interfete de linie sa opereze pe o informatie a controlerului centralizat, prin urmare, se executa în paralel, la fiecare interfață algoritmul centralizat asupra aceleiasi date. În acest caz nu este nevoie sa se distribuie rezultatul despre programare (dar puterea generala de calcul necesară sistemului este crescut cu un factor N în cel mai rău caz). În schimb, algoritmul de planificare intrinsec distribuit poate fi implementat într-un controler centralizat numai cu o creștere în complexitate cu privire la fiecare execuție distribuita.

Cantitatea de informatie care este transmisa la controlerul centralizat , in cazul in care avem un comutator cu N interfete de linie cu viteze egale, independente fata de algoritmul de programare , este N[] biti , avand in vedere ca fiecare interfata de linie trebuie sa indice daca o noua celula a sosit si catre ce iesire este intentionata. Dupa ce algoritmul de programare de la controlerul centralizat a ales un cuplaj maxim, cuplajul trebuie sa fie transferat inapoi catre interfetele de intrare activate.

Acest lucru presupune transportul a N[] biti din nou.

Informatia de control se poate certa cu datele utilizatorului pentru reteaua de comutare sau poate folosi o cale de date dedicata. Mai mult decat atat , transferul informatiei de control poate exploata o facilitate de broadcast nativ, sau poate cere transferul a mai multe copii. Diferitele alternative poate produce performante diferite ale arhitecturii cu siruri pe intrare. Vom presupune ca cale de date dedicata este disponibila, cu aptitudine de broadcast.

Comutatoarele cu siruri pe intrare cu cozi virtuale de iesire (VOQ) sunt in ultimul timp adoptate ca fiind arhitecturile pentru ruterele si switchurile de mare viteza , avand in vedere ca toate componentele unui comutator cu siruri pe intrare (interfete la intrare, reteaua comutatorului, si interfetele de iesire) funcționează la o viteză care nu este cu mult mai mare decât rata de date de intrare și linii de ieșire. Cele mai multe dintre comutatoarele de maare viteza cu siruri pe intrare operează pe plan intern pe unități de date de dimensiuni fixe (celule): GRF Lucent, Cisco GSR , Tiny-Tera , AN2/DEC, iPoint , și MGR / BBN .

O problemă majoră în proiectarea de switch-uri IQ este că accesul la reteaua de comutare trebuie să fie controlată intr-o anumita maniera de un algoritm de programare (SA) pentru a evita divergentele la porturile de iesire. Câtiva SA au fost propuse si comparate pentru comutatoarele cu siruri pe intrare in literatura. Le numim pe acestea algoritmi de programare cell-mode (CM-SA). CM-SA ‚urile bune pentru comutattoarele cu siruri pe intrare (IQ ) furnizeaza o performanta apropiata arhitecturilor switchurilor cu siruri pe iesire (OQ)

Capitolul 2. Performantele comutatoarelor cu siruri pe intrare

Performanta comutatoarelor cu siruri pe intrare este afectata printre altele si de HoL blocking.

blocarea la cap de linie sau HOL blocking în rețele de calculatoare este un fenomen ce limiteaza performanta , si care apare atunci când o linie de pachete este retinut de primul pachet , de exemplu, la comutatoarele cu siruri pe intrare , o livrare „defecta” , și mai multe cereri în HTTP pipelining .

Acesta este un exemplu de HoL blocking :celulele de pe primul si al treilea port de intrare sunt concurente pentru a trimite pachete la aceeași interfață de ieșire . În acest caz , dacă reteaua de comutare decide să transfere pachete din fluxul de intrare 3,fluxul de pe prima intrare nu poate fi prelucrat în același ciclu de ceas . Reținem faptul că fluxul de pe prima intrare a blocat un pachet destinat catre interfața de ieșire 3 , care este disponibil pentru prelucrare .

Un comutator poate fi compus din porturile de intrare , o retea de comutare și porturi de ieșire . În cazul în care este utilizat FIFO la porturile de intrare , doar cel mai vechi pachet este disponibil pentru expediere . Sosirile cele mai recente nu pot fi transmise daca cel mai vechi pachet nu a putut fi transmis , deoarece portul de iesire caruia ii era adresat era ocupat . Portul de ieșire poate fi ocupat în cazul în care :

Exista un conflict la portul de iesire ( vezi schema )

Sau cel mai frecvent atunci când portul de iesire este in plină – congestie ( de exemplu, rata combinata a mai multor intrări depășește rata de ieșire )

Fără blocarea HOL , noile celule sosite ar putea fi transmise pe langa pachetul blocat, catre destinatiilee destinațiile respective . Fenomenul poate avea efecte de grave de degradare a performanței ,în sistemele cu siruri pe intrare .

Efectul asupra performanței comutatorului

Acest fenomen limitează capacitatea de transfer a comutatoarelor. Pentru comutatoarele cu siruri pe intrare care folosesc FIFO , un model simplu de celule cu dimensiuni fixe către destinații distribuite uniform , determină debitul de transfer să fie limitat la 58,6 % din total, pe parcurs ce numarul linkurilor creste .

HOL poate crește în mod semnificativ reordonarea pachetelor.

Depășirea blocarii HOL.

O modalitate de a depăși această limitare este prin utilizarea cozilor virtuale pe iesire . Doar la switch-urile cu siruri la intrare se intalneste blocarea HoL . Cu o lățime de bandă internă suficientă , sirurile pe intrare sunt inutile; toate aceste siruri manevrate la iesiri si blocarea HOL este evitata. Singurul invconvenient este ca arhitectura de comutatoare fara siruri la intrare este intalnita doar la switchurile Ethernet de marimi mici si mijlocii.

Capitol 3 – Modelare matematica pentru calcularea intarzierii si lungimii cozilor

Multe rutere de înaltă performanță ( de exemplu , CISCO 12000 ,Lucent Cajun , sau Nortel Versalar TSR45000 ) sunt construite în jurul retelelor de comutatoare rapide cu siruri pe intrare : datagramele IP de intrare sunt segmentate în unitati de date cu dimensiune fixa , de obicei, numite celule , și sunt transferate la porturile de ieșire , unde datagramele IP sunt reasamblate. Proiectarea acestor routere de înaltă performanță , în general, nu adoptă arhitectura clasica cu siruri pe iesire ( OQ ), (unde celulele sunt stocate la iesirea din reteaua de comutare ) , preferând sa fie ori cu siruri la intrare (IQ), ori structurile combinate cu siruri intrare/iesire ( CIOQ ) . Motivul este faptul că , în OQ , atât reteaua de comutare cat si coada de iesire trebuie să funcționeze la o viteză egală cu suma ratelor tuturor liniilor de intrare ; deoarece aceasta viteza crește liniar cu numărul porturilor comutatorului , abordarea prin OQ este impractica pentru switch-uri mari si rapide . În schimb , în schemele de IQ , toate componentele comutatorului ( interfețe de intrare , reteaua de comutare , interfețe de ieșire ) pot funcționa la o rată de date care este compatibilă cu rata de date de la liniile de intrare și de ieșire și care nu cresc cu dimensiunea comutatorului . O problema uzuala a performantei dupa cum am mentionat si in capitolul referitor la performanta comutatoarelor cu siruri pe intrare este blocarea HOL, dar care poate fi redusa prin scheme cu cozi virtuale de iesire (VOQ) care organizeaza liniile de intrare in seturi de cozi in care celulele care asteapta sa aiba acces la reteaua de comutare sunt stocate in functie de destinatia pentru care sunt intentionate.

O problemă majoră în proiectarea switch-urilor cu siruri pe intrare IQ este că accesul catre reteaua de comutare trebuie să fie controlată de un algoritm de planificare , care funcționează pe cunoașterea stării cozilor de intrare .

Problema cu care se confruntă algoritmul de planificare poate fi formalizată ca o dimensiune maximă sau pondere de cuplaj maxim pe graf bipartit în care nodurile reprezintă porturile de intrare și ieșire, și marginile reprezintă celulele ce urmeaza să fie transmise. Soluția optimă la această problemă este cunoscuta a fi obținute prin algoritmul de pondere de cuplaj maxim (MWM) , dar au existat mai multi algoritmi de planificare cu complexitate mai redusa pentru switch-uri de celule IQ.

MWM s-a dovedit a sustine aceeasi capacitate de transfer la comutatoarele OQ .

Pentru a simplifica proiectarea și implementarea algoritmilor de planificare, de multe ori switch-urile funcționează cu o crestere de viteză, de exemplu, reteaua interna de comutare, precum și memoriile de la intrare și ieșire, funcționeaza la o viteză mai mare în ceea ce privește rata de date de la liniile de intrare / ieșire. În acest caz, tamponarea este necesara atat la ieșiri precum si la intrări, și este folosit termenul de "coi combinate de intrare / ieșire" (CIOQ) este folosit. Evident, atunci când viteza ajunge la punctul in care latimea de banda interna a comutatorului este egala cu suma ratelor de date de la liniile de intrare , bufferele de intrare devin inutile.

Lucrări anterioare au demonstrat că o clasa varianta de algoritmi de programare de dimensiuni maxime mai simple oferă aceeași performanță tranzitată de OQ atunci când o accelerare a celulelor este egala cu 2 este disponibil în comutator .

Aceste rezultate referitoare la transferul din comutatoarele de IQ și CIOQ oferă un background teoretic solid, care este foarte util pentru designerii de switch-uri si routere de mare viteză și care vor

fi un ingredient major al viitoarelor infrastructuri de telecomunicații.

Cu toate acestea, transferul este doar unul dintre parametrii-cheie de performanță utilizați în proiectare și planificare a comunicării rețelelor; o alta problema majora in ceea ce priveste performanta este intarzierea.

Pentru o clasă largă de servicii de telecomunicații, în special cele cu cerințe in timp real, întârzierea este chiar mai importanta decât tranzitia in sine. Prin urmare, extinderea analizei teoretice a intarzierii comutatoarelor de celule cu siruri pe intrare IQ este extrem de important. Calcularea intârzierii de celule în switch-urile IQ nu este ușor si nici un rezultat analitic nu este încă disponibil pentru întârzierile cu care se confruntă comutatoarele IQ de celule.

În această lucrare vom considera algoritmii de planificare MWM, concentrându-ne pe cazul cu trafic uniform, și aflam limitele analitice privind întârzierile medii, și limitele pentru lungimea medie a cozii in comutatoarele cu siruri pe intrare. După introducerea unor definitii si rezultate preliminare, în subcapitolul 3.1 vom arata principalele rezultate ale metodologiei de analiză, pe care o vom aplica apoi la obtinerea de limite privind întârzierile medii și dimensiunile cozii la switch-uri IQ in secțiunea 3.2.

Disponibilitatea unor limite strânse privind întârzierile și dimensiunile cozilor este destul de importanta pentru designerii de comutatoare și routere: ele permit cuantificarea stocarii bufferelor necesar pentru furnizarea de garanții QoS, atât în ​​ceea ce priveste probabilitatea de pierdere si întârziere medie .

Faptul că limitele noastre sunt exprimate într-o formă închisa, le face extrem de ușor de a le calcula și de a le aplica problemelor de proiectare realiste.

3.1 METODOLOGIA ANALIZEI

Având în vedere un sistem de N cozi discrete in timp de capacitati infinite, consideram a fi vectorul pentru lungimea cozilor la momentul n; adica avem, , unde este numărul de celule în coada i la momentul de timp n.

Evoluția lungimii cozii este descrisa de expresia , unde reprezintă numarul celulelor ajunse la coada i în intervalul de timp (n,n+1] , și reprezintă numărul de celule ce au ieșit din coada i în intervalul de timp (n,n+1].

Considerăm ca fiind vectorul numărului de intrări la diferite cozi, si

ca fiind vectorul numărului de ieșiri din cozi.

Cu această notație, evoluția sistemului de cozi poate fi descrisă ca

(1)

Presupunem că vectorii sunt independenți și identic distribuiți. Cu toate acestea, corelația între diferite componente ale vectorului de sosire este permisa.

Indicăm cu ||Y || norma vectorului Y = () . Trei norme diferite vor fi introduse mai tarziu in Definitiile 3,4 si 5.

Definitie 1: Un sistem de cozi este declarat a fi instabil dacă, pentru fiecare e > 0, există B> 0 astfel încât

(unde P{Z} este probabilitatea evenimentului Z).

Definitie 2: Un sistem de cozi este declarat a fi puternic stabil dacă

(unde E[X] este media variabilei aleatoare X).

Presupunem că procesul ce descrie evoluția sistemului de cozi este un Lant Markov Timp Discret ireductibil (DTMC), al cărui vector de stare la momentul n este , ∈ , , și M = N+N’ . este combinația vectorului si un vector cu N’ parametrii intregi.

In această lucrare denotă mulțimea întregilor non negativi.

Consideram H ca fiind spatiul starilor al DTMC, obținut ca un subset din produsul cartezian al spatiului starilor al , si spatiul starilor al .

Dacă toate stările sunt recurente pozitive, sistemul de cozi este instabil; cu toate acestea, reciproca nu este adevarata în general, deoarece lungimile de coadă pot rămâne finite, chiar dacă starile din DTMC nu sunt recurente pozitive datorită instabilității în secvența vectorilor de parametri {}.

Cele mai multe sisteme de cozi discrete in timp de interes practic pot fi descrise cu modele care se încadrează în clasa DTMC . Următorul criteriu general de stabilitate (slab) din sistemele care se incadreaza în această categorie este util.

Teorema 1: Fiind dat un sistem de cozi a căror evoluție este descrisă de un DTMC cu vectorul de stare ∈ , dacă o funcție mărginită inferior V() , numită funcție Lyapunov,

V:  ℝ , poate fi găsita astfel încât

E ∀

și există e ∈ și B ∈ astfel încât

E[ ] < e ∀ > B (2)

apoi toate starile din DTMC sunt recurent pozitive, iar sistemul de cozi este slab stabil.

ℝ reprezintă setul de numere reale, și reprezintă un set de numere non real negative.

Demonstratie : Această teoremă este o extensie directă a criteriului lui Foster.

Dacă starea spațiul H al DTMC este un subset al produsului cartezian al spațiului starilor numarabil și un spatiu al starilor finit , criteriul de stabilitate poate fi ușor modificat, deoarece stabilitatea sistemului poate fi dedusă numai din lungimea cozii vectorului de stare .

Corolarul 1 : Având în vedere un sistem de cozi a căror evoluție este descrisa de un DTMC cu vectorul de stare : , și al cărui spatiu starilor H este un subset al produsului cartezian al unui spatiu al starilor numarabil și o stare de spațiu finită , în cazul în care o funcție mărginită V (), denumit functie Lyapunov, V:  ℝ, pot fi găsite astfel încât

E[ ] < ∀

și există e ∈ și B ∈ astfel încât

E[ ] < e ∀ > B

apoi toate starile din DTMC sunt recurent pozitive.

În acest caz, sistemul este instabil daca si numai daca toate starile din DTMC sunt recurent pozitive.

In cadrul lucrarii ne limitam analiza la clasa sistemelor de cozi pentru care se aplica Corolarul I.

Vom presupune, de asemenea, un DTMC aperiodic avand in vedere procesele de sosire confirma in mod normal această ipoteză, prin urmare, având stari recurent pozitive este echivalent cu a avea ergodicitate de DTMC. Generalizarea DTMC-urilor periodice este simplă.

Teorema 2 : Dat fiind un sistem de cozi a cărui evoluție este descrisă de un DTMC cu vectorul de stare ∈ , și a carui spatiu starilor H este un subset al produsului cartezian al unui spatiu al starilor numarabil și un spațiu al starilor finit , în cazul în care o functie mărginita inferior V (), numit funcție Lyapunov, V:  ℝ, poate fi găsit astfel încât

E[ ] < ∀

și există e ∈ și B ∈ astfel încât

E[ ] < e|||| ∀ > B (3)

atunci sistemul de cozi este puternic stabil.

Demonstatie : Deoarece ipotezele Teoremei 1 sunt îndeplinite, fiecare stare a DTMC este recurent pozitiva. In plus, pentru a dovedi că sistemul este puternic stabil, vom arăta că

Consideram a fi un set de valori luate de pentru care || || B (în cazul în care (3) nu se aplică). Este ușor de demonstrat că este un set compact. În afara acestui set compact, ecuația (3) sustine, de exemplu

E[ ] < e||||

Având în vedere toate care nu fac parte din , luând media expresiei anterioare, avem:

E[ ] < eE[|||| |

In schimb, pentru , fiind un set compact :

E[ ≤ M < ∞

Unde M este maximul luat de E[ pentru .

Combinand ultimele doua expresii , obtinem:

E[ = E[ + E[ <

<MP{} + { E[ eE [ || | ]} <

<M + E[] eE [ ||] +

Unde este o constanta astfel incat

> {[ | ] + eE [ || | ]}

este finit, avand in vedere ca este un set compact.

Prin însumarea peste toate n de la 0 la , obținem:

E[V( ) ] < + E[V( ) ] e

Deci , pentru orice , putem scrie

= < M + [

E[ este delimitata inferior prin definitie ; presupunem E[ > . Atunci

= < M + [ +

Pentru , E[ si finite , putem scrie

= < M + (4)

Atunci este marginita.

Întrucât din DTMC are starile recurent pozitive, există . În plus, este ușor de a arăta că, în cazul în care secvența E[||||] este convergenta, secvența converge la aceeasi limita :

=

Dar partea dreapta s-a vazut ca e marginita, atunci

< ∞

Relatia (4) ofera o prima granita a comportamentului limitei al :

≤ (M + ) (5)

Din păcate, aceasta limita este de multe ori foarte slaba; astfel, vom a obține o limita mai strânsă prin selectarea unei clase speciale de functii Lyapunov.

Mai întâi să ne concentram asupra funcțiilor Lyapunov în forme pătratice.

Corolar 2: Dat fiind, la fel ca în Teorema 2, un sistem de cozi a căror evoluție este descrisă de un DTMC cu vector de stare ϵ , și al căror spatiu al starilor H este un subset al produsului cartezian

Al unui spatiu al starilor numarabil și un spațiu al starilor finit , în cazul în care există o matrice simetrica copositiva Z ,definind funcția V () = Z , astfel încât

E[ < ∞ ∀

și există două numere reale pozitive e ∈ si B ∈ , astfel încât

E[ < || || ∀ > B (6)

atunci sistemul de cozi este puternic stabil. În plus, toate momente polinomiale ale distribuției lungimii cozilor sunt finite.

Demonstratie: Deoarece DTMC ce descrie evoluția unui sistem de cozi stabil are stari recurente pozitive, dacă presupunem aperiodicitate ca mai sus, DTMC este ergodic; deci = . Sub ipotezele din Corolarul 2, ca urmare a faptului că momentele de sunt finite, se poate afirma în continuare ca:

E[ (7)

Demonstratia teoremei 2 arată că < ∞ . Dacă înlocuim în (3) –e cu –eƒ (), undeƒ (∙) este o funcție continuă definită pe , urmand etapele demonstratiei Teoremei 2, este posibil să se arate că < ∞. Prin urmare, putem afirma următoarea teorema.

Teorema 3 : Dat fiind, la fel ca în Teorema 2, un sistem de cozi a cărui evoluție este descrisă de un DTMC cu vectorul de stare ∈ , și a carui spatiu al starilor H este un subset al produsului cartezian al unui spatiu al starilor numarabil și un spațiu al starilor finit , în cazul în care o functie mărginita inferior V (), V:  ℝ, poate fi găsit astfel încât

E[ < ∞ ∀

și există două numere reale pozitive e ∈ si B ∈ , astfel încât

E[ ∀ > B

ƒ (x) fiind o functie continua in , atunci

< ∞

Acum este posibil să precizeze următoarea teoremă important care oferă o mai puternică și mai generală decât legat (5).

Teorema 4: : Dat fiind, un sistem de cozi a cărui evoluție este descrisă de un DTMC cu vectorul de stare ∈ , și a carui spatiu al starilor H este un subset al produsului cartezian al unui spatiu de stare numarabil și un spațiu de stare finit , si pentru care momentele polinomiale aledistributiei lungimii cozii sunt finite, în cazul în care o functie mărginita inferior V (), V:  ℝ, poate fi găsit astfel încât

E[ < ∞ ∀

Si exista doua numerele real positive e ∈ si B ∈ , asa incat

E[ ∀ > B (8)

si ƒ(x) fiind o functie continua in , atunci

≤ P {} (9)

Demonstratie: Datorită ergodicitatii lui DTMC ce descrie evoluția sistemului de cozi, pentru faptul că

momentele polinomiale ale lungimii cozii sunt finite, pentru a faptul că este o functie polinomiala , se poate afirma, în mod similar la (7), faptul ca:

E[ = 0 (10)

Urmand pașii de la demonstratia teoremei 2, și utilizand (10):

E[ =

= E[ P { + E[ P { ≤

≤ E[ P {

P {=

= E[ P {

P { +

P { +

+ P { =

=[ P { + + P {

(11)

Combinând (10) și (11), teorema este demonstrată.

Acest rezultat va fi folosit în următoarele secțiuni, în care formele polinomiale pentru si pentru vor fi utilizate pentru a obține limite pentru întârzierile medii, precum și pentru dimensiunile medii ale cozii in comutatoarele cu siruri pe intrare.

3.2 LIMITE CU PRIVIRE LA INTARZIEREA MEDIE SI DIMENSIUNEA COZII

Considerăm comutatoare cu siruri pe intrare cu P porturi intrare și P porturi de ieșire, toate cu aceeasi rata de celule (și le numim P x P IQS). Reteaua de comutare se presupune a fi nonblocking și fara memorie , adică, celulele sunt stocate numai la intrarea in switch. La fiecare intrare, celulele sunt stocate în conformitate cu politica Cozii virtuale de iesire (VOQ): o coadă separată este menținută pentru fiecare ieșire. Astfel, numărul total de cozi în comutator este N = .

În scopul de a simplifica formulele noastre, în restul acestei lucrări vom adopta o notație cu un vector, mai degrabă decât o notație cu matrice pentru a indica cozile de intrare: consideram , k= Pi+j a fi coada de la intrarea i care stocheaza celulele îndreptate spre ieșirea j, cu i, j = 0, 1,2,. . . . P – 1.

Înainte de a continua, trebuie să definim trei funcții de normă.

Amintiti-va ca norma vectorului Z ∈ este o funcție astfel încât:

||Z|| ≥0 si ||Z||=0 daca Z =0 ,

||αZ|| = |α| ||Z|| pentru orice scalar ,

|||| ≤ |||| + ||||.

Definitia 3 : Fiind dat un vector Z ∈ , Z = {} , norma este definita ca:

= (12)

Definitia 4 : Dat fiind un vector Z ∈ , norma este definita ca:

= (13)

Definitia 5 : Dat fiind un vector Z ∈ , norma este definita ca:

= (14)

Vectorul normalizat paralel cu vectorul Z este notat cu Ẑ, și este definit ca:

Ẑ =

Consideram R ∈ , R= { , k= Pi+j ,i,j= 0,1,…,P-1} = E[A] ca este vectorul ratei de sosire medie a celulelor la cozile în celule / slot.

Definitie 6: Modelul de trafic care încarca un IQS este admisa

= < 1

În cuvinte simple, un model de trafic este admis în cazul în care media totală a ratele de sosire în celule / slot este mai puțin de 1 pentru toate de porturile intrare și ieșire.

La fiecare interval de timp, programul comutatorului selectează celulele ce urmeaza să fie transferate de la cozile de intrare la cozile de ieșire. Setul de celule ce urmeaza sa fie transferate de-a lungul unui interval de timp trebuie să îndeplinească două reguli: 1) Cel mult o celulă poate fi extrasa din structura VOQ de la fiecare intrare, și 2) cel mult o celulă poate fi transferat catre o anumita ieșire.

Definitia 7 : La fiecare interval de timp, programul unui IQS selectează pentru transferul de la cozile un set de celule notat cu vectorul D ϵ , D = { , k= Pi+j ,i,j= 0,1,…,P-1} astfel încât:

≤ 1

Consideram D a fi un set de celule non-concurente, sau un vector de comutare.

Selecția unui vector de comutare a fost dovedit a fi echivalentă cu problema de cuplaj dintr-un graf bipartit ponderat, unde nodurile reprezinta porturile de intrare/iesire, arcele reprezintă prezența de celule care urmeaza sa fie transferate, iar ponderea indică măsurătoarea ce urmeaza sa fie folosita de algoritm. Așa cum am amintit deja, solutia optima la această problemă este obținută cu ajutorul algoritmului MWM .

Definitie 8: Un IQS adoptă un planificator MWM , dacă selecția vectorului de comutare la fiecare interval de timp este realizată conform algoritmul MWM.

Luam care reprezintă un vector de pondere la momentul n, și luam sa fie vectorul de comutare la timp n . Vectorul de iesire Dn produs de un planificator MWM este astfel încât:

Pentru fiecare vector astfel încât ≤ 1, iar pentru fiecare vector :

(15)

Din această proprietate, folosind functia Lyapunov = , a fost apoi dovedit că, pentru orice IQS folosind un planificator MWM cu :

E [ (16)

pentru suficient de mare. Această proprietate deține orice norma considerata, atata timp cat N < ∞, fiind comportamentul asimptotic al lui acelasi pentru toate functiile normate.

Ca o consecință, datorită Corolarul 2 cu matricea Z egală cu matricea identitate I, putem afirma urmatoarea teorema:

Teorema 5: În orice model de trafic de intrare admisibil independent si identic distribuit, un IQS folosind un planificator MWM cu ponderi egale la cu lungimea cozilor este puternic stabil, și toate momentele polinomiale ale distributiei lungimii cozii sunt .

Având în vedere acest rezultat, putem aplica relatia (9), pentru a obține o limita pentru intarzierea medie e celulelor in comutator.

Se arata urmatoarele:

Propoziția 1: Pentru orice ∈ :

≥

Demonstratie: Din (15) avem:

asa încât ≤ 1 , ≥

Consideram = II (cu aceasta alegere avem ), unde II este vectorul cu numai 1, II={1,1,…,1}, astfel obtinem:

II = =

Vom introduce acum prezumția de trafic uniformă: toate porturile de intrare / ieșire ale comutatorului sunt la fel încărcate. Această presupunere poate fi eliminata, dar limitele rezultate ar fi, în general, mai slabe. Fie ρ ≤ 1 sarcina medie a fiecărui port de intrare al comutatorului in celule / slot. Având în vedere că, la fiecare fantă o celulă ajunge la fiecare intrare cu probabilitatea ρ, și nicio celula nu ajunge cu probabilitatea 1 – ρ, și că fiecare port de intrare cuprinde P VOQ’uri, vectorul pentru rata medie la sosirea la slot-ul n este de așa natură încât:

E[] = II (17)

E[ = ρP

Din moment ce E[]= E[] =II datorită stabilității sistemului, în mod similar ca la (17), este posibil, în ipoteza existentei unui trafic uniform, să se declare că:

E[ = ρP (18)

este independent de ,

E[ = E[] E[ = = (19)

În scopul de a obține limitele pentru întârzierile medii și dimensiunile cozii, vom folosi relatia(9), cu ƒ() = si V()= . În aceste condiții, trebuie să calculăm termenii din relatia (9). Pentru e , care apare la numitor, vom calcula , valoarea maxima a lui e pentru care ecuația (8) este adevarata . Pentru a calcula , din ecuatia (16) se poate scrie:

≥ e (20)

∀ : > B

Pentru B > 0 . Funcția din partea stanga a inegalitatii (20) admite o limită pentru → ∞ care depinde de direcția lui ∙este egală cu cea mai mică valoare pentru această limită, deoarece orice valoare mai mică decat verifica exuatia (20), pentru valori mari ale lui .

Astfel, reamintind că , poate fi obținută ca:

=

= =

=

Consideram vectorul Se poate demonstra ca pentru orice

δ > 0. Atunci din relatia (15) :

= ≥ 0

Si

≥ (21)

Ca o consecinta , pentru orice δ > 0 :

≥ = 2

In final , cat Propozitia 1 este adevarata, obtinem :

Sau

Acum sa evaluam termenul E[V()V() | ] care apare in (9) :

= E ( )=

= E[2() ] + E[()]

Aplicand (21) si Propozitia 1, obtinem:

+ E[()] ≤

+ E[()]

Ca o consecinta , ecuatia (9) cu ƒ( ) = devine , pentru valori mari ale lui n:

E[ ] ≤ E[ + | P{}=

= E[ + | P{} ≤

≤ E [ | ] P{} ≤ E [ =

=

Fiind 0 < e ≤ =

Astfel considerand (17),(18),(19) si alegand e = pentru a minimiza valoarea limitei, avem:

E[] ≤ (22)

Este posibil sa se repete aceeasi sursa considerand , si avand in vedere ca ≤ P; rezultatul este :

E[] ≤ P (23)

In cazul unui trafic uniform putem folosi rezultatul din ecuatia (22) pentru a obtine o limita pentru dimensiunea medie a cozilor de intrare. Intradevar , din moment ce = ,

E[] = = N , asa incat :

≤ (24)

Limita pentru intarzierea medie a celulelor este apoi obținută prin aplicarea rezultatului Little:

E[T ≤ (25)

Fiind = ρ/P

(Explicare lucrare)

In urma calculului matematic, dupa definirea unor definitii si rezultate preliminarii , in acest capitol vom arata printr-o simulare realizata in programul MatLab, ca limitele analitice demonstrate in capitolul anterior se potrivesc cuu rezultate simularii. Am implementat in simulator pentru comutatorul de celule cu siruri pe intrare si am derulat mai multe simulari cu diferite siruri la intrare.

Reamintind faptul ca limitele pe care le-am studiat anteriro se aplica la o clasa larga de procese de sosire , si in particular avem faptul ca si trebuie sa fie independente si identic distribuite, dar intre si este permisa corelatia , derulam mai multe simulari pt comutatoarele cu siruri pe intrare cu structuri diferite la intrare.

Definim parametru v ca fiind probabilitatea :

v = P{ =1, },

v reprezentand gradul de corelatie intre procesele de sosire la doua VOQ diferite dar care sunt directionate catre aceeasi iesire. Daca procesul de sosire la diferite VQ este independent atunci v va lua valoarea de v= .

In simulari vom seta v ca fiind v ={1, 0.5 ,0.25, 0.125 , } . Iar atunci cand v=1 inseamna ca avem corelatie completa intre procesele de sosire la diferite VOQ si directionate catre aceeasi iesire.

Pentru a implementa cat mai usor si mai corect gradul de corelatie am folosit o matrice patratica de marime PxP asa cum am amintit si in metodologia analitica , deoarece avem p porturi de intrare si P porturi de iesire.

Avand in vedere ca incarcatura procesului de sosire pentru fiecare port de intrare este Bernoulli , avem incarcare medie oferita egala cu ρ.

Asa cum a fost mentionat mai sus avem ρ ≤ 1 sarcina medie a fiecărui port de intrare al comutatorului in celule / slot. Având în vedere că, la fiecare fantă o celulă ajunge la fiecare intrare cu probabilitatea ρ, și nicio celula nu ajunge cu probabilitatea 1 – ρ, și că fiecare port de intrare cuprinde P VOQ’uri, putem scrie urmatoarele ecuatii cu referire la matricea PxP :

ρ)∙ + P ∙ = 1- ρ pentru prima coloana a matricei (26)

si

+ + (P-1 ) = 1 deoarece incarcarea pe o linie este maxim 1. (27)

In cazul nostru este de fapt gradul de corelatie, si atunci pentru simplificarea ecuatiilor va fi inlocuit cu v.

Din prima ecuatie (26) a rezultat =

Dar avand in vedere ca pe fiecare linie avem maxim 1 putem scrie ca:

0 ≤ ≤ 1 (28)

Din ecuatia (27) ne rezulta in urma calculelor ca =

atunci 0 ≤ ≤ 1 (29)

Din ecuatiile (28) si (29) in urma calculelor reulta faptul ca ≤ ≤ 1

Pentru o mai buna acuratete a calculelor am ales valoarea medie pentru aflat in intervalul mentionat mai sus, deci =

Avand ecuatia pentru aflam in (26) valoarea pentru pentru fiecare v ={1, 0.5 ,0.25, 0.125 , }

si apoi in (27) aflam valoarea pentru .

Pentru a usura scrierea in Matlab am inlocuit = x ; = y ; = z si stim ca = v, iar

Deci matricea devine

Si = m; pentru j ∈ [1..P]

Si ecuatiile (26) si (27 ) devin

(1-ρ)∙ + P ∙ = 1- ρ

Si

+ + (P-1 ) z= 1

Cum =

Pentru v = 1 Pentru v = 0.5

= = 1 = =

y = = 0 y = = =

z = = 0 z = =

m = =0 m = = =

Pentru v = 0.25 Pentru v = 0.125

= = = =

y = = = y = = =

z = = z = =

m = = = m = = =

Pentru v =

= =

y = = =

z = =

m = = =

Capitol 4. Programe de calcul si reprezentare grafica

Avand aceste rezultate matricea PxP poate fi completata in MatLab in felul urmator :

Am realizat o functie generateMatrix.m in care prima oara am initializat matricea cu 0 si toate valorile pe care le-am calculat anterior

outMat = zeros(P + 1);

y = 0; z = 0; m=0;x=0;

dupa care verificam v -ul pe care il primesc ca parametru si in functie de valoarea v-ului pe baza formulelor calculate in partea teoretica a lucrarii determin matricea care are forma PxP si in continuare include valorile care trebuiesc calculate si anume x, y, z si m.

Pentru v = am folosit if(abs(v – ro/P) < 0.0000001) pentru a preintampina erorile de calcul la rotunjiri ce apar in Matlab. Apoi se face completarea matricei cu valorile x, y, z, m

outMat(2:n, 1) = y;

outMat(1, 2:n) = m;

outMat(1,1) = x;

for i = 2:n

for j = i + 1:n

outMat(i, j) = z;

outMat(j, i) = z;

end

end

for di = 2:n

outMat(di, di) = v;

end

Urmatoarea functie realizata este getSumMatrix.m adica in functie de matricea generata anterior aflu o matrice suma ce imi va fi de folos pe parcursul simularii.

In codul programului am declarat inMat ca fiind matricea generata completata anterior cu parametrii calculati, si pe baza matricei generate (inMat) determin matricea suma (outMat). O primesc ca parametru si o trimit mai departe ca outMat in afara functiei .

O vom initializa cu valoarea 0, matricea fiind de marimea n x n, pentru a putea aduna in continuare fara erori de calcul outMat = zeros(n)

Prin outMat(:,1) = inMat(:, 1);

se copiaza prima coloana din matricea de intrare care va ramane la fel deoarece nu am nimic anterior ce sa adaug , iar apoi incepand cu a 2-a coloana incep sa adun coloana anterioara la cea in care ma aflu. (prima coloana va fi identica cu cea din matricea generata). Se aduna doar coloana anterioara deoarece ea retine oricum toate celelalte coloane adunate.

for i = 2:n

outMat(:, i) = outMat(:, i – 1) + inMat(:, i);

end

Din punct de vedere al gandirii algoritmului urmatorii pasi au fost: Avand in vedere ca avem PxP , adica pentru fiecare P porturi fizice avem P porturi virtuale reprezentate mai jos

Am considerat celulele aflate pe intrarea Input 1 ca fiind declansate de program in mod aleator. Stim ca sirul de celule de la intrarile urmatoare Input (2.. N ) trebuie sa aiba un grad de corelare intre ele si anume v ={1, 0.5 ,0.25, 0.125 , } . In functie de v declarat initial se vor completa urmatoarele siruri de intrare corelate ajutandu-ne de matricea suma , astfel: ne uitam la prima celula care urmeaza sa intre in reteaua de comutatie, se declanseaza o valoare aleatoare intre 0 si 1 (deoarece in matrice pe linie avem valori intre aceste limite) , mergem pe linia corespunzatoare numarului celulei ce urmeaza a fi transferata si vedem cu cine este corelata. Astfel aflu pentru urmatorul port fizic care este celula corelata cu prima din portul anterior.

Aflarea sirurilor de intrare ale comutatorului a fost realizata prin functia findVirtualPort.m ce nu are o semnificatie de sine statatoare,ci este o functie ajutatoare pentru functia calculateDelay.m .

Rolul functiei findVirtualPort.m este ca intr-un vector , sa determine pozitia unui element, similar cu o functie de cautare intr-un vector.

Sirul de celule dat aleator Input 1 a fost declarat intr-o functie urmatoare pe care o vom trata.

In findVirtualPort.m, row este un rand din matricea suma , randul de care avem nevoie. Aceasta linie va fi determinata in functie de valoarea intrarii de pe sirul portului fizic anterior. Daca avem celula 0 se va duce pe linia 0 din matricea suma, daca avem celula 1 se va duce pe linia 1 din matricea suma samd. In acest rand in matricea corespunzatoare v-ului dat initial , in functie de vectorul alfa generat aleator intre 0 si 1 imi determina pozitia lui alfa pe randul corespunzator.
alfa=rand(1,1);

Functia rand este implementata in Matlab si genereaza valori numai intre 0 si 1.

if alfa<=row(1,1)

port=0;

else

for i=1:n-1

if alfa>row(1,i) && alfa<=row(1,i+1)

port=i;

end

end

end

Urmatorii pasi in implementarea algoritmului au fost intrarea primelor celulelor de pe fiecare port fizic si stabilirea daca mai au loc in coada de asteptare sau nu , deoarece coada are dimensiuni limitate. Celulele intra la diferite unitati de timp pe portul virtual corespunzator , iar in cazul in care la aceeasi unitate de timp 2 celule sunt destinate catre acelasi port de iesire, apare coloziunea, numai o celula iese, celelalte aflate in coliziune cu aceasta fiind intarziate.

Spre exemplu pentru P = 3 :

T=

Avem in tabelul de mai sus pe prima linie, sirul de celule corespunzator primului port fizic, pe a2-a linie sirul de celule corespunzator celui de-al doilea port fizic si pentru a 3-a linie la fel . Pe a 4-a linie in schimb am reprezentat unitatile de timp la care intra fiecare celula .

La unitatea de timp 1 :

– avem porturile 1 si 3 care au ca destinatie acelasi port de iesire deci vor intra in coliziune, iar celula de pe portul fizic 2 , aflata pe portul virtual 2 , nefiind in coliziune cu alta celula va iesi. Dintre celulele destinate catre iesirea 1 vom alege ca de pe primul port fizic sa iasa celula in coliziune, si urmatoarea va fi intarziata, in cazul acesta cea de pe portul fizic 3.

La unitatea de timp 2 :

Celula de pe portul fizic 2 are ca destinatie portul 3 si nu intra in coliziune cu alta celula si atunci aceasta va iesi , iar in portul fizic 3 aveam celula intarziata din unitatea de timp 1 care are ca destinatie 1 si este in coliziune cu celula care a intrat pe acelasi port fizic 3, cu destinatia 1 . In momentul acesta vom aplica algortimul MWM de tipul OCF (Oldest cell first) ce considera ca pondere timpul de asteptare al celulelor HOL din sirurile VOQ. Aflandu-ne la momentul de timp 2 , va pleca celula cu cea mai mare intarziere , adica cea notata cu 1 (unitatea de timp), iar 2 aflata pe portul fizic 3, VOQ 1 , va fi intarziata.

In functia findEmptyPosition.m se gaseste locatia libera din VOQ pentru destinatia spre care e intentionata in portul fizic corespunzator.

pos=n+1;

for i=1:n

if row(1,i)==0

pos=i;

break;

end

end

In caz ca pentru o anumita destinatie se afla un sir de celule in asteptare , functia determina unde se termina acest sir , si pozitia unde intra urmatoarea celula. Avem ca parametru un rand (row) . Daca coada de asteptare este goala determina prima pozitie libera si depunde celula in coada de asteptare, dar in cazul in care coada este plina, deoarece are marime finita, returneaza dimensiunea cozii de asteptare +1 . In functia calculateDelay.m va vedea ca depaseste lungimea maxima a cozii si aceasta celula va fi neglijata (se pierde ) .

Break se foloseste pentru a termina functia si o data ce o pozitielibera este gasita, celula va intra in coada de asteptare, si nu se va mai cauta o alta pozitie libera.

Urmatoarea functie findMin.m este de asemenea folosita in calculateDelay.m si ajuta la stabilirea pe prima „coloana ” de celule ce urmeaza sa fie transferate , care dintre ele au cea mai mare vechime in coada de asteptare conform OCF, pentru a fi alese sa plece la destinatie.

Ca parametrii avem primele valori din seria de porturi virtuale cu acelasi numar de ordine ( de exemplu: VOQ 3 din portul fizic 1 , VOQ 3 din portul fizic 2 , si VOQ 3 din portul fizic 3).

min=0;

elem=0;

gasit=false;

daca avem elem=0 inseamna ca nu avem celula. Si nu luam 0 ca fiind minim deoarece toate celelalte valori vor fi evident mai mari.

Cat timp nu e gasit, nu avem minim , scopul fiind sa gasim pozitia unde avem minim

if ~gasit

if col(1,i)~=0

min=i;

elem=col(1,i);

gasit=true;

end

Cat timp nu gaseste un element minim diferit de 0 continuam bucla, cand gasim minimul va fi automat asociat cu elementul respectiv pentru ca va fi prima valoare gasita si va ramane termen de comparatie.

Din acest punct se va execut ramura urmatoare.

Cautam in continuare sa existe elementele minime, neglijandu-se valoarea 0. In momentul in care am gasit un elem diferit de 0 comparam cu min , daca e mai mic decat min , devine el min la randul sau. Min imi arata din ce port fizic iese celula. Vom stii din functia calculateDelay care e portul virtual, aceasta functie, operand cu porturile virtuale si CalculateDelay va lua apoi fiecare serie de porturi virtuale in parte.

Functiile calculateDelay.m si calculateLength.m vor fi tratate in paralel deoarece difera prin simple instructiuni

Primeste ca parametru: P- numarul de porturi fizice si virtuale, ro, v- grad de corelatie, d – dimensiunea cozii de asteptare asociata fiecarui port virtual (este practic dimensiunea portului virtual , si o sa fie setabila din functiile de afisare plot), t- perioada de timp pe care se face simularea, input- vectorul de intrare de celule care este random si reprezinta sirul de celule random dat, care intra pe primul port fizic.

portMat = zeros(P,d,P);

PortMat – matrice tridimensionala in care se retin valorile din coada de asteptare pentru fiecare port virtual, pentru fiecare port fizic. Are ca dimensiuni numarul P – nr porturi virtuale, d-dimensiunea cozii de asteptare, P- numarul de porturi fizice.

De exemplu daca se ia valoarea 1,1,1 = portul virtual 1, pe pozitia 1, din portul fizic 1 .

Delay-ul este intarzierea, si este pus cu valoarea initiala 0 pentru ca o sa se incrementeze, intarzierea nemaiputand sa scada, ci doar va creste.

delay=0;

Lungimea este initializata cu 0 si spre deosebire de delay, aceasta va si scadea, dar va si creste.

len=0;

Apoi daca portul e diferit de 0, se introduce in portul virtual daca are loc. Se determina daca are loc , acesta fiind un exemplu al folosirii functiei findEmptyPosition

pos=findEmptyPosition(portMat(input(temp),:,1));

si daca are loc, daca pozitia este mai mica sau egala cu dimensiunea cozii de asteptare, se introduce in coada de asteptare

La calculateLength.m in schimb, crestea si lungimea cozii de asteptare, practic in len nu se retine o coada de asteptare anume, se retin cate elemente sunt in total in toate porturile virtuale din toate porturile fizice

if(pos<=d)

portMat(input(temp),pos,1)=temp;

len=len+1;

end

portIn=input(temp);

In PortIn se retine portul de intrare pentru portul fizic dat de I (I da un port fizic) . Portul fizic o sa creasca si se va suprascrie portIn. Cand i=3 de exemplu, portul 3 fizic, portIn o sa fie :

portIn=findVirtualPort(sumMat(portIn+1,:));

PortIn e de fapt celula de intrare, care iti da portul virtual in care intra.

Daca celula, sau portul e diferit de 0, cauta o pozitie libera, daca o gaseste, il introduce si in cazul asta creste lungimea. Daca nu , o neglijeaza.

Tot ce s-a mentionat mai sus a fost pentru partea de intrare in coada de asteptare. Ce vom analiza in continuare face parte din iesirea din coada.

Se vor lua in considerare eoate porturile si se foloseste functia findMin pentru fiecare port virtual.

Iesirea poate fi facuta doar de pe un singur port virtual. Initial se determina pozitia portului virtual unde trebuie sa se faca iesirea. Pentru iesire va fi ales portul virtual care are elemental cel mai vechi dintre toate porturile. In caz de egalitate, se va alege primul cu intarzierea cea mai mare. Faptul ca se alege primul, este ilustrat in functia find Min, coloana strict mai mica decat element, daca e mai mic sau egal nu o ia in considerare.

if col(1,i)~=0 && col(1,i)<elem

Functia findMin.m gaseste minimul, si daca gaseste altul egal, nu il mai ia in considerare .

Daca exista un port virtual care poate sa faca iesire, o sa ne dea o valoare diferita de 0 , daca nu, o sa ne dea 0. In cazul in care se returneaza 0 nu avem ce iesire sa facem si vom repeta pentru alt port, dar daca ne returneaza diferit de 0, scadem coada de asteptare.

Deplaseaza toate elementele de pe portul virtual care a facut iesirea , cu o pozitie mai spre iesire astefel: vom gasi prima pozitie , ca sa nu deplasam tot vectorul , si dupa acea vom deplasa . De la prima pozitie gasita libera, deplasam totul spre iesirea portului – toate valorile din coada de asteptare.

dim=findEmptyPosition(portMat(i,:,portOut));

Se foloseste pentru optimizare functia de mai sus.

In urmatoarea parte se face literalmente deplasarea:

for j=1:dim-2

portMat(i,j,portOut)=portMat(i,j+1,portOut);

end

if dim>1

portMat(i,dim-1,portOut)=0;

Asociaza 0 pe ultima pozitie , dupa ce deplasam cu totul , o sa mai ramana un element. Iese ultimul element din dreapta, toate celulele se deplaseaza si practic ramane liber un loc in stanga, care va fi scris ca 0

totalDelay=delay;

In functia CalculateLength.m este acelasi principiu. Ne returneaza lungimea medie pe care o are, impartind la numarul de porturi din momentul respective , la timpul t.

Functiile Plot

Parametrii ii setam direct din functie si ii initializam cum dorim. Luam fiecare valoare a lui P in parte, prin P luam toate numerele posibile de porturi de la 1 pana la 20. P fiind acum numarul maxim de porturi, facem plotarea in functie de P.

PlotdelayforP.m

Luam pentru portul 1 – generam un vector de intrare si calculam in conditiile de v=1,v=0.5, 0.25, 0.125, ro/P

result(6,i) – aceasta este limita introdusa

hold on – Vomfolosi functia pentru a le putea pune pe toate pe acelasi graphic. Daca nu punem hold on, vom avea 6 grafice

grid on- ca sa ne afiseze liniile vertical

plot(P,result(1,:),'kx-');

P este pe OX, result (1,:) e pe OY, si apoi cum sa arate linia

legend('v=1','v=0.5','v=0.25','v=0.125','v=ro/P','Limita','Location','NorthEastOutside');

PlotdelayforRo.m

Ro este un vector in cazul acesta, si am mentionat sa fie luat din 0.1 din 0.1

input = randi(P+1,t,1)-1; cand P este constant putem genera un vector pentru toate simularile , in plotDelayforP nu se putea genera la fel, deoarece P era variabil

Capitol 5 – Simulare comutatoare cu siruri pe intrare

Rezumate teoretice și experimentale . Interpretări și concluzii

Bibliografie

Anexe

generateMatrix.m

function[outMat] = generateMatrix(P, ro, v)

outMat = zeros(P + 1);

y = 0; z = 0; m=0;x=0;

if(v == 1)

y = 0;

z = 0;

m = 0;

x = 1;

end

if(v == 0.5)

x = (4-5*ro)/(4*(1-ro));

y = 1/4;

z = 1/(4*(P-1));

m = ro/(4*P*(1-ro));

end

if(v == 0.25)

x = (8-11*ro)/(4*(1-ro));

y = 3/8;

z = 3/(8*(P-1));

m = (3*ro)/(8*P*(1-ro)) ;

end

if(v == 0.125)

x = (16-23*ro)/(16*(1-ro));

y = 7/16;

z = 7/(16*(P-1));

m = (7*ro)/(16*P*(1-ro));

end

if(abs(v – ro/P) < 0.0000001)

x = (P-2*P*ro+ro*ro)/(P*(1-ro));

y = 1- ro/P;

z = 0;

m = (ro*(P-ro))/(P*P*(1-ro));

end

n = size(outMat);

outMat(2:n, 1) = y;

outMat(1, 2:n) = m;

outMat(1,1) = x;

for i = 2:n

for j = i + 1:n

outMat(i, j) = z;

outMat(j, i) = z;

end

end

for di = 2:n

outMat(di, di) = v;

end

end

getSumMatrix.m

function[outMat] = getSumMatrix(inMat)

n = length(inMat);

outMat = zeros(n); %initializare

outMat(:,1) = inMat(:, 1); %copiaza prima coloana din matricea de intrare

for i = 2:n

outMat(:, i) = outMat(:, i – 1) + inMat(:, i);

end

end

findVirtualPort.m

function[port] = findVirtualPort(row)

[m,n]=size(row);

alfa=rand(1,1);

if alfa<=row(1,1)

port=0;

else

for i=1:n-1

if alfa>row(1,i) && alfa<=row(1,i+1)

port=i;

end

end

end

end

findEmptyPosition.m

function[pos] = findEmptyPosition(row)

[m,n]=size(row);

pos=n+1;

for i=1:n

if row(1,i)==0

pos=i;

break;

end

end

end

findMin.m

function[min] = findMin(col)

[m,n]=size(col);

min=0;

elem=0;

gasit=false;

for i=1:n

if ~gasit

if col(1,i)~=0

min=i;

elem=col(1,i);

gasit=true;

end

else

if col(1,i)~=0 && col(1,i)<elem

elem=col(1,i);

min=i;

end

end

end

end

calculateDelay.m

function[totalDelay]=calculateDelay(P, ro, v, d, t, input)

genMat = generateMatrix(P, ro, v);

sumMat = getSumMatrix(genMat);

portMat = zeros(P,d,P);

delay=0;

for temp = 1:t

%se verifica inputul pt primul port

if input(temp)~=0

%se determina prima "pozitie" libera in coada de asteptare a

%portului virtual din primul port fizic, port virtual dat de

%valoarea de intrare pe portul fizic 1 de la perioada de timp temp

pos=findEmptyPosition(portMat(input(temp),:,1));

%daca exista pozitii libere, intrarea va fi pastrata in prima

%pozitie libera gasita; daca nu, celula se pierde

if(pos<=d)

portMat(input(temp),pos,1)=temp;

end

end

portIn=input(temp);

% se realizeaza verificarile pentru celelalte porturi fizice

for i=2:P

% se determina valoarea intrarii pentru portul i la timpul temp,

% calculata pe baza valorii de intrare a portului anterior

portIn=findVirtualPort(sumMat(portIn+1,:));

if portIn~=0

pos=findEmptyPosition(portMat(portIn,:,i));

if(pos<=d)

portMat(portIn,pos,i)=temp;

end

end

end

%iesire

for i=1:P

%se determina portul pe al carui port virtual va face iesirea

portOut=findMin(portMat(i,1,:));

% daca exista element pe liniile virtuale i care pot iesi…

if portOut~=0

%se cumuleaza intarzierea

delay=delay+(temp-portMat(i,1,portOut));

% se realizeaza iesirea elementului de pe portul determinat si

% se deplaseaza coada de asteptare asociata cu o pozitie

dim=findEmptyPosition(portMat(i,:,portOut));

for j=1:dim-2

portMat(i,j,portOut)=portMat(i,j+1,portOut);

end

if dim>1

portMat(i,dim-1,portOut)=0;

end

end

end

end

totalDelay=delay;

end

calculateLength.m

function[mediumLength]=calculateLength(P, ro, v, d, t, input)

genMat = generateMatrix(P, ro, v);

sumMat = getSumMatrix(genMat);

portMat = zeros(P,d,P);

len=0;

for temp = 1:t

%se verifica inputul pt primul port

if input(temp)~=0

%se determina prima "pozitie" libera in coada de asteptare a

%portului virtual din primul port fizic, port virtual dat de

%valoarea de intrare pe portul fizic 1 de la perioada de timp temp

pos=findEmptyPosition(portMat(input(temp),:,1));

%daca exista pozitii libere, intrarea va fi pastrata in prima

%pozitie libera gasita; daca nu, celula se pierde

if(pos<=d)

portMat(input(temp),pos,1)=temp;

len=len+1;

end

end

portIn=input(temp);

% se realizeaza verificarile pentru celelalte porturi fizice

for i=2:P

% se determina valoarea intrarii pentru portul i la timpul temp,

% calculata pe baza valorii de intrare a portului anterior

portIn=findVirtualPort(sumMat(portIn+1,:));

if portIn~=0

pos=findEmptyPosition(portMat(portIn,:,i));

if(pos<=d)

portMat(portIn,pos,i)=temp;

len=len+1;

end

end

end

%iesire

for i=1:P

%se determina portul pe al carui port virtual va face iesirea

portOut=findMin(portMat(i,1,:));

% daca exista element pe liniile virtuale i care pot iesi…

if portOut~=0

%se elimina elementul din coada de asteptare

len=len-1;

% se realizeaza iesirea elementului de pe portul determinat si

% se deplaseaza coada de asteptare asociata cu o pozitie

dim=findEmptyPosition(portMat(i,:,portOut));

for j=1:dim-2

portMat(i,j,portOut)=portMat(i,j+1,portOut);

end

if dim>1

portMat(i,dim-1,portOut)=0;

end

end

end

end

mediumLength=len/P;

end

plotDelayForP.m

function plotDelayForP

Ro=0.9;

P=1:20;

d=40;% capacitatea cozii de asteptare asociate fiecarui port virtual

t=100; %simulare pentru 100 de unitati de timp

for i=1:20

input = randi(i+1,t,1)-1; % vectorul de intrare

result(1,i)=calculateDelay(i, Ro,1, d, t, input);

result(2,i)=calculateDelay(i, Ro,0.5, d, t, input);

result(3,i)=calculateDelay(i, Ro,0.25, d, t, input);

result(4,i)=calculateDelay(i, Ro,0.125, d, t, input);

result(5,i)=calculateDelay(i, Ro,Ro/i, d, t, input);

result(6,i)=(i-Ro)/(1-Ro);

end

hold on

grid on

plot(P,result(1,:),'kx-');

plot(P,result(2,:),'r*-');

plot(P,result(3,:),'gs-');

plot(P,result(4,:),'bo-');

plot(P,result(5,:),'md-');

plot(P,result(6,:),'k-');

legend('v=1','v=0.5','v=0.25','v=0.125','v=ro/P','Limita','Location','NorthEastOutside');

title('Intarzierea in functie de P');

xlabel('P');

ylabel('Intarziere');

hold off

end

plotDelayForRo.m

function plotDelayForRo

Ro=0.1:0.1:0.9;

P=16;%se considera 16 porturi

d=40;% capacitatea cozii de asteptare asociate fiecarui port virtual

t=100; %simulare pentru 100 de unitati de timp

input = randi(P+1,t,1)-1; % vectorul de intrare

for i=1:9

result(1,i)=calculateDelay(P, Ro(1,i),1, d, t, input);

result(2,i)=calculateDelay(P, Ro(1,i),0.5, d, t, input);

result(3,i)=calculateDelay(P, Ro(1,i),0.25, d, t, input);

result(4,i)=calculateDelay(P, Ro(1,i),0.125, d, t, input);

result(5,i)=calculateDelay(P, Ro(1,i),Ro(1,i)/P, d, t, input);

result(6,i)=(P-Ro(1,i))/(1-Ro(1,i));

end

hold on

grid on

plot(Ro,result(1,:),'kx-');

plot(Ro,result(2,:),'r*-');

plot(Ro,result(3,:),'gs-');

plot(Ro,result(4,:),'bo-');

plot(Ro,result(5,:),'md-');

plot(Ro,result(6,:),'k-');

legend('v=1','v=0.5','v=0.25','v=0.125','v=ro/P','Limita','Location','NorthEastOutside');

title('Intarzierea in functie de \rho');

xlabel('\rho');

ylabel('Intarziere');

hold off

end

plotLengthForP.m

function plotLengthForP

Ro=0.9;

P=1:20;

d=40;% capacitatea cozii de asteptare asociate fiecarui port virtual

t=100; %simulare pentru 100 de unitati de timp

for i=1:20

input = randi(i+1,t,1)-1; % vectorul de intrare

result(1,i)=calculateLength(i, Ro,1, d, t, input);

result(2,i)=calculateLength(i, Ro,0.5, d, t, input);

result(3,i)=calculateLength(i, Ro,0.25, d, t, input);

result(4,i)=calculateLength(i, Ro,0.125, d, t, input);

result(5,i)=calculateLength(i, Ro,Ro/i, d, t, input);

end

hold on

grid on

plot(P,result(1,:),'kx-');

plot(P,result(2,:),'r*-');

plot(P,result(3,:),'gs-');

plot(P,result(4,:),'bo-');

plot(P,result(5,:),'md-');

legend('v=1','v=0.5','v=0.25','v=0.125','v=ro/P','Location','NorthEastOutside');

title('Lungimea medie a cozii in functie de P');

xlabel('P');

ylabel('Lungimea medie');

hold off

end

plotLengthForRo.m

function plotLengthForRo

Ro=0.1:0.1:0.9;

P=16;%se considera 16 porturi

d=40;% capacitatea cozii de asteptare asociate fiecarui port virtual

t=100; %simulare pentru 100 de unitati de timp

input = randi(P+1,t,1)-1; % vectorul de intrare

for i=1:9

result(1,i)=calculateLength(P, Ro(1,i),1, d, t, input);

result(2,i)=calculateLength(P, Ro(1,i),0.5, d, t, input);

result(3,i)=calculateLength(P, Ro(1,i),0.25, d, t, input);

result(4,i)=calculateLength(P, Ro(1,i),0.125, d, t, input);

result(5,i)=calculateLength(P, Ro(1,i),Ro(1,i)/P, d, t, input);

end

hold on

grid on

plot(Ro,result(1,:),'kx-');

plot(Ro,result(2,:),'r*-');

plot(Ro,result(3,:),'gs-');

plot(Ro,result(4,:),'bo-');

plot(Ro,result(5,:),'md-');

legend('v=1','v=0.5','v=0.25','v=0.125','v=ro/P','Location','NorthEastOutside');

title('Lungimea medie in functie de \rho');

xlabel('\rho');

ylabel('Lungimea medie');

hold off

end