Le routage OLSR et l’attaque du trou noir: Analyse & Détection

Table des matières

Liste des figures

Liste des tableaux

Introduction générale

1 Les réseaux sans fil et les réseaux ad hoc
1.1 Bref historique des télécommunications
1.1.1 La première transmission aérienne « moderne »
1.1.2 Le fil comme support de communication
1.1.3 La communication sans fil
1.2 Introduction aux réseaux sans fil
1.2.1 Les normes des réseaux sans fil
1.2.1.1 IEEE 802.11
1.2.1.1.1 IEEE 802.11a
1.2.1.1.2 IEEE 802.11b
1.2.1.1.3 IEEE 802.11g
1.2.1.2 HiperLAN
1.2.1.3 Bluetooth
1.2.2 Architecture
1.2.2.1 Le mode BSS (Basic Service Set)
1.2.2.2 Le mode IBSS (Independent Basic Service Set)
1.3 Les réseaux ad hoc
1.3.1 Définition 1
1.3.2 Définition 2
1.3.3 Propriétés et spécificités des réseaux ad hoc
1.3.3.1 L’absence d’une infrastructure centralisée
1.3.3.2 La mobilité des nœuds et maintenance des routes
1.3.3.3 L’hétérogénéité des nœuds
1.3.3.4 La contrainte d’énergie
1.3.3.5 La taille des réseaux ad hoc
1.3.3.6 Vulnérabilité
1.3.4 Domaines d’applications
1.4 Conclusion

2 Etat de l’art des protocoles de routage dans MANET
2.1 Routage hiérarchique ou plat
2.2 Etat de liens ou vecteur de distance
2.3 Les différentes familles de protocoles de routage dans MANET
2.3.1 Les protocoles proactifs
2.3.1.1 DSDV (Destination Sequenced Distance Vector)
2.3.1.2 FSR (Fisheye State Routing)
2.3.1.3 TBRPF (Topology Broadcast Based on Reverse - Path For- warding)
2.3.2 Les protocoles réactifs
2.3.2.1 AODV (Ad hoc On - demand Distance Vector)
2.3.2.2 DSR (Dynamic Source Routing)
2.3.3 Les protocoles hybrides
2.3.3.1 ZRP (Zone Routing Protocol)
2.3.3.2 CBRP (Cluster Based Routing Protocol)
2.3.4 Les protocoles géographiques
2.3.4.1 DREAM (Distance Routing Effect Algorithm for Mobility) .
2.3.4.2 LAR (Location Aided Routing protocol)
2.3.4.3 ZHLS (Zone-Based Hierarchical Link State Routing) . .
2.4 la conception des stratégies de routage
2.5 Conclusion

3 La sécurité dans les réseaux ad hoc : Défis & Solutions
3.1 Introduction
3.2 Les exigences de sécurité
3.2.1 La disponibilité (Availability)
3.2.2 L’authenticité (Authenticity)
3.2.3 La confidentialité (Confidentiality)
3.2.4 Non-répudiation (Non-repudiation)
3.2.5 Anonymat (Anonymity)
3.2.6 Contrôle d’accès (access control)
3.2.7 L’intégrité (Integrity)
3.3 Les problèmes de sécurité pour les protocoles de routage Ad hoc existants
3.3.1 La Révélation d’endroit (Location Disclosure)
3.3.2 Le Trou Noir (Black Hole)
3.3.3 Rejoue (Replay)
3.3.4 Trou de ver (Wormhole)
3.3.5 Déni de service (Denial of Service)
3.3.6 Consommation de ressources (Sleep deprivation torture)
3.3.7 Débordement de la table de routage (Routing table overflow)
3.3.8 Usurpation d’identité (Impersonation)
3.3.9 Attaque de Sybil
3.3.10 Rushing attack
3.4 Approches de protection du MANET
3.5 Etat de l’Art des solutions de sécurité pour MANET
3.5.1 La sécurité de la couche réseau
3.5.1.1 Primitives d’authentification de message
3.5.1.1.1 HMAC (message authentication codes)
3.5.1.1.2 La signature numérique (Digital signature)
3.5.1.1.3 One - way HMAC Key chain
3.5.1.2 La sécurisation du routage Ad Hoc
3.5.1.2.1 Le routage par la source
3.5.1.2.2 Le routage à vecteur de distance
3.5.1.2.3 Le routage à état de lien
3.5.1.3 La sécurisation de l’expédition de paquets
3.5.1.3.1 Détection
3.5.1.3.2 Détection localisée
3.5.1.3.3 Détection basée sur l’acquittement (ACK_based de- tection)
3.5.1.3.4 Réaction (reaction)
3.5.2 La sécurité de la couche liaison
3.5.2.1 IEEE 802.11 MAC (Medium Access Control)
3.5.2.2 IEEE 802.11 WEP (Wireless Equivalent Privacy) . .
3.6 Quelques Travaux effectués
3.6.1 Watchdog & Pathrater
3.6.1.1 watchdog
3.6.1.2 Pathrater
3.6.2 SRP (Secure Routing Protocol)
3.6.3 CONFIDANT(Cooperation Of Nodes : Fairness In Dynamic Ad hoc NeTworks )
3.6.4 WATCHERS
3.6.5 SAODV( Secure Ad hoc On - demand Distance Vector)
3.6.6 ARAN (Authenticated Routing for Ad hoc Networks)
3.7 Conclusion

4 Le protocole OLSR : attaques & solutions
4.1 OLSR ( Optimized Link State Routing )
4.1.1 Le format du paquet OLSR
4.1.2 Découverte de voisinage
4.1.3 Principe des relais multipoints
4.1.4 Les messages TC (Topology Control)
4.1.5 les messages MID (Multiple Interface Declaration)
4.1.6 les messages HNA ( Host and Network Association ) . .
4.2 Attaques contre le protocole OLSR
4.2.1 Génération incorrecte des messages de contrôle
4.2.1.1 Usurpation d’identité dans le message HELLO .
4.2.1.2 Link spoofing dans le message HELLO
4.2.1.3 Usurpation d’identité (identity spoofing) dans le message TC
4.2.1.4 Link spoofing dans le message TC
4.2.2 Relayage incorrect du trafic
4.2.2.1 L’attaque du trou noir (Black hole attack)
4.2.2.2 L’attaque du trou de ver (Wormhole attack) . .
4.2.2.3 L’attaque MPR (MPR attack)
4.3 Les solutions proposées pour sécuriser OLSR
4.4 Conclusion

5 Contribution & Simulation
5.1 Attaque menée par un seul nœud
5.1.1 Supprimer les paquets TC
5.1.2 Falsifier le type de lien entre deux voisins
5.1.2.1 Description de l’attaque
5.1.2.2 La solution proposée
5.2 Attaque menée par deux nœuds
5.2.1 Description de l’attaque
5.2.2 La solution proposée
5.2.3 Simulation
5.2.3.1 Configuration de simulation
5.2.3.2 Résultats de simulation
5.3 Conclusion

Conclusion et Perspectives

Bibliographie

