TEMA 5: Encaminamiento







5.1 Introducción

Podemos definir encaminamiento como un proceso mediante el cual tratamos de encontrar un camino entre dos puntos de la red: el nodo origen y el nodo destino. El objetivo que se persigue es encontrar las mejores rutas entre pares de nodos j-k.
 
a) Mejor Ruta. Por mejor ruta se entiende aquella que cumple alguna de estas condiciones: 
  • presenta el menor retardo medio de transito, 
  • consigue mantener acotado el retardo entre pares de nodos de la red (Tjk<To), 
  • consigue ofrecer altas cadencias efectivas independientemente del retardo medio de transito 
  • ofrezca el menor coste. 
b) Métrica de la Red.  Citaremos dos de ellas: 
  • Numero de saltos (canales) necesarios para ir de un nodo a otro. No se comporta de forma óptima, pero si ofrece buenos resultados, y es empleada con bastante frecuencia.. La distancia (valor que se asocia a cada canal) es igual a 1 para todos los canales. 
  • Retardo de Transito entre nodos vecinos. En este caso la distancia se expresa  en unidades de tiempo (p.e ms), y no es constante a lo largo del tiempo sino que depende del trafico que soporta el canal. 

Algunos de los problemas con los que nos encontramos a la hora de encaminar son:

Por tanto, el encaminamiento debe proveer a la red de mecanismos para que ésta sepa reaccionar ante situaciones como: La nomeclatura que utilizaremos es la siguiente: Nos centraremos en redes de conmutación de paquetes, tanto en modo datagrama como en modo circuito virtual: Los requisitos del algoritmo de encaminamiento son:

5.2 Métodos de Encaminamiento

5.2.1 Conceptos Básicos

Veamos la estructura general de un nodo de conmutación de paquetes, lo cual nos valdrá para hacer una posterior claseficación de los métodos de encaminamiento atendiendo a la forma en la que los nodos recogen y distribuyen la información que les llega de la red y a otros factores:

Básicamente, es funcionamiento es el siguiente: A partir de la RIB, se utiliza el algoritmo de encaminamiento para calcular la FIB, y cuando una PDU llega al nodo, se consulta esta FIB.

Ejemplo:
 
 

Tabla de Encaminamiento del NODO D:



 
 
 
 
 

Destino Next Coste
A E 9
B C 7
C C 2
D D 0
E E 5
F E 6

El numero que aparece junto a los enlaces representa el 'coste' o 'distancia' de los mismos, que puede ser constante o variable.

Llamarémos METRICA a la magnitud o medida a optimizar (retardo, ancho de banda, coste económico, etc).
 
 

5.2.2 Clasificación de los Métodos de Encaminamiento

1.- En función de donde se decide encaminar: 2.- En función de la adaptabilidad:

5.2.2.1 Vector de Distancias

Cada nodo informa a sus nodos vecinos de todas las distancias conocidas por él, mediante vectores de distancias (de longitud variable según los nodos conocidos). El vector de distancias es un vector de longitud variable que contiene un par (nodo:distancia al nodo) por cada nodo conocido por el nodo que lo envia, por ejemplo (A:0;B:1;D:1) que dice que el nodo que lo manda dista "0" de A,"1" de B y "1" de D, y de los demás no sabe nada (ésta es la forma en la que un nodo dice lo que sabe en cada momento). El nodo solo conoce la distancia a los distintos nodos de la red pero no conoce la topologia. Estos vectores de distancia se envían periódicamente y cada vez que varíe su vector de distancias. Veamos el siguiente ejemplo:










El vector de distancias de A sería:
 
 











Este vector de distancias de A llega al nodo B, el cual lo utiliza para actualizar el suyo:
 
 











Este VDB pasa al nodo A, el cual actualiza el suyo, etc.

Al cabo de un tiempo, se estabiliza la información de cada nodo, es decir, sus vectores de distancia quedan constantes aún sin dejar de enviarse información periódicamente.

Con todos los vectores recibidos, cada nodo monta su tabla de encaminamiento ya que al final conoce qué nodo vecino tiene la menor distancia al destino del paquete, pues se lo han dicho con el vector de distancias.

El envío de vectores de distancia entre nodos tiene lugar en el plano de control.

