Analiza Dirijarii Pachetelor la Nivelul Retea Si Aplicarea Algoritmior Dijkstra Si Bellmann

Analiza dirijării pachetelor la nivelul rețea și aplicarea algoritmior DIJKSTRA ȘI BELLMANN

INTRODUCERE

Titlul proiectului de diplomă este “Studiul algoritmilor de dirijare la nivelul rețea”. Lucrarea se poate considera ca fiind structurată în două părți: o parte care abordează problema dirijării unicast și o a doua parte care tratează unele aspecte ale transmisiilor multicast. De asemenea, constitue un material care se dorește a fi un studiu în amănunt al celor mai întâlniți algoritmi și tehnici de dirijare specifice rețelei Internet, precum și al protocoalelor de dirijare unicast și multicast ce implementează acești algoritmi.

Acest subiect este important, având în vedere dezvoltarea explozivă a Internetului și a serviciilor multimedia cerute de către tot mai numeroșii utilizatori.

La ora actuală există o mare varietate de rețele de calculatoare cu caracteristici mult diferite, atât din punct de vedere al dimensiunii, al domeniului de utilizare, cât și din punct de vedere al tehnologiei de transmisie și al structurii elementelor componente.

Internet-ul este o rețea virtuală ce se întinde efectiv pe tot globul, care interconectează în mod uniform calculatoare individuale și rețele de calculatoare, indiferent de deosebirile constructive și de distanțele fizice dintre acestea. La momentul actual, arhitectura Internetului răspunde comunicațiilor așa-numite unicast, care nu implică decât două entități în schimbul de informații și utilizează un principiu numit “best-effort” care nu garentează debitul oferit pentru distribuirea pachetelor. Pentru a îndeplini noile cerințe ale aplicațiilor multimedia și de grup, care pot fi satisfăcute cu dificultate în condițiile actuale, rețelele de comunicații trebuie să-și mărească vitezele de transmisie, dar și să introducă noi servicii și funcționalități. Aceste schimbări au ca efect apariția unor noi tehnici, a unor noi modele de interacțiune, cu protocoale și mecanisme specific, mai sofisticate și mai dinamice. Ca efect al acestor cerințe, a apărut conceptul multicast, care se ocupă de transmiterea pachetelor de la 1 sau N entități, sau de la N la M entități.

În cadrul proiectului de față s-a urmărit realizarea unui program în C# care implementează cei mai utilizați algoritmi în rețeaua Internet: Bellman Ford și Dijkstra, care stau la baza protocoalelor de dirijare OSPF și RIP. La realizarea aplicației s-a urmărit:

• calcularea drumurilor minime pentru grafuri neorientate;

• posibilitatea vizualizării grafului, realizând o dispersie grafică cât mai corectă;

• vizualizarea tuturor etapelor efectuate în timpul rulării celor doi algoritmi, deci a rezultatelor intermediare;

• afișarea informațiilor utile într-un mod plăcut și facil;

• posibilitatea dezvoltării ulterioare a aplicației prin adăugarea de noi facilități.

Lucrarea de față este structurată în patru capitole, cu subcapitolele aferente și lista de referințe bibliografice.

Capitolul 1 “Rețelele de comunicații și protocoalele lor” prezintă câteva lucruri de bază despre rețele și protocoale. Este abordat protocolul de nivel rețea, numit IP (Internet Protocol), liantul care ține legat Internet-ul, care oferă mecanismul suport pentru a transfera date într-un mod neorientat pe conexiune. O mașină este pe Internet dacă folosește stiva de protocoale TCP/IP, are o adresă IP și are posibilitatea de a trimite pachete IP către toate celelalte mașini de pe Internet.

Capitolul 2, “Dirijare în ruterele interioare și în ruterele exterioare”, introduce noțiunile de dirijare, ruter, algoritm de dirijare, tabelă de dirijare, protocol de dirijare. În acest capitol am dezvoltat câțiva dintre cei mai importanți algoritmi, și anume: dirijarea pe calea cea mai scurtă, dirijarea prin inundare, dirijarea bazată pe flux, dirijarea ierarhizată, dar și cei doi algoritmi care sunt utilizați pentru dirijare în rețeaua Internet (după Vectorii Distanță și după Starea Legăturii). Lucrarea prezintă și o clasificare a protocoalelor de dirijare existente,, urmată de descrierea caracteristicilor principalelor protocoale de dirijare unicast interioară (RIP, OSPF), respectiv exterioară (BGP).

Capitolul 3, intitulat “Dirijarea multicast”, tratează câteva aspecte ale dirijării multicast și realizează o clasificare a protocoalelor necesare acestui tip de dirijare. Sunt prezentate în această lucrare două dintre problemele traficului multicast, răspândirea redusă în Internet și transmisia multicast pentru noduri mobile, fiind identificate cauzele fiecăreia, dar și soluțiile posibile.

Capitolul 4 este o prezentare a modului în care aplicația practică a fost implementată, a componentelor software folosite și a facilităților oferite.

În final sunt prezentate concluziile privind utilitatea aplicației, precum și bibliografia folosită.

Capitolul 1. PROBLEMATICA DIRIJARII PACHETELOR

1.1.Dirijarea multicast

Odată cu dezvoltarea Internetului au crescut și nevoile de comunicare, de la text s-a ajuns la text însoțit de imagini, accesibil prin WWW (World Wide Web), cerințele la ora actuală fiind conținut audio/video în timp real. Ca urmare, modele și mecanismele folosite pentru comunicare trebuie să evolueze. Cerințele pentru distribuirea datelor audio-video în timp real la un număr foarte mare de clienți răspândiți în Internet diferă față de necesitățile transmisiei unei pagini web prin HTTP (HyperText Transfer Protocol) sau descărcării unui fișier prin FTP (File Transfer Protocol).

Modelele disponibile, unicast și broadcast, nu corespund noilor cerințe. Comunicarea unicast implică existența unei surse și a unei destinații, pentru transmiterea acelorași date la mai multe destinații fiind necesare căi diferite, pentru fiecare receptor fiind transmisă o copie a fluxului audio-video. Rezultă că folosirea unicast nu oferă o soluție deoarece odată cu creșterea numărului de receptori va crește încărcarea sursei, dar și a rețelei. Cealaltă alternativă este transmisia broadcast, ce permite reducerea debitului ocupat, în comparație cu unicast. Pentru a trimite date tuturor stațiilor dintr-o rețea locală se transmite o singură copie a pachetului. Această soluție pare mai potrivită, dar ea este insuficientă deoarece, foarte probabil, nu toți receptorii se vor găsi în aceeași rețea. O alternativă este cea oferită de modelul multicast, care permite comunicarea între mai multe surse și mai mulți receptori într-un mod optim. Transmisia multicast permite trimiterea datelor la mai mulți receptori, într-un mod eficient, fără a fi necesară o copie a pachetului pentru fiecare destinație. Receptorii pot fi localizați oriunde în Internet, ei decizând dacă doresc să recepționeze datele.

1.2. Modelul multicast IP

Modelul multicast pentru IPv4 (Internet Protocol) a fost propus de Stephen Deering, fiind apoi adoptat ca standard [11]. Caracteristicile acestuia sunt:

• semantică IP: sursa poate trimite pachete multicast în orice moment, fără să se înscrie sau să planifice transmisia, livrarea datelor fiind de tipul best-effort.

• grup deschis: sursa trebuie să cunoască doar adresa grupului multicast, fără a ști membrii grupului și fără a se înscrie la acel grup; un grup poate avea un număr nelimitat de surse.

• grup dinamic: membrii grupului multicast pot să se înscrie sau să părăsească grupul oricând doresc, fără să trebuiască să negocieze cu vreo entitate de management centralizat.

Acest model se referă doar la stațiile finale, el nediscutând modalitățile în care rețeaua realizează rutarea multicast, în acest scop fiind folosite protocoale de rutare dedicate. Modelul nu specifică nici modul de alocare al adreselor multicast, mecanismele pentru asigurarea calității sau securității serviciului.

Modelul multicast a fost introdus sub forma unei extensii în IPv4, acesta fiind motivul pentru care standardul IPv6 a fost proiectat de la început incluzând mecanismele necesare transmisiilor multicast, implementarea acestora fiind obligatorie pentru toate stațiile IPv6.

Pentru a distribui datele de la surse la receptori sunt necesare două tipuri de protocoale. Primul tip este folosit de stații pentru a se înscrie și pentru a părăsi grupul multicast, funcția de management al grupului fiind realizată în IPv4 de IGMP (Internet Group Management Protocol) [12], iar în IPv6 de MLD (Multicast Listener Discovery) [13]. Al doilea tip sunt protocoalele de rutare multicast propriu-zise ce construiesc arborii de distribuție a datelor de la surse la receptori. Rutarea multicast în interiorul unui sistem autonom se realizează cu ajutorul următoarelor protocoale: DVMRP (Distance Vector Multicast Routing Protocol) [14], MOSPF (Multicast extensions for Open Shortest Path First) [15], PIM (Protocol Independet Multicast) [16] sau CBT (Core-Based Tree) [17]. Mecanismele folosite pentru transmisia multicast între sistemele autonome sunt mai complexe, putând fi utilizate protocoalele MSDP (Multicast Source Discovery Protocol) [12] și MBGP (Multiprotocol Border Gateway Protocol) [18]. Multe dintre ruterele folosite în Internet implementează aceste protocoale, dar nu le folosesc, nepermițând astfel dirijarea traficului multicast.

