PROCEDIMIENTO DE CONTROL DE CONGESTIÓN EN REDES MULTIETAPA CON ENCAMINAMIENTO DISTRIBUIDO.

Procedimiento de control de congestión en redes multietapa con encaminamiento distribuido.

De especial aplicación en redes de interconexión de sistemas de computación paralela de altas prestaciones, más en particular para redes multietapa con encaminamiento distribuido implementado mediante etiquetas de encaminamiento, el procedimiento de control de congestión aquí descrito permite eliminar el efecto negativo de bloqueo de cabeza de línea, más conocido como "Hol blocking", de forma que el tráfico no congestionado no se vea afectado por el tráfico congestionado. La presente invención proporciona una solución costo-efectiva y escalable, para el control de situaciones de congestión, permitiendo construir "clusters" basados en redes multietapa con encaminamiento distribuido de elevadas prestaciones incluso en situaciones de alta carga de tráfico de paquetes de información.

PROCEDIMIENTO DE CONTROL DE CONGESTIÓN EN REDES MUL TIETAPA CON ENCAMINAMIENTO DISTRIBUIDO

5

OBJETO DE LA INVENCIÓN

1 o La presente invención pertenece al sector de las redes informáticas, y más concretamente a redes de interconexión de sistemas de computación paralela de altas prestaciones con topología multietapa y encaminamiento distribuido implementado mediante etiquetas de encaminamiento (routing tags) .

15 20 El objeto principal de la presente invención es un procedimiento de control que destaca fundamentalmente por permitir una gestión inteligente y eficiente de la congestión de paquetes de información producida en redes de interconexión multietapa que emplean encaminamiento distribuido implementado mediante etiquetas de encaminamiento, consiguiendo eliminar totalmente el bloqueo de cabeza de línea (Hol blocking) . ANTECEDENTES DE LA INVENCIÓN

2 5 30 En la actualidad, el incremento del uso de los sistemas de computación en paralelo, han hecho que las redes de interconexión pasen a tener un papel crítico. Estas redes son diseñadas bajo un requisito fundamental: el ahorro en coste y consumo de energía. Debido a esta restricción los diseños de red actuales se construyen con un número reducido de componentes, por lo que las redes alcanzan el punto de saturación con una menor carga de tráfico, esto es, el tráfico de paquetes de información en la red se "atasca" más fácilmente y provoca una congestión, o saturación, en gran parte de su estructura interna. Debido a que dichas congestiones pueden degradar de forma muy severa el rendimiento de las redes, se hace necesario algún mecanismo que consiga

mitigar su impacto negativo.

El principal efecto negativo de la congestión es el bloqueo de cabeza de

línea (Head-of-Line blocking, más conocido como Hol blocking) que aparece

5 cuando el tráfico que no genera directamente congestión se ralentiza como

consecuencia de compartir recursos con el tráfico congestionado. Aunque

existen varias propuestas para reducir el Hol-blocking, generalmente su eficacia

es directamente proporcional a sus requisitos en cuanto a recursos o a su

complejidad de implementación.

10

Actualmente existen varios desarrollos a nivel teórico que no han

llegado a ser desarrollados en fase de prototipo debido a que, aunque suponen

un avance en la técnica actual, son inviables comercialmente hablando.

Respecto a las propuestas teóricas que sí han sido desarrolladas

15 comercialmente, el mecanismo de control de congestión más popular

actualmente es el incluido en el estándar de red "lnfiniband", que se encuentra

implementado, por ejemplo, en los conmutadores de la compañía "Mellanox", y

que es hoy día el estándar más extendido entre las redes de interconexión que

emplean encaminamiento distribuido. No obstante, el control que realiza dicho

2 o mecanismo en situaciones de congestión es claramente optimizable, pues las

prestaciones y el rendimiento de las redes a las que se encuentra aplicado se

reducen considerablemente durante dichas situaciones. Además, el

comportamiento de este mecanismo es demasiado sensible a variaciones tanto

