ノンブロッキング最小スパニングスイッチ

ノンブロッキング ミニマル スパニング スイッチは、N 入力を N 出力に任意の組み合わせで接続できるデバイスです。このタイプのスイッチの最も一般的な用途は、電話交換機です。「ノンブロッキング」という用語は、欠陥がない限り、常に接続できることを意味します。「ミニマル」という用語は、可能な限りコンポーネントが少なく、したがってコストが最小限であることを意味します。

歴史的に、電話交換機では、発信者間の接続は、大きくて高価な電気機械式リレー バンク、ストロージャー スイッチによって行われていました。ストロージャー スイッチの基本的な数学的特性は、スイッチへの各入力に対して、正確に 1 つの出力があることです。数学的なスイッチング回路理論の多くは、この特性を利用して、入力の組み合わせを出力の組み合わせに接続するために必要なスイッチの総数を削減しようとしています。

1940年代から1950年代にかけて、ベル研究所のエンジニアたちは、電話交換機を実装するために必要な「スイッチファブリック」のサイズと費用を削減する方法について、数学的な調査を始めました。初期の成功した数学的分析の1つは、シャルル・クロス（フランス語の発音： [ʃaʁl klo]）によって行われ、より小さなスイッチで構成されたスイッチファブリックは、クロスネットワークと呼ばれています。^[1]

クロスバー スイッチには、N 個の入力を N 個の出力に1 対 1 の任意の組み合わせで接続できるという特性があるため、任意の発信者を任意の非ビジー状態の受信者に接続できます。この特性は、専門用語で「非ブロッキング」と呼ばれます。非ブロッキングであるため、常に (非ビジー状態の受信者への) 通話を完了でき、サービスの可用性が最大化されます。

^{しかし、クロスバースイッチは、N 2} (Nの2乗) 個の単純なSPSTスイッチを使用するという犠牲を払ってこれを行います。Nが大きい場合(電話交換機の実際の要件は大きいと見なされます)、この増加はコストがかかりすぎました。さらに、大きなクロスバースイッチには物理的な問題がありました。スイッチに必要なスペースが大きすぎるだけでなく、スイッチ接点を含む金属バーが長くなりすぎてたるんで信頼性が低下します。エンジニアはまた、クロスバースイッチの各バーが常に単一の接続しか行っていないことに気付きました。2つのバーの他の接点は使用されていませんでした。これは、クロスバースイッチのスイッチングファブリックのほとんどが無駄になっていることを意味しているようでした。

クロスバー スイッチをエミュレートする明白な方法は、より小さなクロスバー スイッチからそれを構築する方法を見つけることでした。クロスバー スイッチをより小さなクロスバー スイッチの配置でエミュレートできる場合、これらのより小さなクロスバー スイッチをさらに小さなクロスバー スイッチでエミュレートすることもできます。スイッチング ファブリックは非常に効率的になり、標準化された部品から作成することもできます。これはClos ネットワークと呼ばれます。

次のアプローチは、クロスバー スイッチを 3 つの小さなクロスバー スイッチ層に分割することでした。「入力層」、「中間層」、および「出力層」があります。スイッチが小さいほど、サイズが小さく、信頼性が高く、一般的に構築が容易で、したがってコストも低くなります。

電話システムは、1 対 1 の接続だけを行う必要があります。直感的には、各サブスイッチの入力数と出力数が常に等しくなるように思われますが、直感ではこれが可能であることが証明されず、その方法もわかりません。16 x 16 のクロスバー スイッチを合成するとします。設計では、入力側にサブスイッチを 4 つ (それぞれ入力が 4 つ) 配置して、合計 16 の入力にすることができます。さらに、出力側にも出力サブスイッチを 4 つ (それぞれ出力が 4 つ) 配置して、合計 16 の出力にすることができます。配線にはコストがかかるため、設計で使用する配線はできる限り少なくすることが望ましいです。2 つのサブスイッチを接続できる最小の配線数は 1 本です。したがって、各入力サブスイッチには、各中間サブスイッチへの配線が 1 本あります。また、各中間サブスイッチには、各出力サブスイッチへの配線が 1 本あります。

問題は、中間サブスイッチがいくつ必要か、したがって入力層を中間層に接続する配線の総数がいくつ必要かということです。電話スイッチは対称型 (発信者と着信者は交換可能) なので、同じロジックが出力層に適用され、中間サブスイッチは「正方形」になり、入力と出力の数が同じになります。

中間サブスイッチの数は、それらへの接続を割り当てるために使用されるアルゴリズムによって異なります。 3 層スイッチを管理するための基本的なアルゴリズムは、必要な入力スイッチと出力スイッチへの未使用の配線を持つ中間サブスイッチを中間サブスイッチで検索することです。 接続可能な中間サブスイッチが見つかると、入力スイッチと出力スイッチの正しい入力と出力への接続は簡単です。

理論的には、この例では、各入力スイッチに 1 つの接続、各出力スイッチに 1 つの接続を持つ中央スイッチが 4 つだけ必要です。これは「最小スパニング スイッチ」と呼ばれ、これを管理するのがベル研究所の研究の究極の目標でした。

しかし、鉛筆と紙を使って少し作業してみると、必要な入力スイッチと必要な出力スイッチの両方に接続している中間スイッチが 1 つもないという状況に、このような最小限のスイッチを簡単に導入できることがわかります。スイッチを部分的にブロックするには、4 回の呼び出しだけが必要です。入力スイッチが半分埋まっている場合、2 つの中間スイッチを介して接続されています。出力スイッチも他の 2 つの中間スイッチからの接続で半分埋まっている場合、その入力と出力の間にパスを提供できる中間スイッチは残っていません。

このため、4 つの入力サブスイッチと 4 つの出力スイッチを備えた「単純接続の非ブロッキング スイッチ」16x16 スイッチには、7 つの中間スイッチが必要であると考えられていました。最悪の場合、ほぼ完全な入力サブスイッチは 3 つの中間スイッチを使用し、ほぼ完全な出力サブスイッチは 3 つの異なるスイッチを使用し、7 番目は最後の接続を行うために空いていることが保証されます。このため、このスイッチ配置は「2 n −1 スイッチ」と呼ばれることがあります。ここで、n は入力サブスイッチの入力ポートの数です。

この例は意図的に小さくされており、このような小さな例では、再編成によって多くのスイッチが節約されるわけではありません。16×16 クロスバーには 256 個のコンタクトがありますが、16×16 の最小スパニング スイッチには 4×4×4×3 = 192 個のコンタクトがあります。

数字が大きくなるほど、節約できるコストも増えます。たとえば、10,000 回線の交換機では、完全なクロスバーを実装するために 1 億個のコンタクトが必要です。しかし、100 個の 100×100 サブスイッチを 3 層にすると、10,000 コンタクトのサブスイッチが 300 個、つまり 300 万個のコンタクトしか使用されません。

これらのサブスイッチはそれぞれ 3×10 10×10 クロスバーで構成され、合計 3000 個の接点を持つため、交換機全体では 900,000 個になります。これは 1 億よりはるかに小さい数です。

決定的な発見は、中間スイッチの接続を再編成して「ワイヤを交換する」ことで、新しい接続を完了できるようにする方法でした。

最初のステップは、入力サブスイッチから中間層サブスイッチ (A と呼ぶ) への未使用のリンクと、中間層サブスイッチ (B と呼ぶ) から目的の出力サブスイッチへの未使用のリンクを見つけることです。新しい接続が到着する前は、入力サブスイッチと出力サブスイッチのそれぞれに少なくとも 1 つの未使用の接続があったため、これらの未使用のリンクは両方とも存在している必要があります。

A と B が同じ中間層スイッチである場合は、「2 n −1」スイッチの場合と同様に、すぐに接続できます。ただし、A と B が異なる中間層サブスイッチである場合は、さらに作業が必要です。アルゴリズムは、中間サブスイッチ A と B を介した接続の新しい配置を見つけます。これには、既存のすべての接続と、必要な新しい接続が含まれます。

A または B を通過するすべての必要な接続のリストを作成します。つまり、維持されるすべての既存の接続と新しい接続です。アルゴリズム自体は、入力スイッチから出力スイッチへの内部接続のみを考慮しますが、実際の実装では、正しい入力スイッチと出力スイッチの接続も追跡する必要があります。

このリストでは、各入力サブスイッチは最大 2 つの接続に出現します。1 つはサブスイッチ A への接続、もう 1 つはサブスイッチ B への接続です。オプションは 0、1、または 2 です。同様に、各出力サブスイッチは最大 2 つの接続に出現します。

各接続は、共有入力または出力サブスイッチによって最大 2 つの他の接続にリンクされ、接続の「チェーン」内の 1 つのリンクを形成します。

