Modelli per l’analisi e il dimensionamento

(1)

RETI DI CALCOLATORI II

Prof. PIER LUCA MONTESSORO Ing. DAVIDE PIERATTONI

Facoltà di Ingegneria Università degli Studi di Udine

© 2003 Pier Luca Montessoro (si veda la nota a pagina 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà degli autori prof. Pier Luca Montessoro e ing. Davide Pierattoni, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

Modelli per l’analisi e il dimensionamento

delle reti

Modelli per l’analisi e il dimensionamento

delle reti

Argomenti della lezione Argomenti della lezione

Î Ritardi nelle commutazione di pacchetto e perdita di

pacchetti

Î Ritardi nelle commutazione di pacchetto e perdita di

pacchetti

Î Controllo della congestione in TCP

I ritardi indicati determinano il ritardo totale al router A I ritardi indicati determinano

il ritardo totale al router A

Commutazione di pacchetto Commutazione di pacchetto

multiplexing statistico multiplexing statistico accodamento in attesa di trasmissione accodamento in attesa di trasmissione

A A B B

Ritardi e perdite nelle reti a commutazione di pacchetto Ritardi e perdite nelle reti a commutazione di pacchetto

Î Ritardo di elaborazione

Î

Ritardo di elaborazione

Il ritardo totale introdotto da un nodo è dovuto a:

Î Ritardo di coda

Î

Ritardo di coda

Î Ritardo di trasmissione

Î

Ritardo di trasmissione Î Ritardo di propagazione

Î

Ritardo di propagazione

Questi ritardi determinano

la probabilità di perdere pacchetti Questi ritardi determinano

la probabilità di perdere pacchetti

(2)

Ritardi Ritardi

Questi ritardi determinano il ritardo totale al router A Questi ritardi determinano il ritardo totale al router A

elaborazione elaborazione codacoda

propagazione propagazione

trasmissione trasmissione

A A B B

Ritardo di elaborazione Ritardo di elaborazione

Î Tempo necessario ad esaminare il pacchetto e a determinarne

l’instradamento

Î Tempo necessario ad esaminare il pacchetto e a determinarne

l’instradamento

Î Comprende anche il controllo degli errori

Î Il pacchetto viene poi inviato alla coda di trasmissione Î Il pacchetto viene poi inviato

alla coda di trasmissione Î Ordine di grandezza:

microsecondi (o inferiore) Î Ordine di grandezza:

microsecondi (o inferiore)

Î Tempo di attesa prima della trasmissione Î Tempo di attesa prima

della trasmissione

Î Dipende da quanto pacchetti precedenti sono già in coda Î Dipende da quanto pacchetti

precedenti sono già in coda Î È zero se non ci sono pacchetti

né in coda né in trasmissione Î È zero se non ci sono pacchetti

né in coda né in trasmissione Î Dipende dall’intensità e dalla

natura del traffico

Î Dipende dall’intensità e dalla natura del traffico

Î Ordine di grandezza:

dai microsecondi ai millisecondi Î Ordine di grandezza:

dai microsecondi ai millisecondi Ritardo di coda Ritardo di coda

Î Tempo necessario a trasmettere tutti i bit del pacchetto

Î Dipende dalla velocità R del link e dalla lunghezza L del pacchetto Î Dipende dalla velocità R del link

e dalla lunghezza L del pacchetto Esempio:

Esempio:

L = 1500 byte = 12000 bit

L = 1500 byte = 12000 bit

R = 100 Mb/s

R = 100 Mb/s

d

tras

= L/R = 120 ms

dtras= L/R = 120 ms

Ritardo di trasmissione Ritardo di trasmissione

Î Tempo necessario al segnale per transitare lungo l’intera lunghezza del link fisico

Î Dipende dalla lunghezza l del link e dalla velocità di propagazione s sul mezzo (circa 2 ·10

⁸

m/s) Î Dipende dalla lunghezza l del link

e dalla velocità di propagazione s sul mezzo (circa 2 ·10

⁸

m/s)

l = 1 km (LAN), s = 2 ·10

⁸

m/s

l = 1 km (LAN), s = 2 ·10⁸m/s

d

prop

= l/s = 5 ms

dprop= l/s = 5 ms

l = 72000 km (satellite),

l = 72000 km (satellite),

s = 3 ·10

⁸

m/s

s = 3 ·10⁸m/s

d

prop

= l/s = 0.24 s

dprop= l/s = 0.24 s

Ritardo di propagazione Ritardo di propagazione

Esempio:

Esempio:

A seconda del tipo di collegamento alcuni valori possono essere

trascurabili

A seconda del tipo di collegamento alcuni valori possono essere

trascurabili d

d

nodonodo

= d = d

elabelab

+ + d d

codacoda

+ d + d

trastras

+ + d d

propprop

Ritardo totale al nodo

(3)

Î d

coda

non è costante:

varia da pacchetto a pacchetto Î d

coda

non è costante:

varia da pacchetto a pacchetto Î A causa della lunghezza finita

dei buffer di memoria può

determinare la perdita di pacchetti Î A causa della lunghezza finita

dei buffer di memoria può

determinare la perdita di pacchetti Ritardo di coda

e perdita dei pacchetti Ritardo di coda

e perdita dei pacchetti

Ritardo di coda

e intensità di traffico Ritardo di coda

e intensità di traffico

Si accodano L · a bit/s Si accodano L · a bit/s

a

a = velocità = velocit à media di arrivo media di arrivo

dei pacchetti (pacchetti/s) dei pacchetti (pacchetti/s) L

L

= lunghezza dei pacchetti (in bit) = lunghezza dei pacchetti (in bit)

Ritardo di coda

e intensità di traffico Ritardo di coda

e intensità di traffico

L · a/R = intensità di traffico se L · a/R>1 la lunghezza della coda cresce senza limiti ed il ritardo tende ad infinito

L · a/R

= intensità di traffico se L · a/R>1 la lunghezza della coda cresce senza limiti ed il ritardo tende ad infinito R

R

= velocit = velocità à di trasmissione (b/s) di trasmissione (b/s)

Anche se L · a/R<1 è possibile

la perdita di pacchetti perché

la distribuzione dei tempi di arrivo

è casuale (possono arrivare

a gruppi) Anche se

L · a/R<1

è possibile

la perdita di pacchetti perché

la distribuzione dei tempi di arrivo

è casuale (possono arrivare

a gruppi)

L · a/R

L · a/R ritardo media di coda

ritardo media di coda

1 1

Ritardo di coda

e intensità di traffico Ritardo di coda

e intensità di traffico

Î Se un pacchetto in arrivo trova la coda piena, viene scartato Î Se un pacchetto in arrivo trova

la coda piena, viene scartato Î All’aumentare dell’intensità

di traffico aumenta la probabilità di perdita di pacchetti

Î All’aumentare dell’intensità di traffico aumenta la probabilità di perdita di pacchetti

Î I pacchetti persi possono essere recuperati mediante ritrasmissioni da parte del livello di trasporto o delle applicazioni

Perdita di pacchetti Perdita di pacchetti

Î Effetto combinato dei ritardi in tutti i nodi attraversati Î Effetto combinato dei ritardi

in tutti i nodi attraversati Î In presenza rete omogenea

con poco traffico (d

coda

= 0) e Q-1 router da attraversare:

d

end-to-end

= Q (d

elab

+ d

tras

+ d

prop

) compreso il ritardo dell’host sorgente

Î In presenza rete omogenea con poco traffico (d

coda

= 0) e Q-1 router da attraversare:

d

end-to-end

= Q (d

elab

+ d

tras

+ d

prop

) compreso il ritardo dell’host sorgente

Ritardo end-to-end

(4)

Controllo della congestione in TCP Controllo della Controllo della congestione in TCP congestione in TCP

Î Controllo della congestione Î

Î

Controllo della congestione Controllo della congestione

Protocollo

Protocollo sliding sliding window window Î Controllo di flusso

Î

Controllo di flusso Controllo di flusso

Î Gestione dei pacchetti danneggiati Î

Î

Gestione dei pacchetti danneggiati Gestione dei pacchetti danneggiati

Controllo della congestione del TCP

Stesso meccanismo per:

Î Permettono la trasmissione di più segmenti in successione, anche prima di aver ricevuto i riscontri dei precedenti

Î Ogni segmento spedito è numerato con un numero progressivo

su n bit (da 0 a 2

ⁿ

-1)

Î Ogni segmento spedito è numerato con un numero progressivo

su n bit (da 0 a 2

ⁿ

-1)

Î La numerazione è legata ai buffer di memoria di trasmettitore e ricevitore

Protocolli “sliding window”

Il trasmettitore mantiene una finestra di trasmissione Il trasmettitore mantiene una finestra di trasmissione

Î I segmenti appartenenti alla finestra vengono memorizzati per

eventuali ritrasmissioni

Î

I segmenti appartenenti alla finestra vengono memorizzati per

eventuali ritrasmissioni

Î Numeri di sequenza dei segmenti che può spedire

Î

Numeri di sequenza dei segmenti che può spedire

Î Indica i segmenti che possono essere spediti prima di aver ricevuto

i riscontri dei precedenti

Î

Indica i segmenti che possono essere spediti prima di aver ricevuto

i riscontri dei precedenti

Protocolli “sliding window”

Il ricevitore mantiene una finestra di ricezione Il ricevitore mantiene una finestra di ricezione

Î Segmenti appartenenti alla finestra vengono memorizzati per

eventuali ritrasmissioni

Î

Segmenti appartenenti alla finestra vengono memorizzati per

eventuali ritrasmissioni

Î Numeri di sequenza dei segmenti che può ricevere

Î

Numeri di sequenza dei segmenti che può ricevere

Î Permette di accettare frame fuori ordine e memorizzarli nell’attesa dei segmenti precedenti mancanti

Î

Permette di accettare frame fuori ordine e memorizzarli nell’attesa dei segmenti precedenti mancanti

Protocolli “sliding window”

Î Il limite superiore viene fatto avanzare quando si spedisce un nuovo frame

Î

Il limite superiore viene fatto avanzare

quando si spedisce un nuovo frame

1

1 2 2 5

5 6 6

00

33 44 77

TRASMETTITORE TRASMETTITORE

Î Il limite inferiore viene fatto avanzare quando si riceve il riscontro del frame il cui numero progressivo corrisponde all’estremità inferiore

Î

Il limite inferiore viene fatto avanzare quando si riceve il riscontro del frame il cui numero progressivo corrisponde all’estremità inferiore

Protocolli “sliding window”

(5)

1 1 2 2 5

5 6 6

00

33 44 77 RICEVITORE RICEVITORE

Î La dimensione della finestra è fissa

Î

La dimensione della finestra è fissa Î L’intera finestra viene fatta avanzare

quando si riceve un frame il cui numero progressivo corrisponde all’estremità inferiore

Î

L’intera finestra viene fatta avanzare quando si riceve un frame il cui numero progressivo corrisponde all’estremità inferiore

Protocolli “sliding window”

Î La numerazione non è orientata ai segmenti, ma al byte

Î Il numero di sequenza

di un segmento è sempre il numero di sequenza del primo byte

contenuto nel campo dati Î Il numero di sequenza

di un segmento è sempre il numero di sequenza del primo byte

contenuto nel campo dati

Î Nei messaggi di riscontro viene sempre indicato il numero

di sequenza del byte successivo che il ricevitore sta aspettando (rispetto all’ultimo

ricevuto in ordine)

Î Nei messaggi di riscontro viene sempre indicato il numero

di sequenza del byte successivo che il ricevitore sta aspettando (rispetto all’ultimo

ricevuto in ordine)

TCP: numeri di sequenza TCP: numeri di sequenza

Nei

Nei messaggi messaggi di di riscontro riscontro del protocollo del protocollo TCP

TCP viene viene sempre sempre indicato indicato il il prossimo prossimo numero

numero di di sequenza sequenza che che il il ricevitore ricevitore si si aspetta aspetta Quindi

Quindi, se la , se la sequenza sequenza inizia inizia da da 7200, 7200, per

per confermare confermare l’ l ’avvenuta avvenuta ricezione ricezione dei

dei primi primi 350 byte il 350 byte il ricevitore ricevitore invia invia un acknowledge con

un acknowledge con numero numero di

di sequenza sequenza 7550 (i byte ricevuti 7550 (i byte ricevuti sono sono numerati

numerati da da 7200 a 7549) 7200 a 7549)

TCP: numeri di sequenza TCP: numeri di sequenza

Î Il TCP non usa messaggi espliciti di NACK

Î Se riceve un segmento fuori ordine (buco nella sequenza di dati) invia un duplicato dell’ACK per l’ultimo segmento in ordine ricevuto

Î Il trasmettitore, quando riceve tre ACK duplicati, li interpreta come NACK per il segmento seguente (“ritrasmissione veloce”,

RFC 2581)

Î Il trasmettitore, quando riceve tre ACK duplicati, li interpreta come NACK per il segmento seguente (“ritrasmissione veloce”,

RFC 2581)

TCP: segmenti ricevuti fuori ordine

Ripetizione selettiva:

trasmettitore Ripetizione selettiva:

trasmettitore

dimensione finestra dimensione finestra

next_seq_num next_seq_num riscontrato

riscontrato inviato, non riscontrato inviato, non

riscontrato non disponibile non disponibile disponibile, non ancora spedito disponibile, non ancora spedito

dimensione finestra dimensione finestra

next_seq_num next_seq_num fuori ordine ma già riscontrato fuori ordine ma già riscontrato atteso, non ancora ricevuto atteso, non

ancora ricevuto già accettato o non accettabile già accettato o non accettabile accettabile accettabile

Ripetizione selettiva:

ricevitore

Ripetizione selettiva:

ricevitore

(6)

Î La dimensione della finestra di ricezione varia in funzione della dimensione del buffer (fissa) e dei dati ricevuti ma non ancora prelevati dal processo applicativo Î La dimensione della finestra

di ricezione varia in funzione della dimensione del buffer (fissa) e dei dati ricevuti ma non ancora prelevati dal processo applicativo Î La dimensione della finestra

di ricezione viene comunicata al trasmettitore nel campo

“window size” dei segmenti inviati Î La dimensione della finestra

di ricezione viene comunicata al trasmettitore nel campo

“window size” dei segmenti inviati TCP: finestra di ricezione TCP: finestra di ricezione

finestra di trasmissione =

min (finestra di ricezione, finestra di congestione)

Î La dimensione della finestra

di trasmissione viene modificata dinamicamente in funzione della capacità della rete e del ricevitore Î La dimensione della finestra

di trasmissione viene modificata dinamicamente in funzione della capacità della rete e del ricevitore TCP: finestra di trasmissione TCP: finestra di trasmissione

Î Inizialmente a 1, man mano che arrivano riscontri cresce esponenzialmente fino ad un valore di soglia predefinito, poi linearmente

Î Se un riscontro non arriva entro il timeout, il valore di soglia viene abbassato alla metà dell’attuale valore della finestra di congestione e questa riparte da 1

TCP: finestra di congestione TCP: finestra di congestione

numero di trasmissioni numero di trasmissioni dimensione della finestra di congestionedimensione della finestra di congestione

1

1 22 33 44 55 66 77 88 991010111211121313141415151616 112

23 34 45 56 67 78 8 9 9 101011 11

soglia soglia