FR2770715A1 - Detection de rupture de lien dans un reseau distribue - Google Patents
Detection de rupture de lien dans un reseau distribue Download PDFInfo
- Publication number
- FR2770715A1 FR2770715A1 FR9713785A FR9713785A FR2770715A1 FR 2770715 A1 FR2770715 A1 FR 2770715A1 FR 9713785 A FR9713785 A FR 9713785A FR 9713785 A FR9713785 A FR 9713785A FR 2770715 A1 FR2770715 A1 FR 2770715A1
- Authority
- FR
- France
- Prior art keywords
- station
- message
- stations
- considered
- identifier
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/02—Details
- H04L12/16—Arrangements for providing special services to substations
- H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
- H04L12/1854—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast with non-centralised forwarding system, e.g. chaincast
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/02—Topology update or discovery
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/02—Details
- H04L12/16—Arrangements for providing special services to substations
- H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
- H04L12/189—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast in combination with wireless systems
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W28/00—Network traffic management; Network resource management
- H04W28/02—Traffic management, e.g. flow control or congestion control
- H04W28/06—Optimizing the usage of the radio link, e.g. header compression, information sizing, discarding information
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W4/00—Services specially adapted for wireless communication networks; Facilities therefor
- H04W4/06—Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W8/00—Network data management
- H04W8/26—Network addressing or numbering for mobility support
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W88/00—Devices specially adapted for wireless communication networks, e.g. terminals, base stations or access point devices
- H04W88/02—Terminal devices
- H04W88/04—Terminal devices adapted for relaying to or from another terminal or user
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Mobile Radio Communication Systems (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
Chaque station d'un réseau distribué a en mémoire une table de routage. Selon l'invention, une station effectue les opérations suivantes lorsqu'elle reçoit un message :- mémorisation (E402, E405), dans un journal, de données concernant le message et comportant des identificateurs de message (ID, SEI), de station émettrice intermédiaire (SET), de station destinataire intermédiaire (SDT), de station destinataire finale (SDF) et un nombre (NR) de retransmission du message,et, si le nombre de retransmission atteint une valeur prédéterminée, si la station considérée n'est pas la station destinataire intermédiaire et si la station considérée a dans sa table de routage l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,- émission (E413) d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
Description
La présente invention concerne le routage des communications entre les stations d'un réseau de type distribué.
Le réseau est par exemple un réseau local sans fil dont les stations communiquent entre elles en se partageant un canal radio.
Un réseau de type distribué ne possède pas de station de base pour gérer les communications entre les stations. Une fonction de routage rend possible les communications entre les stations du réseau, en déterminant les chemins de communication dans le réseau. Cette fonction est adaptée aux contraintes d'un réseau local sans fil, notamment la bande passante limitée, et la mobilité des stations ou les modifications de l'environnement des stations qui provoquent des changements de topologie du réseau.
Des procédés connus de routage reposent sur des échanges périodiques de messages de routage pour détecter les changements de topologie du réseau. La fonction de routage doit modifier le plus rapidement possible les chemins de communication dans le réseau, pour que les chemins connus correspondent aux chemins réels existant dans le réseau, faute de quoi le risque de mauvais acheminement et de perte de message est grand. II est donc nécessaire que les messages de routage soient fréquents.
Cependant, les messages de routage occupent le canal radio, au détriment des données utiles. II faut donc que la fonction de routage génère le moins possible de messages de routage, pour occuper peu de bande passante.
Ces contraintes sont contradictoires et rendent complexe le fonctionnement de la fonction de routage.
La présente invention vise à remédier aux inconvénients de la technique antérieure, en foumissant un procédé de détection de chemin et de transmission d'information de routage dans un réseau distribué, qui permet de détecter une rupture de lien et de transmettre l'information correspondante, rapidement et indépendamment de l'exécution de l'algorithme de routage.
A cette fin, I'invention propose un procédé de routage de message entre des stations d'un réseau, chaque station ayant en mémoire une première table respective contenant des identificateurs de stations destinataires finales de message respectivement associés à des identificateurs de stations destinataires intermédiaires de message, caractérisé en ce qu'une station considérée quelconque effectue les opérations suivantes lorsqu'elle reçoit un message de données:
- mémorisation, dans une seconde table respective, de données concernant le message et comportant au moins un identificateur de message, un identificateur de station émettrice intermédiaire, un identificateur de station destinataire intermédiaire, un identificateur de station destinataire finale et un nombre de retransmission du message,
et, si le nombre de retransmission du message atteint une valeur prédéterminée, si la station considérée n'est pas la station destinataire intermédiaire et si la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- émission d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
- mémorisation, dans une seconde table respective, de données concernant le message et comportant au moins un identificateur de message, un identificateur de station émettrice intermédiaire, un identificateur de station destinataire intermédiaire, un identificateur de station destinataire finale et un nombre de retransmission du message,
et, si le nombre de retransmission du message atteint une valeur prédéterminée, si la station considérée n'est pas la station destinataire intermédiaire et si la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- émission d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
Le procédé selon l'invention résout le problème énoncé ci-dessus, en utilisant les messages de données acheminés dans le réseau pour déduire qu'il y a une rupture de lien entre deux stations, afin de transmettre une information de routage à la station ayant subi la rupture de lien, ou à un ensemble de stations.
Le procédé permet de modifier très rapidement les tables de routage des stations du réseau, et ce indépendamment de la périodicité de l'exécution de l'algorithme de routage.
Grâce au procédé selon l'invention, les stations mobiles connaissent les modifications des chemins dans le réseau. En prenant en compte ces modifications pour modifier les tables de routage des stations, le nombre de messages perdus est considérablement réduit. L'acheminement des communications est ainsi fiabilisé.
Le procédé s'adapte à toute fonction de routage connue, dont l'exécution est indépendante du procédé selon l'invention. Grâce à la fiabilisation obtenue par l'invention, I'algorithme de routage peut être exécuté avec une période plus grande, et par conséquent générer moins de message de routage. L'augmentation de trafic de routage due aux messages spécifiques de routage selon l'invention est ainsi négligeable devant la diminution du trafic de routage due à la période plus grande de l'algorithme de routage.
Les performances du réseau sont ainsi améliorées, il résiste mieux aux perturbations que sont les ruptures de lien, il est donc globalement plus robuste.
Selon des caractéristiques préférées, le message spécifique de routage comporte au moins l'adresse de la station considérée, L'adresse de la station destinataire finale dudit message, et un coût de transmission entre la station considérée et la station destinataire finale dudit message, ou le message spécifique contient jusqu'à la totalité de la première table de la station considérée.
Ces données permettent de modifier la table de routage de la station destinataire du message spécifique de routage.
Selon une caractéristique préférée, I'identificateur de message comporte l'adresse de la station émettrice initiale du premier d'un ensemble de messages précédents ayant le même identificateur de message que ledit message. Les messages sont ainsi identifiés de manière simple et fiable.
Dans un autre aspect, I'invention propose un procédé de routage de message entre des stations d'un réseau, chaque station ayant en mémoire une première table respective contenant des identificateurs de stations destinataires finales de message respectivement associés à des identificateurs de stations destinataires intermédiaires de message, caractérisé en ce qu'une station considérée quelconque effectue les opérations suivantes, lorsqu'elle reçoit un message spécifique de routage indiquant l'existence d'un chemin entre deux stations:
- recherche si la station considérée est destinataire du message spécifique de routage, et, en cas de réponse positive,
- modification de la première table de la station considérée en fonction du message spécifique de routage.
- recherche si la station considérée est destinataire du message spécifique de routage, et, en cas de réponse positive,
- modification de la première table de la station considérée en fonction du message spécifique de routage.
La table de routage est ainsi modifiée rapidement et un nouveau chemin pourra etre utilisé dès le prochain message à acheminer.
L'invention conceme encore une station de communication d'un réseau, comportant une mémoire pour mémoriser une première table respective contenant des identificateurs de stations destinataires finales de message respectivement associés à des identificateurs de stations destinataires intermédiaires de message, caractérisée en ce qu'elle comporte, ou en ce qu'elle est adaptée à coopérer avec:
- des moyens de mémorisation, dans une seconde table respective, de données concernant chaque message de données qu'elle reçoit, ces données comportant au moins un identificateur de message, un identificateur de station émettrice intermédiaire, un identificateur de station destinataire intermédiaire, un identificateur de station destinataire finale et un nombre de retransmission du message,
- des moyens de vérification que le nombre de retransmission du message atteint une valeur prédéterminée, que la station considérée n'est pas la station destinataire intermédiaire et que la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- des moyens d'émission d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
- des moyens de mémorisation, dans une seconde table respective, de données concernant chaque message de données qu'elle reçoit, ces données comportant au moins un identificateur de message, un identificateur de station émettrice intermédiaire, un identificateur de station destinataire intermédiaire, un identificateur de station destinataire finale et un nombre de retransmission du message,
- des moyens de vérification que le nombre de retransmission du message atteint une valeur prédéterminée, que la station considérée n'est pas la station destinataire intermédiaire et que la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- des moyens d'émission d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
Dans un autre aspect, I'invention propose une station de communication d'un réseau, ayant en mémoire une première table respective contenant des identificateurs de stations destinataires finales de message respectivement associés à des identificateurs de stations destinataires intermédiaires de message, caractérisée en ce qu'elle comporte, ou en ce qu'elle est adaptée à coopérer avec:
- des moyens de réception de message spécifique de routage indiquant l'existence d'un chemin entre deux stations,
- des moyens de recherche si la station considérée est destinataire du message spécifique de routage, et
- des moyens de modification de la première table de la station considérée en fonction du message spécifique de routage.
- des moyens de réception de message spécifique de routage indiquant l'existence d'un chemin entre deux stations,
- des moyens de recherche si la station considérée est destinataire du message spécifique de routage, et
- des moyens de modification de la première table de la station considérée en fonction du message spécifique de routage.
La station de communication selon l'invention présente les mêmes avantages que ceux du procédé précédemment exposés.
Les caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels:
- la figure I représente un réseau distribué de stations,
- la figure 2 représente une station mobile du réseau de la figure 1,
- la figure 3 représente une table de routage de l'une des stations mobiles du réseau de la figure 1
- la figure 4 représente un message de données transmis d'une station mobile à une autre,
- la figure 5 représente un extrait d'une table de messages entendus par l'une des stations mobiles du réseau, selon l'invention,
- la figure 6 est un algorithme de traitement de message de données et de détection de rupture de lien, selon l'invention,
- la figure 7 est un algorithme de traitement de message spécifique de routage.
- la figure I représente un réseau distribué de stations,
- la figure 2 représente une station mobile du réseau de la figure 1,
- la figure 3 représente une table de routage de l'une des stations mobiles du réseau de la figure 1
- la figure 4 représente un message de données transmis d'une station mobile à une autre,
- la figure 5 représente un extrait d'une table de messages entendus par l'une des stations mobiles du réseau, selon l'invention,
- la figure 6 est un algorithme de traitement de message de données et de détection de rupture de lien, selon l'invention,
- la figure 7 est un algorithme de traitement de message spécifique de routage.
Selon le mode de réalisation choisi et représenté à la figure 1, un réseau local sans fil comporte des stations, dont cinq, référencée SMa à SMe sont représentées. Les stations sont ici mobiles. La connectivité des stations mobiles évolue en permanence, en fonction des déplacements des stations et des modifications de leur environnement. De plus, il est possible que le nombre de stations mobiles effectivement connectées au réseau évolue également. Les stations communiquent entre elles par transmission radio, ou en variante par transmission infrarouge. Chaque station, ou noeud du réseau, est repérée par une adresse unique. On s'intéresse ici plus particulièrement aux communications en mode point à point.
Le réseau est de type distribué, c'est-à-dire qu'il ne comporte pas de station de base pour gérer les communications entre stations. Les communications entre stations sont rendues possibles par une fonction de routage. Si deux stations, par exemple les stations SMa et SMb, sont en écoute directe, c'est-à-dire si ces deux stations sont suffisamment proches l'une de l'autre et sans obstacle à la transmission radio, elles peuvent communiquer directement sur le segment "ab". La station SMa peut envoyer un message, détaillé dans la suite, à la station SMb. La station SMa est dite station émettrice initiale, et la station SMb est dite station destinataire finale.
En revanche, si deux stations, par exemple les stations SM a et SMd, ne peuvent pas communiquer directement, la communication passe par d'autres stations intermédiaires, ici les stations SMb et SMC, qui jouent le rôle de relais entre les deux stations SM a et SMd. Le message est alors transmis successivement sur les segments "ab", puis "bc", et enfin "cd". Ces trois segments forment un chemin entre les stations SMa et SMd.
La fonction de routage s'exécute au-dessus d'un mécanisme d'accès
MAC contrôle d'accès au support (Medium Access Control) de type CSMA'CA accès multiple par détection de porteuse et évitement de collision (Carrier
Sense Multiple Access / Collision Avoidance) qui permet de partager le canal de transmission. Dans le cas des communications point à point, telles qu'envisagées ici, la fiabilité des communications de données est assurée par l'utilisation d'un mécanisme classique d'acquittement, ou accusé de réception, et de retransmission des données, si l'accusé de réception n'est pas reçu.
MAC contrôle d'accès au support (Medium Access Control) de type CSMA'CA accès multiple par détection de porteuse et évitement de collision (Carrier
Sense Multiple Access / Collision Avoidance) qui permet de partager le canal de transmission. Dans le cas des communications point à point, telles qu'envisagées ici, la fiabilité des communications de données est assurée par l'utilisation d'un mécanisme classique d'acquittement, ou accusé de réception, et de retransmission des données, si l'accusé de réception n'est pas reçu.
La fonction de routage est connue en soi et ne sera pas plus décrite.
Un mode de réalisation de l'une quelconque des stations, par exemple la station SMç, est représenté à la figure 2. Les moyens de mise en oeuvre de l'invention sont intégrés dans un ordinateur, qui comporte des interfaces utilisateurs classiques, non décrits ici. En variante, les moyens de mise en oeuvre de l'invention ne sont pas intégrés à une station mobile proprement dite, mais ces moyens et la station mobile sont adaptés à communiquer et coopérer ensemble.
La station SMC intègre une unité centrale de traitement sous la forme d'un processeur 10 relié par un bus d'une part à une mémoire morte (ROM) 30 dans laquelle sont enregistrés les programmes exécutés par le processeur et d'autre part à une mémoire vive (RAM) 20 comportant une zone de travail, des registres de données et une zone réservée au stockage des messages reçus ou en attente d'émission. La mémoire vive 20 stocke entre autres, un journal, exposé dans la suite, correspondant à la table des derniers messages reçus et entendus par la station mobile SMC.
La station mobile SMC comporte un module de communication radiofréquences 50, connu en soi, permettant à la station mobile SMC d'émettre et de recevoir des données vers et depuis d'autres stations mobiles.
L'interface entre le module de communication radiofréquences 50 et le processeur 10 se fait par:
- le port de contrôle 15, dont la valeur binaire représente l'état d'occupation du support de transmission sans fil à un instant donné,
- le port de lecture 16, dans lequel le processeur 10 lit les données reçues par la station mobile SMC,
- le port d'écriture 17, où la station mobile SMC peut aller écrire les données qu'elle souhaite émettre via le support de transmission radiofréquences.
- le port de contrôle 15, dont la valeur binaire représente l'état d'occupation du support de transmission sans fil à un instant donné,
- le port de lecture 16, dans lequel le processeur 10 lit les données reçues par la station mobile SMC,
- le port d'écriture 17, où la station mobile SMC peut aller écrire les données qu'elle souhaite émettre via le support de transmission radiofréquences.
Une horloge 40, reliée au processeur 10, permet à ce demier de réaliser des opérations à intervalles réguliers, telles que par exemple, les opérations de lecture / écriture dans les ports 15, 16, 17.
La station mobile SMC permet aux utilisateurs du réseau local sans fil d'échanger des données le long de chemins pouvant varier dans le temps et pouvant emprunter plusieurs stations intermédiaires, ces chemins étant établis à partir de tables de routage des stations mobiles du réseau.
Pour mettre en oeuvre la fonction de routage, chaque station mobile a en mémoire une table de routage représentée à la figure 3. La table de routage TRC de la station SMC comporte une liste de chacune des stations accessibles à partir de la station considérée, la prochaine station à atteindre pour atteindre chacune des stations accessibles et le coût pour atteindre chacune des stations accessibles. Le coût est par exemple le nombre de sauts nécessaires, c'est-à-dire le nombre de segments à parcourir, pour atteindre chacune des stations accessibles. Selon des variantes de réalisation, le coût peut tenir compte par exemple du rapport signal à bruit, du niveau de réception des messages, des délais d'acheminement, ou du nombre de stations voisines de la station considérée, ou encore être une combinaison de ces paramètres.
Ainsi, par exemple, il est possible d'atteindre la station SMe depuis la station SM, la prochaine station étant SMd, et le coût, c'est-à-dire ici le nombre de sauts, étant de deux.
La table de routage d'une station est valable à un instant donné, et est susceptible d'évoluer dans le temps.
D'autre part, la table de routage d'une station peut comporter d'autres informations, telles que numéro de séquence, drapeau, par exemple, qui ne sont pas utiles pour la présente invention.
Comme représenté à la figure 4, les données sont échangées entre stations sous la forme de message 60 comportant au moins les champs suivants:
- le champ 61 contenant l'adresse SEI de la station émettrice initiale du message,
- le champ 62 contenant l'adresse SDF de la station destinataire finale du message,
- le champ 63 contenant l'adresse SET de la station émettrice intermédiaire,
- le champ 64 contenant l'adresse SDT de la station destinataire intermédiaire,
- le champ 65 contenant un identificateur ID de message créé par la station émettrice initiale,
- le champ 66 contenant le coût CT du message, mis à jour par chaque station intermédiaire et par la station destinataire finale1
- le champ 67 de données proprement dites,
- le champ 68 contenant le type IT du message, ici message de données.
- le champ 61 contenant l'adresse SEI de la station émettrice initiale du message,
- le champ 62 contenant l'adresse SDF de la station destinataire finale du message,
- le champ 63 contenant l'adresse SET de la station émettrice intermédiaire,
- le champ 64 contenant l'adresse SDT de la station destinataire intermédiaire,
- le champ 65 contenant un identificateur ID de message créé par la station émettrice initiale,
- le champ 66 contenant le coût CT du message, mis à jour par chaque station intermédiaire et par la station destinataire finale1
- le champ 67 de données proprement dites,
- le champ 68 contenant le type IT du message, ici message de données.
Les stations émettrice initiale et destinataire finale sont les extrémités du chemin à parcourir par le message. Les stations émettrice intermédiaire et destinataire intermédiaire sont les extrémités d'un segment du chemin.
Chacune des stations mémorise des données sur chacun des messages de données qu'elle entend, même pour les messages qui ne lui sont pas destinés. Ces données sont mémorisées dans une table spécifique, ou joumal, dont la taille prédéterminée, correspondant à une fenêtre temporelle, est choisie en fonction d'un délai d'acheminement maximal de message dans le réseau. Comme représenté à la figure 5, pour chaque message de données entendu, la station SMd mémorise les données suivantes:
- le champ 71 contenant l'adresse SEI de la station émettrice initiale du message,
- le champ 72 contenant l'adresse SDF de la station destinataire finale du message,
- le champ 73 contenant l'adresse SET de la station émettrice intermédiaire,
- le champ 74 contenant l'adresse SDT de la station destinataire intermédiaire,
- le champ 75 contenant l'identificateur ID de message créé par la station émettrice initiale,
- le champ 76 contenant le coût CT du message, mis à jour par chaque station qui entend le message,
- le champ 77 contenant la date DT d'audition du message,
- le champ 78 contenant le nombre NR de retransmission.
- le champ 71 contenant l'adresse SEI de la station émettrice initiale du message,
- le champ 72 contenant l'adresse SDF de la station destinataire finale du message,
- le champ 73 contenant l'adresse SET de la station émettrice intermédiaire,
- le champ 74 contenant l'adresse SDT de la station destinataire intermédiaire,
- le champ 75 contenant l'identificateur ID de message créé par la station émettrice initiale,
- le champ 76 contenant le coût CT du message, mis à jour par chaque station qui entend le message,
- le champ 77 contenant la date DT d'audition du message,
- le champ 78 contenant le nombre NR de retransmission.
Les valeurs des six premiers champs sont déduites du message entendu et les deux demières sont mises à jour par la station SMd. La date d'audition DT n'est pas utilisée par la présente invention et peut servir notamment à contrôler les délais d'acheminement. Le coût CT est ici égal au nombre cumulé de tous les messages ayant le même identificateur que le message considéré.
La figure 6 représente un algorithme mis en oeuvre dans chacune des stations mobiles du réseau, lorsqu'un message de données est reçu, pour traiter ce message, et pour détecter une éventuelle rupture de lien. L'algorithme comporte des étapes E400 à E423 qui sont mémorisées en mémoire morte 30.
L'étape E400 est la réception d'un message par la station mobile.
Pour cela, le processeur 10 lit régulièrement le port 16 pour vérifier si le module radio 50 a reçu des données. Lorsqu'un message est reçu, le processeur lit le type de message dans le champ 68 indiquant qu'il s'agit d'un message de données.
Après la réception d'un message de données, L'étape E400 est suivie de l'étape E401, qui est un test pour vérifier si le message correspond à un message déjà mémorisé dans le journal de la station. Le test consiste à comparer le couple formé de l'identificateur ID du message et de l'adresse SEI de la station émettrice initiale du message avec les couples formés d'identificateur de message et d'adresse de station émettrice initiale de message qui sont mémorisés dans le joumal de la station considérée.
Si la réponse est négative, l'étape E401 est suivie de l'étape E402 à laquelle les données relatives au message en cours de traitement sont mémorisées dans le joumal de la station. Les données mémorisées sont celles représentées à la figure 5. L'étape E402 comporte la mise à jour du coût. Dans le cas où le coût est le nombre de sauts, ou de segments parcourus, le coût mémorisé est égal au coût lu dans le champ 66 du message, incrémenté de une unité. L'étape E402 est suivie de l'étape E407 qui sera décrite dans la suite.
Si la réponse à l'étape E401 est positive, cela signifie qu'il y a correspondance entre le message en cours de traitement et un message précédemment reçu et mémorisé. L'étape E401 est alors suivie de l'étape E403 qui est un test pour vérifier si le message en cours de traitement et le message déjà mémorisé qui lui correspond ont été émis par la même station émettrice intermédiaire. Le test consiste à comparer les adresses de station émettrice intermédiaire relatives aux deux messages, et mémorisées dans les champs 73 respectifs. Si la réponse est positive, cela signifie que le message en cours de traitement est une retransmission d'un message précédent, entre les mêmes stations émettrice et destinataire intermédiaires1 cette retransmission étant provoquée par une absence de réception d'accusé de réception par la station émettrice intermédiaire. Les données relatives au message en cours de traitement ne sont pas mémorisées. L'étape E403 est suivie de l'étape E404 a laquelle le nombre de retransmission NR du message correspondant est incrémenté de une unité, et la date d'audition est mise à jour. L'étape E404 est suivie de l'étape E407 qui sera décrite dans la suite.
Si la réponse à l'étape E403 est négative, cela signifie que le message en cours de traitement et le message déjà mémorisé qui lui correspond ont été émis par deux stations émettrices intermédiaires distinctes.
Cette étape est suivie de l'étape E405 à laquelle les données relatives au message en cours de traitement sont mémorisées dans le journal de la station, tel que représenté à la figure 5. L'étape E404 comporte la mise à jour du coût.
Dans le cas où le coût est le nombre de sauts, ou de segments parcourus, le coût mémorisé est égal au coût lu dans le champ 66 du message, incrémenté de une unité.
Les étapes E405 et E406 sont suivies de l'étape E407 qui est un test pour déterminer si la station considérée est la station destinataire intermédiaire du message en cours de traitement. Le test consiste à comparer l'adresse de la station et l'adresse SDT de station destinataire intermédiaire du message.
Si la station considérée n'est pas la station destinataire intermédiaire du message en cours de traitement, l'étape E407 est suivie de l'étape E410 qui est un test pour vérifier si le nombre NR de retransmission a atteint une valeur maximale prédéterminée. Si la réponse est négative, l'exécution de l'algorithme est terminée.
Si la réponse est positive à l'étape E410, cela signifie que le lien entre la station émettrice intermédiaire et la station destinataire intermédiaire est rompu. L'étape E410 est suivie de l'étape E41 1 qui est la consultation de la table de routage de la station considérée, pour déterminer si un chemin existe entre la station considérée et la station destinataire finale du message et quelle est la station destinataire intermédiaire de la station considérée, en fonction de la station destinataire finale du message.
L'étape suivante E412 est un test pour vérifier si la station destinataire intermédiaire déterminée à l'étape précédente est la station émettrice intermédiaire du message en cours de traitement. Si la réponse est positive, l'exécution de l'algorithme est terminée. En effet, si le prochain saut déterminé par la table de routage est la station ayant subi la rupture de lien, il est inutile d'envoyer un message spécifique de routage.
Si la réponse est négative, la station considérée envoie un message spécifique de routage pour indiquer qu'il existe un chemin entre la station considérée et la station destinataire finale du message en cours de traitement.
Le message spécifique de routage contient une indication de son type, et dans son champ de données, par exemple toute la table de routage de la station considérée, ou en variante seulement l'indication de chemin (prochain saut) entre la station considérée et la station destinataire finale du message en cours de traitement ainsi que le coût associé.
Le message spécifique de routage peut être émis en diffusion à horizon de un, ou en point à point, à destination de la station émettrice intermédiaire du message en cours de traitement, avec les avantages classiques de ces deux modes.
Si, à l'étape E407, la station considérée est la station destinataire intermédiaire du message en cours de traitement, L'étape E407 est suivie de l'étape E420 qui est un test pour déterminer si la station considérée est la station destinataire finale du message en cours de traitement. Le test consiste à comparer l'adresse de la station et l'adresse SDF de station destinataire finale du message.
Si la réponse est positive, l'acheminement du message est terminé, et l'étape E420 est suivie de l'étape E421 qui est la transmission du message vers la couche applicative de la station pour traiter les informations reçues, c'est-à-dire les informations qui étaient contenues dans le champ de données 67 du message.
Si la réponse à l'étape E420 est négative, cette étape est suivie de l'étape E422 qui est la consultation de la table de routage de la station considérée, pour déterminer quelle est la station destinataire intermédiaire vers laquelle la station considérée doit envoyer un message contenant les données à acheminer, en fonction de la station destinataire finale du message.
L'étape suivante E423 est la formation d'un message et l'envoi de ce message vers la station destinataire intermédiaire précédemment déterminée dont l'adresse est écrite dans le champ 64 de ce nouveau message. L'adresse SEI de la station émettrice initiale, l'adresse SDF de station destinataire finale,
I'identificateur ID de message et les données proprement dites de ce nouveau message sont recopiés dans les champs correspondants du message en cours de traitement. Le coût CT est mis à jour par la station considérée. L'adresse
SET de la station émettrice intermédiaire de ce nouveau message est celle de la station considérée.
I'identificateur ID de message et les données proprement dites de ce nouveau message sont recopiés dans les champs correspondants du message en cours de traitement. Le coût CT est mis à jour par la station considérée. L'adresse
SET de la station émettrice intermédiaire de ce nouveau message est celle de la station considérée.
La figure 7 représente un algorithme mis en oeuvre dans chacune des stations mobiles du réseau, lorsqu'un message spécifique de routage est reçu, pour traiter ce message. L'algorithme comporte des étapes E500 à E503 qui sont mémorisées en mémoire morte 30.
L'étape E500 est la réception d'un message par la station mobile.
Pour cela, le processeur 10 lit régulièrement le port 16 pour vérifier si le module radio 50 a reçu des données.
Après la réception d'un message, l'étape E500 est suivie de l'étape
E501, qui est un test pour vérifier si le message est un message spécifique de routage. Le test consiste à analyser le type du message. Si la réponse est négative, l'exécution de l'algorithme est terminée.
E501, qui est un test pour vérifier si le message est un message spécifique de routage. Le test consiste à analyser le type du message. Si la réponse est négative, l'exécution de l'algorithme est terminée.
Si la réponse est positive, l'étape E501 est suivie de l'étape E502 qui est un test pour déterminer si la station considérée est destinataire du message spécifique de routage. Cette indication est incluse dans le message spécifique de routage, lorsqu'il est émis en point à point. Lorsque le message spécifique de routage est émis en diffusion, il contient une adresse de diffusion, dite "adresse broadcast". Dans ce cas, la station considérée est destinataire du message spécifique de routage. Du point de vue de la station considérée, il y a équivalence entre les deux cas.
Si la réponse est négative à l'étape E502, l'exécution de l'algorithme est terminée.
Si la réponse est positive, l'étape E502 est suivie de l'étape E503 à laquelle la station analyse le message spécifique de routage et modifie sa table de routage en conséquence. La modification de la table de routage a pour résultat de modifier les chemins utilisés pour acheminer les messages ultérieurs.
Dans le cas où la station reçoit plusieurs messages spécifiques de routage provenant de plusieurs stations mobiles, la station mobile compare ces messages pour déterminer quelle station intermédiaire fou mit un chemin vers la destination finale avec le coût le plus faible, ou en variante quelle station intermédiaire a le plus de stations voisines. Une combinaison de ces critères peut aussi être prise en compte. La prise en compte du nombre de stations voisines nécessite la transmission de la table de routage en totalité. La station considérée choisit alors l'une des stations et modifie sa table de routage en conséquence.
Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, toute variante à la portée de l'homme du métier.
Notamment, I'invention s'applique à tout type de réseau distribué comportant des stations mobiles. A titre d'exemple, une constellation de satellites en orbite basse (non géostationnaires) peut constituer un tel réseau.
Le routage des communications entre ces satellites peut être analysé par la présente invention de manière à détecter des ruptures de lien et transmettre l'information correspondante.
Claims (11)
1. Procédé de routage de message entre des stations (SMa-SMe) d'un réseau, chaque station ayant en mémoire une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message respectivement associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisé en ce qu'une station considérée quelconque effectue les opérations suivantes lorsqu'elle reçoit un message de données:
- mémorisation (E402, E405), dans une seconde table respective, de données concernant le message et comportant au moins un identificateur (ID,
SEI) de message, un identificateur (SET) de station émettrice intermédiaire, un identificateur (SDT) de station destinataire intermédiaire, un identificateur (SDF) de station destinataire finale et un nombre (NR) de retransmission du message,
et, si le nombre de retransmission du message atteint une valeur prédéterminée, si la station considérée n'est pas la station destinataire intermédiaire et si la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- émission (E413) d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
2. Procédé selon la revendication 1, caractérisé en ce que le message spécifique de routage comporte au moins l'adresse de la station considérée, l'adresse (SDF) de la station destinataire finale dudit message, et un coût (CT) de transmission entre la station considérée et la station destinataire finale dudit message.
3. Procédé selon la revendication 1, caractérisé en ce que le message spécifique contient la première table de la station considérée.
4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que l'identificateur de message comporte l'adresse (SEI) de la station émettrice initiale du premier d'un ensemble de messages précédents ayant le même identificateur de message que ledit message.
5. Procédé de routage de message entre des stations d'un réseau, chaque station ayant en mémoire une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message respectivement associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisé en ce qu'une station considérée quelconque effectue les opérations suivantes, lorsqu'elle reçoit un message spécifique de routage indiquant l'existence d'un chemin entre deux stations
- recherche (E502) si la station considérée est destinataire du message spécifique de routage, et, en cas de réponse positive,
- modification (E503) de la première table de la station considérée en fonction du message spécifique de routage.
6. Station de communication d'un réseau, comportant une mémoire (20) pour mémoriser une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message respectivement associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisée en ce qu'elle comporte:
- des moyens (20) de mémorisation, dans une seconde table respective, de données concernant chaque message de données qu'elle reçoit, ces données comportant au moins un identificateur (ID, SEI) de message, un identificateur (SET) de station émettrice intermédiaire, un identificateur (SDT) de station destinataire intermédiaire, un identificateur (SDF) de station destinataire finale et un nombre (NR) de retransmission du message,
- des moyens (10) de vérification que le nombre (NR) de retransmission du message atteint une valeur prédéterminée, que la station considérée n'est pas la station destinataire intermédiaire et que la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- des moyens (10, 50) d'émission d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
7. Station de communication d'un réseau, comportant une mémoire (20) pour mémoriser une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message respectivement associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisée en ce qu'elle est adaptée à coopérer avec:
- des moyens (20) de mémorisation, dans une seconde table respective, de données concemant chaque message de données qu'elle reçoit, ces données comportant au moins un identificateur (ID, SEI) de message, un identificateur (SET) de station émettrice intermédiaire, un identificateur (SDT) de station destinataire intermédiaire, un identificateur (SDF) de station destinataire finale et un nombre (NR) de retransmission du message,
- des moyens (10) de vérification que le nombre de retransmission du message atteint une valeur prédéterminée, que la station considérée n'est pas la station destinataire intermédiaire et que la station considérée a dans sa première table l'identificateur de station destinataire finale associé à un identificateur de station destinataire intermédiaire différent de celui de la station émettrice intermédiaire,
- des moyens (10, 50) d'émission d'un message spécifique de routage destiné à la station émettrice intermédiaire pour lui indiquer l'existence d'un chemin entre la station considérée et la station destinataire finale.
8. Station selon la revendication 6 ou 7, caractérisé en ce que les moyens d'émission (10, 50) sont adaptés à former le message spécifique de routage de sorte qu'il comporte au moins l'adresse de la station considérée,
L'adresse de la station destinataire finale dudit message, et un coût de transmission entre la station considérée et la station destinataire finale dudit message.
9. Station selon la revendication 6 ou 7, caractérisé en ce que les moyens d'émission (10, 50) sont adaptés à former le message spécifique de routage de sorte qu'il comporte la première table de la station considérée.
10. Station de communication d'un réseau, ayant en mémoire (20) une première table respective contenant des identificateurs (SDF) de stations destinataires finales de message respectivement associés à des identificateurs (SDT) de stations destinataires intermédiaires de message, caractérisée en ce qu'elle comporte:
- des moyens de réception de message spécifique de routage indiquant l'existence d'un chemin entre deux stations,
- des moyens (10) de recherche si la station considérée est destinataire du message spécifique de routage, et
- des moyens (10) de modification de la première table de la station considérée en fonction du message spécifique de routage.
11. Station de communication d'un réseau, ayant en mémoire (20) une première table respective contenant des identificateurs de stations destinataires finales de message respectivement associés à des identificateurs de stations destinataires intermédiaires de message, caractérisée en ce qu'elle est adaptée à coopérer avec:
- des moyens de réception de message spécifique de routage indiquant l'existence d'un chemin entre deux stations,
- des moyens (10) de recherche si la station considérée est destinataire du message spécifique de routage, et
- des moyens (10) de modification de la première table de la station considérée en fonction du message spécifique de routage.
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR9713785A FR2770715A1 (fr) | 1997-11-03 | 1997-11-03 | Detection de rupture de lien dans un reseau distribue |
| EP98402716A EP0913965A1 (fr) | 1997-11-03 | 1998-10-30 | Réduction du trafic de messages dans un réseau distribué |
| US09/184,034 US6459685B1 (en) | 1997-11-03 | 1998-11-02 | Reduction of the message traffic in a distributed network |
| JP31363498A JPH11261599A (ja) | 1997-11-03 | 1998-11-04 | 通信方法及び通信ステーション |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR9713785A FR2770715A1 (fr) | 1997-11-03 | 1997-11-03 | Detection de rupture de lien dans un reseau distribue |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| FR2770715A1 true FR2770715A1 (fr) | 1999-04-30 |
Family
ID=9512965
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| FR9713785A Pending FR2770715A1 (fr) | 1997-11-03 | 1997-11-03 | Detection de rupture de lien dans un reseau distribue |
Country Status (1)
| Country | Link |
|---|---|
| FR (1) | FR2770715A1 (fr) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0481610A2 (fr) * | 1990-10-15 | 1992-04-22 | Digital Equipment Corporation | Méthode et appareil pour le routage de vecteurs de distance dans des liaisons datagrammes point à point |
| WO1997002677A2 (fr) * | 1995-07-03 | 1997-01-23 | Philips Electronics N.V. | Systeme de gestion d'immeubles a l'aide de communication par sauts de paquets |
-
1997
- 1997-11-03 FR FR9713785A patent/FR2770715A1/fr active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0481610A2 (fr) * | 1990-10-15 | 1992-04-22 | Digital Equipment Corporation | Méthode et appareil pour le routage de vecteurs de distance dans des liaisons datagrammes point à point |
| WO1997002677A2 (fr) * | 1995-07-03 | 1997-01-23 | Philips Electronics N.V. | Systeme de gestion d'immeubles a l'aide de communication par sauts de paquets |
Non-Patent Citations (1)
| Title |
|---|
| JUBIN J ET AL: "THE DARPA PACKET RADIO NETWORI PROTOCOLS", PROCEEDINGS OF THE IEEE, vol. 75, no. 1, January 1987 (1987-01-01), pages 21 - 32, XP002061709 * |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CA2712183C (fr) | Architecture de communication ip entre le sol et un vehicule | |
| EP0913965A1 (fr) | Réduction du trafic de messages dans un réseau distribué | |
| FR2929063A1 (fr) | Procede et dispositif d'allocation de chemins de transmission de donnees dans un reseau de communication synchrone, produit programme d'ordinateur et moyen de stockage correspondants | |
| EP3804408A1 (fr) | Procédé de sélection d'une route dans un réseau ad hoc | |
| EP3549352B1 (fr) | Compteur électrique comportant une interface par courants porteurs en ligne et au moins une interface radio fréquence | |
| EP2172074B1 (fr) | Point d'acces et noeud pour controler le routage dans un reseau hybride | |
| EP2158735A1 (fr) | Procédé de communication entre un noeud source et un noeud destinataire, les noeuds appartenant a un réseau véhiculaire | |
| FR2894099A1 (fr) | Procede et dispositif pour la transmission de donnees entre terminaux mobiles communicants. | |
| EP3675435A1 (fr) | Procédé de routage dynamique dans un réseau d'objets connectés | |
| EP3934108B1 (fr) | Procédé de détermination d'un mode de communication entre deux dispositifs voisins d'un réseau | |
| FR2804815A1 (fr) | Procede d'acheminement de messages dans un reseau ad hoc | |
| FR2770715A1 (fr) | Detection de rupture de lien dans un reseau distribue | |
| EP4142244B1 (fr) | Procédé de régulation destiné à résorber un engorgement d'un réseau maillé de communication par courants porteurs en ligne et radio | |
| FR2899416A1 (fr) | Rpocede et dispositif de routage hybride dans un reseau ad hoc. | |
| EP3934114B1 (fr) | Procédé de régulation destine à résorber un engorgement d'un réseau maille de communication par courants porteurs en ligne | |
| FR3091452A1 (fr) | Procédés de traitement de données, dans un réseau ad hoc de radiocommunication, stations mobiles de radiocommunication et programmes d’ordinateur associés | |
| FR2770713A1 (fr) | Detection de chemin dans un reseau distribue | |
| FR2883440A1 (fr) | Procede et equipement pour la transmission de donnees par reseau ad hoc | |
| FR2770714A1 (fr) | Detection de chemin dans un reseau distribue | |
| EP3709185A1 (fr) | Procédé d'optimisation d'échanges de données dans une infrastructure d'objets connectés | |
| FR2818058A1 (fr) | Procede et systeme pour echanger des informations entre une station principale et un cluster de stations mobiles | |
| EP3160188B1 (fr) | Procédé de communication avec calcul de chemin à partir de réseaux élémentaires, programme d'ordinateur, noeud d'interconnexion et poste de radiocommunication associés | |
| FR3109852A1 (fr) | Procede et dispositif de relai d’un message recu d’un premier dispositif par un deuxieme dispositif nœud vers un troisieme dispositif noeud | |
| FR3095914A1 (fr) | Procédé de routage dynamique dans un réseau d’objets connectés | |
| FR2895626A1 (fr) | Routage et optimisation du debit point a point dans un reseau ad hoc multisauts |