El control de flujo de agujero de gusano , también llamado conmutación de agujero de gusano o enrutamiento de 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 llamado control de flujo de búfer flotante . [1] : Capítulo 13.2.1
Conmutación es un término más apropiado que enrutamiento, ya que "enrutamiento" define la ruta o camino tomado para llegar al destino. [2] [3] La técnica del agujero de gusano no dicta la ruta al destino, sino que decide cuándo avanza el paquete desde un enrutador.
La conmutación de agujeros de gusano se utiliza ampliamente en multicomputadoras debido a su baja latencia y pequeños requisitos en los nodos. [3] : 376
El enrutamiento de agujero de gusano permite una entrega garantizada, de alta velocidad y con muy baja latencia , de paquetes adecuados para la comunicación en tiempo real . [4]
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).
Por lo general, los primeros flits, llamados flits de encabezado, contienen información sobre la ruta de este paquete (por ejemplo, la dirección de destino) y configuran el comportamiento de enrutamiento para todos los flits posteriores asociados con el paquete. Los flits de encabezado son seguidos por cero o más flits de cuerpo que contienen la carga útil real de datos. Algunos flits finales, llamados flits de cola, realizan cierta contabilidad para cerrar la conexión entre los dos nodos.
En la conmutación por agujeros de gusano, cada búfer está inactivo o asignado a un paquete. Un flit de encabezado se puede reenviar a un búfer si este búfer está inactivo. Esto asigna el búfer al paquete. Un flit de cuerpo o de final se puede reenviar a un búfer si este búfer está asignado a su paquete y no está lleno. El último flit libera el búfer. Si el flit de encabezado está bloqueado en la red, el búfer se llena y, una vez lleno, no se pueden enviar más flits: este efecto se llama "contrapresión" y se puede propagar de vuelta a la fuente.
El nombre "agujero de gusano" hace referencia a la forma en que se envían los paquetes a través de los enlaces: la dirección es tan corta que se puede traducir antes de que llegue el mensaje. Esto permite al enrutador configurar rápidamente el enrutamiento del mensaje real y luego "retirarse" del resto de la conversación. Dado que un paquete se transmite paso a paso, puede ocupar varios buffers de paso a paso a lo largo de su recorrido, 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", la principal diferencia es que el control de flujo de corte directo asigna buffers 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 llevar a un bloqueo.
En la mayoría de los aspectos, el agujero de gusano es muy similar al reenvío ATM o MPLS , con la excepción de que la celda no tiene que estar en cola .
Una cosa 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, en espera de recursos o activo). El canal virtual también puede incluir punteros a los flits del paquete que se almacenan en el búfer del nodo actual y la cantidad de búferes de flits disponibles en el siguiente nodo. [1] : 237
Consideremos la red 2x2 de la figura de la derecha, con 3 paquetes a enviar: uno rosa, compuesto de 4 flits, 'UVWX', de C a D; uno azul, compuesto de 4 flits 'abcd', de A a F; y uno verde, compuesto de 4 flits 'ijkl', de E a H. Suponemos que el enrutamiento se ha calculado, tal como se ha dibujado, e implica un conflicto de un búfer, en el enrutador inferior izquierdo. El rendimiento es de un flit por unidad de tiempo.
Primero, considere el flujo rosa: en el momento 1, el flit 'U' se envía al primer búfer; en el momento 2, el flit 'U' pasa por el siguiente búfer (asumiendo que el cálculo de la ruta no toma 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:
Las técnicas de agujero de gusano se utilizan principalmente en sistemas multiprocesador , en particular en hipercubos . En un ordenador hipercubo, cada CPU está conectada a varios vecinos en un patrón fijo, lo que reduce el número de saltos de una CPU a otra. A cada CPU se le asigna un número (normalmente de sólo 8 a 16 bits ), que es su dirección de red, y los paquetes a las CPU se envían con este número en el encabezado. Cuando el paquete llega a un enrutador intermedio para su reenvío, el enrutador examina el encabezado (muy rápidamente), establece un circuito hacia el siguiente enrutador y luego se retira de la conversación. Esto reduce la latencia (retardo) notablemente en comparación con la conmutación de almacenamiento y reenvío que espera a que se complete el paquete antes de reenviarlo. Más recientemente, el control de flujo de agujero de gusano ha encontrado su camino hacia aplicaciones en sistemas de red en chip (NOC), de los cuales los procesadores multinúcleo son una variante. Aquí, muchos núcleos de procesador, o en un nivel inferior, incluso unidades funcionales se pueden conectar en una red en un único paquete de CI . A medida que los retrasos en los cables y muchas otras restricciones no escalables en los elementos de procesamiento vinculados 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 juegan un papel importante.
Las tecnologías IEEE 1355 y SpaceWire utilizan agujeros de gusano.
Una extensión del control de flujo de agujero de gusano es el control de flujo de canal virtual , en el que varios canales virtuales pueden multiplexarse en un canal físico. Cada canal virtual unidireccional se realiza mediante un par de buffers (flit) gestionados de forma independiente. A continuación, distintos paquetes pueden compartir el canal físico en cada uno de los casos. Los canales virtuales se introdujeron originalmente para evitar el problema del bloqueo, pero también se pueden utilizar para reducir el bloqueo de agujero de gusano, mejorando la latencia y el rendimiento de la red. El bloqueo de agujero de gusano se produce cuando un paquete adquiere un canal, lo que impide que otros paquetes utilicen el canal y los obliga a detenerse. Supongamos que un paquete P0 ha adquirido el canal entre dos enrutadores. En ausencia de canales virtuales, un paquete P1 que llegue más tarde se bloquearía hasta que se haya completado la transmisión de P0. Si se implementan canales virtuales, son posibles las siguientes mejoras:
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 línea .
Se puede utilizar una combinación de enrutamiento de origen y enrutamiento lógico en el mismo paquete conmutado por agujero de gusano. 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]
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 está en el rango de 1 a 31, indica el puerto correspondiente 1 a 31 del conmutador SpaceWire. El conmutador SpaceWire descarta entonces ese carácter de enrutamiento y envía el resto del paquete por 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]
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 usarse para configurar las entradas de la tabla de enrutamiento para ese conmutador. [7]