• Activitatea de rutare (dirijare)

Nivelul Retea (II)

Lenuta Alboaie ([email protected]) Andrei Panu ([email protected])

1

Cuprins

• Nivelul retea

• Activitatea de rutare (dirijare)

• Preliminarii

• Caracterizare

• Rutare

• Protocoale de rutare – RIP & OSPF

– BGP & EGP

• Congestie – discutii generale

Rutare|Preliminarii

- Partea software-ului nivelului retea care alege calea pe care un pachet receptionat trebuie trimis pentru a ajunge la destinatie - Daca se folosesc datagrame, decizia de rutare trebuie luata

pentru fiecare pachet

- Daca se utilizeaza circuite virtuale, decizia de rutare se ia la stabilirea unui nou circuit

- Cerintele pentru un algoritm de rutare: corect, simplu, robust, optim, rapid convergent

- Activitati

- Determinarea caii optime de rutare (routing)

- Transportarea pachetelor: comutare (packet switching)

3

Terminologie

- end systems – dispozitive de retea fara capacitati de redirectat pachete catre subretele

- intermediate systems – dispozitive de retea avand capacitati de redirectat pachete

- Intradomain IS – comunicare in cadrul unui domeniu de rutare

- Interdomain IS – comunicare si intre domenii de rutare

- sistem autonom – AS (eng. Autonomous system) – colectie de retele care partajeaza aceeasi strategie de dirijare

Nivelul retea | …sa ne reamintim

• La nivelul retea, Internetul poate fi vazut ca o colectie de subretele sau sisteme autonome conectate intre ele

IP-ul este liantul care face posibila aceasta interconectare. (a se vedea Cursul 2)

• Nivelul retea se ocupa cu trimiterea pachetelor de la sursa la destinatie (mecanism care implica trecerea printr-o serie de noduri intermediare) => nivelul retea este nivelul cel mai de jos care se ocupa cu transmisia end-to-end

Obs.: Nivelul legaturii de date are rolul de transport a frame-urilor de la un punct la altul

5

Nivelul retea| …sa ne reamintim

Comunicare end-to-end intre o gazda client si un server la nivelul retea

Comutare

• O gazda (eng. host) are de trimis un pachet la un alt host

• Host-ul sursa trimite pachetul la un router, folosind adresa hardware (MAC) a acestuia, un pachet continand adresa de retea a gazdei destinatie

• Routerul examineaza adresa de retea a destinatarului, iar daca nu cunoaste unde sa trimita pachetul, il va distruge

• Altfel, va modifica adresa continuta de pachet in adresa hardware a urmatorului hop (punct indermediar de

transmitere – Intermediate System) si va trimite pachetul spre acesta

• Daca urmatorul hop nu este destinatia finala, atunci procesul se repeta pentru un alt router s.a.m.d.

7

Comutare

Procesul de comutare

