CURS Solutii de Distributie Multicast

Tudor Mihai BLAGA – DOMOTICĂ: CLĂDIRI INTELIGENTE – Curs

Copyright © Tudor Mihai BLAGA 2010-2011, All rights reserved 1

5.2. Solu ţii de distribu ţie multicast pentru aplica ţii multimedia

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ţă sau aplicaţiile de descoperire a resurselor disponibile. Î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 [Deering 89].

Pentru a putea realiza transmisia multicast sunt necesare o serie de protocoale şi mecanisme 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 sa permită unei staţii să se înscrie sau să părăsească grupul multicast, numite protocoale de management a 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 şi deschise, î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 şi pe fiecare staţie pot exista mai multe aplicaţii care primesc pachete transmise la o adresa IP multicast.

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 ne trebuind să fie membră a acestuia. De asemenea, mai multe staţii pot să transmită simultan către acelaşi grup multicast.

O diferenţă importantă între transmisia unicast şi cea multicast este că aplicaţiile multicast pot folosi ca protocol de transport doar UDP, deoarece nu există o versiune pentru multicast a protocolului TCP. Semnificaţia acestui lucru este că la nivelul transport nu avem un serviciu de distribuţie fiabil.

5.2.1 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 (fig. 5.42). Cei 28 de biţi rămaşi constituie identificatorul grupului multicast [Deering 89].

1110 Identificator grup multicast 4 biţi 28 biţi Fig. 5.42 Formatul adresei multicast IPv4

Adresele multicast IPv6 au 128 de biţi şi sunt împărţite în patru câmpuri (fig. 5.43). 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 care conţine 4 bistabili de condiţie, doar semnificaţia celui mai puţin semnificativ bit fiind definită. Valoarea 0000 indică o adresă binecunoscută (permanentă), iar valoarea 0001 indică o adresă de tranziţie (temporară).

11111111 Flgs Scop Identificator grup multicast 8 biţi 4 biţi 4 biţi 112 biţi

Fig. 5.43 Formatul adresei multicast IPv6

Câmpul scop pe 4 biţi (tab. 5.6) 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ă [Dobrotă 03b]. Tab. 5.6 Semnificaţia valorilor definite pentru câmpul scop

Valoare în hexa Semnificaţie 1 Scop local la nivel de nod 2 Scop local la nivel de legătură 5 Scop local la nivel de site 8 Scop local la nivel de organizaţie E Scop global

Identificatorul grupului multicast este pe 112 biţi, mai multe grupuri putând avea acelaşi identificator dacă

diferă valoarea câmpului flgs sau a câmpului scop.



5.2.2 Managementul grupului multicast

O staţie care doreşte să recepţioneze traficul destinat unui grup multicast trebuie să fie membră a acelui grup. Aceasta poate să se înscrie sau să părăsească grupul 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): routerul poate întreba dacă există membri ai unor grupuri multicast pe acea

legătură, întrebări ce pot fi generice sau specifice unui grup. • raportare (Reporting): staţia poate informa routerul că aparţine unui anumit grup multicast.

Protocolul care realizează aceste funcţii pentru IPv4 este IGMP (Internet Group Management Protocol)

[Fenner 97], iar pentru IPv6 este MLD (Multicast Listener Discovery) [Vida 04]. 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.

5.2.3 Principiile rut ării multicast

Pentru a distribui datele multicast la toţi receptorii routerele 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 [Parkhurst 99].

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 Rendezvous 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ţ, routerele 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 rutare suplimentar poate suprasolicita reţeaua, iar tabelele de rutare multicast vor ocupa memoria routerelor. Arborii partajaţi au avantajul că necesită resurse minime în fiecare router, astfel necesarul de memorie pentru tabelele de rutare este mic. Dezavantajul arborilor partajaţi este că în anumite situaţii calea între sursă şi destinaţie poate fi suboptimală.

În rutarea unicast traficul este transmis prin reţea de la sursă la destinaţie, în funcţie de adresa destinaţie. Routerul caută în tabela de rutare 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. Routerul 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, routerul va multiplica pachetele si le va trimite pe interfeţele corespunzătoare. Putem spune că traficul multicast este transmis dinspre sursă, nu înspre receptori, acest mecanism numindu-se transmisie pe cale inversă RPF (Reverse Path Forwarding).

Mecanismul RPF permite routerului să transmită corect traficul multicast în jos pe arborele de distribuţie, acesta folosind tabela de rutare unicast existentă pentru a determina sensul spre sursă şi cel spre receptori. Un router 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 routerul primeşte un pachet multicast îi caută adresa sursă a pachetului în tabela de rutare 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).

5.2.4 DVMRP

DVMRP (Distance Vector Multicast Routing Protocol) este un protocol de rutare 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 hopuri cu un diametru limitat al reţelei [Rodriguez 01].

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 rutare, reţelele care doresc să primească trafic multicast pentru un anumit grup.

Funcţionarea DVMRP se realizează prin patru procese distincte [Rodriguez 01]: • descoperirea vecinilor • schimbul de rute • procesul Prune • procesul Graft

În momentul în care DVMRP este activat pe un router vor fi căutate routerele DVMRP învecinate. Scopul

descoperirii vecinilor este de a localiza alte routere DVMRP direct conectate, şi de a afla proprietăţile acestora. Procesul de schimbare a rutelor este similar cu cel al protocolului RIP, la început DVMRP anunţând numai reţelele direct conectate. Pe măsură ce sunt învăţate alte reţele rutele corespunzătoare sunt introduse în tabela locală de rutare DVMRP, fiind anunţate routerelor învecinate.

Celelalte două procese ale DVMRP, Prune şi Graft, sunt folosite pentru a realiza operaţiile de ataşare sau ştergere în mod dinamic a reţelelor care doresc să recepţioneze trafic multicast. Reţele sunt incluse în lista de distribuţie a traficului multicast cu ajutorul mesajelor de tip Graft, în timp ce cu ajutorul mesajelor de tip Prune reţelele sunt şterse din această listă.Mesajele DVMRP sunt transmise folosind protocolul IP cu valoarea doi în câmpul protocol (fig. 5.44), ceea ce identifică pachetele drept pachete IGMP.

Fig. 5.44 Încapsularea DVMRP în IP

Valoarea câmpului tip este 19, 0x13 în hexa, pentru a identifica pachetul IGMP drept un mesaj

DVMRP, iar câmpul cod diferenţiază diferitele tipuri de mesaje DVMRP (tab. 5.7).

Tab. 5.7 Tipul mesajelor DVMRP Cod Tip pachet 1 Probe 2 Route Report 5 Ask-Neighbors2 6 Neighbors2 7 Prune 8 Graft 9 Graft-ACK

5.2.5 MOSPF

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. În al doilea rând este mai scalabil în medii dense, în parte datorită algoritmului cu starea legăturii, dar şi datorită faptului că MOSPF foloseşte un mecanism de înscriere explicită [Doyle 01].



OSPF pentru multicast, adică 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). Câmpul opţiuni a fost extins să includă un bit, MC, care indică prezenţa suportului pentru multicast. Câmpul opţiuni se găseşte în mesajele Hello, în pachetele de descriere a bazelor de date şi în toate mesajele LSA. Rezultatul folosiri acestui bit este că routere OSPF şi MOSPF pot funcţiona în aceeaşi reţea. Routerele cu valori deferite ale bitului MC pot crea adiacenţe, totuşi doar vecinii a căror bit MC este setat pot schimba mesaje LSA de apartenenţă la grup, doar acestea putând fi folosite la calcularea rutelor. Ultima extensie a protocolului OSPF se referă la câmpul rtype din mesajele LSA Router ce include un bit W. Acest bit indică dacă routerul care a transmis mesajul este un router receptor wildcard. MOSPF foloseşte tot algoritmul lui Dijkstra pentru a construi arborii de distribuţie a pachetelor multicast de la sursă la receptori. Atât arborii unicast cât şi cei multicast sunt calculaţi folosind informaţiile din aceeaşi bază de date cu starea legăturii.

