FONDAMENTI
Prospettive
Utenti della rete: servizi di cui le loro
applicazioni hanno bisogno (ad esempio,
invio garantito senza errori entro limite
di tempo)
Progettisti della rete: progetto
economicamente effettivo (ad esempio,
utilizzo efficiente ed equo delle risorse)
Fornitori della rete: sistema facile da
amministrare e da gestire (ad esempio,
facilità di isolare i guasti)
Requisiti: connessione
Strumenti base:
collegamenti: cavo coassiale, fibra ottica...
nodi: computer di uso generale...
Collegamenti diretti
punto-punto
accesso multiplo
Connessione indiretta
reti commutate
inter-reti
Una rete può essere definita
ricorsivamente come due o
più nodi connessi da un
collegamento fisico oppure
come due o più reti
connesse da uno o più nodi.
Strategie di commutazione
commutazione di circuito
circuito dedicato per inviare/ricevere un flusso di bit
commutazione di pacchetto
store-and-forward per inviare/ricevere messaggi (pacchetti)
Indirizzi ed instradamento
indirizzo
parola che identifica un nodo
instradamento
determinare come inviare i messaggi a destinazione in base al suo
indirizzo
tipo di indirizzi:
unicast: specifico nodo
broadcast: tutti i nodi sulla rete
multicast: sottoinsieme di nodi sulla rete
Requisiti: condivisione risorse
Condivisione di risorse (nodi e collegamenti)
da parte di più utenti
nodo
nodo
nodo
nodo
nodo
commutatore
commutatore
Strategie comuni di multiplexing:
a divisione di tempo (TDM)
a divisione di frequenza (FDM)
a divisione di tempo ma su richiesta (statistical TDM)
nodo
Pacchetti
Uso di pacchetti per limitare utilizzo
Pacchetti da diverse sorgenti si alternano
Bufferizzazione di pacchetti in attesa
coda di pacchetti gestita come coda (FIFO)
congestione: saturazione del buffer di pacchetti
Funzionalità
Le applicazioni eseguite sui nodi connessi
alla rete devono poter comunicare in
modo da comprendersi
nodo
nodo
applicazione
nodo
applicazione
canale astratto
nodo
nodo
La rete comunemente supporta canali
applicazione-applicazione come:
Richiesta/Risposta: accesso a file, librerie digitali
Flusso di messaggi: applicazioni video
video: sequenza di fotogrammi
risoluzione: 1/4 immagine TV = 352 x 240 pixel
colori a 24-bit: fotogramma = (352 x 240 x 24)/8 = 247.5KB
tasso di trasferimento: 30 fps = 7425KBps (circa 60Mbps)
video su richiesta vs video-conferenza
Problemi
Errori a livello di bit (interferenze)
Errori a livello di pacchetti (congestione)
Mal funzionamento di nodi e collegamenti
Messaggi ritardati
Messaggi consegnati in ordine sbagliato
Ascolto da parte di estranei
Problema chiave: mettere d’accordo ciò che
l’applicazione si aspetta con ciò che la
tecnologia soggiacente fornisce
Prestazioni
Larghezza di banda (throughput)
Quantità di dati che possono essere trasmessi in un’unità
di tempo
Esempio: 10Mbps
Collegamento vs canale astratto
Notazione
KB = 210 byte
Mbps = 106 bit al secondo
Larghezza di banda collegata a “larghezza di un bit”
1Mbps corrisponde a bit di larghezza 1µs
2Mbps corrisponde a bit di larghezza 0.5µs
Ritardo di trasmissione
Tempo richiesto per inviare un bit da un punto A ad un
punto B
Esempio: 24 millisecondi (ms)
Latenza
Latenza = Propagazione + Trasmissione + Coda
Propagazione = Distanza / VelocitàLuce
Trasmissione = Dimensione / LarghezzaBanda
Talvolta conta il tempo andata-ritorno (RTT)
Velocità della luce
3.0 x 108 metri/secondo nel vuoto
2.3 x 108 metri/secondo in un cavo
2.0 x 108 metri/secondo in una fibra
Osservazioni
non ci sono ritardi di coda in collegamenti diretti
larghezza di banda non significativa se Dimensione è 1
bit
latenza applicazione-applicazione include ritardo dovuto
al software che può essere significativo se
Distanza è piccola
Larghezza di banda vs ritardo di trasmissione
messaggi piccoli (ad es., 1 byte):
passare da 1ms a 100ms è più significativo che passare da
1Mbps (Trasmissione = 8µs) a 100Mbps (Trasmissione
= 0.08µs)
messaggi grandi (ad es., 25 MB):
passare da 1Mbps (Trasmissione = 209s) a 100Mbps
(Trasmissione = 2s) è più significativo che passare da
1ms a 100ms
Prodotto latenza x larghezza di banda
latenza
larghezza
di banda
ad es., 100ms e 45Mbps = 560KB di dati (circa)
Architettura di rete
Astrarre per nascondere la complessità
astrazione conduce ad una struttura
a livelli
Applicazione
Canale astratto
Connessione nodo-nodo
Hardware
diverse astrazioni ad ogni livello
Applicazione
Canale
richiesta/
risposta
Canale
flusso di
messaggi
Connessione nodo-nodo
Hardware
Protocolli
Ogni protocollo ha due interfacce
interfaccia di servizio: definisce come usarlo
interfaccia tra entità: definisce come comunica con
l’entità corrispondente nell’altro nodo
nodo
nodo
oggetto di alto livello
protocollo
interfaccia di servizio
interfaccia tra entità
oggetto di alto livello
protocollo
Parola “protocollo” ha due significati
specifica dell’interfaccia tra entità
modulo che realizza tale specifica
Grafo dei protocolli
insieme di protocolli con le loro dipendenze
maggior parte della comunicazione tra entità indiretta
comunicazione tra entità diretta solo al livello hardware
Trasferimento
di file
Libreria
digitale
Video
RRP
MSP
HHP
verso la rete
Incapsulamento
Applicazione
Applicazione
dati
RRP
dati
RRP
RRP dati
HHP
verso la rete
RRP dati
HHP
HHP RRP dati
dal la rete
HHP RRP dati
Architetture Standard
Architettura OSI (Open Systems
Interconnect)
International Standards Organization (ISO)
International Telecommunications Union (ITU),
precedentemente CCITT
serie “X.”: X.25, X.400, X.500
modello di riferimento
Applicazione
Presentazione
Sessione
Trasporto
Rete
nodi dentro
la rete
Collegamento dati
Fisico
Architettura Internet
Internet Engineering Task Force (IETF)
FTP
HTTP
NV
TFTP
Applicazione
TCP
UDP
TCP
UDP
IP
IP
Rete
Caratteristiche
rete
rete
non implica una struttura strettamente a livelli
forma a clessidra
progetto e sviluppo procedono insieme
...
rete
Nodi
Assumiamo computer di uso generale (programmabili) come
le work-station (talvolta considereremo hardware
specializzato) .
CPU
adattatore
di rete
cache
memoria
bus I/O
Memoria finita (quindi buffer limitato)
Connessione alla rete via un adattatore di rete
Processore veloce, memoria lenta
verso la rete
Collegamenti
Cavi
Doppino (cat. 5)
Cavo coassiale (50-ohm)
Cavo coassiale (75-ohm)
Fibra multimodo
Fibra a modo singolo
10-100Mbps, 100m
10-100Mbps, 200m
10-100Mbps, 500m
100Mbps, 2km
100-2400Mbps, 40km
Linee in affitto
T1
T3
STS-1
STS-3
STS-12
STS-24
STS-48
1.544 Mbps
44.736 Mbps
51.840 Mbps
155.250 Mbps
622.080 Mbps
1.244160 Gbps
2.488320 Gbps
Ultimo miglio
POTS
ISDN
xDSL
CATV
28.8-56 Kbps
64-128 Kbps
16 Kbps – 55.2 Mbps
20-40 Mbps
Senza cavo
Teledesic
288 satelliti a 1350 km di altezza
Potenzialmente, 2.048 Mbps
Codifiche
Segnali che si propagano attraverso mezzo
fisico sono digitali/analogici.
Dati sia digitali che analogici: ci limitiamo a
dati digitali.
Problema: codificare i dati binari da inviare in
un segnale che si possa propagare fino alla
destinazione
Bit e segnali
componenti per i segnali
nodo
adattatore
di rete
segnale
adattatore
di rete
nodo
bit
Segnali viaggiano tra due componenti per i
segnali.
Bit viaggiano tra due adattatori.
NRZ (Non-Return to Zero )
bit
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0
NRZ
Problema: molti 1 oppure 0 consecutivi
Segnale basso (0) può essere interpretato come inattività
Segnale alto (1) provoca distorsione del livello medio
Problema: sincronizzazione difficile
NRZI
Non-return to Zero Inverted: esegue una
transizione dal segnale attuale per
codificare un 1, e rimane al segnale
attuale per codificare uno zero.
bit
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0
NRZ
clock
NRZI
Risolve il problema degli 1 consecutivi
Manchester
Trasmette lo XOR dei dati codificati con
NRZ ed il clock
bit
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0
NRZ
clock
Manchester
Efficiente solo al 50%.
4B/5B
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
11110
01001
10100
10101
01010
01011
01110
01111
10010
10011
10110
10111
11010
11011
11100
11101
Ogni 4 bit di dati sono codificati
in 5 bit, in modo che le
parole di codice non hanno
più di uno 0 in testa e non
più di due 0 in coda
Non vi sono mai tre 0 consecutivi
I 5 bit sono trasmessi con NRZI
Raggiunge 80% di efficienza.
Impacchettamento (framing)
Problema: raggruppare sequenza di bit in
pacchetti (frame)
Determinare primo ed ultimo bit di un frame
Tipicamente realizzato dall’adattatore di rete
prende (scarica) frame da (in) memoria del nodo
nodo
adattatore
bit
frame
adattatore
nodo
Protocolli orientati ai byte
8
SYN
SOH
8
HEADER
BODY
8
16
ETX
8
STX
8
SYN
Approccio della sentinella: BISYNC
CRC
Problema: carattere ETX può apparire nel BODY.
Soluzione BISYNC: far precedere ETX e DLE da DLE
Point-to-Point Protocol (PPP)
8
8
8
16
16
8
Flag Address Control Protocol Payload Checksum Flag
8
8
8
SYN
SYN
Class
Approccio di conteggio dei byte (DDCMP)
14
Count
42
HEADER
16
BODY
CRC
Problema: campo Count rovinato (errore di
impacchettamento)
Soluzione: utilizzare il campo di rilevamento dell’errore ed
aspettare il prossimo SYN
Protocolli orientati ai bit
HDLC (High-Level Data Link Control)
Racchiudere il frame con una sequenza
speciale di bit: 01111110
16
01111110 HEADER
16
BODY
CRC
01111110
Riempimento di bit
Mittente: ogni volta che deve trasmettere cinque 1
consecutivi, inserisce uno 0.
Ricevente: se arrivano cinque 1 consecutivi, guarda i bit
successivi:
Se il bit successivo è 0: rimuove il bit
Se i due bit successivi sono 10: sequenza di fine frame
Se i due bit successivi sono 11: errore
Rilevamento di errori
Rilevare errori non è la stessa cosa che correggerli
Due approcci
Avvisare dell’errore e far ritrasmettere
Usare algoritmo di correzione
Idea base dietro ogni metodo di rilevamento degli
errori
Aggiungere k bit di ridondanza ad un messaggio di n bit
da utilizzare per determinare se si sono verificati errori
Parità bidimensionale
bit di parità
dati
byte di parità
0101001
1101001
1011110
0001110
0110100
1011111
1
0
1111011
0
1
1
1
0
Proprietà: rileva errori di 1, 2, e 3 bit e spesso di 4
Algoritmo di checksum Internet
Calcolo:
Messaggio come sequenza di interi a 16 bit
Somma questi interi in aritmetica complemento ad uno
Calcola complemento ad uno del risultato
Includi quest’ultimo numero nel messaggio finale
Verifica:
Messaggio come sequenza di interi a 16 bit
Somma questi interi in aritmetica complemento ad uno
Verifica se risultato è formato da tutti 1
Esempio
Messaggio formato da 8 byte: 00, 01, F2, 03, F4, F5, F6, F7
2 22101101 11112220 Riporti
----------------00000000 00000001
11110010 00000011
11110100 11110101
11110110 11110111
----------------11011101 11110000
00000000 00000010
----------------11011101 11110010 => Checksum = 00100010 00001101
Cyclic Redundancy Check
Aggiunge k bit di ridondanza ad un
messaggio di n bit
Messaggio di n bit visto come polinomio
M(x) in una variabile di grado n-1
ad esempio, 10011010 corrisponde a x7+ x4 + x3 + x1.
k è il grado di un qualche polinomio divisore
C(x)
ad esempio, C(x) = x3+ x2 + 1.
Schema
Trasmettere polinomio P(x) divisibile per C(x) (vedi
esempio), e ricevere polinomio P(x) + E(x)
(dove E(x) rappresenta l’errore)
E(x) = 0 implica che non ci sono errori
Ricevente divide P(x) + E(x) per C(x)
Se il resto è zero, allora:
E(x) era zero (ovvero non ci sono errori), oppure
E(x) è divisibile per C(x)
Scegliere C(x) per evitare il secondo caso
Come ottenere P(x)
Moltiplica M(x) per xk: sia D(x) il risultato
Divide D(x) per C(x): sia R(x) il resto
Invia P(x) = D(x)- R(x)
Esempio
M(x) = x7+ x4 + x3 + x1 (ovvero 10011010)
C(x) = x3+ x2 + 1 (ovvero 1101)
Mittente:
moltiplica M(x) per x3 ottenendo x10 + x7 + x6 + x4 (ovvero
10011010000)
divide risultato per C(x) (ovvero 1101) ottenendo resto
101
invia 10011010000 - 101 = 10011010101 che è divisibile
per C(x)
Proprietà
Errori di un solo bit, se C(x) contiene almeno due
termini.
Due errori di un singolo bit, se C(x) non è divisibile
per x e non divide xk+1 per ogni k minore o
uguale alla lunghezza del frame.
Ogni numero dispari di errori, se C(x) contiene il
fattore (x + 1).
Ogni sequenza di errori consecutivi di lunghezza
minore di k.
molte sequenze di lunghezza maggiore di k possono anche essere
rilevate.
Alcuni polinomi C(x):
CRC
CRC-8
C(x)
x8+x2+x1+1
CRC-10
CRC-12
CRC-16
CRC-CCITT
x10+x9+x5+x4+x1+1
x12+x11+x3+x2+x1+1
x16+x15+x2+1
x16+x12+x5+1
CRC-32
x32+x26+x23+x22+x16+x12+x11+x10+x8
+x7+x5+x4+x2+x+1
Trasmissione affidabile
Recuperare frame rovinati
Codici di Correzione di Errore (ECC)
Ricevute (ACK) e scadenze (timeout):
Automatic Repeat reQuest (ARQ)
Stop-and-Wait
Mittente: dopo aver trasmesso un frame,
attende la ricevuta dal ricevente prima
di trasmettere il successivo
mittente
ricevente
frame
t
e
m
p
o
ACK
frame
ACK
frame
...
Mittente: se ricevuta non arriva entro una
certa scadenza, ritrasmette il frame
timeout
timeout
mittente
ricevente
frame
ACK
stesso frame
prossimo frame
...
Problema
Ricevente: interpreta frame ripetuto come
frame successivo
timeout
timeout
mittente
ricevente
frame
ACK
stesso frame
prossimo frame
ricevente
pensa sia il
frame successivo
...
Soluzione
Mittente: invia un numero di sequenza di 1
bit
mittente
ricevente
frame 0
t
e
m
p
o
ACK[0]
frame 1
ACK[1]
frame 0
...
Problema: Mantenere il canale pieno.
Esempio: collegamento 1.5Mbps x 45ms RTT =
67.5Kb (8KB). Se dimensione del frame è
1KB, stop-and-wait usa circa 1/8 della
capacità del collegamento.
Vogliamo che il mittente possa trasmettere
abbastanza frame da riempire il canale prima
di aspettare un ACK.
Finestra scorrevole
Idea: Imporre un limite superiore sul numero
di frame da mantenere in memoria che
non hanno ancora ricevuto l’ACK
corrispondente.
Tale limite è rappresentato da una finestra che
scorre lungo i possibili numeri di
sequenza dei frame.
Mittente
Assegna un numero di sequenza ad ogni frame
Mantiene tre variabili:
SWS: dimensione della finestra scorrevole (buffer di frame)
LAR: ultimo ACK ricevuto
LFS: ultimo frame inviato
Invariante:
LAR
LFS - LAR <= SWS
sws
LFS
Quando arriva ACK, pone LAR uguale al numero di
sequenza a cui corrisponde l’ACK (se è maggiore
di LAR) e pone LFS = LAR+SWS
Quindi, permette di trasmettere almeno un nuovo frame
Ricevente
Mantiene tre variabili:
RWS: dimensione della finestra (buffer di frame)
LAF: ultimo frame accettabile
LFR: ultimo frame ricevuto in sequenza
Invariante:
LAF - LFR <= RWS
rws
LFR
LAF
Arriva frame con numero SeqNum:
se LFR < SeqNum <= LAF, accetta il frame
se SeqNum <= LFR o SeqNum > LAF, ignora il frame
Invia ACK cumulativo
ACK del frame con numero di sequenza SeqNumToAck più grande
tale che tutti quelli precedenti sono stati ricevuti
Pone LFR = SeqNumToAck e LAF = LFR + SeqNumToAck
Variazioni:
Ricevute selettive: ACK dei singoli frame ricevuti
Ricevute negative: ACK che un frame non è stato ricevuto
Valori tipici di RWS
RWS = 1 oppure RWS = SWS
Esempio:
LFR = 5
RWS = 4
LAF = 9
Arrivano frame 7 e 8:
no ACK oppure ACK per 5
Arriva frame 6:
ACK per 8
LFR = 8
LAF = 12
Spazio dei numeri di sequenza
può assumere un numero finito di
valori
SeqNum
numero di possibili valori (MaxSeqNum) maggiore di
dimensione finestra (SWS)
SWS <= MaxSeqNum-1 non basta (se SWS = RWS):
supponiamo SeqNum in (0..7) e SWS=RWS=7
mittente invia frame 0..6 che arrivano correttamente ma i cui
ACK si perdono
mittente invia di nuovo frame 0..6
ricevente si aspetta 7,0..5, ma riceve i vecchi 0..5
SWS <= MaxSeqNum/2
SeqNum
è la regola corretta (se SWS
= RWS):
scorre tra due metà dello spazio dei numeri di sequenza
Ethernet
Storia
Sviluppata da Xerox PARC a metà degli anni ‘70
Origine dalla rete radio Aloha: algoritmo distribuito che
consente accesso equo a mezzo condiviso
Standardizzata da Xerox, DEC, ed Intel nel 1978
Simile allo standard IEEE 802.3
CSMA/CD
CS: carrier sense
MA: multiple access
CD: collision detection
Larghezza di banda: 10Mbps e 100Mbps
Proprietà fisiche
Ethernet classica (thick-net): 10Base5
Segmento massimo di 500m
Connettori ad almeno
2.5m di distanza
Più segmenti connessi
mediante ripetitori
Al più 4 ripetitori tra una
coppia di nodi (totale: 2500m)
Al più 1024 nodi
Tecnologie alternative
10Base2 (thin-net): 200m; configurazione a margherita
10BaseT (twisted-pair): 100m; configurazione a stella
Formato dei frame
64
48
Preambolo
Ind. Dest.
48
Ind. Sorg.
16
32
8
CRC
Postambolo
Indirizzi:
Unico indirizzo (unicast) a 48 bit assegnato ad
ogni adattatore (al mondo)
Esempio: 8:0:2b:e4:b1:2
Broadcast: tutti 1
Multicast: primo bit è 1
Adattatore riceve tutti i frame e li passa al
nodo se:
Destinazione è il suo indirizzo
Destinazione è indirizzo broadcast
Destinazione è uno degli indirizzi multicast
che è stato programmato ad accettare
Se è in modo promiscuo
Algoritmo di trasmissione
Se la linea è libera:
Invia immediatamente
Messaggio di al più 1500 byte ed almeno 46 byte
Attende 9.6s per spedire il prossimo
Se la linea è occupata:
Attende finché si libera e trasmette immediatamente
Detto 1-persistente (caso speciale di p-persistente)
Se si rileva una collisione:
invia ancora 32 bit
interrompe trasmissione
aspetta
prima volta: sceglie a caso tra 0 s e 51.2s
seconda volta: sceglie a caso tra 0s, 51.2s, 102.4s e 153.6s
n-esima volta: sceglie a caso tra 0s, 51.2s, 102.4s, …, e (2n-1)51.2s
exponential backoff
rinuncia dopo un certo numero di tentativi (generalmente 16, mantenendo però
n minore od uguale a 10)
Frame minimo ha 64 byte (14 byte di header + 46 byte di dati
+ 4 byte di CRC) = 512 bit
Garantisce il caso peggiore in cui due nodi che vogliono inviare dati si
trovano all’estremità opposte della rete
In Ethernet a 10Mbps, 512bit corrispondono a 51,2 s che è il ritardo stimato di
andata e ritorno da un’estremità all’altra della rete
Esperienza con Ethernet
In pratica:
Utilizzo al di sotto del 30%
10-200 nodi (non 1024)
Lunghezza al più 1500m (RTT vicino a 5 e non 51)
Controllo del flusso ad alto livello che limita prestazioni
dei nodi
Vantaggi:
Facile da amministrare e mantenere
Economica
FDDI
Reti Token Ring
PRONET ring: 10Mbps e 80 Mbps
IBM token ring: 4Mbps
IEEE 802.5 token ring: 16Mbps
Fiber Distributed Data Interface (FDDI): 100Mbps
Idea di base
frame viaggiano in una direzione
sequenza di bit speciale (token) circola sull’anello
catturare token prima di trasmettere
rilasciare token dopo trasmissione
rilascio immediato
rilascio ritardato
rimuovere il proprio frame quando ritorna
Proprietà fisiche
Configurazione a due anelli duali
tollera un guasto
Stazioni di attacco singole (SAS) e duali (DAS)
DAS può ignorare SAS guaste
nodo
precedente
nodo
successivo
DAS
SAS
SAS
SAS
Ogni stazione impone un ritardo (ad esempio,
50ns)
Al più 500 stazioni
Al più 100km (200km se fibra)
Usa codifica 4B/5B
Può essere realizzato con cavi di rame (CDDI)
Algoritmo Token Temporalizzato
Tempo di mantenimento del token (THT):
limite superiore sul tempo di possesso
Tempo di rotazione del token (TRT): tempo
richiesto per far passare il token
attraverso l’anello
TRT ≤ Nodi Attivi x THT + Latenza
TRT concordato (TTRT): limite superiore su
TRT deciso in accordo.
Algoritmo
ogni nodo misura TRT tra due arrivi successivi
se TRT misurato > TTRT, allora non invia dati
se TRT misurato < TTRT, allora invia dati e tiene token
per TTRT - TRT misurato
due tipi di traffico
sincrono: può essere trasmesso sempre per TTRT tempo totale
asincrono: può essere trasmesso solo se token in anticipo
caso peggiore: 2xTTRT tra due arrivi del token
Esempio
Token arriva al nodo e viene preso dal nodo
TRT := TTRT (ad es., 100ms) ed inizia a decrementarsi
Traffico sincrono inviato per Synchronous Allocation Value Timer (ad es., 10ms)
Token rilasciato dal nodo, riappare dopo 50ms e viene preso dal nodo
THT := TRT = 40ms, TRT := 100ms ed inizia a decrementarsi
Traffico sincrono inviato per SAVT = 10ms, traffico asincrono inviato per THT = 40ms
Token rilasciato dal nodo, riappare dopo 70ms e viene preso dal nodo
TRT scaduto, DELAY := TRUE e THT := 0
Se non c’è traffico sincrono, nessun dato viene inviato
TRT := TTRT, token rilasciato dal nodo riappare dopo 30 ms e viene preso dal nodo
TRT = 70ms ma DELAY = TRUE: nodo può trasmettere solo traffico sincrono
Traffico sincrono inviato per SAVT = 10ms, DELAY := FALSE
Token rilasciato dal nodo, riappare dopo 40ms e viene preso dal nodo
THT := TRT = 20ms, TRT := 100ms ed inizia a decrementarsi
Traffico sincrono inviato per SAVT = 10ms, traffico asincrono inviato per THT = 20ms
Gestione del token
Token perso
non vi è token quando si avvia l’anello
errori possono rovinare il token
nodo che ha il token si rompe
Generazione del token (e calcolo di TTRT)
da eseguire quando arriva nuovo nodo o vi è malfuzionamento
ogni nodo invia un frame speciale che include la sua
offerta del nodo per TTRT
quando riceve il frame speciale, aggiorna l’offerta ed
invia in avanti
se la propria offerta ha fatto tutto il giro:
la propria offerta era la più bassa
ognuno conosce TTRT
inserisce nuovo token
Controllare validità del token
ogni nodo dovrebbe vedere trasmissioni valide (frame o
token) periodicamente
intervallo massimo = latenza + tempo per trasmettere
frame ≤ 2.5ms
pone contatore a 2.5ms ed invia frame speciale se scade
timeout
Formato del frame
8
start of
frame
8
48
48
Control
32
8
24
CRC
End frame
Status
Campo Control
Primo bit: traffico asincrono (0) o sincrono (1)
Secondo bit: indirizzi a 16-bit (0) o 48-bit (1)
Ultimi 6 bit: chiave di demux (include sequenze speciali per
token e frame speciale)
Campo Status
da ricevente indietro a mittente
errore nel frame
indirizzo riconosciuto
frame accettato (controllo del flusso)
Reti scalabili
Interruttore: smista pacchetti da una porta di
entrata ad una di uscita, selezionata in
base ad indirizzo contenuto in
intestazione
Consente di costruire reti che coprono aree geografiche
estese
Consente di costruire reti con un grande numero di nodi
Consente di aggiungere nuovi nodi senza influenzare le
prestazioni dei nodi già esistenti
Datagrammi
Nessuna fase di configurazione
Ogni pacchetto inviato indipendentemente
Ogni interruttore mantiene una tabella di
smistamento
Esempio
destinazione
porta output
A
3
B
0
C
3
D
3
E
2
F
1
G
0
H
0
Commutazione di circuito virtuale
Fase esplicita di configurazione di
connessione
Ogni pacchetto ha identificatore di VC (VCI) che
cambia lungo il circuito
Pacchetti successivi seguono lo stesso
circuito
Ogni interruttore mantiene una tabella del
circuito virtuale
Riga di tabella:
porta input-VCI input-porta output-VCI output
Esempio
Circuito virtuale vs Datagrammi
Circuito virtuale:
Generalmente aspetta un intero RTT per configurare la
connessione prima di inviare il primo pacchetto dati
La richiesta di connessione contiene l’intero indirizzo di
destinazione, ma ogni pacchetto dati contiene solo un
piccolo identificatore, e quindi un header più piccolo
Se un interruttore o un collegamento si rovinano, la
connessione viene interrotta e bisogna aprirne una
nuova
Configurazione di connessione dà opportunità di riservare
le risorse
Datagrammi:
No RTT di attesa per configurazione: dati inviati subito
Nodo sorgente non sa se la rete può consegnare un
pacchetto o se il nodo destinazione è attivo
Poiché i pacchetti sono indipendenti, si possono evitare
collegamenti o nodi mal funzionanti
Ogni pacchetto deve contenere l’indirizzo completo di
destinazione, quindi l’header è più grande.
Smistamento da sorgente
Indirizzo contiene la sequenza di porte nel
cammino dalla sorgente alla destinazione
0
1
3
...
...
3 0 1
2
3 0
2
1
3
nodo A
0
2
nodo B
0
3
...
1
3
Implementazione
Mediante calcolatori di uso generale
bus I/O
CPU
interfaccia 1
interfaccia 2
Memoria
principale
interfaccia 3
Prestazioni
Larghezza di banda cumulativa
1/2 della larghezza di banda del bus I/O
capacità condivisa tra tutti i nodi collegati all’interruttore
esempio: bus 800Mbps può reggere 8 porte T3
Pacchetti al secondo
capace di smistare pacchetti piccoli
100.000 pacchetti al secondo è un valore normale
esempio: 64-byte pacchetti implica 51.2Mbps
LAN estese
Reti locali (LAN) hanno limiti fisici (ad
esempio, 1500m per Ethernet)
Connettere due o più LAN con un bridge
strategia “accetta-e-invia”
connessione di secondo livello (non aggiunge intestazione al
pacchetto)
Insieme di LAN connesse da bridge formano
una LAN estesa
Principi base
Non inviare se non necessario
nodi dalla stessa parte del bridge
A
B
C
1
bridge
2
X invio
Y
Mantenere tabella di
imparare elementi tabella
con indirizzi nodi sorgente
tabella per ottimizzare: non serve
sia completa
Z
Nodo Porta
A
1
B
1
C
1
X
2
Y
2
Z
2
Albero ricoprente
LAN estese talvolta hanno cicli
più di un amministratore
Bridge eseguono algoritmo distribuito per
calcolo di albero ricoprente
sottografo che contiene tutti i nodi ma non cicli
bridge selezionano le porte attraverso cui inviare i frame
sviluppato da Radia Perlman alla DEC
incluso nella specifica IEEE 802.1
Esempio
A
B
B3
C
B5
B2
B7
K
D
F
E
B1
G
H
B6
B4
I
J
Algoritmo dell’albero ricoprente
Ogni bridge ha un identificatore unico
Radice = bridge con identificatore minimo
Per ogni LAN, seleziona bridge più vicino alla
radice come designato per la LAN (usa
identificatore per risolvere parità)
Ogni bridge invia frame ad ogni LAN per cui
è designato
Bridge inviano messaggi di configurazione
identificatore bridge mittente
identificatore del bridge ritenuto radice dal mittente
distanza dal mittente alla radice
Ogni bridge ricorda il messaggio di
configurazione migliore per ogni porta
Inizialmente ogni bridge si ritiene radice
Se si accorge di non essere radice, bridge non
invia più messaggi di configurazione
stato stabile, solo radice genera messaggi di configurazione
periodicamente
Se non riceve messaggi di configurazione
dopo un certo tempo, bridge ricomincia a
generare messaggi di configurazione
credendosi radice
Broadcast and Multicast
Invia tutti i frame broadcast/multicast
per multicast può
imparare quando una
porta non conduce a
nessun membro di un
gruppo
ogni membro di gruppo
G invia frame multicast
a bridge con G nel
campo sorgente
A
B
B3
C
B5
B2
B7
K
D
F
E
B1
G
H
B6
B4
I
J
Limiti dei bridge
Non scalano
albero ricoprente scala linearmente
broadcast non scala (dipartimento≠università)
Non consentono eterogeneità
Ethernet-Ethernet, FDDI-FDDI, Ethernet-FDDI
Trasparenza può essere pericolosa
bridge congestionato può perdere frame
latenza può aumentare e può essere variabile
Inter-reti (IP)
rete 1 (Ethernet)
H1
H2
H3
H1
R3
H7
TCP
rete 2 (Ethernet)
R1
H4
H5
H2
H8
rete 3
(Token ring)
rete 4
(punto-punto)
R2
TCP
R1
IP
ETH
R2
IP
ETH
H6
Modello di servizi
modello di consegna dei pacchetti
schema di indirizzamento globale
R3
IP
FDDI
FDDI
IP
P2P
P2P
IP
ETH
ETH
Modello di consegna pacchetti
Senza connessione (basato su datagrammi)
Consegna al meglio possibile (servizio
inaffidabile)
pacchetti persi
pacchetti consegnati in ordine errato
copie duplicate di un pacchetto
pacchetti ritardati anche a lungo
Formato del pacchetto
Version
HLen
TOS
Length
Ident
TTL
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variabile)
Pad (variabile)
Data
Version (4): attualmente 4
Hlen (4): numero di parole nell’header
TOS (8): tipo di servizio (spesso non usato)
Length (16): numeri di byte nel pacchetto
Ident (16) e Flags/Offset (16): frammentazione
TTL (8): numero di salti rimasti
Protocol (8): chiave di demux (TCP=6, UDP=17)
Checksum (16): dell’header solo
DestinationAddr & SourceAddr (32)
Frammentazione-riassemblaggio
Ogni rete ha un’unità massima di trasmissione
(MTU)
Strategia
frammentare quando necessario
evitare frammentazione in nodo sorgente
ri-frammentazione possibile
frammenti sono datagrammi auto-contenuti
riassemblaggio in nodo destinazione (se possibile)
Esempio
H1
ETH
R1
IP
1400
FDDI
R2
IP
1400
P2P
P2P
P2P
R3
IP
IP
IP
512
512
376
H8
ETH
ETH
ETH
IP
IP
IP
512
512
376
Inizio header
Ident=x
0
Offset=0
Fine header
Dati: 1400 byte
Inizio header
Ident=x
1 Offset=0
Fine header
Dati: 512 byte
Inizio header
Ident=x
1 Offset=512
Fine header
Dati: 512 byte
Inizio header
Ident=x
0 Offset=1024
Fine header
Dati: 376 byte
Indirizzi globali
Proprietà:
globalmente unico
gerarchico: rete + nodo
0 network
1 0
classe A
host
network
classe B
host
network
1 1 1 0
ID gruppo multicast
classe D
1 1 1 1 0
riservato per usi futuri
classe E
Formato:
Notazione “a punto”:
10.3.2.4, 128.96.33.81, 192.12.69.77
classe A: da 0.0.0.0 a 127.255.255.255
classe B: da 128.0.0.0 a 191.255.255.255
classe C: da 192.0.0.0 a 223.255.255.255
host
classe C
1 1 0
Invio di datagrammi
Strategia
ogni datagramma contiene indirizzo destinazione
se connesso direttamente alla rete destinazione, allora invia a
nodo
se non connesso direttamente, allora invia ad altro router
tabella di invio associa passo successivo a numero di rete
ogni nodo ha un router di default
ogni router mantiene tabella di invio
Esempio
Numero rete
1
2
3
4
Tabella del router R2
rete 1 (Ethernet)
H1
H2
H3
R3
H7
rete 2 (Ethernet)
R1
H4
H5
rete 3
(Token ring)
H8
rete 4
(punto-punto)
R2
H6
Uscita
R3
R1
interface 1
interface 0
ARP
Address Resolution Protocol:
trasforma indirizzi IP in indirizzi fisici
basato su tabella di associazione tra indirizzi IP ed indirizzi fisici
se indirizzo IP non è in tabella, invia richiesta broadcast e nodo
destinazione risponde con suo indirizzo fisico
elementi della tabella scadono dopo un certo periodo di tempo
(tipicamente 15 minuti)
Formato frame ARP
2
2 11 2
HT PT
HS
OP
6
SEA
4
SIPA
6
TEA
4
TIPA
PS
HT: tipo di rete fisica (ad es., Ethernet)
PT: protocollo di livello superiore (ad es., IP)
HS: dimensione indirizzo fisico (ad es., 48)
PS: dimensione indirizzo protocollo (ad es., 32)
OP: tipo di frame (ad es., richiesta)
SEA: indirizzo fisico mittente
SIPA: indirizzo IP mittente
TEA: indirizzo fisico destinatario
TIPA: indirizzo IP destinatario
Osservazioni
Frame ARP permetterebbe di aggiornare le
tabelle di tutti i nodi relativamente al
mittente
se nodo ha già un elemento, allora lo rinfresca
se nodo è destinatario e non ha elemento, allora lo
inserisce
se nodo non è destinatario e non ha elemento, allora non
lo inserisce
ICMP
Internet Control Message Protocol:
gestione errori: errore di checksum, errore di
riassemblaggio, errore di frammentazione,
destinazione irraggiungibile, tempo di vita esaurito
ri-direzionamento (da router a nodo sorgente) in caso
esista strada migliore
Routing
Smistamento vs Indirizzamento
smistamento: seleziona porta di uscita in base a indirizzo
destinazione e tabella di routing
indirizzamento: processo di costruzione della tabella
Rete come grafo
6
A
3
1
1
B
E
4
1
C
9
F
D
2
Problema: trovare il cammino di minimo
costo tra due nodi
Algoritmo di Dijkstra per calcolare i cammini minimi a
partire da un nodo specificato
Fattori:
Approccio statico: topologia
Approccio dinamico: carico
Costo-direzione
Ogni nodo mantiene un insieme di triple:
(Destination, Cost, NextHop)
Ogni nodo invia (riceve) aggiornamenti ai
(dai) nodi vicini
periodicamente (alcuni secondi)
quando la tabella cambia
ogni aggiornamento è una lista di coppie:
(Destination, Cost)
Aggiorna la tabella se riceve cammino
migliore
Esempio
B
A
C
E
F
D
G
Tabella di routing in B
destinazione costo
direzione
A
1
A
C
1
C
D
2
C
E
2
A
F
2
A
G
3
A
Reazione ai guasti
Esempio 1
F si accorge che il collegamento a G è rovinato
F pone la distanza da G uguale ad infinito ed invia
l’aggiornamento ad A
A pone la distanza da G uguale ad infinito poiché usa F
per raggiungere G
A riceve aggiornamenti periodici da C con cammino a G
A pone la distanza da G uguale a 3 ed invia
aggiornamento ad F
F decide che può raggiungere G in 4 passi tramite A
Esempio 2
Collegamento da A ad E mal funziona
A avverte che la sua distanza da E è infinita
B e C danno una distanza 2 da E
B decide che può arrivare ad E in 3 passi; avverte A
A decide che può raggiungere E in 4 passi; avverte C
C decide che può raggiungere E in 5 passi......
Euristiche per rompere cicli
porre 16 uguale ad infinito
split-horizon e sue varianti
ritardano la convergenza dell’algoritmo
Algoritmo di Dijkstra
Inizializzazione:
Per ogni nodo n diverso da s, d(n) è infinito
d(s) = 0
K indica l’insieme dei nodi con distanza minima nota: K = {s}.
Ciclo:
per ogni nodo n in N-K:
d(n) = min(d(n), min[n’ in K](d(n’)+d(n’,n)))
sia n in N-K il nodo con distanza minima: aggiungi n a K
se N = K, abbiamo finito, altrimenti ripeti il ciclo
Dimostrazione
d(n) può solo decrescere
Se un cammino fino ad n passa per n’, allora alla fine d(n) >
d(n’), poichè gli archi hanno peso positivo
Se un nodo è inserito in K, la sua distanza è minore od uguale
alla distanza di tutti i nodi in N-K
Quindi, la distanza di tutti i nodi in K è minore od uguale
della distanza di ogni nodo in N-K
Quindi, la distanza dei nodi in K non può mai diminuire al di
sotto del valore corrente
Quindi, la distanza dei nodi in K è la distanza minima
Stato dei collegamenti
Strategia: inviare a tutti i nodi (non solo ai
vicini) l’informazione riguardo ai propri
collegamenti diretti (non l’intera tabella)
pacchetto di stato dei collegamenti (LSP)
identità del nodo che ha creato il LSP
costo del collegamento ad ogni vicino
numero di sequenza (SEQNO)
tempo-da-vivere (TTL) per questo pacchetto
diffusione affidabile
memorizza LSP più recenti da ogni nodo e li invia a tutti i nodi
vicini tranne quello da cui sono stati ricevuti
genera nuovi LSP periodicamente; aumenta SEQNO (64 bit)
pone SEQNO uguale a 0 quando riavvia
diminuisce TTL di ogni LSP memorizzato ed elimina LSP se
TTL=0
Calcolo del cammino
In teoria: algoritmo di Dijkstra
In pratica:
algoritmo di ricerca in avanti
ogni interruttore mantiene due liste:
Tentative e Confirmed
ogni lista contiene un insieme di triple:
(Destination, Cost, NextHop)
si stabilizza velocemente, non genera troppo traffico,
reagisce velocemente a cambiamenti della rete
richiede molta memoria
Algoritmo di ricerca in avanti
1. Inizializza Confirmed con elemento per me e costo 0
2. Seleziona LSP del nodo Next appena aggiunto a Confirmed
3. Per ogni vicino di Next, calcola il costo a raggiungere questo
vicino come la somma del costo da me a Next e da Next
al vicino
3.1. Se il vicino non è in Confirmed o Tentative,
aggiungilo a Tentative, con NextHop uguale alla
direzione per raggiungere Next ed il costo calcolato
prima
3.2 Se Neighbor è in Tentative ed il costo calcolato prima
è minore del costo attuale, allora sostituisci l’elemento
di Tentative
4. Se Tentative è vuoto, stop. Altrimenti, seleziona elemento di
Tentative con costo minimo, spostalo in Confirmed, e
ritorna al passo 2.
Esempio
passo Confirmed
1
(D,0,-)
2
(D,0,-)
3
(D,0,-)
5
A
Tentative
5
3
11
D
C
2
passo Confirmed
6
(D,0,-)
(B,11,B)
(C,2,C)
(C,2,C)
(B,5,C)
(B,11,B)
(C,2,C)
4
10
B
7
(D,0,-)
(C,2,C)
(D,0,-)
(B,5,C)
(B,5,C)
(C,2,C)
(A,12,C)
(A,10,C)
(D,0,-)
(A,12,C)
(C,2,C)
(B,5,C)
Tentative
(A,10,C)
Metriche
Metrica originale ARPANET
numero di pacchetti in coda su ciascun collegamento
non considera latenza nè larghezza di banda
Nuova metrica ARPANET
etichetta ogni pacchetto con suo tempo di arrivo (AT)
memorizza tempo di partenza (DT)
quando arriva ACK, calcola
Delay = (DT - AT) + Transmit + Latency
se scatta timeout, DT = tempo di ritrasmissione
costo collegamento = ritardo medio in un certo periodo
Problemi
Con molto carico, collegamenti congestionati
hanno alto costo: i pacchetti oscillano tra
collegamenti congestionati e
collegamenti disattivi
con poco carico, fattori statici dominano: OK
Valori del costo molto grandi: cammino di
126 collegamenti a 56Kbps poco carichi
può essere preferito a cammino di un
collegamento a 9.6Kbps molto carico con
costo 127 volte superiore
Metrica ARPANET rivista
misura ritardo sotituita con utilizzo collegamento
variabilità dinamica compressa
collegamento molto carico ha costo non superiore a tre volte il
costo quando disattivo
costo masimo solo 7 volte il costo minimo
costo è funzione di utilizzo solo per carico medio-alto
Frequenza di calcolo
metrica non istantanea ma valore medio
invio aggiornamento solo se il cambio di costo è oltre una
certa soglia
Problemi di scalabilità
Uso inefficiente dello spazio indirizzi
rete di classe C con 2 nodi (efficienza: 0.78%)
rete di classe B con 256 nodi (0.39%)
Troppe reti
decine di migliaia di reti
tabelle di indirizzamento non scalano
protocolli di propagazione del cammino non scalano
Struttura Internet: 1990
NSFNET backbone
Stanford
ISU
BARRNET
regional
Berkeley
PARC
MidNet
regional
Westnet
regional
UNM
NCAR
UA
UNL
KU
Sottoreti
Ulteriore livello nella gerarchia
indirizzo/cammino: sottorete
Maschere di sottorete individuano partizione variabile dei nodi di
una rete di classe A o B
Sottoreti visibili solo nella stessa rete fisica
network
classe B
host
111111111111111111111111 00000000
network
subnet ID
host
maschera
indirizzo
Esempio
maschera: 255.255.255.128
numero: 128.96.34.0
128.96.34.15
128.96.34.1
H1
R1
128.96.34.130
maschera: 255.255.255.128
numero: 128.96.34.128
128.96.34.129
H3
R2
128.96.34.139
H2
128.96.33.14
128.96.33.1
maschera: 255.255.255.0
numero: 128.96.33.0
Tabella di
Num. sottorete
128.96.34.0
routing di R1
128.96.34.128
128.96.33.0
Masch. sottorete
255.255.255.128
255.255.255.128
255.255.255.0
Uscita
interface 0
interface 1
R2
Algoritmo di smistamento
D = destination IP address
for each entry (SubnetNum, SubnetMask, NextHop)
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to D
else
deliver datagram to NextHop
Osservazioni
Usa un router di default se non trova una
corrispondenza
Non è necessario che gli 1 nella maschera
siano contigui
Più sottoreti possono essere messe in una rete
fisica
Sottoreti non visibili dal resto di Internet
Super-reti
Assegna blocchi di numeri di rete contigui a reti
vicine
Detto CIDR: Classless Inter-Domain Routing
Blocchi rappresentati da coppie
(first_network_address, count)
Dimensione dei blocchi vincolata a potenze di 2
Maschera CIDR per identificare la dimensione del
blocco
Tutti i router devono capire l’indirizzamento CIDR
Struttura Internet: Oggi
Large corporation
“Consumer ” ISP
Peering
point
Backbone service provider
“ Consumer” ISP
Large corporation
Small
corporation
“Consumer”ISP
Peering
point
Propagazione del cammino
Imporre una seconda gerarchia sulla rete che
limita quali router possono parlare tra di
loro
La prima gerarchia è quella degli indirizzi che governa il modo
in cui i pacchetti sono inviati
Sistema autonomo (AS)
corrisponde ad un dominio amministrativo
esempi: Università, compagnie, dorsali
assegnare ad ogni AS un numero a 16 bit
Propagazione del cammino a due livelli
protocolli interni (ogni AS sceglie il proprio)
protocolli esterni (standard mondiali)
Protocolli interni ed esterni
Interni
RIP (Route Information Protocol): sviluppato per XNS,
distribuito con Unix, metodo vettore delle distanze, basato
sul numero di passi
OSPF (Open Shortest Path First): standard Internet recente,
metodo stato dei collegamenti, supporta bilanciamento del
carico ed autenticazione
Esterni
EGP (Exterior Gateway Protocol): progettato per Internet con
struttura ad albero, tratta la raggiungibilità (non cammini
ottimi)
BGP (Border Gateway Protocol): complesso
Border Gateway Protocol
Tipi di AS
stub: ha una singola connessione ad un’altro AS
Trasporta solo traffico locale
multihomed: ha connessioni con più AS diversi
Rifiuta di trasportare traffico in transito
transit: ha connessioni con più AS diversi
Trasporta sia traffico locale che in transito
Ogni AS ha:
Uno o più router di confine da cui entrano ed escono i pacchetti
Un portavoce BGP che comunica con altri portavoce per scambiare
informazioni di raggiungibilità tra gli AS
Esempio BGP
Portavoce di AS2 comunica
reti 128.96, 192.4.153, 192.4.32 e 192.4.3 possono essere raggiunte direttamente da
AS2
Customer P
(AS 4)
128.96
192.4.153
Customer Q
(AS 5)
192.4.32
192.4.3
Customer R
(AS 6)
192.12.69
Customer S
(AS 7)
192.4.54
192.4.23
Regional provider A
(AS 2)
Backbone network
(AS 1)
Regional provider B
(AS 3)
Portavoce di AS1 comunica
reti 128.96, 192.4.153, 192.4.32 e 192.4.3 possono essere raggiunte attraverso il
cammino (AS1, AS2).
Portavoce possono cancellare cammini annunciati in precedenza
IPv6: caratteristiche principali
Indirizzi a 128 bit
Servizi real-time
Autenticazione e sicurezza
Auto-configurazione
Estensione protocolli
Nomi dei nodi
Nomi vs indirizzi
nomi di lunghezza variabile, facili da ricordare
indirizzi di lunghezza fissa, facili da elaborare
Spazio dei nomi
definisce insieme dei possibili nomi
piatto e non gerarchico
consiste di un insieme di legami tra nome e valore
Name server (NS)
utente
[email protected]
dsi.unifi.it
name
server
programma
posta
150.217.14.12
150.217.14.12
TCP
150.217.14.12
IP
Domain Name System (DNS)
Nomi organizzati in gerarchia di domini
Gerarchia suddivisa in zone
Ogni zona realizzata da due o più NS
Ogni NS ha un insieme di record di risorse
Strategia ricorsiva
Gerarchia dei domini
com
unifi ... uniroma1 macity
tin
gnim
...
it
dsi
...
...
piluc
ing
edu
uk
Name server (NS)
Partizionamento
in zone
com
edu
uk
unifi ... uniroma1 macity
tin
gnim
...
it
dsi
...
...
piluc
ing
Name server radice
Due o più NS
per zona
Name server unifi
Name server dsi
...
...
Name server tin
Record di risorse
Ogni NS ha un insieme di record di risorse
<Name, Value, Type, Class, TTL>
Name/Value: non sempre nome/indirizzo IP
Type
A: il campo Value è un numero IP
NS: il campo Value è il nome del dominio per un nodo su cui è realizzato un NS che
sa come risolvere i nomi del dominio specificato
CNAME: il campo Value è il nome canonico di un particolare nodo (usato per definire
alias)
MX: il campo Value è il nome del dominio per un nodo su cui è realizzato un mail
server che accetta messaggi per il dominio specificato
TTL:
quanto tempo il record è ancora valido
Esempio
NS radice:
<unifi.it, ns.unifi.it, NS, IN>
<ns.unifi.it, 150.217.128.233, A, IN>
NS unifi:
<dsi.unifi.it, ns.dsi.unifi.it, NS, IN>
<ns.dsi.unifi.it, 150.217.1.32, A, IN>
NS dsi:
<dsi.unifi.it, gnim.dsi.unifi.it, MX, IN>
<piluc.dsi.unifi.it, 150.217.14.142, A, IN>
<www.dsi.unifi.it, dsiI.dsi.unifi.it, CNAME, IN>
Risoluzione del nome
NS radice
piluc.dsi.unifi.it
Host
NS locale
150.217.1.142
piluc.dsi.unifi.it
NS unifi
ns.dsi.unifi.it, 150.217.1.32
NS dsi
Problemi
Rete soggiacente
perde messaggi
permuta messaggi
consegna copie duplicate di un dato messaggio
limita messaggi a dimensione finita
consegna messaggi dopo un ritardo arbitrariamente lungo
Obiettivi
Garantire la consegna dei messaggi
Consegnare i messaggi nel giusto ordine
Consegnare al più una copia di un messaggio
Permettere messaggi arbitrariamente grandi
Consentire sincronizzazione
Permettere al ricevente di controllare il flusso del mittente
Consentire più applicazioni su ogni nodo
UDP
Servizio inaffidabile e non ordinato
Consente multiplexing
Nessuno controllo del flusso
Estremi identificati da porte
vedere /etc/services su Unix
Checksum opzionale
pseudo header + udp header + dati
Flusso di byte affidabile (TCP)
Orientato alla connessione
Flusso di byte
processo mittente scrive un certo numero di byte
TCP spezza in segmenti ed invia ad IP
processo ricevente legge un certo numero di byte
Full duplex
Controllo del flusso
evita che il mittente sommerga il ricevente
Controllo della congestione:
evita che il mittente sommerga la rete
Problematiche “end-to-end”
Basato su protocollo a finestra scorrevole
Connette potenzialmente molti nodi diversi
stabilire e terminare connessione esplicitamente
RTT potenzialmente diversi
meccanismo di timeout adattivo
Ritardo della rete potenzialmente lungo
pronto a ricevere pacchetti molto vechi
Capacità a destinazione potenzialmente diversa
permettere diverse quantità di memorizzazione
Capacità della rete potenzialmente diversa
pronto a gestire congestione
Formato del segmento
SrcPort
DstPort
SequenceNum
Acknowledgment
HdrLen
0
Flags
AdvertisedWindow
Checksum
UrgPtr
Options (variabile)
Data
Ogni connessione è identificata da una
quadrupla:
<SrcPort,SrcIPAddr,DstPort,DstIPAddr>
Finestra scorrevole + controllo flusso
Acknowledgment, SequenceNum, AdvertisedWindow
Flags: SYN, FIN, RESET, PUSH, URG, ACK
Checksum: pseudo-header + TCP header +
dati
Stabilire una connessione
Protocollo “three-way handshake”
SYN, S
equen
ceNum
=x
=y
m
u
nc eN +1
e
u
q
x
, Se gment=
K
C
+A
led
SYN cknow
A
ACK
, Ack
now
ledg
men
t =y +
1
Diagramma degli stati
closed
passive open
close
listen
SYN/SYN+ACK
SYN_rcvd
close
send/SYN
SYN/SYN+ACK
ACK
close/FIN
active open/SYN
SYN+ACK/ACK
established
close/FIN
FIN/ACK
FIN_wait1
ACK
FIN_wait2
SYN_sent
close_wait
FIN/ACK
close/FIN
closing
last_ACK
ACK
ACK
timeout
FIN/ACK
time_wait
closed
Finestra scorrevole (rivista)
Ogni byte ha un numero di sequenza
Gli ACK sono cumulativi
Applicazione mittente
TCP
LastByteWritten
LastByteAcked
LastByteSent
Applicazione destinatario
TCP
LastByteRead
NextByteExpected
LastByteRcvd
Lato mittente
LastByteAcked ≤ LastByteSent
LastByteSent ≤ LastByteWritten
byte tra LastByteAcked e LastByteWritten devono
essere memorizzati
Lato destinatario
LastByteRead < NextByteExpected
NextByteExpected ≤ LastByteRcvd + 1
byte tra LastByteRead e LastByteRcvd devono essere
memorizzati
Controllo del flusso
Dim. buffer mittente: MaxSendBuffer
Dim. buffer destinatario: MaxRcvBuffer
Lato detinatario
LastByteRcvd - LastByteRead ≤ MaxRcvBuffer
AdvertisedWindow =
MaxRcvBuffer - (LastByteRcvd - LastByteRead)
Lato mittente
LastByteSent - LastByteAcked ≤ AdvertisedWindow
EffectiveWindow =
AdvertisedWindow - (LastByteSent - LastByteAcked)
LastByteWritten - LastByteAcked ≤ MaxSendBuffer
blocca applicazione mittente se
(LastByteWritten - LastByteAcked) + y >
MaxSendBuffer
Invia sempre ACK in risposta ad un segmento
dati in arrivo
Persiste quando AdvertisedWindow=0
Ripetizione numeri di sequenza
Numeri in ciclo: SequenceNum è di 32 bit
Banda e tempo prima di termine ciclo
tempo di vita di un pacchetto: 120 secondi
Banda
Tempo
T1 (1.5Mbps)
Ethernet (10Mbps)
T3 (45Mbps)
FDDI (100Mbps)
STS-3 (155Mbps)
STS-12 (622Mbps)
STS-24 (1.2Gbps)
6.4 ore
57 minutti
13 minuti
6 minuti
4 minuti
55 secondi
28 secondi
Mantenere il canale pieno
64KB in transito: AdvertisedWindow di 16 bit
Banda e ritardo x banda
ritardo: 100ms
Banda
T1 (1.5Mbps)
Ethernet (10Mbps)
T3 (45Mbps)
FDDI (100Mbps)
STS-3 (155Mbps)
STS-12 (622Mbps)
STS-24 (1.2Gbps)
Ritardo x Banda
18KB
122KB
549KB
1.2MB
1.8MB
7.4MB
14.8MB
Ritrasmissione adattiva
Algoritmo originale
misura SampleRTT per ogni coppia segmento/ACK
calcola media pesata di RTT
EstimatedRTT =  x EstimatedRTT +  x SampleRTT
dove  +  = 1
tra 0.8 e 0.9
 tra 0.1 e 0.2
