Comunicație - Curs: Computer Networks - IP Protocols

24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Comutarea de pachete de tip “Store-and-Forward” fig 5-1 H1A, EF pot fi linii închiriate H2 - LAN ope...

24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Comutarea de pachete de tip “Store-and-Forward” fig 5-1 H1A, EF pot fi linii închiriate H2 - LAN operat de client Politică simplă - un host trimite pachetul celui mai apropiat ruter 4 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Servicii furnizate Serviciile să fie independente de tehnologia ruterului Nivelul transport să fie independent de numărul, tipul și topologia ruterelor Adresele de rețea să folosească o schemă uniformă (LAN/MAN/WAN) Întrebare: servicii orientate pe conexiune? tabăra Internet: NU Rețelele sunt nesigure => control de flux, erori “End 2 End” Primitive: send_pkt, recv_pkt Pachete rutate independent pe baza adresei tabăra telecom: DA Calitatea serviciului este importantă => conexiuni, căi rezervate Circuite virtuale în ATM 5 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Serviciul datagramă (neorientat pe conexiune) Comunicația între procese folosește nivelul transport. Identificarea procesului partener Mesaje lungi Exemplu P1->P2 Linie serială H1->A, 4 pachete rutare pachete 6 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Serviciul datagramă (neorientat pe conexiune) Ruterul A Rutarea inițială pentru destinația F este C Pachetul 4 poate urma o cale diferită A poate decide un drum alternativ datorită Congestiei Calcul drum mai scurt avarie în rețea 7 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Serviciul orientat pe conexiune Circuit virtual CV From, next = nume de interfețe Se alege o cale la crearea conexiunii Calea este o înșiruire de etichete LOCALE Se evită alegerea unei noi căi pentru fiecare pachet trimis o Relevante doar pentru noduri vecine Fiecare pachet poartă un identificator o P1 și P3 folosesc eticheta “1” de cale, NU de DESTINAȚIE! Exemplu: P1P2 - calea 1; P3P2 - calea 2 8 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Comparație rețele datagramă - rețele cu circuite virtuale problemă rețea datagramă rețea cu circuite virtuale CV stabilirea circuitului nu este necesară obligatorie adresare Fiecare pachet conține adresa Fiecare pachet conține un număr mic completă pentru sursă și de CV destinație informații de stare Ruterele nu păstrează informații Fiecare CV necesită spațiu pentru despre conexiuni tabela ruterului per conexiune rutare Fiecare pachet este rutat Calea este stabilită la inițializarea CV. independent Toate pachetele o urmează defectare ruter Se poate re-ruta Toate CV prin ruter sunt terminate calitate servicii dificil Simplu, dacă se alocă resurse în avans control congestie dificil Simplu, dacă se alocă resurse în avans echilibrare încărcare ușor dificil 9 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Comparație rețele datagramă - rețele cu circuite virtuale Uneori sunt necesare compromisuri Memorie ruter lățime de bandă CV - header mic, fără adrese complete, pachet mic, tabele de CV Datagrame - header mare, adrese complete, pachete mari Tabelele de rutare sunt necesare pentru ambele soluții Timp stabilire circuit timp analiză adresă CV - stabilirea căii durează; retransmiterea rapidă (lookup) Datagrame - se testează prefixe/măști…longest prefix match Exemple de aplicații Tranzacții scurte - CV: overhead mare Rezervări de lunga durata (luni) - CV: garanții 10 24.03.2025 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Rutarea rutare = funcția principală a nivelului rețea – salturi multiple => alegerea ruterului următor – rețele cu difuzare => trecerea prin subrețele Rutare: două procese diferite – Rutare propriu-zisă (routing) - procedura de obținere a căilor, stocate în tabela de rutare – Retransmitere (forwarding) - folosirea tabelei pentru dirijarea pachetelor Proprietățile algoritmului de rutare – Corectitudine - pachetele chiar ajung la destinație – Robustețe - nodurile și liniile pot cădea – Stabilitate - atinge o stare de echilibru – Echitate - nimeni nu este dezavantajat – Optimalitate - se folosesc resurse minime – Simplitate - Exemplu algoritm de rutare: drumul cel mai scurt 11  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Modelul Internetului Nivelele străbătute de pachete  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Protocolul IP Are – o schemă de adresare care permite identificarea oricărui calculator din Internet – un model - datagramă - pentru transmiterea datelor de la un nod gazda la altul datagrama = pachet Modelul de serviciu – best effort – rețeaua “face toate eforturile” să livreze pachetele la destinație – nu face nici o încercare să corecteze erorile Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Protocol IPv4 – formatul pachetului SERVICE TYPE = precedence (3), delay, throughput, reliability, cost OPTIONS: PROTOCOL = (TCP, UDP, etc.) Security IDENTIFICATION Id datagrama de care aparţine Strict source routing fragmentul Loose source routing Record route FRAGMENT OFFSET pozitia fragmentului in pachet Timestamp FLAGS DF = Don’t Fragment / MF = More Fragments max numar 65535 cuvinte octeti de 32 biti max 8192 fragmente a 8 octeti Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare MTU – Maximum Transmission Unit Net1 MTU=1420 1420) Net2 MTU=532 532) Net3 MTU=1420 1420) Fragmentarea se face la R1 Reasamblarea se face la H2 – de ce? Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Câmpurile de antet pentru fragmentare (1) (a) pachet transmis ne-fragmentat prin Net1 cu MTU = 1420 are: 1400 octeți de date 20 octeți de antet IP MF = 0 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Câmpurile de antet pentru fragmentare (2) Net2 are MTU = 532 Ruterul R1 segmentează pachetul în 3 fragmente (fig: b1-b3) - lungimea fiecărui segment b2 este multiplu de 8 octeți - offset-ul numără grupuri de câte 8 octeți - Offset = 64 = 512 / 8 unde e restul până la 532 octeți? b1 b3 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Putem avea refragmentare? Răspunsul teoretic: DA / însă în practică, se folosește PathMTU și singura fragmentare se face la sursă Net1 MTU=1420 1420) Net2 MTU=1020 532) Net3 MTU=532 1420) 512 Ident = X MF = 1 1000 bytes Ident = X MF = 1 bytes 1400 488 Ident = X MF = 0 Ident = X MF = 0 bytes bytes 400 Ident = X MF = 0 bytes 400 Ident = X MF = 0 bytes Reasamblarea se face la destinație, unde se copiază datele în memorie pentru toate pachetele având Ident = X – se copiază tot ce primim pt. pachete până când primim un pachet având Ident != X – dacă un fragment întârzie, datele nu au sens și sunt discarded fie la nivel IP dacă nu avem toate sub-fragmentele din ultima fragmentare fie la nivel TCP dă eroare –se face din nou o verificare CRC Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Clase de adrese IP Fiecare nod (gazdă/ruter) are o adresă IP asociată cu interfața lui de rețea Un nod cu mai multe interfețe are mai multe adrese IP (ex. rutere) Clasa de Biţi în Număr maxim Biţi în Număr maxim de adrese prefix de reţele sufix gazde per reţea A 7 128 24 167777216 B 14 16384 16 65536 C 21 2097152 8 256 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Câteva adrese speciale Prefix Suffix Semnificație Scop (rețea) (gazdă) toţi 0 toţi 0 acest calculator Folosită când nodul încă nu are o adresă network toţi 0 network Identifică reţeaua network toţi 1 broadcast broadcast în reţeaua specificată toţi 1 toţi 1 broadcast broadcast în reţeaua locală 127 orice loopback testare Notații pentru adrese binară 11000010 00011000 00010001 00000100 zecimală 194.24.17.4 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Tabele de dirijare Orice pachet conține o adresă IP a destinatarului, cu două părți Un pachet este transmis de la sursă la destinație trecând prin noduri intermediare (rutere), fiecare legând între ele cel puțin două rețele Rol ruter – primește un pachet și îl livrează gazdei de destinație (dacă este în aceeași rețea) – Toate nodurile care au aceeași adresa_retea sunt situate în aceeasi rețea fizica și pot comunica direct prin legătura de date (transmit cadre) altfel, îl re-transmite (forward) către un alt nod NextHop – Folosește tabela de dirijare (rutare) care are intrări de forma Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Algoritm de forwarding IP Extrage destinație din datagramă Caută o intrare cu adresa_retea în tabela de dirijare if adresa_retea apare în tabela de dirijare if adresa_retea indică o rețea direct conectată then transmite datagrama direct la adresa_gazda else transmite datagrama următorului ruter (Next Hop) else transmite datagrama unui ruter implicit Adresarea ierarhica reduce numărul de intrări în tabela de dirijare (o intrare pentru o adresa_retea) În practică, tabelele de rutare sunt separate pe clase de adrese - Căutare prin: indexare (A şi B) sau hashing (C) Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Exemplu Transferul unei datagrame între H5 și H8 H5 are legătura (printr-un punct de acces AP) la ruterul R1 Pachetul trece prin ruterele R1, R2 și R3 R3 este în aceeași rețea cu H8 și îi livrează direct datagrama Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Subreţele Regula “o adresă pentru fiecare rețea fizică separată” – folosește ineficient spațiul de adrese o rețea de clasă C cu 2 noduri consumă doar 2 din totalul de 255 de adrese de nod o rețea de clasă B cu peste 255 noduri ocupă peste 64000 de adrese indiferent dacă le folosește pe toate sau nu soluția 1 – subrețele – de ex. o rețea clasă B este împărțită în mai multe subrețele apropiate geografic soluția 2 - adrese fără clase Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare CIDR – Classless InterDomain Routing Ideea: alocă spațiul de adrese IP în blocuri de lungimi diferite Notația specială pentru adresa de rețea CIDR 194.24.0.0/21 ➔ din cei 32 de biți ai adresei IP adresa_retea ocupă 21 biţi adresa_gazda ocupă 11 biti Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare CIDR – Exemplu Pentru a afla adresa_retea se folosesc măști Cambridge: Adresă 11000010 00011000 00000000 00000000 Mască 11111111 11111111 11111000 00000000 Edinburgh: Adresă 11000010 00011000 00001000 00000000 Mască 11111111 11111111 11111100 00000000 Oxford: Adresă 11000010 00011000 00010000 00000000 Mască 11111111 11111111 11110000 00000000 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare CIDR – reguli de alocare a adreselor Reguli pentru a avea o mască pentru un bloc de adrese → lungimea blocului trebuie sa fie o putere a lui 2 → toate adresele din bloc au aceeași adresa_retea → adresa de început a blocului de adrese trebuie să fie multiplu de dimensiunea acestuia Ex.: zona de adrese pentru Oxford începe la o frontieră de 4096 octeți 0 2048 3072 4096 Cambridge Edin. Oxford Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Algoritm forwarding Intrare în tabela de rutare - (adresa_retea, Masca, NextHop) Algoritmul alege intrarea pentru care (Adresa_IP AND Masca) = adresa_retea Ex. Sosește pachet cu adresa_IP = 194.24.17.4 compară cu Cambridge /21 – adresa_rețea = 194.24.0.0 adresa_rețea: 11000010 00011000 00000000 00000000 Masca: 11111111 11111111 11111000 00000000 adresa_IP: 11000010 00011000 00010001 00000100 Adresa_IP AND Masca: 11000010 00011000 00010000 00000000 ➔ = 194.24.16.0 ≠ 194.24.0.0 ➔ nepotrivire Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Algoritm forwarding (2) Ex. Sosește pachet cu adresa_IP = 194.24.17.4 Cambridge /21 – adresa_rețea = 194.24.0.0 (Adresa_IP AND Masca) = 194.24.16.0 ➔ nepotrivire Edinburgh /22 - adresa_rețea = 194.24.8.0 (Adresa_IP AND Masca) = 194.24.16.0 ➔ nepotrivire Oxford /20 - adresa_rețea = 194.24.16.0 (Adresa_IP AND Masca) = 194.24.16.0 ➔ potrivire Dacă nu sunt alte potriviri -> folosește intrarea pentru Oxford Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Potriviri multiple Prefixe de lungimi diferite → unele adrese IP se pot potrivi cu mai multe adrese_retea din tabela de dirijare Ex. adresa_IP 171.69.10.5 se potrivește cu adresele de rețea 171.69.0.0/16 171.69.10.0/24 Regula: se alege potrivirea “mai lungă” Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Reducere dimensiune tabelă rutare Soluție - agregarea unor adrese Considerăm adresele de rețea: C - Cambridge: 194.24.0.0/21 E - Edingurgh: 194.24.8.0/22 O - Oxford: 194.24.16.0/20 C: adresa_retea 11000010 00011000 00000000 00000000 E: adresa_retea 11000010 00011000 00001000 00000000 O: adresa_retea 11000010 00011000 00010000 00000000 Presupunem: pentru rutare la C, E, O, nodul NewYork are în tabela de dirijare același NextHop Tabela de dirijare poate include o singură intrare comună pentru adresa_retea 11000010 00011000 00000000 00000000 adică 194.24.0.0/19 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Exercițiu Un număr mare de adrese IP consecutive sunt disponibile începând cu 198.16.0.0. Să presupunem că patru organizații, A, B, C, D, cer câte 4000, 2000, 4000 şi 8000 adrese, în această ordine. Precizați, pentru fiecare dintre ele, prima și ultima adresă IP atribuită, precum și masca în notația w.x.y.z/s. 198.16.0.0 = 11000110.00010000.00000000.00000000 Primul numar ^2 > 4000 = 4.096 (adrese de alocat pt. A, C) Primul numar ^2 > 2000 = 2.048 (adrese de alocat pt. B) Primul numar ^2 > 8000 = 8.192 (adrese de alocat pt. D) 8192 8192 8192 2048 4096 4096 4096 4096 4096 4096 Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Exercitiu (2) 198.16.0.0 = 11000110.00010000.00000000.00000000 8192 8192 8192 2048 4096 4096 4096 4096 4096 4096 A: 4096 = 2^12 => hostID are 12 biti si netID are 20 biti 11000110.00010000.00000000.00000000 / 20 = 198.16.0.0 / 20 B: 2048 = 2^11 => hostID are 11 biti si netID are 21 biti 11000110.00010000.00010000.00000000 / 21 = 198.16.16.0 / 21 C: 4096 = 2^12 => hostID are 12 biti si netID are 20 biti 11000110.00010000.00100000.00000000 / 20 = 198.16.32.0 / 20 D: 8192 = 2^13 => hostID are 13 biti si netID are 19 biti 11000110.00010000.01000000.00000000 / 19 = 198.16.64.0 / 19 Protocoale de comunicaţie – Curs 4 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Nivelul Rețea ICMP, ARP Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare ICMP- Internet Control Message Protocol net/host/protocol/port unreachable; TTL exceeded fragmentation needed and DF set; redirection... Echo request Echo reply... ICMP foloseşte IP ptr transmisie & IP folosește ICMP pentru raportare de erori Test accesibilitate (ping trimite ICMP Echo și așteaptă un timp răspunsul) Trasare ruta (traceroute trimite serie de datagrame cu valori TIME TO LIVE crescătoare și primește mesaje ICMP Time exceeded din care extrage adresa ruterului) Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Folosire ICMP pentru aflare path MTU Path MTU = Maximum Transmission Unit minimă pentru o cale ▪ Folosește mesaj eroare ICMP = fragmentare necesară dar nepermisă – Sursa trimite probe cu DF în datagrama IP – Dacă datagrama > MTU => sursa primeşte eroarea ICMP Destination Unreachable cu Fragmentation Needed and Don't Fragment was Set – Sursa trimite probe mai scurte Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare adresa IP adresa Ethernet La livrarea directă (destinatar în aceeași rețea) se folosește adresa fizică a receptorului (pt. care se cunoaște adresa IP) Nu există o legătură biunivocă între adresa fizică și adresa IP De ex. – adresa IP are 32 biți – adresa Ethernet are 48 biți Pentru mapare se pot folosi – tabele de corespondență – formule de calcul – schimb de mesaje ARP - Address Resolution Protocol – Face maparea între adresa de protocol și adresa hardware Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare ARP - Address Resolution Protocol Secvența de mesaje pentru a afla adresa fizică ▪ w difuzează o cerere ARP cu adresa IP cunoscută ▪ cererea este primită de toate gazdele din rețeaua locală ▪ y – care are adresa IP respectivă – trimite ca răspuns adresa fizică (Ethernet) Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Conversie adresa IP – adresa fizică Format mesaje ARP – conceput pentru diverse categorii de adrese ▪ Hardware type: 1 pentru Ethernet ▪ Protocol type: 0x0800 pentru IP (0000.1000.0000.0000) ▪ HLEN - Hardware len: 6 octeți pentru Ethernet ▪ PLEN - Protocol len: 4 octeți pentru IP ▪ Operation: 1=cerere, 2=răspuns Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare NAT – Network Address Translation O adresă publicå pentru mai multe calculatoare Foloseşte adrese locale (private sau non-rutabile) NAT translatează între adresa privată şi o adresă globală Adrese private 192.168.0.0 – 192.168.255.255 (65.536 adrese IP) 172.16.0.0 – 172.31.255.255 (1.048.576 adrese IP) 10.0.0.0 – 10.255.255.255 (16.777.216 adrese IP)  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Translatarea adresa globală → adresa privată SRC = 10.0.0.3 SRC = 10.0.0.2 SRC = 10.0.0.1 SRC = 128.210.24.6 DST = 128.210.24.6 DST = 10.0.0.1 ? DST = 10.0.0.2 ? DST = 10.0.0.3 ? Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Principiul NAT Foloseşte adresa IP + număr port transmitator tabela de translatare Transmisie înlocuieşte adresa IP locală cu o adresă IP globală memorează (in tabela de translatare) corespondenţa şi număr port inlocuieşte număr port cu index în tabela translatare re-compune sumele de control IP şi TCP port=1200 IP-local = 10.0.0.1 tabela de translatare IP-local IP-glob port antet antet TCP IP 20 10.0.0.1 128.210.24.6 1200 index=20 IP-glob=128.210.24.6 Protocoale de comunicaţie – Curs 5  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Receptie obţine număr port din pachet (= index în tabela translatare) extrage adresa IP locală şi număr port înlocuieşte adresa IP şi număr port din pachet re-calculează sumele de control IP şi TCP port=1200 IP-loc=10.0.0.1 IP-loc IP-glob port antet antet TCP IP 20 10.0.0.1 128.210.24.6 1200 index=20 IP-glob=128.210.24.6 Protocoale de comunicaţie – Curs 5 Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Nivelul Rețea - Algoritmi de rutare - Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Dirijarea - clasificare Rutare – criterii de dirijare 1. statică - tabele fixe 1.calea cea mai scurtă 2. dinamică - tabele 2.întârzierea medie calculate – criterii diverse globală – adaptarea la condițiile de 3.folosirea eficientă a trafic resurselor statică 4.echitabilitatea dinamică – informații schimbate între – locul unde se fac noduri calculele 1. starea legăturii (link centralizată state) distribuită 2. vectorul distanțelor (distance vector) Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Vectorii distanţelor 6 Algoritm distribuit ! 5 Fiecare nod trimite periodic 3 vecinilor săi o listă cu distanțele de la el la celelalte noduri. Următorii vectori au fost primiți de nodul C (lista include distanțele de la B, D, E la nodurile A, B, C, D, E, F, în această ordine): De la B: (5, 0, 8, 12, 6, 2); De la D: (16, 12, 6, 0, 9, 10); De la E: (7, 6, 3, 9, 0, 4). Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare De la B D E La A 5 16 7 În plus, "distanța" măsurată de B 0 12 6 la C la B, D și E este 6, 3 și 5 C 8 6 3 respectiv. D 12 0 9 E 6 9 0 F 2 10 4 Costurile de la C Prin → B D E Cost Ruta La Min next hop  A 5+6 16 + 3 7+5 11 B B 0+6 12 + 3 6+5 6 B C - - - 0 - D 12 + 6 0+3 9+5 3 D E 6+6 9+3 0+5 5 E F 2+6 10 + 3 4+5 8 B Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Problema numărării la infinit De la A B C D E F G cost 1 pentru orice legatură 1 2 2 3 0 2 3 distanțe inițiale către E ∞ 2 2 3 0 2 3 legătura A – E cade distantele către E anunțate de: A = ∞, B = 2, C = 2 În funcție de ordinea evenimentelor, se pot face modificările: ∞ 3 2 3 0 2 3 B alege ruta prin C, dist=3 B anunță dist. 3 lui A Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Problema numărării la infinit (2) De la A B C D E F G 4 3 2 3 0 2 3 A alege ruta prin B dist=4 A anunța dist. 4 lui C 4 3 5 3 0 2 3 C recalculează dist=5 Distanțele cresc teoretic la infinit Practic, se poate limita la un număr > diametru graf (ex. 16) Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Problema numărării la infinit – soluții (3) split horizon: noile distanțe nu se trimit vecinului prin care trec actualele rute – B are ruta de distanță 2 către E prin A – B nu include noua distanță către E în actualizarea trimisă lui A split horizon with poison reverse: trimite o valoare f. mare – B trimite distanța ∞ către A – A nu va mai alege o cale prin B Neajuns: soluțiile nu funcționează în toate cazurile de ex. pentru bucle cu mai multe noduri Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare RIP - Routing Information Protocol Fiecare legătură are cost 1 Folosește distanțe la rețele (nu la noduri) – ruterul C are distanța 0 la rețeaua 2 și 2 la rețeaua 4 Transmit vectorii distanțelor la fiecare 30 secunde Distanțe maxime de 15 hop-uri (16 înseamnă infinit) – rețele de mici dimensiuni Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Starea legăturii Presupune că fiecare nod poate găsi legăturile cu vecinii și costul fiecărei legături Informațiile sunt diseminate prin inundare tuturor celorlalte noduri – LSP – Link State Packet transmis prin inundare; – Pachetul conține Id-ul nodului care creează pachetul lista nodurilor conectate cu costul fiecărei legături un număr de secvență durata de viață a pachetului (număr) Cu informațiile primite, fiecare nod va calcula rutele cele mai scurte către celelalte noduri Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Transmiterea prin inundare ID și nr. secvență: – nodul are o copie a pachetului sau pachetul este vechi - ignorat; – pachet nou - memorat și retransmis vecinilor (mai puțin vecinului de la care l-a primit) durata de viață: – număr decrementat la fiecare nod (hop) – asigură eliminare pachete vechi Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Algoritmul Dijkstra drumul cel mai scurt nnod numărul nodurilor reţelei; sursa nodul sursă; l[i, j] costul legăturii (i,j), având valorile 0 dacă i = j; ∞ dacă i şi j nu sunt adiacente; D[i] costul minim al legăturii de la sursă la i; S mulțimea nodurilor deja rezolvate; V tabloul de dirijare; V[i] = vecinul prin care se transmit date de la nodul curent la nodul i. Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Dijkstra (sursa) S = {sursa} // noduri rezolvate forall nodes if v adjacent sursa) D[v] = I(v, sursa) else D[v] = ∞ repeat find w not in S such that D[w] is minimum add w to S V[w] = v //update D[v] for all v adjacent to w, not in S D[v] = min(D[v], D[w] + I[v, w]) until S contains all nodes Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare https://www.youtube.com/watch?v=wtdtkJgcYUM Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Alte animații https://www.youtube.com/watch?v=aW9kZcJx64o https://www.youtube.com/shorts/gIrDdYtYHpw https://www.youtube.com/watch?v=pktZ1QOA67s Protocoale de comunicaţie – Curs 4  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Structura ierarhică a Internet-ului Internet-ul este partajat în mai multe domenii numite sisteme autonome AS – Autonomous Systems – ASs sunt rețele independente operate de organizații diferite Într-un AS se folosește același algoritm de rutare “intra- domeniu” – denumit interior gateway protocol – ex. OSPF – Open Shortest Path First Rutarea între AS-uri (între domenii) folosește, de asemenea, un protocol comun – denumit exterior gateway protocol – ex. BGP – Border Gateway Protocol (bazat pe RIP) Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Structura ierarhică AS Fiecare AS este partiționat în mai multe zone (areas) – fiecare zonă reprezentând un grup de rețele – zona Z0 – coloana vertebrală (backbone) – zone “stub” Z1, Z2 … – legate la backbone – rutele între noduri din zone stub diferite trec prin zona Z0 ▪ Ierarhizarea crește scalabilitatea – un ruter dintr-un AS nu trebuie să știe cum se ajunge la fiecare rețea din AS, fiind suficient să știe cum se ajunge la zona în care se află rețeaua respectivă → reduce volumul tabelelor de dirijare AS1 Z0 Z1 Z2 Z3 AS2 Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Structura ierarhica AS (2) Tipuri de rutere ▪ interne unei zone ▪ de coloană vertebrală (backbone) ▪ de graniță zonală (aparțin zonei 0 și zonelor conectate) – nodul încercuit face parte din zonele Z0, Z1, Z2 ▪ de graniță AS AS1 Z0 Z1 Z2 Z3 AS2 Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Mesaje OSPF Mesajele OSPF permit schimbul de informații între noduri Sunt transmise în pachete IP cu 89 ca număr de protocol Hello – stabilește și păstrează legături cu vecinii descoperă nodurile (rutere) cu care este conectat direct Link state request - Cerere stare legătură cere info despre anumite legături de la un alt ruter Link state update - Actualizare stare legătură trimite info despre legături, ca răspuns la o cerere Link state ack - Confirmare stare legătură confirmă primirea unui mesaj de actualizare Database description – trimite LSBD – LInk State Data Base mesajele conțin info despre AS sau zonă Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Calcul rute - Nivel 1 (zonă) Folosind inundarea, fiecare ruter informează celelalte rutere din zonă despre legăturile sale și costurile acestora ▪ ex. informațiile de starea legăturilor schimbate între noduri din Z1 nu se transmit în afara acestei zone! Fiecare ruter (inclusiv cele de graniță zonală) din zonă calculează separat căile cele mai scurte către ruterele din aceeași zonă ▪ în final, ruterul de graniță zonală R va cunoaște căile cele mai scurte către oricare rețea din Z1 și Z2 AS1 Z0 R Z1 Z2 Z3 AS2 Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare Calcul rute - Nivel 2 (AS) Ideea: calea unui pachet între două zone diferite are trei părți: – de a nodul sursa la zona backbone – traversează backbone – de la backbone la rețeaua de destinație Ruterele de coloană vertebrală (backbone) primesc informații de la ruterele de granița zonale și calculează cele mai bune rute la rețele din orice zonă ex. R1 oferă căile cele mai scurte pentru Z1 și Z2 ruterele din Z0 calculează căile către orice rețea din Z1,Z2 Rezultatele sunt difuzate de la Z0 Z0 AS1 înapoi la zonele stub, care actualizează căile cele mai scurte la rețele din alte zone Ex. ruterele din Z2 vor ști să aleagă R1 între R1 și R2 pentru rutare spre R2 Z1 AS2 retele din alte zone Z2 Z3 Protocoale de comunicaţie – Curs 6  Universitatea Politehnica Bucureşti - Facultatea de Automatica si Calculatoare BGP – Border Gateway Protocol Algoritmi orientați pe aspectele politice, de securitate, economice Reţea = ASes şi conexiunile Protocol = vectorul distanțelor Tabelele de dirijare conțin și rutele spre destinație Comunică vecinilor căile utilizate efectiv (ocolește numărătoarea la infinit) Ex. pp. F folosește calea FGCD la D G se defectează Informațiile primite de F de la vecinii ramași, despre D: De la B: “Eu folosesc BCD” De la I: “Eu folosesc IFGCD” De la E: “Eu folosesc EFGCD” F elimină căile care conțin F și alege calea FBCD Protocoale de comunicaţie – Curs 6