[Retele de calculatoare –

Rutare

Nivelul retea:

• trebuie sa cunoasca topologia ruterelor si sa aleaga calea pe care un pachet trebuie trimis spre destinatie

• trebuie sa faca alegerea astfel incat sa evite supraincarcarea unor linii de comunicatie si a unor rutere (vezi slide-urile urmatoare)

9

[Computer Networks, 2003 Andrew S. Tanenbaum]

Multimea tuturor ruterelor (engl. communication subnet)

Context pentru protocoalele de la nivelul retea

Determinarea caii optime de rutare

Rutare

• In cazul in care la nivelul retea avem servicii neorientate conexiune, pachetele (numite si datagrame) sunt trimise individual si sunt rutate in mod independent una de alta

Rutare in interiorul unui datagram subnet Algoritmii de rutare

fac managementul tabelelor de rutare

[Computer Networks, 2003 Andrew S. Tanenbaum]

Rutare

• In cazul in care la nivelul retea avem servicii orientate

conexiune se folosesc circuite virtuale si decizia de rutare se ia la stabilirea unui nou circuit

11

Rutare in interiorul

unui virtual-circuit subnet (session routing)

[Computer Networks, 2003 Andrew S. Tanenbaum]

label switching

Rutare

Comparatie intre datagram subnet si virtual-circuit subnet

Rutare

Determinarea caii de rutare

- Pentru fiecare cale de rutare se determina un cost (metrica) - Lungimea caii, siguranta, intarzierea, largimea de banda,

incarcarea, costul comunicarii

- Algoritmii de rutare initializeaza si mentin (pentru fiecare gazda) tabele de rutare continand informatii de dirijare

– Rute catre gazde specificate – Rute spre retele specificate – O ruta implicita

13

Rutare

Un router creeaza o cale logica intre subretele

O aplicatie ruland pe gazda 1.1 nu trebuie sa cunoasca

drumul pentru a trimite date aplicatiei de pe gazda 4.3

[Retele de calculatoare – curs 2007-2008, Sabin Buraga]

Rutare

Algoritmii de rutare - caracteristici:

– Acuratete (engl. Accuracy) – un algoritm trebuie sa opereze in mod corect si rapid pentru gasirea destinatiei

– Complexitate redusa – important pentru rutere cu resurse fizice (soft) limitate

– Optimalitate – abilitatea de a gasi ruta optima

– Robustete – capacitatea de a functiona corect pentru o perioada lunga de timp, in circumstante diferite

– Adaptabilitate – la aparitia unei erori in retea, algoritmul trebuie sa se adapteze (de ex. caderea nodurilor sau coruperea tabelelor de rutare)

– Convergenta – algoritmii de rutare trebuie sa convearga rapid atunci cand sunt distribuite mesaje de rutare de actualizare

– Load balancing – un algoritm de rutare cantareste diferite posibilitati de rutare pentru evitarea legaturilor incete sau a congestiilor ₁₅

Rutare

• Abstractizare – Retea = graf

– Dirijarea= gasirea drumului de cost minim de la un nod sursa la un nod destinatie

Tipuri de rutare:

– Centralizata – drumul de cost minim poate fi determinat avand disponibile toate informatiile despre retea

<– algoritmi folosind starea legaturii

– Descentralizata – drumul de cost minim este determinat in mod iterativ, distribuit (nici un nod nu poseda informatii

complete despre costurile legaturilor din retea) <- algoritmi cu vectori distanta

Rutare

• Rutare folosind starea legaturii

– Topologia retelei & costurile tuturor legaturilor sunt cunoscute

– Un nod trebuie sa cunoasca identitatile & costurile nodurilor vecine

– Fiecare nod difuzeaza prin broadcast identitatile si costurile tuturor legaturilor de la acel nod la altele

17

Rutare

• Rutare cu vectori distanta

– Fiecare nod primeste informatii de la nodurile vecine, realizeaza calcule si distribuie rezultatele inapoi la vecinii directi – algoritmul este distribuit si asincron

– Fiecare nod mentine o tabela de distanta (distance table) – X: nodul dorind sa realizeze o rutare la nodul Y via nodul

vecin Z

– D^x(Y,Z): suma costului legaturii directe intre X si Z (c(X,Z)) plus costul curent al drumului minim de la vecinii lui Z la Y:

D^x(Y,Z)=c(X,Z) + min_w{D^z(Y,w)}

– Tabela de rutare a unui nod poate fi construita cunoscand tabela de distanta a nodului

Rutare

Algoritmii de rutare – clasificare:

• Statici (neadaptivi)

– Topologia legaturilor se incarca pentru o perioada de timp in tabelele de rutare a fiecarui nod

– Dezavantaje:

• Reteaua trebuie sa aiba o dimensiune optima pentru a putea fi controlabila

• Daca au loc esuari in retea, nu se poate reactiona imediat

• Dinamici (adaptivi)

– Starea retelei este “invatata” din comunicarea ruterelor cu vecinii lor; starea fiecarei regiuni din retea este propagata in retea dupa ce toate nodurile isi actualizaza tabelele de rutare

=> fiecare ruter poate gasi calea cea mai buna pe baza

informatiilor de la nodurile vecine ¹⁹

Rutare

Algoritmii de rutare – clasificare:

• Statici (neadaptivi)

– Dirijare pe calea cea mai scurta – Inundare (eng. flooding)

– Deflecting routing (sau hot-potato routing)

• Dinamici (adaptivi) – Cu vectori distanta

– Folosind starea legaturilor – Dirijare ierarhica

– Prin difuziune (broadcast)

– Cu trimitere multipla (multicast)

Rutare

Algoritmii de rutare – clasificare:

• Statici (neadaptivi)

– Dirijare pe calea cea mai scurta (eng. Shortest path routing)

Algoritmul lui Dijkstra (calculeaza drumul de cost minim)

• Este folosit de protocolul OSPF

21

“shortest path”: nr. de hopuri => ABC si ABE sunt egale

Alte metrici posibile: distanta geografica, largimea de banda, costuri de comunicare etc.

Rutare

Algoritmii de rutare – clasificare:

• Statici (neadaptivi)

– Inundare (eng. flooding)

• Un pachet primit este copiat si transmis prin toate legaturile de comunicare (exceptand cea pe unde a venit)

• Problema: packet reflection (un nod poate primi o copie nedorita a unui pachet)

• Utilizari ale algoritmilor de tip flooding: aplicatii militare, baze de date distribuite etc.

Rutare

Algoritmii de rutare – clasificare:

• Statici (neadaptivi) – Deflection routing

• La fiecare pas un pachet este examinat in raport cu adresa destinatie; daca legatura ceruta este libera pachetul este trimis, altfel este deviat (deflected) catre o alta linie de comunicare aleasa aleator;

• Un pachet are asociat un camp cu o valoare de prioritate care il poate ajuta pe viitor sa castige disputa cu alte

pachete

23

Rutare

Algoritmii de rutare – clasificare:

• Dinamici (adaptivi) – Cu vectori distanta

• Fiecare router mentine un tabel (vector) cu distanta si linia de comunicare catre destinatie; tabelele sunt

actualizate cu informatiile de la vecini Algoritmul Bellman-Ford

• Algoritm folosit de protocoalele RIP, BGP, IGRP Exemplu:

– Consideram ca metrica: intarzierea (msec);

– Routerele vor sti intarzierile asociate vecinilor sai

Rutare

Algoritmii de rutare – clasificare:

• Dinamici (adaptivi)

– Cu vectori distanta

25

J doreste sa calculeze ruta catre G J->A->G = 26 (18+8) msec

……

J->H->G 18 msec Exemplu:

[Computer Networks, 2003 Andrew S. Tanenbaum]

Rutare

Problema: conform algoritmului cu vectori distanta, la fiecare actualizare a rutelor, tabelele de rutare trebuie trimise fiecarui vecin; unele pachete cu informatii

legate de dirijare trec pe ruta de pe care deja au venit (reverse route)

Intrebare: Pot fi evitate rutele de tip reverse?

Raspuns: utilizarea tehnicii split horizon

- Cand router-ul trimite actualizari de rute folosind o anumita interfata de retea, ele nu vor fi expediate

retelelor ale caror rute au fost invatate din actualizari

primite via acea interfata

Rutare

Problema:

Modificarea topologiei (deprecierea convergentei algoritmilor de rutare)

27

[Retele de calculatoare – curs 2007-2008, Sabin Buraga]

Rutare

Algoritmii de rutare – clasificare:

• Dinamici (adaptivi)

– Folosind starea legaturilor Fiecare router trebuie sa:

– Descopere vecinii si sa le “invete” adresele de retea – Masoare intarzierea sau costul asociat fiecarui vecin

– Construiasca un pachet prin care anunta pe “toti” ceea ce a invatat

Dilema: cand trebuie construite pachetele? (de ex.

periodic sau cand apare un eveniment special) – Trimita pachetul

– Calculeze cea mai scurta cale catre fiecare router

Rutare

Algoritmii de rutare – clasificare:

• Dinamici (adaptivi) – Dirijare ierarhica

Necesitate: in retele de mari dimensiuni nu este fezabil ca un router sa aiba cate o intrare despre fiecare alt router;

Mecanism: Ruterele stiu detalii asociate unei regiuni , dar nu stiu detalii despre structura interna a altor regiuni

Obs.:

– Pentru retele de dimensiuni mari, ierarhia de nivel 2 nu este

suficienta si atunci regiunile se grupeaza in clustere, clusterele in zone, zonele in grupuri etc.

– Care este numarul optim de niveluri?

Pentru un subnet cu N routere numarul optim ln N [Kamoun&Kleinrock, 1979]

29

Rutare

Algoritmii de rutare – clasificare:

• Dinamici (adaptivi)

– Prin difuziune (broadcast routing)

Utilizare: actualizarea stocurilor (de la bursa de valori), streaming multimedia, serviciu de distribuire a

rapoartelor despre vreme etc.

Modalitati:

– Sursa trimite cate un pachet distinct fiecarui destinatar Obs.: Metoda ineficienta: neutilizarea latimii de banda;

Sursa trebuie sa aiba adresele tuturor destinatarilor – Flooding - util cand alte metode nu pot fi aplicate

Problema: Se genereaza prea multe pachete si se consuma multa latime de banda

Rutare

Algoritmii de rutare – clasificare:

• Dinamici (adaptivi)

– Cu trimitere multipla (multicast routing) Exemplu de utilizare:

Un proces doreste sa transmita un mesaj unui grup de procese implementand un sistem de baze de date distribuite

Obs.: Se poate face broadcast, insa uneori informatia nu este destinata a fi vazuta de oricine

Mecanism: router-ul va face periodic o interogare asupra host-urilor care apartin unui grup; apoi informatia este propagata catre routere

31

Rutare

Exemplu:

Exemplu: Pentru destinatia 172.17.17.0 routerul (gateway-ul) folosit este 172.17.17.1 ; Gateway = 0.0.0.0 -> interfata de retea locala

Flag-uri: U(up) – ruta este operationala; H - indica o ruta catre o anumita gazda; G - ruta utilizeaza un gateway exterior

Crearea tabelelor de rutare

Rute statice: comanda UNIX route Descoperirea unui router prin ICMP

[http://docstore.mik.ua/orelly/networking_2ndEd/tcp/ch02_04.htm]

Rutare

Protocoale de rutare - clasificare

- Intradomain routing protocol – realizeaza rutarea pachetelor intr-un domeniu

– RIP (Routing Information Protocol) – OSPF (Open Shortest Path First)

– Interdomain routing protocol – realizeaza rutarea pachetelor intre domenii

– BGP (Border Gateway Protocol) - EGP (Exterior Gateway Protocol)

- RFC 827, 904

- nu mai este utilizat, fiind inlocuit de BGP

33

Rutare

RIP (Routing Information Protocol)

• RFC 1058, 1723

• Mecanismul de functionare:

– Se aplica algoritmul Bellman-Ford (pentru host-uri si routere)

– Pentru fiecare router, se creeaza un vector continand costul rutei si alte informatii

– Daca survin modificari intr-un punct, acestea sunt

propagate periodic la routerele si host-urile vecine cu acel punct

Rutare

RIP (Routing Information Protocol)

• Foloseste mesaje IP

• Fiecare router trimite un broadcast continand intreaga tabela de rutare a router-ului – la fiecare 30 sec.

• O intrare a tabelei de rutare RIP contine:

– Adresa IP

– Metrica (numarul de hop-uri: 1-15) – Timeout (in secunde)

• Retelele conectate direct au metrica =1 (un hop)

• Daca o ruta da timeout, metrica devine 16 (nu exista conexiune) si ruta e stearsa dupa 1 minut

35

Tabela de rutare A: nodul B e la 1 hop distanta (conexiune directa), nodul C la 2 hop-uri

Rutare

RIP (Routing Information Protocol)

• Daca o informatie de rutare se modifica (de ex. o legatura sau un router esueaza), propagarea acestei schimbari are loc

foarte lent – RIP sufera de convergenta lenta

• RIP

– Este un protocol matur, stabil, larg suportat si usor de implementat

– Este indicat a fi folosit de sistemele autonome de dimensiuni reduse fara rute redundante

– In practica este inlocuit in majoritatea situatiilor de OSPF

Rutare

OSPF (Open Shortest Path First)

• RFC 1247, 2328

• Fiecare router ce foloseste OSPF cunoaste starea intregii topologii de retea (algoritm folosind starea legaturii) si transmite actualizari la toate routerele

• Conduce la trafic aditional, care poate conduce la congestii OSPF permite ca traficul sa fie distribuit pe rute cu costuri similare (load balancing)

OSPF suporta rutarea dupa tipul serviciilor (ToS)

– protocolul IP contine campul ToS (in general neutilizat)

• Convergenta mai rapida

• Ofera suport pentru folosirea mai multor tipuri de metrici ₃₇

Rutare

OSPF (Open Shortest Path First)

• Opereaza intr-o ierarhie de entitati de retea

Motivatie: retele de dimensiuni mari => un router nu poate cunoaste intreaga topologie

– Sistemul autonom (AS) – colectie de retele care partajeaza aceeasi strategie de dirijare

– Un AS este divizat in domenii (engl. areas) – grupuri contigue de retele si gazde; routerele au aceeasi informatie privitoare la topologie si ruleaza acelasi algoritm

– Coloana vertebrala (backbone sau area 0) – responsabila cu distributia informatiilor de rutare intre domenii; orice router conectat la doua sau mai multe domenii face parte din

backbone (aceste routere vor rula algoritmi corespunzatori pt

Rutare

OSPF (Open Shortest Path First)

39

Un AS si

domeniile sale

conectate via routere

[Retele de calculatoare –

Rutare

OSPF (Open Shortest Path First) Tipuri de mesaje OSPF:

• Cu un mesaj “hello” un router isi afla vecinii (de ex. toate routerele din LAN)

• Fiecare router face flood periodic cu un mesaj (ce are asociat un numar de secventa) de tipul Link state update; la aceste mesaje se fac confirmari Link state ack

• Database description furnizeaza numerele de secventa asociate

Rutare

41

BGP (Border Gateway Protocol)

[Retele de calculatoare – curs 2007-2008, Sabin Buraga]

Rutare

BGP (Border Gateway Protocol)

• Utilizat pentru comunicarea intre routere aflate in sisteme autonome diferite

• Functii majore:

• Neighbor relationship – se refera la acordul dintre routerele din doua sisteme autonome de a schimba informatii pe baza unor reguli (un router poate refuza stabilirea unei astfel de relatii in functie de: regulile domeniului, supraincarcare etc)

• Neighbor maintenance – routerele isi vor trimite mesaje de tip keep-alive

• Network maintenance – fiecare router tine o baza de date cu subretelele existente pentru o rutare eficienta in acea subretea

Rutare

43

BGP (Border Gateway Protocol)

• Exista patru tipuri de pachete BGP:

• Open: folosit pentru stabilirea unei relatii dintre doua routere

• Update: contine informatii actualizate despre rute

• Keep-alive: folosit pentru confirmarea de relatii stabilite anterior

• Notification: folosit atunci cand apar erori

• Perechile de routere BGP comunica intre ele folosind conexiuni TCP

• BGP este un protocol bazat pe vectori distanta cu urmatoarele diferente:

• nu se pastreaza doar costul asociat unei destinatii, ci se mentine si calea catre acea destinatie

• nu se furnizeaza vecinilor doar costul estimat, ci si calea exacta

• RFC 1771-1774, 4271

Rutare

Alte protocoale:

- Interior Gateway Routing Protocol (IGRP) - Imbunatatire CISCO a RIP

- Enhanced IGRP (EIGRP)

- Simple Multicast Routing Protocol (SMRP)

- Rutare de fluxuri multimedia la Apple (via AppleTalk)

Obs.: Din 2009 AppleTalk este nesuportat, se utilizeaza TCP/IP

• Resource Reservation Protocol (RSVP) (RFC 2205)

• Nu este un protocol de rutare, dar ofera functionalitati similare

• Asigura calitatea serviciilor IP

Rutare| privire de ansamblu

45

Rutare interna:

• RIP (Routing Information Protocol)

• IGRP (Interior Gateway Routing Protocol)

• EIGRP (Enhanced IGRP )

• OSPF (Open Shortest Path First)

• IS – IS (Intermediate System to Intermediate System) pentru ISO/OSI

• Rutare externa

• BGP (Border Gateway Protocol)

• EGP (Exterior Gateway protocol)

Congestie | Discutii

• Apare atunci cand se realizeaza supraincarcarea resurselor unei retea

In cazul unui trafic foarte mare, se poate instala congestia si performantele scad brusc

Congestie | Discutii

47

Congestia poate aparea:

• La nivelul legaturii de date: cand latimea de banda nu este suficienta

• La nivelul retea: cand coada de pachete de la noduri nu poate fi controlata

• La nivelul transport: cand legatura logica dintre doua rutere aflate intr-o sesiune de comunicare nu mai poate fi controlata

Congestie| Discutii

• Controlul congestiei – solutii

• Open-loop: rezolvarea inseamna de fapt prevenirea aparitiei congestiilor printr-un design si decizii potrivite

• Close-loop

• Monitorizarea sistemului pentru detectarea congestiilor

Metrici: procentul de pachete eliminate datorita lipsei spatiului in buffer, intarzierea pachetelor etc.

• Trimiterea acestei informatii la nodurile care pot lua decizii

• Ajustarea operatiilor pentru corectarea problemei

Congestie| Discutii

49

Obs.:

controlul congestiei != controlul fluxului

• Controlul congestiei asigura faptul ca reteaua are

capacitatea de a transporta traficul oferit; implica actiunile tuturor host-urilor si a routerelor

• Controlul fluxului se ocupa de comunicarea point-to-point dintre un emitator si un receptor si se asigura faptul ca un emitator nu transmite date mai repede decat poate

receptorul sa le proceseze

Rezumat

• Nivelul retea

• Activitatea de rutare (dirijare)

• Preliminarii

• Caracterizare

• Rutare

• Protocoale de rutare – RIP & OSPF

– BGP & EGP

• Congestie – discutii generale

Bibliografie

Content Networking Fundamentals, Silvano Da Ros, Publisher: Cisco Press Pub Date: March 30, 2006 Print ISBN-10: 1-58705-240-7 Print ISBN-13: 978-1- 58705-240-8 Pages: 576

Computer Networks, Andrew S. Tanenbaum, Publisher : Prentice Hall

Computer and Communication Networks, Nader F. Mir, Publisher: Prentice Hall Pub Date: November 02, 2006 Print ISBN-10: 0-13-174799-1 Print ISBN- 13: 978-0-13-174799-9 Pages: 656

http://www.tuxick.net/linux/ip6routing.html

http://www.6diss.org/workshops/see-2/routing-external.pdf http://www.ip6.com/us/book/Chap7.pdf

http://www.nanog.org/meetings/nanog44/presentations/Monday/SmithBonic a_IPv6_N44.pdf

51

Intrebari?