Reti di Calcolatori
a.a. 2005/06
Lezione 11
Reti di Calcolatori
Andrea Frosini
1
Nel modello di riferimento:
Application
Transport
Network
Data Link
Sottolivello MAC
Fisico
Reti di Calcolatori
Andrea Frosini
2
Struttura del frame IEEE 802.3
Preamble
Start of frame Indirizzi Lunghezza dati Dati Pad Checksum
• Preamble: 7 byte uguali a 10101010 che producono a 10 Mbps un’onda quadra
per 5.6 µsec per la sincronizzazione
• Start of frame: 1 byte delimitatore uguale a 10101011 (in Ethernet è un byte
uguale a 10101010)
• Indirizzi (destinazione e sorgente): specifica mittente e destinatario, gruppo di
destinatari (multicast) oppure broadcast a tutte le stazioni (indirizzo 111111)
• Lunghezza: numero di byte nel campo Dati (al massimo 1500 byte)
• Dati: contiene il pacchetto di livello Network
• Pad: utilizzato per garantire che il frame sia lungo almeno 64 byte (esclusi
Preamble e Start of frame)
• Checksum: bit di controllo calcolati tramite CRC (polinomio generatore CRC-32)
Reti di Calcolatori
Andrea Frosini
3
Indirizzi delle schede di rete
Per poter riconoscere ciascuna stazione, ad ogni scheda di rete è assegnato un
unico identificatore a 6 byte (= 48 bit)
Ad esempio: 00:50:DA:61:A7:83
Se il bit più significativo di un indirizzo è posto a 1, l’indirizzo è di tipo multicast:
specifica un gruppo di stazioni
Se tutti i bit di un indirizzo sono posti a 1, l’indirizzo è di tipo broadcast: specifica tutte
le stazioni della rete locale
Se il bit 46 (adiacente al bit più significativo) è posto a 1, l’indirizzo della scheda di
rete è locale ed assegnato dall’amministratore di rete; in caso contrario, esso è
globale ed assegnato da IEEE
Reti di Calcolatori
Andrea Frosini
4
Lunghezza minima del frame I
E’ importante riuscire a stabilire quale deve essere la lunghezza minima di un frame
per evitare
1. confusione tra segnali “spazzatura” e segnali significativi
2. mancato rilevamento di collisioni
La lunghezza minima del frame dipende essenzialmente dal round-trip time della rete
1. In caso di problemi nella trasmissione di un frame, può accadere che questo venga
spezzato o inviato solo parzialmente. In tal caso la linea di trasmissione si riempie di
piccoli pezzi di sequenze di bit che possono creare confusione nei riceventi. Ethernet
assume che ogni frame abbia una lunghezza di almeno 64 byte così da eliminare la
maggior parte di tali segnali indesiderati.
Reti di Calcolatori
Andrea Frosini
5
Lunghezza minima del frame II
2. Assumiamo che se una stazione trasmette un frame senza rilevare collisioni, lo
consideri trasmesso con successo. Sia  il tempo che impiega un segnale per coprire
la massima distanza tra due host. La seguente situazione potrebbe verificarsi:
- Host1 inizia a trasmettere un frame troppo “corto”
- Dopo un tempo 
-  anche Host2 comincia a trasmettere ed avviene una collisione
-
Reti di Calcolatori
Andrea Frosini
6
Lunghezza minima del frame III
- Host2 rileva la collisione e produce 32 bit di rumore (jam) per avvertire le altre
stazioni
bang crash
tam tam bonk
- Host1 finisce di trasmettere il frame prima che il rumore della collisione la raggiunga
bang crash
tam tam bonk
In tal caso Host1 considera il suo frame inviato con successo anche se il
destinatario potrebbe non averlo ricevuto.
Reti di Calcolatori
Andrea Frosini
7
Lunghezza minima del frame IV
Per prevenire la situazione descritta in precedenza occorre che
la lunghezza del frame sia maggiore di 2 
Ad esempio, supponendo che gli elettroni in un cavo in rame abbiano una velocità di
200 000 km/sec, e che la distanza massima tra due host sia di 2500 m, il tempo
massimo di attraversamento della rete è pari a 2500 / 200 106 = 12.5 µsec, perciò il
round trip time (andata e ritorno) è pari a circa 25 µsec
In realtà i componenti elettronici come i ripetitori introducono ulteriori ritardi; sapendo
che se ne possono avere al massimo quattro tra ciascuna coppia di stazioni,
possiamo assumere un round trip time massimo pari a 50 µsec
Se assumiamo una LAN con velocità di trasmissione pari a 10 Mbps, la lunghezza
minima del frame deve essere pari a 50 10-6 sec × 10 106 bit/sec = 500 bit (64 byte
escludendo gli 8 byte iniziali di Preamble e Start of frame)
Reti di Calcolatori
Andrea Frosini
8
Protocollo MAC dell’IEEE 802.3
E’ sostanzialmente il protocollo 1-persistent CSMA/CD:
• Prima di trasmettere si aspetta che il canale sia libero
• Appena si libera, si inizia a trasmettere
• Chiunque rileva una collisione genera un burst di rumore (jam) lungo 32 bit
• In caso di collisione, ciascun trasmittente aspetta un ritardo casuale e poi
ricomincia da capo
Reti di Calcolatori
Andrea Frosini
9
Binary Exponential Backoff Algorithm I
L’intervallo di tempo casuale in caso di collisione è regolato da un algoritmo detto
Binary Exponential Backoff
• dopo una collisione il tempo è discretizzato in slot di lunghezza 51.2 µsec (sufficienti
per trasmettere 512 bit o equivalentemente 64 byte)
• il tempo di attesa è sempre un multiplo di uno slot
• il tempo di attesa è scelto a caso, per ciascun utente, in un intervallo il cui estremo
superiore dipende dal numero n di collisioni consecutive che si sono verificate:
0
 tempo attesa (calcolato in slot) 