Liste des figures

1.1 Le télégraphe de Chappe
1.2 Le modèle de réseaux sans fil en mode BSS (avec infrastructure)
1.3 Le mode IBSS (sans infrastructure)
1.4 Un exemple de transmission d’un message entre noeuds dans un réseau ad hoc
1.5 Exemple d’application des réseaux Ad hoc

2.1 Routage « à plat »
2.2 Routage hiérarchique
2.3 Recherche de route par un protocole réactif

3.1 Les composants de la solution de sécurité
3.2 Génération des clés TESLA
3.3 Collision ambiguë au niveau du watchdog
3.4 Collision au niveau du récepteur

4.1 Le format du paquet dans OLSR
4.2 Diffusion par inondation
4.3 Diffusion par MPR
4.4 Le nœud D usurpe l’identité du nœud C dans son message HELLO
4.5 Le nœud D usurpe l’identité du nœud A dans son message TC
4.6 Le nœud P supprime ses MPR selectors ( les nœuds C et D )
4.7 Un trou de ver créé par le nœud X
4.8 Un plus long trou de ver créé par deux intrus s’entendants X et X’
4.9 Le noeud X lance une attaque MPR

5.1 Trou noir créé par le nœud E
5.2 M fait croire à I et J qu’ils ont un lien symétrique entre eux
5.3 Schema illustratif 1
5.4 Schema illustratif 2
5.5 Deux noeuds collaborent pour créer un trou noir dans le réseau . .
5.6 Le format du message TC avec l’extension de sécurité
5.7 Description du mécanisme d’acquittement
5.8 Nombre total des messages TC relayés avec la présence des attaquants et sans attaquants
5.9 Nombre total des messages TC reçus avec la présence des attaquants et sans attaquants
5.10 Comparaison du nombre moyen des messages TC relayés par les MPRs
5.11 Comparaison du nombre moyen des messages TC reçus par les nœuds
5.12 TC relayés par rapport au temps de pause des nœuds
5.13 TC reçus par rapport au temps de pause des nœuds
5.14 L’overhead des messages de contrôle par rapport au temps de pause des nœuds

Liste des tableaux

3.1 Les solutions de sécurité pour MANETs devraient assurer la protection complète enjambant la pile entière du protocole¹⁰¹
3.2 Mécanisme de découverte de route dans Ariadne
3.3 La défense contre les attaques

5.1 Une entrée dans la table de routage du nœud I
5.2 Une entrée dans la table de routage du nœud A
5.3 Comparaison du nombre de paquets de contrôle introduits avec le nombre total des paquets de contrôle

Introduction générale

L’INTERNET est un environnement distribué, c’est-à-dire qu’il ne dépend pas d’une entité centrale. Les liens existants entre les nœuds de ce réseau permettent d’utiliser différents chemins pour arriver à destination. Ainsi, en cas de rupture d’une liaison, un ordinateur peut échanger des informations avec un autre sans nécessairement devoir passer par les mêmes chemins. Cette architecture est l’une des clés du succès d’Internet car elle donne un système robuste et une forme d’égalité entre participants. D’ailleurs, l’une des applications les plus populaires sur Internet est tous les programmes appelés communément P2P, (d’égal à égal ou peer-to-peer) qui permettent à chacun de communiquer et d’échanger des informations sans recours aux instances dirigeantes pour la recherche d’informations.

Dans les réseaux sans fil, on retrouve de façon élargie cette notion d’universalité : chaque personne à portée radio d’un nœud peut écouter ses communications. Ce système peut donc être considéré comme un système démocratique, permettant à chacun de participer. Mais, à l’opposé d’Internet, une grande majorité des produits « radio »fonctionne de manière hiérarchique et centralisée. Le système GSM par exemple, oblige chaque téléphone portable à être à portée de communication d’une base reliée au réseau téléphonique. Il existe donc un contrôle, une mécanique sous-jacente structurant l’ensemble des communications.

Pourtant, il est possible d’envisager un réseau sans fil universel où chaque mobile participerait aux communications. Si la couverture du réseau est suffisante (c’est-à-dire qu’il existe assez de nœuds pour un espace donné), chacun peut joindre un autre, soit s’il est à portée radio, soit en utilisant des nœuds situés entre eux deux pour relayer leurs messages. Ce contexte est connu sous le nom du réseau ad hoc.

Les réseaux ad hoc sont idéals pour les applications caractérisées par une absence (ou la non fiabilité) d’une infrastructure préexistante, telles que les applications militaires et les autres applications de tactique comme les opérations de secours (incendies, tremblement de terre...) et les missions d’exploration.

Si l’idée générale d’un réseau ad hoc est triviale, il n’en est pas de même pour la réalisation et le déploiement d’un tel système. Il existe de très nombreux défis à résoudre : trouver le chemin entre deux nœuds ou assurer une bonne stabilité dans les communications entre deux nœuds par exemple. Le problème vient du fait que les nœuds peuvent être mobiles, ce qui entraîne des changements topologiques continuels dans l’état du réseau.

Les réseaux sans fil sont par nature sensibles aux problèmes de sécurité. L’intrusion sur le support de transmission est plus facile que pour les réseaux filaires et il est possible de mener des attaques par déni de service en brouillant les bandes de fréquences utilisées. Le contexte ad hoc augmente le nombre de failles de sécurité potentielles. Etant par définition sans infrastructure, les réseaux ad hoc ne peuvent bénéficier des services de sécurité offerts par des équipements dédiés : pare feux, serveurs d’authentification, etc. Les services de sécurité doivent être distribués, coopératifs et compatibles avec la bande passante disponible. Le routage pose aussi des problèmes spécifiques : chaque nœud du réseau peut servir de relais et a donc la possibilité de capturer ou bien de détourner le trafic en transit. C’est dans ce contexte que se situe le travail que nous allons présenter dans ce mémoire. Le problème auquel nous avons décidé de s’attaquer ici est celui de la sécurisation du protocole de routage OLSR contre l’attaque du trou noir.

Organisation du mémoire

Ce mémoire est consacré à la sécurisation du protocole OLSR contre l’attaque du trou noir. A cet effet, nous l’avons scindé en cinq chapitres :

Le premier chapitre présente les réseaux sans fil, leurs normes principales, l’introduction de la notion de réseaux ad hoc en détaillant leurs caractéristiques principales et leurs domaines d’application.

Le deuxième chapitre fournit une classification des protocoles de routages dans les réseaux ad hoc selon deux critères différents ainsi qu’une présentation des différentes familles des protocoles de routages dans MANETs.

Le troisième chapitre est consacré au problème de sécurité de la fonction de routage dans les réseaux ad hoc. Nous présentons les différentes menaces de sécurité en se focalisant sur les problèmes spécifiques à la couche réseau et la couche liaison avec une présentation des différentes solutions qui ont été proposées dans ce contexte. Le quatrième chapitre sera dédié au protocole OLSR. Nous présentons en premier lieu, la technique de relais multipoints puis les différents messages de contrôle de ce protocole. Nous détaillons ensuite les différentes attaques dont OLSR est vulnérable ainsi que nous citons quelques travaux qui ont été faits pour faire face à ces attaques. Enfin, dans le cinquième chapitre, nous analysons l’attaque du trou noir dans le cadre du routage OLSR en proposant deux contre-mesures et en validant la seconde par simulation.

