PDF de programación - Enrutamiento Link-state

ARQUITECTURA DE REDES, SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Enrutamiento

Link-state...

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

Grado en Ingeniería en Tecnologías de Telecomunicación, 2º

,

Temario

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Introducción
Arquitecturas de conmutación y protocolos
Introducción a las tecnologías de red

1.
2.
3.
4. Control de acceso al medio
5. Conmutación de circuitos
6.
7.

Transporte fiable
Encaminamiento

2

,

Temario

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

Introducción
Arquitecturas de conmutación y protocolos
Introducción a las tecnologías de red

1.
2.
3.
4. Control de acceso al medio
5. Conmutación de circuitos
6.
7.

Transporte fiable
Encaminamiento

3

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á



Algoritmo:
Inicializar


•

Algoritmos para encontrar caminos

Algoritmo de Dijkstra para la distancia mínima
Conocemos: Nodos i Nodo raiz r pesos w(i,j)

•
•
• Mantenemos: d(i) mejor distancia de r al nodo i conocida hasta ahora

T conjunto de nodos a los que ya conocemos la distancia mas corta
d(i) es la distancia menor de r hasta el nodo i pasando solo
por nodos que están en T

d(i)=infinito d(r)=0 si el nodo i es vecino de r [ w(i,r)<infinito ] d(i)=w(i,r)
T={r}


Mientras haya nodos que no pertenezcan a T



elegir el nodo i que no este en T con menor d(i)
añadir el nodo i a T
actualizar d(k) de los nodos vecinos al nodo i que no están en T.



Si d(i)+w(k,i) < d(k) entonces d(k)=d(i)+w(k,i)
[es menor la distancia pasando por i que la que ya tenia]

Dijkstra ejemplo

d(C)

d(D)

,



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

T

{D}

{D,C}

{D,C,F}

{D,C,F,B}

{D,C,F,B,E}

1

B

d(B)

infinito

2

2

2

2

C

3

1

F

1

1

1

1

1

2

D

1

B

E

1

1

E

4

C

3

1

4

D

2

F

0

0

0

0

0

d(E)

infinito

4

4

3

3

1

B

1

B

1

1

C

3

F

4

C

3

E

1

E

1

4

d(F)

2

2

2

2

2

D

2

D

2

F

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á



Algoritmo:
Inicializar


Manteniendo el camino

Usando el algoritmo de Dijkstra para el camino mínimo
Conocemos: Nodos i Nodo raiz r pesos w(i,j)

•
•
• Mantenemos: d(i) mejor distancia de r al nodo i conocida hasta ahora

s(i) siguiente nodo a i en el camino hacia r
T conjunto de nodos a los que ya conocemos la distancia mas corta

d(i)=infinito d(r)=0 si el nodo i es vecino de r [ w(i,r)<infinito ] d(i)=w(i,r)
T={r}
s(i)=desconocido si i es vecino de r [ w(i,r)<infinito ] s(i)=r



Mientras haya nodos que no pertenezcan a T



elegir el nodo i que no este en T con menor d(i)
añadir el nodo i a T
actualizar d(k) de los nodos vecinos al nodo i que no están en T.



Si d(i)+w(k,i) < d(k) entonces d(k)=d(i)+w(k,i)

[si el camino por i es mejor i es el nuevo siguiente salto de k]

y tambien s(k)=i



Dijkstra ejemplo con camino

d(B) / s(B)

d(C) / s(C)

d(D) / s(D)

d(E) / s(E)

d(F) / s(F)

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

T

{D}

{D,C}

{D,C,F}

{D,C,F,B}

{D,C,F,B,E}

1

B

infinito / desc

2 / C

2 / C

2 / C

2 / C

1

C

3

F

1 / D

1 / D

1 / D

1 / D

1 / D

D

2

0 / soy yo

0 / soy yo

0 / soy yo

0 / soy yo

0 / soy yo

infinito / desc

4 / C

4 / C

3 / B

3 / B

1

B

1

B

1

1

C

3

F

4

C

3

E

1

E

1

4

2 / D

2 / D

2 / D

2 / D

2 / D

D

2

D

2

F

1

B

E

1

1

E

4

C

3

1

4

D

2

F

Algoritmos de caminos mínimos

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• Dijkstra vs Bellman-Ford

– Los dos calculan el árbol de expansión mínimo para una raiz dada
– Los dos algoritmos dan el mismo resultado
– El resultado no tiene por que ser único (probad a hacer los

ejemplos anteriores cambiando el peso de C-E a 2)

• Cuál es más rápido?

