Protocolli di Link e Comunicazione

Lo strato di collegamento (Parte 1)

• Gli host e i router sono considerati nodi.
• I canali di comunicazione che collegano i nodi sono chiamati link.
• I link possono essere cablati o wireless.
• Le unità di dati scambiate a livello di link sono chiamate frame.
• I protocolli di strato di collegamento gestiscono il trasporto dei pacchetti lungo un singolo canale di comunicazione (link).

Lo strato di collegamento (Parte 3)

• Un pacchetto può essere gestito da diversi protocolli su collegamenti differenti (es. Ethernet, PPP, WAN).
• I servizi offerti dai protocolli del livello di link possono essere differenti (es. controllo d'errore).

Servizi offerti dallo strato di link

• Framing: i protocolli incapsulano i pacchetti del livello di rete in un frame, controllando l'accesso al mezzo (MAC).
• Rivelazione e correzione degli errori: gli errori di trasmissione possono essere individuati e corretti dal nodo ricevente.
• Controllo di flusso: evita che un nodo trasmettente saturi quello ricevente.
• Consegna affidabile dei dati e ritrasmissione: garantisce la consegna corretta dei dati e le eventuali ritrasmissioni per frame danneggiate.
• Half-duplex e full-duplex: in modalità half-duplex la trasmissione avviene in un solo senso per volta, mentre in modalità full-duplex è possibile inviare e ricevere contemporaneamente.

Esempio di implementazione

• Lo strato di collegamento è implementato in una Network Interface Card (NIC).
• Esempi di NIC includono schede Ethernet, PCMCI, 802.11.
• La NIC include componenti hardware, software e firmware.

Esempio di implementazione (lato mittente e ricevente)

• Funzione di lato mittente: Incapsula un pacchetto in un frame, configurando i bit di rilevazione errori, il controllo di flusso ecc.
• Funzione di lato ricevente: Individua gli errori, esegue il trasferimento affidabile dei dati, gestisce il controllo di flusso ecc. Infine, estrae i pacchetti e li invia al nodo ricevente.

Framing

• Lo scopo è di formare la PDU di strato (frame) incapsulando la PDU di strato superiore (pacchetto).
• L'entità ricevente deve riconoscere l'inizio e la fine della frame.
• Ad ogni frame viene aggiunto all'inizio e alla fine una sequenza fissa di bit, denominata flag.
• Problema: simulazione del flag all'interno della frame, risolta mediante bit stuffing.
• Bit Stuffing: In fase di trasmissione, vengono aggiunti bit "0" dopo ogni sequenza di cinque bit "1" consecutivi, per evitare la simulazione del flag.
• Bit Destuffing: In ricezione, viene rimosso il bit "0" aggiuntivo in caso di sequenza di cinque bit "1" consecutivi.

Bit Stuffing e De-Stuffing

• Utilizza una sequenza nota come "control escape" (01111101), usata per evitare la simulazione del flag 01111110 (ad eccezione del flag).
• In ricezione un solo "01111110" viene riconosciuto come flag. Se sono presenti due byte consecutivi "01111101”, uno dei due è eliminato

Rivelazione e correzione degli errori

• La trasmissione introduce errori.
• Il Bit Error Rate (BER) viene utilizzato quando il livello trasmissivo non soddisfa i requisiti dell'applicazione.
• Il controllo d'errore garantisce un livello di accuratezza nel trasferimento dei dati.
• Due approcci possibili: Error detection & retransmission (ARQ) e Forward Error Correction (FEC).

Principio base del controllo degli errori

• La trasmissione dei dati è organizzata in blocchi, trasformati in "parole di codice", per aggiunta di ridondanza (overhead), che permettono la rilevazione di eventuali errori durante il trasferimento.

Rivelazione di errore (2/4)

• Si definisce k la lunghezza del blocco dati da proteggere.
• Si definisce n-k il numero di bit di controllo.
• Si definiscono le codeword di uguale lunghezza a n bit.
• I metodi di codifica per la rivelazione di errori sono classificati come codici con controllo di parità (parity check codes).
• I metodi includono codici a parità singola, codici a parità a blocchi e codici a ridondanza ciclica (CRC).

Funzione di Error Detection

• I processi di calcolo dei bit di controllo vengono elaborati in base ai bit trasmessi.
• Vengono confrontati i bit ricevuti con il calcolo dei bit di controllo che sono stati già calcolati, al fine di rilevare se ci sono stati eventuali errori.
• Se i bit sono uguali, la frame viene accettata, altrimenti viene scartata.
• Metodo di calcolo è attuato in base ai bit di controllo (n-k).

Controllo di parità singola

• Aggiunta di un bit di parità ai bit informativi, in modo che il numero totale di 1 sia pari.
• Il ricevitore verifica se il numero di 1 è pari.
• Qualsiasi configurazione di errore di numero dispari di bit può essere rilevata.

Esempio Controllo di parità singola

• Dato un messaggio (0,1,0,1,1,0,0)
• calcolo il bit di parità (b8) → b8= 1 + 1 + 1 = 3 (dispari)
• Il codice della parola sarà (0, 1, 0, 1, 1, 0, 0, 1)
• Se c'è un errore in un singolo bit, il ricevitore individua l'errore.

Prestazioni del controllo di parità

• La ridondanza è data dall'aggiunta di 1 bit di ridondanza ogni k bit informativi.
• Si può calcolare l'overhead di tale sistema.
• I metodi di codifica per la rivelazione di errori rientrano nella categoria dei codici con controllo di parità.
• È possibile che un'errore non venga rilevato nel caso in cui il numero di bit modificato sia multiplo di 2
• Solo il 50% delle configurazioni di errore può essere rilevato.

Prestazioni del controllo di parità

• Normalmente si assume l'ipotesi che i canali introducono errori sui bit in modo indipendente con probabilità p.
• Alcune configurazioni di errore sono più probabili di altre.
• Quali sono le probabilità non rivelabili gli errori?

Prestazioni del controllo di parità

• Si definisce gli errori non rivelabili.
• La probabilità di non rivelare gli errori è funzione di n+1, del bit error rate (p) e del numero di possibili configuration di errore con numero di bit pari di '1'.

Quanto è "buono" un codice?

• In molti canali le configurazioni di errore più probabili sono quelle con un numero basso di bit errati.
• Questi errori trasformano le codeword in n-tuple "vicine".
• La funzione di rivelazione può fallire perché le codeword sono "vicine" tra loro.
• I buoni codici massimizzano la distanza tra codeword trasmesse.

Codici di Hamming

• Si definisce la distanza d di un codice come il minimo numero di bit in cui differiscono due qualsiasi parole di codice.
• Un codice con una distanza dispari è in grado di rilevare e correggere errori [(d-1)/2].

Esempio di codice di Hamming (7,4)

• 3 bit di parità aggiunti a 4 bit di informazione, distanza 3.

Esempio codice di Hamming (7,4)

• E' in grado di rilevare e correggere un errore o rivelare tutti gli errori di singolo bit e gli errori su due bit.

Controllo di parità bi-dimensionale

• Un numero maggiore di bit di parità aumenta le prestazioni del codice.
• Struttura la sequenza di bit informativi in colonne.
• Aggiunge un bit di parità per ogni colonna.
• Aggiunge una colonna di parità.

Capacità di rivelazione d'errore

• Analisi delle configurazioni con un numero di errori pari di uno o più di uno.

Altri codici di rivelazione d'errore

• I codici a parità singola hanno scarse prestazioni.
• I codici bi-dimensionali hanno overhead elevato.
• I codici più usati sono i checksum Internet e i codici polinomiali a ridondanza ciclica (CRC).
• Questi ultimi sono utilizzati a livello di collegamento.

Internet Checksum

• I protocolli in Internet usano bit di controllo, chiamati checksum, per rilevare errori nell'header IP (o nell'header e nel campo dati TCP/UDP).
• Il checksum è calcolato in ogni router e deve essere di facile implementazione.

Calcolo del Checksum

• Il checksum b₁ è calcolato somma di tutti i bit del blocco dati, mod 2¹⁶ - 1
• L'intero blocco trasmesso deve soddisfare una proprietà zero.
• Il calcolo del checksum viene eseguito in software.

Esempio - Uso di aritmetica modulare

• Viene mostrato un esempio di utilizzo dell'aritmetica modulare per il calcolo di un checksum.
• Viene dimostrato come la stringa binaria per 2^k equivale ad uno shift a sinistra di k posizioni.
• (x+1)(x^2 +x +1)=x^3 + 1 → calcolo modulare dell'espressione. (x+1), (x^2 +x +1) → x^3 + 1 → 3° grado

Codici CRC: i polinomi

• Le entità emittente e ricevente utilizzano un polinomio comune G(x), detto polinomio generatore.
• I coefficienti di G(x) sono binari.
• I coefficienti debbono essere entrambi uguali a 1.

Codici CRC: l'emettitore

• L'entità emittente utilizza G(x) come divisore del polinomio x^nP(x)
• Il polinomio quoziente Q(x) = x^nP(x)/G(x).
• La particolarità della divisione risiede nel fatto che i coefficienti di dividendo e di divisore sono binari e l'aritmetica viene svolta modulo 2.

Codici CRC: il ricevitore

• L'entità ricevente esegue con il polinomio generatore l'operazione di divisione, effettuata in emissione.
• Si immagina un messaggio che possa subire errori di trasmissione con una sequenza rappresentata dal polinomio E(x).

Codici CRC: il ricevitore

• Ogni bit "1" in E(x) corrisponde ad un bit invertito, quindi ad un errore isolato.
• Un errore a burst di lunghezza k è caratterizzato da un "1" iniziale, da una sequenza di 0 e 1, e da un "1" finale.

Codici CRC: il ricevitore

• Il ricevitore calcola il resto della divisione di T(x) + E(x) per G(x).
• Le modalità sono le stesse utilizzate nell'emittente.

Codici CRC: il ricevitore

• Se il resto della divisione T(x)+E(x) / G(x) è nullo, la PDU ricevuta è assume "senza errori".
• In caso contrario, si sono verificati uno o più errori durante il trasferimento.
• Un errore è non-rilevable se il polinomio E(x) contiene G(x) come fattore.

Codici CRC: protezione contro gli errori

• Un codice polinomiale in cui il polinomio generatore contiene x+1 come fattore primo, è in grado di identificare e rilevare tutti gli errori singoli e doppi.
• Il codice può anche rilevare tutti gli errori isolati di molteplicità dispari, gli errori burst di lunghezza ≤Z.

Codici CRC: polinomi generatori

• Sono standard i seguenti polinomi generatori: G(x)=x^16+x^12+x^5+1
• Sono standard i seguenti polinomi generatori: G(x)=x^32+x^26+...+x+1

Esempio calcolo CRC

• Si mostra un esempio con un polinomio generatore G(x) =x^3 + x + 1, e dati (1,1,0,0).

Implementazione tramite shift register

• Descrizione del processo di calcolo dei bit, mediante i shift register.

Implementazione tramite shift register

• Si tratta di dimostrare come i bit informativi (modulo 2^x ) vengono elaborati nell'operazione di shift.
• Il risultato finale sono i bit di controllo.

Forward Error Correction (FEC)

• Date due stringhe binarie di uguale lunghezza, X, Y, e posto W(A) = numero di bit '1' della stringa A, si definisce la distanza di Hamming tra X e Y come W(X xor Y)
• Un codice con parole di 'n' bit può rappresentare 'm' simboli.
• La capacità di correzione è una funzione della ridondanza r=n-m.
• Un codice con HD=2d+1 può correggere fino a 'd' errori binari e rivelare fino a 2d.
• Esempio: un esempio per n=10, m=2, r=8, d=2.

Controllo d'errore e controllo di flusso

• Funzioni per il controllo d'errore nello strato di trasporto vengono svolte, in un approccio end-to-end, tra gli host sorgente e di destinazione, e in un approccio hop-by-hop, in ogni hop del percorso di rete.
• Due approach: End-to-End and Hop-by-Hop.

Controllo d'errore nello strato di Data Link

• Lo strato di data link opera punto-punto tra due elementi di rete direttamente connessi.
• Le frame possono subire errori, ma la sequenza è preservata, in modo affidabile.
• Lo strato esegue la rivelazione degli errori e la ritrasmissione delle frame errate.
• Viene assicurato il trasferimento affidabile dei pacchetti.

Controllo d'errore nello strato di Trasporto (TCP)

• I controlli d'errore end-to-end sono più complessi di quelli hop-by-hop.
• I segmenti possono subire ritardi elevati, subire errori, essere persi o arrivare fuori sequenza nella rete.

End-to-End vs. Hop-by-Hop

• Una funzione può essere eseguita sia da estremo a estremo, che tratta per tratta (hop-by-hop).

Automatic Repeat Request (ARQ)

• Obiettivi: assicurare che una sequenza di PDU sia consegnata in ordine e senza errori o duplicazioni
• Procedure alternative includono Stop-and-Wait ARQ, Go-Back N ARQ, e Selective Repeat ARQ.

Stop-and-Wait ARQ

■ L'entità A trasmette una frame ed attende l'ACK. ■ Dopo ogni trasmissione, viene attivato un temporizzatore. ■ Se il temporizzatore scade, la frame viene ritrasmessa. ■ Se è ricevuto un ACK valido, il trasmettitore procede invariata. ■ Descrizione del modello con i tempi di propagazione(tprop), tempo di processamento (tproc) e il tempo di trasmissione di una frame (tf).

Numeri di Sequenza

■ L'entità emittente si comporta sempre nello stesso modo . ■ Nel secondo caso, l'entità ricevente riceve la frame 1 due volte (duplicazione). ■ B rivela la duplicazione mediante il numero di sequenza (Slast) contenuto nell'header di ciascuna frame

Esaurimento prematuro del time-out

• La stazione emittente interpreta in modo scorretto gli ACK.
• Per evitare la duplicazione è necessario aggiungere un numero di sequenza negli ACK (Rnext).

Numero di sequenza 1-bit

• Stato del trasmettitore (Slast, Rnext).

Stop-and-Wait ARQ (Trasmitter)