Chapitre 1 Les réseaux sans fil et les réseaux ad hoc

« l ’ admirable féerie à laquelle quelques instants suffisent pour qu ’ apparaisse prés de nous, invisible mais présent, l ’ê tre à qui nous voulions parler et qui, restant à sa table, dans la ville qu ’ il habite [...], sous un ciel différent du nôtre, par un temps qui n ’ est pas forcément le m ê me, au milieu de circonstances et de préoccupations que nous ignorons et que cet ê tre va nous dire, se trouve tout à coup transportéà des centaines de lieues ( lui et toute l ’ ambiance o ù il reste plongé) prés de notre oreille, au moment o ù notre caprice l ’ a ordonné. »

À la Recherche du temps Perdu, Marcel Proust.

Ce chapitre, permettra au lecteur de découvrir - si ce n’est déjà fait - le monde des télécommunications et surtout des réseaux ad hoc. Après un bref rappel sur les différents pionniers qui ont permis aux formidables technologies dont nous ne pourrions plus nous passer de voir le jour, nous présenterons ce dont, au vue de l’engouement actuel de la recherche en réseaux, nous ne pourrons sûrement plus nous passer d’ici quelques années. La description que nous ferons des réseaux ad hoc fournira au lecteur les bases nécessaires à la compréhension de la suite de ce document et la sensibilisation à la problématique liée à notre travail.

1.1 Bref historique des télécommunications

1.1.1 La première transmission aérienne « moderne »

L’histoire de la télécommunication débute bien avant l’ère de l’informatique. De nombreuses civilisations ont tenté de proposer des solutions permettant de communiquer au-delà de la portée de la voix. On peut penser aux signaux de fumée des amérindiens, aux pigeons voyageurs utilisés par les Arabes ou les Chinois avant les Européens. Cependant, ce n’est que vers la fin du XV IIIe siècle que le premier dispositif que l’on peut qualifier de « technologique »fit son apparition.

Dans les années 1790, après la révolution française, la guerre gronde aux portes du pays et la nécessité de pouvoir communiquer sur de longues distances plus rapidement qu’en envoyant un coursier à cheval se fait sentir. Un ingénieur français, Claude Chappe (1763-1805), propose une solution qui sera baptisée « tachygraphe »puis « télégraphe »du grec TELE (loin) et GRA- PHEIN (écrire). La machine proposée par Chappe est composée de deux bras (ou voyants) articulés autour d’un troisième (figure 1.1). En fonction de la position de ces trois voyants, on déduit différents signaux qui forment un code permettant de communiquer à 10 kilomètres grâce à une lunette longue portée. Ces voyants peuvent décrire 196 signaux différents qui, utilisés dans un code connu de l’émetteur et du récepteur du message, permettent de commu- niquer des ordres, des évènements et toutes sortes d’informations. En 1794, plusieurs de ces dispositifs sont répartis entre Paris et Lille afin de permettre à ces deux villes de communiquer. Chaque signal est donc répété de proche en proche de Paris à Lille par les opérateurs de ce dispositif (appelés les stationnaires). La première ligne de télégraphie aérienne était née. Le 1er septembre 1794 , la première dépêche télégraphique est transmise avec succès entre ces deux villes¹.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.1 - Le télégraphe de Chappe

1.1.2 Le fil comme support de communication

Dans les années 1840, l’américain Samuel Morse invente un télégraphe électrique simple : des piles, un interrupteur, un électro-aimant et des fils suffisent. L’appareil de Morse, qui transmit le premier télégramme public en 1844, ressemblait à un simple commutateur électrique. Il permettait le passage d’un courant pendant une durée prédéfinie puis l’interrompait, le tout étant commandé avec la pression d’un doigt. Le premier récepteur Morse était équipé d’un crayon contrôlé électromagnétiquement. Ce crayon imprimait des marques sur une bande de papier, fixée sur un cylindre animé par un mouvement d’horlogerie.

Les marques variaient en longueur suivant la durée des impulsions du courant électrique pas- sant à travers les fils d’un électro-aimant et prenaient la forme visuelle de points et de traits. Par la suite, les opérateurs apprirent à reconnaître directement à l’oreille les traits et les points qui leur étaient transmis. Son appareil fut adopté par la plupart des pays européens et des réseaux nationaux basés sur le télégraphe de Morse virent le jour aux Etats-Unis, en France, en Angleterre...En 1866, après plusieurs essais infructueux, le premier câble transatlantique fut installé et avec lui, le premier véritable réseau mondial de télécommunication se développa.

Aux environs de 1940, la première ère de l’informatique moderne fit son apparition. Rapidement, l’adaptation des technologies de télécommunications à l’informatique fut rapidement incontournable. En 1957, le ministère de la défense américain crée l’agence pour les projets de recherche avancée (ARPA). Dans ce cadre, le besoin de faire communiquer les différentes équipes de recherche aux quatre coins des Etats Unis se fait ressentir. Ce besoin a mené les chercheurs de l’ARPA à créer l’ARPANET, réseau destiné à relier entre elles les différentes universités du pays, qui grâce à la standardisation du modèle TCP/IP [94, 79], évoluera vers l’Internet que nous connaissons actuellement.

1.1.3 La communication sans fil

Depuis peu, les systèmes de communication sans fil offrent aux utilisateurs la possibilité de profiter des joies des télécommunications quelle que soit leur localisation géographique. Pourtant, la communication sans fil est presque aussi vielle que la communication filaire ...

En 1887, Heinrich Hertz vérifie par l’expérience les théories de Maxwell. Ces dernières, établies de façon mathématique par James Maxwell, nous disent que toute perturbation élec- trique donne naissance à des oscillations électromagnétiques. Ces oscillations seront amenées à êtres connues sous le nom d’ondes hertziennes. En 1890, Edouard Branly découvre le premier récepteur sensible aux ondes hertziennes. À partir des travaux de Branly, l’italien Gugliemo Marconi invente le premier appareil de télégraphie sans fil en 1895. Puis Marconi va de succès en augmentant les distances de transmission pour atteindre, en 1903, la transmission complète d’un message sur une distance de 3400 Km !

Jusqu’à la fin des années 1980, la technologie sans fil a surtout été utilisée dans le cadre de la radio, de la télévision ou des communications réservées à d’importants organismes comme l’armée. L’arrivée des téléphones cellulaires GSM⁸⁴ (Global System for Mobile communication) a offert à tous la possibilité de communiquer de n’importe où, avec n’importe qui. Cependant, un tel dispositif nécessite le déploiement d’une infrastructure coûteuse devant assurer le relais entre les téléphones portables et le réseau téléphonique filaire.

1.2 Introduction aux réseaux sans fil

Dans les réseaux sans fil [80, 29], des ordinateurs sont reliés et communiquent l’un avec l’autre pas avec un moyen visible , mais par des émissions d’énergie électromagnétique dans l’air . Le support de transmission le plus utilisé est les ondes radio. Les transmissions sans fil utilisent le spectre des micros ondes : les fréquences disponibles sont situées autour de la bande de 2.4GHz ISM (Industrial, Scientific and Medical) pour une bande passante d’environ 83 MHz, et autour de la bande de 5 GHz U-NII (Unlicensed-National Information Infrastructure) pour une bande passante d’environ 300 MHz divisées en deux parties. Les attributions exactes de fréquence sont établies par des lois dans les différents pays ; les mêmes lois règlent également la puissance maximale de transmission attribuée. Selon la puissance d’émission, le débit, la fréquence et le type d’antenne utilisé, un tel réseau sans fil peut avoir une portée de transmission radio d’environ 10-100 mètres à 10 Kilomètres par machine.

L’autre type de support de transmission est l’ infrarouge. Les rayons infrarouges ne peuvent pas pénétrer les matériaux opaques et ont une plus petite portée de transmission d’environ 10 mètres. Pour ces raisons, la technologie infrarouge est principalement utilisée pour de petits dispositifs dans WPANs (Wireless Personal Area Networks), par exemple pour connecter un PDA (Personal Digital Assistant) à un ordinateur portable à l’intérieur d’une salle.

1.2.1 Les normes des réseaux sans fil

Actuellement il y a trois normes principales pour les réseaux sans fil : la famille IEEE 802.11, HiperLAN et Bluetooth.

1.2.1.1 IEEE 802.11

IEEE 802.11⁶⁶ est une norme publiée par l’IEEE (Institut of Electrical and Electronics Engineers). Du point de vue de la couche physique, elle définit trois techniques noninteroperable : IEEE 802.11 FHSS (Frequency Hopping Spread Spectrum) et IEEE 802.11 DSSS (Direct Sequence Spread Spectrum), qui utilisent le support radio à 2.4 GHZ, et IEEE 802.11 IR (infra Red). Le débit obtenu est de 1-2 Mbps ( Mega byte par seconde ). Ces spécifications ont donné naissance à une famille d’autres normes :

1.2.1.1.1 IEEE 802.11a la norme 802.11a¹ (baptisée WiFi 5) permet d’obtenir un haut débit (54 Mbps théoriques, 30 Mbps réels). Elle spécifie 8 canaux radio dans la bande de fréquence de 5 GHz. Elle utilise le codage OFDM (Orthogonal frequency Division Multiplexing). IEEE 802.11a est incompatible avec IEEE 802.11b car elles utilisent des fré- quences différentes.

1.2.1.1.2 IEEE 802.11b baptisée Wi-Fi (Wireless Fidelity)⁷, est la norme la plus ré- pandue actuellement, elle opère dans la bande de 2.4 GHz ISM. Elle constitue une solution de connexion réseau pratique et intéressante, offrant mobilité, flexibilité, faible coût de dé- ploiement et d’utilisation⁵⁵, Wi-Fi est aujourd’hui promue par l’alliance WECA² (Wireless Ethernet Compatibility Alliance). Entérine des transmissions à 5.5 et 11 Mbps, sur un rayon de 50 à 100 mètres.

1.2.1.1.3 IEEE 802.11g IEEE 802.11g⁶ opère dans la bande de 2.4 GHz et a un débit jusqu’à 20 Mbps. Elle utilise les deux techniques de codage OFDM et DSSS pour assurer la compatibilité avec la norme IEEE 802.11b.

Une autre norme est actuellement en cours de développement, IEEE 802.16⁵ ( baptisée WiMAX :Worldwide Interoperability for Microwave Access ), est conçue pour WMANs ( Wireless Metropolitan Area Networks) et donc pour surmonter les limitations sur la portée de transmission d’IEEE 802.11. Elle utilise des fréquences de 10 à 66 GHz et devrait assurer la couverture du réseau pour plusieurs Km².

1.2.1.2 HiperLAN

HiperLAN (High Performance Radio LAN) est une norme publiée par l’ETSI³ (European Telecommunications Standard Institute) et une concurrente d’IEEE 802.11. Elle définit deux genres de réseaux :

HiperLAN 1 utilise la bande de 5 GHz et offre un débit de 10 - 20 Mbps³.

HiperLAN 2 utilise la bande de 5 GHz et offre un débit jusqu’à 54 Mbps [2, 4].

Une norme relative est HiperMAN, concurrente d’IEEE 802.16 et destinée à fournir la couverture de zone métropolitaine. Elle opère dans la bande de 2 - 11 GHz.

1.2.1.3 Bluetooth

Bluetooth⁴ est une norme conçue par un consortium d’entreprises privées telles qu’Agere, Ericsson, IBM, Intel, Microsoft, Motorola, Nokia et Toshiba. Bluetooth opère dans la bande de 2.4 GHz en utilisant FHSS et a une portée d’action courte d’environ 10 mètres. Pour de telles caractéristiques et son bas coût, Bluetooth est adaptée pour de petits WPANs et est également utilisée pour relier des périphériques tels que des claviers, des imprimantes, ou des écouteurs de téléphone mobile. La technologie radio de Bluetooth fonctionne en mode maître esclave, et chaque dispositif peut fonctionner comme maître ou comme esclave. Des communications sont organisées dans de petits réseaux appelés les piconets, chaque piconet se compose de maître et 1 à 7 esclaves actifs. Des piconets multiples peuvent recouvrir pour former un scatternet.

1.2.2 Architecture

Un réseau sans fil peut être structuré pour fonctionner en mode BSS (Basic Service Set) ou en mode IBSS (Independent Basic Service Set). Les deux modes affectent la topologie et la capacité de mobilité des machines (nœuds) qui composent le réseau.

1.2.2.1 Le mode BSS (Basic Service Set)

En mode BSS, également appelé le mode avec infrastructure, un certain nombre de nœuds mobiles sont reliés par un lien radio (sans fil) à un point d’accès non mobile (AP : access point), comme sur la figure 1.2. Les nœuds communiquent par l’intermédiaire d’un point d’accès qui peut également fournir la connectivité avec un réseau filaire externe (par exemple Internet). Plusieurs réseaux de BSS peuvent être reliés pour former un ESS (Extended Service Set).

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.2 - Le modèle de réseaux sans fil en mode BSS (avec infrastructure)

1.2.2.2 Le mode IBSS (Independent Basic Service Set)

Le mode IBSS, également appelé pair à pair ou le mode ad hoc, permet au nœuds de communiquer directement (point à point) sans besoin d’un point d’accès comme sur la figure 1.3. Il n’y a aucune infrastructure fixe. Les nœuds doivent être dans la portée de communication de chacun d’entre eux afin de communiquer.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.3 - Le mode IBSS (sans infrastructure)

1.3 Les réseaux ad hoc

