Tecniche di accesso multiplo - Parte 1

Tecniche di accesso multiplo

4DI - Sistemi e reti

Classificazione delle tecniche di accesso

multiplo

∙Le tecniche di accesso multiplo si dividono in tre classi:

∙Protocolli ad accesso casuale o contesa: si possono avere interferenze tra le
stazione. Le interferenze sono recuperate mediante opportune procedure.

∙Protocolli deterministici o senza contesa: evitano la possibilità che due utenti
accedano al canale contemporaneamente (collisione) programmando l’accesso di
ogni utente.

∙CDMA (Code Division Multiple Access): le stazioni operano in continua
sovrapposizione e interferenza, ma i segnali di ciascuna stazione possono essere
recuperati grazie ad un opportuno codice.

PROTOCOLLI AD ACCESSO MULTIPLO

A CONTESA

(ACCESSO CASUALE)

SENZA CONTESA
( DETRMINISTICI)

CDMA

Protocolli di accesso multiplo casuali

o a contesa

∙Le tecniche di accesso multiplo a contesa, non prevedono nessuna gestione,
centralizzata o distribuita, dell’accesso al canale da parte delle stazioni ad esso
connesse.

∙Nel caso più generale, quando una stazione ha dei dati da trasmettere accede
immediatamente al canale senza preoccuparsi se questo è già occupato, rendendo così
molto alta la probabilità di una collisione.

∙Le tecniche di accesso random devono quindi essere in grado di risolvere le collisioni in
modo da non portare il sistema ad una situazione di blocco.

∙Le tecniche di accesso multiplo casuali più note sono:
− ALOHA (Puro e slotted)
− CSMA/CD (Carrier Sense Multiple Access / Collision Detection)

Protocolli di accesso multiplo

Quando l’accesso ad una risorsa può avvenire da parte di più utenti
indipendenti, si parla di risorsa condivisa ed è necessaria
l’implementazione di particolari protocolli di accesso multiplo. La
necessità di condividere una risorsa può derivare dal costo o dalla scarsa
disponibilità di quest’ultima ma anche dalla necessità di ottenere una
connettività rappresentata da un mezzo di comunicazione comune.

In molte reti di telecomunicazione la risorsa condivisa è rappresentata dal
canale di comunicazione

Collisione

Esempi

Bla bla

Bla bla
Bla bla

Bla bla

B1

B2

Bla bla

B0

B0

Bla bla

Interferenza
Ballablal
??????

Esempi

Collisione

??????

??????

Metodi di accesso multiplo con
contesa

Le tecniche di accesso multiplo a contesa, non prevedono nessuna gestione, centralizzata o distribuita, dell’accesso al canale da parte delle stazioni ad esso connesse. Nel caso più generale, quando una stazione ha dei dati da trasmettere
accede immediatamente al canale senza preoccuparsi se questo è già occupato, rendendo così molto alta la probabilità di una collisione. In altri casi, la stazione
“ascolta il canale” prima di trasmettere e se lo rivela occupato, ritarda la trasmissione.

Aloha

Collisione

Ogni stazione inizia la trasmissione non appena ha dei pacchetti da
trasmettere, senza considerare in nessun modo le condizioni di
occupato/libero del canale.

satellite

Aloha

Dal momento che ogni stazione ignora completamente
tutte le altre, un pacchetto subirà una collisione se la sua
trasmissione si sovrapporrà tutta o in parte a quella di un
altro pacchetto.

T
Intervallo di tempo in cui si può

avere una collisione=2T

t0
T0+2T

Se avviene una collisione il ricevitore non invierà nessun
riscontro positivo (ACK) al trasmettitore

Aloha

collisione

Nessun ACK

Attesa ACK per un tempo di andata e ritorno

???????

La stazione riprogramma una nuova trasmissione del
pacchetto dopo un tempo casuale fra 0 e un valore
massimo Tmax (tempo di back off) in modo da ridurre la
probabilità che due stazioni che hanno colliso
collidano di nuovo

Aloha slotted

Per migliorare le caratteristiche dell’ Aloha si può pensare di dividere il
tempo in time-slot di lunghezza pari al tempo che occorre per trasmettere
un pacchetto. Una stazione che ha un pacchetto da trasmettere dovrà
attendere l’inizio dello slot successivo per iniziare la trasmissione.