Operarea MOSPF implică alegerea unui router desemnat DR (Designated Router) şi a unui router desemnat de rezervă BDR (Backup DR). Toate routerele MOSPF trebuie să ruleze IGMP pe legătura locală pentru a descoperi receptori multicast, dar numai routerul DR poate trimite interogări IGMP. Se foloseşte un mecanism cu înscriere explicită, astfel când o staţie trimite un mesaj IGMP de înscriere la un grup, routerul MOSPF DR creează o înregistrare în baza de date locală cu grupuri (local group database). Această înregistrare conţine adresa grupului şi reţeaua ataşată care are receptori pentru acel grup (fig. 5.45). Dacă două staţii din reţele diferite sunt membre ale aceluiaşi grup, routerul trebuie să ştie numai grupul şi reţelele în care fiecare grup are membrii. El nu trebuie să ştie fiecare membrul al grupului.

Fig. 5.45 Baza de date locală de grupuri

Routerul DR transmite, în continuare, un mesaj LSA de apartenenţă la grup pentru fiecare grup ataşat.

Mesajul LSA specifică adresa grupului şi identificatorul routerului RID (Router ID), totodată listând toate reţelele ataşate care conţin membrii ai acelui grup. În unele situaţii routerul poate rula aplicaţii care sa îl facă membru al unui grup multicast, în acest caz mesajul LSA incluzând un câmp în care routerul specifică dacă el este membru al grupului. Mesajele LSA sunt apoi inundate în toată aria routerului. Mesajul LSA de apartenenţă la grup este similar cu mesajul LSA reţea, folosit în OSPF, din două puncte de vedere [Moy 94]:

• numai un router DR poate transmite mesaje LSA de apartenenţă la grup. • acest mesaj LSA are scop local în aria OSPF, nefiind distribuit dincolo de scopul ariei routerului care a

trimis mesajul. Motivul inundării acestor mesaje LSA în aria OSPF este ca toate routerele 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 routerele MOSPF din arie trebuie să deţină baze de date cu starea legături identice, singura diferenţă între aceste baze de date fiind includerea mesajelor LSA de apartenenţă la grup. Având bazele de date sincronizate, orice router MOSPF din domeniu poate calcula acelaşi arbore de distribuţie, cu rădăcina în reţeaua sursă iar ramurile extinzându-se până la fiecare reţea cu receptori. Totuşi arborele nu este calculat imediat, el fiind calculat la cerere atunci când primul pachet multicast pentru un anumit grup este primit. Acest lucru se întâmplă deoarece deşi toate routerele ştiu unde se găsesc receptorii, ele s-ar putea să nu ştie unde este sursa. Pentru calcularea arborelui de distribuţie informaţia referitoare la receptori este luată din mesajele LSA de apartenenţa la grup, iar informaţia referitoare la sursă este extrasă din primul pachet multicast recepţionat. Pentru a calcula calea cea mai scurtă de la sursă la fiecare destinaţie se folosesc mesajele LSA unicast reţea şi LSA router al căror bit MC este setat [Moy 94].

Avantajul folosiri mecanismului cu înscriere explicită bazat pe mesaje LSA de apartenenţă la grup combinat cu calcularea căi la cerere, este că routerul ştie deja locaţia receptorilor înainte de a realiza calculul. Spre deosebire de



protocoalele care folosesc un mecanism broadcast and prune cum este DVMRP-ul, pachetele multicast nu vor fi transmise în toată reţeaua.

Pe baza rezultatelor obţinute în urma calculului se vor introduce înregistrări în tabela de rutare multicast. Calea obţinută este lipsită de bucle de rutare şi fiecare router ştie care este interfaţa spre sursă şi care sunt interfeţele către receptori, mecanismul RPF ne mai fiind necesar. Înregistrarea din tabela de rutare pentru o anumită pereche (S,G) indică care este routerul de la care va fi recepţionat pachetul multicast şi către ce routere trebuie trimis pachetul mai departe. Baza de date locală de grupuri este folosită pentru a crea înregistrări în tabela de rutare pentru reţelele direct conectate care au receptori multicast.

MOSPF are o serie de limitări, una dintre acestea fiind că deşi protocolul OSPF suportă căi multiple de cost egal MOSPF nu permite folosirea lor. Arborele creat de MOSPF descrie o singură cale între sursă şi toate reţelele care conţin receptori. Altă problemă se poate ivi în situaţia în care routere OSPF şi MOSPF coexistă în reţele multiacces, în acest caz trebuind să ne asigurăm că routerul MOSPF va fi ales router DR. Dacă un router 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 rutat. Cea mai importantă limitare a protocolului MOSPF apare în situaţia în care topologia se modifică toată tabela de rutare trebuind ştearsă şi recalculată. Din acest motiv este foarte important ca domeniul să fie cât mai stabil.

5.2.6 PIM

PIM (Protocol Independent Multicast) are două moduri de operare, dens şi răsfirat, constând astfel în două protocoale de rutare PIM-DM (PIM Dense Mode) şi PIM-SM (PIM Sparse Mode). Are în denumire expresia independent deoarece se foloseşte de protocoalele de rutare 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 şi Juniper le implementează, acesta fiind motivul pentru care ele sunt prezentate în această secţiune. 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 informaţiei de rutare. 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 şi adresa ff02::13 pentru IPv6, cu semnificaţia toate routerele PIM (ALL-PIM-Routers).

PIM-DM

PIM-DM este foarte asemănător cu DVMRP din mai multe puncte de vedere. Amândouă sunt considerate protocoale pentru medii dense, operând în medii unde atât sursele multicast cât şi receptorii multicast sunt localizaţi în aceeaşi arie. Protocoalele care lucrează în mod dens nu ţin cont de debitul ocupat, folosind mecanismul broadcast and prune. Astfel routerele multicast presupun că toată lumea vrea să primească trafic multicast, în acest model traficul de la sursa multicast fiind transmis pe toate interfeţele până când interfaţa este ştearsă din arborele de distribuţie. Fiecare interfaţă are un timer care monitorizează timpul pentru care acea interfaţă este ştearsă din arborele de distribuţie, la expirarea acestui contor interfaţa fiind adăugată din nou la arborele de distribuţie şi traficul multicast fiind din nou transmis în reţea. Atât PIM-DM cât şi DVMRP creează arbori SBT care conectează fiecare sursă cu receptorii corespunzători. Arborii sunt creaţi în mod dinamic pentru fiecare sursă folosind mecanismul RPF, diferenţa majoră între cele două protocoale fiind că PIM-DM se bazează pe alte protocoale de rutare unicast pentru a construi arborele de distribuţie. Putem folosi orice protocol de rutare unicast: RIP, IGRP, EIGRP sau OSPF, împreună cu PIM-DM [Parkhurst 99].

PIM-DM este independent de protocolul de rutare IP unicast folosit, iar ca urmare a acestui fapt se poate întâmpla ca în aceeaşi reţea PIM-DM şi DVMRP să construiască arbori de distribuţie diferiţi, aşa cum se poate observa în fig. 5.46, fig. 5.47 şi fig. 5.48. În reţeaua din fig. 5.46 se foloseşte DVMRP ce construieşte arborii pe baza numărului de hopuri, acesta folosind legăturile la 56kbps.

Fig. 5.46 Rută DVMRP

În reţeaua din fig. 5.47 se utilizează PIM cu OSPF, metrica folosită fiind debitul legăturii, în acest caz cea

mai scurtă cale foloseşte legăturile la 100Mbps.



Fig. 5.47Rută PIM-DM şi OSPF

Fig. 5.48 prezintă o reţea PIM cu RIP arborele rezultat fiind similar cu cel de la DVMRP.

