Remerciementsicapeople.epfl.ch/elfawal/Rapports/DEA02.doc · Web viewEn diminuant p, l’utilité de FEC diminue, une chose intuitive et vérifiée dans les chapitres précédents

UNIVERSITE LIBANAISE UNIVERSITE SAINT-JOSEPH(Faculté de Génie) (Faculté d'Ingénierie)

Sous l'égide de l'Agence Universitaire de la FrancophonieAUF

Diplôme d'Etudes ApprofondiesRéseaux de télécommunications

Projet effectué au sein du Projet Planète, INRIA (Institue National de Recherche en Informatique et en Automatique), Sophia Antipolis, France.

Sujet

Analyse et Optimisation du Modèle Hybride FEC/ARQ-SR Appliqué au Niveau de la Couche Liaison des Liens Sans Fil pour des Connexions TCP

de Longue Durée

Par

Alaeddine Al Fawal

Encadré par : M. Chadi Barakat, INRIA.

Soutenance le 15 Avril 2003 devant le jury composé de

MM. Samir Tohmé PrésidentMohamad Zoaeter Membre

Wajdi Najem MembreImad Mougharbel MembreNicolas Rouhana Membre

Mahmoud Doughan MembreMaroun Chamoun Membre

Remerciements

D’abord je profite de cette occasion pour adresser mes sincères remerciements à

M. Mohamad ZOAETER, doyen de la faculté de génie de l’université libanaise, M. Wajdi

NAJEM, doyen de l’école supérieure d’ingénierie de Beyrouth, M. Samir TOHME et M.

Imad MOUGHARBEL, responsables scientifique et administratif du DEA, pour leur

gestion sage et les bonnes conditions d’études qu’ils nous ont procurées.

Je tiens également à remercier vivement M. Walid DABBOUS, le responsable du

projet PLANETE. Il m’a fait bénéficier de ses conseils et ses compétences, soulignant

ainsi l’intérêt qu’il porte à mes travaux. Je le remercie pour m’avoir accueilli dans son

projet.

Je ne trouve pas les mots pour exprimer ma gratitude envers M. Chadi

BARAKAT, mon directeur de stage. Ses conseils et ses encouragements ont permis à ce

travail d’aboutir. Ses capacités scientifiques et ses compétences étaient mon grand

support. Faire mon projet sous sa direction était pour moi un grand honneur et un

immense bonheur. La liberté qu’il m’a accordé et les responsabilités qu’il m’a confiées

ont beaucoup contribué à la formation de ma personnalité et à mon autonomie de travail.

Je dois aussi une grande partie de mon travail à M. Mahmoud DOUGHAN. Ses

conseils m’ont aidé à surmonter beaucoup de difficultés. Je le remercie chaleureusement

pour sa pédagogie, sa patience, sa disponibilité et son dévouement.

Mes remerciements vont aussi à tous les membres du jury. Je les remercie pour le

soutien et l’attention qu’ils nous ont prêtés pendant toute la durée du DEA.

Je tiens aussi à remercier tous les gens du projet PLANETE, chercheurs,

thésards, stagiaire et visiteurs, pour leur disponibilité, leur sympathie, et pour

l’ambiance amicale qui règne au sein du projet. Je remercie particulièrement Mme

Aurélie RICHARD, assistante du projet, pour sa disponibilité et sa bonne humeur.

Enfin je ne peux pas oublier les gens de la faculté de génie I de l’université

libanaise où était le début de mon chemin scientifique. Je les remercie sincèrement pour

m’avoir donner ce niveau d’ingénieur, ce niveau qui a constitué mon véritable appui et

mon support durant ce travail et il le fera le long du mon chemin professionnel…

Résumé

Puisque le protocole TCP utilise la perte des paquets comme une indication de congestion du réseau, sa performance se dégrade sur les liens sans fil, qui sont caractérisés par un taux d'erreurs élevé. Différentes solutions sont proposées pour améliorer la performance de TCP sur les liens sans fil, la plus prometteuse étant l'utilisation d'un modèle hybride combinant, au niveau de la couche liaison, FEC, ARQ-SR (Automatic Repeat Request with Selective Repeat), et la livraison en-ordre des paquets à IP. L'inconvénient de FEC est qu'elle consomme une partie supplémentaire de la bande passante pour transmettre ses informations redondantes. ARQ-SR ne consomme pas beaucoup de bande passante, son problème est qu'elle augmente le délai aller-retour RTT des paquets, qui peut détériorer la performance de TCP, si elle n ‘est pas appliquée convenablement.

Nous étudions dans ce rapport la performance de TCP sur un lien sans fil disposant du mécanisme hybride FEC/ARQ-SQ. L'étude est faite en simulant et en modélisant analytiquement des transferts TCP de longue durée sur des liens sans fil présentants des erreurs de Bernoulli. Nous sommes motivés par savoir comment on doit régler les différents paramètres du modèle, par exemple la quantité de FEC à utiliser, la persistance de ARQ, les tailles des trames et des paquets, afin d’optimiser la performance de TCP. Nous présentons une étude très détaillée des impacts des différents paramètres du modèle sur la performance de TCP. Cette étude est couronnée par une optimisation du modèle en fonction des caractéristiques physiques du lien sans fil (délai, taux d'erreur) et de la charge de trafic (nombre de connexions TCP). La même procédure est répétée pour un autre mécanisme hybride, ARQ-SR-protégée-par-FEC. Aussi, On trouve dans ce rapport une comparaison entre les deux mécanismes.

Mots-clés : TCP, liens sans fil, FEC, ARQ, mécanisme hybride FEC/ARQ, modélisation, NS-2, simulation, évaluation de performance.

Références : Alaeddine AL FAWAL, Chadi BARAKAT, « Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SR For Wireless Links and Long-Lived TCP traffic », WiOpt’03 : Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Sophia Antipolis, France, March 2003.

Chadi BARAKAT, Alaeddine AL FAWAL, « Analysis of link-level hybrid FEC/ARQ-SR for wireless links and long-lived TCP traffic », INRIA research report No 4752, February 2003.

Abstract

Since the TCP protocol uses the loss of packets as an indication of network congestion, its performance degrades over wireless links, which are characterized by a high bit error rate. Different solutions have been proposed to improve the performance of TCP over wireless links, the most promising one being the use of a hybrid model at the link-level combining FEC, ARQ-SR (Automatic Repeat Request with Selective Repeat), and an in-order delivery of packets to IP. The drawback of FEC is that it consumes some extra bandwidth to transmit the redundant information. ARQ-SR does not consume much bandwidth, its drawback is that it increases the round-trip time (RTT), which may deteriorate the performance of TCP, if not done appropriately.

We study in this paper the performance of TCP over a wireless link implementing hybrid FEC/ARQ-SQ. The study is done by simulating and modeling long-lived TCP transfers over wireless links showing Bernoulli errors. We are motivated by how to tune link-level error recovery e.g. amount of FEC, persistency of ARQ, frame size, so as to maximize the performance of TCP. We present a detailed study of the impact of the different parameters on the performance of TCP. This study is accompanied by an optimization of the model according to the physical characteristics of the wireless link (delay, error rate) and the traffic load (number of TCP connections). The same procedure is repeated for another hybrid error recovery mechanism, ARQ-SR-Protected-By-FEC. We include in this report a comparison of two mechanisms.

Keywords : TCP, wireless link, FEC, ARQ, hybrid FEC/ARQ, modeling, NS-2, simulation, performance evaluation.

References : Alaeddine AL FAWAL, Chadi BARAKAT, « Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SR For Wireless Links and Long-Lived TCP traffic », WiOpt’03 : Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Sophia Antipolis, France, March 2003.

Chadi BARAKAT, Alaeddine AL FAWAL, « Analysis of link-level hybrid FEC/ARQ-SR for wireless links and long-lived TCP traffic », INRIA research report No 4752, February 2003.

Chadi BARAKAT, PhD Sophia Antipolis, le 27 Janvier 2003

INRIA – projet PLANETE2004, route des Lucioles06902 Sophia Antipolis - France

Tel : + 33 (0) 4 92 38 75 96Fax : +33 (0) 4 92 38 79 78Email : [email protected] : http://www.inria.fr/planete/chadi

ATTESTATION

Je, soussigné Chadi BARAKAT, chargé de recherche dans le projet PLANETE de l’INRIA Sophia Antipolis, écris cette attestation en faveur de M. Alaeddine AL FAWAL, de nationalité libanaise, né le 29/10/1977. Cette attestation servira comme document d’évaluation du stage de DEA que M. AL FAWAL a effectué sous ma direction au sein du projet PLANETE entre 15/8/2002 et 15/12/2002.

Le stage de M. AL FAWAL a porté sur l’évaluation des mécanismes hybrides de correction d’erreur ARQ/FEC pour des liens sans fil en présence d’un trafic formé par des connexions TCP de longue durée. L’objectif principal du stage était l’optimisation de ces mécanismes hybrides dans le but de maximiser l’utilisation du lien sans fil. L’étude a été effectuée par modélisation analytique et par simulation. Elle a permis une bonne compréhension de la capacité des mécanismes hybrides ARQ/FEC et de la manière avec laquelle leurs paramètres doivent être choisis.

M. AL FAWAL a réussi à mener l’étude à ses fins. Il a vite compris le problème et les travaux de recherche qui y sont liés. L’étude a nécessité l’implémentation d’un mécanisme hybride de correction d’erreur ARQ/FEC dans le simulateur de réseaux « ns-2 ». Cette implémentation a été réalisée avec succès par M. AL FAWAL, malgré toutes les difficultés qui accompagnent en général une telle implémentation (maîtrise des langages C++ et OTCL, connaissance de la hiérarchie de classes de « ns-2 »). Le mécanisme implémenté a fonctionné correctement et a permis à l’étude d’aboutir.

La deuxième partie du stage a consisté en une modélisation de l’utilisation du lien sans fil en fonction des paramètres du mécanisme ARQ/FEC, des paramètres du lien sans fil, et du nombre de connexions TCP. La modélisation a été effectuée à l’aide des techniques de la théorie des probabilités et des processus stochastiques. Elle a permis l’obtention d’une expression pour l’utilisation du lien sans fil. Cette expression a ensuite été résolue numériquement par « matlab », le programme souvent utilisé par les scientifiques dans leur calcul.

La troisième partie du stage a été la simulation et la validation du modèle analytique. Un scénario de simulation a été en premier lieu défini. Après, plusieurs compagnes de simulation ont été tournées pour différentes valeurs des paramètres du modèle. Pour chaque combinaison des paramètres du modèle, l’utilisation du lien sans fil a été calculée par simulation et par modélisation. La première conclusion était que le modèle analytique donnait des résultats très proches de la simulation, ce qui avait constitué une validation de l’analyse effectuée. Les résultats ont ensuite été analysés dans le but de tirer des conclusions sur la manière avec laquelle il faut choisir les paramètres du mécanisme de correction d’erreur ARQ/FEC. Les résultats étaient très intéressants, parfois contre-intuitifs. Je citerais un des ces résultats, celui de l’avantage de ARQ sur FEC ; la retransmission de paquets erronés au niveau liaison aide les connexions TCP de longue durée beaucoup plus que la redondance envoyée par FEC, et ceci est de plus en plus prononcé lorsque le délai de propagation et le taux d’erreur baissent.

Cette description montre la diversité des problèmes auxquels M. AL FAWAL a été confronté pendant son stage : protocoles réseaux (TCP, liens sans fil), implémentation et simulation, modélisation. M. AL FAWAL a réussi à résoudre ces problèmes avec patience et rigueur. M. AL FAWAL a aussi montré une capacité à apprendre, à interpréter les résultats, et à communiquer ses idées. Son travail s’est achevé par la publication d’un papier de 8 pages en anglais titré « Simulation-based study of link-level hybrid FEC/ARQ-SR for wireless links and long-lived TCP traffic » dans les proceedings du congrès international WiOpt’03 : Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Sophia Antipolis, France, Mars 2003. Le comité technique de WiOpt’03 a tenu à choisir un programme de haute qualité en acceptant seulement 33 papiers parmi les 102 soumis (un taux d’acceptation avoisinant les 30%). M. AL FAWAL a conclu son séjour à l’INRIA par une présentation des ses travaux aux membres du projet PLANETE, une présentation qui a été bien appréciée.

A tout ce qui précède, il faut ajouter le sens de responsabilité que M. AL FAWAL dispose et la capacité d’intégration et de travail en groupe qu’il a montrée.

Faite pour valoir à ce que de droit.

Chadi BARAKAT

http://www.inria.fr/planete/chadi

mailto:[email protected]

SOMMAIRE

INTRODUCTION.................................................................................2

Chapitre I : CADRE DU PROJET..............................................5I.1 Introduction :......................................................................................................5

I.2 Performance de TCP et ses Problèmes :...........................................................5

I.3 Solutions :............................................................................................................6

I.3.1 Solutions au Niveau Transport :......................................................................7

I.3.2 Solutions au Niveau Liaison :..........................................................................8

I.3.3 Solution au niveau des antennes :...................................................................8

I.4 Comparaison :...................................................................................................10

I.5 Conclusions :.....................................................................................................11

Chapitre II : FEC/ARQ-SR, Définition et Modélisation Analytique............................................................................14

II.1 Introduction :....................................................................................................14

II.2 Choix des Différents Mécanismes :.................................................................14

II.3 Modèle :.............................................................................................................15

II.3.1 Processus de perte des unités :..................................................................16

II.3.2 Modèle pour TCP :....................................................................................17

II.4 Analyse :............................................................................................................18

II.4.1 Calcul du taux de perte des paquets TCP:................................................18

II.4.2 Calcul de α :..............................................................................................18

II.4.3 Moyen de Round-Trip Time :.....................................................................19

II.5 Correction de notre modèle pour le délai introduit par ARQ:....................20

II.6 Cas d’un produit délai-bande passante élevé du lien sans fil :.....................21

II.7 Cas d’un produit délai-bande passante moyen du lien sans fil :..................21

II.8 Correction du modèle pour le délai introduit par le module de

reséquencement :..............................................................................................23

II.8.1 Proposition 1, Arrivée Poissoniènne :.......................................................24

II.8.2 Proposition 2, Arrivée déterministe :........................................................25

II.9 Conclusions :.....................................................................................................25

Chapitre III : Simulation, Validation de FEC/ARQ-SR.............28III.1 Introduction :....................................................................................................28

III.2 Simulateur :.......................................................................................................28

III.3 Implémentation :...............................................................................................29

III.4 Outils utilisés :...................................................................................................31

III.5 Simulations :......................................................................................................32

III.6 Première partie : utilisation du lien sans fil (C = 10) :..................................32

III.6.1 Scénarios des simulations :.......................................................................32

III.6.2 FEC seule :................................................................................................34

III.6.3 ARQ-SR seule :..........................................................................................35

III.6.4 L’hybride FEC/ARQ-SR :..........................................................................36

III.7 Deuxième partie : Throughput d’une connexion TCP seule :......................38

III.8 Conclusions :.....................................................................................................40

Chapitre IV : Vérification du modèle, Optimisation..............42IV.1 Introduction :....................................................................................................42

IV.2 Vérification :......................................................................................................42

IV.2.1 Vérification de la partie rigoureuse :........................................................43

IV.2.2 Vérification du modèle complet :...............................................................45

IV.3 Etudes des paramètres K et X :.......................................................................48

IV.4 Optimisation :....................................................................................................50

IV.5 Généralisation des résultats d’optimisation :.................................................54

IV.6 Conclusions :.....................................................................................................57

Chapitre V : ARQ-Protégée-Par-FEC et FEC/ARQ-Stop&Wait.59V.1 Introduction :....................................................................................................59

V.2 Choix des mécanismes du modèle :.................................................................59

V.3 Modèle :.............................................................................................................59

V.4 Simulateur :.......................................................................................................60

V.5 Scénarios des simulations et résultats :...........................................................61

V.6 Etude analytique :.............................................................................................63

V.7 Analyse :............................................................................................................64

V.7.1 Calcul du taux de pertes des paquets :......................................................64

V.7.2 Calcul de α :..............................................................................................64

V.8 Vérification du modèle et optimisation :........................................................65

V.8.1 Vérification :..............................................................................................65

V.8.2 OPTIMISATION :......................................................................................66

V.9 FEC/ARQ-Stop&Wait :...................................................................................68

V.10 Conclusions :.....................................................................................................69

Conclusions Générales.............................................................71

Annexe 1.......................................................................................75Annexe 2.......................................................................................77

Annexe 3.......................................................................................78Annexe 4.......................................................................................80

Annexe 5.......................................................................................84Bibliographie...............................................................................86

A. AL FAWAL, C. BARAKAT. Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SR.............................................................90

INTRODUCTION

INTRODUCTION

Les réseaux informatiques ont évolué très rapidement pendant les 20 dernières

années. En même temps, les demandes sur ces réseaux ont augmenté : les gens veulent un

accès rapide et de haute qualité à tout endroit. C'est pourquoi les utilisateurs sans fil

feront une part substantielle (62,1 %) du nombre total des utilisateurs d'Internet (1,2

milliards) prévu pour 2005 [1].

D'autre part, les demandes sur les services disponibles dans les réseaux sans fil

sont les mêmes que pour les réseaux câblés : Tout le monde veut web browsing, E-

mail check, chat, file transfer… Ainsi, la prochaine génération de l’Internet est

prévue de fournir un support pour ces diverses applications même dans les avions ou les

bateaux en utilisant un réseau sans fil basé sur une pile TCP/IP appropriée. Cependant,

les pertes sur les liens sans fil sont connues pour compromettre la performance de bout-

en-bout de TCP [2], [3].

Pour TCP, la perte d'un paquet est une indication que le réseau est congestionné

[4], [5]. Le paquet perdu est retransmis par la source TCP et la fenêtre est réduite afin

d'alléger la congestion du réseau. Cette stratégie dans la détection de la congestion a

comme conséquence une faible performance du protocole quand des paquets sont perdus

dans le réseau pour autres raisons que la congestion [6], [7], [8], [9]. Les erreurs de

transmission sur un lien bruyant, typiquement un lien sans fil, forment la source

principale des pertes de non-congestion. Un paquet TCP corrompu sur le lien bruyant est

jeté avant d'atteindre le récepteur, ce qu’il a comme conséquence une réduction inutile de

la fenêtre à la source TCP. Dans ce rapport, nous nous concentrerons sur les erreurs de

transmission ayant lieu sur les liens sans fil et nous les appellerons les pertes de non-

congestion des paquets TCP.

Beaucoup de solutions sont proposées pour améliorer la performance de TCP

lorsqu’il fonctionne sur des canaux présentants des pertes de non-congestion [6], [10],

[7], [9], [11]. Nous étudions dans ce rapport la performance de TCP au-dessus d'un lien

sans fil disposant d’un modèle de correction d'erreurs hybride qui combine au niveau de

la couche liaison FEC, ARQ-SR (ARQ Selective Repeat) et une livraison en-ordre des

paquets à IP.

2

Introduction

Toutefois, ce travail a été divisé principalement en 5 grandes parties :

Une phase bibliographique.

Implémentation du modèle dans le simulateur NS-2.

Simulation.

Modélisation, vérification et optimisation.

L’étude d’un autre modèle hybride en repassant par les mêmes étapes que

pour le premier mécanisme hybride.

Pour cela, ce rapport est organisé en 5 chapitres comme suit :

Chapitre 1 :

Ce chapitre montre brièvement les solutions qu’on peut trouver dans la littérature

et qui visent à optimiser la performance de TCP sur les liens sans fil. Le chapitre est

conclu par une petite comparaison entre les différents mécanismes de correction

proposés.

Chapitre 2 :

Ce chapitre commence par une description détaillée du modèle hybride tout en

définissant ses paramètres. Après, une modélisation complète de son comportement est

developpé pour aboutir enfin du compte à l’écriture de l’expression de l’utilisation du

lien sans fil en fonction des paramètres du lien sans fil et de l’hybride.

Chapitre 3 :

C’est dans ce chapitre que le simulateur et les simulations sont présentés. Il

contient les résultats des simulations et une analyse du fonctionnement du modèle.

Chapitre 4 :

Ce chapitre porte sur la vérification de la modélisation en comparant ses résultats

avec ceux des simulations. Il se termine par une optimisation du modèle.

Chapitre 5 :

Dans ce chapitre on a étudié 2 autres propositions : ARQ-SR-protégée-par-FEC et

FEC/ARQ-Stop&Wait. Les résultats obtenus sont comparés avec FEC/ARQ-SR.

3

IC

H

A

P

I

T

R

E

CADRE DU PROJET

Chapitre I : CADRE DU PROJET

I.1 Introduction : Les protocoles du transport fiables tels que TCP sont principalement conçus pour

fonctionner dans les réseaux traditionnels où les pertes de paquets sont dues

principalement à la congestion. Cependant, les réseaux contenant des liens bruyants tel

que les liens sans fil souffrent aussi des pertes de non-congestion causées par d’autres

raisons. TCP répond à toute perte en invoquant ses algorithmes de contrôle de congestion

ce qui résulte en une performance de bout-en-bout dégradée dans les systèmes sans fil.

Dans la littérature, plusieurs solutions sont proposées pour améliorer la

performance de TCP sur de tels liens. En particulier, en combinant l’ARQ à la FEC, on

espère maximiser le débit moyen de TCP.

I.2 Performance de TCP et ses Problèmes : TCP fournit une transmission fiable de données dans un environnement IP. TCP

correspond à la couche transport (couche 4) du modèle OSI. Il est largement utilisé dans

le monde Internet à cause de sa simplicité, la fiabilité qu’il assure et son contrôle de

congestion. Son trafic constitue à peu prés 90 % de la totalité du trafic Internet. Il rend

fiable le transport de données en maintenant des connexions de bout-en-bout entre

l’émetteur et le récepteur. Afin d’aboutir à un partage équitable de la bande passante, il

implémente des algorithmes de contrôle de congestion. En effet, TCP s’adapte au délai de

bout-en-bout et aux pertes de paquets qui indiquent que le réseau est congestionné.

L’émetteur TCP utilise les ACKs cumulatifs qu’il reçoit pour connaître les paquets bien

reçus par le récepteur. Ainsi la fiabilité est assurée par la retransmission des paquets

perdus. Pour cela TCP estime le temps moyen aller-retour (Round-Trip-Time) et son

écart type. L’émetteur détecte la perte d’un paquet par l’arrivée de plusieurs ACKs

dupliqués ou par l’absence de son ACK dans un intervalle de temps (RTO) égale à RTT +

4 fois son écart type [7]. TCP répond à une perte de paquet par une forte réduction de la

fenêtre de congestion, il déclenche des mécanismes de recouvrement des paquets perdus

(e.g. Fast Retransmit, Fast Recovery, etc.) et il recommence de nouveau son cycle de

5

Chapitre I : Cadre du Projet

transmission (en se mettant dans la phase Slow Start ou Congestion Avoidance). Par

suite, la charge dans les liens intermédiaires est réduite et de cette façon, le contrôle de

congestion est achevé.

TCP a montré une efficacité dans les réseaux filaires. Par contre, il s’oppose à la

convergence des réseaux vers la mobilité. En effet, les liens sans fil sont caractérisés par

des taux de pertes très élevés dûs à la nature de ces liens et aux phénomènes de

propagation (trajets multiples, interférences entre fréquences voisines, effet Doppler,

etc.). Pour TCP, la perte est un synonyme de la congestion c.à.d. lors de la détection

d’une perte, il annonce que le réseau est congestionné et il essaie de diminuer la charge

dans le réseau. Cette stratégie résulte en une pauvre performance de TCP sur les liens

sans fil où les paquets sont perdus par autres raisons que la congestion, ce qui provoque

la réduction de la fenêtre de congestion tandis que le réseau n’est pas congestionné.

Alors, sur de tels liens bruyants, la fenêtre de TCP est toujours réduite ce qui tue le débit

de TCP malgré que le canal est vide.

Pour recouvrir ces points de faiblesse, plusieurs solutions sont proposées. Elles

servent à aider TCP à améliorer sa performance sur des liens caractérisés par un taux de

perte élevé comme le cas des liens sans fil.

I.3 Solutions : La popularité croissante des réseaux sans fil indique que les liens sans fil joueront

un rôle important dans le réseau futur [7]. Cependant, TCP, qui a été bien réglé pour le

réseau filaire, sa performance se dégradent en présence de pertes de-non-congestion, dites

pertes de non-congestion. Récemment, plusieurs méthodes ont été proposées pour alléger

les effets de pertes de non-congestion sur la performance de TCP. Ces solutions peuvent

être classées en trois catégories selon la couche à laquelle sont attachées :

1. Solutions au niveau transport.

2. Solutions au niveau liaison.

3. Solutions au niveau antenne.

Toutes ces solutions servent à aider TCP. Ici une question se pose : Pourquoi on a

toujours recours à garder TCP en essayant de l’améliorer et on ne le remplace pas par un

autre protocole plus adapté aux réseaux sans fil que les réseaux filaires? En fait,

l’efficacité de TCP représentée par sa simplicité, sa fiabilité et son contrôle de

congestion, a permis son déploiement dans le monde, il est maintenant installé sur des

6


centaines de millions de machines et ce n’est pas évident de le substituer tout en seul

coup.

I.3.1 Solutions au Niveau Transport : Ces mécanismes sont implémentés au niveau transport. L’idée est de modifier

plus ou moins TCP pour s’adapter aux liens bruyants. Parmi ce qui est proposé, on va

citer 4 solutions.

La première solution consiste à utiliser les acquittements sélectifs (Selective

ACK ; SACK) pour permettre à l'émetteur de recouvrir plusieurs paquets perdus dans une

même fenêtre sans l’attente de l’expiration du temporisateur de TCP [7]. Cependant, TCP

reste considérer toutes les pertes dans une fenêtre comme un indicateur de congestion et

déclenche des mécanismes de contrôle de congestion comme la réduction de sa fenêtre.

La deuxième solution sert à distinguer entre les pertes causées par la congestion et

celles causées par d’autres raisons. Ceci se fait en ajoutant l’option ELN (Explicit Loss

Notification) à l’acquittement de TCP [7]. Si un paquet est jeté à cause du lien sans fil, le

prochain acquittement cumulatif correspondant à ce paquet est marqué pour indiquer à

l’émetteur que le réseau est non congestionné. Ainsi l’émetteur retransmet le paquet

perdu sans réduire sa fenêtre.

La troisième solution est l’utilisation de TCP Vegas, une version de TCP plus

adaptée aux liens sans fil. L’idée derrière cette version est de détecter la congestion par

l’augmentation de RTT et non pas par l’apparition d’une perte. Ainsi, la fenêtre de TCP

est une fonction de RTT. En effet, TCP Vegas calcule un débit moyen cible en fonction

de RTT et il essaie de maintenir son throughput (débit moyen) égal à ce débit cible qui ne

change tant que RTT est le même, malgré l’apparition de pertes [12]. Les premières

simulations de cette version ont montré qu’elle fonctionne mieux que le TCP Tahoe ou la

version Reno. Après, des expériences plus sérieuses ont donné que ce n’est pas toujours

le cas.

7

TCP STP

TCP

Figure I.1 : Division de la connexion TCP en deux connexions.


Dans la quatrième solution, on a décidé de couper la connexion TCP de bout-en-

bout en deux connexions (e.g. I-TCP) [7], [12]. La première est une connexion TCP entre

l’émetteur et l’entrée du lien sans fil. La deuxième est entre l’entrée du lien sans fil

(station de base) et la destination, elle est maintenue par un autre protocole qui est plus

adaptés au lien bruyant comme STP [13]. Cette méthode a présenté une amélioration de

la performance de TCP mais elle viole la sémantique de bout-en-bout de TCP. Un paquet

est acquitté avant qu’il arrive à sa destination.

I.3.2 Solutions au Niveau Liaison : Au niveau liaison, on utilise souvent l’ARQ (Automatic Reapeat Request) et la

FEC (Forward Error Correction) pour rendre fiable la transmission de données.

Généralement, on applique ces deux mécanismes seulement sur la partie bruyante du

réseau (e.g. lien sans fil).

L’ARQ consiste à retransmettre localement les paquets perdus, c.à.d. entre les

deux extrémités du lien sans fil, d’une manière transparente par rapport à TCP. ARQ

réussit à rendre fiable le transport, par contre, il augmente le RTT. On trouve dans [8],

[14] que le débit moyen de TCP est inversement proportionnel à RTT. En outre,

l’instabilité de RTT et le déséquencement des paquets IP causés par ARQ créent une

interférence entre TCP et les retransmissions locales. Le déséquencement génère des

ACKs dupliqués qui incitent l’émetteur à retransmettre le paquet au moment où il est en

train d’être retransmis localement par ARQ. A cause de l’instabilité de RTT, le

temporisateur de TCP peut expirer en provoquant une retransmission inutile du paquet.

La FEC consiste à envoyer, en plus de l’information originale, des informations

supplémentaires afin qu’un paquet, corrompu sur le lien sans fil, peut être reconstruit à la

sortie du lien sans besoin de le retransmettre. En utilisant la FEC, on améliore fortement

la performance de TCP, mais ceci consomme une partie de la bande passante pour faire

passer les informations redondantes. Alors, il faut trouver un compromis entre la bande

passante consommée par la FEC et le gain en terme de l’utilisation du canal.

I.3.3 Solution au niveau des antennes : Ce paragraphe concerne les liens sans fil des réseaux de communication. Dans des

telles liaisons, l’antenne joue deux rôles réciproques : la transmission et la réception [15],

[16], [17]. Ainsi, dans une chaîne de communication, elle est toujours le premier élément

dans une chaîne de réception et le dernier élément dans une chaîne de transmission. Elle

8


est en contact direct avec le canal de propagation. Afin de l’adapter au canal, il faut

connaître les caractéristiques du lien sans fil et les différents phénomènes accompagnant

la propagation du signal électromagnétique.

Brièvement, les deux extrémités d’un lien sans fil sont dans la plupart des cas en

non-visibilité. A la station de base, le signal est émis dans une certaine ouverture. Suivant

leur direction d’émission, les ondes empruntent des chemins différents. En fonction du

type d’obstacles (bâtiment, relief, végétation) rencontrés sur leur parcours, elles subissent

des phénomènes de réflexion, de réfraction, de diffraction et de diffusion. Il en résulte

une multitude de trajets élémentaires au niveau du récepteur (Figure I.2), caractérisés

chacun par un retard, une atténuation et un déphasage propre [18], [19], [20].

Ces caractéristiques spatio-temporelles du canal sans fil, les retards et les angles

d'arrivée des différents trajets multiples, ajoutons à ceci l’interférence entre les

9

Figure I.2 : Propagation par trajets multiples.

Figure I.3 : Réseaux d’antennes.


fréquences voisines et l’effet Doppler dans le cas de la mobilité, constituent les causes

principales de son taux d’erreur très élevé.

Une solution très prometteuse est l’utilisation des antennes adaptatives, dites

antennes intelligentes. Cette solution a constitué le sujet de plusieurs travails tel que le

projet RNRT SIMPAA [17],[21].

L’idée est de remplacer l’antenne par un réseau d’antennes travaillant comme une

seule entité. En jouant sur le déphasage entre les éléments de ce réseau, on fait varier la

direction du diagramme de rayonnement, sa directivité et son gain (Figure I.4). Ainsi on

peut éliminer les signaux parasites (signaux interférents, trajets multiples…) en annulant

le diagramme de rayonnement dans leurs sens et on le fait diriger dans le sens du signal

désiré.

I.4 Comparaison : Jusqu’à maintenant, on a exposé trois types de méthodes proposées pour

améliorer la transmission sur des liens bruyants comme les liens sans fil. Parmi eux,

celles du niveau liaison s’avèrent les plus adaptées à notre application : trafic TCP.

En effet, les trois premières solutions proposées au niveau transport, SACK, ELN

et TCP Vegas, nécessitent la modification de TCP chez l’émetteur et le récepteur. Alors,

si on veut remplacer une liaison filaire par une autre sans fil, par ex. un lien satellitaire, il

faut changer le TCP dans tous les terminaux ayant un trafic passant par cette liaison.

Dans la quatrième solution du même niveau, on n’a plus une connexion TCP bout-en-

bout entre l’émetteur et le récepteur, un paquet est acquitté avant d’arriver à sa

destination. Ainsi, on a perdu le sens de transmission orientée connexion de TCP.

Au niveau antenne, on est transparent par rapport à TCP et on n’exige aucune

modification de TCP chez l’émetteur ni chez le récepteur. Cependant, cette solution est

10

Figure I.4 : Eliminations des interférences et des trajets multiples.


assez complexe, elle nécessite un software et hardware très délicats derrière les antennes.

En outre, pour l’appliquer à un canal donné, il faut relever d’abords ses caractéristiques

spatio-temporelles pour adapter ces antennes intelligentes. Alors il n’y a pas une solution

standard pour tous les canaux. Souvent, cette solution est utilisée non pas seulement pour

rendre fiable le réseau mobile, mais aussi pour le densifier en appliquant le SDMA

(Spatial Division Multiple Access) [17], [18].

Les solutions proposées au niveau liaison, FEC et ARQ, groupent l’efficacité, la

simplicité relative et la transparence par rapport à TCP. Les mêmes mécanismes sont

appliqués à tous les canaux sans fil indépendamment de leurs caractéristiques. Mais

comme nous avons vu, elles présentent des inconvénients comme l’instabilité et

l’augmentation de RTT pour ARQ, et la consommation d’une partie de la bande passante

pour la FEC.

Afin de bénéficier des avantages de ces deux mécanismes et d’éliminer leurs

problèmes, on a proposé un modèle hybride qui les combine au niveau liaison. L’idée

derrière ce modèle est de minimiser les inconvénients de l’un par les avantages de l’autre

dans le but d’obtenir un gain plus grand que celui qu’on peut obtenir en les utilisant

séparément. Ce modèle a constitué le sujet de ce travail ; il a été modélisé et simulé. Le

modèle, les simulations, et les résultats obtenus sont présentés dans les chapitres qui

suivent.

I.5 Conclusions : La simplicité, la fiabilité et le contrôle de congestion que présente TCP, l’ont

rendu le protocole le plus utilisé au niveau transport dans le monde Internet. Pour TCP, la

perte est un indicateur de congestion. Lors d’une perte, la fenêtre de congestion de TCP

est réduite, une chose mauvaise pour le débit TCP sur des liens bruyants, où les pertes

sont causées par d’autres raisons que la congestion, comme le cas des liens sans fil. Ceci

freine la convergence vers les réseaux sans fil et l’intégration des services multimédia

dans les réseaux mobiles.

Plusieurs solutions sont proposées, au niveau transport, au niveau liaison, au

niveau antennes, etc.. Parmi ces solutions, l’utilisation de FEC et de ARQ au niveau

liaison s’avèrent la plus adaptée à notre application. Un modèle très promettant consiste à

combiner la FEC et l’ARQ afin d’améliorer davantage la performance de TCP sur les

liens sans fil.

11


Le chapitre suivant porte sur ce modèle, explique le choix des différents

mécanismes et présente son aspect analytique c.à.d. les équations analytiques et les

expressions mathématiques qui le modélise.

12

II

FEC/ARQ-SR, Définition et Modélisation

Analytique

C

H

A

P

I

T

R

E

Chapitre II : FEC/ARQ-SR, Définition et Modélisation

Analytique

II.1 Introduction : Lorsque la performance de TCP s’est dégradée sur les liens sans fil, les efforts se

sont concentrés à recouvrir ses points de faiblesse. Plusieurs solutions ont été proposées,

la plus prometteuse est l’utilisation d’un modèle hybride au niveau liaison combinant la

FEC (Forward Error Correction), l’ARQ-SR (Automatic Repeat Request with Selective

Repeat) tout en assurant une livraison en ordre des paquets à IP. En appliquant ce

modèle, on espère minimiser les inconvénients des deux mécanismes, FEC et ARQ-SR

lorsqu’ils sont utilisés séparément, afin de maximiser l’utilisation de la bande passante du

lien sans fil.

II.2 Choix des Différents Mécanismes : D’abord, dans le modèle sujet de ce projet, le choix s’est porté sur la FEC et sur

l’ARQ-SR pour être combinés au niveau liaison. Comme il est indiqué dans [8], la FEC

accroît spectaculairement le débit moyen du TCP sur les liens présentant des taux de

pertes élevés. Son problème est la consommation d’une partie de la bande passante pour

ses informations redondantes (voir Chapitre I).

Concernant ARQ-SR, c’est un mécanisme efficace qui évite les retransmissions

inutiles qui apparaissent en utilisant ARQ Go_Back_N. En outre, contrairement à ARQ

Stop-And-Wait, ARQ-SR permet une bonne utilisation de la bande passante disponible,

puisque plusieurs paquets peuvent être transmis sur le lien sans fil avant de recevoir

aucun acquittement. Son problème majeur est le déséquencement de paquets qu’il

introduit. Les paquets déséquencés sont très nuisibles pour TCP parce qu’ils résultent en

des acquittements dupliqués. Par conséquent, la fenêtre de congestion de la source TCP

subit une réduction inutile lors de la réception de 3 ACKs dupliqués successifs au

moment où le paquet sujet de ces ACKs n’est pas perdu mais il est au court de

retransmission locale. Pour résoudre ce problème, on a ajouté au modèle un mécanisme

14

Chapitre II : FEC/ARQ-SR, Définition et Modélisation Analytique

qui assure la livraison en ordre des paquets à IP, d’où la nécessité d’un buffer (tampon) à

la sortie du lien sans fil pour reséquencer les paquets avant de les délivrer à IP.

Etant donné que la FEC réduit le taux de pertes, on la combine avec ARQ-SR

pour réduire le nombre de retransmissions locales des paquets, ainsi on diminue le RTT

et le délai du réséquencement. D’autre part, la présence de ARQ-SR minimise la quantité

de FEC à ajouter en la comparant avec celle utilisée lorsqu’on adopte la FEC seule pour

la correction d’erreurs, ce qui permet une meilleure utilisation de la bande passante du

lien sans fil.

II.3 Modèle : Considérons un lien sans fil où les données sont transmises en trames. Chaque

trame est divisée en K unités de transmission de niveau liaison (Link-Level LL). Une

unité de transmission LL peut être un bit, un octet, ou n'importe quelle autre unité de

données. La FEC est appliquée à chaque trame LL : Aux K unités d'une trame, on ajoute

N - K unités redondantes qu’on obtient en utilisant un code Reed-Solomon [22]. N est

dite la longueur du code, K sa dimension et K/N son taux. Une trame est décodée si à la

sortie du lien sans fil on reçoit correctement au moins K unités de la trame.

Un paquet TCP qui arrive à l'entrée du lien sans fil est divisé en X trames LL

(Figure II.1). On suppose que tous les paquets TCP sont de taille constante S. on

exprimera tous les taux en utilisant les unités de transmission LL. Ainsi, un paquet TCP a

une taille S = X*K unités. On rappelle qu'une trame LL a une taille constante de K unités.

Pour le délivrer à sa destination, les X trames d'un paquet TCP doivent être

correctement reçues. Si FEC ne réussit pas à décoder une trame, on recourt à ARQ-SR

pour la retransmission de cette trame. Dans ce rapport, nous considérons ARQ Selective-

Repeat. La retransmission sera faite un nombre maximum de fois. Ce nombre dénote la

persistance de ARQ-SR (ARQ persistency). On dénote la persistance par δ, δ = 0, 1, 2...

15

Figure II.1 : Le Modèle hybride FEC / ARQ-SR.


Nous dériverons l'expression du throughput d’une connexion TCP en utilisant les

paramètres du modèle X, K, N, δ. Le but est de trouver leurs valeurs qui optimisent la

performance de TCP sur les liens sans fil, ce qui constitue l’objectif des Chapitres 3 et 4.

Nous considérons C connexions TCP partageant simultanément le lien sans fil. L’étude

porte sur des connexions TCP de longue durée.

