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





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



Objetivos

•  Descripción detallada de un protocolo DV
•  Ver

los principales problemas de estos

protocolos con ejemplos claros
•  Analizar las posibles soluciones





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



Contenido

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

– Situaciones y soluciones

•  RIPv2





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



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





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I


I



I

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



i



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 = !

cada 30 segs

•  Se envía el vector de distancias
•  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

con

enlaces

redes
homogéneos

•  Simple
•  Malos tiempos de convergencia

RIP

RIP

RIP

AS 2

RIP

RIP

Tipos de PDUs:
•  Request



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



RIP
Formato

•  Response

la PDU

request

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

destinos o a todos

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

–  Periódico o en respuesta a un

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

20 bytes

se

repite
hasta 25

veces





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



RIP

Funcionamiento

cada interfaz
IP destino broadcast

Inicialización
•  Manda un request especial por
• 
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





l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I



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

I

i

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

RIP

Actualización

• 

• 

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 el coste es menor que el de la tabla

o  Sustituir el coste y el next-hop

RIP

Bad news travel slowly



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i

•  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 envía él (…)
¡ Ahora piensa que se va por R3 !

• 
•  Pero cuando

informa a R3 del
nuevo camino éste verá un aumento
en el coste (…)

•  Y así ad infinitum (…)
•  Proceso de cuenta a infinito
• 

Infinito = 16 !

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: 3

Dst: Red A, cost: 3

Dst: Red A, cost: 5

Dst: Red A, cost: 6

Dst: Red A, cost: 5

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
•  Evita el bucle anterior

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



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



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

R3

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

(A,!)
(B,!)
(C,!)
(D,!)
C

(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

Bad news travel slowly

•  Convergencia lenta
•  Ejemplos:

–  Actualización de información

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



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



–  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

Cuenta a infinito



l

•  Supongamos

la

topología de

la

•  R4 introduce una entrada hacia la



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



figura

•  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 (…)

Red A por R3 (…)

•  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

!

A

(A,!)
…

E

R4
!

(A,!)
…

R3

(A,3)
…

C

D

RIP

Cuenta a infinito



l

•  Supongamos

la

topología de

la

•  R4 introduce una entrada hacia la



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



figura

•  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 (…)

Red A por R3 (…)

•  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 (…)

R2

!

R1

B

E

R4

(A,!)
…

R3

(A,3)
…

C

D

4

A

RIP

Cuenta a infinito

•  Supongamos

la

topología de

la

•  R4 introduce una entrada hacia la



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I

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

I

i



figura

•  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 (…)

Red A por R3 (…)

•  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 (…)

B
5

R1

A

R2

!

C

R3

E
(A,4)
…

R4

D
(A,!)
…

4

RIP

Cuenta a infinito

•  Supongamos

la

topología de

la

•  R4 introduce una entrada hacia la



l



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


S
a
E
c
D
i
t
E
R
E
D
N
Ó
C
A
M
A
R
G
O
R
P

a
e
r
Á

e
d

I



I



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

I

i



figura

•  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 (…)

Red A por R3 (…)

•  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 has