Método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida para supercomputadores y grandes centros de proceso de datos.

Método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida que comprende:

subdividir la red de interconexión en grupos de nodos denominados bandas, donde cada banda comprende una pluralidad de nodos alineados según al menos una dirección comprendida dentro de una única de las dimensiones ortogonales de la red; subdividir el buffer de cada puerto de entrada de cada conmutador en tantas colas como bandas en que se subdivida la red, de manera que a cada banda de la red le corresponda una única cola dentro de cada buffer; almacenar cada paquete de datos transmitido a través de la red, a su llegada al buffer de cada puerto de entrada de cada conmutador, en la cola correspondiente a la banda en la cual está comprendido el nodo al cual se dirige dicho paquete de datos.

Método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida para supercomputadores y grandes centros de proceso de datos.

Objeto de la invención

La presente invención se refiere a un método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida para supercomputadores y grandes centros de proceso de datos.

Tiene aplicación en la industria dedicada al diseño, fabricación y explotación de redes de interconexión, especialmente en las destinadas al tráfico de alta densidad entre supercomputadores que interconectan miles de nodos de procesamiento en paralelo.

Problema técnico a resolver y Antecedentes de la invención

Las necesidades de comunicación de la sociedad contemporánea han hecho que las redes de interconexión hayan crecido enormemente en las últimas décadas, no sólo en tamaño, sino también en complejidad.

En los últimos años, la necesidad de interconectar miles de nodos de procesamiento dentro de supercomputadores de gran potencia que intercambian un flujo de datos cada vez mayor, ha llevado a diseñar nuevas topologías y nuevas arquitecturas de redes de interconexión que permiten gestionar de una manera más eficiente dicho flujo de datos.

Junto a las mencionadas topologías y arquitecturas, se han establecido diversos mecanismos que permiten optimizar la gestión de los flujos de datos a través de las redes de interconexión.

Un tipo común de topología de redes de interconexión es la llamada red "directa". En este tipo de red, los diferentes dispositivos o nodos de procesamiento que componen la red se interconectan de manera directa unos con otros, sin intermediación de ningún tipo de "conmutador" o "switch" que centralice todos o parte de los canales de comunicación. Un ejemplo de este tipo de red son las redes con topología "tórica", malla, en anillo o cubo de dos, tres o más dimensiones. El problema de estas topologías es su elevado diámetro cuando interconectan un gran número de nodos de procesamiento, unido a la alta diversidad de caminos que ofrecen. El resultado es un rendimiento reducido y una alta probabilidad de que el rendimiento de la red se vea afectado por situaciones de saturación.

Otro tipo común de topología de redes de interconexión es la llamada red "indirecta". En este tipo de red, la interconexión entre terminales o nodos de procesamiento que componen la red se hace a través de los mencionados "conmutadores" o "switches", distribuidos en una o más etapas, que centralizan todas o algunas de las vías de comunicación. Un ejemplo de estos tipos de red son las llamadas redes con topología de árbol grueso o "fat tree", como se las conoce comúnmente por su nombre en inglés.

Las topologías indirectas mejoran el rendimiento de la transmisión de paquetes de datos con respecto a las topologías directas, en términos de disminución de la latencia y mayor ancho de banda, cuando dichas redes incorporan un gran número de terminales o nodos. Sin embargo, cuando aumenta el número de nodos de procesamiento que la red debe interconectar, la necesidad de introducir un mayor número de conmutadores que interconectan dichos nodos entre sí encarece la instalación y el mantenimiento de dichas redes.

Recientemente, se ha propuesto una topología de red de interconexión, denominada "red híbrida", que se caracteriza por aunar las características positivas de los dos tipos de redes

mencionados anteriormente. Por un lado, mejora el rendimiento de las redes de tipo directo, al proporcionar rutas más cortas a través de la red mediante pequeñas redes indirectas de una o dos etapas, y por otro, reduce el coste con respecto a las redes de tipo indirecto convencionales, al minimizar al máximo el número de conmutadores necesarios para proporcionar rutas o interconectar todos los nodos de procesamiento de la red de interconexión.

