Les caractéristiques des réseaux Ad Hoc

Les caractéristiques des réseaux Ad Hoc

Les domaines des réseaux mobiles Ad Hoc

Les réseaux Ad Hoc ont un très large potentiel dans un futur proche et l’intérêt que porte la recherche pour ce domaine s’explique donc très largement.
Domaine militaire
Le premier domaine d’application des réseaux Ad Hoc fut le domaine militaire. Dans les années 80, le DARPA (Defense Advanced Research Projects Agency) propose Packet Radio Network. L’intérêt des militaires pour une telle technologie s’explique par le caractère particulièrement adapté de ces réseaux aux situations hostiles.
Situation de sinistres
Leur utilisation est également possible dans le cadre de sinistres, comme les tremblements de terre ou les incendies, pour permettre aux équipes de sauvetage de communiquer alors que les infrastructures de communication classiques sont détruites ou pour permettre aux survivants d’établir un réseau aidant à leurs localisations. De plus, la possibilité pour les communications d’emprunter plusieurs routes renforce la fiabilité d’un tel réseau ce qui est indispensable dans un tel contexte .
Réseaux locaux
Les réseaux Ad Hoc peuvent également servir pour former des réseaux locaux. En effet, la mise en place du réseau est plus simple, pas de câble à tirer dans le bâtiment d’où une économie intéressante pour une entreprise.

Sécurité

Si les transmissions ne sont pas protégées, des nœuds malveillants peuvent espionner les communications radio. Un autre problème qui 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, ces nœuds peuvent engendrer un trafic dans le seul but de consommer toute la bande passante, et d’empêcher les communications, ils peuvent même perturber le routage en émettant des paquets de contrôle déroutant les paquets ou engendrant des pertes. La détection d’une intrusion ou d’un déni de service est donc plus délicate et l’absence de centralisation pose un problème de remontée de l’information de détection d’intrusions .

Ad Hoc On-demand Distance Vector (AODV) 

AODV est un protocole basé sur le principe des vecteurs de distance et appartient à la famille des protocoles réactifs. En s’appuyant sur le principe des numéros de séquences AODV a su éviter le problème des boucles et le comptage à l’infini connu des protocoles à  vecteur de distances classique. Ces numéros de séquences inclus dans les messages de contrôles lui permettant également de maintenir la consistance des informations de routage dont il dispose. AODV effectue les découvertes de route à la demande en diffusant un paquet RREQ (Route REQuest) qui sera acheminé d’un nœud à un nœud. En réponse à ce paquet, la destination ou un nœud intermédiaire ayant une route valide à la destination, émet un paquet RREP (Route REPly) suivant le chemin inverse de paquet de la requête jusqu’à la source (c’est pour cela qu’AODV n’utilise que les routes symétrique). Si le nœud destinataire reçoit d’autres paquets RREQ pour la même requête alors le nombre de sauts sera pris en compte pour décider de répondre à ce paquet ou de le supprimer. AODV stocke les routes découvertes dans chaque nœud traversé par la requête RREP et maintien cette route de façon distribuée on utilisant des procédures de réparation locale de la route à son point de cassure. Par conséquent, il est capable de s’adapter aux changements de topologie du réseau en trouvant très rapidement un chemin alternatif sans devoir reconstruire la route dans sa totalité.

Optimized Link State Routing (OLSR) 

OLSR est un protocole proactif et Comme son nom l’indique, c’est un protocole à état de lien optimisé ; il obtient aussi des routes de plus court chemin. Alors que dans un protocole à état de lien, chaque nœud déclare ses liens directs avec ses voisins à tout le réseau, dans le cas d’OLSR, les nœuds ne déclarent qu’une sous-partie de leur voisinage grâce à la technique des relais multipoints. En un nœud donné, cette technique consiste essentiellement à ignorer un ensemble de liens et de voisins directs, et de ne garder qu’un sous-ensemble des ces voisins considérés comme pertinent. Il est choisi de façon à pouvoir atteindre tout le voisinage à deux sauts (tous les voisins des voisins), cet ensemble est appelé l’ensemble des relais multipoints MPR (Multipoint Relay). Ces relais multipoints sont utilisés pour diminuer le trafic dû à la diffusion des messages de contrôle dans le réseau en appliquant la règle suivante: un nœud retransmet un message si et seulement si il ne l’avait pas déjà reçu, et il vient de le recevoir d’un nœud dont il est un relais multipoint. Pour maintenir à jour toutes les informations nécessaires au choix des relais multipoints et le calcul de la table de routage, les nœuds OLSR ont besoin de s’échanger périodiquement deux type de message :
– Le message dit HELLO diffusé par chaque nœud, contenant la liste de ces voisins. Ces messages permettent à chacun de choisir son ensemble de relais multipoints.
– Le deuxième type est le message TC (Topology Control) diffusé périodiquement par chaque nœud et retransmet uniquement par les MPRs pour atteindre tout le réseau. Ce message contient la liste de ces voisins qui l’ont choisi comme un MPR.

