Remerciements
Yüklə 265,36 Kb.
|
|
(II.23) µ §.
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, ¡K). 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,... 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’à 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 ¨C 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.
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 à (II.24) µ §,
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,¡K), ce qui peut être résolu par itération. Nous pouvons éviter l'itération en faisant une certaine approximation pour ë, par exemple en 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. Proposition 2, Arrivées déterministes : (II.25)
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. 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. C H A P I T R E III Simulation, Validation de FEC/ARQ-SR Simulation, Validation de FEC/ARQ-SR
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.
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 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. 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 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
$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 ; $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)
$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
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.
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].
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.
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 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. 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. Figure III.2 : Utilisation du lien sans fil pour 10 Connexions TCP, FEC seule : p = 10-2. 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 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. Figure III.3 : Utilisation du lien sans fil pour 10 Connexions TCP, FEC seule : D = 200 ms. 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 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). Figure III.4 : Utilisation du lien sans fil pour 10 Connexions TCP, ARQ-SR seul : p = 10-2 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 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. Yüklə 265,36 Kb. Dostları ilə paylaş:
|