Reti di Calcolatori
a.a. 2005/06
Lezione 10
Reti di Calcolatori
Andrea Frosini
1
Nel modello di riferimento:
Application
Transport
Network
Data Link
Sottolivello MAC
Fisico
Reti di Calcolatori
Andrea Frosini
2
Medium Access Control
Nei canali di comunicazione di tipo broadcast (o multiaccess channel, o random
access channel) il livello Data Link deve gestire anche l’arbitraggio del canale:
• sullo stesso canale trasmettono e ricevono molte stazioni
• un frame può essere correttamente ricevuto solo se non si sovrappone ad alcun
altro frame
• l’accesso al canale deve quindi essere arbitrato
Il servizio di arbitraggio del canale è svolto dal sotto-livello MAC (Medium Access
Control) del livello Data Link.
Le reti broadcast più diffuse sono le LAN e le reti locali wireless
Reti di Calcolatori
Andrea Frosini
3
Allocazione statica del canale
L’allocazione statica del canale di comunicazione è il metodo più semplice per
l’arbitraggio
E’ basato sul multiplexing: FDM (Frequency Division Multiplexing) oppure TDM (Time
Division Multiplexing)
E’ efficiente quando il numero di stazioni è limitato e tutte le stazioni
trasmettono continuamente
Se il canale è suddiviso tra N stazioni, il ritardo medio per la trasmissione di
ciascun frame è N volte peggiore rispetto al caso ideale, indipendentemente
dal traffico
Se N+1 stazioni vogliono trasmettere, una di esse deve attendere che il
canale si liberi
Reti di Calcolatori
Andrea Frosini
4
Allocazione dinamica del canale
L’allocazione dinamica del canale di comunicazione consente di adattare il
processo di arbitraggio alle esigenze del traffico reale
• Modello a stazioni: Esistono N stazioni indipendenti. Se il tasso d’arrivo dei frame
è , si assume che le stazioni generino un nuovo frame nell’intervallo di tempo t
con probabilità
 t