Support HTTP pour le cache

L’un des plus importants dispositifs de protocole HTTP utilisés dans le contexte des caches, est celui des requêtes conditionnelles, qui recherchent des documents, seulement si un certain nombre de conditions sont satisfaites. Les clients formulent les requêtes conditionnelles, en utilisant les métas informations du document en question. Les serveurs fournissent ces informations avec les documents dans last-modified et ETag de l’en-tête de leurs réponses. L’en-tête Last-modified contient la date et le temps de la dernière modification du document. L’en-tête ETag, qui signifie Entity Tag, est un identifiant unique pour une instance particulière d’un document.
Un autre groupe d’entêtes est utilisé, pour indiquer quels documents peuvent être cachés, pour combien de temps ils peuvent être cachés, et s’ils peuvent être partagés entre différents clients, etc

Cachabilité des documents

L’objectif primaire d’un cache est de cacher certains documents, des réponses qu’il a reçues. Un document serait cachable, s’il peut être utilisé pour répondre à une future  requête. Il différencie donc entre deux familles de documents, les documents cachables et les documents non cachables. Tous les documents statiques sont considérés comme cachables à l’inverse des documents dynamiques. Les contenus dynamiques sont des pages où les données fournies par le serveur changent dans le temps ou en fonction du client (pages personnalisées).
Par exemple, la réponse à un formulaire rempli par le client est personnalisée et unique, elle est non « cachable ». Un cache décide aussi si une réponse particulière est cachable en examinant différents composants de son en-tête. En particulier ce qui suit :
Le code statut de la réponse
La méthode de la requête
Les directives de Cache-control
Le validateur de la réponse
Authentification de la requête

Défaut/succès de cache (cache hits/misses)

Quand un cache reçoit une requête pour un document, il vérifie si le document a été déjà caché. Si c’est non, on dit que la requête a provoqué un défaut de cache (cache miss). Un cache miss se produit pour les documents qui n’ont jamais été référencés précédemment, pour ceux qui ne sont pas cachables, ou pour ceux qui ont été supprimés pour faire de la place pour les nouveaux.
Si le document est présent dans le cache, alors nous pourrions avoir un cache hit. Cependant, le cache doit d’abord décider si le document stocké est frais ou périmé. Un document caché est frais si son temps d’expiration n’a pas été écoulé ; autrement, il est périmé.
Les documents frais sont donnés au client immédiatement, ils ne provoquent aucune latence et ne consomment aucune bande passante au serveur d’origine. Par contre, les documents périmés exigent la validation avec ce dernier

Politique de remplacement de cache

Comme la capacité mémoire des caches est fixe, ils ne peuvent contenir tous les documents qui leurs sont soumis. Alors, quand cet espace mémoire se remplis le cache doit choisir un ensemble de documents à expulser pour faire de la place aux nouveaux. La politique de remplacement de cache détermine quels documents devraient être expulsés du cache. Le choix de cette politique doit se baser sur le but d’atteindre une meilleure utilisation des ressources disponibles, comme l’énergie, le disque, l’espace mémoire, et la bande passante de réseau. Puisque ce choix peut avoir un impact significatif sur le trafic global de réseau.Parmi les principales caractéristiques des documents cachés qui peuvent influencer ce choix , on peut citer :
La récence : est le temps écoulé depuis le dernier référencement d’un document ;
La fréquence : est le nombre de référencements d’un document ;
La taille : est la taille du document ;
Coût d’acquisition : est le coût de recherche et de chargement d’un document depuis son serveur d’origine ;
Temps de modification : est le temps écoulé depuis la dernière modification d’un document ;
Temps d’expiration (TTL, Time To Live) : est la période de temps pendant lequel le document restera valide (cohérent).

Classification des politiques de remplacement de cache

