Conmutación de Redes: Tipos, Arquitecturas y Planificación

Conmutación: Conceptos Básicos

Una red es un conjunto de dispositivos conectados. Si hay múltiples dispositivos a conectar, es más complicado establecer la comunicación uno a uno. Posibles soluciones son las topologías de malla o estrella, pero resultan demasiado costosas en redes muy grandes. Una alternativa mejor es la conmutación, ya que ofrece la interconexión dinámica entre entradas y salidas y la compartición dinámica de los recursos de transmisión. Un conmutador es una máquina capaz de crear conexiones temporales entre dos o más dispositivos conectados a él.

Tipos de Conmutación

Conmutación de Circuitos

Una red de conmutación de circuitos está formada por un conjunto de conmutadores conectados por enlaces físicos. Cada uno de estos enlaces consta de n canales FDM o TDM. La conexión entre dos estaciones es un camino dedicado formado por n canales de cada uno de los enlaces involucrados. La comunicación entre estaciones pasa por tres fases:

1. Establecimiento de la conexión (se reserva un circuito a cada enlace hasta formar el camino).
2. Transferencia de datos.
3. Liberación de la conexión (los circuitos previamente reservados quedan libres).

Se realiza a nivel físico. Al establecer el circuito no solo se reserva el canal, también otros recursos como buffers, tiempo de procesamiento, puertos de entrada y salida. Estos recursos permanecen dedicados hasta su liberación. La transferencia de datos se realiza en forma de flujo continuo, no es una transferencia de paquetes. No se usa direccionamiento durante la fase de transferencia de datos, pero sí durante la fase de establecimiento.

Conmutación de Paquetes

La transferencia de información se realiza convirtiéndola en paquetes de datos. El tamaño de los paquetes depende de la red y el protocolo que la gobierna. No se realiza ninguna asignación de recursos para el paquete, es decir, no se reserva capacidad de transmisión ni tiempo de procesamiento. La política de asignación más habitual es "el primero que llega es el primero servido". La falta de asignación de recursos puede provocar retardos aleatorios y posibles pérdidas de paquetes. Se realiza normalmente a nivel de red. Los paquetes llevan un mismo mensaje, pero pueden viajar por rutas diferentes, por ejemplo, si el encaminador no dispone de ancho de banda. Las redes de datagramas también se llaman redes no orientadas a conexión.

Tablas de Enrutamiento

Cada conmutador dispone de una propia. Las tablas son dinámicas y se actualizan periódicamente. Cada entrada de la tabla contiene la dirección de destino y el puerto de salida del encaminador. Cada paquete contiene la dirección de destino dentro de la cabecera.

Conmutación de Circuitos Virtuales

La conmutación de circuitos virtuales es una mezcla entre la conmutación de circuitos y la conmutación de paquetes. Consta de las tres fases de la conmutación de circuito. Los recursos pueden asignarse durante el establecimiento o bajo demanda. Los datos se dividen en paquetes y cada paquete contiene una dirección en la cabecera, pero la dirección solo es válida en un enlace. Todos los paquetes siguen el mismo camino, establecido al inicio de la conexión. Suele establecerse a nivel de enlace. Cada origen y destino requiere de una dirección única dentro de la red, pero esta dirección solo se usa durante la fase de establecimiento del circuito. Los paquetes utilizan un identificador de circuito virtual (VCI) válido solo entre dos conmutadores. El VCI es un valor pequeño que requiere mucho menos espacio de cabecera que un identificador global. Los VCI de entrada y salida los deciden los conmutadores durante la fase de establecimiento del circuito. Tanto la fase de establecimiento de la conexión como la liberación son confirmadas por el receptor. Durante la fase de transferencia, la información dividida en paquetes se transmite "bote a bote" a través de la red de conmutadores. A diferencia de la conmutación de paquetes, todos los paquetes siguen la misma ruta.

Arquitecturas de Conmutadores

Conmutador de Barras Cruzadas (Crossbar)

Un conmutador de barras cruzadas es una matriz de NxM conexiones que permiten conectar cualquier entrada con cualquier salida. Son no bloqueantes, es decir, no se niegan peticiones de conexión entre una entrada libre y una salida libre. Los primeros conmutadores Crossbar eran de dos entradas y dos salidas. Posteriormente se ampliaron para permitir un mayor número de conexiones. La complejidad es N². Presentan un elevado rendimiento gracias a que los enlaces entre entrada y salida son simples enlaces punto a punto que pueden operar a gran velocidad y la estructura permite múltiples conexiones simultáneas entre puertos de entrada y salida. El rendimiento se ve reducido cuando los puertos de entrada no tienen datos a transmitir o varias líneas de entrada quieren transmitir sobre la misma salida. Sus ventajas son una implementación sencilla y modular, soporte nativo de la multidifusión y latencia de la ruta entrada-salida menor que la que presentan otros conmutadores. Inconvenientes: coste medido en puntos de cruce, dificultades para ofrecer calidad de servicio garantizada, cada punto de cruce es único y por tanto sensible a fallos, planificación complicada si debe soportar multidifusión.

