2 cucubogdan rutare 2

7/24/2019 2 CucuBogdan Rutare 2

1/17

Tema Retele de Calculatoare-Algoritmi de rutare

Universitatea Politehnica Bucuresti

Facultatea de Electronica, Telecomunicatii si Tehnologia Informatiei

Algoritmi de rutare cu implicatii in

protocoale de rutare

Student: Cucu Bogdan-CristianGrupa: 442A

2014-2015 Pag 1


2/17


Cuprins:

1. Introducere

2. Caracteristicile algoritmilor de rutare3. Metrici ale algoritmilor de rutare

4. Clasificarea algoritmilor de rutare

. !re"entarea algoritmilor de rutare

#. $utarea in retele ad-%oc

&. Comparatie intre algoritmii de rutare

'. Conclu"ii

(. Bi)liografie

2014-2015 Pag 2


3/17


1. Introducere despre rutare

Scopul algoritmilor de rutare1

!rin rutare se intelege procesul de selectare a caii optime pe care se

transmite pac%etul de la sursa la destinatie in interiorul unei retele sau intre

doua retele diferite.

$utarea este utili"ata in cadrul mai multor tipuri de retele: retea

telefonica*comutarea de circuite+, retele electronice de date*Internet+ si retele

de transport.In retelele cu comutatie de pac%ete, fiecare pac%et este rutat cu autorul unor

noduri numite centre de comutatie pana la destinatie, fiecare pac%et fiind

tratat independent.

Aceste centre de comutatie pot fi: rutere, punti*)ridges/+,

porti*gate0as/+, fire0all-uri sau s0itc%-uri.

$utarea presupune eistenta unei ta)ele de rutare, care mentine o eidenta a

rutelor catre diferite destinatii.

a)ela de rutare contine urmatoarele campuri:

-Adresa retea*net address+5

- Masca retea*netmas6+5- Adresa ruterului urmator*net %op+5- Adresa interfetei de iesire*optional+.

Intr-un sens mai ingust al termenului de rutare/, acesta intra in opo"itie cu

notiunea de )ridging/ presupunand ca adresele similare de retea apartin de

aceeasi retea.

In "ilele noastre, rutarea a deenit forma dominanta de adresare in Internet.

Bridging-ul a ramas totusi destul de larg utili"at in cadrul unor medii locale.

1 http://www.inoretele.com/tag/ta!ela-rutare/

2014-2015 Pag "


4/17


2.Caracteristici algoritmi de rutare

Algoritmii de rutare tre)uie sa pre"inte urmatoarele caracteristici2:

- Robustete: functionare corecta in situatii diferite5- Optimalitate: gasirea rutei optime5- Corectitudine: rutarea tre)uie sa asigure ca pac%etele aung la

destinatia lor corecta5

- Adaptabilitate: gasirea unor rute alternatie in ca"ul caderii uneilegaturi5

- Stabilitatea5- Convergenta: algoritmul tre)uie sa calcule"e corect ta)ela de rutare,

deoarece pe durata timpului de conergenta se pot propaga in retea

informatii incorecte priind rutele5

- Incarcare balansataa retelei: se or eita congestia si legaturile incete- Complexitatea cat mai redusa: pentru a se reduce costurile

implementarii %ard0are pe rutere.

- Simplitatea: oer%ead-ul*informatia redundanta+ tre)uie sa fie cat mairedus.

2http://thor.ino.uaic.ro/#adria/teach/cour$e$/net/%le$/&rc'RutareConge$tie.pd

2014-2015 Pag 4


5/17


3.Metrici ale algoritmilor de rutare

a)elele de rutare contin informatia folosita de soft0are-ul de rutare pentrudeterminarea caii optime. 7ista mai multe tipuri de metrici ce sunt utili"ate

de catre algoritmii de rutare. Algoritmii de diriare mai sofisticati pot selecta

ruta optima cu autorul mai multor metrici, com)inate su) forma unei

metrici %i)ride. 3

7emple de metrici sunt:

- 8ungimea caii5- 9ia)ilitatea5- Intar"ierea5

- 8atimea de )anda necesara5- Incarcarea5- Costul datorat comunicatiei.

8ungimea caii este cel mai important criteriu. nele protocoale de

rutare permit administratorilor sa asigne"e costuri ar)itrare fiecarei

