Algoritmos dinámicos de ruteo

En el tipo de los algoritmos dinámicos tenemos:

• Protocolo de Información de Enrutamiento: (RIP) o algoritmo de vector de distancia, puede tomar en cuenta el número de saltos, el retraso calculado o algún otro factor. Cisco y otros fabricantes usan una versión mejorada de este algoritmo. Se usa pricipalmente para intercambiar rutas entre enrutadores y nodos activos (computadoras) de la red. Cada enrutador envía (a su vecino) una tabla que contiene destinos y «precio» de alcanzar cada uno de esos destinos. Así, un enrutador particular puede saber su precio para alcanzar un destino específico sumándole al precio recibido su propio precio por alcanzar el enrutador vecino.
• IGRP (Interior Gateway Routing Protocol): Se utiliza para intercambiar rutas entre enrutadores dentro de un mismo conjunto lógico.
• BGP (Border Gateway Protocol): Se utiliza para intercambiar rutas entre enrutadores que están en el límite de un conjunto lógico.
• Enrutamiento por el status de enlace: El ruteo RIP básico se uso en WANs hasta 1979 porque no consideraba el ancho de banda de los enlaces y fue sustituido por el de estatus del enlace y variaciones. La idea principal de este nuevo algoritmo consiste de 5 pasos:

1. Descubrir los vecinos y registrar sus direcciones de red.

2. Medir el precio para llegar a cada enrutador vecino.

3. Construir un mensaje que contenga todo lo aprendido.

4. Enviar el paquete de conocimiento a los enrutadores vecinos.

5. Calcular la ruta más corta hacia cada enrutador alcanzable.

• Enrutamiento Jerárquico: Si una red cuenta con una gran cantidad de enrutadores, será muy ineficiente y tal vez imposible que cada enrutador tenga una tabla con todas las rutas y que registre toda la topología, además de que esto consumiría mucha memoria, también consumiría el ancho de banda de la red en enviar y recibir tablas. Por eso se ideó el enrutamiento jerárquico, en el cual se agrupan varios enrutadores y sólo uno del grupo intercambia rutas con el representante de otros grupos. Por ejemplo, si una red tiene 64 enrutadores, en lugar de que cada enrutador tenga una lista de 64 entradas, podemos agruparlos de 8 en 8 y entonces cada enrutador tendrá una tabla con 8 entradas en esta jerarquía de dos niveles. Para redes más grandes se pueden hacer jerarquías de mayor profundidad. La desventaja de este esquema es que se pueden pasar por alto rutas más eficientes porque se está restringido las rutas recibidas por el representante.
• Enrutamiento para nodos móviles: Supongamos un representante de ventas que se lleva su computadora portátil en un viaje por tren, y que el tren ofrece el servicio de conectarse a la red a través de un protocolo de ruteo móvil. El tren irá cambiando de posición entrando y saliendo de ciudades y estados. El enrutamiento ya no es tan fácil porque la dirección de la computadora portable permanece fija pero la ciudad o estado tiene direcciones diferentes. En este caso la solución es que el mundo se divide en zonas de cierta área y en cada zona existe un «agente». Cuando el tren entra a la primera región, se registra la dirección de la computadora portátil con ese agente indicando su dirección original, la dirección de su agente original AO y cierta información de seguridad. El agente de registro AR se comunica con el agente original AO diciéndole que hay un miembro de su región de visita. El AO verifica con la información de seguridad la identidad de la computadora portátil CP y lo acepta enviando un mensaje de reconocimiento a AR. El AR entonces acepta a CP y todos los datos que CP quiera enviar son recibidos por AR y los envía dentro de un paquete encapsulado a AO, el cual los recibe y desencapsula, enviando los datos reales a su destino como si hubieran sido originados en la región de AO. Al mecanismo de encapsular los paquetes y que éstos sean liberados en un punto remoto se le llama «tunneling».
• Enrutamiento de mensajes broadcast: Existen aplicaciones que necesitan enviar datos a todos los nodos de una red, lo cual constituye un mensaje broadcast. El primer problema que se presenta es determinar hasta qué grado debe viajar el mensaje broadcast. En segundo lugar está cómo la va a hacer el enrutador para tomar un mensaje broadcast y expandirlo a sus vecinos:

1. Se puede expandir el mensaje por el árbol mínimo de expansión (obtención difícil)
2. Se puede expandir por inundación (requiere mecanismo de paro)
3. El mensaje original puede contener una lista de destinos múltiples (preferible)
4. El mensaje se puede expandir por un árbol de sendero inverso (preferible)

