REDESII

ALGORITMOS DE ENCAMINAMIENTO

Los algoritmos de encaminamiento se pueden agrupar no adaptativos y adaptativos. Los algoritmos no adaptativos no basan sus decisiones de encaminamiento en medicioness o estimaciones del tráfico actuales; más bien, la elección de la ruta utilizable para ir de i 1a la j (para toda i y j), se determina anticipadamente, fuera de línea y se carga en los IMP cuando la red se arranca. A este procedimiento se le denomina a veces encaminamiento estático.

Los algoritmos adaptativos, por otra parte, intentan cambiar sus decisiones de encaminamiento para reflejar los cambios de topología y de tráfico actual. Existen tres familias distintas de algoritmos adaptativos, que se diferencian de acuerdo con la información que utilizan. Los algoritmos globales utilizan información recogida que toda la subred, para intentar tomar decisiones óptimas. A este planteamiento se le conoce como encaminamiento centralizado. Los algoritmos locales operan en forma separada sobre cada IMP, y sólo utilizan la información que se encuentra disponible allí, como la longitud de las colas de espera. A éstos se les conoce como algoritmos aislados. Por último, la tercera dase de algoritmos utiliza una combinación de información del tipo global y local; y se les conoce como algoritmos distribuidos. A continuación se estudiarán con mayor detalle estas tres clases de algoritmos. Para tener una mayor información acerca del encaminamiento, consulte Bell y Jabbour (1986).

Encaminamiento por el camino más corto

Comencemos nuestro estudio de los algoritmos de encaminamiento por medio de una técnica que se utiliza ampliamente de maneras diferentes, gracias a su simplicidad y facilidad de comprensión. La idea consiste en construir un gráfo de la subred, con cada nodo representando una IMP y cada arco, una línea de comunicación. Para escoger una ruta entre un par de IMP dadas, el algoritmo sólo determina el camino más corto que existe entre ellos.

El concepto de camino más corto merece una explicación. Una forma de medir la longitud del camino es a través del número de saltos. Empleando esta métrica, los caminos ABC y ABE, en la figura 5-10, tienen la misma longitud. Otra métrica es el camino geográfico expresado en kilómetros, en cuyo caso la trayectoria ABC es claramente mucho más larga que ABE (suponiendo que la figura se ha dibujado a escala).

_

Sin embargo, existe la posibilidad de utilizar muchos otros tipos de métrica. Por ejemplo, cada arco podría etiquetarse con el retardo promedio de la espera en cola y de la transmisión, para un paquete patrón de prueba, determinado en base a pruebas de varias horas o días. Con este etiquetado del grafo el camino más corto resulta ser el más rápido en lugar del que presenta el menor número de arcos o kilómetros el caso más general, las etiquetas de los arcos se podrían calcular como una función de la distancia, ancho de banda, promedio de tráfico, costo de comunicación, longitud promedio de la cola de espera, retardo medido, y algunos otros factores. Al cambiar la función de peso, el algoritmo calcularía el camino "más corto" de acuerdo con cualquiera de los criterios involucrados.

Se conocen varios algoritmos que calculan el camino más corto entre dos nodos de un gráfo. El que aquí se muestra lo desarrolló Dijkstra (1959). Cada uno de los nodos se etiqueta (entre paréntesis) con la distancia que tiene desde el nodo origen la lo largo de un camino conocido como d mejor. Inicialmente, ningún camino es conocido, así que todos los nodos se etiquetan con infinito. A medida que el algoritmo avanza y los caminos se comienzan a conocer, las etiquetas pueden cambiar reflejando mejores trayectorias. Una etiqueta puede ser tentativa o permanente. Al inicio todas son tentativas. Cuando se descubre que una etiqueta representa el camino más corto posible, desde el origen hasta el nodo respectivo, la etiqueta se hace permanente y desde ese momento jamás se modifica.

