Zone Routing Protocol

Un article de ReseauCitoyen.

(Redirigé depuis ZRP)
Jump to: navigation, search


>ReseauCitoyen>AspectsRoutage>

The Zone Routing Protocol (ZRP)

Zygmunt J. Haas / Marc R. Pearlman (Novembre 1997, expiré en mai 1998)
Traduit de l'anglais par Erwan Doceux (juillet 2000) pour l'ESEO

Sommaire

[modifier] Définition : Protocoles proactifs et réactifs

Un protocole est dit proactif lorsqu’il évalue de manière continue les voies de communication (routes) à l’intérieur du réseau ; de la sorte, lorsque des informations ont besoin d’être acheminées, le parcours qu’elles vont suivre est déjà connu à l’avance et la transmission est immédiate. Un protocole réactif en revanche invoque une procédure de détermination de route uniquement sur demande. Ainsi, lorsqu’une voie de communication est nécessaire, une sorte de procédure de recherche globale est utilisée. En général, les protocoles de routage existant peuvent être classés soit proactifs soit réactifs. La famille des protocoles dits " Distance-Vector " sont proactifs. La famille des algorithmes classiques dits " flooding " appartiennent au groupe réactif aussi appelé " on-demand " (sur demande) comme par exemple Johnson et TORA.

L’avantage d’un système proactif est que, lorsqu’une communication est demandée, un laps de temps négligeable s’écoule avant que la route soit déterminée. Dans les protocoles réactifs, parce que les routes ne peuvent pas être disponibles lorsque le datagramme est reçu, le délai nécessaire pour déterminer une route peut être significatif. De plus, la procédure de recherche globale du protocole réactif nécessite un contrôle du trafic important. A cause du long délai et du contrôle de trafic excessif, les protocoles de routage purement réactifs ne peuvent pas être applicables aux communications temps réel. Cependant, un système purement proactif n’est de même pas approprié à un environnement de type réseau ad hoc de par le fait qu’il utilise un grande partie des capacités du réseau pour la gestion des informations de routage. Comme les nœuds d’un réseau ad hoc bougent assez rapidement, et que les changement peuvent être plus fréquent que les demandes d’établissement de route (Route Request), la plupart de ces informations de routage ne sont jamais utilisées ! Cela aboutit à un gaspillage des capacités du réseau sans fil.

Le meilleur compromis est un protocole qui d’un côté utilise une procédure de détermination de route sur demande mais de l’autre un coût de recherche limité.

Le protocole ZRP est un exemple de bon compromis, il s’agit d’un modèle hybride utilisant les caractéristiques proactives ET réactives des réseaux ad hoc.


[modifier] Introduction

Le protocole ZRP est un modèle hybride entre un schéma proactif et un schéma réactif. Le principal problème dans l’élaboration d’un protocole de routage pour réseau ad hoc réside dans le fait que pour déterminer le parcours d’un paquet de données, le nœud source doit au moins connaître les informations permettant d’atteindre ses proches voisins. D’un autre côté, la topologie d’un tel réseau change fréquemment. De plus, comme le nombre de nœuds peut être élevé, le nombre de destinations potentielles peut également l’être, ce qui requiert des échanges de données important et fréquents. Donc la quantité de données de mise à jour du trafic peut être conséquent. Cela est en contradiction avec le fait que toutes les mises à jour dans un réseau interconnecté ad hoc circulent dans l’air et donc sont coûteuses en ressources.

Le protocole ZRP limite la procédure proactive uniquement aux nœuds voisins et d’autre part, la recherche à travers le réseau, bien que de nature globale, est effectuée sélectionnés de manière efficace dans le réseau, contrairement à une recherche sur tout le réseau.

Pour qu’un protocole de routage soit efficace, les changements de topologies du réseau doivent avoir uniquement un impact local. En d’autres mots, la création d’un nouveau lien à un bout de réseau est un événement local important mais pas à répercuter à l’autre bout du réseau. Les protocoles proactifs tendent à étendre de tels changements topologiques sur tout le réseau, incluant de large coûts. ZRP limite la propagation de telles informations au voisinage seulement de l’endroit où a eu lieu la modification de topologie du réseau, ce qui limite les mises à jour.

[modifier] Notions de Zone de routage, de rayon de zone et de Bordercasting

Une zone de routage est définie pour chaque nœud et inclus les terminaux qui sont à une distance minimale en terme de sauts (" hops ")* du nœud en question. Cette distance est donc un nombre, il est représenté par le rayon de zone.

  • (l’éloignement entre nœuds est mesuré non pas de manière géographique mais suivant le nombre de machines qui les séparent)

