Brevet FR2798798A1 — publié le 20010323

Routeur pour interconnexion de réseaux. Le domaine de l'invention est celui des réseaux de communication. Pour communiquer, des équipements terminaux de traitement de données ETTD (Data Terminal Equipement DTE en anglais) utilisent différents protocoles. On distingue habituellement plusieurs couches de communication, par exemple une couche application, une couche transport et une couche réseau. La couche application ne se préoccupe pas directement des localisations d'exécution de 1o fonctions. A titre d'exemple non limitatif, on peut citer différents protocoles utilisables dans une couche application tel que TELNET pour coupler un terminal local à une machine distante, FTP pour transférer des fichiers entre machines, HTTP pour accéder à des pages WEB. Généralement, une application client émet des requêtes vers une application serveur dont elle reçoit des réponses sans se préoccuper du fait que l'application serveur puisse s'exécuter dans un environnement physique et logiciel différent de celui de l'application client. La couche transport a pour fonction de faire communiquer deux applications en tenant compte de l'environnement physique et logiciel de chacune d'elle. Il existe des protocoles de la couche transport de type connecté tel que TCP et des protocoles de type non connectés tels que UDP. L'intérêt d'un protocole de transport de type connecté est qu'il assure la fiabilité des échanges alors qu'un protocole de type non connecté permet une plus grande rapidité. La couche réseau a pour fonction d'acheminer les messages entre deux ETTD en tenant compte des réseaux sur lesquels sont reliés les deux ETTD. Par exemple, des protocoles de réseau tels que IP ou CLNP rendent un service sans connexion de type datagramme. C'est à dire que pour un message constitué de datagrammes, le protocole de réseau retransmet chaque datagramme de machine en machine suivant la disponibilité des chemins offerts sans assurer que chaque datagramme émis arrive effectivement à destination, par exemple en cas de congestion d'un réseau ou d'une machine intermédiaire. Une telle machine intermédiaire, chargée de propager les datagrammes entre deux réseaux distincts, est généralement appelée routeur. Selon la recommandation 1.113 ITU-T "Vocabulary of Terms for Broadband Aspects of ISDN", Helsinki, mars 1993, un service sans connexion est défini comme un service permettant le transfert d'informations entre deux usagers du service sans le besoin de procédures d'établissement d'appel de bout en bout. 3s 2 2798798 Quand le nombre de datagrammes à propager entre deux réseaux dépasse la capacité d'émission du routeur, les datagrammes sont mis dans des files d'attente à l'intérieur du routeur pour traitement ultérieur. Quand le nombre de datagrammes en attente de traitement dans une file d'attente dépasse un seuil, le routeur jette les nouveaux datagrammes qui arrivent et qui auraient dû prendre place dans cette file d'attente car la capacité mémoire du routeur est limitée. Ces phénomènes de délai et de perte font qu'en cas de congestion, les couches transport des ETTD réémettent, multipliant le nombre de datagrammes à propager par io le routeur et aggravant ainsi la congestion. Des solutions connues existent au niveau des couches transport telles que par exemple le ralentissement pour éviter la congestion (Slow Start with Congestion Avoidance) du protocole TCP. La couche transport de l'ETTD émetteur détecte la congestion de réseau lorsqu'elle constate qu'elle doit retransmettre des données. Elle soulage les routeurs traversés par son trafic en réduisant temporairement et spontanément sa capacité d'émission pour une connexion concernée. Ceci est réalisé par exemple en augmentant l'intervalle de temps entre deux retransmissions éventuelles, en envoyant une quantité d'information plus faible que celle autorisée par I'ETTD récepteur. Un inconvénient de cette solution est que la congestion s'est déjà produite lorsqu'elle est mise en oeuvre, la retransmission est inévitable et la nécessité d'en augmenter le délai diminue considérablement les performances de communication. On peut encore citer l'étouffement de source (Source Quench) du protocole de contrôle ICMP. Quand le routeur constate que le nombre de messages dans une file d'attente atteint un seuil intermédiaire au moment de mettre un nouveau datagramme dans la file d'attente, il envoie un message particulier à î'ETTD qui a émis le datagramme pour lui indiquer que le risque de congestion augmente. L'ETTD Jo émetteur réduit alors sa capacité d'émission. Un inconvénient de cette solution est que I'ETTD émetteur est mal informé de la mesure dans laquelle il peut réaugmenter son débit. D'autre part, cette solution nécessite d'émettre des messages supplémentaires sur les réseaux. 3 2798798 Pour contrôler le débit de l'ETTD émetteur, de façon à le réduire avant qu'une congestion ne se produise, sans générer de trafic supplémentaire, I'invention utilise des datagrammes qui transitent à travers le routeur dans le sens ETTD récepteur vers ETTD émetteur et qui contiennent des informations de fenêtre. Ces informations de fenêtre sont celles générées au niveau du protocole de transport par l'ETTD récepteur pour indiquer à l'ETTD émetteur, la quantité d'information que ce dernier est autorisé à émettre sur une connexion avant réception d'un acquittement indiquant que les informations précédemment transmises ont été reçues correctement. L'invention a pour objet un procédé pour réduire la congestion dans une couche [o réseau d'une machine routeur lorsqu'elle accumule dans une file d'attente des datagrammes à émettre sur un réseau, caractérisé en ce qu'il comprend: - une première étape qui mesure un niveau de remplissage de ladite file d'attente pour élaborer un signal en fonction dudit niveau de remplissage; - une deuxième étape qui détecte tout datagramme reçu dudit réseau, dont un champ d'une couche transport contient une première valeur de fenêtre reçue; - une troisième étape qui élabore une deuxième valeur de fenêtre émise en fonction dudit signal pour traiter le datagramme détecté en y mettant ladite deuxième valeur dans ledit champ; - une quatrième étape qui route le datagramme traité sur un réseau à destination d'une couche transport limitant son débit d'émission en fonction de la valeur de fenêtre émise. Ainsi, dans un environnement avec un protocole de réseau rendant un service sans connexion de type datagramme et un protocole de transport rendant un service de connexion fiable utilisant un système de fenêtre pour le contrôle de flux de bout en bout, une machine intermédiaire qui voit passer tous les datagrammes que s'échangent deux équipements terminaux de traitement de données, peut contrôler le flux de datagrammes qui la traverse, en agissant depuis sa couche réseau sur la couche transport de l'équipement terminal de traitement de données émetteur. Ceci présente l'avantage de réduire la congestion dans la machine intermédiaire sans nécessiter de procédure particulière dans les équipements terminaux de traitement de données. Un exemple préféré de mise en oeuvre de l'invention est expliqué dans la description qui suit en référence aux figures o: 4 2798798 - la figure 1 présente un routeur de l'état de la technique; -la figure 2 présente un segment de couche transport; - la figure 3 présente un datagramme de couche réseau; -la figure 4 présente un routeur qui met l'invention en oeuvre; - la figure 5 présente un datagramme avec information de fenêtre; - la figure 6 présente des étapes de procédé conforme à l'invention. En référence à la figure 1, un ETTD (équipement terminal de traitement de donnée) émetteur 1 communique des messages à un ETTD récepteur 2 au moyen d'un protocole de transport 3. Pour ce faire, une couche transport 4 de l'ETTD 1 génère des segments 5 destinés à une couche transport 6 de l'ETTD 2. De façon plus générale, les segments sont des unités de données de protocole de transport TPDU, acronyme de Transport Protocol Data Unit en anglais. En référence à la figure 2, chaque segment 5 de la couche transport comprend au moins un champ 7 de transport. Lorsque le message concerne une application, la couche transport 4 reçoit d'une couche applicative non représentée de la machine 1, des informations au moyen d'une interface 8. La couche transport 4 incorpore alors ces informations dans un champ 9 du segment 5. En référence à la figure 1, la couche transport 4 transmet le segment 5 à une couche réseau 10 de î'ETTD 1 au moyen d'une interface 11. En référence à la figure 3, la couche réseau 10 juxtapose un champ 13 au segment 5 pour constituer un datagramme 12 destiné à une couche réseau 14 de l'ETTD récepteur 2. Le champ 13 contient des données pour mettre en ceuvre un protocole réseau entre les ETTD 1 et 2. Dans le cas o par exemple le réseau est de type IP, le champ 13 contient une adresse IP qui identifie l'ETTD récepteur 2 et une adresse IP qui identifie l'ETTD émetteur 1. En fonction de la configuration topologique de réseau, le datagramme 12 est acheminé directement de l'ETTD 1 à l'ETTD 2 ou indirectement à travers un ou plusieurs équipements routeurs 15. En référence à la figure 1, la couche réseau 10 achemine le datagramme 12 à une couche réseau 16 d'un équipement routeur 15, au moyen d'un réseau physique 17. La couche réseau 16 achemine ensuite le 2798798 datagramme 12 vers la couche 14 au moyen d'un réseau physique 18. Lorsque le réseau physique 18 n'est pas directement relié à l'ETTD 2, le datagramme 12 passe par autant d'équipements routeurs que nécessaire pour atteindre un réseau physique auquel est directement relié l'ETTD 2. Lorsque la couche réseau 16 de l'équipement routeur 15 reçoit un datagramme 19 qu'elle ne peut réémettre immédiatement sur le réseau physique 18 à cause d'encombrement, elle accumule le datagramme 19 dans une première file d'attente 20 qu'elle vide au fur et à mesure de la disponibilité du réseau physique 18. [u Lorsque la couche réseau 14 de l'ETTD 2 reçoit le datagramme 12, elle en retranche le champ 13 pour le transférer sous forme de segment 5 à la couche transport 6 au moyen d'une interface 21. Lorsque le segment 5 comprend un champ 9 destiné à une application, la couche transport 6 transfert le champ 9 à une couche applicative non représentée de l'ETTD 2 au moyen d'une interface 22. D'autre part, la couche transport 6 envoie à la couche transport 4, un segment d'acquittement pour lui signifier qu'elle a bien reçu le segment 5. Pour ce faire, la couche transport 6 transmet à la couche réseau 14, le segment d'acquittement qui comprend généralement uniquement le champ 7. La couche réseau 14 juxtapose ensuite un champ 13 au champ 7 de façon à obtenir un acheminer un datagramme d'acquittement qui est acheminé jusqu'à la couche réseau 10. La couche réseau 10 transmet ensuite le champ 7 du datagramme d'acquittement à la couche transport 4 au moyen de l'interface 11. En référence à la figure 1, la couche réseau 14 achemine les datagrammes sur le réseau physique 18 vers la couche réseau 16 de l'équipement routeur 15 qui les réachemine sur le réseau physique 17 jusqu'à la couche réseau 10. Lorsque la couche réseau 16 de l'équipement routeur 15 reçoit un datagramme 24 qu'elle ne peut réémettre immédiatement sur le réseau physique 17 à cause d'encombrement, ]0 elle accumule le datagramme 24 dans une deuxième file d'attente 25 qu'elle vide au fur et à mesure de la disponibilité du réseau physique 17. Un système de fenêtre du protocole de transport indique à la couche transport 4, la quantité d'information qu'elle peut émettre à destination de la couche transport 6 avant de recevoir le segment d'acquittement. Pour ce faire, la couche transport 6 6 2798798 envoie régulièrement des segments contenant un indicateur de la quantité d'information qu'elle peut traiter sans saturation. Une façon simple pour ce faire est de mettre par exemple cet indicateur dans le champ 7 des segments d'acquittement. Plusieurs raisons peuvent faire que la couche transport 4 ne reçoive pas d'acquittement a des segments générés à destination de la couche transport 6. Par exemple, les segments générés à destination de la couche transport ou les segments d'acquittement peuvent avoir été perdus dans les couches réseaux. La couche transport 4 peut alors réémettre des segments non acquittés jusqu'à en recevoir lo acquittement. En référence à la figure 4, la machine routeur 15 comprend un dispositif pour réduire la congestion dans sa couche réseau 16 lorsqu'elle accumule dans la file d'attente 20 des datagrammes 12 à émettre sur le réseau 18. Le dispositif comprend des moyens t5 33 pour détecter tout datagramme reçu du réseau 18, dont un champ 28 de la couche transport 6 contient une valeur de fenêtre reçue VFR et y mettre une valeur de fenêtre émise VFE, fonction d'un niveau 26 de remplissage de la file d'attente 20 avant de router le datagramme détecté sur le réseau 17 à destination de la couche transport 4. Lorsque le niveau de remplissage de la première file d'attente 20 dépasse un seuil 26 de prévention, la couche réseau 16 capte les datagrammes d'acquittement 27 en provenance du réseau 18 et effectue un traitement du contenu de leur champ 28 avant de les retransmettre sur le réseau 17. Le traitement du champ 28 est fait de façon à ce que la valeur de fenêtre ralentisse le débit de datagrammes entrant sur le routeur 15 à destination du réseau 18. La couche réseau 10 reçoit alors le datagramme 27 avec une valeur de fenêtre dans le champ 28 qui tient non seulement compte de la capacité de traitement de la couche transport 6 mais qui tient compte aussi de la capacité de traitement de la couche réseau 16. La couche réseau 10 retranche ou déplace le champ 13 du datagramme 27 pour obtenir un segment à transmettre à la couche transport 4. En respectant la valeur de fenêtre du champ 28, Mo la couche transport 4 génère alors un nombre de datagrammes à destination de la couche transport 6, inférieur ou égal au nombre de datagrammes admissibles par la couche transport 6 de I'ETTD 2. En référence à la figure 6, un procédé permettant de réduire la congestion dans une machine comprend quatre étapes. Une première étape 29 mesure le niveau de 7 2798798 remplissage de la première file d'attente 20 des datagrammes à émettre sur le réseau 18, pour élaborer un signal NIV. Une deuxième étape 30 détecte les datagrammes en provenance du réseau 18 contenant le champ 28 avec une valeur de fenêtre reçue VFR. Une troisième étape 31 traite la valeur VFR pour élaborer une valeur de fenêtre émise VFE et remplacer la valeur VFR par la valeur VFE dans le datagramme détecté, en fonction du signal NIV. Une quatrième étape 32 retransmet le datagramme détecté sur le réseau de destination 17. Le procédé, bien que mis en oeuvre au niveau de la couche réseau 16 de t l'équipement routeur 15, en remplaçant la valeur de fenêtre VFR par la valeur VFE, modifie un champ de la couche transport. Il faut tenir compte des contraintes liées au protocole de transport. L'étape 30 commence donc par identifier dans le champ 7 du datagramme reçu, le protocole de transport. I5 Par exemple, dans le cas du protocole de transport connu TCP, les segments sont transmis par séquences d'octets, numérotée chacune du premier au dernier octet de la séquence. A réception du dernier octet d'une séquence, la couche transport 6 de l'ETTD récepteur 2 émet un acquittement si c'est la première séquence ou s'il a déjà émis un acquittement pour la séquence immédiatement précédente. Cet acquittement indique généralement le numéro du premier octet de la séquence suivante en attente de réception. Dans le même segment que celui contenant l'acquittement, I'ETTD récepteur 2, émet une valeur de fenêtre VFR représentative du nombre d'octets que I'ETTD émetteur 1 peut émettre dans les séquences à venir. La valeur VFR tient compte d'une éventuelle valeur déjà transmise avec un acquittement précédent, du nombre d'octets déjà reçus et du nombre d'octets admissibles en réception. Pour chaque connexion établie entre les couches transports 4 et 6, dont les datagrammes des couches réseaux 10 et 14 passent par la couche réseau 16 de l'équipement routeur 15, I'équipement routeur 15 détecte le type de protocole de )O transport en amont. Dans le cas o le protocole de transport détecté est de type TCP, I'équipement routeur 15 calcule, en parallèle avec les étapes 29 à 32, une valeur de fenêtre restante VFER représentative du nombre d'octets que peut encore transmettre l'ETTD émetteur 1 au moment o celle-ci est calculée. De façon à ce que la valeur de fenêtre restante VFER soit représentative de la réalité, il convient de 8 2798798 forcer le passage de tous les datagrammes d'une même connexion par l'équipement routeur que constitue la machine 15. La valeur de fenêtre restante VFER est calculée de la façon suivante. A chaque fois que les moyens 33 reçoivent un datagramme contenant un acquittement, la valeur qu'il indique est mémorisée dans une variable nommée ACK. Une variable ACKp, initialisée à zéro, contient la valeur indiquée par l'acquittement précédent. Une valeur Diff est calculée par la formule: Diff = ACK - ACKp. l0 La valeur Diff représente alors un nombre d'octets émis à l'intérieur d'une fenêtre VFEp transmise précédemment à l'ETTD 1. La valeur VFER est alors donnée par la formule: VFER = VFEp - Diff. ts La valeur VFE obtenue dans l'étape 31 est alors égale à la plus grande de deux valeurs de fenêtre VFER et VFI o VFI est une valeur de fenêtre intermédiaire calculée suivant différentes réalisations possibles comme expliqué dans la suite de la description, laissées au choix d'un administrateur de réseau. VFE = max (VFER, VFI) Ceci permet d'assurer que la valeur VFE ne sera jamais inférieure à la valeur de fenêtre VFER pour laquelle l'ETTD I continue à transmettre des octets avant de recevoir la nouvelle valeur de fenêtre VFE. Selon une première réalisation possible, dans l'étape 29, le signal NIV est mis à un état binaire d'alarme lorsque le niveau de remplissage dépasse un premier seuil. Dans l'étape 31, lorsque le signal NIV est à un état initial, la valeur VFI est égale à la valeur VFR, c'est la couche transport 6 qui impose la valeur de fenêtre à la couche transport 4 pour en réguler l'émission de datagrammes. Les étapes 30 et 31 peuvent être court-circuitées, c'est à dire que les datagrammes à fenêtre peuvent être directement retransmis du réseau 18 au réseau 17. Lorsque le signal NIV est à l'état binaire d'alarme, la valeur VFI est obtenue en prenant la valeur la plus basse parmi la valeur VFR et une valeur talon VFT prédéterminée en fonction de la capacité du réseau 18 à vider la file d'attente 20. Ceci a pour effet de réduire momentanément les échanges sur des couches transport 4, 6 à gros débit de communication sans nécessairement les réduire sur des couches transport 4, 6 à plus faible débit dont les 9 2798798 valeurs de fenêtre sont déjà en dessous de la valeur talon VFT. Une variante consiste à obtenir la valeur VFI en multipliant la valeur VFR par un coefficient inférieur à un. Ceci a pour effet de réduire momentanément les échanges sur toutes les couches transport 4, 6 de manière proportionnellement identique, tant pour celles à faible débit que pour celles à fort débit de communication. Lorsque le signal NIV est remis à l'état initial, les datagrammes avec la valeur de fenêtre VFR sont retransmis à nouveau tel quel. Le signal NIV est remis à l'état initial dans l'étape 29 lorsque le niveau de remplissage redescend en dessous du premier seuil ou lorsque le niveau de remplissage redescend en dessous d'un deuxième seuil inférieur au premier seuil. L'hystérésis ainsi provoqué sur la limitation de la taille des fenêtres a pour effet d'éviter des instabilités. Le deuxième seuil peut être très bas, au point de correspondre à un état vide de la file d'attente 20. Selon une deuxième réalisation possible, dans l'étape 29, le signal NIV est le complément à un d'un nombre TAUX obtenu en divisant le niveau de remplissage mesuré par la capacité totale de la file d'attente 20. Ainsi, lorsque la file d'attente 20 est vide, le signal NIV est égal à un, lorsque la file d'attente 20 est pleine, le signal NIV est égal à zéro. Dans l'étape 31, la valeur VFI est obtenue en multipliant la valeur VFR par le signal NIV. Ainsi, lorsque la file d'attente 20 est vide, la valeur VFI est égale à la valeur VFR et les datagrammes restent inchangés. Lorsque la file d'attente est pleine, la valeur VFI est nulle, c'est à dire que la couche transport 4 ne peut transmettre un datagramme à la couche réseau 10 qu'après avoir reçu un acquittement pour un datagramme précédemment transmis. Entre ces deux extrêmes, la taille des fenêtres est progressivement diminuée avec une valeur VFI comprise entre VFR et zéro. En cas de surcharge momentanée du réseau 18, le niveau de remplissage de la file d'attente 20 a tendance à se stabiliser autour d'une valeur intermédiaire qui permet d'anticiper une diminution de charge ultérieure. Il est possible d'agir sur cette valeur intermédiaire en faisant intervenir le nombre TAUX sous forme polynomiale dans le calcul du signal NIV. 2798798 REVENDICATIONS: 1. Procédé pour réduire la congestion dans une couche réseau (16) d'une machine (15) lorsqu'elle accumule dans une file d'attente (20) des datagrammes (12) à émettre sur un réseau (18), caractérisé en ce qu'il comprend: - une première étape (295 qui mesure un niveau de remplissage de ladite file d'attente (20) pour élaborer un signal (NIV) en fonction dudit niveau de remplissage; - une deuxième étape (30) qui détecte tout datagramme reçu dudit réseau (18), dont un champ (28) d'une couche transport (6) contient une valeur de fenêtre reçue (VFR); - une troisième étape (31) qui élabore une valeur de fenêtre émise (VFE) en fonction dudit signal (NIV) pour traiter le datagramme détecté en y mettant ladite valeur (VFE) dans ledit champ (28); - une quatrième étape (32) qui route le datagramme traité sur un réseau (17) à destination d'une couche transport (4) limitant son débit d'émission en fonction de la !5 valeur de fenêtre émise (VFE). 2. Procédé selon la revendication 1, caractérisé en ce que le signal (NIV) est élaboré au moyen d'une fonction binaire qui donne un état d'alarme lorsque le niveau de remplissage de la file d'attente (20) dépasse un premier seuil. 3. Procédé selon la revendication 1, caractérisé en ce que le signal (NIV) est élaboré au moyen d'une fonction polynomiale proportionnelle au niveau de remplissage et inversement proportionnelle à la capacité de la file d'attente (20). 4. Procédé selon la revendication 2, caractérisé en ce que la valeur de fenêtre émise (VFE) est élaborée en limitant la valeur de fenêtre reçue (VFR) lorsque le signal (NIV) est à l'état d'alarme. 5. Dispositif pour réduire la congestion dans une couche réseau (16) d'une machine (15) lorsqu'elle accumule dans une file d'attente (20) dans une mémoire de ladite machine (15), des datagrammes (12) à émettre sur un réseau (18), caractérisé en ce qu'il comprend des moyens (33) dans ladite mémoire, pour détecter tout datagramme reçu dudit réseau (18), dont un champ (28) d'une couche transport (6) contient une valeur de fenêtre reçue (VFR) et y mettre une valeur de fenêtre émise (VFE) fonction 1h 1 2798798 d'un niveau (26) de remplissage de ladite file d'attente (20) avant de router le datagramme détecté sur un réseau (17) à destination d'une couche transport (4) limitant son débit d'émission en fonction de la valeur de fenêtre émise (VFE).