次に、新しい接続から始めます。入力サブスイッチから中間サブスイッチ A を経由して出力サブスイッチまでのパスを割り当てます。この最初の接続の出力サブスイッチに 2 番目の接続がある場合は、その 2 番目の接続に入力サブスイッチからサブスイッチ B までのパスを割り当てます。その入力サブスイッチに別の接続がある場合は、その 3 番目の接続にサブスイッチ A までのパスを割り当てます。この方法で、中間サブスイッチ A と B を交互に繰り返します。最終的に、次の 2 つのうちのいずれかが発生します。

1. チェーンは1つの接続のみを持つサブスイッチで終了するか、
2. チェーンは最初に選択された接続に戻ります。

最初のケースでは、新しい接続の入力サブスイッチに戻り、そのチェーンを逆方向にたどり、同じ交互パターンで中間のサブスイッチ B と A を通るパスに接続を割り当てます。

これを実行すると、チェーン内の各入力または出力サブスイッチには最大 2 つの接続が通過し、それらは異なる中間スイッチに割り当てられます。したがって、必要なリンクはすべて利用可能になります。

新しい接続を含むチェーンの一部ではないサブスイッチ A および B を介した追加の接続が存在する場合があり、それらの接続はそのまま残される場合があります。

ソフトウェアで新しい接続パターンを設計した後、スイッチの電子部品を実際に再プログラムして、接続を物理的に移動できます。電子スイッチは内部的に設計されているため、既存の接続を妨げずに新しい構成を電子部品に書き込むことができ、単一のロジック パルスで有効になります。その結果、会話が中断されることなく、接続が瞬時に移動されます。古い電気機械式スイッチでは、時々「スイッチング ノイズ」のカチッという音が聞こえました。

このアルゴリズムはトポロジカルソートの一種であり、最小スパニングスイッチを制御するアルゴリズムの中核をなします。

アルゴリズムが発見されるとすぐに、ベルのシステム エンジニアと管理者はそれについて議論を始めました。数年後、ベルのエンジニアは、そのアルゴリズムで制御できる電気機械式スイッチの設計を開始しました。当時、コンピューターは真空管を使用しており、電話システムを制御するには信頼性が不十分でした (電話システムのスイッチは安全性が重要であり、30 年に 1 回程度の予期しない障害が発生するように設計されています)。 リレーベースのコンピューターは、アルゴリズムを実装するには遅すぎました。ただし、コンピューターの信頼性が十分になったら、既存の交換システムに後から組み込めるように、システム全体を設計することができました。

複合スイッチをフォールト トレラントにするのは難しくありません。サブスイッチに障害が発生した場合、発信者は単にリダイヤルするだけです。そのため、新しい接続ごとに、ソフトウェアは、最後に解放された接続を再利用するのではなく、各サブスイッチで次の空き接続を試みます。新しい接続は異なる回路を使用するため、機能する可能性が高くなります。

したがって、ビジー スイッチでは、特定の PCB に接続がない場合、テストに最適です。

特定のプリント回路カードをテストしたり、サービスから削除したりするには、よく知られたアルゴリズムがあります。カードのサブスイッチを通過する接続が少なくなると、ソフトウェアはサブスイッチを介してより多くのテスト信号を測定デバイスにルーティングし、測定値を読み取ります。これにより、古い通話が中断されることはなく、引き続き機能します。

テストが失敗すると、ソフトウェアは複数の外部スイッチから障害を読み取り、回路基板を正確に分離します。次に、障害のある回路の空き回路をビジーとしてマークします。障害のある回路を使用した通話が終了すると、それらの回路もビジーとしてマークされます。しばらくして、障害のある回路を通過する通話がなくなると、コンピューターは交換が必要な回路基板のライトを点灯し、技術者は回路基板を交換できます。交換後すぐに、次のテストが成功し、修復されたサブスイッチへの接続が「ビジーではない」とマークされ、スイッチは完全に動作する状態に戻ります。

ベルの初期の電子スイッチの診断では、正常なプリント基板には緑色のライトが点灯し、故障したプリント基板には赤色のライトが点灯しました。プリント基板は、スイッチ全体の電源を切らずに取り外して交換できるように設計されていました。

最終的な成果がベル1ESSです。これは、信頼性の高いダイオード トランジスタ ロジックを使用した、ロック ステップ方式のハーバード アーキテクチャ デュアル コンピュータである、中央制御(CC) と呼ばれる CPU によって制御されていました。1ESS CPU では、2 台のコンピュータが各ステップを実行し、相互にチェックしていました。意見が一致しない場合は、自己診断を行い、正常に動作しているコンピュータがスイッチ操作を引き継ぎ、もう 1 台は不適格として修理を要求しました。1ESS スイッチは 2012 年の時点でまだ限定的に使用されており、30 年間の運用で予定外の障害が 1 時間未満であるという信頼性が検証され、設計の有効性が実証されました。

