Tag Archives: approfondimento sottostrato MAC

Sottostrato MAC nelle Reti di Calcolatori

SOTTOSTRATO MAC (medium access control)

Nelle reti di calcolatori esistono due tipo di reti, quelle che utilizzando connessioni punto-punto e quelle che usano dei canali broadcast. Il sottostrato mac si occupa di quest’ultime, e in questo tipo di reti a diffusione globale (che possono essere anche multicast, si riserva 1 bit per identificare questo tipo di rete) troviamo alcuni pacchetti che vengono inviati da una qualsiasi macchina e vengono ricevuti da tutte le altre. Un capo indirizzo all’interno del pacchetto stesso indica a chi è destinato, e quando una delle macchine riceve un pacchetto controlla il campo indirizzo: se era destinato a lei lo elabora altrimenti semplicemente lo ignora.

Avendo la rete broadcast un unico canale di trasmissione, il problema principale che si incontra è come gestire il diritto di acquisizione all’utilizzo del canale.

Il sottostrato MAC è utile sopratutto nelle LAN, ovvero nelle reti locali, poiché nelle WAN si preferisce un tipo di connessione point-to-point.

Il tema centrale che sarà trattato qui è il modo di assegnare un singolo canale broadcast a utenti che vanno in competizione tra di loro.

Assegnazione statica del canale in LAN e MAN

