Evaluation de Performances

Modélisation des Réseaux TCP/IP

Olivier BRUN et Urtzi Ayesta

Modelisation des r eseaux TCP/IP – p.1/27

Plan

Introduction

Debit d’une connnexion TCP

Point Fixe TCP

Modelisation des r eseaux TCP/IP – p.2/27

Introduction

Modelisation des r eseaux TCP/IP – p.3/27

Introduction

Les flux Internet sont pilot es par TCP ou UDPTCP et UDP sont des protocoles de niveau Transport

TCP: Transmission Control Protocol.

UDP : User Datagram Protocol.

Physical

Data Link

Network

Transport

Session

Presentation

Application

Modelisation des r eseaux TCP/IP – p.4/27

Introduction

Constitution du trafic InternetCapture sur un lien OC-12 chez Sprint

Large majorit e de flux et de paquets TCP, trafic UDP sensible (VoIP)

Modelisation des r eseaux TCP/IP – p.5/27

Introduction

Transmission Control ProtocolTCP fournit un service de transfert de donn ees fiable et orient econnexion dans les r eseaux a commutation de paquets

Applications: flux non temps r eel tels que web, e-mail, ftp, remote login, etc.

User Datagram ProtocolUDP fournit un service de transfert de donn ees non fiable en modenon connect e

Applications: flux temps r eel tels que streaming audio ou vid eo.

On pr esente dans la suite un rappel rapide dufonctionnement de TCP

Modelisation des r eseaux TCP/IP – p.6/27

Aperçu de TCP

TCP fournit un service fiable orient e connexion enutilisant des ACKs, des num eros de s equence etdes timers

TCP impl emente un m ecanisme de contr ole de congestion AIMD

(Additive Increase, Multiplicative Decrease) en utilisan t une fen etre

glissante.

La taille de la fen etre repr esente le nombre maximum de paquets non

acquitt es qui peuvent etre pr esents sur le r eseau,

La taille de la fen etre evolue en fonction des conditions de trafic sur le

reseau.

Modelisation des r eseaux TCP/IP – p.7/27

Aperçu de TCP

Parametres de TCP wnd : fen etre de congestion de l’ emmeteur,rwnd : fen etre de congestion du recepteur,wm = min( wnd; rwnd) : taille maximale de la fen etre de

congestion,RTT : round trip time,RTO: retransmission timeout

Modelisation des r eseaux TCP/IP – p.8/27

Aperçu de TCP

Etablissement de la connexion TCP:

3-WAY handshake.

Slow Start:Incr emente wnd de 1 a chaque ACK ( w=RTT )

Augmentation agressive pour determiner le d ebit max.

Client

Server

temps

cwnd=1 cwnd=2 cwnd=4

Slow StartConnection Establish.

Modelisation des r eseaux TCP/IP – p.9/27

Aperçu de TCP

Congestion Avoidance (CA)

TCP sort du slow start quand wnd atteint un seuil ( ssthresh)

Incr emente wnd de 1 a chaque RTT (1=RTT )

Reste dans la phase CA jusqu’ a ce que:TimeOut Loss: TCP retourne en slow start ( wnd = 1)

Triple Duplicate ACKs: wnd = wnd=2Client

Server

cwnd=5 cwnd=6cwnd=4

temps

Congestion Avoidance

Modelisation des r eseaux TCP/IP – p.10/27

Aperçu de TCP

Evolution du d ebit TCP

Modelisation des r eseaux TCP/IP – p.11/27

Variantes de TCP

On a pr esent e les grands principes de TCP

Il existe diff erentes versions

TCP Tahoe: r eduit wnd a 1 en cas de perte, utilise le slow start pour

revenir au d ebit ant erieur

TCP Reno : Fast Recovery sans utilisation du slow start.

TCP newReno et TCP Sack: r eagissent a une seule perte par RTT

TCP ECN (Explicit Congestion Notification): les routeurs ma rquent les

paquets pour indiquer la congestion

Modelisation des r eseaux TCP/IP – p.12/27

Débit d’un flux TCP

Modelisation des r eseaux TCP/IP – p.13/27

Débit d’un flux TCP

Modele simplifi e de TCPOn ne consid ere que la phase CA (connexions persistentes).

On neglige les pertes TO

A chaque ACK recu on augmente W (t) de 1.

A chaque perte on r eduit W (t) de moiti e.

Modelisation des r eseaux TCP/IP – p.14/27

Débit d’un flux TCP

Modele simplifi e de TCPLa taille de la fen etre W (t) varie entre W=2 et W , ou W est la taille

maximale de la fen etre d’anticipation.

On veut calculer le d ebit moyen D de TCP.Soit L le nombre moyen de paquets transmis dans un cycle CA (entre 2 p ertes)

Soit S la dur ee moyenne du cycle CA

On a: D = L=SModelisation des r eseaux TCP/IP – p.15/27

Débit d’un flux TCP

Analysela dur ee moyenne du cycle est S = RTT �W=2.

Le nombre moyen de paquet transmis pendant un cycle est:

L = W=2Xi=0 (W=2 + i) = 3W 2 + 5W8 � 3W 28 :

Debit moyen TCP : D = LS = 3W4RTT paquets=s:

Modelisation des r eseaux TCP/IP – p.16/27

Débit d’un flux TCP

AnalyseOn suppose que chaque paquet est perdu de facon independant e avecune probabilit e p.

Distribution g eometrique du nombre de paquets transmis avant perte:pi = (1� p)i�1 � p

