Rutarea bazată pe vectorul Rutarea bazată pe vectorul distanţădistanţă -Modificări de -Modificări de topologietopologie

• Fiecare ruter va trimite Fiecare ruter va trimite periodicperiodic propria tabelă propria tabelă de rutere către ruterele de rutere către ruterele adiacente (vecine)adiacente (vecine)..

• În momentul în care apar În momentul în care apar modificări de topologiemodificări de topologie, , ruterele afectate ruterele afectate actualizează propriile actualizează propriile tabele de rutare şi apoi tabele de rutare şi apoi direcţionează direcţionează modificărilemodificările către către ruterele direct ruterele direct conectateconectate..

Cicluri infinite de rutareCicluri infinite de rutare

• Ciclurile infinite de rutare pot Ciclurile infinite de rutare pot apărea în cazul unei slabe apărea în cazul unei slabe convergenţe pe care o poate convergenţe pe care o poate induce apariţia unei noi induce apariţia unei noi configuraţii ce produce informaţii configuraţii ce produce informaţii inconsistente în tabelele de rutareinconsistente în tabelele de rutare

Cicluri infinite de rutareCicluri infinite de rutare

• Înainte de căderea reţelei Înainte de căderea reţelei 1, toate ruterele posedă 1, toate ruterele posedă informaţii corecte de informaţii corecte de rutarerutare.. Reţeaua este Reţeaua este convergentă. Presupunem convergentă. Presupunem în continuare că în continuare că ruta ruta preferată a ruteruluipreferată a ruterului C C către reţeaua 1 se face către reţeaua 1 se face prin ruterul Bprin ruterul B iar vectorul iar vectorul distanţă de la ruterul distanţă de la ruterul C C la la reţeaua reţeaua 1 1 eesstete 3. 3.

Cicluri infinite de rutareCicluri infinite de rutare• Atunci când reţeaua 1 cade,

ruterul E trimite o actualizare către ruterul A.

• În acest moment, ruterul A blochează rutarea pachetelor către reţeaua 1. Totuşi, ruterele B, C şi D pot continua să facă acest lucru deoarece ele nu au fost încă informate despre căderea reţelei.

• Atunci când ruterul A trimite actualizarea, ruterele B şi D blochează rutarea către reţeaua 1.

• Cu toate acestea, ruterul C nu a recepţionat actualizarea. Pentru ruterul C, reţeaua 1 este încă disponibilă prin intermediul ruterului B.

Cicluri infinite de rutareCicluri infinite de rutare• Ruterul C trimite o Ruterul C trimite o

actualizare periodicactualizare periodică către ă către ruterul Druterul D,, indicând o rută indicând o rută către reţeaua 1 prin către reţeaua 1 prin intermediul ruterului B.intermediul ruterului B.

• RuterRuterulul D D îşi modifică tabela îşi modifică tabela de rutare pentru a reflecta de rutare pentru a reflecta această informaţie incorectă această informaţie incorectă transmiţând-o mai departe transmiţând-o mai departe către ruterulcătre ruterul A. A.

• RuterRuterulul A A trimite informaţia trimite informaţia către ruterele B şi Ecătre ruterele B şi E ş.a.m.dş.a.m.d. . Orice pachet destinat reţelei Orice pachet destinat reţelei 11 va produce un ciclu infinit va produce un ciclu infinit de la ruterulde la ruterul C C cătrecătre B B cătrecătre A A cătrecătre D D şi înapoi cătreşi înapoi către C. C.

Cicluri infinite de rutareCicluri infinite de rutare

• Dacă nu se iau alte Dacă nu se iau alte măsuri, acest proces va măsuri, acest proces va continua până în continua până în momentul în care un momentul în care un anumit proces va opri anumit proces va opri această acţiuneaceastă acţiune..

• Acest fenomen se Acest fenomen se numeşte “numeşte “count to count to infinityinfinity””..

SoluSoluţii pentru ciclurile ţii pentru ciclurile infinite infinite –– DefinDefinirea unuiirea unui maximmaxim

• OO soluţie pentru soluţie pentru ciclurile infinite este ciclurile infinite este aceea de a seta o aceea de a seta o valoare maximă pentru valoare maximă pentru o metrică (de exemplu o metrică (de exemplu numărul de hopuri numărul de hopuri <16)<16)

