sábado, 29 de junio de 2019

LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS


Un interruptor de expansión mínima sin bloqueo es un dispositivo que puede conectar N entradas a N salidas en cualquier combinación. El uso más familiar de los interruptores de este tipo es en una central telefónicaEl término "no bloqueo" significa que si no está defectuoso, siempre puede hacer la conexión. El término "mínimo" significa que tiene la menor cantidad de componentes posibles y, por lo tanto, el gasto mínimo.
Históricamente, en los conmutadores telefónicos, las conexiones entre las personas que llamaban se organizaban con grandes y costosos bancos de relés electromecánicos conmutadores Strowger . La propiedad matemática básica de los conmutadores Strowger es que para cada entrada al conmutador, hay exactamente una salida. Gran parte de la teoría del circuito de conmutación matemática intenta utilizar esta propiedad para reducir el número total de conmutadores necesarios para conectar una combinación de entradas a una combinación de salidas.
En las décadas de 1940 y 1950, los ingenieros de los Laboratorios Bell comenzaron una serie extendida de investigaciones matemáticas sobre métodos para reducir el tamaño y los gastos del " tejido conmutado " necesario para implementar una central telefónica. Una temprana, el análisis matemático se realizó con éxito por Charles Clos ( pronunciación francesa: [ʃaʁl klo] ), y un tejido de conmutación construida de conmutadores más pequeños se llama una red Clos .

Un sustituto para un interruptor de barra transversal de 16x16 hecho de 12 interruptores de barra 4x4.


Fondo: cambiando topologías editar ]

El interruptor de barra transversal editar ]

El interruptor de barra cruzada tiene la propiedad de poder conectar N entradas a N salidas en cualquier combinación de uno a uno , por lo que puede conectar a cualquier persona que llama a cualquier receptor no ocupado, una propiedad que recibe el término técnico de "no bloqueo". Al no estar bloqueado, siempre podría completar una llamada (a un receptor no ocupado), lo que maximizaría la disponibilidad del servicio.
Sin embargo, el interruptor de barra transversal lo hace a expensas de utilizar interruptores SPST simples 2 (N al cuadrado) Para N grande (y los requisitos prácticos de un interruptor de teléfono se consideran grandes) este crecimiento fue demasiado costoso. Además, los interruptores de barra grande tenían problemas físicos. No solo el interruptor requería demasiado espacio, sino que las barras de metal que contenían los contactos del interruptor serían tan largas que se doblarían y serían poco confiables. Los ingenieros también notaron que, en cualquier momento, cada barra de un interruptor de barra cruzada solo hacía una conexión. Los otros contactos en las dos barras no fueron utilizados. Esto parecía implicar que la mayor parte de la estructura de conmutación de un interruptor de barra cruzada se desperdiciaba.
La forma obvia de emular un interruptor de barra cruzada era encontrar una manera de construirlo a partir de interruptores de barra transversal más pequeños. Si un interruptor de barra cruzada pudiera ser emulado por alguna disposición de interruptores de barra transversal más pequeños, entonces estos interruptores de barra transversal más pequeños también podrían, a su vez, ser emulados por interruptores de barra transversal aún más pequeños. El tejido de conmutación podría volverse muy eficiente y posiblemente incluso crearse a partir de piezas estandarizadas. Esto se llama una red Clos .

Conmutadores de 3 capas completamente conectados editar ]

