Método de encaminamiento adaptativo en redes jerárquicas.

Método de encaminamiento de paquetes en una red directa jerárquica formada por una pluralidad de encaminadores,

cada uno con puertos de tipo local y puertos de tipo global; cada puerto comprende una pluralidad de canales virtuales; dichos encaminadores forman grupos, donde los diferentes encaminadores de un mismo grupo están interconectados mediante una topología conexa empleando enlaces de tipo local uniendo parejas de puertos de tipo local, y los diferentes grupos están interconectados mediante una topología conexa empleando enlaces de tipo global uniendo parejas de puertos de tipo global. El método está configurado para emplear saltos por dichos enlaces de acuerdo a rutas mínimas y no mínimas; los saltos que implican rutas no mínimas pueden realizarse tanto a través de enlaces globales como locales. El número de canales virtuales necesarios en cada puerto local y global viene determinado solamente por la longitud de una ruta máxima permitida que no emplea misrouting de tipo local, empleando para ello un orden total en el recorrido de los canales virtuales, que se viola cuando se realiza un misrouting local.

MÉTODO DE ENCAMINAMIENTO ADAPTATIVO EN REDES

CAMPO DE LA INVENCIÓN

La presente invención pertenece al campo de las redes para comunicaciones; más concretamente, es especialmente aplicable al campo de las redes de interconexión para computadores paralelos (multiprocesadores o multicomputadores) .

ANTECEDENTES DE LA INVENCIÓN

En una red de comunicaciones basada en conmutación de paquetes, una serie de clientes (o nodos de cómputo) se comunican entre sí intercambiándose mensajes; cada uno de estos mensajes se divide en uno o más paquetes, que constituyen la unidad básica de conmutación en la red. Cada paquete tiene un cliente origen y uno o múltiples clientes destino (esto último, en el caso de paquetes multicast) . A grandes rasgos, la red está compuesta por una serie de encaminadores (también conocidos como conmutadores, o rauters o switches según los términos en inglés) que son los elementos activos de la red. Estos encaminadores están unidos mediante enlaces de comunicaciones, es decir, cables por los que se envían señales eléctricas u ópticas que transportan los paquetes de la red. Cada cliente se conecta mediante su interfaz de red a uno o más encaminadores utilizando el o los enlaces correspondientes, y a su vez los encaminadores se conectan entre sí mediante otros enlaces. Un encaminador dispone de múltiples puertos, a los que se conectan los enlaces correspondientes a otros encaminadores o clientes. Los clientes envían paquetes a los encaminadores, que se encargan de transportarlos de un encaminador a otro hasta llegar al cliente destino. La topología de la red es una descripción matemática de la forma en la que se conectan los diferentes encaminadores y clientes de la red.

