(57)【特許請求の範囲】
【請求項１】
パケットを入力する入力部と、
前記入力部からのパケットをスイッチするスイッチと、
前記スイッチを制御するスケジューラを具備し、
前記スケジューラは、
前記入力部からのパケット転送要求の優先順位を変更するシャッフラと、
前記シャッフラによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、且つ前記シャッフラによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成するスケジューリングアルゴリズム部と、
前記スケジューリングアルゴリズム部で生成されたパケット転送許可の優先順位を前記シャッフラによって変更される前のパケット転送要求の優先順位と同じになるように変更して前記入力部に返送するリシャッフラとを備え、
前記入力部は、Ｎ個（Ｎは１以上の整数）の入力ポートを含み、
前記シャッフラは、
前記Ｎ個の入力ポートからのパケット転送要求が初期設定される複数段の巡回回路を含み、
最後段以外の巡回回路は、後段の巡回回路からの桁上げ信号に同期して前記初期設定されたパケット転送要求及び前段の巡回回路からセットされたパケット転送要求を巡回させて前記後段の巡回回路にセットし、
最後段の巡回回路は、所定間隔で発生されるスロットパルスに同期して前記初期設定されたパケット転送要求及び前段の巡回回路からセットされたパケット転送要求を巡回させることにより、前記Ｎ個の入力ポートからのＮ個のパケット転送要求の優先順位を、Ｎ！種類の優先順位パターンが順次形成されるように変更するパケットスイッチ。
【請求項２】
パケットを入力する入力部と、
前記入力部からのパケットをスイッチするスイッチと、
前記スイッチを制御するスケジューラを具備し、
前記スケジューラは、
前記入力部からのパケット転送要求の優先順位を変更するシャッフラと、
前記シャッフラによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、且つ前記シャッフラによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成するスケジューリングアルゴリズム部と、
前記スケジューリングアルゴリズム部で生成されたパケット転送許可の優先順位を前記シャッフラによって変更される前のパケット転送要求の優先順位と同じになるように変更して前記入力部に返送するリシャッフラとを備え、
前記入力部は、Ｎ個（Ｎは１以上の整数）の入力ポートを含み、
前記シャッフラは、
前記Ｎ個の入力ポートからのパケット転送要求が初期設定される複数段の巡回回路を含み、
最後段以外の巡回回路は、所定間隔で発生されるスロットパルスに同期して前記初期設定されたパケット転送要求及び前段の巡回回路からセットされたパケット転送要求を巡回させて前記後段の巡回回路にセットし、
最後段の巡回回路は、前記スロットパルスに同期して前記初期設定されたパケット転送要求及び前段の巡回回路からセットされたパケット転送要求を巡回させることにより、前記Ｎ個の入力ポートからのＮ個のパケット転送要求の優先順位を、Ｎ，Ｎ−１，…，２の最小公倍数に等しいＭ種類の優先順位パターンが順次形成されるように変更するパケットスイッチ。
【請求項３】
パケットを入力する入力部と、
前記入力部からのパケットをスイッチするスイッチと、
前記スイッチを制御するスケジューラを具備し、
前記スケジューラは、
前記入力部からのパケット転送要求の優先順位を変更するシャッフラと、
前記シャッフラによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、且つ前記シャッフラによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成するスケジューリングアルゴリズム部と、
前記スケジューリングアルゴリズム部で生成されたパケット転送許可の優先順位を前記シャッフラによって変更される前のパケット転送要求の優先順位と同じになるように変更して前記入力部に返送するリシャッフラとを備え、
前記入力部は、Ｎ個（Ｎは１以上の整数）の入力ポートを含み、
前記シャッフラは、
前記Ｎ個の入力ポートからのパケット転送要求が初期設定される複数段の巡回回路を含み、
最後段以外の巡回回路は所定のタイミングで閉鎖されるゲート回路を備え、該ゲート回路を経由して供給される所定間隔で発生されるスロットパルスに同期して前記初期設定されたパケット転送要求及び前段の巡回回路からセットされたパケット転送要求を巡回させて前記後段の巡回回路にセットし、
最後段の巡回回路は、前記スロットパルスに同期して前記初期設定されたパケット転送要求及び前段の巡回回路からセットされたパケット転送要求を巡回させることにより、前記Ｎ個の入力ポートからのＮ個のパケット転送要求の優先順位を、Ｎ，Ｎ−１，…，２の最小公倍数に等しいＭ種類の優先順位パターンが順次形成され、次いで、前記Ｍ種類の優先順位パターンと異なる他のＭ種類の優先順位パターンが順次形成されるように変更するパケットスイッチ。
【請求項４】
パケットを入力する入力部と、
前記入力部からのパケットをスイッチするスイッチと、
前記スイッチを制御するスケジューラを具備し、
前記スケジューラは、
前記入力部からのパケット転送要求の優先順位を変更するシャッフラと、
前記シャッフラによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、且つ前記シャッフラによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成するスケジューリングアルゴリズム部と、
前記スケジューリングアルゴリズム部で生成されたパケット転送許可の優先順位を前記シャッフラによって変更される前のパケット転送要求の優先順位と同じになるように変更して前記入力部に返送するリシャッフラとを備え、
前記入力部は、Ｎ個（Ｎは１以上の整数）の入力ポートを含み、
前記シャッフラは、Ｎ個の優先順位を表す優先順位データが初期設定される複数段の巡回回路と、
最後段の巡回回路からの出力に応答して、前記Ｎ個の入力ポートからのパケット転送要求の何れかを選択して出力するＮ個のセレクタ、とを含み、
最後段以外の巡回回路は、後段の巡回回路からの桁上げ信号に同期して前記初期設定された優先順位データ及び前段の巡回回路からセットされた優先順位データを巡回させて前記後段の巡回回路にセットし、
最後段の巡回回路は、所定間隔で発生されるスロットパルスに同期して前記初期設定された優先順位データ及び前段の巡回回路からセットされた優先順位データを巡回させて前記Ｎ個のセレクタに供給し、以て前記Ｎ個のセレクタからＮ！種類の優先順位パターンを順次出力させるパケットスイッチ。
【請求項５】
パケットを入力する入力部と、
前記入力部からのパケットをスイッチするスイッチと、
前記スイッチを制御するスケジューラを具備し、
前記スケジューラは、
前記入力部からのパケット転送要求の優先順位を変更するシャッフラと、
前記シャッフラによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、且つ前記シャッフラによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成するスケジューリングアルゴリズム部と、
前記スケジューリングアルゴリズム部で生成されたパケット転送許可の優先順位を前記シャッフラによって変更される前のパケット転送要求の優先順位と同じになるように変更して前記入力部に返送するリシャッフラとを備え、
前記入力部は、Ｎ個（Ｎは１以上の整数）の入力ポートを含み、
前記シャッフラは、Ｎ個の優先順位を表す優先順位データが初期設定される複数段の巡回回路と、
最後段の巡回回路からの出力に応答して、前記Ｎ個の入力ポートからのパケット転送要求の何れかを選択して出力するＮ個のセレクタ、とを含み、
最後段以外の巡回回路は、所定間隔で発生されるスロットパルスに同期して前記初期設定された優先順位データ及び前段の巡回回路からセットされた優先順位データを巡回させて前記後段の巡回回路にセットし、
最後段の巡回回路は、前記スロットパルスに同期して前記初期設定された優先順位データ及び前段の巡回回路からセットされた優先順位データを巡回させて前記Ｎ個のセレクタに供給し、以て前記Ｎ個のセレクタからＮ，Ｎ−１，…，２の最小公倍数に等しいＭ種類の優先順位パターンを順次出力させるパケットスイッチ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットスイッチ及びそのスケジュール方法に関し、特にパケット転送要求の優先順位を入れ替える技術に関する。
【０００２】
【従来の技術】
近年、インターネットは急速な発展を続けており、それに伴いネットワークを構成するスイッチ、ルータといった核ノードは高速なパケット転送能力を備えることが要求されている。このようなパケット転送に使用されるスイッチ方式として、従来、共有バッファ方式、出力バッファ方式、入力バッファ方式等が知られている。
【０００３】
共有バッファ方式が採用された共有バッファ型スイッチは、図１２に示すように、マルチプレクサ１２０２、共有バッファ１２０４、デマルチプレクサ１２０５及びこれらを接続するバス１２０３から構成されている。
【０００４】
マルチプレクサ１２０２は、複数の入力ポート１２０１１〜１２０１ｎから入力されたパケットをマルチプレクスしてバス１２０３に出力する。このバス１２０３に出力されたパケットは共有バッファ１２０４に順次書き込まれる。図示しない制御部は、共通バッファ１２０４に格納されたパケットを所定のアルゴリズムに従って順次読み出してバス１２０３に出力する。このバス１２０３に出力されたパケットはデマルチプレクサ１２０６に供給される。デマルチプレクサ１２０５は、受け取ったパケットを順次デマルチプレクスし、複数の出力ポート１２０６１〜１２０６ｎの何れかから送出する。これにより、パケットをスイッチする機能が実現されている。
【０００５】
この共有バッファ型スイッチは、大規模な共有バッファを備えることができるのでトラフィック特性に優れている。しかしながら、共有バッファ１２０４は、全ての入力ポート１２０１１〜１２０１ｎ及び全ての出力ポート１２０６１〜１２０６ｎからアクセスされるため、バス１２０３上のパケットの転送速度を高速化することが要求されている。しかし、この高速化にも限界があることから、この共有バッファ型スイッチでは高速スイッチの実現が困難である。
【０００６】
また、出力バッファ方式が採用された出力バッファ型スイッチは、図１３に示すように、スイッチ部１３０２及びこのスイッチ部１３０２の出力側に設けられた複数の出力バッファ１３０４１〜１３０４ｎから構成されている。
【０００７】
スイッチ部１３０２は、複数の入力ポート１３０１１〜１３０１ｎからのパケットをスイッチして出力する。このスイッチされたパケットは、出力バッファ１３０４１〜１３０４ｎに格納される。この時、１つの出力ポートへのパケット転送の競合が生じると待ち合わせが行われる。出力バッファ１３０４１〜１３０４ｎは、格納されたパケットを出力ポート１３０５１〜１３０５ｎから順次送出する。
【０００８】
この出力バッファ型スイッチは、１つの出力ポートに同時に全ての入力ポートからのパケットが集中することがあり得る。そのため、パケットの転送速度を、１つのパケットのスイッチ処理に必要な転送速度のｎ（ポート数）倍にしなければならない。従って、この出力バッファ型スイッチでも、上述した共有バッファ型スイッチと同様に、高速スイッチの実現が困難である。
【０００９】
そこで、現在の高速スイッチは、入力バッファ方式を採用した入力バッファ型スイッチが主流となっている。入力バッファ型スイッチは、図１４に示すように、複数の入力バッファ１４０２１〜１４０２ｎ、スケジューラ１４０５及びスイッチ部１４０６から構成されている。
【００１０】
入力バッファ１４０２１〜１４０２ｎは、入力ポート１４０１１〜１４０１ｎからのパケットをそれぞれ受信して格納する。そして、格納されたパケットを宛先情報で指定された出力ポートに転送するために、スケジューラ１４０５にリクエスト１４０４１〜１４０４ｎをそれぞれ送る。
【００１１】
スケジューラ１４０５は入力バッファ１４０２１〜１４０２ｎからのリクエスト１４０４１〜１４０４ｎに基づきスイッチ部１４０６に含まれる各スイッチの方路設定をスケジューリングし、このスケジューリング結果をスイッチ部１４０６に送る。これにより、スイッチ部１４０６に含まれる各スイッチの方路が設定される。また、スケジューラ１４０５は、上記スケジューリング結果に基づき入力バッファ１４０２１〜１４０２ｎにパケット転送許可を表すグラント（図示せず）を通知する。
【００１２】
グラントを受け取った入力バッファ１４０２１〜１４０２ｎは、格納しているパケットをスイッチ部１４０６に転送する。これにより、スイッチ部１４０６は入力されたパケットをスイッチし、出力ポート１４０７１〜１４０７ｎへ転送する。これにより、パケットをスイッチする機能が実現されている。
【００１３】
【発明が解決しようとする課題】
この入力バッファ型スイッチにおいては、スケジューラは、入力バッファからのリクエストに基づき所定のアルゴリズムに従ってスケジューリングを行い、以てスイッチの方路の設定を決定する。従って、入力バッファからのリクエストの優先順位が一定であると、入力ポート間においてスイッチを使用する機会が偏り、公平性が阻害されるという問題がある。
【００１４】
なお、関連する技術として、特開平５−２９２１１６号公報は「入力バッファ型ＡＴＭスイッチの制御回路」を開示している。この制御回路は、ＦＩＦＯメモリの先頭から複数のセルの宛先を読み取る手段と、ＦＩＦＯメモリからのセル送出をセル時間毎に予約管理するテーブルと、各セルの宛先情報を含むセル送出要求信号を送出し、それに対するセル送出時刻を含む応答信号を受信し、更にテーブルを参照して指定されたセル送出時刻にＦＩＦＯメモリからのセル送出を予約すると共に、その時刻にＦＩＦＯメモリからセルを送出させる制御手段とを備え、各セルの送出要求信号を送出後、セル送出を行うまでの一連の処理が終了する前に、次のセルの送出要求信号を送出する。これにより、高速の入力ポートにも容易に対応でき、且つ各回路の処理時間や各回路間の信号伝搬遅延時間のばらつきに柔軟に対応できる。
【００１５】
また、特開平９−１６８０１６号公報は「パケットスイッチ」を開示している。このパケットスイッチは、入力バッファと出力バッファを備えている。そして、出力バッファに複数の出力ポートで共用される複数のバッファ領域を設け、入力バッファにバッファ領域の組み合わせに対応した論理キューを設け、入力制御部によりマルチキャストパケットをその宛先の出力ポートに対応したバッファ領域を含む組み合わせに対応する論理キューに入力し、スケジューリング部およびスイッチ部により宛先の出力ポートに接続されたバッファ領域に転送した後、バッファ領域から宛先の出力ポートに転送する。これにより、マルチキャストに際して入力バッファから出力バッファへの転送パケット量を増大させることなくＨＯＬブロッキングの問題も発生しない。
【００１６】
更に、特許第２９６７７６７号公報は「ＡＴＭスイッチにおけるスケジューリング方式」を開示している。このスケジューリング方式は、各クラスのウエイトとキューの蓄積数から出力セルの選択を行うセル選択部において、予め設定される各クラスのプライオリティを参照し、プライオリティが高いクラスを優先して選択する。即ち、遅延特性が要求されるようなトラヒッククラスに優先度を与え、回転優先制御により出力キューを選択する際に、高優先のクラスから優先して選択する。これにより、他の優先度が低いクラスのセルが出力されるのを待つことなく、セルを出力することが可能となる。その結果、収容するトラヒッククラス数が増加しても、実時間性が要求されるトラヒッククラスの遅延特性の劣化を減少させることができ、ＣＤＶ特性への影響を防ぐことができる。
【００１７】
そこで、本発明の目的は、入力ポート間におけるスイッチの使用機会を公平にすることができるパケットスイッチ及びそのスケジュール方法を提供することにある。
【００１８】
【課題を解決するための手段】
本発明の第１の態様に係るパケットスイッチは、上記目的を達成するために、パケットを入力する入力部と、前記入力部からのパケットをスイッチするスイッチと、前記スイッチを制御するスケジューラ、とを含み、前記スケジューラは、前記入力部からのパケット転送要求の優先順位を変更するシャッフラと、前記シャッフラによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、且つ前記シャッフラによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成するスケジューリングアルゴリズム部と、前記スケジューリングアルゴリズム部で生成されたパケット転送許可の優先順位を前記シャッフラによって変更される前のパケット転送要求の優先順位と同じになるように変更して前記入力部に返送するリシャッフラ、とを備えている。
【００１９】
また、本発明の第２の態様に係るパケットスイッチのスケジュール方法は、上記と同様の目的で、パケットを入力する入力部と、前記入力部からのパケットをスイッチするスイッチ、とが提供され、前記入力部からのパケット転送要求の優先順位をシャッフルし、該シャッフルによって優先順位が変更されたパケット転送要求に基づいて前記スイッチの方路を設定し、前記シャッフルによって優先順位が変更されたパケット転送要求に対応するパケット転送許可を生成し、該生成されたパケット転送許可の優先順位を前記シャッフルによって変更される前のパケット転送要求の優先順位と同じになるようにリシャッフルし、該リシャッフルされたパケット転送許可を前記入力部に返送する、ように構成されている。
【００２０】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。本発明の実施の形態に係るパケットスイッチは、従来の技術の欄で図１４を参照しながら説明したと同様の入力バッファ型スイッチである。
【００２１】
図１は本発明の実施の形態に係るパケットスイッチの構成を示すブロック図である。このパケットスイッチは、複数の入力バッファ１０２１〜１０２ｎ、スケジューラ１０３及びスイッチ部１０４から構成されている。
【００２２】
入力バッファ１０２１〜１０２ｎは、入力ポート１０１１〜１０１ｎからパケットをそれぞれ受信する。各入力バッファ１０２１〜１０２ｎは、出力ポート別キューＶＯＱ（Ｖｉｒｔｕａｌ  Ｏｕｔｐｕｔ  Ｑｕｅｕｅ）を備えており、受信されたパケットを、そのパケットに含まれる宛先情報に従って、出力ポート別にキューイングする。
【００２３】
また、入力バッファ１０２１〜１０２ｎは、受信したパケットを宛先情報で指定される出力ポートに転送するために、スケジューラ１０３に対してパケット転送要求を表すリクエストＲＥＱ＃１〜ＲＥＱ＃Ｎを送る。更に、入力バッファ１０２１〜１０２ｎは、スケジューラ１０３からパケット転送許可を表すグラントＧＮＴ＃１〜ＧＮＴ＃Ｎを受け取った時に、出力ポート別キューＶＯＱにキューイングされているパケットをスイッチ部１０４に転送する。
【００２４】
スケジューラ１０３は、入力バッファ１０２１〜１０２ｎからのリクエストＲＥＱ＃１〜ＲＥＱ＃Ｎに基づきスイッチ部１０４の方路設定をスケジューリングする。そして、このスケジューリング結果に基づきスイッチ部１０４に対して設定信号１０６を送る。また、スケジューラ１０３は、上述したように、入力バッファ１０２１〜１０２ｎにグラントＧＮＴ＃１〜ＧＮＴ＃Ｎを通知する。
【００２５】
スイッチ部１０４は、複数のルーティング用のスイッチを含んでいる。このスイッチ部１０４に含まれるスイッチの開閉の制御、つまり方路の設定はスケジューラ１０３からの設定信号１０６に基づいて行われる。スイッチ部１０４は、入力バッファ１０２１〜１０２ｎからのパケット１１０１〜１１０ｎを、設定信号１０６によって設定された方路に応じてスイッチする。このスイッチされたパケットは出力ポート１０５１〜１０５ｎに転送される。
【００２６】
次に、上記スケジューラ１０３の詳細を図２を参照しながら説明する。このスケジューラ１０３は、シャッフラ２０１、スケジューリングアルゴリズム部２０２及びリシャッフラ２０３から構成されている。シャッフラ２０１は、リクエストＲＥＱ＃１〜ＲＥＱ＃Ｎの優先順位をシャッフルし、シャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃Ｎとして出力する。このシャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃Ｎはスケジューリングアルゴリズム部２０２に供給される。
【００２７】
スケジューリングアルゴリズム部２０２は、例えばシャッフルドリクエストＳＨＦＬＲＥＱ＃１の優先順位が最も高く、シャッフルドリクエストＳＨＦＬＲＥＱ＃Ｎの優先順位が最も低いものとみなしてスケジューリングを行い、このスケジューリングの結果に基づいて設定信号１０６を出力する。また、このスケジューリングの結果に基づいて、パケット転送を許可するシャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃Ｎに対応するシャッフルドグラントＳＨＦＬＧＮＴ＃１〜ＳＨＦＬＧＮＴ＃Ｎをアクティブにし、リシャッフラ２０３に供給する。なお、上記スケジューリングのアルゴリズムとしては種々のアルゴリズムを用いることができる。
【００２８】
リシャッフラ２０３は、シャッフルドグラントＳＨＦＬＧＮＴ＃１〜ＳＨＦＬＧＮＴ＃Ｎの優先順位をリシャッフリングする。即ち、シャッフラ２０１でシャッフリングすることにより入れ替えられたリクエストＲＥＱ＃１〜ＲＥＱ＃Ｎの優先順位を元に戻すような入れ替えを行う。このリシャッフラ２０３でリシャッフルされたシャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃Ｎは、グラントＧＮＴ＃１〜ＧＮＴ＃Ｎとして入力バッファ１０２１〜１０２ｎに供給される。
【００２９】
このように、スケジューラ１０３は、スケジューリングアルゴリズム部２０２がリクエストの入力位置、例えばスケジューラ１０３がハードウェアで構成される場合は回路の物理的な位置、ソフトウェアで構成される場合は変数に付された番号等によって入力ポート間の優先順位が決められるアルゴリズムの場合、リクエストＲＥＱ＃１〜ＲＥＱ＃Ｎをシャッフリングしてスケジューリングを行い、その後、リシャッフリングしてグラントＧＮＴ＃１〜ＧＮＴ＃Ｎを出力する。これにより、各入力ポートからのリクエストの優先順位が適宜変更されるので、各入力ポートのスイッチ使用機会を公平にすることができる。
【００３０】
次に、上記シャッフラ２０１とリシャッフラ２０３の幾つかの具体的な例を説明する。なお、以下では、４個の入力ポート及び４個の出力ポートを有するスイッチに適用される場合について説明するが、入力ポート及び出力ポートの数は４個に限定されることなく任意である。
【００３１】
（実施の形態１）
図３は、本発明の実施の形態１に係るパケットスイッチに適用されるスケジューラ１０３に含まれるシャッフラ２０１の構成を示すブロック図である。このシャッフラ２０１は、優先度巡回回路３０１、３０２及び３０３から構成されている。優先度巡回回路３０１、３０２及び３０３は、例えばリングシフトレジスタから構成される。
【００３２】
１段目の優先度巡回回路３０１は、１位入力端子、２位入力端子、１位出力端子、２位出力端子及び巡回端子を備えている。この優先度巡回回路３０１の１位入力端子にはリクエストＲＥＱ＃３が、２位入力端子にはリクエストＲＥＱ＃４がそれぞれ入力される。また、優先度巡回回路３０１の１位出力端子は優先度巡回回路３０２の２位入力端子に、２位出力端子は優先度巡回回路３０２の３位入力端子にそれぞれ接続されている。更に、優先度巡回回路３０１の巡回端子には、優先度巡回回路３０２からの桁上がり信号ＣＲＹ２が入力される。
【００３３】
この優先度巡回回路３０１には、リクエストＲＥＱ＃３及びＲＥＱ＃４が初期設定される。そして、桁上がり信号ＣＲＹ２が入力される毎に、設定されたリクエストＲＥＱ＃３及びＲＥＱ＃４を巡回させて出力する。従って、初期状態では、１位出力端子からリクエストＲＥＱ＃３が、２位出力端子からリクエストＲＥＱ＃４がそれぞれ出力される。この状態で、巡回端子に桁上げ信号ＣＲＹ２が入力されると、優先度巡回回路３０１は、１位出力端子からリクエストＲＥＱ＃４を、２位出力端子からリクエストＲＥＱ＃３をそれぞれ出力する。以下、同様にして、巡回端子に桁上げ信号ＣＲＹ２が入力される毎に、リクエストＲＥＱ＃３及びＲＥＱ＃４がサイクリックに出力される。
【００３４】
２段目の優先度巡回回路３０２は、１位〜３位入力端子、１位〜３位出力端子、巡回端子及び桁上がり端子を備えている。この優先度巡回回路３０２の１位入力端子にはリクエストＲＥＱ＃２が入力される。また、２位入力端子には優先度巡回回路３０１の１位出力端子からの信号が、３位入力端子には優先度巡回回路３０１の２位出力端子からの信号がそれぞれ入力される。
【００３５】
また、優先度巡回回路３０２の１位出力端子は優先度巡回回路３０３の２位入力端子に、２位出力端子は優先度巡回回路３０３の３位入力端子に、３位出力端子は優先度巡回回路３０３の４位入力端子にそれぞれ接続されている。また、優先度巡回回路３０２の巡回端子には、優先度巡回回路３０３からの桁上がり信号ＣＲＹ１が入力される。更に、優先度巡回回路３０２の桁上がり端子からは桁上がり信号ＣＲＹ２を出力される。この桁上がり信号ＣＲＹ２は、上述したように、優先度巡回回路３０１の巡回端子に供給される。
【００３６】
この優先度巡回回路３０２には、リクエストＲＥＱ＃２、並びに、優先度巡回回路３０１をパススルーしたリクエストＲＥＱ＃４及びＲＥＱ＃４が初期設定される。そして、桁上がり信号ＣＲＹ１が入力される毎に、設定されたリクエストＲＥＱ＃２〜ＲＥＱ＃４を巡回させて出力する。従って、初期状態では、１位出力端子からリクエストＲＥＱ＃２が、２位出力端子からリクエストＲＥＱ＃３が、３位出力端子からリクエストＲＥＱ＃４がそれぞれ出力される。
【００３７】
この状態で、巡回端子に桁上げ信号ＣＲＹ１が入力されると、優先度巡回回路３０２は、１位出力端子からリクエストＲＥＱ＃３を、２位出力端子からリクエストＲＥＱ＃４を、３位出力端子からリクエストＲＥＱ＃２をそれぞれ出力し、更に巡回端子に桁上げ信号ＣＲＹ１が入力されると、１位出力端子からリクエストＲＥＱ＃４を、２位出力端子からリクエストＲＥＱ＃２を、３位出力端子からリクエストＲＥＱ＃３をそれぞれ出力する。以下、同様にして、巡回端子に桁上げ信号ＣＲＹ１が入力される毎に、リクエストＲＥＱ＃２、ＲＥＱ＃３及びＲＥＱ＃４がサイクリックに出力される。そして、桁上がり信号ＣＲＹ１が３回入力される毎に桁上がり端子から桁上がり信号ＣＲＹ２が出力され、この桁上がり信号ＣＲＹ２によって巡回された優先度巡回回路３０１からの信号が下位の２ビットにロードされる。
【００３８】
３段目の優先度巡回回路３０３は、１位〜４位入力端子、１位〜４位出力端子、巡回端子及び桁上がり端子を備えている。この優先度巡回回路３０３の１位入力端子にはリクエストＲＥＱ＃１が入力される。また、２位入力端子には優先度巡回回路３０２の１位出力端子からの信号が、３位入力端子には優先度巡回回路３０２の２位出力端子からの信号が、４位入力端子には優先度巡回回路３０２の３位出力端子からの信号がそれぞれ入力される。
【００３９】
また、優先度巡回回路３０３の１位出力端子からはシャッフルドリクエストＳＨＦＬＲＥＱ＃１が、２位出力端子からはシャッフルドリクエストＳＨＦＬＲＥＱ＃２が、３位出力端子からはシャッフルドリクエストＳＨＦＬＲＥＱ＃３が、４位出力端子からはシャッフルドリクエストＳＨＦＬＲＥＱ＃４がそれぞれ出力される。また、優先度巡回回路３０３の巡回端子には、図示しない制御回路から、スロットパルスＳＰＬＳが入力される。このスロットパルスＳＰＬＳは、スケジューラ１０３の動作単位であるスロット毎に発生される。更に、優先度巡回回路３０３の桁上がり端子からは桁上がり信号ＣＲＹ１が出力される。この桁上がり信号ＣＲＹ１は、上述したように、優先度巡回回路３０２の巡回端子に供給される。
【００４０】
この優先度巡回回路３０３には、リクエストＲＥＱ＃１、優先度巡回回路３０２をパススルーしたリクエストＲＥＱ＃２、並びに優先度巡回回路３０１及び３０２をパススルーしたリクエストＲＥＱ＃３及びＲＥＱ＃４が初期設定される。そして、スロットパルスＳＰＬＳが入力される毎に、設定されたリクエストＲＥＱ＃１〜ＲＥＱ＃４を巡回させて出力する。従って、初期状態では、１位出力端子からリクエストＲＥＱ＃１が、２位出力端子からリクエストＲＥＱ＃２が、３位出力端子からリクエストＲＥＱ＃３が、４位出力端子からリクエストＲＥＱ＃４が、それぞれシャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃４として出力される。
【００４１】
この状態で、巡回端子にスロットパルスＳＰＬＳが入力されると、優先度巡回回路３０３は、１位出力端子からリクエストＲＥＱ＃２を、２位出力端子からリクエストＲＥＱ＃３を、３位出力端子からリクエストＲＥＱ＃４を、４位出力端子からリクエストＲＥＱ＃１をそれぞれ出力し、更に巡回端子にスロットパルスＳＰＬＳが入力されると、１位出力端子からリクエストＲＥＱ＃３を、２位出力端子からリクエストＲＥＱ＃４を、３位出力端子からリクエストＲＥＱ＃１を、４位出力端子からリクエストＲＥＱ＃２をそれぞれ出力する。以下、同様にして、巡回端子にスロットパルスＳＰＬＳが入力される毎に、リクエストＲＥＱ＃１、ＥＱ＃２、ＲＥＱ＃３及びＲＥＱ＃４がサイクリックに出力される。そして、スロットパルスＳＰＬＳが４回入力される毎に桁上がり端子から桁上がり信号ＣＲＹ１が出力され、この桁上がり信号ＣＲＹ１によって巡回された優先度巡回回路３０２からの信号が下位の３ビットにロードされる。
【００４２】
図４は、本発明の実施の形態１に係るパケットスイッチに適用されるスケジューラ１０３に含まれるリシャッフラ２０３の構成を示すブロック図である。このリシャッフラ２０３は、優先度巡回回路４０１、４０２及び４０３から構成されている。優先度巡回回路４０１、４０２及び４０３は、例えばリングシフトレジスタから構成されている。
【００４３】
１段目の優先度巡回回路４０１は、１位〜４位入力端子、１位〜４位出力端子、巡回端子及び桁上がり端子を備えている。この優先度巡回回路４０１の１位入力端子にはシャッフルドグラントＳＨＦＬＧＮＴ＃１が、２位入力端子にはシャッフルドグラントＳＨＦＬＧＮＴ＃２が、３位入力端子にはシャッフルドグラントＳＨＦＬＧＮＴ＃３が、４位入力端子にはシャッフルドグラントＳＨＦＬＧＮＴ＃４がそれぞれ入力される。
【００４４】
また、優先度巡回回路４０１の１位出力端子からはシャッフルドグラントＳＨＦＬＧＮＴ＃１がグラントＧＮＴ＃１として出力される。また、優先度巡回回路４０１の２位出力端子は優先度巡回回路４０２の１位入力端子に、３位出力端子は優先度巡回回路４０２の２位入力端子に、４位出力端子は優先度巡回回路４０２の３位入力端子に、それぞれ接続されている。また、優先度巡回回路４０１の巡回端子には、図示しない制御回路から、スロットパルスＳＰＬＳが入力される。更に、優先度巡回回路４０１の桁上がり端子は桁上がり信号ＣＲＹ１を出力する。この桁上がり信号ＣＲＹ１は、優先度巡回回路４０２の巡回端子に供給される。
【００４５】
この優先度巡回回路４０１には、シャッフルドグラントＳＨＦＬＧＮＴ＃１〜ＳＨＦＬＧＮＴ＃４が初期設定される。そして、巡回端子にスロットパルスＳＰＬＳが入力される毎に、設定されたシャッフルドグラントＳＨＦＬＧＮＴ＃１〜ＳＨＦＬＧＮＴ＃４を巡回させて出力する。従って、初期状態では、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃１が、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃２が、３位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３が、４位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４がそれぞれ出力される。上記１位出力端子から出力されるシャッフルドグラントＳＨＦＬＧＮＴ＃１は、グラントＧＮＴ＃１として外部に出力される。
【００４６】
この状態で、巡回端子にスロットパルスＳＰＬＳが入力されると、優先度巡回回路４０１は、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４を、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃１を、３位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃２を、４位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３をそれぞれ出力し、更に巡回端子にスロットパルスＳＰＬＳが入力されると、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３を、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４を、３位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃１を、４位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃２をそれぞれ出力する。以下、同様にして、巡回端子にスロットパルスＳＰＬＳが入力される毎に、シャッフルドグラントＳＨＦＬＧＮＴ＃１〜ＳＨＦＬＧＮＴ＃４がサイクリックに出力される。そして、スロットパルスＳＰＬＳが４回入力される毎に桁上がり端子から桁上がり信号ＣＲＹ１が出力される。優先度巡回回路４０２は、この桁上がり信号ＣＲＹ１に応答して優先度巡回回路４０１からの巡回された信号をロードする。
【００４７】
２段目の優先度巡回回路４０２は、１位〜３位入力端子、１位〜３位出力端子、巡回端子及び桁上がり端子を備えている。この優先度巡回回路４０２の１位入力端子には優先度巡回回路４０１の２位出力端子からの信号が、２位入力端子には優先度巡回回路４０１の３位出力端子からの信号が、３位入力端子には優先度巡回回路４０１の４位出力端子からの信号がそれぞれ入力される。
【００４８】
また、優先度巡回回路４０２の１位出力端子からはシャッフルドグラントＳＨＦＬＧＮＴ＃２がグラントＧＮＴ＃２として出力される。また、優先度巡回回路４０２の２位出力端子は優先度巡回回路４０３の１位入力端子に、３位出力端子は優先度巡回回路４０３の２位入力端子にそれぞれ接続されている。また、優先度巡回回路４０２の巡回端子には、優先度巡回回路４０１からの桁上がり信号ＣＲＹ１が入力される。更に、優先度巡回回路４０２の桁上がり端子は桁上がり信号ＣＲＹ２を出力する。この桁上がり信号ＣＲＹ２は、優先度巡回回路４０３の巡回端子に供給される。
【００４９】
この優先度巡回回路４０２には、優先度巡回回路４０１をパススルーしたシャッフルドグラントＳＨＦＬＧＮＴ＃２、ＳＨＦＬＧＮＴ＃３及びＳＨＦＬＧＮＴ＃４が初期設定される。そして、桁上がり信号ＣＲＹ１が入力される毎に、設定されたシャッフルドグラントＳＨＦＬＧＮＴ＃２〜ＳＨＦＬＧＮＴ＃４を巡回させて出力する。従って、初期状態では、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃２が、２位出力端子からＳＨＦＬＧＮＴ＃３が、３位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４がそれぞれ出力される。上記２位出力端子から出力されるシャッフルドグラントＳＨＦＬＧＮＴ＃２は、グラントＧＮＴ＃２として外部に出力される。
【００５０】
この状態で、巡回端子に桁上げ信号ＣＲＹ１が入力されると、優先度巡回回路４０２は、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４を、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃２を、３位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３をそれぞれ出力し、更に巡回端子に桁上げ信号ＣＲＹ１が入力されると、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３を、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４を、３位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃２をそれぞれ出力する。以下、同様にして、巡回端子に桁上がり信号ＣＲＹ１が入力される毎に、シャッフルドグラントＳＨＦＬＧＮＴ＃２〜ＳＨＦＬＧＮＴ＃４がサイクリックに出力される。そして、桁上がり信号ＣＲＹ１が３回入力される毎に桁上がり端子から桁上がり信号ＣＲＹ２が出力される。優先度巡回回路４０３は、この桁上がり信号ＣＲＹ２に応答して優先度巡回回路４０２からの巡回された信号をロードする。
【００５１】
３段目の優先度巡回回路４０３は、１位入力端子、２位入力端子、１位出力端子、２位出力端子及び巡回端子を備えている。この優先度巡回回路４０３の１位入力端子には優先度巡回回路４０２の２位出力端子からの信号が、２位入力端子には優先度巡回回路４０２の３位出力端子からの信号がそれぞれ入力される。また、優先度巡回回路４０３の１位出力端子からはシャッフルドグラントＳＨＦＬＧＮＴ＃３がグラントＧＮＴ＃３として、２位出力端子からはシャッフルドグラントＳＨＦＬＧＮＴ＃４がグラントＧＮＴ＃４としてそれぞれ出力される。更に、優先度巡回回路４０３の巡回端子には、優先度巡回回路４０２からの桁上がり信号ＣＲＹ２が入力される。
【００５２】
この優先度巡回回路４０３には、優先度巡回回路４０１及び優先度巡回回路４０２をパススルーしたシャッフルドグラントＳＨＦＬＧＮＴ＃３及びＳＨＦＬＧＮＴ＃４が初期設定される。そして、桁上がり信号ＣＲＹ２が入力される毎に、設定されたシャッフルドグラントＳＨＦＬＧＮＴ＃３及びＳＨＦＬＧＮＴ＃４を巡回させて出力する。従って、初期状態では、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３がグラントＧＮＴ＃３として、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４がグラントＧＮＴ＃４としてそれぞれ出力される。
【００５３】
この状態で、巡回端子に桁上げ信号ＣＲＹ２が入力されると、優先度巡回回路４０３は、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４を、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３をそれぞれ出力し、更に巡回端子に桁上げ信号ＣＲＹ２が入力されると、１位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃３を、２位出力端子からシャッフルドグラントＳＨＦＬＧＮＴ＃４をそれぞれ出力する。以下、同様にして、桁上がり信号ＣＲＹ２が入力される毎に、シャッフルドグラントＳＨＦＬＧＮＴ＃３及びＳＨＦＬＧＮＴ＃４がサイクリックに出力される。
【００５４】
次に、図７を参照しながら、上述したように構成される、実施の形態１に係るスケジューラ１０３に適用されるシャッフラ２０１の動作を説明する。なお、リシャッフラ２０３は、シャッフラ２０１と逆の動作をするだけであるので、その動作の説明は省略する。
【００５５】
シャッフラ２０１では、３段目の優先度巡回回路３０３は、図７の「巡回回路巡回量」に示すように、スロット毎に巡回量をインクリメントし、２段目の優先度巡回回路３０２は３段目の優先度巡回回路３０３が一周したときに発生する桁上がり信号ＣＲＹ１によって巡回量をインクリメントし、１段目の優先度巡回回路３０１は２段目の優先度巡回回路３０２が一周したときに発生する桁上がり信号ＣＲＹ２によって巡回量をインクリメントする。
【００５６】
また、桁上がり信号ＣＲＹ１が発生した時は、優先度巡回回路３０２の出力が優先度巡回回路３０３の下位３ビットにロードされる。更に、桁上がり信号ＣＲＹ２が発生した時は、優先度巡回回路３０１の出力が優先度巡回回路３０２の下位２ビットにロードされる。
【００５７】
これにより、各スロットにおける、各優先度巡回回路３０１〜３０３の巡回回路巡回量、１段目の優先度巡回回路３０１を通過後の各入力ポートの優先順位、２段目の優先度巡回回路３０２を通過後の各入力ポートの優先順位、３段目の優先度巡回回路３０３を通過後の各入力ポートの優先順位は、それぞれ図７に示すように変化する。シャッフリングの１周期は入力ポート数をＮとすると、「Ｎ×Ｎ−１×…×２＝Ｎ！」となり、全てのスロットで異なった優先順位パターンが発生される。従って、シャッフリングの１周期で全ての優先順位パターンを発生させることができる。
【００５８】
（実施の形態２）
図５は、本発明の実施の形態２に係るパケットスイッチに適用されるスケジューラ１０３に含まれるシャッフラ２０１の構成を示すブロック図である。このシャッフラ２０１は、優先度巡回回路５０１、５０２及び５０３から構成されている。
【００５９】
優先度巡回回路５０１、５０２及び５０３は、実施の形態１に係る優先度巡回回路３０１、３０２及び３０３にそれぞれ対応する。この実施の形態２に係るシャッフラ２０１では、優先度巡回回路５０１、５０２及び５０３のそれぞれの巡回端子にスロットパルスＳＰＬＳが入力される点が上述した実施の形態１と異なる。また、実施の形態１では、桁上げ信号ＣＲＹ１及びＣＲＹ２が入力された場合に、その桁上げ信号ＣＲＹ１及びＣＲＹ２によって変化した前段の優先度巡回回路の内容をロードしてリクエストの優先順位を決定しているが、この実施の形態２では、スロットパルスＳＰＬＳによって変化した前段の優先度巡回回路の内容をロードした後に更に巡回させることにより新たな優先順位を決定している。
【００６０】
図６は、本発明の実施の形態２に係るスケジューラ１０３に適用されるリシャッフラ２０３の構成を示すブロック図である。このリシャッフラ２０３は、優先度巡回回路６０１、６０２及び６０３から構成されている。
【００６１】
優先度巡回回路６０１、６０２及び６０３は、実施の形態１に係る優先度巡回回路４０１、４０２及び４０３とそれぞれ対応している。この実施の形態２に係るリシャッフラ２０３では、優先度巡回回路６０１、６０２及び６０３のそれぞれの巡回端子にスロットパルスＳＰＬＳが入力される点が上述した実施の形態１と異なる。また、実施の形態１では、桁上げ信号ＣＲＹ１及びＣＲＹ２が入力された場合に、その桁上げ信号ＣＲＹ１及びＣＲＹ２によって変化した前段の優先度巡回回路の内容を後段の優先度巡回回路にロードしてグラントの優先順位を決定しているが、この実施の形態２では、スロットパルスＳＰＬＳによって変化した前段の優先度巡回回路の内容を後段の優先度巡回回路にロードした後に更に巡回させることによりグラントの優先順位を決定している。
【００６２】
次に、図８を参照しながら、上述したように構成される、実施の形態２に係るスケジューラ１０３に適用されるシャッフラ２０１の動作を説明する。なお、リシャッフラ２０３は、シャッフラ２０１と逆の動作をするだけであるので、その動作の説明は省略する。
【００６３】
実施の形態１に係るシャッフラ２０１では、全ての優先順位パターンを発生させることができるが、シャッフリングの周期がＮ！となり、入力ポート数Ｎが増えるとシャッフリングの周期が非常に長くなってしまう。また、前段側の優先度巡回回路は短期間では巡回量が変化しない。従って、短期間では、前段側でシャッフリングされる入力ポートのスイッチ使用機会が偏り、不公平になる。
【００６４】
これに対し、実施の形態２では、図８の「巡回回路巡回量」に示すように、全ての優先度巡回回路の巡回量がスロット毎にインクリメントされる。その結果、前段側の優先度巡回回路の巡回量もスロット毎に変化するので、短期間であっても、入力ポートのスイッチ使用機会の公平性を実現できる。また、シャッフリングの周期は、Ｎ，Ｎ−１，…，２の数値の最小公倍数となり、実施の形態１のＮ！より短くなる。
【００６５】
（実施の形態３）
図９は、本発明の実施の形態３に係るスケジューラ１０３に適用されるシャッフラ２０１の構成を示すブロック図である。このシャッフラ２０１は、優先度巡回回路９０１、９０２及び９０３、並びにゲート９０４及び９０５から構成されている。
【００６６】
優先度巡回回路９０１、９０２及び９０３の構成は、実施の形態２に係る優先度巡回回路５０１、５０２及び５０３とそれぞれ同じである。この実施の形態３に係るシャッフラ２０１では、優先度巡回回路９０１の巡回端子にはスロットパルスＳＰＬＳがゲート９０４を介して入力され、優先度巡回回路９０２の巡回端子にはスロットパルスＳＰＬＳがゲート９０５を介して入力される点が上述した実施の形態２と異なる。
【００６７】
上述した実施の形態２に係るシャッフラ２０１では、実施の形態１に係るシャッフラよりシャッフリングの周期が短くなるという利点がある。これは、実施の形態２に係るシャッフラでは、実施の形態１のそれで生成されるＮ！種類の優先順位パターンのうちの一部を生成しているからに他ならない。このため実施の形態２に係るシャッフラでは生成されない優先順位パターンが存在する。
【００６８】
この実施の形態３に係るシャッフラでは、シャッフリングが何周かする毎に１スロットだけ、ゲート９０４及び９０５によって巡回信号の供給を抑止する。例えば、図示しない制御回路により、優先度巡回回路９０５への巡回信号の供給をシャッフリングが１周する毎に、優先度巡回回路９０１の巡回信号を３周する毎に１スロットだけ抑止する。
【００６９】
この構成により、シャッフリングの１周期毎に各優先度巡回回路の巡回量にオフセットが与えられることになるので、実施の形態２に係るシャッフラでは生成されなかった優先順位パターンが生成される。
【００７０】
なお、この実施の形態３に係るリシャッフラは、図６に示したリシャッフラにおける優先度巡回回路６０２及び６０３にゲートを追加し、優先度巡回回路６０２及び６０３の巡回端子にゲートを介してスロットパルスＳＰＬＳを供給するように構成することで実現できる。
【００７１】
（実施の形態４）
図１０は、本発明の実施の形態４に係るスケジューラ１０３に適用されるシャッフラ２０１の構成を示すブロック図である。このシャッフラ２０１は、優先度巡回回路１００１、１００２及び１００３、並びにセレクタ１００４〜１００７から構成されている。
【００７２】
優先度巡回回路１００１、１００２及び１００３は、実施の形態１に係るシャッフラの優先度巡回回路３０１、３０２及び３０３にそれぞれ対応する。優先度巡回回路１００１の１位入力端子には実施の形態１におけるリクエストＲＥＱ＃１の代わりに優先順位情報Ｓ１が入力される。優先度巡回回路１００２の１位入力端子には実施の形態１におけるリクエストＲＥＱ＃２の代わりに優先順位情報Ｓ２が入力される。優先度巡回回路１００３の１位入力端子には実施の形態１におけるリクエストＲＥＱ＃３の代わりに優先順位情報Ｓ３が、２位入力端子には実施の形態１におけるリクエストＲＥＱ＃４の代わりに優先順位情報Ｓ４がそれぞれ入力される。
【００７３】
優先順位情報Ｓ１〜Ｓ４の各々は、２ビットのデータから構成されており、Ｓ１＝００Ｂ（末桁の「Ｂ」は２進数を表し、以下においても同じ）、Ｓ２＝０１Ｂ、Ｓ２＝１０Ｂ、Ｓ３＝１１Ｂとすることができる。従って、優先度巡回回路１００１、１００２及び１００の各々は、２ビットの優先順位情報を巡回させることになる。これら優先度巡回回路１００１、１００２及び１００の動作は、２ビットの優先順情報を巡回させることを除けば、実施の形態１のシャッフラの動作と同じである。
【００７４】
従って、優先度巡回回路１００３の各出力端子からは２ビットのシャッフルされた優先順位情報が出力される。優先度巡回回路１００３の１位出力端子から出力されるシャッフルされた優先順位情報は、セレクタ１００４のセレクト端子へ、２位出力端子から出力されるシャッフルされた優先順位情報は、セレクタ１００５のセレクト端子へ、３位出力端子から出力されるシャッフルされた優先順位情報は、セレクタ１００６のセレクト端子へ、４位出力端子から出力されるシャッフルされた優先順位情報は、セレクタ１００７のセレクト端子へ、それぞれ供給される。
【００７５】
各セレクタ１００４、１００５、１００６及び１００７の第１〜第４入力端子には、リクエストＲＥＱ＃１〜ＲＥＱ＃４がそれぞれ入力される。そして、セレクタ１００４、１００５、１００６及び１００７の出力端子からは、シャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃４がそれぞれ出力される。
【００７６】
以上のように構成される実施の形態４に係るシャッフラによれば、実施の形態１に係るシャッフラと同様の効果に加え次の効果を奏する。即ち、この実施の形態４に係るシャッフラによれば、シャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃４は、リクエストＲＥＱ＃１〜ＲＥＱ＃４が入力されてからセレクタの１段分の遅延時間で出力される。これに対し、実施の形態１に係るシャッフラによれば、シャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃４は、リクエストＲＥＱ＃１〜ＲＥＱ＃４が入力されてから優先度巡回回路の３段分の遅延時間で出力される。従って、この実施の形態４に係るシャッフラは、リクエストＲＥＱ＃１〜ＲＥＱ＃４が入力されてからシャッフルドリクエストＳＨＦＬＲＥＱ＃１〜ＳＨＦＬＲＥＱ＃４が出力されるまでの遅延時間が問題になる場合に有効である。
【００７７】
なお、この実施の形態４に係るリシャッフラは、図４に示したリシャッフラに４個のセレクタを追加し、優先度巡回回路４０１に優先順位情報Ｓ１〜Ｓ４を供給し、優先度巡回回路４０１の１位の出力端子、優先度巡回回路４０２の１位出力端子、優先度巡回回路４０３の１位出力端子及び２位出力端子からの信号を上記４個のセレクタのセレクト端子にそれぞれ供給し、各セレクタの入力端子にシャッフルドグラントＳＨＦＬＧＮＴ＃１〜ＳＨＦＬＧＮＴ＃１を供給するように構成することにより実現できる。
【００７８】
（実施の形態５）
図１１は、本発明の実施の形態５に係るスケジューラ１０３に適用されるシャッフラ２０１の構成を示すブロック図である。このシャッフラ２０１は、優先度巡回回路１１０１、１１０２及び１１０３、並びにセレクタ１１０４〜１１０７から構成されている。
【００７９】
優先度巡回回路１１０１、１１０２及び１１０３、並びにセレクタ１１０４〜１１０７の構成は、実施の形態４に係る優先度巡回回路１００１、１００２及び１００３、並びにセレクタ１００４〜１００７とそれぞれ同じである。この実施の形態５に係るシャッフラ２０１では、優先度巡回回路１１０１及び１１０２のそれぞれの巡回端子にスロットパルスＳＰＬＳが入力される点が、上述した実施の形態４に係るシャッフラと相違する。
【００８０】
即ち、この実施の形態５に係るシャッフラは、実施の形態４に係るシャッフラに、実施の形態２と同様の変更を加えたものである。従って、上述した実施の形態５に係るシャッフラによる効果に加え、実施の形態２に係るシャッフラの効果を奏する。
【００８１】
以上説明したように、本発明の実施の形態１〜５に係るパケットスイッチによれば、各入力ポートからのリクエスト間の優先順位をまんべんなく入れ替えることができ、入力ポート間のスイッチ使用の機会を公平にすることができる。
【００８２】
【発明の効果】
以上詳述したように、本発明によれば、入力ポート間におけるスイッチの使用機会を公平にすることができるパケットスイッチ及びそのスケジュール方法を提供できる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るパケットスイッチの構成を示すブロック図である。
【図２】図１に示したスケジューラの概略構成を示すブロック図である。
【図３】本発明の実施の形態１に係るパケットスイッチに適用されるスケジューラのシャッフラの構成を示すブロック図である。
【図４】本発明の実施の形態１に係るパケットスイッチに適用されるスケジューラのリシャッフラの構成を示すブロック図である。
【図５】本発明の実施の形態２に係るパケットスイッチに適用されるスケジューラのシャッフラの構成を示すブロック図である。
【図６】本発明の実施の形態２に係るパケットスイッチに適用されるスケジューラのリシャッフラの構成を示すブロック図である。
【図７】本発明の実施の形態１に係るパケットスイッチに適用されるスケジューラのリシャッフラの動作を説明するための図である。
【図８】本発明の実施の形態２に係るパケットスイッチに適用されるスケジューラのリシャッフラの動作を説明するための図である。
【図９】本発明の実施の形態３に係るパケットスイッチに適用されるスケジューラのシャッフラの構成を示すブロック図である。
【図１０】本発明の実施の形態４に係るパケットスイッチに適用されるスケジューラのシャッフラの構成を示すブロック図である。
【図１１】本発明の実施の形態５に係るパケットスイッチに適用されるスケジューラのシャッフラの構成を示すブロック図である。
【図１２】従来の共有バッファ型スイッチの一例を示す図である。
【図１３】従来の出力バッファ型スイッチの一例を示す図である。
【図１４】従来の入力バッファ型スイッチの一例を示す図である。
【符号の説明】
１０１１〜１０１ｎ  入力ポート
１０２１〜１０２ｎ  入力バッファ
１０３  スケジューラ
１０４  スイッチ部
１０５  出力ポート
２０１  シャッフラ
２０２  スケジューリングアルゴリズム部
２０３  リシャッフラ
３０１〜３０３、４０１〜４０３、５０１〜５０３、６０１〜６０３、９０１〜９０３、１００１〜１００３、１１０１〜１１０３  優先度巡回回路
９０４、９０５  ゲート
１００４〜１００７、１１０４〜１１０７  セレクタ
ＶＯＱ  出力ポート別キュー
【図１】
0003594076.tif 000002
【図２】
0003594076.tif 000003
【図３】
0003594076.tif 000004
【図４】
0003594076.tif 000005
【図５】
0003594076.tif 000006
【図６】
0003594076.tif 000007
【図７】
0003594076.tif 000008
【図８】
0003594076.tif 000009
【図９】
0003594076.tif 000010
【図１０】
0003594076.tif 000011
【図１１】
0003594076.tif 000012
【図１２】
0003594076.tif 000013
【図１３】
0003594076.tif 000014
【図１４】
0003594076.tif 000015