Chapitre VIII

La couche réseau(2)

1

Sommaire1.Introduction2.Services de la couche Réseau offerts3.Fonctions assumées par la couche

Réseau1. Commutation2. notion d'adressage et de nommage 3. L'acheminement dans le réseau4. Adaptation de la taille des unités de données5. La congestion dans les réseaux

2

L'acheminement dans le réseau

3

Le Routage

Routeur : noeud du réseau qui joue un rôle dans l'acheminement des paquets vers le destinataire final (niveau 3 OSI)

Fonctionnalité principale de la couche Réseau qui consiste à déterminer le chemin qui doit être utilisé par les paquets pour arriver à destination.

Chaque noeud intermédiaire doit choisir vers quel noeud (qualifiés de prochain noeud) il doit envoyer un paquet entrant pour que celui-ci arrive à destination.

En mode datagramme, le choix est effectué indépendamment pour chaque paquet. En mode circuit virtuel, le choix est fixé à l’établissement de la connexion, et pour toute la durée de la connexion.

Dans chaque noeud, ces choix sont effectués en se servant d’informations contenues dans une table de routage qui contient les noeuds suivants utilisables pour atteindre la destination.

Les entrées d’une table de routage sont renseignées soit statiquement, soit dynamiquement à l’aide d’algorithme de mise à jour des tables de routage se basant sur différents critères (débit possible, disponibilité de la ligne, taux d’erreurs, nombre de noeuds intermédiaires,...)

Fonctions d’un routeur :commutation des paquets (“datagram forwarding”), c-à-d retransmission des paquets. mise à jour des tables de routage - algorithme de routage.

4

Tables d'acheminement

Chaque routeur contient une table de routage ou table d'acheminement Chaque entrée de la table contient un triplet <@destination, route à prendre, coût>

le paquet doit contenir une information qui permet d'identifier le destinataire pour que le routeur puisse prendre une décision (@destination) "route à prendre est aussi appelé « next hop »  (prochain saut) "coût" permet de choisir la route appropriée si plusieurs routes sont possibles (coût pour atteindre la destination)

Dest Next coût

D

D

E

F

C

…

R3

R4

R3

R4

R3

…..

2

1

3

4

2

.. 5

Routage par le plus court chemin

La route pour atteindre le destinataire est déterminée en calculant le plus court chemin pour atteindre le destinataire.

Chaque lien inter-routeur a un coût (métrique) qui peut être calculé selon le nombre de saut (nombre de routeurs traversés) la distance réelle (en km) entre deux routeurs le délai de transmission le nombre de paquets moyen dans les files d'attente le taux d'erreurs moyen, le trafic moyen observé, …

Chaque routeur peut disposer de plusieurs tables de routage (une par critère) -> la route prise dépend alors de la qualité de service demandée

6

Politiques et protocoles de routage

Politiques de routage : comment la route est-elle choisie ? politique déterministe : la décision de routage ne dépend pas de l'état du réseau ; le choix de la route est défini une fois pour toute lors de l'initialisation politique adaptative : le chemin emprunté est fonction de données sur l'état du réseau ; les tables de routage sont régulièrement mises à jour politique mixte : en mode orienté connexion (circuit virtuel), le chemin est établi de manière adaptative puis les données sont échangées de manière déterministe

Protocoles de routage : comment sont construites et mises à jour les tables de routage ? C- à - d qu’il spécifie les échanges d’information entre nœuds, le mode de calcul de la route et du coût.

Les tables de routage sont mises à jour de manière : statique dynamique

7

Routage statique ou Routage fixe

Routage statique les tables sont mises à jour par l’administrateur uniquement quand la topologie du réseau change simple mais ne recherche pas la route optimale et n'est pas adapté à la défaillance d'un lien adapté aux petits réseaux et aux réseaux dans lesquels le choix de la route est limité (routes rentrées manuellement) assure le séquencement des paquets même en mode non connecté (tous les paquets prennent la même route)

8

Routage dynamique

Routage dynamique Remplissage automatique des tables de routage Protocoles de routage entre routeurs

Principe : Échange de messages (info de routage) entre les équipements de commutation (périodiquement) Traitement des messages par les algorithmes de routage Mettre à jour la table de routage Permettre la reconfiguration rapide lors d’un changement de topologie du réseau

Deux problèmes :Consommation de la bande passante (messages)Possibilité de non convergence des algorithmes (bouclage) 9

Algorithme du vecteur distance (1)

Algorithme de Bellman-Ford, Cette famille de protocoles est basée sur un algorithme de recherche du plus court chemin dans un graphe. Un routeur diffuse régulièrement à ses voisins les routes qu’il connaît

toutes les 30 secondes La liste des réseaux qu’il peut atteindre La distance (nombre de sauts)

L’émission périodique permet de prendre en compte : les évolutions du réseau La coupure des liaisons La panne de un ou de plusieurs routeurs

Une route est composée : adresse destination (adresse réseau)

adresse de passerelle métrique : nombre de sauts pour atteindre la destination

Traitement fait par le routeur : Met à jour sa propre table de routage :Si une route reçue comprend un plus court chemin : nombre de sauts + 1 (le coût pour atteindre son voisin)Si la route n’est pas connue

