Rolul Si Importanta Procesului de Simulare Si Optimizare a Retelelor de Comunicatii
Introducere
Este inutil să mai spunem că trăim astăzi într-o eră a informaticii și a calculatoarelor. Ceea ce este demn de remarcat este faptul că cele mai multe calculatoare sunt folosite azi în interconectare, în rețele locale și de arie largă, ceea ce conferă informaticii un rol determinant în asigurarea legăturilor științifice, de afaceri, bancare sau de natură umană între persoane și instituții. Calculatoarele au devenit terminale ideale, inteligente, care tind să ia locul terminalelor clasice de comunicare (telefon, telefax, videotelefon etc.), în rețele de comunicații de tip Intranet, Extranet sau INTERNET.
Importanța tehnologiilor informatice și a comunicațiilor, pe plan economic, social și politic, este unanim cunoscută și acceptată. Se poate observa că în ultimii ani asistăm la:
multiplicarea numărului de calculatoare;
creșterea puterii de prelucrare și stocare a acestor calculatoare;
scăderea prețului echipamentelor și programelor;
convergența tehnologiilor informatice și de comunicații;
descentralizarea funcțiilor informatice și de comunicații;
dezvoltarea serviciilor informatice, ceea ce face ca, în anumite țări, fiecare persoană să fie un utilizator real sau potențial al rețelelor de calculatoare și de comunicații.
Ca urmare a importanței crescute a sistemelor informatice, s-a pus problema din ce în ce mai acută a fiabilității rețelelor de comunicații. Astfel, s-a pus problema găsirii unor soluții de optimizare a traficului din cadrul rețelelor. Soluțiile la care s-a ajuns s-au concretizat în câteva seturi de algoritmi de optimizare, care, în funcție de specificul lor, își propun să “vindece” și să optimizeze traficul din anumite segmente ale rețelelor.
Această lucrare încearcă o abordare a acestei largi palete de probleme asociate optimizării în rețelele de comunicații. Lucrarea cuprinde în total 5 capitole.
Capitolul unu evidențiază câteva aspecte generale cu privire la rețelele de comunicații. Alături de definirea acestora, se face o prezentare generală a rețelelor de date, atât din punctul de vedere al evoluției, structurii și parametrilor acestora, cât și al avantajelor reale pe care le posedă. În partea finală a capitolului este efectuată o prezentare generală asupra modelului arhitectural ISO-OSI, care cuprinde noțiuni legate de structura, funcționarea și funcțiile caracteristice modelului.
Capitolul doi prezintă pe scurt caracteristicile principale ale rețelelor de date. Cu această ocazie vom întâlni noțiunea de “topologie”, împreună cu tipurile de topologii și caracteristicile acestora. Tot în acest capitol vom întâlni o descriere sumară a protocolului de comunicație (cu definiția, structura și funcțiile lui) și a metodelor de acces la mediul de comunicație (cu descrierea fiecărei metode în parte).
Capitolul trei face o analiză asupra rolului și importanței procesului de simulare și optimizare a rețelelor de comunicații. Este cunoscut faptul că, în ultimul timp, se folosește din ce în ce mai mult procesul de “simulare” în analiza și evaluarea performanțelor unui sistem. Ca urmare, în acest capitol se prezintă etapele de analiză în cadrul proiectării rețelelor de comunicații și probleme legate de modelarea acestora.
Capitolul patru face referire strict la problema optimizării rețelelor de comunicație la nivelul structurii topologice. Tot aici se va defini și noțiunea de “algoritm”, se va face o descriere sumară a acestora, iar în final vor fi prezentate cele mai importante metode de elaborare a algoritmilor.
Capitolul cinci studiază cei mai importanți algoritmi întâlniți în procesul de simulare și optimizare a rețelelor de comunicații. Pentru fiecare algoritm în parte sunt atinse câteva etape: prezentarea problematicii generale a algoritmului, descrierea pe etape a algoritmului, exemplificarea funcționării algoritmului pe un caz particular, observații (unde este cazul) și în final probleme legate de implementarea algoritmului sub forma unui soft prezentat în capitolul de Anexe.
Capitolul șase prezintă pas cu pas modalitatea de utilizare a unui pachet de programe realizat în limbajul de programare DELPHI 5.0, care simulează fiecare algoritm de optimizare prezentat în capitolul anterior.
În capitolul de concluzii sunt punctate câteva idei cu privire la scopurile pe care și le-a propus această lucrare și ce a reușit să contureze în problema optimizării rețelelor de comunicație cu ajutorul algoritmilor de optimizare și a unui pachet de programe atașat.
Capitolul I
NOȚIUNI GENERALE PRIVIND REȚELELE DE COMUNICAȚII
1.1 Definirea rețelelor de comunicații
SIstemele informatice sunt din ce în ce mai utilizate în cele mai diverse domenii ale activității umane. Ele sunt folosite, sau fiecare în parte, în mod independent, sau cooperând și schimbând date cu alte sisteme. Prin cooperarea între calculatoare se poate realiza transferul de informații de la un calculator la altul, se poate accesa de la distanță o bază de date, se pot utiliza resursele software și hardware ale unui supercalculator, etc.
Interconectare
= două calculatoare se consideră interconectate dacă pot schimba informații între ele.
Mediu de comunicație
= mediul fizic prin intermediul căruia se pot transmite informații (cablu, fibră optică, radio, satelit).
Rețea de calculatoare
= ansamblu de calculatoare interconectate prin intermediul unor medii de comunicație, asigurând folosirea în comun, de către un număr mare de utilizatori, a tuturor resurselor fizice, logice și informaționale ale ansamblului.
= reprezintă interconectarea unor stații de lucru, terminale și a altor periferice.
Prin urmare, o rețea de calculatoare este alcătuită dintr-un ansamblu de mijloace de transmisiune și sisteme de calcul, necesare pentru a realiza atât funcțiuni pentru transportul informației, cât și funcțiuni de prelucrare a acesteia. Dar fiecare sistem de calcul are modul său specific de stocare a informației și de interfațare cu exteriorul.
O rețea care interconectează diferite sisteme de calcul poate funcționa numai dacă există o convenție (protocol).
Un protocol de comunicație este constituit din regulile procedurii pe care trebuie să o respecte sistemele de calcul atunci când comunică între ele. Datorită importanței sale, această noțiune va face obiectul unui studiu separat în cadrul lucrării de față.
Revenind la noțiunea de rețea și simplificând-o puțin, putem privi rețeaua de comunicații ca fiind un grup de noduri interconectate, un nod putând să conțină:
calculator gazdă sau host;
terminal video;
controler de comunicație;
echipamente periferice.
Rețelele pentru comunicații de date au devenit parte integrantă a societății moderne. Standardizarea protocoalelor de comunicații a permis ca interconectarea rețelelor și sistemelor de calcul eterogene să devină o realitate.
1.2 Prezentarea generală a rețelelor de date
1.2.1 Evoluția rețelelor de date
Datorită progresului tehnologic oamenii au fost nevoiți să facă față unor cantități din ce în ce mai mari de date și din necesitatea de prelucrare rapidă a acestor date, oamenii au recurs la procesarea informației cu ajutorul echipamentelor de calcul.
În cadrul primelor generații de echipamente de calcul au apărut primele calculatoare de mare capacitate (mainframe) cărora li se atașa un număr mare de terminale neinteligente la care puteau avea acces utilizatori, beneficiind simultan de puterea de calcul a calculatorului central.
Tot progresul tehnologic este acela care a permis miniaturizarea și reducerea costurilor circuitelor integrate, ajungându-se astfel la calculatoarele personale (PC – Personal Computer) accesibile din punct de vedere al prețului și convenabile în ceea ce privește puterea de calcul (rezultând astfel un raport preț-performanță optim). Astfel s-a realizat transferul puterii de procesare de la mainframe la PC-urile utilizatorilor, acesta din urmă reprezentând materializarea conceptului de calculator distribuit.
Pentru aprecierea încadrării arhitecturii rețelelor, există două criterii deosebit de importante: tehnologia de transmisie și scara la care se operează.
Tehnologia de transmisie se găsește de obicei în două forme:
Rețele cu difuzare (cu difuzare):
un singur canal de comunicație este partajat de toate mașinile din rețea;
comunicația se realizează prin intermediul unor mesaje scurte, numite pachete, care au în structura lor, printre altele, un câmp pentru desemnarea expeditorului și unul pentru desemnarea destinatarului;
există și posibilități de transmitere a mesajului ori la o submulțime de mașini, ori la toate mașinile, acest mod de operare numindu-se difuzare.
Rețelele punct-la-punct (peer-to-peer):
dispun de numeroase conexiuni între perechile de mașini individuale ce formează rețeaua;
pentru un pachet de date, pentru a ajunge la destinație, există trasee multiple, fiecare traseu putând să însemne parcurgerea altor mașini individuale; de aceea, în cadrul acestor tipuri de rețele, algoritmii de dirijare joacă un rol deosebit;
este un model folosit pentru rețelele mari, în timp ce difuzarea se folosește pentru rețelele mici.
Scara la care se operează arhitecturile rețelelor mai importante se poate reda sugestiv în graficul următor, care va prezenta doi parametrii importanți caracteristici acestor rețele și anume “distanța între stații” și “viteza de transfer”.
Fig. 1.1 Clasificarea rețelelor în funcție de distanță
După mărimea rețelei, distingem trei tipuri de rețele de date:
Rețele locale (LAN = Local Area Network): rețele localizate într-o singură clădire sau într-un campus de cel mult câțiva kilometri; sunt frecvent utilizate pentru interconectarea PC-urilor și stațiilor de lucru; conectarea se face de obicei cu ajutorul unui singur cablu, la care sunt legate toate mașinile; se disting de alte tipuri de rețele prin trei caracteristici: mărime, tehnologie de transmisie și topologie; pot opera la viteze destul de mari și produc erori foarte puține.
În forma sa elementară, o rețea locală este o facilitate de comunicare a datelor care asigură conexiuni comutate de viteză înaltă de procesare, periferice și terminale, localizate într-o singură clădire, universitate sau institut. Din punct de vedere istoric, dezvoltarea rețelelor locale a avut ca punct de plecare domeniul prelucrărilor de date, la nivelul de birou sau companie, iar în cadrul acestora, prelucrările datelor financiar–contabile (economice) solicitau ca dispozitivele de memorare, de mare capacitate și relativ scumpe, precum și imprimantele, să fie accesibile mai multor calculatoare. Astfel, într-o anumită măsură, rețelele locale s-au dezvoltat ca o soluție pentru prelucrările de date cu cost redus, dar care utilizează echipamente periferice cu costuri ridicate. Într-adevăr, rețelele locale din prima generație erau formate din sisteme distribuite de calculatoare, care utilizau legături private de date de mare viteză, între nodurile de prelucrare și echipamentele periferice.
O a doua rațiune care a stat la baza dezvoltării rețelelor locale a fost nevoia instituțiilor moderne de a efectua prelucrări distribuite de date. O rețea locală asigură distribuirea corectă a puterii de calcul pentru fiecare utilizator, dar permite utilizatorilor conectarea și la alte resurse de calcul din rețea. Distribuirea puterii de calcul permite utilizatorilor să devină mai productivi și multe organizații și-au redimensionat sau chiar și-au eliminat centrele convenționale de date, proces cunoscut sub numele de proces de reducere.
Rețeaua LAN ideală: trebuie să fie asemenea unui sistem de distribuție a informațiilor, la fel de ușor de utilizat ca și rețeaua convențională de distribuție a curentului electric alternativ dintr-o clădire. Astfel, adăugarea unui terminal pentru introducerea datelor, a unui procesor sau a unor echipamente periferice la o rețea locală nu ar trebui să fie mai complicată decât realizarea unor conexiuni la un port de acces, amplasat convenabil. La conectare, fiecare dintre acestea ar trebui să comunice dormanță optim). Astfel s-a realizat transferul puterii de procesare de la mainframe la PC-urile utilizatorilor, acesta din urmă reprezentând materializarea conceptului de calculator distribuit.
Pentru aprecierea încadrării arhitecturii rețelelor, există două criterii deosebit de importante: tehnologia de transmisie și scara la care se operează.
Tehnologia de transmisie se găsește de obicei în două forme:
Rețele cu difuzare (cu difuzare):
un singur canal de comunicație este partajat de toate mașinile din rețea;
comunicația se realizează prin intermediul unor mesaje scurte, numite pachete, care au în structura lor, printre altele, un câmp pentru desemnarea expeditorului și unul pentru desemnarea destinatarului;
există și posibilități de transmitere a mesajului ori la o submulțime de mașini, ori la toate mașinile, acest mod de operare numindu-se difuzare.
Rețelele punct-la-punct (peer-to-peer):
dispun de numeroase conexiuni între perechile de mașini individuale ce formează rețeaua;
pentru un pachet de date, pentru a ajunge la destinație, există trasee multiple, fiecare traseu putând să însemne parcurgerea altor mașini individuale; de aceea, în cadrul acestor tipuri de rețele, algoritmii de dirijare joacă un rol deosebit;
este un model folosit pentru rețelele mari, în timp ce difuzarea se folosește pentru rețelele mici.
Scara la care se operează arhitecturile rețelelor mai importante se poate reda sugestiv în graficul următor, care va prezenta doi parametrii importanți caracteristici acestor rețele și anume “distanța între stații” și “viteza de transfer”.
Fig. 1.1 Clasificarea rețelelor în funcție de distanță
După mărimea rețelei, distingem trei tipuri de rețele de date:
Rețele locale (LAN = Local Area Network): rețele localizate într-o singură clădire sau într-un campus de cel mult câțiva kilometri; sunt frecvent utilizate pentru interconectarea PC-urilor și stațiilor de lucru; conectarea se face de obicei cu ajutorul unui singur cablu, la care sunt legate toate mașinile; se disting de alte tipuri de rețele prin trei caracteristici: mărime, tehnologie de transmisie și topologie; pot opera la viteze destul de mari și produc erori foarte puține.
În forma sa elementară, o rețea locală este o facilitate de comunicare a datelor care asigură conexiuni comutate de viteză înaltă de procesare, periferice și terminale, localizate într-o singură clădire, universitate sau institut. Din punct de vedere istoric, dezvoltarea rețelelor locale a avut ca punct de plecare domeniul prelucrărilor de date, la nivelul de birou sau companie, iar în cadrul acestora, prelucrările datelor financiar–contabile (economice) solicitau ca dispozitivele de memorare, de mare capacitate și relativ scumpe, precum și imprimantele, să fie accesibile mai multor calculatoare. Astfel, într-o anumită măsură, rețelele locale s-au dezvoltat ca o soluție pentru prelucrările de date cu cost redus, dar care utilizează echipamente periferice cu costuri ridicate. Într-adevăr, rețelele locale din prima generație erau formate din sisteme distribuite de calculatoare, care utilizau legături private de date de mare viteză, între nodurile de prelucrare și echipamentele periferice.
O a doua rațiune care a stat la baza dezvoltării rețelelor locale a fost nevoia instituțiilor moderne de a efectua prelucrări distribuite de date. O rețea locală asigură distribuirea corectă a puterii de calcul pentru fiecare utilizator, dar permite utilizatorilor conectarea și la alte resurse de calcul din rețea. Distribuirea puterii de calcul permite utilizatorilor să devină mai productivi și multe organizații și-au redimensionat sau chiar și-au eliminat centrele convenționale de date, proces cunoscut sub numele de proces de reducere.
Rețeaua LAN ideală: trebuie să fie asemenea unui sistem de distribuție a informațiilor, la fel de ușor de utilizat ca și rețeaua convențională de distribuție a curentului electric alternativ dintr-o clădire. Astfel, adăugarea unui terminal pentru introducerea datelor, a unui procesor sau a unor echipamente periferice la o rețea locală nu ar trebui să fie mai complicată decât realizarea unor conexiuni la un port de acces, amplasat convenabil. La conectare, fiecare dintre acestea ar trebui să comunice de o manieră inteligentă cu oricare alt dispozitiv din rețea. Sistemul ideal este caracterizat de trăsăturile care fac ca sistemul de distribuție a energiei electrice să fie ușor de utilizat:
se instalează o singură dată;
acces larg;
independența aplicațiilor;
capacitate în exces;
întreținere și administrare ușoară.
Instalare unică :
Scopul general al instalării unice nu este atins, în practică, de nici o arhitectură LAN. Chiar și un sistem telefonic, care este indispensabil în orice clădire, presupune reinstalarea cablurilor telefonice atunci când abonații se mută, chiar dacă această mutare se efectuează dintr-o zonă în alta a aceluiași birou.
Acces larg :
Înainte ca rețeaua de distribuție a informațiilor să asigure în mod real dreptul nelimitat de acces, este necesar să se reducă costurile numărului semnificativ de porturi neutilizate. Deși cablurile telefonice torsadate sunt relativ ieftine, porturile telefonice neutilizate implică, în general, niște costuri semnificative ascunse, asociate interfețelor electronice prin intermediul cărora sunt conectate cablurile la echipamentul central. Arhitecturile cu acces distribuit, cum ar fi CSMA (Carrier Sense Multiple Acces) sau rețelele cu transfer de jeton, nu determină costuri ascunse pentru porturile neutilizate atât timp cât nu se depășește numărul maxim admis de porturi.
Independență față de aplicații :
O condiție importantă ca o rețea informațională să asigure aplicații multiple este aceea a îndeplinirii funcțiilor de comunicație a datelor de nivel înalt. Furnizorii sistemelor LAN realizate cu cablu coaxial sunt în general mai avansați în această privință, deși este vorba mai degrabă de o tendință a pieței decât de o diferență tehnologică. Sistemele CSMA și cele cu transfer de jeton asigură, de asemenea, o viteză înaltă de transfer a datelor pentru aplicațiile care solicită această capacitate.
Capacitate în exces :
Într-un anume sens, arhitecturile CSMA și cele cu transfer de jeton sunt ideale deoarece întreaga capacitate a sistemului este disponibilă la nivelul fiecărui port. Un port poate utiliza exact lărgimea de bandă care este necesară, dar pe de altă parte, această caracteristică limitează capacitatea sistemului. Dacă cerințele totale de bandă de transfer ale unei stații depășesc lărgimea de bandă a sistemului, extinderea necesară a acesteia este fie foarte costisitoare, fie imposibilă.
Spre deosebire de sistemele menționate mai sus, arhitecturile cu circuite comutabile (PBX) pot fi extinse aproape nelimitat. Lărgimea de bandă asigurată la nivelul fiecărui port rămâne nemodificată pe măsură ce se adaugă noi stații.
Ușurință în întreținere și administrare :
Sistemele cel mai dificil de întreținut sunt sistemele de bandă largă, datorită cerințelor stricte referitoare la factorii de amplificare ai amplificatoarelor și egalizatoarelor. Din punctul de vedere al comunicațiilor de date, unitățile PBX integrate pentru voce/date sunt ușor de întreținut datorită existenței unei proceduri bine stabilite pentru serviciile telefonice. Mai mult decât atât, furnizorii de PBX sunt obișnuiți să asigure sisteme de asistență la cheie pentru întregul ciclu de funcționare al instalației. Dar, datorită specificității produselor, ei nu asigură, în general, cerințe de comunicație de nivel înalt.
Pentru dezvoltarea unei rețele locale ideale, trebuie depășite patru obstacole majore:
Nu există un singur standard: datorită modificării și evoluției continue a rețelelor locale, precum și a concurenței naturale care există între diverșii furnizori, există mai multe standarde pentru rețele LAN – atât oficiale, cât și neoficiale. Situația aceasta tinde să se rezolve, deoarece chiar și furnizorii importanți care și-au protejat specificațiile interfețelor, încep, sub presiunea unei piețe de desfacere din ce în ce mai exigente și mai mature, să pună la dispoziție aceste specificații.
Cerințe diverse: cerințele de comunicație ale unei clădiri de birouri moderne includ comunicațiile prin voce și video, comunicațiile de date cu viteză înaltă și cu viteză joasă, alarmarea în caz de incendiu, securitate, poșta electronică și așa mai departe. Aceste sisteme de comunicație prezintă cerințe de transmisie care variază substanțial în ceea ce privește vitezele de transfer, întârzierile acceptabile în furnizarea datelor, fiabilitatea și toleranța la erori.
Transmisii costisitoare: fiind capabile să livreze zeci de Mbiți/s către un anumit dispozitiv și numai câteva mii de biți către un altul, rezultă că dispozitivul cu o viteză de transfer mai mică este încărcat cu o notă de plată a transmisiei mai mare. Cea mai bună soluție economică în acest caz implică proiectarea unei rețele ierarhizate (cu niveluri ierarhice pe capacități), care să permită conectarea prin cabluri torsadate a dispozitivelor cu viteze mici și medii de transfer a datelor (la nivelul ierarhic inferior), conectate apoi la un sistem de transmisie de tip trunchi, cu o bandă largă de transfer (nivelul ierarhic superior, realizat cu cablu coaxial sau fibre optice).
Cerințe funcționale sofisticate: proiectarea unei rețele locale care să asigure vitezele de transfer dorite și să acopere distanțele cerute
reprezintă doar una din cerințele care trebuie satisfăcute în rezolvarea problemelor comunicațiilor de date. Înainte ca un anumit echipament de date să poată comunica de o manieră inteligentă cu un altul, numeroase alte funcții de comunicație la nivel înalt trebuie să fie compatibile. Acestea includ codurile, formatele, controlul erorilor, modurile de adresare, rutarea, controlul fluxului de date, gestiunea configurației și alocațiile de cost.
Routerele operează la nivelul rețea al modelului de referință ISO (ce va fi studiat separat în cadrul acestei lucrări) și asigură anumite funcții pe care punțile nu sunt capabile să le ofere, deoarece acestea operează la nivelul legăturii de date al modelului mai sus menționat. Două dintre funcțiile suplimentare asigurate de routere se referă la atribuirea dinamică a căilor de comunicație și la fragmentarea cadrului.
Capacitatea de a atribui dinamic diverse căi de comunicație permite routerelor să utilizeze căi alternative de comunicație, în cazul în care un circuit de comunicație devine inoperant. În plus, această abilitate permite routerelor să efectueze dinamic echilibrarea gradului de încărcare al traficului de comunicație atunci când sunt disponibile routere alternative între rețele. Această capacitate poate reduce sau chiar elimina efectul potențial al supraaglomerării traficului, atunci când cantitatea informațiilor transferate de la o rețea la alta depășește capacitatea de transmisie a unui singur circuit de comunicație.
În practică, se întâlnesc rețele industriale (robotică și de producție) și rețele birotice (crearea, modificarea, ocrotirea, gestiunea și circulația documentelor).
Revenind la definiție, o rețea LAN este proprietatea instituției care o folosește, deci nu este o rețea publică sau cu utilități în scopuri comerciale. Debitul datelor transmise în aceste rețele este ridicat, de la 1 Mb/s la 100 Mb/s. Numărul calculatoarelor conectate într-o astfel de rețea este în mod tipic mai mic de 500. Lungimea suportului fizic, dependent de tipul rețelei este mai mic de 2500 m, ceea ce duce la timpi de propagare mici și procent de erori de asemenea mic.
Natura rețelei și, prin urmare, performanțele ei, exprimate prin număr de sisteme și timpi de răspuns, sunt determinate de factori ca:
tipul aplicațiilor suportate de rețea;
echipamentele hardware și software utilizate pentru instalarea rețelei locale;
volumul informațiilor de transferat, natura lor (voce, date structurate sau nestructurate, grafice, imagini de tip facsimil sau video) și debitul la care se face transferul;
– tipul de acces la rețea, modul în care se controlează funcționarea
rețelei, lungimea maximă a sa;
tipul interacțiunii sistemelor, numite și noduri ale rețelei, ceea ce implică cunoașterea relațiilor ierarhice ale nodurilor unele față de altele și față de exterior.
În tehnologia LAN ansamblul acestor considerații coincide cu aspectele legate de:
topologie (care vor fi studiate la un punct viitor al acestui capitol);
metoda de acces, control și alocare a canalelor de comunicații ale rețelei;
modul de transmisie;
suportul de transmisie.
De observat este faptul că aceste aspecte sunt, în parte, independente unele de altele. O topologie liniară poate utiliza mai multe metode de acces diferite, cu mai multe moduri de transmisiune și medii de comunicație. Pe de altă parte, pot fi întâlnite frecvent rețele locale cu o structură hibridă, combinând topologii și mecanisme de acces diferite pe aceeași rețea.
Arhitectura unei LAN este definită de două componente:
topologie, caracterizând configurația căilor de transmisiune între sistemele interconectate;
repartizarea funcțiilor protocolului de comunicații, în particular toate sistemele îndeplinind aceleași funcții, sau unul având rol de coordonator și celelalte de subordonate.
Arhitectura rețelei determină următoarele caracteristici ale sale:
conectivitatea, adică posibilitățile pe care le are un sistem de a comunica împreună cu celelalte sisteme; conectivitatea este totală dacă fiecare sistem poate comunica cu oricare alt sistem din rețea;
difuziunea, adică posibilitatea de a se emite de la un sistem către ansamblul celorlalte sisteme din rețea;
reconfigurarea sau posibilitatea de introducere sau de retragere a unui sistem din rețea; aceste operații se pot face în afara sau în timpul funcționării rețelei, instantaneu sau cu întârziere;
siguranța funcționării, definită prin consecințele defectări unei căi de transmisiune sau a unui sistem asupra funcționării ansamblului rețelei.
Nici o arhitectură de sistem LAN disponibilă în prezent nu poate asigura în mod eficient, din punct de vedere economic, toate comunicațiile de la nivelul unei clădiri sau al unui campus universitar. Și nu este de presupus că un asemenea sistem se va dezvolta vreodată într-o asemenea măsură încât să îndeplinească, din punct de vedere economic, toate aceste cerințe. Astfel, va exista întotdeauna o cerință fie pentru sisteme independente care să rezolve aplicații specifice, fie pentru posibile sisteme hibride, care să beneficieze de cele mai performante caracteristici ale arhitecturilor individuale integrate în sistem.
Interconectarea mai multor rețele LAN:
Pentru conectarea fizică între calculatoare s-a folosit la început topologia de magistrală, la care pe segmentul de mediu fizic (cablu coaxial gros), se puteau conecta până la 29 de echipamente pe o lungime de maxim 500 m. Conectarea echipamentelor se făcea prin intermediul unui dispozitiv numit transceiver. Nu se mai realizează astăzi asemenea rețele, topologia de magistrală având un cablu coaxial subțire, iar conexiunile fiind făcute prin mufe T. Este vorba despre LAN-uri Ethernet. Numele Ethernet este legat de ipoteza vehiculată mult timp de oamenii de știință, potrivit căreia între corpurile cerești se află zone "umplute" de un "gaz" misterios numit eter. Creatorul Ethernetului și-a imaginat o rețea în care nu este important unde se află calculatoarele, ci faptul că acestea pot comunica fără restricții și a ales, metaforic vorbind, eterul ca mediu de comunicație.
Rețeaua Ethernet a fost dezvoltată de Robert Metcalfe în 1973, pe vremea când era angajat al companiei Xerox și a evoluat continuu, devenind cel mai popular tip de rețea locală. Primele rețele Ethernet au fost cele cu cablu coaxial gros și legătura prin transceivere, numite Thick Ethernet. Astăzi se folosește cablul coaxial subțire cu conexiuni T (Thin Ethernet), cablu torsadat sau fibra optică (Twisted Pair Ethernet, Fast Ethernet). Conexiunea cu mufe T are avantajul eliminării transceiverului, mufa conectându-se direct la placa de rețea, "coada" T-ului, cablul continuând prin extremitățile T-ului către calculatorul următor. Cea mai populară versiune Ethernet avea o viteza de transmisie a datelor de 10 Mb/s, iar Fast Ethernet de 100Mb/s. Se lucrează astăzi pentru realizarea unor rețele cu viteză de transfer mai mare de 1000 Mb/s, numele vehiculat pentru acestea fiind Gb Ethernet.
Celelalte topologii, inel (ring) și stea (star) sunt mai puțin răspândite la noi (proprietățile lor vor fi studiate într-un subcapitol următor). Topologia inel a fost utilizată de IBM pentru tipul de rețea Token Ring, folosită astăzi doar pentru conectări rapide la mare distanță cu fibră optică. Topologia stea s-a folosit în rețelele Arcnet, unde conectările erau făcute la un hub, în stea, fiind posibile și conexiuni între hub-uri. Hub-ul (Host Unit Broadcast) este un dispozitiv în care intră un singur cablu și care are mai multe ieșiri.
Rețelele locale, indiferent de tipul lor, stabilesc o limită maximă a numărului echipamentelor ce se pot conecta la rețea. Atunci când este nevoie de conectarea mai multor calculatoare decât permite tipul de rețea utilizat sau atunci când avem mai multe rețele locale, eventual de tipuri diferite, pe care dorim să le conectăm exista două soluții: repetoarele și podurile. Un repetor (REPEATER) este un amplificator electric, care preia semnalul dintr-o parte și îl trece în cealaltă parte, mărind puterea acestuia (semnalul se pierde dacă nu este amplificat). Repetorul nu poate fi folosit decât pentru legarea a două rețele de același tip, iar folosirea unui număr mare de repetoare duce la scăderea vitezei de transmisie a datelor.
Atunci când dorim să conectăm două rețele, mai ales dacă sunt de tipuri diferite, vom utiliza un pod (BRIDGE). Acesta este conectat la două sau mai multe rețele locale, simultan. Podul știe să preia pachetele de date dintr-o rețea și să le transmită în cealaltă, realizând și anumite conversii ale pachetelor (pachetul de date ce "trece pe pod" va trebui "înțeles" de calculatoarele din rețeaua destinație, deci vor trebui făcute conversiile de structură; fiecare tip de rețea folosește pachete diferite ca structură, deci, de exemplu, un pachet Ethernet nu va fi "înțeles" de o rețea Token Ring). Se spune ca un pod "vorbește" cu un protocol diferit la fiecare capăt (regulile de transmisie a datelor sunt diferite de la o rețea la alta). Podul nu copiază un pachet dintr-o parte în alta decât dacă destinația sa se află în altă rețea decât calculatorul care l-a expediat, prevenind aglomerarea inutilă a rețelei. Există și poduri care au un algoritm care le permite să învețe când să preia un pachet și când nu (algoritm de învățare).
Rețele metropolitane (Metropolitan Area Network): reprezintă artere de debit ridicat, realizate cu fibre optice și destinate interconectării sistemelor (ordinatoare sau LAN-uri), care se pot întinde pe o distanță maximă de zeci de kilometrii, într-o zonă de pe suprafața unui întreg oraș.
Pentru conectare se folosesc două cabluri unidirecționale la care sunt conectate toate calculatoarele, fiecare cablu având un capăt de distribuție (dispozitiv care inițiază activitatea de transmisie); pe lângă transmisia de date, permite și transmisia de voce și chiar legături cu rețeaua locală de televiziune prin cablu.
Avantajele unei MAN sunt:
interconectare la mare viteză;
securitate ridicată pentru informația transportată;
serviciu de înaltă calitate;
preț competitiv;
– “autovindecare” în caz de defecțiune, datorită căilor redundante;
înaltă disponibilitate;
flexibilitate.
Rețele larg răspândite geografic (Wide Area Network): rețele care ocupă arii geografice întinse, ajungând la dimensiunea unei țări sau a unui întreg continent, nodurile acesteia numindu-se gazde; aceste gazde sunt conectate prin intermediul unei subrețele de comunicație, care este la rândul ei compusă din linii de transmisie și elemente de comutare.
Tehnicile de racordare, de transmisie (inclusiv sateliții), vitezele de lucru, modurile de funcționare și de gestiune diferă mult de cele ale rețelelor LAN. Ele pun în aplicare tehnici de comutare pentru a stabili legături – fizice sau logice – care conectează între ele două sisteme. Evoluția tehnologiei a favorizat apariția Rețelelor Numerice cu Integrarea Serviciilor (ISDN = Integrated System Digital Network) al căror obiectiv este de a transmite simultan, pe unul și același suport fizic, vocea, textele, date, imagini fixe sau animate, în alb-negru sau în culori. Această rețea multimedia va putea fi folosită de un terminal multifuncțional care să ofere, în același timp, posibilități de dialog cu un interlocutor (îndepărtat sau nu), de vizualizare a personajelor și de transmisie simultană de imagini, texte și date.
Rețeaua “Internet”: reprezintă cea mai mare rețea existentă în prezent, la care sunt conectate zeci de mii de LAN-uri, zeci de milioane de utilizatori, mărimea ei dublându-se la fiecare doi ani, dar să privim puțin în istoria acestei rețele.
Istoria Internetului, deși sub acest nume va apărea mult mai târziu, începe în 1966, odată cu crearea Agenției pentru Proiecte de Cercetare Avansată (ARPA). Obiectivul agenției era crearea unei rețele de comandă a trupelor SUA, care să poată rămâne operațională chiar și în cazul unui atac nuclear. Au fost examinate numeroase posibilități, însă recomandarea finală era aceea de a pune bazele unei rețele cu comutare de “pachete”. Rețeaua a fost denumită ARPAnet și a fost operațională în 1969, când lega 4 calculatoare de mare capacitate și putere din laboratoarele unor universități (Universitatea di Los Angeles, Universitatea Stanford – California, Universitatea din Santa Barbara – California și Universitatea din Utah). Debitul rețelei era de 50 kbiți/s și nimeni nu bănuia că acesta era momentul nașterii a ceea ce urma să se numească INTERNET.
Agenția ARPA a finanțat proiecte de cercetare în domeniul rețelelor ale universităților americane, pe baza cărora s-a dezvoltat rețeaua. Realizarea "practică" a rețelei a fost încredințată firmei BBN (construcția subrețelei de comunicație). S-a hotărât ca subrețeaua să aibă ca routere minicalculatoare IMP Honeywell DDP-316 special modificate (memorie de 12 KB, cuvânt de 16 biți, fără discuri mobile considerate nesigure), conectate prin linii telefonice de 56 Kbps închiriate de la diverse firme de telefoane. Fiecare nod al rețelei era format dintr-un calculator gazdă și un IMP (Interface Message Processors) aflate în aceeași încăpere. Pentru a spori siguranța comunicării, fiecare IMP era conectat cu alte două.
În anii ’70 a fost dezvoltat protocolul de comunicații TCP/IP (Transmission Control Protocol/Internet Protocol), care a devenit ulterior protocolul de interconectare a rețelelor standard, iar rețeaua avea mai mult de 100 de computere. În deceniul următor rețeaua a început să se diversifice trecând dincolo de 250.000 de computere interconectate și aceasta datorită apariției PC-urilor. În 1983, ARPAnet a fost divizată în două sisteme distincte: MILNET (rețea destinată operațiunilor militare) și ARPAnet.
Rețeaua ARPAnet a arătat cercetătorilor cât este de utilă comunicarea rapidă între echipele de cercetători aflate în diverse orașe ale SUA și s-a dorit conectarea cât mai multor universități. Procedura de conectare era restrictivă deoarece rețeaua ARPAnet era finanțată de ARPA (adică, pe scurt, de Pentagon). La sfârșitul anilor '70, din inițiativa Fundației Naționale de Știința (NSF), a demarat proiectul de conectare a universităților care nu aveau contract de colaborare cu ARPA. Inițial au fost oferite servicii de poștă electronică. În 1986 a fost creată o subrețea care conecta șase centre de supercalculatoare din șase orașe americane, fiecare supercalculator conectat fiind legat de un minicalculator LSI-11 (FUZZBALL), numit și "fratele mai mic". Fuzzball-urile au format subrețeaua la care au fost conectate, în timp, 20 de rețele regionale. Rețeaua a fost denumită NSFNET (National Science Foundation).
La mijlocul anilor '80, rețelele ARPAnet și NSFNET au "fuzionat" și, odată cu mărirea exponențială a numărului cererilor de conectare, lumea a început să perceapă colecția de rețele ca fiind o uriașă conexiune de rețele. Putem spune că este momentul nașterii rețelei Internet. Aceasta cuprindea, în 1990, 3000 de rețele și 200 000 gazde pentru a ajunge astăzi la câteva zeci de mii de LAN-uri și milioane de gazde. Expansiunea spectaculoasă a rețelei a început în 1992, după ridicarea interdicției de a desfășura activități comerciale pe Internet și odată cu apariția World Wide Web care exploatează tehnologia “hypertext” dezvoltată la institutul CERN (Centre Européen pour la Recherche Nucléaire). În 1993 debitul rețelei trece la 45 Mbit/s, iar rețeaua numără deja peste 1 milion de computere, iar în 1994 viteza crește la 155 Mbiți/s utilizând modul de transfer asincron (ATM). La 24 octombrie 1995 Federal Networking Council (FNC) adopta în unanimitate rezoluția care definea termenul de INTERNET: “Termenul INTERNET desemnează un sistem de comunicații global care (i) este unificat printr-un spațiu de adresare unic la scară mondială, bazat pe protocolul IP (Internet) sau extensiile/succesorii săi ulteriori, (ii) permite comunicațiile cu ajutorul protocoalelor TCP/IP sau ale extensiilor/succesorilor săi ulteriori, sau al altor protocoale compatibile cu IP și (iii) furnizează, utilizează sau face (public sau particular) accesibile serviciile evoluate suprapuse comunicațiilor și infrastructurii corespunzătoare.”
La sfârșitul anului 1996 erau conectate la rețeaua Internet peste 25 milioane computere, iar creșterea se accelerează pe zi ce trece. De aceea una dintre activitățile profitabile este aceea de furnizor Internet (Internet provider = firma care oferă servicii de conectare la Internet).
1.2.2 Structura unei rețele de date
O rețea de date, după cum este prezentată și în figura următoare, se compune din următoarele elemente:
Echipamente terminale de date (Data Terminal Equipment): reprezintă noduri și stații care aparțin utilizatorului și sunt conectate cu DCE (= Data Communication Equipment) prin intermediul unei interfețe standard;
Subrețeaua de comunicații;
Interfețele (Data – Circuit Terminating Equipment) aparțin subrețelei de comunicații și reprezintă sfârșitul circuitelor.
Fig. 1.2 Structura unei rețele de date
Echipamentele terminale pot fi de intrare, de ieșire și de prelucrare. Pentru a putea prelucra o diversitate practic infinită de informații, acestea sunt traduse din forma lor inițială în fluxuri de date, prin intermediul terminalelor de intrare, transformarea inversă (a datelor în informații) realizându-se prin intermediul terminalelor de ieșire. Datele pot fi atât sub formă analogică, cât și sub formă digitală.
Subrețeaua de comunicații are ca rol esențial transmiterea datelor între două sau mai multe puncte, acest lucru realizându-se transparent din punct de vedere al informației, fără să intereseze informațiile transportate de unitățile de date. Pentru aceasta, datele trebuie să se prezinte sub forma unor semnale electrice adecvate mediului prin care urmează a fi transmise. Dacă se dorește transpunerea datelor sub formă de semnale optice sau de unde electromagnetice, inițial se transpun datele în semnal electric și apoi acestea se transpun în formă finală.
Interfețele dintre terminale și subrețeaua de comunicații reprezintă cea de-a treia componentă a rețelelor de date, cu rolul de a transforma datele în semnale electrice. În cea mai mare parte a situațiilor, interfața este un modem, care poartă diferite denumiri, în funcție de tipul datelor (analogic sau digital) și de tipul semnalelor electrice, astfel:
modem pentru conversia datelor digitale în semnal analogic;
coder pentru conversia datelor analogice în semnal digital;
coder pentru conversia datelor digitale în semnal analogic.
Avantajele rețelelor de date
Folosirea unei rețele de date oferă următoarele avantaje:
avantaje strategice pentru domeniul economic:
fiabilitate sporită – este oferită prin accesul la mai multe echipamente de stocare alternative (fișierele pot fi stocate de două–trei echipamente, asigurând accesul la date chiar dacă unul dintre echipamente se defectează);
extensibilitate – rețeaua se poate extinde ușor prin conectarea altor echipamente, iar realizarea unui up-grade într-o zonă a rețelei nu influențează funcționarea rețelei;
împărțirea resurselor – toate programele, datele și echipamentele sunt disponibile pentru orice utilizator al rețelei, indiferent de localizarea fizică a resursei sau a utilizatorului;
economie financiară – o rețea de calculatoare este mult mai fiabilă și mai ieftină decât un supercalculator;
mediu puternic de comunicație:
poștă electronică (e-mail);
videoconferințe;
divertisment interactiv, etc.
facilitarea comunicațiilor;
creșterea competitivității;
reducerea costului și a timpului de prelucrare a datelor;
creșterea dinamicii echipelor de lucru.
avantaje pentru utilizator:
accesul la informație de la distanță;
comunicațiile interpersonale;
divertismentul interactiv;
lărgirea gamei de aplicații puse la dispoziția acestuia;
creșterea flexibilității;
utilizarea simplificată prin intermediul interfețelor grafice.
avantaje tactice și operaționale:
îmbunătățirea integrității datelor;
fiabilitatea ridicată prin intermediul utilizării rezervelor.
alte avantaje:
pe scară politică;
pe scară socială, etc.
Parametrii de performanță ai rețelelor de date
Parametrii cei mai importanți prin intermediul cărora se poate aprecia performanța unei rețele de date sunt următorii:
probabilitatea de sistem deschis;
viteza de transmisie;
probabilitatea de eroare;
fiabilitatea și disponibilitatea;
timpul de întârziere.
Probabilitatea de sistem deschis se manifestă în modul următor: legătura între două sisteme de comunicație se poate realiza eficient dacă ambele respectă atât modelul de referință privind împărțirea în niveluri, cât și suita de protocoale asociate. Astfel se stabilește comunicația logică între nivelurile de același rang
din cadrul celor două sisteme. Această comunicație logică se realizează în conformitate cu un set precis de reguli și convenții numit protocol. Deoarece două niveluri de același rang aparținând a două sisteme diferite pot comunica logic prin mai multe protocoale, s-au creat pe baza modelului arhitectural suite de protocoale. Datorită faptului că acest parametru are un rol important în ceea ce privește performanțele sistemelor de comunicații, în cadrul unui punct următor al prezentului capitol va fi prezentată pe larg structura sistemului deschis.
Viteza de transmisie reprezintă volumul de date ce poate fi transmis în unitatea de timp. În funcție de modul de considerare al biților transmiși, acest parametru are mai multe definiții. La măsurarea vitezei de transmisie sunt luați în calcul și biții de control introduși de sistemul de comunicații.
Probabilitatea de eroare reprezintă calitatea aproximării datelor transmise cu cele recepționate, prin probabilitatea recepționării eronate a unui bit de informație, sau prin probabilitatea recepționării eronate a unui mesaj.
Fiabilitatea reprezintă proprietatea echipamentelor tehnice și a structurii organizatorice adoptate de a îndeplini, în condiții optime, cerințele impuse rețelei respective. Realizarea unei rețele de date cu fiabilitate ridicată constituie un obiectiv principal al activităților de planificare și organizare. Ideal, fiabilitatea presupune funcționarea în continuu a echipamentelor la parametrii stabiliți, dar în realitate ea este dată de timpul mediu de funcționare (MTBF – Mean Time Between Failure) și timpul mediu de reparare (MTTR – Mean Time To Repair).
Disponibilitatea reprezintă un parametru efect al fiabilității, care reprezintă timpul în care un echipament este funcțional în unitatea de timp.
Timpul de întârziere se poate măsura în mai multe moduri, dar, conform celui fizic, acesta reprezintă durata după care primul bit ce părăsește sursa se regăsește la destinație.
1.3 Modelul arhitectural ISO – OSI
1.3.1. Necesitatea standardizării în cadrul rețelelor de date
În cadrul perioadei de început rețelele de date s-au dezvoltat independent, interconectarea lor fiind foarte dificilă, uneori chiar imposibilă, deoarece fiecare arhitectură de rețea folosea diferite formate ale datelor și diferite convenții de comunicație. Extinderea din ultima vreme a rețelelor informatice la scară națională și internațională i-a luat prin surprindere și pe cei care se ocupau de concepția lor tehnică.
Încetul cu încetul s-a împământenit noțiunea de eterogenitate, altfel spus, asocierea într-o singură rețea, de hardware și software provenind de la o mulțime de furnizori. Pentru interconectarea echipamentelor provenite de la diferiți producători s-a convenit adoptarea unui set comun de convenții, acest lucru presupunând elaborarea și adoptarea de către organizații specializate a unor standarde internaționale, sau cel puțin naționale.
Odată cu apariția unei noi tehnologii, se manifestă și un fenomen de proliferare a produselor ce utilizează tehnologia respectivă, fiecare producător dorind să impună pe piață propria realizare (mai bună sau mai puțin bună decât altele). După un anumit timp, piața realizează o "selecție naturală", rămânând în competiție doar produsele de calitate. Acest interval de timp duce la "maturizarea" tehnologiei respective și reprezintă un test al utilității ei. Urmează interminabile discuții și controverse între firmele combatante, iar o comisie internațională încearcă să stabilească un set de reguli și convenții obligatorii pentru toți cei ce dezvoltă produse bazate pe tehnologia în discuție. Astfel se naște un standard. "Fizic", standardul se prezintă sub forma unui "metru cub" de documentație, prea puțin accesibilă omului de rând, continuând recomandări pe care nu toți le respectă. Standardul este important pentru unificarea diverselor variante ale tehnologiei respective și definește un set de reguli generale, universal acceptate, contribuind la apariția de produse portabile.
Acest considerabil efort este realizat, de o bună bucată de vreme, prin intermediul a numeroase organisme care cooperează pe plan internațional. Standardele sunt aprobate de organizații internaționale, cum ar fi: ECMA (European Computer Manufacturer's Association), IEEE (Institute of Electrical and Electronical Engineers), ANSI (Amaerican National Standards Institute). Una din cele mai importante organizații în procesul de standardizare este ISO (International Standard Organization), pentru care calitatea de membru este voluntară și care are în componența sa câteva organizații de standardizare mai importante din fiecare țară. Pentru România, membru ISO este IRS (Institutul Român de Standardizare). Deși ISO nu impune, ci doar recomandă respectarea standardelor aprobate de ea, acestea au căpătat putere de lege.
1.3.2. Structura Modelului de Referință OSI
Elaborarea standardelor pentru rețele a devenit necesară datorită diversificării echipamentelor și serviciilor, care a condus la apariția de rețele eterogene din punctul de vedere al tipurilor de echipamente folosite. În plus, multitudinea de medii fizice de comunicație a contribuit la decizia de a defini reguli precise pentru interconectarea sistemelor. În 1983, după șase ani de eforturi intense, ISO a publicat un îndrumar – un model de referință – care
descrie arhitecturile sistemelor de comunicație a datelor. Documentul rezultat, Standardul Internațional #7498, a fost redactat din nou de către ITU-T, care a introdus propria terminologie, iar acest proiect a fost intitulat ITU-T X.200. numele generic al ambelor documente este cunoscut sub denumirea de Modelul de referință pentru Interconectarea Sistemelor Deschise (Open Systems Interconnection Reference Model – OSI/RM), pe scurt OSI.
O tehnică larg acceptată de descompunere în probleme o reprezintă structurarea pe niveluri. Funcțiile de comunicație sunt realizate printr-un set ierarhic de niveluri, fiecare nivel realizând un subset de funcții necesare comunicării cu un alt sistem. Această structurare trebuie făcută astfel încât să se îndeplinească în special condițiile următoare:
schimbările necesare în cadrul unui nivel să nu afecteze celelalte niveluri;
partiționarea pe niveluri trebuie să grupeze logic funcțiile într-un număr nici prea mare de niveluri, pentru a nu deveni dificil de procesat, dar nici prea mic, pentru a asigura independența grupurilor logice de funcții de comunicație.
Legătura între două sisteme de comunicație se realizează practic prin comunicația logică ce se stabilește între nivelurile de același rang din cadrul celor două sisteme. Această comunicație logică se realizează în conformitate cu un set precis de reguli și convenții numit, după cum am mai amintit, protocol. Deoarece două niveluri de același rang din sisteme diferite pot comunica logic prin mai multe protocoale, s-au creat pe baza modelului arhitectural suite de protocoale.
Două sisteme se pot interconecta direct dacă respectă atât modelul de referință privind împărțirea în niveluri, cât și suita de protocoale asociată. Modelul de referință nu garantează posibilitatea interconectării sistemelor, ci creează mediul necesar elaborării unor seturi de standarde. Sistemele ce implementează suite de protocoale diferite se pot interconecta prin intermediul echipamentelor de adaptare de genul punților, ruterelor sau porților.
Elementele acestui model sunt:
sistemul: reprezintă unul sau mai multe calculatoare cu toate perifericele, terminalele, procesele de aplicație și software-ul asociat, dar și operatorul uman;
entitatea aplicație: reprezintă o parte a procesului de aplicație care are rol hotărâtor în cadrul cooperării, ea fiind asociată cu noțiunea de nivel; entitățile din cadrul nivelelor de același rang comunică și cooperează între ele. Entitățile creează unități funcționale care realizează serviciile pentru entitățile corespunzătoare nivelurilor superioare;
conectarea: asigură realizarea asocierii între entitățile aplicație;
mediu de interconectare fizic: reprezintă modelul mediului real care permite transmiterea semnalelor și mesajelor.
Fig. 1.3 Elementele componente ale Modelului de Referință
Modelul ISO-OSI împarte arhitectura rețelei în șapte nivele, construite unul deasupra altuia, adăugând funcționalitate serviciilor oferite de nivelul inferior. Modelul nu precizează cum se construiesc nivelele, dar insistă asupra serviciilor oferite de fiecare și specifică modul de comunicare între nivele prin intermediul interfețelor. Fiecare producător poate construi nivelele așa cum dorește, însă fiecare nivel trebuie să furnizeze un anumit set de servicii. Proiectarea arhitecturii pe nivele determină extinderea sau îmbunătățirea facilă a sistemului. De exemplu, schimbarea mediului de comunicație nu determină decât modificarea nivelului fizic, lăsând intacte celelalte nivele.
Fig. 1.4 Structura pe nivele a Modelului de Referință
În cele ce urmează vor prezentate câteva aspecte despre fiecare nivel:
Nivelul fizic: are rolul de a transmite datele de la un calculator la altul prin intermediul unui mediu de comunicație (electric, optic, etc.) sub forma unor secvențe de biți. Nivelul fizic trebuie astfel conceput încât biții transmiși de la un capăt al conexiunii fizice să fie recunoscuți ca atare la celălalt capăt. Problemele tipice, deci, sunt de natură electrică: nivelele de tensiune corespunzătoare unui bit 1 sau 0, durata impulsurilor de tensiune, cum se inițiază și cum se oprește transmiterea semnalelor electrice, asigurarea păstrării formei semnalului propagat.
Nivelul legăturii de date: asigură transferul de date prin legătura fizică, transmiterea blocurilor de date cu sincronizarea necesară, dar și controlarea fluxului și al erorilor de transmitere apărute la nivelul fizic, realizând o comunicare corectă între două noduri adiacente ale rețelei. Sarcina principală a nivelului legătură de date este de a prelua un mijloc de transmisiune “brut” (cel fizic) și a-l transforma într-o cale de comunicație ce pare, pentru nivelul rețea, scutită de erori. El realizează această funcțiune prin formatarea datelor de transmis sub forma unor cadre de câteva sute de octeți (frame), prin transmiterea cadrelor în succesiune și administrarea cadrelor de confirmare transmise de receptor. Cadrele sunt transmise individual, putând fi verificate și confirmate de către receptor. Alte funcții ale nivelului se referă la fluxul de date (astfel încât transmițătorul să nu furnizeze date mai rapid decât le poate accepta receptorul) și la gestiunea legăturii (stabilirea conexiunii, controlul schimbului de date și desființarea conexiunii).
Nivelul rețea: asigură dirijarea unităților de date între nodurile sursă și destinație, trecând eventual prin noduri intermediare (routing), deci acest nivel de fapt asigură transferul transparent al datelor, selectează calea potrivită și rutează datele pe calea selectată. Este foarte important ca fluxul de date să fie astfel dirijat încât să se evite aglomerarea anumitor zone ale rețelei (congestionare). Interconectarea rețelelor cu arhitecturi diferite este o funcție a nivelului rețea, deci, acest nivel asigură entităților de transport independența față de problemele de rutare legate de stabilirea și funcționarea oricărei conexiuni de rețea, inclusiv în cazul în care sunt utilizate în tandem mai multe subrețele. Acest nivel conține funcțiunile necesare pentru a masca (pentru nivelul transport) diferențele dintre caracteristicile diferitelor tehnologii de transmisiune și de subrețele, asigurând un serviciu de rețea coerent. Entitățile de transport se identifică prin adresele de rețea, care, de fapt identifică în mod unic fiecare sistem (de extremitate).
Nivelul transport: realizează o conexiune între două calculatoare gazdă (host), detectând și corectând erorile pe care nivelul rețea nu le tratează. Este nivelul aflat în mijlocul ierarhiei, asigurând nivelelor superioare o interfață independentă de tipul rețelei utilizate. Funcțiile principale sunt: stabilirea unei conexiuni sigure între două mașini gazdă, inițierea transferului, controlul fluxului de date și închiderea conexiunii. În plus, el optimizează utilizarea serviciului rețea disponibil, pentru a asigura cu un cost minim, performanța cerută de fiecare entitate sesiune. Conexiunea tipică de transport constă într-o legătură punct-la-punct, asigurând sosirea la destinație a mesajelor în ordinea în care au fost retransmise.
Nivelul sesiune: stabilește și întreține conexiuni (sesiuni) între procesele aplicație, rolul său fiind acela de a permite proceselor să stabilească "de comun acord" caracteristicile dialogului și să sincronizeze acest dialog. Acest nivel definește trei tipuri de dialoguri: bidirecțional simultan (duplex), bidirecțional alternant (semiduplex) și unidirecțional (simplex). Serviciile nivelului sesiune include stabilirea unor puncte de sincronizare în cadrul dialogului, permițând întreruperea unui dialog și reluarea lui de la un punct de sincronizare.
Nivelul prezentare: realizează operații de transformare a datelor în formate înțelese de entitățile ce intervin într-o conexiune. Transferul de date între mașini de tipuri diferite (Unix-DOS, de exemplu) necesită și codificarea datelor în funcție de caracteristicile acestora. Nivelul prezentare ar trebui să ofere și servicii de criptare/decriptare a datelor, în vederea asigurării securității comunicației în rețea.
Nivelul aplicație: are rolul de "fereastră" de comunicație între utilizatori, aceștia fiind reprezentați de entitățile aplicație (programele). Nivelul aplicație nu comunică cu aplicațiile, ci controlează mediul în care se execută aplicațiile, punându-le la dispoziție servicii de comunicație. Printre funcțiile nivelului aplicație se află:
identificarea partenerilor de comunicație, determinarea disponibilității acestora și autentificarea lor;
sincronizarea aplicațiilor cooperante și selectarea modului de dialog;
stabilirea responsabilităților pentru tratarea erorilor;
identificarea constrângerilor asupra reprezentării datelor;
transferul informației.
Nivelele inferioare sunt considerate: nivelul fizic, nivelul legăturii de date, nivelul rețea și nivelul transport. Din cadrul nivelelor superioare fac parte:
nivelul sesiune, nivelul prezentare și nivelul aplicație. Primele trei niveluri de la baza ierarhiei (fizic, legătura de date, rețea) sunt considerate ca formând o subrețea de comunicație. Subrețeaua este răspunzătoare pentru realizarea transferului efectiv al datelor, pentru verificarea corectitudinii transmisiei și pentru dirijarea fluxului de date prin diversele noduri ale rețelei. Acest termen trebuie înțeles ca desemnând "subrețeaua logică", adică mulțimea protocoalelor de la fiecare nivel care realizează funcțiile de mai sus. Termenul de subrețea este utilizat și pentru a desemna liniile de transmisie și echipamentele fizice care realizează dirijarea și controlul transmisiei.
Modelul OSI nu este implementat în întregime de producători, nivelele sesiune și prezentare putând să lipsească (unele din funcțiile atribuite acestora în modelul OSI sunt îndeplinite de alte nivele). Modelul OSI este un model orientativ, strict teoretic, realizările practice fiind mai mult sau mai puțin diferite. Evident, cineva va putea întreba, de ce ne interesează atât de mult un model teoretic? Motivul este simplu: înțelegerea unui alt model este mult ușurată de studierea modelului ISO-OSI, motiv pentru care orice lucrare de specialitate serioasă îl prezintă detaliat.
În determinarea celor șapte nivele s-au avut în vedere mai multe principii, ca de exemplu:
să se creeze o frontieră (între două niveluri) acolo unde descrierea serviciilor poate fi concisă și numărul interacțiunilor la traversarea acestei frontiere este minim;
să se creeze nivele separate pentru funcțiuni care diferă prin prelucrarea efectuată sau prin tehnologia utilizată;
să se regrupeze funcțiuni similare în același nivel;
să se creeze un nivel acolo unde este nevoie să se distingă o modalitate de administrare a datelor (morfologică, sintactică, semantică);
să fie posibilă efectuarea de modificări ale funcțiilor sau protocolului fără a afecta alte nivele;
pentru fiecare nivel să se creeze frontiere numai cu nivelul imediat inferior și cel imediat superior.
Totodată s-a ținut seama și de următoarele considerente:
– deoarece este esențial ca arhitectura rețelei să permită utilizarea unei varietăți realiste de medii fizice de interconexiune, asociate cu diferite proceduri de control, s-a ales nivelul fizic spre a fi cel mai de jos nivel al arhitecturii;
– unele suporturi fizice de comunicații necesită folosirea de tehnici particulare pentru a transmite datele între sisteme, deoarece prezintă un procent de erori mare, inacceptabil pentru majoritatea aplicațiilor, aceste tehnici particulare fiind utilizate în procedurile de control al legăturii de date. Trebuie de asemenea să se țină seamă că noile suporturi fizice de comunicații, cum ar fi fibrele optice, vor necesita alte proceduri pentru controlul legăturilor. Aceste considerente au dus la identificarea unui nivel legătură de date, deasupra nivelului fizic al arhitecturii;
– nivelul legătură de date asigură o conexiune numai între noduri adiacente ale rețelei; pentru a stabili o conexiune cap-la-cap între terminale este nevoie de nivelul rețea care să grupeze protocoalele de rutare. Nivelul rețea furnizează astfel o conexiune între entitățile de transport, incluzând cazurile când intervin și noduri intermediare;
– controlul transportului datelor de la un sistem de extremitate, sursă, la un sistem de extremitate, destinație, control care nu se face în nodurile intermediare, este ultima funcțiune care trebuie realizată pentru a furniza integral serviciul transport. Nivelul de mai sus al părții care asigură serviciul de transport al arhitecturii este, deci, nivelul transport. Acest nivel eliberează entitățile nivelelor superioare de orice problemă privind transportul datelor între ele;
– deși nivelul transport poate furniza o conexiune cap-la-cap fără erori (virtual), asigurând retransmiterea informației eronate sau pierdute, informația poate fi pierdută în terminale datorită suprasaturării memoriilor. Mai mult, unele aplicații pot necesita ca fluxul de informații între terminale să fie unidirecțional, bidirecțional alternant sau bidirecțional simultan. Nivelul sesiune va furniza această funcționalitate prin utilizarea punctelor de sincronizare și a jetoanelor. Punctele de sincronizare sunt inserate în fluxul informației la cererea entităților de aplicație și, dacă este necesar, fluxul informației poate fi reluat de la un punct de sincronizare anterior;
– funcțiunile privind reprezentarea și manipularea datelor structurate pentru scopul programelor de aplicație au fost incluse în nivelul prezentare, aflat deasupra nivelului sesiune;
– nivelul aplicație, cel mai de sus al arhitecturii, constituind unul din aspectele proceselor de aplicație, conține protocoalele care le servesc pentru a comunica.
Exemplu:
Un transfer de date între două mașini gazdă se poate realiza astfel: cel mai bun exemplu este modul în care putem citi o pagină web aflată pe un calculator situat la mare distanță:
utilizatorul lansează un program pentru vizualizarea paginilor web (browser);
browserul este entitatea aplicație care va "negocia" pentru noi obținerea paginii;
nivelul aplicație va identifica existența resursei cerute de client (clientul este browserul, care-l reprezintă pe utilizator în aceasta "tranzacție") și a posesorului acesteia (serverul, înțeles ca fiind entitatea ce oferă resursa cerută nu calculatorul central al unei rețele; în cazul nostru avem de-a face cu un server de web). Se realizează autentificarea serverului (se verifică dacă partenerul este într-adevăr cine pretinde că este) și se stabilește dacă acesta este disponibil (adică dacă poate și vrea sa ne satisfacă cererea);
nivelul sesiune va stabili o conexiune între procesul client și procesul server;
nivelul transport se va ocupa de întreținerea conexiunii și de corectarea erorilor netratate la nivelul rețea;
nivelul rețea va asigura transferul datelor în secvențe (pachete), stabilind drumul acestora între server și client;
În realitate, lucrurile sunt ceva mai complicate decât în cele prezentate în exemplul anterior. Datele sosesc prin intermediul mediului de comunicație ca un flux de biți. La nivelul legăturii de date, biții sunt transformați în cadre, iar la nivelul rețea în pachete. În cele din urmă, datele ajung la nivelul aplicație unde sunt preluate de browser și ne sunt prezentate. Fiecare nivel adaugă sau șterge o parte din informațiile de control atașate datelor de celelalte nivele.
1.3.3. Funcțiile caracteristice nivelelor
Funcțiile asociate sistemului sunt împărțite în două părți:
funcții de comunicație;
funcții de procesare a datelor.
Distincția principală este aceea că funcțiile de comunicație în cadrul nivelelor inferioare realizează în cea mai mare parte comunicația datelor, în timp ce în cazul nivelelor superioare se desfășoară cu precădere procesarea datelor.
În figura următoare sunt prezentate ponderile funcțiilor de comunicație și de procesare în cadrul fiecărui nivel:
Fig. 1.5 Ponderile funcțiilor de comunicație și de procesare
în cadrul fiecărui nivel
Principalele funcții caracteristice celor șapte nivele ale Modelului de Referință sunt redate sugestiv prin intermediul figurii de mai jos:
Fig. 1.6 Funcțiile caracteristice fiecărui nivel în parte
Funcționarea sistemelor de comunicație
bazate pe OSI RM
Funcționarea unui sistem de comunicații cu arhitectură multinivel se bazează pe legăturile dintre nivele, concretizate în solicitarea de servicii de la nivelul adiacent inferior și furnizarea de servicii către nivelul adiacent superior.
Fiecare nivel din cadrul Modelului de Referință este compus din aceleași tipuri de elemente. Conceptul multinivel este prezentat în cadrul figurii ce urmează, în care elementele caracteristice fiecărui nivel (în cazul nostru fiind vorba de nivelul N) sunt următoarele:
entitățile (N): reprezintă unități funcționale în cadrul fiecărui nivel care desăvârșesc serviciile (N-1) furnizate de către nivelul (N-1) și le adaugă la serviciile (N), ansamblul lor fiind furnizat nivelului (N+1) prin intermediul SAP (Service Acces Point). Entitățile reprezintă implementări ale protocoalelor sau funcțiilor de comunicație;
protocoalele (N): definesc și controlează regulile temporale, semantice și sintactice de cooperare între entitățile (N) pe baza serviciilor (N-1) și reprezintă conceptul fundamental în cadrul Modelului de Referință;
serviciile;
punctele de acces ale serviciilor (SAP): reprezintă interfețele prin care entitățile (N) comunică cu entitățile din cadrul nivelelor adiacente.
Fig. 1.7 Structura multinivel
Cea mai importantă cerință în cadrul rețelei de date este aceea de schimbare de informații între entitățile arhitecturii. Există trei tipuri de unități de date și anume:
unitate de date de protocol (PDU = Protocol Data Unit);
unitate de date de interfațare (IDU = Interface Data Unit);
unitate de date de serviciu (SDU = Service Data Unit).
→ PDU reprezintă informația schimbată între entitățile (N) de același rang din cadrul a două sisteme diferite și este compusă din două părți:
(N)–PDU = (N)–PCI + (N)–UD (1.2)
unde: (N)–PCI : reprezintă Protocol Control Information pe
nivelul (N) care coordonează schimbul de
informații între două entități (N) folosind
conectările (N-1);
(N)–UD : reprezintă User Data care este schimbată de
entitățile (N) între ele.
→ IDU reprezintă informația schimbată între entitățile de pe nivelele (N) și (N+1) de ranguri consecutive și este compusă din două părți:
(N)–IDU = (N)–ICI + (N)–ID (1.3)
unde: (N)–ICI : reprezintă Interface Control Information pe
nivelul (N) care coordonează schimbul de
informații între o entitate de pe nivelul (N)
și alta de pe nivelul (N+1);
(N)–ID : reprezintă Interface Data care este schimbată
între entitățile de pe nivelele (N) și (N+1).
Tabelul următor prezintă mai sugestiv tipul unităților de date schimbate între entități:
Fig. 1.8 Relațiile între unitățile de date
Informațiile schimbate între entitățile (N) și (N+1) se numesc (N)–SDU = Service Data Unit și sunt parametrii ai unui mesaj de tip ASP – Abstract Service Primitive. Conectarea logică între unitățile de date corespunzătoare nivelelor adiacente este prezentată în figura următoare:
Fig. 1.9 Conectarea logică între unități de date corespunzătoare
nivelelor adiacente
Modul în care se transmit datele între procesul emițător și cel receptor prin intermediul Modelului de Referință OSI este prezentat în figura ce urmează:
Fig. 1.10 Funcționarea OSI_RM
În cadrul figurii anterioare, datele emițătorului din primul sistem sunt furnizate ierarhic de la nivelul aplicație, prin intermediul celorlalte nivele, până la nivelul fizic, fiecare dintre aceste nivele atașând la ele un antet:
AH – (Application Header) = antetul corespunzător nivelului Aplicație;
PH – (Presentation Header) = antetul corespunzător nivelului Prezentare;
SH – (Session Header) = antetul corespunzător nivelului Sesiune;
TH – (Transport Header) = antetul corespunzător nivelului Transport;
NH – (Network Header) = antetul corespunzător nivelului Rețea.
Simultan, la sistemul emițător se derulează următoarele procese:
între nivelele Aplicație din cele două sisteme se stabilește o legătură logică printr-un protocol comun de nivel 7, protocol care este implementat de o entitate de pe nivelul Aplicație din fiecare sistem; entitatea (7) solicită servicii unei entități de pe nivelul Prezentare din cadrul aceluiași sistem printr-un SAP și îi trimite un mesaj SDU;
nivelul (6) adaugă propriile informații de control (6) PCI pentru a obține un mesaj (6) PDU pe care îl va comunica entității (6) din celălalt sistem printr-o legătură logică cu aceasta; pentru a realiza schimbul de (6) PDU, nivelul (6) solicită servicii nivelului (5) transmițându-i acestuia din urmă un mesaj (5) SDU printr-un (6) SAP;
procesele următoare decurg în aceeași manieră până la nivelul Fizic la care este posibilă în sfârșit comunicarea fizică între cele două sisteme; aici (1) PDU sunt schimbate între entități (1) corespondente prin intermediul unui mediu fizic de transmisie ghidat sau neghidat.
La sistemul receptor au loc procesele inverse, de la nivelul (1) până la nivelul (7), fiecare nivel extrăgând și verificând informațiile de control adăugate la emisie. Calea de comunicație ce se stabilește între cele două entități străbate pe rând toate nivelele primului sistem, mediul fizic și apoi toate nivelele celui de-al doi-lea sistem, în ordine inversă.
Capitolul II
CARACTERISTICILE PRINCIPALE
ALE REȚELELOR DE DATE
2.1 Prezentarea generală a caracteristicilor
C
aracteristicile principale ale rețelelor de date sunt următoarele:
mediul de transmisie: care poate fi de următoarele tipuri:
ghidat: cablu coaxial gros sau subțire, perechi de fire torsadate ecranate sau neecranate, fibră optică;
neghidat: atmosfera, spațiul cosmic.
topologia rețelei: stea (Star), inel (Ring), magistrală (Bus), arbore (Tree), etc.;
similaritatea sau nesimilaritatea nodurilor: rețele omogene sau eterogene;
schema de modulație în banda de bază (Base Band) sau prin curenți purtători (Carrier Band);
tipul de aplicații care rulează în cadrul rețelei respective;
numărul de noduri din cadrul rețelei respective;
distribuția geografică: locală, națională, multinațională;
controlul accesului la mediul de transmisie (MAC – Media Acces Control) (va face obiectul unui studiu separat).
Alegerea structurii rețelei, liniilor de comunicație și a echipamentelor ce urmează să fie folosite depinde de un număr de factori care derivă din considerațiile de securitate, fiabilitate și localizare a terminalelor.
Spațiul: reprezintă distanțele dintre dispozitivele de transmisie și recepție sau distribuția lor geografică;
Timpul: reprezintă timpul în care transmisia sau mesajul trebuie recepționat;
Cantitatea: reprezintă numărul de biți care sunt transmiși în cadrul unei singure transmisii.
În plus față de factorii fundamentali prezentați anterior mai există unii factori secundari, care au un rol aproximativ la fel de important, cum ar fi:
acuratețea transmisiei;
probabilitatea de eșec a liniei;
probabilitatea de obținere a semnalului de ocupat;
rata erorii;
disponibilitatea rețelei și a terminalelor.
Suplimentar, în cadrul rețelelor militare, disponibilitatea rețelei trebuie să aibă un grad înalt de siguranță în ceea ce privește obținerea accesului în punctul dorit, acest lucru putându-se obține prin creșterea conectivității acesteia, dar și prin duplicarea datelor care trebuie să fie accesate.
Topologie și arhitectură
Prin topologia unei rețele se înțelege modul de interconectare a calculatoarelor în rețea, definind structura rețelei. Există două părți ale definiției noțiunii de topologie:
cea fizică;
cea logică – care definește cum este accesat mediul de comunicații de către gazde.
Folosirea unei anumite topologii are influență asupra vitezei de transmitere a datelor, a costului de interconectare și a fiabilității rețelei.
Topologiile fizice cele mai folosite sunt: magistrală (Bus), inel (Ring), stea (Star), lanțul de stele (Extended Star), ierarhică (Hierarchical) și ochi (Mesh):
Fig. 2.1 Tipuri de topologii de rețele
Topologia magistrală: este cea mai folosită atunci când se realizează rețele locale de mici dimensiuni, iar performanțele nu trebuie să fie spectaculoase. Acest model topologic se mai numește și magistrală liniară, deoarece există un singur cablu care leagă toate calculatoarele din rețea. Topologia liniară reprezintă o conexiune multipunct, informațiile emise de un sistem fiind recepționate de toate celelalte sisteme, dar aceste informații sunt copiate și transmise către un nivel superior numai de sistemele care recunosc în adresa destinației propria lor adresă. Avantajul este atât acela al costului mai scăzut (se folosește mai puțin cablu), dar și acela că, în cazul ruperii unui cablu sau defectării unui calculator, nu se ajunge la oprirea întregii rețele. Dezavantajul folosirii unui singur cablu este că, atunci când dorește să transmită date, calculatorul trebuie să "lupte" pentru a câștiga accesul (trebuie să aștepte eliberarea cablului).
Topologia în inel: conectează fiecare calculator cu alte două, imaginea fiind aceea a unor calculatoare așezate în cerc. Fiecare sistem recepționează semnalul transmis pe buclă și-l retransmite mai departe, copiind mesajul dacă îi este destinat. Mesajul emis de un sistem (sursă) va fi retras din buclă de către același sistem atunci când îi va reveni după parcurgerea buclei. Dacă nu se folosesc cabluri suplimentare, oprirea unui calculator sau ruperea unui cablu duce la oprirea întregii rețele. Performantele unei rețele inel sunt ceva mai mari decât ale unei rețele magistrală.
Topologia stea: folosește un punct central la care se conectează toate celelalte calculatoare prin cabluri directe, acest punct fiind de obicei un HUB (Host Unit Broadcast) sau un swich (comutator), deci, orice comunicație între două sisteme trece prin nodul central. Dacă în punctul respectiv se folosește un calculator central de mare putere, atunci rețeaua va avea performanțe ridicate, însă defectarea acestuia duce la oprirea rețelei. Transferul informației se face punct-la-punct, dar, cu ultimele tipuri de comutatoare, este posibil și un transfer în legătură multipunct. Această topologie are și câteva dezavantaje, dintre care pot fi menționate: fiabilitatea rețelei depinde foarte mult de nodul central, o defectare a acestuia conducând la defectarea rețelei; este necesar un suport fizic de comunicație individual pentru fiecare sistem; existența rețelei este limitată la capacitatea nodului central.
Topologia lanț de stele: este o topologie combinată din mai multe topologii de tip stea.
Topologia ierarhică: reprezintă o topologie creată în mod similar cu “lanțul de stele”, numai că sistemul este legat la un computer care controlează traficul topologiei.
Topologia ochi: este folosită atunci când nu trebuie să existe absolut nici o întrerupere a comunicației, de exemplu controlul sistemelor nucleare. După cum se poate observa în figura care descrie tipurile de topologii, fiecare gazdă are propria conectare la toate celelalte gazde.
Orice topologie ar fi aleasă, există un număr de probleme ce trebuiesc rezolvate (modul de obținere a accesului este una dintre cele mai importante, trebuind eliminată posibilitatea ca un singur calculator sa "monopolizeze" mediul de transmisie). Apar probleme suplimentare atunci când rețeaua noastră este eterogenă (conectează diverse tipuri de calculatoare sau este formată din mai multe rețele diferite ca tip).
Trebuie, însă, să facem distincție între topologia fizică, despre care am discutat anterior și topologia logică.
Topologia logică a unei rețele reprezintă modul în care datele sunt transferate de la un calculator la altul prin intermediul mediului de transmisiune. Cele mai folosite topologii logice sunt:
Broadcast: fiecare gazdă trimite date la toate celelalte gazde din mediul rețelei; în acest caz nu există nici o ordine de servire, ci primul venit va fi primul servit (este modul de funcționare al rețelelor Ethernet);
Token-passing: controlează accesul în rețea prin trecerea unei cereri în mod secvențial pe la toate gazdele; când o gazdă răspunde la cerere, înseamnă că această gazdă poate trimite date în rețea, iar dacă nu are de trimis date, pasează cererea la următoarea gazdă, iar procesul se repetă de la sine.
Exemplu:
Fig. 2.2 Exemplu de topologie logică
Diagrama din graficul anterior prezintă un exemplu de mai multe topologii. Ea reprezintă o LAN cu o complexitate mai mică, tipică unei școli sau unei mici afaceri.
Arhitectura unei rețele reprezintă modul de interconectare a componentelor rețelei, pentru a realiza un anumit mod de funcționare. Ea trebuie să ne dea informații despre modul în care se conectează componentele sistemului și despre interacțiunea dintre acestea, dar oferă și o imagine generală a sistemului. Stabilirea arhitecturii sistemului, fie că este vorba despre o rețea sau despre un produs software, este una dintre cele mai importante etape ale realizării unui proiect. Este vital să se stabilească zonele critice ale sistemului, adică acele componente ce prezintă risc mare de defectare sau care, prin defectarea lor, pot provoca oprirea parțială sau totală a sistemului. Trebuiesc luați în considerare și factorii care ar putea avea influență asupra sistemului (până și condițiile atmosferice ar putea influența funcționarea unei rețele).
Pentru reducerea complexității alcătuirii, majoritatea rețelelor sunt organizate pe mai multe nivele (straturi), în sensul împărțirii stricte a sarcinilor: fiecare nivel este proiectat să ofere anumite servicii, bazându-se pe serviciile oferite de nivelele inferioare. Atunci când două calculatoare comunică, în fapt, se realizează o comunicare între nivelele de același rang ale celor două mașini (vezi fincționarea modelului arhitectural ISO – OSI). Nivelul n al mașinii “A” realizează schimb de date cu nivelul n al mașinii “B” prin intermediul unui protocol numit protocolul nivelului n. În realitate, datele nu sunt transmise de la nivelul n al unei mașini către nivelul n al alteia, ci fiecare nivel realizează prelucrările specifice asupra datelor și transmit aceste date nivelului inferior, până la nivelul fizic unde se realizează schimbul efectiv de date (această a fost descrisă amănunțit la prezentarea modelul de referință ISO-OSI). Doar din punct de vedere logic se poate vorbi de o "conversație" între nivelele a două mașini.
Mulțimea protocoalelor și a nivelelor reprezintă arhitectura rețelei. Specificațiile arhitecturii trebuie să fie destul de detaliate pentru a permite implementarea de aplicații care să se conformeze specificului fiecărui nivel.
2.3. Protocolul de comunicație
Definirea, structura și funcțiile protocolului
de comunicație
Două procese (aplicații) comunică între ele prin intermediul sistemelor de comunicații atașate dacă fiecare nivel din cadrul arhitecturii primului sistem atașat comunică cu nivelul corespondent din cadrul celui de-al doi-lea sistem. Această comunicare se realizează prin schimbul de mesaje între nivelele corespondente, mesaje care conțin, după cum am prezentat în cadrul subcapitolului anterior, atât date, cât și informații de control. Aceste mesaje sunt de fapt reprezentate de PDU, noțiune definită anterior, și respectă un anumit set de reguli numit PROTOCOL.
Elementele de bază ale unui protocol sunt:
Sintaxa: include formatul datelor și nivelele electrice ale semnalelor;
Semantica: include informații de control pentru coordonare și pentru tratarea erorilor;
Temporizarea: include secvențierea și adaptarea vitezei de transmisie.
În primă fază, pentru ca două sisteme să poată comunica ar fi suficientă definirea unui set de protocoale, câte unul pentru fiecare nivel. Deoarece comunicația fizică este posibilă numai la primul nivel, este necesar ca mesajele pe care procesele doresc să le transmită, să ajungă a nivelul fizic străbătând toate nivelele arhitecturii. Acest lucru este posibil prin intermediul interfețelor dintre nivelele adiacente SAP.
După cum am mai arătat, prin aceste interfețe nivelele arhitecturale comunică primitive ale serviciului (SP). Interfețele corespunzătoare nivelelor sunt foarte precis definite, iar funcțiile de comunicație asociate nivelului superior se bazează pe serviciile oferite de nivelul inferior. Din acest motiv primitivele de la nivelul interfeței se numesc și primitive abstracte de serviciu (ASP = Abstract Service Primitive).
Astfel, un protocol este constituit din:
protocolul propriu-zis care specifică formatul fiecărui PDU;
interfețele care specifică reguli de dialog cu nivelele adiacente.
Aceste funcții (cererea de către utilizator și oferirea de către furnizorul de servicii) se realizează cu ajutorul a patru tipuri de primitive:
cerere (request): de la utilizator la furnizor pentru a solicita un serviciu;
indicare (indication): de la furnizor la utilizator pentru a indica stareainternă a nivelului furnizor semnificativă pentru utilizator;
răspuns (response): de la utilizator la furnizor pentru continuarea procedurii începute anterior de primitiva indication;
confirmare (confirmation): de la furnizor la utilizator pentru a comunica rezultatul uneia sau mai multo cereri.
Modul de obținere a serviciilor și desfășurarea lor în timp sunt prezentate sugestiv în următoarea figură:
Fig. 2.3 Distribuția în timp a primitivelor
Datorită structurii pe bază de nivele, o SP request determină pornirea serviciului și ca urmare se transmite o SP indication către SAP corespunzător, care va semnala acceptarea cererii printr-o SP response, pe baza căreia nivelul inferior va confirma nivelului superior îndeplinirea serviciului solicitat printr-o SP confirmation.
Protocoalele de comunicație sunt foarte diverse, ele implementând diverse funcții. Dintre aceste funcții se disting unele care sunt uzuale și sunt necesare oricărui sistem de comunicație cu comutare de pachete, cum ar fi:
controlul fluxului: se folosește pentru adaptarea vitezei de transmisie între diferitele echipamente hardware ce participă la comunicație;
segmentarea și reasamblarea pachetelor: fluxul total de date se împarte în pachete mai mici, proces numit segmentare; la recepție pachetele trebuie reasamblate astfel:
– la comunicațiile orientate pe conexiune, segmentarea și reasamblarea sunt mai simple și se fac pe baza unui indicator de pachet final;
– la comunicațiile orientate pe pachete, fiecare pachet trebuie să aibă un indicator de ordine, deoarece pachetele pot ajunge la destinație în altă ordine decât au fost transmise, ele putând parcurge căi diferite.
livrarea secvențială a pachetelor: livrarea secvențială este necesară pentru a trata erori, ca de exemplu un pachet duplicat sau un pachet pierdut;
detecția și corecția erorilor: se poate realiza fie printr-un cod ciclic pentru corecția erorilor aleatoare ce apar la nivel fizic (realizată hard), fie printr-o sumă de control pentru erorile ce apar la nivelele superioare (realizată hard).
2.4. Controlul accesului la mediul de
transmisiuni
În rețelele în care suportul de transmisiune este folosit în comun de către sistemele conectate în rețea este necesar un mecanism care să permită distribuirea capacității de transmisiune a acestui suport între sistemele interconectate, astfel ca:
fiecărui sistem să-i revină o parte din această capacitate de transmisiune;
fiecare sistem să aibă acces la suportul de transmisiune într-un interval de timp rezonabil;
pierderile din capacitatea de transmisiune datorită acestui mecanism să fie minime.
Tehnicile de acces, foarte diferite, pot fi clasificate astfel:
Fig. 2.4 Tehnici de acces
În tehnicile de acces cu alocare statică, capacitatea de transmisiune a suportului este repartizată sistemelor din rețea, fie prin diviziune în frecvență (MRF – multiplexare cu repartiție în frecvență), fie prin diviziune în timp (MRT – multiplexare cu repartiție în timp).
În cazul MRF fiecare sistem emite într-o anumită bandă de frecvențe și trebuie să fie capabil să recepționeze în toate benzile de frecvențe utilizate de celelalte sisteme. Metoda prezintă dezavantajele unui cost ridicat și al unei eficiențe mai scăzute în utilizarea capacității de transmisiune a suportului.
În cazul MRT fiecărui sistem i se alocă ciclic un anumit interval de timp pentru emisie. Eficiența acestei metode este de asemenea scăzută și, în plus, întârzierile în transmiterea mesajelor sunt mari, proporționale cu numărul sistemelor din rețea.
În tehnicile de acces prin alocare dinamică, suportul de comunicație este alocat doar utilizatorilor care au nevoie. Apare deci o dificultate legată de posibilitatea de cunoaștere a necesităților utilizatorilor.
În tehnicile cu acces aleatoriu, fiecare sistem poate încerca să transmită, deci să ocupe suportul de transmisiune, în orice moment, însă va transmite numai după ce a ascultat suportul și a constatat că acesta este liber.
În continuare vor fi prezentate câteva metode de acces frecvent utilizate.
2.4.1. Metode polling
Metodele de acces prin polling (interogare) sunt utilizate în topologiile liniară și în stea. Într-una din variantele sale și anume polling cu control centralizat, un sistem coordonator are responsabilitatea de a parola dreptul de transmitere al fiecărui sistem din rețea, într-o ordine predominantă. Sistemele sunt interogate succesiv și dacă unul din ele dorește (este gata) să transmită, răspunde pozitiv și sistemul coordonator îi transmite parola. El obține astfel accesul la suportul de transmisiune. După ce termină de transmis va înapoia parola sistemului coordonator care, în continuare, va interoga un alt sistem. Aceasta este o tehnică de tip master–slave. Se pot introduce ușor priorități pentru anumite sisteme, cărora li se va da accesul mai des. Este totuși o tehnică greoaie, ineficientă. O ameliorare poate fi adusă printr-un control descentralizat.
În tehnica de acces prin polling cu control descentralizat sistemul care primește parola de la sistemul coordonator o trece, când nu are de transmis sau a terminat de transmis un mesaj, sistemului următor, fără a o mai întoarce la sistemul coordonator. Față de polling-ul centralizat aici este necesar un software mai complex, stocat în fiecare sistem.
În aceste două tehnici de polling doar sistemul central (coordonator) are dreptul să conecteze sisteme noi în rețea. În polling-ul de control descentralizat, acest lucru se face numai dacă sistemul central a preluat parola, după o rotație a acesteia la sistemele active.
Aceste tehnici sunt greoaie. Ele sunt utilizate în special pentru a concentra traficul de la terminalele lente. În mod deosebit aceste tehnici nu sunt eficiente când numărul utilizatorilor este mare.
O versiune ameliorată, care permite reducerea timpului de gestiune a legăturii este polling-ul adaptativ, numit și probing. În această tehnică sistemul coordonator încearcă să afle care sunt sistemele care doresc să transmită. Pentru aceasta el transmite un semnal ansamblului celorlaltor sisteme, interpretat ca “Aveți de transsmis ?”. în caz afirmativ, sistemele trebuie să emită un semnal pe un interval de timp care le este destinat, fiecăruia în parte, permițând sistemului central să cunoască explicit terminalele active. Acesta va da parola succesiv terminalelor care au răspuns, apoi din nou va emite semnalul de interogare. Dacă nu este nici un răspuns, repetă semnalul de interogare până când unul sau mai multe sisteme răspund. Această tehnică poate fi socotită ca o rezervare dinamică a tranșelor (slots) de timp. Ea diminuează sensibil timpul de gestiune în comparație cu tehnicile prezentate anterior. Totuși, dacă multe sisteme au de transmis, ameliorarea nu este sensibilă.
2.4.2. Tehnici cu jeton
La modul general, aceste tehnici constau în a face să circule în rețea un permis de emisie, numit jeton (token) și numai sistemul care posedă jetonul este autorizat să emită.
Tehnicile de acces cu jeton diferă, în special, prin algoritmul de trecere a jetonului de la un sistem la altul și prin momentul în care este eliberat jetonul de către sistemul care l-a deținut.
a) – Tehnici cu jeton neadresat
Acestea sunt folosite în rețelele cu topologie de tip inel. Jetonul este o configurație de biți (poate fi și un singur bit), plasată într-un câmp bine precizat al formatului (cadrului) în care se transmite mesajul, sau care reprezintă un cadru particular care circulă în rețea, de la un sistem la altul. Un jeton circulant poate fi captat (reținut) de orice sistem gata să emită. Aflat în posesia jetonului, sistemul transmite mesajul său. Când emisia semnalului s-a terminat, jetonul este retransmis și, în funcție de momentul în care se face retransmiterea sa, sunt mai multe variante. Astfel, jetonul poate fi retransmis (eliberat) de sistemul care îl deține:
după ce cadrul emis de el, parcurgând inelul, i-a revenit în întregime;
imediat ce recepționează antetul cadrului emis;
imediat ce a emis cadrul.
Eficacitatea rețelei este influențată foarte mult de soluția aleasă. Prima variantă are dezavantajul blocării jetonului pe un interval de timp mare, deci, la debite mari eficiența este foarte scăzută. În schimb, cadrul de informație nu necesită un câmp pentru jeton.
În a doua soluție un cadru circulă fără oprire în buclă și jetonul este materializat printr-un bit situat într-un câmp la începutul cadrului:
Fig. 2.5 Formatul cadrului cu jeton
Dacă bitul jeton este 0, înseamnă că jetonul este liber. Un sistem care vede acest bit în 0, poate capta jetonul, înlocuindu-l printr-un 1. Jetonul va fi lăsat liber când bitul jeton va trece din nou pe la sistemul emițător. Pentru a putea examina starea jetonului și pentru a introduce informația în cadrul care circulă este necesar ca, la fiecare sistem, cadrul circulant să fie introdus într-un registru de deplasare, ceea ca va însemna o întârziere suplimentară.
În variantele prezentate, monopolizarea jetonului într-un sistem, pe intervalul de timp în care cadrul face un tur pe buclă, toate antrenau o utilizare nesatisfăcătoare a suportului de transmisiune.
Cea de-a treia variantă se prezintă astfel:
Fig. 2.6 Jeton plasat la sfârșitul cadrului
În această variantă suportul de transmisiune este mult mai bine utilizat deoarece jetonul este eliberat imediat după ce sistemul care în deține a terminat de emis cadrul său, jetonul găsindu-se într-o zonă la sfârșitul cadrului. În felul acesta este posibilă propagarea (nu emisia!) simultană a mai multor cadre provenind de la sisteme diferite.
Sistemul care este gata să transmită, găsind jetonul liber într-un cadru de informație ce trece prin registrul său de deplasare, îl pune în starea ocupat și inițiază formarea altul cadru de informație, al cărui jeton va fi pus în starea liber. Spre deosebire de celelalte două variante, aici cadrul de informație nu este retras de către emițător, ci de către destinatar. Este o soluție atractivă pentru rețelele de mare viteză, cum ar fi rețele FDDI (Fiber Distribution Data Interface), în care suportul de transmisiune este fibra optică.
Aceste tehnici cu jeton prezintă inconvenientul că necesită un control pentru menținerea în permanență a jetonului în rețea și pentru ca acesta să nu se multiplice. În cazul pierderii jetonului, scade debitul efectiv al rețelei. În general este necesară o stație monitor care face acest control. Pentru o funcționare mai sigură este bine ca fiecare sistem să posede software-ul necesar pentru a fi stație monitor, însă, în orice moment numai un sistem poate fi în serviciu ca stație monitor.
b) – Tehnici cu jeton adresat
O metodă folosită este aceea de a adresa explicit jetonul unui anumit sistem, prin intermediul unui cadru de supervizare. Dacă sistemul care a primit jetonul nu are nimic de transmis, îl va pasa altui sistem, specificând adresa acestuia.
2.4.3. Inelul cu tranșe (slotted ring)
Această este utilizată numai în rețelele cu topologie inel și constă în divizarea capacității inelului într-o serie de intervale (slots), constituite fiecare dintr-un număr de biți și capabile să transmită câte un cadru de informație de mărime fixă. Formatul cadrului pe un astfel de interval se prezintă astfel:
Fig. 2.7 Formatul cadrului pentru inelul cu tranșee
Diferitele sisteme din inel emit continuu cadre de lungime fixă, de la un sistem la altul în jurul inelului. Fiecare interval (cadru) conține un indicator PV (plin-vid) la începutul său, indicând dacă este gol (V) sau conține date (P). Dacă un sistem are de transmis un mesaj el așteaptă un interval gol, îi schimbă indicatorul PV, deci ocupă acest interval, inserează adresele destinație și sursă și o parte din mesaj, cât să umple intervalul, și transmite cadrul astfel format către următorul sistem în inel.
Atunci când un astfel de cadru, conținând date, este recepționat de un sistem, acesta verifică adresa destinație pentru a vedea dacă trebuie să copieze masajul sau nu. În ambele situații va transmite apoi cadrul către următorul sistem în inel. Cadrul poate fi retras de către sistemul care l-a emis, lăsând liber intervalul corespunzător, sau de către un sistem monitor în anumite situații de funcționare anormală.
Această tehnică de acces permite emiterea simultană de către mai multe sisteme a unor mesaje pentru că în rețea circulă mai multe tranșe simultan. Spre exemplu, la un debit de 50 Mbs durata unui bit este 20 ns și dacă timpul de propagare în inel, ținând seama și de întârzierea introdusă de registrele de deplasare asociate sistemelor, este de 10s, se pot propaga simultan în inel 500 de biți, reprezentând mai multe tranșe.
Fig. 2.8 Inel cu tranșe
O tranșă ar putea fi utilizată de mai multe sisteme diferite într-un tur al inelului dacă ea ar fi eliberată de către sistemul destinatar.
Tehnica inelului cu tranșe este adaptată mesajelor scurte și are avantajul simplității, necesitând o interfață și software relativ simple în fiecare sistem. Pentru transmiterea mesajelor lungi sunt necesare multe tranșe iar informația de adresare și de control din fiecare tranșă face ca metoda să fie mai puțin eficientă decât pentru mesajele scurte.
2.4.4. Accesul aleatoriu
În tehnicile cu acces aleatoriu un sistem poate accede la mediul de transmisiune, cu unele restricții, în orice moment. Principalul avantaj al acestor tehnici este disponibilitatea completă a suportului de transmisiune pentru un sistem dacă celelalte sisteme conectate în rețea nu sunt pregătite să transmită. Dar, datorită accesului aleatoriu, pot surveni situații de contenție, când două sau mai multe sisteme transmit în același timp. Mesajele care sunt în conflict (coliziune) sunt pierdute și trebuie retransmise. Au fost propuse diferite metode pentru a reduce numărul conflictelor și pentru a le rezolva. În continuare vor fi prezentate câteva din aceste metode.
a) – Aloha în tranșe (Slotted Aloha)
Se discretizează timpul în intervale egale și fiecare sistem are voie să intre în emisie numai la începutul unui astfel de interval. Dacă apare o coliziune se va relua transmisia după un interval de timp aleatoriu, dar numai la început de tranșă.
b) – Acces aleatoriu cu ascultarea putătoarei
Un sistem care este gata să transmită ascultă mai întâi mediul de transmisiune și dacă acesta este liber (deci nu se detectează semnal pe el) va începe să emită, iar dacă mediul este ocupat, va amâna transmisiunea. Această metodă reduce considerabil riscurile de coliziune dar nu le reduce complet. Spre exemplu, dacă timpul de propagare între două sisteme cele mai îndepărtate din rețea este și dacă unul din aceste două sisteme începe să transmită, celălalt va simți mediul ocupat după o întârziere , interval în care poate și el să înceapă emisia, survenind astfel o coliziune.
Sunt numeroase variante la această tehnică, diferențiindu-se prin următoarele caracteristici:
strategia urmată când se detectează mediul ocupat;
modul în care sunt detectate coliziunile;
strategia urmată după detectarea coliziunilor.
În toate variantele, înainte de a transmite, sistemul ascultă mediul și dacă mediul este liber începe să transmită.
c) – Metoda CSMA nonpersistent (Carrier Sense Multiple Access – Acces multiplu cu perceperea purtătoarei).
Sistemul gata să transmită ascultă mediul. Dacă acesta este ocupat va reîncepe același proces după o întârziere aleatorie:
Fig. 2.9 CSMA nonpersistent
d) – Metoda CSMA persistent
Sistemul care, fiind gata să transmită, ascultă mediul și-l găsește ocupat, va continua să-l asculte până ce acesta devine liber, moment în care începe să transmită:
Fig. 2.10 CSMA persistent
În această variantă se pierde mai puțin timp decât în precedenta în ceea ce privește așteptarea pentru a începe transmisia, în schimb crește probabilitate de coliziune pentru că mesajele care se acumulează în perioada în care este ocupat mediul vor fi transmise toate în același timp.
e) – Metoda CSMA p-persistent (0p1).
În această variantă algoritmul este ca și cel precedent, doar că atunci când mediul devine liber sistemul emite cu o probabilitate p sau, altfel spus, amână transmisiunea cu o probabilitate 1p. Se micșorează probabilitatea de coliziune dar pot fi pierderi de timp, deoarece, la eliberarea suportului de transmisiune, deși unul sau mai multe sisteme sunt gata să transmită, acesta poate să rămână în continuare liber un interval de timp oarecare.
f) – Metoda CSMA cu detectarea coliziunii (CSMACD – Collision Detection).
Fig. 2.11 CSMA / CD
Este cea mai utilizată tehnică de acces aleatoriu, normalizată în standardele IEEE 802.3 și ISO 8802.3 pentru rețele liniare. La ascultarea mediului înainte de a transmite se adaugă și ascultarea în timpul transmisiunii (vezi figura anterioară).
Un sistem gata să transmită, detectând mediul liber, începe să transmită și continuă să asculte mediul de transmisiune. Astfel, dacă va avea loc o coliziune, aceasta este sesizată, transmisia mesajului este abandonată și sistemul emite un semnal special de bruiaj cu scopul de a avertiza și celelalte sisteme aflate în emisie. Sistemul va încerca să retransmită ulterior, conform unui anumit algoritm de reluare a transmisiunii.
Această variantă aduce un plus de eficacitate în raport cu celelalte pentru că se detectează imediat coliziunile și se abandonează transmisia în curs.
Coliziunea este sesizată comparând semnalul emis cu cel care se propagă pe mediul de transmisiune. Metoda de detectare a coliziunilor este relativ simplă, dar necesită tehnici de codare ( reprezentare a datelor) adecvate pentru a recunoaște ușor o suprapunere de semnale.
g) – Metoda CSMA cu evitarea coliziunii (CSMACA – Collision Avoidance).
Cu această metodă, care are la rândul ei mai multe variante, sistemul ascultă mediul de transmisiune și, dacă este ocupat, continuă ascultarea până când devine liber. Apoi așteaptă un anumit interval de timp, depinzând de poziția lui relativă într-o listă logică a sistemelor din rețea. Cum va proceda sistemul în continuare, după ce acest interval de timp s-a scurs fără ca un alt sistem să înceapă să transmită, depinde de varianta CSMACA adoptată.
Capitolul III
ROLUL ȘI IMPORTANȚA PROCESULUI DE SIMULARE ȘI OPTIMIZARE A REȚELELOR DE COMUNICAȚII
3.1. Modelarea sistemelor
Studiul sistemelor de comunicații nu este posibil în condiții reale de funcționare decât în foarte rare ocazii, chiar și dacă sistemele există. Același fenomen se prezintă identic pentru orice altă categorie de sisteme. De aceea este absolut necesară reprezentarea funcționării sistemelor prin mijloace matematice sau descriptive, mijloace care să permită aproximarea cât mai corectă a realității. Se realizează astfel un model al sistemului, într-un proces de modelare atât a caracteristicilor fizice ale sistemului, cât și a operațiilor pe care el le execută (operații calitative șisau cantitative, logice, temporale etc.).
Cum multe dintre sistemele ce compun rețelele actuale de comunicații sunt deosebit de complexe, modelarea lor globală este de-a dreptul imposibil de realizat. În consecință se recurge la descompunerea sistemelor în câteva blocuri componente (subsisteme), ce sunt entități bine determinate funcțional. În final, se modelează aceste subsisteme prin mijloace cunoscute, care sunt cu siguranță cu mult mai simple decât sistemul global. Rămâne însă de rezolvat problema interconectării subsistemelor și a verificării prin simulare a rezultatelor obținute.
3.1.1. Modelarea – proces complex
Modelarea poate fi utilizată pentru analiza sistemelor existente, deci în faza de exploatare operațională, pentru evaluare și eventual îmbunătățirea performanțelor acestora, dar și în faza de concepție a unor sisteme noi. Modelul folosit este totdeauna o reprezentare simbolică, o abstractizare a sistemului în cauză. Abstractizarea se realizează într-un mod convenabil prin raportarea la anumiți parametri șisau anumite caracteristici funcționale ale sistemului. Alegerea acestora, ca fiind cei mai reprezentativi pentru scopul urmărit
(analiză sau concepție), se face totdeauna cu un anumit grad de subiectivitate, deoarece depinde de priceperea și de experiența modelatorului.
Etapizarea procesului de modelare
În procesul de modelare a oricărui sistem se produc în mod obligatoriu următoarele etape succesive:
Stabilirea modelului care să înlocuiască sistemul real sau cel ce urmează a fi proiectat.
Modelul unui sistem este o abstractizare pentru care sunt reținute cele mai reprezentative caracteristici ale sale, aprecierea făcându-se în raport de scopul urmărit. Orice model este realizat ca un ansamblu de resurse materiale și logice, abordabile prin funcțiile ce le revin. Cum resursele sunt totdeauna un număr finit, accesul clienților la ele implică probleme de concurență, ce pot fi eventual rezolvate prin utilizarea șirurilor de așteptare.
Rezolvarea modelului cu ajutorul unor metode analitice sau prin simularea funcționării, în vederea estimării performanțelor sistemului.
Urmând procedurile clasice adecvate șirurilor de așteptare pot fi evaluate mărimile parametrilor caracteristici pentru modelul ales: rata de utilizare a resurselor, timpul de așteptare în șir, lungimea șirului de așteptare, timpul total de staționare în sistem etc.
În această etapă, pentru ușurarea calculelor, se pot considera unele ipoteze simplificatoare. O asemenea ipoteză este de exemplu independența resurselor componente ale unui sistem, dar ea nu este perfect conformă cu realitatea, mai ales dacă ne gândim la sincronismul funcționării unor componente ale sistemelor informatice. Simularea se impune a fi folosită ca metodă de rezolvare a modelului, deoarece metodele matematice curente nu pot considera prin mijloace obișnuite orice problemă. Tehnica modernă face posibilă astăzi utilizarea simulării în condiții de cost suficient de avantajoase.
Analiza rezultatelor obținute:
Dimensionarea sistemului se face utilizând rezultatele măsurătorilor efectuate prin intermediul diferitelor scenarii și modificând apoi după necesități anumite elemente ale modelului. În această fază de studiu se pot identifica diferiți factori deosebit de sensibili, care afectează în mod hotărâtor comportamentul sistemului. Asupra lor va trebui să se intervină în primul rând pentru a se dirija în sensul dorit comportamentul sistemului.
În funcție de evaluarea ce se urmărește a fi realizată trebuie să se realizeze procese diferite de optimizare, astfel încât să se obțină parametrii de intrare ai modelului care dau cele mai bune performanțe, în limitele restricțiilor impuse. Este evident că validarea modelului este indispensabilă și cere uneori revizuirea modelului însuși sau chiar modificarea ipotezelor de funcționare a sistemului în ansamblul său.
Etapele succesive în care se derulează un proces de modelare sunt prezentate sintetic în figura următoare:
Fig. 3.1 Etape ale procesului de modelare
Este evident că evaluarea globală descrisă conduce la observații aproximative ale comportamentului sistemului, datorită faptului că în fiecare fază a procesului este introdusă o eroare. Se pare că până în prezent nu există vreo metodologie care să permită trecerea directă de la sistem la model. Eroarea E1 ce apare în faza 1 este greu de măsurat și depinde de gradul de detaliere a modelului. Se poate afirma că absența mecanismelor de descriere în rețelele cu așteptare nu poate decât să accentueze această eroare. Eroarea E2 introdusă în faza de rezolvare a modelului depinde de tehnicile folosite la rezolvare: ea este nulă în cazul folosirii metodelor exacte și variabilă în cazul simulărilor, cu valori ce pot fi neglijabile sau foarte importante, în raport cu gradul de aproximare utilizat.
Modelarea cantitativă
Modelarea cantitativă începe totdeauna cu stabilirea parametrilor care să permită măsurarea performanțelor sistemelor (debit de informații, timp de răspuns, număr mediu de resurse ocupate, rată de utilizare a resurselor etc.). Metodele de evaluare cantitativă sunt grupate în trei categorii, fiecare cu avantajele și inconvenientele lor:
Măsurarea – se execută pe anumiți parametri ai sistemului. Există tehnici complexe de măsură, dar unele dintre ele conduc la o optimizare deosebit de dificilă.
Metodele analitice – sunt foarte eficiente în vederea optimizării, în măsura în care pot fi scrise și rezolvate ecuațiile matematice. De
asemenea în aceste condiții calculele pentru aflarea valorilor parametrilor sunt foarte rapide. Inconvenientele majore rezidă însă în numărul foarte mic de modele care au o soluție matematică exactă. Metodele analitice provin din teoria șirurilor de așteptare. Există unele modele foarte simple, care au soluții exacte în condițiile impuse de unele ipoteze stricte. Pentru unele modele mai complexe există soluții deseori aproximative, dar este foarte dificil de a aprecia corectitudinea lor. În ultimul timp, în domeniul cercetării, sunt mai des folosite rețelele Petri stocastice, introduse de C.A. Petri în 1962, sau chiar o îmbinare a rețelelor cu șiruri de așteptare cu rețelele Petri, rezultatele astfel obținute fin satisfăcătoare.
Simularea permite a se intra mult mai în detaliu, de a descrie mai precis modelul cu restricțiile sale. Soluția este aproximativă, dar se poate cunoaște cu o anumită precizie (90-95% în general) intervalul în care se situează rezultatul exact. Pentru a se obține un interval de precizie suficient de mic, trebuie să fie considerate un număr mare de eșantioane, deci se va folosi un calculator pentru un timp îndelungat. Trebuie însă precizat că pentru fiecare simulare nu se obține decât un singur punct de funcționare a sistemului. Dacă s-ar dori optimizarea întregului sistem, atunci procedura ar deveni deosebit de dificil de folosit.
Modelarea calitativă
Complexitatea crescândă a sistemelor, precum și aplicațiile executate prin intermediul acestora, necesită utilizarea unor metode capabile să controleze comportamentul logic al operațiilor puse în joc. Rezultă deci necesitatea metodelor formale de validare. Se remarcă rețelele Petri, utilizate împreună cu teoria grafurilor și a algebrei liniare.
Concluzie : În procesul de modelare se realizează o descriere a sistemului pe baza unor ecuații matematice, care pot fi ușor rezolvate direct sau printr-o programare nu foarte costisitoare. Însă stabilirea ecuațiilor este uneori foarte dificil de efectuat.
3.1.2. Utilizarea simulării în procesul de modelare
Una dintre tehnicile cele mai importante care pot fi folosite în cadrul estimării performanțelor sistemului de comunicații o constituie simularea. Simularea reprezintă un ansamblu de tehnici și proceduri care permit aproximarea comportamentului unui sistem, mai ales al sistemelor foarte complexe pentru care tehnicile modelării analitice nu pot face față.
Este totdeauna o metodă stohastică, nedeterministă, deoarece măsura sau simulatorul se bazează pe exploatarea unor variabile aleatoare, deci comportamentul sistemului studiat este stohastic și dinamic, deoarece conține evenimente care apar în mod aleator în decursul timpului. Simularea este o tehnică prin care se asociază sistemului real un model adecvat, numit model de simulare, care reprezintă toate intersecțiile logice ale componentelor sistemului, precum și mecanismul schimbării lor în timp. Modelul este folosit apoi pentru a produce, prin intermediul calculatorului, succesiunea cronologică de stări prin care va trece sistemul, considerându-se dată starea inițială. Cu alte cuvinte, modelul de simulare permite crearea unor experiențe artificiale asupra sistemului, care să furnizeze materialul statistic necesar unor evaluări cantitative asupra sistemului real.
Metodele analitice sunt deosebit de avantajoase pentru că rezolvă principiile generale și conduc la obținerea unor soluții ușor de folosit în practică și totodată general aplicabile. În cadrul unei rețele reale de comunicații, chiar pentru cele mai simple structuri, se manifestă existența unor fenomene funcționale complexe.
Metodele de simulare creează, în termeni logici, un model valabil pentru rețeaua de comunicații, omițând pentru etapa dată doar detalii neesențiale. Acest model este folosit tot timpul într-o analiză statistică a comportamentului rețelei. Simularea reprezintă un experiment statistic al unui model ipotetic al rețelei. Pentru un nivel de încredere acceptabilă, modelul de simulare al unei rețele de comunicații trebuie să corespundă structurii rețelei și caracteristicilor esențiale ale comportamentului abonaților.
Ca orice model dinamic, un model matematic de simulare trebuie să pună în evidență trei seturi de variabile:
de intrare;
de stare;
de ieșire.
Acestea pot fi deterministe sau stohastice și de regulă iau valori într-o mulțime de stări cel mult numărabilă. Variabilele de ieșire depind de cele de intrare prin intermediul variabilelor de stare. Dependența este determinată de structura modelului considerat și trebuie transpusă într-un ALGORITM care să precizeze modul de ducere a variantelor de ieșire din cele de intrare.
În momentul în care modelul de simulare este construit, acesta va primi ca date de intrare, pentru o anumită perioadă de timp setată, volumul și tipul de trafic pe care rețeaua respectivă trebuie să poată să îl prelucreze. Ca date de ieșire se furnizează anumite caracteristici legate de comportamentul modelului, mai exact furnizându-se următoarele elemente:
timpul de răspuns obținut;
nivelul de încărcare a factorilor critici;
evoluția cozilor, valorile medie și maximă ale cozilor în momentul în care acestea au loc;
histograma timpilor de tranzit și de răspuns între punctele selectare în cadrul rețelei;
procentul de utilizare, de încărcare a diferitelor elemente ale sistemului;
cerința de memorare pentru cozi;
maximul fluxului în cadrul modelului.
Modelele odată construite, pot fi modificate și experimentate ușor și de un număr nelimitat de ori. Astfel, volumul și tipul de trafic pot fi furnizate pentru a observa cum se comportă modelul în funcție de nivelul de trafic. De asemenea, parametrii asociați liniilor de comunicații și nodurilor pot fi modificați, pot fi adăugate linii de comunicație, capacitățile de memorare pot fi variate, se pot crește vitezele corespunzătoare canalelor și se poate modifica mecanismul de programare.
Utilizarea simulării pentru studierea fenomenelor lumii reale necesită o muncă laborioasă, de aceea cel ce folosește această tehnică trebuie să facă uz de anumite jaloane menite să-l ajute în organizarea muncii sale. Potrivit literaturii de specialitate, realizarea unui experiment de simulare se desfășoară de obicei în următoarele etape:
formularea problemei;
colectarea și prelucrarea primară a datelor;
elaborarea modelului de simulare;
estimarea parametrilor repartițiilor;
evaluarea performanțelor modelului;
realizarea programului de calcul;
validarea programului;
planificarea experimentelor de simulare;
analiza și interpretarea datelor simulării.
De menționat că rezolvarea unei probleme concrete poate să nu facă apel la toate etapele menționate anterior. Astfel, pentru unele probleme, modelele pot să fie deja cunoscute, rămânând a fi determinate doar variabilele de ieșire.
În continuare, pe scurt, se vor prezenta câteva repere cu privire la conținutul etapelor anterioare:
a) – Formularea problemei:
Înainte de a planifica un experiment de simulare este necesar să se definească obiectivele urmărite, întrebările la care trebuie să se răspundă, ipotezele care trebuie testate și efectele care trebuie estimate, impunând de la început o anumită precizie a estimării. Este de menționat faptul că, rezolvarea cât mai precisă a acestei etape este un element care facilitează în măsură determinantă soluționarea problemei.
b) – Colectarea și prelucrarea primară a datelor:
Datele, după o prelucrare primară, sugerează ipotezele care pot fi formulate pentru elaborarea modelului matematic, și permit considerații care să conducă la îmbunătățirea acestuia. În plus, ele sunt indispensabile atât pentru estimarea parametrilor repartițiilor, cât și pentru validarea programului de simulare.
c) – Elaborarea modelului de simulare:
pentru a fi rezolvată pe calculator, problema formulată trebuie pusă într-o formă algoritmică, ceea ce presupune, de regulă, realizarea prealabilă a unui model matematic al ei. După cum se subliniază în literatură, este greu să se realizeze reguli standard pentru găsirea celui mai bun model al unei probleme date, astfel încât elaborarea modelului este în prezent mai mult o artă decât o știință. Sunt menționate, totuși, anumite repere de care să se țină seamă în construirea modelului.
Unul dintre ele se referă la numărul variabilelor incluse în model. Dacă modelul are un număr prea mare de variabile este greu de manevrat, atât în ceea ce privește stabilitatea relațiilor dintre ele, cât și în privința lucrului efectiv pe calculator. Pe de altă parte, modelul care conține prea puține variabile poate să piardă din model anumite aspecte ale problemei. De aceea, un model trebuie să includă, pe cât posibil, variabilele esențiale ale problemei.
O altă cerință este eficacitatea de calcul a modelului, exprimată prin timpul de calcul necesar rezolvării problemei, trebuind să fie rezonabil de mic. Astfel, un model complex, cu multe variabile și relații funcționale, cere un personal de programare cu înaltă calificare, precum și un consum de timp ridicat, ceea ce poate să crească mult costul experimentului de simulare. Pe de altă parte, încercările de a reduce timpul de programare pe seama limbajelor specializate se soldează, de cele mai multe ori, cu scăderea flexibilității modelului și cu creșterea timpului de calcul.
În sfârșit, pentru construirea modelului trebuie avute în vedere și mijloacele prin care ne putem convinge atât de corectitudinea acestuia, cât și de tipul de experimente pe care intenționăm să le producem, prin intermediul calculatorului, asupra modelului.
Toate aceste considerații sunt importante deoarece simularea este o tehnică proprie cercetării sistemelor foarte complexe, pentru a căror studiere s-a impus, din ce în ce mai mult, tendința de a concepe modele sub formă modulară, care permit utilizarea în mod recursiv a unor modele, ceea ce ușurează mult folosirea calculatorului.
d) – Estimarea parametrilor repartițiilor:
Parametrii repartițiilor variabilelor aleatoare care intervin în model trebuie estimați prin procedee specifice statisticii matematice, aplicate datelor colectate din sistemul real.
e) – Evaluarea performanțelor modelului:
Înainte de a realiza algoritmul și programul de simulare, trebuie făcută o primă verificare, atât în ceea ce privește adecvarea modelului la fenomenul studiat, cât și cu privire la corectitudinea estimării parametrilor repartițiilor pe care el le implică. Aceasta se realizează, de obicei, pe baza unor calcule preliminare, făcute de multe ori cu mâna, sau cu echipamente mai simple, pentru a surprinde eventualele neconcordanțe între valorile calculate ale variabilelor de ieșire și cele reale, observate în sistemul dat. În cazul în care se constată existența unor astfel de neconcordanțe, atunci toate etapele anterioare trebuie reluate, în vederea îmbunătățirii modelului.
f) – Realizarea programului de calcul:
După ce modelul de simulare a fost elaborat, iar parametrii săi au fost estimați, următorul obiectiv îl constituie realizarea algoritmului de simulare, prin care să se obțină estimările variabilelor de ieșire și transpunerea sa într-un program de calcul. Dacă sistemul este complex, iar pentru realizarea modelului s-a folosit procedura modularizării, atunci construirea algoritmului de simulare revine la asamblarea algoritmilor corespunzători modulelor sistemului și a schemelor logice corespunzătoare lor.
g) – Validarea programului:
Validarea unui program de simulare este o problemă complexă. Deși din punct de vedere teoretic nu există procedee generale de validare pentru modelele de simulare, experiența sugerează două direcții principale de urmat: cea mai simplă este de a testa programul într-un caz particular, în care soluția este cunoscută; dacă o asemenea posibilitate nu există, atunci singura alternativă este de a compara valorile variabilelor de ieșire obținute prin observarea situațiilor reale similare.
h) – Planificarea experimentelor de simulare:
Obiectivul principal al planificării unui experiment de simulare constă în acoperirea cât mai mult posibil a tuturor situațiilor reale în care s-ar putea găsi sistemul, cu scopul de a selecta acele regimuri de funcționare care realizează optimul în raport cu un anumit criteriu prestabilit. Întrucât modelul de simulare este un model stohastic, această planificare trebuie să se facă după procedee stohastice.
i) – Analiza și interpretarea rezultatelor simulării:
Acesta este stadiul final al unui experiment de simulare. Această fază constă în colecționarea datelor simulate și prelucrarea lor primară prin procedee stohastice. Aceasta întâmpină, însă, o serie de dificultăți, datorită faptului că procedeele obținute prin simulare nu sunt nici complet aleatoare și nici independente stohastic, așa cum cer procedurile stohastice uzuale, de prelucrare. Mare parte din aceste inconveniente dispar dacă pentru generarea variabilelor de intrare se folosesc generatori de bună calitate
Este foarte important faptul că între aceste etape există o strânsă dependență, motiv pentru care unele dintre ele pot fi contopite
În concluzie, simularea reprezintă o tehnică foarte importantă de monitorizare și asistare în cadrul proiectării, implementării și supervizării rețelelor de comunicații.
3.2. Rolul optimizării și metode de
optimizare în proiectarea rețelelor
Rețeaua de comunicații reprezintă un ansamblu complex format din echipamente și mijloace tehnice capabile să asigure, la cerere, interconectarea oricăror utilizatori și să permită transportul în condiții de calitate superioară, a informațiilor între terminalele interconectate. Informațiile în format analogic sau numeric, corespunzătoare fiecărui tip de utilizator, pot reprezenta semnale vocale, imagini fixe sau în mișcare, date numerice, texte, etc.
În cadrul evoluției în timp, rețeaua de comunicații este supusă unei dezvoltări susținute și continue. Având în vedere volumul investițiilor necesare realizării acesteia, dar și dezvoltării ei continue, trebuie ca deciziile luate pentru realizarea ei să fie optime din punctul de vedere al cerințelor impuse, deoarece ele au consecințe hotărâtoare de-a lungul multor ani.
Optimizarea structurii și funcționării unui sistem de comunicații urmărește realizarea unei concordanțe depline între intrările și ieșirile acestuia, între starea acestuia și cea a sistemului de supervizare din care face parte, între parametrii informaționali și cei funcționali ai acestuia și indicatorii globali de eficacitate.
Optimizarea sistemelor de comunicații nu se poate face pe baza intuiției și a experienței acumulate, ci se impune aplicarea unor metode cantitative de calcul a parametrilor de structură, informaționali, funcționali, de fiabilitate și viabilitate pornindu-se de la elementele determinante pentru rețelele de comunicații și anume:
costurile necesare pentru realizare;
traficul de informații;
tipurile de transmisii, etc.
Ca urmare, este necesar să se înlocuiască sau să se completeze vechile metode de planificare, analiză și sinteză bazate pe intuiție și experiență cu metode științifice bazate pe aplicarea cercetării operaționale, ciberneticii și informaticii. Acestea din urmă oferă posibilități de optimizare fundamentate matematic și astfel prelucrarea datelor devine mai eficientă.
Rețelele de comunicații nu trebuie să fie privite simplist, ca un ansamblu de centre și lini de comunicații interconectate, fără a se evidenția echipamentele de automatizare, componentele software și bazele de date. Acestea trebuie analizate pe baza teoriei informaticii și ciberneticii, iar proiectarea acestora se fundamentează prin cercetarea operațională, ce cuprinde activități de analiză, modelare și evaluare a proceselor cu caracter repetitiv și rezultat măsurabil. Acest fapt permite stabilirea soluției celei mai indicate din mulțimea alternativelor posibile.
Principalele criterii care stau la baza proiectării unei rețele de comunicații sunt următoarele:
Cost minim: se urmărește minimizarea costurilor totale de realizare;
Încredere maximă: încrederea rețelei reprezintă un element de maximă importanță în cadrul sistemelor orientate pe comunicații;
Complexitatea: variantele de realizare a rețelelor cu complexitate mare trebuie evitate, deoarece problemele care își pot face simțită prezența în cadrul ei depind direct proporțional de radicalul complexității ei;
Costul software-ului: pentru realizarea unei supervizări dorite este nevoie de software, dar folosirea excesivă a acestuia duce la creșterea costului total;
Flexibilitate și expandabilitate: este necesar să se aleagă tehnicile software și hardware care pot fi ușor modificate și expandate mai târziu.
Datorită faptului că realizarea unei rețele de comunicații implică costuri ridicate, încă din etapa de proiectare a acesteia trebuie să se folosească procedee de optimizare și simulare cu scopul de a îndeplini criteriile de mai jos.
Fiecare variantă de implementare a rețelei are o încredere caracteristică proprie. La nivelul primelor două criterii apare o tatonare astfel încât să se evalueze corect costul suplimentar necesar pentru a realiza varianta cu încrederea dorită.
3.3. Etapele de analiză în cadrul proiectării
rețelelor de comunicații
În cadrul ingineriei de proiectare a rețelelor de comunicație analiza este făcută în trei etape, după cum urmează:
– calculele primare (Paper Calculation);
– modelele analitice programabile (Programable Analytical Models);
– modelele de simulare (Simulation models).
În cadrul primei etape, pe baza unor calcule brute, se urmărește dacă anumite idei sunt fezabile, putându-se alege din mai multe variante. Exemple de asemenea calcule ar putea fi: variațiile timpului de răspuns, priorități, viteza de transmisie, etc.
În cea de a doua etapă se efectuează calcule mai elaborate, se pot dezvolta programe pe calculator, se ridică grafice, etc. pe baza unor modele analitice care încearcă o aproximare a sistemului real. Exemple de asemenea calcule pot fi: optimizarea distribuției geografice a liniilor de comunicație, programarea modelelor folosind teoria cozilor, etc.
Modele matematice, chiar și programabile, conțin presupuneri simplificatoare, ele reprezentând parțial comportarea echipamentelor de comunicații. Pentru a obține o reprezentare mult mai exactă trebuie să se folosească modele de simulare. Programele de simulare necesită timpi mai mari de descriere, dar și de rulare.
Modelele matematice de înaltă fidelitate, pentru a putea fi procesate de calculator, sunt greu de construit. Ca urmare, în cadrul proiectării se optează pentru modele de simulare. Adesea, un model matematic aproximativ poate să fie mai relevant și folositor decât un model de simulare exact datorită ușurinței cu care în cadrul primului se modifică variabilele și se realizează observarea efectelor acestor modificări.
3.4. Metode de scădere a costurilor rețelelor
de comunicații
În situația unei creșteri continue a complexității rețelelor de comunicații, scopul principal constă în minimizarea costurilor generale de implementare. Rețelele de comunicații ar fi foarte costisitoare dacă nu s-ar folosi concentratoare, multiplexoare și alte dispozitive. Tehnica de abordare pentru minimizarea costurilor depinde de liniile de comunicație și de numărul de terminale. Având în vedere criteriul dat de lungimea liniilor de comunicații, avem două situații:
liniile de comunicație sunt lungi: atunci ele necesită costuri ridicate și ca urmare tehnica de minimizare a costurilor liniilor va domina procesul de proiectare a rețelei;
liniile de comunicație sunt scurte: costurile lor devin mai puțin importante și ca urmare costurile terminalelor și dispozitivelor atașate liniilor capătă o importanță sporită în proiectarea rețelei.
Dacă rețeaua trebuie să conecteze un număr mai mare de terminale, costul terminalelor capătă o importanță majoră, deci în cadrul organizării rețelei trebuie să se folosească scheme care să permită proiectarea terminalelor astfel încât costul acestora să fie cât mai redus posibil.
– Liniile de comunicații scurte:
Problema care apare în cadrul acestui tip de linii constă în existența unui număr ridicat de cabluri de scurtă lungime care au un grad de utilizare foarte mic și ca urmare eficiență scăzută. Această problemă apare datorită utilizatorilor care nu vor să împartă același mediu fizic de comunicații între ei atât timp cît ei plătesc pentru el. O soluție pentru această problemă o constituie folosirea unei bucle digitale de mare viteză. Pentru liniile scurte, datele pot fi transmise și fără modem, iar în cazurile în care acesta se folosește, costurile liniilor sunt scăzute deoarece ele au fost proiectate pentru distanțe scurte, având o complexitate scăzută.
– Liniile de comunicații lungi:
În cadrul rețelelor de comunicații în care sunt folosite linii lungi, tehnica de abordare se schimbă. În acest caz liniile sunt mai scumpe și ca urmare trebuie să fie folosite la un grad mult mai ridicat. Dacă liniile au lungimi care depășesc zeci de kilometrii, costul liniilor domină proiectarea rețelei.
Primul pas în abordarea problemei de creștere a eficienței se poate face prin intermediul proiectării de modemuri bune, deși acestea conferă rezolvarea problemei doar într-o fracțiune mică. Următorul pas pentru a obține structura optimă de implementare se face folosind o serie de algoritmi care au fost realizați de către numeroase organizații de proiectare a rețelelor de comunicații. În general, algoritmii matematici se bazează pe presupuneri simplificatoare, unii fiind concepuți să ia în calcul doar lungimile liniei, alții doar traficul pe care acestea trebuie să le suporte, etc.
O variantă de metodă de implementare a unei rețele caracterizate de cost minim, folosind linii multiple, ar putea fi următoare:
determinarea încărcării de trafic corespunzătoare fiecărui nod;
determinarea numărului de terminale alocate fiecărui nod;
determinarea încărcării maxime pe care linia poate să o suporte concomitent cu îndeplinirea cerințelor legate de timpul de răspuns;
marcarea nodurilor pe o hartă potrivită în timpul proiectării;
începând cu punctele cele mai îndepărtate, o linie poate uni nodurile până când acea linie atinge încărcarea maximă posibilă sau numărul maxim de terminale permis; această linie este atașată la nodul central; trebuie încercate diferite combinații cu scopul de a minimiza lungimea totală a liniei respective;
liniile de interconectare fiind stabilite, pe baza tabelelor cu distanțele între noduri se pot obține costurile necesare realizării liniilor.
Soluțiile pentru minimizarea costurilor rețelelor de comunicații care folosesc linii lungi pot fi următoarele:
Liniile multipunct: terminalele sunt conectate la aceeași linie, linie care asigură calea minimă între ele. În situația în care se constată că linia respectivă are o încărcare ridicată, atunci pot exista mai multe linii multipunct care pot realiza o distribuție echilibrată a traficului;
Multiplexoare: se urmărește multiplexarea canalelor de viteze scăzute pentru a se obține un canal cu viteză ridicată: de exemplu, 16 canale a câte 150 biți/s vor da un canal de 2400 biți/s.
Buffere și unități de control a terminalelor: se folosesc deoarece terminalele operează la viteze diferite de viteza optimă din linie, dar folosirea acestora va duce implicit la creșterea costurilor terminalelor;
Buffere comune: deoarece elementele prezentate la punctul anterior sunt caracterizate de costuri ridicate și sunt folosite ineficient, se pot folosi în comun;
Concentratoare: legătura între nodul principal și concentrator se face prin transmisie sincronă la viteză maximă, iar între concentrator și terminal se face asincron;
Sisteme de comutare a mesajelor sau pachetelor.
Capitolul IV
OPTIMIZAREA REȚELELOR DE COMUNICAȚII LA NIVELUL STRUCTURII TOPOLOGICE
4.1. Importanța și avantajele optimizării
topologice
Principala funcție a unei rețele de comunicații este aceea de a realiza legătura între nodurile sursă și nodurile destinație. Pentru realizarea acestui scop se alege un drum (rută sau cale) de realizare a legăturii. În mod uzual există mai multe căi posibile, selectarea uneia dintre ele se face urmărind satisfacerea unor cerințe adesea contradictorii ale utilizatorilor și ale administratorilor rețelei.
Cele mai importante dintre acestea sunt următoarele:
legătura (transferul de date) să se facă corect și cu operativitate;
să nu existe utilizatori defavorizați;
nodurile și legăturile să fie folosite eficient.
Pentru realizarea funcției de dirijare, deci pentru realizarea legăturii, se cunosc mai mulți algoritmi, clasificarea lor făcându-se din mai multe puncte de vedere, ca de exemplu:
În funcție de adaptarea la condițiile de trafic:
algoritmi de dirijare statică (atunci când conținutul tabelelor de dirijare este fix);
algoritmi de dirijare adaptivă (atunci când conținutul tabelelor de dirijare se modifică în funcție de traficul curent sau de topologia rețelei).
În funcție de locul unde se realizează procesarea (calculele):
algoritmi de dirijare centralizată (care folosesc un algoritm global care utilizează informații despre întreaga rețea pentru a lua decizii optime de dirijare);
algoritmi de dirijare izolată (care utilizează în fiecare nod informații disponibile local);
algoritmi de dirijare distribuită (care utilizează o combinație de informații locale și globale).
În funcție de obiectivele urmărite:
algoritmi de dirijare care asigură transmiterea pe cale optimă, pentru fiecare pereche sursă-destinație;
algoritmi care minimizează întârzierea medie globală de transmitere a pachetelor de date.
Mai multe din rețele operaționale includ algoritmi din prima categorie (cea pe calea optimă), iar algoritmii din cea de-a doua categorie conduc la o dirijare bifurcată mai greu de gestionat practic și de aceea sunt folosiți cu predilecție în proiectarea la nivel topologic și mai puțin ca metode efective de dirijare.
După cum am prezentat în cadrul primului capitol, pentru rețele de comunicații care se întind pe suprafețe mari, adică folosesc linii lungi, liniile sunt scumpe și ca urmare trebuie să fi folosite la un grad mult mai ridicat. Dacă liniile au lungimi care depășesc zeci de kilometri costul liniilor domină proiectarea rețelei. Ca urmare, pentru a obține rețeaua dorită cu costuri minime, trebuie să realizăm o optimizare a ei la nivel topologic.
O etapă foarte importantă pentru a obține structura rețelei de cost minim de implementare este aceea de folosire a algoritmilor de optimizare.
Algoritmii de optimizare, pe lângă procesul de proiectare, pot să fie folosiți în cadrul rețelei de comunicații atunci când se dorește obținerea unei căi de obținere a mesajelor, apelurilor, fișierelor între toate nodurile din cadrul rețelei pe baza unor criterii bine fundamentate, criteriile putând fi de distanță, de probabilitate de realizare a legăturii, de flux, etc. Inexistența unui criteriu bine argumentat de alegere a unui drum din cadrul unei mulțimi posibile de drumuri duce la nedeterminare și ca urmare la pierdere de timp.
În plus, după cum vom prezenta în cadrul acestui capitol există o strânsă legătură între structura topologică și erorile de transmisie. Ca urmare, un avantaj al optimizării structurii topologice este acela al minimizării numărului de erori de transmisie.
Obținerea soluțiilor problemelor de optimizare a structurii topologice după un anumit criteriu în cadrul rețelelor de complexitate mică se poate face și mental. În momentul în care rețelele au complexitate ridicată și se cere optimizarea după mai multe criterii, soluțiile se pot obține numai pe baza unor algoritmi elaborați care sunt implementați pe calculator.
4.2. Modelarea matematică a structurii
topologice
După cum am văzut, modelarea este o metodă de analiză și optimizare a sistemelor reale de comunicații prin substituirea acestora (având la bază identificarea unor asemănări fizice și matematice) între cele două sisteme studiate în raport cu anumite caracteristici stabilite. Cu cât modelul de studiat este mai detaliat, cu atât acesta reflectă mai exact caracteristicile si performanțele sistemului real.
Modelarea unui sistem de comunicații (rețele) presupune găsirea unei relații care să îndeplinească condițiile următoare:
modelul să reprezinte o aproximare suficientă a sistemului real;
să asigure o concordanță deplină între elementele procesului fizic și cele ale modelului său matematic.
Modelul matematic reprezintă ansamblul relațiilor logico-matematice care definesc caracteristicile stărilor sistemului și prin intermediul lor, ieșirile acestuia, în funcție de parametrii și intrările sale dar și de condițiile inițiale. Ca urmare modelarea sistemelor de comunicații prin intermediul grafurilor reprezintă o modelare matematică.
Studierea rețelelor de comunicații în cercetare folosind matematica este dedicată găsirii atributelor lor care satisfac anumite condiții impuse, folosind proprietățile linilor (cunoscute în teoria grafurilor ca arce) și a modului lor de dispunere.
În calitate de model al structurii oricărei rețele de comunicație se folosește graful legăturilor, în care nodurile acestuia reprezintă nodurile de comunicații iar muchiile corespund direcțiilor de legătură. Ca urmare, principalele elemente ele modelului matematic al rețelei de comunicații sunt:
nodurile : care reprezintă centrele de comunicație care sunt în număr de n și formează mulțimea N;
arcele : reprezintă liniile de legătură care există fizic în cadrul sistemului de comunicații între oarecare două centre de comunicație și formează mulțimea A;
În concluzie, orice sistem de comunicație poate fi modelat matematic prin intermediul unui graf care se notează (N;A), un exemplu de asemenea graf fiind prezentat în cadrul figurii ce urmează:
1
2 3
5 6
4
n-2 n-1
n
Fig. 4.1 Graful asociat rețelei
Graful asociat rețelei are pentru toate arcele o valoare caracteristică a unui atribut, în funcție de criteriul după care se face optimizarea: distanță, flux de transmisie sau probabilitate de realizare a legăturii. Un arc (i, j) realizează legătura între nodurile i și j. Arcele pot fi de două feluri: orientate și neorientate.
Pentru optimizare în cadrul grafurilor neorientate valoarea atributului corespunzătoare oricărui arc din cadrul rețelei se definește conform formulei (3.1):
unde – a reprezintă valoare caracteristică arcului respectiv.
Definirea este valabilă atât pentru distanță (cost) dar și pentru probabilitatea de realizare a legăturii p(i, j). În cadrul grafurilor orientate prima egalitate din cadrul relației anterioare nu se mai respectă, partea a doua rămânând însă valabilă.
Modelarea prin intermediul grafurilor neorientate se folosește, în general, în momentul în care se dorește optimizarea după atributul distanță și probabilitatea de realizare a legăturii iar grafurile orientate în situația în care optimizarea se face după fluxul informațional.
Un lanț între două noduri s și t este o mulțime de arce ce unesc cele două noduri. Acest set de arce parcurg noduri intermediare și nu este necesar ca sensul lor să fie același, unele fiind direcționate de la s la t, iar altele de la t la s.
O cale între s și t este un lanț între cele două noduri, în care toate arcele sunt orientate de la s la t.
Un ciclu este un lanț la care nodul de plecare s se identifică cu nodul de sosire t.
Un circuit este o cale la care nodul sursă s și cel destinație t se confundă.
Un lanț sau o cale se numește simplă dacă nu conține cicluri sau circuite.
Un graf parțial (N,A’) al grafului (N,A) este un graf obținut dintr-un subset al lui A și mulțimea N.
Un subgraf (N’, A’) al grafului (N,A) este un graf obținut dintr-un subset de noduri N’N și subsetul corespunzător de arce A’A.
Grafurile pot fi conexe sau nonconexe. În grafurile conexe, între oricare două noduri, există un lanț.
Considerăm un graf de forma (N,A) cu N mulțimea de noduri și A mulțimea de arce. Structura grafului oricărei rețele poate fi descrisă matematic și memorată (pentru că vom realiza programe de optimizare) sub formă matriceală, relațiile din cadrul grafului și mărimile caracteristice fiind exprimate prin următoarele matrice (de ordin date de ordinul lui N):
matricea legăturilor nemijlocite sau a adiacențelor: este o matrice pătratică care ne informează dacă între nodul i și nodul j există legătură, având doar legăturile următoare: 0 dacă nu există legătură și 1 dacă aceasta există. Această matrice pătratică este o matrice simetrică iar elementele de pe diagonala principală sunt egale cu unitatea;
matricea fluxului de informații: reprezintă o matrice pătratică simetrică dacă graful este neorientat și nesimetrică în caz contrar. Ea memorează fluxul mediu de comunicări care au loc în unitate de timp între oricare două noduri ale rețelei. Elementele de pe diagonala principală sunt egale cu zero;
matricea capacității reale de transmitere: este o matrice pătratică la care elementele de pe diagonala principală sunt infinite iar celelalte elemente pot reprezenta atât numărul de canale pe direcțiile de comunicație dar și viteza de transmisie;
matricea probabilităților de realizare a legăturilor: este o matrice pătratică simetrică, cu elementele de pe diagonala principală unitare, iar restul elementelor subunitare;
matricea distanțelor nemijlocite: este o matrice pătratică simetrică cu elementele de pe diagonala principală egale cu zero iar celelalte elemente definite așa cum am prezentat anterior.
După cum am precizat anterior, costul fiind direct proporțional cu distanța, matricea distanțelor este echivalentă cu cea a costurilor, optimizarea după criteriul de distanță fiind similar cu cel de cost.
Fiecare dintre aceste matrice au avantajele și dezavantajele lor, alegerea între ele făcându-se pe baza a două considerente, primul fiind reprezentat de criteriul de optimizare iar cel de-al doilea de gradul de simplificare pe care o conferă utilizarea sa în cadrul optimizării.
4.3. Noțiunea de algoritm
Progresele obținute în domeniul calculatoarelor electronice au influențat în sens pozitiv dezvoltarea metodelor de calcul numeric. Îmbunătățirile aduse echipamentelor, gestiunii resurselor și tehnicilor moderne de prelucrare a informației au condus la apariția unor metode de calcul, a unor algoritmi, a unor criterii de alegere a diverselor metode ce se pot aplica aceleiași probleme date, precum și la fundamentarea unei teorii a analizei numerice care furnizează o serie de elemente ce permit măsura calitativă a unei aproximări sau a unei metode iterative.
4.3.1. Definiții și caracteristici ale algoritmilor
Noțiunea de algoritm reprezintă baza programării calculatoarelor electronice. În dicționarul “Vollstaduges Mathematisches Lexicon”, apărut la Leipzig în secolul al XVIII-lea, se dădea definiția cuvântului alghoritmus astfel: se înțelege prin această descriere o combinare a celor patru tipuri de operații aritmetice, adică adunarea, înmulțirea, scăderea li împărțirea. În situația actuală definiția nu mai corespunde.
Definiția 1:
Numim algoritm o prescripție care determină un anumit proces de calcul și care este precisă, perfect inteligibilă și nu admite nici un fel de interpretări din partea celui care o duce la îndeplinire.
Înțelesul modern de algoritm este destul de apropiat de cel de rețetă, proces, metodă, procedură, rutină.
Definiția 2:
Algoritmul reprezintă un set de reguli care dă o secvență de operații pentru soluționarea unui tip specific de probleme.
Caracteristicile unui algoritm:
generalitate = algoritmul nu trebuie să rezolve numai o problemă, ci toate problemele din clasa respectivă;
finititudine = numărul de transformări intermediare aplicate asupra informației inițiale pentru a obține informația finală este finit;
unicitate = toate transformările intermediare aplicate asupra informației inițiale sunt unic determinate de regulile algoritmului; acesta trebuie să precizeze ordinea strictă a transformărilor; de asemenea, regulile precizează în ce caz se obține informația finală, după care activitatea algoritmului se întrerupe;
claritate = fiecare pas al unui algoritm trebuie definit în mod precis; ordinele date trebuie specificate în mod riguros și fără ambiguități;
eficacitate = orice algoritm trebuie să ne conducă la rezultatul scontat în timp optim; toate operațiile ce urmează a fi executate în algoritm trebuie să fie suficient de fundamentate încât, în principiu, să poată fi făcute exact și într-un interval finit de timp;
intrarea = un algoritm are una sau mai multe intrări constituite din cantitățile inițiale care îi sunt date înainte ca algoritmul să înceapă; aceste intrări sunt luate dintr-un set specific de obiecte;
ieșirea = un algoritm are una sau mai multe ieșiri, adică acele cantități ce sunt într-o relație specifică cu intrările.
În concluzie, un algoritm de calcul trebuie descris în mod complet astfel încât altcineva să îl poată aplica corect și ușor, iar descrierea regulilor algoritmului să nu conducă la confuzii, nedumeriri.
Din punct de vedere structural un algoritm cuprinde, în general, următoarele etape:
etapa de inițializare;
etapa de calcul;
etapa finală.
Etapa de inițializare și cea finală au rolul de a preciza informația inițială, respectiv finală, fără a se aplica transformări efective asupra unor informații. În etapa de calcul se aplică o prelucrare (transformare) efectivă a informației și ea conține, de obicei, instrucțiuni de calcul și de decizie.
4.3.2. Descrierea algoritmilor
După ce un algoritm este elaborat, el trebuie prezentat într-o forma accesibilă omului sau calculatorului. Această operație este denumită descrierea
algoritmului. Această descriere se poate face în mai multe moduri, fiecare formă având avantajele și dezavantajele ei:
printr-un limbaj logico-matemetic;
cu ajutorul schemelor logice;
prin intermediul limbajelor de programare, etc.
a) – Descrierea cu ajutorul schemelor logice:
Înaintea etapei de programare trebuie efectuată o analiză minuțioasă a algoritmilor de calcul pentru a lua în considerare toate situațiile care apar în procesul de calcul. Pentru aceasta se utilizează schema logică. Ea este o reprezentare grafică a algoritmului prin care fiecărei etape din structura sa I se atașează un simbol numit bloc, iar modul de înlănțuire a acestor blocuri este dat prin segmente orientate.
Simbolurile blocurilor dintr-o schemă logică și semnificația lor sunt prezentate în continuare:
a) – Descrierea cu ajutorul limbajului algoritmic:
Descrierea algoritmului prin intermediul schemelor logice se dovedește uneori destul de greoaie din cauza dificultăților legate de reprezentarea, inserarea comentariilor, etc., la care se adaugă citirea dificilă. De aceea, s-a căutat o altă modalitate de descriere cât mai apropiată de cea liniară, ajungându-se la un limbaj algoritmic, care conține câteva subscheme frecvent utilizate.
4.4. Metode de elaborare a algoritmilor
De multe ori, puși în fața unei probleme pentru care trebuie să elaborăm un algoritm, nu știm cum să începem. În continuare vor fi prezentate mai multe metode generale de elaborare a algoritmilor care, dacă sunt bine însușite, pot ajuta la rezolvarea unor clase de probleme.
4.4.1. Recursivitate
Despre un obiect se spune că este recursiv dacă de poate defini în funcție de el însuși. Recursivitatea se întâlnește nu numai în matematică, ci și în viața de toate zilele. Ea reprezintă un instrument matematic puternic de definire a conceptelor. Exemple în acest sens sunt numerele naturale, arborii și anumite funcții.
Puterea de exprimare a recursivității constă în posibilitatea definirii unei mulțimi infinite de obiecte cu ajutorul unui număr finit de afirmații. Într-o manieră similară se poate defini un număr infinit de calcule printr-un program recursiv, chiar dacă acesta nu conține repetări explicite. Algoritmii recursivi se dovedesc a fi potriviți în cazul în care problema care trebuie să fie rezolvată, funcția care trebuie calculată sau structurile de date aferente sunt definite în manieră recursivă.
Instrumentul necesar și suficient folosit la exprimarea calculelor recursive este procedura sau subrutina, deoarece acest mecanism permite identificarea printr-un nume a mai multor instrucțiuni. Acest nume este folosit pentru apelarea secvenței de instrucțiuni. O procedură P care conține o referire explicită la ea însăși se numește direct recursivă. Dacă P conține o referire la o altă procedură Q care conține o referire directă sau indirectă la P, atunci P se numește indirect recursivă. Ca atare, folosirea recursivității poate uneori să nu fie evidentă.
Unei proceduri i se asociază de obicei un set de obiecte locale, ca de exemplu variabile, constante, tipuri și proceduri care sunt definite local și nu au semnificație în afara procedurii. Ori de câte ori este activată recursiv o procedură, se creează setul corespunzător de variabile locale. Deși aceste
variabile au același nume ca și elementele corespunzătoare funcției apelate anterior, ele sunt distincte față de acestea. Aceeași regulă este valabilă și pentru parametrii procedurii, care prin definiție sunt legați de această procedură.
Procedurile recursive por conduce, la fel ca și instrucțiunile repetitive, la existența unor calcule infinite. De aceea este necesară rezolvarea problemei în timp finit. O cerință fundamentală în acest sens este existența unei condiții B, care la un moment dat devine falsă, caz în care se încheie apelarea recursivă. Schema corespunzătoare de apel recursiv poate fi descrisă astfel:
procedura P este
dacă B atunci
S
execută P
sfârșit
Cea mai des folosită tehnică pentru demonstrarea terminării apelului recursiv constă în definirea unei funcții f(x), astfel încât f(x) 0 determină terminarea apelului recursiv. Dacă se poate demonstra că la fiecare apel valoarea funcției scade, se poate demonstra caracterul finit al calculului descris de procedura respectivă. O metodă evidentă constă în asocierea unui parametru, de exemplu n, apelul recursiv al unei funcții făcându-se pentru o valoare n-1 a parametrului corespunzător. Acest lucru poate fi exprimat de următoarea schemă de program:
procedura P(n) este
dacă B atunci
S
execută P(n-1)
sfârșit
În aplicațiile practice este de dorit să se arate că adâncimea finală a apelului recursiv nu este numai finită, ci și mică. Motivul este acela că fiecare activare recursivă a unei proceduri conduce la executarea unor operații în plus, precum și la necesitatea utilizării unei cantități mai mare de memorie.
Algoritmii recursivi sunt potriviți în cazul în care problema care trebuie rezolvată sau datele care urmează a fi prelucrate sunt definite în manieră recursivă. Aceasta nu înseamnă că astfel de definiții recursive garantează faptul că algoritmul recursiv corespunzător este cea mai bună metodă de rezolvare a problemei.
4.4.2. Metoda Greedy
Este poate cea mai directă tehnică de prelucrare a algoritmilor și mai mult, poate fi aplicată la o gamă largă de probleme. Majoritatea acestor probleme constau în determinarea unei submulțimi B a unei mulțimi A cu n elemente, care să îndeplinească anumite condiții pentru a fi acceptată. Orice astfel de submulțime care respectă aceste restricții se numește soluție posibilă. Din mulțimea tuturor soluțiilor posibile se dorește determinarea unei soluții care maximizează sau minimizează o funcție de cost. O soluție posibilă care realizează acest lucru se numește soluție optimă. Considerăm că soluțiile posibile au următoarea proprietate: dacă B este o soluție posibilă, atunci orice submulțime a sa este o soluție posibilă.
Având în vedere cele de mai sus, se poate construi un algoritm care operează în etape, considerând pe rând câte un element din A. în fiecare etapă se decide dacă o soluție este sau nu optimală. Acest lucru este realizat dacă se consideră pe rând câte un element din A, într-o ordine dată de o procedură de selecție. Dacă adăugarea acestui element conduce la o soluție imposibilă, se renunță la adăugarea sa în soluția parțială. Procedura de selecție are la bază un cost, care poate fi sau nu identic cu costul care stabilește dacă o soluție posibilă este optimă sau nu.
Procedeul Greedy poate fi descris mai precis dacă se consideră algoritmul:
funcția GREEDY (A,n) este
B
pentru i = 1, n, 1 repetă
x SELECT (a)
dacă POSIBIL (B,x) atunci
B UNION (B,x)
GREEDY B
sfârșit
funcția UNION (B,n) este
k k+1
B(k) x
UNION B
sfârșit
Funcția SELECT alege un element din A, îl elimină și atribuie această valoare lui x. funcția POSIBIL este o funcție booleană care stabilește dacă elementul x poate fi adăugat în mulțimea B. procedura GREEDY descrie modul general în care funcționează un algoritm de această natură.
După cum se vede, metoda Geedy nu încearcă să determine toate soluțiile posibile și s-o stabilească apoi pe cea optimală, comparând costurile. Ea alege pe rând câte un element, urmând ca eventual să-l adauge. De aici vine și numele de greedy (lacom, în engleză).
Partea cea mai delicată a proiectării unui algoritm în maniera Greedy o constituie răspunsul la întrebarea: este soluția oferită de metoda Greedy optimală? În cazul în care soluția nu este optimală, ea reprezintă o aproximare a soluției optimale și, ca atare, trebuie analizat modul în care se realizează aproximarea.
Metoda backtracking
Această metodă se folosește în cazul problemelor a căror soluție se prezintă sub forma x1, x2, … , xi, …
O metodă simplă de determinare a soluțiilor constă în a genera într-un mod oarecare toate soluțiile posibile și de a verifica dacă ele satisfac condițiile interne. Dezavantajul constă în faptul că timpul cerut de această investigare exhaustivă este foarte mare. Metoda determină aceste șiruri prin încercări succesive de extindere a unei soluții parțiale. În fiecare etapă a căutării pentru care nu este posibilă o extindere a soluției parțiale curente, se revine la o soluție parțială anterioară și se încearcă din nou. În mod curent, metoda este utilizată pe scară largă pentru rezolvarea problemelor combinatorice din domeniul analizei sintactice, jocurilor și optimizărilor.
Să presupunem că soluția unei probleme constă dintr-un vector (x1, x2, …) de lungime neprecizată, dar finită. Acest vector satisface anumite restricții care se referă la componentele sale. Orice element xi aparține unei mulțimi finite, total ordonate, Ai. Pentru a determina soluțiile problemei, trebuie să se considere toate elementele produsului cartezian
A1 A2 … Ai cu i 0.
Procesul de generare începe cu soluția parțială formată de vectorul vid. Vom alege ca primă componentă pe cel mai mic element din mulțimea A1. În general, dacă soluția parțială curentă este (x1, x2, … , xk) se verifică întâi dacă este soluție, apoi se încearcă extinderea sa la soluția (x1, x2, … , xk, xk+1) cu xk+1 din Ak+1. Dacă extinderea nu este posibilă, atunci se revine la soluția (x1, x2, … , xk, xk-1) și se încearcă o nouă alegere a valorii xk. această valoare poate fi aleasă din submulțimea Sk a mulțimii Ak. Mulțimea Sk conține toate elementele lui Ak care nu au fost încercate. Algoritmul se oprește în momentul în care au fost încercate toate elementele mulțimii A1.
Algoritmul poate fi descris în mod formal astfel:
procedura BACKTRACK este
k 1
S1 A1
cât_timp k > 0 repetă
cât_timp S k 0 repetă
xk *cel mai mic element din sk
sk sk – {xk}
dacă *x este soluție atunci
*memorează soluția
k k-1
*calculează sk
k k – 1
sfârșit
Fig. 4.3 Graful asociat
Acest proces poate fi reprezentat cu ajutorul unui arbore care reprezintă mulțimea soluțiilor parțiale. Reprezentarea se face după cum urmează:
rădăcina arborelui este reprezentată de vectorul nul;
fii unui nod de pe nivelul k–1 reprezintă elementele mulțimii Ak.
În situația descrisă în figura precedentă, algoritmul parcurge arborele în ordinea indicată de săgețile punctate. O astfel de căutare este numită și căutare depth-first. Această căutare a fost utilizată pentru câteva probleme de grafuri, el dând totodată și o procedură recursivă pentru metoda backtracking.
Metoda programării dinamice
Programarea dinamică este o metodă de proiectare a algoritmilor care poate fi utilizată în cazul în care soluția problemei poate fi privită ca rezultatul unei succesiuni de decizii. De remarcat faptul că este posibil ca decizia luată la un moment dat să depindă de cele luate în etapele anterioare (în cazul metodei Greedy fiecare decizie care se ia este independentă de celelalte).
O modalitate de rezolvare a problemelor pentru care nu este posibil să se efectueze o secvență de decizii care să conducă la soluția optimă constă în încercarea tuturor secvențelor posibile de decizii. Programarea dinamică oferă posibilitatea reducerii drastice a secvențelor de decizii, eliminându-le pe cele care nu conduc la soluția optimă.
La baza programării dinamice stă principiul optimalității, care afirmă că secvența optimală de decizii d1, … , dn care transformă starea S0 în S1, … , Sn are proprietatea că indiferent de starea inițială Sk și de decizia care se ia, deciziile rămase trebuie să formeze o secvență optimală de decizii pentru stările Sk și Sn.
Diferența dintre programarea dinamică și metoda Greedy constă în faptul că cea din urmă generează o singură secvență de decizii, în timp ce metoda programării dinamice poate genera mai multe secvența de decizii.
Metoda programării dinamice constă în stabilirea relațiilor de recurență în deciziile care se iau și apoi în rezolvarea acestora. De obicei, relațiile de recurență sunt de două feluri:
înainte, atunci când orice decizie di depinde de deciziile di+1, … , dn caz în care decizia se ia în ordinea dn, dn-1, … , d1;
înapoi, atunci când orice decizie di depinde de deciziile d1, d2, … , di-1, iar deciziile se iau în ordinea d1, d2, … , dn.
Metoda “Branch and Bound”
Metoda “Branch and Bound” (“ramifică și mărginește”) este înrudită cu metoda backtracking. Diferențele constau în ordinea de parcurgere a arborelui spațiului de soluții (stări) și în modul în care se elimină subarbori care nu pot conduce la rezultat.
Metoda va folosi o listă în care vor fi înscrise vârfuri ale arborelui spațiului de stări pentru a fi prelucrate la un moment ulterior; vârfurile din această listă se numesc vârfuri active. Dintre vârfurile active se alege câte un vârf pentru a fi prelucrat; el se numește vârf curent.
În privința ordinii de parcurgere vârfurilor arborelui spațiului de stări, metoda de față diferă de metoda backtracking prin aceea că în momentul în care un vârf activ devine vârf curent, sunt generați (determinați) toți descendenții săi,
aceștia devenind vârfuri active (fiind deci adăugate listei vârfurilor active), după care unul dintre elementele acestei liste devine vârf curent.
Metoda “Divide et impera”
Metoda “Divide et impera” (“desparte și stăpânește”) este o altă metodă generală de elaborare a algoritmilor. Rezolvarea unei probleme se poate face uneori astfel: se partiționează problema în părți mai mici, se rezolvă fiecare parte separat și apoi se combină soluțiile, obținându-se soluția finală. Această abordare conduce, mai ales atunci când este folosită recursiv, la soluții eficiente pentru probleme la care subproblemele sunt versiuni mai mici ale problemei inițiale.
Metode euristice
Mare parte din algoritmii prezentați au comportare în timp exponențială, fapt care face uneori total neeficientă utilizarea lor. Din acest motiv se acceptă adesea utilizarea (pentru problemele respective) a unor algoritmi despre care nu se știe sau nu s-a demonstrat deocamdată că sunt optimali, dar care furnizează rezultate “acceptabile”, într-un timp mai scurt. O situație analogă poate avea loc și cu privire la aria de memorie necesară, dar datorită importanței mai mari a criteriului timp față de criteriul necesarului de memorie, se va prezenta numai analiza timpului.
Un algoritm se numește euristic dacă are următoarele proprietăți:
furnizează de obicei soluții “bune”, dat nu neapărat optimale;
poate fi implementat mai ușor și permite obținerea rezultatelor într-un timp rezonabil, în orice caz mai scurt decât cel cerut de orice algoritm exact cunoscut.
Una din ideile frecvent utilizate în elaborarea algoritmilor euristici constă în descompunerea procesului de căutare a soluției (soluțiilor) în mai multe subprocese (etape) succesive, fiecare dintre aceste subprocese fiind optimal. Evident că o asemenea strategie nu poate conduce întotdeauna la o soluție optimală, deoarece alegerea unei soluții optimale la o anumită etapă poate împiedica atingerea în final a unei soluții optime a întregii probleme; cu alte cuvinte, optimizarea locală nu împiedică (în general) optimizarea totală. De exemplu, un algoritm elaborat pe baza metodei Greedy și care furnizează o soluție care nu este optimă (sau nu putem demonstra optimalitatea ei) este un algoritm euristic.
Pentru sistematizarea elaborării unui algoritm euristic, este convenabil să se pună în evidență toate condițiile care le satisface o soluție exactă, după care să se împartă aceste condiții în două (sau mai multe) clase, conform unor anumite criterii. Două asemenea criterii sunt facilitatea, respectiv necesitatea satisfacerii condițiilor enunțate. În primul caz se pot considera următoarele două clase de condiții:
condiții ușor de îndeplinit;
condiții dificil de îndeplinit.
În asemenea situații se poate accepta satisfacerea numai a condițiilor din prima clasă, cu condiția ca ele să fie suficient de cuprinzătoare pentru a se obține o soluție posibilă (chiar dacă nu neapărat optimală); este necesar să se demonstreze că rezultatul obținut este o soluție posibilă.
În al doilea caz menționat anterior, condițiile pot fi împărțite în:
condiții necesare, în sensul că neîndeplinirea lor împiedică obținerea unei soluții posibile a problemei;
condiții pentru care se poate accepta un compromis, în sensul că ele pot fi înlocuite cu alte condiții ce permit apropierea de o soluție optimală (eventual chiar obținerea unei soluții optimale).
Într-o asemenea situație, satisfacerea condițiilor din prima clasă este obligatorie, iar calitatea soluției depinde în mare măsură de compromisul adoptat pentru condițiile din a doua clasă.
Mai trebuie menționate următoarele două aspecte:
algoritmii euristici sunt folositori și în situația în care ei sunt utilizați o singură dată (sau de puține ori), caz în care efortul de determinare a unei soluții optime este prea mare față de câștigul obținut;
deși algoritmii euristici pot la prima vedere să șocheze un matematician “pur”, situația este de cele mai multe ori exact inversă; într-adevăr, toți algoritmii din analiza numerică (încadrată în “matematica pură”) furnizează soluții aproximative chiar teoretic, fără a pune la socoteală propagarea erorilor de rotunjire, care sunt greu controlabile și pot schimba uneori un proces convergent într-unul divergent.
Capitolul V
ALGORITMI PENTRU OPTIMIZAREA REȚELELOR DE COMUNICAȚII
Pe parcursul acestui capitol se vor prezenta soluții matematice și computaționale, care au drept scop optimizarea rețelelor de comunicații la nivelul structurii topologice, bazate pe teoria grafurilor. Cu această ocazie vor fi elaborate programe de simulare realizate în limbajul de programare DELPHI 5.0, ce vor furniza soluțiile de optimizare ca o frontieră între teorie și practică. Acest limbaj este foarte răspândit în cadrul programării calculatoarelor, în special în procesul de învățământ. Între tehnicile de programare și teoria grafurilor există o strânsă legătură, obținându-se astfel rezultate deosebit de importante prin intermediul mecanismelor specifice de programare (tehnici deja prezentate în capitolul anterior). De exemplu, pentru aflarea ciclurilor hamiltoiniene se folosește metoda backtraking, pentru aflare ciclurilor culeriene folosim tehnica Greedy, pentru aflarea drumurilor optime se poate folosi metoda programării dinamice.
Fiecare metodă de optimizare este prezentată folosind setul următoarelor etape:
prezentarea problemei de optimizare = conține principalele aspecte care intervin în rezolvarea algoritmului respectiv și pregătește noțiunile necesare parcurgerii pas cu pas a algoritmului;
prezentarea algoritmului = în această secțiune sunt parcurși pașii din care este format algoritmul (tratați din punct de vedere teoretic);
prezentarea unui exemplu de funcționare a algoritmului, ținând cont de fiecare pas în parte (tratați din punct de vedre numeric);
observații cu privire la problemele specifice fiecărui algoritm;
implementarea algoritmului = sunt prezentate principalele probleme care intervin în implementarea computațională a algoritmului și variabilele folosite în acest scop;
Analiza și optimizarea rețelelor de comunicații la nivel topologic, atât în faza de proiectare cât și în cea de exploatare a ei, se poate face după următoarele criterii:
distanță:
flux informațional;
probabilitate de realizare a legăturii;
întârziere;
fiabilitate, etc.
În cele ce urmează vor fi prezentate soluții care realizează optimizări la nivelul structurii topologice după criterii de distanță și flux informațional.
Algoritmi simplii pentru grafuri
(arbori minimali)
Un arbore de interes special este arborele minimal. Determinarea acestui tip de arbore are un rol important în cadrul optimizării rețelelor de comunicații la nivel de topologie, atât în faza de proiectare, cât și în cadrul celei de exploatare. Arborele minimal, ales din multitudinea de arbori corespunzători grafului, respectă următoarele condiții:
permite realizarea legăturii între oricare două noduri ale rețelei;
valoarea atributului, corespunzătoare reuniunii de arce, care formează arborele este optimă, adică pentru atributul de distanță (cost) valoarea acestuia este minimă, iar pentru cel de flux informațional este maximă.
Pentru a construi acest arbore se poate folosi o procedură iterativă, începând cu cel mai scurt arc și extinzând în mod gradual la celelalte arce din rețea. Există două moduri distincte de realizare a acestei iterații, acestea fiind prezentate în continuare.
Algoritmul lui J.B. KRUSKAL și
cel al lui R.C. PRIM
Prima metodă, numită și algoritmul lui J.B. Kruskal, permite construirea arborelui parțial de cost minim muchie cu muchie astfel: toate arcele sunt aranjate după lungime și sunt adăugate la setul de arce dacă nu formează un ciclu cu acele arce care deja există în set; această metodă a fost elaborată de J.B. Kruskal și poate conduce la câțiva subarbori care cresc simultan. Graful obținut are n vârfuri, este conex, nu are cicluri și deci este arbore. Evident, trebuie să demonstrăm că arborele construit este de cost minim.
Pentru a doua metodă, numită și algoritmul lui R.C. Prim, metoda Greedy permite construirea arborelui parțial de cost minim astfel: arborele crește constant, de la un arc inițial, iar la fiecare pas al algoritmului arcul care este adăugat este cel mai scurt arc rămas, ce are un vârf în arbore. Deci, pentru a selecta un arc, acele arce care nu fac parte din arborele parțial sunt scanate și împărțite în două seturi: cele care au un nod (și numai unul) în arbore și cele care nu au deloc, sau au două.
Diferența dintre cei doi algoritmi constă în faptul că algoritmul lui Kruskal poate crea câțiva arbori mici până când arborele este complet, pe când algoritmul lui Prim dezvoltă un arbore parțial pentru a deveni arborele dorit.
Algoritmul “Kruskal” pentru o rețea (N,A,D) poate fi etapizat astfel:
Pasul 0: Se inițializează graful T cu n noduri și fără arce;
Pasul 1: Se creează o listă L de arce din cele N, în ordinea ascendentă a
dimensiunilor;
Pasul 2: Se selectează arcul (i,j) din fruntea listei L; dacă acesta formează un
ciclu în T este eliminat din lista L și se repetă pasul 2. Altfel arcul
este transferat din L în T;
Pasul 3: dacă T este arbore, ne oprim; dacă nu, se repetă pasul 2.
Algoritmul “Prim” pentru o rețea (N,A,D) poate fi etapizat astfel:
Pasul 0: Se inițializează graful T cu 1 nod selectat în mod arbitrar și fără arce;
Pasul 1: Se selectează arcul (i,j) cu lungimea cea mai mică, dintre acele arce
(i,l) care îl au pe i în T, iar pe l neaparținând lui T. Se adaugă acest
arc la T și nodul j la setul de noduri aparținând lui T.
Pasul 2: Dacă T este arbore pentru graful (N,A), ne oprim; dacă nu, se repetă
pasul 1.
Exemplu practic de funcționare a algoritmilor:
Se consideră rețeaua prezentată în figura următoare:
Fig. 4.1 Exemplu practic
În acest caz, setul de noduri N este {1,2,3,4,5}, setul de arce A este {(1,2), (2,3), (3,4), (4,5), (1,5), (1,3), (3,5),}, iar matricea distanțelor este:
5 8 10
5 10
8 10 4 7
4 6
10 7 6
Aplicând algoritmul lui J.B. Kruskal pentru acest exemplu, arborele minimal T se formează în modul următor:
Pasul 0: T = ({1,2,3,4,5}, );
Pasul 1: Lista L ordonată este (3,4), (1,2), (4,5), (3,5), (1,3), (1,5), (2,3);
Pasul 2: Arcul (3,4) este transferat din L în T;
L este (1,2), (4,5), (3,5), (1,3), (1,5), (2,3)
T este ({1,2,3,4,5}, {(3,4)});
Fig. 4.2 Evoluția arborelui
Pasul 3: T nu este un arbore, deci se repetă pasul 2;
Pasul 2: Arcul (1,2) este transferat din L în T;
L este (4,5), (3,5), (1,3), (1,5), (2,3)
T este ({1,2,3,4,5}, {(3,4)}, {(1,2)});
Fig. 4.3 Evoluția arborelui
Pasul 3: T nu este un arbore, deci se repetă pasul 2;
Pasul 2: Arcul (4,5) este transferat din L în T;
L este (3,5), (1,3), (1,5), (2,3)
T este ({1,2,3,4,5}, {(3,4)}, {(1,2)}, {(4,5)});
Fig. 4.4 Evoluția arborelui
Pasul 3: T nu este un arbore, deci se repetă pasul 2;
Pasul 2: Arcul (3,5) este acum în fruntea listei L. Dacă acest arc ar fi adăugat
în T ar forma un circuit cu acele arce care deja aparțin lui T (în acest
caz cu arcele (3,4), (4,5)). Deci îl ștergem din listă, L devine (1,3),
(1,5), (2,3) și repetăm pasul 2;
Pasul 2: Arcul (1,3) este transferat din L în T;
Fig. 4.5 Evoluția arborelui
L este acum (1,5), (2,3)
T este acum ({1,2,3,4,5}, {(3,4)}, {(1,2)}, {(4,5)} , {(1,3)});
T este acum arbore minimal, deci ne vom opri. T este prezentat în
figura următoare, având dimensiunea totală 23.
Fig. 4.6 Arborele minimal
Aplicând algoritmul lui R.C. Prim pentru acest exemplu, arborele minimal T se formează în modul următor:
Pasul 0: Inițializăm pe T = ({1}, );
Fig. 4.7 Evoluția arborelui
Pasul 1: Considerăm arcele (1,2), (1,3), (1,5). Dintre acestea, arcul (1,2) este
cel mai scurt, deci estre adăugat la T; nodul 2 este adăugat la setul de
noduri al lui T, iar T devine: T = ({1,2}, {(1,2)});
Fig. 4.8 Evoluția arborelui
Pasul 2: T nu este un arbore, deci se repetă pasul 1;
Pasul 1: Considerăm arcele (1,3), (1,5), (2,3). Dintre acestea, arcul (1,3) este
cel mai scurt, deci estre adăugat la T; nodul 3 este adăugat la setul de
noduri al lui T, iar T devine: T = ({1,2,3}, {(1,2)}, {(1,3)});
Fig. 4.9 Evoluția arborelui
Pasul 2: T nu este un arbore, deci se repetă pasul 1;
Pasul 1: Considerăm arcele (1,5), (3,4), (3,5). (Arcul (2,3) nu este considerat
deoarece ambele noduri ale sale sunt deja în T).Dintre acestea arcul
(3,4) este cel mai scurt, deci estre adăugat la T; nodul 4 este adăugat
la setul de noduri al lui T, iar T devine: T = ({1,2,3,4}, {(1,2)},
{(1,3)}, {(3,4)});
Fig. 4.10 Evoluția arborelui
Pasul 2: T nu este un arbore, deci se repetă pasul 1;
Pasul 1: Considerăm arcele (1,5), (3,5), (4,5). Dintre acestea arcul, (4,5)
este cel mai scurt, deci estre adăugat la T; nodul 5 este adăugat la
setul de noduri al lui T, iar T devine: T =({1,2,3,4,5}, {(1,2)}, {(1,3)},
{(3,4)}, {(4,5)});
Fig. 4.10 Evoluția arborelui
Pasul 2: T este acum arbore și este arbore minimal pentru rețea.
Fig. 4.11 Arborele minimal
Observații:
Arborele parțial optim trebuie să fie unic.
În metoda lui Kruskal arcele de egală măsură sunt preluate în mod arbitrar. Pentru unele rețele, o schimbare a ordinii ar fi condus la găsirea unui alt arbore. În metoda lui Prim primul nod a fost ales arbitrar. Dacă ar fi fost ales un alt nod, în unele rețele, alt arbore ar fi fost găsit. (În cazul exemplului studiat, arborele găsit este unic.)
Cei doi algoritmi au determinat arborele minimal, în sensul lungimii totale minime. Într-un mod analog se poate defini și arborele maximal, care ar însemna arborele cu lungimea cea mai mare. Pentru aceasta nu este nevoie da alți algoritmi, deoarece ne putem folosi de cei doi prezentați anterior astfel: presupunem arborele maximal dorit. Creăm o rețea (N,A,D’) în care d’(i,j)=M- d(i,j), unde M este un număr mare ales mai mare decât orice legătură din (N,A,D). Arcele aborelui minimal al (N,A,D) sunt arcele arborelui maximal al (N,A,D’).
5.1.2. Implementarea algoritmilor:
Pentru oricare din algoritmi este necesar să se creeze o reprezentare convenabilă a celor trei părți ale unei rețele: setul de noduri, setul de arce și distanțele dintre arce. Pentru aceasta există câteva metode posibile, dintre care, cea mai convenabilă consideră nodurile numerotate consecutiv de la 1 la numărul total de noduri, deci setul de noduri este în mod simplu setul de numere întregi {1,2,3, …, n}. Apoi, arcele și dimensiunile lor pot fi reprezentate într-una din două modalități: în prima modalitate pot fi memorate ca trei vectori unidimensionali reprezentând nodurile de start, nodurile de sosire și dimensiunea legăturii. Dimensiunea acestor șiruri va fi numărul de arce ale rețelei; în a doua modalitate poate fi creată o matrice a dimensiunilor arcelor, care va avea valori reale numai acolo unde arcele corespunzătoare există și valoare infinită acolo unde nu există legătură (pentru programare noțiunea de “infinit” este un concept dificil, deci se va folosi un număr foarte mare). Fiecare dintre aceste posibilități are propriile avantaje și dezavantaje, iar alegerea uneia dintre ele depinde de mărimea problemei care trebuie studiată.
Implementarea algoritmului lui J.B. Kruskal:
Din punctul de vedere al programatorului, cea mai dificilă parte a algoritmului lui Kruskal este testarea formării ciclurilor. Dacă un arc (i,j) preluat pentru a fi inclus în arbore și nici i, nici j nu sunt încă în arbore, atunci nici un ciclu nu poate fi format incluzând acest arc. Dar dacă ambele noduri (și i și j) sunt în arborele parțial, este posibil ca, adăugând acest arc, să ia naștere un ciclu (un ciclu se va forma numai dacă există deja o legătură între i și j).
Pentru cazul programării în DELPHI, va exista o listă a nodurilor care sunt conectate la nodul i, formată în ordinea în care nodurile au fost găsite de program. Această listă este construită prin listarea tuturor nodurilor care sunt conectate direct la nodul i; apoi examinează aceste noduri și adaugă acele noduri care sunt conectate cu el (cu i). Deci, există doi pointeri în listă: unul pentru nodul examinat și unul pentru pasul listei. Întregul proces de scanare este implementat ca o funcție boolean-ă, care are valoarea “true” dacă se formează un ciclu prin includerea unui arc particular.
Arborele este memorat de un vector corespunzător arcelor; arcele care se află în arbore au câte o etichetă, care este suficientă pentru identificarea lor când arborele este produs.
Implementarea algoritmului lui R.C. Prim:
Partea cheie a algoritmului lui Prim este pasul 1, unde unul din criteriile pentru selectarea arcului următor pentru incluziune este faptul că arcul trebuie să aibă un nod în arborele parțial, iar celălalt nod să nu aparțină acestui arbore. Aceasta reclamă ca programul să conțină o cale de a identifica nodurile care aparțin arborelui. În DELPHI, această chestiune se poate face cu ajutorul unui vector boolean variabil, care va avea valoarea “false” pentru nodurile neconectate încă la arborele parțial și valoarea “true” pentru acele noduri care sunt conectate. Apoi, pentru arcele care sunt în mod convenabil candidate la includerea în arbore este necesară verificarea ca un nod să aibă eticheta “true”, iar celălalt “false”. În program, acest lucru este realizat cu o funcție boolean-ă (‘diff’), care este “true” când doar unul dintre noduri are eticheta “true”.
De data aceasta, primul arc ce trebuie inclus nu este ales arbitrar, așa cum algoritmul formal sugerează. În schimb, în timp ce matricea distanțelor este introdusă, programul memorează cel mai scurt arc și este folosit ca fiind primul arc ce se adaugă arborelui. Efectul acestei deviații minore este de a grăbi căutarea în pasul 1, pentru toate cazurile. Dacă nu este găsit nici un arc, variabila ‘minarc’ nu este schimbată și se va afișa un mesaj de avertizare. Întregimea arborelui este verificată prin numărarea nodurilor neincluse în arbore.
În final, trebuie să existe o cale de memorare a arborelui într-o formă convenabilă pentru a permite afișarea lui. Acest lucru poate fi făcut cu o matrice boolean-ă, corespunzătoare matricei distanțelor, dar este mult mai convenabil să folosim chiar matricea distanțelor pentru a memora această informație. Acelor care sunt incluse în arbore l-i se va înmulți valoarea distanței cu valoarea –1; pentru ca matricea distanțelor să poată fi recuperată ulterior, intrarea poziției (i,j) trebuie setată cu valoarea complementară negativă, până când arborele se creează, apoi se revine la valoarea adevărată.
Algoritmi pentru căi optimale
Acest subpunct va studia câteva metode de găsire a căilor de comunicație printr-o rețea care posedă proprietăți optimale. Problema principală pentru aceste metode este găsirea “căii celei mai scurte”, prin aceasta înțelegând nu neapărat calea cu lungimea cea mai scurtă, ci poate fi vorba și de un cost asociat (moment în care trebuie să găsim calea cea mai “ieftină”), sau de un risc (și vom căuta calea cea mai “sigură”). Însă, pentru simplificare și o mai bună înțelegere a problemei, se va apela la studiul din punctul de vedere al distanței. Mai întâi se examinează cazul cel mai simplu, de găsire a căii celei mai scurte dintre două noduri particulare ale unei rețele; apoi calea cea mai scurtă dintre un nod dat și toate nodurile din rețea și o generalizare a acestui caz, ce constă în găsirea căii celei mai scurte dintre oricare pereche de noduri din rețea; în final se va studia o problemă particulară, de găsire a căii minime secunde (din punctul de vedere al minimalității distanței) dintre o pereche de noduri din rețea.
Problema căi celei mai scurte – Algoritmul lui
E.W. DIJKSTRA
Să presupunem că există o distanță d(i,j) asociată unui arc (i,j) din rețeaua N. Este evident faptul că distanța dintre nodul i și nodul k, via nodul j este egală cu suma d(i,j)+d(j,k). Acest rezultat va fi folosit pentru a calcula toate distanțele dintre oricare două noduri s (nodul de start) și t (nodul de sosire) din N, printr-o cale de forma (s,i1), (i1,i2) ,…, (ip,t). Astfel, distanța dintre s și t va fi de forma d(s,i1) + d(i1,i2) + …+ d(ip,t). În orice rețea, vor exista multe căi între s și t, dar scopul nostru este de a o identifica pe cea mai scurtă și de a-i calcula lungimea. Una dintre cele mai folosite și mai eficiente metode a fost elaborată de E.W. Dijkstra.
În metoda lui Dijkstra, primul pas este de a ne asigura că există o distanță asociată cu fiecare pereche de noduri din rețea. Distanța va fi reprezentată de lungimea arcului, dacă există un arc între cele două noduri (dacă există mai multe arce între cele două noduri se alege arcul cu cea mai mică lungime),valoarea zero pentru distanța de la nod la nodul însuși și infinit pentru orice pereche de noduri care nu sunt legate printr-un arc (după cum am mai amintit, în practică, în locul valorii infinit, se folosește un număr foarte mare). Nu este în mod obligatoriu necesar ca distanța dintre i și j să fie egală cu distanța dintre j și i, lucru care permite ca pentru o anumită cale ce trebuie traversată, lungimea ei să depindă de direcția în care aceasta este traversată.
Metoda lui Dijkstra asignează o etichetă fiecărui nod al rețelei. Această etichetă reprezintă distanța de la nodul de start s, la nodul respectiv, de-a lungul căii celei mai scurte găsite. Eticheta se poate găsi în una din două stări: poate fi o etichetă permanentă, în care caz distanța găsită este cea mai scurtă dintre toate căile găsite, sau poate fi temporară, corespunzătoare unei căi care nu are certitudinea minimalității decât până la un moment dat, când este găsită o altă cale mai scurtă. Având un set de noduri cu etichete temporare, scopul este de a încerca să facem aceste etichete cât mai mici prin găsirea căilor la aceste noduri, folosind căile cele mai scurte urmate de un arc până la nodurile cu etichete permanente. Odată făcut acest lucru, nodul cu eticheta temporară cea mai mică este selectat, iar eticheta lui este făcută permanentă. Acest proces este repetat până când nodului terminal t îi este asignată o etichetă permanentă.
Algoritmul “Dijkstra” pentru o rețea N poate fi etapizat astfel:
Pasul 0: asignăm o etichetă temporară l(i) = tuturor nodurilor is; setăm
l(s)=0 și p=s; o facem pe l(s) permanentă (p este ultimul nod căruia
i s-a asignat etichetă permanentă);
Pasul 1: pentru fiecare nod i cu etichetă temporară, redefinim l(i), astfel
încât să fie eticheta temporară cea mai mică dintre etichetele l(i)
cu valoarea l(p)+d(p,i); găsim nodul i cu cea mai mică etichetă
temporară, setăm p egal cu acest i și facem l(p) permanentă;
Pasul 2: dacă nodul t are o etichetă temporară, se repetă pasul 1; altfel, t are o
etichetă permanentă, aceasta corespunde lungimii căii celei mai scurte
dintre s și t și algoritmul se oprește deoarece a rezolvat problema.
Exemplu practic de funcționare a algoritmului:
Se consideră rețeaua prezentată în figura următoare:
Fig. 4.12 Exemplu practic
În acest caz, setul de noduri N este {s,1,2,3,4,t}, iar matricea distanțelor este:
s 1 2 3 4 t
s 0 29 57 106
1 29 0 90 97
2 57 0 83 49
3 83 0 35
4 106 97 49 0 78
t 35 78 0
Aplicând algoritmul lui E.W. Dijkstra pentru acest exemplu, calea cea mai scurtă se determină astfel:
Pasul 0: Asignăm etichetele ca în tabelul următor:
Setăm p = s și facem l(s) permanentă;
Fig. 4.13 Evoluție căutare
Pasul 1: Redefinim etichetele astfel:
l(1) = min(, 0+29) = 29
l(2) = min(, 0+57) = 57
l(3) = min(, 0+) =
l(4) = min(, 0+106) = 106
l(t) = min(, 0+) =
Setăm p = 1, facem l(1) permanent;
Fig. 4.14 Evoluție căutare
Pasul 2: Repetă pasul 1;
Pasul 1: Redefinim etichetele astfel:
l(2) = min(57, 29+) = 57
l(3) = min(, 29+90) = 119
l(4) = min(106, 29+97) = 106
l(t) = min(, 29+) =
Setăm p = 2, facem l(2) permanent;
Fig. 4.15 Evoluție căutare
Pasul 2: Repetă pasul 1;
Pasul 1: Redefinim etichetele astfel:
l(3) = min(119, 57+83) = 119
l(4) = min(106, 57+49) = 106
l(t) = min(, 57+) =
Setăm p = 4, facem l(4) permanent;
Fig. 4.16 Evoluție căutare
Pasul 2: Repetă pasul 1;
Pasul 1: Redefinim etichetele astfel:
l(3) = min(119, 106+) = 119
l(t) = min(, 106+78) =
Setăm p = 3, facem l(3) permanent;
Fig. 4.17 Evoluție căutare
Pasul 2: Repetă pasul 1;
Pasul 1: Redefinim etichetele astfel:
l(t) = min(184, 119+35) = 154
Fig. 4.18 Final algoritm
Pasul 2: Stop. Cea mai scurtă cale din rețea de la nodul s la nodul t are
lungimea 154 de unități.
Observații:
Din acest exemplu reies câteva concluzii. În primul rând, au fost atașate etichete permanente tuturor nodurilor și astfel a fost găsită cea mai scurtă cale dintre s și t, însă nu este obligatoriu să se întâmple așa, în sensul că putem modifica algoritmul lui Dijkstra prin schimbarea regulii de oprire de la pasul 2, astfel:
Pasul 2: Dacă fiecare nod are o etichetă temporară, atunci repetă pasul 2;
altfel, toate etichetele au etichete permanente și am găsit toate căile
minime de la s la toate nodurile; stop.
În al doi-lea rând, se poate observa o slăbiciune a algoritmului: nu există indicații cu privire la istoria compunerii căii optime, singura informație furnizată de algoritm fiind lungimea căii. Pentru a afla nodurile care compun calea optimă, de exemplu pentru exercițiul anterior, urmărim algoritmul și observăm că valoarea 154 a fost stabilită prin considerarea etichetei permanente l(3), deci arcul (3,t) a fost ultimul arc din calea optimă; l(3) a fost ea însăși stabilită considerând eticheta l(1), deci arcul (1,3) trebuie să facă parte și el din istoria căii și în final arcul (s,1) trebuie să fie și el membru al căii optime. Deci, cea mai scurtă rută de la s la t cuprinde arcele (s,1), (1,3), (3,t).
Pentru a corecta acest neajuns, putem crea o a doua etichetă pentru fiecare nod i pe care îl accesează algoritmul care va indica nodul precedent din cale al cărui lungime este l(i) și se va schimba atunci când este găsită o cale mai mică. Acest lucru cere introducerea unui nou pas în algoritm și ștergerea instrucțiunii “stop” din cadrul pasului 2. Acest pas va găsi nodul predecesor r(i) pentru fiecare nod i, ca fiind ultimul nod care a vizitat calea de la s la i. Apoi putem reconstrui calea în ordine inversă ca fiind:
(r(t,t)), (r(r(t)), r(t)), (r(r(r(t))), r(r(t))), . . . , (s, r(r …)))
Noul pas al algoritmului va fi:
Pasul 3: Pentru fiecare nod j etichetat, altul decât s, se definește r(j) = i,
unde l(j) = l(i) + d(i,j) și ij (dacă sunt mai multe valori i care
satisfac această condiție, se alege una în mod arbitrar, caz în care
pot exista mai multe căi de lungime minimă până la j). Stop
În cadrul exemplului anterior:
r(1) = s
r(2) = s
r(3) = 1
r(4) = 1 (sau 2)
r(t) = 3 și, deci, ruta este: (3,t) , (1,3), (s,1).
Implementarea algoritmului lui E.W. Dijkstra:
Etichetele cerute de algoritm pot fi memorate foarte convenabil ca vectori, iar fiecare componentă a vectorilor corespunde unui nod. Distanțele dintre noduri pot fi memorate ca o matrice, iar proprietățile “permanent” și “temporar” pot fi implementate în mai multe feluri: cu variabile logice (booleen-e), cu un vector de astfel de variabile, sau în alte moduri convenabile.
Pasul 1 cere scanarea vectorului cu etichete, ceea ce s-ar putea executa ușor folosind o procedură care va calcula valoarea minimă dintre două cantități; în program, acest lucru se execută cu o funcție numită MIN.
Pasul 2 cere testarea stării etichetelor, acțiune care este inclusă împreună cu pasul 1 într-o structură de tip REPEAT…UNTIL.
Generalizarea celor mai scurte căi – Algoritmul
lui L.R. Ford
O importantă presupunere în cadrul algoritmului Dijkstra a fost faptul că toate lungimile arcelor sunt pozitive sau zero, lucru care este rezonabil când ne referim la distanțe. Însă, dacă valoarea asociată arcului este un cost, atunci este posibil ca această valoare să fie negativă. De exemplu, un furnizor de mijloace de transport trebuie să stabilească un preț pe un arc pe care camionul său circulă gol și alt preț (un cost negativ) dacă acesta circulă încărcat. Prin urmare, a fost elaborat un algoritm de această natură, numit algoritmul lui L.R. Ford, care permite ca arcele cu valoare negativă să fie incluse în problemele căilor cele mai scurte, cu condiția ca să nu existe circuite în jur care să aibă un cost negativ. Aceasta înseamnă că două astfel de arce (care aparțin unui circuit) nu pot avea cost negativ.
Introducerea costurilor negative la arce conduce la un algoritm care este foarte apropiat de cel al lui Dijkstra, dar care nu mai reclamă două tipuri de etichete. În acest caz trebuie să determinăm cea mai scurtă rută de la nodul de start la toate nodurile din rețea.
În acest algoritm, etichetele sunt asignate fiecărui nod și reprezintă cea mai scurtă cale găsită până la momentul respectiv. La fiecare iterație a algoritmului este executată o operație de căutare a etichetei care poate fi eliminată, folosind aceeași abordare ca în cazul metodei lui Dijkstra. Algoritmul se termină când nici o etichetă nu mai poate fi eliminată.
Algoritmul “Ford” pentru o rețea N poate fi etapizat astfel:
Pasul 0: asignăm o etichetă temporară l(i) = tuturor nodurilor i din rețea și
setăm l(s)=0;
Pasul 1: pentru fiecare nod j testăm dacă există vreun arc (i,j) care să satisfacă
condiția l(i) + d(i,j) < l(j); dacă există un astfel de arc, se trece la
pasul 2; dacă nu există, algoritmul se oprește.
Pasul 2: se schimbă l(j) cu l(i) + d(i,j) și se repetă pasul 1.
La final, l(t) este lungimea căii celei mai scurte de la s la t; istoria căii, din punctul de vedere al nodurilor, se poate afla prin algoritm sau introducând încă un pas, asemenea algoritmului lui Dijkstra.
Pentru ca algoritmul să nu eșueze când întâlnește un circuit cu cost negativ, trebuie luate anumite precauții: prima ar fi de a interzice existența arcelor cu două căi cu cost negativ, dar circuitele mai mari sunt mai greu de recunoscut. În orice caz, existența lor poate fi recunoscută dacă eticheta oricărui nod este schimbată de un număr de ori excesiv de mare. Algoritmul se va termina când numărul de schimbări al oricărei etichete de pășește valoarea n, numărul de noduri din rețea. În acest sens, poate fi implementat un contor, care memorează numărul de executări al pasului 2, pentru fiecare nod j. Limita n este setată deoarece este posibil ca eticheta unui nod să fie schimbată de n-1 ori, într-o rețea în care nu există circuite cu cost negativ.
Exemplu practic de funcționare a algoritmului:
Un om de afaceri plănuiește să călătorească între două orașe s și t, așa cum este prezentat în figura de mai jos. Pe anumite arce el își poate conduce afacerile (vânzări, seminarii, etc.) care îi aduc un profit efectiv, iar pe altele există un cost asociat călătoriilor sale. Costurile asociate fiecărui arc sunt vizibile, iar profiturile sunt reprezentate ca și costuri negative. Ce rută trebuie să aleagă pentru minimizarea costurilor sale?
Fig. 4.19 Exemplu practic
Matricea legăturilor: s 1 2 3 t
s 0 12 10
1 0 -3 -1 -5
2 0 -2
3 -4 0 10
t 0
Aplicând algoritmul lui L.R. Ford pentru acest exemplu, calea cea mai scurtă se determină astfel:
Pasul 0: Asignăm etichetele ca în tabelul următor:
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(s) + d(s,1) = 12 < l(1). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului 1.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) = l(1) pentru toți i.
Testăm nodul 2: l(s) + d(s,2) =10 < l(2). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului 2.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) l(1) pentru toți i.
Testăm nodul 2: l(1) + d(1,2) =9 < l(2). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului 2.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) l(1) pentru toți i.
Testăm nodul 2: l(i) + d(i,2) l(2) pentru toți i.
Testăm nodul 3: l(1) + d(1,3) =11 < l(3). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului 3.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) l(1) pentru toți i.
Testăm nodul 2: l(3) + d(3,2) =7 < l(2). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului 2.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) l(1) pentru toți i.
Testăm nodul 2: l(i) + d(i,2) l(2) pentru toți i.
Testăm nodul 3: l(i) + d(i,3) l(3) pentru toți i.
Testăm nodul t: l(1) + d(1,t) < l(t). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului t.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) l(1) pentru toți i.
Testăm nodul 2: l(i) + d(i,2) l(2) pentru toți i.
Testăm nodul 3: l(i) + d(i,3) l(3) pentru toți i.
Testăm nodul t: l(2) + d(2,t) < l(t). Execută pasul 2.
Pasul 2: Schimbăm eticheta nodului t.
Execută pasul 1.
Pasul 1: Testăm nodul s: l(i) + d(i,s) l(s) pentru toți i.
Testăm nodul 1: l(i) + d(i,1) l(1) pentru toți i.
Testăm nodul 2: l(i) + d(i,2) l(2) pentru toți i.
Testăm nodul 3: l(i) + d(i,3) l(3) pentru toți i.
Testăm nodul t: l(i) + d(i,t) l(t) pentru toți i.
Nu se mai face nici o schimbare a nici unei etichete. Stop.
Costul minim al căii de la nodul s la nodul t are valoarea 5 unități.
Implementarea algoritmului lui L.R. Ford:
Programul pentru acest algoritm este similar cu cel folosit pentru Dijkstra, numai că nu mai este necesară verificarea stării etichetelor. În schimb, este folosit un contor care memorează de câte ori se schimbă fiecare etichetă, iar aceste valori sunt memorate într-un vector de valori întregi. Când se execută prea multe schimbări pentru o etichetă, se afișează un mesaj de avertizare, iar programul se oprește și nu mai este posibilă găsirea cu certitudine a căii de cost minim (acest program nu identifică circuitele care cauzează această problemă, ea putând fi rezolvată folosind un alt algoritm specializat în acest sens).
Algoritm pentru a determina toate căile cele mai scurte – Algoritmul lui R.W. FLOYD
Dacă am dori să folosim algoritmul lui Ford de n ori, pentru fiecare nod al rețelei, am putea determina calea cea mai scurtă dintre toate perechile de noduri dintr-o rețea. Un astfel de exemplu îl constituie folosirea unei hărți a străzilor, de mai mare dimensiune.
În metoda lui Floyd, nodurile sunt numerotate de la 1 la n. Algoritmul construiește cea mai scurtă cale dintre perechile de noduri, prima oară găsind calea cea mai scurtă directă sau care folosește nodul 1, ca nod intermediar, a doua oară calea cea mai scurtă directă și/sau care folosește nodul 2, și continuă în acest fel până când calea cea mai scurtă directă, sau care folosește unul sau toate nodurile de la 1 la n (ca noduri intermediare) este găsită. Distanța găsită la orice pas al algoritmului este memorată într-o matrice Dk cu dimensiunea n*n și elementele dk(i,j) ( –> dk(i,j) reprezintă cea mai scurtă distanță de la i la j, via oricare sau toate nodurile 1,…,k). Atunci, elementele dk+1(i,j) ale matricei următoare vor fi, fie elementele dk(i,j) (dacă nu este avantajos să includem nodul k+1 în cale), fie dk(i,k+1)+ dk(k+1,j) (dacă includerea nodului k+1 în cale este avantajoasă) și va fi ales cel mai mic dintre acestea.
Lungimile arcelor din rețea vor forma matricea D0, iar matricea finală – harta distanțelor – va fi Dn.
Algoritmul “Floyd” pentru o rețea N poate fi etapizat astfel:
Pasul 0: Creăm matricea n*n D0 , care conține elementele:
d0(i,j) = d(i,j) (lungimea arcului (i,j), dacă există),
= 0 (dacă i = j),
= (dacă arcul (i,j) nu există).
Setăm k = 0.
Pasul 1: Definim matricea n*n Dk+1, care conține elementele
dk+1(i,j) = min( dk(i,j), dk(i,k+1)+ dk(k+1,j)).
Pasul 2: Îl majorăm pe k cu 1. Dacă k = n, stop, altfel se reia pasul 1.
Când algoritmul se oprește, el deja a găsit calea cea mai scurtă dintre oricare pereche de noduri din rețea. Nodurile care formează aceste căi pot fi memorate, asemenea algoritmilor lui Dijksrta și Ford, fie prin includerea unei evaluări a nodului precedent, fie prin calcularea acestui nod cu ajutorul matricei inițiale a distanțelor, odată ce algoritmul a găsit matricea Dn (nodul predecesor nodului t din calea cea mai scurtă formată de la s la t va fi nodul k ce satisface relația: dn(s,t)=ds(s,k)+d(k,t).
Algoritmul modificat, incluzând și evaluarea căii, va fi:
Pasul 0: Creăm matricea n*n D0 , care conține elementele:
d0(i,j) = d(i,j) (lungimea arcului (i,j), dacă există),
= 0 (dacă i = j),
= (dacă arcul (i,j) nu există).
Creăm matricea n*n P, care conține elementele:
p(i,j) = i.
Setăm k = 0.
Pasul 1: Definim matricea n*n Dk+1, care conține elementele
dk+1(i,j) = min( dk(i,j), dk(i,k+1)+ dk(k+1,j))
Pasul 2: Îl majorăm pe k cu 1. Dacă k = n, stop, altfel se reia pasul 1.
Când algoritmul se oprește, matricea P conține numere întregi între 1 și n; valoarea p(i,j) este ultimul nod vizitat de calea cea mai scurtă de la i la j și astfel calea se poate refece de la sfârșit spre început folosind arcele:
(p(i,j),j), (p(i, r(i,j)), p(i,j)), . . . , (i, p(i,p(i, …(i,j) …).
Exemplu practic de funcționare a algoritmului:
Considerăm algoritmul modificat aplicat rețelei următoare:
Fig. 4.20 Exemplu practic
Matricea distanțelor: 0 97 90
0 83 49
97 83 0 35
90 49 0 78
35 78 0
Aplicând algoritmul lui R.W. Floyd pentru acest exemplu, căile cele mai scurte se determină astfel:
Pasul 0: D0 = 0 97 90 P = 1 1 1 1 1
0 83 49 2 2 2 2 2
97 83 0 35 ; 3 3 3 3 3
90 49 0 78 4 4 4 4 4
35 78 0 5 5 5 5 5
k = 0
Pasul 1: d1(1,1) = min(0, 0+0) = 0 p(1,1) = 1
d1(1,2) = min(, 0+) = p(1,2) = 1
d1(1,3) = min(97, 0+97) = 97 p(1,3) = 1
d1(1,4) = min(90, 0+90) = 90 p(1,4) = 1
d1(1,5) = min(, 0+) = p(1,5) = 1
d1(2,1) = min(,+0) = p(2,1) = 2
d1(2,2) = min(0, 0+0) = 0 p(2,2) = 2
d1(2,3) = min(83, +97) = 83 p(2,3) = 2
d1(2,4) = min(49, +90) = 49 p(2,4) = 2
d1(2,5) = min(,+) = p(2,5) = 2
d1(3,1) = min(97, 97+0) = 97 p(3,1) = 3
d1(3,2) = min(83, 97+) = 83 p(3,2) = 3
d1(3,3) = min(0, +) = 0 p(3,3) = 3
d1(3,4) = min(, 97+90) = 187 p(3,4) = 1
d1(3,5) = min(35, 97+) = 35 p(3,5) = 3
d1(4,1) = min9(0, 90+0) = 90 p(4,1) = 4
d1(4,2) = min(49, 90+) = 49 p(4,2) = 4
d1(4,3) = min(, 90+97) = 187 p(4,3) = 1
d1(4,4) = min(0, 90+90) = 0 p(4,4) = 4
d1(4,5) = min(78, 90+) = 78 p(4,5) = 4
d1(5,1) = min(,+0) = p(5,1) = 5
d1(5,2) = min(,+) = p(5,2) = 5
d1(5,3) = min(35, +97) = 35 p(5,3) = 5
d1(5,4) = min(78, +90) = 78 p(5,4) = 5
d1(5,5) = min(0, +) = 0 p(5,5) = 5
Deci : D1 = 0 97 90 P = 1 1 1 1 1
0 83 49 2 2 2 2 2
97 83 0 187 35 ; 3 3 3 1 3
90 49 187 0 78 4 4 1 4 4
35 78 0 5 5 5 5 5
Pasul 2: k = 1 (nu este egal cu 5); reluăm pasul 1.
Pasul 1: Folosind aceeași metodă ca mai înainte, calculăm D2 și P.
Deci : D2 = 0 97 90 P = 1 1 1 1 1
0 83 49 2 2 2 2 2
97 83 0 132 35 ; 3 3 3 2 3
90 49 132 0 78 4 4 2 4 4
35 78 0 5 5 5 5 5
Pasul 2: k = 2 (nu este egal cu 5); reluăm pasul 1.
Pasul 1: Folosind aceeași metodă ca mai înainte, calculăm D3 și P.
Deci : D3 = 0 180 97 90 132 P = 1 1 1 1 1
180 0 83 49 118 3 2 2 2 3
97 83 0 132 35 ; 3 3 3 2 3
90 49 132 0 78 4 4 2 4 4
132 118 35 78 0 3 3 5 5 5
Pasul 2: k = 3 (nu este egal cu 5); reluăm pasul 1.
Pasul 1: Folosind aceeași metodă ca mai înainte, calculăm D4 și P.
Deci : D4 = 0 139 97 90 132 P = 1 4 1 1 3
139 0 83 49 118 4 2 2 2 3
97 83 0 132 35 ; 3 3 3 2 3
90 49 132 0 78 4 4 2 4 4
132 118 35 78 0 3 3 5 5 5
Pasul 2: k = 4 (nu este egal cu 5); reluăm pasul 1.
Pasul 1: Folosind aceeași metodă ca mai înainte, calculăm D5 și P.
Deci : D5 = 0 139 97 90 132 P = 1 4 1 1 3
139 0 83 49 118 4 2 2 2 3
97 83 0 113 35 ; 3 3 3 5 3
90 49 113 0 78 4 4 5 4 4
132 118 35 78 0 3 3 5 5 5
Pasul 2: k = 5: stop.
Observații:
Din acest exemplu reiese în mod aparent că algoritmul este plictisitor pentru calculul cu mâna. Însă, i se poate crește rapiditatea cu o cantitate considerabilă în pasul 2, prin nefolosirea relației de recurență pentru cazurile dk+1(i,i), care vor fi totdeauna 0, dar și pentru cazurile dk+1(k+1,i) și dk+1(i,k+1), care vor fi egale cu elementele corespunzătoare din matricea Dk. Prin nefolosirea acestor relații de recurență reducem numărul comparațiilor ce trebuie făcute pentru o valoare de la n*n la (n-1)*(n-2) pe iterație, astfel salvând un număr de (3*n*n – 2*n) comparații în întregul algoritm.
Implementarea algoritmului lui R.W. Floyd:
Algoritmul a fost prezentat cu ajutorul matricelor de dimensiune n*n, acesta fiind cel mai eficient mod de memorare a datelor. Oricum, nu este necesar să folosim n+1 matrice pentru datele D0, D1, … , Dn, atât timp cât algoritmul face modificări asupra matricei precedente la fiecare iterație. Deci, la pasul 1, reținem numai două matrice: o matrice “veche” și una “nouă”, care corespund matricelor Dk și Dk+1. La pasul 2, copiem matricea “nouă” peste matricea “veche” pentru pregătirea repetării pasului 1. Este posibilă și folosirea unui pointer care să dea informații cu privire la matricea care a fost cel mai recent modificată.
Calea minimă secundă – Algoritmul
lui M. POLLACK
Câteodată este dezirabil să cunoaștem nu numai cea mai scurtă cale dintr-o rețea, dar de asemenea și superioritatea acesteia asupra oricăror căi rivale. Pentru a cunoaște acest aspect este necesar să descoperim lungimea (posibil și calea) căii minime secunde. Există câteva metode pentru a descoperi această cale, iar una dintre ele este metoda lui Pollack. Aceasta este cea mai simplă dintre metode, de aceea nu este neapărat necesar să fie cea mai eficientă. Algoritmul pune în evidență faptul că noțiunea de “cale minimă secundă” diferă de cea a “căii celei mai scurte” prin cel puțin un arc și va fi cea mai scurtă cale care satisface această condiție. Metoda decurge din găsirea căilor minime dintr-o serie de rețele modificate față de rețeaua originală, prin setarea temporară la un moment dat a lungimii arcului i cu valoarea “infinit” (ceea ce înseamnă de fapt, eliminarea unui arc). Cea mai mică dintre căile minime găsite în rețelele modificate va fi calea minimă secundă a rețelei inițiale.
Este posibil ca valoarea găsită prin această metodă să fie egală cu valoarea căii minime inițiale. Aceasta corespunde cu posibilitatea existenței a două căi minime egale într-o rețea, ceea ce duce la alegerea unei dintre ele, în mod arbitrar. Această situație poate fi satisfăcătoare pentru anumite scopuri, dar pot exista cazuri în care se dorește ca cele două valori să fie diferite. Astfel, metoda poate fi extinsă astfel încât acest criteriu de diferențiere să fie satisfăcut.
Algoritmul “Pollack” pentru o rețea N poate fi etapizat astfel:
Pasul 0: Găsim (folosind algoritmul lui Dijkstra) calea cea mai scurtă din
rețea; numerotăm arcele acestei căi de la 1 la m, unde arcul l este de
la nodul i(l-1) la nodul i(l), iar i(0)=s și i(m)=t. Setăm k = 1, q = ,
r= 0.
Pasul 1: Setăm temporar d(i(k-1), i(k))= ; găsim cea mai scurtă cale din
rețeaua rezultată; dacă aceasta are lungimea mai mică decât q, atunci:
setăm q egal cu lungimea căii găsite;
memorăm calea;
setăm r = k.
Pasul 2: Dacă k = m, stop. Altfel, setăm k = k + 1 și repetăm pasul 1.
Algoritmul se încheie cu găsirea căii minime secunde și cu valoarea lungimii acesteia memorată în variabila q. Această corespunde eliminării arcului r din calea minimă inițială.
Exemplu practic de funcționare a algoritmului:
Se consideră rețeaua prezentată în figura următoare:
Fig. 4.21 Exemplu practic
Matricea distanțelor se prezintă astfel:
s 1 2 3 4 t
s 0 29 57 106
1 29 0 90 97
2 57 0 83 49
3 83 0 35
4 106 97 49 0 78
t 35 78 0
Aplicând algoritmul lui M. Pollack pentru acest exemplu, calea minimă secundă se determină astfel:
Pasul 0: Găsim (folosind algoritmul lui Dijkstra) calea cea mai scurtă de la
nodul s la nodul t; acesta este (s,1), (1,3), (3,4), cu lungimea 154.
Fig. 4.21 Evoluție algoritm
Setăm k = 1, q = , r = 0.
Pasul 1: Setăm temporar d(s, 1)= ; găsim cea mai scurtă cale din rețeaua
nouă; aceasta este (s,2), (2,3), (3,4), cu lungimea 175;
Setăm q = 175, r = 1 și memorăm calea.
Fig. 4.22 Evoluție algoritm
Pasul 2: k = 2 și repetăm pasul 1.
Pasul 1: Setăm temporar d(1, 3)= (și d(s,1)=29); găsim cea mai scurtă cale
din rețeaua nouă; aceasta este din nou (s,2), (2,3), (3,4), cu aceeași
lungime 175;
Fig. 4.23 Evoluție algoritm
Pasul 2: k = 3 și repetăm pasul 1.
Pasul 1: Setăm temporar d(3,t)= (și d(1,3)=90); găsim cea mai scurtă cale
din rețeaua nouă; aceasta (s,2), (2,4), (4,t), cu lungimea 184;
Fig. 4.24 Evoluție algoritm
Pasul 2: Stop. Calea minimă secundă are valoarea 175 și corespunde eliminării
Arcului 1 (sau 2) din calea cea mai scurtă inițială.
SAU
Fig. 4.25 Exemplul rezolvat
Implementarea algoritmului lui M. Pollack:
Algoritmul implică câteva schimbări relative în cadrul algoritmului lui Dijkstra, în sensul că va folosi o subrutină numită “Dijk” pentru determinarea căii minime. În plus, mai este necesară introducerea unor variabile noi pentru memorarea unor informații despre căile găsite la fiecare pas și pentru detalii referitoare la calea minimă secundă.
Asemenea programului elaborat pentru metoda lui Dijskstra, calea cea mai scurtă este memorată într-un vector, iar calea căutată este reconstituită de la finele vectorului către începutul acestuia. Este imperios necesară indexarea arcelor căii minime și, de asemenea, avem nevoie de un contor al arcelor (identificat cu k în algoritm), setat inițial corespunzător arcului 1 în cadrul vectorului.
Algoritm pentru fluxuri optimale
Pentru a înțelege mai bine această problemă, putem lua cazul alimentării cu apă pentru clienți prin canale de alimentare, rezervoare cu conducte de legătură, izvoare sau stații de pompare. Fiecare dintre acestea are o capacitate limitată pentru furnizarea și transmiterea apei în fiecare zi. În astfel de cazuri este evidentă întrebarea: care este cel mai mare flux pe care sistemul îl întâlnește? Pot exista limitări date de legăturile din izvoare, de conductele de legătură ce servesc clienții, sau poate să nu fie nici una dintre aceste situații? Atunci, care este limita?
Pe lângă capacitatea asociată fiecărei părți a rețelei, mai poate fi asociat un cost fiecărei unități de flux care este trimisă de-a lungul rețelei. Se poate pune întrebarea: cum pot fi aprovizionați clienții cu o cantitate fixă de apă, în fiecare zi, la un cost minim? Continuând pe aceeași idee, a companiei de apă, este bine de știut aria întreruperii aprovizionării în cazul în care o anumită conductă de aprovizionare a fost distrusă sau trebuie reparată. În aceste circumstanțe, o întrebare devine evidentă: care conductă este cea mai importantă pentru aprovizionarea cu apă?
Toate aceste probleme sunt toate înrudite și pot fi studiate sub titulatura de “algoritmi pentru fluxuri”. În general vorbind, ideea de flux ar însemna ceva care se mută de la un punct la altul, de-a lungul unei rute predeterminate. Ceea ce este mutat poate fi măsurat în unități convenabile, existând limite asociate cantității de flux, care se pot instala în orice parte a rutei la un moment dat. Această structură poate fi privită ca o rețea în care există arce (unde fluxul se transmite de la un punct la altul), care leagă noduri (unde fluxurile converg sau diverg). În cea mai simplă versiune a problemei, fiecare arc (i,j) are asociat un flux maxim, u(i,j), dar și un flux curent x(i,j), care satisfac inegalitatea:
0 x(i,j) u(i,j).
Valoarea lui u(i,j) va fi determinată de natura fizică a legăturii și corespunde “gâtului” legăturii, locul unde legătura este cel mai mult limitată.
Când fluxul în arce întâlnește un nod, este de dorit să nu existe nici un câștig și nici o pierdere, astfel încât să existe un flux constant la fiecare nod, iar suma fluxurilor ce intră în nod să fie egală cu suma fluxurilor de la ieșirea acestuia. În termeni de flux, pentru nodul j, aceasta corespunde relației:
Singura excepție de la această regulă o reprezintă ceea ce numim noduri terminale. Acestea se împart în două grupuri: cele care acționează ca sursă pentru flux și cele care acționează ca destinație. În cazul cel mai simplu, există o singură sursă și o singură destinație și sunt în mod frecvent notate cu s și t. În cazul de față, problema care trebuie studiată într-o rețea este de a găsi calea de flux maxim de la s la t, folosind arcele rețelei, constrângerea fluxului în arce și conservarea fluxului la fiecare nod, exceptând sursa și destinația.
Lanțuri de flux augmentativ
Un lanț de flux augmentativ între o pereche de noduri este un lanț de arce care conectează noduri și care poate fi folosit pentru a mări fluxul de la un nod la altul. În cazul unui flux dintr-o rețea, de la sursă la destinație, lanțul începe da la sursa s și se încheie la destinația t. În astfel de lanțuri se pot fi folosi două tipuri de arce:
primul este cel care va fi un arc în direcția “de la s la t”, cu capacitate de rezervă; într-un astfel de arc, fluxul de la s la t poate fi crescut prin creșterea fluxului în arc; se mai numește și arc direct;
al doi-lea este în sens opus, de la t la s și nu are flux de rezervă, deci poate fi folosit un astfel de arc pentru a crește fluxul de la s la t prin reducerea fluxului din el; se mai numește și arc invers;
Un lanț de flux augmentativ conține o mixare a celor două tipuri de arce, după cum putem observa în figurile următoare:
s x(s,1)=1 1 x(1,2)=0 2 x(2,t)=2 t
u(s,1)=5 u(1,2)=3 u(2,t)=7
Fig. 4.26 Lanț de flux augmetativ cu toate arcele directe
s x(1,s)=4 1 x(2,1)=5 2 x(t,2)=1 t
Fig. 4.27 Lanț de flux augmetativ cu toate arcele inverse
s x(1,s)=4 1 x(2,1)=5 2 x(t,2)=1 t
Fig. 4.28 Lanț de flux augmetativ cu arce directe și inverse
Pentru arcele directe, cantitatea surplusului de flux este calculată ca diferența u(i,j)-x(i,j), iar pentru arcele inverse cantitatea surplusului de flux se va obține, prin convenție, prin reducerea fluxului către 0, astfel surplusul obținut va fi chiar valoarea lui x(ir,ir+1). Deci, pentru un lanț de flux augmentativ, al cărui legături sunt (s, i1), (i1, i2), … , (ir, ir-1), … , (iq,t), volumul surplusului de flux posibil este găsit calculând:
pentru arcele directe: (ir, ir+1) = u(ir, ir+1) – x(ir, ir+1)
pentru arcele inverse: x(ir+1, ir),
iar, capacitatea lanțului = min((ir, ir+1)).
Ajutându-ne de noțiunile anterioare, ne putem întoarce la problema inițială, de a găsi fluxul maxim printr-o rețea, de la s la t.
Algoritm pentru maximizarea fluxului – Algoritmul
L.R FORD & D.R. FULKERSON
Există două părți complementare ale algoritmului de maximizare a fluxului între două noduri ale unei rețele:
în pasul 1, se caută un lanț de flux augmentativ între cele două noduri s și t; odată găsit, se desfășoară pasul 2;
în pasul 2, se calculează care este surplusul de flux adus de lanțul găsit și apoi se fac modificările adecvate în încărcarea arcelor, pentru a asigura flux maxim; se reia pasul 1 al algoritmului pentru a găsi un alt lanț, i se modifică și acestuia fluxul, și așa mai departe.
Acesta este un proces iterativ, care caută în mod repetat lanțuri și le modifică fluxul, până când nici un lanț nu mai este găsit. Când se întâmplă acest lucru, fluxul de la sursă la destinație are cea mai mare valoare posibilă; distribuția fluxurilor în arcele rețelei este una dintre (poate mai multe) posibilele alocări de flux care conduc la maximizarea fluxului total.
Intrând mai în amănunt, când se face căutarea de lanțuri augmentative, nodurile lanțului se etichetează cu o etichetă dublă, astfel: prima valoare indică nodul anterior (pentru arcele directe) sau posterior (pentru arcele inverse) de unde se preia fluxul, iar a doua valoare indică valoarea surplusului de flux ce poate fi trimis de la sursă la nodul curent.
Ar putea fi posibil, odată ce un lanț a fost găsit, să examinăm fiecare din arcele componente, în ordinea în care surplusul de flux este calculat. Dar este mult mai convenabil să folosim etichete pentru aceasta, iar după ce etichetele au fost stabilite, calculele se realizează cu ajutorul tehnicii recursive. Să presupunem că nodul j a fost etichetat, iar nodul imediat predecesor în lanț este nodul i, care are deja eticheta (ai, bi). Se disting două cazuri ce trebuie examinate:
dacă este un arc direct (i,j), atunci capacitatea potențială a surplusului de flux este u(i,j)-x(i,j); capacitatea lanțului de la s la j va fi valoarea minimă dintre:
capacitatea lanțului de la s la i;
capacitatea potențială a arcului (i,j).
Deci, eticheta nodului j se definește ca (i, min(bi, u(i,j)-x(i,j))).
dacă este un arc invers (j,i), atunci capacitatea potențială a surplusului de flux este x(j,i); capacitatea lanțului de la s la i va fi valoarea minimă dintre:
capacitatea lanțului de la s la i;
capacitatea potențială a arcului (j,i).
Deci, eticheta nodului j se definește ca (i, min(bi, x(j,i))).
( Uneori este mai convenabil de recunoscut un arc invers prin marcarea
etichetei ai = -i )
Pentru a porni procedura de etichetare, inițial toate nodurile sunt neetichetate, iar sursei s, din moment ce predecesorul său e inexistent, i se dă eticheta (-, ), deci fluxul de la el către el însuși poate fi oricât de mare. Apoi nodurile sunt etichetate găsind arce care au un capăt etichetat și celălalt nu și care pot fi folosite ca lanțuri augmentative. Dacă lanțul este unul augmentativ, în cele din urmă va fi etichetat prin acest algoritm și nodul t. Apoi fluxul prin acel lanț va fi crescut (pentru arcele directe) sau scăzut (pentru arcele inverse) cu valoarea bt, valoare calculată prin modalitatea de mai sus. Algoritmul se repetă până când singurul nod neetichetat rămas este nodul destinație, t.
Algoritmul “Ford & Fulkerson” pentru o rețea N poate fi etapizat astfel:
Pasul 0: (Inițializarea) Se dă fiecărui arc un flux real, asigurându-ne de
conservarea acestuia la fiecare nod, altul decât nodul sursă și cel
destinație; acest lucru se poate face prin inițializarea cu 0 a fluxului
pe fiecare arc, condiție scrisă astfel: x(ir,ir+1)=0, iN.
Pasul 1: Etichetăm nodul s cu (-, ) și ne asigurăm că nici un alt nod nu este
etichetat;
Pasul 2: Scanăm printre arce până când este găsit un arc (i,j) cu:
(a) – nodul i etichetat și nodul j neetichetat și x(i,j) < u(i,j)
(pentru arcele directe);
(b) – nodul j etichetat și nodul i neetichetat și x(i,j) > 0
(pentru arcele inverse).
Dacă nici un arc nu există, mergi la pasul 5.
Pasul 3: Dacă (a) este adevărată, atunci etichetăm nodul j cu eticheta dublă
(ai,bi), unde aj = i, bj = min(bi, u(i,j)-x(i,j));
Dacă (b) este adevărată, atunci etichetăm nodul i cu eticheta dublă
(ai,bi), unde ai = -j, bi = min(bj, x(j,i));
Dacă nodul t nu este etichetat, execută pasul 4, altfel execută din nou
pasul 2.
Pasul 4: (A fost găsit un lanț de flux augmentativ.) Se adaugă la fluxul din
lanțul de flux augmentativ, cantitatea bt; dacă nodul t este etichetat
(l, bt), atunci se adaugă fluxul la arcul (l, t); dacă nodul t este etichetat
(-l, bt), atunci se scade fluxul din arcul (t,l,); acum examinăm eticheta
nodului l și repetăm procedura până când sursa este atinsă, mereu
făcând schimbarea cu bt. Mergi la pasul 1.
Pasul 5: Fluxul optim a fost găsit. Stop.
Algoritmul poate fi prezentat sub forma unei scheme logice de forma:
Fig. 4.29 Schema bloc a algoritmului Ford & Fulkerson
Exemplu practic de funcționare a algoritmului:
Se consideră rețeaua (N, A, U) prezentată în figura următoare:
Fig. 4.30 Exemplu practic
Pe figură sunt reprezentate nodurile numerotate de la 1 la 4, arcele direcționate numerotate de la 1 la 5 și valorile capacităților liniilor. Deci avem o rețea cu 4 noduri și 5 arce, în care presupunem că vrem să maximizam traficul între nodul 1 și nodul 4.
N = {1, 2, 3, 4};
A = {(1,2), (2,3), (3,4), (1,3), (3,4)};
u(1,2) = 8; u(2,3) = 5; u(3,4) = 6; u(1,3) = 3; u(2,4) = 7.
Arcele vor fi scanate în ordinea dată în mulțimea A.
Aplicând algoritmul lui Ford & Fulkerson pentru acest exemplu, calea de flux maxim se determină astfel:
Pasul 0: Asignăm flux 0 tuturor arcelor;
Pasul 1: Dăm nodului 1 eticheta (-, );
Pasul 2: Arcul (1, 2) se află în situația (a);
Pasul 3: Dăm nodului 2 eticheta (1, min(, 8-0)) = (1,8);
Pasul 2: Arcul (2, 3) se află în situația (a);
Pasul 3: Dăm nodului 3 eticheta (2, min(8, 5-0)) = (2,5);
Pasul 2: Arcul (3, 4) se află în situația (a);
Pasul 3: Dăm nodului 4 eticheta (3, min(5, 6-0)) = (3,5); nodul 4 a fost
etichetat;
Pasul 4: Mărim fluxul în lanțul (1,2), (2,3), (3,4) cu valoarea 5;
Deci: x(3,4) = 0 + 5 = 5;
x(2,3) = 0 + 5 = 5;
x(1,2) = 0 + 5 = 5;
Pasul 1: Dăm nodului 1 eticheta (-, );
Pasul 2: Arcul (1, 2) se află în situația (a);
Pasul 3: Dăm nodului 2 eticheta (1, min(, 8-5)) = (1,3);
Pasul 2: Arcul (1, 3) se află în situația (a);
Pasul 3: Dăm nodului 3 eticheta (1, min(, 3-0)) = (1,3);
Pasul 2: Arcul (2, 4) se află în situația (a);
Pasul 3: Dăm nodului 4 eticheta (2, min(3, 7-0)) = (2,3); nodul 4 a fost
etichetat;
Pasul 4: Mărim fluxul în lanțul (1,2), (2,4) cu valoarea 3;
Deci: x(2,4) = 0 + 3 = 3;
x(1,2) = 5 + 3 = 8;
(De notat că există un lanț incomplet în rețea, format de arcul (1,3).)
Pasul 1: Dăm nodului 1 eticheta (-, );
Pasul 2: Arcul (1, 3) se află în situația (a);
Pasul 3: Dăm nodului 3 eticheta (1, min(, 3-0)) = (1,3);
Pasul 2: Arcul (2, 3) se află în situația (b);
Pasul 3: Dăm nodului 2 eticheta (-3, min(3, 5)) = (-3,3);
Pasul 2: Arcul (3, 4) se află în situația (a);
Pasul 3: Dăm nodului 4 eticheta (3, min(3, 6-5)) = (3,1); nodul 4 a fost
etichetat;
Pasul 4: Mărim fluxul în lanțul (1,3), (3,4) cu valoarea 1;
Deci: x(3,4) = 5 + 1 = 6;
x(1,3) = 0 + 1 = 1;
(Din nou există un lanț incomplet în rețea, format de arcele (1,3),
(2,3).)
Pasul 1: Dăm nodului 1 eticheta (-, );
Pasul 2: Arcul (1, 3) se află în situația (a);
Pasul 3: Dăm nodului 3 eticheta (1, min(, 3-1)) = (1,2);
Pasul 2: Arcul (2, 3) se află în situația (b);
Pasul 3: Dăm nodului 2 eticheta (1, min(, 8-5)) = (1,3);
Pasul 2: Arcul (2, 4) se află în situația (a);
Pasul 3: Dăm nodului 4 eticheta ( 2, min(2, 7-3)) = (2,2); nodul 4 a fost
etichetat;
Pasul 4: Mărim fluxul în lanțul (1,3), (2,3), (2,4) cu valoarea 2;
Deci: x(2,4) = 3 + 2 = 5;
x(2,3) = 5 – 2 = 3;
x(1,3) = 1 + 2 = 3;
Pasul 1: Dăm nodului 1 eticheta (-, );
Pasul 2: Nu mai există arce în cazul (a) sau (b);
Pasul 5: Stop. Fluxul maxim este x(1, 2) + x(1, 3) = 8 + 3 = 11.
Fig. 4.31 Exemplul rezolvat
Observații:
Acest algoritm folosește rezultate din teoria fluxurilor în rețele, cum ar fi teorema flux maxim tăietură minimă. Prin urmare, o tăietură care întrerupe toate lanțurile dintre două noduri i și j ale unui graf conex, se numește tăietură i-j. teorema amintită precizează că valoarea maximă a fluxului de la s la t este egală cu minimul capacităților tăieturilor s-t, capacitatea unei tăieturi fiind suma capacităților arcelor din acea tăietură.
Implementarea algoritmului
Forma de pseudocod a algoritmului prezintă câteva probleme minore la implementarea lui sub formă computațională. Una dintre acestea este procedura de etichetare a nodurilor și constă în faptul că ar fi indicată folosirea unei metode care asignează etichete nodurilor, iar în cazul în care un nod nu are etichetă, acesta să fie prompt detectat. Pentru aceasta, etichetele nodurilor sunt memorate în două șiruri, corespunzătoare celor două tipuri de etichete.
Rețeaua este memorată într-o serie de șiruri unidimensionale; fiecare arc poate fi reprezentat prin nodul de start, nodul de final, capacitatea sa și fluxul curent asignat. Acesta din urmă este variat de program.
O altă problemă ar putea apărea la pasul 2, la declararea arcelor directe și inverse, împreună cu definirea surplusului de flux. De aceea, apare o problemă și în pasul 4, când trebuie găsit nodul final al unui arc, pentru definirea fluxului său. Aceasta implică determinarea orientării arcului și poziția sa în lista de arce. Pentru aceasta s-a recurs la atașarea la prima parte a etichetei a unui semn, astfel: semnul “+” pentru arcele directe și semnul “–” pentru arcele inverse, astfel încât la scanare să poată fi recunoscut tipul de arc.
Capitolul VI
STUDIU DE CAZ
În capitolul anterior a fost prezentată o sumă de algoritmi de optimizare pentru rețelele de comunicații, care își regăsesc finalitatea într-un pachet de programe de simulare a acestor algoritmi, realizat cu limbajul de programare DELPHI 5.0. Deoarece acest limbaj ne oferă posibilitatea programării pe obiecte, softul realizat are o foarte mare flexibilitate și este foarte ușor de manevrat. El prezintă o interfață “VISUAL”, care permite comutarea cu ușurință dintr-o fereastră în alta, fără a întrerupe aplicația sau a pierde date introduse anterior.
Interfața principală se prezintă astfel:
Fig. 6.1 Interfața principală
Această interfață, pe lângă prezentarea autorului și a titlului lucrării pe care o însoțește, cuprinde patru meniuri, după cum urmează:
File: conține numai submeniul Close, care dacă este apelat, închide aplicația;
1 – Algoritmi pentru grafuri: conține trei submeniuri:
Algoritmul lui R.C. Prim.
Algoritmul lui J.B. Kruskal.
Fiecare dintre aceste submeniuri apelează o nouă fereastră de aplicații (vor fi prezentate fiecare în parte).
2 – Algoritmi pentru căi minimale
Algoritmul lui E.W. Dijkstra.
Algoritmul lui L.R. Ford.
Algoritmul lui R.W. Floyd.
Algoritmul lui M. Pollack.
3 – Algoritm pentru fluxuri
Algoritmul lui Ford & Fulkerson.
– Algoritmi pentru grafuri – Prim & Kruskal
Interfața inițială a algoritmului lui Prim se prezintă astfel:
Fig. 6.2 Interfața algoritmului lui Prim
După cum se poate observa pe figură, aplicația permite încărcarea unui exemplu demonstrativ (sau eliminarea lui) cu ajutorul butonului Load (sau Delete pentru ștergerea exemplului), această operație fiind opțională. Odată ca avem un exemplu de rețea, putem introduce datele necesare simulării și anume: numărul de noduri de date și legăturile dintre noduri (nodul de start, nodul de stop și lungimea legăturii de date).
Odată introdus numărul de noduri al rețelei, se va apăsa butonul Create pentru ca programul să poată culege informația (evenimentul) introdusă și să înceapă crearea scheletului rețelei de comunicații. După aceasta putem începe introducerea celorlalte 3 tipuri de date, având grijă ca după fiecare succesiune de 3 introduceri (nod de start, nod de stop și lungimea legăturii dintre noduri), să apăsăm butonul Next, care are rolul de a introduce datele furnizate de utilizator în baza de date a programului și de a permite o nouă introducere de date. Trebuie menționat faptul că la orice introducere de date eronate, sistemul de validări atenționează utilizatorul despre eroarea de introducere și îndrumă către reintroducerea datelor în formatul corect.
După ce toate datele au fost introduse se va apăsa butonul OK, care va permite afișarea matricei de legături într-o fereastră de afișare a rezultatelor, dar și afișarea rețelei sub formă grafică, conform datelor introduse. Fereastra aplicației suferă modificări astfel:
Fig. 6.3 Interfața algoritmului după introducerea datelor
La acest moment, pentru protecția datelor introduse, nu mai este activ decât butonul Run, care are rolul de a da în execuție simularea efectivă și de a afișa rezultatele finale în fereastra de rezultate. Pentru exemplul din figură, simularea întoarce o sumă de rezultate matematice și grafice, care se prezintă astfel:
Fig. 6.4 Interfața după terminarea simulării
Pe figură se pot distinge trei tipuri de rezultate: rezultatele din caseta de rezultate, care constau în istoria arborelui minimal, rezultate grafice, care prezintă în mod sugestiv (cu culoare roșie) arborele minimal calculat de algoritm și un rezultat matematic reprezentat de dimensiunea arborelui minimal.
Avantajul principal al aplicației îl constă interactivitatea de care beneficiază, avantaj care poate fi foarte folositor pentru compararea unor rezultate. La terminarea aplicației se poate închide fereastra cu butonul Exit.
În principal, algoritmul lui Kruskal nu diferă cu mult de cel al lui Prim, în sensul că rezultatele furnizate de el trebuie să fie aceleași cu cele furnizate de algoritmul anterior. Diferența care apare constă în faptul că pe lângă numărul de noduri, mai trebuie introdus și numărul de arce, iar acestea trebuie gestionate corect, pentru a nu se produce vreo eroare. Această gestionare se face cu o casetă de editare în care, la fiecare introducere de arc (cu butonul Next), are loc o incrementare automată, pentru a putea gestiona numărul de arce care trebuie introdus. Cele menționate anterior se materializează în următoarea interfață:
Fig. 6.5 Interfața pentru algoritmul lui Kruskal
După introducerea datelor, lucrurile decurg asemănător algoritmului lui Prim, iar rezultatele sunt identice.
2. – Algoritmi pentru căi minimale
În cadrul acestui tip de algoritmi, softul prevede patru algoritmi pentru căi minimale, fiecare cu specificul lor:
algoritmul lui Dijkstra furnizează calea minimă dintre două noduri de date introduse de utilizator;
algoritmul lui Ford, față de algoritmul lui Dijkstra, ia în calcul și căile cu cost negativ și apoi calculează calea minimă dintre cele două noduri;
algoritmul lui Floyd calculează toate căile minime dintr-o rețea, dintre toate perechile de noduri existente în rețea;
algoritmul lui Pollack furnizează calea minimă secundă dintre două noduri ale unei rețele.
Algoritmul lui Dijkstra
Interfața algoritmului se aseamănă foarte mult cu cea de la algoritmii pentru grafuri, însă de această dată este nevoie de intervenția utilizatorului pentru a se putea efectua calculele, în sensul că acesta trebuie să introducă în plus și nodul sursă și cel destinație. În funcție de acestea calculele sunt efectuate și se afișează rezultatele.
Procedeul de introducere al datelor este același cu cel de la algoritmii pentru grafuri, iar după introducerea nodurilor de start și de stop se apasă butonul Run, care are ca rezultat afișarea rezultatelor în forma următoare:
Fig. 6.6 Interfața de rezultate pentru algoritmul lui Dijkstra
Se observă același tipuri de rezultate ca și în cazul anterior, în plus apărând marcate pe reprezentarea grafică și nodul sursă și cel destinație sub forma “S” și “D”.
Algoritmul lui Ford
Acest algoritm se deosebește de cel al lui Dijkstra prin faptul că include în calcule și arcele cu cost negativ, astfel modificându-se fundamental rezultatele finale. În capitolul V au fost prezentate pe larg aspectele particulare ale acestui procedeu, împreună cu avantajele lui.
Algoritmul lui Floyd
Odată calculată calea minimă dintre două noduri, ne poate interesa să calculăm într-o rețea toate căile minime între oricare pereche de noduri din rețea. Acest lucru este realizat cu algoritmul lui Floyd.
Introducerea datelor este similară cu cea de la algoritmii pentru grafuri, în sensul că nu mai este nevoie de introducerea nodurilor sursă și destinație, deoarece acestea sunt selectate automat în toate combinațiile posibile oferite de rețea. După introducerea obișnuită a datelor, se vor activa două butoane: Run 1 și Run 2, care au următoarele sarcini:
Run 1 – furnizează matricea cu toate căile minime găsite;
Run 2 – furnizează matricea nodurilor predecesoare pentru fiecare combinație de noduri.
Pe un exemplu particular, la apelarea butonului Run 1, interfața va arăta astfel:
Fig. 6.7 Interfața algoritmului la apelarea butonului “Run1”
Datorită numărului mare de căi minime, nu se pot reprezenta toate pe o singură interfață, motiv pentru care, datorită interactivității programului, se poate apela unul din algoritmii anteriori pentru calcularea și vizualizarea oricărei căi minime dorite și a istoriei acesteia. Însă, istoria căii se poate deduce și din matricea nodurilor predecesoare afișată la apelarea butonului Run2:
Fig. 6.8 Interfața algoritmului la apelarea butonului “Run2”
Algoritmul lui Pollack
În unele cazuri este necesară aflarea căii minime secunde dintre două noduri ale unei rețele. Acest lucru este realizat cu ajutorul algoritmului lui Pollack în felul următor: după introducerea datelor și a perechii de noduri între care se dorește calcularea căii minime secunde, se vor activa două butoane:
Run 1 – furnizează calea minimă dintre cele două noduri;
Run 2 – furnizează calea minimă secundă dintre cele două noduri și arcul care a fost eliminat din calea minimă pentru găsirea acesteia.
La apelarea butonului Run 1, interfața are forma:
Fig. 6.9 Interfața algoritmului la apelarea butonului “Run1”
La apelarea butonului Run 2, interfața are forma:
Fig. 6.10 Interfața algoritmului la apelarea butonului “Run2”
3. – Algoritm pentru fluxuri – Ford & Fulkerson
Și în acest caz datele sunt introduse normal: număr de noduri, număr de arce, arcele (cu nod de start, de stop și lungimea arcului), nodul sursă și nodul destinație. De data aceasta avem numai un buton de Run, care, dacă este apelat, furnizează rezultatele algoritmului în caseta de rezultate, astfel:
Fig. 6.11 Rezultatele algoritmului lui Ford & Fulkerson
Concluzii:
În forma în care a fost prezentat, softul reprezintă un bun instrument pentru studierea algoritmilor pentru optimizarea rețelelor de comunicații. În urma rulării programului se pot obține informații utile cu privire la problema optimizării rețelelor de comunicații, care pot fi folosite la proiectarea și managementul acestora. Noțiunea de optimizare ridică, însă, foarte multe probleme și reclamă tot atâtea resurse din partea celui care dorește să o execute, motiv pentru care, în ultimul timp s-a pus din ce în ce mai mult accent pe acest aspect care a dus la reducerea semnificativă a costurilor unei rețele, dar și a timpului de transfer a informației. Fără îndoială avantajele optimizării sunt multiple și merită efortul studiilor îndelungate care au loc pe acest subiect.
Concluzii
Organizarea și implementarea sistemelor de comunicații reprezintă două procese mult prea complexe și care implică costuri destul de ridicate pentru a se baza numai pe intuiție și experiență acumulată și ca urmare se impune asocierea acestora cu aplicarea unor metode de calcul a parametrilor de structură, informaționali, funcționali, de fiabilitate și viabilitate, pornindu-se de la elementele determinante pentru rețelele de comunicații și anume:
costul sistemului de distribuție;
prioritatea datelor;
timpul necesar de răspuns;
productivitatea transferului de informații;
accesibilitatea;
fiabilitatea;
testarea;
planificarea evenimentelor;
confidențialitatea;
autenticitatea.
Vom ține cont de acești factori și vom avea parte de o rețea viabilă și de lungă durată.
Costul include o multitudine de elemente, altele decât prețul terminalelor sau al rețelelor. De exemplu, costurile aferente rețelelor locale sunt justificate de regulă de asigurarea unei viteze de operare superioară, deoarece timpul operatorilor și al calculatoarelor care utilizează aceste rețele este foarte prețios. În alte situații, fiabilitatea comunicațiilor este justificarea principală a costului. În multe cazuri, căderea unui sistem de comunicație a datelor atunci când ar trebui să funcționeze corect poate costa mult mai mult decât prețul sistemului însuși. Dacă prețurile nu ar conta, atunci majoritatea rețelelor de date ar fi o colecție de canale simple punct-la-punct. Într-adevăr, dacă un canal punct-la-punct poate fi încărcat la o viteză suficient de înaltă de transmitere a datelor, aceasta ar putea fi cea mai eficientă soluție de a rezolva o anumită problemă de transmitere a datelor, din punct de vedere al costului.
Ca urmare, după cum am mai amintit, vechile metode de planificare, analiză și sinteză bazate pe intuiție și experiență au trebuit completate cu metode științifice bazate pe aplicarea cercetării operaționale, ciberneticii și informaticii, acestea oferind posibilități de optimizare fundamentate matematic și astfel prelucrarea datelor devine mai eficientă.
Această lucrare a prezentat abordări ale modelelor matematice programabile și de simulare ale sistemelor de comunicații bazate pe aplicații ale teoriilor moderne ale matematicii, pornind de la elementele fundamentale ale teoriei probabilităților, statisticii matematice, teoriei grafurilor și fluxurilor de date.
În cadrul primei părți a lucrării au fost prezentate soluții matematice cu privire la optimizarea rețelelor de comunicații la nivel topologic, un domeniu cu aplicații de o gamă largă, având în vedere numeroasele arhitecturi topologice de rețele existente care se pot modela foarte eficient folosind teoria grafurilor.
În cea dea de-a doua parte, au fost descriși câțiva algoritmi de optimizare și câteva exemple particulare de funcționare a acestora. Fiecare algoritm în parte este însoțit de simularea computațională cu ajutorul limbajului de programare DELPHI 5.0, ca o frontieră între teorie și practică. Acest limbaj este foarte răspândit în cadrul programării calculatoarelor, iar un argument în plus pentru folosirea acestuia a fost faptul că este des utilizat în procesul de învățământ.
Lucrarea de față poate reprezenta un bun ghid pentru un studiu mai aprofundat al tipurilor de algoritmi pentru optimizarea rețelelor de comunicații. Datorită multitudinii de probleme care le reclamă acest subiect și volumului mare de informații, studiul poate fi continuat și completat și cu alți algoritmi existenți, sau în fază de proiect.
Bibliografie
“ Telecomunicații ” – Tatiana Rădulescu – Ed. Teora, București, 1998
“ Comunicații de date ” – Gilbert Held – Ed. Teora, București, 1998
“ Dicționar – calculatoare și Internet ” – Dr. Bryan Pfaffenberger, David Wall – Ed. Teora, București, 1999
“ Rețele de calculatoare ” – Andrew S. Tanenbaum, Computerpress Aora, București, 1997
“ Telefonia digitală în rețelele de telecomunicații (acces, transport, gestiune) ” – Sorina Zăhan, Grupul Microinformatica Cluj-Napoca, 1998
“ Teoria grafurilor. Analiza drumului critic ” – Gh. Ciobanu, Floare Mustață, Vasile Nica, Virginia Mărăcine
“Managementul rețelelor moderne de telecomunicații” – Titu Băjenescu – Ed. Teora, București, 1998
“Rețele de comunicații între calculatoare” – Ion Bănică, Ed. Teora, București, 1998
“Tehnologia CLIENT/SERVER pentru toți” – Doug Lowe, Ed. Teora, București, 1996
“Cercetare operațională” – vol. I, Vasile Podaru, Alexandru Ghiță, George Georgescu, Nicolae Vlad, Ed. ATM, București, 1988
“Structuri de date și algoritmi” – Vasile Podaru, Nicolae Vlad, Ed. ATM, București, 1999
“Rețele Locale de calculatoare – arhitecturi prezente și viitoare”, Claudiu Bulăceanu, Ed. Tehnică, București, 1995
“Optimizarea algoritmilor” – Ion Odăcescu, Ed. Militară, București, 1991
“Sinteza și analiza algoritmilor” – Leon Livovschi, Horia Georgescu, Ed. Științifică și Enciclopedică, București, 1986
“Tehnici de programare” – Tudor Sorin, Ed. Teora, București, 1995
“Tehnici de programare” – Valentin Cristea, Irina Athanasiu, Eugenia Kalisz, Valeriu Iorga, Ed. Teora, București, 1993
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Rolul Si Importanta Procesului de Simulare Si Optimizare a Retelelor de Comunicatii (ID: 149180)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.