Brevet FR2924242A1 — publié le 20090529

PROCEDE DE RESERVATION AVEC GARANTIE DE LATENCE ET DE DEBIT DANS UN RESEAU A ALLOCATION DYNAMIQUE DE CRENEAUX TEMPORELS L'invention concerne les réseaux radio ad hoc à accès temporel multiple ou TDMA (Time Division Multiple Access). Elle vise plus particulièrement la capacité de réservation de ressources incluant les contraintes de débit et de latence bout en bout, l'une ou l'autre de ces contraintes pouvant être prépondérante. Un réseau ad hoc est défini comme un réseau dans lequel les noeuds le constituant sont mobiles, c'est-à-dire que le nombre de noeuds dans le réseau est susceptible d'évoluer dans le temps. Elle s'applique aussi dans des systèmes multi-canaux à accès temporel et fréquentiel multiple ou � TDMA � acronyme anglo-saxon pour � Time and Frequency Division Multiple Access �, les réseaux radio utilisant une modulation orthogonale en fréquence OFDMA (Orthogonal Frequency Division Multiple Access) et dans tout autre système, qui utilise un schéma d'allocation dynamique à la place d'un schéma d'allocation fixe. Pour mémoire, dans la description, les messages el objets suivants du protocole RSVP sont utilisés : L'objet Tspec du message PATH, décrit le profil de trafic de l'application, L'objet Adspec décrit, entre autres, les caractéristiques du chemin et en particulier la largeur de bande maximum disponible sur le chemin, L'objet Rspec du message RESV de réservation contient la largeur de bande à réserver pour le flux de données. L'émetteur envoie un message PATH à un destinataire vers lequel doivent être transmises des données, le destinataire ou récepteur répond en émettant un message de réservation RESV contenant la largeur de bande à réserver pour les routeurs par lesquels sont relayés les messages ou paquets de données. Les réseaux radio TDMA utilisent généralement des allocations statiques. L'allocation est, soit totalement fixée (trame cyclique avec un slot par noeud), soit définie à l'avance pour une configuration donnée. Les nouveaux systèmes radio commencent à prendre en compte la qualité de service, mais ils ne permettent pas encore de supporter la réservation globale de ressources avec garantie de service de bout en bout en débit et latence. Par exemple, ils ne supportent pas les protocoles de garantie de service sur IP (Internet Protocol), tel que le protocole de réservation de ressources � Reservation Protocol services � plus connu sous l'abréviation RSVP. En ce qui concerne la réservation de ressources, les systèmes de radio actuels et connus du Demandeur à accès temporels multiples tel que le TDMA (abréviation anglo-saxonne de Time Division Multiple Access) ne peuvent garantir à la fois un débit minimal et une latence maximale de bout en bout. Un procédé récent décrit dans la demande de brevet FF: 06 11279 déposée par le Demandeur et intitulée � Procédé de réservation et d'allocation dynamique de créneaux temporels dans un réseau avec garantie de service � permet d'appliquer le protocole RSVP à un réseau TDMA avec les restrictions d'implémentation suivantes : des paquets de contrôle d'accès au média MAC (Medium Access Control) de taille fixe pour les sessions et une réservation adaptée aux applications à contraintes de latence prépondérante vis-à-vis des contraintes de débit. En effet, ce procédé ne permet pas d'optimiser la consommation de ressources et s'avère peu économe, tout particulièrement pour les applications à contraintes de débit prépondérantes. L'invention concerne un procédé de niveau contrôle d'accès au milieu MAC permettant l'allocation dynamique des créneaux temporels de ressources radio, plus connu sous l'acronyme anglo-saxon slot, avec des paquets de session ou paquets réservés pour une session dans une application, ayant une taille variable et une garantie de service, utilisables aussi bien dans des applications demandant le respect de contrainte de latence prépondérante et/ou de contrainte de débit prépondérante. Deux types de trafic sont distingués : le trafic élastique et le trafic de session. Le trafic de session correspond, par exemple, à des flux multimédias continus (voix et vidéo) et des flux de données temps-réel pour lesquels une garantie de service forte (débit et latence) est souhaitée. Le trafic élastique correspond, par exemple, à un échange de fichier. La présente invention s'appuie notamment sur l'invention décrite dans la demande de brevet FR 06 11279 précitée qui permet de réaliser des allocations dynamiques de slots de session de manière locale, c'est-à- dire sans recours à une gestion centralisée en fonctionnement normal. Le procédé décrit dans cet art antérieur repose, sur une attribution explicite des � slots � de sessions à un ou plusieurs noeuds et sur une notion de réservation de ces � slots �. Un � slot � attribué à un noeud peut être librement réservé par ce noeud pour satisfaire une requête de réservation de ressource. Vu d'un noeud donné, l'ensemble des � slots � de session non réservés, forme un groupe ou pool de ressources dans lequel le noeud peut potentiellement puiser. Dans le cas d'une application à contrainte de latence prépondérante, le procédé décrit dans la demande de brevet FR 06 11279 permet de décliner une réservation globale de bout en bout à garantie de latence, de type RSVP en mode gestion de latence plus connu sous l'abréviation anglo-saxonne OPWA pour � One Pass With Advertising �, au niveau de la couche MAC lorsqu'un slot est composé d'un nombre NPS de paquets MAC de taille fixe. Dans ce cas les paramètres C et D du message Adspec ont pour valeur : C = BR.Ts /NPS = taille d'un paquet MAC D = temps de transmission additionnel Avec les paramètres MAC suivants (en partie précédemment définis) : 30 BR : débit du canal TDMA, N : nombre de noeuds du réseau, K : nombre de slots physiques pour un noeud, NPS : nombre de paquets MAC par slot physique H : nombre de stols physiques empruntés par le noeud considéré, Ts : durée d'un slot physique m : nombre de paquets MAC réservés La requête RSVP est alors déclinée à la couche MAC de la façon suivante: Délai de transmission maximal requis : i = C/R - Débit minimal requis :R = r La présente invention, utilise une nouvelle approche qui comporte une réservation des paquets de session de taille variable, la taille d'un paquet de session étant défini notamment par la taille maximum d'un paquet de l'application, augmenté des données d'encapsulation de niveau MAC tel que l'en-tête, ainsi que la gestion explicite de délai d'accès radio au niveau du protocole de réservation. L'objet de l'invention concerne un procédé réservation de ressources avec garantie de service en débit minimum Dmin et en temps d'accès maximum Amax au niveau des n noeuds traversés d'un réseau radio utilisant des créneaux temporels ou slots Di associée chacun à un débit élémentaire Deli pour émettre et transmettre des données, un noeud du réseau comprenant une couche protocolaire et une couche accès au réseau MAC caractérisée en ce qu'il comporte au moins les étapes suivantes : pour un noeud donné, la couche protocolaire dudit noeud émet une requête 25 de réservation vers la couche MAC dudit noeud, le noeud source émetteur des données, introduit au niveau du format des messages PATH et RESV du protocole RSVP : un champ Ts correspondant à la durée maximale du créneau temporel observé sur le chemin courant dans la requête de réservation Adspec 30 du message PATH transmise de la source vers un destinataire, un champ n sur le nombre de noeuds radio traversés dans l'objet Adspec du message PATH, un champ de délai maximum d'attente du créneau temporel dans l'objet Rspec du message RESV correspondant à la réponse à la requête de réservation PATH émis par le destinataire vers le noeud source, la couche MAC réserve le nombre de créneaux temporels Di nécessaires pour satisfaire la garantie de service inscrite dans la requête de réservation. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description qui suit d'un exemple donné à titre illustratif et nullement limitatif annexé des figures qui représentent : • La figure 1, le principe de la réservation de ressources, • Les figures 2A et 2B, un format de trame et un créneau temporel dans le cas d'une application monosource TDMA, et • La figure 3, les échanges entre les couches IP et MAC TDMA, pour l'exemple donné. Afin de mieux faire comprendre le principe mis en oeuvre dans le procédé selon l'invention, la description est donnée à titre illustratif et nullement limitatif, pour un réseau radio ad hoc TDMA dans lequel tous les noeuds sont autonomes et peuvent jouer un même rôle. Un noeud 1 jouera le rôle de la source à un instant donné, un deuxième noeud 2, le destinataire du message ou des données et plusieurs noeuds intermédiaires 3i Pour cela, les noeuds sont équipés chacun d'un processeur Pi adapté à mettre en oeuvre les étapes du procédé selon l'invention. Ils sont aussi pourvus de moyens radio, émetteur et récepteur Ei, Ri, permettant de transmettre les messages vers d'autres noeuds et de recevoir des messages en provenance de ces autres noeuds. Ces équipements sont connus de l'Homme du métier et ne seront pas détaillés. Quelques rappels sont donnés pour les terminologies utilisées et le contexte de l'invention en préambule à l'exposé du procédé et du système selon l'invention. Terminologie L'architecture d'une trame radio est composée de 4 éléments en couche dans lesquels vont être véhiculées les données utiles, une unité de données utiles pouvant être un paquet de l'application, par exemple un paquet IP: Ressource MAC élémentaire : paquet MAC (paquet d'encapsulation au niveau MAC d'un paquet d'application) Créneau temporel : plus connu sous le terme ango-saxon � slot � 10 Trame de base : BF Trame : F Ces différents éléments sont détaillés ci-après. Paquet MAC Le paquet MAC est une structure de donnée élémentaire au niveau MAC. Il 15 est de taille variable. Pour une session donnée, sa taille est fixée et est déterminée par la taille maximum d'un paquet de l'application. Créneau temporel � slot �, trame de base et trame La trame de base et les � slots � sont illustrés sur les figures 2A et 2B Cn : slot de contrôle pour le noeud n 20 Di : slot de la trame de base (autre que le slot de contrôle) Ts : durée du slot K : nombre de slots composant la trame de base TBF : durée de la trame de base avec TBF=K*Ts Chaque trame de base contient K slots. Le premier slot Cno dans chaque 25 trame de base est appelé � slot de contrôle � C'est un � slot fixe �alloué de façon permanente au noeud n. Les slots, peuvent être divisés en trois classes : o Les slots de contrôle Cni utilisés pour transmettre la signalisation de niveau MAC (paquets de signalisation nécessaires aux 30 fonctionnement des services du niveau MAC tels que la découverte de voisins et la synchronisation trame). Ces services et leur mise en oeuvre sont connus de l'Homme du métier et ne seront pas redétaillés. o Les slots � élastiques � utilisés pour transmettre les données élastiques : en général un sous-ensemble K de Di slots (où i = 1...K- 1) sont alloués statistiquement à des noeuds, afin de transmettre des données élastiques. Ainsi, Dij, (où j= 1...P) slots sont réservés pour la transmission de données élastiques (chaque noeud disposant ainsi de P slots régulièrement répartis dans la trame). Là aussi, le terme � élastique � est un terme usuellement connu par un Homme du métier et désigne sans ambiguïté des données. o Les slots de � session � utilisés pour transmettre des paquets de session. Ces slots peuvent supporter des données élastiques. Ils sont réservés pour une session donnée. Si l'on décompte le slot de contrôle Cni et les slots élastiques Dij, les N.(K-1-P) slots restants dans la trame globale constituent des slots de session qui sont allouables dynamiquement de façon à transmettre les paquets de session. Les slots de session non attribués sont regroupés dans un ensemble ou pool et sont partagés entre tous les noeuds du réseau. C'est-à-dire que tout noeud ayant besoin de satisfaire à une qualité de service requise peut utiliser un ou plusieurs slots de l'ensemble ou pool. Un slot � Di �(où i = 1....K-1) de la trame globale peut être attribué de façon permanente à un noeud (slot élastique), de façon provisoire (slot de session alloué à un noeud ou à plusieurs noeuds en cas de réutilisation spatiale), ou faire partie du pool des slots de session disponibles. II y a autant de trames de base que de noeuds dans le réseau. La trame F est composée de l'ensemble des trames de base. Si le réseau est formé de N noeuds, la structure de trame F est composée de N trames de base BF. La durée TF de la trame a pour valeur TF =N*TBF=N*K*Ts. Requête de réservation de ressource et allocation des slots de session Le � pool � des slots de sessions est composé au maximum de N*(K-1-P) slots. Chaque noeud peut potentiellement utiliser tout slot de session du pool, alors que le slot de contrôle et les slots élastiques sont définitivement alloués à un noeud. En présence d'une nouvelle session, la couche MAC 5i d'un noeud 3i (figure 3) reçoit une requête Res(Dmin, Amax) de réservation de ressource (flèche en pointillé sur la figure) assortie d'une contrainte de débit minimal Dmin et d'une contrainte de délai d'accès au slot Di maximal Amax. La requête de réservation de ressource est émise à partir de la couche protocolaire, dans l'exemple, le protocole IP (figure 3). Chaque slot Di est caractérisé par un débit élémentaire associé Deli. Un noeud Ni peut ainsi évaluer le nombre de slots Di dont il a besoin pour satisfaire la requête de réservation en terme de débit Drnin en se basant sur le débit élémentaire Deli offert par un slot Di. C'est la couche d'accès au milieu MAC qui réalise l'allocation effective des ressources correspondant à une requête de réservation de ressource pour une session. Pour un noeud donné, cette couche MAC choisit les slots de sessions Di de la trame F nécessaires pour satisfaire la requête de réservation de ressource et ensuite, la couche MAC démarre des procédures propres de négociation pour réserver les slots appartenant au pool. La couche MAC démarre ses procédures selon un principe divulgué dans la demande de brevet du Demandeur FR 06 11 279. Elle réserve ensuite dans les slots alloués, l'espace nécessaire aux paquets MAC, c'est-à-dire que le procédé réserve un espace correspondant à un nombre de paquets MAC, un slot pouvant supporter plusieurs paquets MAC. La taille d'un paquet MAC est déterminée par la taille maximale d'un paquet de l'application supportée par la session, la session étant ouverte au profit d'une application. La taille maximale est précisée dans l'objet Tspec du message Path. Plusieurs contraintes sont prises en compte au niveau de l'algorithme d'allocation des slots et des paquets MAC : o Les ressources allouées doivent être compatibles avec les exigences de débit minimal Dmin spécifiées dans la requête de réservation, o Le délai d'accès maximal au slot Amax doit être compatible avec le délai maximum imposé dans la requête de réservation. Déclinaison d'une réservation de ressource globale, de type RSVP, au niveau de la couche MAC De façon à supporter la requête de réservation de ressource au niveau MAC, deux paramètres sont introduits dans la requête MAC: T : le délai maximum requis pour accéder à un slot, - R : le débit minimal requis Ces deux paramètres sont utilisés dans l'algorithme d'allocation de ressources, de façon à garantir le respect de la requête de réservation avec garantie de service. Dans le cas d'un TDMA périodique, le message Resv pour la requête de ressource RSVP se traduit dans la couche MAC par une réservation en termes de nombre de paquets MAC. Les paramètres RSVP sont décrits selon les spécifications RFC de l'IETF connues de l'Homme du métier et ne seront donc pas explicitées dans la présente demande de brevet. Par exemple, les paramètres utilisés pour décrire l'enveloppe du trafic selon le modèle de sceau à jeton sont, selon la recommandation � token bucket � RFC 2212 disponible sur le lien internet http://www.faqs.org/rfcs/rfc2212.html. - p = débit crête (� peak rate �) (octets/sec) - b = capacité du baquet (� bucket depth �) (octets) r = débit du sceau à jeton (� token bucket rate �) (octets/sec) 25 m = granularité minimum (� minimum policed unit >>) (octets) - M = taille maximum des paquets de donnée de l'application (� maximum datagram size �) (octets). Les délais de transmission pour chaque noeud Ni sont décrits par les deux paramètres suivants : 30 - C; = facteur dépendant du débit (� rate dependent factor �) (octets) D; = terme indépendant du débit (� rate independent term �) (sec) Ainsi, la borne du délai de transmission d'un paquet à un débit minimal R pour le noeud Ni est : Ti = C;/R + D; Dans le cas d'un protocole TDMA avec des slots totalement périodiques au niveau de chaque noeud le procédé de calcul de RSVP peut être utilisé en établissant une correspondance rigoureuse entre les paramètres MAC et les paramètres RSVP. Les relations mathématiques entre les paramètres C; et D; du champ correspondant au message du chemin que vont emprunter les données pour le protocole RSVP AdSpec (du message PATH du protocole RSVP) et des paramètres du niveau MAC décrits précédemment sont alors les suivantes : -C; : taille d'un paquet MAC (en octets) - D; : délai additionnel éventuel lié à la gestion des slots ou au traitement et au transit interne d'un paquet MAC. Pour des noeuds identiques, les paramètres sont indépendants du noeud et n'ont plus besoin d'être indicés. Notons que la relation pour le paramètre Ci ou C n'est rigoureusement valide que si l'allocation conduit à une répartition temporelle sensiblement uniforme des slots physiques de chaque noeud à l'intérieur de la trame globale et si les paquets MAC d'une même session sont répartis sur des slots physiques distincts. Le procédé considère des paquets MAC de taille variable. Pour une session donnée, toujours à contrainte de latence prépondérante, la taille des paquets MAC réservés sera fixée à la valeur M de la taille maximale des paquets de l'application supportée. Dans ce cas, lorsque les slots sont décodés de façon globale, les paramètres du message de réservation de ressource � Adspec � C et D correspondant aux paramètres respectifs taille d'un paquet et délai additionnel éventuel lié à la gestion des slots ou au traitement et au transit interne d'un paquet MAC ont alors pour valeur : C = M taille maximale des paquets D = Ts + Do Avec Do temps de transmission additionnel éventuel. Le débit consommé au niveau MAC pour l'encapsulation des paquets n'a pas été pris en compte dans un souci de simplification. La prise en compte de cette encapsulation revient à considérer R comme le débit utile pour l'application. En considérant maintenant le cas général d'une session à double contrainte de latence et de débit, sans supposer que la contrainte de latence est prépondérante. La déclinaison de � RSVP OPWA �, basée sur une équivalence entre latence et débit, devient inadaptée pour les applications à contrainte de débit prépondérante, pour lesquelles elle introduit des contraintes excessives de délai d'accès maximal au slot. En effet, par exemple, une requête RSVP à contrainte de latence inexistante devrait être déclinée à la couche MAC de la façon suivante : Délai de transmission maximal requis : T = infini - Débit minimal requis : R = r Pour traiter convenablement la réservation de ressource à garantie de débit et de latence pour des applications pour lesquelles la contrainte prépondérante n'est pas connue a priori, ni en l'occurrence si la contrainte de latence est faible, le procédé doit pouvoir gérer séparément les caractéristiques de latence et de débit. II est alors possible de considérer une extension du mode OPWA du protocole RSVP en ajoutant les champs suivants : un champs Ts correspondant à la durée slot dans l'objet AdSpec du message de réservation de ressources, - un champ n sur le nombre de noeud radio traversés dans l'objet AdSpec du message de réservation de ressources, un champ i de délai maximum d'attente du slot dans l'objet Rspec du message de réponse au message de réservation de ressources Resv. 20 Considérant la latence maximale de bout en bout 8, et le délai maximum d'attente t du slot au niveau de chaque noeud, les relations mathématiques suivantes sont établies : Dans le cas où le débit garanti est inférieur au débit crête R Max m Min R Où la maximisation de m est considérée prioritairement à la minimisation du débit R sous les contraintes suivantes : (0, T) Rr R Ç R. R M z+Ts z = m.Ts Où Rmax est le débit maximum admissible et 8max la contrainte de latence maximum de bout en bout.5 La solution pour l'optimum (R, m') s'écrit : si Rmax REVENDICATIONS 1 ù Procédé de réservation de ressources avec garantie de service en débit minimum Dmin et en temps d'accès maximum Amax au niveau des N noeuds d'un réseau radio utilisant des créneaux temporels Di associée chacun à un débit élémentaire Deli pour émettre et transmettre des données, un noeud du réseau comprenant une couche protocolaire et une couche accès au réseau MAC caractérisé en ce qu'il comporte au moins les étapes suivantes : pour un noeud donné (3i), la couche protocolaire (4i) dudit noeud émet une requête de réservation vers la couche MAC (5i) dudit noeud, le noeud source (1) émetteur des données, introduit au niveau du format des messages Path et Resv du protocole RSVP : un champ Ts correspondant à la durée maximale du créneau temporel observé sur le chemin courant dans la requête de réservation Adspec du message Path, transmise du noeud source (1) vers un destinataire (2), un champ n sur le nombre de noeuds radio traversés dans l'objet du message Path, un champ t de délai maximum d'attente du créneau temporel dans l'objet Rspec du message Resv correspondant à la réponse à la requête de réservation émise par le destinataire vers le noeud source (1), la couche MAC (5i) dudit noeud (3i) réserve le nombre de créneaux temporels Di nécessaires pour satisfaire la garantie de service inscrite dans 25 la requête de réservation. 2 ù Procédé de réservation selon la revendication 1 caractérisé en ce qu'elle met en oeuvre une méthode d'allocation dynamique de créneaux temporels pour les sessions, puis une réservation des paquets MAC pour les sessions 30 sur les slots réservés en adaptant dynamiquement la taille des paquets MAC au besoin de l'application.3 - Procédé selon la revendication 1 caractérisé en ce que la requête de réservation RSVP est alors déclinée à la couche MAC de la façon suivante : - Délai de transmission maximal requis : i' = m'.Ts - Débit minimal requis : R' Où Ts correspond à la durée d'un slot et m' le nombre de paquets réservés. 4 û Procédé selon l'une des revendications 1 à 3 caractérisé en ce que le réseau est un réseau radio ad hoc, une trame radio étant composée de quatre éléments en couche: une ressource MAC élémentaire, un créneau temporel ou � slot �, une trame de base BF, une trame F, une trame comprenant un slot de contrôle alloué à un noeud donné transmettant la signalisation de niveau MAC, plusieurs créneaux temporels destinés à transmettre des données élastiques ou des paquets de session. 5 û Procédé selon l'une des revendications 1 à 4 caractérisé en ce qu'il utilise un TDMA périodique au niveau de chaque noeud. 6 û Procédé de réservation globale selon les revendications 1 et 2 20 caractérisé en ce qu'il est utilisé pour modifier le format des messages utilisés dans le mode OPWA. 7 û Procédé selon l'une des revendications 1 à 6 caractérisé en ce qu'il utilise un protocole IP. 25 8 û Réseau constitué de plusieurs noeuds, un noeud source (1), un noeud destinataire (2) et un ou plusieurs noeuds intermédiaires (3i), le noeud source comprenant des moyens d'émission, Ei, pour émettre une requête en réservation de ressources, le noeud destinataire ayant des moyens pour 30 recevoir cette requête et émettre à son tour un message de réservation de chemin, les noeuds utilisant des créneaux temporels pour émettre et 5transmettre des données caractérisé en ce que chaque noeud intermédiaire comprend une couche MAC et une couche protocolaire, et des moyens permettant la mise en oeuvre du procédé selon l'une des revendications 1 à 6. 9 ù Réseau selon la revendication 8 caractérisé en ce que le réseau est un réseau ad hoc.