El siguiente enfoque fue dividir el interruptor de barra transversal en tres capas de interruptores de barra transversal más pequeños. Habría una "capa de entrada", una "capa intermedia" y una "capa de salida". Los interruptores más pequeños son menos masivos, más confiables y, por lo general, más fáciles de construir y, por lo tanto, menos costosos.
Un sistema telefónico solo tiene que hacer una conexión uno a uno. Intuitivamente esto parece significar que la cantidad de entradas y la cantidad de salidas siempre pueden ser iguales en cada interruptor secundario, pero la intuición no prueba que esto se pueda hacer ni nos dice cómo hacerlo. Supongamos que queremos sintetizar un interruptor de barra cruzada de 16 por 16. El diseño podría tener 4 conmutadores secundarios en el lado de entrada, cada uno con 4 entradas, para un total de 16 entradas. Además, en el lado de la salida, también podríamos tener 4 conmutadores de salida, cada uno con 4 salidas, para un total de 16 salidas. Es deseable que el diseño use la menor cantidad de cables posible, ya que los cables cuestan dinero real. El menor número posible de cables que pueden conectar dos conmutadores secundarios es un solo cable. Por lo tanto, cada interruptor de entrada tendrá un solo cable para cada interruptor secundario. También,
La pregunta es cuántos de los conmutadores intermedios se necesitan y, por lo tanto, cuántos cables totales deben conectar la capa de entrada a la capa intermedia. Dado que los interruptores telefónicos son simétricos (las personas que llaman y las personas que llaman son intercambiables), la misma lógica se aplicará a la capa de salida, y los conmutadores centrales serán "cuadrados", con el mismo número de entradas que las salidas.
El número de conmutadores intermedios depende del algoritmo utilizado para asignar la conexión a ellos. El algoritmo básico para administrar un interruptor de tres capas es buscar en los conmutadores intermedios un interruptor secundario que tenga cables no utilizados para los interruptores de entrada y salida necesarios. Una vez que se encuentra un interruptor secundario conectable, la conexión a las entradas y salidas correctas en los interruptores de entrada y salida es trivial.
Teóricamente, en el ejemplo, solo se necesitan cuatro interruptores centrales, cada uno con exactamente una conexión a cada interruptor de entrada y una conexión a cada interruptor de salida. Esto se denomina un "interruptor de expansión mínimo", y su gestión fue el santo grial de las investigaciones de Bell Labs.
Sin embargo, un poco de trabajo con un lápiz y papel demostrará que es fácil conseguir un cambio tan mínimo en condiciones en las que ningún interruptor central tenga una conexión con el interruptor de entrada necesario y el interruptor de salida necesario. Solo se necesitan cuatro llamadas para bloquear parcialmente el interruptor. Si un interruptor de entrada está medio lleno, tiene conexiones a través de dos interruptores centrales. Si un interruptor de salida también está medio lleno con las conexiones de los otros dos interruptores centrales, entonces no queda ningún interruptor intermedio que pueda proporcionar una ruta entre esa entrada y la salida.
Por esta razón, se pensó que un conmutador 16x16 "conmutador sin bloqueo simplemente conectado" con cuatro conmutadores de entrada y cuatro conmutadores de salida requería 7 conmutadores centrales; en el peor de los casos, un interruptor de entrada casi completo usaría tres interruptores centrales, un interruptor de salida casi completo usaría tres diferentes y se garantizaría que el séptimo quedaría libre para realizar la última conexión. Por esta razón, a veces esta disposición de conmutador se denomina " conmutador n −1", donde nes el número de puertos de entrada de los conmutadores de entrada.
El ejemplo es intencionalmente pequeño, y en un ejemplo tan pequeño, la reorganización no guarda muchos interruptores. Una barra transversal de 16 × 16 tiene 256 contactos, mientras que un interruptor de expansión mínima de 16 × 16 tiene 4 × 4 × 4 × 3 = 192 contactos.
A medida que los números aumentan, los ahorros aumentan. Por ejemplo, un intercambio de 10,000 líneas necesitaría 100 millones de contactos para implementar una barra transversal completa. Pero tres capas de 100 conmutadores de 100 x 100 utilizarían solo 300 conmutadores de 10.000 o 3 millones de contactos.
Esos sub-conmutadores podrían, a su vez, estar hechos de barras cruzadas de 3 × 10 10 × 10, un total de 3000 contactos, lo que hace 900,000 para todo el intercambio; Ese es un número mucho más pequeño que 100 millones.

Administrar un interruptor de expansión mínima editar ]

