Recommandations sur la gestion de file d'attente et l'évitement d'encombrement dans l'Internet

Statut de ce mémoire

Le présent mémoire apporte des informations pour la communauté de l'Internet. Il ne spécifie aucune forme de norme de l'Internet. La distribution du présent mémoire n'est soumise à aucune restriction

Notice de copyright

Copyright (C) The Internet Society (1998). Tous droits réservés.

Résumé

Le présent mémoire présente deux recommandations à la communauté de l'Internet concernant les mesures destinées à améliorer et préserver les performances de l'Internet. Il présente une forte recommandation en faveur de l'essai, la normalisation, et le large déploiement d'une gestion active de file d'attente dans les routeurs, pour améliorer les performances de l'Internet actuel. Il invite instamment également à un effort concerté de recherche, de mesures et au développement final de mécanismes de routeurs pour protéger l'Internet contre des flux qui ne sont pas suffisamment élaborés pour effectuer des notifications d'encombrement.

1.   Introduction

L'architecture du protocole Internet se fonde sur un service de paquets sans connexion de bout en bout utilisant le protocole IP. Les avantages de cette conception sans connexion, sa souplesse et sa robustesse, ont été amplement démontrés. Cependant, ces avantages ont un coût : une conception soignée est nécessaire pour fournir un bon service en présence d'une charge élevée. En fait, le manque d'attention à la dynamique de la transmission de paquet peut résulter en une sévère dégradation de service ou "débâcle de l'Internet". Ce phénomène a été observé pour la première fois durant la première phase de croissance de l'Internet au milieu de années 1980 [RFC0896], et est désigné par l'appellation technique de "collapsus d'encombrement".

Le remède original à la débâcle de l'Internet a été fourni par Van Jacobson. Au début de 1986, Jacobson a développé les mécanismes d'évitement d'encombrement qui sont maintenant exigés dans les mises en œuvre de TCP [Jacobson88, RFC1122]. Ces mécanismes qui fonctionnent dans les hôtes amènent les connexions TCP à "sauvegarder" durant les phases d'encombrement. On dit que les flux TCP "répondent" aux signaux d'encombrement (c'est-à-dire, aux abandons de paquets) provenant du réseau. Ce sont principalement ces algorithmes d'évitement d'encombrement sur TCP qui empêchent le collapsus d'encombrement de l'Internet actuel.

Cependant, ceci n'est pas la fin de l'histoire. D'importantes recherches ont été effectuées sur la dynamique de l'Internet depuis 1988, et l'Internet a grandi. Il est devenu évident que les mécanismes TCP d'évitement d'encombrement de la [RFC2001] bien que nécessaires et puissants, ne sont pas suffisants pour fournir un bon service dans toutes les circonstances. Fondamentalement, il y a une limite à la quantité de contrôle qui peut être accompli depuis les extrémités du réseau. Certains mécanismes doivent être ajoutés dans les routeurs pour compléter les mécanismes d'évitement d'encombrement des points d'extrémité.

Il faut faire une distinction entre les deux classes d'algorithmes de routeur qui se rapportent au contrôle d'encombrement : les algorithmes "de gestion de file d'attente" et ceux de "programmation". Pour donner une approximation grossière, les algorithmes de gestion de file d'attente gèrent la longueur des files d'attente des paquets en abandonnant des paquets lorsque nécessaire ou approprié, alors que les algorithmes de programmation déterminent quel sera le prochain paquet envoyé, et ils sont principalement utilisés pour gérer l'allocation de bande passante entre les flux. Bien que ces deux mécanismes de routeurs entretiennent des relations étroites, ils s'adressent à des questions de performances assez différentes.

Le présent mémoire se concentre sur deux questions de performance des routeurs. La première question est le besoin d'une formé évoluée de gestion de la file d'attente au routeur qu'on appellera "gestion active de file d'attente." La Section 2 récapitule les avantages de la gestion active de file d'attente. La Section 3 décrit un mécanisme recommandé de gestion active de file d'attente, appelé détection précoce aléatoire (RED, Random Early Detection). Il est prévu que l'algorithme RED soit utilisé avec des algorithmes de programmation très divers, qu'il puisse être mis en œuvre de façon relativement efficace, et qu'il apporte une amélioration significative des performances de l'Internet.

