Alma Mater Studiorum – Università di Bologna
Facoltà di Scienze Matematiche Fisiche e Naturali
Corso di laurea in Scienze dell’Informazione
TCP E APPLICAZIONI
IN AMBIENTE WIRELESS
Sistemi e Applicazioni Multimediali
Claudio Enrico Palazzi
[email protected]
27 aprile 2004
Internet e wireless 1/2
• Situazione attuale:
– Crescita del traffico di Internet e della sua importanza nel quotidiano
– Aumento esponenziale nell’utilizzo di dispositivi mobili
(computer portatili, telefoni cellulari, PDA, …)
– Incremento nell’utilizzo delle connessioni wireless in generale
(Hot Spots, Satelliti, …)
Last Hop
GEO Satellite
Internet
Sat
UAV + proxy
802.11
Ad Hoc
Urban Environment
Gateway
Internet e wireless 2/2
• Prospettiva futura:
– Interazione tra mobile e Internet sempre più frequente:
comunicazioni a voce e a video su IP
 biblioteche virtuali
 conference calling indipendenti da luogo e da operatori
 telelavoro
 giochi on line
 video e musica on-demand
 supporto al traffico (navigazione e info su congestione vie)
 reperimento di informazioni “location-based”
SOMMARIO
I.
II.
Principali funzioni del TCP
Problematiche proprie di un ambiente
wireless con particolare attenzione a quelle
correlate con il TCP
III. Tipologia di soluzioni proposte ed esempi
(Snoop Protocol, TCP Westwood)
IV. Un applicazione pratica per lo streaming
video.
Collocazione di TCP
OSI - ISO
Internet
Applicazione
Presentazione
Applicazione
Sessione
Trasporto
Trasporto - TCP
Rete
Rete
Collegamento
Fisico
Collegamento
Caratteristiche e funzionalità di TCP
•
•
•
•
Affidabilità della trasmissione
Rilascio ordinato dei pacchetti (segmenti) al livello superiore
Semantica End-to-End della connessione
Controllo del flusso:
– Ack cumulativi
– Sliding window
• Controllo della congestione:
– Scadenza di timeout o ricezione di 3 DUPACK: perdita di pacchetto
• Perdite dovute a congestione
• Riduzione della finestra di invio
TCP: Controllo della Congestione
Contesto Wireless
GEO Satellite
Sat
UAV + proxy
802.11
Urban Environment
Gatew ay
Last Hop
Ad Hoc
Internet
Diagramma interazione TCP-Wireless
Bandwidth Latenza Pacch. Disconn. BER Bandwidth Incapac. Errori Latenza
elevata piccoli: handoff e elevato variabile
bassa
distinz. in burst variab.
framm. fading
errore –
congest.
Diffic. stima
RTT-RTO
Perdita di tanti
pacchetti
Timeout a
sproposito
Restringimento
finestra di invio
Ritrasmiss.
ridondanti
Spreco di
Bandwidth
Spreco di tempo
Legenda:
Data Rate basso
Caratteristica Caratteristica Problema
wireless
TCP
conseguente
Spreco di
Energia
Tassonomia delle soluzioni
(livello di trasporto)
• Divisione della connessione:
– Ritrasmissioni locali
– Tempestività nell’intervenire sul tratto wireless
– TCP specifico sul wireless
• End-to-End puro:
– Nuovo protocollo di trasporto
– Mittente consapevole del tratto wireless
– Rispetto del paradigma End-to-End
Protocolli di trasporto
TCP tradizionali:
•
•
•
•
TCP Reno
TCP New Reno
TCP Vegas
TCP Sack
Divisione della
connessione:
• I-TCP
• M-TCP
• Snoop Protocol
End-to-End puri:
•
•
•
•
•
•
•
Delayed Dupacks
TCP-Aware
Freeze-TCP
TCP Probing
WTCP
Fast TCP
TCP Westwood
Snoop Protocol (Balakrishnan et al., 1995)
• Ideato per combattere le conseguenze dei BER elevati
• Implementa nella base station uno Snoop Agent:
– Monitoraggio di tutti i pacchetti in transito in entrambe
le direzioni
– Memorizzazione dei pacchetti non ancora confermati da
ack in una cache presente nella base station:
• Ritrasmissioni locali dei dati persi e filtraggio dei dupack
allo scopo di evitare che il mittente invochi meccanismi
per il controllo della congestione.
TCP modificato
Internet
Base Station
(Snoop Agent)
Snoop Protocol – Esempio (1/9)
15
20
16
17
19
18
18
17
14
Legenda:
dati
in cache
16
perso
ack
dupack
16
Snoop Protocol – Esempio (2/9)
15
16
21
17
20
18
19
14
Legenda:
dati
19
18
16
16
in cache
perso
ack
dupack
Snoop Protocol – Esempio (3/9)
17
18
19
20
22
21
20
19
16
18
16
14
Legenda:
dati
in cache
perso
ack
dupack
16
Snoop Protocol – Esempio (4/9)
17
20
18
19
21
19
23
22
21
16
Legenda:
dati
20
16
in cache
perso
18
16
ack
dupack
16
Snoop Protocol – Esempio (5/9)
17
20
21
18
19
22
20
19
Ritrasmissione
24
23
17
21
16
18
16
16
16
Legenda:
dati
in cache
Dupack scartati da BS
perso
ack
dupack
16
Snoop Protocol – Esempio (6/9)
20
21
17
18
22
23
19
21
20
19
25
24
22
17
16
16
Legenda:
dati
16
in cache
18
16
Dupack scartati da BS
perso
ack
dupack
16
Snoop Protocol – Esempio (8/9)
25
20
21
27
17
18
19
22
23
24
26
24
23
21
21
Niente Fast Retransmit
16
Legenda:
dati
16
16
16
in cache
Dupack scartati da BS
perso
ack
dupack
Snoop Protocol – Esempio (7/9)
20
21
17
18
19
17
22
23
24
21
20
19
26
25
23
22
16
18
21
Niente Fast Retransmit
16
Legenda:
dati
16
16
in cache
Dupack scartati da BS
perso
ack
dupack
16
Snoop Protocol – Esempio (9/9)
25
26
22
28
27
23
24
25
24
21
Legenda:
dati
in cache
23
perso
ack
dupack
21
Snoop Protocol: Pro & Cons
• Vantaggi:
– Preserva la semantica
End-to-End
– Effettua recupero locale (e
tempestivo) delle perdite
– Affronta BER elevati
• Svantaggi:
– Richiede RTT brevi sul
tratto wireless
– Non gestisce
adeguatamente le lunghe
disconnessioni
– Non utilizzabile subito
dopo un handoff (assenza
di pacchetti nella nuova
cache)
TCP Westwood (Mascolo et al., 2001)
• Utilizzo di meccanismi puramente End-to-End
• Controllo del flusso basato sulla stima della bandwidth
disponibile (BWE):
– Monitoraggio della frequenza di arrivo degli ack al mittente
– Utilizzo di BWE per impostare cwnd e ssthresh:
Arrivo di tre dupack:
Scadenza di timeout:
• ssthresh=BWE*RTTmin
• ssthresh=BWE*RTTmin
anziché TCP Reno:
Ssthresh = cwnd/2
anziché TCP Reno:
Ssthresh = cwnd/2
• se(cwnd > ssthresh)
allora cwnd=ssthresh
• cwnd = 1
TCP Westwood (1/3)
dk (bit ricevuti nell’intervallo)
tk-1
tk tk+1
• La prima (e piu’ semplice) versione di TCPW utilizzava
uno stimatore di bandwidth (BWE) dato da:
bk  d k /(t k  t k 1 )
campione
 bk  bk 1 