El descubrimiento crucial fue una forma de reorganizar las conexiones en los conmutadores centrales para "intercambiar cables" para que se pueda completar una nueva conexión.
El primer paso es encontrar un enlace no utilizado desde el interruptor secundario de entrada a un interruptor secundario de capa media (que llamaremos A), y un enlace no utilizado desde un interruptor secundario de capa media (que llamaremos B) al interruptor secundario de salida deseado. Dado que, antes de la llegada de la nueva conexión, cada uno de los conmutadores de entrada y salida tenía al menos una conexión no utilizada, estos dos enlaces no utilizados deben existir.
Si A y B resultan ser el mismo interruptor de la capa media, entonces la conexión se puede hacer inmediatamente como en el caso del interruptor "2 n −1". Sin embargo, si A y B son subswitches de capa media diferentes , se requiere más trabajo. El algoritmo encuentra una nueva disposición de las conexiones a través de los conmutadores intermedios A y B, que incluye todas las conexiones existentes, además de la nueva conexión deseada.
Haga una lista de todas las conexiones deseadas que pasan a través de A o B. Es decir, todas las conexiones existentes que se mantendrán y la nueva conexión. El algoritmo adecuado solo se preocupa por las conexiones internas desde el interruptor de entrada a salida, aunque una implementación práctica también tiene que hacer un seguimiento de las conexiones correctas del interruptor de entrada y salida.
En esta lista, cada interruptor secundario de entrada puede aparecer como máximo en dos conexiones: una para el interruptor secundario A y una para el interruptor secundario B. Las opciones son cero, uno o dos. Del mismo modo, cada interruptor de salida aparece como máximo dos conexiones.
Cada conexión está vinculada como máximo a otras dos por un interruptor de entrada o salida compartido, que forma un enlace en una "cadena" de conexiones.
A continuación, comience con la nueva conexión. Asígnele la ruta desde su interruptor de entrada, a través del interruptor intermedio A, hasta su interruptor de salida. Si el interruptor secundario de salida de esta primera conexión tiene una segunda conexión, asigne a esa segunda conexión un camino desde su interruptor de entrada a través del interruptor secundario B. Si ese interruptor secundario de entrada tiene otra conexión, asigne una ruta a esa tercera conexión a través del interruptor secundario A. Continúe adelante y atrás de esta manera , alternando entre los conmutadores intermedios A y B. Finalmente, debe suceder una de dos cosas:
  1. la cadena termina en un interruptor secundario con una sola conexión, o
  2. la cadena vuelve a la conexión elegida originalmente.
En el primer caso, vuelva al conmutador de entrada de la nueva conexión y siga su cadena hacia atrás, asignando conexiones a las rutas a través de los conmutadores intermedios B y A en el mismo patrón alternativo.
Cuando se hace esto, cada interruptor de entrada o salida en la cadena tiene como máximo dos conexiones que pasan a través de él, y se asignan a diferentes interruptores centrales. Por lo tanto, todos los enlaces necesarios están disponibles.
Puede haber conexiones adicionales a través de los conmutadores A y B que no forman parte de la cadena, incluida la nueva conexión; Esas conexiones pueden dejarse como están.
Una vez que el nuevo patrón de conexión está diseñado en el software, entonces la electrónica del conmutador se puede reprogramar, moviendo físicamente las conexiones. Los interruptores electrónicos están diseñados internamente para que la nueva configuración pueda escribirse en la electrónica sin alterar la conexión existente, y luego tener efecto con un solo pulso lógico. El resultado es que la conexión se mueve instantáneamente, con una interrupción imperceptible de la conversación. En interruptores electromecánicos más antiguos, uno escuchaba ocasionalmente un ruido de "ruido de conmutación".
Este algoritmo es una forma de ordenamiento topológico , y es el corazón del algoritmo que controla un interruptor de expansión mínimo.

Implementaciones prácticas de switches editar ]

