Pagina documente » Informatica, Matematica » Arborii si algoritmi folositi in protocoalele de rutare

Despre lucrare

lucrare-licenta-arborii-si-algoritmi-folositi-in-protocoalele-de-rutare
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-arborii-si-algoritmi-folositi-in-protocoalele-de-rutare


Cuprins

CUPRINS
Capitolul I - Introducere..........
1
Capitolul II - Modelul multicast
4
2.1 Istoria arborilor...........
7
2.2 Calcularea rutei multicast
8
2.3 Concepte si tehnologia DVMRP......
8
2.3.1 Conexiunile vecine
9
2.3.2 Anuntarea rutei sursei............
10
2.4 Cum alege DVMRP rutele.............
11
2.5 Tabelul de rutare si cel de expedieri..
11
2.6 Arborii calea cea mai scurta........
12
2.7 Folosirea protocolului DVMRP.......
13
2.7.1 Modurile DVMRP.
13
2.7.2 Rularea DVMRP peste MOSPF
14
Capitolul III - Descrierea algoritmilor folositi in protocoalele de rutare..........
15
3.1 Adresele multicast........
16
3.2 Internet Group Management Protocol (IGMP).....
18
3.3 Grupuri multicast.........
19
3.4 Protocolul numarului de membri ai unui grup......
20
3.5 Internet Group Management Protocol (IGMP) - versiunea a doua............
20
3.6 Multicast Forwarding Algorithms.....
22
3.7 Descrierea algoritmilor..
23
3.7.1 Flooding............
23
3.7.2 Spanning tree......
23
3.7.3 Reverse Path Broadcasting (RPB)............
24
3.7.4 Reverse Path Multicasting (RPM)............
27
3.7.5 Core-Based Trees (CBT)........
29
Capitolul IV - Descrierea protocolului DVMRP..........
32
4.1 Interfete tunel si fizice...
32
4.2 Operatii de baza..........
33
4.3 Functiile ruterului DVMRP............
34
4.4 Tabelul de rutare DVMRP.............
35
4.5 Tabelul de expediere DVMRP.........
36
4.6 Ierarhia DVMRP.........
37
4.6.1 Avantaje ale rutarii ierarhice multicast.......
37
4.6.2 Protocolul ierarhic DVMRP.....
38
4.7 Abordarea rutarii IP multicast.........
39
4.8 Rutarea DVMRP.........
40
4.9 Tunelarea ca strategie de tranzitie pentru rutarea IP multicast..
43
4.10 Concluzii..
43
Capitolul V - Implementarea protocolului DVMRP......
44
5.1 Descoperirea vecinilor...
44
5.2 Localizarea sursei .........
44
5.3 Rutele inferioare dependente............
45
5.4 Expedierea indicata.......
46
5.5 Constructia arborilor multicast........
46
5.6 Curatarea arborilor multicast............
47
5.7 Grefarea arborilor multicast............
48
5.9 Masajele proba............
49
5.9.1 Capabilitatile ruterului...........
50
5.9.2 Identificarea generatiei...........
53
5.9.3 Adresele vecinilor.
53
5.9.4 Expirarea vecinului
54
5.9.5 Formatul pachetului proba......
54
5.9.6 Selectarea chestionarului desemnat de IGMP............
55
5.10 Expedierea multicast...
55
5.10.1 Expeditorul desemnat...........
56
5.10.2 Determinarea interfetei superioare...........
56
5.10.3 Determinarea listei interfetei inferioare.....
56
5.11 Schimbarea rutei.........
57
5.11.1 Agrearea (acceptarea) retelei sursa..........
57
5.11.2 Ordonarea si impachetarea rutei..............
58
5.11.3 Metrica rutei......
59
5.11.4 Dependentele rutei..............
59
5.11.5 Trimiterea raporturilor de ruta
60
5.11.6 Primirea raporturilor rutei......
60
5.11.7 Expirarea rutei....
63
5.12 Curatarea .
63
5.12.1 Retele foaie........
63
5.12.2 Retele sursa.......
64
5.12.3 Receptionarea unei curatari....
64
5.12.4 Trimiterea unei curatari.........
65
5.12.5 Retransmiterea unei curatari...
65
5.12.6 Formatul pachetului de curatare..............
66
5.13 Grefarea (alipirea)......
67
5.13.1 Trimiterea unei grefe............
68
5.13.2 Receptionarea unei grefe.......
68
5.13.3 Formatul pachetului grefa .....
69
5.13.4 Trimiterea unei instiintari a grefei...........
69
5.13.5 Receptia Graft Acknowledgement.........
69
5.13.6 Formatul Graft Acknowledgement........
70
5.14 Interfete...
70
5.15 Tranzitiile interfetei....
71
Glosar