Para que la comunicación sea posible, un encaminador debe ser capaz de recibir cada paquete que llegue por un cierto puerto de entrada, almacenarlo temporalmente, procesarlo para determinar la ruta a seguir, y reenviarlo por el puerto de salida correspondiente. Para todo ello, los encaminadores 10 suelen tener una estructura interna similar al esquema presentado en la figura 1. Cada puerto de entrada Pin tiene asociada una unidad de entrada 11 con una o más memorias (también denominadas bufferes o colas) 12 en las que se almacenan datos correspondientes a los paquetes que se reciben por ese puerto pino Estos múltiples bufferes 12 se suelen utilizar para separar diferentes paquetes según su prioridad, tipo, o según una política de evitación de bloqueos (como se explica más adelante) . Los paquetes almacenados en los bufferes 12 comparten el mismo enlace físico y puerto de entrada al switch; por ello, cuando hay varios de estos bufferes 12 se suelen denominar canales virtuales o "clases de buffer". Existe una lógica de encaminamiento que se encarga de determinar por qué puerto de salida Pout es apropiado reenviar cada paquete de los canales virtuales de entrada 12, y si acaso, en cuál de los canales virtuales del puerto de entrada del siguiente encaminador hay que introducir el paquete. A su vez, cada puerto de salida pout puede tener o no una cierta memoria para almacenar los paquetes que tienen que salir por dicho puerto. La conexión entre los bufferes 12 de los puertos de entrada Pin y los puertos de salida Pout se realiza típicamente mediante un crossbar 13 ( en ocasiones traducido como matriz de cruces) que puede unir en cada ciclo de conmutación cualesquiera parejas de buffer de entradas y puerto de salida, una a una. Cada pareja de puertos de entrada y salida se conecta con un único enlace bidireccional. Un asignador ("allocator") regula el uso de recursos compartidos. Múltiples paquetes pueden solicitar un mismo puerto de salida, pero sólo se concede a uno de ellos cada vez. Un asignador ("allocator") puede ser de tipo dividido (es decir, separable) o no dividido (es decir, unificado) . En caso de que el arbitraje sobre los recursos compartidos esté implementado mediante un asignador no separable, de acuerdo con William Dally y Brian T owles en PrincipIes and Practices ofInterconnection Networks. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003, el asignador (allocator) asigna los puertos de salida pout en función de todas las rutas posibles que pueda seguir cada paquete en un puerto de entrada pino Para ello, se calcula para cada paquete el conjunto de rutas (puertos de salida Pout y canal virtual) por el que puede salir, y se pasan al asignador todos aquellas en las que hay hueco suficiente para el paquete. Después, el asignador busca la asignación de salidas a cada paquete que maximice el throughput del router. En caso de que el arbitraje esté implementado mediante un asignador dividido, de acuerdo con William Dally y Brian Towles en PrincipIes and Practices ofInterconnection Networks. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003, cada puerto de entrada pin elige uno de los canales virtuales que tengan un paquete listo para avanzar (por ejemplo, mediante una política round-robin) , y el paquete decide, de entre todas las rutas posibles proporcionadas por la lógica de encaminamiento, la que más le interese. Después, se pasa la ruta seleccionada al asignador, que realiza la asignación de los puertos de salida pout a los solicitantes. Para poder enviar datos de un paquete a través de un puerto de salida sin pérdida de datos, es necesario que exista espacio de almacenamiento suficiente en el buffer, cola o canal virtual 12 del puerto de entrada pin correspondiente del siguiente conmutador o encaminador. Existen dos mecanismos típicos de control de flujo para gestionar dicho espacio en el buffer de entrada del siguiente encaminador: virtual cut-through (Ve]) (en ocasiones denominado paso a través en castellano) permite el avance de un paquete solo si existe espacio disponible para almacenarlo completo; wormhole (WH) (encaminamiento de agujero de gusano, aunque el nombre en castellano no se suele emplear) divide los paquetes enjlits (flow control digit, en español unidad de control de flujo) , y permite que avancen tantos jlits como hueco haya en el siguiente buffer. Así, WH permite que un paquete se quede parado en la red ocupando dos o más canales virtuales o bufferes de entrada de diferentes encaminadores consecutivos. De hecho, VCT requiere que los bufferes o canales virtuales tengan una capacidad igualo superior al tamaño máximo de un paquete mientras que WH solo precisa que tengan capacidad para uno o más flits. De esta manera, WH se suele emplear en entornos en los que el área del chip o el consumo energético (generado por dichos bufferes) resulta crítico, como redes dentro del chip. Sin embargo, en redes de sistema , es habitual el uso de VCT al ser más sencilla su implementación. En cualquiera de los dos casos, si no existe espacio suficiente en el siguiente buffer o canal virtual, típicamente es necesario esperar a que los datos del dicho buffer avancen hacia su destino, y se libere espacio. En este caso, se dice que existe una dependencia entre un conmutador y el siguiente.

En una red, el interbloqueo (habitualmente denominado deadlock según el término inglés, o simplemente bloqueo) es la situación en la que ningún paquete de un conjunto de paquetes dado no puede avanzar hacia su destino porque se produce una dependencia cíclica entre los recursos solicitados para implementar dicho avance. Por ejemplo, cada paquete está ocupando un hueco en una cola de un encaminador, y para poder avanzar necesita que se libere un hueco en la cola correspondiente del siguiente encaminador, que a su vez está esperando a que se libere un hueco en un tercer encaminador, etc., formándose al final un ciclo de colas llenas en el que ninguno de los paquetes puede avanzar y nunca se libera un hueco. Esta situación es crítica para una red, ya que provoca una parada completa de su funcionamiento de la que no se puede salir. Para evitar este problema del interbloqueo (deadlock) , se han desarrollado diferentes técnicas, que o bien detectan y solventan esta situación (por ejemplo, descartando alguno de los paquetes que conforman la dependencia cíclica y liberando su "hueco" en el buffer) o bien no permiten que se llegue a ella (por ejemplo, mediante restricciones en el encaminamiento de los paquetes en la red que no permiten que se generen dependencias cíclicas) . Las primeras técnicas se denominan de resolución de bloqueos, y son más frecuentes en las redes con pérdidas, que son aquellas que se asumen poco fiables y que no garantizan la entrega de los datos en el destino (como Ethernet) . En cambio, las técnicas del segundo tipo se denominan de evitación de bloqueos, y son preferibles en redes sin pérdidas ya que no precisan de la retransmisión de los datos. Los mecanismos de evitación de bloqueos están en muchos casos íntimamente relacionados con la topología...

