TCP et réseaux ad hoc
L'évitement de la congestion

Mathias Péron
Rapport de stage MIM2 - 2004







Résumé : A l'heure actuelle 80% du trafic dans l'Internet est basé sur le protocole de transport TCP. La question de son utilisation et de ses performances dans un environnement ad hoc va de soi. Plusieurs recherches récentes tendent à montrer que TCP se comporte mal dans ce type de réseau.

Après une introduction au protocole TCP ce rapport s'attelle à cerner les problèmes que TCP rencontre dans les réseaux ad hoc, par le biais entre autres d'un étude du médium radio. On parlera alors des solutions envisagées jusqu'à présent, dont les architectures inter-couches. Enfin, après diverses constatations, un nouvel algorithme de contrôle de la congestion pour TCP est proposé et ses résultats exposés.







      

Table des matières

1  Introduction

Le début des années 1970 voit, au sein du projet militaire Américain DARPA1, la naissance des premiers réseaux utilisant le médium radio. Ce n'est qu'avec l'arrivée du protocole 802.11 de l'IEEE2 qui permet de bâtir des réseaux sans fil autour de bases fixes, que la recherche civile s'empare à la fin des années 90 des problématiques liées à ces réseaux.
La couche MAC3 de la norme 802.11 porte en elle une méthode d'accès au médium totalement distribuée, c'est à dire ne nécessitant en fait aucune base pour que les éléments du réseau communiquent entre eux. En utilisant cette méthode dite DCF4, ces réseaux, nommés ad hoc, ne nécessitent donc aucune infrastructure fixe, et chacun de ses noeudspeut à la fois agir comme client et comme routeur, le tout dans un environnement mobile.

De par leur facilité et rapidité d'auto-organisation, les réseaux ad hoc se trouvent des applications de plus en plus nombreuses, avec par exemple la mise en communication de véhicules ou encore la prise de mesures à l'aide de capteurs (sensors networks).
Dans ce champ d'étude récent, la recherche s'est focalisée sur la conception de protocoles de routage, dont témoigne la création du groupe de travail MANET5 au sein de l'IETF6 qui s'occupe de standardiser ces protocoles. Les autres couches du modèle commencent à attirer l'attention, et plusieurs recherches pointent de nombreuses défaillances. Au niveau de la couche MAC nous avions par exemple mis à jour de nombreux problèmes d'équité d'accès au médium et proposé une solution [Pér03].

Au niveau de la couche transport, le protocole TCP7 montre un comportement inattendu par rapport à certaines de ses propriétés lorsqu'il est utilisé dans un cadre ad hoc. C'est ce problème que nous nous sommes proposés d'étudier, du fait que l'existence d'un service de transport fiable est nécessaire aux communications entre applications, et donc au futur des technologies ad hoc.
Après la section deux dédiée à un bref rappel du fonctionnement de TCP, nous essayerons dans la section suivante de discerner les problèmes que rencontre TCP en ad hoc. La section quatre rappelera au lecteur l'ensemble des solutions qui ont été jusqu'alors envisagées. Enfin la dernière section présente notre algorithme dont les performances seront étudiées.

2  Vue d'ensemble de TCP

Le protocole TCP, élaboré par Vinton Cerf en 19738, fonctionne en commutation par paquets et détient les propriétés suivantes: Les deux sous sections suivantes décrivent les mécanismes mis en place par TCP pour assurer ces différentes propriétés.

Le but n'est pas de donner une description exhaustive de TCP, mais juste de fournir au lecteur toutes les clés essentielles à la compréhension de la problématique. Pour ceux qui souhaiteraient approfondir, nous les renvoyons à un ouvrage de référence [Com96].

2.1  Fiabilité de la transmission

La mise en oeuvre de la fiabilité passe par l'utilisation de paquets d'acquittement (ACK) et de numéros de séquences (conceptuellement le numéro du premier octet contenu dans un paquet). Lorsqu'un noeudreçoit un paquet, il émet un acquittement en renseignant le numéro de séquence jusqu'auquel il a reçu tous les octets. On parle d'acquittement cumulatif.

Il est alors possible que l'on obtienne un second acquittement pour un même numéro de séquence (acquittement dupliqué), qui signifie qu'un paquet précédent a été détruit dans le réseau ou qu'il y est retardé.

Cependant TCP décidera de réémettre le paquet en question qu'à l'expiration (TimeOut) d'un délai avant retransmission, le RTO9, propre à chaque paquet qui court au moment de l'émission de celui-ci.

Le RTO, est calculé à partir du temps de transmission aller-retour, le RTT10. Ce dernier est une estimation du temps qui s'écoule entre l'émission d'un paquet et l'arrivée de son acquittement.

Les retransmissions du côté de l'émetteur comme le réordonnancement du côté du récepteur imposent naturellement la présence de buffers des deux côtés de la connexion.

La figure 1 propose un résumé de ces mécanismes en illustrant l'échange de quelques paquets.


Figure 1 : TCP: échange de paquets illustrant les mécanismes de fiabilité


2.2  Régulation du débit

TCP régule ses envois à travers un système de fenêtre glissante (sliding windows) qui définit la quantité de paquets pouvant être envoyés sans être acquittés, en terme de numéro de séquence. Cette fenêtre, dite fenêtre de transmission, que l'on abrègera en TWND11, est calculée à partir de deux autres fenêtres. La fenêtre de transmission est alors régie par la formule:
min(CWND, AWND)
La figure 2 illustre son fonctionnement au moment où dans la figure précédente le dernier acquittement n'est pas encore parvenu.


Figure 2 : TCP: fenêtre de transmission de 1000 octets


2.2.1  Contrôle de la congestion

Dans les réseaux filaires, la congestion prend racine dans la destruction ou la rétention des paquets au niveau des buffers (seulement 1% des pertes de paquets dans l'Internet est dû à l'altération du contenu).

La fenêtre de congestion doit donc être en mesure de s'adapter à l'état courant des buffers, et ce sans surestimer la congestion au risque d'influer négativement sur le débit de la connexion.

Pour atteindre ce but, TCP va au début d'une connexion envoyer un paquet, puis, de plus en plus en augmentant CWND de façon exponentielle jusqu'à recevoir un signe de saturation dans le réseau. C'est la phase de départ lent, notée SS14. En réponse à l'apparition de congestion, ce schéma est répété, mais cette fois s'arrête à certaine valeur (SSThreshold) de CWND, inférieure au dernier pic qu'elle a atteint, pour laisser place à une seconde phase dite d'évitement de la congestion, notée CA15, où le paramètre CWND va maintenant augmenter de façon linéaire.

Un graphique schématique du comportement de CWND est donné en figure 3.


Figure 3 : TCP: comportement de la fenêtre de congestion


L'idée consiste donc à jauger au plus près la congestion, et à diminuer drastiquement le débit dès son apparition. Les signes que TCP utilise pour la détecter sont les acquittements dupliqués et les timeouts (Algorithme 2.2.1). Ceci implique que les algorithmes d'estimation du RTT et du RTO peuvent jouer un rôle néfaste sur le débit, s'ils ne sont pas conçus avec soin.

[!h]

cwnd := 1 MSS  /* Maximum Segment Size : taille max. du paquet en bytes */ ss_threshold = 216  max_dup_ack = 3  état = SS 

est_connecté reception_ack état SS cwnd += MSS  CA cwnd += (MSS2/cwnd)  cwnd > ss_threshold état = CA  timeout || dup_ack timeout || #dup_ack consécutifs == max_dup_ack cwnd = 1 MSS  état = SS  ss_threshold = max(1/2TWND, 2MSS Gestion de la fenêtre de congestion de TCP