Para ilustrar la manera como trabaja el algoritmo de etiquetado, véase en la figura 5-10a el grafo ponderado y no dirigido, en donde los pesos representan, por ejemplo, la distancia. Se desea determinar el camino más corto desde A hasta D. El procedimiento se inicia al hacer el nodo A permanente, indicando esto mediante un circulo relleno. Después, se examina de uno en uno, cada nodo adyacente al A (que es el nodo de trabajo), reetiquetando cada uno de ellos con la distancia a A. Cada vez que se reetiqueta un nodo, también se le etiqueta con el nodo desde el cual se hizo la prueba, de tal forma que se puede reconstruir después el camino final. Una vez que se examinó cada uno de los nodos adyacentes a A, se continúan examinando todos los nodos con etiqueta temporal en el grafo completo, y se hace permanente el nodo con la etiqueta más pequeña, como se muestra en la figura 5-10b. Este nodo se convierte en el nuevo nodo de trabajo.

Ahora se comienza con el nodo B, y se examinan todos los nodos adyacentes a éste. Si la suma de la etiqueta en B y la distancia desde B al nodo que se está considerando, es menor que el valor de la etiqueta en ese nodo, tenemos entonces una trayectoria más corta, por lo tanto el nodo se reetiqueta.

Después de que se hayan revisado todos los nodos adyacentes al nodo de trabajo, y que las etiquetas temporales se hayan modificado, si fue posible, el grafo entero se investiga para encontrar el nodo etiquetado temporalmente con el valor más pequeño. Este nodo se hace permanente y se convierte en el nuevo nodo de trabajo para la siguiente ronda. En la figura 5-10 se muestran los primeros cinco pasos del algoritmo.

Para ver por qué funciona el algoritmo, rnirese en la figura 5-I0c. En este momento, E acaba de hacerse permanente. Supóngase que había un camino más corto que el correspondiente a ABE, sea éste AXYZE. Existen dos posibilidades: o que el nodo Z ya se haya convertido en permanente, o bien, que todavía no lo sea. Si se convirtió, entonces E ya se había probado (en la ronda siguiente a aquélla en la que Z se hizo permanente), por lo tanto la trayectoria AXYZE no habría escapado a nuestra atención.

Ahora, considérese el caso en donde Z todavía tiene una etiqueta temporal o bien la etiqueta en Z es mayor que o igual que el valor de E, en cuyo caso el camino AXYZE no puede ser más corto que el ABE, o bien tiene un valor menor que el de E, en cuyo caso Z y no E se hará permanente primero, permitiendo que E se pueda probar desde Z.

En la figura 5-11 se muestra este algoritmo en lenguaje Pascal. La única diferencia que existe entre el programa y el algoritmo que se describió anteriormente, es que, en la figura 5-11 se calcula el camino más corto comenzando en el nodo terminal, t, más que en el nodo de origen, s. Puesto que el camino más corto, desde i hasta v en un grafo no dirigido, es el mismo que la trayectoria más corta que existe desde s a t, no importa en qué extremo se comience (a menos que existan varios caminos igual de cortos, en cuyo caso al invertir la búsqueda se podría descubrir uno diferente). La razón por la cual se va hacia atrás es que cada nodo es etiquetado con su predecesor, más que con su sucesor. Cuando se copia el camino final en la variable de salida, path, se lleva a cabo la inversión del camino. Al invertir la búsqueda, los dos efectos se cancelan y la respuesta se produce en el orden correcto.

Encaminamiento de camino múltiple

Hasta ahora se ha supuesto tácitamente que existe un solo "mejor" camino entre cualquier par de nodos y que todo el tráfico entre ellos deberá utilizarlo. En muchas redes hay varios caminos entre pares de nodos, que son casi igualmente buenos. Con frecuencia, se puede obtener un mejor rendimiento al dividir el tráfico entre varios caminos, para reducir la carga en cada una de las líneas de comunicación. La técnica de utilizar encaminamiento múltiple entre un sólo par de nodos se conoce como encaminamiento de camino múltiple, o algunas veces encaminamiento bifurcado.

El encaminamiento de camino múltiple se aplica tanto en subredes con datagramas, como en subredes con circuitos virtuales. Para el caso de subredes con datagramas, cuando un paquete llega a un IMP para su reexpedición, se hace una selección entre varias alternativas, para ese paquete en particular, en forma independiente de las selecciones que se hicieron para otros paquetes que se dirigieron al mismo destino, en el pasado. Para subredes con circuitos virtuales, cada vez que se establece un circuito virtual, se selecciona una ruta, pero el encaminamiento para los diferentes circuitos virtuales (en beneficio de los diferentes usuarios) se lleva a cabo en forma independiente.