Al igual que para otros tipos de topología de redes, para las redes de tipo híbrido también se han desarrollado diversos algoritmos de encaminamiento que distribuyen con mayor o menor eficiencia el tráfico de paquetes de datos a través de la red de interconexión. Algunos de estos algoritmos se diseñan específicamente para redes que utilizan componentes con arquitecturas estandarizadas, como puede ser InfiniBand.

En concreto, algunos algoritmos de encaminamiento de los paquetes de datos tienen la capacidad de variar su ruta en función de diversos criterios, como puede ser el estado del tráfico en la red o la topología de la misma. Estos son los algoritmos de encaminamiento de tipo adaptativo.

Por el contrario, algunos algoritmos de encaminamiento se caracterizan por establecer unas pautas acerca de cómo debe realizarse la transmisión de los datos a través de la red, sin tener en cuenta su topología concreta y su estado de carga. Estos son los algoritmos de tipo determinista. Los algoritmos de encaminamiento de tipo determinista fijan el camino a seguir por cada paquete de datos para que éste se transmita a través de la red, desde su nodo de origen hasta su nodo de destino, de manera que, dado un nodo origen y un nodo destino, siempre se configura el mismo camino para todos los paquetes de datos que circulan por la red. Algunos algoritmos de encaminamiento deterministas suelen conseguir tan buenos resultados como los algoritmos de encaminamiento adaptativos en términos de proporcionar un elevado rendimiento de la red, haciendo un menor uso de los recursos disponibles de la red.

Un algoritmo de encaminamiento de tipo determinista utilizado comúnmente en redes con topología de tipo híbrido se denomina "Hybrid-DOR", que se deriva de otro algoritmo de encaminamiento denominado DOR (del inglés, Dimension-Order Routing), pero en este caso particularizado para redes de tipo híbrido.

Según el algoritmo Hybrid-DOR, los paquetes se encaminan a través de la red híbrida recorriendo la distancia que va desde su nodo de origen hacia su nodo de destino en tantas etapas como dimensiones ortogonales tenga la red híbrida; en cada una de estas etapas los paquetes de datos circulan entre dos nodos (a través de un conmutador de la red) que pertenecen a una alineación comprendida dentro de una de las dimensiones ortogonales de la red.

El algoritmo Hybrid-DOR establece una "dimensión prioritaria" dentro de la red híbrida, de manera que en la primera etapa de transmisión, los paquetes de datos recorren la distancia que va desde su nodo de origen hasta otro nodo (a través de un conmutador de la red), estando ambos nodos alineados según una dirección comprendida dentro de dicha dimensión prioritaria.

Los puertos de entrada de los conmutadores de la red de interconexión disponen de una memoria RAM denominada "buffer", en donde se almacenan transitoriamente dichos paquetes de datos hasta que se envían a través del puerto de salida de dicho conmutador en dirección a su nodo de destino de la red.

El buffer de cada puerto de entrada de cada conmutador está típicamente dividido en una serie de estructuras lógicas de almacenamiento de paquetes, denominadas "colas" o "canales virtuales". Dichas colas organizan los paquetes según su orden de llegada, y el paquete en

cabeza de cada cola se selecciona primero para ser transmitido hacia el puerto de salida seleccionado.

Según la topología de la red y el algoritmo de encaminamiento, el usuario o programador de la red de interconexión puede establecer el denominado "algoritmo de mapeo de paquetes a colas o canales virtuales del buffer". El algoritmo de mapeo gestiona el tráfico de paquetes de datos a través de la red, desde una unidad denominada "Gestor de Subred", SM (del inglés, Subnet Manager).

Gracias al algoritmo de mapeo, el programador de la red establece de qué manera se van a distribuir los paquetes de datos en colas o canales virtuales a su llegada a los puertos de entrada de los conmutadores o nodos de la red.

El algoritmo de mapeo establece en cuántas colas ha de dividirse el buffer de cada puerto de entrada de cada conmutador.

