4) Il sottolivello MAC (Medium Access Control)

Come già chiarito, le reti sono divise in due categorie: punto a punto e broadcast.

Nelle reti broadcast il problema principale è decidere quale elaboratore (detto anche stazione) ha diritto di usare il mezzo trasmissivo quando c'è competizione (qui non si può alzare la mano per chiedere la parola!). Si deve evitare che molte stazioni trasmettano contemporaneamente, perché i relativi segnali si disturberebbero a vicenda.

I protocolli per decidere chi è il prossimo a trasmettere su un canale broadcast (detto anche multiaccess channel o random access channel) appartengono ad un sottolivello del livello data link, detto sottolivello MAC.

Essi sono usati sopratutto nelle LAN, ma anche nelle parti di WAN basate su satelliti.

Il problema principale è come allocare il canale ai vari utenti in competizione. Ci sono due meccanismi fondamentali:

• allocazione statica, che viene decisa in anticipo;
• allocazione dinamica, che si adatta alle esigenze di ogni momento.

L'allocazione statica prevede la suddivisione del canale fra gli N utenti, ciascuno dei quali riceve di conseguenza una frazione della banda totale. Si può fare, ad esempio, con tecniche quali FDM, allocando a ciascun utente una banda di frequenze distinta da quella degli altri utenti. Ciò va bene se il numero di utenti non varia rapidamente e se tutti trasmettono con un data rate più o meno costante, però in genere comporta vari problemi:

• si verifica uno spreco di banda quando uno o più utenti non trasmettono;
• poiché il traffico è in generale molto bursty, i picchi che si verificano non possono essere gestiti solamente con la sottobanda allocata.

Viceversa, l'allocazione dinamica cerca di adeguarsi alle esigenze trasmissive, in modo da soddisfarle al meglio. Ci sono alcune assunzioni da fare:

1. modello a stazioni: ci sono N stazioni indipendenti, ognuna delle quali genera nuovi frame per la trasmissione. La probabilità di generare un frame in un intervallo di tempo T è uguale a pT, dove p è una costante e rappresenta il tasso d'arrivo dei nuovi frame. Quando un frame è generato, la stazione si blocca finché esso non è trasmesso;
2. singolo canale: un singolo canale, e null'altro, è disponibile per le comunicazioni; tutte le stazioni vi possono trasmettere e da esso possono ricevere, e tutte sono ad uguale livello;
3. collisioni: se due frame vengono trasmessi contemporaneamente, si sovrappongono ed il segnale risultante è rovinato (si verifica collisione):
   • tutte le stazioni possono rilevare la collisione;
   • i frame devono essere ritrasmessi;
   • non ci sono altri tipi di errori;
4. tempo: può essere gestito in due modi:
   • continuous time: la trasmissione di un frame può iniziare in un qualunque istante;
   • slotted time: il tempo è diviso in intervalli discreti (slot). Uno slot può contenere 0, 1 oppure più di un frame. Ciò corrisponde ad uno slot vuoto, ad uno slot con un frame e ad uno slot in cui si verifica una collisione. La trasmissione può iniziare solo all'inizio di uno slot;
5. ascolto del canale: ci sono due possibilità,
   • carrier sense (tipico delle LAN): le stazioni, prima di trasmettere, ascoltano il canale; se è occupato non cercano di trasmettere;
   • no carrier sense (tipico dei canali via satellite, nei quali vi è un elevato round trip time): le stazioni non ascoltano, trasmettono senz'altro; si preoccuperanno dopo di vedere se c'è stata una collisione.

4.1) Protocollo ALOHA

Nacque negli anni '70 per collegare tra loro, tramite radio al suolo, gli elaboratori sparsi nelle isole Hawaii.

Esistono due versioni, Pure Aloha e Slotted Aloha.

Nel Pure Aloha le stazioni trasmettono quando vogliono, però durante la trasmissione ascoltano il canale e confrontano ciò che ricevono con ciò che hanno spedito.

Dunque, se si verifica una collisione se ne accorgono, e in tal caso, dopo aver lasciato passare una quantità di tempo casuale, ritrasmettono il frame. La scelta di attendere per una quantità di tempo casuale discende dal fatto che altrimenti una collisione ne ricrea infinite altre.

Qual'è l'efficenza dello schema Aloha puro, in queste circostanze caotiche?

Definiamo come frame time il tempo necessario alla trasmissione di un frame, che ha lunghezza fissa. Supponiamo che vengano complessivamente generati dei frame con una distribuzione di Poisson avente media di S frame per frame time.

Ovviamente, se S >= 1, ci saranno quasi sempre collisioni. Per un throughput ragionevole ci aspettiamo 0 < S < 1. Purtroppo, oltre ai frame nuovi, ci sono anche quelli relativi alla ritrasmissione causata da collisioni precedenti.

