FR 2899054 A1 20070928 FR 0602649 A 20060327 PROCEDE ET' SYSTEME D'ALLOCATION DE RESSOURCES L'invention concerne un procédé et un système d'allocation de ressources. Elle s'applique dans un réseau de communications, en particulier aux communications dans un réseau radio. La présente invention trouve son application dans le domaine des réseaux radio fonctionnant sur le principe de l'accès multiple à répartition dans le temps ou TDMA (abrégé en anglo-saxon de Time Division Multiple Access). Elle s'applique entre autre et de façon non exclusive aux communications dans un réseau distribué ad hoc et en particulier dans un réseau de type ad hoc dont les données présentent un caractère d'urgence. Il existe plusieurs techniques permettant de partager des ressources entre les différents utilisateurs ou services d'un réseau. Le multiplexage en fréquence (en anglais Frequency-Division Multiple Access ou FDMA), par exemple, consiste à diviser la bande passante d'un support de communication en bandes de fréquences distinctes. Le multiplexage temporel ou l'accès multiple à répartition dans le temps (TDMA) consiste à diviser le temps en petits intervalles ou fenêtres temporelles parfois appelées slots en anglais, et à attribuer un intervalle de temps donné à chaque service ou utilisateur. Les utilisateurs émettent alors des données sur des intervalles de temps différents. Dans un réseau ad hoc, fonctionnant sur le principe du TDMA, une station ou un noeud du réseau joue le rôle de coordinateur du réseau en attribuant les instants de transmission aux différents utilisateurs ou services en fonction de leurs besoins. Ce noeud peut être appelé noeud central, noeud maître, ordonnanceur ou cluster head en anglais. Chaque noeud du réseau, par exemple, peut être associé à un utilisateur ou à un service. Les réseaux de type ad hoc présentent comme avantage de permettre des transferts de haut débit et la possibilité d'interconnexion avec des structures existantes. La mise en oeuvre de ce type de réseau nécessite une gestion des allocations très précise et équitable entre les utilisateurs ou les services. De plus, dans un tel réseau, les données à transmettre n'ont pas toutes les mêmes besoins. Par exemple, la voix périrne rapidement (à environs 250ms) et il faut donc minimiser les délais de transmission. Par contre, la perte de quelques paquets de ce type de données ne détériore pas de manière significative la qualité de transmission. En revanche, pour la classe trafic de fond qui correspond à des trafics secondaires sans contraintes de temps réel, comme par exemple le courrier électronique, les données peuvent être soumises aux délais mais il est impératif que tous les paquets soient transmis. Les besoins exprimés par les noeuds peuvent être liés à la qualité de service (QoS) du service associé. La qualité de service est spécifiée par des paramètres de QoS exprimant des caractéristiques prévues pour le transfert de données telles que le débit, le temps de transit, l'exactitude et la fiabilité. Différents procédés de gestion de files d'attente pour l'allocation des ressources sont actuellement connus de l'art antérieur, par exemple : • le premier arrivé est le premier servi ou en anglo-saxon FIFO ou First in First out ; • l'ordonnancement statique avec priorités absolues ou en anglo-saxon priority queuing ; • l'ordonnancement juste des paquets en fonction des flux détectés ou en anglo-saxon vveighted fair queuing ou flow based queuing ; • l'ordonnancement en fonction d'une classe de trafic déterminé ou en anglo-saxon class based queuing ou CBQ . Les classes peuvent être basées sur un nornbre de paramètres tels que la priorité, l'interface ou le programme d'origine; et • l'ordonnancement statique avec priorités relatives calculées sur une demande de garantie de bande passante ou en anglo-saxon Custom queuing . Le brevet US 2003/0198204 divulgue un procédé et un système d'allocation de ressources pour la transmission de données soumises à des contraintes de qualité de Service (C!oS). Ce système permet d'ordonner les trafics en se basant, dans un premier temps, sur des paramètres d'allocation statiques puis, en adaptant cet ordre grâce à des coefficients de compensation calculés en fonction du flux, du temps d'attente dans la file d'attente et de la priorité. Cette approche s'adapte bien à des trafics de type isochrones comme la vidéo. Toutefois, dans le cas de sources non déterministes (la voix par exemple dépend des locuteurs), la compensation ne semble pas suffisante pour rendre l'approche exploitable. (L'adaptation s'effectue peu à peu et ne peut pas répondre de façon immédiate à des trafics fortement variables. Par ailleurs, dans ce système, la notion de péremption des données ou de délai n'est pas absolue et rie permet donc pas de garantir des délais imposés par certaines applications. Par exemple, la voix qui périme rapidement. Bien qu'elles soient efficaces, les différentes techniques d'allocation de ressources dans l'art antérieur présentent un certain nombre d'inconvénients : elles ne garantissent pas un ordonnancement selon la réelle urgence des données; - elles ne supportent pas de classification absolue selon des notions de délai ou de péremption de données et donc elles ne permettent pas de garantir des délais imposés par certaines applications; et elles ne résolvent pas les problèmes d'ordonnancement pour les trafics fortement variables et non déterministes. Dans la description, on désigne par noeud ou station toute entité du réseau, implémentée en (matériel ou logiciel qui peut être le point d'entrée ou le point de sortie d'un échange ou d'une transmission de données ou d'informations entre stations. Une requête caractérise un besoin de ressource, comme par exemple, un instant de transmission ("slot en anglais"), associé à une application ou une classe de service exprimée par un noeud d'un réseau auprès d'un mécanisme30 d'allocation (l'ordonnanceur). Un besoin peut indiquer notamment une spécification de qualité de service de bout en bout. L'invention concerne un procédé d'allocation de ressources dans un réseau de communication comportant plusieurs noeuds adaptés à émettre et à recevoir des données et un noeud central adapté à allouer des ressources, caractérisé en ce qu'il comporte au moins les étapes suivantes : - au moins un noeud émet une ou plusieurs requêtes vers le noeud central, chaque requête étant associée à un besoin, le noeud central attribue une durée de vie à chaque requête en fonction du besoin de la requête, et on ordonne chaque requête dans une file d'attente en fonction de la durée de vie et de l'instant de réception de la requête. Dans un mode de réalisation de l'invention, la durée de vie peut être attribuée à une requête selon l'application associée à la requête. Ainsi, les requêtes associées à des applications urgentes ou importantes peuvent être placées au début de la file d'attente. La durée de vie peut être attribuée à une requête en fonction d'une qualité de service (QoS) associée à la requête. Ceci permet une classification de requêtes selon la qualité de service de l'application associée et permet de respecter les priorités entre les différents niveaux de qualité de service. Ainsi, les requêtes de haute priorité peuvent être privilégiées dans le classement de la file d'attente. La durée de vie peut être attribuée en fonction des contraintes temporelles de l'application associée à la requête ou en fonction du temps admissible pour le transfert des données associées à la requête. Ceci permet de satisfaire les requêtes les plus pressées et de fournir un ordonnancement répondant à la réelle urgence des paquets. Le réseau est par exemple un réseau ad hoc. La durée de vie attribuée à une requête peut dépendre du nombre de noeuds du réseau que devront traverser les données à transmettre. Ceci permet d'assurer la transmission des données de bout en bout d'un réseau. On peut utiliser un protocole TDMA. Ainsi, les ressources à allouer peuvent être les instants de transmission. Dans un mode de réalisation pour des instants d'expirations égaux, on ordonne les requêtes dans la file d'attente selon la qualité de service des requêtes, un instant d'expiration pour une requête étant défini à partir de la durée de vie allouée à la requête et l'instant de réception de la requête. Le procédé peut comporter une étape consistant à discriminer entre les requêtes périssables et les requêtes non-périssables. Le procédé peut, par exemple, comporter en outre une étape où l'on vérifie si les requêtes sont périmées, et on élimine la ou les requêtes périmées de la file d'attente. Ceci permet la gestion des données périmées et ainsi de répondre à des contraintes temporelles imposées par les services associés aux requêtes. La vérification des requêtes peut, par exemple, consister à comparer l'instant d'expiration de chaque requête avec l'instant en cours et dans le cas où l'instant d'expiration d'une requête est inférieur à l'instant en cours, la requête est éliminée. Dans un autre mode de l'invention, on alloue à chaque requête une durée de vie en sortie et on compare un instant d'expiration en sortie, défini à partir du temps de vie en sortie de la requête, et l'instant de réception de la requête, avec l'instant en cours. Dans le cas ou l'instant d'expiration en sortie d'une requête est inférieur à l'instant en cours, la requête est éliminée. Le réseau est par exemple un réseau radio. Dans un mode de réalisation, on peut régler la durée de vie attribuée à une requête en fonction de la priorité ou les contraintes temporelles associées à la requête. Ceci permet cle fournir à ces requêtes un avantage concurrentiel dans l'accès à la ressource puisqu'elles seront systématiquement privilégiées dans le classement dans la file d'attente. L'invention concerne aussi un système d'allocation de ressources dans un réseau de communication comportant plusieurs noeuds adaptés à émettre et recevoir des données et un noeud central adapté à allouer des ressources, caractérisé en ce que plusieurs noeuds sont équipés d'un processeur adapté à envoyer une ou plusieurs requêtes vers le noeud central, chaque requête étant associée à un besoin et en ce que le noeud central est équipé d'un processeur adapté à attribuer un temps de vie à chaque requête reçue par le noeud central selon le besoin de ladite requête ; et ordonner chaque requête reçu dans une file d'attente en fonction de la durée de vie et de l'instant de réception de ladite requête tR . Le procédé et le système d'allocation de ressources selon l'invention présentent notamment les avantages suivants : ils permettent d'optimiser l'allocation des ressources ; ils permettent une allocation qui est équitable entre les noeuds d'un réseau ; ils permettent de satisfaire les priorités des services associées aux noeuds ; - ils permettent de fournir des garanties de service en terme de débit et de délai, qu'il s'agisse de transferts point à point ou de bout à bout ; et ils permettent de tenir compte des contraintes temporelles des données à transmettre et garantir un ordonnancement selon la réelle urgence des données. De plus, les données rie sont pas entrelacées par priorité ou par flux mais par réelles contraintes temporelles, et donc par leur réel degré d'urgence. Cet entrelacement est dépendant des données et non des flux, et s'adapte donc naturellement au caractère burst et non-déterministe de trafics tel que la voix, puisqu'il agit paquet par paquet. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description qui suit donnée à titre illustratif et nullement limitative en référence aux figures annexées dans lesquelles : - la figure 1 schématise un exemple d'un réseau ad hoc avec plusieurs noeuds et un noeud central; les figures 2A à 2C illustrent des échanges des données dans le réseau de la figure 1; - la figure 3 détaille les étapes du procédé selon un mode de réalisation de l'invention; les figures 4A à E illustrent le procédé détaillé dans la figure 3; la figure 5 illustre une étape de contrôle de données selon une variante de l'invention; et la figure 6 illustre une étape de contrôle de données selon une autre variante de l'invention. Afin de mieux faire comprendre l'objet de l'invention, l'exemple qui suit donné à titre illustratif concerne un réseau de communications ad hoc. La figure 1 schématise un exemple d'un réseau ad hoc 1 fonctionnant sur le principe du TDMA (accès multiple par division temporelle). Le réseau 1 comporte un noeud central 2 et une pluralité de noeuds 3 reliés entre eux et au noeud central 2 par des liens de communication. Chaque noeud 3 est équipé de moyens d'émission/réception et est associé à un service ou à un utilisateur. Le noeud central 2 est aussi équipé de moyens d'émission/réception et joue le rôle de coordinateur ou ordonnanceur du réseau en attribuant les instants de transmission aux noeuds 3 en fonction de leurs besoins q. Le besoin q peut correspondre à une qualité de service. Les noeuds 3 peuvent être mobiles ou non mobiles, par exemple, des micro-ordinateurs, des téléphones sans fils, des postes de télévision numériques. Les liens de communication peuvent être soit des liaisons filaires, soit des liaisons sans fils, par exemple, des liaisons radio. On notera que le procédé selon l'invention s'applique aussi pour tout autre protocole de communicai:ion. Les figure 2A à 2C illustrent d'une façon générale les échanges des données dans le réseau de la figure 1. Dans une première étape illustrée dans la figure 2A, chaque noeud 3 émet au moins une requête, sous la forme d'un paquet de données contenant les demandes des instants de transmission, à l'Ordonnanceur 2. Une requête correspond à un paquet de données qui contient une demande d'un instant ou des instants de transmission pour un noeud 3 donné. Les besoins d'instants de transmission sont spécifiés dans un espace à deux dimensions (Temporel et Importance, qualité de service) issues des applications associées aux noeuds via un système = connu en soi pour spécifier les caractéristiques d'un flux de données, tel que l'utilisation du champ TOS type of service de l'entête des paquets IP, l'interprétation du port des entêtes TCP/UDP qui indique l'application correspondante ou l'utilisation de multiples files d'attentes. A partir des requêtes reçues, l'ordonnanceur 2 détermine la répartition des instants de transmission comme il sera expliqué ci-après. L'ordonnanceur 2 transmet aux noeuds 3, la répartition des instants de transmission qui a été définie, comme représenté sur la figure 2B. Les noeuds 3 utilisent les instants de transmission qui leur ont été attribués pour transmettre des paquets de données vers leur destinataire comme illustré à la figure 2C. Sur les figures 3, 4A à 4C, on a illustré un exemple du procédé d'allocation des instants de transmission pour les différents noeuds. Ce procédé comporte les étapes suivantes :30 Dans une première étape 31, l'ordonnanceur 2 reçoit des demandes de ressources ou requêtes Rnqt émises par les noeuds 3 où n représente le noeud demandant la ressource, q la qualité de service (QoS) associée à cette requête Rnqt et t l'instant de réception de la requête Rnqt par l'ordonnanceur 2. La figure 4A illustre une première série des requêtes, R130,R120, R120 R100, R230,R230, R220 et R210 de deux noeuds N1 et N2 du réseau, les requêtes étant classées selon leur qualité de service qO à q3. Dans une deuxième étape 32, l'ordonnanceur 2 alloue une durée de vie Atqi à chaque requête Rnqt, en fonction de la qualité de service qi associée à la requête Rnqt. La durée de vie Atq; allouée à chaque requête Rnqt est choisie, par exemple, en fonction des contraintes temporelles de l'application associée à la requête. La figure 4A illustre l'allocation de la durée de vie Atq; à la première série de requêtes reçues par l'ordonnanceur à un instant T0. Aux requêtes associées à la qualité de service q3 est attribuée une durée de vie Aq3=0, et aux requêtes associées à la qualité de service q2, q1 et qO sont attribuées respectivement une durée de vie Aq2, Aq1 et AqO où Aq0>Aq1>Aq2. Les figures 4B et 4C illustrent l'allocation des durées de vie associées à une deuxième série de requêtes R111, R231 R221, R201 et une troisième série de requêtes R132,R122, R232 R212, R202, reçues respectivement par l'ordonnanceur aux temps Ti et T2. Dans une troisième étape 33a, 33b, l'ordonnanceur 2 récupère les requêtes Rnqt en partant de la plus pressée jusqu'à la moins pressée. Il ordonne ensuite les requêtes Rnqt dans une file d'attente en respectant les instants d'expiration des requêtes comme représenté sur la figure 4D. L'instant d'expiration pour une requête Rnqt est défini par t+dtq;. L'ordre pour deux requêtes Rnigiti et Rn2q2t2 ayant respectivement une durée de vie Atgi et Atq2 est imposée par la relation suivante : Atql q21 Rnl,gl,tl Dans une quatrième étape 34a et 34b, on vérifie que les requêtes Rnqt dans la file d'attente ne sont pas périmées. Cette étape de contrôle consiste à comparer l'instant en cours Tc avec l'instant d'expiration t+dtq; de la requête Rnqt. Si l'instant d'expiration t+dtq; de la requête Rnqt est inférieur à l'instant en cours Tc, la requête Rrigt est éliminée de la file d'attente comme représenté sur la figure 4E. Dans une cinquième étape 35, les m premières requêtes Rnqt dans la file d'attente sont récupérées pour m instants de transmission disponibles comme illustré à la figure 4E. Dans une sixième étape 36, les requêtes récupérées sont ordonnées par noeud 25 n comme représenté sur la figure 4E. Dans une septième étape 37, la répartition des instants de transmission est inscrite dans un drapeau de signalisation et ensuite transmise de l'ordonnanceur aux noeuds. Le procédé selon invention décrit ci-dessus peut être réalisé selon de nombreuses variantes. Ainsi, selon certaines variantes le procédé ne comporte 30 pas la quatrième étape 34a et 34b de contrôle et d'élimination des requêtes périmées. Selon une variante de l'invention on peut affiner ou régler la durée de vie Atq; attribuée aux requêtes. A cet effet, on peut diminuer, voire annuler une durée de vie Atq; pour les applications à très fortes contraintes temporelles ou haute priorité par exemple la voix. Ceci permet de fournir à ces requêtes un avantage concurrentiel dans l'accès à la ressource puisqu'elles seront systématiquement privilégiées dans le classement dans la file d'attente. Selon une autre variante de l'invention, l'étape de contrôle consiste à définir des contraintes en sortie distinctes des contraintes imposées pour l'ordonnancement de la liste. Pour cela, on peut attribuer une durée de vie en sortie A tS; à chaque requête. La durée de vie en entrée A tq;, visant selon les cas, uniquement à avantager les requêtes de telle ou telle priorité ou QoS, elle ne correspond pas toujours aux contraintes réelles acceptables. On peut, par exemple, pour les requêtes à très fortes contraintes temporelles pour lesquelles on s'est imposé des durées de vie nulles pour l'ordonnancement (la voix par exemple) autoriser une marge du niveau de la sortie correspondant à la durée de vie réelle acceptable afin de permettre l'allocation. Dans ce cas, la vérification des requêtes périmées consiste à comparer l'instant d'expiration en sortie, défini à partir du temps de vie en sortie et l'instant de réception de la requête, avec l'instant en cours. Ainsi, les requêtes avec un instant d'expiration en sortie inférieur à l'instant en cours seront éliminées de la file d'attente. Dans le cas de données qui doivent être transmises quoiqu'il arrive, comme par exemple le trafic de fond, le procédé peut comporter en outre une étape de discrimination entre requêtes périssables et requêtes non périssables. La figure 5 illustre une variante de l'invention dans laquelle le procédé comporte une étape de discrimination 52 entre requêtes périssables et requêtes non périssables et une étape de contrôle 53 où les requêtes périssables sont ensuite contrôlées, selon une des méthodes de contrôle décrites ci-dessus, pour vérifier si elles sons: périmées ou pas. Les requêtes non-périmées et non périssables, comme par exemple les requêtes associées au courrier électronique, sont gardées dans la file d'attente 54 pour l'émission de l'allocation aux noeuds. La figure 6 illustre une autre variante de l'invention dans laquelle le procédé comporte une étape de contrôle 63 dans laquelle les requêtes non périssables sont re-échelonnées clans la file d'attente 61 et les requêtes périmées sont éliminées dans le cas où il ne reste plus d'instants de transmission à allouer. Ceci permet de gérer la congestion de la file d'attente et d'assurer les requêtes de qualité de service la plus forte. L'étape de contrôle des requêtes périssables et non périssables peut consister à allouer une durée de vie factice aux requêtes non périssables. Cette durée de vie est choisie, par exemple, selon la priorité du trafic, le rendant plus ou moins concurrentiel, mais n'est pas prise en compte par le contrôle de sortie. Les requêtes non périssables sont ajoutées aux requêtes allouées suivant l'ordre d'urgence temporelle sans qu'il y ait de vérification sur leur éventuelle péremption. Selon encore d'autres variantes de réalisation, la durée de vie peut être allouée à chaque requête ou affinée en fonction d'un ou plus des critères suivants : l'application associée à la requête, les contraintes temporelles liées à l'application et/ou le nombre de noeuds du réseau que devront traverser les données. Ce procédé peut être interfacé à un mécanisme de sessions de niveau MAC type mode connecté ou de niveau réseau type RSVP qui est à même de fournir les caractéristiques d'urgence et d'importances des données à transmettre. On notera que le procédé selon l'invention peut, sans sortir du cadre d'invention, s'appliquer à tout autre type de réseau et à des canaux de propagation de nature quelconque.30 REVENDICATIONS 1. Procédé d'allocation de ressources dans un réseau de communication (1) comportant plusieurs noeuds (3) adaptés à émettre et recevoir des données et un noeud central (2) adapté à allouer des ressources, caractérisé en ce qu'il comporte au moins les étapes suivantes : au moins un noeud (3) émet une ou plusieurs requêtes (Rnqt) vers le noeud central (2), chaque requête (Rnqt) étant associée à un besoin (q;) ; - le noeud central (2) attribue une durée de vie (Atqi) à chaque requête (Rngt) en fonction du besoin (q;) de la requête, et - on ordonne chaque requête (Rnqt) dans une file d'attente en fonction de la durée de vie (Atqi) et de l'instant de réception (tR) de la requête. 2. Procédé selon la revendication 1, caractérisé en ce que la durée de vie (Atqi) est attribuée à une requête (Rnqt) selon l'application associée à la requête (Rnqt) 3. Procédé selon l'une des revendications 1 à 2, caractérisé en ce que la durée de vie (Atqi) est attribuée à une requête (Rnqt) en fonction d'une qualité de service (QoS) associée à la requête (Rnqt). 25 4. Procédé selon la revendication 1, caractérisé en ce que la durée de vie (Atqi) attribuée à une requête (Rnqt) dépend du nombre de noeuds du réseau que devront traverser les données à transmettre. 5. Procédé selon l'une quelconque des revendications précédentes, 30 caractérisé en ce que l'on utilise un protocole TDMA et les ressources à allouer sont les instants de transmission. 15 20 6. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, pour des instants d'expirations égaux, on ordonne les requêtes (Rnqt) dans la file d'attente selon la qualité de service (QoS) des requêtes (Rnqt), un instant d'expiration pour une requête étant défini à partir de la durée de vie (Atqi) allouée à la requête (Rnqt) et l'instant de réception (tR) de la requête (Rnqt). 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte une étape consistant à discriminer entre les requêtes périssables et les requêtes non-périssables. 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte une étape où l'on vérifie si les requêtes (Rnqt) sont périmées, et on élimine la ou les requêtes périmées de la file d'attente. 9. Procédé selon l'une des revendications 7 à 8, caractérisé en ce que la vérification des requêtes (Rnqt) consiste à comparer l'instant d'expiration de chaque requête avec l'instant en cours et dans le cas ou l'instant d'expiration d'une requête est inférieur à l'instant en cours la requête (Rnqt) est éliminée. 20 10. Procédé selon l'une des revendications 7 à 9, caractérisé en ce qu'on alloue à chaque requête (Rnqt) une durée de vie en sortie et on compare un instant d'expiration en sortie, défini à partir du temps de vie en sortie de la requête (Rnqt), et l'instant de réception de la requête (Rnqt) avec l'instant en 25 cours et dans le cas ou l'instant d'expiration en sortie d'une requête (Rnqt) est inférieur à l'instant en cours la requête (Rnqt) est éliminé. 11. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le réseau (1) est un réseau radio. 12. Procédé selon 1une quelconque des revendications précédentes, caractérisé en ce qu'on peut régler la durée de vie (Atqi) attribuée à une requête (Rngt) en fonction de la priorité ou les contraintes temporelles associées à la requête (Rnqt). 30 13. Système d'allocation de ressources dans un réseau de communication (1) cornportant plusieurs noeuds (3) adaptés à émettre et recevoir des données et un noeud central (2) adapté à allouer des ressources, caractérisé en ce que plusieurs noeuds (3) sont équipés d'un processeur adapté à : émettre une ou plusieurs requêtes (Rnqt) vers le noeud central (3) (2), chaque requête (Rnqt) étant associée à un besoin (q;), et en ce que le noeud central est équipé d'un processeur adapté à : attribuer un temps de vie (Mo) à chaque requête (Rnqt) reçue par le noeud central (3) selon le besoin (q;) de ladite requête (Rnqt); et ordonner chaque requête (Rnqt) reçue dans une file d'attente en fonction de la durée de vie (Atg;) et de l'instant de réception (tR) de ladite requête (Rngt). 14. Système selon Ila revendication 13, caractérisé en ce que le réseau (1) est un réseau radio.