Reti di Calcolatori
a.a. 2005/06
Lezione 14
Reti di Calcolatori
Andrea Frosini
1
Nel modello di riferimento:
Application
Transport
Network
Data Link
Fisico
Reti di Calcolatori
Andrea Frosini
2
Controllo della congestione
Il controllo della congestione della communication subnet è uno dei compiti
fondamentali del livello Network
Non è da confondere con il controllo del flusso!
Il controllo del flusso è relativo ad una singola connessione tra due entità sorgente
e destinazione: un canale di comunicazione (gestito a livello Data Link), un
circuito virtuale (gestito a livello Network), una connessione tra due applicazioni
(gestito a livello Transport o superiore)…
Il controllo della congestione è globale, ossia relativo all’intera communication
subnet, ed è svolto dal livello Network o dal livello Transport
Reti di Calcolatori
Andrea Frosini
3
Cause della congestione
Si verifica congestione quando un router non è più in grado di gestire i pacchetti che
gli arrivano
E’ un meccanismo a cascata, perché i pacchetti scartati causano ritrasmissioni (da
parte dei router vicini a quello congestionato oppure da parte degli host trasmittenti)
Generalmente la congestione è dovuta a componenti della subnet non adeguati per
gestire il carico:
• troppi pochi buffer in un router (ma una
quantità infinita di buffer nei router non
necessariamente allevia la congestione)
• processore troppo lento in un router
• linea di trasmissione troppo lenta
Reti di Calcolatori
Andrea Frosini
4
Tipologie di controllo della congestione
• open loop (senza contro-reazione):
– corretto dimensionamento degli elementi della communication subnet
– opportune strategie per accettazione di nuovi pacchetti o nuove connessioni
– opportune strategie di scheduling dei pacchetti nei router
– opportune scelte per i parametri dei protocolli di livello Data Link, Network e Transport
– non è adattivo
• closed loop (con contro-reazione):
– monitorizza il sistema per rilevare quando e dove si verifica congestione
– invia le informazioni nei luoghi in cui si può rimediare
– modifica i parametri dei protocolli per correggere il problema
Reti di Calcolatori
Andrea Frosini
5
Traffic shaping
Una delle principali difficoltà nel controllo della congestione è che il traffico è spesso
di tipo burst (alte punte di traffico in tempi brevi alternate a lunghi periodi di traffico
più basso)
Un metodo per controllare la congestione consiste nel modellare il traffico (traffic
shaping) in modo da renderlo predicibile
E’ un approccio di tipo open loop (non adattivo)
• algoritmo leaky bucket
• algoritmo token bucket
Reti di Calcolatori
Andrea Frosini
6
Algoritmo leaky bucket I
L’algoritmo leaky bucket (secchio che perde) regolarizza il traffico uscente da un host
ritardando il traffico “burst”:
• è basato su un buffer a coda (queue) di dimensione finita
• i pacchetti possono essere rimossi dalla coda e trasmessi ad una frequenza
massima prefissata
• se la coda si riempie completamente, nuovi pacchetti vengono scartati
• se i pacchetti hanno dimensione variabile, si può modificare l’algoritmo in modo
da inviare byte con frequenza massima prefissata
Reti di Calcolatori
Andrea Frosini
7
Algoritmo leaky bucket II
Host
Livello Fisico
Reti di Calcolatori
Andrea Frosini
8
Algoritmo token bucket I
L’algoritmo token bucket (secchio di gettoni) è simile all’algoritmo leaky bucket, ma è
più flessibile nel tagliare il traffico di tipo burst e non perde pacchetti quando la coda
è piena. In pratica si consentono irregolarità “controllate” nel flusso in uscita sulla rete
• Il secchio contiene gettoni (token) e non pacchetti
• Per spedire un pacchetto si deve prelevare un gettone dal secchio
• Nuovi gettoni vengono immessi nel secchio ad intervalli di tempo regolari (ad
esempio, uno ogni millisecondo)
• Il secchio ha una capacità massima prefissata
Reti di Calcolatori
Andrea Frosini
9
Algoritmo token bucket II
• Se i pacchetti hanno dimensione variabile, un gettone può rappresentare il diritto
di trasmettere un numero prefissato di byte invece di un intero pacchetto
• Le trasmissioni di pacchetti avvengono alla massima velocità possibile del
canale di comunicazione finché il secchio è pieno, poi secondo il tasso di
generazione dei gettoni
• Se il secchio è vuoto, i pacchetti non vengono perduti: l’host deve bloccare e
attendere che venga generato un nuovo gettone
• Consente alte punte di traffico, ma limita la lunghezza del burst. Per ridurre i
picchi si usa spesso un leaky bucket dopo il token bucket
Leaky bucket e token bucket sono utili per il traffico host-router e router-router
Se il router sorgente deve fermarsi e non ha spazio sufficiente, si può aver perdita
Reti di Calcolatori
Andrea Frosini
10
Flow specification: controllo della congestione
Gli algoritmi di traffic shaping sono molto efficaci quando sono adottati
consistentemente da sorgente, communication subnet e ricevente.
In particolare, sorgente, subnet e ricevente devono accordarsi in anticipo su:
• le caratteristiche del traffico generato (data rate, frequenza dei burst, . . . )
• la qualità del servizio garantita dalla subnet (ritardo di trasmissione, varianza del
tempo di trasmissione (jitter ), tasso di pacchetti persi, . . . )
E’ possibile adottare il flow specification sia nelle subnet organizzate con circuiti virtuali
(più facile) che in quelle organizzate con datagram (più difficile)
Reti di Calcolatori
Andrea Frosini
11
Controllo della congestione con circuiti virtuali
Il metodo più semplice per controllare la congestione delle subnet organizzate con
circuiti virtuali è l’admission control (controllo d’accesso)
Quando viene rilevata congestione in una parte della subnet:
• i nuovi circuiti virtuali vengono instradati su percorsi non sovraccarichi
• se non è possibile trovare un percorso non sovraccarico, viene impedita la
creazione di nuovi circuiti virtuali fino alla scomparsa della congestione
E’ un algoritmo di tipo closed loop, perché si adatta al traffico della subnet
E’ anche possibile utilizzare il flow specification per “prenotare” le risorse della
subnet utilizzate da ciascun circuito virtuale
Reti di Calcolatori
Andrea Frosini
12
Controllo della congestione in subnet basate su datagram
Gli algoritmi closed loop utilizzati nelle subnet a commutazione di pacchetto
possono essere utilizzati anche nelle subnet con circuiti virtuali
In ogni algoritmo closed loop, ciascun router monitorizza l’utilizzo delle sue linee di
comunicazione e delle altre sue risorse
Ad esempio, si associa a ciascuna linea una variabile reale u che rappresenta il
suo utilizzo; ad intervalli regolari la linea viene monitorata e la variabile aggiornata:
unew = a × uold + (1 - a) × f
f rappresenta l’utilizzo istantaneo della linea, ed a  (0, 1) il peso che viene dato
alla storia passata
Reti di Calcolatori
Andrea Frosini
13
Algoritmo choke packet
Se per una certa linea di un router la variabile u supera una soglia prefissata, allora
per ogni pacchetto P che transita su una linea sovraccarica, il router:
• invia un choke packet all’ host sorgente del pacchetto
• prima di ri-trasmettere P al router successivo, imposta un flag nella testata del
pacchetto cosicché il router seguente non generi un altro choke packet
Quando l’ host sorgente riceve un choke packet:
• riduce il tasso di trasmissione (ad esempio, del 50%)
• fa partire un timer ed ignora i choke packet che arrivano prima che il timer scada
• dopo la scadenza del timer:
– se arriva un altro choke packet, riduce ulteriormente il tasso di
trasmissione (ad esempio, per un ulteriore 25%)
– se non arrivano altri choke packet, aumenta gradualmente il tasso di
trasmissione (ad esempio, del 5% alla volta)
Reti di Calcolatori
Andrea Frosini
14
Algoritmo hop-by-hop choke packet
Il principale difetto dell’algoritmo choke packet è la sua lentezza quando il router
congestionato è molto distante dall’ host sorgente oppure la subnet è molto veloce
L’algoritmo hop-by-hop choke packet è una variante del choke packet in cui
ciascun router che riceve il choke packet rallenta il tasso di trasmissione (oltre a
ritrasmettere all’indietro il choke packet stesso)
Il router congestionato ha immediato sollievo
La capacità dei buffer nei router deve essere maggiore
Reti di Calcolatori
Andrea Frosini
15
Internetworking
Per connettere fra loro reti eterogenee si devono superare problemi non banali, tra i
quali:
- Difformità nei formati dei pacchetti e degli indirizzi
- Difformità, nelle subnet, dei meccanismi di controllo dell'errore e della congestione
- Diverse architetture di rete, diversi servizi offerti dai vari livelli, diverse modalità di
indirizzamento, diverse dimensioni massime dei pacchetti
Tecniche
- Bridge livello data link
- Router multiprotocollo: gestione contemporanea di più pile di protocolli
Reti di Calcolatori
Andrea Frosini
16
Router multiprotocollo
Un dispositivo operante a livello Network in grado di gestire pacchetti appartenenti a
reti con diversa architettura di rete è chiamato router multiprotocollo, o anche gateway
Il termine gateway talvolta indica anche dispositivi che operano a livello differente:
ripetitori (livello Fisico) e bridge (livello Data Link), transport gateway e application
gateway
Il termine router multiprotocollo denota un dispositivo che opera solamente a livello
Network
In pratica i dispositivi in vendita hanno caratteristiche tali per cui non è sempre facile
stabilire a quale livello essi operano. Ad esempio, molti dispositivi operano come
ripetitori, come bridge e come router multiprotocollo (brouter)
Reti di Calcolatori
Andrea Frosini
17
Concatenazione di circuiti virtuali
Se tutte le reti interessate offrono servizi della stessa tipologia a livello Network (ad
esempio, connection-oriented affidabile, con determinate garanzie sulla
qualità del servizio, . . . ) è possibile costruire un circuito virtuale che si estende
attraverso più reti eterogenee come concatenazione di circuiti virtuali che
attraversano ciascuno una delle reti (ricordiamo: circuito virtuale = connessione
logica tra due host, anche non consecutivi, della rete).
Ciascun circuito virtuale di una subnet omogenea termina in un router multiprotocollo
che lo collega al circuito virtuale di un’altra subnet e che instrada successivamente i
pacchetti lungo tale circuito virtuale
E’ una tipica strategia di internetworking tra communication subnet organizzate con
circuiti virtuali
Reti di Calcolatori
Andrea Frosini
18
Connectionless internetworking
La strategia connectionless internetworking è utilizzata quando le communication
subnet sono organizzate con datagram
E’ alternativa ai circuiti virtuali concatenati
I pacchetti viaggiano indipendentemente e possono arrivare fuori ordine
rete C
rete B
rete A
router
rete C
Reti di Calcolatori
Andrea Frosini
rete A
router
multiprotocollo
19
Limiti dell’internetworking
Sebbene i router multiprotocollo possano in teoria permettere la comunicazione tra
host in reti con architetture molto differenti tra loro, in pratica questo avviene molto
raramente:
• ciascun host dovrebbe possedere non solo l’indirizzo relativo alla rete di cui fa
parte, ma anche un indirizzo valido per ciascuna rete da cui potrebbe ricevere
pacchetti (IP, DECnet, IPX, SNA, AppleTalk, . . . )
• i formati dei pacchetti nelle due reti possono essere troppo differenti perché una
completa conversione di formato sia possibile
• funzionalità quali trasmissione di pacchetti broadcast, qualità del servizio e
sicurezza potrebbero essere supportate da una rete ma non dall’altra
Quindi anche se i router multiprotocollo possono gestire pacchetti di diverso tipo, le
reti in cui si trovano gli host sorgente e destinazione sono generalmente dello stesso
tipo o almeno “compatibili”
Reti di Calcolatori
Andrea Frosini
20
Tunneling
Il tunneling è una strategia di internetworking che consente di collegare due reti A e
B utilizzanti la stessa architettura tramite una rete C utilizzante una architettura
differente
• Il pacchetto Network proveniente da una rete viene incapsulato da un router
multiprotocollo all’interno di un pacchetto Network della rete C
• Il nuovo pacchetto viaggia normalmente all’interno della rete C fino ad un altro
router multiprotocollo
• Il secondo router multiprotocollo estrae il vecchio pacchetto Network e lo invia sulla
rete B
tunnel
rete C
rete A
Head A
Head A
Head C
Reti di Calcolatori
rete A
Head A
Andrea Frosini
21
Internetworking a livello Transport
Il livello Transport di quasi tutte le architetture di rete offre un servizio di tipo
connection oriented affidabile
E’ quindi naturale definire un meccanismo di internetworking a livello Transport
basato sulla concatenazione di circuiti virtuali
E’ analogo all’internetworking basato sulla concatenazione di circuiti virtuali a livello
Network, ma si appoggia ai protocolli del livello Transport
I dispositivi che svolgono questo servizio sono chiamati transport gateway
Reti di Calcolatori
Andrea Frosini
22
Internetworking a livello Application
Un ulteriore servizio di internetworking può essere offerto dal livello Application da
dispositivi chiamati application gateway
Ad esempio è possibile definire un servizio di posta elettronica che converta il
formato dei messaggi di posta quando sorgente e destinazione sono in reti con
diverse architetture
Ad esempio per inviare un messaggio da un host TCP/IP ad un host OSI:
• si compone il messaggio di posta elettronica nel formato Internet; l’indirizzo è quello
dell’utente OSI, codificato secondo lo standard TCP/IP
• il messaggio viene inviato ad un mail gateway
• il mail gateway converte il messaggio nel formato OSI, e lo invia all’utente OSI
Reti di Calcolatori
Andrea Frosini
23
Internetwork routing
In una internetwork le singole reti componenti sono entità autonome e vengono
chiamate AS (Autonomous System)
Il routing complessivo è a due livelli:
1. Un primo livello è costituito dall'Interior Gateway Protocol (IGP) che identifica
l'algoritmo di routing usato da un AS al proprio interno. Diversi AS possono utilizzare
diversi IGP
2. Un secondo livello è dato dall’Exterior Gateway Protocol (EGP), che è l'algoritmo
che si usa per gestire il routing fra diversi AS. Deve tener conto di specifiche leggi
nazionali (divieto di far transitare dati sul suolo di una nazione ostile), per cui le
decisioni di routing devono adattarsi a tali direttive
Reti di Calcolatori
Andrea Frosini
24
Internet
Una particolare internetwork è chiamata Internet
• è molto grande ed estesa
• è costituita da molti AS (Autonomous Systems) connessi tra loro
• le linee di comunicazione principali sono le backbone: communication subnet con
linee ad alta capacità e router veloci
• ai backbones sono collegati le communication subnet nazionali e regionali
(midlevel subnet)
• alle midlevel subnet sono collegate le LAN di università, compagnie, Internet
service provider, . . .
Reti di Calcolatori
Andrea Frosini
25
Schema di Internet
Reti di Calcolatori
Andrea Frosini
26
Il livello Network dell’IPS
Il livello Network dell’Internet Protocol Suite è il più importante:
• svolge principalmente i servizi di internetworking e routing
• è basato sul protocollo IP (Internet Protocol)
• offre un servizio connectionless non affidabile
• è organizzato con datagram
Reti di Calcolatori
Andrea Frosini
27
Schema del protocollo IP
• riceve i dati dal livello Transport
• incapsula i dati in pacchetti di max 64 Kbyte (in genere la lunghezza è di 1.500 byte)
• instrada i pacchetti sulla subnet, eventualmente frammentandoli
• riassembla (se necessario) i frammenti ricevuti in pacchetti
• estrae dai pacchetti ricevuti i dati del livello Transport
• consegna al livello Transport i dati nell’ordine in cui sono arrivati (che non è
necessariamente quello in cui sono partiti)
Reti di Calcolatori
Andrea Frosini
28
Formato del pacchetto IP
Reti di Calcolatori
Andrea Frosini
29
L’header IP I
• Version (4 bit): numero di versione del protocollo IP
• IHL (4 bit): lunghezza dell’ header del pacchetto in parole da 32 bit (minimo=20
byte, massimo=60 byte)
• Type of service (8 bit, non tutti necessariamente utilizzati): codifica la qualità del
servizio richiesto dall’ host alla communication subnet; in pratica `e ignorato
• Total length (16 bit): lunghezza totale del pacchetto, compreso l’header
(massimo=65535 byte)
• Identification (16 bit): Identificatore del datagram utilizzato in caso di
frammentazione
• DF (1 bit, Don’t Fragment): indica che il datagram non può essere frammentato (il
ricevente non è in grado di riassemblare il pacchetto)
• MF (1 bit, More Fragments): indica che il frammento non è l’ultimo del datagram
Reti di Calcolatori
Andrea Frosini
30
L’header IP II
• Fragment offset (13 bit): posizione relativa del frammento all’interno del datagram
in multipli di 8 byte (non è il numero d’ordine del frammento!)
• Time to live o TTL (8 bit): contatore per limitare la vita del pacchetto; in teoria è
decrementato una volta al secondo, in pratica ad ogni hop; quando raggiunge zero il
pacchetto viene scartato ed un avvertimento inviato all’host sorgente
• Protocol (8 bit): indica quale protocollo deve ricevere i dati nel pacchetto
(generalmente un protocollo di livello Transport come TCP o UDP; in RFC 1700
sono definiti un centinaio di numeri, ma il database completo oggi on-line su
www.iana.org)
• Header checksum (16 bit): bit di controllo per il solo header, calcolati raggruppando
i bit dell’header in parole da 16 bit (escluso il campo Header checksum stesso),
calcolandone la somma in complemento ad 1, e prendendo il complemento ad 1 del
risultato; deve essere ricalcolato ad ogni hop
• Source address (32 bit): network number e host number dell’host sorgente
Reti di Calcolatori
Andrea Frosini
31
L’header IP III
• Destination address (32 bit): network number e host number dell’host destinazione
• Options (da 0 a 10 parole da 32 bit): alcune possibili opzioni sono:
– Security: indica la “segretezza” del datagram
– Strict source routing: indica il percorso che il datagram deve seguire
– Loose source routing: indica alcuni router da includere nel percorso
– Record route: forza ogni router ad appendere il proprio indirizzo IP
– Timestamp: come sopra, ma i router appendono anche un timestamp
In totale sono state definite una ventina di opzioni
In generale le opzioni non sono molto utilizzate, e non tutti i router sono in grado di
gestirle
Reti di Calcolatori
Andrea Frosini
32