Brevet FR2878106A1 — publié le 20060519

Arrière-plan de l'invention L'invention concerne le domaine de l'architecture de réseaux de télécommunications. Elle vise plus particulièrement, un procédé, un dispositif d'ordonnancement, et un routeur de paquets de données multiservices visant à améliorer la qualité du service d'acheminement de paquets de données io multiservices compris dans différents flots de ce réseau, de faible complexité. Elle s'applique en particulier au réseau Internet. La notion de flot utilisée dans ce document est par exemple celle de l'architecture flow-aware exposée dans l'article de Bonald et al. IP traffic and QoS control: the need for a flow-aware architecture , World Telecom 15 Conference, Paris, 2002. L'internet est à vocation multiservices et appelé à fournir le support pour une large gamme de services et d'applications. On distingue deux grandes classes de trafic dans ce réseau le trafic temps réel (ou trafic streaming ) produit en général par les applications audio ou vidéo, et le trafic de données (ou trafic élastique) correspondant au transfert de documents numériques. Le trafic temps réel a des exigences de qualité de service correspondant au besoin de conservation du signal les variations de débit qui caractérisent le signal produit par la source doivent être préservées lorsque le signal traverse le réseau. La qualité de service du trafic de données se mesure par le temps de transfert des documents. Ce temps, ou de manière équivalente le débit moyen réalisé lors du transfert, dépend de toute la chaîne de communication de la source à la destination. Un objectif de qualité de service pour un réseau internet pourrait être de paraître transparent au trafic cle données en n'introduisant pas de réduction de débit supplémentaire par rapport aux limitations introduites ailleurs (serveur, réseaux d'accès, équipement de l'utilisateur); dans ce sens le réseau assure la conservation du débit des flots de données. Le réseau Internet public offre un service de transport à des clients utilisateurs dans un contexte commercial. La question de la tarification est donc importante. L'architecture de réseau doit permettre un retour sur investissement pour l'opérateur avec des prix compétitifs pour les services de qualité demandés par les utilisateurs. On connaît une méthode d'ordonnancement de faible complexité (de l'ordre 0(1), c'est-à-dire indépendante du nombre de flots) baptisée DRR (pour io Deficit Round Robin ), et décrite par M. SHREEDHAR et G. VARGHESE: Efficient fair queuing using Deficit round robin , IEEE/ACM Transactions on Networking, Volume: 4, Issue: 3, June 1996, pages 375-385. La méthode DRR est une méthode d'ordonnancement basée sur le traitement des flots de manière cyclique, selon le principe round robin . Cette is méthode associe une file d'attente à chaque flot, chacune de ces files d'attente, traitées cycliquement, étant autorisée à émettre, par cycle, des paquets jusqu'à hauteur d'un quota (quantité de données, par exemple mesurée en octets). Cette méthode DRR permet d'avoir un degré d'équité raisonnable grâce au maintien d'un compteur de déficit qui permet de compenser la différence éventuelle de taille des paquets des différents flots. Des variantes de la méthode DRR ont permis d'associer un traitement prioritaire aux paquets de certains flots. En particulier, la méthode DRR+, décrite dans l'article précité, permet de traiter en priorité les flots sensibles au délai, au détriment des flots best effort . Dans cette méthode, les flots prioritaires doivent respecter un contrat, à savoir ne pas émettre plus d'un certain volume de données pendant une période de temps prédéterminée. Le document FR2854296 de la demanderesse propose une méthode d'ordonnancement avec différenciation implicite des paquets à traiter en priorité, et permettant en conséquence de s'affranchir avantageusement de ce type de contrat. Mais la méthode d'ordonnancement décrite dans ce document, de type self-clock fair queuing est en ordre O(log n), n étant le nombre de flots à prendre en compte, ce qui peut apparaître comme une limitation pour son implémentation dans certains types de routeurs. L'invention vise à résoudre les inconvénients précédents. Objet et résumé de l'invention A cet effet, et selon un premier aspect, elle concerne un procédé d'ordonnancement de paquets appartenant à différents flots, ce procédé comportant: une étape de mise en file de chaque paquet dans une file d'attente associée au flot de ce paquet; ro pour chacune des files d'attente traitées cycliquement, une étape d'émission des paquets contenus dans cette file d'attente jusqu'à hauteur d'un quota pour ce cycle; - une étape de détermination de la priorité du paquet, préliminaire à l'étape précitée de mise en file, les paquets prioritaires étant d'une part s - les premiers paquets des flots non actifs, à savoir les flots dont aucun paquet n'a été reçu dans le cycle; et d'autre part: - les paquets des flots actifs et dont le volume de paquets reçus dans le cycle est inférieur à ce quota; et une étape d'émission, en priorité dans le cycle, des paquets déterminés 20 prioritaires au cours de cette étape de détermination. Corrélativement, l'invention concerne aussi un dispositif d'ordonnancement de paquets appartenant à différents flots, ce dispositif comportant: des moyens de mise en file de chaque paquet dans une file d'attente 25 associée au flot de ce paquet; et des moyens pour traiter cycliquement chacune des files d'attente, ces moyens de traitement comportant des moyens d'émission des paquets contenus dans une file d'attente jusqu'à hauteur d'un quota pour ce cycle; des moyens de détermination de la priorité d'un paquet, préalablement à la mise en file précitée de ce paquet, les paquets prioritaires étant d'une part: - les premiers paquets des flots non actifs, à savoir les flots dont aucun paquet n'a été reçu dans le cycle; et d'autre part: - les paquets des flots actifs et dont le volume de paquets reçus dans le cycle est inférieur à ce quota; et des moyens d'émission, en priorité dans le cycle, des paquets déterminés prioritaires par ces moyens de détermination. Ainsi, l'ordonnancement selon l'invention se distingue de ceux de l'état de la technique connue à ce jour, en ce qu'il réalise une distinction de la priorité des flots en fonction de leurs caractéristiques intrinsèques de débit, et non en ro fonction d'un contrat ou d'une attribution externe d'un niveau de priorité associée aux paquets ou aux flots, tout en gardant une complexité indépendante du nombre de flots. Le dispositif et le procédé d'ordonnancement ordonnent les paquets dans une file d'attente, selon un algorithme de partage équitable avec priorité. Un ordonnancement de type partage équitable avec priorité permet de donner priorité aux paquets des flots dont le débit est inférieur à un seuil dynamique. Ce seuil correspond au débit que réaliserait un flot qui aurait toujours des paquets à émettre. Avantageusement, ce procédé et ce dispositif d'ordonnancement 20 s'appuient sur la méthode d'ordonnancement DRR susmentionnée. Préférentiellement, le procédé d'ordonnancement selon l'invention comporte en outre une étape de mesure de paramètres de congestion. Ces paramètres de congestion peuvent notamment servir pour un contrôle d'admission en coeur de réseau. Préférentiellement, ces paramètres de congestion sont constitués par: une valeur de débit équitable, qui est une mesure de débit que réaliserait un flot de données qui aurait toujours des paquets à émettre; et une valeur de charge prioritaire, correspondant au volume desdits paquets prioritaires, transmis pendant un intervalle de temps, divisé par la durée de 30 cet intervalle. Dans un mode préféré de réalisation, l'ordonnancement selon l'invention est associé à un contrôle d'admission par flot de type fair queueing . Ainsi, et selon un deuxième aspect, l'invention vise aussi un routeur de paquets comportant un dispositif d'ordonnancement tel que mentionné cidessus, et un module de contrôle d'admission des paquets en fonction des paramètres de congestion mesurés par le dispositif d'ordonnancement. Préférentiellement, le module d'admission est en outre adapté à acheminer directement les paquets appartenant à des flots dits protégés, à savoir les flots pour lesquels au moins un paquet a été reçu par ledit module d'admission depuis un intervalle de temps prédéterminé. Un tel dispositif ou procédé peut fonctionner, sans moyens de contrôle o d'admission, notamment dans le cadre d'un réseau d'accès où le risque de congestion est davantage maîtrisable qu'en coeur de réseau. Dans un mode de réalisation préféré, les étapes du procédé d'ordonnancement sont exécutées par un ordinateur sous la commande d'instructions d'un programme informatique. Par conséquent, l'invention concerne également un programme d'ordinateur stocké sur un support d'informations, ce programme comportant des instructions permettant la mise en oeuvre d'un procédé d'ordonnancement tel que mentionné ci-dessus, lorsque ce programme est chargé et exécuté par un système informatique. L'invention vise aussi un support d'informations lisible par un système 2.0 informatique, éventuellement totalement ou partiellement amovible, notamment CD-ROM ou support magnétique, tel un disque dur ou une disquette, ou support transmissible, tel un signal électrique ou optique, caractérisé en ce qu'il comporte des instructions d'un programme d'ordinateur permettant la mise en oeuvre d'un procédé d'ordonnancement tel que mentionné ci-dessus, lorsque ce programme est chargé et exécuté par un système informatique. Les avantages particuliers du dispositif d'ordonnancement, du routeur, du support d'informations, et du programme d'ordinateur étant identiques à ceux du procédé d'ordonnancement mentionné précédemment, ils ne seront pas rappelés ici. 2878106 6 Brève description des dessins D'autres aspects et avantages de la présente invention apparaîtront plus clairement à la lecture de la description des modes particuliers de réalisation qui vont suivre, cette description étant donnée uniquement à titre d'exemple non limitatif et faite en référence aux dessins annexés sur lesquels: - la figure 1 représente, sous forme d'organigramme, les principales étapes d'un opérateur de mise en file dans un procédé d'ordonnancement conforme à l'invention, dans un mode préféré de réalisation; - la figure 2 représente, sous forme d'organigramme, les principales io étapes d'un opérateur d'extraction de file dans un procédé d'ordonnancement conforme à l'invention, dans un mode préféré de réalisation; - les figures 3A à 3F représentent un exemple de fonctionnement du procédé d'ordonnancement des figures 1 et 2; - la figure 4 représente un dispositif d'ordonnancement conforme à 15 l'invention dans un mode préféré de réalisation; et - la figure 5 représente un dispositif de traitement de paquets conforme à l'invention dans un mode préféré de réalisation. Description détaillée d'un mode de réalisation Nous allons maintenant décrire un procédé d'ordonnancement conforme à l'invention dans un mode préféré de réalisation. Dans l'exemple décrit ici, ce procédé d'ordonnancement est mis en oeuvre par un programme informatique PROG_ORD. Conformément à l'invention, ce procédé d'ordonnancement est un procédé de type DRR, modifié afin de permettre un traitement prioritaire aux 25 paquets des flots dont le débit ne dépasse pas le débit équitable. Dans le mode préféré de réalisation décrit ici, ce procédé d'ordonnancement permet en outre de réaliser des mesures de congestion nécessaires à un module de contrôle d'admission décrit ultérieurement en référence à la figure 4. :3o On supposera par la suite que le procédé d'ordonnancement traite des paquets p, appartenant à des flots d'indice i. Dans le mode préféré de réalisation décrit ici, le procédé d'ordonnancement selon l'invention utilise des files d'attente différentes Queue_i pour mémoriser les paquets p de chacun des flots actifs i. On notera que le procédé d'ordonnancement selon l'invention permet un quota différent par flot i, bien que l'application envisagée de différenciation implicite de qualité de service suppose que les quotas soient identiques et égaux à la taille maximale d'un paquet MTU (Maximum Transfert Unit). Quoi qu'il en soit, le quota (Li est supérieur ou égal à la taille maximale MTU. ro Dans l'exemple détaillé décrit ici, ces files d'attente sont numérotées de 1 à n, n étant le nombre maximal de flots actifs. Le procédé d'ordonnancement décrit ici utilise en outre une file d'attente supplémentaire réservée à un flot fictif destiné à la mesure du débit équitable, le débit équitable devant être entendu comme le débit que réaliserait un flot de données qui aurait en permanence des paquets à émettre. Conformément à l'invention, le procédé d'ordonnancement utilise également une file d'attente prioritaire PQ pour servir les paquets déterminés prioritaires en fonction des caractéristiques intrinsèques du débit des flots auxquels ils appartiennent. Dans la suite de la description on distinguera les files d'attente réelles (PQ, Queue_1, ..., Queue_n) de la file d'attente fictive pour la mesure du débit équitable. Les files d'attente réelles sont toutes des files d'attente du type FIFO (first in first out) connu de l'homme du métier. Le procédé d'ordonnancement selon l'invention décrit ici utilise également une liste des flots actifs ActiveList, et deux opérateurs, InsertActiveList() et RemoveActiveList(), respectivement adaptés à ajouter un indice de flot à la fin de la liste des flots actifs ActiveList et à enlever un indice de flot de cette liste. Ce procédé d'ordonnancement utilise également une fonction FreeBuffer() adaptée à libérer une place mémoire en rejetant le paquet situé à la tête de la file d'attente Queue_i la plus longue, selon la méthode décrite dans Stochastic Fairness Queueing , P. McKenney, Internetworking: Research and Experience, Vol. 2, jan. 1991, pp 113-131. D'autres stratégies de libération de la mémoire qui veillent à préserver l'équité entre les flots peuvent aussi être utilisées. Comme dans la plupart des procédés d'ordonnancement connus, le procédé d'ordonnancement selon l'invention décrit ici utilise principalement deux opérateurs standards de manipulation de files d'attente: - un opérateur InsertInQueue() d'insertion d'un paquet en fin de file; io - un opérateur RemoveFromQueue() adapté à retourner l'élément en tête de la file. Au cours d'une étape préliminaire d'initialisation, le programme d'ordonnancement PROG_ORD initialise les compteurs de déficit DC i à 0 pour toutes les files d'attente Queue_i, et insère, dans la liste de flots actifs ActiveList l'indice 0 correspondant au flot fictif pour la mesure du débit équitable. Nous allons maintenant décrire, en référence à la figure 1, les principales étapes de l'opérateur de mise en file Enqueue(). Sur réception d'un paquet p, l'opérateur de mise en file Enqueue() met en oeuvre une première étape E10 au cours de laquelle il teste si la zone de :?o mémoire tampon ( buffer zone an anglais) dans laquelle sont mémorisés les paquets de tous les flots actifs est saturée ou non; Si la mémoire tampon est saturée, le résultat du test E10 est positif. Ce test est alors suivi par une étape E20 au cours de laquelle on libère de la place mémoire en rejetant le paquet situé à la tête de la file d'attente Queue_i :2s la plus longue, ceci par appel à la fonction FreeBuffer() précitée. L'étape E20 de libération mémoire est suivie par une étape E30, au cours de laquelle on obtient le numéro i du flot auquel appartient le paquet p. En revanche, si la liste de flots actifs ActiveList n'est pas pleine, le résultat du test E10, précédemment décrit, est négatif. Ce test est alors suivi par l'étape :3o E30 d'obtention décrite ci-dessus. L'étape E30 d'obtention de l'indice de flot est suivie par un test E40, au cours duquel on vérifie si le flot i du paquet p est actif, ce qui revient à vérifier si le flot i est contenu dans la liste de flots actifs ActiveList. Lorsque tel n'est pas le cas, le résultat du test E40 est négatif. Ce test est alors suivi par une étape E42, au cours de laquelle on insère le flot i dans la liste de flots actifs ActiveList par appel à la fonction InsertActiveList() précitée. Cette étape E42 d'insertion est suivie par une étape E44, au cours de laquelle on initialise à 0 un compteur de déficit DC_i de la file d'attente Queue_i associée au flot actif i. to Ce compteur de déficit DC_i, est similaire à celui de la méthode d'ordonnancement DRR connue de l'homme du métier. Conformément à l'invention, chaque flot nouvellement reçu peut émettre, par cycle, des données en priorité à hauteur de son quota A cet effet, l'étape E44 d'initialisation est suivie par une étape E46, au is cours de laquelle on mémorise dans une variable BytesCount_i, la taille size(p) du paquet p, cette variable BytesCount__i, étant utilisée pour mémoriser le nombre d'octets des paquets du flot i à traiter avec priorité. Cette étape E46 d'affectation est suivie par une étape E48, au cours de laquelle on ajoute le paquet p à la fin de la file prioritaire PQ, en utilisant la :zo fonction InsertInQueue() d'insertion d'un paquet en fin d'une file d'attente. Cette étape E48 de mise en file est suivie par une étape E50, au cours de laquelle on initialise une variable Silence avec une valeur booléenne FALSE afin de mémoriser le fait qu'au moins un paquet p est prêt à être émis. Comme décrit ultérieurement, cet: indicateur Silence est utilisé pour:25 mesurer le débit équitable en cas d'absence de trafic, l'état d'absence de trafic étant représenté par le fait que l'identificateur égale la valeur booléenne TRUE. Cette étape E50 termine le procédé de mise en file du paquet p dans ce mode de réalisation. Lorsque le paquet p en cours de traitement est le paquet d'un flot i actif, :;o le résultat du test E40 décrit précédemment est positif. Ce test est alors suivi par une étape E52, au cours de laquelle on ajoute, au contenu de la variable précitée BytesCount_i, la taille du paquet p, cette 2878106 io variable BytesCount_i étant utilisée pour mémoriser le nombre d'octets des paquets du flot i à traiter avec priorité. Cette étape de cumul est suivie par un test E54, au cours duquel on vérifie si le nombre d'octets du flot i du paquet p à traiter en priorité (à savoir BytesCount_i) est inférieur ou égal au quota de la file d'attente Queue_i réservée à ce flot. Si tel est le cas, le résultat du test E54 est positif. Ce test est alors suivi par une étape de mise en file E56, similaire à l'étape de mise en file E48, déjà décrite, au cours de laquelle on ajoute le paquet p à la fin de la file prioritaire Io PQ. En revanche, si le nombre d'octets BytesCount_i à traiter avec priorité pour le flot i excède le quota pour ce cycle, le résultat du test E54 est négatif. Ce test est alors suivi par une étape E58 de mise en file du paquet p dans la file normale, c'est-à-dire non prioritaire, Queue_i réservée à ce flot i. is Les étapes E56 et E58 de mise en file terminent le procédé de mise en file de ce mode préféré de réalisation. Nous allons maintenant décrire, en référence à la figure 2, les principales étapes de l'opérateur d'extraction de file Dequeue(). Cet opérateur Dequeue() de fin de traitement d'un paquet est mis en 20 oeuvre: - à la fin de chaque opération d'envoi d'un paquet p; et - suite à l'arrivée d'un paquet lorsque le système est vide, cette deuxième condition étant remplie lorsque chaque file d'attente Queue_i, pour i variant de 1 à n, est vide et la file PQ est vide. Dans l'exemple de réalisation décrit ici, cet opérateur Dequeue() est réalisé sous la forme d'une boucle sans fin, constituée par les étapes F10 à F84 qui vont maintenant être décrites. Au cours d'une première étape F10,, on vérifie si la file prioritaire PQ est vide. Si tel n'est pas le cas, ce test F10 est: suivi par une étape F20, au cours de 3o laquelle on extrait le paquet p en tête de liste de la file prioritaire PQ. Cette opération s'effectue en utilisant la fonction RemoveFromQueue() adaptée à retourner un élément en tête d'une file d'attente. Cette étape F20 d'extraction est suivie par une étape F22, similaire à l'étape E30 déjà décrite en référence à la figure 1, d'obtention du numéro de flot i de ce paquet p. Cette étape F22 d'obtention est suivie par une étape F24 au cours de 5 laquelle on émet le paquet p. Cette étape d'envoi F24 est suivie par une étape F26, au cours de laquelle on soustrait, au compteur de déficit DC_i cle la file d'attente Queue_i associée au flot i du paquet p retiré de la file prioritaire PQ à l'étape F20, la taille size(p) de ce paquet p. io Cette étape F26 de soustraction est suivie par une étape F28, au cours de laquelle on ajoute la taille du paquet p au contenu d'une variable PB, cette variable PB étant utilisée pour mémoriser le volume du trafic à traiter avec priorité. Cette étape de cumul F28 est suivie par le test F10 déjà décrit, au cours duquel on vérifie si la file prioritaire PQ est vide. Ainsi, les étapes F10 à F28 constituent une boucle qui se prolonge tant qu'il y a des paquets présents dans la file prioritaire PQ. Au cours de cette boucle, les compteurs de déficit DC_i associés aux flots i dont les paquets ont été émis en priorité sont décrémentés afin d'empêcher 20 chacun des flots de dépasser son quota dans le cycle courant. Lorsque la file prioritaire PQ est vide, le résultat du test F10 est positif. Ce test est alors suivi par un test F30, au cours duquel on vérifie si au moins un flot réel est actif. Dans le mode de réalisation décrit ici, cela revient à vérifier que la liste de 25 flots actifs ActiveList contient plus d'un élément, cette liste contenant de toute façon le flot fictif 0 utilisé pour la mesure du débit équitable. Lorsque tel n'est pas le cas, le résultat de ce test F30 est négatif. Ce test est alors suivi par une étape F32 au cours de laquelle on affecte à la variable Silence, décrite précédemment à l'étape E50 de la figure 1, la constante booléenne TRUE, afin de représenter le fait qu'il n'y a plus aucun paquet à émettre, que ce soit dans la file prioritaire PQ ou dans l'une de ses files d'attente non prioritaires Queue_i. Cette étape d'affectation F32 est suivie par l'étape F10 déjà décrite, au cours de laquelle on teste si la file prioritaire PQ est vide ou non. Lorsqu'au moins un flot réel est actif, le résultat du test F30 est positif. Ce test est alors suivi par une étape F34, au cours de laquelle on obtient 5 'Identificateur du flot i en tête de la liste des flots actifs ActiveList. Cette étape d'obtention F34 est suivie par un ensemble d'étapes F40 à F48, destiné à mesurer le volume d'octets FB qu'aurait pu émettre le flot fictif 0, ce volume FB servant, comme décrit ultérieurement, à estimer le débit équitable. Plus précisément, au cours de l'étape F40, on teste si le flot obtenu en lo tête de la liste des flots ActiveList à l'étape précédente F34, est le flot fictif 0. Si tel est le cas, le résultat du test F40 est positif. Ce test est alors suivi par une étape F42, au cours de laquelle on ajoute au volume FB le quota Q_0 alloué au flot fictif O. Cette étape de cumul F42 est suivie par une étape F44, au cours de 1s laquelle on enlève la file fictive 0 de la tête du cycle pour la rajouter immédiatement à la fin du cycle en utilisant les opérations standard InsertActiveList() et RemoveActiveList() précitées. Lorsque le flot actif i obtenu en test de la liste des flots actifs ActiveList, au cours de l'étape F34 est un flot réel, le résultat du test F40 est négatif. Ce test est alors suivi par une étape F50, au cours de laquelle, on ajoute, à la valeur courante du compteur de déficit DC_i pour ce flot i, son quota Q_i. Cette étape de cumul F50 est suivie par une série d'étapes F60 à F68 pour émettre les paquets du flot i jusqu'à hauteur de son quota Q_i. Plus précisément, au cours d'un test F60, on vérifie que le compteur de 25 déficit DC_i est strictement positif et que la file d'attente non prioritaire Queue_i est non vide. Lorsque tel est le cas, le résultat du test F60 est positif. Ce test est alors suivi par une étape F61, au cours de laquelle on mémorise dans une variable s la taille du paquet en tête de la file d'attente Queue_i. :;o Cette étape F61 est suivie par un 1:est F62 au cours duquel on vérifie si cette taille s est inférieure ou égale au compteur de déficit DC_i pour ce flot. Lorsque tel est le cas, le résultat du test F62 est positif. Ce test est alors suivi par une étape F64, au cours de laquelle on envoie ce paquet, après l'avoir retiré de la file d'attente Queue_i par utilisation de la fonction RemoveFromQueueQ. L'étape F64 d'envoi est suivie par une étape F66, au cours de laquelle on soustrait, du compteur de déficit DC_i, la taille s de ce paquet. Cette étape de soustraction F66 est: suivie par le test F60 déjà décrit, au cours duquel on vérifie que la file d'attente Queue_i associée au flot i est non vide et que le compteur de déficit DC_i pour cette file est strictement positif. lo Lorsque tous les paquets du flot i ont été émis, jusqu'au quota DC_i autorisé, le résultat du test F60 ou du test F62 est négatif. On retire alors, au cours d'une étape F70 le flot i de la liste des flots actifs ActiveList en utilisant l'opérateur RemoveActiveList, déjà mentionné. Cette étape F70 de retrait est suivie par un test F80, au cours duquel on vérifie si la file d'attente Queue_i associée au flot i est vide. Si tel est le cas, on initialise le compteur de déficit DC_i associé à ce flot i à 0, au cours d'une étape F82 d'initialisation. Dans le cas contraire, on insère le flot i à la fin de la liste des flots actifs ActiveList, en utilisant la fonction InsertActiveList au cours d'une étape ?o d'insertion F84. Les étapes F82 d'initialisation du compteur de déficit DC_i et F84 d'insertion du flot i dans la liste des flots actifs ActiveList sont suivies par le test F10 déjà décrit. L'homme du métier comprendra que, en pratique, la liste des flots actifs ActiveList doit être dimensionnée pour une faible probabilité de débordement. Dans un mode préféré de réalisation, lorsqu'un paquet d'un nouveau flot est reçu et que la liste des flots actifs ActiveList est pleine, ce paquet est mis dans la file prioritaire PQ mais le flot auquel il appartient n'est pas rajouté à la liste des flots actifs ActiveList. Ce paquet est alors envoyé (étape F24) mais les informations associées au flot auquel il appartient ne sont pas mises à jour. Ainsi, les paquets auxquels s'applique le traitement d'exception sont prioritaires même si le débit de leur flot excède le débit équitable actuel. Cette violation n'est pas gênante dans la mesure où la probabilité de rester dans cet état est très faible pour un flot à débit supérieur au débit équitable au fur et à mesure de l'arrivée des paquets. Il est à noter que l'algorithme d'ordonnancement, selon l'invention, bassur la méthode DRR connue est de complexité en 0(1). Les figures 3A à 3F illustrent un exemple de fonctionnement du procédé d'ordonnancement conforme à l'invention décrit précédemment, en référence lo aux figures 1 et 2. On supposera ici que cette description commence avec l'hypothèse que trois files d'attente Queue_1, Queue_2, Queue_3 contiennent des paquets p des flots respectifs flot 1, flot 2, flot 3. La taille de ces paquets est reportée sur ces figures. On supposera aussi qu'au début de ce scénario, la file prioritaire PQ est vide. Enfin, la valeur du quota allouée à chaque flot i est supposée égale à 1 500. Dans ces différentes figures, la flèche noire indique la tête de la liste des 20 flots actifs dans le cycle, ce cycle suivant l'ordre des files non prioritaires suivant: Queue_1, Queue_2, Queue_3, Queue_4. Le paquet en cours de service est grisé à chacune des différentes étapes. Initialement, comme représenté figure 3A, le flot qui est en tête de liste est le flot 1 associé à la file d'attente Queue_1. Son compteur de déficit DC_1 est augmenté par son quota Q1, à savoir 1 500. Le routeur 100 peut donc commencer à servir le premier paquet, grisé, de cette file d'attente Queue_1, la taille de ce paquet étant ici de 500 octets. On suppose, en référence à la figure 3B, qu'un paquet appartenant à un 3o nouveau flot 4, arrive pendant le service du paquet précédent. Une file Queue_4 est créée et est associée à ce flot 4. Contrairement à ce qui se passerait dans le cadre d'un ordonnancement de type DRR classique, ce paquet est ici inséré dans la file prioritaire PQ, comme décrit précédemment, en référence à l'étape E48. Cependant, on poursuit le traitement du flot 1, la taille du deuxième 5 paquet de la Queue_1, à savoir 500 octets, étant inférieure au nouveau déficit DC_1 (résultats des tests F60 et F62 positifs). A l'étape représentée à la figure 3C, le traitement du flot 1 est achevé puisque le déficit DC_1 associé à la file d'attente Queue_1 égale 500, ce déficit étant inférieur à la taille 1 000 du prochain paquet (résultat du test F62 négatif). Conformément à l'invention et, contrairement à ce qui se passerait dans le cadre d'un ordonnancement de type DRR classique, on sert la file prioritaire PQ (résultat du test F10 négatif), celle-ci contenant le paquet appartenant au flot 4 dont le déficit DC _4 est décrémenté (voir étape F66). Au cours de l'étape suivante représentée à la figure 3D, la file prioritaire PQ étant devenue vide (test F10 positif), on traite le premier flot réel actif (test F30 positif), à savoir ici le flot 2, associé à la file d'attente Queue_2. Au cours de l'étape suivante représentée à la figure 3E, on traite le flot suivant (flot 3) car la taille du paquet restant dans la file d'attente Queue_2 est supérieure au quota DC_2 associé à cette file d'attente (résultat du test F62 zo négatif). La dernière étape représentée à la figure 3F, constitue le début d'un nouveau cycle où l'on recommence à servir le flot 1. Le flot 4 n'est plus actif car sa file Queue_4 est vide, il ne fait donc plus partie de ActiveList. La figure 4 représente un disposit:if d'ordonnancement 100 conforme à l'invention dans un mode préféré de réalisation. Typiquement, ce dispositif d'ordonnancement peut être implémenté dans un routeur, ou dans un processeur ou microprocesseur pour un routeur. De façon classique, ce dispositif reçoit des paquets p, qu'il ordonne en vue de leur émission, ou rejette en cas de débordement. :3o Sur cette figure 4, la référence 34 désigne le départ des paquets (étapes F24, F64) tandis que la référence 32 désigne le rejet des paquets (étape E20). Ce dispositif d'ordonnancement 100, comporte un processeur 110, une mémoire morte 120, une mémoire vive 130, une horloge 140. Le dispositif d'ordonnancement 100 comporte également des moyens matériels et logiciels de communication 150 constitués par exemple par une carte réseau reliée au réseau Internet 10 et par des couches logicielles adaptées à mettre en oeuvre le protocole de communication TCP/IP. Ces moyens de communication 150 sont notamment adaptés à recevoir un paquet p et à le mémoriser dans une zone 131 de la mémoire vive 130 et à lire un paquet p à partir de cette zone pour l'envoyer sur le réseau Internet 10. De façon connue les différents matériels du dispositif d'ordonnancement sont reliés entre eux par un système de bus 160. Conformément à l'invention, la mémoire morte 120 comporte le programme d'ordonnancement PROG_ORD, et la mémoire vive 130 une structure de données 170 pour la rnise en oeuvre de ce programme d'ordonnancement PROG_ORD. Cette structure de données 170 est représentée sous forme d'un tableau dont chaque ligne correspond chacune à une file d'attente Queue_i, associée à un flot i. Plus précisément, dans ce tableau: - la première colonne mémorise l'indice i du flot; - la deuxième colonne mémorise l'identificateur du flot i; - la troisième colonne mémorise le quota de la file Queue_i; - la quatrième colonne mémorise le compteur de déficit DC_i de la file Queue_i; - la cinquième colonne permet de gérer le cycle des flots de la liste des flots actifs ActiveList en mémorisant l'indice de la file d'attente suivant la file Queue_i dans cette liste. La gestion de ces pointeurs permet, de façon connue, l'insertion et l'extraction de flots dans la liste des flots actifs ActiveList; et - la dernière colonne donne l'adresse de mémorisation du paquet en tête de la file d'attente Queue_i dans la mémoire vive 130. De façon connue, les paquets suivants dans la file d'attente Queue_i sont accessibles au moyen d'une liste de pointeurs chaînés. Dans un mode préféré de réalisation, la vérification de l'activité d'un flot i est effectuée en comparant l'identificateur d'un flot au contenu de la deuxième colonne de la structure de données 170, par exemple en employant une mémoire CAM (Content Addressable Memory). Nous allons maintenant décrire, en référence à la figure 5, un routeur 50 conforme à l'invention dans un mode préféré de réalisation. Ce routeur 50 comporte un dispositif d'ordonnancement 100 identique ou similaire à celui décrit précédemment en référence à la figure 4. Dans le mode préféré de réalisation décrit ici, ce routeur comporte en io outre un module 24 de contrôle d'admission de chaque paquet p des flots entrants (flèche pleine référencée 31). Les paquets p présentés à ce module sont, par exemple, déterminés par des fonctions d'acheminement classiques qui peuvent inclure un partage de charge, obtenu en appliquant une fonction hash à un sous-ensemble des champs de l'identificateur de flot. Dans l'exemple de réalisation décrit ici, ce module 24 de contrôle d'admission effectue deux niveaux de contrôle pouvant être mis en oeuvre indépendamment. A cet effet, le module d'acheminement 24 consulte et met à jour une liste 30 de flots dits protégés , à savoir les flots admis par les moyens d'acheminement 24 actifs (c'est-à-dire qu'un paquet de ce flot a été identifié depuis un intervalle de temps prédéterminé), et décide, sur la base de cette liste 30 de flots protégés, si les paquets d'un flot donné doivent être directement acheminés ou non, c'est-à-dire sans qu'il soit nécessaire de vérifier les conditions d'admission pour acheminer le paquet vers le dispositif d'ordonnancement. Concrètement, cette liste de flots protégés 30 est une liste d'identificateurs de flots indiquant pour c:hacun d'entre eux, l'heure d'arrivée du dernier paquet. Dans un mode préféré de réalisation, chaque liste est associée à une 30 partition de l'espace des identificateurs, ceci afin de limiter les capacités de chaque liste et donc de garantir l'extensibilité. Dans ce mode de réalisation, un flot est effacé de la liste d'identificateurs 30 lorsque le temps écoulé depuis le dernier paquet reçu pour ce flot, dépasse un seuil ou un intervalle de temporisation. La longueur de cet intervalle est un paramètre du système, par exemple de l'ordre de quelques secondes. Préférentiellement, cette liste 30 est dimensionnée de façon à limiter la probabilité de saturation, situation dans laquelle un flot devrait être mis dans la liste, alors que celle-ci est déjà pleine. La conséquence d'une telle saturation serait qu'un flot tarderait à acquérir le statut de flot protégé. Ces paquets seraient néanmoins acheminés correctement si l'état de congestion le permet. De façon connue, la probabilité de saturation peut être rendue suffisamment faible par un dimensionnement adéquat. Si le paquet appartient à un flot: protégé, il est acheminé directement (flèche 38) vers le dispositif d'ordonnancement 100 correspondant à la bonne interface de sortie, l'heure d'arrivée du dernier paquet de ce flot protégé étant mise à jour dans la liste d'identificateurs 30. Si le flot n'est pas déjà protégé, il faut procéder à une prise de décision d'acheminement, cette décision étant prise sur la base de conditions d'admission reçues du module d'ordonnancement. Conformément à l'invention, une autre fonction détermine les conditions d'admission à partir de mesures de congestion effectuées par le dispositif d'ordonnancement 100. La fourniture de ces conditions est matérialisée par la flèche référencée 36 sur la figure 5. Préférentiellement, on utilise deux estimateurs de congestion, le débit 25 équitable DE et la charge prioritaire CP: - le débit équitable est une mesure du débit que réaliserait un flot de données qui aurait, en permanence, des paquets à émettre; et - la charge prioritaire est la somme de la longueur des paquets prioritaires transmis dans un certain intervalle, divisée par la durée de cet intervalle. En effectuant des mesures périodiques, on obtient un comptage en continu de l'état de charge du lien contrôlé. La période des mesures est typiquement différente pour les deux valeurs de débit équitable (par exemple, de l'ordre de la centaine de millisecondes) et de charge prioritaire (par exemple, de l'ordre de la dizaine de millisecondes). Dans le mode préféré de réalisation de l'invention décrit ici, ces estimateurs de congestion, CP et DE sont calculés par un processus de mesure distinct du procédé d'ordonnancement décrit ci-dessus à partir des compteurs de congestion PB et FB régulièrement mis à jour par le procédé d'ordonnancement aux étapes F28 et F42. Par ailleurs, le processus de mesure (ou un autre module) comporte des moyens, non détaillés ici, adaptés à mesurer le temps total Silence Time, io pendant lequel la variable logique Silence est égale à la valeur booléenne TRUE, étant rappelé que cette variable Silence est mise à la valeur TRUE à l'étape F32 et à la valeur FALSE, à l'étape E50. En échantillonnant le compteur de congestion PB à intervalles réguliers, le processus de mesure déduit une estimation de la charge prioritaire, comme la différence entre les valeurs PB mesurées au début et à la fin de l'intervalle de mesure, divisée par la durée de cet intervalle. Soit: - PB(T) la valeur, en octets, de PB à l'instant T; - (Tl, T2) un intervalle de mesure (en secondes) ; et - C le débit du lien (en bits/seconde), alors, un estimateur de charge prioritaire CP pour cet intervalle est: CP(T1, T2) = (PB(T2) PE3(T1)) x 8 / (T2 Ti) / C. Conformément à l'invention, on suppose, pour estimer le débit équitable 25 DE, que le flot fictif 0 émet continuellernent des paquets de taille fixe égale à Q0 (quota associé au flot fictif 0). Dans une période où la file prioritaire est constamment occupée, le nombre d'octets qu'aurait pu émettre le flot fictif 0 se déduit de l'évolution du compteur de congestion FB. Lorsque la file est vide, le flot fictif 0 aurait pu émettre, au débit C du lien. En conjuguant la succession de périodes d'activité et de silence, on déduit une estimation du débit équitable DE de la manière suivante, soit FB (T) la valeur, en octets, de FB à l'instant T; - (Ti, T2) un intervalle de mesure; et - Silence Time la durée totale de silence pendant l'intervalle (Tl, T2), on obtient: DE (Tl, T2) = max (Silence_Time x C/ (T2-T1), (FB(T2)-FB(T1)) x 8 / (T2-T1)). L'homme du métier comprendra aisément, que dans le calcul du débit équitable DE, le premier terme prévaut, lorsque la charge du lien est faible (car le flot fictif 0 aurait utilisé toute la capacité du lien restant disponible), le deuxième terme prévalant en période d'activité, ce terme mesurant io approximativement le débit réalisé par un flot réel qui a toujours au moins un paquet dans la file d'attente qui lui est associée. Le module d'ordonnancement 1.00 détermine ensuite une condition d'admission à partir des estimateurs de congestion CP (charge prioritaire) et DE (débit équitable). En pratique, cette détermination peut être effectuée en utilisant une fonction Admit(CP, DE) dont le résultat égale 1 (respectivement 0), lorsque les paquets p de nouveaux flots, n'ayant pas encore le statut de flot protégé, doivent être acheminés (respectivement rejetés), le résultat de cette fonction d'admission étant fourni (flèche 36) par le module d'ordonnancement 100 au module d'acheminement 24. Lorsque les conditions d'admission sont favorables, le nouveau flot dont le paquet est acheminé, est inséré dans la liste des flots protégés et acquière ainsi le statut de flot protégé. Sur cette figure, la flèche pleine 39 représente le rejet des premiers paquets des nouveaux flots par le module d'acheminement 24. Sur cette figure, la flèche pleine 38 représente l'acheminement des paquets des flots protégés vers le module d'ordonnancement 100. Les conditions appliquées peuvent dépendre d'attribut particulier du paquet dont la valeur du champ classe de trafic en IPv6 ou le champ ToS en IPv4 ou des adresses IP source et destination. Le contrôle d'admission permet d'assurer la transparence des flots admis: conservation du signal pour les flots temps réel, conservation du débit pour les flots de données. En fait, cette transparence n'est offerte qu'aux flots dont le débit crête (déterminé par les limitations externes) reste inférieur à un certain seuil. Pour choisir des seuils d'admission relatifs au débit équitable et à la charge prioritaire permettant de réaliser un contrôle d'admission permettant 5 d'assurer la transparence des flots, l'homme du métier pourra se reporter au document FR2854296 de la Demanderesse précédemment cité. REVENDICATIONS 1. Procédé d'ordonnancement de paquets (p) appartenant à différents flots 5 (i), comportant: - une étape (E58) de mise en file de chaque paquet dans une file d'attente (Queue_i) associée au flot dudit paquet (p) ; et - pour chacune desdites files d'attente (Queue_i) traitées cycliquement, une étape (F64) d'émission des paquets contenus dans io ladite file d'attente (Queue_i) jusqu'à hauteur d'un quota (Q_i) pour ledit cycle; ledit procédé étant caractérisé en ce qu'il comporte en outre: - une étape (E40, E54) de détermination de la priorité dudit paquet (p), préliminaire à ladite étape (E58) de mise en file, les paquets prioritaires étant d'une part: - les premiers paquets des flots non actifs, à savoir les flots dont aucun paquet n'a été reçu dans ledit cycle; et d'autre part: - les paquets des flots actifs et dont le volume (BytesCount_i) de paquets reçus dans ledit cycle est inférieur audit quota (Q_i) ; et - une étape (F24) d'émission, en priorité dans ledit cycle, des paquets déterminés prioritaires au cours de ladite étape (E40, E54) de détermination. 2. Procédé d'ordonnancement selon la revendication 1, caractérisé en ce qu'il comporte en outre une étape de mesure de paramètres (CP, DE) de 25 congestion. 3. Procédé d'ordonnancement selon la revendication 2, caractérisé en ce que lesdits paramètres de congestion sont constitués par: - une valeur (DE) de débit équitable, qui est une mesure de débit que réaliserait un flot de données qui aurait toujours des paquets à 30 émettre; et - une valeur (CP) de charge prioritaire, correspondant au volume desdits paquets prioritaires, transmis pendant un intervalle de temps, divisé par la durée de cet intervalle. 4. Dispositif d'ordonnancement de paquets (p) appartenant à différents flots 5 (i), comportant: - des moyens de mise en file de chaque paquet dans une file d'attente (Queue_i) associée au flot dudit paquet (p) ; et des moyens pour traiter cycliquement chacune desdites files d'attente (Queue_i), lesdits moyens de traitement comportant des io moyens d'émission des paquets contenus dans ladite file d'attente (Queue_i) jusqu'à hauteur d'un quota ((Li) pour ledit cycle; ledit dispositif d'ordonnancement étant: caractérisé en ce qu'il comporte en outre: - des moyens de détermination de la priorité dudit paquet (p), 15 préalablement à ladite mise en file dudit paquet, les paquets prioritaires étant d'une part: - les premiers paquets des flots non actifs, à savoir les flots dont aucun paquet n'a été reçu dans ledit cycle; et d'autre part: - les paquets des flots actifs et dont le volume (BytesCount_i) de paquets reçus dans ledit cycle est inférieur audit quota (Q_i) ; et - des moyens d'émission, en priorité dans ledit cycle, des paquets déterminés prioritaires par lesdits rnoyens de détermination. 5. Dispositif d'ordonnancement selon la revendication 4, caractérisé en ce 25 que lesdits moyens de détermination sont adaptés à déterminer également comme prioritaire, les paquets des flots dont aucun paquet n'a été reçu depuis une durée prédéterminée. 6. Dispositif d'ordonnancement selon la revendication 4 ou 5, caractérisé en ce qu'il comporte en outre des moyens de mesure de paramètres (CP, DE) 30 de congestion dudit dispositif. 24 2878106 7. Dispositif d'ordonnancement selon la revendication 6, caractérisé en ce que lesdits paramètres de congestion sont constitués par: - une valeur (DE) de débit équitable, qui est une mesure de débit que réaliserait un flot de données qui aurait toujours des paquets à 5 émettre; et - une valeur (CP) de charge prioritaire, correspondant au volume desdits paquets prioritaires, transmis pendant un intervalle de temps, divisé par la durée de cet intervalle. 8. Routeur de paquets caractérisé en ce qu'il comporte un dispositif lo d'ordonnancement (100) selon la revendication 6 ou 7, et un module (24) de contrôle d'admission desdits paquets en fonction des paramètres de congestion mesurés par ledit dispositif d'ordonnancement. 9. Routeur selon la revendication 8, caractérisé en ce que ledit module d'admission est en outre adapté à acheminer directement les paquets appartenant à des flots dits protégés, à savoir les flots pour lesquels au moins un paquet a été reçu par ledit module d'admission depuis un intervalle de temps prédéterminé. 10. Programme d'ordinateur stocké sur un support d'informations, ledit programme comportant des instructions permettant la mise en oeuvre d'un procédé d'ordonnancement selon l'une quelconque des revendications 1 à 3, lorsque ce programme est chargé et exécuté par un système informatique. 11. Support d'informations lisible par un système informatique, éventuellement totalement ou partiellement amovible, notamment CD- ROM ou support magnétique, tel un disque dur ou une disquette, ou support transmissible, tel un signal électrique ou optique, caractérisé en ce qu'il comporte des instructions d'un programme d'ordinateur permettant la mise en oeuvre d'un procédé d'ordonnancement selon l'une quelconque des revendications 1 à 3, lorsque ce programme est chargé et exécuté par un système informatique.