TimeOut = 2 x EstimatedRTT
ritrasmissione
trasmissione
SampleRTT
SampleRTT
trasmissione
ACK
ritrasmissione
ACK
Algoritmo di Karn/Partridge
non stima RTT quando ritrasmette
duplica timeout dopo ogni ritrasmissione
Algoritmo di Jacobson/Karels
Nuovo calcolo del valore medio di RTT
Diff = SampleRTT - EstimatedRTT
EstimatedRTT = EstimatedRTT + ( x Diff)
Dev = Dev + (|Diff|- Dev)
dove  è tra 0 e 1
Considera varianza in calcolo timeout
TimeOut =  x EstimatedRTT +  x Dev
dove  = 1 e  = 4
Esperimenti
Due workstation DEC 3000/600 (Alpha
21064 a 175MHz)
10Mbps Ethernet
Test ping-pong (10,000 volte)
Ogni test ripetuto cinque volte
Dimensione messaggi
Latenza: 1-byte, 100-byte, 200-byte,... 1000-byte
Throughput: 1KB, 2KB, 4KB,... 32KB
Latenza
Latenza di livello
ETH + cavo: 219µs
UDP/IP: 60µs
Dim. messaggio
1
100
200
300
400
500
600
700
800
900
1000
UDP
279
413
572
732
898
1067
1226
1386
1551
1719
1878
TCP
365
519
691
853
1016
1185
1354
1514
1676
1845
2015
Throughput
10
9.8
9.6
Mbps
9.4
9.2
9
8.8
8.6
8.4
8.2
8
2
4
8
UDP throughput
16
32
Introduzione
Due facce della stessa medaglia
Allocare in anticipo le risorse per evitrare la congestione
Controllare la congestone se (e quando) si verifica
Reti a commutazione di pacchetti
Router
1.5-Mbps T1 link
Due punti di realizzazione
Source
2
Nodi all’estremità della rete (protocollo di trasporto)
Router dentro la rete (gestioen delle code)
Modello di servizio soggiacente
Al meglio delle proprie possibilità
Diverse qualità di servizio (non lo studieremo)
Destination
Contesto
Flussi non orientati alla connessione
Sequenza di pacchetti scambiati da una coppia sorgente/destinazione
Diverso dal canale astratto:
visibile dai router
Gestione di una stato “soft”
nei router
Tassonomia
Source
1
Router
Destination
1
Router
Source
2
Router
Source
3
Centrato sui router – centrato sui nodi
Basato sulla prenotazione – basato sul feedback
Basato sulla finestra – basato sul tasso
Destination
2
Criteri di valutazione
Potenza della rete
Throughput/delay
Power = Throughput/Delay
Carico
ottimale
Carico
Equità dell’allocazione delle risorse
Metrica di Jain
Insieme di n flussi con throughput x1, …, xn
Indice di equità
somma(x1, …, xn)2/(n x somma(x12, …, xn2))
Tutti i flussi con throughput 1
Indice = n2/(n x n) = 1
Un flusso con throughput 1+D e gli altri con throughput 1
Indice = (n2+2nD+D2)/(n2+2nD+D2) < 1per qualunque D
k flussi con throughput 1 e gli altri con throughput 0
Indice = k/n
Gestione delle code
First-In-First-Out (FIFO)
Non discrimina tra le diverse sorgenti di traffico
Gestione equa della coda (Fair Queuing)
Una coda per ogni flusso
Code servite mediante un
meccanismo di round-robin
Variazione: code pesate
(Weighted FQ)
Flusso 1
Flusso 2
Round-robin
Flusso 3
Flusso 4
Algoritmo FQ: singolo flusso
Assumiamo che un clock avanza ad ogni bit trasmesso
Sia
Pi : lunghezza del pacchetto i
Si : il tempo di inizio trasmissione del pacchetto i
Fi : il tempo di fine trasmissione del pacchetto i
Fi = Si + Pi
Router inizia a trasmettere il pacchetto i
Immediatamente dopo l’ultimo bit del pacchetto i - 1 (Fi-1), se il pacchetto i
arriva prima che il router abbia finito di trasmettere il pacchetto i – 1
Appena arriva (Ai), altrimenti
Quindi: Fi = max(Fi - 1, Ai) + Pi
Algoritmo FQ: flussi multipli
Clock avanza ogni n bit spediti, se si hanno n flussi
attivi
Calcola Fi per ogni pacchetto che arriva per ogni
flusso
Spedisce pacchetto con Fi minimo
Non interrompe la trasmissione di un pacchetto
Flusso 1
F=8
F=5
Flusso 2
Output
Flusso 1
(in arrivo)
F = 10
Flusso 2
(in trasmissione) Output
F = 10
F=2
(a)
(b)
Controllo congestione in TCP
Assume gestione FIFO delle code
Funziona anche con FQ
Ciascuna sorgente determina la capacità della rete
Uso degli ACK per regolare la trasmissione (selfclocking)
Problemi
Determinare la capacità disponibile
Adattarsi ai cambiamenti nella capacità
AI/MD
Obiettivo: adattarsi ai cambiamenti di capacità disponibile
Nuova variabile di stato CongestionWindow che limita la
quantità di dati in transito
EffectiveWindow diventa
MaxWindow - (LastByteSent - LastByteAcked)
dove MaxWindow è
MIN(CongestionWindow,AdvertisedWindow)
Aumentare CongestionWindow quando diminuisce la
congestione e diminuirla quando aumenta la
congestione
AI/MD = Additive Increase/Multiplicative Decrease
Domanda: come può la sorgente determinare
se la rete è congestionata o meno?
Risposta: utilizzo dei timeout
Timeout indica che un pacchetto si è perso
I pacchetti raramente si perdono per errori di trasmissione
Un pacchetto perso è indice di congestione
Algoritmo
Aumenta CongestionWindow di un pacchetto ogni
volta che è stato ricevuto l’ACK di tutti i pacchetti
inviati in un RTT (aumento lineare)
Dimezza CongestionWindow ad ogni timeout
(diminuzione moltiplicativa)
In pratica: aumenta un poco per ogni ACK
Sorgente Destinazione
MSS
indica la massima dimensione di un segmento
CongestionWindow += Increment
…
Increment = (MSS * MSS)/CongestionWindow
KB
70
60
50
40
30
20
10
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
TTempo (secondi)
In realtà, l’andamento di crescita non è
esattamente lineare
9.0
10.0
Partenza lenta
Problema: Determinare la capacità disponibile
all’inizio
Sorgente
Destinazione
AI/MD troppo lento
Soluzione:
Inizia con CongestionWindow = 1
Aumenta CongestionWindow di 1
per ogni ACK
raddoppia ad ogni RTT
…
Crescita esponenziale, ma più lenta che tutti insieme
Partenza lenta usata
Quando inizia la connessione
Quando la connessione si ferma in attesa di un timeout
Il nuovo valore di CongestionWindow (detto
CongestionThreshold) può essere usato come valore da
raggiungere con la partenza lenta
Successivamente, si usa l’aumento lineare
Ritrasmissione veloce
Problema: stima
approssimativa del
timeout in TCP
Periodi di non attività
Mittente
Destinatario
Pacchetto 1
Pacchetto 2
Pacchetto 3
ACK 1
Pacchetto 4
ACK 2
Pacchetto 5
ACK 2
Pacchetto 6
Soluzione: utilizzo di ACK
duplicati per stimolare la
ritrasmissione
ACK 2
ACK 2
Ritrasmette
pacchetto 3
ACK 6
Prevenzione della congestione
Strategia di TCP
Controllare la congestione quando si verifica
Aumentare ripetutamente il carico fino a trovare il punto in cui si
verifica la congestione, quindi diminuirlo
Strategia alternativa: prevenzione della congestione
Prevedere quando la congestione sta per verificarsi
Ridurre il tasso prima che i pacchetti siano scartati
Due possibilità
Centrato sul router: DECbit e RED Gateways
Centrato sul nodo: TCP Vegas
DECbit
Aggiunge un bit di congestione all’intestazione dei pacchetti
Router pone tale bit ad 1 se la lunghezza media della coda è
maggiore di 1
Media su ultimo ciclo attivo-disattivo più il ciclo attivo corrente
Tenta di bilanciare il throughput rispetto al ritardo
Lunghezza coda
Tempo
attuale
Ciclo
precedente
Intervallo
di media
Ciclo
corrente
Tempo
Nodo destinazione trasmette il bit di congestione
nell’ACK
Nodo mittente memorizza quanti pacchetti hanno il
biti di congestione ad 1
Se meno del 50% dell’ultima finestra aveva il bit ad
1, allora aumenta CongestionWindow di 1
Altrimenti, diminuisce CongestionWindow di un
fattore 0.875
Random Early Detection (RED)
Notifica implicita
Semplicemente, scarta il pacchetto (TCP andrà in timeout)
Scarta (a caso) il pacchetto in anticipo
Invece di aspettare che la coda divenga piena, scarta ogni
pacchetto che arriva, con una certa probabilità, ogni
qualvolta la coda supera un certo livello
Dettagli
Calcola lunghezza media della coda
AvgLen = (1-Weight)*AvgLen+Weight*SampleLen
0 < Weight < 1 (generalmente, 0.002)
SampleLen misurata ogni volta che arriva un pacchetto
MinThreshold MaxThreshold
AvgLen
if AvgLen <= MinThreshold then
metti in coda il pacchetto
if MinThreshold<AvgLen<MaxThreshold then
calcola probabilità P
scarta il pacchetto con probabilità P
if ManThreshold <= AvgLen then
scarta il pacchetto
P
1.0
MaxP
AvgLen
MinThreshold MaxThreshold
Calcolo effettivo di P
TempP = MaxP * (AvgLen - MinThreshold)/
(MaxThreshold - MinThreshold)
P = TempP/(1 - count * TempP)
dove count indica il numero di pacchetti arrivati che sono stati
messi in coda mentre AvgLen era tra le due soglie
Osservazioni
Probabilità di scartare i pacchetti di un particolare
flusso è (circa) proporzionale alla percentuale di
banda assegnata al flusso
MaxP è tipicamente uguale a 0.02
Quando la lunghezza media è a metà tra le due soglie, il router scarta
circa un pacchetto ogni 50
Impostazione delle due soglie basata su esperienza
Impostare MaxThreshold pari al doppio di MinThreshold è
ragionevole per il traffico attuale di Internet
TCP Vegas
Sorgente osserva se ci sono segnali che
indicano che la coda del router sta
crescendo e che si verificherà la
congestione
RTT cresce
Tasso di invio si appiattisce
Algoritmo
BaseRTT: minimo RTT misurato (generalmente, RTT del primo pacchetto)
Se non si verifica congestione, allora
ExpectedRate = CongestionWindow/BaseRTT
Calcola tasso di invio reale (ActualRate) una volta per RTT
Confronta ActualRate con ExpectedRate
Diff = ExpectedRate – ActualRate
if Diff < 
aumenta CongestionWindow linearmente
if Diff > 
diminuisce CongestionWindow linearmente
if  <= Diff <= 
lascia CongestionWindow inalterata
KB
Esempio
70
60
50
40
30
20
10
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
6.5
7.0
7.5
8.0
5.0
5.5
6.0
6.5
7.0
7.5
8.0
CAM KBps
Time (seconds)
240
200
160
120
80
40
0.5
1.0
1.5
2.0
2.5
3.0
3.5 4.0 4.5
Time (seconds)