PDF de programación - Enrutamiento Link-state...

REDES
Á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

3º Ingeniería de Telecomunicación

,

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
Á

Temario

Introducción

•
• Arquitecturas, protocolos y estándares
• Conmutación de paquetes
• Conmutación de circuitos
• Tecnologías
• Control de acceso al medio en redes de área local
• Servicios de Internet

2/34

,

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
Á

Temario

Introducción

•
• Arquitecturas, protocolos y estándares
• Conmutación de paquetes

– Principios
– Problemas básicos

• Como funcionan los routers (Nivel de red)
• Encaminamiento (Nivel de red)
• Transporte fiable (Nivel de transporte en TCP/IP)
• Control de flujo (Nivel de transporte en TCP/IP)
• Control de congestión (Nivel de transoporte en TCP/IP)

• Conmutación de circuitos
• Tecnologías
• Control de acceso al medio en redes de área local
• Servicios de Internet

a
c
i
t

l



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

i

I


S
E
D
E
R

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)

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

T

{D}

{D,C}

{D,C,F}

{D,C,F,B}

{D,C,F,B,E}

1

B

1

B

1

d(B)

infinito

2

2

2

2

C

3

1

F

1

1

1

1

1

D

2

E

1

4

C

1

3

F

E

4

D

2

0

0

0

0

0

1

B

1

E

1

B

1

d(E)

infinito

4

4

3

3

1

C

3

4

C

3

d(F)

2

2

2

2

2

D

2

F

1

D

2

F

E

4

a
c
i
t

l



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

i

I


e
d



S
E
D
E
R

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)

infinito / desc

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

T

{D}

{D,C}

{D,C,F}

{D,C,F,B}

{D,C,F,B,E}

infinito / desc

2 / C

2 / C

2 / C

2 / C

1

B

1

B

1

1

C

3

F

E

1

4

C

1

3

F

E

4

1 / D

1 / D

1 / D

1 / D

1 / D

D

2

D

2

0 / soy yo

0 / soy yo

0 / soy yo

0 / soy yo

0 / soy yo

1

B

1

E

1

B

1

4 / C

4 / C

3 / B

3 / B

1

C

3

4

C

3

E

4

2 / D

2 / D

2 / D

2 / D

2 / D

D

2

F

1

D

2

F

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

Algoritmos de caminos mínimos

• 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

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

Funciona Distance-Vector?

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

•

•

Se llegar a
la red X
distancia 0

red X

A

Se llegar a
la red X
distancia 1

4

1

1

B

2

1

C

1

E

4

Se llegar a
la red X
distancia 4

D

1

1

I

2

F

2

G

1

6

6

1

J

H

Funciona Distance-Vector?

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

•

•

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

red X

A

Se llegar a
la red X
distancia 1

4

Se llegar a
la red X
distancia 4

Se llegar a
la red X
distancia 2

1

1

B

2

1

C

1

E

4

D

1

1

I

2

F

2

G

1

6

6

1

J

H

Funciona Distance-Vector?

•

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)

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

red X

A

Se llegar a
la red X
distancia 1

4

Se llegar a
la red X
distancia 4

Se llegar a
la red X
distancia 2

1

1

B

2

1

C

1

E

4

D

1

1

I

2

F

2

G

1

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

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

•

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

red X

A

1

Se llegar a
la red X
distancia 3

Se llegar a
la red X
distancia 2

4

B

2

1

1

C

1

E

4

D

1

1

I

2

F

2

G

1

6

6

1

J

H

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

Funciona Distance-Vector?

• 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

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

Problemas

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

A

B

C

D

1

1

1

un enlace
menos

red X

Se llegar a
la red X
distancia 2

Se llegar a
la red X
distancia 3

ouch

A

B

C

D

1

1

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

La cuenta a infinito

• Cuando un enlace se cae...

C sabe llegar
a la red X

Se llegar a
la red X
distancia 2

red X

A

B

C

D

1

1

Se llegar a
la red X
distancia 3

Se llegar a
la red X
distancia 3

Se llegar a
la red X
distancia 4

B

C

D

1

1

Se llegar a
la red X
distancia 5

Se llegar a
la red X
distancia 6

La cuenta a infinito

a
c
i
t

l



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

i

I


S
E
D
E
R

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 X

A

B

C

D

1

1

No se puede
llegar a la
red X !!

No se puede
llegar a la
red X

No se puede
llegar a la
red X

•

Se adapta tambien al cambio en este caso pero tarda un poco
y genera unos cuantos mensajes de actualización en el proceso

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

Problemas distance-vector

•

Las cuentas a infinito hacen que los protocolos distance-vector puedan tardar
en bastante en converger a la solución

• Mientras convergen las rutas puede no ser buenas

(ciclos de enrutamiento y perdidas)

•

Se puede resolver el problema de las cuentas a infinito?
Hay algunas optimizaciónes que parecen obvias...
– Mejor no anunciar una ruta a un nodo si la ruta pasa por el (split-horizon)
– Cuando una ruta se vuelve es descartada no aceptar nuev