6. Nivelul reţea

Introducere
Serviciu nivel reţea: circuit virtual
Serviciu nivel reţea: datagrame
Funcţia de rutare
Tabela de rutare: probleme
Algoritmul pentru calea cea mai scurtă al lui Dijkstra: definiţii
Rutarea vectorului distanţă
Oscilaţii
Comparare între algoritmii LS şi DV
Rutarea difuzării
Informaţii despre rutarea distribuită
Rutarea spre mai multe staţii
Rutarea multistaţie: Starea legăturii
Rutarea multistaţie: Vectorul distanţă
Gazde şi rutere
Studiu de caz al nivelului reţea: Internetul
Fragmentarea IP şi Reasamblarea
Rutarea intradomeniu a Internetului: RIP
Rutarea intradomeniu a Internetului: OSPF
Rutarea interdomeniu Internet: BGP
ICMP: Protocolul de Control al Mesajului Internet
IPv6: următoarea generaţie IP
Studiu de caz: nivel reţea ATM
Comutatoare şi rutere: introspectivă
Echipamentul de comutare

Introducere

Nivel reţea: aspecte generale:

• nivel transport: între două gazde

• nivel legătură date: între două gazde conectate fizic, rutere

• nivel reţea: implică fiecare ruter în part, gazdă, poartă din reţea

Serviciu nivel reţea: circuit virtual

Virtual, pare un circuit, dar nu este.

În general asociat cu serviciu orientat pe conexiune.e

Toate pachetele din conexiune urmăresc aceeaşi rută.

La timpul de stabilire a conexiunii:

• pachetul de setare a conexiunii trece de la expeditor la destinatar

• tabelele de rutare sunt actualizate în nodurile intermediare pentru a reflecta noile VC

• esenţial: starea la ruter per conexiune

• se potrivesc bine cu garanţiile SC: rezervă resurse şi/sau acceptă/refuză apeluri bazate pe resurse la acest ruter

Analogie: reţeaua telefonică.

Serviciu nivel reţea: datagrame

Nu există o noţiune privind conexiunea în nivelul reţea.

Nu există nicio setare a ruterelor la timpul de stabilire a conexiunii - fiecare pachet "în conexiune" poate urma căi diferite.

Nu exista o garanţie de siguranţă, sau avantajele livrării în ordine.

Avantaje:

• nicio stare de conexiune în rutere

• robust faţă de vulnerabilităţile legăturii

• recuperare la sistemele terminal (nivel transport).

Diferite modele de serviciu:

• cel mai bun serviciu din puctuş de vedere al efirtului: datagramele

• servciul cu performanţe garantate: SC

Funcţia de rutare

Un pachet pentru nivelul reţea conţine:

• pachetul nivelului transport (port, secvenţă, recunpaştere, date, verificare sume, etc)

• informaţii de adresare (de ex., sursa, adresa destinatarului sau identificator VC)

• alte cîmpuri (de ex., versiunea, lungimea, timpul de viaţă)

Ruterul/comutarea acţionează simplu la recepţia pachetului:

• caută identificatorul de pachet (adresa destinatarului sau identificatorul VC) în tabela de rutare şi îl direcţionează către legătura de plecare adecvată (sau în sus dacă într-acolo este destinaţia).

Tabela de rutare: probleme

Probleme de rutare

Scalabilitatea: trebuie să poată suporta numere mari de gazde, rutere, reţele

Se adaptează rapid şi eficient la schimbări în topologie sau modificări semnificative în trafic.

Selecţia rutei poate depinde de diferite criterii.

Clasificarea algoritmilor de rutare

Centralizare sau descentralizare

• centralizat: situl central procesează şi rutele distribuite (echivalent: informaţii despre rutele de procesare cunoscute ca globale, fiecare rută efectuează aceeaşi procesare)

• decentralizat: fiecare ruter vede numai informaţii locale (de la el insuşi şi vecinii fizic conectaţi) şi determină ruterele pe această bază

Static sau adaptiv

• static: tabela de rutare se modifică foarte încet, adesea ca răspuns la intervenţia umană

• dinamic: tabelele de rutare se schimbă cu modificarea traficului sau topologiei de reţea

Două abordări de bază adoptate în practică:

• rutarea stării de legături: centralizat, dinamic (funcţionează periodic)

• vector distanţă: distribuit, dinamic (ca răspuns direct la schimbări).

Rutarea stării de legătură

Fiecare nod cunoaşte topologia reţelei şi costul fiecărei legături.

• cvasi-centralizat: fiecare ruter difuzează periodic costurile legăturii ataşate.

Costul poate reflecta

• întârzierile în aşteptare pe legătură

• lărgimea de bandă a legăturii

• toate legăturile cu costuri egale: rute cu calea cea mai scurtă.