Fig. 5.48 Rută PIM-DM şi RIP

Această serie de figuri ne arată că PIM-DM este independent de protocolul de rutare unicast în sensul că el

poate opera indiferent de protocolul unicast folosit, dar arborele de distribuţie rezultat depinde de protocolul unicast. Fig. 5.49 prezintă modul de creare al arborilor SBT de către protocolul PIM-DM. Routerul A din figura

primeşte un pachet multicast şi verifică adresa sursă pentru a determina dacă pachetul a fost recepţionat pe interfaţa aflată pe calea cea mai scurtă către sursă (RPF check). Deoarece sursa este direct legată pe interfaţa routerului A, pachetul va fi transmis mai departe pe toate interfeţele, mai puţin cea pe care el a fost recepţionat.

Fig. 5.49 Crearea arborelui de distribiţie PIM-DM

Routerul B primeşte pachetul de la routerul A şi determină dacă a fost primit pe interfaţa RPF pentru acea

sursă. Deoarece pachetul a fost primit pe interfaţa corectă, routerul B îl va trimite mai departe către receptorul 1 şi routerul C. În acelaşi timp şi routerul C primeşte pachetul de la routerul A şi determină că a fost primit pe interfaţa RPF pentru acea sursă. În continuare routerul C îl va trimite mai departe către receptorul 2 şi routerul B. Pachetul multicast primit de routerul B de la routerul C şi cel primit de C de la B vor fi eliminate deoarece ele nu au fost recepţionate pe interfaţa aflată pe calea cea mai scurtă către sursă. În acest moment arborele de distribuţie a fost construit.

PIM-SM

PIM-SM este foarte asemănător cu PIM-DM deoarece amândouă folosesc un protocol de rutare unicast pentru a determina interfeţele RPF. Un protocol de mod răsfirat funcţionează într-un mediu în care sursele multicast şi receptorii nu sunt localizaţi în apropriere, acest lucru nu înseamnă că PIM-SM nu poate fi folosit într-o reţea locala (LAN), dar protocoalele de acest tip funcţionează mai eficient în reţele WAN (Wide Area Network).

Protocoalele de mod răsfirat folosesc un model cu înscriere explicită în care traficul multicast este transmis pe o interfaţa doar dacă acest lucru a fost solicitat. PIM-SM foloseşte arbori partajaţi pentru distribuirea traficului multicast, ce conţin un punct central care colectează traficul de la toate sursele pentru un grup multicast dat (fig. 5.50). Fiecare sursă rutează traficul pe calea cea mai scurtă către punctul central, de unde traficul este distribuit către receptori, din nou, pe calea cea mai scurtă. Acest punct central se numeşte la PIM-SM Rendezvous Point, adică RP. Într-o reţea pot exista mai multe routere RP, dar pentru un anumit grup trebuie să existe doar un singur RP.



Fig. 5.50Arborele partajat PIM-SM

Protocolul PIM-SM permite trecerea de la arborele de distribuţie partajat la un arbore de distribuţie sursă, la

depăşirea unui prag specificat pe routerele de tip frunză [Estrin 98]. Avantajul comutării la arborele sursă este că traficul este recepţionat pe calea cea mai scurtă, aceasta având în general o întârziere mai mică decât calea prin arborele partajat. Dezavantajul comutării îl constituie faptul că routerul trebuie să menţină mai multă informaţie de stare de tipul (S,G) [Parkhurst 99].

Mesajele PIM-SM sunt încapsulate în pachete IGMP (fig. 5.51), având un antet comun care identifică tipul mesajului şi modul de operare dens sau răsfirat.

Fig. 5.51 Încapsularea PIM-SM în IGMP

Tab. 5.8 prezintă tipul mesajelor PIM-SM conform [Estrin 98].

Tab. 5.8 Codul mesajelor PIM-SM Cod Tip pachet 0 Router Query 1 Register (Sparse Mode) 2 Register-Stop (Sparse Mode) 3 Join/Prune 4 RP Reachability 5 Assert

Mesajele de interogare PIM-SM sunt folosite pentru a descoperi routerele PIM-SM învecinate, acestea ne

conţinând o listă cu routerele învecinate. Dacă un vecin recepţionează mesajul de interogare el va înregistra adresa IP a vecinului, dar nu există nici un mecanism explicit de a anunţa vecinul că mesajul a fost primit. Routerul care a primit mesajul va trimite la rândul său un mesaj de interogare care are ca rol informarea routerelor PIM-SM de existenţa sa. În cazul protocolului PIM-DM la recepţia unui mesaj de interogare pe o interfaţă, această interfaţă era introdusa în oilist. Acest lucru nu se întâmplă în cazul PIM-SM, deoarece acesta foloseşte un mecanism de înscriere explicit.

Routerul trebuie să se înscrie la grup înainte ca traficul să fie transmis pe interfaţa corespunzătoare. În cazul unei reţele multiacces, cum ar fi o reţea de ce foloseşte FastEthernet, mesajele de interogare sunt trimise la adresa 224.0.0.2 ce desemnează grupul tuturor routerelor, mecanism folosit la alegerea routerului desemnat DR.

Parametrul Holdtime din mesajul de interogare indică timpul care trebuie să se scurgă până când vecinul va fi declarat nefuncţional. Intervalul de transmitere a mesajelor de interogare trebuie sa fie mai mic decât cel din parametrul Holdtime. Mesajele de interogare asigură un mecanism de menţinere în viaţa a legăturii între routere. Dacă



timpul specificat de parametrul Holdtime expiră şi vecinul respectiv era routerul DR pentru acea legătura, va fi ales un nou DR.

5.2.7 Parametrii de performan ţă multicast

Modul de operare şi performanţele protocoalelor de rutare multicast au fost studiate într-o serie de lucrări ştiinţifice şi teze de doctorat [Billhartz 97; Ueno 00; Li 05; Blaga 05; Blaga 07]. Parametri determinaţi diferă de la caz la caz, în continuare fiind prezentaţi parametrii cei mai des utilizaţi:

• întârzierea de transfer (end-to-end delay): timpul scurs între generarea unui pachet la sursă şi recepţia acestuia de un membru al grupului. Este timpul în care un pachet de date este rutat prin reţea de la sursă la destinaţie.

• bfseries utilizarea de resurse în reţea (network resource usage): numărul total de hopuri prin care trec copii ale unui pachet pentru a ajunge la toţi membri grupului. Se calculează împărţind numărul total de hopuri determinat pe parcursul simulări cu numărul total de pachete recepţionate.

• procentul de trafic de control (overhead traffic percentage): procentul de biţi de control din numărul total de biţi transmişi.

• concentrarea traficului (traffic concentration): este măsura distribuţiei traficului pe toate legăturile reţelei, fiind definit de raportul între debitul maxim pe o legătură şi debitul mediu pe toate legăturile.

• întârzierea de înscriere (join latency): timpul scurs de la trimiterea unei cereri de înscriere la grup până la recepţia primului mesaj multicast. Întârzierea de înscriere la grup (join latency) se manifestă în două cazuri:

• apariţia unui nou receptor. În modul dens, routerul DR asociat receptorului va trimite un mesaj Graft către sursele existente. Atunci când acest mesaj ajunge la un router care face parte din arborele de distribuţie multicast a grupului, numit punct de ataşare, pachetele de date vor putea ajunge la noul receptor. Acest proces ar trebui să dureze echivalentul întârzierii de transfer dus-întors (RTT) între receptor şi punctul de ataşare. În modul de lucru răsfirat înscrierea la grup se face prin trimiterea unui mesaj Join către routerul RP. Atunci când acest mesaj ajunge la un router care face parte din arborele de distribuţie RP al grupului pachetele de date vor putea ajunge la noul receptor. Se estimează durata procesului de înscriere ca fiind aproximativ egală cu RTT între receptor şi punctul de ataşare la arborele RP.

