Planificación y Administración de Redes/Tema 10/Clasificación

Los métodos de encaminamiento los podemos clasificar en función de:

• El procedimiento de encaminamiento.
• Las tablas de encaminamiento empleadas.

En función del procedimiento.

Los procedimientos de encaminamiento pueden ser:

Determinísticos o Estáticos

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

Estático

Las tablas de encaminamiento de los nodos se configuran de forma manual y permanecen inalterables hasta que no se vuelve a actuar sobre ellas. La adaptación a cambios es nula. Tanto la recogida como la distribución de información se realiza por gestión (se realiza de manera externa a la red), sin ocupar capacidad de red. El calculo de ruta se realiza off-line (en una maquina especifica),y las rutas pueden ser las óptimas al no estar sometido al requisito de tiempo real.

Este tipo de encaminamiento es el óptimo para topologías en los que solo hay una posibilidad de encaminamiento (topología en estrella).

Cuasiestático

Este encaminamiento, es igual que el estático pero en vez de dar una sola ruta fija, se dan además varias alternativas en caso de que la principal no funcione, de ahí que tenga una adaptabilidad reducida.

Este tipo de encaminamiento puede dar lugar a situaciones incoherentes, ya que no se enteran todos los nodos de los problemas de la red, sino sólo los adyacentes a los problemas.

Adaptativos o Dinámicos

En este tipo de procedimientos de encaminamiento la información se recoge y envía de forma periódica con el fin de detectar cambios en la red.

Centralizado

En este tipo de encaminamiento, todos los nodos son iguales salvo el nodo central, que recoge la información de control de todos los nodos y calcula la FIB (tabla de encaminamiento) para cada nodo, es decir, el nodo central decide la tabla de encaminamiento de cada nodo en función de la información de control que éstos le mandan. El inconveniente de este método es que consumimos recursos de la red, y se harían necesaria rutas alternativas para comunicarse con el nodo central. La adaptación a cambios es perfecta siempre y cuando las notificaciones de los cambios lleguen antes de iniciar los cálculos de las rutas.

Aislado

Se basa en que cada vez que un nodo recibe un paquete que tiene que reenviar (porque no es para él) lo reenvía por todos los enlaces salvo por el que le llegó.

Distribuido

En este tipo de encaminamiento todos los nodos son iguales, todos envían y reciben información de control y todos calculan, a partir de su RIB (base de información de encaminamiento) sus tablas de encaminamiento. La adaptación a cambios es optima siempre y cuando estos sean notificados.

Hay dos familias de procedimientos distribuidos:

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 envía, 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 topología.

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.

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 método es la difusión.

A continuación se muestra una tabla comparativa de todos los tipos de encaminamiento vistos.

Clasificació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	Adaptación a los cambios
Estático	NO	NO	OFF-LINE	NO
Cuasi - estático	NO	NO	OFF-LINE	Reducida
Centralizado	Nodos-Nodo central	Nodo central-Nodos	Nodo central	SI
Aislado	NO	NO	Inundación, por ejemplo	SI
Distribuido	Todos los nodos	Todos los nodos	Todos los nodos	SI

Comparación Vector de distancias – Estado del Enlaces.

Haremos una comparación entre los algortitmos de vector de distancias y de estado de enlaces, ambos del tipo distribuido:

Consumo de capacidad.

Lo ideal es que el tráfico de control sea lo más pequeño posible. Con vectores de distancia se transmiten vectores cuyo tamaño es del orden del número de nodos de la red pues cada nodo comunica a su vecino todas las distancias que conoce; con procedimientos de estado de enlace, el tamaño del tráfico enviado es siempre el mismo independientemente del tamaño de la red. En consecuencia, consume más capacidad un vector de distancias.

Consumo de memoria

El encaminamiento basado en estado de enlace hace que cada nodo almacene toda la topología de la red, sin embargo con vectores de distancias sólo ha de almacenar distancias con el resto de los nodos. Luego consume más memoria en los nodos un procedimiento basado en estado de enlace.

Adaptabilidad a los cambios

