Corso Reti ed Applicazioni Mauro Campanella Como 2003cmp/CorsoReti/slides03/Cap4-1.pdf ·...

Capitolo 4 - parte 1

Corso Reti ed ApplicazioniMauro Campanella

Como 2003

M. Campanella Corso Reti ed Applicazioni - Como 2003 Cap 4 - 1 pag. 2

Lo strato di rete

Lo scopo è di trasportare ipacchetti dalla sorgente alladestinazione utilizzando unoschema di indirizzamento.Lo strato esiste in ogni nododella rete (host o router)

La funzione principale è diindividuare un percorsoopportuno:

algoritmi (e protocolli) di routing

retedata link

fisico

retedata link

fisico

retedata link

fisico

retedata link

fisico

retedata link

fisico

retedata link

fisico

retedata link

fisico

retedata link

fisico

applicazionetrasporto

retedata link

fisico


retedata link

fisico


Modelli di servizio di rete

Lo strato di rete offre allo stratodi trasporto un servizio diconsegna dei segmenti.Le caratteristiche del serviziopossono variare fra due estremi:- servizio orientato alla

connessione con garanzia diqualità (es: circuito telefonico)

- multiplexing statistico dipacchetti senza connessione(esempio: Internet)

? ??su circuiti virtuali

o senza ?

Inoltre, il servizio èofferto :


Memento: Parametri di QoS

I principali parametri per quantificare la qualità del servizioofferto da una rete sono :

�- ritardo in una direzione (one-way delay)�- la variazione del ritardo (one-way IP packet delay variation o ipdv);�- capacità;�- perdita di pacchetti in una direzione (non dati).

L’insieme è comune a IETF e ITU-T.Nomenclatura e definizioni seguono la RFC 2330 (Frameworkfor IP Performance metrics) and sono modificate secondol’evoluzione decisa dal gruppo di lavoro IPPM di IETF.


Parziale tassonomia delle reti

Reti ditelecomunicazione

Reti a commutazionedi circuito

TDM

Reti a commutazionedi pacchetto

Reti a CircuitiVirtuali (VC)

Reti adatagrammi

• Il multiplexing statistico di datagrammi funziona su entrambe.• Le reti a commutazione di circuito possono offrire maggiori

garanzie di Qualità del Servizio (QoS)

WDMFDM


I modelli di rete per i dati

Internet– richiesta base alla rete di

puro instradamento, senzagaranzie di QoS (Best Effort)

– intelligenza solo negli end-node, ai “bordi”

– gestione errori e controllonel protocollo di trasportonegli end node

– “agnostico” sul tipo di datalink, permettendo lacomplessità e la variabilità

Asynchronous Transfer Modeevoluzione ai dati del modellotelefonico e quindi:– richieste di sincronia e

affidabilità– garanzie di servizio (QoS)– end node “stupidi”– complessità solo all’interno

della rete– basato su circuiti virtuali– rete omogenea (solo ATM)


Il modello Internet- nessuna chiamata all’inizio della connessione- router: nessun stato per connessione (flusso) - la gestione è pacchetto per pacchetto, senza “storia”- pacchetti smistati usando l’indirizzo di destinazione- pacchetti fra la stessa sorgente e destinazione possono

percorrere percorsi diversi


retedata link

fisico


retedata link

fisico

1. Invio dati 2. Ricezione dati


⇒⇒⇒⇒ E’ in grado di crescere bene

Il servizio standard di rete di Internet:Best Effort

⇒⇒⇒⇒ Complessità nei sistemi, rete semplice (modello end-to-end)

⇒⇒⇒⇒ Degrada bene, il service non è mai rifiutato anche se le risorse sono congestionate (capacità, sistemi…)

Basato sulmultiplexing statistico


Confronto modelli di rete

Architetturadi rete

Internet

ATM

ATM

ATM

ATM

Modello diServizio

best effort

CBR

VBR

ABR

UBR

Capacità

no

costante

garantitavalore medio

minimogarantito nessunagaranzia

Perdita

no

si

si

no

no

Ordine

no

si

si

si

si

ipdv

no

si

si

no

no

SegnalazioneCongestione

no (inferitadalle perdite)

no

no

si

no

Garanzie ?

ATM suppone un traffico predicibile per poter funzionare bene,che non è possibile con traffico dati statistico


I circuiti virtuali (VC)