Voici un exemple de zone de routage (pour le nœud A) de rayon 2 :

         +-----------------------------------------+
         |                       +---+             |
         |            +---+      | F |             |
  +---+  |  +---+ ----| C |------+---+-----+---+   |
  | G |-----| D |     +---+                | E |   |  Zone of node A
  +---+  |  +---+       |        +---+-----+---+   |  of radius=2
         |            +---+------| B |             |
         |            | A |      +---+             |
         |            +---+                        |
         +-----------------------------------------+

On peut noter sur cet exemple que les nœuds B à E appartiennent à la zone de routage de A alors que G en revanche est en dehors de cette zone. On peut aussi noter que E peut être atteint de deux manières à partir de A, une avec une longueur de 2 "hops" et une autre avec une longueur de 3 "hops". A partir du moment où le minimum est inférieur ou égal à 2, E est dans la zone de routage de A.

Les nœuds périphériques sont ceux pour lesquels la distance minimum qui les séparent du nœud considéré est exactement égale au rayon de zone. Donc, sur la figure, les nœuds D, F et E sont des nœuds périphériques.

Bordercasting est un processus d’émission de datagrammes IP (RFC-0791) à partir d’un nœud vers tous ses nœuds périphériques. Bordercasting peut être implémenté soit à travers une émission IP unicast classique soit à travers une émission multicast (Distance Vector Multicast Protocol – RFC 1075). L’approche multicast est évidemment préférable afin de réduire la quantité de trafic dans l’air.


[modifier] Explications du " Zone Routing Protocol " (ZRP)

ZRP est basé sur deux procédures : le protocole de routage intrazone (IARP) et le protocole de routage interzone (IERP). A travers l’utilisation d’IARP, chaque nœud apprend la distance qui le sépare de chaque autre nœud présent dans sa zone de routage. Le protocole IARP réel n’est pas spécifié et peut être implémenté à partir de différents protocoles comme des dérivés de protocoles dits " Distance Vector Protocol " comme AODV par exemple. En fait, différentes portions d’un réseau ad hoc peuvent utiliser des implémentations différente du protocole IARP. Cependant, quelque soit le choix de celui-ci, le protocole nécessite d’être modifié afin de s’assurer que les opérations effectuée par IARP sont restreintes à la zone du nœud en question. En conséquence, malgré le fait que le réseau puisse être relativement étendu, les mises à jour ne sont propagées que localement.


[modifier] Le protocole de routage interzone (IERP)

Alors que IARP permet de trouver des routes à l’intérieur d’une zone, IERP quant à lui est responsable d’établir des liens entre des nœuds dont la distance qui les sépare est supérieure au rayon de zone. IERP s’appui sur les techniques de bordercasting. Cette procédure est possible si chaque nœud connaît la distance qui le sépare de tous les nœuds de sa zone ainsi que leur identité par l’intermédiaire du protocole IARP. IERP fonctionne comme suit : le nœud source vérifie d’abord que le destinataire se trouve dans sa zone (encore une fois, cela n’est possible que si chaque nœud connaît le contenu de sa zone). Si c’est le cas, le chemin vers la destination est déjà connu et aucun processus d’établissement de connexion n’est nécessaire. En revanche, si ce n’est pas le cas, la source émet une demande d’établissement de route à tous les nœuds périphériques (il s’agit d’un paquet appelé " Route Request "). Maintenant, à leur tour, tous les nœuds périphériques exécutent le même algorithme : ils vérifient si la destination demandée par la source est présente dans leur zone. Si c’est le cas, un signal " Route Reply " est envoyé en retour à la source indiquant le chemin à emprunter pour atteindre la destination. Si ce n’est pas le cas, les nœuds périphériques font suivre la demande à leurs propres nœuds périphériques qui à leur tour effectuent la même procédure. Exemple d’établissement de route :

                             +---+
                    +---+    | F |
            +---+---| C |----+---+-----+---+    +---+
            | D |   +---+              | E |----| H |
            +---+     |      +---+-----+---+    +---+
                    +---+----| B |                |
                    | A |    +---+-----+---+    +---+
                    +---+              | G |    | I |
                                       +---+    +---+
                                         |
                                       +---+
                              +---+    | J |
                              | C |----+---+----+---+    +---+
                              +---+             | K |----| L |
                                                +---+    +---+

Le nœud A veut envoyer un datagramme à L. Supposons que le rayon de zone soit égal à 2. Etant donné que L n'est pas dans la zone de A qui inclus B, C, D, E, F et G, A doit envoyer un signal bordercast de type "Route Request" vers ces noeuds périphériques, à savoir : D, F, E et G. Chacun de ces noeuds périphériques vérifie que L n'est pas dans sa zone. Si L n'a été trouvé dans aucune de ces zones étendues, les noeuds émettent à leur tour un signal bordercast vers leurs noeuds périphériques. En particulier, G émet vers K, qui réalise que L est dans sa zone et retourne le chemin à parcourir pour atteindre L à partir de A (L-K-G-A).


[modifier] La procédure d'accumulation de route

Le processus par lequelle le noeud qui reçoit une requête connait le chemin de retour vers la source s'appelle la procédure d'accumulation de route. En particulier, cette technique est utilisée par le dernier noeud périphérique de la zone dans laquelle réside le destinataire pour retourner la réponse à la requête du noeud source. Elle est basée sur le fait que chaque noeud qui reçoit la requête et qui la fait suivre inscrit son identificateur dans le paquet dit "de requête". La séquence complète de ces identificateurs représente le chemin de la source jusqu'au noeud courant et de même, le le chemin inverse par déduction.


[modifier] Limiter le flot de requêtes

Il est souhaitable qu'une requête de type "Route Request" se propage loin du noeud source et non pas qu'elle revienne dans une zone qui a déjà été parcourue. Pour aboutir à ce type de propagation du signal de requête, IERP utilise deux mécanismes de prévention de ce genre d'aléa. Le premier tue les processus qui reviennent sur eux-même : cela se produit lorsque l'accumulation de route qui contient tous les identificateurs précédents possède un élément présent à l'intérieur de la zone de routage en cours de scrutation (excepté s'il s'agit du noeud immédiatement précédent). Un mécanisme complémentaire, basé sur l'écoute passive des paquets, est utilisé pour réduire l'émission de paquets redondants. Lorsqu'un terminal reçoit une "Route Request", IERP enregistre l'identificateur de l'hôte dans sa liste*. Si le noeud reçoit "officiellement" une requête qui a déjà été formulée auparavant, celle-ci est ignorée. Sans ces mesures, la transmission bordercast innonderait l'environnement.

  • L'écoute passive par les noeuds est uniquement autorisée en période de requête de route ("route request") et ils doivent l'indiquer dans leur liste de requête ("processed request list"); ils n'ont alors plus le droit de traiter la requête.


[modifier] Notifications d'erreur de route

IERP dispose également d'un mécanisme de réponse réactive aux erreurs de route. Une erreur de route est générée par IP lorsque le terminal qui suit ("next hop") est déterminé comme inaccessible (c'est-à-dire qu'il n'apparait plus dans la table de routage intrazone). A partir d'une erreur de route, IERP est alerté et un paquet d'erreur de route est généré ("route failure")**. Ce paquet se propage en direction de la source comme un paquet de réponse ("route reply"). Lorsqu'une notification d'erreur est émise, la voie de communication ayant expirée est retirée de la table de routage interzone. IERP peut aussi être configuré pour réparer locallement la route interzone endommagée en initialisant une nouvelle procédure d'établissement de route vers le noeud inaccessible.

    • ICMP fournit un service similaire à la notification d'erreur de route. Toutefois, les services de IERP fournissent un diagnostique d'information complémentaire, autorisant la source à répondre à l'erreur de manière plus efficace.


[modifier] Limiter le flot de requêtes

Le protocole de résolution bordercast (BRP) est inclus avec IERP efin de fournir des services dits "bordercasting" qui n'existent pas dans IP. Dans la version actuelle de BRP, le contenu d'un message bordercast est considéré comme accessible par n'importe quel noeud qui reçoit le paquet. Les prochaines versions de BRP seront améliorer de manière semi-privée de telle sorte que ces messages seront délivrés aux couches supérieures (noeuds périphériques) uniquement.


[modifier] L'architecture ZRP

+---------+    :    +---------+         +---------+    :    +---------+
|   NDM   |====:===>|  IARP   |========>|  IERP   |<===:====|  ICMP   |
+---------+    :    +---------+         +---------+    :    +---------+
    /|\        :        /|\             |   BRP   |    :        /|\
     |         :         |              +---------+    :         |
     |         :         |                  /|\        :         |
     |         :.......................................:         |
     |                   |                   |                   |
    \|/                 \|/                 \|/                 \|/
+---------+---------+---------+---------+---------+---------+---------+
|                               IP                                    |
+---------+---------+---------+---------+---------+---------+---------+

