비차단 최소 스패닝 스위치
Nonblocking minimal spanning switch | 이 글은 검증을 위해 인용구가 추가로 필요하다. – · · · JSTOR(2018년 6월)(이 |
비차단 최소 스패닝 스위치는 어떤 조합에서도 N입력을 N출력에 연결할 수 있는 장치다. 이러한 유형의 스위치의 가장 익숙한 용도는 전화 교환이다. "비차단"이란 결함이 없는 경우 항상 연결될 수 있는 것을 말한다. "최소"란 가능한 구성요소가 가장 적고, 따라서 최소한의 비용을 부담하는 것을 말한다.
역사적으로, 전화 스위치에서, 통화자 사이의 연결은 전기 기계식 계전기, 스트로거 스위치의 크고 비싼 뱅크와 함께 배치되었다. Strowger 스위치의 기본적인 수학적 특성은 스위치에 대한 각 입력에 대해 정확히 하나의 출력이 있다는 것이다. 많은 수학적 전환 회로 이론은 입력의 조합을 출력 조합에 연결하는 데 필요한 총 스위치 수를 줄이기 위해 이 속성을 사용하려고 시도한다.
1940년대와 1950년대에 벨 연구소의 엔지니어들은 전화 교환을 시행하는 데 필요한 "교환된 직물"의 크기와 비용을 줄이기 위한 방법에 대한 일련의 수학적인 조사를 시작했다. 한 초기 성공적인 수학 분석은 찰스 클로(프랑스어 발음: [ʃaʁl klo])에 의해 수행되었으며, 작은 스위치로 구성된 스위치 원단을 클로즈 네트워크라고 한다.[1]
배경: 위상 전환
크로스바 스위치
크로스바 스위치는 어떤 일대일 조합에서도 N 입력을 N 출력에 연결할 수 있는 특성을 가지고 있으므로, 발신자 누구라도 비버스티 수신기에 연결할 수 있으며, 기술 용어 "비차단"이 주어지는 속성이다. 차단되지 않으면 항상 통화(바쁨이 아닌 수신기로의 통화)를 완료할 수 있어 서비스 가용성을 극대화할 수 있다.
그러나 크로스바 스위치는 N(N2 제곱) 단순 SPST 스위치의 사용 비용으로 그렇게 한다. 큰 N의 경우(그리고 전화 스위치의 실제 요구사항은 큰 것으로 간주됨) 이러한 성장은 너무 비쌌다. 게다가 대형 크로스바 스위치에는 물리적 문제가 있었다. 스위치에 너무 많은 공간이 필요했을 뿐만 아니라 스위치 접점이 들어 있는 금속 막대가 너무 길어져서 축 처지고 신뢰할 수 없게 되었다. 엔지니어들은 또한 언제든지 크로스바 스위치의 각 막대가 단 하나의 연결만 하고 있다는 것을 알아챘다. 두 개의 바의 다른 접점은 사용되지 않았다. 이는 크로스바 스위치의 스위치 원단 대부분이 낭비되었음을 암시하는 것 같았다.
크로스바 스위치를 에뮬레이트하는 명백한 방법은 더 작은 크로스바 스위치에서 크로스바 스위치를 빌드하는 방법을 찾는 것이었다. 크로스바 스위치가 작은 크로스바 스위치의 배열로 에뮬레이션될 수 있다면, 이 작은 크로스바 스위치도 에뮬레이션될 수 있다. 전환 원단은 매우 효율적이고 표준화된 부품으로 만들어질 수도 있다. 이것을 클로즈 네트워크라고 한다.
완전히 연결된 3단 스위치
다음 접근방식은 크로스바 스위치를 작은 크로스바 스위치의 세 겹으로 분리하는 것이었다. "입력층", "중간층" 그리고 "출력층"이 있을 것이다. 소형 스위치는 덜 크고, 더 안정적이며, 일반적으로 만들기 쉬우며, 따라서 비용이 덜 든다.
전화 시스템은 일대일 연결만 하면 된다. 직관적으로 이것은 입력의 수와 출력 수가 각 서브스위치에서 항상 같을 수 있다는 것을 의미하는 것 같지만, 직관은 이것이 이루어질 수 있다는 것을 증명할 수도 없고, 그렇게 하는 방법을 우리에게 말해주지도 않는다. 16x16 크로스바 스위치를 합성한다고 가정합시다. 설계에는 16개의 총 입력에 대해 각각 4개의 입력을 가진 4개의 하위 스위치가 있을 수 있다. 또한 출력 측에서는 출력 4개씩 총 16개의 출력을 위해 출력 하위 스위치 4개를 각각 보유할 수 있다. 와이어는 실제 비용이 들기 때문에 가능한 적은 수의 와이어를 사용하는 것이 바람직하다. 두 개의 서브스위치를 연결할 수 있는 최소한의 와이어 수는 하나의 와이어다. 따라서 각 입력 서브스위치는 각 중간 서브스위치에 대한 단일 와이어를 가진다. 또한 각 중간 서브스위치는 각 출력 서브스위치에 대한 단일 와이어를 가진다.
문제는 얼마나 많은 중간 서브스위치가 필요한지, 따라서 입력층을 중간층에 연결해야 하는 총 와이어가 몇 개인가 하는 것이다. 전화 스위치는 대칭이기 때문에(콜러와 캘리는 상호 교환 가능), 출력 레이어에 동일한 논리가 적용되며, 중간 서브스위치는 출력과 동일한 입력 수를 갖는 "제곱"이 된다.
중간 하위 스위치의 수는 연결을 할당하는 데 사용되는 알고리즘에 따라 달라진다. 3단 스위치 관리를 위한 기본 알고리즘은 필요한 입력 및 출력 스위치에 사용하지 않는 와이어가 있는 중간 서브스위치를 검색하는 것이다. 연결 가능한 중간 서브스위치가 발견되면 입력 및 출력 스위치에서 올바른 입력 및 출력에 연결하는 것은 사소한 일이다.
이론적으로 이 예에서는 각 입력 스위치에 정확히 한 개씩, 각 출력 스위치에 한 개씩의 연결이 있는 4개의 중앙 스위치만 필요하다. 이를 '최소 스패닝 스위치'라고 하는데, 이를 관리하는 것이 벨랩스 수사의 성배였다.
그러나 연필과 종이를 가지고 약간의 작업을 하는 것은 하나의 중간 스위치가 필요한 입력 스위치와 필요한 출력 스위치 둘 다에 연결되지 않는 상태로 그러한 최소한의 스위치를 얻는 것이 쉽다는 것을 보여줄 것이다. 스위치를 부분적으로 차단하는 데는 네 번의 통화밖에 걸리지 않는다. 입력 스위치가 절반만 차면 두 개의 중간 스위치를 통해 연결된다. 출력 스위치도 다른 두 개의 중간 스위치로부터의 연결로 절반만 채워져 있다면, 그 입력과 출력 사이에 경로를 제공할 수 있는 나머지 중간 스위치는 없다.
이러한 이유로, 4개의 입력 서브스위치와 4개의 출력스위치를 가진 "간소하게 연결된 비차단 스위치" 16x16 스위치는 7개의 중간 스위치가 필요하다고 생각되었다; 최악의 경우 거의 완전한 입력 서브스위치는 3개의 미들스위치를 사용하고, 거의 완전한 출력 서브스위치는 3개의 다른 스위치를 사용하고, 7번째 스위치는 다음과 같이 보장된다. 종착역에 자유롭다 이 때문에 이 스위치 배열을 "2n-1 스위치"라고 부르기도 하는데, 여기서 n은 입력 서브스위치의 입력 포트 수입니다.
그 예는 의도적으로 작으며, 그렇게 작은 예에서는 조직 개편이 많은 스위치를 절약하지 않는다. 16×16 크로스바에는 256개의 접점이 있고, 16×16 미니 스패닝 스위치에는 4×4×3 = 192개의 접점이 있다.
숫자가 커질수록 저축은 늘어난다. 예를 들어, 1만 개의 회선 교환은 완전한 크로스바를 구현하기 위해 1억 개의 연락처가 필요할 것이다. 그러나 100×100 서브스위치의 3개 층은 300개의 1만개의 접점 서브스위치, 즉 300만개의 접점만을 사용할 것이다.
이 하위 스위치는 각각 3×10 10×10 크로스바(총 3000개)로 만들어질 수 있으며, 전체 교환을 위해 90만 개를 만들 수 있다. 이는 1억 개보다 훨씬 적은 수이다.
최소 스패닝 스위치 관리
중요한 발견은 새로운 연결이 완료될 수 있도록 중간 스위치의 연결을 "거래선"으로 재구성하는 방법이었다.
첫 번째 단계는 입력 하위 스위치에서 중간 계층 하위 스위치(A라고 부름)로 연결되는 사용되지 않은 링크와 원하는 출력 하위 스위치로 연결되는 중간 계층 하위 스위치(B라고 부름)에서 사용되지 않은 링크를 찾는 것이다. 새로운 연결이 도착하기 전에, 입력 및 출력 하위 스위치는 각각 적어도 하나의 미사용 연결을 가지고 있었으므로, 이러한 미사용 링크가 모두 존재해야 한다.
A와 B가 동일한 중층 스위치일 경우, "2n-1" 스위치 케이스와 같이 즉시 연결할 수 있다. 단, A와 B가 다른 중층 서브스위치라면 더 많은 작업이 필요하다. 알고리즘은 기존의 모든 연결과 원하는 새 연결을 포함하는 중간 하위 스위치 A와 B를 통해 연결의 새로운 배열을 찾는다.
A 또는 B를 통과하는 모든 연결 목록을 만드십시오. 즉, 유지될 기존의 모든 연결과 새로운 연결이다. 알고리즘은 입력 스위치에서 출력 스위치까지의 내부 연결만 고려하지만 실제 구현은 정확한 입력 및 출력 스위치 연결도 추적해야 한다.
이 목록에서 각 입력 서브스위치는 최대 두 개의 연결, 즉 하나는 서브스위치 A, 하나는 서브스위치 B에 나타날 수 있다. 옵션은 0, 1, 2이다. 마찬가지로 각 출력 하위 스위치는 최대 두 개의 연결에 나타난다.
각 연결은 공유 입력 또는 출력 하위 스위치에 의해 최대 2개의 다른 연결로 연결되며, 연결의 "체인"에서 하나의 링크를 형성한다.
다음으로 새 연결부터 시작하십시오. 입력 서브스위치의 경로를 중간 서브스위치 A를 통해 출력 서브스위치에 할당한다. 이 첫 번째 연결의 출력 서브스위치에 두 번째 연결이 있는 경우, 두 번째 연결에 입력 서브스위치의 경로를 서브스위치 B를 통해 할당하십시오. 입력 하위 스위치에 다른 연결이 있는 경우 세 번째 연결에 하위 스위치 A를 통과하는 경로를 할당하십시오. 중간 서브스위치 A와 B를 번갈아 가며 이 방법으로 앞뒤로 계속 진행하십시오. 결국 두 가지 중 하나가 일어나야 한다.
- 하나의 연결만 있는 서브스위치에서 체인이 종료된다.
- 체인은 원래 선택된 연결부로 되돌아간다.
첫 번째 경우, 새 연결의 입력 서브스위치로 돌아가서 체인을 뒤로 따라가면서, 동일한 교대 패턴으로 중간 서브스위치 B와 A를 통한 경로에 연결을 할당한다.
이 작업이 완료되면 체인의 각 입력 또는 출력 서브스위치는 이를 통과하는 연결부가 최대 2개 있으며, 서로 다른 중간 스위치에 할당된다. 따라서 필요한 모든 링크를 이용할 수 있다.
새 연결을 포함하여 체인의 일부가 아닌 하위 스위치 A 및 B를 통한 추가 연결이 있을 수 있으며, 이러한 연결은 그대로 유지될 수 있다.
소프트웨어에서 새로운 연결 패턴을 설계한 후, 스위치의 전자장치를 실제로 재프로그래밍하여 물리적으로 연결을 이동할 수 있다. 전자스위치는 기존 연결을 방해하지 않고 새로운 구성이 전자기에 기록될 수 있도록 내부적으로 설계한 뒤 단일 논리 펄스로 효과를 발휘한다. 그 결과, 대화가 감지할 수 없는 중단과 함께 연결이 순간적으로 움직이게 된다. 오래된 전자기계 스위치에서는 때때로 "전환 소음"이 나는 소리가 들렸다."
이 알고리즘은 위상학적 분류의 한 형태로, 최소 스패닝 스위치를 제어하는 알고리즘의 심장이다.
스위치의 실제 구현
알고리즘이 발견되자마자 벨 시스템 엔지니어들과 매니저들은 이에 대해 논의하기 시작했다. 몇 년 후, 벨 엔지니어들은 그것에 의해 제어될 수 있는 전자기계 스위치를 설계하기 시작했다. 당시 컴퓨터는 튜브를 사용했고 전화 시스템을 제어할 수 있을 만큼 신뢰할 수 없었다(전화 시스템 스위치는 안전에 중요하며 30년에 한 번 정도 계획되지 않은 고장이 발생하도록 설계되었다). 릴레이 기반 컴퓨터는 알고리즘 구현이 너무 느렸다. 그러나 컴퓨터가 충분히 신뢰할 수 있을 때 기존 스위칭 시스템으로 개조할 수 있도록 전체 시스템을 설계할 수 있었다.
복합 스위치를 내결함성으로 만드는 것은 어렵지 않다. 서브스위치가 실패하면 호출자는 간단히 재다이얼을 한다. 따라서 각각의 새로운 연결에서 소프트웨어는 가장 최근에 출시된 연결 장치를 재사용하는 대신 각 서브스위치의 다음 무료 연결을 시도한다. 새로운 연결은 다른 회로를 사용하기 때문에 작동될 가능성이 더 높다.
따라서 바쁜 스위치에서 특정 PCB의 연결이 부족할 때는 시험의 우수한 후보라고 할 수 있다.
특정 인쇄 회로 카드를 테스트하거나 서비스에서 제거하기 위해 잘 알려진 알고리즘이 있다. 카드의 서브스위치를 통과하는 연결 수가 줄어들면서 소프트웨어가 더 많은 테스트 신호를 서브스위치를 통해 측정 장치로 전송한 다음 측정값을 읽는다. 이것은 여전히 작동하고 있는 오래된 전화들을 방해하지 않는다.
테스트가 실패하면 소프트웨어는 여러 개의 외부 스위치에서 고장을 판독하여 정확한 회로 보드를 격리한다. 그런 다음 고장난 회로에 있는 자유회로를 사용중으로 표시한다. 결함이 있는 회로를 이용한 통화가 종료됨에 따라 해당 회로도 통화중으로 표시된다. 얼마 후 결함이 있는 회로를 통화가 되지 않으면 교체가 필요한 회로판에 전등을 켜고, 기술자가 회로판을 교체할 수 있다. 교체 직후, 다음 테스트가 성공하고, 수리된 서브스위치와의 연결은 "사용중 아님"으로 표시되며, 스위치는 완전 작동으로 돌아간다.
벨의 초기 전자 스위치의 진단은 실제로 각 양호한 인쇄 회로 기판에 녹색등을 켜고, 고장난 각 인쇄 회로 기판에 빨간불을 켤 것이다. 인쇄된 회로는 전체 스위치를 끄지 않고도 분리 및 교체가 가능하도록 설계되었다.
최종 결과는 벨 1ESS였다. 이것은 신뢰할 수 있는 다이오드-트랜지스터 로직을 사용하는 하버드대 건축 양방향 컴퓨터인 중앙 제어(CC)라고 불리는 CPU에 의해 제어되었다. 1ESS CPU에서는 두 대의 컴퓨터가 각 단계를 수행하여 서로를 점검했다. 그들이 동의하지 않을 때, 그들은 스스로 진단했고, 올바르게 작동하는 컴퓨터는 스위치 작동을 하는 반면, 다른 컴퓨터는 스스로 자격을 박탈하고 수리를 요청한다. 1ESS 스위치는 2012년 현재도 제한적으로 사용 중이었으며, 30년 작동 시마다 1시간 미만의 불시 고장 신뢰성이 검증되어 설계가 검증되었다.
처음에는 주요 도시의 장거리 트렁크에 설치되었는데, 각 전화 교환에서 가장 많이 사용되는 부분이었다. 주요 도시들이 함께 운영한 첫 번째 어머니의 날에 벨 시스템은 통화 완료와 스위치당 초당 총 통화 수에서 총 네트워크 용량 기록을 세웠다. 이로 인해 트렁크당 총수입이 기록되었다.
디지털 스위치
스위치의 실제 구현은 더 작은 서브스위치의 홀수 층에서 만들어질 수 있다. 개념적으로 3단계 스위치의 크로스바 스위치는 각각 더 작은 크로스바 스위치로 분해될 수 있다. 각 서브스위치는 제한된 멀티플렉싱 기능을 가지고 있지만, 함께 작동하면 더 큰 N×N 크로스바 스위치의 효과를 합성한다.
현대의 디지털 전화 스위치에서, 서로 다른 두 개의 멀티플렉서 접근방식을 대체 계층에 적용하면 전환 원단 비용을 더욱 절감할 수 있다.
- 공간 분할 멀티플렉서는 이미 설명한 크로스바 스위치 또는 크로스오버 스위치 또는 반얀 스위치의 일부 배열과 같은 것이다. 모든 단일 출력은 모든 입력에서 선택할 수 있다. 디지털 스위치에서 이것은 대개 AND 게이트의 배열이다. 초당 8000회, 연결은 시간 슬롯 기간 동안 특정 와이어를 연결하도록 재프로그래밍된다. 설계상의 이점: 공간 분할 시스템에서 공간 분할 연결의 수는 시간 분할 다중화 시스템의 시간 간격 수로 나눈다. 이것은 스위칭 원단의 크기와 비용을 극적으로 줄인다. 또한 장애에 대한 물리적 연결이 훨씬 적기 때문에 신뢰성이 높아진다.
- 시간 분할 멀티플렉서는 각각 고정된 순서로 읽혀지고 프로그램 가능한 순서로 쓰여지는 메모리를 가지고 있다(또는 그 반대의 경우). 이러한 유형의 스위치는 시분할 멀티플렉싱 신호에서 시간대를 허용하며, 인접 계층의 공간 분할 멀티플렉서로 전달된다. 설계상의 이점: 타임 디비전 스위치는 입력 및 출력 와이어가 하나만 있다. 그들은 고장날 전기 연결이 훨씬 적기 때문에 공간 분할 스위치보다 훨씬 신뢰성이 높으며, 따라서 현대 전화 스위치의 외부(입력 및 출력) 층에 선호되는 스위치다.
실용적인 디지털 텔레폰 스위치는 전자제품의 크기와 비용을 최소화한다. 첫째, 스위치를 "접는" 것이 일반적이어서 가입자 회선에 대한 입력과 출력 연결 모두 동일한 제어 논리에 의해 처리된다. 그 후, 시간 분할 스위치를 외층에 사용한다. 외부 계층은 로컬 프레즌스 스트리트 사이드 박스에서 가입자 회선 인터페이스 카드(SLICs)로 구현된다. 중앙 스위치의 원격 제어 하에서 카드는 시간 다중 선에서 중앙 스위치로 타이밍 슬롯에 연결된다. 미국에서 멀티플렉스 라인은 T-1 라인의 배수다. 유럽과 많은 다른 나라들에서 그것은 E-1 라인의 배수다.
전화 스위치의 부족한 자원은 하위 스위치 층 사이의 연결이다. 이러한 연결은 멀티플렉싱의 유형에 따라 시간 간격 또는 와이어가 될 수 있다. 제어 논리는 이러한 연결을 할당해야 하며, 기본 방법은 이미 논의된 알고리즘이다. 서브스위치는 더 큰 서브스위치를 합성하도록 논리적으로 배열되어 있다. 각 서브스위치 및 합성 서브스위치는 Clos의 수학에서 도출된 논리에 의해 제어된다(재발적으로). 컴퓨터 코드는 더 큰 멀티플렉서를 더 작은 멀티플렉서로 분해한다.
가능한 최소 개수의 스위칭 요소까지 크로스바를 분해하면서 재귀가 한계에 도달하면, 그 위상에 따라 그 결과 장치를 크로스오버 스위치 또는 반얀 스위치라고 부르기도 한다.
스위치는 일반적으로 SONET과 같은 고속 멀티플렉스 데이터 라인을 통해 다른 스위치와 광섬유 네트워크에 접속한다.
스위치의 각 라인은 그것을 통해 시험 데이터를 전송함으로써 컴퓨터에 의해 주기적으로 시험될 수 있다. 스위치 라인이 고장 나면 스위치의 모든 라인이 사용 중인 것으로 표시된다. 멀티플렉서 라인은 선입선출 방식으로 할당되어 새로운 연결부가 새로운 스위치 요소를 찾는다. 결함이 있는 스위치에서 모든 연결이 끊어지면 결함이 있는 스위치를 피할 수 있으며, 나중에 교체할 수 있다.
2018년 현재, 그러한 스위치는 더 이상 만들어지지 않는다. 그것들은 초고속 인터넷 프로토콜 라우터로 대체되고 있다.
스위치 재라우팅 예제
참고 항목
참조
- ^ Clos, Charles (Mar 1953). "A study of non-blocking switching networks" (PDF). Bell System Technical Journal. 32 (2): 406–424. doi:10.1002/j.1538-7305.1953.tb01433.x. ISSN 0005-8580. Retrieved 22 March 2011.