Tan pronto como se descubrió el algoritmo, los ingenieros y gerentes de sistemas de Bell comenzaron a discutirlo. Después de varios años, los ingenieros de Bell comenzaron a diseñar interruptores electromecánicos que podían ser controlados por él. En ese momento, las computadoras usaban tubos y no eran lo suficientemente confiables para controlar un sistema telefónico (los interruptores del sistema telefónico son críticos para la seguridad y están diseñados para tener una falla no planificada aproximadamente una vez cada treinta años). Las computadoras basadas en relés eran demasiado lentas para implementar el algoritmo. Sin embargo, todo el sistema podría diseñarse de modo que cuando las computadoras fueran lo suficientemente confiables, pudieran ser adaptadas a los sistemas de conmutación existentes.
No es difícil hacer que los interruptores compuestos sean tolerantes a los fallos . Cuando falla un interruptor secundario, las personas que llaman simplemente vuelven a marcar. Por lo tanto, en cada nueva conexión, el software intenta la siguiente conexión gratuita en cada interruptor secundario en lugar de reutilizar la última versión lanzada. Es más probable que la nueva conexión funcione porque usa diferentes circuitos.
Por lo tanto, en un conmutador ocupado, cuando un PCB particular carece de conexiones, es un excelente candidato para la prueba.
Para probar o quitar una tarjeta de circuito impreso en particular del servicio, existe un algoritmo conocido. A medida que pasan menos conexiones a través del interruptor secundario de la tarjeta, el software envía más señales de prueba a través del interruptor secundario a un dispositivo de medición y luego lee la medición. Esto no interrumpe las llamadas antiguas, que siguen funcionando.
Si una prueba falla, el software aísla la placa de circuito exacta leyendo la falla de varios interruptores externos. Luego marca los circuitos libres en el circuito defectuoso como ocupado. Cuando las llamadas que usan el circuito defectuoso se terminan, esos circuitos también se marcan como ocupados. Algún tiempo después, cuando no pasa ninguna llamada a través del circuito defectuoso, la computadora enciende una luz en la placa del circuito que necesita reemplazo, y un técnico puede reemplazar la placa del circuito. Poco después de la sustitución, la siguiente prueba es satisfactoria, las conexiones al interruptor secundario reparado se marcan como "no ocupado" y el interruptor vuelve a la operación completa.
Los diagnósticos en los primeros interruptores electrónicos de Bell en realidad encenderían una luz verde en cada buena placa de circuito impreso, y encenderían una luz roja en cada placa de circuito impreso fallada. Los circuitos impresos se diseñaron de manera que se pudieran quitar y reemplazar sin apagar todo el interruptor.
El resultado final fue la campana 1ESS . Esto fue controlado por un CPU llamada la central de control (CC), un bloqueo de paso , la arquitectura Harvard ordenador dual usando fiable lógica diodo-transistor . En la CPU 1ESS, dos computadoras realizaron cada paso, verificándose entre sí. Cuando no estaban de acuerdo, se diagnosticaban a sí mismos, y la computadora que funcionaba correctamente tomaba el interruptor mientras que la otra se descalificaba y pedía reparación. El interruptor 1ESS todavía estaba en uso limitado a partir de 2012, y tenía una confiabilidad verificada de menos de una hora de falla no programada en cada treinta años de operación, validando su diseño.
Inicialmente, se instaló en troncales de larga distancia en las principales ciudades, las partes más utilizadas de cada central telefónica. En el primer Día de la Madre que las principales ciudades operaron con él, el sistema Bell estableció un récord para la capacidad total de la red, tanto en llamadas completadas, como en el total de llamadas por segundo por conmutador. Esto dio lugar a un récord de ingresos totales por troncal.

Interruptores digitales editar ]

