Cours Interconnexion de réseaux et routage avancé

Introduction

  • Un réseau informatique est une interconnexion d’un ensemble d’équipements permettant l’échange d’information entre les terminaux (généralement des PC).
  • L’interconnexion peut être :
    • Câblée (réseau filaire)
    • Sans fil (réseau Wifi, Wimax, UMTS, GSM,etc).
  • Les équipements d’interconnexion peuvent être :
    • Niveau 1: répéteur, concentrateur (couche physique)
    • Niveau 2: pont, commutateur (couche liaison de données)
    • Niveau 3 : Routeur, commutateur (couche réseau)
  • L’administration des réseaux informatiques comprend :
    • La mise en place des équipements si c’est nécessaire (équipe spécialisée pour l’installation).
    • La configuration des équipements d’interconnexion (au-delà du niveau 2).
    • Mise en place de stratégies pour la sécurité d’accès :
      • Interne (réseau local)
      • Externe (accès à travers le réseau WAN)
    • La gestion  réseau :
      • Supervision de l’activité des équipements réseau (continuité du service)
      • Gestion de performance (qualité du service) n
  • De nos jours, les concepteurs de réseaux tendent à délaisser les ponts et les concentrateurs au profit des commutateurs et des routeurs
  • Ethernet est l’architecture LAN la plus répandue utilisée pour transporter des données entre les unités d’un réseau
  • Le média Ethernet utilise un mode de broadcast de trames de données pour transmettre et recevoir des données entre tous les nœuds du média partagé
Le média Ethernet - routage

Le mode Ethernet half-duplex

  • Ethernet est fondé sur une technologie half-duplex
  • Chaque hôte Ethernet vérifie le réseau pour savoir si des données sont en cours de transmission avant de transmettre des données supplémentaires
  • Lorsqu’une collision se produit, l’hôte qui détecte la collision en premier envoie un signal de bourrage
Le mode Ethernet half-duplex

Le mode Ethernet full-duplex

  • permet de transmettre un paquet et d’en recevoir un autre simultanément qui nécessitent l’utilisation d’un câble contenant deux paires de fils et d’une connexion commutée entre chaque nœud.
  • Cette connexion est considérée comme une connexion point à point et s’effectue sans collision
  • Comme les deux nœuds peuvent transmettre et recevoir en même temps, il n’y a pas de négociation pour l’obtention de la bande passante
  • Le mode Ethernet full duplex offre 100 % de la bande passante dans les deux directions 

La segmentation LAN

  • Un réseau peut être divisé en unités plus petites appelées segments
  • Chaque segment utilise le mode d’accès CSMA/CD et assure le trafic entre les utilisateurs sur le segment
  • La division du réseau en plusieurs segments permet à un administrateur réseau de réduire la congestion réseau à l’intérieur de chaque segment
  • Dans un LAN Ethernet segmenté, les données échangées entre les segments sont transmises sur la backbone du réseau en empruntant un pont, un routeur ou un commutateur
  • La segmentation permet d’isoler le trafic entre les segments et augmenter la bande passante disponible 
La segmentation LAN. routage

La segmentation avec les commutateurs

  • Un commutateur peut segmenter un LAN en microsegments, qui sont des segments à hôte unique
  • Cela a pour effet de créer des domaines sans collision à partir d’un grand domaine de collision n n
La segmentation avec les commutateurs

La commutation LAN

  • Il existe deux méthodes pour effectuer la commutation des trames de données : la commutation de couche 2 et la commutation de couche 3
  • La commutation est un processus qui consiste à prendre une trame entrante sur une interface et à l’acheminer par une autre interface
  • Les routeurs utilisent la commutation de couche 3 pour acheminer un paquet
  • les commutateurs utilisent la commutation de couche 2 pour acheminer les trames
  • Dans le cas de la commutation de couche 2, les trames sont commutées en fonction des adresses MAC
  • Dans le cas de la commutation de couche 3, les trames sont commutées selon les informations de couche réseau  
  • La commutation de couche 2 crée et met à jour une table de commutation qui consigne les adresses MAC associées à chaque port ou interface
  • Si le commutateur de couche 2 ne sait pas où envoyer la trame, il l’envoie par tous ses ports au réseau pour connaître la bonne destination
  • Lorsque la réponse est renvoyée, le commutateur prend connaissance de l’emplacement de la nouvelle adresse et ajoute les informations à la table de commutation

