Brevet FR2779302A1 — publié le 19991203

CONTROLE DE CONGESTION DANS UN NOEUD ATM La présente invention a pour objet un procédé de contrôle de la congestion dans un noeud d'un système de transmission asynchrone. L'invention concerne les transmission en mode asynchrone, appelées dans la suite ATM, pour l'acronyme de l'anglais Asynchronous Transfer Mode. Dans un tel mode de transmission, des cellules de taille fixe sont transmises, dans un mode orienté connexion. L'établissement d'une connexion s'effectue par marquage d'un chemin, i.e. d'une chaîne d'identifiants. Localement, on o n'utilise dans un noeud ATM qu'un identifiant local d'un utilisateur appelé VPVC ou virtual path virtual channel; on procède dans chaque noeud à une translation locale des identifiants pour transmettre les paquets. Pour plus de détail sur la structure et le fonctionnement de l'ATM, on pourra se reporter aux travaux de l'ITU, de l'ATM Forum ou de l'ETSI. L'ATM est actuellement utilisé comme support de couche 2 dans le modèle ISO pour le protocole internet ou IP. A cette fin est prévue une couche d'adaptation IP-ATM, connue. sous l'acronyme AAL-5 (ATM Adapatation Layer). Sous AAL-5, le transport d'un paquet IP s'effectue en segmentant le paquet IP en cellules ATM; une recommandation ITU propose d'introduire dans l'en-tête des cellules ATM un bit représentatif de la fin du paquet IP, i. e. de la dernière cellule ATM d'un paquet IP. Ce bit noté bit AUU (ATM User to User indication) permet de repérer la fin d'un paquet IP; il permet aussi de repérer le début d'un paquet IP, dans la mesure o la cellule ATM suivant une cellule avec un bit AUU à 1 correspond au début d'un paquet IP. Ces fonctionnalités d'AAL-5 sont documentées dans ITU-T 1361, BiSDN ATM Layer Specification, Helsinki, Mars 1993. Un des problèmes rencontrés en ATM est le contrôle de congestion au niveau des noeuds. L'avantage d'un mode ATM est la flexibilité en débit, du fait du caractère asynchrone de la transmission; localement, dans un noeud présentant des ressources finies, cette flexibilité induit des problèmes de contrôle des congestions. Diverses solutions au problème du contrôle des congestions ont été proposées. La première solution consiste à ne pas contrôler la congestion dans les noeuds, i. e. de multiplexer à l'aveugle les cellules entrantes. Cette solution a un coût en ressources important pour assurer des performances. De nouveaux modèles de service tentent de fournir des solutions plus adaptées, notamment des solutions dites de "best efforts", qui prennent en compte que tous les types d'application n'ont pas nécessairement besoin de la même qualité de service. Ont été suggérées, notamment sous l'impulsion de 'ATM Forum des solutions de "packet discard" (destruction de paquet) ou de "frame discard" (destruction de trame). Une solution proposée dans le document ATM Forum Traffic Management Specification 4.0 est appelée Tail Packet Discard ou TPD. Cette solution consiste, lorsqu'une cellule est rejetée ou détruite du fait d'un débordement d'un tampon, à rejeter ou détruire toutes les cellules suivantes jusqu'à la fin du paquet. Cette solution est mise en oeuvre en utilisant le bit AUU pour repérer la fin d'un paquet: après la destruction d'une cellule, on o détruit toutes les cellules suivantes présentant le même VPVC, jusqu'à ce que l'on détruise une cellule dont le bit AUU est validé, qui est la fin d'un paquet. Cette solution permet de récupérer de la place dans le tampon, étant entendu qu'un paquet dont une cellule a été supprimée est inutilisable pour l'application. Une autre solution proposée dans le document ATM Forum Trafic Management Group Living List, December 1997, pages 18-20 est appelée Early Packet Discard ou EPD. L'idée de cette solution est de décider dès le début de la réception d'un paquet si les cellules qui composent le paquet doivent être acceptées ou non, en fonction de la place disponible dans le tampon lors de la réception de la première cellule. A cet effet, on définit dans le tampon un seuil d'EPD. Lorsque la première cellule d'un paquet arrive dans le tampon, elle est rejetée, avec toutes les cellules suivantes du paquet, si le tampon est déjà empli au delà du seuil d'EPD. Inversement, si lors de l'arrivée de la première cellule le seuil d'EPD dans le tampon n'est pas atteint, la cellule est acceptée - ce qui ne préjuge pas de l'acceptation des cellules suivantes du paquet. Ces solutions ne sont pas pleinement satisfaisantes. Le TPD n'est pas optimal, dans la mesure o il est possible d'accepter la plupart des cellules d'un paquet, et de devoir néanmoins retransmettre l'ensemble du paquet si les dernières cellules sont rejetées; I'EPD est peu efficace dans une file d'attente de petite taille, ou en cas de charge importante du noeud de transmission. En outre, la fixation du seuil d'EPD est difficile, car ce seuil est sensible à la taille des paquets, et à leur processus d'arrivée. On utilise généralement pour fixer le seuil d'EPD des informations statistiques sur les tailles et les arrivées des cellules. Il a aussi été proposé un modèle de service de la couche ATM, appelé ABT/IT (ATM Block Transfer with Immediate Transmission), qui prévoit la possibilité de marquer des blocs dans la couche ATM. Ces blocs ne sont pas forcément liés à un PDU (protocol data unit ou unité de données du protocole) du niveau supérieur - un paquet dans le cas de l'IP. Ce marquage s'effectue par insertion de cellules RM (Resource Management ou gestion de ressources) qui définissent les extrémités de blocs, et qui portent des informations de débit du bloc transmis entre deux cellules RM successives, et optionnellement des informations de taille du bloc. Ce modèle de service est par exemple décrit dans le document ITU-T Recommandation 1.371, Toronto, septembre 1997, page 19. Il n'est pas mis en oeuvre dans les systèmes actuels, du fait de la complexité nécessaire pour la mise en oeuvre de cette solution en réseau. En outre, I'insertion de cellules RM induit une augmentation du trafic (overhead). L'invention propose une solution de contrôle de congestion pour un noeud ATM, qui permette un contrôle plus efficace que les solutions d'EPD et de TPD connues, et qui soit d'une mise en oeuvre plus simple que les solutions de ABT/IT. Plus précisément, I'invention propose un procédé de contrôle de congestion dans un noeud d'un système de transmission asynchrone, dans lequel sont transmis des cellules, caractérisé par l'acceptation ou le rejet des cellules en fonction du débit (PCR) de la connexion sur laquelle sont transmises les cellules, le débit étant évalué à partir des informations de débit crête négociées avec le système pour la connexion. Dans un mode de réalisation, les cellules forment des paquets, et le procédé comprend, à l'arrivée d'une première cellule d'un paquet, une étape de comparaison du débit évalué des cellules du paquet et du débit disponible (RTC) sur le noeud. De préférence, le débit disponible sur le noeud est égal à la différence entre le débit possible du noeud et la somme des débits des connexions des paquets en cours de transmission par le noeud. Avantageusement, les paquets en cours de transmission par le noeud sont les paquets dont la dernière cellule n'a pas été transmise. Dans un autre mode de réalisation, les paquets en cours de transmission par le noeud comprennent les paquets dont la dernière cellule n'a pas été transmise et les paquets dont la dernière cellule-a été transmise depuis une durée inférieure à la durée moyenne (1/PCR) entre cellules du paquet. De préférence, le procédé comprend l'introduction d'espaceurs sur au moins une connexion, et le débit négocié de la dite connexion est corrigé en fonction de l'introduction des dits espaceurs. On peut aussi prévoir le rejet de toutes les cellules d'un paquet dont la première cellule a été rejetée. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description qui suit de modes de réalisation de l'invention, donnée à titre d'exemple et en référence aux dessins annexés qui montrent: - figure 1, un schéma d'une mémoire tampon située dans un noeud d'un réseau ATM, dans laquelle l'invention peut être mise en oeuvre; - figure 2, une représentation un ordinogramme du procédé mis en oeuvre à la réception d'une cellule; - figure 3 à 8, des résultats de simulation de l'invention. L'invention propose d'utiliser, pour le contrôle de la congestion, des o informations de débit implicites, qui ne sont pas véhiculées par les cellules ATM, mais qui sont déduites des informations de débit négociées lors de l'établissement des connexions. En effet, lors de l'établissement d'une connexion dans un système ATM, est négocié pour la connexion un débit crête ou PCR (Peak Cell Rate), qui correspond au débit maximal autorisé pour la connexion en cause. Il s'avère expérimentalement que les cellules dans un paquet sont généralement émises au débit offert à un terminal, i. e. sensiblement au débit crête négocié pour la connexion. Alternativement, il est possible, sur une connexion donnée, de réduire le débit des cellules pour mieux exploiter les capacités d'une ligne de transmission, en introduisant des espaceurs de cellules, en entrée du réseau; cette solution est décrite dans la demande de brevet français FR-A-2 653 285 ayant pour titre "Dispositif d'évaluation du débit de circuits virtuels empruntant une voie de transmission à multiplexage temporel axynchrone"; on pourra se reporter à cette demande pour plus de précisions quant à la nature de la transformation prévue. Dans un tel cas, I'invention propose de considérer non pas le débit négocié correspondant au PCR, mais le débit réduit noté dans la suite PCR'. L'un comme l'autre sont des paramètres du système connus localement pour les différentes connexions. La figure 1 montre un schéma d'une mémoire tampon d'un noeud d'un réseau ATM, dans laquelle l'invention peut être mise en oeuvre; la figure 1 montre un ensemble de connexions entrantes 21 à 2n, un tampon 3, et un serveur 4 qui transmet les cellules contenues dans le tampon sur une ligne 6 de débit de ligne connu. Lors de l'arrivée d'une nouvelle cellule d'un nouveau paquet sur une connexion donnée, I'invention propose de considérer le débit requis pour la connexion sur laquelle arrive cette cellule, et de comparer ce débit au débit restant du serveur ou RTC (acronyme de l'anglais Remaining Transmission Capacity, ou capacité de transmission restante) du serveur. Le RTC est calculé à partir du débit du serveur, localement connu, et de la somme des débits des connexions actives, i. e. de la somme des débits négociés PCR ou PCR' de chacune des connexions pour lesquels des paquets sont en cours de transmission. Il convient de noter que si un paquet précédemment reçu a été rejeté, I'information de débit correspondante n'est pas prise en compte pour le calcul du RTC. Le RTC ainsi calculé est comparé au débit requis pour la connexion nouvelle; s'il s'avère que le serveur dispose encore d'une capacité supérieure au débit requis, la cellule est acceptée, et le RTC est diminué d'autant. Sinon, la cellule est rejetée, et toutes les cellules suivantes du paquet le sont aussi. La figure 2 montre en détail un ordinogramme du procédé mis en oeuvre à la réception d'une cellule. A l'étape 10, on reçoit une cellule; on passe à l'étape 1 1 après la réception d'une cellule. A l'étape 1 1, on détermine si la cellule entrante est la première cellule d'un nouveau paquet; une nouvelle cellule d'un nouveau paquet qui arrive en entrée sur le noeud est identifiée comme nouvelle cellule, par exemple grâce au bit AUU de la cellule précédente. Si tel est le cas, on passe à l'étape 1 2, et sinon, on passe à l'étape 13. A l'étape 13, on est en présence d'une cellule d'un paquet dont la première cellule est déjà arrivée; on détermine si la première cellule a été rejetée, par consultation du bit d'activation; si tel est le cas, on passe à l'étape 14, o la cellule est aussi rejetée; en effet, comme dans le TPD, il n'est pas utile de continuer à transmettre des cellules d'un paquet qui arrivera en tout état de cause incomplet. Après l'étape 14, on revient à l'étape 10 pour la cellule suivante. Sinon, on passe à l'étape 15, o la cellule est acceptée, sauf débordement du tampon. A l'étape 12, on est en présence d'une première cellule de paquet. On détermine alors le débit implicite, PCR, par consultation des tables système, à partir du VPVC de la cellule, et on passe à l'étape 16. Le cas échéant, ce PCR est corrigé, comme expliqué plus haut. A l'étape 16, on compare le PCR déterminé à l'étape 12 au RTC. Si le PCR est inférieur ou égal au RTC, on passe à l'étape 17. Sinon, on passe à l'étape 19. A l'étape 17, on suppose que le paquet est accepté, et on met à jour le bit d'activation correspondant, à une première valeur logique, de telle sorte que les cellules suivantes soient aussi acceptées. On passe ensuite à l'étape 18. A l'étape 18, on met à jour le RTC, pour prendre en compte l'acceptation de la cellule, et donc l'utilisation de capacités correspondant au débit PCR. On calcule un nouveau RTC par la formule: RTC = RTC - PCR On passe ensuite à l'étape 15 o la cellule est acceptée, sauf débordement du tampon; on repasse ensuite à l'étape 10, pour attendre la cellule suivante. A l'étape 1 9, on se trouve en présence d'une première cellule de paquet, qui est destinée à être rejetée dans la mesure o les capacités du noeud ne permettent pas de garantir son acheminement. On met à jour le bit d'activation, à une deuxième valeur logique, de sorte que les cellules suivantes soient rejetées à l'étape 13. On passe ensuite à l'étape 14. La mise à jour du bit d'activation permet de rejeter les cellules suivantes du paquet. L'invention permet ainsi à tout instant de prévoir l'utilisation des ressources du noeud de transmission. Elle fournit une solution indépendante de la taille des paquets. Elle ne préjuge pas du débordement du tampon; toutefois, un débordement du tampon est improbable. On décrit maintenant la mise à jour du RTC lorsque l'on reçoit la dernière cellule d'un paquet, identifiée par un bit AUU. Lors de la réception d'une telle cellule, si le paquet correspondant a été rejeté, il convient simplement de mettre à une valeur logique donnée un bit permettant de repérer que la cellule suivante est une première cellule de paquet. Ceci assure que le paquet suivant pourra être traité et acheminé, si les ressources sont de nouveau disponibles. Au contraire, si le paquet correspondant à la dernière cellule a été accepté, il convient de mettre à une valeur logique donnée un bit permettant de repérer que la cellule suivante est une première cellule de paquet, et en outre de mettre à jour le RTC, pour indiquer que l'ensemble du paquet a été acheminé, et que la ressource correspondante peut être utilisée pour un autre paquet. Deux modes de réalisation sont possibles. Dans un premier mode de réalisation, on calcule un nouveau RTC, par la formule suivante, dès la réception de la cellule de fin de paquet: RTC = RTC + PCR, o PCR est le débit pour la connexion portant la cellule. Ce mode de réalisation, appelé relâchement immédiat, présente l'avantage de la simplicité. Dans un autre mode de réalisation, on calcule un nouveau RTC, par la même formule, mais après avoir attendu un temps correspondant à l'intervalle entre les arrivées des cellules du paquet, i. e. après un temps 1/PCR. Cette solution présente une meilleure sécurité, notamment en cas de paquets de petite taille, et évite tout remplissage intempestif du tampon. De fait, le relâchement différé selon ce mode de réalisation permet d'éviter tout relâchement avant la transmission effective de la cellule. Le mode de réalisation à relâchement immédiat reste acceptable pour des tailles de paquets correspondant aux tailles de paquet de l'IP, à savoir de à 200 cellules. Le fait de ne pas allouer de ressources sur la dernière cellule est acceptable au vu de la capacité de charge du serveur, qui est toujours différente de 100%. Dans un cas comme dans l'autre, on comprend comment le RTC est mis à jour, après le passage d'un paquet, et comment le paquet suivant peut être acheminé. Il convient encore de noter que le RTC, au départ, est initialisé à la capacité du serveur. Il est mis à jour en permanence, en fonction de l'activité du serveur. La solution de l'invention est plus simple à mettre en oeuvre que l'ABT/IT, dans la mesure o elle utilise des informations déjà présentes, et que les terminaux peuvent exploiter. En outre, I'utilisation d'informations de débit implicites n'induit pas d'augmentation du trafic (overhead). La solution est plus performante que l'EPD, et notamment est plus robuste par rapport à la taille des cellules, et susceptible d'être mise en oeuvre pour des tampons de petite taille. Elle présente un avantage particulier pour les systèmes temps réel, qui travaillent sur des tampons de petite taille. Avantageusement, le procédé de la figure 2 comme le procédé de relâchement s'effectue au maximum en un temps cellule. On prévoit aussi, si nécessaire, une procédure de réinitialisation périodique, qui permet de survivre à des circonstances du genre: paquet de longueur infini, erreur de calcul du RTC ou autre. L'invention, grâce à l'utilisation d'informations de débit implicites, permet ainsi de gérer les congestions. Dans la mesure o elle travaille sur les débits, elle est fiable et limite le risque de débordement du tampon. Les figures 3 à 8 montrent des résultats de simulation de l'invention, par comparaison à des mécanismes d'EPD et de TPD. On a utilisé pour les simulation, les hypothèses suivantes: 1000 connexions; longueur des paquets: 50 cellules ou 1000 cellules; PCR des connexions: débit de ligne/1 00 ou débit de ligne/5; taille du tampon: 64 cellules; seuil de TPD: 64 cellules; seuil d'EPD: 5 ou 50 cellules. Les résultats sont fournis sous forme d'une part du PER ou taux d'erreur sur les paquets (acronyme de l'anglais Packet Error Ratio), qui est égal au rapport: (nombre de paquets entranis - nombre de paquets transmis) / nombre de paquets entrants. Le PER est représentatif de l'efficacité du système ATM, de bout en bout. On utilise d'autre part le critère de charge en sortie du système, ou "goodput", défini comme le rapport: 0 (nombre de paquets intègres en sortie x taille des paquets) /débit de ligne. Cette charge en sortie est représentative de l'utilisation du système, et du filtrage qu'effectue le mécanisme de contrôle de congestion. Dans la mesure o un système de transmission ATM est constitué d'un grand nombre de noeuds, ce paramètre est important; en effet, il évite que des paquets partiels ne soient acheminés, ce qui ne sert à rien puisqu'un paquet incomplet est retransmis. Sur chacune des figures, on a représenté, en trait plein, un multiplexage direct, en traits pointillés longs un TPD, en traits pointillés moyens un EPD avec un seuil faible à 5 cellules, en traits pointillés courts un EPD avec un seuil élevé à 50 cellules, et en traits interrompus le procédé de l'invention. Les figures 3 et 4 donnent le cas d'un PCR faible (débit de ligne/1 00) et de paquets de petite taille (50 cellules). La figure 3 montre en abscisse la charge en entrée, normalisé par rapport au débit de ligne en sortie; en ordonnées est portée le PER. La figure 4 montre en abscisse la charge en entrée, normalisé par rapport au débit de ligne en sortie; en ordonnées est porté le "goodput". Les figures 5 et 6 sont analogues aux figures 3 et 4, mais pour un PCR élevé (débit de ligne/5), et des paquets de grande taille (1000 cellules). Les figures 7 et 8 sont analogues aux figures 3 et 4, mais pour un PCR élevé (débit de ligne/100), toujours pour des paquets de petite taille (50 cellules). Les figures 3 à 8 montrent que les mécanismes de TPD ou d'EPD à seuil élevé fonctionnent de manière satisfaisante dans des conditions de charge faible. Toutefois, le procédé de l'invention et dans une moindre mesure l'EPD à seuil faible assurent de meilleurs résultats en forte charge. Le procédé de l'invention assure les meilleurs résultats dans une large plage de conditions de fonctionnement. Il assure aussi les meilleures performances en termes de "goodput". Bien entendu, la présente invention n'est pas limitée aux exemples et modes de réalisation décrits et représentés, mais elle est susceptible de nombreuses variantes accessibles à l'homme de l'art. Ainsi, elle peut être mise en oeuvre pour des cellules qui ne forment pas des paquets, en mettant en oeuvre à chaque cellule le procédé de l'invention. On peut aussi choisir de ne pas systématiquement rejeter les cellules suivantes d'un paquet, si cela présente une utilité pour une transmission donnée. L'invention peut être combinée avec des mécanismes de gestion de priorité, par exemple en fonction du RTC, en conditionnant l'acceptation d'un paquet à une nature de connexion au dessous d'un certain RTC. REVENDICATIONS 1.- Procédé de contrôle de congestion dans un noeud d'un système de transmission asynchrone, dans lequel sont transmis des cellules, caractérisé par l'acceptation ou le rejet (16) des cellules en fonction du débit (PCR) de la connexion sur laquelle sont transmises les cellules, le débit étant évalué à partir des informations de débit crête négociées avec le système pour la, connexion. 2.- Procédé selon la revendication 1, caractérisé en ce que les cellules forment des paquets, et en ce qu'il comprend, à l'arrivée d'une première cellule d'un paquet, une étape de comparaison du débit évalué des cellules du paquet et du débit disponible (RTC) sur le noeud. 3.- Procédé selon la revendication 2, caractérisé en ce que le débit disponible sur le noeud est égal à la différence entre le débit possible du noeud et la somme des débits des connexions des paquets en cours de transmission par le noeud. 4.- Procédé selon la revendication 3, caractérisé en ce que les paquets en cours de transmission par le noeud sont les paquets dont la dernière cellule n'a pas été transmise. 5.- Procédé selon la revendication 3, caractérisé en ce que les paquets en cours de transmission par le noeud comprennent les paquets dont la dernière cellule n'a pas été transmise et les paquets dont la dernière cellule a été transmise depuis une durée inférieure à la durée moyenne (1/PCR) entre cellules du paquet. 6.- Procédé selon l'une des revendications 1 à 5, caractérisé en ce qu'il comprend l'introduction d'espaceurs sur au moins une connexion, et en ce que le débit négocié de la dite connexion est corrigé-en fonction de l'introduction des dits espaceurs. 7.- Procédé selon l'une des revendications 2 à 6, caractérisé en ce qu'il comprend le rejet de toutes les cellules d'un paquet dont la première cellule a été rejetée.