Se puede crear una implementación práctica de un conmutador a partir de un número impar de capas de conmutadores más pequeños. Conceptualmente, los interruptores de barra transversal del interruptor de tres etapas se pueden descomponer en interruptores de barra transversal más pequeños. Aunque cada interruptor secundario tiene una capacidad de multiplexación limitada, al trabajar juntos sintetizan el efecto de un interruptor de barra cruzada N × N más grande .
En un conmutador de teléfono digital moderno, la aplicación de dos enfoques de multiplexor diferentes en capas alternativas reduce aún más el costo de la estructura de conmutación:
  1. Los multiplexores de división de espacio son algo así como los interruptores de barra cruzada ya descritos, o alguna disposición de interruptores de cruce o interruptores de Banyan . Cualquier salida individual puede seleccionar desde cualquier entrada. En los conmutadores digitales, esto suele ser una disposición de puertas AND . 8000 veces por segundo, la conexión se reprograma para conectar cables específicos durante un intervalo de tiempo . Ventaja de diseño:En los sistemas de división espacial, el número de conexiones de división de espacio se divide por el número de intervalos de tiempo en el sistema de multiplexación por división de tiempo. Esto reduce drásticamente el tamaño y el gasto de la tela de conmutación. También aumenta la confiabilidad, porque hay muchas menos conexiones físicas para fallar.
  2. Los multiplexores de división de tiempo tienen cada uno una memoria que se lee en un orden fijo y se escribe en un orden programable (o viceversa ). Este tipo de conmutador permuta los intervalos de tiempoen una señal multiplexada por división de tiempo que va a los multiplexores de división espacial en sus capas adyacentes. Ventaja de diseño: los interruptores de división de tiempo tienen un solo cable de entrada y salida. Dado que tienen muchas menos conexiones eléctricas para fallar, son mucho más confiables que los interruptores de división de espacio y, por lo tanto, son los interruptores preferidos para las capas externas (entrada y salida) de los interruptores telefónicos modernos.
Los prácticos conmutadores telefónicos digitales minimizan el tamaño y los gastos de la electrónica. Primero, es típico "plegar" el conmutador, de modo que tanto la conexión de entrada como la de salida a una línea de abonado se manejen mediante la misma lógica de control. Luego, se utiliza un interruptor de división de tiempo en la capa exterior. La capa externa se implementa en las tarjetas de interfaz de línea de abonado (SLIC) en las casillas de la calle de presencia local. Bajo el control remoto del interruptor central, las tarjetas se conectan a los intervalos de tiempo en una línea multiplexada en el tiempo a un interruptor central. En los Estados Unidos, la línea multiplexada es un múltiplo de una línea T-1 . En Europa y en muchos otros países, es un múltiplo de una línea E-1 .
Los recursos escasos en un conmutador telefónico son las conexiones entre capas de conmutadores secundarios. Estas conexiones pueden ser ranuras de tiempo o cables, según el tipo de multiplexación. La lógica de control tiene que asignar estas conexiones, y el método básico es el algoritmo ya analizado. Los conmutadores se organizan de forma lógica para que puedan sintetizar conmutadores más grandes. Cada conmutador secundario y sintetizado se controlan ( recursivamente ) por la lógica derivada de las matemáticas de Clos. El código de la computadora descompone los multiplexores más grandes en multiplexores más pequeños.
Si la recursión se lleva al límite, descomponiendo la barra transversal al mínimo número posible de elementos de conmutación, el dispositivo resultante a veces se denomina conmutador de cruce o conmutador de Banyan enfunción de su topología.
Los conmutadores suelen interactuar con otros conmutadores y redes de fibra óptica a través de líneas de datos multiplexados rápidos como SONET .
Cada línea de un interruptor puede ser probada periódicamente por la computadora, enviando datos de prueba a través de ella. Si la línea de un interruptor falla, todas las líneas de un interruptor se marcan como en uso. Las líneas de multiplexor se asignan de una forma de primero a primero, para que las nuevas conexiones encuentren nuevos elementos de conmutador. Cuando todas las conexiones se van de un interruptor defectuoso, se puede evitar el interruptor defectuoso y luego reemplazarlo.
A partir de 2018, tales interruptores ya no se hacen. Están siendo reemplazados por enrutadores de protocolo de Internet de alta velocidad .

Ejemplo de reencaminamiento de un interruptor editar ]


Las señales A, B, C, D se enrutan, pero la señal E se bloquea, a menos que una señal, como la D que se muestra en púrpura, se desvíe.

Después de que D, en púrpura, se redirecciona, la señal E puede enrutarse y todas las señales adicionales más E están conectadas

No hay comentarios:

Publicar un comentario