• Dacă vectorul distanţă Dacă vectorul distanţă depăşeşte acest număr depăşeşte acest număr maxim, ruta este maxim, ruta este înlăturatăînlăturată..

SoluSoluţii pentru ciclurile ţii pentru ciclurile infinite infinite –– “ “Split horizonSplit horizon””

• ““Split horizonSplit horizon” specifică ” specifică faptul că nu este faptul că nu este recomandat să se trimită recomandat să se trimită informaţii informaţii catre un catre un rutruterer de de la care a provenit înainte o la care a provenit înainte o actualizareactualizare..

• Atunci când ruterulAtunci când ruterul A A iniţiază o actualizare în iniţiază o actualizare în momentul căderii reţeleimomentul căderii reţelei 1 1, , nici un alt ruter nu poate nici un alt ruter nu poate transmite ruterului transmite ruterului A A că are că are o ruta validă către reţeaua o ruta validă către reţeaua 1.1.

SoluSoluţii pentru ciclurile ţii pentru ciclurile infinite infinite –– “Hold down timers” “Hold down timers”

• Atunci când apare o nouă Atunci când apare o nouă actualizare datorită actualizare datorită căderii unei rute, ruterul căderii unei rute, ruterul porneşte un porneşte un hold-down hold-down timer pentru acea rutătimer pentru acea rută..

• Rutele actualizate cu Rutele actualizate cu metrici mai bune sunt metrici mai bune sunt permise iar rutele cu o permise iar rutele cu o valoare mai mare a valoare mai mare a metricii sunt ignorate în metricii sunt ignorate în timpul acestui “timpul acestui “hold-down hold-down timetime””..

Hold-Down TimersHold-Down Timers

Algoritmi “Algoritmi “Distance VectorDistance Vector””

• BaBazaţi pe algoritmizaţi pe algoritmi• Se atribuie numere Se atribuie numere

“d“distance vectoristance vector” ” fiecărei rutefiecărei rute

• PeriodicPeriodic se se actualizează întreaga actualizează întreaga tabelă de rutaretabelă de rutare

• RuterRuterele actualizeză ele actualizeză doar vecinii direct doar vecinii direct conectaţiconectaţi

• Ciclurile infinite de Ciclurile infinite de rutare sunt cauzate de rutare sunt cauzate de slaba convergenţăslaba convergenţă

• Exemplu de ciclu infinit – Exemplu de ciclu infinit – “c“count to ount to iinfinitynfinity””

• Ciclurile infinite sunt Ciclurile infinite sunt rezolvate prin setarea rezolvate prin setarea unei valori maxime a unei valori maxime a metricii iar cele “splitmetricii iar cele “split horizonhorizon” folosesc” folosesc ““hold-hold-down timersdown timers””

• RIP & IGRP RIP & IGRP sunt exemple sunt exemple de protocoale de rutare de protocoale de rutare ““distance vectordistance vector””

Rutarea link-stateRutarea link-state

• Este cel de-al doilea protocol ca Este cel de-al doilea protocol ca popularitate.popularitate.

• Cunoscut Cunoscut şi sub denumirea de şi sub denumirea de Shortest Shortest Path First (SPF).Path First (SPF).

• Administrează baze de date complexe Administrează baze de date complexe legate de topologia completă a inter-legate de topologia completă a inter-reţeleireţelei..

• Sunt cunoscute informaţii detaliate Sunt cunoscute informaţii detaliate despre rutere, interfeţe şi legăturile ce despre rutere, interfeţe şi legăturile ce conectează aceste interfeţeconectează aceste interfeţe..

Rutarea link-stateRutarea link-state

• Rutarea lRutarea link-state ink-state utilizeazăutilizează::• Popularizări ale stării Popularizări ale stării

legăturilor legăturilor (LSA(LSA - - Link-Link-SState tate AAdvertisements)dvertisements)

• Bază de date a topologieiBază de date a topologiei• Algoritmul Algoritmul SPF SPF precumşi precumşi

arborele arborele SPF SPF rezultatrezultat• O tabelă de rutare ce O tabelă de rutare ce

conţine rute şi porturi conţine rute şi porturi către fiecare reţeacătre fiecare reţea

• OSPF OSPF este un exemplu de este un exemplu de protocol de rutare protocol de rutare Link-Link-state.state.

Rutarea link-stateRutarea link-state• RuterRuterele schimbă între ele ele schimbă între ele