Comment un commutateur prend-il connaissance des adresses ?

  • Un commutateur Ethernet peut apprendre l’adresse de chaque unité sur le réseau en lisant l’adresse d’origine de chaque paquet transmis et en enregistrant le port par lequel la trame est entrée dans le commutateur
  • Le commutateur ajoute alors ces informations à sa base de données d’acheminement
  • Lors de la lecture d’une source qui ne se trouve pas dans la mémoire associative, elle est enregistrée et stockée en vue d’une consultation ultérieure.
  • Les adresses qui ne sont pas consultées durant une période déterminée sont éliminées de la liste.
Comment un commutateur prend-il connaissance des adresses ?

Les types de commutation:

Il existe 3 types de commutation:

  1. Commutation de circuits
  2. Commutation de messages
  3. Commutation de paquets

Commutation de circuits:

Commutation de circuits: Dans la commutation de circuits, un circuit (fréquentiel ou temporel) est établi entre l’émetteur et le récepteur. Ce mode se caractérise essentiellement par la réservation des ressources de communication.

Le service offert est orienté connexion où on distingue trois étapes:

    -Etablissement de la connexion

    –Transfert de l’information

Les applications classiques de ce type de réseau sont celles à contrainte temporelle telles que le service téléphonique et toutes les applications “streaming“.

L’inconvénient majeur est le gaspillage possible de la Bande Passante.=>Réserver n’est pas Utiliser.

Commutation de Messages:

Dans la Commutation de Messages, il n’y a pas de réservation de ressources. Ainsi, les messages qui arrivent dans le nœud de commutation sont traités selon l’ordre d’arrivée, file FIFO (First In First Out). S’il y a trop de trafic, il y a attente dans la file.

=>  le temps de traversée du réseau n’est pas constant.

La technique utilisée est le Store & Forward. Si on rajoute au traitement de routage, le traitement d’erreurs et d’autres traitements pour assurer un service fiable de transmission, le temps d’attente augmente.

=>L’avantage de cette technique est une meilleure utilisation des ressources.

Commutation de paquets:

Commutation de paquets

Amélioration de commmutation de message => découper le message en unités de données en packets.

En effet, la même technique (Store & Forward) est

utilisée avec deux avantages:

  • Effet pipe line.
  • Temps d’émission plus réduit.

=>Le problème à résoudre est le réassemblage du message avant de le donner à la couche supérieure.

Les services offerts par un réseau à  commutation de paquets :

  • Service orienté connexion:

les paquets  arrivent dans l’ordre d’émission à la station destinatrice.

On parle ainsi de Circuit Virtuel.

Circuit virtuel:

  • système de communication.
  • les données d’un utilisateur source peuvent circuler sur différents circuits réels.
  • Changements de circuit, sont totalement transparents à l’utilisateur

-Service orienté Sans Connexion:

Les paquets arrivent chez le destinataire sans aucune garantie de séquencement.

En effet, si les paquets ont pris différents chemins ils risquent d’arriver dans le désordre.

On parle ainsi de Datagramme.

Datagramme:

  • Chaque paquet contient l’adresse du destinataire et acheminé indépendamment des autres paquets avec le risque d’arrivée dans le désordre.
  • Si le routage est fixe, les paquets suivant le même chemin, ils arriveront dans l’ordre.

Les différents types de routage

  • Routage statique:
    • Les tables de routages sont configurées d’une manière statique par l’administrateur réseau (utilisé pour les petits réseaux : rapidité)
    • Les routes ne peuvent changer que par intervention de l’administrateur
  • Routage dynamique
    • Les routes changes périodiquement par les algorithmes de routages appliqués (utilisé pour les grands réseaux : fiabilité)
    • Les routes sont adaptatives selon l’état de connexion et le coût des liaisons

Routage statique