Sinon, il n’y a pas de changement Émet sa table de routage (si modifications) à l’ensemble des routeurs voisins

10

Routage par vecteur de distance(2)

Avant les annonces (rose)Après les annonces les tables de routage deviennent (bleu) 11

Routage par vecteur de distance(3) Problème de convergence

rapide lorsque tout se passe bien sur le réseau moins vite lorsqu’un routeur ou une liaison est en panne aucune annonce de routes de son voisin (depuis 180 s),

met la métrique pour atteindre ce voisin à l’infinicontinue à annoncer cette route à ses voisins durant 180speut provoquer des bouclesconvergence à un temps infini

12

Routage par vecteur de distance (4)

Dans le cas où R3 tombe en panne (Res4 n’est pas accessible)

R2 le détecte et met le coût vers Res4 à l’infini

R1 possède une route vers Res4 dont le coût est 2

R2 met à jour sa table de routage suite à cette annonce Res4 accessible en passant par R1 avec un coût = 3 (2+1) R1 fait passer le coût pour atteindre Res4 à 4 (3+1) Ainsi de suite …. La convergence prend un temps infini

Solutions:

Diminuer la valeur de l’infini

Horizon coupé ou « split horizon » 13

1. Diminuer la valeur de l’infini Le protocole RIP (Routing Information Protocol) diminue la valeur de l’infini à 16

Si la métrique associée à une route est 16, le réseau n’est plus accessible Réduit le temps de convergence

2. Horizon coupé ou split horizon » Un routeur ne doit jamais annoncer la route vers un réseau qui doit traverser la route du destinataire

Si R3 devient inaccessible, R2 le détecte et met le coût de la route vers Res4 à l’infini Les routeurs R1 et R4 n’ont pas le droit d’annoncer la route à R2 vers Res4 Le routeur R4 voit que R1 offre un coût de 2 pour atteindre Res4 (R2 propose l’infini) R4 modifie sa table de routage R4 peut diffuser l’information à R2 R2 pense que R4 peut atteindre Res4 avec un coût de 3, etc…

14

Routage à état des laisons (1) (OSPF (Open Shortest Path First))

Problème du routage à vecteur de distance : la seule info que connaît un routeur est le coût pour atteindre chaque destination la convergence peut être longue sur de grands réseaux (les routeurs n’ont la connaissance d’un changement d’état du réseau que lorsque leur voisin le leur communique)

solution : chaque routeur doit avoir une vision globale du réseau : algorithme d’état de liaisons

préféré lorsque le réseau devient important RIP limité à de petits réseaux

Principe du routage à état des liens : chaque nœud détermine le coût de chaque lien qui lui est raccordé en cas de modification de cet état, le nœud diffuse cette information dans le réseau, sous la forme (A,B,c), le lien du nœud A vers nœud B à un coût de c. chaque nœud entretien une table où figure pour chaque lien son coût (matrice de coût). À l’aide de ces informations, chaque nœud peut construire la cartographie complète du réseau. À partir de ces informations, il calcule la table de routage. 15

Chaque passerelle détermine sa table deroutage en utilisant cette base de données et se basant sur l’algorithme du plus court chemin (SPF: Shortest Path First)

Routage à état des liaisons (2)

16

Routage à état des laisons (3)

L’algorithme utilise deux structures :

PATH (l’état validé)contient le plus court chemin pour aller d’un routeur à un autre A l’état initial, PATH contient le routeur qui calcule le plus court chemin (la racine)

TENT : contient les tentatives de chemins possibles non encore explorés (l’état découverte ou état d’attente)

Examiner pour chaque routeur R de PATH les voisins immédiats

Pour chaque voisin R’ de R, ajouter le coût de la liaison racine-R au coût de la liaison R-R’

Si R’ n’est ni dans PATH ni dans TENT avec un meilleur coût, insérer R’ dans TENT (état d’attente : après découverte une route peut être rejetée, s’il en existe déjà une route de moindre coût pour joindre le nœud d’extrémité )

Reprendre l’algorithme : Considérer une entrée dans TENT qui a un coût plus faible L’insérer dans PATH Calculer du coût de la liaison de la racine à ces voisins L’insérer dans PATH si le plus court chemin

L’algorithme est terminé si la structure TENT est vide17

18

Routage hiérarchique

Les protocoles de routage nécessitent la diffusion d'informations à travers le réseau

surcharge du réseau au détriment des données à écouler plus le réseau est grand, plus les échanges sont importants, plus les tables consomment de la mémoire et plus la convergence est longue

Routage hiérarchique découpage du réseau en domaines (AS = Autonomus System) des routeurs de bordure (gateways ou edge routers) réalisent l'interconnexion des domaines limite les diffusions inhérentes au routage

Protocoles de routage intra et inter domaines IGP (Interior Gateway Protocol) : routage interne au domaine -> ignore les noeuds externes au domaine EGP (External Gateway Protocol) : gère l'échange d'information de routage entre domaines le routeur de bordure doit supporter le protocole interne à son domaine et un protocole externe

19