• apariţia unei surse noi. În modul dens, pachetele de date sunt transmise prin inundare la toate routerele. Astfel un receptor va primi datele după un timp echivalent cu întârzierea de transfer de la sursă la receptor. În mod răsfirat, datele de la sursa nouă ajung la RP încapsulate în mesaje Register. Acesta le decapsulează şi distribuie datele către receptori. Întârzierea de transfer de la sursă la receptor pe calea dată de arborele RP reprezintă timpul scurs până la primirea datelor de către receptor.

5.2.8 Servicii alternative de comunicare în grup În condiţiile în care tehnologia multicast nativă nu este disponibilă la scală largă în Internet, au apărut o serie

de tehnologii alternative. Serviciile alternative de comunicare în grup, numite AGCS (Alternative Group Communication Service), grupează într-un singur termen toate mecanismele care au abilitatea de a transmite informaţie simultan la mai mulţi receptori în mod asemănător cu rutarea multicast [El-Sayed 03].

Aceste tehnologii pot fi folosite pentru a depăşi limitările rutării multicast native. Pot fi folosite pentru a interconecta regiunile care suportă multicast, sau în medii în care rutarea nativă multicast nu este potrivită, cum ar fi reţelele ad-hoc, reţele mobile, care nu au o infrastructură fixă. Rutarea multicast a fost gândită pentru o infrastructură fixă, ierarhică în care routerele multicast sunt clar definite. Altă situaţie ce poată 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 native pentru fiecare grup în parte, va limita scalabilitatea sistemului.

Clasificarea acestor tehnologii este însoţită de prezentarea caracteristicilor şi a modului de operare a patru propuneri AGCS: CastGate, XCast/XCast+, ESM (End System Multicast) şi HyperCast.

Clasificarea AGCS

În funcţie de modul în care se realizează distribuţia datelor, avem următoarea clasificare: • reflector unicast/multicast, exemple: UMTP (UDP Multicast Tunneling Protocol), CastGate. • tunelare permanentă, exemple: DVMRP, AMT (Automatic Multicast Tunnels). • multicast cu topologie suprapusă (overlay), exemple: ESM, HyperCast. • servicii de rutare specifice, exemple: XCast/XCast+, DCM (Distributed Core Multicast).

Reflector unicast/multicast Soluţiile din această categorie sunt folosite pentru staţiile care au acces numai la

rutare unicast şi care folosesc un reflector. Acesta este o poartă între lumea multicast şi staţiile din regiunea unicast,



transmiţând fiecare pachet din regiunea multicast către staţiile unicast. Aceste soluţii se mai numesc tunelare punctuală deoarece ele creează un tunel între reflector şi receptor, acestea diferind de soluţiile cu tunelare permanentă.

Un aspect important pentru aceste AGCS este că reprezintă o soluţie de strat aplicaţie, datele putând ajunge de la reflector la receptor fie încapsulate în datagrame unicast, fie prin deschiderea unui socket UDP şi transmiterea numai a informaţiei utile din partea de date (payload), fără antetele iniţiale. În ultimul caz adresa sursă şi portul se vor pierde, dar protocoalele de strat superior pot recupera identitatea sursei. Acest tip de serviciu funcţionează o perioadă de timp limitată şi pentru un număr limitat de grupuri, în mod uzual existând câte un reflector pentru fiecare grup. Din această categorie fac parte UMTP, CastGate şi Mtunnel (Multicast Tunneling).

Această abordare nu este cea mai eficientă deoarece se creează puncte de concentrare a traficului (hot spot) în aproprierea reflectorilor. Totuşi aceste soluţii sunt uşor de implementat, iar reflectorul permite un control total asupra parametrilor serviciului: durată, grupul multicast, receptorii autorizaţi.

Tunelare permanentă Această abordare diferă de soluţia precedentă deoarece tunelarea se realizează la stratul reţea, prin rutare şi foloseşte încapsularea IP în IP. Crearea acestor tunele necesită diferite privilegii şi ele nu sunt create de receptor. În al doilea rând, dacă un reflector rezolvă necesităţile unui anumit grup, soluţia tunelării permanent oferă conectivitate întregului site. Aceste tunele sunt integrate în protocoalele de rutare multicast şi pot fi folosite indiferent de grupul multicast, implementarea mrouted a protocolului DVMRP oferind o astfel de soluţie. Această categorie a fost îndelung folosită în MBone pentru a interconecta regiuni multicast izolate, dar deoarece aceste tunele au performanţe reduse ele nu mai sunt folosite în prezent.

Multicast cu topologie suprapusă Această clasă de propuneri transferă suportul multicast din routere la nivelul receptorilor, de la stratul reţea la stratul aplicaţie. Receptorii trebuie să implementeze toate funcţiile necesare comunicării de grup, cum ar fi managementul apartenenţei la grup, replicarea şi distribuţia pachetelor. Membrii grupului comunică printr-o topologie suprapusă peste căile unicast, topologie care poate fi independentă de topologia fizică.

Acest tip de AGCS diferă din multe puncte de vedere de rutarea nativă multicast: • un nod care distribuie pachete în topologia suprapusă poate să fie un receptor, un server dedicat, sau un

router de graniţă, arborii de distribuţie multicast incluzând numai routere. • prin folosirea unei topologii multicast suprapuse, topologia fizică a reţelei este complet ascunsă, un arbore

virtual de distribuţie fiind creat între toate nodurile. • în cazul transmisiei multicast native informaţia referitoare la apartenenţa la grup este distribuită între

routerele multicast, iar în cazul topologiei overlay această informaţie poate fi deţinută de RP, sursă sau chiar de toate nodurile. Avantajul major al acestei abordări este că nu necesită suport special din partea routerelor, astfel ea putând fi

folosită în orice situaţie. Performanţele acestei abordări sunt mult influenţate de nivelul de congruenţă dintre topologia fizică şi cea suprapusă, căile din topologia suprapusă putând fi suboptimale din punctul de vedere al întârzierii, iar datele pot fi replicate de mai multe ori pe aceeaşi legătură fizică.

Servicii de rutare specifice Această categorie se bazează pe servicii de rutare dedicate, ele ne putând fi implementate şi folosite la cerere de receptori. Acestea încearcă se rezolve o parte din limitările rutării multicast native referitoare la scalabilitatea redusă în cazul unui număr mare de grupuri multicast cu receptori puţini şi dinamici.

Propunerea XCast introduce o listă explicită de destinaţii unicast în fiecare pachet folosind un antet nou XCast pentru IPv4 şi o nouă extensie de rutare pentru IPv6 [Boivie 05]]. Fiecare router de-a lungul căi procesează antetul IP şi în cazul unei ramificări în arborele de distribuţie, creează şi trimite noul pachet cu un subset potrivit de destinaţii pe interfeţele corespunzătoare. Când în noul antet mai rămâne o singură destinaţie pachetul este transformat într-un pachet unicast normal. Gradul ridicat de scalabilitatea al abordări XCast este dat de faptul că nu este necesară menţinerea de informaţie de stare în routerele din reţea.

CastGate

Tehnologia CastGate a fost dezvoltată de un grup de cercetători ai departamentului ETRO de la Vrije Universiteit Brussel (VUB). Aceasta asigură acces la conţinut multicast prin auto-tunelare, fiind gândită ca o tehnologie de tranziţie care va produce creşterea numărului de utilizatori multicast, determinând astfel furnizorii de servicii să implementeze multicast nativ [Liefooghe 04a].

Datele multicast sunt transmise printr-un tunel unicast de la serverul tunel localizat în Internet într-o zonă unde există acces multicast, şi clientul tunel care se găseşte la utilizator. Pentru a realiza acest lucru se foloseşte versiunea extinsă a protocolului UMTP. Sunt disponibile două moduri de tunelare, tunelarea per canal şi tunelarea neprelucrată (raw tunneling). În primul mod de lucru doar datele multicast destinate unui grup multicast precizat de adresă şi port vor fi tunelate. Al doilea mod de lucru permite tunelarea întregului trafic multicast. Deoarece unele echipamente filtrează traficul UDP este posibilă transportarea datelor prin tunelare HTTP ce nu va fi filtrată.