1. Un método de encaminamiento de paquetes en una red directa jerárquica formada por una pluralidad de encaminadores, cada uno de ellos con una pluralidad de puertos de tipo local y una pluralidad de puertos de tipo global, donde cada uno de dichos puertos comprende una pluralidad de canales virtuales, donde dichos encaminadores forman grupos, donde los diferentes encaminadores de un mismo grupo están interconectados mediante una topología conexa empleando enlaces de tipo local uniendo parejas de puertos de tipo local, y a su vez los diferentes grupos están interconectados mediante una topología conexa empleando enlaces de tipo global uniendo parejas de puertos de tipo global, estando el método configurado para emplear saltos por dichos enlaces de acuerdo a rutas mínimas y no mínimas, donde los saltos que implican rutas no mínimas pueden realizarse tanto a través de enlaces globales como locales,

estando el método caracterizado por que el número de canales virtuales necesarios en cada puerto local y global viene determinado solamente por la longitud de una ruta máxima permitida que no emplea misrouting de tipo local, empleando para ello un orden total en el recorrido de los canales virtuales, que se viola cuando se realiza un misrouting local.

2. El método de la reivindicación 1, donde la conexión entre los diferentes encaminadores de un mismo grupo se realiza de acuerdo a un grafo completo, y la conexión entre los diferentes grupos también se realiza de acuerdo a un grafo completo, y cada puerto local comprende solo 3 canales virtuales y cada puerto global comprende solo 2 canales virtuales.

3. El método de cualquiera de las reivindicaciones anteriores, donde para cada paquete situado en un canal virtual de un puerto de un encaminador, comprende:

-calcular al menos un salto de acuerdo a un encaminamiento mínimo entre el encaminador en que se encuentra dicho paquete y el encaminador al que está conectado el nodo al que dicho paquete está dirigido;

-calcular al menos un salto de acuerdo a un encaminamiento no-mínimo que comprende un misrouting global, a través de un grupo de encaminadores intermedio diferente del grupo al que pertenecen el encaminador de origen y el encaminador al que está conectado el nodo destino del paquete;

-calcular, si no se ha alcanzado un determinado límite de misrouting locales y el encaminamiento mínimo ha calculado saltos de tipo local, al menos un salto local no-mínimo diferente a dichos saltos calculados mediante el encaminamiento mínimo;

-seleccionar uno de dichos saltos en función de un determinado criterio.

4. El método de la reivindicación 3, que emplea un asignador unificado en cada encaminador para llevar a cabo la selección de uno de dichos saltos para que avance un paquete.

5. El método de la reivindicación 3, seleccionándose una ruta para cada paquete en cada ciclo de arbitraje mediante una comparación de la ocupación del canal virtual de entrada en el siguiente encaminador correspondiente a una ruta mínima seleccionada, frente a la ocupación de los canales virtuales de entrada de los encaminadores correspondientes a otras rutas.

6. El método de la reivindicación 3, seleccionándose una ruta para cada paquete en cada ciclo de arbitraje mediante una comparación de los valores de una pluralidad de contadores de contención, existiendo tantos contadores como puertos de salida tiene el encaminador, registrando dichos contadores el número de paquetes de los puertos de entrada cuya ruta mínima avanza por el puerto de salida correspondiente.

7. El método de la reivindicación 3, seleccionándose una ruta para cada paquete en cada ciclo de arbitraje de acuerdo a una combinación tanto de la información obtenida de la ocupación de los canales virtuales de entrada de los encaminadores vecinos como de una pluralidad de contadores de contención, registrando dichos contadores el número de paquetes de los puertos de entrada cuya ruta mínima avanza por el puerto de salida correspondiente.

8. El método de cualquiera de las reivindicaciones anteriores, en el que se emplea control de flujo de agujero de gusano o wormhole en todos los saltos en que se respeta el orden total establecido para los canales virtuales, y control de flujo de paso a través o virtual cut-through en los saltos en que se hace un misrouting local que viola dicho orden total, permitiendo que todos los canales virtuales tengan un tamaño inferior al tamaño máximo del paquete menos los correspondientes al primer canal virtual.

9. El método de cualquiera de las reivindicaciones anteriores, donde dicho orden total puede ser un orden ascendente o un orden descendente.

10. Una red directa jerárquica formada por una pluralidad de encaminadores, cada uno de ellos con una pluralidad de puertos de tipo local y una pluralidad de puertos de tipo global, donde cada uno de dichos puertos comprende una pluralidad de canales virtuales, donde dichos encaminado res forman grupos, donde los diferentes encaminadores de un mismo grupo están interconectados mediante una topología conexa empleando enlaces de tipo local uniendo parejas de puertos de tipo local, y a su vez los diferentes grupos están interconectados mediante una topología conexa empleando enlaces de tipo global uniendo parejas de puertos de tipo global, estando dicha red directa jerárquica caracterizada por que comprende medios para llevar a cabo el método según cualquiera de las reivindicaciones de la 1 a la 9.

Pout

!

Li2j

FIGURA 1

FIGURA 2

FIGURA 3

[43-1 1

FIGURA 4

152-1 Go I

FIGURA 5

FIGURA 6

. ... -------._---.

. -....

a)

f)

FIGURA 7

al bl el

FIGURA 8