de sus parámetros de configuración como del tráfico presente en la red.

25

Por otra parte, una de las propuestas teóricas más eficientes actualmente

para abordar los problemas derivados de la congestión de tráfico es la estrategia

de "Notificación Explícita de Congestión Regional" (RECN) , basada en aislar en

colas especiales los flujos de paquetes que contribuyen a la congestión, evitando

3º así el efecto de bloqueo de la cabecera de línea (Hol blocking) que estos flujos

pueden causar a los demás. Con esta técnica "RECN", la localización y

caminos de los flujos de paquetes consisten en una secuencia explícita de saltos

entre los puertos de cada conmutador de la ruta.

Sin embargo, dicha estrategia "RECN" requiere del uso de

5 encaminamiento basado en fuente (source-based routing) , no siendo por tanto

aplicable en redes de interconexión con encaminamiento distribuido (distributed

routing) como "lnfiniBand". Aunque existen propuestas para adaptar la técnica

RECN a redes con encaminamiento distribuido, dichas propuestas presentan

algunos inconvenientes entre los que cabe destacar:

10

- no son escalables (baja o nula escalabilidad) debido a la enorme .

cantidad de memoria de control que requieren para redes de dimensión mediana

y grande,

- en situaciones con gran número de puntos congestionados diferentes,

15 dichos mecanismos RECN se quedan sin colas especiales donde almacenar el

tráfico congestionado,

- requieren de una memoria direccionable por contenido (CAM) en todos

los puertos de sus conmutadores, lo que hace que los costes de implementación

así como la superficie de silicio requerida aumenten.

20

En general, estos inconvenientes se deben a que las soluciones actuales

dirigidas a redes con encaminamiento distribuido, emplean listas de destinos

finales que llevan a los paquetes de información a cruzar por un punto

determinado. Dichas listas de destinos requieren de una gran cantidad de

2 5 memoria de control, especialmente en redes de gran tamaño, presentando una

baja escalabilidad y unos costes de implementación elevados.

DESCRIPCIÓN DE LA INVENCIÓN

3 o Mediante la presente invención se solucionan los inconvenientes

anteriormente citados proporcionando un procedimiento de control que permite

provocado por situaciones de congestión originadas en redes de interconexión

de sistemas de computación paralela de altas prestaciones, más concretamente

en redes multietapa con encaminamiento distribuido implementado mediante

etiquetas de encaminamiento, consiguiendo todo ello de forma eficiente, con un

5 menor coste y una menor complejidad de implementación que las técnicas

actuales, y permitiendo, por tanto, construir "clusters" basados en redes

multietapa con encaminamiento distribuido de elevadas prestaciones incluso en

situaciones de alta carga.

1º El procedimiento de control de congestión de la presente invención, parte

de los principios básicos de la estrategia "RECN", basada fundamentalmente en

el aislamiento dinámico del tráfico congestionado en colas especiales

asignadas en los puertos de los conmutadores cuando éstos últimos son

conscientes de la existencia de una situación de congestión en un punto

15 concreto de la red. De esta manera se consigue que el tráfico no

congestionado no se vea afectado por el tráfico congestionado, y por tanto, los

paquetes de información que no producen congestión no ven ralentizadas sus

rutas, desde su puerto de origen hasta el puerto final de destino.

2º Más concretamente, el procedimiento de control de congestión aquí

descrito comprende una primera etapa de detección e identificación de puntos

críticos o puntos congestionados existentes en los conmutadores de la red.

Dichos puntos críticos representan los lugares en los que existe una congestión

de tráfico y por tanto los paquetes de información sufren un retardo que reduce

2 5 de forma importante la velocidad y el rendimiento de la red de interconexión

multietapa. De acuerdo con una realización preferente, esta primera etapa de

detección de puntos críticos se ejecuta midiendo el nivel de ocupación de las

colas convencionales de los puertos de entrada de cada conmutador.

3º A continuación, se almacenan en el puerto de entrada que detecta

congestión datos de interés e información relativa a la localización de cada punto

preferentemente una memoria ternaria direccionable por contenido, más

conocida como T-CAM. Más en particular, la localización del punto crítico se

indica implícitamente mediante una serie de bits (etiqueta) con un valor concreto,

de manera que todos los paquetes dirigidos al punto crítico contienen dicha

5 etiqueta (esto es, dicho valor) en la codificación binaria del identificador de su

destino final. Cabe señalar que esto es posible gracias a que se asume que la

red usa encaminamiento distribuido implementado mediante etiquetas de

encaminamiento. El resto de bits de la codificación binaria del destino es

irrelevante, de ahí que sea necesario el uso de la T-CAM, que permite almacenar

10 bits con valor "1", "0", y "cualquiera".

Además, al mismo tiempo que se almacena la información...

1.Procedimiento de control de congestión en redes multietapa con

encaminamiento distribuido implementado mediante etiquetas de

5 encaminamiento, presentando dichas redes al menos un conmutador (SW)

dotado de puertos de entrada y puertos de salida (S) entre los que fluyen con

diferentes rutas (R) , paquetes (P) de información dispuestos inicialmente en

colas convencionales de almacenamiento, estando dicho procedimiento de

control caracterizado porque comprende las siguientes etapas:

lO a) identificación de al menos un punto crítico (C) en un conmutador (SW)

de la red, existiendo en dicho punto crítico (C) una congestión de paquetes (P)

de información,

b) almacenamiento en una memoria de control interna, de la localización

específica del punto crítico (C) identificado, mediante una secuencia concreta de

15 bits (etiqueta) que está incluida en la codificación binaria del identificador del

destino de todos los paquetes (P) que crucen dicho punto crítico (C) ,

c) asignación de una cola especial de almacenamiento en el puerto de

entrada del conmutador (SW) que ha detectado el punto crítico (C) , para

almacenar paquetes (P) que están destinados a cruzar por dicho punto crítico

20 (C) ,

d) identificación de la ruta (R) a seguir por cada uno de los paquetes (P)

de información, a partir de la codificación binaria del identificador del destino

final de dichos paquetes (P) ,

e) detección de los paquetes (P) de información que están destinados a

25 cruzar por los puntos críticos (C) , estableciendo a dichos paquetes (P) como los

causantes de la cogestión producida,

f) almacenamiento en colas especiales, de aquellos paquetes (P) de

información que están destinados a cruzar los puntos críticos (C) previamente

identificados, y

3 O g) notificación de la existencia de una congestión a los demás

conmutadores (SW) de la red, informándoles de la localización de cada uno de

los puntos críticos (C) previamente detectados.

5 2.Procedimiento de control, de acuerdo con la reivindicación caracterizado porque la identificación del punto crítico (C) de la etapa a) realiza midiendo el nivel de ocupación de las colas convencionales almacenamiento de los puertos de entrada de cada conmutador (SW) . 1, se de

10 3.Procedimiento de control, de acuerdo con la reivindicación 2, caracterizado porque se considera que existe un punto crítico (C) si al medir el nivel de ocupación de una cola convencional se sobrepasa un determinado valor umbral.

15 4.Procedimiento de control, de acuerdo con la reivindicación 1, caracterizado porque el almacenamiento de la localización del punto crítico (C) de la etapa b) se lleva a cabo en una memoria ternaria direccionable por contenido, donde se guarda un valor binario de etiqueta que estará incluido en el valor binario del destino de todos los paquetes (P) que crucen dicho punto crítico (C) , no siendo relevantes el resto de bits de dicha codificación.

2 O 25 5.Procedimiento de control, de acuerdo con la reivindicación 1, caracterizado porque la notificación de la existencia de una congestión a los demás conmutadores (SW) de la red de la etapa g) , se realiza mediante el empleo de mensajes especiales de notificación que contienen la etiqueta correspondiente al punto crítico (C) cuya información se propaga, y almacenando igualmente esta información en una memoria ternaria direccionable por contenido.