Aujourd’hui, de nombreux systèmes de communication sans fil existent. Ils permettent d’éviter l’obligation pour un usager d’être relié à un ensemble filaire pour accéder aux ressources d’un réseau. De nombreux exemples existent déjà de manière commerciale, comme le GSM, un système de téléphonie portable permettant de joindre un correspondant quelle que soit sa position. Mais un tel ensemble est dépendant de l’emplacement des bases (les antennes permettant de relier le monde des ondes hertziennes au réseau filaire) car cette structuration impose certaines restrictions, comme la nécessité d’un déploiement d’infrastructures coûteuses.

On peut imaginer un système plus évolué et décentralisé, utilisant les usagers du réseau comme support de l’ensemble des communications. Dans un emplacement de taille définie (une pièce, un bâtiment, une ville, un pays ou même une planète) se trouve un nombre impor- tant d’ordinateurs, éventuellement mobiles. Les entités qui composent ce réseau possèdent un dispositif de communication sans fil leur permettant de communiquer avec les entités situées dans leur voisinage. Chaque nœud peut donc directement joindre ses voisins en utilisant son interface radio. Ils ont aussi la possibilité de contacter n’importe quel autre noeud à l’intérieur du réseau en utilisant les noeuds intermédiaires (situés entre la source et le destinataire). Ces derniers se chargent de relayer les messages (voir figure 1.4) et ainsi offrir un réseau autonome, conçu et supporté par l’ensemble des participants. Ce type d’organisation s’appelle réseaux ad hoc (Ad Hoc Networks). Ce domaine est devenu une nouvelle voie de recherche à part entière, avec la formation d’un groupe de recherche de l’IETF (Internet Engineering Task Force) bap- tisé MANET (Mobile Ad-hoc Networks). De nombreuses publications et livres proposent une présentation complète de ce type d’architecture[76, 91, 96].

Mais des problèmes existent, de la couche matérielle jusqu’à la couche application³⁷. Par exemple, la possibilité que l’ensemble ou une partie des entités soient mobiles entraîne des variations dans la recherche ou la maintenance d’un chemin entre deux noeuds. On peut aussi citer le fait que chaque entité est autonome et qu’il n’existe pas de système centralisé pour gérer les communications. Cette contrainte oblige alors l’élaboration d’algorithmes totalement distribués, dans le but d’obtenir un comportement global cohérent malgré le caractère plus ou moins indépendant de chaque noeud.

D’autres problématiques se posent : comment distribuer une information à l’ensemble des nœuds (et comment conserver une information cohérente vis-à-vis des évolutions dans le ré- seau) ? Quelles sont les modifications qu’entraîne ce modèle sur la pile réseau OSI⁵ pour apporter une certaine flexibilité tout en restant compatible avec la plus grande partie possible des protocoles existants ? Il existe aussi des questions sociales et économiques sur l’émergence de réseaux ad hoc en concurrence aux réseaux actuels, qu’ils soient filaires ou non (le téléphone portable par exemple, qui supportera difficilement un réseau ouvert et coopératif de ce type).

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.4 - Un exemple de transmission d’un message entre noeuds dans un réseau ad hoc

1.3.1 Définition 1

Le groupe MANET de l’IETF (Internet Engineering Task Force ) fournit une définition plus précise en introduction de la RFC 2501²⁴:

« Un réseau ad hoc comprend des plates-formes mobiles (par exemple, un routeur intercon nectant différents hôtes etéquipements sans fil) appelées n œ uds qui sont libres de se déplacer sans contrainte. Un réseau ad hoc est donc un syst è me autonome de n œ uds mobiles. Ce sys t è me peut fonctionner d ’ une mani è re isolée ou s ’ interfacer à des réseaux fixes au travers de passerelles. Dans ce dernier cas, un réseau ad hoc est un réseau d ’ extrémit é. »

1.3.2 Définition 2

Le terme « ad hoc » est une locution d’origine latine qui signifie « qui convient au sujet, à la situation ». On parle donc de réseaux auto-adaptatifs (capables de s’organiser par euxmêmes). Une autre lecture de la définition peut signifier une propriété d’universalité de ce moyen de communication, comme si ce procédé pouvait satisfaire tous les besoins en terme de communication entre objets mobiles²¹.

La définition la plus concise d’un réseau ad hoc est la suivante : « un réseau ad hoc est un réseau sans fil à contrôle totalement décentralisé ». Par réseau sans fil, on entend que toutes les communications entre objets se font par voie aérienne, une interface radio dans chaque mobile permettant d’émettre et de recevoir. Le terme de contrôle décentralisé indique que l’ensemble des opérations pour la découverte et la maintenance du réseau se fait localement par chaque nœud. Chacun gère ses communications à partir des informations connues sur le réseau et sur l’état interne du noeud, dans le but de faire émerger un comportement cohérent du réseau (i.e. des routes correctement établies).

Les réseaux ad hoc peuvent inclure le concept de mobilité¹¹. Par mobilité, on désigne le fait que chaque terminal peut se déplacer à l’intérieur du site, seul ou avec un groupe. Ces mouvements entraînent des changements dans les routes construites, ainsi que dans les caches d’information sur la topologie du réseau. Un noeud doit maintenir à jour ces informations et conserver dans un état valide les routes qui commencent, passent ou finissent par lui-même.

Le concept de mobilité inclut aussi certains états, tels que la déconnexion ou l’impossibilité de joindre le réseau. La topologie des réseaux ad hoc étant volatile, variable et éphémère, chacun des membres peut quitter le groupe de communication sans avertissement. Ainsi, le fait qu’un nœud soit absent du réseau est un état normal, qui ne doit pas gêner les autres par- ticipants. Cette caractéristique doit être prise en compte à chaque couche du modèle réseau OSI : le routage doit se faire dans la mesure du possible (i.e. le nœud destinataire doit être joignable), de manière transparente, tout en s’adaptant aux déficiences d’une partie du réseau (en trouvant des chemins alternatifs par exemple). Au niveau des couches supérieures (ap- plications), chaque programme doit pouvoir accéder à des informations supplémentaires pour tenir compte de l’aspect changeant et sans garantie du réseau. Par exemple, il peut disposer d’outils lui indiquant la qualité d’un lien entre deux nœuds [38, 39].

1.3.3 Propriétés et spécificités des réseaux ad hoc

Les réseaux ad hoc héritent des mêmes propriétés et problèmes liés au réseaux sans fil. Particulièrement, le fait que le canal radio soit limité en terme de capacité, plus exposé aux pertes (comparé au médium filaire), et sujet à des variations dans le temps. Le canal est confronté aux problèmes de « station cachée »et « station exposée ». En outre, les liens sans fil sont asymétriques et pas sécurisés.

D’autres caractéristiques spécifiques aux réseaux ad hoc conduisent à ajouter une complexité et des contraintes supplémentaires qui doivent être prises en compte lors de la conception des algorithmes et des protocoles réseaux, à savoir :

1.3.3.1 L’absence d’une infrastructure centralisée

chaque nœud travaille dans un environnement pair à pair distribué, et agit en tant que routeur pour relayer des communications, ou génère ses propres données. La gestion du réseau est ainsi distribuée sur l’ensemble des éléments du réseau.