1.3. Soluții alternative multicast

Ca urmare a faptului că modelul multicast IP nu este disponibil la scală largă în Internet, dar și pentru a rezolva o parte dintre limitările modelului multicast IP, au apărut o serie de tehnologii alternative multicast, sau servicii alternativele de comunicare în grup, numite AGCS (Alternative Group Communication Service). Acestea grupează sub o singură denumire toate mecanismele care au abilitatea de a transmite simultan informația de la o sursă la mai mulți receptori. Tehnologiile AGCS pot fi folosite pentru a interconecta regiunile care suportă multicast, sau în mediile în care dirijarea multicast nu este potrivită, cum ar fi rețelele ad-hoc și rețele mobile fără o infrastructură fixă. Altă situație ce poate fi rezolvată prin folosirea AGCS este cazul în care avem un număr mare de grupuri multicast cu un număr mic și foarte dinamic de receptori. Pentru acest exemplu, încărcarea cauzată de schimbul de semnalizări datorat protocoalelor multicast limitează scalabilitatea sistemului. Mecanismele de securitate ca autentificarea, autorizarea, criptarea nu sunt posibile pentru transmisiile multicast, ele putând fi implementate cu ajutorul serviciilor alternative. Există o sumedenie de propuneri de mecanisme alternative, câteva exemple fiind: UMTP (UDP Multicast Tunnelling Protocol), CastGate, XCast, Xcast+ și HyperCast.

Capitolul 2. PROTOCOALE DE DIRIJARE A PACHETELOR

2.1. Protocoale de dirijare multicast intradomeniu

Transmisia IP multicast este un mecanism de strat rețea în care datele sunt transmise de la o sursă la mai mulți destinatari. Aplicații de acest gen sunt transmisiile audio-video, aplicațiile de teleconferință. În cazul transmisiei unicast (punct la punct), datele sunt trimise către o singură stație, iar în cazul broadcast, datele sunt trimise către toate stațiile dintr-o arie dată, de exemplu dintr-o rețea locală. În cazul multicast, datele sunt transmise unui set de stații care au indicat că doresc să recepționeze datele, set numit grup multicast [11].

Pentru a putea realiza transmisia multicast sunt necesare o serie de protocoale și meca-nisme specifice la stratul rețea. În primul rând, avem nevoie de adrese speciale, numite adrese multicast, care desemnează grupul multicast drept destinatar al datagramei. În al doilea rând, este necesar un mecanism care să permită unei stații să se înscrie sau să părăsească grupul multicast, numite protocoale de management al grupului. În final, sunt necesare protocoale de rutare multicast, care trebuie să creeze arbori de distribuție de la sursă la membrii grupului.

Grupurile multicast sunt dinamice, în sensul că orice stație poate să se înscrie și să părăsească orice grup. Dimensiunea unui grup multicast nu este limitată la un anumit număr de membri. O stație poate să se înscrie simultan la mai multe grupuri. Un pachet multicast este o datagramă IP care are drept adresă destinație o adresă IP multicast. Acest pachet este distribuit la toate stațiile care sunt membre ale grupului desemnate de adresa multicast. O stație poate să trimită pachete multicast către orice grup, stația care transmite netrebuind să fie membră a acestuia. De asemenea, mai multe stații pot să transmită simultan către același grup multicast.

2.2. Adrese multicast IPv4 și IPv6

Adresele multicast IPv4 au o structură diferită de cea a adreselor unicast. Acestea au tot 32 de biți, aparținând clasei D, clasă identificată de primi patru biți ai adresei cu valoarea 1110 (figura

3.1). Cei 28 de biți rămași constituie identificatorul grupului multicast [11].

Figura 3.1 Formatul adresei multicast IPv4

Adresele multicast IPv6 au 128 de biți și sunt împărțite în patru câmpuri (figura 3.2). Primul câmp pe 8 biți identifică adresa ca fiind o adresa multicast. Acesta este urmat de un câmp pe 4 biți, doar semnificația celui mai puțin semnificativ bit fiind definită. Valoarea 0 indică o adresă binecunoscută (permanentă), iar valoarea 1 indică o adresă de tranziție (temporară).

Câmpul scop pe 4 biți indică dacă grupul multicast poate include numai noduri din aceeași rețea locală, același site, aceeași organizație, sau pot fi adrese IPv6 cu semnificație globală [19]. Identificatorul grupului multicast este pe 112 biți, mai multe grupuri putând avea același identificator dacă diferă valoarea câmpului flags sau a câmpului scop.

2.3. Managementul grupului multicast

O stație poate să se înscrie sau să părăsească grupul multicast oricând dorește, ea putând să fie membră a mai multor grupuri. Apartenența stațiilor la diferitele grupuri multicast este gestionată folosind protocoale de management a grupului multicast. Funcțiile specifice ale unui astfel de protocol sunt:

• înscriere (Join): stația se poate înscrie la un grup multicast.

•părăsire (Leave): stația poate informa routerul că a părăsit un anumit grup.

•întrebare (Querying): ruterul poate întreba dacă există membri ai unor grupuri multicast pe acea legătură.

•raportare (Reporting): stația poate informa ruterul că aparține unui anumit grup multicast.

Protocolul care realizează aceste funcții pentru IPv4 este IGMP (Internet Group Manage-ment Protocol) [12], iar pentru IPv6 este MLD (Multicast Listener Discovery) [13]. Protocolul IGMP are trei versiuni, iar MLD are doar două versiuni, ultima versiune a fiecărui protocol permițând stației să specifice în mod explicit sursa de la care dorește să primească date multicast.

2.4. Principiile dirijării multicast

Pentru a distribui datele multicast la toți receptorii, ruterele multicast creează arbori de distribuție care definesc calea pe care pachetele o urmează prin rețea. Exista două tipuri de arbori de distribuție multicast, arbori sursă (source tree) și arbori partajați (shared tree).

Cel mai simplu arbore de distribuție multicast este arborele sursă SBT (Source Based Tree). Acesta are rădăcina la sursă iar ramurile formează un arbore care se răspândește prin rețea până la receptori, acest tip de arbore folosind calea cea mai scurtă prin rețea. Se folosește notația (S, G) pentru a desemna un arbore sursă, unde S este adresa IP a stație sursă, iar G este adresa multicast a grupului. Această notație ne arată că există un SBT diferit pentru fiecare sursă care transmite către același grup multicast.

Spre deosebire de arborii sursă care au rădăcina la stația sursă, arborii partajați SDT (Shared Distribution Tree) folosesc o singură rădăcină comună, care este plasată într-un punct ales din rețea. Această rădăcina comună se numește Rendez-vous Point (RP) în cazul protocolului PIM (Protocol Independent Multicast). Arborele partajat este unidirecțional, traficul de la sursă fiind trimis spre RP folosind un arbore sursă. Traficul este apoi transmis mai departe pe arborele partajat de la RP către fiecare receptor. O situație interesantă poate apărea dacă între sursă și RP există receptori, în acest caz receptorul primind traficul direct de la sursă.

Arborii sursă prezintă avantajul de a construi calea optimă între sursă și receptori, avantaj ce garantează întârzierea cea mai mică la transmisia traficului multicast. Totuși această optimizare are un preț, ruterele trebuind să mențină informații referitoare la calea către fiecare sursă. Într-o rețea care are mii de surse și mii de grupuri, traficul de dirijare suplimentar poate suprasolicita rețeaua, iar tabelele de dirijare multicast vor ocupa memoria ruterelor. Arborii partajați au avantajul că necesită resurse minime în fiecare ruter, astfel necesarul de memorie pentru tabelele de dirijare este mic. Dezavantajul arborilor partajați este că în anumite situații, calea între sursă și destinație poate fi suboptimală. În dirijarea unicast traficul este transmis prin rețea de la sursă la destinație, în funcție de adresa destinație. Ruterul caută în tabela de dirijare adresa rețelei destinație și transmite o singură copie a pachetului pe interfața corespunzătoare acesteia. În transmisia multicast, traficul trebuie distribuit la mai multe destinații, reprezentate de grupul multicast. Ruterul multicast trebuie să determine care este sensul către sursă și care este sensul către receptori, iar dacă există mai multe direcții către receptori, ruterul va multiplica pachetele și le va trimite pe interfețele corespunzătoare. Putem spune că traficul multicast este transmis înspre sursă, nu înspre receptori,

acest mecanism numindu-se transmisie pe cale inversă RPF (Reverse Path Forwarding) [11].

