Reti di Computer: ALOHA e Switch

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

• Il capitolo si concentra sul livello data link delle reti di computer.
• Il docente è Fabrizio Granelli, e l'anno accademico è 2024/2025.

Sommario

• Livello data link: Rilevamento e correzione di errori (CRC), Protocolli e tecnologie per l'accesso multiplo al canale (TDMA, FDMA, CDMA, Slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA), IEEE 802 ed Ethernet.
• Ethernet switching: Backward learning.

Livello Data Link: Obiettivi

• Comprendere i principi di 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.
• Local area networks: Ethernet.
• Implementazione di alcune tecnologie di livello data link.

Livello Data Link: Introduzione

• Terminologia: Host e router (nodi di rete), Canali di comunicazione (link cablati e wireless), Pacchetto di livello 2 (frame), incapsula un datagramma (livello 3), Trasporta un frame da un nodo a un altro nodo fisicamente adiacente.

Livello Data Link: Contesto

• Analogia con sistemi di trasporto (viaggio esempio Princeton - Losanna).
• Il percorso può contenere link di diversi tipi
• Un datagramma attraversati vari livelli con protocolli differenti
• Ogni protocollo fornisce servizi diversi (e.g., controllo di errore).

Servizi di livello Data Link

• Creazione di un frame di livello 2, accesso al link.
• Incapsula un datagramma in un frame, aggiunge header e trailer.
• Fornisce un meccanismo di accesso al canale.
• Utilizza indirizzi di livello 2 (MAC) per identificare mittente e destinatario.
• Diverso dall'indirizzo IP.
• Consegna affidabile tra nodi adiacenti. (meno usato in caso di basso tasso di errore)
• Link wireless: alti tassi di errore.
• Perché inserire controllo di errore a livello 2 e 4?

Servizi di Livello Data Link (continua)

• Controllo di flusso: Adattare la velocità di trasmissione alle capacità di mittente e ricevente.
• Rilevamento di errore: Errori dovuti ad attenuazione eccessiva del segnale, rumore, ecc. Il ricevitore può rilevare la presenza di errori e informare il mittente di scartare il pacchetto.
• Correzione di errore: Il ricevitore identifica e corregge gli errori sui bit senza richiedere ritrasmissioni.
• Half-duplex e full-duplex: In full-duplex i nodi possono trasmettere e ricevere contemporaneamente.

Chi implementa il livello data link?

• Implementato in tutti gli host come firmware (es. schede di rete Ethernet o 802.11),
• Combinando hardware, software e firmware collegato al bus di sistema dell'host.

Comunicazione tra adattatori di rete

• Mittente: Incapsula un datagramma in un frame e aggiunge informazioni per il controllo di errore e di flusso.
• Ricevente: Cerca eventuali errori, collabora al controllo del flusso e estrae il datagramma per i livelli superiori.

Rilevamento di errori

• EDC = Bit ridondanti inseriti per la rilevazione e correzione degli errori
• D = Dati protetti dall'EDC (campi dell'header)
• Rilevamento di errore non affidabile al 100%.
• Maggiore ridondanza, maggiore protezione del datagramma

Controllo di parità

• Singolo bit di parità: Rileva errori singoli (es. "even parity").
• Parità su due dimensioni: Rileva e corregge singoli errori sui bit (es. "even parity").

Correzione di errori tramite ridondanza

• CCFooommmree vvveeeddheeetxteee, ecc.
• Un'operazione di interleaving (riordino dei bit) fornisce una protezione contro errori a "raffica" (burst).
• Esempi di utilizzo di ridondanza e interleaving

Cyclic Redundancy Check (CRC)

• Algoritmo efficiente per il rilevamento degli errori.
• Considera i bit di dati come un numero binario.
• Sceglie una sequenza di bit (generatore).
• Obiettivo: comporre il CRC (R) in modo che i dati D siano divisibili per G (con resto R).
• Il ricevitore conosce G: se divide <D,R> per G e il resto è diverso da 0, rileva l'errore.

Tipi di collegamento

• Punto-punto (PPP, collegamento tra una switch Ethernet e un host).
• Broadcast (mezzo di trasmissione condiviso: versioni di Ethernet, HFC, wireless 802.11).

Protocolli per l'accesso multiplo

• Canale broadcast condiviso: Due o più trasmissioni contemporanee creano interferenza e collisioni.
• Protocollo di accesso multiplo (algoritmo distribuito): determina come i nodi condividono il canale e quando possono trasmettere.

Un protocollo MAC ideale

• MAC: multiple access control
• Data: un canale broadcast capace di gestire comunicazioni a R bit/s
• Caratteristiche desiderate per il protocollo: quando un singolo nodo trasmette, può farlo a velocità R; quando più nodi vogliono trasmettere, possono farlo con un tasso medio pari a R/M; il sistema è decentralizzato e senza sincronizzazione di clock.

