ZRP is a hybrid protocol. This protocol divides the network into non-overlapping routing zones and runs independent protocols that study within and between the zones.
Intra-zone protocol (IARP) operates within a zone and learns all the possible routes, proactively. So, all nodes within a zone knows about its zone topology very well. Inter-zone protocol (IERP) is reactive and a source node finds a destination node which is not located within the same zone, by sending RREQ messages to all border nodes. This continues until destination is found.
Routing zone diameter is variable and this should be chosen optimal for a scaled topology. By zoning, control message overhead is attempted to be lowered. Current zone size estimation techniques allow ZRP to operate within 2 percent of the control traffic from optimal value.
Il n'existe que deux façons pour gérer dynamiquement les routes : proactive ou réactive.
Un protocole proactif évalue de manière continue les routes à l'intérieur du réseau. Lorsqu'un paquet doit transiter, la route est déjà connue et la transmission est immédiate. Un protocole réactif détermine la route uniquement sur demande. La recherche sera globale.
L'avantage d'un protocole de routage proactif est le gain de temps lorsqu'une route est demandée. Le problème c'est que dans le réseau AdHoc, les changements de routes peuvent être plus fréquents que la demande de route. D'ailleurs, la plupart des informations ne sont jamais utilisées, ce qui gaspille de capacités du réseau sans fil.
Inversément, l'avantage d'un protocole réactif est de ne pas gaspiller ces ressouces. Par contre, ses retards dépassent bien souvent les délais moyens admis par les logiciels, aboutissant à une impossibilité de se connecter alors que le destinataire est bien là. Et surtout, il saturera le réseau rapidement à cause de sa technique de flood.
C'est là que ZRP intervient : C'est un protocole qui se veut comme une solution mettant en commun les avantages des deux approches distinctes en utilisant une notion de découpe du réseau. Dans cette implémentation, le routage entre les noeuds proches (IARP) se fait par le protocole proactif AODV. Le routage plus distant (IERP) se fait par le protocole réactif OLSR. Un troisième protocole, interne à ZRP, sert à la définir la frontière des zones: c'est BRP.
Autrement dit, ZRP utilise une procédure de détermination de route pour les noeuds proches et une procédure de recherche limitée pour les noeuds distants.
Ainsi, lors du changement du topologie du réseau, ZRP limite la propagation des informations au voisinage seulement. C'est de là que vient toute son efficacité.
Dans le protocole ZRP, le mot « /routing zone/ » (zone de routage) définit la zone autour du noeud X avec un certain nombre de sauts (hops).
Par exemple, pour un rayon de zone égal à 2, la zone de routage du noeud Y est tous les noeuds qui sont autour du noeud Y avec un maximum de hop de 2. Donc, tous les voisins du noeud Y ainsi que tous les voisins de ces voisins font partie de la zone de routage du noeud Y.
Le rayon de zone est le nombre de sauts : nombre de machines qui séparent une machine d'une autre.
Bordercasting est un processus d'émission de paquets IP à partir
d'un noeud vers tous les noeuds periphériques. Il peut être implémenté
soit à travers une émission IP unicast soit multicast.
Il est basé sur deux procédures :IARP et IERP (protocole de routage intrazone et interzone).
A travers l'IARP chaque noeud apprend la distance qui le sépare de chaque autre noeud présent dans sa zone.Le protocole peut être implémenté à partir d'autres protocoles dérivés comme AODV etc.
Et l'IERP quant à ce protocole, établit des liens entre noeuds dont la distance est > au rayon de la zone. Il s'appuie sur la technique de bordercasting.
ZRP est un protocole de routage dit hybride, il met en place simultanément un routage proactif et un routage réactif afin de combler les problèmes spécifiques à ces deux types de routage. Pour se faire il passe par une notion de zone. Une zone regroupe l'ensemble des noeuds se trouvant à une distance maximum de X hops du noeud de référence. Le routage au sein d'une zone se fait de manière proactive à l'aide d'un protocole à état des liens, le routage vers des noeuds extérieurs à cette zone se faisant de façon réactive. L'architecture de ZRP est basée sur une simple constatation :
Un événement proche est plus important qu'un événement lointain
En suivant cette façon d'aborder le problème, nous devrons donc accorder plus d'importance au routage vis à vis des noeuds les plus proches. Il faudra cependant déterminer une taille de zone adaptée afin de trouver le bon équilibre entre le routage proactif et le routage réactif, cette valeur dépendant directement du réseau lui même.Une zone peut être vue comme un sous ensemble du réseau, c'est ensemble de noeud se trouvant à une distance maximale du noeud source, cette distance étant comptée en nombre de hop sur le chemin le plus cours menant à ce noeud. Nous appellerons cette distance le zone radius. Ces zones serviront de frontière entre le routage proactif et réactif. IARP nous fournira le routage au sein de la zone de façon proactive, notre noeud central n'échangera d'informations de routage que pour établir la route au sein de cette zone, toute information sur le reste du réseau ne lui parvenant pas car le TTL est initialisé au zone radius - 1 dans le paquet IP.
L'ensemble des noeuds périphériques de la zone (les noeuds se trouvant à une distance au minimum égale au zone radius) serviront quant à eux de points de recherche pour IERP qui exercera ainsi une recherche par zone.
Il faudra également noter que la notion de zone est locale et unique au noeud, chaque noeud dispose de sa vision de sa zone et ignore tout des autres zones.
La détection des voisins se fait par consultation des couches inférieures. ZRP se contente de récupérer la table de voisinage que lui fournit un agent extérieur de recherche du voisinage. Cette table sera utilisée par IARP pour construire le plan du réseau. Chaque modification de cette table de voisinage devra donner suite à une mise à jour du plan de la zone par IARP ainsi qu'à une mise à jour des tables de routage par IERP.
La détection des voisins pourrait être basée sur des critères plus complexes, il pourrait être envisageable d'y faire un tri en supprimant par exemple les noeuds dont la force d'émission est trop faible, les noeuds qui seraient ignorés par NDP ne seraient cependant pas ignorés, seul le lien direct qui nous parait peut fiable est refusé, ce noeud pourra toujours être atteint par un routage passant par IARP ou IERP.
Le routage intrazone de ZRP se fait par l'intermédiaire d'un
protocole proactif à état des liens. Cependant, pour
diminuer la charge du réseau, la portée de ce protocole
est limitée par la taille de la zone ZRP. Chaque noeud
construira donc une carte de sa zone et pourra ainsi adapter ses routes
en temps réel si un lien venait à disparaître
(Cette correction locale de certaines pertes de lien permettent de
limiter les recherches par inondation). La façon dont la table
de routage sera générée dépendra du
protocole à état des liens que nous adapterons au
fonctionnement d'IARP. IARP permet d'intégrer d'autres
propriétés selon le protocole qui lui est
appliqué, il pourra en reprendre toutes les
caractéristiques à condition que celles si ne rentrent
pas en conflit avec le comportement général d'IARP. Il
faudra cependant noter que certaines de ces propriétés
pourraient n'être supportées qu'en intrazone si IERP
n'offre pas la possibilité d'exploiter ces
propriétés. Certaines modifications seront cependant
nécessaire à l'adaptation des protocole
s à état des liens existants pour les rendre compatibles
avec IARP.
Le routage interzone de ZRP se fait par un protocole de routage réactif. Ce protocole recherchera un lien entre le noeud source et un noeud qui dispose du noeud destination de la requête dans sa zone. Cette recherche se fera par inondation contrôlée du réseau. Afin de contrôler les flux de messages, chaque message IERP se verra attribuer un identifiant unique pour l'ordinateur source (en se basant sur la combinaison adresse/identifiant de requête, nous pourrons reconnaître tout message sans risque de confusion). Chaque noeud tiendra un historique des requêtes déjà traitées et ne tiendra pas compte des allusions suivantes à ces requêtes. Le contrôle de l'inondation ne revient cependant pas complètement à IERP, il nous faudra passer par le protocole BRP afin de limiter les répétitions inutiles sur le réseau et tirer tout l'avantage de nos zones. Les propriétés plus spécifiques qui peuvent êtres apportés à IERP dépendront du protocole qui lui est appliqué. Les propriétés exploitables seront cependant limitées par les possibilités offertes par notre implémentation de IARP (par exemple, la gestion de lien unidirectionnel par IERP ne servirait à rien si ces liens sont considérés comme inexistant par IARP).
IERP peut être adapté à l'utilisation de n'importe quel protocole de routage réactif existant, il nécessitera cependant quelques adaptations.
La notion de zone nous permet de contrôler plus précisément l'inondation du réseau, il est en effet inutile d'interroger tous les noeuds quand on sait que chaque noeud connaît l'ensemble de ses voisins. Ce protocole nous propose 3 mécanismes de contrôle du trafic afin de limiter l'utilisation de notre bande passante.
Sachant que notre noeud connaît toutes les routes existantes sur une distance de X hops, nous pouvons supposer qu'il est inutile d'interroger l'ensemble des noeuds de la zone, nous pouvons nous contenter d'interroger les noeuds frontaliers de nos zones de routage. Nous allons donc pouvoir remplacer l'utilisation du broadcast au sein d'IERP par des messages à destination des noeuds périphériques non couverts, nous parlerons de bordercast.
BRP utilisant des mécanismes d'inondation, il devra s'assurer de ne pas créer de tempête de broadcast. Afin d'éviter qu'un message ne revienne en boucle, chaque message BRP sera identifié de façon unique. Nous les identifierons par un numéro de séquence ainsi que l'adresse de son noeud d'origine. Chaque noeud du réseau recevant un message BRP ayant un identifiant déjà traité l'ignorera, nous parlerons de Loopback Termination. Ce mécanisme est celui utilisé par l'ensemble des protocoles basés sur une inondation.
Afin de limiter un maximum les retransmission dans des zones du réseau déjà parcourues, les noeuds ne devront pas seulement vérifier s'ils ont répondu à une requête, mais également si aucun noeud ne l'a fait à sa place. Pour cela, nous allons devoir utiliser des mécanismes de Query Detection, cela peut se faire à deux niveaux différents, à un premier niveau (QD1) les noeuds retiennent les identifiant des paquets qu'ils ont transmis à d'autres noeuds même s'ils ne les ont pas traités eux mêmes car le paquet ne leur était pas directement adressé. Ce mécanisme nécessite cependant que le transfert des paquets BRP soit géré par BRP et non par les couches inférieures et que le noeud intermédiaire ait accès au contenu du paquet (Les données ne peuvent donc êtres cryptées).
Un second niveau de détection (QD2) peut être ajouté par écoute du support par l'ensemble des noeuds et par marquage de tout les paquets BRP qui passent mêmes si ils ne nous concernent pas. Cette détection n'est cependant possible que si les différents noeuds sont sur le même canal de communication.
Quel que soit le niveau de détection effectué, la zone du noeud d'origine de la requête sera marquée comme entièrement couverte suite à une détection.
Afin de rentabiliser les gains apportés par le Query Detection au maximum, il ne faut pas seulement contrôler nos propres paquets, mais également ceux que nous devons relayer. Nous devrons donc évaluer quels noeuds ont déjà été couverts par l'inondation afin de ne pas retransmettre le paquet vers ces noeuds. Seront considérés comme couverts tous les noeuds présent dans la zone du noeud d'origine de la requête bordercast. Ces noeuds auront en effet déjà été traités dans la recherche du noeud précédent. Il serait donc inutile de retransmettre une seconde fois la requête dans cette zone. La retransmission du paquet sera interrompue, nous parlerons d'Early Termination. Ce mécanisme devra être appliqué autant pour les noeuds sources, destinations et intermédiaires. Il est donc tout à fait envisageable que la transmission d'un paquet soit interrompue de cette manière entre la source et la destination.
Lors de la réception d'un paquet, l'attente d'un léger délai aléatoire nous permettrait également de diminuer le besoin de répétition. En attendant, nous pourrions recevoir à nouveau la requête par un autre noeud. Cela nous permet de ne pas retransmettre un message qui serait répété par notre voisin. Le délai étant aléatoire, il devient moins probable que deux noeuds devant transmettre un message le fassent en même temps. Cette attente nous permet de nous faire une meilleure idée des retransmissions réellement nécessaires. Nous aurons plus d'occasions de marquer la zone comme couverte.
ZRP a été pensé pour tourner sur la couche IP et en se basant sur une aide extérieure pour la détection des voisins, ce n'est pas directement ZRP lui-même qui communique sur le réseau, mais ses différents composants qui communiquent par eux même. C'est IERP qui s'occupera de la mise à jour des tables de routage à partir de ses propres recherches et des routes qui lui ont été importées par IARP.
Les droits d'auteurs sont détenus par Jean-Charles de Longueville, Kamil turut, Sébastien Jardon, Kim de Biber et Hellea sprl.
Ce site incarne la primo-publication de l'implentation du protole de routage ZRP définit par le MANET selon les documents publiés ici.
Le code publié ici est accompagné de la license de rediffusion GPL(v2).
Ce développement fut proposé par Hellea sprl à l'ESI comme sujet de travail de fin d'études pour un de leurs étudiants. Deux ce sont déjà succédé en provenance de l'ESI. Un toisième continua venant de Liège. Nous attendons un quatrième étudiant pour 2005...
