Conmutación vermiforme

La técnica de conmutación o encaminamiento vermiforme (en inglés: «Wormhole Switching») es un sistema básico de control de flujo en redes con conexiones punto a punto estáticas. Se propuso para mejorar el rendimiento en sistemas multicomputadores, segmentando el camino entre los nodos origen y destino de modo que cada paquete pudiera transferirse por varios componentes de la red al mismo tiempo. Cada nodo integra un conmutador que decide qué camino tomará el paquete en su viaje por la red.^[1]​

En rigor, conmutación es un término más adecuado que encaminamiento. El encaminamiento o "enrutamiento" consiste en planear la ruta o itinerario a seguir por un paquete de datos para alcanzar el punto de destino. En el modelo vermiforme no se planifica la ruta entre el origen y el destino, tan solo se decide por qué canal deberá salir el paquete en cada etapa del recorrido.^[2]​

Características

Descripción

Los paquetes de red se dividen en unidades más pequeñas llamadas flits (de «flow control units»). La unidad de transferencia entre interfaces (nivel de red del modelo OSI) es el paquete, mientras que la unidad de transferencia entre conmutadores (nivel de enlace) es el flit. El primer flit, llamado "flit de cabecera", porta información relativa a la ruta del paquete (concretamente la dirección de destino) y configura el encaminamiento para los demás flits asociados al paquete. El flit de cabecera es seguido por los flits restantes, que son los que transportan el contenido del mensaje (ver vídeo). El último flit, llamado "flit de cola", se encarga de cerrar la conexión entre los dos nodos. De todo lo anterior se deduce que los recursos de red (buffer y enlaces) se asignan a nivel de flit.^[1]​

La conmutación virtual cut-through adopta un enfoque similar. La principal diferencia radica en que el control de flujo cut-through asigna almacenamiento (buffers) y ancho de banda a nivel de paquete, mientras que el control de flujo vermiforme hace lo propio a nivel de flit. En la mayoría de los aspectos, vermiforme funciona de manera similar al redireccionamiento ATM o MPLS, con la salvedad de que en ATM las celdas no tienen que pasar por una cola de espera.^[2]​

Una característica especial del control de flujo vermiforme es la implementación de canales virtuales, donde cada puerto de entrada o salida proporciona múltiples canales virtuales.

Un canal virtual se encarga de coordinar el direccionamiento de los flits de un paquete a través de un canal. Como mínimo, identifica el canal de salida del nodo actual para el siguiente salto de la ruta y el estado del canal virtual (ocioso, en espera o activo). El canal virtual puede asimismo incluir punteros a los flits del paquete que se almacenan en el nodo actual y el número de buffers disponibles en el próximo nodo.

(Dally y Towles 2004, pg. 237)

Funcionamiento

Una vez que el conmutador recibe la cabecera del paquete con la información sobre el nodo destino, pone en marcha el algoritmo de encaminamiento. Por lo general, la cabecera del paquete equivale a un solo flit. Una vez encaminado el flit de cabecera, los demás flits llegan en orden a cada conmutador, siguiendo la ruta del flit de cabecera. De este modo, la cabecera va abriendo el camino que luego cierra el flit de cola. Así, el paquete se mueve hacia su destino ofreciendo una imagen que recuerda al movimiento elástico de un gusano ("movimiento vermiforme"), de ahí el nombre de esta técnica.^[1]​

En cada instante de tiempo, el paquete se está transfiriendo por múltiples canales de la red simultáneamente. El camino a recorrer por los flits del paquete se segmenta en etapas. Cada etapa está demarcada por un espacio de almacenamiento (buffer) a la entrada o la salida de un conmutador. Si cada conmutador dispone de almacenamiento tanto en las entradas como en las salidas, en unas etapas del cauce se atraviesa el conmutador y en otras el enlace. A mayor número de etapas, mayor eficiencia en el uso de los recursos de red por parte de cada paquete, lo que redunda en una mejor latencia de transporte.

Prestaciones

Latencia de transporte

Considerando que tenemos almacenamiento solo en las entradas de los conmutadores, y que el tiempo de transferencia por un enlace (${\displaystyle t_{w}}$ ) es siempre uniforme, la latencia de transporte en conmutación vermiforme viene dada por la siguiente expresión:^[1]​

(1)${\displaystyle t_{V}=\left[t_{w}+D\cdot (t_{r}+t_{s}+t_{w})\right]+\left[(t_{s}+t_{w})\left\lceil {\frac {L}{W}}\right\rceil \right]}$ 

(2)${\displaystyle t_{V}=t_{cabecera}+t_{datos}}$ 

Donde:

• ${\displaystyle t_{r}\;:}$  tiempo de encaminamiento (routing) en el conmutador
• ${\displaystyle t_{s}\;:}$  tiempo de transferencia por el conmutador
• ${\displaystyle t_{w}\,:}$  tiempo de transferencia por el enlace
• ${\displaystyle D\,:}$  distancia entre origen y destino
• ${\displaystyle {\frac {L}{W}}:}$  tamaño (en n.º de flits) del paquete

