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

Temario

,



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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

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

,



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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

a
c

i
t

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

1/36

2/36

1

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

I



,



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

I

a
c

i
t

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

En clases anteriores…

a
c

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

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

,



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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

a Algoritmo de Bellman-Ford

c

i
t

• 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

• …

3/36

4/36

5/36

2

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

I



a Algoritmo de Bellman-Ford

c

• 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

,



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



i

í
r
e
n
e
g
n

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

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

á
m
e
e
T

i
t

a

c



l

• 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

anterior

– 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

terminado

a
c

i
t

Ejemplo

,



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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

6/36

7/36

8/36

3

Ejemplo

h

Lh(2)

Path

Lh(3)

Path

Lh(4)

Path

Lh(5)

Path

Lh(6)

Path

∞0

1

2

3

4

2

2

2

2

-

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

Resumen 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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

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

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

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

10/36

11/36

4

,



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

I

a
c

i
t

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

a
c

Comparación

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

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

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

Topología variable

a
c

i
t

¿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

,



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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

,



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



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

Topología variable

a
c

i
t

• 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

12/36

13/36

14/36

5

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

I



,



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

I

a
c

i
t

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

,



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

I

a
c

i
t

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

Topología variable

a
c

• 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

Ventajas de Bellman-Ford

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

aplicando continuamente.

• 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

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:

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

cola

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

15/36

16/36

1