Pour présenter les différentes propositions de politiques de remplacement de cache qui existent, d’une manière structurée, nous procédons d’abord à leurs classifications, selon les paramètres (caractéristiques) des documents, qui peuvent influencer le processus de remplacement. La plupart de ces paramètres sont décrits dans Krishnamurthy et Rexford.
On donne ci après un récapitulatif des paramètres importants :
1) récence : période (depuis) la dernière référence de document ;
2) fréquence : nombre d’accès à un document ;
3) taille : taille de document ;
4) coût de chargement: coût de chargement d’un document depuis son serveur d’origine;
5) temps de modification : période depuis la dernière modification ;
6) temps d’expiration (TTL) : est la période de temps pendant laquelle le document restera valide (cohérent). Quand cette période expire le document devient périmé et peut être remplacé immédiatement.

Les documents référencés une seul fois (one-timers)

Ce sont les documents qui ne sont accédés qu’une seule fois, dans la littérature ils sont communément appelé les one-timers. Des études ont montrés que ces documents constituent un grand pourcentage du trafic Web (jusqu’à 70 %). Il est évident que ces documents ne doivent pas être cachés car en réalité ils ne seront jamais accédés dans le futur, et ils ne font que réduire les performances des caches. Par conséquent, les politiques de remplacement de cache doivent se doter de mécanisme de contrôle d’admission au cache et avoir la capacité de distinguer ces documents parmi d’autres.
Du point de vue positif, les one-timers peuvent être considérés comme une conséquence logique et inévitable de l’efficacité des mécanismes et techniques utilisés dans le cadre des caches Web comme les politiques de remplacement, le perfetching, la réplication, les proxys etc. L’un des objectifs de ces techniques est de réduire la charge des proxys et des serveurs originaux, donc les one-timers s’explique par le fait que ces derniers ne sont pas atteint par les requêtes répétées pour le même document parce qu’elles étaient servies au niveau des caches.

Table des matières

