Remerciements

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.

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 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.

Figure I.2 : Propagation par trajets multiples.

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].

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

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 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].

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

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¡K) en annulant le diagramme de rayonnement dans leurs sens et on le fait diriger dans le sens du signal désiré.

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 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.

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.

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.

C

H

A

P

I

T

R

E

II

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

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

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.
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 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.

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.

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

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...

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).

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 (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.
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 à :

(II.1)

µ §

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 à

(II.2)

µ §

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.

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 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).

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,

(II.3)

µ §

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

(II.4)

µ §

(II.5)

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.
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 à

(II.6)

µ §
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

(II.7)

µ §

Soit äi, i = 1,¡K,X, äi = 0,1,¡K,ä, 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 :

(II.8)

µ §

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,¡K,ä,

(II.9)

µ §.

(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 :

(II.10)

µ §

On intègre seulement jusqu’à µ §parce que c’est la valeur maximum que Z peut atteindre. On sait que

µ §(II.11)

,

avec

(II.12)

µ §.

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

(II.13)

µ §

ce qui donne,

(II.14)

µ §

Pour le moment, nous pensons à calculer numériquement cette expression de la valeur moyenne de RTT.
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

(II.15)

µ §.

Pour calculer la moyenne de RTT, on peut utiliser la même technique que celle dans le Paragraphe II.4.3.

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,

(II.16)

µ §.

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

(II.17)

µ §

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

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 suit :µ §. Il est très facile de voir que l'expression de RTT donné dans (Eq. II.15) peut être écrite comme

(II.18)

µ §.

(II.19)

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ù

(II.20)

µ §.

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

(II.21)

µ §.

Pour obtenir µ §, on a besoin de (Eq. II.13). Aussi, on a besoin de l’expression de µ §, k = 0,1,..,ä. En effet,

(II.22)

µ §.

µ §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 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,