1.3.3.2 La mobilité des nœuds et maintenance des routes

la mobilité continue des nœuds crée un changement dynamique de topologie. Par exemple, un nœud peut joindre un réseau, changer de position ou quitter le réseau. Ce déplacement a naturellement un impact sur la morphologie du réseau et peut modifier le comportement du canal de communication. Ajoutant à cela la nature des communications (longues et synchrones, courtes et asynchrones, ...). Les algorithmes de routage doivent ainsi résoudre ces problèmes et supporter la maintenance et prendre en charge en un temps limité la reconstruction des routes tout en minimisant l’overhead généré par les messages de contrôle.

1.3.3.3 L’hétérogénéité des nœuds

Un nœud mobile peut être équipé d’une ou plusieurs interfaces radio ayant des capacités de transmission variées et opérant dans des plages de fréquences différentes. Cette hétérogénéité de capacité peut engendrer des liens asymétriques dans le réseau. De plus, les nœuds peuvent avoir des différences en terme de capacité de traitement (CPU, mémoire), de logiciel, de taille (petit, grand) et de mobilité (lent, rapide). Dans ce cas, une adaptation dynamique des protocoles s’avère nécessaire pour supporter de telles situations.

1.3.3.4 La contrainte d’énergie

Les équipements mobiles disposent de batteries limitées, et dans certains cas très limitées tels que les PDA, et par conséquent d’une durée de traitement réduite. Sachant qu’une partie de l’énergie est déjà consommée par la fonctionnalité du routage. Cela limite les services et les applications supportées par chaque nœud.

1.3.3.5 La taille des réseaux ad hoc

elle est souvent de petite ou moyenne taille (une centaine de noeuds) ; le réseau est utilisé pour étendre temporairement un réseau filaire, comme pour une conférence ou des situations où le déploiement du réseau fixe n’est pas approprié (ex : catastrophes naturelles). Cependant, quelques applications des réseaux ad hoc nécessitent une utilisation allant jusqu’à des dizaines de milliers de nœuds, comme dans les réseaux de senseurs³¹. Des problèmes liés au passage à l’échelle tels que : l’adressage, le routage, la gestion de la localisation des senseurs et la configuration du réseau, la sécurité, etc, doivent être résolus pour une meilleure gestion du réseau.

1.3.3.6 Vulnérabilité

Les réseaux sans fil sont par nature plus sensibles aux problèmes de sécurité. Pour les réseaux ad hoc, le principal problème ne se situe pas tant au niveau du support physique mais principalement dans le fait que tous les nœuds sont équivalents et potentiellement nécessaires au fonctionnement du réseau. Les possibilités de s’insérer dans le réseau sont plus grandes, la détection d’une intrusion ou d’un déni de service plus délicate et l’absence de centralisation pose un problème de remontée de l’information de détection d’intrusions.

1.3.4 Domaines d’applications

Les recherches sur les réseaux ad hoc ont été initiées par le DARPA (Defense Advanced Research Projects Agency) avec le développement de PRN ou Packet Radio Networks⁵⁶. Ce protocole, conçu pour l’armée américaine, permet de déployer une infrastructure de com- munication entre chaque bataillon, par l’intermédiaire de plusieurs véhicules communiquant ensemble. Il inspire de bonnes idées, comme un modèle de couche MAC (Medium Access Control) avec approbation passive ou la prise en compte de la qualité des liens. Mais ce pro- tocole possède de trop nombreux défauts. D’une part, il prend l’hypothèse que l’ensemble des entités se déplacent lentement (avec peu de changements dans la topologie du réseau). D’autre part, la difficulté de concevoir, dans les années 1970, des composants électroniques suffisants pour mémoriser les paquets lors d’une réémission impliquant un matériel de taille assez importante et difficile à utiliser.

Le fait que ce soit les militaires qui aient commencé les premières expérimentations sur les réseaux ad hoc n’est pas un hasard. En effet, cette infrastructure est très adaptée aux envi- ronnements « hostiles », car ils sont rapidement déployables, et robustes dans les cas de perte de liens. De plus, la possibilité de posséder plusieurs routes renforce la fiabilité de l’ensemble du réseau. Ils sont donc particulièrement intéressants pour un système de communication sur les champs de bataille mais aussi dans d’autres environnements. On peut évoquer les sinistres (tremblements de terre, inondations) où l’ensemble des infrastructures existantes a été détruites. Les unités de secours disposent alors d’un moyen de communication qui n’est pas influencé par les dégâts causés à l’environnement. Ou encore, les survivants peuvent établir un réseau pour aider à leur localisation¹⁰⁵.

Les réseaux ad hoc peuvent aussi être utilisés pour relier plusieurs ordinateurs entre-eux. Ils sont donc adaptés pour la formation de réunions, où la nécessité temporaire d’une infrastructure pour les communications est soutenue par l’ensemble des participants. Il existe aussi des recherches⁶⁴ proposant d’utiliser les réseaux ad hoc avec les véhicules routiers. On peut entrevoir de nombreuses applications possibles pour un tel usage : distribution d’information au niveau local (risque d’accidents ou d’encombrements), aide automatique à la conduite (feux d’avertissement), téléphonie entre véhicules, etc.

Avec l’émergence de l’informatique mobile et les possibilités offertes par l’informatique ves- timentaire (Wearable Computing)⁶¹, chaque usager se voit doté d’ordinateurs qu’il transporte avec lui. Ces appareils peuvent se mettre à communiquer entre eux, ou avec l’environnement. Dans le premier cas, on parle de réseau personnel (PAN), et la solution ad hoc permet la liaison entre chacun des éléments¹⁵ (avec l’utilisation de Bluetooth³³ par exemple, adapté pour des petits objets et des courtes distances). Dans le deuxième cas, les réseaux ad hoc permettent à chacun de se connecter à l’environnement et d’y participer sans pré-requis par- ticulier. On parle alors d’informatique omniprésente (Ubiquitous Computing)⁹⁹: chaque entité se reconfigure en fonction des communications disponibles, de façon transparente pour l’utilisateur.

Un autre domaine très intéressant pour les réseaux ad hoc concerne les senseurs²⁷. Ce sont des équipements possédant des capacités très limitées (mémoire, processeur, bande passante) et de taille réduite. Ces équipements ont de nombreux domaines d’applications : médicales ou militaires par exemple. Ils sont en général utilisés en grande quantité, et les réseaux ad hoc permettent alors la liaison entre tous les objets. On peut citer l’exemple de capteurs météorologiques, de surveillance d’un site, de mesure des constantes d’un être humain ou de contrôle de structures (par exemple, des capteurs coulés dans le béton d’un pont).

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.5 - Exemple d’application des réseaux Ad hoc

1.4 Conclusion

Les réseaux ad hoc font partie d’un domaine de recherche qui n’a pris d’essor que très récemment. Le facteur qui a déclenché cet intérêt fut l’arrivée de technologies relativement bon marché qui ont favorisé la conception et le déploiement de tels réseaux. Avant cela, ce domaine était réservé aux militaires qui disposent de moyens tout autres.

