Point d'accès et nœud pour contrôler le routage dans un réseau hybride

Arrière-plan de l'invention La présente invention se rapporte au domaine du routage dans les réseaux de télécommunication hybrides, autrement appelés réseaux maillés sans fil (en anglais « wireless mesh networks, WMN »).

De tels réseaux permettent d'interfacer par l'intermédiaire de points d'accès (ou passerelles) des réseaux de télécommunication mobile ad hoc, dans lesquels des équipements mobiles appelés « nœuds » sont libres de se déplacer et de communiquer sans fil les uns avec les autres, avec un réseau d'infrastructure.

Les réseaux hybrides résolvent notamment les problèmes connus de mise à l'échelle et de performance dont souffrent les réseaux mobiles ad hoc. Par ailleurs, le réseau d'infrastructure intégré au réseau ad-hoc en renforce considérablement le contrôle et la sécurité.

Les nœuds couverts par un même point d'accès dans un réseau hybride forment un réseau ad hoc. Quand deux réseaux ad hoc se recouvrent, même partiellement, ils forment un réseau ad hoc plus large. Dans un réseau hybride, un message émis par un nœud source vers un nœud destination, peut être routé de bout en bout au sein du réseau ad hoc ou via les points d'accès.

L'invention vise plus particulièrement la recherche de la meilleure route pour acheminer un message entre un nœud source et un nœud destination dans un réseau hybride.

De nombreux efforts de recherche ont porté sur le problème de déterminer un protocole de routage efficace dans un réseau hybride.

Les solutions existantes à ce jour peuvent être classées en deux catégories. Dans les solutions de la première catégorie, chaque nœud du réseau met en œuvre ses propres algorithmes de recherche de topologie et maintient lui-même la connaissance de cette topologie. Ces solutions ne sont pas modulaires, et consomment de la puissance de calcul dans chacun des nœuds, ce qui peut être préjudiciable quand ceux-ci ont des ressources énergétiques limitées. Au surplus, le trafic total généré par

l'ensemble des nœuds pour ce contrôle peut devenir très important lorsque le nombre de nœuds augmente.

Dans la deuxième catégorie de solutions, chaque nœud du réseau informe périodiquement le point d'accès de l'état des liens qui le concerne, le point d'accès utilisant ces informations pour maintenir la connaissance de la topologie du réseau dans son intégralité. La mise à jour permanente de la topologie entière du réseau par le point d'accès nécessite un trafic de contrôle purement dédié à cet effet très important.

Or, il est légitime de considérer que tous les nœuds ne sont pas « actifs », à un instant donné, c'est-à-dire susceptible de communiquer avec un autre nœud ou avec un point d'accès. De telles solutions génèrent dont des paquets de contrôle fortement redondants en toute inutilité.

Obiet et résumé de l'invention Selon un premier aspect, l'invention concerne un procédé de traitement d'un message d'annonce diffusé, dans un réseau de télécommunications hybride, par un point d'accès auprès duquel au moins un premier nœud du réseau a pu s'enregistrer par l'envoi d'une requête d'enregistrement. Ce procédé, susceptible d'être mis en œuvre par un deuxième nœud dudit réseau, comporte :

- une étape d'envoi, par le deuxième nœud et à destination du point d'accès, d'un message de réponse au message d'annonce ;

- une première étape de vérification au cours de laquelle le deuxième nœud vérifie s'il a un statut représentatif du fait qu'il n'a pas contribué à l'acheminement d'une requête d'enregistrement, l'étape d'envoi étant effectuée uniquement en cas de succès de la première étape de vérification.

Selon un deuxième aspect, l'invention concerne un procédé de sélection d'une route entre un nœud source et un nœud destination susceptible d'être mis en œuvre par un point d'accès dans un réseau de télécommunication hybride. Ce procédé comportant :

- une étape d'enregistrement dans une table de topologie du point d'accès, pour au moins un nœud du réseau, d'un identifiant de ce nœud et d'une route entre ce nœud et le point d'accès, sur réception d'une requête d'enregistrement émise par ce nœud ;

- une étape de réception de messages émis par des nœuds du réseau en réponse à un message d'annonce diffusé par le point d'accès aux seuls noeuds ayant un statut prédéterminé, ce message reçu comportant une route entre le nœud émetteur de ce message et le point d'accès ; et - une étape de sélection d'une route parmi toutes les routes possibles entre le nœud source et le nœud destination déterminées à partir des messages de réponse reçus susmentionnés.

Conformément à l'invention, la topologie du réseau hybride est maintenue à jour par les points d'accès. Cette caractéristique permet avantageusement de centraliser les algorithmes de routage dans les points d'accès et résout les problèmes de performance et de modularité des solutions existantes de la première catégorie.

Conformément à l'invention, la mise à jour de la topologie par le point d'accès se fait sur la base de messages de contrôle envoyés uniquement par certains nœuds du réseau, ce qui limite considérablement l'encombrement du réseau pour le contrôle de la topologie par rapport aux solutions de la deuxième catégorie.

Dans un mode de réalisation, le procédé de traitement selon l'invention comporte : - une deuxième étape de vérification au cours de laquelle le deuxième nœud vérifie qu'il a un statut représentatif du fait qu'il est enregistré auprès du point d'accès ou du fait qu'il a contribué à l'acheminement de la requête d'enregistrement du au moins un premier nœud vers le point d'accès ; et, en cas de succès de ladite deuxième étape de vérification : - une étape de retransmission dudit message d'annonce vers au moins un nœud dudit réseau en tenant compte d'une profondeur de diffusion comprise dans le message d'annonce.