legaturi din retea. In aceasta situatie, lungimea caii deine suma

costurilor asociate cu fiecare legatura traersata. Alte protocoale

presupun contori"area numarului de %op-uri, adica numarul de rutere

traersate pana la destinatie.

9ia)ilitatea. In contetul algoritmilor de diriare, fia)ilitatea se refera

la un )it error rate *B7$+ cat mai sca"ut pe fiecare legatura.

Intar"ierea se refera la timpul necesar ca un pac%et sa aunga de la

sursa la destinatie. ;epinde de mai multi factori, printre care latimea

de )anda a legaturilor intermediare, precum si distanta fi"ica.

Incarcarea repre"inta gradul de utili"are a unui ec%ipament de retea,

cum este ruterul. Incarcarea tine cont de mai multi factori, inclu"andutili"area C! si numarul de pac%ete procesate pe secunda.

8atimea de )anda se refera la capacitatea unei legaturi.

" http://docwi(i.ci$co.com/wi(i/Routing')a$ic$

2014-2015 Pag 5


6/17


4.Clasificarea algoritmilor de rutare4

Algoritmii de rutare se pot clasifica dupa cum urmea"a:

Algoritmi de rutare glo)ali: care presupun cunoasterea intregii retele,

toate coneiunile si costurile asociate fiecarei legaturi. Algoritmi de rutare descentrali"ati: initial fiecare nod cunoaste doar

legaturile cu ecinii sai. 8a sc%im)area ta)elei de rutare au loc calcule

iteratie.

< alta clasificare imparte algoritmii de diriare in:

=eadaptii*statici+: rutele sunt configurate manual si sunt usor de

implementat in retele de mici dimensiuni. Ca de"aantae: nu sunt

fe"a)ili decat pentru retele de mici dimensiuni5 pe masura ce

compleitatea retelei creste, gestionarea ta)elei de rutare se doedeste

a fi consumatoare de timp . In plus, daca o legatura cade, nu se poatesta)ili o ruta alternatia.

o S%ortest !at% Algorit%m*Algoritmul de diriare cu cea mai

scurta cale+

o 9looding*Inundare+

Adaptii*dinamici+: in general, rutarea dinamica nu depinde de

dimensiunea retelei si se adaptea"a automat cu sc%im)arile de

topologie a retelei. Ca de"aanta, acest tip de rutare ofera mai putina

siguranta.

o ;istance >ector $outing*Algoritm de diriare cu ector

distanta+

o 8in6 State $outing*$utarea folosind starea legaturii+

o ?ierarc%ical $outing*$utarea ierar%ica+

< su)clasificare a algoritmilor dinamici iii imparte in algoritmi cu rutare de

tip:

- Broadcast*;ifu"iune+- Multicast*rimitere multipla+

5. Prezentarea algoritmilor

4 Andre0 anen)aum @ $etele de calculatoare editia I>, 7d. B)los 23

2014-2015 Pag *


7/17


Algoritmi statici5

Shortest Path outing

8egaturile dintre rutere au un cost asociat. Acesta poate fi o functie de

distanta, latime de )anda, trafic mediu, cost al comunicatiei, intar"iere,

ite"a de procesare a ruterului, etc.

Algoritmul S%ortest !at% cauta sa gaseasca cea mai putin costisitoare cale

prin retea, pe )a"a unei functii de cost.

Algoritmul lui ;i6stra este un astfel de eemplu. 9olosind algoritmul lui

;i6stra se poate determina drumul de cost minim. Algoritmul este utili"at in

protocolul !SP".

Se etic%etea"a fiecare nod, etic%eta repre"entand distanta de la nodul sursapana la nodul destinatie. Initial, deoarece nu este cunoscuta o cale, toate

nodurile or aea etic%eta infinit. In decursul eecutiei algoritmului, noi cai

sunt descoperite si se actuali"ea"a etic%etele. 7tic%eta pot fi de doua tipuri:

permanenta si temporara. 8a inceput, toate sunt temporare. < etic%eta deine

permanenta in momentul in care s-a determinat ruta optima.

"looding#Inundare$

9looding/ este un algoritm de rutare simplu in care fiecare pac%et

receptionat de un ruter este trimis prin fiecare legatura mai putin cea de la

care a fost receptionat. Astfel, fiecare mesa este lirat catre toate nodurile