On dénote par B la bande passante du lien sans fil (en termes d'unités/s). Soit D

son délai de propagation unidirectionnelle. Soit T le délai bi-directionnel de bout-en-bout

des connexions TCP, à l'exclusion du délai de propagation sur le lien sans fil. Pour la

simplicité, nous supposons que toutes les connexions ont la même valeur de T (T peut

être une variable aléatoire plutôt qu'une constante). Pour le moment, nous supposons que

le lien sans fil délivre les paquets (après le rassemblement de toutes les trames) dès qu'ils

seront correctement reçus. Une fois qu'un paquet TCP est correctement décodé à la sortie

du lien sans fil, il est expédié à sa destination, même s'il y a un ou plusieurs paquets

précédents de la même connexion étant partiellement décodés. Clairement, cette livraison

en désordre peut résulter en des ACKs dupliqués et des faux signaux de congestion. Nous

négligeons cet effet pour le moment. Plus tard, nous présenterons dans notre modèle le

fait que le lien sans fil délivre les paquets dans le même ordre avec lequel ils ont été

reçus.

Nous faisons également quelques hypothèses au sujet de ARQ Selective-Repeat.

Nous supposons que chaque trame LL est acquittée, avec un ACK positif ou un NACK.

Quand un NACK est reçu à l'entrée du lien sans fil, la trame correspondante est

directement retransmise étant donné qu’elle est prioritaire sur toute autre trame qui n'a

pas été encore transmise. Une retransmission peut trouver une trame qui est actuellement

en cours de transmission. Ceci aura comme conséquence un certain délai additionnel.

Une trame à transmettre pour la première fois peut également être retardée par un ou

plusieurs retransmissions. Pour le moment, on néglige tous ces retards présentés par

ARQ-SR. Après, nous les introduirons dans notre modèle (Paragraphe II.5).

II.3.1 Processus de pertes des unités : Nous modélisons les erreurs sur le lien sans fil par un processus de Bernoulli où

les pertes des unités LL se produisent indépendamment avec la probabilité p. Donc c’est

un processus uniforme sans mémoire. On l’applique sur les trames de données seulement.

Les ACKs de ARQ-SR et de TCP sont supposés traverser le lien sans fil sans erreurs

étant données leurs petites tailles. Si les unités correspondent aux bits, p dénotera le BER

16


(Bit Error Ratio) du canal. Notons que le BER peut être lié aux différents paramètres du

lien sans fil comme la technique de modulation, le taux de transmission, la bande de

fréquence, le bruit, la vitesse du terminal mobile, l'atténuation, etc...

D’habitude, les erreurs sur les liens sans fil sont modélisées par une chaîne de

Markov de deux d'états ou plus puisqu’elles apparaissent en « bursts » (rafales) [8],[11],

[22], [23]. Notre choix s’est porté sur le processus de Bernoulli pour la simplicité de

l'analyse qu'il permet. Ce processus est connu pour bien fonctionner sur des canaux

présentant un « fast fading » et quand l’entrelacement est utilisé. Nous sommes intéressés

dans cette étude par l'impact du taux d'erreurs moyen. L'impact du « burstiness » des

erreurs sera le sujet d'une future recherche.

II.3.2 Modèle pour TCP : Nous donnons maintenant notre expression générale pour l'utilisation du lien sans

fil. Cette expression est une fonction de quelques quantités qui seront calculées dans les

prochains paragraphes. Soit R le débit d'une connexion TCP de longue durée, dit

« throughput ». Différentes expressions existent dans la littérature pour exprimer ce débit

[14], [24], [25], [26]. Nous utiliserons celle dans [24]. Selon [24], R (en unités-LL/s) est

égal à :

où A est la valeur moyenne du RTT (Round-Trip Time), et P la probabilité de perte d’un

paquet TCP. En activant les ACKs retardés (delayed ACKs), b est un coefficient égal à 2.

Le terme (1 - P) à la fin de l’équation considère les pertes de paquets sur le lien sans fil.

L'utilisation du lien sans fil est égale à

Par utilisation, on désigne le débit du lien sans fil. L'objectif est de maximiser

cette utilisation. Le facteur α dans l'expression de l'utilisation est pour tenir en compte la

quantité de bande passante gaspillée par FEC et par les retransmissions de ARQ-SR.

II.4 Analyse : Pour trouver l'utilisation du lien sans fil pour un certain taux de pertes et certains

paramètres du modèle FEC/ARQ, on doit calculer les trois quantités A, P et α. Le premier

17

(II.1)

(II.2)


est le délai aller-retour moyen d'un paquet TCP. Le second est le taux de perte des

paquets. Le troisième est la partie de la bande passante du lien qui est utilisée pour la

transmission de l'information utile. Une fois ces quantités sont obtenues, on les met dans

l'expression de l'utilisation (Eq. II.2).

II.4.1 Calcul du taux de perte des paquets TCP: Un paquet TCP est perdu si une de ses trames LL est perdue. Soit PF la probabilité

de perte d’une trame. Alors,

On calcule maintenant la probabilité qu'une trame est perdue. Ceci exige, en plus

de la perte de la transmission originale, l'échec des δ retransmissions. Ceci donne en total

δ+1 occasions pour transmettre correctement une trame. Un essai échoue quand plus que

N - K unités de la trame sont perdues. Ceci se produit avec la probabilité PT tel que

Les δ+1 essais échouent (ou la trame est considérée sans aucun doute perdue)

avec la probabilité

En insérant (Eq. II.4) et (Eq. II.5) dans (Eq. II.3), on peut obtenir la probabilité P

avec laquelle un paquet TCP est perdu.

II.4.2 Calcul de α : Ce coefficient tient en compte la partie de la bande passante du lien sans fil

gaspillée sur la FEC et sur les retransmissions par ARQ-SR. Considérons une trame LL

qui quitte le lien sans fil. Cette trame peut correspondre à une transmission originale ou à

une retransmission. Si la trame est corrompue, ce qui se produit avec la probabilité PT, la

quantité de données qu’on perd est égale à N unités. Une trame correctement reçue peut

également être rejetée. Ceci se produit quand le paquet auquel elle appartient ne peut pas

être rassemblé. La probabilité de ce dernier événement est égale à , et le

nombre d'unités qu’on perd dans ce cas est de même égal à N. Quand une trame est

correctement reçue et le paquet auquel elle appartient est correctement rassemblé, la

quantité de données qu’on perd est seulement égale à N - K unités. Par conséquent, α sera

égale à

18

(II.3)

(II.5)

(II.4)


II.4.3 Round-Trip Time Moyen: Nous supposons que les trames sont rapidement acquittées à la sortie du lien sans

fil, et nous ignorons le temps de transmission des ACKs des trames. Ainsi, le temps entre

le début de la transmission d'une trame et la réception de son ACK-ARQ est

Soit δi, i = 1,…,X, δi = 0,1,…,δ, le nombre de fois qu’on a retransmis la trame i

d’un paquet TCP. Alors, le RTT d’un paquet TCP peut être écrit comme suit :

Pour obtenir cette expression, nous avons fait la supposition que les ACKs TCP

sont de taille très petite, de sorte que leur temps de transmission et leur probabilité de

perte soient égaux à 0. Nous négligeons également la durée de traitement des trames aux

deux extrémités du lien sans fil. Le paquet TCP dont nous calculons le RTT doit être bien

reçu, autrement il n'est pas utilisé pour mesurer le RTT. Ceci signifie que l'espérance du

RTT doit être calculée sous la condition que toutes les trames du paquet ont été bien

décodées à la sortie du lien sans fil. La probabilité que toutes les trames d'un paquet

soient bien décodées est égale à .

RTT est une variable aléatoire. L'aspect aléatoire vient des variables aléatoires δi,

qui sont iid (independent and identically distributed). On a que, pour k = 0,1,…,δ,

.

(Eq. II.9) est une probabilité conditionnelle, la condition étant que le paquet

correspondant est correctement reçu. Notons que .

Notre but est de calculer A, l’espérance du RTT. Cette espérance doit être après

insérée dans l'expression du débit (Eq. II.1).

Soit . On a . L’espérance de Z

peut être écrite comme suit :

19

(II.6)

(II.7)

(II.9)

(II.8)


On intègre seulement jusqu’à parce que c’est la valeur maximum que Z

peut atteindre. On sait que

,

avec

.

En utilisant (Eq. II.9), on a pour ,

ce qui donne,

Pour le moment, nous pensons à calculer numériquement cette expression de la

valeur moyenne de RTT.

II.5 Correction de notre modèle pour le délai introduit par ARQ: Les X trames d'un même paquet TCP ne sont pas nécessairement transmises back-

to-back, puisqu’elles peuvent être intercalées par des trames retransmises. Notons qu’on

travaille avec une technique ARQ prioritaire, où les retransmissions n'attendent pas dans

la file d'attente à l'entrée du lien sans fil derrière les autres trames, mais elles sont

directement mises à la tête de la file d'attente au niveau de la couche liaison, pour être

transmises une fois que le lien devient vide. A cause de ce retard causé par les

retransmissions, une trame voit une augmentation de son temps de transmission par une

certaine quantité aléatoire, qui dépend du nombre de NACKs reçus. En l'absence de

NACKs, la période de transmission d'une trame est simplement égale à N/B.

Soit σi le temps de transmission de la trame i d'un paquet TCP. σ i est égal à N/B

plus un certain délai variable dû aux NACKs reçus. Supposons que ni NACKs ont été

reçus, alors σi = N/B (1+ ni). L'expression du RTT donné par (Eq. II.8), sera

.

20

(II.14)

(II.13)

(II.10)

(II.11)

(II.12)

(II.15)


Pour calculer la moyenne de RTT, on peut utiliser la même technique que celle

dans le Paragraphe II.4.3.

II.6 Cas d’un produit délai-bande passante élevé du lien sans fil :

Dans ce cas particulier, on peut négliger le temps de transmission des trames, σi,

devant le temps de propagation D. Le calcul ci-dessus du RTT moyen peut alors être

simplifié. On peut écrire,

.

De même, on a dans ce cas : . Ainsi,

Du paragraphe précédent, on a , pour .

II.7 Cas d’un produit délai-bande passante moyen du lien sans fil :

Le calcul du temps aller-retour moyen dans le cas général est difficile,

particulièrement quand on introduit le délai dû aux NACKs. Paragraphe II.6 montre une

simplification du modèle pour le cas d’un lien sans fil ayant un grand produit délai-bande

passante. Dans ce paragraphe, nous considérons un autre cas qui est plus important que le

précédent puisque le temps de transmission des trames n'est plus négligeable.

La supposition qu’on fait dans cette section est que toutes les trames d'un paquet

TCP sont transmises avant que nous recevions aucun NACK pour ce même paquet. En

d'autres termes, le produit délai-bande passante est supposé plus grand que la taille d’un

paquet. Ce produit n'a pas besoin d'être infini comme dans le cas précédent. Le gain de

cette hypothèse est que nous pouvons écrire différemment l'expression de RTT, ce qui

permet une solution pour A = E[RTT].

Soit M le nombre maximal de fois qu’on a retransmis les trames d’un paquet

TCP, alors . On définit Y comme étant le plus grand indice des

trames qui ont exigé le nombre maximum des retransmissions. Notons que plus qu'une

trame dans un paquet peut être retransmise M fois. Formellement, Y est défini comme

21

(II.16)

(II.17)


suit : . Il est très facile de voir que l'expression de RTT donné dans (Eq.

II.15) peut être écrite comme

.

On peut assumer sans risque que les variables σi sont indépendantes l'une de

l'autre. Ceci ne se tient pas pour un lien sans fil de petit produit délai-bande passante,

puisqu'une trame d'un paquet peut être retardée par des NACKs appartenant aux trames

de ce même paquet. Etant donné cette indépendance de σi, nous écrivons,

.

L'espérance de M peut être déduite de dans Paragraphe II.6. D’où

.

L’espérance de Y est calculée dans l’Annexe 1. On trouve

.

Pour obtenir , on a besoin de (Eq. II.13). Aussi, on a besoin de l’expression

de , k = 0,1,..,δ. En effet,

.

est égale à 0 pour k = 0.

On doit encore calculer l'espérance de σi, afin de résoudre le RTT moyen, et puis

le throuhgput de TCP. La transmission d'une trame LL pour la première fois sur le lien

sans fil, peut être retardée par un ou plusieurs retransmissions. Soit π la probabilité que le

lien sans fil est occupé. π est égal à . La probabilité pour avoir un ACK

LL ou un NACK LL arrivant juste avant la transmission d'une trame est donc égale à π.

La probabilité qu'un NACK, causant une retransmission, arrive est égale à

. Nous multiplions par PT pour tenir en compte le fait que la trame

est perdue. Le terme est utilisé pour éviter le cas où c’était sa dernière

retransmission (avec ARQ-SR, une trame est supposée être retransmise δ fois au

maximum en plus de la transmission originale). Supposons qu'un NACK est reçu. La

transmission de la trame est alors retardée et la trame perdue est retransmise. Pendant

22

(II.18)

(II.19)

(II.20)

(II.21)

(II.22)


cette retransmission, un deuxième NACK peut arriver, et ainsi de suite. Nous supposons

que ceci se produit avec la même probabilité . Chaque retransmission retarde la

transmission de notre trame de N/B. Le nombre de NACKs reçu est géométriquement

distribué et sa moyenne est égale à . Le délai moyen dû au NACK est alors

égal à . À ce délai moyen, on doit ajouter le temps de transmission de

la trame, qui donne,

.

La difficulté avec cette expression est qu'elle dépend de R via π, le throughput de

TCP que nous visons à calculer. Nous avons alors un système du type R = f(R, …). f est

une fonction de R et des paramètres du modèle comme p, δ, X, etc... Etant donné la

complexité de la fonction f, on ne peut pas résoudre ce système pour une telle expression

de R. La solution peut être obtenue par l'itération du type , où Rn est la

valeur du throughput à la nième itération. Une autre solution possible est de trouver une

approximation pour π, afin de se débarrasser de R dans l'expression de , qui évite

l'itération. Nous examinerons l'exactitude de notre modèle pour quelques valeurs par

défaut de π : 1, 0.5,...

II.8 Correction du modèle pour le délai introduit par le module de reséquencement :

Le mécanisme ARQ-SR est connu par son déséquencement des paquets. Ces

paquets doivent être reséquencés avant de quitter le lien sans fil, autrement ils arrivent

aux récepteurs de TCP en désordre tout en causant la génération d’ACKs dupliqués. Si

plus de deux ACKs dupliqués sont produits (et par suite traversent successivement le

réseau vers la source), la source TCP considérera alors qu'il y a eu une perte de paquet, et

réduira sa fenêtre de congestion, ce qui peut être inutile si le paquet perdu est

actuellement en cours de retransmission sur le lien sans fil, et si la retransmission va

réussit.

Pour éviter ce problème des ACKs dupliqués, les liens sans fil sont censés fournir

les paquets en ordre à la couche IP. Cette livraison en ordre cause cependant une

augmentation du RTT. Un paquet de TCP peut être obligé d’attendre dans un buffer à la

sortie du lien sans fil jusqu'à ce que les paquets précédents soient bien reçus, ou jusqu’à

23

(II.23)


ce que ARQ décide que ces paquets sont certainement perdus et qu’il ne peut pas les

recouvrir. Une certaine quantité est alors à ajouter à l'expression du délai aller-retour dans

(Eq. II.15), pour tenir en compte cette livraison en ordre des paquets. Notons que les

paquets sont reséquencés à la sortie du lien sans fil en se basant sur le flux global du lien

sans fil et non pas sur les différents flux des connexions TCP, c.à.d. le lien est considéré

comme une seule queue FIFO.

Soit Ai = RTTi le délai aller-retour moyen d'un paquet TCP, quand l'impact de la

livraison en ordre est considéré. Nous recherchons cette moyenne, qui doit être insérée

dans (Eq. II.1). A = E[RTT] est le délai aller-retour moyen où la livraison en ordre n'est

pas considérée. L’expression de A est déjà calculé. Soit sn le temps nécessaire pour que le

nième paquet TCP traverse le lien sans fil, par conséquent . Soit λ le taux

d’arrivées des paquets TCP (de toutes les connexions) à l'entrée du lien sans fil.

Définissons . Nous avons alors un problème de reséquencement classique, qui

est bien connue dans la théorie des fils d’attente [27]. Différents travails ont étudié ce

problème afin de calculer le temps moyen de reséquencement. Et c’est exactement ce que

nous recherchons. Dans notre cas, le temps moyen de reséquencement est Ai – A.

Résoudre un tel problème de reséquencement est dur. Une expression

relativement simple pour le temps moyen de reséquencement a été obtenue dans un cas

très précis [27], que nous récapitulons dans la proposition suivante.

II.8.1 Proposition 1, Arrivée Poissoniènne : Supposons que l’arrivée des paquets TCP au lien sans fil suit un processus

Poissonien de taux λ. Supposons encore que les variables sn sont exponentiellement

distribuées. Quand le lien sans fil est légèrement chargé et la livraison en ordre est

activée, le temps aller-retour moyen est approximativement égal à

,

avec , et A est calculé dans les sections précédentes comme étant

le délai aller-retour moyen où les paquets sont délivré en désordre.

Nous avons le problème d'identifier λ. Le taux d’arrivées des paquets est une

fonction du throughput des connexions TCP, que nous voulons calculer. Nous nous

trouvons dans un problème de type R = f(R,…), ce qui peut être résolu par itération. Nous

pouvons éviter l'itération en faisant une certaine approximation pour λ, par exemple en

24

(II.24)


considérant que le lien sans fil est entièrement utilisé, et en prenant .

Nous multiplions λ par (1- P) pour tenir en compte les paquets qui sont perdus dans le

lien sans fil et qui ne peuvent pas être récupérés. Une autre approximation possible est de

mettre λ à la valeur obtenue à partir des mesures.

II.8.2 Proposition 2, Arrivées déterministes : On peut suggérer de prendre le processus d'arrivée de paquets comme

déterministe au lieu de Poisson, c.à.d. les arrivées sont régulièrement espacées. Par suite,

on trouve une expression du délai moyen de reséquencement. On assume que les

variables sn sont toujours exponentiellement distribuées. À notre connaissance, aucune

expression explicite n’existe pour un tel problème. Un calcul simple (voir Annexe 2 pour

plus de détails) prouve que le délai aller-retour moyen peut être écrit comme suit :

,

avec . De même λ peut être rapproché par , ce

qui correspond à la pleine utilisation du lien sans fil. Cette expression peut être résolue

numériquement.

II.9 Conclusions : Notre modèle consiste à combiner FEC avec ARQ-SR. Le but est toujours

d’améliorer la performance de TCP sur des liens bruyant, comme le lien sans fil. Etant

donné que ARQ-SR cause un déséquencement des paquets, un module est inséré à la

sortie du lien sans fil, son rôle est d’assurer une livraison en ordre des paquets à IP.

L’idée derrière cette combinaison est de grouper les avantages des deux mécanismes et

de minimiser leurs inconvénients qui apparaissent lorsqu’ils sont appliqués séparément.

Dans ce chapitre, on a mis une modélisation de l’utilisation du lien sans fil en fonction

des paramètres de l’hybride FEC/ARQ-SR, des paramètres du lien sans fil, et du nombre

de connexions TCP. La modélisation a été effectuée à l’aide des techniques de la théorie

des probabilités et des processus stochastiques. Elle a permis l’obtention d’une

expression pour l’utilisation du lien sans fil. Une expression assez complexe mais qui

peut être résolue numériquement.

Le chapitre suivant porte sur la validation de ce modèle. On y trouve les résultats

des simulations qu’on a effectuées.

25

(II.25)

III

Simulation, Validation de FEC/ARQ-SR

C

H

A

P

I

T

R

E

Chapitre III : Simulation, Validation de FEC/ARQ-SR

III.1 Introduction : Dans le chapitre précédent on a défini un modèle hybride dans le but d’améliorer

la performance du TCP sur des liens bruyants, en particulier les liens sans fil. On a

montré sa place dans la pile TCP/IP, on a décrit son fonctionnement et on a bien détaillé

son aspect analytique en présentant les différentes équations décrivant son comportement.

Tout ça n’a pas donné aucune idée de sa performance. On ne sait pas s’il peut achever

l’objectif pour lequel il est développé. On a besoin de valider ce modèle et de vérifier ses

équations.

Ce chapitre porte sur la validation du mécanisme hybride FEC/ARQ-SR et sur

l’analyse de son comportement. La vérification de ses équations est laissée pour le

chapitre qui suit.

Notons qu’une validation est basée généralement sur la simulation ou bien sur des

mesures réelles. Dans notre travail, le choix s’est porté sur la simulation depuis qu’elle

est relativement plus simple et qu’elle nécessite moins de matériels.

III.2 Simulateur : On a décidé de simuler le modèle hybride FEC/ARQ-SR afin de le valider, d’où

la nécessité d’un simulateur qui groupe à la fois FEC, ARQ-SR et la livraison en-ordre

des paquets à IP. On n’a pas trouvé un simulateur qui répond à cet objectif. On l’a alors

implémenté dans NS-2, le simulateur du réseau développé à LBNL [28]. Cette

implémentation a nécessité une forte connaissance des langages C++ et OTCL, et une

base solide dans la programmation orientée objet. La hiérarchie des classes dans NS-2 a

été bien étudiée. Ce qui gène dans cette implémentation est le dialogue existant dans le

mécanisme ARQ-SR ; deux terminaux doivent échanger entre eux des trames ARQ et des

acquittements ARQ d’une manière transparente par rapport à TCP et à tout le reste du

réseau, ce qui nécessite une gestion très précise du temps dans NS-2. Aussi, on doit gérer

la priorité entre les transmissions originales des trames ARQ et les retransmissions. En

outre, il faut ajouter la complexité de programmation bas niveau en travaillant avec les

27


pointeurs et en manipulant les adresses des variables, en particulier lors du besoin de

créer des nouvelles structures de listes chaînées. La difficulté dans cette implémentation

n’est pas dans l’algorithme à mettre pour programmer ces protocoles, mais elle apparaît

dans le fait que le code à écrire doit être harmonisé avec la structure de NS-2, il doit

interagir avec des centaines des fichiers et des classes. Ainsi, ce n’est pas étonnant qu’une

vingtaine des fichiers a été modifiée pour réaliser ce modèle, une réalisation qui a pris

environ cinq semaines.

III.3 Implémentation : Brièvement, au niveau de la couche liaison, on ne voit pas les caractéristiques

physiques du lien sans fil, comme les trajets multiples, l’interférence, la mobilité, etc., ce

qui nous intéresse est son taux de perte élevé. Pour cela, on a décidé d'assimiler un lien

sans file dans NS-2 à une connexion filaire ordinaire à laquelle on associe un module

d'erreur. Ce module d'erreur est unidirectionnel, on doit préciser dans quel sens on veut

l'appliquer. Le modèle hybride est implémenté entre la classe LinkDelay (delay.cc,

delay.h), qui modélise le délai des liens, et la classe ErrorModel (errmodel.cc,

errmodel.h) de ce même lien, qui modélise le processus de pertes dans les liens.

LinkDelay simule l'entrée du lien sans fil, c'est dans ce module où se fait la segmentation

des paquets IP en X trames ARQ (LL frames) et qu'on ajoute la redondance de la FEC.

La sortie du lien sans fil est simulée par le module Errormodel qui assure le décodage de

la FEC, qui acquitte les trames ARQ par des ACKs ou des NACKs, et qui livre les

paquets correctement reçus à leurs destinations après les avoir reséquencés.

Pour avoir un accès malléable aux différents paramètres du modèle, on les a

rendus accessible à travers OTCL. On a attaché ces paramètres écrits en C++ avec leurs

correspondants en OTCL en utilisant la méthode « bind() ». Ainsi, le modèle sera défini,

activé ou désactivé à travers le script « .tcl » à exécuter pour lancer une simulation, au

lieu d’ouvrir le code C++ chaque fois qu’on veut changer la valeur d’un paramètre, et de

refaire la compilation après. Pour clarifier les idées, soit cet exemple d’un script « .tcl »

montrant les différentes étapes à suivre pour définir le modèle :

D’abords, il faut choisir la connexion filaire qu'on va l'assimiler à un lien sans fil

et on y ajoute le module d'erreur. Après, on doit ajuster les différents paramètres du

modèle.

#On définit une liaison entre 2 nœuds n0 et n1

28


set n0 [$ns node]

set n1 [$ns node]

$ns duplex-link $n0 $n1 2Mb 100ms DropTail

#On définit le modèle d'erreurs.

set loss [new ErrorModel]

#On cherche le Handle du lien entre les deux nœuds n0 et n1

#(lien unidirectionnel dans le sens n0 n1)

set lossylink [$ns link $n0 $n1]

#On associe le module d'erreurs au lien n0 n1

$lossylink install-error $loss

#On cherche le Handle de l'objet LinkDelay utilisé par le lien

#unidirectionnel lossylink

set Delay [$lossylink link]

#on indique aux 2 modules qu'on veut activer le modèle hybride

$loss set ARQ 1

$Delay set ARQ 1

#par défaut, les 2 variables ARQ sont mises à zéro, càd le

#modèle hybride est désactivé, pour qu'il fonctionne, on doit

#les mettre à 1

#ajuster les différents paramètres du modèle :

#configuration du module ErrorModel

$loss set K 10

$loss set N 11

$loss set delta 5

$loss set ACK_size 10 ; #préciser la taille (en octets) de

#l'ACK de ARQ

#configuration du module LinkDelay

$Delay set N 11

$Delay set K 10

$Delay set delta 5

$Delay set FEC 1 ; #activation de la FEC dans le modèle

#hybride

$Delay set X 6 ;