Dans un mode de réalisation, la table de topologie comprend des informations relatives à des nœuds appartenant à une zone active. Par "zone active" au sens de l'invention, on entend un ensemble de nœuds comprenant au moins un nœud enregistré auprès du point d'accès, des nœuds intermédiaires qui servent de relais à un nœud enregistré et des nœuds récepteurs de ce message d'annonce.

Dans un mode de réalisation, le procédé de sélection selon l'invention comporte une étape au cours de laquelle le point d'accès

enregistre dans ladite table de topologie une route extraite dudit message reçu, entre le nœud émetteur de ce message et le point d'accès.

Les routes ainsi extraites permettent au point d'accès de déduire des routes possibles entre le nœud source et le nœud destination même si elles ne passent pas par le point d'accès.

Dans un mode particulier de réalisation, le message d'annonce est diffusé par le point d'accès avec une profondeur d'un saut et relayé par les nœuds du réseau ayant un statut prédéterminé. Les messages relayés peuvent aussi être relayés avec une profondeur d'un saut. Dans un mode particulier de réalisation de l'invention, les nœuds autorisés à relayer le message d'annonce sont :

- les nœuds de statut « R », c'est-à-dire les nœuds enregistrés dans le point d'accès ; et

- les nœuds de statut « I », à savoir les nœuds intermédiaires, un nœud intermédiaire étant un nœud qui se trouve sur une route empruntée par le message d'enregistrement d'un autre nœud à destination du point d'accès.

Comme il a été dit précédemment seuls certains nœuds sont mémorisés dans la table de topologie du point d'accès. En conséquence, il se peut qu'un nœud destination n'y soit pas enregistré.

Dans ce cas, dans un mode particulier de réalisation, le procédé de sélection selon l'invention comporte une première étape de recherche du nœud destination auprès d'au moins un autre point d'accès, si le point d'accès ne connaît pas le nœud de destination. Cette première recherche utilise donc les liaisons entre points d'accès et n'encombre pas le réseau ad hoc.

Dans un mode particulier de réalisation, le procédé de sélection selon l'invention comporte, en cas d'échec de la première étape de recherche, une deuxième étape de recherche du nœud destination par un mécanisme de recherche par diffusion (en anglais "ring-based search").

Un exemple d'un tel mécanisme est mis en œuvre par le protocole de routage AODV (en anglais, Ad-hoc On-Demand Distance Vector) défini dans le document RCF 3561 ("Request for Commeπts").

Ce mécanisme est donc utilisé uniquement en dernier recours. Il est en effet connu que cet algorithme très efficace présente l'inconvénient

majeur de surcharger le réseau avec des messages de contrôle très nombreux.

L'homme du métier comprendra donc que l'invention est très avantageuse par rapport à toutes les solutions qui recourent systématiquement à l'usage du mécanisme de recherche par diffusion pour la recherche d'un nœud destination, que celui soit mis en œuvre par un point d'accès ou par les nœuds eux-mêmes.

Dans un mode préféré de réalisation, l'étape de sélection de route prend au moins en compte : - le nombre de sauts entre le nœud source et le nœud destination dans chacune des routes possibles ; ou

- le fait qu'une route possible passe ou non par le point d'accès ; ou

- une qualité de service sur chacune des routes possibles évaluée en fonction d'un type application compris dans la requête d'obtention de route.

Dans un mode particulier de réalisation, les différentes étapes du procédé de sélection et/ou du procédé de traitement d'un message d'annonce sont déterminées par des instructions de programmes d'ordinateurs. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre dans un point d'accès ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé de sélection tel que décrit ci-dessus.

Et l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre dans un nœud ou plus - généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé de traitement de message tel que décrit ci-dessus.

Ces programme peuvent utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.

L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus.

Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question.

L'invention vise également un point d'accès pouvant être utilisé dans un réseau de télécommunication hybride. Ce point d'accès comporte :

- des moyens d'enregistrement dans une table de topologie, pour au moins un nœud du réseau, d'un identifiant de ce nœud et d'une route entre le nœud et Ie point d'accès, sur réception d'une requête d'enregistrement émise par ce nœud ;

- des moyens de réception de messages émis par des nœuds du réseau en réponse à un message d'annonce diffusé par le point d'accès aux seuls nœuds ayant un statut prédéterminé, ces messages comportant une route entre ce nœud émetteur et le point d'accès ; - des moyens d'enregistrement, dans la table de topologie, de la route, en association avec un identifiant du nœud émetteur ;

- des moyens de réception d'une requête émise par le nœud source pour obtenir une route vers le nœud destination ;

- des moyens de sélection d'une route parmi toutes les routes possibles entre ledit nœud source et le nœud destination déterminées à partir des messages de réponse reçus susmentionnés ; et

- des moyens d'envoi d'un message comportant la route sélectionnée au nœud source.

L'invention vise aussi un nœud susceptible d'être utilisé dans un réseau de télécommunications hybride comportant un point d'accès auprès duquel au moins un premier nœud du réseau a pu s'enregistrer par l'envoi d'une requête d'enregistrement, ce nœud comportant :

- des moyens de réception d'un message d'annonce diffusé par le point d'accès, éventuellement relayé par un autre nœud du réseau ;

