Conmutación de agujeros de gusano

El control de flujo por agujero de gusano , también llamado conmutación por agujero de gusano o enrutamiento por agujero de gusano , es un sistema de control de flujo simple en redes informáticas basado en enlaces fijos conocidos. Es un subconjunto de los métodos de control de flujo denominados control de flujo de búfer de flit . ^{[ 1 ]}^{: Capítulo 13.2.1}

El término conmutación es más apropiado que enrutamiento, ya que "enrutamiento" define la ruta o el camino que se toma para llegar al destino. ^{[ 2 ]}^{[ 3 ]} La técnica del agujero de gusano no dicta la ruta hacia el destino, sino que decide cuándo el paquete avanza desde un enrutador.

La conmutación por agujero de gusano se utiliza ampliamente en sistemas multicomputadora debido a su baja latencia y sus reducidos requisitos en los nodos. ^{[ 3 ]}^{: 376}

El enrutamiento de agujero de gusano admite una entrega garantizada de paquetes de muy baja latencia y alta velocidad, adecuada para la comunicación en tiempo real . ^{[ 4 ]}

Principio del mecanismo

En el control de flujo del agujero de gusano, cada paquete se divide en pequeños fragmentos llamados flits (unidades de control de flujo o dígitos de control de flujo).

Generalmente, los primeros flits, denominados flits de cabecera, contienen información sobre la ruta del paquete (por ejemplo, la dirección de destino) y establecen el comportamiento de enrutamiento para todos los flits subsiguientes asociados al paquete. A los flits de cabecera les siguen cero o más flits de cuerpo, que contienen la carga útil de datos. Algunos flits finales, denominados flits de cola, realizan tareas administrativas para cerrar la conexión entre los dos nodos.

En la conmutación por bucle, cada búfer está inactivo o asignado a un paquete. Un flit de encabezado se puede reenviar a un búfer si este está inactivo, asignándolo al paquete. Un flit de cuerpo o de cola se puede reenviar a un búfer si este está asignado a su paquete y no está lleno. El último flit libera el búfer. Si el flit de encabezado se bloquea en la red, el búfer se llena y, una vez lleno, no se pueden enviar más flits: este efecto se denomina "contrapresión" y puede propagarse hasta la fuente.

El nombre "agujero de gusano" alude a la forma en que se envían los paquetes a través de los enlaces: la dirección es tan corta que puede traducirse antes de que llegue el mensaje. Esto permite al enrutador configurar rápidamente el enrutamiento del mensaje y luego "retirarse" del resto de la conversación. Dado que un paquete se transmite flit a flit, puede ocupar varios búferes de flit a lo largo de su ruta, creando una imagen similar a la de un gusano.

Este comportamiento es bastante similar a la conmutación de corte directo , ^{[ 5 ]} comúnmente llamada "corte directo virtual", siendo la principal diferencia que el control de flujo de corte directo asigna búferes y ancho de banda de canal a nivel de paquete, mientras que el control de flujo de agujero de gusano lo hace a nivel de flit.

En caso de dependencia circular , esta contrapresión puede provocar un bloqueo mutuo.

En la mayoría de los aspectos, el protocolo wormhole es muy similar al reenvío ATM o MPLS , con la excepción de que la celda no tiene que ponerse en cola .

Una característica especial del control de flujo de agujeros de gusano es la implementación de canales virtuales:

Un canal virtual contiene el estado necesario para coordinar el manejo de los flits de un paquete a través de un canal. Como mínimo, este estado identifica el canal de salida del nodo actual para el siguiente salto de la ruta y el estado del canal virtual (inactivo, esperando recursos o activo). El canal virtual también puede incluir punteros a los flits del paquete que están almacenados en búfer en el nodo actual y la cantidad de búferes de flits disponibles en el siguiente nodo. ^{[ 1 ]}^{: 237}

Ejemplo

Una animación del cambio de un agujero de gusano con tres flujos diferentes. — Tres flujos en una red 2x2 usando conmutación de agujero de gusano

Consideremos la red 2x2 de la figura de la derecha, con 3 paquetes a enviar: uno rosa, compuesto por 4 flits, 'UVWX', de C a D; uno azul, compuesto por 4 flits, 'abcd', de A a F; y uno verde, compuesto por 4 flits, 'ijkl', de E a H. Suponemos que el enrutamiento se ha calculado tal como se muestra en el diagrama, lo que implica un conflicto de búfer en el enrutador inferior izquierdo. El rendimiento es de un flit por unidad de tiempo.

Primero, consideremos el flujo rosa: en el instante 1, el flit 'U' se envía al primer búfer; en el instante 2, el flit 'U' pasa por el siguiente búfer (suponiendo que el cálculo de la ruta no lleva tiempo), y el flit 'V' se envía al primer búfer, y así sucesivamente.

Los flujos azul y verde requieren una presentación paso a paso:

Tiempo 1: Tanto el flujo azul como el verde envían sus primeros destellos, 'i' y 'a'.
Tiempo 2: El flit 'i' puede pasar al siguiente búfer. Pero un búfer está dedicado a un paquete desde su primer flit hasta su último flit, por lo que el flit 'a' no puede ser reenviado. Este es el comienzo de un efecto de contrapresión . El flit 'j' puede reemplazar al flit 'i'. El flit 'b' puede ser enviado.
Tiempo 3: El paquete verde continúa. El flit azul 'c' no se puede reenviar (el búfer está ocupado con los flits 'b' y 'a'): este efecto de contrapresión llega a la fuente del paquete.
Tiempo 4: Igual que en el tiempo 3
Tiempo 5: El paquete verde ya no utiliza el búfer inferior izquierdo. El paquete azul se desbloquea y puede reenviarse (suponiendo que la información de "desbloqueo" se pueda reenviar en tiempo nulo).
Tiempo 6-10: El paquete azul atraviesa la red.

Ventajas

El control de flujo Wormhole hace un uso más eficiente de los búferes que el corte directo. Mientras que el corte directo requiere espacio de búfer para muchos paquetes, el método Wormhole necesita muy pocos búferes de flit (en comparación).
No es necesario almacenar en búfer un paquete completo para pasar al siguiente nodo, lo que reduce la latencia de la red en comparación con la conmutación de almacenamiento y reenvío .
El ancho de banda y la asignación de canales están desacoplados.

Uso

Las técnicas de túnel se utilizan principalmente en sistemas multiprocesador , especialmente en hipercubos . En un ordenador hipercubo, cada CPU se conecta a varios vecinos siguiendo un patrón fijo, lo que reduce el número de saltos entre CPUs. A cada CPU se le asigna un número (normalmente de 8 a 16 bits ), que es su dirección de red , y los paquetes se envían con este número en la cabecera. Cuando el paquete llega a un enrutador intermedio para su reenvío, este examina la cabecera (muy rápidamente), establece un circuito con el siguiente enrutador y finaliza la comunicación. Esto reduce la latencia (retraso) de forma notable en comparación con la conmutación de almacenamiento y reenvío , que espera a que el paquete esté completo antes de reenviarlo. Más recientemente, el control de flujo de túnel se ha aplicado en sistemas de red en chip (NOC), entre los que destacan los procesadores multinúcleo. En estos sistemas, se pueden conectar en red varios núcleos de procesador, o incluso unidades funcionales, en un único encapsulado de circuito integrado . A medida que los retrasos en los cables y muchas otras limitaciones no escalables en los elementos de procesamiento conectados se convierten en el factor dominante para el diseño, los ingenieros buscan simplificar las redes de interconexión organizadas, en las que los métodos de control de flujo desempeñan un papel importante.

Las tecnologías IEEE 1355 y SpaceWire utilizan agujeros de gusano.

Canales virtuales

Una extensión del control de flujo de túnel es el control de flujo de canal virtual , donde varios canales virtuales pueden multiplexarse a través de un canal físico. Cada canal virtual unidireccional se implementa mediante un par de búferes (flit) gestionados de forma independiente. De esta manera, diferentes paquetes pueden compartir el canal físico flit a flit. Los canales virtuales se introdujeron originalmente para evitar el problema del interbloqueo, pero también pueden utilizarse para reducir el bloqueo de túnel, mejorando la latencia y el rendimiento de la red. El bloqueo de túnel ocurre cuando un paquete adquiere un canal, impidiendo así que otros paquetes lo utilicen y obligándolos a detenerse. Supongamos que un paquete P0 ha adquirido el canal entre dos enrutadores. En ausencia de canales virtuales, un paquete P1 que llegue posteriormente se bloquearía hasta que se complete la transmisión de P0. Si se implementan canales virtuales, son posibles las siguientes mejoras:

Tras la llegada de P1, el canal físico puede multiplexarse entre ellos de forma iterativa, de modo que ambos paquetes avancen a la mitad de velocidad (dependiendo del esquema de arbitraje).
Si P0 es un paquete completo y P1 es solo un pequeño paquete de control del tamaño de unos pocos flits, este esquema permite que P1 pase por ambos enrutadores mientras que P0 se ralentiza durante un breve período de tiempo correspondiente a la transmisión de unos pocos paquetes. Esto reduce la latencia para P1.
Supongamos que P0 está temporalmente bloqueado aguas abajo del enrutador actual. El rendimiento aumenta al permitir que P1 proceda a la velocidad máxima del canal físico. Sin canales virtuales, P0 estaría ocupando el canal, sin utilizar realmente el ancho de banda disponible (ya que está bloqueado). ^{[ 6 ]}

