PDF de programación - Clase 13 Tipos de algoritmos de enrutamiento - Enrutamiento Distance-Vector

Clase 13
Tipos de algoritmos de enrutamiento
Enrutamiento Distance-Vector
Tema 4.- Enrutamiento con IP

Dr. Daniel Morató
Redes de Ordenadores
Ingeniero Técnico de Telecomunicación Especialidad en
Sonido e Imagen, 3º curso

Temario

1.- Introducción
2.- Nivel de enlace en LANs
3.- Interconexión de redes IP
4.- Enrutamiento con IP
5.- Nivel de transporte en Internet
6.- Nivel de aplicación en Internet
7.- Ampliación de temas

Enrutamiento distance vector

1/25

Temario

1.- Introducción
2.- Nivel de enlace en LANs
3.- Interconexión de redes IP
4.- Enrutamiento con IP







Carácterísticas del enrutamiento dinámico en Internet
Tipos de algoritmos. Enrutamiento Distance-Vector
RIP
Problemas de RIP


5.- Nivel de transporte en Internet
6.- Nivel de aplicación en Internet
7.- Ampliación de temas

Enrutamiento distance vector

2/25

Objetivo
 Características de los tipos de algoritmos

de enrutamiento

Enrutamiento distance vector

3/25

Contenido
 Tipos de algoritmos de enrutamiento
 Algoritmos Distance-Vector

 Descripción
 Bellman-Ford

Enrutamiento distance vector

4/25

Contenido
 Tipos de algoritmos de enrutamiento
 Algoritmos Distance-Vector

 Descripción
 Bellman-Ford

Enrutamiento distance vector

5/25

Tipos de
Protocolos de Enrutamiento
Enrutamiento jerárquico
 Sistemas Autónomos (AS)
 Dentro de un AS:

 IGP = Interior Gateway Protocol

 Entre ASs:

 EGP = Exterior Gateway Protocol

AS 1

AS 2

Enrutamiento distance vector

AS 3

6/25

Tipos de
Algoritmos de Enrutamiento

informar

la
 Deben
topología y los cambios en la
misma

de

 Según cómo diseminan

la

información

Link State:
 Comunican

tienen y el coste

 Inundan la red
nodo
 Cada
topología entera

Distance Vector:
 Comunican estimación de

distancia a destinos
 Informan a vecinos
Path Vector:
 Comunican estimación de

caminos preferidos a destinos

AS 2

qué

vecinos

AS 1

conoce

la

Enrutamiento distance vector

AS 3

7/25

Tipos de
Algoritmos de Enrutamiento

e

t

t

a
S

k
n
L

i

r
o



t
c
e
V
e
c
n
a

t
s
D

i

r
o

t
c
e
V

h
t
a
P

A

A

A

2

1

2

1

2

1

B
C

B
C

B
C

1

3

1

3

1

3

D

D

D

0

0

0

0

A

A

2

1

2

1

1
B
C
3

B,D
B
C
C,D

A: [B, 2], [C, 1]
B: [A, 2], [D, 1]
C: [A, 1], [D, 3]
D: [B, 1], [C, 3]

D

A

No me gusta “B”

D

A

2

1

2

1

B
C

B
C

D

D

1

3

1

3

1

3

1

3

Enrutamiento distance vector

8/25

Contenido
 Tipos de algoritmos de enrutamiento
 Algoritmos Distance-Vector

 Descripción
 Bellman-Ford

 Algoritmos Path-Vector

Enrutamiento distance vector

9/25

 Cada nodo llega a conocer la distancia desde él a todos los

Distance Vector

destinos
 D(X,di)

 D(X,d)=c(X,d)

 Inicialmente cada nodo solo conoce la distancia a sus vecinos

 Periódicamente comunica D(X,d) a todos sus vecinos

 Informan con un vector con las distancias a los destinos

( D(X,d1), D(X,d2), D(X,d3), D(X,d4)…)

 Asíncrono

 Al recibir información actualiza:
 D(X,d)←mínj/c(X,j)<∞{c(X,j)+D(j,d)}

 Algoritmo de Bellman-Ford distribuido
 Empleado desde los comienzos de la ARPANET

Enrutamiento distance vector

10/25

Algoritmo de Bellman-Ford
B

A

 Comienzo

Dest
B
C
D
E

Next
B
-
-
E