El método de vector de distancia es más sencillo, pero se adapta peor a los cambios que el de estado de enlace. Esto es porque mientras que este último tiene información de toda la red, el primero sólo sabe a quién tiene que reenviar un paquete, pero no tiene información de la topología. Luego se adapta mejor un encaminamiento de estado de enlaces.

No obstante, el encaminamiento basado en vector de distancias es mucho menos complejo que el de estado de enlaces, cosa que en algunos casos prácticos puede llegar a ser muy importante.

En función de las tablas de encaminamiento empleadas.

Los nodos manejan tablas de encaminamiento, en las que aparece la ruta que deben seguir los paquetes con destino a un nodo determinado de la red.

Podemos distinguir entre encaminamiento salto a salto y encaminamiento fijado en origen. Nosotros veremos con detalle sólo el primer tipo (salto a salto).

Encaminamiento salto a salto

En la literatura inglesa, este tipo de encaminamiento se denomina como hop by hop. Se basa en que cada nodo no tiene que conocer la ruta completa hasta el destino, sino que sólo debe saber cuál es el siguiente nodo al que tiene que mandar el paquete: las tablas dan el nodo siguiente en función del destino. Como ejemplo, tomemos la siguiente red:

Red de ejemplo

Las tablas de encaminamiento de los nodos A y B serán:

Tabla 1. Tablas de encaminamiento para la red de laFigura 1

Tabla de encaminamiento del nodo A		Tabla de encaminamiento del nodo B
Destino	Siguiente nodo	Destino	Siguiente nodo
B	B	A	A
C	B	C	C
D	B	D	C
E	H	E	C
F	H	F	C
G	H	G	G
H	H	H	A

En la tabla de encaminamiento de cada nodo deberá aparecer una entrada en el campo destino por cada nodo que se pueda alcanzar desde el citado nodo, y en el campo siguiente nodo aparecerá el nodo vecino al que se deberá enviar los datos para alcanzar el citado nodo destino. Las soluciones propuestas no son únicas, pudiendo elegir otros caminos que minimicen el tiempo de retardo, el número de saltos, etc. La única condición que se impone es que debe haber consistencia: si, por ejemplo, para ir de A a B pasamos por C, entonces para ir de B a C no podremos pasar por A, porque entonces se formaría un bucle y el paquete mandado estaría continuamente viajando entre los nodos B y A, como puede comprobarse fácilmente.

Encaminamiento fijado en origen.

En inglés este encaminamiento se llama source routing. En él, son los sistemas finales los que fijan la ruta que ha de seguir cada paquete. Para ello, cada paquete lleva un campo que especifica su ruta(campo RI: Routing Information), y los nodos sólo se dedican a reenviar los paquetes por esas rutas ya especificadas. Así pues, son los sistemas finales los que tienen las tablas de encaminamiento y no se hace necesaria la consulta o existencia de tablas de encaminamiento en los nodos intermedios. Este tipo de encaminamiento suele ser típico de las redes de IBM.

Tabla 2. Tablas de encaminamiento para la red de laFigura 1

Tabla de encaminamiento del nodo A		Tabla de encaminamiento del nodo B
Destino	Ruta a seguir	Destino	Ruta a seguir
B	B	A	A
C	B-C	C	C
D	B-C-D	D	C-D
E	H-G-E	E	C-F-E
F	H-G-F	F	C-F
G	H-G	G	G
H	H	H	A-H

Comparación entre ambos tipos de encaminamiento.

Lo veremos por medio de la siguiente tabla:

Tabla 3. Comparación entre encaminamiento salto a salto y fijado en origen

	Fijado en Origen	Salto a Salto
Conocimiento	Los sistemas finales han de tener un conocimiento completo de la red	SIMPLICIDAD: Los nodos han de tener un conocimiento parcial de la red (saber qué rutas son las mejores)
Complejidad	Recae toda en los sistemas finales	En los sistemas intermedios ya que son los que tienen que encaminar
Problemas de Bucles	No hay bucles: el sistema final fija la ruta (ROBUSTEZ).	Sí pueden ocurrir: no se tiene una visión completa de la red (INCONSISTENCIA)

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