Arhitectura de bază CastGate are trei elemente componente: client tunel CastGate (TC - Tunnel Client), server tunel CastGate (TS - Tunnel Server) şi server tunel bază de date CastGate (TDS - Tunnel Database Server) (fig. 5.52). Baza de date conţine informaţii despre locaţia serverelor tunel disponibile, fiind posibilă utilizarea unui sistem ierarhic de baze de date, asemănător cu cel folosit pentru DNS (Domain Name System).



Fig. 5.52 Arhitectura CastGate

Un client tunel care doreşte să recepţioneze date multicast va cere serverului bază de date o listă cu serverele tunel disponibile, listă din care va alege unul. În continuare clientul anunţă serverul de ce grup multicast este interesat, urmând ca apoi serverul tunel să trimită datele clientului. Clientul poate fi integrat în orice aplicaţie multicast, sau poate funcţiona în forma de applet Java care rulează într-un browser de web. Din punct de vedere al utilizatorului operarea acestuia este transparentă, fără ca utilizatorul să stie că nu dispune de acces multicast nativ.

Ca urmare a dezvoltării continue a tehnologiei a apărut routerul CastGate [Liefooghe 04b]. Acesta integrează protocolul IGMP cu clientul tunel (fig. 5.53). În acest fel se poate asigura acces multicast pentru toate staţiile conectate la acelaşi segment de reţea, evidenţa tuturor staţiilor care se înscriu la grupul multicast fiind ţinută de routerul CastGate prin protocolul IGMP.

Routerul CastGate a fost extins prin introducerea protocolului de rutare nativă multicast PIM-SM [Blaga 05; Blaga 06; Blaga 07]. Această soluţie foloseşte tunelarea pentru a aduce datele multicast în domeniul local, de unde ele sunt distribuite prin multicast. A fost ales protocolul PIM-SM deoarece acesta construieşte arbori partajaţi cu o rădăcină comună, numită Redezvous Point. Toată informaţia despre activitatea multicast (surse active şi receptori) din domeniu este centralizată în routerul RP. Rezultatele experimentale ce au vizat determinarea stresului, a utilizării resurselor şi a întiderii, prezentate în [Blaga 07], arată că folosirea routerului CastGate cu PIM-SM este de 5 ori mai eficientă decât clientul CastGate şi de 2 ori mai eficientă decăt routerul CastGate.

Fig. 5.53 Routerul CastGate

Tehnologia CastGate permite rezolvarea unor probleme care nu sunt adresate de modelul multicast

nativ, cum este lipsa suportului AAA (Authentication, Authorization, Accounting), problemă rezolvată prin folosirea unei versiuni modificate de UMTP. Serverul tunel poate fi integrat cu un server RADIUS (Remote Authenticastion Dial-In User Service) pentru a permite autentificarea utilizatorilor, autorizarea sesiunilor şi pentru a realiza tarifarea serviciului multicast.

CastGuide şi CastContent au fost dezvoltate tot în cadrul proiectului [Liefooghe 04b]. CastGuide permite obţinerea unei liste cu sesiunile multicast în desfăşurare sau care urmează să fie difuzate, fiind echivalentul unui ghid TV pentru conţinut multicast. CastContent este gândit pentru furnizorii de conţinut, fiind în curs de dezvoltare două versiuni: CastLive care permite distribuţia în timp real a conţinutului multicast şi CastCOD pentru distribuţia conţinutului multicast la cerere (Content-On-Demand).

XCast, XCast+ şi XCast++

XCast a fost proiectat pentru a depăşi problemele legate de scalabilatea şi lipsa implementării multicast-ului nativ. Crearea şi menţinerea arborilor de distribuţie multicast în cazul grupurilor cu număr redus de membrii implică costuri nejustificat de mari, folosirea XCast pentru acest tip de grup eliminând semnalizările dintre routerele multicast şi informaţia de stare memorată de acestea [Bag-Mohammadi 05].

Serviciul multicast explicit se bazează numai pe rutarea unicast, sursa multicast incluzând o listă cu adresele IP a tuturor destinaţiilor într-un antet special (antet XCast), antet prezent în toate pachetele de date. Routerele intermediare determină hopul următor pentru fiecare destinaţie din listă folosind tabela de rutare



unicast, iar în funcţie de interfaţa de ieşire din router lista cu destinatari este împărţită în mai multe seturi. Pentru fiecare set routerul multiplică pachetul şi îl trimite pe interfaţa corespunzătoare. Dacă în listă mai există doar o singură destinaţie pachetul va fi trimis mai departe fără antetul XCast, ca orice pachet unicast, procedeu ce se numeşte X2U (Xcast to Unicast) [Boivie 05].

În fig. 5.54 sursa XCast doreşte să trimită date următoarelor cinci destinaţii: c1, c2, c5, c9 şi c17. Pachetul pleacă de la sursă având în antetul XCast o listă cu aceste destinaţii. Routerul R1 va realiza X2U pentru staţia c17, destinaţie ce va fi eliminată din listă. Procedeul X2U este folosit de R2 pentru c9 pe o interfaţă, iar pe cealaltă interfaţă lista va conţine doar trei destinatari. În ultimul nod, routerul R3, se foloseşte din nou X2U pentru a trimite datele către staţiile corespunzătoare. Aşa cum se poate observa din figură în fiecare nod lista este parsată şi scurtată.

Fig. 5.54 Distribuţia datelor folosind XCast

Antetul XCast în IPv4 este transportat între antetul IP şi antetul de strat transport, câmpul număr

protocol din antetul IP având valoarea PROTO_XCast. Adresa sursă este adresa sursei XCast, iar adresa destinaţie este adresa All_XCast_Nodes. În IPv6, antetul XCast este transmis folosind un antet de rutare extins.

În comparaţie cu modelul multicast nativ XCast prezintă mai multe avantaje. Astfel routerele nu mai memorează informaţie de stare, XCast fiind mai scalabil. Nu este necesară alocarea unei adrese multicast, iar răspuns la modificare rutelor unicast este automat. Protocoalele de rutare multicast se bazează pe informaţie referitoare la rutele unicast, iar în momentul în care acestea se modifică arborele de distribuţie trebuie refăcut. Deoarece sursa cunoaşte toţi destinatarii XCast oferă suport pentru AAA. Ca dezavantaje ale tehnologiei XCast trebuie să menţionăm prezenţa unui antet suplimentar, ce conţine lista destinaţiilor, în fiecare pachet de date. Prezenţa acestui antet implică procesări suplimentare în nodurile din reţea astfel apărând întârzieri. Alt dezavantaj este că numărul membrilor grupului multicast este limitat de dimensiunea antetului XCast.

Succesul XCast depinde de larga sa răspândire, existând mai multe modalităţi de a implementa XCast într-o reţea în care nu toate nodurile au suport pentru acesta. Prima modalitate implică configurarea de tunele între routerele XCast, iar folosirea procedeului X2U în mod prematur este o modalitate prin care un router ce descoperă că nu mai are vecini capabili XCast poate trimite datele către receptori. În acest caz pentru fiecare destinatar din antetul XCast se va trimite un pachet unicast, dezavantajul acestei metode fiind că duplicarea datelor se realizează mai devreme decât ar fi necesar conform topologiei reţelei. Ultima modalitate, tunelarea semipermeabilă, foloseşte tot tunelarea dar nu necesită configurare manuală, adresa uneia dintre destinaţiile din listă fiind folosită drept adresă destinaţie a pachetului IP. Routerele intermediare care nu suportă XCast, vor trata aceste pachet ca pachete unicast obişnuit. Dezavantajul acestei metode este calea suboptimală urmată de pachete, în cazul cel mai defavorabil, destinaţia a cărei adresă IP a fost folosită, trebuie să trimită datele mai departe către destinaţiile rămase în listă [Boivie 05].

