PDF de programación - Enrutamiento Distance-Vector: RIP

LABORATORIO DE PROGRAMACIÓN DE REDES
Área de Ingeniería Telemática

Enrutamiento Distance-Vector: RIP

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Laboratorio de Programación de Redes

3º Ingeniería Técnica en Informática de Gestión





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Objetivos

• Descripción detallada de un protocolo DV
• Ver

los principales problemas de estos

protocolos con ejemplos claros
• Analizar las posibles soluciones

RIP

1/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Contenido

RIP
• Características
• Formato
• Funcionamiento
• Cuenta a infinito

– Situaciones y soluciones

• RIPv2

RIP

2/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Contenido

RIP
• Características
• Formato
• Funcionamiento
• Cuenta a infinito

– Situaciones y soluciones

• RIPv2

RIP

3/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Distance Vector

• Cada nodo tiene unas distancias estimadas a cada destino

(vector de distancias)

• Se las envía a todos sus vecinos periódicamente
• Algoritmo de Bellman-Ford distribuido
• No necesitan conocer la topología completa de la red
• Usado en la ARPANET hasta 1979
• Ejemplos: RIP, Xerox XNS RIP, IPX RIP, Cisco IGRP, DEC’s

DNA Phase IV, Apple’s RTMP

RIP

4/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Características

IGP

• Routing Information Protocol
• Distance Vector
•
• RFCs 1058 (v1), 2453 (v2)
•
• Emplea UDP
• Métrica:

routed en Unix BSD

– Número de saltos
– 16 = ∞

• Se envía el vector de distancias

cada 30 segs

• Cambios en la topología:

– Ruta a red N por router G
– Si no recibimos vector de G en
180segs marcar como inválida (∞)

• No escala para redes

grandes

• Para redes con enlaces

homogéneos

• Simple
• Malos

convergencia

tiempos

de

RIP

RIP

RIP

AS 2

RIP

RIP

RIP

5/24

Tipos de PDUs:
• Request

– Comando=1
– Se puede pedir el coste a unos

destinos o a todos

RIP
Formato

• Response

– Comando=2
– El next-hop es la IP que envía

la PDU

– Periódico o en respuesta a un

request



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

7 8

0
Comando Versión

15 16

Address family
IP=2, todo=0

IP Address

0
0

0
0

Métrica (1-16)

31

Permitiría otros
protocolos de
red

RIP

RIP

RIP

RIP

AS 2

RIP

RIP

6/24

20 bytes

se

repite
hasta 25

veces

RIP

Funcionamiento



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Inicialización
• Manda un request especial por

cada interfaz
IP destino broadcast

•
Recibe un request
• Si es de inicialización manda

• Si no responde con los valores

todo el vector

solicitados

Periódicamente
• Timer 30seg (de 25 a 35)
• Manda un response con todo el

vector por cada interfaz
IP destino broadcast

•

Recibe response
• Actualiza su vector y tabla de

rutas

• Si la tiene reinicializa timer
Caduca timer de una ruta
• Timer de 180s para cada una
• Pasa a coste ∞
•
Timer de borrado
• Timer de 120s para una ruta

Inicia timer para borrarla

invalidada

RIP

7/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Actualización

1. Añadir 1 a la métrica de cada destino anunciado en

el paquete de RIP recibido

2. Para cada entrada en el paquete

•

•

Si el destino no está en la tabla de rutas
1. Añadirlo
Si no (sí está en la tabla)
1. Si el siguiente salto en la tabla es el mismo que quien ha

mandado el paquete de IP


Sustituir el coste por el nuevo

2. Si no (diferente next-hop)



Si la coste es menor que el de la tabla
o Sustituir el coste y el next-hop

RIP

8/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Bad news travel slowly

•
•

•

•
•

•
•
•

Supongamos que R1 falla (…)
Aprox. 3min después R2 marca la
ruta como inválida (…)
Si antes de que envíe el vector a R3
se lo enviá él (…)
¡ Ahora piensa que se va por R3 !
Pero cuando
nuevo
camino éste
aumento en el coste (…)
Y así ad infinitum (…)
Proceso de cuenta a infinito
Infinito = 16 !

informa a R3 del
verá un

R1

R2

R3

A

B

C

D

Dst: Red A, cost: 2

Dst: Red A, cost: 3

Dst: Red A, cost: ∞
Dst: Red A, cost: 4

Dst: Red A, cost: 4

Dst: Red A, cost: 6

RIP

Dst: Red A, cost: 3

Dst: Red A, cost: 3

Dst: Red A, cost: 5

Dst: Red A, cost: 5

9/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Contenido

RIP
• Carácterísticas
• Formato
• Funcionamiento
• Cuenta a infinito

– Situaciones y soluciones

• RIPv2

RIP

10/24

RIP

Evitar las cuentas a infinito

Split horizon
•

Al enviar vector por un interfaz no
incluir los destinos a los que se llega
por él