Routage statique
routage par defaut
exemple de route statique
Router (config) # ip route réseau [masque] {adresse | interface} [distance]

Routage statique par défaut

Routage statique par défaut cisco
Router (config) # ip default network numéro de réseau
  • Permet de réduire les entrées dans la table de routage

Routage dynamique (adaptatif)

adaptation aux changements topologiques
fonctionnement du routage dynamique

Systèmes de routage interne de l’Internet

Connus par Interior Gateway Protocols (IGP)

Les protocoles les plus utilisés :

  • RIP: Routing Information Protocol
  • OSPF: Open Shortest Path First
  • BGP : Border Gateway Protocol
  • IGRP: Interior Gateway Routing Protocol (Cisco proprietary)

Description et critique des protocoles de routage

Le routage

  • Le routage est l’opération permettant de choisir le chemin vers la destination.
  • Le routage est assuré par des protocoles basés sur des algorithmes.
  • L’algorithme du protocole dépend de l’environement réseau.

Algorithme de routage pour les réseaux sans fils

Les réseaux sans fils sont:

  • Réseaux sans fils avec infrastructure
  • Réseaux sans fils AdHoc

Les stratégies de routage 

  • La minimisation de la charge du réseau
  • Offrir un support pour pouvoir effectuer des communications multi-points fiables
  • Assurer un routage optimal en considerant differents metriques de couts
  • Le temps de latence

Evaluation des protocoles de routage

Tout simulateur doit être en mesure d’évaluer :

  • Le contrôle utilisé dans le mécanisme de mise à jour de routage.
  • Les délais moyens du transfert des paquets.
  • Le nombre moyen de nœuds traversés par les paquets de données.

Les protocoles de routage

Les protocoles de routage 
bases sur la localisation et independants de la localisation

Protocole de routage réactif 

  • représentes les protocoles les plus récents proposés dans le but d’assurer le service du routage dans les réseaux sans fil.
  • La majorité des solutions proposées pour le routage dans les réseaux Ad Hoc évaluées par le groupe de travail MANET ainsi que l’IETF appartient à cette classe de protocoles

Le protocole de routage DSR

Le protocole “Routage à Source Dynamique” (DSR : Dynamic Source Routing), est basé sur l’utilisation de la technique “routage source”

Fonctionnement du protocole DSR

Le protocole de routage AODV

  • Le protocole “Routage avec Vecteur de Distance à la Demande” (AODV : Ad hoc On-demand Distance Vector). L’AODV est basé sur l’utilisation des deux mécanismes “Découverte de route” et “Maintenance de route” (utilisés par le DSR), en plus du routage nœud-par-nœud

Une entrée de la table de routage contient essentiellement :

  • L’adresse de la destination. nLe nœud suivant.
  • La distance en nombre de nœud (i.e. le nombre de nœud nécessaire pour atteindre la destination).
  • Le numéro de séquence destination. nLe temps d’expiration de l’entrée de la table

Principe de fonctionnement du protocole AODV

Principe de fonctionnement du protocole AODV

Avec :

  • Route Request : “J’ai besoin d’une route”
  • Route Response : “Annoncer la Route”
  • Route Error : “Annuler la route”
  • Réponses périodiques (similaire aux messages « hello ») pour l’installation et le  renouvellement de la route

Les protocoles de routage proactifs

  • Les protocoles de routage proactifs pour les réseaux mobiles ad-hoc, sont basé sur la même philosophie des protocoles de routage utilisés dans les réseaux filaires conventionnels, et se base sur les protocoles à états de lien et les protocoles à vecteurs de distance

Le protocole  OLSR (Optimized Link State Routing)

  • C’est un protocole proactif à état des liens optimisé ; il permet d’obtenir aussi des routes de plus court chemin
  • Diffusion pure et diffusion en utilisant les MPR
Le protocole  OLSR (Optimized Link State Routing)

Le protocole  OLSR

  • les relais multipoints sont déclarés périodiquement dans le réseau. Ils sont diffusés en utilisant une diffusion optimisée par relais multipoints
  • La table de routage est calculée par chacun des nœuds et le routage des données s’effectue saut par saut sans l’intervention d’OLSR dont le rôle s’arrête à la mise à jour de la table de routage