• Singolo canale: Tutte le stazioni comunicano utilizzando uno ed un solo canale;
tutte le stazioni sono equivalenti (almeno a livello Fisico)
• Collisioni: Se due frame si sovrappongono temporalmente sul canale, si ha una
collisione: tutte le stazioni rilevano la collisione ma non possono ricevere i frame
originali. Nell’analisi, si assume che non ci siano altri errori di trasmissione
Reti di Calcolatori
Andrea Frosini
5
Gestione del tempo
Due possibilità:
• Tempo continuo (continuous time): ciascuna stazione può inviare un frame in
qualunque istante
• Tempo quantizzato (slotted time):
– ciascuna stazione è sincronizzata temporalmente con le altre
– il tempo è diviso in intervalli discreti (slot)
– ciascuna stazione può trasmettere un frame solo all’inizio di uno slot
Reti di Calcolatori
Andrea Frosini
6
Ascolto del canale
Due possibilità:
• Rilevazione dello stato del canale (carrier sense): ciascuna stazione può stabilire
prima della trasmissione se il canale è libero od occupato
• Nessuna rilevazione dello stato del canale (no carrier sense): ciascuna stazione non
può stabilire prima della trasmissione se il canale è libero od occupato
Attenzione! Poiché il canale è broadcast, ogni stazione può sempre stabilire dopo
l’invio di un frame se si è verificata una collisione oppure no
Reti di Calcolatori
Andrea Frosini
7
Protocollo ALOHA
Il protocollo ALOHA
• nato negli anni ’70 per la rete a onde radio dell’arcipelago delle Hawaii
• protocollo su rete broadcast
• si applica a qualunque sistema con stazioni non coordinate tra loro e unico canale
di comunicazione
• non vi è rilevazione del canale libero o occupato (no carrier sense)
• due versioni:
– Pure ALOHA: utilizza tempo continuo
– Slotted ALOHA: utilizza tempo quantizzato
Reti di Calcolatori
Andrea Frosini
8
Pure ALOHA
1.
una stazione inizia a trasmettere non appena un frame è pronto per essere
inviato
2.
la stazione rimane in ascolto sul canale confrontando ciò che ha spedito con ciò
che arriva (ricordarsi che il canale è broadcast, quindi alla stazione torna ciò che
lei stessa ha spedito)
3.
la stazione controlla se il proprio frame è correttamente ricevuto (assenza di
collisioni). Il feedback può essere immediato (LAN) o ritardato (in reti satellitari
circa 270 millisecondi)
4.
in caso di collisione, la stazione aspetta un certo intervallo di tempo casuale, e
poi ripete la trasmissione (se il ritardo non fosse casuale le collisioni si
potrebbero ripetere all’infinito)
Reti di Calcolatori
Andrea Frosini
9
Pure ALOHA – Esempio
tempo
tempo random di attesa
collisione
Reti di Calcolatori
Andrea Frosini
10
Pure ALOHA – Assunzioni
Assunzioni:
• Tutti i frame hanno la stessa lunghezza
• Il tempo necessario per trasmettere un frame è costante (frame time = t)
• Il numero di stazioni tende ad infinito
• Nuovi frame vengono generati con una distribuzione di Poisson con media inferiore
ad un frame per frame time
• Vecchi e nuovi frame vengono generati con una distribuzione di Poisson con media
pari a G frame per frame time
• Il tempo di vulnerabilità di un frame f è il tempo in cui nessun frame deve essere
generato se si vogliono evitare collisioni. Tale tempo è pari a 2t poiché f non deve
essere generato quando un altro frame è in trasmissione né un altro frame deve
essere generato quando f è in trasmissione.
Reti di Calcolatori
Andrea Frosini
11
Distribuzione di Poisson I
Vi sono fenomeni in cui determinati eventi, con riferimento ad un particolare periodo di
tempo, accadono raramente: il numero di eventi che si verifica in quel periodo è
aleatorio e varia da 0 a un numero n, il cui valore non è determinabile a priori.
Prima di enunciare la formula che descrive una distribuzione di Poisson, è utile
avere presenti le caratteristiche cui deve soddisfare un processo per poter essere
considerato poissoniano:
• il numero di eventi che possono verificarsi in ogni intervallo di tempo, o di spazio,
preso in considerazione, è una variabile aleatoria indipendente (ogni evento non è
influenzato dai precedenti e non influenza i successivi);
• ogni evento avviene raramente, e quindi, per un intervallo di tempo sufficientemente
piccolo, il numero di eventi non è superiore a 1;
• la probabilità che si abbiano simultaneamente k eventi è costante al trascorrere del
tempo; ciò vuol dire che, per distinti intervalli di tempo, la probabilità di k eventi
simultanei è costante.
Reti di Calcolatori
Andrea Frosini
12
Distribuzione di Poisson II
Se indichiamo con N(t) = k il numero di intervalli di tempo considerati per fenomeni
aventi le caratteristiche appena descritte e cerchiamo la probabilità di un evento in tali
intervalli (o equivalentemente cerchiamo la probabilità di k eventi in un singolo
intervallo, visto che in prima approssimazione tale numero è proporzionale al tempo
trascorso), vale la seguente formula di Poisson:
Pr [ N(t)= k ] =
a k e -a
k!
a rappresenta il numero medio di eventi nell'unità di tempo e dipende esclusivamente
dal particolare fenomeno preso in considerazione.
Reti di Calcolatori
Andrea Frosini
13
Pure ALOHA – Analisi
La probabilità che k frame (vecchi o nuovi) siano inviati in un certo frame time è
Pr [ k ] =
G k e -G
k!
Poiché in un intervallo pari a 2t (tempo di vulnerabilità di un frame) il numero medio di
frame generati è 2G, la probabilità che nessun frame sia generato (k = 0) in tale
periodo è
P0 =
2G 0 e -2G
0!
= e –2G
Il throughput per frame time (quantità di frame che arrivano a destinazione) è quindi
la probabilità di generare un frame G moltiplicato la probabilità che nessuna collisione
avvenga P0:
S = G P0 = G e –2G
Reti di Calcolatori
Andrea Frosini
14
Pure ALOHA – Analisi III
Essendo il throughput ottenibile con il protocollo Pure ALOHA
S = G e -2G
Abbiamo un massimo nel throughput quando G = 0.5 con valore Smax = 0.184
S (throughput)
(utilizzazione massima del canale: 18.4%)
G (tentativi per tempo di frame)
Reti di Calcolatori
Andrea Frosini
15
Slotted ALOHA
Il protocollo Slotted ALOHA è simile al Pure ALOHA, ma ha tempo quantizzato
• Tutte le stazioni sono temporalmente sincronizzate (ad esempio, per mezzo di un
segnale emesso da una particolare stazione “orologio”)
• Il tempo è suddiviso in slot, ciascuno lungo un frame time (tempo necessario a
trasmettere un frame)
• Ciascuna stazione può trasmettere solo all’inizio di uno slot, scandito da un segnale
speciale
Reti di Calcolatori
Andrea Frosini
16
Slotted ALOHA – Analisi
Rispetto al Pure ALOHA, l’intervallo di vulnerabilità per la probabilità di collisione di
un frame è dimezzato, dunque il throughput è raddoppiato:
S (throughput)
S = G e –G, massimo in G = 1 con valore Smax = 0.368 (utilizzo del canale: 36.8%)
G (tentativi per tempo di frame)
Reti di Calcolatori
Andrea Frosini
17
Protocolli CSMA
L’efficienza dei protocolli ALOHA è bassa perché ciascuna stazione inizia a
trasmettere senza prima verificare se il canale sia impegnato
I protocolli CSMA (Carrier Sense Multiple Access) sono molto più efficienti.
Esistono tre classi fondamentali:
• 1-persistent CSMA
• Nonpersistent CSMA
• p-persistent CSMA
Reti di Calcolatori
Andrea Frosini
18
1-persistent CSMA
Prima di trasmettere, ciascuna stazione ascolta il canale
• se il canale è libero, trasmette il frame
• se il canale è occupato, aspetta che si liberi e poi trasmette il frame
1-persistent perché trasmette con probabilità 1 se il canale è libero
Le collisioni si gestiscono con ritardi casuali. Possono comunque avvenire:
• una stazione trova il canale libero, ma un’altra ha già cominciato a trasmettere il
frame (la velocità di propagazione del segnale è finita)
• due stazioni aspettano che il canale si liberi: cominciano a trasmettere
contemporaneamente
Reti di Calcolatori
Andrea Frosini
19
Nonpersistent CSMA
Prima di trasmettere, ciascuna stazione ascolta il canale
• se il canale è libero, trasmette il frame
• se il canale è occupato, aspetta un tempo casuale, e ricomincia da capo
Anche le collisioni si gestiscono con ritardi casuali.
Poiché ciascuna stazione è meno “avida”:
è più efficiente di 1-persistent CSMA (meno collisioni)
ha ritardi di trasmissione maggiori di 1-persistent CSMA
Reti di Calcolatori
Andrea Frosini
20
p-persistent CSMA
Il tempo è quantizzato. Prima di trasmettere, ciascuna stazione ascolta il canale
• se il canale è occupato, aspetta lo slot successivo e ricomincia da capo
• se il canale è libero, con probabilità p trasmette il frame, con probabilità 1 – p
aspetta lo slot successivo e
– se lo slot successivo è libero, trasmette con probabilità p o aspetta lo slot
successivo con probabilità 1 - p
– se lo slot successivo è occupato, aspetta un tempo casuale e ricomincia
da capo (come una collisione)
Reti di Calcolatori
Andrea Frosini
21
S (throughput)
Efficienza dei protocolli CSMA
G (tentativi per tempo di frame)
Reti di Calcolatori
Andrea Frosini
22
Protocolli CSMA/CD I
L’efficienza dei protocolli CSMA è migliorabile se le stazioni sono in grado di rilevare le
collisioni prima che il frame sia completamente trasmesso
Nei protocolli CSMA/CD (Carrier Sense Multiple Access with Collision Detection)
ciascuna stazione interrompe la trasmissione del frame non appena rivela la collisione
Rilevare le collisioni non appena si verificano è possibile:
• confrontando la potenza del segnale ricevuto con quella del segnale trasmesso
• rilevando stati della funzione segnale che non codificano bit fisici (cfr. codifica di
Manchester)
Reti di Calcolatori
Andrea Frosini
23
Protocolli CSMA/CD II
Se si verifica una collisione,
- la stazione aspetta un tempo casuale
- al termine riprova a trasmettere
Se T tempo di propagazione del segnale fra gli estremi della rete, allora occorre un
tempo 2T (T in andata e T in ritorno) perché una stazione possa essere sicura di
rilevare una collisione.
Il modello concettuale che si utilizza è il seguente:
Vi è un'alternanza di periodi di contesa, di trasmissione e di inattività
Il periodo di contesa è modellato come uno Slotted Aloha con slot di durata 2T
es.: per un cavo di 1 km si ricava T = 5 µsec
Reti di Calcolatori
Andrea Frosini
24
Il periodo di contesa
Ciascun periodo di contesa è suddiviso in più slot temporali, ciascuno dei quali è
sufficientemente lungo da poter rilevare senza incertezze la presenza o l’assenza di
collisioni
contesa
Trasmissione
contesa
Trasmissione
collisione
Reti di Calcolatori
contesa
Trasmissione
non collisione
Andrea Frosini
Trasmissione
inattività
25
Gli standard IEEE 802
Descrivono diversi tipi di reti locali (LAN), wireless e metropolitane (MAN)
Adottati anche da ANSI, NIST, ISO
I più importanti:
– IEEE 802.1: introduzione, primitive delle interfaccie
– IEEE 802.2: livello Data Link superiore (protocollo LLC)
– IEEE 802.3: livello Fisico e sotto-livello MAC per CSMA/CD (Ethernet)
– IEEE 802.4: livello Fisico e sotto-livello MAC per Token Bus
– IEEE 802.5: livello Fisico e sotto-livello MAC per Token Ring
– IEEE 802.6: livello Fisico e sotto-livello MAC per DQDB (MAN)
– IEEE 802.11: livello Fisico e sotto-livello MAC per wireless LAN
– IEEE 802.15: livello Fisico e sotto-livello MAC per wireless PAN (Bluetooth)
– IEEE 802.16: livello Fisico e sotto-livello MAC per wireless MAN
Reti di Calcolatori
Andrea Frosini
26
Il protocollo LLC (Logical Link Control)
I vari standard differiscono a livello fisico e nel sottolivello MAC, ma sono compatibili
a livello data link.
Ciò è ottenuto separando dal resto, attraverso l'apposito standard LLC, la parte
superiore del livello data link, che viene usata da tutti i protocolli standard del gruppo.
Tale standard definisce il formato della PDU generica, definisce le primitive dei
servizi offerti ed infine nasconde i dettagli del sottolivello MAC al livello superiore
Reti di Calcolatori
Andrea Frosini
27
Lo standard IEEE 802.3
Descrive reti locali (LAN) di tipo broadcast con protocollo di arbitraggio di tipo
1-persistent CSMA/CD (con tempo quantizzato nella fase di contesa)
Progenitori:
• Rete ALOHA
• Rete Ethernet costruita da Xerox PARC (2.94 Mbps)
• Standard Ethernet (Xerox, DEC, Intel) (10 Mbps)
Lo standard IEEE 802.3 è largamente compatibile con lo standard Ethernet
Reti di Calcolatori
Andrea Frosini
28
Livello Fisico – Cablaggio
Sono definiti diversi tipi di cablaggi:
• Thick Ethernet
• Thin Ethernet
• Doppino telefonico
• Fibra ottica
Reti di Calcolatori
Andrea Frosini
29
Thick Ethernet I
E’ un cavo coassiale di notevole spessore (1 cm) e di colore giallo
Ufficialmente si chiama 10BASE5, che significa:
• velocità di trasmissione: 10 Mbps
• tipo di trasmissione: baseband (non multiplexing)
• lunghezza massima di ciascun segmento: 500 metri
Su ciascun segmento si possono installare al massimo 100 stazioni
Il cavo originale, usato per lo più per backbone (dorsali), è ora obsoleto
Reti di Calcolatori
Andrea Frosini
30
Thick Ethernet II
Ogni stazione è collegata al cavo coassiale da
• una scheda di rete (Ethernet card, o genericamente
NIC—Network Interface Card) installata nella stazione,
che trasmette e riceve frame, calcola il checksum, …
• un transceiver drop cable, lungo fino a 50 m,
composto da 5 doppini intrecciati schermati tra loro
• un transceiver, collegato alla scheda di rete dal
transceiver drop cable, contenente la circuiteria per
monitorare il canale (carrier sense) e rilevare le
collisioni (collision detection)
• un vampiro, un particolare spinotto che collega il
transceiver al cavo coassiale senza interromperlo
Reti di Calcolatori
Andrea Frosini
(Attachment Unit
Interface)
31
Thin Ethernet I
E’ un cavo coassiale di minore spessore (5 mm), di colore nero
Ufficialmente si chiama 10BASE2, che significa:
• velocità di trasmissione: 10 Mbps
• tipo di trasmissione: baseband (non multiplexing)
• lunghezza massima di ciascun segmento: 185 (~200) metri
Su ciascun segmento si possono installare al massimo 30 stazioni.
E’ molto economico, ma è anche poco pratico ed in via di sparizione
Reti di Calcolatori
Andrea Frosini
32
Thin Ethernet II
Ogni stazione è collegata al cavo coassiale da
• una scheda di rete (Ethernet card, o genericamente
NIC—Network Interface Card) installata nella stazione,
che trasmette e riceve frame, calcola il checksum, …
Include anche il transceiver che monitorizza il canale e
rileva le collisioni
• una giunzione a T costituita da connettori BNC
Reti di Calcolatori
Andrea Frosini
33
Doppino intrecciato
Un hub è connesso a ciascuna stazione da un doppino intrecciato
Ufficialmente si chiama 10BASE-T, che significa:
• velocità di trasmissione: 10 Mbps
• tipo di trasmissione: baseband (non multiplexing)
• basato su Twisted pair (doppino intrecciato)
La lunghezza massima di ciascun segmento (stazione–hub) va da 100 m a 200 m, a
seconda del tipo di cavo
E’ il più facile da installare e mantenere
Si possono raggiungere 100 Mbps od anche 1000 Mbps utilizzando doppini di
qualità superiore (categoria 5) e/o aumentando il numero di doppini (100BASE-TX,
100BASE-T4, 1000BASE-T)
Reti di Calcolatori
Andrea Frosini
34
Fibra ottica
E’ costituito da segmenti di fibre ottiche connessi tra loro tramite stelle passive o
ripetitori
Ufficialmente si chiama 10BASE-F (o 10BASE-FP), cioè:
• velocità di trasmissione: 10 Mbps (la limitazione è dovuta
all’interfaccia di rete tra la stazione ed il cavo a fibre ottiche)
• tipo di trasmissione: baseband (non multiplexing)
• basato su Fibra ottica
La lunghezza massima di ciascun segmento è di 2 km
Ha la più alta immunità da disturbi ed interferenze
elettromagnetiche
Esistono anche le versioni 100BASE-FX, 1000BASE-SX e 1000BASE-LX in cui le
interfacce raggiungono i 100 Mbps o 1000 Mbps
Reti di Calcolatori
Andrea Frosini
35
Ripetitori
Ogni segmento dello standard IEEE 802.3 ha una lunghezza massima (che
dipende dal tipo di cavo)
Su ciascun segmento si possono installare un numero limitato di stazioni
Per costruire reti più grandi si fa uso di ripetitori, che ricevono, amplificano e
ritrasmettono i segnali su ciascun segmento
Dal punto di vista software, due segmenti connessi da due ripetitori sono identici
ad un unico segmento
In altri termini, la presenza dei ripetitori non è visibile al livello Data Link
Reti di Calcolatori
Andrea Frosini
36
Lo standard IEEE 802.3 I
Per ciascuna rete locale IEEE 802.3:
• la distanza tra ogni coppia di stazioni deve essere minore di 2500 m
• tra due stazioni ci possono essere al più 4 ripetitori
Queste limitazioni hanno lo scopo di limitare il ritardo di trasmissione massimo, ossia
il tempo occorrente per trasmettere un bit tra le stazioni più lontane nella LAN
Reti di Calcolatori
Andrea Frosini
37
Lo standard IEEE 802.3 II
Nello standard IEEE 802.3 si utilizza la codifica di Manchester
Ciascun bit di dati è codificato da una transizione tra due valori di tensione:
• HIGH = +0.85 Volt (approssimativamente)
• LOW = -0.85 Volt (approssimativamente)
Il bit di dati 0 è codificato da una transizione dal valore HIGH al valore LOW
Il bit di dati 1 è codificato da una transizione dal valore LOW al valore HIGH
Attenzione! Nei libri di testo si possono trovare descrizioni diverse della codifica.
Qui si fa riferimento allo standard IEEE ufficiale (IEEE 802.3, 2002 Edition,
CSMA/CD, pag. 118)
Reti di Calcolatori
Andrea Frosini
38
Lo standard IEEE 802.3 III
La codifica di Manchester
• facilita la sincronizzazione temporale tra le stazioni
• ha un codice bilanciato (uguale energia per 0 e 1)
• facilita la rivelazione delle collisioni
Reti di Calcolatori
Andrea Frosini
39