1

Protocolli di Accesso al MezzoProtocolli di Accesso al Mezzo

2

MACMAC

RoadmapRoadmap

Accesso ad un mezzo di comunicazione

Allocazione delle risorse

Protocolli MACAloha puroAloha a slotAloha satellitare

Prestazioni

3

MACMAC

Materiale didatticoMateriale didatticoLibro di testo

A. Roveri – “Retematica III parte” disponibile sul sito di InfoCom– La Sapienza

Tanenbaum – “Reti di computer”

B. Walke – “Mobile Radio Networks, Networking and Protocols”

4

MACMAC

Accesso multiploAccesso multiploMezzo di comunicazione

Consente la trasmissione di informazioni a distanzaUtilizza un mezzo fisico (canale trasmissivo)

Punto – punto• Una sorgente - Una destinazione• Qualità dipende dal segnale trasmesso e dal disturbo sul canale

Multi – accesso• Due o più sistemi sorgenti/collettori di informazioni (stazioni)• Qualità dipende dal segnale tx da due o più stazioni• Somma delle versioni attenuate, ritardate, ev. rumorose di questi

contributi

2

5

MACMAC

Esempi topologie di LANEsempi topologie di LAN

Satellite

Stazioni di terra

BUS a prese multiple

Collegamento radio a pacchetti

6

MACMAC

Allocazione delle risorseAllocazione delle risorseRiguarda i mezzi di comunicazione

Statica: Suddivisione in sub-canaliPre-assegnazione individuale delle risorse

• Frequency Division Multiple Access - FDMA, • Time Division Multiple Access - TDMA, • Code Division Multiple Access – CDMA

Dinamica: il mezzo e’ una risorsa singolaAccesso in base ad una procedura di controllo

• A domanda• Pre-assegnata collettivamente

7

MACMAC

Problema dellProblema dell’’allocazioneallocazioneAssunzioni del modello:

1. N stazioni indipendentiLa probabilità che un pacchetto venga generato in un IT ΔT e’ λ∗ΔT (λcostante, frequenza di arrivo di un nuovo pacchetto)Generato il pacchetto la stazione e’ bloccata e resta inattiva finché il pacchetto non e’ stato completamente trasmesso

2. Canale singolo

3. Collisione

4. TempoContinuoDiscreto

5. Rilevamento di utilizzo del canale da parte delle stazioniCon rivelamentoSenza rivelamento

8

MACMAC

Accesso multiplo con Accesso multiplo con allocazioneallocazione dinamicadinamica

Consideriamo il dominio del tempo

Assegnazione a domanda: accesso controllato o casuale

Accesso controllato: ogni stazione emette solo quando riceve una autorizzazioneControllo:• Centralizzato

– Una stazione primaria abilita le altre secondarie alla trasmissione• Distribuito (passa da stazione a stazione)

– Le stazioni inattive non impegnano risorse– Efficiente utilizzo del mezzo trasmissivo

3

9

MACMAC

Strato MAC Strato MAC -- Medium Access ControlMedium Access Control

“Nei casi di accesso multiplo con allocazione dinamica la regolazione dell’accesso al mezzo, con la risoluzione delle eventuali contese, e’ affidata a protocolli di accesso al mezzo”

Protocolli MAC (Medium Access Control)

Roveri – Retematica III

Protocolli ad accesso controllato

Protocolli ad accesso casuale

10

MACMAC

Accesso casualeAccesso casualeModalità: ogni stazione accede al canale indipendentemente dall’effettiva disponibilità dello stesso.

UI viene emessa non appena pronta.

Se due o più stazioni richiedono contemporaneamente la risorsa: SISTEMA di CONTESA ⇒ Collisione

Mutua interferenza tra i segnali: il contenuto non e’ più utilizzabile dalle stazioniRiemissione dell’unita’ informativaMeccanismo di gestione dei conflitti

Prestazioni dipendono dall’intervallo di vulnerabilità: l’intervallo massimo di tempo entro cui una stazione può emettere una UI e collidere con un’altra emissione