EXTRAS DIN DOCUMENT

?Capitolul I

Introducere

DVMRP a fost sursa tuturor rutarilor multicast initiale (backbone sau Mbone). Cum tehnologia a evoluat, rolul sau a fost redus in multe locuri, dar ramane inca la baza tuturor rutarilor Mbone. În continuare vom vedea unul dintre cele mai folosite protocoale de rutare si anume, protocolul de rutare multicast distanta-vector (DVMRP). În realitate, DVMRP este un pic mai mult decat un simplu protocol de rutare. Pentru furnizarea suportului necesar, protocolul este alcatuit din doua parti principale: un protocol de informare si o strategie pentru expedierile actuale ale transmisiilor multicast. Ca protocol al rutarii informatiei, DVMRP este derivat din mult acceptatul RIP, cu modificarile pentru suportarea distributiei traficului multicast. Au existat doi algoritmi principali folositi pentru mecanismele de furnizare. Originalul DVMRP foloseste algoritmul TRPB. Mai recent, a fost introdus un algoritm numit RPB (Reverse Path Broadcasting).

DVMRP a fost sursa rutarii Mbone initiale. Odata cu avansul tehnologic, rolul sau a fost micsorat in multe locuri, dar ramane inca la baza tuturor rutarilor Mbone. Face parte dintr-o clasa a algoritmilor de rutare numiti “dense mode”. În aceasta clasa de algoritmi rutele sunt definite in asa maniera incat participarea multicast este grupata intr-o zona particulara a retelei.

Similaritatile dintre DVMRP si RIP constau in principal in modul in care cele doua protocoale identifica rutele. Amandoua se bazeaza pe mecanismul vector distanta in care fiecare ruter acumuleaza si expediaza metrica distantelor unor locatii destinatie. Principala distinctie intre cele doua protocoale este aceea ca in timp ce RIP este folosit in masurarea si identificarea rutelor spre adresele destinatie, DVMRP este preocupat in principal cu identificarea rutelor spre sursa transmisiilor multicast. Identificarea acestei informatii doteaza ruterele cu abilitatea de determinare a cailor cautate de expediere care vor fi folosite pentru expedierea traficului multicast.