Conmutadores Multietapa

Un conmutador multietapa está compuesto por tres etapas de conmutadores más pequeños. La estructura de un conmutador NxN es:

• Primera etapa: N/n conmutadores de nxk puntos de conexión.
• Segunda etapa: k conmutadores de N/nxN/n puntos de conexión.
• Tercera etapa: N/n conmutadores de kxn puntos de conexión.

Pueden ser bloqueantes.

Redes de Clos

Charles Clos investigó las condiciones para conseguir un conmutador multietapa no bloqueante. Una red de Clos(m,n,r) es no bloqueante si m ≥ 2n-1. Donde:

• M: número de conmutadores de la etapa intermedia.
• N: número de entradas (salidas) de cada conmutador de entrada (salida).
• R: número de conmutadores de entrada o salida.

Conmutación por División del Tiempo

La técnica del intercambio de partes de tiempo (TSI) sustituye los puntos de cruce de los conmutadores en el espacio para lecturas y escrituras en memoria a partir de tramas temporales TDM.

Conmutación Tiempo-Espacio-Tiempo (TST)

Para minimizar el retardo que introducen los conmutadores de tiempo y el número de cruces necesarios en los conmutadores en el espacio, se pueden combinar las dos tecnologías.

Estructura de un Conmutador

Un conmutador típico consta de los siguientes componentes:

• Interfaz de entrada al tejido: conecta el procesador de paquetes de entrada al tejido de conmutación. Coordina con el planificador la presencia de paquetes. Si hace falta, segmenta los paquetes de tamaño variable en paquetes de tamaño fijo, permite la transmisión de acuerdo con el planificador.
• Buffers de entrada al tejido: almacén temporal de paquetes si el tejido de conmutación no puede procesarlos inmediatamente, reduce las pérdidas de paquetes durante el tráfico a ráfagas.
• Tejido de conmutación: transfiere datos de una línea de entrada a una de salida. Conecta de forma dinámica las diferentes tarjetas para disponer de las rutas necesarias, el planificador es el que identifica las rutas.
• Interfaz de salida del tejido: recibe el tráfico del tejido de conmutación y lo pasa al procesador de salida, conecta con el planificador la recepción de los paquetes, si hace falta reensambla los paquetes divididos para volver al tamaño original. Coordina la transmisión de los paquetes con el planificador de salida, considerando los requerimientos de prioridades y calidad del servicio.
• Buffers de salida del tejido: guarda los paquetes pendientes de transmisión. Muchos encaminadores presentan las interfaces de entrada y salida en un mismo chip residente en la tarjeta de línea.

Requerimientos

• Maximizar la cantidad de datos transferidos a través del tejido de conmutación.
• El tejido debe permitir la transferencia simultánea desde diferentes tarjetas.
• Ancho de banda equitativo para todas las tarjetas de línea (incluso con sobrecargas, no se debe robar ancho de banda a otras tarjetas).
• No se deben reordenar los paquetes (si se reordenan paquetes se introducen retardos que obligan a imponer requerimientos de prioridad).
• Redundancia para permitir fallos que no impidan la continuidad del servicio (hay que recordar que el tejido de conmutación es un componente crítico de un encaminador, y sin él no funciona).

Métricas de Rendimiento

El rendimiento de un tejido de conmutación depende de diversos factores como son la arquitectura interna, el tipo de tráfico, etc. Las métricas que suelen usarse son:

• Throughput: determina la cantidad de datos que pueden transferirse por unidad de tiempo.
• Latencia: el tiempo necesario para atravesar el tejido. Formalmente la latencia se mide entre puertos de entrada y salida, pero uno de los factores que interviene en ella es el tejido de conmutación.
• Diversidad de caminos: número de caminos disponibles entre cada par entrada-salida. Si dispone de más de una ruta, es más robusto y puede repartir la carga entre ellas.

Placas de Interconexión

Placas de Interconexión Compartidas

Son aquellas placas que utilizan un medio compartido para transferir paquetes de una tarjeta de línea a otra. Por ejemplo, bus o anillo. Son muy económicos, pero con un throughput limitado.

Bus Compartido