Mecanismul RPF permite ruterului să transmită corect traficul multicast în jos pe arborele de distribuție, acesta folosind tabela de dirijare unicast existentă pentru a determina sensul spre sursă și cel spre receptori. Un ruter transmite pachete multicast numai dacă ele au fost recepționate pe interfața corespunzătoare sensului spre sursă, acest mecanism garantând că arborii de distribuție nu conțin bucle de rutare. Când ruterul primește un pachet multicast, îi caută adresa sursă a pachetului în tabela de dirijare unicast pentru a determina dacă pachetul a fost recepționat pe interfața care se găsește pe calea cea mai scurtă spre sursă și doar în acest caz va distribui pachetul mai departe, în caz contrar pachetul fiind eliminat. Acest mecanism se numește verificare RPF (RPF check).

2.5. PROTOCOALE DE DIRIJARE MULTICAST

DVMRP (Distance Vector Multicast Routing Protocol) este un protocol de dirijare multicast inspirat de RIP care creează arbori SBT, fiind standardizat prin documentul RFC1075. Diferența este că RIP transmite pachetele pe baza informației referitoare la nodul următor spre destinație, în timp ce DVMRP creează arbori de distribuție pe baza informației referitoare la nodul precedent spre sursă. Datorită înrudirii cu RIP, DVMRP se confruntă cu limitări similare cum ar fi: convergența lentă, problema numărări la infinit, metrica fiind numărul de hop-uri.

DVMRP trebuie să interopereze cu IGMP pentru a afla dacă pachetele multicast trebuie transmise mai departe. Acest protocol poate atașa sau șterge în mod dinamic, în tabela de dirijare, rețelele care doresc să primească trafic multicast pentru un anumit grup. Funcționarea DVMRP se realizează prin 2 procese esențiale: descoperirea vecinilor și schimbul de rute [14]. Mesajele DVMRP sunt transmise folosind protocolul IP cu valoarea doi în câmpul protocol, ceea ce identifică pachetele drept pachete IGMP [14].

În momentul în care DVMRP este activat, pe un ruter vor fi căutate rutere DVMRP învecinate. Scopul descoperirii vecinilor este de a localiza alte rutere DVMRP direct conectate și de a afla proprietățile acestor vecini [14]. Mesaje de tip Probe sunt transmise pe toate interfețele pe care a fost pornit DVMRP la un interval de 10 secunde. Dacă un vecin descoperit mai devreme nu răspunde cu propriul mesaj Probe pe parcursul a 35 de secunde, acel vecin este declarat nefuncțional. Inițial, DVMRP anunță numai rețelele direct conectate, iar pe măsură ce sunt învățate alte rețele, prin mecanismul de anunțare a rutelor, acestea sunt introduse în tabela locală de dirijare, fiind anunțate vecinilor. Spre deosebire de mesajele de anunțare a rutelor RIP, rutele DVMRP sunt transmise în format prescurtat.

Protocolul MOSPF (Multicast Extensions to OSPF) oferă performanțe mai bune decât DVMRP deoarece este un protocol cu starea legăturii, având o convergență mai rapidă, mecanisme pentru evitarea buclelor de rutare și nu există trafic de control periodic. MOSPF nu este un protocol separat de OSPF, fiind o extensie a acestuia standardizată în RFC 1584. A fost definit un nou mesaj LSA (Link State Advertisment) de apartenență la grup (Group Membership LSA), iar câmpul Opțiuni a fost extins să includă un bit care indică prezența suportului pentru multicast.

Operarea MOSPF implică alegerea unui ruter desemnat DR (Designated Router). Atunci când o stație trimite un mesaj IGMP de înscriere la un grup, ruterul DR creează o înregistrare în baza de date locală cu grupuri, care conține adresa grupului și rețeaua atașată care are receptori pentru acel grup. Ruterul DR transmite un mesaj LSA de apartenență la grup pentru fiecare grup atașat, care specifică adresa grupului, identificatorul ruterului și toate rețelele atașate care conțin membri ai acelui grup. Motivul inundării acestor mesaje LSA în aria OSPF este ca toate ruterele MOSPF să dețină o copie a tuturor mesajelor LSA de apartenență la grup care își au originea în acea arie. La fel ca la OSPF, toate ruterele MOSPF din arie trebuie să dețină baze de date cu starea legăturii identice, singura diferență între aceste baze de date fiind includerea mesajelor LSA de apartenență la grup. Astfel, orice ruter MOSPF din domeniu poate calcula același arbore de distribuție. Arborele nu este calculat imediat, el fiind calculat la cerere atunci când primul pachet multicast pentru un anumit grup este primit. Pentru aceasta, informația referitoare la receptori este luată din mesajele LSA de apartenență la grup, iar informația referitoare la sursă este extrasă din primul pachet multicast recepționat. Avantajul acestui mecanism este că ruterul știe deja locația receptorilor înainte de a realiza calculul, iar pachetele multicast nu vor fi transmise în toată rețeaua.

O problemă se poate ivi în situația în care rutere OSPF și MOSPF coexistă în rețele multiacces, în acest caz trebuind să ne asigurăm că ruterul MOSPF va fi ales ruter DR. Dacă un ruter OSPF devine DR nu se vor mai transmite mesajele LSA de apartenență la grup și în consecință nici un pachet multicast nu va mai fi dirijat. Cea mai importantă limitare a protocolului MOSPF apare în situația în care topologia se modifică, toată tabela de dirijare trebuind ștearsă și recalculată. Din acest motiv este foarte important ca domeniul să fie cât mai stabil [15]

PIM (Protocol Independent Multicast) are două moduri de operare, dens și răsfirat, constând astfel în două protocoale de dirijare PIM-DM (PIM Dense Mode) și PIM-SM (PIM Sparse Mode). Are în denumire expresia independent doarece se folosește de protocoalele de dirijare unicast existente pentru a determina căile multicast.

Versiunea întâi a celor două moduri de lucru PIM, DM și SM, nu a fost standardizată de IETF, totuși echipamentele produse de Cisco le impelmentează. Versiunea a doua a modului PIM-DM a fost standardizată prin RFC 3973, iar PIM-SMv2 a fost standardizat prin RFC 4601, ce revizuiește documentul RFC 2362.

Mesajele versiunii a doua, PIMv2, sunt încapsulate în datagrame IP având numărul de protocol 103, iar prima versiune folosește mesaje de tip IGMP pentru transportul infomației de rutare [16]. Mesajele PIM pot fi transmise folosind atât unicast cât și multicast, în cazul folosirii transmisiei multicast fiind utilizată adresa 224.0.0.13 pentru IPv4 [11].

2.6. Protocoale de dirijare multicast interdomeniu

Transmisia multicast interdomeniu necesită folosirea mai multor protocoale: MBGP (Multiprotocol Border Gateway Protocol), MSDP (Multicast Source Discovery Protocol) și PIM-SSM (PIM Source Specific Multicast). Cerințele acestor protocoale explică dificultățile ridicate ale implementării dirijării multicast interdomeniu.

MBGP: asigură o metodă pentru a alege rutele folosite pentru verificarea RPF. Verificarea RPF este un mecanism folosit în dirijarea multicast pentru a determina căile pe care arborii de distribuție multicast le vor urma. Documentul RFC 2858 descrie specificațiile protocolului MBGP, acesta fiind o extensie a protocolului BGP [8]. Rutele obținute sunt folosite pentru a realiza verificarea RPF la granița dintre două AS-uri.

Tabele de dirijare BGP sunt menținute separat pentru unicast și pentru multicast. Tabela pentru multicast este creată din tabela unicast prin aplicarea politicilor de dirijare multicast, pentru verificările RPF și pentru protocolul PIM folosindu-se înregistrările din această tabelă.

MSDP: Ruterele RP dintr-un sistem autonom nu au nici un mecanism prin care să descopere sursele multicast aflate în alte domenii. Protocolul MSDP permite ruterelor RP să partajeze informația referitoare la sursele multicast active [12]. Fiecare RP cunoaște receptorii din propriul domeniu, iar dacă un RP descoperă surse active din alt domeniu, el poate transmite această informație stațiilor interesate, permițând și transmisia traficul multicast între diferitele domenii. Protocolul MSDP permite ca fiecare domeniu să aibă propriul ruter RP, independent de alte domenii, dar care să realizeze transmisia traficului multicast între domenii, folosind protocolul PIM-SM.

PIM-SSM: Dacă două aplicații cu surse și receptori diferiți folosesc aceeași adresă IP multicast, utilizatorii celor două aplicații vor recepționa traficul de la toate sursele. Receptorii pot filtra traficul nedorit la nivel aplicație, dar este de dorit evitarea acestei situații, deoarece ea provoacă trafic nedorit în rețea. Mecanismul SSM este o extensie a protocolului PIM care permite distribuția eficientă a datelor în aplicațiile de tipul o singură sursă și mai mulți receptori. SSM permite clientului, care a aflat adresa sursei multicast, să recepționeze traficul multicast direct de la sursă, nemaitrebuind să folosească arborele partajat. Descoperirea surselor multicast din alte domenii, folosind MSDP, nu mai este necesară în cazul folosirii SSM.