– Il circuito deve essere creato prima che i dati possano passare– un pacchetto può portare un identificatore di circuito– ogni router lungo il canale deve mantenere “stato” per ogni

circuito virtuale che lo attraversa– ulteriori risorse del router e del canale possono essere

dedicate al VC per ottenere QoS

Stabilire un canale “logico” dalla sorgente alladestinazione che si comporti come un circuito telefonico– permetta anche di avere garanzie di QoS– la rete sia parte “attiva” nella gestione del canale


I circuiti virtuali (VC)

Il circuito virtuale può essere creato manualmente, in anticipo,(circuito virtuale permanente o statico) includendo o menogaranzie di QoS. Vi è il problema della complessità di gestionemanuale dei VC il cui numero cresce come N(N-1)/2, dove N è ilnumero di nodi coinvolti.

Oppure si può usare un protocollo di segnalazione per lacreazione dinamica del VC.

In entrambi i casi vi sono problemi di– tempo per la creazione del circuito– autenticazione ed autorizzazione fra router e domini diversi



retedata link

fisico


retedata link

fisico

Protocollo di segnalazione

In pratica solo ReSource reserVation Protocol (RSVP)– usato to creare, mantenere, cancellare VC con certe

caratteristiche– usato da data link quali ATM, frame-relay, X.25– usato oggi (poco) in Internet da Multi Protocol Label

Switching (MPLS)

1. inizio chiamata 2. arrivo chiamata

3. accettazione4. connessione5. inizio flusso dati 6. ricezione dati


Algoritmi di routing

Per gli algoritmi di routing siastrae la rete fisica in grafi:- i nodi del grafo sono router- i lati del grafo sono linee fisiche– costo delle linee: ritardo, costo

monetario, livello dicongestione o di saturazione

Scopo: determinare un “buon”percorso (serie di router) dalla

sorgente alla destinazione.

Protocollo di Routing

A

ED

CB

F2

21

3

1

1

2

53

5

“buon” percorso:– tipicamente minimizza il

costo totale– altre definizioni possibili…


Classificazione degli algoritmi di routing

Informazione globale o localeglobale: tutti i router conosconol’intera topologia ed i costi:

algoritmi di “link state”decentralizzato:– i router conoscono solo i vicini

direttamente connessi ed i costirelativi

– processo iterativo di calcolo conscambio di informazione con ivicinialgoritmi di “distance vector”

Statico or dinamicoStatico:le “rotte” cambianolentamente nel tempoDinamico:“rotte” cambiano piùrapidamente– aggiornamenti periodici– reazioni a cambiamenti di

costo


Un algoritmo di routing Link-State

L’algoritmo di DijkstraLa topologia della rete e i costidelle linee noti a tutti i nodi– realizzato attraverso “link

state broadcast”– tutti i nodi hanno la stessa

informazionecalcola il percorso con costominore da un nodo (sorgente) atutti gli altri– fornisce routing table– iterativo: dopo k iterazioni,

coverge al percorso di costominore verso k destinazioni

Notazione:c(i,j): costo della linea dalnodo i a j. Il costo è infinitose non sono vicini direttiD(v): valore corrente delcosto del cammino dallasorgente alla destinazione Vp(v): nodo che precede v (edè collegato a v) nel percorsodalla sorgente a vN: insieme dei nodi di cui ilcammino di costo minore ènoto


Algoritmo di Dijsktra

1 Initializzazione: 2 N = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* il nuovo costo per v è o il vecchio costo per v oppure il 14 percorso a costo minore per w più il costo da w a v */ 15 until all nodes in N


Algoritmo di Dijsktra: esempio

Passo012345

N inizialeA

ADADE

ADEBADEBC

ADEBCF

D(B),p(B)2,A2,A2,A

D(C),p(C)5,A4,D3,E3,E

D(D),p(D)1,A

D(E),p(E)∞ 2,D

D(F),p(F)∞∞

4,E4,E4,E

A

ED

CB

F2

21

3

1

1

2

53

5


Algoritmo di Dijsktra: discussione

Complessità dell’algoritmo : n nodi– ogni iterazione: controllo di tutti i nodi, w, non in N e quindi

sono necessari n*(n+1)/2 confronti: O(n2)– La più efficente implementazione è dell’ordine di O( n·log(n) )

Possibili oscillazioni in funzione del tipo di costo: per esempio se ilcosto del percorso è funzione della quantità di traffico.

Lentezza in caso di reti di grandi dimensioni magliate.

AD

C

B1 1+e