filtro
BWE k   k BWE k 1  1   k 
 esponenziale
2


2  t k
k 
2  t k
guadagno del filtro
TCP Westwood (2/3)
dk-1 dk
tk
(intervallo di campionamento)
T
• Stima della bandwidth ottenuta per aggregazione dei dati
ricevuti durante l’intervallo T.
bk 

dj
t j tk T
campione
T
 bk  bk 1 
filtro
RE k   k RE k 1  1   k 

2  esponenziale

k 
2  t k
2  t k
guadagno del filtro
TCP Westwood (3/3)
• La dimensione dell’intervallo di campionamento viene
continuamente adattato seguendo il livello di congestione
misurato
Tk
adattamento
continuo
senza congestione: Tk = inter ACK
(risulta una stima piu’ aggressiva)
Tk  RTT * (
Throughput massimo,
assumendo che non vi sia
congestione nel collegamento
Tk
con congestione: Tk cresce
(risulta una stima piu’ prudente)
cwin
cwin
 Thˆk ) /
RTT min
RTT min
Throughput corrente reale
TCP Westwood (ssthresh a confronto)
cwnd
capacità del canale
TCP Westwood
TCP Reno
ssthresh =
BWE * RTTmin
guadagno
ssthresh media
TCP Reno
Perdite casuali
tempo
TCP Westwood: Pro & Cons
• Vantaggi:
– Stima della bandwidth al
mittente per impostare la
ssthresh e la cwnd che
gli permette throughput
elevati
– Modifiche del codice
richieste solo al mittente
– Fair & Friendly
• Svantaggi:
– Stima della bandwidth
falsata in collegamenti
asimmetrici
– Assenza di meccanismi
specifici per gestire
disconnessioni
– Scarse prestazioni su pipe
piccole
– Prestazioni al variare delle
dimensioni dei buffer?
Analisi attraverso un modello di confronto
• Problematiche NON
prestazionali:
–
–
–
–
–
–
–
–
• Problematiche prestazionali:
– Gest. disconness.
– Limitaz. spreco
tempo
– Gest. BER elevato
– Discriminaz perdite
– Finestra invio non
eccesivam. ridotta
– Limitaz. difficoltà
calcolo RTT e RTO
– Limitaz. ridondanze
Ricevente inalterato
Mittente inalterato
Nodi inalterati
Traffico criptato
Semantica E2E
Risparmio energia
Collegam. asimmet.
Fair & Friendly
Legenda:
Snoop
Westwood
Approcci per il controllo del flusso
• RAP (Rate Adaptation Protocol)
somiglianza con TCP (meccanismo AIMD); adattamento del video trasmesso
• SR-RTP (Selective Retransmission-RTP)
Ritrasmette solo alcuni tipi di pacchetti che trasportano informazioni chiave
• SCTP (Stream Control Transmission Protocol)
somiglianza con TCP; multistream;
• TFRC (TCP-Friendly Rate Control)
somiglianza con TCP tramite equazioni;
Limitazioni:
– Il meccanismo AIMD (Additional Increase Multiplicative Decrease) provoca
oscillazioni nella frequenza di trasmissione
– Scarsa utilizzazione della bandwidth disponibile in presenza di errori random
Caratteristiche MPEG-4
Compressione realizzata grazie alla compresenza di
frame di diverso tipo (per importanza e dimensioni):
• Intra-coded frames (I-frames) sono codificati indipendentemente
dagli altri frame; fungono da frame di riferimento.
• Predicted frames (P-frames) dipendono dal frame che li precede
(I o P); contengono dati di movimento immagine e informazioni su
errori.
• Bi-directionally predicted frames (B-frames) dipendono sia dal
frame precedente e sia da quello succesivo.
VTP: Video Transport Protocol
Caratteristiche principali:
• Stima della bandwidth utilizzata per adattare il flusso
video
• Utilizzo dei livelli di compressione disponibili in MPEG-4
allo scopo di selezionare la qualita’ video piu’ appropriata
per la trasmissione
• Mantenimento di un frame rate costante in modo da
preservare la qualita’ percepita del video
• Equo utilizzo del canale con TCP preservato
Stima della Bandwidth
• Il ricevente stima la Bandwidth disponibile
• Tecnica di stima della Bandwidth ispirata al
meccanismo di TCP Westwood):
Bi=()Bi-1+(1-)(bi+bi-1)/2
Bi: stima della bandwidth
bi: bandwidth sample (bits_nel_pacchetto/ intervallo tra arrivo di
pacchetti)
: coefficiente modificabile
• Il ricevente retro-invia al mittente la stima della
bandwidth periodicamente (almeno ogni RTT)
Algoritmo VTP
• Copie multiple dello stream video con diversi livelli di quantizzazione
(compressione) sono disponibili sul server
• Lato mittente: se la stima della bandwidth comunicata dal ricevente e’
maggiore o uguale alla frequenza di invio, allora incrementa
gradualmente (un pacchetto per RTT) la frequenza di invio (probing
phase)
• Quando la stima della bandwidth e’ sufficiente da supportare il livello
di quantizzazione successivo, utilizza lo stream video con un livello
di qualita’ superiore e maggiore bitrate.
• Se la stima della bandwidth ricade sotto la frequenza di invio corrente,
utilizza un livello di quantizzazione inferiore
Cambiameto di rate e codifica
DR = Stato di Decremento
IR = Stato di Incremento
Q1, Q2, Q3: Stati di codifica MPEG
Esempio: supponiamo di trovarci in Q1
Se la stima della bandwidth eccede l’ultimo valore, andiamo da Q1 a IR1.
Controlliamo se la bandwidth e’ sufficiente per supportare Q2. Se non lo e’,
incrementiamo il rate e ritorniamo in Q1. Altrimenti, andiamo in Q2.
VTP vs TFRC con errori
VTP vs TFRC con perdite casuali – stessa traccia video per entrambi
CONCLUSIONI
• Integrazione di Internet con ambiente
wireless: caratteristiche e problematiche
• Analisi critica di soluzioni differenti
• Esempio di applicazione derivata da una
delle soluzioni proposte