(57)【要約】本特許請求の範囲で定まる一発明は、交差接続デバイスのスイッチ行列ユニットにおけるスイッチ行列ユニットプログラミングを生成する方法を提供する。本方法は、交差接続デバイスの入力ポートを特定し、かつ、その特定された入力ポートに接続するのに望ましい交差接続デバイスの出力ポートを特定する情報を取得するステップを含む。本方法はさらに、その特定された入力ポートを提供する交差接続デバイス内のスイッチ行列ユニットから、その望ましい出力ポートを提供する交差接続デバイス内のスイッチ行列ユニットまでの経路を特定するステップを含む。本方法はさらに、特定された入力ポートから望ましい出力ポートへの接続を可能にするために、充分なチャネルが、特定された経路内に存在するかどうかを判断するステップを含む。また、本方法は、特定された入力ポートから望ましい出力ポートへの接続を可能にする、特定された経路内の特定のチャネルを特定するステップを含む。さらに、本方法は、特定された入力ポートから望ましい出力ポートへの接続を可能にするために、交差接続デバイス内の複数のスイッチ行列ユニットで作成されなければならない接続を特定する情報を、プログラミングデータ構造内に格納するステップを含む。
2005532729.tif 000002
【特許請求の範囲】
【請求項１】
多段にCLOS配置され、各々が複数の入力ポート及び出力ポートを持つ複数のスイッチ行列ユニットを備えるスイッチ行列サブシステム、
を備え、前記スイッチ行列ユニットの少なくとも2つが多数の出力ポートを有し、これら出力ポートが、次の段のスイッチ行列ユニットの一方の入力ポートに一意に接続され、かつ、同数のその出力ポートが、前記次の段のスイッチ行列ユニットの他方の入力ポートに一意に接続され、
前記スイッチ行列サブシステムと関連付けられる複数のサブシステム入力ポート、
前記スイッチ行列サブシステムと関連付けられる複数のサブシステム出力ポート、及び
一又はそれ以上のサブシステム入力ポートに存在する一又はそれ以上の入力信号を、一又はそれ以上のサブシステム出力ポートに接続することを可能にする特定の内部交差接続を生成するように、前記スイッチ行列ユニットを指示するスイッチ行列ユニットプログラミング、
が設けられたことを特徴とするデジタル交差接続システム。
【請求項２】
前記スイッチ行列サブシステムが、各段に少なくとも2つのスイッチ行列ユニットを持つ三段アーキテクチャを備える、
請求項1記載のシステム。
【請求項３】
前記第一の段のスイッチ行列ユニットの入力ポートが、前記スイッチ行列サブシステムの入力ポートであり、前記第三の段のスイッチ行列ユニットの出力ポートが、前記スイッチ行列サブシステムの出力ポートであり、第一の段及び第二の段の各スイッチ行列ユニットは出力ポートを有し、これら出力ポートが、当該スイッチ行列ユニットと関連付けられた出力セットA又は出力セットBのいずれかに割り当てられ、スイッチ行列ユニットの出力セットA内の各出力ポートが、次の段の2つのスイッチ行列ユニットの一方の入力ポートに一意に繋がれており、スイッチ行列ユニットの出力セットB内の各出力ポートが、前記次の段の2つのスイッチ行列ユニットの他方の入力ポートに一意に繋がれている、
請求項2記載のシステム。
【請求項４】
特定のサブシステム入力ポート、及び、前記特定のサブシステム入力ポートに接続するのに望ましいサブシステム出力ポートを特定する情報を取得し、
前記交差接続システム内の、前記特定のサブシステム入力ポートを提供するスイッチ行列ユニットから、前記交差接続システム内の、前記望ましいサブシステム出力ポートを提供するスイッチ行列ユニットまでの経路を特定し、
前記特定された経路内に、前記特定のサブシステム入力ポートから前記望ましいサブシステム出力ポートへの接続を可能にするために、充分なチャネルが存在するかどうかを判断し、
前記特定のサブシステム入力ポートから前記望ましいサブシステム出力ポートへの接続を可能にする、前記特定された経路内の特定のチャネルを特定し、及び、
前記特定のサブシステム入力ポートから前記望ましいサブシステム出力ポートへの前記接続を可能にするために、前記交差接続システム内の複数のスイッチ行列ユニットで作成されなければならない接続を特定する情報を、プログラミングデータ構造内に格納する
ステップを持つ方法により、前記スイッチ行列ユニットプログラミングを生成する請求項1記載のシステム。
【請求項５】
各スイッチ行列ユニットが正方行列を備える、
請求項1記載のシステム。
【請求項６】
どのスイッチ行列ユニットの入力ポートの数も同じである、
請求項1記載のシステム。
【請求項７】
各々が入力ポート及び出力ポートを持つ複数のスイッチ行列ユニット、
を備え、前記スイッチ行列ユニットの少なくとも6つが、各段に2つのスイッチ出力ユニットを持つ3つの段に組織化され、前記第一の段のスイッチ行列ユニットの入力ポートが、前記機構の入力ポートであり、前記第三の段のスイッチ行列ユニットの出力ポートが、前記機構の出力ポートであり、第一の段及び第二の段の各スイッチ行列ユニットが出力ポートを有し、これら出力ポートが、当該スイッチ行列ユニットと関連付けられた出力セットA又は出力セットBのいずれかに割り当てられ、スイッチ行列ユニットの出力セットA内の各出力ポートが、次の段の2つのスイッチ行列ユニットの一方の入力ポートに一意に繋がれており、スイッチ行列ユニットの出力セットB内の各出力ポートが、前記次の段の2つのスイッチ行列ユニットの他方の入力ポートに一意に繋がれていて、各スイッチ行列ユニットが、その入力ポートとその出力ポートの間の接続を提供するようにプログラム可能であり、
第一の段、第二の段、及び第三の段の各スイッチ行列ユニットにおける、前記機構の入力の1つに生じる信号を前記機構の出力の少なくとも1つに切り替えることを可能にする内部接続を各々確立するように、前記第一の段のスイッチ行列ユニットの少なくとも1つ、前記第二の段のスイッチ行列ユニットの少なくとも1つ、及び、前記第三の段のスイッチ行列ユニットの少なくとも1つを指示するスイッチ行列ユニットプログラミング、
が設けられたことを特徴とするスイッチング機能を実行する機構。
【請求項８】
前記機構の入力ポートを特定し、かつ、前記特定された入力ポートに接続するのに望ましい前記機構の出力ポートを特定する情報を取得し、
前記機構内の、前記特定された入力ポートを提供するスイッチ行列ユニットから、前記機構内の、前記望ましい出力ポートを提供するスイッチ行列ユニットまでの経路を特定し、
前記特定された入力ポートから前記望ましい出力ポートへの接続を可能にするために、充分なチャネルが、前記特定された経路内に存在するかどうかを判断し、
前記特定された入力ポートから前記望ましい出力ポートへの接続を可能にする、前記特定された経路内の特定のチャネルを特定し、
前記特定された入力ポートから前記望ましい出力ポートへの前記接続を可能にするために、前記機構内の複数のスイッチ行列ユニットで作成されなければならない接続を特定する情報を、プログラミングデータ構造内に格納する
ステップを持つ方法を使用して、前記プログラミングを生成する請求項7記載の機構。
【請求項９】
交差接続デバイスのスイッチ行列ユニットにおけるスイッチ行列ユニットプログラミングを生成する方法であって、
前記交差接続デバイスの入力ポートを特定し、前記特定された入力ポートに接続するのに望ましい前記交差接続デバイスの出力ポートを特定する情報を取得し、
前記交差接続デバイス内の、前記特定された入力ポートを提供するスイッチ行列ユニットから、前記交差接続デバイス内の、前記望ましい出力ポートを提供するスイッチ行列ユニットまでの経路を特定し、
前記特定された入力ポートから前記望ましい出力ポートへの接続を可能にするために、充分なチャネルが、前記特定された経路内に存在するかどうかを判断し、
前記特定された入力ポートから前記望ましい出力ポートへの接続を可能にする、前記特定された経路内の特定のチャネルを特定し、
前記特定された入力ポートから前記望ましい出力ポートへの前記接続を可能にするために、前記交差接続デバイス内の複数のスイッチ行列ユニットで作成されなければならない接続を特定する情報を、プログラミングデータ構造内に格納する
ステップを含むことを特徴とする方法。
【請求項１０】
前記プログラミングデータ構造を使用して、前記交差接続デバイスのスイッチ行列ユニットにおける、前記特定された入力を前記望ましい出力に接続するために前記スイッチ行列ユニット内で作成されなければならない内部接続を特定する前記スイッチ行列ユニットプログラミングを生成するステップ、
をさらに含む請求項9記載の方法。
【請求項１１】
前記経路を特定するステップが、代替の経路ではなく、より好ましい経路を特定することを含む、
請求項9記載の方法。
【請求項１２】
前記より好ましい経路を特定するステップが、前の繰り返しにおいて、前記代替の経路を特定したとき、前記より好ましい経路を特定することを含む、
請求項11記載の方法。
【請求項１３】
前記経路を特定するステップが、より好ましい経路ではなく、代替の経路を特定することを含む、
請求項9記載の方法。
【請求項１４】
前記代替の経路を特定するステップが、前の繰り返しにおいて、前記より好ましい経路を特定したとき、前記代替の経路を特定することを含む、
請求項13記載の方法。
【請求項１５】
前記充分なチャネルが存在するかどうかを判断するステップが、
前記複数のスイッチ行列ユニットにおける利用可能な出力ポートの数を記憶すること、及び、
前記特定された経路内に出力ポートを持つ各スイッチ行列ユニットが、利用可能な出力ポートを持つかどうかを判断すること、
を含む請求項9記載の方法。
【請求項１６】
前記記憶するステップが、利用可能でない出力ポートの数を憶えていることを含む、
請求項15記載の方法。
【請求項１７】
前記特定のチャネルを特定するステップが、前記利用可能でない出力ポートのカウントを増やすことを含む、
請求項16記載の方法。
【請求項１８】
前記特定のチャネルを特定するステップが、
前記特定された経路内にあり、利用可能である、特定のスイッチ行列ユニット内の特定の出力ポートを特定すること、及び、
前記特定された入力ポートから前記望ましい出力ポートへの前記接続を作成することにおいて使用するために、前記特定された特定の出力ポートを確保すること、
を含む請求項9記載の方法。
【請求項１９】
前記特定の出力ポートを特定するステップが、
前記出力ポートに数値を割り当てること、及び、
最も低い数値を持つ利用可能な出力ポートを特定すること、
を含む、請求項18記載の方法。
【請求項２０】
前記入力ポートを特定する情報を取得するステップが、複数の入力ポート及び望ましい出力ポートのペアを特定する情報を取得することを含む、
請求項9記載の方法。
【請求項２１】
前記入力ポート及び望ましい出力ポートのペアを、同じ入口スイッチ行列ユニット及び出口スイッチ行列ユニットを持つ全てのペアが一緒に分類されるように分類する、
請求項20記載の方法。
【請求項２２】
前記複数の入力ポート及び望ましい出力ポートのペアが、一以上の出力ポートに接続される少なくとも1つの入力ポートを含む、
請求項21記載の方法。
【請求項２３】
同じ入口スイッチ行列ユニット及び複数の出口スイッチ行列ユニットを持つ前記入力ポートを、一緒に分類する、
請求項22記載の方法。
【請求項２４】
前記入力ポート及び望ましい出力ポートの全てのペアについて、請求項9記載のステップを繰り返す、
請求項23記載の方法。
【請求項２５】
同じ入口スイッチ行列ユニット及び出口スイッチ行列ユニットを持つ前記入力ポート及び望ましい出力ポートのペアのグループより前に処理するために、一以上の出力ポートに接続される前記入力ポートを選択する、
請求項24記載の方法。
【請求項２６】
少なくとも6つのスイッチ行列ユニットが、各段に2つのスイッチ行列ユニットを持つ3つの段に組織化される機構をプログラムする方法であって、
前記第一の段のスイッチ行列ユニットの入力ポートが、前記機構の入力ポートであり、前記第三の段のスイッチ行列ユニットの出力ポートが、前記機構の出力ポートであり、第一の段及び第二の段の各スイッチ行列ユニットが出力ポートを有し、これら出力ポートが、当該スイッチ行列ユニットと関連付けられた出力セットA又は出力セットBのいずれかに割り当てられ、スイッチ行列ユニットの出力セットA内の各出力ポートが、次の段の2つのスイッチ行列ユニットの一方の入力ポートに一意に繋がれており、スイッチ行列ユニットの出力セットB内の各出力ポートが、前記次の段の2つのスイッチ行列ユニットの他方の入力ポートに一意に繋がれており、各スイッチ行列ユニットが、その入力ポートとその出力ポートの間の接続を提供するようにプログラム可能であり、
前記機構の入力ポート上の信号の、前記機構の出力ポートへのパスを計算し、
前記機構の入力ポートに生じる信号を前記機構の出力ポートに接続することを可能にする内部接続を各々確立するように、前記第一の段のスイッチ行列ユニットの少なくとも1つ、前記第二の段のスイッチ行列ユニットの少なくとも1つ、及び、前記第三の段のスイッチ行列ユニットの少なくとも1つをプログラムする、
ステップを含むことを特徴とする方法。
【請求項２７】
前記計算するステップが、
前記機構内の、前記入力ポートを提供するスイッチ行列ユニットから、前記機構内の、前記望ましい出力ポートを提供するスイッチ行列ユニットまでの経路を特定すること、
前記特定された入力ポートから前記望ましい出力ポートへの接続を可能にするために、充分なチャネルが、前記特定された経路内に存在するかどうかを判断すること、及び、
前記特定された入力ポートから前記望ましい出力ポートへの接続を可能にする、前記特定された経路内の特定のチャネルを特定すること、
を含む請求項26記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、データ通信ネットワークに関するものである。特に、本発明は、交差接続のスイッチ行列に関するものである。
【０００２】
(優先権主張)
本出願は、2002年7月8日に出願された「デジタル交差接続のスイッチ行列マッピングの方法及びシステム」という名称の米国仮特許出願第60/394403号に基づく優先権を主張するものである。ここで、米国仮特許出願第60/394403号の開示全体が、引用により本出願に組み入れられる。
【背景技術】
【０００３】
トランスポートネットワークは、データ通信の技術分野でよく知られている。トランスポートネットワークは、ATMネットワーク、フレームリレーネットワーク、同期光通信ネットワーク(SONET)、同期デジタルハイアラーキ(SDH)ネットワーク等を含む。トランスポートネットワークは、典型的には、一又はそれ以上のデータ通信チャネル(又はパス)で一つに繋がれる複数のネットワーク要素(エレメント)を含む。これらネットワークエレメントは、交替で、ローカルエレメント又はネットワークに繋ぐことができる、又は、他のネットワーク構造に繋ぐことができる。
【０００４】
トランスポートネットワーク内のネットワークエレメントの多くは、1データ通信チャネルから他のデータ通信チャネルにデータを切り替えるために使用されるスイッチングハードウェアを含む。ネットワークエレメント内でのスイッチング処理は、典型的には、ハードウェア交差接続のスイッチ行列を使用して実行される。交差接続のスイッチ行列は、複数の入力ポート、複数の出力ポート、及び複数のスイッチを含む。良く知られた多くのスイッチ行列アーキテクチャが存在する。
【０００５】
(要約)
本特許請求の範囲で定まる一発明は、交差接続デバイスのスイッチ行列ユニットにおけるスイッチ行列ユニットプログラミングを生成する方法を提供する。本方法は、交差接続デバイスの入力ポートを特定し、かつ、その特定された入力ポートに接続するのに望ましい交差接続デバイスの出力ポートを特定する情報を取得するステップを含む。本方法はさらに、その特定された入力ポートを提供する交差接続デバイス内のスイッチ行列ユニットから、その望ましい出力ポートを提供する交差接続デバイス内のスイッチ行列ユニットまでの経路を特定するステップを含む。本方法はさらに、特定された入力ポートから望ましい出力ポートへの接続を可能にするために、充分なチャネルが、特定された経路内に存在するかどうかを判断するステップを含む。また、本方法は、特定された入力ポートから望ましい出力ポートへの接続を可能にする、特定された経路内の特定のチャネルを特定するステップを含む。さらに、本方法は、特定された入力ポートから望ましい出力ポートへの接続を可能にするために、交差接続デバイス内の複数のスイッチ行列ユニットで作成されなければならない接続を特定する情報を、プログラミングデータ構造内に格納するステップを含む。
【０００６】
本特許請求の範囲で定まるもう1つの発明は、多段にCLOS配置された複数のスイッチ行列ユニットを備えるスイッチ行列サブシステムを含むデジタル交差接続システム、を提供する。各スイッチ行列ユニットは、複数の入力ポート及び出力ポートを持つ。少なくとも2つのスイッチ行列ユニットは、その多数の出力ポートを、次の段のスイッチ行列ユニットの1つの入力ポートに一意に接続される。少なくとも2つのスイッチ行列ユニットは、その同数の出力ポートを、次の段の他のスイッチ行列ユニットの入力ポートに一意に接続される。デジタル交差接続システムはまた、スイッチ行列サブシステムと関連付けられる複数のサブシステム入力ポート、及び、スイッチ行列サブシステムと関連付けられる複数のサブシステム出力ポートを含む。さらに、デジタル交差接続システムは、一又はそれ以上のサブシステム入力ポートに存在する一又はそれ以上の入力信号を、一又はそれ以上のサブシステム出力ポートに接続することを可能にする特定の内部交差接続を生成するように、スイッチ行列ユニットを指示するスイッチ行列ユニットプログラミング、を含む。
【０００７】
本特許請求の範囲で定まるもう1つの発明は、少なくとも6つのスイッチ行列ユニットが、各段に2つのスイッチ行列ユニットを持つ3つの段に組織化される機構をプログラムする方法を提供する。第一の段のスイッチ行列ユニットの入力ポートは、本機構の入力ポートであり、第三の段のスイッチ行列ユニットの出力ポートは、本機構の出力ポートである。第一の段及び第二の段のどのスイッチ行列ユニットも出力ポートを有し、これら出力ポートは、そのスイッチ行列ユニットと関連付けられる出力セットA、又は出力セットBのいずれかに割り当てられる。スイッチ行列ユニットの出力セットA内の各出力ポートは、次の段の2つのスイッチ行列ユニットの一方の入力ポートに一意に繋がり、スイッチ行列ユニットの出力セットB内の各出力ポートは、次の段の2つのスイッチ行列ユニットのもう一方の入力ポートに一意に繋がる。各スイッチ行列ユニットは、その入力ポートとその出力ポートの間の接続を提供するようにプログラム可能である。本方法は、本機構の入力ポート上の信号の、本機構の出力ポートへのパスを算出するステップを含む。本方法はさらに、本機構の入力ポートに生じる信号を本機構の出力ポートに接続することを可能にする内部接続を各々確立するように、第一の段のスイッチ行列ユニットの少なくとも1つ、第二の段のスイッチ行列ユニットの少なくとも1つ、及び、第三の段のスイッチ行列ユニットの少なくとも1つをプログラムするステップを含む。
【０００８】
本特許請求の範囲で定まるもう1つの発明は、スイッチング機能を実行する機構を提供する。本機構は、各々が入力ポート及び出力ポートを持つ複数のスイッチ行列ユニットを備える。少なくとも6つのスイッチ行列ユニットが、各段に2つのスイッチ行列ユニットを持つ3つの段に組織化される。第一の段のスイッチ行列ユニットの入力ポートは、本機構の入力ポートであり、第三の段のスイッチ行列ユニットの出力ポートは、本機構の出力ポートである。第一の段及び第二の段のどのスイッチ行列ユニットも出力ポートを有し、これらの出力ポートは、そのスイッチ行列ユニットと関連付けられる出力セットA、又は出力セットBのいずれかに割り当てられる。スイッチ行列ユニットの出力セットA内の各出力ポートは、次の段の2つのスイッチ行列ユニットの一方の入力ポートに一意に繋がり、スイッチ行列ユニットの出力セットB内の各出力ポートは、次の段の2つのスイッチ行列ユニットのもう一方の入力ポートに一意に繋がる。各スイッチ行列ユニットは、その入力ポートとその出力ポートの間の接続を提供するようにプログラム可能である。本機構はさらに、第一の段、第二の段、及び第三の段の各スイッチ行列ユニットにおけるスイッチ行列ユニットプログラミングを含む。このプログラミングは、本機構の入力の1つに生じる信号を本機構の出力の少なくとも1つに切り替えることを可能にする内部接続を各々確立するように、第一の段のスイッチ行列ユニットの少なくとも1つ、第二の段のスイッチ行列ユニットの少なくとも1つ、及び、第三の段のスイッチ行列ユニットの少なくとも1つを指示する。
【０００９】
本特許請求の範囲で特定される発明をより明確に理解できるように、エレメントが、本特許請求の範囲で列挙された本発明のエレメントに対応する構造、システム、及び方法のより好ましい実施形態を、例を介して、添付図面を参照して、詳細に説明する。
【００１０】
(詳細な説明)
ここで図面を見ると、図1は、デジタル交差接続システムの一部となり得る、より好ましいスイッチ行列サブシステム100のブロック図を示している。示されたより好ましいスイッチ行列サブシステム100は、複数(この例では6個)のスイッチ行列ユニット101、102、103、104、105、106(スイッチ行列ユニットNo.1〜6)を含む。この例では、スイッチ行列ユニット101、102、103、104、105、106はCommonLispObjectSystem(CLOS)アーキテクチャで配列されて、スイッチ行列サブシステム100を形成する。示されたCLOSスイッチ行列サブシステム100は、各段に2つのスイッチ行列ユニットを持つ(すなわち、各段に対応するスイッチ行列ユニットの2つの並び)、3つの列又は段の6つのスイッチ行列ユニットを備える。この例で、各スイッチ行列ユニット101、102、103、104、105、106は、1024×1024の正方行列であり、各々1024の入力ポート及び1024の出力ポートを持ち、かつ、各々別個の特定用途向け集積回路(ASIC)内に常駐する。従って、この例示のスイッチ行列サブシステム100は、2048個の入力ポート108、及び、2048個の出力ポート110を含む。複数のスイッチ行列サブシステム100を結合して、より大きいスイッチデバイスを形成することもできるであろう、そこでは、各スイッチ行列サブシステム100が、データ語内の(2ビット分割のような)一部のデータに作用することができる。例えば、4つのスイッチ行列サブシステム100を結合して、より大きなスイッチデバイスを形成することもできるであろう、そこでは、各スイッチデバイスサブシステム100が2ビット部分のデータに作用し、スイッチデバイス全体は8ビットのデータ語に作用する。この例では、2048個の入力ポートの各々が、所定の瞬間に2ビット分の情報を入力することができ、2048個の出力ポートの各々が、所定の瞬間に2ビット分の情報を出力することができる。
【００１１】
各スイッチ行列ユニット内での出力ポートの入力ポートへのマッピング、及び、1スイッチ行列ユニットの出力ポートの、次の段のスイッチ行列ユニットの入力ポートへのマッピングを制御することにより、スイッチ行列100の出力ポートを、スイッチ行列サブシステム100の入力ポートに接続して、そのスイッチ行列サブシステム100で実行されるスイッチング機能をもたらすことができる。
【００１２】
スイッチ行列サブシステム100では、スイッチ行列ユニットNo.1〜4(それぞれ101、102、103、及び104)の各々の出力ポートが、2つの出力セットA又はBの一方に割り当てられる。示された例では、512個の出力ポートが、出力セットAに割り当てられ、かつ、512個の出力ポートが、出力セットBに割り当てられる。一段のスイッチ行列ユニット内の出力セットAの出力ポートは、同じ並びにある次の段のスイッチ行列ユニットの入力ポートにつながる。一段のスイッチ行列ユニット内の出力セットBの出力ポートは、反対側の並びにある次の段のスイッチ行列ユニットの入力ポートにつながる。例えば、スイッチ行列ユニット#1の出力セットAの各出力ポートは、スイッチ行列ユニット#3の入力ポートに一意につながり、かつ、スイッチ行列ユニット#1の出力セットBの各出力ポートは、スイッチ行列ユニット#4の入力ポートに一意につながる。スイッチ行列ユニット内では、どの入力も、出力セットAの出力ポート、又は出力セットBの出力ポートのいずれかに接続され得る。
【００１３】
スイッチ行列サブシステム100をプログラムするために典型的に使用される例示の入力は、典型的に入力ベクトルIN[4N]を備え、そこでは、N=各スイッチ行列ユニット内の入力又は出力ポートの数の1/2であり、かつ4Nは、スイッチ行列サブシステム100内の入力及び出力の全数に等しい。この例では、4Nは2048に等しい。入力ベクトルは、スイッチ行列100における望ましい入力対出力マッピングを示すIN[2048]である。例示的な入力ベクトルIN[4N]が図2に示されており、そこでは、各段のヘッデッィングは、出力ポートの場所を表し、各段に収容された情報は、図3に示すような、その出力ポートにスイッチされるべき入力ポート、又はその出力ポートの状態を示すステータス信号を表す。最初に、入力ベクトル内の全てのエントリは、4Nのような、ポートの準備されていない状態(UNEQ-P)に対応する値にセットされるであろう。出力ポートが準備されたとき、その準備された出力ポートに対するエントリが、入力ポート番号に置き換えられるであろう。
【００１４】
入力ベクトルは、図4に示すように、出力ベクトルOUT[][]に変換されるが、これは、スイッチ行列サブシステム100の出力へのスイッチ行列サブシステム100の入力の望ましいマッピングを行うために、各スイッチ行列内で作られなければならない接続を示している。各列は、スイッチ行列ユニットにおける出力ポートを表し、各行は、特定のスイッチ行列ユニットを表す。一又はそれ以上のアルゴリズムを利用して、出力ベクトルOUT[][]を生成するために各スイッチ行列ユニット内で作られなければならない接続を特定することができる。2つの例示のアルゴリズムを、以下に説明する。
【００１５】
スイッチ行列サブシステム100は、ユニキャスト(通常)接続、及び、ブロードキャスト接続を処理できる能力がある。通常の接続は、1つの出力が1つの入力に接続される、スイッチ行列サブシステム100内の接続である。通常の接続で、信号は、スイッチ行列ユニット#1又は#2のいずれかの1つの入力ポートに接続されてスイッチ行列サブシステム100の中に入り、スイッチ行列ユニット#5又は#6のいずれかの1つの出力ポートに接続されてスイッチ行列を出る。
【００１６】
第一の段の各スイッチ行列ユニット(スイッチ行列ユニット#1及び#2)について、第三の段のスイッチ行列ユニット(スイッチ行列ユニット#5及び#6)の1つの出力ポートへの2つの予想される経路がある。予想される経路の一方が、より好ましい経路として指定され、もう一方の経路が、代替の経路として指定される。どちらがより好もしい経路であるか、及び、どちらが代替の岐路であるかの決定は、本発明を実践するのに重要ではない。図5は、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5を出る信号の予想される経路を示している。図6は、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#6を出る信号の予想される経路を示している。図7は、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5を出る信号の予想される経路を示している。図8は、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#6を出る信号の予想される経路を示している。図12は、例示のスイッチ行列システム内での通常接続におけるより好ましい経路、及び、代替の経路の例を示している。
【００１７】
ブロードキャスト接続は、複数の出力が1つの入力に接続される、スイッチ行列サブシステム100内の接続である。ブロードキャスト接続で、信号は、スイッチ行列ユニット#1又は#2のいずれかの1つの入力ポートに接続されてスイッチ行列サブシステム100の中に入り、スイッチ行列ユニット#5及び#6双方の複数の出力ポートに接続されてスイッチ行列を出る。
【００１８】
ブロードキャスト接続では、第一の段のスイッチ行列ユニットから第三の段のスイッチ行列ユニットの各々の出力ポートまでの4つの予想される経路がある。第三の段の各スイッチ行列ユニットへの予想される経路(全部で2つの経路)の一方は、より好ましい経路として指定され、もう一方の経路は、代替の経路として指定される。図9は、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5及び#6を出る信号の全ての予想される経路の例を示している。図10は、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5及び#6を出る信号の全ての予想される経路の例を示している。図11は、ブロードキャスト接続におけるより好ましい経路、及び、代替の経路を示している。
【００１９】
出力ベクトルOUT[][]を算出するために、以下の一般則に従うことができる。第一に、第三び段のスイッチ行列ユニットの出力ポートへの第一の段のスイッチ行列ユニットの入力ポートのどの新しい接続も、スイッチ行列ユニット内の適切な出力セットで次に利用可能なパスを使って確立される。出力ベクトルOUT[][]が空のとき、通常接続の前に、ブロードキャスト接続を算出する。カウンタが、各出力セットと関連付けられる。次に利用可能な出力ポートを検索し、関連付けられた出力セットが接続で埋め尽くされているかどうかを判断するために、このカウンタを使用する。最初、カウンタは値0で始まる。その出力セット内の出力ポートを使用する新しい接続が確立される度に、それを増やす。例えば、スイッチ行列ユニットNo.1〜4の各々が、各出力セット内に512個の出力ポートを持つ2つの出力セットを有すると仮定すると、0から512まで増加し得る、スイッチ行列ユニット#1の出力セットAと関連付けられるカウンタが存在するであろう。この出力セット内の出力ポートを使って接続が作られる度に、カウンタは増やされるであろう。カウンタが値512に達したとき、この出力セット内の出力ポートを使って、もはや接続を作ることはできない。
【００２０】
通常接続で、以下の手順を続けることができる。スイッチ行列サブシステム100の入力ポートと出力ポートの間の望ましい接続について、第一に、その接続のための全体的な経路を定めるであろう。例えば、スイッチ行列ユニット#1上の入力ポートからスイッチ行列ユニット#5のポートへの接続を確立することが望まれる場合には、第一に、より好ましい経路が利用可能であるかどうかを判断するために調べるであろう。図5に示すように、より好ましい経路は、出力セット1A(スイッチ行列ユニット#1の出力セットA)、出力セット3A(スイッチ行列ユニット#3の出力セットA)、スイッチ行列ユニット#5へと横断するであろう。それゆえ、出力セット1A、及び出力セット3Aと関連付けられたカウンタを調べて、利用可能なポートがあるかどうかを判断するであろう。出力セット1A、及び出力セット3Aの両方に利用可能なポートが存在する場合には、接続を提供するために、特定のチャネルを確立することができる。この説明の目的のため、チャネルは、スイッチ行列ユニット入力ポートの、同じスイッチユニットと関連付けられるスイッチ行列ユニット出力ポートへの接続とする。この例では、スイッチ行列ユニット#1の入力ポートを出力セット1A内の次に利用可能な出力ポートにマッピングすることにより、チャネルが確立されるであろう、及び、選択された出力セット1Aのその出力ポートに接続されたスイッチ行列ユニット#3の入力ポートを、出力セット3A内の次に利用可能な出力ポートにマッピングすることにより、チャネルが確立されるであろう。出力セット1A及び3Aと関連付けられたカウンタが、増やされるであろう。次に、選択された出力セット3Aの出力ポートに接続されたスイッチ行列#5の入力ポートを、スイッチ行列サブシステム100の望ましい出力ポートにマップして、そのマッピングを完了するであろう。出力ベクトルOUT[][]内の適切なエントリが、選択されたチャネルを反映するように作成されるであろう。このマッピングを行うようにスイッチ行列ユニットをプログラムするために、その出力ベクトルOUT[][]を使用することができるであろう。
【００２１】
スイッチ行列サブシステム100は、スイッチ行列ユニットにこれらの内部接続を作らせるための様々な形式のスイッチ行列プログラミングを持つことができる。このプログラミングは、メモリ内に格納された指示、そのスイッチ行列ユニットが作用することのできるバイナリ値、ソフトウェアコード、ASICのようなプログラム可能な回路素子、フィールドプログラマブル論理アレイ、その他の論理アレイ、又は、そのスイッチ行列ユニットに様々な内部接続を作らせるための他の構造を備えることができる。この指示、バイナリ値、ソフトウェアコード等は、読み出し専用メモリ(ROM)、又はランダムアクセスメモリ(RAM)のようなメモリデバイス内に格納することができる。
【００２２】
出力セット1A、又は出力セット3Aのいずれかに利用可能なポートが全くない場合には、代替の経路を選択するであろう。この場合、出力セット1B及び出力セット4Bと関連付けられたカウンタを調べて、利用可能なポートがあるかどうかを判断するであろう。出力セット1B及び出力セット4Bの両方の中に利用可能なポートがある場合には、スイッチ行列ユニット#1の入力ポートを、出力セット1B内の次に利用可能な出力ポートにマッピングすることにより、チャネルを確立するであろう、及び、出力セット1Bの選択された出力ポートに接続されたスイッチ行列ユニット#4の入力ポートを、出力セット4B内の次に利用可能な出力ポートにマッピングすることにより、チャネルを確立するであろう。出力セット1B及び4Bと関連付けられたカウンタが増やされるであろう。次に、出力セット4Bの選択された出力ポートに接続されたスイッチ行列ユニット#5の入力ポートを、スイッチ行列サブシステム100の望ましい出力ポートにマッピングすることにより、もう1つのチャネルが確立され、マッピング例を完了するであろう。出力ベクトルOUT[][]内の適切なエントリが、選択されたチャネルを反映するように作られるであろう。このマッピングを行うようにスイッチ行列ユニットをプログラムするために、その出力ベクトルOUT[][]を使用することができるであろう。
【００２３】
ブロードキャスト接続では、次のステップを適用することができるであろう。望ましいどのブロードキャスト接続においても、スイッチ行列ユニット#1又はスイッチ行列ユニット#2のいずれかから、スイッチ行列ユニット#5及びスイッチ行列ユニット#6両方への接続が存在する。ブロードキャスト接続の要求を、1つは、(例えば)スイッチ行列ユニット#1の入力ポートからスイッチ行列ユニット#5の望ましい出力ポートへ、もう1つは、スイッチ行列ユニット#1の同じ入力ポートからスイッチ行列ユニット#6の望ましい出力ポートへ、の2つの接続要求に分ける。図12に示すより好ましい経路、及び代替の経路を参照しながら、第一の接続要求で開始して、出力セットと関連付けられた適切なカウンタの値を調べて、スイッチ行列ユニット#1とスイッチ行列ユニット#5の間の利用可能なチャネルが、可能な場合にはより好ましい経路を使っている経路を定めなさい。次に、出力セットと関連付けられた適切なカウンタの値を調べて、スイッチ行列ユニット#1とスイッチ行列ユニット#6の間の利用可能なチャネルが、可能な場合にはより好ましい経路を使っている経路を定める。注意：第一の接続において代替のパスを使用しなければならなくても、次に、第二の接続においてより好ましいパスを取得できることも在り得る。両方の接続要求について、次に利用可能なポートを選択することにより、チャネルを確立し、影響を受けるカウンタを増やし、及び、選択されたチャネルを反映するように出力ベクトルOUT[][]を更新する。
【００２４】
図13に示すように、複数の出力ポートにブロードキャストされた信号があるとき、上で説明したステップが解に収束することができない幾つかのシナリオが存在する。この例では、各スイッチ行列ユニットは、2つの入力ポート及び2つの出力ポートを持つ。入力1から出力1及び出力3へブロードキャストし、入力3から出力2への通常接続を作る場合には、入力4から出力4への通常接続を作ることはできない。ブロードキャスト接続が作られるときに生じる制約は、以下に説明するマッピングアルゴリズムと共に説明する。
【００２５】
第一の例示のマッピングアルゴリズム
以下で説明する例示のマッピングアルゴリズムのベースを形成する多数の提案が続く。
【００２６】
提案1
異なるスイッチ行列ユニット間の2Nの信号の容量が守られる限り、個々のスイッチ行列ユニットについて、入力ポートの正確な数を抽出することができ、かつ、出力ポートの正確な数を抽出することができる。個々に、各スイッチ行列ユニットは正方行列である。どの入力ポートも、一又はそれ以上の出力ポートのいずれかに接続されることができる。従って、一スイッチ行列ユニットの中に入る信号の順序は、重要でなく、抽出することができる。例えば、0から2N-1までの入力接続を持つ第一のスイッチ行列ユニットについて、第一の信号は、スイッチ行列ユニットの入力ポートiに入り、ここでiは0≦i<2Nであり、かつ、スイッチ行列ユニットの出力ポートpに出て、ここでpは0≦p<2Nである。第二の信号は、スイッチ行列ユニットの入力ポートjに入り、ここでjは0≦j<2Nであり、かつ、スイッチ行列ユニットの出力ポートqに出て、ここでqは0≦q<2Nである。i<jであると仮定すると、i及びjは交換可能であることを示すことができる。個々のスイッチ行列ユニットにおいて、如何なる入力も、いずれかの出力に接続することが可能であるので、次の接続の全て、すなわち、iからpへ、jからqへ、iからqへ、及びjからpへ、が有効である。それゆえ、第一の信号が、入力ポートiではなく、入力ポートjに入った場合には、それをポートpへ出力することもまたできるであろう。また、第二の信号が、入力ポートjではなく、入力ポートiに入った場合には、それをポートqへ出力することもまたできるであろう。
【００２７】
提案1を使って、例示のシステムでは、信号は、スイッチ行列ユニット#1(入口スイッチ行列ユニット)に入り、スイッチ行列ユニット#5(出口スイッチ行列ユニット)又はスイッチ行列ユニット#6(出口スイッチ行列ユニット)のいずれか、又は両方(マルチキャスト信号の場合)に出る。同じように、信号は、スイッチ行列ユニット#2(入口スイッチ行列ユニット)に入り、スイッチ行列ユニット#5又はスイッチ行列ユニット#6のいずれか、又は両方に出る。
【００２８】
結果として、以下の異なる経路が提案される、すなわち、
スイッチ行列ユニット#1から、スイッチ行列ユニット#5へ、
スイッチ行列ユニット#1から、スイッチ行列ユニット#6へ、
スイッチ行列ユニット#1から、スイッチ行列ユニット#5及びスイッチ行列ユニット#6へ、
スイッチ行列ユニット#2から、スイッチ行列ユニット#5へ、
スイッチ行列ユニット#2から、スイッチ行列ユニット#6へ、及び、
スイッチ行列ユニット#2から、スイッチ行列ユニット#5及びスイッチ行列ユニット#6へ、である。
【００２９】
提案2
スイッチ行列ユニットの入力ポートに入る信号は、次のスイッチ行列ユニットにつきたった1回、次のスイッチ行列ユニットにマルチキャストされる。2N以下の信号が、スイッチ行列ユニットから出力され得る。従って、スイッチ行列ユニットの入力ポートに接続されて入る単一信号は、そのスイッチ行列ユニットの必要とされる数の出力ポートに、マルチキャストされることができる。1つの単一信号をスイッチ行列ユニットに入力させ、多くの出力ポートにマルチキャストさせることは、多くの入力ポートに接続された入力信号の複数のコピーが、同じ出力ポートに出力されることと等価である。同じ入力信号の多くのコピーをスイッチ行列ユニットに入力させることは、スイッチ行列ユニット間の容量を消費するので、一般性を全く失うことなく、各信号の1つのコピーを各信号行列ユニットに入力させることに、システムを制限すべきである。
【００３０】
この提案は、この例のスイッチ行列ユニット#5及び#6には当てはまらない。実際、提案2に従うことにより、スイッチ行列ユニット#5及びスイッチ行列ユニット#6で、殆どのマルチキャストを実行することがより好ましい。それは、信号が、何の制約もなくマルチキャストされることができるその最終宛先(スイッチ行列ユニット#5、又はスイッチ行列ユニット#6)に到達するまで、スイッチ行列ユニット間の接続の余っているリソースが、提案2によって保持されるからである。
【００３１】
提案3
スイッチ行列ユニット#1から一意にスイッチ行列ユニット#5に達する信号は、マルチキャストされない。スイッチ行列ユニット#1から一意にスイッチ行列ユニット#6に達する信号も、マルチキャストされない。スイッチ行列ユニット#2から一意にスイッチ行列ユニット#5に達する信号も、マルチキャストされない。スイッチ行列ユニット#2から一意にスイッチ行列ユニット#6に達する信号も、マルチキャストされない。スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6に達する信号は、スイッチ行列ユニット#1、スイッチ行列ユニット#3、又はスイッチ行列ユニット#4のいずれかで、一度だけマルチキャストされる。スイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6に達する信号は、スイッチ行列ユニット#2、スイッチ行列ユニット#3、又はスイッチ行列ユニット#4のいずれかで、一度だけマルチキャストされる。
【００３２】
提案4
どのマルチキャスト信号も、スイッチ行列ユニット#1又はスイッチ行列ユニット#2のいずれかに向けて、まさに1つの使われていない入力ポートを出発する。この例における出力ポートの数は、スイッチ行列ユニット#5の出力ポートの数にスイッチ行列ユニット#6の出力ポートの数を加えたものである(この例では4N)。この例における入力ポートの数もまた4Nである。ある入力ポートに入る単一信号が、k個の出力ポートに出力される場合には、他の信号のために利用可能なたった4N-kの出力ポートしか存在しない。出力ポートは、一以上の入力ポートの信号を受け取ることができないので、たった4N-k個の入力ポートしか使用することができない。その場合、使われていない入力ポートの数はk-1である。マッピングアルゴリズムは、スイッチ行列ユニット#1及び#2上の使用されていない入力ポートの正確な数(直前の例では、k-1)を考慮に入れる。
【００３３】
提案5
スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への一信号について、スイッチ行列ユニット#1に使用されていない入力ポートが存在する場合には、そのスイッチ行列ユニット#1の使用されていない入力ポートの数を1つずつ減らさなければならず、スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への接続を、2つの接続、すなわち一方は、スイッチ行列ユニット#1からスイッチ行列ユニット#5への接続、もう一方は、スイッチ行列ユニット#1からスイッチ行列ユニット#6への接続、で置き換えることができる。また、スイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への一信号についても、スイッチ行列ユニット#2に使用されていない入力ポートがある場合には、スイッチ行列ユニット#2の使用されていない入力ポートの数を１つ減らさなければならず、スイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への接続を、2つの接続、すなわち一方は、スイッチ行列ユニット#2からスイッチ行列ユニット#5への接続、もう一方は、スイッチ行列ユニット#2からスイッチ行列ユニット#6への接続、で置き換えることができる。
【００３４】
同じ入口行列ユニットに、利用可能な使用されていない入力ポートが存在するとき、スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への接続について4つの予想される代用が存在する。どの代用も、2つの接続、すなわち一方は、スイッチ行列ユニット#1からスイッチ行列ユニット#5への接続、もう一方は、スイッチ行列ユニット#1からスイッチ行列ユニット#6への接続、から構成される。スイッチ行列ユニット#2から発する接続についても、同じことが言える。
【００３５】
提案6
スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への一信号について、スイッチ行列ユニット#1に使われていない入力ポートが全く存在しない場合には、スイッチ行列ユニット#2にそれは存在する。その場合、スイッチ行列ユニット#2の使われていない入力ポートが「捕らえられ」、スイッチ行列ユニット#2の使われていない入力ポートの数を1つ減らさなければならず、スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への接続は、スイッチ行列ユニット#1及びスイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への2つの予想される接続で置き換えられる。また、スイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への一信号について、スイッチ行列ユニット#2に使われていない入力ポートが全くない場合には、スイッチ行列ユニット#1にそれは存在する。その場合、スイッチ行列ユニット#1の使われていない入力ポートが「捕らえられ」、スイッチ行列ユニット#1の使われていない入力ポートの数を1つ減らさなければならず、スイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への接続が、スイッチ行列ユニット#1及びスイッチ行列ユニット#2からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への2つの予想される接続で置き換えられる。
【００３６】
起点と同じ入口スイッチ行列ユニットに、利用可能な使われていない入力ポートが全く存在しないとき、スイッチ行列ユニット#1からスイッチ行列ユニット#5及びスイッチ行列ユニット#6への接続について、2つの考えられる代用が存在する。各代用は、2つの接続、すなわち一方は、スイッチ行列ユニット#1からスイッチ行列ユニット#5への接続、もう一方は、スイッチ行列ユニット#1からスイッチ行列ユニット#6への接続、の(拒否されない)有効な組み合わせから構成される(拒否される組み合わせは、2つの接続が、スイッチ行列ユニット#3又はスイッチ行列ユニット#4で合流しないものである)。スイッチ行列ユニット#2から発する接続についても、同じことが言える。
【００３７】
従って、そのアルゴリズムにおいて、以下の変数を使用する。
c15:   一意に、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5に出力する信号の数(どの信号も、考えられる2つのパスをとることができる)
c16:   一意に、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#6に出力する信号の数(どの信号も、考えられる2つのパスをとることができる)
c25:   一意に、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5に出力する信号の数(どの信号も、考えられる2つのパスをとることができる)
c26:   一意に、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#6に出力する信号の数(どの信号も、考えられる2つのパスをとることができる)、及び、
csp:   同じスイッチ行列ユニットで、使用されていない入力ポートを全く「捕らえる」ことができないとき、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5及びスイッチ行列ユニット#6に出力する信号の数、又は、同じスイッチ行列ユニットで、使用されていない入力ポートを全く「捕らえる」ことができないとき、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5及びスイッチ行列ユニット#6に出力する信号の数(どの信号も、考えられる2つのパスをとることができる)
【００３８】
同じスイッチ行列ユニットで、使われていない入力ポートを「捕らえる」ことができるとき、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5及びスイッチ行列ユニット#6に出力する信号の数は、実際には、c15の中で1と数え、またc16の中でも1と数えることに注意する。また、同じスイッチ行列ユニットで、使われていない入力ポートを「捕らえる」ことができるとき、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5及びスイッチ行列ユニット#6に出力する信号の数は、実際には、c25の中で1と数え、またc26の中でも1と数える。
【００３９】
提案7
以下の4つの不等式が、c15、c16、c25、c26、cspの値の上限を定める。不等式は、全てのスイッチ行列ユニット間の容量(線)を表す。スイッチ行列ユニット#1を発する全ての信号は、c15、c16、又はcspのいずれかでカウントされる。スイッチ行列ユニット#1を発する全てのアークの容量は、N+Nで制限されるので、式(1)は正しい。また、スイッチ行列ユニット#2を発する全ての信号は、c25、c26、又はcspのいずれかでカウントされる。再び、スイッチ行列ユニット#2を発する全てのアークの容量は、N+Nで制限されるので、式(2)は正しい。この証明はまた、スイッチ行列ユニット#5及びスイッチ行列ユニット#6に到着するアークの容量についても有効であり、そのため、式(3)及び(4)は正しい。
c15+c16+csp≦2N        (1)
c25+c26+csp≦2N        (2)
c15+c25+csp≦2N        (3)
c16+c26+csp≦2N        (4)
【００４０】
提案8
以下の不等式は等価である。
c15+c16+csp≦2N  ⇔  c15/2+c16/2+csp/2≦N        (5)
c25+c26+csp≦2N  ⇔  c25/2+c26/2+csp/2≦N        (6)
c15+c25+csp≦2N  ⇔  c15/2+c25/2+csp/2≦N        (7)
c16+c26+csp≦2N  ⇔  c16/2+c26/2+csp/2≦N        (8)
【００４１】
前で説明したように、考えられる異なるパスのどのカテゴリにおいても、各信号について考えられる2つのパスが存在する。そのため、この問題の解法は、パスのカテゴリの各々において、考えられる2つのパスの各々のどのくらいを使用すべきかを見つけることである。考えられるパスを厳密に同じ量で使用する解法を提案する。この解法は、以下で表される。
一意に、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#3を通り抜け、スイッチ行列ユニット#5に出力するc15/2個の信号、及び、一意に、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#4を通り抜け、スイッチ行列ユニット#5に出力するc15/2個の信号。
一意に、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#3を通り抜け、スイッチ行列ユニット#6に出力するc16/2個の信号、及び、一意に、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#4を通り抜け、スイッチ行列ユニット#6に出力するc16/2個の信号。
一意に、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#3を通り抜け、スイッチ行列ユニット#5に出力するc25/2個の信号、及び、一意に、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#4を通り抜け、スイッチ行列ユニット#5に出力するc25/2個の信号。
一意に、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#3を通り抜け、スイッチ行列ユニット#6に出力するc26/2個の信号、及び、一意に、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#4を通り抜け、スイッチ行列ユニット#6に出力するc26/2個の信号。
スイッチ行列ユニット#1及びスイッチ行列ユニット#2に入り、スイッチ行列ユニット#5及びスイッチ行列ユニット#6に出力し、両方ともスイッチ行列ユニット#3を通り抜けるcsp/2個の信号、及び、スイッチ行列ユニット#1及びスイッチ行列ユニット#2に入り、スイッチ行列#5及びスイッチ行列ユニット#6に出力し、両方ともスイッチ行列ユニット#4を通り抜けるcsp/2個の信号。
【００４２】
提案された解法のため、スイッチ行列ユニット間のアーク消費を計算する。
スイッチ行列ユニット#1とスイッチ行列ユニット#3の間：  c15/2+c16/2+csp/2
スイッチ行列ユニット#1とスイッチ行列ユニット#4の間：  c15/2+c16/2+csp/2
スイッチ行列ユニット#2とスイッチ行列ユニット#3の間：  c25/2+c26/2+csp/2
スイッチ行列ユニット#2とスイッチ行列ユニット#4の間：  c25/2+c26/2+csp/2
スイッチ行列ユニット#3とスイッチ行列ユニット#5の間：  c15/2+c25/2+csp/2
スイッチ行列ユニット#3とスイッチ行列ユニット#6の間：  c16/2+c26/2+csp/2
スイッチ行列ユニット#4とスイッチ行列ユニット#5の間；  c15/2+c25/2+csp/2
スイッチ行列ユニット#4とスイッチ行列ユニット#6の間：  c16/2+c26/2+csp/2
【００４３】
これら全ての前の合計は、式(5)、(6)、(7)、又は(8)のいずれかであると認めることができるので、提案された解法は、乏しいリソースの制約、すなわちスイッチ行列ユニット間の容量に違反しない。
【００４４】
注：奇数の場合、整数値のみを使って解法を構築し、絶対に2**5=32より少ない列挙により最終選択を解く。そのため、その提案された解法について、提案8を使用することにより、その提案された解法は有効と認定される。
【００４５】
前の提案から、様々なアルゴリズムが、非常に短く、決定的、かつ有限な時間で、如何なる入力に対する解も作り出すことができる。
【００４６】
高度なアルゴリズム
第一の例示のアルゴリズムの簡単な説明を以下につづける。
1)サイズ4Nの新しい配列NEW_OUT[]を作成し、それは、各入力ポートを特徴付ける(配列内の各インデックスは、対応する入力ポートを特定する)。例を図14で示す。その配列内の各エントリーは4つのフィールドを持つ、すなわち、
Boolean「InputGoesToSwitchMatrixUnit#5(入力がスイッチ行列ユニット#5へ行く)」
Boolean「InputGoesToSwitchMatrixUnit#6(入力がスイッチ行列ユニット#6へ行く)」
Boolean「InputCapturedAnUnusedOnSameSwitchMatrixUnit(同じスイッチ行列ユニット上で捕らえられる、使用されていない入力)」、及び、
Boolean「InputCapturedAnUnusedOnOtherSwitchMatrixUnit(他のスイッチ行列ユニット上で捕らえられる、使用されていない入力)」、
(デフォルトは、全ての値についてFalse(偽))である。
【００４７】
2)各出力ポートiについて、入力ポートj=IN[i]を獲得する。出力ポートiがスイッチ行列ユニット#5の一部である場合には、OUT[j][「InputGoesToSwitchMatrixUnit#5」]=true(真)、と書く、又は、出力ポートiがスイッチ行列ユニット#6の一部である場合には、OUT[j][「InputGoesToSwitchMatrixUnit#6」]=true(真)、と書く。
【００４８】
3)それが行われたら、スイッチ行列ユニット#1、及びスイッチ行列ユニット#2内の使用されていない入力ポートの数を計算し、それらの値をそれぞれ、「UnusedInputPortSwitchMatrixUnit#1」及び「UnusedInputPortSwitchMatrixUnit#2」に格納する。使用されていない入力ポートは、特定するのが容易であり、それらは、「InputGoesToSwitchMatrix#5」及び「InputGoesToSwitchMatrix#6」の両方において、false(偽)の値を持つ。
【００４９】
4)各スイッチ行列ユニットaの各入力ポートjについて、入力ポートjが、「InputGoesToSwitchMatrix#5」及び「InputGoesToSwitchMatrix#6」の両方ともtrue(真)にセットされ、かつ、「UnusedInputPortSwitchMatrixUnit#a」がゼロでない場合には、OUT[j][「InputCapturedAnUnusedOnSameSwitchMatrixUnit」]=true(真)と書き、かつ、「UnusedInputPortSwitchMatrixUnit#a」を減らす。そうでない場合には、OUT[j][「InputCapturedAnUnusedOnOtherSwitchMatrixUnit」]=true(真)と書き、かつ、もう一方の「UnusedInputPortSwitchMatrixUnit#x」を減らす。注：常に、充分な使用されていないポートが存在しているべきである。そうでない場合には、無効データにより、エラーが引き起こされる。前の提案を参照しなさい。
【００５０】
5)前述の節の規則に従って、c15、c16、c25、c26、cspの値を計算する。
【００５１】
6)前で説明したように、係数1/2を使う有効な解法が存在する。IN[]配列内の各出力について、OUT[]配列内でのカテゴリを特定し、その解法の1/2という係数を維持するように、正しいパスを選択する(多くの出力が共通入力を共有することを、思い出しなさい)。
【００５２】
従って、このアルゴリズムは線形時間で実行される。このように、より少ないハードウェアコンポーネントを使用して、デジタル交差接続製品の信号のルーティングに、解法が与えられる。
【００５３】
第一の例示のアルゴリズムのより詳細な説明が続く。
【００５４】
ステップ0
サイズ4NのIN[]アレイを検索する、ここで、2Nは一つのスイッチ行列ユニット上のポート数に等しい。アレイのインデックスの位置は、第一の段のスイッチ行列ユニットの入力ポート番号を表す。アレイの第一の半分(インデックス0〜2N-1)は、スイッチ行列ユニット#1の入力ポートを表す。アレイの第二の半分(インデックス2N〜4N-1)は、スイッチ行列ユニット#2の入力ポートを表す。
【００５５】
各フィールドにおける可能な値は、0から4N-1までの範囲の整数である。これらの値は、スイッチ行列ユニット#5又はスイッチ行列ユニット#6の宛先ポートを表す。0から2N-1までの値は、スイッチ行列ユニット#5のポートを表し、2Nから4N-1までの値は、スイッチ行列ユニット#6のポートを表す。
(1)0〜4N-1の値  -  入力ポートアドレス
(2)4Nという値  -  UNEQ-P状態(準備されていない)
(3)4N+1という値  -  AIS-P状態(警報信号)
【００５６】
ステップ1
二次元のOUT[][]アレイを作成する。第一次元は、スイッチ行列ユニットの数と等しいサイズMである。行表現である第一次元は、第一のインデックス値+1のスイッチ行列ユニットに対応する(注：Mがスイッチ行列ユニットの数であるとき、インデックス値は0からM-1までの範囲である。我々の番号付けの規則は、0で開始する位置の値によって、及び、1で始まるスイッチ行列ユニットによって異なるので、対応するスイッチ行列ユニットの数は、M=1である)。
【００５７】
列は、サイズ2Nであるアレイの第二次元で表され、ここでNは、スイッチ行列ユニットの半分にあるポート数に等しい。アレイの第二次元のインデックスの位置は、スイッチ行列ユニットの出力ポート番号を表す。各フィールドにおける可能な値は、0から2N-1までの範囲の整数である。これらの値は、スイッチ行列ユニットの入力ポートを表す。
【００５８】
どの第一及び第二の段のスイッチ行列ユニットも、2つの出力セットを各々異なるスイッチ行列ユニットに接続されるので(例えば、スイッチ行列ユニット#1が出力セットA及び出力セットBを持ち、出力セットAはスイッチ行列ユニット#3に接続され、出力セットBはスイッチ行列ユニット#4に接続される)、第一又は第二の段の如何なるスイッチ行列ユニットも、次の段の1つのスイッチ行列ユニットへの、せいぜいN個の接続しか持つことはできないことに注意する。
【００５９】
第三の段でのマルチキャストは、スイッチ行列ユニット間の乏しいリソースを消費しないので、全てのマルチキャストが、第三の段のスイッチ行列ユニット(スイッチ行列ユニット#5又はスイッチ行列ユニット#6)で行われることが理想的である。これは、第一の段のスイッチ行列ユニットからの信号が、たった1つの第三の段のスイッチ行列ユニットに向かう場合には、可能である。第一の段のスイッチ行列ユニットからの信号が、第三の段のスイッチ行列ユニットの両方に向かうとき、マルチキャストは、第二の段(より好ましい)、又は第一の段(必要な場合のみ)のいすれかで行われなければならない。さらなる説明のため、マルチキャストが第一又は第二の段で行われた場合には、信号は、マルチキャストされたとして参照される。第三の段までマルチキャストされない信号は、ユニキャストとして扱われる。
【００６０】
ステップ2
経路を定め、信号移動のための容量を計算する。
【００６１】
例：
c15を、スイッチ行列ユニット#1とスイッチ行列ユニット#5の間の信号のセットとする。c16を、スイッチ行列ユニット#1とスイッチ行列ユニット#6の間の信号のセットとする。c25を、スイッチ行列ユニット#2とスイッチ行列ユニット#5の間の信号のセットとする。cspを、スイッチ行列ユニット#1と、スイッチ行列ユニット#5及びスイッチ行列ユニット#6両方との間の信号のセット、及び、スイッチ行列ユニット#2と、スイッチ行列ユニット#5及びスイッチ行列ユニット#6両方との間の信号のセットとする。システムの制約のため、いつでも、行列内に最大2Nの信号が存在する。
【００６２】
サイズ4NのNEW_OUT[]と呼ばれる新しいアレイを作成する。NEW_OUT[]の各インデックス値は、スイッチ行列ユニット#1又はスイッチ行列ユニット#2の入力ポートに対応する。アレイの第一の半分(インデックス0〜2N-1)は、スイッチ行列ユニット#1の入力ポートを表す。アレイの第二の半分(インデックス2N〜4N-1)は、スイッチ行列ユニット#2の入力ポートを表す。各インデックスのエントリは、対応するポート上の信号を特徴付ける働きをする4個組である。
【００６３】
例：
各スイッチ行列ユニットが2N個のポートを持ち、第一の段の2つのスイッチ行列ユニットが存在する場合には、0〜4N-1までの範囲の数を割り当てることによって、スイッチ行列ユニット#1及びスイッチ行列ユニット#2の両方の各ポートに連続的に番号を付けることにより、ポートを識別することができる。それゆえ、NEW_OUT[]アレイは、4N-1行を持つ。
4個組の要素1は、InputGoesToSwitchMatrixUnit#5と名付けられる。
要素2は、InputGoesToSwitchMatrixUnit#6と名付けられる。
要素3は、InputCapturedAnUnusedOnSameSwitchMatrixUnitと名付けられる。
要素4は、InputCapturedAnUnusedOnOtherSwitchMatrixUnitと名付けられる。
【００６４】
各インデックスのエントリは、Boolean値であり、デフォルトでFALSE(偽)とセットされる。ニブル(4ビット＝1/2バイト)を割り当て、そのニブル内の個々のビットをセットすることにより、フィールドを実装することができる。
【００６５】
ステップ3：
NEW_OUT[]アレイを、第一の段のスイッチ行列ユニットに入る信号の特性を表す値で埋める。
【００６６】
例：
各出力ポートは、対応する入力ポートを持つ。IN[]アレイは、入力及び出力ポートをマップする。該当する入力ポートに対する出力ポートが、第三の段のスイッチ行列ユニットの1つにある場合には、NEW_OUT[]配列の、検討されている入力ポートに対応する位置において、InputGoesToSwitchMatrixUnit#5又はInputGoesToSwitchMatrixUnit#6のいずれかを、TRUE(真)にセットする。NEW_OUT[]配列が完全に埋まるまで、すべての入力ポートについてこの検討を実行する。
【００６７】
ステップ4：
第一の段の各スイッチ行列ユニットの使用されていない入力ポートの数を追跡するためのカウンタ変数を作成する。
【００６８】
例：
整数の変数UnusedInputPortSwitchMatrixUnit#1は、スイッチ行列ユニット#1の使用されていない入力ポートの全数を収容する。整数の変数UnusesdInputPortSwitchMatrixUnit#2は、スイッチ行列ユニット#2の使用されていない入力ポートの全数を収容する。
【００６９】
ステップ5：
使用されていない入力ポートの数を計算し、値を格納する。
【００７０】
例：
NEW_OUT[]アレイを通してスキャンする。使用されないポートは、4個組の中の、InputGoesToSwitchMatrixUnit#5及びInputGoesToSwitchMatrixUnit#6に対するエントリがFALSE(偽)である行に対応するポートである。アレイの上半分の行は、スイッチ行列ユニット#1と関連付けられ、その上半分の中の、InputGoesToSwitchMatrixUnit#5及びInputGoesToSwitchMatrixUnit#6の両方の列がFALSE(偽)であるエントリの全数を数え、結果として生じた値は、整数の変数UnusedInputPortSwitchMatrixUnit#1に格納される。
【００７１】
アレイの下半分の行は、スイッチ行列ユニット#2と関連付けられ、その下半分の中の、InputGoesToSwitchMatrixUnit#5及びInputGoesToSwitchMatrixUnit#6の両方の列がFALSE(偽)であるエントリの全数を数え、結果として生じた値は、整数の変数UnusedInputPortSwitchMatrixUnit#2に格納される。
【００７２】
ステップ6：
ポートの利用可能性に基づくスイッチ行列ユニットを通るルーティングパス、スイッチ行列ユニットを通るより好ましいルート、及び、マルチキャスト信号を生成する段を計算し、第一の段のスイッチ行列ユニット(スイッチ行列ユニット#1又はスイッチ行列ユニット#2)でマルチキャストするよりも、第二の段のスイッチ行列ユニット(スイッチ行列ユニット#3又はスイッチ行列ユニット#4)でマルチキャストすることを好むマルチキャスト信号のほうを取り、それによって、マルチキャスト、及びそれに応じた利用可能なポートの数の調整のために「捕らえられ」た入力ポートの数を計算する。
【００７３】
アレイを通して複数の工程を実行して、全接続のセット内の接続形式の各サブセットについて、接続を計算する。サブセットは、c15(スイッチ行列ユニット#1からスイッチ行列ユニット#5へのユニキャスト)、c16(スイッチ行列ユニット#1からスイッチ行列ユニット#6へのユニキャスト)、c25(スイッチ行列ユニット#2からスイッチ行列ユニット#5へのユニキャスト)、c26(スイッチ行列ユニット#2からスイッチ行列ユニット#6へのユニキャスト)、及び、csp(スイッチ行列ユニット#1又はスイッチ行列ユニット#2のいずれかから、スイッチ行列ユニット#5及びスイッチ行列ユニット#6の両方へのマルチキャスト)を含む。
ユニキャスト接続の前に、マルチキャスト接続を計算することが望ましい。
【００７４】
例：
ｃspについて接続ルートを計算するために、NEW_OUT[]アレイを通してスキャンし、InputGoesToSwitchMatrixUnit#5及びInputGoesToSwitchMatrixUnit#6の両方がTRUE(真)にセットされた4個組のエントリを探す。これらのエントリは、ポートに入る信号がマルチキャストされていることを示す。マルチキャスト動作を説明し、ポートの利用可能性を計算する。
【００７５】
第一の段の各スイッチ行列ユニット(#1及び#2)において、
入力信号がマルチキャストされており(InputGoesToSwitchMatrixUnit#5及びInputGoesToSwitchMatrixUnit#6がTRUE(真)にセットされている)、かつ、考察されているスイッチ行列ユニットに少なくとも1つの利用可能な入力ポートが存在する(スイッチ行列ユニット#1についてのUnusedInputPortSwitchMatrixUnit#1、又はスイッチ行列ユニット#2についてのUnusedInputPortSwitchMatrixUnit#2が非ゼロの値である)場合には、
【００７６】
(a)NEW_OUT[]アレイの適切な4個組において、InputCapturedAnUnusedOnSameSwitchMatrixUnitの値をTRUE(真)に等しくセットし、及び
(b)信号のより好ましいパスに沿って充分なポートが利用可能である場合には、その信号のルートに、各スイッチ行列ユニットおいて関連付けられたカウンタで与えられる、各スイッチ行列ユニットの次に利用可能なポートのポート識別子を加え、信号の代替のパスに沿って充分なポートが利用可能である場合には、その信号のルートに、各スイッチ行列ユニットの次に利用可能なポートのポート識別子を加え、不充分なポートしか利用可能でない場合には、エラーコードを返し(注-システム上の制約のため、この最後のイベントは決して起こるべきではない)、及び、
(c)配列の上半分の4個組におけるUnusedInputPortSwitchMatrixUnit#1、又は配列の下半分の4個組におけるUnusedInputPortSwitchMatrixUnit#2のいずれかの値を減らし、及び
(d)それに応じて、各スイッチ行列ユニットにおいて関連付けられたカウンタを増やして、各スイッチ行列ユニットの次に利用可能なポートを反映する。代わりに、各スイッチ行列ユニットの入力ポートの全数を表す定数値からUnusedInputPortSwitchMatrixUnit#xの値を引くことにより、次に利用可能なポート数を計算することもできる。
【００７７】
そうでない場合には、
(a)NEW_OUT[]アレイの適切な4個組おいて、InputCapturedAnUnusedOnOtherSwitchMatrixUnitの値をTRUE(真)に等しくセットし、及び
(b)信号のより好ましいパスに沿って充分なポートが利用可能である場合には、その信号のルートに、各スイッチ行列ユニットにおいて関連付けられたカウンタで与えられる、各スイッチ行列ユニットの次に利用可能なポートのポート識別子を加え、信号の代替のパスに沿って充分なポートが利用可能である場合には、その信号のルートに、各スイッチ行列ユニットの次に利用可能なポートのポート識別子を加え、不充分なポートしか利用可能でない場合には、エラーコードを返し(注-システム上の制約のため、この最後のイベントは起こるべきではない)、及び、
(c)配列の上半分の4個組におけるUnusedInputPortSwitchMatrixUnit#1、又は、配列の下半分の4個組におけるUnusedInputPortSwitchMatrixUnit#2のいずれかの値を減らし、及び、
(d)それに応じて、各スイッチ行列ユニットにおいて関連付けられたカウンタを増やして、各スイッチ行列ユニットの次に利用可能なポートを反映する。代わりに、各スイッチ行列の入力ポートの全数を表す定数値からUnusedInputPortSwitchMatrixUnit#xの値を引くことにより、次に利用可能なポート数を計算することもできる。
【００７８】
ステップ7：
マルチキャスト信号に対してあらかじめ確立された接続ルートを使って、かつ、ユニキャスト信号によって使われないマルチキャスト接続のセグメントを削除して、工程を繰り返して、ユニキャスト専用チャネルを計算する。
【００７９】
第二の例示のマッピングアルゴリズム
以下の章では、スイッチ行列ユニットの次元をNで表す。
【００８０】
グローバルには、入力から出力までの6つの形式の接続が存在する。
1.  C15：スイッチ行列ユニット#1から入力し、全てスイッチ行列ユニット#5で出力する。
2.  C16：スイッチ行列ユニット#1から入力し、全てスイッチ行列ユニット#6で出力する。
3.  C25：スイッチ行列ユニット#2から入力し、全てスイッチ行列ユニット#5で出力する。
4.  C26：スイッチ行列ユニット#2から入力し、全てスイッチ行列ユニット#6で出力する。
5.  C156：スイッチ行列ユニット#1から入力し、スイッチ行列ユニット#5及び#6の両方に出力する。
6.  C256：スイッチ行列ユニット#2から入力し、スイッチ行列ユニット#5及び#6の両方に出力する。
大文字「C」はグループを表す一方で、小文字「c」は、そのグループ内の接続の数を表す。
【００８１】
どの接続も、6つのグループのうちの1つに分類することができる。同じ出力スイッチ行列ユニット(#5又は#6)で、接続が複数回存在するとき、マルチキャストは出力スイッチ行列ユニット(各スイッチ行列ユニットは正方行列)で実行されるので、それはまだシンプルな接続であると考えられることに注意しなさい。
【００８２】
接続の各形式は、6個のスイッチ行列ユニット間の内部接続を拡張することにより表現することができ、以下の式のセットを与える。
C15=(C13&C35)∪(C14&C45)
C16=(C14&C46)∪(C13&C36)
C25=(C24&C45)∪(C23&C35)
C26=(C23&C36)∪(C24&C46)
C156=(C13&C35&C36)∪(C14&C45&C46)∪[(C14&C46)+(C13&C35)]∪[(C13&C36)+(C14&C45)]
C256=(C23&C35&C36)∪(C24&C45&C46)∪[(C24&C46)+(C23&C35)]∪[(C23&C36)+(C24&C45)]
【００８３】
式のセット11
式のセット11の最初の4式については、接続を確立するための2つの選択がある。最後の2式については、4つの選択がある。しかし、最後の2つはより多くの接続を使用するので、収束を促進する可能性があるときはいつでも避けるべきである。
【００８４】
スイッチ行列ユニットに入る/出る接続をグローバルに見ると、以下の式のセットを確立することができる。
スイッチ行列ユニット#1  出力：  C15+C16+C156≦N
スイッチ行列ユニット#2  出力：  C25+C26+C256≦N
スイッチ行列ユニット#5  入力：  C15+C25+C156+C256≦N
スイッチ行列ユニット#6  入力：  C16+C26+C156+C256≦N
【００８５】
式のセット12
最初の2つの式については、C156の幾つかの接続が、C13及びC14の接続を同時に使用する。従って、それらは、c156の中で2つの接続として数えられる。これらは、避けられるべき接続であることを既に示された接続である。これらの接続を取り除くことにより、式のセット11は以下のように簡単化される、すなわち、
C15=(C13&C35)∪(C14&C45)
C16=(C14&C46)∪(C13&C36)
C25=(C24&C45)∪(C23&C35)
C26=(C23&C36)∪(C24&C46)
C156=(C13&C35&C36)∪(C14&C45&C46)
C256=(C23&C35&C36)∪(C24&C45&C46)
【００８６】
式のセット13
それゆえ、接続の各形式は、2つの所定のパスを持つ。例示のスイッチ行列サブシステムの物理的な接続より、どの内部グループにおける接続の最大数もN/2(すなわち、c13≦N/2, c14≦N/2,等)であることが明らかである。
【００８７】
アルゴリズム
式のセット13の対称性のため、接続の各形式(C15, C16, C25, C26, C156, C256)において、接続の半分が第一の選択に割り当てられ、もう半分が第二の選択に割り当てられる場合には、式のセット12で与えられる行列の物理的制約が守られるであろう。
【００８８】
このアルゴリズムの考え方は、接続を厳密に二分することにより、どのセグメントの使用も最小化するということである。これを行うために、アルゴリズムは、6つの工程、すなわち各グループに対して1工程を使う。
【００８９】
それゆえ、このアルゴリズムは、前のアルゴリズムに非常に似ており、以下の3つの変更点を持つ。
変更1：接続の6つのサブセットを認識する。CSPを、C156(スイッチ行列ユニット#1から、スイッチ行列ユニット#5及びスイッチ行列ユニット#6の両方への全ての接続)と、C256(スイッチ行列ユニット#2から、スイッチ行列ユニット#5及びスイッチ行列ユニット#6の両方への全ての接続)とに分ける。
変更2：接続の6つのサブセットが認識されるので、NEW_OUT[]アレイを通して6つの工程を実行して、接続を計算することが必要である。
変更3：ステップ6では、接続を割り当てるとき、より好ましいパスと代替のパスとの間で交互にパスを選択する。
【００９０】
正当性の証明
以下の証明では、各グループが偶数個の接続を持つと仮定する。すなわち、c15, c16, c25, c26, c156, c25,は全て偶数である。如何なる奇数値も、最後に処理する必要のある接続が残されている偶数値+1として扱われる。
【００９１】
1) 初期条件
初めは、システム内には全く接続が存在しない。結果として、容量値は以下のようになる、すなわち、
c13=0
c14=0
c23=0
c24=0
c35=0
c36=0
c45=0
c46=0
2) C156=(C13&C35&C36)∪(C14&C45&C46)
全ての内部接続がクリアされ、2つの選択は、互いに排他的なセグメントを使用するので、その2つの選択を交互に繰り返す。この繰り返しの最後には、
c13=c156/2
c14= c156/2
c23=0
c24=0
c35= c156/2
c36= c156/2
c45= c156/2
c46= c156/2
となる。
3) C256=(C23&C35&C36)∪(C24&C45&C46)
この時点で、c23=c24, c35= c45, c36= c46である。それゆえ、再び、その2つの解法を交互に繰り返すことになる。この繰り返しの最後には、
c13= c156/2
c14= c156/2
c23= c256/2
c24= c256/2
c35= c156+c256/2
c36= c156+c256/2
c45= c156+c256/2
c46= c156+c256/2
となる。
4) C15=(C13&C35)∪(C14&C45)
前式より、c13=c14, c35=c45である。再び、2つの選択を交互に繰り返す。この繰り返しの最後には、
c13= c156+c15/2
c14= c156+c15/2
c23= c256/2
c24= c256/2
c35= c156+c256+c15/2
c36= c156+c256/2
c45= c156+c256+c15/2
c46= c156+c256/2
となる。
5) C25=(C24&C45)∪(C23&C35)
ステップ4を見ると、c24=c23, c45=c35ということがわかる。従って、2つの選択の間で均等に分ける。この繰り返しの最後には、
c13= c156+c15/2
c14= c156+c15/2
c23= c256+c25/2
c24= c256+c25/2
c35= c156+c256+c15+c25/2
c36= c156+c256/2
c45= c156+c256+c15+c25/2
c46= c156+c256/2
となる。
6) C16=(C14&C46)∪(C13&C36)
再び、前式より、c14=c13, c46=c36である。この繰り返しの最後には、
c13= c156+c15+c16/2
c14= c156+c15+c16/2
c23= c256+c25/2
c24= c256+c25/2
c35= c156+c256+c15+c25/2
c36= c156+c256+c16/2
c45= c156+c256+c15+c25/2
c46= c156+c256+c16/2
となる。
7) C26=(C23&C36)∪(C24&C46)
前式より、c23=c24, c36=c46である。接続を均等に分けることになる。この繰り返しの最後には、
c13= c156+c15+c16/2
c14= c156+c15+c16/2
c23= c256+c25+c26/2
c24= c256+c25+c26/2
c35= c156+c256+c15+c25/2
c36= c156+c256+c16+c26/2
c45= c156+c256+c15+c25/2
c46= c156+c256+c16+c26/2
となる。
【００９２】
式の最新のシステムは、式のセット12を遵守するものであり、従って、アルゴリズムの収束を確実なものとする。前述の証明は、収束を確実にするために6つの工程が存在すべきことを示している。しかし、グループを処理する順番は重要ではない。
【００９３】
本特許請求の範囲で定められる本発明の技術的範囲から外れることなく、これらのシステム及び方法の他の変形が、当業者には明らかになるはずである。本出願で説明し、かつ添付図面に示す実施形態は、本発明の要素又はステップに対応する要素又はステップが、本特許請求の範囲で列挙されている構造、システム、又は方法の例である。ここで記述された説明及び図面は、同様に本発明の要素又はステップに対応する代替の要素又はステップが、本特許請求の範囲で列挙されている実施形態を、当業者が作成及び使用することを可能にすることができる。従って、意図された本発明の技術的範囲は、本特許請求の範囲の文字通りの語と異ならない他の構造、システム、又は方法を含み、更に、本特許請求の範囲の文字通りの語と実質的に差異のない他の構造、システム、又は方法を含む。
【図面の簡単な説明】
【００９４】
【図１】デジタル交差接続システムの一部となり得る、より好ましいスイッチ行列サブシステムのブロック図を示している。
【図２】例示の入力ベクトルIN[4N]の図である。
【図３】入力ベクトルIN[4N]内に収容され得る情報の形式を示した図である。
【図４】例示の出力ベクトルOUT[][]の図である。
【図５】例示の実施形態において、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5を出る信号について考えられる経路を示す図である。
【図６】例示の実施形態において、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#6を出る信号について考えられる経路を示す図である。
【図７】例示の実施形態において、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5を出る信号について考えられる経路を示す図である。
【図８】例示の実施形態において、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#6を出る信号について考えられる経路を示す図である。
【図９】例示の実施形態において、スイッチ行列ユニット#1に入り、スイッチ行列ユニット#5及び#6を出る信号について考えられる全ての経路の例を示す図である。
【図１０】例示の実施形態において、スイッチ行列ユニット#2に入り、スイッチ行列ユニット#5及び#6を出る信号について考えられる全て経路の例を示す図である。
【図１１】例示のスイッチ行列システムにおけるブロードキャスト接続のためのより好ましい経路、及び、代替の経路の例を示す図である。
【図１２】例示のスイッチ行列システムにおける通常接続のためのより好ましい経路、及び、代替の経路の例を示す図である。
【図１３】実施形態の1つで考えられるシナリオの例を示す図である。
【図１４】ルートを計算するとき使用することのできる、サイズ4Nの例示の配列NEW_OUT[]を示す図である。
【図１】
2005532729.tif 000003
【図２】
2005532729.tif 000004
【図３】
2005532729.tif 000005
【図４】
2005532729.tif 000006
【図５】
2005532729.tif 000007
【図６】
2005532729.tif 000008
【図７】
2005532729.tif 000009
【図８】
2005532729.tif 000010
【図９】
2005532729.tif 000011
【図１０】
2005532729.tif 000012
【図１１】
2005532729.tif 000013
【図１２】
2005532729.tif 000014
【図１３】
2005532729.tif 000015
【図１４】
2005532729.tif 000016
【国際調査報告】
2005532729.tif 000017
2005532729.tif 000018