Protocoles et services réseaux

Mme Ines ABBES

17

Amélioration de la solution

Mme Ines ABBES

18

Amélioration de la solution

Mme Ines ABBES

19

Le routage en pratique

Mme Ines ABBES

20

Le routage en pratique

Mme Ines ABBES

21

Le routage en pratique

Mme Ines ABBES

22

Le routage en pratique

Mme Ines ABBES

23

Devenir routeur

Mme Ines ABBES

24

Protocoles et algorithmes

 Deux classes de protocole de routage

 Les protocoles de routage Intra-domaine

 Les protocoles de routage Inter-domaine

 Deux types d’algorithme de routage

 État de lien

 Vecteur de distance

Mme Ines ABBES

25

Système autonome

 Système autonome (domaine) (AS – Autonomous System)

 Ensemble des routeurs contrôlés par une même autorité

administrative et utilisant un même protocole de routage

Mme Ines ABBES

26

Algorithme de routage

 Objectif : choisir un « bon chemin » (suite de routeurs)

dans le réseau de la source à la destination.

 Abstraction du réseau en graphe

 Les nœuds sont des routeurs

 Les liens sont les liaisons physiques

5

B

2

D

2

A

1

3

C

1

E

3

1

F

5

2

 Coût du lien : délai, prix du lien ou niveau de congestion

 «Bon chemin» : Typiquement un chemin de coût minimal

Mme Ines ABBES

27

Classification des algorithmes de

routage (1)

Information globale ou locale ?

Globale :

 Chaque routeur connaît toutes les informations de

topologie, de coût des liens, etc.

 Algorithme “link state (LS)”

Locale :

 Le routeur ne connaît que le côut des liens vers les voisins.

 Calcul itératif et échange régulier d’infos avec les voisins

 Algorithmes “distance vector (DS)”

Mme Ines ABBES

28

Classification des algorithmes de

routage (2)

Statique ou dynamique ?

Statique :

 Les routes ne changent pas dans le temps

Dynamique :

 Les routes changent régulièrement

 Mise à jour régulière

 En réponse aux changement de coût des liens

Mme Ines ABBES

29

Un Algorithme de routage Link-State

(à état de lien)

Algorithme de Dijkstra

 La topologie et le coût des liens sont connus de tous les

nœuds

 accompli avec une diffusion de l’état des liens

 Tout les nœuds ont la même information

 Calculer le plus court chemin (le chemin le moins

coûteux) d’un nœud à tout les autres

 Génère la table de routage du noeud

 De façon itérative : après k itérations, on connaît le

chemin le plus cours vers K destinations

Mme Ines ABBES

30

Algorithme de Dijkstra

Notation :

 c(i,j) : coût du lien de i à j. Est infini si i et j ne

sont pas voisins

 D(v) : Valeur courante du coût du chemin de la

source à la destination V

 p(v) : noeud précédant v dans le chemin de la

source à v

 N : Ensemble des nœuds dont on connaît le coût

minimal

Mme Ines ABBES

31

Algorithme de Dijkstra

1 Initialisation :

2 N = {A}

3 Pour tout noeud v

4 si v est adjacent à A

5 alors D(v) = c(A,v)

6 Sinon D(v) = infinity

7 boucle

8 Trouver w  N tel que D(w) est minimal

10 ajouter w à N

11 Mettre à jour D(v) pour tout les nœuds v  N adjacents à w

12 D(v) = min( D(v), D(w) + c(w,v) )

13 jusqu’à la fin des nœuds de N

Mme Ines ABBES

32

Algorithme de Dijkstra : exemple

étapes

0

1

2

3

4

5

start N

A

AD

ADE

ADEB

ADEBC

ADEBCF

D(B),p(B)

2,A

2,A

2,A

D(C),p(C)

5,A

4,D

3,E

3,E

D(D),p(D)

1,A

D(E),p(E)

inf

2,D

D(F),p(F)

inf

inf

4,E

4,E

4,E

5

B

2

D

2

A

1

3

C

1

E

3

1

F

5

2

4 : Network Layer