Les principaux protocoles de routage

RIP (Routing Information Protocol) protocole interne au domaine de type vecteur distance largement utilisé dans Internet RIP (RFC 1058), RIP-2 (RFC 1723)

OSPF (Open Short Path First) - RFC 2178 protocole interne à état des liens largement utilisé dans Internet (tend à remplacer RIP)

IS-IS (Intermediate System to Intermediate System) protocole de routage interne à état des liens, ISO 10589

EIGRP (Enhanced Interior Gateway Routing Protocol) protocole propriétaire CISCO de type vecteur distance utilise une métrique complexe fonction du délai d'acheminement, du débit, de la fiabilité et de la charge du réseau

EGP (Exterior Gateway Protocol) - RFC 827 premier protocole externe utilisé dans Internet largement utilisé dans Internet

BGP (Border Gateway Protocol) - RFC 1771 protocole de routage utilisé dans Internet qui définit les échanges internes au domaine (iBGP) et externes (eBGP) 20

Ce qu’il faut retenir

Routage = fonction nécessaire pour acheminer les données dans un réseau maillé

Infos de routage transmis sur le réseau =>

Trouver des critères pour être efficace sans saturer le réseau

Retard inévitable dans la connaissance de la topologie (grands réseaux) => boucles possibles

Algorithmes les plus employés dans Internet :

à vecteurs de distance

à états des liaisons 21

Adaptation de la taille des unités de données

22

Notion de MTU

MTU - Maximum Transfer Unit Taille maximale des paquets admis dans le réseau (en-tête compris) Cette taille varie d'un réseau à l'autre et d'une couche à l'autre Si un paquet a une taille supérieure à la MTU, il doit être fragmenté en plusieurs blocs à l'entrée du réseau et réassemblé à la sortie

Pourquoi imposer une taille maximale ?

stockage des paquets dans les files d'attente des routeurs/commutateurs (mémoire limitée) au matériel (ex. taille des trames Ethernet) au protocole (nombre de bits réservés au champ longueur du paquet) limiter les retransmissions en cas d'erreurs limiter le risque de congestion (temps d'occupation du canal par un paquet)

Quelques MTU en octets

Ethernet (1500), Frame Relay (1600), Token Ring (4464 en 4Mbps, 17914 en 16Mbps)

23

Fragmentation et réassemblage

La fragmentation est réalisée par le routeur d'entrée qui doit reconstruire un en-tête d'acheminement pour chaque fragment

Mode non connecté les différents fragments peuvent arrivés dans le désordre les fragments doivent être numérotés et comptés le réassemblage ne peut se faire que sur le destinataire qui doit connaître le nombre de fragments attendus

Mode connecté (fragmentation transparente) le routeur de sortie peut reconstituer le paquet fragmenté chaque fragment contient uniquement un bit (bit More) d'information indiquant s'il s'agit du dernier fragment

24

Congestion dans le réseau

25

Qu'est ce que la congestion ?

Les routeurs/commutateurs ont des files d'attente finies ! Congestion légère

le trafic augmente -> les files d'attente des nœuds intermédiaires se remplissent -> le temps d'attente avant traitement dans les noeuds augmente -> le temps de transit dans le réseau augmente -> le débit des sources diminue globalement

Congestion sévère congestion légère -> les paquets retardés ne sont pas acquittés à temps -> ils sont retransmis -> le trafic augmente d'autant plus -> les files d'attente débordent -> le réseau s'effondre, tous les paquets sont perdus !

Causes des congestions : trop de paquets pour la ligne de sortie choisie processeur trop lent dans le routeur

26

Contrôle de Congestion vs Contrôle de flux

Contrôle de flux (préventif) ≠ Contrôle de congestion (réactif)

Contrôle de flux (rappel) l'émetteur utilise une fenêtre d'anticipation qui lui permet d'envoyer plusieurs messages sans acquittement du récepteur évite la surcharge du récepteur concerne l'état d'une communication point-à-point

• Exemple 1 : transfert d’un fichier entre une station Fast Ethernet et une station Ethernet 10BaseT

Contrôle de congestion évite que le réseau ait un trafic à écouler supérieur à ses capacités cherche à limiter le nombre de paquets en transit dans le réseau concerne l'état global du réseau

• Exemple 2 : cas d’un réseau WAN avec des liens à 1 Mbps et 1000 stations connectées

Le contrôle de flux participe à la prévention de la congestion en limitant le débit de certaines sources trop bavardes mais ne le résout pas complètement

27

Contrôle de congestion

Contrôle préventif - éviter la congestion contrôle de flux : asservir le débit des sources aux capacités de traitement de chacun des noeuds contrôle d'admission : ne pas admettre plus de trafic que le réseau ne peut en écouler (contrat de trafic) lissage du trafic : réguler le trafic irrégulier des sources (moins de congestion avec un trafic régulier et uniforme)

Contrôle réactif - guérir la congestion éliminer le trafic en excès (tout ou une partie) traiter les paquets plus prioritaires, rejeter des paquets moins prioritaires (marquage des paquets)Envoyer à la source ou aux sources responsables une demande de ralentissement contourner les zones encombrées

28