29


$Delay set inord 1 ; #inord = 1 : On active le

#reséquencement des paquets IP

#avant de les délivrer à IP; sinon

#on met inord = 0 (valeur par

#défaut)

#ajuster les autres paramètres du module ErrorModel

$loss set rate_ 0.01 ; #taux de perte

$loss drop-target [new Agent/Null] ;

$loss unit packet ; #en précisant le paquet comme unité de

#perte, le taux de perte déjà précisée

#est le block error rate càd la

#probabilité de perte d'un block

#(=unité) est indépendante de leurs

#tailles

III.4 Outils utilisés : Pour bien étudier la performance du modèle et pour le comprendre, on a fait

environ 8000 simulations en faisant balayer les paramètres du modèle (p, D, δ, K, N, X,

reséquencement actif ou non) selon des marges de valeurs convenables. Pour chaque

combinaison d’eux on a tiré la valeur de l’utilisation du lien sans fil.

Pour économiser le temps, on a tourné toutes les simulations à l’aide d’un petit

programme « matlab » qui fait lui-même le balayage des différents paramètres et les faire

passer au script « .tcl » à exécuter. Ainsi on lance un programme « matlab » pour avoir en

fin du compte un fichier contenant 8000 résultas correspondants à 8000 simulations. Pour

présenter les résultats obtenus, on doit leur appliquer un filtrage pour aboutir à tirer les

différentes figures montrant l’utilisation du lien sans fil en fonction des différents

paramètres du modèle. De même, ce filtrage est fait par un autre programme « matlab »

qui utilise l’outil « awk ». En outre, ce programme assure l’organisation des résultats

dans des répertoires d’une manière convenable (un répertoire par graphe) et il crée un

fichier par figure, ce fichier sera exécuté par l’outil graphique «gnuplot » [29], [30] pour

tracer le graphe correspondant.

30


III.5 Simulations : Après qu’on a implémenté le modèle dans NS-2, on est entré la phase de

simulation. Le modèle est seulement appliqué au lien sans fil, et il est transparent au reste

du réseau même aux hôtes TCP. Nos simulations sont divisées en deux parties. La

première partie se concentre sur l'utilisation du lien sans fil en cas où C = 10 connexions

TCP concourantes. La deuxième partie se concentre sur le throughput d'une connexion

TCP utilisant seule le lien sans fil pour son trafic. Dans tous les scénarios étudiés, K est

fixé à 10, X à 6 et la taille des unités LL (link-level) à 25 octets. Les paquets TCP sont

alors de taille constante égale à 1500 octets (MTU d'Ethernet). Chaque simulation

tournée a duré 2000 secondes. Cette durée relativement longue est nécessaire pour

absorber la phase Slow Start initiale du TCP.

Les valeurs données à K et X sont aléatoirement choisies. D'autres valeurs sont

possibles. Pour le moment, notre but n'est pas d’optimiser ces quantités, mais plutôt

d’optimiser la quantité de FEC à utiliser et le niveau de persistance δ. On regarde pour K

et X comme des entrées du problème plutôt que des sorties. Ceci réduit le nombre de

paramètres à optimiser. Notons que l'optimisation de K et X est également un problème

intéressant étant donné le paradoxe qu'il implique. Nous étudierons ce problème

d'optimisation dans le chapitre qui suit. Par exemple, pour des tailles constantes des

paquets (S constante), la taille des trames LL diminue quand X augmente, ce qui décroît

la probabilité qu'une trame LL est corrompue. Ceci devrait améliorer la performance.

Cependant, en augmentant X, K diminue, par conséquent le nombre des unités

redondantes dans une trame LL diminue, si la quantité de FEC n’est pas changée. Il est

montré dans [8] que ceci peut détériorer la performance puisque les trames peuvent

maintenant résister à moins d'erreurs. Le problème d'optimisation devient plus intéressant

quand nous permettons à la taille S de paquet de changer. La taille de paquet décide sur le

taux avec lequel TCP augmente sa fenêtre de congestion [8], [31].

III.6 Première partie : utilisation du lien sans fil (C = 10) : III.6.1 Scénarios des simulations :

Dans ce paragraphe, nous présentons comment l'utilisation du lien sans fil varie

selon les divers paramètres de FEC et de ARQ-SR. Dix connexions TCP de longues

durées croisent le lien sans fil dans le même sens. Nous avons considéré plusieurs

scénarios qui sont dérivés de la topologie de réseau mise dans la Figure III.1.

31


Comme la figure montre, il y a 10 sources TCP qui transmettent des données FTP

simultanément et sans interruption vers la même destination. Chaque source correspond à

une seule connexion TCP. Les sources adoptent la version NewReno du TCP. Les

sources et la destination sont reliées au lien sans fil par l'intermédiaire des liens de 10

Mbps ayant un délai de propagation unidirectionnel égale à 20 ms. la bande passante B

du lien sans fil est de 2 Mbps, son délai D change entre 20 ms. et 200 ms selon le

scénario étudié. Les valeurs données à D modélisent différents types de liens sans fil

s'étendant des liens terrestres aux liens satellitaires. Les unités de transmission sont

corrompues dans le lien sans fil avec une probabilité p, avec p varie entre 10 -4 et 10-2 ce

qui correspond à P (taux de perte des paquets TCP) s'étendant de 0.0060 à 0.4528 (Eq.

II.3, II.4, II.5) dans l’absence des mécanismes de correction.

La destination utilise la fonctionnalité « delayed ACK » de TCP [31]. Pour éviter

n'importe quelle limitation du trafic due à d'autres raisons que les erreurs dans le lien sans

fil, nous avons pris les mesures suivantes:

Les liens filaires sont complètement fiables.

La taille de la fenêtre négociée de TCP est très grande, jusqu'à 2000 paquets.

Les « buffers » dans les routeurs du réseau sont très grands, ils peuvent stocker

jusqu'à 500 paquets.

Le buffer utilisé pour le reséquencement des paquets à la sortie du lien sans fil est

très grand.

Dans ces conditions, il est clair que le lien sans fil est le seul goulot sur le chemin

des connexions TCP. Les pertes de congestion n'apparaissent pas dans les routeurs du

réseau à moins que le lien sans fil soit entièrement utilisé. Nous voulons optimiser les

paramètres de FEC et de ARQ-SR dans cet arrangement. Le problème d'optimisation

32

Figure III.1 : Topologie du réseau.


n'est pas significatif quand les connexions TCP sont contraintes par les autres parties du

réseau.

On commence à étudier séparément les effets de FEC et de ARQ-SR sur

l'utilisation du lien sans fil, c.-à-d. l'effet de FEC seule et celui de ARQ-SR seul. En

second lieu, on étudie la performance du modèle hybride, c.à.d. quand FEC et ARQ-SR

sont combinés ensemble. Intuitivement, le besoin de FEC est important quand le délai du

lien sans fil est grand et pour un taux d'erreur élevé, puisque l'utilisation de ARQ-SR dans

ce cas-ci résulte en une augmentation considérable du RTT. Dans les autres scénarios

(petit délai, moins de pertes), l'utilité de FEC est réduite puisque l'augmentation du RTT

provoqué par les retransmissions ARQ-SR a moins d'impact sur l'utilisation que la

quantité de la bande passante consommée par FEC. Ce raisonnement est confirmé par nos

simulations. Pour ne pas compliquer la présentation, nous montrons seulement les

scénarios qui donnent les résultats les plus significatifs. Plus de résultats sont exposés

dans Annexe 3.

III.6.2 FEC seule : En appliquant le modèle hybride, l'effet de FEC seule est obtenu en mettant δ à 0.

Dans ce cas, les trames LL ne sont pas retransmises, mais elles sont seulement protégées

par FEC.

La Figure III.2 présente 3 lignes qui montrent la variation de l'utilisation en

fonction du paramètre N de FEC, qui modélise la quantité de redondance. Ces 3 courbes

correspondent à 3 valeurs distinctes du délai; D = 20, 100, 200 ms. Dans tous ces cas, p

est pris très élevé 10-2 (P = 0.4528 dans l’absence des mécanismes de correction), c.à.d.

des cas extrêmes. Clairement, il y a une amélioration importante de l'utilisation avec la

33

Figure III.2 : Utilisation du lien sans fil pour 10 Connexions TCP, FEC seule : p = 10-2.


première unité de redondance. En augmentant N, l'utilisation passe par un maximum. Ce

point correspond à la quantité optimale de FEC, qui à son tour correspond à N = 11 pour

D = 20 ms et à N = 12 pour D = 100, 200 ms. Quand N=12, environ 80% de la bande

passante du lien est utilisé par les données TCP, et le 20% restant est utilisé par

l'information redondante. Ajouter de la redondance au-delà du point optimal résulte en

une diminution de l'utilisation, mais cette diminution est plus lente que l'augmentation de

l'utilisation du côté gauche du point optimal. Le même comportement est trouvé dans [8].

Pour toutes les valeurs de N du côté droite du point optimal, la quantité de FEC est plus

que nécessaire. On devrait compter que l'affaiblissement de l'utilisation du côté droite est

près de 100*K/N. Quand D diminue, on observe sur la Figure III.2 qu’on a besoin moins

de FEC pour atteindre l’utilisation maximale. On a le même résultat quand p diminue, qui

est illustré sur le Figure III.3, où on voit 3 courbes qui correspondent à 3 valeurs de p =

10-2, 10-3, 10-4, D est mis à 200 ms.

III.6.3 ARQ-SR seule : Maintenant, on examine l'effet de ARQ-SR seule en regardant les valeurs de

l'utilisation pour N = K (= 10). Les résultats sont tracés dans la Figure III.4. Cette figure

montre l'utilisation du lien sans fil tracée en fonction du δ (persistance de ARQ-SR). On

examine deux cas: (i) la livraison en-ordre des paquets à IP à la sortie du lien sans fil est

activée, ce qui est indiqué sur la figure par ord = 1, et (ii) la livraison en-ordre des

paquets à IP n'est pas activée, qui est indiqué sur la figure par ord = 0. Pour D et p, on

considère les mêmes valeurs comme ci-dessus (cas de FEC seule); on a trois valeurs du

délai, D = 20, 100, 200 ms, et p est mis à 10-2. Etonnamment, l'utilisation augmente

toujours avec δ, quoiqu’on traite un cas extrême où le délai D est grand et le taux de perte

est élevé. ARQ-SR réduit le taux de perte des paquets TCP beaucoup plus qu'il augmente

34

Figure III.3 : Utilisation du lien sans fil pour 10 Connexions TCP, FEC seule : D = 200 ms.


le délai de bout-en-bout, ce qui a comme conséquence cette amélioration monotone. On

note dans ces simulations que le reséquencement des paquets à la sortie du lien sans fil

est essentiel pour obtenir la bonne performance avec ARQ-SR, autrement les paquets

arrivent déséquencés au récepteur TCP et déclenchent la transmission des ACKs

dupliqués, quelque chose très nocive pour TCP depuis qu’il résulte en une division inutile

de la fenêtre de congestion. Un autre résultat étonnant est celui qu’avec ARQ-SR seule,

lorsque le reséquencement des paquets est activé, on peut atteindre une utilisation plus

élevée que celle atteinte avec la quantité optimale de FEC lorsqu’elle est utilisée seule.

La même découverte s'applique aux autres scénarios lorsque p est plus petite, et il est bien

plus prononcé en faveur de ARQ-SR (Annexe 3).

III.6.4 L’hybride FEC/ARQ-SR : Maintenant, on présente les résultats qu’on obtient en appliquant le modèle

hybride FEC/ARQ-SR avec la livraison en-ordre. Nous considérons le scénario très

délicat, où le délai du lien sans fil est le plus grand D = 200 ms, et où le taux d'erreur est

très élevé p = 10-2. Pour ce scénario, la Figure III.5 montre l'utilisation du lien sans fil en

fonction du paramètre N de FEC. On voit dans la figure 6 courbes qui correspondent à 6

valeurs de la persistance, δ = 0, 1, 2, 3, 4, 5. La ligne δ = 0 donne l'impact de FEC seule

sur l'utilisation, il est la même ligne qui apparaît dans les Figure III.2 et III.3 pour le

couple (p, D) = (10-2, 200 ms). En regardant les valeurs de l'utilisation sur l'axe des

ordonnées, c.à.d. pour N = K = 10, on peut examiner l'effet de ARQ-SR seule, qui est

détaillé dans la Figure III.4. En combinant FEC et ARQ-SR, on espère réaliser une

meilleure performance qu'en utilisant les deux mécanismes séparément. Les résultats

dans la Figure III.5 semblent contredisant cette idée, au moins dans les suppositions de

notre analyse (transferts TCP de longue durée, processus d’erreurs de Bernoulli). On

35

Figure III.4 : Utilisation du lien sans fil pour 10 Connexions TCP, ARQ-SR seul : p = 10-2


remarque que la meilleure performance qu’un mécanisme hybride FEC/ARQ-SR peut

donner est près de ce qui est obtenu par ARQ-SR seule (pour δ = 5). Pas plus d'une unité

de redondance (N=K+1) est nécessaire pour atteindre l'utilisation la plus élevée.

Dans les autres scénarios où le délai et le taux d'erreur sont plus petits (comme

dans la Figure III.6 qui correspond à un plus petit p = 10-3 mais au même D = 200 ms, ou

dans la Figure III.7 où p = 10-2 et D = 100 ms), nos résultats de simulation prouvent qu'il

n'y a aucun besoin de tout de FEC, et que ARQ-SR seule peut réaliser la meilleure

performance. C'est un résultat étonnant, mais il semble logique, puisque FEC consomme

une partie supplémentaire de la bande tout le temps, tandis que ARQ-SR consomme une

partie supplémentaire de la bande seulement quand des paquets sont perdus. Une idée a

pu être d’utiliser FEC pour protéger seulement des retransmissions, trames non

originales. Cette idée sera détaillée dans le Chapitre V.

36

Figure III.5 : Utilisation du lien sans fil pour 10 Connexions TCP, Modèle Hybride, p = 10-2, D = 200 ms

Figure III.6 : Utilisation du lien sans fil pour 10Connexions TCP, Modèle Hybride, p = 10-3, D = 200 ms


III.7 Deuxième partie : Throughput d’une connexion TCP seule : En présence de 10 connexions TCP, les erreurs de transmission qui apparaissent

sur le lien sans fil sont réparties sur toutes ces connexions. Ainsi leur impact sur chacune

de ces connexions est plus petit que lorsqu’une connexion TCP seule est active sur le lien

sans fil. Nous voulons étudier l'impact du mécanisme hybride dans le cas extrême où une

connexion TCP souffre seule des erreurs de transmission, et essayer d’optimiser les

paramètres de FEC et de ARQ-SR pour ce cas. Clairement, plus d'effort (plus de FEC, de

plus grand δ) est nécessaire dans le cas d'une seule connexion que dans le cas de 10 pour

réaliser l’utilisation maximale.

On considère la même topologie du réseau que celle utilisée dans le paragraphe

précédent, avec la différence que maintenant on a une source TCP qui correspond à une

connexion TCP. Pour ne pas compliquer les choses, nous présentons seulement deux

ensembles de résultats, plus de résultats sont mis dans Annexe 3. Le premier ensemble

(Figure III.8) correspond au cas où D = 200 ms et p = 10-2. L'axe des ordonnées dans la

37

Figure III.8 : Throughput d’une connexion TCP seule sur le lien sans fil, Modèle Hybride, p = 10-2, D = 200 ms

Figure III.7 : Utilisation du lien sans fil pour 10Connexions TCP, Modèle Hybride, p = 10-2, D = 100 ms


figure montre le throughput de la connexion TCP exprimé en Mbps. On note la même

tendance que dans le cas de 10 connexions TCP. Avec ARQ-SR seule, TCP peut réaliser

une utilisation très élevée, qui ne peut pas être achevée par FEC seule. Le point optimal

de fonctionnement du modèle hybride est près de celui de ARQ-SR seule. On note

également comment on a besoin d'un plus grand δ dans ce cas pour achever la pleine

utilisation du lien sans fil. L'utilisation optimale est égale à celle obtenue pour 10

connexions, qui est une bonne indication que l'utilisation maximale qu’on peut atteindre

avec un hybride FEC/ARQ-SR est approximativement indépendante du nombre de

connexions TCP.

Le deuxième ensemble de résultats correspond à la variation du throughput de

TCP en fonction du niveau de persistance (δ) lorsque ARQ-SR seule est appliqué. Nous

voulons être sûrs que l'utilisation du lien sans fil augmente toujours avec δ, un résultat

que nous avons montré dans le cas de 10 connexions TCP. Nous traçons le throughput

d'une connexion TCP pour différentes valeurs de δ s'étendant de 0 à 10. Ce deuxième

ensemble de résultats est indiqué sur la Figure III.9. L'axe des abscisses dans la figure

correspond à δ et l'axe des ordonnées au throughput de TCP. Pour ces résultats, la valeur

de p est mise à 10-2 et le reséquencement des paquets à la sortie du lien sans fil est activé

(ord = 1). La figure montre trois lignes qui correspondent à trois valeurs distinctes de D;

D = 20, 100, 200 ms. pour les trois lignes dans la figure, les throughputs de TCP

commencent par un accroissement rapide pour être en fin du compte saturés. Aucune

dégradation des throughputs n’est provoquée par l’augmentation de δ. En se basant sur

les résultats de nos simulations, nous concluons que dans les hypothèses de notre étude,

l'utilisation du lien sans fil augmente toujours monotonement avec δ, quelque soient le

nombre de connexions TCP, le délai et le taux de perte.

38

Figure III.9 : Throughput d’une connexion TCP seule sur le lien sans fil, ARQ-SR seul, p = 10-2, D = 200 ms


III.8 Conclusions : L’étude du modèle hybride a nécessité son implémentation dans le simulateur de

réseaux « NS-2 ». Cette implémentation a été réalisée avec succès, malgré toutes les

difficultés qui accompagnent en général une telle implémentation (maîtrise des langages

C++ et OTCL, connaissance de la hiérarchie de classes de « NS-2 »). Le mécanisme

implémenté a fonctionné correctement et a permis à l’étude d’aboutir.

Après une campagne de simulations, la conclusion principale de notre analyse est

celle pour des transferts TCP de longue durée et un processus d’erreurs de Bernoulli,

l'utilisation de ARQ-SR est plus avantageuse que l'utilisation de FEC, même dans les cas

extrêmes où le délai est grand et le taux d'erreur est élevé. Par conséquent, l'utilisation

maximum que nous pouvons atteindre avec un modèle hybride FEC/ARQ-SR est

approximativement indépendante du nombre de connexions TCP. Pour une certaine

persistance δ, il y a une quantité optimale de FEC à ajouter afin de réaliser la pleine

utilisation du lien sans fil. Toute quantité supplémentaire de FEC détériore la

performance au lieu de l'améliorer.

Ces résultats seront comparés avec leurs homologues numériques dans le chapitre

suivant. En outre, on va y rencontrer une étude plus détaillée qui porte sur l’optimisation

des paramètres du modèle y compris les 2 paramètres X et K.

39

IV

Vérification du modèle, Optimisation

C

H

A

P

I

T

R

E

Chapitre IV : Vérification du modèle, Optimisation

IV.1 Introduction : Comme on a vu dans le chapitre précédent, les simulations ont bien validé le

modèle hybride FEC/ARQ-SR et elles ont démontré son utilité. Afin de compléter l’étude

de ce modèle on va vérifier ses équations.

Ce chapitre porte sur la comparaison des résultats analytiques avec ceux obtenus

par simulation. Après, une étude détaillée montre l’impact des différents paramètres sur

la performance du modèle tout en calculant numériquement leurs valeurs qui servent à

optimiser l’utilisation du lien sans fil.

IV.2 Vérification : Lorsqu’on a développé les équations du modèle, on n’a pas pu les simplifier

davantage. Elles sont assez complexes étant donnée la diversité des opérations effectuées

(probabilités, statistiques, intégrales, etc.). Pour cela on a décidé de les résoudre

numériquement en les implémentant dans matlab, le logiciel souvent utilisé par les

scientifiques pour effectuer leurs calculs. Le choix s’est porté sur matlab à cause des

facilités qu’il assure en particulier, il est un langage haut niveau, facile à traiter et il

couvre le calcul des probabilités, les statistiques, les intégrales, l’optimisation et la

présentation professionnelle des résultats sous formes de courbes illustratrices. Ainsi

chaque expression y est écrite comme une fonction indépendante ayant ses paramètres

d’entrée et de sortie, ce qui facilite la manipulation de ces équations et permet de les

vérifier une par une. Ces fonctions interagissent entre elles pour calculer l’utilisation du

lien sans fil.

La vérification du modèle analytique se fait en comparant les résultats des

simulations avec ceux analytiques correspondants aux même scénarios. Chaque scénario

est indiqué en matlab par les paramètres d’entrée des différentes fonctions.

En regardant les équations du modèle, on peut les diviser en deux parties. La

première partie contient des expressions rigoureuses n’impliquant aucune approximation.

Cette partie groupe les expressions de : R, U, PT, PF, P, α et le calcul de RTT (Eq. II.8) en

41


l’absence du délai de reséquencement et de celui de la priorité des retransmissions sur les

transmissions originales, c.à.d. le calcul de RTT dans le cas de FEC seule en éliminant

l’ARQ-SR.

La deuxième partie contient ce qui reste, c.à.d. la présence de ARQ-SR. On a

commencé par des équations très rigoureuses comme le calcul du temps mis par un

paquet donné pour qu’il soit correctement transmis sur le lien sans fil, c.à.d. le calcul de

M et de Y. Mais en traitant le délai de reséquencement, on est opposé par le problème

classique qui est bien étudié dans [27] et dont les équations sont très complexes qu’on ne

peut pas résoudre qu’en faisant quelques suppositions. Pour cela on a vu deux solutions,

la première en supposant que l’arrivée des paquets est poissoniènne tandis que la

deuxième en la supposant déterministe. Dans les deux cas le temps mis par un paquet