Introduction générale
1 Etude des réseaux mobiles Ad Hoc
1.1 Introduction
1.2 Définition
1.3 Les domaines des réseaux mobiles Ad Hoc
1.3.1 Domaine militaire
1.3.2 Situation de sinistres
1.3.3 Réseaux locaux
1.4 Les caractéristiques des réseaux Ad Hoc
1.4.1 Bande passante
1.4.2 Portée radio limitée
1.4.3 Interférences
1.4.4 Energie
1.4.5 Mobilité et changement de topologie
1.4.6 Sécurité
1.5 Les normes des réseaux locaux sans fil
1.5.1 Le Bluetooth
1.5.2 L’ HiperLAN 1
1.5.3 L’HiperLAN 2
1.5.4 La 802.11
1.5.4.1 La couche physique
1.5.4.2 La couche MAC
1.5.4.3 Les différentes extensions de la norme 802.11
1.6 Le routage dans les réseaux Ad Hoc
1.6.1 Les approches de routage des réseaux mobiles Ad Hoc
1.6.1.1 L’architecture de routage
1.6.1.2 Les techniques utilisées pour le routage
1.6.1.3 Les familles de protocoles de routage
1.6.2 Présentation de quelques protocoles de routage des réseaux Ad Hoc
1.6.2.1 Ad Hoc On-demand Distance Vector (AODV)
1.6.2.2 Optimized Link State Routing (OLSR)
1.6.2.3 Dynamic Source Routing (DSR)
1.6.2.4 Zone Routing Protocol (ZRP)
1.7 Conclusion
2 Les caches et les réseaux mobiles Ad Hoc
2.1 Introduction
2.2 Classification des caches
2.2.1 Organisation interne des caches
2.2.1.1 Le cache non bloquant
2.2.1.2 Le cache victime
2.2.1.3 Le cache en mode pipeline (pipelining)
2.2.2 Localisation des caches
2.2.2.1 Le cache de navigateur
2.2.2.2 Le cache de Proxy
2.2.2.3 Le cache de serveur d’origine
2.2.3 La fonction des caches
2.2.3.1 Les caches CPU traditionnels
2.2.3.2 Les caches Web
2.2.3.3 Les caches des systèmes mobiles
2.3 Fonctionnement de cache
2.3.1 Support HTTP pour le cache
2.3.2 Cachabilité des documents
2.3.3 Défaut/succès de cache (cache hits/misses)
2.3.4 Mécanismes de validation/invalidation de documents
2.3.4.1 Mécanismes de validation
2.3.4.2 Mécanismes d’invalidation
2.3.5 Le préchargement (Prefetching)
2.3.6 Politique de remplacement de cache
2.3.6.1 Les métriques des politiques de remplacement
2.3.6.2 Les algorithmes de remplacement de caches
2.4 L’apport d’utilisation de cache dans les réseaux Ad Hoc
2.4.1 Réduction de la latence
2.4.2 Sauvegarde de la bande passante
2.4.3 Augmentation de l’accessibilité des données
2.5 Conclusion
3 Les politiques de remplacement de caches
3.1 Introduction
3.2 Classification des politiques de remplacement de cache
3.2.1 Les stratégies de remplacement de cache basées sur la récence
3.2.1.1 LRU
3.2.1.2 LRU-Threshold
3.2.1.3 SIZE
3.2.1.4 LRU-Min
3.2.1.5 EXP1
3.2.1.6 HLRU
3.2.1.7 PSS (Pyramidal Selection Scheme)
3.2.1.8 Avantages
3.2.1.9 Inconvénients
3.2.2 Les stratégies de remplacement de cache basées sur la fréquence
3.2.2.1 LFU
3.2.2.2 LFU-Aging
3.2.2.3 LFU-DA
3.2.2.4 SWLFU (Server-Weighted LFU)
3.2.2.5 Fréquence relative de Benhamida
3.2.2.6 Avantages
3.2.2.7 Inconvénients
3.2.3 Les stratégies de remplacement de cache basées sur la récence et la fréquence
3.2.3.1 SLRU (Segmented LRU)
3.2.3.2 LRU*
3.2.3.3 LRU-Hot
3.2.3.4 HYPER-G
3.2.3.5 LRU-K
3.2.3.6 Avantages
3.2.3.7 Inconvénients
3.2.4 Les stratégies de remplacement de cache basées sur les fonctions
3.2.4.1 GD (Greedy Dual)-Size
3.2.4.2 GDSF
3.2.4.3 TSP (Taylor Series Prediction)
3.2.4.4 Stratégie de Bolot et Hoschka
3.2.4.5 LRV
3.2.4.6 Avantages
3.2.4.7 Inconvénients
3.3 Les stratégies de remplacement de cache dédiées aux environnements mobiles
3.3.1 La politique TDS (Time and Distance Sensitive)
3.3.2 La politique ZC (Zone coopérative)
3.3.3 Politique de remplacement de cache orientée énergie
3.3.4 La politique de remplacement de cache PIX
3.3.5 La politique Min-SAUD
3.4 Proposition d’une politique de remplacement de cache pour les réseaux Ad Hoc
3.5 Conclusion
4 Caractérisation de trafic, modélisation et simulation
4.1 Introduction
4.2 Les méthodes d’évaluation de performances
4.2.1 Mesures directes
4.2.2 Analyse mathématique
4.2.3 Simulation basée sur les traces
4.2.4 Simulation basée sur le benchmarking
4.3 Etat de l’art sur la caractérisation du trafic
4.3.1 La popularité des documents
4.3.2 La taille des documents
4.3.3 La localité des références
4.3.3.1 La localité temporelle
4.3.3.2 La localité spatiale
4.3.4 Les documents référencés une seul fois (one-timers)
4.3.5 Le taux de modification des documents
4.3.6 Le type des documents
4.4 Modélisation et génération de trafic
4.4.1 Modèle de simulation
4.4.2 La génération de trafic
4.4.3 Environnement de simulation
4.4.4 Validation du simulateur
4.4.5 Les caractéristiques statistiques de trafic généré
4.4.5.1 la distribution des tailles de documents
4.4.5.2 la distribution des TTL de documents
4.5 Résultats de la simulation
4.5.1 Impact du paramètre de l’âge moyen maximum sur la politique FSDV .
4.5.2 Influence de la taille du cache
4.5.2.1 Taux de succès de FSDV en comparaison avec LRU et LFU
4.5.2.2 Taux de succès de FSDV en comparaison avec TDS et ZC
4.5.2.3 Taux de succès en octets de FSDV en comparaison avec LRU et LFU
4.5.2.4 Taux de succès en octets de FSDV en comparaison avec TDS et ZC
4.5.2.5 Taux de succès en distance de FSDV en comparaison avec LFU et LRU
4.5.2.6 Taux de succès en distance de FSDV en comparaison avec TDS et ZC
4.5.3 Impact du paramètre de la loi de distribution Zipf
4.5.3.1 Taux de succès de FSDV en comparaison avec LFU et LRU
4.5.3.2 Taux de succès de FSDV en comparaison avec TDS et ZC
4.5.3.3 Taux de succès en octets de FSDV en comparaison avec LFU et LRU
4.5.3.4 Taux de succès en octets de FSDV en comparaison avec TDS et ZC
4.5.3.5 Taux de succès en distances de FSDV en comparaison avec LFU et LRU
4.5.3.6 Taux de succès en distances de FSDV en comparaison avec TDS et ZC
4.6 Conclusion
Conclusion générale

Télécharger le rapport complet