Folosite în Internet OSPF, ISO IS-IS, DECnet, "noi" (1980) algoritmul de rutare ARPAnet.

Scop: determinarea căii cu costul cel mai mic de la un nod (sursă) la toate celelalte noduri: algoritmul pentru calea cea mai scurtă al lui Dijkstra.

Algoritmul pentru calea cea mai scurtă al lui Dijkstra: definiţii

Definim:

• c(i,j): costul legăturii de la i la j. c(i,j) = infinit dacă i,j nu sunt conectate direct. Vom presupune c(i,j) egal cu c(j,i) dar nu întotdeauna adevărat în practică.

• D(v): costul căii cunoscute în prezent cu cheltuielile cele mai mici de la sursă la nodul v.

• p(v): nodul anterior (vecinul lui v) în lungul căii curente cea mai scurtă de la sursă la v

• N:  set de noduri a cărei cale cea mai scurtă de la sursă este definitiv cunoscută.

Presupunem:

• nodul sursei este A

• interativ: după k iteraţii, se cunosc căile la "cel mai scurt" k (costul căii) la A.

Algoritmul lui Dijkstra: expunere

Iniţializare:

N = {A}

pentru toate nodurile v

dacă v adiacent lui A

atunci D(v) = c(A,v)

altfel D(v) = infinit

Bucla

Găseşte w care nu este în N astfel încât D(w) să fie minim.

adaugă w la N

actualizează D(v) pentru toţi v care nu sunt în N:

D(v) min( D(v), D(w) + c(w,v) )

/* noul cost la v este sau costul vechi la v sau costul cunoscut al celei mai scurte căi la w plus de la w la v */

Până când toate nodurile ajung în N.

Algoritmul lui Dijkstra: exemplu

• exemplu: în treapta 1: D(C) D(D)+c(D,C)

1+3

• pentru fiecare coloană, ultima intrare dă imediat informaţii despre calea cu costul cel mai mic la/de la A, şi costul la acel nod

• timpul de rulare pentru cazul cel mai rău: O(N**2)

Rutarea vectorului distanţă

Procesare asincronă, iterativă, distribuită:

• La fiecare treaptă:

  • primeşte informaţii de la vecin sau notează schimbările în costul legăturii locale

  • procesează

  • posibil să transmită noi informaţii la vecinii adiacenţi

Procesarea/comunicarea dintre entităşile nivelului reţea!

Tabela de distanţă:

• tabelă per nod înregistrând costurile tuturor nodurilor prin fiecare din vecinii săi

• DE(A,B) dă costul minim de la E la A considerând că primul nod al căii este B

  • DE(A,B) = c(E,B) + min DB(A,*)

  • minDE(A,*) dă costul minim al lui E către A

  • tabela de rutare derivată din tabela de distanţă

• exemplu: DE(A,B) = 14 (notă: nu 15!)

• exemplu: DE(C,D) = 4, DE(C,A) = 6

Algoritmul vectorului distanţă

1. Bazat pe algoritmul Bellman-Ford

2. Folosit în multe protocoale de rutare: Internet BGP, ISO IDRP, Novell IPX, ARPAnet original.

Algoritm (în nodul X):

Initializare: pentru toate nodurile adiacente v:

D(*,v) = infinit

D(v,v) = c(X,v)

transmite costul căii cea mai scurtă către fiecare destinaţie din vecinătate.

Bucla

Execută algoritmul de actualizare a topologiei distribuite.

Continuu

Algoritmul de utilizare a topologiei

În nodul X:

1. wait (until I see a link cost change to neighbor Y or until I receive update from neighbor W)

2. if (c(X,Y) changes by delta) {

/* change my cost to my neighbor Y */

change all column-Y entries in distance table by delta if this changes my least cost path to Z

send update wrt Z, DX(Z,*) , to all neighbors

}