- des moyens pour vérifier si le nœud a un statut représentatif du fait qu'il n'a pas contribué à l'acheminement d'une requête d'enregistrement ; et

- des moyens d'envoi d'un message de réponse au message d'annonce à destination du point d'accès en cas de succès de la vérification.

L'invention vise aussi un réseau hybride comportant au moins un point d'accès et au moins un nœud tels que mentionnés ci-dessus.

Les avantages et caractéristiques du point d'accès, du nœud et du réseau selon l'invention sont les mêmes que ceux mentionnés ci-dessus en référence au procédé de sélection et au procédé de traitement d'un message. Ils ne seront pas rappelés ici.

Brève description des dessins

D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures :

- la figure 1 représente un point d'accès conforme à l'invention dans son environnement, dans un mode particulier de réalisation ;

- la figure 2 représente de façon schématique l'architecture matérielle d'un nœud pouvant être utilisé dans le contexte de l'invention ; - la figure 3 représente de façon schématique l'architecture matérielle d'un point d'accès conforme à l'invention, dans un mode particulier de réalisation ;

- la figure 4 représente, sous forme d'organigramme, les principales étapes mises en œuvre pour enregistrer un nœud auprès d'un point d'accès conforme à l'invention, dans un mode particulier de réalisation ;

- la figure 5 représente, sous forme d'organigramme, les principales étapes mises en œuvre pour découvrir un point d'accès et pour découvrir et maintenir à jour la topologie du réseau, dans un mode particulier de mise en œuvre de l'invention ; - la figure 6 représente, sous forme d'organigramme, les principales étapes mises en œuvre pour découvrir une route découvrir une route, dans un mode particulier de mise en œuvre de l'invention ;

- la figure 7 représente, sous forme d'organigramme, les principales étapes mises en œuvre pour sélectionner une route, dans un mode particulier de mise en œuvre de l'invention ; et

- les figures 8 à 10 présentent des données de topologie mémorisées par un point d'accès conforme à l'invention à différents stades de mise en œuvre de l'invention dans un mode particulier de réalisation.

Description détaillée d'un mode de réalisation

La figure 1 représente un point d'accès 30, dans son environnement, dans un mode particulier de réalisation de l'invention.

La référence 1 désigne un réseau hybride dans lequel peut être mis en œuvre un procédé conforme à l'invention. Ce réseau hybride 1 est constitué par un réseau d'infrastructure fixe 2 et par deux réseaux ad hoc 5 et 6.

Dans l'exemple décrit ici, le réseau d'infrastructure fixe 2 est le réseau Internet.

Les réseaux ad hoc 5 et 6 sont respectivement connectés à un point d'accès 30, 30i.

Ces points d'accès sont reliés entre eux par une liaison filaire 52.

Dans l'exemple décrit ici, le point d'accès 30 est relié à une entité 3 du réseau Internet 2 par une liaison filaire 51. Dans l'exemple décrit ici, on s'intéresse à la sélection d'une route pour acheminer des données entre un nœud source S et un nœud destination D du réseau ad hoc 5.

Dans l'exemple décrit ici, tous les nœuds du réseau hybride 1, A à U sont identiques. Ils ont l'architecture matérielle d'un ordinateur conventionnel 10 qui va maintenant être décrit en référence à la figure 2.

Un tel ordinateur comporte un processeur 11, une mémoire vive de type RAM 12, une mémoire morte de type ROM 13 et des moyens de télécommunication 14 pour communiquer avec les autres nœuds du réseau ad hoc et avec les point d'accès 30, 30i. La mémoire morte 13 comporte un programme d'ordinateur conforme à l'invention, ce programme comportant des instructions pour exécuter les étapes du procédé de traitement d'un message d'annonce conforme à l'invention dont les principales étapes sont décrites, dans un mode de réalisation en référence aux figures 4 à 6. Un état ou statut d'un nœud est défini par rapport au point d'accès. Dans le mode de réalisation décrit ici, il peut prendre trois valeurs :

- "R" ou statut "enregistré" : le nœud a effectué une phase d'enregistrement auprès du point d'accès. Cette phase d'enregistrement est décrite ultérieurement ;

- "I" ou statut "intermédiaire" le nœud a servi de relais lors d'une phase d'enregistrement d'un autre nœud ;

- "N" ou statut "nul" : dans les autres cas.

Chaque nœud comporte également une table de routage 15 dans laquelle il mémorise notamment son statut. A la mise sous tension, le statut d'un nœud est « N » (statut nul).

La figure 3 représente de façon schématique le point d'accès

30, le point d'accès 3O ₁ étant identique. Il comporte un processeur 31, une mémoire vive de type RAM 32, une mémoire morte de type ROM 33. La mémoire morte 33 comporte un programme d'ordinateur conforme à l'invention, ce programme comportant des instructions pour exécuter les étapes du procédé de sélection conforme à l'invention, dont les principales étapes seront décrites, dans un mode particulier de réalisation, en référence aux figures 4 à 7. Le point d'accès 30, 3Oi comporte également des moyens de télécommunication filaires 34 adaptés à communiquer avec un autre point d'accès, et une entité 3 du réseau Internet 2.

Le point d'accès 30, 3Oi comporte également des moyens de télécommunication sans fil 37 pour communiquer avec les nœuds du réseau ad hoc dans sa zone de couverture.

