(57)【特許請求の範囲】
【請求項１】
ＴＤＭ方式のネットワークシステムを構成するスケジューラであって、
前記ネットワークシステムを構成する複数のノードをグループ化するグループ化手段と、
グループ間のパスに必要なトラヒック量に応じて、同一グループ間にはネットワーク内の全リンクにおける同一タイムスロットを割り当て、異なるグループ間には同一のタイムスロットで同一グループが送信元と宛先との両方を担うことを許容せずにタイムスロットを割り当てるスケジューリング、もしくは、グループ間のパスに必要なトラヒック量に応じて階段状のブロック単位のタイムスロット群を割り当てるスケジューリングを行う第１のスケジューリング手段と、
グループ内のパスに必要なトラヒック量に応じてタイムスロットを割り当てるスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う、スケジューラ。
【請求項２】
前記第２のスケジューリング手段は、
各々がグループ内のノード間のパスのスケジューリングを行う複数の第２のスケジューリング手段を含み、
前記複数の第２のスケジューリング手段の各々は、並列にスケジューリングを行う、請求項１に記載のスケジューラ。
【請求項３】
ＴＤＭ方式のネットワークシステムを構成するスケジューラであって、
前記ネットワークシステムを構成する複数のノード間のパスをグループ化するグループ化手段と、
グループ間のパスに必要なトラヒック量に応じて、ネットワーク内の全リンクにおける同一タイムスロットを各グループ間パスに割り当てるスケジューリングを行う第１のスケジューリング手段と、
グループ内のパスに必要なトラヒック量に応じてタイムスロットを割り当てるスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う、スケジューラ。
【請求項４】
前記第２のスケジューリング手段は、
各々がグループ内のパスのスケジューリングを行う複数の第２のスケジューリング手段を含み、
前記複数の第２のスケジューリング手段の各々は、並列にスケジューリングを行う、請求項３に記載のスケジューラ。
【請求項５】
複数のノードと、前記複数のノード間を接続するリンクと、を有してなるＴＤＭ方式のネットワークシステムであって、
前記ネットワークシステムを構成する複数のノードをグループ化するグループ化手段と、
グループ間のパスに必要なトラヒック量に応じて、同一グループ間にはネットワーク内の全リンクにおける同一タイムスロットを割り当て、異なるグループ間には同一のタイムスロットで同一グループが送信元と宛先との両方を担うことを許容せずにタイムスロットを割り当てるスケジューリング、もしくは、グループ間のパスに必要なトラヒック量に応じて階段状のブロック単位のタイムスロット群を割り当てるスケジューリングを行う第１のスケジューリング手段と、
グループ内のパスに必要なトラヒック量に応じてタイムスロットを割り当てるスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う、ネットワークシステム。
【請求項６】
複数のノードと、前記複数のノード間を接続するリンクと、を有してなるＴＤＭ方式のネットワークシステムであって、
前記ネットワークシステムを構成する複数のノード間のパスをグループ化するグループ化手段と、
グループ間のパスに必要なトラヒック量に応じて、ネットワーク内の全リンクにおける同一タイムスロットを各グループ間パス割り当てるスケジューリングを行う第１のスケジューリング手段と、
グループ内のパスに必要なトラヒック量に応じてタイムスロットを割り当てるスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う、ネットワークシステム。
【請求項７】
ＴＤＭ方式のネットワークシステムを構成するスケジューラに、
前記ネットワークシステムを構成する複数のノードをグループ化する手順と、
グループ間のパスに必要なトラヒック量に応じて、同一グループ間にはネットワーク内の全リンクにおける同一タイムスロットを割り当て、異なるグループ間には同一のタイムスロットで同一グループが送信元と宛先との両方を担うことを許容せずにタイムスロットを割り当てるスケジューリング、もしくは、グループ間のパスに必要なトラヒック量に応じて階段状のブロック単位のタイムスロット群を割り当てるスケジューリングを行った後に、グループ内のパスに必要なトラヒック量に応じてタイムスロットを割り当てるスケジューリングを行うか、または、グループ内の前記スケジューリングを行った後に、グループ間の前記スケジューリングを行う手順と、を実行させるためのプログラム。
【請求項８】
ＴＤＭ方式のネットワークシステムを構成するスケジューラに、
前記ネットワークシステムを構成する複数のノード間のパスをグループ化する手順と、
グループ間のパスに必要なトラヒック量に応じて、ネットワーク内の全リンクにおける同一タイムスロットを各グループ間パス割り当てるスケジューリングを行った後に、グループ内のパスに必要なトラヒック量に応じてタイムスロットを割り当てるスケジューリングを行うか、または、グループ内の前記スケジューリングを行った後に、グループ間の前記スケジューリングを行う手順と、を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＴＤＭ（time division multiplexing、時分割多重）方式のネットワークシステムにおいて、ノードやリンクのスケジューリングを行うための技術に関する。
【背景技術】
【０００２】
ＴＤＭ方式のネットワークシステムでは、ＴＳ（time slot、タイムスロット）長の整数倍の時間（ｔ）を周期として繰り返し処理を行う。以下では、ｔをＴＤＭフレーム長と呼ぶ。
【０００３】
以下、ＴＤＭ方式のネットワークシステムにおいて、ノードやリンクのスケジューリングを行う従来のスケジューリング方法について説明する（例えば、非特許文献１，２参照）。ここでは、図１２に示すように、ネットワークシステムが、ノードＡ〜Ｅとリンクａ〜ｅとからなり、１波長、単方向リングの構成であるとする。また、スケジューラは、ノードＡに配置されているとする。
【０００４】
ステップＳ１：
まず、図１２に示すように、スケジューラは、各パスが要求するトラヒック量を所要ＴＳ数に換算し、トラヒックマトリクスをＴＳマトリクスに変換する。なお、パスとは、送信元ノードと宛先ノードとの間を結ぶ通信経路を指す。ここでは、トラヒック量５０Ｍｂｐｓを１ＴＳに換算する。例えば、ノードＡ→ノードＤのパスのトラヒック量は１５０Ｍｂｐｓであるため、所要ＴＳ数は３となる。
【０００５】
ステップＳ２：
次に、図１３に示すように、スケジューラは、ＴＳマトリクスを基に、各リンクａ〜ｅの所要ＴＳ数を算出する。例えば、リンクａの所要ＴＳ数は、リンクａを通るパスの所要ＴＳ数（角丸四角形で囲った所要ＴＳ数）を合計した１８となる。次に、リンクａ〜ｅの所要ＴＳ数の最大値に基づき、全てのＴＳを収容し得るＴＤＭフレーム長（非特許文献２では、スーパーフレーム長と称している）を求める。リンクａ，ｂの所要ＴＳ数が１８で最大値であるため、ＴＤＭフレーム長は１８となる。なお、非特許文献２では、ｔを基本フレーム長（ＴＳ長の整数倍として定義）の整数倍にするという制約を設けているため、基本フレーム長を１０ＴＳとした場合、全てのＴＳを収容し得るＴＤＭフレーム長（非特許文献２では、スーパーフレーム長と称している）は、２フレーム分の２０ＴＳとなる。なお、ここでは、全てのＴＳを収容し得るフレーム長を可変としているが、固定としても良い。
【０００６】
ステップＳ３：
その後、図１４に示すように、スケジューラは、ステップＳ２で求めたフレーム長の空きＴＳに、各パスを所要ＴＳ数分割り当てる。このとき、例えば、Ｆｉｒｓｔ  Ｆｉｔ割当（空きを発見したら即割当）や、連続ＴＳ優先割当（要求するＴＳ数が連続して確保できれば即割当）等の様々な割当ポリシが存在する。この工程で、各リンクａ〜ｅの各ＴＳにおいて、どのパスのデータを流すかを表すリンクスケジュールテーブルが作成される。
【０００７】
以上のスケジューリング方法の流れを、図１５のフロー図に示す。すなわち、スケジューラは、各パスが要求するトラヒック量の集計後に上述のステップＳ１〜Ｓ３の処理を行い、各ノードＡ〜Ｅに対し、そのノードを終点とするリンクおよび始点とするリンクのリンクスケジュールテーブルを通知する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】X. Zhang and C. Qiao, "Pipelined transmission scheduling in all-optical TDM/WDM rings," in Proc. Int. Conf. Computer Communication and Networks, Sept. 1997, pp. 144-149.
【非特許文献２】K. Gokyu, K. Baba, and M. Murata, "Path accommodation methods for unidirectional rings with optical compression TDM," IEICE Transactions on Communications, vol. E83-B, pp. 2294-2303, Oct. 2000.
【非特許文献３】T. Tatsuta, N. Oota, N. Miki, and K. Kumozaki, "Design philosophy and performance of a GE-PON system for mass deployment," JOURNAL OF OPTICAL NETWORKING, vol. 6, no. 6, pp. 689-700, June 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、ネットワークシステムにおいては、各パスのトラヒック量は、固定ではなく、随時変動する。
【００１０】
例えば、図１６に示すように、ノードＣ→ノードＡのパスのトラヒック量が多く、ノードＣ→ノードＢのパスのトラヒック量が少ない状態でＴＳ割当を行った場合に、その後、ノードＣ→ノードＡのパスのトラヒック量が少なくなり、ノードＣ→ノードＢのパスのトラヒック量が多くなることがある。
【００１１】
このとき、ＴＳを変更しないと、トラヒック量が少なくなったノードＣ→ノードＡのパスに多くのＴＳを割り当てたままとなり、非常に非効率な状態になる。
【００１２】
そのため、スケジューラは、再度スケジューリングを行い、リンクスケジュールテーブルを書き換えることで、トラヒック変動に追従する。
【００１３】
しかしながら、全パス数は、ノード数をＮとするとＯ（Ｎ2）と表されるため、従来法のように、１パスずつシーケンシャルにＴＳ割当を行う場合、１パスあたりの平均ＴＳ割当計算時間をαとおくと、全パスのＴＳ割当の計算時間はα×Ｏ（Ｎ2）となる。加えて、それぞれのパスが通るリンク数、すなわちＴＳ割当の際に空塞状況を確認する必要があるリンク数はＯ（Ｎ）と表されるため、α自体もＮに依存することとなる。したがって、ＴＳ割当の計算時間は、ネットワークシステムの規模と共に増大する。
【００１４】
そのため、トラヒック変動に追従するネットワークシステムの大規模化を実現するためには、ＴＳ割当の計算時間を削減することによって、スケジューリング時間を削減することが重要な課題となる。
【００１５】
そこで、本発明の目的は、ＴＤＭ方式のネットワークシステムにおいて、スケジューリング時間を削減することで、システムの大規模化を実現することができる技術を提供することにある。
【課題を解決するための手段】
【００１６】
本発明の第１のスケジューラは、
ＴＤＭ方式のネットワークシステムを構成するスケジューラであって、
前記ネットワークシステムを構成する複数のノードをグループ化するグループ化手段と、
グループ間のスケジューリングを行う第１のスケジューリング手段と、
グループ内のスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う。
【００１７】
本発明の第２のスケジューラは、
ＴＤＭ方式のネットワークシステムを構成するスケジューラであって、
前記ネットワークシステムを構成する複数のノード間のパスをグループ化するグループ化手段と、
グループ間のスケジューリングを行う第１のスケジューリング手段と、
グループ内のスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う。
【００１８】
本発明の第１のネットワークシステムは、
複数のノードと、前記複数のノード間を接続するリンクと、を有してなるＴＤＭ方式のネットワークシステムであって、
前記ネットワークシステムを構成する複数のノードをグループ化するグループ化手段と、
グループ間のスケジューリングを行う第１のスケジューリング手段と、
グループ内のスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う。
【００１９】
本発明の第２のネットワークシステムは、
複数のノードと、前記複数のノード間を接続するリンクと、を有してなるＴＤＭ方式のネットワークシステムであって、
前記ネットワークシステムを構成する複数のノード間のパスをグループ化するグループ化手段と、
グループ間のスケジューリングを行う第１のスケジューリング手段と、
グループ内のスケジューリングを行う第２のスケジューリング手段と、を有し、
前記第１のスケジューリング手段によるスケジューリング後に、前記第２のスケジューリング手段によるスケジューリングを行うか、または、前記第２のスケジューリング手段によるスケジューリング後に、前記第１のスケジューリング手段によるスケジューリングを行う。
【００２０】
本発明の第１のプログラムは、
ＴＤＭ方式のネットワークシステムを構成するスケジューラに、
前記ネットワークシステムを構成する複数のノードをグループ化する手順と、
グループ間のスケジューリングを行った後に、グループ内のスケジューリングを行うか、または、グループ内のスケジューリングを行った後に、グループ間のスケジューリングを行う手順と、を実行させる。
【００２１】
本発明の第２のプログラムは、
ＴＤＭ方式のネットワークシステムを構成するスケジューラに、
前記ネットワークシステムを構成する複数のノード間のパスをグループ化する手順と、
グループ間のスケジューリングを行った後に、グループ内のスケジューリングを行うか、または、グループ内のスケジューリングを行った後に、グループ間のスケジューリングを行う手順と、を実行させる。
【発明の効果】
【００２２】
本発明によれば、ネットワークシステムを構成する複数のノードまたは複数のノード間のパスをグループ化し、グループ間のスケジューリングを行った後に、段階的に、グループ内のスケジューリングを行うか、または、グループ内のスケジューリングを行った後に、段階的に、グループ間のスケジューリングを行う。
【００２３】
これにより、スケジューリング時間が削減されるため、システムの大規模化を実現することができるという効果が得られる。
【図面の簡単な説明】
【００２４】
【図１】本発明のネットワークシステムの構成を示す図である。
【図２】本発明の第１の実施形態のスケジューラの構成を示す図である。
【図３】本発明の第１の実施形態のスケジューラの前提条件を説明する図である。
【図４】本発明の第１の実施形態のスケジューラの概略動作を説明する図である。
【図５】本発明の第１の実施形態のスケジューラの詳細動作を説明する図である。
【図６】本発明の第１の実施形態のスケジューラの詳細動作を説明する図である。
【図７】本発明の第１の実施形態のスケジューラの詳細動作（第１の例）を説明する図である。
【図８】本発明の第１の実施形態のスケジューラの詳細動作（第２の例）を説明する図である。
【図９】本発明の第２の実施形態のスケジューラの構成を示す図である。
【図１０】本発明の第２の実施形態のスケジューラの動作を説明する図である。
【図１１】本発明を多段リング構成のネットワークシステムに適用する場合の動作を説明する図である。
【図１２】従来のスケジューリング方法を説明する図である。
【図１３】従来のスケジューリング方法を説明する図である。
【図１４】従来のスケジューリング方法を説明する図である。
【図１５】従来のスケジューリング方法の流れを説明するフロー図である。
【図１６】従来のスケジューリング方法の課題を説明する図である。
【発明を実施するための形態】
【００２５】
以下に、本発明を実施するための形態について図面を参照して説明する。
（１）第１の実施形態
図１に、本発明のスケジューラが適用されるネットワークシステムの構成を示す。
【００２６】
図１に示すように、本実施形態のネットワークシステムは、Ｎ（Ｎは、２以上の自然数）個のノード１０間がリンク２０によって接続されたリング型のネットワークシステムである。なお、図１においては、Ｎ＝５となっているが、Ｎの数はこれに限定されない。
【００２７】
各ノード１０は、それぞれホストコンピュータ３０が接続されており、ホストコンピュータ３０間のデータを転送する。このとき、ノード１０は、リング上の前段のノードから送られてきたデータを処理し、次段のノードへデータを送る。
【００２８】
スケジューラ４０は、ネットワークシステム全体を管理し、各リンク２０および各ノード１０のスケジューリングを行う。スケジューラ４０の配置場所は、図１に限定されず、別のノードに配置されても良い。
【００２９】
なお、本発明においては、スケジューラ４０に主な特徴があり、ノード１０は、公知の構成にパスのトラヒック量を動的に収集しスケジューラ４０に通知する機能を追加した構成であれば良く、また、ホストコンピュータ３０は公知の構成であれば良い。そのため、以下では、スケジューラ４０の構成についてのみ詳細に説明する。
【００３０】
図２に、本発明の第１の実施形態のスケジューラ４０の構成を示す。
【００３１】
図２に示すように、本発明の第１の実施形態のスケジューラ４０は、交流トラヒック量集計部４０１と、ノードグルーパ４０２と、グループ間帯域割当部４０３と、リンクテーブル（グループ単位）４０４と、グループ内（ノード間）帯域割当部４０５と、テーブル変換部４０６と、リンクスケジュールテーブル４０７と、テーブル換算部４０８と、ノードグループテーブル４０９と、テーブル変換部４１０と、ノードスケジュールテーブル４１１と、テーブルトランスミッタ４１２と、タイマ４１３と、を有している。
【００３２】
交流トラヒック量集計部４０１は、各ノード１０から、各パスが要求するトラヒック量を動的に集計する。
【００３３】
ノードグルーパ４０２は、Ｎ個のノード１０を、論理的に、Ｇ（Ｇは、Ｎ＞Ｇの関係を満たす２以上の自然数）個のグループにグループ化するグループ化手段である。
【００３４】
グループ間帯域割当部４０３は、各グループ間（同一のグループ間、異なるグループ間の双方を含む）にＴＳを割り当て、そのＴＳ割当結果を基に、各リンク２０のリンクテーブル（グループ単位）４０４を作成する。
【００３５】
すなわち、グループ間帯域割当部４０３は、グループ間のスケジューリングを行うもので、第１のスケジューリング手段に相当する。
【００３６】
リンクテーブル（グループ単位）４０４は、リンク数分（Ｎ個）配置されるものであり、そのリンク２０の各ＴＳにおいて、どのグループ間のデータを流すかを表すテーブルである。
【００３７】
グループ内（ノード間）帯域割当部４０５は、グループ数の２乗分（Ｇ2個）配置されるものであり、グループ内のノード１０間（同一のグループに属するノード１０間、異なるグループに属するノード１０間の双方を含む）のパスにＴＳを割り当てる。各グループ内（ノード間）帯域割当部４０５は、並列処理が可能である。
【００３８】
すなわち、グループ内（ノード間）帯域割当部４０５は、グループ内のスケジューリングを行うもので、第２のスケジューリング手段に相当する。
【００３９】
なお、Ｇ2個のグループ内（ノード間）帯域割当部４０５の内訳は、同一のグループに属するノード１０間のパス（送信元ノードと宛先ノードが同一のグループに属するパス）へのＴＳ割当を行うのがＧ個、異なるグループに属するノード１０間のパス（送信元ノードと宛先ノードが異なるグループに属するパス）へのＴＳ割当を行うのがＧ（Ｇ−１）個で、合計Ｇ2個となる。
【００４０】
テーブル変換部４０６は、リンク数分（Ｎ個）配置されるものであり、そのリンク２０のリンクテーブル（グループ単位）４０４を、グループ内（ノード間）帯域割当部４０５のＴＳ割当結果を基に、リンクスケジュールテーブル４０７に変換する。各テーブル変換部４０６は、並列処理が可能である。
【００４１】
リンクスケジュールテーブル４０７は、リンク数分（Ｎ個）配置されるものであり、そのリンク２０の各ＴＳにおいて、どのパスのデータを流すかを表すテーブルである。
【００４２】
テーブル換算部４０８は、グループ数分（Ｇ個）配置されるものであり、各リンク２０のリンクテーブル（グループ単位）４０４を基に、そのグループのノードグループテーブル４０９を作成する。各テーブル換算部４０８は、並列処理が可能である。
【００４３】
ノードグループテーブル４０９は、グループ数分（Ｇ個）配置されるものであり、そのグループの各ＴＳにおけるノード処理の内容（データ送信、方路切替等）を表すテーブルである。
【００４４】
テーブル変換部４１０は、グループ数分（Ｇ個）配置されるものであり、そのグループのノードグループテーブル４０９を、各リンク２０のリンクスケジュールテーブル４０７を基に、ノードスケジュールテーブル４１１に変換する。各テーブル変換部４１０は、並列処理が可能である。
【００４５】
ノードスケジュールテーブル４１１は、ノード数分（Ｎ個）配置されるものであり、そのノード１０の各ＴＳにおけるノード処理の内容（データ送信、方路切替等）を表すテーブルである。
【００４６】
テーブルトランスミッタ４１２は、各ノード１０に対し、そのノードのノードスケジュールテーブル４１１を送信する。ここで、従来法においては、各ノードが独自にリンクのスケジュールテーブルから各ＴＳにおけるノード処理を認識する必要があった。しかし、本実施形態においては、各ノードにノードスケジュールテーブル４１１を送信するため、各ノードがリンクのスケジュールテーブルからノード処理を認識するという機能を配備する必要がなくなる。
【００４７】
タイマ４１３は、各ノード１０が処理を行う時間を管理する。
【００４８】
以下、本実施形態のスケジューラ４０の動作について説明する。
（ｉ）概略動作
まず、スケジューラ４０の概略動作について説明する。
【００４９】
図３に示すように、ここでは説明の便宜上、ネットワークシステムが、Ｎ＝６とした単方向リングの構成であり、リンクあたりで同一スロットに同時に接続可能なチャネルは１個（ファイバ多重や波長多重を行わない）であるものとする。なお、６個のノード１０をそれぞれノードＡ〜Ｆとし、６個のリンク２０をそれぞれリンクａ〜ｆとする。ただし、本発明は、これに限定されず、双方向リングをはじめ任意トポロジおよび波長多重を行った場合にも適用可能である（各ファイバの各波長についてリンクスケジュールテーブル４０７が作成される）。
【００５０】
また、スケジューラ４０がノードＡに設けられているとする。
【００５１】
図４に、本実施形態のスケジューラ４０において、リンクスケジュールテーブル４０７を作成するまでの動作の概要を示す。
【００５２】
図４に示すように、まず、ノードグルーパ４０２は、６個のノードＡ〜Ｆを論理的にグループ化する。ここでは、６個のノードＡ〜Ｆを、２ノードずつの３個のグループにグループ化することとし、ノードＡ，Ｂはグループｇ１に、ノードＣ，Ｄはグループｇ２に、ノードＥ，Ｆはグループｇ３に、それぞれグループ化している。
【００５３】
次に、グループ間帯域割当部４０３は、ノード単位のＴＳマトリクスを、グループ単位のＴＳマトリクスに変換する。例えば、ｇ３→ｇ３の所要ＴＳ数は、ｇ３に属するノードＥ，Ｆの一方を送信元ノード、他方を宛先ノードとするパスの所要ＴＳ数（角丸四角形で囲った所要ＴＳ数）に基づき、４となる。
【００５４】
次に、グループ間帯域割当部４０３は、グループ単位のＴＳマトリクスを基に、各グループ間にＴＳを割り当てる。例えば、ｇ１→ｇ３には、リンクａ〜ｅのＳ１〜Ｓ４のＴＳを割り当てる。
【００５５】
次に、グループ間帯域割当部４０３は、各リンクのリンクテーブル（グループ単位）４０４を作成する。例えば、リンクａのリンクテーブル（グループ単位）４０４において、Ｓ１のＴＳには、ｇ１→ｇ３をスケジューリングする。
【００５６】
一方、各グループ内（ノード間）帯域割当部４０５は、グループ内のノード間の各パスにＴＳを割り当てる。例えば、ｇ１→ｇ３内のノード間のパスのＴＳ割当を行うグループ内（ノード間）帯域割当部４０５は、ノードＡ→ノードＦのパスには、リンクａ〜ｅのＳ１のＴＳを割り当てる。このとき、ｇ１→ｇ３内のノード間のパスに対するＴＳ割当処理とｇ１→ｇ２内のノード間のパスに対するＴＳ割当処理とは、独立して実行可能である。
【００５７】
その後、各テーブル変換部４０６は、各リンクのリンクテーブル（グループ単位）４０４をリンクスケジュールテーブル４０７に変換する。例えば、リンクａのリンクスケジュールテーブル４０７において、Ｓ１のＴＳには、ノードＡ→ノードＦのパスをスケジューリングする。
【００５８】
本実施形態においては、Ｎ個のノード１０をグループ化し、グループ間でのＴＳ割当の後に、段階的に、グループ内のノード間のパスのＴＳ割当を実行する。そのため、従来法と比較して、ＴＳ割当の計算時間を削減することができる。
【００５９】
すなわち、従来法においては、Ｏ（Ｎ2）本のパスを、Ｏ（Ｎ）本のリンク上に割り当てていた。これに対して、本実施形態においては、グループ単位の計算では、Ｏ（Ｇ2）本のパスを、Ｏ（Ｇ）本のリンク上に割り当て、グループ内のノード単位の計算では、１グループあたり、Ｏ｛（Ｎ／Ｇ）2｝本のパスを、Ｏ｛（Ｎ／Ｇ）｝本のリンク上に割り当てる。さらに、本実施形態においては、テーブル分割を行っているため、ＴＳ割当の際に、空塞状況を確認する必要があるＴＳ数は従来法に比べて小さい値となる。以上より、本実施形態においては、従来法と比較して、ＴＳ割当の計算時間を削減することができる。
【００６０】
また、例えば、図４のテーブル上では、ｇ１→ｇ３の部分と、ｇ１→ｇ２の部分と、は排他的に分割されている。そのため、ｇ１→ｇ３内のノード間のパスに対するＴＳ割当処理と、ｇ１→ｇ２内のノード間のパスに対するＴＳ割当処理とは、独立して実行可能である。よって、グループ内（ノード間）帯域割当部４０５によるＴＳ割当処理を、並列処理することで、ＴＳ割当の計算時間をさらに削減することができる。
（ｉｉ）詳細動作
次に、スケジューラ４０の詳細動作について説明する。
【００６１】
図５に示すように、ここでは説明の便宜上、ネットワークシステムが、Ｎ＝８とした単方向リングの構成であり、リンクあたりで同一スロットに同時に接続可能なチャネルは１個（ファイバ多重や波長多重を行わない）であるものとする。なお、８個のノード１０をそれぞれノードＡ〜Ｈとし、８個のリンク２０をそれぞれリンクａ〜ｈとする。ただし、本発明は、これに限定されず、双方向リングをはじめ任意トポロジおよび波長多重を行った場合にも適用可能である（各ファイバの各波長についてリンクスケジュールテーブル４０７が作成される）。
【００６２】
また、スケジューラ４０がノードＡに設けられているとする。
【００６３】
まず、ノードグルーパ４０２は、８個のノードＡ〜Ｈをグループ化する。ここでは、８個のノードＡ〜Ｈを２ノードずつの４個のグループにグループ化することとし、ノードＡ，Ｂはグループｇ１に、ノードＣ，Ｄはグループｇ２に、ノードＥ，Ｆはグループｇ３に、ノードＧ，Ｈはグループｇ４に、それぞれグループ化している。ここでは、隣接するノードを同数ずつグループ化しているが、グループ化の方法はこれに限定されない。
【００６４】
次に、グループ間帯域割当部４０３は、図５の上側のノード間のリンクテーブル（各リンクａ〜ｈのリンクスケジュールテーブル４０７を集合したテーブルに相当）を、図５の下側のグループ間のリンクテーブル（各リンクａ〜ｈのリンクテーブル（グループ単位）４０４を集合したテーブルに相当）を用意する。
【００６５】
次に、図６に示すように、グループ間帯域割当部４０３は、ノード単位のＴＳマトリクスを、グループ単位のＴＳマトリクスに変換する。
【００６６】
次に、グループ間帯域割当部４０３は、グループ単位のＴＳマトリクスを基に、グループ間のリンクテーブル上で各グループ間にＴＳを割り当てていく。
【００６７】
ここで、グループ間にＴＳを割り当てる方法としては、例えば、２つの例が考えられる。以下、この２つの例について説明する。
【００６８】
図７に示すように、第１の例では、グループ間帯域割当部４０３は、同一のグループ間（送信元ノードと宛先ノードが同一のグループに属する）には、リング１周分×所要ＴＳ数を割り当てる。図７では、ｇ１→ｇ１の所要ＴＳ数は１と仮定しており、そのため、Ｓ１のＴＳをリング１周分割り当てる。
【００６９】
また、グループ間帯域割当部４０３は、異なるグループ間（送信元ノードと宛先ノードが異なるグループに属する）には、同一のＴＳで同一グループが送信元と宛先の両方を担うことを許容しないＴＳ割当を行う。例えば、Ｓ２，Ｓ３のＴＳでは、ｇ１，ｇ３は、送信元にはなっているが、宛先にはなっておらず、逆に、ｇ２，ｇ４は、宛先にはなっているが、送信元にはなっていない。
【００７０】
続いて、各グループ内（ノード間）帯域割当部４０５は、ノード単位のＴＳマトリクスを基に、ノード間のリンクテーブル上でグループ内のノード間のパスにＴＳを割り当てていく。例えば、ｇ１→ｇ１内のノード間のパスのＴＳ割当を行うグループ内（ノード間）帯域割当部４０５は、ノードＡ→ノードＢのパスには、リンクａのＳ１のＴＳを割り当て、ノードＢ→ノードＡのパスには、リンクｂ〜ｈのＳ１のＴＳを割り当てる。また、ｇ２→ｇ１内のノード間のパスのＴＳ割当を行うグループ内（ノード間）帯域割当部４０５は、ノードＣ→ノードＡのパスには、リンクｃ〜ｈのＳ８のＴＳを割り当て、ノードＤ→ノードＢのパスには、リンクｄ〜ｈ，ａのＳ９のＴＳを割り当てる。また、これらのグループ内（ノード間）帯域割当部４０５は、独立して実行可能である。
【００７１】
第１の例では、グループ単位で割り当てられたＴＳは、完全に排他的となる。
【００７２】
一方、図８に示すように、第２の例では、グループ間帯域割当部４０３は、同一のグループ間（送信元ノードと宛先ノードが同一のグループに属する）には、第１の例と同様のＴＳ割当を行う。
【００７３】
また、グループ間帯域割当部４０３は、異なるグループ間（送信元ノードと宛先ノードが異なるグループに属する）には、同一のＴＳで同一グループが送信元と宛先の両方を担うことを許容するＴＳ割当を行う。例えば、Ｓ２，Ｓ３のＴＳでは、ｇ１，ｇ２，ｇ３，ｇ４はいずれも、送信元にも宛先にもなっている。
【００７４】
続いて、各グループ内（ノード間）帯域割当部４０５は、ノード単位のＴＳマトリクスを基に、ノード間のリンクテーブル上でグループ内のノード間のパスにＴＳを割り当てていく。例えば、ｇ１→ｇ１内のノード間のパスのＴＳ割当を行うグループ内（ノード間）帯域割当部４０５は、第１の例と同様のＴＳ割当を行う。また、ｇ３→ｇ１内のノード間のパスのＴＳ割当を行うグループ内（ノード間）帯域割当部４０５は、ノードＦ→ノードＡのパスには、リンクｆ〜ｈのＳ４のＴＳを割り当て、ノードＥ→ノードＢのパスには、リンクｅ〜ｈ，ａのＳ５のＴＳを割り当てる。
【００７５】
第２の例では、グループ単位で割り当てられたＴＳは、完全に排他的とはならないが、グループ内のノード間のパスに割り当てるＴＳを階段状のブロック単位とすることで、グループ間の排他性が保持される（どのグループも独立にグループ内のＴＳ割当が可能になる）。
【００７６】
上述したように本実施形態においては、ノード１０をグループ化し、グループ間でのＴＳ割当の後に、段階的に、グループ内のノード間のパスでのＴＳ割当を実行する。そのため、従来法と比較して、ＴＳ割当の計算時間を削減することができる。
【００７７】
すなわち、従来法においては、Ｏ（Ｎ2）本のパスを、Ｏ（Ｎ）本のリンク上に割り当てていた。これに対して、本実施形態においては、グループ単位の計算では、Ｏ（Ｇ2）本のパスを、Ｏ（Ｇ）本のリンク上に割り当て、グループ内のノード単位の計算では、１グループあたり、Ｏ｛（Ｎ／Ｇ）2｝本のパスを、Ｏ｛（Ｎ／Ｇ）｝本のリンク上に割り当てる。さらに、本実施形態においては、テーブル分割を行っているため、ＴＳ割当の際に、空塞状況を確認する必要があるＴＳ数は従来法に比べて小さい値となる。以上より、本実施形態においては、従来法と比較して、ＴＳ割当の計算時間を削減することができる。
【００７８】
また、グループ内（ノード間）帯域割当部４０５によるＴＳ割当処理を、並列処理することにより、ＴＳ割当の計算時間をさらに削減することができる。
【００７９】
このように、本実施形態においては、ＴＳ割当の計算時間を削減することができるため、スケジューリング時間を削減することができ、それにより、トラヒック変動に追従するネットワークシステムの大規模化を実現することができる。
【００８０】
また、本実施形態においては、テーブル変換部４０６、テーブル換算部４０８、およびテーブル変換部４１０による処理の並列処理も可能であるため、スケジューリング時間をさらに削減することができる。
（２）第２の実施形態
図９に、本発明の第２の実施形態のスケジューラ４０の構成を示す。なお、図９において、図２と同一の構成要素には同一の符号を付し、説明を省略する。
【００８１】
図９に示すように、本発明の第２の実施形態のスケジューラ４０は、交流トラヒック量集計部４０１と、パスグルーパ４１４と、グループ間帯域割当部４１５と、リンクテーブル（グループ単位）４１６と、グループ内（ノード間）帯域割当部４１７と、テーブル変換部４１８と、リンクスケジュールテーブル４０７と、テーブル換算部４１９と、ノードスケジュールテーブル４１１と、テーブルトランスミッタ４１２と、タイマ４１３と、を有している。
【００８２】
パスグルーパ４１４は、Ｎ個のノード１０間のパス（フルメッシュ通信であれば、Ｎ（Ｎ−１）本）を、論理的に、Ｇ個のグループにグループ化するグループ化手段である。
【００８３】
グループ間帯域割当部４１５は、各グループにＴＳを割り当て、そのＴＳ割当結果を基に、各リンク２０のリンクテーブル（グループ単位）４１６を作成する。
【００８４】
すなわち、グループ間帯域割当部４１５は、グループ間のスケジューリングを行うもので、第１のスケジューリング手段に相当する。
【００８５】
リンクテーブル（グループ単位）４１６は、リンク数分（Ｎ個）配置されるものであり、そのリンク２０の各ＴＳにおいて、どのグループのデータを流すかを表すテーブルである。
【００８６】
グループ内（ノード間）帯域割当部４１７は、グループ数分（Ｇ個）配置されるものであり、そのグループ内のパスにＴＳを割り当てる。各グループ内（ノード間）帯域割当部４１７は、並列処理が可能である。
【００８７】
すなわち、グループ内（ノード間）帯域割当部４１７は、グループ内のスケジューリングを行うもので、第２のスケジューリング手段に相当する。
【００８８】
テーブル変換部４１８は、グループ数分（Ｇ個）配置されるものであり、各リンク２０のリンクテーブル（グループ単位）４０４を、グループ内（ノード間）帯域割当部４０５による、そのグループのＴＳ割当結果を基に、リンクスケジュールテーブル４０７に変換する。各テーブル変換部４１８は、並列処理が可能である。
【００８９】
テーブル換算部４１９は、グループ数分（Ｇ個）配置されるものであり、各リンク２０のリンクスケジュールテーブル４０７を、グループ内（ノード間）帯域割当部４０５による、そのグループのＴＳ割当結果を基に、ノードスケジュールテーブル４１１に変換する。各テーブル換算部４１９は、並列処理が可能である。
【００９０】
以下、本実施形態のスケジューラ４０の動作について説明する。
【００９１】
ここでは、説明の便宜上、第１の実施形態と同様に、図３にした前提条件が適用されるものとする。
【００９２】
図１０に、本実施形態のスケジューラ４０において、リンクスケジュールテーブル４０７を作成するまでの動作の概要を示す。
【００９３】
図１０に示すように、まず、パスグルーパ４１４は、６個のノードＡ〜ＦからなるネットワークシステムにおけるパスをＧ個のグループにグループ化する。ここでは、パスを３個のグループにグループ化することとする。なお、ＷＤＭ（Wavelength Division Multiplexing、波長分割多重）伝送を用いる場合は、例えば、Ｇを１ファイバあたりの波長数の整数倍に設定することが考えられる。
【００９４】
リング型のネットワークシステムの場合、ノードｉ→ｊのパスとノードｊ→ｉのパスとでリングを１周する。言い換えると、このような対称となるパスをペアとすると、ＴＳ割当の単位がリング１周分となる。
【００９５】
そこで、図１０では、パスグルーパ４１４は、対称となるパスをペア化した後、送信元ノード番号、宛先ノード番号の昇順に、パスをグループ化している。ただし、このグループ化方法は、一例であって、これに限定されない。
【００９６】
次に、グループ間帯域割当部４１５は、各グループにＴＳを割り当てる。例えば、ｇ１には、リンクａ〜ｅのＳ１〜Ｓ９のＴＳを割り当てる。
【００９７】
次に、グループ間帯域割当部４１５は、各リンクのリンクテーブル（グループ単位）４０４を作成する。例えば、リンクａのリンクテーブル（グループ単位）４０４において、Ｓ１のＴＳには、ｇ１をスケジューリングする。
【００９８】
一方、各グループ内（ノード間）帯域割当部４１７は、グループ内の各パスにＴＳを割り当てる。このとき、ｇ１内のパスに対するＴＳ割当処理と、ｇ２内のパスに対するＴＳ割当処理と、ｇ３内のパスに対するＴＳ割当処理とは、独立して実行可能である。
【００９９】
その後、各テーブル変換部４１８は、各リンクのリンクテーブル（グループ単位）４１６をリンクスケジュールテーブル４０７に変換する。
【０１００】
上述したように本実施形態においては、パスをグループ化し、グループ間でのＴＳ割当の後に、段階的に、グループ内のパスでのＴＳ割当を実行する。
【０１０１】
そのため、第１の実施形態と同様に、ＴＳ割当の計算時間を削減することができる。
【０１０２】
また、グループ内（ノード間）帯域割当部４１７によるＴＳ割当処理を、並列処理することにより、ＴＳ割当の計算時間をさらに削減することができる。
【０１０３】
このように、本実施形態においては、ＴＳ割当の計算時間を削減することができるため、スケジューリング時間を削減することができ、それにより、トラヒック変動に追従するネットワークシステムの大規模化を図ることができる。
【０１０４】
また、本実施形態においては、テーブル変換部４１８およびテーブル換算部４１９による処理の並列処理も可能であるため、スケジューリング時間をさらに削減することができる。
【０１０５】
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明の要旨を逸脱しない範囲で当業者が理解し得る各種の変形が可能である。
【０１０６】
例えば、上記実施形態においては、リング段数が１であるリング型のネットワークシステムに適用する場合の例を挙げて説明したが、本発明は、多段リング構成のネットワークシステムにも適用可能である。
【０１０７】
例えば、図１１に示すように、上位リングに、３個の下位リングＸ〜Ｚが接続された多段リング構成について考える。詳細には、上位リングは、ノードＡ〜Ｄにより構成され、ノードＡを介して下位リングＸ（ノードＡ，Ｅ〜Ｇにより構成）が接続され、ノードＢを介して下位リングＹ（ノードＢ，Ｈ〜Ｊにより構成）が接続され、ノードＣを介して下位リングＺ（ノードＣ，Ｋ〜Ｍにより構成）が接続されている。
【０１０８】
この場合、まず、上位リングのノードＤに配置されたマスタースケジューラ４０Ａは、下位リングＸ〜Ｚを、それぞれ１つのグループにグループ化する。すなわち、下位リングＸを構成するノードＡ，Ｅ〜ＧはグループＲＸに、下位リングＹを構成するノードＢ，Ｈ〜ＪはグループＲＹに、下位リングＺを構成するノードＣ，Ｋ〜ＭはグループＲＺに、それぞれグループ化する。また、ノードＤはグループＤとする。
【０１０９】
そして、マスタースケジューラ４０Ａは、まず、グループ間のＴＳ割当を行い、その後に、グループ内のノード間のパスのＴＳ割当を行う。
【０１１０】
このとき、ノードＡ，Ｂ，Ｃにもスレーブスケジューラ４０Ｂを配置し、各々が属するグループ内のＴＳ割当を並列に処理することとすれば、スケジューリング時間の削減においてより効果的となる。
【０１１１】
また、上位リングと下位リングのそれぞれのスケジューリングで異なる周期を用いることも可能である。
【０１１２】
また、上記実施形態においては、グループ間のスケジューリング（ＴＳ割当）の後に、段階的に、グループ内のスケジューリング（ＴＳ割当）を実行する例を説明したが、本発明は、スケジューリングの順番はこれに限定されず、グループ内のスケジューリングの後に、段階的に、グループ間のスケジューリングを実行しても良い。この場合でも、ＴＳ割当の計算時間を削減することができる。
【０１１３】
また、本発明のスケジューラ４０，４０Ａ，４０Ｂにて行われる方法は、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１１４】
１０，Ａ〜Ｈ    ノード
２０，ａ〜ｈ    リンク
３０    ホストコンピュータ
４０    スケジューラ
４０Ａ    マスタースケジューラ
４０Ｂ    スレーブスケジューラ
４０１    交流トラヒック量集計部
４０２    ノードグルーパ
４０３，４１５    グループ間帯域割当部
４０４，４１６    リンクテーブル（グループ単位）
４０５，４１７    グループ内（ノード間）帯域割当部
４０６，４１０，４１８    テーブル変換部
４０７    リンクスケジュールテーブル
４０８，４１９    テーブル換算部
４０９    ノードグループテーブル
４１１    ノードスケジュールテーブル
４１２    テーブルトランスミッタ
４１３    タイマ
４１４    パスグルーパ
ｇ１〜ｇ３，ＲＸ〜ＲＺ    グループ
【図２】
0005775027.tif 000002
【図３】
0005775027.tif 000003
【図４】
0005775027.tif 000004
【図５】
0005775027.tif 000005
【図６】
0005775027.tif 000006
【図９】
0005775027.tif 000007
【図１２】
0005775027.tif 000008
【図１３】
0005775027.tif 000009
【図１４】
0005775027.tif 000010
【図１５】
0005775027.tif 000011
【図１】
0005775027.tif 000012
【図７】
0005775027.tif 000013
【図８】
0005775027.tif 000014
【図１０】
0005775027.tif 000015
【図１１】
0005775027.tif 000016
【図１６】
0005775027.tif 000017