– Parece que Bellman-Ford hace menos iteraciones pero las

iteraciónes de Dijkstra parecen más cortas y rápidas

• Cuál preferiríais programar?
• Normalmente se suele considerar mejor el algoritmo de Dijkstra para

resolver el problema de los caminos en un grafo

• Bellman-Ford permite construir algoritmos distribuidos basados en el

concepto distance-vector

Funciona Distance-Vector?

,



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

I

La información para cada destino se propaga desde los routers que la
saben...

•

•

Se llegar a la
red X
distancia 0

red

A

1

4

B

2

Se llegar a la
red X
distancia 4

Se llegar a la
red X
distancia 1

C

1

1

E

1

4

D

1

2

F

2

G
1

1

I

6

6

1

J

H

Funciona Distance-Vector?

,



I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

I

La información para cada destino se propaga desde los routers que la
saben...

•

•

red

A

1

4

B

2

Se llegar a la
red X
distancia 4

Se llegar a la
red X
distancia 2

Se llegar a la
red X
distancia 1

C

1

1

E

1

4

D

1

2

F

2

G
1

1

I

6

6

1

J

H

Funciona Distance-Vector?

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á



•

La información para cada destino se propaga desde los routers que la
saben...

• El tiempo de propagación depende de cuantos routers hay hasta el destino
• El tiempo de propagación no es tanto si cada router envía la información a

sus vecinos cada vez que hay cambios (triggered updates)

red

A

1

4

B

2

Se llegar a la
red X
distancia 4

Se llegar a la
red X
distancia 2

Se llegar a la
red X
distancia 1

C

1

1

E

1

4

D

1

2

F

2

G
1

1

I

6

6

1

J

H

Funciona Distance-Vector?

,

•

La información para cada destino se propaga desde los routers que la
saben...

• No necesariamente la mejor ruta es la que oigo la primera vez por eso el



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

algoritmo debe funcionar de forma continua
Lo mismo pasa a la vez con todos los demas destinos

•

red

A

1

Se llegar a la
red X
distancia 3

Se llegar a la
red X
distancia 2

4

B

2

C

1

1

E

1

4

D

1

2

F

2

G
1

1

I

6

6

1

J

H

Funciona Distance-Vector?

,



I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• El algoritmo no sabe cuando ha terminado
• Pero no importa mucho que se ejecute de forma continua
• Si usamos envío de información periódica controlamos el trafico de

enrutamiento que se envía... pero el tiempo en propagar rutas es mas largo
• Si enviamos en cuanto hay cambios (triggered updates) la propagación es
rapida y se envía más tráfico cuando hay un cambio pero es self-stoping se
autocontrola y deja de enviar cuando las rutas se estabilizan

• Normalmente se utiliza triggered updates con y envio periodico no

demasiado frecuente
– Envío rapido de cambios
– El envio periodico ayuda si se pierden mensajes o para descubrir

vecinos cuando un router se conecta a la red

• Parece razonable. Funciona, se propaga rapido y no crea mucho trafico...
• Y entonces por que es el sistama de enrutamiento antiguo de Internet

,

Problemas

I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• Es lento en reaccionar !!!
• No todos los cambios se propagan rápido hay situaciones anómalas
• Un caso muy simple y bien conocido
• Qué pasa si se cae el primer enlace?

Se llegar a la
red X
distancia 0

Se llegar a la
red X
distancia 1

Se llegar a la
red X
distancia 2

Se llegar a la
red X
distancia 3

red

A

1

B

1

D

1

un enlace

C

red

Se llegar a la
red X
distancia 2

Se llegar a la
red X
distancia 3

ouch

A

B

C

1

D

1

,

La cuenta a infinito



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

I

• Cuando un enlace se cae...

C sabe llegar a
la red X

Se llegar a la
red X
distancia 2

red

A

B

Se
llegar a la red
X

C

1

D

1

Se llegar a la
red X
distancia 3

Se llegar a la
red X
distancia 4

B

1

C

Se
llegar a la red
X

D

1

Se
llegar a la red
X

,

La cuenta a infinito

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• Como acaba esto?
•

Se hace que el campo para indicar la distancia tendrá bits limitados
Cuando llegue al máximo se considera infinito y la ruta se descarta
Establcer un valor de infinito pequeño hace que estos casos se detecten antes
Pero entonces solo podremos calcular distancias menores a ese valor
Por ejemplo en RIP se usa infinito=16 :-)

Se llegar a la
red X
distancia 16

red

A

B

1

C

1

D

No se puede
llegar a la red
X !!

No se puede
llegar a la red
X

No se puede
llegar a la