Reti di Calcolatori III-A - rete · Appunti Universitari

01 Jul 2004

Riassunto gerarchico delle nozioni del corso 2003-2004 di RETI DI CALCOLATORI del Prof. G.Fenu - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

Riferimenti: Andrew S. Tanenbaum, Reti di Calcolatori IV ed., Prentice Hall

3. livello rete (network layer)

descrizione
- è lo strato più basso ad occuparsi della trasmissione da punto a punto
- è situato tra il livello di collegamento (data-link layer) ed il livello di trasporto (transport layer)
- si occupa del trasporto dei pacchetti lungo tutto il cammino percorso dall'origine alla destinazione finale, attraversando tanti sistemi intermedi (router) della sottorete (subnet) di comunicazione quanti è necessario
- le incombenze principali di questo livello sono:
  - conoscere la topologia della sottorete (subnet) di comunicazione (l'insieme di tutti i router)
  - scegliere di volta in volta il cammino migliore (routing)
  - gestire il flusso dei dati (flow control)
  - gestire le congestioni (congestion control)
  - gestire le problematiche derivanti dalla presenza di più reti diverse (internetworking)
- nel progetto e nella realizzazione del livello network di una architettura di rete si devono prendere decisioni importanti in merito a:
  - servizi offerti al livello transport
  - organizzazione interna della sottorete

problemi dell'architettura

commutazione di pacchetto store-and-forward
- contesto in cui operano i protocolli dello strato network
  - i componenti principali del sistema sono gli apparecchi dell'operatore di telecomunicazioni (i router collegati alle linee di trasmissione)
  - i router nei locali dei clienti sono considerati come parte della sottorete perchè utilizzano gli stessi algoritmi di routing dell'operatore
- gli apparecchi operano in questo modo:
  - a) un host con un pacchetto da trasmettere invia i dati al router più vicino attraverso la sua stessa LAN, oppure attraverso un collegamento punto-punto con l'operatore di telecomunicazioni
  - b) il pacchetto viene memorizzato fino a quando non è interamente arrivato, per verificare il checksum
  - c) il pacchetto viene inoltrato al router successivo che si trova lungo il percorso, fino a quando non raggiunge l'host di destinazione dove viene consegnato
servizi forniti allo strato trasporto
- i servizi dovrebbero sempre soddisfare i seguenti obiettivi:
  - 1. i servizi non dovrebbero essere legati alla tecnologia del router
  - 2. allo strato trasporto dovrebbero essere nascosti dettagli quali il numero, il tipo e la topologia dei router
  - 3. gli indirizzi di rete disponibili allo strato di trasporto dovrebbero utilizzare uno schema di numerazione uniforme, anche attraverso le LAN e le WAN
- esistono due fazioni che si dividono sul tipo di connessione (servizio) che dovrebbe offrire questo strato:
  - 1. servizio senza connessione (connectionless) - comunità internet (Internet)
    - il lavoro dei router si limita a spostare pacchetti da un punto ad un'altro
    - la sottorete è intrinsecamente inaffidabile, quindi il controllo degli errori, la loro rilevazione ed il controllo di flusso sono lasciati agli host
    - ogni pacchetto deve contenere l'intero indirizzo di destinazione per poter essere trasportato in maniera indipendente dagli altri
    - I recenti sviluppi di Internet la stanno portando verso servizi orientati alla connessione
  - 2. servizio orientato alla connessione (circuiti virtuali) - aziende telefoniche (ATM)
    - la qualità del servizio è il fattore dominante, pertanto si preferiscono le connessioni, soprattutto per il traffico in tempo reale (voce e video)
- i servizi offerti sono indipendenti dalla realizzazione interna della subnet, è possibile infatti avere tutte le quattro combinazioni di servizio offerto e implementazione della subnet:
  - servizi connection oriented su circuiti virtuali
  - servizi connectionless su subnet datagram
  - servizi connection oriented su subnet datagram (si cerca di fornire comunque un servizio robusto)
  - servizi connectionless su circuito virtuale (esempio: IP su subnet ATM)
implementazione del servizio senza connessione (datagramma o datagram)
- i pacchetti sono inoltrati nella sottorete individualmente ed instradati indipendentemente l'uno dall'altro (non occorre una configurazione anticipata)
- i pacchetti sono denominati spesso datagramma o datagram
- la sottorete è chiamata sottorete a datagrammi
- esempio di funzionamento:
  - a) il processo P1 sull'host H1 (sorgente) deve inviare un lungo messaggio al processo P2 sull'host H2 (destinazione) attraverso una sottorete costituita da diversi router collegati tra loro
  - b) il processo sorgente porge il messaggio allo strato di trasporto dando istruzioni di inoltrarlo a P2 su H2
  - c) il codice dello strato di trasporto su H1 (tipicamente dentro il sistema operativo) aggiunge un'intestazione di trasporto all'inizio del messaggio e passa il risultato allo strato network
  - d) se il messaggio è lungo n volte la dimensione massima del pacchetto, verrà suddiviso dallo strato network in n pacchetti
  - e) i pacchetti verranno inviati in sequenza al primo router usando un protocollo punto-punto (es: PPP)
  - f) a questo punto l'operatore di telecomunicazioni assume il controllo dell'operazione
    - ogni router ha una tabella interna che indica dove devono essere inviati i pacchetti diretti ad ogni possibile destinazione
    - ogni voce della tabella è costituita da una coppia di valori che rappresentano:
      - una destinazione
      - la linea di trasmissione da utilizzare
    - possono essere utilizzate solo linee collegate direttamente
  - g) non appena raggiungono il primo router, i pacchetti vengono archiviati temporaneamente per verificare il checksum
  - h) dal primo router i pacchetti memorizzati vengono inoltrati al secondo router secondo la tabella di routing del primo (tale tabella può anche cambiare a seconda dell'algoritmo di routing)
  - i) i pacchetti vengono così passati da un router all'altro fino ad arrivare all'ultimo
  - j) raggiunto l'ultimo router, il pacchetto viene incapsulato in un frame dello strato data link e passato all'host H2
implementazione del servizio orientato alla connessione
- prima di inviare i pacchetti si deve stabilire un percorso che colleghi il router sorgente al router destinazione
- la connessione è chiamata CV (Circuito Virtuale) in analogia con i circuiti fisici del sistema telefonico
- la sottorete è chiamata sottorete a circuito virtuale
- funzionamento:
  - a) il percorso dal computer sorgente a quello di destinazione viene scelto durante l'impostazione della connessione ed archiviato nelle tabelle di routing:
    - IN (ingresso)
      - sorgente
      - circuito
    - OUT (uscita)
      - destinazione
      - circuito
  - b) ad ogni pacchetto viene associato un identificatore che indica il circuito virtuale di appartenenza
  - c) per evitare conflitti, i router sono in grado di assegnare diversi identificatori di connessione ai pacchetti in uscita (commutazione di etichetta)
  - b) quando la connessione viene rilasciata, anche il circuito virtuale viene terminato

confronto tra sottoreti CV e datagramma

problema	sottorete a datagrammi	sottorete a circuito virtuale
impostazione circuito	non è necessaria (ogni pacchetto va instradato con una procedura di ricerca complicata)	è richiesta (occorre un certo tempo per configurare il circuito - talvolta questo tempo può essere superiore al tempo di utilizzo del circuito)
indirizzamento	ogni pacchetto contiene l'indirizzo completo di destinazione e quello di origine (se i pacchetti sono corti aumenta l'overhead e si spreca banda)	ogni pacchetto contiene un numero CV corto
informazioni sullo stato	i router non conservano le informazioni sullo stato delle connessioni	ogni CV richiede spazio nella tabella del router per la connessione
routing	ogni pacchetto è instradato indipendentemente	il percorso è scelto durante l'impostazione del CV - tutti i pacchetti seguono lo stesso percorso
effetto dei guasti nei router	nessuno, tranne per i pacchetti perduti durante il guasto	tutti i CV che passano attraverso il router guasto sono terminati
qualità del servizio	difficile	facile se è possibile assegnare in anticipo abbastanza risorse ad ogni CV (buffer, banda, cicli CPU)
controllo della congestione	difficile	facile se è possibile assegnare in anticipo abbastanza risorse ad ogni CV (buffer, banda, cicli CPU)

algoritmi di routing
- svolgono la funzione principale dello strato network
- rappresentano quella parte del software dello strato network che si preoccupa di scegliere lungo quale linea di uscita vanno instradati i pacchetti in arrivo
- nella maggior parte delle sottoreti, con alcune eccezioni per quelle broadcast, i pacchetti compiono salti (hop) multipli per raggiungere la meta
- instradamento o routing
  - si occupa di riempire ed aggiornare le tabelle di inoltro attraverso l'uso degli algoritmi di routing
- inoltro
  - gestisce ogni pacchetto che arriva cercando nella tabella di routing la linea di trasmissione più adatta