• Mensajes más pequeños



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Ejemplo (… …):

– Caduca timer (180s) en R2 (…)
– Caduca timer (180s) en R3 (…)

(B,1)
(C,2)
(D,3)

A

(A,1)

(C,1)
(D,2)

(D,1)

(A,2)
(B,1)

(A,3)
(B,2)
(C,3)

R3

R2

R1

B

C

D

Dst: Red A, cost: 2

Dst: Red A, cost: 3

Dst: Red A, cost: ∞

Dst: Red A, cost: 3

Dst: Red A, cost: ∞

Dst: Red A, cost: ∞

RIP

11/24

RIP

Evitar las cuentas a infinito

Split horizon with poisoned reverse
•

Al enviar vector por un interfaz anunciar
los destinos a los que se llega por él con
métrica ∞

• No hay que esperar al timeout de la ruta
• Mensajes vuelven a ser grandes



S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

Ejemplo (… …):

– Caduca timer (180s) en R2 (…)
– Caduca timer (30s) en R2,

envía vector (…)

(A,∞)
(B,1)
(C,2)
(D,3)

A

R1

(A,∞)
(B,∞)
(C,1)
(D,2)

(A,1)
(B,∞)
(C,∞)
(D,∞)
B

R2

(A,2)
(B,1)
(C,∞)
(D,∞)

(A,∞)
(B,∞)
(C,∞)
(D,∞)
C

R3

(A,3)
(B,2)
(C,1)
(D,∞)

D

Dst: Red A, cost: 2

Dst: Red A, cost: 3

Dst: Red A, cost: ∞

Dst: Red A, cost: 3

Dst: Red A, cost: ∞

Dst: Red A, cost: ∞

RIP

12/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Bad news travel slowly

• Convergencia lenta
• Ejemplos:

– Actualización de información

• Caso peor N x 30seg para llegar al otro extremo

– Pérdida de ruta

•

Caso peor N x 180seg hasta el otro extremo

• ¿ Mejorar estos tiempos ?

– Triggered updates: Enviar el vector en cuanto se produzca un

cambio en el mismo

R1

R2

R3

RN

…

RIP

13/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Cuenta a infinito

•

Supongamos
figura

la

topología de

la

• R4 introduce una entrada hacia la

Red A por R3 (…)

• Usan split horizon with poisoned

•

•

reverse
Las flechas son las rutas hacia la
Red A (…)
Supongamos que falla el interfaz de
R1 en la Red A (…)

• R1 anuncia coste ∞ a R2 y R4 (…)
•

Puede que antes de que avisen a
R3 él envíe su actualización
periódica (…)

• R4 anunciará esa ruta a R1 (…)
• R1 creerá que se llega por R4 con

coste 5 (…)

• R1 lo anunciará a R2 (…)
• R2 creerá que se llega por R1 (…)
Y luego R2 hasta llegar a R3 (…)
•

(A,∞)
…

B

R1

R2

∞

E

R4

∞

(A,∞)
…

A

RIP

C

D

(A,∞)
…

R3

(A,3)
…

14/24





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I



E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Cuenta a infinito

•

Supongamos
figura

la

topología de

la

• R4 introduce una entrada hacia la

Red A por R3 (…)

• Usan split horizon with poisoned

•

•

reverse
Las flechas son las rutas hacia la
Red A (…)
Supongamos que falla el interfaz de
R1 en la Red A (…)

• R1 anuncia coste ∞ a R2 y R4 (…)
•

Puede que antes de que avisen a
R3 él envíe su actualización
periódica (…)

• R4 anunciará esa ruta a R1 (…)
• R1 creerá que se llega por R4 con

coste 5 (…)

• R1 lo anunciará a R2 (…)
• R2 creerá que se llega por R1 (…)
Y luego R2 hasta llegar a R3 (…)
•

R1

B

E

R2

∞

R4

4

C

D

(A,∞)
…

R3

(A,3)
…

15/24

A

RIP





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Cuenta a infinito

•

Supongamos
figura

la

topología de

la

• R4 introduce una entrada hacia la

Red A por R3 (…)

• Usan split horizon with poisoned

•

•

reverse
Las flechas son las rutas hacia la
Red A (…)
Supongamos que falla el interfaz de
R1 en la Red A (…)

• R1 anuncia coste ∞ a R2 y R4 (…)
•

Puede que antes de que avisen a
R3 él envíe su actualización
periódica (…)

• R4 anunciará esa ruta a R1 (…)
• R1 creerá que se llega por R4 con

coste 5 (…)

• R1 lo anunciará a R2 (…)
• R2 creerá que se llega por R1 (…)
Y luego R2 hasta llegar a R3 (…)
•

R1

B

E

5

R2

∞

C

R3

R4

D
(A,∞)
…

4

(A,4)
…

16/24

A

RIP





S
E
D
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

I



I

E
D
O
R
O
T
A
R
O
B
A
L

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I



e
d
a
e
r

Á

RIP

Cuenta