(57)【特許請求の範囲】
【請求項１】
入力バッファ型パケット交換システムにおいて、入力ポートからのデータに対するスケジューリングを行って当該データの宛先に対応する出力ポートに出力するスケジューラを含むスケジューリング装置であって、各々独立に前記スケジューリングを行いかつ前記スケジューラを分割してなる複数のサブスケジューラブロックと、前記スケジューリングの対象となる出力ポートが重複しないように前記複数のサブスケジューラブロック各々に割り当てる割り当て手段とを有することを特徴とするスケジューリング装置。
【請求項２】
前記割り当て手段は、単位スケジューリング時間で前記スケジューリングの対象となる出力ポートが重複しないように前記複数のサブスケジューラブロックに割り当てるよう構成したことを特徴とする請求項１記載のスケジューリング装置。
【請求項３】
前記割り当て手段は、前記出力ポートの割り当てを外部からの制御に基づいて行うよう構成したことを特徴とする請求項１または請求項２記載のスケジューリング装置。
【請求項４】
Ｎ×Ｎ入力バッファ型パケット交換システム（Ｎは正の整数）において前記スケジューラをＮ／Ｋ個（Ｋ＜Ｎ、ＫはＮの約数とする）のサブスケジューラブロックに分割するようにしたことを特徴とする請求項１から請求項３のいずれか記載のスケジューリング装置。
【請求項５】
入力バッファ型パケット交換システムにおいて、スケジューラを用いて入力ポートからのデータに対するスケジューリングを行って当該データの宛先に対応する出力ポートに出力するスケジューリング方法であって、前記スケジューラを各々独立に前記スケジューリングを行う複数のサブスケジューラブロックに分割し、前記スケジューリングの対象となる出力ポートが重複しないように前記複数のサブスケジューラブロック各々に割り当てるようにしたことを特徴とするスケジューリング方法。
【請求項６】
前記出力ポートを前記複数のサブスケジューラブロック各々に割り当てる際に、単位スケジューリング時間で前記スケジューリングの対象となる出力ポートが重複しないように前記複数のサブスケジューラブロックに割り当てるようにしたことを特徴とする請求項５記載のスケジューリング方法。
【請求項７】
前記出力ポートを前記複数のサブスケジューラブロック各々に割り当てる際に、前記出力ポートの割り当てを外部からの制御に基づいて行うようにしたことを特徴とする請求項５または請求項６記載のスケジューリング方法。
【請求項８】
Ｎ×Ｎ入力バッファ型パケット交換システム（Ｎは正の整数）において前記スケジューラをＮ／Ｋ個（Ｋ＜Ｎ、ＫはＮの約数とする）のサブスケジューラブロックに分割するようにしたことを特徴とする請求項５から請求項７のいずれか記載のスケジューリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はスケジューリング装置及びそれに用いるスケジューリング方法に関し、特に入力バッファ型のパケット交換システムにおけるスケジューリング方法に関する。
【０００２】
【従来の技術】
近年、トラフィックの急激な増加に伴い、大容量かつ高速な交換システムが必要とされており、これを実現する手段として入力バッファ型のパケット交換システムが有力視されている。
【０００３】
しかしながら、入力バッファ型のパケット交換システムの場合には、入力バッファから送出されるデータが出力ポート間で衝突しないためのスケジューラが必要であり、入出力ポート速度でスケジューリング処理が可能な高速なスケジューラ及びスケジューリング方法が必要とされている。
【０００４】
上記の高速なスケジュ−リングを実現する方法としては、特開２０００−１７４８１７号公報に開示されたＲＲＧＳ（Ｒｏｕｎｄ  Ｒｏｂｉｎ  ＧｒｅｅｄｙＳｃｈｅｄｕｌｉｎｇ）アルゴリズム、またはフレーム化ＲＲＧＳアルゴリズム等が提案されている。
【０００５】
このフレーム化ＲＲＧＳを、８×８入力バッファ型パケット交換システムに適用した構成例を図５に示し、そのタイムチャートを図６に示す。これら図５及び図６を参照して上記の構成例について説明する。
【０００６】
図５に示すように、フレーム化ＲＲＧＳを適用した構成例では、スケジューラ部５をサブスケジューラブロック（ＳＢ）６が分割されていない。つまり、スケジューラ部５はサブスケジューラブロック６と、セレクト信号生成部７とから構成され、サブスケジューラブロック６はキューテーブル（ＱＴ）６１−１〜６１−８と、ラウンドロビン回路（ＲＲ）６２−１〜６２−８と、ＧＮＴ（グラント信号）生成部６３−１〜６３−８とから構成されている。
【０００７】
図６において、Ｔ時間は各ラウンドロビン回路６２−１〜６２−８においてキュー信号（ＱＳ）６０１−１〜６０１−８，６０２−１〜６０２−８，・・・，６０８−１〜６０８−８から１出力ポートを選択するのに要する時間を表し、スケジューラ部５はこのＴ時間を基準に動作する。ラウンドロビン回路６２−１〜６２−８においては１出力ポートを選択するのに必要な処理時間が出力ポート数に正比例する。
【０００８】
また、各リザルト信号（ＲＥＳ）７０１−１〜７０１−８，７０２−１〜７０２−８，・・・，７０８−１〜７０８−８に示した値は、図中に示したＴ時間（Ｔ９→Ｔ＝９を示す）にＧＮＴ６０−１〜６０−８として送出する出力ポートを選択することを表す。
【０００９】
図５及び図６を用いてサブスケジューラブロック６の動作について説明する。図５に示すキューテーブル６１−１〜６１−８、ラウンドロビン回路６２−１〜６２−８、ＧＮＴ生成部６３−１〜６３−８各々は全出力ポートの８ポートに対して処理を行う。また、サブスケジューラブロック６には８個のラウンドロビン回路６２−１〜６２−８がリング構造をとっているため、図６に示すように、同時に８スケジューリングがパイプライン処理される。フレーム化ＲＲＧＳではスケジューリングを完全なパイプラインを組んで処理することによって、高速なスケジューリングを実現している。
【００１０】
【発明が解決しようとする課題】
しかしながら、上述した従来の技術では、スケジューリング時間が入出力ポート数に比例するため、スケジューリングに使用しているラウンドロビン回路において、１出力ポートを選択するのに必要な処理時間が出力ポート数に正比例するので、交換システムの大容量化に伴い、入出力ポート数Ｎが増大すると、ラウンドロビン回路における処理時間が入出力ポート数Ｎに正比例して大きくなる。
【００１１】
また、入出力ポート数と同じスケジューリングをパイプライン処理しているため、一番初めのスケジューリング結果を送出するまでの時間が入出力ポート数Ｎに正比例するため、入出力ポート数Ｎが増大すると、一番初めのスケジューリング結果を送出するまでの時間が入出力ポート数Ｎに正比例して大きくなる。したがって、従来の技術ではスケジューリング処理に時間がかかるという問題がある。
【００１２】
さらに、フレーム化ＲＲＧＳアルゴリズムでは、入出力ポート数と同じスケジューリングをパイプライン処理する必要があるため、入出力ポート数Ｎが増大すると、Ｎスケジューリングをパイプライン処理することにつながり、さらに制御が複雑になるので、スケジューラ部の制御が複雑になるという問題がある。
【００１３】
そこで、本発明の目的は上記の問題点を解消し、スケジューラ部の制御を複雑化することなく、入出力ポート数の拡張やポート速度の向上にスケーラブルに対応することができるスケジューリング装置及びそれに用いるスケジューリング方法を提供することにある。
【００１４】
【課題を解決するための手段】
本発明によるスケジューリング装置は、入力バッファ型パケット交換システムにおいて、入力ポートからのデータに対するスケジューリングを行って当該データの宛先に対応する出力ポートに出力するスケジューラを含むスケジューリング装置であって、各々独立に前記スケジューリングを行いかつ前記スケジューラを分割してなる複数のサブスケジューラブロックと、前記スケジューリングの対象となる出力ポートが重複しないように前記複数のサブスケジューラブロック各々に割り当てる割り当て手段とを備えている。
【００１５】
本発明によるスケジューリング方法は、入力バッファ型パケット交換システムにおいて、スケジューラを用いて入力ポートからのデータに対するスケジューリングを行って当該データの宛先に対応する出力ポートに出力するスケジューリング方法であって、前記スケジューラを各々独立に前記スケジューリングを行う複数のサブスケジューラブロックに分割し、前記スケジューリングの対象となる出力ポートが重複しないように前記複数のサブスケジューラブロック各々に割り当てるようにしている。
【００１６】
すなわち、本発明のスケジューリング装置は、スケジューラ部を幾つかのサブスケジューラブロックに分割し、分割したサブスケジューラブロック毎に独立にスケジューリングを行っている。この時、単位スケジューリング時間で、スケジューリング対象となる出力ポートが重複しないように各サブスケジューラブロックに割り当てることで、各サブスケジューラブロックでは入出力ポートの組み合わせが競合することがなくなり、またスケジューリング時間の高速化を図ることが可能となる。よって、本発明のスケジューリング装置では入出力ポート数の拡張やポート速度の向上にスケーラブルで、高速なスケジューリングを実現することが可能となる。
【００１７】
より具体的に説明すると、本発明のスケジューリング装置では、Ｎ×Ｎ入力バッファ型パケット交換システム（Ｎは正の整数）において、スケジューラ部をＮ／Ｋ個（Ｋ＜Ｎ、ＫはＮの約数とする）のサブスケジューラブロックに分割し、入力バッファ部からのリクエスト信号をＮ／Ｋに分割して各サブスケジューラブロックに割り当てる。
【００１８】
各サブスケジューラブロックでは出力ポート時分割制御部の出力ポート分割信号に沿って、スケジューリング対象とする出力ポートＫを選択し、スケジューリングを行う。ここで、出力ポート分割信号は重複しないように全て異なる値をとるものとする。
【００１９】
上記のように、各サブスケジューラブロックで独立にスケジューリングを行うこと、またスケジューリング対象となる出力ポートをＫに減少させることの２点によって、高速なスケジューリングが可能となる。
【００２０】
【発明の実施の形態】
次に、本発明の一実施例について図面を参照して説明する。図１は本発明の一実施例によるパケット交換システムの構成を示すブロック図である。図１において、本発明の一実施例によるパケット交換システムはＮ×Ｎ入力バッファ型パケット交換システムであり、入力ポート＃１〜＃Ｎに対応した入力バッファ１−１〜１−Ｎと、スケジューラ部２と、Ｎ×Ｎクロスバスイッチ制御部３と、Ｎ×Ｎクロスバスイッチ部４とから構成されている。
【００２１】
入力バッファ１−１〜１−Ｎはデータの宛先となる出力ポート別のバッファ（図示せず）を有し、各バッファにパケットが蓄積された情報をスケジューラ部２に対してリクエスト信号（ＲＥＱ）１０−１〜１０−Ｎを送出する。
【００２２】
スケジューラ部２は受信したリクエスト信号１０−１〜１０−Ｎから入出力ポートの組み合わせが競合しないようにスケジューリングを行い、スケジューリング結果であるグラント信号（ＧＮＴ）２０−１〜２０−Ｎを入力バッファ１−１〜１−Ｎへ、セレクト信号（ＳＥＬ）３０−１〜３０−ＮをＮ×Ｎクロスバスイッチ制御部３に送出する。
【００２３】
この結果、データ＃１〜＃Ｎが入力バッファ１−１〜１−ＮからＮ×Ｎクロスバスイッチ部４に送出される。ここで、各グラント信号２０−１〜２０−Ｎは対応する入力ポート＃１〜＃Ｎに対してパケット送出宛先である出力ポート＃１〜＃Ｎを示し、各セレクト信号３０−１〜３０−Ｎは対応する出力ポート＃１〜＃Ｎに対してパケット送出元である入力ポート＃１〜＃Ｎを示す。
【００２４】
図２は図１のスケジューラ部２の詳細な構成を示すブロック図である。図２において、スケジューラ部２はＮ／Ｋ個（Ｋ＜Ｎ、ＫはＮの約数とする）のサブスケジューラブロック（ＳＢ）２１−１〜２１−Ｎ／Ｋと、出力ポート時分割制御部２２と、セレクト信号生成部２３とから構成されている。
【００２５】
各サブスケジューラブロック２１−１〜２１−Ｎ／ＫはそれぞれＫ個の入力バッファ１−１〜１−Ｋ，１−Ｋ＋１〜１−２Ｋ，・・・，１−（Ｎ／Ｋ−１）×Ｋ＋１〜１−Ｎに対応する。各サブスケジューラブロック２１−１〜２１−Ｎ／Ｋは出力ポート時分割制御部２２の出力ポート分割信号（ＤＩＶ）４０−１〜４０−Ｎ／Ｋによってスケジューリング対象とする出力ポート＃Ｋを選択する機能を有し、選択した出力ポート＃Ｋを対象にスケジューリングを行う。
【００２６】
各サブスケジューラブロック２１−１〜２１−Ｎ／Ｋはスケジューリング結果であるグラント信号２０−１〜２０−Ｎを対応する入力バッファ１−１〜１−Ｎ及びセレクト信号生成部２３に送出する。
【００２７】
セレクト信号生成部２３は各サブスケジューラブロック２１−１〜２１−Ｎ／Ｋからのグラント信号２０−１〜２０−Ｎと、出力ポート時分割制御部２２からの出力ポート分割信号４０−１〜４０−Ｎ／Ｋとを基に信号のフォーマット変換を行い、セレクト信号３０−１〜３０−Ｎを生成する。
【００２８】
図３は図２のサブスケジューラブロック２１−１の詳細な構成を示すブロック図である。図３において、サブスケジューラブロック２１−１はリクエスト信号１０−１〜１０−Ｎにそれぞれ対応するキューテーブル（ＱＴ）３１−１−１〜３１−Ｋ−１と、ラウンドロビン回路（ＲＲ）３２−１−１〜３２−Ｋ−１と、ＧＮＴ生成部３３−１−１〜３３−Ｋ−１と、ラウンドロビン制御部３４−１とから構成されている。
【００２９】
以下、リクエスト信号１０−１に対応するキューテーブル３１−１−１、ラウンドロビン回路３２−１−１、ＧＮＴ生成部３３−１−１の動作について説明する。キューテーブル３１−１−１はクラス別、出力ポートＮ別のテーブル（図示せず）を有し、リクエスト信号１０−１の情報に基づいて該当するテーブルにキューをスタックし、各テーブルにキューが１つでも存在する場合、ラウンドロビン回路３２−１−１にキュー信号（ＱＳ）１０１−１〜１０１−Ｋを送出する。この時、キュー信号１０１−１〜１０１−Ｋは出力ポート分割信号４０−１の値に基づいて出力ポート＃１〜＃Ｎの中から選択された出力ポート＃Ｋに対するものである。
【００３０】
キュー信号１０１−１〜１０１−Ｋを受信したラウンドロビン回路３２−１−１はキュー信号１０１−１〜１０１−Ｋを対象にラウンドロビン回路を用いてスケジューリングを行い、リザルト信号（ＲＥＳ）２０１−１〜２０１−Ｋをキューテーブル３１−１−１及びＧＮＴ生成部３３−１−１に送出する。
【００３１】
キューテーブル３１−１−１は受信したリザルト信号２０１−１〜２０１−Ｋに該当するキューテーブルのキューを削除し、ＧＮＴ生成部３３−１−１はグラント信号２０−１を生成する。
【００３２】
次に、ラウンドロビンの構造について説明する。ラウンドロビン回路３２−１−１〜３２−Ｋ−１はリング構造をとっており、ラウンドロビン制御部３４−１のスタート信号５００に沿って新たなスケジューリングを開始する。
【００３３】
すなわち、ラウンドロビン回路３２−１−１はキュー信号１０１−１〜１０１−Ｋから１つの出力ポートを選択する。ラウンドロビン回路３２−１−１は選択した出力ポートの情報であるマスク信号（ＭＳＫ）３０１−１〜３０１−Ｋを次段のラウンドロビン回路３２−２−１に送出する。
【００３４】
ラウンドロビン回路３２−２−１ではキュー信号１０２−１〜１０２−Ｋからマスク信号３０１−１〜３０１−Ｋによって既に選択された出力ポート以外の出力ポートを対象にして１つの出力ポートを選択する。ラウンドロビン回路３２−２−１はマスク信号３０１−１〜３０１−Ｋに選択した出力ポート情報を加えたマスク信号３０２−１〜３０２−Ｋを次段のラウンドロビン回路３２−３−１に送出する。
【００３５】
以上のような一連の処理をラウンドロビン回路３２−Ｋ−１まで繰り返して行うことで、ラウンドロビン回路３２−１−１〜３２−Ｋ−１によるスケジューリング処理が終了となる。
【００３６】
本実施例はＮ×Ｎ入力バッファ型パケット交換システムにおけるスケジューリング方法であるパイプライン・スケジューリング方法に関するものである。パイプライン・スケジューリング方法には、特開２０００−１７４８１７号公報に開示されたＲＲＧＳ（Ｒｏｕｎｄ  Ｒｏｂｉｎ  Ｇｒｅｅｄｙ  Ｓｃｈｅｄｕｌｉｎｇ）アルゴリズムがある。このＲＲＧＳアルゴリズムでは入力ポート＃１〜＃Ｎに対応したＮ個のスケジューラを有し、各スケジューラがスケジューリング結果を順次次のスケジューラに渡していく。この時、前のスケジューラで既に決定された出力ポートはスケジューリング対象からはずされる。
【００３７】
ＲＲＧＳアルゴリズムではパイプライン処理を行うことによって、複数のスケジューリングをタイミングをずらして開始し、Ｎタイムスロットだけ未来のタイムスロットが決定される。このパイプライン処理によって高速なスケジューリングが可能である。
【００３８】
また、上記のＲＲＧＳアルゴリズムの変形としてフレーム化ＲＲＧＳアルゴリズムがある。フレーム化ＲＲＧＳアルゴリズムは複数のスケジューリングを同時に開始し、同時に終了させるという点で上記のＲＲＧＳアルゴリズムとは異なる。本実施例のスケジューリングては上記のフレーム化ＲＲＧＳアルゴリズムを用いて行う。
【００３９】
図４は本発明の一実施例によるパケット交換システムの動作を示すタイムチャートである。これら図１〜図４を参照して本発明の一実施例によるパケット交換システムの動作について説明する。以下、本実施例によるパケット交換システムが８×８入力バッファ型パケット交換システム（Ｎ＝８）で、スケジューラ部２を２個のサブスケジューラブロック２１−１，２１−２に分割する場合（Ｋ＝４）について説明する。
【００４０】
図４は８×８入力バッファ型パケット交換システムにおけるサブスケジューラブロック２１−１，２１−２での動作を示し、図４に示すｔ時間が各ラウンドロビン回路３２−１−１〜３２−４−１，３２−１−２〜３２−４−２においてキュー信号１０１−１〜１０１−４から１つの出力ポートを選択するのに要する時間を表し、スケジューラ部２はこのｔ時間を基準に動作するものとする。
【００４１】
また、出力ポート分割信号４０−１〜４０−２の値は対応する出力ポートを表し、本実施例では‘０’→出力ポート＃１〜＃４、‘１’→出力ポート＃５〜＃８に対応するものとする。
【００４２】
さらに、各リザルト信号２０１−１〜２０１−４，２０２−１〜２０２−４，２０３−１〜２０３−４，２０４−１〜２０４−４，２０５−１〜２０５−４，２０６−１〜２０６−４，２０７−１〜２０７−４，２０８−１〜２０８−４に示した値は、図中に示したｔ時間（ｔ５→ｔ＝５を示す）にグラント信号２０−１〜２０−４，２０−５〜２０−８として送出する出力ポートを選択することを表している。
【００４３】
図３及び図４を用いてサブスケジューラブロック２１−１の動作について説明する。入力バッファ１−１からｔ＝１時間にリクエスト信号１０−１を受信したキューテーブル３１−１−１は該当するキューテーブルにキューをスタックする。次に、キューテーブル３１−１−１は出力ポート分割信号４０−１＝‘０’から、出力ポート＃１〜＃４に該当するキューテーブルにキューが存在する場合に‘１’として、存在しない場合に‘０’としてキュー信号１０１−１〜１０１−４をラウンドロビン回路３２−１−１に送出する。
【００４４】
ラウンドロビン回路３２−１−１はキュー信号１０１−１〜１０１−４から、次回選択した出力ポートが最低優先となるようなラウンドロビン回路を用いて１つの出力ポートを選択する。その結果、ラウンドロビン回路３２−１−１はリザルト信号２０１−１〜２０１−４のうちの選択した出力ポートに該当するものを‘１’、それ以外のものを‘０’としてキューテーブル３１−１−１とＧＮＴ生成部３３−１−１とに送出する。
【００４５】
また、ラウンドロビン回路３２−１−１はリザルト信号２０１−１〜２０１−４と同様の信号をマスク信号３０１−１〜３０１−４としてラウンドロビン回路３２−２−１に送出する。リザルト信号２０１−１〜２０１−４を受信したキューテーブル３１−１−１は選択された出力ポートに該当するキューテーブルのスタックを削除し、ＧＮＴ生成部３３−１−１はｔ＝５時間に送出するグラント信号２０−１を生成する。但し、グラント信号２０−１が送出されるのはｔ＝５時間であり、生成されたグラント信号２０−１は内部で保持されるものとする。
【００４６】
その他のキューテーブル３１−２−１〜３１−４−１、ラウンドロビン回路３２−２−１〜３２−４−１、ＧＮＴ生成部３３−２−１〜３３−４−１においても上記と同様の動作を行う。
【００４７】
次に、ｔ＝２時間にリクエスト信号１０−１を受信したキューテーブル３１−１−１は、上記のｔ＝１時間と同様の動作を繰り返し、キュー信号１０１−１〜１０１−４をラウンドロビン回路３２−１−１に送出する。
【００４８】
ラウンドロビン回路３２−１−１はキューテーブル３１−１−１からキュー信号１０１−１〜１０１−４、ラウンドロビン回路３２−１−４からマスク信号３０４−１〜３０４−４をそれぞれ受信し、マスク信号３０４−１〜３０４−４から既にラウンドロビン回路３２−４−１で選択された出力ポート以外の出力ポートを対象として１つの出力ポートを選択し、リザルト信号２０１−１〜２０１−４を送出する。ここで、マスク信号３０１−１〜３０１−４はマスク信号３０４−１〜３０４−４に自身で選択した出力ポートの情報を加えたものとし、ラウンドロビン回路３２−２−１に送出する。
【００４９】
リザルト信号２０１−１〜２０１−４を受信したキューテーブル３１−１−１、ＧＮＴ生成部３３−１−１の動作は上記のｔ＝１の時と同様である。但し、図４から、ｔ＝２時間にＧＮＴ生成部３３−１−１で生成されるＧＮＴ２０−１が送出されるのはｔ＝８時間である。
【００５０】
以上の動作をｔ＝４時間まで繰り返し行うことで、サブスケジューラブロック２１−１によるスケジューリングが終了となる。また、サブスケジューラブロック２１−２の動作も、上記のサブスケジューラブロック２１−１の動作と同様である。
【００５１】
次に、ｔ＝５時間でＳＴＡＲＴ信号５００の立上りを検出し、新たなスケジューリングを開始する。ｔ＝５時間では出力ポート分割信号４０−１＝‘１’から、キューテーブル３１−１−１は出力ポート＃５〜＃８に該当するキューテーブルを参照し、キュー信号１０１−１〜１０１−４を送出する。また、ラウンドロビン回路３２−１−１ではラウンドロビン回路３２−４−１からのマスク信号３０４−１〜３０４−４を無視して新たなスケジューリングを開始する。
【００５２】
キューテーブル３１−１−１及びラウンドロビン回路３２−１−１の動作に関しては、上述したｔ＝１時間の場合と同様である。ＧＮＴ生成部３３−１−１は、上述したｔ＝１時間の場合と同様に、ｔ＝９時間に送出するグラント信号２０−１を生成するとともに、ｔ＝１時間の場合に生成し、保持していたｔ＝５時間に送出するグラント信号２０−１を入力バッファ１−１及びセレクト信号生成部２３に送出する。
【００５３】
ｔ＝６時間以後の各ブロックの動作に関しては、上述したｔ＝２〜ｔ＝４時間の場合の動作を繰り返すものとする。
【００５４】
次に、図３及び図４を用いてサブスケジューラブロック２１−２の動作について説明する。図４に示すように、サブスケジューラブロック２１−２では参照している出力ポート分割信号４０−２の信号値が出力ポート分割信号４０−１の反転の値を取るため、ｔ＝１〜４時間にスケジューリング対象となるのは出力ポート＃５〜＃８であり、ｔ＝５〜８時間では出力ポート＃１〜＃４となる。
【００５５】
各キューテーブル３１−１−２〜３１−４−２、ラウンドロビン回路３２−１−２〜３２−４−２、ＧＮＴ生成部３３−１−２〜３３−４−２の動作に関しては、上述したサブスケジューラブロック２１−１の動作と同様である。
【００５６】
このように、スケジューラ部２を幾つかのサブスケジューラブロック２１−１〜２１−Ｎ／Ｋに分割し、分割したサブスケジューラブロック２１−１〜２１−Ｎ／Ｋ毎に独立にスケジューリングを行う。その際、各サブスケジューラブロック２１−１〜２１−Ｎ／Ｋでのスケジューリング結果が競合しないように、スケジューリング対象とする出力ポートをサブスケジューラブロック２１−１〜２１−Ｎ／Ｋに分散する必要があり、これによって、スケジューリング対象となる出力ポート数が減少することで更なるスケジューリング時間の短縮を図ることができる。
【００５７】
また、分割するサブスケジューラブロック２１−１〜２１−Ｎ／Ｋの数を多くすることでもスケジューリング時間の短縮を図ることができる。よって、高速なスケジューリングを行うことができ、入出力ポート数の拡張やポート速度の向上にスケーラブルに対応することができる。
【００５８】
さらに、サブスケジューラブロック２１−１〜２１−Ｎ／Ｋが独立にスケジューリングを行うことから、各サブスケジューラブロック２１−１〜２１−Ｎ／Ｋ間での制御が不要となり、またサブスケジューラブロック２１−１〜２１−Ｎ／Ｋ各々の規模も小さいことから、複雑な制御が不要となる。よって、スケジューラ部２の制御が容易となる。
【００５９】
尚、本発明の一実施例では８×８入力バッファ型パケット交換システムを例にとってスケジューラ部２を２つのサブスケジューラブロック２１−１，２１−２に分割する場合について述べたが、スケジューラ部２を幾つに分割するかはシステムの特性に依存するものであり、分割数に制限はない。
【００６０】
次に、本発明の他の実施例として、図２に示す出力ポート時分割制御部２２を外部から制御する例について説明する。尚、本発明の他の実施例では出力ポート時分割制御部２２を外部から制御するようにすること以外は、つまり図示していないが、その構成や動作は本発明の一実施例と同様である。
【００６１】
上述した本発明の一実施例ではスケジューラ部２を２つのサブスケジューラブロック２１−１，２１−２に分割する場合について、出力ポート時分割制御部２２の出力ポート分割信号４０−１，４０−２に対応する出力ポートを‘０’→出力ポート＃１〜＃４、‘１’→出力ポート＃５〜＃８と一意的に定義している。また、図４に示すように、出力ポート分割信号値の変化も出力ポート分割信号４０−１，４０−２が機械的に変化するように定義している。
【００６２】
これらの定義によって、各入出力ポート間の公平性が確保され、出力ポート時分割制御部２２の制御も不要であるという利点がある。しかしながら、トラフィックが特定の入出力ポートに集中した場合、該当する出力ポートがスケジューリング対象外であった場合には、当然、その出力ポートが選択されることはなく、キューテーブルのキューがオーバフローすることが考えられる。すなわち、入力バッファ１−１〜１−Ｎがオーバフローすることが考えられる。
【００６３】
本発明の他の実施例ではトラフィックが特定の入出力ポートに集中した場合、出力ポート時分割制御部２２を外部から制御することで、出力ポート分割信号の値を任意に変更することが可能なため、該当する出力ポートがスケジューリング対象となる割合を任意に変更することが可能となる。この他にも、出力ポート分割信号の値に対応する出力ポートを一意的ではなく任意に設定することも可能である。
【００６４】
本実施例では、出力ポート時分割制御部２２に対して外部からの制御を加えることで、トラフィックの増減に柔軟に対応することができるスケジューリングが可能であるという新たな効果を奏する。
【００６５】
【発明の効果】
以上説明したように本発明によれば、入力ポートからのデータに対するスケジューリングを行って当該データの宛先に対応する出力ポートに出力するスケジューラを含むスケジューリング装置において、スケジューラを各々独立にスケジューリングを行う複数のサブスケジューラブロックに分割し、スケジューリングの対象となる出力ポートが重複しないように複数のサブスケジューラブロック各々に割り当てることによって、スケジューラ部の制御を複雑化することなく、入出力ポート数の拡張やポート速度の向上にスケーラブルに対応することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例によるパケット交換システムの構成を示すブロック図である。
【図２】図１のスケジューラ部の詳細な構成を示すブロック図である。
【図３】図２のサブスケジューラブロックの詳細な構成を示すブロック図である。
【図４】本発明の一実施例によるパケット交換システムの動作を示すタイムチャートである。
【図５】従来の８×８入力バッファ型パケット交換システムにおけるスケジューラ部の構成を示すブロック図である。
【図６】図５のスケジューラ部におけるスケジューリング動作を示すタイムチャートである。
【符号の説明】
１−１〜１−Ｎ  入力バッファ
２  スケジューラ部
３  Ｎ×Ｎクロスバスイッチ制御部
４  Ｎ×Ｎクロスバスイッチ部
１０−１〜１０−Ｎ  リクエスト信号
２０−１〜２０−Ｎ  グラント信号
２１−１〜２１−Ｎ／Ｋ  サブスケジューラブロック
２２  出力ポート時分割制御部
２３  セレクト信号生成部
３０−１〜３０−Ｎ  セレクト信号
３１−１−１〜３１−Ｋ−１  キューテーブル
３２−１−１〜３２−Ｋ−１  ラウンドロビン回路
３３−１−１〜３３−Ｋ−１  ＧＮＴ生成部
３４−１  ラウンドロビン制御部
４０−１〜４０−Ｎ  出力ポート分割信号
１０１−１〜１０Ｋ−Ｋ  キュー信号
２０１−１〜２０Ｋ−Ｋ  リザルト信号
３０１−１〜３０Ｋ−Ｋ  マスク信号
５００  スタート信号
【図１】
0003586660.tif 000002
【図２】
0003586660.tif 000003
【図３】
0003586660.tif 000004
【図４】
0003586660.tif 000005
【図５】
0003586660.tif 000006
【図６】
0003586660.tif 000007