PDF de programación - Enrutamiento (2)

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



,



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

I

I

I



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

I



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

1/36

Temario


a
c
i
t



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

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



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

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



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

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


,


a
c
i
t



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

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


a
c
i
t



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

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

Algoritmo de Bellman-Ford


a
c
i
t



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

•  Paso 1 [Inicialización]

–  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)]

anterior

–  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
–  Si en una iteración no hacemos ningún cambio el algoritmo ha

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

terminado

7/36


a
c
i
t



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

Ejemplo

8/36

Ejemplo

h Lh(2) Path Lh(3) Path

Lh(4) Path Lh(5) Path

Lh(6) Path

0 ∞

-

1 2

2 2

3 2

4 2

1-2

1-2

1-2

1-2

∞

5

4

3

3

-

1-3

1-4-3

∞

1

1

1-4-5-3 1

1-4-5-3 1

-

∞

1-4 ∞

1-4

1-4

1-4

2

2

2

-

-

∞

∞

-

-

1-4-5 10

1-3-6

1-4-5 4

1-4-5-6

1-4-5 4

1-4-5-6


a
c
i
t



,



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

I



I

I

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



I

l



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

i

I


e
d



a
e
r
Á

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

l



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

i

I



,



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

I

I

I



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

I



a
c
i
t



e
d



a
e
r
Á

Esta demostrado
•  Los dos convergen bajo condiciones de topología estática (no
•  Los dos convergen a la misma solución
•  Si los enlaces cambian los algoritmos tratan de recalcular los

cambian los enlaces ni sus pesos)

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


a
c
i
t



l



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

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

i

I



,



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

I

I

I



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

I



e
d



a
e
r
Á

–  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
–  Es suficiente con intercambiar información entre nodos vecinos
–  Se puede actualizar la el coste y el camino en cada nodo basado en la

realidad vale con el siguiente salto)

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


a
c
i
t



,



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

I



I

I

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



I

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

2

2

S

5

1

3

5

5

3

3

8

13/36


a
c
i
t



,



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

I



I

I

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



I

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

2

2

S

5

1

3

5

1

3

3

8

14/36


a
c
i
t



,



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

I

I

I



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

I



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
•  Se obtiene un algoritmo que se adapta a la

aplicando continuamente.


a
c
i
t



,



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

I

I

I



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

I



l



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

i

I


e
d



a
e
r
Á

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


a
c
i
t



,



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

I

I



I

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



I

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 i