Riassunto Reti di Calcolatori Kurose-Ross (PDF)

RETI DI CALCOLATORI I Riassunto basato sul libro: Kurose Ross – Reti di Calcolatori. Un approccio Top Down (7a ed.) CAPITOLO 1 – RETI DI CALCOLATORI E INTERNET INTERNET Internet è una rete ad accesso pubblico che connette vari dispositivi in tutto il mondo. Questi sono detti host (ospiti) o end system (sistemi periferici). Gli end system sono connessi tra loro tramite una communication link (rete di collegamenti) e packet switch (commutatori di pacchetti). I collegamenti possono essere costituiti da varie tipologie con relative trasmission rate (velocità di trasmissione). Due host collegati alla rete suddividono i dati che si scambiano in pacchetti, che trasmettono tramite router, posti nel nucleo della rete o tramite link-layer switch (commutatori a livello di collegamento) sulle reti di accesso. La sequenza di collegamenti e commutatori attraversati da un pacchetto per arrivare da un end-system all’altro è detta path (percorso). I sistemi periferici accedono a Internet tramite Internet Service Provider (ISP). Un provider è un insieme di commutatori di pacchetto e di collegamenti, che sotto sottoscrizione di contratto fornisce ai clienti diversi tipi di accesso alla rete (DSL, wireless, dial-up). Tutti i nodi all’interno rete per comunicare tra loro fanno uso di protocolli, ovvero definizioni del formato e l’ordine dei messaggi scambiati. Questi garantiscono interoperabilità, e cioè che un terminale (o un software) possa comunicare efficacemente con un altro terminale senza conoscerne le caratteristiche implementative. Gli standard Internet sono sviluppati dall’ Engineering Task Force (IETF) e consistono in specifiche normative di una tecnologia o metodologia applicabile su Internet. Uno standard nasce come Internet Draft, pubblicato da IETF, può essere promosso a Request for Comments (RFC) cioè un documento che propone uno standard e richiede simultaneamente proposte di miglioramento a tutti gli esperti. Questo, una volta supervisionato ed approvato diventa un vero e proprio standard. Si parla di standard de facto per riferirsi ad architetture, protocolli che sono effettivamente di ampia diffusione e di dominio pubblico, ma che non sono state mai normate. Mentre invece sono standard de iure quelli ufficializzati da enti come ISO. STRUTTURA DI INTERNET L’Accesso ad internet avviene per mezzo di un fornitore di servizi o ISP (Internet Service Provider). Gli ISP sono collegati tra loro secondo una struttura gerarchica (ISP Locali-> ISP Nazionali). Gli ISP Nazionali si collegano a fornitori di connettività internazionali (NBP, Network Backbone Provider), che sono a loro volta collegati in punti di interscambio detti NAP (Network Access Point) SERVIZI INTERNET DISTRIBUITI Internet può essere vista come una piattaforma che fornisce servizi alle applicazioni. Queste ultime sono dette applicazioni distribuite perché coinvolgono più sistemi periferici che si scambiano reciprocamente dati. I moduli software sono eseguiti sulle periferiche, e quindi i nodi della rete non hanno a che fare propriamente con l’elaborazione, però necessitano della rete per comunicare con altri sistemi. L’applicazione deve fornire delle API (Application Programming Interface) che specificano come un modulo software possa servirsi di Internet per recapitare dati ad un altro modulo software residente su un altro terminale collegato alla rete stessa. SISTEMI PERIFERICI Sono tutti i dispositivi connessi alla rete che si trovano ai confini della stessa (calcolatori, smartphone, server, ecc.). Questi vengono anche detti host in quanto ospitano (ed eseguono) i programmi applicativi. Talvolta questi vengono suddivisi in client che richiedono i servizi e server che erogano i servizi. RETI DI ACCESSO Le Access Network sono reti che connettono fisicamente un sistema al suo edge router (router di bordo) cioè il primo router sul percorso verso la destinazione. Accesso Residenziale:  un accesso di tipo DSL (Digital Subscriber Line) viene fornito da una compagnia telefonica che assume il ruolo di ISP. Questa tecnologia usufruisce della linea telefonica (doppino telefonico in rame) per scambiare dati con una DSLAM (Digital Subscriber Line Access Multiplex) che si trova nella centrale locale. Il model DLS converte i dati digitali in toni ad alta frequenza per poterli trasmettere alla centrale locale sul cavo telefonico. Analogamente tutti i segnali analogici in arrivo al modem vengono riconvertiti in formato digitale. Vengono utilizzate tecniche di Multiplazione a divisione di frequenza (FDM) per separare il segnale vocale (0-4KHz) dal traffico dati in downstream (50kHz-1MHz) e upstream (4-50kHz). ADSL: l’accesso è asimmetrico, perché la velocità di trasmissione e di ricezione sono diverse.  Un accesso di tipo DIAL-UP consiste in una connessione di tipo non permanente, dove la banda utilizzata è quella fonica a bassa frequenza, che viene occupata tramite una composizione di una numerazione telefonica utilizzando programmi Dialer. (velocità di accesso 56 kbps).  L’accesso di tipo FTTH (fiber to the home) fornisce un collegamento in fibra ottica dalla centrale locale direttamente alle abitazioni. (velocità di accesso potenziale dell’ordine dei gigabit). Accesso aziendale (e residenziale):  Rete locale (LAN, Local Area Network) è una rete di collegamento che copre un’area limitata (abitazioni, aziende, università) e che utilizza tecnologia Ethernet (LAN) o Wireless (WLAN). La tecnologia Ethernet utilizza un doppino in rame intrecciato per collegare numerosi end-system tra loro, connetterli ad uno switch Ethernet e portarli verso l’ISP tramite un router. L’accesso ha generalmente velocità intorno ai 100 Mbps. La tecnologia Wireless (Wi-Fi) consiste in una comunicazione che non fa uso di cavi e che si oppone quindi a sistemi wired (cablati). Accesso wireless su scala geografica:  3G Wireless di terza generazione consentono accesso wireless a Internet con commutazione a pacchetto anche a decine di chilometri dalla stazione base, a velocità che superano 1Mbps.  4G Wireless di quarta generazione può potenzialmente raggiungere velocità superiori a 10 Mbps. NUCLEO DELLA RETE Commutatori di pacchetto Ciascun flusso di dati che si scambiano le applicazioni distribuite viene diviso in parti piccole detti pacchetti. Per raggiungere il destinatario questi pacchetti viaggiano attraverso diversi commutatori di pacchetto posti sul path (che possono essere di tecnologia e velocità trasmissiva differente). Ogni pacchetto è composto da un - Header utilizzato ai fini dell’identificazione e gestione; - Payload che contiene i dati veri e propri. Store and Forward La maggior parte dei commutatori utilizza la trasmissione store-and-forward. Ciò significa che il commutatore deve ricevere l’intero pacchetto e storarlo in un buffer prima di poter cominciare la trasmissione in uscita. Trascurando ritardi e tempi di elaborazione, se T è il tempo di trasmissione tra un host e il commutatore (numero bit/velocità mezzo), allora il tempo totale di trasmissione tra due host che vogliono scambiare un pacchetto attraverso un router è pari a 2T. Il tempo di trasmissione di P pacchetti attraverso un router è (P+1)T. Il ritardo totale per una trasmissione di P pacchetti su un percorso di N router è pari a (P+N)T. Ritardi di accodamento e perdita di pacchetti Ogni commutatore, per ciascuno dei collegamenti a cui è connesso, mantiene un buffer di output (o coda) dove conserva i pacchetti che sta per inviare. Un pacchetto in arrivo che richiede l’invio attraverso un determinato collegamento, ma lo trova occupato dalla trasmissione di un altro, deve accodarsi nel buffer. Questo comporta dei ritardi di accodamento che vanno ad incrementare i tempi di trasmissione di un pacchetto. Tali ritardi ovviamente sono variabili e dipendono dal livello di traffico sulla rete. Dato che la dimensione del buffer è finita può accadere che un pacchetto in arrivo trovi il buffer completamente pieno. Si verificherà una perdita di pacchetto (packet loss). Un problema di interesse ingegneristico è il controllo di congestione: adeguare la velocità di invio pacchetti da parte dell’end-system alla velocità di inoltro del router, in modo da evitare code di bufferizzazione piene. Tabelle di inoltro e protocolli di instradamento Un router prende un pacchetto in arrivo da un suo collegamento e lo inoltra su un atro dei suoi collegamenti. Esistono diversi modi, a seconda del tipo di rete, tramite i quali un router può determinare su quale collegamento inoltrare il pacchetto. In Internet ogni end-system ha un indirizzo IP. Ogni pacchetto che percorre la rete contiene nella sua intestazione (header) l’indirizzo ip della sua destinazione. Ogni router ha una tabella di inoltro (forwarding table) che mette in relazione gli indirizzi di destinazione con in collegamenti in uscita del router stesso. Quando il pacchetto giunge ad un router, quest’ultimo esamina l’indirizzo della destinazione e consulta la propria tabella per determinare il collegamento uscente appropriato verso cui dirigere il pacchetto in uscita. Internet implementa parecchi protocolli di instradamento (routing protocol) per impostare automaticamente queste tabelle di inoltro. COMMUTAZIONE A CIRCUITO Nelle reti a commutazione di pacchetto i messaggi utilizzano le risorse di rete (il canale) solo quando necessario. Nelle reti a commutazione di circuito, al contrario, le risorse richieste per la comunicazione tra due end-system sono riservate per l’intera durata della sessione di comunicazione ed inoltre prima che la comunicazione avvenga, la rete deve stabilire una connessione (circuito) end-to-end tra mittente e destinatario, con capacità trasmissiva assegnata. Rispetto ad alla commutazione a pacchetti usata in Internet offre una maggiore garanzia sulla ricezione dei pacchetti, che viaggiano su canali dedicati. Non esiste dunque il problema della congestione. Lo svantaggio è rappresentato dal fatto che i circuiti dedicati sono inutilizzati durante i periodi di silenzio e non possono essere sfruttati da altre connessioni. Multiplexing Un circuito all’interno di un unico collegamento è realizzato tramite multiplexing a divisione di frequenza (FDM) o multiplexing a divisione di tempo (TDM). Con il primo, lo spettro di frequenza di un collegamento viene suddiviso tra le diverse connessioni. Nello specifico viene dedicata un’ ampiezza di banda (bandwidth) a ciascuna connessione. Con il secondo invece, il tempo viene suddiviso in frame (intervalli) di durata fissa, a loro volta ripartiti in un numero fisso di slot temporali. Quando la rete stabilisce una connessione attraverso un collegamento, le dedica uno slot di tempo in ogni frame. PROBLEMATICHE COMMUTAZIONE DI PACCHETTO L’obiettivo di qualunque rete, idealmente, sarebbe spostare una quantità di dati tra due host, istantaneamente e senza perdita di dati. Purtroppo l’architettura della rete stessa e i mezzi materiali costitutivi limitano necessariamente il throughput (quantità di bit al secondo) e introdugono ritardi e perdite. 1. Ritardo di elaborazione Il tempo richiesto per esaminare l’header del pacchetto e per determinare dove dirigerlo fa parte del processing delay. Questo può includere altri fattori, tra i quali il tempo richiesto per controllare errori a livello di bit nel pacchetto. Dopo l’elaborazione il router dirige il pacchetto verso la coda in uscita. 2. Ritardo di accodamento Una volta in coda, il pacchetto subisce un queuing delay mentre attende la trasmissione sul collegamento. Tale ritardo dipende è variabile e cambia dinamicamente in funzione della dimensione della coda. Può essere caratterizzato staticamente tramite distribuzioni di probabilità e i modelli della teoria delle code. 3. Ritardo di trasmissione Sia L la lunghezza del pacchetto in bit ed R la velocità di trasmissione del collegamento tra router A e router B; Il trasmission delay è dato da L/R e misura il tempo effettivamente impiegato per trasmette tutti i bit del pacchetto sul collegamento. 4. Ritardo di propagazione Il propagation delay misura il tempo impiegato da un bit immesso sul collegamento per propagarsi fino al router B. Il bit viaggia alla velocità di propagazione del collegamento, che dipende dunque dal mezzo fisico. È dato da d/v, dove d è la distanza e v la velocità di propagazione. Ritardo di accodamento La componente più complessa del ritardo totale di nodo è il ritardo di accodamento. Essendo una grandezza variabile in funzione della velocità di arrivo sulla coda, della velocità di trasmissione del collegamento e della natura del traffico (periodico, a raffiche, ecc.) per caratterizzarla si fa uso di misure statistiche quali il ritardo di accodamento medio, la varianza del ritardo di accodamento e la probabilità che il ritardo di accodamento superi un valore fissato. a è la velocità media di arrivo dei pacchetti alla coda (packet/s), R la velocità di trasmissione (bit/s). Supponiamo che tutti i pacchetti siano di L bit. La velocità media di arrivo dei bit è La (bit/s); Il rapporto La/R è detto intensità di traffico. La/R>1 allora la velocità media di arrivo dei bit supera la velocità alla quale vengono ritrasmessi in uscita; In questa situazione la coda tenderà a crescere all’infinito e con essa il ritardo di accodamento. La/R 10000010) Subnet Mask 255.255.255.192 (192-> 11000000) Subnet Address 192.168.5.128 (10000000 = 128) Utilizzo Subnet Al momento dell’invio di un pacchetto, l’host confronta l’indirizzo IP della destinazione con il proprio. Se la destinazione è sulla sua stessa sottorete invia i pacchetti sulla LAN, altrimenti li invia ad un Gateway, che sarà connesso alle altre reti e si occuperà di inoltrare i pacchetti ricevuti. A seconda della subnet mask utilizzata l’indirizzo ricade in una delle seguenti classi: CLASSE UTILIZZO BIT SUBNET MASK RETI HOST A 0NNNNNNN.HHHHHHHH.HHHHHHHH.HHHHHHHH 255.0.0.0 / 8 128 16M B 10NNNNNN.NNNNNNNN.HHHHHHHH.HHHHHHHH 255.255.0.0 / 16 16K 65K C 110NNNNN.NNNNNNNN.NNNNNNNN.HHHHHHHH 255.255.255.0 / 24 2M 256 D 1110XXXX.XXXXXXXX.XXXXXXXX.XXXXXXXX MULTICAST Classe A:  Il primo byte rappresenta la rete (va da 0-128), gli altri tre gli host per ogni rete  La maschera di rete è 255.0.0.0 oppure /8 perché i primi 8 bit sono dedicati alla rete.  Questi indirizzi iniziano con i bit 0 Classe B:  I primi due byte rappresentano la rete (da 128-191), gli altri due gli host per ogni rete  La maschera di rete è 255.255.0.0 oppure /16  Gli indirizzi iniziano con i bit 10 Classe C:  I primi tre byte rappresentano la rete (192- 223), l’ultimo gli host per ogni rete  La maschera di rete è 255.255.255.0 oppure /24)  Gli indirizzi iniziano con i bit 110 Classe D:  È riservata agli indirizzi Multicast.  Non è definita una maschera di rete, essendo tutti i 32 bit utilizzati per indicare un gruppo, non un singolo host.  Questi indirizzi in binario iniziano con i bit 1110. I seguenti sono indirizzi speciali riservati ad usi specifici. Network address: indirizzi di qualsiasi classe, il cui suffisso è costituito da tutti ‘0’ e dunque non sono assegnati a nessun host ma identificano una rete specifica. ES. x.0.0.0/8 Direct Broadcast Address: indirizzi che consentono l’invio di un messaggio a tutti gli host sulla stessa sottorete. Il suffisso dell’indirizzo è costituito da tutti ‘1’. ES x.x.1.1/16 Limited Broadcast Address: 1.1.1.1 (255.255.255.255) viene utilizzato da un host per inviare un messaggio a tutti gli host della stessa rete (il router blocca questi messaggi verso reti esterne). This Computer Address: 0.0.0.0 utilizzato da un host durante la procedura di avvio del suo stack IP in quanto non è ancora a conoscenza del proprio indirizzo IP; il destinatario di tale pacchetto è un server di bootstrap presente sulla rete Zero Address: è un indirizzo che contiene tutti 0 nel prefisso e indica un particolare host nella rete locale con i bit del suffisso. ES 0.0.0.46/24 Loopback Address (o Localhost): è un indirizzo ip con il primo byte pari a 127 utilizzati per il test dello stack IP. Individuano la stessa macchina e non abbandonano mai l’host che li ha generati ES 127.0.0.1 L’indirizzamento a classi presenta diversi limiti dovuti soprattutto al numero di host gestibili dalle diverse classi. In pratica se si esauriscono gli indirizzi univoci resi disponibili da una classe, occorre fare ricorso ad un indirizzo di classe superiore. CLASSLESS INTERDOMAIN ROUTING (CIDR) A partire dal 1993 si abbandonò il concetto di classful routing in favore di una nuova strategia detta classless interdomain routing (CIDR) che generalizza la nozione di indirizzamento di sottorete. L’indirizzo IP è ancora diviso in prefisso e suffisso e mantiene la forma decimale puntata a.b.c.d/x. La novità essenziale consiste nell’utilizzare subnet mask di lunghezza arbitraria x, quando l’indirizzamento classfull ammette solo tre lunghezze (/8, /16, /24). All’interno di una tradizionale Classe C (/24) sono possibili le seguenti sottoreti: Con il vecchio approccio classfull in una sottorete di classe C, 24 bit individuano la singola sottorete, e i restanti 8 bit sono per identificare 256 host. Per cui se sono necessari ad esempio 300 indirizzi una rete di classe C’è insufficiente ed una rete di classe B è sovrabbondante. Con l’approccio classless possono essere forniti blocchi di indirizzi con 31 netmask diverse. Ciò rende più flessibile la suddivisione di reti in più sottoreti mantenendo un adeguato numero di host in ogni sottorete. Esempio: Su un blocco di 256 indirizzi (classe C) è possibile usare una netmask /25 (cioè 255.255.255.128) per ottenere 2 subnet da 128 indirizzi. È possibile suddividere la seconda in ulteriori 2 subnet da 64 indirizzi con una mask 255.255.255.192 (/26). INDIRIZZI PRIVATI Tra gli indirizzi speciali riservati, alcuni blocchi sono riservati per uso privato.  10.0.0.0 – 10.255.255.255 CLASSE A  172.16.0.0 – 172.31.255.255 CLASSE B  192.168.0.0 – 192.168.255.255 CLASSE C Sono indirizzi riservati alle reti locali. I pacchetti con tali indirizzi non vengono utilizzati per l’indirizzamento e l’instradamento tramite protocollo IP dai router Internet verso la rete di trasporto. Risolvono dunque il problema della limitatezza degli indirizzi IP pubblici perché possono essere replicati su reti differenti senza avere conflitti. Nel caso occorra connettere ad Internet una rete locale che utilizza indirizzi privati si deve ricorrere al NAT il quale multipla (o mappa) più indirizzi IP privati su un solo indirizzo IP pubblico, visibile all’esterno della sottorete ed utilizzabile per l’instradamento. NAT – Network Address Translation Il NAT è una tecnica che funziona al livello di rete e in particolare è implementato nei router e nei firewall interposti tra le reti private e Internet. All’interno di una rete privata, sono utilizzati solitamente indirizzi IP privati, che non permettono il routing verso l’esterno. Quando il router che implementa il NAT riceve un pacchetto dalla rete privata, scambia l’indirizzo IP privato (e la porta) con uno pubblico valido per il routing assegnato al router stesso. In pratica un insieme di macchine interne alla rete è vista dall’esterno con un unico ip pubblico, che è quello del router. Il NAT mantiene una tabella di routing per gestire le connessioni e le diverse comunicazioni fra host. Quando riceve un pacchetto dall’esterno, verifica con la tabella di routing se c’è un host interno che aspetta un pacchetto e lo inoltra. Il NAT può essere di tipo:  Statico: il NAT associa un indirizzo IP pubblico ad un indirizzo IP privato interno alla rete. Permette di connettere terminali della rete interna ad internet in maniera trasparente ma non risolve il problema della scarsità di indirizzi.  Dinamico (Network Address and Port Translation): il NAT permette di condividere un indirizzo IP routabile fra più terminali in indirizzamento privato. Tutti i terminali della rete interna hanno virtualmente, lo stesso indirizzo IP, se visti dall’esterno. Questa meccanismo può essere infatti chiamato anche IP masquerading (maschera IP). Per multiplexare i diversi indirizzi IP su un indirizzo pubblico il NAT dinamico usa il meccanismo di traslazione della porta (PAT Port Address Translation), cioè l’attribuzione di una porta sorgente diversa ad ogni nuova richiesta in maniera tale da poter mantenere una corrispondenza tra le richieste che provengono dalla rete interna e le risposte dei terminali su Internet, tutte indirizzata all’indirizzo IP del router. PORT FORWARDING La traslazione di indirizzo, tramite NAT, permette di collegare solo delle richieste che provengono dalla rete interna verso quella esterna, il che significa che è impossibile per un terminale esterno inviare un pacchetto verso un terminale della rete interna. Esiste un’estensione del NAT detta port forwarding che consiste nel configurare in gateway per trasmettere ad un terminale specifico della rete interna, tutti i pacchetti ricevuti su una particolare porta. Così, ad esempio, se si vuole accedere ad un server web (porta 80) funzionante su un terminale 192.168.1.2 (privato) dall’esterno, sarà necessario definire una regola di forwarding della porta sul gateway, ridirigendo tutti i pacchetti TCP ricevuti sulla porta 80 verso il terminale 192.168.1.2. DHCP - DYNAMIC HOST CONFIGURATION PROTOCOL DHCP è un protocollo di rete di livello applicativo che permette agli host di una rete locale di ricevere automaticamente ad ogni richiesta di accesso ad una rete, la configurazione IP necessaria per stabilire una connessione e inter operare con tutte le altre sottoreti. Oltre che all’indirizzo IP da assegnare all’host, DHCP fornisce dinamicamente, al client richiedete:  Maschera di sottorete  Gateway di default  Indirizzi del server DNS  Indirizzi del server WINS  Indirizzi del server NTP  Altro DHCP è implementato come protocollo Client-Server. Un client DHCP di solito è un host che, connesso alla rete, richiede informazioni sulla configurazione di rete. Di solito ogni sottorete dispone di un server DHCP che assegna gli indirizzi, ma in caso contrario è necessario un agente di Relay DHCP, che si occupa di inoltrare le richieste ad un server. Sessione tipica DHCP: 1. Individuazione del server DHCP: il client collegato sulla rete invia un pacchetto UDP chiamato DHCPDISCOVER in broadcast sulla porta 67, con indirizzo IP sorgente 0.0.0.0 (this computer address) e destinazione 255.255.255.255 (indirizzo di broadcast); 2. Offerta del server DHCP: il pacchetto è ricevuto da tutto il dominio di broadcast e in particolare da tutti i server DHCP presenti, i quali possono rispondere (o meno) ciascuno con un pacchetto di DHCPOFFER in cui propongono un indirizzo IP e gli altri parametri di configurazione al client. Questo pacchetto di ritorno è indirizzato in broadcast all’indirizzo di livello datalink del client (che non ha ancora un indirizzo IP) cioè in unicast, per cui può essere inviato solo da un server che si trovi sullo stesso dominio di broadcast. Il pacchetto contiene oltre che a tutte le configurazioni di rete che DHCP offre, anche un lease time, cioè il lasso di tempo durante il quale l’indirizzo IP è valido. 3. Richiesta DHCP: Il client sceglie tra le offerte dei server dopodiché invia un pacchetto di DHCPREQUEST in broadcast, indicando all’interno del pacchetto quale server ha selezionato. Anche questo pacchetto raggiunge tutti i server DHCP presenti sulla rete. 4. Conferma DHCP: Il server che è stato selezionato conferma l’assegnazione dell’indirizzo con un pacchetto di DHCPACK (nuovamente indirizzato in broadcast all’indirizzo di livello datalink del client); gli altri server vengono automaticamente informati che la loro offerta non è stata scelta dal client, e che sulla sottorete è presente un altro server DHCP. Sicurezza DHCP Il client si identifica verso il server attraverso un campo client-id dei pacchetti DHCP. Questo campo normalmente ha come valore il mac address della scheda di rete per cui si richiede l’indirizzo. Questa è l’unica forma di autenticazione disponibile ed è piuttosto debole, in quanto utilizza un dato che viene inviato in broadcast sulla rete locale, e quindi può essere facilmente trovato da qualunque host connesso alla stessa rete. Un host malevolo, connesso alla rete, e configurato come server DHCP potrebbe rispondere ad una richiesta DHCP e fornire come gateway di default il proprio mac address. A questo punto l’host malevolo potrà sniffare tutto il traffico generato dal client, e tramite IP masquerading può ridirigere le connessioni verso il gateway ufficiale (MITM). Per prevenire questi attacchi, alcuni switch offrono la funzionalità DHCP snooping che permette di fermare i pacchetti che non sono originati da server autorizzati. PROTOCOLLO ICMP Il protocollo ICMP (Internet Control Message Protocol) viene usato da host e router per scambiarsi informazioni a livello di rete, tipicamente riguardanti errori, malfunzionamenti o informazioni di controllo. ICMP è incapsulato direttamente in IP e non è quindi garantita la consegna a destinazione di tali pacchetti (best effort). ICMP può essere usato per veicolare diversi tipi di messaggi di gestione, identificati dal tipo e dal relativo codice. PROTOCOLLO IPv6 Nei primi anni ’90 l’IETF diede inizio alla versione successiva del protocollo IPv4. La prima problematica affrontata fu quella dello spazio di indirizzamento. I 4 miliardi di indirizzi possibili con IPv4 stavano per terminare. Inoltre sulla base dell’esperienza accumulata, i progettisti colsero l’occasione per apportare altre migliorie e risolvere diverse problematiche:  spazio di indirizzamento  routing  sicurezza (confidenzialità, integrità, autenticazione)  configurazione automatica  servizi di tipo real-time (IPv6 cerca di garantire un servizio efficiente a differenza di IPv4) L’indirizzo di rete è lungo 268 bit, cioè 32 cifre esadecimali. Questo porta il numero di indirizzi esprimibili dall’IPv6 a 2128 = 1632 = 3,4 x 1038. Viene definito un nuovo tipo di indirizzo, anycast, che si riferisce ad un insieme di interfacce. Un pacchetto inviato ad un indirizzo anycast, viene recapitato ad una delle interfacce che fanno parte dell’insieme da esso individuato (tipicamente quella più vicina secondo la metrica utilizzata dal protocollo di routing. L’header è stato semplificato. Alcuni campo sono stati eliminati o resi opzionali. Ciò ha consentito che, malgrado gli indirizzi IPv6 siano 4 volte più lunghi di quelli di IPv4, l’header del primo è soltanto il doppio di quello del secondo. Viene introdotto il supporto per la Quality of Service , cioè una funzionalità che permette di etichettare (flow label) i pacchetti appartenenti a flussi di dati particolari per i quali si richiede un trattamento di tipo non default. L’header consiste di due parti: header principale ed extension headers. Gli extension headers sono introdotti per ospitare opzioni aggiuntive tra le quali opzioni per la gestione del routing, della frammentazione, dell’autenticazione e della sicurezza.  vers: indica il numero della versione del protocollo IP  prio: livello di priorità del datagramma  flow label: associato alla QoS richiesta  payload lenght: lunghezza del payload  next Hdr: tipo di header che segue quello IPv6 (es. 6 per pacchetti TCP e 16 per UDP)  hop limit: contatore del numero di hops (analogo a TTL)  source address: indirizzo del mittente  destination address: indirizzo del destinatario Differenze con l’header IPv4  checksum: rimossa completamente per ridurre il tempo di processamento nei router ad ogni hop;  options: previste, ma non nell’header. È possibile inserirle nel payload utilizzando il next header;  ICMPv6: nuova versione di ICMP. Le priorità dei pacchetti possono essere: Il meccanismo degli header, incapsulati nel payload funziona come segue: Frammentazione Un’altra differenza sostanziale con IPv4 è la modalità di frammentazione dei pacchetti. In IPv4 la frammentazione avviene all’occorrenza sui router intermedi, quando il pacchetto è più grande del MTU del router. In IPv6 la frammentazione viene effettuata invece in modalità end-to-end. Se un IPv6 datagram ha dimensioni maggiori della MTU, questo viene scomposto (dalla sorgente) in datagrammi più piccoli, detti frammenti, ognuno dei quali contiene una parte del payload relativo all’IP datagram originale. Il livello Network prima di inviare il datagramma richiede all’interfaccia di rete di destinazione la sua MTU per poter eventualmente effettuare la frammentazione. L’header non è frammentabile ed è inviato con ciascun frammento. Questa frammentazione avviene con l’ausilio di un particolare extension header, detto Fragment Header, identificato dal valore 44 nel campo Next Header. L’header in questione contiene i campi relativi alla frammentazione presenti anche nell’header dell’IPv4 (fragment offset, M, identification). In questo modo si riduce l’overhead dei router, in modo che essi possano gestire più pacchetti per unità di tempo. Indirizzi IPv6 Gli indirizzi sono rappresentati come 8 gruppi di 4 cifre esadecimali separati dal carattere : Se uno dei gruppi è composto da una sequenza di quattro zeri può essere contratto ad un solo zero; Una sequenza di zeri contigui (e una soltanto) composta da 2 o più gruppi può essere contratta con :: Di seguito sono riportate varie rappresentazione dello stesso indirizzo 2001:0db8:0000:0000:0000:0000:1428:57ab 2001:0db8:0000:0000::1428:57ab 2001:0db8:0:0:0:0:1428:57ab 2001:0db8:0::0:1428:57ab 2001:0db8::1428:57ab Inoltre possono essere omessi gli zeri inziali di ogni gruppo: 2001:db8:2de::e13 Gli ultimi 32 bit possono essere scritti in decimale, nella notazione dotted decimal, rendendo così la sintassi IPv6 retro compatibile con quella IPv4. Esistono due rappresentazioni per gli IPv4 utilizzando indirizzi IPv6. IPv4-mapped address I primi 80 bit sono posti a 0, i successivi 16 sono posti a 1 (ffff) e gli ultimi 32 rappresentano l’IPv4. 0:0:0:0:0:ffff:192.168.0.1 ::ffff:192.168.0.1 IPv4-compatible address I primi 96 bit sono posti a 0 e gli ultimi 32 rappresentano l’indirizzo IPv4 (deprecati in favore di mapped ) 0:0:0:0:0:0:192.168.0.1 ::192.168.0.1 Transizione IPv4/IPv6 Il passaggio nella rete Internet del protocollo di livello rete IP dalla versione 4 alla versione 6 ha portato ingenti problemi di compatibilità. La politica naturalmente adoperabile consisterebbe nel costruire router e switch in grado di interpretare entrambi i protocolli. Questo risulta di difficile applicazione per la vastità dei router da sostituire nel mondo. Si adottano dunque soluzioni software quali dual stack o tunneling. La tecnica del dual stack prevede l’utilizzo del doppio stack IP, nella pila protocollare. Questo è di semplice implementazione ma aumenta la complessità della rete, nel senso che i router e gli switch devono interpretare più istanze dello stesso protocollo. Inoltre non risolve il problema dell’indirizzamento, perché ogni interfaccia deve comunque essere dotata di un indirizzo IPv4 e uno IPv6. La tecnica del tunneling è quella più utilizzata. Il principio del tunneling stabilisce un collegamento point to point tra due host. I pacchetti IPv6 vengono incapsulati dall’host sorgente in pacchetti IPv4 (nel payload), inviati nel tunnel, e una volta giunti a destinazione, l’host li decapsula e li tratta come se fossero comuni pacchetti IP. Indirizzi Speciali È stato definito un certo numero di indirizzi speciali riservati ad usi particolati. Nella notazione CIDR:  ::/128 – indirizzo composto da tutti zeri utilizzato per inizializzare l’host prima che esso conosca il proprio indirizzo.  ::1/128 – indirizzo di loopback utilizzato per identificare la macchina locale (localhost) su cui i programmi sono in esecuzione  ::/96 – utilizzato per interconnettere le due tecnologie IPv4/IPv6 nelle reti ibride (deprecati)  ::ffff:0:0/96 – indirizzo IPv4 mapped address utilizzato nei dispositivi dual stack  fe80::/10 – il prefisso link-local specifica che l’indirizzo è valido solo sullo specifico link fisico  ff00::/8 – indirizzo multicast PROTOCOLLO ARP Una volta noto l’indirizzo IP di destinazione, la scheda di rete per indirizzare il frame alla destinazione deve conoscere l’indirizzo fisico della scheda di rete dell’host di destinazione. La mappatura tra indirizzo fisico MAC e indirizzo IPv4 è fornita dal protocollo ARP, address resolution protocol. Il suo analogo in IPv6 è NDP (Neighbor Discovery Protocol). ARP è un protocollo di servizio, utilizzato in una rete che utilizzi il protocollo di rete IP sopra un livello di datalink che supporti il servizio broadcast. Per inviare un pacchetto IP ad un host della stessa sottorete, è necessario incapsularlo in un pacchetto a livello di datalink, che dovrà avere come indirizzo di destinazione il MAC Address dell’host destinatario. ARP è utilizzato per ottenere questo indirizzo. Se il pacchetto deve essere inviato ad un host di un’altra sottorete, ARP è utilizzato per recuperare il MAC Address del gateway o del router che interfaccia le due reti. In ogni host il protocollo ARP tiene traccia delle risposte precedentemente ottenute in una ARP Cache per evitare di dover utilizzare continuamente ARP prima di inviare ciascun pacchetto al destinatario (overhead). Le informazioni contenute nella cache vengono cancellate tipicamente dopo 5 minuti. 1. L’host che vuole conoscere il MAC Address di un altro host sulla stessa rete di cui conosce l’IP (ad esempio tramite DNS) invia in broadcast una ARP Request contenente il proprio indirizzo MAC e l’indirizzo IP del destinatario. 2. Tutti gli host collegati alla rete ricevono la richiesta 3. In ciascun host, il protocollo ARP verifica, confrontando l’IP proprio con quello inviato, se viene richiesta il proprio indirizzo MAC; 4. L’host di destinazione che riconosce il proprio indirizzo IP, provvede ad inviare una risposta ARP Reply contenente il proprio MAC direttamente all’host mittente (in unicast) Questo protocollo è applicato in maniera identica quando un host deve recuperare un MAC Address di un host su un'altra rete. Il protocollo in questo caso è utilizzato per recuperare il MAC Address del gateway (il cui indirizzo IP è settato nella configurazione della scheda di rete) che inoltrerà poi la richiesta all’host destinatario. Formato del pacchetto ARP Ogni scambio di pacchetti ARP avviene tramite incapsulamento di questi all’interno di frame di livello datalink (ad esempio frame Ethernet), così come sono incapsulati i pacchetti IP. Il campo protocol type nell’header discrimina i pacchetti. Il pacchetto ARP è costituito dai seguenti campi:  Hardware type: specifica il tipo di interfaccia hw su cui l’utente cerca una risposta, per Ethernet si setta il campo 1;  Protocol type: indica il tipo di indirizzo ad alto livello che il mittente ha fornito, per IP si setta a 0x0800  Hardware len e Protocol len: consentono di usare ARP su reti arbitrarie perché specificano la lunghezza dell’indirizzo hardware (MAX) e dell’indirizzo del protocollo di alto livello (IP);  ARP operation: ARP Request (valore 1), ARP Reply (valore 2), RARP Request (3), RARP Reply (4). Proxy ARP È una tecnica di utilizzo del protocollo ARP per fornire un meccanismo ad hoc di routing, che non richiede la configurazione dell’indirizzo IP del default gateway sugli host. Un router che implementa il Proxy Arp risponde alle richieste ARP per tutti gli host che appartengono a reti che sa come raggiungere, fingendo che il proprio indirizzo MAC corrisponda a quello degli host di ciascun indirizzo IP richiesto. In questo modo gli host non avranno bisogno di configurare un router di default. ARP Spoofing La costruzione di un pacchetto ARP ingannevole è semplice ed infatti questa è una tra le maggiori vulnerabilità delle reti locali. Inviando ad un host un ARP REPLY opportunamente contraffatto possiamo modificare la sua cache ARP, ottenendo ad esempio la possibilità di intercettare dati destinati ad altri host (MITM). Questa tecnica è detta ARP Spoofing o ARP Cache Poisoning. PROTOCOLLO RARP Il Reverse Resolution Address Protocol è un protocollo usato per risalire all’indirizzo IP conoscendo l’indirizzo fisico MAC. Opera come ARP a livello di collegamento e in pratica svolge l’operazione inversa rispetto al protocollo di risoluzione degli indirizzi ARP. La traduzione è necessaria in quanto la maggior parte delle reti locali collegate a Interne impiega un metodo diverso per indirizzare un messaggio al computer di destinazione. Situazioni tipiche in cui si rende necessario l’utilizzo di questo protocollo riguardano per lo più sistemi diskless. Questi al momento dell’accensione caricano un’immagine del sistema operativo da un server remoto, per cui l’unica informazione di cui dispongono è l’indirizzo fisico della scheda di rete. RARP consente di mandare una richiesta di IP in broadcast, agli altri host connessi in rete. In generale la richiesta arriva ad un server RARP che contiene l’indirizzo di risposta nei propri file di configurazione. Il fatto che RARP utilizzi il meccanismo di broadcast significa che l’utilizzo è limitato all’interno di una subnet, e che quindi i messaggi RARP non possono essere inoltrati dai router. Questo protocollo è infatti diventato obsoleto e sostituito dal BOOTP (BOOTstrap Protocol) o DHCP. CAPITOLO 5 – LIVELLO DI RETE: Piano di controllo Il piano di controllo del livello di collegamento, come abbiamo visto, racchiude la logica globale di rete che controlla come i datagrammi sono instradati tra i router su un percorso end-to-end tra sorgente e destinazione. Nel definire la tecnica con la quale le tabelle di inoltro e dei flussi vengano calcolate possono essere adottati due approcci:  Controllo locale: l’algoritmo di instradamento viene eseguito su ogni singolo router, all’interno del quale vengono effettuate sia le funzioni di inoltro (piano dei dati) che quelle di instradamento (piano di controllo). Ogni router ha un componente di instradamento che comunica con le componenti di instradamento degli altri router per calcolare la propria tabella di inoltro. I protocolli OSPF E BGP sono basati su tale approccio.  Controllo logicamente centralizzato: il controller centralizzato calcola e distribuisce le tabelle di inoltro che devono essere utilizzate da ogni router. Il controller interagisce i control agent di ogni router i quali non partecipano attivamente all’elaborazione della tabella di inoltro. Le architetture SDN utilizzano tale approccio. ALGORITMI DI INSTRADAMENTO Gli algoritmi di instradamento hanno lo scopo di determinare i percorsi, o cammini , tra le sorgenti e le destinazioni attraverso la rete di router. Tipicamente il percorso migliore è quello che ha un costo minimo, anche se nella pratica giocano un ruolo importante anche problematiche di interesse concreto, quali possono essere le policy adottate dalle parti interagenti (es. un utente della rete potrebbe non voler far passare i pacchetti per determinati router.). Per formulare i problemi di instradamento, le reti sono modellate attraverso dei grafi:  I nodi rappresentano i router della rete;  Gli archi rappresentano i link fisici che connettono i vari router della rete. Ad un arco è associato un valore che ne indica il costo. Nel grafo d’esempio, gli archi non sono orientati (sono bidirezionali), ragion per cui si presume un costo uguale per entrami i versi di percorrenza. In generale un link può non essere simmetrico, e presentare un costo diverso per ognuno dei versi. Dati due nodi qualsiasi, esistono più percorsi che li congiungono, ciascuno con il proprio costo (somma dei costi di tutti gli archi attraversati). L’obiettivo di un algoritmo di instradamento è l’individuazione dei percorsi a costo minimo tra la sorgente e la destinazione. In generale si distinguono, in base al tipo di controllo adottato, due macro classi di algoritmi:  Algoritmi centralizzati: sono algoritmi globali che ricevono in ingresso tutti i collegamenti tra i nodi e i relativi costi. Quindi “consci” del grafo della rete possono determinare il percorso a costo minimo;  Algoritmi decentralizzati: il percorso a costo minimo è calcolato in modo distribuito e iterativo. Nessun nodo possiede informazioni complete sul costo di tutti i collegamenti di rete. Inizialmente i nodi conoscono solo i costi dei collegamenti a loro incidenti. Attraverso un processo iterativo, e tramite lo scambio di informazioni con i nodi adiacenti un nodo gradualmente calcola il percorso a costo minimo. Si dice che un singolo nodo deve prendere una decisione a livello globale sulla base di informazioni locali. Un secondo criterio per classificare gli algoritmi di instradamento li suddivide in:  Algoritmi statici (non adattivi): non basano le loro decisione di routing su misurazioni o stime del traffico corrente e della tipologia. La scelta dei percorsi da usare è calcolata in anticipo e caricata nei router.  Algoritmi dinamici (adattivi): i percorsi sono individuati e aggiornati automaticamente in funzione delle modifiche di topologia o di traffico. Parametri del processo decisionale Una metrica è la misura di quanto buono è un percorso, ricavata dalla trasformazione di una grandezza fisica (o di una combinazione di essere), in forma numerica (costo), al fine di scegliere il percorso a costo inferiore come percorso migliore. La scelta della metrica va fatta in funzione del tipo di traffico (campo TOS del pacchetto IP) e inoltre prendendo in considerazione alcuni fattori rilevanti:  non-ottimizzazione: il compito del router è inoltrare il traffico degli utenti, non passare il tempo a fare routing. Conviene sempre prediligere soluzioni che, pur non essendo pienamente ottimizzate, non compromettono la funzionalità primaria della rete;  complessità: più criteri vengono combinati, più l’algoritmo diventa complesso e richiede risorse computazionali in fase di esecuzione;  stabilità: una metrica basata sulla banda disponibile, ad esempio, è troppo instabile, poiché dipende dal carico istantaneo di traffico, che è molto variabile nel tempo;  inconsistenza: le metriche adottate dai nodi nella rete devono essere coerenti per evitare il rischio di cicli di pacchetti tra due router che utilizzano metriche differenti in conflitto. Parametri correntemente usati per definire una metrica, e quindi confluiscono nel costo del link sono:  Bandwidth: capacità di un link, tipicamente definita in bit per secondo;  Delay: il tempo necessario per spedire un pacchetto da una sorgente ad una destinazione;  Load: una misura del carico di un link;  Reliability: o affidabilità riferita, ad esempio, all’error rate di un link;  Hop count: numero di salti effettuati, cioè il numero di router da attraversare lungo il cammino. Dal punto di vista dell’instradamento è comodo intendere la rete come un insieme di sistemi autonomi (AS) ognuno dei quali si occupa di gestire autonomamente e uniformemente il routing interno alla propria interrete. Per cui è possibile, ed è in pratica quello che succede, che i diversi AS adottino metriche e algoritmi di routing diversi tra di loro. L’importante che la scelta sia omogenea all’interno della rete. TECNICHE DI ROUTING La funzione principale di un router è quella di determinare i percorsi che i pacchetti devono seguire per arrivare a destinazione, partendo da una data sorgente. Ogni router si occupa quindi del processo di ricerca di un percorso per l’instradamento di pacchetti tra due nodi. Le principali tecniche utilizzate sono:  Routing by Network Address: ogni pacchetto contiene l’indirizzo del nodo destinatario, il quale viene usato come chiave di accesso alla tabella di routing. Questa tecnica è molto semplice da implementare ed è utilizzata tipicamente nei protocolli non connessi (es IP);  Label Swapping: consiste nell’inserimento di un’etichetta (label) all’interno di ogni pacchetto in transito. Quando un end-system ha necessità di instaurare una connessione con un altro end- system remoto, il primo invierà una richiesta di path-setup (instaurazione del percorso) alla rete, durante la quale, ogni router preparerà l’opportuna serie di etichette da utilizzare durante quella connessione. Dunque non è necessario indicare in ogni pacchetto il mittente. Il percorso è univocamente determinato in fase di preparazione del percorso. UPDATE E TRANSITORI Lo scambio delle informazioni tra i nodi (router) della rete che permette l’aggiornamento delle tabelle di routing può essere effettuato secondo due metodologie:  Broadcast periodico: i router possono trasmettere agli altri router informazioni circa la raggiungibilità delle reti di propria competenza ad intervalli regolari di tempi. Risulta inefficiente, in quanto si spediscono informazioni anche quando non è cambiato nulla rispetto all’update predente;  Event-driven: in questo caso gli update sono inviati solo quando è cambiato qualcosa nella topologia oppure nello stato della rete (costo link). Questa tecnica garantisce un uso più efficiente della banda disponibile. I cambiamenti di stato con i conseguenti update danno luogo a fasi di transitorio: non è possibile aggiornare contemporaneamente tutti i nodi di un sistema distribuito, poiché una variazione è propagata nella rete a velocità finita. Durante il transitorio le informazioni di stato nella rete possono essere inconsistenti (alcuni nodi hanno già le informazioni nuove, mentre altri hanno ancora le informazioni vecchie). Il tempo utile perché il transitorio si estingua è chiamato tempo di convergenza e dipende dal particolare algoritmo di routing implementato. Due problemi comuni affliggono gli algoritmi di instradamento durante il transitorio:  Black Hole: i pacchetti verso una data destinazione sono inviati ad un router il quale, non disponendo di un percorso per la destinazione, li scarta;  Routing loop: un router invia un pacchetto su un link ma, a causa di un’inconsistenza nelle tabelle di instradamento, il router all’altra estremità del link lo rispedisce indietro, creando path ciclici. Può provocare una saturazione del link se i pacchetti non sono scartati (eccessivo time to live). ALGORITMI DISTANCE VECTOR L’instradamento distance vector, noto anche come routing Bellman-Ford, è un tipo di algoritmo di routing dinamico, che tiene conto del carico istantaneo della rete. È un algoritmo di tipo: - distribuito nel senso che ciascun nodo riceve parte dell’informazione da uno o più dei suoi neighbors (vicini) direttamente connessi, a cui, dopo aver effettuato il calcolo, restituisce i risultati. - Iterativo nel senso che questo processo si ripete fino a quando non avviene ulteriore scambio informativo tra vicini. È dunque anche auto-terminante. - Asincrono: nel senso che non richiede che tutti i nodi operino al passo con gli altri. Concettualmente l’algoritmo misura la distanza di ogni singolo router dagli altri nodi della rete ricevendo i dati dai router vicini collegati. A partire da tali dati, utilizzando l’algoritmo di Bellman-Ford, il router costruisce una tabella che indica per ogni entry:  Un nodo della rete raggiungibile  Il next hop  Il numero di hop necessari per raggiungere la destinazione (o altra metrica per il costo) Periodicamente il router aggiorna il proprio vettore delle distanze e comunica la propria tabella ai vicini. I router che ricevono tale messaggio aggiornano la propria tabella modificando le informazioni sui cammini aggiunti, modificati o cambiati. Dopo sufficienti scambi di informazioni, ciascun router potrà avere una riga per ogni altro nodo della rete. Esempio: Il distance vector è un algoritmo di facile implementazione e richiede risorse computazionali limitate, quindi hardware nei router economico, però presenta alcuni svantaggi:  Ogni messaggio deve contenere un’intera tabella di routing, il che occupa molta banda.  La convergenza può essere piuttosto lenta, proporzionale al link e al router più lento della rete. Se lo stato della rete cambia velocemente, le rotte possono risultare inconsistenti.  Può scatenare routing loop dovuti a particolari cambiamenti nella topologia. Nella pratica, per il calcolo dei percorsi a costo minimo l’algoritmo si avvale della Formula di Bellman-Ford dx(y) = minv{c(x,y) + dv(y)} Con v sono denotati tutti i vicini di x. Se dopo aver viaggiato da x ad un generico vicino v, consideriamo il percorso a costo minimo da v a y, il costo del percorso sarà c(x,y)+dv(x). Dato che per raggiungere y, partendo da x, dobbiamo iniziare viaggiando verso qualche vicino v, il costo minimo da x a y è il minimo di c(x,v)+dv(y) calcolato su tutti i nodi. Un nodo x quando vede il cambiamento di costo di uno dei collegamenti direttamente connessi o quando riceve da qualche vicino un vettore aggiornato (linea 9-10) aggiorna la propria stima del vettore delle distanze (linea 15 e 21) e, se si verifica un cambiamento nel costo del percorso a costo minimo (linea 23), trasmette ai propri vicini il proprio nuovo vettore delle distanze (linea 24). Problema del conteggio all’infinito Il distance vector funziona in teoria, ma in alcuni casi, sebbene converga al risultato corretto, può farlo molto lentamente. In particolare reagisce rapidamente alle “buone notizie” e lentamente alle “cattive notizie”. Questo significa che, ad esempio, in uno scenario in cui il costo del collegamento da y a x passa da 4 ad 1, l’algoritmo provocherà i seguenti eventi: - All’istante t0, y rileva il cambiamento nel costo del collegamento (da 4 a 1), aggiorna il proprio vettore delle distanze e informa i vicini del cambiamento. - All’istante t1, z riceve l’aggiornamento da y e aggiorna la propria tabella, calcola un nuovo costo minimo verso x (che passa da 5 a 2) e invia il nuovo vettore delle distanze ai vicini - All’istante t2, y riceve l’aggiornamento di z e aggiorna la propria tabella delle distanze. I costi minimi di y non cambiano e y non manda alcun messaggio a z. Dopo due interazioni l’algoritmo raggiunge uno stato di quiete. - Prendiamo in considerazione lo scenario in cui il costo di un collegamento tra x e y aumenta da 4 a 60. - All’istante t0, y rileva che il costo del collegamento è passato da 4 a 60 e calcola il suo nuovo percorso a costo minimo con la formula Dy(x) = min {c(y,x)+Dx(x), c(y,z)+Dz(x)} = min {60+0, 1+5}=6 Ovviamente se si avesse una visione globale della rete sarebbe ovvio che il nuovo costo attraverso z è errato. Ma l’unica informazione che il nodo y possiede è che il costo diretto verso x è 60 e che z ha ultimamente detto a y di essere in grado di raggiungere x con un costo di 5. All’istante t, abbiamo un istradamento ciclico: al fine di giungere a x, y fa passare il percorso per z e z lo fa passare per y. - Dato che il nodo y ha calcolato un nuovo costo minimo verso x, informa z del suo nuovo vettore delle distanze al tempo t1 - In un istante successivo, z riceve il nuovo vettore delle distanze di y, che indica che il costo minimo di y verso x è 6, sa che può giungere a y a costo 1 e quindi calcola un nuovo costo minimo verso x pari a Dz(x) = min {50+0, 6+1} = 7. Dato che il costo minimo di z verso x è aumentato, z informa y del suo nuovo vettore delle distanze al tempo t2. - Y determina un altro costo minimo verso x che è 8 e invia a z il suo nuovo vettore. Il ciclo prosegue per 44 interazioni, fino a quando z considera il costo del proprio percorso attraverso y maggiore di 50. A questo punto, z determina che il percorso a costo minimo verso x è quello con costo 50. Il problema descritto viene talvolta detto problema di conteggio all’infinito e dimostra che le “cattive notizie” viaggiano senza dubbio assai lentamente. Algoritmo Split Horizon È una algoritmo che cerca di prevenire i routing loops (count to infinity). Esso impedisce ad un router di inviare informazioni di route al router da cui le ha apprese. Un modello avanzato di questa tecnica è detto Poison Reverse. Il router invierà un’informazione allo stesso router da cui l’ha ricevuta, ma con una metrica “infinita”, comunicando di fatto a quel router che per lui la destinazione è irraggiungibile. Lo scopo è simile alla modalità semplice, ma con una maggiore efficacia contro gli anelli di routing. La tecnica descritta può essere utile a volte, ma non rappresenta una soluzione generale al problema. Infatti se i cicli non riguardano semplicemente due nodi adiacenti, essi non verranno rilevati. Nell’esempio raffigurato quando il link tra C e D si interrompe, C setterà la sua distanza da D ad infinito. Però, A userà B per andare a D e B userà A per andare a D. Dopo questi update, sia A che B riporteranno un nuovo percorso da C a D (diverso da infinito). ALGORITMI LINK STATE In un instradamento link state la topologia di rete e tutti i costi dei collegamenti sono noti, ossia disponibili in input all’algoritmo. Ciò si ottiene facendo inviare a ciascun nodo pacchetti sullo stato (Link State Packet) dei suoi collegamenti a tutti gli altri nodi della rete, ossia in broadcast. Ciascun nodo esegue in maniere indipendente l’algoritmo per determinare il cammino minimo per raggiungere ogni nodo della rete ponendosi come radice dell’albero dei cammini minimi. Questo tipo di approccio al routing è utilizzato in alcuni protocolli di instradamento, e soprattutto nel protocollo OSPF. Questi tipi di algoritmi presentano diversi vantaggi:  Possono gestire reti composte da un gran numero di nodi;  Convergono rapidamente al cammino minimo;  Difficilmente generano cammini ciclici;  È facile da comprendere poiché ogni nodo ha la mappa della rete. Il principale svantaggio di un algoritmo Link State è la complessità di realizzazione, anche dovuta alla notevole capacità di memoria ed elaborazione richiesti dai router stessi. Per il funzionamento del protocollo è fondamentale il pacchetto LSP che contiene:  Informazioni relative allo stato di ogni link connesso al router  L’identità di ogni vicino connesso all’altro estremo del link  Il costo del link  Numero di sequenza per l’LSP: trasmessi continuamente per aggiornare lo stato della rete.  Una checksum per capire se l’LSP è stato corrotto nel viaggio;  Lifetime: la validità di ogni LSP è limitata nel tempo. LSP flooding Ogni nodo della rete, come abbiamo detto, inoltra in broadcast, a tutti i suoi collegamenti, il suo LSP. Da un punto di vista globale gli LSP si diffondono su tutta la rete tramite un meccanismo di flooding. La trasmissione avviene periodicamente ogni tot secondi, oppure quando viene rilevata una variazione nella topologia locale (adiacenze) ossia:  Viene riconosciuto un nuovo vicino  Il costo verso un vicino è cambiato  Si è persa la connettività verso un vicino precedentemente raggiungibile. Gestione degli LSP Quando un nodo riceve un pacchetto LSP confronta il numero di sequenza del pacchetto con quello dell’ultimo pacchetto ricevuto da quel nodo: - Se il numero di sequenza indica che il pacchetto è più recente di quello memorizzato, il nuovo pacchetto viene memorizzato e inoltrato a tutti i nodi collegati, eccetto quello da cui è stato ricevuto; - Se il numero di sequenza è invariato il pacchetto viene scartato; - Se il numero di sequenza indica che il pacchetto ricevuto è meno recente di quello memorizzato, quest’ultimo viene trasmesso al nodo mittente. Ogni nodo memorizza i pacchetti ricevuti e costruisce una mappa completa e aggiornata della rete mantenuta in un Link State Database (uguale per tutti). Quest’ultimo può essere rappresentato con una tabella che mostra quali router è in grado di raggiungere un router con relativo costo del link o anche tramite una matrice di raggiungibilità, dove sulle righe ci sono tutte le destinazioni, sulle colonne tutti i mittenti e ogni casella rappresenta il costo del collegamento tra sorgente e destinazione. Routing La conoscenza topologica non è sufficiente di per sé a determinare i percorsi, perché anche se sono noti i costi dei singoli collegamenti tra i router non si hanno conoscenze sufficienti per stabilire i percorsi globali tra i router. Sono necessari algoritmi di Forwarding, ad esempio quello di Dijkstra, per elaborare il Link State Database e produrre il Forwarding Database. Sulla base di ogni singola destinazione, l’algoritmo decide qual è il next hop attraverso un calcolo nel quale ogni nodo si mette come radice di un albero e raggiunge con le sue foglie tutti gli altri nodi della rete. Il forwarding database contiene per ogni nodo destinazione l’insieme delle coppie {path, collegamento in uscita} e la dimensione di tale insieme. ALGORITMO DI DIJKSTRA Ogni nodo ha a disposizione il grafo della rete ed utilizza l’algoritmo per costruire lo Spanning Tree del grafo, ovvero l’albero dei cammini di costo minimo. Ad ogni nodo si assegna un’etichetta che rappresenta il costo massimo per raggiungere quel nodo. L’algoritmo modifica le etichette cercando di minimizzarne il valore e di renderle permanenti. L’algoritmo è di tipo iterativo: ad ogni interazione si determina il costo minimo verso un altro nodo, e se n è il numero di nodi della rete, alla n-esima interazione il forwarding è completo per l’intera rete.  C(i,j): costo del collegamento tra i e j. Se non c’è un collegamento il costo è infinito. Assumiamo il costo simmetrico, anche se non è strettamente necessario.  D(v): il costo attualmente calcolato del percorso che va dalla sorgente al nodo v.  P(v): predecessore nel cammino di costo minimo dalla sorgente fino a v.  N: insieme dei nodi per i quali la distanza minima è stata trovata. Alla fine dell’algoritmo, questo N deve coincidere con la totalità dei nodi sulla rete L’algoritmo consiste in un passo di inizializzazione, più un ciclo di durata pari al numero di nodi della rete. Al termine avremo i percorsi più brevi dal nodo sorgente a tutti gli altri nodi. Consideriamo una rete di esempio fatta di sei nodi. Si vuole trovare il minimo spanning tree che collega A con tutti gli altri nodi della rete. Si esegue l’algoritmo Step 0 : Al passo di inzializzazione, nell’insieme N è incluso solo il nodo A. Tutti i nodi che non sono direttamente collegati ad A hanno distanza da A infinita, mentre i nodi direttamente collegati presentano come costo il costo del collegamento diretto. Step 1 : Si entra nel ciclo. Viene scelto uno dei nodi che non stanno nello spanning tree e soprattutto quello che ha costo minimo (D) e viene aggiunto allo spanning tree. E’ stato trovato in effetti il percorso a costo minimo che collega A a D. Vengono ricalcolate le distanze per i nodi raggiungibili da D (B,C ed E). Step 2 : Viene scelto il nodo che ha costo minimo da D. Step 3: … Problematiche In un algoritmo di questo tipo se il costo del link è proporzionale al traffico su quel link, cioè viene scelta una metrica che porti in conto livello di congestione del link, allora è possibile che si creino oscillazioni. L’algoritmo periodicamente, infatti, ricalcolerà le route instradando i pacchetti verso i link meno trafficati, rendendoli di fatto più trafficati rispetto a prima. Periodicamente il traffico oscilla tra diversi rami, mentre sarebbe preferibile che questo traffico si distribuisse uniformemente. CONFRONTO LS E DV Nel DV ciascun nodo dialoga solo con i vicini direttamente connessi, informandoli delle stime a costo minimo da sé stesso a tutti i nodi (che conosce) nella rete. Nel LS, ciascun nodo dialoga con tutti gli altri nodi via broadcast, ma comunica loro solo i costi dei collegamenti direttamente connessi.  Complessità dei messaggi: LS richiede che ciascun nodo conosca il costo di ogni collegamento nella rete. Ciò implica l’invio di O(|N|*|E|) messaggi. Inoltre ogni qualvolta cambia il costo di un collegamento, il nuovo costo deve essere comunicato a tutti i nodi. A ogni interazione l’instradamento DV richiede scambi di messaggi tra nodi adiacenti. Il tempo di convergenza può dipendere da molti fattori. Quando cambiano i costi dei collegamenti, l’instradamento DV propaga i risultati dei costi cambiati se il nuovo costo ha causato la variazione del percorso a costo minimo per uno o più nodi connessi a tale collegamento.  Velocità di convergenza: l’implementazione di LS è un algoritmo O(|N|2) che richiede O(|N|*|E|) messaggi. L’algoritmo del DV può convergere lentamente e può presentare cicli di instradamento e anche il problema del conteggio all’infinito.  Robustezza: Con LS un router può comunicare via broadcast un costo sbagliato per uno dei suoi collegamenti connessi (ma non per altri). Un nodo può anche alterare o eliminare i pacchetti ricevuti in broadcast LS. Ma i nodi LS si occupano di calcolare soltanto le proprie tabelle di inoltro, e gli altri nodi effettuano calcoli simili per quanto li riguarda. Ciò significa che i calcoli di instradamento sono in qualche modo isolati, il che fornisce un certo grado di robustezza. Con DV, un nodo può comunicare percorsi a costo minimo errati a tutte le destinazioni. ROUTING IN INTERNET Il modello semplificato utilizzato per la trattazione degli algoritmi di instradamento era quello che vedeva la rete come un insieme di router interconnessi, ognuno di questi indistinguibile dagli altri, nel senso che eseguivano tutti lo stesso algoritmo per calcolare le route. Questo modello risulta un po' semplicistico e presenta diverse problematiche:  Scalabilità: al crescere del numero di router, il tempo richiesto per calcolare, memorizzare e comunicare le informazioni di instradamento diventa proibitivo.  Autonomia amministrativa: Internet è una rete di ISP che generalmente desiderano gestire i propri router liberamente e in modo diversificato all’interno della rete. Questi problemi possono essere risolti organizzando la rete in Autonomous System , generalmente composti da gruppi di router amministrato da un’unica autorità. Ogni AS deve essere identificato con un AD number (16 bit) assegnato da ICANN. I router di uno stesso AS eseguono lo stesso algoritmo di instradamento. Ogni AS è responsabile del routing interno delle sue reti ed inoltre tutti gli AS devono scambiarsi informazioni di raggiungibilità tramite un routing esterno. Le tabelle di routing interne di un AS sono mantenute da algoritmi come :  RIP (distance vector)  OSPF (link state)  IGRP (Interior Gateway Routing Protocol) Le tabelle di routing esterne di un AS sono mantenute invece da :  EGP (Exterior Gateway Protocol), ormai obsoleto  BGP (Border Gateway Protocol): approccio path vector CAPITOLO 6 – LIVELLO TRASPORTO Un protocollo a livello di trasporto mette a disposizione una comunicazione logica tra processi applicativi di host differenti. Per comunicazione logica si intende, dal punto di vista dell’applicazione, che tutto proceda come se gli host che eseguono i processi fossero direttamente connessi. La differenza con il livello di rete e che se quest’ultimo di preoccupa del trasferimento e della consegna dei dati tra end-system, il livello di trasporto si occupa del trasferimento e smistamento dati tra processi residenti su determinati end-system. I processi applicativi usano la comunicazione logica fornita dal livello di trasporto per scambiare messaggi, senza preoccuparsi dell’infrastruttura fisica utilizzata per trasportarli. I messaggi ricevuti dal livello applicativo sono incapsulati in pacchetti a livello di trasporto detti segmenti. È un livello generalmente implementato nei sistemi periferici, ma non neri router della rete. Uno dei servizi fondamentali del livello di trasporto è quello aumentare l’efficienza e l’affidabilità non garantite dai livelli superiori. Una rete TCP/IP, e in particolare Internet, mette a disposizione del livello di applicazione due diversi protocolli: UDP (user datagram protocol), che fornisce alle applicazioni un servizio non affidabile e non orientato alla connessione, e TPC (trasmission control protocol), che offre un servizio affidabile e orientato alla connessione. Come visto, lo sviluppatore dell’applicazione sceglie tra UDP e TCP durante la creazione delle socket. I modelli di servizio offerti da UDP e TCP hanno i seguenti compiti fondamentali:  Estendere il servizio di consegna IP tra sistemi periferici a quello di consegna tra processi in esecuzione sui sistemi periferici. Il passaggio da consegna host-to-host a consegna process-to- process viene detto multiplexing e demultiplexing a livello di trasporto.  Fornire un controllo di integrità includendo campi per il riconoscimento di errori nelle intestazioni dei propri segmenti. Questi due servizi minimi a livello di trasporto sono gli unici offerti da UDP. In particolare UDP, come IP, costituisce un servizio inaffidabile e cioè non garantisce che i dati inviati da un processo arrivino intatti (e neppure che arrivino) al processo destinatario. TCP, d’altra parte, offre alle applicazioni diversi servizi aggiuntivi che permettono di fornire un trasferimento dati affidabile:  Controllo di flusso  Acknowledgement  Timer  Controllo di congestione Multiplexing e Demultiplexing Per multiplexing e demultiplexing si intende il passaggio del servizio di trasporto da host a host (fornito con dal livello di rete) a un servizio di trasporto da processo a processo per le applicazioni in esecuzione sugli host. Nell’host destinatario il livello di trasporto riceve segmenti dal livello di rete immediatamente sottostante. Il livello di trasporto ha il compito di consegnare i dati di questi segmenti al processo applicativo appropriato in esecuzione nell’host. Un processo può gestire una o più socket, attraverso le quali i dati fluiscono dalla rete al processo e viceversa. Per cui il livello di trasporto nell’host di ricezione in realtà non trasferisce i dati direttamente a un processo, ma piuttosto ad una socket che fa da intermediario. Nello stesso istante saranno presenti più socket aperte in riferimento ad un unico processo (identificata univocamente). Il compito di trasportare i dati dei segmenti a livello di trasporto verso la giusta socket viene detto demultiplexing. Il compito di radunare frammenti di dati da diverse socket sull’host di origine e incapsulare ognuno con intestazioni a livello di trasporto per creare segmenti e passarli al livello di rete, viene detto multiplexing. Il multiplexing e il demultiplexing è realizzato inserendo all’interno dei segmenti UDP e TCP gli identificatori delle socket:  Campo del numero di porta di origine  Campo del numero di porta di destinazione Quando arriva un segmento all’host, il livello di trasporto esamina il numero della porta di destinazione e dirige il segmento verso la socket corrispondente. I dati del segmento passano, quindi, dalla socket al processo assegnato. Mux e Demux Connectionless Quando un processo in esecuzione crea una socket UDP, il livello di trasporto le assegna automaticamente un numero di porta compreso tra 1024 e 65535 che non sia ancora utilizzato. In alternativa le si può assegnare uno specifico numero di porta con il metodo bind(). Quando un processo su un host A con porta x vuole inviare un blocco di dati a un processo con porta y nell’host B, il livello di trasporto di A crea un segmento che include i dati, il numero di porta di origine (x) e il numero di porta di destinazione (y). Il livello di trasporto passa il segmento risultante al livello di rete, che lo incapsula in un datagramma IP, ed effettua un tentativo best-effort di consegna del segmento all’host in ricezione. Se il segmento arriva all’host B, il suo livello di trasporto esamina il numero di porta di destinazione del segmento e lo consegna alla propria socket identificata da y. È da ricordare che una socket UDP viene identificata completamente da una coppia che consiste di un indirizzo IP e di un numero di porta di destinazione. Di conseguenza, se due segmenti UDP se hanno stesso indirizzo IP e porta di destinazione, saranno diretti sulla stessa socket qualunque sia l’indirizzo e la porta di origine. Per quanto riguarda indirizzo e porto di origine, questi sono inclusi nei segmenti come indirizzi di ritorno nel caso l’host B voglia rispondere all’host A. Mux e Demux Connection-oriented La differenza tra una socket TCP e una UDP risiede nel fatto che la prima è identificata da quattro parametri: indirizzo e porta di origine, indirizzo e porta di destinazione. Pertanto quando un segmento TCP giunge alla rete di un host, quest’ultimo utilizza i quattro parametri per dirigere (fare demultiplexing) il segmento verso la socket appropriata. Al contrario di UDP, due segmenti TCP in arrivo, aventi indirizzi IP di origine o numeri di porta di origine diversi, saranno sempre diretti a due socket differenti, anche a fronte di indirizzo IP e porta di destinazione uguali. PROTOCOLLO UDP UDP, User Datagram Protocol, definito in RFC 768, fa praticamente il minimo che un protocollo di trasporto debba fare. A parte la funzione di multiplexing/demultiplexing e una forma di controllo degli errori molto semplice, non aggiunge nulla a IP. UDP prende i messaggi dal processo applicativo, aggiunge il numero di porta di origine e di destinazione per il mux/demux, aggiunge altri due piccoli campi e passa il segmento risultante al livello di rete. Questi incapsula il segmento in un datagramma IP ed effettua un tentativo di consegna all’host di destinazione in modalità best-effort. In UDP non esiste handshaking tra le entità di invio e di ricezione a livello trasporto per questo motivo si dice non orientato alla connessione. Nonostante la mancanza di garanzie, per molte applicazioni è preferibile UDP a TCP per i seguenti motivi:  Controllo più fine a livello applicazione su quali dati sono inviati e quando (TCP dispone di un meccanismo di controllo della congestione che può ritardare l’invio). Utile per applicazioni in tempo reale.  Nessuna connessione stabilita e nessun relativo ritardo.  Nessuno stato di connessione per cui non è necessario includere buffer di ricezione e invio, parametri per il controllo della congestione, parametri sul numero di sequenza e di acknowledgment. Un server UDP può supportare molti più client attivi rispetto ad un server TCP.  Minor spazio usato per l’intestazione del pacchetto. L’intestazione dei pacchetti TCP aggiunge 20 byte, mentre UDP solo 8. Segmenti UDP L’intestazione UDP presenta solo quattro campi di due byte ciascuno.  I numeri di porta consentono all’host di destinazione di trasferire i dati applicativi al processo corretto (Demultiplexing)  Il campo lunghezza specifica il numero di byte del segmento UDP (header + dati) ed è necessario perché la lunghezza del campo dati può essere diversa tra un segmento e quello successivo.  La checksum è utilizzata dall’host ricevente per verificare se sono avvenuti errori nel segmento. La checksum UDP serve per il rilevamento degli errori. Viene utilizzato per determinare se i bit del segmento UDP sono stati alterati durante il loro trasferimento da sorgente a destinazione. Lato mittente UDP effettua il complemento a 1 della somma di tutte le parole da 16 bit nel segmento, e l’eventuale riporto finale viene sommato al primo bit. Tale risultato viene posto nel campo checksum del segmento UDP. UDP mette a disposizione un checksum, anche se molti protocolli a livello di collegamento prevendono il controllo degli errori, perché non c’è garanzia che tutti i collegamenti tra sorgente e destinazione controllino gli errori. Si mette a disposizione così a livello di trasporto un meccanismo di verifica su base end-to-end. TRASMISSIONE DATI AFFIDABILE SU UN CANALE CON ERRORI Il compito dei protocolli di trasferimento dati affidabile è l’implementazione di un’astrazione di un canale affidabile tramite il quale si possono trasferire i dati. Con un canale affidabile vengono evitati:  Presenza di errori  Perdita di pacchetti  Ordine dei pacchetti non garantito  Duplicazione di pacchetti E sono introdotti:  Controllo di flusso  Controllo di congestione In un modello semplificato, in cui il protocollo di trasferimento presenti al livello sottostante un canale di trasmissione non affidabile in cui l’unico problema è che i bit di un pacchetto possono essere corrotti è necessario:  Rilevamento dell’errore: è richiesto un meccanismo che consenta al destinatario di rilevare gli errori sui bit. Vengono utilizzate delle notifiche (acknowledgement) positive o negative per comunicare al mittente cosa sia stato ricevuto correttamente e cosa no, chiedendone quindi il rinvio.  Feedback del destinatario: dato che mittente e destinatario sono generalmente in esecuzione su sistemi periferici diversi, l’unico modo che ha il mittente per conoscere la visione del destinatario consiste nel feedback esplicito del destinatario. Le risposte di notifica positiva ACK e negativa NAK.  Ritrasmissione: un pacchetto ricevuto con errori sarà ritrasmesso dal mittente. In un protocollo che utilizza questi strumenti, e cioè rilevamento dell’errore e notifiche positive e negative: 1. Il protocollo di trasporto lato mittente attende i dati da raccogliere dal livello superiore 2. Quando si verifica l’evento, il lato mittente crea un pacchetto contenente i dati da inviare, insieme al checksum e spedisce il pacchetto. 3. Il lato mittente si mette in attesa di un pacchetto ACK o NAK dal destinatario. a. Se riceve un ACK sa che il pacchetto trasmesso più di recente è stato ricevuto correttamente e pertanto il protocollo ritorna allo stato di attesa dei dati provenienti dal livello superiore b. Se riceve un NAK il protocollo ritrasmette l’ultimo pacchetto e attende una risposta alla ritrasmissione È importante osservare che quando il mittente è nello stato di attesa di ACK o NAK non può recepire dati dal livello superiore. Quindi il mittente non invia nuovi dati finché non è certo che il destinatario abbia ricevuto correttamente il pacchetto corrente. Problema ACK NAK corrotti L’osservazione da fare è che gli stessi pacchetti di ACK e NAK possono essere corrotti. Se un ACK o un NAK è corrotto, il mittente non ha modo di sapere se il destinatario abbia ricevuto correttamente l’ultimo blocco di dati trasmessi. La soluzione a questo problema potrebbe essere semplicemente quella che prevede, in ogni caso, il rinvio da parte del mittente qualora l’ACK o il NAK risulti alterato. Con questa soluzione ovviamente, se il pacchetto dati trasmesso arriva correttamente la prima volta, in seguito ad un ACK corrotto, con il relativo rinvio si introdurranno dei pacchetti duplicati. Conseguentemente il destinatario, non sapendo se l’ultimo ACK inviato sia stato ricevuto correttamente dal mittente, non può sapere a priori se un pacchetto in arrivo è frutto di una ritrasmissione o è un pacchetto contenente dati nuovi. La soluzione generale al problema consiste nell’aggiungere un campo al pacchetto dati, obbligando il mittente a numerare i propri pacchetti dati con un numero di sequenza nel nuovo campo. Al destinatario sarà sufficiente controllare questo numero per sapere se il pacchetto ricevuto rappresenti o meno una ritrasmissione. In accordo con ciò, i pacchetti ACK e NAK non devono indicare il numero di sequenza per non essere confusi con i pacchetti dati. Protocollo senza NAK In un'altra versione del protocollo, si possono avere le stesse funzionalità del protocollo descritto precedentemente, utilizzando però solo notifiche di ACK. Possiamo ottenere lo stesso effetto di un NAK spedendo piuttosto un ACK per il più recente pacchetto ricevuto correttamente. Un mittente che riceve due ACK per lo stesso pacchetto (ossia riceve ACK duplicati) sa che il destinatario non ha ricevuto correttamente il pacchetto successivo a quello confermato due volte. Il destinatario deve ora includere il numero di sequenza del pacchetto di cui invia l’acknowledgement all’interno del messaggio ACK, e il mittente deve ora controllare il numero di sequenza del pacchetto confermato da un messaggio ACK ricevuto. TRASMISSIONE DATI AFFIDABILE SU UN CANALE CON PERDITE E ERRORI Supponiamo ora che il canale di trasmissione, oltre a danneggiare i bit, possa anche smarrire i pacchetti. Il protocollo ora deve preoccuparsi di due aspetti aggiuntivi:  Rilevare lo smarrimento di pacchetto  Cosa fare quando avviene la perdita Supposto che il mittente spedisca un pacchetto dati e che questo o l’ACK corrispondente del ricevente vada smarrito, se questo è disposto ad attendere un tempo sufficiente per essere certo dello smarrimento del pacchetto, allora può semplicemente ritrasmettere il pacchetto. Il problema è quello di quantificare questo timeout. Certamente, il mittente deve attendere almeno per il minimo ritardo di andata e ritorno tra mittente e destinatario più il tempo richiesto per l’elaborazione di un pacchetto da parte del destinatario. In molte reti questo ritardo relativo al caso peggiore è difficile perfino da stimare ed inoltre il protocollo dovrebbe ipoteticamente risolvere la perdita di dati prima possibile e quindi è inefficiente aspettare il ritardo peggiore calcolabile. Nella pratica l’approccio adottato è scegliere in modo assennato un valore di tempo tale per cui la perdita di pacchetti risulta probabile, anche se non garantito. Se non si riceve un ACK in questo lasso di tempo, il pacchetto viene ritrasmesso. Ragionevolmente, se un pacchetto sperimenta un ritardo particolarmente largo, ma comunque arriva a destinazione, il mittente potrebbe ritrasmetterle introducendo pacchetto duplicati sula canale. Il protocollo gestisce i duplicati con il meccanismo introdotto precedentemente dei numeri di sequenza. Implementazione del timeout Implementare un meccanismo di ritrasmissione basato sul tempo richiede un contatore in grado di segnalare al mittente l’avvenuta scadenza di un dato lasso di tempo. Il mittente dovrà essere in grado: 1. Inizializzare il contatore ogni volta che invia il pacchetto 2. Rispondere a un interrupt generato dal timer con l’azione appropriata 3. Fermare il contatore Un riepilogo del funzionamento del protocollo fin qui descritto è rappresentato di seguito. Il protocollo è detto Stop&Wait o anche ad alternanza di bit dato che i numeri di sequenza dei pacchetti si alternano tra 0 e 1. TRASFERIMENTO DATI AFFIDABILE CON PIPELINE Il protocollo mostrato precedentemente è corretto dal punto di vista funzionale, ma non ottimo dal punto di vista prestazionale proprio per il fatto che si tratta di un protocollo stop-and-wait. Se definiamo l’utilizzo del canale come la frazione di tempo in cui il mittente è stato effettivamente occupato nell’invio di bit sul canale, un’analisi delle prestazioni mostra che il protocollo presenta effettivamente un throughput molto basso. Una soluzione a questo problema è quello di consentire al mittente di inviare più pacchetti senza attendere gli acknowledgement. Se si consente al mittente di trasmettere, ad esempio, tre pacchetti senza aspettare gli ACK, l’utilizzo viene sostanzialmente triplicato. Dato che molti pacchetti in transito dal mittente al destinatario possono essere visualizzati come il riempimento di una tubatura, questa tecnica è nota come pipelining. Le conseguenze su un protocollo di trasferimento dati affidabile sono le seguenti:  L’intervallo di numeri di sequenza disponibili deve essere incrementato, dato che ogni pacchetto in transito deve presentare un numero di sequenza e univoco e che ci potrebbero essere più pacchetti in transito ancora in attesa di acknowledgement.  I lati di invio e ricezione dei protocolli possono dover memorizzare in un buffer più di un pacchetto e in particolare quei pacchetti trasmessi, ma il cui acknowledgement non è ancora stato ricevuto. Si possono identificare due approcci di base verso la risoluzione degli errori con pipeline: Go-Back-N e Selective Repeat. Go-Back-N In un protocollo di questo tipo il mittente può trasmettere più pacchetti senza dover attendere alcun acknowledgement, ma non può avere più di un dato numero massimo consentito N di pacchetti in attesa di acknowledgement nella pipeline. Se definiamo base come il numero di sequenza del pacchetto più vecchio che non ha ancora ricevuto un acknowledgement e nextseqnum il più piccolo numero di sequenza inutilizzato, allora si possono identificare quattro intervalli di numeri di sequenza.  Il primo gruppo corrisponde ai pacchetti già trasmessi e che hanno ricevuto acknowledgement.  Il secondo intervallo corrisponde ai pacchetti inviati, ma che non hanno ancora ricevuto alcun acknowledgement.  I numeri di sequenza del terzo intervallo possono essere per i pacchetti da inviare immediatamente, nel caso arrivassero dati dal livello superiore.  I numeri di sequenza maggiori o uguale a base+N non possono essere utilizzati finchè il mittente non riceva un acknowledgement relativo a un pacchetto che si trova nella pipeline ed è ancora privo di riscontro. L’intervallo di numeri di sequenza ammissibili per i pacchetti trasmessi, ma che non hanno ancora ricevuto alcun acknowledgement, può essere visto come una finestra di dimensione N. Quando il protocollo è in funzione, questa finestra trasla lungo lo spazio dei numeri di sequenza. Il principale motivo per il quale è necessario imporre un limite al mittente sul numero i pacchetti in sospeso N è il controllo di flusso. Il mittente GBN deve rispondere a tre tipi di evento:  Invocazione dall’alto: quando dall’alto si chiama send(), come prima cosa il mittente controlla se la finestra sia piena, ossia se vi siano N pacchetti in sospeso senza acknowledgement. Se la finestra non è piena, crea e invia un pacchetto e le variabili vengono aggiornate di conseguenza. Se la finestra è piena, il mittente restituisce i dati al livello superiore che, presumibilmente, ritenterà più tardi. In una reale implementazione è più probabile che il mittente mantenga questo dato nei buffer o implementi un meccanismo di sincronizzazione (semaforo o flag) che consenta al livello superiore di invocare send() solo quando la finestra non sia piena.  Ricezione di un ACK: nel protocollo GBN, l’acknowledgement del pacchetto con il numero di sequenza n verrà considerato un acknowledgement cumulativo, che indica che tutti i pacchetti con un numero di sequenza minore o uguale a n sono stati correttamente ricevuti dal destinatario.  Evento del timeout: In presenza di pacchetti persi o eccessivamente in ritardo, come nei protocolli stop-and-wait, si usa ancora un contatore per risolvere il problema. Quando si verifica un timeout, il mittente invia nuovamente tutti i pacchetti spediti che ancora non hanno ricevuto acknowledgement. Se si riceve un ACK, ma ci sono ancora pacchetti aggiuntivi trasmessi e non riscontrati, il timer viene fatto ripartire. Se, invece, non ci sono pacchetti in sospeso in attesa di acknowledgement, il contatore viene fermato. Le azioni del destinatario:  Se un pacchetto con numero di sequenza n viene ricevuto correttamente ed è in ordine il destinatario manda un ACK per quel pacchetto e consegna i suoi dati al livello superiore.  In tutti gli altri casi, il destinatario scarta i pacchetti e rimanda un ACK per il pacchetto in ordine ricevuto più di recente. Essendo i pacchetti consegnati uno alla volta al livello superiore, se il pacchetto k è stato ricevuto e consegnato, tutti i pacchetti con un numero di sequenza inferiore di k sono anch’essi consegnati. Si potrebbe pensare di storare in un buffer i pacchetti arrivati fuori sequenza, per poi trasferirli riordinati al livello superiore. Il motivo per cui il destinatario scarta questi pacchetti, anche se questi sono stati ricevuti correttamente è che se al tempo t0 è stato ricevuto il pacchetto n+1 ma il pacchetto n va perduto, sia quest’ultimo, sia il pacchetto n+1 verranno ritrasmessi. La conseguenza è che se il mittente deve mantenere i limiti superiore e inferiore della propria finestra e la posizione nextseqnum all’interno di tale finestra, il destinatario deve mantenere solo il numero di sequenza del successivo pacchetto nell’ordine (salvato nella variabile expectedseqnum) Esempio: la figura mostra come opera un protocollo GBN con una finestra di 4 pacchetti. Il mittente invia i pacchetti da 0 a 3, ma poi deve attendere la notifica di ricezione di uno di loro prima di poter procedere. Quando giungono i successivi ACK (ACK0 e ACK1), la finestra scorre in avanti e il mittente può trasmettere un nuovo pacchetto (pkt4 e pkt5). Dal lato ricevente il pacchetto 2 viene perso e pertanto i pacchetti 3,4 e 5 non rispettano l’ordine e sono scartati. Discussione: potenzialmente il protocollo GBN consente al mittente di riempire il canale del trasporto con i pacchetti, evitando così i problemi di scarso utilizzo del canale riscontrati nei protocolli stop-and-wait. Esistono, tuttavia, scenari in cui lo stesso GBN ha problemi di prestazioni. In particolare quando l’ampiezza della finestra e il prodotto tra larghezza di banda e ritardo sono entrambi grandi, nella pipeline si possono trovare numerosi pacchetti. Un errore su un solo pacchetto può provocare pertanto un elevato numero di ritrasmissioni, in molti casi inutili, che potrebbe saturare la pipeline. Selective Repeat I protocolli a ripetizione selettiva (SR) evitano le ritrasmissioni non necessarie facendo ritrasmettere al mittente solo quei pacchetti su cui esistono sospetti di errore. Questa forma di ritrasmissione a richiesta e personalizzata costringe il destinatario a mandare acknowledgement specifici per i pacchetti ricevuti in modo corretto. Si userà una nuova ampiezza di finestra pari a N per limitare il numero di pacchetti privi di acknowledgement nella pipeline. Tuttavia a differenza di GBN, il mittente avrà già ricevuto gli ACK di qualche pacchetto nella finestra. Eventi e azioni di un mittente SR:  Dati ricevuti dall’alto: Quando si ricevono dati dall’alto, il mittente SR controlla il successivo numero di sequenza disponibile per il pacchetto. Se è all’interno della finestra del mittente, i dati vengono impacchettati e inviati; altrimenti sono salvati nei buffer o restituiti al livello superiore per una successiva ritrasmissione, come in GBN  Timeout: vengono usati ancora i contatori per cautelarsi contro la perdita di pacchetti. Ora però ogni pacchetto deve vere un proprio timer logico, dato che al timeout sarà ritrasmesso un solo pacchetto. Si può realizzare un solo contatore hardware per simulare le operazioni di più timer logici.  ACK ricevuto: se si riceve un ACK, il mittente SR etichetta tale pacchetto come ricevuto, ammesso che sia nella finestra. Se il numero di sequenza del pacchetto è uguale a send_base, la base della finestra si muove verso il pacchetto che non ha ricevuto acknowledgement con il più piccolo numero di sequenza. Se la finestra si sposta e ci sono pacchetti non trasmessi con il numero di sequenza che ora cade all’interno della finestra, questi vengono ritrasmessi. Il destinatario SR invia un riscontro per i pacchetti correttamente ricevuti sia in ordine sia fuori sequenza. Questi vengono memorizzati in un buffer finché non sono stati ricevuti tutti i pacchetti mancanti (ossia quelli con i numeri di sequenza più bassi), momento in cui un blocco di pacchetti può essere trasportato in ordine al livello superiore. Eventi e azioni di un destinatario SR:  Il pacchetto con un numero di sequenza nell’intervallo [rcv_base, rcv_base+N-1] viene ricevuto correttamente. In questo caso, il pacchetto ricevuto ricade all’interno della finestra del ricevente e al mittente viene restituito un ACK selettivo. Se il pacchetto non era già stato ricevuto viene inserito nel buffer. Se presenta un numero di sequenza uguale alla base della finestra di ricezione (rcv_base) allora questo pacchetto e tutti i pacchetti nel buffer aventi numeri consecutivi vengono consegnati al livello superiore.  Viene ricevuto il pacchetto con numero di sequenza nell’intervallo [rcv_base-N, rcv_base-1]. In questo caso si deve generare un ACK, anche se si tratta di un pacchetto che il ricevente già ha riscontrato.  Altrimenti si ignora il pacchetto. Esempio: la figura mostra un esempio di comportamento SR in presenza di pacchetti persi. Inizialmente il destinatario memorizza i pacchetti 3,4,5 nel buffer e li consegna al livello superiore insieme al pacchetto 2 quando quest’ultimo viene finalmente ricevuto. Discussione: è importante notare che il destinatario, come descritto sopra, spedisce un acknowledgment (anziché ignorare) per i pacchetti già ricevuti con certi numeri di sequenza al di sotto dell’attuale base della finestra. Questa nuova notifica è necessaria considerando l’ambito dei numeri di sequenza del mittente e del destinatario. Per esempio tra destinatario e mittente non si propaga un ACK per il pacchetto con numero di sequenza send_base, il mittente ritrasmetterlo anche se il destinatario lo ha già ricevuto. Se il destinatario non invia un acknowledgement per questo pacchetto, la finestra del mittente non può avanzare. Non sempre mittente e destinatario hanno la stessa visuale su che cosa sia stato ricevuto correttaemente Manca esempio pag 214-217, ultima slide LivelloTrasporto2 Riepilogo dei meccanismi di trasferimento dati affidabile e loro utilizzo Meccanismo Uso e commenti Checksum Utilizzato per rilevare errori sui bit in un pacchetto trasmesso Timer Serve a far scadere un pacchetto e ritrasmetterlo, forse perché il pacchetto (o il suo ACK) si è smarrito all’interno del canale. I timeout si possono verificare per via dei ritardi anziché degli smarrimenti (timeout prematuro), o quando il pacchetto è stato ricevuto dal destinatario, ma è andato perduto il relativo ACK dal destinatario al mittente. Per questi motivi il destinatario può ricevere copie duplicate di un pacchetto. Numero di sequenza Usato per numerare sequenzialmente i pacchetti di dati che fluiscono tra mittente e destinatario. Le discontinuità nei numeri di sequenza di pacchetti ricevuti consentono al destinatario di rilevare i pacchetti persi. I pacchetti con numero di sequenza ripetuto consentono di rilevare pacchetti duplicati. Acknowledgement positivo (ACK) Utilizzato dal destinatario per comunicare al mittente che un pacchetto o un insieme di pacchetti sono stati ricevuti correttaemente. Gli acknowledgement trasporteranno generalmente i numeri di sequenza dei pacchetti da confermare. A seconda del protocollo, i riscontri possono essere individuali o cumulativi. Acknowledgement negativo (NAK) Usato dal destinatario per comunicare al mittente che un pacchetto non è stato ricevuto correttamente. Gli acknowledgement negativi trasporteranno generalmente il numero di sequenza del pacchetto che non è stato ricevuto correttamente. Finestra e pipelining Il mittente può essere forzato a inviare soltanto pacchetti con numeri di sequenza che ricadono in un determinato intervallo. Consentendo a più pacchetti di essere trasmessi e non aver ancora ricevuto acknowledgement si può migliorare l’utilizzo del canale rispetto alla modalità operativa stop-and-wait. L’ampiezza della finestra può essere impostata sulla base della capacità del destinatario di ricevere e memorizzare messaggi in un buffer, su quella del livello di congestione della rete, o su entrambe.. TRASPORTO ORIENTATO ALLA CONNESSIONE: PROTOCOLLO TCP Le caratteristiche principali del protocollo TCP sono:  Connection-oriented: TCP è un protocollo orientato alla connessione in quanto, prima di effettuare lo scambio dei dati, i processi devono effettuare un three-way handshake. È detto a tre vie perché i processi devono scambiarsi tre segmenti al fine di instaurare la connessione. Come parte dell’instaurazione della connessione TCP, entrambe le parti inizializzano molte variabili di stato associate alla connessione;  Full duplex data: su una stessa connessione TCP tra due processi residenti su due host diversi, il flusso di dati è bidirezionale, cioè può fluire contemporaneamente nelle due direzioni.  End-to-end : si tratta di una connessione end-to-end tra due host, in quanto lo stato della connessione risiede completamente nei due sistemi periferici, per cui gli elementi intermedi di rete sono completamente ignari della connessione;  Punto a punto: ha luogo tra un singolo mittente e un singolo destinatario (non è realizzabile il multicast);  Senza errori, sequenza ordinata  Pipelined: controllo di lusso e di congestione impostano la TCP window  Controllo di flusso: il mittente non invia più di quanto il ricevente non possa accettare;  Buffer su mittente e ricevente: TCP dirige i dati al buffer di invio della connessione, uno dei buffer riservato durante l’handshake a tre via, da cui di tanto in tanto preleverà blocchi di dati e li passerà al livello di rete. La massima quantità di dati prelevabili e posizionabili in un segmento viene limitata dalla dimensione massima di segmento (MSS, maximum segment size). Questo valore viene generalmente impostato determinando prima la lunghezza del frame più grande che può essere inviato a livello di collegamento dall’host mittente locale, la cosiddetta unità trasmissiva massima (MTU) e poi scegliendo un MSS tale che il segmento TCP (una volta incapsulato in un datagramma IP) stia all’interno di un singolo frame a livello di collegamento, considerando anche la lunghezza dell’intestazione TCP/IP normalmente pari a 40 byte. OSS. L’MSS rappresenta la massima quantità di dati a livello applicazione nel segmento e non la massima dimensione del segmento TCP con intestazioni incluse. OSS. I protocolli Ethernet e PPP hanno un MTU di 1500 byte per cui un valore tipico di MSS è di 1460 byte. OSS. Sono stati proposti approcci per scoprire la MTU più grande lungo il percorso tra sorgente e destinazione per impostare MSS sulla base di quel valore. Struttura dei segmenti TCP La Protocol Data Unit (PDU) di TCP è detta segmento. Ciascun segmento viene normalmente imbustato in un pacchetto IP, ed è costituito da un header TCP e da un payload, ovvero dati a livello applicativo. Un segmento TCP è così strutturato:  numeri di porta di origine e destinazione, 16 bit utilizzati per il multiplexing/demultiplexing  il campo numero di sequenza di 32 bit che indica lo scostamento (in byte) dell’inizio del se

Riassunto Reti di Calcolatori Kurose-Ross (PDF)

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue