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.
Tipo: Patente de Invención. Resumen de patente/invención. Número de Solicitud: P201101278.
Solicitante: UNIVERSIDAD CASTILLA - LA MANCHA.
Nacionalidad solicitante: España.
Inventor/es: GARCÍA GARCÍA,Pedro Javier, QUILES FLOR,Francisco José, ESCUDEROS SAHUQUILLO,Jesús, DUATO MARÍN,José, FLICH CARDO,José.
Fecha de Publicación: .
Clasificación Internacional de Patentes:
- H04L12/801 ELECTRICIDAD. › H04 TECNICA DE LAS COMUNICACIONES ELECTRICAS. › H04L TRANSMISION DE INFORMACION DIGITAL, p. ej. COMUNICACION TELEGRAFICA (disposiciones comunes a las comunicaciones telegráficas y telefónicas H04M). › H04L 12/00 Redes de datos de conmutación (interconexión o transferencia de información o de otras señales entre memorias, dispositivos de entrada/salida o unidades de tratamiento G06F 13/00). › Control de flujo o control de congestión.
![PROCEDIMIENTO DE CONTROL DE CONGESTIÓN EN REDES MULTIETAPA CON ENCAMINAMIENTO DISTRIBUIDO.](https://patentados.com/img/2013/06/1241756/procedimiento-control-congestion-redes-multietapa-encaminamiento-distribuido.jpg)
Fragmento de la descripció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
notificación de los puntos congestionados es relativamente sencilla ya que loscaminos 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
eliminar el bloqueo de cabeza de línea, más conocido como "Hol blocking",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
crítico detectado, utilizando una memoria de control interna, siendopreferentemente 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...
Reivindicaciones:
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.
Patentes similares o relacionadas:
Método y conmutador para gestionar tráfico en una red de transporte, del 1 de Julio de 2020, de TELEFONAKTIEBOLAGET LM ERICSSON (PUBL): Un método para gestionar el tráfico de una pluralidad de paquetes en una pluralidad de flujos de paquetes transmitidos mediante el uso de una interfaz con intervalos […]
Control adaptativo de sobrecarga de pares en redes móviles, del 1 de Julio de 2020, de Microsoft Technology Licensing, LLC: Un método informatizado para ajustar adaptativamente una tasa de transacción en un nodo de la red móvil , el método informatizado que comprende: recibir […]
Selección de una instancia de segmento de red para la transmisión de paquetes ascendentes, del 27 de Mayo de 2020, de Orange: Procedimiento de selección de una instancia de segmento de red (S0, S1, S2) en una red de comunicación para la transmisión de datos ascendentes desde un terminal […]
Aparatos de telecomunicaciones y método para comunicar paquetes de datos en el protocolo de Internet, del 20 de Mayo de 2020, de Orange: Un sistema de telecomunicación para proporcionar un mecanismo para comunicar paquetes de datos de Internet con un equipo de usuario de comunicaciones […]
Proxy de protocolo de control de trasmisión en una red de acceso de radio de evolución a largo plazo, del 20 de Mayo de 2020, de Altiostar Networks, Inc: Un dispositivo para la transmisión de paquetes de datos entre un dispositivo de usuario y un servidor , comprendiendo el dispositivo […]
Método de potenciación de conectividad de paquetes continua en un sistema de comunicaciones inalámbrico y aparato relacionado, del 6 de Mayo de 2020, de INNOVATIVE SONIC LIMITED: Método de potenciación de conectividad de paquetes continua, abreviada como CPC, para un equipo de usuario, denominado UE a continuación en el presente […]
Dispositivo de transmisión de datos y método de transmisión de datos, del 4 de Marzo de 2020, de NEC CORPORATION: Un dispositivo de transmisión de datos , que comprende: un receptor , configurado para recibir datos encriptados; un transmisor , configurado para transmitir […]
Procedimiento y aparato para la segmentación de paquetes y la señalización de concatenación en un sistema de comunicación, del 4 de Marzo de 2020, de OPTIS WIRELESS TECHNOLOGY, LLC: Un procedimiento para transmitir un paquete de datos que tiene una cabecera y una carga útil, que comprende las etapas de: configurar la carga […]