El encaminamiento de camino múltiple se puede realizar de la siguiente manera. 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, la tercera mejor, etc. línea de salida para ese destino en particular, junto con un paso o ponderación relativa. Antes de que se reexpida un paquete, un IMP genera un número aleatorio y después selecciona entre las diferentes alternativas que se presentan, haciendo uso de los pesos como probabilidades. Los operadores calculan las tablas manualmente, cargándolas en los IMP antes de que arranque la red y que no se modifique después.

Como un ejemplo, considérese la subred de la figura 5-12a. En la figura 5-12b se muestra la tabla de encaminamiento del IMP J. Si J recibe un paquete cuyo destino es A, éste utiliza la ristra etiquetada con-A. En este caso se presentan tres opciones.

_

La línea hacia A es la primera elección, y después le siguen las líneas hacia I y H, respectivamente. Para tomar una decisión, J genera un número aleatorio entre 0.00 y 0.99. Si el número es inferior a 0.63, se utilizará la línea A. Si el número se encuentra entre 0.63 y 0.83, se utilizará I; y si no, se utilizará H. Los tres pesos representan, por consiguiente, las respectivas probabilidades para que se utilice A, I o H.

Una de las ventajas del encaminamiento de camino múltiple sobre el encaminamiento por camino más corto, es la posibilidad de poder transmitir diferentes clases de tráfico sobre diferentes caminos. Por ejemplo, una conexión entre un terminal y un ordenador remoto, que consta de paquetes cortos que deben de entregarse rápidamente, podría tomar una ruta a través de líneas terrestres, en tanto que la transferencia de un archivo grande, que necesita un gran ancho de banda, podría transmitirse a través de un enlace vía satélite. No sólo ofrece este método el gran ancho de banda que necesita la transferencia de archivo, sino que también evita que los paquetes cortos de terminal se retarden por estar detrás de una cola larga de paquetes de transferencia de archivos.

Aunque el encaminamiento de trayectoria múltiple se utiliza extensamente con objeto de mejorar el rendimiento, también se puede utilizar para mejorarla fiabilidad de la subred. En particular, si las tablas de encaminamiento contienen n rutas separadas entre cada par de IMP, la subred, entonces, podrá soportar la pérdida de (n - 1) líneas, sin que se rompa en dos partes.

Una manera simple de asegurar que todas las rutas alternativas se separen, consiste en calcular primero el camino más corto entre la fuente y el destino. Después, eliminar del grafo todos los nodos y arcos utilizados en la trayectoria más corta, para finalmente calcular la trayectoria más corta a través del nuevo grato. Con este algoritmo se asegura que los fallos originados en la línea o en el IMP del primer camino, no vayan a hacer que el segundo también falle. Además, al eliminar el segundo camino del gráfo, se puede calcular un tercer camino que viene a ser completamente independiente de los dos primeros. Even (1975) diseñó un algoritmo más sofisticado para localizar caminos separados en un grato.

Encaminamiento centralizado

Todos los algoritmos de encaminamiento que se estudiaron anteriormente necesitan tener información acerca de la topología y el tráfico de la red, para poder ' tomar las mejores decisiones. Si la topología es de característica estática y el tráfico, cambia muy rara vez, la construcción de las tablas de encaminamiento es muy sencilla, y se realiza una sola vez, fuera de línea, cargándolas en los IMP. Sin embargo, si los IMP y las líneas se desactivan y después se reestablecen, o bien, si el tráfico varia violentamente durante todo el día, se necesitará algún mecanismo para adaptar las tablas a las circunstancias que imperan en ese momento. En esta sección se estudiarán las técnicas para la construcción de las tablas de encaminamiento en un lugar central. En las secciones posteriores se verá la manera cómo este trabajo puede realizarse en una forma total o parcialmente descentralizada.

Cuando se utiliza un encaminamiento centralizado, en alguna parte de la red hay un RCC (Centro de control del enrutamiento). Periódicamente, cada IMP transmítela información de su estado al RCC (por ejemplo, una lista de sus vecinos activos, las longitudes actuales de las colas de espera, la cantidad de tráfico procesado por línea desde el último informe, etc.) El RCC recoge toda esta información, y después, con base en el conocimiento total de la red completa, calcula las rutas óptimas de todos los IMP a cada uno de los IMP restantes, utilizando por ejemplo el algoritmo del camino más corto, que se estudió anteriormente. A partir de esta información puede construir nuevas tablas de encaminamiento y distribuirlas a todos los IMP.

