(57)【特許請求の範囲】
【請求項１】
複数の入力ポートと、複数の出力ポートと、結合マトリックスと、この結合マトリックスを制御するアービタユニットと、を備える少なくとも１つの切換ユニットを有するパケット切換装置において、
前記アービタユニットは、そのラインがそれぞれ入力ポートに対応すると共にそのカラムがそれぞれ出力ポートに対応する状態マトリックスを生成するために設けられており、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続のための重みをそれぞれが表す複数の要素を備え、さらに、
前記アービタユニットは、前記状態マトリックスのカラムの幾つかのグループについて並列に動作するアルゴリズムに基づいて、幾つかの受け入れられた相互関係を備える第１の決定マトリックスを形成するために設けられると共に、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の最新の重みと、前記ポート制御により既に生成された重みとの間の差をそれぞれが表している複数の要素を備えることを特徴とするパケット切換装置。
【請求項２】
複数の入力ポートと、複数の出力ポートと、結合マトリックスと、この結合マトリックスを制御するアービタユニットと、を備える少なくとも１つの切換ユニットを有するパケット切換装置において、
前記アービタユニットは、そのラインがそれぞれ入力ポートに対応すると共にそのカラムがそれぞれ出力ポートに対応する状態マトリックスを生成するために設けられており、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続のための重みをそれぞれが表す複数の要素を備え、さらに、
前記アービタユニットは、前記状態マトリックスのカラムの幾つかのグループについて並列に動作するアルゴリズムに基づいて、幾つかの受け入れられた相互関係を備える第１の決定マトリックスを形成するために設けられると共に、
前記アービタユニットは、
もしも幾つかの相互接続が前記第１の決定マトリックス内の１つの入力ポートのために受け入れられたとしたならば、最も高い重みを伴う前記相互接続を選択し、
前記選択された相互接続を含む決定マトリックスを形成する、
ために設けられることを特徴とするパケット切換装置。
【請求項３】
前記アービタユニットは、反復プロセスにおける前記入力ポートを前記出力ポートに接続するために設けられることを特徴とする請求項２に記載のパケット切換装置。
【請求項４】
前記アービタユニットは、グループについてのアルゴリズムを実行するために設けられ、前記グループのそれぞれのカラムでは、最も高い重みを伴う相互接続が受け入れられると共に、相互接続された入力ポートが全てのグループの次のカラム内で考慮されないことを特徴とする請求項２に記載のパケット切換装置。
【請求項５】
複数の入力ポートと、複数の出力ポートと、結合ユニットと、前記結合ユニットを制御するアービタユニットと、を備える少なくとも１つの切換ユニットを備えるパケット切換装置のためのパケット切換方法において、
状態マトリックスが前記アービタユニット内に生成され、前記マトリックスのラインのそれぞれは入力ポートに対応し、前記マトリックスのカラムのそれぞれは出力ポートに対応し、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の重みをそれぞれの要素が表す複数の要素を備え、
幾つかの受け入れられた相互接続より構成される、第１の決定マトリックスが前記状態マトリックスのカラムの幾つかのグループに並列に供給されるアルゴリズムに基づいて形成されていると共に、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の最新の重みと、前記ポート制御により既に生成された重みとの間の差をそれぞれが表している複数の要素を備えることを特徴とするパケット切換方法。
【請求項６】
幾つかの入力および出力ポートを備えるパケット切換装置用の切換ユニットであって、結合マトリックスと、この結合マトリックスを制御するためのアービタユニットとを備える切換ユニットにおいて、
前記アービタユニットは、それぞれが入力ポートに対応している複数のラインと、それぞれが出力ポートに対応している複数のカラムと、を備える状態マトリックスを生成するために設けられ、
前記状態マトリックスは、それぞれの要素が前記パケット切換装置の入力ポートと出力ポートとの間相互接続のための重みを表す複数の要素を備え、
前記アービタユニットは、前記状態マトリックスのカラムの幾つかのグループについて並列に動作可能であるアルゴリズムに基づいて、幾つかの受け入れられた相互関係を含んでいる第１の決定マトリックスを形成するために設けられると共に、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の最新の重みと、前記ポート制御により既に生成された重みとの間の差をそれぞれが表している複数の要素を備えることを特徴とする切換ユニット。
【請求項７】
幾つかの入力ポートと出力ポートとを備えるパケット切換装置の切換ユニット内の結合マトリックスを制御するためのアービタユニットにおいて、
前記アービタユニットは、それぞれが入力ポートに対応している複数のラインと、それぞれが出力ポートに対応している複数のカラムと、を備える状態マトリックスを生成するために設けられ、
前記状態マトリックスは、それぞれの要素が前記パケット切換装置の入力ポートと出力ポートとの間相互接続のための重みを表す複数の要素を備え、
前記アービタユニットは、前記状態マトリックスのカラムの幾つかのグループについて並列に動作可能であるアルゴリズムに基づいて、幾つかの受け入れられた相互関係を含んでいる第１の決定マトリックスを形成するために設けられると共に、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の最新の重みと、前記ポート制御により既に生成された重みとの間の差をそれぞれが表している複数の要素を備えることを特徴とするアービタユニット。
【請求項８】
幾つかの入力ポートおよび出力ポートと、結合ユニットとこの結合ユニットを制御するアービタユニットとを備える少なくとも１つの切換ユニットと、を備えるパケット切換装置のためのパケット切換方法において、
状態マトリックスが前記アービタユニット内に生成され、前記マトリックスのラインのそれぞれは入力ポートに対応し、前記マトリックスのカラムのそれぞれは出力ポートに対応し、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の重みをそれぞれの要素が表す複数の要素を備え、
幾つかの受け入れられた相互接続より構成される、第１の決定マトリックスが前記状態マトリックスのカラムの幾つかのグループに並列に供給されるアルゴリズムに基づいて形成されていると共に、
前記アービタユニットは、
もしも幾つかの相互接続が前記第１の決定マトリックス内の１つの入力ポートのために受け入れられたとしたならば、最も高い重みを伴う前記相互接続を選択し、
前記選択された相互接続を含む決定マトリックスを形成する、
ために設けられることを特徴とするパケット切換方法。
【請求項９】
幾つかの入力および出力ポートを備えるパケット切換装置用の切換ユニットであって、結合マトリックスと、この結合マトリックスを制御するためのアービタユニットとを備える切換ユニットにおいて、
前記アービタユニットは、それぞれが入力ポートに対応している複数のラインと、それぞれが出力ポートに対応している複数のカラムと、を備える状態マトリックスを生成するために設けられ、
前記状態マトリックスは、それぞれの要素が前記パケット切換装置の入力ポートと出力ポートとの間相互接続のための重みを表す複数の要素を備え、
前記アービタユニットは、前記状態マトリックスのカラムの幾つかのグループについて並列に動作可能であるアルゴリズムに基づいて、幾つかの受け入れられた相互関係を含んでいる第１の決定マトリックスを形成するために設けられると共に、
前記アービタユニットは、
もしも幾つかの相互接続が前記第１の決定マトリックス内の１つの入力ポートのために受け入れられたとしたならば、最も高い重みを伴う前記相互接続を選択し、
前記選択された相互接続を含む決定マトリックスを形成する、
ために設けられることを特徴とする切換ユニット。
【請求項１０】
幾つかの入力ポートと出力ポートとを備えるパケット切換装置の切換ユニット内の結合マトリックスを制御するためのアービタユニットにおいて、
前記アービタユニットは、それぞれが入力ポートに対応している複数のラインと、それぞれが出力ポートに対応している複数のカラムと、を備える状態マトリックスを生成するために設けられ、
前記状態マトリックスは、それぞれの要素が前記パケット切換装置の入力ポートと出力ポートとの間相互接続のための重みを表す複数の要素を備え、
前記アービタユニットは、前記状態マトリックスのカラムの幾つかのグループについて並列に動作可能であるアルゴリズムに基づいて、幾つかの受け入れられた相互関係を含んでいる第１の決定マトリックスを形成するために設けられると共に、
前記アービタユニットは、
もしも幾つかの相互接続が前記第１の決定マトリックス内の１つの入力ポートのために受け入れられたとしたならば、最も高い重みを伴う前記相互接続を選択し、
前記選択された相互接続を含む決定マトリックスを形成する、
ために設けられることを特徴とするアービタユニット。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数のラインユニットと複数の切換ユニットとを備えるパケット切換装置に関する。さらに、このパケット切換装置用の切換ユニット、アービタユニットおよびパケット切換方法に関する。
【０００２】
【従来の技術】
Ｒ．ショーネン（R. Schoenen）、Ｇ．ポスト（G. Post）およびＧ．サンダー（G. Sander）により、'９９ 年ブロードバンド・スイッチング・シンポジウムでの公知文献「１００％のスループットを有する入力待ち行列化されたスイッチ用の優先権を備える重み付けされたアービットレーション（仲裁）アルゴリズム」は、パケット切換装置の種々の重み付けされた切換アルゴリズムを比較している。この切換アルゴリズムは、パケット切換装置の同一の出力ポートを対象とした幾つかのパケットの衝突を防止すると共に、結果的にデータの損失および遅延を低減させるよう試みている。しかしながら、切換動作中の出力ポートの状態を考慮に入れる方法は、この公知文献の中では説明されていない。
【０００３】
この公知文献は、入力ポートと出力ポートとを相互に接続するための相対的な重みに基づいて、仲裁アルゴリズムに関するものである。従って、マトリックスは、それぞれが切換装置の所定の出力ポートに対するデータパケットの所定の入力ポートの切り換えのための重み割り当てを示す要素より構成されている。マトリックスの複数のカラム（行）と複数のライン（列）は、データパケット用の切換装置の入力ポートと出力ポートとに対応している。可能な限り高い重付けは、マトリックスの各カラム毎に選択され、入力ポートと出力ポートとの間で受け入れられた相互接続として印を付けられる。連続する計算において、選択された入力ポートすなわち入力ポートに対応するマトリックスのラインは、これ以上は用いられなくなる。
【０００４】
【発明が解決しようとする課題】
この発明の目的は、パケット切換装置内のデータパケットの迅速に計算された切り換えを可能にさせることにある。
【０００５】
【課題を解決するための手段】
この目的は、複数の入力ポートおよび複数の出力ポートを備えるパケット切換装置と、結合マトリックスおよびこの結合マトリックスを制御するアービタユニットとを備える少なくとも１つの切換ユニットとを用いて達成され、
前記アービタユニットは、各ライン（列）が入力ポートに対応すると共に、各カラム（行）が各出力ポートに対応するような状態（ステート）マトリックスを生成するように構成され、
前記状態マトリックスは、それぞれが前記パケット切換装置の入力ポートと出力ポートとの間の相互接続用の重みを示す複数の素子を備え、
前記アービタユニットは、前記状態マトリックスの行方向の幾つかのグループに並列に動作可能であるアルゴリズムに基づいて、幾つかの受け入れられる相互関係を構成する第１の決定マトリックスを形成するように設計され、
前記状態マトリックスは、前記パケット切換装置の入力ポートと出力ポートとの間の相互接続の最新の重みと、前記ポート制御により既に生成された重みとの間の差をそれぞれが表している複数の要素を備えることを特徴としている。
【０００６】
パケット切換装置は、幾つかのラインユニットまたはラインカードおよび幾つかの切換ユニットまたは切換カードより構成されている。ラインユニットの重要な構成要素は、ポート制御である。各ポート制御は、並列に動作する幾つかの切換ユニットに接続されると共に、切り換えられるべきパケットを配列し、パケット切換装置に到達し、それらの優先性とパケット切換装置における所望の出力ポートとに従って待機ライン（列）または待ち行列のタスクを有している。
【０００７】
パケット切換装置における各スイッチングユニットは、カップリングまたは交差点マトリックスおよびアービタユニットまたはアービタより構成されている。カップリングマトリックスの構成は、規則的な時間の間隔でのアルゴリズムを用いてアービタユニットにより新たに決定されているので、新たな相互接続がパケットを切り換えるためのパケット切換装置の入力ポートと出力ポートとの間で確立されている。
【０００８】
パケット切換装置の状態マトリックスは、入力ポートと出力ポートとの間の各相互接続の重みを示す幾つかの素子を備えている。重みはポート制御により生成されているので、このポート制御は、入力ポートに存在するパケットが転送されるべきか否かおよびどのように転送されるかをアービタに対して通知することができる。重みは、パケットの優先性およびクラス、または待機ライン（列）または待ち行列の待ち時間または長さなどについての表示部を含んでいても良い。
【０００９】
状態マトリックスのラインは、パケット切換装置の入力ポートに対応し、各カラムは出力ポートに対応している。アービタユニットは、各時間毎のカラムのグループについて同時にアルゴリズムを実行する。カラムのグループは、複数のカラムを含んでいても良いが、それらは必ずしも状態マトリックス内で互いに次々と配置されている必要はない。しかしながら、２つまたはそれ以上の隣接しているカラムがまた１つのグループを形成していても良い。アルゴリズムが実行されてしまった後に、アービタユニットは、第１の暫定的な決定マトリックス内で受け入れられた各相互接続をマーク（mark）するようにしている。
【００１０】
このアルゴリズムは、多数のポートに関する連続的な増分マッチング（ＳＩＭＰ―Successive Incremental Matching over Multiple Ports ―）であっても良く、これは、Ｒ．ショーネン（R. Schoenen）、Ｇ．ポスト（G. Post）およびＧ．サンダー（G. Sander）により、'９９ 年ブロードバンド・スイッチング・シンポジウムでの公知文献「１００％のスループットを有する入力待ち行列化されたスイッチ用の優先権を備える重み付けされたアービットレーション（仲裁）アルゴリズム」に説明されている。状態マトリックスに適用されるアルゴリズムの同時の実行は、１つの入力ポートがデータパケット用の２つの出力ポートに同時に結合されている相互接続を引き起こすかもしれない。
【００１１】
相互接続の演算においては、２つの条件が満たされるべきである。１つの入力ポートは同時に幾つかの出力ポートと結合することはできず、および／または、１つの出力ポートは同時に幾つかの入力ポートを結合することはできない。並列で処理されているアルゴリズムの結果は、第１の決定マトリックス内に保持されている。しかしながら、カラムグループにおける並列処理は、１つの入力ポートに割り当てられている幾つかの出力ポートへと通じていても良い。このような理由により、最も高い重みを伴う相互接続は、第１の決定マトリックスの各ライン毎に選択されて、第２の決定マトリックス内に記録される。
【００１２】
アービタユニットは、反復プロセスを用いて、結合マトリックスの構成のための最終の決定マトリックスを決定している。１つの反復プロセスは、並列で動作するアルゴリズムの実行と、選択された相互接続を備える決定マトリックスの形成と、より構成されている。ここで、アービタユニットは、相互接続がまだ決定されていないこれらのカラムからグループを形成すると共にそれらの入力ポートについて出力ポートに対して一般に認められていない相互接続が実施されるためのそれらのラインとカラムへのアルゴリズムを提供する。最も好ましい場合、反復ステップは全ての入力ポートおよび出力ポートの相互接続へと通じている。
【００１３】
データパケットの迅速で信頼性のあるスイッチングを導くことにより、入力ポートと出力ポートとの間の好ましい相互接続を実行することは、最終の決定マトリックスの反復決定により保護することができる。
【００１４】
最も高い重みを伴う相互接続は、状態マトリックスの１つのグループの各カラム毎に選択され、入力ポートと出力ポートの間の受け入れられた相互接続としてマークされる。カラムの各グループにおける選択された入力ポートすなわちこの入力ポートに対応するラインは、アルゴリズムの更なる実行においては考慮されず、結果的にはマークされる。
【００１５】
ポート制御は、結合マトリックスの構成を決定するための重みを生成して、それらを規則的な時間間隔でアービタユニットへと送っている。状態マトリックスの好適な実施形態は、ポート制御により生成された最新の重みと、１つの時間間隔よりも早く生成された重みとの間の差異をそれぞれが意味している複数の要素を備えている。
【００１６】
この発明はまた、複数の入力ポートと出力ポートとを備えるパケット切換装置のための切換ユニットに関するものである。この切換ユニットは、結合マトリックスと、この結合マトリックスを制御するためのアービタユニットを備えると共に、複数の要素を備える状態マトリックスが前記アービタユニット内に設けられており、複数の要素のそれぞれはパケット切換装置の入力ポートと出力ポートととの間の相互接続の重みを表しており、そのラインのそれぞれは入力ポートに対応すると共にそのカラムのそれぞれは出力ポートに対応している。アービタユニットは、状態マトリックスのカラムの幾つかのグループと並列に動作するアルゴリズムを用いて、第１の決定マトリックスを形成している。この第１の決定マトリックスは、パケット切換装置の入力ポートと出力ポートとの間の幾つかの受け入れられた相互接続より構成されている。
【００１７】
この発明はさらに、幾つかの入力ポートと出力ポートとを備えるパケット切換装置用の切換ユニットの結合マトリックスを制御するためのアービタユニットに関するものである。ここで、複数の要素を備える状態マトリックスは、その要素のそれぞれがパケット切換装置の入力ポートと出力ポートとの間の相互接続を表しているアービタユニット内に設けられており、そのラインはそれぞれ入力ポートに対応すると共にそのカラムはそれぞれ出力ポートに対応している。このアービタユニットは、状態マトリックスの幾つかのカラムグループと並列に動作するアルゴリズムを用いて第１の決定マトリックスを形成している。この第１の決定マトリックスは、パケット切換装置の入力ポートと出力ポートとの間の幾つかの受け入れられた相互接続により構成されている。
【００１８】
この発明はさらに、幾つかの入力ポートと出力ポートと少なくとも１つの切換ユニットまたは切換カードとを備えるパケット切換装置のための切換方法に関するものである。この切換ユニットは、結合マトリックスと、この結合マトリックスを制御するためのアービタユニットと、を備えている。ここで、状態マトリックスは、それぞれがパケット切換装置の入力ポートと出力ポートとの間の相互接続の重みを表す複数の要素を備えるアービタユニット内に設けられており、そのラインのそれぞれは、入力ポートに対応し、カラムのそれぞれは出力ポートに対応している。アービタユニットは、状態マトリックスのカラムの幾つかのグループと並列に動作するアルゴリズムを用いて、第１の決定マトリックスを形成しており、この決定マトリックスは幾つかの受け入れられた相互接続より構成されている。
【００１９】
【発明の実施の形態】
以下、添付図面を用いてこの発明の実施形態を詳細に説明する。
図１に示されたパケット切換装置は、２つのラインユニット１および２と、複数の切換ユニット３ないし５と、より構成されている。複数のラインユニット１および２は、しばしば２個よりも遙かに大きな例えば６４個であろうが、図面の明瞭さを維持するためにこの実施形態においては２個に限定して説明する。ラインユニット１および２はそれぞれ、個別の構成要素により構成されており、これらは実施形態の説明には不適切であり、したがって図示されていないが、光送信ユニット、フレーム生成器、ネットワークプロセッサ等や、実施形態の具体例にとっては本質的なものであるポート制御６および７である。例えばスイッチカード等の切換ユニット３ないし５のそれぞれは、結合マトリックス８と、アービタユニット９とより構成されている。それぞれの並列動作切換ユニット３ないし５におけるアービタユニット９および結合マトリックス８の両者は、ポート制御６および７のそれぞれに接続されている。
【００２０】
一定の長さのデータパケットはセルとして知られている。この一定の長さのセルは、パケットのサイズを変化させることよりも切り換える方法の方がより容易に取り扱えるので、入来するパケットは、ラインユニット１および２の中で一定の長さの複数のセルに再分割され、待ち行列の形式で中間記憶装置の中で保持される。成功した切り換え動作、すなわち、それぞれのたび毎に１つの入力ポートから１つの出力ポートへと受け入れられた割り当ての後に、複数のセルは待ち行列から取り出される。
【００２１】
重付けに基づいて、ポート制御は、入力ポート内の複数のセルが順送りにされるべきであるか否か、および如何に緊急に送られるべきであるかを、アービタユニットに対して通知することができる。重付けは、パケットの優先性およびクラス、または入力ポート内の待ち行列の待機時間または長さについての表示部を有していても良い。
【００２２】
ポート制御６および７は、重付けに混じって、アービタユニット９に対して結合マトリックス８の構成を決定するために必要な情報を送っている。
【００２３】
アービタユニットが結合マトリックス８の構成を決定してしまってポート制御吐血号マトリックスの両方へとこの構成を送ってしまった後に、それぞれの切換ユニットの結合マトリックス８は、その結果として構成される。ポート制御６および７は、いわゆるセル周期としての規則的な時間間隔で切り換えるために、結合マトリックス８へとセルを送ることになる。
【００２４】
図２は、アービタユニット９内で実行されると共に、結合マトリックス８の構成のためにカラムのグループに適用されるアルゴリズムを示している。このアルゴリズムは、Ｒ．ショーネン（R. Schoenen）、Ｇ．ポスト（G. Post）およびＧ．サンダー（G. Sander）により、'９９ 年ブロードバンド・スイッチング・シンポジウムでの公知文献「１００％のスループットを有する入力待ち行列化されたスイッチ用の優先権を備える重み付けされたアービットレーション（仲裁）アルゴリズム」の文献の中で提案されているものの１つである。図２は、状態マトリックス１１と，カラムのグループ１２と，決定マトリックス１３とより構成されている。
【００２５】
状態マトリックス１１は、４つの入力ポートＩ０ないしＩ３と４つの出力ポートＯ０ないしＯ３とを備えるパケット切換装置に対応している。この状態マトリックス１１は、１６個の要素を備えており、これらは入力ポートＩ０ないしＩ３および出力ポートＯ０ないしＯ３の間の全ての相互接続における個別の重みを表している。
【００２６】
図２の実施形態において、多数のカラムおよびラインすなわち入力ポートおよび出力ポートは、４つに制限されているので、説明を簡単にすることができる。多数のグループは、状態マトリックス１１の全てのカラムを備える１つのグループへと低減されている。
【００２７】
適用されるアルゴリズムは、以下の４つのステップ：
−カラムの最も高い重みが状態マトリックス１１の第１のカラムで決定され；
−次のカラムで、既に選択されたラインまたは入力ポートが計数されるという但し書きを付けて、カラムの中で最も高い重みが再び決定され；
−次のカラムにおける最も高い重みの決定において、既に選択されたラインまたは入力ポートの重み付けが考慮されないで；
−それぞれのカラムにおける最も高い重みの決定がこのように継続されて、状態マトリックスの最終のカラムを含むことになる；
を備えている。
【００２８】
アービタユニットは、このアルゴリズムをカラムのグループ１２に適用して、第１のカラムまたは出力ポートＯ０における最も高い重みである入力ポートＩ２の重みを決定している。選択された重みは、入力ポートＩ２および出力ポートＯ０の間の受け入れられた相互接続としてマークされる。次のカラムにおける最も高い重みを決定する際に、入力ポートＩ２の重みは考慮されず、入力Ｉ３および出力Ｏ１の間の相互接続がマークされる。
【００２９】
出力ポートＯ２のため、入力ポートＩ０およびＩ１の重みは、最も大きな重みを選択するときに考慮され、入力ポートＩ０が受け入れられた相互接続として決定される。この結果は、入力ポートＩ３のみが出力ポートＯ３との間の受け入れられた接続として選択可能となる。
【００３０】
受け入れられた相互接続は、決定マトリックス１３内にマークされる。
図３は、並列に適用されると共に図２を参照しながら説明したように反復的に切り換えるアルゴリズムを明瞭化するための役目を果たしている。状態マトリックス１１，決定マトリックス１３，カラムのグループ１２は、第２のグループ１４および暫定的な決定マトリックス１５により補われている。
【００３１】
状態マトリックス１１のカラムは、２つのカラムのそれぞれのグループ１２と１４とに再分割されていた。図２のアルゴリズムは、それぞれのグループ１２および１４について並列なアービタユニット９により実行される。
【００３２】
２つのカラムの結果は、暫定的な決定マトリックス１５内に保持されている。第１のグループ１２のカラムは、入力ポートＩ２およびＩ３に接続され、第２のグループ１４のカラムは、入力ポートＩ０およびＩ２に接続されている。２つのグループの並列処理のおかげにより、入力ポートＩ２は、出力ポートＯ０および出力ポートＯ３の両方に対して割り当てられた。
【００３３】
したがって、最も高い重みは、暫定的な決定マトリックス１５の各ラインにおける一般的に認定される相互接続のために決定される。暫定的な決定マトリックス１５の第１のラインのマークされた相互接続は、決定マトリックス１３における受け入れられた相互接続として取り入れられる。相互接続は、暫定的な決定マトリックス１５内の入力ポートＩ１のためには取り入れられることはなく、それは、出力ポートと入力ポートＩ１との間の相互接続がまた決定マトリックス１３内になぜ存在しないかということである。２つの相互接続は入力ポートＩ２のために選択されていたので、これはこの相互接続が一般的に認められる重みに基づいて決定されている。
【００３４】
より高い重みを伴う相互接続は、決定マトリックス１３内に受け入れられるので、入力ポートＩ２は、出力ポートＯ３との間で受け入れられた相互接続としてマークされる。入力ポートＩ３のためには、暫定的な決定マトリックス１５からのマークされた相互接続が、受け入れられた相互接続として採用される。
【００３５】
決定マトリックス１３の相互接続は、反復を通して改善されており、この反復においては、アービタユニット９が、出力ポートとの間で接続が達成されていなかった入力ポートのために、状態マトリックス１１のそれらのラインに対して並列動作アルゴリズムを供給している。ここでは、未だに相互接続されていなかったこれらの出力ポートのみが、考慮される。
【００３６】
出力ポートに対する接続が入力ポートＩ１のためには決定されていなかったので、このアルゴリズムは状態マトリックス１１へと反復的に供給される。出力ポートＯ１ないしＯ２と同様に既に相互接続されている入力ポートＩ０，Ｉ２およびＩ３は、最早これ以上は考慮されない。
【００３７】
図４において、グループ１２および１４の並列処理は、グループ１２および１４の相互接続により改善されている。
【００３８】
状態マトリックス１１の複数のカラムは、それぞれ２つのカラムグループ１２および１４に再分割されていた。図２を参照して説明したアルゴリズムは、アービタユニット９により、それぞれのグループ１２および１４へと供給される。このアルゴリズムは、グループ１２および１４の相互接続により補われている。
【００３９】
それぞれのグループに供給されたアルゴリズムは、全てのグループのために、アービタユニットにより並列に実行され、以下の４つ：
−カラムの最も高い重みがそれぞれのグループの第１のカラムで決定され；
−次のカラムにおいて、再び、最も高い重みは、既に選択されたラインまたは入力ポートの重みは全てのグループで考慮されないという但し書きを伴って、決定され；
−既に選択されたラインまたは入力ポートの重みは、次のカラムにおける最も大きな重みの決定の際に考慮されず；
−それぞれのカラムにおける最も大きな重みの決定は、このようにして継続されて、状態マトリックスの最終のカラムを含んでいる、
ステップより構成されている。
【００４０】
２つのカラムの結果は、暫定的な決定マトリックス１５内に保持されている。第１のグループ１２の複数のカラムは、入力ポートＩ２およびＩ３に接続され、第２のグループ１４の複数のカラムは、入力ポートＩ０およびＩ１にそれぞれ接続されている。複数のグループの相互接続のおかげで、入力ポートＩ２は出力ポートＯ０および出力ポートＯ３に同時に割り当てられることはない。
【００４１】
さらに、最も高い重みは、暫定的な決定マトリックス１５のそれぞれのラインにおける受け入れられた相互接続であるものとして決定される。暫定的な決定マトリックス１５における第１のラインのマークされた相互接続は、決定マトリックス１３内に受け入れられた相互接続であるものとして取り入れられる。出力ポートＯ３は、入力ポートＩ１のために暫定的な決定マトリックス１５内でマークされているので、これにより、決定マトリックス１３はまた、出力ポートＯ３および入力ポートＩ１の間で相互接続を保持することができる。出力ポートＯ０との相互接続は、入力ポートＩ２のためにマークされる。最も高い重みを伴う相互接続は、もしも幾つかの相互接続が１つの入力ポートのために暫定的な決定マトリックス１５内にマークされたならば、決定マトリックス１３内に受け入れられる。
【００４２】
もしも入力ポートＩ０ないしＩ３の全てが決定マトリックス１３内で相互接続されていないならば、この決定マトリックス１３は、アービタユニット９が状態マトリックス１１のこれらのラインに対して、出力ポートへの相互接続が達成されていない入力ポートのために、並列動作アルゴリズムを供給する繰り返しステップを通して改善することができる。未だに相互接続されていないこれらの出力ポートのみが、ここでは考慮される。
【００４３】
【発明の効果】
以上詳細に説明したように、本発明によれば、パケット切換装置内のデータパケットの切り換えを、迅速に計算された手段により行なうことができる。
【図面の簡単な説明】
【図１】この発明の実施形態によるパケット切換装置を示すブロック図である。
【図２】この発明の実施形態におけるカラムグループに適用されるアルゴリズムを示す説明図である。
【図３】この発明の実施形態における切換を目的とする幾つかのカラムグループと並列に適用されるアルゴリズムを示す説明図である。
【図４】この発明の実施形態におけるカラムグループの相互接続を示す説明図である。
【符号の説明】
３〜５  切換ユニット
８  結合マトリックス
９  アービタ（調停・仲裁）ユニット
１１  状態マトリックス
１２  グループ
１４  グループ
【図１】
0004065159.tif 000002
【図２】
0004065159.tif 000003
【図３】
0004065159.tif 000004
【図４】
0004065159.tif 000005