• Enrutamiento de mensajes multicast: Existen aplicaciones que necesitan enviar paquetes a un grupo de nodos que tienen en común cierta característica, por ejemplo, participar en una videoconferencia. En ese caso, el enrutamiento se puede llevar a cabo con árbol de expansión podado cuando se usa enrutamiento de estado de enlace y un árbol de sendero inverso cuando se usa enrutamiento RIP. Para evitar la inclusión de algoritmos muy complejos en Internet, se determinan grupos de trabajo que usan un número de red específico. Por ejemplo, para un servicio de videoconferencia se usa la dirección 224.0.0.0, cuando un nodo quiere participar, debe copnocer la dirección IP (por ejemplo, 140.148.4.100) y ahi se conecta el nodo, colectando los paquetes que vayan dirigidos a la dirección 224.0.0.0 por parte del emisor 140.148.4.100.

• Problema de conteo al infinito: Periódicamente, los enrutadores reciben las tablas de enrutamiento de sus vecinos y actualizan las propias. Por ejemplo, si para alcanzar el destino D se requiere pasar por los enrutadores A y B, el enrutador local sabe que para alcanzar A el precio es 3, y para alcanzar B otros 2 puntos, y de B al destino D otros 5 puntos, de manera que el precio total es (3+2+5) = 10. Si cada Q unidades de tiempo B le envía sus tablas a A, y luego de otras Q unidades A se las envía al enrutador local, podemos decir que en general si un enrutador está a N saltos las tablas locales se actalizan en NQ unidades de tiempo. Inicialmente, si deseamos alzanzar un destino para el que no hay una ruta, se marca el precio con un valor de «infinito» y se envía un error de destino inalcanzable. Por otro lado, si existía una ruta pero el destino está apagado, entonces el enrutador más cercano debería actualizar su tabla marcando ese destino con precio de «infinito», pero sucede que su vecino, que no sabe que el destino es físicamente inalcanzable, le envía una tabla diciendo que puede alcanzar ese destino con un precio que llamaremos «S». Así, en NQ unidades de tiempo todos los enrutadores calcularán que para alcanzar el destino fallido (DF) en (S+ precio local) puntos. Sin embargo, el enrutador vecino a DF no lo puede alcanzar y otra vez recibe la tabla del vecino con un precio de S’ > S. Inmediatamente cree que puede alcanzar DF por esa ruta y actualiza su propia tabla con un precio S’+ precio local y otra vez en NQ unidades de tiempo todos los enrutadores reciben esas tablas. Todo el proceso anterior se repite por muchos NQ unidades de tiempo hasta que alcanzan un precio que se iguala con el valor de «infinito», lo cual es demasiado lento y provoca que los enrutadores traten de crear enlaces hacia DF desperdiciando el tiempo.
• El truco del horizonte dividido: Se ha intentado evitar el problema del conteo al infinito y hasta el momento no se ha encontrado una solución 100% efectiva, sin embargo, analicemos uno de tales algoritmos llamado «horizonte dividido». La solución consiste en evitar que un nodo más distante a DF le regrese una ruta a un nodo más cercano a DF. Para lograr eso, un enrutador envía como precio infinito la ruta hacia el enrutador por el cual recibe paquetes de un destino específico. Así, cuando se origina un DF, el enrutador adyacente A marca su precio como infinito. Luego, en Q unidades su vecino B le envía sus tablas pero como los paquetes de DF eran recibidos a través de A, esa ruta estará marcada como precio infinito y cuando A le pase las tablas a B, B las actualizará apropiadamente con precio infinito y a lo más en NQ unidades de tiempo la nueva ruta con precio infinito será conocida en toda la subred. La falla de este algoritmo sucede en topologías específicas. Por ejemplo, si del enrutador A se derivan dos enrutadores vecinos B y C, es claro que B y C no le pasan la ruta hacia DF al enrutador A, pero entre B y C si hay intercambio de la ruta hacia DF. Así, cuando DF se presenta, A tendrá su precio como infinito y se lo pasa a B y C. Pero si hay una diferencia de tiempo en la actualización de B y C, puede suceder que C actualiza más rápido y B todavía tiene una ruta hacia DF con precio X, por lo tanto es factible que C actualice sus tablas con esa ruta vieja con precio X’ = X + precio local. A su vez, B recibe el precio infinito de A, pero recibe «de rebote» la ruta vieja de C con precio X’ y actualiza su ruta hacia DF con precio X» = X’ + precio local. Y así pueden estarse pasando esas rutas y el problema del conteo al infinito existe otra vez.