Los algoritmos de mapeo se han utilizado ampliamente en las redes de interconexión de altas prestaciones para combatir los efectos negativos de la congestión, que degradan las prestaciones en este tipo de redes. La congestión se origina cuando dos flujos de datos que confluyen dentro del mismo conmutador, solicitan el mismo puerto de salida. Puesto que el ancho de banda de dicho puerto de salida no puede dar servicio a ambos flujos a la vez, se introduce un retardo en el avance de ambos flujos, lo que se conoce como "contención".

Si la contención es persistente, principalmente debido a que los flujos de...

1. Método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida para supercomputadores y grandes centros de proceso de datos, donde dichas redes incorporan una pluralidad de nodos (1) distribuidos en una o más dimensiones ortogonales (8) e interconectados entre sí de manera indirecta por conmutadores (2) distribuidos en una o más etapas, donde los nodos (1) se envían entre sí información agrupada en mensajes, estando dichos mensajes a su vez formados por unidades básicas denominadas paquetes de datos, donde los conmutadores (2) comprenden una pluralidad de puertos (5) de entrada de enlaces (4) que conectan los nodos (1) de la red con dichos conmutadores (2), donde en cada puerto (5) de entrada de cada conmutador (2) existe un buffer (6) para el almacenamiento transitorio de los paquetes de datos que se transmiten por la red y que llegan a cada puerto (5) de entrada de cada conmutador (2), donde cada buffer (6) se subdivide en tantas colas (7) como determine el usuario o administrador de la red de interconexión, donde la transmisión de los paquetes de datos entre los distintos nodos (1) de la red se lleva a cabo siguiendo las directrices de un algoritmo de encaminamiento que establece que los paquetes de datos se transmiten a través de la red por etapas en cada una de las cuales los paquetes de datos recorren la red en una única dirección alineada según una de las dimensiones ortogonales (8) en que se distribuyen los nodos (1) de la red, de manera que el recorrido que realiza el paquete de datos desde su nodo (1) de origen hasta su nodo (1) de destino se realiza en tantas etapas como dimensiones ortogonales (8) de la red tenga que recorrer dicho paquete de datos para alcanzar su nodo (1) de destino desde su nodo (1) de origen, donde dicho algoritmo de encaminamiento establece una dimensión prioritaria que define la primera etapa de transmisión de paquetes de datos, caracterizado por que comprende las siguientes fases:

a) subdividir la red de interconexión en grupos de nodos (1) denominados bandas (3), donde cada banda (3) comprende una pluralidad de nodos (1) alineados según al menos una dirección, donde cada dirección está comprendida dentro de una única de las dimensiones ortogonales (8) de la red híbrida de interconexión;

b) subdividir el buffer (6) de cada puerto (5) de entrada de cada conmutador (2) en tantas colas (7) como bandas (3) en que se haya subdividido la red de interconexión, de manera que a cada banda (3) de la red le corresponda una única cola (7) dentro de cada buffer (6);

c) almacenar cada paquete de datos transmitido a través de la red, a su llegada al buffer (6) de un puerto (5) de entrada de un conmutador (2) de la red, en la cola (7) correspondiente a la banda (3) en la cual está comprendido el nodo (1) de la red al cual se dirige dicho paquete de datos.

2. Método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida para supercomputadores y grandes centros de proceso de datos según la reivindicación 1, caracterizado por que las bandas (3) en las que se subdivide la red comprenden nodos (1) alineados según al menos una dirección, donde cada dirección está comprendida dentro de la mencionada dimensión prioritaria establecida por el algoritmo de encaminamiento.

3. Método para reducir los efectos negativos de la congestión en redes de interconexión de alto rendimiento con topología híbrida para supercomputadores y grandes centros de proceso de datos según la reivindicación 1, caracterizado por que la correspondencia de cada cola (7) de los buffer (6) de los puertos (5) de entrada de los conmutadores (2) de la

red, con cada banda (3) en que se ha subdividido la red, se establece según la siguiente fórmula matemática:

Nodo de destino x Número de colas

Cola seleccionada = ----------------;----------------------------------

Numero de nodos

donde la cola (7) seleccionada es igual al cociente o parte entera de la división indicada en la fórmula anterior.