Si no se sabe a donde enviar un paquete, se descarta.

Ventajas del método:

(NOTA: los nodos no tienen información topologica de la red completa, es decir, pueden conocer la distancia a nodos lejanos, pero no donde están).

Inconvenientes del método:

(NOTA: Los bucles (situación que se da cuando los paquetes pasan más de una vez por un nodo) ocurren porque los criterios de los nodos no son coherentes, generalmente debido a que los criterios de encaminamiento o no han convergido después de un cambio en la ruta de un paquete; cuando por cualquier causa un paquete sufre un cambio de encaminamiento, la red tarda en adaptarse a ese cambio pues la noticia del cambio tiene que llegar a todos los nodos. Es en ese transitorio cuando se pueden dar los bucles, ya que unos nodos se han adaptado y otros no. El objetivo de los algoritmos de encaminamiento es detener el curso de los paquetes antes de que se produzcan bucles. Esto es importante sobre todo cuando se envían los paquete s por varias rutas simultáneamente (técnicas de inundación, etc...)).
 

5.2.2.2 Estado de Enlaces

Cada nodo difunde a todos los demás nodos de la red sus distancias con sus enlaces vecinos, es decir, cada nodo comunica su entorno local a todos los nodos. Así cada nodo es capaz de conocer la topología de la red. La clave y dificultad de este metodo es la difusión.

Ventajas del método:

Inconvenientes del método:

5.2.2.3 Comparación de los Métodos de Encaminamiento

 
Tipos de Encaminamiento Recepción de Información de Control Envío de Información de Control Decisión de encaminamiento (calculo de FIB) Adaptación
Estático NO NO OFF-LINE NO
Q-Estático NO NO OFF-LINE Reducida
Centralizado Nodos -> Nodo Central Nodo Central -> Nodos Nodo Central SI
Aislado NO NO -- SI
Distribuído Todos los nodos Todos los nodos Todos los nodos si

NOTA: En los encaminamientos estático y cuasi-estático la información necesaria se recoge y envía mediante gestión (al crear la red y en operaciones de mantenimiento), y los cálculos de la FIB se realizan off - line (mediante gestión, es decir en una máquina a parte).

5.3 Algoritmos de Encaminamiento

5.3.0 Introducción

Existen varios tipos de algoritmos de encaminamiento:

5.3.1 Notación

Distancia o coste de un canal: es una medida de la calidad de un enlace en base a la métrica que se haya definido (por ej., para el método de Gerla es la sensibilidad al aumento de tráfico; otras veces es coste económico, probabilidad de error, etc.).

dij     es la distancia del enlace entre dos nodos 'i' y 'j' contiguos. Si no existe enlace entre dichos nodos, valdrá infinito. Si 'i' es igual a 'j' (se trata del mismo nodo), esta distancia será nula.

Dij = D[ i,j] es la distancia entre dos nodos no contiguos.

P[ i,j] = (K1 = i, ..., Kn = j)    es el Path o camino tal que
 
 







"Si P[ i,j] es un camino mínimo y P[ r,t] es un subcamino de P[ i,j] , éste también será mínimo".
 
 

5.3.2 Algoritmo de Dijkstra

Es un algoritmo iterativo que debe ejecutarse para todos y cada uno de los nodos de la red. Este algoritmo, aplicado a un nodo, tiene una complegidad del orden de N² operaciones, por lo que aplicado a los N nodos de la red, resultará tener una complejidad del orden de N³ operaciones (siendo N el número de nodos de la red), por lo que es facil imaginar que no se trata de un algoritmo eficiente para redes de gran tamaño.. A cada nodo se le asigna una etiqueta, que es un indicador de la distancia del nodo origen al nodo en cuestión. Así, se hace una partición de la red: se crea un conjunto de nodos con etiqueta permanente (conjunto P) y un conjunto de nodos con etiqueta tentativa (conjunto T), es decir, un conjunto de nodos cuya etiqueta puede cambiar en las siguientes iteraciones.

Pasos del algoritmo:

1.- PASO 0 (INICIACIÓN):
2.- PASO 1: 3.- PASO 2 (ACTUALIZACIÓN):
4.- SALTO AL PASO 1.
Veamos, para mayor claridad del método, un ejemplo:
Tenemos la siguiente red: 

