GU A DE ESTUDIO

Redes de Computadoras (Andrew. S. Tanenbaum)

5.2 Algoritmos de Enrutamiento
La función principal de la capa de red es enrutar paquetes de la máquina de origen a la de destino.
En la mayoría de las subredes, los paquetes requerirán varios saltos para completar el viaje.
La única excepción importante son las redes de difusión, pero aun aquí es importante el enrutamiento si el origen y el destinono están en la misma red.
Los algoritmos que eligen las rutas y las estructuras de datos que usan constituyen un aspecto principal del diseño de la capa de red.
El algoritmo de enrutamiento es aquella 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 de manera interna, esta decisión debe tomarsecada vez que llega un paquete de datos, dado que la mejor ruta podría haber cambiado desde la última vez.
Si la subred usa circuitos virtuales internamente, las decisiones de enrutamiento se toman sólo al establecerse un circuito virtual nuevo.
El enrutamiento de sesión es cuando una ruta permanece vigente durante toda la sesión de usuario (por ejemplo, durante una sesión desde una terminal, odurante una transferencia de archivos).
Se puede considerar que un enrutador realiza dos procesos internos.
Uno de ellos maneja cada paquete conforme llega, buscando en las tablas de enrutamiento la línea de salida por la cual se enviará. Este proceso se conoce como reenvío.
El otro proceso es responsable de llenar y actualizar las tablas de enrutamiento. Es ahí donde entra en acción el algoritmode enrutamiento.
Hay ciertas propiedades que todo algoritmo de enrutamiento debe poseer: exactitud, sencillez, robustez, estabilidad, equidad y optimización.
El algoritmo de enrutamiento debe ser capaz de manejar los cambios de topología y tráfico sin requerir el aborto de todas las actividades en todos los hosts y el reinicio de la red con cada caída de un enrutador.
La estabilidad también esuna meta importante del algoritmo de enrutamiento.
Existen algoritmos de enrutamiento que nunca alcanzan el equilibrio, sin importar el tiempo que permanezcan operativos.
Un algoritmo estable alcanza el equilibrio y lo conserva.
La equidad y la optimización pueden parecer algo obvias (ciertamente nadie se opondrá a ellas), pero resulta que con frecuencia son metas contradictorias.
Como términomedio, muchas redes intentan minimizar el número de saltos que tiene que dar un paquete, puesto que la reducción de la cantidad de saltos reduce el retardo y también el consumo de ancho de banda, lo que a su vez mejora la velocidad real de transporte.
Los algoritmos de enrutamiento pueden agruparse en dos clases principales: no adaptativos y adaptativos.
Los algoritmos no adaptativos no basan susdecisiones de enrutamiento en mediciones o estimaciones del tráfico y la topología actuales.
En contraste, los algoritmos adaptativos cambian sus decisiones de enrutamiento para reflejar los cambios de topología y, por lo general también el tráfico.
Los algoritmos adaptativos difieren en el lugar de donde obtienen su información (por ejemplo, localmente, de los enrutadores adyacentes o de todos losenrutadores), el momento de cambio de sus rutas (por ejemplo, cada ΔT segundos, cuando cambia la carga o cuando cambia la topología) y la métrica usada para la optimización (por ejemplo, distancia, número de saltos o tiempo estimado de tránsito).

5.2.2 Enrutamiento Por La Ruta Más Corta
La idea es armar un grafo de la subred, en el que cada nodo representa un enrutador y cada arco del grafo unalínea de comunicación (con frecuencia llamada enlace).
Para elegir una ruta entre un par dado de enrutadores, el algoritmo simplemente encuentra en el grafo la ruta más corta entre ellos.
Una manera de medir la longitud de una ruta es por la cantidad de saltos.

5.2.3 Inundación
Otro algoritmo estático es la inundación, en la que cada paquete de entrada se envía por cada una de las líneas de...