Tehnologia necesară transmisiei multicast în Internet este diponibilă de mai mult de o decadă, astfel toate echipamentele de dirijare implementând protocoale de dirijare multicast. De asemenea toate sistemele de operare includ protocoale multicast în implementarea proprie a stivei TCP/IP, totuși în realitate accesul la multicast în Internet este disponibil doar în mediile academice și în instituțiile de cercetare în domeniul telecomunicațiilor, nu și pentru utilizatorul obișnuit.

Această problemă are numeroase cauze tehnice și comerciale. abordate de mai mulți autori [20]. Pe de o parte avem complexitatea și limitările protocoalelor multicast, iar pe de altă parte avem lipsa unei cereri reale din partea clienților.

Blocajul tripartit

Pieter Liefooghe menționează ca principală cauză a răspândirii reduse a accesului multicast blocajul tripartit, ce implică clienții, furnizorii de Internet și furnizorii de conținut [20]. Clienții nu sunt interesați de modul în care se face accesul la conținut, unicast sau multicast. Aceștia doresc un serviciu de calitate și nu sunt conștienți de avantajele oferite de multicast. Atât timp cât utilizatorii nu știu ce este multicast și la ce le poate fi de folos, ei nu solicită acest serviciu de la furnizorul de Internet. Din punctul de vedere al furnizorilor de conținut, folosirea multicast ar însemna o reducere substanțială a debitului ocupat, dar lipsa clienților și a funizorilor de Internet care să poată transporta conținut multicast nu justifică investiția în această tehnologie. Cea de-a treia parte implicată, dar și cea mai importantă, sunt furnizorii de Internet. În ciuda eforturilor depuse de grupuri din industrie pentru a promova tehnologia multicast, doar o mică parte a furnizorilor îl oferă. Furnizorii de Internet se justifică prin lipsa unui număr destul de mare de clienți (furnizori de conținut și utilizatori obișnuiți) care să acopere costurile activării multicast în rețelele proprii.

Transmisia multicast fiabilă

Pe stratul transport se folosește UDP deoarece, în general, comunicarea se face unidirecțional și fără stabilirea unei conexiuni, deci nu se poate utiliza TCP. Folosirea UDP implică lipsa unor mecanisme pentru controlul conexiunii și al erorilor. Altă problemă datorată folosirii UDP este fenomenul de fragmentare a pachetelor care poate duce la pierderea de pachete. Caracteristica transmisiilor multicast de la o sursă la mai mulți receptori face ca mecanismele de corecție a erorilor bazate pe cereri de retransmisie să fie imposibil de implementat, în cazul comunicării fără stabilirea unei conexiuni fiind sarcina stratului aplicație să rezolve probleme cauzate de erori. Principala aplicație pentru tehnologia multicast este transmisia de fluxuri audio/video, care suferă la pierderile de pachete datorită tehnicilor de compresie folosite. O posibilă soluție ar fi utilizarea unor algoritmi de compresie care să reziste la pierderile de pachete.

Complexitatea dirijării multicast

Modelul multicast are două componente, grupul de receptori și protocoalele de dirijare. Un grup multicast este identificat printr-o adresă IP multicast, ce este folosită pentru înscrierea la grup, dar și pentru transmiterea datelor. Inițiatorul unui grup multicast trebuie să aloce o adresă multicast unică globală folosind imul dintre următoarele protocoale: MASC (Multicast Address Set Claim) sau MADCAP (Multicast Address Dynamic Client Allocation Protocol). Managementul grupului multicast necesită folosirea protocoalelor IGMP și MLD, cu versiunile aferente.

Distribuția datelor multicast implică utilizarea unor protocoale de dirijare specifice pentru crearea și menținerea arborilor de distribuție. Toate ruterele din arborele de distribuție trebuie să stocheze informație de stare pentru fiecare pereche sursă, grup multicast. Este necesar un mecanism de anunțare a surselor multicast pentru a permite receptorilor să se înscrie la grup. Protocoale de rutare multicast care lucrează în mod răsfirat folosesc un nod central pe care îl anunță receptorilor, care se vor putea înscrie la grup fără a cunoaște sursa. Aceste mecanisme ridică probleme de scalabilitate odată cu creșterea numărului de grupuri.

Pentru a permite funcționarea protocoalelor de dirijare multicast este obligatoriu ca toate ruterele aflate pe calea de la sursă la receptor să fie configurate pentru multicast. Este suficient ca doar o legătură să nu fie configurată corect pentru ca traficul multicast să numai fie recepționat.

Securitatea transmisiilor multicast

Asigurarea securității pentru modelul de comunicare multicast este mai complicată decât pentru unicast, deoarece sunt implicate mult mai multe entități, între care nu se stabilesc relații de încredere, sursa multicast necunoscând membrii grupului.

Mecanisme de securitate ca autentificarea, autorizarea, criptarea nu sunt posibile pentru transmisiile multicast. Autentificarea este procesul prin care o stație trebuie să furnizeze informații despre identitatea sa pentru a putea trimite sau recepționa date pentru un grup multicast. Autorizarea este procesul prin care unei stații autentificate i se permite efectuarea unor acțiuni, iar criptarea asigură confidențialitatea datelor transmise, astfel încât ele să nu poată fi citite de alții.

Un utilizator se poate înscrie la oricâte grupuri dorește și astfel poate cauza congestie pe legătura sa, sau chiar în toată rețeaua. Această problemă este agravată de faptul că se folosește UDP pentru multicast, iar pentru unicast TCP, într-o situație de congestie fluxul TCP reducându-și rata, în timp ce fluxul UDP va ocupa toată capacitatea legăturii.

2.7. Transmisia multicast pentru noduri mobile

Dirijarea multicast

Unele dintre soluțiile oferite pentru transmiterea datelor multicast către nodurile mobile folosesc tunelarea IP. Acest lucru implică mai multe operații de încapsulare/decapsulare, operații care suprasolicită resursele de procesare și de memorie ale ruterului. De asemenea aceste încapsulări cresc dimensiunea pachetului multicast rezultând astfel o creștere a debitului utilizat.

Drijarea pachetelor multicast pentru receptorii mobili implică modificări frecvente ale arborelui de distribuție. Costul asociat reconstrucției arborelui este important deoarece implică transmiterea de informație de dirijare suplimentară. întreținerea arborelui se realizează folosind două abordări diferite. Ramurile arborelui sunt șterse dacă nu sunt reînnoite după o anumită perioadă de timp, sau ele sunt șterse doar la primirea unor mesaje explicite de la membri grupului multicast.

Folosirea protocoalelor de dirijare care creează arbori de distribuție partajați, PIM-SM și CBT (Core Based Trees), implică alegerea atentă a locației ruterului RP. Modificarea frecventă a topologiei rețelei poate duce la situații în care locația ruterului RP nu este optimă, iar în consecință rutele vor fi suboptimale.

Receptori multicast mobili

Un receptor mobil va experimenta întârzieri adiționale la recepția pachetelor multicast datorită proceduri de relocalizare, protocoalelor de management a grupului multicast, recalcularea arborelui multicast, și întârzierea de propagare. Receptorul mobil este văzut ca un nou receptor în rețeaua vizitată, el trebuind să se reînscrie la grup.

Pe perioada relocalizării dintr-o rețea LP în alta, nodul mobil trebuie să recepționeze pachete multicast în mod continuu, totuși relocalizarea nu poate fi prevăzută și nu există mecanisme pentru retransmiterea traficului multicast adresat nodului mobil în standard. Pachetele multicast sunt livrate în continuare în rețeaua vizitată chiar și după ce nodul mobil s-a mutat, existând riscul pierderii secvențialității pachetelor. Un fenomen ce poate apărea este duplicarea pachetelor multicast, situație în care un receptor mobil primește aceeași informație de la stația de bază și de la un ruter multicast. Înainte de a părăsi rețeaua vizitată se poate ca nodul mobil să nu aibă timp pentru a părăsi grupul multicast la care a fost înscris, situație în care datele multicast vor fi livrate într-o rețea fără receptori.

Surse multicast mobile

Transparența este o problemă majoră pentru sursele multicast mobile. La trecerea unei surse active într-o rețea vizitată, ea primește o nouă adresă, care va fi folosită drept adresă sursă pentru pachetele multicast. Noul ruter multicast la care este conectată sursa nu poate transmite pachetele multicast care au drept adresă sursă repectiva adresă, dacă receptori multicast nu solicită traficul în mod explicit. De asemenea datorită modificării adresei receptorii multicast nu pot interpreta traficul multicast recepționat. Dacă transparența relocalizării nu se realizează, receptorii multicast împreună cu ruterele multicast vor fi induși în eroare. În acest caz trebuie realizată notificarea relocalizării, pentru ca receptorii să fie informați de modificarea adresei IP a sursei, folosind protocolul MSNIP (Multicast Source Notification of Interest Protocol). După ce are loc relocalizarea sursa multicast nu poate folosi drept adresă sursă adresa din rețeaua de reședință, deoarece mecanismul de verificare RPF va eșua, acest mecanism comparând adresa sursă a pachetului multicast recepționat cu rutele de pe interfața pe care acel pachet a fost primit.

