(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.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、上述のステップＳ３において、各パスにＴＳを割り当てる方法として、パス長の降順に割当を行う方法、トラヒック量の降順に割当を行う方法、波長・スロット使用率が小さいＴＳを優先する方法等、様々なヒューリスティックアルゴリズムが存在する。
【００１０】
しかし、従来法では、例えば、図２２の右側に示すように、パス長の降順に割当を行う場合、パス長が長いパスには要求通りにＴＳが割り当てられるが、後で割当が行われるパス長が短いパスには要求通りにＴＳが割り当てられない可能性がある。
【００１１】
また、図２２の左側に示すように、パス長を考慮せずに割当を行う場合、パス長が短いパスには隙間をぬってＴＳを割り当てることができるが、パス長が長いパスには要求通りにＴＳが割り当てられない可能性がある。
【００１２】
このように、従来法では、フレーム内に要求された全ＴＳを収容しきれない場合に、要求通りにＴＳが割り当てられないパスが生じ、パス間の公平性を担保することができないという課題がある。
【００１３】
そこで、本発明の目的は、ＴＤＭ方式のネットワークシステムにおいて、パス間の公平性を担保しつつＴＳ割当を行うことができる技術を提供することにある。
【課題を解決するための手段】
【００１４】
本発明のスケジューラは、
ＴＤＭ方式のネットワークシステムを構成するスケジューラであって、
リンクあふれチェック部と
あふれ処理部と、を備え、
前記リンクあふれチェック部は、
前記ネットワークシステムを構成する各リンク毎に、各パスが要求する要求タイムスロット数の和が、該リンクに収容可能なタイムスロット数を超過した状態である要求タイムスロットあふれが生じているか否かを判定し、
前記あふれ処理部は、
前記リンクあふれチェック部にて前記要求タイムスロットあふれが生じると判定されたリンクにおいて、前記要求タイムスロット数が相対的に多いパスを優先的に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、前記要求タイムスロットあふれを解消する。
【００１５】
本発明のネットワークシステムは、
複数のノードと、前記複数のノード間を接続するリンクと、スケジューラと、を有してなるＴＤＭ方式のネットワークシステムであって、
前記スケジューラは、
リンクあふれチェック部と
あふれ処理部と、を備え、
前記リンクあふれチェック部は、
前記ネットワークシステムを構成する各リンク毎に、各パスが要求する要求タイムスロット数の和が、該リンクに収容可能なタイムスロット数を超過した状態である要求タイムスロットあふれが生じているか否かを判定し、
前記あふれ処理部は、
前記リンクあふれチェック部にて前記要求タイムスロットあふれが生じると判定されたリンクにおいて、前記要求タイムスロット数が相対的に多いパスを優先的に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、前記要求タイムスロットあふれを解消する。
【００１６】
本発明のプログラムは、
ＴＤＭ方式のネットワークシステムを構成するスケジューラに、
前記ネットワークシステムを構成する各リンク毎に、各パスが要求する要求タイムスロット数の和が、該リンクに収容可能なタイムスロット数を超過した状態である要求タイムスロットあふれが生じているか否かを判定する手順と、
前記要求タイムスロットあふれが生じると判定されたリンクにおいて、前記要求タイムスロット数が相対的に多いパスを優先的に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、前記要求タイムスロットあふれを解消する手順と、を実行させる。
【発明の効果】
【００１７】
本発明によれば、スケジューラは、要求タイムスロットあふれが生じると判定されたリンクにおいて、要求タイムスロット数が相対的に多いパスを優先的に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、要求タイムスロットあふれを解消する。
【００１８】
そのため、パス間のタイムスロット割当の公平性を担保することができるという効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】本発明のネットワークシステムの構成を示す図である。
【図２】本発明の第１の実施形態のスケジューラの構成を示す図である。
【図３】本発明の第２の実施形態のスケジューラの構成を示す図である。
【図４】本発明の第３の実施形態のスケジューラの構成を示す図である。
【図５】本発明の第４の実施形態のスケジューラの構成を示す図である。
【図６】本発明の第５の実施形態のスケジューラの構成を示す図である。
【図７】本発明の実施例の前提条件を説明する図である。
【図８】本発明の実施例１の概要を説明する図である。
【図９】本発明の実施例１の具体的な動作例の流れを説明するフロー図である。
【図１０】本発明の実施例１で減少させられる割当ＴＳの順番を説明する図である。
【図１１】本発明の実施例２の概要を説明する図である。
【図１２】本発明の実施例２の具体的な動作例の流れを説明するフロー図である。
【図１３】本発明の実施例２で減少させられる割当ＴＳの順番を説明する図である。
【図１４】本発明の実施例３の概要を説明する図である。
【図１５】本発明の実施例３の具体的な動作例の流れを説明するフロー図である。
【図１６】本発明の実施例３で減少させられる割当ＴＳの順番を説明する図である。
【図１７】本発明の実施例４の概要を説明する図である。
【図１８】従来のスケジューリング方法を説明する図である。
【図１９】従来のスケジューリング方法を説明する図である。
【図２０】従来のスケジューリング方法を説明する図である。
【図２１】従来のスケジューリング方法の流れを説明するフロー図である。
【図２２】従来のスケジューリング方法の課題を説明する図である。
【発明を実施するための形態】
【００２０】
以下に、本発明を実施するための形態について図面を参照して説明する。
【００２１】
図１に、本発明のスケジューラが適用されるネットワークシステムの構成を示す。
【００２２】
図１に示すように、本実施形態のネットワークシステムは、ノードＡ〜Ｅ間がリンクａ〜ｅによって接続されたリング型のネットワークシステムである。
【００２３】
ノードＡ〜Ｅは、それぞれホストコンピュータＨＣが接続されており、ホストコンピュータＨＣ間のデータを転送する。このとき、ノードＡ〜Ｅは、リング上の前段のノードから送られてきたデータを処理し、次段のノードへデータを送る。
【００２４】
スケジューラＳＣは、ネットワークシステム全体を管理し、リンクａ〜ｅで転送されるデータのスケジュールおよびノードＡ〜Ｅの処理スケジュールを決定する。図１では、スケジューラＳＣは、ノードＡに配置されているが、配置場所はこれに限定されない。
【００２５】
なお、本発明は、スケジューラＳＣに特徴があり、ノードＡ〜ＥおよびホストコンピュータＨＣは公知のものを使用できるため、以下では、スケジューラＳＣの構成についてのみ詳細に説明する。
【００２６】
図２に、本発明の第１の実施形態のスケジューラＳＣの構成を示す。
【００２７】
図２に示すように、本発明の第１の実施形態のスケジューラＳＣは、交流トラヒック量集計部１０１と、帯域割当部１０２と、リンクあふれチェック部１０３と、リンクあふれ対処部１０４と、リンクスケジュールテーブル１０５と、テーブル換算部１０６と、ノードスケジュールテーブル１０７と、テーブルトランスミッタ１０８と、タイマ１０９と、を有している。本発明の特徴部分は、リンクあふれチェック部１０３およびリンクあふれ対処部１０４にある。
【００２８】
交流トラヒック量集計部１０１は、各ノードＡ〜Ｅから、各パスが要求するトラヒック量を集計する。
【００２９】
帯域割当部１０２は、交流トラヒック量集計部１０１が集計した、各パスが要求するトラヒック量を要求ＴＳ数に換算し、全てのリンクａ〜ｅにおいて、各パスに要求ＴＳを割り当てる（図１８〜図２０のステップＳ１〜Ｓ３参照）。
【００３０】
リンクあふれチェック部１０３は、リンクａ〜ｅ毎に、要求ＴＳあふれ（各パスの要求ＴＳ数の和が、リンクに収容可能なＴＳ数を超過した状態）が生じているか否かを判定する。
【００３１】
リンクあふれ対処部１０４は、リンクあふれチェック部１０３が要求ＴＳあふれを生じていると判定したリンクにおいて、要求ＴＳ数が相対的に多いパスを優先的に選択し、選択したパスに割り当てる割当ＴＳ数を、合計で少なくとも要求ＴＳのあふれ数分、減少させる処理（リンクあふれ対処）を行うことで、要求ＴＳあふれを解消する。
【００３２】
これにより、各リンクａ〜ｅに要求ＴＳあふれが生じないように各パスにＴＳが割り当てられることになる。
【００３３】
帯域割当部１０２は、リンクあふれ対処部１０４によるリンクあふれ対処後、各パスのＴＳ割当結果を基に、各リンクａ〜ｅの各ＴＳにおいて、どのパスのデータを流すかを表すリンクスケジュールテーブル１０５を作成する。
【００３４】
なお、帯域割当部１０２は、リンクａ〜ｅのいずれでも要求ＴＳあふれが生じていない場合は、その旨の通知をリンクあふれチェック部１０３から受ける等した後に、リンクスケジュールテーブル１０５を作成すれば良い。
【００３５】
テーブル換算部１０６は、帯域割当部１０２が作成した、各リンクａ〜ｅのリンクスケジュールテーブル１０５を基に、各ノードＡ〜Ｅの各ＴＳにおけるノード処理の内容（データ送信、方路切替等）を表すノードスケジュールテーブル１０７を作成する（図２１のステップＳ４参照）。
【００３６】
テーブルトランスミッタ１０８は、各ノードＡ〜Ｅに対し、テーブル換算部１０６が作成した、ノードスケジュールテーブル１０７を送信する。
【００３７】
タイマ１０９は、各ノードＡ〜Ｅが処理を行う時間を管理する。
【００３８】
図３に、本発明の第２の実施形態のスケジューラＳＣの構成を示す。
【００３９】
図３に示すように、本発明の第２の実施形態のスケジューラＳＣは、第１の実施の形態に対し、あふれ対処履歴保持部１１０を追加した点に特徴がある。
【００４０】
あふれ対処履歴保持部１１０は、リンクあふれ対処部１０４による前回のリンクあふれ対処の履歴（例えば、割当ＴＳ数を減少させたパス等）を保持する。
【００４１】
第２の実施形態では、リンクあふれ対処部１０４は、前回のリンクあふれ対処の履歴を利用して、リンクあふれ対処を行うことができる。
【００４２】
図４に、本発明の第３の実施形態のスケジューラＳＣの構成を示す。
【００４３】
図４に示すように、本発明の第３の実施形態のスケジューラＳＣは、第１の実施の形態に対し、割当履歴保持部１１１を追加した点に特徴がある。
【００４４】
割当履歴保持部１１１は、帯域割当部１０２による過去のＴＳ割当の履歴（例えば、各パスの要求ＴＳ数と割当ＴＳ数との関係等）を保持する。
【００４５】
第３の実施形態では、リンクあふれ対処部１０４は、過去のＴＳ割当の履歴を利用して、リンクあふれ対処を行うことができる。
【００４６】
図５に、本発明の第４の実施形態のスケジューラＳＣの構成を示す。
【００４７】
図５に示すように、本発明の第４の実施形態のスケジューラＳＣは、第１の実施の形態に対し、第２の実施形態のあふれ対処履歴保持部１１０と、第３の実施形態の割当履歴保持部１１１と、を追加した点に特徴がある。
【００４８】
第４の実施形態では、リンクあふれ対処部１０４は、前回のリンクあふれ対処の履歴および過去のＴＳ割当の履歴のいずれか、もしくは両方を利用して、リンクあふれ対処を行うことができる。
【００４９】
図６に、本発明の第５の実施形態のスケジューラＳＣの構成を示す。
【００５０】
図６に示すように、本発明の第５の実施形態のスケジューラＳＣは、リンクあふれチェック部１０３を帯域割当部１０２に接続した第１の実施の形態に対し、リンクあふれチェック部１０３をリンクスケジュールテーブル１０５に接続した点に特徴がある。
【００５１】
第１の実施形態では、リンクあふれ対処部１０４は、リンクスケジュールテーブル１０５の作成前にリンクあふれ対処を行う必要があったが、第５の実施形態では、リンクスケジュールテーブル１０５の作成時や作成後等に適宜リンクあふれ対処を行うことができる。
【００５２】
なお、第５の実施形態では、第２から第４の実施形態のように、あふれ対処履歴保持部１１０および割当履歴保持部１１１のいずれか、もしくは両方を追加しても良い。
【実施例】
【００５３】
以下、本発明の具体的な実施例について説明する。
【００５４】
ここでは、説明の便宜上、図７に示すように、ネットワークシステムが単方向リングの構成であり、リンクあたりで同一スロットに同時に接続可能なチャネルは１つ（ファイバ多重や波長多重を行わない）であるものとする。ただし、本発明は、これに限定されず、双方向リングをはじめ任意トポロジおよび波長多重を行った場合にも適用可能である（各ファイバの各波長についてリンクスケジュールテーブル１０５が作成される）。
【００５５】
また、ＴＳ長が１００μｓ、フレーム長が５ｍｓであるとする。よって、各リンクに収容可能なＴＳ数の上限は５０となる。
【００５６】
また、各パスにパスＩＤを定義し、各パスの要求パス数は図７の通りとする。例えば、ノードＡ→ノードＢのパスは、パスＩＤが１で、要求ＴＳ数は５である。
【００５７】
また、要求ＴＳあふれが生じているリンク（図７では、リンクａ，ｅ，ｄ）について、順次、リンクあふれ対処を行うものとする。
【００５８】
また、リンクあふれ対処では、リンクには可能な限り要求ＴＳを収容し、かつ各パスの割当ＴＳ数が略均一になるようにして、パス間の公平性を担保することを前提とする。
【００５９】
例えば、リンクａの場合、リンクａを通るパス集合は、図７右側の通りである。このとき、リンクａに２ＴＳ分の要求ＴＳあふれが生じている場合、少なくとも２つの割当パスを減少させる必要がある。そこで、リンクあふれ対処部１０４は、リンクａを通るパスの中で、どのパスの割当ＴＳをどれだけ減少させるか決定する。
【００６０】
本発明の実施例では、リンクあふれ対処部１０４によるリンクあふれ対処において、割当ＴＳを減少させるパスを選択する方法として、以下の４つの方法のいずれかを行うものとする。
【００６１】
Ａ）ラウンドロビン方式でパスを選択する方法（以下、Ｆｉｒｓｔ  Ｆｉｔベースの方法と称す）
Ｂ）ランダムにパスを選択する方法（以下、Ｒａｎｄｏｍ  Ｆｉｔベースの方法と称す）
Ｃ）ソーティング後にパスを選択する方法（以下、ソーティングベースの方法と称す）
Ｄ）Ａ）〜Ｃ）のいずれかの方法において過去の履歴も利用してパスを選択する方法
（１）実施例１
実施例１は、上記のＡ）のＦｉｒｓｔ  Ｆｉｔベースの方法を用いるもので、第２の実施形態または第４の実施形態のスケジューラＳＣの構成で実現される。
【００６２】
図８に、実施例１の概要を示す。
【００６３】
図８に示すように、実施例１では、リンクあふれ対処部１０４は、１フレーム中のＴＳ数（リンクに収容可能なＴＳ数）Ｓを、リンクを通るパスの数で割った値である公平ＴＳ数Ｓfを導出する。言い換えれば、Ｓfは、Ｓをパス間で公平に分け合った場合に、それぞれのパスに割り当てられるＴＳ数を表す。
【００６４】
例えば、Ｓ＝５０を、リンクａを通る１０本のパスで分け合う場合、Ｓf＝５となる。
【００６５】
また、実施例１では、リンクあふれ対処部１０４は、各パスに優先順位（図８では、パスＩＤの昇順）を付与し、要求ＴＳ数がＳｆを超過しているパスの中から、優先順位が高い順にパスを選択し、割当ＴＳ数を減少させていく。ただし、割当ＴＳ数の下限値をＳfとし、Ｓf未満まで減少させることはしない。
【００６６】
例えば、図８の例では、パスＩＤが１，２，３のパスにおいて、要求パス数がＳfを超過しているため、リンクあふれ対処部１０４は、この順に割当ＴＳ数を減少させていく。
【００６７】
このとき、あふれ対処履歴保持部１１０は、前回のリンクあふれ対処の履歴として、割当ＴＳ数を減少させたパスのパスＩＤを保持しておく。次回のリンクあふれ対処では、パスＩＤが保持されたパスの次のパスの優先順位を最も高くし、以降のパスの優先順位を低くしていく。これにより、毎回、特定のパスだけが割当ＴＳ数を減少させられる状況を回避することができる。
【００６８】
図９に、実施例１の具体的な動作例の流れを示す。なお、図９では、あるパスのパスＩＤをｐ（ｐ＝１，２，．．．）と表す。また、パスＩＤがｐのパスの要求ＴＳ数をｒｅｑ（ｐ）、割当ＴＳ数をａｓｓｉｇｎ（ｐ）と表す。また、あるリンクのリンクＩＤをｋ（ｋ＝ａ，ｂ，．．．）と表す。
【００６９】
図９に示すように、まず、帯域割当部１０２は、全てのリンクａ〜ｅにおいて、各パスにＴＳを割り当てる（ステップＡ１）。この時点では、各パスに割り当てる割当ＴＳ数は、各パスが要求する要求ＴＳ数と同数になっている。
【００７０】
次に、リンクあふれチェック部１０３は、リンクａを注目リンクとし（ステップＡ２）、注目リンクに要求ＴＳあふれが生じているか否かを判定する（ステップＡ３）。
【００７１】
ステップＡ３において、注目リンクに要求ＴＳあふれが生じていなければ、リンクあふれチェック部１０３は、ネットワークシステム内に要求ＴＳあふれが未チェックのリンクがあるか否を判定し（ステップＡ４）、未チェックのリンクがあれば次のリンクを注目リンクとして（ステップＡ５）、ステップＡ３に戻り、未チェックのリンクがなければ処理を終了する。
【００７２】
一方、ステップＡ３において、注目リンクに要求ＴＳあふれが生じていれば、リンクあふれ対処部１０４は、要求ＴＳのあふれ数Ｘ（ｋ）をチェックする（ステップＡ６）。
【００７３】
次に、リンクあふれ対処部１０４は、あるパスのパスＩＤを示すｐrを１増加させる（ステップＡ７）。ここで、ｐrは、前回のリンクあふれ対処で最後に割当ＴＳを減少させたパスのパスＩＤに相当し、あふれ対処履歴保持部１１０に保持されている。また、ステップＡ７では、初回のリンクあふれ対処の場合は、ｐrを初期値である１にし、また、ｐrが最後のパスＩＤである場合は、ｐrを初期値である１に戻す。
【００７４】
次に、リンクあふれ対処部１０４は、ｐrのパスが注目リンクを通るパスであるか否かを判定する（ステップＡ８）。なお、リンクあふれ対処部１０４は、各リンクａ〜ｅを通るパスを事前に記憶しているものとする。
【００７５】
ステップＡ８において、ｐrのパスが注目リンクを通るパスでなければステップＡ７に戻る。
【００７６】
一方、ステップＡ８において、ｐrのパスが注目リンクを通るパスであれば、リンクあふれ対処部１０４は、ｐrのパスの割当ＴＳ数（この時点では、要求ＴＳ数と同数）を示すａｓｓｉｇｎ（ｐr）が、公平ＴＳ数であるＳf（ｋ）を超過しているか否かを判定する（ステップＡ９）。
【００７７】
ステップＡ９において、ａｓｓｉｇｎ（ｐr）がＳf（ｋ）を超過していなければステップＡ７に戻る。
【００７８】
一方、ステップＡ９において、ａｓｓｉｇｎ（ｐr）がＳf（ｋ）を超過していれば、リンクあふれ対処部１０４は、｛ａｓｓｉｇｎ（ｐr）−Ｓf（ｋ）｝が、Ｘ（ｋ）よりも多いか否かを判定する（ステップＡ１０）。以下では、ステップＡ１０の右辺の｛ａｓｓｉｇｎ（ｐr）−Ｓf（ｋ）｝をＹk（ｐr）とおく。
【００７９】
ステップＡ１０において、Ｙk（ｐr）がＸ（ｋ）よりも多ければ、リンクあふれ対処部１０４は、ａｓｓｉｇｎ（ｐr）をＸ（ｋ）だけ減少させて（ステップＡ１１）、ステップＡ４に戻る。
【００８０】
一方、ステップＡ１０において、Ｙk（ｐr）がＸ（ｋ）よりも多くなければ、リンクあふれ対処部１０４は、ａｓｓｉｇｎ（ｐr）をＹk（ｐr）だけ減少させ（ステップＡ１２）、Ｘ（ｋ）をＹk（ｐr）だけ減少させて（ステップＡ１３）、ステップＡ７に戻る。
【００８１】
その結果、図９の例では、リンクあふれ対処部１０４は、図１０に示すような順番で、割当ＴＳを減少させていくことになる。なお、あふれ数が３ＴＳ以上６ＴＳ以下であった場合、最後に割当ＴＳを減少させたのはパスＩＤが２のパスであり、このパスＩＤがあふれ対処履歴保持部１１０に保持される。この場合、リンクあふれ対処部１０４は、次回のリンクあふれ対処では、パスＩＤが３のパスの優先順位を最も高くし、このパスから順に、割当ＴＳ数を減少させていく。
【００８２】
上述のように、実施例１では、前回のリンクあふれ対処の履歴を利用するため、割当ＴＳ数を減少させるパスは、その都度、変更される。
【００８３】
また、実施例１では、公平ＴＳ数Ｓfを導入しているため、あるタイミングであるパスの割当ＴＳ数を過度に減少させて、過剰な不公平が生じるような状況は回避される。
【００８４】
よって、パス間のＴＳ割当の公平性を担保することができる。
【００８５】
また、実施例１では、各パスの優先順位としてパスＩＤを用いれば、各パスをソートする必要がないため、リンクあふれ対処の計算時間の短縮化を図れる。
（２）実施例２
実施例２は、上記のＢ）のＲａｎｄｏｍ  Ｆｉｔベースの方法を用いるもので、第１の実施形態または第５の実施形態のスケジューラＳＣの構成で実現される。
【００８６】
図１１に、実施例２の概要を示す。
【００８７】
図１１に示すように、実施例２では、リンクあふれ対処部１０４は、実施例１と同様に、公平ＴＳ数Ｓfを導出する。
【００８８】
また、実施例２では、リンクあふれ対処部１０４は、要求ＴＳがＳｆを超過しているパスの中から、毎回、ランダムにパスを選択し、割当ＴＳ数を減少させていく。ただし、実施例１と同様に、リンクあふれ対処を行う場合、割当ＴＳ数の下限値をＳfとし、Ｓf未満まで減少させることはしない。
【００８９】
図１２に、実施例２の具体的な動作例の流れを示す。なお、図１２では、あるパスのパスＩＤをｐ（ｐ＝１，２，．．．）と表す。また、パスＩＤがｐのパスの要求ＴＳ数をｒｅｑ（ｐ）、割当ＴＳ数をａｓｓｉｇｎ（ｐ）と表す。また、あるリンクのリンクＩＤをｋ（ｋ＝ａ，ｂ，．．．）と表す。
【００９０】
図１２に示すように、まず、帯域割当部１０２は、全てのリンクａ〜ｅにおいて、各パスにＴＳを割り当てる（ステップＢ１）。この時点では、各パスに割り当てる割当ＴＳ数は、各パスが要求する要求ＴＳ数と同数になっている。
【００９１】
次に、リンクあふれチェック部１０３は、リンクａを注目リンクとし（ステップＢ２）、注目リンクに要求ＴＳあふれが生じているか否かを判定する（ステップＢ３）。
【００９２】
ステップＢ３において、注目リンクに要求ＴＳあふれが生じていなければ、リンクあふれチェック部１０３は、ネットワークシステム内に要求ＴＳあふれが未チェックのリンクがあるか否を判定し（ステップＢ４）、未チェックのリンクがあれば次のリンクを注目リンクとして（ステップＢ５）、ステップＢ３に戻り、未チェックのリンクがなければ処理を終了する。
【００９３】
一方、ステップＢ３において、注目リンクに要求ＴＳあふれが生じていれば、リンクあふれ対処部１０４は、要求ＴＳのあふれ数Ｘ（ｋ）をチェックする（ステップＢ６）。
【００９４】
次に、リンクあふれ対処部１０４は、注目リンクを通るパスの中から、１本のパスをランダムに選択する（ステップＢ７）。ここでは、選択したパスのパスＩＤをｐrとする。なお、リンクあふれ対処部１０４は、各リンクａ〜ｅを通るパスを事前に記憶しているものとする。
【００９５】
次に、リンクあふれ対処部１０４は、ｐrのパスの割当ＴＳ数（この時点では、要求ＴＳ数と同数）を示すａｓｓｉｇｎ（ｐr）が、公平ＴＳ数であるＳf（ｋ）を超過しているか否かを判定する（ステップＢ８）。
【００９６】
ステップＢ８において、ａｓｓｉｇｎ（ｐr）がＳf（ｋ）を超過していなければステップＢ７に戻る。
【００９７】
一方、ステップＢ８において、ａｓｓｉｇｎ（ｐr）がＳf（ｋ）を超過していれば、リンクあふれ対処部１０４は、｛ａｓｓｉｇｎ（ｐr）−Ｓf（ｋ）｝が、Ｘ（ｋ）よりも多いか否かを判定する（ステップＢ９）。以下では、ステップＢ９の右辺の｛ａｓｓｉｇｎ（ｐr）−Ｓf（ｋ）｝をＹk（ｐr）とおく。
【００９８】
ステップＢ９において、Ｙk（ｐr）がＸ（ｋ）よりも多ければ、リンクあふれ対処部１０４は、ａｓｓｉｇｎ（ｐr）をＸ（ｋ）だけ減少させて（ステップＢ１０）、ステップＢ４に戻る。
【００９９】
一方、ステップＢ９において、Ｙk（ｐr）がＸ（ｋ）よりも多くなければ、リンクあふれ対処部１０４は、ａｓｓｉｇｎ（ｐr）をＹk（ｐr）だけ減少させ（ステップＢ１１）、Ｘ（ｋ）をＹk（ｐr）だけ減少させて（ステップＢ１２）、ステップＢ７に戻る。
【０１００】
その結果、図１２の例では、リンクあふれ対処部１０４は、図１３に示すような順番で、割当ＴＳを減少させていくことになる。
【０１０１】
上述のように、実施例２では、パスの選択にランダム性を利用するため、特定のパスだけが割当ＴＳ数を減少させられることが回避される。
【０１０２】
また、実施例２では、公平ＴＳ数Ｓfを導入しているため、あるタイミングであるパスの割当ＴＳ数を過度に減少させて、過剰な不公平が生じるような状況は回避される。
【０１０３】
よって、パス間のＴＳ割当の公平性を担保することができる。
【０１０４】
また、実施例２では、各パスをソートする必要がないため、リンクあふれ対処の計算時間の短縮化を図れる。
（３）実施例３
実施例３は、上記のＣ）のソーティングベースの方法を用いるもので、第１の実施形態または第５の実施形態のスケジューラＳＣの構成で実現される。
【０１０５】
図１４に、実施例３の概要を示す。
【０１０６】
図１４に示すように、実施例３では、リンクあふれ対処部１０４は、各パスの要求ＴＳ数が多い順に、各パスをソートする。
【０１０７】
その上で、リンクあふれ対処部１０４は、要求ＴＳ数が多いパスについて、優先的に割当ＴＳ数を減少させる。
【０１０８】
この方法としては、例えば、以下の３通りが考えられる。
【０１０９】
ｉ）各パスの割当ＴＳを略均一化する。
【０１１０】
ｉｉ）ｉ）に加えて、要求ＴＳ数が多いパス（要求ＴＳ数が第１の閾値よりも多いパス）の割当ＴＳ数を増加させる。この場合、この増加数分だけ、他のパスの割当ＴＳ数を減少させる。
【０１１１】
ｉｉｉ）ｉ）に加えて、要求ＴＳ数が過度に多いパス（要求ＴＳ数が第２の閾値（＞第１の閾値）よりも多いパス）の割当ＴＳ数を、ペナルティとしてさらに減少させる。この場合、この減少数分だけ、他のパスの割当ＴＳ数を増加させる。
【０１１２】
図１５に、実施例３の具体的な動作例の流れを示す。なお、図１５は、上記のｉ）の方法を実現する場合の流れを示している。また、図１５では、あるパスのソート前のパスＩＤをｐ（ｐ＝１，２，．．．）、ソート後のパスＩＤをｐ’（ｐ’＝１，２，．．．）と表す。また、ソート後のパスＩＤがｐ’のパスの要求ＴＳ数をｒｅｑ（ｐ’）、割当ＴＳ数をａｓｓｉｇｎ（ｐ’）と表す。
【０１１３】
図１５に示すように、まず、帯域割当部１０２は、全てのリンクａ〜ｅにおいて、各パスにＴＳを割り当てる（ステップＣ１）。この時点では、各パスに割り当てる割当ＴＳ数は、各パスが要求する要求ＴＳ数と同数になっている。
【０１１４】
次に、リンクあふれチェック部１０３は、リンクａを注目リンクとし（ステップＣ２）、注目リンクに要求ＴＳあふれが生じているか否かを判定する（ステップＣ３）。
【０１１５】
ステップＣ３において、注目リンクに要求ＴＳあふれが生じていなければ、リンクあふれチェック部１０３は、ネットワークシステム内に要求ＴＳあふれが未チェックのリンクがあるか否を判定し（ステップＣ４）、未チェックのリンクがあれば次のリンクを注目リンクとして（ステップＣ５）、ステップＣ３に戻り、未チェックのリンクがなければ処理を終了する。
【０１１６】
一方、ステップＣ３において、注目リンクに要求ＴＳあふれが生じていれば、リンクあふれ対処部１０４は、各パスを要求ＴＳ数が多い順にソートする（ステップＣ６）。このとき、リンクあふれ対処部１０４は、各パスに対し、要求ＴＳ数が多い順にパスＩＤを付し直す。これにより、各パスのパスＩＤは、ｐ→ｐ’に変更される。
【０１１７】
次に、リンクあふれ対処部１０４は、ｐ’＝１とし（ステップＣ７）、ｐ’のパスが注目リンクを通るパスであるか否かを判定する（ステップＣ８）。なお、リンクあふれ対処部１０４は、各リンクａ〜ｅを通るパスを事前に記憶しているものとする。
【０１１８】
ステップＣ８において、ｐ’のパスが注目リンクを通るパスでなければ、リンクあふれ対処部１０４は、ｐ’を１増加させて（ステップＣ９）、ステップＣ８に戻る。
【０１１９】
一方、ステップＣ８において、ｐ’のパスが注目リンクを通るパスであれば、リンクあふれ対処部１０４は、ｐ’のパスの割当ＴＳ数（この時点では、要求ＴＳ数と同数）を示すａｓｓｉｇｎ（ｐ’）を１減少させ（ステップＣ１０）、その上で、注目リンクの要求ＴＳあふれが解消したか否かを判定する（ステップＣ１１）。
【０１２０】
ステップＣ１１において、注目リンクの要求ＴＳあふれが解消していればステップＣ４に戻る。
【０１２１】
一方、ステップＣ１１において、注目リンクの要求ＴＳあふれが解消していなければ、リンクあふれ対処部１０４は、ｐ’のパスのａｓｓｉｇｎ（ｐ’）が、ｐ’＋１のパスのａｓｓｉｇｎ（ｐ’＋１）よりも少ないか否かを判定する（ステップＣ１２）。
【０１２２】
ステップＣ１２において、ａｓｓｉｇｎ（ｐ’）がａｓｓｉｇｎ（ｐ’＋１）よりも少なくなければ、ステップＣ１０に戻る。
【０１２３】
一方、ステップＣ１２において、ａｓｓｉｇｎ（ｐ’）がａｓｓｉｇｎ（ｐ’＋１）よりも少なければ、リンクあふれ対処部１０４は、ｐ’を１増加させて（ステップＣ９）、ステップＣ８に戻る。
【０１２４】
その結果、図１５の例では、リンクあふれ対処部１０４は、図１６に示すような順番で、割当ＴＳを減少させていくことになる。
【０１２５】
なお、上記のｉｉ）の方法を実現する場合、例えば、図１５に示した上記のｉ）の方法で要求ＴＳあふれを解消した後、要求ＴＳ数が第１の閾値よりも多いパスの割当ＴＳ数を増加させ、この増加数分だけ、他のパスの割当ＴＳ数を減少させればよい。
【０１２６】
また、上記のｉｉｉ）の方法を実現する場合、例えば、図１５に示した上記のｉ）の方法で要求ＴＳあふれを解消した後、要求ＴＳ数が第２の閾値（＞第１の閾値）よりも多いパスの割当ＴＳ数を減少させ、この減少数分だけ、他のパスの割当ＴＳ数を増加させればよい。
【０１２７】
上述のように、実施例３では、各パスの要求ＴＳ数に応じて、各パスをソートし、要求ＴＳ数が多いパスを優先的に割当ＴＳを減少させる。
【０１２８】
よって、パス間のＴＳ割当の公平性を担保することができる。
（４）実施例４
実施例４は、上記のＤ）の過去の履歴を利用する方法を用いるものである。
【０１２９】
実施例４で利用する過去の履歴とは、あふれ対処履歴保持部１１０に保持された前回のリンクあふれ対処の履歴、および、割当履歴保持部１１１に保持された過去のＴＳ割当の履歴のいずれか、もしくは両方である。
【０１３０】
そのため、実施例４は、前回のリンクあふれ対処の履歴のみを利用する場合は、第２の実施形態のスケジューラＳＣの構成で実現され、過去のＴＳ割当の履歴のみを利用する場合は、第３の実施形態のスケジューラＳＣの構成で実現され、両方の履歴を利用する場合は、第４の実施形態のスケジューラＳＣの構成で実現される。
【０１３１】
図１７に、実施例４の概要を示す。なお、図１７は、上記のＣ）のソーティングベースの方法において、過去のＴＳ割当の履歴（各パスの要求ＴＳ数と割当ＴＳ数との関係）を利用する場合の方法を示している。
【０１３２】
図１７に示すように、まず、リンクあふれ対処部１０４は、各パスを要求ＴＳ数が多い順にソートする。このとき、要求ＴＳ数ｒｅｑ（ｐ）がＳg未満のパスについては、割当ＴＳ数を減少させる対象から外す。なお、Ｓgは、実施例１，２で用いた公平ＴＳ数Ｓfでも、固定値でも良く、図１７では２としている。
【０１３３】
次に、リンクあふれ対処部１０４は、割当履歴保持部１１１に保持された過去のＴＳ割当の履歴を基に、各パスにつき、前回の要求ＴＳ数と割当ＴＳとの差と、過去１０回の要求ＴＳ数と割当ＴＳとの差の合計と、を求める。
【０１３４】
次に、リンクあふれ対処部１０４は、今回の要求ＴＳ数（Ａ）と、前回の要求ＴＳ数と割当ＴＳとの差（Ｂ）と、過去１０回の要求ＴＳ数と割当ＴＳとの差の合計（Ｃ）と、を用いて、各パスをソートする。
【０１３５】
このとき、例えば、リンクあふれ対処部１０４は、各パスにつき、αＡ＋βＢ＋γＣの値を算出し、算出した値に応じて各パスをソートする。なお、α、β、γは、（α＞＞β＞＞γ）の関係を満たす定数である。
【０１３６】
その後、リンクあふれ対処部１０４は、ソートした順に、各パスの割当ＴＳ数を減少させていく。なお、この場合、各パスの割当ＴＳ数を減少させる方法としては、実施例１のように、あるパスを公平ＴＳ数Ｓf未満にならないように減少させてから次のパスに移る方法等が考えられるが、特に制限はない。
【０１３７】
なお、図１７では、過去の履歴として、前回の要求ＴＳ数と割当ＴＳとの差（Ｂ）と、過去１０回の要求ＴＳ数と割当ＴＳとの差の合計（Ｃ）と、の両方を用いているが、いずれか一方を用いても良い。
【０１３８】
上述のように、実施例４では、過去の割当履歴を利用して、割当ＴＳ数を減少させるパスが選択される。
【０１３９】
そのため、例えば、過去にパス間のＴＳ割当に不公平が生じたとしても、その不公平を解消していくことが可能である。
【０１４０】
よって、長いスパンにわたって、パス間のＴＳ割当の公平性を担保することができる。
【０１４１】
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明の要旨を逸脱しない範囲で当業者が理解し得る各種の変形が可能である。
【０１４２】
例えば、本発明のスケジューラＳＣにて行われる方法は、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１４３】
Ａ〜Ｅ    ノード
ａ〜ｅ    リンク
ＨＣ    ホストコンピュータ
ＳＣ    スケジューラ
１０１    交流トラヒック量集計部
１０２    帯域割当部
１０３    リンクあふれチェック部
１０４    リンクあふれ対処部
１０５    リンクスケジュールテーブル
１０６    テーブル換算部
１０７    ノードスケジュールテーブル
１０８    テーブルトランスミッタ
１０９    タイマ
１１０    あふれ対処履歴保持部
１１１    割当履歴保持部
【図２】
0005756055.tif 000002
【図３】
0005756055.tif 000003
【図４】
0005756055.tif 000004
【図５】
0005756055.tif 000005
【図６】
0005756055.tif 000006
【図７】
0005756055.tif 000007
【図８】
0005756055.tif 000008
【図９】
0005756055.tif 000009
【図１０】
0005756055.tif 000010
【図１１】
0005756055.tif 000011
【図１２】
0005756055.tif 000012
【図１３】
0005756055.tif 000013
【図１４】
0005756055.tif 000014
【図１５】
0005756055.tif 000015
【図１６】
0005756055.tif 000016
【図１７】
0005756055.tif 000017
【図１８】
0005756055.tif 000018
【図１９】
0005756055.tif 000019
【図２０】
0005756055.tif 000020
【図２１】
0005756055.tif 000021
【図２２】
0005756055.tif 000022
【図１】
0005756055.tif 000023