Cette section nous aura rappelé quelles sont les propriétés de TCP et comment il les assure, spécialement celle du contrôle de la congestion. Il est à noter qu'il existe une foule de variantes apportées à TCP -- calcul du RTT, calcul de l'accroissement en phase CA -- mais qui respectent le schéma standard présenté ici.

Nous verrons quelques modifications importantes de TCP à la section quatre. A présent nous allons nous replacer dans le contexte ad hoc.

3  TCP dans le cadre ad hoc

Placer TCP dans un environnement ad hoc suppose de choisir au préalable les protocoles que l'on va utiliser au niveau des couches inférieures -- au sens du modèle TCP/IP -- qui sont la couche réseau et la couche de liaison (MAC).
Si le choix de 802.1116 est naturel pour la couche MAC, il existe de nombreux protocoles de routage à notre disposition, que l'on peut classer dans deux familles différentes. D'un côté les réactifs, qui innondent le réseau de messages pour découvrir à la demande le chemin entre deux noeuds, et de l'autre les proactifs qui par l'échange régulier de messages construisent des tables de routage (directement inspiré du protocole RIP17 d'IP). L'IETF a standardisé, respectivement dans chacune de ces familles, les protocoles AODV18 et DSDV19.

Nous avons opté pour le protocole AODV, car la majeure partie de nos simulations se sont faites dans des réseaux peu denses dans lesquels il génère moins de paquets de signalisation qu'un protocle proactif.

Toutes les simulations de ce rapport ont été obtenues à partir de NS220, un simulateur au fonctionnement validé et reconnu par la communauté scientifique. Projet open source, il présente l'avantage de permettre des modifications aisées à tous les niveaux.
Des cinq propriétés de TCP que nous avions listées (page ??), on remarque que seul l'évitement de la congestion est dépendant du réseau. On acceptera aisément qu'en ad hoc les autres propriétés sont préservées.
Si l'on souhaite montrer que TCP est défaillant quant à la régulation de son débit, on note de prime abord la difficulté à évaluer ce qu'est une bonne régulation du débit par rapport à la congestion du réseau.

Cela suppose d'abord d'avoir une définition de la congestion, et de savoir si celle-ci est identique en ad hoc et en filaire. Il s'agit ensuite d'avoir, selon celle-ci, des indicateurs de l'efficacité de l'évitement de la congestion. On pense au taux d'occupation des buffers des routeurs, au nombre de paquets détruits et pourquoi, ou encore au débit global que l'on atteint pendant une connexion TCP.
Afin de pouvoir répondre à ces questions il nous faut au préalable comprendre les caractéristiques des réseaux ad hoc. C'est ce que propose la section suivante.

3.1  Particularités d'un environnement ad hoc

Note: une description exhaustive de l'ensemble de la couche MAC est donnée dans le rapport de stage [Pér03] à la section intitulée "Le protocole de l'IEEE 802.11". Nous invitons le lecteur à s'y reporter pour de plus amples explications concernant l'exposé de faits de cette section.
Le médium radio, à contrario du filaire, n'est pas en mesure de détecter les collisions. Il doit donc les éviter et utilise dans ce but un temps aléatoire avant d'accéder au médium, pour réduire la probabilité de collision avec un voisin et des paquets d'acquittement pour s'assurer de la bonne transmission d'un paquet.
La diffusion radio, par exemple entre les noeuds a et b de la figure 3.1, impose un comportement aux noeudsenvironnants. Les noeudsse trouvant dans la zone (1) ne peuvent être récepteur et ceux se trouvant dans la zone (2) ne peuvent émettre sans quoi une collision aurait lieu au noeud b. Remarquons que ces deux zones s'inversent lors de l'échange de l'acquittement.

[la diffusion radio]     [le problème des noeuds cachés]
Figure 4 : Conséquences du médium radio


La figure 3.1 représente le scénario classique où un noeud ne respecte pas la contrainte (2). Les noeuds a et b, sont trop éloignés l'un de l'autre pour comprendre la vrai raison des collisions en c et de fait diminuent drastiquement leur débit à tort afin d'éviter cette situation.

Un mécanisme de réservation du canal a donc été mis en place: le noeud a envoie une demande d'émission, le RTS21, auquel c répond par l'affirmative en envoyant un CTS22 qui va imposer le silence au noeud b durant l'émission du paquet et de son acquittement.
Il reste à prendre en compte que la diffusion radio d'un paquet engendre des interférences bien au delà de la zone où le paquet est en mesure d'être décodé. Ainsi on distingue la zone de transmission, notée TR23 et la zone de détection de signal, notée CS24. La détection d'un signal dans cette dernière zone impose au noeudde respecter la contrainte (1). Comme le suggère la figure 3.1, on estime que la fin de la zone CS est deux fois plus éloignée que celle de la zone TR.

[Atténuation du signal]     [ensemble des flux en compétition d'accès avec le flux f]
Figure 5 : L'espace de compétition d'accès dans un environnement ad hoc


Enfin, si on considère un flux f, de par les particularités qui précèdent on peut déterminer l'ensemble des flux, et donc des noeuds, qui sont en compétition d'accès au médium avec f. Ces flux sont représentés de façon schématique à la figure 3.1.
Ces particularités donnent aux réseaux ad hoc les propriétés désavantageuses suivantes: C'est dans ce cadre que TCP va devoir réguler son débit.

Théorie de l'information (parenthèse)
Dans la description de l'environnement ad hoc que l'on vient de fournir, on a tendance à oublier qu'elle repose sur une des visions possibles de mode d'opération. Par exemple, toute interférence est traitée comme du bruit, ou encore tout paquet est entièrement décodé avant d'être retransmis.

Or, comme le souligne [XK02], les interférences peuvent être de l'information ! Dans le cas où un noeudreçoit la superposition d'un signal fort et d'un signal très faible, il peut être en mesure de décoder le premier et par soustraction obtenir le second.

Répondre à la question de la quantité d'informations qui peut transiter dans un réseau ad hoc, ou encore du meilleur modèle à appliquer, sont des interrogations qui intéresseront les lecteurs qui, en fin de lecture, auront un avis pessimiste sur la résolution des problèmes en ad hoc.

3.2  Questionnement

Notre point de départ a été de regarder comment TCP se comportait dans des scénarios simples que sont les chaînes de noeudsoù l'émetteur et le récepteur se trouvent en bout (figure 3.2).
Les résultats obtenus, visibles à la figure 3.2, montrent que le débit de la connexion diminue exponentiellement avec la longueur de la chaîne pour finalement se stabiliser à un débit extrêmement faible de l'ordre de 70 KBps.

[débit par rapport à la longeur de la chaîne] [les chaînes de nos simulations. Exemple d'une 5-chaîne]
Figure 6 : Comportement comparé dans les chaînes de TCP filaire et ad hoc


Nous avons mis en regard le comportement de TCP dans des réseaux filaires équivalents qui sans surprise est linéaire (on constate une très légère baisse due au temps de recherche de la route et surtout, de par l'allongement du RTT, un accroissement légèrement plus faible de la fenêtre de congestion).
Dans les deux environnements, et quelle que soit la longueur de la chaîne, aucun buffer n'est mis à mal. Mais si aucun paquet n'est donc perdu en filaire ce n'est pas le cas de l'environnement ad hoc ou en moyenne 5% des paquets n'arrivent pas à destination. Cependant ceci ne représente pas de telles pertes au point d'expliquer une baisse exponentielle du débit.
Une question qui surgit alors est celle des performances d'un protocole de transport qui n'assure pas de régulation de son débit. C'est le cas du protocole UDP25, qui n'assure pas non plus de propriété de fiabilité, mais qui, à l'instar de TCP, fonctionne en commutation par paquets et avec une sémantique bout-à-bout. Nous avons alors comparé les performances de ces deux protocoles dans une 8-chaîne. Les résultats sont donnés à la table 1.

  UDP TCP
débit (KBps) 173 99
paquets perdus (%) 60.74 5.16
débordement de buffers 62 0

Table 1 : Différents indicateurs de TCP et UDP dans la 8-chaîne


UDP, en surchargeant le réseau perd beaucoup de paquets et cause des débordements au niveau des buffers, mais cependant atteint 70% de débit supplémentaire par rapport à la connexion TCP26. TCP devrait être en mesure de s'approcher au moins d'un débit équivalent.

Le mécanisme de régulation de débit est le premier suspect. La figure 7, qui montre l'évolution du débit et de la fenêtre de congestion de TCP dans ce scénario, nous dit qu'il s'agit du coupable.

[évolution du débit]   [évolution de CWND]

Figure 7 : Performances de TCP dans la 8-chaîne


Le débit souffre de grandes pauses au nombre de trois, d'une dizaine de secondes chacune, directement corrélées à une stagnation de CWND à 1 paquet. On remarque de plus que hors de ces phases TCP arrive à atteindre un débit moyen aux alentours de 200 KBps.

Le blocage de la fenêtre de congestion en phase de départ lent a diverses origines. Dans le cas présent le premier est dû à trois timeouts successifs, les deux suivants sont dus à une absence de route au moment du recalcul de celle-ci par le protocole de routage.
L'algorithme d'évitement de la congestion de TCP a été conçu pour répondre aux problèmes des goulots d'étranglement dans les réseaux filaires. La nature du médium radio, avec son espace de compétition d'accès large, fait que cette notion devient diffuse faisant de la perte d'un paquet ou de son retardement dans le réseau une conséquence de nombreux faits.

Nous nous sommes proposés de lister dans la section suivante l'ensemble des facteurs qui engendrent des pertes lors d'une connexion TCP dans les réseaux ad hoc actuels.

Au final, nous avons vu que les réseaux ad hoc montrent un mauvais comportement quant à un simple flux. Si celui-ci paraît être inhérent au médium radio, il semble cependant possible de faire en sorte que TCP évite le blocage de ses envois en prenant en compte ce qu'est réellement la congestion en ad hoc. On obtiendrait alors un meilleur débit qu'avec UDP, rendant TCP viable pour les réseaux ad hoc.

3.3  Facteurs de pertes

Une foule d'études propose des évaluations de ces facteurs, comme par exemple [DB01] qui s'intéresse aux performances de TCP en présence des trois protocoles de routage standards. Leur défaut réside dans le fait que tant les études basées sur les simulations que les approches théoriques se doivent de fixer de nombreux paramètres qui souvent constituent les principales influences sur le résultat qu'elles nous donnent.

Ainsi nous ne nous sommes pas attachés à quantifier les pertes générées mais plutôt à répertorier l'ensemble des mécanismes qui pour nous constituent l'ensemble de congestion ad hoc, qui rassemble tant les pertes que la création d'indices de pertes (timeouts, etc).

3.3.1  La mobilité

Le caractère mobile du réseau implique que deux noeuds puissent à tout moment être déconnectés, créant ainsi de nombreuses pertes de paquets, notamment d'acquittements, qui pour TCP vont engendrer de nombreux timeouts consécutifs.

Le problème réside dans la transition qui doit s'effectuer lorsqu'un mobile change de position. Ce problème, connu sous le nom de handoff intervient à plusieurs niveaux réseau et concerne plusieurs mobiles. Le noeuden mouvement devra peut-être changer d'adresse IP s'il atteint un nouveau réseau, alors qu'un autre noeudqui se servait de celui-ci pour router des données devra invoquer une recherche de route.

Ainsi on souhaite minimiser la perte de paquets, ce que tente de faire les smooth handoff ou encore réduire l'augmentation du délai d'arrivée des paquets, rôle proposé par les fast handoff.

3.3.2  Le protocole de routage

Recherche de route
La construction des tables de routage implique l'envoi de nombreux paquets de signalisation. Dans le cas des protocoles réactifs, durant une période assez longue le médium va leur être quasiment dédié.

Le fort coût d'accès au médium en temps et en espace fait que cette période peut-être suffisament longue pour produire des timeouts sur certaines connexions.

Cependant le problème le plus fréquent, se situe au niveau de l'un des noeuds, dans la perte d'une route pendant la phase de recherche distribuée, ce qui peut provoquer des destructions de paquets conséquentes selon la façon dont le protocole réagit.

Multi-route
Certains protocoles de routage maintiennent plusieurs routes pour une même destination dans le but de diminuer la fréquence de recherche de routes ou encore d'améliorer la connectivité dans un environnement très mobile.

Les différentes routes que vont emprunter les paquets ne sont pas équivalentes en terme de délais, ni de compétion d'accès subit, ce qui va résulter au niveau du récepteur de la connexion en une arrivée plus désordonnée des paquets. La conséquence de ces paquets dits out-of-sequence est bien sûr la génération de nombreux acquittements dupliqués qui sont des indices de congestion, mais également un point de difficulté pour le calcul du RTO.

Zones grises
Sous 802.11b les paquets diffusés sont envoyés avec une vitesse de transmission de 1/2 Mbps alors que les paquets envoyés en unicast le sont à 11 Mbps.

Les protocoles de routage utilisent typiquement la diffusion pour envoyer leurs paquets de signalisation lors de recherche de routes. Par contre l'envoi des paquets de données se fait en unicast. La portée du signal décroissant avec l'augmentation de la vitesse, le protocole de routage aura obtenu des routes dont certaines, dans la zone grise, ne seront pas accessibles lors de l'envoi des données, créant là encore une source de pertes.

3.3.3  La couche d'accès au médium

Altération
Le médium radio est connu pour avoir un fort taux d'erreur par bit, BER27, c'est à dire de paquets au contenu altéré, dû aux interférences, ce qui constitue encore des destructions de paquets.

Retransmissions
La couche MAC effectue des retransmissions des paquets, dans la limite de quatre, lorsqu'elle n'a pas reçu d'acquittement. Ce mécanisme qui a pour but d'améliorer la fiabilité rentre en conflit avec celui de retransmission de TCP.

Tout d'abord il influe considérablement sur le calcul du RTT qui est crucial quant au problème de la congestion. Enfin, il n'est pas rare que TCP et la couche MAC effectuent une retransmission d'un même paquet. Ceci va avoir pour conséquence la génération d'acquittement dupliqués. D'après [DCY93] en deça d'un certain taux d'erreur la plupart des paquets sont retransmis par les deux couches causant alors une perte de l'ordre de 30% du débit par rapport au scénario où TCP est seul garant de la fiabilité.

3.3.4  Probabilité de destruction

Dans l'excellent article [FZL+03], les auteurs décrivent l'évolution de la probabilité qu'un paquet soit détruit par la couche MAC, à l'aide d'une vue simplifiée du réseau qui leur permet de proposer une formule pour la calculer, classiquement à l'aide de chaînes de Markov. Leur résultat tend à montrer que cette probabilité augmente avec le débit offert, pour finir par stagner.

Pour clore et illustrer cette section, nous avons calculé la probabilité de destruction d'un paquet durant nos simulations dans la 8-chaîne en fonction du débit offert. Le résultat, à la figure 3.3.4, différencie les destructions effectuées par la couche MAC à cause de la compétition d'accès, et celles par la couche réseau à cause d'un défaut de route.

On observe que le résultat est pour ce scénario à l'inverse du résultat théorique précédent, puisque la probabilité de perte décroît avec le débit offert avant de se stabiliser. Cependant on soupçonne tout simplement que le nombre de paquets détruits soit quasiment constant (au vue du nombre de paquets transitants allant de 4500 pour un débit de 1 Mbps à 45000 pour un débit de 11 Mbps) quel que soit le débit proposé, ce que nous montre la figure 3.3.4.

[Probabilité de destruction selon le débit offert] [Nombre de paques détruits selon le débit offert]

Figure 8 : Probabilité de destruction dans la 8-chaîne sous TCP


On conclura uniquement sur le fait que les réseaux ad hoc ont un comportement de destruction très différent des réseaux filaires (où la probabilité de destruction d'un paquet va être de 1 dès l'apparition d'un buffer plein) qui se concrétise en un certain nombre de paquets détruits indicateur de la compétition d'accès subit, et ce dès le début de la connexion.

3.4  Conclusions

L'ensemble de congestion comme nous l'avons définit, prend sa source dans toutes les couches réseaux inférieures à la couche de transport. En plus d'imposer une congestion constante, des pics de pertes sont produits lors de handoffs ou d'actions du protocole de routage.
Les dernières améliorations apportées ces dernières années à TCP, telles les implémentations Vegas, Reno et NewReno ainsi que le système SACK28 n'ont pas montré de résultats significatifs dans le cadre ad hoc lors de nos simulations, tout au plus une légère augmentation du débit global, loin de celle espérée à la fin de notre questionnement.
Si l'on souhaite améliorer les performances de TCP dans un cadre ad hoc, plusieurs voies s'offrent à nous. La première voie suppose que TCP se voie offrir des informations ou qu'il puisse accéder aux mécanismes des couches inférieures. Quelques protocoles basés sur cette approche sont présentés à la section suivante.
Nous n'explorerons pas la seconde voie. Cependant on notera au niveau MAC l'existence du mécanisme ARQ29 qui effectue des retransmissions si un paquet a été altéré (au regard du CRC ou alors couplé au FEC30 basé sur l'ajout de bits de parité). L'article [AB04] montre que ARQ/FEC améliorent la latence de transfert de TCP, alors que [CZ99] affirme que ce système peut être néfaste au débit de TCP, ARQ augmentant le RTT et FEC diminuant la bande passante.
Enfin, la dernière voie est celle que nous avons ouverte, à travers notre algorithme présenté à la section 5.

4  Vers des conceptions inter-couches

L'architecture actuelle des protocoles réseaux, que ce soit le modèle OSI31 ou le modèle TCP/IP, repose sur un ensemble de modules devant chacun fournir un service précis et ce de façon autonome. Ces modules on été organisés hiérarchiquement dans une pile, chaque module se trouvant au dessus du service dont il a besoin pour fournir le sien (figure 4).

Une telle conception a l'avantage de fournir un niveau d'abstraction permettant de découper le problème en sous-problèmes, plus facile à aborder, et par là même d'améliorer la compréhension que l'on a du problème entier.
Le succès de TCP/IP réside certainement plus dans la conception de son architecture que dans les algorithmes qu'il met en oeuvre.

Cependant, dès l'apparition d'influences entre deux couches, l'envie est forte que ces couches puissent communiquer entre elles un ensemble de variables, statistiques, qui aideront à la résolution d'un problème. C'est ce que proposent les architectures inter-couches (cross-layers) notamment à travers des retours d'informations (en anglais, feedbacks).
De nombreux feedbacks ont été proposés pour les réseaux ad hoc, comme par exemple la couche physique informant la couche MAC de la qualité de la liaison permettant à ce dernier de décider d'utiliser ou non des mécanismes de contrôle d'erreur. Au niveau de la consommation d'énergie, très importante dans le cas des réseaux de capteurs, on souhaite par exemple que la couche MAC adapte sa portée de transmission ou encore que la couche réseau préfère des noeuds à d'autres lors du routage.

On notera tout de suite que ceci accroît la difficulté pour TCP de fournir son propre service. En effet, la considération précédente sur l'état des batteries mène par exemple directement à une sorte de handoffs.

Au final, comme le prophétise [CRR04] les réseaux sans fil devraient s'orienter vers une architecture comptant un module cross-layer auquel les évènements de chaque couche seraient relayés, et qui aurait pour rôle de base de données des variables du réseaux. La figure 4 illustre cette vision.

[les 4 premières couches du modèle OSI actuel]     [future architecture proposée pour les réseaux sans fil]

Figure 9 : Architecture des protocoles réseaux


Nous allons voir à présent quelques protocoles cross-layers représentatifs qui ont été inventés pour améliorer les performances de TCP en ad hoc. Le récent rapport de recherche [AEP04] donne un état de l'art en la matière dans lequel le lecteur trouvera une liste exhaustive de ce type de protocoles.

4.1  Contrôle des échecs de routage

L'idée consiste à imposer à un noeudqui détecte la perte d'une route l'envoi d'un paquet de feedback. A la réception de celui-ci l'émetteur TCP, que ce soit dans le protocole TCP-F32 [CRVP97] ou ELFN33 [HV99], va bloquer son fonctionnement: gel des horloges, des émissions et des fenêtres de régulation de débit. Ainsi à la fin du blocage (TCP-F attend un paquet de notification de reconstruction de la route alors que ELFN teste par l'envoi de paquets spéciaux si la route est de nouveau disponible) TCP va pouvoir reprendre immédiatement ses envois à un débit concordant avec la réalité du réseau et donc ne pas souffrir d'un départ lent de sa fenêtre de congestion.

On remarquera la proposition de [KTC01] dans TCP-BuS34 d'imposer aux noeudsdu réseau une bufferisation des paquets en cours de transit lorsqu'ils reçoivent le feedback de perte de route. Ainsi ces paquets ne seront pas perdus et en augmentant suffisamment le RTO de ces paquets ils ne provoqueront pas de timeouts, ce qui rend le blocage de TCP encore plus transparent en rapport à l'échec de routage.
TCP-BuS, dont l'idée de mise en cache des paquets est à souligner, a montré de bons résultats au vu des échecs de routage en atteignant 30% de débit supplémentaire en moyenne par rapport à TCP (10% par rapport à TCP-F).

4.2  Contrôle de la congestion

Venu du monde filaire, le mécanisme ECN35 permet à un noeudrouteur, selon l'occupation moyenne de son buffer, de positionner un bit dans l'entête IP36 du paquet qu'il est en train de traiter, pour signifier qu'une congestion est probable. Le paquet, en arrivant au récepteur de la connexion TCP va positionner le bit ECN-echo dans quelques-uns des acquittements suivants. l'ECN-echo va avoir pour effet d'inhiber l'accroissement de CWND à l'arrivée de l'acquittement au niveau de l'emetteur TCP.

D'après [CMP00]37 ECN atteint de bonnes performances en prévenant la congestion dans les réseaux ad hoc.
ATCP38, proposé par [LS99] est l'un des protocoles cross-layers le mieux conçu actuellement. Il inclut une nouvelle couche entre la couche réseau et la couche TCP qui a pour but de filtrer les signes de congestion émanants du réseau.

Celle-ci garde trace des acquittements reçus et des horloges de retransmissions. Ainsi lorsque trois39 acquittements dupliqués arrivent, ou lorsque un timeout est proche de s'effectuer, ATCP bloque TCP et effectue la retransmission lui-même des paquets nécessaires, jusqu'au moment où un acquittement non dupliqué arrive. TCP est alors débloqué et l'acquittement lui est délivré.

Enfin ATCP inclut également le mécanisme ECN et un contrôle d'échecs de routage similaire à ceux vus précédemment. L'avantage de ATCP est sa transparence tant au niveau du noeudoù il opère que pour l'ensemble du réseau. Malheureusement, si des simulations ont été entreprises, elles ne sont pas de nature40 à rendre compte de l'amélioration réelle apportée, et nous ne pouvons donc reporter ici de résultats.
Une dernière approche qui nous a paru prometteuse est celle de [KKFT02] nommée Split-TCP. Le protocole élit un ensemble de proxys tout au long d'une connexion TCP qui vont acquitter, par un paquet nommé LocalACK, l'arrivée du paquet au proxy précédent. Un proxy fait suivre les paquets au débit auquel il reçoit les acquittements LocalACK du proxy suivant. Afin de préserver la sémantique bout-à-bout de TCP les acquittements standards sont conservés.

Au final, la fenêtre de congestion de l'émetteur TCP est calculée à partir de l'ajout de la fenêtre bout-à-bout (ancienne CWND) et de la fenêtre locale variant selon le débit du proxy suivant, cette dernière étant implémentée également au niveau de chaque proxy.

L'équipe de recherche annonce une amélioration de 5 à 30 % du débit par rapport à TCP. Le plus grand inconvénient réside dans le trafic généré par les acquittements LocalACK et par l'élection des proxys, surtout dans un environnement mobile. Cependant on insistera sur le fait que c'est le seul protocole qui ne propose pas de bloquer TCP mais de réguler son débit selon ce qu'expérimente la connexion sur des tronçons du réseau, à savoir entre deux proxys voisins.

Conclusion
Le plus grand nombre de protocoles cherchant à améliorer TCP utilise des mécanismes cross-layers. Ceux-ci demandent une coopération de plus en plus importante des noeudsintermédiaires -- bufferisation par exemple -- et nécessitent souvent l'utilisation de paquets de feedbacks.

Le fait qu'une partie du mécanisme soit implémentée dans les noeudsintermédiaires implique que la totalité du réseau implémente le protocole TCP proposé, tant pour son fonctionnement que pour éviter de créer des situations inégalitaires. Or ceci va à l'encontre de la philosophie première des réseaux ad hoc où on souhaite s'affranchir d'une telle homogénéité. Enfin, dans un médium souffrant d'un haut BER, de forte compétition et de nombreuses déconnexions, l'ajout de paquets de signalisation n'est pas souhaitable.

On ne peut douter des résultats positifs sur le débit de TCP mais la dérive vers des architectures de plus en plus complexes où l'on colle des ``rustines'' sur chaque problème est à craindre. Si l'utilisation de feedbacks paraît inévitable sur certains points en ad hoc comme les ressources en énergie, il serait souhaitable que la recherche se mette d'accord sur l'ensemble des variables qui pourraient être communiquées sans obscurcir la compréhension à la fois générale et particulière de l'ensemble des couches réseaux.

5  TCPToK: évitement de l'ensemble de congestion

5.1  Point de départ

Face à l'ensemble de congestion nous avions émis l'avis que la réduction de paquets introduits dans le réseau à un même moment pourrait être bénéfique.

Dans [FZL+03], les auteurs -- M. Gerla -- proposent de regarder l'effet d'une borne supérieure imposée à la variable CWND lors du contrôle de congestion. Nous avons effectué nos propres simulations en ajoutant cette borne, nommée CWL41, à l'algorithme 2.2.1. Le débit atteint et le pourcentage de perte selon la valeur de CWL dans la 8-chaîne et la 14-chaîne sont exposés à la figure 10. Ces résultats sont similaires à ceux exposés dans leur article.

[débit atteint par rapport à CWL]   [pertes subies par rapport à CWL]

Figure 10 : Effets de la borne Congestion Window Limit


On remarque immédiatement une variation extrême dans les résultats tant au niveau du débit qu'au niveau des pertes. En effet pour une valeur de CWL aux environs de 3, le débit par rapport à TCP est doublé et les pertes, quant à elles, sont devenues quasi normales -- de l'ordre de 0,1 %.

Il est à noter que si on augmente fortement le débit, l'écart de performance se situe dans une fourchette de 30 à 40 % et non 100 % -- on se souvient en effet que la probabilité de pertes diminue avec le débit (cf. section 3.3.4).
Ainsi limiter les envois à une très petite valeur annule une grande partie de l'ensemble de congestion. En effet la probabilité de destruction, qui est l'un de ses indicateurs, est de 2,5.10-4 pour la 8-chaîne et de 1,4.10-4 pour la 14-chaîne, lorsque CWL est égale à 3. Ce résultat est à mettre en rapport avec la probabilité de 10-3 que nous avions mis à jour à la figure 3.3.4, et nous indique donc que 10 fois moins de paquets sont perdus à cause d'un défaut de route ou de la compétition d'accès au médium.
Considérations sur CWL
L'explication d'un tel résultat se trouve dans ce que l'équipe de M. Gerla appelle la réutilisation spatiale. Celle-ci consiste pour une connexion, dans une configuration donnée d'un réseau, en la maximisation du nombre de transmissions parallèles. Les émissions parallèles possibles sont régies exactement par l'espace de compétition d'accès au médium42 présenté au début de ce rapport à la figure 3.1 ce qui implique, dans le cas des chaînes qu'un seul flux peut être actif sur quatre liens radios ou encore qu'un noeudpeut émettre tous les cinq noeuds43.

Les auteurs concluent alors que la valeur de CWL optimale dans une chaîne est de h/4 où h représente le nombre de liens dans la chaîne -- il s'agit donc d'une (h+1)-chaîne.
On remarque que le contrôle de congestion de TCP devient très simple pour les chaînes de moins de cinq noeuds. Dans [CXN03], qui se base sur ces travaux, il est proposé d'ajuster CWL à l'aide du nombre de liens aller-retour de la connexion, le RTHC44, selon la formule 1/5 RTHC. Les résultats montrent jusqu'à 15% d'amélioration en terme de débit (il est passé sous silence comment on calcule le RHTC ...). Le facteur de la formule est fixé à partir de simulations et on remarque qu'il correspond au calcul 2 h/5 dans la chaîne.
Ceci défait le raisonnement précédent sur la réutilisation spatiale. En fait, vouloir que CWL augmente avec la longeur de la chaîne est une erreur. Comme l'a expérimenté [CXN03] et comme nous le montrent nos simulations la valeur optimale de CWL se situe entre 3 et 5 et doit rester dans cet intervalle.

L'idée sous-jacente est qu'une fois que l'ensemble des noeudsparticipant à une connexion sont tous en possession de quelques paquets à délivrer, CWL devrait être positionnée à la valeur un, la chaîne fonctionnant alors comme un pipeline. Cependant ceci ne prend pas en compte le délai d'arrivée des acquittements qui conditionne les transmissions à travers le système de fenêtre glissante, ni les aléas du réseau qui font que finalement une fenêtre de transmissions de quelques paquets seulement permet de ne pas casser le comportement en flux tendu que l'on souhaite avoir dans la chaîne. Aller au delà de ces quelques paquets, c'est engendrer une augmentation rapide de la probabilité de destruction et donc des pertes comme l'illustre la figure 5.1.

5.2  La régulation du débit dans TCPToK

Fort de ces connaissances, nous avons voulu construire un algorithme qui régule CWND aux valeurs que l'on a montré optimales pour les performances de TCP. Il s'agit donc de concevoir un nouvel algorithme de régulation de la fenêtre de congestion, et ce si possible, sans recourir à des architectures cross-layers.

On constate tout d'abord que maintenir CWND en dessous de 5 implique de laisser de côté le schéma exponentiel du départ lent, voire même d'abandonner l'algorithme premier de TCP. En effet on souhaiterait plutôt avoir deux mécanismes, l'un qui régule la fenêtre de congestion en fonction de la capacité du réseau en terme de réutilisation spatiale et l'autre qui offre une réponse à l'apparition des indices de congestion tels les timeouts, l'idée étant que le second sera d'autant plus performant si le premier accomplit parfaitement sa tâche.

Fondement
Il nous est apparu qu'un indice de la réutilisation spatiale était offert à l'émetteur TCP par le premier noeudqui relaye les paquets que ce premier émet. Sous l'hypothèse d'une mobilité faible, lorsque ce noeudva faire suivre le paquet TCP, l'émetteur de la connexion TCP étant dans son voisinage va également le recevoir, puisqu'il se trouve en situation de noeudexposé.

Deux constatations. Premièrement, lorsqu'on émet un paquet TCP, il est quasiment certain que l'on devra laisser l'équivalent de deux temps d'émission à des noeudsde notre voisinage, l'un étant dû au routage du paquet de données vers sa destination -- qui peut donc ne pas avoir lieu si le paquet à été pris par un noeudqui s'est très éloigné de l'émetteur TCP avant de router le paquet -- et l'autre dû à l'arrivée de l'acquittement -- qui lui est certain.

Deuxièmement, le fait que les noeudsde mon voisinage puissent introduire rapidement le paquet de données dans la suite du réseau montre que celui-ci tend à avoir une bonne réutilisation spatiale, dont l'étendue va bien au delà des quatre liens de l'espace de compétition, si l'on considère en effet que chaque noeudavait également un paquet à envoyer et qu'il a pu l'effectuer dans ce même délai.

Régulation
C'est sur ces indices que notre algorithme TCPToK va se baser pour réguler son débit, à travers un simple système d'échange de jetons45 avec son voisinage, ces jetons étant les paquets de données eux-mêmes. L'idée est que lorsque l'émetteur TCP va effectuer une transmission de paquets, il va lui en coûter un nombre équivalent de jetons. Sur ces paquets, un certain nombre va être transmis au noeud suivant, et l'émetteur TCP en les recevant également, va obtenir un jeton pour chacun d'eux.

On souhaite avoir constamment un nombre de jetons équivalent à CWND, et donc lorsque une fenêtre à été envoyée et que tous les jetons ne sont pas revenus l'algorithme décide que la réutilisation spatiale est mise à mal et que CWND doit s'adapter au nombre de jetons reçus puisqu'ils constituent une mesure de ce qui est actuellement transférable dans le réseau.

Congestion
Il reste à définir le comportement à tenir face aux indices de congestion. Là encore, le fait de réinitialiser la fenêtre de congestion n'a plus vraiment de sens, surtout que l'on souhaite qu'elle soit liée à l'échange de jetons. A l'instar de TCP, on souhaite diminuer de façon forte le débit. La limite CWL nous est apparu comme un excellent moyen de poser une barrière à l'évolution de CWND, à une valeur où elle génère de la congestion.

Si TCPToK va positionner CWL lorsqu'il détecte de la congestion, il est possible que la valeur de cette borne puisse augmenter pour prendre en compte un changement de comportement du réseau. Cependant afin que les effets du changement de CWL soient effectifs, une période de stabilisation est imposée durant laquelle CWL reste inchangée.

5.2.1  Algorithme complet

Les mécanismes étant exposés, on souhaite ici discuter l'algorithme TCPToK de façon exhaustive.

L'algorithme 5.2.1 a pour but de récupérer les messages qui consituent des jetons et implique donc des modifications au niveau MAC et réseau afin de porter le jeton à la connaissance de TCP.

[!h] /* ns-2/mac/mac-802_11.cc, recv_timer(), appellée à l'arrivée d'un paquet */ c'est un paquet de données ET je ne suis pas le destinataire MAC marquer le paquet  transmettre à la couche supérieure  retour  /* ns-2/aodv/aodv.cc, recv(), appellée à l'arrivée d'un paquet */ le paquet est marqué l'adresse IP de l'émetteur est la mienne ET le nombre de retransmissions est de 1 transmettre à la couche supérieure  détruire le paquet  retour  TCPToK, niveau MAC et réseau

L'algorithme 5.2.1 constitue la première partie du code modifié au niveau de TCP. On y trouve le comptage basique des jetons et les initialisations.

La variable avg_cwnd contiendra une estimation de la valeur moyenne de CWND. stable consiste en un compteur de jetons reçus et constitue l'avancement de la période de stabilité: lorsque sa valeur dépasse seuil_stable, CWL peut être réévaluée. Enfin last_cwl est la mémoire de la valeur maximale que CWND a atteint depuis le dernier changement de CWL.

[!h] /* ns-2/tcp/tcp.cc, TcpAgent(), constructeur d'un agent TCP */ tokens = 1  last_cwl = 1  avg_cwnd = 1  cwnd = 1  stable = 0  /* ns-2/tcp/tcp.cc, output(), envoi d'un paquet */ tokens--  /* ns-2/tcp/tcp.cc, recv(), réception d'un paquet */ le paquet est marqué tokens++  stable++  détruire le paquet  TCPToK, niveau TCP, partie un

L'algorithme 5.2.1 s'occupe de la régulation de CWND et du nombre de jetons, et de fixer la valeur de CWL.
Lorsqu'un acquittement arrive, l'état Congestion Avoidance est imposé. Si l'ensemble des jetons envoyés est revenu le calcul de CWND est identique à celui de TCP. Dans le cas contraire on assigne à CWND le nombre de jetons courants. Le nombre de jetons alors à disposition de TCP est égal à la nouvelle valeur de CWND moins les jetons qui vont arriver en retard.

Ainsi dans TCPToK le fait qu'un acquittement soit délivré n'implique pas une augmentation de CWND mais sa réévaluation. Enfin, si la connexion est stable et si l'écart entre CWL et l'évaluation moyenne de CWND est faible, on considère que l'on peut être en mesure d'envoyer plus de paquets et donc CWL est augmenté.
Le calcul de CWND invoqué par les timeouts et les acquittements dupliqués n'est pas modifié. Comme précédemment le changement de CWND impose le recalcul du nombre de jetons alloués. Par contre c'est ici qu'intervient le calcul de la limite CWL. Si l'écart entre celle-ci et l'évaluation de CWND est important, CWL va être placée entre ces deux valeurs. Par contre si la différence est faible, un tel mécanisme mènerait à une stagnation de CWL, et donc celle-ci est placée légèrement en dessous de l'évaluation moyenne de CWND.

[!h] /* ns-2/tcp/tcp.cc, opencwnd(), augmenter CWND, appellée à l'arrivée d'un ACK non dupliqué */ cwnd_before = cwnd  état = CA  /* calcul de ``increment'' selon le standard TCP */ tokens == cwnd cwnd += increment  tokens = partie_inf(cwnd)  tokens < partie_inf(cwnd) cwnd = tokens  tokens = cwnd - (partie_inf(cwnd_before) - tokens)  tokens < 1 cwnd = 1  tokens = 1  tokens = partie_inf(cwnd)  avg_cwnd = (0,9 × avg_cwnd) + (0,1 × cwnd)  cwnd > last_cwl last_cwl = cwnd  stable > seuil_stable diff = 1/2 (last_cwl - avg_cwnd)  diff < 0,5 cwl = avg_cwnd + diff  stable = 0  /* ns-2/tcp/tcp.cc, slowdown(), réduire CWND, appellée au déclanchement d'un timeout ou à l'arrivée d'ACK dupliqués */ cwnd_before = cwnd  /* calcul du nouveau CWND selon le standard TCP */ avg_cwnd = (0,9 × avg_cwnd) + (0,1 × cwnd)  tokens = partie_inf(cwnd) - (partie_inf(cwnd_before) - tokens)  tokens < 1 cwnd = 1  tokens = 1  diff = 1/2 (last_cwl - avg_cwnd)  diff < 0,5 cwl = avg_cwnd - diff  cwl = avg_cwnd + diff  last_cwl = cwnd  stable = 0  TCPToK, niveau TCP, partie deux

5.3  Résultats

Pour illustrer le fonctionnement de TCPToK nous avons choisi la 14-chaîne. Le comportement de la fenêtre de congestion donné en figure 5.3 est celui attendu: l'échange de jetons conduit à une fluctuation de CWND aux alentours de 5 jusqu'à la seconde 20 où un timeout est déclenché. La borne CWL rentre alors en action et au fur et à mesure des timeouts (secondes 28, 33, 39, 44) se réactualise de façon coordonnée à l'évolution de CWND. On remarque que jusqu'à la seconde 45 l'échange de jetons est quasiment le seul à intervenir dans la valeur de CWND. Puis finalement CWL est bloquée à la valeur 5, et le mécanisme des jetons vient en butée sur cette borne.

L'algorithme a alors réussi à fixer la limite des émissions à laquelle il obtient un débit maximal pour un minimum de congestion. Ce résultat est très visible à la figure 5.3 qui montre l'évolution du débit dans ce scénario.

On remarquera enfin que la limite CWL est réhaussée un peu avant la centième seconde, de par un retour efficient des jetons.

[évolution de CWND et de CWL dans la 14-chaîne avec TCPToK]   [débit dans la 14-chaîne avec TCPToK]

Figure 11 : Performances de TCPToK dans la 14-chaîne


TCPToK permet un débit dans ce scénario de 174 KBps, et souffre de 0,27% de perte sur les paquets qu'il émet. Ceci est à mettre en regard, à la fois avec les performances de TCP, soit un débit de 63 KBps et un pourcentage de perte de 6,19%, et les performances de TCP avec CWL constante, qui sont de 177 KBps et de 0,20% de perte.

Ainsi on a quasiment triplé le débit de TCP, et atteint notre objectif de coller à l'optimal du schéma où l'on positionne la limite CWL. Si la différence entre TCP et TCPToK est dans ce scénario la plus forte que nous ayons, la plupart de nos simulations montre un gain minimal de 35% sur le débit pour TCPToK, ce qui constitue un très bon résultat.
Pour rendre compte du changement de comportement que TCPToK apporte, nous avons comparé les débits avec l'accroissement de la longueur de la chaîne. Ceux-ci sont mis en parallèle à ceux de TCP dans la figure 5.3. Outre la forte amélioration du débit, le résultat caché réside dans le fait que les chaînes de longueur 10, 12 et 16 pourraient atteindre un meilleur débit (au vue des simulations) de telle sorte que celui-ci soit -- quasiment -- indépendant de la longueur de la chaîne, à l'instar du filaire. Savoir si cela était possible, faisait partie de notre questionnement initial.

[débit par rapport à la longueur de la chaîne]   [nombre de paquets en moyenne en attente dans les noeudsrouteurs (exemple: 14-chaîne)]

Figure 12 : Comportement de TCPToK


Enfin, au niveau de la réutilisation spatiale, on a regardé le nombre de paquets en attente de transmission à un temps t au niveau de chaque noeud. La figure 5.3 trace la moyenne sur tous les noeudsde ces informations pour TCP et TCPToK. On remarque que le nombre de paquets en transit dans le réseau sous TCPToK est presque constant, ce qui n'est pas le cas de TCP où les noeudsvont se retrouver avec de plus en plus de paquets à envoyer, marque d'une compétition d'accès forte. La régulation du débit de TCPToK permet bien une avancée des paquets de façon continue dans la chaîne.

Déchaîner
Une question incontournable est de savoir comment se comporte TCPToK dans d'autres configurations, comme la grille, la croix -- deux flux s'entrecoupants -- ou encore en présence de noeudsn'ayant pas la même capacité de débit (goulot d'étranglement). Le tableau 2 donne un récapitulatif des résultats expérimentés dans ces différents scénarios.

  débit TCP (KBps) débit TCPToK (Kbps)
(4,4)-grille 1 flux diagonal 171 200 (+17%)
(4,4)-grille 2 flux diagonaux 97 131 (+35%)
8-chaîne 4-goulot 139 187 (+35%)
12-chaîne 8-goulot 86 131 (+52%)
(12,4)-croix au noeud 6 (12-chaîne) 63 72 (+14%)
  (4-chaîne) 208 271 (+30%)
8-chaîne handoff 7s 73 154 (+111%)

Table 2 : TCPToK à l'épreuve de différents scénarios


On remarquera, dans le scénario de la croix, la forte inégalité au niveau du débit entre les deux flux, accentuée par TCPToK. [XBLG02] se sont intéressés au problème de l'équité au niveau TCP.
Un dernier résultat important de TCPToK est qu'il ne crée pas de gigue -- variation dans le délai de transfert d'un paquet, ce qui constitue l'un des critères sine qua non pour fournir de la qualité de service (QoS) dans un réseau.

5.4  Futur travail

Comme le montre la sous-section précédente, les résultats de TCPToK sont encourageants. Cependant il faut être conscient que sa conception souffre de beaucoup de manques. Voici quelques considérations qui devront être prises en compte.

6  Conclusion

Dans ce rapport nous avons essayé de caractériser le comportement de TCP dans un environnement ad hoc. Nous avons noté que sa propriété de régulation de débit était basée sur une vision de la congestion en filaire, qui est toute autre dans les réseaux ad hoc. Nous avons alors exhibé l'ensemble de congestion ad hoc qui prend source dans les couches MAC et réseau.

Il était alors naturel de se tourner vers des architectures inter-couches pour capturer le phénomène de congestion. Cependant outre les doutes sur les effets secondaires de ce type d'architecture, nous avons vu que le problème du comportement de TCP prenait source en lui même, à cause d'une régulation de son débit inadaptée au médium ad hoc et ses contraintes.
Nous nous sommes donc dirigés vers la conception d'un algorithme capable de s'adapter à un maximum de réseaux différents, et ce en testant sa capacité de réponse. TCPToK change le niveau de performances que l'on peut atteindre et réduit la congestion à un niveau où elle peut être appréhendée efficacement.

Au vue de l'importance démontrée d'un bon contrôle de débit et de congestion, ces mécanismes ne pourront pas être occultés, par exemple dans la conception d'un nouveau protocole de transport.

La communauté scientifique travaillant sur ces problématiques devrait être interessée par la modélisation de TCPToK, ou encore son amélioration et son évaluation et espérons que ceci la mènera sur la voie d'une adaptation réussie de TCP au monde ad hoc.

Références

[AA03]
Sorav Bansal Arup Acharya, Archan Mistra, Maca-p : A mac for concurrent transmissions in multi-hop wireless networks, IEEE PerCom (2003).

[AB04]
Raja Abdelmoumen and Chadi Barakat, Analysis of tcp latency over wireless links supporting fec/arq-sr for error recovery, IEEE International Conference on Communications (2004).

[AEP04]
Al Hanbali Ahmad, Altman Eitan, and Nain Philippe, A survey of tcp over mobile ad hoc networks, Tech. report, INRIA maestro, May 2004.

[CMP00]
Shiduan Cheng, Jian Ma, and Fei Peng, A proposal to apply ecn to wireless and mobile networks, Internet Society INET (2000).

[Com96]
Douglas Comer, Tcp/ip: architecture, protocoles, applications, 3ème ed., Mai 1996.

[CRR04]
Gustavo Carneiro, José Ruela, and Manuel Ricardo, Cross-layer design in 4g wireless terminals, IEEE Wireless Communications 11 (2004), no. 2.

[CRVP97]
Kartik Chandran, Sudarshan Raghunathan, S. Venkatesan, and Ravi Prakash, A feedback based scheme for improving tcp performance in ad-hoc wireless networks, International Conference on Distributed Computing Systems (1997).

[CXN03]
Kai Chen, Yuan Xue, and Klara Nahrstedt, On setting tcp's congestion window limit in mobile ad hoc networks, IEEE ICC (2003).

[CZ99]
A. Chockalingam and M. Zorzi, Wireless tcp performance with link layer fec/arq, IEEE ICC (1999).

[DB01]
Thomas D. Dyer and Rajendra V. Boppana, A comparison of tcp performance over three routing protocols for mobile ad hoc networks, MobiHoc (2001).

[DCY93]
A. DeSimone, M. Chuah, and O. Yue, Throughput performance of transport-layer protocols over wireless lans, GLOBECOM 1 (1993).

[FZL+03]
Zhenghua Fu, Petros Zerfos, Haiyun Luo, Songwu Lu, Lixia Zhang, and Mario Gerla, The impact of multihop wireless channel on tcp throughput and loss, IEEE INFOCOM (2003).

[HV99]
Gavin Holland and Nitin Vaidya, Analysis of tcp performance over mobile ad hoc networks.

[KKFT02]
S. Kopparty, S.V. Krishnamurthy, M. Faloutsos, and S.K. Tripathi, Split tcp for mobile ad hoc networks, IEEE GLOBECOM (2002).

[KTC01]
Dongkyun Kim, C.-K. Toh, and Yanghee Choi, Tcp-bus: Improving tcp performance in wireless ad hoc networks, IEEE Communications Society Journal on Communications and Networks 3 (2001), no. 2.

[LS99]
Jian Liu and Suresh Singh, Atcp: Tcp for mobile ad hoc networks, IEEE Journal on Selected Areas in Communications 19 (1999), no. 7.

[Pér03]
Mathias Péron, Etude de l'équité dans les réseaux ad hoc, Master's thesis, Ecole Normale Supérieure de Lyon, 2003.

[XBLG02]
Kaixin Xu, Sang Bae, Sungwook Lee, and Mario Gerla, Tcp behavior across multihop wireless networks and the wired internet, ACM WoWMoM (2002).

[XK02]
Liang-Liang Xie and P. R. Kumar, A network information theory for wireless communication: Scaling laws and optimal operation, IEEE Transactions on Information Theory (2002).

Equipe d'accueil

 

Ce stage s'est déroulé au sein de l'équipe systèmes distribués DSG46, l'un des groupes de recherche en informatique du Trinity College à Dublin. Le groupe, qui compte plus de cent personnes, se concentre sur quatre grands thèmes, les architectures middleware, la programmation distribuée, l'informatique omniprésente et enfin les réseaux mobiles.

C'est dans cette dernière thématique que M. Stephan Weber a encadré ce stage.

Il est à noter que le laboratoire est en train d'installer dans la ville de Dublin un réseau ad hoc fixe comportant une quinzaine de noeuds, nommé WAND47. Ce réseau devrait vite devenir un banc d'essai apprécié. Malheureusement, seul quatre noeudssont pour l'instant opérationnels, dans Westland Row48 où se trouve le laboratoire. J'ai été chargé d'effectuer un tracé de la topologie actuelle du réseau afin de pouvoir mener des comparaisons avec le simulateur ns2.


Figure 13 : Topologie du projet WAND, côté Westland row



Ressources éléctroniques disponibles à l'adresse
http://perso.ens-lyon.fr/mathias.peron/


1
The Defense Advanced Research Projects Agency
2
Institute of Electrical and Electronics Engineers
3
Medium Access Control
4
Distributed Coordination Function
5
Mobile Ad hoc NETworking
6
The Internet Engineering Task Force
7
Transmission Control Protocol
8
La spécification de TCP se trouve dans le RFC 793 (Request For Comments) publié en 1981
9
Retransmission TimeOut
10
Round-Trip Time
11
Transmission WiNDow
12
Allowed sender WiNDow
13
Congestion WiNDow
14
Slow Start (aux initiales pas forcément heureuses)
15
Congestion Avoidance
16
Sous-entendu 802.11b, opérant à un meilleur débit théorique de 11 Mbps
17
Routing Information Protocol
18
Ad hoc On Demand Distance Vector
19
Destination Sequence Distance Vector
20
Network Simulator 2. La page internet du projet: http://www.isi.edu/nsnam/ns/
21
Request To Send
22
Clear To Send
23
Transmission Range
24
Carrier Sense
25
User Datagram Protocol
26
Ce qui ne signifie pas 70% de "données" supplémentaires, par exemple dans le cas d'un transfert de fichiers, puisque UDP n'est pas fiable
27
Bit Error Rate
28
Selective ACKnowledgment. Les intervalles des numéros de séquence des paquets reçus sont placés par le récepteur dans les options de l'entête IP, informant ainsi exactement l'émetteur des paquets qu'il doit retransmettre.
29
Automatic Repeat reQuest
30
Forward Error Correction
31
Open Systems Interconnection
32
TCP-Feedback
33
Explicit Link Failure Notification
34
TCP Buffering capability and Sequence information
35
Explicit Congestion Notification, définit par le RFC 3168. L'idée fait suite au mécanisme RED (Random Early Detection) de gestion active des buffers, où tout simplement au lieu de positionner le drapeau CE, le paquet est détruit
36
En l'occurence le bit CE (Congestion Experienced), septième drapeau TOS (Type Of Service)
37
Les auteurs ont d'ailleurs écrit en 2001 un Internet-Draft à l'IETF pour proposer la standardisation d'ECN dans les réseaux sans fil
38
Ad Hoc TCP
39
variable max_dup_ack de l'algorithme 2.2.1
40
Les simulations n'incluaient pas de protocoles de routage et s'effectuaient en filaire !
41
Congestion Window Limit
42
Des transmissions parallèles sont possibles dans cet espace de compétition, à condition qu'elles puissent se synchroniser afin de ne pas interférer. Cette possibilité concerne uniquement deux flux dont les émetteurs ou les récepteurs sont en opposition comme le souligne [AA03], qui propose un algorithme de synchronisation
43
Cette analyse dépend bien sûr de la distance au noeudsdes zones TR et CS. Ici on se base sur les distances des cartes les plus courantes, comme l'équipe de M. Gerla, ce qui nous donne les chaînes de la figure 3.2
44
Round-Trip Hop-Count
45
En anglais tokens, d'où le nom de l'agorithme
46
Distributed Systems Group
47
WAN Dublin
48
Oscar Wilde est né au numéro 21 de cette rue en 1854

Ce document a été traduit de LATEX par HEVEA.