1. if (update received from W wrt Z) {

/* shortest path from W to some Z has changed */

DX(Z,W) = c(X,W) + DW(Z,*)

if this changes my least cost path to Z send update wrt Z, DX(Z,*) , to all neighbors

Rutarea vectorului distanţă: exemplu

Rutarea vectorului distanţă: recuperarea din legăturile defecte

Dacă legătura XY pică, setează c(X,Y) la infinit şi rulează algoritmul de actualizare a topologiei.

Bucla:

• tabele de rutare inconsistente: saă se ajungă la rutele A, D prin E, şi la rutele E prin D

• buclele eventual dispar (după suficiente iteraţii)

• buclele determină degradarea performanţei, livrarea peste rând

Rutarea vectorului distanţă: exemplu de recuperare

Rutarea vectorului distanţă: rezolvarea problemei buclelor

Buclele vor exista în tabele până când valorile din tabel "calculează" costul rutei alternante.

Algoritm de splitare orizontală

• regulă: dacă rutele A trec prin Y via B atunci A îi spune lui B că distanţa sa până la Y este infinită

• exemplu: B nu va trece niciodată traficul său către Y prin A

Oscilaţii

Un scenariu rezonabil

• costul legăturii depinde de cantitatea de trafic transportat

• nodurile schimbă costurile legăturii la fiecare T

• presupunem:

  • A este destinaţia pentru întreg traficul

  • B, D trimit 1 unitate de trafic la A

  • C trimite e unităţi de trafic (e<<1) la A.

Întreaga reţea poate oscila. Soluţii posibile:

• eliminarea schimburilor periodice

• costurile legăturilor nu trebuie să fie funcţie de sarcină.

Oscilaţiile vectorului distanţă

Comparare între algoritmii LS şi DV

Complexitatea mesajului:

• "LS este mai bun": DV necesită iterarea cu schimbarea mesajului la fiecare iteraţie

• "DV este mai bun": dacă schimbările legăturii nu afectează calea cu costul cel mai mic, nu se schimbă niciun mesaj.

Robusteţea: ce se întâmplă daca ruterul pică, nu se comportă cum trebuie sau este sabotat?

LS poate:

• să raporteze distanţa incorectă la vecinii conectaţi

• să corupă/piardă oricare mesaje care trec

• să raporteze vecinătăţi incorecte.

DV poate:

• să avertizeze asupra costurilor pentru calea cea mai scurtă la nici o/toate destinaţiile.

Viteza de convergenţă

DV:

• poate itera de mai multe ori în timp ce converge

• bucle, numărare la infinit, oscilaţii

• nu poate propaga noi informaţii până când nu recalculează propriile sale rute

LS:

• necesită 1 difuzare per nod per recalculare

• poate avea probleme din cauza oscilaţiilor.

Amândouă au avantaje şi dezavantaje

• una din ele va fi utilizată cu preponderenţă în reţea.

Rutarea difuzării

Difuzarea: trimiterea unui pachet la toţi cei N destinatari

• rutarea se actualizează în cazul LS

• avertisment privind serviciul/solicitarea în stratul aplicaţie (de ex., Novell)

Algoritmul de difuzare 1: N transmiteri punct-la-punct

• trimite pachetul la fiecare destinaţie, punct-la-punct.

• Pierdere a lărgimii de bandă.

• Necesită cunoaşterea tuturor destinaţiilor.

Algoritmul de difuyare 2: flooding

• când nodul primeţte un pachet de difuzare, îl transmite la fiecare legătură

• nodul poate primi multe copii ale pachetului difuzat, deci trebuie să poată detecta duplicatele

Rutarea difuzării: direcţionarea căii inverse

Scop: eliminarea duplicatelor de flooding

Presupuneri:

• A doreşte să difuzeze

• toate nodurile cunosc nodul predecesor pe calea cea mai scurtă înapoi la A

Direcţionarea căii inverse: dacă nodul primeşte un pachet de difuzat

• dacă pachetul soselte de la nodul predecesor pe calea cea mai scurtă la A, atunci floodează totţi vecinii

• altfel se ignoră pachetul de difuzat - care a ajuns deja sau va ajunge de la nodul predecesor

Informaţii despre rutarea distribuită

Va fi bun un algoritm de difuzare precum direcţionarea căii inverse pentru actualizări distribuite ale Stării de Legătură (în rutarea LS)?

Prima încercare (la distribuţia de difuzare a LS):

Fiecare ruter păstrează o copie a celui mai recent pachet LS (LSP) primit din fiecare celălalt nod

După primirea LSP(R) de la ruterul R:

• dacă LSP(R) nu este identic cu copia stocată

atunci stochează LSP(R), actualizează informaţiile LS pentru R, şi floodează LSP(R)

altfel ignoră duplicatul

A 2-a încercare (la distribuţie de difuzare LS):

Fiecare ruter pune un număr de secvenţă pe LSP proprii.

După primirea LSP(R) de la R

• dacă (seq # > seq # a copiei stocate ) a LSP(R)

atunci stochează LSP(R), actualizează informatille LS pentru R, şi floodează LSP(R)

altfel ignoră duplicatul.

A 3-a încercare (la distribuţia de difuzare LS)

Foloseşte secvenţe de numere "mari".

Adaugă câmp pentru "vârstă" pe bază de timp

• fiecare ruter scade valoarea câmpului vârstei cum LSP(R) rezidă în memorie

• informaşii de rutare pentru aşteptarea locală (uitare) dacă vârsta este zero

• nu floodează

• pachet cu vârsta zero.

Înlătură LSP(R) în aşteptare (pentru transmisie) dar netransmise înainte de a flooda LSP(R) mai noi.

Rutarea | Exemplu: ATM