Slot T

La collisione avviene solo quando due stazioni decidono di
trasmettere nello stesso slot di durata T.
Adesso l’intervallo di tempo in cui si può avere la collisione
è T e non 2T come nell’Aloha puro.

tempo

ALOHA Puro

∙Ogni stazione trasmette un pacchetto composto da:
− Testata (H =header) : contenente l’indirizzo

della stazione trasmittente

− Dati
− Simboli per il controllo degli errori ( CRC)

H

DATI

CRC
Pacchetto dati

.
.

INTERFERENZA

mainframe

Definito nel 1970 da N.
Abramson all’università delle
Hawaii

Assenza di interferenza

ACK alla stazione i

Solo la
stazione i
trasmette
un pacchetto

stazione RX

A questo istante la stazione i
può trasmettere un nuovo pacchetto
poiché riceve un ACK

∙La stazione di ricezione effettua le seguenti operazioni:
− controlla se il pacchetto è stato ricevuto correttamente
− in caso positivo legge nella testata del pacchetto l’indirizzo della stazione

trasmittente (nell’esempio l’indirizzo i) e invia un riconoscimento
positivo (ACK) alla stazione trasmittente.

− Nel caso in cui il pacchetto sia rivelato in errore la stazione ricevente non

può sapere se l’indirizzo contenuto nella testata del pacchetto è corretto
oppure no e quindi non può inviare nessuna informazione (perché non sa
con certezza quale stazione ha trasmesso il pacchetto)

Il pacchetto è rivelato in errore

∙Quando una stazione non riceve dopo il tempo prestabilito la conferma di ricezione
corretta del pacchetto provvede a ritrasmetterlo adottando le seguenti regole:
−la ritrasmissione può avvenire in un istante qualunque della zona di ritrasmissione

−la stazione genera a caso l’istante di ritrasmissione generando un numero casuale tra 0 e T

Interferenza tra
i due pacchetti

Istante in cui la stazione si aspetta il segnale ACK

Zona di ritrasmissione T

Zona di ritrasmissione T

Interferenza tra stazioni

Stazione i

Stazione k

ALOHA Puro

2d

Intervallo di interferenza

to

∙Se la stazione i genera un pacchetto nell’istante t0, questo pacchetto
viene interferito se almeno un’altra stazione genera un pacchetto tra t0-d
e t0+d (d durata temporale di invio del pacchetto)

d

to-d

ot +d

ALOHA Slotted

∙Una stazione può trasmettere un pacchetto solo all’inizio di uno slot, per cui un
pacchetto generato all’istante t può essere trasmesso soltanto all’inizio
dell’intervallo successivo

La stazione i
genera un pacchetto

La stazione i trasmette il pacchetto
in questo intervallo
slot

Trasmissione
con successo

Interferenza

Stazione i

Stazione j

Stazione k

Canale

Intervallo di interferenza

Intervallo di
interferenza

Tutti i pacchetti generati in questo intervallo sono trasmessi nello slot successivo e quindi interferiscono tra
loro.
Rispetto al protocollo ALOHA puro l’ampiezza dell’intervallo di interferenza ha un’ampiezza dimezzata.

ALOHA Slotted

Aloha puro / Aloha slotted

∙Grazie all’introduzione degli slot l’Aloha slotted riesce
ad avere un’efficienza doppia rispetto all’Aloha puro.

•L’Aloha slotted richiede una sincronizzazione fra le
stazioni che comporta una maggiore complessità e costo
delle stesse.

•In ogni caso l’efficienza massima (throughput) che si
ottiene con lo slotted è solo 0.36 che è comunque molto
bassa.

Multiple Choice

Cosa sono i protocolli?

• Servono per far andare la rete più veloce

• Sono i bus collegati al microprocessore.

• I protocolli sono delle regole convenzionali che determinano uno standard per la comunicazione tra vari dispositivi.

• Sono il mezzo di trasferimento delle informazioni.

• Sono regole che permettono la comunicazione tra i vari componenti del pc.

Multiple Choice