Soluții propuse

Două concepte au fost propuse pentru a soluționa problemele transmisie multicast pentru nodurile mobile. Prima metodă propune folosirea de tunele bidirecționale între agentul din rețeaua de reședință (Home Agent) și nodul mobil, prin care traficul multicast să fie directat. Cea de-a doua idee propune ca nodul mobil să se înscrie la grupul multicast din rețeaua vizitată.

Folosirea tunelării bidirecționale implică ca nodul mobil să se înscrie la grupul multicast prin rețeaua de reședință, folosind agentul din rețeaua de reședință HA. Nodul mobil tunelează mesajele de control a aparteneței la grup (IGMP/MLD) către HA, iar acest agent tunelează pachetele multicast către nodul mobil. Această abordare impune ca HA să fie ruter multicast între nodul mobil și ruterul multicast din rețeaua de reședință. O sursă mobilă multicast va trimite pachetele multicast prin tunelul bidirecțional către rețeaua de reședință, folosind drept adresă sursă adresa din rețeaua de reședință, indiferent de locația curentă.

Principalul avantaj al folosirii tunelării bidirecționale este că nu necesită reconstruirea arborelui de distribuție în timp ce nodul mobil, fie că este receptor sau sursă, își modifică locația. Acest mecanism asigură transparența mobilității nodului față de arborele de distribuție. Totuși această abordare introduce o dirijare neoptimă a traficului multicast datorită transmiterii pachetelor prin HA. Folosirea tunelării duce și la o utilizare sporită a resurselor, astfel HA va multiplica pachetele multicast pentru fiecare receptor mobil din același grup multicast, fenomen numit avalanșă multicast. Această problemă poate avea efecte și mai grave dacă o mare parte a receptorilor multicast mobili, se găsesc în aceeași rețea vizitată.

Înscrierea de la distanță presupune ca nodul mobil să se înscrie la grupul multicast folosind ruterul multicast din rețeaua vizitată [13]. Astfel nodul mobil se comportă ca oricare altă stație din rețeaua vizitată, și va trimite mesaje IGMP/MLD către ruterul local. Acest mecanism permite dirijarea optimală deoarece arborele multicast este reconstruit pentru locația curentă a nodului mobil. Consumul de resurse din rețea este de asemenea minimizat, deoarece nodurile mobile din aceeași rețea vizitată și care fac parte din același grup multicast, nu mai necesită multiplicarea pachetelor.

O posibilă rezolvare sugerează combinarea tunelării bidirecționale cu înscrierea de la distanță pentru a beneficia de avantajele celor două abordări. Traficul multicast va fi livrat nodului mobil prin tunel până când se termină procesul de înscriere, moment în care nodul mobil trebuie să anunțe HA să înceteze tunelarea traficului multicast către nodul mobil. Dezavantajul acestei metode este că folosesc ineficient resursele rețelei, deoarece trebuie menținute două ramuri în arborele de distribuție multicast pentru aceeași stație.

Capitolul .3. APLICAREA ALGORITMILOR DE DIRIJARE DIJIKSTRA

SI BELLMANN – FORD

3.1. APLICATIA DE DESENARE A GRAFULUI

Aplicația a fost concepută în C# ca un program demonstrativ care implementează și verifică rezultatele pas cu pas pentru cei mai importanți algoritmi din teoria grafurilor: Dijkstra și Bellman Ford. Datele de intrare sunt dinamice și se poate modifica calea spre fișierul de intrare, de unde se citesc datele. Se poate vizualiza graful, aplicația dispunând de un modul care ajută utilizatorul în alegerea unei dispersii grafice cât mai corectă. De asemenea, aplicația dispune de o serie de facilități pentru a studia algoritmii Dijkstra și Bellman Ford.

Figura 3.1 Formularul Gprint

Aplicația pornește cu formularul (sau fereastra) principal “Gprint”, în care se pot identifica mai multe module. În partea de sus a aplicației se poate introduce fișierul de intrare, care trebuie să conțină pe prima linie numărul n de noduri ale grafului, iar pe celelalte n linii, elementele matricii de costuri asociate acestuia.

Dacă drumul spre fișier este greșit sau forma fișierului nu este recunoscută, va apărea o casetă cu mesaj de eroare (figura 3.2). În momentul când o matrice este încărcată, se poate vizualiza atât matricea costurilor (figura 3.3) asociate muchiilor dintre noduri (matrice citită din fișier), apelând metoda Click pe butonul cu eticheta “A” din stânga-sus, cât și matricea ponderilor (figura 3.4), prin activarea butonului cu eticheta “C”.

Figura 3.2. Casetă cu mesaj de eroare

Figura 3.3. Activarea formularului Form2, care conține matricea costurilor

Figura 3.4 Activarea formularului Form2, care conține matricea ponderilor

Numai în cazul în care calea spre fișier este corectă se poate desena graful în panelul gri, apelând metoda Click pe butonul “Draw” (figura 3.5). Această fază este obligatorie. În această figură apare în mod aleator o soluție de desenare a grafului, care nu respectă nici o regulă de distanță (în această fază o muchie care are costul 1 poate fi desenată de lungime mai mare decât o muchie de cost mai mare). În partea dreaptă sus apar într-un “panel” de culoare albastră butoanele necesare pentru obținerea unei dispersii grafice cât mai bună.

Modul de a genera o soluție grafică cât mai apropiată de cea ideală este următoarea (figura 4.6):