11

MACMAC

AlohaAloha –– cenni storicicenni storici

(anni ’70) per una rete radio multiaccesso Università delle Hawaii, in cui più stazioni periferiche erano logicamente connesse da un unico canale ad una stazione centrale (Norman Abramson);

Il principio-chiave si adatta ad una qualsiasi rete con esigenze di accesso multiplo con allocazione dinamica;

E’ il più semplice protocollo ad accesso casuale;

Due versioni:

Aloha puroSlotted Aloha

12

MACMAC

AlohaAloha puropuroFunzionamento:

Una stazione emette una UI non appena questa è disponibile senza alcun controllo sulla disponibilità del mezzo trasmissivo.

La stazione emittente assume che si sia verificata una collisione se non riceve un Ack positivo dalla stazione di destinazione entro un determinato intervallo di tempo (time-out).

Tutte le UI coinvolte nella collisione sono considerate perdute e quindi vanno riemesse.

La UI viene riemessa dopo un tempo calcolato in base ad un algoritmo di subentro (back off); ciò per evitare nuove collisioni rendendo casuale la riemissione.

• Una legge deterministica di ritrasmissione porterebbe inevitabilmente al ripetersi della collisione

4

13

MACMAC

CollisioneCollisioneLa MAC-PDU in verde collide con quelle in blu.

Nessun arrivo, nessuna collisione!

t0 t0+Tt0-T t0+2T

14

MACMAC

AlohaAloha

15

MACMAC

AlohaAloha puro puro -- 22

Per la proprietà di retroazione del broadcasting un utente può sempre sapere se il suo pacchetto e’ giunto a destinazione

LAN: retroazione immediataSatellite: ritardo di circa 270 ms

Il tempo di ritrasmissione DEVE essere casuale per evitare fenomeni di STALLO

I pacchetti hanno la stessa dimensione perché la produttività di Alohasia MAX

Non esiste distinzione tra perdita totale e parziale di pacchetto

16

MACMAC

AlohaAloha puro puro -- 33Non c’e’ sincronizzazione

Una trama viene trasmessa SENZA aspettare l’inizio dello slot

Probabilità di collisione:la trama inviata a t0 collide con altre trame inviate nell’intervallo [t0-1, t0+1]Hp. Tempo di trasmissione trama = 1

5

17

MACMAC

AlohaAloha puropuroDef.: periodo di vulnerabilita’ V l’intervallo di tempo durante il quale possono verificarsi collisioni

Il periodo e’ pari a 2T se T e’ la durata di una trama

18

MACMAC

AlohaAloha prestazioniprestazioniLe prestazioni di una tecnica a contesa sono valutate tramite:

Throughput S: numero medio di trame trasmesse con successo per unita’ di tempoRitardo medio D per trama

19

MACMAC

StabilitStabilitàà -- 1 1 Ipotesi:

Trame di lunghezza costante (durata T)Data rate del canale fissatoN. stazioni e’ finito = mN. stazioni prenotate in un certo istante = n (assunto come stato dell’evoluzione del sistema)nello stato n

• ogni stazione tra le (m – n) “non-prenotate” emette nuove UI in modo indipendente dall’emissione di altre stazioni e con uguale probabilità p che una UI sia emessa in un dato IT;

• ogni stazione “prenotata” riemette UI in modo indipendente dalle altre n - 1 “prenotate” e con uguale probabilità q che una UI sia emessa in un dato IT.

20

MACMAC

Processo di Processo di PoissonPoissonProcesso puntuale:

Descrive la posizione di punti su un asse ordinato (es. Asse temporale)

Descrizione:n(0, t) numero di punti nell’intervallo [0,t]n(t, t+τ) numero di punti nell’intervallo [t, t+τ]

6

21

MACMAC

Processo di Processo di PoissonPoisson1. La probabilita’ che ci sia un punto di Poisson in un intervallo infinitesimo

dt e’ pari a:

λ: frequenza del processo (punti per unita’ di tempo)

2. La probabilita’ che ci siano piu’ punti in un intervallo infinitesimo dt e’nulla

3. I punti presenti in intervalli di tempo disgiunti sono variabili causali indipendenti

( )[ ] dtdtttnP λ==+ 1,

( )[ ] 01, =>+ dtttnP

22

MACMAC

Processo di Processo di PoissonPoissonLa probabilita’ che vi siano k punti di Poisson in un intervallo temporale τ e’ pari a:

( )[ ] ( ) λτλτ −==+ ek

kdtttnPk

!,

23

MACMAC

AlohaAloha: prestazioni: prestazioniIl numero medio di tentativi di trasmissione da parte delle stazioni nell'unità di tempo T (pari al tempo di trasmissione di una trama) è indicata con G ed è pari a:

G = λTλ è la frequenza media di arrivo delle trame (sia quelle nuove sia i tentativi di ritrasmissione)G è una misura relativa dell’utilizzazione del canale; se G>1 le trame generate superano il max rate di trasmissione del canale

24

MACMAC

AlohaAloha: prestazioni: prestazioniLa probabilità che vengano generate n trame dalla popolazione utente, durante il tempo di durata di una trama T, è distribuita secondo Poisson:

La probabilità di non avere collisioni (probabilità di successo Ps) è pari alla probabilità di non avere arrivi di trame (n=0) nel periodo di vulnerabilità 2T :

7

25

MACMAC

AlohaAloha: prestazioni: prestazioniHp. di processo di Poisson sul traffico ⇒ la probabilità che una trasmissione non venga interferita da altre Ps è data dalla probabilità che nell'intervallo di vulnerabilità 2T non vi siano altre trasmissioni

Il throughput S della rete si esprime come il prodotto del traffico offerto G per la probabilità di successo Ps

S indica il throughput normalizzato espresso in trame trasmesse con successo nell’unità di tempo T (varia quindi tra 0 e 1)

Viene anche detto coefficiente di utilizzazione della reteperché definisce la frazione di tempo in cui la rete è impegnata nella trasmissione con successo di trame

26

MACMAC

AlohaAloha: prestazioni: prestazioni

27

MACMAC

AlohaAloha: prestazioni: prestazioni

28

MACMAC

SlottedSlotted AlohaAlohaSimile al protocollo ALOHA, ma introduce con una sincronizzazione tra le stazioni.

L’asse dei tempi è suddiviso in intervalli temporali (IT) di durata fissa, uguale al tempo di trasmissione T di una UI.

Ogni stazione è vincolata ad iniziare l’emissione delle proprie UI in corrispondenza dell’inizio di un IT.

L’intervallo di vulnerabilità nella emissione di una UI si riduce alla durata T. si ha collisione solo in caso di emissione contemporanea di trame

8

29

MACMAC

SlottedSlotted AlohaAlohaun nodo che ha una nuova trama in arrivo: trasmette all’iniziodello slot successivo

se c’è collisione: ritrasmette la trama negli slot seguenti con probabilità p, finché ha successo

30

MACMAC

SlottedSlotted AlohaAlohaQuando arriva una trama la stazione prova a trasmetterla nel primo slot disponibile

Se si verifica una collisione la stazione prova a ritrasmetterladopo un numero di slot scelto uniformemente in un intervallo [0 – r]

31

MACMAC

SlottedSlotted AlohaAlohaRisoluzione delle collisioni:

r = 0la collisione si ripete all’infinitothroughput = 0

Se il traffico è elevato occorre un valore di r elevato per evitare instabilità

Conviene r piccolo in situazione di rete scarica, r grande in situazioni di congestione !!

32

MACMAC

SlottedSlotted AlohaAloha: : backoffbackoff esponenzialeesponenzialeCome si sceglie r?

Riconosciuta la collisione la stazione opera nel seguente modo:

sceglie un intero X a caso ed in modo uniformenell’intervallo0 – 2 Min (k, max)