Per assegnare un singolo canale, solitamente si usa il multiplexing a divisione di frequenza (il cosiddetto FDM (Frequency Division Multiplexing), ma se ci sono N utenti, la banda è divisa in N parti uguali e quindi ogni singolo utente ne riceve un po’.

In questo caso poiché ogni utente ha una singola banda di frequenza non c’è alcuna interferenza tra di loro.

C’è un problema: quando il traffico di informazioni diventa molto elevato, o il traffico è irregolare, questo meccanismo (l’FDM) presenta delle inefficienze: semplicemente se degli utenti non stanno effettuando delle operazioni e quindi sono inattivi la banda che era stata loro concessa viene sprecata, e siccome questo meccanismo ripartisce la banda in parti esattamente uguali non vi sarà alcun modo di assegnare la banda inutilizzata a chi ne richiede di più in quel momento.

  • Assegnazione dinamica del canale in LAN e MAN

Supponiamo che le stazioni di comunicazione sono indipendenti e che il lavoro viene generato ad una frequenza considerata costante. Le stazioni non possono fare come si farebbe in una riunione di lavoro, ovvero alzare la mano per chiedere il permesso di parlare, quindi vi sarebbero inevitabilmente delle collisioni.

Si potrebbe quindi fare in due modi: adottare il tempo continuo dove la trasmissione dei frame può iniziare in qualunque istante, e non esiste un orologio di riferimento principale che divide il tempo in intervalli discreti, oppure utilizzare il tempo diviso in intervalli. In quest’ultimo il tempo è diviso in intervalli discreti (slot) dove la trasmissione di un frame concide sempre con l’inizio di un intervallo. Questo intervallo contiene 0, 1 o più frame.

Andiamo ora ad analizzare alcuni protocolli del sottostrato MAC per l’accesso multiplo.

Iniziamo col parlare di ALOHA, un metodo inventato da Norman Abramson negli anni 70 che cerca di risolvere l’assegnazione del canale.

Questo sistema adotta la trasmissione radio broadcast basata sulle stazioni terrestri, e l’idea di fondo può essere applicata a qualunque sistema dove degli utenti che non sono coordinati, competono per utilizzare un singolo canale condiviso.

Vi sono due versioni di ALOHA, aloha puro e lo slotted aloha.

Il sistema ALOHA PURO si basa sostanzialmente sul fatto che i frame sono trasmessi in momenti totalmente arbitrari. I frame devono avere la stessa identica dimensione per massimizzare le prestazioni, e ogni volta che due frame cercano di occupare contemporaneamente il canale, si verifica una collisione che danneggia entrambi i frame. Non importa se i frame sono sovrapposti anche di un solo bit, entrambi vengono inesorabilmente danneggiati e scartati. In questo particolare caso il checksum di fatto non deve fare distinzione tra una perdita parziale o totale dei dati. Se c’è stata una collisione, quei frame devono essere rispediti totalmente.

Le probabilità che due frame abbiano una collisione sono discretamente alte, e se tutti trasmettono a piacimento è difficile aspettarsi una percentuale di successo del cento per cento.

Slotted ALOHA

Roberts intorno al 1972 pubblicò un interessante metodo per raddoppiare la capacità di un sistema ALOHA.

In questa versione il tempo viene diviso in intervalli discreti, e ogni intervallo corrisponde esattamente ad un frame. Questo metodo, conosciuto come slotted ALOHA, ha una differenza sostanziale rispetto al metodo di Abramson: un computer non può inviare dati ogni volta che viene premuto il tasto vi avanzamento riga. Quando l’utente preme invio il computer deve attendere il prossimo intervallo (slot) successivo. Questo metodo, secondo alcuni dati probabilistici, ha una capacità doppia rispetto all’ALOHA puro. Alcuni dati alla mano (A. Tanenbaum, Reti di Calcolatori I), prevede che il 37% degli intervalli sarà vuoto, il 37% delle trasmissioni senza errore e il 26% di collisioni.

In delle stazioni che trasmettono a piacimento senza verificare le azioni che compiono le altre, è facile imbattersi in un numero elevato di collisioni. Nelle reti locali è però possibile verificare le azioni intraprese dalle stazioni vicine, e di seguito elenco alcuni protocolli che consentono di migliorare le prestazioni rispetto ai sistema ALOHA, ormai in disuso.

I protocolli che rimangono in ascolto di una portante (una trasmissione) sono chiamati protocolli con rilevamento della portante.

CSMA (Carrier Sense Multiple Access) 1-persistente

Questo primo protocollo, quando si hanno dei dati da trasmettere, prima di tutto ascolta il canale per scoprire se qualcun altro in quel momento sta trasmettendo. Se il canale risulta occupato, la stazione aspetta fino a quando non si è liberato.

Quando diventa libero, trasmette un frame ed in caso di collisione, la sazione rimane in attesa per un intevallo casuale prima di ritentare la connessione.

Il nome di questo protocollo, ovvero “1-persistente” deriva dal fatto che la stazione trasmette con una probabilità di 1 quando trova il canale libero. Le collisioni sono sempre presenti, poiché vi è una piccola possibilità che subito dopo l’inizio di una trasmissione da parte di una stazione, un’altra stazione sia pronta a inviare dati e controlli il canale. Ma se il segnale della prima non ha ancora raggiunto la seconda, entrambe ritengono il canale libero, iniziano a trasmettere i propri dati e collidono.

CSMA non persistente

Prima di trasmettere ogni stazione controlla il canale: se nessuno sta trasmettendo inizia ad inviare i dati, ma se il canale è occupato la stazione non esegue un controllo continuo per trasmettere subito il proprio frame; ma attende per un intervallo di tempo casuale prima di ritentare. Questo metodo usa in modo più equilibrato il canale, ma allunga i ritardi.

CSMA p-persistente

Questo è l’ultimo protocollo e si applica ai canali divisi in intervalli di tempo. Il funzionamento è semplice, quando una stazione è pronta a trasmettere, ogni altra stazione controlla il canale. Se è libero trasmette subito con una probabilità p (da qui il nome), e rimanda fino all’intervallo successivo con probabilità q=1 – p. Se quell’intervallo è libero, la stazione trasmette oppure rimanda un’altra volta. Il processo (ovviamente) si ripete fino a quando quel frame non è stato trasmesso o un’altra stazione non inizia a trasmettere. Se inizialmente rileva che il canale è occupato, la stazione attende fino all’intervallo successivo e ritenta nuovamente questo algoritmo.

CSMA/CD (CSMA con Collision Detection)

E’ possibile fare un ulteriore passo avanti se si consente ad ogni stazione di annullare la propria trasmissione qualora ci fosse una collisione. Se due stazioni rilevano che il canale è libero in contemporanea, e iniziano a trasmettere, possono rivelare che vi è stata una collisione praticamente nell’immediato. Si risparmia del tempo facendogli annullare (appena rilevano la collisione) immediatamente la trasmissione. In questo modo si risparmia molta banda e anche del tempo.

Questo tipo di protocollo è molto utilizzato nel sottostrato MAC delle LAN e costituisce la base delle famose LAN Ethernet.

Il modello CSMA/CD è composto da periodi di contesa alternati a periodi di trasmissione, con dei periodi che sono inattivi e che si presentano soltanto quando tutte le stazioni sono “spente” per mancanza di lavoro.

Sostanzialmente questo algoritmo può trovarsi in tre stati, quello di contesa, quello di trasmissione e quello di inattività.

Protocolli esenti da collisioni

Andiamo ora ad analizzare alcuni protocolli che non soffrono del problema delle collisioni. Anzitutto si ipotizza di avere N stazioni, ognuna con un proprio indirizzo univoco che va da 0 a N-1. Questi algoritmi sono basati sempre sugli intervalli di contesa discreti spiegati prima.

Protocollo a mappa di bit

Il primo protocollo senza collisione si chiama “protocollo a mappa di bit elementare”, ed ogni periodo di contesa è composto esattamente da N intervalli. Se la stazione numero zero ha un frame da inviare, trasmette esattamente un bit 1 durante l’intervallo 0. In questo modo a nessun’ altra stazione è concesso di trasmettere durante l’intervallo zero. Senza preoccuparsi di quello che fanno le altre stazioni precedenti, la stazione uno potrà a sua volta trasmettere un bit 1 durante l’intervallo 1, ma solo se ha un frame accodato.

Una volta che sono trascorsi tutti gli N intervalli, ogni stazione sa quali sono le stazioni che vogliono trasmettere e a questo punto le stazioni iniziano a trasmettere in ordine numerico.

Proprio per il fatto che tutti sanno chi sarà il prossimo a trasmettere non ci sarà mai una collisione. Una volta finito il “ciclo”, si ricomincia con un altro periodo di contesa di N bit.

Conteggio Binario

Un problema del protocollo a mappa di bit elementare è che serve un bit di controllo per ogni stazione, perciò non si adatta molto bene alle reti composte da migliaia di stazioni. Un risultato migliore si può ottenere usando indirizzi binari. Una stazione che desidera utilizzare il canale deve comunicare a tutti il proprio indirizzo sotto forma di stringa binaria, partendo dal bit di ordine più elevato. I bit che occupano la stessa posizione negli indirizzi delle stazioni diverse vengono elaborati mediante un OR logico.

Per evitare i conflitti si usa una regola che dice che la stazione deve rinunciare non appena si accorge che è stata sovrascritta da un 1 una posizione di bit in ordine elevato che nel proprio indirizzo vale 0.

Protocolli a contesa limitata

Solitamente nelle situazioni dove c’è del carico leggero la contesa (per esempio nell’ALOHA puro o in quello a intervalli) viene preferito per il basso ritardo. Una volta che il carico cresce, tutto diventa alquanto inefficiente perché la quantità di dati necessari all’arbitraggio del canale aumenta. Nei protocolli senza collisioni si verifica invece che quando si ha un basso carico si ha un ritardo elevato, ma al crescere del carico l’efficienza del canale migliora notevolmente.

Allora perché non prendere un po’ dall’uno e un po’ dall’altro?

I protocolli a contesa limitata sono quello che fanno al caso nostro, e terminano lo studio delle reti con controllo di portante.

Protocollo Adaptive Tree Walk

In questo particolare protocollo le stazioni vengono immaginate come foglie di una struttura ad albero binaria. Nel primo intervallo di contesa che segue una trasmissione senza collisioni, l’intervallo 0, tutte le stazioni possono tentare di acquisire il controllo del canale. Se almeno una ci riesce bene, altrimenti nel caso di una collisione, durante l’intervallo 1 possono competere solo quelle stazioni che si trovano sotto il nodo 2 della struttura ad albero. Se una di queste acquisisce il controllo del canale, l’intervallo successivo è riservato alle stazioni che si trovano sotto il nodo 3.

In breve, in caso di collisione durante l‘intervallo 0 l’algoritmo analizza l’intera struttura ad albero partendo dal basso per individuare tutte le stazioni che sono pronte. Ogni intervallo di bit viene associato a qualche nodo dell’albero. Nel caso si verificasse una qualche collisione, la ricerca continua in modo ricorsivo con gli elementi figli posti a sinistra e a destra di quel nodo.

Protocollo WDMA (suddivisione di lunghezze d’onda)

Per consentire trasmissioni multiple contemporaneamente lo spettro è diviso in canali (bande di lunghezza d’onda).

In questo protocollo chiamato WDMA (wavelenght division multiple access) a ogni stazione sono assegnati due canali, uno stretto è utilizzato come canale per il controllo per trasmettere segnali alla stazione e poi un canale più largo che consente alla stazione di trasmettere frame di dati.

Ogni canale è diviso in gruppi di intervalli temporanei detti slot. Su entrambi i canali la sequenza di intervalli si ripete senza fine con l’intervallo 0 contrassegnato in modo speciale per aiutare i ritardatari a rilevarlo. Tutti i canali sono ovviamente sincronizzati da un singolo segnale di clock generale.

In breve, ogni stazione rimane in ascolto sul proprio canale di controllo per rilevare le richieste in arrivo, ma deve sintonizzarsi sulla lunghezza d’onda del trasmettitore per ricevere i dati.

Fin ora ho parlato dei protocolli e di come vengono utilizzati per cercare di distribuire il canale tra le varie stazioni. Ora introduco in che modo questi algoritmi si applicano ai sistemi reali ed in particolare alle reti LAN.

IEEE ha standardizzato diverse reti locali e reti metropolitane sotto il nome standard di IEEE 802.2. Tra i tanti standard scomparsi oggi troviamo 802.3 (l’ethernet) e 802.11 (Lan Wireless). Ovviamente ci sarebbe da parte anche di 802.15 (bluetooth) e 802.16 (MAN wireless) ma non lo farò qui.

Ethernet

Il nome deriva sostanzialmente dal cavo fisico, che sta per “etere”. Vi sono quattro tipi di cavi (generalizziamo): il 10Base5 (obsoleto), il 10Base2 (non occore un hub), 10Base-T (quello che di solito utilizziamo nelle nostre case), 10Base-F (Fibra ottica).

I problemi associati alla ricerca di guasti in un cavo (cosa che risulta/risultava abbastanza difficile) ha portato ad un differente schema di cablaggio che viene chiamato hub. Lo schema è chiamato 10Base-T, e gli hub non elaborano il traffico (al contrario degli switch che altro non è che una versione più elaborata dell’hub stesso).

Lo svantaggio del 10Base-T è che i cavi che partono dall’hub possono avere una lunghezza massima di 100metri, salvo nei casi in cui il cavo è di alta qualità (cat 5), in questi casi si possono raggiungere anche i 200 metri.

Ogni versione di ethernet ha una lunghezza massima per segmento. Se si ha la necessità di creare reti più grandi di quelle consentite dalla lunghezza di un singolo cavo bisogna prendere più cavi e dei ripetitori. Il ripetitore non fa altro che ricevere (lavora sullo strato fisico), amplificare (rigenerare il segnale) e ritrasmetterlo. Con i ripetitori ovviamente il ritardo aumenta.

Codifica Manchester

Velocità di clock diverse possono mandare il ricevitore e il trasmettitore fuori sincronia facendo perdere l’informazione dal punto in cui iniziano i bit, specialmente dopo una lunga serie di 0 oppure di 1 consecutivi.

Il sistema che si usa per consentire ai ricevitori di determinare senza confusione qual’è il punto iniziale, quello finale e il punto centrale di ogni bit si adottano due tecniche chiamate codifica Manchester e codifica Manchester differenziale. Con la prima tecnica ogni periodo di bit è diviso in due intervalli uguali, in modo da avere la certezza che ogni periodo di bit ha una transizione nel punto centrale, cosa che permette al ricevitore di sincronizzarsi col trasmettitore. Nella versione della codifica Manchester differenziale il bit 1 è indicato dall’assenza di una transizione all’inizio dell’intervallo mentre il bit 0 è indicato dalla presenza di una transizione all’inizio dell’intervallo. In entrambi i casi c’è una transizione nel punto centrale. Ovviamente questo schema richiede dispositivi più complessi.

Algoritmo di backoff esponenziale binario

Dopo un certo numero di collisioni (e quindi di errori) il chip di controllo comunica al computer un errore. L’algoritmo di backoff si adatta dinamicamente al numero di stazioni che tentano di trasmettere, e non fa altro che assicurare un basso ritardo quando poche stazioni collidono e garantisce la risoluzione della collisione in un intervallo di tempo ragionevole quando la collisione coinvolte molte stazioni.

Prestazioni dell’Ethernet 802.3

Sia P il tempo medio di trasmissione di un frame, si ha che l’efficienza è data da

P/(P+2t/A) dove A è la probabilità che una stazione acquisisca il canale.

Fast Ethernet

Per aumentare la velocità, differenti gruppo industriali proposero due nuove LAN ottiche basate su topologie ad anello. Una era la FDDI (Fiber Distributed Data Interface) e l’altra Fibre Channel. Entrambe furono utilizzare come reti dorsali, ma non arrivarono mai nei computer desktop salvo alcuni casi particolari. Quindi il comitato IEEE decise di mantenere lo standard 802.3 aumentandone la velocità. Il risultato fu la nascita dell‘802.3u, il cosiddetto fast ethernet. Si mantengono i vecchi formati dei frame, le interfacce e le regole procedurali, ma viene ridotto il tempo di trasferimnto dei bit da 100ns a 10ns.

Gigabit Ethernet

Lo sviluppo della fast ethernet era stato concluso da poco quando il comitato IEEE decise di mettersi al lavoro su di uno standard ancora più veloce, denominato gigabit ethernet. Il nome era 802.3z, e si è cercato di mantenere gli standard con le vecchie ethernet pur migliorando la velocità di 10 volte. Gigabit Ethernet supporta sostanzialmente due modalità operative, quella full duplex e half duplex. La prima modalità  permette al traffico di viaggiare contemporaneamente in entrambe le direzioni, e viene usata quando uno switch centrale è collegato ai computer o ad altri switch.

L’altra modalità operativa half duplex è utilizzata quando i computer sono collegati ad un hub e non ad uno switch. Qui la lunghezza massima del cavo diventa di soli 25 metri.

I nomi delle gigabit ethernet più diffuse sono 1000Base-SX (fibra multimodale), 1000Base-LX (fibra mono o multimodale), 1000Base-CX (doppino schermato), 1000Base-T (UTP standard di categoria 5, quelle che solitamente abbiamo nelle nostre case oggi giorno).

LAN Wireless (802.11)

Le LAN wireless sono sempre più popolari e un numero crescente di luoghi pubblici ne vengono equipaggiati. Questo tipo di lan si può configurare in due modi, con o senza stazione di base. Questo tipo di connessione si chiama anche 802.11.

Nei protocolli dell‘802.11 lo strato datalink è diviso in due parti: lo strato MAC che stabilisce il metodo di allocazione del canale, cioè chi deve trasmettere per primo. Al di sopra si trova lo stato “Logical Link Control”, che ha il compito di nascondere le differenze tra le varianti di 802 per renderle indistinguibili allo stato di rete.

Livello fisico dell‘802.11b

Il livello fisico ha alcune caratteristiche particolari, come ad esempio il fatto che la connessione arriva al massimo a 11Mbps, ha una frequenza di 2,4Ghz e ha un CDMA con un unico codice.

Livello fisico dell‘802.11a

Il livello fisico dell‘802.11a a differenza dell‘802.11b arriva a ben 54Mbps, lavora sulla frequenza dei 5Ghz ed è basata su OFDM, che utilizza molte frequenze (52 per la precisione) 48 dei quali per i dati (ecco perché è più veloce) e 4 per la sincronizzazione.

Livello fisico dell‘802.11g

Come l‘802.11a la velocità arriva a 54Mbps, lavora però sulla frequenza dei 2,5Ghz ed è basata su OFDM.

Livello fisico dell‘802.11n

Utilizza fino a 4 antenne per trasmettere fino a 4 flussi d’informazione contemporaneamente. Usa la tecnologia MIMO, che permette di avere dei miglioramenti notevoli nella trasmissione e nella distanza di trasmissione senza ricorrere a banda addizionale o a maggiore potenza, usa semplicemente una migliore efficienza spettrale (più bit al secondo per hertz di banda).

Protocollo del sottostrato MAC di 802.11

Il protocollo del sottostrato MAC di 802.11 è leggermente diverso da quello dell’ethernet. Poiché non tutte le stazioni sono all’interno del campo radio delle altre, le trasmissioni che avvengono in una parte della cella possono non essere ricevute in un’altra parte della stessa cella. Sostanzialmente i problemi sono due.

Problema della stazione nascosta: A vuole trasmettere dati a B ma non è in grado di scoprire se B è occupato.

Problema della stazione esposta: B vuole trasmettere dati a C ma erroneamente pensa che la trasmissione non avrà buon fine.

Per risolvere il problema si utilizza un protocollo chiamato CSMA/CA (diverso da CSMA/CD usato nelle ethernet), dove vengono controllati sia il canale fisico sia quello virtuale.

Rilevazione del canale virtuali in 802.11, affidabilità, risparmio energetico

Il NAV è un canale virtuale, più che altro un segnale NAV è un segnale non trasmesso che funge da semplice promemoria interno.

A differenza delle reti clablate le reti wirleess sono rumorose e inaffidabili, anche per colpa dei forni a microonde che utilizzano le stesse bande ISM senza licenze. Di sonseguenza, la probabilità che un frame arrivi a destinazione senza problemi diminuisce con la lunghezza del frame. Per risolvere il problema nei canali rumorosi 802.11 ammette la frammentazione dei frame in parti più piccole, ognuna dotata del proprio checksum di controllo, e ricevono l’acknowledgement individualmente con un protocollo stop-and-wait. La sequenza di frammenti è detta burst di frammenti.

La durata della batteria è sempre un problema con i dispositivi wireless, perciò 802.11 si preoccupa anche della gestione dell’energia. In particolare, la stazione base può obbligare una stazione mobile ad attivare la modalità di sospensione, il dispositivo rimarrà inattivo fino a quando non interviene l’utente o la stazione base.

Intervalli tra frame nell‘802.11

L‘802.11 prevede quattro intervalli di tempo, ognuno con una funzione specificas.

Il primo (SIFS) che è il più breve, serve per inviare un frame di controllo o il successivo frammento. Il secondo (PIFS) che è due volte SIFS, serve per inviare frame PCF. Il terzo che si chiama DIFS ed è tre volte SIFS serve per inviare frame DCF e l’ultimo (EIFS), che corrisponde a quattro volte l’intervallo di tempo di SIFS serve per eseguire il ripristino dei frame danneggiati.

Struttura del frame di 802.11

Nelle reti cablate lo standard 802.11 definisce tre diverse classi di frame: dati, controllo e gestione. Ognuna ha un’intestazione composta da campi utilizzati nel sottostrato MAC.

Servizi 802.11

Lo standard 802.11 definisce nove servizi che ogni lan wireless conforme deve fornire. Si dividono in due categorie: cinque servizi di distribuzione e quattro servizi stazione.

I più importanti sono:

Associazione e riassociazione – è utilizzato dalle stazioni mobili per effettuare la connessione alle stazioni base.

Autenticazione: Poiché la comunicazione wireless può facilmente essere iviata o ricevuta da stazioni non autorizzate, solo le stazioni che si autenticano ricevono l’autorizzazione a trasmettere dati.

Distribuzione: Stabilisce come saranno instradati i frame verso la stazione base.

Bibliografia: