PDF de programación - Enrutamiento (2)

Imágen de pdf Enrutamiento (2)

Enrutamiento (2)gráfica de visualizaciones

Publicado el 5 de Junio del 2017
392 visualizaciones desde el 5 de Junio del 2017
897,2 KB
37 paginas
Creado hace 12a (12/05/2009)
ARQUITECTURA DE REDES, SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Enrutamiento (2)

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

3º Ingeniería de Telecomunicación

Basadas en el material docente de Lawrie Brown sobre el libro de
William Stallings (Data and Computer Communications)

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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



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

1/36

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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



Temario

Introducción

1.
2. Arquitecturas, protocolos y estándares
3. 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)

4. Conmutación de circuitos
5. Tecnologías
6. Control de acceso al medio en redes de área local
7. Servicios de Internet

2/36

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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



En clases anteriores…

• Conmutación de circuitos y de paquetes
• El problema del enrutamiento
• Técnicas de enrutamiento básicas

– Enrutamiento estático
– Inundación
– Enrutamiento aleatorio
– Enrutamiento de mínimo coste

• Algoritmo de Dijkstra (de mínimo coste)

3/36

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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

Hoy
• Algoritmo de Bellman-Ford

(el otro algoritmo clásico de mínimo coste)

• Historia del enrutamiento en ARPANET
• De los algoritmos de grafos al enrutamiento
• Enrutamiento en Internet

4/36

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



c
i
t

l



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

i

I



e
d
a
e
r

Á

a Algoritmo de Bellman-Ford

,

• Encontrar los caminos mas cortos desde un nodo origen

dado, sujetos a la restricción de que como mucho tengan un
enlace (1 salto)

• Encontrar los caminos mas cortos desde un nodo origen

dado, sujetos a la restriccion de que como mucho tengan dos
enlace (2 saltos)

• Encontrar los caminos mas cortos desde un nodo origen

dado, sujetos a la restriccion de que como mucho tengan h
enlaces (h saltos)
Es facil si se conocen los caminos para el caso h-1

• …

5/36

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



c
i
t

l



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

i

I



e
d
a
e
r

Á

a Algoritmo de Bellman-Ford

,

• Variables del algoritmo
• Conjunto de nodos E={ni nodos en el grafo}
• Pesos de los enlaces

w(ni ,nj ) peso del enlace de ni a nj
en general distinto de w(nj ,ni )
w(ni ,nj ) = infinito si no hay enlace

s nodo origen del que pretendemos calcular los caminos
• h número de iteración del algoritmo = máximo número de

enlaces que se consideran

• Lh(ni) distancia mínima de s a ni considerando solo caminos que

tengan como mucho h enlaces

6/36

a Algoritmo de Bellman-Ford
• Paso 1 [Inicialización]

c
i
t

l

,

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



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

i

I



e
d
a
e
r

Á

– L0(n) = ∞, para todo n ≠ s
– Lh(s) = 0, para todo h

• Paso 2 [Actualización]

– Para cada h ≥ 0 sucesivo

• Para cada n s, : Lh+1(n)=min

j[Lh(j)+w(j,n)]

– Conectar n con el predecesor j que de menor camino
– Eliminar la conexión de n con predecesores de una iteracion

– El camino nuevo es el camino para llegar al nodo elegido j al

que se ha añadido el enlace de j a n

– Si en una iteración no hacemos ningún cambio el algoritmo ha

anterior

terminado

7/36

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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



Ejemplo

8/36

Ejemplo

h

Lh(2)

Path

Lh(3)

Path

Lh(4)

Path

Lh(5)

Path

Lh(6)

Path

∞0

21

22

23

24

-

1-2

1-2

1-2

1-2



5

4

3

3

-

1-3

1-4-3

1-4-5-3

1-4-5-3



1

1

1

1

-

1-4

1-4

1-4

1-4





2

2

2

-

-





-

-

1-4-5

10

1-3-6

1-4-5

1-4-5

4

4

1-4-5-6

1-4-5-6

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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



Resumen Bellman-Ford

• Funciona, si hay camino más corto lo calcula (Si el grafo es

conexo)

• Calcula los mismos caminos que Dijkstra (También da un

spanning tree centrado en el nodo que queremos)

• También necesita la topología completa, pero…
• Cual es más rápido?

