PDF de programación - Protocolos de Enrutamiento Para la Capa de Red en Arquitecturas de Redes de Datos

Protocolos de Enrutamiento Para la Capa de Red en
Arquitecturas de Redes de Datos



Andres Gomez Marquez



Dpto. Informática. Universidad Cooperativa de Colombia.

E-mail: [email protected]


Resumen. Los protocolos de enrutamiento para la capa de red son usados para
resolver peticiones de servicios de envío de paquetes de datos a través de
diferentes redes de datos. El punto más importante de este estudio es mostrar los
diferentes algoritmos de enrutamiento que resuelven esta cuestión, y a su vez
compararlos en forma cualitativa para conocer cuáles son sus fortalezas y cuáles
son sus puntos débiles. También se analiza brevemente qué pasa en la capa de
red en la Internet.

Palabras Claves: Protocolo de Enrutamiento – Algoritmos Estáticos –
Algoritmos Dinámicos

1 Introducción

Teniendo en cuenta las necesidades y los avances producidos en una sociedad
sumamente compleja, resulta de gran importancia destacar tanto la transmisión de
información, como la necesidad de que ésta llegue a destino en el momento preciso
mediante el uso de las redes.
Es a través de la Internet que queda probado, y todos los días se muestra con mejor y
mayor detalle, que ésta ha sido y será revolucionaria en las áreas de los servicios
financieros, de entretenimiento, salud, educación y gobierno (Mondel y Hof, 2001).
El proceso de digitalización de todas las técnicas de comunicación, transmisión (cable,
satélite) y recepción, producen nuevas convergencias entre diferentes sectores (cultura,
comunicación, lengua, educación, telecomunicaciones, etc.), pero muy especialmente lo
que producen es la transformación de los "espacios de comunicación" los límites y las
fronteras y, como consecuencia, la transformación de los espacios de intercambios
culturales. De hecho, todas las sociedades, por definición, han sido y serán "sociedades
de la comunicación”.
Los principales cambios estructurales de la sociedad se producen ahora entorno del
tratamiento y de la transmisión de la información.
La capa de Red, dentro de una arquitectura de rede de datos, es la que se encarga de
llevar los paquetes de datos desde el origen (estación transmisora) hasta el destino
(estación receptora). Llegar a destino, en tiempo y forma, puede requerir que el

algoritmo de ruteo, que es el encargado de escoger las rutas y las estructuras de datos,
cumpla con ciertas propiedades que aseguren la eficiencia de su trabajo.
Estas propiedades son: corrección, estabilidad, robustez, equitatividad, sencillez y
optimalidad.
La corrección y la sencillez casi no requieren comentarios; no así la necesidad de
robustez, la cual se refiere a que el algoritmo debe ser diseñado para que funcione
dentro de la red por años, sin fallas generales. El algoritmo deberá estar preparado para
manejar cambios de topología y tráfico sin requerir el aborto de las actividades o el
rearranque de la red.
La equitatividad y la optimalidad resultan con frecuencia contradictorias, ya que
muchas veces se requiere una concesión entre la eficacia global (optimización) y la
equitatividad; es decir, antes de intentar encontrar un justo medio entre estas dos, se
debe decidir qué es lo que se busca optimizar.
Minimizar el retardo de los paquetes (disminuyendo escalas y ancho de banda) y
maximizar el rendimiento total de la red sería la combinación más apropiada para un
algoritmo de ruteo.

2 Algoritmos de Ruteo

La capa de Red proporciona la dirección lógica que permite que dos sistemas dispares
que se encuentran en redes lógicas diferentes determinen una posible ruta para
comunicarse.
En la capa de red es donde residen los algoritmos que implementan los protocolos de
enrutamiento.
En la mayoría de las subredes, los paquetes requerirán varias escalas para completar el
viaje. La excepción serían las redes de difusión, pero aún aquí es importante el
enrutamiento, ya que el origen y el destino pueden no estar en la misma red.

El algoritmo de enrutamiento es la parte del software de la capa de red encargada de
decidir la línea de salida por la que se transmitirá un paquete de entrada.
Si la subred usa datagramas entonces esta decisión debe hacerse cada vez que llega un
paquete de datos de entrada, debido a que la mejor ruta podría haber cambiado desde la
última vez.
Si la subred utiliza circuitos virtuales internamente, las decisiones de enrutamiento se
tomarán sólo al establecerse el circuito y los paquetes seguirán la ruta previamente
establecida.

3 Clasificación de los Algoritmos de Enrutamiento

Algoritmos no adaptables: No basan sus decisiones de enrutamiento en mediciones o
estimaciones del tráfico ni en la topología. La decisión de qué ruta tomar de I a J se
calcula por adelantado, fuera de línea y se cargan en los routers al iniciar la red. Éste
procedimiento se llama enrutamiento estáticos. La desventaja de este tipo de
algoritmos es que no es posible responder a situaciones cambiantes como por ejemplo
saturación, exceso de tráfico o fallo en una línea.
En un conjunto de redes complejas, se necesita cierto grado de cooperación “dinámica”
entre los dispositivos de encaminamiento. En particular se deben evitar aquellas
porciones de red que sufren congestión, entendiéndose esto como aquella situación
donde hay demasiados paquetes en alguna parte de la subred, y como consecuencia el
rendimiento de ésta baja.
Para poder tomar estas decisiones de encaminamiento dinámicas, los dispositivos
involucrados en el ruteo deben intercambiar información usando algoritmos de
encaminamiento especiales para este propósito. La información que se necesita sobre el
estado del conjunto de redes tiene que venir expresada en términos de qué redes son
accesibles a través de qué dispositivos y en términos de las características de retardo de
varias rutas.
Algoritmos adaptables: En contraste con los algoritmos no adaptables, éstos cambian
sus decisiones de enrutamiento para reflejar los cambios de topología y de tráfico.
Difieren de los algoritmos estáticos en el lugar de obtención de su información (ej.
localmente, en los routers adyacentes o de todos), el momento del cambio de sus rutas
(ej. cada ∆t seg., o cuando cambia la carga) y la métrica usada para la optimalidad (ej.
distancia, nº de escalas, tiempo estimado del tránsito). Este tipo de algoritmos no
pueden ser demasiado complejos ya que son implementados en los routers y deben
ejecutarse en tiempo real con recursos de CPU y la memoria con que el router dispone.

4 Principio de Optimización

Este postulado establece que, si el enrutador J está en la trayectoria óptima del enrutador I al
enrutador K, entonces la trayectoria óptima de J a K también está en la misma ruta.
Haciendo referencia a la figura 1, llamemos r1 a la parte de la ruta de I a J, y r2 al resto de la
ruta. Si existiera una ruta mejor que r2 entre J y K, podría concatenarse con r1 para mejorar
la ruta entre I y K, contradiciendo nuestra aseveración de que r1 y r2 es óptima.

Como consecuencia directa del principio de optimalidad, podemos ver que el grupo de
trayectorias óptimas de todas las de orígenes a un destino dado forma un árbol con raíz
en el destino. Ese árbol que se forma, se llama árbol de descenso, donde la métrica de
distancia es el número de escalas. El árbol de descenso puede no ser único, pueden
existir otros árboles con las mismas longitudes de trayectoria.
La meta de todos los algoritmos de enrutamiento es descubrir y usar los árboles de
descenso para todos los enrutadores.



Figura 1. (a) Subred. (b) Árbol descendente para el ruteador B.

Dado que un árbol de descenso ciertamente es un árbol, no contiene ciclos, por lo que
cada paquete será entregado con un número de escalas finito y limitado.
En la práctica, no siempre sucede esto, los enlaces y los enrutadores pueden caerse y
reactivarse durante la operación, por lo que diferentes enrutadores pueden tener ideas
distintas sobre la topología actual de la subred. El fin último de los algoritmos de ruteo
es descubrir y usar los árboles de descenso de todos los enrutadores.

5 Algoritmos Estáticos

Enrutamiento por trayectoria más corta

Esta es una técnica de amplio uso en muchas formas, ya que es sencilla y fácil de
entender. La idea es armar un grafo de la subred en el que cada nodo representa un
enrutador y cada arco del grafo una línea de comunicación (enlace). Para seleccionar
la ruta entre un par dado de enrutadores, el algoritmo simplemente encuentra en el
grafo la trayectoria más corta entre ellos.
El concepto de trayectoria más corta se debe a que la forma de medir la longitud de la
ruta es usando alguna métrica, entendiéndose por métrica al peso relativo que se da a
cada uno de los factores que intervienen en el cálculo de la distancia en una red, los
cuales podrían ser el número de saltos, la distancia física, el retraso de transmisión por
un paquete de prueba, el ancho de banda, el tráfico promedio, el costo de
comunicación, etc.
Se conocen varios algoritmos de cálculo de la trayectoria más corta entre dos nodos de
un grafo. Cada nodo se etiqueta (entre paréntesis) con su distancia al nodo de origen a
través de la mejor trayectoria conocida. Inicialmente no se conocen trayectorias, por lo
que todos los nodos tienen la etiqueta infinito. A medida que avanza el algoritmo y se
encuentran trayectorias, pueden cambiar las etiquetas, reflejando mejores trayectorias.
Una etiqueta puede ser tentativa o permanente. Inicialme