El encaminamiento centralizado parece atractivo a primera vista: dado que el RCC tiene la información completa, y puede tomar decisiones perfectas. Otra ventaja es que alivia a los IMP de la carga de calcular el encaminamiento.

Desafortunadamente, el encaminamiento centralizado también tiene algunos serios, si no es que fatales, inconvenientes. Por una razón, si la subred se tiene que adaptar a un tráfico variable, el cálculo del encaminamiento tendrá que efectuarse con bastante frecuencia. Para una red grande, este cálculo tomará muchos segundos, incluso cuando se tenga un CPU razonablemente rápido. Si el propósito de correr el algoritmo consiste en adaptarlo a cambios en la topología de la red; y no tanto a cambios en el tráfico, podría ser adecuado si se llegara a ejecutar cada minuto aproximadamente, dependiendo de cuán estable sea dicha topología.

La vulnerabilidad del RCC resulta ser un problema más serio; si éste se desactiva o llega a aislarse, debido a fallos en las líneas, la subred estará súbitamente en una situación problemática. Una solución consiste en tener una segunda máquina disponible como respaldo, pero esto conlleva a desperdiciar un ordenador de gran tamaño. También, se necesitará establecer un método de arbitraje para tener la seguridad de que el RCC primario y el de respaldo no lleguen a entrar en conflicto para saber quién es el jefe.

Otro problema adicional con el encaminamiento centralizado es el relacionado con la distribución de las tablas de encaminamiento a los IMP. Los IMP que se encuentran próximos al RRC obtendrán primero sus tablas nuevas y conmutarán a las nuevas rutas antes que, los IMP localizados a más distancia, hayan recibido sus correspondientes tablas. En esta circunstancia pueden surgir algunas inconsistencias, de tal forma que los paquetes pueden sufrir retardos. Entre los paquetes retardados habrá algunas nuevas tablas de encaminamiento para IMP distantes, por lo que el problema se realmente a si mismo.

Si el RCC calcula la ruta óptima para cada par de IMP, sin rutas alternas, la pérdida de tan sólo una línea o IMP, llegará a desconectar algunos IMP del RCC, creando así terribles consecuencias para el sistema. Si el RCC utiliza rutas alternas, se debilitará el argumento en favor de tener un RCC, esto es el que pueda encontrar rutas óptimas.

Un último problema relacionado con el encaminamiento centralizado es la fuerte concentración de tráfico encaminado sobre las líneas que conducen al RCC. En la figura 5-13 se ilustra este problema. La figura se dibujó trazando el camino más corto desde cada máquina hasta el RCC, y colocando una flecha en cada línea. Una línea con n flechas significa que hay n IMP que se están notificando al RCC a través de ella. El efecto de una carga fuerte y la vulnerabilidad resultante de las líneas próximas al RCC es evidente.

_

Considérese la red comercial de conmutación de paquetes TYMNET, con más de 1000 nodos que ha estado trabajando desde 1971, como un ejemplo ilustrativo de la forma cómo el encaminamiento centralizado trabaja en la práctica. TYMNET se utiliza principalmente con objeto de permitir que los terminales se conecten a los ordenadores remotos, la subred ofrece un servicio orientado a conexión y utiliza circuitos virtuales para realizar este tipo de servicio. Los IMP de la red TYMNET envían periódicamente información al RCC sobre su estado: por ejemplo indicando las líneas que están activas o inactivas, las longitudes de las colas de espera, así como otros datos estadísticos. El RCC mantiene tablas en las que se lleva d seguimiento de toda esta información que llega.

Cuando un nuevo usuario se conecta y especifica el hostal al cual desea conectarse, se envía un paquete al RCC informándole acerca del registro. El RCC entonces calcula la mejor ruta, utilizando toda la información que tiene a su disposición. Luego, envía un paquete de itinerario de regreso al IMP, al cual está conectado el usuario. El paquete de itinerario contiene la ruta seleccionada por el RCC. Este paquete traza su camino a través de la subred, efectuando anotaciones de entrada en las tablas de los IMP que se encuentran a su paso, estableciendo de esta forma de circuito virtual. Cuando el usuario se retira, se sigue un proceso similar para liberar el circuito virtual.