LSALSA-uri-uri (se începe cu (se începe cu vecinii)vecinii)..

• Fiecare ruter Fiecare ruter recepţionează recepţionează LSALSA-uri din -uri din partea tuturor ruterelor, partea tuturor ruterelor, formându-se o bază de formându-se o bază de date şi un arbore date şi un arbore topologic ce conţine drept topologic ce conţine drept rădăcină ruterul însuşirădăcină ruterul însuşi..

• Arborele este format din Arborele este format din toate rutele către fiecare toate rutele către fiecare ruterruter. . Din arbore se Din arbore se selectează cele mai bune selectează cele mai bune rute şi se scriu în tabela rute şi se scriu în tabela de rutare, fiecare ruter de rutare, fiecare ruter acţionând în mod acţionând în mod independent.independent.

Rutarea link-state Rutarea link-state Condiţii de convergenţăCondiţii de convergenţă

• Se ţine cont de toţi veciniiSe ţine cont de toţi vecinii• Se construiesc pachetele Se construiesc pachetele LSALSA• SeSe trimit pachete trimit pachete LSA LSA către toate către toate

rutereleruterele• Se înregistrează pachetele Se înregistrează pachetele LSALSA

primite în baza de dateprimite în baza de date• Se obţine o hartă completă a inter-Se obţine o hartă completă a inter-

reţeleireţelei

Rutarea link-stateRutarea link-stateProblemeProbleme

• Cerinţe de pCerinţe de procesorrocesor şi şi memoriememorie– Cerinţele de memorie ale Cerinţele de memorie ale

ruterului sunt mai mari ruterului sunt mai mari decât în cazul decât în cazul Distance Distance VectorVector

– Trebuie stocate în memorie Trebuie stocate în memorie baza de date şi informaţiile baza de date şi informaţiile legate de arborelegate de arbore

– Algoritmul Algoritmul DijkstraDijkstra pentru pentru SPF SPF necesită o capacitate necesită o capacitate de procesare proporţională de procesare proporţională cu numărul de legături cu numărul de legături dintre rutere dintre rutere x numx numărul de ărul de rutererutere..

• Cerinţe de bCerinţe de bandwidthandwidth– Lăţimea de bandă Lăţimea de bandă

consumată în timpul consumată în timpul fluxurilor de date fluxurilor de date iniţiale ale protocolului iniţiale ale protocolului link-state link-state îneacă îneacă reţeauareţeaua

– O dată cu asigurarea O dată cu asigurarea convergenţei iniţiale, convergenţei iniţiale, cerinţele de bandwidth cerinţele de bandwidth sunt minimesunt minime..

Rutarea link-stateRutarea link-stateProblemeProbleme

• Cea mai mare Cea mai mare problemă apare în problemă apare în cazul în care nu toate cazul în care nu toate ruterele au aceleaşi ruterele au aceleaşi LSALSA-uri-uri..

• Ruterele conectate la Ruterele conectate la legături mai încete vor legături mai încete vor primi actualizările mai primi actualizările mai târziu decât celelaltetârziu decât celelalte

• Dacă există confuzii în Dacă există confuzii în alegerea informaţiilor alegerea informaţiilor LSALSA pot apărea pot apărea disfuncţionalităţi în disfuncţionalităţi în reţeareţea..

Compararea rutării link-state Compararea rutării link-state cu cea distance vectorcu cea distance vector

Rutarea hibridă Rutarea hibridă (balansată)(balansată)

• Alege avantajele din Alege avantajele din ambele metode ambele metode Distance Vector Distance Vector şişi LLink-ink-SStatetate

• Alege rute pe baza Alege rute pe baza vectorilor distanţăvectorilor distanţă

• ConvergeConverge rapid prin rapid prin utilizarea actualizărilor utilizarea actualizărilor apărute în urma apărute în urma modificărilor modificărilor topologicetopologice

• Exemple: Exemple: EIGRPEIGRP (Cisco (Cisco Systems)Systems) şişi IS-IS IS-IS ( (OSIOSI))

Rutarea Rutarea LAN-LANLAN-LAN

Rutarea Rutarea LAN-WANLAN-WAN

Selecţia drumului de la sursă la Selecţia drumului de la sursă la destinaţie şi comutarea între destinaţie şi comutarea între diferite protocoale şi medii de diferite protocoale şi medii de comunicaţiecomunicaţie