Brevet FR2899416A1 — publié le 20071005

Arrière-plan de l'invention Le domaine de l'invention est celui du routage dans un réseau de télécommunication. L'invention s'applique de façon privilégiée, mais non limitative, dans les réseaux de télécommunication de type ad hoc. De façon connue, ces réseaux sont constitués de noeuds mobiles et/ou fixes ayant la propriété de constituer automatiquement et dynamiquement un réseau capable d'acheminer des paquets d'un noeud quelconque du réseau à un autre dès lors qu'une communication radio peut être établie entre un noeud et ses voisins. Les paquets sont transmis directement entre le noeud source et le noeud destinataire si ce destinataire est dans la zone de connectivité du noeud source ou via des noeuds intermédiaires voisins assurant le rôle de routeurs si le noeud destinataire est hors de portée d'une source. Les noeuds sont donc responsables de l'établissement et du maintien de la connectivité du réseau d'une manière continue. Ceci est réalisé par l'utilisation de protocoles de routage ad hoc. D'une façon générale, il existe deux grandes familles de protocoles de routage, à savoir les protocoles proactifs et réactifs. L'invention concerne un protocole hybride, c'est-à-dire faisant l'usage de ces deux techniques. Dans un protocole de routage proactif, un mécanisme d'échange périodique de messages de contrôle est mis en place afin que chaque noeud puisse construire de manière distribuée la topologie du réseau. Cela se fait par la diffusion de messages de contrôle ayant pour but d'informer l'ensemble des noeuds de l'évolution de la topologie du e-. Chaque noe iodiquemefl* jour sa abie ,outage 'ors s de con proac le très bonne nl)OrOgIP du res H une spOnihillH routes. Dans un protocole de routage proactif, les routes sont généralement calculées selon un algorithme du plus court chemin utilisant 22899416 2 une métrique définie à partir de contraintes prédéterminées, par exemple nombre de sauts, contrainte de qualité de service (QOS pour Quality Of Service en anglais),... En conséquence, ces protocoles de routage proactifs sont mal 5 adaptés lorsque ces contraintes varient, puisque les routes pré-calculées l'ont été sur la base d'hypothèses devenues erronées. Contrairement à une approche proactive, dans un protocole de routage réactif un noeud source ne calcule les routes vers un noeud destinataire qu'à la demande d'une application qui souhaite envoyer un 10 paquet à ce noeud destinataire. Ce calcul de route se fait par la diffusion d'une requête dans tout le réseau. La réponse à cette requête de diffusion permet à la source d'obtenir les informations topologiques relatives à cette route. Dans un protocole réactif, les routes sont ainsi créées à la 15 demande. De ce fait, ces protocoles de routage sont bien adaptés aux réseaux dans lesquels les contraintes sont susceptibles de varier dans le temps. En revanche, les protocoles réactifs présentent un inconvénient majeur en ce qu'ils introduisent un coût élevé d'inondation du réseau lors 20 de la découverte des routes, et ce contrairement aux protocoles de routage proactifs qui eux maintiennent une visibilité sur la topologie du réseau. Objet et résumé de l'invention 25 D'une façon générale, l'invention vise un nouveau procédé de routage adapté aux réseaux dans lesquels les contraintes prises en compte pour le calcul des routes sont susceptibles de varier dans le temps. Plus précisément, l'invention concerne un procédé d'iden- 30 tific:tIon i'au moins une route satisfaiTi-i - au moins L preulère coi entre un na-ri source et un na n r . ?.au de idmmunications Ce procédé COrr r)(:ii..- 1. emière étape de re( ie cette route en utilisant une table de routage maintenue à jour par mise en 35 oeuvre d'un protocole de routage proactif. Ce procédé comporte, en cas d'échec de la première étape de recherche : -une étape de sélection d'un nombre prédéterminé de routes potentielles à partir d'une table de topologie maintenue à jour par le protocole de 5 routage proactif ; et - une deuxième étape de recherche d'au moins une route parmi les routes potentielles. Corrélativement, l'invention concerne un dispositif d'identification d'au moins une route satisfaisant au moins une première 10 contrainte entre un noeud source et un noeud destinataire dans un réseau de télécommunications. Ce dispositif comporte : - des moyens de mise en oeuvre d'un protocole de routage proactif apte à établir et maintenir une table de routage et une table de topologie ; 15 - des premiers moyens de recherche d'au moins une route en utilisant la table de routage ; - des moyens de sélection d'un nombre prédéterminé de routes potentielles à partir de la table de topologie et - des deuxièmes moyens de recherche aptes à rechercher au moins une 20 route parmi les routes potentielles. D'une façon générale, l'invention vise ainsi un procédé et un dispositif mettant en oeuvre un protocole réactif pour la recherche de nouvelles routes lorsque des routes précédemment établies par un protocole proactif ne permettent pas d'identifier une route satisfaisant au 25 moins une contrainte entre un noeud source et un noeud destinataire. Autrement dit, on cherche, a priori, les routes parmi celles qui sont identifiées par le protocole proactif, de façon à ne pas diffuser de requêtes inutiles. Mais lorsque les routes identifiées par ce protocole proactif ne 30 perme a de satisfaire une cIntrainte on déclenche un u ,s r a la che des nouve fait en utius op()ogle ntaF par le prote ale ,)n ro-Hcri7`, de sorte que les requêtes de diffusion n'inondent pas le réseau, mais 35 parcourent uniquement un nombre limité de routes potentielles. Dans un mode particulier de réalisation de l'invention, le protocole de routage proactif obtient la table de routage en utilisant un algorithme du plus court chemin. L'algorithme de Dijkstra peut être utilisé. Dans un mode particulier de réalisation de l'invention, les routes potentielles sont calculées en utilisant un algorithme de type BFS ou DFS, tels que décrits dans le document "Introduction to Algorithms, Second Edition", par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ISBN: 0262032937. Dans un mode particulier de réalisation de l'invention, on diffuse, au cours de la deuxième étape de recherche, une requête de recherche de ladite au moins une route dans les routes potentielles, conformément à un mécanisme de type "source routing". On rappelle que dans un mécanisme de type "source routing", on insère, dans les requêtes, l'identité des noeuds au fur et à mesure de leur progression dans le réseau, de sorte que la requête contient, lorsqu'elle atteint le noeud destinataire, l'ensemble des références des noeuds de la route parcourue jusqu'alors. Dans un mode particulier de réalisation de l'invention, le protocole de routage proactif établit la table de routage en prenant en compte au moins une deuxième contrainte différente de la première contrainte. Afin de limiter la complexité du protocole de routage proactif, on se limitera préférentiellement à trois deuxièmes contraintes. Dans ce mode particulier de réalisation de l'invention, le protocole de routage réactif sera mis en oeuvre, lorsque l'on recherche une route devant satisfaire au moins une quatrième contrainte supplémentaire. Dans un mode particulier de réalisation de l'invention, les . d -2. es contraintes prises en cos- pour la construction pi ' les de otc~Dro métriques de qualité rvice, et par e; .riques si entes délai ; - taux de perte ; et - bande passante disponible. L'invention trouve une utilisation privilégiée lorsque les noeuds du réseau sont constitués par des équipements de télécommunication mobiles. Dans ce mode de réalisation, la première contrainte qui déclenche la mise en oeuvre du protocole réactif pourra par exemple être une contrainte satisfaite lorsque la somme des énergies disponibles (autrement dit l'autonomie restante) dans les équipements mobiles constituant une route est supérieure à un niveau minimal d'énergie prédéterminé. Une route ainsi établie est une route peu sensible aux interférences et aux bruits environnants. Dans un mode particulier de réalisation de l'invention, le protocole de routage réactif permet d'identifier plusieurs routes possibles entre le noeud source et le noeud destinataire. On met alors en oeuvre une étape de sélection utilisant une métrique prenant en compte le nombre de sauts entre le noeud source et le noeud destinataire pour sélectionner la meilleure route parmi ces différentes routes. Dans un mode particulier de réalisation, les différentes étapes du procédé d'identification de route sont déterminées par des instructions 20 de programmes d'ordinateurs. Dans ce document, le terme "ordinateur" est à prendre au sens large. Il vise tout dispositif de traitement de données et notamment un téléphone cellulaire. En conséquence, l'invention vise aussi un programme 25 d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en oeuvre dans un dispositif d'identification de route ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en oeuvre des étapes d'un procédé d'identification de route tel que décrit ci-dessus. 30 pngramme peut utii t'importe de ni soi ce i orme part1ellel rien dans n'i Ort sauhaitable 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 disc) 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 aussi un réseau de télécommunication 20 comportant une pluralité de noeuds adaptés à mettre en oeuvre un procédé d'identification de route tel que mentionné ci-dessus. Brève description des dessins D'autres caractéristiques et avantages de la présente invention 25 ressortiront de la description faite ci-dessous, en référence aux annexes et aux dessins qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif et dans lesquels : -l'annexe 1 est un listing, en pseudo-code, d'un programme informatique permettant de mettre en oeuvre l'algorithme connu de 30 Dijkstra ; 2B sc )seudo-ci le partic 111v(P.Ill 10r] ; - a figure 1 représente un réseau ad hoc dans lequel l'invention 35 peut être utilisée ; - la figure 2 représente une table de routage d'un noeud de ce réseau ; - la figure 3 représente, de façon schématique, un dispositif d'identification de route conforme à l'invention dans un mode particulier de réalisation ; et - la figure 4 représente, sous forme d'organigramme, les principales étapes d'un procédé d'identification de route conforme à l'invention dans un mode particulier de réalisation. 10 Description détaillée d'un mode de réalisation La figure 1 représente un réseau ad hoc 1 dans lequel peut être utilisée l'invention. Ce réseau est constitué par un ensemble de noeuds 10. Ces noeuds sont identiques ou non. Ils peuvent être par 15 exemple tous constitués par des équipements mobiles. Dans la suite de ce document, on désignera : - par S un noeud source - par D un noeud destinataire ; et - par les lettres minuscules a, b, c, d des noeuds intermédiaires pouvant 20 être utilisés pour acheminer un paquet entre le noeud source S et le noeud destinataire D. Un trait simple ou un double trait entre deux noeuds 10 représente le fait que ces deux noeuds sont voisins et qu'une communication radio peut être établie entre ces noeuds pour 25 l'acheminement d'un paquet. On va maintenant décrire, en référence à l'annexe 1, l'algorithme de Dijkstra, cet algorithme de plus court chemin pouvant être utilisé par un protocole de routage proactif pour établir, à partir d'une table de topologie TT, une table de routage TR du réseau ad hoc 1. 30 rappelle à et ~ 'off -t : est une matrice qui repré les u ces noeuds. El à i'f,cHnge diq Ir le Ine',s'ge As, comme c'est le cas pour le protocole proactif OLSR ( timized Link State 35 Routing" ; et - qu'une table de routage TR, au niveau d'un noeud S, contient, pour chaque destination D dans le réseau, l'adresse d'un élément E qui est le prochain noeud de routage voisin de S à un saut, pour atteindre la destination D. L'algorithme de Dijkstra permet de trouver le plus court chemin (selon des métriques prédéfinies : le nombre de sauts par exemple) entre un noeud d'origine donné s et n'importe quel noeud v du graphe G représentatif du réseau ad hoc 1. L'algorithme de Dijkstra emploie la technique de relâchement. Plus précisément, pour chaque noeud von gère un attribut djv] qui est un majorant d'un plus court chemin entre l'origine set v. djv]est appelé "estimation du plus court chemin". Les estimations et les prédécesseurs K.]) sont initialisés par la procédure "7'nitiallsation"de l'annexe 1. La procédure Welax" est utilisée pour le processus de relâchement. La table de topologie U et la table de routage TR obtenues par l'algorithme de Dijkstra sont données à la figure 2. Selon les notations de l'annexe 1, l'ensemble E contient la liste des noeuds formant le plus court chemin (en termes de métrique de routage choisie) entre la source s et la destination d. L'élément de E, qui est voisin de s à un saut, est le "prochain routeur" dans la table de routage TR pour atteindre le noeud destinataire d. La table de routage TR décrite à la figure 2 est celle de la 25 source S. Elle comporte une première colonne dans laquelle apparaissent tous les noeuds a, b, c, d, D du réseau ad hoc 1 et une deuxième colonne dans laquelle est mémorisé, en vis-à-vis d'un noeud v, le prochain routeur PR(V) suivant S dans le plus court chemin vers v. 30 figure 1, -ln a représe -t' dot trait le plus court ,ins buis. a bcr( i a ol intermédiaire a est associé au noeud destinataire D dans la table de 35 routage TR. L'algorithme de Dijkstra décrit précédemment en référence à l'annexe 1 utilise une métrique représentative du nombre de sauts entre le noeud source S et le noeud destinataire D. Nous allons maintenant décrire en référence aux annexes 2A et 2B un algorithme de Dijkstra modifié (Dijkstra-Moc/ifie) utilisant, à la place de la métrique "nombre de sauts", une métrique composée de trois métriques primaires de qualité de service, à savoir : - le délai (contrainte CI), - le taux de perte (contrainte C2), et - la bande passante disponible (contrainte C3) sur le réseau ad hoc 1. Le taux de perte étant une métrique multiplicative, on peut la transformer en une métrique additive comme décrit ci-dessous : Si pu est la probabilité de perte sur le lien (i, j), la probabilité de succès sur le lien (i, j) serait alors qu = 1 - pu . Ainsi, sur le chemin P de la source /vers la destination t : la probabilité de perte serait : Pperte(P) = 1- qu)(q,k) ..(q1t)). Supposons que la probabilité-logarithmique de succès du lien (i, j), eu, soit définie par : pis,/ = ùlog q,, . Alors la probabilité-logarithmique de succès sur le chemin P est : pls(P) = log q,- Si on suppose que la probabilité de perte sur une route donnée, R, est inférieure à 0.9. On a alors 0.1 Soit une route R = (s, k, d). La bande passante disponible sur R est min b,, et la longueur de R est Mh + 111k, + .+ Mra . Le problème est de trouver une route, R, telle que la bande passante disponible sur R soit supérieure à B, et la longueur de R soit 10 inférieure à M. Soit une route R du sommet s vers le sommet d comportant y sauts, si plsu Dans l'exemple décrit ici, ce dispositif 20 est incorporé dans un téléphone portable 10 constituant un noeud du réseau ad hoc 1. Dans l'exemple décrit ici, le dispositif 20 d'identification selon l'invention comporte des moyens classiques de traitement d'un ordinateur, à savoir un processeur 31, une mémoire morte de type ROM 33 et une 10 mémoire vive de type RAM 312. Dans l'exemple décrit ici, un programme d'ordinateur PG conforme à l'invention est enregistré dans la mémoire morte 33. Ce programme d'ordinateur comprend des instructions pour l'exécution des étapes du procédé d'identification de route conforme à 15 l'invention dont l'organigramme est représenté à la figure 4. Dans l'exemple de réalisation décrit ici, le programme informatique PG comporte un module PRP adapté à mettre en oeuvre le protocole de routage proactif PRP basé sur l'algorithme de Dijkstra modifié décrit précédemment en référence aux annexes 2A et 2B. 20 En particulier, le module de routage proactif PRP est apte à établir et à maintenir une table de routage TR et une table de topologie TT qui, dans l'exemple décrit ici, sont mémorisées dans une mémoire réinscriptible non volatile 34 du dispositif d'identification 20 conforme à l'invention. 25 Conformément aux notations de l'annexe 1B, l'ensemble L contient la liste des noeuds formant le plus court chemin entre la source s et la destination d. L'élément de L, qui est voisin de s à un saut, est le "prochain routeur" dans la table de routage TR pour atteindre le noeud destinataire di 30 pri Noi allons g( es s du ration un ;ii 11 [SHI [(Ji \sious nous placerons dans le contexte dans lequel les tables de routage TR et de topologie H sont déjà établies par le module de routage 35 proactif PRp. Ainsi, la table de topologie TT représente une topologie du réseau ad hoc prenant en compte les trois contraintes constituées par les métriques délai (C1), taux de perte (C2) et bande passante disponible (C3). Nous supposerons dans cet exemple qu'une nouvelle connexion est établie entre le noeud source S et le noeud destinataire D demandant qu'une quatrième contrainte C4 soit satisfaite. Dans l'exemple décrit ici, cette contrainte C4 est satisfaite lorsque la somme des énergies disponibles el des équipements mobiles 10 constituant la route R entre le noeud source S et le noeud destinataire D est supérieure à un niveau minimal E d'énergie prédéterminé. Au cours d'un premier test E10 du procédé, on vérifie si le plus court chemin défini par les tables de routage TR, entre le noeud source S et le noeud destinataire D, vérifie cette quatrième contrainte. Dans l'exemple décrit ici, ceci revient à vérifier si la somme des 15 énergies disponibles dans les téléphones mobiles S, a, c et D est supérieure à l'énergie minimale E. Si tel est le cas, le résultat du test E10 est positif. Ce test est alors suivi par une étape E20 au cours de laquelle on établit une connexion entre le noeud source S et le noeud destinataire D en suivant la 20 route R définie par ces tables de routage. Si tel n'est pas le cas, le résultat du test E10 est négatif et on déclenche un algorithme de routage réactif pour identifier de nouvelles routes permettant de satisfaire toutes les contraintes. A cet effet, le noeud S détermine, au cours d'une étape E30, un 25 certain nombre de routes potentielles Rk à partir de la table de topologie TT maintenue à jour par le module de routage proactif PRR Dans l'exemple décrit ici, ces routes potentielles Rk sont mémorisées dans la mémoire vive 32 du dispositif d'identification conforme à l'invention. 30 Cette 'ti-spe E30 de s ti 1. des routes pote n; iell est irs noeud IrCE wc" source-rou D, une reque' su :une d R if )-1 Ament '1! " ,r de source-routing, on vérifie au fur et à mesure que ces requêtes traversent les noeuds 35 intermédiaires vers le noeud destinataire D, si cette route vérifie la quatrième contrainte C4. Typiquement, puisqu'il s'agit d'une contrainte additive, on établit le cumul des énergies e, disponibles dans tous les noeuds traversés par la requête. Une fois le noeud destinataire D atteint, on vérifie si l'énergie de 5 ce chemin est supérieure à la valeur minimale requise E. Si tel est le cas, une réponse positive est renvoyée vers le noeud source S. Dans le cas contraire, une réponse négative est renvoyée vers le noeud source S. 10 Cette étape E40 de diffusion de la requête est suivie par une étape E50 au cours de laquelle le noeud source S vérifie si les contraintes sont satisfaites, en fonction de la réponse reçue à l'étape précédente. Si tel est le cas, le résultat du test E50 est positif. Ce test est alors suivi par une étape E60 au cours de laquelle on choisit, parmi toutes 15 les routes satisfaisantes, celle qui comporte le moins de sauts. Puis, au cours d'une étape E70, on établit la connexion entre le noeud source S et le noeud destinataire D suivant cette route. Si aucune des routes potentielles Rk ne permet de satisfaire la quatrième contrainte, le résultat du test E50 est négatif. 20 Ce test est alors suivi par une étape E80 au cours de laquelle on diffuse une requête sur tout le réseau ad hoc 1 pour rechercher les routes qui satisfont à la contrainte C4. Dans l'exemple décrit précédemment, l'algorithme de routage réactif est mis en oeuvre pour rechercher une route lorsqu'une nouvelle 25 contrainte (en l'occurrence la quatrième contrainte) doit être prise en compte. Dans d'autres modes de réalisation de l'invention, le routage réactif peut être mis en oeuvre à l'initiative de l'application de routage, dès lors que l'algorithme de routage proactif ne constitue pas ou plus une 30 utiT-7tisf-'1ante pot ratifier les routes, même si les contraintes DM Ur ' de ces route- inchan ANNEXE 1 Initialisation (G, s) DEBUT pour chaque noeud v faire ct[v] : = co 7r[v] : = NIL ces] := 0 FIN Relax (u, v DEBUT si ci[v] > d[u] + w(u, v) alors d[v] := d[u] + w(u, v) 7r[v] := u FIN Dijkstra (G, w, s) DEBUT Initialisation (G, s) E : = 0 F := S[G] tant que F# 0 faire u:= Extract-Min(F) E := E U {} pour chaque sommet vadjacent à u faire Relax(u, v) FIN ANNEXE 2A Initiallsation Modifié (IV, A) DEBUT Dijkstra (N, A) ; pour chaque sommet adjacent à j faire si (bu Relax Modifié (MO DEBUT pour chaque i e L faire si ((Mk + mk, , RPkfinsi fait ANNEXE 2B D,jkstra Modifié(N,A) DEBUT Initialisation Modifié (N, A) F:=S[G]; 1* F contient l'ensemble des sommets du graphe G */ tantque F* 0 Trouver k e L tel que (Mk = min;l I, ET MI - P ) si Mk > M alors il n'y pas de chemin faisable. STOP. L := Lu {(k, -ii-[k])}; F :=F-{k} ; Si L contient la destinataire d alors la route a été trouvée. STOP Relax Modifié (N, L); fin tantque FIN REVENDICATIONS 1. Procédé d'identification d'au moins une route (R) satisfaisant au moins une première contrainte (C4) entre un noeud source (S) et un noeud destinataire (D) dans un réseau de télécommunications, ce procédé comportant : - une première étape (EIO) de recherche de ladite au moins une route (R) en utilisant une table de routage (TR) maintenue à jour par la mise en oeuvre d'un protocole de routage proactif (PRP) ; ce procédé étant caractérisé en ce qu'il comporte, en cas d'échec (E20) de ladite première étape de recherche (ElO) : - une étape (E30) de sélection d'un nombre prédéterminé (k) de routes potentielles (Rk) à partir d'une table de topologie (TT) maintenue à jour 15 par ledit protocole de routage proactif (PRP) ; et - une deuxième étape (E40) de recherche de ladite au moins une route (R) parmi lesdites routes potentielles (Rk). 2. Procédé d'identification selon la revendication 1, caractérisé 20 en ce que ledit protocole de routage proactif (PRP) obtient ladite table de routage (TR) en utilisant un algorithme du plus court chemin. 3. Procédé d'identification selon la revendication 1 ou 2, caractérisé en ce que lesdites routes potentielles (Rk) sont calculées en 25 utilisant un algorithme de type BFS ou DFS. 4. Procédé d'identification selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'on diffuse, au cours de ladite deuxième étape (E40) de recherche, une requête de recherche de ladite 30 au moins ,Ine route dans '-,)sdtes routes potentielles (Rk), i,s( 5 r,y-eô,= '^ r ' quelconque des revendications à 4, caractérisé en ce que ledit protocole de routage 35 proactif (PRP) établit ladite table de routage (TR) en prenant en compte aumoins une deuxième contrainte (CI, C2, C3) différente de ladite au moins une première contrainte (C4). 6. Procédé d'identification selon la revendication 5, caractérisé en ce que ladite au moins une deuxième contrainte (C1, C2, C3) est une métrique de qualité de service. 7. Procédé d'identification selon la revendication 6 dans lequel on utilise trois deuxièmes contraintes constituées par les métriques 10 suivantes: - délai (CI) ; - taux de perte (C2) ; et - bande passante disponible (C3). 15 8. Procédé d'identification selon l'une quelconque de s revendications 1 à 7 dans lequel les noeuds du réseau sont constitués par des équipements de télécommunication mobiles (10), caractérisé en ce que ladite première contrainte (C4) est satisfaite lorsque la somme des énergies disponibles (ei) des noeuds (10) constituant ladite route (R) est 20 supérieure à un niveau minimal (E) d'énergie prédéterminé. 9. Procédé d'identification selon l'une quelconque des revendications 1 à 8, caractérisé en ce qu'il comporte une étape (E60) de sélection d'une seule route parmi lesdites au moins une route (R), ladite 25 étape (E60) de sélection utilisant une métrique prenant en compte un nombre de sauts entre ledit noeud source (S) et ledit noeud destinataire (D). 10. Dispositif (20) d'identification d'au moins une route (R) 30 satisfaisant au moins premi cc - intc _titre un noeud rce -t un nos -,ir, comr ns, , JeÇ TlOyetl( lise en oeuvre d'un protocole de ntage proactit (Pkp) apte à établir et maintenir une table de routage (TR) et une 35 table de topologie (U); et- des premiers moyens (31, 32, 33) de recherche de ladite au moins une route (R) en utilisant ladite table de routage (TR) ; ce dispositif (20) étant caractérisé en ce qu'il comporte en outre : - des moyens (31, 32, 33) de recherche d'un nombre prédéterminé (k) de routes potentielles (Rk) à partir de ladite table de topologie (U) ; et - des deuxièmes (31, 32, 33) moyens de recherche aptes à rechercher ladite au moins une route (R) parmi lesdites routes potentielles (Rk). 11. Programme d'ordinateur (PG) comportant des instructions 0 pour l'exécution des étapes du procédé d'identification de route selon l'une quelconque des revendications 1 à 10 lorsque ledit programme est exécuté par un ordinateur (10). 12. Support d'enregistrement (33) lisible par un ordinateur (10) 15 sur lequel est enregistré un programme d'ordinateur (PG) comprenant des instructions pour l'exécution des étapes du procédé d'identification de route selon l'une quelconque des revendications 1 à 10. 13. Réseau de télécommunications (1) comportant une pluralité 20 de noeuds (10) adaptés à mettre en oeuvre le procédé d'identification de route selon l'une quelconque des revendications 1 à 10.