Encaminamiento aislado

Todos los problemas que se suscitan con los algoritmos de encaminamiento centralizado sugieren que los algoritmos descentralizados podrían tener algo que ofrecer. En los algoritmos de encaminamiento descentralizado más sencillos, los IMP llevan a cabo decisiones de encaminamiento, únicamente basados en la información que ellos mismos hayan reunido. No intercambian información de rutas con otros IMP. Sin embargo, tratan de adaptarse a los cambios de topología y tráfico que se llegan a presentar. A éstos se les conoce comúnmente como algoritmos de encaminamiento adaptables aislados.

Un algoritmo adaptable aislado sencillo es el desarrollado por Baran (1964), conocido como el algoritmo de la pata caliente. En el momento en que le llega un paquete, el IMP trata de deshacerse de él tan rápido como le sea posible, al ponerlo en la cola de espera de salida más corta. En otras palabras, cuando llega un paquete, el IMP cuenta el número de paquetes que se encuentran en la cola de espera de cada una de las líneas de salida. Entonces instala el nuevo paquete al final de la cola de salida más corta, sin tomar en cuenta el lugar al que se dirije esta línea. El interior del IMP J de la f1gtlra 5-12, tomado en un instante de tiempo cualquiera, se muestra en la figura 5-14. Hay cuatro colas de salida correspondientes a las cuatro líneas de salida. Los paquetes se acomodan en cola en cada una de las líneas, aguardando hasta que llegue el momento de su transmisión. En este ejemplo, la cola de espera I es la más corta, con un solo paquete esperando en la cola. El algoritmo de la patata caliente, por consiguiente, colocaría el paquete recién llegado en esta cola de espera.

_

Una variante de esta idea consiste en combinar el encaminamiento estático con el algoritmo de la patata caliente. Cuando llega un paquete, el algoritmo de encaminamiento toma en consideración tanto el peso estático de las líneas como las longitudes de las colas de espera. Una posibilidad consiste en utilizar la mejor opción estática, a menos que la cola excediera un cierto valor de umbral. Otra posibilidad consiste en utilizar la cola de espera más corta, a menos que, su peso estático sea demasiado pequeño. Una alternativa adicional consistiría en ordenar las líneas en términos de sus pesos estáticos, y nuevamente, en términos de las longitudes de las colas de espera, tomando en consideración la línea para la cual resulte menor la suma de los dos ordenamientos. Cualquiera que sea el algoritmo que se elija, éste deberá tener la propiedad que, bajo una condición de baja carga, la línea con un peso estático más alto será la que normalmente se elija pero, a medida que empiece a crecer la cola de espera para esta línea, alguna parte del tráfico se derivará hacia líneas menos ocupadas.

Otro algoritmo de encaminamiento aislado, también desarrollado por Baran, es el conocido como de aprendizaje hacia atrás. En los años de 1950 y 1960, cuando a los reporteros de países Occidentales difícilmente se les permitía visitar China, era común ver noticias que se iniciaban con "De acuerdo con los viajeros que acababan de llegar de Hong Kong procedentes de China...". La idea era que, en lugar de que el reportero fuera al lugar X, él pudiera hablar con la gente que acababa de llegar de X, preguntándoles qué era lo que estaba sucediendo ahí? El algoritmo de aprendizaje hacia atrás se comporta de la misma manera.

Una manera de realizar el aprendizaje hacia atrás consiste en incluir la identidad del IMP origen en cada paquete, junto con un contador que se incrementa después de cada salto. Si un IMP ve llegar un paquete en la línea k, procedente del IMP H, con la cuenta de 4 saltos, sabe que H no puede estar más lejos de cuatro saltos sobre la línea k. Si su mejor ruta actual hacia H se estima en más de cuatro saltos, marca la línea k como la elegida para el tráfico hacia H y registra la distancia estimada con un valor de cuatro saltos. Después de un rato, cada IMP descubrirá el camino más corto hacia cualquier otro IMP.

