27 Enrutamiento2

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Temario
1.
2.
3.
4.
5.

Introducción
Protocolos y arquitectura
Redes de área local
Protocolos de Internet
Conmutación de paquetes
•
•

Principios
Problemas básicos
•
•
•
•

6.
7.
8.

Encaminamiento (y van 2)
Transporte fiable
Control de flujo
Control de congestión

Conmutación de circuitos
Gestión de recursos enconmutadores
Protocolos de control de acceso al medio
2

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

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ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

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

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Algoritmo de Bellman-Ford
• Encontrar los caminos mas cortosdesde 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 parael caso h-1

• …

5

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

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(ni ,nj )
w(ni ,nj ) = infinito si no hay enlace
• s nodo origen del que pretendemos calcular los
caminos
• h número deiteració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

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Algoritmo de Bellman-Ford
• 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)=minj[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
7

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Áreade Ingeniería Telemática

Ejemplo

8

Ejemplo

h Lh(2) Path Lh(3) Path

Lh(4) Path Lh(5) Path

Lh(6) Path

0 ∞

-

∞

-

∞

-

∞

-

∞

-

1 2

1-2

5

1-3

1

1-4

∞

-

∞

-

2 2

1-2

4

1-4-3

1

1-4

2

1-4-5

10

1-3-6

3 2

1-2

3

1-4-5-3

1

1-4

2

1-4-5

4

1-4-5-6

4 2

1-2

3

1-4-5-3

1

1-4

2

1-4-5

4

1-4-5-6

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de IngenieríaTelemática

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 enmenos iteraciones)
• Pero hay otros factores…

10

ARQUITECTURA DE REDES,
SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

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