- il routing (la scelta del percorso) può essere eseguito in tempi diversi:
  - routing di pacchetto
    - nelle sottoreti a datagrammi le scelte di routing vanno ripetute per ogni pacchetto
  - routing di CV
    - nelle sottoreti a CV la scelta del routing va eseguita solo durante l'impostazione del CV
  - routing di sessione (session routing)
    - un percorso rimane valido per tutta la sessione utente (es: per l'accesso ad un terminale od il trasferimento di un file)
- proprietà desiderabili per un generico algoritmo di routing:
  - precisione (correttezza)
    - deve muovere il pacchetto nella giusta direzione
  - semplicità
    - l'implementazione non deve essere troppo complicata
  - robustezza
    - dovrebbe essere in grado di far fronte ai cambiamenti di topologia e di traffico, senza che sia necessario interrompere tutto il lavoro in tutti gli host e riavviare la rete ogni volta che un router si blocca
  - stabilità
    - un algoritmo stabile raggiunge rapidamente l'equilibrio e ci rimane
  - imparzialità (equità)
    - non deve favorire nessuno
    - spesso va in contraddizione con l'ottimizzazione
  - ottimizzazione (ottimalità)
    - deve scegliere la soluzione globalmente migliore
    - molte reti tentano di ridurre il numero dei salti che il pacchetto deve compiere, perchè in questo modo si migliora il tempo di attesa, si riduce la banda consumata, e di conseguenza si migliora anche la capacità di carico
    - spesso va in contraddizione con l'imparzialità
- gli algoritmi di routing si possono raggruppare in due classi principali:
  - non adattativi (statici, static routing)
    - non basano le loro decisioni su misure o stime del traffico e della topologia corrente
    - il percorso è calcolato in anticipo, in modalità fuori linea (offline), ed è scaricato nei router all'avvio della rete
    - non tengono conto del carico istantaneo della rete
  - adattativi (dinamici, dynamic routing)
    - cambiano le loro decisioni secondo le modifiche apportate alla topologia, e di solito anche al traffico
    - si distinguono per:
      - la fonte da cui traggono le informazioni:
        
        localmente
        
        da router adiacenti
        
        da tutti i router
      - il momento in cui modificano i percorsi:
        
        ogni ΔT secondi
        
        al cambiamento del carico
        
        al cambiamento della topologia
      - il tipo di metrica utilizzata per l'ottimizzazione:
        
        distanza
        
        numero di salti (hop)
        
        tempo di transito stimato
- principio di ottimalità (assioma)
  - è un'ipotesi generale riguardo ai percorsi ottimali indipendentemente dalla topologia di rete o dal traffico
  - afferma che se il router J si trova sul percorso ottimale che collega I a K, allora anche il percorso ottimale da J a K segue la stessa rotta
  - dimostrazione:
    - posto r1 il percorso tra I e J ed r2 è quello tra J e K, se esistesse un percorso migliore di r2 questo potrebbe essere concatenato con r1 negando l'ipotesi iniziale che r1r2 è ottimale
  - sink tree
    - la serie di percorsi ottimali che collegano tutte le sorgenti ad una data destinazione formano una struttura ad albero (sink tree) dove il nodo principale è costituito dalla destinazione
    - la distanza è calcolata in base al numero di salti
    - non è necessariamente unico
    - non contiene cicli, ogni pacchetto verrà inoltrato in un numero finito e limitato di salti
    - fornisce un modo per valutare le prestazioni degli algoritmi di routing
  - l'obiettivo di tutti gli algoritmi di routing è scoprire ed utilizzare i sink tree per tutti i router
  - i collegamenti ed i router possono attivarsi e disattivarsi durante il funzionamento della rete, perciò router diversi possono avere una diversa cognizione della topologia di rete
  - i router possono acquisire le informazioni necessarie per il calcolo del sink tree in maniera differente
- routing basato sul percorso più breve (cammino minimo)
  - è un'algoritmo statico (non adattativo)
  - l'algoritmo cerca la strada più breve (cammino minimo) tra la sorgente e la destinazione
  - è possibile rappresentare i router come nodi di un grafo pesato in cui gli archi rappresentano le linee
  - la lunghezza del percorso (etichetta dell'arco) può riferirsi a diverse metriche che possono anche essere combinate tra loro:
    - numero di salti
    - distanza geografica in Km
    - percorso più veloce
    - banda
    - traffico medio
    - costo della comunicazione
    - lunghezza media della coda
    - ritardo
    - ...
  - algoritmo di Dijkstra (1959, SPF - Shortest Path First)
    - ad ogni nodo è associata un'etichetta che riporta il nodo di origine e la distanza
    - inizialmente nessun percorso è conosciuto ed i nodi sono etichettati con il simbolo di infinito
    - le etichette possono essere provvisorie (inizialmente) o permanenti (quando si trova il percorso più breve possibile dall'origine)
    - l'algoritmo prende in considerazione un nodo alla volta (working node) partendo dall'origine o dalla destinazione (marcata subito come permanente perchè non ha predecessori o successori)
    - si analizzano tutti i nodi provvisori adiacenti al working node e si rietichettano se la distanza che li separa dal nodo iniziale secondo il percorso corrente è minore di quella indicata nell'etichetta
    - si rende permanente l'etichetta provvisoria del nodo con il valore minore, facendolo così diventare il nuovo working node e si ripete il processo
- flooding (inondazione)
  - è un'algoritmo statico (non adattativo)
  - ogni pacchetto in arrivo è inviato a tutte le linee tranne quella da cui proviene
  - genera un numero elevato di pacchetti duplicati (teoricamente infinito) che vengono limitati con opportuni accorgimenti:
    - a) può utilizzare un contatore di salti nell'intestazione del pacchetto e decrementare il suo valore ad ogni salto in modo da scartare il pacchetto quando il contatore raggiunge lo zero
      - il valore iniziale del contatore dovrebbe corrispondere alla distanza tra l'origine alla destinazione ma, se questa non è conosciuta, si può assegnare il diametro dell'intera sottorete (caso peggiore)
    - b) si tiene traccia dei pacchetti già trasmessi in maniera da evitare una ritrasmissione
      - il router di origine inserisce un numero di sequenza in ogni pacchetto che riceve dai suoi host
      - ogni router ha bisogno di una lista per ciascuno dei router sorgenti che indichi i numeri di sequenza già trasmessi da quella di origine
      - per impedire una crescita illimitata ogni lista dovrebbe essere integrata con un contatore k in modo da indicare che sono stati visti tutti i numeri di sequenza fino a k
  - flooding selettivo (selective flooding)
    - è una variante dell'algoritmo di flooding
    - i router trasmettono i pacchetti in arrivo solo verso le linee che vanno approssimativamente nella direzione giusta
  - l'algoritmo di flooding non è molto funzionale ma ha alcuni impieghi pratici:
    - nelle applicazioni militari dove un gran numero di router può saltare in aria in un istante la robustezza dell'algoritmo riveste una particolare importanza
    - nelle applicazioni database distribuite, quando è necessario aggiornare contemporaneamente tutti i database
    - nelle reti wireless tutti i messaggi trasmessi da una sorgente radio possono essere ricevuti da tutte le stazioni raggiungibili
    - può essere utilizzato come metrica di confronto per altri algoritmi di flooding (l'algoritmo di flooding sceglie sempre il percorso più breve)
- Flow-based routing (routing basato sul flusso)
  - si basa sull'idea di:
    - calcolare in anticipo il traffico atteso su ogni linea
    - da questi calcoli derivare una stima del ritardo medio atteso per ciascuna linea
    - basare su tali informazioni le decisioni di routing
  - le informazioni necessarie per poter applicare l'algoritmo sono:
    - la topologia della rete
    - la matrice delle quantità di traffico T(i,j) stimate fra ogni coppia (i,j) di router
    - le capacità (in bps ad esempio) delle linee point to point
  - vengono fatte le seguenti assunzioni:
    - il traffico è stabile nel tempo e noto in anticipo
    - il ritardo su ciascuna linea aumenta all'aumentare del traffico sulla linea e diminuisce all'aumentare della velocità della linea secondo le leggi della teoria delle code
  - dai ritardi calcolati per le singole linee si può calcolare il ritardo medio dell'intera rete, espresso come somma pesata dei ritardi delle singole linee. Il peso di ogni linea è dato dal traffico su quella linea diviso il traffico totale sulla rete.
  - funzionamento:
    - si sceglie un algoritmo di routing
    - sulla base di tale algoritmo si determinano i percorsi che verranno seguiti per il collegamento fra ogni coppia di router
    - si calcola il traffico che incide su ogni linea (che è uguale alla somma di tutti i T(i,j) instradati su quella linea)
    - si calcola il ritardo di ogni linea
    - si calcola il ritardo medio della rete
    - si ripete il procedimento con vari algoritmi di routing, scegliendo alla fine quello che minimizza il ritardo medio dell'intera rete
- routing basato sul vettore delle distanze (distance vector routing)
  - è un'algoritmo dinamico (adattativo)
  - è anche noto come algoritmo di routing di Bellman-Ford distribuito o algoritmo Ford-Fulkerson
  - è stato l'algoritmo di routing originale di ARPANET (fino al 1979)
  - è stato utilizzato in Internet col nome di RIP (Routing Internet Protocol):
    - 1. pacchetti ECHO (misurano il ritardo su una tratta)
    - 2. ogni router invia ciclicamente ai router limitrofi i ritardi stimati per raggiungere i nodi della rete
    - 3. ogni router somma, al tempo per raggiungere il nodo x, il tempo che da questo serve per giungere al nodo-destinazione
    - 4. la mappa di tali path con ritardo è la tabella di routing
  - è stato utilizzato nelle prime versioni di DECnet e IPX
  - ogni router conserva una tabella (vettore) che definisce la miglior distanza conosciuta per ogni destinazione (router) e la linea che conduce a tale destinazione
  - le tabelle vengono aggiornate scambiando informazioni (lista delle proprie stime di ritardo relative a ciascuna destinazione) con i router vicini ogni T msec
  - ogni voce del vettore è composta da due parti:
    - la linea di trasmissione preferita da utilizzare per quella destinazione
    - la stima del tempo o della distanza associata a quella destinazione
  - la distanza puo essere espressa utilizzando metriche differenti, ad es:
    - numero di salti
      - la "distanza" è pari ad un solo salto
    - lunghezza della coda
      - il router esamina ogni coda
    - ritardo
      - il router può misurare questo valore mediante speciali pacchetti ECHO che il ricevitore manda indietro il più velocemente possibile dopo aver registrato al loro interno la data e l'ora di trasmissione
  - problema del conto all'infinito (convergenza lenta, count-to-infinity)
    - il routing basato sul vettore delle distanze ha il serio difetto pratico di convergere alla soluzione corretta molto lentamente
    - le buone notizie (uno scambio con un router vicino indica un ritardo più breve verso la destinazione) vengono elaborate rapidamente in un solo scambio di vettori
    - le cattive notizie (interruzione di linea, spegnimento di un router) vengono interpretate molto lentamente
    - il nocciolo del problema è che quando X dice ad Y che ha un percorso che punta da qualche parte, Y non ha modo di sapere se lui stesso fa parte di quel percorso
    - nessun router ha mai un valore che supera di oltre una unità quello minimo di tutti i vicini
    - lentamente tutti i router trovano la loro strada per l'infinito
    - per limitare il numero di scambi conviene impostare come infinito il valore corrispondente al percorso più lungo più 1
    - se la metrica è basata sul ritardo non esiste un valore massimo, si imposta quindi un valore alto arbitrario
- routing basato sullo stato dei collegamenti (link state routing)
  - è un'algoritmo dinamico (adattativo)
  - nel 1979 ha sostituito l'algoritmo basato sul vettore delle distanze utilizzato in ARPANET
  - è largamente utilizzato in diverse varianti
  - l'idea di base può essere riassunta in 5 punti, ogni router deve:
    - 1. scoperta dei vicini
      - quando viene acceso il router cerca di scoprire chi sono i suoi vicini inviando uno speciale pacchetto HELLO su ogni linea punto-punto
      - i router dall'altro capo della linea devono rispondere fornendo la propria identità
      - le identità dei router devono essere definite da nomi globalmente unici
      - se più router sono collegati alla stessa LAN, quest'ultima può essere sostituita con un nodo virtuale
    - 2. misurazione del costo della linea
      - ogni router deve poter conoscere o stimare il ritardo di ognuno dei suoi vicini
      - il ritardo viene stimato dividendo per due il tempo di andata e ritorno di uno speciale pacchetto ECHO che viene inviato a tutti i router vicini
      - le misurazioni con gli ECHO possono essere eseguite più volte per poter calcolare una media dei risultati ed avere così stime più affidabili
      - è anche possibile temporizzare gli ECHO in maniera da tener conto delle assimmetrie della linea in andata e ritorno (valutazione del carico)
      - in alcuni casi la valutazione del carico può mettere in oscillazione i router tra due linee che vengono caricate e scaricate alternativamente
    - 3. costruzione dei pacchetti che contengono lo stato dei collegamenti
      - ogni router deve costruire un pacchetto che contiene tutte le informazioni raccolte:
        
        identità del trasmittente
        
        numero di sequenza
        
        età
        
        lista dei vicini con relativo ritardo misurato
      - tali pacchetti possono essere costruiti:
        
        periodicamente ad intervalli regolari
        
        al verificarsi di un'evento significativo (interruzione di linea, spegnimento, accensione o cambiamento delle proprietà di un router, ...)
    - 4. distribuzione dei pacchetti che contengono lo stato dei collegamenti
      - occorre distribuire i pacchetti in maniera affidabile
      - durante la distribuzione i router modificano i loro percorsi, quindi router diversi potrebbero usare topologie diverse col rischio di creare inconsistenza, cicli, computer irraggiungibili e così via
      - l'idea di base è quella di utilizzare il flooding per la distribuzione dei pacchetti
        
        il flusso è tenuto sotto controllo inserendo un numero di sequenza che viene incrementato di uno ad ogni nuovo pacchetto inviato
        
        i router tengono traccia di tutte le coppie (router sorgente, sequenza) rilevate
        
        all'arrivo di un nuovo pacchetto, il router confronta i dati con quelli già visti e scarta i pacchetti duplicati o obsoleti
        
        difetti:
        
        i numeri di sequenza ripetitivi potrebbero generare il caos
        
        si utilizzano pertanto numeri di sequenza da 32 bit che trasmessi ogni secondo si esaurirebbero in 137 anni
        
        quando un router si blocca perde traccia dei suoi numeri di sequenza
        
        se il conteggio ricomincia da 0, il pacchetto successivo viene rifiutato perchè ritenuto duplicato
        
        se un numero di sequenza arriva danneggiato può sfasare l'intera ricezione dei pacchetti
        
        soluzione ai difetti:
        
        si aggiunge l'età ad ogni pacchetto e si decrementa il suo valore una volta al secondo così da poterlo scartare quando l'età raggiunge lo zero
        
        il campo età è anche decrementato da ogni router durante il processo di flooding
        
        migliorie:
        
        i pacchetti sullo stato dei collegamenti, una volta ricevuti, vengono inseriti temporaneamente in un'area di mantenimento prima di essere accodati per la trasmissione, così da poter essere confrontati con i pacchetti successivi
        
        tutti i pacchetti sullo stato dei collegamenti ricevono un'acknowledgement per prevenire errori sullo stato delle linee da router a router
        
        quando una linea smette di essere impegnata, l'area di mantenimento viene esaminata in modalità round robin per selezionare un pacchetto o un acknowledgement da inviare
    - 5. elaborazione dei nuovi percorsi
      - dopo aver accumulato una serie completa di pacchetti sullo stato della connessione, il router può costruire l'intero grafo della sottorete poiché è rappresentato ogni collegamento
      - ogni collegamento è rappresentato due volte, una per ogni direzione
        
        si può usare la media dei valori o usarli separatamente
      - si può utilizzare l'algoritmo di Dijkstra per costruire il percorso più breve verso tutte le possibili destinazioni
      - i risultati dell'algoritmo di Dijkstra possono essere memorizzati nelle tabelle di routing prima di riprendere le normali operazioni
      - difetti (descritti da Perlman - 1998):
        
        per una sottorete con n nodi, ognuno con k vicini, la memoria necessaria per conservare i dati in input è proporzionale a kn, questo può essere un problema per grandi sottoreti
        
        se un router afferma di avere una linea che non ha o dimentica di indicare una linea esistente, il grafo della sottorete risulterà scorretto
        
        se un router non riesce ad inoltrare pacchetti o li danneggia durante l'inoltro, sorgeranno guai
        
        se un router esaurisce la memoria o esegue un calcolo di routing errato c'è da aspettarsi il peggio
        
        se la sottorete è composta da decine o centinaia di migliaia di nodi, non è più trascurabile l'eventualità che saltuariamente un router si guasti
  - è largamente utilizzato nelle reti reali:
    - protocollo OSPF, ampiamente utilizzato in Internet
    - protocollo IS-IS (Intermediate System-Intermediate System) progettato per DECnet e poi adottato da OSI
    - la differenza principale tra OSPF e IS-IS è che quest'ultimo è codificato in modo da rendere semplice e naturale il trasporto simultaneo di informazioni relative a più protocolli di strato network (molto vantaggioso in ambienti multiprotocollo), funzionalità non supportata da OSPF
- routing gerarchico (routing di frontiera, autonomous system)
  - si utilizza per grandi sottoreti per limitare sia la dimensione delle tabelle nei router (memoria) che il tempo di analisi dei dati (carico CPU)
  - i router sono divisi in zone chiamate anche regioni
  - ogni router conosce i dettagli relativi al routing dei pacchetti diretti a destinazioni nella stessa regione ma non sa nulla della struttura interna delle altre regioni
  - quando si interconnettono reti diverse è naturale considerare ogni rete come una regione separata
  - per reti enormi è possibile aumentare il numero di livelli raggruppando le regioni in cluster, zone, gruppi, ...
  - le varie regioni sono interfacciate tramite dei router "di frontiera"
  - le tabelle di routing conterranno una riga (destinazione, linea, salto) per ogni router locale, mentre le destinazioni che si riferiscono alle altre regioni saranno condensate in un'unico router di frontiera
  - lo spazio risparmiato nelle tabelle aumenta al crescere del rapporto tra numero di regioni e numero di router per regione
  - lo svantaggio è rappresentato dalla crescita della lunghezza dei percorsi
  - numero ottimale di livelli (Kamoun e Kleinrock, 1979)
    - il numero ottimale di livelli per una sottorete di N router è uguale a ln(N), per un totale di e ·ln(N) voci per router
    - l'aumento della lunghezza del percorso medio reale causato dal routing gerarchico è sufficientemente piccolo da renderlo il più delle volte accettabile
- routing broadcast
  - è utilizzato per le trasmissioni broadcast (trasmissione contemporanea di un pacchetto a tutte le destinazioni)
  - esistono diversi metodi:
    - grezzo
      - la sorgente invia un pacchetto distinto a tutte le destinazioni
      - non richiede alcuna implementazione speciale
      - svantaggi
        
        spreca la banda
        
        obbliga la sorgente a possedere una lista completa delle destinazioni
    - flooding
      - usa la stessa tecnica dell'algoritmo di routing punto-punto
      - utilizza un meccanismo speciale per l'interruzione del processo che adotta un contatore di salto in ogni pacchetto ed una conoscenza a priori del diametro della sottorete, oppure un elenco di pacchetti già visti per ogni sorgente
      - genera troppi pacchetti e consuma troppa banda
    - multidestination routing (routing a più destinazioni)
      - ogni pacchetto contiene una lista delle destinazioni o una mappa di bit che indica le destinazioni desiderate
      - l'insieme delle destinazioni viene diviso tra le linee di trasmissione
      - funzionamento
        
        quando riceve un pacchetto, il router controlla tutte le destinazioni per determinare l'insieme di linee di trasmissione richieste
        
        il router genera una nuova copia del pacchetto per ogni linea di output usata ed include in ogni pacchetto solo quelle linee che si trovano su quella linea
        
        dopo un numero sufficiente di salti ogni pacchetto conterrà una sola destinazione e potrà essere trattato come un pacchetto normale
    - sink tree (alberi di ricoprimento, spanning tree)
      - spanning tree
        
        sottoinsieme che comprende tutti i router ma che non contiene cicli
      - se ogni router sa quali delle sue linee appartengono allo spanning tree, allora può copiare un pacchetto broadcast in arrivo su tutte le linee dello spanning tree esclusa quella di ingresso
      - vantaggi
        
        utilizza in modo eccellente la banda
        
        genera in assoluto il minimo numero di pacchetti necessari per svolgere il lavoro
      - svantaggi
        
        ogni router deve conoscere uno spanning tree (informazione disponibile nel routing basato sullo stato dei collegamenti)
    - reverse path forwarding
      - approssima il comportamento del metodo precedente ache quando il router non conosce il sink tree
      - funzionamento
        
        quando riceve un pacchetto broadcast, il router verifica se è giunto attraverso la linea che normalmente è utilizzata per inviare i pacchetti alla sorgente della trasmissione broadcast
        
        in caso affermativo
        
        è molto probabile che il pacchetto di broadcast abbia seguito il percorso migliore dal router, e che perciò sia la prima copia arrivata al router
        
        il router inoltra le copie del pacchetto attraverso tutte le linee esclusa quella di input
        
        in caso negativo
        
        il pacchetto è scartato in quanto è probabile che si tratti di un duplicato
      - vantaggi
        
        è un sistema ragionevolmente efficiente e facile da implementare
        
        non richiede che i router conoscano lo spanning tree
        
        non si deve elaborare una lista di destinazione o mappa di bit per ogni pacchetto broadcast (come nel multidestination routing)
        
        non è necessario alcun meccanismo speciale d'interruzione del processo (come nel flooding)
- routing multicast
  - è utilizzato per le trasmissioni multicast (trasmissione contemporanea di un pacchetto ad un gruppo ben definito di nodi ma non a tutti)
    - la trasmissione punto-punto risulta troppo costosa
    - la trasmissione broadcast è inefficiente e presenta problemi di sicurezza
    - richiede la gestione dei gruppi
      - sistema che consente di creare e distruggere i gruppi e che permette ai processi di entrare ed uscire dai gruppi
      - non riguarda l'algoritmo di routing
      - quando un processo si unisce ad un gruppo deve informare il suo host
      - i router devono sapere quali sono gli host appartenenti ad ogni gruppo
        
        metodi:
        
        gli host devono comunicare ai loro router i cambi di gruppo
        
        i router devono interrogare periodicamente i loro host
      - i router comunicano con i loro vicini, perciò le informazioni si propagano attraverso la sottorete
    - funzionamento:
      - ogni router elabora uno spanning tree che copre tutti gli altri router
      - quando un processo invia un pacchetto multicast ad un gruppo, il primo router esamina il suo spanning tree e lo accorcia, rimuovendo tutte le linee che non conducono agli host che sono membri di quel gruppo
      - i pacchetti multicast sono inoltrati solo attraverso lo spanning tree appropriato
    - metodi di riduzione dello spanning tree
      - semplice
        
        può essere utilizzato se si adotta il routing basato sullo stato dei collegamenti e se ogni router conosce la topologia completa, quindi sa quali host appartengono a ciascun gruppo
        
        lo spanning tree si può accorciare partendo dalla fine di ogni percorso, procedendo verso il nodo principale (la radice) e rimuovendo tutti i router che non appartengono al gruppo in questione
      - reverse path forwarding modificato
        
        può essere utilizzato quando si adotta il routing basato sul vettore delle distanze
        
        si usa l'algoritmo di base del reverse path forwarding
        
        ogni volta che un router che non ha host interessati ad un particolare gruppo (e non ha connessioni dirette con altri router) riceve un pacchetto multicast diretto a quel gruppo, risponde con un messaggio PRUNE che avvisa il trasmittente di non inviare più alcun messaggio multicast per quel gruppo
        
        può rispondere con un messaggio PRUNE anche un router che riceve messaggi di questo tipo su tutte le sue linee, e non ha host appartenenti a quel gruppo
        
        la sottorete viene ridotta in modo ricorsivo
        
        si adatta male alle grandi reti
        
        ogni router dovrà memorizzare m·n strutture ad albero per n gruppi con m numero di membri medio)
      - core-based tree
        
        viene elaborato un singolo spanning tree per gruppo, con il nodo principale (radice) vicino alla metà del gruppo
        
        per inviare un messaggio multicast, un host trasmette i dati al nodo principale, che poi esegue il multicast lungo lo spanning tree
        
        la riduzione del fabbisogno per ciascun gruppo (in termini di consumo di memoria) da m gruppi ad una sola struttura ad albero rappresenta un grande risparmio
algoritmi per il controllo della congestione
- controllo della congestione
  - garantisce che la sottorete sia in grado di trasportare il traffico immesso
  - è un problema globale che coinvolge il comportamento di tutti gli host, tutti i router, l'elaborazione di tipo store-and-forward eseguita dai router, e tutti gli altri fattori che tendono a diminuire la capacità di carico della sottorete
  - non va confuso con il controllo di flusso che si riferisce unicamente al traffico punto-punto e che si preoccupa di evitare che un trasmettitore veloce sovraccarichi un ricevitore lento
- congestione
  - situazione nella quale sono presenti troppi pacchetti in una porzione della sottorete che determinano un degrado delle prestazioni
  - il carico è (temporaneamente) più grande di quello che può essere gestito dalle risorse (in una parte del sistema)
  - quando il numero dei pacchetti immesso dagli host nella sottorete è minore della capacità di trasporto della sottorete, tutti i pacchetti vengono inoltrati (tranne i pochi afflitti dagli errori di trasmissione) ed il loro numero è proporzionale al numero trasmesso
  - se il traffico aumenta in modo eccessivo, i router non riescono a far fronte alla situazione e cominciano a perdere pacchetti, ciò tende a far peggiorare le cose
  - con un traffico elevatissimo, le prestazioni crollano completamente e quasi nessun pacchetto viene inoltrato
  - può essere causata da diversi fattori:
    - memoria insufficiente
      - se improvvisamente diversi flussi di pacchetti cominciano ad arrivare da varie linee di input e tutti necessitano della stessa linea di output, inizia a formarsi una coda
      - se la memoria non è sufficiente, alcuni pacchetti non potranno essere memorizzati e quindi andranno persi
      - la memoria potrà essere aumentata fino ad una certa soglia, oltre la quale la congestione subirá un peggioramento dovuto alla ritrasmissione dei pacchetti scaduti in coda
    - processori lenti
      - se le CPU dei processori eseguono lentamente le operazioni richieste (accodamento dei buffer, aggiornamento delle tabelle, ...), le code possono formarsi anche quando la capacità della linea è maggiore del necessario
    - linee a banda stretta
      - generano code
    - adattamento delle parti del sistema
      - generalmente è il vero problema
      - occorre raggiungere un equilibrio tra le parti del sistema evitando colli di bottiglia
- principi generali del controllo della congestione
  - secondo la teoria del controllo è possibile dividere le soluzioni in due gruppi:
    - cicli aperti (open loop, senza controreazione)
      - tentano di risolvere il problema mediante un buon progetto che renda improbabile la manifestazione del problema stesso
      - una volta che il sistema è stato attivato, non viene eseguita alcuna correzione in corsa
      - gli strumenti che eseguono il controllo sono prese senza tener conto dello stato corrente della rete:
        
        decidere quando deve essere accettato nuovo traffico
        
        decidere quando e quali pacchetti devono essere scartati
        
        decidere la pianificazione della rete in vari punti
    - cicli chiusi (closed loop, con controreazione)
      - si basano sul concetto di retroazione
      - nel controllo della congestione, si dividono in tre parti:
        
        1. controllo del sistema (sottorete) per rilevare quando e dove si presenta la congestione
        
        si possono usare diverse metriche (valori crescenti indicano una congestione crescente):
        
        percentuale di pacchetti scartati a causa di un esaurimento del buffer
        
        lunghezza media della coda
        
        numero di pacchetti scaduti e ritrasmessi
        
        ritardo medio dei pacchetti
        
        deviazione standard del ritardo di pacchetto
        
        2. passaggio di queste informazioni ai punti dove si possono eseguire le azioni di correzione
        
        le informazioni sulla congestione sono trasferite dal punto dove sono state rilevate a quello dove è possibile fare qualcosa per risolvere il problema
        
        esistono diversi approcci:
        
        a) il router che ha rilevato la congestione invia un pacchetto alla/e sorgente/i del traffico annunciando il problema
        
        i pacchetti aggiuntivi aumentano il carico proprio quando sarebbe necessario diminuirlo
        
        b) è possibile riservare ai router un bit od un campo in ogni pacchetto per segnalare la congestione ai suoi vicini
        
        c) host e router spediscono periodicamente dei pacchetti di segnalazione per richiedere in modo esplicito informazioni sulla congestione
        
        queste informazioni possono essere usate per instradare il traffico in modo da aggirare le aree congestionate
        
        3. regolazione del funzionamento del sistema per correggere il problema
        
        è necessario regolare con attenzione la scala temporale per evitare oscillazioni dovute a tempi troppo brevi o eccessivi ritardi
  - tassonomia degli algoritmi di controllo della congestione (Yang e Reddy, 1995):
    - ciclo aperto
      - soluzioni che agiscono sulla sorgente
      - soluzioni che lavorano sulla destinazione
    - ciclo chiuso
      - soluzione a retroazione esplicita
        
        i pacchetti per avvisare la sorgente vengono spediti indietro dal punto della congestione
      - soluzioni a retroazione implicita
        
        la sorgente deduce l'esistenza della congestione effettuando osservazioni locali (es: tempo di arrivo degli acknowledgement)
  - possibili soluzioni:
    - aumentare le risorse, ad esempio:
      - la sottorete può iniziare ad utilizzare linee telefoniche dial-up per aumentare temporaneamente la banda tra certi punti
      - alcuni sistemi satellitari possono aumentare la banda attraverso l'aumento della potenza di trasmissione
      - ripartire il carico tra più percorsi può aumentare efficacemente la banda
      - talvolta è possibile utilizzare i router di riserva (utilizzati normalmente solo come dispositivi di emergenza per la robustezza ai guasti) per gestire congestioni gravi
    - diminuire il carico
      - quando non è possibile aumentare la capacità della sottorete si cerca di diminuire il carico
      - il carico può essere ridotto in diversi modi:
        
        negando servizi ad alcuni utenti
        
        degradando il servizio ad alcuni o tutti gli utenti
        
        facendo in modo che gli utenti programmino le richieste in modo più prevedibile
  - le soluzioni possono essere applicate meglio sullo strato network per le sottoreti che usano internamente i circuiti virtuali, per le sottoreti a datagramma si possono implementare meglio sulle connessioni dello strato di trasporto
- criteri per prevenire la congestione
  - sono i criteri che vengono applicati nei sistemi a ciclo aperto per prevenire le congestioni
  - tentano di raggiungere il loro obiettivo usando opportuni criteri su più livelli (organizzati per strato):
    - trasporto (transport)
      - criterio di ritrasmissione
        
        riguarda la velocità con la quale un trasmettitore gestisce la scadenza dei pacchetti e che cosa ritrasmette dopo un timeout
        
        un trasmettitore nervoso che ritrasmette troppo velocemente tutti i pacchetti scaduti usando il go-back-n immetterà nel sistema un carico più pesante di quello che utilizza una tranquilla ripetizione selettiva
      - criterio di caching fuori sequenza (criterio di utilizzo dei buffer)
        
        se i ricevitori scartano sistematicamente tutti i pacchetti fuori sequenza, questi pacchetti verranno successivamente ritrasmessi, creando altro carico
      - criterio di acknowledgement
        
        se ogni pacchetto riceve immediatamente acknowledgement, i pacchetti di acknowledgement generano traffico aggiuntivo
        
        se i pacchetti di acknowledgement vengono trasportati dal traffico inverso si possono avere ritrasmissioni e scadenze aggiuntive
      - criterio di controllo di flusso
        
        uno schema di controllo di flusso rigido (es: finestra piccola) riduce la velocità di trasmissione dei dati e di conseguenza aiuta a combattere la congestione
      - determinazione dei timeout
        
        è difficile determinare l'intervallo di scadenza perchè il tempo di transito attraverso la rete è meno prevedibile del tempo di transito attraverso un cavo che collega due router
        
        se l'intervallo di scadenza è troppo breve, verranno trasmessi inutilmente i pacchetti aggiuntivi
        
        se l'intervallo di scadenza è troppo lungo, la congestione verrà ridotta ma il tempo di risposta ne soffrirà ogni volta che un pacchetto si perde
    - rete (network)
      - scelta fra circuiti virtuali e datagrammi nella sottorete
        
        molti algoritmi di controllo della congestione funzionano solo con le sottoreti a circuito virtuale
      - criterio di accodamento e di servizio dei pacchetti
        
        riguarda il numero di code presenti sui router: uno coda per ogni linea di input, una coda per ogni linea di output o entrambe
        
        si riferisce inoltre all'ordine in cui i pacchetti sono elaborati (round robin o in base alla priorità)
      - criterio di eliminazione dei pacchetti (criterio di scarto)
        
        regola che stabilisce quale pacchetto scartare quando non c'è più spazio
        
        un buon criterio può alleviare la congestione, uno cattivo può peggiorarla
      - algoritmo di routing
        
        è possibile alleviare la congestione distribuendo il traffico su tutte le linee (evitando di sovraccaricare le linee congestionate)
      - gestione della vita utile dei pacchetti
        
        definisce quanto devono vivere i pacchetti prima di essere scartati
        
        se la vita è troppo lunga, i pacchetti persi possono intasare tutto per molto tempo
        
        se la vita è troppo breve, i pacchetti possono scadere prima di raggiungere le destinazioni, causando ritrasmissioni
    - collegamento (data link)
      - criterio di ritrasmissione
      - criterio di caching fuori sequenza
      - criterio di acknowledgement
      - criterio di controllo di flusso
- controllo della congestione nelle sottoreti a circuito virtuale
  - tecniche dinamiche (ciclo chiuso) per controllare le congestioni nei CV:
    - controllo di ammissione
      - tecnica largamente utilizzata per evitare il peggioramento di una congestione già iniziata
      - una volta che la congestione è stata segnalata, nessun circuito virtuale viene più impostato fino a quando il problema non scompare
      - i tentativi di impostare nuove connessioni sullo strato di trasporto falliscono
      - è un metodo semplice e facile da implementare
    - creazione di nuovi circuiti virtuali
      - si creano nuovi circuiti virtuali instradati in maniera tale da aggirare le aree congestionate (si evitano i router e le linee congestionate)
    - negoziazione delle risorse
      - durante l'impostazione del CV l'host e la sottorete negoziano vari parametri tra i quali:
        
        il volume del traffico
        
        la forma del traffico
        
        la qualità di servizio
        
        ...
      - i parametri negoziati possono comprendere dello spazio nelle tabelle e nei buffer dei router e della banda sulle linee
      - questo rende poco probabile la congestione perchè tutte le risorse necessarie sono garantite e disponibili
      - l'utilizzo costante di questa tecnica presenta lo svantaggio di sprecare risorse (spreco di banda)