Cost
1
∞
∞
1

Dest
A
C
D
E

Next
A
C
D
E

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
-
B
-
-

Cost
∞
1
∞
∞

Dest
A
B
C
E

D

Next
-
B
-
E

Cost
∞
3
∞
1

Dest
A
B
C
D

E

Next
A
B
-
D

Cost
1
1
3
4

Cost
1
4
∞
1

Enrutamiento distance vector

11/25

Algoritmo de Bellman-Ford
B

D(E,d)←mín{c(E,A)+D(A,d)}
D(B,d)←mín{c(B,A)+D(A,d)}
(…)

A envía

Dest
A
C
D
E

Next
A
C
D
E

Dest
B
C
D
E

A

Next
B
-
-
E

Cost
1
∞
∞
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
-
B
-
-

Cost
∞
1
∞
∞

Dest
A
B
C
E

D

Next
-
B
-
E

Cost
∞
3
∞
1

Dest
A
B
C
D

E

Next
A
B
-
D

Cost
1
1
3
4

Cost
1
4
∞
1

Enrutamiento distance vector

12/25

Algoritmo de Bellman-Ford
B

D(E,d)←mín{c(E,A)+D(A,d)}
D(B,d)←mín{c(B,A)+D(A,d)}

A envía

Dest
A
C
D
E

Next
A
C
D
A (E)

Dest
B
C
D
E

A

Next
B
-
-
E

Cost
1
∞
∞
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
-
B
-
-

Cost
∞
1
∞
∞

Dest
A
B
C
E

D

Next
-
B
-
E

Cost
∞
3
∞
1

Dest
A
B
C
D

Next
A
A (B)

E

-
D

Cost
1
1
3
2 (4)

Cost
1
2 (4)
∞
1

Enrutamiento distance vector

13/25

Algoritmo de Bellman-Ford
B

D(E,d)←mín{c(E,D)+D(D,d)}
D(B,d)←mín{c(B,D)+D(D,d)}
No hay cambios

D envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
-
-
E

Cost
1
∞
∞
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
-
B
-
-

Cost
∞
1
∞
∞

Dest
A
B
C
E

D

Next
-
B
-
E

Cost
∞
3
∞
1

Dest
A
B
C
D

E

Next
A
A
-
D

Cost
1
1
3
2

Cost
1
2
∞
1

Enrutamiento distance vector

14/25

B envía

Algoritmo de Bellman-Ford
B

D(A,d)←mín{c(A,B)+D(B,d)}
D(C,d)←mín{c(C,B)+D(B,d)}
D(D,d)←mín{c(D,B)+D(B,d)}
D(E,d)←mín{c(E,B)+D(B,d)}
(…)

Cost
1
∞
∞
1

Dest
B
C
D
E

A

Next
B
-
-
E

Dest
A
C
D
E

Next
A
C
D
A

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
-
B
-
-

Cost
∞
1
∞
∞

Dest
A
B
C
E

D

Next
-
B
-
E

Cost
∞
3
∞
1

Dest
A
B
C
D

E

Next
A
A
-
D

Cost
1
1
3
2

Cost
1
2
∞
1

Enrutamiento distance vector

15/25

Algoritmo de Bellman-Ford
B

D(A,d)←mín{c(A,B)+D(B,d)}
D(C,d)←mín{c(C,B)+D(B,d)}
D(D,d)←mín{c(D,B)+D(B,d)}
D(E,d)←mín{c(E,B)+D(B,d)}

B envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
B (-)
B (-)
E

Cost
1
2 (∞)
4 (∞)
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
B (-)
B
B (-)
B (-)

Cost
2 (∞)
1
4 (∞)
3 (∞)

Dest
A
B
C
E

D

Next
B (-)
B
B (-)
E

Cost
4 (∞)
3
4 (∞)
1

Dest
A
B
C
D

E

Next
A
A
B (-)
D

Cost
1
1
3
2

Cost
1
2
5 (∞)
1

Enrutamiento distance vector

16/25

Algoritmo de Bellman-Ford
B

D(B,d)←mín{c(B,C)+D(C,d)}
No hay cambios

C envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
B
B
E

Cost
1
2
4
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
B
B
B
B

Cost
2
1
4
3

Dest
A
B
C
E

D

Next
B
B
B
E

Cost
4
3
4
1