În timp ce protocolul de informare este cheia numelui protocolului, mecanismele expedierii traficului sunt integrale ale retelelor bazate pe DVMRP. Cum traficul multicast este primit de rutere in retea, el este expediat prin unul dintre cei doi algoritmi generali, depinzand de versiunea particulara a protocolului care a fost implementat. Multicast (punct-la-multipunct) este un model de comunicatie in care o sursa gazda trimite un mesaj spre un grup de gazde destinatie. Desi aceasta poate fi realizata si prin trimiterea unor diferite mesaje unicast (punct-la-punct) spre fiecare dintre gazdele destinatie, exista mai multe motive care fac sa se doreasca capabilitatea multicast. Primul avantaj major in folosirea multicast este reducerea incarcarii retelei. Sunt multe aplicatii care cer trimiterea pachetelor spre sute de statii. Pachetele trimise acestor statii impart un grup de linii pe caile lor spre destinatii. Din moment ce multicast cere transmiterea unui singur pachet de la sursa si replicarile acestui pachet numai daca este necesar, transmisia multicast poate conserva atat de mult dorita banda a retelei. Alt loc unde transmisia multicast poate fi de un mare folos este in “descoperirea resursei”. Sunt multe aplicatii in care o gazda are nevoie sa afle daca un anumit tip de serviciu este disponibil sau nu. Protocoalele Internet, cum ar fi Bootstrap Protocol (BOOTP) si Open Shortest Path First (OSPF), sunt printre aceste aplicatii. Folosirea mesajelor multicast si trimiterea intrebarilor spre aceste gazde sunt potential capabile sa furnizeze acest serviciu care ar fi de un mare ajutor. Desi unele aplicatii folosesc mesajele multicast in transmiterea unui pachet spre un grup de gazde aflate pe aceeasi retea, nu exista nici un motiv pentru impunerea acestei limitari. Pentru descoperirea serverului domeniu-nume local este necesar ca mesajele multicast sa fie expediate pe retele straine daca exista mai putin de un server pe retea. Scopul pachetelor multicast poate fi limitat prin folosirea campului TTL al acestor pachete. O alta trasatura importanta pentru multicast este suportul ei pentru aplicatiile “datacasting”. În ultimii ani, transmisia multimedia a devenit din ce in ce mai populara. Semnalele audio si video sunt capturate, compresate si transmise unui grup de statii receptoare. În locul folosirii unui set de conexiuni punct-la-punct intre nodurile participante, multicast poate fi folosit pentru distribuirea datelor multimedia receptoarelor. In realitate, statiile din lume pot sa se alature sau sa paraseasca o distributie audio sau video in orice moment. Flexibilitatea in alaturarea si parasirea unui grup furnizata de multicast poate face mult mai usor de suportat variabilitatea membrilor.

Notiunea de grup este esentiala pentru conceptul multicast. Prin definitie, un mesaj multicast este trimis de la o sursa spre un grup de gazde destinatie. În distributia multipla IP, grupurile multicast au un ID numit identificatorul grupului multicast. Oricand un mesaj multicast este transmis in afara, un ID al grupului multicast specifica grupul destinatie. Aceste ID-uri sunt de fapt un set de adrese IP ce apartin clasei D de adrese. De aceea, daca o gazda vrea sa primeasca mesaje multicast trimise unui grup particular, trebuie sa asculte cumva toate mesajele trimise acelui grup particular.

Daca sursa si destinatia unui pachet multicast impart un “bus” comun, fiecare gazda trebuie sa cunoasca doar care grupuri au membrii in procesele acelei gazde. În orice caz, daca sursa si destinatia nu sunt pe acelasi LAN, expedierea mesajelor multicast spre destinatii devine mai complicata. Pentru a rezolva problema rutarii Internet-wide a mesajelor multicast, gazdele trebuie sa se alature unui grup prin informarea ruterului multicast de pe subreteaua lor. Internet Group Management Protocol (IGMP) este folosit in acest scop. Parasirea unui grup este facuta si prin IGMP. În acest fel ruterele multicast ale retelelor stiu membrii grupurilor multicast de pe reteaua lor si pot decide daca sa expedieze un mesaj multicast pe reteaua lor sau nu. În orice moment in care un ruter multicast primeste un pachet multicast, verifica ID-ul grupului mesajului si expediaza pachetul numai daca exista un membru al acelui grup in retelele conectate la el.

IGMP furnizeaza informatia ceruta in ultima parte a expedierii mesajului multicast destinatiilor sale. În orice caz, pentru furnizarea pachetului multicast de la sursa spre nodurile destinatie de pe alte retele, ruterele multicast trebuie sa schimbe informatiile pe care le-au adunat de la grupul membrilor gazdelor conectate direct la ele.