Desgraciadamente, hay una mosca en la sopa. Dado que los IMP sólo registran cambios hacia lo que sea mejor, si una línea se desactiva o llega a sobrecargarse, no hay mecanismo alguno que permita registrar este hecho. En consecuencia, los IMP deberán olvidar en forma periódica cualquier cosa que hayan aprendido y comenzar todo de nuevo. Durante el nuevo periodo de aprendizaje, el encaminamiento estará muy lejos de ser el óptimo. Si las tablas se depuran con frecuencia, los IMP encaminarán un número substancial de paquetes, utilizando rutas de calidad desconocida; en tanto que si las tablas se depuran rara vez, el proceso de adaptación resultará muy lento.

Rudin (1976) ha descrito un encaminamiento híbrido interesante, el cual se encuentra entre un encaminamiento centralizado y uno aislado, el cual denominó encaminamiento delta. En este algoritmo, cada una de los IMP mide el "costo" de cada línea (es decir, alguna función del retardo, de la longitud de la cola de espera, de su utilización, de su ancho de banda, etc.) y periódicamente transmite un paquete al RCC entregándole estos valores.

Utilizando la información enviada por los IMP, el RCC calcula las k mejores trayectorias que van desde el IMP i hasta el IMP j, para todo i y todo j, en donde sólo sé consideran los caminos que difieren en su línea inicial. Sea C1ij el costo total del mejor camino 1-j, y C2ij el costo total del siguiente mejor camino, etc. Si Cnij –C1ij < �÷ la trayectoria n se declara equivalente a la trayectoria 1, dado que sus costos difieren por una cantidad rnínima, para cada uno de sus posibles destinos. (En realidad, sólo se necesitarán las líneas iniciales, y no todas las trayectorias).

Para realizar encaminamiento real, a los IMP se les permite seleccionar cualquiera de las trayectorias equivalentes. Puede decidir entre todas ellas en forma aleatoria, o bien, utilizar el valor actualmente medido del costo de la línea, es decir, escoger el camino de aquéllos que se encuentran en el conjunto permitido, cuya línea inicial actual sea la más económica. Al ajustar los valores de k y d , los operadores de la red pueden realizar transferencias de autoridad entre el RCC y los IMP.

A medida que d ® 0, todas las trayectorias restantes se considerarán inferiores a 14 mejor trayectoria, y el RCC tomará todas las decisiones. Sin embargo, cuando d ® ¥ , todas las demás trayectorias se considerarán equivalentes, y las decisiones sobre el encaminamiento se tomarán en los IMP, basándose solamente en la información local. Las simulaciones que realizó Rudin, han demostrado que el valor de ó puede escogerse para dar un mejor rendimiento que cl obtenido con un encaminamiento puramente centralizado o aislado.

Inundación

La inundación es un caso extremo del encaminamiento aislado, en el cual cada paquete que llega se transmite en todas las líneas de salida, exceptuando aquélla por el que llega. Obviamente, con la inundación se genera un número considerable de paquetes duplicados; de hecho, un número infinito, a menos que se tomen algunas medidas para amortiguar el proceso. Una de tales medidas consiste en tener un contador de saltos contenido en la cabecera de cada uno de los paquetes, el cual se decrementa con cada salto que se lleve a cabo, y el paquete se desecha en el momento en que el contador alcance el valor de cero. Idealmente, cl contador de saltos deberá iniciarse con un valor correspondiente a la longitud del camino que existe entre el origen y el destino. 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.

Una técnica alternativa para retener la inundación consiste en hacer que el IMP de origen ponga un número de secuencia en cada paquete que recibe de su hostal. De esta forma, cada IMP necesitará una lista por IMP origen, indicando qué números de secuencia originados en la fuente ya fueron vistos. Para evitar que la lista crezca sin limite, cada lista deberá aumentarse por medio de un contador, k, indicando que todos los números de secuencia hasta k ya fueron vistos. En el momento en que un paquete llega, resulta muy fácil verificar si éste es un duplicado; si es el caso, se desechará.