Un bus conecta una serie de puertos mediante un canal compartido que sirve de medio de difusión. Cuando un paquete se transmite, todos los puertos lo reciben. Dependiendo de si son los destinatarios o no, lo aceptan o lo ignoran. Un protocolo permite decidir qué puerto es el que dispone del permiso de transmisión en cada instante. Implementa la multidifusión y difusión de forma natural, sin más gastos. Solo transmite un puerto, por tanto, no hay que reorganizar paquetes a las tarjetas de destino. Si cada puerto conectado al bus puede transmitir a R bit/s, un bus con N tarjetas deberá operar a RN bit/s. Si el bus opera con una frecuencia de reloj de r Hz, el ancho del bus (w) deberá ser, como mínimo, de RN/r bit. A medida que la capacidad de las CPU aumenta, el cuello de botella de los encaminadores de bus compartido es el propio bus. Otro inconveniente es que el aumento de la carga eléctrica debida a un incremento en el número de puertos provoca que la frecuencia de reloj deba reducirse y se deba incrementar el ancho del bus. Supón un encaminador de bus compartido con 16 puertos que operan a 100 Mbit/s, el ancho de banda del bus será de 1.6 Gbit/s, si el reloj interno tiene una frecuencia interna de 40 MHz, hará falta que el bus tenga un ancho de 40 bit.

Placas de Interconexión Conmutadas

Permiten la transferencia simultánea entre diferentes tarjetas de línea. Un componente muy importante de este tipo de placas es el planificador. Es el que decide qué puertos de entrada transmiten sus paquetes y a qué puertos de salida lo hacen. Como los paquetes IP presentan longitudes variables, el diseño de un planificador es complicado y puede provocar situaciones de postergación indefinida y reducción del throughput. Por tanto, habitualmente, los paquetes se descomponen en fragmentos de igual tamaño antes de atravesar el tejido de conmutación. Eso sucede en lo que se conoce como una ranura temporal. Las placas de interconexión conmutadas incluyen las formadas por memoria compartida, barras cruzadas, redes de Clos, redes de Benes o redes toroidales.

Memoria Compartida

La implementación más sencilla de una placa de interconexión conmutada es la basada en una memoria compartida entre puertos de entrada y salida. La memoria está dividida en varias colas asignadas a un puerto de salida, el paquete de entrada se añade directamente a la cola de salida. Las particiones pueden ser iguales o flexibles. Las memorias actuales no alcanzan los requisitos necesarios (el ancho de banda de memoria necesaria de un conmutador de N puertos de entrada con líneas de R bit/s es 2NR, el tiempo de acceso de las memorias es muy superior al necesario. A medida que aumenta la tasa de transmisión de las líneas, la memoria debe aumentar). Velocidad del controlador: el tiempo para decidir la cola de cada paquete y activar las señales de control necesarias debe ser muy corto.

Algoritmos de Planificación

Take a Ticket

Funcionamiento similar al de algunos bares donde primero pagamos la comanda y luego esperamos el aviso para recogerla. Cada puerto de salida Q mantiene una cola con todos los puertos de entrada P que desean transmitir a través de Q. Realmente la cola se implementa en cada puerto P donde se guarda el turno asignado por la cola Q.

Algoritmo:

1. Petición: cada puerto de entrada envía una petición al puerto de salida correspondiente en la celda de la cabecera de cola.
2. Concesión: el puerto de salida recibe las peticiones y asigna un tique de acuerdo al orden de llegada de las peticiones.
3. Conexión de transferencia: el puerto de salida comunica su disponibilidad comunicando un tique a través del bus de control. El puerto de entrada que será servido inicia el flujo de datos correspondiente.

Ventajas:

• Habilitado para gestionar paquetes de diferentes longitudes.
• No hay dependencias entre puertos y funciona asíncronamente.
• Utiliza poca memoria para mantener el estado, tiene dos contadores log₂N bit en cada puerto de salida (número del tique servido, número del último tique asignado).

Inconvenientes:

• El bloqueo de cabecera de línea reduce el nivel de paralelismo y por tanto el throughput del conmutador.
• Como la planificación de cada puerto de salida es independiente, su coordinación por multidifusión es muy complicada.

Colas de Salida

Si las colas pasan a la salida, los paquetes pueden enviarse directamente a la cola correspondiente, y se elimina el bloqueo de cabecera. Si todos los puertos de entrada reciben paquetes destinados a la misma salida, estos se deberán añadir a la cola en el tiempo equivalente a la recepción de un paquete. Por tanto, la red de conmutación y las colas de salida deben trabajar a una tasa N veces superior a la de los puertos de entrada.

Knockout