pour traverser correctement le lien sans fil est considéré exponentiellement distribué.

Pour bien comprendre l’impact de ces approximations, on présente d’abords la partie

rigoureuse seule c.à.d. en l’absence de ARQ-SR, après on montre les résultats du modèle

complet en mettant en relief l’exactitude des telles suppositions.

Notons que dans les calculs numériques, on a adopté la même topologie étudiée

dans les simulations, X est fixé à 6 et K à 10. En outre, on a mis π , dans (Eq. II.23), à 1

en considérant que le lien est en pleine utilisation en essayant d’éviter un calcul itératif,

on se rappelle que π indique l’utilisation du lien qu’on est en train de calculer.

IV.2.1 Vérification de la partie rigoureuse : En activant seulement la FEC sur le lien sans fil, on aura δ = 0, ainsi tout délai de

reséquencement et le délai de la priorité des retransmissions sur les transmissions

originales sont éliminés. Dans ces conditions, E[M] dans (Eq. II.20) sera égale à zéro,

dès que M = 0, et de même on aura dans (Eq. II.21) E[Y] = X. on peut écrire :

42

(IV.1)


Les figures ci-dessus correspondent à 3 scénarios, les gauches (série a) présentent

les résultats analytiques. Les résultats des simulations sont présentés à droite, séries b.

Dans les figures IV.1.a et IV.1.b on a tracé l’utilisation du lien sans fil en fonction du

paramètre de FEC, N, lorsque la bande passante du lien est partagée simultanément entre

10 connexions TCP. Dans ce cas p = 10-2 et on a 3 valeurs de D, D = 20, 100, 200 ms.

43

Figure IV.2 : FEC seule, une connexion, p = 10-2, D = 20, 100, 200 ms

b) Résultats des Simulations.a) Résultats analytiques.

Figure IV.1 : FEC seule, 10 connexions, p = 10-2, D = 20, 100, 200 ms

Figure IV.3 : FEC seule, une connexion, D = 200 ms, p = 10-2, 10-3, 10-4.

b) Résultats des Simulations.

b) Résultats des Simulations.

a) Résultats analytiques.

a) Résultats analytiques.


Les deux ensembles de courbes, à droite et à gauche, sont semblables. Cette observation

se répète pour les deux autres scénarios où il est présenté le throughput d’une connexion

TCP traversante seule le lien sans fil. De même, le throughput est tracé en fonction de N.

Les résultats des simulations vérifient bien ceux analytiques. Des petites erreurs

apparaissent, ceci est dû aux hypothèses qu’on a prises dans le modèle analytique. Par

exemple, on a supposé qu’il n’y a pas de perte de congestion mais, en fait, ce n’est pas le

cas. En effet, on a utilisé dans les simulations des grands buffers de routage pour éviter

des telles pertes. Mais, à la pleine utilisation du lien sans fil, ces buffers sont pleines et

des paquets seront rejetés. Ces pertes ne sont pas comptées dans le calcul de P.

Autrement dit, en matlab, c.à.d. dans le modèle analytique, on calcule les throughputs des

connexions TCP en fonction du RTT calculé et de P qui compte les pertes sur le lien, et

toute perte de congestion est exclue. Si la somme de ces throughputs est inférieure que

α*B on le considère comme l’utilisation du lien, sinon l’utilisation sera égale à α*B. En

réalité, en appliquant le modèle hybride sur le lien sans fil, P tend vers zéro, par suite

l’équation (Eq. II.1) donne un débit infini pour TCP et ce n’est pas logique parce que la

bande passante du lien est limitée. Alors ce qui peut limiter ce débit en l’absence de toute

erreur sur le lien sont les pertes de congestion qui apparaissent lorsque le lien est saturé

malgré les grands buffers de routage et ces pertes sont plus dangereuses lors d’un grand

délai. Ce qui explique l’abaissement du throughput dans le graphe IV.2.a par rapport à

celui dans le graphe IV.2.b à la pleine utilisation à partir de N = 12, 13, …

La même chose s’applique au scénario (D = 200 ms, p = 10-2, 10-3, 10-4) présenté

dans les figures IV.3.a et IV.3.b.

Ainsi, cette partie rigoureuse du modèle est bien vérifiée. On a les mêmes

résultats analytiques et de simulation et par suite on a les mêmes conclusions sur la

performance du modèle en cas de la FEC seule citée dans le Paragraphe (III.6.2).

IV.2.2 Vérification du modèle complet : Dans ce paragraphe, l’utilisation du lien sans fil est calculée pour le modèle

hybride FEC/ARQ-SR tout en considérant deux processus d’arrivée de paquets au lien

sans fil : poissonien et déterministe. Le but est de comparer ces deux processus avec les

résultats de simulation, de voir leur exactitude et de déterminer leurs domaines de

validité.

A la pleine utilisation, on est toujours limité par α*B. Alors les processus vont

donner les mêmes résultats. Le problème apparaît lorsqu’on est dans un état intermédiaire

44


où l’utilisation est entre zéro et α*B. Pour qu’on puisse calculer l’utilisation, on a besoin

du temps d’inter-arrivée 1/λ (Eq. II.24 et II.25) qui est, lui-même, fonction de

l’utilisation. Pour résoudre ce problème, on a considéré que le lien est saturée, ainsi :

45

Figure IV.4 : Modèle complet, une connexion TCP.

c) Arrivée déterministe

b) Arrivée Poissoniènne.

a) Résultats des simulations.

(IV.2)


Dans ces trois figures IV.4.a, IV.4.b et IV.4.c on présente le throughput d’une

connexion TCP traversante seule le lien sans fil. Il est tracé en fonction du paramètre N.

Figure IV.4.a contient les résultats des simulations, Figure IV.4.b contient les résultats

analytiques pour un processus d’arrivée des paquets poissonien et Figure IV.4.c contient

ceux analytiques pour un processus d’arrivée déterministe. Dans chacune de ces trois

figures sont tracés six courbes correspondantes à six valeurs de δ, δ = 0, …, 5. Le

throughput est exprimé sur l’axe des y en Mbps. Dans les trois figures, les courbes δ = 0

correspondent à l’absence de ARQ-SR, le cas qu’on a traité dans le paragraphe précédent.

Ce qui nous intéresse maintenant sont les cas où .

En regardant les figures IV.4.a et IV.4.b, on constate une grande ressemblance

entre les simulations et les résultats analytiques ayant des arrivées poissoniènnes pour les

faibles valeurs de throughput. Pour δ = 1, 2 et 3, ce qui correspondent à une utilisation

du lien respectivement d’environ 4%, 10% et 24%, on a les mêmes résultats. Pour δ = 4,

le processus poissoniènne a augmenté considérablement le throughput. Pour les autres

scénarios (Annexe 4) on trouve le même comportement : Pour des valeurs de l’utilisation

inférieures à 40%, les résultats analytiques sont semblables à ceux des simulations. Au-

dessus de 40%, l’utilisation calculée est supérieure que celle simulée. Ces résultats sont

prévus dès que la supposition des arrivées poissoniènnes est fait dans [27] lorsque le lien

est faiblement chargé.

Dans le cas des arrivées déterministes (Figures IV.4.c), on a le contraire. Les

résultats analytiques sont proches de ceux simulées pour des grandes valeurs de

throughput, lorsqu’on est proche de la pleine utilisation du lien. En adoptant ce processus,

on a toujours des valeurs numériques inférieures que celles des simulations. Le cas pire

est pour des faibles valeurs de l’utilisation où on remarque une grande erreur entre les

deux.

Ajoutons que les valeurs optimales de l’utilisation obtenues par simulation sont

légèrement inférieures que celle analytiques pour les deux processus, ceci est dû à la

même raison citée dans le Paragraphe IV.2.1 précédant que les pertes de congestion qui

apparaissent à la pleine utilisation ne sont pas comptées dans le calcul de P.

Pour conclure ce paragraphe on peut dire que les deux processus sont

complémentaires. Dans les scénarios étudiés, pour des petites valeurs de l’utilisation, on

adopte le processus poissonien et pour les grandes valeurs on considère que les arrivées

sont déterministes. Dans les deux cas, on a obtenu les mêmes valeurs de N et de δ qui

46


optimisent la performance du modèle, ce qui permet d’adopter avec confiance les

résultats de l’optimisation numérique.

IV.3 Etudes des paramètres K et X : Pour simplifier l’étude dans les simulations qu’on a effectuées, on a considéré les

paramètres X et K comme étant des entrées du problème étant donné que le but était de

valider le modèle et non pas de l’optimiser. Leurs valeurs ont été choisies arbitrairement.

Lors de l’optimisation du modèle, on doit tenir en compte leurs impacts sur la

performance, ce qui constitue l’objectif de ce paragraphe. Pour le réaliser, on a étudié la

variation de α en fonction de S, X et K. Notons que α indique l’utilisation optimale pour

un scénario donné c.à.d. lorsqu’on est à la pleine utilisation du lien sans fil.

En l’absence de FEC, on n’a que les retransmissions pour recouvrir les erreurs sur

le lien bruyant. Ainsi le paramètre K, qui implique la capacité de FEC à corriger les

erreurs [8], perd ce sens et il est maintenant juste un indicateur de la quantité

d’information dans une trame donnée. Pour S = K*X = cte, en diminuant X, la taille de

trame augmente, de même pour sa probabilité de perte PT. En outre, si une grande trame

est perdue, une grande quantité d’information doit être retransmise, ce qui diminue

l’utilisation du lien.

X 1 2 3 4 5 6 10 12 15 20 30 60

K 60 30 20 15 12 10 6 5 4 3 2 1

α 0.5472 0.7395 0.8178 0.8600 0.8864 0.9044 0.9415 0.9510 0.9606 0.9703 0.9801 0.9900

Le Tableau IV.1 montre les valeurs de α dans le cas où S = K*X = 60 unité de

transmissions LL en faisant balayer X sur toutes les valeurs possibles. Ce scénario

correspond à p = 10-2. La FEC est éliminée en mettant N = K. Notons que α est

indépendante de D. Ce tableau (Tableau IV.1) vérifie notre raisonnement ; pour X = 1, α

est égale à 0.5472 tandis qu’elle arrive à 0.99 pour X = 60. notons que dans le Tableau

IV.1 δ est mis à 10 pour s’assurer qu’on travail à la pleine utilisation ainsi maximiser α

équivalent à maximiser l’utilisation. Dans le cas contraire où on n’a pas la pleine

utilisation, on peut avoir α très grande mais l’utilisation est beaucoup inférieure que α*B.

soit α = 0,8638 pour δ = 1, p = 10-2, K = N = 10 et X = 6 mais l’utilisation est égale à

20.98% pour D = 200 ms.

47

TABLEAU IV.1 : Optimisation de α, ARQ-SR seul, δ = 10.


Ainsi, en l’absence de FEC, on a toujours intérêt à diminuer la taille des trames

LL, par suite si S augmente on doit augmenter X avec S et non pas K. lorsque S diminue,

on diminue le nombre des unités de transmissions par trame c.à.d. on diminue K.

En présence de FEC, K reprend sa place dans l’évaluation de la capacité de FEC.

K joue maintenant un rôle très important surtout parce que c’est la FEC qui intervient

premièrement pour corriger les erreurs du lien sans fil tandis que l’ARQ-SR n’est

demandée que lors de l’échec de FEC. L’étude présentée dans [8] montre que la capacité

de FEC à corriger les erreurs augmente avec K. par contre pour un S = K*X = cte, en

augmentant K, X diminue, ainsi retrouve le même raisonnement déjà cité pour le cas de

l’absence de FEC.

X 1 2 5 10 K/N δ

K 100 50 20 10

10/11 5N 110 55 22 11

α 0.9091 0.9091 0.9079 0.9044

Le calcul qu’on a effectué montre que, pour S = K*X = cte, en augmentant K la

capacité de FEC augmente plus que la diminution de X affaiblit la performance du

modèle. Le Tableau IV.2, qui est calculé pour p = 10-2 et δ = 5, montre les valeurs de α

obtenues en balayant plusieurs valeurs de K et de X tel que K*X = 100 unités de

transmissions LL. Il est clair que α est plus sensible à K en presence de FEC, pour le

même taux de FEC, K/N = 10/11, elle accroît avec K. Ainsi, en augmentant S, on doit

augmenter K pour garder la performance. Et si S diminue on doit diminuer X.

Notons qu’en mettant δ à zéro, l’impact de X sur l’utilisation est éliminé

totalement dès que les trames perdues ne sont pas retransmises et toute perte d’une unité

de transmission cause la perte du paquet entier. Dans ce cas on peut présenter l’impact de

K seul où X n’a aucune influence sur la performance.

X 1 2 5 10 K/N δ

K 100 50 20 10

10/11 0N 110 55 20 10

α 0.9091 0.9091 0.9030 0.8631

48

TABLEAU I.V.2 : Optimisation de α, Modèle hybride.

TABLEAU IV.3 : Optimisation de α, FEC seule.


Le Tableau IV.3 montre comment α diminue lorsque K diminue. Cette

décroissance est plus forte que celle dans le cas où δ = 5 (TABLEAU IV.2).

IV.4 Optimisation : On désigne par optimisation le calcul des valeurs des paramètres du modèle qui

servent à maximiser l’utilisation du lien sans fil dans un scénario donné. Bien sûr on ne

peut pas traiter tous les scénarios existants dans le monde. On présente dans ce

paragraphe un exemple d’optimisation des certains scénarios tout en mettant en relief la

variation des valeurs optimales des différents paramètres du modèle, une variation qui

vérifie parfaitement les raisonnements déjà faits dans ce chapitre et le chapitre précédent.

Ces scénarios sont pris de la même topologie déjà étudiée dans le Chapitre III où on a 10

sources TCP qui émettent simultanément.

Chaque source correspond à une connexion TCP et elle est liée à l’entrée du lien

sans fil via un lien filaire de 10 Mbps de bande passante et de 20 ms comme délai de

propagation. De même la destination est liée à la sortie du lien sans fil par une connexion

similaire. Le lien sans fil est caractérisé par une bande passante B = 2 Mbps, par un délai

de propagation D et un taux de pertes des unités de transmission p.

D [ms] P δ X K N Utilisation

20 1.E-04 4 100 1 1 99.99

20 5.E-04 4 100 1 1 99.95

20 1.E-03 5 100 1 1 99.9

20 5.E-03 5 100 1 1 99.5

20 1.E-02 5 100 1 1 99

40 1.E-04 4 100 1 1 99.99

40 5.E-04 4 100 1 1 99.95

40 1.E-03 5 100 1 1 99.9

40 5.E-03 5 100 1 1 99.5

49

Figure IV.5 : Topologie du réseau.


40 1.E-02 5 100 1 1 99

60 1.E-04 4 100 1 1 99.99

60 5.E-04 4 100 1 1 99.95

60 1.E-03 5 100 1 1 99.9

60 5.E-03 5 100 1 1 99.5

60 1.E-02 5 100 1 1 99

80 1.E-04 4 100 1 1 99.99

80 5.E-04 4 100 1 1 99.95

80 1.E-03 5 100 1 1 99.9

80 5.E-03 5 100 1 1 99.5

80 1.E-02 5 100 1 1 99

100 1.E-04 4 100 1 1 99.99

100 5.E-04 4 100 1 1 99.95

100 1.E-03 5 100 1 1 99.9

100 5.E-03 5 100 1 1 99.5

100 1.E-02 5 100 1 1 99

120 1.E-04 4 100 1 1 99.99

120 5.E-04 4 100 1 1 99.95

120 1.E-03 5 100 1 1 99.9

120 5.E-03 5 100 1 1 99.5

120 1.E-02 5 100 1 1 99

140 1.E-04 4 100 1 1 99.99

140 5.E-04 4 100 1 1 99.95

140 1.E-03 5 100 1 1 99.9

140 5.E-03 5 100 1 1 99.5

140 1.E-02 5 100 1 1 99

160 1.E-04 4 100 1 1 99.99

160 5.E-04 4 100 1 1 99.95

160 1.E-03 5 100 1 1 99.9

160 5.E-03 5 100 1 1 99.5

160 1.E-02 5 100 1 1 99

180 1.E-04 4 100 1 1 99.99

180 5.E-04 4 100 1 1 99.95

180 1.E-03 5 100 1 1 99.9

180 5.E-03 5 100 1 1 99.5

180 1.E-02 5 100 1 1 99

200 1.E-04 4 100 1 1 99.99

200 5.E-04 4 100 1 1 99.95

200 1.E-03 5 100 1 1 99.9

50


200 5.E-03 5 100 1 1 99.5

200 1.E-02 5 100 1 1 99

Le TABLEAU IV.4, montre les résultats d’optimisation, chaque entrée du tableau

présente les valeurs optimales des paramètres δ, X, K et N, et la valeur optimale de

l’utilisation obtenue, correspondantes à un couple (D, p) donné. D prend les valeurs

suivantes {20, 40, 60, …, 200} ms, p appartient à {10-4, 5*10-4, 10-3, 5*10-3, 10-2} et S est

fixé à 100 unités de transmission. Pour chaque couple (D, p) on a calculé l’utilisation du

lien sans fil pour chaque combinaison des paramètres δ, X, K et N et on a relevé leurs

valeurs qui maximisent l’utilisation.

En l’absence de FEC (K = N)

X 1 2 4 5 10 20 25 50 100

K 100 50 25 20 10 5 4 2 1

δ 0…5 0…5 0…5 0…5 0…5 0…5 0…5 0…5 0…5

En présence de FEC

X 1 2 5 10

K 100 50 20 10

N

101

.

.

110

51

.

.

55

21

2211

δ 0…5 0…5 0…5 0…5

Le TABLEAU IV.5 donne toutes les combinaisons calculées pour un couple (D,

p) donné. Dans toutes ces combinaisons, le rapport K/N varie entre 1 et 10/11.

Dans le chapitre précédent, on a vu que l’utilité de FEC apparaît dans le cas

extrême, grand délai et taux de pertes élevé, et dans les autres cas, aucune utilisation de

FEC va affaiblir l’utilisation du lien sans fil depuis qu’elle consomme une partie de la

bande passante pour ses informations redondantes. Après on a vu dans ce chapitre que la

51

TABLEAU IV.4 : Résultats de l’optimisation numérique, 10 connexions.

TABLEAU IV.5 : Combinaisons des paramètres pour lesquels l’utilisation est calculée.


capacité de ARQ-SR augmente avec X ; en augmentant X α s’accroît. Ce raisonnement

est bien vérifié dans le TABLEAU IV.4. Il est clair qu’en prenant X très grande, X = 100

trames et K = 1 unité de transmission c.à.d. chaque trame ARQ contient une seule unité

de transmission, la capacité de ARQ-SR à recouvrir les pertes augmente et aucune utilité

de FEC n’apparaît même dans le cas le plus délicat où p = 10 -2 et D = 200 ms. Notons

qu’on a besoin d’une grande valeur de δ, ses valeurs optimales varient entre 4 et 5, 4

signifie qu’il est suffisant de prendre δ égale à 4 pour optimiser l’utilisation et en

augmentant δ au-delà de ce point l’utilisation reste la même.

On a répété les même calculs, mais cette fois pour une connexion TCP

accaparante le lien sans fil pour son trafic, pour aboutir enfin aux mêmes résultats trouvés

pour 10 connexions. Les résultats sont portés par le Tableau IV.6 :

D [ms] P δ X K N Utilisation

200 0.01 5 100 1 1 99

Pour vérifier les résultats de l’optimisation numérique, on a refait quelques

simulations des transferts FTP de longues durées, de 2000 s. Les scénarios simulés

correspondent aux cas de grand délai ; D = 200 ms, et un taux de perte égale à 10 -2. on a

obtenu :

D [ms] p δ X K N Utilisation

200 ms 0.01 5 100 1 1 97.81389

200 ms 0.01 5 1 100 102 89.04595

Dans le Tableau IV.7, on présente quelques résultats des simulations tournées

pour dix connexions. On a gardé S égale à 1500 octets mais elle est, comme le cas des

calculs numériques, divisée en 100 unités de transmission LL. Les paramètres des

scénarios simulés sont indiqués dans le même tableau (Tableau IV.7). Ces résultats

vérifient parfaitement les résultats du modèle analytique. Avec ARQ-SR seule et en

mettant X égale à 100 trames par paquet, la valeur maximale qu’on peut donner dans ce

cas à X, l’utilisation atteinte est de 97.81389 %. En combinant la FEC avec ARQ-SR on a

obtenu une utilisation de 89.04595 % pour une K maximale, K = 100, et un taux de FEC

égale à 100/102. il est clair qu’en augmentant N au-delà de 102, on aura un rapport K/N

52

TABLEAU IV.6 : Résultats de l’optimisation numérique, une connexion.

TABLEAU IV.7 : Résultats des simulations, 10 connexions.


inférieur que 97.81389 %, l’utilisation achevée par ARQ-SR seule. Ainsi ce n’est pas la

peine de continuer les simulations en augmentant N. dans ce scénario, maximiser X

augmente la capacité de ARQ_SR à recouvrir les erreurs plus que maximiser K le fait

pour FEC malgré le grand délai et le taux de pertes élevé.

De tout ce paragraphe, on peut tirer qu’il faut maximiser le nombre des unités

de transmission par paquet afin d’aboutir à la meilleure performance quel que soit le

scénario et le nombre des connexions.

Pour finir, tous ces calculs sont effectués par un programme matlab qui a assuré le

balayage des différents paramètres, le calcul de l’utilisation et l’extraction des valeurs

optimales. L’exécution de ce programme a pris une trentaine d’heures. Si on veut faire

cette optimisation manuellement, on a besoin d’une trentaine de jours pour obtenir tous

ces résultats.

IV.5 Généralisation des résultats d’optimisation : Puisque le throughput de TCP est une fonction croissante de δ, il est très facile de

conclure que la meilleure performance est réalisée pour une valeur de δ très élevée. On