Protocolli MAC: Tassonomia

• Tre classi di protocolli MAC: divisone di risorse del canale (e.g., TDMA, FDMA, CDMA), accesso casuale (e.g., ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA) e protocolli "a turni" (e.g., polling, token passing).

Ripartizione delle risorse: TDMA, FDMA, CDMA

• Descrizioni dei meccanismi.
• Esempi e comparazioni
• Vengono descritti meccanismi specifici di accesso al mezzo di trasmissione

Protocolli ad accesso casuale

• Descrizioni di accesso casuale (con esempi quali ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA).
• Come rilevare e gestire le collisioni

Slotted ALOHA

• Assunzioni (pacchetti con la stessa lunghezza, tempo diviso in slot, sincronizzazione dei nodi).
• Come funziona il protocollo

Slotted ALOHA: Calcolo efficienza

• Formula per calcolo dell'efficienza (probabilità di successo di una trasmissione).

ALOHA puro (non slotted)

• Caratteristiche, funzionamento e confronto con Slotted ALOHA.

ALOHA puro: Efficienza

• Assunzioni e formula per calcolo dell´efficienza (probabilità di successo di una trasmissione).

Throughput: Confronto

• Grafico che confronta l'efficienza di diversi protocolli in funzione del carico.

Un po' di storia

• Inizio degli studi e della sperimentazione riguardanti le tecnologie wireless.

Standardizzazione di Ethernet: da DIX a 802.3

• Origine e standardizzazione dello standard Ethernet
• Descrizione delle tecnologie e tecnologie di comunicazione utilizzate (a cavo spesso e sottile)

Prima topologia Ethernet: il bus

• Descrizione del funzionamento in topologia a bus, con mezzi di trasmissione condivisi quali cavi coassiali thick e thin.

Transceiver Ethernet

• (10BASE5) e (10BASE2)
• Descrizione dei componenti hardware inclusi: transceiver, vampir taps, cavo trasmissore

Idea spartiacque (1990): gli hub

• Introduzione di hub (multi-port repeater) come strumento di collegamento multi-punto

... i doppini incrociati

• Introduzione dei cavi a doppini incrociati per miglioramento della gestione e semplicità di installazione

... e infine il connettore RJ45

• Specifiche del connettoreRJ45 e la connessione con cavo Ethernet

Struttura del frame Ethernet

• Descrizione dei campi del frame (preambolo, indirizzi di sorgente e destinazione, dati, CRC).
• Spiegazione del processo di incapsulamento

Struttura del frame Ethernet (continua)

• Indirizzi MAC
• Tipo (indica il protocollo di livello superiore)
• CRC (Cyclic Redundancy Check)

Ethernet: Connessione? ACK/NACK?

• Principi di connessione Ethernet come connessione senza connessione (connectionless) , e mancanza di affidabilità (non affidabile).
• Mancanza di controllo a livello di protocollo (es. TCP)

Algoritmo CSMA/CD in Ethernet

• Descrizione del funzionamento dell'algoritmo CSMA/CD in Ethernet: incapsulazione nel frame, identificazione del canale, trasmissione, gestione delle collisioni, backoff.

Standard Ethernet 802.3: livello fisico e data link

• Molti standard Ethernet differenti : Descrizione di diversi standard Ethernet , velocità di trasmissione, tecnologie utilizzate.

Evoluzione di Ethernet

• Descrizione dell'evoluzione delle velocità di trasmissione Ethernet.

Switch Ethernet

• Differenze tra hub e switch.
• Descrizione del funzionamento dello switch, inclusi filtraggio, inoltro e apprendimento.

Ethernet e domini di collisione

• Topologie a bus e a stella.
• Confronto tra domini di collisione utilizzando hub e switch.

Switch: Trasmissioni simultanee

• Funzionamento dei switch e gestione delle trasmissioni simultanee,
• Eliminazione delle collisioni

Tabella di inoltro degli switch

• Come viene mantenuta la tabella.
• Processo di autoapprendimento, aggiornamenti e cancellazione

Switch: Autoapprendimento

• Descrizione più approfondita dell'apprendimento backward dello switch.

Switch: Filtraggio e inoltro dei frame

• Illustrazione del processo decisionale dello switch per l'inoltro dei frame (filtraggio e inoltro).

Caso con switch multipli

• Funzionamento degli switch collegati in topologie complesse

Rete istituzionale (molto semplice)

• Schema di una rete istituzionale con router e switch,
• Server, subnet

Switch, router e hub

• Differenze tra switch, router e hub a livello di incapsulamento e inoltro dati
• Tabelle di inoltro (router, switch)