Le point d'accès 30, 3Oi comporte également une table de topologie 35 dans laquelle sont mémorisées les statuts de certains nœuds du réseau, formant une zone active et des informations nécessaires pour lui permettre d'identifier toutes les routes possibles entre deux nœuds enregistrés dans la table.

Par "zone active" au sens de l'invention, on entend un ensemble de nœuds comprenant au moins un nœud enregistré auprès du point d'accès (statut "R"), des nœuds intermédiaires (statut "I") qui servent de relais à au moins un nœud enregistré et des nœuds récepteurs d'un message d'annonce diffusé par le point d'accès. La méthode de détermination de ces derniers nœuds est détaillée par la suite.

Le point d'accès 30, 3Oi comporte également une table des connexions actives 36 dans le réseau ad hoc 5, 6.

En référence à la figure 4, nous allons maintenant décrire comment s'effectue l'enregistrement d'un nœud auprès du point d'accès 30, dans un mode particulier de réalisation de l'invention.

L'enregistrement d'un nœud fait intervenir le nœud qui souhaite s'enregistrer, le point d'accès 30 et d'autres nœuds du réseau ad hoc 5 dès lors que le nœud qui souhaite s'enregistrer se trouve à plus d'un saut du point d'accès 30.

A la figure 4 on a représenté sous formes d'organigrammes, les processus PA (étapes AlO à A14), PB (étapes BlO à B14) et PC (étapes

ClO à C24) respectivement mis en œuvre par le nœud qui souhaite s'enregistrer, par le point d'accès 30 et par les autres nœuds du réseau lors de cet enregistrement.

On suppose que le nœud qui souhaite s'enregistrer a déjà découvert le point d'accès 30. Ce mécanisme de découverte sera décrit ultérieurement en référence à la figure 5.

Au cours d'une étape AlO, le nœud qui souhaite s'enregistrer diffuse une requête d'enregistrement RREQ (Route Request), cette requête ayant pour adresse source l'adresse ID_N de ce nœud, et pour adresse de destination, celle du point d'accès 30.

Si un autre nœud reçoit, au cours d'une étape ClO, ce message RREQ, il met à jour, au cours d'une étape C12 sa table de routage 15 pour y renseigner une route entre lui et le nœud émetteur de la requête RREQ.

Puis, au cours d'un test C14, le nœud ayant reçu la requête RREQ détermine, par lecture de sa table de routage 15, s'il connaît déjà une route vers le point d'accès 30.

Si c'est le cas, le résultat du test C14 est positif, et le nœud transmet, au cours d'une étape C16, la requête RREQ au point d'accès 30 selon cette route.

Sinon le résultat du test C14 est négatif et le nœud diffuse, au cours d'une étape C18, la requête RREQ dans le réseau ad hoc 5.

Nous supposerons que le point d'accès 30 reçoit la requête RREQ au cours d'une étape BlO.

Dans ce cas, il enregistre dans sa table de topologie 35, au cours d'une étape B12 dans un enregistrement associé au nœud émetteur de la requête RREQ :

- l'identifiant ID_N correspondant à l'adresse source de la requête RREQ ;

- le premier nœud sur la route entre le point d'accès 30 et le nœud émetteur de la requête RREQ, c'est-à-dire le dernier nœud qui a transmis la requête RREQ ; et

- le statut « R » représentatif du fait que le nœud émetteur de la requête RREQ est enregistré auprès d'un point d'accès 30 et est actif au sens de ce document.

Un nœud enregistré auprès d'un point d'accès est un nœud actif au sens de ce document.

Ces informations sont respectivement enregistrées dans des colonnes « ID_N », « Suivant » et « Statut » représentées notamment à la figure 8.

Puis au cours d'une étape B14, le point d'accès 30 envoie un message RREP (Route Reply) à destination du nœud qu'il vient d'enregistrer, par l'intermédiaire du premier nœud sur la route entre le point d'accès 30 et le nœud de destination, ce message ayant pour adresse de destination l'adresse ID_N de ce nœud, et pour adresse source celle du point d'accès 30.

Si un nœud reçoit ce message RREP au cours d'une étape C20, il enregistre dans sa table de routage 15, au cours d'une étape C22, son statut « I » représentatif du fait qu'il est un nœud « intermédiaire » au

sens de ce document, c'est-à-dire qu'il a contribué à l'acheminement d'une requête d'enregistrement d'un autre nœud.

Au cours d'une étape C24, il détermine par lecture de sa table de routage 15 l'identité du nœud lui permettant d'atteindre le nœud destinataire de ce message RREP et lui transmet ce message.

Le nœud à l'origine de la requête d'enregistrement RREQ reçoit finalement le message de réponse RREP au cours d'une étape A12.

Au cours d'une étape A14 il met à jour sa table de routage 15 et y enregistre son nouveau statut « R » représentatif du fait qu'il est enregistré dans la table de topologie 35 du point d'accès 30.

En référence à la figure 5, nous allons maintenant décrire comment s'effectuent la découverte d'un point d'accès 30, 3Oi et la découverte de la topologie du réseau hybride 1, dans un mode particulier de réalisation de l'invention. A la figure 5 on a représenté sous formes d'organigrammes, les processus PD (étapes DlO à D14) et PE (étapes ElO à E14) respectivement mis en œuvre par le point d'accès 30, et par les nœuds du réseau pour effectuer ces découvertes.