Routage Ad-Hoc

le routage ad-hoc

Solution

Routage basé sur l’emplacement physique

Hypotheses

  • Chaque noeud connait son emplacement
    • Par GPS
  • la source peut localiser la destination
  • Le lien est bidirectionnel

Mécanisme de routage

Parmi les mécanismes utilisés dans les algorithmes de routage, on cite:

  • L’algorithme Dijkstra
  • Le mécanisme de Greedy Forwarding
  • La régle right-hand

Algorithme Dijkstra

Algorithme Dijkstra plus courte chaine du sommet
Algorithme Dijkstra  2
ABCDEFGHIJSélCoef
0C0
4 C 10 C16 CA4
 14 A 8 A16 C14 AD8
 14 A  16 C14 A29 DB14
    16 C14 A29 D31 B24 BF14
    16 C 29 D 17 F31 B24 BE16
      20 E17 F31 B24 BH17
      20 E 31 B22 HG20
        31 B22 HJ22
        30 J I30
  • Alors le chemin le plus optimum pour arriver à la destination est C, A, F, H, J, I
  • Par la suite, on utilisera ce principe pour le protocole de routage proposé

La régle: Right-Hand Rule

La régle: Right-Hand Rule
  • Appliquer la régle right-hand pour affronter le vide:
  • Choisir le prochain front vers la gauche

x envoie le paquet vers u pour arriver à la destination D

En utilisant le mécanisme Right-hand rule il en résulte le circuit suivant xuz-D

Limite de la régle: Right-Hand Rule

Limite de la régle: Right-Hand Rule

x envoie le paquet vers u pour arriver à la destination D

En utilisant le mécanisme de la régle Right-hand il en résulte le circuit suivant xuzwux

Problème de rebouclage

Le mécanisme de Greedy Routing

Le mécanisme de Greedy Routing

– Chercher le voisin le plus proche de la destination

– Envoyer le paquet au voisin le plus proche de la destination

Avantages de GF

  • Le nœud peut se rappeler uniquement de l’emplacement d’un seul nœud de ses voisins
  • Le décision de routage est dynamique

Limite de Greedy Forwarding

Limite de Greedy Forwarding

La méthode GF réussit dans le cas où  le réseau est suffisamment dense de telle façon à ce qu’il aura un noeud mobile chaque 120°

Solution pour GF

  • Le principe de Store and Forwarding, ie que le noeud mobile garde le paquet jusqu’à ce qu’il trouve un noeud mobile dans sa portée
  • Dans le cas où il y’a plusieurs noeuds mobiles candidats, le noeud mobile d’envoi choisit celui possédant la vitesse la plus élevée

Limite de Greedy Forwarding

Limite de Greedy Forwarding
  • On suppose que A a une vitesse Va<Vb (vitesse de B), la vitesse de B est plus grande, que celle de A, permettant d’atteindre la limite de la portée du noeud mobile d’envoi  avant le noeud mobile A dans le cas où ce  noeud mobile n’a aucun  noeud mobile à sa portée dans la direction de la déstination
  • Alors il fallait envoyer le paquet au noeud mobile B au lieu du noeud mobile A pour arriver le plus rapide possible à la destination

Protocole de routage

Parmi les problèmes posés par les protocoles de routage dans les réseaux des Manets, l’absence de solutions distribuées en terme de d’utilisation radio et qui permettent de caractériser d’une manière fine la densité linéaire d’un tronçon de route dans un environnement urbain

Le routage géographique

Le routage géographique utilise le mécanisme d’envoi des paquets basé sur :

  • La position géographique de :
    • La source
    • La destination
    • Les voisins
  • La fonction de routage supporte les types de communications suivantes :
    • Communications point à point
    • Communications  point – multipoint
    • Communication geo-anycast
    • Communication geo-broadcast

GSR (Geographic Source Routing)

  • Dédié pour le milieu urbain
  • Combine un routage basé sur la position et les informations topologiques
  • Utilise les informations cartographique (street map) pour calculer le chemin le plus court en utilisant l’algorithme dijkstra

Telecharger PDF