Para s = 1: 

(i=4): añadimos nodo 'i' a P. Como P no contiene a todos los nodos 3, 5 y 6:

Vemos que tenemos empate entre los nodos 2 y 5, luego elegimos uno al azar: i=2:

Seguimos con (i=5): Ahora con (i=3): 

El arbol final de encaminamiento del nodo 1 al resto de los nodos de la red queda:

No obtiene directamente las tablas de encaminamiento, sino las distancias entre nodos (arbol de encaminamiento), las cuales se tendrán que traducir a unas tablas de encaminamiento en todos los nodos. Para nuestro ejemplo, en el nodo 1, tendríamos para el caso de encaminamiento fuente y encaminamiento salto a salto las siguientes tablas, respectivamente:
 
 







El algoritmo de Dijkstra puede utilizarse como algoritmo estático y también como algoritmo dinámico centralizado, que consistiría en que hubiera un nodo central al que todos los demás nodos de la red enviaran información de su estado y del de los enlaces que salen de ese nodo. El nodo central recalcularía las distancias de todos los canales, aplicaría el algoritmo de Dijkstra y mandaría las nuevas tablas de encaminamiento a todos los nodos de la red.

Veamos otro ejemplo (i = 1):
 
 

El resultado, por pasos, es el siguiente:
1.- P = {1}; T = {2,3,4,5,6}; D1K = {0,1,-,4,-,-}

2.- P = {1,2}; T = {3,4,5,6}; D1K = {0,1,4,4,2,-}

(NOTA: las dos nuevas distancias las conozco a través del nodo que acabo de incluir en P)

3.- P = {1,2,5}; T = {3,4,6}; D1K = {0,1,3,3,2,6}

4.- P = {1,2,5,4}; T = {3,6}; D1K = {0,1,3,3,2,6}

5.- P = {1,2,5,4,3}; T = {6}; D1K = {0,1,3,3,2,5}

6.- P = {1,2,5,4,3,6}; T = {}; D1K = {0,1,3,3,2,5}

Luego la mínima distancia del nodo 1 al resto es: D1K = {0,1,3,3,2,5}

5.3.3 Algoritmo de Floyd-Marshall

A diferencia del algoritmo anterior (algoritmo de Dijkstra), que consideraba un nodo origen cada vez, este algoritmo obtiene la ruta más corta entre todo par de nodos (todos con todos). Itera sobre el conjunto de nodos que se permiten como nodos intermedios en los caminos. Empieza con caminos de un solo salto y en cada paso ve si es mejor la ruta de la iteración anterior o si por el contrario conviene ir por otro nodo intermedio más(aquél sobre el cual se itera).

 Para ello se construye la matriz D, cuyos elementos, Dij, son las etiquetas (indicadores de distancia) de la ruta entre el nodo i y el j. El algoritmo es el siguiente:

es el camino del nodo 'i' al nodo 'j' pasando por 'n' nodos intermedios.

Pasos del algoritmo:

1.- PASO 0 (INICIACIÓN):
2.- PASO 1 (ITERACIÓN):
En cada paso se ve si es mejor la ruta de la iteración anterior o si es mejor ir a través del nodo n.

Como ejemplo, para la siguiente red, tendremos la siguiente secuencia de matrices:
 
 











Nota: El nodo 1 es el nodo A de la red, el 2 es el B y así sucesivamente.

La segunda matriz tiene el nodo 1 como nodo intermedio, la tercera matriz tiene el nodo 2 como nodo intermedio, ... y así hasta la última matriz que tiene el nodo 5 como nodo intermedio y da como resultado la matriz de distancias mínimas buscada.

La primera fila de la matriz (distancias del nodo A a todos los demás) coincidiría con las etiquetas halladas con Dijkstra.

 La última matriz es la matriz de distancias buscada, ya que se han probado todos los nodos intermedios. Hay que tener en cuenta que el algoritmo da sólo la menor distancia; se debe manejar información adicional para encontrar tablas de encaminamiento.

 La complejidad de este algoritmo es del orden de N3, igual que para Dijkstra. Para un encaminamiento distribuído con estado de enlaces es mejor Dijkstra, que tiene una menor complejidad para un nodo dado.
 
 

