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 puede conectarse 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 conmutador de entrada, y que este debe conectarse 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. 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 etapa intermedia no pueden transportar la nueva llamada. Por lo tanto, para garantizar un funcionamiento sin bloqueo en sentido estricto, se requiere otro interruptor de etapa intermedia, lo que da un total de 2 n − 1.

El siguiente diagrama muestra el peor caso, cuando las llamadas ya establecidas (azul y roja) 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 verdes.

Si m ≥ n , la red Clos es reorganizable sin bloqueo , lo que significa que una entrada no utilizada en un conmutador de entrada siempre puede conectarse a una salida no utilizada en un conmutador de salida, pero para que esto ocurra, las llamadas existentes pueden tener que reorganizarse asignándolas a diferentes conmutadores centrales en la red Clos. ^{[ 6 ]} Para demostrar esto, es suficiente considerar m = n , con la red Clos completamente utilizada; es decir, r × n llamadas en curso. La demostración 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 que pueden ser implementadas cada una por los conmutadores de barra cruzada individuales en una red Clos con m = n .

La demostración 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 chicos y r chicas. El teorema establece que si cada subconjunto de k chicos (para cada k tal que 0 ≤ k ≤ r ) conoce a k o más chicas, entonces cada chico puede ser emparejado con una chica que conoce. Es obvio que esta es una condición necesaria para que se produzca el emparejamiento; lo sorprendente es que es suficiente.

En el contexto de una red Clos, cada niño representa un interruptor de entrada y cada niña un interruptor de salida. Se dice que un niño conoce a una niña si los interruptores de entrada y salida correspondientes transmiten la misma llamada. Cada conjunto de k niños debe conocer al menos a k niñas, ya que k interruptores de entrada transmiten k × n llamadas, y estas no pueden ser transmitidas por menos de k interruptores de salida. Por lo tanto, cada interruptor de entrada puede emparejarse con un interruptor de salida que transmita la misma llamada, mediante una correspondencia uno a uno. Estas r llamadas pueden ser transmitidas por un interruptor de etapa intermedia. Si este interruptor de etapa intermedia se elimina de la red Clos, m se reduce en 1, y nos queda una red Clos más pequeña. El proceso se repite hasta que m = 1, y cada llamada se asigna a un interruptor 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 p − p ^2. La probabilidad de bloqueo, o la probabilidad de que ninguna ruta de este tipo esté libre, es entonces [1 − (1 − p ) ² ] ^m .

La aproximación de Jacobaeus es más precisa, y para ver cómo se deriva, supongamos que ya existe una asignación particular de las llamadas que ingresan a la red Clos (llamadas de entrada) a los conmutadores de etapa intermedia. Esto refleja el hecho de que solo las configuraciones relativas de los conmutadores de entrada y 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 maneras de asignar las j llamadas de salida a los m conmutadores de la 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 restantes de la 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:

${\displaystyle \beta _{ij}={\frac {B}{A}}={\frac {\left({\begin{array}{c}i\\mj\end{array}}\right)}{\left({\begin{array}{c}m\\j\end{array}}\right)}}={\frac {i!j!}{(i+jm)!m!}}}$

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:

${\displaystyle P_{B}=\sum _{i=0}^{u}\sum _{j=0}^{u}f_{i}g_{j}\beta _{ij}}$

Esto se puede evaluar con f _i y g _j denotados cada uno por una distribución binomial . Después de una considerable manipulación algebraica, esto se puede escribir como:

${\displaystyle P_{B}={\frac {(u!)^{2}(2-p)^{2u-m}p^{m}}{m!(2u-m)!}}}$

Una red reconfigurable sin bloqueo de este tipo con m = n = 2 se denomina generalmente red de Beneš , aunque otros la discutieron y analizaron antes que Václav E. Beneš . El número de entradas y salidas es N = r × n = 2 r . Dichas redes tienen 2log ₂ N − 1 etapas, cada una con N /2 conmutadores de barra transversal de 2 × 2, y utilizan un total de N log ₂ N − N /2 conmutadores de barra transversal de 2 × 2. Por ejemplo, una red de Beneš de 8 × 8 (es decir, con N = 8) se muestra a continuación; tiene 2log ₂ 8 − 1 = 5 etapas, cada una con N /2 = 4 conmutadores de barra transversal de 2 × 2, y utiliza un total de N log ₂ N − N /2 = 20 conmutadores de barra transversal de 2 × 2. Las tres etapas centrales constan de dos redes Beneš más pequeñas de 4 × 4, mientras que en la etapa central, cada conmutador de barra transversal de 2 × 2 puede considerarse a su vez una red Beneš de 2 × 2. Este ejemplo, por lo tanto, resalta la construcción recursiva de este tipo de red, con una de las dos redes Beneš de 4 × 4 constituyentes resaltada. El color de las líneas entre los bloques de 2 × 2 se eligió para enfatizar la descomposición recursiva par-impar de las entradas, donde las entradas impares van a un subbloque y las entradas pares al otro.