4a-33

Algorithme de routage

Distance Vector (DV)

itératif :

 Continue jusqu’à ce que les nœuds ne s’échangent

plus d’info

 Auto-terminaison : pas de «signal» d’arrêt

asynchrone :

 L’échange des infos ne nécessite pas d’horloge

distribué :

 Chaque nœud ne communique qu’avec ses voisins

Mme Ines ABBES

34

Algorithme de routage DV

 Chaque nœud maintient une table de distances

 Une ligne pour chaque destination possible

 Une colonne pour chaque voisin direct

 D (Y,Z) = c(X,Z) + min {D (Y,w)}

x

z

w

 X: le noeud source (le noeud qui maintient la table)

 D (Y,Z): le coût du chemin de X à Y en passant par Z

 min {D (Y,w)}: le coût du chemin le plus court de Z à

x

z

w

Y

 c(X,Z): le coût du lien (X,Z)

Mme Ines ABBES

35

Table de distance : exemple

7

A

1

B

1

C

8

E

2

D

2

E

D (C,D)

E

D (A,D)

E

D (A,B)

c(E,D) + min {D (C,w)}

D

D

w

w

=

= 2+2 = 4

=

= 2+3 = 5

c(E,D) + min {D (A,w)}

boucle!

c(E,B) + min {D (A,w)}

B

=

= 8+6 = 14

w

boucle!

coût destination via

E

D ()

A

B

D

A

1

14

B

7

C

6

8

9

D

4

11

5

5

4

2

Mme Ines ABBES

36

Table de routage

coût destination via

E

D ()

A

B

D

Lien sortant , coût

A

1

14

B

7

C

6

8

9

D

4

11

5

5

4

2

A

A,1

B

D,5

C

D,4

D

D,2

Table de distance

Table de routage

Mme Ines ABBES

37

Algorithme de routage DV

Itératif, asynchrone : chaque itération locale est

causée par :

 Changement de coût d’un lien adjacent

 Message d’un voisin du au changement de sa table de

distance

Distribué :

 Chaque nœud annonce à ces voisins seulement quand

sa table de distance change

Mme Ines ABBES

38

Algorithme de routage DV

Chaque nœud:

Mme Ines ABBES

39

Algorithme de routage DV: exemple

Dans chaque nœud X:

1 Initialisation :

2 Pour tout nœud adjacent v :

3 D (*,v) = inf

4 D (v,v) = c(X,v)

5 pour toute destination y

6 envoyer min D (y,w) à

tous les voisins w

2

X

Y

7

1

Z

Mme Ines ABBES

40

Algorithme de routage DV : exemple

2

X

Y

7

1

Z

X

X

=

D (Y,Z)

= 7+1 = 8

c(X,Z) + min {D (Y,w)}

w

=

D (Z,Y)

= 2+1 = 3

c(X,Y) + min {D (Z,w)}

w

Z

Y

Mme Ines ABBES

41

Le protocole RIP

 Routing Information Protocol

 RFC 1058, 2453

 Protocole de routage à vecteur de distance

 Le coût du chemin est mesuré en nombre de sauts (15 au

maximum)

 Message de réponse RIP/ message d’annonce RIP

 Les routeurs échangent des information de routage (les

vecteurs de distance) avec leurs voisins directs toutes les

30 seconds

 Le vecteur de distance est une liste comprenant jusqu’à 25

réseaux de destination au sein du système autonome

Mme Ines ABBES

42

Le protocole OSPF

 Open Shortest Path First

 RFC 2328

 Protocole de routage à état de lien

 Le coût du chemin n’est pas forcément le nombre de sauts (à définir

par l’administrateur)

 Message Hello

 Échangés entre les voisins pour vérifier le bon état des liens

 Message d’annonce OSPF

 Les routeurs communiquent les informations de routage (les états des

liens) à tous les routeurs de leur système autonome, et pas seulement à

ses voisins directs

 Les messages d’annonces sont échangés d’une manière périodique (au

moins une fois toutes les demi-heures) et à chaque changement d’état

d’une liaison

43