PDF de programación - Enrutamiento Link-state

Imágen de pdf Enrutamiento Link-state

Enrutamiento Link-stategráfica de visualizaciones

Publicado el 2 de Junio del 2017
205 visualizaciones desde el 2 de Junio del 2017
333,3 KB
34 paginas
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

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...





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



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...





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?

,



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...

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

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



a
c
i
t

l



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

i

I



e
d
a
e
r
Á

I

• 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

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
Á

• 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
  • Links de descarga
http://lwp-l.com/pdf3928

Comentarios de: Enrutamiento Link-state (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad