Un protocole de fiabilité basé sur un code à effacement ”on-the-fly”

Objectifs de l’étude et challenges liés aux réseaux anarchiques 

Comme l’ensemble des travaux sur les réseaux anarchiques, nous considérons que le réseau participe activement à la répartition du trafic avec des files d’attente à répartition équitable des pertes (Fair-Drop). Sous cette hypothèse nous adressons les points suivants.

Efficacité du débit reçu

 Dans ces réseaux, le débit d’émission n’est borné que par la vitesse de l’interface tandis que le débit de réception est limité par la capacité disponible sur le chemin utilisé par le flot. Si il est aisé de générer des paquets à la vitesse de l’interface via la répétition ou divers mécanismes de codage, la difficulté réside dans le fait que la réception de chacun de ces paquets doit apporter de l’information supplémentaire par rapport aux précédents. Tetrys permet une telle d’assurer une telle efficacité dès lors que la vitesse d’ajout des paquets source dans la fenêtre d’encodage correspond exactement à la bande passante disponible du récepteur. Etant donné qu’il n’est pas possible pour la source de prév ´ oir la vitesse de réception du destinataire durant le prochain RTT, nous proposons un mécanisme d’adaptation des paramètres de codage qui réduit considérablement la probabilité qu’un paquet reçu soit inutile et permet une efficacité proche de celle de TCP. 

Réduire le cout d’ émission 

Sur certaines topologies, le problème des paquets morts peut survenir malgré les files d’attente FairDrop. L’importance de ce problème augmente avec le débit d’émission des flots générateurs de paquets morts. Dans les réseaux anarchiques, les utilisateurs ne coopèrent pas entre eux et cherchent à réduire le coût associé au transfert (le temps nécessaire au transfert) via l’augmentation de leur débit. Or, si un utilisateur sait qu’en émettant au delà d’un certain débit limite D il ne pourra plus améliorer son débit de réception, ce dernier n’a aucun intérêt à dépasser D (les paquets en excès seront morts). Le coût est donc à la fois fonction du temps de transfert (débit auquel les paquets sont reçus) et du coût relatif à l’émission d’un paquet (débit d’émission). 0 D etv (Debit d′ emission) C(etv) paquets utiles paquets morts Figure 7.3: Efficacité (en termes de coût) du transfert en fonction du débit d’émission etv. Un utilisateur égo¨ıste cherchera donc à maximiser une fonction d’utilité du type C(etv) = CR · rtv − CE · etv avec etv (resp. rtv) le débit d’émission (resp. réception), CR l’utilité associée au débit de réception et CE le coût associé au débit émis. Comme l’illustre la figure 7.3, C(etv) atteint son maximum pour etv = D. Lorsque les files d’attente sont de type FairDrop, le débit limite D correspond au débit de la max-min-fairness pour le flot. Ainsi, sur la base de cette hypothèse de minimisation de coût, nous proposons ≪ Tetrys Min ≫ un mécanisme dont l’utilisation conjointe avec Fair-Drop, permet de minimiser le nombre de paquets morts et de s’approcher du max-min-fairness. La conception d’un tel mécanisme pour d’autres types de files d’attente (Drop-Tail ou RED) dépasse le cadre de cette étude.

Supporter les applications temps réel

 Le caractère opportuniste de TCP engendre bien souvent des pertes et une augmentation du délai de traversée des files d’attente [102] sur les flux UDP (potentiellement temps réel) avec lesquels ils partagent la bande passante. Bien que la cohabitation avec l’algorithme AIMD de TCP soit pénalisante, les applications temps réel de l’Internet basées sur UDP rencontrent des taux de pertes assez faibles et de faibles variations de délai ce qui constitue des conditions relativement favorables. Dans les réseaux anarchiques 7 , le taux de perte et leur répartition est par contre plus délicat à gérer et la question du support des applications temps réel dans ce contexte a été jusqu’à maintenant explicitement négligé. Emettre des paquets de redondance ´ Tetrys à la vitesse de l’interface est certes optimal en termes de délai de reconstruction des pertes mais peut mener à une sous utilisation du réseau et à un coût d’émission inutilement élevé. Etant donné que le mécanisme de configuration développé ´ section 3.4 supporte également des taux de pertes conséquents et des distributions variées, nous l’utiliserons pour le support des applications temps réel dans les réseaux anarchiques tout en minimisant le débit d’émission. 

