En el campo de las telecomunicaciones , una red Clos es un tipo de red de conmutación de circuitos de varias etapas que representa una idealización teórica de los sistemas de conmutación de varias etapas prácticos. Fue inventado por Edson Erwin [1] en 1938 y la primera formalizado por Charles Clos ( pronunciación francesa: [ʃaʁl klo] ) [2] en 1952.
Al agregar etapas, una red Clos reduce la cantidad de puntos de cruce necesarios para componer un gran conmutador de barra transversal . A Clos topología de la red (diagramada abajo) se parametriza por tres enteros n , m , y r : n representa el número de fuentes que alimentan cada uno de r entrada etapa travesaño interruptores; cada interruptor de barra transversal de la etapa de entrada 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 de Clos, el número 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 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 llegada de los centros de datos complejos, con enormes estructuras de interconexión, cada una basada en enlaces de fibra óptica, las redes de Clos recuperaron importancia. [3] Un subtipo de la red Clos, la red Beneš, también ha encontrado una aplicación reciente en el aprendizaje automático . [4]
Topología
Las redes de Clos tienen tres etapas: la etapa de ingreso, la etapa intermedia y la etapa de salida. Cada etapa se compone de una serie de interruptores de barras transversales (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 conmutador de barra transversal de entrada se puede enrutar a través de cualquiera de los conmutadores de barra transversal de etapa intermedia disponibles, al conmutador de barra transversal de salida correspondiente. Una barra transversal de etapa intermedia está disponible para una nueva llamada en 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.
Redes Clos se definen por tres enteros n , m , y r . n representa el número de fuentes que alimentan cada uno de los interruptores de barra transversal de la etapa de ingreso r . Cada interruptor de barra transversal de etapa de entrada tiene m salidas y hay m interruptores de barra transversal de etapa intermedia. Existe exactamente una conexión entre cada conmutador de etapa de entrada y cada conmutador de etapa intermedia. Hay r conmutadores de la etapa de salida, cada uno con m entradas y n salidas. Cada interruptor de etapa intermedia está conectado exactamente una vez a cada interruptor de etapa de salida. Por 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 interruptores, cada uno de los cuales tiene m entradas y n salidas.
Características de bloqueo
Los valores relativos de m y n definen las características de bloqueo de la red Clos.
Redes Clos sin bloqueo de sentido estricto ( m ≥ 2 n −1): el resultado original de Clos de 1953
Si m ≥ 2 n −1, la red Clos es sin bloqueo de sentido estricto , 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, 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 interruptor de entrada, y esto tiene que estar conectado a un terminal libre en un interruptor de salida en particular. En el peor de los casos, otras n -1 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 por un conmutador de etapa intermedia diferente. Por tanto, en el peor de los casos, 2 n -2 de los conmutadores de la etapa intermedia no pueden realizar la nueva llamada. Por lo tanto, para garantizar una operación sin bloqueo de sentido estricto, se requiere otro interruptor de etapa intermedia, lo que hace un total de 2 n −1.
Redes Clos sin bloqueo reorganizable ( m ≥ n )
Si m ≥ n , la red Clos se reorganiza 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 los diferentes conmutadores centrales de la red de Clos. [5] Para probar esto, es suficiente considerar m = n , con la red de 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 que pueden ser implementadas por los interruptores de barra transversal individuales en una red Clos con m = n .
La demostración utiliza el teorema del matrimonio de Hall [6], que recibe este nombre porque a menudo se explica de la siguiente manera. Suponga 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 conocen k o más niñas, entonces cada niño puede emparejarse con una niña que él 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 de 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 grupo de k niños debe conocer al menos k niñas porque los k conmutadores de entrada llevan k × n llamadas y estas no pueden ser transmitidas por menos de k conmutadores de salida. Por lo tanto, cada interruptor de entrada se puede emparejar con un interruptor de salida que transmite la misma llamada, a través de un mapeo uno a uno. Estas llamadas r pueden realizarse mediante un conmutador de etapa intermedia. Si este interruptor de etapa intermedia ahora se elimina de la red de Clos, m se reduce en 1 y nos queda una red de 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.
Probabilidades de bloqueo: las aproximaciones de Lee y Jacobaeus
Los sistemas de conmutación de teléfonos reales rara vez son sin bloqueo en sentido estricto por razones de costo, y tienen una pequeña probabilidad de bloqueo, que puede ser evaluada por las aproximaciones de Lee o Jacobaeus , [7] 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 asume 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ña . 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 vínculo esté libre es 1− p . La probabilidad de que la ruta que conecta un interruptor de entrada a un interruptor de salida a través de un interruptor de etapa intermedia en particular sea 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 tal camino no sea libre, es entonces [1− (1− p ) 2 ] m .
La aproximación de Jacobaeus es más precisa, y para ver cómo se deriva, asuma que algún mapeo particular de las llamadas que ingresan a la red Clos (llamadas de entrada) ya existe en los conmutadores de etapa intermedia. Esto refleja el hecho de que solo las configuraciones relativas del conmutador de entrada y de salida son relevantes. Hay llamadas de entrada i que ingresan a través del mismo interruptor de entrada que el terminal de entrada libre que se va a conectar, y hay llamadas j que salen de la red Clos (llamadas de salida) a través del mismo interruptor de salida que el terminal de salida libre que se va 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 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 conmutadores de etapa intermedia m - j 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 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 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:
Clos redes con más de tres etapas
Las redes Clos también pueden generalizarse a cualquier número impar de etapas. Reemplazando cada conmutador de barra transversal de la 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.
Red Beneš ( m = n = 2)
Una red sin bloqueo reordenable de este tipo con m = n = 2 generalmente se denomina red Beneš , aunque fue discutida y analizada por otros antes de Václav E. Beneš . El número de entradas y salidas es N = r × n = 2 r . Dichas redes tienen 2 etapas log 2 N - 1, 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 con N / 2 = 4 interruptores de barra transversal 2 × 2, y utiliza un total de N log 2 N - N / 2 = 20 interruptores de barra transversal 2 × 2. Las tres etapas centrales consisten en dos redes Beneš 4 × 4 más pequeñas, mientras que en la etapa central, cada conmutador de barra transversal 2 × 2 puede considerarse en sí mismo como una red Beneš 2 × 2. Por tanto, este ejemplo pone de relieve la construcción recursiva de este tipo de red.
Ver también
- Interruptor de barra transversal , describe el elemento de conmutación de una red Clos
- Switch de expansión mínima sin bloqueo , describe el algoritmo de conmutación de una red Clos
- Banyan Switch , una forma alternativa de conectar redes
- Fat Tree , una forma alternativa de conectar redes
- Red Omega , una forma alternativa de conectar redes
Referencias
- ^ Patente estadounidense 2244004
- ^ Clos, Charles (marzo de 1953). "Un estudio de las redes de conmutación sin bloqueo" . Revista técnica de Bell System . 32 (2): 406–424. doi : 10.1002 / j.1538-7305.1953.tb01433.x . ISSN 0005-8580 .
- ^ Hogg, Scott (11 de enero de 2014). "Clos Networks: lo viejo es nuevo otra vez" . Mundo de la red.
- ^ Moore, Samuel (31 de octubre de 2018). "Flex Logix dice que ha resuelto el problema de DRAM de Deep Learning" . espectro.ieee.org . Espectro IEEE . Consultado el 1 de noviembre de 2018 .
- ^ Beneš, Václav E. (11 de septiembre de 1965). Teoría matemática de la conexión de redes y tráfico telefónico . Prensa académica . ISBN 0-12-087550-0.
- ^ Hall, Philip (enero de 1935). "Sobre representantes de subconjuntos" (PDF) . Revista de la Sociedad Matemática de Londres . s1. 10 (1): 26–30. doi : 10.1112 / jlms / s1-10.37.26 . Consultado el 18 de junio de 2015 .
- ^ Hui, Joseph Y. (1990). Teoría de conmutación y tráfico para redes integradas de banda ancha . Académico Kluwer. ISBN 0-7923-9061-X.