retelei. 7ista mai multe ariante ale acestui algoritm.

5 Andre0 anen)aum @ Computer =et0or6s editia >, 7d. !rentice ?all

211

2014-2015 Pag +


8/17


Sursa:

%ttp:000.iarcce.comupload213octo)er1'-o-$a%ulD;esai-98, 7d. !rentice ?all

211

2014-2015 Pag &


9/17


- ;escoperirea ecinilor, prin trimiterea unui pac%et E?788


10/17


ote$/c$+1-note$-02".html

Tabela derutare a

nodului..

Distanta(ostul! catre nodul..

" B D E F #

" 1 1 2 1 1 2

B 1 1 2 2 2 3

1 1 1 2 2 2

D 2 2 1 3 2 1

E 1 2 2 3 2 3

F 1 2 2 2 2 1

# 2 3 2 1 3 1

Sursa: %ttp:000.cs.)u.edufac)erscourses&(19((scri)eDnotescs&(1-

notes-(((23.%tml

!e scurt, modul de functionare consta din urmatorii pasi':

- 9iecare nod calculea"a distanta dintre el insusi si toate nodurile dinretea si stoc%ea"a informatia in ta)ela proprie de rutare5

- 9iecare nod trimite ta)ela sa de rutare nodurilor ecine5- Cand un nod primeste ta)ela cu distante de la ecinii sai, calculea"a

cea mai scurta ruta catre toate nodurile si isi actuali"ea"a ta)ela.;e"aantaele acestui algoritm sunt urmatoarele:

- =u este scala)il5

& Andre0 anen)aum @ Computer =et0or6s editia >, 7d. !rentice ?all

211

2014-2015 Pag 10


11/17


- ;aca topologia se modifica, timpul de conergenta este destul demare, fapt ce se a reflecta in informatii eronate priind topologia

retelei 5

- !ro)lema numararii la infinit: daca un nodo legatura cade lasand

astfel un nod i"olat, atunci celelalte noduri or cauta sa determine rutaoptima si a dura destul de mult pana cand rutele neia)ile or fi

eliminate.

Algoritmul mai este utili"at si in cadrul protocolului derutare *ael, care

este un algoritm eficient si ro)ust atat in retelele ca)late, cat si in cele

0ireless cu topologie de tip mes%(.

utarea ierarhica1/

;aca retelele sunt de dimensiuni mari atunci nu este ia)il a utili"a ta)ele de

rutare de dimensiuni mari, din ratiuni ce tin de memoria necesara, timpul

cautarii, si timpul de calcul. Solutia consta in ierar%i"are.

Ideea acestui algoritm consta in a incloui = intrari in ta)ela de rutare cu =

rutere cu o singura intrare pentru un cluster de = rutere. ;e"aantaul este

dat de faptul ca nu a mai eista notiunea de ruta optimala pentru fiecare

ruter.

Algoritmul cu actualizare difuzata (0A%#(iffusing 0pdate Algorithm$11

Algoritmul de rutare ;A8*;iffusing pdate Algorit%m+ este un algoritm

de rutare implementat in cadrul protocolului CISC! I-P, protocol ce

utili"ea"a algoritm ;> *ector distanta+.

!rotocolul 7IG$! utili"ea"a o conditie de test pentru a se asigura ca or fi

selectate doar rutele care nu contin )ucle.In situatia cand nu se gaseste nicio

ruta catre destinatie, algoritmul ;A8 face apel la algoritmul Bellman-9orm

pentru a o)tine o ruta.

tili"ea"a trei ta)ele separate pentru calculul rutei, com)inand informatiile

ruterelor 7IG$!. Spre deose)ire de protocoalele de rutare )a"ate pe starea

http$://tool$.iet.org/html/rc*12*10 http://www.c$e.iit(.ac.in/u$er$/dheera/c$425/lec12.html/11 Ci$co 3RP ocial white paper 6ep 0 2005

2014-2015 Pag 11


12/17


legaturilor*8in6 State $outing+, la 7IG$! informatiile cuprind: rute, metrici

de cost pentru fiecare ruta in parte, timer-e.

a)elea de ecini.

Contine informatii despre nodurile ecine, fiecare linie repre"entand un

ecin, cu descrierea aferenta a interfetei de retea si a adresei. Mai esteprea"ut si un timer care se declansea"a periodic pentru a testa daca o