En varias aplicaciones, la inundación no resulta ser muy práctica, pero sí tiene algunos usos importantes. Por ejemplo, en aplicaciones militares, en donde un gran número de IMP pueden desintegrarse en pedazos en cualquier instante, la robustez de la inundación es una característica altamente deseable. En aplicaciones de bases de datos distribuidas, algunas veces se necesita actualizar todas las bases de datos en forma concurrente, en cuyo caso la inundación puede ser de gran utilidad. Una tercera forma posible de utilización de la inundación es como un sistema de medición contra cl cual otros algoritmos de encaminamiento se pueden comparar. La inundación siempre escoje el camino más corto, porque selecciona todos los posibles caminos en paralelo, por consiguiente, ningún otro algoritmo puede producir un retardo más corto (si se llegara a ignorar la sobrecarga generada por el proceso mismo de inundación).

Una variante de la inundación que es un poco más práctica, es la conocida como inundación selectiva. En este algoritmo los IMP no transmiten cada paquete que llega por todas las líneas de salida, sino por aquellas líneas que van aproximadamente en la dirección correcta. En general, es ilógico enviar un paquete hacia el oeste, a través de líneas que van al este, a menos que la topología sea muy extraña.

Otros algoritmos no adaptable es el de camino aleatorio; aquí el IMP se encarga simplemente de seleccionar una línea aleatoriamente y reexpedir el paquete a través de ella. Aquí, también, el IMP puede hacer algún intento de enfilar el paquete hacia la dirección correcta. Si la subred tiene una cantidad considerable de interconexiones, este algoritmo tiene la propiedad de hacer un uso excelente de los encaminamientos alternativos. También es muy robusto.

Encaminamiento distribuido

En esta clase de algoritmos de encaminamiento, que en sus inicios se utilizaron en ARPANET, cada IMP intercambia periódicamente información de encaminamiento explícito con cada uno de sus vecinos. Por lo general, cada IMP mantiene una tabla de encaminamiento con una entrada por cada uno de los demás IMP de la subred. Esta entrada consta de dos partes: la línea preferida de salida que se utilice para dicho destino, y alguna estimación del tiempo o distancia hacia él. La métrica utilizada podría ser el número de saltos, el tiempo estimado de retardo en milisegundos, la estimación del número total de paquetes encolados a lo largo de la ruta, el exceso de ancho de banda, o bien, algo similar.

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 sólo 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 el 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.

Como un ejemplo, supóngase que se utiliza el retardo como una métrica y que el IMP conoce el retardo para llegar a cada uno de sus vecinos. Cada IMP le envía a cada uno de sus vecinos una lista de sus retardos estimados para cada destino, una vez cada T mseg. También recibe una lista parecida de cada uno de sus vecinos. Imagínese ahora que una de estas tablas acaba de llegar, procedente de su vecino X, con Xi siendo la estimación hecha por X del tiempo que le lleva llegar al IMP i. Si el IMP sabe que el retardo para X es de m mseg, también sabe que puede alcanzar al IMP la través de X, en un tiempo de (Xi + m) mseg a través de X. Al efectuar este cálculo para cada vecino, un IMP podría determinar qué estimación parece serla mejor, y utilizarla junto con su correspondiente línea en su nueva tabla de encaminamiento. Nótese que la antigua tabla de encaminamiento no se utiliza en el proceso de cálculo.

Este proceso de actualización se ilustra en la figura 5-15. En la parte a) se muestra una subred. En las primeras cuatro columnas de la parte b) se muestran los vectores de retardo que se recibieron, procedentes de los vecinos del IMP J. A dice tener 12 mseg de retardo para llegar a B, 25 mseg de retardo para C, 40 mseg de re- tardo para D, etc. Supóngase que J ha medido o estimado su retardo para llegar hasta sus vecinos A, I, H y K en 8, lo, 12 y 6 mseg, respectivamente.

_

Considérese ahora la forma como J calcula su nueva ruta para llegar al IMP G. Sabe que puede llegar a A en 8 mseg, y A afirma que es capaz de llegar a G en 18 mseg, así que J sabe que puede contar con un retardo de 26 mseg hacia G, si reexpide los paquetes de G a A. De una manera similar, calcula el retardo para llegar a G a través de I, H y K como 41(31 + lo), 18(6 + 12) y 37(31 + 6) mseg, respectivamente. El mejor de estos valores es 18, así que hace una anotación en su tabla de encaminamiento indicando que el retardo a G es de 18 mseg, y que la ruta a usar es a través de H. Este mismo cálculo se lleva a cabo para todos los demás destinos, obteniendo la nueva tabla de encaminamiento mostrada en la última columna de la figura.

  Encaminamiento óptimo

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 óptimas; una de estas declaraciones se conoce con el nombre de principio de optimización. Este declara que si el IMP J está en la trayectoria óptima que va desde el 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. Para ver esto, llámese r1 a la porción de la ruta que va desde I hasta J, y al resto de la ruta r2. Si existiera una ruta mejor que r2, desde J hasta K, podría concatenarse con r1 para mejorar la ruta de la K, contradiciendo, por consiguiente, la afirmación de que la ruta r1 r2 es la óptima.