Quale tra queste opzioni è una tecnica o protocollo di accesso casuale o a contesa?

• Access point

• Routing

• WAN

• CSMA

• Half-duplex

Fill in the Blank

Nei protocolli ___________________: si possono avere interferenze tra le stazioni trasmittenti che sono gestite con particolari procedure.

Multiple Select

Quali sono i principali protocolli di accesso multiplo casuale o a contesa?

• TDMA

• CDMA

• FDMA

• ALOHA

• CSMA/CD

Multiple Select

Quali sono le tecniche di accesso casuali?

• Aloha

• TDMA

• CSMA/CD

• FDMA

• PAN

Fill in the Blank

Le reti _________ hanno una connessione di rete diretta tra coppie di nodi, con canali riservati senza stazioni intermedie.

Multiple Choice

Le entità_________e__________sono chiamate nodi terminali del sistema mentre tutti gli altri nodi del sistema sono chiamati nodi di commutazione.

• sorgente e destinzione

• iniziale e finale

• router e bridge

• ISO e OSI

Multiple Choice

Quale fra le seguenti NON è una modalità di utilizzo del canale trasmissivo?

• simplex

• haloa

• Half-duplex

• Full-duplex

Multiple Choice

Nel protocollo "Slotted ALOHA" un nodo intende iniziare una comunicazione

• Inizia subito la comunicazione nello slot corrente senza attendere l'inizio dello successivo, se si verifica una collisione il nodo la rileva prima della fine dello slot e ritrasmette con probabilità p il suo pacchetto durante gli slot successivo

• Attende l'inizio dello slot successivo, se si verifica una collisione il nodo la rileva prima della fine dello slot e ritrasmette il suo pacchetto durante gli slot successivi, attendendo un periodo di tempo casuale

• Ascolta la comunicazione nello slot corrente per assicurarsi che nessun altro stia comunicando e senza attendere l'inizio dello slot successivo inizia la comunicazione

Multiple Choice

Affinche i dati possano arrivare dalla sorgente alla destinazione, cos'è necessario?

• i due sistemi devono usare un protocollo diverso

• un cavo usb che faccia da tramite

• i due sistemi devono usare lo stesso protocollo

• un sistema operativo diverso

Multiple Choice

Tempo di back-off

• Tempo per rilevare la collisione

• Tempo di trasmissione del pacchetto

• Tempo di attesa prima della successiva ritrasmissione

• Tempo di ritrasmissione del pacchetto

CSMA (Carrier Sense Multiple Access)
Accesso multiplo con ascolto della portante.

Il CSMA è molto simile all’Aloha, ma in questa tecnica, ogni stazione
può analizzare (ascoltare) il canale per rivelare o meno una trasmissione
in corso. L’accesso al canale avviene solo se questo è rivelato libero.

Questo non elimina del tutto la probabilità di collisioni. Infatti, occorre
considerare i tempi di propagazione del segnale fra due stazioni.

A sta
trasmettendo

A

B ascolta il canale. Lo
sente libero perché il
segnale di A non è ancora
arrivato. Inizia a
trasmettere e collide

B

CSMA: collisioni

• A causa dei ritardi di propagazione il

protocollo CSMA NON evita le COLLISIONI

∙ il ritardo di propagazione implica che due nodi

non possano sentirsi reciprocamente all’inizio
della trasmissione

CSMA: collisioni

• Si ha collisione tra due stazioni se esse

accedono al canale in istanti che distano
tra loro un tempo inferiore a quello di
propagazione tra le due stazioni

CSMA (Carrier Sense Multiple Access)
Accesso multiplo con ascolto della portante.

Nell’analisi dei protocolli CSMA, i ritardi di propagazione rivestono una
grande importanza. Quando una stazione inizia la trasmissione, le altre
stazioni connesse al mezzo potranno accorgersene solo dopo il tempo
necessario perchè il segnale si propaghi fino a loro. Si può dire che ogni
pacchetto trasmesso con CSMA ha una finestra di vulnerabilità che
coincide con il tempo che occorre affinchè la stazione più distante possa
ricevere l’inizio del pacchetto. Per questo motivo, i protocolli CSMA
funzionano bene in reti abbastanza piccole e con lunghezza dei pacchetti
elevata dato che i ritardi di propagazione devono essere piccoli rispetto
alla lunghezza dei pacchetti.