La deuxième question, exposée à la Section 4 du présent mémoire, est celle de la possibilité d'un collapsus d'encombrement de l'Internet dû à l'avenir à des flux qui ne savent pas répondre aux indications d'encombrement, ou ne le savent pas suffisamment. Malheureusement, il n'y a pas de consensus sur les solutions de contrôle de l'encombrement causé par de tels flux agressifs ; des recherches et des ressources d'ingénierie significatives seront nécessaires avant qu'une solution se dégage. Il est impératif que ce travail soit poursuivi avec énergie pour assurer la stabilité future de l'Internet.

La Section 5 conclut le présent mémoire par un ensemble de recommandations à l'IETF au sujet de ces questions.

L'exposé du présent mémoire s'applique au trafic "au mieux" (best effort). L'architecture Internet des services intégrés, qui donne un mécanisme de protection des flux individuels contre l'encombrement, introduit ses propres algorithmes de gestion de file d'attente et de programmation [RFC2211, RFC2212]. De même, l'exposé sur les exigences de gestion de file d'attente et de contrôle d'encombrement pour les services différenciés est une question distincte. Cependant, on ne s'attend pas à ce que la mise en place de services intégrés et de services différenciés diminue de façon significative l'importance des questions de trafic au mieux exposées dans le présent mémoire.

La préparation du présent mémoire est le résultat des discussions passées sur les performances de bout en bout, l'encombrement dans l'Internet, et sur RED dans le groupe de recherche Bout-en bout au sein de l'équipe de recherche de l'Internet (IRTF).

2.   Le besoin d'une gestion active de file d'attente