Legend:

       A<--->B      échanges de paquets entre les protocoles A & B
       A====>B      passage d'informations du protocole A au protocole B
       Existing Protocols
       ------------------
               IP              Internet Protocol
               ICMP            Internet Control Message Protocol
       ZRP Entities
       ------------
               IARP            IntrAzone Routing Protocol
               IERP            IntErzone Routing Protocol
               BRP             Bordercast Resolution Protocol
       Additional Protocols
       --------------------
               NDM             Neighbor Discovery/Maintenance Protocol


[modifier] Le protocole de routage IARP

Bien que IARP peut être implémenté par des protocoles proactifs variés, nous présentons ici un exemple d'implémentation basé sur une version modifiée de l'algorithme "Distance Vector" qui restreint les opérations sur une zone apr l'intermédiaire du rayon de zone. Un terminal peut recevoir de nouvelles informations sur la topologie soit en provenance d'un paquet IARP soit d'une interruption généré par ses voisins ("Maintenance Process" : NDM)*. Dans le cas particulier où un hôte a découvert un nouveau voisin, IARP est responsable d'envoyer à ce nouvel arrivant la route la plus courte vers tous les noeuds présents à la fois dans les deux zones de routage. Le terminal enregistre ensuite les nouvelles données dans sa table de routage intrazone. Si le chemin le plus court vers un hôte a changé, le terminal broadcast un paquet IARP pour répercuter le changement.

  • IARP dépend des services d'un protocole distinct (référencé ici comme le "Neighbour Discovery/Maintenance Protocol) en vue de fournir des informations concernant les voisins de l'hôte. Au minimum, cette information contient l'adresse IP de tous les voisins. IARP peut être configuré pour supporter des informations complémentaires sur les voisins, comme le coût d'une liaison.


[modifier] Le protocole de routage IERP (suite...)

On rappelle que IERP est respondable de la gestion des hôtes qui sont présents au-delà de la zone de routage. IERP collecte des informations de routage de façon réactive grâce aux requêtes bordercast qui contiennent les accumulations de routes depuis la source. Quand IP reçoit un paquet de données destiné à une destination inconnue (c'est-à-dire que celle-ci n'est répertoriée ni dans la table de routage interzone ni dans la table de routage intrazone), IERP est interrompu. Il répond alors en initialisant une recherche de solution ("route discovery") et bordercast une requête de route. Chaque requête sur le réseau identifiée de manière unique par l'adresse IP de la source et l'identifiant de requête (local sur la source). Après réception d'un paquet de type "Route Request", l'hôte effectue une recherche dans sa table de routage intrazone si le destinataire appartient à sa zone de routage. Si c'est le cas, le terminal répond avec un message "Route Reply" qu'il renvoie à la source grâce la route accumulée. Si la destination ne se trouve pas dans la table de routage intrazone, le l'hôte ajoute son identificateur de terminal dans la route accumulée et bordercast cette requête.


[modifier] Le protocole de résolution bordercast (BRP)

L'interface de la couche supérieure de BRP est implémenté pour être compatible avec n'importe quelle application basée sur IP. Toutefois, nous supposons que la hiérarchie de la zone de routage est visible uniquement par les entités du protocole ZRP. Après réception d'un paquet IERP, BRP translate l'adresse de bordercast vers les adresses IP individuelles des noeuds périphériques. Le paquet reçu est encapsulé et envoyé à chacun de ces noeuds périphériques (via "IP broadcast transmission"). Quand un paquet BRP est délivré par IP, la donnée IERP est "désencapsulée" et transmise aux couches supérieures. Si le paquet BRP n'a pas atteint sa destination, BRP est responsable de faire suivre les paquets au noeud suivant vers sa destination.


[modifier] Autre considération : déterminer la taille du rayon de zone

La valeur du rayon de zone détermine la performance du protocole ZRP. En général, les réseaux mobiles doivent fixer cette variable à la valeur la plus petite possible, alors que pour un réseau fixe, elle prendra une valeur plus grande. De même, dans des réseaux très actifs (requêtes fréquentes), le rayon de zone doit être plus grand contrairement aux réseaux moins actifs. Nous croyons que fixer la taille d'une telle variable doit être laissé aux soins de l'administration du réseau, s'il en existe une, ou par le fabricant comme une valeur par défaut. Bien que certaines valeurs de cette variable peuvent être données comme optimales, des contraintes peuvent venir s'ajouter ainsi que certaines conditions qui pourraient affecter the choix.

[modifier] ToutSurZrp

[modifier] Sources

http://www.guill.net/index.php?cat=3&pro=6&oth=2 Zygmunt J. Haas / Marc R. Pearlman (Novembre 1997, expiré en mai 1998) Traduit de l'anglais par Erwan Doceux (juillet 2000) pour l'ESEO