経路割当装置および経路割当方法
【課題】通信効率の向上を図る。
【解決手段】経路割当装置１０は、経路算出部１１と経路割当制御部１２を備える。経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、通信スロットに経路を割当てる。また、経路割当制御部１２は、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当を選択し、経路割当後、選択された通信スロットに対する経路の割当可能な数を求めて、期待値を更新する。
【解決手段】経路割当装置１０は、経路算出部１１と経路割当制御部１２を備える。経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、通信スロットに経路を割当てる。また、経路割当制御部１２は、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当を選択し、経路割当後、選択された通信スロットに対する経路の割当可能な数を求めて、期待値を更新する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ通信を行う経路割当装置および経路割当を行う経路割当方法に関する。
【背景技術】
【０００２】
インターネット等によるマルチメディアサービスの拡大に伴い、ネットワーク上を流れる情報量は飛躍的に増大し、情報通信ネットワークを流れるトラフィックは大きく増加している。
【０００３】
トラフィックが増加すると、例えば、ネットワークを構成するルータの内部では、同時に到着するパケット数が増えて、パケットのバッファリング回数が増えたり、またはルーティングテーブルにもとづく経路計算の制御にかかる負荷が増大したりすることになる。
【０００４】
このため、ルータ内には、パケットバッファに用いるための大容量メモリや、経路計算に用いるための高速メモリといった、消費電力の大きなメモリデバイスが配置されていた。
【０００５】
近年になって、省電力ネットワークの構築を望む声は多いが、上記のように、ネットワーク全体の消費電力は、特にルータにおける消費電力が大きく影響しており、ルータの消費電力をいかに低減するかがネットワーク省電力化の鍵といえる。
【０００６】
従来技術として、経路リストのすべての経路の振り分け割合を計算してルーティングテーブルを作成し、周期的に更新する技術が提案されている（特許文献１）。また、自局と宛先とに割り付けられた帯域と、宛先以外のノードに割り付けられた帯域とから伝送帯域を算出し、伝送帯域の範囲で情報を送信する技術が提案されている（特許文献２）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平１１−２３９１８１号公報
【特許文献２】特開２００２−２４７０９２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
省電力ネットワークを構築する場合、ネットワークの管理を行うサーバ側で、送信すべきパケットのスロット（タイムスロット）をあらかじめ割当て、時分割ベースでパケット転送を行う通信方式が考えられる。
【０００９】
これは、サーバが、どの時間で、どこの送信元からどこの宛先へ行くのかといったパケット転送のスケジューリングをしておいてから、パケット送出を行うものである。
このような制御を行うことにより、例えば、ルータに複数パケットが同時に到着するといった状態の発生頻度を低減させることができ、バッファリング回数を減少させることができる。このため、パケットバッファとして使用されていた消費電力の大きな大容量メモリをルータから排除することが可能になる。
【００１０】
また、例えば、ルータ自身が、従来行われていたような経路計算を実行せずに済むので、経路計算に要する負荷の軽減を図ることもでき、経路計算時に使用されていた消費電力の大きな高速メモリを不要とすることが可能になる。なお、上記では、ルータの消費電力に注目して説明したが、ネットワークを構成するスイッチの消費電力についても同様の理由で低減可能である。
【００１１】
一方、スケジューリングを行う場合に、ネットワークのトラフィック変動に伴う経路の増加に対応できるように、あとどれくらいの経路をスロットに割当てることができるかの指標をあらかじめ算出しておき、その指標にもとづいて経路を割当てるとしたスケジューリングを行うことが考えられる。これにより、運用中において経路割当の追加要求があった場合にも柔軟に対応することができる。
【００１２】
また、運用中に経路の割当を行った後には、次の経路割当要求に備えて、経路を割当てた現在の状態に対して、あとどれくらいの経路をスロットに割当てることができるかの指標を、あらためて算出して最適化しておくことが望ましい。
【００１３】
しかし、経路とスロットとの任意の組合せから上記の指標を求めるための計算量は大きく、ネットワーク構成が複雑になるほど、計算量は大きいものとなる。このため、運用時に経路追加要求がある度に、運用前に実施していた、計算量の大きなスケジューリングを再度行って、経路割当の最適化を図ろうとすると、リアルタイムに応答することができず、また通信効率も低下するといった問題があった。
【００１４】
本発明はこのような点に鑑みてなされたものであり、経路割当を高速に行って通信効率の向上を図った経路割当装置を提供することを目的とする。
また、本発明の他の目的は、経路割当を高速に行って通信効率の向上を図った経路割当方法を提供することである。
【課題を解決するための手段】
【００１５】
上記課題を解決するために、経路割当装置が提供される。この経路割当装置は、ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、通信スロットに前記経路を割当てる経路割当制御部とを備える。前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する。
【発明の効果】
【００１６】
通信効率の向上を図ることが可能になる。
【図面の簡単な説明】
【００１７】
【図１】経路割当装置の構成例を示す図である。
【図２】ネットワーク構成例を示す図である。
【図３】経路テーブルを示す図である。
【図４】スロットが使用している経路を示す図である。
【図５】スロットが使用している経路を示す図である。
【図６】スロットが使用している経路を示す図である。
【図７】経路割当数テーブルを示す図である。
【図８】経路割当数テーブルを示す図である。
【図９】期待値テーブルを示す図である。
【図１０】更新後の経路割当数テーブルを示す図である。
【図１１】更新後の経路割当数テーブルを示す図である。
【図１２】更新後の期待値テーブルを示す図である。
【図１３】運用前の動作シーケンスを示す図である。
【図１４】運用時の動作シーケンスを示す図である。
【図１５】経路割当装置の構成例を示す図である。
【図１６】ネットワーク構成例を示す図である。
【図１７】波長が使用している経路を示す図である。
【図１８】波長が使用している経路を示す図である。
【図１９】経路割当数テーブルを示す図である。
【図２０】経路割当数テーブルを示す図である。
【図２１】期待値テーブルを示す図である。
【図２２】更新後の経路割当数テーブルを示す図である。
【図２３】更新後の経路割当数テーブルを示す図である。
【図２４】更新後の期待値テーブルを示す図である。
【図２５】省電力ネットワークの構成例を示す図である。
【図２６】スロットが配置されたフレームを示す図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態を図面を参照して説明する。図１は経路割当装置の構成例を示す図である。経路割当装置１０は、経路算出部１１と経路割当制御部１２を備える。経路割当装置１０は、例えば、ネットワークの管理サーバなどに設置される。
【００１９】
経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、ネットワーク運用前に通信スロットへの経路の割当を行う。
この場合、データ衝突が起きないように、かつ経路変動に対応できるように、ネットワーク運用時にも経路をより多く通信スロットに割当てられるような、通信スロットへの経路の割当を行う。
【００２０】
ここで、経路割当制御部１２は、複数の通信スロットに経路を割当てる際に、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当を選択する。
【００２１】
また、経路割当後には次の経路変化に備えて期待値を更新する。この場合、すべての通信スロットに対する経路の割当可能数を算出して期待値を求めるのではなく、差分があった部分を認識しての計算処理を行い、経路割当時に選択された１つの通信スロットに対する、経路割当変更後の経路の割当可能な数をあらためて求めて、次の期待値を更新する（詳細は具体例を挙げて後述する）。
【００２２】
これにより、運用中フェーズにおいても、経路変更時に期待値ベースの演算結果による経路割当を即時に提供し、期待値ベースの最適割当をリアルタイムで行うことが可能になる。なお、以降の説明では、通信スロットを単にスロットと呼ぶ。また、スロットに経路を割当てることを、経路を詰め込むといった表現も使用する。
【００２３】
次に“スロット”、“経路”、“パス”および“期待値”の用語について説明する。“スロット”とは、パケットを送るための一定長の時間間隔のことで、フレームの中で、一定範囲の固定した時間間隔を占める。ある特定番号のスロットは、フレーム内に１つあり、フレームは周期的に繰り返されるため、その中にある特定番号のスロットも同じ周期で繰り返される。
【００２４】
“経路”とは、発信エッジノードと着信エッジノードの組合せとして定義される（通常、発着エッジノード間に位置する中継ノードは意識しない）。また、経路に対しては、所望帯域としての帯域デマンドが与えられる。さらに、経路は（帯域に合わせて割当てられた）１つ以上のパスを含む。
【００２５】
“パス”とは、１つのスロット内で発信エッジノードから着信エッジノードに至るリンク（ノード間を結ぶ伝送路）の組合せとして定義される。１つのパスの帯域は、帯域割当の最小単位であり、（リンク速度／スロット数）である。
【００２６】
“期待値（経路詰め込み期待値）”とは、スロットへの経路の割当可能数の指標となるもので、簡単には、１スロット当り全経路の何％を詰め込めるかを表す指標である。また、期待値は、０〜１の範囲の値をとり、０の場合は、これ以上経路を詰める余裕がないことを示し、１の場合は、最大まで経路を詰める余裕があることを示す。
【００２７】
期待値の大きい方が、トラフィック変動に伴う経路変化にとって好ましい状態であると見なす（期待値が大きいことは、経路詰め込み余裕度が大きいということなので、経路増加要求があっても、運用中において、経路をスロットにダイナミックに詰め込むことができる）。期待値の定義式については後述する。
【００２８】
次に経路割当装置１０における経路割当に関する全体動作について説明する。運用前フェーズにおいて、ネットワーク構成から導き出される、すべての発信エッジノードと着信エッジノードの組合せである全経路を求める。
【００２９】
そして、スロットに対する経路の割当可能な組み合わせを算出し（例えば、ダイクストラ法（Dijkstra法：最短経路問題を解くための汎用的な計算アルゴリズム）などを使用して算出する）、期待値を事前に計算しておく。本計算は、最初に一度だけ行う。
【００３０】
また、運用中フェーズにおいては、経路変更要求時には、要求経路に対して期待値が最大となるスロットを、割当スロットとして即時に応答する。また、経路割当後の次の状態の期待値を、次の経路変更要求が上がるまでに必要な要素の部分のみを更新して計算する。これにより、必要な計算量を減らす。
【００３１】
次にスロットへの経路詰め込みについて図２〜図６を用いて説明する。図２はネットワーク構成例を示す図である。以降では、エッジノードを四角枠で示し、中継ノードを丸枠で示す。
【００３２】
ネットワークＮ１は、エッジノード１〜４および中継ノード５、６を含む。エッジノード１と中継ノード５が接続し、エッジノード２と中継ノード５が接続し、エッジノード３と中継ノード６が接続し、エッジノード４と中継ノード６が接続する。また、中継ノード５と中継ノード６が接続する。
【００３３】
ネットワークＮ１において、エッジノード間をフルメッシュで結ぶと経路数は１２となる（エッジ間を結ぶ途中の中継ノードも示すと、1→5→2、1→5→6→3、1→5→6→4、2→5→1、2→5→6→3、2→5→6→4、3→6→5→1、3→6→5→2、3→6→4、4→6→5→1、4→6→5→2、4→6→3の計１２経路）。
【００３４】
図３は経路テーブルを示す図である。始点エッジノードから終点エッジノードへの経路に番号を振った経路テーブルＴ０を示している（経路テーブルＴ０は、経路算出部１１で管理される）。
【００３５】
あるスロット（スロットｓ１とする）が仮に未使用の場合、スロットｓ１には、テーブルＴ０のどの経路でも１つは詰めることが可能である。すなわち、「スロットｓ１に詰め込み可能な経路数」は１２となる。
【００３６】
図４はスロットが使用している経路を示す図である。図４に示す太矢印の経路（１）の1→5→2のルートが、スロットｓ１に現在詰め込まれていたとする。この状態に対して、あとどれだけの経路を経路（２）〜（１２）の中から選んで詰め込むことができるかを考える。
【００３７】
ここで、“詰め込む”、“詰め込めない”とは、すでにスロットに詰め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有しない経路であればデータ衝突が起きず、そのスロットに該当経路を詰め込むことができる。
【００３８】
また、すでにスロットに詰め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有するようなリンクを含んでいる経路は、データ衝突が生じるため、そのスロットには該経路を詰め込むことができない。
【００３９】
図４に示すように、エッジノード１から中継ノード５へのデータ転送方向のリンクをリンクＬ１、中継ノード５からエッジノード２へのデータ転送方向のリンクをリンクＬ２とする。
【００４０】
例えば、経路（２）の1→5→6→3のルートを見ると、リンクＬ１が経路（１）と経路（２）で共有することになるので、経路（１）がすでに詰め込まれているスロットｓ１に対しては、経路（２）は詰め込めない。
【００４１】
これに対し、経路（９）の3→6→4のルートは、リンクＬ１、Ｌ２を共有しないので、経路（９）は、スロットｓ１に詰め込むことができる。また、経路（４）の2→5→1のルートでは、リンクＬ１、Ｌ２のデータ転送方向とは逆方向にデータを転送するので、リンクＬ１、Ｌ２を共有していることにはならず、経路（４）は、スロットｓ１に詰め込むことができる。
【００４２】
このような考え方で、経路（１）がすでに詰め込まれているスロットｓ１に詰め込み可能な経路を見つけると、この例の場合、経路（４）、（５）、（６）、（７）、（９）、（１０）、（１２）の７つある。したがって、経路（１）がすでに詰め込まれているスロットｓ１に対し、「スロットｓ１に詰め込み可能な経路数」は７となる。
【００４３】
図５、図６はスロットが使用している経路を示す図である。スロットが全部で４（＝N）つあるとし（スロットｓ１〜ｓ４）、スロットｓ１〜ｓ４のそれぞれには図５、図６に示すような利用状況で経路が現在詰め込まれているとする。
【００４４】
すなわち、図５に対し、スロットｓ１、ｓ２には、経路（１）が詰め込まれ、図６に対し、スロットｓ３には、経路（２）が詰め込まれており、スロットｓ４には、経路は何も詰め込まれていないとする。
【００４５】
この場合、スロットｓ１〜ｓ４に詰め込み可能な経路数を上述したような考え方で求めると、スロットｓ１に対してさらに詰め込み可能な経路数は７、スロットｓ２に対してさらに詰め込み可能な経路数も７となる。また、スロットｓ３に対してさらに詰め込み可能な経路数は６、スロットｓ４に対して詰め込み可能な経路数は１２となる。
【００４６】
なお、スロット数を算出する際は、全経路の最小帯域デマンド（Min帯域デマンド）を、その最大公約数（１スロットの帯域）で割算し、各経路に必要なパス数を求め、あわせて、スロット数を（リンク速度／１スロットの帯域）で決定する。
【００４７】
次にスロットｓ１〜ｓ４に対する期待値の事前計算について説明する（“事前”とは運用前フェーズということである）。経路割当制御部１２では、期待値算出に当たって、まず、パラメータ（aj、bi,j）をそれぞれ構成要素とするテーブルを作成管理する。なお、jはスロット番号、iは経路番号である。
【００４８】
図７は経路割当数テーブルを示す図である。経路割当数テーブルＴ１ａは、パラメータajを含むテーブルであり、ajは、現在の割当状態においてスロットjに詰め込み可能な経路数を示す。上述したように、スロットｓ１〜ｓ４に詰め込み可能な経路数は７、７、６、１２であるので、a1＝７、a2＝７、a3＝６、a4＝１２である。
【００４９】
図８は経路割当数テーブルを示す図である。経路割当数テーブルＴ１ｂは、パラメータbi,jを含むテーブルであり、bi,jは、現在の経路割当状態に対し、もし任意の経路iをスロットjに割当てたとした場合の、その後の詰め込み可能な経路数を示す。
【００５０】
例えば、テーブルＴ１ｂ中のb1,4が示す “７”とは、スロットｓ４に経路（１）が現在詰め込まれている状態のときに、あといくつの経路を詰め込めるかを示す値であり、７つの経路が詰め込み可能なことを示している。
【００５１】
また、テーブルＴ１ｂ中のbi,jが示す“０”とは、スロットjには経路iを詰め込むことができないことを示している。例えば、b1,3＝０となっており、これは、スロットｓ３には経路（１）は詰め込めないことを示している（経路（２）と経路（１）とで、データ転送方向が同じリンクを共有してしまうため）。
【００５２】
上記のように、ajおよびbi,jをそれぞれ事前に、例えば、Dijkstra法などのアルゴリズムを用いてすべての経路に当たることで求めておき、経路割当数テーブルＴ１ａ、Ｔ１ｂを作成する。
【００５３】
その後、経路割当数テーブルＴ１ａ、Ｔ１ｂ使って、現在の経路割当状態に対して、経路iをスロットjに割当てたときの期待値ei,jを事前に計算する。ここでの期待値ei,jは、現在の割当状態に対し、もし経路iをスロットjに割当てたとした場合の、その後のシステム全体の期待値を表す。
【００５４】
ここで、Nを経路割当に使用するスロットの数、Lを経路数とすると、期待値ei,jは式（１）で算出される。
【００５５】
【数１】
【００５６】
図９は期待値テーブルを示す図である。期待値テーブルＴ２は、図７、図８で示した経路割当数テーブルＴ１ａ、Ｔ１ｂそれぞれのajおよびbi,jにもとづき、式（１）を用いて計算した期待値ei,jの結果を示している。
【００５７】
期待値の算出例として、スロットｓ４に経路（１）を詰め込むと、あとどれぐらいの経路を詰め込むことができるかの期待値e1,4を求める場合について以下に示す。
経路割当数テーブルＴ１ａから、a1＝７、a2＝７、a3＝６であり、経路割当数テーブルＴ１ｂから、b1,4＝７であるから、式（１）にもとづいて、期待値e1,4は、以下のように算出される。
【００５８】
e1,4＝（a1＋a2＋a3＋b1,4）／（L×N）＝（７＋７＋６＋７）／（１２×４）＝０．５６・・・（１ａ）
現在のシステム全体の経路割当状態に対して、もし経路（１）を割当てたならば、経路（１）を割当てた後のスロットｓ４の期待値e1,4は０．５６となる。
【００５９】
他の期待値について見ると、例えば、期待値e12,1は、０．６０となり、期待値e12,4は０．５４となっている。
これは、期待値e12,1に関しては、経路（１２）の要求があったときに、スロットｓ１に経路（１２）を詰め込めば、システム全体の次の期待値が０．６０になるということである。また、期待値e12,4に関しては、経路（１２）の要求があったときに、スロットｓ４に経路（１２）を詰め込めば、システム全体の次の期待値が０．５４になるということである。
【００６０】
上記のような演算を行うことで各ei,jを求めて期待値テーブルＴ２を作成する。式（１）によって期待値を算出することで、あるスロットに対する現在の経路割当状態に対して、ある経路を仮に詰め込んだ場合に、どれだけ経路を詰め込めるかといった指標を効率よく求めることが可能になる。
【００６１】
なお、期待値テーブルＴ２において、各行で一番値の大きいものが、経路要求されたときに割当てるスロットになり（期待値が大きい方がより多くの経路を動的に割当てることができるため）、これを割当スロットとして記憶保持しておく。
【００６２】
図９中の黒太枠欄は、割当スロットとして記憶しておくべき値である。例えば、経路（１）を要求された場合には、スロット番号j＝４であるスロットｓ４に経路（１）を割当てることになる。
【００６３】
運用前に実施する上記の期待値事前計算において、各パラメータの計算量について記すと、ajおよびbi,jは、個々の値を求めるためにすべての経路に対して逐一Dijkstra演算を行う必要があるため、計算量が大きい。それに対して、ei,jは単純な四則演算の範囲で求まるため計算量は小さい。
【００６４】
次に運用時に経路変更要求があった場合の動作について説明する。経路変更要求を受信したとき、事前の期待値計算によって抽出しておいた、期待値が一番大きいスロットを経路割当先に決定して即時応答する。
【００６５】
その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。この更新を行う場合に、期待値事前計算で行った手順を再び最初から繰り返すと計算量が大きくなるので、変化のあった部分のみを抽出して計算することで計算量を削減する。
【００６６】
期待値の更新処理を以下の［１］〜［３］に示す。なお、割当てた経路の番号をI、割当られたスロットの番号をJとする。
［１］aJをbI,Jで置き換えて経路割当数テーブルＴ１ａを書き替える。
【００６７】
［２］経路割当後のbi,J（1≦i≦L）を求めて（例えば、Dijkstra法などを利用して再計算を行うが、bi,J（1≦i≦L）のみを求めるため計算量は小さい）、経路割当数テーブルＴ１ｂを書き替える。このとき、他のbi,jの再計算は行わない。
【００６８】
［３］［１］、［２］で求めたaj、bi,jより、ei,jを再計算する。
ここで、一例として、スロットｓ４に経路（１）を割当てた後の更新処理について説明する。更新手順としてはまず、aJをbI,Jで置き換えることになる。
【００６９】
図１０は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１ａ−１は、更新後のパラメータajを含むテーブル状態を示している。
スロットｓ４に経路（１）を割当てたので、I＝１、J＝４である。したがって、図７に示した経路割当数テーブルＴ１ａのa4（＝１２）を、図８の経路割当数テーブルＴ１ｂのb1,4（＝７）で置き換えることになるので、経路割当数テーブルＴ１ａ−１のa4が７に更新される（テーブル太線枠が更新部分）。
【００７０】
次の更新手順として、スロットｓ４の現在の割当状態に対して、経路（１）〜（１２）を割当てた場合に、あと何個経路を詰め込めるかを再計算して経路割当数テーブルＴ１ｂを書き替える。このとき、スロットｓ１〜ｓ３に関しての再計算は行わない。
【００７１】
図１１は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１ｂ−１は、更新後のパラメータbi,jを含むテーブル状態を示している。
経路割当後のスロットｓ４への詰め込み可能数であるbi,4（1≦i≦L）を求める。すなわち、b1,4、b2,4、b3,4、b4,4、b5,4、b6,4、b7,4、b8,4、b9,4、b10,4、b11,4、b12,4の値をそれぞれ計算し、例えば、太線枠内に示すような数値が得られたとする。
【００７２】
なお、例えば、経路割当数テーブルＴ１ｂ−１のb12,4＝４となっており、これは、スロットｓ４に経路（１）を詰め込んだ状態で、さらに経路（１２）を詰め込んだとしたら、あと何個詰め込めるか、すなわち４個の経路を詰め込めることを表している（テーブル中の０は、経路を詰め込めないことを示している）。
【００７３】
次の更新手順としては、経路割当数テーブルＴ１ａ−１、Ｔ１ｂ−１それぞれのajおよびbi,jにもとづき、式（１）により期待値ei,jを計算する。
図１２は更新後の期待値テーブルを示す図である。更新時の期待値の計算によって期待値テーブルＴ２−１が作成される。期待値の算出として、例えば、スロットｓ４に経路（１２）を詰め込むと、あとどれぐらいの経路を詰め込むことができるかの期待値e12,4を求める場合を考える。
【００７４】
経路割当数テーブルＴ１ａ−１から、a1＝７、a2＝７、a3＝６であり、経路割当数テーブルＴ１ｂ−１から、b12,4＝４であるから、式（１）にもとづいて、期待値e12,4は、以下のように算出される。
【００７５】
e12,4＝（a1＋a2＋a3＋b12,4）／（L×N）＝（７＋７＋６＋４）／（１２×４）＝０．５・・・（１ｂ）
同様にして他の期待値も算出して期待値テーブルＴ２−１を作成しておくことになる。そして、次の経路要求があった場合には、期待値テーブルＴ２−１で管理されている期待値にもとづき、期待値の最も大きいスロットを経路割当先に決定して即時応答する。その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。以降この繰り返しとなる。上記のような期待値の更新処理を行うことで、短時間で次の経路変更要求に備えた期待値の導出が可能となる。
【００７６】
なお、上記の制御は、経路を増やす方向の期待値の算出について説明したが、経路を減らす方向に対しても上述のaj、bi,j、ei,jに相当する値を準備しておき、同様の期待値の予測計算を適用することができる。
【００７７】
図１３は運用前の動作シーケンスを示す図である。
〔Ｓ１〕経路割当装置１０の経路算出部１１は、所定の経路に含まれるパス数を計算する。
【００７８】
〔Ｓ２〕経路算出部１１は、エッジノードに対して、所定の経路に含まれるパスを登録する。
〔Ｓ３〕エッジノードは、自ノードにパス登録を行って応答を返信する。なお、ステップＳ２のパス登録およびステップＳ３のパス登録応答は必要なパス数の数だけ繰り返す。
【００７９】
〔Ｓ４〕経路算出部１１は、中継ノードに対して、所定の経路に含まれるパスを登録する。
〔Ｓ５〕中継ノードは、自ノードにパス登録を行って応答を返信する。なお、ステップＳ４のパス登録およびステップＳ５のパス登録応答は必要なパス数の数だけ繰り返す。
【００８０】
〔Ｓ６〕経路割当制御部１２は、期待値の事前計算を行う。
〔Ｓ７〕システムの運用が開始される。
図１４は運用時の動作シーケンスを示す図である。
【００８１】
〔Ｓ１１〕発信（送信元）エッジノードが経路の帯域変動を認識する。
〔Ｓ１２〕発信エッジノードは、経路内のパス数の増加または減少に関するパス数変更要求を経路割当装置１０へ送信する。
【００８２】
〔Ｓ１３〕経路割当装置１０の経路割当制御部１２は、現在の期待値テーブルにもとづいて、パス増加要求時には、期待値の最も大きいスロットに対して、増加したパスを割当てる。パス減少要求時には、期待値の最も大きいスロットから、減少したパスを削除する。
【００８３】
〔Ｓ１４〕経路算出部１１は、発信エッジノード、中継ノードおよび着信（宛先）エッジノードに、パス登録またはパス削除のメッセージを送信する。
〔Ｓ１５〕発信エッジノード、中継ノードおよび着信エッジノードは、自ノードにパスの登録またはパスの削除を行って応答を返信する。
【００８４】
〔Ｓ１６〕経路割当制御部１２は、発信エッジノードに対して、どのスロットに経路を詰め込むかのスロット変更を示すスロット変更要求応答を送信する。
〔Ｓ１７〕経路割当制御部１２は、変更があった箇所の差分に関する部分だけ演算を行って、次の経路変更要求に備えて期待値更新処理を行う。
【００８５】
以上説明したように、経路割当装置１０によれば、運用中フェーズにおいても期待値ベースの経路割当を適用して、スロットの利用効率の最適化を実現することができる（より多くの経路を詰込むことができる）。また、運用中の期待値計算は、計算量を小さくして更新するので、運用時にも経路割当を高速に行うことができ、リアルタイムの応答が可能となり、通信効率の向上を図ることが可能になる。
【００８６】
次に変形例について説明する。経路割当装置１０では、TDM（Time Division Multiplexing）により時間軸上に複数のスロットを設けて、動的割り当てを高速に行うものとして説明したが、時間間隔のスロットではなく、波長に経路を割当て、光通信を行うことも可能である。
【００８７】
図１５は経路割当装置の構成例を示す図である。上述の経路割当装置１０では、時間軸上でスロットを定義したが、経路割当装置１０ａでは、波長軸上で定義される波長に置き換える。つまり、時間軸上のTDMパスが、波長軸上のλパスに置き換わる。
【００８８】
経路割当装置１０ａは、経路算出部１１ａと経路割当制御部１２ａを含む。経路算出部１１ａは、光ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２ａは、波長に経路を割当てる。
【００８９】
ここで、経路割当制御部１２ａは、波長への経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当を選択する。また、選択された１つの波長に対する経路の割当可能な数を求めて、経路割当後の次の期待値を更新する。
【００９０】
次に波長への経路詰め込みについて図１６〜図１８を用いて説明する。図１６はネットワーク構成例を示す図である。ネットワークＮ１ａは、エッジノード１〜４および中継ノード５、６を含む。基本トポロジは、図２のネットワークＮ１と同じであるが、ノード間のリンクは、光ファイバで構成される。なお、ネットワークＮ１ａの経路テーブルは、図３と同じである。
【００９１】
図１７、図１８は波長が使用している経路を示す図である。異なる波長が全部で４（＝W）つあるとし（波長λ１〜λ４）、波長λ１〜λ４のそれぞれには図１７、図１８に示すような利用状況で経路が現在詰め込まれているとする。
【００９２】
すなわち、図１７に対し、波長λ１、λ２には、経路（１）が詰め込まれ、図１８に対し、波長λ３には、経路（２）が詰め込まれており、波長λ４には、経路は何も詰め込まれていないとする。
【００９３】
この場合、波長λ１に対してさらに詰め込み可能な経路数は７、波長λ２に対してさらに詰め込み可能な経路数は７となる。また、波長λ３に対してさらに詰め込み可能な経路数は６、波長λ４に対して詰め込み可能な経路数は１２となる。
【００９４】
次に波長λ１〜λ４に対する期待値の事前計算について説明する。経路割当制御部１２ａでは、期待値算出に当たって、まず、パラメータ（aj、bi,j）をそれぞれ構成要素とするテーブルを作成管理する。なお、jは波長番号、iは経路番号である。
【００９５】
図１９は経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ａは、パラメータajを含むテーブルであり、ajは、現在の割当状態において波長jに詰め込み可能な経路数を示す。波長λ１〜λ４に詰め込み可能な経路数は７、７、６、１２であるので、a1＝７、a2＝７、a3＝６、a4＝１２である。
【００９６】
図２０は経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ｂは、パラメータbi,jを含むテーブルであり、bi,jは、現在の経路割当状態に対し、もし任意の経路iを波長jに割当てたとした場合の、その後の詰め込み可能な経路数を示す。
【００９７】
経路割当数テーブルＴ１１ａ、Ｔ１１ｂ使って、現在の経路割当状態に対して、経路iを波長jに割当てたときの期待値ei,jを計算する。ei,jは、現在の割当状態に対し、もし経路iを波長jに割当てたとした場合の、その後のシステム全体の期待値を表す。
【００９８】
ここで、Wを経路割当に使用する波長の数、Lを経路数とすると、期待値ei,jは式（２）で算出される。
【００９９】
【数２】
【０１００】
図２１は期待値テーブルを示す図である。期待値テーブルＴ２２は、図１９、図２０で示した経路割当数テーブルＴ１１ａ、Ｔ１１ｂそれぞれのajおよびbi,jにもとづき、式（２）を用いて計算した期待値ei,jの値を示している。期待値算出例は、上述の経路割当装置１０の場合と同じなので説明は省略する。
【０１０１】
式（２）によって期待値を算出することで、ある波長に対する現在の経路割当状態に対して、ある経路を仮に詰め込んだ場合に、その後どれだけ経路を詰め込めるかといった指標を効率よく求めることが可能になる。
【０１０２】
なお、期待値テーブルＴ２２において、各行で一番値の大きいものが、経路要求されたときに割当てる波長になり（期待値が大きい方がより多くの経路を動的に割当てることができるため）、これを割当波長として記憶保持しておく。図２１中の黒太枠欄は、割当波長として記憶しておくべき値である。
【０１０３】
次に運用時に経路変更要求があった場合の動作について説明する。経路変更要求を受信したとき、事前の期待値計算によって抽出しておいた、期待値が一番大きい波長を経路割当先に決定して応答する。
【０１０４】
その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。この更新を行う場合に、期待値事前計算で行った手順を再び最初から繰り返すと計算量が大きくなるので、変化のあった部分のみを計算して計算量を削減する。期待値の更新処理は上記の［１］〜［３］と同じである。ここでは、割当てられた波長の番号をJとする。
【０１０５】
ここで、波長λ４に経路（１）を割当てた後の更新処理について説明する。更新手順としてまず、aJをbI,Jで置き換える。
図２２は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ａ−１は、更新後のパラメータajを含むテーブル状態を示している。
【０１０６】
波長λ４に経路（１）を割当てたので、I＝１、J＝４である。したがって、図１９に示した経路割当数テーブルＴ１１ａのa4（＝１２）を、図２０の経路割当数テーブルＴ１１ｂのb1,4（＝７）で置き換えることになるので、経路割当数テーブルＴ１１ａ−１のa4が７と更新される。
【０１０７】
次の更新手順として、波長λ４の現在の割当状態に対して、経路（１）〜（１２）を割当てた場合に、あと何個経路を詰め込めるかを再計算して経路割当数テーブルＴ１１ｂを書き替える。このとき、波長λ１〜λ３に関しての再計算は行わない。
【０１０８】
図２３は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ｂ−１は、更新後のパラメータbi,jを含むテーブル状態を示している。経路割当後の波長λ４への詰め込み可能数であるbi,4（1≦i≦L）を求めることになる。すなわち、b1,4、b2,4、b3,4、b4,4、b5,4、b6,4、b7,4、b8,4、b9,4、b10,4、b11,4、b12,4の値をそれぞれ計算し、例えば、太線枠内に示すような数値となったとする。
【０１０９】
次の更新手順としては、経路割当数テーブルＴ１１ａ−１、Ｔ１１ｂ−１それぞれのajおよびbi,jにもとづき、式（２）により期待値ei,jを計算する。
図２４は更新後の期待値テーブルを示す図である。更新時の期待値の計算によって期待値テーブルＴ２２−１が作成される。期待値の算出として、例えば、波長λ４に経路（１２）を詰め込むと、あとどれぐらいの経路を詰め込むことができるかの期待値e12,4を求める場合を考える。
【０１１０】
経路割当数テーブルＴ１１ａ−１から、a1＝７、a2＝７、a3＝６であり、経路割当数テーブルＴ１１ｂ−１から、b12,4＝４であるから、式（２）にもとづいて、期待値e12,4は、以下のように算出される。
【０１１１】
e12,4＝（a1＋a2＋a3＋b12,4）／（L×W）＝（７＋７＋６＋４）／（１２×４）＝０．５・・・（２ａ）
同様にして他の期待値も算出して期待値テーブルＴ２２−１を作成しておく。そして、次の経路要求があった場合には、期待値テーブルＴ２２−１で管理されている期待値にもとづき、期待値の最も大きい波長を経路割当先に決定して即時応答する。その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。以降この繰り返しとなる。上記のような期待値の更新処理を行うことで、短時間で次の経路変更要求に備えた期待値の導出が可能となる。
【０１１２】
次に経路割当装置１０の機能を含む管理サーバが配置された、省電力ネットワークの概要について説明する。図２５は省電力ネットワークの構成例を示す図である。ネットワークＮ１−１は、図２で示したネットワークＮ１に管理サーバ１０−１が配置された構成をとる。
【０１１３】
〔Ｓ２１〕管理サーバ１０−１は、ネットワークＮ１−１の構成と、各経路（発信エッジノードと着信エッジノードとの組合せ）とを認識し、経路の帯域デマンドとして、経路毎の最小帯域値および最大帯域値を認識する。
【０１１４】
〔Ｓ２２〕管理サーバ１０−１は、さらに、最小帯域値を満たすように、スロットへの経路割当を導出し、各ノード（エッジノード１〜４および中継ノード５、６）に設定する。
【０１１５】
〔Ｓ２３〕エッジノード１〜４は、経路毎のトラフィック量を監視し、その経路に割当てられた帯域が適切か、余剰か、または不足かを判定して、最小帯域値から最大帯域値の間でパス数の変更があるか否かを認識し、変更がある場合は管理サーバ１０−１に通知する。
【０１１６】
〔Ｓ２４〕エッジノード１に例えば、外部からパケットが到着する。エッジノード１は、宛先エッジノード毎にパケットを分類し、パス割当の増加が必要と判断したとする。
〔Ｓ２５〕エッジノード１は、管理サーバ１０−１に対し、パケット送出に必要なスロットの予約を要求する。
【０１１７】
〔Ｓ２６〕管理サーバ１０−１は、スロット予約要求を受信すると、期待値にもとづいて経路割当において最適なスロットを選択して、経路割当の調整を行う。
〔Ｓ２６ａ〕管理サーバ１０−１は、経路割当の結果をエッジノード１に応答する。
【０１１８】
〔Ｓ２７〕エッジノード１は、中継ノード５、６にスロットの付け替えを指定する。
〔Ｓ２８〕エッジノード１は、管理サーバ１０−１で通知されたスロットに合わせて、該当パケットを送出する。なお、中継ノード５、６は、スロットＩＤに合わせてバッファレス伝送でパケットを中継送信する。
【０１１９】
図２６はスロットが配置されたフレームを示す図である。横軸は時間、縦軸はフレームデリミタである。スロット＃１〜＃ｎが配置されたフレームが繰り返しエッジノードから送出される。また、同じ経路（パス）は、同一番号のスロットを連続して使用して送信される。
【０１２０】
以上説明したように、経路割当装置１０の機能を含む管理サーバ１０−１を配置して、送信すべきパケットのスロットをあらかじめ割当て、時分割ベースでパケット転送を行うことで、省電力ネットワークを構築することが可能になる。
【０１２１】
また、管理サーバ１０−１では、スロットへ経路を割当てる期待値を算出し、短時間で期待値更新処理を行って、最適経路割当を高速に行うことができるので、エッジノードからの経路変更要求に対してリアルタイムの応答が可能であり、遅延を抑制して通信効率の向上を図ることが可能になる。
【０１２２】
なお、上記の経路割当装置１０の処理機能は、コンピュータによって実現することができる。その場合、経路割当装置１０が有すべき機能の処理内容を記述したプログラム（経路割当プログラム）が提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１２３】
コンピュータは、ＣＰＵによって装置全体が制御される。ＣＰＵには、バスを介してＲＡＭ、ハードディスクドライブ、通信インタフェース、グラフィック処理装置、および入出力インタフェースが接続される。
【０１２４】
ＲＡＭには、ＣＰＵに実行させるＯＳ（Operating System）のプログラムや、経路割当を行うためのプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭには、ＣＰＵによる処理に必要な各種データが格納される。ＨＤＤメッセージには、ＯＳやアプリケーションプログラムが格納される。
【０１２５】
通信インタフェースは、ネットワークに接続されている。通信インタフェースは、ネットワークを介して、他のコンピュータとの間でデータの送受信を行う。グラフィック処理装置は、モニタが接続されている。グラフィック処理装置は、ＣＰＵからの命令にしたがって画像をモニタの画面に表示させる。
【０１２６】
入出力インタフェースには、キーボードとマウスとが接続されている。入出力インタフェースは、キーボードやマウスから送られてくる信号を、バスを介してＣＰＵに送信する。また、入出力インタフェースは、外部記憶媒体への情報の書き込みおよび外部記憶媒体への情報の読出しが可能な外部記憶媒体インタフェースと接続可能になっている。
【０１２７】
経路割当装置１０は、経路割当装置が有すべき機能の処理内容を記述したプログラムをコンピュータで実行することにより実現することができる。すなわち、図１の経路算出部１１、経路割当制御部１２に対応する処理内容をプログラムとして記述する。ここで、記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１２８】
コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。
【０１２９】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１３０】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０１３１】
プログラムを実行するコンピュータは、例えば、外部記憶媒体に記録されたプログラムまたはサーバプログラムから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは自己の記憶装置からプログラムを読み取り、プログラムにしたがった処理を実行する。なお、コンピュータは、外部記憶媒体から直接プログラムを読み取り、そのプログラムにしたがった処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次受け取ったプログラムにしたがった処理を実行することもできる。
【０１３２】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。
（付記１） ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
通信スロットに前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【０１３３】
（付記２） 前記経路割当制御部は、
前記通信スロットの番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して通信スロットjに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを通信スロットjに割当てたとした場合の通信スロットjに割当可能な前記経路の数をbi,jとし、前記通信スロットの数をN、前記経路の数をLとした場合、前記期待値であるei,jを、
【０１３４】
【数１】
【０１３５】
で算出することを特徴とする付記１記載の経路割当装置。
（付記３） 前記経路割当制御部は、番号Jの前記通信スロットに、番号Iの前記経路の割当を行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする付記２記載の経路割当装置。
【０１３６】
（付記４） 経路割当方法において、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
通信スロットに前記経路を割当てる場合に、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【０１３７】
（付記５） 光ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
波長に前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【０１３８】
（付記６） 前記経路割当制御部は、
前記波長の番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して波長jに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを波長jに割当てたとした場合の波長jに割当可能な前記経路の数をbi,jとし、前記波長の数をW、前記経路の数をLとした場合、前記期待値であるei,jを、
【０１３９】
【数２】
【０１４０】
で算出することを特徴とする付記５記載の経路割当装置。
（付記７） 前記経路割当制御部は、番号Jの前記波長に、番号Iの前記経路の割当を行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする付記６記載の経路割当装置。
【０１４１】
（付記８） 経路割当方法において、
光ネットワーク内の発信ノードから着信ノード間の経路を求め、
波長に前記経路を割当てる場合に、
前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【０１４２】
（付記９） 通信システムにおいて、
データ送信元の発信ノードと、
前記発信ノードから着信ノード間の経路を求める経路算出部と、通信スロットに前記経路を割当てる経路割当制御部とを含む管理サーバと、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択して前記発信ノードへ通知し、経路割当後に選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新しておき、
前記発信ノードは、経路が割当てられた前記通信スロットに合わせてデータを送信し、運用中に経路変動を認識した場合は、前記管理サーバへ経路変更要求を送信し、
前記経路割当制御部は、前記経路変更要求を受信すると、先に更新しておいた前記期待値が最大となる経路割当を選択して前記発信ノードへ通知し、前記期待値の更新処理を繰り返す、
ことを特徴とする通信システム。
【０１４３】
（付記１０） 前記経路割当制御部は、
前記通信スロットの番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して通信スロットjに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを通信スロットjに割当てたとした場合の通信スロットjに割当可能な前記経路の数をbi,jとし、前記通信スロットの数をN、前記経路の数をLとした場合、前記期待値であるei,jを、
【０１４４】
【数１】
【０１４５】
で算出することを特徴とする付記９記載の通信システム。
（付記１１） 前記経路割当制御部は、番号Jの前記通信スロットに、番号Iの前記経路の割当てを行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする付記１０記載の通信システム。
【０１４６】
（付記１２） 通信スロットに経路を割当てる制御をコンピュータに実行させる経路割当プログラムにおいて、
前記コンピュータに、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
処理を実行させることを特徴とする経路割当プログラム。
【符号の説明】
【０１４７】
１０ 経路割当装置
１１ 経路算出部
１２ 経路割当制御部
【技術分野】
【０００１】
本発明は、データ通信を行う経路割当装置および経路割当を行う経路割当方法に関する。
【背景技術】
【０００２】
インターネット等によるマルチメディアサービスの拡大に伴い、ネットワーク上を流れる情報量は飛躍的に増大し、情報通信ネットワークを流れるトラフィックは大きく増加している。
【０００３】
トラフィックが増加すると、例えば、ネットワークを構成するルータの内部では、同時に到着するパケット数が増えて、パケットのバッファリング回数が増えたり、またはルーティングテーブルにもとづく経路計算の制御にかかる負荷が増大したりすることになる。
【０００４】
このため、ルータ内には、パケットバッファに用いるための大容量メモリや、経路計算に用いるための高速メモリといった、消費電力の大きなメモリデバイスが配置されていた。
【０００５】
近年になって、省電力ネットワークの構築を望む声は多いが、上記のように、ネットワーク全体の消費電力は、特にルータにおける消費電力が大きく影響しており、ルータの消費電力をいかに低減するかがネットワーク省電力化の鍵といえる。
【０００６】
従来技術として、経路リストのすべての経路の振り分け割合を計算してルーティングテーブルを作成し、周期的に更新する技術が提案されている（特許文献１）。また、自局と宛先とに割り付けられた帯域と、宛先以外のノードに割り付けられた帯域とから伝送帯域を算出し、伝送帯域の範囲で情報を送信する技術が提案されている（特許文献２）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平１１−２３９１８１号公報
【特許文献２】特開２００２−２４７０９２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
省電力ネットワークを構築する場合、ネットワークの管理を行うサーバ側で、送信すべきパケットのスロット（タイムスロット）をあらかじめ割当て、時分割ベースでパケット転送を行う通信方式が考えられる。
【０００９】
これは、サーバが、どの時間で、どこの送信元からどこの宛先へ行くのかといったパケット転送のスケジューリングをしておいてから、パケット送出を行うものである。
このような制御を行うことにより、例えば、ルータに複数パケットが同時に到着するといった状態の発生頻度を低減させることができ、バッファリング回数を減少させることができる。このため、パケットバッファとして使用されていた消費電力の大きな大容量メモリをルータから排除することが可能になる。
【００１０】
また、例えば、ルータ自身が、従来行われていたような経路計算を実行せずに済むので、経路計算に要する負荷の軽減を図ることもでき、経路計算時に使用されていた消費電力の大きな高速メモリを不要とすることが可能になる。なお、上記では、ルータの消費電力に注目して説明したが、ネットワークを構成するスイッチの消費電力についても同様の理由で低減可能である。
【００１１】
一方、スケジューリングを行う場合に、ネットワークのトラフィック変動に伴う経路の増加に対応できるように、あとどれくらいの経路をスロットに割当てることができるかの指標をあらかじめ算出しておき、その指標にもとづいて経路を割当てるとしたスケジューリングを行うことが考えられる。これにより、運用中において経路割当の追加要求があった場合にも柔軟に対応することができる。
【００１２】
また、運用中に経路の割当を行った後には、次の経路割当要求に備えて、経路を割当てた現在の状態に対して、あとどれくらいの経路をスロットに割当てることができるかの指標を、あらためて算出して最適化しておくことが望ましい。
【００１３】
しかし、経路とスロットとの任意の組合せから上記の指標を求めるための計算量は大きく、ネットワーク構成が複雑になるほど、計算量は大きいものとなる。このため、運用時に経路追加要求がある度に、運用前に実施していた、計算量の大きなスケジューリングを再度行って、経路割当の最適化を図ろうとすると、リアルタイムに応答することができず、また通信効率も低下するといった問題があった。
【００１４】
本発明はこのような点に鑑みてなされたものであり、経路割当を高速に行って通信効率の向上を図った経路割当装置を提供することを目的とする。
また、本発明の他の目的は、経路割当を高速に行って通信効率の向上を図った経路割当方法を提供することである。
【課題を解決するための手段】
【００１５】
上記課題を解決するために、経路割当装置が提供される。この経路割当装置は、ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、通信スロットに前記経路を割当てる経路割当制御部とを備える。前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する。
【発明の効果】
【００１６】
通信効率の向上を図ることが可能になる。
【図面の簡単な説明】
【００１７】
【図１】経路割当装置の構成例を示す図である。
【図２】ネットワーク構成例を示す図である。
【図３】経路テーブルを示す図である。
【図４】スロットが使用している経路を示す図である。
【図５】スロットが使用している経路を示す図である。
【図６】スロットが使用している経路を示す図である。
【図７】経路割当数テーブルを示す図である。
【図８】経路割当数テーブルを示す図である。
【図９】期待値テーブルを示す図である。
【図１０】更新後の経路割当数テーブルを示す図である。
【図１１】更新後の経路割当数テーブルを示す図である。
【図１２】更新後の期待値テーブルを示す図である。
【図１３】運用前の動作シーケンスを示す図である。
【図１４】運用時の動作シーケンスを示す図である。
【図１５】経路割当装置の構成例を示す図である。
【図１６】ネットワーク構成例を示す図である。
【図１７】波長が使用している経路を示す図である。
【図１８】波長が使用している経路を示す図である。
【図１９】経路割当数テーブルを示す図である。
【図２０】経路割当数テーブルを示す図である。
【図２１】期待値テーブルを示す図である。
【図２２】更新後の経路割当数テーブルを示す図である。
【図２３】更新後の経路割当数テーブルを示す図である。
【図２４】更新後の期待値テーブルを示す図である。
【図２５】省電力ネットワークの構成例を示す図である。
【図２６】スロットが配置されたフレームを示す図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態を図面を参照して説明する。図１は経路割当装置の構成例を示す図である。経路割当装置１０は、経路算出部１１と経路割当制御部１２を備える。経路割当装置１０は、例えば、ネットワークの管理サーバなどに設置される。
【００１９】
経路算出部１１は、ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２は、ネットワーク運用前に通信スロットへの経路の割当を行う。
この場合、データ衝突が起きないように、かつ経路変動に対応できるように、ネットワーク運用時にも経路をより多く通信スロットに割当てられるような、通信スロットへの経路の割当を行う。
【００２０】
ここで、経路割当制御部１２は、複数の通信スロットに経路を割当てる際に、通信スロットへの経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当を選択する。
【００２１】
また、経路割当後には次の経路変化に備えて期待値を更新する。この場合、すべての通信スロットに対する経路の割当可能数を算出して期待値を求めるのではなく、差分があった部分を認識しての計算処理を行い、経路割当時に選択された１つの通信スロットに対する、経路割当変更後の経路の割当可能な数をあらためて求めて、次の期待値を更新する（詳細は具体例を挙げて後述する）。
【００２２】
これにより、運用中フェーズにおいても、経路変更時に期待値ベースの演算結果による経路割当を即時に提供し、期待値ベースの最適割当をリアルタイムで行うことが可能になる。なお、以降の説明では、通信スロットを単にスロットと呼ぶ。また、スロットに経路を割当てることを、経路を詰め込むといった表現も使用する。
【００２３】
次に“スロット”、“経路”、“パス”および“期待値”の用語について説明する。“スロット”とは、パケットを送るための一定長の時間間隔のことで、フレームの中で、一定範囲の固定した時間間隔を占める。ある特定番号のスロットは、フレーム内に１つあり、フレームは周期的に繰り返されるため、その中にある特定番号のスロットも同じ周期で繰り返される。
【００２４】
“経路”とは、発信エッジノードと着信エッジノードの組合せとして定義される（通常、発着エッジノード間に位置する中継ノードは意識しない）。また、経路に対しては、所望帯域としての帯域デマンドが与えられる。さらに、経路は（帯域に合わせて割当てられた）１つ以上のパスを含む。
【００２５】
“パス”とは、１つのスロット内で発信エッジノードから着信エッジノードに至るリンク（ノード間を結ぶ伝送路）の組合せとして定義される。１つのパスの帯域は、帯域割当の最小単位であり、（リンク速度／スロット数）である。
【００２６】
“期待値（経路詰め込み期待値）”とは、スロットへの経路の割当可能数の指標となるもので、簡単には、１スロット当り全経路の何％を詰め込めるかを表す指標である。また、期待値は、０〜１の範囲の値をとり、０の場合は、これ以上経路を詰める余裕がないことを示し、１の場合は、最大まで経路を詰める余裕があることを示す。
【００２７】
期待値の大きい方が、トラフィック変動に伴う経路変化にとって好ましい状態であると見なす（期待値が大きいことは、経路詰め込み余裕度が大きいということなので、経路増加要求があっても、運用中において、経路をスロットにダイナミックに詰め込むことができる）。期待値の定義式については後述する。
【００２８】
次に経路割当装置１０における経路割当に関する全体動作について説明する。運用前フェーズにおいて、ネットワーク構成から導き出される、すべての発信エッジノードと着信エッジノードの組合せである全経路を求める。
【００２９】
そして、スロットに対する経路の割当可能な組み合わせを算出し（例えば、ダイクストラ法（Dijkstra法：最短経路問題を解くための汎用的な計算アルゴリズム）などを使用して算出する）、期待値を事前に計算しておく。本計算は、最初に一度だけ行う。
【００３０】
また、運用中フェーズにおいては、経路変更要求時には、要求経路に対して期待値が最大となるスロットを、割当スロットとして即時に応答する。また、経路割当後の次の状態の期待値を、次の経路変更要求が上がるまでに必要な要素の部分のみを更新して計算する。これにより、必要な計算量を減らす。
【００３１】
次にスロットへの経路詰め込みについて図２〜図６を用いて説明する。図２はネットワーク構成例を示す図である。以降では、エッジノードを四角枠で示し、中継ノードを丸枠で示す。
【００３２】
ネットワークＮ１は、エッジノード１〜４および中継ノード５、６を含む。エッジノード１と中継ノード５が接続し、エッジノード２と中継ノード５が接続し、エッジノード３と中継ノード６が接続し、エッジノード４と中継ノード６が接続する。また、中継ノード５と中継ノード６が接続する。
【００３３】
ネットワークＮ１において、エッジノード間をフルメッシュで結ぶと経路数は１２となる（エッジ間を結ぶ途中の中継ノードも示すと、1→5→2、1→5→6→3、1→5→6→4、2→5→1、2→5→6→3、2→5→6→4、3→6→5→1、3→6→5→2、3→6→4、4→6→5→1、4→6→5→2、4→6→3の計１２経路）。
【００３４】
図３は経路テーブルを示す図である。始点エッジノードから終点エッジノードへの経路に番号を振った経路テーブルＴ０を示している（経路テーブルＴ０は、経路算出部１１で管理される）。
【００３５】
あるスロット（スロットｓ１とする）が仮に未使用の場合、スロットｓ１には、テーブルＴ０のどの経路でも１つは詰めることが可能である。すなわち、「スロットｓ１に詰め込み可能な経路数」は１２となる。
【００３６】
図４はスロットが使用している経路を示す図である。図４に示す太矢印の経路（１）の1→5→2のルートが、スロットｓ１に現在詰め込まれていたとする。この状態に対して、あとどれだけの経路を経路（２）〜（１２）の中から選んで詰め込むことができるかを考える。
【００３７】
ここで、“詰め込む”、“詰め込めない”とは、すでにスロットに詰め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有しない経路であればデータ衝突が起きず、そのスロットに該当経路を詰め込むことができる。
【００３８】
また、すでにスロットに詰め込まれている経路に対し、その経路のリンクと、データ転送方向が同じリンクを共有するようなリンクを含んでいる経路は、データ衝突が生じるため、そのスロットには該経路を詰め込むことができない。
【００３９】
図４に示すように、エッジノード１から中継ノード５へのデータ転送方向のリンクをリンクＬ１、中継ノード５からエッジノード２へのデータ転送方向のリンクをリンクＬ２とする。
【００４０】
例えば、経路（２）の1→5→6→3のルートを見ると、リンクＬ１が経路（１）と経路（２）で共有することになるので、経路（１）がすでに詰め込まれているスロットｓ１に対しては、経路（２）は詰め込めない。
【００４１】
これに対し、経路（９）の3→6→4のルートは、リンクＬ１、Ｌ２を共有しないので、経路（９）は、スロットｓ１に詰め込むことができる。また、経路（４）の2→5→1のルートでは、リンクＬ１、Ｌ２のデータ転送方向とは逆方向にデータを転送するので、リンクＬ１、Ｌ２を共有していることにはならず、経路（４）は、スロットｓ１に詰め込むことができる。
【００４２】
このような考え方で、経路（１）がすでに詰め込まれているスロットｓ１に詰め込み可能な経路を見つけると、この例の場合、経路（４）、（５）、（６）、（７）、（９）、（１０）、（１２）の７つある。したがって、経路（１）がすでに詰め込まれているスロットｓ１に対し、「スロットｓ１に詰め込み可能な経路数」は７となる。
【００４３】
図５、図６はスロットが使用している経路を示す図である。スロットが全部で４（＝N）つあるとし（スロットｓ１〜ｓ４）、スロットｓ１〜ｓ４のそれぞれには図５、図６に示すような利用状況で経路が現在詰め込まれているとする。
【００４４】
すなわち、図５に対し、スロットｓ１、ｓ２には、経路（１）が詰め込まれ、図６に対し、スロットｓ３には、経路（２）が詰め込まれており、スロットｓ４には、経路は何も詰め込まれていないとする。
【００４５】
この場合、スロットｓ１〜ｓ４に詰め込み可能な経路数を上述したような考え方で求めると、スロットｓ１に対してさらに詰め込み可能な経路数は７、スロットｓ２に対してさらに詰め込み可能な経路数も７となる。また、スロットｓ３に対してさらに詰め込み可能な経路数は６、スロットｓ４に対して詰め込み可能な経路数は１２となる。
【００４６】
なお、スロット数を算出する際は、全経路の最小帯域デマンド（Min帯域デマンド）を、その最大公約数（１スロットの帯域）で割算し、各経路に必要なパス数を求め、あわせて、スロット数を（リンク速度／１スロットの帯域）で決定する。
【００４７】
次にスロットｓ１〜ｓ４に対する期待値の事前計算について説明する（“事前”とは運用前フェーズということである）。経路割当制御部１２では、期待値算出に当たって、まず、パラメータ（aj、bi,j）をそれぞれ構成要素とするテーブルを作成管理する。なお、jはスロット番号、iは経路番号である。
【００４８】
図７は経路割当数テーブルを示す図である。経路割当数テーブルＴ１ａは、パラメータajを含むテーブルであり、ajは、現在の割当状態においてスロットjに詰め込み可能な経路数を示す。上述したように、スロットｓ１〜ｓ４に詰め込み可能な経路数は７、７、６、１２であるので、a1＝７、a2＝７、a3＝６、a4＝１２である。
【００４９】
図８は経路割当数テーブルを示す図である。経路割当数テーブルＴ１ｂは、パラメータbi,jを含むテーブルであり、bi,jは、現在の経路割当状態に対し、もし任意の経路iをスロットjに割当てたとした場合の、その後の詰め込み可能な経路数を示す。
【００５０】
例えば、テーブルＴ１ｂ中のb1,4が示す “７”とは、スロットｓ４に経路（１）が現在詰め込まれている状態のときに、あといくつの経路を詰め込めるかを示す値であり、７つの経路が詰め込み可能なことを示している。
【００５１】
また、テーブルＴ１ｂ中のbi,jが示す“０”とは、スロットjには経路iを詰め込むことができないことを示している。例えば、b1,3＝０となっており、これは、スロットｓ３には経路（１）は詰め込めないことを示している（経路（２）と経路（１）とで、データ転送方向が同じリンクを共有してしまうため）。
【００５２】
上記のように、ajおよびbi,jをそれぞれ事前に、例えば、Dijkstra法などのアルゴリズムを用いてすべての経路に当たることで求めておき、経路割当数テーブルＴ１ａ、Ｔ１ｂを作成する。
【００５３】
その後、経路割当数テーブルＴ１ａ、Ｔ１ｂ使って、現在の経路割当状態に対して、経路iをスロットjに割当てたときの期待値ei,jを事前に計算する。ここでの期待値ei,jは、現在の割当状態に対し、もし経路iをスロットjに割当てたとした場合の、その後のシステム全体の期待値を表す。
【００５４】
ここで、Nを経路割当に使用するスロットの数、Lを経路数とすると、期待値ei,jは式（１）で算出される。
【００５５】
【数１】
【００５６】
図９は期待値テーブルを示す図である。期待値テーブルＴ２は、図７、図８で示した経路割当数テーブルＴ１ａ、Ｔ１ｂそれぞれのajおよびbi,jにもとづき、式（１）を用いて計算した期待値ei,jの結果を示している。
【００５７】
期待値の算出例として、スロットｓ４に経路（１）を詰め込むと、あとどれぐらいの経路を詰め込むことができるかの期待値e1,4を求める場合について以下に示す。
経路割当数テーブルＴ１ａから、a1＝７、a2＝７、a3＝６であり、経路割当数テーブルＴ１ｂから、b1,4＝７であるから、式（１）にもとづいて、期待値e1,4は、以下のように算出される。
【００５８】
e1,4＝（a1＋a2＋a3＋b1,4）／（L×N）＝（７＋７＋６＋７）／（１２×４）＝０．５６・・・（１ａ）
現在のシステム全体の経路割当状態に対して、もし経路（１）を割当てたならば、経路（１）を割当てた後のスロットｓ４の期待値e1,4は０．５６となる。
【００５９】
他の期待値について見ると、例えば、期待値e12,1は、０．６０となり、期待値e12,4は０．５４となっている。
これは、期待値e12,1に関しては、経路（１２）の要求があったときに、スロットｓ１に経路（１２）を詰め込めば、システム全体の次の期待値が０．６０になるということである。また、期待値e12,4に関しては、経路（１２）の要求があったときに、スロットｓ４に経路（１２）を詰め込めば、システム全体の次の期待値が０．５４になるということである。
【００６０】
上記のような演算を行うことで各ei,jを求めて期待値テーブルＴ２を作成する。式（１）によって期待値を算出することで、あるスロットに対する現在の経路割当状態に対して、ある経路を仮に詰め込んだ場合に、どれだけ経路を詰め込めるかといった指標を効率よく求めることが可能になる。
【００６１】
なお、期待値テーブルＴ２において、各行で一番値の大きいものが、経路要求されたときに割当てるスロットになり（期待値が大きい方がより多くの経路を動的に割当てることができるため）、これを割当スロットとして記憶保持しておく。
【００６２】
図９中の黒太枠欄は、割当スロットとして記憶しておくべき値である。例えば、経路（１）を要求された場合には、スロット番号j＝４であるスロットｓ４に経路（１）を割当てることになる。
【００６３】
運用前に実施する上記の期待値事前計算において、各パラメータの計算量について記すと、ajおよびbi,jは、個々の値を求めるためにすべての経路に対して逐一Dijkstra演算を行う必要があるため、計算量が大きい。それに対して、ei,jは単純な四則演算の範囲で求まるため計算量は小さい。
【００６４】
次に運用時に経路変更要求があった場合の動作について説明する。経路変更要求を受信したとき、事前の期待値計算によって抽出しておいた、期待値が一番大きいスロットを経路割当先に決定して即時応答する。
【００６５】
その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。この更新を行う場合に、期待値事前計算で行った手順を再び最初から繰り返すと計算量が大きくなるので、変化のあった部分のみを抽出して計算することで計算量を削減する。
【００６６】
期待値の更新処理を以下の［１］〜［３］に示す。なお、割当てた経路の番号をI、割当られたスロットの番号をJとする。
［１］aJをbI,Jで置き換えて経路割当数テーブルＴ１ａを書き替える。
【００６７】
［２］経路割当後のbi,J（1≦i≦L）を求めて（例えば、Dijkstra法などを利用して再計算を行うが、bi,J（1≦i≦L）のみを求めるため計算量は小さい）、経路割当数テーブルＴ１ｂを書き替える。このとき、他のbi,jの再計算は行わない。
【００６８】
［３］［１］、［２］で求めたaj、bi,jより、ei,jを再計算する。
ここで、一例として、スロットｓ４に経路（１）を割当てた後の更新処理について説明する。更新手順としてはまず、aJをbI,Jで置き換えることになる。
【００６９】
図１０は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１ａ−１は、更新後のパラメータajを含むテーブル状態を示している。
スロットｓ４に経路（１）を割当てたので、I＝１、J＝４である。したがって、図７に示した経路割当数テーブルＴ１ａのa4（＝１２）を、図８の経路割当数テーブルＴ１ｂのb1,4（＝７）で置き換えることになるので、経路割当数テーブルＴ１ａ−１のa4が７に更新される（テーブル太線枠が更新部分）。
【００７０】
次の更新手順として、スロットｓ４の現在の割当状態に対して、経路（１）〜（１２）を割当てた場合に、あと何個経路を詰め込めるかを再計算して経路割当数テーブルＴ１ｂを書き替える。このとき、スロットｓ１〜ｓ３に関しての再計算は行わない。
【００７１】
図１１は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１ｂ−１は、更新後のパラメータbi,jを含むテーブル状態を示している。
経路割当後のスロットｓ４への詰め込み可能数であるbi,4（1≦i≦L）を求める。すなわち、b1,4、b2,4、b3,4、b4,4、b5,4、b6,4、b7,4、b8,4、b9,4、b10,4、b11,4、b12,4の値をそれぞれ計算し、例えば、太線枠内に示すような数値が得られたとする。
【００７２】
なお、例えば、経路割当数テーブルＴ１ｂ−１のb12,4＝４となっており、これは、スロットｓ４に経路（１）を詰め込んだ状態で、さらに経路（１２）を詰め込んだとしたら、あと何個詰め込めるか、すなわち４個の経路を詰め込めることを表している（テーブル中の０は、経路を詰め込めないことを示している）。
【００７３】
次の更新手順としては、経路割当数テーブルＴ１ａ−１、Ｔ１ｂ−１それぞれのajおよびbi,jにもとづき、式（１）により期待値ei,jを計算する。
図１２は更新後の期待値テーブルを示す図である。更新時の期待値の計算によって期待値テーブルＴ２−１が作成される。期待値の算出として、例えば、スロットｓ４に経路（１２）を詰め込むと、あとどれぐらいの経路を詰め込むことができるかの期待値e12,4を求める場合を考える。
【００７４】
経路割当数テーブルＴ１ａ−１から、a1＝７、a2＝７、a3＝６であり、経路割当数テーブルＴ１ｂ−１から、b12,4＝４であるから、式（１）にもとづいて、期待値e12,4は、以下のように算出される。
【００７５】
e12,4＝（a1＋a2＋a3＋b12,4）／（L×N）＝（７＋７＋６＋４）／（１２×４）＝０．５・・・（１ｂ）
同様にして他の期待値も算出して期待値テーブルＴ２−１を作成しておくことになる。そして、次の経路要求があった場合には、期待値テーブルＴ２−１で管理されている期待値にもとづき、期待値の最も大きいスロットを経路割当先に決定して即時応答する。その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。以降この繰り返しとなる。上記のような期待値の更新処理を行うことで、短時間で次の経路変更要求に備えた期待値の導出が可能となる。
【００７６】
なお、上記の制御は、経路を増やす方向の期待値の算出について説明したが、経路を減らす方向に対しても上述のaj、bi,j、ei,jに相当する値を準備しておき、同様の期待値の予測計算を適用することができる。
【００７７】
図１３は運用前の動作シーケンスを示す図である。
〔Ｓ１〕経路割当装置１０の経路算出部１１は、所定の経路に含まれるパス数を計算する。
【００７８】
〔Ｓ２〕経路算出部１１は、エッジノードに対して、所定の経路に含まれるパスを登録する。
〔Ｓ３〕エッジノードは、自ノードにパス登録を行って応答を返信する。なお、ステップＳ２のパス登録およびステップＳ３のパス登録応答は必要なパス数の数だけ繰り返す。
【００７９】
〔Ｓ４〕経路算出部１１は、中継ノードに対して、所定の経路に含まれるパスを登録する。
〔Ｓ５〕中継ノードは、自ノードにパス登録を行って応答を返信する。なお、ステップＳ４のパス登録およびステップＳ５のパス登録応答は必要なパス数の数だけ繰り返す。
【００８０】
〔Ｓ６〕経路割当制御部１２は、期待値の事前計算を行う。
〔Ｓ７〕システムの運用が開始される。
図１４は運用時の動作シーケンスを示す図である。
【００８１】
〔Ｓ１１〕発信（送信元）エッジノードが経路の帯域変動を認識する。
〔Ｓ１２〕発信エッジノードは、経路内のパス数の増加または減少に関するパス数変更要求を経路割当装置１０へ送信する。
【００８２】
〔Ｓ１３〕経路割当装置１０の経路割当制御部１２は、現在の期待値テーブルにもとづいて、パス増加要求時には、期待値の最も大きいスロットに対して、増加したパスを割当てる。パス減少要求時には、期待値の最も大きいスロットから、減少したパスを削除する。
【００８３】
〔Ｓ１４〕経路算出部１１は、発信エッジノード、中継ノードおよび着信（宛先）エッジノードに、パス登録またはパス削除のメッセージを送信する。
〔Ｓ１５〕発信エッジノード、中継ノードおよび着信エッジノードは、自ノードにパスの登録またはパスの削除を行って応答を返信する。
【００８４】
〔Ｓ１６〕経路割当制御部１２は、発信エッジノードに対して、どのスロットに経路を詰め込むかのスロット変更を示すスロット変更要求応答を送信する。
〔Ｓ１７〕経路割当制御部１２は、変更があった箇所の差分に関する部分だけ演算を行って、次の経路変更要求に備えて期待値更新処理を行う。
【００８５】
以上説明したように、経路割当装置１０によれば、運用中フェーズにおいても期待値ベースの経路割当を適用して、スロットの利用効率の最適化を実現することができる（より多くの経路を詰込むことができる）。また、運用中の期待値計算は、計算量を小さくして更新するので、運用時にも経路割当を高速に行うことができ、リアルタイムの応答が可能となり、通信効率の向上を図ることが可能になる。
【００８６】
次に変形例について説明する。経路割当装置１０では、TDM（Time Division Multiplexing）により時間軸上に複数のスロットを設けて、動的割り当てを高速に行うものとして説明したが、時間間隔のスロットではなく、波長に経路を割当て、光通信を行うことも可能である。
【００８７】
図１５は経路割当装置の構成例を示す図である。上述の経路割当装置１０では、時間軸上でスロットを定義したが、経路割当装置１０ａでは、波長軸上で定義される波長に置き換える。つまり、時間軸上のTDMパスが、波長軸上のλパスに置き換わる。
【００８８】
経路割当装置１０ａは、経路算出部１１ａと経路割当制御部１２ａを含む。経路算出部１１ａは、光ネットワーク内の発信ノードから着信ノード間の経路を求める。経路割当制御部１２ａは、波長に経路を割当てる。
【００８９】
ここで、経路割当制御部１２ａは、波長への経路の割当可能数の指標となる期待値を算出して、期待値が最大となる経路割当を選択する。また、選択された１つの波長に対する経路の割当可能な数を求めて、経路割当後の次の期待値を更新する。
【００９０】
次に波長への経路詰め込みについて図１６〜図１８を用いて説明する。図１６はネットワーク構成例を示す図である。ネットワークＮ１ａは、エッジノード１〜４および中継ノード５、６を含む。基本トポロジは、図２のネットワークＮ１と同じであるが、ノード間のリンクは、光ファイバで構成される。なお、ネットワークＮ１ａの経路テーブルは、図３と同じである。
【００９１】
図１７、図１８は波長が使用している経路を示す図である。異なる波長が全部で４（＝W）つあるとし（波長λ１〜λ４）、波長λ１〜λ４のそれぞれには図１７、図１８に示すような利用状況で経路が現在詰め込まれているとする。
【００９２】
すなわち、図１７に対し、波長λ１、λ２には、経路（１）が詰め込まれ、図１８に対し、波長λ３には、経路（２）が詰め込まれており、波長λ４には、経路は何も詰め込まれていないとする。
【００９３】
この場合、波長λ１に対してさらに詰め込み可能な経路数は７、波長λ２に対してさらに詰め込み可能な経路数は７となる。また、波長λ３に対してさらに詰め込み可能な経路数は６、波長λ４に対して詰め込み可能な経路数は１２となる。
【００９４】
次に波長λ１〜λ４に対する期待値の事前計算について説明する。経路割当制御部１２ａでは、期待値算出に当たって、まず、パラメータ（aj、bi,j）をそれぞれ構成要素とするテーブルを作成管理する。なお、jは波長番号、iは経路番号である。
【００９５】
図１９は経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ａは、パラメータajを含むテーブルであり、ajは、現在の割当状態において波長jに詰め込み可能な経路数を示す。波長λ１〜λ４に詰め込み可能な経路数は７、７、６、１２であるので、a1＝７、a2＝７、a3＝６、a4＝１２である。
【００９６】
図２０は経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ｂは、パラメータbi,jを含むテーブルであり、bi,jは、現在の経路割当状態に対し、もし任意の経路iを波長jに割当てたとした場合の、その後の詰め込み可能な経路数を示す。
【００９７】
経路割当数テーブルＴ１１ａ、Ｔ１１ｂ使って、現在の経路割当状態に対して、経路iを波長jに割当てたときの期待値ei,jを計算する。ei,jは、現在の割当状態に対し、もし経路iを波長jに割当てたとした場合の、その後のシステム全体の期待値を表す。
【００９８】
ここで、Wを経路割当に使用する波長の数、Lを経路数とすると、期待値ei,jは式（２）で算出される。
【００９９】
【数２】
【０１００】
図２１は期待値テーブルを示す図である。期待値テーブルＴ２２は、図１９、図２０で示した経路割当数テーブルＴ１１ａ、Ｔ１１ｂそれぞれのajおよびbi,jにもとづき、式（２）を用いて計算した期待値ei,jの値を示している。期待値算出例は、上述の経路割当装置１０の場合と同じなので説明は省略する。
【０１０１】
式（２）によって期待値を算出することで、ある波長に対する現在の経路割当状態に対して、ある経路を仮に詰め込んだ場合に、その後どれだけ経路を詰め込めるかといった指標を効率よく求めることが可能になる。
【０１０２】
なお、期待値テーブルＴ２２において、各行で一番値の大きいものが、経路要求されたときに割当てる波長になり（期待値が大きい方がより多くの経路を動的に割当てることができるため）、これを割当波長として記憶保持しておく。図２１中の黒太枠欄は、割当波長として記憶しておくべき値である。
【０１０３】
次に運用時に経路変更要求があった場合の動作について説明する。経路変更要求を受信したとき、事前の期待値計算によって抽出しておいた、期待値が一番大きい波長を経路割当先に決定して応答する。
【０１０４】
その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。この更新を行う場合に、期待値事前計算で行った手順を再び最初から繰り返すと計算量が大きくなるので、変化のあった部分のみを計算して計算量を削減する。期待値の更新処理は上記の［１］〜［３］と同じである。ここでは、割当てられた波長の番号をJとする。
【０１０５】
ここで、波長λ４に経路（１）を割当てた後の更新処理について説明する。更新手順としてまず、aJをbI,Jで置き換える。
図２２は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ａ−１は、更新後のパラメータajを含むテーブル状態を示している。
【０１０６】
波長λ４に経路（１）を割当てたので、I＝１、J＝４である。したがって、図１９に示した経路割当数テーブルＴ１１ａのa4（＝１２）を、図２０の経路割当数テーブルＴ１１ｂのb1,4（＝７）で置き換えることになるので、経路割当数テーブルＴ１１ａ−１のa4が７と更新される。
【０１０７】
次の更新手順として、波長λ４の現在の割当状態に対して、経路（１）〜（１２）を割当てた場合に、あと何個経路を詰め込めるかを再計算して経路割当数テーブルＴ１１ｂを書き替える。このとき、波長λ１〜λ３に関しての再計算は行わない。
【０１０８】
図２３は更新後の経路割当数テーブルを示す図である。経路割当数テーブルＴ１１ｂ−１は、更新後のパラメータbi,jを含むテーブル状態を示している。経路割当後の波長λ４への詰め込み可能数であるbi,4（1≦i≦L）を求めることになる。すなわち、b1,4、b2,4、b3,4、b4,4、b5,4、b6,4、b7,4、b8,4、b9,4、b10,4、b11,4、b12,4の値をそれぞれ計算し、例えば、太線枠内に示すような数値となったとする。
【０１０９】
次の更新手順としては、経路割当数テーブルＴ１１ａ−１、Ｔ１１ｂ−１それぞれのajおよびbi,jにもとづき、式（２）により期待値ei,jを計算する。
図２４は更新後の期待値テーブルを示す図である。更新時の期待値の計算によって期待値テーブルＴ２２−１が作成される。期待値の算出として、例えば、波長λ４に経路（１２）を詰め込むと、あとどれぐらいの経路を詰め込むことができるかの期待値e12,4を求める場合を考える。
【０１１０】
経路割当数テーブルＴ１１ａ−１から、a1＝７、a2＝７、a3＝６であり、経路割当数テーブルＴ１１ｂ−１から、b12,4＝４であるから、式（２）にもとづいて、期待値e12,4は、以下のように算出される。
【０１１１】
e12,4＝（a1＋a2＋a3＋b12,4）／（L×W）＝（７＋７＋６＋４）／（１２×４）＝０．５・・・（２ａ）
同様にして他の期待値も算出して期待値テーブルＴ２２−１を作成しておく。そして、次の経路要求があった場合には、期待値テーブルＴ２２−１で管理されている期待値にもとづき、期待値の最も大きい波長を経路割当先に決定して即時応答する。その後、経路割当決定後のajとbi,jを修正し、次の変更要求に備えて、あらためて期待値を算出して更新する。以降この繰り返しとなる。上記のような期待値の更新処理を行うことで、短時間で次の経路変更要求に備えた期待値の導出が可能となる。
【０１１２】
次に経路割当装置１０の機能を含む管理サーバが配置された、省電力ネットワークの概要について説明する。図２５は省電力ネットワークの構成例を示す図である。ネットワークＮ１−１は、図２で示したネットワークＮ１に管理サーバ１０−１が配置された構成をとる。
【０１１３】
〔Ｓ２１〕管理サーバ１０−１は、ネットワークＮ１−１の構成と、各経路（発信エッジノードと着信エッジノードとの組合せ）とを認識し、経路の帯域デマンドとして、経路毎の最小帯域値および最大帯域値を認識する。
【０１１４】
〔Ｓ２２〕管理サーバ１０−１は、さらに、最小帯域値を満たすように、スロットへの経路割当を導出し、各ノード（エッジノード１〜４および中継ノード５、６）に設定する。
【０１１５】
〔Ｓ２３〕エッジノード１〜４は、経路毎のトラフィック量を監視し、その経路に割当てられた帯域が適切か、余剰か、または不足かを判定して、最小帯域値から最大帯域値の間でパス数の変更があるか否かを認識し、変更がある場合は管理サーバ１０−１に通知する。
【０１１６】
〔Ｓ２４〕エッジノード１に例えば、外部からパケットが到着する。エッジノード１は、宛先エッジノード毎にパケットを分類し、パス割当の増加が必要と判断したとする。
〔Ｓ２５〕エッジノード１は、管理サーバ１０−１に対し、パケット送出に必要なスロットの予約を要求する。
【０１１７】
〔Ｓ２６〕管理サーバ１０−１は、スロット予約要求を受信すると、期待値にもとづいて経路割当において最適なスロットを選択して、経路割当の調整を行う。
〔Ｓ２６ａ〕管理サーバ１０−１は、経路割当の結果をエッジノード１に応答する。
【０１１８】
〔Ｓ２７〕エッジノード１は、中継ノード５、６にスロットの付け替えを指定する。
〔Ｓ２８〕エッジノード１は、管理サーバ１０−１で通知されたスロットに合わせて、該当パケットを送出する。なお、中継ノード５、６は、スロットＩＤに合わせてバッファレス伝送でパケットを中継送信する。
【０１１９】
図２６はスロットが配置されたフレームを示す図である。横軸は時間、縦軸はフレームデリミタである。スロット＃１〜＃ｎが配置されたフレームが繰り返しエッジノードから送出される。また、同じ経路（パス）は、同一番号のスロットを連続して使用して送信される。
【０１２０】
以上説明したように、経路割当装置１０の機能を含む管理サーバ１０−１を配置して、送信すべきパケットのスロットをあらかじめ割当て、時分割ベースでパケット転送を行うことで、省電力ネットワークを構築することが可能になる。
【０１２１】
また、管理サーバ１０−１では、スロットへ経路を割当てる期待値を算出し、短時間で期待値更新処理を行って、最適経路割当を高速に行うことができるので、エッジノードからの経路変更要求に対してリアルタイムの応答が可能であり、遅延を抑制して通信効率の向上を図ることが可能になる。
【０１２２】
なお、上記の経路割当装置１０の処理機能は、コンピュータによって実現することができる。その場合、経路割当装置１０が有すべき機能の処理内容を記述したプログラム（経路割当プログラム）が提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１２３】
コンピュータは、ＣＰＵによって装置全体が制御される。ＣＰＵには、バスを介してＲＡＭ、ハードディスクドライブ、通信インタフェース、グラフィック処理装置、および入出力インタフェースが接続される。
【０１２４】
ＲＡＭには、ＣＰＵに実行させるＯＳ（Operating System）のプログラムや、経路割当を行うためのプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭには、ＣＰＵによる処理に必要な各種データが格納される。ＨＤＤメッセージには、ＯＳやアプリケーションプログラムが格納される。
【０１２５】
通信インタフェースは、ネットワークに接続されている。通信インタフェースは、ネットワークを介して、他のコンピュータとの間でデータの送受信を行う。グラフィック処理装置は、モニタが接続されている。グラフィック処理装置は、ＣＰＵからの命令にしたがって画像をモニタの画面に表示させる。
【０１２６】
入出力インタフェースには、キーボードとマウスとが接続されている。入出力インタフェースは、キーボードやマウスから送られてくる信号を、バスを介してＣＰＵに送信する。また、入出力インタフェースは、外部記憶媒体への情報の書き込みおよび外部記憶媒体への情報の読出しが可能な外部記憶媒体インタフェースと接続可能になっている。
【０１２７】
経路割当装置１０は、経路割当装置が有すべき機能の処理内容を記述したプログラムをコンピュータで実行することにより実現することができる。すなわち、図１の経路算出部１１、経路割当制御部１２に対応する処理内容をプログラムとして記述する。ここで、記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【０１２８】
コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。
【０１２９】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１３０】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０１３１】
プログラムを実行するコンピュータは、例えば、外部記憶媒体に記録されたプログラムまたはサーバプログラムから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは自己の記憶装置からプログラムを読み取り、プログラムにしたがった処理を実行する。なお、コンピュータは、外部記憶媒体から直接プログラムを読み取り、そのプログラムにしたがった処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次受け取ったプログラムにしたがった処理を実行することもできる。
【０１３２】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。
（付記１） ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
通信スロットに前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【０１３３】
（付記２） 前記経路割当制御部は、
前記通信スロットの番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して通信スロットjに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを通信スロットjに割当てたとした場合の通信スロットjに割当可能な前記経路の数をbi,jとし、前記通信スロットの数をN、前記経路の数をLとした場合、前記期待値であるei,jを、
【０１３４】
【数１】
【０１３５】
で算出することを特徴とする付記１記載の経路割当装置。
（付記３） 前記経路割当制御部は、番号Jの前記通信スロットに、番号Iの前記経路の割当を行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする付記２記載の経路割当装置。
【０１３６】
（付記４） 経路割当方法において、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
通信スロットに前記経路を割当てる場合に、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【０１３７】
（付記５） 光ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
波長に前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【０１３８】
（付記６） 前記経路割当制御部は、
前記波長の番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して波長jに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを波長jに割当てたとした場合の波長jに割当可能な前記経路の数をbi,jとし、前記波長の数をW、前記経路の数をLとした場合、前記期待値であるei,jを、
【０１３９】
【数２】
【０１４０】
で算出することを特徴とする付記５記載の経路割当装置。
（付記７） 前記経路割当制御部は、番号Jの前記波長に、番号Iの前記経路の割当を行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする付記６記載の経路割当装置。
【０１４１】
（付記８） 経路割当方法において、
光ネットワーク内の発信ノードから着信ノード間の経路を求め、
波長に前記経路を割当てる場合に、
前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【０１４２】
（付記９） 通信システムにおいて、
データ送信元の発信ノードと、
前記発信ノードから着信ノード間の経路を求める経路算出部と、通信スロットに前記経路を割当てる経路割当制御部とを含む管理サーバと、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択して前記発信ノードへ通知し、経路割当後に選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新しておき、
前記発信ノードは、経路が割当てられた前記通信スロットに合わせてデータを送信し、運用中に経路変動を認識した場合は、前記管理サーバへ経路変更要求を送信し、
前記経路割当制御部は、前記経路変更要求を受信すると、先に更新しておいた前記期待値が最大となる経路割当を選択して前記発信ノードへ通知し、前記期待値の更新処理を繰り返す、
ことを特徴とする通信システム。
【０１４３】
（付記１０） 前記経路割当制御部は、
前記通信スロットの番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して通信スロットjに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを通信スロットjに割当てたとした場合の通信スロットjに割当可能な前記経路の数をbi,jとし、前記通信スロットの数をN、前記経路の数をLとした場合、前記期待値であるei,jを、
【０１４４】
【数１】
【０１４５】
で算出することを特徴とする付記９記載の通信システム。
（付記１１） 前記経路割当制御部は、番号Jの前記通信スロットに、番号Iの前記経路の割当てを行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする付記１０記載の通信システム。
【０１４６】
（付記１２） 通信スロットに経路を割当てる制御をコンピュータに実行させる経路割当プログラムにおいて、
前記コンピュータに、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
処理を実行させることを特徴とする経路割当プログラム。
【符号の説明】
【０１４７】
１０ 経路割当装置
１１ 経路算出部
１２ 経路割当制御部
【特許請求の範囲】
【請求項１】
ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
通信スロットに前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【請求項２】
前記経路割当制御部は、
前記通信スロットの番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して通信スロットjに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを通信スロットjに割当てたとした場合の通信スロットjに割当可能な前記経路の数をbi,jとし、前記通信スロットの数をN、前記経路の数をLとした場合、前記期待値であるei,jを、
【数１】
で算出することを特徴とする請求項１記載の経路割当装置。
【請求項３】
前記経路割当制御部は、番号Jの前記通信スロットに、番号Iの前記経路の割当を行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする請求項２記載の経路割当装置。
【請求項４】
経路割当方法において、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
通信スロットに前記経路を割当てる場合に、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【請求項５】
光ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
波長に前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【請求項６】
前記経路割当制御部は、
前記波長の番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して波長jに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを波長jに割当てたとした場合の波長jに割当可能な前記経路の数をbi,jとし、前記波長の数をW、前記経路の数をLとした場合、前記期待値であるei,jを、
【数２】
で算出することを特徴とする請求項５記載の経路割当装置。
【請求項７】
通信スロットに経路を割当てる制御をコンピュータに実行させる経路割当プログラムにおいて、
前記コンピュータに、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
処理を実行させることを特徴とする経路割当プログラム。
【請求項８】
経路割当方法において、
光ネットワーク内の発信ノードから着信ノード間の経路を求め、
波長に前記経路を割当てる場合に、
前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【請求項１】
ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
通信スロットに前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【請求項２】
前記経路割当制御部は、
前記通信スロットの番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して通信スロットjに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを通信スロットjに割当てたとした場合の通信スロットjに割当可能な前記経路の数をbi,jとし、前記通信スロットの数をN、前記経路の数をLとした場合、前記期待値であるei,jを、
【数１】
で算出することを特徴とする請求項１記載の経路割当装置。
【請求項３】
前記経路割当制御部は、番号Jの前記通信スロットに、番号Iの前記経路の割当を行った場合、aJをbI,Jで置き換え、経路割当後のbi,J（1≦i≦L）を求めて、ei,jを再計算することで、前記期待値を更新することを特徴とする請求項２記載の経路割当装置。
【請求項４】
経路割当方法において、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
通信スロットに前記経路を割当てる場合に、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【請求項５】
光ネットワーク内の発信ノードから着信ノード間の経路を求める経路算出部と、
波長に前記経路を割当てる経路割当制御部と、
を備え、
前記経路割当制御部は、前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当装置。
【請求項６】
前記経路割当制御部は、
前記波長の番号をj、前記経路の番号をiとしたとき、
現在の経路割当状態に対して波長jに割当可能な前記経路の数をajとし、現在の経路割当状態に対して経路iを波長jに割当てたとした場合の波長jに割当可能な前記経路の数をbi,jとし、前記波長の数をW、前記経路の数をLとした場合、前記期待値であるei,jを、
【数２】
で算出することを特徴とする請求項５記載の経路割当装置。
【請求項７】
通信スロットに経路を割当てる制御をコンピュータに実行させる経路割当プログラムにおいて、
前記コンピュータに、
ネットワーク内の発信ノードから着信ノード間の経路を求め、
前記通信スロットへの前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記通信スロットに対する前記経路の割当可能な数を求めて、前記期待値を更新する、
処理を実行させることを特徴とする経路割当プログラム。
【請求項８】
経路割当方法において、
光ネットワーク内の発信ノードから着信ノード間の経路を求め、
波長に前記経路を割当てる場合に、
前記波長への前記経路の割当可能数の指標となる期待値を算出して、前記期待値が最大となる経路割当を選択し、
経路割当後、選択された前記波長に対する前記経路の割当可能な数を求めて、前記期待値を更新する、
ことを特徴とする経路割当方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２０１１−１７６５１８（Ｐ２０１１−１７６５１８Ａ）
【公開日】平成２３年９月８日（２０１１．９．８）
【国際特許分類】
【出願番号】特願２０１０−３８１４１（Ｐ２０１０−３８１４１）
【出願日】平成２２年２月２４日（２０１０．２．２４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、総務省、「低消費電力型通信技術等の研究開発（エコインターネットの実現）」研究開発委託契約に基づく開発項目「 簡素化ルータを用いた省電力フォワーディング技術」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年９月８日（２０１１．９．８）
【国際特許分類】
【出願日】平成２２年２月２４日（２０１０．２．２４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、総務省、「低消費電力型通信技術等の研究開発（エコインターネットの実現）」研究開発委託契約に基づく開発項目「 簡素化ルータを用いた省電力フォワーディング技術」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]