Comparaison aux autres travaux du domaine 

Dans [90], Raghavan et Snoeren proposent Achoo, un mécanisme de transmission adapté aux réseaux anarchiques. La couche transport découpe les données émises par l’application en blocs appelés caravanes. Chaque caravane est émise au débit maximum possible. Ce débit maximum possible correspond à Ic/n avec Ic la capacité de l’interface et n le nombre de flots se partageant l’interface. L’émission de chaque caravane permet de sonder la bonne utilisation du débit de chacun des flots se partageant l’interface. Ainsi, si le débit utile d’un flot est inférieur à Ic/n (i.e. inférieur au débit équitable entre les différents flots se partageant l’interface), il tentera de réduire son débit d’émission sur la caravane suivante afin de favoriser les autres flots de l’interface qui peuvent éventuellement avoir une meilleur efficacité (et donc augmenter l’efficacité totale). Si cette réduction de débit à l’émission est suivie d’une réduction de débit à la réception 8 , le précèdent débit est conservé. L’augmentation du débit suit le même principe et s’effectue quand le débit d’émission est le même que le débit de réception. L’envoi des informations par caravanes implique qu’à la fin de l’émission de chacune d’entre-elles, des paquets relatifs à cette caravane sont envoyés durant un RTT alors qu’ils sont déjà intégralement reçus. Comme le montre la figure 7.4, cela peut réduire considérablement l’efficacité du mécanisme de transmission si le RTT est significatif. De plus, les auteurs ne considèrent pas non plus le cas de topologies défavorables qui peuvent générer des paquets morts. Cependant, cette proposition est adéquate pour gérer l’accès des différents flots à l’interface. De manière complémentaire, notre étude se focalisera sur la gestion d’un unique flot afin de réduire la proportion de paquets morts et d’améliorer l’équité à l’échelle du réseau plutˆot que pour une interface donnée. Bien entendu il n’y a des pertes que si il y a de la congestion. Dans les réseaux ante-contrˆole de congestion, les flots sources ne dépassaient pas la capacité du réseau et il n’y avait donc que rarement des pertes. 8. Le récepteur émet périodiquement des acquittements qui indique notamment le débit utile.Les auteurs de ont proposé l’utilisation des codes Tornado comme mécanisme de transmission pour la livraison de flux dans l’Internet. Plus récemment, le développement des LT-codes a motivé les auteurs de [91] qui proposent de les utiliser. Leur évaluation est basée sur la théorie des jeux avec laquelle ils comparent l’efficacité de TCP et des codes fontaines. La topologie utilisée dans leur modèle n’a qu’un seul goulot d’étranglement et il n’y a donc, par définition, aucune chance d’avoir des paquets morts. Dans [89], Bonald et Al. ont montré que sur la plupart des topologies de base, la perte d’efficacité est tolérable et sans commune mesure avec les préjugés sur les causes possibles du congestion collapse. Cependant ils ne considèrent la traversée que d’une seule des topologies de base à la fois (triangle, chaine, arbre montant ou descendant). Le coût de l’anarchie qu’ils mesurent est donc à pondérer avec le nombre d’éléments de ce type qu’il y aurait à traverser sur des topologies plus réalistes. Comparé à [91] et [89], nous évaluons de façon réaliste un réseau anarchique par l’implémentation complète de la pile protocolaire et par le choix des topologies utilisées (c.a.d. avec un fort potentiel de paquets morts). De plus et contrairement à [91], nous aborderons les aspects d’équité. A l’inverse, les travaux des auteurs de [89] ayant déjà abo ´ rdé les problèmes de stabilité du processus stochastique relatif au nombre de flots présents dans le réseau, nous nous focaliserons que sur les performances des flots longs.