(57)【特許請求の範囲】
【請求項１】
データフレームを一時的に蓄積するキューを複数のグループに分け、各グループにおいて、当該グループの属するキューを優先等級が互いに等しいキューごとにサブグループに分け、各キューにおいて、それぞれ一段目の伝送レート制御を行い、各サブグループにおいて、当該サブグループに属するキューどうしのデータフレームを送出する優先順位を決定し、前記グループごとに、帯域制御回路により二段目の伝送レート制御を行うデータ転送方法であって、
前記帯域制御回路ごとの伝送レート制御における伝送レートの配分比率に応じて、一連のスロット番号に前記グループを割り付け、
前記スロット番号順に循環的に、各スロット番号に一つずつ対応する前記優先順位を決定するための回送テーブルを生成し、
前記キューごとに、キュー情報テーブルを生成しておき、
前記キュー情報テーブルに、当該キューからのデータフレームの送信の可否を示すフラグを設け、
当該キューにデータフレームが蓄積されており、かつ、当該データフレームの送出レートが、当該キューの送出レート制御によるレート以下である場合に、前記フラグは送信可を示し、
前記回送テーブルを、全てのキューへ順次に転送し、
前記回送テーブルに対応するスロット番号に割り付けられたグループに属するキューにおいてのみ、当該回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較し、
前記フラグが送信可を示すキューにおいてのみ、前記回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較し、
前記回送テーブルが転送されてきたキューの優先順位が、当該回送テーブルに次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、前記次送出キューを当該キューに更新し、
全てのキューを転送した回送テーブルに次送出キューとして登録されているキューから、次のデータフレームを送出する
ことを特徴とするデータ転送方法。
【請求項２】
前記スロット番号に割り付けられたグループを示す番号を第１テーブルに登録しておき、
前記回送テーブルの生成にあたり、前記第１テーブルにおいてスロット番号に割り付けられたグループ番号を前記回送テーブルに登録する
ことを特徴とする請求項１記載のデータ転送方法。
【請求項３】
前記回送テーブルに、次送出キューの属するサブグループを登録し、
前記回送テーブルが転送されてきたキューの属するサブグループと、前記次送出キューの属するサブグループとが同一である場合に、登録されている次送出キューと当該キューとの優先順位を比較する
ことを特徴とする請求項１又は２記載のデータ転送方法。
【請求項４】
前記グループごとに、当該グループに属するキューのうち、最低帯域保証が予約されたキューを第１テーブルに登録しておき、
前記回送テーブルの生成にあたり、前記第１テーブルに登録された最低帯域保証キューを、前記回送テーブルに登録し、
前記優先順位の比較にあたり、回送テーブルが転送されてきたキューと、回送テーブルに登録されている最低帯域保証キューとが一致した場合に、当該キュー番号を次送出キューとして、当該回送テーブルに登録する
ことを特徴とする請求項１〜３のいずれかに記載のデータ転送方法。
【請求項５】
同一サブグループに属する各キューに通し番号を付与し、ラウンドロビンにおいて前記通し番号順にデータフレームを順次に送出するアルゴリズムを与えておき、
各グループについて、前記サブグループごとに、当該サブグループに属するキューのうち、最後にデータフレームを送出した最終送出キューの通し番号を第２テーブルに登録しておき、
前記回送テーブルの生成にあたり、前記第２テーブルに登録されている最終送出キューの通り番号のうち、当該回送テーブルに対応するグループに属する各サブグループの最終送出キューの通し番号を当該回送テーブルに登録し、
前記回送テーブルに登録されている次送出キューの通し番号が、前記最終送出キューの通し番号よりも小さく、かつ、当該最終送出キューの通し番号が、当該回送テーブルが転送されてきたキューの通し番号よりも小さい場合に、前記次送出キューを当該キューに更新し、
第２テーブルにおいて、前記次送出キューが更新されたサブグループの最終送出キューの通し番号を更新する
ことを特徴とする請求項１〜４のいずれかに記載のデータ転送方法。
【請求項６】
データフレームを一時的に蓄積する複数のキューを備え、
前記キューは、複数のグループに分けられ、各グループにおいて、当該グループの属するキューを優先等級が互いに等しいキューごとにサブグループに分けられており、各キューにおいて、それぞれ一段目の伝送レート制御を行い、
各サブグループにおいて、当該サブグループに属するキューどうしのデータフレームを送出する優先順位を決定する優先順位決定手段と、
前記グループごとに、二段目の伝送レート制御を行う帯域制御回路とを備えたデータ転送装置であって、
前記優先順位を決定するための全てのキューへ順次に転送される回送テーブルを生成し、前記帯域制御回路ごとの伝送レート制御における伝送レートの配分比率に応じて、一連のスロット番号に前記グループを割り付け、前記スロット番号順に循環的に、各スロット番号に一つずつ対応する回送テーブルを生成する回送テーブル生成部と、
前記キューごとに、キュー情報テーブルを生成し、各キュー情報テーブルに、当該キューからのデータフレームの送信の可否を示すフラグを設け、当該キューにデータフレームが蓄積されており、かつ、当該データフレームの送出レートが、当該キューの送出レート制御によるレート以下である場合に、送信可を示す前記フラグを設けるキュー情報テーブル生成部と、
前記回送テーブルが全てのキューへ順次に転送されると、当該回送テーブルに対応するスロット番号に割り付けられたグループに属するキューにおいてのみ、当該回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較し、前記フラグが送信可を示すキューにおいてのみ、前記回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較し、前記回送テーブルが転送されてきたキューの優先順位が、当該回送テーブルに次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、前記次送出キューを当該キューに更新し、全てのキューを転送した回送テーブルに次送出キューとして登録されているキューから、次のデータフレームを送出させる調停手段と、を有することを特徴とするデータ転送装置。
【請求項７】
データフレームを一時的に蓄積するキューを複数のグループに分け、各グループにおいて、当該グループの属するキューを優先等級が互いに等しいキューごとにサブグループに分け、各キューにおいて、それぞれ一段目の伝送レート制御を行い、各サブグループにおいて、当該サブグループに属するキューどうしのデータフレームを送出する優先順位を決定し、前記グループごとに、帯域制御回路により二段目の伝送レート制御を行うデータ転送方法のプログラムであって、
前記帯域制御回路ごとの伝送レート制御における伝送レートの配分比率に応じて、一連のスロット番号に前記グループを割り付ける処理と、
前記スロット番号順に循環的に、各スロット番号に一つずつ対応する前記優先順位を決定するための回送テーブルを生成する処理と、
前記キューごとに、キュー情報テーブルを生成する処理と、
前記キュー情報テーブルに、当該キューからのデータフレームの送信の可否を示すフラグを設け、当該キューにデータフレームが蓄積されており、かつ、当該データフレームの送出レートが、当該キューの送出レート制御によるレート以下である場合に、送信可を示す前記フラグを設ける処理と、
前記回送テーブルを、全てのキューへ順次に転送する処理と、
前記回送テーブルに対応するスロット番号に割り付けられたグループに属するキューにおいてのみ、当該回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較する処理と、
前記フラグが送信可を示すキューにおいてのみ、前記回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較する処理と、
前記回送テーブルが転送されてきたキューの優先順位が、当該回送テーブルに次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、前記次送出キューを当該キューに更新する処理と、
全てのキューを転送した回送テーブルに次送出キューとして登録されているキューから、次のデータフレームを送出する処理と
をコンピュータに実行させることを特徴とするデータ転送方法のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信装置等におけるデータ転送技術に関し、特に、複数のキューどうしにおいてデータフレーム送出優先順位を決定するデータ転送装置、データ転送方法及びその方法を実現するためのプログラムに関する。
【０００２】
【従来の技術】
まず、図７を参照して、ＡＴＭ通信等に利用されるデータ交換機の一般的な構成例について説明する。
図７に示すように、データ交換機１００は、複数の入力バッファカード１１０、スイッチコア部１２０、及び、複数の出力バッファカード１３０により構成されている。
【０００３】
データ交換機１００に受信されたデータフレーム（Data frame）は、入力バッファカード１１０の入力バッファキュー１１１を通過した後、スイッチコア部１２０によってスイッチングされ、いずれかの出力バッファカード１３０へと送られる。各出力バッファカード１３０には、それぞれ複数の出力バッファキュー（以下、単に「キュー（Queue）」とも称する。）１３１が設けられている。そして、出力バッファカード１３０へ送られたデータフレームは、その特性に応じて、いずれかのキュー１３１に割り付けられる。
【０００４】
各キュー１３１には、それぞれ、最低保障帯域や優先順位といったデータフレームの送出条件が定められている。このため、データフレームは、それら条件を満たしながら送出レート制御（シェーピング：shaping）され、データ交換機１００から送信される。
【０００５】
そして、各キューの優先順位や最低保障帯域を保証した上で、効率よくデータフレームのシェーピングを行うため、制御部１４０により、例えば、複数のキューにそれぞれ蓄積されたデータフレームについて、二段階でシェーピングを行ったり、さらに、個々のキューについて、優先順位（Priority）と最低保障帯域（Minimum guaranteed rate）を定義したりしている。
【０００６】
ここで、図８を参照して、二段階のシェーピングについて簡単に説明する。
図８に示すように、キューに蓄積されたデータフレームは、先ず、各キューにおいてそれぞれシェーピング（以下、「キューシェーピング」と称する。）される。すなわち、データフレームの送出レートが、そのキューについて設定された最大送出レート（シェーピングレート）よりも大きい場合に、データフレームの送出に制限がかけられる。
【０００７】
次に、帯域制御回路（スケジューラ：scheduler）により、他のキューのデータフレームと一緒に、再度シェーピング（以下、「スケジューラシェーピング」と称する。）される。
同一のスケジューラによりスケジューラシェーピングされる部分をスケジューラグループ（scheduler group）と称する。図９に、一つのスケジューラグループの拡大図を示す。
【０００８】
各スケジューラグループに含まれるキューは、優先等級別に複数のグループ（以下、「キューグループ」と称する。）１０に分けられている。そして、キューグループ１０ごとにラウンドロビン３が設けられている。各ラウンドロビン３は、キューグループ１０ごとに、次にデータフレームを送出すべきキューを決定する。
なお、この決定の際には、個々のキューに定義されている最低保証帯域を保証して、各キュー間のデータフレーム送信の優先順位を決定する必要がある。
【０００９】
そして、各キューグループ１０から送出されたデータフレーム１は、固定的な優先順位制御（Static priority）により優先順位が決定されるとともに、スケジューラシェーピングされる。
【００１０】
【発明が解決しようとする課題】
しかしながら、上述した従来の２段階のシェーピングにおいては、各キュー間のデータフレーム送信の優先順位を決定する際に、次の三つの問題点があった。
第一の問題点は、トラフィックシェーピングの組合せの変化に応じて、個々のラウンドロビンの所属するキューグループを再構成する必要がある点である。
また、第二の問題点は、個々のキューに優先順位や最低保障帯域が定義されている場合、その特定に応じたキューを個別に用意するか、若しくは、それら特性を全て有するキューを用意して機能を切り替える等して対応する必要がある点である。
また、第三の問題点は、従来の回路では、個々のキューやラウンドロビンが、トラフィック優先順位や最低保障帯域に対応する場合、比較的大規模な回路が必要となるため、キューの数を増加させることが困難である点である。
【００１１】
本発明は、上記の問題を解決すべくなされたものであり、個々のキューに定義されている最低保証帯域を保証しつつ、複数のキュー間のデータフレーム送出優先順位を容易かつ効率的に決定できる技術の提供を目的とする。
【００１２】
【課題を解決するための手段】
この目的の達成を図るため、本発明の請求項１に係るデータ転送方法によれば、データフレームを一時的に蓄積するキューを複数のグループに分け、各グループにおいて、当該グループの属するキューを優先等級が互いに等しいキューごとにサブグループに分け、各キューにおいて、それぞれ一段目の伝送レート制御を行い、各サブグループにおいて、当該サブグループに属するキューどうしのデータフレームを送出する優先順位を決定し、前記グループごとに、帯域制御回路により二段目の伝送レート制御を行うデータ転送方法であって、前記優先順位を決定するための回送テーブルを、全てのキューへ順次に転送し、前記回送テーブルが転送されてきたキューの優先順位が、当該回送テーブルに次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、前記次送出キューを当該キューに更新し、全てのキューを転送した回送テーブルに次送出キューとして登録されているキューから、次のデータフレームを送出する方法としてある。
【００１３】
このように、本発明のデータ転送方法によれば、回送テーブルを各キューに順次に転送して次送出キューを決定する。すなわち、各キューにおいてパイプライン状に回送テーブルを処理する。このため、トラフィックシェーピングの組合せの変化に応じて、個々のサブグループを再構成する必要がない。また、個々のキューの回路規模を小さくすることができる。このため、キューの数を容易に増加させることができる。
【００１４】
特に、本発明では、帯域制御回路ごとの伝送レート制御における伝送レートの配分比率に応じて、一連のスロット番号に前記グループを割り付け、前記スロット番号順に循環的に、各スロット番号に一つずつ対応する前記回送テーブルを生成し、前記回送テーブルに対応するスロット番号に割り付けられたグループに属するキューにおいてのみ、当該回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較する方法としてある。
これにより、各帯域制御回路（スケジューラ）のシェーピングレートの配分比率に応じたトラフィックシェーピングを容易に行うことができる。
【００１５】
また、請求項２記載の発明によれば、スロット番号に割り付けられたグループを示す番号を第１テーブルに登録しておき、前記回送テーブルの生成にあたり、前記第１テーブルにおいてスロット番号に割り付けられたグループ番号を前記回送テーブルに登録する方法としてある。
これにより、第１テーブルを参照することにより、一層容易にシェーピングレートの配分比率に応じたトラフィックシェーピングを容易に行うことができる。
【００１６】
また、請求項３記載の発明によれば、回送テーブルに、次送出キューの属するサブグループを登録し、前記回送テーブルが転送されてきたキューの属するサブグループと、前記次送出キューの属するサブグループとが同一である場合に、登録されている次送出キューと当該キューとの優先順位を比較する方法としてある。
これにより、サブグループごとに優先等級が設定されている場合にも、容易に優先順位を決定することができる。
【００１７】
また、請求項４記載の発明によれば、グループごとに、当該グループに属するキューのうち、最低帯域保証が予約されたキューを第１テーブルに登録しておき、前記回送テーブルの生成にあたり、前記第１テーブルに登録された最低帯域保証キューを、前記回送テーブルに登録し、前記優先順位の比較にあたり、回送テーブルが転送されてきたキューと、回送テーブルに登録されている最低帯域保証キューとが一致した場合に、当該キュー番号を次送出キューとして、当該回送テーブルに登録する方法としてある。
【００１８】
これにより、最低保障帯域が定義されている場合であっても、その情報を第１テーブルに登録することにより容易に対応することができる。このため、優先順位や最低帯域保証ごとにキューを個別に用意したり、それら特性を全て有するキューを用意して機能を切り替えたりする必要がない。
【００１９】
また、請求項５記載の発明によれば、同一サブグループに属する各キューに通し番号を付与し、ラウンドロビンにおいて前記通し番号順にデータフレームを順次に送出するアルゴリズムを与えておき、各グループについて、前記サブグループごとに、当該サブグループに属するキューのうち、最後にデータフレームを送出した最終送出キューの通し番号を第２テーブルに登録しておき、前記回送テーブルの生成にあたり、前記第２テーブルに登録されている最終送出キューの通り番号のうち、当該回送テーブルに対応するグループに属する各サブグループの最終送出キューの通し番号を当該回送テーブルに登録し、前記回送テーブルに登録されている次送出キューの通し番号が、前記最終送出キューの通し番号よりも小さく、かつ、当該最終送出キューの通し番号が、当該回送テーブルが転送されてきたキューの通し番号よりも小さい場合に、前記次送出キューを当該キューに更新し、第２テーブルにおいて、前記次送出キューが更新されたサブグループの最終送出キューの通し番号を更新する方法としてある。
これにより、最終送出キューの通し番号に基づいて、容易に優先順位の比較を行うことができる。
【００２０】
特に、本発明では、キューごとに、キュー情報テーブルを生成しておき、前記キュー情報テーブルに、当該キューからのデータフレームの送信の可否を示すフラグを設け、当該キューにデータフレームが蓄積されており、かつ、当該データフレームの送出レートが、当該キューの送出レート制御によるレート以下である場合に、前記フラグは送信可を示し前記フラグが送信可を示すキューにおいてのみ、前記回送テーブルに登録されている次送出キューと当該キューとの優先順位を比較する方法としてある。
これにより、より効率的に優先順位を決定することができる。
【００２１】
また、本発明の請求項６に係るデータ転送装置によれば、データフレームを一時的に蓄積する複数のキューを備え、前記キューは、複数のグループに分けられ、各グループにおいて、当該グループの属するキューを優先等級が互いに等しいキューごとにサブグループに分けられており、各キューにおいて、それぞれ一段目の伝送レート制御を行い、各サブグループにおいて、当該サブグループに属するキューどうしのデータフレームを送出する優先順位を決定する優先順位決定手段と、前記グループごとに、二段目の伝送レート制御を行う帯域制御回路とを備えたデータ転送装置であって、前記優先順位を決定するための全てのキューへ順次に転送される回送テーブルを生成する回送テーブル生成部を備え、前記キューは、前記回送テーブルが転送されてきたキューの優先順位が、当該回送テーブルに次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、前記次送出キューを当該キューに更新し、全てのキューを転送した回送テーブルに次送出キューとして登録されているキューから、次のデータフレームを送出させる調停手段とを有する構成としてある。
【００２２】
このように、本発明のデータ転送装置によれば、回送テーブルを各キューに順次に転送して次送出キューを決定する。すなわち、各キューにおいてパイプライン状に回送テーブルを処理する。このため、トラフィックシェーピングの組合せの変化に応じて、個々のサブグループを再構成する必要がない。また、個々のキューの回路規模を小さくすることができる。このため、キューの数を容易に増加させることができる。
【００２３】
また、本発明の請求項７に係るデータ転送方法のプログラムによれば、データフレームを一時的に蓄積するキューを複数のグループに分け、各グループにおいて、当該グループの属するキューを優先等級が互いに等しいキューごとにサブグループに分け、各キューにおいて、それぞれ一段目の伝送レート制御を行い、各サブグループにおいて、当該サブグループに属するキューどうしのデータフレームを送出する優先順位を決定し、前記グループごとに、帯域制御回路により二段目の伝送レート制御を行うデータ転送方法のプログラムであって、前記優先順位を決定するための回送テーブルを、全てのキューへ順次に転送する処理と、前記回送テーブルが転送されてきたキューの優先順位が、当該回送テーブルに次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、前記次送出キューを当該キューに更新する処理と、全てのキューを転送した回送テーブルに次送出キューとして登録されているキューから、次のデータフレームを送出する処理とをコンピュータに実行させる。
【００２４】
このように、本発明のデータ転送方法のプログラムによれば、コンピュータの各構成要素へ所定の指令を送ることにより、コンピュータにデータ転送機能を実現させることができる。すなわち、データ転送機能は、本発明のプログラムとコンピュータとが協働して実現される。
【００２５】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を参照して説明する。
なお、以下の各実施形態におけるデータ転送における優先順位の決定処理は、プログラムに制御されたコンピュータにより実行される。このプログラムは、例えば、記録媒体により提供される。記録媒体としては、例えば、磁気ディスク、半導体メモリ、その他の任意の、コンピュータで読み取り可能なものを使用することができる。また、記録媒体に記録されたプログラムは、通信回線を介してコンピュータに読込ませることもできる。
【００２６】
本実施形態のデータ転送装置の構成は、図７に示した従来のデータ交換機１００の構成と基本的に同じであり、データフレームを一時的に蓄積する複数のキュー（出力バッファキュー）１３１を備えている。また、図８及び図９に示したように、キュー１３１は、Ｍ個（Ｍは２以上の整数）のグループ（スケジューラシェーピンググループ）１０に分けられている。さらに、各グループ１０において、当該グループの属するキューは、優先等級が互いに等しいキューごとにＰ個（Ｐは２以上の整数）のサブグループ（キューグループ）２０に分けられている。
【００２７】
そして、各キュー１３１において、それぞれ一段目の伝送レート制御（キューシェーピング）が行われる。続いて、ラウンドロビン３によって、サブグループ２０ごとに、当該サブグループに属するキュー間のデータフレーム１を送出する優先順位が決定される。ここでは、同一サブグループに属する各キューに通し番号（１〜Ｐ）が付与されており、ラウンドロビン３には、通し番号順に各キューからデータフレームを順次に送出するアルゴリズムが与えられている。
【００２８】
さらに、グループ１０ごとに、固定的な優先順位が決定されるとともに、帯域制御回路（スケジューラ）により二段目の伝送レート制御（スケジューラシェーピング）が行われる。
ただし、本実施形態では、図７に示した制御装置１４０による、キュー間でのデータフレームの送出の優先順位を決定する機能が従来のものと異なっている。
【００２９】
図１を参照して、本実施形態における優先順位の決定方法について説明する。
本実施形態では、第１テーブル４及び第２テーブル５に基づいて、回送テーブル生成部６が、優先順位を決定するための回送テーブル７を生成する。
なお、第１テーブル４、第２テーブル５及び回送テーブル７の具体的な内容については後述する。
【００３０】
そして、回送テーブル７は、全てのキュー１３１からなるキューチェーン３０を順次に転送される。そして、回送テーブル７が転送されてきたキューの優先順位が、当該回送テーブル７に次にデータフレームを送出する次送出キューとして登録されているキューの優先順位よりも高い場合に、次送出キューを当該キューに更新する。
【００３１】
なお、キューチェーン３０には、通常、同時に複数の回送テーブル７が転送される。例えば、図２に示す例では、回送テーブルＡが第ｎキューから第ｎ＋１キューへ転送された後、第ｎキューへ回送テーブルＢが転送されている。この場合、第ｎ＋１キューにおいて回送テーブルＡについて優先度が比較されているときに、第ｎキューにおいて回送テーブルＢについて優先度が比較されることになる。さらに、第ｎ＋２キュー、第ｎ＋１キュー及び第ｎキューにおいて、それぞれ回送テーブルＡ、回送テーブルＢ及び回送テーブルＣについて優先度比較が行われることもある。
なお、図２では、隣接したキューで同時に優先度比較が行われている例について説明したが、隣接していない複数のキューで同時に優先度比較が行われてもよい。
【００３２】
このように、パイプライン方式で優先度比較を行うので、個々のキューにおいて、それぞれ簡単なアルゴリズムを組合せた処理により優先順位を決定することができるとともに、個々のキューの回路構成を簡単にすることができる。
【００３３】
そして、アービタ８は、全てのキューを転送してきた回送テーブル７に次送出キューとして登録されているキューに対して、次のデータフレームを送出させる送信命令を出力する。これにより、優先順位の最も高いキューから次のデータフレームが送出される。
【００３４】
また、次のデータフレームが送出されることにより、後述するように第２テーブルの登録内容を変更する必要が生じる場合があるので、アービタ８は、第２テーブルへ更新情報を出力する。これにより、第２テーブルの登録内容を最新の状態を反映したものに更新することができる。
【００３５】
次に、データ転送方法における優先順位決定方法についてより詳細に説明する。
まず、図３に示すフレームスロット９について説明する。フレームスロット９は、データフレームを送出するためのループ状の時間スロットであり、１〜Ｎまでのスロットに分割されている。そして、スケジューラ２ごと、すなわち、スケジューラグループ１０ごとのシェーピングレートの配分比率に応じて、一連のスロット番号にスケジューラグループが割り付けられている。この割付けにより、各スロットのタイミングごとに、どのスケジューラグループ１０からデータフレームを送出すべきかが指定される。
【００３６】
例えば、図４に示すように、キュー群が３つのスケジューラグループ１０に分けられており、第１〜第３スケジューラグループ１０それぞれのシェーピングレートを、それぞれ全レートの４０％、１０％及び２０％とし、スロット数をＮ＝２０とした場合について説明する。
この場合、一連のスロット番号のうち８つのスロット番号に、第１スケジューラグループが割り付けられる。また、２つのスロット番号に、第２スケジューラグループが割り付けられる。また、４つのスロット番号に、第３スケジューラグループが割り付けられる。
【００３７】
なお、図４では、各スロットに、スケジューラグループの番号を割り付けている。ただし、一連のスロット番号のうち１２個のスロット番号には、未使用セルレートとしてゼロが割り付けられる。また、スロット番号上の同一グループの割付の間隔は、任意好適なアルゴリズムにより設定するとよい。
【００３８】
そして、スロット番号順に、各スロット番号に対応する回送テーブル７が一つずつ生成される。そして、最終のスロット番号「Ｎ」に対応する回送テーブル７が生成された次には、先頭のスロット番号「１」に対応する回送テーブル７が循環的に生成される。
【００３９】
本実施形態では、スロット番号に割り付けられたグループを示す番号を、下記の表１に示すように第１テーブル（トランスミッションテーブル）に登録しておく。
また、第１テーブルには、スロット番号ごとに、そのスロット番号に対応するスケジューラグループ１０中で最低保障帯域が設定されているキューが最低保証帯域予約キュー番号として登録されている。これにより、容易に最低保障帯域を予め確保することができる。
【００４０】
例えば、下記の表１に示す例では、スロット番号「１」に、スケジューラグループ番号「ｘ」が割り付けられており、さらに、スケジューラグループ「ｘ」中の最低帯域保証予約キュー番号として「ｘｘｘ」が登録されている。また、スロット番号「２」には、スケジューラグループが割り付けられていないので、スケジューラグループ番号の欄には、未使用であることを示す「０」が登録されている。また、スロット番号「Ｎ」には、スケジューラグループ「ｙ」が割り付けられているが、スケジューラグループ「ｙ」中には、最低帯域保証されたキューが存在しないので、最低帯域保証予約キュー番号の欄には、最低保証予約キューの割当てがないことを示す「０」が登録されている。
【００４１】
【表１】
0003698079.tif 000002
【００４２】
また、本実施形態では、各スケジューラグループ１０について、キューグループ２０ごとに、当該キューグループ２０に属するキューのうち、最後にデータフレームを送出した最終送出キューの通し番号を、下記の表２に示すように第２テーブルに登録しておく。
【００４３】
【表２】
0003698079.tif 000003
【００４４】
そして、スロット番号ごとに、上記の第１テーブル及び第２テーブルから読み出した情報に基づいて、回送テーブル生成部６により回送テーブルが生成される。下記の表３に示すように、回送テーブルは、第１テーブルから読み出されたスケジューラグループ番号及び最低保障予約キュー番号と、そのスケジューラグループ番号について第２テーブルから読み出された、各優先等級１〜Ｐにおける最終読出しキュー番号とが登録される。
【００４５】
さらに、回送テーブルには、次にデータフレームを送出すべき、最も優先順位高いキューを示す次送出キュー番号と、そのキューが含まれるサブグループの優先等級を示す次送出優先等級番号とが登録される。
ただし、回送テーブル生成部６において回送テーブルが生成された初期段階では、次送出キュー番号及び次送出優先等級番号としてそれぞれゼロが登録されている。そして、回送テーブルがキューチェーンを順次に転送される過程において、次送出優先等級番号及び次送出キュー番号が更新される。
【００４６】
【表３】
0003698079.tif 000004
【００４７】
また、本実施形態では、キューごとに、下記の表４に示すキュー情報テーブルを設けている。キュー情報テーブルには、そのキューの属するスケジューラグループ番号と、そのキューの属するサブグループの優先等級番号と、そのキューの一連の番号であるキュー番号とが登録される。
【００４８】
さらに、キュー情報テーブルには、最大送出レートと、送信可否フラグとが登録される。最大送出レートは、シェーピングのために設定されたレートであって、データフレームが最大送出レートよりも大きなレートで送出されると、シェーピングにより送出が制限される。送信可否フラグは、条件▲１▼：そのキューにデータフレームが蓄積されており、かつ、条件▲２▼：そのデータフレームの送出レートがそのキューの送出レート制御による設定レート以下である場合に、送信可のフラグを示す。ここでは、送信可のフラグを「１」とする。
一方、条件▲１▼又は▲２▼のいずれか一方が満たされない場合には、送信可否フラグは、送信不可のフラグを示す。ここでは、送信不可のフラグを「０」とする。
【００４９】
【表４】
0003698079.tif 000005
【００５０】
そして、本実施形態では、パイプライン状に回送テーブルが転送されてきた各キューにおいて、それぞれキュー情報テーブルの内容と回送テーブルの内容とを比較して、一定の条件の下で、回送テーブルの内容を更新する。
以下、図５のフローチャートを参照して、各キューにおける処理について説明する。
【００５１】
まず、回送テーブルに登録されているスケジューラグループと、回送テーブルが転送されてきた現キューの属するスケジューラグループとが一致し、かつ、現キューのキュー情報テーブルの送信可否フラグが「１」であるか、否かを判断する（ステップＳ１）。
そして、スケジューラグループが不一致、及び／又は、送信可否フラグが「０」の場合には、現キューにおける処理を終了し、回送テーブルを次のキューへ転送する。
【００５２】
一方、スケジューラグループが一致し、かつ、送信可否フラグが「１」である場合には、回送テーブルに登録されている次送出キュー番号が「０」であるか否かを判断する。
そして、次送出キュー番号が「０」である場合、現キューを次送出キューとして登録し、現キューの属するサブグループの優先等級を登録する（ステップＳ５）。
【００５３】
一方、次送出キュー番号が「０」でない場合、回送テーブルに登録されている優先等級と、現キューの属するサブグループの優先等級とを比較する（ステップＳ３）。
そして、現キューの優先等級が、登録されている優先等級よりも低い場合、現キューにおける処理を終了し、回送テーブルを次のキューへ転送する。
また、現キューの優先等級が、登録されている優先等級よりも高い場合、登録されている次送出キュー番号を現キューに更新するとともに、登録されている優先等級を現キューの優先等級に更新する（ステップＳ５）。
【００５４】
また、登録されている優先等級と現キューの優先等級とが等しい場合は、条件１として、回送テーブルに登録されている最低帯域保障予約キュー番号と、現キュー番号とが同一が否かを判断する。
また、条件２として、回送テーブルに登録されている次送出キューの通し番号が、最終送出キューの通し番号よりも小さく、かつ、最終送出キューの通し番号が、現キューの通し番号よりも小さいか否かを判断する（ステップＳ４）。
【００５５】
ここで、図６を参照して、上記の条件２について説明する。
図６の（Ａ）に示すように、各サブグループにおいては、そのサブグループに属する各キューに通し番号を付与し、ラウンドロビンにおいて通し番号順にデータフレームを順次に送出するアルゴリズムを与えている。
このため、ラウンドロビンにおける優先順位は、図６の（Ｂ）に示すように、最終送出キューの次のキューが最も高く、キューの通し番号が大きくなるに従って優先順位が低下していく。そして、通し番号が最後のキューの次に、通し番号が先頭のキューの優先順位が続き、以下、最終送出キューまで順次に優先順位が低下していく。そして、最終送出キューの優先順位が最低となっている。
【００５６】
ここで、現キュー番号が、最終送出キュー番号よりも前である場合、すなわち、（現キュー番号＜最終送出キュー番号）の場合について検討する。この場合、転送されてきた回送テーブルに、次送出キュー番号として、現キューよりも若い番号のキューが登録されているときは、登録されているキューの優先順位の方が、現キューの優先順位よりも常に高くなっている。例えば、図６の（Ｂ）に示すよう、現キュー番号が「４」である場合に、回送テーブルに、次送出キュー番号として、「１」、「２」又は「３」が登録されているときは、現キューの優先順位より登録されているキューの優先順位の方が常に高くなっている。
【００５７】
次に、現キュー番号が、最終送出キュー番号よりも後である場合、すなわち、（最終送出キュー番号＜現キュー番号）について検討する。この場合において、回送テーブルに次送出キューとして登録されているキューの優先順位よりも現キューの優先順位が高くなる条件は、登録されているキューの番号が最終送出キューよりも若いことである。すなわち、（次送出キュー番号＜最終送出キュー番号）となることである。なぜならば、図６の（Ｂ）に示すように、最終送出キューよりも後ろのキューの優先順位は、常に、最終送出キューよりも前のキューの優先順位よりも高くなっているからである。
【００５８】
したがって、上記条件２である（次送出キュー番号＜最終送出キュー番号＜現キュー番号）は、現キューの優先順位が、次送出キューとして登録されているキューの優先順位よりも高い条件となる。
【００５９】
そして、条件１及び条件２のうちの少なくとも一方が満たされた場合、次送出キューを当該キューに更新するとともに、登録されている優先等級を現キューの優先等級に更新する（ステップＳ５）。そして、次送出キュー番号等が更新された回送テーブルを、次のキューへ転送する。
一方、条件１及び条件２のどちらも満たされていない場合、回送テーブルを更新することなく、次のキューへ転送する。
【００６０】
このような処理を各キューで行った後、アービタ８が、回送テーブルに登録されている次送出キュー番号を読み出す。そして、アービタ８は、読み出された次送出キュー番号の示すキューに対して、次にデータフレームを送出させる送信命令を出力する。
【００６１】
ところで、データフレームが新たに送出したキューは、そのキューの属するサブグループにおける最終送出キューとなる。このため、最終送出キュー番号が登録されている第２テーブルの内容を更新する必要が生じる。そこで、アービタ８は、第２テーブルに対して更新情報を出力する。更新情報には、次送出キュー番号及びそのキューの含まれるサブグループの優先等級が含まれている。第２テーブルでは、更新情報に基づいて、次送出キューの属するサブグループ（優先等級）の最終送出キュー番号が更新される。
【００６２】
なお、回送テーブル生成部６により第２テーブルに基づいて回送テーブルが生成されてから、第２テーブルの最終送出キュー番号が更新されるまでの間には、時間のずれが生じる。このため、あるキューから新たにデータフレームが送出されても、そのキューが属するサブグループの最終送出キュー番号の更新が遅れ、連続して生成された複数の回送テーブルにおいて更新されずにいる場合が生じうる。
【００６３】
しかし、長い時間で見たときのラウンドロビンの実行結果は公平であり、最終送出キューの更新が遅れることは実用上大きな問題とならない。また、データ送出遅延に敏感なアプリケーションに適用する場合には、最低帯域保証を設定して、更新の遅れの影響を受けないようにすることが可能である。
【００６４】
このように、回送テーブルを各キューの集合体であるキューチェーン内で順次に転送し、各キューにおいてそれぞれパイプライン状に優先順位を決定する処理を行う。
このため、全てのキューをその優先順位や最低保証帯域に関わらず、同じ構成とすることができる。このため、個々のキューは、全てのトラフィックを収容することができる。
【００６５】
また、優先順位を決定するためのラウンドロビン機能ブロックを複数設ける必要がないため、キューの使用方法の変化に応じて、個々のラウンドロビンに属するサブグループ（キューグループ）を再編成する必要がない。その結果、様々な組合せのキューの使用方法に容易に対応することができる。
【００６６】
また、一定時間でキュー間の送出優先順位を決定することができるので、タイムラグが明確となる。
【００６７】
また、パイプライン状に優先順位の決定をおこなうため、個々のキューの有するアルゴリズムを単純なものとすることができる。このため、簡単な回路構成で優先順位を決定する処理機能を実現することができる。
【００６８】
上述した実施の形態においては、本発明を特定の条件で構成した例について説明したが、本発明は、種々の変更を行うことができる。例えば、上述した実施形態では、回送テーブルの更新にあたり、登録されている優先等級を、最低保証帯域の割当て結果よりも先に判断したが、本発明では、これらの判断順序を逆にしてもよい。
【００６９】
また、例えば、上述した実施形態では、固定長のデータフレームを送出する優先順序を決定する例について説明したが、本発明では、データフレームは固定長であってもよいし、可変長であってもよい。
なお、データフレームが可変長である場合には、回送テーブル生成部により、キューチェーン中に存在する回送テーブルの数を制御するとよい。
【００７０】
また、例えば、上述した実施形態では、第２テーブルであるトランスミッションテーブルにより、スケジューラグループの送出の順番を決定した例について説明したが、本発明では、トランスミッションテーブルの代わりに、周期的に信号を送信するカウンタ回路により、スケジューラグループの送出の順番を決定してもよい。
【００７１】
【発明の効果】
以上、詳細に説明したように、本発明によれば、回送テーブルを各キューに順次に転送して次送出キューを決定する。すなわち、各キューにおいてパイプライン状に回送テーブルを処理する。このため、トラフィックシェーピングの組合せの変化に応じて、個々のサブグループを再構成する必要がない。また、個々のキューの回路規模を小さくすることができる。このため、キューの数を容易に増加させることができる。
【図面の簡単な説明】
【図１】実施形態のデータ転送装置の制御部の概略図である。
【図２】実施形態におけるパイプライン方式の説明図である。
【図３】実施形態におけるフレームスロットの概念図である。
【図４】実施形態におけるフレームスロットのスケジューラの割付け説明図である。
【図５】実施形態のデータ転送方法のフローチャートである。
【図６】ラウンドロビンの優先等級の説明図である。
【図７】データ交換機の概念図である。
【図８】２段階シェーピングの説明図である。
【図９】図８に示すスケジューラグループの拡大図である。
【符号の説明】
１  データフレーム
２  スケジューラ
３  ラウンドロビン
４  第１テーブル（スケジューラテーブル）
５  第２テーブル（トランスミッションテーブル）
６  回送テーブル生成部
７  回送テーブル
８  アービタ
９  フレームスロット
１０  スケジューラグループ
２０  キューグループ
３０  キューチェーン
１００  データ交換機
１１０  入力バッファカード
１２０  スイッチコア部
１３０  出力バッファカード
１３１  キュー
１４０  制御部
【図１】
0003698079.tif 000006
【図２】
0003698079.tif 000007
【図３】
0003698079.tif 000008
【図４】
0003698079.tif 000009
【図５】
0003698079.tif 000010
【図６】
0003698079.tif 000011
【図７】
0003698079.tif 000012
【図８】
0003698079.tif 000013
【図９】
0003698079.tif 000014