ALGORITMOS DE RUTEO
Los algoritmos de ruteo se dividen en dos clases: adaptativos y
no adaptativos. Los algoritmos no adaptativos determinan anticipadamente la
ruta a seguir. En cambio los algoritmos adaptativos intentan cambiar sus
decisiones de ruteo para reflejar los cambios de topología de red y en el
tráfico.
Ruteo
por el camino más corto.
Consiste en construir una gráfica de la subred, con cada nodo
representando una IMP y cada arco una línea de comunicación. Para escoger una
ruta entre cada par de IMP. El algoritmo sólo determina el camino más corto que
existe entre ellos, mediante algoritmos de ruta más corta.
Muchas veces ocurre que existe más de un camino óptimo, entonces
para reducir la carga en cada una de las líneas de comunicación se divide el
tráfico entre varios caminos.
Cuando un paquete llega para su reenvío, se hace una selección
de varias alternativas para que un paquete en particular. Para las subredes
virtuales se selecciona una ruta, pero el ruteo para los diferentes circuitos
virtuales se lleva a cabo de manera independiente.
El proceso de ruteo de camino múltiple es el siguiente. Cada IMP
mantiene una tabla con una ristra reservada para cada uno de los posibles IMP
destinatarios; cada ristra ofrece la mejor, la segunda mejor… línea de salida
para cada destino en particular. Antes de que se reenvié el paquete, un IMP
genera un número aleatorio y después selecciona entre diferentes alternativas
que se presentan. Los operadores calculan las tablas manualmente, cargándolas
en los IMP antes de que arranque la red y que no se modifique después.
Cuando se utiliza un ruteo centralizado, en alguna parte de la
red hay un RCC (Centro de control de ruteo). Periódicamente cada IMP transmite
la información de su estado al RCC; después el RCC recoge toda esta información
y con el conocimiento total de la red, calcula las rutas óptimas de todos los
IMP a cada uno de los IMP restantes utilizando un algoritmo de rutas más
cortas.
El ruteo centralizado tiene varios inconvenientes como por
ejemplo; si la subred tiene que adaptar a un tráfico variable, el calculo
tendrá que realizarse con mucha frecuencia y para una red grande, esto tomaría
bastante tiempo.
Si el RCC calcula la ruta optima para cada par de IMP, sin rutas
alternas, la perdida de una sola línea puede desconectar algunos IMP del RCC,
creando terribles consecuencias para el sistema. Pero si el RCC utiliza rutas
alternas se debilitara el argumento a favor de tener un RCC si es que se pueden
encontrar rutas óptimas.
Ruteo aislado
El algoritmo de ruteo asilado también se le conoce como la papa
caliente. El algoritmo es el siguiente. En el momento en que le llega un
paquete al IMP, trata de deshacerse de el tan rápido como sea posible
poniéndolo en la cola de espera se salida más corta. El IMP cuenta los paquetes
que se encuentran en la cola de espera de cada una de las salidas.
Después se instala el nuevo paquete al final de la cola de
salida más corta sin tomar en cuenta el lugar a donde va la línea. Los paquetes
se acomodan en cola en cada una de las líneas esperando hasta que llegue el
momento de transmisión.
La inundación es un caso extremo del ruteo aislado, en la cual
cada paquete que llega se transmite un todas las líneas de salida, exceptuando
aquella por la que llega. Con la inundación se genera un número considerable de
paquetes duplicados. Si el emisor no conoce la longitud del camino, puede
iniciar el contador con el valor del peor caso, es decir, el valor del diámetro
completo de la subred.
En esta clase de algoritmos de ruteo cada IMD intercambia
periódicamente información de ruteo explicito con cada uno de sus vecinos. Por
lo general cada IMP mantiene una tabla de ruteo con una entrada por cada uno de
los demás IMP de la subred. Esta entrada consta de dos partes: la línea
preferida sea salida que se utilice para dicho destino, y alguna estimación del
tiempo de distancia hacia él.
Se supone que el IMP conoce la distancia a cada uno de sus
vecinos. Si la métrica es la de saltos, la distancia es solo un salto. Si la
métrica es la longitud de la cola de espera, el IMP simplemente investiga cada
una de las colas. Si la métrica es de retardo, el IMP puede medirlo en forma
directa con paquetes especiales de eco que el receptor sólo marca con un sello
de tiempo, y lo envía de vuelta tan rápido como puede.
Aun sin conocer los detalles de la topología y tráfico de la
subred, es posible hacer algunas declaraciones generales acerca de las rutas optimas;
una de estas se conoce como principio de optimización. Este principio declara
que si el IMP J esta en la trayectoria óptima que va del IMP I hasta el IMP K,
entonces la trayectoria óptima de J a K también se encuentra a lo largo de la
misma ruta.
Como una consecuencia directa del principio de optimización, el
conjunto de rutas óptimas procedentes de todos los orígenes a un destino dado,
forman un árbol cuya raíz sale del destino.
En algunos casos los hosts necesitan transmitir mensajes a todos
los demás hosts. En algunas redes los IMP pueden llegar a necesitar servicios
como distribuir la actualización de las tablas de ruteo. Entonces a la
transmisión de un paquete en forma simultanea se le conoce como difusión.
En el método de difusión no es necesario que la subred tenga
características especiales como que el emisor tiene que enviar un paquete
distinto a cada destino. Esto requiere que la fuente tenga una lista completa
de todos los destinos.
A) El ruteo multidestino
Cada paquete contiene una lista en donde se indican los destinos
deseados. Cuando un paquete llega a un IMP se comprueban todos los destinos
para determinar un conjunto de líneas de salida que necesitaran. El IMP genera
una nueva copia del paquete para cada una de las líneas de salida que
utilizarán. El conjunto de los destinos se subdivide entre las líneas de salida
y después de un número de saltos, cada paquete conducirá solo un destino y
podrá tratarse como un paquete normal.
B) Ruteo por árbol de expansión
El árbol de expansión es un subconjunto de una subred que
incluye todos los IMP. Si cada uno de los IMP conociera que las líneas
pertenecen al árbol de expansión, podría copiar un paquete de difusión de
entrada sobre todas las líneas del árbol de expansión con excepción de la línea
que llego.
El ruteo por árbol de expansión hace un uso muy eficaz del ancho
de banda, ya que genera un número mínimo de paquetes necesarios para realizar
el trabajo. El único problema es que cada IMP deberá tener conocimiento de
algún árbol de expansión al que se pudiera referir.
Este
capítulo aborda una revisión general acerca de los métodos y algoritmos de
ruteo de datos en una red. También se habla acerca de las ventajas y
desventajas de dichos métodos y menciona de las situaciones en donde es
conveniente aplicar cada método de ruteo.
TANENBAUM.
Redes de ordenadores, cap 5.2