coneiune este in continuare ia)ila.

a)ela de topologie.

Cuprinde informatii despre costul tuturor rutelor din cadrul sistemului

autonom. Informatiile sunt preluate din ta)elele ruterelor ecine. $utele

primara*succesor+ si secundara*fe"a)ila+ or fi determinate cu autorul

cunoasterii topologiei. Campurile continute in aceasta ta)ela sunt:

9;*;istanta fe"a)ila+ , repre"inta metrica calculata a unei rute catre nodul

destinatie, $;*;istanta raportata+ repre"inta distanta catre destinatie

conform cu informatiile de la nodurile ecine, Starea $utei*$outeStatus+,indicand daca o ruta este actia sau pasia. < ruta actia este o ruta care nu

este disponi)ila si este in proces de re-calculare. < ruta pasia este o ruta

care poate fi folosita, fiind considerata sta)ila.

a)ela de rutare. Contine informatii priind ruta optima din punct de edere

al costului minim. Caile optime sunt date de succesorii din ta)ela de

topologie.

Astfel, algoritmul ;A8 calculea"a pe )a"a datelor primite de la nodurile

ecine rutele primare*succesor+ si pe cele fe"a)ile,

utarea de tip roadcast

In ca"ul acestui tip de rutare, se rutea"a un pac%et de la sursa catre toate

nodurile din retea. !osi)ile implementari sunt : 9looding-ul si protocolul

Spanning ree outing. ;e"aantaele sunt date de eistenta pac%etelor

duplicat si consumul de latime da )anda. n eemplu de utili"are este

streaming-ul multimedia.

utarea de tip Multicast

!rin intermediul acestui tip de rutare se incearca marirea eficientei fata de

unicast, dar fara a facilita accesul la informatie oricui. Ca mod de

functionare, ruterul interog%ea"a nodurile ga"da apartinand unui anumit

grup. Se trimit apoi pac%etele catre rutere.

2014-2015 Pag 12


13/17


utarea in retele ad+hoc12

n protocol de rutare de tip ad-%oc repre"inta un standard care controlea"a

modul in care un nod decide pe care ruta or fi transmise pac%etele intr-o

retea mo)ila de tip ad-%oc.

9iecare nod este conectat la retea 0ireless si actionea"a atat ca un

%ost*ga"da+, cat si ca un ruter. $etelele de noduri care se afla langa orice alt

nod se numesc retele de tip ad+hoc/ sau MA*Mo)ile Ad %oc

=70or6s+.In retelele ad-%oc, nodurile nu cunosc topoloogia retelei din care fac parte.

$uterele tre)uie sa inete topologia , astfel: un nod isi anunta pre"enta si

asculta mesaele de tip )roadcast de la celelalte rutere.

Au fost propusi mai multi algoritmi de rutare pentru retelele ad %oc, unul

dintre cei mai populari fiind algoritmul A*Ad %oc ector+, propus de catre !er6ins si $oer in 1(((. 7ste de fapt o ersiune a

algoritmului ;istance modificata pentru a opera in medii mo)ile in care

nodurile au )anda limitata sau o durata de iata dictata de nielul )ateriei.

Algoritmul A!()13

Algoritmul A cauta rute la cerere, cand un nod sursa doreste sa trimita

pac%ete. tili"ea"a numere de secenta pentru identificarea celei mai recente

cai. =odul sursa si nodurile intermediare pastrea"a informatii despre

urmatorul nod din retea*net-%op+ corespun"ator fiecarui flu de pac%ete de

date trimise. Intr-un protocol de rutare de tip on-demand*de rutare la cerere+

nodul sursa trimite pac%ete de cerere a rutei *$oute$eHuest+ su) forma unui

flood atunci cand nu se cunoaste o ruta catre nodul destinatie. ;intr-o astfel

de cerere de o)tinere a rutei poate descoperi c%iar mai multe rute .

;esoe)irea dintre A si alti algoritmi care cauta rute la cerere consta in

12Andre0 anen)aum @ Computer =et0or6s editia >, 7d. !rentice ?all 211

1"!er6ins, C.5 Belding-$oer, 7.5 ;as, S. *ul 23+.Ad hoc On-Demand Distance Vector(AODV Routing.I79. $9C 3#1. $etrieed 21-#-1'.