• k numero di collisioni già subite dal pacchetto• max settato per limitare la dimensione massima

dell’intervallo di ritrasmissioneaspetta X slot prima di tentare la ritrasmissione

9

33

MACMAC

SlottedSlotted AlohaAloha: prestazioni: prestazioniIl periodo di vulnerabilità è pari alla durata di una trama T

La probabilità di non avere collisioni per un tempo pari al periodo di vulnerabilità (cioè la probabilità di successo Ps) è:

34

MACMAC

SlottedSlotted AlohaAloha: prestazioni: prestazioniCalcolo del max throughput

Derivando ed uguagliando a zero l’espressione:

Si ottiene il valore di G (Gmax) che corrisponde al maxtroughput Smax

35

MACMAC

SlottedSlotted AlohaAloha: prestazioni: prestazioni

36

MACMAC

AlohaAloha satellitaresatellitarePuro: efficienza del canale e’ solo del 18% ⇒ inaccettabile per un apparato del costo di milioni di $

Slotted: l’efficienza raddoppia; problema della sincronizzazione. Quando inizia uno slot?

Il satellite gestisce il problema:

Una stazione di riferimento a terra, trasmette periodicamente unsegnale speciale la cui ridiffusione viene usata da tutte le stazioni come origine dei tempi

10

37

MACMAC

AlohaAloha satellitare satellitare –– 22Ipotesi:

ΔT: lunghezza dello slot temporaleTutti gli slot hanno la stessa lunghezza

Il k-esimo slot inizierà dopo k * ΔT es. sec

Problemi:Orologi hanno velocità differenti ⇒ risincronizzazione periodicaIl tempo di propagazione dal satellite, è diverso per ogni stazione di terra ⇒ correzione preventiva

38

MACMAC

AlohaAloha satellitare satellitare –– 33Come aumentare l’utilizzo del canale di salita oltre 1/e?

Si raddoppiano il numero di canali in salita.

39

MACMAC

AlohaAloha satellitare satellitare –– 44Ogni canale di salita funziona come un canale Alhoa a slot indipendente.

Stazione sorgente:Appena pronto un pacchetto sceglie in modo casuale uno dei due canali in salitaTrasmette il pacchetto nello slot successivo.

Satellite:Se uno dei canali di salita contiene un unico pacchetto ⇒ trasmesso sul canale di discesa nello slot successivo

Se da entrambi i canali arriva un pacchetto ⇒• Trasmesso uno e memorizzato il secondo• Slot successivo viene trasmesso il secondo

40

MACMAC

AlohaAloha satellitare satellitare -- 55Prestazioni:

Si può dimostrare:Data una quantità infinita dello spazio di buffer

L’utilizzazione del canale di discesa puo’ essere aumentata fino allo 0.736

La larghezza di banda deve essere incrementata di 0.5

11

ProtocolloProtocolloCSMACSMA

42

MACMAC

CarrierCarrier SenseSense Multiple AccessMultiple Access

Deriva dall’Aloha puro, con l’aggiunta del feedbacksull’occupazione di canale

Lo strumento che rivela l'occupazione del canale viene chiamato Carrier Sensing (rilevazione di portante) e dà il nome al protocollo

È usato nella topologia a bus bidirezionale

43

MACMAC

CarrierCarrier SenseSense Multiple AccessMultiple AccessRegola: ASCOLTA PRIMA DI PARLARE

Procedura:una stazione che desidera emettere ascolta se il canale èoccupato da una emissione precedente (carrier sensing)

canale libero (idle) ⇒ la stazione emette;

canale occupato (busy) ⇒ la stazione ritarda l’emissione all’istante successivo

• CSMA Persistente: riprova immediatamente con probabilitàp quando il canale diventa idle (può causare instabilità)

• CSMA Non-persistente: riprova dopo un intervallo random 44

MACMAC

CSMA: CSMA: ritrasmissioniritrasmissioni

Nel caso di canale occupato, l'istante successivo di emissione è determinato in base ad una PROCEDURA DI PERSISTENZA:

1-persistente: il terminale ascolta finché il canale è libero e poi trasmette con probabilità 1

0-persistente o non-persistente: il terminale aspetta un tempo random prima di ritrasmettere (come se avesse colliso) (es. wireless-LAN)

p-persistente: il terminale aspetta finché il canale è libero e quindi trasmette con probabilità p, oppure con probabilità 1-p ritarda la trasmissione di un tempo casuale

12

45

MACMAC

CSMA: CSMA: ritrasmissioniritrasmissioni

1-persistente: la stazione aspetta che il canale torni libero, quindi trasmette.

46

MACMAC

CSMA: CSMA: ritrasmissioniritrasmissioni0-persistente: la stazione ritarda l’emissione di un intervallo ditempo calcolato in base ad un algoritmo di subentro (backoff)

47

MACMAC

CSMA: CSMA: ritrasmissioniritrasmissionip-persistente: la stazione attende che il canale torni libero, quindi effettua l’emissione con probabilità p, altrimenti la trasmissione èritardata di un intervallo di tempo calcolato in base ad un algoritmo di subentro

48

MACMAC

CSMA: CSMA: ritrasmissioniritrasmissioniL'algoritmo di subentro serve a rendere casuale l'accesso al canale

La procedura 1-persistente tende ad aumentare la portata media di rete, ma ad alto traffico aumenta il numero di collisioni

La procedura 0-persistente riduce lo svantaggio delle collisioni ad alto traffico

La procedura p-persistente consente di regolare la probabilità p in base al traffico di rete

13

49

MACMAC

CSMA: collisioniCSMA: collisioniA causa dei ritardi di propagazione il protocollo CSMA NON evita le COLLISIONI

il ritardo di propagazione implica che due nodi non possanosentirsi reciprocamente all’inizio della trasmissione

50

MACMAC

CSMA: collisioniCSMA: collisioniSi ha collisione tra due stazioni se esse accedono al canalein istanti che distano tra loro un tempo inferiore a quello dipropagazione tra le due stazioni

51

MACMAC

CSMA: collisioniCSMA: collisionicollisione: il tempo speso per trasmettere l’intera trama èsprecato

B e D continuano a trasmetterele loro trame interamente anchese c’è stata collisione

nota: maggiore è il ritardo dipropagazione maggiore è la probabilità di collisione!

52

MACMAC

Intervallo di Intervallo di vulnerabilitavulnerabilita’’L’intervallo di vulnerabilità, cioè l'intervallo di tempo in cui una trama emessa può subire collisione, è uguale a 2τ, dove τ è il ritardo di propagazione da estremo a estremo sul bus

14

53

MACMAC

Intervallo di Intervallo di vulnerabilitavulnerabilita’’

54

MACMAC

CSMA: prestazioniCSMA: prestazioniPer valutare le prestazioni del CSMA si assume lo stesso modello dell’Aloha con

T tempo di trasmissione di tramaτ tempo di propagazionea=τ/T

si assume inoltre la modalità non-persistente (l’unicache consente di trattare facilmente il traffico sulcanale)

55

MACMAC

CSMA: prestazioniCSMA: prestazioni

56

MACMAC

CSMA: prestazioniCSMA: prestazioni

15

CMSA CMSA –– CDCD

58

MACMAC

CSMA / CDCSMA / CDIl tempo necessario perché tutte le stazioni coinvolte in unacollisione se ne accorgano dipende dal tempo di propagazione(piccolo rispetto al tempo di trasmissione nelle LAN)

Constatazione: Perché continuare a trasmettere trame chehanno colliso?

Non appena una stazione si accorge della collisione smette ditrasmettere la trama!

CSMA-CD: “Ascolta prima di parlare e mentreparli”

Collision Detection (rilevazione delle collisioni)Rispetto al protocollo CSMA, migliora le prestazioniriducendo la durata delle collisioni=> Throughput più elevato

59

MACMAC

CSMA / CDCSMA / CDCSMA-CD

Carrier sensing, come nel CSMA collisioni rilevate in breve tempole trasmissioni che hanno colliso sono abortite, riducendo lo spreco sul canale

Collision detectionfacile nelle LAN cablate: misura le intensità dei segnali, confronta segnali trasmessi e ricevutidifficile nelle wireless-LAN: il ricevitore si disattiva mentretrasmette

60

MACMAC

CSMA / CDCSMA / CDNel caso di collisione:

La collisione viene riconosciuta (Collision Detection) La collisione viene ”rinforzata” (sequenza di jamming)Viene tentato nuovamente l'accesso dopo un intervallo di tempo casuale ∆TPer ridurre l'aumento di traffico per ritrasmissioni il valore di ∆T aumenta esponenzialmente all'aumentare del numero di collisioni consecutive

16

61

MACMAC

CSMA / CDCSMA / CD

62

MACMAC

ProtocolloProtocollo CSMA/CD (2)CSMA/CD (2)Tra due stazioni avviene una collisione se esse accedono al canale in istanti che distano tra loro un tempo inferiore a quello dipropagazione tra le due stazioni

A B C

t1

t2

t3

t

...

...

...

t4 ...

All’istante t4 C scopre la collisione

t0

63

MACMAC

CSMA / CDCSMA / CDIl tempo totale necessario affinché, nel caso di collisione, tutti i terminali si accorgano della collisione e interrompano l’emissione è:

Se R è il ritmo binario in linea, una PDU di strato MAC non può avere lunghezza inferiore a

64

MACMAC

ProtocolloProtocollo CSMA/CD (4)CSMA/CD (4)Nel caso di canale occupato, l'istante successivo di emissione èdeterminato in base ad una PROCEDURA DI PERSISTENZA

Esempio di accesso CSMA/CD:

17

65

MACMAC

CSMA / CD: vantaggi CSMA / CD: vantaggi vsvs CSMACSMA

Il vantaggio del CSMA-CD rispetto al CSMA ètanto più elevato quanto più il tempo necessario perché le stazioni coinvolte nella collisione se ne accorgano è piccolo rispetto al tempo di trasmissione della trama T

66

MACMAC

CSMA / CD: applicabilitCSMA / CD: applicabilitààIl CSMA/CD è utilizzabile in sistemi in cui il ritardo di propagazione τ sia piccolo

ascolto del canale prima di trasmettere: se il ritardo di propagazione τ è piccolo alloral’informazione raccolta dalla stazione è significativa;è bassa la probabilità che le altre stazioni tentino una trasmissione nell’intervallo [o, τ] (le altre stazioni si accorgono della collisione nel caso peggiore dopo un tempo τ);

è minore la banda sprecata a causa di una collisione

67

MACMAC

CSMA / CD: applicabilitCSMA / CD: applicabilitààIl CSMA/CD è utilizzabile in sistemi in cui il ritardodi propagazione τ sia breve rispetto alla durata T della trasmissione di una trama

ascolto del canale durante la trasmissione della trama: se iltempo di trasmissione di trama è minore del ritardo dipropagazione, la stazione finisce di trasmettere la trama, e quindi di ascoltare il canale, prima di potersi accorgere dieventuali collisioni

• la stazione può smettere di ascoltare il canale dopo un tempo 2τ e continuare a trasmettere la trama

• la condizione τ<T limita la lunghezza massima del bus!

68

MACMAC

CSMA / CD: CSMA / CD: applicabilitaapplicabilita’’

18

69

MACMAC

CSMA / CD: prestazioniCSMA / CD: prestazioniPer le prestazioni si assume sempre lo stessomodello

T tempo di trasmissione di tramaτ tempo di propagazionea=τ/Tδ tempo per accorgersi della collisione e interrompere

si assume sempre la modalità non-persistente

70

MACMAC

CSMA / CD: prestazioniCSMA / CD: prestazioni

71

MACMAC

CSMA / CD: prestazioniCSMA / CD: prestazioni