Brevet FR2822324A1 — publié le 20020920

station de base. - - 1 2822324 Procédé dichotomique pour la détermination d'un chemin entre deux n_uds d'un réseau de données La présente invention est relotive à un procédé de détermination d'un chemin entre deux n_uds d'un réseau de données utilisant les protocoles de la famille TCP/IP (Transmission Control Protocol / Internet Profocol). Typiquement, selon ces protocoles, chaque n_ud du réscau n'a une vision que d'une partie du réseau, de sorte que la fonction d'acheminement est répartie à travers le réscau sans qu'aucun des n_ubs n'ait la connaissance du chemin complet suivi par les paquets de données. Ce protocole d'acheminement peut par exemple 8tre TCP (Transmission Control Profocol) ou UDP (User Datagram Protocol). Dans la majorité des cas, ces protocoles sont suffisants car en général, I'émetteur d'un paquet est uniquement intéressé par la transmission effective de son paquet, et non par le chemin exact qu'il suit. Toutefois, il existe quelques applications pour lesquelles la connaissance du chemin complet pris par les paquets est sinon indispensable, tout du moins importante. Une telle application est par exemple, la diffusion de paquets vers plusieurs destinataires, tel qu'illustré par la figure 1 et tel que décrit dans le RFC (Request for Comments) numéro 1054, intitulé " Host Extensions for IP Multicasting >. Sur cette figure 1, on a représenté 7 n_ubs R1, R2, R3... R7. Le n_ud R1 est l'émetteur de paquets de donnces. Ces paquets de données font typiquement partie d'un flux de donnses, par exemple de la vidéo. On a représenté aussi des flèches correspondant aux sens de communication de 1031 42/SYC/NAD \\klefilO 1 \DPI $\5ci le\F 1031 42\PREMD E P\F IT\projelbr.doc 2 2822324 I'information entre les différents n_uds. Les double-flèches représentent des communications symétriques. Les n_uds R6 et R7 sont intéressés par recevoir ce flux de donnéss. Aussi, ils émettent à destination de la source du flux, R, un message d'enregistrement, par exemple un message "Join" selon le protocole IGMP (Internet Group Management Protocol) tel que délini dans le RFC 1 1 12. Le message d'enregistrement du n_ud R7 passe par les n_uds R5 et R2 avant d'aboutir au n_ud source R3. Par ailleurs, le message d'enregistrement du n_ud R6 passe par les n_uds R4, R3, R2 et Rj. Le flux de données va donc étre transmis à la fois vers le n_ud R2 pour transmission vers le n_ud R6 et vers R5 pour transmission vers le n_ud R5. Si le n_ud R. avait été à méme de conna^'tre le chemin exact vers chacun des n_uds destinata ires, il au ra it tra nsmis u n seu l flux de don nées vers le n_ud R5, à charge pour lui de dupliquer ce flux d'une part vers le n_ud R7 et d'autre part vers le n_ud R6. On voit donc que la maconnaissance du chemin complet entre les n_uds ne permet pas une utilisation optimale du réseau de donnéss et le surcharge inutilement. Une solution permettant de conna^tre un chemin entre deux nçuds a été proposée par le logiciel "TraceRoute", datant pour ses premières versions de 1 988. Son principe consiste à utiliser un paquet vers le n_ud vers lequel on cherche un chemin, en lui fixant une durée de vie croissante. Chaque n_ud traversé décrémente la durée de vie du paquet, d'une unité. Lorsque la durée de vie atteint 0, le n_ud ayant recu le paquet, ne le transmet plus, mais émet vers l'émetteur un message de dépassement de durée de vie, en y insérant son identificateur. Ainsi, un procédé simple, mis en _uvre par le logiciel 1031 42/SYC/NAD L:\Solle\F 1031 42\PREAiDEP\TEXTE\Dernier. doc 3 2822324 TraceRoute, consiste à transmettre un paquet avec une durée de vie de 1, puis de 2, 3 etc. jusqu'à ce que finalement, le n_ud cible soit atteint. En mémorisant à chaque fois, le n_ud émetteur du message de dépassement de durce de vie, on peut reconstituer le chemin complet vers le n_ud cible. Toutefois, un tel procédé présente l'inconvénient majeur de nécessiter un grand nombre de paquets. En effet, dans un réssau de donnces de grandeur réel, la taille des chemins peut 8tre importante et donc impliquer un nombre trop important de paquets et de messages de dépassement de durce de vie. Le but de la présente invention est donc de réduire le nombre de paquets, et donc l'encombrement du réscau de donnces, nécessaire pour déterminer un chemin complet entre deux n_ubs. Pour ce faire, I'invention a pour objet un procédé de détermination d'un chemin entre un n_ud d'origine et un n_ud cible d'un réseau de donnces de type TCP/IP, consistant à définir une fonction de recherche de chemin, ayant pour paramètre une distance de début, et une distance de fin et comprenant les étapes suivantes: arrêter le traitement récursif de la fonction, si les distances de début et de fin diffèrent d'une unité, envoyer un message vers le n_ud cible, avec une durée de vie égale à une valeur intermédiaire comprise entre les distances de début et de fin, recevoir une réponse, Si la réponse provient du n_ud cible, alors on le mémorise dans la liste des n_ubs connus, et on exécute récursivement la fonction de recherche avec comme paramètres la distance de début et la distance du n_ud cible, Si la réponse est un message de dépassement provenant d'un n_ud intermédiaire faisant partie de la liste des n_uds connus, 103142/SYC/NAD \\klefilOl\DPl$\Salle\F103142\PREMDEP\FIT\projelEr. doc 4 2822324 alors on exécute récursivement la fonction de recherche avec comme paramètres la distance du n_ud intermédiaire et la distance de fin, Si la réponse est un message de dépassement provenant d'un n_ud intermédiaire ne faisant pas partie de la liste des n_uds connus, alors on mémorise le n_ud intermédiaire dans la liste des n_uds connus, et on exécute récursivement la fonction de recherche, une première fois avec comme paramètres la distance de début et la distance du n_ud intermédiaire, et une seconde fois avec comme paramètres la distance du n_ud intermédiaire et la distance de fin. Le procédé consiste alors à exécuter initialement cette fonction de recherche de chemin avec une distance de début égale à 0. Ainsi, par l'utilisation d'un procédé dichotomique, on peut sensiblement rébuire le nombre de paquets transmis. Celui-ci devient en effet de l'ordre de grandeur du logaritEme du chemin complet. L'invention et ses avantages appara^tront de facon plus claire dans la description qui va suivre, en liaison avec les figures jointes. La figure 1, précédemment commentée, représente un réssau de données et une application possible de l'invention. Les figures 2a, 2b et 2c illustrent les trois situations possibles, après réception d'une réponse, selon le procédé de l'invention. La figure 3 schématise un exemple pratique de mise en _uvre de l'invention. La première étape du procédé selon l'invention consiste à exécuter la fonction de recherche de chemin en lui spécifiant une distance de début égale 1 03142/SYC/NAD \\klefilOl\DPI$\5alle\F1031 42\PREMDEP\FIT\projelbr.doc 2822324 à 0, et une distance de fin préférentiellement égale au double de la moyenne des distances des n_ubs compris dans la liste des n_ubs connus. La justification de cette dernière valeur est statistique: on suppose que la distance du n_ud cible est égale à la moyenne des distances des n_ubs que I'on conna'^t déjà, et l'on considère que le n_ud cible se trouve à une distance au plus égale au double de cette valeur moyenne. La fonction de recherche de chemin envoi, en premier lieu, un message vers le n_ud cible, ayant une durée de vie fixée. La fixation d'une durée de vie à un message peut se faire en utilisant le champ TTL (Time To Live) ainsi que spécifié dans le RFC 791. Ce champ TTL est décrémenté d'une unité à chaque n_ud traversé par le message. Lorsqu'il atteint 0, le message n'est plus transmis et un message de dépassement de durée de vie est transmis vers l'émetteur de ce message. Typiquement, donc, ce message est un message ICMP ECHO, conformément au protocole ICMP (Internet Control Message Protocol), tel que défini dans le RFC 792. Le message de dépassement de durée de vie est un message du type ICMP "TTL excceded", conforme à ce même protocole. Conformément à une caractéristique de l'invention, lorsque le n_ud cible rec,oit le message ICMP Echo, il répond à l'émetteur par un message contenant au moins son identificateur. Ainsi, le n_ud mettant en _uvre le procédé selon l'invention se trouve devant trois situations illustrces par les figures 2a à 2c. Dans ces figures, les références RO et RF représentent, respectivement, les n_uds d'origines et de fin. 1031 42/SYC/NAD \\kl efilO 1 \D Pl $\Sa lle\F 1031 42\PREMDEP\FIT\projelbr.doc 6 2822324 Le cas o la réponse provient du n_ud cible est illustré par la figure 2a. Cela signifie que le n_ud cible, R. se trouve à une distance plus courte que prévue. On exécute donc la fonction de recherche trécursivement) en lui fixant la même distance de début (donc originairement, 0) et une distance de fin égale à la distance du n_ud cible. Autrement dit, on recherche le chemin menant jusqu'à ce n_ud cible, R. Le cas o la réponse est un message de dépassement provenant d'un n_ud intermédiaire faisant partie de ia liste des n_uds connus est illustré par la figure 2b. Il représente cette fois-ci le cas o le n_ud cible, R. est plus loin qu'escompté. Toutefois, comme on connaissait déjà le n_ud qui a répondu, R2, on doit rechercher le n_ud cible entre ce n_ud intermédiaire et le n_ud correspondant à la distance de fin. On exécute donc la fonction de recherche avec comme paramètres la distance du n_ud intermédiaire, R2, et la distance de fin. Le troisième cas correspond à la situation o la réponse est un message de dépassement de durce de vie, comme dans le cas précédent, ma is cette fois-ci provenant d'un n_ud intermédiaire ne faisant pas partie de la liste des n_uds connus. Cette situation est illustrse par la figure 2c. Elle représente le cas o le n_ud cible est plus loin que prévu, et o le n_ud intermédiaire, R, n'est pas dans la liste des n_uds connus. On doit donc à la fois rechercher le n_ud cible, R. qui se trouve forcément au delà du n_ud intermédiaire R, et rechercher le chemin menant à ce n_ud intermédiaire. Da ns cette situation, on mémorise le n_ud intermédiaire da ns la l iste des n_uds connus, et on exécute récursivement la fonction de recherche, une première fois avec comme paramètres la distance de début et la distance du n_ud intermédia ire, et une seconde fois avec comme pa ra mètres la distance du n_ud intermédiaire et la distance de fin, 103142/SYC/NAD \\klefilOl\DPl$\Salle\F103142\PREMDEP\FIT\projelbr.doc 7 2822324 On arrête le traitement récursif lorsque les distances de début et de fin ne diffèrent que d'une unité. La figure 3 illustre un exemple de mise en _uvre du procédé selon I'invention. Les références a, b... k représentent ies n_ubs d'un chemin. Le n_ud a est le n_ud sur lequel est mis en _uvre le procédé de détermination de chemin. On suppose que la longueur moyenne des chemins connus est de 5, et que le n_ud cible est le n_ud i. On suppose aussi que tous les n_ubs jusqu'au n_ud f inclus font parties de la liste des n_ubs connus. Dans un premier temps, on exécute la fonction de recherche de chemin avec comme paramètres 0 et 10 (2 fois la longueur moyenne des chemins connus). Un paquet m est alors envoyé à destination du n_ud i avec une durée de vie égale à 5 (moyenne entre 0 et 10). Le paquet arrive au n_ud f, qui renvoi un message de dépassement de durce de vie. Comme le n_ud f fait partie de la liste des n_uds connus, on exécute alors la fonction de recherche de chemin avec comme paramètres 5 et 10. Un deuxième paquet, m2, est alors émis à destination du n_ud i, avec une durée de vie égale à 7 (moyenne tronquée de 5 et 10). Le paquet arrive au n_ud h qui renvoi un message de dépassement de durée de vie. Le n_ud h ne fait pas partie de la liste des n_uds connus. On l'a joute donc dans la liste des n_ubs connus, et on exécute deux fois la fonction de recherche de chemin. Une première fois, avec pour paramètres 5 (ancienne distance de début) et 7 (distance du n_ud h) 1031 42/SYC/NAD \\klefilO 1 \DPI $\5011e\F 1031 42\PRElADEP\Fll\projelbr.doc 8 2822324 À Une seconde fois, avec pour paramètres 7 (distance du n_ud h) et (ancienne distance de fin). Dans la première exécution de la fonction de recherche de chemin, un paquet m3a est envoyé à destination du n_ud i, avec une durée de vie égale à 6, moyenne des deux paramètres 5 et 7. Le paquet m3a arrive donc au n_ud g, qui renvoi un message de dépassement de durce de vie. Ce n_ud g ne fait pas partie de la liste des n_uds connus. Il y est donc l O a jouté. Comme les distances 5 et 6 d'une part, et 6 et 7 d'autre part, ne différent que d'une unité, le traitement récursif s'arréte ici. Dans la seconde exécution de la fonction de recherche de chemin, un paquet m3b est envoyé à destination du n_ud i avec une durée de vie égale à 7, moyenne tronquse des deux paramètres 7 et 10. Le paquet m3b arrive au n_ud i qui est le n_ud cible. Ce n_ud i répond alors au n_ud en insérant son identificateur dans ce message de réponse. A la réception de ce message, le n_ud a inséré le n_ud i dans la liste des n_uds connus, pour les mémes raisons que pour la première exécution, le traitement récursif s'arrête ici. Ainsi, moyennant l'émission de 4 paquets, m, m2, m3a et m3b, le n_ud i ainsi que le chemin complet y parvenant ont été trouvés et ajoutés à la liste des n_uds connus. 1031 42/SYC/NAD \\klefilO 1 \DPI$\Salle\F 1031 42\PREMDEP\FIT\projelbr. doc 9 2822324 Revendications 1) Procédé de détermination d'un chemin entre un n_ud d'origine et un n_ud cible d'un réscau de données de type TCP/IP, consistant à définir une fonction de recherche de chemin, ayant pour paramètre une distance de début, et une distance de fin et comprenant les étapes suivantes: arréter le traitement récursif de la fonction, si les distances de début et de fin diffèrent d'une unité, envoyer un message vers ledit n_ud cible, avec une durée de vie égale à une valeur intermédiaire comprise entre les distances de début et de fin, recevoir une réponse, Si ladite réponse provient du n_ud cible, alors on le mémorise dans la liste des n_uds connus, et on exécute récursivement la fonction de recherche avec comme paramètres la distance de début et la distance du n_ud cible, Si ladite réponse est un message de dépassement provenant d'un n_ud intermédiaire faisant partie de ladite liste des n_ubs connus, alors on exécute récursivement la fonction de recherche avec comme paramètres la distance du n_ud intermédiaire et ladite distance de fin, Si ladite réponse est un message de dépassement provenant dun n_ud intermédiaire ne faisant pas partie de ladite liste des n_ubs connus, alors on mémorise ledit n_ud intermédiaire dans la liste des n_ubs connus, et on exécute récursivement la fonction de recherche, une première fois avec comme paramètres la distance de début et la distance du n_ud intermédiaire, et une seconde fois avec comme paramètres la distance du n_ud intermédiaire et la distance de fin, 1031 42/SYC/NAD \\klefilO 1 \DPI$\Salle\F 1031 42\PREMDEP\FIT\projelbr.doc 1 0 2822324 et à exécuter initialement cette fonction de recherche de chemin, avec une distance de début égale à 0. 2) Procédé selon la revendication 1, dans lequel ladite valeur intermédiaire est égale à la moyenne des distances de début et de fin. 3) Procédé selon l'une des revendications 1 ou 2, dans lequel la distance de fin est initialement fixée au double de la moyenne des distances des n_uds compris dans ladite liste des n_uds connus. 4) Procédé selon l'une des revendications précédentes, dans lequel ladite durée de vie est enregistrce dans un champ TTL (Time To Live) conforme au RFC 791. 5) Procédé selon l'une des revendications précédentes, dans lequel ledit message et ladite réponse sont conformes au protocole ICMP, défini par le RFC 792.