Como una consecuencia directa del principio de optimización, se puede observar que, d conjunto de rutas óptimas, procedentes de todos los orígenes a un destino dado, forman un árbol cuya raíz sale del destino. A este árbol se le llama árbol sumidero y se ilustra en la figura 5-16. Dado que el árbol sumidero es efectivamente un árbol, no contiene ningún lazo, de tal forma que, cada paquete será entregado a través de un número limitado y finito de saltos.

_

En general, si el tráfico de la IMP X pasa por la IMP Y, a medida que fluye a través del árbol sumidero, para llegar a su destino, se dice que X se encuentra corriente arriba de Y y Y no abajo de X. Con objeto de ilustrar estos conceptos, considérese la subred de la figura 5-17a, con el árbol sumidero para el destino H, como se muestra en la figura 5-17b. IA lo largo de este ejemplo, se utilizará el encaminamiento de camino más corto, según un orden alfabético; por ejemplo, B encaminado hacia H, a través de BCEH, en lugar de BDGH, porque BCEH < BDGH).

Con la imagen del árbol sumidero en mente, considérese lo que sucedería si una línea llegara a desactivarse, bloqueando así la trayectoria hacia un destino determinado. Un IMP sencillamente no puede enviar su tráfico a otra IMP, que se encuentra corriente arriba de la ruta con respecto a dicho destino.. Este deberá buscar un vecino que esté unido a otra rama (independiente) del árbol sumidero. En cl algoritmo de Chu (1978), cada IMP mantiene una tabla de encaminamiento con una ristra por destino, como se puede apreciar en la figura 5-17c. Cada columna da el número de saltos necesarios para llegar al destino, a través de una línea de salida especifica.

Para la IMP G, las líneas de salida son D, F y H. La mejor ruta está indicada por medio de un circulo. Las entradas que se refieren a los IMP que se encuentran corriente arriba se dejan en blanco. Nótese que el árbol sumidero utilizado para determinar quién está corriente arriba y quién está río abajo, es diferente para cada ristra de la tabla.

Ahora, veamos qué sucede cuando falla la línea GH. El IMP G comienza marcando todas las anotaciones de la columna H como inutilizables. Después, comprueba cada una de las ristras en las cuales se ha borrado la mejor ruta, para ver si se encuentra disponible una ruta alternativa. Para el destino E, por ejemplo, se puede seguir una ruta alternativa a través de D. (Recuérdese que en este ejemplo D encamina a E, a través de B, porque DBCE < DGHE).

_

Para cl destino H, la situación es peor, porque los dos vecinos se encuentran corriente arriba de G. Por consiguiente, G envía a cada vecino un paquete de control indicando "No podré jamás llegar hasta H, por favor ayúdenme". Después de recibir el paquete con esta información, cada vecino comprueba si tiene una ruta alterna (previamente suboptimizada). D tiene una ruta alternativa y, por lo tanto, devuelve una respuesta anunciándola. Sin embargo, F no tiene ninguna alternativa, porque A, que es su único vecino, se encuentra corriente arriba de su posición, por lo que actúa de la misma manera que lo haría si la línea FG se hubiera desactivado, es decir, solicitando ayuda de A. Los paquetes de control continúan propagándose corriente arriba hasta que alguien encuentra una ruta alternativa. Cuando G finalmente recibe las respuestas de todos sus vecinos localizados corriente arriba puede hacer nuevas anotaciones en su tabla de encaminamiento y seleccionar la mejor. La única condición bajo la cual el algoritmo falla es cuando ninguno de los IMP, corriente arriba del enlace que fracasó, puede hacer contacto con cualquier otro IMP en otra rama del árbol sumidero. Esta condición ocurre sólo cuando la subred se llega a romper en dos componentes independientes.