TCP E APPLICAZIONIIN AMBIENTE WIRELESS

Claudio Enrico Palazzi cpalazzi@cs.unibo.it

Alma Mater Studiorum – Università di Bologna

27 aprile 2004

Facoltà di Scienze Matematiche Fisiche e NaturaliCorso di laurea in Scienze dell’Informazione

Sistemi e Applicazioni Multimediali

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, …)

Ad Hoc

Internet

Last Hop

Gateway

802.11

GEO Satellite

UAV + proxy

Urban Environment

Sat

Internet e wireless 2/2

• Prospettiva futura:– Interazione tra mobile e Internet sempre più frequente:

comunicazioni a voce e a video su IP biblioteche virtualiconference calling indipendenti da luogo e da operatoritelelavorogiochi on linevideo e musica on-demandsupporto al traffico (navigazione e info su congestione vie)reperimento di informazioni “location-based”

SOMMARIO

I. Principali funzioni del TCPII. 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.

Architettura TCP/IP

Applicazione

Presentazione

Sessione

Trasporto

Rete

Collegamento

Fisico

OSI - ISO Internet

Applicazione

Trasporto -

Rete

Collegamento

TCP

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

TCP New Reno

Contesto Wireless

Ad HocInternet

Last Hop

Gatewa y

802 .11

GE O Sat elli te

UA V + proxy

Urba n Enviro nme nt

Sat

Diagramma interazione TCP-WirelessBER

elevatoIncapac. distinz. errore –congest.

Latenza variab.

Disconn. handoff e fading

Errori in burst

Latenza elevata

Pacch.piccoli: framm.

Perdita di tanti pacchetti

Diffic. stimaRTT-RTO

Timeout a sproposito

Spreco di Energia

Ritrasmiss. ridondanti

Restringimentofinestra di invio

Spreco di tempo

Spreco di Bandwidth

Data Rate basso

Bandwidthbassa

Bandwidth variabile

Caratteristicawireless

CaratteristicaTCP

Problemaconseguente

Legenda:

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

• I-TCP• M-TCP• Snoop Protocol

• Delayed Dupacks• TCP-Aware• Freeze-TCP• TCP Probing• WTCP• Fast TCP• TCP Westwood

• TCP Reno• TCP New Reno• TCP Vegas• TCP Sack

TCP tradizionali:Divisione della connessione: End-to-End puri:

Snoop Protocol• 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.

InternetInternetBase Station

(Snoop Agent)

TCP modificato

Snoop Protocol – Esempio (1/9)

20 19 1718

1614

16 17 1815

ackdati in cache persoLegenda: dupack

16

Snoop Protocol – Esempio (2/9)

21 20 1819

1614

16 17 1815

19

ackdati in cache persoLegenda: dupack

16

Snoop Protocol – Esempio (3/9)

22 21 1920

1616

17 18

20

ackdati in cache persoLegenda:

19

dupack

14

18

16

Snoop Protocol – Esempio (4/9)

23 22 2021

1616

17 18

20

ackdati in cache persoLegenda:

19

dupack

21

16

19

18

16

Snoop Protocol – Esempio (5/9)

24 23 2117

16

17 18

20

ackdati in cache persoLegenda:

19

dupack

21

16

22

16 Dupack scartati da BS

Ritrasmissione

20

16

19

18

16

Snoop Protocol – Esempio (6/9)

25 24 1722

16

17 18

20

ackdati in cache persoLegenda:

19

dupack

21

16

22

16 Dupack scartati da BS

23

16

21

20

19

18

16

Snoop Protocol – Esempio (7/9)

26 25 2223

16

17 18

20

ackdati in cache persoLegenda:

19

dupack

21

21

22

16 Dupack scartati da BS

23

16

24

16

Niente Fast Retransmit

17

21

20

19

18

16

Snoop Protocol – Esempio (8/9)

27 26 2324

21

17 18

20

ackdati in cache persoLegenda:

19

dupack

21 22

16 Dupack scartati da BS

23

16

24

1616

25

Niente Fast Retransmit

21

Snoop Protocol – Esempio (9/9)

28 27 2425

23

ackdati in cache persoLegenda: dupack

22 23 24

25 26

21 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• 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:

• ssthresh=BWE*RTTminanziché TCP Reno:

Ssthresh = cwnd/2