• Stato Ready (attesa di una richiesta): Attesa di una richiesta di invio di un pacchetto per lo strato superiore. Quando arriva la richiesta si trasmette la frame con numero di sequenza Slast e completa di CRC.
• Stato Wait (attesa dell'ACK oppure timeout): Attesa per il riscontro della frame emessa o per l'esaurimento del timer. Se il timer scade la frame viene ritrasmessa e viene riavviato il timer. Se viene ricevuto un ACK il numero di sequenza è corretto (Rnext=Slast+1).La frame è accettata e si torna nello stato Ready. Altrimenti, l'ACK è ignorato.

Stop-and-Wait ARQ (Receiver)

• Stato Ready (attesa di una nuova frame): Attesa dell'arrivo di una nuova frame.
• ricezione di una frame viene svolto il controllo d'errore (CRC).
• Se non si rilevano errori e il numero di sequenza è corretto Slast = Rnext, la frame viene ricevuta.
• Viene aggiornato il valore di Rnext, viene emesso l'ACK con valore Rnext e il pacchetto viene consegnato allo strato superiore.
• Se non si rilevano errori e il numero di sequenza non è corretto la frame viene scartata.
• Se si rilevano errori la frame viene scartata e viene emesso un ACK con valore Rnext.

Modello Stop-and-Wait ARQ

• Descrizione del modello Stop-and-Wait ARQ con le relative componenti di ritardo (tprop, tproc, TACK, tf) e relative considerazioni in termini di lunghezza di una frame e di un ACK per calcolare il tempo totale di trasferimento di una frame.

Efficienza su un canale senza-errori

• Si definiscono le componenti per il calcolo dell'efficienza di trasmissione in un canale senza errori.
• Si definiscono le componenti: numero di bit informativi consegnati, tempo totale necessario.

Esempio: Impatto del Bit Error Rate

• Calcolo dell'efficienza per un BER=0, 10^-6, 10^-5, 10^-4 dove si definiscono nf e no, tprop e tproc.

Go-back N ARQ

• Miglioramento del protocollo Stop-and-Wait.
• Eliminazione delle attese dei riscontri.
• Utilizza una finestra in trasmissione di ampiezza W.
• Usa m bit per la numerazione delle frame.
• Se vengono ricevuti gli Ack delle frame emesse prima di esaurire la finestra, la finestra viene aggiornata.
• La trasmissione viene interrotta in attesa degli Ack se la finestra si esaurisce.
• Se non sono ricevuti Ack, allo scadere di un timeout le frame della finestra vengono ritrasmesse.

Go-back-N ARQ

■ Frame con errori e fuori sequenza vengono scartate.

Go-Back-N Transmitter & Receiver

• Descrizione delle finestre di trasmissione e ricezione.

Sliding window

• Descrizione di come viene gestita la finestra di trasmissione, con il numero di sequenza e l'estremità superiore (Slast+Ws-1) della finestra.
• Descrizione di come viene gestita la finestra di ricezione, usando il numero di sequenza Rnext.

Dimensionamento della finestra e del timeout

• Descrizione delle componenti temporali per il calcolo del valore del Timeout(Tout).
• W è grande abbastanza per mantenere il canale occupato per il periodo Tout.

Dimensione della finestra vs prodotto banda-ritardo

• Tabella per il calcolo della dimensione della finestra in base al prodotto banda-ritardo e al tempo.

Efficienza del Go-Back-N

• Si definisce il tempo di trasferimento di una frame tGBN in funzione di (1-pf), t_f e W_s
• Formula per il calcolo dell'efficienza NSR (in funzione di tf,(1-pf), nf e no, Wsf )

Impatto del BER su GBN

• Calcolo dell'efficienza del Go-Back-N in funzione del Bit Error Rate (BER) (p), con nf e no, e tprop e tproc.

Selective Repeat ARQ

• Go-Back-N ARQ è inefficiente perché in caso di ritrasmissione viene emesso un numero elevato di frame, anche se queste sono state corrette dal receiver.
• Selective Repeat ritrasmette solo le frame che sono state perse.
• L'esaurimento del Timeout determina la ritrasmissione solo della frame corrispondente.
• La ricezione di un NAK causa la ritrasmissione della trama non riscontrata più vecchia.
• Il Receiver gestisce una finestra in ricezione che indica i numeri di sequenza che possono essere accettati.
• Le frame corrette ma fuori sequenza vengono bufferizzate.
• Un arrivo di una frame con Rnext determina lo scorrimento della finestra in trasmissione.

Selective Repeat ARQ

• Rappresentazione grafica delle finestre di trasmissione e ricezione.

Finestre in trasmissione e ricezione

• Come vengono gestite i limiti delle finestre (Slast e Rnext) con il numero di sequenza durante il processo di spostamento della finestra in avanti, dato un ACK.

Valori massimi di Ws e Wr

• Descrizione delle finestre di trasmissione e ricezione (con valori numerici per l'esempio).

Perchè Ws + Wr = 2^m

• Motivazione della somma massima consentita per le finestre di trasmissione e ricezione.

Efficienza del Selective Repeat

• Si definisce la probabilità Pf di perdita di una frame.
• Si definisce il numero di trasmissioni richieste per trasferire una frame in funzione di (1-Pf).
• Si definisce il tempo di trasferimento di una frame in funzione di (1-Pf)

Esempio: Impatto del BER sul Selective Repeat

• Calcolo dell'efficienza del Selective Repeat in funzione del Bit Error Rate (BER) (p).
• Esempio con nf,no, e tprop.

Confronto tra i metodi ARQ

• Formula dell'efficienza per Selective Repeat (NSR).
• Formula dell'efficienza per Go-Back-N (NGBN).
• Formula dell'efficienza per Stop-and-Wait (NSN) in funzione di (1-pf), nf e no.

Efficienza ARQ

• Confronto grafico tra l'efficienza di diverse tecniche ARQ in funzione del BER.

Strato di rete (Parte 2)

• Autoconfigurazione del protocollo DHCP.
• Procedura manuale e autoconfigurazione.
• DHCP (Dynamic Host Configuration Protocol), Plug and Play, Uso efficiente degli indirizzi.
• DHCP client_server scenario.

Protocollo DHCP

• Descrizione dei messaggi DHCP: DHCP_Discover, DHCP_Offer, DHCP_Request, DHCP_Ack.
• Descrizione dei messaggi DHCP con relativi contenuti e le rispettive funzioni.
• Descrizione dei messaggi DHCP con relativi contenuti e tempi di trasmissione.

DHCP

• Supporta tre meccanismi per la gestione degli indirizzi IP: allocazione automatica, allocazione dinamica, allocazione manuale.
• Descrizione dei campi del pacchetto DHCP.

Network Address Translator (NAT)

• Riduce l'utilizzazione dello spazio di indirizzi IP.
• Ad una Intranet è assegnato un insieme di indirizzi IP pubblici.
• All'interno della Intranet possono essere utilizzati liberamente indirizzi IP privati.
• Indirizzi di classe A, B e C.
• Dispositivo NAT che assegna un indirizzo pubblico ad un host solo quando questi deve comunicare con l'esterno.
• Esegue la traslazione dell'indirizzo privato con un indirizzo pubblico.

NAT

• Un NAT nasconde i dettagli di una Intranet al mondo esterno.
• Non è necessario allocare un intervallo di indirizzi.
• Un unico indirizzo IP è sufficiente per tutti gli host di una rete locale
• È possibile cambiare gli indirizzi delle macchine senza comunicazione
• È possibile cambiare ISP senza modificare gli indirizzi delle macchine
• Descrizione dei dispositivi interni alla rete non esplicitamente indirizzabili

NAT

• Descrizione del funzionamento del NAT durante il momento della ricezione di un pacchetto dalla rete locale.
• Descrizione del funzionamento del NAT durante il momento della ricezione di un pacchetto da Internet.

Traduzione degli indirizzi di rete

• Descrizione del funzionamento della tabella di traduzione NAT.
• Funzionamento della tabella di traduzione NAT, con descrizione dei campi presenti al suo interno.

Traduzione degli indirizzi di rete

• Il campo numero di porta è lungo 16 bit, per una migliore gestione delle connessioni.
• Il protocollo NAT contrasta i principi dell'architettura a strati TCP/IP, poiché i dispositivi di rete dovrebbero elaborare i pacchetti fino al livello 3.

Raggiungibilità di un server interno

• Il client desidera connettersi al server con indirizzo 10.0.0.1.
• L'indirizzo del server è locale, ma non può essere direttamente utilizzato come indirizzo di destinazione.
• Un unico indirizzo NAT è visibile esternamente.

Raggiungibilità di un server interno

• Soluzione 1: configurazione staticamente NAT per inoltrare le richieste di collegamento entranti a una data porta del server
• Soluzione 2: Universal Plug and Play (UPnP) e Internet Gateway Device Protocol (IGD).
• Soluzione 3: relay (usato in Skype).

Strato di rete (Parte 3)

• Funzione di instradamento (generalità).
• Instradamento in reti a pacchetto (loopfree), e definizione del cammino migliore.
• Creazione delle tabelle di routing.
• Requisiti (risposta a variazioni di stato, ottimalità, robustezza, semplicità).
• Instradamento centralizzato e distribuito.
• Instradamento statico e dinamico.

Routing Table: principio di funzionamento

• Descrizione del principio di funzionamento di una tabella di routing.

Instradamento in reti IP

• Un router possiede un Database Topologico in cui sono memorizzate le informazioni sulla topologia della rete.
• Le informazioni sulla topologia di rete sono aggiornate dai messaggi del protocollo di routing.
• L'algoritmo di routing, sulla base delle informazioni nel Database Topologico, determina periodicamente i percorsi a costo minimo tra il router e le possibili reti di destinazione (network prefix).
• La Routing Table è costruita inserendo informazioni per ogni destinazione, relative al prossimo hop per instradare il pacchetto.

Instradamento in reti IP

• Le Routing Table sono dinamiche.
• Ogni router e host aggiornano la routing table in tempo reale per tenere traccia delle informazioni sulla topologia di rete.
• L'aggiornamento dinamico è necessario perché la rete Internet non è statica.

Sistemi autonomi

• Definizione di un Sistema Autonomo (AS).
• AS particolare 'Core AS', che costituisce il backbone di Internet, e router che lo compongono (Core Router).
• Gli altri AS sono detti Stub AS.
• Ogni AS ha il proprio protocollo di instradamento.
• Definizione degli Exterior Gateway (EG) e Interior Gateway (IG).

IGP e EGP

• I protocolli di instradamento interni a un AS sono chiamati Interior Gateway Protocols (IGP).
• Le informazioni di instradamento tra sistemi autonomi (AS) sono gestite mediante Exterior Gateway Protocols (EGP).
• L'instradamento all'interno di un AS e la raccolta dei dati avviene per mezzo degli IGP.

IGP e EGP

• Un EGP svolge tre funzioni: individuazione dei router adiacenti, verifica continua della funzionalità dei router interlocutori e lo scambio periodico delle informazioni di instradamento, che riguardano la sola raggiungibilità delle reti.

Modelli a grafo di una rete

• Rappresentazione della rete come grafo pesato G=(N, E, c) dove N è l'insieme dei nodi (router), E è l'insieme degli archi (collegamenti), che ha costo c associato a ciascun ramo
• Definizione di c(x,x') = costo associato ramo (x,x’).

Costo di un cammino

• Il costo di un cammino è definito come la somma di tutti i costi degli archi presenti nel cammino.
• Un protocollo di instradamento permette di determinare il modello a grafo della rete.
• Un algoritmo determina il cammino a costo minimo tra due nodi della rete.

Metriche

• Le metriche sono utilizzate per misurare la qualità di un link o di un cammino.
• Misure come costo basso, costo elevato, lunghezza del cammino e numero di hop.
• Ulteriori metriche includono l'affidabilità, il ritardo, la larghezza di banda e il carico.

Approcci Shortest Path

• Descrizione dei protocolli di instradamento di tipo Distance Vector e Link State, presentando gli algoritmi di instradamento relativi, come Bellman-Ford e Dijkstra.

Algoritmo di Dijkstran

• Descrizione dell'algoritmo passo-passo, per calcolare il cammino a costo minimo tra un dato nodo sorgente e tutti gli altri nodi della rete.
• Tabella di esempio dell'algoritmo di Djikstra, con i relativi passi.

Algoritmo di Dijkstra

• Descrizione del funzionamento dell'algoritmo, identificando i nodi ed il costo minimo, con riferimento alle notazioni utilizzate: N, s,T, c(i,j), c(i,i).
• Inizializzazione k=1: Definizione dei nodi T1, L1(n).

Algoritmo di Dijkstra

• Definizione dell'insieme T (spanning tree del grafo).
• L'algoritmo termina quando vengono esplorati tutti i nodi.

Algoritmo di Dijkstra: esempio

• Esempio illustrativo dell'algoritmo di Dijkstra su un grafo pesato.

Esempio Dijkstra Algorithm - 1 (2)

• Descrizione con tabella delle fasi dell'algoritmo di Dijkstra su un grafico di un esempio.

Esempio Dijkstra Algorithm -2(2)

• Descrizione con tabella delle fasi dell'algoritmo di Dijkstra su un grafico di esempio.

Algoritmo di Dijkstra

• Complessità dell'algoritmo: O(n^2)

Strato di rete (Parte 1)

• Descrizione delle funzioni dello strato di rete: forwarding e routing.
• Classificazione dei servizi in reti datagramma e reti a circuito virtuale.
• Risultato dell'operazione di routing inreti a datagramma, come dati senza connessione, e come entità indipendenti.

Tipologie di servizio di rete

• Servizio senza connessione, reti a datagramma (i pacchetti sono trattati come entità indipendenti, l'instradamento è pacchetto per pacchetto, i router sono stateless).
• Servizio connection-oriented, reti a circuito virtuale (VC) (prima dell'invio dei pacchetti, viene instaurata una connessione di rete, il cammino è deciso al momento dell'instaurazione, i nodi hanno un funzionamento statefull).
• Descrizione del funzionamento in rete datagramma.

Packet Switching - Virtual Circuit

• Descrizione della necessità di una fase di set-up di connessione.
• Necessità di un protocollo di segnalazione per gestire i pacchetti in sequenza.

Connection Setup

• Descrizione dei messaggi di segnalazione per stabilire la connessione.

Connection Setup Delay

• Definizione del ritardo di instaurazione della connessione.
• Questo ritardo si somma al ritardo di transito dei pacchetti.

Virtual Circuit Forwarding Table

• Ogni porta di ingresso ha una propria tabella di forwarding.
• All'interno della tabella sono presenti i record con Input VCI, Output port e Output VCI.

Riassumendo...

• Specifica di cosa consista un circuito virtuale.
• Descrizione del funzionamento del VCI (Virtual Circuit Identifier) che cambia su tutti i collegamenti durante il percorso.

Reti a datagramma

• Descrizione delle reti a datagramma, come la rete è “stateless”.

Esempio di Tabella di routing

• Tabelle di esempio per un router, con destinazioni e Interfaccia di uscita.
• I possibili indirizzi di destinazione sono 4 miliardi.

Concetto di prefisso

• Concetto di prefisso nell'indirizzamento di una rete.
• Esempio: come si trova l'interfaccia di uscita per un certo prefisso.

Il protocollo IP

• Descrizione dell'architettura del protocollo IP e la sua posizione all'interno della pila di protocolli.

Architettura protocollare

• Descrizione dell'architettura protocollare del protocollo IP, descrivendo i protocolli come Protocolli di instradamento (RIP, OSPF, BGP), tabella d'inoltro, e protocollo ICMP.

Architettura protocollare

• Descrizione del protocollo IP (RFC 791, 919, ...) che opera con modalità di trasferimento senza connessione, non fornisce alcuna garanzia sulla QoS (servizio "best-effort").
• Descrizione delle funzionalità del protocollo IP: definizione del formato dei pacchetti, lo schema di indirizzamento, le modalità di instradamento dei pacchetti, la frammentazione e il riassemblaggio delle unità dati.

Architettura protocollare - ICMP

• Descrizione del protocollo ICMP che gestisce eventuali problemi.

Formato del pacchetto IPv4

• Descrizione generale del formato del pacchetto IP versione 4, con i campi contenuti e la loro lunghezza.

Formato del pacchetto IP

• Descrizione dei campi Vers, HLEN, Service Type, Total Length, Flag + Fragment Offset, Header Checksum, Source IP Address, Destination IP Address, Padding, Data, che possono essere contenuti nel pacchetto IPv4.

Formato del pacchetto IP

• Descrizione di versi, HLEN (Header Length), totale length, i Flags (Don't Fragment, More Fragment), Fragment Offset.

Formato del pacchetto IP

• Descrizione di tutti i campi importanti contenuti nel pacchetto IP (Service Type (TOS), Precedence, Time To Live (TTL), Protocol, Header Checksum e altri campi come Source Address (32 bit), Destination Address (32 bit), Options.).

Formato del pacchetto IP

Descrizioni dei campi importanti del pacchetto IP, e dei campi che possono variare in lunghezza (Options).

Formato del pacchetto IP - Frammentazione

Descrizioni della frammentazione del pacchetto IP.

Frammentazione dei pacchetti IP

• L'unità massima di trasmissione (MTU) è la massima quantità di dati che un frame può trasportare.
• I pacchetti IP grandi vengono suddivisi in pacchetti più piccoli
• I frammenti vengono riassemblati solo quando raggiungono la destinazione.
• Descrizione dei bit dell'intestazione IP.

Frammentazione e riassemblaggio IP

• Esempio di frammentazione di un pacchetto di 4000 byte con una MTU di 1500 byte.
• Spiegazioni di lunghezza ID, Flag, Offsett.

Formato del pacchetto IP - Time To Live (TTL)

• Descrizione del campo Time To Live (TTL) che indica quante hop sono permessi al pacchetto prima di essere scartato.
• Inizializzazione del campo TTL dall'host sorgente; decremento di una unità per ogni router attraversato dal pacchetto.

Formato del pacchetto IP - Protocol

■ Indica a quale protocollo dello stato superiore deve essere trasferito il contenuto informativo del pacchetto (es. TCP=6, UDP=17, ICMP=1)

Formato del pacchetto IP - Header Checksum

■ Protegge solo l'intestazione del pacchetto. ■ Se viene rivelato un errore, il pacchetto viene scartato.

Formato del pacchetto IP - Altri campi

• Descrizione di Source Address, Destination Address, Options (che possono variare di lunghezza).

Il protocollo ICMP

• Descrizioni delle

Questo quiz esplora i servizi e le funzioni dei protocolli a livello di link nella comunicazione di rete. Attenzione particolare viene posta su aspetti come l'identificazione degli indirizzi MAC, il controllo di flusso e la gestione degli errori. Testa la tua comprensione delle tecnologie e dei protocolli utilizzati nel livello di collegamento.