Reti ALOHA e Accesso Multiplo

Reti (Computer Networks) - Capitolo 6: Livello Data Link

• Il livello data link si occupa del rilevamento e della correzione degli errori
• Utilizza il controllo ciclico di ridondanza (CRC) per il rilevamento di errori
• Implementa protocolli e tecnologie per l'accesso multiplo al canale, come TDMA, FDMA, CDMA, Slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA
• Il livello data link comprende anche la tecnologia Ethernet e lo standard IEEE 802
• Si occupa dei protocolli ed implementazioni per le reti locali
• Gestione della condivisione del canale di comunicazione

Sommario

• Il livello data link comprende il rilevamento e la correzione degli errori (CRC)
• Presenta protocolli moderni per l'accesso multiplo al canale, come TDMA, FDMA, e CDMA
• Include protocolli più vecchi come Slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA
• E' necessario per l'implementazione di Ethernet e lo standard IEEE 802
• Ethernet switching e Backward Learning sono parte del livello data link

Livello data link: obiettivi

• Comprendere i principi base di alcuni servizi di livello data link
• Rilevamento e correzione di errori
• Condivisione di un canale di tipo broadcast e accesso multiplo
• Indirizzamento di livello data link
• Implementazione di tecnologie di livello data link, come Ethernet nelle reti locali

Livello data link: introduzione

• Terminologia:
  • Host e router: nodi di rete
  • Canale: collega due nodi adiacenti
  • Collegamenti/link: cablati o wireless
  • LAN: Local Area Network
  • Pacchetto di livello 2: frame (incapsula un datagramma di livello 3)
  • Funzione: trasportare un frame da un nodo all'altro

Livello data link: contesto

• Un percorso link può contenere link di diversi tipi
• Un datagramma attraversa reti con differenti protocolli di livello 2
• Ethernet, Frame Relay e 802.11 sono esempi di protocolli di livello 2
• I protocolli offrono servizi diversi (es. controllo degli errori)

Servizi di livello data link

• Creazione di un frame di livello 2, con header e trailer
• Incapsulazione di un datagramma in un frame
• Accesso al canale di comunicazione condiviso
• Indirizzamento dei frame tramite indirizzi MAC (diverso dall'indirizzo IP)
• Consegna affidabile tra nodi adiacenti
• Controlla il flusso di dati
• Rilevamento e correzione degli errori: adatta la trasmissione ai requisiti del ricevitore

Servizi di livello data link (Continuazione)

• Controllo di flusso: adatta la velocità di trasmissione
• Rilevamento di errori: errori dovuti ad attenuazione e rumore del segnale
• Correzione di errori: identifica e corregge gli errori sui bit senza richiedere ritrasmissioni
• Half-duplex e full-duplex: modalità di trasmissione dati

Chi implementa il livello data link?

• Normalmente implementato come firmware di un adattatore di rete (NIC)
• Spesso su un chip (es. scheda Ethernet)
• Funzioni sia del livello data link che del livello fisico
• Collegato al bus di sistema dell'host (CPU, memoria, etc.)
• Combinazione di hardware, software e firmware

Comunicazione tra adattatori di rete

• Il mittente incapsula il datagramma in un frame e aggiunge dati di controllo
• Il ricevente verifica eventuali errori e passa il datagramma ai livelli superiori

Rilevamento di errori

• EDC: bit ridondanti per la rilevazione e correzione errori
• D: dati protetti dall'EDC (campi dell'header)
• Rilevamento non 100% affidabile: il protocollo potrebbe non accorgersi di errori minori o su dati ridondanti
• Maggiore ridondanza in genere aumenta la protezione

Controllo di parità

• Rileva errori singoli (solo parità pari/dispari dei bit)
• Esempio: Even Parity
• Il numero totale di 1 nei dati deve essere pari

Correzione di errori tramite ridondanza

• Interleaving: riordino dei bit per migliorare la protezione contro errori a raffica
• Ridondanza: informazioni aggiuntive per la correzione di eventuali alterazioni nei messaggi
• Esempi: HHH, EEE, LLL, LLO, HEL, LOH, ELL, etc.

Cyclic Redundancy Check (CRC)

• Algoritmo efficiente per il rilevamento di errori
• I bit dei dati vengono trattati come un numero binario
• Si sceglie una sequenza di bit "generatore"
• Il CRC (R) viene calcolato in modo che la concatenazione (D,R) sia divisibile per G (modulo 2) senza resto

Protocolli per il controllo dell'accesso multiplo

• Canale broadcast condiviso: due o più nodi possono trasmettere contemporaneamente
• Interferenza e collisione: quando più segnali arrivano nello stesso momento
• Protokolli di accesso multiplo algorìtmi distribuiti che gestiscono la condivisione del canale, determinando quando ciascun nodo può trasmettere
• Metodo di accesso multiplo al canale senza coordinazione

Un protocollo MAC ideale

