En el campo de las telecomunicaciones , una red Clos es un tipo de red de conmutación de circuitos de múltiples etapas que representa una idealización teórica de los sistemas de conmutación de múltiples etapas prácticos. Fue inventado por Edson Erwin [1] en 1938 y formalizado por primera vez por el ingeniero estadounidense [2] Charles Clos [3] en 1952.
Al agregar etapas, una red Clos reduce la cantidad de puntos de cruce necesarios para componer un interruptor de barra transversal grande . Una topología de red Clos (diagramada a continuación) está parametrizada por tres números enteros n , m y r : n representa el número de fuentes que alimentan cada uno de los r conmutadores de barra transversal de etapa de ingreso; cada interruptor de barra transversal de etapa de ingreso tiene m salidas; y hay m interruptores de barra transversal de etapa intermedia.
La conmutación de circuitos organiza una ruta de comunicaciones dedicada para una conexión entre puntos finales durante la duración de la conexión. Esto sacrifica el ancho de banda total disponible si las conexiones dedicadas se utilizan mal, pero hace que la conexión y el ancho de banda sean más predecibles y solo introduce una sobrecarga de control cuando se inician las conexiones, en lugar de con cada paquete manejado, como en las redes modernas de conmutación de paquetes .
Cuando se ideó por primera vez la red Clos, el número de puntos de cruce era una buena aproximación del coste total del sistema de conmutación. Si bien esto era importante para las barras transversales electromecánicas, se volvió menos relevante con la llegada de VLSI , en el que las interconexiones se podían implementar directamente en silicio o dentro de un grupo relativamente pequeño de placas. Con la aparición de complejos centros de datos, con enormes estructuras de interconexión, cada una de ellas basada en enlaces de fibra óptica, las redes Clos recuperaron importancia. [4] Un subtipo de red Clos, la red Beneš, también ha encontrado aplicación reciente en el aprendizaje automático . [5]
Las redes Clos tienen tres etapas: la etapa de ingreso, la etapa intermedia y la etapa de salida. Cada etapa se compone de varios interruptores de barra transversal (consulte el diagrama a continuación), a menudo llamados simplemente barras transversales . La red implementa una combinación perfecta de r-way entre etapas. Cada llamada que ingresa a un interruptor de barra transversal de entrada se puede enrutar a través de cualquiera de los interruptores de barra transversal de etapa intermedia disponibles, hasta el interruptor de barra transversal de salida correspondiente. Una barra transversal de etapa intermedia está disponible para una nueva llamada particular si tanto el enlace que conecta el interruptor de entrada al interruptor de etapa intermedia como el enlace que conecta el interruptor de etapa intermedia al interruptor de salida están libres.
Las redes Clos están definidas por tres números enteros n , m y r . n representa el número de fuentes que alimentan cada uno de los r interruptores de barra transversal de etapa de ingreso. Cada interruptor de barra transversal de etapa de ingreso tiene m salidas y hay m interruptores de barra transversal de etapa intermedia. Hay exactamente una conexión entre cada interruptor de etapa de ingreso y cada interruptor de etapa intermedia. Hay interruptores de etapa de regresión, cada uno con m entradas yn salidas . Cada interruptor de etapa intermedia se conecta exactamente una vez a cada interruptor de etapa de salida. Por lo tanto, la etapa de ingreso tiene r interruptores, cada uno de los cuales tiene n entradas ym salidas. La etapa intermedia tiene m interruptores, cada uno de los cuales tiene r entradas y r salidas. La etapa de salida tiene r interruptores, cada uno de los cuales tiene m entradas yn salidas.
Los valores relativos de myn definen las características de bloqueo de la red Clos.
Si m ≥ 2 n −1, la red Clos es sin bloqueo en sentido estricto , lo que significa que una entrada no utilizada en un conmutador de entrada siempre se puede conectar a una salida no utilizada en un conmutador de salida, sin tener que reorganizar las llamadas existentes . Este es el resultado que formó la base del clásico artículo de Clos de 1953. Supongamos que hay un terminal libre en la entrada de un interruptor de ingreso y que este debe conectarse a un terminal libre en un interruptor de salida en particular. En el peor de los casos, n −1 otras llamadas están activas en el conmutador de entrada en cuestión, y n −1 otras llamadas están activas en el conmutador de salida en cuestión. Supongamos, también en el peor de los casos, que cada una de estas llamadas pasa por un conmutador de etapa intermedia diferente. Por lo tanto, en el peor de los casos, 2 n −2 de los conmutadores de la etapa intermedia no pueden transportar la nueva llamada. Por lo tanto, para garantizar una operación sin bloqueo en sentido estricto, se requiere otro interruptor de etapa intermedia, lo que hace un total de 2 n −1.
El siguiente diagrama muestra el peor caso cuando las llamadas ya establecidas (azul y roja) pasan por diferentes interruptores de etapa intermedia, por lo que es necesario otro interruptor de etapa intermedia para establecer una llamada entre la entrada y la salida verdes.
Si m ≥ n , la red Clos se puede reorganizar sin bloqueo , lo que significa que una entrada no utilizada en un interruptor de entrada siempre se puede conectar a una salida no utilizada en un interruptor de salida, pero para que esto suceda, es posible que las llamadas existentes deban reorganizarse asignando a distintos conmutadores centrales de la red Clos. [6] Para probar esto, es suficiente considerar m = n , con la red Clos completamente utilizada; es decir, r × n llamadas en curso. La prueba muestra cómo cualquier permutación de estos r × n terminales de entrada en r × n terminales de salida puede dividirse en permutaciones más pequeñas, cada una de las cuales puede implementarse mediante interruptores de barra transversal individuales en una red Clos con m = n .
La prueba utiliza el teorema del matrimonio de Hall [7], al que se le da este nombre porque a menudo se explica de la siguiente manera. Supongamos que hay r niños y r niñas. El teorema establece que si cada subconjunto de k niños (para cada k tal que 0 ≤ k ≤ r ) entre ellos conoce k o más niñas, entonces cada niño puede emparejarse con una niña que conoce. Es obvio que ésta es una condición necesaria para que se produzca el emparejamiento; lo sorprendente es que sea suficiente.
En el contexto de una red Clos, cada niño representa un interruptor de entrada y cada niña representa un interruptor de salida. Se dice que un niño conoce a una niña si los interruptores de entrada y salida correspondientes llevan la misma llamada. Cada conjunto de k niños debe conocer al menos k niñas porque k conmutadores de ingreso transportan k × n llamadas y éstas no pueden ser transportadas por menos de k conmutadores de salida. Por lo tanto, cada conmutador de entrada se puede emparejar con un conmutador de salida que transporta la misma llamada, mediante una asignación uno a uno. Estas llamadas r pueden ser transportadas por un interruptor de etapa intermedia. Si ahora se elimina este conmutador de etapa intermedia de la red Clos, m se reduce en 1 y nos queda una red Clos más pequeña. Luego, el proceso se repite hasta m = 1, y cada llamada se asigna a un conmutador de etapa intermedia.
Los sistemas de conmutación telefónica reales rara vez son sin bloqueo en sentido estricto por razones de costo, y tienen una pequeña probabilidad de bloqueo, que puede evaluarse mediante las aproximaciones de Lee o Jacobaeus , [8] asumiendo que no hay reordenamientos de las llamadas existentes. Aquí, el número potencial de otras llamadas activas en cada conmutador de entrada o salida es u = n −1.
En la aproximación de Lee se supone que cada enlace interno entre etapas ya está ocupado por una llamada con una cierta probabilidad p , y que esta es completamente independiente entre diferentes enlaces. Esto sobreestima la probabilidad de bloqueo, particularmente para r pequeño . La probabilidad de que un enlace interno determinado esté ocupado es p = uq / m , donde q es la probabilidad de que un enlace de entrada o salida esté ocupado. Por el contrario, la probabilidad de que un enlace esté libre es 1− p . La probabilidad de que la ruta que conecta un conmutador de entrada con un conmutador de salida a través de un conmutador de etapa intermedia en particular esté libre es la probabilidad de que ambos enlaces estén libres, (1− p ) 2 . Por tanto, la probabilidad de que no esté disponible es 1−(1− p ) 2 = 2 p − p 2 . La probabilidad de bloqueo, o la probabilidad de que ningún camino esté libre, es entonces [1−(1− p ) 2 ] m .
La aproximación de Jacobaeus es más precisa y, para ver cómo se deriva, supongamos que ya existe algún mapeo particular de llamadas que ingresan a la red Clos (llamadas de entrada) en conmutadores de etapa intermedia. Esto refleja el hecho de que sólo las configuraciones relativas de los interruptores de entrada y de salida son relevantes. Hay i llamadas de entrada que ingresan a través del mismo interruptor de entrada que el terminal de entrada libre a conectar, y hay j llamadas que salen de la red Clos (llamadas de salida) a través del mismo interruptor de salida que el terminal de salida libre a conectar. Por tanto 0 ≤ i ≤ u y 0 ≤ j ≤ u .
Sea A el número de formas de asignar las j llamadas de salida a los m interruptores de etapa intermedia. Sea B el número de estas asignaciones que resultan en bloqueo. Este es el número de casos en los que los restantes m − j interruptores de etapa intermedia coinciden con m − j de las i llamadas de entrada, que es el número de subconjuntos que contienen m − j de estas llamadas. Entonces la probabilidad de bloqueo es:
Si f i es la probabilidad de que i otras llamadas ya estén activas en el conmutador de entrada, y g j es la probabilidad de que j otras llamadas ya estén activas en el conmutador de salida, la probabilidad de bloqueo general es:
Esto puede evaluarse denotando cada uno de ellos mediante una distribución binomial . Después de una considerable manipulación algebraica, esto puede escribirse como:
Las redes Clos también pueden generalizarse a cualquier número impar de etapas. Al reemplazar cada interruptor de barra transversal de etapa central con una red Clos de 3 etapas, se pueden construir redes Clos de cinco etapas. Aplicando el mismo proceso repetidamente, son posibles 7, 9, 11,... etapas.
Una red reordenable sin bloqueo de este tipo con m = n = 2 generalmente se denomina red Beneš , aunque fue discutida y analizada por otros [ ¿quién? ] ante Václav E. Beneš . El número de entradas y salidas es N = r × n = 2 r . Dichas redes tienen 2 log 2 N − 1 etapas, cada una de las cuales contiene N /2 2 × 2 interruptores de barra transversal, y utilizan un total de N log 2 N − N /2 2 × 2 interruptores de barra transversal. Por ejemplo, a continuación se muestra una red Beneš de 8 × 8 (es decir, con N = 8); tiene 2 log 2 8 − 1 = 5 etapas, cada una de las cuales contiene N /2 = 4 interruptores de barra transversal de 2×2, y utiliza un total de N log 2 N − N /2 = 20 interruptores de barra transversal de 2×2. Las tres etapas centrales constan de dos redes Beneš 4×4 más pequeñas, mientras que en el escenario central, cada interruptor de barra transversal 2×2 puede considerarse a su vez como una red Beneš 2×2. Por tanto, este ejemplo pone de relieve la construcción recursiva de este tipo de red.