5.3.4 Algoritmo de Bellman-Ford

Encuentra la mínima distancia de un nodo dado al resto de los nodos, y si se lleva información adicional, proporciona las tablas de encaminamiento, al igual que los anteriores.

 Itera sobre el número de saltos, h, es decir, se busca el mejor camino, el de distancia más corta, con la restricción de llegar al destino en un número de saltos h (número de la iteración). No encuentra las mejores rutas hasta que el algoritmo no se ha ejecutado por completo.

Es decir, consiste fundamentalmente en calcular la distancia de un nodo (aquel para el cual aplicamos el algoritmo) a los demas sin dar ningún salto, luego dando uno, etc.

 Sea el nodo i aquél para el que queremos encontrar las mejores rutas al resto de nodos. El algoritmo es el siguiente:

Pasos del algoritmo:

1.- PASO 0 :
n = 0 ('n' es el número de saltos)
2.- PASO 1:
Veamos el siguiente ejemplo con la red:

Tendremos entonces:












 
 

(vemos que con un salto, 'cuesta' más llegar al nodo 3 (distancia 5) que con dos saltos (distancia 4))










y paramos, ya que (n=4) y (n=5) no aportan mejora alguna.
 
 

Se prueba dando un salto más. Notar que está permitido el caso i=j, resultando entonces que no se da un nuevo salto (era mejor la ruta hallada antes).

Tiene una complejidad del orden de N3 por cada nodo que realiza el algoritmo, es decir, un orden mayor que Dijkstra. El interés del algoritmo radica en que se asemeja al de una red en la que se parte de la ignorancia total de un nodo, en la siguiente iteración conoce a sus nodos vecinos y así va progresivamente conociendo nodos más lejanos. Puede verse que esta es la forma de trabajar de un encaminamiento mediante vector de distancias. Para ello, necesita ser enunciado de forma distribuída, de la forma que vemos a continuación.

5.3.5 Algoritmo de Bellman-Ford Distribuído

Es la base de un algoritmo de vector de distancias.Se ejecuta para cada nodo i.


 
 

Pasos del algoritmo:

1.- PASO 0 :
2.- PASO 1 (ACTUALIZACIÓN): cada cierto tiempo, el nodo 'i' envía a sus vecinos D(i,j), recibiendo a su vez de todos sus vecinos 'j' los D(j,k). Entonces, el nodo 'i' calcula la distancia de 'i' a 'k' pasando por 'j':

y realiza la siguiente actualización de su tabla de encaminamiento::

El proceso de actualización se sigue repitiendo: cuando un nodo i recibe un vector de distancias de un nodo vecino j, calcula las distancias a todos los demás nodos k a través del vecino j, y si es mejor que por el camino anterior se actualiza la tabla de encaminamiento del nodo i, ( n(i,k)=j) y las nuevas distancias D(i,k). Una vez obtenido el nuevo vector de distancias, i se lo manda a los demás nodos j para que éstos actualicen a su vez los suyos.

Pasemos al siguiente ejemplo:
 
 

INICIO (nodo A): 

Vector distancias de B: D(B,j) = (A,1;B,0;C,4;D,2;E,3)

Este VDB llega a A, el cual actualiza el suyo:
 
 

5.4 Anexo 1: Algoritmos de Inundación

En este algoritmo los nodos no intercambian información de control. Cuando un paquete llega a un nodo de la red, lo que éste hace es conmutarlo por todos los puertos de salida sin mirar ninguna tabla de encaminamiento.  De esta forma se asegura que el paquete llegue al destino.

Problema: si la topología presenta bucles el paquete estará dando vueltas de manera indefinida. Como consecuencia, se consume  capacidad de red ilimitada. Además, llegan paquetes duplicados.