Supponiamo che la distribuzione di tutti i frame (vecchi e nuovi) sia anch'essa di Poisson, con valor medio pari a G frame per frame time.

A basso carico ci aspettiamo poche collisioni, quindi G è circa uguale ad S. Ad alto carico invece avremo più collisioni, per cui G sarà maggiore di S.

In ogni caso, sotto qualunque condizione di carico il throughput (cioé la quantità di pacchetti che arrivano a destinazione) è uguale al carico offerto moltiplicato per la probabilità che la trasmissione abbia successo, ossia:

dove P(0) è la probabilità che un frame non soffra collisioni.

Per calcolare il throughput effettivo, e quindi l'efficienza, ottenibile col protocollo Pure Aloha, si devono fare due considerazioni.

La prima è che la probabilità di generare k frame durante un intervallo di tempo pari ad un frame time è data, per la distribuzione di Poisson sopra definita (avente, si ricordi, valor medio pari a G frame per frame time) dalla relazione:

Dunque, la probabilità che si generino zero frame in un intervallo di tempo pari ad un frame time è pari a

La seconda considerazione è che il periodo di vulnerabilità di un frame, cioé l'intervallo di tempo nel quale esso è a rischio di collisioni, è lungo 2 volte il frame time.

In tale periodo vengono generati mediamente 2G frame. Di conseguenza, la probabilità che non si generino nuovi frame per tutto il periodo di vulnerabilità di un frame è:

Utilizzando tale probabilità nella relazione vista sopra per il throughput, otteniamo la stima del throughput ragggiungibile col protocollo Pure Aloha, che è

ed ha la seguente forma:

Il massimo throughput è 0,184, cioé meno del 20% (due frame su 10 slot) in corrispondenza di un carico G pari a 0,5 frame per frame time.

Un modo per aumentare l'efficienza di Aloha (Roberts, 1972) consiste nel dividere il tempo in intervalli discreti, ciascuno corrispondente ad un frame time. Ovviamente gli utenti devono essere d'accordo nel confine fra gli intervalli, e ciò può essere fatto facendo emettere da una attrezzatura speciale un breve segnale all'inizio di ogni intervallo.

Le stazioni non possono iniziare a trasmettere quando vogliono, ma solo all'inizio dell'intervallo. Questo protocollo, che prende il nome di Slotted Aloha, dimezza il periodo di vulnerabilità che diviene uguale ad un solo frame time.

In tale periodo vengono generati mediamente G frame, per cui la probabilità che non si generino nuovi frame per tutto il periodo di vulnerabilità di un frame è:

Utilizzando tale probabilità nella relazione vista precedentemente per il throughput, otteniamo la stima del throughput ragggiungibile col protocollo Slotted Aloha, che è:

ed ha la seguente forma:

Il massimo throughput è 0,368, in corrispondenza di un carico G pari a 1 frame per frame time.

4.2) Protocolli CSMA (Carrier Sense Multiple Access)

Anche Slotted Aloha ha una bassa efficienza, il che d'altronde è comprensibile visto che le stazioni trasmettono senza preoccuparsi se il canale è libero.

Nelle reti locali invece le stazioni possono ascoltare il canale e regolarsi di conseguenza, ottenendo un'efficienza molto più alta. I protocolli nei quali le stazioni ascoltano il canale prima di iniziare a trasmettere si dicono carrier sense.

Ci sono vari tipi di protocolli carrier sense:

• 1-persistent
  • Quando una stazione deve trasmettere, ascolta il canale:
    • se è occupato, aspetta finché si libera e quindi trasmette;
    • se è libero, trasmette (con probabilità 1, da cui il nome).
  • Se avviene una collisione, la stazione aspetta un tempo random e riprova tutto da capo.
  • Problemi:
    • una stazione A trasmette, e prima che il suo segnale arrivi a B anche B inizia a trasmette, dunque si verifica una collisione. Più alto è il tempo di propagazione fra A e B e più grave è il fenomeno;
    • A e B ascoltano contemporaneamente durante la trasmissione di C, e non appena quest'ultima termina iniziano entrambe a trasmettere: anche in questo caso si verifica una collisione.
• Nonpersistent
  • Quando una stazione deve trasmettere, ascolta il canale:
    • se è occupato, invece di trasmettere non appena si libera come in 1-persistent la stazione aspetta comunque un tempo random e ripete tutto il procedimento da capo;
    • se è libero, si comporta come in 1-persistent.
  • Intuitivamente, ci si aspettano maggiori ritardi prima di riuscire a trasmettere un frame e meno collisioni rispetto a 1-persistent.