e0

e1 1

0 0

iniziale

AD

C

B2+e 0

001+e 1

… ricalcolo

AD

C

B0 2+e

1+e10 0

… ricalcolo

AD

C

B2+e 0

e01+e 1

… ricalcolo


Algoritmo di distance vector

Iterativo:continua fino a quandonessun nodo scambia altreinformazioniauto-terminante:nessun “segnale” di fineasincrono:l’iterazione non dipende datutti i nodi in cicli chiusidistributo (locale):ciascun nodo comunica solocon i nodi vicini

Tabella delle distanzeogni nodo ha la suariga per ogni possibile destinazionecolonna per ogni vicino direttamenteconnessoesempio: nel nodo X, destinazione Yattraverso il vicino Z:

D (Y,Z)X

distanza da X a Yvia Z come “next hop”

c(X,Z) + min {D (Y,w)}Z

w

=

=


Tabella di distanze : esempio

A

E D

CB7

81

2

1

2D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

E

costo per la destinazione via

dest

inaz

ione

D (C,D)E

c(E,D) + min {D (C,w)}D

w== 2+2 = 4

D (A,D)E

c(E,D) + min {D (A,w)}D

w== 2+3 = 5

D (A,B)E

c(E,B) + min {D (A,w)}B

w== 8+6 = 14

loop!

loop!


Dalla tabella delle distanze a quella di routing

D ()

A

B

C

D

A

1

7

6

4

B

14

8

9

11

D

5

5

4

2

Ecosto alla destin. via

dest

inaz

ione

DE()

A

B

C

D

A,1

D,5

D,4

D,2

next hop (linea) in uscita da usare, costo

dest

inaz

ione

Tabella delle distanze Tabella di routing

A

E D

CB7

81

2

1

2


Routing con algoritmo di Distance Vector

Iterativo, asincrono: ogniiterazione locale è causata da:cambio costo link localemessaggio da un vicino:cambio del suo percorso dicosto minimo verso un vicinoDistribuito (locale):ogni nodo notifica i vicini soloquando vi è un cambio dicosto di un suo percorso aduna qualsiasi destinazione– i vicini quindi notificano i

loro vicini se necessario

