En el campo de las telecomunicaciones , una red Clos es un tipo de red de conmutación de circuitos multietapa que representa una idealización teórica de los sistemas prácticos de conmutación multietapa. Fue inventada por Edson Erwin [1] en 1938 y formalizada 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 conmutador 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 la cantidad de fuentes que alimentan cada uno de los r conmutadores de barra transversal de la etapa de ingreso; cada conmutador de barra transversal de la etapa de ingreso tiene m salidas; y hay m conmutadores de barra transversal de la 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 de forma deficiente, 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 procesado, como en las redes modernas de conmutación de paquetes .
Cuando se diseñó por primera vez la red Clos, la cantidad de puntos de cruce era una buena aproximación del costo total del sistema de conmutación. Si bien esto era importante para las barras cruzadas electromecánicas, perdió relevancia con la llegada de VLSI , en la que las interconexiones se podían implementar directamente en silicio o dentro de un grupo relativamente pequeño de placas. Con la llegada de los centros de datos complejos, con enormes estructuras de interconexión, cada una basada en enlaces de fibra óptica, las redes Clos recuperaron importancia. [4] Un subtipo de red Clos, la red Beneš, también ha encontrado una 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 egreso. Cada etapa está formada por una serie de conmutadores de barra cruzada (consulte el diagrama a continuación), a menudo llamados simplemente barras cruzadas . La red implementa una redistribución perfecta de r-way entre etapas. Cada llamada que ingresa a un conmutador de barra cruzada de ingreso se puede enrutar a través de cualquiera de los conmutadores de barra cruzada de etapa intermedia disponibles, al conmutador de barra cruzada de egreso relevante. Una barra cruzada de etapa intermedia está disponible para una nueva llamada en particular si tanto el enlace que conecta el conmutador de ingreso con el conmutador de etapa intermedia como el enlace que conecta el conmutador de etapa intermedia con el conmutador de egreso están libres.
Las redes Clos se definen mediante 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 la etapa de entrada. Cada conmutador de barra transversal de la etapa de entrada tiene m salidas y hay m conmutadores de barra transversal de la etapa intermedia. Hay exactamente una conexión entre cada conmutador de la etapa de entrada y cada conmutador de la etapa intermedia. Hay r conmutadores de la etapa de salida, cada uno con m entradas y n salidas. Cada conmutador de la etapa intermedia está conectado exactamente una vez a cada conmutador de la etapa de salida. Por lo tanto, la etapa de entrada tiene r conmutadores, cada uno de los cuales tiene n entradas y m salidas. La etapa intermedia tiene m conmutadores, cada uno de los cuales tiene r entradas y r salidas. La etapa de salida tiene r conmutadores, cada uno de los cuales tiene m entradas y n salidas.
Los valores relativos de m y n definen las características de bloqueo de la red Clos.
Si m ≥ 2 n −1, la red de Clos es no bloqueante 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 artículo clásico de Clos de 1953. Suponga que hay un terminal libre en la entrada de un conmutador de entrada, y este tiene que estar conectado a un terminal libre en un conmutador de salida 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. Suponga, también en el peor de los casos, que cada una de estas llamadas pasa a través de un conmutador de etapa intermedia diferente. Por lo tanto, en el peor de los casos, 2 n −2 de los conmutadores de etapa intermedia no pueden llevar la nueva llamada. Por lo tanto, para garantizar un funcionamiento 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 rojo) pasan por diferentes conmutadores de etapa intermedia, por lo que es necesario otro conmutador de etapa intermedia para establecer una llamada entre la entrada y la salida verde.
Si m ≥ n , la red Clos es reordenable sin bloqueo , 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, pero para que esto ocurra, es posible que las llamadas existentes deban reordenarse asignándolas a diferentes conmutadores de etapa central en la red Clos. [6] Para demostrarlo, 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 se puede descomponer en permutaciones más pequeñas que pueden implementarse cada una mediante los conmutadores de barra cruzada individuales en una red Clos con m = n .
La prueba utiliza el teorema del matrimonio de Hall [7] , que recibe 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 ) conoce entre ellos k o más niñas, entonces cada niño puede emparejarse con una niña que conozca. Es obvio que esta 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 conmutador de entrada y cada niña representa un conmutador de salida. Se dice que un niño conoce a una niña si los conmutadores de entrada y salida correspondientes llevan la misma llamada. Cada conjunto de k niños debe conocer al menos a k niñas porque k conmutadores de entrada llevan k × n llamadas y estas no pueden ser llevadas por menos de k conmutadores de salida. Por lo tanto, cada conmutador de entrada se puede emparejar con un conmutador de salida que lleva la misma llamada, a través de una asignación uno a uno. Estas r llamadas pueden ser llevadas por un conmutador de etapa intermedia. Si ahora se elimina este conmutador de etapa intermedia de la red Clos, m se reduce en 1 y nos quedamos con una red Clos más pequeña. Luego, el proceso se repite hasta que m = 1 y cada llamada se asigna a un conmutador de etapa intermedia.
Los sistemas de conmutación telefónica reales rara vez son estrictamente no bloqueantes por razones de costo, y tienen una pequeña probabilidad de bloqueo, que puede evaluarse mediante las aproximaciones de Lee o Jacobaeus [8] , suponiendo 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 esto es completamente independiente entre diferentes enlaces. Esto sobreestima la probabilidad de bloqueo, particularmente para r pequeño . La probabilidad de que un enlace interno dado 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 a un conmutador de salida a través de un conmutador de etapa intermedia particular esté libre es la probabilidad de que ambos enlaces estén libres, (1− p ) 2 . Por lo 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 ninguna ruta 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, suponga que ya existe algún mapeo particular de llamadas que ingresan a la red Clos (llamadas de entrada) en los conmutadores de etapa intermedia. Esto refleja el hecho de que solo las configuraciones relativas del conmutador de entrada y los conmutadores de salida son relevantes. Hay i llamadas de entrada que ingresan a través del mismo conmutador de entrada que el terminal de entrada libre que se va a conectar, y hay j llamadas que salen de la red Clos (llamadas de salida) a través del mismo conmutador de salida que el terminal de salida libre que se va a conectar. Por lo 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 conmutadores 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 m − j conmutadores de etapa intermedia restantes 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 otras i llamadas ya estén activas en el conmutador de entrada, y g j es la probabilidad de que otras j llamadas ya estén activas en el conmutador de salida, la probabilidad de bloqueo general es:
Esto se puede evaluar con f i y g j, cada uno denotado por una distribución binomial . Después de una considerable manipulación algebraica, esto se puede escribir como:
Las redes Clos también pueden generalizarse a cualquier número impar de etapas. Al reemplazar cada interruptor de barra transversal de la etapa central por 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 no bloqueante reordenable de este tipo con m = n = 2 generalmente se denomina red Beneš , aunque fue discutida y analizada por otros [ ¿quién? ] antes de Václav E. Beneš . El número de entradas y salidas es N = r × n = 2 r . Tales redes tienen 2 log 2 N − 1 etapas, cada una con N /2 2×2 interruptores de barra cruzada, y utilizan un total de N log 2 N − N /2 2×2 interruptores de barra cruzada. Por ejemplo, una red Beneš 8×8 (es decir, con N = 8) se muestra a continuación; tiene 2 log 2 8 − 1 = 5 etapas, cada una con N /2 = 4 2×2 interruptores de barra cruzada, y utiliza un total de N log 2 N − N /2 = 20 2×2 interruptores de barra cruzada. Las tres etapas centrales consisten en dos redes Beneš 4x4 más pequeñas, mientras que en la etapa central, cada interruptor de barra transversal 2x2 puede considerarse en sí mismo como una red Beneš 2x2. Por lo tanto, este ejemplo resalta la construcción recursiva de este tipo de red, con uno de los dos Beneš 4x4 constituyentes resaltado. El color de las líneas entre los bloques 2x2 se elige para enfatizar la descomposición recursiva impar-par de las entradas, con las entradas con números impares yendo a un subbloque y las entradas con números pares yendo al otro subbloque.
