(57)【特許請求の範囲】
【請求項１】
Ｍ個（Ｍ：自然数）の入力ポートとＮ個（Ｎ：自然数）の出力ポートとを持つクロスポイントスイッチのポート接続の割り当てを行うスケジューラを複数個用い、前記複数のスケジューラ各々に複数のサービスクラスをそれぞれ割り当て、前記複数のサービスクラス間の優先順位を考慮したポート接続割り当てを行うスケジューリング回路であって、
自回路よりも高優先クラスを扱うスケジューラでのポート割当結果と外部から受信した接続割当要求とに基づいてポート接続割り当てを行う手段を前記複数のスケジューラ各々に有し、
前記ポート接続割り当てを行う手段は、前記自回路よりも高優先クラスを扱うスケジューラでのポート割当結果と重複が起こらないような接続割り当てを行うように構成したことを特徴とするスケジューリング回路。
【請求項２】
前記自回路よりも高優先クラスを扱うスケジューラでのポート割当結果に基づいて前記外部から受信した接続割当要求に対してマスク処理を行う手段を前記複数のスケジューラ各々に含むことを特徴とする請求項１記載のスケジューリング回路。
【請求項３】
前記ポート接続割り当てを行う手段の接続割当結果を低優先クラスを扱うスケジューラへ通知する手段を含むことを特徴とする請求項１または請求項２記載のスケジューリング回路。
【請求項４】
前記接続割当結果は、少なくとも使用済み状態となっている入力ポート及び出力ポートの情報からなることを特徴とする請求項１から請求項３のいずれか記載のスケジューリング回路。
【請求項５】
前記接続割当結果は、少なくとも未使用状態となっている入力ポート及び出力ポートの情報からなることを特徴とする請求項１から請求項３のいずれか記載のスケジューリング回路。
【請求項６】
前記接続割当結果は、接続割り当てが行われた入力ポート及び出力ポートの組合せを示すＭ×Ｎマトリックスからなることを特徴とする請求項１から請求項５のいずれか記載のスケジューリング回路。
【請求項７】
Ｍ個（Ｍ：自然数）の入力ポートとＮ個（Ｎ：自然数）の出力ポートとを持つクロスポイントスイッチのポート接続の割り当てを行うスケジューラを複数個用い、前記複数のスケジューラ各々に複数のサービスクラスをそれぞれ割り当て、前記複数のサービスクラス間の優先順位を考慮したポート接続割り当てを行うスケジューリング回路のスケジューリング方式であって、
前記複数のスケジューラ各々において、自回路よりも高優先クラスを扱うスケジューラにおける接続割当結果と重複が起こらないような接続割り当てを、優先度の高いサービスクラスを扱うスケジューラから優先度の低いサービスクラスを扱うスケジューラへと順に行うようにしたことを特徴とするスケジューリング方式。
【請求項８】
前記複数のスケジューラ各々において、前記自回路よりも高優先クラスを扱うスケジューラでのポート割当結果に基づいて前記外部から受信した接続割当要求に対してマスク処理を行うようにしたことを特徴とする請求項７記載のスケジューリング方式。
【請求項９】
前記複数のスケジューラ各々において、自回路の接続割当結果を自回路よりも低優先クラスを扱うスケジューラへ通知するようにしたことを特徴とする請求項７または請求項８記載のスケジューリング方式。
【請求項１０】
前記接続割当結果は、少なくとも使用済み状態となっている入力ポート及び出力ポートの情報からなることを特徴とする請求項７から請求項９のいずれか記載のスケジューリング方式。
【請求項１１】
前記接続割当結果は、少なくとも未使用状態となっている入力ポート及び出力ポートの情報からなることを特徴とする請求項７から請求項９のいずれか記載のスケジューリング方式。
【請求項１２】
前記接続割当結果は、接続割り当てが行われた入力ポート及び出力ポートの組合せを示すＭ×Ｎマトリックスからなることを特徴とする請求項７から請求項１１のいずれか記載のスケジューリング方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はスケジューリング回路及びそれに用いるスケジューリング方式に関し、特に同一ポート内の複数サービスクラス間に優先順位をつけてスケジューリングを行うスケジューリング方式に関する。
【０００２】
【従来の技術】
従来、この種のスケジューリング方式としては、Ｍ×Ｎスケジューラを複数個用い、同一ポート内の複数サービスクラス間に優先順位をつけてスケジューリングを行うという方法がある。この方法については、特開平９−３２６８２８号公報に開示されている。
【０００３】
上記の方法を用いたスケジューリング回路の構成を図８に示す。図８において、このスケジューリング回路は優先度の異なるｋ種類のサービスクラスの接続割当要求を、優先度の高いサービスクラスから順にＭ×Ｎスケジューラ５１，５２，・・・，５ｋに入力してスケジューリングを行っている。
【０００４】
Ｍ×Ｎスケジューラ５１，５２，・・・，５ｋはそれぞれ独立に接続割り当てを行い、接続割当結果Ｓ５２１，Ｓ５２２，・・・，Ｓ５２ｋを出力する。各Ｍ×Ｎスケジューラ５１，５２，・・・，５ｋは独立にスケジューリング動作を行うため、出力された接続割当結果Ｓ５２１，Ｓ５２２，・・・，Ｓ５２ｋの間で、ある一つの入力ポートまたは出力ポートに対して二つ以上のスケジューラにおいて接続割り当てが行われていることがありうる。
【０００５】
しかしながら、実際に接続を行う場合、任意の一つの入力ポートまたは出力ポートに注目した際、二つ以上の接続割り当てがあってはならない。したがって、出力された接続割当結果Ｓ５２１，Ｓ５２２，・・・，Ｓ５２ｋの間で調停を行う割当結果調停回路６０が必要となる。
【０００６】
【発明が解決しようとする課題】
上述した従来のスケジューリング方式では、ｋ＝３の場合、Ｍ×Ｎスケジューラ５１，５２，５３による各サービスクラス毎の接続割当結果が図９の上段に示すようになったとする。
【０００７】
この場合、割当結果調停回路６０によって調停を行うと、例えば優先度の高いサービスクラスの割当結果から順番に採用していくとすると、調停した結果は図９の下段に示すようになる。調停結果のマトリックス内で、実線の丸印は実際に割り当てられた接続、破線の丸印は調停によって失われた接続である。丸印内の数字は優先度を表す。
【０００８】
調停結果を見ると、Ｍ×Ｎスケジューラ５１，５２，５３によって接続割り当てがなされたにもかかわらず、割当結果調停回路６０の調停作業によって失われる接続がある。
【０００９】
予め高優先側のサービスクラスの割り当て状況が分かっていれば、別の接続割り当てが可能となる場合がある。このような割り当てが可能な場合、従来の方式では転送効率が低下する。例えば、予め高優先側のサービスクラスの割り当て状況が分かっていれば、図９の星印で示すように接続を割り当てることも可能であり、調停作業により失われる接続は存在せず、転送効率の低下は発生しない。
【００１０】
上記のような問題は、複数のＭ×Ｎスケジューラにおいてスケジューリングを行う際に、ポート割当結果をスケジューラ間で共有していないことによって発生する。
【００１１】
そこで、本発明の目的は上記の問題点を解消し、効率的な無駄の少ない接続割り当てを行うことができるスケジューリング回路及びそれに用いるスケジューリング方式を提供することにある。
【００１２】
【課題を解決するための手段】
本発明によるスケジューリング回路は、Ｍ個（Ｍ：自然数）の入力ポートとＮ個（Ｎ：自然数）の出力ポートとを持つクロスポイントスイッチのポート接続の割り当てを行うスケジューラを複数個用い、前記複数のスケジューラ各々に複数のサービスクラスをそれぞれ割り当て、前記複数のサービスクラス間の優先順位を考慮したポート接続割り当てを行うスケジューリング回路であって、
自回路よりも高優先クラスを扱うスケジューラでのポート割当結果と外部から受信した接続割当要求とに基づいてポート接続割り当てを行う手段を前記複数のスケジューラ各々に有し、
前記ポート接続割り当てを行う手段は、前記自回路よりも高優先クラスを扱うスケジューラでのポート割当結果と重複が起こらないような接続割り当てを行うように構成している。
【００１３】
本発明によるスケジューリング方式は、Ｍ個（Ｍ：自然数）の入力ポートとＮ個（Ｎ：自然数）の出力ポートとを持つクロスポイントスイッチのポート接続の割り当てを行うスケジューラを複数個用い、前記複数のスケジューラ各々に複数のサービスクラスをそれぞれ割り当て、前記複数のサービスクラス間の優先順位を考慮したポート接続割り当てを行うスケジューリング回路のスケジューリング方式であって、前記複数のスケジューラ各々において、自回路よりも高優先クラスを扱うスケジューラにおける接続割当結果と重複が起こらないような接続割り当てを、優先度の高いサービスクラスを扱うスケジューラから優先度の低いサービスクラスを扱うスケジューラへと順に行うようにしている。
【００１４】
すなわち、本発明のスケジューリング方式は、Ｍ個（Ｍ：自然数）の入力ポートとＮ個（Ｎ：自然数）の出力ポートとを持つクロスポイントスイッチのポート接続の割り当てを行うスケジューラを複数個用い、個々のスケジューラに複数サービスクラスをそれぞれ割り当て、複数のサービスクラス間の優先順位を考慮したポート接続割り当てを行うスケジューラにおいて、高優先クラスを扱うスケジューラでのポート割当結果を低優先クラスを扱うスケジューラへ伝達するようにしている。
【００１５】
これによって、調停作業によって失われる接続が存在せず、転送効率の低下を発生させることがなくなるので、効率的な無駄の少ない接続割り当てを行うことが可能となる。また、接続割当結果についてポートの重複が入力ポート及び出力ポートともに発生しないため、割当結果調停回路が不用となる。
【００１６】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。図１は本発明の第１の実施の形態によるスケジューラの構成を示すブロック図である。図１において、スケジューラ１０は割当結果受信回路１１と、割当要求マスク回路１２と、Ｍ×Ｎスケジューラ回路１３と、割当結果送信回路１４とから構成されている。
【００１７】
割当結果受信回路１１は外部から累積割当結果Ｓ１１を受信し、割り当て済み入力ポート・出力ポート情報を割当要求マスク回路１２へ出力する。割当要求マスク回路１２は割当結果受信回路１１から受信した割り当て済み入力ポート・出力ポート情報を用いて、外部から受信した接続割当要求Ｒ１１に対してマスク処理を行い、その結果をＭ×Ｎスケジューラ回路１３へ出力する。
【００１８】
Ｍ×Ｎスケジューラ回路１３は割当要求マスク回路１２から受信した情報を基づいてポート接続の割り当てを決定し、接続割当結果を外部（Ｇ１１）及び割当結果送信回路１４へ送信する。割当結果送信回路１４はＭ×Ｎスケジューラ回路１３から受信した接続割当結果と外部から受信した累積割当結果Ｓ１１との論理和をとって外部へ送信する。
【００１９】
図２は本発明の本発明の第１の実施の形態によるスケジューリング回路の構成を示すブロック図である。図２において、本発明の第１の実施の形態によるスケジューリング回路はｋ個（ｋ：自然数）のスケジューラ２１，２２，２３，・・・，２ｋから構成されている。
【００２０】
スケジューラ２１は累積割当結果（Ｓ２１）をスケジューラ２２へ送信する。スケジューラ２２は累積割当結果（Ｓ２２）をスケジューラ２３へ送信する。これを一般化すると、スケジューラ２ｉ（ｉ＝１〜ｋ−１の整数）は、累積割当結果（Ｓ２ｉ）をスケジューラ２（ｉ＋１）へ送信する。尚、スケジューラ２１，２２，２３，・・・，２ｋはそれぞれ図１に示すスケジューラ１０と同様の構成となっており、その動作も同様である。
【００２１】
上記の各スケジューラ２１，２２，２３，・・・，２ｋの内部動作を、図１を参照して説明する。
【００２２】
割当結果受信回路１１は外部から受信した累積割当結果Ｓ１１に基づいて、既に使用済み状態となっている入力ポート及び出力ポート（以下、使用済み状態となっている入力ポート及び出力ポートをまとめて使用済みポート情報とする）を計算し、使用済みポート情報を割当要求マスク回路１２へ送信する。
【００２３】
割当要求マスク回路１２は割当結果受信回路１１から受信した使用済みポート情報に基づき、スケジューラ１０の外部から入力された接続割当要求（Ｒ１１）のうちの既に使用済みのポートの接続割当要求を無効にする。
【００２４】
具体的に、入力ポートｓ（ｓは１〜Ｍの整数）が既に使用済みであった場合には、入力ポートｓに関係する接続割当要求を全て無効にする。また、出力ポートｄ（ｄは１〜Ｎの整数）が既に使用済みであった場合には、出力ポートｄに関係する接続割当要求を全て無効にする。割当要求マスク回路１２は上記の操作を全ての入力ポート・出力ポートについて行い、上記の操作によって更新された接続割当要求をＭ×Ｎスケジューラ回路１３へ送信する。
【００２５】
Ｍ×Ｎスケジューラ回路１３は割当要求マスク回路１２から受信した情報に基づいてＭ個の入力ポートとＮ個の出力ポートとの間のスケジューリングを行う。スケジューリングには任意のアルゴリズムを採用することが可能である。
【００２６】
Ｍ×Ｎスケジューラ回路１３は上記のスケジューリング操作によって得られた接続割当結果を接続結果送信回路１４へ送信し、また接続割当結果をスケジューラ１０の外部へ送出する（Ｇ１１）。
【００２７】
割当結果送信回路１４はスケジューラ１０の外部から入力された累積割当結果Ｓ１１にＭ×Ｎスケジューラ回路１３から受信した接続割当結果を加え、得られた結果を外部へ送出する（Ｓ１２）。
【００２８】
隣接するスケジューラ間で通信する累積割当結果としてはＭ×Ｎのマトリックスを利用し、接続割当が行われた入力ポートと出力ポートの組を送信する方法と、既に割当済みの入力ポート及び出力ポートの情報を送信する方法との二つが考えられる。後者の類似の方法としては、未使用の入力ポート及び出力ポートの情報を送信する方法がある。
【００２９】
本発明の第１の実施の形態によるスケジューリング回路、つまりスケジューラ２１，２２，２３，・・・，２ｋの動作を図２を参照して説明する。
【００３０】
本発明の第１の実施の形態によるスケジューリング方式はＭ個の入力ポートとＮ個の出力ポートとの間の接続割り当てを決定する。同一ポート内には複数（以下、ｋ個）のサービスクラスのトラヒックが収容されており、接続割り当ては優先度の高いサービスクラスから順に行うものである。
【００３１】
接続割当要求はサービスクラス毎のマトリックスの形でスケジューラ２１，２２，２３，・・・，２ｋに入力される。接続割当要求マトリックスはＭ行×Ｎ列で構成され、Ｍは入力ポート数、Ｎは出力ポート数に等しい。上記のマトリックスはサービスクラス毎に用意され、対応するサービスクラスに属する接続要求を表す。
【００３２】
最も優先度の高いサービスクラスの接続割当要求（Ｒ２１）はスケジューラ２１に、二番目に優先度の高いサービスクラスの接続割当要求（Ｒ２２）はスケジューラ２２に、以下同様に、接続割当要求はサービスクラスに対応するスケジューラに入力され、最も優先度の低いサービスクラスの接続割当要求（Ｒ２ｋ）はスケジューラ２ｋに入力される。
【００３３】
各スケジューラ２１，２２，２３，・・・，２ｋは接続割当要求及び隣接する優先度の高いサービスクラスを扱うスケジューラから累積割当結果を受信し、既に接続割り当て済みの入力ポート及び出力ポートを使用しないような接続割り当てを行い、その接続割当結果を出力する。
【００３４】
また同時に、各スケジューラ２１，２２，２３，・・・，２ｋは累積割当結果に、新たに得られた接続割当結果を反映させ、隣接する優先度の低いサービスクラスを扱うスケジューラへ更新された累積割当結果を送信する。
【００３５】
スケジューラ２１へ入力される累積割当結果（Ｓ２０）として、全く接続割り当てがなされていない、すなわち全てのポートが選択可能であるという情報を入力する。
【００３６】
スケジューラ２１は接続割当要求（Ｒ２１）と累積割当結果（Ｓ２０）とに基づいてスケジューリングを行い、接続割当結果を送出し（Ｇ２１）、同時にスケジューラ２２へ累積割当結果（Ｓ２１）を送信する。
【００３７】
スケジューラ２１は最も優先度の高いスケジューリングを行うため、スケジューラ２２へ送信される累積割当結果（Ｓ２１）は接続割当結果（Ｇ２１）と全く同じである。
【００３８】
スケジューラ２２は接続割当要求（Ｒ２２）及びスケジューラ２１からの累積割当結果（Ｓ２１）を受信する。スケジューラ２２は累積割当結果（Ｓ２１）に基づき、接続割当要求（Ｒ２２）のうちのスケジューラ２１で既に接続割り当ての行われた入力ポート・出力ポートに関係する割当要求を無効とし、更新された接続割当要求に基づいてスケジューリングを行い、接続割当結果を送出する（Ｇ２２）。
【００３９】
同時に、スケジューラ２２はスケジューラ２３へスケジューラ２２までの累積割当結果（Ｓ２２）を送信する。累積割当結果（Ｓ２２）はスケジューラ２１及びスケジューラ２２において決定された接続割当結果の合計である。
【００４０】
スケジューラ２３は接続割当要求（Ｒ２３）及びスケジューラ２２からの累積割当結果（Ｓ２２）を受信する。スケジューラ２３は累積割当結果（Ｓ２２）に基づき、接続割当要求（Ｒ２３）のうちのスケジューラ２１及びスケジューラ２２で既に接続割り当ての行われた入力ポート・出力ポートに関係する割当要求を無効とし、更新された接続割当要求に基づいてスケジューリングを行い、接続割当結果を送出する（Ｇ２３）。
【００４１】
同時に、スケジューラ２３はスケジューラ２４へ累積割当結果を送信する（Ｓ２３）。累積割当結果（Ｓ２３）はスケジューラ２１とスケジューラ２２とスケジューラ２３とにおいて決定された接続割当結果の合計である。
【００４２】
以下、スケジューラ２（ｋ−１）まで、上記と同様の動作が行われる。スケジューラ２ｋは接続割当要求（Ｒ２ｋ）及びスケジューラ２（ｋ−１）からの累積割当結果［Ｓ２（ｋ−１）］を受信する。
【００４３】
スケジューラ２ｋは累積割当結果［Ｓ２（ｋ−１）］に基づき、接続割当要求（Ｒ２ｋ）のうちのスケジューラ２ｋよりも優先度の高いサービスクラスを扱うスケジューラで既に接続割り当ての行われた入力ポート・出力ポートに関係する割当要求を無効とし、更新された接続割当要求に基づいてスケジューリングを行い、接続割当結果を送出する（Ｇ２ｋ）。
【００４４】
同時に、スケジューラ２ｋは累積割当結果を送出する（Ｓ２ｋ）。累積割当結果（Ｓ２ｋ）はスケジューラ２１，２２，２３，・・・，２ｋにおいて決定された接続割当結果の合計である。
【００４５】
上記の動作によって、接続割当結果Ｇ２１，Ｇ２２，Ｇ２３，・・・，Ｇ２ｋが得られる。各スケジューラ２１，２２，２３，・・・，２ｋ間で累積割当結果を通信することによって、接続割当結果Ｇ２１，Ｇ２２，Ｇ２３，・・・，Ｇ２ｋにおいて、ある一つの入力ポートまたは出力ポートが二度以上重複して選択されることはない。そのため、接続割当結果Ｇ２１，Ｇ２２，Ｇ２３，・・・，Ｇ２ｋの間で、重複する入力ポートまたは出力ポートがないかを確認する必要がない。
【００４６】
図３は本発明の第２の実施の形態によるスケジューラの構成を示すブロック図である。図３において、スケジューラ３０は割当結果受信回路３１と、割当要求マスク回路３２と、Ｍ×Ｎスケジューラ回路３３と、割当結果送信回路３４とから構成されている。
【００４７】
割当結果受信回路３１は外部からｊ本（ｊ：自然数）のポート接続割当結果を受信し、割り当て済み入力ポート・出力ポート情報を割当要求マスク回路３２へ出力する。割当結果受信回路３１に入力されるポート接続割当結果の数ｊは各スケジューラ毎に異なる値となる。
【００４８】
割当要求マスク回路３２は割当結果受信回路３１から受信した割り当て済み入力ポート・出力ポート情報を用いて、外部から受信した接続割当要求Ｒ３１に対してマスクを行い、その結果をＭ×Ｎスケジューラ回路３３へ出力する。
【００４９】
Ｍ×Ｎスケジューラ回路３３は割当要求マスク回路３２から受信した情報に基づいてポート接続の割り当てを決定し、接続割当結果を外部及び割当結果送信回路３４へ送信する。割当結果送信回路３４はＭ×Ｎスケジューラ回路３３から受信した接続割当結果を外部へ送信する。
【００５０】
図４は本発明の本発明の第２の実施の形態によるスケジューリング回路の構成を示すブロック図である。図４において、本発明の第２の実施の形態によるスケジューリング回路はｋ個（ｋ：自然数）のスケジューラ４１，４２，４３，・・・，４ｋから構成されている。
【００５１】
スケジューラ４１は接続割当結果（Ｓ４１）をスケジューラ４２，４３，・・・，４ｋにそれぞれ送信する。スケジューラ４２は接続割当結果（Ｓ４２）をスケジューラ４３，４４，・・・，４ｋ（スケジューラ４４は図示せず）にそれぞれ送信する。これを一般化すると、スケジューラ４ｉ（ｉ＝１〜Ｋ−１の整数）は接続割当結果（Ｓ４ｉ）をスケジューラ４（ｉ＋１），４（ｉ＋２），・・・，４ｋにそれぞれ送信する。
【００５２】
尚、スケジューラ４１，４２，４３，・・・，４ｋはそれぞれ図３に示すスケジューラ３０と同様の構成となっており、その動作も同様である。この場合、割当結果受信回路３１に入力されるポート接続割当結果の数ｊは各スケジューラ４１，４２，４３，・・・，４ｋ毎に異なる値となり、スケジューラ４ｉ（ｉ＝１〜Ｋ−１）の場合、ｊ＝ｉ−１となる。
【００５３】
上記の各スケジューラ４１，４２，４３，・・・，４ｋの内部動作を、図３を参照して説明する。
【００５４】
割当結果受信回路３１は外部から入力される接続割当結果Ｓ３１１〜Ｓ３１ｊを受信し、受信した情報から既に使用済み状態となっている入力ポート及び出力ポート（以下、使用済み状態となっている入力ポート及び出力ポートをまとめて使用済みポート情報とする）を計算し、使用済みポート情報を割当要求マスク回路３２へ送信する。
【００５５】
割当要求マスク回路３２は割当結果受信回路３１から受信した使用済みポート情報に基づいて、スケジューラ３０の外部から入力された接続割当要求（Ｒ３１）のうち、既に使用済みのポートの接続割当要求を無効にする。
【００５６】
具体的に、入力ポートｉが既に使用済みであった場合には、入力ポートｉに関係する接続割当要求を全て無効にする。また、出力ポートｊが既に使用済みであった場合には、出力ポートｊに関係する接続割当要求を全て無効にする。割当要求マスク回路３２は上記の操作を全ての入力ポート・出力ポートについて行い、上記の操作によって更新された接続割当要求をＭ×Ｎスケジューラ回路３３へ送信する。
【００５７】
Ｍ×Ｎスケジューラ回路３３は割当要求マスク回路３２から受信した情報に基づいて、Ｍ個の入力ポートとＮ個の出力ポートとの間のスケジューリングを行う。スケジューリングには任意のアルゴリズムを採用することが可能である。
【００５８】
Ｍ×Ｎスケジューラ回路３３は上記のスケジューリング操作によって得られた接続割当結果を接続結果送信回路３４へ送信し、また接続割当結果をスケジューラ３０の外部へ送出する（Ｇ３１）。割当結果送信回路３４はＭ×Ｎスケジューラ回路３３から受信した接続割当結果をスケジューラ３０の外部へ送出する（Ｓ３２）。
【００５９】
スケジューラ間で通信する接続割当結果（Ｓ４１，Ｓ４２，Ｓ４３，・・・，Ｓ２ｋ）としては、Ｍ×Ｎのマトリックスを利用し、接続割り当てが行われた入力ポートと出力ポートの組を送信する方法と、割り当て済みの入力ポート及び出力ポートの情報を送信する方法との二つが考えられる。後者の類似の方法としては、未使用の入力ポート及び出力ポートの情報を送信する方法がある。
【００６０】
本発明の第２の実施の形態によるスケジューリング回路、つまりスケジューラ４１，４２，４３，・・・，４ｋの動作を図４を参照して説明する。この場合、接続割当要求の入力に関しては本発明の第１の実施の形態によるスケジューリング回路の場合と全く同様である。
【００６１】
各スケジューラ４１，４２，４３，・・・，４ｋは接続割当要求及び優先度の高いサービスクラスを扱う全てのスケジューラから接続割当結果を受信し、優先度が上位のスケジューラで既に割り当て済みの入力ポート及び出力ポートを計算し、既に使用済みの入力ポート及び出力ポートを使用しないような接続割り当てを行い、その接続割当結果を出力する。また同時に、各スケジューラ４１，４２，４３，・・・，４ｋは接続割当結果を優先度の低い全てのスケジューラに対して送信する。
【００６２】
スケジューラ４１への接続割当結果（Ｓ４０）としては全く接続割り当てがなされていない、すなわち全てのポートが選択可能であるという情報が入力される。スケジューラ４１は接続割当要求（Ｒ４１）と接続割当結果（Ｓ４０）とに基づいてスケジューリングを行い、接続割当結果を送出し（Ｇ２１）、同時にスケジューラ４２，４３，・・・，４ｋに対して接続割当結果を送信する（Ｓ４１）。
【００６３】
スケジューラ４２は接続割当要求（Ｒ４２）及びスケジューラ４１からの接続割当結果（Ｓ４１）を受信する。スケジューラ４２は接続割当結果（Ｓ４１）に基づいて、接続割当要求（Ｒ４２）のうちのスケジューラ４１で既に接続割り当ての行われた入力ポート・出力ポートに関係する割当要求を無効とし、更新された接続割当要求に基づいてスケジューリングを行い、接続割当結果を送出する（Ｇ４２）。同時に、スケジューラ４２はスケジューラ４３，・・・，４ｋに対して接続割当結果を送信する（Ｓ４２）。
【００６４】
スケジューラ４３は接続割当要求（Ｒ４３）とスケジューラ４１及びスケジューラ４２からの接続割当結果（Ｓ４１，Ｓ４２）とを受信する。スケジューラ４３は受信した接続割当結果（Ｓ４１，Ｓ４２）に基づいて、接続割当要求（Ｒ４３）のうちのスケジューラ４１及びスケジューラ４２で既に接続割り当ての行われた入力ポート・出力ポートに関係する割当要求を無効とし、更新された接続割当要求に基づいてスケジューリングを行い、接続割当結果を送出する（Ｇ４３）。同時に、スケジューラ４３はスケジューラ４４，・・・，４ｋに対して接続割当結果を送信する（Ｓ４３）。
【００６５】
以下、スケジューラ４（ｋ−１）［スケジューラ４（ｋ−１）は図示せず］まで、上記と同様の動作が実行される。スケジューラ４ｋは接続割当要求（Ｒ４ｋ）とスケジューラ４１，４２，４３，・・・，４（ｋ−１）からの累積割当結果［Ｓ４１，Ｓ４２，Ｓ４３，・・・，Ｓ４（ｋ−１）］を受信する。
【００６６】
スケジューラ４ｋは受信した接続割当結果［Ｓ４１，Ｓ４２，Ｓ４３，・・・，Ｓ４（ｋ−１）］に基づいて、接続割当要求（Ｒ４ｋ）のうちのスケジューラ４ｋよりも優先度の高いサービスクラスを扱うスケジューラで既に接続割り当ての行われた入力ポート・出力ポートに関係する割当要求を無効とし、更新された接続割当要求に基づいてスケジューリングを行い、接続割当結果を送出する（Ｇ４ｋ）。同時に、スケジューラ４ｋは接続割当結果を送出する（Ｓ４ｋ）。
【００６７】
上記の動作によって、接続割当結果Ｇ４１，Ｇ４２，Ｇ４３，・・・，Ｇ４ｋが得られる。各スケジューラ４１，４２，４３，・・・，４ｋ間で接続割当結果を通信することによって、接続割当結果Ｇ４１，Ｇ４２，Ｇ４３，・・・，Ｇ４ｋにおいて、どの入力ポートまたは出力ポートも二度以上選択されることはない。
【００６８】
図５は本発明の第１の実施例によるスケジューリング回路の構成を示すブロック図である。図５において、本発明の第１の実施例によるスケジューリング回路には本発明の第１の実施の形態によるスケジューリング回路が適用され、Ｍ＝Ｎ＝５、サービスクラス数がｋ＝４の場合を示している。
【００６９】
本発明の第１の実施例によるスケジューリング回路においては優先度の異なる４つのサービスクラスが存在し、各サービスクラスの接続割当要求が５×５のマトリックスで表現されている。そのマトリックスにおいて、縦軸は入力ポートを示し、横軸は出力ポートを示している。その場合には入力ポートｓ、出力ポートｄの要素が１であれば、入力ポートｓから出力ポートｄへの接続割当要求があることを意味している。
【００７０】
上記の構成において、スケジューラ２１，２２，２３，２４には最優先クラス、優先度２番目クラス、優先度３番目クラス、最低優先クラスの接続割当要求がそれぞれ入力される。
【００７１】
また、スケジューラ２１，２２，２３，２４から出力される接続割当結果のマトリックスも上記と同様に定義され、要素が１となっている場所が接続割り当てがなされた入力ポート・出力ポートの組を表している。以下、（ｓ，ｄ）と記述した場合、入力ポートｓ、出力ポートｄに対応するものとする。
【００７２】
本発明の第１の実施例ではスケジューラ２１，２２，２３，２４間で通信される累積割当結果として、使用済み入力ポート情報、使用済み出力ポート情報が用いられている。そのマトリックスにおいて、値が１になっているポートは既に使用済みであることを示す。以下、使用済み入力ポート情報と使用済み出力ポート情報とをまとめて使用済みポート情報とする。
【００７３】
上記の構成においてはスケジューラ２１よりも優先度の高いスケジューラがないため、スケジューラ２１に入力される使用済み入力ポート情報、使用済み出力ポート情報には双方とも全て０が入力される。
【００７４】
スケジューラ２１においては入力ポート及び出力ポートとも使用済みのポートが存在しないため、入力された割当要求Ｒ２１が変更されることなく、Ｍ×Ｎスケジューラ回路１３に入力され、Ｇ２１に示す接続割り当てがなされたとする。尚、Ｍ×Ｎスケジューラ回路１３では任意のスケジューリングアルゴリズムを採用することができる。
【００７５】
割当結果送信回路１４ではＭ×Ｎスケジューラ回路１３から受信したＧ２１と同様の接続割当結果及び使用済みポート情報Ｓ２０に基づいて、使用済み入力ポート情報及び使用済み出力ポート情報を計算する。スケジューラ２１で得られた接続割り当ては（１，１）（４，４）なので、使用済み入力ポート情報及び使用済み出力ポート情報ともポート１，４に１がセットされ、スケジューラ２１からスケジューラ２２に送信される。
【００７６】
スケジューラ２２は割当結果受信回路１１においてスケジューラ２１からの使用済みポート情報Ｓ２１を受信し、受信した情報を割当要求マスク回路１２へ伝える。割当要求マスク回路１２では割当結果受信回路１１から受信した使用済みポート情報を基に、入力された接続割当要求Ｒ２２のマスク処理を行う。
【００７７】
割当要求マスク回路１２では使用済み入力ポート情報が１となっている入力ポート１，４、使用済み出力ポート情報が１となっている出力ポート１，４に関係する接続割当要求が無効となる。割当要求マスク回路１２でのマスク処理によって接続割当要求Ｒ２２のマトリックスにおいて、背景に斜線の入っている部分の要素は全て０に置き換えられる。
【００７８】
Ｍ×Ｎスケジューラ回路１３では割当要求マスク回路１２で更新された接続割当要求に基づいて接続割り当てが実行され、Ｇ２２に示す接続割り当てがなされたとする。割当結果送信回路１４ではＭ×Ｎスケジューラ回路１３から受信したＧ２２と同様の接続割当結果及び入力された使用済みポート情報に基づき、使用済み入力ポート情報及び使用済み出力ポート情報を計算する。
【００７９】
スケジューラ２２で得られた接続割り当ては（３，５）なので、スケジューラ２１から受信した使用済み入力ポート情報に、さらに新たに割り当てられた入力ポート３に１がセットされ、計３ヶ所が使用済みとなる。使用済み出力ポート情報についても、上記の入力ポート同様に、出力ポート５に１がセットされ、こちらも計３ヶ所が使用済みとなる。
【００８０】
スケジューラ２２は更新した使用済みポート情報Ｓ２２をスケジューラ２３へ送信する。この時、使用済みポート情報Ｓ２２にはスケジューラ２１及びスケジューラ２２での割当結果が反映されている。
【００８１】
スケジューラ２３は割当結果受信回路１１においてスケジューラ２２から使用済みポート情報Ｓ２２を受信し、受信した使用済みポート情報を割当要求マスク回路１２へ伝える。割当要求マスク回路１２では割当結果受信回路１１から受信した使用済みポート情報を基に、入力された接続割当要求Ｒ２３のマスク処理を
行う。
【００８２】
割当要求マスク回路１２では使用済み入力ポート情報が１となっている入力ポート１，３，４、使用済み出力ポート情報が１となっている出力ポート１，４，５に関係する接続割当要求が無効となる。割当要求マスク回路１２でのマスク処理によって、接続割当要求Ｒ２３のマトリックスにおいて、背景に斜線の入っている部分の要素は全て０に置き換えられる。
【００８３】
Ｍ×Ｎスケジューラ回路１３では割当要求マスク回路１２で更新された接続割当要求に基づいて接続割り当てが実行されるが、マスク処理によって全ての接続割当要求が０となったため、接続割り当ては行われない（Ｇ２３のマトリックスは全て０となる）。
【００８４】
割当結果送信回路１４ではＭ×Ｎスケジューラ回路１３から受信したＧ２３と同様の接続割当結果及び入力された使用済みポート情報Ｓ２２に基づき、使用済み入力ポート情報及び使用済み出力ポート情報を計算するが、接続割り当てがなされていないため、スケジューラ２２から受信した使用済みポート情報を変更せずにスケジューラ２４へ送信する。
【００８５】
スケジューラ２４では接続割当要求Ｒ２４及びスケジューラ２３からの使用済みポート情報Ｓ２３を受信し、スケジューラ２３と同様の動作を行い、接続割当結果Ｇ２４及び使用済みポート情報Ｓ２４を出力する。使用済みポート情報Ｓ２４はスケジューラ２１，２２，２３，２４での割当結果が反映されている。
【００８６】
接続割当結果Ｇ２１，Ｇ２２，Ｇ２３，Ｇ２４において、いずれの入力ポート及び出力ポートとも二度以上選択されていない。これは優先順位の高いスケジューラから優先順位の低いスケジューラへ累積割当結果（本実施例では使用済みポート情報）を送信することによって、既に使用されている入力ポート／出力ポートに関係する接続割当要求を無効にしていることによる効果である。
【００８７】
図６は本発明の第２の実施例によるスケジューリング回路の構成を示すブロック図である。図６において、本発明の第２の実施例によるスケジューリング回路には本発明の第１の実施の形態によるスケジューリング回路が適用され、Ｍ＝Ｎ＝５、サービスクラス数がｋ＝４の場合を示している。
【００８８】
本発明の第２の実施例において、サービスクラスと接続割当要求とを入力するスケジューラとの対応関係、接続割当要求・接続割当結果のマトリックスの定義、各スケジューラ内の割当要求マスク回路１２及びＭ×Ｎスケジューラ回路１３の動作は上記の本発明の第１の実施例と全く同じである。本発明の第２の実施例が本発明の第１の実施例と異なる点は、累積割当結果の送信方法、割当結果受信回路１１の動作、割当結果送信回路１２の動作の３点である。
【００８９】
スケジューラ間で通信する累積割当結果としては、既に接続割り当ての行われた入力ポートと出力ポートとの組を示すＭ×Ｎのマトリックスを用いている。累積割当結果を表すマトリックスの定義は接続割当結果と同様で、入力ポートｓから出力ポートｄへ接続割り当てがなされた場合、対応するマトリックスの要素（ｓ、ｄ）に１がセットされる。接続割り当てがされていない入力ポートと出力ポートとの組に対応するマトリックスの要素は０である。
【００９０】
本発明の第２の実施例におけるスケジューラ２１，２２，２３，２４の動作は本発明の第１の実施例と全く同じである。スケジューラ２２を例にとり、割当結果受信回路１１及び割当結果送信回路１２の動作について以下説明する。
【００９１】
割当結果受信回路１１はスケジューラ２１から受信した累積割当結果Ｓ２１に基づき、スケジューラ２２よりも優先度の高いサービスクラスを扱うスケジューラで既に割当済みの入力ポート及び出力ポートを計算する。本実施例では入力ポートに関してはポート１，４が既に割り当て済み、出力ポートに関してはポート１，４が割り当て済みであると求められる。得られた割り当て済みの入力ポート及び出力ポートについての情報は割当要求マスク回路１２へ送信される。
【００９２】
割当結果送信回路１４はＭ×Ｎスケジューラ回路１３から受信する接続割当結果（Ｇ２２と同じ）とスケジューラ２１から送信された累積割当結果Ｓ２１との論理和をマトリックスの要素毎に計算し、新たな累積割当結果Ｓ２２を作成し、スケジューラ２３へ送信する。累積割当結果Ｓ２２を累積割当結果Ｓ２１と比較すると、スケジューラ２２で割り当てられた接続（３，５）が累積割当結果Ｓ２２に追加されていることがわかる。
【００９３】
図７は本発明の第３の実施例によるスケジューリング回路の構成を示すブロック図である。図７において、本発明の第３の実施例によるスケジューリング回路には本発明の第２の実施の形態によるスケジューリング回路が適用され、Ｍ＝Ｎ＝５、サービスクラス数がｋ＝４の場合を示している。
【００９４】
本発明の第３の実施例において、サービスクラスと接続割当要求とを入力するスケジューラとの対応関係、接続割当要求・接続割当結果のマトリックスの定義は本発明の第１の実施例の場合と同じとする。
【００９５】
本発明の第３の実施例ではスケジューラ間で通信する累積割当結果として、使用済み入力ポート情報、使用済み出力ポート情報を用いる。値が１になっているポートは既に使用済みであることを示す。以下、使用済み入力ポート情報と使用済み出力ポート情報とをまとめて使用済みポート情報とする。
【００９６】
上記の構成において、スケジューラ４１よりも優先度の高いスケジューラはないため、スケジューラ４１に入力される使用済み入力ポート情報、使用済み出力ポート情報には双方とも全て０が入力されている。
【００９７】
スケジューラ４１においては入力ポート及び出力ポートとも使用済みのポートが存在しないため、入力された割当要求Ｒ４１が変更されることなく、Ｍ×Ｎスケジューラ回路３３に入力され、Ｇ４１に示す接続割り当てがなされたとする。尚、Ｍ×Ｎスケジューラ回路３３で使用されるスケジューリングアルゴリズムの選択については自由である。
【００９８】
割当結果送信回路３４ではＭ×Ｎスケジューラ回路３３から受信したＧ４１と同様の接続割当結果に基づき、使用済み入力ポート情報及び使用済み出力ポート情報を計算する。スケジューラ４１で得られた接続割当は（１，１）（４，４）なので、使用済み入力ポート情報及び使用済み出力ポート情報ともポート１，４に１がセットされ、スケジューラ４１から使用済みポート情報Ｓ４１が出力される。
【００９９】
スケジューラ４１から出力される使用済みポート情報Ｓ４１は、スケジューラ４１より優先度の低いスケジューラ全て、すなわちスケジューラ４２，４３，４４に分配される。
【０１００】
スケジューラ４２は割当結果受信回路３１においてスケジューラ４１からの使用済みポート情報Ｓ４１を受信し、受信した情報を割当要求マスク回路３２へ伝える。割当要求マスク回路３２では割当結果受信回路３１から受信した使用済みポート情報を基に、入力された接続割当要求Ｒ４２のマスク処理を行う。
【０１０１】
割当要求マスク回路３２では使用済み入力ポート情報が１となっている入力ポート１，４、使用済み出力ポート情報が１となっている出力ポート１，４に関係する接続割当要求が無効となる。割当要求マスク回路３２でのマスク処理によって、接続割当要求Ｒ４２のマトリックスにおいて、背景に斜線の入っている部分の要素は全て０に置き換えられる。
【０１０２】
Ｍ×Ｎスケジューラ回路３３では割当要求マスク回路３２で更新された接続割当要求に基づいて接続割り当てが実行され、Ｇ４２に示す接続割り当てがなされたとする。
【０１０３】
割当結果送信回路３４ではＭ×Ｎスケジューラ回路３３から受信したＧ４２と同様の接続割当結果に基づき、使用済み入力ポート情報及び使用済み出力ポート情報を計算する。スケジューラ４２で得られた接続割り当てが（３，５）なので、使用済み入力ポート情報については入力ポート３に１がセットされ、他のポートは全て０である。使用済み出力ポート情報についても上記の入力ポート同様に出力ポート５に１がセットされ、他のポートは全て０である。
【０１０４】
スケジューラ４２はスケジューラ４２よりも優先度の低いスケジューラ全て、すなわちスケジューラ４３，４４に分配される。使用済みポート情報Ｓ４２にはスケジューラ４２での割当結果のみが反映されている。
【０１０５】
スケジューラ４３は割当結果受信回路３１においてスケジューラ４１及びスケジューラ４２からそれぞれ使用済みポート情報Ｓ４１，Ｓ４２を受信し、使用済みポート情報Ｓ４１と使用済みポート情報Ｓ４２との論理和を計算することによって、既に使用済みの入力ポート、出力ポート情報を求める。
【０１０６】
求められた使用済み入力ポート情報は入力ポート１，３，４が使用済み、使用済み出力ポート情報は出力ポート１，４，５が使用済みとなっている。割当結果受信回路３１でこのようにして求めた使用済みポート情報は割当要求マスク回路３２に伝えられる。
【０１０７】
割当要求マスク回路３２では割当結果受信回路３１から受信した使用済みポート情報を基に、入力された接続割当要求Ｒ４２のマスク処理を行う。割当要求マスク回路３２では使用済み入力ポート情報が１となっている入力ポート１，３，４、使用済み出力ポート情報が１となっている出力ポート１，４，５に関係する接続割当要求が無効となる。割当要求マスク回路３２でのマスク処理によって、接続割当要求Ｒ４３のマトリックスにおいて、背景に斜線の入っている部分の要素は全て０に置き換えられる。
【０１０８】
Ｍ×Ｎスケジューラ回路３３では割当要求マスク回路３２で更新された接続割当要求に基づいて接続割り当てが実行されるが、マスク処理によって全ての接続割当要求が０となったため、接続割り当ては行われない（Ｇ４３のマトリックスは全て０となる）。
【０１０９】
割当結果送信回路３４ではＭ×Ｎスケジューラ回路３３から受信したＧ４３と同様の接続割当結果に基づき、使用済み入力ポート情報及び使用済み出力ポート情報を計算するが、接続割り当てがなされていないため、使用済みポート情報は全て０（使用済みなし）に設定され、スケジューラ４４へ送信される。使用済みポート情報Ｓ４３にはスケジューラ４３での割当結果のみが反映されている。
【０１１０】
スケジューラ４４では割当結果受信回路３１においてスケジューラ４４よりも優先度の高いスケジューラ４１，４２，４３の使用済みポート情報Ｓ４１，Ｓ４２，Ｓ４３を受信し、スケジューラ４３と同様の使用済みポート情報の和を計算し、既に使用済みのポートを求め、割当要求マスク回路３２へ送信する。
【０１１１】
割当要求マスク回路３２では接続割当要求Ｒ４４及び使用済みポート情報に基づき、スケジューラ４３の場合と同様に接続要求マスク処理を動作を行う。Ｍ×Ｎスケジューラ回路３３では更新された接続割当要求に基づいて接続割り当てが実行され、Ｇ４４に示す接続割り当てがなされたとする。
【０１１２】
割当結果送信回路３４ではＭ×Ｎスケジューラ回路３３から受信したＧ４４と同様の接続割当結果に基づき、使用済み入力ポート情報及び使用済み出力ポート情報を計算し、その接続割当結果を出力する（Ｓ４４）。使用済みポート情報Ｓ４４にはスケジューラ４４での割当結果のみが反映されている。
【０１１３】
接続割当結果Ｇ４１，Ｇ４２，Ｇ４３，Ｇ４４において、いずれの入力ポート及び出力ポートとも二度以上選択されていない。これは優先順位の高いスケジューラから優先順位の低いスケジューラへ接続割当結果（本実施例では使用済みポート情報）を送信することによって、既に使用されている入力ポート／出力ポートに関係する接続割当要求を無効にしていることによる効果である。
【０１１４】
このように、Ｍ×Ｍスケジューラを複数用いることによって、複数のサービスクラス間の優先順位を考慮した接続割り当てを行うスケジューラにおいて、高優先クラスを扱うスケジューラの接続割当結果を低優先クラスを扱うスケジューラが参照することによって、効率的な無駄の少ない接続割り当てを行うことができる。
【０１１５】
【発明の効果】
以上説明したように本発明によれば、Ｍ個（Ｍ：自然数）の入力ポートとＮ個（Ｎ：自然数）の出力ポートとを持つクロスポイントスイッチのポート接続の割り当てを行うスケジューラを複数個用い、前記複数のスケジューラ各々に複数のサービスクラスをそれぞれ割り当て、前記複数のサービスクラス間の優先順位を考慮したポート接続割り当てを行うスケジューリング回路において、複数のスケジューラ各々が、自回路よりも高優先クラスを扱うスケジューラにおける接続割当結果と重複が起こらないような接続割り当てを、優先度の高いサービスクラスを扱うスケジューラから優先度の低いサービスクラスを扱うスケジューラへと順に行うことによって、効率的な無駄の少ない接続割り当てを行うことができるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態によるスケジューラの構成を示すブロック図である。
【図２】本発明の本発明の第１の実施の形態によるスケジューリング回路の構成を示すブロック図である。
【図３】本発明の第２の実施の形態によるスケジューラの構成を示すブロック図である。
【図４】本発明の本発明の第２の実施の形態によるスケジューリング回路の構成を示すブロック図である。
【図５】本発明の第１の実施例によるスケジューリング回路の構成を示すブロック図である。
【図６】本発明の第２の実施例によるスケジューリング回路の構成を示すブロック図である。
【図７】本発明の第３の実施例によるスケジューリング回路の構成を示すブロック図である。
【図８】従来例によるスケジューリング回路の構成を示すブロック図である。
【図９】従来手法の問題点を示す図である。
【符号の説明】
１１，３１  割当結果受信回路
１２，３２  割当要求マスク回路
１３，３３  Ｍ×Ｎスケジューラ回路
１４，３４  割当結果送信回路
２１，４１  優先度が最も高いスケジューラ
２２，４２  優先度が２番目のスケジューラ
２３，４３  優先度が３番目のスケジューラ
２４，４４  優先度が４番目のスケジューラ
２ｋ，４ｋ  優先度が最も低いスケジューラ
【図１】
0003606126.tif 000002
【図２】
0003606126.tif 000003
【図３】
0003606126.tif 000004
【図４】
0003606126.tif 000005
【図５】
0003606126.tif 000006
【図６】
0003606126.tif 000007
【図７】
0003606126.tif 000008
【図８】
0003606126.tif 000009
【図９】
0003606126.tif 000010