Il est incontestable que les réseaux ad hoc de la famille MANET sont très intéressants. En effet, la mobilité et la simplicité d’installation de tels réseaux en plus des débits de plus en plus importants, leur promettent un bel avenir.

Mais ces réseaux n’offriront entière satisfaction à l’utilisateur que s’ils sont dotés d’un routage (stratégie d’acheminement de packets) efficace. En effet, la fragilité des liens radio à utiliser et la limite de la portée radio nous incitent à profiter de la possibilité du relayage par des nœuds intermédiaires. Par ailleurs, la topologie de ces réseaux qui peut être continuellement mobile oblige les protocoles de routage à réagir rapidement.

Dans ce chapitre nous avons donné un survol sur les réseaux sans fil, ses différentes normes, ses architectures et le concept de réseau ad hoc. Dans la pratique, les réseaux ad hoc connaissent aujourd’hui plusieurs applications tel que les applications militaires et les applications de secours et de façon générale, toutes les applications caractérisées par une absence d’infrastructures préexistantes. Après avoir défini l’environnement mobile ad hoc et décrit ses principales applications et caractéristiques, nous allons traiter le problème d’acheminement des paquets dans les réseaux ad hoc, objet du chapitre suivant.

Chapitre 2 Etat de l’art des protocoles de routage dans MANET

Les réseaux ad hoc que nous considérons sont multi-sauts. Il peut donc arriver qu’un mobile veuille communiquer avec un autre qui n’est pas dans sa portée de communication directe. Les messages vont devoir être transmis de proche en proche jusqu’à la destination : c’est ce que l’on appelle « le routage ». La technique la plus basique est l’inondation, où chaque mobile réémet tous les paquets qu’il reçoit pour la première fois. Evidemment, l’inondation consomme beaucoup de ressources (bande passante et énergie) et n’est pas optimale. De nombreux pro- tocoles de routage ont donc été proposés pour rendre les communications multi-sauts plus efficaces (moins de réémissions, chemins plus courts, etc.) que l’inondation basique.

Dans ce chapitre, nous allons donc présenter certains des protocoles de routage développés dans le cadre du groupe de travail MANET⁵⁹ de l’IETF. Ces protocoles travaillent au niveau IP et sont donc indépendants des couches physique et MAC. Le routage IP permet en particulier une interconnectivité aisée avec toutes sortes d’autres réseaux ou matériels. Il est d’ailleurs possible d’utiliser ces protocoles pour fédérer en un seul réseau MANET des utilisateurs utilisant des matériels différents (cartes radios de technologies diverses, réseaux filaires, etc). Les protocoles présentés sont parmi les plus représentatifs des diverses techniques utilisées pour le routage ad hoc.

2.1 Routage hiérarchique ou plat

Les protocoles de routage pour les réseaux ad hoc peuvent être classés suivant plusieurs critères. Le premier d’entre eux concerne le type de vision qu’ils ont du réseau et les rôles qu’ils accordent aux différents mobiles.

Les protocoles de routage « à plat » considèrent que tous les nœuds sont égaux (figure 17 Fig. 2.1 - Routage « à plat » Fig. 2.2 - Routage hiérarchique 2.1). La décision d’un nœud de router des paquets pour un autre dépendra de sa position et pourra être remise en cause au cours du temps.

Les protocoles de routage hiérarchique fonctionnent en confiant aux nœuds des rôles qui varient de l’un à l’autre. Certains nœuds sont élus et assument des fonctions par- ticulières qui conduisent à une vision en plusieurs niveaux de la topologie du réseau. Par exemple, un nœud pourra servir de passerelle pour un certain nombre de nœuds qui se seront attachés à lui. Le routage en sera simplifié, puisqu’il se fera de passerelle à passerelle, jusqu’à celle directement attaché au destinataire. Un exemple est donné sur la figure 2.2, où le nœud N3 passe par les passerelles P1, P2 et P3 pour atteindre N7. Dans ce type de protocole, les passerelles supportent la majeure partie de la charge du routage ( les nœuds qui s’y rattachent savent que si le destinataire n’est pas dans leur voisinage direct, il suffit d’envoyer à la passerelle qui se débrouillera ). Dans les réseaux où certains nœuds s’avèrent très sédentaires et disposent de suffisamment d’énergie (par exemple réseau d’ordinateurs portables mais où certains sont reliés à une source d’éner- gie, stations de base disposées pour garantir la connectivité, etc), ce type de routage présente certains avantages.

2.2 Etat de liens ou vecteur de distance

Une autre classification, héritée du monde filaire, est possible pour les protocoles de rou- tage :

- Les protocoles à état de liens (link state) se basent sur les informations rassemblées sur l’état des liens dans le réseau (l’état des liens est typiquement l’ensemble des liens vers des voisins d’un nœud). Ces informations sont disséminées dans le réseau périodique- ment, permettant ainsi aux nœuds de construire une carte (graphe) complète du réseau.

Le protocole de routage à état de lien le plus connu est OSPF⁶⁵ (Open Shortest Path First). OSPF se base sur l’algorithme SPF de Dijkstra²⁵ pour calculer les chemins les plus courts entre un nœud source et les autres nœuds du réseau.

- Les protocoles à vecteur de distance (distance vector) se basent sur un échange entre voisins des informations de distance des destinations connues. Chaque nœud envoie à ses voisins la liste des destinations qui lui sont accessibles et le coût correspondant. Le nœud récepteur mis à jour sa liste locale des destinations avec les coûts minimums. Le protocole de routage le plus connu de cette famille est sans doute RIP⁶⁰ ( Routing Information Protocol). Le calcul des routes est basé sur l’algorithme de Bellman-Ford ¹³ distribué.

Les protocoles de routage à vecteur de distance possèdent un grand avantage qui est la simplicité de programmation ; en contre partie, ils possèdent deux problèmes de taille qui sont la génération de boucle et le comptage à l ’ infini. Parfois des nœuds peuvent se trouver isolés du reste du réseau avec l’apparition d’une boucle. Chacun d’eux croit que le chemin le plus court menant vers l’autre partie du réseau passe par un autre nœud que lui. Dans ce cas, l’échange des vecteurs des distances entraînera à chaque fois une incrémentation du coût de la destination . Cette incrémentation ne cessera que lorsqu’on atteint une valeur maximale définie comme l’infini et entre temps, les paquets de données vont boucler dans le réseau.

Les protocoles de routage à état de liens évitent facilement les boucles, et permettent d’in- tégrer des métriques multiples, puisque les informations échangées concernent les liens (débit, délai, coût, fiabilité). Les protocoles à état de liens peuvent calculer des chemins multiples, ce qui est très important pour répartir le trafic par exemple, ou encore, trouver une alterna- tive à une route endommagée. Comme le calcul est effectué d’une façon distribuée au niveau de chaque routeur, il faut être attentif à ce qu’il soit le même. C’est-à-dire que les routeurs doivent posséder les mêmes informations sur le réseau et utiliser les mêmes critères lors des choix multiples.