2014-2015 Pag 1"
https://tools.ietf.org/html/rfc3561https://tools.ietf.org/html/rfc3561https://tools.ietf.org/html/rfc3561https://tools.ietf.org/html/rfc3561http://en.wikipedia.org/wiki/Internet_Engineering_Task_Forcehttp://en.wikipedia.org/wiki/Internet_Engineering_Task_Forcehttps://tools.ietf.org/html/rfc3561https://tools.ietf.org/html/rfc3561


14/17


utili"area numarului de secenta ;estSeH=um. Astfel, un nod isi

actuali"ea"ata)ele de rutare doar daca numarul de secenta al pac%etului

curent receptionat este mai mare decat aloarea stocata.

Cererea de aflare a rutei*$oute$eHuest+ contine urmatoarele campuri:

- SrcI;, numarul de identificare al nodului sursa5- ;estI;, numarul de identificare al nodului destinatie5- SrcSeH=um, numarul de secenta al nodului sursa5- ;estSeH=um, numarul de secenta al nodului destinatie5- BcastId, identificator de )roadcast5- 8, timp de iata.

Aantaul maor al acestui algoritm consta in faptul ca rutele se sta)ilesc la

cerere si ca utili"area numerelor de secenta la destinatie permit aflarea celei

mai recente rute, ruta optima. impul de sta)ilire al coneiunii este sca"ut.

;e"aantaul este ca nodurile intermediare pot duce la rute inconsistentedaca numarul de secenta al rutei este ec%i, iar nodurile intermediare

poseda o aloare mai mare, dar nu actuali"ata.

2014-2015 Pag 14


15/17


'.Comparatie intre algoritmii de rutare

Scopul oricarui algoritm de rutare este simplu, gasirea celei mai )une

cai de transmitere a pac%etelor de la sursa la destinatie. Intrucat fiecare retea

are reguli diferite, procesul de rutare nu este tot simplu. 9iecare legatura are

asociat un cost, cost ce se traduce prin distanta fi"ica.

In continuare se compara algoritmii : 8in6 State $otuting si ;istance >ector.

Compleitatea mesaului in ca"ul 8S*8in6 State+ este mult mai mare,

intrucat 8S tre)uie sa transmita costul fiecarei legaturi catre toate nodurile,

pe cand ;> *;istance >ector+ comunica doar cu ecinii sai si doar in situatiain care au loc modificari in ta)ela de rutare. !e de alta parte, pentru ;>,

timpul de conergenta este mare si se poate aunge la pro)lema numararii la

infinit.

In ceea ce prieste ro)ustetea algoritmului, 8S sta mai )ine din acest punct

de edere intrucat a face )roadcast numai pentru sc%im)arile asupra unui

singur nod. ;>, spre deose)ire, a tre)ui sa auste"e toti ectorii distanta

catre toate nodurile, intr-un anumit numar de iteratii.

2014-2015 Pag 15


16/17


. Concluzii

In conclu"ie, desi scopul algoritmilor de rutarediriare este unul

simplu si anume aflarea caii optime de trimitere a pac%etelor de la un nod la

altul, procesul de rutare nu este unul simplu, deoarece tre)uie sa se tina cont

de o serie de criterii si cerinte. re)uie determinata ruta cea mai ieftina/ ,

insa retele diferite au reguli diferite.

Algoritmii pot fi statici cand sunt cunoscute topologia si capacitatea

legaturilor, sau dinamici, cand ruterele iau deci"iile pe )a"a informatiilor

adunate, gasind rute alternatie.

Asadar, rutarea este o functie c%eie a nielului $etea/ o)iectiul fiind dat

de gasirea rutei optime.

2014-2015 Pag 1*


17/17


. *iliografie

J1K%ttp:000.inforetele.comtagta)ela-rutare

J2K%ttp:t%or.info.uaic.roLadriateac%coursesnetfiles'rcD$utareCongestie

.pdf

J3K-%ttp:doc0i6i.cisco.com0i6i$outingDBasics

J4K-Andre0 anen)aum @ $etele de calculatoare editia I>, 7d. B)los

23JK-Andre0 anen)aum @ Computer =et0or6s editia >, 7d. !rentice ?all

211

J#K-%ttp:000.iarcce.comupload213octo)er1'-o-$a%ulD;esai-

98

2 cucubogdan rutare 2

Documents