En la expresión simplificada (2) vemos con mayor claridad que hay dos términos. El primer término representa el tiempo que tarda el flit de cabecera en llegar desde el nodo origen hasta el destino, y el segundo, el tiempo que tardan los demás flits en atravesar la última etapa conmutador-enlace. La principal ventaja de esta técnica es que las distintas unidades en que se divide el mensaje pueden transferirse al mismo tiempo, siguiendo el mismo camino. Sin embargo, un posible contratiempo es que los paquetes de poca longitud pueden verse notablemente penalizados si se producen bloqueos causados por paquetes largos.

Ancho de banda global

El ancho de banda global de una red depende del número de canales que puedan estar transfiriendo información simultáneamente. Este número dependerá de la cantidad de enlaces que ocupe un paquete bloqueado; estos enlaces no podrán transferir datos mientras dure el bloqueo, lo que mermará la productividad global de la red. Si en un momento dado un paquete no puede acceder a un recurso (i.e. el puerto de salida del conmutador por el que debe encaminarse), se bloquea. Esto implica que un cierto número de enlaces quedarán ocupados por el paquete bloqueado, permaneciendo inutilizados mientras dure el bloqueo. Estos enlaces ocupados pueden a su vez provocar el bloqueo de otros paquetes y, en última instancia, causar un bloqueo en cadena y saturar la red. El problema se debe a un espacio insuficiente de almacenamiento en los conmutadores, de uno a unos pocos flits.^[2]​ Nótese que, con un almacenamiento en cada puerto de entrada mínimo (1 flit), un paquete puede ocupar tantos enlaces como flits tenga desde el punto de bloqueo hasta el nodo fuente. No obstante, el uso de canales virtuales permite mejorar significativamente las prestaciones (latencia, ancho de banda global) en conmutación vermiforme, incluso en implementaciones donde la asignación de recursos se realiza a nivel de paquete. La combinación de esta técnica con canales virtuales permite además un uso más eficiente del espacio de almacenamiento en los conmutadores.

Coste

Suponiendo un buffer independiente para cada entrada, la técnica vermiforme permite conmutadores de menor coste que en técnicas donde se asigna almacenamiento a nivel de paquete (cut-through, store-and-forward), ya que comparativamente los buffers asociados a cada canal son de inferior tamaño (múltiplo de flit, en lugar de múltiplo de paquete).

Ventajas

• La conmutación vermiforme hace un uso más eficiente del espacio de almacenamiento intermedio (buffers) que la variante Cut-through.^[2]​ Los requerimientos de almacenamiento en los conmutadores se reducen al precisar buffers a escala de flit, en lugar de a escala de paquete.
• No necesita almacenar el paquete completo en el buffer para empezar a transmitir, lo que aumenta el rendimiento.
• El ancho de banda y la asignación de canales se gestionan por separado.

Usos

Las técnicas del modelo de conmutación vermiforme son ampliamente usadas en sistemas multiprocesadores, especialmente en redes de topología hipercúbica. En un sistema de hipercubo cada nodo (CPU) se conecta con un conjunto de nodos vecinos, siguiendo una pauta que minimiza el número de saltos o enlaces entre dos nodos cualesquiera. Cada nodo se identifica por un número (normalmente de 8 o 16 bits) que representa su dirección dentro de la red. Los paquetes destinados a cada CPU incluyen el número correspondiente en su cabecera. Cuando un paquete en tránsito llega a un nodo intermedio, éste examina la cabecera del paquete, determina por qué canal debe reenviarlo hasta el siguiente nodo y luego se desentiende de él. Este esquema reduce sensiblemente la latencia (retardo) en la transmisión con respecto al enfoque de "almacenamiento y reenvío" («Store-and-forward»), que requiere esperar a obtener el paquete completo antes de poder retransmitirlo al siguiente nodo.^[1]​

Más recientemente, la conmutación vermiforme ha demostrado su utilidad en sistemas de tipo «Network-on-Chip» (NOC), conformados por procesadores multinúcleo del mismo tipo. Estos sistemas integran varios núcleos (cores) de procesamiento –o, a más bajo nivel, varias unidades funcionales– que pueden conectarse en red dentro de un mismo circuito integrado (IC). En la medida en que los retardos de transmisión y otros límites no escalables lastran el rendimiento de los sistemas multiprocesadores, es preciso diseñar redes de interconexión más y más eficientes, donde las técnicas de conmutación tienen un papel determinante en cuanto al tiempo de latencia y el ancho de banda global obtenidos.^[1]​

Referencias

1. ORTEGA, Julio; ANGUITA, Mancia; PRIETO, Alberto (2005). Arquitectura de computadores. Paraninfo. pp. 468-474. ISBN 9788497322744. 
2. «Wormhole Switching». Techopedia (en inglés). Consultado el 30 de julio de 2013. 

Véase también

• Técnicas de conmutación
• Almacenamiento y reenvío
• Conmutación virtual cut-through

Bibliografía

• ORTEGA, JULIO et al (2005). Arquitectura de computadores. Paraninfo. ISBN 9788497322744. 

•   Datos: Q8036869