Au cours d'une étape DlO, le point d'accès 30 diffuse le message d'annonce GWADV (Gateway Advertisment) avec une profondeur d'un saut (TTL=I), ce message contenant l'identifiant du point d'accès 30.

L'étape ElO du processus PE est mise en œuvre à chaque fois qu'un nœud reçoit un message.

Lorsqu'un nœud reçoit le message d'annonce GWADV, il met à jour sa table de routage 15 au cours d'une étape E12.

Puis, au cours d'un test E14, il détermine si son statut enregistré dans sa table de routage 15 est « R » (nœud enregistré), « I » (nœud intermédiaire) ou « N » (statut nul).

Si son statut est « R » ou « I », le test E14 est suivi par une étape E16 au cours de laquelle il diffuse le message d'annonce GWADV avec une profondeur d'un saut.

Puis au cours d'un test E18, le nœud détermine si son statut enregistré dans sa table de routage est « R » (nœud enregistré) ou « N » (statut nul). Un nœud de statut "N", ayant reçu le message d'annonce, est un nœud situé à un saut d'un nœud de statut "R" ou "I".

Si c'est le cas, le nœud envoie, au cours d'une étape E20, un message RREP-PA (PA : « path accumulation ») en direction du point d'accès 30, pour que celui-ci mette à jour sa table de topologie 35. On rappelle qu'un tel message permet d'accumuler une route de bout en bout entre un nœud source et un nœud destination. En pratique, tous les nœuds intermédiaires y insèrent leur propre identifiant. Dans le mode particulier de réalisation décrit ici, chacun des nœuds y insère également des informations de qualité de service (QoSjnfo) relatives au lien par lequel ils ont reçu ce message. Ces informations QoSjnfo sont utilisées pour la sélection des routes par les points d'accès comme décrit ultérieurement en référence à la figure 7.

Le message RREP-PA a pour adresse de destination celle du point d'accès 30.

Ainsi, seuls les nœuds de statut "R" enregistrés auprès du point d'accès 30 et les nœuds situés à un saut d'un nœud enregistré (statut

"N") ou d'un nœud intermédiaire (statut "I") répondent au message d'annonce GWADV. On limite ainsi les messages de contrôle échangés entre les nœuds. De plus, la connaissance d'un environnement proche des nœuds intermédiaires et des nœuds enregistrés facilite la gestion de la mobilité des nœuds.

Si un nœud reçoit le message RREP-PA au cours de l'étape générale ElO de réception des messages, il met à jour sa table de routage

15 avec la route entre le nœud source de ce message et lui-même contenue dans ce message, au cours d'une étape E22, puis il transmet ce message au cours d'une étape E24.

Le point d'accès 30 reçoit le message RREP-PA au cours d'une étape D12.

Au cours d'une étape D14, le point d'accès 30 en extrait la route entre lui-même et le nœud source émetteur de ce message et met à jour sa table de topologie 35 avec cette route (champ « Suivant »), et le statut

« R » ou « N » de cet émetteur. Les nœuds ayant répondu au message d'annonce GWADV sont actifs au sens de l'invention.

Au cours de cette même étape D14, le point d'accès enregistre dans la table de topologie 35, pour chacun des nœuds de la route comprise dans le message RREP-PA, le premier nœud permettant d'atteindre ce nœud.

Le point d'accès 30 enregistre aussi, dans une liste L de ladite table de topologie, la route extraite dudit message RREP-PA, entre le nœud émetteur de ce message et le point d'accès.

La liste L est notamment utilisée pour déterminer ultérieurement toutes les routes possibles entre le nœud source S et le nœud destination D.

Le mécanisme de découverte de point d'accès 30, 3Oi et de découverte de la topologie du réseau hybride 1 est répété périodiquement, à l'initiative de ces points d'accès par diffusion des messages d'annonce GWADV.

En référence aux figures 6 et 7, nous allons maintenant décrire comment s'effectue la sélection d'une route entre le nœud source S et le nœud destination D, dans un mode particulier de réalisation de l'invention. Ce mécanisme de découverte fait intervenir le nœud source S, le point d'accès 30 et éventuellement d'autres nœuds du réseau ou d'autres points d'accès 30i.

A la figure 6, on a représenté sous formes d'organigrammes, les processus PF (étapes FlO à F18), PG (étapes GlO à G26) et PH (étapes HlO à H22) respectivement mis en œuvre par le nœud source S, par le point d'accès 30 et par les autres nœuds du réseau dans cette découverte.

Au cours d'une étape FlO, le nœud source S émet une requête

RREQ à destination du point d'accès 30, cette requête ayant pour adresse source l'adresse du nœud source S, et pour adresse de destination, celle du point d'accès 30 et comprenant un champ QoS_champ de qualité de service et une adresse D du nœud de destination.

L'étape HlO du processus PH est mise en œuvre à chaque fois qu'un nœud reçoit un message.

Lorsqu'un nœud reçoit le message RREQ au cours de cette étape HlO, il le transmet vers le point d'accès 30 au cours d'une étape

H 12. En effet, le nœud source S s'étant normalement enregistré auprès du point d'accès 30, les nœuds intermédiaires entre le nœud source S et le point d'accès 30 connaissent déjà une route mémorisée dans leur table de routage 15 respective pour acheminer le message RREQ vers ce point d'accès 30.

Le point d'accès 30 reçoit le message RREQ au cours d'une étape GlO.