•Se generează aleator o posibilă soluție (o soluție înseamnă un vector de dimensiune 2n de forma : S (Nod1x, Nod1y, Nod2x,…, Nodnx, Nodny), unde n este numărul de noduri ale grafului, citit din fișierul de intrare, iar (Noda, Noday) reprezintă coordonatele punctului a în panelul gri.

•Construim o funcție (de adecvare) care generează aleator o populație de N soluții posibile și determină generic dacă o soluție este mai bună decât alta.

•Pe baza fucției de adecvare se alege cea mai bună soluție din cele N.

Figura 3.5 Generarea unei soluții aleatoare de desenare a grafului

Figura 3.6 Generarea unei soluții de desenare a grafului cât mai bună

Dacă are loc un eveniment Win care șterge o porțiune din panelul gri, afectând afișarea grafului, se poate apela butonul din stânga sus cu eticheta “R” pentru redesenare.

Figura 3.7 Activarea butonului Dijkstra

Odată ce se alege o dispersie convenabilă, se pot apela funcțiile principale ale aplicației, “Algoritmul Dijkstra” și “Algoritmul Bellman-Ford”. Cei doi algoritmi sunt accesibili prin cele două butoane etichetate cu numele algoritmilor. În figura anterioară este selectat butonul “Dijkstra”, a fost introdus nodul de start al algoritmului și aplicația așteaptă apăsarea butonului “Accept”, pentru a putea trece la calcularea distanțelor și drumurilor minime de la nodul curent până la toate celelalte noduri ale grafului, folosind algoritmul lui Dijkstra. Se poate schimba nodul de start prin scrierea unei alte valori în căsuța de text din dreapta (figura 3.7).

Figura 3.8 Rezultatele obținute în urma rulării algoritmului Dijkstra

În jurul nodului de start se observă un marker roșu și se poate vizualiza drumul cel mai scurt către fiecare din celelalte noduri ale grafului (ce se schimbă în timp la fiecare 3 secunde), fiind marcat prin desenarea unor cercuri gri de-a lungul rutei (figura 3.8). În partea de jos a formularului principal există un obiect de tip listBox, care conține toate datele rezultate în timpul rulării algoritmului. Rularea algoritmului se încheie prin apelul Click pe butonul etichetat “Stop”. În cazul în care se dorește o nouă sesiune de lucru, se poate apela metoda de curățare a conținutului listBox – ului prin Click pe butonul etichetat “C”.

Dacă se activează butonul View, în formularul Full view se pot observa datele complete de ieșire ale algorimului: atât vectorii D, S și T, calculați pe parcursul rulării algoritmului, cât și drumurile minime rezultate de la nodul sursă (1 în exemplul prezentat) la toate celelalte noduri (figura 3.9).

Figura 3.9 Activarea formularului Full view pentru algoritmul Dijkstra

Odată închisă sesiunea “Dijkstra”, aceasta se poate reporni, sau se poate trece la rularea algoritmului Bellman Ford prin Click pe butonul “Bellman”(figura 3.10). În această figură se poate observa că fost deja introdus nodul destinație și a fost apăsat butonul “Accept”, pentru a se putea trece la calcularea distanțelor minime de la toate nodurile grafului pâna la cel ales ca destinatar (6 în exemplul prezentat), folosind algoritmul lui Bellman Ford. Se poate schimba nodul destinație prin scrierea unei alte valori în căsuța de text din dreapta (figura 3.10).

În formularul Full view se pot observa datele complete de ieșire ale algorimului: atât calculele realizate și distanțele intermediare obținute, cât și rezultatul final (figura 3.11).

Figura 3.10 Rezultatele obținute în urma rulării algoritmului Bellman Ford

Figura 3.11 Activarea formularului Full view pentru algoritmul Bellman Ford

3.2. PROGRAMAREA APLICATIEI

O aplicație este vizuală dacă dispune de o interfață grafică sugestivă și pune la dispoziția utilizatorului instrumente specifice de utilizare. Interfața (nivelul de prezentare) se ocupă numai de afișarea informațiilor către utilizator și de captarea celor introduse de acesta. Mediul de dezvoltare Microsoft Visual C# dispune de instrumente specializate de proiectare, ceea ce permite crearea aplicațiilor în mod interactiv, rapid și ușor.

Pentru a construi o aplicație Windows (File->New Project), se selecteazã ca template Windows Application. O aplicație Windows conține cel puțin o fereastră sau un formular (Form) în care se poate crea o interfață cu utilizatorul aplicației. Form1.cs este formularul creat implicit de Visual Studio.NET ca parte a proiectului.

La crearea unei noi aplicații vizuale, Visual Studio.NET generează un spațiu de nume (namespace) ce conține clasa statică Program, cu metoda statică (), ce constituie punctul de intrare (de lansare) al aplicației.

static class Program

{

static void ()

{

………

Application.Run(new Form1());

}

}

Clasa Application este responsabilă cu administrarea unei aplicații Windows, punând la dispoziție proprietăți pentru a obține informații despre aplicație, metode de lucru cu aplicația și altele. Toate metodele și proprietățile clasei Application sunt statice. Metoda Run() invocată mai sus creează un formular implicit, aplicația răspunzând la mesajele utilizatorului până când formularul va fi închis.

Spațiul Forms ne oferă clase specializate pentru creare de :

•ferestre sau formulare (System.Windows.Forms.Form),

•elemente specifice (controale), cum ar fi butoanele (System.Windows.Forms.Button), casetele de text (System.Windows.Forms.TextBox).

Clasele derivate din Form moștenesc o serie de proprietăți care determină atributele vizuale ale ferestrei (stilul marginilor, culoare de fundal, etc.), metode care implementeazã anumite comportamente (Show, Hide, Focus etc.) și o serie de metode specifice (handlere) de tratare a evenimentelor (Load, Click, Textchanged etc.).

O fereastră poate fi activată cu form.ShowDialog(), aceasta permițând ca revenirea în fereastra din care a fost activat noul formular să se facă numai după ce noul formular a fost închis (spunem că formularul nou este deschis modal). Pentru a crea o casetă de mesaj, se apelează metoda MessageBox.Show(), care are ca argument un string.

Unitatea de bazã a unei interfețe Windows o reprezintă un control. Acesta poate fi „găzduit” de un container ce poate fi un formular sau un alt control. Un control este o instanță a unei clase derivate din System.Windows.Forms și este reponsabil cu desenarea unei părți din container. Visual Studio .NET vine cu o serie de controale standard, disponibile în Toolbox.

Prenzentăm în continuare principalele obiecte Windows folosite, precum și rolul utilizării lor.

Figura 3.12 Tipuri de controale utilizate

TextBox: este obiectul Windows prin care se pot introduce date de la tastatură de către utilizator.. Principala sa proprietate este proprietatea “Text” (partea vizibilă și este de tip string). Conversia string-ului în integer se face cu ajutorul clasei Parse, de exemplu:

int i = int.Parse (textBox1.Text);

Button: dispune de o serie de evenimente, dintre care aplicația folosește metoda principală, “Click”. Numele metodei button1_Click este alcătuit din numele controlului (button1), urmat de numele evenimentului (Click). Această metodă se execută de fiecare dată când se execută click cu “mouse”-ul pe butonul respectiv, deci se va executa o secvență de instrucțiuni in momentul activării butonului.

private void button1_Click(object sender, EventArgs e)

{ instructiuni; }

Label : este folosit pentru plasarea de text pe un formular. Este obiectul Windows care se folosește în mod direct ca și marcaj pentru diferite îndrumări, textul afișat fiind conținut în proprietatea Text:

labelX.Text = “Optimization” (va apărea scris textul “Optimization” în locația destinată labelX).

Panel: se poate folosi ca și Display pentru o clasă grafică (panel gri), respectiv ca și un container de către alte controale (panel albastru). Proprietăți și metode folosite:

Visible (false/true): care ascund panel sau se poate vizualiza împreună cu toate obiectele din el.

Graphics g = panelX.CreateGrafics () : metodă prin care obiectul g va desena doar în interiorul panelX

g.Clear(Color): prin care se șterge și se redesenează panelul cu o culoare dată ca și argument.

ProgressBar: Control folosit pentru a gestiona (vizibil) timpul alocat unei proceduri. Proiprietăți :

Minimum = valoarea de la care pornește;

Maximum = valoarea maximă la care poate ajunge;

Value = valoare între minim și max;

Exemplu:

progressBar1.Minimum = 1;

progressBar1.Value=0;

progressBar1.Maximum = 10000;

{

for (int i = 0 ;i < 9999 ; i++ )

progressBar1.Value = ++;

}

ListBox: este un container care introduce linii de text prin metoda:

listBoxX.Items.Add (string);

Metoda de curățare a listBox-ului este:

listBoxX.Items.Clear();

Timer: este un obiect Windows de control al executării, care are următoarele proprietăți și metode importante:

•Interval : care reprezintă numărul de milisecunde dintre apelurile la metoda de tratare a

evenimentului.

•Enabled = cu proprietatea (true/false)

•Metoda Tick(): se execută tot ce este scris în procedura Tick din interval în interval, atâta timp cât timer.Enabled = true, de exemplu:

private void button1_Click(object sender, EventArgs e)

{

instructiuni;

timer1.Enabled=true;

}

private void timer1_Tick(object sender, EventArgs e)

{ instructiuni; }

Se poate observa că, aducând din Toolbox controlul Timer, acesta nu se afișeazã pe formular, el apărând într-o zonă gri a suprafeței de lucru (Designer).

Printre proprietățile comune ale controalelor se numără:

•Enable=true/false: determină dacă un control este activ/inactiv într-un formular.

•Visible=true/false: setează vizibilitatea controlului/ascunde controlul.

Random: este clasa folosită de C# pentru a genera numere întregi aleatoare, iar metoda Random.Next() generează un număr întreg nenegativ aleator.

Random r = new Random();

X = r.Next ()%t;

În X vor fi valori între 0 și t-1.

Spațiul System.Drawing conține tipuri care permit realizarea unor desene 2D și au rol deosebit în proiectarea interfețelor grafice. Un obiect de tip Point este reprezentat prin coordonatele unui punct într-un spațiu bidimensional.

Exemplu: Point myPoint = new Point(1,2);

Point este utilizat frecvent nu numai pentru desene, ci și pentru a identifica în program un punct dintr-un anumit spațiu.

Structura Color conține date, tipuri și metode utile în lucrul cu culori. Fiind un tip valoare (struct) și nu o clasã, aceasta conține date și metode, însã nu permite instanțiere, moștenire.

Color myColor = Color.Brown;

button1.BackColor = myColor;

Clasa Graphics este o clasă sigilată, reprezentând o arie rectangulară care permite reprezentări grafice. De exemplu, o linie frântă se poate realiza astfel:

Point[] points = new Point[4];

points[0] = new Point(0, 0);points[1] = new Point(0, 120);

points[2] = new Point(20, 120);points[3] = new Point(20, 0);

Graphics g = this.CreateGraphics();

Pen pen = new Pen(Color.Yellow, 2);

g.DrawLines(pen, points);

Funcțiile de desenare ale acestei clase pe care le-am folosit în aplicație sunt:

Graphics g;

g.DrawEllipse (pen.culoare) ,int x, int y, int r1, int r2): desenează o elipsă de culoare pen.culoare, x și y fiind coordonatele punctului din colțul stânga-sus al dreptunghiului, iar r1 și r2 lățimea, respectiv înalțimea dreptunghiului.

g.FillElipse(solidbrush.culoare,int x, int y, int r1, int r2): are aceiași parametri, doar că elipsa este umplută.

g.DrawLine (pen,A,B): care desenează o muchie între punctele (A.x,A.y) și (B.x,B.y) de culoare pen.

g.DrawString (str,font,color,A): care desenează un string str cu caractere font, de culoare color, la punctul de coordonate (A.x, A.y).

3.3. Implementarea aplicației

Pentru implementarea aplicației am creat namespace-ul sau pachetul Grafs, care conține următoarele clase: Program, Form1, Form2 și Form3. Codul programului principal este generat de Project Win App și rulează un obiect de tip Form1. Cu ajutorul claselor Form1, Form 2 și Form3 se realizează interfața grafică a aplicației.

Pentru desenarea grafului în interiorul panelului 1 (panelul gri) al formularului principal al

aplicației, Gprint, am utilizat 3 funcții:

•Funcția d(Point A, Point B), care calculează și returnează distanța Euclidiană dintre 2 puncte A și B.

•Funcția initRND(), care generează aleator o posibilă soluție pentru desenare. Pentru toate nodurile se generează coordonatele X și Y în interiorul panelului 1.

•Funcția drawRND(), care desenează efectiv graful.

button4_Click() este procedura folosită pentru realizarea unei dispersii grafice a grafului cât mai apropiată de realitate. Aceasta generează o posibilă soluție pe care o presupune cea mai bună și pentru toate celelalte încercări (maxTry), generează posibile soluții pe care le compară cu precedent prin funcția errorNo(). Dacă găsește o soluție mai bună, o pastrează și merge mai departe. errorNo() este funcția de adecvare care pentru fiecare pereche de noduri (i,j) între care există muchie, calculează diferența la pătrat dintre dimensiunea ideală a muchiei (reprezentată de costul asociat muchiei înmulțit cu numărul de pixeli alocați pentru un cost unitar) și distanța Euclidiană dintre i și j calculată pentru soluția cel mai recent generată. errorNo() însumează aceste valori și returnează suma. Dintre toate soluțiile generate, soluția cea mai bună este aceea pentru care această sumă este minimă.

De asemenea, am utilizat controlul progressBar pentru a gestiona (vizibil) timpul alocat dispersării grafului.

3.4. Algoritmul lui Dijkstra

Algoritmul lui Dijkstra, utilizat pentru prima dată în anul 1959, oferă unul dintre cei mai eficienți algoritmi de calcul pentru rezolvarea problemei de cost minim. Acesta calculează căile de cost minim dintr-un nod sursă ns către toate celelalte noduri din rețea, bazându-se pe afirmația următoare: dacă nodul k este parte a drumului cel mai scurt între nodurile i și j, atunci drumul cel mai scurt între i și j trebuie să rezulte din calea cea mai scurtă între i și k urmată de calea cea mai scurtă între k și j.

Înseamnă că de fapt ar rezulta o formulă de optimizare de forma:

Fiecare nod este etichetat în paranteze cu distanța de la nodul sursă până la el (D[i]), de-a lungul celei mai bune căi cunoscute până în prezent (T[i]). Inițial, cum nu se cunoaște nici o cale, etichetele provizorii ale nodurilor au forma (∞,0), deoarece orice nod i se află deocamdată la o distanță infinit de mare față de sursă. Eticheta sursei ns, care este considerată permanentă (activă), este de forma (0,0) , deoarece un nod este totdeauna la distanță nulă față de el însuși.

Într-o primă etapă, se examinează fiecare nod vecin nodului sursă ns, reetichetând fiecare nod cu distanța spre ns. De fiecare dată când un nod este reetichetat, îl vom eticheta de asemenea și cu nodul de la care s-a făcut încercarea, pentru a putea reface calea ulterior. Algoritmul selectează nodurile grafului, unul câte unul, în ordinea crescătoare a costului drumului de la nodul ns la ele, într-o mulțime S, care inițial conține numai nodul ns.

În procesul de prelucrare, se folosesc 3 vectori: D, S și T.

Vectorul D este vectorul lungimii drumurilor de la nodul ns la toate vârfurile grafului. Prin D[i], unde i este un număr întreg între 1 și n (n fiind numărul de noduri ale grafului) se înțelege costul drumului găsit la un moment dat, între nodul ns și nodul i.

Vectorul T indică drumurile găsite între nodul ns și celelalte noduri ale grafului. Pentru aceasta se utilizează o memorare specială a drumurilor, numită legătură de tip „tată”, în care pentru nodul i se reține nodul anterior (vecinul lui i) în lungul celei mai scurte căi până în momentul de față, de la sursă la i.

Vectorul S, numit și vector caracteristic, indică mulțimea S a nodurilor permanente: S[i]=0 dacă nodul i nu este permanent și S[i]=1 dacă nodul i este permanent.

În fiecare pas de aplicare al algoritmului, nodul permanent este indicat de o săgeată, iar toate etichetele reactualizate ale nodurilor succesoare sunt marcate cu steluță (*). După prima reactualizare a etichetelor se va considera ca nod permanent succesorul sursei care deține o etichetă minimă (cel ce prezintă distanța cea mai mică până la sursă); cu siguranță că acest succesor se va afla pe drumul cel mai scurt. Acesta va fi nodul de referință în pasul următor, toate etichetele succesorilor lui putând să fie acum reactualizate. Aplicarea algoritmului se încheie atunci când au fost parcurse toate arcele rețelei, fără însă a fi necesar ca toate nodurile să fie pe rând considerate ca noduri active.

Arcele grafului, ce sunt considerate în procesul de stabilire a drumului minim sunt desenate cu linie îngroșată în figura 3.13. Ultima schemă, reactualizarea 6, nu aduce nici o modificare a etichetelor față de iterația anterioară, dar ea a fost necesară doar pentru a considera și ultimul arc (6-7) al grafului.

Figura 3.13 Exemplu de aplicare a algoritmului lui Dijkstra

În aplicația practică am construit metoda public void debug(), care realizează afișarea celor trei vectori D, S și T în listBox1, care se află în formularul principal al aplicației, numit Gprint.

Prin metoda button10_Click() am realizat implementarea algoritmului lui Dijkstra.

Atunci când se apelează funcțiile recursive drum() și drumd() care au ca argument un nod oarecare i al grafului, se verifică dacă pe ruta de la nodul sursă la nodul i există un nod anterior nodului i (T[i]!=0, T[i] fiind nodul anterior), iar dacă da, funcțiile se apelează recursiv, având de această dată ca argument chiar nodul precedent.

Am utilizat funcția drum() pentru afișarea drumului de la nodul sursă la toate celelalte noduri ale grafului în listBox1, iar funcția drumd() pentru evidențierea acestuia pe graf, prin marcarea nodurilor aflate de-a lungul rutei cu elipse de culoare gri.

Am utilizat metoda timer1_Tick(), pentru a marca pe graf, la fiecare 3 secunde, drumul de la nodul sursă la nodul curent. Toate instrucțiunile scrise în procedura timer1_Tick() se execută din interval în interval, atâta timp cât timer1.Enabled = true.

3.5. Algoritmul lui Bellman Ford

Algoritmul presupune căutarea celei mai scurte căi de la fiecare ruter al unei subrețele la un ruter destinație d. Se impune ca fiecărui nod i să i se asocieze o etichetă Ch(i), care reprezintă distanța celei mai scurte căi de la nodul i la nodul destinație, cale care nu conține mai mult de h arce.

Se construiește matricea pătratică M (matricea ponderilor) cu dimensiunea egală cu numărul de noduri ale grafului, n, ale cărei elemente sunt:

Figura 3.14 Exemplu de aplicare a algoritmului lui Bellman Ford

Figura 3.15 Matricea M după adăugarea liniilor Lh

La matricea M se adaugă succesiv liniile Lh, elementele acestora calculându-se prin relații de recurență (figura 3.15):

1.Pentru linia L1, C1(i) = did, i = 1,…,n (prima linie este coloana d, transpusă, a matricii M).

2. Pentru liniile Lh, h≠1,

Se consideră Ch(i)=0 pentru i=d.

Inițial, nici o cale nu este cunoscută, deci în mod convențional, etichetele provizorii ale tuturor nodurilor sunt ∞, mai puțin eticheta nodului destinație, aceasta fiind evident 0. Eticheta destinației este considerată validă și nu se va modifica ulterior (figura 3.14). Etichetele provizorii ale nodurilor se modifică iterativ pe măsură ce se derulează procedura de minimizare a drumului, ajungând evident la o formă finală, după un număr de pași de rulare a algoritmului. La fiecare pas de rulare a algoritmului se completează matricea cu câte o linie, distanțele recalculându-se pentru fiecare nod al grafului, cu excepția nodului d. Algoritmul presupune considerarea tuturor succesorilor fiecărui nod și reactualizarea etichetelor provizorii ale acestor noduri, în raport cu lungimile arcelor de acces spre ele.

Reactualizarea etichetelor se “judecă” pe baza comparației dintre vechile distanțe Ch-1(i) ale nodurilor și noile distanțe Ch(i) , ce sunt calculate pe trasee care includ nodurile predecesoare și care dețin valori valide în etichetele lor (aceste valori valide sunt etichetele de la pasul anterior). Un nod este valid atunci când are eticheta asociată diferită de ∞. Distanța de la nodul curent i până la d va fi modificată numai dacă Ch(i) < Ch-1(i) cu i≠d, deci se va menține tot timpul calea cea mai bună. În acest caz, se elimină orice conexiune a lui i formată într-o iterație anterioară cu un nod predecesor. Altfel, se păstrează eticheta de la pasul anterior.

Algoritmul se termină după h iterații dacă Ch(i) = Ch-1(i) pentru oricare i, adică atunci când nu mai au loc modificări ale etichetelor de la iterația anterioară.

