Brevet FR2852760A1 — publié le 20040924

Transmission de paquets en fonction de leur temps total de traitement La présente invention est relative à la transmission de paquets au sein 5 d'un réseau de données, notamment de télécommunication. Elle s'applique particulièrement bien dans le cas o les paquets transmettent des flux de données nécessitant une certaine qualité de service (QoS, pour Quality of Service, en anglais). Il est connu d'affecter aux paquets transportant des flux associés à une qualité de service, une valeur d'identificateur, représentative de cette qualité de service. Ce mécanisme est par exemple celui décrit dans le RFC 2475 intitulé " An Architecture for Differentiated Services ", et est communément appelé " DiffServ ". Selon cette solution de l'état de l'art, les équipements de réseau traitent les paquets selon des priorités associées à chaque valeur d'identificateur (ou " couleur "). Il est ainsi possible d'affecter une priorité plus importante à des flux nécessitant une qualité de service élevée, et une priorité 20 moins importante aux flux nécessitant une qualité de service moindre. Cette solution de l'état de l'art souffre toutefois de plusieurs inconvénients. Elle est notamment insuffisante pour arbitrer les problèmes posés par des flux de données de priorité identique, c'est-à- dire transportant 25 des flux associés à une même classe de service. En effet, pour deux paquets ayant des priorités identiques, le délai de transmission peut différer de façon substantielle, en fonction du chemin suivi, c'est-à-dire de la longueur de ce chemin (en nombre d'équipements traversés) et de l'encombrement de ce chemin. Autrement dit, la qualité de service 10471 3/SYC/NVND F:\Saile\F 10471 3\PREMDEP\FIT\projetbr.doc réellement fournie peut varier fortement, entre deux flux de données ayant demandés la même qualité de service. La figure 1 illustre une telle situation. Un réseau N est composé de 5 équipements de réseau Ri, R2... R5. 5 Deux flux de données sont indiqués sur la figure: le premier entre par R1 et ressort par R4. Le second entre par R5 et ressort par R6. Ces deux flux de données ont des priorités identiques. Dans chaque équipement de réseau, les paquets subissent un traitement classique, consistant typiquement à lire et analyser une partie de ce 10 paquet (son entête), puis à l'insérer dans une file d'attente de sortie, avant de le transmettre vers l'équipement de réseau suivant. En fonction du nombre de paquets transitant par un équipement, la longueur de cette file d'attente peut être plus ou moins importante, et donc le temps passé par un paquet dans cette file peut aussi être plus long. Par la suite, pour la clarté de l'exposé, on supposera que la charge d'un équipement de réseau est directement fonction de la longueur de sa ou ses files d'attente. C'est-à-dire que l'on négligera l'impact des autres délais impliqués par le traitement dans cet équipement. Cet impact n'influera en effet nullement l'exposé des problèmes de l'état de la technique, ni la validité 20 de la solution de l'invention. Dans l'exemple de la figure 1, on suppose pour la clarté de l'exposé, que la charge des différents équipements de réseau est sensiblement identique. Auquel cas, on comprend aisément que les paquets suivant le chemin R1, R2, R3, R4 subissent un délai plus long que ceux suivant le chemin 25 R5, R4, puisqu'il traverse un plus grand nombre d'équipements. Comme ces deux flux de données ont des priorités identiques, l'équipement de réseau R4 les traitera indifféremment. Généralement, le choix entre la transmission en dehors du réseau N, d'un paquet venant de R5 ou de R. sera effectué de façon aléatoire. 1047 13/SYC/NVND F:\Salle\F 104713\PREMDEP\FIT\projetbr.doc Par conséquent, en sortie de l'équipement R5, les deux flux de données auront subit des délais de transmission très différents, et les flux transportés auront des qualités de service réelles, différentes. La demanderesse a remarqué qu'il était important de réaliser un arbitrage intelligent pour le choix des paquets ayant des priorités identiques. Plus précisément, l'invention consiste à faire dépendre ce choix, du retard déjà subit par les paquets, le long du chemin. Pour ce faire, l'invention a pour objet un procédé pour transmettre un 10 paquet au sein d'un réseau de télécommunication. Il se caractérise en ce qu'un temps total de traitement est associé au paquet et est modifié par au moins certains des équipements de réseau en fonction d'un temps particulier de traitement. Les équipements de réseau traitent le paquet, en fonction du temps total de traitement associé. Selon un mode de réalisation le temps total de traitement est contenu dans un champ du paquet. Selon un mode de réalisation, le temps particulier de traitement est déterminé, par l'équipement de réseau, comme une fonction de la taille de la 20 ou des files d'attente de l'équipement de réseau. Ce temps total de traitement est par exemple initialisé, préférentiellement par l'émetteur dudit paquet, à une durée maximale de transmission, et le temps particulier de traitement est retranché à ce temps total de traitement. L'invention a aussi pour objet un équipement d'un réseau de données, notamment de télécommunication, possédant des moyens pour recevoir des paquets entrants et des moyens pour transmettre des paquets sortants. Cet équipement, par exemple un routeur IP, est caractérise en ce 30 qu'il dispose de surcroît 10471 3/SYC/NVN D F:\Salle\Fl 0471 3\PREMDEP\FIT\projetbr.doc * d'un moyen d'évaluation du temps élémentaire de traitement des paquets entrants, * de moyens pour modifier une valeur représentative du temps total de traitement, contenue dans le paquet entrant, en fonction du temps élémentaire de traitement, et * des moyens pour choisir les paquets sortants selon une priorité dépendante du temps total de traitement. Selon un mode de réalisation, le temps total de traitement est contenu 10 dans un champ dudit paquet. Selon un mode de réalisation de l'invention, le temps particulier de traitement est déterminé, par l'équipement de réseau, comme une fonction de la taille de la ou des files d'attente de cet équipement de réseau. 15 Le temps total de traitement est par exemple initialisé, préférentiellement par l'émetteur du paquet, à une durée maximale de transmission, et le temps particulier de traitement est retranché à ce temps total de traitement. De cette façon, les paquets ayant déjà subit le plus de retard sont privilégiés par le ou les équipements suivants. Ainsi, le délai total de transmission des paquets tend à s'harmoniser, et les qualités de service réellement offertes par le réseau tendent à être sensiblement identiques, si les 25 qualités de service demandées sont elles-mêmes identiques. L'invention et ses avantages apparaîtront de façon plus claire dans la description de mises en oeuvre qui va suivre, en liaison avec les figures annexées. 10471 3/SYC/NVND F:\Solle\F1 04713\PREMDEP\FIT\projetbr.doc La figure 1, précédemment commentée, illustre un réseau de données et les problèmes de la solution de l'état de la technique. La figure 2 schématise le parcours d'un paquet le long d'un chemin composé de plusieurs équipements de réseau. La figure 3 illustre l'architecture fonctionnelle interne d'un équipement de réseau de type routeur. La figure 4 illustre un exemple d'utilisation de l'invention sur le réseau de la figure 1. Selon une mise en oeuvre de l'invention, les paquets contiennent un temps total de traitement. Ce temps total de traitement peut notamment être inséré dans un des champs de l'entête IP (Internet Protocol) des paquets. Selon un mode de réalisation préférentiel, la valeur du temps total de 15 traitement est initialisée à une durée maximale de transmission, par l'émetteur du paquet. Cet émetteur peut notamment être une entité de niveau application, qui connaissant le contenu sémantique des paquets, peut être à même de déterminer la durée maximale de transmission, c'est-àdire la durée maximale souhaitée pour la transmission du paquet de bout en bout (c'est-à20 dire depuis l'émetteur jusqu'au(x) destinataire(s).) Certains au moins des équipements de réseau traversés par le paquet déduisent de ce temps total de traitement, son temps particulier de traitement. Lorsque le temps total de traitement atteint un certain seuil, par exemple 0, une action peut être déclenchée par l'équipement de réseau. Notamment, le paquet peut être supprimé. En effet, par exemple si le paquet appartient à un flux vidéo pour un service de vidéo à la demande, le caractère "temps réel " est primordial afin d'obtenir un bon rendu sur le terminal destinataire. Aussi, un paquet trop retardé lors de sa transmission perd son caractère pertinent, et il peut être plus intéressant de perdre ce 10471 3/SYC/NVND F:\Solle\F1 0471 3\PREMDEP\FIT\projetbr.doc paquet (et donc potentiellement, un peu de qualité de l'image vidéo) que prendre en compte un paquet trop retardé. Alternativement, le paquet peut se voir " surclasser ", c'est-à-dire se voir affecter une priorité plus importante afin de " rattraper son retard ". Ce mécanisme de forcer la perte de paquet lorsque le temps total de traitement devient inférieur à un seuil est similaire à celui mis en oeuvre pour le champ TTL (Time To Live) spécifié par le protocole IP. Ce champ TTL est toutefois insuffisant à résoudre la problématique de l'invention puisqu'il ne 10 mesure qu'un nombre d'équipements traversés et ne tient pas compte du temps particulier de traitement dans chaque équipement. Or, en fonction de la charge de ces équipements, les temps particuliers de traitement peuvent être très différents. La figure 2 montre un chemin composé de 3 équipements de réseau, A, B et C. Un paquet P suit ce chemin. Il comporte un champ contenant le temps total de traitement associé à ce paquet. Lorsque l'équipement de réseau A reçoit le paquet P, il évalue son temps particulier de traitement, c'est-à-dire le temps que lui-même va mettre 20 pour traiter le paquet. Ce temps est fonction de sa charge, éventuellement de sa capacité de traitement (vitesse du microprocesseur, longueur des files d'attente...) etc. Il modifie le champ du paquet P contenant le temps total de traitement en fonction de l'évaluation de ce temps particulier de traitement. Le paquet modifié P(A) est ensuite transmis vers l'équipement de réseau B, qui de la même façon, modifie le paquet P(A) en un paquet P(B), en fonction de son propre temps particulier de traitement. Ce paquet P(B) est finalement transmis à l'équipement de réseau C qui à son tour le modifie en fonction de son temps particulier de traitement et le 30 transmet sous la forme d'un paquet une nouvelle fois modifié P(c) 1047 13/SYC/NVND F:\Sale\FI 0471 3\PREMDEP\FIT\projetbr.doc La figure 3 montre schématiquement l'architecture fonctionnelle interne d'un routeur IP, référencé R. Ce routeur est composé d'un processus de traitement T, d'un ensemble de files d'attente F1, F2... Fn (l'ensemble pouvant éventuellement être réduit à un singleton) et d'un ordonnanceur S. Les paquets entrants arrivent au processus de traitement T qui lit au moins une partie de leur contenu, typiquement l'entête IP, et en fonction de ce contenu, il choisit, entre autres choses, d'affecter le paquet entrant à une des 10 files d'attente F, F2... F,. Ce choix peut par exemple être effectué en fonction d'une indication de priorité ou d'une " couleur DiffServ ". Selon l'invention, le processus de traitement T est en outre chargé de déterminer le temps particulier de traitement et de modifier le temps total de traitement associé à ce paquet en fonction de ce temps particulier de 1 5 traitement. Selon un mode de réalisation de l'invention le temps particulier est contenu dans un des champs du paquet, notamment de l'entête IP. Il peut par exemple s'agit du champ " IP options ", dans le cas d'une mise en oeuvre sous I Pv4. Le processus de traitement T lit donc la valeur du temps total de traitement du paquet entrant. Il détermine, par ailleurs, le temps particulier de traitement, c'estàdire une estimation du temps qu'il sera nécessaire pour cet équipement de 25 réseau R pour traiter ce paquet. Ce temps particulier de traitement peut être fonction de la charge de l'équipement de réseau et notamment, selon une mise en oeuvre de l'invention, de la longueur de ces files d'attente. Plus précisément, le processus de traitement T peut déterminer la 30 longueur de la file d'attente Fi dans laquelle il va insérer le paquet entrant. En 1 0471 3/SYC/NVND F:\Sa lle\Fl 0471 3\PREMDEP\FIT\projetbr.doc fonction de la longueur et du temps moyen de traitement d'un paquet, il peut déterminer facilement le temps que le paquet va passer dans cette file d'attente. Compte tenu du fait que le temps de traitement par le processus de traitement T et par I'ordonnanceur S peut être considéré comme négligeable 5 par rapport à ce temps passé dans la file d'attente, il est pertinent de considérer que le temps particulier est uniquement fonction du temps passé dans les files d'attente. Selon cette mise en oeuvre, on peut donc écrire que le temps particulier de traitement t(R) de l'équipement de réseau R est donné 10 par l'équation t(R) = tR x LRi dans laquelle tR est le temps moyen de traitement d'un paquet par l'équipement de réseau R. et LR jest la longueur, en nombre de paquets, de la file d'attente numéro i de l'équipement de réseau R. 15 Le processus de traitement T peut alors modifier le temps total de traitement en fonction de ce temps particulier de traitement t(R). Comme il a décrit précédemment, plusieurs mises en oeuvre sont possibles pour cela. Le paquet ainsi modifié est alors effectivement inséré dans une des 20 files d'attente F1, F2- Fn. Selon un mode de réalisation de l'invention, l'insertion dans une des files d'attente peut être faite en fonction du temps total de traitement. Selon un premier exemple, les files d'attente sont associées à des intervalles de temps correspondants à des temps totaux de traitement. Ainsi, 25 par exemple, la file d'attente F1 correspond à temps total de traitement dans l'intervalle [0; 10 ms], la file d'attente F2 à un temps total de traitement dans l'intervalle [11 ms; 20 ms] et ainsi de suite. Selon un second exemple, les files d'attente sont associées, de façon classique en soit, à des priorités. Chaque paquet arrivant possède de même 30 une priorité. En fonction de la valeur du temps total de traitement du paquet 104 71 3/SYC/NVN D F:\Salle\F 104713\PREMDEP\FIT\projetbr.doc arrivant, celui-ci peut être classé dans une file d'attente différente de celle associée à sa priorité: ainsi, si un paquet possède une priorité 2 mais ayant un temps total de traitement trop important, il peut être rangé dans la file F1 associé à la priorité 1. L'ordonnanceur a pour rôle de choisir parmi les files d'attente, un paquet à transmettre sur le ou les ports de sortie. Ce choix peut être fait en fonction d'un ordre donné à cet ensemble de files d'attente. Par exemple, il peut choisir prioritairement les paquets de la file d'attente F, puis de la file 10 d'attente F2, puis de la file d'attente F3 et ainsi de suite. La figure 3 illustre la mise en oeuvre de l'invention sur le réseau de la figure 1. Comme dans l'exemple de la figure 1, on a représenté deux flux de données, l'un entrant dans le réseau par l'équipement de réseau R1, l'autre 15 par l'équipement de réseau R5, les deux sortants par l'équipement de réseau R4. Pour chacun de ces flux, on considère un paquet, respectivement P et Q. Le temps total de traitement de ces deux paquets est modifié le long de leur chemin respectif par les équipements de réseau traversé (toutefois, par soucis de lisibilité, on a conservé la même référence, P ou Q, tout le long du 20 chemin). Si l'on conserve la supposition qui avait été faite que chaque équipement de réseau possède une charge similaire, c'est-à-dire que les files d'attente des équipements de réseau sont à peu près uniformément remplies, le temps total de traitement devient fonction du nombre d'équipements 25 traversés. Par conséquent, l'équipement de réseau R5 peut déterminer facilement que le paquet P a subit un retard plus important que le paquet Q. Il peut donc choisir le paquet P en priorité, par rapport au paquet Q, et donc contribuer à réduire ce retard. 104 71 3/SYC/NVND F:\Salle\F104713\PREMDEP\FIT\projetbr.doc Lorsque ce même processus est répété sur un grand nombre d'équipement de réseau, on peut arriver à une optimisation des temps totaux de traitement. Dans le cas o une durée maximale de transmission a été fixée, cette optimisation se fait naturellement par rapport à celle-ci. Selon un mode de réalisation, la valeur du temps total de traitement est initialement fixée à 0, puis incrémentée, par les équipements de réseau traversé, de la valeur de leurs temps particuliers de traitement. La valeur du temps total de traitement va donc croissant. Les 10 équipements de réseau peuvent comparer cette valeur à un seuil et, en fonction du résultat de cette comparaison, déclencher des mécanismes similaires à ceux qui ont été décrit dans le cadre du mode de réalisation préférentiel. Préférentiellement, chaque équipement de réseau est apte à modifier le temps total de traitement, et à déclencher le ou les mécanismes adéquats. Toutefois, l'invention peut aussi fonctionner lorsque seulement une partie des équipements de réseau dispose des fonctionnalités décrites. L'invention fonctionnera alors en 10471 3/SYC/NVND F:\Salle\Fl 0471 3\PREMDEP\FIT\projetbr.doc REVENDICATIONS 1) Procédé pour transmettre un paquet au sein d'un réseau de télécommunication, caractérisé en ce qu'un temps total de traitement est 5 associé audit paquet et modifié par au moins certains des équipements de réseau en fonction d'un temps particulier de traitement, et en ce que lesdits équipements de réseau traitent ledit paquet, en fonction dudit temps total de traitement associé. 2) Procédé selon la revendication précédente, dans lequel ledit temps total de traitement est contenu dans un champ dudit paquet. 3) Procédé selon l'une des revendications 1 ou 2, dans lequel ledit temps particulier de traitement est déterminé, par ledit équipement de réseau, 15 comme une fonction de la taille de la ou des files d'attente dudit équipement de réseau. 4) Procédé selon l'une des revendications précédentes, dans lequel ledit temps total de traitement est initialisé, préférentiellement par l'émetteur 20 dudit paquet, à une durée maximale de transmission, et ledit temps particulier de traitement est retranché à ce temps total de traitement. 5) Équipement d'un réseau de données, notamment de télécommunication, possédant des moyens pour recevoir des paquets entrants 25 et des moyens pour transmettre des paquets sortants, caractérisé en ce qu'il dispose de surcroît d'un moyen d'évaluation du temps élémentaire de traitement des paquets entrants, de moyens pour modifier une valeur représentative du temps total de traitement, contenue dans ledit paquet entrant, en fonction dudit temps élémentaire de traitement, et des moyens 104 71 3/SYC/NVN D F:\Salie\Fl 0471 3\PREMDEP\FIT\projetbr.doc pour choisir les paquets sortants selon une priorité dépendante dudit temps total de traitement. 6) Équipement selon la revendication précédente, dans lequel ledit temps total de traitement est contenu dans un champ dudit paquet. 7) Équipement selon l'une des revendications 5 ou 6, dans lequel ledit temps particulier de traitement est déterminé, par ledit équipement de réseau, comme une fonction de la taille de la ou des files d'attente dudit 10 équipement de réseau. 8) Équipement selon l'une des revendications 5 à 7, dans lequel ledit temps total de traitement est initialisé, préférentiellement par l'émetteur dudit paquet, à une durée maximale de transmission, et ledit temps particulier de 15 traitement est retranché à ce temps total de traitement. 1047 13/SYC/NVND F:\Salle\Fl 0471 3\PREMDEP\FIT\projetbr.doc