Design of Congestion Management Strategies for High-Performance Interconnection Networks Using Adaptive Routing
José Manuel Rocher González · RUIdeRA - Institutional University Repository (University of Castilla-La Mancha) · 2024
En los sistemas de computación de alto rendimiento (HPC, en inglés), en los que miles de nodos trabajan colectivamente, la red de interconexión es crucial para lograr un buen rendimiento. De hecho, la topología de la red, la arquitectura de los switches y el algoritmo de encaminamiento determinan el rendimiento de la red y, en última instancia, el del sistema. A medida que aumenta el número de nodos en los sistemas HPC y las aplicaciones soportadas son cada vez más exigentes en cuanto a la comunicación, el uso de técnicas para hacer frente a la congestión de la red y a sus efectos negativos gana importancia. Entre las topologías más comunes en los sistemas HPC, la familia de topologías Fat-Tree ofrece varias rutas de camino mínimo entre cualquier par de nodos, lo que permite que los algoritmos de encaminamiento equilibren la carga de los flujos de tráfico entre los enlaces disponibles. Por un lado, los algoritmos de encaminamiento, como el adaptativo o el oblivous, tratan de equilibrar la carga de tráfico en la red para prevenir o eliminar la congestión. Por otro lado, existen esquemas de encaminamiento determinista que equilibran el número de caminos por enlace con el objetivo de reducir el bloqueo de cabea de línea (Head-of-Line blocking, en inglés) generado por la congestión. Otras técnicas ampliamente utilizadas para hacer frente a la congestión se basan en los esquemas de colas. Este enfoque se basa en el almacenamiento por separado de diferentes flujos de paquetes en los buffers de los puertos, de forma que se reduce el Head-of-Line blocking y el acaparamiento del buffer por parte de algún flujo (buffer hogging). Los esquemas de colas existentes utilizan diferentes políticas para separar los flujos, y pueden implementarse de diferentes maneras. Sin embargo, la mayoría de los esquemas de colas suelen utilizarse y diseñarse asumiendo que la red está configurada para usar un encaminamiento determinista, mientras que en realidad podrían combinarse también con un encaminamiento multicamino. Esta tesis se centra en proponer técnicas de encaminamiento adaptativo para hacer frente a los efectos adversos de la congestión. Las propuestas resultantes de los trabajos desarrollados para conseguir este objetivo básico han evolucionado de forma que se pueden diferenciar tres partes en la tesis. En la primera parte, durante el inicio de la tesis, se estudiaron los efectos adversos de la congestión en los encaminamientos adaptativos y también cómo éstos afectan a la eficiencia de distintos esquemas de colas. Con los resultados obtenidos, se concluyó que la congestión se esparce por más enlaces y colas cuando se usan encaminamientos adaptativos, reduciendo la eficacia de estos esquemas de colas. Para mitigar estos efectos se proponen una serie de restricciones al encaminamiento adaptativo. En la segunda parte, se propone una técnica para almacenar los flujos adaptados en una cola especial. La idea principal es adaptar los flujos congestionantes y, al aislarlos en la cola especial una vez adaptados, se consigue reducir los efectos adversos de la congestión en la red. Esta propuesta fue evaluada, mediante simulaciones, probándola en switches que usan bien información local, bien información global, obteniendo mejores resultados en el segundo caso. En la tercera parte de la tesis, se propone una nueva estrategia para el encaminamiento adaptativo. Mediante el uso de la información global de la red se propone una técnica de encaminamiento adaptativo basada en el tratamiento de distintos tipos de escenarios de congestión de forma independiente. Por un lado, los escenarios de congestión ``in-cast'' se resuelven aislando los flujos congestionantes (utilizando encaminamiento determinista) y adaptando los flujos víctima. Por otro lado, los escenarios de congestión “in- network'' se resuelven adaptando los flujos congestionantes para eliminar el punto de congestión. Por último, es importante mencionar que durante el desarrollo de esta tesis, el autor ha realizado una estancia de investigación en el laboratorio de investigación Simula, en Noruega. La estancia se centró en la evaluación del encaminamiento adaptativo en redes Infiniband. Más concretamente, el estudio se basó en experimentos realizados en un cluster heterogéneo donde todos los nodos estaban conectados a través de una red Infiniband HDR de 200 Gbps. La investigación realizada durante la estancia analiza el comportamiento básico del encaminamiento adaptativo en InfiniBand, sus ventajas y los efectos adversos en las topologías Fat-Tree.