attende (cambio nei costilocali o messaggio dal unvicino

ricalcola la tabella distanze

se un percorso di costominimo qualsiasi è cambiato,notifica i vicini

Ogni nodo:


Confronto degli algoritmi di LS e DV

Complessità del messaggio:LS: con n nodi, E linee, O(nE)messaggi ciascun nodoDV: scambio solo fra vicini– tempo variabile

Velocità di convergenzaLS: algoritmo O(n2) cherichiede O(nE) messaggi– può oscillare

DV: tempo variabile– possibilità di loop– aumento all’infinito

Robustezza: (malfunzionamenti)LS:– nodo può segnalare un costo

errato della linea– ciascun nodo calcola solo la

sua propria tabellaDV:– nodo può segnalare un costo

di percorso errato– la tabella di ogni nodo è

usata dagli altri e l’errore sipropaga nella rete


Scalabilità del routing

scalabilità: centinaia dimilioni di destinazioni:– impossibile avere tabelle

di routing che lecontengano tutte

– tabelle troppo grandi peressere scambiate

autonomia amministrativa– Internet = rete delle reti– ciascun dominio (rete)

desidera avere la libertà didecidere il routing alproprio interno

I modelli presentati sono un’astrazione:– tutti i router identici– rete “piatta”

… la realtà è diversa


Gerarchia nel routing

Aggregare blocchi di indirizzi(e quindi router) in aree dette“autonomous systems” (AS)I router nello stesso AS runutilizzano il medesimoprotocollo di routing– routing “intra-AS”

Router in AS differenti possonousare protocolli di routingintra-AS differenti.

In ogni AS router specialiche :utilizzano un protocollo intra-AS con gli altri router dell’ASsono responsabili dellecomunicazioni con altri AS– routing inter-AS

Il protocollo di routing fra ASè diverso da quello interno

Gateway routers


Routing Intra-AS ed Inter-AS

Gateways:• calcolano routing

inter-AS fra di loro• calcolano routing

intra-AS con altrirouter dello stessoAS

routing intra-ASe

routing inter-ASnel gateway A.c

strato di rete

strato di data linkstrato fisico

a

b

b

aaC

A

Bd

A.aA.c

C.bB.a

cb

c


Host h2a

b

b

aaC

A

Bd c

A.aA.c

C.bB.a

cb

Hosth1

Routing intra-AS all’interno dell’AS A

Routinginter-ASfra A e B

Routing intra-ASall’interno dell’AS B

Routing Intra-AS ed Inter-AS


Lo strato di rete di Internet

tabella diinstradamento

Protocolli di routing •selezione percorso•RIP, OSPF, BGP

Protocollo IP • specifica indirizzamento• formato del datagramma • gestione dei pacchetti

Protocollo ICMP• segnalazione errori• “scoperta e segnalazione” fra router

Trasporto: TCP, UDP, …

Data Link

Fisico

Stratodi rete


Indirizzamento IP : introduzione

Indirizzo IP : identificatore a32-bit identifier senza segnoper l’interfaccia del nodo.interfaccia: punto diconnessione fra il nodo e lalinea fisicai router hanno tipicamentepiù di un’interfaccia– anche gli host possono

avere più interfacce– uno o più indirizzi IP

sono associati a ciascunainterfaccia

223.1.1.1

223.1.1.2

223.1.1.3

223.1.1.4 223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2223.1.3.1

223.1.3.27

223.1.1.1 = 11011111 00000001 00000001 00000001

223 1 11

notazione decimale puntata


Indirizzamento IPUn indirizzo IP è diviso in dueparti:– rete (bit più significativi)– nodo (bit meno significativi)

attraverso una maschera direte (network mask) a bit (ad1 per la parte di rete ed a 0per la parte di nodo).Deve essere specificato quindinon solo l’indirizzo, ma anchela maschera di rete.Tutti i nodi con identica partedi rete possono parlarsi fra lorosenza l’aiuto di un router.

222.1.1.1

222.1.1.2

222.1.1.3

222.1.1.4 333.1.2.9

333.1.2.2

333.1.2.1

111.1.3.2111.1.3.1

111.1.3.27

Rete composta di 3 “reti” IP (in cuivariano i primi tre byte per la parte direte e l’ultimo (meno significativo) per laparte di nodo. Maschera di rete:255.255.255.0

LAN


Scalabilità e semplicità:Attraverso la maschera direte, si creano “reti”autonome e che possonoparlare con le altre reti IPsolo attraverso un router.Il router deve avereun’interfaccia con unindirizzo in ogni rete.

223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.2223.1.2.1

223.1.2.6223.1.3.2

223.1.3.1

223.1.3.27

223.1.1.2

223.1.7.0

223.1.7.1223.1.8.0223.1.8.1

223.1.9.1

223.1.9.2

Indirizzamento IP

Tre “reti” ciascuna conmaschera di rete:

255.255.255.0


Indirizzamento IP

0 rete nodo

10 rete nodo

110 rete nodo

1110 indirizzi multicast

A

B

C

D

classe1.0.0.0 a127.255.255.255

128.0.0.0 a191.255.255.255

192.0.0.0 a223.255.255.255

224.0.0.0 a239.255.255.255

32 bit

La classificazione originale degli indirizzi in “reti” era semplice.

Indirizzamento “class-full”

1111 riservatiE 244.0.0.0 a255.255.255.255


Indirizzamento IP: CIDR

Oggi usato un indirizzamenrto class-less :– per ottimizzare l’uso degli indirizzi– per esempio una rete di classe B blocca indirizzi per 65535

nodi, anche se l’ente ne possiede solo 2000CIDR: Classless InterDomain Routing– la parte di rete può avere un numero arbitrario di bit– descritto come : a.b.c.d/x, dove x è il numero di bit della

parte di rete (più significativi)

11001000 00010111 01000000 00000001rete nodo

200.23.64.1/22 : maschera di rete 255.255.252.0


Indirizzamento IP: CIDR

11001000 00010111 010000 00 00000001 = 3 356 966 913

200 23 16 1

maschera di rete: 11111111 11111111 111111(00) =255.255.(128+64+32+16+8+4) = 255.255.252.0 =

255.255.(255-1-2) = 255.255.252.0

11001000 00010111 01000000 00000001rete nodo

200.23.64.1/22 : maschera di rete 255.255.252.0

Corso Reti ed Applicazioni Mauro Campanella Como 2003cmp/CorsoReti/slides03/Cap4-1.pdf ·...

Documents

Transcript of Corso Reti ed Applicazioni Mauro Campanella Como 2003cmp/CorsoReti/slides03/Cap4-1.pdf ·...