(2n - 1)
• dopo 16 collisioni consecutive viene segnalato un errore al livello superiore
Reti di Calcolatori
Andrea Frosini
10
Binary Exponential Backoff Algorithm II
L’algoritmo consente di mantenere a livelli accettabili sia il numero di collisioni che il
ritardo medio per la trasmissione di un frame
Supponendo che due stazioni vogliano trasmettere contemporaneamente:
• dopo la prima collisione, vi è una probabilità del 50% che si verifichi una seconda
collisione
• dopo la seconda collisione, vi è una probabilità del 25% che si verifichi una terza
collisione
• dopo la terza collisione, vi è una probabilità del 12.5% che si verifichi una quarta
collisione
• dopo la n-esima collisione (n  10), vi è una probabilità inferiore allo 0.1% che si
verifichi un’altra collisione
Reti di Calcolatori
Andrea Frosini
11
Prestazioni di IEEE 802.3
L’analisi teorica delle prestazioni di IEEE 802.3 è molto complessa, e dipende dal
modello di traffico adottato: generalmente Poissoniano (ogni stazione trasmette in
un dato istante con la stessa probabilità).
L’efficienza del canale, cioè il numero di collisioni tra frame al variare del traffico,
dipende da principalmente da
- tprop = tempo di propagazione del canale
- ttras = tempo di trasmissione del frame
- dimensioni del frame
Le prestazioni reali dello standard IEEE 802.3 sono migliori di quelle teoriche:
• tollera un carico medio del 30% (3 Mbps) con picchi del 60% (6 Mbps)
• con un carico del 30%, solo il 2–3% dei frame ha una collisione
• con un carico del 30%, solo pochi frame su 10 000 hanno due o più collisioni
Reti di Calcolatori
Andrea Frosini
12
Efficienza del canale in termini di lunghezza del frame
Efficienza di Ethernet
su linea a 10 Mbps con
time slot di 512 bit
Reti di Calcolatori
Andrea Frosini
13
Switched hub (Ethernet commutata)
La gestione delle collisioni diventa sempre più difficoltosa al crescere del traffico
nella rete e spesso sono necessari sistemi HW che ne aiutino la gestione.
In particolare, gli switched hub (o semplicemente switch), collegano le stazioni
dividendole in domini di collisione indipendenti l’uno dall’altro
Ciascun dominio include un certo numero di stazioni (tra 1 e 8)
Una collisione all’interno di un dominio è gestita come una normale collisione
All’interno dello switch, si esamina l’indirizzo destinazione di ogni frame arrivato
senza collisioni, poi, se necessario, si indirizza il frame sulla porta di destinazione
in un altro dominio di collisione
L’uso di uno switch può migliorare il throughput della rete di un ordine di grandezza
Reti di Calcolatori
Andrea Frosini
14
Standard IEEE 802.3u — Fast Ethernet
Lo standard IEEE 802.3u (emanato nel 1995 e chiamato spesso Fast Ethernet)
prevede un aumento della velocità di trasmissione da 10 Mbps a 100 Mbps
La principale difficoltà consiste nella rilevazione delle collisioni (lunghezza minima
del frame vs. distanza massima tra ciascuna coppia di stazioni)
E’ basata sulla topologia a stella, come 10BASE-T, ma ha tre varianti principali:
• 100BASE-T4 (usa 4 doppini di categoria 3)
• 100BASE-T2 (usa 2 doppini di categoria 3)
• 100BASE-TX (usa 2 doppini di categoria 5)
• 100BASE-FX (usa 1 cavo a fibre ottiche)
Reti di Calcolatori
Andrea Frosini
15
Standard IEEE 802.3z — Gigabit Ethernet I
Lo standard IEEE 802.3z è stato emanato nel 1998.
Usa il formato standard Ethernet ed compatibile con 10BASE-T e 100BASE-T, ma
la velocità arriva a 1 Gbps
Permette sia il collegamento punto a punto tra due stazioni, che il collegamento a
stella tramite hub o switch
Quattro varianti principali:
Nome
Mezzo trasmissivo
Segmento max
1000BASE-SX
Fibra ottica multimodale
550 m
1000BASE-LX
Fibra ottica mono o multimodale
5000 m
1000BASE-CX
Due doppini schermati (STP)
25 m
Quattro doppini cat. 5
100 m
1000BASE-T
Reti di Calcolatori
Andrea Frosini
16
Standard IEEE 802.3z — Gigabit Ethernet II
Può operare in due modalità:
• Full-duplex: si usano switch senza collisioni (domini di collisione di dimensione 1),
quindi la lunghezza max dei segmenti non è dovuta alla rilevazione delle collisioni
• Half-duplex: si usano hub, quindi vi sono collisioni gestite con CSMA/CD. Poiché
il frame minimo di 64 byte può essere trasmesso in soli 512 nanosecondi, la
distanza massima tra due stazioni dovrebbe essere ridotta a 25 m. Per arrivare fino
a 200 m:
– l’hardware aggiunge dati al frame fino a 512 byte (carrier extension)
– è possibile inviare più frame in sequenza (frame bursting)
In ogni caso, la velocità è così alta che Gigabit Ethernet deve avere un controllo di
flusso (frame di tipo “PAUSE”)
Reti di Calcolatori
Andrea Frosini
17
IEEE 802.4 (Token Bus)
Lo standard IEEE 802.4 descrive una LAN chiamata Token Bus:
• Al livello Fisico è un “bus” (un unico canale di tipo broadcast), come IEEE 802.3
• Progettata per applicazioni “real-time” (il ritardo massimo di trasmissione di un
frame è limitato)
• Logicamente le stazioni sono disposte ad anello (ciascuna conosce gli indirizzi
delle stazioni a “destra” e “sinistra”)
• L’arbitraggio del canale è basato sulla circolazione di un token
• Il mezzo trasmissivo è costituito da uno o due cavi coassiali broadband
• Ha velocità di 1, 5, e 10 Mbps
E’ uno standard ormai in disuso
Reti di Calcolatori
Andrea Frosini
18
IEEE 802.5 (Token Ring)
Lo standard IEEE 802.5 descrive una LAN chiamata Token Ring:
• A livello Fisico è di tipo punto a punto, ma le stazioni sono disposte ad anello
• A livello Data Link è di tipo broadcast (la rete Token Ring è considerata una rete
broadcast)
• Basato sul modello di rete locale proposto dall’IBM se ne differenzia per la
velocità di 1 Mbps, non prevista da IBM
• L’arbitraggio del canale (logico) formato dai link è basato su token
• Velocità di trasmissione: 1 Mbps, 4 Mbps, 16 Mbps, 100 Mbps
Reti di Calcolatori
Andrea Frosini
19
IEEE 802.5: interfaccia tra stazione e anello
• Ciascuna stazione è connessa
all’anello da una interfaccia
• In ciascuna interfaccia entrano due
link punto a punto dell’anello, e due
linee di input/output verso la stazione
• Ciascuna interfaccia opera in due
modalità: listen mode e transmit
mode
Reti di Calcolatori
Andrea Frosini
20
IEEE 802.5 Il token
Quando tutte le stazioni sono inattive, una particolare sequenza di 3 byte chiamata
token (gettone) circola sull’anello
La trasmissione è possibile solo subito dopo aver ricevuto il token
Poiché un solo token circola, una sola stazione può trasmettere in ciascun istante
L’anello deve essere in grado di contenere interamente il token
Ma … da quanti bit deve essere formato il token al massimo?
Reti di Calcolatori
Andrea Frosini
21
IEEE 802.5 Lunghezza di un bit
Se la rete ad anello ha un tasso di trasmissione di R Mbps, viene trasmesso 1 bit ogni
1/R µsec
Con una velocità di propagazione del segnale tipicamente di 200 m/µsec, ogni bit
occupa 200/R metri dell’anello
Ad esempio, una rete ad anello lunga 500 m e con data rate di 4 Mbps può contenere
in ciascun istante solo
500 × 4 / 200 = 10 bit
Quindi è necessario introdurre ritardi in ciascuna stazione in modo che l’anello sia in
grado di contenere almeno il token (24 bit). Il ritardo viene introdotto dall’interfaccia di
ogni stazione che viene attraversata. Tale ritardo è usualmente di un bit (125 µsec).
Reti di Calcolatori
Andrea Frosini
22
IEEE 802.5 Il token
Byte
1
1
1
SD
AC
ED
SD, ED (Starting Delimiter e Ending Delimiter): sono due byte che violano la
codifica Manchester differenziale: HIGH/HIGH e LOW/LOW
AC (Access Control): serve per il controllo dell'accesso. Sono 8 bit organizzati in
PPP T M RRR
- i tre bit P indicano la priorità attuale
- il bit M serve per il controllo di frame orfani
- il bit T, detto token bit, identifica un token (0) o un frame (1)
- i tre bit R indicano la priorità richiesta
Reti di Calcolatori
Andrea Frosini
23
IEEE 802.5 Il frame
1
1
SD
AC
1
2/6
Frame Destination
Control Address
2/6
Source
Address
no limit
4
Data Checksum
1
ED
1
Frame
Status
Frame Control: distingue frame dati da quelli di controllo
Checksum: come in IEEE 802.3
Frame Status: contiene due bit A (arrivato) e due bit C (copiato) che sono
duplicati per aumentare la robustezza del protocollo. Tale campo non è compreso
nel checksum
Reti di Calcolatori
Andrea Frosini
24
IEEE 802.5 Trasmissione di un frame
Se una stazione vuole trasmettere un frame:
1. aspetta l’arrivo del token (in listen mode, quindi ritrasmettendo subito tutti i bit in
transito, cioè facendoli passare senza alterazioni); il token è lungo tre byte, ma viene
riconosciuto per mezzo di un bit nel byte centrale (parte CD)
2. trasforma il byte centrale del token nel secondo byte del frame da trasmettere, e lo
trasmette (si passa da listen mode a transmit mode; il primo byte di ciascun frame è
sempre uguale al primo byte del token)
3. trasmette il resto del frame (in transmit mode); durante la trasmissione del frame,
scarta tutti i bit del proprio frame che hanno già completato il giro dell’anello
4. trasmette altri frame se ne ha da spedire ed ha ricevuto il token da meno di 10 msec
(token-holding time)
5. scarta i restanti bit dei frame che hanno completato il giro dell’anello
6. rigenera il token (in transmit mode) e ritorna in listen mode
Reti di Calcolatori
Andrea Frosini
25
IEEE 802.5 Ricezione di un frame
Per ricevere un frame una stazione opera solo in listen mode:
1. per ciascun frame che si sta ricevendo, controlla l’indirizzo di destinazione
2. se l’indirizzo di destinazione coincide con quello dell’interfaccia:
• invia il frame alla stazione
• ritrasmette il frame sull’anello (eventualmente modificandolo se deve
confermare l’avvenuta ricezione)
Tutto questo operando su di un solo bit alla volta!
Reti di Calcolatori
Andrea Frosini
26
IEEE 802.5 Il mezzo trasmissivo
Ciascun collegamento punto a punto di una rete IEEE 802.5 generalmente realizzato
da un doppino intrecciato; altri mezzi trasmissivi come la fibra ottica sono possibili
- La lunghezza massima di ciascun collegamento con doppino intrecciato varia tra
150 m e 340 m
- Il numero massimo di stazioni è 260
- Il cablaggio è effettuato tramite un wire center
• fisicamente assomiglia ad una topologia a stella,
in realtà è sempre un anello (star-shaped ring)
• consente di cortocircuitare automaticamente una
stazione se una interfaccia o un collegamento non
funziona
• più wire center possono essere collegati tra loro
Reti di Calcolatori
Andrea Frosini
27
IEEE 802.5 Codifica Manchester differenziale
Nello standard IEEE 802.5 si utilizza la codifica di Manchester differenziale
Ciascun bit di dati è codificato da una transizione tra due valori di tensione:
• HIGH = un valore compreso tra +3.0 e +4.5 Volts
• LOW = un valore compreso tra -4.5 e -3.0 Volts
Il bit di dati 0 è codificato da una transizione del bit fisico all’inizio del bit logico
Il bit di dati 1 è codificato dall’assenza di una transizione del bit fisico all’inizio di un
bit logico In ogni caso, in mezzo al bit logico vi è sempre una transizione
Reti di Calcolatori
Andrea Frosini
28
IEEE 802.5 Ack del frame
Quando una interfaccia riceve un frame avente il suo indirizzo destinazione,
ritrasmette il frame settando ad 1 i bit A del Frame Status
Se inoltre il frame viene inviato alla stazione, imposta ad 1 anche i bit C del Frame
Status
Quando il trasmittente legge i bit di ritorno:
• Se A=0 e C=0: la stazione destinazione non è nell’anello
• Se A=1 e C=0: la stazione destinazione è nell’anello ma non può accettare il
frame (ad esempio, buffer pieni)
• Se A=1 e C=1: la stazione destinazione ha ricevuto il frame senza problemi
Reti di Calcolatori
Andrea Frosini
29
IEEE 802.5 Rilevamento di errori
Ciascuna interfaccia effettua un controllo dei bit in transito
Se una qualsiasi interfaccia rileva un errore (ad esempio, una codifica di
Manchester illegale), imposta a 1 un bit E nell’ Ending Delimiter del frame
Inoltre l’interfaccia destinazione imposta a 1 il bit E se il campo Checksum rileva un
errore di trasmissione
Reti di Calcolatori
Andrea Frosini
30
IEEE 802.5 Priorità dei frame
Il campo Access Control contiene alcuni bit Priority che identificano la priorità del
frame da trasmettere (maggiore valore = maggiore priorità)
Se una stazione vuole trasmettere con una certa priorità n:
• deve attendere un token con un valore minore o uguale a n in Priority
• può prenotare la priorità del prossimo token scrivendo n nei bit Reservation del
campo Access Control dei frame in transito
Il protocollo è complicato: esistono regole per cercare di evitare che i frame con
bassa priorità siano completamente “tagliati fuori”
Reti di Calcolatori
Andrea Frosini
31
IEEE 802.5 Stazione monitor
Un protocollo apposito permette di scegliere una stazione dell’anello come monitor.
Ogni stazione può diventare monitor, ma ad ogni istante ne esiste uno solo.
La stazione monitor deve:
• controllare (usando un timer) che il token non vada perso
• togliere i frame danneggiati dall’anello controllando il formato e/o il checksum di
ogni frame in transito
• togliere i frame orfani utilizzando il bit Monitor nel campo Access Control di ogni
frame. Un frame diventa orfano quando la rete è lunga, il frame è corto, ed il
trasmittente viene isolato prima che possa rimuovere il frame dall’anello
• introdurre ritardi se l’anello non può contenere i 24 bit del token
Reti di Calcolatori
Andrea Frosini
32
IEEE 802.5 Vantaggi e svantaggi
il mezzo trasmissivo usa tecnologia hardware punto a punto: ben collaudata,
semplice, affidabile
la circuiteria delle interfacce è completamente digitale
l’uso di wire center permette di escludere una stazione o interfaccia guasta
“automaticamente”
ha supporto per traffico “real-time”
i frame hanno ridotta dimensione minima e alta dimensione massima
ha ottime prestazioni in termini di efficienza e throughput per carichi elevati
la stazione monitor è un punto debole
il ritardo di trasmissione non è mai trascurabile ed aumenta con la
dimensione della rete
Reti di Calcolatori
Andrea Frosini
33