Le monde sans fil mobile possède des contraintes supplémentaires par rapport au monde filaire. Les protocoles classiques du monde filaire tels que le RIP ou OSPF ayant fait leurs preuves se trouvent confrontés à des situations inédites et non prises en compte : mobilité physique, versatilité des liens, interférences, etc.

2.3 Les différentes familles de protocoles de routage dans MANET

Dans les sous-sections suivantes, nous allons présenter les quatre familles de protocoles de routage : proactif, réactif, hybride et géographique. Pour plus d’informations, le lecteur pourra se reporter à un exposé des problèmes⁴⁸ et à différentes analyses des protocoles de routage existants [28, 45].

2.3.1 Les protocoles proactifs

Dans ce type d’approche (appelé aussi table driven), une maintenance régulière du réseau entre les nœuds permet de faciliter la découverte des routes. Le principe est inspiré du protocole de routage Bellman-Ford³⁰, utilisé entre autre dans les mises à jour des routeurs sur Internet. Chaque nœud maintient des informations sur chaque autre nœud du réseau, avec une table de routage (indiquant par quel voisin passer pour le destinataire). Quand la topologie du réseau est modifiée, les noeuds diffusent les modifications qu’ils perçoivent afin de mettre à jour les informations contenues dans les tables de routage . Il existe plusieurs protocoles de ce type, différentiables par le nombre de tables maintenues par chaque nœud, et par la façon de diffuser les mises à jour lors de modifications de la topologie du réseau.

2.3.1.1 DSDV (Destination Sequenced Distance Vector)

Proposé par Perkins et al dans⁷⁵, DSDV maintient une table contenant, pour chaque destination, le voisin à joindre pour y parvenir, ainsi que le nombre de sauts et un numéro de séquence. L’algorithme considère une route R 1 comme meilleure qu’une route R 2 si elle a un numéro de séquence plus important (i.e., la route est plus récente, donc les informations ont plus de chances d’être correctes) ou si le numéro de séquence est le même mais que la distance estimée vers la destination en empruntant la route R 1 est plus faible. Chaque nœud émet sa table de routage régulièrement en incrémentant le numéro de séquence correspondant à la route menant à lui. Quand un nœud estime que sa route vers un autre est coupée, il met à jour sa table de routage avec une distance infinie. Afin de diffuser les mises à jour de la table, le nœud peut émettre deux types de paquets : la table complète (full dump) ou uniquement les parties de la table qui ont été modifiées (incremental) afin de réduire l’utilisation du médium.

2.3.1.2 FSR (Fisheye State Routing)

Proposé par Pei et al dans⁷³, la particularité de l’œil de poisson ( fish eye ) est qu’il distingue les choses en détail au centre, et que sa précision se dégrade en s’éloignant du point focal . Cette caractéristique a été exploitée par Kleinrock et Stevens⁵¹ pour réduire la taille des informations nécessaires pour représenter des données graphiques. FSR utilise cette technique pour maintenir des routes précises pour le voisinage proche du nœud. La précision se dégrade ainsi avec la distance. Il part du principe qu’un changement de topologie lointain n’a pas une influence significative sur le calcul de la route localement. De ce fait, la fréquence de rafraîchissement se fait en fonction de la distance. Plus un nœud est loin, moins il reçoit fréquemment les mises à jour de topologie locale. Sur la base des informations de voisinage et de topologie, FSR construit sa table de routage. Au cours du routage, le chemin à parcourir se précise en se rapprochant de la destination.

2.3.1.3 TBRPF (Topology Broadcast Based on Reverse - Path Forwarding)

Proposé par Bellur et al dans¹⁴, chaque nœud maintient en permanence un arbre dont il est la racine et qui fournit les chemins les plus courts pour tous les autres nœuds du réseau. TBRPF est constitué de deux parties complémentaires : la découverte des voisins et le routage proprement dit. La découverte des voisins est assurée par un mécanisme de paquets hello diffusés régulièrement au voisinage direct. Ces paquets hello contiennent la liste des voisins du nœud, et permettent ainsi de connaître rapidement la topologie complète du réseau à deux sauts. Il faut noter que TBRPF emploie une technique de hello différentiels où seuls les changements de topologie sont notifiés (diminuant ainsi la taille moyenne des paquets et autorisant leur envoi à une plus grande fréquence).

La partie routage quant à elle est basée sur un échange des arbres de routage entre nœuds voisins, conduisant progressivement à la diffusion de l’information dans l’ensemble du réseau. Là encore seules des parties d’arbres sont échangées. Normalement, un nœud ne diffuse qu’un sous-arbre à deux niveaux dont il est la racine. Au premier niveau apparaissant les liens vers tous les voisins directs du nœud, et au deuxième niveau un unique lien vers chaque voisin à deux sauts. A noter enfin que dans un souci d’économie de bande passante, les sous-arbres et les paquets hello sont regroupés autant que possible dans un même paquet ( on parle d’agrégation ou piggybacking puisque l’on profite des paquets hello pour envoyer en même temps les sous-arbres).

L’intérêt principal des protocoles proactifs est que l’on peut trouver facilement et rapide- ment le destinataire sans avoir à lancer une recherche dans le réseau. De plus, les informations collectées pour aider au routage peuvent s’avérer très utile pour d’autres applications et, comme les informations sont mises à jour régulièrement, les pertes de routes sont peu fréquentes.

Cependant, ces protocoles sont tributaires d’une mise à jour régulière et fiable des informations, ce qui induit une charge constante du réseau, due aux messages de contrôle. Dans le cas de réseaux à mobilité forte, cette charge se révèle être une catastrophe car la quasi-totalité de la bande passante est consacrée aux messages de contrôle et les applications n’ont plus assez de ressources. De plus, si le réseau est très grand, la quantité d’information à diffuser et à mémoriser devient également un problème.

2.3.2 Les protocoles réactifs

Les protocoles réactifs suivent une politique radicalement opposée à celle des protocoles proactifs. Ici, aucune maintenance régulière n’est effectuée et la recherche de routes est effectuée « à la demande ». Lorsqu’un noeud cherche à en joindre un autre, il utilise un protocole de diffusion (envoi d’un message à tous le réseau) afin de découvrir une route permettant d’y mener. Quand le correspondant reçoit le message de diffusion, dans lequel est stocké la liste des nœuds qui ont été utilisés pour acheminer ce message, il peut répondre par un message qui suivra cette route afin d’informer la source. La figure 2.3 donne un exemple simple d’une telle procédure.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 2.3 - Recherche de route par un protocole réactif

[...]

---

¹ Ce premier message était destiné à l’assemblée nationale qui siégeait à Paris. " Condé restituée à la république. la reddition a eu lieu ce matin à 6 heures "

² http ://www.wi-fizone.org

³ http ://www.etsi.org

⁴ http ://www.bluetooth.org

⁵ Le lecteur pourra trouver une description complète des couches du modèle OSI (Open System Interconnexion) de l’organisme ISO (International Standard Organisation) dans 93