Exista mai multi algoritmi diferiti, cum ar fi: “flooding”, “spanning tree”, “reverse path broadcasting” si “reverse path multicasting”, pentru schimbul informatiei de rutare intre rutere. Unii dintre acesti algoritmi sunt folositi in protocoalele de rutare multicast dinamice, cum ar fi Distance-Vector Multicast Routing Protocol (DVMRP), Multicast extension to Open Shortest Path First (MOSPF) si Protocol Independent Multicast (PIM). Bazandu-se pe informatia de rutare obtinuta dintr-un asemenea protocol, oricand un pachet multicast este trimis in afara spre un grup multicast, ruterele multicast vor decide daca sa expedieze pachetul retelelor lor sau nu. În sfarsit, ruterele frunza vor vedea daca exista macar un membru al acelui grup particular pe retelele fizice atasate bazandu-se pe informatia IGMP si decid daca sa expedieze pachetul sau nu.

Capitolul II

Modelul multicast

Prima imbunatatire functionala importanta a Internet-ului, care a facut atractiva video-conferinta, a fost introducerea multicast. Pe scurt, multicast reprezinta abilitatea retelei de a eficientiza furnizarea informatiei mai multor recipiente. Cea mai buna analogie care se poate face este cu transmisia radio si TV. Spectrul electromagnetic este divizat in doua frecvente care sunt alocate, de anumite autoritati, statiilor TV si radio.

Figura 2.1: Modelul multicast Internet

Modelul de furnizare al pachetului multicast, aratat in figura 2.1, este similar cu broadcast, insa superior. Un computer gazda, capabil de multicast pe Internet, ruleaza o aplicatie in care primeste alaturari simple unicast ale unui set de receptoare de pe retea, identificate de o adresa a grupului.

Adresele grup sunt extensii ale schemei de adresare Internet, pentru a furniza adrese desemnate dinamic pentru un set de interfete cu un singur identificator. Efectele alaturarii unui computer gazda la un grup multicast sunt:

1. Gazda isi reprogrameaza interfata de retea pentru a primi pachetele adresate grupului aditional care a fost folosit pentru multicast

2. Gazda informeaza ruterele apropiate de faptul ca exista cel putin o destinatie pentru pachete al acelor adrese multicast.

Grupurile sunt deosebite prin adresele multicast separate pe care le au. Alocarea adresei multicast este dinamica in general si sub controlul colectiei utilizatorilor. Aceasta este in contrast cu frecventa alocata in spectrul electromagnetic, unde banda (in sensul numarului diferitelor frecvente posibile) este o resursa saraca in comparatie cu numarul adreselor multicast de pe Internet. In domeniul radio si TV, frecventele sunt alocate sub legile si tratatele nationale si globale. In Internet, exista unele mecanisme pentru managementul adreselor multicast. Este instructiv sa se compare natura programabila soft, dinamica, a grupurilor multicast cu mai multe modele de retele conectate telefonic.

Un computer gazda nu trebuie sa fie intr-un grup multicast pentru a fi capabil sa ii trimita. Oricine, oriunde, oricand, poate trimite un pachet oricarui grup. Gazdele pot lua parte la mai multe sesiuni multicast.

Daca un utilizator primeste audio de la mai multe surse trimitatoare aceleiasi sesiuni, utilizatorul doreste, probabil, sa le asculte. Daca primeste mai multe sesiuni video, va vrea sa se afiseze intrebari diferite unei capacitati a retelei si altor adrese. Din moment ce adresele internet sunt folosite pentru fiecare pachet, nu sunt circuite virtuale sau asociatii pe termen lung. Folosind multicast, un receptor poate prelua mai mult trafic decat daca s-ar alatura mai multor grupuri.

