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 de computadoras basado en enlaces fijos conocidos. Es un subconjunto de métodos de control de flujo llamado Flit-Buffer Flow Control. [1] : Capítulo 13.2.1
El cambio es un término más apropiado que el 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 al destino, pero decide cuándo el paquete avanza desde un enrutador.
La conmutación por agujero de gusano se usa ampliamente en multicomputadoras debido a su baja latencia y pequeños requisitos en los nodos. [3] : 376
El enrutamiento de agujero de gusano admite la entrega garantizada de muy baja latencia , alta velocidad y paquetes adecuados 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 pedazos llamados flits (unidades de control de flujo).
Por lo general, los primeros movimientos, llamados movimientos 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 movimientos posteriores asociados con el paquete. Los movimientos del encabezado son seguidos por cero o más movimientos del cuerpo que contienen la carga útil real de datos. Algunos movimientos finales, llamados movimientos de cola, realizan cierta contabilidad para cerrar la conexión entre los dos nodos.
En la conmutación por agujero de gusano, cada búfer está inactivo o asignado a un paquete. Un encabezado se puede reenviar a un búfer si este búfer está inactivo. Esto asigna el búfer al paquete. Se puede reenviar un flit de cuerpo o remolque a un búfer si este búfer está asignado a su paquete y no está lleno. El último movimiento libera el búfer. Si el encabezado se bloquea en la red, el búfer se llena y, una vez que está lleno, no se pueden enviar más movimientos: este efecto se llama "contrapresión" y se puede propagar de regreso a la fuente.
El nombre "agujero de gusano" se reproduce en 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 revoloteo a revoloteo, puede ocupar varios búferes de revoloteo a lo largo de su trayectoria, creando una imagen parecida a un gusano.
Este comportamiento es bastante similar a la conmutación de corte , [5] comúnmente llamado "corte virtual", la principal diferencia es que el control de flujo de corte 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 en el nivel de revoloteo.
En caso de dependencia circular, esta contrapresión puede conducir a un punto muerto.
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 sobre el control de flujo de agujeros de gusano es la implementación de canales virtuales:
Un canal virtual mantiene el estado necesario para coordinar el manejo de los movimientos de un paquete en 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 movimientos del paquete que están almacenados en el nodo actual y el número de búferes disponibles en el siguiente nodo. [1] : 237
Ejemplo
Considere la red 2x2 de la figura de la derecha, con 3 paquetes para enviar: uno rosa, hecho de 4 flits, 'UVWX', de C a D; uno azul, formado por 4 pulsos 'abcd', de la A a la F; y uno verde, formado por 4 flits 'ijkl', de E a H. Suponemos que el enrutamiento se ha calculado, como se dibujó, e implica un conflicto de búfer, en el enrutador inferior izquierdo. El rendimiento es de un movimiento por unidad de tiempo.
Primero, considere el flujo rosa: en el momento 1, la 'U' revoloteante se envía al primer búfer; en el momento 2, el revoloteo 'U' pasa por el siguiente búfer (asumiendo que el cálculo de la ruta no lleva tiempo), y el revoloteo '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 movimientos, 'i' y 'a'.
- Tiempo 2: El flit 'i' puede pasar al siguiente búfer. Pero un búfer está dedicado a un paquete desde el primero hasta el último, por lo que no se puede reenviar el "a". Este es el comienzo de un efecto de contrapresión . El revoloteo 'j' puede reemplazar al revoloteo 'i'. Se puede enviar el revoloteo 'b'.
- Hora 3: El paquete verde continúa. El revoloteo azul 'c' no se puede reenviar (el búfer está ocupado con los movimientos 'b' y 'a'): este efecto de contrapresión llega a la fuente del paquete.
- Tiempo 4: como en el tiempo 3
- Hora 5: el paquete verde ya no usa el búfer de izquierda hacia abajo. El paquete azul está desbloqueado y se puede reenviar (asumiendo que la información 'desbloqueada' se puede reenviar en tiempo nulo)
- Tiempo 6-10: el paquete azul pasa por la red.
Ventajas
- El control de flujo del agujero de gusano hace un uso más eficiente de los amortiguadores que el corte. Cuando el corte requiere muchos paquetes de espacio de búfer, el método del agujero de gusano necesita muy pocos búferes de flit (comparativamente).
- 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 agujero de gusano se utilizan principalmente en sistemas multiprocesador , especialmente en los hipercubos . En una computadora 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 solo de 8 bits 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), configura un circuito para el siguiente enrutador y luego se retira de la conversación. Esto reduce la latencia (retraso) notablemente en comparación con la conmutación de almacenamiento y reenvío que espera todo el paquete antes de reenviarlo. Más recientemente, el control de flujo de agujeros de gusano ha encontrado su camino hacia aplicaciones en sistemas Network On Chip (NOC), de los cuales los procesadores de múltiples núcleos son una de las variedades. Aquí, muchos núcleos de procesador, o en un nivel inferior, incluso las unidades funcionales se pueden conectar en una red en un solo paquete IC . 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 un agujero de gusano.
Canales virtuales
Una extensión de control de flujo de agujero de gusano es Virtual-Canal de control de flujo , donde varios canales virtuales pueden ser multiplexados a través de un canal físico. Cada canal virtual unidireccional se realiza mediante un par de búferes (flit) gestionados de forma independiente. A continuación, distintos paquetes pueden compartir el canal físico paso a paso. Los canales virtuales se introdujeron originalmente para evitar el problema del interbloqueo, pero también se pueden usar para reducir el bloqueo de agujeros de gusano, mejorando la latencia y el rendimiento de la red. El bloqueo de agujeros de gusano ocurre cuando un paquete adquiere un canal, evitando así que otros paquetes usen el canal y forzándolos a detenerse. Suponga 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á hasta que se complete la transmisión de P0. Si se implementan canales virtuales, son posibles las siguientes mejoras:
- A la llegada de P1, el canal físico se puede multiplexar entre ellos paso a paso, de modo que ambos paquetes avancen a la mitad de la velocidad (dependiendo del esquema de arbitraje).
- Si P0 es un paquete de longitud completa mientras que P1 es solo un pequeño paquete de control del tamaño de unos pocos movimientos, entonces este esquema permite que P1 pase a través de 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.
- Suponga 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 la cola de salida virtual para reducir el bloqueo de la cabecera de línea .
Enrutamiento
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 usa 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 está en el rango de 1 a 31, indica el puerto correspondiente 1 a 31 del conmutador Spacewire. El conmutador SpaceWire luego descarta 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]
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 usa ese valor como índice en una tabla de enrutamiento interna que indica qué puerto (s) enviar el paquete y si eliminarlo. o retener ese primer byte. [7]
La dirección 0 se utiliza para comunicarse directamente con el conmutador y se puede utilizar para configurar las entradas de la tabla de enrutamiento para ese conmutador. [7]
Ver también
Referencias
- ^ a b 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 computadora: un enfoque cuantitativo (Cuarta ed.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0.
- ^ a b Mohapatra, Prasant (1998), "Técnicas de enrutamiento de agujeros de gusano para sistemas multicomputadores conectados directamente" (PDF) , Encuestas de computación ACM , 30 (3): 374–410, CiteSeerX 10.1.1.11.9098 , doi : 10.1145 / 292469.292472
- ^ Sharad Sundaresan; Riccardo Bettati. "Gestión de conexión distribuida para comunicación en tiempo real a través de redes enrutadas por agujeros de gusano" . 1997.
- ^ Stefan Haas. "El estándar IEEE 1355: desarrollos, rendimiento y aplicación en física de altas energías" . 1998. p. 59.
- ^ Pavel Tvrdik. "Por qué el enrutamiento de agujeros de gusano es una técnica de conmutación importante"
- ^ a b c d Dr. Barry M Cook; Paul Walker. "Ethernet sobre SpaceWire - problemas de software" . 2007. p. 2.