Remerciements
Yüklə 265,36 Kb.
|
|
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 : pDelayXKäNUtilisation0.012ms61051018.80.012ms61051118.80.012ms61051219.20.012ms61051318.8Tableau V.4 : Résultats des simulations de FEC/ARQ-SR-Stop&Wait. 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 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 : (V.11) µ §
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 : pDäknordxutilisation0.010.001ms510111690.291150.010.001ms510101690.22511Tableau V.5 : Résultats des simulations de FEC/ARQ-SR-Stop&Wait, petit produit délai*bande. passante 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.
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. 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 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 ¨C 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 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.
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. ANNEXE
Annexe 1 Calcul 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 µ §
µ § µ §
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 : µ §
µ §. 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. Annexe 3
10 connexions TCP Une connexion TCP seule Annexe 4 FEC/ARQ-SR, résultats analytiques. 10 connexions TCP, arrivée Poissoniènne. une connexion TCP seule, arrivée Poissoniènne. 10 connexions TCP, arrivée déterministe. . Une connexion TCP seule, arrivée déterministe Annexe 5 ARQ-SR-Protégée-Par-FEC, Simulations, 10 connexions TCP. 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. [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 ¨C 900 ¨C 1800 ¨C 2400 ¨C 5800 MHz. INSA de Rennes ¨C 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 ¨C SIMPAA www.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. [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. Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SR For Wireless Links and Long-Lived TCP traffic Simulation-Based Study Of Link-Level Hybrid FEC/ARQ-SR For Wireless Links and Long-Lived TCP traffic
{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. Introduction For 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 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. Yüklə 265,36 Kb. Dostları ilə paylaş:
|