prend quoiqu’on sache que ceci ne peut pas être faisable dans la pratique (à un

moment donné on doit s’arrêter la retransmission d’une trame). Quand , le lien sans

fil est entièrement utilisé et l’utilsation du lien sans fil dans (Eq. II.2) est égale à

,

avec PT donné en (Eq. II.4) ; On se rappelle que PT est la probabilité qu'une trame soit

perdue, elle est fonction seulement du taux d'erreur, taille de la trame et la quantité de

FEC. Le throughput d'une connexion TCP, R, ne figure pas dans cette expression de

l’utilisation du lien sans fil. On se débarrasse de R puisqu'on l'avère une fonction

croissante de δ. Cependant l'expression de R est nécessaire lors de l’optimisation de la

quantité de FEC pour une petite valeur du δ, puisque dans ce cas le lien sans fil ne sera

pas toujours entièrement utilisé et la limite C*R dans l'expression de l’utilisation (Eq.

II.2) jouera un rôle.

Le problème revient alors à maximiser le terme qu’on dénote par .

En l’absence de FEC, est égale à . En ajoutant de FEC, augmente jusqu'à

53

(IV.3)

(IV.4)


son maximum, puis elle diminue et converge vers K/N pour des grandes valeurs de N

(c.à.d. PT tend vers zéro). La quantité optimale de FEC est celle qui maximise . Ainsi

Pour K = 10, on trace dans la Figure IV.6 pour différentes valeurs de p en

fonction de la quantité de FEC. est évaluée en %. On voit nettement que pour chaque

valeur de p, il y a une quantité optimale de FEC à ajouter. Pour des taux de pertes bas et

modérés, cette quantité optimale de FEC est près de zéro. Pour des taux de pertes élevés,

elle est non-négligeable. Par exemple pour p = 0.25, on a besoin de 6 unités de

redondance pour achever la meilleure utilisation, qui correspond à un taux de FEC égal à

10/16.

Une autre conclusion qu’on peut tirer de l’expression de , est que la

performance de ARQ-SR seule est une fonction décroissante de K. En effet, quand K

augmente, c.-à-d. les trames deviennent plus grandes, la valeur de pour N = K tend

vers zéro. C'est logique puisque les grandes trames sont plus sensibles aux pertes d'une

part, et d'autre part la retransmission des grandes trames n'est pas efficace. Ces résultats

sont illustrés dans la Figure IV.7 où est tracée en fonction du rapport N/K. On a 5

54

Figure IV.6 : Optimisation de pour plusieurs valeurs de p.

Figure IV.7 : Optimisation de pour plusieurs valeurs de K.


courbes correspondantes à 5 valeurs de K, K = 1, 2, 5, 25, 100. p est mis à 0.25. L’axe

des ordonnées présente les valeurs de lorsque ARQ-SR est utilisée seule pour

recouvrir les pertes. En ce qui concerne la quantité de FEC nécessaire pour optimiser la

performance, nos analyses ont montré qu’elle est presque indépendante de la taille des

trames LL, elle ne dépend que de p. Cependant, augmenter K est nécessaire pour achever

une meilleure utilisation, ceci est bien vérifié dans la Figure IV.7. Enfin, pour K = 1,

ARQ-SR seule a pu réaliser une utilisation de 75 %, ce qui est égale à (1 - p), tandis

qu’elle est de 65 % (égale à K/N) pour K = 100 en présence de FEC.Pour terminer ce paragraphe, on présente quelques résultats de

simulation qui vérifient parfaitement l’analyse effectué.

10 connexions TCP

p D δ X K N Utilisation

0.25 100ms 5 100 1 1 26.25731

0.25 100ms 10 100 1 1 74.10431

0.25 100ms 5 1 100 150 65.9469

0.25 100ms 5 10 10 15 56.56213

Le Tableau IV.8 montre la nécessité d’un δ très élevé, pour δ = 5 l’utilisation est

de 26 % (1ère entrée du tableau) et elle est de 74 % pour δ = 10 (2ème entrée du tableau). En

présence de FEC, l’utilisation est augmenté de 56 % pour K = 10 à 66 % pour K = 100

pour le même taux de FEC, K/N = 2/3. De nouveau ARQ-SR a montré sa supériorité sur

FEC pour des connexions TCP de longues durées, dans sa meilleure condition du travail

où K est le plus petit, K = 1.

IV.6 Conclusions : On a pu diviser les équations du modèle analytique FEC/ARQ-SR en deux

parties. La première partie contient les équations rigoureuses qui n’impliquent aucune

approximation. Ce sont les expressions de α, PT, PF, P et RTT en l’absence de ARQ-SR.

La résolution de ces équations a donné les mêmes résultats obtenus par simulation. La

deuxième partie, qui englobe le reste des expressions, contient le problème de

reséquencement des paquets à la sortie du lien sans fil, ce problème qui est bien étudié

dans [27]. Pour qu’on puisse le résoudre on a essayé deux approximations qui sont

55

Tableau IV.8 : Optimisation, résultats des simulations.


apparues complémentaires. La première considère que l’arrivée des paquets à l’entrée du

lien sans fil est poissoniènne. Elle donne des valeurs exactes quand l’utilisation est

inférieure à 40%. La deuxième traite le problème de reséquencement comme si l’arrivée

des paquets était déterministe. Elle s’avère adaptée pour des valeurs élevées de

l’utilisation.

Tandis qu’à l’optimisation du modèle, on a considéré l’impact des paramètres X

et K sur la performance. Pour l’améliorer on a besoin des grandes valeurs de X et de K,

mais ces derniers sont inversement proportionnels pour une S = cte. Les résultats

numériques ont montré qu’en présence de FEC, l’augmentation de K est plus importante

que l’augmentation de X. Mais, l’utilisation achevée par ARQ-SR seule avec X maximale

est supérieure que celle obtenue en présence de FEC. Les résultats de l’optimisation ont

confirmé tous les raisonnements faits.

Etant donné que l’utilisation de la FEC pour toutes les trames ARQ consomme

une partie de la bande passante, une proposition consiste à appliquer la FEC seulement

sur les trames retransmises. L’étude de ce nouveau modèle hybride utilisant la FEC pour

protéger seulement les retransmissions ARQ-SR sera l’objectif du chapitre suivant.

56

V

ARQ-Protégée-Par-FEC et FEC/ARQ-Stop&Wait

C

H

A

P

I

T

R

E

Chapitre V : ARQ-Protégée-Par-FEC et FEC/ARQ-

Stop&Wait

V.1 Introduction : Pour améliorer la performance de TCP sur les liens présentants des pertes de non-

congestion, plusieurs méthodes de recouvrement des erreurs ont été proposées. Dans les

chapitres qui précédent on a étudié jusqu’au fond le modèle hybride FEC/ARQ-SR. Etant

donné que FEC, appliquée à la totalité des trames ARQ, consomme une partie de la

bande passante pour ses informations supplémentaires qu’elle ajoute, un autre modèle

hybride consiste à l’utiliser seulement pour protéger les retransmissions ARQ-SR. On

l’appelle modèle hybride ARQ-SR-protegée-Par-FEC.

Ce chapitre porte sur l’étude de ce modèle tout en le comparant avec FEC/ARQ-

SR et il se termine par une comparaison rapide entre les performances des deux modèles

hybrides FEC/ARQ-SR et FEC/ARQ-Stop&Wait, une comparaison qui apprécie

l’utilisation de FEC/ARQ-SR avec le reséquencement des paquets.

V.2 Choix des mécanismes du modèle : ARQ-SR a montré une efficacité dans le recouvrement des erreurs (Chapitre III

et IV) en assurant une livraison en ordre des paquets à IP. Contrairement à FEC, il ne

consomme pas de la bande passante que lors de l’apparition d’une perte. Il adopte la

retransmission locale des trames LL perdues. Ainsi il augmente excessivement le délai

aller-retour (RTT) des paquets TCP, une chose nuisible pour TCP dès que son débit est

inversement proportionnel à la valeur moyenne de RTT [8], [14], (Eq. II.1). Pour aider

ARQ-SR, une idée est d’appliquer FEC seulement sur les retransmissions ARQ-SR en

essayant de limiter le nombre des retransmissions nécessaires d’une trame LL perdue. Le

but est de minimiser le délai aller-retour d’un paquet TCP.

58

Chapitre V : ARQ-Protégée-Par-FEC et FEC/ARQ-Stop&Wait

V.3 Modèle : Ce modèle, ARQ-SR-Protégée-Par-FEC, est semblable à l’ancien hybride

FEC/ARQ-SR à la seule différence que FEC n’est pas appliqué maintenant que sur les

trames retransmises. Pour garder l’analogie entre les deux hybrides, on utilisera les

mêmes notations que pour FEC/ARQ-SR.

Figure V.1 illustre cette différence : Une trame transmise pour la première fois ne

contient que K unités LL. Si elle est perdue, on la retransmet en y appliquant la FEC, par

suite elle contiendra en plus N – K unités redondantes, . Les mêmes choses dites

dans Paragraphe II.3 au sujet du reséquencement des paquets, des ACKs ARQ et TCP,

la priorité des retransmissions, le processus de pertes, etc., sont répétées ici.

V.4 Simulateur : Le code ajouté au simulateur des réseaux NS-2 pour qu’il puisse supporter le

modèle hybride FEC/AR-SR ne peut pas simuler le nouvel hybride ARQ-Protégée-Par-

FEC qui fait la distinction entre transmissions originales des trames et leurs

retransmissions pour l’application de FEC. Pour cela, on a écrit un autre code dans NS-2

pour le simuler. Cette implémentation est semblable à celle du premier hybride : on a la

même modélisation du lien sans fil, touts les paramètres sont accessibles à travers OTCL

et ils peuvent être initialisés à travers le script « .tcl » à exécuter pour lancer une

simulation. Le même exemple présenté dans le Paragraphe III.3 peut être utilisé ici.

De même, le modèle est seulement appliqué au lien sans fil, et il est transparent au

reste du réseau même aux hôtes TCP. Dans tous les scénarios simulés, K est fixé à 10, X

à 6 et la taille des unités LL (link-level) à 25 octets. Les paquets TCP sont alors de taille