Au cours d'un test G12, il vérifie si le nœud destination D est enregistré dans sa table de topologie 35. Si c'est le cas, il sélectionne, au cours d'une étape générale G14, qui sera décrite ultérieurement en référence à la figure 7, une route entre le nœud source S et le nœud de destination D, parmi toutes les routes possibles entre ces nœuds qu'il peut déduire de la liste L de sa table de topologie 35. Une fois que cette route est sélectionnée, le point d'accès 30 enrichit sa table des connexions actives 36 au cours d'une étape G16 avec :

- les informations obtenues dans la requête RREQ : adresse de la source S, de la destination D, informations de qualité de service QoSJnfo ; et avec

- la route sélectionnée à l'étape G14 entre ces nœuds S, D.

Au cours d'une étape G18, le point d'accès 30 envoie un message RREP au nœud source S, l'adresse source de ce message RREP est l'adresse du point d'accès 30 et son adresse destination celle de l'adresse source S. Ce message RREP comporte la route entre le nœud source S et le nœud destination D et des paramètres de qualité de service QoS_param effectivement disponibles sur cette route.

Lorsqu'un nœud reçoit ce message RREP au cours de l'étape générale HlO de réception des messages, il transfère ce message vers le nœud source S au cours d'une étape H14 en utilisant sa table de routage 15.

Le nœud source S reçoit le message RREP au cours d'une étape F12. Il extrait la route sélectionnée par le point d'accès et les paramètres de qualité de service QoS_param et met à jour sa table de routage au cours d'une étape F14 à l'aide de cette route.

Comme nous l'avions dit précédemment, il se peut que le point d'accès 30 ne connaisse pas le nœud destination D. Dans ce cas le résultat du test G12 est négatif.

Dans un autre mode de réalisation particulier, le point d'accès 30 envoie un message au nœud source S pour lui indiquer que le nœud destination D est inaccessible.

Dans le mode de réalisation décrit ici, le test G12 est suivi, lorsque son résultat est négatif, par une étape G20 au cours de laquelle le point d'accès 30 recherche le nœud de destination D auprès des autres points d'accès 3Oi du réseau hybride 1. Pour cela il peut utiliser un mécanisme de recherche par diffusion ou "ring-based search" limité à ces points d'accès, par exemple par la mise en œuvre du mécanisme défini dans le document RFC 3561 ("Request For Comments") du protocole de routage AOPV (pour Ad hoc On-Demand Distance Vector). Au cours d'un test G22 le point d'accès analyse le résultat de cette première recherche. Si cette recherche est fructueuse, le test G22 est suivi par l'étape générale G14 de sélection de route déjà décrite.

En revanche, si la première recherche échoue, le test G22 est suivi par une étape G24 au cours de laquelle le point d'accès 30 initie un mécanisme de recherche par diffusion ou "ring-based search" dans le réseau ad hoc. Pour cela il diffuse un message RREQ dans lequel un indicateur s (Search) est positionné à 1. L'adresse source de ce message est l'adresse du point d'accès 30 et l'adresse de destination est l'adresse du nœud de destination D recherché. Dans le mode de réalisation décrit ici, la profondeur TTL de ce message RREQ est égale au rayon du réseau ad hoc 5. Par "rayon" du réseau ad hoc, on entend le nombre maximum de sauts entre le point d'accès et un nœud du réseau. Les mécanismes connus de l'art antérieur recherchent le nœud sur une zone correspondant au diamètre. L'invention tire ainsi avantage de la position centrale du point d'accès et limite l'encombrement du réseau ad hoc par les messages de recherche.

Lorsqu'un nœud reçoit ce message RREQ avec l'indicateur S positionné à 1 au cours de l'étape générale HlO de réception des messages, il met à jour la route par défaut vers le point d'accès 30 dans sa table de routage 15 au cours d'une étape H18. Si le nœud est destinataire de ce message, il prépare un message RREP-PA à destination du point d'accès 30, le long de la route par défaut. Au cours de cette même étape H 18, le nœud initie le mécanisme d'enregistrement précédemment décrit en référence à la figure 4 en mettant en œuvre le processus PA. Si le nœud n'est pas destinataire du message RREQ, il le diffuse.

Lorsqu'un nœud reçoit le message RREP-PA au cours de l'étape générale HlO de réception des messages, il y insère sa propre adresse au cours d'une étape H16, et le transfère vers le point d'accès 30, comme cela est décrit en référence à l'étape E22. Le point d'accès reçoit le message RREP-PA au cours d'une étape G26. Il en extrait notamment la route vers le nœud de destination D et met à jour sa table de topologie 35 comme décrit en référence à l'étape D14. Le processus PG se poursuit alors par l'étape générale G14 de sélection de route déjà mentionnée et qui va maintenant être décrite précédemment en référence à la figure 7.

Dans le mode de réalisation décrit ici, le nœud source est enregistré au préalable auprès du point d'accès.

En variante, des nœuds ayant un statut "I" ou "N", connaissant une route vers le point d'accès 30, peuvent émettre le message RREQ à destination du point d'accès sans s'enregistrer au préalable. La réception du message RREQ modifie leur statut de "I" ou "N" à "R".

La figure 7 décrit un mécanisme de sélection de route mis en œuvre par le point d'accès 30 dans un mode particulier de réalisation de l'invention. Il détaille l'étape G14. Dans le mode de réalisation décrit ici, ce mécanisme de sélection est aussi mis en œuvre quand le point d'accès détermine qu'une nouvelle route est disponible.