Dest
A
B
C
D

E

Next
A
A
B
D

Cost
1
1
3
2

Cost
1
2
5
1

Enrutamiento distance vector

17/25

Algoritmo de Bellman-Ford
B

D(A,d)←mín{c(A,E)+D(E,d)}
D(B,d)←mín{c(B,E)+D(E,d)}
D(D,d)←mín{c(D,E)+D(E,d)}
(…)

E envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
B
B
E

Cost
1
2
4
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
B
B
B
B

Cost
2
1
4
3

Dest
A
B
C
E

D

Next
B
B
B
E

Cost
4
3
4
1

Dest
A
B
C
D

E

Next
A
A
B
D

Cost
1
1
3
2

Cost
1
2
5
1

Enrutamiento distance vector

18/25

Algoritmo de Bellman-Ford
B

D(A,d)←mín{c(A,E)+D(E,d)}
D(B,d)←mín{c(B,E)+D(E,d)}
D(D,d)←mín{c(D,E)+D(E,d)}

E envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
B
E (B)
E

Cost
1
2
2 (4)
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
B
B
B
B

Cost
2
1
4
3

Dest
A
B
C
E

D

Next
E (B)
B
B
E

Cost
2 (4)
3
4
1

Dest
A
B
C
D

E

Next
A
A
B
D

Cost
1
1
3
2

Cost
1
2
5
1

Enrutamiento distance vector

19/25

Algoritmo de Bellman-Ford
B

D(E,d)←mín{c(E,A)+D(A,d)}
D(B,d)←mín{c(B,A)+D(A,d)}
(…)

A envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
B
E
E

Cost
1
2
2
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
B
B
B
B

Cost
2
1
4
3

Dest
A
B
C
E

D

Next
E
B
B
E

Cost
2
3
4
1

Dest
A
B
C
D

E

Next
A
A
B
D

Cost
1
1
3
2

Cost
1
2
5
1

Enrutamiento distance vector

20/25

Algoritmo de Bellman-Ford
B

D(E,d)←mín{c(E,A)+D(A,d)}
D(B,d)←mín{c(B,A)+D(A,d)}

A envía

Dest
A
C
D
E

Next
A
C
D
A

Dest
B
C
D
E

A

Next
B
B
E
E

Cost
1
2
2
1

C
1
B
4
E

A

1

1

3

D

1

Dest
A
B
D
E

C

Next
B
B
B
B

Cost
2
1
4
3

Dest
A
B
C
E

D

Next
E
B
B
E

Cost
2
3
4
1

Dest
A
B
C
D

E

Next
A
A
A (B)
D

Cost
1
1
3
2

Cost
1
2
3 (5)
1

Enrutamiento distance vector

21/25

Algoritmo de Bellman-Ford
B

A

Dest
B
C
D
E

Next
B
B
E
E

Cost
1
2
2
1

Dest
A
C
D
E

Next
A
C
D
A

D envía
B envía
C envía
E envía
A envía

No hay cambios
No hay cambios
No hay cambios
No hay cambios
No hay cambios
C
1
B
4
E

D

3

1

A

1

1

Cost
1
1
3
2

Cost
1
2
3
1

Dest
A
B
D
E

C

Next
B
B
B
B

Cost
2
1
4
3

Dest
A
B
C
E

D

Next
E
B
B
E

Cost
2
3
4
1

Dest
A
B
C
D

E

Next
A
A
A
D

Enrutamiento distance vector

22/25

Distance Vector
 Cálculo distribuido
 Iterativo e incremental
 Asíncrono
 Converge a los caminos de menor coste
IPX-RIP, DECnet,
 Protocolos: RIP,

IGRP, EIGRP, DSDV

Enrutamiento distance vector

23/25

Temario

1.- Introducción
2.- Nivel de enlace en LANs
3.- Interconexión de redes IP
4.- Enrutamiento con IP







Carácterísticas del enrutamiento dinámico en Internet
Tipos de algoritmos. Enrutamiento Distance-Vector
RIP
Problemas de RIP


5.- Nivel de transporte en Internet
6.- Nivel de aplicación en Internet
7.- Ampliación de temas

Enrutamiento distance vector

24/25

Próxima clase

RIP

 Lecturas recomendadas:

 [Forouzan03] 13.2
 12 páginas

Enrutamiento distance vector

25/25