- controllo della congestione nelle sottoreti a datagrammi
  - ogni router può facilmente tenere sotto controllo l'utilizzo delle sue linee di output ed altre risorse
  - è possibile associare ad ogni linea una variabile reale u (valore compreso tra 0 ed 1) che rifletta l'utilizzo recente della linea:
    - u _nuovo = au _vecchio + (1 - a)f
    - f : campione istantaneo della linea che ne mostra l'utilizzo (0 = non utilizzata, 1= utilizzata)
    - a : costante che determina la velocità con cui il router dimentica la cronologia recente
  - ogni volta che la variabile u si sposta sopra la soglia di guardia, la linea di output entra in stato di allarme
  - il router controlla ogni pacchetto in arrivo per vedere se la linea di output associata a quei dati è in allarme, in caso affermativo esegue un'azione correttiva:
    - bit di allarme
      - utilizzato dalla vecchia architettura DECNET e frame relay
      - quando il pacchetto arriva a destinazione, l'entità di trasporto copia il bit nel successivo pacchetto di acknowledgement trasmesso alla sorgente, che quindi riduce il traffico (diminuisce la velocità di trasmissione)
      - finchè rimane in stato di allarme, il router continua ad impostare il bit di allarme
    - choke packet (pacchetti regolatori)
      - il router invia all'host sorgente un choke packet dandogli la destinazione trovata nel pacchetto
      - il pacchetto originale viene etichettato in modo da impedire la generazione di altri choke packet
      - l'host che riceve il choke packet riduce di una certa percentuale il traffico verso la destinazione specificata
      - per un certo intervallo di tempo l'host ignora i choke packet successivi che si riferiscono alla stessa destinazione e poi riprende l'ascolto
      - trascorso un certo periodo di tempo senza la ricezione di choke packet, l'host riaumenta la velocità
      - gli host possono ridurre il traffico regolando i loro parametri, per esempio la dimensione della finestra
      - riduzioni di velocità tipiche sono 0.5 seguita da 0.25 e così via
      - gli aumenti di velocità avvengono per incrementi più piccoli per evitare una veloce ricomparsa della congestione
      - esistono diverse varianti di questo algoritmo
        
        a) i router possono mantenere diverse soglie di guardia
        
        in base alla soglia che viene oltrepassata, il choke packet può contenere un avviso, un allarme o un vero e proprio ultimatum
        
        b) come segnale di attivazione si utilizza la lunghezza della coda o l'utilizzo del buffer al posto dell'utilizzazione della linea
        
        con queste metriche si può utilizzare la stessa ponderazione esponenziale applicata ad u
    - choke packet hop-by-hop
      - pone rimedio alla la lentezza di reazione del sistema a choke packet (l'host che produce i pacchetti ci mette un certo tempo a ricevere i choke packet ed a diminuire di conseguenza il ritmo della trasmissione)
      - si costringono i router sul percorso a rallentare subito il ritmo appena ricevono i choke packet
      - questa tecnica rende molto più veloce il sollievo del router che hanno per primi i problemi di congestione
      - richiede più spazio di buffer nei router che si trovano sul percorso che va dall'host originario a quel router
- load shedding (caduta di carico)
  - tecnica di eliminazione dei pacchetti intrapresa dai router inondati da troppi pacchetti
  - il termine deriva dal mondo della generazione dell'energia elettrica: si oscurano intenzionalmente certe aree per evitare il collasso dell'intera rete
  - la scelta del pacchetto da scartare può dipendere dalle applicazioni in esecuzione, esistono diversi criteri:
    - wine (vino)
      - il vecchio pacchetto è più importante del nuovo
      - si tenderà ad eliminare gli ultimi pacchetti della sequenza
      - es: trasferimento file
    - milk (latte)
      - il nuovo pacchetto è più importante del vecchio
      - si tenderà ad eliminare i primi pacchetti della sequenza
      - es: trasmissioni multimediali in tempo reale
    - cooperazione dei trasmettitori
      - per alcune applicazioni alcuni pacchetti sono più importanti di altri
      - esempi:
        
        algoritmi di compressione video (che trasmettono periodicamente un keyframe)
        
        documento contenente testo ed immagini (la perdita di qualche riga di pixel dell'immagine è meno grave della perdita di una riga di testo)
  - le applicazioni devono contrassegnare i loro pacchetti in classi di priorità
  - i router scarteranno i pacchetti a partire da quelli con priorità minore
  - per evitare che le applicazioni usino tutte la massima priorità si utilizzano degli incentivi per le priorità inferiori:
    - i pacchetti a bassa priorità possono essere meno costosi di quelli ad alta priorità
    - si può consentire ai trasmittenti di inviare i pacchetti ad alta priorità solo in condizioni di basso carico (all'aumentare del carico, i pacchetti potrebbero essere scartati)
    - si può consentire agli host di superare i limiti specificati nell'accordo negoziato durante l'impostazione del circuito virtuale (es: utilizzo di una banda maggiore di quella consentita) a condizione che si trasmetta tutto il traffico in eccesso a bassa priorità
  - RED (Random Early Detection, Floyd and Jacobson - 1993)
    - celebre algoritmo utilizzato per scartare i pacchetti prima che tutto lo spazio del buffer sia esaurito
    - nelle reti cablate la perdita dei pacchetti è causata più che altro dall'esaurimento dei buffer e non dagli errori di trasmissione
    - per decidere quando iniziare a scartare, i router mantengono una media mobile delle lunghezze delle code
    - la linea è considerata congestionata quando la lunghezza media della coda su una linea supera la soglia di guardia
    - il router scarta i pacchetti senza rendere nota l'operazione (per non peggiorare la congestione), la sorgente noterà l'assenza dell'acknowledgement e rallenterà il flusso in considerazione del fatto che i pacchetti persi sono causati generalmente da congestioni ed eliminazioni
    - questo approccio non può essere utilizzato nelle reti wireless, dove la maggior parte delle perdite è causata dal rumore presente nel collegamento aereo
- controllo del jitter (controllo del tremolio)
  - jitter
    - variazione (deviazione standard) nel tempo di arrivo dei pacchetti
  - per applicazioni come la trasmissione di flussi audio e video, è essenziale che il tempo di transito dei pacchetti sia costante
  - l'intervallo di jitter scelto dovrà tener conto del tempo di transito a velocità luce e dal ritardo minimo causato dai router
  - funzionamento:
    - i router controllano di quanto i pacchetti sono in ritardo o in anticipo rispetto alla loro programmazione
    - aggiornano le informazioni del pacchetto sui tempi di consegna
    - i router spediscono il più velocemente possibile i pacchetti in ritardo e trattengono quelli in anticipo (diminuendo così il jitter)
  - in alcune applicazioni è possibile eliminare il jitter memorizzando i dati in un buffer nel computer ricevente (es: video on demand), tale bufferizzazione non è applicabile a trasmissioni real-time (es: videoconferenza, telefonate)

qualità del servizio (QoS)

lo sviluppo di reti multimediali ha richiesto sforzi significativi per garantire la qualità del servizio attraverso architetture di protocollo e di rete

requisiti

flusso
- flusso di pacchetti diretto da una sorgente ad una destinazione
- in una sottorete orientata alle connessioni tutti i pacchetti che appartengono ad un flusso seguono lo stesso percorso
QoS (Quality of Service)
- qualità del servizio richiesta dal flusso
- è caratterizzata da quattro parametri primari del flusso:
  - affidabilità
  - ritardo
  - jitter
  - banda

rigidità dei requisiti relativi alla QoS

applicazione	affidabilità	ritardo	jitter	banda
posta elettronica	alta	bassa	bassa	bassa
trasferimento file	alta	bassa	bassa	media
accesso al web	alta	media	bassa	media
login remoto	alta	media	media	bassa
audio a richiesta	bassa	bassa	alta	media
video a richiesta	bassa	bassa	alta	alta
telefonia	bassa	alta	alta	bassa
videoconferenza	bassa	alta	alta	alta

nelle applicazioni che richiedono un'alta affidabilità (prime quattro), nessun bit può essere perso, quindi ad ogni pacchetto verrà aggiunto un checksum di verifica

le reti ATM classificano i flussi in quattro ampie categorie a seconda delle QoS richieste:
- 1. velocità costante
  - tenta di simulare un cavo fornendo una banda uniforme ed un ritardo uniforme
  - è utilizzata per la telefonia
- 2. velocità variabile in tempo reale
  - è utilizzata per la videoconferenza compressa
- 3. velocità variabile non in tempo reale
  - è utilizzata per video on demand (video trasmessi su Internet)
- 4. velocità disponibile
  - è utilizzata per il trasferimento dei file e la posta elettronica

tecniche per ottenere una buona QoS
- nessuna tecnica da sola è in grado di fornire QoS efficiente e sicura in modo ottimo
- nella pratica si utilizzano varie tecniche combinate:
  - sovradimensionamento
    - consiste nel fornire ai router un'elevata capacità in termini di spazio di buffer e banda, così che i pacchetti possano transitare con facilità
    - questa tecnica è utilizzata nei sistemi telefonici dove la capacità è talmente elevata da poter soddisfare sempre la domanda
  - utilizzo dei buffer
    - i flussi possono essere memorizzati dal dispositivo ricevente in un buffer prima di essere consegnati
    - l'archiviazione nei buffer non influenza né l'affidabilità né la banda ma aumenta il ritardo ed elimina il jitter (ottimo per trasmissioni audio e video, i pacchetti possono essere rimossi dal buffer ad intervalli uniformi garantendo una riproduzione fluida)
  - traffic shaping (modellatura del traffico)
    - tecnica che fluidifica il traffico (regola la velocità media della trasmissione dati) sul lato server invece che sul lato client
    - è utilizzato per far fronte al problema del ritardo introdotto dai buffer (inaccettabile durante una videoconferenza)
    - service level agreement (accordo sul livello di servizio)
      - accordo stipulato durante l'impostazione della connessione tra l'utente e la sottorete (cliente ed operatore di telecomunicazioni) su un particolare modello di traffico (su una forma) per quel circuito
      - fintanto che il cliente si attiene alla sua parte dell'accordo, l'operatore di telecomunicazioni promette di consegnare tutti i dati in modo tempestivo
    - il traffic shaping riduce la congestione ed aiuta l'operatore a tener fede alle sue promesse
  - algoritmo leaky bucket (secchio che perde, Turner - 1986)
    - principio:
      - in un secchio bucato, qualunque sia la velocità di ingresso dell'acqua, l'eflusso avrà una velocità costante ρ quando ci sarà acqua nel secchio, ed avrà una velocità 0 quando il secchio sarà vuoto, l'acqua aggiunta al secchio pieno si riverserà all'esterno andando persa
    - è un sistema di accodamento a singolo server con tempo di servizio costante
    - ogni host è collegato alla rete da un'interfaccia che contiene un leaky bucket, ossia una coda interna finita
    - un pacchetto in ingresso viene aggiunto alla coda se c'è spazio, altrimenti viene scartato
    - l'host è autorizzato ad inserire nella rete un solo pacchetto per ogni ciclo di clock
    - questo meccanismo trasforma un flusso irregolare di pacchetti proveniente dai processi dell'utente dell'host in un flusso regolare di pacchetti immessi nella rete, appianando i picchi e riducendo enormemente le possibilità di congestioni
    - questa configurazione può essere costruita nell'interfaccia hardware o simulata nel sistema operativo dell'host
    - se i pacchetti hanno tutti la stessa dimensione (es. celle ATM) l'algoritmo può essere usato così come descritto
    - leaky bucket a conteggio di byte
      - se si usano pacchetti di dimensione variabile, è meglio consentire un numero fisso di byte per ogni ciclo di clock
      - per ogni ciclo un contatore è inizializzato ad n
      - se il primo pacchetto della coda ha meno byte del valore corrente del contatore, allora viene trasmesso ed il contatore viene decrementato di quel numero di byte
      - i pacchetti aggiuntivi possono essere trasmessi fintanto che il valore del contatore è abbastanza alto
      - quando il contatore scende sotto la lunghezza del pacchetto successivo nella coda, la trasmissione s'interrompe fino al ciclo di clock successivo, quando il conteggio dei byte residui è azzerato ed il flusso può riprendere
    - può essere utilizzato anche per regolarizzare il traffico tra i router
  - algoritmo token bucket
    - impone un rigido modello di output a velocità media, che non segue la variabilità del traffico
    - permettere all'output di accelerare un po' quando arrivano grandi raffiche di dati (può generare flussi di output meno regolari e dare una risposta più veloce a picchi improvvisi in ingresso)
    - contiene token generati (e distrutti) da un clock ogni ΔT secondi
    - una variabile conta il numero di token
    - perché possa essere trasmesso, un pacchetto deve catturare e distruggere un token (decremento del contatore)
    - quando il contatore raggiunge lo zero, nessun pacchetto può essere trasmesso
    - permette agli host inattivi di risparmiare permessi in modo da inviare successivamente grandi raffiche di dati composte da un massimo di n pacchetti (n = dimensione massima del secchio)
    - quando il secchio si riempie completamente vengono gettati via i token (capacità di trasmissione) senza scartare i pacchetti
    - la trasmissione di raffiche è permessa solo se non superano una lunghezza massima prefissata
      - C + ρS = MS
      - C [byte] : capacità del token bucket
      - ρ [byte/sec] : velocità di arrivo dei token
      - S [sec] : lunghezza della raffica
      - M [byte/sec] : velocità di output massima
    - token bucket a conteggio di byte
      - variante in cui ogni token rappresenta il diritto ad inviare non un pacchetto ma k byte
      - un pacchetto può essere trasmesso solo se è disponibile un numero di token sufficiente a coprire la sua lunghezza espressa in byte
      - i token frazionari sono utilizzati per un uso futuro
      - il contatore è incrementato di k byte ogni ΔT ed è decrementato della lunghezza di ogni pacchetto trasmesso
    - problema potenziale:
      - consente di trasmettere grandi raffiche di dati anche se l'intervallo massimo della raffica può essere regolato selezionando attentamente ρ ed M
      - spesso si desidera ridurre la velocità di picco senza tornare al basso valore del leaky bucket originale
      - si può ottenere un traffico più uniforme inserendo un leaky bucket dopo il token bucket
        
        la velocità del leaky bucket dovrebbe essere più alta di quella di ρ del token bucket ma più bassa della velocità massima della rete
    - può essere utilizzato anche per regolarizzare il traffico tra i router, in questo caso un'interruzione della trasmissione può far perdere i dati
  - prenotazione delle risorse
    - affinchè l'informazione relativa al traffic shaping possa essere utilizzata efficacemente, è implicitamente necessario che tutti i pacchetti di un flusso seguano lo stesso percorso
    - una volta definito il percorso del flusso, diventa possibile prenotare lungo tutto il tracciato le risorse che garantiscono la disponibilità della capacità necessaria:
      - 1. banda
        
        è la risorsa più ovvia
        
        prenotare la banda significa non sovraccaricare alcuna linea di output
      - 2. spazio del buffer
        
        se non è disponibile alcun buffer il pacchetto viene scartato perché non è possibile memorizzarlo
        
        per una buona QoS alcuni buffer possono essere dedicati ad un flusso specifico
      - 3. cicli di CPU
        
        si tratta di una risorsa limitata
        
        l'elaborazione di un pacchetto consuma cicli di CPU del router, perciò un apparecchio può elaborare solo un certo numero di pacchetti al secondo
  - controllo di ammissione
    - quando un flusso che è ben modellato e può idealmente seguire un singolo percorso, viene offerto ad un router, questo deve decidere, in base alla propria capacità ed al numero di impegni già presi con altri flussi, se accettare il nuovo flusso o no
    - è necessario un sistema di descrizione dei flussi per permettere al router una corretta valutazione
    - specifica di flusso
      - insieme di parametri specifici che possono essere utilizzati nella negoziazione del flusso
      - in genere il trasmittente (es: server che distribuisce video) produce una specifica di flusso per proporre i parametri da utilizzare
      - quando la specifica si propaga lungo il percorso ogni router la esamina e modifica i parametri in base alle necessità (le modifiche possono solo ridurre il flusso e non aumentarlo)
      - quando la specifica arriva a destinazione, i parametri possono essere fissati
      - più la specifica di flusso è stretta, più è utile ai router
      - esempio di specifica di flusso:
        
        token bucket rate [byte/sec]
        
        numero di byte al secondo immessi nel secchio
        
        rappresenta la velocità massima della sorgente, mediata su un lungo intervallo
        
        token bucket size [byte]
        
        dimensione del secchio espressa in byte
        
        peak data rate [byte/sec]
        
        velocità di trasmissione massima tollerata, anche per brevi intervalli di tempo
        
        dimensione minima del pacchetto [byte]
        
        include le intestazioni degli strati network e di trasporto (es: TCP e IP)
        
        è importante perchè l'elaborazione del pacchetto richiede sempre un tempo prefissato indipendente dalla lunghezza
        
        dimensione massima del pacchetto [byte]
        
        è importante a causa delle limitazioni interne della rete che non possono essere superate
  - routing proporzionale
    - metodo semplice che consiste nel dividere il traffico in parti uguali, o proporzionali alla capacità dei collegamenti diretti verso l'esterno
    - serve a non sovraccaricare un unico percorso
  - pianificazione dei pacchetti
    - se un router sta gestendo più flussi, c'è il pericolo che uno di questi si accaparri troppa capacità lasciando gli altri senza risorse
    - host aggressivi potrebbero monopolizzare la capacità dei router riducendo la QoS degli altri host
    - per ovviare a questi scenari si utilizzano degli algoritmi di pianificazione dei pacchetti:
      - accodamento equo (fair queuing, Nagle, 1987)
        
        attribuisce ai router code separate per ogni linea di trasmissione, una per ogni flusso
        
        quando una linea si libera, il router esamina le code in modo round robin prendendo il primo pacchetto della coda successiva
        
        con n host che concorrono per una data linea di trasmissione, ogni host riesce a trasmettere uno dei suoi pacchetti ogni n pacchetti
        
        l'invio di un numero maggiore di pacchetti non migliora questa frazione
        
        questo algoritmo offre più banda agli host che usano pacchetti grandi
      - variante accodamento equo (Demers et al., 1990)
        
        il round robin è fatto in modo da simulare una sequenza byte per byte invece che pacchetto per pacchetto
        
        esamina ripetutamente le code un byte alla volta, fino a quando non trova il ciclo di clock finale di ogni pacchetto
        
        i pacchetti sono quindi ordinati in base al loro completamento e vengono trasmessi esattamente in quest'ordine
        
        questo algoritmo da a tutti gli host la stessa priorità
      - accodamento equo pesato
        
        è una variante del metodo precedente ed è largamente utilizzato
        
        talvolta il peso è uguale al numero di flussi trasmessi da un computer, perciò ogni processo riceve la stessa banda
servizi integrati (algoritmi basati sui flussi)
- collezioni di circa 20 RFC (2205-2210) elaborati dall'IETF tra il 1995 ed il 1997
- il lavoro era rivolto alle applicazioni unicast e multicast
- consideriamo il multicast perché è possibile considerare l'unicast come un caso speciale del multicast
- in molte applicazioni multicast i gruppi possono cambiare dinamicamente l'appartenenza, rendendo così poco funzionale l'approccio che riserva in anticipo la banda ai trasmettitori.
- RSVP (Resource reSerVation Protocol)
  - è il protocollo IETF principale per l'architettura dei servizi integrati
  - è utilizzato per il controllo di congestione per il multicasting
  - si occupa delle prenotazioni
  - consente a più trasmettitori di trasmettere a diversi gruppi di ricevitori
  - permette a singoli ricevitori di cambiare canale liberamente
  - ottimizza l'uso della banda eliminando contemporaneamente le congestioni
  - funzionamento (forma semplice):
    - il protocollo utilizza il routing multicast basato su strutture di tipo spanning tree
    - ogni gruppo riceve un indirizzo di gruppo
    - per trasmettere ad un gruppo, un trasmettitore inserisce l'indirizzo del gruppo nei suoi pacchetti (in tal modo l'algoritmo di routing multicast standard costruisce uno spanning tree che copre tutti i membri del gruppo)
    - l'unica differenza rispetto alla normale trasmissione multicast è rappresentata da qualche informazione in più, trasmessa periodicamente in modalità multicast al gruppo per dire ai router lungo la struttura ad albero di conservare alcune strutture dati nella loro memoria
    - per avere una migliore ricezione ed eliminare le congestioni, tutti i ricevitori di un gruppo possono inviare al trasmettitore un messaggio di prenotazione attraverso la struttura ad albero
    - il messaggio è propagato usando l'algoritmo di reverse path forwarding
    - ad ogni salto il router prende nota della prenotazione, e riserva la banda necessaria
    - se non è disponibile una banda sufficiente, il dispositivo risponde comunicando il fallimento
    - quando il messaggio torna alla sorgente, la banda è stata prenotata su tutto il percorso che collega il trasmettitore al ricevitore che ha inviato la richiesta di prenotazione lungo lo spanning tree
    - quando fa una prenotazione, il ricevitore può (facoltativamente) specificare una o più sorgenti dalle quali desidera ricevere i dati; può anche specificare se queste scelte sono fisse o possono essere cambiate in corsa
    - due o più ricevitori sono configurati per condividere un percorso solo se entrambi accettano di non cambiare le risorse in un secondo tempo
    - una volta che ha riservato la banda, il ricevitore può passare ad un'altra sorgente e mantenere la parte di percorso esistente che è valida per la nuova sorgente
  - offre una buona QoS ma è poco utilizzato per via degli svantaggi:
    - richiedono la preventiva impostazione di ogni flusso
    - mantengono nei router uno stato interno per ogni flusso (rendendo il sistema vulnerabile)
    - le modifiche apportate ai router sono considerevoli e richiedono complessi scambi tra router
servizi differenziati (DS, differentiated services, RFC 2474 - 2475)
- approccio IETF più semplice di RSVP, mirato alla QoS
- può essere implementato per lo più localmente in ogni router
- non richiede l'impostazione anticipata, nessuna prenotazione di risorse e nessuna pesante negoziazione punto-punto per ogni flusso
- l'approccio è chiamato: qualità di servizio basata sulle classi
- i DS possono essere offerti da un insieme di router che costituiscono un dominio amministrativo (ISP o compagnia telefonica)
- l'amministrazione definisce una serie di classi di servizio e le corrispondenti regole di inoltro
- se un cliente firma un contratto per DS, i pacchetti del cliente che entrano nel dominio possono contenere un campo type of service (tipo di servizio)
- alcune classi hanno diritto ad un servizio migliore di altre (servizio premium)
- a causa del fatto che spesso i pacchetti sono inoltrati tra sottoreti gestite da operatori diversi, IETF sta cercando di definire classi di servizio indipendenti dalle reti:
  - inoltro accelerato (expedited forwarding, RFC 3246)
  - inoltro sicuro (assured forwarding, RFC 2597)
MPLS (MultiProtocol Label Switching, RFC 3031)
- tecnica di comunicazione che usa come indice della tabella di routing un'etichetta presa dal pacchetto
- aggiunge davanti ad ogni pacchetto un'etichetta che consente ai router di instradare i dati in base all'etichetta, invece che in base all'indirizzo di destinazione

internetworking (collegamento tra reti)
- esistono molte reti diverse, tra cui LAN, MAN e WAN, inoltre esistono numerosi protocolli utilizzati comunemente in ogni strato
- internet
  - si forma attraverso l'unione tra due o più reti
- la diversità delle reti (e dei protocolli) è dovuto sia ad aspetti funzionali che economici (commerciali)
- differenze tra le reti nello strato network
  - sono le differenze che creano le maggiori difficoltà di comunicazione:
    - servizio offerto
      - orientato alle connessioni o pure no
    - protocolli
      - IP, IPX, SNA, ATM, MPLS, AppleTalk, ...
    - indirizzamento
      - piatto (802) o gerarchico (IP)
    - trasmissione multicast
      - presente o assente (vale anche per la modalità broadcast)
    - dimensionamento del pacchetto
      - ogni rete supporta una dimensione massima particolare
    - qualità del servizio (QoS)
      - presente o assente; molti tipi diversi
    - gestione degli errori
      - inoltro affidabile, ordinato o non ordinato
    - controllo di flusso
      - sliding window, controllo della velocità, altro o nessuno
    - controllo della congestione
      - secchio bucato, secchio a token, RED, pacchetti di interruzione, ...
    - sicurezza
      - regole di riservatezza, codifica dei dati, ...
    - parametri
      - scadenze diverse, specifiche di flusso, ...
    - conteggio dei costi
      - in base al tempo di connessione, per pacchetto, per byte, nessuna
- connessione tra le reti
  - le reti possono essere collegate tra loro attraverso dispositivi di tipo diverso a seconda degli strati:
    - fisico (physical layer)
      - ripetitori o hub
        
        apparecchi che spostano i bit da una rete ad un'altra identica, senza modifiche
        
        sono prevalentemente dispositivi analogici che si limitano a rigenerare il segnale trasmesso
    - collegamento (data link)
      - bridge e switch
        
        possono accettare frame, esaminare gli indirizzi MAC ed inoltrare i frame su reti diverse eseguendo una limitata conversione di protocollo
        
        trasportano i frame interi sulla base dei loro indirizzi MAC
        
        non devono comprendere il protocollo dello strato network per commutare i pacchetti
    - rete (network)
      - router
        
        se gli strati di rete sono differenti, il router può essere capace di tradurre i formati dei pacchetti, sebbene la traduzione del pacchetto oggi sia sempre più rara
        
        i pacchetti vengono estratti dai frame e gli indirizzi dei pacchetti sono utilizzati per decidere dove inviarli
      - router multiprotocollo
        
        router che può gestire più protocolli
    - trasporto (transport)
      - gateway
        
        possono interfacciare due connessioni di trasporto
    - applicazione (application)
      - gateway applicativi
        
        traducono la semantica dei linguaggi
- circuiti virtuali concatenati
  - in passato la maggior parte delle reti (pubbliche) era orientata alle connessioni (frame relay, SNA, 802.16 e ATM ancora lo sono)
  - l'importanza crescente delle reti multimediali rende probabile un ritorno alle soluzioni orientate alle connessioni
  - con questo tipo di circuiti è più facile garantire la qualità di servizio
  - funzionamento:
    - viene impostata la connessione all'host di una rete lontana, seguendo le consuete modalità
    - la sottorete si accorge che la destinazione è remota e costruisce un circuito virtuale diretto al router più vicino alla rete di destinazione; quindi crea un circuito virtuale da quel router ad un gateway esterno (router multiprotocollo)
    - il gateway registra l'esistenza del circuito virtuale nelle sue tabelle e procede costruendo un'altro circuito virtuale ad un router nella sottorete successiva
    - il processo si ripete fino al raggiungimento dell'host di destinazione
    - quando i pacchetti iniziano a scorrere lungo il percorso, ogni gateway inoltra i pacchetti in arrivo, convertendo i formati dei pacchetti ed i numeri di circuito virtuale in base alle necessità
    - tutti i pacchetti di dati devono attraversare la stessa sequenza di gateway, quindi i pacchetti di un flusso non sono mai riordinati dalla rete
  - la caratteristica essenziale è che una sequenza di circuiti virtuali è impostata dalla sorgente, attraverso uno o più gateway, fino alla destinazione
  - ogni gateway gestisce le tabelle che indicano i circuiti virtuali che passano attraverso il dispositivo, le destinazioni degli instradamenti ed i numeri dei nuovi circuiti virtuali
  - questo schema funziona meglio quando tutte le reti hanno all'incirca le stesse proprietà (la concatenazione modifica pesantemente la natura del servizio)
  - i circuiti virtuali concatenati sono comuni anche nello strato di trasporto
    - è possibile costruire un canale di bit usando (per esempio) SNA che termina in un gateway, ed una connessione TCP che va da tale gateway al successivo
    - si può quindi realizzare un circuito virtuale punto-punto che attraversa reti e protocolli diversi
  - non è possibile impostare questo metodo se una delle sottoreti coinvolte è una rete a datagrammi inaffidabile
  - presenta gli stessi vantaggi e svantaggi dei circuiti virtuali usati in un'unica sottorete
- collegamento tra reti senza connessione (datagramma)
  - con lo sviluppo di Internet, le reti a datagrammi sono diventate la soluzione più utilizzata
  - l'unico servizio che lo strato network offre allo strato di trasporto è la capacità di introdurre datagrammi nella sottorete, sperando per il meglio
  - non esiste alcuna nozione di circuito virtuale, e tanto meno di concatenazione di circuiti
  - non richiede che tutti i pacchetti che appartengono ad una connessione debbano attraversare la stessa sequenza di gateway
  - una decisione di routing è presa separatamente per ogni pacchetto, magari in base al traffico al momento della trasmissione del pacchetto
  - questa strategia può utilizzare più percorsi e perciò può ottenere una banda maggiore rispetto al modello basato sui circuiti virtuali concatenati
  - non esiste alcuna garanzia che i pacchetti raggiungano la destinazione in ordine (potrebbero anche non arrivare)
  - se ogni rete utilizza un protocollo di strato network diverso, un pacchetto proveniente da una rete non può passare in un'altra rete
  - un routing multiprotocollo potrà eseguire una conversione corretta solo se i formati saranno molto simili ed utilizzeranno gli stessi campi di informazioni
  - l'indirizzamento tra reti diverse e un problema ancora più importante
    - tra reti diverse può cambiare sia il tipo di indirizzamento sia ciò che è indirizzabile
  - Internet utilizza un pacchetto "internet" universale facendo in modo che tutti i router lo riconoscano (approccio IP)
  - far accettare a tutti un singolo formato è difficile, se le aziende pensano che avere un formato proprietario garantisce un vantaggio commerciale
  - presenta gli stessi vantaggi e svantaggi di un'unica sottorete a datagrammi
  - in una internet si possono adottare diversi algoritmi di routing adattativi (così come in una singola rete a datagramma)
  - l'approccio basato su datagrammi può essere utilizzato su sottoreti che non usano al loro interno circuiti virtuali
- tunnelling
  - tecnica che risolve il caso particolare in cui l'host sorgente e l'host destinazione si trovano su reti dello stesso tipo e sono separati da una rete diversa
  - funzionamento (LAN Ethernet TCP/IP - WAN ATM - LAN Ethernet TCP/IP)
    - per inviare un pacchetto IP all'host 2, l'host 1 costruisce un pacchetto contenente l'indirizzo IP dell'host 2
    - inserisce il pacchetto in un frame Ethernet indirizzato al router multiprotocollo della rete 1 ed immette i dati nella Ethernet
    - quando il router multiprotocollo 1 riceve il frame, rimuove il pacchetto IP, lo inserisce nel carico utile dello strato network della WAN ed indirizza quest'ultimo all'indirizzo WAN del router multiprotocollo 2
    - quando arriva a destinazione, il router multiprotocollo 2 rimuove il pacchetto IP e lo trasmette all'host 2 in un frame Ethernet
  - la rete WAN di interconnessione può essere vista come un grande tunnel che si estende da un router multiprotocollo all'altro
  - il pacchetto IP viaggia da un'estremità all'altra del tunnel incapsulato in un frame
  - in pratica l'intero percorso compreso tra i due router funziona come una linea seriale
- routing in una internetwork
  - è simile al routing eseguito in una singola sottorete ma con alcune complicazioni in più
  - autonomous system (AS)
    - nome dato alle reti che compongono l'internetwork e che indica l'indipendenza di ogni rete dalle altre
  - protocollo di gateway interno (IGP - Interior Gateway Protocol)
    - algoritmo di routing usato da un AS al proprio interno
    - diversi AS possono utilizzare diversi IGP
    - può anche essere gerarchico, in particolare quando le dimensioni dell'AS sono considerevoli
  - protocollo di gateway esterno (EGP - Exterior Gateway Protocol)
    - algoritmo che si usa per gestire il routing fra diversi AS
    - in questo scenario EGP è tipicamente l'algoritmo di routing che riguarda i router multiprotocollo
    - EGP deve spesso tener conto di particolari situazioni:
      - specifiche leggi nazionali (es: divieto di far transitare dati sul suolo di una nazione ostile)
      - il costo di transito può variare da rete a rete
      - la QoS può cambiare da rete a rete
  - funzionamento (esempio):
    - un classico pacchetto internet nasce nella propria LAN, dove viene indirizzato al router multiprotocollo locale (nell'intestazione dello strato MAC)
    - raggiunto il router, il codice dello strato network decide, usando le sue tabelle di routing, a quale router multiprotocollo deve essere inoltrato il pacchetto
    - se quel router può essere raggiunto usando il protocollo di rete nativo del pacchetto, il pacchetto è inoltrato direttamente, altrimenti i dati vengono trasmessi via tunnelling, ossia incapsulati nel protocollo richiesto dalla rete intermedia
    - questo processo si ripete fino a quando il pacchetto non raggiunge la rete di destinazione
- frammentazione
  - tecnica implementata nei gateway per suddividere i pacchetti in frammenti così piccoli da poter essere trasmessi in reti che non supportano pacchetti della dimensione originale
  - ogni rete impone una dimensione massima ai suoi pacchetti che può dipendere da:
    - 1. dall'hardware (come nel caso del frame Ethernet)
    - 2. dal sistema operativo (per esempio, tutti i buffer sono grandi 512 byte)
    - 3. dai protocolli (numero di bit nel campo che definisce la lunghezza del pacchetto)
    - 4. dalla conformità con qualche standard internazionale
    - 5. dal desiderio di ridurre di un certo livello le ritrasmissioni causate dagli errori
    - 6. dal desiderio di impedire ad un pacchetto di occupare il canale per troppo tempo
  - i carichi utili massimi per un pacchetto variano da 48 byte (celle ATM) a 65515 (pacchetti IP)
  - la difficoltà maggiore è rappresentata dalla ricomposizione dei frammenti in pacchetti, che si effettua utilizzando due opposte strategie:
    - 1. frammentazione trasparente (usata da ATM)
      - la frammentazione che è eseguita da una rete "a pacchetti piccoli" viene resa trasparente ad ogni altra rete situata più a valle lungo il percorso che il pacchetto deve attraversare per raggiungere la destinazione
      - la rete a pacchetti piccoli ha gateway (router specializzati) che si interfacciano con le altre reti
      - quando riceve un pacchetto troppo grande, il gateway suddivide i dati in frammenti
      - ogni frammento è indirizzato allo stesso gateway in uscita, dove i pezzi sono riassemblati
      - in tal modo il passaggio attraverso la rete a pacchetti piccoli diventa trasparente (invisibile alle altre reti)
      - nel mondo ATM la frammentazione è chiamata segmentazione (cambiano solo alcuni dettagli)
      - problemi/svantaggi:
        
        il gateway di uscita deve sapere quando ha ricevuto tutti i pezzi, è quindi necessario un campo contatore o un campo di fine pacchetto
        
        tutti i pacchetti devono seguire lo stesso percorso per poter uscire dallo stesso gateway, quindi le prestazioni possono diminuire per l'impossibilità di viaggiare parallelamente su strade diverse
        
        il tempo di elaborazione richiesto per frammentare e ricomporre ripetutamente un pacchetto che attraversa diverse reti a pacchetti piccoli
    - 2. frammentazione non trasparente (usata da IP)
      - si astiene dal ricombinare i frammenti ad ogni gateway intermedio
      - una volta che il pacchetto è stato suddiviso, ogni frammento è trattato come se fosse un pacchetto originale
      - la ricostruzione avviene unicamente dall'host di destinazione
      - problemi/svantaggi:
        
        richiede che ogni host sia in grado di ricostruire i pacchetti
        
        se si frammenta un pacchetto molto grande il tempo di elaborazione totale aumenta perchè ogni frammento deve avere un'intestazione (l'overhead rimane per tutta la durata del viaggio)
      - vantaggi:
        
        permette di utilizzare più gateway di uscita e quindi consente di ottenere prestazioni migliori (se si utilizza il modello a circuiti virtuali concatenati, questo vantaggio non è di alcuna utilità)
      - numerazione dei pacchetti
        
        gerarchico
        
        i pacchetti vengono numerati in maniera gerarchica (ad albero) così da poter essere frammentati a più riprese (es: 0 -> 0.0, 0.1, 0.2, ... -> 0.0.0, 0.0.1, 0.0.2, ...)
        
        se nell'intestazione sono stati riservati campi sufficienti al caso peggiore e se non vengono generati duplicati, questo schema assicura la possibilità di riassemblare correttamente tutti i frammenti una volta giunti a destinazione, qualunque sia il loro ordine di arrivo
        
        se anche solo una delle reti perde o scarta dei pacchetti, sono necessarie ritrasmissioni end-to-end che influenzano il sistema di numerazione (i frammenti ritrasmessi potrebbero seguire strade diverse ed essere ulteriormente frammentati)
        
        pacchetto minimo
        
        il protocollo di comunicazione stabilisce una dimensione di frammento elementare così piccolo da poter passare attraverso tutte le reti
        
        l'ultimo frammento può essere più piccolo del frammento elementare
        
        un pacchetto internet può contenere diversi frammenti per motivi di efficienza
        
        l'intestazione internet deve indicare il numero di pacchetto originale ed il numero del (primo) frammento elementare contenuto nel pacchetto
        
        ci deve essere anche un bit che indica che l'ultimo frammento elementare contenuto nel pacchetto internet è l'ultimo del pacchetto originale
        
        questo approccio richiede due campi di sequenza nell'intestazione internet:
        
        il numero di pacchetto originale
        
        il numero del frammento
        
        esiste un compromesso tra la dimensione del frammento elementare ed il numero di bit del numero di frammento
        
        il limite massimo è rappresentato da un frammento elementare grande come un singolo bit o byte, con il numero del frammento che rappresenta l'offset del bit o del byte dentro il pacchetto originale
        
        alcuni protocolli internet considerano l'intera trasmissione su un circuito virtuale come un gigantesco pacchetto, così che ogni frammento contiene il numero di byte assoluto del primo byte dentro il frammento
- firewall
  - sistema di sicurezza per proteggere le LAN connesse ad Internet da accessi abusivi
  - attraverso di esso passano tutte le comunicazioni da e verso l'esterno
  - genericamente implementa due router che fanno il filtraggio dei pacchetti (uno per quelli in ingresso ed uno per quelli in uscita) ed un gateway applicativo posto tra di essi
  - packet filter (filtro di pacchetti)
    - è un router standard equipaggiato con funzionalità extra
    - ispeziona ogni pacchetto in entrata o in uscita
    - i pacchetti sospetti vengono scartati
    - sono tipicamente gestiti attraverso delle tabelle configurate dall'amministratore di sistema
      - è possibile definire diverse regole che riguardano le sorgenti e le destinazioni (indirizzo IP e porta) e cosa fare dei pacchetti che vanno o vengono da altre macchine
      - bloccare i pacchetti in uscita è più complesso di quelli in ingresso perchè spesso le applicazioni non si attengono agli standard
  - gateway applicativo
    - non riguarda più i singoli pacchetti ma opera sullo strato applicativo
    - è possibile per esempio esaminare i messaggi di posta e scartarli in base alle intestazioni o al contenuto
  - anche quando il firewall è configurato perfettamente, rimangono ancora molti problemi di sicurezza
  - esistono diversi metodi elusivi per "ingannare" il router, ad esempio:
    - cifrare dei documenti e spedirli come un'immagine JPEG
    - DoS (Denial od Service)
      - tentano di bloccare le funzionalità di certi siti, sommergendoli di richieste
      - ad esempio se si inviano dei pacchetti TCP SYN per stabilire delle connessioni e non si risponde, il sito manterrà allocato uno slot per ogni richiesta per alcuni secondi (fino al timeout)
      - se il numero di richieste è elevato il sito può bloccarsi completamente (la CPU della macchina attaccata sarà costretta a spendere tutto il tempo per gestire queste richieste)
    - DDoS (Distributed Denial od Service)
      - si istruiscono centinaia di macchine in tutto il mondo per portare avanti un attacco DoS
lo strato network in Internet
- principi fondamentali di sviluppo dell'architettura Internet (RFC 1958):
  - 1. assicurarsi che funzioni
    - non ultimare il progetto o lo standard fino a quando diversi prototipi non hanno comunicato con successo gli uni con gli altri
  - 2. mantenerlo semplice
    - nel dubbio si utilizzi la soluzione più semplice (rasoio di Occam, IV sec.)
    - le funzionalità non strettamente necessarie vanno eliminate, soprattutto se lo stesso effetto può essere ottenuto combinando altre caratteristiche
  - 3. fare scelte chiare
    - se la stessa cosa può essere fatta in modi diversi, sceglierne uno
  - 4. sfruttare la modularità
    - la modifica di un modulo non influenzerà gli altri
  - 5. aspettarsi l'eterogeneicità
    - l'architettura di rete deve essere semplice, generale e flessibile per adattarsi a diversi tipi di hardware, attrezzature di trasmissione ed applicazioni
  - 6. evitare opzioni e parametri statici
    - se i parametri sono inevitabili, invece di definire scelte fisse è meglio che il trasmettitore ed il ricevente concordino un valore
  - 7. mirare ad un buon progetto; non è necessario che sia anche perfetto
    - un buon progetto non va scartato solo perchè non gestisce alcuni misteriosi casi speciali
  - 8. essere rigorosi nella trasmissione e tolleranti nella ricezione
    - inviare solo pacchetti che si attengono rigorosamente agli standard
    - tentare di gestire anche i pacchetti in arrivo che non sono completamente compatibili
  - 9. pensare alla scalabilità
    - deve essere possibile distribuire il carico tra tutte le risorse disponibili
  - 10. considerare le prestazioni ed i costi
    - se una rete ha scarse prestazioni o costi oltraggiosi, nessuno la utilizzerà
- rete Internet
  - nello strato network, la rete Internet può essere vista come un insieme di sottoreti o Autonomuos Systems (AS) interconnessi
  - non esiste alcuna vera struttura, esistono solo molte dorsali principali formate da linee a larga banda e router veloci
  - alle dorsali si collegano le reti regionali (di livello intermedio), a cui si collegano le LAN di molte università, aziende ed ISP (Internet Service Provider)
  - il compito dello strato network è fornire un mezzo di tipo best effort (non garantito) per trasportare i datagrammi inviati da una sorgente ad una destinazione, senza tener conto della posizione delle macchine (che possono trovarsi su reti diverse) e dell'eventuale presenza di reti intermedie (poste tra le macchine)
  - funzionamento della comunicazione
    - lo strato di trasporto prende i flussi di dati e li divide in datagrammi
    - la dimensione dei datagrammi può essere di 64 KB ma solitamente non supera i 1500 byte (quindi coincide con quella del frame Ethernet)
    - ogni datagramma è trasmesso attraverso Internet, e magari viene frammentato in unità più piccole
    - quando alla fine tutti i pezzi raggiungono la macchina di destinazione, lo strato network ricostruisce il datagramma originale, che sarà passato allo strato di trasporto che lo inserisce nel flusso di input del processo ricevente
- protocollo IP (Internet Protocol)
  - è il protocollo dello strato network che tiene unita la rete Internet
    - è stato progettato pensando alla comunicazione tra reti
    - pacchetto IP (IPv4)
      - intestazione (header) [20 - 60 byte]
        
        è trasmessa in ordine big endian: da sinistra a destra, a partire dal bit di ordine più elevato del campo version
        
        sulle macchine little endian (Pentium) è necessario eseguire una conversione software sia in ricezione che in trasmissione
        
        è costituita da:
        
        parte fissa [20 byte]
        
        Version [4 bit]
        
        tiene traccia della versione del protocollo usato per il datagramma
        
        rende possibile le transizioni tra diverse versioni (es: da IPv4 a IPv6)
        
        IHL (Internet Header Length) [4 bit]
        
        lunghezza dell'intestazione espressa in parole (word) di 32 bit
        
        il valore minimo 5 si applica quando non sono presenti altre opzioni
        
        il valore massimo è 15 = 60 byte (20 parte fissa + 40 options e padding)
        
        ToS (Type of Service, tipo di servizio) [8 bit]
        
        ha leggermente cambiato il suo significato nel corso degli anni
        
        è utilizzato per indicare la classe di servizio di appartenenza del pacchetto che includono: quattro priorità di accodamento, tre probabilità di eliminazione e le classi storiche
        
        sono ammesse svariate combinazioni di affidabilità e velocità
        
        è spesso ignorato dai moderni router
        
        è/era costituito da:
        
        Precedence (priorità) [3 bit]
        
        111 = Network Control
        
        110 = Internetwork Control
        
        101 = CRITIC/ECP
        
        100 = Flash Override
        
        011 = Flash
        
        010 = Immediate
        
        001 = Priority
        
        000 = Routine
        
        D (Delay, ritardo) [1 bit]
        
        0 = Normal Delay
        
        1 = Low Delay
        
        T (Throughput, capacità) [1 bit]
        
        capacità di trasporto
        
        0 = Normal Throughput
        
        1 = High Throughput
        
        R (Reliability, affidabilità) [1 bit]
        
        0 = Normal Reliability
        
        1 = High Reliability
        
        M (Monetary cost, costo economico, aggiunto in RFC 1349) [1 bit]
        
        0 = Normal monetary cost
        
        1 = Minimize monetary cost
        
        - [1 bit]
        
        riservato per usi futuri, dovrebbe essere impostato a 0
        
        Total Length (lunghezza totale) [16 bit]
        
        indica la lunghezza totale del datagramma (intestazione e dati) misurata in byte (da 8 bit)
        
        al massimo può essere di 65535 byte
        
        Identification (identificazione) [16 bit]
        
        serve all'host di destinazione per determinare a quale datagramma appartiene il frammento appena arrivato
        
        tutti i frammenti di un datagramma contengono lo stesso valore identification
        
        R (Reserved) [1 bit]
        
        bit riservato, dovrebbe essere impostato a 0
        
        DF (Don't Fragment, non frammentare) [1 bit]
        
        0 = Fragment if necessary
        
        qualsiasi computer deve accettare frammenti con dimensione di 576 byte, ma può accettarne anche più brevi
        
        1 = Do not fragment
        
        indica ai router di non frammentare il pacchetto perchè la destinazione non è in grado di ricomporlo
        
        MF (More Fragments, più frammenti) [1 bit]
        
        0 = This is the last fragment
        
        ultimo frammento
        
        1 = More fragments follow this fragment
        
        tutti i frammenti tranne l'ultimo hanno questo bit impostato ad 1
        
        Fragment Offset (offset del frammento) [13 bit]
        
        indica la posizione del frammento nel datagramma corrente
        
        tutti i frammenti tranne l'ultimo devono essere multipli di 8 byte (frammento elementare)
        
        con 13 bit si possono avere al massimo 8192 frammenti per ogni datagramma
        
        la dimensione massima di un datagramma è 65536 byte (uno in più del campo total lenght)
        
        TTL (Time To Live, tempo di vita) [8 bit]
        
        contatore utilizzato per limitare la vita di un pacchetto
        
        il valore massimo è 255
        
        il valore consigliato è 64
        
        viene decrementato ad ogni salto
        
        quando il contatore raggiunge lo zero, il pacchetto viene scartato ed un pacchetto di avviso viene inviato all'host sorgente
        
        questo evita ai datagrammi di girare a vuoto per sempre
        
        Protocol (protocollo) [8 bit]
        
        indica quale processo di trasporto è in attesa di quei dati
        
        le possibilità sono svariate TCP, UDP, ...
        
        la numerazione dei protocolli è valida globalmente in Internet (RFC 1700)
        
        Header checksum (checksum dell'intestazione) [16 bit]
        
        verifica solo l'intestazione comprese le opzioni
        
        aiuta a rilevare errori generati da locazioni di memoria difettose nei router
        
        l'algoritmo somma tutte le mezze parole di 16 bit appena arrivate, usando l'aritmetica in complemento ad uno, e poi prende il complemento ad uno del risultato
        
        si suppone che questo campo sia zero all'arrivo
        
        deve essere ricalcolato ad ogni salto perchè almeno un campo cambia sempre (time to live)
        
        Source IP address (indirizzo sorgente) [32 bit]
        
        indirizzo IP della sorgente
        
        Destination IP address (indirizzo destinazione) [32 bit]
        
        indirizzo IP della destinazione
        
        Options (opzioni) [0 - n byte]
        
        questo campo era stato pensato come via di fuga per dare alle versione successive del protocollo la possibilità di includere informazioni non presenti nel progetto originale
        
        è riempito con multiply di 4 byte
        
        lista di opzioni di lunghezza variabile
        
        ogni opzione è costituita da:
        
        C (Copy flag, copia) [1 bit]
        
        indica se l'opzione va copiata in ogni frammento
        
        0 = Do not copy
        
        1 = Copy
        
        Class (classe) [2 bit]
        
        0 = Control
        
        1 = Reserved
        
        2 = Debugging and measurement
        
        3 = Reserved
        
        Option (opzione) [5 bits]
        
        indica il tipo di opzione secondo una tabella valida globalmente
        
        l'elenco delle opzioni si trova su http://www.iana.org/assignments/ip-parameters
        
        le cinque opzioni definite inizialmente sono:
        
        SEC (Security)
        
        indica il livello di segretezza delle informazioni
        
        SSR (Strict Source Route)
        
        definisce il percorso completo da seguire attraverso una sequenza di indirizzi IP
        
        LSR (Loose Source Route)
        
        costringe il pacchetto ad attraversare in ordine l'elenco dei router specificati
        
        RR (Record Route)
        
        costringe ogni router lungo il percorso ad aggiungere alle opzioni il proprio indirizzo IP
        
        TS (Time Stamp)
        
        costringe ogni router lungo il percorso ad aggiungere alle opzioni il proprio indirizzo IP e la data ed ora di elaborazione (32 bit)
        
        option lenght (lunghezza di opzione) [0 - 1 byte]
        
        campo opzionale che precede uno o più byte di dati
        
        option data (dati dell'opzione) [0 - n byte]
        
        specifica i dati dell'opzione
        
        Padding (riempimento) [0 - n bit]
        
        campo di lunghezza variabile per fare in modo che l'intestazione abbia un numero di bit multiplo di 32
      - dati (data) [0 - 65515 byte]
        
        contenuto del pacchetto IP
- indirizzi IP
  - ogni host e router di Internet ha un indirizzo IP che codifica il suo indirizzo di rete ed il suo numero di host
  - la combinazione è unica: in teoria, non possono esistere su Internet due macchine con lo stesso indirizzo IP
  - per evitare conflitti i numeri di rete sono gestiti da un'ente no profit chiamato ICANN (Internet Coporation for Assigned Names and Numbers)
  - tutti gli indirizzi IP sono lunghi 32 bit
  - sono rappresentabili in notazione decimale a punti
    - i 32 bit vengono divisi in gruppi di 4 byte (0 - 255), rappresentati in decimale e separati da punti
  - sono utilizzati nell'intestazione dei pacchetti IP
  - un indirizzo IP non si riferisce realmente ad un host ma ad una scheda di rete (un host con due schede può avere due indirizzi IP)
  - indirizzamento per classi
    - oggi non è più utilizzato ma in letteratura ci si riferisce spesso a questa suddivisione:
      - A [1.0.0.0 - 127.255.255.255] (/8)
        
        bit 0 = 0
        
        bit 1-7 = rete (max 128)
        
        bit 8-31 = host (max 16.000.000)
      - B [128.0.0.0 - 191.255.255.255] (/16)
        
        bit 0-1 = 10
        
        bit 2-15 = rete (max 16.384)
        
        bit 16-31 = host (max 64.000)
      - C [192.0.0.0 - 223.255.255.255] (/24)
        
        bit 0-2 = 110
        
        bit 3-23 = rete (max 2.000.000)
        
        bit 24-31 = host (max 256)
      - D [224.0.0.0 - 239.255.255.255]
        
        bit 0-3 = 1110
        
        bit 4-31 = indirizzi multicast (max 268.435.456)
      - E [240.0.0.0 - 255.255.255.255]
        
        bit 0-3 = 1111
        
        bit 4-31 = riservati per usi futuri
  - indirizzi speciali
    - 0 (0.0.0.0)
      - è utilizzato dagli host al momento del boot
    - 0 + host
      - gli indirizzi IP che hanno 0 come numero di rete si riferiscono alla rete corrente
    - -1 (255.255.255.255)
      - è utilizzato come indirizzo broadcast sulla rete locale (LAN)
    - rete + 1
      - gli indirizzi con un opportuno numero di rete e tutti 1 nel campo host permettono la trasmissione broadcast a LAN distanti collegati ad Internet
        
        questa funzionalità è spesso disabilitata dagli amministratori di rete
    - 127.xxx.yyy.zzz
      - sono riservati per prove di loopback
      - i pacchetti immessi su questi indirizzi non sono immessi nel cavo, ma elaborati localmente e trattati come pacchetti in arrivo
      - questo permette di inviare pacchetti alla rete locale senza che il trasmettitore conosca il suo numero
- sottoreti (subnet)
  - quando si hanno un numero elevato di host, puo non essere possibile gestire un'intera rete con un unico indirizzo di rete, in tal caso si suddivide la rete in varie sottoreti
  - in questo contesto il termine sottorete indica una parte della rete e non l'insieme di tutti i router e le linee di comunicazione di una rete
  - la suddivisione in sottoreti è un fatto privato della network che viene suddivisa, e non ha bisogno di essere comunicato all'esterno, pertanto non richiede l'approvazione di ICANN o la modifica di database esterni
  - per poter suddividere la rete in sottoreti si considera l'host number dell'indirizzo IP come una coppia di valori:
    - subnet number
      - indirizzo di sottorete
    - host number
      - indirizzo dell'host
  - subnet mask (maschera di sottorete):
    - è unica per tutta la rete
    - maschera di bit che indica il punto di demarcazione tra subnet number ed host number
    - è scritta in notazione decimale a punti oppure in notazione "/n" dove n rappresenta il numero di bit da 0 fino alla fine del numero di sottorete
    - a seconda dell'ampiezza del campo dedicato alla subnet, si possono ottenere molte subnet con pochi host oppure poche subnet con molti host
    - elaborazione nel router dei pacchetti IP
      - normalmente
        
        ogni router ha una tabella che elenca i numeri di indirizzi IP del tipo:
        
        [rete, 0]
        
        indica come raggiungere le reti distanti
        
        [questa rete, host]
        
        indica come raggiungere gli host locali
        
        ad ogni tabella è associata la scheda di rete da utilizzare per raggiungere la destinazione, insieme ad altre informazioni
        
        quando riceve un pacchetto IP, il router cerca il suo indirizzo di destinazione nella tabella di routing
        
        se il pacchetto è indirizzato ad una rete distante, viene inoltrato al router successivo sull'interfaccia indicata dalla tabella
        
        se la destinazione è un host locale (sulla LAN del router), il pacchetto viene inviato direttamente alla destinazione
        
        se la rete non viene trovata nella tabella, il pacchetto viene inoltrato ad un router predefinito contenente tabelle più estese
        
        ogni router deve tener traccia solo delle altre reti e degli host locali, anzichè di tutte le coppie [rete, host]
      - con la divisione in sottoreti
        
        si aggiungono alle tabelle di routing delle voci nella forma:
        
        [questa rete, sottorete, 0]
        
        [questa rete, questa sottorete, host]
        
        un router su una sottorete k sa come raggiungere tutte le altre sottoreti e sa anche come raggiungere tutti gli host della sottorete k
        
        il router non deve conoscere i dettagli relativi agli host che si trovano sulle altre sottoreti
        
        il router esegue un'operazione di AND con la maschera di sottorete per eliminare il numero di host e cercare l'indirizzo risultante nelle proprie tabelle (dopo aver determinato la classe di rete di appartenenza)
        
        la divisione in sottoreti riduce lo spazio della tabella del router, in quanto crea una gerarchia a tre livelli associata alla rete, alla sottorete ed agli host
  - soluzione all'esaurimento degli indirizzi Internet
    - IPv6
      - protocollo che utilizza indirizzi a 128 bit
      - IPv4 sta lentamente passando ad IPv6, ci vorranno anni prima del completamento
    - CIDR (Classes InterDomain Routing, RFC 1519)
      - consiste nell'assegnare gli indirizzi IP rimanenti in blocchi di dimensioni variabili, senza tener conto delle classi
      - l'abbandono delle classi rende l'inoltro più complicato
      - ad ogni voce della tabella di routing è integrata una maschera di 32 bit, perciò c'è una sola tabella di routing per tutte le reti costituita da una matrice di valori nella forma:
        
        [indirizzo IP, subnet mask, rete, linea di output]
    - NAT (Network Address Translation, RFC 3022)
      - ogni LAN riceve un unico indirizzo IP per instradare il traffico interno alla rete locale
      - all'interno della rete locale i vari host usano degli intervalli di indirizzi IP che sono stati dichiarati privati e che non possono essere utilizzati su Internet:
        
        10.0.0.0 - 10.255.255.255/8 (16.777.216 host)
        
        172.16.0.0 - 172.31.255.255/12 (1.048.576 host)
        
        192.168.0.0 - 192.168.255.255/16 (65.536 host)
      - ogni volta che un pacchetto varca la frontiera del dispositivo NAT (router, firewall) l'indirizzo viene tradotto
      - il dispositivo NAT contiene una tabella di traduzione che utilizza le porte dei protocolli TCP o UDP per specificare l'host sorgente e l'host destinazione
      - il NAT è considerato un espediente temporaneo di scarsa qualità in attesa di IPv6
- protocolli di controllo internet
  - Internet ha diversi protocolli di controllo utilizzati nello strato network, tra cui:
    - ICMP (Internet Control Message Protocol)
      - protocollo utilizzato per comunicare eventi imprevisti e per testare Internet
      - sono stati definiti circa una dozzina di tipi di messaggi ICMP ( http://www.iana.org/assignments/icmp-parameters )tra cui:
        
        DESTINATION UNREACHABLE
        
        è utilizzato quando una sottorete o un router non sono in grado di individuare la destinazione, o quando un pacchetto con il bit DF non può essere inoltrato perchè lungo il percorso si trova una rete a pacchetti piccoli
        
        TIME EXCEEDED
        
        è inviato quando un pacchetto è scartato perchè il suo contatore ha raggiunto il valore zero
        
        PARAMETER PROBLEM
        
        indica che è stato rilevato un valore illegale in un campo dell'intestazione
        
        SOURCE QUENCH
        
        era utilizzato in passato per rallentare gli host che trasmettevano troppi pacchetti
        
        oggi è utilizzato raramente perchè in caso di congestione peggiorano la situazione
        
        REDIRECT
        
        è utilizzato dal router per comunicare all'host trasmittente che un pacchetto sembra essere stato instradato in modo errato
        
        ECHO REQUEST
        
        viene inviato per scoprire se una certa destinazione è raggiungibile ed attiva
        
        ECHO REPLY
        
        risposta ai messaggi ECHO REQUEST
        
        TIMESTAMP REQUEST
        
        richiesta ECHO con timestamp
        
        si utilizza per misurare le prestazioni della rete
        
        TIMESTAMP REPLY
        
        risposta alle richieste TIMESTAMP REQUEST con registrazione dell'ora di arrivo del messaggio e l'ora di invio della risposta
    - ARP (Address Resolution Protocol, RFC 826)
      - gli indirizzi IP Internet delle macchine non possono essere utilizzati per inviare pacchetti perché l'hardware che opera sullo strato data link non comprende gli indirizzi Internet
      - le schede di rete conoscono solo gli indirizzi di rete (es: 48 bit dell'indirizzo Ethernet) tali indirizzi sono unici per ogni scheda a livello globale
      - le schede di rete inviano e ricevono frame basati sull'indirizzo di rete, ignorando gli indirizzi IP a 32 bit
      - per poter comunicare con l'host di destinazione, l'host sorgente deve scoprirne l'indirizzo di rete:
        
        l'host sorgente invia un pacchetto broadcast (ARP) che chiede chi è il proprietario dell'indirizzo IP cercato
        
        l'host di destinazione risponde inviando il proprio indirizzo di rete
        
        il software IP sull'host sorgente costruisce un frame di rete (es: Ethernet) indirizzato all'indirizzo di rete dell'host di destinazione ed inserisce il pacchetto IP nel carico utile
        
        l'host di destinazione rileva il frame, si accorge di essere il destinatario della comunicazione, preleva i dati e genera un'interrupt
        
        il driver di rete (Ethernet) dell'host di destinazione estrae il pacchetto IP dal carico utile e lo passa al software IP, che verifica la correttezza dell'indirizzo ed elabora i dati
      - varie ottimizzazioni consentono ad ARP di funzionare in maniera più efficiente:
        
        utilizzo della cache per evitare di ripetere l'operazione ARP ad ogni comunicazione
        
        invio dell'associazione IP - indirizzo di rete dell'host sorgente con il primo pacchetto ARP (così da evitare una controrichiesta)
        
        fare in modo che ogni computer trasmetta in broadcast durante l'accensione la propria associazione di indirizzi (questo non genera risposte ma permette l'aggiornamento delle cache ARP degli altri computer)
      - le voci nella cache ARP dovrebbero scadere dopo pochi minuti per consentire la modifica delle associazioni
      - se l'indirizzo IP di destinazione è relativo ad un'altra rete non è possibile inviare pacchetti broadcast, quindi si adottano due varianti:
        
        1. ARP Proxy
        
        il primo router potrebbe essere configurato per rispondere alle richieste ARP della rete dell'host sorgente (e possibilmente delle altre reti locali)
        
        l'host uno crea un'associazione tra l'indirizzo IP dell'host di destinazione e l'indirizzo di rete del router, e trasmette al router tutto il traffico per la destinazione
        
        il router farà poi da tramite nella conversazione IP fra il mittente e il destinatario, inviando di volta in volta all'uno i pacchetti IP che gli giungono dall'altro
        
        2. indirizzo predefinito
        
        si configura l'host impostando al suo interno l'indirizzo Ethernet di default (quello del router) a cui mandare i pacchetti IP per le altre reti
        
        anche in questo caso il router deve fare da tramite nella conversazione IP fra il mittente e il destinatario
        
        questa soluzione non richiede che il router sappia quali sono le reti remote che sta servendo
      - la tecnica ARP è utilizzata anche nella comunicazione fra router
    - RARP (Reverse Resolution Protocol, RFC 903)
      - consente di scoprire l'indirizzo IP a partire dall'indirizzo di rete
      - è utilizzato da stazioni di lavoro senza dischi interni che normalmente ricevono una copia binaria del sistema operativo da server remoti
      - permette ad una stazione di lavoro appena avviata di inviare in modalità broadcast il proprio indirizzo di rete chiedendo come risposta il proprio indirizzo IP
      - il server RARP riceve la richiesta, cerca l'indirizzo di rete nei suoi file di configurazione e trasmette una risposta contenente l'indirizzo IP corrispondente
      - questo meccanismo funziona solo su rete locale (occorre un server RARP per ogni rete)
    - BOOTP (BOOTstrap Protocol, RFC 951, RFC 1048, RFC 1084)
      - risolve il problema di RARP relativo alla comunicazione con altre reti
      - utilizza messaggi UDP che sono inoltrati attraverso i router
      - fornisce alle stazioni di lavoro senza dischi delle informazioni aggiuntive:
        
        l'indirizzo IP del file server che contiene l'immagine della memoria
        
        l'indirizzo IP del router predefinito
        
        la subnet mask da utilizzare
      - richiede la configurazione manuale delle tabelle che associano gli indirizzi IP a quelli di rete
    - DHCP (Dynamic Host Configuration Protocol, RFC 2131, RFC 2132)
      - versione migliorativa di BOOTP che permette l'assegnazione manuale oppure automatica degli indirizzi IP
      - si basa sull'idea di un server speciale che assegna gli indirizzi IP agli host che ne richiedono uno
      - il server DHCP non deve trovarsi necessariamente nella LAN dell'host richiedente
      - agente di inoltro DHCP (DHCP relay agent)
        
        è necessario installarne uno in ogni LAN perché il server DHCP potrebbe non essere raggiungibile da trasmissioni broadcast
        
        necessita solo dell'indirizzo IP del server DHCP
      - funzionamento:
        
        all'avvio una macchina invia in modalità broadcast un pacchetto DHCP DISCOVER
        
        l'agente di inoltro sulla stessa LAN, che intercetta tutte le trasmissioni DHCP, rileva il pacchetto DHCP DISCOVER e lo trasmette in modalità unicast al server DHCP
      - leasing
        
        tecnica che consente il rilascio degli indirizzi IP allocati dal server DHCP dopo un certo periodo di tempo
        
        poco prima della scadenza il server DHCP chiede all'host il rinnovo dell'indirizzo
        
        se l'host non conferma, l'indirizzo viene rilasciato
        
        questo consente di evitare l'esaurimento del pool di indirizzi a causa di disconnessioni
- OSPF (Open Shortest Path First, RFC 2328) - protocollo di routing per i gateway interni (interior gateway protocol)
  - principale algoritmo di routing adottato all'interno di un AS (Autonomous System) di Internet
  - utilizza l'algoritmo Shortest Path First (SPF) anche noto come algoritmo di Dijkstra
  - è di tipo link-state (routing basato sullo stato dei collegamenti) con supporto per i sistemi gerarchici
  - gli aggiornamenti sul routing sono inviati solo se c'è un effettivo cambiamento della topologia, riducendo così il packet overhead
  - inizialmente si adottò un protocollo basato sul vettore delle distanze (RIP - Routing Information Protocol, RFC 1058), poi nel 1979 si passò ad un protocollo basato sullo stato dei collegamenti, nel 1988 IETF cominciò a lavorare su OSPF che divenne uno standard nel 1990
  - requisiti di progettazione:
    - doveva essere pubblicato senza vincoli di brevetto (da cui la dicitura Open)
    - doveva supportare diverse metriche di distanza (es: distanza fisica, ritardo, ...)
    - doveva essere un algoritmo dinamico, in grado di modificarsi rapidamente ed automaticamente in base alla topologia
    - doveva supportare il routing basato sul tipo di servizio
      - il campo type of service del protocollo IP fu incluso in OSPF ma poichè continuava ad essere inutilizzato, alla fine venne rimosso
    - doveva eseguire il bilanciamento del carico, ossia suddividere il carico su più linee
    - doveva supportare i sistemi gerarchici (nell'1988 nessun router poteva conoscere l'intera topologia di Internet)
    - doveva implementare maggior sicurezza
    - doveva provvedere alla gestione dei router collegati ad Internet tramite tunnel
  - OSPF supporta 4 tipi di connessioni e reti:
    - 1. reti multiaccesso con trasmissioni broadcast
      - esempi: Ethernet, token ring, FDDI (la maggior parte delle LAN)
    - 2. reti multiaccesso senza trasmissione broadcast
      - esempi: frame relay, x.25, SMDS (la maggior parte delle WAN a commutazione di pacchetto)
    - 3. linee punto-punto tra due router
      - esempi: PPP, HDLC
    - 4. linee punto-multipunto
      - esempi: Administrator-defined
  - rete multiaccesso
    - è una rete che può contenere più router, ognuno in grado di comunicare direttamente con tutti gli altri
    - tutte le LAN e le WAN hanno questa proprietà
  - funzionamento generico di OSPF:
    - riassume l'insieme di reti reali, router e linee in un grafo orientato in cui ad ogni arco è assegnato un costo (distanza, ritardo, ...)
    - una connessione seriale tra due router è rappresentata da una coppia di archi con pesi che possono essere diversi
    - una rete multiaccesso è rappresentata da un nodo per la rete stessa più un nodo per ogni router
    - gli archi dal nodo di rete ai router hanno peso 0 e sono omessi dal grafo
    - OSPF calcola il percorso più breve da ogni router ad ogni altro router in base al peso degli archi
  - OSPF consente la suddivisione degli AS in più aree
    - area
      - è una rete o un'insieme di reti contigue
      - è una generalizzazione di una sottorete
      - le aree non si sovrappongono e non hanno bisogno di essere complete (alcuni router possono non appartenere ad alcuna area)
      - tutte le aree sono collegate alla dorsale (per esempio con tunnel)
    - dorsale
      - ogni AS ha un'area dorsale chiamata area 0
      - un tunnel è rappresentato nel grafo come un arco con un costo (peso)
      - è possibile passare da un'area all'altra dello stesso AS passando attraverso la dorsale
      - ogni router collegato a due o più aree fa parte della dorsale
      - la topologia della dorsale non è visibile all'esterno della stessa
    - dentro un'area, ogni router ha lo stesso database degli stati dei collegamenti ed esegue lo stesso algoritmo di individuazione del percorso più breve
      - il suo compito principale è calcolare il percorso più breve da se stesso ad ogni altro router nell'area, incluso il router che è collegato alla dorsale (ci deve essere almeno un router di questo tipo)
    - un router che collega due aree ha bisogno dei database di entrambe le aree, e deve eseguire separatamente un diverso algoritmo di ricerca del percorso più breve per ogni area
    - durante il funzionamento normale possono essere necessari tre tipi di percorsi:
      - interni all'area
        
        sono i più semplici, perché il router sorgente conosce già il percorso più breve diretto al router di destinazione
      - tra aree
        
        segue sempre tre fasi:
        
        dalla sorgente alla dorsale
        
        attraverso la dorsale fino all'area di destinazione
        
        alla destinazione
      - tra AS
    - questo algoritmo crea su OSPF una configurazione a stella, con la dorsale che funge da hub e le altre aree che fungono da raggi
    - i pacchetti sono instradati dalla sorgente alla destinazione così come sono, perciò non sono incapsulati ne trasmessi attraverso tunnel, a meno che l'area di destinazione non si colleghi alla dorsale attraverso un tunnel
  - classi di router
    - OSPF distingue 4 classi di router:
      - 1. router interni (internal router)
        
        si trovano completamente dentro un'area
      - 2. router di confine (border router)
        
        collegano due o più aree
      - 3. router di dorsale (backbone router)
        
        sono sulla dorsale
      - 4. router sul confine dell'AS (boundary router)
        
        comunicano con i router che si trovano in altri AS
    - le classi di router possono sovrapporsi
      - tutti i router di confine fanno automaticamente parte della dorsale
      - un router che si trova sulla dorsale ma che non fa parte di nessun'altra area è anche un router interno
  - funzionamento:
    - router
      - DR (Designated Router, router designato)
        
        per evitare che ogni router su una LAN comunichi con ogni altro router, un router è denominato router designato
        
        è considerato adiacente a tutti gli altri router della sua LAN
        
        scambia informazioni con gli altri apparecchi
        
        i router confinanti che non sono adiacenti non scambiano informazioni gli uni con gli altri
        
        esiste solo nelle reti multiaccesso
      - BDR (Backup Designated Router, router di backup)
        
        viene costantemente aggiornato per facilitare la transizione in caso di blocco del router designato principale
        
        esiste solo nelle reti multiaccesso
    - messaggi OSPF (inviati come pacchetti IP grezzi)
      - HELLO (presentazione)
        
        utilizzato per scoprire chi sono i vicini
        
        all'avvio il router trasmette messaggi HELLO attraverso tutte le sue linee punto-punto e comunica questi messaggi in modalità multicast sulle LAN, ai gruppi composti da tutti gli altri router
        
        sulle WAN, per individuare chi deve essere contattato, il router ha bisogno di alcune informazioni di configurazione
        
        in base alle risposte, ogni router scopre chi sono i suoi vicini (i router sulla stessa LAN sono tutti vicini)
      - DBD (Database Description Packet, descrizione del database)
        
        annuncia gli aggiornamenti posseduti dal trasmittente
        
        sono utilizzati quando la linea viene attivata
        
        contengono i numeri di sequenza di tutte le voci relative allo stato dei collegamenti possedute in quel momento dal trasmittente
        
        confrontando i propri valori con quelli inviati dal router trasmittente, il ricevente può scoprire chi possiede i valori più recenti
      - LSR (Link-State Request, richiesta stato del collegamento)
        
        richiede informazioni al partner sullo stato dei collegamenti
        
        ogni coppia di router adiacenti si controlla per vedere chi ha i dati più recenti, in questo modo le informazioni si propagano attraverso l'area
      - LSU (Link-State Update, aggiornamento stato del collegamento)
        
        comunica ai vicini i costi del trasmittente
        
        vengono inviati periodicamente, quando la linea si attiva o si disattiva, e quando il suo costo cambia
        
        vengono inviati in flooding ad ognuno dei router adiacenti
        
        questo messaggio comunica lo stato del dispositivo ed i costi utilizzati nel database della topologia
        
        la ricezione di acknowledgement rende questi messaggi affidabili
        
        ogni messaggio ha un numero di sequenza, perciò un router può scoprire se un LSU appena arrivato è più vecchio o più nuovo di quello già posseduto
      - LSAck (Link-State Acknowledgement, conferma stato del collegamento)
        
        conferma l'aggiornamento dello stato del collegamento
    - OSPF funziona scambiando informazioni tra router adiacenti (il che non equivale a dire tra router vicini)
    - quando OSPF viene inizialmente inizializzato su un router, passa attraverso 7 stati:
      - 1. Down State
        
        nessuna informazione è stata ancora scambiata
      - 2. Init State Routers
        
        invia un pacchetto HELLO ad intervalli regolari (10 sec) per stabilire una comunicazione
        
        tutti i pacchetti HELLO ricevuti dagli altri router vengono elaborati ed il loro IP utilizzato per i futuri invii di pacchetti HELLO
      - 3. Two-way State
        
        il router riceve un pacchetto HELLO contenente il proprio IP
      - 4. ExStart
        
        attraverso i pacchetti HELLO i router negoziano una relazione master/slave confrontando i loro ID
        
        il master è determinato dall'ID più alto
      - 5. Exchange State
        
        si utilizzano i pacchetti DBD per inviare agli altri router le informazioni sullo stato del collegamento
        
        se un router riceve informazioni su un nuovo collegamento, richiede un completo aggiornamento
      - 6. Loading State
        
        un router può richiedere maggiori informazioni utilizzando un pacchetto LSR
        
        il router ricevente risponderà con un pacchetto di tipo LSU contente le informazioni sul collegamento
        
        un pacchetto di acknowledgement (LSAck) viene inviato per confermare l'avvenuto aggiornamento
      - 7. Full adjacency
        
        i router sono ora adiacenti
    - funzionamento descrittivo:
      - il flooding permette ad ogni router di comunicare a tutti gli altri router della sua area chi sono i vicini ed i costi utilizzati
      - queste informazioni consentono ad ogni router di costruire il grafo dell'area e di calcolare il percorso più corto, la dorsale fa lo stesso
      - i router della dorsale accettano informazioni dai router di confine dell'area in modo da poter calcolare il percorso migliore diretto da ogni router di dorsale ad ogni altro router
      - queste informazioni si propagano all'indietro verso i router di confine dell'area, che le annunciano dentro le loro aree
      - usando questi dati, un router che sta per inviare un pacchetto da un'area ad un'altra può selezionare il router di uscita migliore verso la dorsale
- Internet multicasting
  - la normale comunicazione IP avviene tra un trasmittente ed un ricevente, ma per alcune applicazioni è utile che un processo possa comunicare contemporaneamente con un gran numero di ricevitori
    - esempi: aggiornamento di database distribuiti e replicati, gestione di audioconferenze digitali, ...
  - IP supporta la trasmissione multicast, utilizzando gli indirizzi di classe D
  - ogni indirizzo di classe D identifica un gruppo di host e 28 bit sono utilizzati per identificare i gruppi, perciò possono esistere nello stesso momento più di 250 milioni di gruppi
  - quando un processo invia un pacchetto ad un indirizzo di classe D, viene fatto un tentativo best effort per trasmettere i dati a tutti i membri del gruppo di destinazione, ma non viene data alcuna garanzia (alcuni membri possono non ricevere il pacchetto)
  - sono supportati due tipi di indirizzi di gruppo:
    - permanenti
      - un gruppo permanente è sempre presente, non deve essere impostato
      - ad esempio:
        
        224.0.0.1 tutti gli apparati LAN
        
        224.0.0.2 tutti i router su una LAN
        
        224.0.0.5 tutti i router OSPF su una LAN
        
        224.0.0.6 tutti i router OSPF designati su una LAN
    - temporanei
      - devono essere creati prima di poter essere utilizzati
      - un processo può chiedere al suo host di unirsi ad un gruppo specifico oppure di abbandonarlo
      - quando l'ultimo processo su un host lascia un gruppo, quel gruppo non è più presente sull'host
      - ogni host tiene traccia dei gruppi di appartenenza correnti dei propri processi
  - la trasmissione multicast è implementata da speciali router multicast, che eventualmente possono essere abbinati ai router standard
    - circa una volta al minuto, ogni router multicast genera una trasmissione hardware multicast (sullo strato data-link) diretta agli host della sua LAN (224.0.0.1) che chiede alle macchine di indicare i gruppi di appartenenza dei loro processi
    - ogni host risponde comunicando tutti gli indirizzi di classe D che gli interessano
    - i pacchetti di interrogazione e risposta utilizzano il protocollo IGMP
    - IGMP (Internet Group Management Protocol, protocollo Internet di gestione dei gruppi, RFC 1112)
      - ha solo due tipi di pacchetti di interrogazione e risposta con un formato molto semplice
      - contengono alcune informazioni di controllo nella prima word del carico utile ed un indirizzo di classe D nella seconda word
  - il routing multicast è eseguito usando le strutture spanning tree
  - ogni router multicast scambia informazioni con i suoi vicini utilizzando un protocollo basato sul vettore delle distanze, ciò consente ad ogni router di costruire per ogni gruppo uno spanning tree che copre tutti i membri del gruppo
  - si utilizzano svariati meccanismi di ottimizzazione per sfrondare la struttura ad albero ed eliminare i router e le reti che non sono interessati a particolari gruppi
  - il protocollo usa in modo pesante i tunnel per evitare di infastidire i nodi che non fanno parte dello spanning tree