constante égale à 1500 octets (MTU d'Ethernet). Chaque simulation tournée a duré 2000

59

Figure V.1: Modèle ARQ-SR-Protégée-Par-FEC.


secondes. Cette durée relativement longue est nécessaire pour absorber la phase Slow

Start initiale du TCP.

V.5 Scénarios des simulations et résultats : Dans cette section, nous présentons comment l'utilisation du lien sans fil change

en fonction des divers paramètres de FEC et de ARQ-SR. Dix connexions TCP de

longues durées croisent le lien sans fil dans le même sens. Nous avons considéré

plusieurs scénarios qui sont dérivés de la topologie de réseau tracée dans la Figure V.2.

Comme la figure montre, il y a 10 sources TCP qui transmettent des données FTP

simultanément et sans interruption vers la même destination. Chaque source correspond à

une seule connexion TCP. Les sources adoptent la version NewReno du TCP. Les

sources et la destination sont reliées au lien sans fil par l'intermédiaire des liens filaires de

10 Mbps ayant un délai de propagation allée simple égale à 20 ms. la bande passante B

du lien sans fil est de 2 Mbps, son délai D change entre 20 ms et 200 ms selon le scénario

étudié. Les valeurs données à D modélisent différents types de liens sans fil s'étendant

des liens terrestres aux liens satellitaire. Les unités de transmission sont corrompu dans

le lien sans fil avec une probabilité p, avec p varie entre 10-4 et 10-2 ce qui correspond à P

(taux de perte des paquets TCP) s'étendant de 0.0060 à 0.4528, voir (Eq. V.2) dans

Paragraphe V.7.1.

La destination utilise la fonctionnalité « delayed ACK » de TCP [31]. Pour éviter

n'importe quelle limitation du trafic due à d'autres raisons que les erreurs dans le lien sans

fil, nous avons pris les mesures suivantes:

Les liens filaires sont complètement fiables.

La taille de la fenêtre négociée de TCP est très grande, jusqu'à 2000 paquets.

Les « buffers » dans les routeurs du réseau sont très grands, ils peuvent stocker

jusqu'à 500 paquets.

60

Figure V.2 : Topologie du réseau.


Le buffer utilisé pour le reséquencement des paquets à la sortie du lien sans fil est très

grand.

Dans ces conditions, il est clair que le lien sans fil est le seul goulot sur le chemin

des connexions TCP. Les pertes de congestion n'apparaissent pas dans les routeurs du

réseau à moins que le lien sans fil soit entièrement utilisé. Nous voulons optimiser les

paramètres de FEC et de ARQ-SR dans cet arrangement. Le problème d'optimisation

n'est pas significatif quand les connexions TCP sont contraintes par les autres parties du

réseau.

La Figure V.3 présente l’utilisation du lien sans fil en fonction du paramètre de

FEC N qui représente la quantité de redondance ajoutée. Dans cette figure on trouve six

courbes qui correspondent aux six valeurs de δ, δ = 0, 1, 2, 3, 4, 5. D est fixé à 200 ms et

p est mis à 10-2. En regardant les valeurs de l’utilisation sur l’axe des ordonnées où N =

K, on examine l’effet de ARQ-AR seule. Elle a pu achever une utilisation d’environ 89 %

à partir de δ = 3. On trouve les mêmes résultats dans la Figure III.5. La ligne δ = 0

correspond à l’absence de ARQ-SR. Ainsi la FEC n’a aucune influence sur la

performance dès qu’il n’y a pas des retransmissions ARQ-SR pour les protéger. Pour

cela, dans ce cas extrême, grand délai et p élevé, on a une utilisation proche de zéro et

elle est constante quel que soit N. En utilisant la FEC, on observe une amélioration

négligeable dans la performance, mais ce qui est clair est que FEC a pu diminuer la

valeur de δ nécessaire pour optimiser l’utilisation de 3 à 1 dans ce cas le plus délicat. En

augmentant N au-delà de 11, on constate une décroissance de l’utilisation. Ceci est dû au

fait que la FEC consomme une partie de la bande passante pour ses informations

supplémentaires. Etant donné que ces redondantes sont ajoutées seulement aux trames

retransmises, cette décroissance est plus lente que celle trouvée dans le modèle

61

Figure V.3 : Utilisation du lien sans fil, p = 10-2, D = 200ms.


FEC/ARQ-SR où la FEC est appliquée à la totalité des trames. Notons que la valeur

optimale de l’utilisation obtenue pour cet hybride est inférieure que celle obtenue pour

l’ancien hybride.

En diminuant p, l’utilité de FEC diminue, une chose intuitive et vérifiée dans les

chapitres précédents. La Figure V.4 montre l’utilisation en fonction de N, elle est prise

pour D = 200 ms et p = 10-3. Dans ce cas, l’utilisation optimale est obtenue pour N = K à

partir de δ = 1. L’utilisation de FEC a diminué l’utilisation mais cette fois elle décroît

plus lentement que lorsque p =10-2. C’est prévisible parce que le nombre de trames

retransmises diminue lorsque p diminue et de même pour la partie de la bande passante

absorbée par FEC. Pour δ = 0, il est clair que l’utilisation est constante en fonction de N.

V.6 Etude analytique : Nous complétons notre étude en modélisant analytiquement la performance de

TCP sur le lien sans fil disposant du mécanisme de recouvrement d’erreur, ARQ-SR-

protégée-Par-FEC, au niveau liaison. Notre analyse est basée sur le modèle décrit dans le

Paragraphe V.3. Nous voulons calculer l'utilisation du lien sans fil en fonction des

paramètres de notre modèle : C, B, D, p, X, K, N, δ, etc... Puis, nous résolvons ce modèle

et nous comparons sa performance à nos résultats de simulation. L'avantage d'un modèle

analytique est qu'il laisse trouver directement le réglage optimal de ARQ-SR-Protégée-

Par-FEC à réaliser pour un scénario donné, plutôt que d'effectuer des longues

simulations. Nous faisons ici les mêmes hypothèses qu’on peut trouver dans la définition

de l’hybride FEC/ARQ-SR. Les paquets correctement reçus à la sortie du canal sans fil

sont reséquencés avant d'être délivré à leur destination. Nous adoptons l'expression du

62

Figure V.4 : Utilisation du lien sans fil, p = 10-3, D = 200ms.


Throughput d'une connexion TCP de longue durée donnée par (Eq. II.1) et nous avons la

même formule de l'utilisation U que dans (Eq. II.2) :

V.7 Analyse : L'utilisation U est une fonction de trois quantités, de A, RTT moyen, de P, le taux

de perte des paquets, et de α, le coefficient qui présente la partie de la bande passante du

lien qui est utilisée pour la transmission de l'information utile en en enlevant la partie

consommée par FEC et par les retransmissions de ARQ-SR. Une fois ces quantités sont

calculées, on peut les insérer dans (Eq. V.1) pour obtenir l'utilisation.

V.7.1 Calcul du taux de pertes des paquets : Un paquet TCP est perdu si un ou plus de ses trames LL sont perdues. Soit PF le

taux de perte des trames. Dans nos hypothèses, les trames sont perdues indépendamment

les unes des autres. Par conséquent, la probabilité P qu’un paquet TCP sera perdu est :

On calcule maintenant la probabilité qu'une trame est perdue. Ceci exige, en plus

de la perte de la transmission originale, l'échec des δ retransmissions. On sait qu’une

transmission originale ne contient pas des unités LL de redondance qu’on trouve dans les

retransmissions. Ainsi, leurs probabilités d’echec sont différentes. Soit PT1 la probabilité

de perte d’une trame originale et PT2 celle d’une trame retransmise, on a :

Par suite une trame est considérée perdue avec la probabilité :

En insérant (Eq. V.3) et (Eq. V.4) dans (Eq. V.5), après dans (Eq. V.2), on obtient

la probabilité qu’un paquet TCP soit perdu.

V.7.2 Calcul de α : On se rappelle que ce coefficient indique la partie de la bande passante du lien

sans fil gaspillée sur FEC et sur les retransmissions de ARQ-SR. Soit λ le taux d’arrivée des

paquets à l’entrée du lien sans fil. Alors :

63

(V.1)

(V.2)

(V.3)

(V.5)

(V.4)

(V.6)


Pour calculer λ, considérons la quantité moyenne des ressources consommées par un

paquet TCP :

Ainsi, à la pleine utilization du lien on peut écrire :

Ce qui donne :

Finalement, on obtient :

V.8 Vérification du modèle et optimisation : Jusqu’à maintenant on a calculé les quantités P et α. Il nous reste, selon nos

hypothèses, à calculer la valeur moyenne du délai aller-retour pour aboutir enfin du

compte à calculer le throughput des connexions TCP. Lorsque le lien sans fil est saturé,

l’utilisation doit être égale à α. Et comme on a vu dans le Chapitre IV, maximiser α

équivalent à optimiser le modèle, ce qui a été bien validé par simulation. Pour cela, on a

décidé de vérifier l’expression de α et de l’optimiser avant de compléter la modélisation

analytique du modèle. Si les résultats obtenus sont mieux que ceux atteints pour

FEC/ARQ-SR, on complète la modélisation, sinon, alors ce n’est pas la peine de le faire

dès que FEC/ARQ-SR s’avère plus performant.

V.8.1 Vérification : Pour résoudre les équations mises pour ce modèle on a procédé de la même

manière que pour l’ancien hybride. Toutes les expressions sont implémentées en matlab

afin d’être résolues numériquement.

64

(V.7)

(V.8)

(V.9)

(V.10)


Figures V.5 et V.6 montre α en fonction de N. Figure V.5 correspond à p = 10-2 et

celle Figure V.6 à p = 10-3. Dans les deux figures on a K = 10, X = 6 et δ = 5. en les

comparant avec les Figures V.3 et V.4 on trouve que l’expression de α est parfaitement

vérifiée, de même pour les autres expressions de probabilités. Ce qui permet de passer à

la phase d’optimisation.

V.8.2 OPTIMISATION : Dans le modèle ARQ-SR-Protégée-Par-FEC, c’est ARQ-SR qui prend l’initiative

pour recouvrir les pertes tandis que la FEC vient en deuxième lieu et elle n’est appliquée

qu’à une petite proportion de la totalité des trames ARQ-SR. Ainsi, il est intuitif

qu’améliorer les conditions de fonctionnement de ARQ-SR est plus avantageux

qu’améliorer celle de FEC, ce qui est vérifié par nos calculs présentés après. Notons que

la meilleure performance de ARQ-SR est achevée en maximisant X.

X 1 2 5 10 20 50 100

K 100 50 20 10 5 2 1

N 101 51 21 11 6 3 2

65

Figure V.5 : Modèle analytique, α en (%), p = 10-2.

Figure V.6 : Modèle analytique, α en (%), p = 10-3.


.

.

110

.

.

55

22

δ 0…5 0…5 0…5 0…5 0…5 0…5 0…5

L’optimisation est réalisée en faisant le balayage des paramètres K, X, N et δ

pour un taux de perte donné. Pour chaque combinaison on a calculé α correspondante.

Enfin on a tiré les valeurs qui la maximisent. Tableau V.1 montre toutes les

combinaisons effectuées. Un paquet est constitué de 100 unités de transmission. Ainsi K

et X varie de sorte que K*X = S = 100 unités.

p δ X K N α

1.E-04 3 100 1 2 0.9999

5.E-04 3 100 1 2 0.9993

1.E-03 4 100 1 2 0.9985

5.E-03 5 100 1 2 0.9925

1.E-02 5 100 1 2 0.9851

Tableau V.2 contient les résultats obtenus. Il est clair que α maximale est achevée

en maximisant X, X = 100, malgré un taux de FEC = égal à 1/2, c.à.d. la quantité de

redondance ajoutée égale la quantité de l’information originale. En comparant les valeurs

de α dans le Tableau V.2 avec celles de l’utilisation obtenues pour FEC/ARQ-SR

(Tableau IV.4), ce dernier s’avère mieux dès qu’il a pu donner une meilleure utilisation

du lien sans fil.

10 CONNEXIONS D [ms] p δ X K N Utilisation

ARQ-SR 200 ms 0.01 5 100 1 1 97.8

ARQ-SR 100 ms 0.25 10 100 1 1 74

ARQ-SR-protégée 200 ms 0.01 5 100 1 2 96.8

ARQ-SR-protégée 100 ms 0.25 10 100 1 2 69



66

Tableau V.3 : comparaisons des résultats des simulations des deux hybrides

Tableau V.2 : Optimisation de α.

Tableau V.1 : Combinaisons des paramètres pour lesquels α est calculée.


Les simulations ont vérifié les calculs faits pour α. Leurs résultats sont portés dans

le Tableau V.3 où on voit nettement l’avantage de ARQ-SR seule. Il nous semble que

nos calculs sont suffisants pour affirmer la supériorité du premier hybride en terme

d’utilisation maximale du lien sans fil. Ainsi, on n’a pas complété la modélisation

analytique de ARQ-SR-Protégée-Par-FEC. Cependant, ce dernier a pu diminuer

considérablement la valeur nécessaire de δ ce qui est en fait avantageux pour des trafic

sensibles au délai et à la variation du délai (jitter). Ainsi un des perspectives peut être

l’évaluation de la performance de ce modèle pour des tels trafics.

V.9 FEC/ARQ-Stop&Wait : Etant donné que ARQ-Stop&Wait est utilisé par le protocole I.EEE 802.11 pour

recouvrir les pertes sur les liens sans fil dans les réseaux locaux, on a voulu de voir si l’on

peut améliorer sa performance en le combinant avec FEC.

Ce troisième modèle hybride diffère de FEC/ARQ-SR par le fait que les trames ne

sont pas transmises back-to-back : Une trame ne peut pas être transmise que lors de la

réception d’un ACK de la trame précédente, c.à.d. elle est reçue correcte à la sortie du

lien sans fil, ou lors de la réception de (δ +1) NACKs de cette trame précédente, c.à.d.

elle est perdue. Une trame peut être rejetée avant qu’elle soit transmise si une des trames

précédentes qui correspondent au même paquet n’a pas pu être correctement transmise.

Comme dans FEC/ARQ-SR, FEC est appliquée à toutes les trames LL.

On a implémenté ce modèle dans le simulateur NS-2. Mais malheureusement, on

n’a pas eu le temps pour compléter son étude. Cependant, on a effectué quelques

simulations, en considérant la même topologie déjà étudiée, pour seulement comparer sa

performance avec FEC/ARQ-SR, on a obtenu :

p Delay X K δ N Utilisation

0.01 2ms 6 10 5 10 18.8

0.01 2ms 6 10 5 11 18.8

0.01 2ms 6 10 5 12 19.2

0.01 2ms 6 10 5 13 18.8

Le Tableau V.4 montre que le premier hybride est beaucoup plus performant que

le troisième, une chose attendue dès que les trames sont transmises back-to-back avec

67

Tableau V.4 : Résultats des simulations de FEC/ARQ-SR-Stop&Wait.


ARQ-SR, mais ce n’est pas le cas avec ARQ-Stop&Wait. En effet, l’intervalle de temps

entre le début de transmission d’une trame et la réception de son acquittement positif ou

négatif est :

N est la taille d’une trame, B la bande passante du canal et D son délai de

propagation (on a négligé le temps de transmission des ACKs ARQ). Pour D très petit

devant N/B, autrement dit, pour un petit produit délai-bande passante, T est presque égal

à N/B et les trames sont comme si elles étaient transmises back-to-back. Considérons le tableau

suivant :

p D δ k n ord x utilisation

0.01 0.001ms 5 10 11 1 6 90.291150.01 0.001ms 5 10 10 1 6 90.22511

Le Tableau V.5 montre l’efficacité de FEC/ARQ-Stop&Wait pour des petits

produits délai-bande passante. L’utilisation est de 90 % pour un délai de 1 μs, ce qui

correspond à une distance émetteur-récepteur de 300 m. L’étude de cet hybride doit donc

se concentre sur des telles situations.

V.10 Conclusions : Le modèle ARQ-SR-Protégée-Par-FEC est proposé pour minimiser l’impact de

FEC sur la bande passante. L’étude de ce modèle a nécessité son implémentation dans

NS-2 et l’écriture de l’expression de α. Il a bien amélioré la performance de TCP. Les

résultats des simulations obtenus et les calculs effectués nous ont permis de conclure que

cet hybride ne peut pas achever une meilleure utilisation que ARQ-SR utilisée seule.

Tandis que pour le modèle FEC/ARQ-Stop&Wait, on l’a implémenté dans NS-2.

Mais l’étude n’a pas pu aboutir, c’était un problème de temps. Ce qui est sûr pour cet

hybride est que son efficacité n’apparaît que pour des petits produits délai-bande

passante.

68

Tableau V.5 : Résultats des simulations de FEC/ARQ-SR-Stop&Wait, petit produit délai*bande.

(V.11)

CONCLUSIONS GENERALES

Conclusions Générales

TCP considère toutes les pertes dans une fenêtre comme étant un indicateur de

congestion. Ainsi, si un paquet est perdu, sa fenêtre de congestion sera réduite et on aura

une chute dans son débit. Cette stratégie résulte en une pauvre performance de TCP sur

les liens présentant des pertes de non-congestion, un exemple typique est les liens sans

fil. Plusieurs solutions ont été proposées pour aider TCP.

L’objectif de ce stage était de valider et d’optimiser le modèle hybride FEC/ARQ-

SR. Ce modèle est appliqué au niveau de la couche liaison sur le lien sans fil. Le but est

de recouvrir les pertes de non-congestion d’une manière transparente par rapport à TCP

afin d’accroître son débit sur ce lien. L’utilisation de FEC seule augmente

spectaculairement le throughput de TCP tout en consommant une partie de la bande

passante pour ses informations redondantes. ARQ-SR seule améliore considérablement la

performance de TCP mais elle accroît le RTT des paquets TCP et on sait que son

throughput est inversement proportionnel à RTT. En combinant les deux mécanismes de

correction d’erreurs, on a besoin de moins de FEC pour le recouvrement des pertes. Et

l’impact de ARQ-SR sur le RTT diminue étant donné que le nombre de retransmission

nécessaire pour recouvrir une trame perdue est maintenant plus petit. En outre de cette

combinaison, le modèle hybride implémente à la sortie du lien sans fil un module pour

reséquencer les paquets avant de les délivrer à IP. Notons que le déséquencement des

paquets causé par ARQ-SR provoque la génération des ACKs dupliqués qui vont

constituer des fausses alarmes de congestion.

La validation du modèle est fait par simulation. On l’a implémenté dans le

simulateur NS-2. L’étude a porté sur l’utilisation du lien sans fil. Les résultats obtenus

ont démontré l’utilité de cet hybride, en particulier dans le cas extrême correspondant à

un grand délai de propagation pour le lien sans fil et un taux de perte élevé. Lorsque le

taux de perte ou le délai diminue, ARQ-SR seule s’avère mieux dès que FEC consomme

toujours de la bande passante tandis que ARQ-SR le fait seulement lors de l’apparition

des pertes. Notons que ces simulations sont tournées pour des connexions TCP de longue

70


durée pour absorber la phase de slow start initiale. En outre, les scénarios simulés son

conçus d’une manière à avoir le lien sans fil le seul goulot dans le réseau.

Après, on a modélisé analytiquement l’utilisation du lien sans fil en fonction des

paramètres du mécanisme FEC/ARQ-SR, des paramètres du lien sans fil, et du nombre de

connexions TCP. La modélisation a été effectuée à l’aide des techniques de la théorie des

probabilités et des processus stochastiques. Elle a permis l’obtention d’une expression

pour l’utilisation du lien sans fil. Cette expression a ensuite été résolue numériquement

par « matlab ». Malgré les difficultés rencontrées dans la modélisation et les

approximations faites, les résultats analytiques sont très proches de ceux obtenus dans les

simulations. L’optimisation du modèle est faite numériquement et elle est vérifiée

parfaitement par simulation. Un des résultats inattendus est que l’utilisation du lien sans

fil augmente toujours avec δ malgré l’accroissement excessif de RTT. Ainsi on a intérêt à

donner une grande valeur à δ. Un autre résultat étonnant est que ARQ-SR a montré sa

supériorité sur FEC dans le cas des connexions TCP de longue durée. En effet,

l’efficacité de ARQ-SR apparaît en minimisant la taille des trames. La meilleure

performance pour ARQ-SR seule est réalisée pour K = 1. Par contre, l’efficacité de FEC

réside pour des grandes trames, c’est pour cela que cet hybride a nécessité une valeur plus

grande de K. Ainsi, dans la meilleure condition de fonctionnement de ARQ-SR, c.à.d.

pour K = 1, elle a pu achever seule une utilisation de 75 % pour p = 0.25 et D = 100 ms.

En présence de FEC, on a mis K = 100 et on a obtenu une utilisation maximale de 65 %.

Généralement, ARQ-SR seule peut atteindre une utilisation très proche de (1 – p), tandis

qu’elle est majorée par K/N en présence de FEC.

Etant donné que FEC vole une partie de la bande passante pour ses informations

supplémentaires, une idée était de l’appliquer seulement sur les trames retransmises par

ARQ-SR. Ainsi on assure une protection des retransmissions ARQ, on diminue la

persistance de ARQ et par suite on affaiblit le RTT des paquets TCP. Ce modèle, qu’on a

appelé ARQ-SR-Protégée-Par-FEC, est bien étudié dans ce rapport. Après l’avoir

implémenté dans NS-2, on l’a simulé et on en a mis l’expression de α, le coefficient qui

indique la partie de la bande passante gaspillée par FEC et les retransmissions de ARQ.

Les résultats des simulations obtenus et les calculs effectués par matlab nous ont permis

de conclure que ce modèle ne peut pas réaliser une utilisation du lien sans fil supérieure à

celle achevée par ARQ-SR seule.

Comme dernière chose effectuée durant ce stage, on a essayé de voir la

performance d’un autre hybride qui groupe FEC et ARQ-Stop&Wait. On a inséré ce

71


modèle dans NS-2. Il est clair que ARQ-Stop&Wait ne tient pas que pour des petits

produits délai-bande passante. L’utilisation obtenue dans ce cas et pour ce dernier

hybride est de l’ordre de 90 %. Dans le cas contraire, grand produit délai-bande passante,

elle est d’environ de 19 %. Malheureusement, on n’a pas eu le temps pour compléter

l’étude de ce modèle et on s’est arrêté ici.

Notre travail peut être prolongé dans des différentes directions. Nous voulons

vérifier si nos conclusions tiennent dans le cas des courts transferts TCP et des erreurs de

transmission en « burst ». Une autre extension possible est d’étudier quel est le

mécanisme optimal de recouvrement d'erreur pour un trafic non-TCP sensible au délai,

comme voice and video streams. Prolonger le modèle analytique à ces scénarios est

également une direction pour une future recherche.

Au plan personnel, ce rapport montre la diversité des problèmes qu’on a été

confronté pendant ce travail : protocoles réseaux (TCP, liens sans fil, FEC, ARQ),

implémentation et simulation, modélisation. On a résolu ces problèmes en combinant la

recherche, l’informatique et la théorie des probabilités et des processus stochastiques.

L’implémentation des 3 modèles a nécessité une maîtrise des langages C++ et OTCL,

une base solide dans la programmation orientée objet et une forte compréhension de

l’hiérarchie des classes de NS-2. Le traitement des résultats des simulations s’est fait avec

les outils “AWK” et “gnuplot”. Et on n’oublie pas “matlab” qui nous a accompagnés

presque dans toutes les étapes de ce stage (modélisation, automatisation des simulations,

optimisation…). Le “background de ce travail était le système d’exploitation linux.

Ajoutons que c’étaient les deux premières publications pour moi : La première était dans

les proceedings du congrès international WiOpt’03 : Modeling and Optimization in

Mobile, Ad Hoc and Wireless Networks, Sophia Antipolis, France, Mars 2003. Elle est

titrée : Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SR For Wireless

Links and Long-Lived TCP traffic. La deuxième a contenu le modèle complet,

simulation, modélisation et optimisation, elle sera publiée dans le journal « Performance

Evaluation » sous le titre : Analysis of link-level hybrid FEC/ARQ-SR for wireless links

and long-lived TCP traffic.

En deux mots je peux dire que cette expérience professionnelle m’a permis une

richesse dans l’esprit recherche scientifique et d’approfondir davantage mes techniques.

72

ANNEXE

Annexe 1Calcul de

Par définition, Y est le plus grand indice des trames qui exigent le nombre

maximum des retransmissions. Y est une variable aléatoire qui prend des valeurs entières

de 1 à X. Nous nous concentrons ici sur le calcul de son espérance. Soit M le nombre

maximum des retransmissions que subissent les trames d’un paquet TCP :

.

Y est definie comme

Une remarque rapide est que s'il y a seulement une trame retransmise un nombre

maximum de fois, alors Y est uniformément distribuée sur [1, x], et sa moyenne est

simplement . Le problème est plus difficile quand plus qu'une trame sont

retransmises M fois.

On commence par le calcul de la distribution de Y. L'espérance de Y est connue

pour être égale à

.

On a,

.

Soit My égale à

.

En conditionnant sur la valeur de My, on peut écrire

74

Annexe 1

Pour k = 0, la probabilité est égale à 0. l’expression de est

donnée dans (Eq II.13). De même on sait que

.

Parsuite,

.

Pour simplifier les résultats, on dénote par Fk, Fk est égale à 0 pour k<0,

et à 1 pour . Alors,on obtient

.

On inserre cette expression dans l’expression de E[Y], ce qui donne

.

Il est simple de prouver que égal à

.

par suite

.

En appliquant l’inéquation de Jensen, E[Y] sera majorée par :

.

75

Annexe 2

Calcul de la valeur moyenne du délai de reséquencement dans le cas

d’un processus d’arrivées déterministes :

Supposons que les arrivées des paquets TCP sont régulièrement espacées de 1/λ .

Soit sn le temps pris par le paquet n pour traverser le lien sans fil, dans le cas où les

paquets sont délivrés sans reséquencement. soit an l’instant d’arrivée du paquet n. alors,

dans le cas où le reséquencement des paquets à la sortie du lien sans fil est activé,

l’instant où le paquet n quitte ce lien sera :

.

Le temps aller-retour du paquet n quand la livraison en ordre est activée est donc,

.

Soit . Alors, .

Nous nous concentrons sur le calcul de E[Z]. on a

,

et

.

Cela tient depuis que tous les sn sont iid. Si on suppose en outre que sn est

exponentiellement distribuée avec une moyenne de 1/μ , on peut écrire

.

En combinant cette expression avec Ai, la preuve sera terminée.

76

Annexe 3

FEC/SRQ-SR : Résultats des simulations.

77

10 connexions TCP

Annexe 3

78

Une connexion TCP seule

Annexe 4

FEC/ARQ-SR, résultats analytiques.

79

10 connexions TCP, arrivée Poissoniènne.

Annexe 4

80

une connexion TCP seule, arrivée Poissoniènne.

Annexe 4

81

10 connexions TCP, arrivée déterministe.

Annexe 4

.

82

Une connexion TCP seule, arrivée déterministe

Annexe 5

ARQ-SR-Protégée-Par-FEC, Simulations, 10 connexions TCP.

83

BIBLIOGRAPHIE

Bibliographie

[1] Marcin Michalak. Master of Science Thesis Computer Science, University Of Mining And Metallurgy Cracow, Faculty Of Electrical Engineering, Automatics,Computer Science And Electronics, Institute Of Computer Science June 2001

[2] Jing Zhu, Sumit Roy. Modeling TCP over Selective Repeat ARQ in Wireless Networks with Non-Neglectable Propagation Delay. Department of Electrical Engineering, University of Washington.

[3] P. Charalambos, V. S. Frost, and J. B. Evans, “Performance of TCP Extensions On Noisy High BDP Networks”, IEEE Communications Letters, Vol. 3 , No. 10, October, 1999.

[4] V. Jacobson, “Congestion avoidance and control”, ACM SIGCOMM, Aug. 1988.

[5] W. Stevens, “TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms”, RFC 2001, Jan. 1997.

[6] M. Allman, D. Glover, L. Sanchez, “Enhancing TCP Over Satellite Channels using Standard Mechanisms”, RFC 2488, Jan. 1999.

[7] Hari Balakrisme, Venkata N. Padmanabhan, Srinivasan Seshan and Randy H. Katz. A Comparison of Mechanism for Improving TCP Performance over Wireless Links. ACM SIGCOMM ’96, Stanford, CA, August 1996.

[8] C. Barakat, E. Altman, ”Bandwidth tradeoff between TCP and link-level FEC”, Computer Networks, vol. 39, no. 2, pp.133-150, Jun. 2002.

[9] S. Biaz, N. H. Vaidya, “Distinguishing Congestion Losses from Wireless Transmission Losses: A Negative Result”, International Conference on Computer Communications and Networks (IC3N), Oct. 1998.

[10] A. Bakre, B. R. Badrinath, “I-TCP: Indirect TCP for Mobile Hosts”, International Conference on Dis-tributed Computing Systems (ICDCS), May 1995.

[11] H. Chaskar, T. V. Lakshman, U. Madhow, “On the design of interfaces for TCP/IP over wireless”, IEEE MILCOM, Oct. 1996.

[12] S. Keshav. An Engineering Approach to Computer Networking: ATM Networks, The Internet, And The Telephone Network. AT&T Labs-Research.

85

Bibliographie

[13] T. Henderson, R.H. Katz, “Transport Protocols for Internet-Compatible Satellite Networks”, IEEE Journal on Selected Areas in Communications, vol. 17, no. 2, pp. 326-344, Feb. 1999.

[14] M. Mathis, J. Semke, J. Mahdavi, T. Ott, “The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm”, Computer Communication Review, vol. 27, no. 3, pp. 67-82, Jul. 1997.

[15] IEEE Transaction on Antennas and Propagation,Vols. AP-17, No. 3. May 1969; AP-20, No. 1, january 1974 and AP-31, No. 6, Part II, Novembre 1983.

[16] Webster’s Dictionary.

[17] A. Al Fawal. Mémoire de fin d’études. Conception et Réalisation de Réseaux d’Antennes pour les Mesures de Propagation et de Transmission Application aux Réseaux de Communication sans Fil UMTS, WLAN, WLL ET HIPERLAN/2. INSA-Rennes, Juin 2001.

[18] S. GALLIOU. Rapport de Stage : Etude et Validation de Méthodes Hautes Résolutions Bidimensionnelles pour la Determination des Directions d’Arrivées du Champ Radioelectrique. CENT - Juin 1999

[19] A. AFFANDI. Rapport de Thèse : Caractérisation et Modélisation de la Propagation à l’Interieur des Batiments dans les Bandes de 450 – 900 – 1800 – 2400 – 5800 MHz. INSA de Rennes – Mai 2000.

[20] M. TAJANI. Rapport de Thèse : Egalisation Adaptative de Multi-Trajet dans des Liaisons de Télémesure à Haut Débit. Ecole Doctorale Science pour l’Ingénieur de Nantes- Janvier 1996

[21] Réseau National de Recherche en Télécommunication – SIMPAAwww.RNRT 99 - Projet SIMPAA - SImulateur Matériel de Propagation pour les Antennes Adaptatives - N° 12.htm

[22] A. Chockalingam, M. Zorzi, R.R. Rao, “Performance of TCP on Wireless Fading Links with Memory”, IEEE ICC, Jun. 1998.

[23] A. Kumar, J. Holtzman, “Performance Analysis of Versions of TCP in a Local Network with a Mobile Radio Link”, Sadhana: Indian Academy of Sciences Proceedings in Engg. Sciences, Feb. 1998.

[24] C. Barakat, ”TCP modeling and validation”, IEEE Network, vol. 15, no. 3, pp. 38-47, May 2001.

[25] T.V. Lakshman, U. Madhow, “The performance of TCP/IP for networks with high bandwidth-delay products and random loss”, IEEE/ACM Transactions on Networking, vol. 5, no. 3, pp. 336-350, Jun. 1997.

[26] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, ”Modeling TCP Throughput: a Simple Model and its Empirical Valida-tion”, ACM SIGCOMM, Sep. 1998.

86

Bibliographie

[27] F. Baccelli, E. Gelenbe, B. Plateau, “An end-to-end approach to the resequencing problem”, Journal of the ACM, vol. 31, no. 3, pp. 474-485, July 1984.

[28] The LBNL Network Simulator, ns-2, http://www.isi.edu/nsnam/ns/

[29] URL:http://www.cs.dartmouth.edu/gnuplot_info.html

[30] URL:http://mucha.obspm.fr/~grouss/gnuplt/gnuplot.html (in french)

[31] J. Padhye, V. Firoiu, D. Towsley, J. Kurose, Modeling TCP throughput: a simple model and its empirical validation, ACM SIGCOMM, September 1998.

87

url:http://mucha.obspm.fr/~grouss/gnuplt/gnuplot.html

url:http://www.cs.dartmouth.edu/gnuplot_info.html

http://www.isi.edu/nsnam/ns/

Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SRFor Wireless Links and Long-Lived TCP traffic

Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SRFor Wireless Links and Long-Lived TCP traffic

Alaeddine Al Fawal* Chadi Barakat

PLANETE Project, INRIA Sophia Antipolis, France{Alaeddine.Al_Fawal, Chadi.Barakat}@sophia.inria.fr

Abstract: Since the TCP protocol uses the loss of packets as an indication of network congestion, its performance degrades over wireless links, which are characterized by a high bit error rate. Different solutions have been proposed to improve the performance of TCP over wireless links, the most promising one being the use of a hybrid model at the link-level combining FEC, ARQ-SR (Automatic Repeat Request with Selective Repeat), and an in-order delivery of packets to IP. The drawback of FEC is that it consumes some extra bandwidth to transmit the redundant information. ARQ-SR does not consume much bandwidth, its drawback is that it increases the round-trip time (RTT), which may deteriorate the performance of TCP, if not done appropriately. We study in this paper the performance of TCP over a wireless link implementing hybrid FEC/ARQ-SQ. The study is done by simulating long-lived TCP transfers with ns-2 over wireless links showing Bernoulli errors. We are motivated by how to tune link-level error recovery e.g. amount of FEC, persistency of ARQ, so as to maximize the performance of TCP. We provide simulation results for different physical characteristics of the wireless link (delay, error rate) and for different traffic loads.

1. IntroductionFor TCP, the loss of a packet is an indication that the network is congested. The

lost packet is retransmitted by the TCP source and the window is reduced in order to alleviate the congestion of the network. This strategy in the detection of congestion results in a poor performance of the protocol when packets are lost in the network for other reasons than congestion [1,4,5]. Transmission errors on a noisy link, typically a wireless link, form the main source for non-congestion losses. A TCP packet corrupted while crossing a noisy link is discarded before reaching the receiver, which results in an unnecessary window reduction at the TCP source. In the following, we will focus on transmission errors on wireless links and we will call the corrupted TCP packets non-congestion losses or link-level losses since they appear at a level below IP.

Many solutions have been proposed to improve the performance of TCP when operating on paths with non-congestion losses [1,4,5]. Some of these solutions consist in enhancing TCP with additional mechanisms to help it to recover from non-congestion losses without reducing its window (explicit loss notification [4], loss predictors [6], etc.). Other solutions, e.g. I-TCP [2], propose to shield the sender from these undesirable losses by splitting the TCP connection at the entry of the lossy part of the network, i.e. at the base station in the case of wireless networks. A special well-tuned transport protocol, e.g. STP [10], is then used over the lossy part. Although they improve the overall performance, these solutions break the end-to-end semantics of TCP. A packet is acknowledged before arriving at its final destination.

To preserve the end-to-end semantics of TCP, other promising solutions propose to correct errors at the wireless link level by using a combination of FEC (Forward Error Correction) and ARQ (Automatic Repeat Request) [1,4]. The drawback of FEC is that it consumes some extra bandwidth to transmit the redundant information. It has been shown in [3] that there is an optimal amount of redundancy to be added, above which 1 the performance of TCP degrades instead of improving, although this degradation is slower than the gain in performance we obtain when the first units of redundancy are added. ARQ does not consume much bandwidth, its drawback is that * This work has been done while the author was doing his DEA internship in the PLANETE research group at Sophia Antipolis.

89

it increases the round-trip time (RTT), which may deteriorate the performance of TCP, if not done appropriately. The throughput of TCP is known to be inversely proportional to the average round-trip time [14,16]. Another problem of ARQ is the interference with TCP timeout. TCP retransmission timer may expire while the lost packet is being retransmitted over the wireless link. FEC does not cause neither an increase in RTT nor an interference with TCP timeout [1]. For these reasons, FEC-alone has been recommended to be used over long delay wireless links as the satellite ones [1].

We study in this paper the performance of TCP over a wireless link implementing a link-level hybrid error correction model implementing FEC, ARQ-SR (ARQ Selective Repeat) and an in-order delivery of packets to IP. ARQ-SR is an efficient ARQ scheme that avoids the unnecessary retransmissions that we see with ARQ Go-Back-N. In contrast to ARQ Stop-Wait, ARQ-SR allows an efficient utilization of the available bandwidth, since many packets can be transmitted over the wireless link before receiving any acknowledgment. The main problem with ARQ-SR is that it desequences packets, hence a buffer is needed at the output of the wireless link for the purpose of resequencing packets and delivering them in-order to IP. Out-of-order packets are harmful for TCP since they result in duplicate ACKs, with the TCP source dividing its congestion window by two if three or more duplicate ACKs are received. The combination of FEC and ARQ-SR reduces the number of times we retransmit packets, which shortens the RTT and the resquencing delay in the buffer at the output of the wireless link. On the other hand, this combination reduces the bandwidth available to TCP, since FEC consists in sending redundant information in addition to TCP data. At the same time, this combination reduces the necessary amount of FEC to be used compared to the case when FEC alone is used for error correction. We are motivated in this study by how to tune the parameters of a link-level hybrid FEC/ARQ-SR model so as to maximize the performance of TCP. A typical example of parameters to tune is the amount of FEC and the maximum number of trials we allow ARQ-SR to do before deciding that the packet cannot be locally recovered, and that it has to be recovered by TCP on end-to-end basis.

Our study is done by simulating long-lived TCP transfers with ns-2 simulator [15] over wireless links showing Bernoulli non-congestion losses. For the purpose of the study, a hybrid FEC/ARQ-SR error correction model with in-order delivery has been implemented in ns-2. We have done simulations for different physical characteristics of the wireless link (delay, bandwidth, error rate) and for different traffic loads. For lack of space, we only present in this paper a summary of our simulation results. All our results have been validated by an analytical model based on stochastic processes.

We start by a description of the model, then we present the simulated scenarios. Sections 3 summarizes our results. We conclude the paper by some conclusions and perspectives on our future research.

2. ModelWe consider a wireless link where data are transmitted in link-level (LL) frames (Figure 1). We

denote by B the bandwidth of the wireless link, and by D its one-way propagation delay. As we see in Figure 1 , each LL frame is divided into K link-level transmission units. A LL transmission unit can be a bit, a byte, or any other data unit. To the K units of a LL frame, we add N - K redundant units that we obtain using a Reed-Solomon code. N is called the length of the code, K its dimension, and K/N its rate. We suppose that we have an erasure channel (the position of the error is known). A LL frame is decoded if we correctly receive K or more units of the frame at the output of the wireless link. A TCP packet that arrives at the input of the wireless link is divided into X frames. All TCP packets are of constant size S (MSS + TCP/IP header). Hence, S = X K transmission units. To be delivered to the destination, the X frames of a TCP packet have to be well received. If FEC does not succeed to decode one frame, the error recovery mechanism resorts to ARQ-SR for the retransmission of the frame. The retransmission will be done a maximum number of times, called the persistency of ARQ-SR. We denote this persistency by , = 0, 1, 2, … When trials are done and the frame did not get through the wireless link, ARQ-SR assumes that the frame cannot be locally recovered, and leaves for TCP the correction of the frame on end-to-end basis.

90

The ARQ-SR receiver at the output of the wireless link acknowledges each LL frame either with a positive ACK or a NACK. When a NACK is received at the input of the wireless link, the corresponding frame is directly retransmitted, and given priority over all other frames that have not yet been transmitted. One can imagine the use of a priority queue for retransmissions. The packets correctly received at the output of the wireless link are resequenced before being delivered to IP. An out-of-order delivery takes place only if a packet cannot be locally corrected, due to the failure of the retransmission of one of its frames. Note that packets are resequenced at the output of the wireless link on an aggregate basis, not on a flow basis. This simplifies the implementation of the error recovery mechanism and respects the principle of layering in the Internet.

Concerning errors over the wireless link, we model them using a Bernoulli process, where transmission units are lost independently of each other with probability p. The error process is only applied to data packets. ACKs of ARQ-SR and those of TCP are supposed to cross the wireless link without being dropped, given their small size. Usually, errors over wireless links are modeled by a Markov chain of two states [3,7,8,11,12]. We choose the Bernoulli process for its simplicity. The Bernoulli process is known to hold over fast fading channels (high speed users) [12] and when interleaving is used [4]. We are only interested in this paper by the impact of the average error rate. The impact of burstiness of errors will be the subject of a future research.

Our traffic is composed of C long-lived TCP connections crossing the wireless link in the same direction. The focus is on how to maximize the aggregate throughput of the C connections, and hence the utilization of the wireless link.

3. SimulationsWe implement our model for link-level FEC/ARQ-SR with in-order delivery into ns-2, the network

simulator developed at LBNL [15]. The model is only applied to the wireless link, and is transparent to the rest of the network and to TCP peers. Our simulations are divided into two parts. The first part focuses on the utilization of the wireless link in case of C = 10 concurrent TCP connections. The second part focuses on the throughput of one TCP connection using alone the wireless link for its transfer. In all studied scenarios, K is fixed to 10, X to 6 and the size of link-level units to 25 bytes. TCP packets are then of constant size equal to 1500 bytes (MTU of Ethernet). Simulations are run for 2000 seconds. This relatively long duration is necessary to absorb the initial slow start phase of TCP.

The values given to K and X are randomly chosen. Other values are possible. Our purpose is not to optimize these quantities, but rather to optimize the amount of FEC to be used and the persistency level d. We look for K and X as inputs of the problem rather than outputs. This reduces the number of parameters to optimize. Note that the optimization of K and X is also an interesting problem given the tradeoff it involves. We are studying this optimization problem with our analytical model. For instance, for constant packet sizes (constant S), the size of LL frames decreases when X increases, which decreases the probability that a LL frame is corrupted. This should improve the performance. However, when we increase X, K decreases, hence the number of redundant units per LL frame decreases, if we do not change the amount of FEC. It has been shown in [3] that this may deteriorate the performance since frames can now resist to less errors. The optimization problem becomes more interesting when we allow the packet size S to change. The packet size decides on the rate with which TCP increases its congestion window [3,16].

3.1First part: Link utilization

3.1.1 Simulation scenariosIn this section, we present how the utilization of the wireless link varies according

to the various parameters of FEC and ARQ-SR. Ten long-lived TCP connections cross

91

Figure 1 : The Hybrid Model FEC /

the wireless link in the same direction. We considered several scenarios that are derived from the network topology shown in Figure 2.

As Figure 2 shows, there are 10 TCP sources that transmit FTP data simultaneously and continuously to the same destination. Each source corresponds to one TCP connection. The sources use the NewReno version of TCP. The sources and destination are connected to the wireless link via 10 Mbps links having a one-way propagation delay equal to 20 ms. The bandwidth of the wireless link B is set to 2 Mbps, its delay D varies between 20 ms and 200 ms depending on the scenario. The values we give to D model different types of wireless links ranging from terrestrial links to satellite ones. Transmission units are lost (corrupted) over the wireless link with probability p, with the value of p ranging from 10-5 to 10-2.

The destination enables the Delay ACK functionality of TCP [16]. To avoid any limitation of traffic due to other reasons than errors in the wireless link, we have taken the following measures:

The wired links are completely reliable.The size of TCP advertised window is very large, up to 2000 packets.The buffers in network routers of are very large, they can store up to 500 packets.The buffer used for resequencing packets at the output of the wireless link is very large.

Under these conditions, it is clear that the wireless link is the only bottleneck on the path of the TCP connections. Congestion losses do not appear in network routers unless the wireless link is fully utilized. We want to optimize the parameters of FEC and ARQ-SR in this setting. The optimization problem is not meaningful when the TCP connections are constrained by some other parts of the network.

We begin by studying separately the effects of FEC and ARQ-SR on the utilization of the wireless link, i.e. the effect of FEC alone and that of ARQ-SR alone. Second, we study the performance of the hybrid model, i.e. FEC and ARQ-SR are combined together. Intuitively, the need for FEC is important when the delay of the wireless link is large and when the error rate high, since the use of ARQ-SR in this case results in a considerable increase in the round-trip time. In the other scenarios (lower delay, less losses), FEC utility is reduced since the increase in RTT caused by ARQ-SR retransmissions has less impact on the utilization than the amount of bandwidth consumed by FEC. This reasoning is confirmed by our simulations. For lack of space, we only present the challenging scenarios that yield the most significant results.

3.1.2 FEC aloneThe case FEC alone can be obtained by setting = 0. In this case, LL frames are

not retransmitted but only protected by FEC. Figure 3 shows three lines that illustrate the variation of the utilization of the wireless link as a function of the parameter of FEC “N”, which we recall models the amount of redundancy. These three lines correspond to three distinct values of the delay, D = 20, 100, 200 ms. In all the cases, p is set to a high value 0.01. Clearly, there is an important improvement of the utilization with the first units of redundancy. When N=12, the maximum utilization is attained. At this point, the amount of FEC is optimal; about 80% of link bandwidth is used by TCP data, and the remaining 20% is used by the redundant information. Increasing N beyond 12 results in a decrease in the utilization, but this decrease is slower than the increase in the utilization on the left-hand side of the optimal point. The same behavior has been observed in [3]. For all values of N on the right-hand side of the optimal point, the amount of FEC is more than necessary. One should expect that the decay of the utilization on the right-hand side of the optimal point is given by K.B/N.

92

Figure 2 : Network Topology.

3.1.3 ARQ-SR aloneNow, we examine the effect of ARQ-SR alone by looking at the values of the utilization for N = K

(=10). The results are plotted in Figure 4 . This figure shows the utilization of the wireless link plotted as a function of (ARQ-SR persistency). We examine two cases: (i) the in-order delivery of packets to IP at the output of the wireless link is activated, which is indicated in the figure by ord = 1, and (ii) the in-order delivery of packets to IP is not activated, which is indicated in the figure by ord = 0. For D and p, we consider the same values as above (case of FEC alone); we have three values of delay, D = 20, 100, 200 ms, and p is set to 0.01. Surprisingly, the utilization is always increasing with , even though we are dealing with an extreme case where the delay D is large and the loss rate is high. ARQ-SR reduces the loss rate of TCP packets much more than it increases the end-to-end delay, which results in this monotonous improvement. We notice in these simulations that the resequencing of packets at the output of the wireless link is essential to obtain good performance with ARQ-SR, otherwise packets arrive out-of-order at the TCP receiver and trigger the transmission of duplicate ACKs, something very harmful for TCP since it results in unnecessary division of the congestion window. Another surprising result is that with ARQ-SR alone, when the reordering of packets is activated, we can reach higher utilization than what we can reach with the optimal amount of FEC, when FEC is used alone. The same finding applies to other scenarios with smaller p, and it is even more pronounced in favor of ARQ-SR.

3.1.4 Hybrid FEC/ARQ-SRNow, we present the results we obtain when we use the hybrid FEC/ARQ-SR with in-order delivery.

We consider the most challenging scenario, where the delay of the wireless link is the largest D = 200 ms, and where the error rate is the highest p = 0.01. For this scenario, Figure 5 shows the utilization of the wireless link as a function of the parameter of FEC “N”. We see six lines in the figure that correspond to six values of persistency, = 0, 1, 2, 3, 4, 5. The line = 0 gives the impact of FEC alone on the utilization, it is the same line that appears in Figure 3 for the tuple (p , D) = (0.01 , 200 ms). By looking at the values of the utilization on the y-axis, i.e. for N = K = 10, one can examine the effect of ARQ-SR alone, which is detailed in Figure 4 . By combining FEC and ARQ-SR, we hope to realize better performance than when using both schemes separately. The results in Figure 5 seems contradicting this idea, at least under the assumptions of our analysis (long-lived TCP transfers, Bernoulli errors). We remark

93

Figure 3 : Utilization of the Wireless Link for 10 TCP Connections, FEC Alone.

Figure 4 : Utilization of the Wireless Link for 10 TCP Connections, ARQ-SR alone

that the best performance a hybrid FEC/ARQ-SR scheme can give is close to what is given by ARQ-SR alone (for = 5). No more than one unit of redundancy (N=K+1) is needed to attain the highest utilization.

In the other scenarios where the delay and the error rate are smaller (like in Figure 6 which corresponds to smaller p = 0.001 and same D = 200 ms), our simulation results show that there is no need at all for FEC, and that ARQ-SR alone is able to realize the best performance. This is a surprising result, but it seems logical, since FEC consumes extra bandwidth all time, whereas ARQ-SR consumes extra bandwidth only when packets are lost. One idea could be to use FEC only to protect retransmissions, not original frames. We are currently investigating this idea by simulations and analytical modeling.

3.2 Second part: Throughput of a single TCP connectionWhen 10 TCP connections are used, transmission errors are spread over all the

connections, so their impact on one connection is smaller than when a TCP connection alone is active over the wireless link. We want to study the impact of the hybrid error recovery mechanism in the extreme case when the TCP connection suffers alone from transmission errors, and try to optimize the parameters of FEC and ARQ-SR for this case. Clearly, more effort (more FEC, larger ) is needed in the case of one connection than in the case of 10 connections to achieve full link utilization.

94

Figure 5 : Utilization of the Wireless Link for 10 TCP Connections, Hybrid ModelD = 200 ms, p = 0.01

Figure 6 : Utilization of the Wireless Link for 10 TCP Connections, Hybrid ModelD = 200 ms, p = 0.001

We consider the same network topology as the one used in the previous section, with the difference that now we have one TCP source that corresponds to one TCP connection. For lack of space, we only present two sets of results. The first set (Figure 7) corresponds to the extreme case D = 200 ms and p = 0.01. The y-axis in the figure shows the throughput of the TCP connection expressed in Mbps. We notice the same trend as that in the previous section (case of 10 TCP connections). With ARQ-SR alone, TCP is able to achieve very high utilization, which can not be realized by FEC alone. The optimal operating point of the hybrid scheme is close to that of ARQ-SR alone. We also notice how we need a larger in this case to achieve full utilization of the wireless link. The optimal utilization is equal to that obtained for 10 connections, which is a good indication that the maximum utilization we can reach with a hybrid FEC/ARQ-SR is roughly independent of the number of TCP connections.

The second set of results corresponds to the variation of the throughput of TCP as a function of the persistency level when ARQ-SR alone is used. We want to be sure that the utilization of the wireless link is always increasing with , a result that we have shown in the case of 10 TCP connections. We plot the throughput of one TCP connection for different values of ranging from 0 to 10. This second set of results is given in Figure 8 . The x-axis in the figure corresponds to and the y-axis to the throughput of TCP. For these results, the value of p is set to 0.01 and the in-order delivery of packets at the output of the wireless link is enabled (ord=1). The figure shows three lines that correspond to three distinct values of D; D = 20, 100, 200 ms. For the three lines in the figure, the throughput of TCP starts by quickly increasing then saturates. No degradation in the throughput caused by an increase in is noticed. Based on our simulations results, we conclude that under the assumptions of our study, the utilization of the wireless link is always monotonously increasing with , whatever are the number of TCP connections, the delay and the loss rate.

4 ConclusionsThe key finding of our analysis is that for long-lived TCP transfers and Bernoulli

errors, the use of ARQ-SR is more beneficial than the use of FEC, even in extreme cases where the delay is large and the error rate is high. As a consequence, the maximum utilization we can reach with a hybrid FEC/ARQ-SR is roughly independent of the number of TCP connections. For a certain persistency , there is an optimal

95

Figure 7 : Throughput of One TCP Connection over the Wireless Link, Hybrid Model.

Figure 8 : Throughput of One TCP Connection over the Wireless Link, ARQ-SR alone.

amount of FEC to be added in order to achieve full utilization of the wireless link. Any extra amount of FEC deteriorates the performance instead of improving it.

Our work can be extended in different directions. We want to check whether our finding holds in the case of finite TCP transfers and bursty transmission errors. Another possible extension is to study what will be the optimal error recovery scheme when delay-sensitive non-TCP traffic is used, as voice and video streams.

References[1] M. Allman, D. Glover, L. Sanchez, Enhancing TCP over satellite channels using standard mechanisms,

RFC 2488, January 1999.[2] A. Bakre, B.R. Badrinath, I-TCP: indirect TCP for mobile hosts, International Conference on

Distributed Computing Systems, May 1995.[3] C. Barakat and E. Altman, Bandwidth tradeoff between TCP and link-level FEC,

Computer Networks, vol. 39, no. 2, pp. 133-150, June 2002.[4] H. Balakrishnan, V.N. Padmanabhan, S. Seshan, R. Katz, A comparison of

mechanisms for improving TCP performance over wireless links, ACM SIGCOMM, August 1996.

[5] C. Barakat, E. Altman, W. Dabbous, On TCP performance in a heterogenous network: a survey, IEEE Communications Magazine 38 (2000) 40 46.

[6] S. Biaz, N.H. Vaidya, Distinguishing congestion losses from wireless transmission losses: a negative result, Seventh International Conference on Computer Communications and Networks (IC3N), October 1998.

[7] H. Chaskar, T.V. Lakshman, U. Madhow, On the design of interfaces for TCP/IP over wireless, IEEE MILCOM, 1996.

[8] A. Chockalingam, M. Zorzi, R.R. Rao, Performance of TCP on wireless fading links with memory, IEEE ICC, June 1998.

[9] E.N. Gilbert, Capacity of a burst-noise channel, Bell Systems Technical Journal 39 (1960) 1253 1266.

[10] T. Henderson, R.H. Katz, Transport protocols for Internet- compatible satellite networks, IEEE Journal on Selected Areas in Communications 17 (1999) 326 344.

[11] V. Jacobson, Congestion avoidance and control, ACM SIGCOMM, August 1988.[12] A. Kumar, J. Holtzman, Performance analysis of versions of TCP in a local network with a mobile

radio link, Sadhana: Indian Academy of Sciences Proceedings in Engineering Sciences, February 1998.[13] T.V. Lakshman, U. Madhow, The performance of TCP/IP for networks with high

bandwidth-delay products and random loss, IEEE/ACM Transactions on Networking 5 (1997) 336 350.

[14] M. Mathis, J. Semke, J. Mahdavi, T. Ott, The macroscopic behavior of the TCP congestion avoidance algorithm, Computer Communication Review 27 (1997) 67 82.

[15] The LBNL Network Simulator, ns-2, available at http://www.isi.edu/nsnam/ns/[16] J. Padhye, V. Firoiu, D. Towsley, J. Kurose, Modeling TCP throughput: a simple

model and its empirical validation, ACM SIGCOMM, September 1998.[17] C. Stevens, TCP Slow start, congestion avoidance, fast retransmit, and fast

recovery algorithms, RFC 2001, january 1997.

96

Documents

Remerciementsicapeople.epfl.ch/elfawal/Rapports/DEA02.doc · Web viewEn diminuant p, l’utilité de FEC diminue, une chose intuitive et vérifiée dans les chapitres précédents