În figura 3.14 sunt precizate cele 5 reactualizări ale etichetelor nodurilor raportate la nodul 6 considerat ca destinație; la prima reactualizare sunt modificate etichetele celor 3 vecini ai acesteia: nodurile 7, 3 și 5, deoarece deocamdată numărul maxim de arce pe care îl poate avea o legătură este 1. De fiecare dată se marchează cu steluță (*) etichetele modificate și se desenează cu linie îngroșată arcele participante la drumurile minime stabilite până în acel moment. Fiecare reactualizare se execută luându-se în considerare doar căile de la nodurile considerate valide la pasul anterior până la destinație. Dacă distanța de la un nod oarecare până la destinație, considerând un nod valid ca predecesor este mai mică decât la pasul anterior, atunci eticheta lui se modifică; în caz contrar sau de egalitate, se menține eticheta anterioară. În exemplul prezentat, la cea de-a doua reactualizare, se iau în considerare căile 7-6, 3-6 și 5-1. De la nodul 2 se poate ajunge la destinație pe o cale care conține maxim 2 arce prin nodurile 7 și 3, considerate valide la pasul precedent. Se compară cele 2 distanțe, 4+3 și 5+1 și se ajunge la concluzia că cea mai bună cale de la 2 la 6 este prin 3. În acest moment, nodul 3 devine valid și i se asociază eticheta 6. La fel se procedează și cu celelalte noduri vecine nodurilor valide de la pasul anterior, nodul 7 fiind reetichetat cu valoarea 3 (7-3-6), iar nodul 4 primind eticheta 3 (4-3-6). În continuare se caută căi minime având un număr de maxim 3 arce.

Pentru implementarea algoritmului lui Bellman Ford, am realizat trei funcții:

•button7_click();

•Calc(int poz, int d), care recalculează distanța minimă de la fiecare nod diferit de d până la destinație; această funcție mai are în plus afișarea elementelor pe care le calculează;

•idc(), care compară ultimele 2 soluții parțiale ale algoritmului Bellman și returnează false dacă sunt diferite, respectiv true dacă sunt egale.

Pentru afișarea în listBox2 a distanțelor intermediare ale algoritmului de la fiecare nod al grafului până la destinație, am realizat funcția debug2(). Funcția debug2Complette() afișează în listBox2 soluția finală, deci distanțele cele mai mici de la fiecare nod al grafului până la nodul destinație d.

4. Concluzii

Problema găsirii celor mai scurte rute joacă un rol central în modelarea și analiza rețelelor. Majoritatea problemelor de dirijare pot fi rezolvate ca probleme de găsire a celei mai scurte căi, odată ce o “lungime” a fost asociată cu fiecare arc din rețea. Proiectarea algoritmilor în acest scop duce la crearea unor rețele care satisfac criteriul de lungime a căii.

În aplicația practică asociată acestei lucrări s-a propus un model de interpretare și studiere a principalilor algoritmi de determinare a drumurilor de cost minim din teoria grafurilor, Bellman Ford și Dijkstra, aducându-se un plus de complexitate prin posibilitatea studierii pas cu pas a fiecărei acțiuni determinate de aceștia. Aplicația, pe lângă conținutul metodic relativ la elementele de teoria grafurilor, este și un model demonstrativ de folosire a metodelor aleatoare de reprezentare grafică, a modului de construire și implementare a acestora.

Concluzia care se desprinde este aceea că prin aplicarea algoritmului Dijkstra există șansa ca, pentru grafuri mari și dense, să se obțină drumul minim mai rapid decât prin folosirea algoritmului Bellman Ford.

Informațiile prezentate în această lucrare oferă posibilitatea unei dezvoltări ulterioare a aplicației “Grafs”.

În această aplicație ar fi util să se realizeze citirea unor fișiere text care au incluse alte date de intrare, de exemplu pentru fiecare nod mulțimea nodurilor cu care formează arce, în care el este pe prima poziție, dar și reprezentarea grafică prin corespondență, listarea numărului de arce.

Un plus ar putea fi adus dacă aplicația ar calcula drumurile minime și pentru grafuri orientate.

S-ar putea realiza detectarea de către aplicație a conceptelor de bază din teoria grafurilor, cum ar fi: gradul unui nod, drumul elementar, ciclurile hamiltoniene, recunoașterea unui graf tare conex, a unui graf simplu conex și interfața vizuală asociată acestor opțiuni.

La nivel de programare, se pot încerca metode prin care aplicația să realizeze reprezentarea arborilor minimi de acoperire, pentru găsirea acestora putându-se implementa algoritmul lui Kruskal, algoritmul lui Prim sau algoritmul Greedy.

De asemenea, se pot căuta unele metode mai eficiente de desenare și dispersie grafică a nodurilor unui graf (să se țină cont de un număr minim de muchii intersectate), iar dacă s-a găsit o configurație grafică acceptabilă, aceasta să se poată salva pentru graful în cauză.

B I B L I O G R A F I E

[1] Stallings, William, (2007), Data and Computer Communications, 5th edition, Prentice-Hall International, 1997

[2] Gallager, Robert, Bertsekas, Dimitri, Data networks, 2th edition, Prentice-Hall, 1992

[3] Tanenbaum, A.S., Rețele de calculatoare, ediția a treia, Computer Press Agora, 1997

[4] Isar, Alexandru., Protocoale de comunicații-curs, Timișoara, 2004

[5] Naforniță, Miranda, Arhitectura rețelelor de calculatoare, Editura Politehnică, 2008

[6] Munteanu, Adrian, Rețele locale de calculatoare – Proiectare și administrare, Editura Polirom, 2003

[7] Kurose, James, Ross, Keith, Computer Networking

[8] Network Protocols, 2th edition, Javvin Technologies, 2004

[9] Sharp, Robin, Principles of Protocol Design, Springer, 2008

[10] IP routing fundamentals, Cisco Systems Inc.

[11] Deering, S, Host extensions for IP multicasting, RFC1112, 1989

[12] Fenner, William, Internet Group Management Protocol, RFC 2236, 1997

[13] Vida, R., “Multicast Listener Discovery Version 2 (MLDv2) for IPv6,” Internet Draft, updates RFC 2710, draftvida-mld-v2-08.txt, Dec. 2004

[14] Waitzman, D., Distance Vector Multicast Routing, RFC 1075, 1988

[15] J. Moy, “Multicast Extensions to OSPF,” Internet RFC 1584, Mar. 1994

[16] Estrin, D., Protocol Independent Multicast, Internet-Draft, 1996

[17] Ballardie, A.J., Core-based-trees, ACM SIGcomm, 1993

[18] http://www.hds.utc.fr/~hbettaha/papers/imed_IEEE_Com_Surveys_and_Tutorials2004.pdf

[19] Hinden, R., IP Version 6 Addressing Architecture, RFC 1884, 1995

[20] Liefooghe, P., “An Architecture for Seamless Access to Multicast Content,” 25th Annual IEEE Conf. Local Comp. Net. (LCN’00), 2000.

ANEXĂ

B I B L I O G R A F I E

[1] Stallings, William, (2007), Data and Computer Communications, 5th edition, Prentice-Hall International, 1997

[2] Gallager, Robert, Bertsekas, Dimitri, Data networks, 2th edition, Prentice-Hall, 1992

[3] Tanenbaum, A.S., Rețele de calculatoare, ediția a treia, Computer Press Agora, 1997

[4] Isar, Alexandru., Protocoale de comunicații-curs, Timișoara, 2004

[5] Naforniță, Miranda, Arhitectura rețelelor de calculatoare, Editura Politehnică, 2008

[6] Munteanu, Adrian, Rețele locale de calculatoare – Proiectare și administrare, Editura Polirom, 2003

[7] Kurose, James, Ross, Keith, Computer Networking

[8] Network Protocols, 2th edition, Javvin Technologies, 2004

[9] Sharp, Robin, Principles of Protocol Design, Springer, 2008

[10] IP routing fundamentals, Cisco Systems Inc.

[11] Deering, S, Host extensions for IP multicasting, RFC1112, 1989

[12] Fenner, William, Internet Group Management Protocol, RFC 2236, 1997

[13] Vida, R., “Multicast Listener Discovery Version 2 (MLDv2) for IPv6,” Internet Draft, updates RFC 2710, draftvida-mld-v2-08.txt, Dec. 2004

[14] Waitzman, D., Distance Vector Multicast Routing, RFC 1075, 1988

[15] J. Moy, “Multicast Extensions to OSPF,” Internet RFC 1584, Mar. 1994

[16] Estrin, D., Protocol Independent Multicast, Internet-Draft, 1996

[17] Ballardie, A.J., Core-based-trees, ACM SIGcomm, 1993

[18] http://www.hds.utc.fr/~hbettaha/papers/imed_IEEE_Com_Surveys_and_Tutorials2004.pdf

[19] Hinden, R., IP Version 6 Addressing Architecture, RFC 1884, 1995

[20] Liefooghe, P., “An Architecture for Seamless Access to Multicast Content,” 25th Annual IEEE Conf. Local Comp. Net. (LCN’00), 2000.