• Il MAC ideale supporterebbe trasmissione a velocità costante di un singolo nodo, anche in condizioni multiple di trasmissioni provenienti da più nodi
• La decentralizzazione è preferibile e il sistema non dovrebbe aver bisogno di un clock centrale
• Semplicità nella implementazione

Protocolli MAC (Classificazione)

• Ripartizione risorse canale: canale diviso in sotto-canali (es. tempo, frequenza)
• Accessi casuali: gestione collisioni (es. ALOHA, CSMA)
• Turni intelligenti: accesso a turno, con priorità e gestione delle collisioni (es. polling, token passing)

Time Division Multiple Access (TDMA)

• Accesso al canale in "round" o "slot"
• Ogni nodo usa uno slot di durata fissa in ogni round

Frequency Division Multiple Access (FDMA)

• Lo spettro del canale viene suddiviso in "sotto-bande"
• Ad ogni stazione viene assegnata una sotto-banda

Code Division Multiple Access (CDMA)

• La ripartizione delle risorse avviene assegnando un codice diverso ad ogni nodo
• Ogni codice è costituito da una sequenza di "chip" (bit)
• I bit sono trasmessi molto più rapidamente dei bit del messaggio

Tipi di collegamento

• Collegamenti punto-punto (PPP per accesso dial-up tra una rete e un dispositivo)
• Collegamenti broadcast (es. vecchie versioni Ethernet, HFC, WLAN)

CSMA

• Carrier Sense Multiple Access (CSMA): ogni nodo ascolta il canale prima di trasmettere per evitare collisioni

CSMA con persistenza

• CSMA (non persistente/1-persistente/p-persistente) modi differenti di gestire le collisioni

CSMA/CD

• Collision Detection (CSMA/CD): i nodi rilevano le collisioni e le interrompono per evitare sprechi di risorse

CSMA/CA

• Collision Avoidance (CSMA/CA): i nodi cercano di evitare le collisioni anticipando possibili interferenze

Topologia Ethernet (bus & stelle)

• Topologia a bus: un singolo cavo con tutti i nodi connessi
• Topologia a stella: un dispositivo centrale (hub o switch) collega tutti i nodi

Ethernet-Switch

• Hub: ripetitori di livello 1
• Switch: dispositivi di livello 2 (data link) più attivi, memorizzano e inoltra i frame in base agli indirizzi MAC, gestiscono collisioni
• Funzionalità: trasparenza, plug-and-play, autoapprendimento

Tabella di inoltro (Switch)

• La tabella di inoltro indica l'interfaccia per raggiungere un indirizzo MAC
• Autoapprendimento, aggiornamento, cancellazione righe
• Algoritmi: filtraggio e inoltro frame tramite la tabella

Switch: Autoapprendimento (Backward Learning)

• Lo switch impara quali host possono essere raggiunti attraverso ogni interfaccia
• Alla ricezione di ogni frame, lo switch memorizza la porta di origine dell'host e il suo indirizzo MAC.
• Questo algoritmo è fondamentale per l'inoltro di frame.

Switch: Filtraggio e inoltro

• Se lo switch vede che la destinazione di un frame è su un'altra porta, li inoltra
• Se la destinazione è sulla stessa porta, non inoltra il frame

Algoritmo CSMA/CD in Ethernet

• Metodo per gestire l'accesso al mezzo di trasmissione Ethernet
• Ripetizioni a ritardo casuale per evitare collisioni
• Ritrasmissioni in caso di collisioni

Standard Ethernet 802.3

• Numerosi standard differenti
• Variazioni nelle velocità di trasmissione (2Mbit/s, 10Mbit/s, etc.)
• Utilizzo di diversi mezzi fisici (fibre ottiche, cavo a doppini)

Evoluzione di Ethernet

• Ethernet ha subito molte evoluzioni nella velocità e la capacità di collegamento
• Caratteristiche: tecnologie come Fast Ethernet, Gigabit Ethernet e 40/100 Gigabit Ethernet

Ethernet: connessione? ACK/NACK?

• Ethernet è una tecnologia connectionless senza controllo di flusso attraverso ACK/NACK
• Si basa su CRC per il rilevamento di errori, ma la consegna non è garantita. La correzione degli errori è gestita da protocolli a livello superiore (es., TCP)

Altro esempio (Switch multipli)

• Gli switch apprendono e gestiscono l'inoltro attraverso più switch senza perdita di dati durante le comunicazioni.
• Il meccanismo di memorizzazione e inoltro è lo stesso sia con 1 che con più switch

Rete istituzionale

• Rete tipica con un router per le connessioni esterne
• Server mail e web sono disponibili
• I server sono connessi a interfacce di rete per le connessioni ai computer.
• Il router si collega direttamente alle reti più esterne.

Questo quiz esplora vari aspetti delle reti ALOHA, inclusi throughput, collisioni e tecnologie di accesso. Metterà alla prova la tua conoscenza delle differenze tra ALOHA puro e ALOHA slotted, oltre a questioni relative al livello data link e al rilevamento degli errori. Ideale per studenti di informatica e ingegneria delle reti.