(57)【特許請求の範囲】
【請求項１】
ネットワークにおけるデータのフローを制御するスイッチであって、
複数の入力ポートと、
複数の出力ポートと、
前記複数の出力ポートのうちの指定出力ポートへデータを送るように、前記複数の入力ポートのうちの特定の入力ポートを予約し、入力ポートと出力ポートとの接続状態を決定するＮ個（Ｎは自然数、以下同じ）の入力ポートスケジューリングモジュールを有するスケジューラと、
を含み、
前記スケジューラは、
タイムスロット単位に、
各入力ポートスケジューリングモジュールが、前段のスケジューリングモジュールから、ある予約タイムスロットの予約状況情報を受信し、
各入力ポートスケジューリングモジュールが、その予約タイムスロットにおける当該入力ポートスケジューリングモジュールからのパケット送出予約可否を決定し、
各入力ポートスケジューリングモジュールが、前段のスケジューリングモジュールから受信した予約状況情報に、自スケジューリングモジュールの予約結果を反映させて、次段のスケジューリングモジュールに送信する手段と、
Ｎ個のタイムスロットを単位とするフレームを定義して、前記フレーム時間内で、前記フレームの次のフレーム中のＮ個のタイムスロットでの予約を行う手段と、
現在のスケジューリングモジュールが、前のスケジューリングモジュールから予約状況情報を受信する手段と、
前記現在のスケジューリングモジュールが、前記複数の出力ポートのうちの１つにアクセスしようとする将来のタイムスロットを予め次のフレーム内の特定のタイムスロットに決定する手段と、
前記複数の出力ポートのうちの１つを前記将来のタイムスロットでの送信用に予約するように選択する手段と、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約済みかどうかを判断する手段と、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約されていない場合には、前記将来のタイムスロットを予約し、前記将来のタイムスロットが予約されたことを示す情報を前記予約状況情報に入れる手段と、
前記予約状況情報を次のスケジューリングモジュールに渡す手段と、
タイムスロットでの予約過程の観点から見た場合、
前記予約過程が、フレームの先頭で同時に開始され、フレーム内で同時にパイプライン処理により進行し、
フレームの末端で同時に完了し、
前記入力ポートスケジューリングモジュールが、フレームの先頭で同時に開始する複数の前記予約過程それぞれにおいて、次のフレーム内の各々異なる予約タイムスロットを対象として処理を開始する手段と、
前記複数のスケジューリングモジュールによる前記予約の順序を変更する予約順序変更手段とを含み、
この変更された順序で前記複数のスケジューリングモジュールそれぞれが各フレーム毎に次のフレームのパケットについて出力すべきポートを予約するようにし、
前記複数のスケジューリングモジュールは他のモジュールとの論理的接続順序に対応した順序で前記予約を実行するものであり、前記予約順序変更手段は前記複数のスケジューリングモジュールの接続トポロジを変更することを特徴とするパケットスイッチ。
【請求項２】
前記予約順序変更手段は、前記複数のスケジューリングモジュールの論理的接続状態を変更するようにスイッチング動作するスイッチと、このスイッチのスイッチング動作を制御する制御データを記憶したテーブルとを含むことを特徴とする請求項１記載のパケットスイッチ。
【請求項３】
前記複数のスケジューリングモジュールと前記スイッチ間の物理的接続は、電気的接続であることを特徴とする請求項２記載のパケットスイッチ。
【請求項４】
前記複数のスケジューリングモジュールと前記スイッチ間の物理的接続は、光学的接続であることを特徴とする請求項２記載のパケットスイッチ。
【請求項５】
前記テーブルは、前記複数のスケジューリングモジュールそれぞれの内部に設けられていることを特徴とする請求項２〜４のいずれかに記載のパケットスイッチ。
【請求項６】
前記テーブルは、前記複数のスケジューリングモジュールに対して共通に設けられていることを特徴とする請求項２〜４のいずれかに記載のパケットスイッチ。
【請求項７】
前記制御データは、前記複数のスケジューリングモジュール各々がフレーム内の先頭において予約を開始するタイムスロットを各フレーム毎に変更できるように前記スイッチのスイッチング動作を制御するデータであることを特徴とする請求項２〜６のいずれかに記載のパケットスイッチ。
【請求項８】
前記制御データは、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用頻度を均等とするスケジューリングを実現するデータであることを特徴とする請求項２〜６のいずれかに記載のパケットスイッチ。
【請求項９】
前記制御データは、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用順序及び使用頻度を変更可能とするスケジューリングを実現するデータであることを特徴とする請求項２〜６のいずれかに記載のパケットスイッチ。
【請求項１０】
Ｎ個の入力ポートスケジューリングモジュールを有するスイッチのスケジューラにて使用する、複数の出力ポートのうちの指定出力ポートへデータを送るように、複数の入力ポートのうちの特定の入力ポートを予約し、入力ポートと出力ポートとの接続状態を決定するパケットスイッチング方法であって、
各入力スケジューリングモジュールが、前段のスケジューリングモジュールからあるタイムスロットの予約状況情報を受信するステップと、
各スケジューリングモジュールが、その予約タイムスロットにおける当該入力ポートスケジューリングモジュールからのパケット送出予約可否を決定するステップと、
各入力スケジューリングモジュールが、前段のスケジューリングモジュールから受信した予約状況情報に、自スケジューリングモジュールの予約結果を反映させて、次段のスケジューリングモジュールに送信するステップと、
を含み、
前記スケジューラは、
現在のスケジューリングモジュールが、前のスケジューリングモジュールから予約状況情報を受信するステップと、
前記現在のスケジューリングモジュールが、前記複数の出力ポートのうちの１つにアクセスしようとする将来のタイムスロットを予め次のフレーム内のタイムスロットに決定するステップと、
前記複数の出力ポートのうちの１つを前記将来のタイムスロットでの送信用に予約するように選択するステップと、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約済みかどうかを判断するステップと、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約されていない場合には、前記将来のタイムスロットを予約し、前記将来のタイムスロットが予約されたことを示す情報を前記予約状況情報に入れるステップと、
前記予約状況情報を次のスケジューリングモジュールに渡すステップと、
を実行し、
タイムスロットでの予約過程の観点から見た場合、
前記予約過程が、フレームの先頭で同時に開始され、フレーム内で同時にパイプライン処理により進行し、
フレームの末端で同時に完了し、
前記入力ポートスケジューリングモジュールが、フレームの先頭で同時に開始する複数の前記予約過程それぞれにおいて、次のフレーム内の各々異なる予約タイムスロットを対象として処理を開始し、
さらに、前記複数のスケジューリングモジュールによる前記予約の順序を変更し、この変更された順序で前記複数のスケジューリングモジュールそれぞれが各フレーム毎に次のフレームのパケットについて出力すべきポートを予約するようにし、
前記複数のスケジューリングモジュールは他のモジュールとの論理的接続順序に対応した順序で前記予約を実行するものであり、前記予約順序の変更においては前記複数のスケジューリングモジュールの接続トポロジを変更することを特徴とするパケットスイッチング方法。
【請求項１１】
前記予約の順序の変更においては、前記複数のスケジューリングモジュールの論理的接続状態を変更するようにスイッチング動作するスイッチと、このスイッチのスイッチング動作を制御する制御データを記憶したテーブルとを用いて予約順序を変更することを特徴とする請求項１０記載のパケットスイッチング方法。
【請求項１２】
前記複数のスケジューリングモジュールと前記スイッチ間の物理的接続は、電気的接続であることを特徴とする請求項１１記載のパケットスイッチング方法。
【請求項１３】
前記複数のスケジューリングモジュールと前記スイッチ間の物理的接続は、光学的接続であることを特徴とする請求項１１記載のパケットスイッチング方法。
【請求項１４】
前記テーブルは、前記複数のスケジューリングモジュールそれぞれの内部に設けられていることを特徴とする請求項１１〜１３のいずれかに記載のパケットスイッチング方法。
【請求項１５】
前記テーブルは、前記複数のスケジューリングモジュールに対して共通に設けられていることを特徴とする請求項１１〜１３のいずれかに記載のパケットスイッチング方法。
【請求項１６】
前記制御データは、前記複数のスケジューリングモジュール各々がフレーム内の先頭において予約を開始するタイムスロットを各フレーム毎に変更できるように前記スイッチのスイッチング動作を制御するデータであることを特徴とする請求項１１〜１５のいずれかに記載のパケットスイッチング方法。
【請求項１７】
前記制御データは、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用頻度を均等とするスケジューリングを実現するデータであることを特徴とする請求項１１〜１５のいずれかに記載のパケットスイッチング方法。
【請求項１８】
前記制御データは、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用順序及び使用頻度を変更可能とするスケジューリングを実現するデータであることを特徴とする請求項１１〜１５のいずれかに記載のパケットスイッチング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケットスイッチに関し、特にパケット交換システムにおける入出力間のスケジューリング及びそのスケジューリングを実現するためのパケットスイッチに関する。
【０００２】
【従来の技術】
近年のパケット交換システムでは、Ｎ入力、Ｎ出力（Ｎは自然数、以下同じ）を有し、かつ各入力部がＮ個の仮想出力キュー（Ｖｉｒｔｕａｌ  ＯｕｔｐｕｔＱｕｅｕｉｎｇ：ＶＯＱ）を有する入力バッファ型スイッチが用いられることがある。
【０００３】
図１１に一般的なＮ入力、Ｎ出力（Ｎは自然数、以下同じ）の入力バッファ型パケットスイッチの構成が示されている。同図を参照すると、パケットスイッチ４０は、データを入力する複数の入力ポートと、データを出力する複数の出力ポートと、入力ポートから入力されたデータをスイッチングして出力ポートへ転送するデータスイッチング素子５４と、スイッチ素子５４を制御するスケジューラ５０とを備えている。
【０００４】
入力ポートは仮想出力キュー（ＶＯＱ）５２の構成をとっている。スイッチング素子５４としてはクロスバースイッチが考えられる。スケジューラ５０は分散スケジューリングの構成をとっており、入力ポート毎の分散スケジューリングモジュール５１−ｉ（ｉ＝１〜Ｎ）から構成される。
【０００５】
上述したパケットスイッチは、クロスバースイッチ内の転送を、固定サイズのパケットにて行っているとする。これにより、スイッチシステムの動作時刻を量子化している。この量子化単位をタイムスロットと呼ぶ。
【０００６】
スケジューラは、タイムスロット単位に各入力ポートから各出力ポート毎の接続要求情報（ＲＥＱ）を受信し、接続要求情報に基づいて入力ポートと出力ポートの間の接続許可情報（ＧＲＡＮＴ）を決定する。スケジューラは接続許可情報を基に入力ポートと出力ポートとの接続情報（ＭＳＥＬ）を生成してスイッチング素子に通知し、スイッチング素子の入出力の接続を設定する。
【０００７】
また、スケジューラは接続許可情報を基に各入力ポートがどの出力ポートからのデータ転送が許可されているかを示す転送許可情報（ＤＳＴＭＳＧ）を作成し、各入力ポートに対して転送許可情報を通知する。入力ポートは転送許可情報に従ってデータをスイッチング素子へ出力し、出力ポートがデータを受信してスイッチングが完了する。
【０００８】
スケジューラの目的は、Ｎ×Ｎの接続要求情報からＮ×Ｎの接続許可情報を生成することである。接続許可情報を生成するに当たり、各分散スケジューリングモジュール５１−１〜５１−Ｎは、個々の入力ポートに対する出力ポートへの接続可否を決定している。
【０００９】
ある分散スケジューリングモジュール５１−ｎ（ｎは自然数で、１≦ｎ≦Ｎ）が接続許可とした出力ポートは、他の分散スケジューリングモジュール５１−ｍ（ｍ≠ｎ）にとっては別の分散スケジューリングモジュールに「予約」されたポートであり、接続許可を発出することが不可能なポートとなる。以下、ある分散スケジューリングモジュールがある出力ポートへ接続許可と決定する動作を「出力ポートを予約する」と表現する。
【００１０】
パケットスイッチの分散型スケジューリングアルゴリズムとして、１９９９年ＧｌｏｂｅｃｏｍにおいてＡ．Ｓｍｉｌｊａｎｉｃ，Ｒ．Ｆａｎ及びＧ．Ｒａｍａｍｕｒｔｈｙが発表した「ＲＲＧＳ：Ｒｏｕｎｄ  Ｒｏｂｉｎ  ＧｒｅｅｄｙＳｃｈｅｄｕｌｉｎｇ  ｆｏｒ  Ｅｌｅｃｔｒｉｃ  ／Ｏｐｔｉｃａｌ  Ｔｅｒａｂｉｔ  Ｓｗｉｔｃｈｅｓ」に示されているラウンド・ロビン・グリーディ・スケジューリング（Ｒｏｕｎｄ  Ｒｏｂｉｎ  Ｇｒｅｅｄｙ  Ｓｃｈｅｄｕｌｉｎｇ：ＲＲＧＳ）アルゴリズムがある。
【００１１】
ＲＲＧＳアルゴリズムを用いたスケジューラでは、分散スケジューリングモジュールがリング状に接続され、隣接した分散スケジューリングモジュール間でメッセージ受渡しを行う。ＲＲＧＳアルゴリズムでは、各分散スケジューリングモジュールが対象となるタイムスロットの予約（接続許可決定）を行い、結果の情報を次の分散スケジューリングモジュールに渡す。メッセージ受渡し速度要求条件を緩和するために、ＲＲＧＳはパイプライン機能を導入している。あるタイムスロットの予約過程は、各分散スケジューリングモジュール間でメッセージ受渡しが一周することにより完了する。また、ＲＲＧＳアルゴリズムでは、Ｎ個の分散スケジューリングモジュールが、現在のスロットの少なくともＮスロット先のタイムスロットに関して予約する。更に、ＲＲＧＳアルゴリズムは、Ｎ個のタイムスロットに対する予約過程を１タイムスロットずつ位相をずらしながら同時に進行させていく。
【００１２】
一方、ＲＲＧＳアルゴリズムの変形として、複数のタイムスロットに対する予約過程をそれぞれ異なる分散スケジュールモジュールから同時に開始し、進行させ、同時に終了させるアルゴリズムも考えられる。本アルゴリズムをフレーム化ＲＲＧＳと呼ぶこととする。
【００１３】
図１２はＲＲＧＳ及びフレーム化ＲＲＧＳを使用する分散型スケジューラによるパケットスイッチの構成を示すブロック図である。同図においては、例としてポート数Ｎ＝４の場合を示している。同図において、スケジューラ１は分散型スケジューリングのためのインプットモジュール（Ｉｎｐｕｔ  Ｍｏｄｕｌｅ；ＩＭ）１０−１〜１０−４から構成される。各モジュール１０−ｉ（ｉ＝１〜４）には、フレームの先頭を示すフレームパルス（ＦＰ）２１と、スーパーフレームの先頭を示すスーパーフレームパルス（ＳｕｐｅｒＦＰ）２２が入力される。各モジュール１０−ｉはフレームパルス２１もしくはスーパーフレームパルス２２に同期して動作する。
【００１４】
また、各モジュール１０−ｉにはモジュール識別のための物理番号２３が設定される。各入力ポートから接続要求情報１１がモジュール１０−ｉに入力され、各モジュール１０−ｉは接続要求の調停の結果、予約（接続許可）を決定し接続許可情報１２−１〜１２−４を出力する。
【００１５】
ＲＲＧＳ及びフレーム化ＲＲＧＳにおいては、隣接分散スケジューリングモジュール間で接続許可情報から入力ポート情報を縮退させた情報（入力ポート情報を参照して作成した情報）である「出力ポート予約済情報」を受け渡すことにより、出力ポートに対する接続要求の競合を回避している。例えば、モジュール１０−３は、前段のモジュール１０−２から出力ポート予約済情報１４−２を出力ポート予約済情報１３−３として受信して接続要求の調停に使用する。接続許可情報決定後、出力ポート予約済情報１４−３を次段のモジュール１０−４に通知する。
【００１６】
図１３はフレーム化ＲＲＧＳの一般的な動作例を示した図である。以下、図１２及び図１３を参照してフレーム化ＲＲＧＳの動作を説明する。例として４×４の入出力ポートを有するスイッチの動作を示す。
【００１７】
出力ポート予約済情報の転送方向は、モジュールの番号で＃１→＃２→＃３→＃４→＃１→＃２…とする。
【００１８】
各情報の極性を以下のように定義する。各入力ポートの接続要求は、１が要求あり、０が要求無しとする。接続許可情報（予約情報）は、１が許可（予約済）、０が禁止（未予約）とする。出力ポート予約済情報は、１が予約済、０が未予約とする。
【００１９】
また、本例では４タイムスロットで１フレームを構成しており、フレームパルス２１は４タイムスロット周期で入力される。なお、スーパーフレームパルス２２は、本例では使用されない。
【００２０】
図１３において、タイムスロットＴＳ１でモジュール１０−１〜１０−４にフレームパルス２１が入力されると、モジュール１０−１が次フレームのタイムスロットＴＳ１に対する入力ポート１の接続許可情報を最初に決定する。最初の決定であるので、出力ポート予約済情報は、出力ポート１から４まで順番に（０，０，０，０）である。入力ポート１の接続要求が出力ポート１から４まで順番に（０，１，０，１）であるとする。モジュール１０−１が出力ポート２を選択すると、モジュール１０−１は次フレームのタイムスロットＴＳ１の接続許可情報として出力ポート２を記憶し、出力ポート予約済情報を（０，１，０，０）としてモジュール１０−２に通知する。
【００２１】
続けてタイムスロットＴＳ２でモジュール１０−２が次フレームのタイムスロットＴＳ１に対する入力ポート２の接続許可情報を決定する。モジュール１０−２は出力ポート予約済情報（０，１，０，０）を受信する。入力ポート２の接続要求が（０，１，１，１）であるとすると、出力ポート２に対する割当ては行えないため、モジュール１０−２は出力ポート２に対する接続要求は拒否し、出力ポート３及び４の接続要求から許可する出力ポートを選択する。ここでポート３を選択すると、モジュール１０−２はＴ５の接続許可情報として出力ポート３を記憶し、出力ポート予約済情報を（０，１，１，０）としてモジュール１０−３に通知する。
【００２２】
以下、タイムスロットＴＳ３でモジュール１０−３が、タイムスロットＴＳ４でモジュール１０−４が次フレームのタイムスロットＴＳ１の接続許可情報を決定する。タイムスロットＴＳ４が終了した時点で各モジュールは次フレームのタイムスロットＴＳ１における接続許可情報を有しているので、次フレームのタイムスロットＴＳ１における４×４の接続許可情報が確定することとなる。
【００２３】
更に上記処理手順においては、タイムスロットＴＳ１でモジュール１０−１以外のモジュールがそれぞれ異なるタイムスロットに対する「予約」を開始する。例えば、モジュール１０−２は次フレームのタイムスロットＴＳ４、モジュール１０−３は次フレームのタイムスロットＴＳ３、モジュール１０−４は次フレームのタイムスロットＴＳ２に対する「予約」を開始する。
【００２４】
各モジュールは当該タイムスロットにて各予約タイムスロットの処理を行い、該当する予約タイムスロットの出力ポート予約済情報をそれぞれ次段のモジュールに転送することにより、各モジュール１０−１〜１０−４とも未動作の時間がないようにスケジューリング処理を実行できる。そして、タイムスロットＴＳ４が終了した時点で各モジュールは次フレームのタイムスロットＴＳ１からＴＳ４までの接続許可情報を有しているので、次フレームのタイムスロットＴＳ１からＴＳ４までの４×４の接続許可情報が確定することとなる。
【００２５】
図１４は各モジュールの予約（接続許可決定）順序を示す図である。４×４スケジューラの場合を例示している。横軸は時間であり４タイムスロットで１つのフレームを構成している。縦軸にはモジュールの物理番号が並べられている。出力ポート予約済情報の転送方向は、モジュールの物理番号で＃１→＃２→＃３→＃４→＃１→＃２…である。マトリックス内の数字は予約をする次フレーム内のタイムスロットの番号を指す。
【００２６】
図１４に示されているように、物理番号＃１のモジュールは、フレームの先頭（タイムスロットＴＳ１）で次フレームのタイムスロットＴＳ１の予約から開始する。以下同様に、物理番号＃２のモジュールはタイムスロットＴＳ４、物理番号＃３のモジュールはタイムスロットＴＳ３、物理番号＃４のモジュールはタイムスロットＴＳ２の予約から開始する。
【００２７】
【発明が解決しようとする課題】
上述した従来のアルゴリズムを採用する場合には、以下のような問題点がある。
【００２８】
まず第１の問題点は、２本以上全ポート数未満のポートに均一トラヒックを入力した場合のポート間の予約獲得（接続要求処理）割合が不公平となる点である。ＲＲＧＳではパイプライン上で先に予約機会のあるスケジューラの方の予約優先度が高いため、接続機会を獲得する確率が高くなる。従って先に予約機会のあるスケジューラが予約の面で絶対的に有利となる。この特性はモジュールの接続トポロジが固定化されていることに起因しており、この特性のため隣接ポート間の接続機会獲得に関して不公平が生じるという欠点があった。
【００２９】
この点について、上述した図１２、図１４を例として説明する。入力ポート１と２に出力ポート３行きのデータが溜まっており、他にはデータが全くないとする。この場合、スケジューラには入力ポート１から出力ポート３への接続要求と、入力ポート２から出力ポート３への接続要求が毎タイムスロット送出される。ポート間の公平性を考慮するとこの２種類の接続要求は均等に１：１で処理されるべきである。
【００３０】
しかし図１４を参照すると、本スケジューラでは、タイムスロットＴＳ４の予約の時のみ入力ポート２が入力ポート１よりも先に出力ポート３を確保することができ、他のタイムスロットでは入力ポート１が出力ポート３を確保する。従って入力ポート１側が７５％、入力ポート２側が２５％の処理割合となる。一般にＮポート中の隣接２ポートにおいて上記の現象を考えると、パイプラインの上流側と下流側のポートの獲得割合はＮ−１：１の比率となり、ポート数の増大に伴い不公平の度合いが増大する。本問題は隣接する２ポート以上，Ｎ−１以下の場合に発生し、隣接ポート数がｍの場合最上流のポートとそれ以外のポートの獲得割合はＮ−ｍ＋１：１：…：１（項の数はｍ個）となる。
【００３１】
次に、第２の問題点は、同一フレーム内の処理遅延（接続要求に対する接続許可応答までの時間）に関してポート間に不公平が発生する点である。本例では、各モジュールがフレーム内で予約するタイムスロットの開始順序が固定化されていた。そのため、あるモジュールでは最初に予約機会の与えられるタイムスロットがフレーム内の先頭タイムスロットとなり、他のモジュールでは最初に予約機会の与えられるタイムスロットがフレーム内の最終タイムスロットとなっていた。
【００３２】
上述した通り、従来のアルゴリズムでは、パイプライン上で先に予約機会のあるスケジューラの方が予約する確率が高くなるため、先頭に予約機会のあるスケジューラが予約の面で絶対的に有利となる。そのため、各モジュール１０の最初に予約機会のあるタイムスロットの送出時刻が固定化されていると、モジュール間で同タイミングに到着した接続要求に対する予約までの時刻差が不公平となり、結果としてセル送出の遅延時間に不公平が発生するという欠点があった。
【００３３】
この点について、上述した図１２、図１４の場合を例として説明する。フレーム先頭であるタイムスロットＴＳ１における各モジュール１０−１〜１０−４の接続予約するタイムスロットに注目すると、モジュール１０−１はフレーム先頭で次フレーム・タイムスロットＴＳ１の予約が行われる。モジュール１０２はフレーム先頭で次フレーム・タイムスロットＴＳ４の予約が行われる。モジュール１０−１が最も早いスロットを予約することができ、モジュール１０−２は最も遅いタイムスロットを予約することとなり、同タイミングに到着した接続要求に対して常にモジュール１０−１の方が、他のモジュール１０−２〜１０−２より早いタイムスロットを予約することとなる。
【００３４】
本発明は上述した従来技術の欠点を解決するためになされたものであり、その目的は簡単な付加機能によってポート間の不公平を解消することのできるパケットスイッチ及びパケットスイッチにおけるパケットスイッチング方法を提供することである。
【００３５】
【課題を解決するための手段】
本発明によるパケットスイッチは、ネットワークにおけるデータのフローを制御するスイッチであって、
複数の入力ポートと、
複数の出力ポートと、
前記複数の出力ポートのうちの指定出力ポートへデータを送るように、前記複数の入力ポートのうちの特定の入力ポートを予約し、入力ポートと出力ポートとの接続状態を決定するＮ個（Ｎは自然数、以下同じ）の入力ポートスケジューリングモジュールを有するスケジューラと、
を含み、
前記スケジューラは、
タイムスロット単位に、
各入力ポートスケジューリングモジュールが、前段のスケジューリングモジュールから、ある予約タイムスロットの予約状況情報を受信し、
各入力ポートスケジューリングモジュールが、その予約タイムスロットにおける当該入力ポートスケジューリングモジュールからのパケット送出予約可否を決定し、
各入力ポートスケジューリングモジュールが、前段のスケジューリングモジュールから受信した予約状況情報に、自スケジューリングモジュールの予約結果を反映させて、次段のスケジューリングモジュールに送信する手段と、
Ｎ個のタイムスロットを単位とするフレームを定義して、前記フレーム時間内で、前記フレームの次のフレーム中のＮ個のタイムスロットでの予約を行う手段と、
現在のスケジューリングモジュールが、前のスケジューリングモジュールから予約状況情報を受信する手段と、
前記現在のスケジューリングモジュールが、前記複数の出力ポートのうちの１つにアクセスしようとする将来のタイムスロットを予め次のフレーム内の特定のタイムスロットに決定する手段と、
前記複数の出力ポートのうちの１つを前記将来のタイムスロットでの送信用に予約するように選択する手段と、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約済みかどうかを判断する手段と、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約されていない場合には、前記将来のタイムスロットを予約し、前記将来のタイムスロットが予約されたことを示す情報を前記予約状況情報に入れる手段と、
前記予約状況情報を次のスケジューリングモジュールに渡す手段と、
タイムスロットでの予約過程の観点から見た場合、
前記予約過程が、フレームの先頭で同時に開始され、フレーム内で同時にパイプライン処理により進行し、
フレームの末端で同時に完了し、
前記入力ポートスケジューリングモジュールが、フレームの先頭で同時に開始する複数の前記予約過程それぞれにおいて、次のフレーム内の各々異なる予約タイムスロットを対象として処理を開始する手段と、
前記複数のスケジューリングモジュールによる前記予約の順序を変更する予約順序変更手段とを含み、
この変更された順序で前記複数のスケジューリングモジュールそれぞれが各フレーム毎に次のフレームのパケットについて出力すべきポートを予約するようにし、
前記複数のスケジューリングモジュールは他のモジュールとの論理的接続順序に対応した順序で前記予約を実行するものであり、前記予約順序変更手段は前記複数のスケジューリングモジュールの接続トポロジを変更することを特徴とする。
【００３６】
また、前記予約順序変更手段は、前記複数のスケジューリングモジュールの論理的接続状態を変更するようにスイッチング動作するスイッチと、このスイッチのスイッチング動作を制御する制御データを記憶したテーブルとを含む。前記複数のスケジューリングモジュールと前記スイッチ間の物理的接続は、電気的接続か光学的接続とする。
【００３７】
さらに、前記テーブルは、前記複数のスケジューリングモジュールそれぞれの内部に設けられているか、前記複数のスケジューリングモジュールに対して共通に設けられているものとする。そして、前記制御データは、前記複数のスケジューリングモジュール各々がフレーム内の先頭において予約を開始するタイムスロットを各フレーム毎に変更できるように前記スイッチのスイッチング動作を制御するデータであるか、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用頻度を均等とするスケジューリングを実現するデータであるか、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用順序及び使用頻度を変更可能とするスケジューリングを実現するデータであるものとする。
【００３８】
本発明によるパケットスイッチング方法は、Ｎ個の入力ポートスケジューリングモジュールを有するスイッチのスケジューラにて使用する、複数の出力ポートのうちの指定出力ポートへデータを送るように、複数の入力ポートのうちの特定の入力ポートを予約し、入力ポートと出力ポートとの接続状態を決定するパケットスイッチング方法であって、
各入力スケジューリングモジュールが、前段のスケジューリングモジュールからあるタイムスロットの予約状況情報を受信するステップと、
各スケジューリングモジュールが、その予約タイムスロットにおける当該入力ポートスケジューリングモジュールからのパケット送出予約可否を決定するステップと、
各入力スケジューリングモジュールが、前段のスケジューリングモジュールから受信した予約状況情報に、自スケジューリングモジュールの予約結果を反映させて、次段のスケジューリングモジュールに送信するステップと、
を含み、
前記スケジューラは、
現在のスケジューリングモジュールが、前のスケジューリングモジュールから予約状況情報を受信するステップと、
前記現在のスケジューリングモジュールが、前記複数の出力ポートのうちの１つにアクセスしようとする将来のタイムスロットを予め次のフレーム内のタイムスロットに決定するステップと、
前記複数の出力ポートのうちの１つを前記将来のタイムスロットでの送信用に予約するように選択するステップと、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約済みかどうかを判断するステップと、
前記将来のタイムスロットが他のスケジューリングモジュールによって予約されていない場合には、前記将来のタイムスロットを予約し、前記将来のタイムスロットが予約されたことを示す情報を前記予約状況情報に入れるステップと、
前記予約状況情報を次のスケジューリングモジュールに渡すステップと、
を実行し、
タイムスロットでの予約過程の観点から見た場合、
前記予約過程が、フレームの先頭で同時に開始され、フレーム内で同時にパイプライン処理により進行し、
フレームの末端で同時に完了し、
前記入力ポートスケジューリングモジュールが、フレームの先頭で同時に開始する複数の前記予約過程それぞれにおいて、次のフレーム内の各々異なる予約タイムスロットを対象として処理を開始し、
さらに、前記複数のスケジューリングモジュールによる前記予約の順序を変更し、この変更された順序で前記複数のスケジューリングモジュールそれぞれが各フレーム毎に次のフレームのパケットについて出力すべきポートを予約するようにし、
前記複数のスケジューリングモジュールは他のモジュールとの論理的接続順序に対応した順序で前記予約を実行するものであり、前記予約順序の変更においては前記複数のスケジューリングモジュールの接続トポロジを変更することを特徴とする。
【００３９】
また、前記予約の順序の変更においては、前記複数のスケジューリングモジュールの論理的接続状態を変更するようにスイッチング動作するスイッチと、このスイッチのスイッチング動作を制御する制御データを記憶したテーブルとを用いて予約順序を変更することを特徴とする。前記複数のスケジューリングモジュールと前記スイッチ間の物理的接続は、電気的接続か、光学的接続とする。前記テーブルは、前記複数のスケジューリングモジュールそれぞれの内部に設けられているか、前記複数のスケジューリングモジュールに対して共通に設けられているものとする。
【００４０】
前記制御データは、前記複数のスケジューリングモジュール各々がフレーム内の先頭において予約を開始するタイムスロットを各フレーム毎に変更できるように前記スイッチのスイッチング動作を制御するデータであるか、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用頻度を均等とするスケジューリングを実現するデータであるか、前記予約を開始する予約開始スロットの前記複数のスケジューリングモジュールによる使用順序及び使用頻度を変更可能とするスケジューリングを実現するデータであるものとする。
【００４１】
要するに本発明では、入力バッファの構成として仮想出力キューを有し、データスイッチング素子としてクロスバースイッチを有する、入力バッファ型のパケットスイッチを実現しているのである。そして、各モジュールは、入力バッファの各ＶＯＱからの接続要求に対してあるタイムスロットのクロスバースイッチの入力ポートと出力ポートの接続情報を決定する。
【００４２】
前述の通り、ＲＲＧＳ、フレーム化ＲＲＧＳには２つの不公平性が存在する。すなわち、第１に、ＲＲＧＳ、フレーム化ＲＲＧＳ共通の問題で、隣接ポート間における接続予約機会に関する不公平性である（第１の不公平性）。また、第２に、フレーム化ＲＲＧＳについての問題で、ポート間における接続要求に対する接続許可応答までの同一フレーム内の処理遅延に関する不公平性である（第２の不公平性）。
【００４３】
そこで、本発明では、第１の不公平性の解消のために、モジュール間の接続トポロジが変更できる構成をとる。装置としては、モジュールの間で受け渡しをしている出力ポート予約済情報をモジュール外の切替スイッチに入力し、出力先を変更できるようにする。モジュールと切替スイッチは、モジュールが複数タイムスロットの接続許可処理を行っているフレームを単位に同期して動作し、フレーム単位に接続トポロジを変更し全接続トポロジのパタンが出現するように動作する。
【００４４】
接続トポロジが変更されることにより、様々な隣接ポートの組み合わせが出現し、固定化されていた入力ポートに関する優先度がシャッフルされることになり、入力ポートの予約機会に関する不公平性が解消される。また、特定の接続トポロジのパタンのみを用意して使用したり、パタンの適用頻度に重み付けを与えて各パタンの適用割合を変化させることにより、特定の入力ポートもしくは複数の特定の入力ポートに対する優先ポート割当ての頻度を上げる制御を実現することができる。
【００４５】
そして、第２の不公平性の解消のためには、モジュール内の処理フレームでの予約タイムスロットの処理順序を、フレーム単位で変更する。装置としては、各モジュールがフレームに同期して、各モジュール毎に予約タイムスロットの順序パタンを変更する。予約タイムスロットの順序パタンを各モジュールが同期して変更することにより、固定化していた接続要求に対する接続許可応答までの遅延時間の平均値が変更できるようになる。
【００４６】
これにより、平均値を平準化することが実現でき、入力ポートの処理遅延に関する不公平性が解消される。また、特定の予約タイムスロットの順序パタンのみを用意して使用したり、パタンの適用頻度に重み付けを与えて各パタンの適用割合を変化させることにより、特定の入力ポートもしくは特定の複数の入力ポートに対する処理遅延に関する優先制御を実現することができなる。
【００４７】
【発明の実施の形態】
次に、本発明の実施の一形態について図面を参照して説明する。なお、以下の説明において参照する各図においては、他の図と同等部分には同一符号が付されている。
【００４８】
図２を参照すると、本発明の第１の実施の形態としての各モジュールの接続トポロジのタイプが示されている。本形態では第１の問題点を解決する方法を示している。例ではポート数Ｎ＝４の場合を示している。ポート数がＮの場合接続トポロジの数はＮの円順列となり、（Ｎ−１）の階乗（（Ｎ−１）！）となる。スケジューラはこの（Ｎ−１）！分の接続トポロジパタンを用意し、各接続トポロジタイプを均等に発生させてモジュールの接続を変更することにより、隣接モジュール間のポート予約に関する不公平性を解消することができる。本例の場合、（４−１）！＝６通りの接続トポロジタイプが存在する。この６通りの接続トポロジタイプを均等に発生させてモジュールの接続を変更する。
【００４９】
論理的モジュール番号をａからｄまでとし、実モジュール番号を１から４までとする。論理的モジュール番号でａ→ｂ→ｃ→ｄ→ａの順に出力ポート予約済情報の転送をする。６通りの接続トポロジタイプにおける実モジュール番号の割当ては図２に示されているようになる。例えば、Ｔｙｐｅ＃１では物理番号１のモジュールの論理番号はａとなり、物理番号２の論理番号はｂ、物理番号３の論理番号はｃ、物理番号４の論理番号はｄとなる。
【００５０】
図３を参照すると、本発明の第１の実施の形態としての各モジュールの予約（接続許可決定）順序が示されている。縦軸、横軸、マトリックス内の数字の内容は図１４の場合と同様である。例ではポート数Ｎ＝４の場合を示している。複数タイムスロットからフレームを構成しており、１フレームはポート数から４タイムスロットとなる。また複数フレームからスーパーフレームを構成している。フレーム１からフレーム６までの６フレームで前述の接続トポロジタイプ１から６までを適用している。この６フレームをまとめて１つのスーパーフレームが構成される。６通りの接続トポロジタイプを順番にフレーム単位に適用することにより、隣接モジュール間のポート予約に関する不公平性を解消している。なお、各フレームとも論理番号ａの予約開始タイムスロットが１、ｂが４、ｃが３、ｄが２となる接続許可情報予約開始パターンにて例を示している（これをＴｙｐｅ＃Ａの接続許可情報予約開始パタンとする）。
【００５１】
図１を参照すると、本発明の第１の実施例によるスケジューラの構成が示されている。本例においてもポート数Ｎ＝４の場合を示す。スケジューラ１はポート数分のモジュール１０−１〜１０−４と、切替スイッチ３０とから構成されている。
【００５２】
各モジュール１０−ｉには、フレームの先頭を示すフレームパルス（ＦＰ）２１と、スーパーフレームの先頭を示すスーパーフレームパルス（ＳｕｐｅｒＦＰ）２２が入力される。また、各モジュール１０−ｉにはモジュール識別のための物理番号２３が設定される。さらに、各モジュール１０−ｉには、接続要求情報１１と出力ポート予約済情報１３が入力される。
【００５３】
モジュール１０−ｉは、接続要求の調停を行って接続許可（予約）を決定し、接続許可情報１２と更新された出力ポート予約済情報１４を出力する機能を有している。各モジュール１０は出力ポート予約済情報１４、及び切替情報２０を切替スイッチ３０に入力し、切替スイッチ３０は切替情報２０を基に出力ポート予約済情報１３をスイッチングして各モジュール１０に出力する。
【００５４】
ここで、図１中の各モジュール１０−ｉの構成例について図４を参照して説明する。同図を参照すると、モジュール１０−ｉは、アロケータ１５と、接続許可記憶部１６と、接続許可記憶制御部１７と、パタン記憶部１８と、パタン読出制御部１９とを含んで構成されている。
【００５５】
アロケータ１５は、接続要求情報１１と出力ポート予約済情報１３とから、本モジュールで管理する入力ポートに対する出力ポートの接続許可情報１２を決定する。決定のためのアルゴリズムは公知のアルゴリズムを適用する。
【００５６】
接続許可記憶部１６は、アロケータ１５にて決定した接続許可情報１２を使用するタイムスロットの時刻まで記憶しておく機能を有する。この接続許可記憶部１６は、図５に示されているように、接続許可情報を記憶するためのメモリ１６０を含んで構成されている。
【００５７】
接続許可記憶制御部１７は、フレームパルス２１に同期して、パタン記憶部１８からの接続許可情報の予約順序パタンと、モジュール識別のための物理番号２３から、当該モジュールにおける接続許可情報の予約順序パタンとを決定し、タイムスロット毎の接続許可情報１２の書込読出順序を制御する。この接続許可記憶制御部１７は、図５に示されているように、接続許可記憶部１６内のメモリ１６０に対する書込アドレスを生成するための書込アドレスカウンタ１７０と、同じく読出アドレスを生成するための読出アドレスカウンタ１７１と、ロードデータ生成部１７２とを含んで構成されている。
【００５８】
ロードデータ生成部１７２は、接続許可情報予約開始パタンと接続トポロジタイプと物理番号２３から接続許可情報予約開始値を決定する。書込アドレスカウンタ１７０は、接続許可情報予約開始値をロードデータ（Ｌｏａｄ  Ｄａｔａ）とし、フレームパルスをロード入力（Ｌｏａｄ）とする。また、読出アドレスカウンタ１７１は、フレームパルスをロード入力（Ｌｏａｄ）とする。これらのカウンタ１７０及び１７１は、共に、タイムスロット時間を１周期とする図示せぬクロックに応じてカウント動作を行う。そして、そのカウント値を書込アドレス及び読出アドレスとして接続許可記憶部１６内のメモリ１６０に入力し、接続許可情報の書込み及び読出しを行う。
【００５９】
パタン記憶部１８は、接続許可情報１２の出力順序パタンを決定するためのパタン情報を記憶している。このパタン記憶部１８は、図６（Ａ）に示されているように、パタン番号を入力とし、接続トポロジタイプ及び接続許可情報予約開始パタンを出力とするパタンテーブル１８０を含んで構成されている。同図（Ｂ）を参照すると、本発明の第１の実施例によるパタンテーブル１８０の内容が示されている。パタンテーブル１８０には、０から５までの各パタン番号に対応してＴｙｐｅ＃１から＃６の接続トポロジタイプが保持されている。また、本例では各パタン番号に共通してＴｙｐｅ＃Ａの接続許可情報予約開始パタンが保持されている。このような内容のパタンテーブル１８０を設けることにより、パタン記憶部１８は、図３に示されている、接続トポロジパタン毎の接続許可情報の予約順序パタンを出力することができる。
【００６０】
パタン読出制御部１９は、スーパーフレームパルス２２に同期して、フレーム毎に接続許可情報１２の出力順序のパタンの読出を決定し、接続許可記憶制御部１７にパタンを通知する。また、パタン読出制御部１９は、切替スイッチ３０に対して接続トポロジの切替情報２０を通知する。このパタン読出制御部１９は、図７に示されているように、フレームを周期とするクロック（ＣＬＫ）に同期して動作するカウンタ１９０と、接続トポロジタイプを切替情報２０に変換する切替情報変換部１９１とを含んで構成されている。
【００６１】
カウンタ１９０のカウント値は、クロックの入力に応じて増加していき、パタン番号としてパタン記憶部１８に送出される。そして、このカウント値がスーパーフレームパルス２２の遷移タイミングでリセットされることにより、同じパタン番号が繰返しパタン記憶部１８に送出されることになる。また、パタン記憶部１８から送出される接続トポロジタイプが切替情報変換部１９１に入力されると、切替情報変換部１９１はそのタイプに対応する切替情報２０を出力する。
【００６２】
図１中の切替スイッチ３０の内部構成例について図８を参照して説明する。同図に示されているように、切替スイッチ３０は、４つの入力のうちの１つを出力する４：１セレクタ（ＳＥＬ）１０１〜１０４と、セレクタ１０１〜１０４に対応して設けられ対応するセレクタに入力するデータを一時保持するフリップフロップ（以下、Ｆ／Ｆと略す）１００ａ〜１００ｄと、セレクタ１０１〜１０４に対応して設けられ対応するセレクタから出力されるデータを一時保持するＦ／Ｆ１０１ｂ，１０２ｂ，１０３ｂ，１０４ｂと、セレクタ１０１〜１０４の制御端子ＣＴＬに与える切替情報を一時保持するＦ／Ｆ１０１ａ，１０２ａ，１０３ａ，１０４ａとを含んで構成されている。
【００６３】
また、同図中のＦ／Ｆ１００ａ〜１００ｄに入力するデータが印加されるポートＩＳ１ＵＰ〜ポートＩＳ４ＵＰには、上述した出力ポート予約済み情報１４−１〜１４−４が入力される。ポートＩＵＰ１ＳＷ〜ポートＩＵＰ４ＳＷには、上述した切替情報２０−１〜２０−４が入力される。切替情報２０−１〜２０−４は、４：１セレクタ１０１〜１０４が各々異なる入力を選択するような情報として、ポートＩＳ１ＵＰ〜ポートＩＳ４ＵＰに入力される。ポートＯＳ１ＵＰ〜ポートＯＳ４ＵＰからは、Ｆ／Ｆ１０１ｂ，１０２ｂ，１０３ｂ，１０４ｂに保持されている出力ポート予約済み情報１３−１〜１３−４が出力される。
【００６４】
なお、同図中の各Ｆ／Ｆは、ポートＩＳＹＳＣＬＫに印加されているシステムクロックに同期して動作するものとする。また、同図中のポートＩＲＳＴＢに印加されるリセット信号に応答して各Ｆ／Ｆはクリア状態になるものとする。
【００６５】
かかる構成からなる切替スイッチ３０においては、各モジュール１０−１〜１０−４から出力される４種類の出力ポート予約済み情報が４：１セレクタ１０１〜１０４にそれぞれ入力される。そして、これらセレクタ１０１〜１０４それぞれにおいて１種類の出力ポート予約済み情報が選択されて出力される。この選択された出力ポート予約済み情報は、各モジュール１０−１〜１０−４に入力される。
【００６６】
次に、本実施例のスケジューラの動作について、各モジュール１０−ｉが図３の順序に従ってポートの予約処理を行う場合を説明する。
【００６７】
フレームパルス２１は４タイムスロット周期、スーパーフレームパルス２２は６フレーム周期（２４タイムスロット周期）で入力される。図３のフレーム１のタイムスロット１において、図４に示されているモジュール１０−ｉにフレームパルス２１、スーパーフレームパルス２２が入力されると、パタン読出制御部１９は、図２の接続トポロジタイプ１をパタン記憶部１８から接続許可記憶制御部１７にセットする。また、パタン読出制御部１９は接続トポロジタイプ１の切替情報を出力する。各モジュールは自モジュールを識別するための物理番号２３と設定された接続トポロジタイプから現フレームでの接続許可情報の予約順序パタンを選択する。例えば物理番号２３に「１」が設定されているモジュール１０−１は図３の接続許可情報の予約順序にて物理番号１、フレーム１のパタンを選択する。
【００６８】
図１中の切替スイッチ３０はモジュール１０からの切替情報２０に基づいて、各モジュール１０−１〜１０−４からの出力ポート予約済情報の接続を、図２の接続トポロジタイプ１となるように接続する。図１中の各モジュール１０−１〜１０−４は、図３に示されているフレーム１の区間で接続トポロジタイプ１の場合の接続許可情報予約順序に従って予約を実施する。
【００６９】
図３のフレーム１終了時にはフレーム２の４個のタイムスロットにおける接続許可情報１２が確定し、図４中の接続情報記憶部１６に記憶されている。図１中の各モジュール１０−１〜１０−４は、図３のフレーム２のタイムスロット１から４の区間で、決定済の接続許可情報を使用するタイムスロットに応じて図４中の接続情報記憶部１６から接続許可情報１２を読出して、クロスバースイッチと入力ポートに通知し、データのスイッチングを実行する。
【００７０】
上記の接続許可情報の通知と同時に次フレームの接続許可情報の決定を行う。図３のフレーム２のタイムスロット１においてフレームパルス２１が入力されると、図４中のパタン読出制御部１９は、図２の接続トポロジタイプ２をパタン記憶部１８から接続許可記憶制御部１７にセットする。また、パタン読出制御部１９から接続トポロジタイプ２の切替情報を出力する。各モジュール１０−ｉは自モジュールを識別するための物理番号２３と設定された接続トポロジタイプ２から現フレームでの接続許可情報の予約順序パタンを選択する。
【００７１】
図１中の切替スイッチ３０はモジュール１０−１〜１０−４からの切替情報２０に基づいて、各モジュール１０−１〜１０−４からの出力ポート予約済情報の接続を図２の接続トポロジタイプ２となるように接続する。図１中の各モジュール１０−１〜１０−４は、図３のフレーム２の区間で接続トポロジタイプ２の場合の接続許可情報予約順序に従って予約を実施する。以下同様に、接続トポロジの変更と、次フレームの予約と、接続許可情報の通知を行う。タイプ６の接続トポロジによる予約が実行された後には、フレームパルス２１、スーパーフレームパルス２２が入力される。モジュール１０は接続トポロジタイプをタイプ１に戻し、予約処理を継続する。
【００７２】
上述したように、切替スイッチ３０によって各モジュール１０−１〜１０−４間の接続トポロジを変更し、全接続トポロジのパタンを均一に出現させることにより、固定化されていた入力ポートの予約機会に関する優先度がシャッフルされることになり、入力ポートの予約機会に関する不公平性が解消される。
【００７３】
上述した第１の実施例においては、切替スイッチ３０における出力ポート予約済情報のスイッチのための切替情報を各モジュール１０−１〜１０−Ｎから通知する形態について説明した。これにより、各モジュール１０−ｉを同一構成とし、各モジュールにフレームパルス２１及びスーパーフレームパルス２２を入力し、更にモジュール識別のための物理番号２３を外部から入力するだけで、容易にパケットスイッチを構成できる。このように、各モジュール１０−ｉを同一構成とすることができるので、モジュールの量産に適し、製造コストの低減が図れる。なお、この切替情報をある特定のモジュール１０−ｋ（ｋは自然数、かつ、１≦ｋ≦Ｎ）から切替スイッチ３０に通知する形態も考えられる。
【００７４】
また、モジュール１０−ｉにて、接続トポロジパタンを読出す方法としては、各パタンをラウンドロビンにて読み出すことにより均一にパタンを使用する方法がある。その他、適用したい順番に各パタンをパタン記憶部１８に記憶させておくという方法も考えられる。
【００７５】
さらにまた上述した実施例では、モジュール１０−ｉにフレームパルス２１及びスーパーフレームパルス２２を入力し、スーパーフレームパルス２２に同期して各モジュール１０−ｉの接続トポロジタイプの変更順序の同期をとり、フレームパルス２１に同期して接続トポロジタイプ及び接続許可情報の予約順序パタンを更新している。この構成以外に接続トポロジタイプや接続許可情報の予約順序パタンをモジュール１０−ｉの外部から入力する構成も考えられる。つまり、図９に示されているように、接続トポロジタイプや接続許可情報の予約順序パタンを発生する情報発生部１４０を設ければ良い。ただし、同期をとるために、図示せぬ信号線によってフレームパルス２１及びスーパーフレームパルス２２を情報発生部１４０に入力する必要がある。
【００７６】
なお、上述した第１の実施例では全接続トポロジのパタンを均一に発生させたが、逆に特定の接続トポロジパタンの出現頻度を高めることもできる。この場合、特定の入力ポートに対する予約機会に関する優先度を高めることができるという効果がある。
【００７７】
次に、本発明の第２の実施例について説明する。図１０には、本実施例における、各モジュール１０−ｉの予約（接続許可決定）順序が示されている。本形態では第２の問題点を解決する方法を示している。縦軸、横軸、マトリックス内の数字の内容は図１４の場合と同様である。例では同じくポート数Ｎ＝４の場合を示している。複数タイムスロットからフレームを構成しており、１フレームはポート数から４タイムスロットとなる。また複数フレームからスーパーフレームを構成している。ポート数がＮの場合、モジュール１０−ｉがフレーム内の先頭において予約を開始するタイムスロットの場合の数（位相タイプと呼ぶ）はＮ通りとなる。なお、各フレームとも、接続トポロジパタンとしてはＴｙｐｅ＃１のパタンにて例を示している。すなわち、物理番号１のモジュールの論理的モジュール番号がａ、物理番号２のモジュールの論理的モジュール番号がｂ、物理番号３のモジュールの論理的モジュール番号がｃ、物理番号３のモジュールの論理的モジュール番号がｄとなる例を示している。
【００７８】
本例の場合、位相タイプとしてＴｙｐｅ＃ＡからＴｙｐｅ＃Ｄまでの４通りの場合が存在する。例えば、Ｔｙｐｅ＃Ａでは、論理的モジュール番号ａの予約開始タイムスロットが１となり、論理番号ｂの予約開始タイムスロットが４、論理番号ｃの予約開始タイムスロットが３、論理番号ｄの予約開始タイムスロットが２となる。従って、Ｔｙｐｅ＃Ａでは、物理番号１のモジュールの予約開始タイムスロットが１となり、物理番号２の予約タイムスロットが４、物理番号３の予約タイムスロットが３、物理番号４の予約タイムスロットが２となる。フレーム１から４までで前述の位相タイプＡからＤまでを適用している。この４フレームをまとめて１つのスーパーフレームが構成される。４通りの位相タイプを順番にフレーム単位に適用することにより、各モジュール間の遅延に関する不公平性を解消している。
【００７９】
本実施例におけるスケジューラの全体構成は、図１２に示されている構成と同様である。ただし、図１２中の各モジュール１０−１〜１０−４は、図４に示されている構成であるものとする。
【００８０】
各モジュール１０−ｉには、フレームの先頭を示すフレームパルス（ＦＰ）と、スーパーフレームの先頭を示すスーパーフレームパルス（ＳｕｐｅｒＦＰ）が入力される。モジュール１０−ｉの切替情報２０は本実施例では使用しない。
【００８１】
モジュール１０−ｉ内のパタン記憶部１８は、接続許可情報の予約順序のパタンを記憶しておく。図６（Ｃ）を参照すると、本発明の第２の実施例によるパタンテーブルの内容が示されている。パタンテーブル１８０には、０から３までの各パタン番号に対応してＴｙｐｅ＃Ａから＃Ｄの接続許可情報予約開始パタンが保持されている。また、本例では各パタン番号に共通してＴｙｐｅ＃１の接続トポロジタイプが保持されている。このような内容のパタンテーブル１８０を設けることにより、パタン記憶部１８は、図６（Ｃ）に示されているパタンを記憶している。このような内容のパタンテーブル１８０を設けることにより、パタン記憶部１８は、図１０に示されている位相パタン毎の接続許可情報の予約順序パタンを出力することができる。
【００８２】
次に、本発明の第２の実施例のスケジューラの動作について説明する。図１２の各分散スケジューリングモジュール１０−１〜１０−Ｎが図１０に示されている順序に従ってポートの予約処理を行う場合を説明する。なお、フレームパルス２１は４タイムスロット周期、スーパーフレームパルス２２は４フレーム周期（１６タイムスロット周期）で入力されるものとする。
【００８３】
図１０中のフレーム１のタイムスロット１において、図４に示されているモジュール１０−ｉにフレームパルス２１、スーパーフレームパルス２２が入力されると、パタン読出制御部１９は、図１０中の位相タイプＡをパタン記憶部１８から接続許可記憶制御部１７にセットする。各モジュールは自モジュールを識別するための物理番号２３と設定された位相タイプから現フレームでの接続許可情報の予約順序パタンを選択する。例えば物理番号２３に１が設定されているモジュール１０−１は図１０中の接続許可情報の予約順序にて物理番号１、フレーム１のパタンを選択する。
【００８４】
各モジュール１０−ｉは、フレーム１の区間で位相タイプＡの場合のスケジューリング順序に従ってフレーム化ＲＲＧＳによるスケジューリングを実施する。図１０中のフレーム１終了時にはフレーム２の４個のタイムスロットにおける接続許可情報が確定し、図４中の接続情報記憶部１６に記憶されている。各モジュールは、フレーム２のタイムスロット１から４にかけて決定済の接続許可情報をタイムスロットに応じて図４中の接続情報記憶部１６から接続許可情報１２を読出して、クロスバースイッチと入力ポートに通知し、データ転送を実行する。
【００８５】
上記接続許可情報の通知と同時に次フレームの接続許可情報の決定を行う。図１０中のフレーム２のタイムスロット１においてフレームパルス２１が入力されると、図４中のパタン読出制御部１９は、図１０中の位相タイプＢをパタン記憶部１８から接続許可記憶制御部１７にセットする。各モジュールは自モジュールを識別するための物理番号２３と設定された位相タイプＢから現フレームでの接続許可情報の予約順序パタンを選択する。
【００８６】
各モジュール１０−１〜１０−４はフレーム２の区間で位相タイプＢの場合の接続許可情報予約順序に従って予約を開始する。
【００８７】
以下同様に、位相タイプの変更と、次フレームの予約と、接続許可情報の通知を行う。タイプＤの位相タイプによる予約が実行された後には、フレームパルス２１、スーパーフレームパルス２２が入力される。モジュール１０は位相タイプをタイプＡに戻し、予約処理を継続する。
【００８８】
以上のように、各モジュール１０−１〜１０−Ｎ間の予約開始タイムスロットの位相パタンを変更し、全位相パタンが均一に出現することにより、固定化されていた入力ポートの平均遅延がシャッフルされることになる。よって、入力ポートの平均遅延に関する不公平性が解消される。
【００８９】
入力ポートの平均遅延に関する不公平性の解消には、各モジュール１０−１〜１０−Ｎの接続トポロジを変更する必要がないので、第１の実施例のようなモジュール１０−ｉ外で出力ポート予約済情報をスイッチする機能は必要ない。従って外部に回路を追加しなくても、第１の実施例と同じモジュール１０−ｉの構成で実現できる。
【００９０】
第１の実施例の場合と同様に、位相パタンの読出に関して各パタンをラウンドロビンにて読出すことにより均一にパタンを使用する方法がある。その他、適用したい順番に各パタンをパタン記憶部１８に記憶させておくという方法も考えられる。
【００９１】
また、上述の実施例では各モジュール１０−ｉにフレームパルス２１及びスーパーフレームパルス２２を入力し、スーパーフレームパルス２２に同期して各モジュール１０−ｉの位相タイプの変更順序の同期をとり、フレームパルス２１に同期して位相タイプ及び接続許可情報の予約順序パタンを更新していた。第１の実施例と同様に、本構成以外に位相タイプや接続許可情報の予約順序パタンをモジュール１０−ｉの外部から入力する方法も考えられる。
【００９２】
更に、上記実施の形態では全位相パタンを均一に発生させたが、逆に特定の位相パタンの出現頻度を高めて、特定の入力ポートの平均遅延を小さくすることもできる。
【００９３】
なお、第１の実施例の構成では、平均遅延の公平化と入力ポートの予約機会に関する公平化を同時に実現することができる。
【００９４】
モジュール１０−ｉの接続トポロジは、各モジュール１０−１〜１０−Ｎ間の予約開始タイムスロットの位相を固定にした場合に相当する。図３及び図１０を例にとって説明すると、ポート数Ｎ＝４の場合、図３に示されている６通りの各モジュールの予約順序は、図１０に示されている位相タイプＡで接続変更を実施した場合に対応する。従って図１０のタイプＢ，Ｃ，Ｄの場合に接続変更を実施したパタンを考慮すると、全部で２４通りのパタンが存在することとなる。これはスケジューラ１におけるモジュールの順列に他ならない。すなわち、モジュールの接続トポロジタイプと予約開始タイムスロットの位相タイプとの直積（掛け算）がモジュールの順列となる。
【００９５】
第１の実施例の構成で、接続トポロジパタンを記憶しているパタン記憶部１８に接続トポロジパタン（６通り）に代わってモジュールの順列（２４通り）を記憶し、スーパーフレームパルス２２を２４フレーム（９６タイムスロット）の整数倍周期で入力して、パタン読出制御部１９が２４通りの読出を実行するように変更することによって、入力ポートの予約機会に関する公平化と平均遅延の公平化とを同時に解消できる。図６（Ｄ）を参照すると、上述の本発明の他の実施例によるパタンテーブル１８０の内容が示されている。パタンテーブル１８０には、０から２３までの各パタン番号に対応して、Ｔｙｐｅ＃１から＃６の接続トポロジタイプとＴｙｐｅ＃Ａから＃Ｄの接続許可情報予約開始パタンの全組み合わせが保持されている。
【００９６】
【発明の効果】
以上説明したように本発明は、接続トポロジを変更することにより、様々な隣接ポートの組み合わせが出現し、固定化されていた入力ポートに関する優先度がシャッフルされることになり、入力ポートの予約機会に関する不公平性が解消できるという効果がある。
【００９７】
また、各モジュール内の処理フレームでの予約タイムスロットの処理順序を、フレーム単位で変更することにより、固定化していた接続要求に対する接続許可応答までの遅延時間の平均値が変更できるようになり、平均値を平準化することが実現できて、入力ポートの処理遅延に関する不公平性が解消できるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１の実施例によるパケットスイッチの構成を示すブロック図である。
【図２】本発明の第１の実施例によるパケットスイッチの各モジュールの接続トポロジのタイプを示す図である。
【図３】第１の実施例の各モジュールの予約（接続許可決定）順序を示す図である。
【図４】図１中の各モジュールの構成例を示すブロック図である。
【図５】図４中の接続許可記憶部及び接続許可記憶制御部の内部構成例を示す図である。
【図６】図（Ａ）は図４中のパタン記憶部の構成例を示す図、図（Ｂ）は本発明の第１の実施例による図（Ａ）中のパタンテーブルの内容例を示す図、図（Ｃ）は本発明の第２の実施例による図（Ａ）中のパタンテーブルの内容例を示す図、図（Ｄ）は本発明の他の実施例による図（Ａ）中のパタンテーブルの内容例を示す図である。
【図７】図４中のパタン読出制御部の内部構成例を示す図である。
【図８】図１中の切替スイッチの内部構成例を示す図である。
【図９】本発明の第２の実施例によるパケットスイッチの構成を示すブロック図である。
【図１０】本発明の第２の実施例によるパケットスイッチの各モジュールの予約（接続許可決定）順序を示す図である。
【図１１】ＶＯＱ使用の入力バッファ型パケットスイッチの一般的な構成を示す図である。
【図１２】一般的なパケットスイッチの構成を示す図である。
【図１３】フレーム化ＲＲＧＳの接続許可情報の決定方法を示す図である。
【図１４】従来のフレーム化ＲＲＧＳにおける各モジュールの予約（接続許可決定）順序を示す図である。
【符号の説明】
１０−１〜１０−４  モジュール
１５  アロケータ
１６  接続許可記憶部
１７  接続許可記憶制御部
１８  パタン記憶部
１９  パタン読出制御部
３０  切替スイッチ
【図１】
0003565121.tif 000002
【図２】
0003565121.tif 000003
【図３】
0003565121.tif 000004
【図４】
0003565121.tif 000005
【図５】
0003565121.tif 000006
【図６】
0003565121.tif 000007
【図７】
0003565121.tif 000008
【図８】
0003565121.tif 000009
【図９】
0003565121.tif 000010
【図１０】
0003565121.tif 000011
【図１１】
0003565121.tif 000012
【図１２】
0003565121.tif 000013
【図１３】
0003565121.tif 000014
【図１４】
0003565121.tif 000015