Ruterele din Internet care sunt capabile de multicast, folosesc locatia grupurilor sau a trimitatoarelor pentru a determina arborele furnizor care este folosit pentru a lua pachete de la sursa spre setul de receptoare. Acest arbore este, in mod uzual, chiar optim in termenii numarului de linii pe care le traverseaza pachetele. Pachetele nu sunt trimise de mai multe ori pe aceeasi linie in orice loc, ele sunt numai copiate in punctele cele mai apropiate.

Sa ne imaginam trimiterea unui memo spre un grup de persoane, dar avand numai de tiparit o copie la sursa. Atunci, cum soseste acest memo, oficiul de sortare il pune in copiator si il furnizeaza acelor recipiente, salvand un mare numar de copii de la trimitatorul original spre toate oficiile de sortare, dar la acelasi cost, in loc de copierea in lungul drumului. Acest model de furnizare a avut un mare efect pe drumul pe care programatorii aplicatiei au invatat sa construiasca programe multicast.

De exemplu, in telefonia audio, receptoarele trebuie sa fie ridicate din furca. Un apelant particular trebuie sa ii sune, pe fiecare la rand si sa adauge recipientele la un apel conferinta. Exista doua moduri in care oamenii au ajuns sa foloseasca conferintele multicast pe Internet:

1. Modelul TV broadcast, unde o intalnire sau un seminar pot fi vazute si auzite de oricine.

2. Stilul radio CB, unde utilizatorii discuta deschis si interactiv, venind din interiorul sau exteriorul unui loc de intalnire virtual.

Figura 2.2: Cresterea Mbone

Este instructiv sa ne gandim la modurile alternative in care comunicatia grup poate fi suportata pe intr-o retea. De exemplu, putem pune o lista a adreselor intr-un pachet de informatie pe care vrem sa il trimitem unei liste a recipientelor. Aceasta va functiona atata timp cat grupul a fost fixat si rezonabil de mic, dar care devine repede de necontrolat pentru grupuri intre 100 si 1000, pe care le-am gasit deja folosind Internetul. O alternativa poate fi de a accesa un server de distributie central unde sa trimitem totul. În loc de aceasta, Internet-ul distribuie multicast atat grupul de control cat si distributia datelor in retea. Ruterele expediaza pachetele cu destinatii multicast folosind adresa grupului sau adresa sursei, impreuna cu informatia nedistribuita, printr-un protocol de management al grupului, pentru a determina unde sa expedieze pachetele.

2.1 Istoria arborilor

Reteaua multicast are doua componente:

1. Tunelele – sunt folosite pentru a uni site-urile Internet care au rutere capabile de multicast, dar sunt separate de ruterele care nu suporta multicast, acestea formand o topologie virtuala la inceputul rutarii unicast Internet. S-a dovedit a fi nefolositoare aici, in termenii dezvoltarii unei noi versiuni a rutarii. Aceasta a dat un suport termenului Mbone, prescurtarea de la Multicast Backbone, care este numele unirii virtuale a ruterelor care interconecteaza insulele multicast via tunele , prin sectiunile incapabile de multicast ale Internetului.

2. Distance Vector Multicast Reverse Path routing – acesta este protocolul de rutare actual, care este o extensie naturala le vechiul Routing Information Protocol (RIP), folosind caile care sunt calculate pentru a lua de la un set de surse S spre o destinatie particulara, D pentru unicast, ca un mod de a lua multicast de la S spre D.

DVMRP foloseste o schema numita “curatare” pentru eliminarea ramurilor de la retea, care nu contin membrii ai unui grup cand o sursa incepe sa transmita. Cum Mbone a crescut (la inceputul anului 1995 avea 1500 de site-uri, unde un site putea fi un laborator de cercetare sau un Campus universitar, in 22 de tari), au existat multe grupuri care erau mici si imprastiate. Aceasta insemna ca volumul controlului de rutare, suprapusa peste traficul de curatare, au determinat oamenii sa regandeasca schema de rutare.

Au rezultat cateva alternative:

Oferta anului

Reducere 2020