JP5756055B2 - スケジューラ、ネットワークシステム、プログラム - Google Patents

Description

本発明は、ＴＤＭ（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未満にならないように減少させてから次のパスに移る方法等が考えられるが、特に制限はない。

なお、図１７では、過去の履歴として、前回の要求ＴＳ数と割当ＴＳとの差（Ｂ）と、過去１０回の要求ＴＳ数と割当ＴＳとの差の合計（Ｃ）と、の両方を用いているが、いずれか一方を用いても良い。

上述のように、実施例４では、過去の割当履歴を利用して、割当ＴＳ数を減少させるパスが選択される。

そのため、例えば、過去にパス間のＴＳ割当に不公平が生じたとしても、その不公平を解消していくことが可能である。

よって、長いスパンにわたって、パス間のＴＳ割当の公平性を担保することができる。

以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明の要旨を逸脱しない範囲で当業者が理解し得る各種の変形が可能である。

例えば、本発明のスケジューラＳＣにて行われる方法は、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。

Ａ〜Ｅ ノード
ａ〜ｅ リンク
ＨＣ ホストコンピュータ
ＳＣ スケジューラ
１０１ 交流トラヒック量集計部
１０２ 帯域割当部
１０３ リンクあふれチェック部
１０４ リンクあふれ対処部
１０５ リンクスケジュールテーブル
１０６ テーブル換算部
１０７ ノードスケジュールテーブル
１０８ テーブルトランスミッタ
１０９ タイマ
１１０ あふれ対処履歴保持部
１１１ 割当履歴保持部

Claims (4)

1. ＴＤＭ方式のネットワークシステムを構成するスケジューラであって、
   リンクあふれチェック部と
   あふれ処理部と、を備え、
   前記リンクあふれチェック部は、
   前記ネットワークシステムを構成する各リンク毎に、各パスが要求する要求タイムスロット数の和が、該リンクに収容可能なタイムスロット数を超過した状態である要求タイムスロットあふれが生じているか否かを判定し、
   前記あふれ処理部は、
   前記リンクあふれチェック部にて前記要求タイムスロットあふれが生じると判定されたリンクにおいて、前記要求タイムスロット数が相対的に多いパスを選択順に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、前記要求タイムスロットあふれを解消する際に、
   各パスの前記要求タイムスロット数に加えて、前回のあふれ対処で前記割当タイムスロット数を減少させたパスの履歴と、各パスの過去の前記要求タイムスロット数と前記割当タイムスロット数との関係の履歴と、のいずれかもしくは両方を用いて、各パスの前記選択順を決定する、スケジューラ。
2. 前記あふれ処理部は、
   前記リンクに収容可能なタイムスロット数を、該リンクを通るパスの数で割った値である公平タイムスロット数を導出し、
   前記要求タイムスロット数が前記公平タイムスロット数を超えるパスの中から、前記選択順にしたがってパスを選択し、選択したパスの前記割当タイムスロット数を、前記公平タイムスロット数を下限値として減少させる処理を、前記要求タイムスロットあふれが解消されるまで繰り返す、請求項１に記載のスケジューラ。
3. 複数のノードと、前記複数のノード間を接続するリンクと、スケジューラと、を有してなるＴＤＭ方式のネットワークシステムであって、
   前記スケジューラは、
   リンクあふれチェック部と
   あふれ処理部と、を備え、
   前記リンクあふれチェック部は、
   前記ネットワークシステムを構成する各リンク毎に、各パスが要求する要求タイムスロット数の和が、該リンクに収容可能なタイムスロット数を超過した状態である要求タイムスロットあふれが生じているか否かを判定し、
   前記あふれ処理部は、
   前記リンクあふれチェック部にて前記要求タイムスロットあふれが生じると判定されたリンクにおいて、前記要求タイムスロット数が相対的に多いパスを選択順に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、前記要求タイムスロットあふれを解消する際に、
   各パスの前記要求タイムスロット数に加えて、前回のあふれ対処で前記割当タイムスロット数を減少させたパスの履歴と、各パスの過去の前記要求タイムスロット数と前記割当タイムスロット数との関係の履歴と、のいずれかもしくは両方を用いて、各パスの前記選択順を決定する、ネットワークシステム。
4. ＴＤＭ方式のネットワークシステムを構成するスケジューラに、
   前記ネットワークシステムを構成する各リンク毎に、各パスが要求する要求タイムスロット数の和が、該リンクに収容可能なタイムスロット数を超過した状態である要求タイムスロットあふれが生じているか否かを判定する手順と、
   前記要求タイムスロットあふれが生じると判定されたリンクにおいて、前記要求タイムスロット数が相対的に多いパスを選択順に選択し、選択したパスに割り当てる割当タイムスロット数を減少させる処理であるあふれ対処を実行し、前記要求タイムスロットあふれを解消する際に、
   各パスの前記要求タイムスロット数に加えて、前回のあふれ対処で前記割当タイムスロット数を減少させたパスの履歴と、各パスの過去の前記要求タイムスロット数と前記割当タイムスロット数との関係の履歴と、のいずれかもしくは両方を用いて、各パスの前記選択順を決定する手順と、を実行させるためのプログラム。