Reti (Computer Networks) - Capitolo 6 - Livello Data Link - 2024/2025 PDF

Reti (Computer Networks) Capitolo 6 Livello data link Docente: Fabrizio Granelli AA 2024/2025 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso mul...

Reti (Computer Networks) Capitolo 6 Livello data link Docente: Fabrizio Granelli AA 2024/2025 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning 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 4-2 Livello data link ❑ Obiettivi ❖ Comprendere i principi di base di alcuni servizi di livello data link Rilevamento e correzione di errore 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 6-3 Livello data link: introduzione Terminologia: ❑ Host e router: nodi (di rete) ❑ Canale di comunicazione che collega due nodi adiacenti lungo un certo percorso: collegamenti, o link ❖ Link cablati ❖ Link wireless ❖ LANs ❑ Pacchetto di livello 2: frame ❖ Incapsula un datagramma (liv 3) Il livello data link ha la funzione di trasportare un frame da un nodo a un’altro nodo fisicamente adiacente 6-4 Livello data link: contesto ❑ Un percorso può contenere Analogia con i sistemi di trasporto link di diversi tipi ❑ Viaggio Princeton – Losanna ❑ Un datagramma trasferito ❖ Limousine: Princeton – JFK lungo questo percorso ❖ Aereo: JFK – Ginevra attraversa quindi reti con ❖ Treno: Ginevra – Losanna protocolli di livello 2 differenti ❖ Ethernet sul primo link ❑ Turista = datagramma ❖ Frame relay sui link intermedi ❑ Porzione del viaggio = link ❖ 802.11 sull’ultimo link ❑ Modalità di viaggio = protocollo ❑ Ogni protocollo fornisce servizi di livello data link diversi ❑ (Agenzia di viaggio ❖ Es. controllo di errore o meno = algoritmo di routing) 6-5 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 se il mezzo di comunicazione è condiviso con altri dispositivi ❖ Utilizza indirizzi di livello 2 (detti indirizzi “MAC”) negli header dei frame per identificare mittente e destinatario Diverso dall’indirizzo IP! ❑ Consegna affidabile tra nodi adiacenti ❖ Sappiamo come ottenere questo servizio ❖ Poco usato su link a basso tasso di errore (es., fibre ottiche) ❖ Link wireless: alti tassi di errore D: perché inserire controllo di errore sia a livello 2 sia a livello 4? 6-6 Servizi di livello data link ❑ Controllo di flusso: ❖ Adatta la velocità di trasmissione alle possibilità di trasmettitore e ricevitore ❑ Rilevamento di errore: ❖ Errori causati da atenuazione eccessiva del segnale, rumore, … ❖ Il ricevitore può rilevare la presenza di errori E di conseguenza avvertire il mittente e/o scartare il pacchetto ❑ Correzione d’errore: ❖ Il ricevitore identifica e corregge gli errori sui bit senza richiedere ritrasmissioni ❑ Half-duplex e full-duplex ❖ In un collegamento full-duplex, i nodi possono trasmettere e ricevere contemporaneamente (in uno half-duplex, no) 6-7 Chi implementa il livello data link? ❑ Implementato in tutti gli host ❑ Di solito, come firmware di un “adattatore di rete” (detto anche “network interface applicazione card”, NIC) o su un chip trasporto rete CPU memoria ❖ Scheda Ethernet, scheda data link 802.11; chipset Ethernet ❖ Nota: implementa sia il Bus di sistema livello data link sia il livello controller (es., PCI) fisico data link fisico fisico ❑ Collegata direttamente al bus trasmissione di sistema dell’host Adattatore di rete ❑ Combinazione di hardware, software, firmware 6-8 Comunicazione tra adattatori di rete ❑ Mittente: ❑ Ricevente ❖ Incapsula un datagramma in ❖ Cerca eventuali errori, un frame collabora al controllo di ❖ Aggiunge bit ulteriori per flusso, ecc. controllo di errore, controllo ❖ Estrae il datagramma e lo di flusso, ecc. passa ai livelli superiori datagramma datagramma controller controller Mittente Ricevente datagramma Frame 6-9 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning 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 4-10 Rilevamento di errori ❑ EDC = Bit ridondanti inseriti per Error Detection and Correction ❑ D = Dati protetti dall’EDC (o anche campi dell’header) ❑ Il rilevamento di errore non è mai affidabile al 100%! ❖ Il protocollo potrebbe non accorgersi di qualche errore ❖ Maggiore è la ridondanza, maggiore è la protezione (in generale) datagramma datagramma Sì I bit No sono Rilevato errore OK? D EDC D' EDC' Link affetto da errori 6-11 Controllo di parità ❑ Singolo bit di parità: ❑ Parità su due dimensioni ❖ Rileva errori singoli ❖ Rileva e corregge singoli errori sui bit ❑ Esempio: “even parity” ❖ Il numero totale di 1 deve ❑ Esempio: even parity su due essere pari dimensioni ❖ Sinistra: nessun errore ❖ Destra: singolo errore rilevato e correggibile data bits parity bit 1 0 1 0 1 1 1 0 1 0 1 1 0111000110101011 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 6-12 Correzione di errori tramite ridondanza ❑ CCFooommmree vvveeeddheeetxteee, lllaab rrriijddqowonnndddajannmzzyaaa pppeegrrlmpmgeehtteee dddiii rrriiklbleewvvvaaaruruee eee ccoooorrreeggggteearreee aaalllcxcuzunnmiii eeerrjooprrqwii ❑ Un’operazione detta “interleaving” (che consiste nel riordino dei bit) fornisce anche una protezione contro errori a “raffica” (burst) ❖ Messaggio: HELLO ❖ Ridondanza: HHH EEE LLL LLL OOO ❖ Interleaving: HEL LOH ELL OHE LLO ❖ Raffica di errori: HEL LOH EXX XXX LLO ❖ De-interleaving: HHX EEX LXL LXL OXO ❖ Scelta a maggioranza: HELLO 6-13 Cyclic redundancy check (CRC) ❑ Algoritmo più efficiente per il rilevamento di errore ❑ Considera i bit di dati come un numero binario D ❑ Sceglie una sequenza di r+1 bit (detta “generatore”), e un numero G (noto sia al mittente sia al ricevente) ❑ Obiettivo: comporre il CRC (R) scegliendo r bit in modo che: ❖ I dati D siano esattamente divisibili per G (modulo 2) con resto R O in altre parole, che la concatenazione sia divisibile per G ❖ Il ricevente conosce G: se divide per G e resto ≠ 0 → errore! ❖ Può rilevare anche errori a raffica, se meno di r bit errati consecutivi ❑ Nota: per concatenare D ed R basta calcolare: ❖ = (D × 2r) XOR R D: bit dati da proteggere R: r bit del CRC 6-14 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning 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 4-15 Tipi di collegamento ❑ Punto-punto ❖ PPP per accesso dial-up ❖ Collegamento punto-punto tra uno switch Ethernet e un host ❑ Broadcast (mezzo di trasmissione condiviso) ❖ Vecchie versioni di Ethernet ❖ Hybrid fiber-coaxial (HFC) per TV e Internet ❖ 802.11 wireless LAN Cavo condiviso (es., Canale radio RF Canale radio RF Persone ad un party Vecchie versioni Ethernet) (es., 802.11 WiFi) (satellite) (mezzo aereo condiviso, segnali acoustici) 6-16 Protocolli per il controllo dell’accesso multiplo ❑ Canale broadcast condiviso ❑ Due o più trasmissioni simultanee partono da nodi diversi: si crea interferenza ❖ Se un nodo riceve due o più segnali nello stesso momento si verifica una collisione ❑ Protocollo di accesso multiplo ❖ Algoritmo distribuito che determina come i nodi condividano il canale, quando un nodo può trasmettere e quando no ❖ In un canale broadcast condiviso gli “accordi” di trasmissione vengono preso comunicando sullo stesso canale usato per i dati! Nella maggioranza dei casi non c’è un canale esterno dedicato al coordinamento (“out-of-band” channel) 6-17 Un protocollo MAC ideale ❑ MAC: multiple access control ❑ Dato: ❖ Un canale broadcast capace di supportare comunicazioni a R bit/s ❑ Vorremmo che: 1. Quando un nodo trasmette, possa farlo a velocità R 2. Quando M nodi vogliono trasmettere, possano farlo ad un tasso medio pari a R/M 3. Il sistema fosse completamente decentralizzato: Nessun “centro stella” che coordina le trasmissioni degli altri Nessuna sincronizzazione di clock 4. …e se possibile che fosse semplice 6-18 Protocolli MAC: tassonomia ❑ Tre classi: ❖ A ripartizione delle risorse di canale Dividono il canale in “sotto-canali” più piccolo (es. Slot temporali, sotto-frequenze, codici di spreading) Allocano ciascun sotto-canale a un nodo in modo esclusivo ❖ Ad accesso casuale Il canale non viene suddiviso, si accetta che si verifichino collisioni Si cerca comunque di minimizzarle ❖ A “turni” intelligenti I nodi accedono al canale a turno, ma i nodi con molti dati da trasmettere possono ottenere turni più lunghi 6-19 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso multiplo al canale ❖ TDMA, FDMA, CDMA ❖ Slotted ALOHA, ALOHA ❖ CSMA, CSMA/CD, CSMA/CA ❖ Protocolli “a turni” ❖ IEEE 802 ed Ethernet 4-20 Ripartizione delle risorse: TDMA TDMA: time division multiple access ❑ Accesso al canale in "round" ❑ Ogni nodo ottiene uno slot di durata fissa in ogni round ❖ Lunghezza = tempo di trasmissione di un pacchetto ❑ Gli slot inutilizzati rimangono liberi in ogni caso ❑ Esempio: LAN con 6 nodi, di cui il nodo 1, il nodo 3 e il nodo 4 hanno pacchetti da trasmettere, mentre gli slot 2, 5 e 6 rimangono vuoti ❑ I round si chiamano più tipicamente “frame” (sorry) Round Round di 6 slot di 6 slot 1 3 4 1 3 4 6-21 Ripartizione delle risorse: FDMA FDMA: frequency division multiple access ❑ Spettro del canale suddiviso in “sotto-bande” ❑ Ad ogni stazione si assegna una sotto-banda ❑ Quando una sotto-banda non viene usata per trasmettere, la risorsa rimane inutilizzata ❑ Esempio: LAN con 6 nodi, di cui il nodo 1, il nodo 3 e il nodo 4 hanno pacchetti da trasmettere, mentre le sotto-bande 2, 5 e 6 rimangono vuote Sotto-bande Cavo con FDMA 6-22 Ripartizione delle risorse: CDMA ❑ CDMA: code-division multiple access ❑ La ripartizione delle risorse avviene assegnando un “codice” diverso ad ogni nodo ❖ “Codice” = sequenza di “chip” che commuta più rapidamente di quanto commutino i bit ❑ Confronto con TDMA e FDMA 6-23 Ripartizione delle risorse: CDMA 𝑇𝑏𝑖𝑡 𝑇𝑐ℎ𝑖𝑝 ❑ Perché funziona? 1 0 Codice 1 1 Dati 0 1 Dati XOR Codice 1 0 Codice 1 Codice 1 XOR (Dati XOR Codice 1) Dati XOR Codice 1 Codice 2 (Dati XOR Codice 1) XOR Codice 2 6-24 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso multiplo al canale ❖ TDMA, FDMA, CDMA ❖ Slotted ALOHA, ALOHA ❖ CSMA, CSMA/CD, CSMA/CA ❖ Protocolli “a turni” ❖ IEEE 802 ed Ethernet 4-25 Protocolli ad accesso casuale ❑ Quando un nodo ha un pacchetto da trasmettere ❖ Può trasmettere al data rate massimo, R ❖ Non c’è coordinamento con gli altri nodi prima della trasmissione ❑ Se due o più nodi trasmettono contemporaneamente → collisione ❑ Un protocollo ad accesso casuale specifica: ❖ Come (e se) rilevare le collisioni ❖ Come (e se) recuperare uno stato di collisione (ad esempio, imponendo a ciascun nodo di riprovare dopo un ritardo casuale) ❑ Esempi di protocolli ad accesso casuale: ❖ Slotted ALOHA ❖ ALOHA ❖ CSMA, CSMA/CD, CSMA/CA 6-26 Slotted ALOHA Assunzioni Come funziona ❑ Tutti i pacchetti (frame) ❑ Quando un nodo ha qualcosa hanno la stessa lunghezza da inviare, lo invia nello slot ❑ Il tempo è suddiviso in slot, immediatamente successivo ciascuno lungo quanto un ❑ Se non ci sono collisioni: il pacchetto nodo può trasmettere ancora ❑ I nodi possono trasmettere nello slot seguente solo all’inizio di uno slot ❑ Se c’è una collisione: il nodo ❑ I nodi sono sincronizzati ritrasmette il pacchetto con probabilità p in ogni slot ❑ Se 2 o più nodi trasmettono, seguente finché non ha tutti vedono la collisione successo 6-27 Slotted ALOHA ❑ Vantaggi: ❑ Svantaggi: ❖ Se un solo nodo è attivo, può ❖ Le collisioni sono probabili e usare il canale continuamente sprecano risorse ❖ Decentralizzato: serve solo ❖ Gli slot potrebbero rimanere sincronizzarsi sullo slot vuoti ❖ Molto semplice ❖ Si potrebbe rilevare la collisione senza aspettare la fine di una trasmissione ❖ Sincronizzarsi richiede coordinamento nodo 1 nodo 2 nodo 3 C V C S V C V S S 6-28 Slotted ALOHA: calcolo efficienza ❑ Assunzioni ❖ Tutti i pacchetti hanno la stessa dimensione ❖ Chiamiamo G≥0 il traffico offerto (numero medio di pacchetti inviati sul canale da tutte le stazioni in uno slot, includendo trasmissioni e ritrasmissioni) ❖ La probabilità che ci siano k pacchetti da trasmettere in uno slot ha una distribuzione statistica di Poisson 𝐺 𝑘 𝑒 −𝐺 𝑃𝑘 = 𝑘! ❑ Throughput ideale = 1 (D: perche?) ❑ Throughput effettivamente ottenuto: 𝑃 𝑘 = 1 = 𝐺𝑒 −𝐺 ❑ Quale valore di G massimizza il throughput? 𝑑𝐺𝑒−𝐺 ❖ Risolviamo 𝑑𝐺 = 0 ottenendo 𝐺 ∗ = 1 1 ❖ Sostituiamo e otteniamo un throughput massimo pari a 𝑒 ≈ 0.368 6-29 ALOHA puro (non slotted) ❑ Aloha: ancora più semplice, nessuna sincronizzazione ❑ Quando un frame arriva, viene trasmesso subito ❑ La probabilità di collisione aumenta: ❖ Un frame inviato a t0 collide con altri frame inviati in [t0-1, t0+1] Sovrapposto Sovrapposto all’inizio del frame alla fine del frame del nodo 2 del nodo 2 node 1 node 2 node 2 frame node 3 t0 - 1 t0 t0 + 1 6-30 ALOHA puro: efficienza ❑ Assunzioni ❖ Tutti i pacchetti hanno la stessa dimensione, infiniti host ❖ Chiamiamo G≥0 il traffico offerto (numero medio di pacchetti inviati sul canale da tutte le stazioni in uno slot, includendo trasmissioni e ritrasmissioni) ❖ La probabilità che ci siano k pacchetti da trasmettere in uno slot ha una distribuzione statistica di Poisson 𝐺𝑘 𝑒 −𝐺 𝑃𝑘 = 𝑘! : ❑ Throughput: probabilità che un solo frame venga trasmesso durante il periodo di vulnerabilità [t0-1, t0+1] 6-31 ALOHA puro: efficienza ❑ Probabilità che un solo frame venga trasmesso al tempo t: ❖ 𝑃 𝑘 = 1 = 𝐺𝑒 −𝐺 ❑ Probabilità che non ci siano frame la cui trasmissione inizia nell’intervallo [t0-1, t0] ❖ 𝑃 𝑘 = 0 = 𝑒 −𝐺 ❑ Throughput: probabilità che una trasmissione abbia successo: ❖ 𝑃 𝑘 = 1 × 𝑃 𝑘 = 0 = 𝐺𝑒 −2𝐺 ❑ Throughput massimo: 𝑑𝐺𝑒 −2𝐺 1 ❖ Risolviamo = 0 ottenendo G = 𝑑𝐺 2 1 ❖ Sostituendo, otteniamo un throughput massimo pari a ≈ 0.184 2𝑒 ❖ Metà di quello dello slotted ALOHA → D: perché? 6-32 Throughput: confronto 6-33 Un po’ di storia ❑ Verso la fine del 1960: ALOHA network (Norman Abramson) ❖ Primo sistema radio a commutazione di pacchetto (Hawaii) ❖ Primo sistema di accesso distribuito al mezzo radio 34 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso multiplo al canale ❖ TDMA, FDMA, CDMA ❖ Slotted ALOHA, ALOHA ❖ CSMA, CSMA/CD, CSMA/CA ❖ Protocolli “a turni” ❖ IEEE 802 ed Ethernet 4-35 Carrier sense multiple access (CSMA) ❑ CSMA: carrier sense multiple access ❖ “Carrier” (cioè “portante”) è un termine che si riferisce al segnale che trasporta l’informazione ❑ In termini umani: ascolta prima di parlare ❖ Se il canale viene valutato vuoto: si trasmette un intero frame ❖ Se il canale viene valutato occupato: si ritarda la trasmissione 6-36 Versioni di CSMA: persistenza ❑ Non-persistente (0-persistente): ❖ Quando un nodo è pronto a mandare un frame Se il canale è vuoto: → trasmette Se il canale è occupato → attende un tempo casuale e molto più lungo del tempo di trasmissione, esaurito il quale ritenta ❑ 1-persistente ❖ Quando un nodo è pronto a mandare un frame Se il canale è vuoto: → trasmette Se il canale è occupato: Attende finché non si libera Dopodiché trasmette subito ❑ Se si verifica una collisione, il nodo attende un tempo casuale, poi ritenta seguendo la stessa procedura 6-37 CSMA p-persistente ❑ Quando un nodo è pronto a mandare un frame ❖ Se il canale è vuoto: → trasmette ❖ Se il canale è occupato: Attende finché non si libera Dopodiché Con probabilità p → trasmette il frame Con probabilità 1 – p → attende un tempo casuale e molto più lungo del tempo di trasmissione, poi ritenta ❑ Se si verifica una collisione, il nodo attende un tempo casuale, poi ritenta seguendo la stessa procedura ❑ Nota: se avete il libro di Tanenbaum, troverete le regole un po’ diverse ❖ Tanenbaum segue l’articolo originale di Tobagi e Kleinrock , che è un po’ ambiguo sulle regole L. Kleinrock and F. A. Tobagi, "Packet Switching in Radio Channels: Part I-Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics", in IEEE Transactions on Communications, vol. COM-23, no. 12, December 1975 6-38 Throughput di CSMA: confronto Source: "Computer Networks" book by Tanenbaum 6-39 CSMA: periodo di vulnerabilità ❑ Il periodo di vulnerabilità dipende dal tempo di propagazione 𝜏 e dal tempo richiesto per rilevare se il canale è occupato, 𝑇𝑎 ❖ Se un nodo trasmette ma il segnale non ha raggiunto tutti gli altri nodi, un altro nodo potrebbe iniziare a trasmettere ❖ Periodo di vulnerabilità: 𝑇𝑣 = 𝜏 + 𝑇𝑎 ❑ In generale, CSMA si usa quando 𝜏 ≪ 𝑇 (tempo di trasmissione) Ta tempo nodo A tempo nodo B 𝜏 𝜏 6-40 CSMA: collisioni Disposizione dei nodi ❑ Anche con il CSMA ci possono essere collisioni: esiste un ritardo di propagazione, quindi due nodi potrebbero non rilevare in tempo i rispettivi segnali ❑ Collisione: spreca l’intero tempo di trasmissione ❖ La distanza (e quindi il tempo di propagazione) giocano il ruolo più importante nel determinare la probabilità di collisione 6-41 CSMA/CD (collision detection) ❑ CSMA/CD: usa comunque il carrier sensing, e se il canale è occupato posticipa le trasmissioni come nel normale CSMA ❑ In aggiunta ❖ Permette di rilevare le collisioni entro breve ❖ Permette di interrompere le trasmissioni e ridurre lo spreco di risorse di comunicazione (uso canale, energia) ❑ Collision detection: ❖ Facile nelle LAN cablate: Full-duplex La potenza del segnale ricevuto è confrontabile con quella del segnale trasmesso da un nodo ❖ Piuttosto difficile nelle reti wireless Potenza segnale ricevuto ≪ Potenza segnale trasmesso ❑ Analogia umana: il chiacchierone educato 6-42 CSMA/CD (collision detection) spatial layout of nodes 6-43 CSMA/CA (collision avoidance) ❑ Si usa quando non si possono rilevare le collisioni e inoltre: ❖ 𝑇 ≪ 𝜏 + 𝑇𝑎 ❖ Tipico per tutte le LAN wireless ❑ CSMA 1-persistente non funziona bene in questo caso ❖ Le collisioni sono più probabili ❖ … e non si possono rilevare ❑ CSMA p-persistente è altrettanto subottimo ❖ Il parametro p è fisso, mentre dovrebbe essere adattato alle condizioni di rete (traffico, numero di nodi, …) 6-44 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso multiplo al canale ❖ TDMA, FDMA, CDMA ❖ Slotted ALOHA, ALOHA ❖ CSMA, CSMA/CD, CSMA/CA ❖ Protocolli “a turni” ❖ IEEE 802 ed Ethernet 4-45 Protocolli MAC “a turni” Polling: ❑ Un nodo master “invita” gli altri nodi (“slave”) a trasmettere a Dati turno poll ❑ Usato di solito se i dispositivi master slave hanno poche risorse o poca Dati “intelligenza” ❑ Problemi: ❖ I messaggi di polling occupano il canale (overhead) slaves ❖ Latenza elevata ❖ Single point of failure (master) 6-46 Protocolli MAC “a turni” Token passing: T ❑ Il diritto di trasmettere è rappresentato dal possesso di un token (“gettone”) ❑ Il token si passa (niente da sequenzialmente da un nodo inviare) all’altro T ❑ Il token è un pacchetto ❑ Problemi: ❖ Overhead dovuto al token ❖ Latenza ❖ Single point of failure (token) Dati 6-47 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso multiplo al canale ❖ TDMA, FDMA, CDMA ❖ Slotted ALOHA, ALOHA ❖ CSMA, CSMA/CD, CSMA/CA ❖ Protocolli “a turni” ❖ IEEE 802 ed Ethernet 4-48 Gruppo di standard IEEE 802 rete Protocollo di livello rete (ad es., IP) Logical Link Control (LLC) data-link 802.3 (Ethernet) 802.11 MAC (vari) 802.11 (WiFi) 802.3 MAC … MAC es., PCF, DCF, HCF … 802.11 PHY (vari) 802.3 PHY (vari) … PHY es., 802.11a/b/g/n/ac fisico 6-49 Gruppo di standard IEEE 802 ❑ Le prime standardizzazioni ❖ 802.10: Network Security iniziarono negli anni ‘80 ❖ 802.11: Wireless LAN ❖ 802.1: LAN Internetworking (/a/b/g/h/f/s/n/p/ac/...) ❖ 802.2: LLC Sublayer ❖ 802.12: 100base VG ❖ 802.3: Ethernet ❖ 802.13: 100base X ❖ 802.4: Token Bus ❖ 802.15: Personal Area ❖ 802.5: Token Ring Networks ❖ 802.6: DQDB (for MANs).1 → Bluetooth.4 → ZigBee ❖ 802.7: Broadband Technical Advisory Group ❖ 802.16: Wireless MAN ❖ 802.8: Fiber-Optic Technical WiMax & Co. Advisory Group ❖... ❖ 802.9: Integrated Data and Voice Networks 6-50 Ethernet De facto, lo standard dominante nelle reti cablate: ❑ E’ stata la prima tecnologia LAN di uso massivo ❑ Un singolo chip supporta varie velocità (es., Broadcom BCM5761) ❑ Semplice ed economico ❑ Continua a migliorare 10 Mbit/s → 10+ Gbit/s Name Standard Status Mbit/ Pairs Distance Cable s 10BASE-T 802.3i-1990 Legacy 10 2 100 m Cat. 3 100BASE-TX 802.3u-1995 Current 100 2 100 m Cat 5e 1000BASE-T 802.3ab-1999 Current 1000 3 100 m Cat 5e 5GBASE-T 802.3bz-2016 Current 5000 4 100 m Cat 6 10GBASE-T 802.3an-2016 Current 10000 4 100 m Cat 6A 25GBASE-T 802.3bq-2016 Future 25000 4 30 m Cat 8 40GBASE-T 802.3bq-2016 Future 40000 4 30 m Cat 8 6-51 Nascita di Ethernet ❑ Robert Metcalfe, 1973, Xerox Palo Alto Research Center ❑ Carrier Sense Multiple Access / Collision Detection and exponential backoff → 3 Mbit/s ❑ US Patent 4.063.220, 1977 52  Nascita di Ethernet ❑ Da Spurgeon, «Ethernet – The definitive guide» In late 1972, Metcalfe and his Xerox PARC colleagues developed the first experimental Ethernet system to interconnect the Xerox Alto, a personal workstation with a graphical user interface. The experimental Ethernet was used to link Altos to one another, and to servers and laser printers. The signal clock for the experimental Ethernet interface was derived from the Alto’s system clock, which resulted in a data transmission rate on the experimental Ethernet of 2.94 Mbps. Metcalfe's first experimental network was called the Alto Aloha Network. In 1973 Metcalfe changed the name to "Ethernet," to make it clear that the system could support any computer--not just Altos--and to point out that his new network mechanisms had evolved well beyond the Aloha system. He chose to base the name on the word "ether" as a way of describing an essential feature of the system: the physical medium (i.e., a cable) carries bits to all stations, much the same way that the old "luminiferous ether" was once thought to propagate electromagnetic waves through space. Thus, Ethernet was born. 53 Standardizzazione di Ethernet: da DIX a 802.3 ❑ 1980: DIX Ethernet standard ❖ DIX = Digital-Intel-Xerox vendor consortium ❖ Interoperabilità tra i prodotti delle tre aziende ❑ 1982: Xerox rinuncia al marchio “Ethernet” ❑ 1985: IEEE 802.3 ❖ Ethernet diventa uno standard IEEE 802 Solo cambiamenti minori rispetto a DIX Inizio dell’interoperabilità globale ❖ Velocità: 10 Mbit/s ❖ Mezzo di comunicazione: Cavo coassiale spesso, max 500 m (10BASE5) Cavo coassiale sottile, max 185 m (10BASE2) Estensione di gittata fino a un limite massimo tramite ripetitori ( 1536) Indirizzo Indirizzo Dati Preambolo dest. sorgente (payload) CRC 6-61 Struttura del frame Ethernet ❑ Indirizzi: 6 byte per gli indirizzi MAC (livello 2) di sorgente e dest. ❖ Se la scheda di rete riceve un frame diretto a sè, o diretto a un indirizzo broadcast (es. i pacchetti ARP), passa il payload del frame ai protocolli di livello rete ❖ Altrimenti, scarta il frame ❖ D: perché l’indirizzo di destinazione viene prima di quello sorgente? ❑ Tipo: indica il protocollo di livello superiore (tipicamente IP, ma ce ne possono essere altri, es., Novell IPX, AppleTalk) ❑ CRC: cyclic redundancy check ❖ Se si rilevano errori, il frame viene scartato (no ARQ) ❖ D: perché il CRC viene per ultimo? Lunghezza o Tipo (se > 1536) Indirizzo Indirizzo Dati Preambolo dest. sorgente (payload) CRC 6-62 Ethernet: connessione? ACK/NACK? ❑ Connectionless: nessuno scambio di messaggi di controllo tra le interfacce di rete di mittente e destinatario ❑ Non affidabile: ❖ Non si usano ACK/NACK per recuperare frame persi tramite ritrasmissioni ❖ Non si usano codici a correzione di errore, solo CRC ❖ Quindi, i dati nel payload del frame si recuperano solo se un protocollo di livello più alto (es. TCP) implementa controllo di errore 6-63 Algoritmo CSMA/CD in Ethernet 1. La scheda di rete riceve un datagramma dal livello di rete e lo incapsula in un frame 2. Se una scheda di rete vede il canale libero, comincia a trasmettere; se lo vede occupato, attende finché non è libero e poi trasmette 3. Se la trasmissione termina senza rilevare altre trasmissioni, la scheda ritiene di aver trasmesso con successo il frame 4. Altrimenti, se la scheda rileva una collisione, trasmette un segnale di “abort” 5. Con ogni collisione, la scheda sceglie a caso il backoff tra il valore 0 e il valore 2𝑘 − 1 𝑇, 𝑘 ≤ 7, dove T è il tempo necessario a trasmettere 512 bit 6-64 Standard Ethernet 802.3: livello fisico e data link ❑ Molti standard Ethernet differenti ❖ Il protocollo MAC e formato sono comuni ❖ Diverse velocità di trasmissione 2 Mbit/s, 10 Mbit/s, 100 Mbit/s, 1 Gbit/s, 10 Gbit/s, 40 Gbit/s ❖ Diversi mezzi fisici: cavi a doppini incrociati, fibra ottica, … Protocollo MAC applicazione e formato del frame trasporto rete 100BASE-TX 100BASE-T2 100BASE-FX data link 100BASE-T4 100BASE-SX 100BASE-BX fisico Livello fisico: Livello fisico: fibra ottica rame (doppini incrociati) 6-65 Evoluzione di Ethernet ❑ Fast Ethernet ❖ 100 Mbit/s ❖ Funziona sia con gli switch sia con un canale condiviso e CSMA/CD ❑ Gigabit Ethernet ❖ 1 and 10 Gbit/s ❖ Solo reti con switch ❑ 40/100 Gigabit Ethernet ❖ 40 and 100 Gbit/s ❖ Solo reti con switch ❖ Principalmente su fibra ottica Fino a 40 km di distanza 6-66 Sommario ❑ Livello data link ❑ Ethernet switching ❑ Rilevamento e correzione di ❖ Backward learning errori, CRC ❑ Protocolli e tecnologie per l’accesso multiplo al canale ❖ TDMA, FDMA, CDMA ❖ Slotted ALOHA, ALOHA ❖ CSMA, CSMA/CD, CSMA/CA ❖ Protocolli “a turni” ❖ IEEE 802 ed Ethernet 4-67 Switch Ethernet ❑ Hub: ripetitore di livello 1 ❑ Switch: dispositivo di livello 2 (data link): ruolo più attivo ❖ Memorizza e inoltra i frame Ethernet ❖ Esamina il MAC address dei frame che arrivano Li inoltre selettivamente su uno o più link collegati Solo se necessario, ricorre a CSMA/CD per accedere al canale ❑ Trasparente ❖ Gli host non sanno (nè hanno bisogno di sapere) se sono collegati a uno switch ❑ Plug-and-play, autoapprendimento ❖ Non c’è bisogno di configurare esplicitamente gli switch per nessuna operazione di base 6-68 Ethernet e domini di collisione ❑ Topologia a bus ❖ Tutti i nodi sono nello stesso dominio di collisione, ovvero chiunque può potenzialmente collidere con chiunque altro ❑ Topologia a stella: la prevalente al giorno d’oggi ❖ Se il centro stella è un hub (ripetitore layer-1): stesso dominio di collisione ❖ Se il centro stella è uno switch (layer-2): diverso dominio di collisione Stella: switch oppure hub Bus (cavo coassiale) 6-69 Switch: trasmissioni simultanee A ❑ In una rete “switched”, ogni host ha un canale dedicato B C' per comunicare con lo switch ❑ Si usa il protocollo Ethernet su 6 1 2 ciascun link, ma gli unici nodi a usarlo sono l’host e lo 5 4 3 switch B' C ❖ No collisioni, full duplex ❖ Ogni link è un dominio di collisione a parte A' ❑ Quindi: A e A’ possono Switch con 6 interfacce (1,2,3,4,5,6) comunicare insieme a B e B’, senza collidere 6-70  Tabella di inoltro degli switch ❑ Come fa lo switch a sapere che A A’ è raggiungibile tramite l’interfaccia 4 e B’ tramite 5? C' B ❑ Mantiene una tabella del tipo: 6 1 2 MAC address Interfaccia per Time to live dell’host raggiungere l’host 5 4 3 … … … B' C ❑ Come viene mantenuta la tabella? ❖ Autoapprendimento A' ❖ Aggiornando le corrispondenze quando si ricevono nuovi frame Switch con 6 interfacce ❖ Cancellando le righe vecchie (1,2,3,4,5,6) 6-71 Switch: autoapprendimento Mittente: A Dest: A' A A A' ❑ “Backward learning” C' B ❑ Lo switch impara quali host possono essere raggiunti 6 1 2 attraverso ogni interfaccia ❖ Alla ricezione di un frame, si 5 4 3 annota la porta da cui proviene e l’indirizzo MAC B' C dell’host A' MAC address Interfaccia TTL Tabella dello switch A 1 60 (inizialmente vuota) 6-72 Switch: filtraggio e inoltro dei frame Quando si riceve un frame ❑ Si aggiorna la tabella ❑ Si inoltra il frame ❑ Se si trova una riga nella tabella che indica come raggiungere la destinazione del frame ❖ Se la destinazione si trova su una porta diversa da quella del mittente Inoltra il frame ❖ Altrimenti D: Come può essere? Scarta il frame ❑ Se non c’è una riga nella tabella Switch ❖ Flooding del frame su tutte le interfacce (eccetto quella di arrivo) 6-73 Altro esempio A A A' ❑ Destinazione A’: porta di uscita sconosciuta C' B ❖ Flooding 6 1 2 ❑ Destinazione A nota: A A' ❖ Si invia il frame 5 4 3 selettivamente su quel link B' C A' A A' MAC addr interface TTL A 1 60 switch table A' 4 60 (initially empty) 6-74 Caso con switch multipli ❑ Gli switch apprendono automaticamente anche quando sono connessi in topologie più complesse ❑ Es.: A vuole trasmettere a G → Come fanno gli switch a capire su quali porte inviare i frame? ❖ Autoapprendimento, esattamente come nel caso di un solo switch S4 S1 S3 A S2 F D I B C G H E 6-75 Rete istituzionale (molto semplice) mail server Verso reti esterne web server router Subnet IP 6-76 Switch, router e hub applicazione ❑ Store-and-forward: trasporto ❖ Router: dispositivi di livello di datagram rete rete (esaminano gli header dei frame data link datagrammi) fisico data link frame ❖ Switch: dispositivi di livello data fisico link (esaminano gli header dei frame) switch ❖ Hub : puri ripetitori di segnale ❑ Tabelle di inoltro: rete datagram ❖ Router: riempiono le tabelle data link frame usando algoritmi di routing, fisico indirizzi di rete (es. IP) ❖ Switch: apprendono le tabelle di applicazione inoltro usando il flooding e I trasporto MAC address (livello 2) rete ❖ Hub: nulla data link fisico 6-77