• P-persistent (si applica a canali slotted)
  • Quando una stazione deve trasmettere, ascolta il canale:
    • se è occupato, aspetta il prossimo slot e ricomincia da capo;
    • se è libero:
      • con probabilità p trasmette subito;
      • con probabilità 1 - p aspetta il prossimo slot; se anch'esso è libero, riapplica tale procedimento;
  • Il processo si ripete finché:
    • il frame è trasmesso, oppure
    • qualcun altro ha iniziato a trasmettere. In questo caso la stazione si comporta come in una collisione: aspetta un tempo random e ricomincia da capo.
  • Intuitivamente, al diminuire di p ci si aspettano crescenti ritardi prima di riuscire a trasmettere un frame ed una progressiva diminuzione delle collisioni.

4.3) Protocolli CSMA/CD (CSMA with Collision Detection)

Un ulteriore miglioramento si ha se le stazioni interrompono la loro trasmissione non appena rilevano una collisione, invece di portarla a termine.

Rilevare la collisione è un processo analogico: si ascolta il canale durante la propria trasmissione, e se la potenza del segnale ricevuto è superiore a quella trasmessa si scopre la collisione.

Quando si verifica una collisione, la stazione aspetta una quantità casuale di tempo e riprova a trasmettere.

Posto uguale a T il tempo di propagazione del segnale da un capo all'altro della rete, è necessario che trascorra un tempo pari a 2T perché una stazione possa essere sicura di rilevare una collisione.

Infatti, se una stazione A posta ad una estremità della rete inizia a trasmettere al tempo t₀, il suo segnale arriva a B (posta all'altra estremità della rete) dopo al tempo t₀ + T; se un attimo prima di tale istante anche B inizia a trasmettere, la collisione conseguente viene rilevata da B quasi immediatamente, ma impiega una ulteriore quantità T di tempo per giungere ad A, che la può quindi rilevare solo un attimo prima dell'istante t₀ + 2T.

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: a titolo di esempio, per un cavo di 1 km T vale circa 5 microsecondi.

4.4) Le reti ad anello

Una rete ad anello consiste di una collezione di interfacce di rete, collegate a coppie da linee punto a punto:

Le reti ad anello hanno diverse attrattive:

• non sono reti basate su un mezzo trasmissivo broadcast;
• non c'è una significativa componente analogica per la rilevazione delle collisioni (che non possono verificarsi);
• l'anello è intrinsecamente equo.

Ogni bit che arriva all'interfaccia è copiato in un buffer interno, poi rigenerato e ritrasmesso sul ring. Può essere modificato prima di essere ritrasmesso.

L'interfaccia di rete può operare in due diverse modalità, listen mode e transmit mode:

In listen mode i bit in ingresso vengono copiati nel buffer interno (dove possono essere anche modificati) e quindi ritrasmessi con un ritardo di un bit (1-bit delay).

In transmit mode l'anello è aperto, e i bit in arrivo vengono rimossi; nuovi bit vengono trasmessi sull'anello.

Una speciale configurazione binaria, detta token (gettone) circola in continuazione se nessuno vuole trasmettere.

Quando una stazione vuole trasmettere, deve:

1. aspettare che arrivi il token (in listen mode);
2. rimuoverlo dal ring (in listen mode, vedremo come);
3. trasmettere i dati (in transmit mode);
4. rigenerare il token (in transmit mode);
5. rimettersi in listen mode.

Poiché c'è un solo token, questo meccanismo risolve senza conflitti il problema dell'accesso al mezzo.

Alcune considerazioni sono degne di nota:

• il token deve essere contenuto per intero sull'anello, il che non è così ovvio come sembra (qual'è la lunghezza di un bit?);
• un frame, invece, non è necessario che ci stia tutto sull'anello (che in trasmissione è aperto), quindi non ci sono limiti alla dimensione dei frame;
• in genere esiste un tempo massimo entro il quale, una volta preso il token, si deve completare la trasmissione; ciò permette di ottenere una schedulazione round-robin delle trasmissioni;
• quando tutte le stazioni hanno qualcosa da trasmettere, l'efficienza si avvicina al 100%;
• viceversa, quando non c'è traffico, una stazione deve attendere un pò più che in CSMA/CD per trasmettere (mediamente dovrà attendere un tempo pari a quello di attraversamento di mezzo anello, per ricevere il token).

La velocità di propagazione del segnale nel rame è circa 200 metri per microsecondo. Con un data rate (ad esempio) di 1 Mbps, si genera un bit al microsecondo. Dunque, un bit è lungo in tal caso circa 200 metri, per cui per contenere 10 bit un anello dovrebbe essere lungo almeno 2 km.

In realtà sul ring trovano posto:

• x bit sull'anello, in funzione della sua lunghezza totale;
• y bit nei buffer delle interfacce delle y stazioni presenti (1 bit delay).

In definitiva, è necessario che x + y sia maggiore del numero di bit del token. Ciò significa che, a seconda delle caratteristiche dimensionali della rete in questione, può essere necessario ricavare un ritardo addizionale, sotto forma di buffer aggiuntivi, in una stazione (che ha un ruolo particolare, quello di monitor dell'anello).