La technique traditionnelle pour la gestion des longueurs de file d'attente chez un routeur est d'établir une longueur maximum (en termes de paquets) pour chaque file d'attente, d'accepter ces paquets pour la file d'attente jusque à ce que la longueur maximum soit atteinte, puis de rejeter (abandonner) les paquets entrants suivants jusque à ce que la file d'attente diminue à cause de la transmission d'un paquet de la file d'attente. Cette technique est connue sous le nom de "abandon du bout de la queue" (tail drop), car le paquet arrivé le plus récemment (c'est-à-dire, celui qui est au bout de la queue) est abandonné lorsque la file d'attente est pleine. Cette méthode a bien servi l'Internet pendant des années, mais elle présente deux inconvénients importants.

(1)   Verrouillage

Dans certaines situations, l'exclusion du bout de la queue permet à une seule connexion ou à quelques flux de monopoliser l'espace de file d'attente, empêchant ainsi les autres connexions d'obtenir de l'espace dans la file d'attente. Ce phénomène de "verrouillage" est souvent le résultat d'effets de synchronisation ou autres effets temporels.

(2)   Files d'attente pleines

La discipline de l'abandon du bout de la queue permet aux files d'attente de conserver un statut de file d'attente complète (ou presque complète) pendant de longues périodes car l'abandon du bout de la queue ne signale l'encombrement (via un abandon de paquet) que si la file d'attente est devenue pleine. Il est important de réduire la taille de la file d'attente en régime permanent, et c'est peut être l'objectif le plus important de la gestion de file d'attente.

Une hypothèse naïve serait ici de supposer qu'il y a un simple arbitrage entre retard et débit, et que la recommandation que les files d'attentes soient conservées dans un état "non plein" traduit essentiellement la recommandation que le faible retard de bout en bout soit plus important qu'un fort débit. Cependant, cela ne prend pas en compte le rôle critique que jouent les salves de paquets dans les performances de l'Internet. Bien que TCP établisse des contraintes sur la taille de fenêtre d'un flux, les paquets arrivent souvent par salves aux routeurs [Leland94]. Si la file d'attente est pleine ou presque pleine, une salve entrante va causer l'abandon de plusieurs paquets. Il peut en résulter une synchronisation globale de ralentissement des flux, suivie par une période durable de sous utilisation de la liaison, réduisant le débit global.

L'objet de la mise en mémoire tampon sur le réseau est d'absorber les salves de données et de les transmettre durant les salves de silence qui (on l'espère) vont suivre. Cela est essentiel pour permettre la transmission de salves de données. La raison pour laquelle on veut avoir des files d'attente normalement petites dans les routeurs devrait être claire : on veut avoir la capacité de file d'attente pour absorber les salves. Le résultat contraire à l'intuition est que d'entretenir des files d'attente normalement petites peut déboucher sur un débit supérieur ainsi que sur un plus petit délai de bout en bout. En bref, les limites des files d'attente ne devraient pas refléter les files d'attente d'état permanent qu'on veut conserver dans le réseau ; elles devraient plutôt refléter la taille des salves qu'on a besoin d'absorber.

À côté de l'abandon du bout de la file d'attente, on peut appliquer deux autres disciplines de file d'attente lorsque celle-ci est pleine, qui sont "l'abandon aléatoire lorsque c'est plein" ou "l'abandon du début lorsque la file est pleine". Dans la discipline d'abandon aléatoire lorsque c'est plein, un routeur abandonne un paquet choisi de façon aléatoire dans la file d'attente (ce qui peut être une opération coûteuse, car elle exige O(n) balayages complets de la file d'attente des paquets) lorsque la file d'attente est pleine et qu'un nouveau paquet arrive. Dans la discipline "d'abandon du début lorsque la file est pleine" [Lakshman96], le routeur abandonne le paquet au début de la queue lorsque celle-ci est pleine et qu'un nouveau paquet arrive. Ces deux disciplines résolvent le problème du verrouillage, mais ni l'une ni l'autre ne résolvent le problème des files d'attentes pleines décrit ci-dessus.

On sait en général comment résoudre le problème des files d'attente pleines sur les flux qui "répondent", c'est-à-dire, les flux qui ralentissent en réponse à une notification d'encombrement. Dans l'Internet actuel, les paquets abandonnés servent de mécanisme critique de notification d'encombrement aux nœuds d'extrémité. La solution au problème des files d'attente pleines est que les routeurs abandonnent les paquets avant qu'une file d'attente ne soit pleine, de façon à ce que les nœuds d'extrémité puissent répondre à l'encombrement avant que les mémoire tampon ne débordent. On appelle une telle approche préventive "gestion active de file d'attente". En abandonnant les paquets avant le débordement des mémoires tampon, la gestion active de file d'attente permet aux routeurs de contrôler le moment et la quantité de paquets à abandonner. La section suivante présente RED, un mécanisme de gestion active de file d'attente qui résout les deux problèmes cités ci-dessus (pour des flux qui "répondent").

En résumé, un mécanisme de gestion active de file d'attente peut fournir les avantages suivants pour les flux qui "répondent".

(1)   Réduire le nombre de paquets abandonnés dans les routeurs

Les salves de paquet sont un aspect inévitable des réseaux par paquet [Willinger95]. Si tout l'espace de file d'attente dans un routeur est déjà affecté au trafic "d'état permanent" ou si l'espace de mémoire tampon est inadéquat, le routeur n'aura alors aucune capacité pour mettre les salves en mémoire tampon. En maintenant petite la taille moyenne de file d'attente, la gestion active de file d'attente donne une plus grande capacité d'absorption des salves qui surviennent naturellement sans abandonner de paquets.

De plus, sans une gestion active de file d'attente, plus de paquets seront abandonnés lorsque une file d'attente déborde. Cela n'est pas souhaitable pour plusieurs raisons. Tout d'abord, avec une file d'attente partagée et la discipline d'abandon du bout de la file d'attente, une synchronisation globale inutile du ralentissement des flux peut résulter en une diminution de l'utilisation moyenne de la liaison, et donc en une diminution du débit du réseau. Ensuite, TCP récupère plus difficilement d'une salve d'abandons de paquets que de l'abandon d'un seul paquet. Troisièmement, des abandons inutiles de paquet représentent un gâchis possible de bande passante sur le chemin vers le point d'abandon.

On note qu'alors que RED peut gérer les longueurs de file d'attente et réduire la latence de bout en bout même en l'absence de contrôle d'encombrement de bout en bout, RED ne sera capable de réduire l'abandon de paquet que dans un environnement qui continue d'être dominé par le contrôle d'encombrement de bout en bout.

(2)   Fournir un service interactif à plus faible délai

En conservant petite la taille moyenne de la file d'attente, la gestion de file d'attente va réduire les délais subis par les flux. Ceci est particulièrement important pour les applications interactives telles que les courts transferts sur la Toile, le trafic Telnet, ou les sessions audio-vidéo interactives, dont les performances subjectives (et objectives) sont meilleures lorsque le délai de bout en bout est faible.

(3)   Éviter le comportement de verrouillage

La gestion active de file d'attente peut empêcher le comportement de verrouillage en s'assurant qu'il y aura presque toujours une mémoire tampon disponible pour un paquet entrant. Pour la même raison, la gestion active de file d'attente peut empêcher un biais du routeur à l'encontre des flux à faible bande passante mais très saccadés.

Il est clair que le verrouillage est indésirable parce qu'il constitue une injustice criante entre les groupes de flux. Cependant, on ne va pas appeler cet avantage "égalité accrue", parce que l'égalité parfaite entre les flux nécessite un état par flux, ce qui n'est pas fourni par la gestion de file d'attente. Par exemple, dans un routeur qui utilise la gestion de file d'attente mais seulement la programmation FIFO, deux flux TCP peuvent recevoir des bandes passantes très différentes simplement parce que ils ont des délais d'aller-retour différents [Floyd91], et un flux qui n'utilise pas le contrôle d'encombrement reçoit plus de bande passante qu'un flux qui l'utilise. L'état flux par flux pour réaliser l'égalité parfaite pourrait être entretenu par un algorithme de programmation flux par flux tel que la mise en file d'attente équitable (FQ, Fair Queueing) [Demers90], ou un algorithme de programmation fondé sur la classe tel que CBQ [Floyd95], par exemple.

D'un autre côté, la gestion active de file d'attente est nécessaire même pour les routeurs qui utilisent des algorithmes de programmation flux par flux tels que FQ ou des algorithmes de programmation fondés sur la classe tels que CBQ. La raison en est que par eux-mêmes les algorithmes de programmation flux par flux ne font rien pour contrôler la taille globale de file d'attente des queues individuelles. la gestion active de file d'attente est nécessaire pour contrôler les tailles moyennes globales de file d'attente, de telle sorte que les salves arrivantes puissent être traitées sans abandon de paquet. De plus, la gestion active de file d'attente devrait être utilisée pour contrôler la taille de la file d'attente pour chaque flux ou classe individuel, de façon à ce qu'ils ne subissent pas de forts retards inutiles. Donc, la gestion active de file d'attente devrait être appliquée entre classes ou flux aussi bien qu'au sein de chaque classe ou flux.

En bref, les algorithmes de programmation et la gestion de file d'attente devraient être perçus comme complémentaires, et non comme se remplaçant les uns les autres. En particulier, il y a eu des mises en œuvre de gestion de file d'attente qui ont été ajoutées à FQ, et des travaux sont en cours pour ajouter la gestion de file d'attente RED à CBQ.

3.   Algorithme "RED" de gestion de file d'attente

La détection précoce aléatoire (RED, Random Early Detection) est un algorithme de gestion active de file d'attente pour les routeurs qui présente les avantages de performances pour l'Internet cités dans la section précédente [RED93]. À la différence des algorithmes traditionnels de gestion de file d'attente, qui n'abandonnent les paquets que lorsque la mémoire tampon est pleine, l'algorithme RED abandonne de façon probabiliste les paquets arrivants. La probabilité d'abandon augmente avec la croissance de la taille moyenne estimée de la file d'attente. Noter que RED répond à une longueur de file d'attente moyenne sur une période de temps, et non à une taille instantanée. Et donc, si la file d'attente a été presque vide dans le "passé récent", RED ne va pas tendre à abandonner de paquets (sauf, bien sûr, débordement de la file d'attente !) D'un autre côté, si la file d'attente a récemment été relativement pleine, indiquant un encombrement persistant, les paquets nouveaux arrivants auront plus de chances d'être abandonnés.

L'algorithme RED lui-même comporte deux parties principales : l'estimation de la taille moyenne de la file d'attente et la décision d'abandonner ou non un paquet entrant.

(a)   Estimation de la taille moyenne de file d'attente

RED estime la taille moyenne de la file d'attente soit dans le chemin de transmission en utilisant une simple moyenne mobile à pondération exponentielle (telle que celle présentée dans l'Appendice A de [Jacobson88]) soit en arrière plan (c'est-à-dire, pas dans le chemin de transmission) en utilisant un mécanisme similaire.

Note : La taille de la file d'attente peut se mesurer en paquets ou en octets. Cette question est brièvement discutée dans [RED93] au paragraphe "Travaux futurs".

Note : Lorsque la taille moyenne de la file d'attente est calculée dans le chemin de transmission, il y a le cas particulier de l'arrivée d'un paquet alors que la file d'attente est vide. Dans ce cas, le calcul de la taille moyenne de file d'attente doit prendre en compte le temps passé depuis que la file d'attente est vide. Ceci est discuté plus en détails dans [RED93].

(b)   Décision d'abandon de paquet

Dans la seconde portion de l'algorithme, RED décide de l'abandon ou non d'un paquet entrant. C'est l'algorithme particulier de RED pour l'abandon qui donne l'amélioration des performances pour les flux qui "répondent". Deux paramètres RED, minth (seuil minimum) et maxth (seuil maximum) tiennent une place prééminente dans ce processus de décision. Minth spécifie la taille moyenne de la file d'attente *en dessous de laquelle* aucun paquet ne sera abandonné, alors que maxth spécifie la taille moyenne de file d'attente *au-dessus de laquelle* tous les paquets seront abandonnés. Comme la taille moyenne de file d'attente varie de minth à maxth, les paquets seront abandonnés avec une probabilité qui varie de façon linéaire de 0 à maxp.

Note : Une méthode simpliste pour mettre cela en œuvre serait de calculer un nouveau nombre aléatoire à chaque arrivée de paquet, puis de comparer ce nombre à la probabilité ci-dessus qui varie de 0 à maxp. Une mise en œuvre plus efficace, décrite dans [RED93], calcule un nombre aléatoire *une seule fois* pour chaque paquet abandonné.

Note : La décision d'abandonner ou non un paquet entrant peut être faite en "mode paquet", ignorant la taille du paquet, ou en "mode octet", en prenant en compte la taille du paquet entrant. Les implications du choix entre mode paquet et mode octet sur les performances sont discutées plus en détails dans [Floyd97].

RED contrôle effectivement la taille moyenne de file d'attente tout en s'accommodant sans perte des salves de paquets. L'utilisation de nombres aléatoires par RED casse le processus de synchronisation qui conduirait au phénomène de verrouillage.

Il y a eu plusieurs mises en œuvre de RED dans les routeurs, et des articles ont été publiés qui rapportent l'expérience de ces mises en œuvre ([Villamizar94], [Gaynor96]). Des rapports supplémentaires sur ces expériences de mise en œuvre seraient les bienvenus et seraient publiés sur la page de la Toile consacrée à RED [REDWWW].

Toutes les preuves empiriques disponibles montrent que le déploiement de mécanismes de gestion active de file d'attente dans l'Internet présenteraient des avantages substantiels. Il n'y a pas d'inconvénient visible à l'utilisation de l'algorithme RED, et de nombreux avantages. Par conséquent, nous pensons que l'algorithme RED de gestion active de file d'attente devrait être largement déployé.

On devrait noter qu'il y a des scénarios extrêmes pour lesquels RED ne sera d'aucun secours, bien qu'il ne cause pas de dommages et puisse encore aider. Un exemple d'un tel scénario serait celui d'un grand nombre de flux, dont chacun serait si petit que leur partage équitable serait inférieur à un seul paquet par délai d'aller-retour (RTT).

4.   Gestion des flux agressifs

Une des clés du succès de l'Internet a été les mécanismes d'évitement d'encombrement de TCP. Comme TCP "sauvegarde" durant l'encombrement, un grand nombre de connexions TCP peuvent partager une seule liaison encombrée d'une façon telle que la bande passante soit partagée d'une façon raisonnablement équitable entre des flux d'une situation similaire. Le partage équitable de la bande passante entre les flux dépend du fait que tous les flux fonctionnent en principe avec les mêmes algorithmes d'évitement d'encombrement, conformément à la spécification TCP actuelle [RFC1122].

On introduit le terme de "TCP compatible" pour un flux qui se comporte dans l'encombrement comme un flux produit par un TCP conforme. Un flux TCP compatible répond à une notification d'encombrement, et n'utilise en état permanent pas plus de bande passante qu'un TCP conforme fonctionnant dans des conditions comparables (taux d'abandon, RTT, MTU, etc.)

Il est pratique de répartir les flux en trois classes : (1) flux TCP compatibles, (2) flux qui ne répondent pas, c'est-à-dire, flux qui ne ralentissent pas lorsque survient un encombrement, et (3) flux qui répondent mais ne sont pas compatibles TCP. Les deux dernières classes contiennent des flux plus agressifs qui présentent des menaces significatives pour les performances de l'Internet, comme nous allons le voir maintenant.

o   Flux qui ne répondent pas

Il y a un ensemble croissant d'applications fondées sur UDP dont les algorithmes d'évitement d'encombrement sont inadéquats ou non existants (c'est-à-dire que le flux ne ralentit pas à réception d'une notification d'encombrement). De telles applications UDP incluent des applications en direct comme le vocal et la vidéo, et aussi du transport de données en vrac en diffusion groupée [SRM96]. Si aucune mesure n'est prise, ces flux qui ne répondent pas pourraient conduire à un nouveau collapsus d'encombrement.

En général, toutes les applications en direct fondées sur UDP devraient comporter des mécanismes d'évitement d'encombrement. Par exemple, des recherches récentes ont montré la possibilité d'incorporation de mécanismes d'évitement d'encombrement tels que la diffusion groupée en couches pilotées par le receveur (RLM, Receiver-driven Layered Multicast) au sein d'applications en direct fondées sur UDP comme la vidéo par paquet [McCanne96; Bolot94]. D'autres recherches et développements en cours pour réaliser l'évitement d'encombrement pour les applications en direct seront très importants.

Cependant, il sera aussi important que le réseau soit capable de se protéger lui-même contre les flux qui ne répondent pas, et les mécanismes pour le réaliser doivent être développés et déployés. Le déploiement de tels mécanismes donnerait une incitation pour que chaque application en direct réponde en incorporant son propre contrôle d'encombrement.

o   Protocoles de transport non compatibles TCP

La seconde menace provient des mises en œuvre de protocoles de transport qui répondent à la notification d'encombrement mais, soit délibérément, soit à cause de mises en œuvre fautives, ne sont pas compatibles TCP. De telles applications peuvent s'attribuer une part inéquitable de la bande passante du réseau.

Par exemple, la popularité de l'Internet a causé une prolifération du nombre de mises en œuvre de TCP. Certaines d'entre elles ne réussissent pas à mettre correctement en œuvre les mécanismes TCP d'évitement d'encombrement à cause d'une mise en œuvre déficiente. D'autres peuvent être délibérément mises en œuvre avec des algorithmes d'évitement d'encombrement qui sont plus agressifs dans leur utilisation de la bande passante que les autres mises en œuvre de TCP ; cela permet à un fabricant de prétendre avoir un "TCP plus rapide". La conséquence logique de telles mises en œuvre serait une spirale de mises en œuvre de TCP d'une agressivité croissante, ramenant au point où il n'y a en fait plus d'évitement d'encombrement et que l'Internet est encombré de façon chronique.

Noter qu'il y a une façon bien connue pour réaliser des performances plus agressives de TCP sans même changer TCP : ouvrir plusieurs connexions avec le même site, comme cela a été fait sur certains navigateurs de la Toile.

L'augmentation prévue de flux plus agressifs de ces deux classes dans le trafic total de l'Internet fait clairement peser une menace sur l'avenir de l'Internet. Il y a un besoin urgent de mesures des conditions actuelles et de recherches sur les divers moyens de gérer de tels flux. Il y a de nombreuses difficultés pour identifier et isoler les flux qui ne répondent pas ou qui ne sont pas compatibles TCP à un coût de routeur acceptable. Finalement, il y a peu de preuves par des mesures ou des simulations disponibles sur le taux auquel ces menaces pourraient se réaliser, ou sur les bénéfices attendus d'algorithmes de routeur pour gérer de tels flux.

Il y a un problème sur la granularité appropriée pour un "flux". Il y a peu de réponses "naturelles" : 1) une connexion TCP ou UDP (adresse/accès de source, adresse/accès de destination) ; 2) une paire d'hôtes de source/destination ; 3) un hôte de source donné ou un hôte de destination donné. On peut supposer que la paire hôte de source/destination donne la granularité la plus appropriée dans de nombreuses circonstances. Cependant, il est possible que des fabricants/fournisseurs différents établissent des granularités différentes pour définir un flux (comme moyen de se "distinguer" les uns des autres) ou que des granularités différentes pourraient être choisies pour différents endroits du réseau. Il peut se faire que la granularité soit moins importante que le fait qu'on a à traiter plus de flux qui ne répondent pas à *une certaine* granularité. La granularité des flux pour la gestion de l'encombrement est, au moins en partie, une question de politique qui doit être examinée au sein de la plus large communauté de l'IETF.

5.   Conclusions et recommandations

Cet exposé nous conduit à proposer les recommandations suivantes à l'IETF et à la communauté globale de l'Internet.

o   Recommandation 1 :

Les routeurs de l'Internet devraient mettre en œuvre un mécanisme de gestion active de file d'attente pour gérer les longueurs des files d'attente, pour réduire les délais de bout en bout, réduire l'abandon de paquet, et éviter les phénomènes de verrouillage au sein de l'Internet.

Le mécanisme par défaut pour gérer les longueurs de files d'attente pour atteindre ces objectifs dans les files d'attentes FIFO est la détection précoce aléatoire (RED, Random Early Detection) [RED93]. Sauf si un développeur a des raisons pour fournir un autre mécanisme équivalent, nous recommandons d'utiliser RED.

o   Recommandation 2 :

Il est urgent de commencer ou continuer des efforts de recherche, d'ingénierie, et de mesures pour contribuer à la conception de mécanismes pour traiter les flux qui ne répondent pas à la notification d'encombrement ou qui répondent mais sont plus agressifs que TCP.

Bien qu'il y ait déjà eu quelques déploiements limités de RED dans l'Internet, on peut s'attendre à une large mise en œuvre et un grand déploiement de RED conformément à la recommandation 1 qui vont poser un grand nombre de problèmes d'ingénierie. Par exemple, les questions de mise en œuvre pour les routeurs en Gigabits, l'utilisation de RED dans les commutateurs de couche 2, et l'éventuelle utilisation de considérations supplémentaires, comme la priorité, pour décider quels paquets abandonner.

On souligne encore que la large mise en œuvre de RED et son déploiement ne vont pas, par sa seule vertu, réaliser l'objectif de la recommandation 2.

La large mise en œuvre de RED et son déploiement vont aussi permettre l'introduction d'autre nouvelles fonctionnalités dans l'Internet. Un exemple d'une fonctionnalité possible serait l'ajout de la notification explicite d'encombrement [RFC2481] à l'architecture de l'Internet, comme mécanisme de notification d'encombrement en plus de l'abandon de paquet. Un second exemple de nouvelle fonctionnalité serait la mise en œuvre de files d'attente avec des paquets de priorités d'abandon différentes ; les paquets seraient transmis dans l'ordre dans lequel ils sont arrivés, mais durant les périodes d'encombrement les paquets de plus faible priorité d'abandon seraient abandonnés de préférence.

6.   Références

[Bolot94]   Bolot, J.-C., Turletti, T., and Wakeman, I., "Scalable Feedback Control for Multicast Video Distribution in the Internet", ACM SIGCOMM '94, septembre 1994.

[Demers90]   Demers, A., Keshav, S., and Shenker, S., "Analysis and Simulation of a Fair Queueing Algorithm, Internetworking: Research and Experience", Vol. 1, 1990, pp. 3-26.

[Floyd91]   Floyd, S., "Connections with Multiple Congested Gateways in Packet-Switched Networks Part 1: One-way Traffic", Computer Communications Review, Vol.21, n° 5, octobre 1991, pp. 30-47. URL, http://ftp.ee.lbl.gov/floyd/.

[Floyd95]   Floyd, S., and Jacobson, V., "Link-sharing and Resource Management Models for Packet Networks", IEEE/ACM Transactions on Networking, Vol. 3 n° 4, pp. 365-386, août 1995.

[Floyd97]   Floyd, S.," RED: Discussions of Byte and Packet Modes", mars 1997. URL, http://www-nrg.ee.lbl.gov/floyd/REDaveraging.txt.

[Gaynor96]   Gaynor, M., "Proactive Packet Dropping Methods for TCP Gateways", octobre 1996, URL, http://www.eecs.harvard.edu/~gaynor/final.ps.

[Jacobson88]   V. Jacobson, "Congestion Avoidance and Control", ACM SIGCOMM '88, août 1988.

[Lakshman96]   T. V. Lakshman, Arnie Neidhardt, Teunis Ott, "The Drop From Front Strategy in TCP Over ATM and Its Interworking with Other Control Features", Infocom 96, MA28.1.

[Leland94]   W. Leland, M. Taqqu, W. Willinger, and D. Wilson, "On the Self-Similar Nature of Ethernet Traffic (Extended Version)", IEEE/ACM Transactions on Networking, 2(1), pp. 1-15, février 1994.

[McCanne96]   McCanne, S., Jacobson, V., and M. Vetterli, "Receiver-driven Layered Multicast", ACM SIGCOMM

[RED93]   Floyd, S., and Jacobson, V., "Random Early Detection gateways for Congestion Avoidance", IEEE/ACM Transactions on Networking, V.1 n° 4, août 1993, pp. 397-413. Aussi disponible sur http://ftp.ee.lbl.gov/floyd/red.html.

[REDWWW]   Floyd, S., "The RED Web Page", 1997, URL, http://ftp.ee.lbl.gov/floyd/red.html.

[RFC0896]   J. Nagle, "Contrôle de l'encombrement dans l'inter-réseau IP/TCP", janvier 1984.

[RFC1122]   R. Braden, "Exigences pour les hôtes Internet – couches de communication", STD 3, octobre 1989.

[RFC2001]   W. Stevens, "Algorithmes de démarrage lent, d'évitement d'encombrement, de retransmission rapide et de récupération rapide dans TCP", janvier 1997. (Obsolète, voirRFC2581) (P.S.)

[RFC2212]   S. Shenker, C. Partridge, R. Guerin, "Spécification de la qualité de service garantie", septembre 1997. (P.S.)

[RFC2211]   J. Wroclawski, "Spécification du service d'élément de réseau à charge contrôlée", septembre 1997. (P.S.)

[RFC2481]   K. Ramakrishnan, S. Floyd, "Proposition d'ajout de la notification d'encombrement explicite (ECN) à IP", janvier 1999.

[SRM96]   Floyd. S., Jacobson, V., McCanne, S., Liu, C., and L. Zhang, "A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing", ACM SIGCOMM '96, pp 342-355.

[Villamizar94]   Villamizar, C., and Song, C., "High Performance TCP in ANSNET", Computer Communications Review, V. 24 N. 5, octobre 1994, pp. 45-60. URL, http://ftp.ans.net/pub/papers/tcp-performance.ps.

[Willinger95]   W. Willinger, M. S. Taqqu, R. Sherman, D. V. Wilson, "Self-Similarity Through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level", ACM SIGCOMM '95, pp. 100- 113, août 1995.

Considérations pour la sécurité

Bien que la sécurité soit une question très importante, elle est largement étrangère aux questions de performances exposées dans le présent mémoire. On note cependant que des attaques de déni de service peuvent créer des flux de trafic non interactifs qu'on ne peut pas distinguer des flux des applications isochrones normales à forte bande passante, et le mécanisme suggéré dans la recommandation 2 seront également applicables à de telles attaques.

Adresse des auteurs

Déclaration complète de droits de reproduction

Copyright (C) The Internet Society (1998). Tous droits réservés.

Ce document et les traductions de celui-ci peuvent être copiés et diffusés, et les travaux dérivés qui commentent ou expliquent autrement ou aident à sa mise en œuvre peuvent être préparés, copiés, publiés et distribués, partiellement ou en totalité, sans restriction d'aucune sorte, à condition que l'avis de copyright ci-dessus et ce paragraphe soit inclus sur toutes ces copies et œuvres dérivées. Toutefois, ce document lui-même ne peut être modifié en aucune façon, par exemple en supprimant le droit d'auteur ou les références à l'Internet Society ou d'autres organisations Internet, sauf si c'est nécessaire à l'élaboration des normes Internet, auquel cas les procédures pour les droits de reproduction définis dans les processus des normes pour l'Internet doivent être suivies, ou si nécessaire pour le traduire dans des langues autres que l'anglais.

Les permissions limitées accordées ci-dessus sont perpétuelles et ne seront pas révoquées par la Société Internet, ses successeurs ou ayants droit.

Ce document et les renseignements qu'il contient sont fournis "TELS QUELS" et l'INTERNET SOCIETY et l'INTERNET ENGINEERING TASK FORCE déclinent toute garantie, expresse ou implicite, y compris mais sans s'y limiter, toute garantie que l'utilisation de l'information ici présente n'enfreindra aucun droit ou aucune garantie implicite de commercialisation ou d'adaptation a un objet particulier.