El uso de canales virtuales para reducir el bloqueo de agujeros de gusano tiene muchas similitudes con el uso de colas de salida virtuales para reducir el bloqueo de cabecera de cola .

Enrutamiento

En un mismo paquete conmutado por túnel se puede utilizar una combinación de enrutamiento de origen y enrutamiento lógico. El valor del primer byte de un paquete Myrinet o SpaceWire es la dirección del paquete. Cada conmutador SpaceWire utiliza la dirección para decidir cómo enrutar el paquete. ^{[ 7 ]}

Enrutamiento de origen

Con el enrutamiento de origen, el remitente del paquete elige cómo se enruta el paquete a través del conmutador.

Si el primer byte de un paquete SpaceWire entrante se encuentra en el rango de 1 a 31, indica el puerto correspondiente del 1 al 31 del conmutador SpaceWire. El conmutador SpaceWire descarta ese carácter de enrutamiento y envía el resto del paquete a través de ese puerto. Esto expone el siguiente byte del paquete original al siguiente conmutador SpaceWire. El remitente del paquete puede optar por utilizar el enrutamiento de origen para especificar explícitamente la ruta completa a través de la red hasta el destino final de esta manera. ^{[ 7 ]}

Enrutamiento lógico

Con el enrutamiento lógico, el propio conmutador Spacewire decide cómo enrutar el paquete.

Si la dirección (el primer byte) de un paquete SpaceWire entrante está en el rango de 32 a 255, el conmutador SpaceWire utiliza ese valor como índice en una tabla de enrutamiento interna que indica a qué puerto(s) enviar el paquete y si eliminar o conservar ese primer byte. ^{[ 7 ]}

La dirección 0 se utiliza para comunicarse directamente con el conmutador y puede utilizarse para establecer las entradas de la tabla de enrutamiento para ese conmutador. ^{[ 7 ]}

Véase también

Referencias

1 2 William James Dally; Brian Towles (2004). "13.2.1". Principios y prácticas de las redes de interconexión . Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-200751-4.
↑ John L. Hennessy y David A. Patterson (2006). «Apéndice E.5». Arquitectura de computadoras: un enfoque cuantitativo (cuarta ed.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0.
1 2 Mohapatra, Prasant (1998), "Técnicas de enrutamiento de agujeros de gusano para sistemas multicomputadora conectados directamente" (PDF) , ACM Computing Surveys , 30 (3): 374–410 , CiteSeerX 10.1.1.11.9098 , doi : 10.1145/292469.292472 , S2CID 7850481 , archivado del original (PDF) el 11 de agosto de 2017 , recuperado el 12 de julio de 2017
↑ Sharad Sundaresan; Riccardo Bettati. "Gestión de conexiones distribuidas para comunicación en tiempo real sobre redes con enrutamiento tipo "wormhole" . 1997.
↑ Stefan Haas. "El estándar IEEE 1355: desarrollos, rendimiento y aplicación en física de altas energías" . 1998. pág. 59.
↑ Pavel Tvrdik. "Por qué el enrutamiento por agujeros de gusano es una técnica de conmutación importante"
1 2 3 4 Dr. Barry M Cook; Paul Walker. "Ethernet sobre SpaceWire: problemas de software" . 2007. pág. 2.

[Dally_and_Towles-1] 1 2 William James Dally; Brian Towles (2004). "13.2.1". Principios y prácticas de las redes de interconexión . Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-200751-4.

[2] John L. Hennessy y David A. Patterson (2006). «Apéndice E.5». Arquitectura de computadoras: un enfoque cuantitativo (cuarta ed.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0.

[Mohapatra-3] 1 2 Mohapatra, Prasant (1998), "Técnicas de enrutamiento de agujeros de gusano para sistemas multicomputadora conectados directamente" (PDF) , ACM Computing Surveys , 30 (3): 374–410 , CiteSeerX 10.1.1.11.9098 , doi : 10.1145/292469.292472 , S2CID 7850481 , archivado del original (PDF) el 11 de agosto de 2017 , recuperado el 12 de julio de 2017

[4] Sharad Sundaresan; Riccardo Bettati. "Gestión de conexiones distribuidas para comunicación en tiempo real sobre redes con enrutamiento tipo "wormhole" . 1997.

[5] Stefan Haas. "El estándar IEEE 1355: desarrollos, rendimiento y aplicación en física de altas energías" . 1998. pág. 59.

[6] Pavel Tvrdik. "Por qué el enrutamiento por agujeros de gusano es una técnica de conmutación importante"

[Cook-Walker-7] 1 2 3 4 Dr. Barry M Cook; Paul Walker. "Ethernet sobre SpaceWire: problemas de software" . 2007. pág. 2.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]