当初、このシステムは各電話交換機で最も頻繁に使用される主要都市の長距離トランクに導入されました。主要都市でこのシステムが運用された最初の母の日に、ベル システムは、完了した通話数と交換機あたりの 1 秒あたりの通話数の両方で、総ネットワーク容量の記録を樹立しました。これにより、トランクあたりの総収益の記録が達成されました。

スイッチの実用的な実装は、奇数層の小さなサブスイッチから作成できます。概念的には、3 段スイッチのクロスバー スイッチはそれぞれ、さらに小さなクロスバー スイッチに分解できます。各サブスイッチの多重化機能は限られていますが、連携して動作することで、より大きなN × Nクロスバー スイッチの効果が得られます。

現代のデジタル電話交換機では、2 つの異なるマルチプレクサ アプローチを交互のレイヤーに適用することで、スイッチング ファブリックのコストがさらに削減されます。

1. 空間分割多重化装置は、すでに説明したクロスバー スイッチ、またはクロスオーバー スイッチやバンヤン スイッチの配置のようなものです。任意の単一の出力は、任意の入力から選択できます。デジタル スイッチでは、これは通常、AND ゲートの配置です。1 秒間に 8000 回、接続は、タイム スロットの期間に特定のワイヤを接続するように再プログラムされます。設計上の利点:空間分割システムでは、空間分割接続の数は、時分割多重化システムのタイム スロットの数で分割されます。これにより、スイッチング ファブリックのサイズと費用が大幅に削減されます。また、障害が発生する物理接続が大幅に減少するため、信頼性が向上します。
2. 時分割マルチプレクサにはそれぞれメモリがあり、固定順序で読み取られ、プログラム可能な順序で書き込まれます (またはその逆)。このタイプのスイッチは、隣接する層の空間分割マルチプレクサに送られる時分割多重化信号のタイムスロットを並べ替えます。設計上の利点: 時分割スイッチには入力線と出力線が 1 つしかありません。故障する電気接続がはるかに少ないため、空間分割スイッチよりもはるかに信頼性が高く、そのため現代の電話交換機の外側 (入力および出力) 層に適したスイッチです。

実用的なデジタル電話スイッチは、電子機器のサイズと費用を最小限に抑えます。まず、スイッチを「折りたたむ」のが一般的です。これにより、加入者回線への入力接続と出力接続の両方が同じ制御ロジックによって処理されます。次に、時分割スイッチが外層で使用されます。外層は、ローカル プレゼンス ストリートサイド ボックス内の加入者回線インターフェイス カード (SLIC) に実装されます。中央スイッチからのリモート制御により、カードは中央スイッチへの時間多重回線のタイミング スロットに接続します。米国では、多重回線はT-1 回線の倍数です。ヨーロッパおよび他の多くの国では、多重回線はE-1 回線の倍数です。

電話交換機の希少なリソースは、サブスイッチの層間の接続です。これらの接続は、多重化のタイプに応じて、タイムスロットまたはワイヤのいずれかになります。制御ロジックはこれらの接続を割り当てる必要があり、基本的な方法は、すでに説明したアルゴリズムです。サブスイッチは、より大きなサブスイッチを合成するように論理的に配置されます。各サブスイッチと合成されたサブスイッチは、Clos の数学から派生したロジックによって (再帰的に) 制御されます。コンピュータ コードは、より大きなマルチプレクサをより小さなマルチプレクサに分解します。

再帰を極限まで進めて、クロスバーを可能な限り最小限のスイッチング要素に分割すると、結果として得られるデバイスは、そのトポロジに応じて クロスオーバー スイッチまたはバンヤン スイッチと呼ばれることがあります。

スイッチは通常、 SONETなどの高速多重化データ回線を介して他のスイッチや光ファイバー ネットワークとインターフェイスします。

スイッチの各回線は、テスト データをコンピュータに送信することで定期的にテストできます。スイッチの回線に障害が発生すると、スイッチのすべての回線が使用中としてマークされます。マルチプレクサ回線は先入れ先出し方式で割り当てられるため、新しい接続は新しいスイッチ要素を見つけます。故障したスイッチからすべての接続がなくなると、故障したスイッチを回避して後で交換できます。

2018 年現在、このようなスイッチは製造されておらず、高速インターネット プロトコルルーターに置き換えられています。

• 時間帯の交換
• クロスネットワーク
• クロスバースイッチ
• バンヤンスイッチ
• 太った木
• オメガネットワーク