Solución: La solución pasa por limitar la vida del paquete en la red TTL, es decir, establecer una caducidad. Cuando se genera un   paquete se incluye en un campo el número máximo de saltos que éste puede dar. Cada vez que ese paquete es conmutado el campo "número de saltos" se decrementa en una unidad hasta que sea cero, en cuyo caso los nodos ya no lo conmutan, sino que lo descartan. De esta manera  aseguramos una existencia limitada de paquete dentro de la red.
Es necesario establecer el valor inicial del contador lo suficientemente alto como para que el paquete sea capaz de llegar al destino, pero tampoco excesivamente alto para que no consuma muchos recursos. La decisión que se adopta es inicializar el contador al número de saltos necesario para llegar desde cualquier nodo de la red a otro (El valor es el mismo para todos los paquetes generados, sea cual sea el nodo de la red que lo haga).

        Otra solución es determinar si un nodo ha conmutado ya ese paquete. En este caso, un nodo origen marca el paquete generado con un número de secuencia de tal forma que la unicidad de ese paquete viene dada por el par (origen, secuencia). Cuando un nodo conmuta un paquete  mira en tabla; si ya lo ha conmutado lo descarta, y si no lo ha conmutado lo introduce en la tabla. Como ventaja respecto de la solución anterior se consume menos capacidad de red, pero posee el inconveniente de que la tecnología del nodo es muy compleja y el tamaño de las tablas puede ser muy grande. Además esta solución puede dar mayores retardos que la anterior.

        Concluyendo, la inundación es buena si tenemos la red sobredimensionada, ya que no tendríamos tantas limitaciones en cuanto a ocupación de recursos. En este caso, la inundación es el algoritmo más robusto y óptimo, ya que encuentra todas las rutas, entre ellas la mejor.

    Por último, queda solucionar el problema de multiplicidad de paquetes en  el nodo destino, pero eso queda para los niveles superiores de la jerarquía OSI.
 

5.5 Anexo 2: Algoritmo de Aprrendizaje hacia Atrás


Podemos observar que no es completamente aislado, ya que hace uso de tablas de encaminamiento.

Son los usados en redes locales. Cuando llega un paquete a un nodo con destino a otro nodo cualquiera, se hace lo siguiente:

  1. Si  no se conoce el nodo destino se inunda y se incrementa el campo número de saltos dados por el paquete.(al contrario que en inundación, donde se decrementaba).
  2. Si el destino se conoce, se envia el paquete por la ruta que se indica en las tablas.
El aprendizaje se basa en que partimos de no tener ninguna información de control, y segun se van produciendo inundaciones se aprende. Cuando llega un paquete se mira el origen , el puerto a través del que ha llegado y el número de saltos dados por ese paquete hasta que ha llegado. Si no teníamos ninguna entrada en la tabla de encaminamiento con el nodo del que ha llegado o si la teniamos pero con numero de saltos mayor (mayor distancia) se actualizan las tablas. Para evitar que un paquete esté dando vueltas eternamente en la red y por lo tanto consuma recursos innecesariamente, se limita el número de saltos que éste puede dar.

En principio, cuando todos los nodos hayan aprendido las mejores rutas se acabará la inundación. Sin embargo, a las entradas se les asocia un tiempo de vida, que se renueva cada vez que se hace uso de la entrada. Si transcurrido el tiempo de vida la entrada no ha sido empleada se borra, volviendo a inundar. Así se logra que la red se adapte a los cambios.

  •  Problema: la inundación consume recursos indefinidamente y pueden aparecer bucles. Esto puede evitarse añadiendo un poco de control: en los paquetes se introduce información sobre el número de saltos que ha realizado éste (se tiene un contador que se incrementa en cada salto); cuando este número llega a un valor máximo, se descarta el paquete. De esta forma podemos cuantificar distancias además de conocer la conectividad entre dos nodos.

    •        Este tipo de algoritmos es óptimo (consiguen la mejor ruta, ya que en realidad consiguen todas), siempre que se controle que no se saturen los enlaces de los nodos.

     Estos algoritmos se llaman de Backward Learning, o aprendizaje hacia atrás, debido a que la forma que tienen de aprender los nodos es a través de la información que les llega del nodo origen.

    Vuelta al Indice de Apuntes
    Ver problemas de este tema.

    5.6 Bibliografía

      Tanenbaum, Andrew S., Computer Networks, Prentice-Hall, 1996. 
      Bertsekas, D. y Gallager, R., Data Networks, 2a edición, Prentice-Hall, 1992. 
      Comer, Douglas E., Internetworking with TCP/IP, 3a edición, Volumen 1: Principles, Potocols and Architectures, Prentice-Hall, 1995.