XCast a fost gândit pentru a permite operarea unui număr mare de grupuri cu un număr redus de receptori, iar XCast+ reprezintă o extindere a funcţionalităţii acestuia în sensul creşterii numărului de receptori pentru un grup multicast. Introducerea suportului pentru IGMP/MLD (la fel ca la routerul CastGate) în routerele XCast oferă acces multicast tuturor nodurilor conectate la acel segment de reţea [Shin 01b].

Analizând modul de distribuţie a datelor, observăm că acestea sunt trimise routerelor XCast+ nu direct receptorilor (fig. 5.55). Este sarcina routerului XCast+ de a expedia datele către utilizatori prin multicast nativ, folosind procedeul X2M (XCast to Multicast) [Shin 01a].



Fig. 5.55 Distribuţia datelor folosind XCast+

Propunerea XCast++ extinde funcţionalitatea XCast+ prin introducerea de facilităţi PIM-SM [Blaga

07]. XCast++ poate fi utilizat fără a fi necesare routere specializate, suportă un număr crescut de receptori, obţinând performanţe apropriate de transmisia multicast. Rezultatele experimentale arată că performanţele XCast++ sunt doar cu 15% inferioare transmisiei multicast native [Blaga 07].

ESM

End System Multicast este o tehnologie în care toate funcţiile multicast: managementul grupului, rutarea datelor şi replicarea pachetelor sunt implementate de staţia finală (end system) folosind doar transmisii unicast [ESM 06]. Mutarea de pe stratul reţea pe stratul aplicaţie a suportului pentru multicast rezolvă unele dintre problemele transmisiei multicast native. Deoarece toate datele sunt transmise folosind unicast se depăşeşte problema răspândirii reduse a accesului multicast, iar toată informaţia de stare este stocată de staţiile finale nu în reţea. Această abordare permite soluţionarea simplificată a unor probleme inerente transmisiei multicast: corecţia erorilor, controlul fluxului şi al congestiei.

În ciuda numeroaselor avantaje ESM există câteva aspecte ce trebuie soluţionate pentru ca această tehnologie să devină o alternativă practică. Folosirea unei topologii overlay nu poate oferi performanţe similare IP multicast din punctul de vedere al debitului şi al întârzierii.

Protocolul Narada a fost dezvoltat pentru a implementa conceptul ESM, acesta permiţând auto-organizarea clienţilor într-o structură overlay în mod distribuit, luând în cosiderare obţinerea unei structuri cât mai eficiente. Protocolul a fost dezvoltat ţinând seama de următoarele aspecte [ESM 06]:

• auto-organizare: construcţia topologiei overlay trebuie să se facă total distribuit, iar procesul trebuie să fie robust la schimbarea dinamică a membrilor grupului.

• eficienţa topologiei overlay: arborele de distribuţie obţinut trebuie să fie eficient din punctul de vedere al aplicaţiei dar şi al reţelei. Din perspectiva reţelei trebuie să minimizăm redundanţa transmisiei şi întârzierea. Aplicaţiile pot avea cerinţe diferite, astfel o aplicaţie interactivă de genul audioconferinţă necesitând o întârziere redusă, iar o aplicaţie de distribuţie video având nevoie de un debit mare şi de întârzieri reduse.

• auto-îmbunătăţire: construcţia topologiei suprapuse trebuie să includă un mecanism prin care să se poate culege informaţii despre reţea, oferind astfel posibilitatea de îmbunătăţire a topologie pe măsură ce este disponibilă informaţie suplimentară.

• adaptare la dinamica reţelei: topologia trebuie să se adapteze continuu la schimbările dese din Internet. Crearea arborelui de distribuţie folosind Narada se face în doi paşi. Prima oară se construieşte unui graf

virtual complet între toate nodurile, care să respecte aspectele menţionate anterior, iar în pasul al doilea se construieşte arborele de distribuţie folosind algoritmi de rutare cunoscuţi. Fig. 5.56 prezintă procesul de creare a plasei (mesh) şi a arborelui de cale minimă cu sursa în nodul A.

Fig. 5.56 Etapele principale în construcţia ESM



În proiectarea protocolului s-a luat în considerare ca întârzierea căii între oricare membru din plasă să fie minimă şi cel mult de K ori mai mare decât întârzierea căii unicast, unde K este o constantă. Fiecare membru are un număr limitat de vecini, pe cei care nu depăşesc pragul. Pragul este dat de debitul conexiunii fiecărui membru la Internet.

Protocolul Narada construieşte peste plasa care leagă toţi membrii un arbore de distribuţie a datelor printr-un protocol cu algoritm vector distanţă. Pentru evitarea numărării până la infinit Narada foloseşte o strategie similară BGP [Rekhter 95b]. Fiecare membru din grup păstrează informaţii despre costul către ceilalţi membri dar şi calea care ne permite obţinerea acelui cost. Informaţiile despre costul şi calea legăturii între vecini sunt incluse în mesajele de rutare schimbate, arborele de distribuţie a datelor fiind construit din calea inversă cea mai scurtă între fiecare membru şi sursă, la fel ca la protocolul DVMRP Rodriguez 01].

Un membrul M primeşte pachete de date de la sursa S printr-un vecin N doar dacă N este următorul hop pe calea cea mai scurtă de la M la S. Membrul M trimite pachetele pentru toţi vecinii care au ca următor hop pe membrul M, pentru a ajunge la sursa S. Metrica folosită pentru alegerea căilor este întârzierea legăturii între vecini, fiecare nod estimând independent întârzierea legăturilor, iar arborele astfel obţinut se adaptează la dinamica reţelei.

Pierderile de pachete apar din cauza stărilor de tranziţie care se datorează ne convergenţelor tabelelor de rutare. Pierderi de pachete pot apărea şi la părăsirea grupului de un membru sau prin eliminarea unei căi. Pentru evitarea acestora se pot transmite datele pe vechea rută până la momentul convergenţei tabelelor de rutare. Acest lucru a fost realizat prin introducerea unei funcţii care măsoară costul rutării, valoarea unei rute obţinută cu această funcţiei fiind mai mare decât a unei căi valide şi mai mică decât infinit. Un membru care părăseşte arborele anunţă tuturor membrilor cu care a avut cale directă un cost obţinut folosind funcţia precedentă. Operaţiile cu vectori distanţă îi obligă pe membrii care au avut cale directă prin M să-şi aleagă altă rută validă, iar membrul care părăseşte grupul continuă să transmită pachete până în momentul în care nu mai este folosit de nici un alt membru.

HyperCast

Protocolul HyperCast permite crearea şi menţinerea topologiilor logice overlay între aplicaţiile, oferind astfel posibilitatea transferului de date între acestea. Aplicaţiile se auto-organizează formând o reţea logică suprapusă, datele fiind transmise pe căile acestei reţele cu ajutorul mecanismelor unicast. Fiecare aplicaţie comunică doar cu vecini din reţeaua overlay, nu cu toate nodurile. O reţea overlay este o reţea virtuală creată peste reţeaua fizică ce include routerele şi legăturile dintre acestea. Fiecare legătură logică din această reţea virtuală constă într-o cale unicast între două aplicaţii/noduri [HyperCast 06].

HyperCast oferă două metode pentru crearea de topologii overlay, folosind hipercuburi logice şi folosind triangulaţia Delaunay. Caracteristica principală a topologiilor HyperCast este că datele sunt transmise imediat după formarea topologiei, fără a fi necesar un protocol de rutare. Criteriile pentru evaluarea unei topologii overlay sunt [HyperCast 06]:

• necesitatea informaţiilor globale: scalabilitatea unei topologii overlay este limitată deoarece informaţia de stare dintr-un nod creşte puternic odată cu creşterea numărului nodurilor din topologie. Ambele metode de creare a topologiei overlay limitează informaţia de stare dintr-un nod.

• efortul de a construi şi menţine o topologie overlay: într-un caz ideal, numărul calculelor făcute odată cu aderarea sau părăsirea topologiei de către un membru trebuie să fie constant. Topologia hipercub respectă această condiţie doar la adăugarea unui nod nu şi la părăsire, iar triangulaţia Delaunay respectă acest criteriu doar în medie.

• necesitatea unui protocol de rutare: transmisia datelor într-o topologie overlay necesită menţinerea unei tabele de rutare care determină următorul hop. În alte tehnologii overlay fiecare nod este nevoit să ruleze un algoritm de rutare cu cale minimală pentru stabilirea tabelelor de rutare. Folosirea HyperCast cu triangulaţie Delaunay sau cu hipercuburi implică utilizarea unor adrese logice pentru noduri, adrese care determină următorul hop, eliminând astfel necesitatea unui protocol de rutare.

• potrivirea între topologia overlay şi cea fizică: în reţelele overlay transferul de date se face la stratul aplicaţie, astfel pachetul poate traversa Internetul de mai multe ori înainte de a ajunge la destinaţie. În consecinţă resursele disponibile nu sunt folosite în mod eficient şi pot apărea întârzieri nedorite în comparaţie cu transmisia la stratul reţea. Aceste dezavantaje apar la majoritatea reţelelor overlay, deci şi la tehnologia HyperCast, deoarece topologia este creată fără a lua în considerare topologia fizică. Reţele overlay folosind triangulaţia Delaunay În această secţiune se prezintă triangulaţia Delaunay

(Delaunay Triangulation – DT), folosită pentru a construi reţele overlay cu mii de noduri. Triangulaţia Delaunay pentru o mulţime de vârfuri A însemnă că pentru fiecare cerc circumscris unui triunghi format din trei vârfuri care aparţin mulţimii A nu există alt vârf în interiorul cercului respectiv (fig. 5.57). Fiecare vârf în DT are coordonate de tipul (x, y) care sunt puncte din plan. Trinagulaţia Delaunay a fost studiată în geometria computaţională [de Berg 97] şi aplicată în multe domenii ale ştiinţei şi ingineriei, inclusiv a reţelelor de telecomunicaţii [Baccelli 99].



Fig. 5.57 Triangulaţia Delaunay

Pentru a putea forma o reţea overlay DT fiecare aplicaţie, numită în continuare nod, este asociată cu un

vârf în plan cu coordonatele (x, y). Coordonatele sunt definite printr-un mecanism extern şi ar trebui să reflecte locaţia geografică a nodului. Două noduri au o legătură logică dacă vârfurile corespunzătoare sunt conectate de o latură în triangulaţia Delaunay asociată tuturor nodurilor.

Avantajul topologiilor overlay DT este că pot fi construite în mod distribuit şi rapid. În reţelele DT fiecare nod are în medie şase vecini, iar în cazul cel mai defavorabil N-1, unde N este numărul nodurilor. Dacă coordonatele unui nod din DT reflectă localizarea geografică atunci nodurile apropiate din reţeaua overlay sunt apropiate şi din punct de vedere geografic, totuşi acest mecanism nu ţine cont de infrastructura stratului reţea.

Proprietăţile triangulaţiei Delaunay sunt [Liebeherr 01]: • între orice pereche de vârfuri DT există un set de căi alternative distincte, existenţa acestor căi putând fi

exploatată de aplicaţii în cazul în care un nod se defectează sau nu mai răspunde. • numărul legăturilor unui vârf este în medie mai mic decât şase, iar în cea mai dezavantajoasă situaţie el

este N-1, unde N este numărul tuturor vârfurilor. • odată cu realizarea topologiei dispunem de informaţie de rutare care este conţinută în coordonate, astfel

nu mai este nevoie de un protocol de rutare • topologiile DT se realizează şi se întreţin în mod distribuit.

Reţele overlay folosind hipercuburi Un hipercub (HyperCube - HC) n-dimensional este un graf cu N=2n noduri, în care fiecare nod este etichetat cu un şir de caractere de forma kn......k1, unde ki = {0,1}. Nodurile din hipercub sunt conectate de o latură dacă şi numai dacă etichetele lor diferă doar printr-un bit. Un hipercub de dimensiunea n=3 este prezentat în fig. 5.58.

Fig. 5.58 Hipercub tridimensional

Deoarece numărul membrilor unui grup multicast este rareori o putere a lui doi va trebui să lucrăm cu

hipercuburi în care anumite poziţii nu sunt ocupate. Numim un hipercub incomplet, dacă are N noduri cu N<2n. În cazul hipercuburilor incomplete trebuie respectate următoarele condiţii:

• compact: dimensiunea hipercubului va fi cât mai redusă posibil n=log2N. includerea integrală a arborilor : asigură prezenţa fiecărui nod din hipercubul incomplet în arborele

de distribuţie, aşa cum se poate vedea în fig. 5.59.



Fig. 5.59 Arbore de distribuţie încoporat în hipercub incomplet

Prima condiţie poate fi îndeplinită prin reetichetarea nodurilor atunci când un nod părăseşte hipercubul.

Garantarea includerii integrale a arborilor se realizează prin folosirea codul Gray pentru a ordona sau a adăuga noduri în hipercub. Codul Gray este folosit pentru construcţia arborilor de distribuţie din hipercuburi incomplete, un nod cu eticheta G(i) calculând eticheta nodului părinte din arborele de distribuţie cu nodul rădăcină având eticheta G(r). Algoritmul constă în schimbarea unui singur bit.

Arborele construit astfel are următoarele proprietăţi: • lungimea căii între un nod şi rădăcină este dată de distanţa Hamming între etichete. • dacă N=2n, arborele este binomial (N numărul nodurilor). • pentru un hipercub incomplet şi compact arborii obţinuţi din algoritm sunt incluşi integral.

Protocolul HyperCast poate ordona şi menţine membrii unui grup multicast într-o structură logică de

tip hipercub, astfel încât să se poată implementa servicii fiabile multicast, protocolul ne fiind folosit pentru transmisia datelor. Acesta foloseşte avantajele oferite de serviciile IP multicast, un membru al grupului multicast putând deveni membru al unei structuri hipercub prin înscrierea la un canal de control. Fiecare nod poate primi sau trimite mesaje pe acest canal de control.

Nodurile din hipercub au adrese logice şi fizice. Adresa fizică este adresa IP a nodului şi portul UDP folosit pentru transmiterea unicast a mesajelor, fiecare nod având o adresă fizică unică. Adresa logică este eticheta formată dintr-un şir de biţi care determină poziţia nodului în hipercub. Pentru un hipercub m-dimensional sunt necesari m biţi pentru adresa logică a nodului. Protocolul HyperCast reprezintă adresele logice pe 32 de biţi cu un bit rezervat pentru a desemna adresele logice invalide, teoretic protocolul permiţând 231 noduri.

Se spune că hipercubul este într-o stare stabilă dacă are următoarele caracteristici: • consistent: nu există noduri cu aceeaşi adresă logică. • compact: într-un grup multicast cu N noduri, nodurile sunt etichetate de la G(0) până la G(N-1) • conectat: fiecare nod cunoaşte adresa fizică a vecinilor din hipercub.

Ataşarea sau detaşarea nodurilor din hipercub şi defectele apărute în reţea, pot conduce la instabilitatea

hipercubului şi astfel la neîndeplinirea condiţiilor anterior menţionate. Sarcina protocolului HyperCast este de a menţine stabilitatea hipercubului într-un mod eficient şi sigur.