Au cours d'un test JlO, le point d'accès 30 détermine, à partir de sa table de topologie 35, s'il existe plusieurs routes possibles entre le nœud source S et le nœud destination D.

Si c'est le cas, le résultat du test JlO est positif et ce test est suivi par une étape J12 au cours de laquelle le point d'accès 30 calcule les paramètres QoS_param de qualité de service, à savoir par exemple des délais, des informations de bande passante, des taux de perte sur chacune des routes possibles. Ces paramètres sont calculés à partir des informations de qualité de service (QoSjnfo) reçues par le point d'accès 30 dans les messages RREP-PA.

Au cours d'une étape J 14, le point d'accès 30 vérifie si les paramètres QoS_param sont compatibles avec les exigences contenues dans le champ QoS_champ de qualité de service de la requête émise à l'étape FlO par la source S pour obtenir une route. Il élimine ainsi les

routes incompatibles avec les exigences de l'application qui utilisera la route sélectionnée par le point d'accès.

Au cours d'un test J16, le point d'accès 30 détermine si plusieurs routes sont encore envisageables. Si tel est le cas, le résultat du test J16 est positif. Ce test est alors suivi par une étape J18 au cours de laquelle le point d'accès analyse la stabilité de ces routes. A cet effet, le point d'accès 30 consulte une base d'historique du comportement de ces routes, et retient les routes les plus stables. Si le point d'accès 30 est surchargé, il peut aussi choisir une route qui ne passe pas par ce point d'accès. Une telle base d'historique peut être localisée au point d'accès 30 ou centralisée dans le réseau Internet 2 et partagée par plusieurs points d'accès.

Le point d'accès 30 peut également prendre en compte un profil de l'utilisateur du nœud source. Lorsqu'il ne reste plus qu'une route, le point d'accès la considère comme étant la route à sélectionner entre le nœud source S et le nœud destination D.

Au cours d'un test J20, le point d'accès 30 détermine si une route est déjà établie entre le nœud source S et le nœud destination D. Si ce n'est pas le cas, le résultat du test 320 est négatif et on exécute les étapes G16 de mise à jour la table 36 des connexions actives et G18 d'envoi du message RREP au nœud source S déjà décrites pour lui donner les paramètres de la route sélectionnée.

En revanche, si une route est déjà établie entre le nœud source S et le nœud destination D, il convient de déterminer, au cours d'une étape 324, s'il est nécessaire de remplacer cette route par la nouvelle route sélectionnée. Dans l'exemple de réalisation décrit, on ne change de route que si un gain significatif prédéterminé peut être obtenu en termes de qualité de service. Nous allons maintenant décrire comment la route est établie entre le nœud source S et le nœud destination D.

Après avoir extrait la route sélectionnée vers le nœud destination D (étape F14), le nœud source S prépare, au cours d'une étape F16, un message RREQ dont l'adresse source est l'adresse du nœud source S et l'adresse de destination celle du nœud destination D. Ce

message contient la route sélectionnée de bout en bout et un indicateur RE (Route Establishment) positionné à 1.

Le nœud source envoie ce message au cours de la même étape F16 le long de la route sélectionnée. Lorsqu'un nœud reçoit ce message RREQ avec l'indicateur RE positionné à 1 au cours de l'étape générale HlO de réception des messages, deux cas se présentent, ces deux cas étant traités au cours d'une étape H20.

Si le nœud qui reçoit ce message est le nœud destination D, il y répond en envoyant au nœud source S par un message RREP dans lequel l'adresse source est l'adresse du nœud destination D et l'adresse de destination celle du nœud source S, l'indicateur RE étant positionné à 1.

Si le nœud qui reçoit le message RREQ n'est pas le nœud destination D, il met à jour sa table de routage 15 en fonction de la route de bout en bout contenue dans le message RREQ. Puis il transmet le message RREQ vers le nœud suivant de la route sélectionnée pour qu'il soit acheminé vers le nœud destination D.

Lorsqu'un nœud reçoit le message RREP avec l'indicateur RE positionné à 1 au cours de l'étape générale HlO de réception des messages, il met à jour sa table de routage 15 au cours d'une étape H22, puis il transfère ce message en consultant sa table de routage à destination du nœud source S.

Le nœud source S reçoit finalement le message RREP avec l'indicateur RE positionné à 1 au cours d'une étape F18. II considère alors que la route sélectionnée est établie et il peut commencer à émettre des données sur cette route.

Le nœud source S peut également adapter les paramètres de l'application en fonction des paramètres de qualité de service QoS_param reçus du point d'accès 30 à l'étape F14. En référence aux figures 8 à 10, nous allons maintenant décrire l'état des tables de topologie 35 du point d'accès 30 à différents stades du procédé de sélection selon l'invention dans un exemple particulier.

A la figure 8, on a représenté sous forme de flèches, des messages échangés au cours de l'enregistrement des nœuds source S et destination D auprès du point d'accès 30 dans le réseau hybride de la figure 1.

Tout d'abord, le nœud source S diffuse un message RREQ 1 (étape AlO). Le point d'accès 30 enregistre le statut « R » du nœud source S dans sa table de topologie 35. Etant donné que le nœud source S est à un saut du point d'accès 30, l'identifiant du nœud S est enregistré dans la colonne « Suivant » de cette table. Le point d'accès 30 répond au message RREQ par l'envoi d'un message RREP 2 (étape B14).