• se(cwnd > ssthresh) allora cwnd=ssthresh

• ssthresh=BWE*RTTminanziché TCP Reno:

Ssthresh = cwnd/2

• cwnd = 1

Arrivo di tre dupack: Scadenza di timeout:

TCP Westwood (1/3)

• La prima (e piu’ semplice) versione di TCPW utilizzava uno stimatore di bandwidth (BWE) dato da:

)/( 1−−= kkkk ttdb

tk-1 tk

dk (bit ricevuti nell’intervallo)

( ) ⎟⎠⎞

⎜⎝⎛ +

−+= −− 2

1 11

kkkkkk

bbBWEBWE αα

campione

filtro esponenziale

k

kk t

t∆+∆−

=ττ

α22

guadagno del filtro

tk+1

TCP Westwood (2/3)

• Stima della bandwidth ottenuta per aggregazione dei dati ricevuti durante l’intervallo T.

( ) ⎟⎠⎞

⎜⎝⎛ +

−+= −− 2

1 11

kkkkkk

bbRERE αα

campione

filtro esponenziale

k

kk t

t∆+∆−

=ττ

α22

guadagno del filtro

dk

T

dk-1

T

d

k

jTktjtb

∑= −>

tk(intervallo di campionamento)

TCP Westwood (3/3)

• La dimensione dell’intervallo di campionamento vienecontinuamente adattato seguendo il livello di congestionemisurato

Tk

con congestione: Tk cresce(risulta una stima piu’ prudente)

Tk

adattamentocontinuo

senza congestione: Tk = inter ACK(risulta una stima piu’ aggressiva)

minmin

/)ˆ(*RTTcwinhT

RTTcwinRTTT kk −=

Throughput massimo, assumendo che non vi sia

congestione nel collegamentoThroughput corrente reale

TCP Westwood (ssthresh a confronto)

cwnd

tempo

ssthresh = BWE * RTTmin

capacità del canale

TCP WestwoodTCP Reno

Perdite casuali

ssthresh media TCP Reno

guadagno

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 delledimensioni dei buffer?

Analisi attraverso un modello di confronto• Problematiche NON

prestazionali:– Ricevente inalterato– Mittente inalterato– Nodi inalterati– Traffico criptato– Semantica E2E– Risparmio energia– Collegam. asimmet.– Fair & Friendly

• 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

Snoop WestwoodLegenda:

Videostreaming - Background

• Applicazioni Internet multimedia streaming in aumento• La maggior parte di real-time video utilizza UDP:

– nessun controllo della congestione– no ACK, no ritrasmissioni– pacchetti di dati inviati con rate prestabilito dal mittente.– potenziale collasso della congestione

• Ricerca di soluzioni alternative volte a creare dei protocolliper lo streamin video (ma anche audio) che incorporinomeccanismi di controllo della congestione

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 diframe di diverso tipo (per importanza e dimensioni):

• Intra-coded frames (I-frames) sono codificati indipendentementedagli 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 suerrori.

• Bi-directionally predicted frames (B-frames) dipendono sia dalframe 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 dapreservare 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 bandwidthbi: bandwidth sample (bits_nel_pacchetto/ intervallo tra arrivo di

pacchetti)α: coefficiente modificabile

• Il ricevente retro-invia al mittente la stima dellabandwidth 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 incrementagradualmente (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 DecrementoIR = Stato di Incremento

Q1, Q2, Q3: Stati di codifica MPEG

Esempio: supponiamo di trovarci in Q1Se 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

Breve Bibliografia

• H. Balakrishnan, S. Seshan, E. Amir, R. H. Katz, "Improving TCP/IP Performance over Wireless Networks", Proc. ACMMobiCom '95, Berkeley, CA, USA, vol. 2, n. 11, pp. 2 - 11, November 1995.

• C. Casetti, M. Gerla, S. Mascolo, M. Y. Sanadidi, and R. Wang, "TCP Westwood: Bandwidth Estimation for Enhanced Transport over Wireless Links", In Proceedings of ACMMobicom 2001, pp 287-297, Rome, Italy, July 16-21 2001

• Alex Balk, Dario Maggiorini, Mario Gerla, M. Y. Sanadidi "Adaptive MPEG-4 Video Streaming with Bandwidth Estimation", QOS-IP 2003, Milano, Italy, February 2003