5.2.9 Parametrii de performan ţă AGCS

Mai mulţi parametri au fost folosiţi pentru a evalua performanţele şi implicaţiile asupra reţelei a sistemelor AGCS în [El-Sayed 03; Blaga 07], parametrii fiind împărţiţi în două clase. Prima clasă se referă la calea pe care se realizează transmisia datelor:

• stres (stress): defineşte încărcarea unei legături ca fiind numărul de pachete identice transportat, valoarea optimă 1 obţinându-se folosind rutarea multicast.

• utilizarea resurselor (resource usage): se defineşte drept suma produsului între întârziere şi stres pe toate legăturile l care participă la distribuţia datelor). Acest parametru evaluează efectul asupra întregii reţele, presupunând că legăturile cu întârzieri mari sunt mai costisitoare.

sd i

l

ii

R *1∑

=

=

• întindere (stretch): este raportul între întârzierea dintre noduri folosind topologia de distribuţie suprapusă şi întârzierea de-a lungul căi directe unicast între acestea. Acest parametru se mai numeşte întârziere relativă între sursă şi un receptor (relative delay penalty). A doua clasă de parametri se referă la performanţele staţiei finale:

• pierderi în caz de defecţiune (losses after failures): ne dă numărul mediu de pachetele pierdute ca urmare a defectării unui singur nod.



• timpul până la primul pachet (time to first packet): defineşte timpul după care un nou membru care s-a înscris la grup începe să recepţioneze date.

• traficul de control (control overhead): menţinerea topologiei AGCS are un cost din punctul de vedere al informaţiei de control schimbate, adică numărul de mesaje procesate şi debitul transmis.

5.4 Referin ţe [Baccelli 99] F. Baccelli, D. Kofman & J.-L. Rougier. Self organizing hierarchical multicast trees and their optimization. In IEEE INFOCOM, 1999. [Bag-Mohammadi 05] M. Bag-Mohammadi, N. Yazdani & S. Samadian-Barzoki. On the Efficiency of Explicit Multicast Routing Protocols. In 10th IEEE Symposium on Computers and Communications (ISCC2005), 2005. [Billhartz 97] Tom Billhartz, J. Bibb Cain, Ellen Farrey-Goudreau, Doug Fieg & Stephen Gordon Batsell. Performance and Resource Cost Comparisons for the CBT and PIM Multicast Routing Protocols. IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pages 304–315, 1997. [Blaga 05] Tudor Mihai Blaga, Virgil Dobrota, Kris Steenhaut, Ionut Trestian & Gabriel Lazar. Steps Towards Native IPv6 Multicast: CastGate Router with PIM-SM Support. In Proceedings of the 14th IEEE Workshop on Local and Metropolitan Area Networks LANMAN 2005, September 2005. [Blaga 06] Tudor Mihai Blaga & Virgil Dobrota. Evaluating and Improving Alternative Multicast Solutions, CastGate and CastGate with PIM-SM. In COST290, 5th Management Committee Meeting, February 2006. [Blaga 07] Tudor Mihai Blaga, Contribuţii la îmbunătăţirea rutării multicast, teză de doctorat, Universitatea Tehnică din Cluj-Napoca, 2007. [Boivie 05] R. Boivie, N. Feldman, Y. Imai, W. Livens, D. Ooms & O. Paridaens. Explicit Multicast (Xcast) Basic Specification. draft-ooms-xcast-basicspec-09.txt, December 2005.



[Buzila 07] A. Buzila, G. Lazar, T. Blaga, V. Dobrota, Evaluation of QoS Parameters for IPTV, The Scientific Bulletin "Acta Technica Napocensis" Electronics And Telecommunications, Technical University of Cluj-Napoca, Cluj-Napoca, Romania, vol. 48, nr. 3, 2007, pp.9-14. [Deering 89] S.E. Deering. Host extensions for IP multicasting. RFC 1112 (Standard), August 1989. Updated by RFC 2236. [Dobrotă 03b] Virgil Dobrotă. Reţele digitale în telecomunicaţii. Volumul III: Osi si TXP/IP. Editura Mediamira, Cluj-Napoca, 2003. [Doyle 01] Jeff Doyle. Routing tcp/ip, volume ii. Cisco Press, 2001. [El-Sayed 03] Ayman El-Sayed, V. Roca & L. Mathy. A Survey of Proposals for an Alternative Group Communication Service. IEEE Network, no. January-February, pages pp. 46–51, 2003. [ESM 06] ESM. End System Multicast. http://esm.cs.cmu.edu/, 2006. [Estrin 98] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma & L. Wei. Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. RFC 2362 (Experimental), June 1998. [Fenner 97] W. Fenner. Internet Group Management Protocol, Version 2. RFC 2236 (Proposed Standard), November 1997. Obsoleted by RFC 3376. [HyperCast 06] HyperCast. HyperCast General Information. http://www.cs.virginia.edu/mngroup/hypercast/general.html, 2006. [Li 05] Dan Li, Jianping Wu, Ke Xu, Yong Cui, Ying Liu & Xiaoping Zhang. Performance Analysis of Multicast Routing Protocol PIM-SM. In Proceedings of the Advanced Industrial Conference on Telecommunications Service Assurance with Partial and Intermittent Resources Conference/E-Learnig on Telecommunications Workshop, July 2005. [Liebeherr 01] J. Liebeherr & M. Nahas. Application-layer Multicast with Delaunay Triangulations. In Global Internet Symposium, IEEE Globecom, 2001. [Liefooghe 02] Pieter Liefooghe. An Architecture for Seamless Access to Multicast Content. Phd thesis, Vrije Universiteit Brussel, 2002. [Liefooghe 04a] Pieter Liefooghe. CastGate: An Auto-Tunneling Architecture for IP Multicast. Draft-liefooghe-castgate-02.txt, October 2004. [Liefooghe 04b] Pieter Liefooghe, M. Goossens, A. Swinnen & B. Haagdorens. The VUB Internet Multicast "CastGate" Project. Technical Report 10/2004 v1.8, Vrije Universiteit Brussel, 2004. [Moy 94] J. Moy. Multicast Extensions to OSPF. RFC 1584 (Proposed Standard), March 1994. [Parkhurst 99] William Parkhurst. Cisco multicast routing & switching. McGraw-Hill, 1999. [Rekhter 95b] Y. Rekhter & T. Li. A Border Gateway Protocol 4 (BGP-4). RFC 1771 (Draft Standard), March 1995. Obsoleted by RFC 4271. [Rodriguez 01] Adolfo Rodriguez, J. Gatrell, J. Karas & R. Peschke. Tcp/ip tutorial and technical overview. IBM, 2001. [Shin 01a] M.K. Shin, Y.J. Kim, J. Lee & S.H. Kim. Explicit Multicast Extension (Xcast+) Supporting Receiver Initiated Join. draft-shin-xcast-receiverjoin-01.txt, 2001. [Shin 01b] M.K. Shin, Y.J. Kim, K.S. Park & S.H. Kim. Explicit Multicast Extension (Xcast+) for Efficient Multicast Packet Delivery. ETRI Journal, vol. Volume 23, no. Number 4, 2001. [Ueno 00] Seiji Ueno, Toshihiko Kato & Kenji Suzuki. Analysis of Internet Multicast Traffic Performance Considering Multicast Routing Protocol. In Proceedings of the 2000 International Conference on Network Protocols, November 2000. [Vida 04] R. Vida & L. Costa. Multicast Listener Discovery Version 2 (MLDv2) for IPv6. RFC 3810 (Proposed Standard), June 2004. Updated by RFC4604. [Waitzman 88] D. Waitzman, C. Partridge & S.E. Deering. Distance Vector Multicast Routing Protocol. RFC 1075 (Experimental), November 1988.

CURS Solutii de Distributie Multicast

Documents

Transcript of CURS Solutii de Distributie Multicast