Este principio permite abaratar el coste de implementar un sistema de N colas de salida. El principio dice que es muy poco probable que las N entradas reciban simultáneamente un paquete direccionado al mismo puerto de salida. Por tanto, si S < N colas de salida son suficientes para garantizar una probabilidad de pérdida de paquetes muy baja.

Colas de Salida Virtuales

Para evitar el bloqueo de cabecera de línea hay que planificar sobre todos los paquetes de todos los puertos de entrada. Realmente basta hacerlo sobre los primeros paquetes destinados a cada cola de salida en cada una de las colas de entrada. El efecto es similar a considerar que cada cola de entrada está dividida en tantas colas como puertos de salida tiene el conmutador. El sistema de colas virtual complica considerablemente el proceso de planificación, por tanto, se han desarrollado algoritmos específicos (PIM, iSLIP).

Maximum vs Maximal Matching

• Máximo (Maximum): aquel que empareja el máximo número posible de puertos de entrada con los de salida.
• Maximal: aquel emparejamiento que no permite añadir nuevas parejas fácilmente. Cada puerto de entrada está emparejado con uno de salida o no puede emparejarse.

Maximum es maximal, pero maximal no siempre es máximo.

Parallel Iterative Matching (PIM)

La idea fundamental es usar la aleatoriedad para encontrar un aparejamiento maximal entre puertos de entrada y salida. Este emparejamiento se consigue a través de varias iteraciones para asegurar que se maximiza el número de transferencias simultáneas en cada caso.

Funcionamiento:

1. Petición: cada puerto de entrada envía una petición en todos los puertos de salida correspondientes a las celdas pendientes.
2. Concesión: el puerto de salida recibe las peticiones y aleatoriamente concede una. Lo notifica al puerto de entrada correspondiente.
3. Aceptación y transferencia: el puerto de entrada acepta una de las concesiones, también aleatoriamente, e informa al puerto de salida correspondiente.

Planificación iSLIP

Pretende resolver los problemas de inecuidad y complejidad del sistema PIM. Permite llegar a emparejamientos maximales en una o dos iteraciones. Elimina las selecciones aleatorias mediante unos punteros rotatorios que determinan el puerto a servir. Se gestionan los contadores:

• I_i: puntero de aceptación al puerto de entrada i. Todos los punteros de aceptación se inicializan al primer puerto de salida. Indica el puerto de salida del que un puerto de entrada debe aceptar la concesión, en caso de recibir varias.
• O_i: puntero de concesión al puerto de salida i. Todos los punteros de concesión se inicializan al primer puerto de entrada. Indica el puerto de entrada al que un puerto de salida debe entregar la concesión, en caso de recibir varias peticiones.

Algoritmo:

1. Petición: cada puerto de entrada envía una petición a cada uno de los puertos de salida para los cuales tiene celdas pendientes.
2. Concesión: el puerto de salida j recibe las peticiones y concede la correspondiente al puerto menor que es igual o mayor que el valor de O_j. Lo notifica al puerto de entrada correspondiente.
3. Aceptación y transferencia: el puerto de entrada i recibe las concesiones y acepta la proveniente del puerto menor que es igual o mayor que I_i. Una vez aceptada, incrementa el valor de I_i e informa al puerto de salida correspondiente que actualiza el valor de O_j.

La actualización de los punteros solo se realiza durante la primera iteración de cada capa. El procedimiento anterior puede repetirse varias iteraciones conservando las concesiones ya asignadas y añadiendo nuevas.

Bloqueo de Entrada y Salida

• Entrada: aparece cuando las diferentes colas de salida virtuales de un puerto de entrada tienen múltiples celdas en espera.
• Salida: aparece cuando varias celdas van destinadas al mismo puerto de salida.

Técnicas para controlar los retardos:

• Dividir los paquetes en diferentes clases de prioridad de acuerdo a los requerimientos de retardo (menor retardo tolerable, mayor prioridad, no elimina bloqueos pero reduce el retardo, hay que modificar los planificadores para que consideren los niveles de prioridad).
• Disponer de un conmutador más rápido que los enlaces de entrada y salida (si el conmutador trabaja S veces más rápido que las líneas externas, puede transferir S celdas durante una ranura temporal. El escenario peor es aquel donde las celdas se deben transmitir para la misma salida, ya que requiere un incremento de velocidad de N veces. No es posible).

Redes de Bañan (Autorruta, Self-routing)

Son redes multietapa formadas por conmutadores 2x2 conectados de tal forma que permiten el autoencaminamiento de los paquetes hacia la dirección que contiene el propio paquete. Así la planificación se puede hacer de forma distribuida.