Capitolo 8 Strato di Collegamento- Accesso Multiplo e Reti in Area
by user
Comments
Transcript
Capitolo 8 Strato di Collegamento- Accesso Multiplo e Reti in Area
Capitolo 8
Strato di CollegamentoAccesso Multiplo e Reti in Area
Locale
1
Sommario del Capitolo
Servizi offerti dallo Strato di Collegamento
o
o
o
o
Rivelazione di errore e controllo di errore (ARQ)
Indirizzamento
Controllo di flusso
Accesso Multiplo
Reti in Area Locale
o
o
o
La famiglia delle Reti Ethernet
L’interconnessione di Reti in Area Locale
Il protocollo PPP
Reti a Circuito Virtuale
o
o
Generalità
Indirizzamento
Introduzione alle Reti ATM
o
o
o
Architettura Protocollare
Servizi Offerti
Virtualizzazione dello Strato di Collegamento
2
Il Servizio di Base offerto dallo
Strato di Collegamento
Il servizio di base offerto dallo Strato di
Collegamento è quello di permettere il trasferimento
di interi datagrammi (cioè, di pacchetti generati dallo
Strato di Rete) da un nodo (utente terminale o
Commutatore) ad uno ad esso adiacente attraverso un
singolo canale fisico.
Il canale fisico che collega una coppia di nodi adiacenti
può essere
o
o
dedicato esclusivamente alla comunicazione della coppia di
nodi in oggetto (canale punto-punto);
Condiviso (ovvero, utilizzato) da più coppie di nodi che
vogliono comunicare tra di loro simultaneamente (canale
broadcast).
3
Strato di Collegamento- Contesto
Operativo
I datagrammi vengono trasferiti da differenti protocolli di
Collegamento mediante canali diversi:
o
esempio: Ethernet sul primo collegamento, rilancio delle
trame sui collegamenti intermedi e 802.11 sull’ultimo
collegamento.
Ogni protocollo di collegamento fornisce servizi differenti.
Analogia
viaggio da Princeton a Losanna
i.
macchina da Princeton fino all’aeroporto JFK;
ii.
aereo dall’aeroporto JFK a Ginevra;
iii.
treno da Ginevra a Losanna.
turista= datagramma
segmento di trasporto= collegamento di comunicazione
modo di trasporto= protocollo dello strato di collegamento.
4
Strato di Collegamento- Servizio di
Base (1/2)
Terminologia:
hosts and router sono i nodi
i canali di comunicazione che
collegano nodi adiacenti lungo
un cammino di comunicazione
sono i collegamenti (link)
o collegamenti wired
o collegamenti wireless
o LANs
il pacchetto di strato-2 è
una trama, datagramma
incapsulato
Lo strato di collegamento ha la
responsabilità di trasferire datagrammi da
un nodo ad un nodo adiacente su un
collegamento che può essere dedicato
(punto-punto) o condiviso (broadcast).
Baccarelli,
Cordeschi, Patriarca, Polli
5
Strato di Collegamento: Servizio di
Base (2/2)
I canali di comunicazione che collegano nodi
adiacenti lungo un cammino sono i collegamenti
(canali trasmissivi o “link”). Essi possono
essere:
o
o
cablati
wireless (radio)
Le unità di dati scambiate dai protocolli a
livello di Strato di Collegamento sono
chiamate trame (frame).
I protocolli a livello di Strato di Collegamento
si occupano del trasporto di Trame lungo un
singolo canale di comunicazione.
6
Modalità di Trasmissione tra coppie
di nodi (1/5)
modalità che una coppia di nodi
possono adottare per trasferire segnali tra di
loro attraverso il canale fisico che li collega?
Quali sono le
7
Modalità di Trasmissione (2/5)
Ad una via (unidirezionale): dalla sorgente S
verso al destinazione D.
S
D
A due vie (bidirezionale): tra 2 terminali T1,
T2.
T1
T2
(Duplexing)
8
Modalità di Trasmissione
Bidirezionale (Duplexing) (3/5)
Duplexing a divisione di frequenza
(FDD: Frequency Division Duplexing)
T1
f1
f2
T2
T1 --> T2 T2 -->T1
f1
f2
B1
B2
Frequenza
(Hz)
Duplexing a divisione di tempo (TDD: Time Division
Duplexing)
T1
T2
T1 --> T2
T2 --> T1
T1 --> T2
T2 --> T1
…
Tempo
(sec)
Duplexing a divisione di spazio
T1
Collegamento 1
Collegamento 2
T2
9
Modalità di Trasmissione
Bidirezionale Full-Duplex e HalfDuplex (4/5)
Consideriamo la trasmissione bidirezionale tra due
terminali (nodi) T1 e T2.
T1
T2
Full-Duplex quando sia T1 che
T2 possono trasmettere e ricevere simultaneamente.
La trasmissione è detta Half-Duplex quando
alternativamente, T1 trasmette e T2 riceve e, poi, T2
trasmette e T1 riceve.
La modalità di trasmissione Full-Duplex è detta anche
bidirezionale simultanea. La modalità di trasmissione
Half-Duplex è detta anche bidirezionale alternata.
La trasmissione è detta
10
Modalità di Trasmissione tra
Sorgente e Destinazione (5/5)
Unicast: da una sorgente S verso una sola destinazione D
(es. telefono)
D
S
Broadcast: da una sorgente
verso tutte le destinazioni
(es. radio, televisione “in
chiaro”)
Multicast: da una sorgente
verso solo alcune
S
destinazioni (es.
televisione “criptata”,
video-conferenza)
D
S
D
D
D
D
D
S
D
D
D
D
11
Ulteriori Servizi offerti dallo Strato
di Collegamento (1/3)
Gli ulteriori servizi che i protocolli di Strato di
Collegamento possono offrire sono:
o
o
o
o
o
o
la delimitazione delle trame (frames);
l’indirizzamento delle trame;
la rivelazione degli (eventuali) errori introdotti dal canale;
il recupero, quando richiesto, del corretto trasferimento
delle trame in caso di errori (controllo di errore mediante
tecniche ARQ);
il controllo della velocità di trasferimento delle trame dal
nodo-sorgente al nodo-destinazione (controllo di flusso);
la gestione (instaurazione, abbattimento e reinizializzazione) della connessione di strato di collegamento.
12
Ulteriori Servizi offerti dallo Strato
di Collegamento (2/3)
Delimitazione di trame (Framing):
o I protocolli incapsulano i datagrammi generati dallo
Strato di Rete all’interno di un frame di Strato di
Collegamento;
o Per identificare origine e destinatario di ciascuna
trama, vengono utilizzati indirizzi di Strato di
Collegamento (detti anche indirizzi MAC).
Trasferimento affidabile dei datagrammi
o E’ considerato non necessario nei collegamenti che
presentano un basso numero di errori (fibra ottica,
cavo coassiale e doppino intrecciato)
o E’ spesso utilizzata nei collegamenti soggetti a
elevati tassi di errori (es.: collegamenti radio)
13
Ulteriori Servizi offerti dallo Strato
di Collegamento (3/3)
Controllo di flusso:
o
Evita che il nodo trasmittente saturi la memoria
tampone presente presso il nodo ricevente.
Rivelazione degli errori:
o
o
gli errori sono causati dall’attenuazione del segnale
e dal rumore;
il nodo ricevente individua la presenza di errori
grazie all’inserimento, da parte del nodo
trasmittente, di bit per il controllo di errore
all’interno delle trame trasmesse.
14
Adattatori (1/3)
Per ogni assegnato canale di comunicazione tra coppie
di nodi adiacenti, il protocollo di Strato di
Collegamento è realizzato in un Adattatore.
Un Adattatore è una scheda PCMCIA (detta anche
Network Interface Card(NIC)) che è costituita da
RAM, DSP chips e linee di collegamento.
Nodo Tr.
Nodo Ric.
Datagramma
Datagramma
Frame
Canale Fisico
Adattatore
Frame
Adattatore
Baccarelli,
Protocollo
di Strato
di Collegamento
Cordeschi,
Patriarca,
Polli
15
Adattatori- Funzionamento (2/3)
L’Adattatore al lato Trasmittente:
i.
Incapsula il datagramma in una trama
(frame);
ii. Invia il frame nel canale fisico.
L’Adattatore al lato Ricevente:
i.
Effettua le funzioni di rivelazione/controllo
degli errori sul frame ricevuto;
ii. Se non sono stati rivelati errori nel frame
ricevuto, estrae il datagramma dal frame e
passa il datagramma allo Strato di Rete
presso il nodo-Ricevente.
16
Adattatori- Funzionamento (3/3)
Tutti i servizi offerti dal protocollo di Strato di
Collegamento sono attuati dagli Adattatori presenti al
Nodo-Tr. e al Nodo-Ric.
Un Adattatore è un sistema Semi-Autonomo, ossia è
un sistema che è in grado di svolgere alcuni servizi
(quali la rivelazione e il controllo degli errori sui frame
ricevuti) autonomamente, ossia senza il controllo dello
Strato di Rete del nodo a cui l’Adattatore appartiene.
Ad esempio, un Adattatore può ricevere un frame,
verificare se il frame contiene errori, e ,se vi sono
errori, scartare autonomamente il frame, senza
interpellare lo Strato di Rete del nodo a cui
l’Adattatore appartiene.
17
Indirizzamento al Livello di Strato di
Collegamento (1/3)
Ciascun Adattatore ha un suo proprio indirizzo, in
generale noto come Indirizzo MAC.
Un indirizzo MAC è costituito da 6 bytes (48 bits) e
il contenuto di ogni byte è espresso mediante una
coppia ordinata di cifre esadecimali.
Le 16 cifre della numerazione esadecimale sono:
0, 1, 2, 3, 4, 5, 6, 7, 8 , 9, A, B, C, D, E, F.
Esempi di indirizzi MAC:
i. 1A- 23- F9- CD- 06- 9B
ii. 88- B2- 2F- 54- 1A- 0F
iii. 49- BD- D2- C7- 56- 2A
18
Indirizzamento MAC (2/3)
Ogni Adattatore ha un unico indirizzo MAC
Indirizzo Broadcast=
FF-FF-FF-FF-FF-FF
1A-2F-BB-76-09-AD
= Adattatore
71-65-F7-2B-08-53
LAN
(wired o
wireless)
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
19
Proprietà degli Indirizzi MAC (3/3)
uno e uno solo
indirizzo MAC (unicità dell’Indirizzamento MAC).
L’indirizzo MAC è permanente, ossia non cambia
quando l’adattatore cambia area geografica di
funzionamento.
L’indirizzo MAC è piatto (ossia, non è di tipo
gerarchico). Ciò significa che non vi è alcun legame tra
l’indirizzo MAC di un adattatore e la regione
geografica in cui l’adattatore si trova ad operare.
L’indirizzo MAC per frames di tipo Broadcast (cioè,
per frames che hanno come destinatari tutti gli
adattatori presenti nella rete) è:
FF-FF-FF-FF-FF-FF
Ad ogni Adattatore corrisponde
20
Servizi Offerti dallo Strato di
Collegamento
21
Servizio di Rivelazione degli Errori
(1/3)
Ha lo scopo di rivelare la presenza di eventuali
errori introdotti dal canale trasmissivo e
presenti (eventualmente) nel frame ricevuto
dal nodo-destinazione.
Per essere attuato, è richiesto l’impiego di un
codice a rivelazione degli errori.
Poiché la capacità di rivelazione degli errori di
un (qualsiasi) codice è sempre finita, non
rivelare errori nel frame ricevuto non assicura
che il frame ricevuto è privo di errori.
22
Attuazione della Rivelazione degli
Errori (2/3)
EDC= Error Detection and Correction
D= Dati che devono essere protetti da errori e ai quali
vengono aggiunti dei bit EDC.
Datagram
Datagram
Yes
All
Bits in D’ OK?
detection
Error-chiedi la
ritrasmissione del frame
d data bits
D
No
EDC
D’
EDC’
Bit-error prone link
23
Servizio di Rivelazione degli Errori
(3/3)
riveli errori
nel frame ricevuto, il nodo ricevente chiede al
nodo trasmittente di ri-trasmettere di nuovo
il frame in oggetto.
Nel caso in cui il nodo ricevente
Quindi, il Servizio di Rivelazione degli errori è
sempre attuato in congiunzione col Servizio di
Controllo degli Errori mediante strategie di
Automatic Repeat Request (Sistemi ARQ).
24
Servizio di Recupero degli
Errori mediante Strategie di
tipo ARQ
25
Trasferimento Dati AffidabileDefinizione (1/2)
Supponiamo che il nodo NT trasmetta frame
al nodo NR attraverso un canale che
introduce errori.
Per definizione, il trasferimento di frame da
NT a NR è detto affidabile se:
i.
ii.
iii.
Tutti i frame sono ricevuti da NR senza errori;
Ciascun frame privo di errori è ricevuto da NR
una ed una sola volta (no duplicazione di frame
corretti);
I frame corretti sono ricevuti da NR nello stesso
ordine in cui sono stati trasmessi da NT.
26
Trasferimento Dati Affidabile
(2/2)
Lo scopo del Servizio di Recupero degli errori è quello
di dar luogo ad un trasferimento di frame affidabile
impiegando un canale trasmissivo che introduce errori
nei frame in transito.
Processo
trasmittente
Processo
ricevente
Processo
trasmittente
Protocollo
X affidabilità
Canale affidabile
Processo
ricevente
Protocollo
X affidabilità
Canale
Canale non
non affidabile
affidabile
27
Schema Generale di un Sistema ARQ
di tipo punto-punto (1/3)
Nodo
sorgente
Frame trasmesso
Riscontro (ACK/NACK)
Canale diretto
Canale di
Ritorno
Frame trasmesso
Nodo
destinazione
Riscontro (ACK/NACK)
E’ supposto che:
Il Canale Diretto possa introdurre errori e/o perdite, così che il
frame ricevuto non coincida col frame trasmesso o non venga mai
ricevuto.
Il Canale di Ritorno non introduca errori, ma possa introdurre
perdite, così che uno o più messaggi di riscontro (ACK o NACK)
generati dal Nodo-Destinazione potrebbero non raggiungere mai
il Nodo-Sorgente.
28
Parametri Principali di un Sistema
ARQ (2/3)
I parametri principali che definiscono il funzionamento di
un sistema ARQ sono:
o C (bit/sec) capacità trasmissiva del canale diretto;
o v (m/sec) velocità di propagazione del segnale
elettrico nel Canale Diretto;
o dmax(m) distanza massima tra il Nodo-Sorgente e il
Nodo-Destinazione;
o τ dmax/v (sec) ritardo di propagazione del segnale
elettrico dal Nodo-Sorgente al Nodo-Destinazione;
o Lmin (bit) lunghezza minima di una trama;
o Lmax (bit) lunghezza massima di una trama;
o Tt Lmax/C (sec) tempo richiesto per trasmettere una
trama di lunghezza massima;
o Tout (sec) intervallo (o tempo) di Time-Out.
o v!
29
o v!
Principio Generale dei Sistemi ARQ
(3/3)
Nei sistemi ARQ, a ciascun frame da trasmettere si
aggiunge un campo che contiene un codice per la rivelazione
degli errori. Una volta rivelato l’(eventuale) errore nel
frame ricevuto, il Nodo-Destinazione deve comunicare
questa situazione al Nodo-Sorgente, affinchè quest’ultimo
provveda a ri-trasmettere i frame ricevuti con errore. Per
questo motivo, i Sistemi ARQ prevedono sempre la
presenza di un Canale di Ritorno dal Nodo-Destinazione al
Nodo-Sorgente.
Poiché uno stesso frame potrebbe essere ri-trasmesso più
volte, i Sistemi ARQ richiedono sempre la presenza di un
buffer dal Nodo-Sorgente, dove vengono temporaneamente
memorizzati i frame trasmessi e che sono in attesa di un
riscontro positivo da parte del Nodo-Destinazione.
30
Classificazione dei Sistemi ARQ (1/2)
I protocolli ARQ si suddividono in Stop and Wait e
Continuous ARQ.
Nel protocollo Stop and Wait, il Nodo-Sorgente invia un
frame e, quindi, aspetta di ricevere un riscontro positivo
(ACK) da parte del Nodo-Destinazione prima di
procedere alla trasmissione di un nuovo frame.
Nei protocolli Continuous ARQ, il Nodo-Sorgente può
trasmettere con continuità frame che vengono, però,
opportunamente numerate, così che il Nodo-Destinazione
possa ri-posizionarle nell’ordine corretto.
A loro volta, i protocolli Continuous ARQ si suddividono
in:
i.
Protocollo Go-Back-m (GBm)
ii. Protocollo Selective Repeat (SR)
31
Classificazione dei Sistemi ARQ
(2/2)
Recupero degli errori
Protocolli ARQ
Stop and Wait
(SaW)
Countinuous
ARQ
Go-Back-m
(GBm)
Selective Repeat
(SR)
32
Strategie impiegate nei Sistemi ARQ
Per ottenere un trasferimento di frame affidabile
mediante un canale diretto che introduce errori e/o
perdite, i sistemi ARQ fanno (opportuno) impiego
delle seguenti 3 strategie di base:
i.
ii.
iii.
iv.
I frame trasmessi vengono numerati progressivamente,
come anche i corrispondenti riscontri (ACK/NACK);
Il Nodo-Destinazione invia nel canale di ritorno opportuni
messaggi di riscontro positivo (ACK) oppure negativo
(NACK);
Il Nodo-Sorgente impiega un Temporizzatore (Timer) per
misurare il tempo trascorso dalla trasmissione di un frame;
Si impiegano buffer in trasmissione (sempre) e in ricezione
(talvolta) per la memorizzazione temporanea dei frame
trasmessi e di (alcuni) di quelli ricevuti.
33
Numerazione “Ciclica” dei Frame e dei
Riscontri (1/4)
Nei protocolli Continuous ARQ si possono
trasmettere più trame consecutivamente in
attesa dei riscontri (positivi o negativi) sulle
prime trame trasmesse.
Ciò richiede un meccanismo di numerazione delle
trame trasmesse e dei corrispondenti riscontri
(positivi o negativi) per far si che le trame
trasmesse, ma non ancora riscontrate
positivamente, abbiano un numero di sequenza NS
per consentire al Nodo-Sorgente e al NodoDestinazione di intendersi su quali trame sono
state ricevute correttamente e quali no.
34
Numerazione “Ciclica” dei Frame e dei
Riscontri (2/4)
Indichiamo con:
o
o
o
b (bit) numero (intero) di bit a
disposizione per numerare le trame;
M 2b numero di numeri di trama
distinti;
NS numero di sequenza di una (generica)
trama.
35
Numerazione “Ciclica” dei Frame e dei
Riscontri (3/4)
Allora, si ha che:
La numerazione NS delle trame è ciclica modulo-M, con ciò
intendendo dire che NS può assumere solo i seguenti M 2b
valori distinti:
NS ∊ {0,1,2,3,…,M-2,M-1}.
Per esempio, se b=3, le trame vengono trasmesse con i seguenti
numeri di sequenza consecutivi:
0,1,2,3,4,5,6,7,0,1,2,…
Dato un (qualsiasi) numero intero (non negativo) x, per
definizione, l’operazione
(x) mod.M
sta ad indicare il resto della divisione intera di x per M. Quindi, il
suddetto resto è sempre un numero intero compreso tra 0 e
(M-1).
36
Numerazione “Ciclica” dei Frame e dei
Riscontri (3/3)
Ad esempio,
(0) mod.8 = (8) mod.8 = (16) mod.8 ≡ 0;
(7) mod.8 = (15) mod.8 = (23) mod.8 ≡ 7;
(12) mod.8 = (20) mod.8 = (28) mod.8 ≡ 4.
Gli esempi precedenti mostrano che la
numerazione mod.M delle trame può dar
luogo ad ambiguità, con ciò intendo dire che:
i.
ii.
dato M;
dato il risultato di (x) mod.M;
non è univocamente calcolabile il numero x
che è il dividendo dell’operazione mod.M.
37
Riscontri Positivi e Negativi (1/5)
Per indicare che la trama con numero di sequenza
NS=i è stata rivelata priva di errori, il NodoDestinazione invia indietro al Nodo-Sorgente
attraverso il canale di ritorno un messaggio di
riscontro positivo che reca il numero di sequenza NS=i
della trama riscontrata, ossia il messaggio:
ACK(i).
Per definizione, in tutti i protocolli ARQ, il riscontro
ACK(i) ha il seguente significato:
o
Tutte le trame sino alla i-ma compresa sono state rivelate
prive di errori (ricevute correttamente) dal NodoDestinazione.
38
Riscontri Positivi e Negativi (2/5)
Per indicare che la trama con numero di
sequenza NS=s è stata rivelata con errori (è
corrotta da errori), il Nodo di Destinazione
invia indietro al Nodo-Sorgente attraverso il
canale di ritorno un messaggio di riscontro
negativo che reca il numero di sequenza NS=s
della trama riscontrata negativamente, ossia il
messaggio:
NACK(s).
Per definizione, il protocollo SaW non impiega
messaggi di riscontro negativi.
39
Riscontri Positivi e Negativi (3/5)
Per definizione, nel protocollo Go-Back-m, il
messaggio NACK(s) significa:
o la trama s-ma è stata ricevuta con errori,
ma tutte le trame precedenti (sino alla
(s-1)-ma compresa) sono state ricevute
correttamente.
Per definizione, nel protocollo SR, il messaggio
NACK(s) significa:
o La trama s-ma è stata ricevuta con errori.
40
Riscontri Positivi e Negativi (4/5)
In tutti i protocolli ARQ, una stessa trama è
ri-trasmessa dal Nodo-Sorgente una o più
volte, finchè il Nodo-Sorgente non riceve da
parte del Nodo-Destinazione un riscontro
positivo (ACK) relativo alla trama in oggetto.
Al Nodo-Destinazione, una trama con lo
stesso numero di sequenza può essere
ricevuta più volte, dando così luogo al
fenomeno della Duplicazione della trama.
41
Riscontri Positivi e Negativi (5/5)
Duplicazioni di Trama al Nodo-Destinazione
possono aver luogo per 2 motivi diversi:
i.
ii.
È il Nodo-Destinazione ad avere richiesto
(mediante invio di un NACK) la ri-trasmissione di
una trama che era stata ricevuta con errori;
È il Nodo-Sorgente che spontaneamente ritrasmette una trama che aveva già trasmessa,
perché il Nodo-Sorgente non ha ricevuto il
riscontro positivo ( messaggio ACK) relativo alla
trama in oggetto.
42
Temporizzatori e Time-Out (1/3)
Poiché il Canale di Ritorno e il Canale Diretto possono
introdurre perdite, può accadere che uno (o più) messaggi
di riscontro positivo relativi al frame s-mo non siano mai
ricevuti dal Nodo-Sorgente e/o che uno o più frame non
siano mai ricevuti dal Nodo-Destinazione.
Per ovviare a questo inconveniente, in tutti i protocolli
ARQ, il Nodo-Sorgente:
i.
Avvia un Temporizzatore (Timer) nell’istante in cui inizia
a trasmettere la trama s-ma;
ii.
Aspetta per un prefissato tempo di Time-Out (Tout) di
ricevere un riscontro (positivo o negativo) da parte del
Nodo-Destinazione relativamente alla trama s-ma;
iii.
Se non ha ricevuto alcun riscontro (né positivo, né
negativo), allo scadere del tempo di Tout, il NodoSorgente ri-trasmette spontaneamente la trama s-ma.
43
Temporizzatori e Time-Out (2/3)
Poiché
i.
il Temporizzatore è avviato nell’istante in cui la trama sma inizia ad essere trasmessa;
ii.
il Tempo necessario per trasmettere una trama di
dimensione massima è Tt≡
Lmax/C (sec);
iii.
poiché il segnale elettrico impiega un tempo
τ dmax/v per propagarsi dal Nodo-Sorgente al NodoDestinazione (tempo di propagazione di una trama), e, poi,
un altro tempo τ per propagarsi dal Nodo-Destinazione al
Nodo-Sorgente (tempo di propagazione del messaggio di
riscontro), allora il Tempo di Time-Out (Tout ) deve
soddisfare il seguente limite:
Tout ≥ Tt+2 τ
44
Temporizzatori e Time-Out (3/3)
In tutti i protocolli ARQ, il Nodo-Sorgente
impiega uno e un solo Temporizzatore.
Specificatamente, in ogni istante t0 di
funzionamento del Sistema ARQ, il
Temporizzatore è sempre associato dal NodoSorgente al frame trasmesso e non ancora
riscontrato positivamente che, tra tutti i
frame trasmessi e non ancora riscontrati
positivamente, è quello che è stato trasmesso
per primo (ossia, il frame trasmesso e non
ancora riscontrato positivamente più anziano).
45
Buffer di memoria
Tutti i protocolli ARQ impiegano, al Nodo-Sorgente,
un Buffer di Trasmissione in cui vengono
temporaneamente memorizzati i frame che sono già
stati trasmessi almeno una volta, ma che non sono
ancora stati riscontrati positivamente.
Solo il protocollo SR richiede, al NodoDestinazione, un Buffer di Ricezione in cui vengono
i.
memorizzati temporaneamente;
ii.
ordinati sequenzialmente in accordo ai Numeri di
Sequenza,
le trame che sono state ricevute correttamente.
46
Esempio di Numerazione delle trame
(1/2)
Ogni trama contiene un
numero di sequenza (nell’esempio,
NS∊
{0,1}).
o Il numero di sequenza NS è il numero d’ordine sequenziale
caratterizzante la trama uscente dal Nodo-Sorgente.
NodoSorgente
Tout
0
NodoDestinazione
ACK(1)
0
0
Tout
1
ACK(1)
0 (duplicata)
ACK(0)
0
1
La ricezione di trame consecutive recanti lo
numero di sequenza è indice di duplicazione.
0
stesso valore del
47
Esempio di Numerazione delle trame
(2/2)
È necessario numerare anche i riscontri,
altrimenti il Nodo-Sorgente non sarebbe in
grado di sapere a quale trama fa riferimento il
riscontro ricevuto (i riscontri possono
perdersi; nell’esempio NS∊ {0,1}).
NodoSorgente
0
Tout
NodoDestinazione
0
1
ACK
0
?
Tout
ACK
0 (duplicata)
1
48
Esempi di uso dei temporizzatori
Temporizzatori
Si introducono dei meccanismi di temporizzazione:
quando il Nodo-Sorgente emette una trama fa
contemporaneamente partire un temporizzatore allo
scadere del quale la trama viene ri-trasmessa dal
Nodo-Sorgente.
Nodo- Trama 1
Sorgente
Tout
Trama 1
Trama 2
tempo
ACK
ACK
NodoDestinazione
tempo
1
2
49
Protocollo Stop-and-Wait (SaW)
(1/6)
Il principio generale del protocollo SaW è che il NodoSorgente non trasmette la prossima trama se non ha
ricevuto un riscontro positivo (ACK) relativo alla trama
correntemente trasmessa.
Nel protocollo SaW, il Nodo-Sorgente opera come segue:
i.
numera la trama da trasmettere, avvia il
temporizzatore (Timer), trasmette la trama e,
contemporaneamente, la memorizza nel Buffer di
Trasmissione;
ii.
se riceve l’ACK prima che scada il Timer, allora il
Nodo-Sorgente rimuove la trama dal Buffer di
Trasmissione e, poi, passa a trasmettere il frame
successivo;
iii.
se il Timer scade prima di ricevere l’ACK, allora il
Nodo-Sorgente ri-inizializza il Timer e, poi,
ritrasmette il frame memorizzato nel Buffer di
Trasmissione.
50
Protocollo Stop-and-Wait (SaW)
(2/6)
Nel protocollo SaW, il Nodo-Destinazione opera
come segue sul frame correntemente ricevuto:
i.
ii.
iii.
iv.
applica la decodifica a rivelazione di errore;
se il frame ricevuto è corrotto da errori, allora il NodoDestinazione scarta il frame e non invia alcun messaggio al
Nodo-Sorgente;
se il frame è ricevuto correttamente ed ha lo stesso
numero di sequenza del frame ricevuto precedentemente,
allora il Nodo-Destinazione scarta il frame (frame
duplicato) e, poi, invia un messaggio ACK al Nodo-Sorgente;
se il frame è ricevuto correttamente e non ha lo stesso
numero di sequenza del frame ricevuto precedentemente,
allora il Nodo-Destinazione accetta il frame e, poi, invia un
messaggio ACK al Nodo-Sorgente.
51
Protocollo Stop-and-Wait (SaW)
(3/6)
inutilizzato
negli intervalli di tempo intercorrenti tra la fine della
trasmissione del frame corrente e l’istante di ricezione
dell’ACK o quello di superamento di Tout.
Poiché il Nodo-Sorgente non trasmette un nuovo frame
prima che quello attualmente sotto trasmissione sia stato
riscontrato positivamente, nel protocollo SaW il numero di
sequenza NS assume solo i due valori {0,1} (ossia, b=1 e M
2b ≡2).
Specificatamente, il Nodo-Sorgente numera
alternativamente le trame trasmesse con NS=0 e NS=1. Il
Nodo-Destinazione può accettare solo trame consecutive
con numerazione alternata. Quando il Nodo-Destinazione
riceve due trame consecutive prive di errori e con lo
stesso numero di sequenza, il Nodo-Destinazione scarta la
seconda trama ricevuta in quanto è trama duplicata.
Nel protocollo SaW, il Canale Diretto rimane
52
Protocollo Stop-and-Wait (SaW)
(4/6)
Riscontri
il principio è quello per cui il Nodo-Sorgente non invia
la prossima trama se non riceve il riscontro relativo a
quella precedentemente trasmessa.
NodoSorgente
Trama 0
Trama 1
Tout
Trama 1
ACK
NodoDestinazione
ACK
Diagramma spazio tempo
Trama 0 consegnata
allo strato superiore
Trama 1 consegnata
allo strato superiore
53
Protocollo SaW: Azioni del NodoSorgente (5/6)
Inizializza Numero Sequenza
NS:=0
Preleva nuovo datagramma
Dat e costruisci nuovo frame
F: = < NS, DAT >
Aggiorna NS
NS : = NS+1
Memorizza F in Buffer
Trasmissione
Ri-trasmetti
F
Inizializza Timer
Ri-inizializza
Timer
Preleva frame F dal
Buffer di
Trasmissione
Rimuovi F dal Buffer di
Trasmissione
SI
Ricevuto ACK ?
SI
NO
NO
Timer > Tout
54
Protocollo SaW: Azioni del Nodo-Destinazione
(6/6)
Inizializza Numero Atteso di Sequenza
X : =0
Hai ricevuto un frame
F dal Canale Diretto?
NO
Attendi
SI
Hai rivelato errori
in F
Aggiorna Numero Atteso di
Sequenza
X : = (X+1)mod.2
Scarta
F
NO
Invia ACK
Estrai Numero di Sequenza NS da F
Invia ACK
Accetta F
SI
SI
NO
NS è uguale a x ?
Scarta
Frame F
(F è
duplicato)
55
Protocollo Go-Back-m (GBm) (1/8)
Nel protocollo Go-Back-m, il Nodo-Sorgente
mantiene una finestra di emissione WS di
dimensione m dove sono via via memorizzati i
numeri di sequenza NS che il Nodo-Sorgente
può trasmettere consecutivamente, senza,
cioè, attendere alcun riscontro positivo da
parte del Nodo-Destinazione.
In altri termini, il numero (intero) m ≥ 1 nel
nome stesso del protocollo indica il numero
massimo di trame che il Nodo-Sorgente può
trasmettere consecutivamente in assenza di
alcun riscontro positivo da parte del NodoDestinazione.
56
Protocollo Go-Back-m (GBm) (2/8)
Nel protocollo GBm, il Nodo-Destinazione accetta
le trame ricevute solo se:
i.
non vi rileva errori e, inoltre,
ii.
esse sono rigidamente in sequenza.
Se una trama è ricevuta con errore, allora il NodoDestinazione:
i.
scarta la trama in oggetto;
ii.
richiede la ri-trasmissione della trama in
oggetto;
iii.
scarta anche tutte le trame ricevute dopo la
ricezione della trama con errore, e questo anche
se le suddette trame sono state ricevute
correttamente.
57
Protocollo Go-Back-m: NodoSorgente (3/8)
Specificatamente, nel protocollo GBm, il NodoSorgente opera come segue:
i.
ii.
iii.
trasmette al massimo, WS ≡ m trame consecutive senz
attendere alcun riscontro positivo;
memorizza temporaneamente nel Buffer di Trasmissione
le trame trasmesse e delle quali non ha ancora ricevuto un
riscontro positivo;
quando riceve il riscontro ACK(i), allora:
o
rimuove dal Buffer di Trasmissione tutti i frames con
Numero di Sequenza: NS ≤ i;
o
trasmette tutti i frames con numero di sequenza
compreso tra:
(i+1) ≤ NS ≤ (i+m),
e che non sono mai stati ancora trasmessi.
o
Infine, memorizza nel Buffer di Trasmissione i frames
che sono stati correttamente trasmessi;
58
Protocollo Go-Back-m: NodoSorgente (4/8)
quando riceve NACK(j), allora:
iv.
o
o
ri-trasmette il frame j-mo;
ri-trasmette anche tutti i frames già trasmessi e con
numero di sequenza NS strettamente maggiore di j;
quando riceve un riscontro (positivo o negativo),
allora:
v.
o
vi.
o
o
inizializza il Timer;
quando il Timer scade (ossia quando Timer> TOUT,
allora:
ri-inizializza (cioè pone a zero) il Timer;
ri-trasmette il frame già trasmesso, ma non ancora
riscontrato positivamente e che, tra tutti i frames già
trasmessi, ma non ancora ri-scontrati, è quello col
numero di sequenza NS più piccolo (ossia, il frame “più
vecchio”).
59
Protocollo Go-Back-m: NodoDestinazione (5/8)
Nel protocollo GBm, il Nodo-Destinazione opera
come segue su ciascun frame ricevuto dal canale
diretto:
i.
Applica la procedure di rivelazione di errori;
ii.
Se sono stati rivelati errori, allora:
o
invia al Nodo-Sorgente il messaggio NACK(j),
dove j è il numero di sequenza del frame con
errori;
o
scarta tutti i frame ricevuti dal Canale
Diretto e con numero di sequenza
strettamente maggiore di j.
60
Protocollo Go-Back-m: NodoDestinazione (6/8)
iii.
iv.
Se non sono stati rivelati errori e il frame
ricevuto non è un frame duplicato, allora:
o
accetta il frame ricevuto;
o
invia al Nodo-Sorgente il messaggio ACK(j),
dove j è il numero di sequenza del frame
ricevuto;
Se non sono stati rivelati errori e il frame
ricevuto è un frame duplicato, allora:
o
scarta il frame ricevuto;
o
invia al Nodo-Sorgente il messaggio ACK(j),
dove j è il numero di sequenza del frame
ricevuto.
61
Protocollo Go-Back-m: Azioni del
Nodo-Sorgente (7/8)
Inizializza Timer
Timer : = 0
Trasmetti m frame
consecutivi
Trasmetti tutti i frame
non ancora trasmessi e
con NS compreso tra
(i+1)<=NS<= (i+m)
Timer : =0
Timer > Tout
Rimuovi dal Buffer di
Trasmissione tutti i
frame con numeri di
Sequenza:
NS<=i
Tra tutti i frame trasmessi
e non ancora riscontrati, ritrasmetti quello col NS più basso
Memorizza frames Trasmessi
nel Buffer di Trasmissione
SI
Timer : =0
NO
SI
Ricevuto ACK (i)?
NO
Ricevuto NACK (j)?
NO
SI
Timer : =0
Baccarelli,
Cordeschi, Patriarca, Polli
Ritrasmetti il frame j-mo
E, poi, tutti i frames già
Trasmessi dopo il frame j-mo
62
Protocollo Go-Back-m: Azioni del
Nodo-Destinazione (8/8)
Inizializza Numero Atteso di Sequenza
X : = 0
Hai ricevuto un frame F
dal Canale Diretto?
Attendi
SI
Estrai Numero di
Sequenza NS dal frame
F
Invia
ACK (NS)
Aggiorna il Numero
Atteso di Sequenza:
X : = (NS+1) mod. M
NS = X ?
NO
Scarta il frame
F
Invia
NACK (NS)
SI
Accetta
Frame F
NO
Hai rivelato errori
nel frame F ?
Baccarelli,
Cordeschi, Patriarca, Polli
SI
Scarta
Frame F
63
Protocollo Selective Repeat (SR)
(1/15)
Nel protocollo SR, il Nodo-Sorgente può trasmettere
consecutivamente un numero massimo di trame WS ≥ 1
senza bisogno di ricevere alcun riscontro positivo dal
Nodo-Destinazione.
Il Nodo-Destinazione può accettare un numero
massimo di trame WR ≥ 1 anche se ricevute non in
ordine; ciò richiede la presenza presso il NodoDestinazione di un Buffer di Ricezione che consenta
di ripristinare l’ordine corretto delle trame ricevute,
affinchè i Datagrammi da esse trasportati possano
essere consegnati in ordine sequenziale allo Strato di
Rete del Nodo-Destinazione.
64
Protocollo SR (2/15)
Nel protocollo SR, il riscontro NACK(i) indica
che il solo frame i-mo deve essere
ritrasmesso dal Nodo-Sorgente, ma non indica
che tutti i frame precedenti l’i-mo sono stati
ricevuti correttamente.
Nel protocollo SR, il riscontro ACK(i) indica
che il frame i-mo e tutti quelli precedenti
sono stati ricevuti correttamente dal NodoDestinazione.
65
Protocollo SR- Finestre di
Trasmissione e Ricezione (3/15)
Nel protocollo SR,
il Nodo-Sorgente mantiene e aggiorna una finestra che
contiene WS ≥ 1 numeri di sequenza consecutivi. La
suddetta finestra è detta Finestra di Trasmissione, e, in
ogni istante, contiene i numeri di sequenza dei frame che il
Nodo-Sorgente può trasmettere consecutivamente senza
bisogno di attendere riscontri da parte del NodoDestinazione;
il Nodo-Destinazione mantiene ed aggiorna una finestra
che contiene WD ≥ 1 numeri di sequenza consecutivi. La
suddetta finestra è detta Finestra di Ricezione, e, in ogni
istante, contiene i numeri di sequenza dei frame che il
Nodo-Destinazione è disposto ad accettare, anche se
ricevuti non in ordine sequenziale.
66
Protocollo SR- Finestre di
Trasmissione e Ricezione (4/15)
In ogni istante,
i.
il Nodo-Sorgente non può trasmettere (o ritrasmettere) frame i cui Numeri di Sequenza non
cadano nella Finestra di Trasmissione corrente;
ii.
il Nodo-Destinazione non può accettare trame i
cui numeri di sequenza non cadano nella corrente
Finestra di Ricezione, anche se le suddette
trame sono state ricevute correttamente.
67
Protocollo SR- Aggiornamento della
Finestra di Trasmissione (5/15)
Indichiamo con IS ≥ 0 l’estremo inferiore
corrente della Finestra di Trasmissione,
ossia il più piccolo Numero di Sequenza che
fa correntemente parte della Finestra di
Trasmissione. Allora:
i.
la Finestra di Trasmissione corrente è costituita
da tutti i Numeri di Sequenza NS compresi tra
IS ≤ NS ≤ ( IS + WS – 1) mod. M
68
Protocollo SR- Aggiornamento della
Finestra di Trasmissione (6/15)
ii.
Quando il Nodo-Sorgente riceve un
riscontro ACK(i), allora aggiorna il valore di
IS in accordo a :
IS:= (i+1) mod. M
iii.
Poiché i riscontri ACK(i) ricevuti dal NodoSorgente hanno Numero di Sequenza
incrementale, e poiché, alla ricezione di ciascun
ACK(i), il Nodo-Sorgente aggiorna (ovvero
incrementa) IS, la Finestra di Trasmissione è
detta anche Finestra Mobile (Sliding Window).
69
Protocollo SR- Aggiornamento della
Finestra di Ricezione (7/15)
Indichiamo con ID ≥ 0 l’estremo inferiore
corrente della Finestra di Ricezione, ossia il
più piccolo Numero di Sequenza che il NodoDestinazione è correntemente in grado di
accettare.
Allora,
i.
La Finestra di Ricezione corrente è costituita da
tutti i Numeri di Sequenza compresi tra:
ID ≤ NS ≤ ( ID+ WD– 1) mod. M.
70
Protocollo SR- Aggiornamento della
Finestra di Ricezione (8/15)
ii.
Dopo aver inviato al Nodo-Sorgente un riscontro positivo
ACK(j), il Nodo-Destinazione aggiorna ID in accordo a:
ID := (NSMAX + 1 ) mod. M,
iii.
dove NSMAX è il valore più alto del Numero di Sequenza
dei frame che il Nodo-Destinazione ha ricevuto senza
errori e in ordine sino all’istante corrente.
In generale, NSMAX ≥ J. Quindi, poiché, ad ogni invio di un
riscontro ACK(.), l’estremo inferiore ID della Finestra di
Ricezione assume un valore non inferiore a quello assunto
precedentemente, anche la Finestra di Ricezione è una
Finestra Mobile (Sliding Window).
71
Protocollo SR- Nodo Sorgente (9/15)
Nel protocollo SR, il Nodo-Sorgente opera come
segue:
i.
ii.
senza attendere alcun riscontro, il NodoSorgente trasmette tutti i frame che non sono
già stati trasmessi e i cui Numeri di Sequenza
cadono nella Finestra di Trasmissione corrente;
memorizza temporaneamente nel Buffer di
Trasmissione le trame trasmesse e delle quali
non ha ancora ricevuto un riscontro positivo;
72
Protocollo SR- Nodo Sorgente
(10/15)
i.
quando riceve il riscontro ACK(i), allora:
o
rimuove dal Buffer di Trasmissione tutti i frames
con Numeri di Sequenza: NS ≤ i;
o
aggiorna IS in accordo a: IS:= (i+1) mod. M;
o
trasmette tutti i frame che non sono stati
ancora trasmessi e che hanno un Numero di
Sequenza compreso tra:
IS ≤ NS ≤ ( IS + WS – 1) mod. M;
o
memorizza i frame trasmessi nel Buffer di
Trasmissione.
73
Protocollo SR- Nodo Sorgente (11/15)
quando riceve NACK(j), allora
iv.
o
ri-trasmette solo il frame j-mo;
quando riceve un riscontro (positivo o
negativo), allora
v.
o
inizializza il Timer;
quando il Timer scade (ossia quando Timer >
TOUT )
vi.
o
o
ri-inizializza il Timer;
tra tutti i frame già trasmessi e non riscontrati
positivamente, ri-trasmette quello con il Numero
di Sequenza più piccolo.
74
Protocollo SR- Nodo Destinazione
(12/15)
Nel protocollo SR, il Nodo-Destinazione
estrae il Numero di Sequenza NS dal frame
F correntemente ricevuto dal Canale Diretto
e, quindi:
se NS non cade nella Finestra di Ricezione
corrente, allora il Nodo-Destinazione scarta il
frame F ricevuto;
se NS cade nella Finestra di Ricezione corrente
e in F sono rivelati errori, allora il NodoDestinazione:
i.
ii.
o
o
scarta il frame F ricevuto;
Invia al Nodo-Sorgente il riscontro NACK(NS).
75
Protocollo SR- Nodo Destinazione
(13/15)
Se NS cade nella Finestra di Ricezione corrente e
in F non sono rivelati errori, allora il NodoDestinazione:
iii.
o
o
o
o
pone F nel Buffer di Ricezione;
ri-ordina i frame correntemente contenuti nel Buffer di
Ricezione secondo Numeri di Sequenza crescenti;
invia al Nodo-Sorgente il riscontro ACK(NS);
aggiorna l’estremo inferiore ID della Finestra di Ricezione
in accordo a:
ID := (NSMAX + 1 ) mod. M
o
preleva dal Buffer di Ricezione tutti i frame ivi contenuti
con Numeri di Sequenza strettamente consecutivi e li
passa allo Strato di Rete del Nodo-Destinazione.
76
Protocollo SR- Azioni del Nodo
Sorgente (14/15)
Inizializza
IS : = 0 e Timer : = 0
Trasmetti tutti i frame non ancora
trasmessi e con Numero di
Sequenza NS:
IS ≤ NS ≤ ( IS + WS – 1) mod. M
Memorizza frame trasmessi nel
Buffer di Trasmissione
Timer : = 0
Elimina dal Buffer di
Trasmissione tutti i frame con
NS ≤ ( i )
IS : = ( i+1 ) mod.M
Ritrasmetti il frame
non ancora riscontrato
e con Numero di
Sequenza più piccolo
Timer > Tout
SI
Timer : =0
NO
SI
Ricevuto ACK (i)?
Ritrasmetti solo il
frame j-mo
NO
NO
Baccarelli,
Ricevuto
NACK (j)?
Cordeschi, Patriarca, Polli
SI
Timer : =0
77
Protocollo SR- Azioni del Nodo
Destinazione (15/15)
Inizializza
ID : = 0
Hai ricevuto un frame
F dal Canale Diretto?
Preleva dal Buffer di
Ricezione tutti i frame con
Numeri di Sequenza
strettamente consecutivi
Attendi
Estrai da F il Numero di Sequenza
NS
Aggiorna ID come in
ID : = ( NSmax + 1 ) mod.M
E’ NS compreso nella
Finestra di Ricezione
[ID, (ID + WD – 1 ) mod.M ]
?
Invia ACK(NS)
Memorizza F nel Buffer di
Ricezione.
Ri-ordina il Buffer di
Ricezione
NO
NO
Scarta F
SI
NO
Sono rivelati errori in
F ?
Baccarelli,
Cordeschi, Patriarca, Polli
SI
Invia NACK (NS)
78
Ambiguità nella Numerazione
delle Sequenza nel protocollo SR
(1/3)
Come già osservato, la Numerazione delle
Sequenze è mod.M, con M2b, b ≥1. La
numerazione mod.M può dar luogo ad
ambiguità.
79
Ambiguità nella Numerazione delle
Sequenza nel protocollo SR (2/3)
Esempio di ambiguità di numerazione
o
Supponiamo M=23=8 ed anche WS=8.
o
Assumiamo che il Nodo-Sorgente trasmetta 8 trame
consecutive, con Numeri di Sequenza pari a: 4, 5, 6, 7, 0, 1,
2, 3.
o
Il Nodo-Ricevente invia indietro al Nodo-Sorgente il
riscontro positivo ACK(3).
o
Purtroppo, il Nodo-Sorgente può interpretare ACK(3) in
due modi diversi:
i.
Il Nodo-Destinazione ha ricevuto correttamente tutte
le 8 trame trasmesse
ii.
Il Nodo-Destinazione non ha ricevuto correttamente
nessuna delle 8 trame trasmesse, e il messaggio ACK(3)
si riferisce alla trama con NS=3 che era già stata
trasmessa prima della trasmissione della trama con
NS=4.
80
Ambiguità nella Numerazione delle
Sequenza nel protocollo SR (3/3)
Si può dimostrare che, nel protocollo SR, l’ambiguità
di numerazione delle trame è eliminata se le
dimensioni WS e WD delle finestre di trasmissione e di
ricezione soddisfano alla seguente disuguaglianza:
WS+WD ≤ M2b
Tipicamente, nel protocollo SR si pone
WS ≡WD = M/2.
81
Confronto Complessità-Prestazioni
tra i protocolli ARQ (1/2)
Tutti e tre i protocolli ARQ ri-trasmettono uno stesso frame sin
tanto che non ricevono un riscontro positivo. Quindi, tutti e tre i
protocolli danno luogo alla stessa Probabilità di Errore residua e,
da questo punto di vista, sono equivalenti.
Il protocollo SaW trasmette un frame e poi si arresta sino alla
ricezione del corrispondente riscontro. I protocolli GBm e SR
trasmettono senza mai interrompersi nuovi frame o frame
riscontrati negativamente. Quindi il protocollo SaW è quello che
utilizza di meno la capacità trasmissiva del Canale Diretto.
Il protocollo SR ri-trasmette solo i frame in cui il NodoDestinazione ha rivelato errori. Il protocollo GBm ri-trasmette
anche i frame che seguono quelli rivelati con errori. Quindi, il
protocollo SR è quello che utilizza meglio la capacità trasmissiva
del Canale Diretto.
82
Confronto Complessità-Prestazioni
tra i protocolli ARQ (2/2)
Il protocollo SR richiede la Numerazione mod.M dei frame
trasmessi e l’impiego di un Buffer in Trasmissione e di un
Buffer in Ricezione.
Il protocollo GBm richiede la Numerazione mod.M dei
frame trasmessi e l’impiego del solo Buffer di
Trasmissione.
Il protocollo SaW richiede solo la Numerazione mod.2 dei
frame trasmessi e l’impiego di un Buffer di Trasmissione in
grado di memorizzare un solo frame alla volta.
Quindi il protocollo SR è il più complesso da realizzare,
mentre il protocollo SaW è il più semplice da realizzare.
83
Servizio di Controllo di Flusso (1/4)
Supponiamo che il Nodo-Sorgente S
trasmetta
trame al Nodo-Destinazione D . Supponiamo che le
trame ricevute dal Nodo-Destinazione siano
temporaneamente memorizzate in un Buffer di
Ricezione che può contenere al più NF ≥ 1 trame.
scopo del Servizio di Controllo di Flusso è quello di
regolare (ossia, controllare) la velocità con cui il
Nodo-Sorgente invia nuove trame in modo che il
numero di trame da memorizzare nel Buffer di
Ricezione non sia mai superiore a NF.
Lo
84
Controllo di Flusso mediante il
protocollo SR (2/4)
Il protocollo SR precedentemente descritto è
anche in grado di espletare il Servizio di Controllo
di Flusso.
Nel protocollo SR, il Controllo di Flusso viene
effettuato:
i. scegliendo opportunamente le dimensioni WS e
WD delle finestre di trasmissione e di ricezione;
ii. regolando la velocità (ossia, il ritmo) con cui il
Nodo-Destinazione invia indietro al NodoSorgente messaggi di riscontro positivi (riscontri
ACK).
85
Controllo di Flusso mediante il
protocollo SR (3/4)
Ricordiamo che, nel protocollo SR:
i. WS è il numero massimo di trame che il
Nodo-Sorgente può trasmettere
consecutivamente senza bisogno di
ricevere riscontri positivi da parte del
Nodo-Destinazione;
ii. WD è il numero massimo di trame che il
Nodo-Destinazione può ricevere
consecutivamente senza bisogno di inviare
messaggi ACK(.) al Nodo-Sorgente.
86
Controllo di Flusso mediante il
protocollo SR (4/4)
Quindi,
i.
ii.
se si scelgono: WS ≤ NF e WD ≤ NF , e, inoltre,
se il Nodo-Destinazione rallenta la velocità con
cui invia messaggi ACK al Nodo-Sorgente quando
il numero di trame temporaneamente
memorizzate nel Buffer di Ricezione si avvicina a
NF;
allora
il numero di trame da tenere in memoria nel
Buffer di Ricezione non supererà mai il valore
massimo consentito NF.
87
88
Il problema dell’Accesso Multiplo (1/5)
Il problema dell’accesso multiplo si ha quando più NodiSorgente vogliono trasmettere le loro trame ad uno o più
Nodi-Destinazione attraverso un singolo canale
trasmissivo.
Il canale trasmissivo è, quindi, condiviso dalle
trasmissioni di più (almeno due) Nodi-Sorgente e, per
questo motivo, viene detto canale broadcast.
Dal punto di vista fisico, un canale broadcast può essere
di tipo:
i.
Cablato (cavo coassiale, doppino telefonico, fibra
ottica);
ii. Radio (trasmissione nello spazio libero).
89
Il problema dell’Accesso Multiplo
(2/5)
simultaneamente
i segnali da esse generati nel canale condiviso, allora
i segnali interferiscono tra di loro e il segnale
interferito risultante è inutilizzabile da parte dei
Nodi-Destinazione.
In questo caso, si dice che si è verificata una
collisione tra i segnali trasmessi simultaneamente dai
Nodi-Sorgente.
Lo scopo dei Protocolli per l’Accesso Multiplo
(Protocolli MAC) è quello di regolare (disciplinare)
opportunamente le trasmissioni dei Nodi-Sorgente in
modo da evitare (o, quanto meno, minimizzare)
l’occorrenza di collisioni.
Se due o più Nodi-Sorgente inviano
90
Il problema dell’Accesso Multiplo
(3/5)
Più sorgenti (almeno 2) che trasmettono verso le
destinazioni (almeno una) tramite lo stesso mezzo
trasmissivo
D1
S1
D2
S2
D3
S3
Mezzo trasmissivo (cavo, fibra, aria…)
D5
D4
La trasmissione da parte delle sorgenti deve essere
disciplinata attraverso regole di accesso al mezzo per
evitare fenomeni di interferenza tra messaggi generati
da sorgenti diverse (collisioni).
91
Il problema dell’Accesso Multiplo
(4/5)
Collegamento broadcast o multiaccesso (cavo o canale
condiviso: multipunto)
Il termine broadcast indica che quando un nodo
trasmette una trama il canale la diffonde e tutti gli altri
nodi ne ricevono una copia
o Ethernet tradizionale
o Wireless LAN 802.11
Shared wireless
Shared wire
(e.g. Ethernet)
(e.g. WaveLAN)
Satellite
92
Il problema dell’Accesso Multiplo
(5/5)
Centinaia o anche migliaia di nodi possono
comunicare direttamente su un canale
broadcast:
o
Si genera una collisione quando due o più nodi
trasmettono trame contemporaneamente.
Protocolli
di Accesso Multiplo
Protocolli che fissano le modalità con cui i nodi
regolano l’immissione delle Trame da essi
generate nel canale condiviso.
93
Sistema di Accesso Multiplo (1/3)
In generale, un sistema di Accesso Multiplo
è costituito da N≥2 stazioni (nodi), ciascuna
delle quali può sia trasmettere che ricevere
da un canale condiviso di capacità C (bit/
sec).
Ciascuna stazione può sia inviare trame che
ricevere da qualsiasi altra stazione.
Ciascuna stazione è univocamente
individuata da un indirizzo MAC costituito
da 6 byte ed espresso in forma
esadecimale.
94
Sistema di Accesso Multiplo
(2/3)
Canale condiviso (Broadcast channel)
Nodo 1
Nodo 2
Nodo N
dmax (m)
95
Sistema di Accesso Multiplo:
Parametri Principali (3/3)
Con riferimento alla figura precedente,
introduciamo le seguenti definizioni:
o
o
o
o
o
o
o
o
N numero di nodi che compongono il sistema;
C (bit/sec) capacità trasmissiva del Canale condiviso;
dMAX (m) distanza massima tra due nodi del sistema;
v (m/sec) velocità di propagazione del segnale
elettrico nel canale condiviso;
τ dMAX /v (sec) = ritardo massimo di propagazione del
segnale elettrico;
L MIN (bit) lunghezza minima di una trama;
LMAX (bit) lunghezza massima di una trama;
Tt LMAX/C (sec) = tempo necessario a trasmettere una
trama di lunghezza massima.
96
Proprietà di un Protocollo MAC ‘ideale’
Idealmente, un protocollo MAC per un sistema di
Accesso Multiplo con N nodi che impiega un
canale condiviso di capacità C dovrebbe
possedere le seguenti due proprietà:
i.
quando un solo nodo ha dati da trasmettere,
quel nodo può trasmettere ad una velocità
(tasso) pari alla capacità C (bit/sec) del
canale condiviso (Proprietà di utilizzo
efficiente del canale);
ii.
quando N ≥ 2 nodi hanno dati da trasmettere,
ciascuno di questi può trasmettere ad una
velocità media di C/N (bit/sec) (Proprietà di
equità di condivisione del canale).
97
Prestazioni di un Protocollo MACEfficienza (1/3)
Supponiamo assegnato un Protocollo MAC che
regoli (in qualche modo) le trasmissioni di N ≥ 2
nodi attraverso un canale condiviso di capacità C.
In ogni intervallo temporale di durata Tt, il
canale condiviso può trovarsi in uno e in uno solo
dei seguenti tre stati:
i. Stato libero: nessun nodo sta trasmettendo
nel canale;
ii. Stato di collisione: due o più nodi stanno
trasmettendo simultaneamente nel canale;
iii. Stato utile: uno e uno solo nodo sta
trasmettendo nel canale.
98
Prestazioni di un Protocollo MACEfficienza (2/3)
Indichiamo con:
o
o
o
o
TL (sec) tempo che il canale passa nello stato Libero;
TC (sec) tempo che il canale passa nello stato di
Collisione;
TU (sec) tempo che il canale passa nello stato Utile;
Ttot (sec) TL + TC + TU = tempo di lavoro del canale.
Ciò posto, l’efficienza del protocollo MAC
assegnato è così definita:
99
Prestazioni di un Protocollo MACEfficienza (3/3)
Il valore di varia al variare del Protocollo MAC
considerato.
Dal punto di vista analitico,
compreso in [0,1].
Dal punto di vista ingegneristico, i Protocolli MAC
più efficienti (migliori) sono quelli che hanno più
alti valori di , perché consentono agli N nodi di
condividere il canale broadcast dando luogo a
“poche” collisioni.
è un numero reale
100
Classificazione dei Protocolli MAC
(1/2)
Protocolli MAC si possono classificare in
(almeno) due categorie:
i. Protocolli a suddivisione del canale (Channel
Partitioning Protocols): partizionano la
capacità C del canale condiviso in parti “più
piccole”, dette sotto-canali, non interferenti;
ii. Protocolli ad accesso casuale (Random Access
Protocols): il canale condiviso non viene
suddiviso tra i nodi. Trasmissioni simultanee
danno luogo a collisioni. I nodi collidenti ritrasmettono le trame che hanno colliso.
101
Classificazione dei Protocolli MAC
(2/2)
Protocolli MAC
Protocolli a
suddivisione
del canale
TDMA
FDMA
Protocolli ad
accesso casuale
CDMA
Slotted
ALOHA
CSMA/CD
102
Protocolli a suddivisione di canaleGeneralità (1/2)
Consideriamo un sistema di accesso con N ≥ 2
nodi che impiega un canale condiviso di capacità
C (bit/sec).
Per definizione, un Protocollo MAC a
suddivisione di canale opera come segue:
i.
Suddivide il canale in N sotto-canali non
interferenti, ciascuno di capacità C/N (bit/
sec);
ii.
Assegna permanentemente a ciascuno dei nodi
uno dei sotto-canali per l’intero tempo della
comunicazione.
103
Protocolli a suddivisione di canaleGeneralità (2/2)
i.
ii.
iii.
iv.
v.
Dalla precedente definizione, discendono alcune proprietà
generali possedute da tutti i protocolli MAC a suddivisione di
canale, e cioè:
La trasmissione di dati da parte di ciascun nodo avviene sempre
senza collisioni;
Tutti i nodi possono trasmettere alla stessa velocità di C/N (il
protocollo è equo);
Quando c’è un solo nodo che ha dati da trasmettere, esso può
farlo alla velocità di C/N (bit/sec) (il protocollo non utilizza
efficientemente la capacità C del canale condiviso);
Il protocollo offre un modo di trasferimento “a circuito”;
C’è bisogno di un nodo controllore (nodo Master) che disciplini
l’accesso al canale condiviso da parte degli N nodi (il protocollo
è di tipo centralizzato).
104
Protocolli a suddivisione di canaleClassificazione
A seconda della tecnica (strategia) impiegata
per partizionare il canale condiviso in sottocanali non interferenti, i Protocolli a suddivisione
del canale possono essere di tre tipi :
i. Protocollo d’accesso a Divisione di Tempo
(TDMA);
ii. Protocollo d’accesso a Divisione di Frequenza
(FDMA);
iii. Protocollo d’accesso a Divisione di Codice
(CDMA).
105
Accesso Multiplo a divisione di tempo
(TDMA, Time Division Multiple Access)
Le sorgenti trasmettono sulla stessa banda di frequenza ma in
intervalli di tempo diversi, alternati e separati da intervalli di
guardia Tg
1
2
3
4
1
2
3
4
…
Tempo (sec)
Trama
Tg
timeslot
Definizione di una trama : ciascuna destinazione estrae il proprio
segnale generato dalla sorgente desiderata sulla base del
sincronismo della trama
Esempi:
i. Assegnazione timeslot per collegamenti GSM
ii. trasmissioni dati su fibra ottica, con allocazione fissa o
dinamica degli intervalli (“timeslot”)
106
Accesso Multiplo a divisione di
frequenza
(FDMA, Frequency Division Multiple Access)
Le varie sorgenti trasmettono contemporaneamente nel tempo
ma impiegano bande di frequenza diverse, separate da bande di
guardia Bg
T1
T2
T3
f1
f2
f3
B1
B2
Bg
B3
Frequenza
(Hz)
Ciascuna destinazione estrae il proprio segnale della sorgente
desiderata tramite un filtraggio in banda
Esempi:
i. broadcasting radio e tv, con allocazione fissa della banda
(multiplazione in frequenza)
ii. trasmissioni in HF, con allocazione dinamica della banda
107
Accesso Multiplo a divisione di codice
(1/5)
Dato A= 1
Utente A
t
Codice A:
1-1-11-111-1
t
integratore
1
A
A
Dato B= 1
Utente B
t
t
Codice B:
-1-111-11-11
Trasmettitori
(“Spreaders”)
t
Codice A:
1-1-11-111-1
-1
Decisore
Canale Ricevitore per l’utente A
(“Despreader”)
108
Accesso Multiplo a divisione di
codice- Parametri di sistema (2/5)
Ciascun utente (“A” o “B”) genera forme d’onda binarie che
assumono i valori ± 1. Ciascuna forma d’onda elementare è di durata
TB, detto “periodo di bit”
Ciascun utente moltiplica ciascun suo singolo dato da trasmettere
per un segnale di codice (cA(t) o cB(t)) di durata complessiva Tb e
costituito da SF>1 forme d’onda binarie elementari, ciascuna delle
quali è di durata TC (periodo di chip).
Il rapporto SF
>1 è detto spreading factor (fattore di
allargamento) del sistema e rappresenta il numero di chips contenuti in un
periodo di bit TB.
Il segnale CDMA sA(t) trasmesso dall’utente A durante un periodo di
bit è quindi pari a:
sA(t)=AcA(t),
0 ≤ t ≤ Tb,
dove A= ±1 è il bit di messaggio trasmesso
dall’utente A.
Baccarelli,
Cordeschi, Patriarca, Polli
109
Accesso Multiplo a divisione di codiceForme d’onda dei segnali (3/5)
+1
A(t)
-1
(segnale digitale dell’utente A)
2Tb
Tb
CA(t)
t
(segnale di codice A)
+1
Tb
-1
2Tb
t
2Tb
t
TC
SA(t) A(t)CA(t)
(segnale CDMA di A)
+1
Tb
-1
SF
=8
110
Accesso Multiplo a divisione di codice
(4/5)
La Banda occupata dal segnale CDMA generato da ciascuno
degli utenti (“A” o “B”) è SF volte la banda fm del
corrispondente segnale binario prima della moltiplicazione per
il segnale di codice, ossia abbiamo che
BCDMA ≡ SF x fm
(allargamento di banda del segnale A)
Quindi, il CDMA è un formato di segnale a Banda LARGA.
111
Accesso Multiplo a divisione di codice
(5/5)
rumore di canale e sotto l’assunzione (fondamentale) che i
due segnali di codice soddisfino alla seguente condizione di ortogonalità:
In assenza di
(condizione di ortogonalità tra i segnali di codice),
all’uscita dell’integratore di ricezione è sempre ricostruibile senza errore
il valore rA del bit di messaggio A realmente trasmesso dall’utente A.
Infatti dalla figura precedente abbiamo che:
1
0
112
Protocolli MAC Ad Accesso CasualeGeneralità (1/3)
Consideriamo N ≥ 2 nodi che condividono un canale di
capacità C (bit/sec).
Per definizione, i protocolli ad accesso casuale
operano in accordo alla eseguenti regole generali:
i.
Un nodo che vuole trasmettere, lo fa sempre alla
velocità di C (bit/sec);
ii.
Quando si verifica una collisione, ciascun nodo
coinvolto nella collisione ritrasmettere il suo
frame ripetutamente, sin tanto che il frame è
trasmesso senza collisione;
113
Protocolli MAC Ad Accesso CasualeGeneralità (2/3)
i.
ii.
Quando un nodo subisce una collisione, non
cerca di ritrasmettere il suo frame
immediatamente. Al contrario, il nodo
attende un certo intervallo di tempo prima
di ritrasmettere il suo frame;
Ciascun nodo coinvolto in una collisione
sceglie un tempo di attesa per la
ritrasmissione del suo frame
indipendentemente da tutti gli altri nodi.
114
Protocolli MAC Ad Accesso CasualeGeneralità (3/3)
Dalla definizione precedente, scaturiscono le seguenti proprietà
generali dei Protocolli ad Accesso Casuale:
i.
Quando c’è un solo nodo che vuole trasmettere, può farlo
alla velocità C(bit/sec) (Proprietà di utilizzo efficiente del
canale);
ii.
Quando N ≥ 2 nodi hanno dati da trasmettere, il protocollo
non garantisce che possano farlo ad una velocità media di
C/N (bit/sec) (il protocollo non è “equo”);
iii.
Trasmissioni simultanee da parte di più nodi danno sempre
origine a collisioni;
iv.
Il protocollo offre un modo di trasferimento “a
pacchetto” con perdita;
v.
Non c’è alcun nodo controllore (nodo Master) che disciplina
le trasmissioni da parte dei nodi (il protocollo è di tipo
Distribuito).
115
Protocolli MAC ad Accesso CasualeClassificazione (1/2)
In funzione delle diverse tecniche (strategie) che
possono essere adottate per prevenire oppure per
risolvere le collisioni, i protocolli MAC ad accesso
casuale si suddividono in (almeno) due categorie:
i. Protocolli di tipo ALOHA
Non effettuano alcune rilevazione dello stato (libero
oppure occupato) del canale condiviso al momento di
iniziare la trasmissione di ua trama da parte di un
nodo.
ii. Protocolli di tipo ‘Carrier Sensing Multiple
Access with Collision Detection’ (CSMA/CD)
116
Protocolli MAC ad Accesso CasualeClassificazione (2/2)
Effettuano una rilevazione (“sensing”) dello stato
(libero o occupato) del canale prima di iniziare la
trasmissione di una trama, cercando così di prevenire
gli eventi di collisione. Inoltre, dopo che un nodo ha
iniziato a trasmettere una trama, esso continua a
rilevare lo stato del canale per accorgersi se la
collisione si stia comunque verificando, così da essere
in grado di sospendere subito la trasmissione non
appena la collisione avviene (Collision Detection).
117
Protocollo d’accesso Slotted ALOHAGeneralità (1/5)
Nei sistemi d’accesso Slotted ALOHA, si assume che:
i.
Il tempo è suddiviso in sotto-intervalli (timeslot) di durata ciascuno LMAX/C (sec);
ii.
I nodi possono iniziare le trasmissioni solo agli
inizi degli slot;
iii. Ciascun nodo conosce esattamente gli istanti
d’inizio dei vari slot;
iv. Se due o più nodi trasmettono simultaneamente
in uno stesso slot, i corrispondenti frame
collidono (cioè, vanno persi) e i nodi che hanno
colliso si accorgono (rilevano) tale collisione.
118
Protocollo d’accesso Slotted ALOHAFunzionamento (2/5)
Indichiamo con p un valore di probabilità, cioè un numero compreso tra
[0,1]. p è la ”probabilità di persistenza ” del protocollo.
Allora un qualunque nodo che abbia una trama da trasmette opera in
accordo al seguente protocollo “Slotted Aloha”:
a)
Quando un nodo ha una nuova trama da trasmettere, aspetta
l’inizio del successivo slot e poi trasmettere l’intera trama
durante lo slot;
b)
Se non c’è stata collisione, il nodo ha trasmesso con successo la
sua trama e torna al passo a);
c)
Se il nodo ha rilevato la collisione, allora esso ritrasmette la
stessa trama con probabilità p in ciascuno dei seguenti slot, sin
tanto che la trama non è stata trasmessa senza collisione.
I passi a), b), c) definiscono il modo di operare del protocollo “Slotted
ALOHA”.
119
Protocollo d’accesso Slotted ALOHACalcolo dell’Efficienza (3/5)
Ricordiamo che, per definizione:
Ovvero, l’efficienza di un protocollo è la frazione del tempo
totale in cui il canale trasmette trame senza collisioni.
Nel caso dello Slotted ALOHA, supponiamo di avere N nodi,
ciascuno dei quali trasmette la propria trama in uno slot con
probabilità p.
Allora, la probabilità Ps che un singolo nodo trasmette la sua
trama senza collisioni è: Ps = p (1-p)N-1.
Poiché vi sono N nodi, la probabilità totale Pst che un qualsiasi
nodo trasmetta la sua trama con successo è pari a:
Pst= NPs= Np (1-p)N-1.
Per definizione, Pst coincide con l’efficienza dello Slotted
ALOHA cioè
≡ Pst = Np (1-p)N-1
120
Protocollo d’accesso Slotted ALOHACalcolo dell’Efficienza (4/5)
Definiamo come efficienza massima
ALOHA il seguente limite:
Per N finito, il valore p* della probabilità di
persistenza che massimizza è: p* = 1/N, così che
abbiamo:
dello Slotted
121
Protocollo d’accesso Slotted ALOHACalcolo dell’Efficienza (5/5)
Ricordiamo il seguente limite notevole:
Allora passando al limite per N ∞ l’espressione precedentemente
trovata per:
, otteniamo che l’efficienza massima
alla quale può dar luogo il protocollo Slotted ALOHA è pari a :
al più, solo (circa)
il 37% degli slot trasporta trame che non collidono. In altri
termini, nello slotted ALOHA, almeno il 63% degli slot o rimane
inutilizzato o trasporta trame che collidono.
Ciò significa che, nel caso dello slotted ALOHA,
122
Accesso Multiplo con Rivelazione
della portante (CSMA) (1/4)
Una prima strategia che si può usare per migliorare l’efficienza
dello Slotted ALOHA è quella di rilevare lo stato del canale
(libero o occupato) prima di iniziare a trasmettere.
Specificatamente, i protocolli di tipo Carrier Sensing Multiple
Access (CSMA) prevedono che ogni nodo che ha una trama da
trasmettere effettui le seguenti operazioni:
i.
Si pone in ascolto del canale (sensing) per verificarne lo
stato;
ii.
Se il canale è libero, il nodo trasmette l’intera trama;
iii.
Se il canale è occupato, il nodo aspetta un opportuno
intervallo di tempo e, poi, torna ad ascoltare il canale.
Quindi, i protocolli CSMA adottano la seguente regola: “Ascolta
prima di parlare e, se qualcun altro sta già parlando, aspetta
finchè non ha concluso”.
123
Accesso Multiplo con Rivelazione della
portante (CSMA) (2/4)
La strategia di accesso CSMA non garantisce l’assenza di collisioni.
Supponiamo che il nodo B e il nodo D siano alla massima distanza dmax.
o
Supponiamo che, all’istante t0, il nodo B ascolti il canale, lo trovi libero
ed inizi a trasmettere;
o
Supponiamo che all’istante t1 (dove t1≥t0), il nodo D ascolti il canale.
o
Se la differenza (t1-t0) è minore del ritardo di propagazione τ del
segnale elettrico nel canale condiviso, ossia, se è verificata la
condizione:
(t1-t0) < τ
allora all’istante t1, il nodo D “sente” il canale libero ed inizia a
trasmettere la propria trama.
o
Poiché il nodo B sta già trasmettendo la propria trama le trame
generate dai nodi D e B collidono.
Ne concludiamo che, in generale, la strategia di accesso CSMA è tanto meno
efficace quanto maggiore è il ritardo di propagazione τ del sistema d’accesso
considerato.
124
Accesso Multiplo con Rivelazione
della portante (CSMA) (3/4)
Le collisioni possono ancora verificarsi:
o
tra i due nodi trasmittenti avviene una collisione se
essi accedono al canale in istanti che differiscono tra
loro meno del tempo di propagazione tra i nodi;
o
Il ritardo di propagazione fa sì che due nodi non
rilevino la reciproca trasmissione.
collisione
B
D
125
Accesso Multiplo con Rivelazione
della portante (CSMA) (4/4)
Il ritardo di
propagazione τ
gioca un ruolo
importante nel
determinare le
collisioni
126
CSMA con Rilevazione di Collisione
(CSMA/CD) (1/3)
Le prestazioni dei protocolli CSMA possono essere
migliorate facendo ricorso alla funzione di Rilevazione delle
Collisioni (Collision Detection- CD)
Per definizione, la funzione di Collision Detection richiede
che un qualsiasi nodo che ha già iniziato a trasmettere
continui ad ascoltare il canale, ed interrompa
immediatamente la trasmissione nel caso in cui si accorga
che c’è anche un altro nodo che sta trasmettendo.
Quindi, la funzione di Collision Detection permette di
minimizzare la durata temporale di ciascuna collisione.
E’ da rimarcare che un nodo può espletare la funzione di
Collision Detection solo durante l’intervallo temporale in cui
sta trasmettendo la propria trama, ma non dopo aver
terminato di trasmetterla.
Baccarelli,
127
Cordeschi, Patriarca, Polli
CSMA con Rilevazione di Collisione
(CSMA/CD) (2/3)
Ricapitolando, i protocolli CSMA/CD prevedono che ogni
nodo che abbia una trama da trasmettere:
i. Ascolti lo stato del canale e inizi a trasmettere solo se
il canale è libero (fase CSMA);
ii. Continui ad ascoltare il canale durante la trasmissione
della propria trama e interrompa immediatamente la
trasmissione appena si accorga che un altro nodo sta
trasmettendo (fase CD).
In essenza, i protocolli CSMA/CD adottano la regola:
“Ascolta prima di parlare e anche mentre stai parlando”.
128
CSMA con Rilevazione di collisione
(CSMA/CD) (3/3)
Rispetto al
protocollo CSMA,
migliora le
prestazioni
riducendo la
durata temporale
delle collisioni
129
Il protocollo CSMA/CD (1/2)
Nei sistemi d’accessi di tipo CSMA/CD, ciascun nodo opera
in accordo al seguente protocollo:
Nodo pronto a
trasmettere
Canale
occupato?
Attesa di Δ
si
no
Trasmissione e
sensing del canale
Collisione
Rilevata?
no
Scelta casuale del
tempo di attesa Δ
nell’insieme
{0, T0, 2T0, …, (2k-1)T0}
Calcolo di (2k-1)T0
si
Trasmetti il
segnale di jam
Trasmissione
completata
Attendi Δ1=9.6µs
130
Il protocollo CSMA/CD –
Definizione dei parametri (2/2)
I parametri introdotti nel diagramma precedente hanno i
seguenti significati/valori:
o
T0 (sec) ≡ tempo necessario a trasmettere una trama
di lunghezza minima ≡ Lmin/C
tipicamente T0=51.2µs;
o
Δ1 ≡ tempo che deve intercorrere tra l’istante in cui
termina la trasmissione di una trama e l’istante in cui il
nodo torna a sentire il canale per trasmettere la trama
successiva (Inter-Frame Gap)
tipicamente Δ1 = 9.6 µs;
o
K ≡ min {Nc,10};
o
Nc ≡ numero di collisioni già subite dalla trama che il
nodo sta cercando di trasmettere.
131
Il protocollo CSMA/CD- Descrizione (1/3)
Quando il nodo ha una trama da trasmettere, inizia ad
ascoltare (sensing) il canale. Nel caso in cui rilevi una
trasmissione già in atto, il nodo si pone in uno stato di
attesa per un opportuno intervallo di tempo Δ (sec) e,
quindi, torna di nuovo ad ascoltare il canale.
Nel caso in cui l’operazione di Collision Detection rilevi
una collisione mentre il nodo sta già trasmettendo, il
nodo interrompe immediatamente la trasmissione della
trama e, poi, emette un segnale di allarme (segnale di
jam).
Il segnale di jam è una particolare sequenza di 32 bit
che ha il compito di avvertire tutti i nodi del sistema
delle collisioni e, che, quindi, tutti i bit che essi hanno
ricevuto sono da scartare.
132
Il protocollo CSMA/CD- Descrizione
(2/3)
Dopo la trasmissione del segnale di jam, il nodo si pone in attesa di
riprovare la trasmissione della trama che ha colliso.
La durata Δ (sec) (variabile) dello stato di attesa è calcolata
applicando il cosiddetto algoritmo di subentro (Algoritmo di Backoff), che è basato sulla definizione di un intervallo di base
T0 ≡ 51.2µs che rappresenta il tempo necessario a trasmettere una
trama di lunghezza minima.
Specificatamente, l’Algoritmo di Back-off prevede che il nodo
torni ad ascoltare il canale dopo un tempo di attesa Δ che è scelto
casualmente nell’insieme:
Δ {0, T0, 2T0, …, (2k-1)T0},
dove
K ≡ min {Nc,10}
e l’intero Nc ≥ 1 è il numero di collisioni che la trama da
Baccarelli,
trasmettere ha già subito.
Cordeschi, Patriarca, Polli
133
Il protocollo CSMA/CD- Descrizione
(3/3)
Nell’Algoritmo di Back-off, il numero di possibili valori
assumibili dal tempo di attesa Δ cresce in modo
esponenziale con K, ossia cresce in modo esponenziale
con il numero Nc di collisioni già subite dalla trama da
trasmettere, almeno finchè Nc ≥ 10.
Infatti, maggiore è Nc, maggiore è il numero di nodi che
stanno cercando di trasmettere. Quindi, per evitare
che due o più nodi continuino a collidere più e più volte,
l’insieme dei possibili valori che può assumere Δ deve
crescere al crescere di Nc.
134
Corretto funzionamento della procedura
di Collision Detection (1/2)
Poiché un nodo espleta la funzione di Collision Detection solo
durante l’intervallo di tempo in cui sta trasmettendo una
trama, è necessario che il tempo
LMIN/C (sec)
che un nodo impiega per trasmettere una trama di lunghezza
minima sia non inferiore al ritardo massimo ΔMAX (sec) con
cui un nodo che ha iniziato a trasmettere di accorge che un
altro nodo sta già trasmettendo.
Ovviamente, ΔMAX è pari al tempo impiegato dal segnale
elettrico per propagarsi dal nodo A al nodo B e, poi, dal nodo
B al nodo A, dove A e B sono due nodi posti alla massima
distanza dMAX . Ovvero,
ΔMAX = 2 τ = 2 dMAX /v
135
Corretto funzionamento della procedura
di Collision Detection (2/2)
Quindi, affinchè la funzione di CD operi correttamente,
dobbiamo avere
LMIN/C ≥ ΔMAX ≡ 2 dMAX /v,
ovvero,
dMAX ≤ v (m/sec) x LMIN (bit) /2 C (bit/sec)
(1)
Ciò significa che i sistemi d’accesso di tipo CSMA/CD
hanno una estensione massima dMAX (ovvero, una
copertura) che è limitata dal secondo membro della
disuguaglianza riportata nella eq. (1).
136
Efficienza massima del protocollo
CSMA/CD (1/3)
L’impiego del protocollo CSMA/CD non garantisce
l’assenza di collisioni.
Anche nel caso dei sistemi di accesso CSMA/CD, il
canale condiviso dagli N nodi può trovarsi in uno dei tre
stati:
i. Stato libero,
ii. Stato con collisione,
iii. Stato utile.
precedentemente definiti.
137
Efficienza massima del protocollo
CSMA/CD (2/3)
Si può dimostrare che, al tendere all’inifinito del numero di
nodi N che compongono il sistema, l’efficienza massima di un
sistema CSMA/CD è pari a:
dove
o
o
o
a ≡ τ /Tt (sec) ≡ tempo di propagazione normalizzato al
tempo di trasmissione;
τ ≡ dMAX /v (sec) = tempo di propagazione del segnale
elettrico nel sistema;
Tt ≡ LMAX /C (sec) = tempo di trasmissione di una trama
di dimensione massima.
138
Efficienza massima del protocollo
CSMA/CD (3/3)
E’ interessante osservare che:
Quindi, il protocollo CSMA/CD è tanto più efficiente
(cioè, tanto più capace di evitare collisioni) quanto più è
piccolo il valore a del rapporto tra il ritardo di
propagazione τ il tempo di trasmissione Tt di una trama
di dimensione massima.
139
Reti in Area Locale (LAN) e
Reti Ethernet
140
Reti in Area Locale - Definizione (1/2)
Le reti in Area Locale (Local Area Networks) nascono per
interconnettere utenti terminali distribuiti su un’area geografica
limitata e dell’ordine di 2.5km-3.0km.
Dal punto di vista componentistico, una LAN è costituita da:
o
Più utenti terminali;
o
Elementi di inter-connessione tra utenti terminali (hub e/o
bridge);
o
Canali trasmissivi che collegano le coppie di nodi.
Le caratteristiche fondamentali di una LAN sono:
i.
Estensione geografica limitata, ossia dMAX ≤ 2.5km-3.0km;
ii.
Elementi di inter-connessione che attuano solo protocolli
degli Strati Fisico e di Collegamento;
iii.
Canali trasmissivi che possono essere di tipo punto-punto,
oppure condivisi (canali broadcast).
141
Reti in Area Locale - Definizione (2/2)
Le LAN si suddividono in due grandi categorie:
i.
LAN cablate (wired LAN):
usano come mezzi trasmissivi i cavi coassiali, e/o i
doppini telefonici e/o le fibre ottiche;
i.
LAN radio (wireless LAN):
usano come mezzo trasmissivo lo spetto radio.
142
La Famiglia delle LAN Ethernet
143
Ethernet - Generalità (1/2)
La tecnologia Ethernet è nata a metà anni ’70; ad oggi,
detiene una posizione dominante nel mercato delle LAN
cablate.
Gli adattatori Ethernet sono poco costosi (dell’ordine dei
20 Euro) e permettono agli utenti collegati di trasmettere a
velocità che vanno dai 10Mb/sec sino ai 10 Gb/sec.
La tecnologia Ethernet comprende tutta una famiglia di
reti che si differenziano principalmente per:
i.
Velocità di trasmissione (dai 10Mb/sec ai 10 Gb/sec);
ii.
Coperture (da qualche decina di metri ai 3.5/4.0km);
iii.
Mezzi trasmissivi impiegati (cavo coassiale, doppino
telefonico, fibra ottica);
iv.
Strategia usata per l’accesso (CSMA/CD oppure
accesso dedicato).
144
Ethernet - Generalità (2/2)
Dal punto di vista dell’Architettura Protocollare, gli standard Ethernet
definiscono solo i protocolli degli:
i.
Strato fisico
ii.
Strato di Collegamento.
Modello di Servizio
Tutte le tecnologie Ethernet forniscono un servizio privo di connessione
e non affidabile al corrispondente Strato di Rete. Specificatamente:
i.
Servizio privo di connessione significa che quando un adattatore A
vuole inviare una trama ad un adattatore B lo fa direttamente
senza ricorrere alla fase di Instaurazione della connessione (fase
di handshaking);
ii.
Servizio non affidabile significa che quando un adattatore B riceve
una trama da A, esso applica la procedura di rivelazione degli
errori, ma non invia indietro ad A né alcun riscontro positivo né
negativo. Quando l’adattatore B rivela errori nella trama ricevuta,
esso scarta semplicemente la trama, senza richiederne la ritrasmissione.
145
Strato Fisico della Tecnologia
Ethernet
146
Topologia delle Reti Ethernet (1/2)
Le reti Ethernet attuali impiegano una topologia a stella, in cui
gli N ≥2 nodi che compongono la rete sono collegati (in modo
bidirezionale) ad un nodo di interconnessione detto Centro
Stella.
Ciascun nodo è connesso al Centro Stella mediante due canali, il
primo dei quali è impiegato per inviare segnali verso il Centro
Stella, mentre il secondo è utilizzato per ricevere segnali dal
Centro Stella.
Le trame generate da un Nodo-Sorgente A debbono
necessariamente transitare per il Centro Stella prima di
raggiungere il Nodo-Destinazione desiderato B.
Il Centro Stella può essere un hub oppure un bridge.
Il modo di trasmissione di una rete Ethernet è sempre
bidirezionale e può essere half-duplex o full-duplex.
147
Topologia delle Reti Ethernet (2/2)
Nodo
1
Centro Stella
(hub o bridge)
Nodo
2
Nodo
3
Nodo
N
148
Mezzi trasmissivi nelle Reti Ethernet
(1/2)
Per la maggior parte, le reti Ethernet attuali impiegano come
mezzo trasmissivo il doppino telefonico oppure la fibra ottica.
I doppini telefonici impiegati sono di tipo non schermato (UTPUnshielded Twisted Pair) e, a seconda della qualità del rame
impiegato, si suddividono in 7 categorie, di qualità via via
crescente.
Specificatamente, i doppini UTP impiegati nelle reti Ethernet
sono quelli di:
i.
Categoria 3 – hanno una larghezza di banda di 16MHz;
ii.
Categoria 4 – hanno una larghezza di banda di 20MHz;
iii. Categoria 5 – hanno una larghezza di banda di 100MHz;
iv. Categoria 6 – hanno una larghezza di banda di 250MHz;
v.
Categoria 7 – hanno una larghezza di banda di 1000MHz.
149
Mezzi trasmissivi nelle Reti Ethernet
(2/2)
Le fibre ottiche impiegate nelle reti Ethernet
possono essere di tipo monomodo o multimodo.
La fibre multimodo operano in 1° finestra e in 2°
finestra, ossia a lunghezze d’onda dell’ordine dei
850nm e dei 1300nm. Esse sono dispersive e
introducono attenuazioni non trascurabili.
Le fibre monomodo operano in 2° finestra e in 3°
finestra, ossia a lunghezze d’onda dell’ordine di
1300nm e 1500nm. Esse sono poco dispersive e
introducono basse attenuazioni.
150
Modulazione nelle Reti Ethernet (1/3)
Il formato di modulazione impiegato è il Manchester, che è
un formato di modulazione binario e di banda base.
Indicato con Tb (sec) il periodo di bit, nel formato
Manchester:
i.
Il bit ‘0’ è rappresentato da un segnale che presenta
una transizione: altobasso a Tb/2;
ii.
Il bit ‘1’ è rappresentato da un segnale che presenta
una transizione: bassoalto a Tb/2.
Poiché nelle reti Ethernet non c’è un segnale di sincronismo
che coordina (allinea temporalmente) i nodi della rete, le
suddette transizioni facilitano l’estrazione del segnale di
sincronismo dalla sequenza di bit ricevuti da ciascun nodo.
151
Modulazione nelle Reti Ethernet (2/3)
Le reti Ethernet che impiegano il doppino
telefonico come mezzo trasmissivo usano la
modulazione Manchester di tipo bipolare.
S1(t)
S0(t)
+1
+1
Tb/2
-1
Tb
Tb/2
t
Tb
t
-1
152
Modulazione nelle Reti Ethernet (3/3)
fibra ottica
come mezzo trasmissivo usano la modulazione
Manchester di tipo on-off.
Le reti Ethernet che impiegano la
S1(t)
S0(t)
+1
+1
Tb/2
Tb
t
Tb/2
Tb
t
153
Strato di Collegamento della
Tecnologia Ethernet
154
Formato della Trama Ethernet (1/3)
Le trama Ethernet ha una lunghezza minima di
73 byte e una lunghezza massima di 1527 byte.
Il tempo T0 per la trasmissione di una trama di
lunghezza minima è fissata a T0 = 51.2µs.
La struttura di trama è la seguente (standard
IEEE802.3):
64-1518 byte
preamble
S
F
D
DA
8
1
6
SA
L
E
N
data
P
A
D
CRC
6
2
0-1500
0-46
4
155
Formato della Trama Ethernet (2/3)
Il significato dei campi della Trama è il seguente:
o
preamble (8 byte) - consente, trama per trama, la
sincronizzazione del segnale numerico ricevuto dal
Nodo-Destinazione;
o
Short Frame Delimiter (SFD) (1 byte) - contiene
la stringa ‘10101011’ che individua l’inizio della
trama;
o
Destination Address (DA) (6 byte) - contiene
l’indirizzo MAC del Nodo-Destinazione della
trama;
o
Source Address (SA) (6 byte) - contiene
l’indirizzo MAC del Nodo-Sorgente della trama;
156
Formato della Trama Ethernet (3/3)
o
o
o
o
Length (LEN) (2 byte) - specifica la lunghezza del
campo DATA;
Data (0-1500 byte) - contiene il datagramma generato
dallo strato di rete del Nodo-Sorgente;
PAD (0-46 byte) - serve a garantire che ogni trama
abbia una lunghezza minima non inferiore a 73 byte;
Cyclic Redundancy Check (CRC) (4 byte) - contiene i
bit di controllo di parità del codice impiegato per
rilevare in ricezione eventuali errori presenti nella
trama ricevuta.
157
Reti EthernetInterconnessione tramite Hub
158
Interconnessione tramite Hub (1/4)
Nelle reti Ethernet che impiegano un hub come centrostella, ogni nodo è connesso all’hub mediante due canali, uno
dei quali è impiegato per trasmettere verso l’hub, mentre
l’altro è usato per ricevere dall’hub.
L’hub è un dispositivo che opera semplicemente la ritrasmissione del segnale ricevuto da uno dei nodi di rete
verso tutti gli altri nodi della rete, tranne il nodo da cui il
segnale è stato ricevuto.
Quindi, se 2 o più nodi trasmettono contemporaneamente
verso l’hub, i corrispondenti segnali collidono e sono
inutilizzabili.
Dal punto di vista logico, una rete Ethernet con centro-stella
costituito da un hub di comporta come un sistema ad accesso
multiplo con protocollo CSMA/CD.
159
Interconnessione tramite Hub (2/4)
Dal punto di vista fisico (hardware), un hub è un dispositivo con N
interfacce, ciascuna delle quali è collegata bidirezionalmente con
uno dei nodi di rete.
Ciascuna interfaccia è costituita da:
i.
Una porta d’ingresso, dalla quale l’hub riceve il segnale
trasmesso dal nodo;
ii.
Una porta di uscita, attraverso la quale l’hub invia il segnale
verso il nodo.
Il segnale che l’hub riceve dall’m-sima porta d’ingresso viene:
i.
Demodulato;
ii.
Ri-modulato;
iii.
Amplificato;
iv.
Ritrasmesso su tutte le porte d’uscita tranne che sulla
porta di uscita m-sima.
160
Interconnessione tramite Hub (3/4)
La struttura interna di un hub è riportata in figura, per il caso N = 3.
Dal nodo 1
Al nodo 1
Porta di
Ingresso 1
DemodMod.
Ampl.
Dal nodo 2
Porta di
Uscita
1
Al nodo 2
Porta di
Ingresso 2
DemodMod.
Ampl.
Dal nodo 3
Porta di
Uscita
2
Al nodo 3
Porta di
Ingresso 3
DemodMod.
Ampl.
Porta di
Uscita
3
161
Interconnessione tramite Hub (4/4)
Dal punto di vista dell’Architettura Protocollare, un hub
attua solo protocolli di Strato Fisico. Quindi un hub non
può essere impiegato per interconnettere nodi che
adottano protocolli di Strato di Collegamento diversi
tra loro.
Strato Fisico
Simbolo grafico
di un Hub
Pila protocollare
attuata da un Hub
162
Reti EthernetInterconnessione tramite Bridge
163
Bridge - Generalità
Il centro-stella di una rete Ethernet può essere costituito da un
Bridge.
Un Bridge è un dispositivo con N interfacce che attua sia
protocolli di strato fisico che protocolli di strato di collegamento.
In particolare, un Bridge opera su ogni tarma ricevuta al seguente
modo:
i.
Legge l’indirizzo di destinazione della trama;
ii.
Inoltra la trama solo sulla porta di uscita connessa alla
destinazione;
iii.
Trasmette la trama verso la destinazione solo quando non ci
sono altre trame che sono correntemente trasmesse verso la
stessa destinazione.
Quindi l’interconnessione tramite Bridge evita completamente le
collisioni.
164
Bridge – Struttura (1/2)
La struttura di un Bridge è riportata in figura.
Dispositivo di indirizzamento e inoltro
B
u
f
f
e
r
1
Porta 1 . . . Porta N
Porte
d’ingresso
B
u
f
f
e
r
N
Porta 1
Porta N
Porte
d’uscita
165
Bridge – Struttura (2/2)
Un Bridge è costituito da N interfacce, ciascuna della quali è
composta da una porta di ingresso e da una porta d’uscita. Il
Bridge riceve le trame generate dal nodo m-simo mediante la mporta di ingresso. Il Bridge invia le trame destinate al nodo m-simo
mediante la m-sima porta di uscita.
La trama ricevuta da una (generica) porta di ingresso viene
prelevata dal Dispositivo di Indirizzamento, che svolge le seguenti
funzioni:
i.
Legge l’indirizzo del nodo di destinazione contenuto nella
trama;
ii.
Inoltra la trama solo verso il buffer connesso con la porta di
uscita collegata col nodo di destinazione;
iii. Preleva la trama dal buffer e la trasmette verso il nodo di
destinazione solo quando non ci sono altre trame che
correntemente sono trasmesse verso lo stesso nodo di
destinazione (assenza di collisioni).
166
Bridge – Architettura Protocollare
Dal punto di vista dell’Architettura Protocollare, un Bridge attua
sia i protocolli di Strato Fisico che i protocolli di Strato di
Collegamento.
In particolare, un Bridge è in grado di leggere e interpretare gli
indirizzi MAC di una trama, ma non è in grado né di leggere né di
interpretare gli indirizzi IP di un Datagramma.
Un Bridge può essere anche utilizzato per inter-connettere nodi
che adottano differenti protocolli di Strato di Collegamento.
Strato di
collegamento
Strato Fisico
Simbolo grafico
di un Bridge
Pila protocollare
attuata da un Bridge
167
Le funzione svolte da un Bridge
Più in dettaglio, un Bridge svolge le seguenti
funzioni (operazioni) su ciascuna trama che
riceve da una delle sue porte di ingresso:
i. Filtraggio;
ii. Inoltro;
iii. Auto-apprendimento;
iv. Conversione del formato di trama
(opzionale).
168
Filtraggio e Inoltro (1/5)
Filtraggio si riferisce alla capacità che un Bridge ha di
decidere se una trama ricevuta da una delle sue porte di
ingresso debba essere inoltrata ad una opportuna sua
porta di uscita oppure debba essere scartata.
Inoltro (forwarding) è la capacità che un Bridge ha di
determinare (calcolare) a quale porta di uscita debba
essere inviata ciascuna trama che il bridge ha ricevuto
da una delle sue porte di ingresso.
Il bridge svolge le funzioni di filtraggio e inoltro
avvalendosi delle informazioni memorizzate in una
tabella residente nel bridge stesso, e detta Tabella di
Inoltro.
169
Filtraggio e Inoltro (2/5)
Specificatamente, la Tabella di Inoltro memorizzata in
ciascun Bridge ha tante righe quanti sono i nodi
destinazione raggiungibili dalle porte di uscita del
Bridge stesso.
Ciascuna riga della Tabella di Inoltro contiene 3
informazioni:
i.
Indirizzo MAC (6 byte) di un nodo di destinazione;
ii.
Il numero d’ordine della porta di uscita del bridge
dalla quale è raggiungibile il nodo di destinazione;
iii. Il tempo (l’ora) in cui l’indirizzo del nodo di
destinazione è stato inserito (scritto) nella Tabella
di Inoltro.
170
Filtraggio e Inoltro (3/5)
Un possibile esempio di Tabella di Inoltro
memorizzata da un bridge è la seguente
Indirizzo MAC del
nodo di destinazione
Numero della porta
di uscita del Bridge
Tempo di
inserimento
dell’indirizzo MAC
62-FE-F7-11-89-A3
1
9:32
7C-BA-B2-B4-91-10
3
10:37
88-B2-2F-54-1A-0F
1
10:52
…
…
…
171
Filtraggio e Inoltro- Algoritmo
(4/5)
Supponiamo che il bridge riceva una trama dalla porta di ingresso con
numero m e che la trama contenga come indirizzo di destinazione DD-DDDD-DD-DD-DD.
L’algoritmo di Filtraggio e Inoltro eseguito dal bridge procede come segue:
i.
Se l’indirizzo DD-DD-DD-DD-DD-DD non è contenuto nella Tabella
di Inoltro, allora il bridge inoltra la trama ricevuta su tutte le sue
porte d’uscita tranne l’m-sima;
ii.
Se l’indirizzo DD-DD-DD-DD-DD-DD è contenuto nella Tabella e la
porta di uscita ad esso associata è l’m-sima, allora il bridge scarta
la trama ricevuta (ossia, non inoltra la trama su nessuna delle porte
d’uscita) (Filtraggio);
iii.
Se l’indirizzo DD-DD-DD-DD-DD-DD è contenuto nella tabella e la
porta di uscita ad esso associata è l’x-sima con x ≠ m, allora il
bridge memorizza temporaneamente la trama nel buffer che
precede la porta d’uscita x-sima. Il bridge rimuove la trama dal
buffer e la trasmette sulla porta d’uscita x-sima solo quando la
suddetta trasmissione non provoca collisione con altre trasmissioni
172
già in corso (Inoltro). Baccarelli,
Cordeschi, Patriarca, Polli
Filtraggio e Inoltro- Esempio (5/5)
Source: A
Dest: A’
Destinazione della trama
sconosciuta: flood
Destinazione A
conosciuta: inoltro
selettivo
A A A’
C’
B
A6A’
porta
A’ A
tempo
A
1
9:57
A’
4
10:19
1
5
bridge
MAC addr
Tabella di
inoltro
trama
2
3
4
C
B’
173
Auto-Apprendimento (1/3)
La Tabella di Inoltro di un bridge è
inizialmente vuota. Essa viene costruita e
aggiornata automaticamente, ossia senza
bisogno dell’intervento dell’amministratore di
rete.
La capacità di un bridge di costruire e
aggiornare la propria Tabella di Inoltro in
modo autonomo è detta capacità di autoapprendimento (self-learning) del bridge.
174
Auto-Apprendimento: algoritmo
(2/3)
Specificatamente, l’algoritmo di auto-apprendimento procede
come segue:
1. La tabella di Inoltro è inizialmente vuota;
2. Quando una trama arriva al bridge e l’indirizzo MAC del nodoSorgente della trama non è già contenuto nella Tabella di
Inoltro, allora il bridge memorizza:
i.
L’indirizzo MAC di tale nodo;
ii. Il numero della porta di ingresso dalla quale è arrivata la
trama;
iii. L’istante di tempo in cui la trama è arrivata.
3. Quando una trama arriva al bridge e l’indirizzo del nodoSorgente è già contenuto nella Tabella, allora la Tabella non
viene modificata.
4. Il bridge elimina (cancella) un indirizzo dalla tabella se nessuna
trama è stata ricevuta con quell’indirizzo di sorgente per un
intervallo di tempo (Tempo di Età) che, tipicamente, è
dell’ordine dei 60 minuti.
175
Auto-Apprendimento- Esempio (3/3)
Supponiamo che all’istante 9:39 una trama arrivi dalla porta di
ingresso no.2 e con indirizzo-sorgente: 01-12-23-34-45-56.
Supponiamo che questo indirizzo non sia nella Tabella di Inoltro
del bridge. Allora, il bridge lo inserisce nella Tabella di Inoltro.
Indirizzo MAC del
nodo di destinazione
Numero della porta di
uscita del Bridge
Tempo di inserimento
dell’indirizzo MAC
01-12-23-34-45-56
2
9:39
Supponiamo, ora, che il Tempo di Età della tabella sia di 60
minuti e che nessuna trama con indirizzo-sorgente:
01-12-23-34-45-56 arrivi al bridge tra l’istante 9:39 e l’istante
10:39. Allora all’istante 10:39 il bridge rimuove tale indirizzo
dalla sua Tabella di Inoltro.
176
Conversione del formato di trama
– Translating Bridge
Un bridge può essere anche usato per
interconnettere nodi di rete che impiegano
protocolli di Strato di Collegamento diversi
(eterogenei).
In questo caso il bridge, oltre ad effettuare le
funzioni di Filtraggio, Inoltro e AutoApprendimento, effettua anche la conversione
del formato della trama ricevuta dal nodosorgente nel formato di trama richiesto dal
nodo-destinazione.
I bridge che effettuano anche questa
conversione sono detti “translating bridge”.
177
Reti Ethernet con accesso a contesa
e Reti Ethernet a commutazione
178
Classificazione delle Reti
Ethernet
• Le reti Ethernet che impiegano come centrostella un hub sono dette Reti Ethernet con
accesso a contesa.
• Le reti Ethernet che impiegano come centrostella un bridge sono dette Reti Ethernet a
commutazione (Switched Ethernet LANs).
179
Reti Ethernet con Accesso a
Contesa – Generalità (1/2)
Reti Ethernet con accesso a
contesa impiegano un hub come centro-stella.
A tutti gli effetti, una rete Ethernet con accesso a
contesa alla quale sono collegati N nodi di rete
mediante canali fisici di capacità C (bit/sec) si
comporta come un sistema d’accesso multiplo che
impiega il protocollo d’accesso CSMA/CD
precedentemente descritto e analizzato.
Tipicamente, ciascun nodo di una rete Ethernet con
accesso a contesa comunica con l’hub in modo
bidirezionale e half-duplex.
Per definizione, le
180
Reti Ethernet con Accesso a
Contesa – Generalità (2/2)
Ciò significa che, dei due canali che connettono
ciascun nodo all’hub:
i. Uno è impiegato, alternativamente nel tempo,
per trasmettere dati verso l’hub e per ricevere
dati dall’hub (comunicazione nodo-hub di tipo
bi-direzionale e half-duplex);
ii. L’altro canale è impiegato dal nodo
esclusivamente per espletare la funzione di
Collision Detection (CD) richiesta dalla tecnica
di accesso CSMA/CD.
181
Reti Ethernet con Accesso a
Contesa - Tassonomia
Esistono più tipi di reti Ethernet con accesso, che si
differenziano per:
i.
la capacità C (bit/sec) del canale condiviso;
ii.
il tipo di mezzo trasmissivo impiegato dal canale condiviso.
Le diverse topologie di reti Ethernet con accesso a contesa sono
individuate con la notazione
X –Base- Y
dove:
a. X indica la capacità del canale condiviso, espressa in Mb/sec;
b. Base sta ad indicare che la modulazione adottata è di banda
base (tipicamente, la Manchester);
c. Y può essere un numero oppure una lettera:
-
-
quando è un numero, indica la copertura della rete misurata in
centinaia di metri;
quando è una lettere, specifica il mezzo trasmissivo del canale
condiviso (tipicamente, doppino telefonico o fibra ottica).
182
Caratteristiche delle principali Reti
Ethernet con Accesso a Contesa
10-Base-T
10-Base-F
Mezzo trasmissivo
Doppino UTP
Fibra in I finestra
Topologia
Stella con hub
Stella con hub
Modulazione
Manchester Bipolare
Manchester On-Off
Velocità di trasmissione
10Mb/sec
10Mb/sec
Tecnica di accesso
CSMA/CD
CSMA/CD
Velocità di propagazione
del segnale nel mezzo
trasmissivo
0.59x3x108m/sec
0.66x3x108m/sec
Distanza massima tra
due nodi
100m
500m
Numero massimo di nodi
Non specificato
33
Modalità di trasmissione
Bidirezionale half-duplex Bidirezionale half-duplex
183
Reti Ethernet con Accesso Commutato
(Switched Ethernet) – Generalità (1/2)
Per definizione, le reti Switched Ethernet
impiegano un bridge come centro-stella.
A tutti gli effetti, in una Switched Ethernet,
ad ogni coppia di nodi Sorgente-Destinazione è
dedicato un collegamento punto-punto privo di
collisioni attraverso cui i nodi possano
comunicare ad una velocità (bit/sec) pari alla
capacità C del mezzo trasmissivo impiegato
dalla rete.
Tipicamente, ciascun nodo di una rete
Switched Ethernet comunica con il bridge in
modo bidirezionale e full-duplex.
184
Reti Ethernet con Accesso Commutato
(Switched Ethernet) – Generalità
(2/2)
Ciò significa che i due canali che connettono
ciascun nodo al bridge vengono usati
simultaneamente, uno per trasmettere dati
dal nodo al bridge, e l’altro per trasmettere
dati dal bridge al nodo.
185
Classificazione delle Reti Switched
Ethernet
più famiglie di Reti Switched Ethernet, che
si differenziano per la velocità di trasmissione e/o il
tipo di mezzo trasmissivo impiegato.
Specificatamente, le tre principali famiglie di Reti
Switched Ethernet sono:
Esistono
a.
b.
c.
La famiglia Fast-Ethernet
È caratterizzata da una velocità di trasmissione di 100Mb/
sec;
La famiglia Gigabit-Ethernet
È caratterizzata da una velocità di trasmissione di 1000Mb/
sec;
La famiglia TenGigabit-Ethernet
È caratterizzata da una velocità di trasmissione di
10000Mb/sec.
186
Caratteristiche principali delle
Reti Fast - Ethernet
100-Base-T
100-Base-F
Mezzo trasmissivo
2 UTP di categoria 5
2 fibre ottiche
Topologia
Stella con bridge
Stella con bridge
Modulazione
Manchester bipolare
Manchester On-Off
Velocità di trasmissione
125 Mb/sec
125 Mb/sec
copertura
Centinaia di metri
≤ 2 Km
Modalità di trasmissione
Bidirezionale full-duplex
Bidirezionale full-duplex
187
Caratteristiche principali delle
Reti Gigabit - Ethernet
1000-Base-S
1000-Base-L
Mezzo trasmissivo
Fibra multimodo in 1°
finestra
Fibra monomodo in 2°
finestra
Topologia
Stella con bridge
Stella con bridge
Velocità di trasmissione
1.25 Gb/sec
1.25 Gb/sec
copertura
≤ 550 m
≤ 5 Km
Modalità di trasmissione
Bidirezionale full-duplex
Bidirezionale full-duplex
188
Caratteristiche principali delle
Reti TenGigabit - Ethernet
Impiegano solo fibre ottiche
Trasmettono a velocità dell’ordine di 10Gb/sec, con modalità
bidirezionale e full-duplex.
Hanno topologia a stella con bridge come centro stella.
Lunghezza d’onda
impiegata
copertura
850nm
65m
1310nm
300m
monomodo
1310nm
10Km
monomodo
1550nm
40Km
multimodo
multimodo
189
Inter-connessione di più LAN
190
Inter-connessione di più LAN –
Generalità (1/3)
Due o più LAN, di stesso tipo o di tipo
diverso, possono essere inter-connesse tra
di loro mediante:
i.
ii.
un hub;
un bridge.
scopo dell’inter-connessione è quello di
far comunicare tra di loro nodi (terminali
d’utente) che fanno parte di LAN distinte.
L’intera rete ottenuta mediante l’interconnessione è chiamata LAN. Le singole
sotto-reti che sono state inter-connesse
sono chiamate segmenti (LAN segment).
Lo
191
Inter-connessione di più LAN –
Generalità (2/3)
Hub oppure Bridge
Connessione
Connessione
Hub 3
Connessione punto-punto
Hub 1
Hub 2
NodoI
NodoC
NodoA
NodoB
Segmento 1
NodoH
NodoD
NodoE
NodoF
Baccarelli,
Segmento
2 Polli
Cordeschi,
Patriarca,
NodoG
Segmento 3
192
Inter-connessione di più LAN –
Generalità (3/3)
L’architettura di base di una LAN inter-
connessa è quella riportata nella figura
precedente. In questo caso,
i.
ii.
iii.
Il segmento 1 è costituito dall’hub 1 e i nodi A,B,C;
Il segmento 2 è costituito dall’hub 2 e i nodi D,E,F;
Il segmento 3 è costituito dall’hub 3 e i nodi G,H,I.
Ciascuno degli hub ha una connessione
bidirezionale, full-duplex oppure half-duplex
con l’hub/bridge centrale.
L’ hub/bridge centrale è chiamato hub/
bridge dorsale (backbone hub/bridge).
193
Dominio di Collisione
Quando più segmenti vengono inter-connessi,
può accadere che la trasmissione simultanea di
nodi appartenenti a segmenti differenti dia
luogo a collisioni.
In una LAN inter-connessa, si definisce
Dominio di Collisione l’insieme dei nodi
(appartenenti allo stesso segmento o a
segmenti differenti) la cui trasmissione
simultanea dà luogo a collisioni.
A seconda del modo in cui viene effettuata
l’inter-connessione, una LAN inter-connessa
può presentare uno o più domini di collisione.
194
Interconnessione mediante
Backbone-Hub (1/3)
Consideriamo l’architettura generale di inter-
connessione di M segmenti LAN mediante un
backbone-Hub riportato in figura.
Backbone Hub
Connessione
Connessione
Connessione punto-punto
Segmento M
Segmento 1
Segmento 2
195
Interconnessione mediante
Backbone-Hub (2/3)
L’inter-connessione mediante backbone-hub
ha i seguenti vantaggi:
i. E’ poco costosa e facile da realizzare;
ii. Permette a nodi appartenenti a segmenti
differenti di comunicare tra loro;
iii. Estende la copertura consentita a ciascun
singolo segmento.
196
Interconnessione mediante
Backbone-Hub (3/3)
L’inter-connessione mediante backbone-hub ha i seguenti
svantaggi:
i. Poiché un hub attua solo protocolli di Strato Fisico,
tutti i segmenti inter-connessi debbono usare la stessa
tecnologia (ad es., devono tutti essere reti Ethernet
10-base-T, oppure tutti 100-base-T);
ii. Poiché un hub non effettua l’operazione di inoltro
(forwarding), né legge gli indirizzi delle trame che gli
pervengono, tutti i segmenti inter-connessi con un
backbone-hub costituiscono un unico dominio di
collisione. Ciò significa che, se due nodi appartenenti a
due segmenti differenti trasmettono simultaneamente,
le loro trasmissioni danno luogo a collisione.
197
Interconnessione mediante
Backbone-Bridge (1/2)
Consideriamo l’altra architettura generale di
interconnessione di M segmenti mediante
backbone-bridge riportata in figura.
Backbone Bridge
Connessione punto-punto
Segmento 1
Connessione punto-punto
Connessione punto-punto
Segmento M
Segmento 2
198
Interconnessione mediante
Backbone-Bridge (2/2)
L’inter-connessione mediante backbone-bridge ha i seguenti
vantaggi:
i.
ii.
iii.
iv.
Permette a nodi di segmenti differenti di comunicare tra di loro e
quindi estende la copertura di un singolo segmento;
Poiché un bridge è in grado di modificare il formato delle trame che
riceve, i segmenti possono usare anche tecnologie diverse;
Poiché un bridge esegue le operazioni di inoltro e legge gli indirizzi
MAC delle trame che gli pervengono, ciascuno dei segmenti connessi da
un backbone bridge costituisce un singolo dominio di collisione. Ciò
significa che, se due nodi appartenenti a segmenti differenti
trasmettono simultaneamente, le loro trasmissioni non danno luogo a
collisioni.
La modalità di trasmissione tra ciascun segmento e il backbone bridge
è bidirezionale e full-duplex.
Tuttavia, un backbone-bridge è
installare di un backbone-hub.
più costoso e più difficile da
199
Protocolli di Strato di Collegamento
per canali punto-punto
200
Collegamenti Punto-Punto
Consideriamo un collegamento tra un
singolo
nodo-Sorgente e un singolo nodoDestinazione collegati da un canale fisico
dedicato.
In questo scenario,
i.
ii.
iii.
Non c’è bisogno di un protocollo di accesso al mezzo;
Non occorre indirizzare i nodi;
Il canale fisico potrebbe essere una linea telefonica, o un
collegamento SONET/SDM.
Il protocollo di Strato di Collegamento più
usato per gestire le connessioni punto-punto
è il Protocollo PPP (Point-to-Point Protocol).
201
Funzioni che il PPP deve svolgere
(1/2)
Al PPP è richiesto di svolgere le seguenti funzioni e possedere i
seguenti requisiti:
i. Costruzione di trame (packet framing): al nodo-Sorgente, il
protocollo deve essere in grado di incapsulare i datagrammi
generati dallo Strato di Rete in trame PPP;
ii. Trasparenza: il PPP non deve porre alcuna restrizione sul
formato dei dati che costituiscono i datagrammi generati
dallo Strato di Rete del nodo-Sorgente;
iii. Rivelazione degli errori: al nodo-Destinazione, il PPP deve
essere in grado di rivelare (ma non di correggere) gli
eventuali errori introdotti nelle trame ricevute dal canale
trasmissivo.
iv. Disponibilità della connessione: il PPP deve essere in grado di
rilevare l’eventuale presenza di guasti nel collegamento
sorgente-destinazione;
v. Negoziazione degli indirizzi IP: PPP deve fornire un
meccanismo agli Strati di Rete dei nodi-Sorgente e
Destinazione per scambiarsi e/o configurare gli indirizzi IP.
202
Funzioni che il PPP non deve
svolgere (2/2)
non è richiesto di svolgere le seguenti
funzioni:
Al PPP
i.
ii.
iii.
iv.
v.
Correzione degli errori eventualmente presenti
nella trama ricevuta;
Controllo della velocità del flusso di dati che il
Nodo-Sorgente invia al Nodo-Destinazione;
Trasferimento in ordine (in sequenza) delle trame
generate dal Nodo-Sorgente;
Instaurazione e gestione di collegamenti punto-amultipunto (multicast);
Attuazione di strategie ARQ per il controllo degli
errori.
203
Modello di servizio offerto dal
PPP
Il PPP è un protocollo di Strato di
Collegamento. Esso offre allo Strato di Rete
un servizio di trasferimento di datagrammi:
i. con connessione;
ii. non affidabile (no correzione errori, no
trasferimento in sequenza);
attuato mediante una modalità di
trasmissione che è:
i. Bidirezionale;
ii. Full-duplex.
204
Architettura del PPP (1/2)
Dal punto di vista dell’Architettura
Protocollare, per attuare il servizio descritto,
il PPP si avvale di 2 famiglie di protocolli, e
cioè dei:
i.
ii.
Link Control Protocol (LCP): ha il compito di
instaurare, gestire e abbattere il collegamento PPP
tra sorgente e destinazione;
Network Control Protocol (NCP): famiglia di
protocolli che il PPP utilizza per configurare
opportunamente gli Strati di Rete del NodoSorgente e del Nodo-Destinazione.
205
Architettura Protocollare del PPP
(2/2)
Strato di Rete
Strato di
collegamento
NCP
PPP
LCP
Strato Fisico
206
Formato della trama PPP
Flag: indica l’inizio della trama PPP;
Address: non viene realmente utilizzato nel PPP e gli è
assegnato come valore fisso la stringa “11111111”;
Control: anche questo campo è al momento inutilizzato;
potrebbe in futuro contenere campi di controllo multipli;
Protocol: protocollo di strato superiore al quale la trama
deve essere consegnata (e.s., PPP-LCP, IP, IPCP, etc);
Info: datagrammi degli strati superiori (datagramma IP);
Check: cyclic redundancy check per la rivelazione degli
errori.
Num.byte 1
1
1
01111110
11111111
00000011
Flag
Address
Control
1 or 2
protocol
info
Variable
length
2 or 4
1
check
01111110
Flag
207
Byte Stuffing (Aggiunta di byte)
(1/2)
requisito di trasparenza richiede che nel campo info
della trama PPP possa comparire anche la stringa di bit
“01111110”. Poiché la suddetta stringa è impiegata per
delimitare l’inizio e la fine del frame, come fa il nodoricevente a sapere se tale stringa fa parte del campo info
oppure è un flag di inizio/fine trama?
Si applica la tecnica del Byte-Stuffing, e cioè:
i. Il nodo-sorgente aggiunge (“stuff”) un byte di controllo
“01111101” prima di ogni byte di dati “01111110”;
ii. Il nodo ricevente che vede la stringa “01111110”
preceduta dal byte di controllo “01111101”,
Il
o
o
Comprende che la stringa è un byte di dati e non un
flag;
Rimuove il byte di controllo e continua a ricevere i
successivi byte.
208
Byte Stuffing (Aggiunta di byte)
(2/2)
Dati con
stesso
valore del
byte di
Flag
b5
b1
b4
b2
01111110
01111110
b2
b4
b1
b5
PPP
b5
b4
PPP
01111110
01111101
b2
Flag byte più stuffed byte
b1
209
Gestione del Collegamento PPP
(1/4)
Link Control Protocol (LCP)
gestire tutte le fasi di un collegamento tra
Nodo-Sorgente e Nodo-Destinazione.
E’ compito del
Specificatamente, le fasi previste da un
collegamento PPP sono riassunte dal seguente
Diagramma degli Stati (Diagramma dei Stati
del PPP).
210
Gestione del Collegamento PPP
(2/4)
Link
establishment
dead
authenticate
terminating
open
Network
layer config.
211
Gestione del Collegamento PPP
(3/4)
Tutti i collegamenti PPP, iniziano e terminano
nello Stato Dead;
Nello stato Link Establishment, viene instaurata
la connessione tra il Nodo-Sorgente e il NodoDestinazione (fase di hand-shaking);
Quando è prevista (per motivi di sicurezza) una
autenticazione delle identità dei Nodi-Sorgente
e Destinazione, la suddetta autenticazione è
effettuata nello Stato Authenticate.
212
Gestione del Collegamento PPP
(4/4)
Stato Network Layer Configuration, il
protocollo LCP attiva il protocollo NCP che, a sua
volta, provvede a negoziare e configurare i parametri
(quali gli indirizzi IP) degli Strati di Rete dei nodi
Sorgente e Destinazione;
Nello Stato Open, il protocollo LCP gestisce il
trasferimento delle trame tra i due nodi comunicanti;
Nello Stato Terminating, uno dei due nodi invia il
messaggio di “richiesta di Terminazione”. Se l’altro
nodo risponde con il messaggio “terminazione
accettata”, la connessione passa nello stato Dead e
viene chiusa.
Nello
213
Reti a commutazione di Pacchetto
con Modo di Trasferimento a
Circuito Virtuale (CV)
214
Reti a CV come tecnologie di
Strato di Collegamento
Come abbiamo visto, le reti Ethernet costituiscono una
tecnologia di Strato di Collegamento che offrono un
servizio privo di connessione allo Strato di Rete per il
trasferimento di datagrammi.
Le reti ATM (Asynchronous Transfer Mode) e le reti
MPLS (MultiProtocol Label Switching) possono essere
considerate tecnologie di Strato di Collegamento
basate sulla commutazione di pacchetto (multiplazione
statistica) e che offrono un servizio orientato alla
connessione allo Strato di Rete per il trasferimento
dei datagrammi.
215
Reti a Circuito Virtuale
Generalmente, ricordiamo che le Reti a
Circuito Virtuale sono caratterizzate da:
i.
ii.
iii.
iv.
Essere reti a commutazione di pacchetto;
Impiegare la multiplazione statistica ai nodi di rete;
Offrire un servizio di trasferimento dei pacchetti orientato
alla connessione;
Far ricorso ai cosiddetti Circuiti Virtuali (CV) per
implementare le connessioni tra nodi-Sorgente e nodiDestinazione.
I nodi di commutazione di una Rete a CV sono
chiamati Commutatori (Switch) o anche
Router.
216
Che cos’è un Circuito Virtuale
Consideriamo un Nodo-Sorgente A e un NodoDestinazione B all’interno di una rete a CV.
Per definizione, un Circuito Virtuale da A a B è
costituito da:
i. Una sequenza ordinata (directed path) di nodi di
rete e di canali di comunicazione dal NodoSorgente A al Nodo-Destinazione B;
ii. Un insieme di Identificatori del Circuito Virtuale
(VC Identifiers), un identificatore per ciascun
canale che costituisce il circuito virtuale. Ciascun
identificatore è, tipicamente, un numero intero.
217
Tabelle di Instradamento (1/2)
Un pacchetto generato dal Nodo-Sorgente A e che
appartiene ad un CV reca nel suo campo Intestazione
(Header Field) il numero del CV cui appartiene.
Poiché ad un medesimo Circuito Virtuale possono
corrispondere differenti identificatori (diversi VCI) su
ciascuno dei canali che costituiscono il CV stesso,
ciascun nodo di commutazione (Switch o Router) che fa
parte del CV in oggetto deve essere in grado di
aggiornare opportunamente l’identificatore di ciascuno
dei pacchetti che riceve dalle sue porte di ingresso
prima di inoltrarlo ad una (opportuna) porta di uscita.
218
Tabelle di Instradamento (2/2)
A questo scopo, il nodo di commutazione impiega la Tabella di
Instradamento in esso memorizzata.
Essenzialmente, una Tabella di Instradamento ha tante righe
quanti sono i Circuiti Virtuali che attraversano il nodo di
commutazione in cui la tabella risiede.
Ogni riga della tabella fa riferimento ad uno specifico CV e
riporta 4 informazioni:
i.
Il numero della porta di ingresso dalla quale il nodo riceve i
pacchetti del CV in oggetto;
ii.
L’identificatore di CV dal quale il nodo riceve in ingresso i
pacchetti del CV in oggetto;
iii. Il numero della porta di uscita alla quale il nodo deve
inoltrare i pacchetti;
iv. L’identificatore del CV che il nodo assegna in uscita del CV
in oggetto.
219
Tabelle di InstradamentoEsempio (1/2)
Per illustrare il concetto, consideriamo la rete illustrata in figura.
VC number
Nodo A
12
1
S1
2
22
3
S2
32
Nodo B
port
S3
S4
number
I numeri 1, 2, 3 vicino al commutatore S1 sono i numeri delle sue porte di
ingresso e uscita (bidirezionali).
Supponiamo che il nodo A richieda l’instaurazione di un CV col nodo B e
supponiamo che la rete assegni il cammino (path): AS1 S2 B e
assegni al suddetto CV i seguenti identificatori: 12, 22, 32 per ciascuno
dei 3 canali che compongono il CV.
220
Tabelle di InstradamentoEsempio (2/2)
Allora, la Tabella di Instradamento memorizzata nel
nodo di commutazione S1 assume la seguente forma:
Porta
d’ingresso
VCI
d’ingresso
Porta
d’uscita
VCI
d’uscita
1
12
3
22
Ciò significa che tutti i pacchetti che arrivano a S1
dalla porta di ingresso 1 e con VCI=12 nell’header
verranno inoltrati alla porta di uscita 3 di S1 e il loro
VCI verrà posto dal commutatore S1 pari a 22.
221
Indirizzamento nelle reti a CV
Da quanto esposto, ne concludiamo che nelle reti a CV:
L’indirizzamento dei pacchetti non è fatto
specificando gli indirizzi dei nodi sorgente e
destinazione, ma è fatto specificando il CV (ossia, il
cammino) al quale il pacchetto appartiene;
ii. Ogni volta che un nuovo CV è attivato attraverso un
nodo di commutazione, una nuova riga va aggiunta
alla Tabella di Instradamento residente nel nodo
stesso;
iii. Dualmente, ogni volta che un CV è disattivato, la
corrispondente riga va eliminata dalla Tabella di
Instradamento del commutatore.
Quindi, ciascun commutatore mantiene uno stato per
ciascun CV che lo attraversa.
i.
222
Gestione di un CV (1/2)
Poiché una rete a CV offre un servizio
orientato alla connessione, la gestione di un
CV è articolata in 3 fasi:
i. Fase di instaurazione del CV : durante
questa fase, la rete:
o
o
o
o
Individua il cammino (path) tra il nodo-sorgente e il nodo
destinazione;
Assegna i VCI ai canali che compongono il cammino;
Aggiorna le Tabelle di Instradamento di tutti i nodi di
commutazione che fanno parte del cammino;
Riserva risorse (banda, spazio nei buffer) per i
pacchetti che saranno trasmessi lungo il cammino.
223
Gestione di un CV (2/2)
ii. Fase di trasferimento dei pacchetti: la rete
trasferisce i pacchetti generati dal NodoSorgente verso il Nodo-Destinazione e
attraverso il cammino precedentemente
instaurato.
iii. Fase di abbattimento del CV: durante questa
fase, la rete:
o
o
Termina il flusso dei pacchetti attraverso il CV;
Elimina l’informazione (la riga) circa il CV in
oggetto dalle Tabelle di Instradamento di tutti i
nodi di commutazione facenti parte del cammino.
224
La tecnologia ATM
(Asynchronous Transfer Mode)
225
Reti ATM – Generalità (1/2)
esempio (non l’unico) di
rete a commutazione di pacchetto e con
modalità di trasferimento a Circuito Virtuale.
Esse possono essere viste come una tecnologia
di Strato di Collegamento in grado di offrire
un servizio di trasferimento dati orientato alla
connessione allo Strato di Rete.
I nodi di commutazione di una rete ATM
impiegano la tecnica di multiplazione statistica
e sono detti ATM switche (commutatori ATM).
Le reti ATM sono un
226
Reti ATM – Generalità (2/2)
Gli standard per ATM cominciarono a essere
sviluppati alla metà degli anni ’80 dall’ATM Forum e
dall’ITU; in pratica fu utilizzata principalmente
all’interno di reti telefoniche e IP, servendo, per
esempio, come tecnologia dei collegamenti che
connettono router IP.
Obiettivo: progettare reti in grado di trasportare file
audio e video in tempo reale, oltre a testo, e-mail e
file di immagini:
- rispondenza ai requisiti di tempo/QoS per voce e
video (rispetto al modello best-effort di Internet)
- Telefonia di ultima generazione
- Commutazione di pacchetto usando circuiti virtuali
227
Architettura protocollare di ATM
– Generalità (1/2)
AAL
celle
ATM
ATM
ATM
ATM
physical
physical
physical
physical
end system
switch
switch
end system
bit
AAL
AAL PDU
L’Architettura Protocollare di ATM è suddivisa in 3 strati:
i.
ATM Adaptation Layer (AAL)
o
è attivato solo nei nodi terminali (end-system);
o
ha lo scopo di segmentare/riassemblare i datagrammi
ricevuti/consegnati allo Strato di Rete e di attuare tutte le
funzioni necessarie per implementare il servizio di
trasferimento dati richiesto dallo Strato di Rete;
o
le unità informative generate dallo strato AAL sono dette
AAL Protocol Data Units (AAL PDU).
228
Architettura protocollare di ATM
– Generalità (2/2)
ATM Layer
o
è attuato sia dai nodi terminali che dai nodi di commutazione;
o
ha il compito di instradare il flusso di dati generato dal NodoSorgente verso il Nodo-Destinazione corrispondente;
o
le unità informative generate dallo strato ATM sono dette celle
e sono di lunghezza fissa (53 bytes).
iv. Physical Layer (Strato Fisico)
o
è attuato sia dai nodi terminali che dai nodi di commutazione;
o
ha lo scopo di convertire il flusso di celle generato dallo strato
ATM in un flusso di bit, e , poi, di consentire il trasferimento
dei bit attraverso il mezzo trasmissivo adottato dalla rete;
o
le unità informative generate dallo strato fisico sono i bit.
ii.
229
Strato AAL (1/2)
solo ai nodi terminali (non è
presente nei nodi di commutazione).
E’ presente
Al nodo sorgente, lo strato AAL riceve
datagrammi dallo Strato di Rete e li frammenta
in AAL PDU. Al nodo destinazione, lo strato AAL
riassembla le AAL PDU ricevute in datagrammi.
230
Strato AAL (2/2)
In base al tipo di servizio che la rete ATM
offre allo Strato di Rete, esistono più
protocolli di strato AAL, e
specificatamente:
i.
ii.
iii.
Protocollo AAL1 – è impiegato per emulare reti a
commutazione di circuito, quale la rete telefonica
analogica;
Protocollo AAL2 – è impiegato per il trasferimento con
bassi tempi di ritardo dei dati generati da sorgenti a
velocità di emissione variabile (ad es., codificatori video
MPEG);
Protocollo AAL5 – è impiegato per il trasferimento di
datagrammi generati dallo Strato di Rete di Internet
(trasferimento dei dati).
231
Struttura della PDU del
Protocollo AAL5 (1/2)
La struttura della PDU (unità informativa)
generata dal protocollo AAL5 è riportata in
figura.
Payload
PAD
Length
0-65535
0-47
2
CRC
4
byte
232
Struttura della PDU del
Protocollo AAL5 (2/2)
Specificatamente,
o Payload – contiene il Datagramma (dati) generato
dallo Strato di Rete. La lunghezza massima è di
65535 byte.
o PAD – serve a garantire che, complessivamente, la
lunghezza della PDU sia un multiplo intero di 48
bytes. Quindi la dimensione massima del campo PAD
è di 47 byte.
o Cyclic Redundancy Check (CRC) – serve a rivelare
(ma non a correggere) al nodo ricevente l’eventuale
presenza di errori nella AAL PDU ricevuta. Il
campo ha dimensione di 4 byte.
233
Lo Strato ATM – Funzioni (1/2)
Lo strato ATM è attuato sia ai nodi terminali che ai nodi di
commutazione della rete ATM.
Le funzioni principali svolte dallo Strato ATM sono le
seguenti tra:
i. Generazione/riassemblamento delle celle – al nodo
sorgente, lo strato ATM genera celle (cioè, Unità
Informative) di 53bytes frammentando le PDU passate
dallo Strato AAL. Al Nodo-Destinazione, lo Strato ATM
riassembla le celle ricevute, così da rigenerare le PDU
dello Strato AAL.
ii. Gestione dei circuiti virtuali – gli Strati ATM dei Nodi Sorgente e destinazione e dei nodi di commutazione
provvedono alla instaurazione, mantenimento e
abbattimento di ciascun Circuito Virtuale. Essi
provvedono anche ad assegnare a ciascun CV i
corrispondenti Identificatori (VCI).
234
Lo Strato ATM – Funzioni (2/2)
iii. Instradamento delle celle – a ciascun nodo di
commutazione il corrispondente strato ATM
provvede a :
o
Instradare le celle ricevute dalle porte di
ingresso verso le (opportune) porte
d’uscita;
o
Aggiornare la Tabella di Instradamento
memorizzata nel nodo.
235
Servizio offerto dallo Strato ATM
Il servizio offerto dallo Strato ATM allo Strato AAL
è quello di trasferimento delle PDU generate sotto
forma di celle ATM.
Il modo di trasferimento attuato dallo strato ATM è
a commutazione di pacchetto e con indirizzamento a
Circuito Virtuale.
Il servizio offerto è di tipo orientato alla connessione,
ma (in generale) non affidabile.
A seconda della tipologia della connessione instaurata,
lo Strato ATM offre:
o
o
o
o
un trasferimento di celle a velocità costante in ogni istante;
un trasferimento di celle a velocità media costante;
un trasferimento di celle a velocità minima prefissata;
un trasferimento di celle a velocità variabile e non garantita.
236
La cella ATM (1/2)
Le unità informative generate e trasferite
dallo strato ATM si chiamano celle. Ogni
cella ha una lunghezza fissa di 53 byte.
Ogni cella è costituita da
i.
ii.
un Campo Header di 5 byte;
un Campo Payload di 48 byte.
Header
5
Payload
48
byte
237
La cella ATM (2/2)
Il campo Payload contiene parte della PDU
generata dallo strato AAL.
Il campo Header è:
i. Aggiunto dallo Strato ATM del NodoSorgente;
ii. Letto e (eventualmente) modificato dallo
Strato ATM di ciascuno dei nodi di
commutazione attraversati dalla cella;
iii. Rimosso dallo Strato ATM del NodoDestinazione.
238
L’Header della cella ATM (1/2)
Essenzialmente, l’Header (5 byte) di una cella
ATM contiene l’informazione circa il CV al
quale la cella appartiene.
Sulla base della suddetta informazione,
ciascun nodo di commutazione provvede al
corretto instradamento della cella ricevuta.
La struttura dell’Header di cella ATM è
riportato in figura.
VCI
28
PT
3
CLP
HEC
1
8
bit
239
L’Header della cella ATM (2/2)
Il significato dei campi dell’Header è il seguente:
i. Virtual Channel Identifier (VCI) – è un campo di 28bit che
specifica il CV al quale appartiene la cella. Il contenuto del
VCI può essere modificato da ciascun nodo di commutazione
attraversato dalla cella.
ii. Payload Type (PT) – è un campo di 3 bit che specifica il tipo di
informazione (dati oppure informazione di controllo)
trasportata dal campo Payload della cella.
iii. Cell-Loss Priority (CLP) – è un campo di 1 bit. Le celle con
CLP=1 sono a bassa priorità (possono essere eliminate nel caso
di congestione), mentre le celle con CLP=0 sono ad alta
priorità (non possono essere scartate in caso di congestione).
iv. Header Error Control – è un campo di 8 bit. Costituisce i bit di
controllo di parità del codice che è impiegato per la
rivelazione e la correzione degli (eventuali) errori che il
canale trasmissivo ha introdotto nel (solo) header della cella.
240
Lo Strato Fisico di ATM (1/4)
sia a
nodi terminali che ai nodi di commutazione della
Rete ATM.
La funzione dello Strato Fisico è quello di
fornire una opportuna interfaccia col mezzo
trasmissivo impiegato, così che lo Strato ATM
possa trasmettere e ricevere celle con modalità
che sono indipendenti dalle caratteristiche
specifiche del mezzo trasmissivo di volta in
volta adottato.
I protocolli di Strato Fisico sono attuati
241
Lo Strato Fisico di ATM (2/4)
Lo Strato Fisico di ATM è suddiviso in
sotto-strati:
o
o
due
Trasmission Convergence Sub-Layer (TCS);
Physical-Medium Dependent Sub-Layer (PMDS);
TCS
Strato fisico di ATM
PMDS
Mezzo trasmissivo
242
Lo Strato Fisico di ATM (3/4)
Il TCS svolge tutte le funzioni richieste per
trasformare una sequenza di celle ATM in una
sequenza di bit. In particolare,
o genera e riceve il flusso binario che è
trasferito dal/al mezzo trasmissivo;
o allinea le celle ricevute/trasmesse allo
Strato ATM;
o effettua la rivelazione e correzione degli
errori eventualmente presenti nell’Header
di ciascuna cella ricevuta.
243
Lo Strato Fisico di ATM (4/4)
Il PMDS modula e demodula la sequenza di bit
ricevuta/trasmessa dal/al TCS, ed,
eventualmente, codifica e decodifica la
suddetta sequenza di bit.
Le velocità di trasmissione del flusso binario
generato/ricevuto dal PMDS possono essere
di: 155.52Mb/sec, 622.08Mb/sec, 51.84 Mb/
sec e 2.5 Gb/sec.
244