Nombre moyen de paquets transmis avant perte: L =Pi i pi = 1pDe L = 3W 2=8, on d eduit W =q 83p

Debit moyen TCP :

D = 3W4RTT = 1RTT � r 32p paquets=s:

Cette formule est connue sous le nom formule SQRT (Square roo t

Throughput) pour le d ebit de TCP.

Modelisation des r eseaux TCP/IP – p.17/27

Débit d’un flux TCP

Cons equences de la formule SQRT

Le debit d’une connexion est inversement proportionnel a la racinecarr ee de la probabilit e de perte.

Les performances de TCP dans les r eseaux sans fils ne sont pas satisfaisantes car

la perte d’un paquet ne signifie pas qu’il y a congestion (erre urs de transmissions).

Le debit d’une connexion est aussi inversement proportionnel a u RTT.Les performances de TCP ne sont pas satisfaisantes lorsque l e RTT est tr es long

(e.g. lien satellite: RTT � 500ms).

Le debit moyen TCP est proportionnel a la taille en octet des paquets.

Modelisation des r eseaux TCP/IP – p.18/27

Débit d’un flux TCP

Precision de la formule SQRT

Comparaison avec des simulation evenementielles.

Modelisation des r eseaux TCP/IP – p.19/27

Point Fixe TCP

Modelisation des r eseaux TCP/IP – p.20/27

Point Fixe TCP

On consid ere:

Un reseau IP constitu es de plusieurs routeurs et de plusieurs liens,

Un ensemble de flux TCP traversant ce r eseau, chaque flux

repr esentant plusieurs connexions TCP persistentes.

Objectifs

Determiner le d ebit moyen et la probabilit e de perte associ es a chaque

flux TCP,

Determiner la charge et la probabilit e de perte de chaque lien,

Identifier les goulots d’ etranglement.

Modelisation des r eseaux TCP/IP – p.21/27

Point Fixe TCP

Notations:

Soit V l’ensemble des liens du r eseau.On note �v la bande-passante du lien v 2 V ,

On note pv la probabilit e de perte d’un paquet sur le lien v 2 V .

On note p le vecteur des probabilit es de perte.

Soit I l’ensemble des flux TCP:On note Ti le d ebit de chaque connexion du flux i 2 I ,

On note Ni le nombre (fixe) de connexions du flux i 2 I ,

On note �i = hvi1; : : : ; vin(i)i le chemin des connexions TCP du flux i 2 I , ou vij

est le jeme lien sur le chemin,

On note �i(u) = �vi1; : : : ; u� le meme chemin jusqu’au lien u

On note �i la probabilit e de perte d’un paquet du flux i 2 I de bout-en-bout.

Modelisation des r eseaux TCP/IP – p.22/27

Point Fixe TCP

Hypoth ese d’ind ependance des probabilit e deperte:

�i(p) = Xv2�i pv Yu2�i(v)�v (1� pu) i 2 IHypoth ese: bande-passante � delai grand

Les d elais de queueing deviennent n egligeable.

On utilise la formule SQRT pour le d ebit TCP

Ti(�i) = MSSi � min� 1RTTi r st�i ; W imaxRTTi � i 2 I

Modelisation des r eseaux TCP/IP – p.23/27

Point Fixe TCP

Debit des flux sur le lien v 2 V :

rv(p) =Xi2I i;v0� Yu2�i(v) (1� pu)1A Ni Ti(�i)

ou i;v = 1 si le flux i passe par le lien v et 0 sinon.

Le debit sur un lien doit etre inf erieur a sa capacit e

rv(p) � �v v 2 VjV j in egalit es avec jV j inconnus p1; : : : ; pjV j.Modelisation des r eseaux TCP/IP – p.24/27

Point Fixe TCP

Observation: 2 etats possibles pour un lien

Soit satur e (�v = rv(p)) : fortes pertes de paquets en entr ee,

Soit sous utilis e (rv(p) < �v) : probabilit e de perte n egligeable.

Condition de compl ementarit e

pv (�v � rv(p)) = 0 v 2 VLes paquets ne sont perdus que par les bottlenecks

Si rv(p) < �v , alors pv = 0.

Conditions suppl ementaires:0 � pv � 1 v 2 V

Modelisation des r eseaux TCP/IP – p.25/27

Point Fixe TCP

Les equations pr ecedentes admettent un uniquevecteur solution p

Le vecteur solution p des probabilit es de perte estsolution de l’ equation de point fixe,

pv = Pr[0;1℄ fpv � � (�v � rv(p))gou � > 0 est un param etre et ou Pr[0;1℄ est la projection sur l’intervalle[0; 1℄

Pr[0;1℄(x) = 8>><>>: 0, x < 0,x, 0 � x � 1,

1, 1 < x.

Modelisation des r eseaux TCP/IP – p.26/27

Point Fixe TCP

Algorithme de r esolution

p(k+1)v = Pr[0;1℄ npkv � � ��v � rv(p(k))�oConverge vers une solution unique quelle que soit les valeur s initiales

des probabilit es

Choix du param etre �:Demarrer avec une valeur de � assez grande, e.g. �=0.01

Diviser � par 2 si pv > 1 ou pv < 0 ou si l’erreur relative augmente

Convergence en moins de 100 iterations...

Prise en compte des d elais de queueing:Inclure le d elais de queueing �v �Buffer Size(v) des liens

bottlenecks v dans l’estimation du RTT.

Modelisation des r eseaux TCP/IP – p.27/27