Nous supposerons en parallèle que le nœud destination D envoie également un message RREQ 3, ce message étant relayé par le nœud J (message RREQ 4), puis par le nœud O (message RREQ 5) jusqu'au point d'accès 30.

Le point d'accès 30 enregistre le statut « R » du nœud D dans sa table de topologie 35 et l'identifiant du nœud « O » dans la colonne

« Suivant ». Puis le point d'accès 30 répond au message RREQ 5 par l'envoi d'un message RREP 6 relayé par le nœud O (message RREP 7) puis par le nœud J (message RREP 8) jusqu'au nœud destination D.

Sur réception du message RREQ 5 (respectivement 6), le nœud O (respectivement J) enregistre son statut « I » de nœud intermédiaire dans sa table de routage 15.

Et sur réception du message RREQ 2 (respectivement 8), le nœud S (respectivement D) enregistre son statut « R » de nœud enregistré dans sa table de routage 15.

Dans l'exemple décrit ici, la table de topologie 35 comporte une colonne "valide" représentative de la validité d'une entrée dans cette table. La table de topologie doit en effet être rafraîchie régulièrement pour refléter la topologie réelle du réseau, les nœuds étant susceptibles de se déplacer et/ou de quitter le réseau. Si une information n'est pas rafraîchie pendant une durée prédéterminée, elle devient obsolète et son état change dans la colonne "valide".

A la figure 9, on a représenté des messages échangés au cours d'une phase de découverte de la topologie du réseau hybride 1.

Les messages 1, 2, 3, 4, 9, 10, 11, 12 et 13 sont des messages d'annonce GWADV diffusés par le point d'accès 30 avec une profondeur d'un saut et relayés par les nœuds S, O et J qui ont un statut « R » ou « I » également avec une profondeur d'un saut. Les messages 7, 5, 6, 8, 15, 16 et 14 sont des messages de type RREP-PA en réponse aux messages GWADV précités. Le message 17

correspond également à des messages RREP-PA correspondant aux messages 14, 15 et 16 retransmis par le nœud J en y adjoignant son identité. Le message 18 correspond à ces messages retransmis par le nœud O en y adjoignant son identité.

Dans l'exemple décrit ici, la table de topologie 35 comporte une colonne "valide" représentative de la validité d'une entrée dans cette table. La table de topologie doit en effet être rafraîchie régulièrement pour refléter la topologie réelle du réseau, les nœuds étant susceptibles de se déplacer et/ou de quitter le réseau. Si une information n'est pas rafraîchie pendant une durée prédéterminée, elle devient obsolète et son état change dans la colonne "valide".

La table de topologie 35 du point d'accès 30 mémorise l'état « N », « R » ou « I » des nœuds connus de ce point d'accès et dans la colonne « Suivant » le premier nœud dans chacune des routes connues vers ces nœuds.

La figure 10 illustre un mécanisme de sélection de route conforme à l'invention, entre le nœud source S et le nœud destination D.

Les routes possibles entre les nœuds S et D pouvant être déduites de la table de topologie 35 sont :

- la route 1 : S-30-O-J-D ; et

- la route 2 : S-I-J-D ; et

- la route 3 : S-I-30-O-J-D.

Parmi ces routes, seule la route 2 ne passe pas par le point d'accès 30.

Le point d'accès 30 calcule des paramètres de qualité de service QoS_param pour chacune des routes 1 à 3 et obtient le résultat suivant :

Le point d'accès détermine la ou les route(s) qui présentent les meilleures caractéristiques au vu des exigences de qualité de service requises pour l'application annoncée par le nœud source S dans sa requête.

On suppose que l'application est de type voix et que le paramètre de délai est très important. Le point d'accès 30 rejette la route 3 pour qui présente un délai excessif de 250 ms.

Puis, le point d'accès 30 consulte la base d'historique du comportement des routes 1 et 2 et y apprend que ces routes sont stables.

Etant donné que la route 1 passe par le point d'accès 30 et que celui-ci est chargé, il donne la priorité à la route 2.

Le point d'accès 30 met à jour sa table des connexions actives 36 avec les paramètres de la route 2. La route sélectionnée 2 est envoyée au nœud S dans un message RREP, ce message contenant les paramètres QoS_param de qualité de service de la route 2.

Sur réception de ce message le nœud S adapte les paramètres de qualité de service de l'application voix en choisissant un codeur de voix efficace au débit de 100 kbps.

Dans le mode de réalisation qui vient d'être décrit, le programme d'ordinateur conforme à l'invention, mémorisé dans la mémoire morte 33 des points d'accès 30, 3Oi comporte des instructions pour mettre en œuvre : - le processus PB lors de l'enregistrement d'un nœud ;

- le processus PD pour la découverte de ces points d'accès et de la topologie du réseau hybride ;

- le processus PG et l'algorithme de la figure 7 pour la sélection d'une route. Dans le mode de réalisation qui vient d'être décrit, le programme d'ordinateur conforme à l'invention, mémorisé dans la mémoire morte 13 des noeuds 10 comporte des instructions pour mettre en œuvre :

- le processus PA lors de l'enregistrement d'un nœud ; - le processus PE pour la découverte de ces points d'accès et de la topologie du réseau hybride.