Se acepta que desde un punto de vista algorítmico Dijkstra es
más rápido, acaba en menos operaciones (no necesariamente
en menos iteraciones)

• Pero hay otros factores…

10/36

Prestaciones para uso en enrutamiento
• Depende de:

– Tiempo de proceso de los algoritmos
– Cantidad de información requerida de otros nodos
• Es especifico de la implementación del algoritmo

,

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

Á

Esta demostrado
• Los dos convergen bajo condiciones de topología estática (no

cambian los enlaces ni sus pesos)

• Los dos convergen a la misma solución
• Si los enlaces cambian los algoritmos tratan de recalcular los

caminos (Spanning-Tree)
– Dijkstra tiene que empezar de nuevo las iteraciones

• Si los costes dependen del tráfico en los enlaces (enrutamiento

sensible a la congestion), el tráfico depende a su vez de los
caminos elegidos lo que lleva a inestabilidades

11/36

Comparación

• Los dos algoritmos dan el mismo resultado
• Quizas Dijkstra incluso lo calcula antes pero…
• Bellman-Ford

,

a
c
i
t

l



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

i

I



e
d
a
e
r

Á

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



– El calculo para el nodo n necesita el coste de los enlaces desde los

vecinos de n mas el coste total del camino desde s a los vecinos de n
– Cada nodo puede mantener el coste y el camino a cada otro nodo (en

realidad vale con el siguiente salto)

– Es suficiente con intercambiar información entre nodos vecinos
– Se puede actualizar la el coste y el camino en cada nodo basado en la

información de los vecinos y los costes de los enlaces a los vecinos

• Dijkstra

– Cada nodo necesita toda la topología
– Necesita conocer los costes de todos los enlaces en la red
– Debe intercambiar información con el resto de nodos

12/36

,

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

Á

Topología variable

¿qué pasa si cambia un enlace?
• Dijkstra: reinicio el algoritmo y al
añadir ese nodo a T se tendrá en
cuenta el nuevo enlace

• Bellman-Ford: Aunque hemos

detenido el algoritmo al dejar de
producirse cambios. Las iteraciones
de Bellman-Ford se pueden
mantener periódicamente.

• Si no hay cambios reelegirán los

mismos caminos, si hay cambios se
adaptara a los cambios

S

3

2

2

5

1

5

3

5

3

8

13/36

,



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

Á

Topología variable

• Aplicando la iteración de

Bellman-Ford se cambia el
camino de este nodo

• La distancia más corta es

ahora la de su vecino S + el
nuevo peso

• El camino se mantiene

S

3

2

2

5

1

1

3

5

3

8

14/36

,



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

Á

Topología variable

• Aplicando la iteración de

Bellman-Ford una segunda
vez se evalúa el camino para
este nodo

• Ahora el camino por el nodo

de la izquierda tiene distancia
5 pero el de la derecha sería
4

• El camino se cambia al nodo

de la derecha

• Las siguiente iteración no

cambia de nuevo

S

3

2

2

5

1

1

3

5

4

3

8

15/36

Ventajas de Bellman-Ford

• Las iteraciónes de Bellman-Ford se pueden ir

aplicando continuamente.

,



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

Á

• Se obtiene un algoritmo que se adapta a la

topología cambiante

• Se puede mantener la información de los
caminos a todos los nodos en cada nodo.

• Se pueden ir aplicando correcciones a esos
caminos con información procedente sólo de
los vecinos.

• Algoritmo de Bellman-Ford distribuido
• Algoritmo distribuido y que utiliza información

de nodos vecinos

16/36

,

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

Á

Encaminamiento en ARPANET

• 1969
• Enrutamiento distribuido adaptativo

– Usando la ocupación de la cola como estimación del retardo

• Basado en el algoritmo de Bellman-Ford
• Cada nodo intercambia su vector de retardos con los

vecinos (varias veces por segundo cada 128ms)

• Se recalcula la tabla de rutas basada en la

información nueva (usando la ecuación de Bellman-
Ford)

• Problemas:

cola

– No considera la velocidad del enlace solo el tamaño de la

– El tamaño de cola no es buena estimación del retardo
– Responde despacio a la congestión (Para cuando envio un

paquete el tamaño de cola ha cambiado mucho)

17/36

,



I

I



S
E
D
E
R
E
D
A
R
U
T
C
  • Links de descarga
http://lwp-l.com/pdf4235

Comentarios de: Enrutamiento (2) (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