RETE

Distanza massima =

diametro della rete

CSMA

∙ Ambito LAN: le stazioni possono monitorare lo stato del canale

di trasmissione

∙ Le stazioni sono in grado di “ascoltare” il canale prima di iniziare

a trasmettere per verificare se c’è una trasmissione in corso

∙ Algoritmo CSMA

− se il canale è libero, si trasmette
− se è occupato, sono possibili diverse varianti

∙ non-persistent : rimanda la trasmissione ad un nuovo istante, scelto in modo

casuale

∙ Persistent : nel momento in cui si libera il canale, la stazione inizia a

trasmettere, se c’è collisione, come in ALOHA, si attende un tempo casuale e
poi si cerca di ritrasmettere

Non-persistent CSMA

Pacchetto A

Arrivo pacchetto

B

La stazione che ha un pacchetto da trasmettere ascolta il canale. Se lo
rivela libero inizia la trasmissione. Se il mezzo è occupato, cessa di
ascoltare il canale e genera, in modo casuale, un tempo di back-off
dopo il quale ritenterà l’accesso.

Inizio trasmissione

pacchetto B

Tempo di back-off

casuale fra 0 ed un valore

massimo

In questo modo si riduce la probabilità che più stazioni accedano
contemporaneamente non appena il canale diventa libero.

1-persistent CSMA

Pacchetto A

Arrivo pacchetto da
trasmettere alla

stazione B

Attesa

ed ascolto:

canale occupato

Ogni stazione ascolta il canale: se lo rivela libero
trasmette subito, altrimenti continua ad ascoltarlo finché
non diviene libero e subito dopo trasmette

Inizio trasmissione pacchetto da parte della
stazione B

PROBLEMA: se due stazioni generano un pacchetto durante la trasmissione
di A, attenderanno entrambe la fine della trasmissione in atto e poi
occuperanno entrambe il canale creando una collisione.

QUINDI questo sistema funziona se il traffico è poco e la probabilità che
due o più stazioni generino pacchetti durante una trasmissione è molto bassa.

P-persistent CSMA

E’ una tecnica che permette di ottenere le prestazioni
dell’ 1-persistent per bassi carichi e del non-persistent per
alti carichi.

Si tratta comunque di un protocollo poco usato perché
richiede un’elevata complessità hardware.

∙ Il tempo viene suddiviso in intervalli
∙ Algoritmo
∙ 1. ascolta il canale

− se il canale è libero

∙ si trasmette con probabilità p;
∙ se si è deciso di trasmettere, si passa al punto 2
∙ se non si è deciso di trasmettere, si attende un intervallo di tempo e si torna al punto 1

− se è occupato, si attende un intervallo di tempo e si torna al punto 1

∙ 2. se c’è collisione

− si attende un tempo casuale e poi si torna al punto 1

CSMA: p-persistente

Prestazioni sistemi CSMA

Protocollo CSMA/CD

∙ Se la stazione che sta trasmettendo rileva la collisione,

interrompe immediatamente

∙ Una volta rilevata collisione, non si continua a trasmettere

trame già corrotte

∙ Quando si verifica una collisione, si trasmette una

particolare sequenza, detta di jamming

CSMA/CD (Collision Detection)
CSMA con rivelazione delle collisioni

Nei protocolli che abbiamo visto, le stazioni non si accorgono quando
avviene una collisione e quindi continuano a trasmettere tutto il
pacchetto inutilmente.

Il protocollo CSMA/CD è stato studiato proprio per eliminare questo
spreco di banda.

Ogni stazione è dotata di un hardware che permette di rilevare una
collisione. In pratica ogni stazione ascolta il canale anche quando sta
trasmettendo.

Non appena la stazione si accorge di una collisione, cessa
immediatamente la trasmissione ed invia sul mezzo un segnale di
jamming per comunicare alle altre stazioni che il canale è occupato
dall’estinzione di una collisione. La stazione aspetta un periodo di
tempo casuale (back-off) e tenta nuovamente l’accesso.

A sta trasmettendo

CSMA/CD
A

B ascolta il canale. Lo
sente libero perché il
segnale di A non è ancora
arrivato. Inizia a
trasmettere continuando ad
ascoltare il canale.

B

A sta trasmettendo

A

B si accorge della
collisione ed interrompe
la trasmissione.
Invia il segnale di
JAMMING

B

CSMA/CD

Nel CSMA/CD il tempo di propagazione dei segnali attraverso l’intera
rete è un parametro fondamentale. E’ infatti necessario che quando
avviene una collisione tutte le stazioni lo sappiano e per questo
occorre un tempo che dipende dalla velocità di trasmissione e dalle
dimensioni della rete.

Perché il protocollo sia efficiente occorre che vi sia un certo rapporto
fra le dimensioni della rete e la durata di un pacchetto. In particolare,
la stazione A deve sapere della collisione prima che abbia finito di
trasmettere il pacchetto

RETE

PACCHETTO

JAMMING

B

A

CSMA/CD

Quindi la durata temporale di un pacchetto deve essere superiore al
tempo di propagazione (andata e ritorno) fra le stazioni più distanti
della rete.

∙A parità di lunghezza del pacchetto, per aumentare la velocità di
trasmissione occorre diminuire le dimensioni della rete.

•A parità di dimensioni della rete, per aumentare la velocità occorre
aumentare la lunghezza in bit del pacchetto

Dominio collisione 1

Dominio

collisione 2

Dominio

collisione 3

Dominio collisione 4

CSMA/CD - Domini di collisione

∙Per realizzare reti estese e ad elevata velocità occorre suddividere tali
reti in parti più piccole dette domini di collisione. Ogni stazione può
collidere solo con le macchine del proprio dominio di collisione.
Questa suddivisione si può realizzare attraverso particolari apparati di
rete quali BRIDGE e SWITCH.

Multiple Choice

Il protocollo CSMA/CD:

• è utilizzato dallo standard 802.1q

• è utile per la correzione degli errori di trasmissione

• è utile per prevenire le collisioni

• è utile per rilevare le collisioni

• nessuna delle precedenti

Multiple Choice

Segnale di jamming

• Segnale di rilevamento di collisione

• Segnale di corretta trasmissione

• Segnale di errore

• Segnale di un rischio

Multiple Choice

In un protocollo CSMA p-persistente

• In caso di collisione, o se durante i tentativi di trasmissione qualche altra stazione inizia a trasmettere, la stazione attende un tempo fisso e riprova a trasmettere nello slot successivo.

• Sono evitate tutte le collisioni grazie ad un meccanismo chiamato "Collision Avoidance"

• Chi desidera trasmettere ascolta il canale continuamente e quando lo trova libero trasmette con probabilità p oppure attende la slot successiva con probabilità 1-p

Multiple Choice

Domini di collisione

• Dominio per il rilevamento delle collisioni

• Suddivisione della rete per il rilevamento delle collisioni

• Numero di collisioni sulla rete

• Domini in cui è impossibile che avvenga una collisione

Multiple Choice

Cosa è necessario per trasmettere informazioni attraverso tutti i dispositivi di una rete?

• Un cavo di collegamento tra tutti gli host

• Un'unica tipologia di messaggio che può essere scambiato tra le diverse applicazioni

• Un insieme di regole rigide e senza ambiguità

• Un'ampia liberta di utilizzo delle modalità di comunicazione

Multiple Choice

Cosa significa CSMA/CD?

• Carrier Signal Multiple Access/Collision Detection

• Common Sense Multiple Access/Collision Detection

• Common Signal Multiple Access/Collision Detection

• Carrier Sense Multiple Access/Collision Detection

Multiple Choice

Un protocollo CSMA 1-persistente consente di

• Controllare con probaiblità 1% se il canale è libero. Appena è libero si trasmette.

• Controllare continuamente se il canale è libero. Appena è libero si trasmette.

• Controllare se il canale è libero dopo un tempo casuale. Appena è libero si trasmette.

Multiple Select

Slots (due risposte)

• Il tempo è suddiviso in frames di durata fissata

• Un numero fisso di intervalli più piccoli in cui avviene la trasmissione

• Tipica di FDMA

• Ha a disposizione tutta la banda