Lezione 5 – Gestione delle collisioni
Reti di Calcolatori
Modulo 1 - Tecniche di comunicazione digitale
Unità didattica 2 - Standard di rete locale
Ernesto Damiani
Università degli Studi di Milano - SSRI
Collisioni (1)
• Le collisioni si verificano quando due interfacce di
rete trasmettono contemporaneamente un frame
sullo stesso cavo o hub
– Evento molto improbabile se non fosse che la velocità di
propagazione del segnale sul vao o attraverso lo hub è
finita
Collisioni (2)
• I due nodi coinvolti rilevano la collisione
accorgendosi che il frame che leggono non sono
uguali a quelli che stanno scrivendo
Problema della rilevazione
Come si può assicurare che A si accorga che è
avvenuta una collisione?
• Analisi
– il messaggio di A raggiunge B al tempo T
– il messaggio di B raggiunge A al tempo 2T
• Pertanto:
– A si accorgerà della collisione se sta ancora trasmettendo
al tempo 2T
Un po’ di conti (1)
• Lo standard IEEE 802.3 specifica che il valore
massimo di 2T deve essere 51,2 µs, che corrisponde
a una distanza massima di 2500 m tra host
• A 10 Mbps richiede 0,1 µs per trasmettere un bit,
quindi 512 bit (64 byte) richiedono 51,2 µs per l’invio
– Conseguenza: i frame Ethernet devono essere lunghi
almeno 64 byte
Un po’ di conti (2)
Quanti dati servono?
• Intestazione 14 byte, dati 46 byte, CRC 4 byte
– se i dati sono meno di 46 byte, viene usato il riempimento
(“padding”)
• Per essere certi che tutti gli host vedano la collisione
dopo la rilevazione viene inviato un segnale di
disturbo
– Segnale di jam di 48 byte
Backoff esponenziale (1)
• Se viene rilevata una collisione, ciascuno dei due
host coinvolti attende un tempo casuale e riprova
• Se il tempo d’attesa fosse scelto casualmente tra
pochi valori, potrebbero verificarsi collisioni ripetute
Backoff esponenziale (2)
• Il tempo d’attesa viene calcolato usando il backoff
esponenziale binario
– 1a volta: sceglie K tra {0,1}, poi attesa = K*51.2 µs
– 2a volta: sceglie K tra {0,1,2,3}, poi attesa = K*51.2 µs
– n-esima volta: delay y = K*51.2 µs per K= 0... 2n – 1
• Valore massimo K= 1023
– dopo 16 tentativi l’interfaccia di rete smette di riprovare e
comunica l’errore di trasmissione all’host
FINE