(57)【特許請求の範囲】
【請求項１】
他のルータとの間に張られたリンクを経由して、転送順が定義された経路に沿ってネットワークに入力されたトラフィックを転送するルータにおいて、
特定のリンクを経由して転送されるトラフィックの少なくとも一部を前記特定のリンクを経由しない経路で転送させる場合に、各リンクを介して転送されるトラフィックの前記ネットワーク内での経路を記憶する経路記憶手段を参照し、前記特定のリンクを介して転送される１または複数のトラフィックの経路を対象経路とし、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ前記特定のリンクを経由しない経路を分散経路候補とし、分散経路候補のトラフィックを中継するルータの状態を示す状態情報を管理している管理装置から、各分散経路候補の状態情報を取得する状態情報取得手段と、
前記状態情報取得手段が取得した各分散経路候補の状態情報に基づいて、分散経路候補へ前記特定のリンクのトラフィックの一部を流した場合の経路上の他のルータの状態の変化を比較し、状態の変化による消費電力の増加量が少ない経路を優先的に分散先経路として決定する分散先決定手段と、
前記分散先決定手段で決定した前記分散先経路へ、経路上の最初と最後のルータの両方が前記分散先経路と共通である前記対象経路のトラフィックの少なくとも一部を振り分けるように、該対象経路上の最初のルータに指示する分散要求を送信する分散要求手段と、
を有することを特徴とするルータ。
【請求項２】
前記状態情報取得手段は、前記分散経路候補の経路上のルータのうち省電力モードの状態のルータ数を管理装置から取得し、
前記分散先決定手段は、経路上のルータのうち省電力モードの状態のルータ数が少ない分散経路候補を、優先的に分散先経路に決定することを特徴とする請求項１記載のルータ。
【請求項３】
前記状態情報取得手段は、前記分散経路候補の経路上のトラフィックが単位データ量増加したときの経路上の各ルータの消費電力増加量を管理装置から取得し、
前記分散先決定手段は、トラフィックが所定量だけ増加したときの経路上の各ルータの消費電力増加量が少ない分散経路候補を、優先的に分散先経路に決定することを特徴とする請求項１または請求項２のいずれかに記載のルータ。
【請求項４】
他のルータとの間に張られた各リンクのトラフィック量を測定し、輻輳発生の予兆を検出する輻輳予兆検出手段をさらに有し、
前記状態情報取得手段は、前記輻輳予兆検出手段が輻輳発生の予兆を検出したリンクを、前記特定のリンクとすることを特徴とする請求項１乃至３のいずれかに記載のルータ。
【請求項５】
前記分散要求手段は、前記輻輳予兆検出手段により輻輳発生の予兆が検出されたリンクの輻輳発生の予兆が継続している間、所定間隔で前記分散要求を繰り返し送信することを特徴とする請求項４記載のルータ。
【請求項６】
前記状態情報取得手段は、対象経路それぞれの最初のルータを前記管理装置と判断し、対象経路それぞれの最初のルータから各分散経路候補の状態情報を取得することを特徴とする請求項１乃至５のいずれかに記載のルータ。
【請求項７】
前記状態情報取得手段は、対象経路それぞれの最初のルータに対して該対象経路の最初と最後のルータが示されたアラーム情報を送信し、該最初のルータから、経路上の最初と最後のルータが該対象経路と共通の分散経路候補、および該分散経路候補の状態情報を取得することを特徴とする請求項６記載のルータ。
【請求項８】
ネットワーク内でトラフィックを転送順が定義された経路に沿って転送する各ルータから、該ルータの状態を示す状態情報を収集し、該ルータの状態情報を、該ルータが転送するトラフィックの経路と対応付けて経路状態記憶手段に格納する状態情報収集手段と、
前記ネットワーク内の複数ルータ間に張られた特定のリンクを経由して転送されるトラフィックの経路を対象経路とし、該対象経路の最初と最後のルータが示されたアラーム情報を受信すると、前記経路状態記憶手段を参照し、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ前記特定のリンクを経由しない経路を分散経路候補とし、該分散経路候補の状態情報を前記アラーム情報の発信元に送信する状態情報通知手段と、
を有することを特徴とする管理装置。
【請求項９】
前記経路状態記憶手段は、経路上の最初と最後のルータが共通の経路間での各経路へのトラフィックの送出確率を記憶しており、
前記経路状態記憶手段に示される送出確率で、他のネットワークから流入するトラフィックを前記ネットワーク内の経路に分散して転送する中継手段と、
前記対象経路のトラフィックの少なくとも一部を振り分ける分散先経路を指定する分散指示を受け取ると、前記経路状態記憶手段に対して、前記対象経路へのトラフィックの送出確率を減らし、前記分散先経路へのトラフィックの送出確率を増やす更新処理を行う送出確率変更手段と、
をさらに有することを特徴とする請求項８記載の管理装置。
【請求項１０】
他のルータとの間に張られたリンクを経由して、転送順が定義された経路に沿ってネットワークに入力されたトラフィックを転送する処理をコンピュータに実行させるルーティング制御プログラムにおいて、
前記コンピュータに、
特定のリンクを経由して転送されるトラフィックの少なくとも一部を前記特定のリンクを経由しない経路で転送させる場合に、各リンクを介して転送されるトラフィックの前記ネットワーク内での経路を記憶する経路記憶手段を参照し、前記特定のリンクを介して転送される１または複数のトラフィックの経路を対象経路とし、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ前記特定のリンクを経由しない経路を分散経路候補とし、分散経路候補のトラフィックを中継するルータの状態を示す状態情報を管理している管理装置から、各分散経路候補の状態情報を取得し、
取得した各分散経路候補の状態情報に基づいて、分散経路候補へ前記特定のリンクのトラフィックの一部を流した場合の経路上の他のルータの状態の変化を比較し、状態の変化による消費電力の増加量が少ない経路を優先的に分散先経路として決定し、
決定した前記分散先経路へ、経路上の最初と最後のルータの両方が分散先経路と共通である前記対象経路のトラフィックの少なくとも一部を振り分けるように、該対象経路上の最初のルータに指示する分散要求を送信する、
処理を実行させることを特徴とするルーティング制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワーク上のトラフィックの振り分けを制御するルータ、管理装置およびルーティング制御プログラムに関する。
【背景技術】
【０００２】
ネットワークでは複数のルータがパケットを中継し、宛先のコンピュータまでパケットを伝送させる。各ルータはパケットの宛先までの伝送経路を認識するために、経路情報を相互に交換している。経路情報には、その経路情報を送信したルータが認識している伝送経路が示されている。各ルータは、他のルータから受信した経路情報に基づいて、宛先に応じたパケットの転送先を選択する。
【０００３】
ルータから宛先のコンピュータへの伝送経路が複数存在する場合、ルータは、所定のアルゴリズムで経路選択を行う。ルータにおける経路選択のアルゴリズムは、ＯＳＰＦ（Open Shortest Path First）やＲＩＰ（Routing Information Protocol）などのルーティングプロトコルに規定されている。これらのルーティングプロトコルでは、基本的には最短経路を採るように経路選択が行われる。あるいは、これらのルーティングプロトコルを用いた既存の高度な制御としては、ネットワーク利用率のピークを最小化するよう平滑化しつつ、最短経路を採るように経路選択が行われる。
【０００４】
このような従来のルーティングプロトコルでは、パケットなどのトラフィック（ネットワーク上を移動するデータ）は予め決められた経路に沿って転送される。そのため、全体的にトラフィックが少ない時間帯が存在しても、各ルータを起動させ続けなければならない。
【０００５】
他方、ネットワークの処理能力の向上に伴い、ネットワークを構成する機器による消費電力も増加している。そのため、ネットワーク全体での消費電力を抑制した運用を行うことの重要性が高まっている。そこで、例えばトラフィックの低下したハイウェイを自動的に検出して、該ハイウェイ内のデータを他のハイウェイに自動的に迂回させる技術が考えられている。データを迂回させたことで未使用状態に移行した電子交換機内装置に対し電源をＯＦＦの制御を行うことで、消費電力の削減が可能となる。また、トラフィックが少ない場合には経路を集約させることで、多くの空きルータを生成する技術も考えられている。
【０００６】
逆に、トラフィックで輻輳が発生した場合には、トラフィックを分散させる技術がある。例えば、入力エッジルータと出力エッジルータとの間に設定した複数のパスに、入力エッジルータへの入力トラフィックを分散させる技術がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００１−１１９７３０号公報
【特許文献２】特開２００４−４８３３０号公報
【非特許文献】
【０００８】
【非特許文献１】山田亜紀子、外３名、「グリーンネットワークに向けた一検討（３）ＥＣＯルーティング」、電子情報通信学会総合大会講演論文集、社団法人電子情報通信学会、２００９年３月４日、2009年＿通信（２）、pp.252
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、ネットワークを構成するルータ間を接続するリンクのうち、一部のリンクで輻輳が発生することがある。その場合、そのリンクを経由したパスを利用するトラフィックが、他のパスに分散される。パスは、トラフィックが入力されるルータから、そのトラフィックの転送先となるルータへの転送経路である。
【００１０】
しかし、一部のルータが省電力モード（スリープモード）となっているネットワークにおいて、輻輳発生の可能性があるリンクを経由するトラフィックをすべて分散させると、省電力モードとなっていたルータが起動してしまい、省電力化の妨げとなる場合がある。例えば、トラフィックが所定の閾値を超えたリンクを経由するパスが複数ある場合がある。輻輳の発生を抑制するには、トラフィックが閾値を超えたリンクを経由する一部のパスのトラフィックを、別経路に負荷分散すれば十分な場合もある。このような場合にまで、閾値を超えたリンクを経由するすべてのパスを介したトラフィックを別経路へ負荷分散させると、転送経路を集約して通過トラフィックを無くしてスリープしていたルータを必要以上に起動させることになる。その結果、消費電力が必要以上に増加することになる。
【００１１】
なお、このような問題は、輻輳発生の抑制のみではなく、例えばリンクの障害によるトラフィックの迂回経路探索時にも同様に生じる。
本発明はこのような点に鑑みてなされたものであり、トラフィックの少なくとも一部の転送経路を変更する際の消費電力の増加を抑制することができるルータ、管理装置およびルーティング制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、他のルータとの間に張られたリンクを経由して、転送順が定義された経路に沿ってネットワークに入力されたトラフィックを転送する、以下に示すルータが提供される。
【００１３】
ルータは、状態情報取得手段、分散先決定手段、および分散要求手段を有する。状態情報取得手段は、特定のリンクを経由して転送されるトラフィックの少なくとも一部を特定のリンクを経由しない経路で転送させる場合に、各リンクを介して転送されるトラフィックのネットワーク内での経路を記憶する経路記憶手段を参照する。そして状態情報取得手段は、特定のリンクを介して転送される１または複数のトラフィックの経路を対象経路とする。さらに状態情報取得手段は、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ特定のリンクを経由しない経路を分散経路候補とする。そして状態情報取得手段は、分散経路候補のトラフィックを中継するルータの状態を示す状態情報を管理している管理装置から、各分散経路候補の状態情報を取得する。分散先決定手段は、状態情報取得手段が取得した各分散経路候補の状態情報に基づいて、分散経路候補へ特定のリンクのトラフィックの一部を流した場合の経路上の他のルータの状態の変化を比較する。そして分散先決定手段は、状態の変化による消費電力の増加量が少ない経路を優先的に分散先経路として決定する。分散要求手段は、分散先決定手段で決定した分散先経路へ、経路上の最初と最後のルータの両方が分散先経路と共通である対象経路のトラフィックの少なくとも一部を振り分けるように、その対象経路上の最初のルータに指示する分散要求を送信する。
【００１４】
また上記課題を解決するために、以下に示す管理装置が提供される。
管理装置は、状態情報収集手段と状態情報通知手段とを有する。状態情報収集手段は、ネットワーク内でトラフィックを転送順が定義された経路に沿って転送する各ルータから、該ルータの状態を示す状態情報を収集する。そして状態情報収集手段は、ルータの状態情報を、該ルータが転送するトラフィックの経路と対応付けて経路状態記憶手段に格納する。状態情報通知手段は、ネットワーク内の複数ルータ間に張られた特定のリンクを経由して転送されるトラフィックの経路を対象経路とする。状態情報通知手段は、該対象経路の最初と最後のルータが示されたアラーム情報を受信すると、経路状態記憶手段を参照し、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ特定のリンクを経由しない経路を分散経路候補とする。そして状態情報通知手段は、該分散経路候補の状態情報をアラーム情報の発信元に送信する。
【００１５】
さらに上記課題を解決するために、上記ルータと同様の処理をコンピュータに実行させるためのルーティング制御プログラムが提供される。
【発明の効果】
【００１６】
トラフィックの少なくとも一部の転送経路を他の経路に振り分ける場合に、消費電力の増加量が少ない経路へトラフィックを振り分けることができる。
【図面の簡単な説明】
【００１７】
【図１】第１の実施の形態の機能を示すブロック図である。
【図２】輻輳の予兆検出時の処理を示す図である。
【図３】アラーム情報を受信したルータの処理を示す図である。
【図４】分散要求の送信処理を示す図である。
【図５】送出確率変更後のトラフィックの振り分けを示す図である。
【図６】第２の実施の形態のシステム構成例を示す図である。
【図７】本実施の形態に用いる中継ノードのハードウェアの一構成例を示す図である。
【図８】トラフィックの集約例を示す図である。
【図９】リンク利用率とアラーム情報送信との関係を示す図である。
【図１０】中継ノードの機能を示すブロック図である。
【図１１】フロー情報記憶部のデータ構造例を示す図である。
【図１２】リンク情報記憶部のデータ構造例を示す図である。
【図１３】エッジノードの機能を示すブロック図である。
【図１４】ノードＩＤ「Ａ」のエッジノードの経路状態情報記憶部のデータ構造例を示す図である。
【図１５】経路状態情報収集処理の一例を示す図である。
【図１６】経路「ＡＥＤ」と経路「ＢＥＤ」との経路空き容量計算例を示す図である。
【図１７】ノードＩＤ「Ｂ」のエッジノードの経路状態情報記憶部のデータ構造例を示す図である。
【図１８】入口ノードでの経路状態情報収集処理の手順を示すフローチャートである。
【図１９】経路状態情報通知処理の手順を示すフローチャートである。
【図２０】輻輳の予兆発生例を示す図である。
【図２１】輻輳検出処理の手順の一例を示すフローチャートである。
【図２２】フロー情報更新後のフロー情報記憶部の例を示す図である。
【図２３】リンク情報更新後のリンク情報記憶部の例を示す図である。
【図２４】ノードＩＤ「Ａ」のエッジノードの更新後の経路状態情報記憶部の例を示す図である。
【図２５】ノードＩＤ「Ｂ」のエッジノードの更新後の経路状態情報記憶部の例を示す図である。
【図２６】輻輳制御処理の手順の一例を示すフローチャートである。
【図２７】分散経路募集処理によるアラーム情報の送信状況を示す図である。
【図２８】アラーム情報の転送が生じる態様を示す図である。
【図２９】分散経路募集処理の一例を示すフローチャートである。
【図３０】ノードＩＤ「Ａ」のエッジノードのアラーム情報受信後の経路状態情報記憶部の例を示す図である。
【図３１】ノードＩＤ「Ｂ」のエッジノードのアラーム情報受信後の経路状態情報記憶部の例を示す図である。
【図３２】入札メッセージの送信例を示す図である。
【図３３】入札処理の手順を示す図である。
【図３４】分散要求の送信例を示す図である。
【図３５】分散先経路決定処理の手順の一例を示すフローチャートである。
【図３６】分散経路候補評価処理の手順の一例を示すフローチャートである。
【図３７】送出確率更新後の経路状態情報記憶部の例を示す図である。
【図３８】負荷分散の一例を示す図である。
【図３９】送出確率更新処理の手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下、本実施の形態について図面を参照して説明する。
〔第１の実施の形態〕
図１は、第１の実施の形態の機能を示すブロック図である。図１の例では、複数のルータ１〜６を含むネットワークが示されている。各ルータ１〜６には識別子（ＩＤ）が付与されている。ルータ１のＩＤは「Ｅ」、ルータ２のＩＤは「Ａ」、ルータ３のＩＤは「Ｂ」、ルータ４のＩＤは「Ｃ」、ルータ５のＩＤは「Ｆ」、ルータ６のＩＤは「Ｄ」である。各ルータ１〜６は、一定期間トラフィックの流入が途絶えると、省電力モードに移行することができる。省電力モードでは、例えば、トラフィックの転送に関する機能を停止することで、消費電力が抑えられる。ここで、省電力モードで動作しているルータを、スリープノードと呼ぶ。図１の例では、ルータ５がスリープノードである。
【００１９】
図１に示すような構成のネットワークでは、輻輳の予兆が検出されていない状況下では、トラフィックを特定の経路に集約して転送することができる。図１の例ではルータ２，３，４に対して、外部のネットワークからトラフィックが流入している。流入したトラフィックは、ルータ６から他のネットワークへ送出される。このようなとき、ルータ１は、トラフィックを転送する中継ノードとして機能する。また、ルータ２，３，４は、トラフィックの入力を受け付ける入口ノードとして機能する。ルータ６は、トラフィックを出力する出口ノードとして機能する。またルータ４，５は、中継ノードとして機能することができるものとする。
【００２０】
各ルータ２，３，４に流入したトラフィックは、それぞれ１つの経路に集約されている。すなわち、ルータ２，３に流入したトラフィックは、すべてルータ１を介してルータ６に転送されている。ルータ４に流入したトラフィックは、すべてルータ６に直接転送されている。このようなトラフィックの集約を行うことで、省電力モードに移行できるルータの数を増やし、ネットワーク全体での省電力化が図れる。
【００２１】
ただし、トラフィックを集約させた経路で輻輳の予兆が検出された際に、その経路を通るすべてのトラフィックを複数の経路に分散させると、必要以上にスリープノードが通常モードに移行する可能性がある。そこで、第１の実施の形態では、適切なトラフィックの分散制御を行うことで、トラフィックを分散させることによる消費電力の増加の抑制を図っている。そのような分散制御を行うために、各ルータが有する機能を以下に説明する。
【００２２】
ここでルータ１は、中継ノードとして機能するため、中継手段１ａ、輻輳予兆検出手段１ｂ、経路記憶手段１ｃ、状態情報取得手段１ｄ、分散先決定手段１ｅ、および分散要求手段１ｆを有する。
【００２３】
中継手段１ａは、入力されたトラフィックを、転送順が定義された経路に沿って転送する。図１の例では、中継手段１ａは、ルータ２，３から入力されたトラフィックを、ルータ６に転送している。
【００２４】
輻輳予兆検出手段１ｂは、他のルータとの間に張られた各リンクのトラフィック量を測定し、輻輳発生の予兆を検出する。例えば輻輳予兆検出手段１ｂは、トラフィック量が所定の閾値を超えたリンクを、輻輳発生の予兆があるリンクとして検出する。
【００２５】
経路記憶手段１ｃは、ルータ１と他のルータ２，３，６との間に設けられた各リンクを介して転送されるトラフィックのネットワーク内での経路を記憶する。例えばルータ１とルータ６との間のリンクを介して転送されるトラフィックの経路として、「ルータ２、ルータ１、ルータ６」の順で転送する経路と、「ルータ３、ルータ２、ルータ６」の順で転送する経路とが、経路記憶手段１ｃに記憶されている。
【００２６】
状態情報取得手段１ｄは、特定のリンクを経由して転送されるトラフィックの少なくとも一部を特定のリンクを経由しない経路で転送させる場合に、経路の状態情報を管理している管理装置から状態情報を取得する。例えば、状態情報取得手段１ｄは、輻輳予兆検出手段１ｂが輻輳発生の予兆を検出したリンクを、特定のリンクとして状態情報を取得する。
【００２７】
状態情報取得手段１ｄは、状態情報を取得する際には、経路記憶手段１ｃを参照する。
そして状態情報取得手段１ｄは、特定のリンクを介して転送されるトラフィックの経路を対象経路とする。対象経路は、１または複数である。例えば、ルータ１とルータ６との間のリンクが特定のリンクとされた場合、対象経路は「ルータ２、ルータ１、ルータ６」の順で転送する経路と、「ルータ３、ルータ１、ルータ６」の順で転送する経路との２つのである。
【００２８】
さらに状態情報取得手段１ｄは、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ特定のリンクを経由しない経路を分散経路候補とする。そして状態情報取得手段１ｄは、分散経路候補のトラフィックを中継するルータの状態を示す状態情報を管理している管理装置から、各分散経路候補の状態情報を取得する。
【００２９】
例えば、状態情報取得手段１ｄにネットワーク内のすべての経路の情報が登録されていれば、状態情報取得手段１ｄにおいて分散経路候補を特定でききる。またネットワーク内のすべての経路を管理している管理装置があれば、状態情報取得手段１ｄは、その管理装置から経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ特定のリンクを経由しない経路である分散経路候補を取得することができる。ネットワーク内の経路が複数の管理装置に分散して管理されている場合、状態情報取得手段１ｄは、それぞれの管理装置から分散経路候補を取得する。例えば各経路の最初のルータにおいて、経路が管理されている場合、状態情報取得手段１ｄは、対象経路の最初のルータが管理装置であると判断し、そのルータから分散経路候補を取得する。
【００３０】
図１の例では、対象経路の最初のルータであるルータ２，３から分散経路候補と、分散経路候補のトラフィックを中継するルータの状態を示す状態情報とを取得している。
ルータ２，３から分散経路候補と状態情報を取得する場合、例えば状態情報取得手段１ｄは、対象経路それぞれの最初のルータ２，３に対して、対象経路の最初と最後のルータが示されたアラーム情報を送信する。すると、対象経路の最初のルータ２，３から、経路上の最初と最後のルータが対象経路と共通の分散経路候補、および分散経路候補の状態情報が応答される。
【００３１】
状態情報取得手段１ｄは、例えば状態情報として、分散経路候補の経路上のルータのうち省電力モードの状態のルータ数（スリープノード数）を取得する。また状態情報取得手段１ｄは、状態情報として、分散経路候補の経路上のトラフィックが単位データ量だけ増加したときの経路上の各ルータの消費電力増加量を管理装置から取得してもよい。
【００３２】
分散先決定手段１ｅは、状態情報取得手段１ｄが取得した各分散経路候補の状態情報に基づいて、分散経路候補へ特定のリンクのトラフィックの一部を流した場合の経路上の他のルータの状態の変化を比較する。そして分散先決定手段１ｅは、状態の変化による消費電力の増加量が少ない経路を優先的に分散先経路として決定する。例えば、分散先決定手段１ｅは、経路上のルータのうち省電力モードの状態のルータ数（スリープノード数）が少ない分散経路候補を、優先的に分散先経路に決定する。すなわち、経路上のスリープノード数が多いほど、その経路にトラフィックを振り分けたときに、省電力モードから通常モードに移行するルータ数が多くなる。省電力モードから通常モードに移行するルータが少ないほど、消費電力を抑制できる。そのため、スリープノード数が少ない分散経路候補が優先的に分散先経路に決定される。また分散先決定手段１ｅは、トラフィックが所定量だけ増加したときの経路上の各ルータの消費電力増加量が少ない分散経路候補を、優先的に分散先経路に決定することもできる。
【００３３】
分散要求手段１ｆは、分散先決定手段１ｅで決定した分散先経路へ、その分散先経路と経路上の最初と最後のルータの両方が共通な対象経路のトラフィックの少なくとも一部を振り分けるように、対象経路上の最初のルータに指示する分散要求を送信する。分散要求手段１ｆは、輻輳予兆検出手段１ｂにより輻輳発生の予兆が検出されたリンクの輻輳発生の予兆が継続している間、所定間隔で分散要求を繰り返し送信してもよい。
【００３４】
ルータ２は、入口ノードとして機能するため、経路状態記憶手段２ａ、中継手段２ｂ、状態情報収集手段２ｃ、状態情報通知手段２ｄ、および送出確率変更手段２ｅを有している。
【００３５】
経路状態記憶手段２ａは、ネットワーク内でトラフィックを中継する各ルータの状態情報を、そのルータが中継するトラフィックの経路と対応付けて記憶する。また、経路状態記憶手段２ａは、経路上の最初と最後のルータが共通の経路間での各経路へのトラフィックの送出確率を記憶する。
【００３６】
中継手段２ｂは、他のネットワークから流入するトラフィックを転送する。その際、中継手段２ｂは、経路状態記憶手段２ａに示される送出確率で、ルータ１〜６が属するネットワーク内の経路に分散して転送する。
【００３７】
状態情報収集手段２ｃは、ネットワーク内でトラフィックを中継する各ルータから、そのルータの状態を示す状態情報を収集し、該ルータの状態情報を、該ルータが中継するトラフィックの経路と対応付けて経路状態記憶手段２ａに格納する。例えば、状態情報収集手段２ｃは、ルータ２に他のネットワークから流入するトラフィックを転送する経路上の他のルータから状態情報を収集する。また状態情報収集手段２ｃは、例えばトラフィックを転送する経路上のルータのうちの省電力モードとなっているルータの数を状態情報として収集する。また状態情報収集手段２ｃは、トラフィックを転送する経路上のルータにおける、トラフィックが単位データ量増加したときの消費電力増加量を状態情報として収集してもよい。
【００３８】
状態情報通知手段２ｄは、アラーム情報に応答して状態情報を送信する。例えば状態情報通知手段２ｄは、特定のリンクを経由してトラフィックを転送する対象経路の最初と最後のルータが示されたアラーム情報を受信する。すると状態情報通知手段２ｄは、経路状態記憶手段２ａを参照し、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ特定のリンクを経由しない経路を分散経路候補とする。そして状態情報通知手段２ｄは、分散経路候補の状態情報をアラーム情報の発信元に送信する。
【００３９】
送出確率変更手段２ｅは、対象経路のトラフィックの少なくとも一部を振り分ける分散先経路を指定する分散指示を受け取ると、経路状態記憶手段２ａの対象経路と分散先経路との送出確率を更新する。例えば送出確率変更手段２ｅは、対象経路へのトラフィックの送出確率を減らし、分散先経路へのトラフィックの送出確率を増やす更新処理を行う。
【００４０】
なお、図１には、代表的にルータ１，２の機能を示したが、中継ノードとしての機能を有する他のルータ４，５は、ルータ１と同様の機能を有している。また入口ノードとして機能する他のルータ３，４は、ルータ２と同様の機能を有している。
【００４１】
各ルータ１〜６がこのような機能を有することで、適切なトラフィックの分散制御が可能となる。例えば、図１のルータ１からルータ６へトラフィックを転送するリンクにおいて、輻輳の予兆が検出されたものとする。
【００４２】
図２は、輻輳の予兆検出時の処理を示す図である。ルータ１からルータ６へトラフィックを転送するリンクにおける輻輳の予兆は、例えばルータ１の輻輳予兆検出手段１ｂで検出される。ルータ１からルータ６へのリンクを経由するトラフィックの経路は、「ルータ２、ルータ１、ルータ６」の順で転送する経路と、「ルータ３、ルータ１、ルータ６」の順で転送する経路とがある。そこで、これらの経路が対象経路とされ、状態情報取得手段１ｄによって、例えば対象経路の最初のルータ２，３に対してアラーム情報が送信される。アラーム情報には、例えば対象経路の最初と最後のルータとが示される。図２では、例えば「ＡＤ」という情報によって、経路の最初がＩＤ「Ａ」のルータ２であり、経路の最後がＩＤ「Ｄ」のルータ６であることが示されている。
【００４３】
図３は、アラーム情報を受信したルータの処理を示す図である。アラーム情報を受け取ったルータ２，３は、例えば分散経路候補と、その分散経路候補の状態情報とを、ルータ１に通知する。ルータ２であれば、状態情報通知手段２ｄによって状態情報が通知される。図３の例では、状態情報として、分散経路候補上のスリープノード数が通知されている。
【００４４】
分散経路候補とその状態情報に基づいて、ルータ１の分散先決定手段１ｅにより分散先経路が決定される。図３の例は、ルータ３から通知された分散経路候補（「経路「ＢＦＤ」）はスリープノードを含んでいるが、ルータ２から通知された分散経路候補（「経路「ＡＣＤ」）にはスリープノードが含まれない。すると、経路「ＡＣＤ」にトラフィックを分散させた方が消費電力の増加を抑制できることが分かる。そこで、経路「ＡＣＤ」が、分散先経路として決定される。すると、分散要求手段１ｆにより、ルータ２に対して分散要求が送信される。
【００４５】
図４は、分散要求の送信処理を示す図である。分散要求には、トラフィックの分散先となる分散先経路が指定されている。ルータ２の送出確率変更手段２ｅは、分散要求に従ってルータ２からルータ６へ転送するトラフィックの各経路への、トラフィックの送出確率を更新する。例えば、送出確率変更手段２ｅは、経路「ＡＥＤ」への送出確率を下げ、経路「ＡＣＤ」への送出確率を上げる。図４の例では、経路「ＡＣＤ」への送出確率が「０」から０より大きな値に変更される。変更された送出確率は、経路状態記憶手段２ａに設定される。送出確率が更新されると、中継手段２ｂは更新後の送出確率に従ってトラフィックを振り分ける。
【００４６】
図５は、送出確率変更後のトラフィックの振り分けを示す図である。図５に示すように、経路「ＡＣＤ」へのトラフィックの送出確率を「０」よりも大きな値に変更されたことで、その経路にもトラフィックが振り分けられている。経路「ＡＣＤ」へ振り分けたトラフィックの分だけ、ルータ１とルータ６との間のリンクのトラフィック量は減少し、輻輳の発生が抑制される。
【００４７】
このように、第１の実施の形態では、輻輳の可能性のあるリンクを経由するすべてのトラフィックの入口ノードに対しトラフィックの分散要求を送信するのではなく、分散経路候補の中から決定された分散先経路の入口ノードにのみ分散要求を送信する。この際、分散先候補を評価し、できるだけスリープノードを含む経路へはトラフィックの振り分けを行わないように、分散先経路が決定される。
【００４８】
これにより、輻輳発生の予兆が検出された際においても、限られた入口ノードだけ、トラフィックを特定の経路に集約させる集約モードから、トラフィックを複数の経路に分散させる分散モードに移行する。そのため、必要以上のスリープノードの起動が抑制される。その結果、消費電力の不必要な増加を抑えることが可能になる。
【００４９】
なお第１の実施の形態では、入口ノードとして機能するルータが、状態情報収集手段２ｃと状態情報通知手段２ｄとを有しているが、これらの機能は入口ノードとして機能するルータ以外の管理装置が有していてもよい。例えば、ネットワーク全体を管理する管理装置が、ネットワーク全体のトラフィックの経路と、その経路上のルータの状態を管理している場合も考えられる。その場合、管理装置が状態情報収集手段２ｃと状態情報通知手段２ｄの機能、および経路状態記憶手段２ａにおける状態情報の記憶機能を有する。管理装置がネットワーク内のすべての経路と各経路の状態情報とを管理している場合、ルータ１は、管理装置から分散経路候補と、分散先経路候補の状態情報とを、一括して取得することができる。
【００５０】
〔第２の実施の形態〕
第２の実施の形態は、第１の実施の形態で示した機能に、実際に運用するシステムに適用させるために有用な機能を追加したものである。例えば、第２の実施の形態では、入口ノードが定期的に、自己に設定されているパス（経路）の状態情報を収集する。経路状態情報には、経路上のスリープノード数が含められる。このようにして、各入口ノードが動的に変化するネットワーク上の状況を自律的に把握することができる。すなわち、ネットワーク全体を制御するサーバを設けることなく、スリープノード数の把握が可能となる。
【００５１】
また、第２の実施の形態では、新たにトラフィックを送出する経路に対して、少しずつトラフィック量を増加させるように、分散モードに移行した入口ノードを制御する。これにより、トラフィックの転送先を変更したことに起因して、輻輳を検出したリンクとは別のリンクで輻輳を発生させてしまうことを抑制できる。
【００５２】
図６は、第２の実施の形態のシステム構成例を示す図である。ネットワーク１０には、複数のノード（ルータ）が含まれている。ネットワーク１０に含まれるノードは、中継ノード１００，１００ａ，１００ｂとエッジノード２００，２００ａ，２００ｂ，２００ｃとに分かれる。中継ノード１００，１００ａ，１００ｂは、ネットワーク１０内のトラフィックを転送するものである。エッジノード２００，２００ａ，２００ｂ，２００ｃは、ネットワーク１０内でのトラフィックの転送に加え、他のネットワークから入力されるトラフィックや他のネットワークへ出力するトラフィックの転送を行うものである。
【００５３】
各ノードには、ネットワーク１０上で識別するためのＩＤが付与されている。エッジノード２００のＩＤは「Ａ」である。エッジノード２００ａのＩＤは「Ｂ」である。エッジノード２００ｂのＩＤは「Ｃ」である。エッジノード２００ｃのＩＤは「Ｄ」である。中継ノード１００のＩＤは「Ｅ」である。中継ノード１００ａのＩＤは「Ｆ」である。中継ノード１００ｂのＩＤは「Ｇ」である。
【００５４】
中継ノード１００は、エッジノード２００，２００ａ，２００ｂ，２００ｃと中継ノード１００ａとに接続されている。中継ノード１００ａは、エッジノード２００ａ，２００ｃと中継ノード１００とに接続されている。中継ノード１００ｂは、エッジノード２００とエッジノード２００ｃとに接続されている。
【００５５】
エッジノード２００は、エッジノード２００ｂと中継ノード１００，１００ｂとに接続されていると共に、他のネットワーク２１にも接続されている。エッジノード２００ａは、エッジノード２００ｂと中継ノード１００，１００ａとに接続されていると共に、他のネットワーク２２にも接続されている。エッジノード２００ｂは、エッジノード２００，２００ａ，２００ｃと中継ノード１００とに接続されていると共に、他のネットワーク２３にも接続されている。エッジノード２００ｃは、エッジノード２００ｂと中継ノード１００，１００ａ，１００ｂとに接続されていると共に、他のネットワーク２４にも接続されている。
【００５６】
以下、２台のノード間を接続する伝送経路を「リンク」と呼ぶ。
ネットワーク１０内では、中継ノード１００，１００ａ，１００ｂとエッジノード２００，２００ａ，２００ｂ，２００ｃとが、例えば個々のパケット単位で、伝送経路を選択する。なお、エッジノードとして機能しているルータは、ネットワーク１０内でのパケットの中継をするため、中継ノードとしての機能も兼ね備える。
【００５７】
また各ノードは、トラフィックの流入が一定時間途絶えると、スリープモードに移行する。スリープモードでは、ノードの多くの機能が停止し、消費電力が低く抑えられる。ただしスリープモードであっても、制御パケットの転送に必要な機能は動作し続ける。なお、スリープモードは、省電力モードの一例である。例えばノードへのトラフィックの流入が一定時間途絶えた場合、省電力モードとして、該当ノードを、動作周波数を低下させる低電力モードに移行させることも可能である。
【００５８】
図７は、本実施の形態に用いる中継ノードのハードウェアの一構成例を示す図である。中継ノード１００は、ＣＰＵ（Central Processing Unit）１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ（Random Access Memory）１０２と複数の周辺機器が接続されている。
【００５９】
ＲＡＭ１０２は、中継ノード１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。
【００６０】
バス１０８に接続されている周辺機器としては、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７ａ，１０７ｂ，１０７ｃ，１０７ｄ，１０７ｅがある。
【００６１】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、中継ノード１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００６２】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００６３】
入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００６４】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００６５】
通信インタフェース１０７ａは、エッジノード２００に接続されている。通信インタフェース１０７ａは、エッジノード２００との間でデータの送受信を行う。通信インタフェース１０７ｂは、エッジノード２００ａに接続されている。通信インタフェース１０７ｂは、エッジノード２００ａとの間でデータの送受信を行う。通信インタフェース１０７ｃは、エッジノード２００ｂに接続されている。通信インタフェース１０７ｃは、エッジノード２００ｂとの間でデータの送受信を行う。通信インタフェース１０７ｄは、エッジノード２００ｃに接続されている。通信インタフェース１０７ｄは、エッジノード２００ｃとの間でデータの送受信を行う。通信インタフェース１０７ｅは、中継ノード１００ａに接続されている。通信インタフェース１０７ｅは、中継ノード１００ａとの間でデータの送受信を行う。
【００６６】
なお、図７に示した中継ノード１００の構成のうち、グラフィック処理装置１０４、光学ドライブ装置１０６、モニタ１１、キーボード１２、およびマウス１３は、なくてもよい。例えば、シリアルインタフェースや制御用の通信インタフェースを通じて端末装置から中継ノード１００へアクセスし、中継ノード１００への各種設定を端末装置から遠隔で行うことも可能である。
【００６７】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。図７には中継ノード１００のハードウェア構成例を示したが、他の中継ノード１００ａ，１００ｂおよびエッジノード２００，２００ａ，２００ｂ，２００ｃも同様のハードウェア構成で実現することができる。
【００６８】
なお、以下の説明では、ネットワークの特定のエッジノードに入力されたトラフィック（データ）が特定のエッジノードから出力されるトラフィックの流れを「フロー」と呼ぶ。フローは、トラフィックが入力されるエッジノードと、トラフィックが出力されるエッジノードとの組み合わせごとに存在する。また、各フローにおけるトラフィックを転送するための経路は、１または複数である。すなわち、１つのフローに流入するトラフィックを１つの経路で転送してもよいし、複数の経路に分散させて転送してもよい。トラフィックが入力されるエッジノードが入口ノードであり、トラフィックを出力するエッジノードが出口ノードである。
【００６９】
第２の実施の形態では、フローの転送に使用可能な経路が、そのフローの入口となるエッジノード（入口ノード）に予め設定されているものとする。そして、入口ノードにフローのトラフィックが流入すると、フローに対応付けてエッジノードに予め設定された経路にトラフィックを振り分ける。ある入口ノードからある出口ノードへのトラフィックは、入口ノードで決定された経路に沿って転送される。
【００７０】
中継ノードでは、各フローのトラフィック（入口ノードと出口ノードの組みが指定されたトラフィック）はフローごとに設定されている経路にしたがって次のノードに送られる。例えば、各トラフィックのパケットには、転送の経路を示す情報が含まれる。中継ノードは、パケットで示される経路に従ってそのパケットを転送する。その結果、エッジノードで決定した経路でトラフィックが転送される。このように入口ノードで経路を決定してトラフィックをする制御方式を、経路指定型と呼ぶ。経路指定型のトラフィック制御では、中継ノードは指定された経路でトラフィックを転送し、指定された経路以外の経路への振り分けは行わない。
【００７１】
このような経路指定型のトラフィック制御を行う場合、エッジノードは、例えば、予め設定された複数の経路それぞれのトラフィック誘引力を用いて、トラフィックの振り分けを行う。トラフィック誘引力は、トラフィックを特定の経路に集約する場合に用いられる。トラフィック誘引力は、その経路を介して転送されるトラフィック量が多い程、大きな値となる。例えば、出口ノードから経路に沿って、中継ノードがトラフィック誘引力を計算していく。各中継ノードでは、経路上を出口ノード側に隣接するノードへのリンクのトラフィック量が大きい程、そのリンクのトラフィック誘引力を大きくする。また、各中継ノードでは、経路上を出口ノード側に隣接するノードから渡されたトラフィック誘引力が大きい程、そのリンクに関するトラフィック誘引力を大きくする。このようにして、経路上の各中継ノードがトラフィック誘引力を計算する。そして、最後に、入口ノードにおいても、経路上を出口ノード側に隣接するノードへのリンクのトラフィック誘引力を、そのリンクのトラフィック量と、隣接するノードから渡されたトラフィック誘引力を用いて計算する。その計算結果が、経路のトラフィック誘引力となる。入口ノードでは、フローに対応付けて予め設定された経路ごとのトラフィック誘引力を定期的に計算し、計算結果をＲＡＭなどの記憶装置に格納する。
【００７２】
入口ノードは、出口ノードが指定されたトラフィックについて、その出口ノード宛の経路のトラフィック誘引力に従った確率で、各経路にトラフィックを振り分ける。
以下、図６に示すシステム構成を用いて、経路指定型のトラフィック制御例を示す。例えば、エッジノード２００には、エッジノード２００ｃへのトラフィックが流入しているものとする。このトラフィックの流れをフロー「ＡＤ」とする。エッジノード２００ａには、エッジノード２００ｃへのトラフィックが流入しているものとする。このトラフィックの流れをフロー「ＢＤ」とする。エッジノード２００ｂには、エッジノード２００ｃへのトラフィックが流入しているものとする。このトラフィックの流れをフロー「ＣＤ」とする。
【００７３】
エッジノード２００からエッジノード２００ｃへは、エッジノード２００ｂを経由する経路（経路「ＡＣＤ」）、中継ノード１００を経由する経路（経路「ＡＥＤ」）、および中継ノード１００ｂを経由する経路（経路「ＡＧＤ」）が設定されているものとする。入口であるエッジノード２００において、各経路のトラフィック誘引力に対応した確率で、各々の経路に流入トラフィックは分配される。
【００７４】
エッジノード２００ａからエッジノード２００ｃへは、中継ノード１００を経由する経路（経路「ＢＥＤ」）、中継ノード１００ａを経由する経路（経路「ＢＦＤ」）が設定されているものとする。エッジノード２００ａにおいても、各経路のトラフィック誘引力に対応した確率で、各々の経路に流入トラフィックは分配される。
【００７５】
また、エッジノード２００ｂからエッジノード２００ｃへは、他のノードを経由しない１つの経路（経路「ＣＤ」）が設定されているものとする。そのため、エッジノード２００ｂへの流入トラフィックはすべて経路「ＣＤ」を通る。
【００７６】
中継ノード１００からエッジノード２００ｃへのリンク（リンク「ＥＤ」）には、フロー「ＡＤ」とフロー「ＢＤ」とのトラフィックが流れる。そのため、中継ノード１００のトラフィック誘引力が高くなる。それが、それぞれ中継ノード１００からエッジノード２００，２００ａに通知される。その結果、例えば経路「ＡＥＤ」のトラフィック誘引力が経路「ＡＣＤ」よりも高くなることによりエッジノード２００からエッジノード２００ｃへ流れるトラフィックはすべて経路「ＡＥＤ」に流れるように入口ノードであるエッジノード２００でのフロー「ＡＤ」の分配確率は計算される。同様にフロー「ＢＤ」のトラフィックも経路「ＢＥＤ」に集約される。
【００７７】
図８は、トラフィックの集約例を示す図である。トラフィックが集約されたことで、中継ノード１００ａや中継ノード１００ｂを通過するトラフィックがなくなる。その結果、中継ノード１００ａや中継ノード１００ｂをスリープモードに移行させることが可能となる。中継ノード１００ａや中継ノード１００ｂがスリープモードに移行することで、ネットワーク全体での低消費電力が実現される。このような低消費電力化を実現する技術として、本出願人は特願２００９−４９１３９号を出願している。また、同様の低消費電力化の技術は以下の論文で公表されている。
【００７８】
“山田亜紀子、外３名、「グリーンネットワークに向けた一検討（３）ＥＣＯルーティング」、電子情報通信学会総合大会講演論文集、社団法人電子情報通信学会、２００９年３月４日、2009年＿通信（２）、pp.252”
図８の例では、各フローのトラフィックがそれぞれ１つの経路に集約されている。すなわち経路「ＡＣＤ」のトラフィック計測値は「０．０」である。経路「ＡＥＤ」のトラフィック計測値は「０．３」である。経路「ＢＥＤ」のトラフィック計測値は「０．４」である。経路「ＢＦＤ」のトラフィック計測値は「０．０」である。経路「ＣＤ」のトラフィック計測値は「０．１」である。なお、各リンクのリンク容量は「１．０」である。
【００７９】
このようにトラフィックの集約が実現された状態において、中継ノード１００からエッジノード２００ｃへのリンク（リンク「ＥＤ」）には、フロー「ＡＤ」とフロー「ＢＤ」との両方のトラフィックの全てが流れる。この状態で、エッジノード２００あるいはエッジノード２００ａへの流入トラフィックが増大した場合を考える。この場合、各リンクでは流れるトラフィック量を計測しておき、リンク最大容量に対する輻輳検出判定閾値を超えないかどうか、常時チェックしておく。フロー「ＡＤ」とフロー「ＢＤ」のトラフィック量の和がリンク「ＥＤ」のリンク容量に近づくと、輻輳発生の可能性が生じる。ここで、輻輳発生の可能性が生じたリンクを制御対象リンクとする。輻輳の発生を抑制するには制御対象リンクを流れるトラフィックの一部を他の経路へ分散させる輻輳制御が行われる。
【００８０】
輻輳制御では、例えば輻輳発生の可能性を検出したノードから、制御対象リンクへトラフィックを流している経路の入口ノードに対し、アラーム情報が送信される。そして、アラーム情報を受信した入口ノードが、トラフィックを集約させる制御を停止し、トラフィックの分散制御を行う。
【００８１】
ここで、制御対象リンクへトラフィックを流している経路のすべての入口ノードが、アラーム情報の受信に応じてトラフィックを分散させてしまうと、必要以上の消費電力の増加を招いてしまう。
【００８２】
例えば図８の例であれば、リンク「ＥＤ」を流れるフロー「ＡＤ」およびフロー「ＢＤ」のトラフィック量増加によりリンク「ＥＤ」の輻輳発生の可能性が検出された場合を想定する。この場合に、アラーム情報がリンク「ＢＤ」を通過する全フローの経路の入口ノードに対し送出されると、スリープノードであった中継ノード１００ａ，１００ｂが通常モードに移行してしまう。
【００８３】
つまり通過するフロー「ＡＤ」の経路「ＡＥＤ」、フロー「ＢＤ」の経路「ＢＥＤ」に沿ってそれぞれ入口のエッジノード２００、エッジノード２００ａに対してアラーム情報が送出される。すると、アラーム情報を受け取ったエッジノード２００では、フロー「ＡＤ」の経路（経路「ＡＥＤ」、経路「ＡＣＥ」、経路「ＡＧＤ」の３つがある）を集約モードから分散モードに切り替える。すなわちエッジノード２００は、アラーム情報がきた経路「ＡＥＤ」へのトラフィック送出確率を減らし、別の経路「ＡＣＤ」、「ＡＧＤ」への送出確率を上げる。このように、エッジノード２００は、経路「ＡＣＤ」、「ＡＧＤ」へ一部のトラフィックを分配することにより負荷分散を図り、リンク「ＥＤ」を通過する経路「ＡＥＤ」のトラフィックを下げる。この結果、中継ノード１００ｂを通過するトラフィックが発生し、中継ノード１００ｂはスリープモードから起動し、通常モードでの動作を開始する。
【００８４】
同様に、エッジノード２００ａにおいてもフロー「ＢＤ」の経路「ＢＥＤ」への送出確率を下げ、経路「ＢＦＤ」への送出確率を上げる。この結果、中継ノード１００ａを通過するトラフィックが発生し、中継ノード１００ａはスリープモードから起動し、通常モードでの動作を開始する。
【００８５】
このようにすべてのスリープノードが通常モードに移行してしまうと、ネットワーク全体としての消費電力が増加する。ところが、輻輳発生の抑制には、該当リンクを経由するフローの一部だけを、別経路に負荷分散すれば十分な場合もある。例えば、図８に示すリンク「ＥＤ」で輻輳発生の可能性が検出された場合において、エッジノード２００のみが負荷分散を行えば、輻輳の発生を抑制可能な場合も考えられる。例えば、エッジノード２００においてフロー「ＡＤ」のトラフィックの多くを経路「ＡＣＤ」へ振り向けることができれば、フロー「ＢＤ」のトラフィックは経路「ＢＥＤ」に集約したままでも、リンク「ＥＤ」の輻輳は回避可能な場合があり得る。この場合、スリープノードである中継ノード１００ａは、スリープモードのままでよく、低消費電力化が図られる。なお、エッジノード２００ｂは、フロー「ＣＤ」があることにより既に起動しており、経路「ＡＣＤ」へトラフィックを流入させても、スリープノードを通常モードに移行させる場合に比べ、消費電力の増加は少なくてすむ。
【００８６】
しかも、エッジノード２００においてアラーム情報を受信した際に、既知の経路すべてのトラフィックを分散させるのではなく、一部の経路のみを分散先とすれば、さらに省電力化を図ることができる。例えば、図８の例では、エッジノード２００がフロー「ＡＤ」のトラフィックを分散させる際に、既知のすべての経路である経路「ＡＥＤ」、経路「ＡＣＤ」、経路「ＡＧＤ」それぞれにトラフィックを分散させてしまうと、中継ノード１００ｂが通常モードに移行する。その結果、消費電力が増加する。そこで、エッジノード２００がアラーム情報を受信した場合であっても、分散先の経路を経路「ＡＣＤ」のみに限定すれば、中継ノード１００ｂをスリープモードのまま維持できる。
【００８７】
そこで、第２の実施の形態では、輻輳発生の可能性が検出された場合であっても、できるだけスリープノードを起動させずにすむように輻輳制御を行う。以下、このような輻輳制御を実現するための機能および処理内容について、詳細に説明する。なお、第２の実施の形態では、以下のように情報を定義する。
【００８８】
〔リンク容量〕リンク容量は、リンクを通すことのできるトラフィックの最大量である。
〔リンク利用率〕リンク利用率は、リンクを流れるトラフィック量をリンク容量で除算した値である。
【００８９】
〔リンク目標容量〕リンク目標容量は、輻輳を起こさないように（最大リンク容量から余裕をもって）、リンクのトラフィック量がこの値を超えない様に制御する目標値である。
【００９０】
〔Target値〕Target値は、リンク目標容量をリンク容量で除算した値である。リンク利用率がTarget値を超えないように、各ルータの連係動作によってトラフィックの分散制御が実行される。
【００９１】
〔Control値〕リンク利用率がTarget値を超えないように保つためには、トラフィック増加に伴って上昇するリンク利用率がTarget値に近づいた手前の時点で輻輳抑止の制御を開始する必要がある。Control値は、輻輳制御を開始する閾値を決めるための数値である。
【００９２】
〔制御開始閾値〕制御開始閾値は、輻輳制御を開始する基準となるリンク利用率の閾値である。例えば、Control値とTarget値を用いて、以下の式により輻輳制御を開始する閾値が決められる。
制御開始閾値＝Target値−Control値    ・・・（１）
〔偏差〕偏差は、Target値とリンク利用率との差である。偏差は、以下の式で算出される。
偏差＝Target値−リンク利用率    ・・・（２）
これらの情報を用いて、輻輳制御が行われる。輻輳制御では、輻輳の予兆の検出や、輻輳抑制のためのアラーム情報の通知の継続判断などが行われる。そのために、各フローの入口ノードにおいて、所定周期ごとに、そのノードを入口ノードとするフローのトラフィック量が計測される。また、各ノードでは、計測されたトラフィック量に基づいて、各ノードにおいて各リンクのリンク利用率が計算される。そして、「リンク利用率＞制御開始閾値（＝Target値−Control値）」という条件が満たされるとき、条件を満たしたリンクにおいて輻輳発生の予兆があると判断される。このとき、条件を満たしたリンクが、制御対象リンクとされる。
【００９３】
輻輳発生の予兆が検出されると、検出したノードにおいて、制御対象リンクに関する輻輳制御が開始される。輻輳発生の予兆を検出したノードは、アラーム情報を作成して制御パケットとして、制御対象リンクを通る各トラフィックの入口ノード宛へ経路を逆に辿るように送り出す。アラーム情報は、制御対象リンクを通るトラフィックの入口ノードにおいて、そのトラフィックの分散経路候補の募集通知とみなされる。ここで、リンク利用率が輻輳制御の制御開始閾値を下回らない限り、定期的にアラーム情報が送信される。
【００９４】
図９は、リンク利用率とアラーム情報送信との関係を示す図である。図９では、横軸に時間、縦軸にリンク利用率を示している。図９の例では、徐々にリンク利用率が上昇し、輻輳制御が開始されている。輻輳制御が開始されたことでアラーム情報が送信される。輻輳制御が開始されると、徐々にリンク利用率の上昇傾向が緩やかになり、しばらく経つとリンク利用率が低下する。リンク利用率が制御開始閾値以下になると、輻輳制御が終了する。すなわち、定期的なアラーム情報の送信が終了する。
【００９５】
ここでTarget値は、輻輳を発生させないためにリンク利用率の目標値として定めた値である。本実施の形態では輻輳制御において、徐々に分散するトラフィック量を増やすため、輻輳制御の開始と同時にリンク利用率が急減するわけではない。そのため、Target値よりもControl値分低い値を制御開始閾値とし、リンク利用率が制御開始閾値を超えた時点で輻輳制御を開始する。これにより、リンク利用率が上昇傾向にあっても、リンク利用率をTarget値付近で抑えることができる。
【００９６】
ここで、Target値とリンク利用率との差が偏差である。偏差は、アラーム値（規制率）の算出に使用される。例えば、偏差の増加度合いが大きい程、アラーム値が大きくなる。アラーム値は、アラーム情報に含められ、入口ノードでの分散の度合いを決定するのに利用される。例えばアラーム値は、対象経路への現在のトラフィックの送出確率に対する振り分け後の送出確率の比率である。
【００９７】
各フローの入口ノードは、アラーム情報に対して分散経路の候補を応答するために、予め経路状態情報収集処理を行う。経路状態情報収集処理は、特定のフローの入口ノードが、そのフローの各経路上のリンクやルータの状態を収集する処理である。入口ノードは、経路状態情報収集処理を実行することで、各出口ノード宛フローの（複数の）経路とその状態を管理できる。例えば入口ノードは、定期的に、状態収集パケットを各経路に沿って送出する。状態収集パケットは、経路上のルータで転送されるごとに、スリープノード数、経路空き容量、消費電力パラメータなどの情報が更新される。そして、状態収集パケットは、出口ノードに到達すると、出口ノードから入口ノードに送り返される。これにより、入口ノードにおいて、各経路のスリープノード数、経路空き容量、消費電力パラメータ集計が可能となる。状態収集パケットを用いて収集される情報の内容は以下の通りである。
【００９８】
〔経路空き容量〕経路空き容量は、その経路にあとどれぐらいのトラフィックを転送することができるかを示す値である。経路の空き容量は、経路上の各リンクの空き容量に基づいて決定される。リンクの空き容量は以下の式で計算される。
リンクの空き容量＝リンク容量×Target値−リンクトラフィック量    ・・・（３）
なお、上記式によるリンクの空き容量の値が負になる時は、リンクの空き容量＝０とされる。また、経路上の各リンクの空き容量のうちの最小値が、経路空き容量となる。なお、リンクを複数のフローの経路が共有する可能性がある。その場合、リンクの空き容量は複数のフローの経路の空き容量として重複して使われる。そのため、この計算による経路の空き容量は、あくまで状態収集時点での目安量であって、必ずその量が保証されている（つまりその分だけその経路にトラフィックを増やしても輻輳が発生しない）という訳ではない。
【００９９】
〔経路の消費電力パラメータ〕経路の消費電力パラメータは、単位トラフィック量の増加に対する経路上の全ノードでの消費電力増加量を示す値である。経路の消費電力パラメータは、経路上の各ノードの消費電力パラメータに基づいて決定される。ノードの消費電力パラメータは、単位トラフィック量分のトラフィックの増加に対する該当ノードの消費電力増加量である。経路上の各中継ノードの消費電力パラメータの和が、経路の消費電力パラメータとなる。
【０１００】
なお、経路上の全ノードの消費電力パラメータが総トラフィック量に関係なく一定であれば、経路の消費電力パラメータは、一回だけ収集すればよい。経路上の少なくとも１つのノードの消費電力パラメータが総トラフィック量の影響を受けて変動する場合は、状態収集パケットが転送されるごとに、経路の消費電力パラメータが収集される。
【０１０１】
〔スリープノード数〕スリープノード数は、経路上のスリープモードの状態の中継ノードの数である。なお、スリープノード数を収集せずに、各スリープノードの起動状態になる消費電力増加量の和に加えることも可能である。この場合、分散経路を決定する際に、スリープノード数による判定は行われないこととなる。ただし、スリープ状態から起動状態に移行する際の電力増加量は、処理トラフィック増による増加分より遥かに大きい固定量である。そのため第２の実施の形態では、消費電力パラメータとは別に、スリープノード数を収集し、分散経路の判定においては、スリープノード数による判定結果を、消費電力パラメータによる判定結果に優先する。
【０１０２】
次に、経路状態情報収集処理と輻輳発生の予兆検出時の輻輳制御との実行に用いられる各ルータの機能について説明する。
図１０は、中継ノードの機能を示すブロック図である。中継ノード１００は、フロー情報記憶部１１０、リンク情報記憶部１２０、経路状態通知部１３０、輻輳検出部１４０、分散制御部１５０、パケット中継部１６０、およびスリープ制御部１７０を有している。
【０１０３】
フロー情報記憶部１１０は、中継ノード１００を経由するトラフィックの転送に使用するフローに関する情報（フロー情報）を記憶する。例えば、ＲＡＭ１０２やＨＤＤ１０３の記憶領域の一部が、フロー情報記憶部１１０として使用される。フロー情報記憶部１１０に格納されるフロー情報には、中継ノード１００を経由して転送されるフローに関する経路情報や、その経路のトラフィックの量に関する情報などが含まれる。
【０１０４】
リンク情報記憶部１２０は、中継ノード１００と他のルータとの間のリンクに関する情報を記憶する。例えば、ＲＡＭ１０２やＨＤＤ１０３の記憶領域の一部が、リンク情報記憶部１２０として使用される。リンク情報記憶部１２０には、例えば、リンクごとのトラフィック量などの情報が格納される。
【０１０５】
経路状態通知部１３０は、特定の経路に関する状態収集パケットを受信すると、その状態収集パケットの内容を更新する。例えば経路状態通知部１３０は、自身がスリープノードであれば、状態収集パケットに含まれるスリープノード数を示す情報をカウントアップする。また経路状態通知部１３０は、転送するトラフィック量に応じた中継ノード１００の消費電力パラメータを、状態収集パケットに含まれる経路の消費電力パラメータに加算する。さらに、経路状態通知部１３０は、状態収集パケットに示される経路の次のノードへのリンクの空き容量を算出する。経路状態通知部１３０は、算出したリンクの空き容量と状態収集パケットに示される経路空き容量とを比較する。リンクの空き容量の方が少なければ、算出したリンクの空き容量の値を、新たな経路空き容量として状態収集パケットに設定する。そして経路状態通知部１３０は、状態収集パケットに示される経路における次ノードへ、内容更新後の状態収集パケットを転送する。
【０１０６】
輻輳検出部１４０は、中継ノード１００と他のノードとの間のリンクに関するトラフィックを計測し、輻輳発生の予兆を検出する。例えば、リンク利用率が輻輳制御の制御開始閾値よりも大きくなると、輻輳検出部１４０において輻輳発生の予兆有りと判断される。また輻輳検出部１４０は、トラフィックの計測結果に応じて、フロー情報記憶部１１０内のフロー情報やリンク情報記憶部１２０内のリンク情報を更新する。例えば、輻輳検出部１４０は、リンクのトラフィック量を計測すると、フロー情報におけるフローごとのトラフィック計測値などの情報を更新する。また、輻輳検出部１４０は、リンクのトラフィック量を計測すると、リンク情報におけるリンクのトラフィック量、リンク利用率、偏差などの情報を更新する。
【０１０７】
分散制御部１５０は、特定のリンクにおいて輻輳発生の予兆を検出すると、そのリンク（制御対象リンク）を通る経路を有するフローのうちの少なくとも一部に関し、トラフィックを別の経路へ分散することを決定する。例えば分散制御部１５０は、特定のリンクにおいて輻輳発生の予兆を検出すると、該当リンクを通る経路上を入口ノード方向にアラーム情報を送信する。このアラーム情報は、分散経路候補募集の意味を有している。そのため、アラーム情報を受け取った入口ノードから、分散経路候補情報が送り返される。分散制御部１５０は、取得した分散経路候補情報の中から、トラフィックを分散させることによる消費電力の増加が少ない経路を優先的に選択し、分散先経路に決定する。そして、分散制御部１５０は、決定した分散先経路の入口ノードに対して、分散先経路へのトラフィックの分散を指示する。
【０１０８】
パケット中継部１６０は、隣接する他のノードから送られたパケットを中継する。パケット中継部１６０は、パケットを中継する際には、フロー情報記憶部１１０を参照し、パケットの宛先が出口ノードとなる経路情報を抽出する。そして、パケット中継部１６０は、抽出した経路情報において、中継ノード１００の次のノードにパケットを転送する。ただしパケット中継部１６０は、制御パケットについては、その制御パケット内で指定された経路で転送する。制御パケットには、状態収集パケット、アラーム情報を含むパケット、入札メッセージを含むパケット、分散要求を含むパケットなどがある。
【０１０９】
スリープ制御部１７０は、中継ノード１００のスリープモードへの移行、およびスリープモードから通常モードへの復帰を制御する。例えば、スリープ制御部１７０は、一定期間、制御パケット以外のトラフィックの流入が途絶えた場合、中継ノード１００をスリープモードに移行させる。スリープモードに移行させた場合、スリープ制御部１７０は、例えば、輻輳検出部１４０、分散制御部１５０、パケット中継部１６０を停止することで、消費電力を低下させる。なお、経路状態通知部１３０については、スリープモードに移行しても動作を継続させる。またスリープ制御部１７０は、スリープモードで動作中に制御パケット以外のパケットが入力されると、中継ノード１００を通常モードに移行させる。通常モードに移行する場合、例えば輻輳検出部１４０、分散制御部１５０、パケット中継部１６０の全機能が起動される。
【０１１０】
なおスリープ制御部１７０は、現在の動作モードを示すフラグを保持している。そのフラグは、例えばＲＡＭ１０２内に格納される。経路状態通知部１３０などの他の要素は、スリープ制御部１７０が保持しているフラグを参照して、現在の動作モードを認識できる。
【０１１１】
図１１は、フロー情報記憶部のデータ構造例を示す図である。図１１の例では、フロー情報記憶部１１０にフロー管理テーブル１１１が格納されている。フロー管理テーブル１１１には、フローＩＤ、入口ノード、経路情報、入口ポート、出口ポート、フローのトラフィック計測値、および前回のフローのトラフィック計測値の欄が設けられている。フロー管理テーブル１１１内の横方向に並べられた情報が互いに関連付けられている。互いに関連付けられた情報を含むレコードが、１つのフロー情報となる。
【０１１２】
フローＩＤの欄には、中継ノード１００を経由する経路を有するフローの識別情報（フローＩＤ）が設定される。フローＩＤは、フローの入口ノードのノードＩＤと出口ノードのノードＩＤとの組で表される。例えば、エッジノード２００（ノードＩＤ：Ａ）に入力され、エッジノード２００ｃ（ノードＩＤ：Ｄ）から出力されるフローのフローＩＤは「ＡＤ」となる。
【０１１３】
入口ノードの欄には、フローの入口ノードのノードＩＤが設定される。
経路情報の欄には、フローのトラフィックを転送するために予め設定された経路の情報（経路情報）が設定される。中継ノード１００が有するフロー管理テーブル１１１には、中継ノード１００を含む経路の経路情報が設定される。経路情報には、トラフィックを中継するノードのノードＩＤが、入口ノードに近い順に左から並べられている。
【０１１４】
入口ポートの欄には、経路情報における前のノードとの間のリンクに接続された中継ノード１００の通信ポートのポートＩＤが設定される。
出口ポートの欄には、経路情報における次のノードとの間のリンクに接続された中継ノード１００の通信ポートのポートＩＤが設定される。
【０１１５】
フローのトラフィック計測値の欄には、経路情報で示される経路における中継ノード１００と次のノードとの間の対応するフローに関するトラフィック（トラフィック計測値）が設定される。トラフィック計測値は、例えば、一定間隔（トラフィック計測周期）ごとに、その一定時間内に流れるフローごとの各パケットのデータ長を合計した値である。
【０１１６】
前回のフローのトラフィック計測値の欄には、最近のトラフィック計測値の前のトラフィック計測によって得られた各フローのトラフィック計測値が設定される。
フロー情報のうち、フローＩＤ、入口ノード、経路情報、入口ポート、および出口ポートの欄の情報は、システムの管理者によって予め設定される。またフローのトラフィック計測値、前回のフローのトラフィック計測値の欄の情報は、輻輳検出部１４０がリンクのトラフィックを計測するごとに、輻輳検出部１４０によって更新される。
【０１１７】
図１２は、リンク情報記憶部のデータ構造例を示す図である。図１２の例では、リンク情報記憶部１２０には、リンク情報管理テーブル１２１が格納されている。リンク情報管理テーブル１２１には、ポート番号、リンク容量、Target値、Control値、リンクのトラフィック量、リンク利用率、偏差、前回リンク利用率、前回偏差、輻輳制御フラグ、アラーム値、および前回アラーム値の欄が設けられている。リンク情報管理テーブル１２１内の横方向に並べられた情報が互いに関連付けられている。互いに関連付けられた情報を含むレコードが、１つのリンク情報となる。
【０１１８】
ポート番号の欄には、中継ノード１００の通信ポートのポート番号が設定される。
リンク容量の欄には、通信ポートを介した通信の単位時間当たりの最大通信容量（バンド幅）が、基準値の倍数で示される。第２の実施の形態では、各通信ポートのバンド幅が同じであるため、各通信ポートのバンド幅を単位容量とし、リンク容量として「１」が設定されている。
【０１１９】
Target値の欄には、リンクごとのTarget値が設定されている。Target値は、リンク容量設定の際の単位容量に対する比率で示される。例えば、ポート番号「＃４」に対応するリンクのTarget値は「０．８」である。
【０１２０】
Control値の欄には、リンクごとのControl値が設定されている。Control値は、リンク容量に対する比率で示される。図１２の例では、すべてのリンクのControl値として「０．１」が設定されている。
【０１２１】
リンクのトラフィック量の欄には、各リンクについて最近測定したトラフィック量が設定される。リンクのトラフィック量は、リンク容量設定の際の単位容量に対する比率で示される。トラフィック量が「０」の通信ポートは、送出しているトラフィックがないことを示している。
【０１２２】
リンク利用率の欄には、最近測定した各リンクのリンク利用率が設定されている。なお図１２の例では、各通信ポートのバンド幅を単位容量とし、リンク容量が「１」となっているため、リンクのトラフィック量とリンク利用率とは同じ値となる。
【０１２３】
偏差の欄には、最近測定した各リンクの偏差が設定される。
前回リンク利用率の欄には、最近の測定の１回前に測定した各リンクのリンク利用率が設定されている。
【０１２４】
前回偏差の欄には、最近の測定の１回前に測定した各リンクの偏差が設定されている。
輻輳制御フラグの欄には、輻輳の予兆を検出した場合に、輻輳制御フラグが設定される。
【０１２５】
アラーム値の欄には、輻輳の予兆を検出した場合に、直前のアラーム情報の送信時に計算されたアラーム値が設定される。
前回アラーム値の欄には、直前のアラーム情報の送信の前のアラーム送信時に計算されたアラーム値が設定される。
【０１２６】
リンク情報のうち、ポート番号、リンク容量、Target値、およびControl値の欄の情報は、システムの管理者によって予め設定される。リンク情報のうち、リンク利用率、偏差、前回リンク利用率、および前回偏差の欄の情報は、輻輳検出部１４０がリンクのトラフィックを計測するごとに、輻輳検出部１４０によって更新される。リンク情報のうち、輻輳制御フラグ、アラーム値、および前回アラーム値の欄の情報は、輻輳制御が行われているときに、輻輳検出部１４０によって更新される。
【０１２７】
図１３は、エッジノードの機能を示すブロック図である。エッジノード２００には、フロー情報記憶部２１１、リンク情報記憶部２１２、経路状態通知部２１３、輻輳検出部２１４、分散制御部２１５、パケット中継部２１６、スリープ制御部２１７、経路状態情報記憶部２２０、経路状態情報収集部２３０、入札処理部２４０、および送出確率変更部２５０を有している。このうちフロー情報記憶部２１１、リンク情報記憶部２１２、経路状態通知部２１３、輻輳検出部２１４、および分散制御部２１５については、エッジノード２００が中継ノードと同様にトラフィックを中継するのに用いられる機能である。従って、フロー情報記憶部２１１、リンク情報記憶部２１２、経路状態通知部２１３、輻輳検出部２１４、分散制御部２１５、パケット中継部２１６、スリープ制御部２１７は、図１０に示した中継ノード１００内の同名の要素と同様の機能を有している。ただし、パケット中継部２１６は、エッジノード２００が入口ノードとなるフローについては、経路状態情報記憶部２２０に設定されている送出確率に従って、該当フローに設定された経路にトラフィックを振り分ける。またパケット中継部２１６は、エッジノード２００が入口ノードとなるフローの経路ごとのトラフィック量を定期的に計測し、経路状態情報記憶部２２０に設定する。
【０１２８】
経路状態情報記憶部２２０は、エッジノード２００を入口ノードとするフローの経路の状態に関する情報（経路状態情報）を記憶する。例えばエッジノード２００のＲＡＭやＨＤＤの記憶領域の一部が経路状態情報記憶部２２０として使用される。
【０１２９】
経路状態情報収集部２３０は、経路状態情報を定期的に収集する。例えば経路状態情報収集部２３０は、制御パケットの一種である状態収集パケットを、予め設定されている経路に沿って出口ノード宛に送信する。状態収集パケットは、出口ノードに到達すると、収集結果がエッジノード２００に送り返される。また状態収集パケットは各ノードで転送されるごとに内部の情報が更新され、エッジノード２００に送り返される収集結果には、経路の最新の状態を示す情報が設定される。経路状態情報収集部２３０は、収集した経路状態情報を経路状態情報記憶部２２０に格納する。
【０１３０】
入札処理部２４０は、トラフィックを中継するノード（中継ノードまたはエッジノード）からアラーム情報が入力されると、分散経路の候補を示す情報（分散経路候補情報）を作成して、アラーム情報の送信元のノードで送信する。分散経路の候補は、アラームが発生したフローの経路のうち、アラーム情報の送信元のノードを経由しない経路から選択される。
【０１３１】
送出確率変更部２５０は、特定のフローに関する負荷分散要求を受け取ると、特定のフローのトラフィックの一部を負荷分散要求に示される分散対象経路へ分散させる。分散させるトラフィックの量は、負荷分散要求に示されるアラーム値によって決定される。
【０１３２】
図１４は、ノードＩＤ「Ａ」のエッジノードの経路状態情報記憶部のデータ構造例を示す図である。経路状態情報記憶部２２０には、経路管理テーブル２２１が格納されている。経路管理テーブル２２１には、フローＩＤ、経路、スリープノード数、送出確率、経路空き容量、経路消費電力パラメータ、受信アラーム値、およびフローのトラフィック値の欄が設けられている。経路管理テーブル２２１内の横方向に並べられた情報が互いに関連付けられている。互いに関連付けられた情報を含むレコードが、１つの経路状態情報となる。
【０１３３】
フローＩＤの欄には、エッジノード２００を入口ノードとするフローのフローＩＤが設定される。
経路の欄には、エッジノード２００を入口ノードとするフローにおけるトラフィックの経路が設定される。
【０１３４】
スリープノード数の欄には、経路上の中継ノードのうちのスリープノードの数が設定される。
送出確率の欄には、フローにおけるトラフィックの対応する経路への送出確率が設定される。図１４の例では、経路「ＡＣＤ」及び経路「ＡＧＤ」に対する送出確率が「０．０」であり、経路「ＡＥＤ」に対する送出確率が「１．０」である。これは、フローＩＤ「ＡＤ」で示されるフローのトラフィックが、経路「ＡＥＤ」に集約されていることを示している。
【０１３５】
経路空き容量の欄には、対応する経路空き容量が設定される。
経路消費電力パラメータの欄には、対応する経路の消費電力パラメータが設定される。
受信アラーム値の欄には、対応する経路でアラームが発生したときに受信したアラーム値が設定される。
【０１３６】
フローのトラフィック値の欄には、エッジノード２００で該当経路に振り分けたトラフィック量が設定される。
経路状態情報のうち、フローＩＤと経路との欄に設定される情報は、システムの管理者によって予め設定される。経路状態情報のうち、スリープノード数、経路空き容量、経路消費電力パラメータについては、経路状態情報収集部２３０が経路状態情報収集処理を行うごとに経路状態情報収集部２３０によって更新される。経路状態情報のうち送出確率については、送出確率変更部２５０が送出確率を計算するごとに送出確率変更部２５０によって更新される。経路状態情報のうちフローのトラフィック値については、パケット中継部２１６が単位時間当たりの各フローの経路ごとのトラフィック量を計測するごとに、パケット中継部２１６によって更新される。なおパケット中継部２１６は、定期的にフローの経路ごとのトラフィック量を計測する。
【０１３７】
次に、経路状態情報収集処理について詳細に説明する。
図１５は、経路状態情報収集処理の一例を示す図である。図１５の例では、エッジノード２００ｃを出口ノードとする３つのフローに関する経路状態情報収集処理が示されている。１つのフローの入口ノードは、エッジノード２００である。他の１つのフローの入口ノードはエッジノード２００ａである。また、もう１つのフローの入口ノードはエッジノード２００ｂである。
【０１３８】
図１５では、エッジノード２００ｃを出口ノードとする３つのフローのトラフィックを、実線の矢印で示している。エッジノード２００には、エッジノード２００ｃを出口ノードとするフローに対して、３つの経路が登録されている。１つの経路は、エッジノード２００ｂのみを経由する。他の１つの経路は、中継ノード１００のみを経由する。もう１つの経路は中継ノード１００ｂのみを経由する。エッジノード２００ａには、エッジノード２００ｃを出口ノードとするフローに対して、２つの経路が登録されている。１つの経路は、中継ノード１００のみを経由する。他の１つの経路は、中継ノード１００ａのみを経由する。エッジノード２００ｂには、エッジノード２００ｃを出口ノードとするフローに対して、他のノードを経由しない１つの経路のみが登録されている。
【０１３９】
入口ノードとなる各エッジノード２００，２００ａ，２００ｂは、エッジノード２００ｃを出口ノードとするフローに設定されている各経路を介して、状態収集パケット３１〜３６を出力する。例えば状態収集パケット３１〜３６には、状態情報パケットであることを示す識別子、および状態情報の収集対象となる経路の情報が含まれる。またエッジノード２００，２００ａ，２００ｂから送出直後の状態収集パケット３１〜３６には、収集すべき各種情報が初期状態で含められている。図１５では、状態収集パケット３１〜３６が転送される経路を、点線の矢印で示している。例えば、エッジノード２００から出力された状態収集パケット３１は、中継ノード１００を経由してエッジノード２００ｃに転送される。中継ノード２００は、状態収集パケット３１を転送する際には、状態収集パケット３１内の情報を更新する。エッジノード２００ｃは、自身が、状態収集パケットで経路状態情報を収集すべき経路における出口ノードであることを認識し、状態収集パケット３１による収集結果をエッジノード２００に送り返す。
【０１４０】
各エッジノード２００，２００ａ，２００ｂは、自己の認識している経路に沿って状態収集パケット３１〜３６を、定期的に送信する。その結果、エッジノード２００，２００ａ，２００ｂで経路状態情報が定期的に取得される。経路状態情報には、経路の空き容量、経路の消費電力パラメータ、スリープノード数などが含まれる。各エッジノード２００，２００ａ，２００ｂは、取得した状態収集パケット３１〜３６に基づいて、自己の管理する経路状態情報を更新する。
【０１４１】
ここで、経路「ＡＥＤ」と経路「ＢＥＤ」とについて着目し、経路空き容量の計算例について説明する。
図１６は、経路「ＡＥＤ」と経路「ＢＥＤ」との経路空き容量計算例を示す図である。経路「ＡＥＤ」と経路「ＢＥＤ」との両方の経路上に配置された中継ノード１００は、出力ポートごとのリンクのトラフィック量を計測している。図１６の例では、ポート番号「＃１」の通信ポートがエッジノード２００に接続されている。ポート番号「＃２」の通信ポートがエッジノード２００ａに接続されている。ポート番号「＃３」の通信ポートがエッジノード２００ｂに接続されている。ポート番号「＃４」の通信ポートがエッジノード２００ｃに接続されている。ポート番号「＃５」の通信ポートが中継ノード１００ａに接続されている。
【０１４２】
ここで、リンクのトラフィック量は、そのリンクを通過するフローのトラフィック量の和である。このトラフィック量は、中継ノード１００の輻輳検出部１４０がトラフィック計測周期ごとに、単位時間内に流れるフローごとのパケット数とデータ長とを集計することにより測定される。図１６の例では、フロー「ＡＤ」のトラフィック量が「０．３」であり、すべてのトラフィックが経路「ＡＥＤ」に集約されている。また、フロー「ＢＤ」のトラフィック量が「０．４」であり、すべてのトラフィックが経路「ＢＥＤ」に集約されている。すると、中継ノード１００におけるポート番号「＃４」の通信ポートを出力ポートとするリンクのトラフィック量は、「０．７＝０．３＋０．４」となる。
【０１４３】
図１６の例では、中継ノード１００において、ポート番号「＃４」の通信ポートを出力ポートとするリンクのTarget値が「０．８」に設定されている。この場合、ポート番号「＃４」の通信ポートを出力ポートとするリンクの空き容量は「０．１＝０．８−０．７」となる。ネットワーク１０上に図示した以外のフローが存在していない場合、経路「ＡＥＤ」と経路「ＢＥＤ」とのそれぞれの状態収集パケットは、共に中継ノード１００において経路空き容量が「０．１」に更新される。このようにして更新された状態収集パケットの収集結果が、各エッジノード２００，２００ａに送信され、経路状態情報が更新される。例えば、エッジノード２００の経路状態情報は、図１４に示した通りの内容となる。また、エッジノード２００ａが管理する経路状態情報は、図１７に示す通りの内容となる。
【０１４４】
図１７は、ノードＩＤ「Ｂ」のエッジノードの経路状態情報記憶部のデータ構造例を示す図である。エッジノード２００ａが有する経路状態情報記憶部２２０ａには、図１４と同様のデータ構造の経路管理テーブル２２１ａが格納されている。この経路管理テーブル２２１ａには、エッジノード２００ａを入口ノードとするフローの経路状態情報が登録されている。
【０１４５】
このような経路状態情報収集処理は、入口ノードであるエッジノードの経路状態情報収集部と、経路上の他のノードの経路状態通知部との連携処理である。
図１８は、入口ノードでの経路状態情報収集処理の手順を示すフローチャートである。図１８には、１つの経路に対する処理手順が示されている。すなわち、図１８に示した処理が、経路管理テーブルに登録されている経路状態情報に示される経路ごとに個別に実行される。以下、図１８に示す処理をステップ番号に沿って説明する。
【０１４６】
［ステップＳ１１］経路状態情報収集部２３０は、状態収集パケットを送信する。状態収集パケットは制御パケットの一種であり、転送の経路がパケット内に指定されている。状態収集パケットの伝送経路は、経路状態情報収集の対象となる経路（経路管理テーブルの経路の欄に示される経路）である。また、生成された状態収集パケットには、スリープノード数、経路空き容量、消費電力パラメータの初期値が設定されている。スリープノード数の初期値は、例えば「０」である。経路空き容量の初期値は、例えば「１」である。消費電力パラメータの初期値は、例えば「０」である。
【０１４７】
［ステップＳ１２］経路状態情報収集部２３０は、経路状態情報の収集結果を受信したか否かを判断する。収集結果を受信した場合、処理がステップＳ１３に進められる。収集結果を受信していなければステップＳ１２の処理が繰り返され、収集結果の受信待ち状態となる。
【０１４８】
［ステップＳ１３］経路状態情報収集部２３０は、受信した収集結果に基づいて、経路状態情報記憶部２２０内の該当する経路の経路状態情報を更新する。
［ステップＳ１４］経路状態情報収集部２３０は、予め設定された経路状態情報収集周期だけ待機する。ステップＳ１３の処理が終了してから経路状態情報収集周期が経過すると、処理がステップＳ１１に進められる。
【０１４９】
このようにして、入口ノードにおいて定期的な経路状態情報の収集処理が行われる。次に、状態収集パケットを受信したノードで実行される経路状態情報通知処理について説明する。
【０１５０】
図１９は、経路状態情報通知処理の手順を示すフローチャートである。以下、図１９に示す処理をステップ番号に沿って説明する。
［ステップＳ２１］経路状態通知部１３０は、状態収集パケットを受信すると、その状態収集パケットに示される経路において、中継ノード１００自身が出口ノードとなる経路か否かを判断する。出口ノードであれば、処理がステップＳ２２に進められる。出口ノードでなければ処理がステップＳ２３に進められる。
【０１５１】
［ステップＳ２２］経路状態通知部１３０は、状態収集パケットに示される経路の入口ノードへ、収集結果を送信する。収集結果は、制御パケットに含めて送信される。その後、経路状態情報通知処理が終了する。
【０１５２】
なお図１９のフローチャートは、中継ノードとエッジノードとのいずれの経路状態通知部でも同様の処理を実行することを前提としている。そのため、中継ノード１００の経路状態通知部１３０においてもステップＳ２１，Ｓ２２のような出口ノードにおける処理が含まれている。ただし、第２の実施の形態では中継ノードは出口ノードとはならない。そのため、中継ノード内の経路状態通知部１３０においては、ステップＳ２１，Ｓ２２の処理を行わなくてもよい。
【０１５３】
［ステップＳ２３］経路状態通知部１３０は、自身が出口ノードでなければ、スリープノードか否かを判断する。例えば経路状態通知部１３０は、スリープ制御部１７０が保持しているフラグを参照し、動作モードがスリープモードか否かを判断する。動作モードがスリープモードであれば、経路状態通知部１３０は、中継ノード１００がスリープノードであると判断する。スリープノードであれば、処理がステップＳ２４に進められる。スリープノードでなければ、処理がステップＳ２５に進められる。
【０１５４】
［ステップＳ２４］経路状態通知部１３０は、中継ノード１００がスリープノードであれば、状態収集パケットに含まれるスリープノード数の値に「１」を加算する。
［ステップＳ２５］経路状態通知部１３０は、経路の次のノードへのリンクの空き容量を計算する。例えば経路状態通知部１３０は、状態収集パケットに示される経路（対象経路）に基づいて、中継ノード１００の次となるノードを判断する。次に、経路状態通知部１３０は、フロー情報記憶部１１０内の対象経路に対応するフロー情報を参照し、出口ポートを判断する。さらに経路状態通知部１３０は、リンク情報記憶部１２０内の対象経路の出口ポートに対応するリンク情報を参照し、リンク容量、Target値、およびリンクのトラフィック量を抽出する。そして、経路状態通知部１３０は、「リンク容量×Target値−リンクトラフィック量」の計算結果を、リンクの空き容量とする。
【０１５５】
［ステップＳ２６］経路状態通知部１３０は、状態収集パケットをこれまで転送したノードで算出されたリンクの空き容量のなかで、ステップＳ２５で算出したリンクの空き容量が最も少ないか否かを判断する。例えば経路状態通知部１３０は、状態収集パケットに含まれる経路空き容量と、算出したリンクの空き容量とを比較する。リンク空き容量の方が少なければ、算出したリンクの空き容量がこれまでで最も少ないと判断される。算出したリンクの空き容量がこれまでで最も少ない場合、処理がステップＳ２７に進められる。そうでなければ、処理がステップＳ２８に進められる。
【０１５６】
［ステップＳ２７］経路状態通知部１３０は、状態収集パケットに含まれている経路空き容量の値を、ステップＳ２５で算出したリンク空き容量の値に更新する。その後、処理がステップＳ２８に進められる。
【０１５７】
［ステップＳ２８］経路状態通知部１３０は、状態収集パケットに含まれている消費電力パラメータを更新する。例えば経路状態通知部１３０は、中継ノード１００の消費電力パラメータの値を、状態収集パケットに含まれている消費電力パラメータの値に加算する。
【０１５８】
［ステップＳ２９］経路状態通知部１３０は、経路上の次のノードへ状態収集パケットを転送する。その後、処理が終了する。
以上のようにして、入口ノードと他のノードとの連携動作により、入口ノードにおいて経路状態情報が収集される。そして、経路状態情報の収集が定期的に行われることで、入口ノードにおける経路状態情報記憶部内の経路状態情報が、随時最新の情報に更新される。
【０１５９】
次に、輻輳検出処理について説明する。
図２０は、輻輳の予兆発生例を示す図である。図２０の例では、フロー「ＢＤ」のトラフィック量が「０．４」から「０．６」に増加している。すると、中継ノード１００のノード番号「＃４」の通信ポートを出力ポートとするリンクにおいて、リンクのトラフィック量が「０．９」となる。ここで中継ノード１００において、ノード番号「＃４」の通信ポートを出力ポートとするリンクのTarget値が「０．８」、Control値が「０．１」であるものとする。この場合、制御開始閾値は「０．７＝０．８−０．１」である。すると、リンクのトラフィック量が制御開始閾値より大きくなっている。中継ノード１００では、輻輳検出部１４０がリンクのトラフィック量が制御開始閾値を超えたことを検出し、輻輳制御を開始する。
【０１６０】
図２１は、輻輳検出処理の手順の一例を示すフローチャートである。以下、図２１に示す処理をステップ番号に沿って説明する。
［ステップＳ３１］輻輳検出部１４０は、中継ノード１００を経由する各フローの単位時間当たりの通過データ量を計測する。これにより、各フローのトラフィック量が得られる。輻輳検出部１４０は、算出したフローのトラフィック量を、各フローのトラフィック計測値としてフロー情報記憶部１１０内に新たに格納する。この際、輻輳検出部１４０は、新たに計測したトラフィック計測値の登録以前に、フローのトラフィック計測値として設定されていた値を、前回のフローのトラフィック計測値としてフロー情報記憶部１１０に格納する。
【０１６１】
［ステップＳ３２］輻輳検出部１４０は、中継ノード１００と他のノードとの間の各リンクを処理対象リンクとし、処理対象リンクごとに、ステップＳ３３〜ステップＳ３６の処理を実行する。
【０１６２】
［ステップＳ３３］輻輳検出部１４０は、リンクのトラフィック量、リンク利用率、および偏差を計算する。例えば輻輳検出部１４０は、フロー情報記憶部１１０内の各フローの出力ポートを参照し、処理対象リンクを通過するフローを判断する。次に輻輳検出部１４０は、処理対象リンクを通過するフローのトラフィック量の和を求める。算出された和が、処理対象リンクのトラフィック量となる。さらに輻輳検出部１４０は、リンクのトラフィック量をリンク容量で除算し、リンク利用率を求める。また輻輳検出部１４０は、Target値からリンク利用率を減算し、偏差を求める。
【０１６３】
輻輳検出部１４０は、算出したリンクのトラフィック量、リンクの利用率、および偏差を、リンク情報記憶部１２０に格納する。この際、輻輳検出部１４０は、新たに算出したリンク利用率および偏差の登録前に該当項目に格納されていた情報を、それぞれ前回リンク利用率、前回偏差としてリンク情報記憶部１２０に格納する。
【０１６４】
［ステップＳ３４］輻輳検出部１４０は、処理対象リンクのリンク利用率が、輻輳制御の制御開始閾値を超えているか否かを判断する。リンク利用率が制御開始閾値を超えていれば、処理がステップＳ３６に進められる。制御開始閾値を超えていなければ、処理がステップＳ３５に進められる。
【０１６５】
［ステップＳ３５］輻輳検出部１４０は、リンク利用率が制御開始閾値を超えていなければ、輻輳制御フラグをリセットする。例えば、輻輳制御フラグが「１」のとき輻輳制御実行中を示し、「０」のとき輻輳制御を実行していないことを示す場合、輻輳検出部１４０は輻輳制御フラグを「０」にセットする。なお、ステップＳ３５の処理以前から輻輳制御フラグがセットされていない場合には、リセットの処理を行わなくてもよい。その後、処理がステップＳ３７に進められる。
【０１６６】
［ステップＳ３６］輻輳検出部１４０は、リンク利用率が制御開始閾値を超えていれば、輻輳制御処理を実行する。この処理の詳細は後述する（図２６参照）。その後、処理がステップＳ３７に進められる。
【０１６７】
［ステップＳ３７］輻輳検出部１４０は、すべてのリンクに対してステップＳ３３〜ステップＳ３６の処理が完了すると、処理をステップＳ３８に進める。
［ステップＳ３８］輻輳検出部１４０は、トラフィック計測周期の時間だけ待機し、処理をステップＳ３１進める。
【０１６８】
このような処理により、定期的にフローのトラフィックが計測され、フロー情報記憶部１１０内のフロー情報が更新される。
図２２は、フロー情報更新後のフロー情報記憶部の例を示す図である。図２２には、図２０に示した各フローのトラフィックの計測結果が反映されている。図１１と比較すると分かるように、フローＩＤ「ＢＤ」のフロー情報に関して、フローのトラフィック計測値と前回のフローのトラフィック計測値とが更新されている。フローのトラフィック計測値は「０．４」から「０．６」に変更されている。前回のフローのトラフィック計測値は「０．３」から「０．４」に変更されている。
【０１６９】
また、リンクのトラフィック量が計測されることで、リンク情報記憶部１２０内のリンク情報が更新される。この際、リンク利用率が制御開始閾値を超えたリンクを含むフローに関するリンク情報には、輻輳制御フラグが立てられ、アラーム値が設定される。
【０１７０】
図２３は、リンク情報更新後のリンク情報記憶部の例を示す図である。図２３は、図２０に示した輻輳の予兆を検出したことによりアラーム発生後のリンク情報記憶部１２０内のリンク情報を示している。図１２と比較すると分かるように、ポート番号「＃４」の通信ポートを出力ポートとするリンクについて、リンクのトラフィック量、リンク利用率、偏差、前回リンク利用率、前回偏差、輻輳制御フラグ、アラーム値、および前回アラーム値が更新されている。
【０１７１】
ポート番号「＃４」の通信ポートを出力ポートとするリンクのリンク情報は、トラフィック量が「０．７」から「０．９」に変更されている。リンク利用率が「０．７」から「０．９」に変更されている。偏差が「０．１」から「−０．１」に変更されている。前回リンク利用率が「０．６」から「０．７」に変更されている。前回偏差が「０．２」から「０．１」に変更されている。輻輳制御フラグが新たにセットされている。アラーム値として新たに「０．８９」が設定されている。前回アラーム値には、初期値として「１」が設定されている。
【０１７２】
このように中継ノード１００におけるフロー情報やリンク情報が更新されると、経路状態情報収集処理によって、エッジノード２００，２００ａの経路状態情報にも変更内容が反映される。
【０１７３】
図２４は、ノードＩＤ「Ａ」のエッジノードの更新後の経路状態情報記憶部の例を示す図である。図２４には、図２０に示した各フローのトラフィックの計測結果が反映されている。図１４と比較すると分かるように、フローＩＤ「ＡＤ」の経路「ＡＥＤ」の経路状態情報に関して、経路空き容量が更新されている。経路空き容量は「０．１」から「０」に変更されている。
【０１７４】
なお経路空き容量は、経路上のリンクの空き容量のうちの最小値である。リンクの空き容量は、リンク容量×Target値−リンクトラフィック量である。そのため、図２０の例では、中継ノード１００のポート番号「＃４」の通信ポートを出力ポートとするリンクの空き容量は、計算式上は「−０．１」（１×０．８−０．９）となってしまう。ただし、リンクの空き容量が計算上負の数になるときは、リンクの空き容量の値は「０」とされる。「０」は最小値であるため、該当リンクを通るすべての経路の経路空き容量も「０」となる。
【０１７５】
図２５は、ノードＩＤ「Ｂ」のエッジノードの更新後の経路状態情報記憶部の例を示す図である。図２５には、図２０に示した各フローのトラフィックの計測結果が反映されている。図１７と比較すると分かるように、フローＩＤ「ＢＤ」の経路「ＢＥＤ」の経路状態情報に関して、経路空き容量が更新されている。経路空き容量は「０．１」から「０」に変更されている。
【０１７６】
トラフィックの計測が行われた結果、リンク利用率が制御開始閾値を超えるリンクが検出されると、輻輳の予兆検出と判断され輻輳制御処理が行われる。
図２６は、輻輳制御処理の手順の一例を示すフローチャートである。以下、図２６に示す処理をステップ番号に沿って説明する。
【０１７７】
［ステップＳ４１］輻輳検出部１４０は、分散経路募集処理を実行する。分散経路募集処理は、トラフィックの分散先となる経路の候補を、入口ノードに募集する処理である。分散経路募集処理において、入口ノードに対してアラーム情報が送信される。この処理の詳細は後述する（図２９参照）。
【０１７８】
［ステップＳ４２］分散制御部１５０は、分散経路候補の中からトラフィックの分散先とする経路を決定し、その経路の入口ノードに対してトラフィックの負荷分散を指示する。この処理の詳細は後述する（図３５参照）。
【０１７９】
図２７は、分散経路募集処理によるアラーム情報の送信状況を示す図である。図２７の例では、中継ノード１００のポート番号「＃４」の通信ポートを出力ポートとするリンクにおいて、輻輳の予兆が検出されている。この場合、輻輳の予兆が検出された制御対象リンクを通る経路の入口ノードであるエッジノード２００，２００ａに対してアラーム情報が送信されている。
【０１８０】
アラーム情報には、「アラーム値（規制率）」、「フローＩＤ」、「入口ノード名（アラーム情報宛先）」、「経路情報」、および「制御対象リンク名」が含まれる。制御対象リンク名は、輻輳の予兆が検出されたリンクのリンク名である。リンク名は、リンクの両端のノードのノードＩＤの組で表される。その際、左側にリンクへトラフィックを出力するノードのノードＩＤ、右側に該当リンクからトラフィックが入力されるノードのノードＩＤが設定される。例えば、中継ノード１００のポート番号「＃４」の通信ポートを出力ポートとするリンクのリンク名は「ＥＤ」となる。
【０１８１】
リンクｉのアラーム値が以下の式で計算される。
ａi（ｔ）＝ａi（ｔ−１）＋Ｐ×（ｅi（ｔ）−ｅi（ｔ−１））＋Ｉ×ｅi（ｔ）
・・・（４）
ここで「ｔ」はアラーム情報送信周期における何周期目かを示す値である。ｔは、１から開始され、一周期ごとに１ずつ増加される。ただし、「ａi（０）＝１」と定義する。
【０１８２】
「Ｐ」、「Ｉ」は、ＰＩ（Proportional-Integral）コントローラにおける制御パラメータであり、所定の値が設定される。例えば、本実施の形態では、Ｐ＝０．５、Ｉ＝０．１であるものとする。
【０１８３】
ｅi（ｔ）は、リンクｉにおけるｔ周期目の偏差である。偏差「ｅi（ｔ）」は、以下の式で表される。
ｅi（ｔ）＝Ｔi−Ｔｒi（ｔ）    ・・・（５）
ここで「Ｔi」はリンクｉのTarget値である。「Ｔｒi（ｔ）」はリンクｉのトラフィック利用率である。
【０１８４】
例えば、図２３のポート番号「＃４」の通信ポートを出力ポートとするリンク（リンクＥＤ）のアラーム値を計算する場合を考える。
前回アラーム値：ａED（ｔ−１）＝１
偏差：ｅED（ｔ）＝−０．１
前回偏差：ｅED（ｔ−１）＝０．１
ここでＰ＝０．５、Ｉ＝０．１である。そこで、アラーム値は以下の値となる。
アラーム値：
ａED（ｔ）＝１＋０．５（−０．１−０．１）＋０．１（−０．１）＝０．８９
アラーム情報は、制御パケットに含めて送信される。制御パケットは、その制御パケットを転送する経路を指定する情報を付加することができる。例えば、図２７に示すように中継ノード１００のポート番号「＃４」の通信ポートを出力ポートとするリンクでリンク利用率が制御開始閾値を超えると、そのリンク（制御対象リンク）へのトラフィックの入力側である中継ノード１００において、輻輳の予兆が検出される。その場合、中継ノード１００が、アラーム情報を作成して制御パケットに載せる。
【０１８５】
中継ノード１００は、制御対象リンクを介してエッジノード２００ｃへ流れる全フローの各経路の入口ノード宛に、アラーム情報を含む制御パケットを送信する。この制御パケットが出力される通信ポートは、制御対象リンクを含む経路の入口ポート側の隣接ノードに接続された通信ポートである。すなわち、制御対象リンクを含む経路上の入口ノード側に隣接するノードに対して、中継ノード１００から制御パケットが渡される。そして、制御パケットに含められる経路の指定は、制御対象リンクを含む経路を入口ノードに向かって辿る経路である。例えば、図２７のフロー「ＡＤ」の経路「ＡＥＤ」に対しては、中継ノード１００からエッジノード２００へ、アラーム情報を含む制御パケットが送信される。また、フロー「ＢＤ」の経路「ＢＥＤ」に対しては、中継ノード１００からエッジノード２００ａへ、アラーム情報を含む制御パケットが送信される。
【０１８６】
送信されるアラーム情報のデータフォーマットを［フローＩＤ，入口ノード，アラーム発生経路状態情報，制御対象リンク，アラーム値］と表すと、各エッジノード２００，２００ａに送信されるアラーム情報の内容は以下の通りである。
・エッジノード２００宛の制御パケットに含まれるアラーム情報
［ＡＤ，Ａ，（Ａ，Ｅ，Ｄ），ＥＤ，０．８９］
・エッジノード２００ａ宛の制御パケットに含まれるアラーム情報
［ＢＤ，Ｂ，（Ｂ，Ｅ，Ｄ），ＥＤ，０．８９］
図２７の例では、輻輳の予兆を検出した中継ノード１００に対して、制御対象リンクを含む経路の入口ノードが隣接している。そのため、アラーム情報を含む制御パケットの転送は発生していない。もし輻輳の予兆を検出したノードと制御対象リンクを含む経路の入口ノードとが隣接していない場合、アラーム情報を含む制御パケットは、その制御パケットで指定された経路で転送される。
【０１８７】
図２８は、アラーム情報の転送が生じる態様を示す図である。図２８には、図６に示した構成に対し、２台の中継ノード１００ｃ，１００ｄが追加された例が示されている。中継ノード１００ｃは、中継ノード１００とエッジノード２００との間に設けられている。また中継ノード１００ｄは、中継ノード１００と、エッジノード２００ａとの間に設けられている。中継ノード１００ｃのノードＩＤは「Ｈ」である。中継ノード１００ｄのノードＩＤは「Ｉ」である。
【０１８８】
このようなネットワーク構成の場合、フローＩＤ「ＡＤ」のフローの経路は、「Ａ，Ｈ，Ｅ，Ｄ」となる。また、フローＩＤ「ＢＤ」のフローの経路は、経路「ＢＩＥＤ」となる。従って、中継ノード１００におけるフロー管理テーブル１１１ａでは、フローＩＤ「ＡＤ」のフロー情報に経路「ＡＨＥＤ」が設定され、フローＩＤ「ＢＤ」のフロー情報に経路「ＢＩＥＤ」が設定されている。中継ノード１００ｃにおけるフロー管理テーブル１１１ｂにおいても、フローＩＤ「ＡＤ」のフロー情報に経路「ＡＨＥＤ」が設定されている。
【０１８９】
このようなネットワーク構成のときに、中継ノード１００とエッジノード２００ｃとの間のリンクで輻輳の予兆が検出されたものとする。この場合、中継ノード１００において、輻輳の予兆が検出された制御対象リンクを通る２つの経路が認識される。そして、中継ノード１００から各経路の入口ノードであるエッジノード２００，２００ａそれぞれへのアラーム情報が送信される。中継ノード１００からエッジノード２００宛のアラーム情報は、経路「ＡＨＥＤ」を逆向きに沿って、中継ノード１００ｃに送出される。また中継ノード１００からエッジノード２００ａ宛のアラーム情報は、経路「ＢＩＥＤ」を逆向きに沿って、中継ノード１００ｄに送出される。
【０１９０】
中継ノード１００ｃは、取得したアラーム情報を、フローＩＤ「ＡＤ」の経路「ＡＨＥＤ」を逆向きに沿って、エッジノード２００に送出する。中継ノード１００ｄは、取得したアラーム情報を、フローＩＤ「ＢＤ」の経路「ＢＩＥＤ」を逆向きに沿って、エッジノード２００ａに送出する。
【０１９１】
第２の実施の形態では、アラーム情報内に経路状態情報が含まれている。そのため、アラーム情報を受信したノードは、アラーム情報内の経路状態情報を参照して、転送先を判断できる。また、各ノードがフローの経路の情報を有している。従って、アラーム情報に経路状態情報が含まれていなくても、そのアラーム情報の転送が可能である。例えば、アラーム情報を受信したノードは、アラーム情報に含まれるフローＩＤを参照し、そのフローＩＤに対応する経路状態情報をフロー情報記憶部から取得する。そして、アラーム情報を受信したノードは、取得した経路状態情報を逆方向に辿るように、アラーム情報を転送する。
【０１９２】
このようにして、アラーム情報は、経路に沿って逆向きに転送され、入口ノードに渡される。
図２９は、分散経路募集処理の一例を示すフローチャートである。以下、図２９に示す処理をステップ番号に沿って説明する。
【０１９３】
［ステップＳ５１］輻輳検出部１４０は、輻輳制御フラグがリセット状態か否かを判断する。例えば輻輳検出部１４０は、リンク情報記憶部１２０内の制御対象リンクに関するリンク情報を参照し、そのリンク情報に輻輳制御フラグがセットされているか否かを判断する。輻輳制御フラグがリセット状態であれば、処理がステップＳ５２に進められる。輻輳制御フラグがすでにセットされていれば、処理がステップＳ５４に進められる。
【０１９４】
［ステップＳ５２］輻輳検出部１４０は、輻輳制御フラグをセットする。例えば輻輳検出部１４０は、リンク情報記憶部１２０内の制御対象リンクに関するリンク情報に対して、輻輳制御フラグをセットする。
【０１９５】
［ステップＳ５３］輻輳検出部１４０は、前回アラーム値を初期化する。例えば輻輳検出部１４０は、リンク情報記憶部１２０内の制御対象リンクに関するリンク情報の前回アラーム値の項目に対して、「１」を設定する。
【０１９６】
［ステップＳ５４］輻輳検出部１４０は、アラーム値「ａi（ｔ）」を計算する。例えばアラーム値は、上記の式（４）、式（５）によって計算できる。また輻輳検出部１４０はアラーム値の計算に用いられるデータを、リンク情報記憶部１２０内の制御対象リンクに関するリンク情報から取得する。
【０１９７】
［ステップＳ５５］輻輳検出部１４０は、制御対象リンクを通過するフローごとに、ステップＳ５６〜ステップＳ５７の処理を実行する。
［ステップＳ５６］輻輳検出部１４０は、フロー情報記憶部１１０内の制御対象リンクを通過するフローに関するフロー情報から、入口ノードと経路状態情報とを抽出する。
【０１９８】
［ステップＳ５７］輻輳検出部１４０は、フローの経路上を入口ノード側に隣接するノードに対して、アラーム情報を含む入口ノード宛の制御パケットを送信する。
［ステップＳ５８］輻輳検出部１４０は、制御対象リンクを通過するすべてのフローに対するステップＳ５６〜ステップＳ５７の処理が完了した場合、アラーム情報送信処理を終了する。
【０１９９】
以上のようにして、輻輳予兆検出に応じたアラーム情報の送信が行われる。次に、アラーム情報を受信した入口ノードにおける入札処理について説明する。
アラーム情報を受信した入口ノードでは、まず、受信したアラーム情報に基づいて経路状態情報を更新する。
【０２００】
図３０は、ノードＩＤ「Ａ」のエッジノードのアラーム情報受信後の経路状態情報記憶部の例を示す図である。図３０の例は、経路「ＡＥＤ」で輻輳の予兆が検出された場合である。エッジノード２００では、アラーム情報から経路情報とアラーム値が抽出され、経路情報に対応する経路の受信アラーム値の欄に、アラーム情報から抽出したアラーム値が設定される。図３０の例では、受信アラーム値として「０．８９」が設定されている。
【０２０１】
図３１は、ノードＩＤ「Ｂ」のエッジノードのアラーム情報受信後の経路状態情報記憶部の例を示す図である。エッジノード２００ａにおいても、アラーム情報から経路情報とアラーム値が抽出され、経路情報に対応する経路の受信アラーム値の欄に、アラーム情報から抽出したアラーム値が設定される。図３１の例では、受信アラーム値として「０．８９」が設定されている。
【０２０２】
経路状態情報の更新後、アラーム情報を受信したエッジノードは、入札メッセージを送信する。
図３２は、入札メッセージの送信例を示す図である。アラーム情報を受信したエッジノード２００，２００ａは、アラーム情報の送信元である中継ノード１００に対して入札メッセージを送信する。入札メッセージは、アラーム情報で示されたフローに関するアラーム発生経路以外の経路（分散経路候補）を通知するメッセージである。入札メッセージのデータには、「フローＩＤ」、「経路」、「スリープノード数」、「空き容量」、「消費電力パラメータ」を有する分散経路候補情報が含まれる。分散経路候補情報は、分散経路候補ごとに作成され、入札メッセージに含められる。
【０２０３】
図３２の例では、エッジノード２００には、フロー「ＡＤ」の経路として３つの経路「ＡＥＤ」、「ＡＣＤ」、「ＡＧＤ」が設定されている。このうち経路「ＡＥＤ」はアラーム発生経路である。従って２つの経路「ＡＣＤ」、「ＡＧＤ」が、分散経路候補となる。ここで、入札メッセージに含まれる分散経路候補情報のデータフォーマットを（フローＩＤ，経路，スリープノード数，空き容量，消費電力パラメータ）とする。このときエッジノード２００から中継ノード１００に送信される入札メッセージに含まれる分散経路候補情報は以下の通りである。
［（ＡＤ，ＡＣＤ，０，０．７，２０），（ＡＤ，ＡＧＤ，１，０．８，２０）］
エッジノード２００ａには、フロー「ＢＤ」の経路として２つの経路「ＢＥＤ」、「ＢＦＤ」が設定されている。このうち経路「ＢＥＤ」はアラーム発生経路である。従って１つの経路「ＢＦＤ」が、分散経路候補となる。このときエッジノード２００ａから中継ノード１００に送信される入札メッセージに含まれる分散経路候補情報は以下の通りである。
［（ＢＤ，ＢＦＤ，１，０．８，１５）］
次に、入口ノードにおける入札処理の手順について説明する。
【０２０４】
図３３は、入札処理の手順を示す図である。以下、図３３に示す処理をステップ番号に沿って説明する。
［ステップＳ６１］入札処理部２４０は、アラーム情報を受信する。
【０２０５】
［ステップＳ６２］入札処理部２４０は、受信したアラーム情報から、フローＩＤ，入口ノード、アラーム発生経路情報、制御対象リンク、アラーム値フローＩＤを抽出する。このとき、入札処理部２４０は、抽出した入口ノードとしてエッジノード２００のノードＩＤが設定されていることにより、エッジノード２００が入口ノードとなることを認識する。
【０２０６】
［ステップＳ６３］入札処理部２４０は、経路状態情報記憶部２２０内の経路状態情報を更新する。具体的には入札処理部２４０は、アラーム情報から抽出したフローＩＤと経路との組に対応する経路状態情報を、経路状態情報記憶部２２０から特定する。そして入札処理部２４０は、特定した経路状態情報の受信アラーム値として、受信したアラーム情報から抽出したアラーム値を設定する。
【０２０７】
［ステップＳ６４］入札処理部２４０は、分散経路候補があるか否かを判断する。分散経路候補とは、アラーム情報から抽出したフローＩＤで示されるフローの経路のうち、アラーム発生経路以外の経路である。分散経路候補があれば、処理がステップＳ６５に進められる。分散経路候補がなければ、入札処理が終了する。
【０２０８】
［ステップＳ６５］入札処理部２４０は、分散経路候補がある場合、分散経路候補ごとの分散経路候補情報を作成する。なお、入札処理部２４０は、分散経路候補情報を構成する「フローＩＤ」、「経路」、「スリープノード数」、「空き容量」、「消費電力パラメータ」は、経路状態情報記憶部２２０から取得する。
【０２０９】
［ステップＳ６６］入札処理部２４０は、作成した分散経路候補情報を１つの入札メッセージに含め、アラーム情報の送信元であるノードに入札メッセージを送信する。その後、処理が終了する。
【０２１０】
入札メッセージを取得した中継ノード１００では、各入札メッセージに含まれる分散経路候補情報を比較し、分散先経路を決定する。例えば中継ノード１００は、起動するスリープノードが少ない分散経路候補を選択し、分散先経路に決定する。そして、中継ノード１００は決定した分散経路の入口ノードであるエッジノードに対して分散要求を送信する。
【０２１１】
図３４は、分散要求の送信例を示す図である。図３４の例では、中継ノード１００ａと１００ｂがスリープノードであり、エッジノード２００ａが提示した分散経路候補は、中継ノード１００ａを経由する経路である。また、エッジノード２００が提示した分散経路候補は中継ノード１００ｂを経由する経路と、エッジノード２００ｂを経由する経路である。そこで中継ノード１００では提示された分散経路候補の中から１つを選択し、分散経路に決定する。例えば中継ノード１００は、提示された３つの分散経路候補のうち、スリープノード数の少ない方の経路（つまり経路「ＡＣＤ」）を選択する。そして、中継ノード１００は、エッジノード２００に対して経路「ＡＣＤ」へのトラフィックの分散要求を送信する。
【０２１２】
分散要求には、「フローＩＤ」、「分散先経路」、「アラーム発生経路」、「アラーム値」が含まれる。分散要求のデータフォーマットを［フローＩＤ，分散先経路，アラーム発生経路，アラーム値］とすると、図３４の例においてエッジノード２００に送信される分散要求の内容は以下の通りとなる。
［ＡＤ，ＡＣＤ，ＡＥＤ，０．８９］
次に、分散先候補決定処理の手順について説明する。
【０２１３】
図３５は、分散先経路決定処理の手順の一例を示すフローチャートである。以下、図３５に示す処理をステップ番号に沿って説明する。
［ステップＳ７１］分散制御部１５０は、入札メッセージを受信したか否かを判断する。入札メッセージを受信したら処理がステップＳ７２に進められる。入札メッセージを受信していなければ、処理がステップＳ７３に進められる。
【０２１４】
［ステップＳ７２］分散制御部１５０は、入札メッセージに含まれる分散経路候補をＲＡＭ１０２またはＨＤＤ１０３内の記憶領域に格納する。
［ステップＳ７３］分散制御部１５０は、入札メッセージ待ち時間がタイムアウトとなったか否かを判断する。入札メッセージ待ち時間は、アラーム情報を送信してから所定の時間である。分散制御部１５０は、アラーム情報を送信したときから時間計測を開始し、入札メッセージ待ち時間を経過するとタイムアウトと判定する。タイムアウトになった場合、処理がステップＳ７４に進められる。タイムアウトとなっていなければ、処理がステップＳ７１に進められる。
【０２１５】
［ステップＳ７４］分散制御部１５０は、分散経路候補評価処理を行う。この処理の詳細は後述する（図３６参照）。
［ステップＳ７５］分散制御部１５０は、分散経路候補評価処理によって選択した分散経路候補を、分散先経路に決定する。
【０２１６】
［ステップＳ７６］分散制御部１５０は、分散先経路の入口ノードに対して、分散先経路へのトラフィックの分散要求を送信する。その後、分散先決定処理が終了する。
次に、分散経路候補評価処理について説明する。
【０２１７】
図３６は、分散経路候補評価処理の手順の一例を示すフローチャートである。以下、図３６に示す処理をステップ番号に沿って説明する。
［ステップＳ８１］分散制御部１５０は、入札メッセージ中の分散経路候補をスリープノード数が少ない順に整列させる。
【０２１８】
［ステップＳ８２］分散制御部１５０は、ステップＳ８１で整列させた分散経路候補から、スリープノード数が最も少ない分散経路候補を抽出する。
［ステップＳ８３］分散制御部１５０は、ステップＳ８２においてスリープノード数が最も少ない分散経路候補が複数抽出されたか否かを判断する。複数の分散経路候補が抽出された場合、処理がステップＳ８５に進められる。抽出された分散経路候補が１つだけの場合、処理がステップＳ８４に進められる。
【０２１９】
［ステップＳ８４］分散制御部１５０は、ステップＳ８２で抽出した分散経路候補が１つだけであれば、その分散経路候補を選択し、分散経路候補評価処理を終了する。
［ステップＳ８５］分散制御部１５０は、ステップＳ８２で抽出した分散経路候補が複数あれば、抽出した分散経路候補を消費電力パラメータが小さい順に整列させる。
【０２２０】
［ステップＳ８６］分散制御部１５０は、ステップＳ８５で整列させた分散経路候補から、消費電力パラメータが最小の分散経路候補を抽出する。
［ステップＳ８７］分散制御部１５０は、ステップＳ８６において消費電力パラメータが最小の分散経路候補が複数抽出されたか否かを判断する複数の分散経路候補が抽出された場合、処理がステップＳ８９に進められる。抽出された分散経路候補が１つだけの場合、処理がステップＳ８８に進められる。
【０２２１】
［ステップＳ８８］分散制御部１５０は、ステップＳ８６で抽出した分散経路候補が１つだけであれば、その分散経路候補を選択し、分散経路候補評価処理を終了する。
［ステップＳ８９］分散制御部１５０は、ステップＳ８６で抽出した分散経路候補が複数あれば、抽出した分散経路候補を空き容量が大きい順に整列させる。
【０２２２】
［ステップＳ９０］分散制御部１５０は、ステップＳ８９で整列させた分散経路候補から、空き容量が最大の経路を抽出する。
［ステップＳ９１］分散制御部１５０は、ステップＳ９０で抽出した分散経路候補のうちの１つを選択し、分散経路候補評価処理を終了する。
【０２２３】
以上のような処理により、分散先経路が決定され、分散先経路の入口ノードに対して分散要求が送信される。分散要求を受信した入口ノードでは、分散要求に従ってトラフィックの負荷分散を行う。
【０２２４】
次に入口ノードにおけるトラフィックの負荷分散処理について説明する。負荷分散処理では、入口ノードにおいて、アラーム発生経路と分散先経路とへのトラフィックの送出確率を変更する。例えば、入口ノードは以下の式により、アラーム発生経路と分散先経路との送出確率を決定する。
アラーム発生経路への送出確率（新確率）＝アラーム値×旧確率    ・・・（６）
分散先経路への送出確率（新確率）
＝旧確率＋（１−アラーム値）×アラーム発生経路の旧確率    ・・・（７）
これらの式（６）、式（７）で送出確率を決定することで、アラーム発生経路への送出確率は、アラーム発生経路への確率を減らした分が増やされる。なお、アラーム発生経路と分散先経路以外の経路の送出確率は変更されない。
【０２２５】
例えば、エッジノード２００が［ＡＤ，ＡＣＤ，ＡＥＤ，０．８９］という内容の分散要求を受信した場合を考える。このときアラーム発生経路「ＡＥＤ」の旧送出確率は「１」である。すると、アラーム発生経路への送出確率（新確率）は、「０．８９」となる。他方、分散先経路「ＡＣＤ」への送出確率（新確率）は、「０．１１」となる。エッジノード２００では、送出確率変更部２５０が新たな送出確率を計算し、経路状態情報記憶部２２０に格納されている経路状態情報の送出確率を更新する。また、その後の経路状態情報収集処理によって、経路容量などの値が経路状態情報収集部２３０によって更新される。
【０２２６】
図３７は、送出確率更新後の経路状態情報記憶部の例を示す図である。図３０と比較すると分かるように、経路状態情報記憶部２２０のフローＩＤ「ＡＤ」の経路「ＡＣＤ」の送出確率が「０」から「０．１１」に変更されている。経路「ＡＣＤ」の送出確率が変更されたことで、この経路「ＡＣＤ」におけるフローのトラフィック値が「０」から「０．０３３」に変更されている。またこの経路「ＡＣＤ」にトラフィックが振り分けられるようになったことで、経路空き容量が「０．７」から「０．５９」に変更されている。
【０２２７】
またフローＩＤ「ＡＤ」の経路「ＡＥＤ」の送出確率が「１」から「０．８９」に変更されている。経路「ＡＥＤ」の送出確率が変更されたことで、この経路「ＡＥＤ」におけるフローのトラフィック値が「０．３」から「０．２６７」に変更されている。
【０２２８】
ただし、経路「ＡＥＤ」の経路空き容量は「０」のままである。これは経路「ＡＥＤ」のトラフィック量が「０．２６７」になっても、フロー「ＢＤ」のトラフィック量「０．６」と合算すると、リンク「ＥＤ」のトラフィック量は「０．８６７」となる。このリンク「ＥＤ」のリンク容量×Target値は「０．８」であるため、空き容量の計算結果が負の値となる。そのためリンク「ＥＤ」の空き容量が「０」と判定され、経路空き容量も「０」のままとなる。
【０２２９】
送出確率が更新されると、パケット中継部２１６は、フロー「ＡＤ」のトラフィックを、更新後の送出確率に従って、経路「ＡＥＤ」と経路「ＡＣＤ」とに振り分ける。これにより、経路「ＡＥＤ」に集中していたトラフィックが複数の経路に分散される。
【０２３０】
図３８は、負荷分散の一例を示す図である。図３８の例では、フロー「ＡＤ」の全トラフィック量は「０．３」のままである。このトラフィックが、エッジノード２００において、経路「ＡＥＤ」と経路「ＡＣＤ」とに、それぞれ０．８９：０．１１の割合で振り分けられている。その結果、経路「ＡＥＤ」のトラフィック量が「０．２６７」、経路「ＡＣＤ」のトラフィック量が「０．０３３」となっている。
【０２３１】
なお、図３７、図３８の例は、一回目のアラーム情報に応じた負荷分散結果を示しており、リンク「ＥＤ」のリンク利用率が制御開始閾値「０．７」以下になるまで、アラーム情報が繰り返し出力される。そのアラーム情報に応じて負荷分散によるトラフィックの送出確率の更新も繰り返し実行される。このような送出確率の更新を繰り返すことで、徐々に経路「ＡＥＤ」のトラフィックのうち経路「ＡＣＤ」に迂回させる量が多くなり、経路「ＡＥＤ」のトラフィック量が減少する。
【０２３２】
図３９は、送出確率更新処理の手順の一例を示すフローチャートである。以下、図３９に示す処理をステップ番号に沿って説明する。
［ステップＳ１０１］送出確率変更部２５０は、分散要求を受信する。
【０２３３】
［ステップＳ１０２］送出確率変更部２５０は、分散要求からフローＩＤ、分散先経路、アラーム発生経路、およびアラーム値を抽出する。
［ステップＳ１０３］送出確率変更部２５０は、アラーム発生経路の送出確率を更新する。例えば送出確率変更部２５０は、アラーム発生経路の送出確率を式（６）に基づいて計算する。そして送出確率変更部２５０は、算出した送出確率を、経路状態情報記憶部２２０内のアラーム発生経路の送出確率として設定する。
【０２３４】
［ステップＳ１０４］送出確率変更部２５０は、分散先経路の送出確率を更新する。例えば送出確率変更部２５０は、分散先経路の送出確率を式（７）に基づいて計算する。そして送出確率変更部２５０は、算出した送出確率を、経路状態情報記憶部２２０内の分散先経路の送出確率として設定する。
【０２３５】
このようにして、送出確率を変更し、負荷分散の度合いを調整することができる。
以上説明したように、第２の実施の形態によれば、特定のリンクで輻輳の予兆が検出された場合、そのリンクを通るすべてのトラフィックを分散させるのではなく、経路上のスリープノードが少ない経路に優先的にトラフィックが分散される。これにより、無駄なスリープノードの起動を抑制できる。
【０２３６】
しかも、ＰＩコントローラを用いて、分散先経路へ振り分けるトラフィック量を調整するようにしている。すなわち、トラフィックの集約が段階的に解かれる。そのため、必要以上のスリープノードが起動されることや、無駄な消費電力の増加が避けられる。さらには、分散先経路へのトラフィックが急激に増加し、分散先経路で輻輳が発生することも抑制されている。
【０２３７】
〔その他の応用例〕
上記の第１、第２の実施の形態では、輻輳発生の予兆検出をきっかけとして、トラフィックの分散を行っているが、トラフィックを分散させるきっかけは輻輳発生の予兆検出に限らない。たとえば、いずれかのリンクで障害を検出した場合、そのリンクを通るトラフィックを分散させる場合もある。その場合、例えば輻輳検出部１４０が、輻輳の予兆の検出に加えリンクの障害検出も行えばよい。
【０２３８】
上記の処理機能は、コンピュータによって実現することができる。その場合、各ルータ（エッジノード、中継ノードを含む）が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。
【０２３９】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０２４０】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０２４１】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０２４２】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【０２４３】
以上の実施の形態に開示された技術には、以下の付記に示す技術が含まれる。
（付記１）  他のルータとの間に張られたリンクを経由して、転送順が定義された経路に沿ってネットワークに入力されたトラフィックを転送するルータにおいて、
特定のリンクを経由して転送されるトラフィックの少なくとも一部を前記特定のリンクを経由しない経路で転送させる場合に、各リンクを介して転送されるトラフィックの前記ネットワーク内での経路を記憶する経路記憶手段を参照し、前記特定のリンクを介して転送される１または複数のトラフィックの経路を対象経路とし、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ前記特定のリンクを経由しない経路を分散経路候補とし、分散経路候補のトラフィックを中継するルータの状態を示す状態情報を管理している管理装置から、各分散経路候補の状態情報を取得する状態情報取得手段と、
前記状態情報取得手段が取得した各分散経路候補の状態情報に基づいて、分散経路候補へ前記特定のリンクのトラフィックの一部を流した場合の経路上の他のルータの状態の変化を比較し、状態の変化による消費電力の増加量が少ない経路を優先的に分散先経路として決定する分散先決定手段と、
前記分散先決定手段で決定した前記分散先経路へ、経路上の最初と最後のルータの両方が前記分散先経路と共通である前記対象経路のトラフィックの少なくとも一部を振り分けるように、該対象経路上の最初のルータに指示する分散要求を送信する分散要求手段と、
を有することを特徴とするルータ。
【０２４４】
（付記２）  前記状態情報取得手段は、前記分散経路候補の経路上のルータのうち省電力モードの状態のルータ数を管理装置から取得し、
前記分散先決定手段は、経路上のルータのうち省電力モードの状態のルータ数が少ない分散経路候補を、優先的に分散先経路に決定することを特徴とする付記１記載のルータ。
【０２４５】
（付記３）  前記状態情報取得手段は、前記分散経路候補の経路上のトラフィックが単位データ量増加したときの経路上の各ルータの消費電力増加量を管理装置から取得し、
前記分散先決定手段は、トラフィックが所定量だけ増加したときの経路上の各ルータの消費電力増加量が少ない分散経路候補を、優先的に分散先経路に決定することを特徴とする付記１または付記２のいずれかに記載のルータ。
【０２４６】
（付記４）  前記分散要求手段は、前記分散要求に、前記対象経路から前記分散先経路へ振り分けるトラフィック量の計算指標となるアラーム値を含めることを特徴とする付記１乃至５記載のルータ。
【０２４７】
（付記５）  前記アラーム値は、前記対象経路への現在のトラフィックの送出確率に対する振り分け後の送出確率の比率であることを特徴とする付記４記載のルータ。
（付記６）  他のルータとの間に張られた各リンクのトラフィック量を測定し、輻輳発生の予兆を検出する輻輳予兆検出手段をさらに有し、
前記状態情報取得手段は、前記輻輳予兆検出手段が輻輳発生の予兆を検出したリンクを、前記特定のリンクとすることを特徴とする付記１乃至５のいずれかに記載のルータ。
【０２４８】
（付記７）  前記分散要求手段は、前記輻輳予兆検出手段により輻輳発生の予兆が検出されたリンクの輻輳発生の予兆が継続している間、所定間隔で前記分散要求を繰り返し送信することを特徴とする付記６記載のルータ。
【０２４９】
（付記８）  前記輻輳予兆検出手段は、トラフィック量が所定の閾値を超えたリンクを、輻輳発生の予兆があるリンクとして検出することを特徴とする付記６または付記７記載のルータ。
【０２５０】
（付記９）  前記状態情報取得手段は、対象経路それぞれの最初のルータを前記管理装置と判断し、対象経路それぞれの最初のルータから各分散経路候補の状態情報を取得することを特徴とする付記１乃至８のいずれかに記載のルータ。
【０２５１】
（付記１０）  前記状態情報取得手段は、対象経路それぞれの最初のルータに対して該対象経路の最初と最後のルータが示されたアラーム情報を送信し、該最初のルータから、経路上の最初と最後のルータが該対象経路と共通の分散経路候補、および該分散経路候補の状態情報を取得することを特徴とする付記９記載のルータ。
【０２５２】
（付記１１）  ネットワーク内でトラフィックを転送順が定義された経路に沿って転送する各ルータから、該ルータの状態を示す状態情報を収集し、該ルータの状態情報を、該ルータが転送するトラフィックの経路と対応付けて経路状態記憶手段に格納する状態情報収集手段と、
前記ネットワーク内の複数ルータ間に張られた特定のリンクを経由して転送されるトラフィックの経路を対象経路とし、該対象経路の最初と最後のルータが示されたアラーム情報を受信すると、前記経路状態記憶手段を参照し、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ前記特定のリンクを経由しない経路を分散経路候補とし、該分散経路候補の状態情報を前記アラーム情報の発信元に送信する状態情報通知手段と、
を有することを特徴とする管理装置。
【０２５３】
（付記１２）  前記経路状態記憶手段は、経路上の最初と最後のルータが共通の経路間での各経路へのトラフィックの送出確率を記憶しており、
前記経路状態記憶手段に示される送出確率で、他のネットワークから流入するトラフィックを前記ネットワーク内の経路に分散して転送する中継手段と、
前記対象経路のトラフィックの少なくとも一部を振り分ける分散先経路を指定する分散指示を受け取ると、前記経路状態記憶手段に対して、前記対象経路へのトラフィックの送出確率を減らし、前記分散先経路へのトラフィックの送出確率を増やす更新処理を行う送出確率変更手段と、
をさらに有することを特徴とする付記１１記載の管理装置。
【０２５４】
（付記１３）  前記状態情報収集手段は、他のネットワークから流入するトラフィックを転送する経路上のルータから状態情報を収集することを特徴とする付記１１または付記１２のいずれかに記載の管理装置。
【０２５５】
（付記１４）  前記状態情報収集手段は、トラフィックを転送する経路上のルータのうちの省電力モードとなっているルータの数を状態情報として収集することを特徴とする付記１１乃至１３のいずれかに記載の管理装置。
【０２５６】
（付記１５）  前記状態情報収集手段は、トラフィックを転送する経路上のルータにおける、トラフィックが単位データ量増加したときの消費電力増加量を状態情報として収集することを特徴とする付記１１乃至１４のいずれかに記載の管理装置。
【０２５７】
（付記１６）  他のルータとの間に張られたリンクを経由して、転送順が定義された経路に沿ってネットワークに入力されたトラフィックを転送する処理をコンピュータに実行させるルーティング制御プログラムにおいて、
前記コンピュータに、
特定のリンクを経由して転送されるトラフィックの少なくとも一部を前記特定のリンクを経由しない経路で転送させる場合に、各リンクを介して転送されるトラフィックの前記ネットワーク内での経路を記憶する経路記憶手段を参照し、前記特定のリンクを介して転送される１または複数のトラフィックの経路を対象経路とし、経路上の最初と最後のルータの両方がいずれかの対象経路と共通であり、かつ前記特定のリンクを経由しない経路を分散経路候補とし、分散経路候補のトラフィックを中継するルータの状態を示す状態情報を管理している管理装置から、各分散経路候補の状態情報を取得し、
取得した各分散経路候補の状態情報に基づいて、分散経路候補へ前記特定のリンクのトラフィックの一部を流した場合の経路上の他のルータの状態の変化を比較し、状態の変化による消費電力の増加量が少ない経路を優先的に分散先経路として決定し、
決定した前記分散先経路へ、経路上の最初と最後のルータの両方が前記分散先経路と共通である前記対象経路のトラフィックの少なくとも一部を振り分けるように、該対象経路上の最初のルータに指示する分散要求を送信する、
処理を実行させることを特徴とするルーティング制御プログラム。
【符号の説明】
【０２５８】
１〜６  ルータ
１ａ  中継手段
１ｂ  輻輳予兆検出手段
１ｃ  経路記憶手段
１ｄ  状態情報取得手段
１ｅ  分散先決定手段
１ｆ  分散要求手段
２ａ  経路状態記憶手段
２ｂ  中継手段
２ｃ  状態情報収集手段
２ｄ  状態情報通知手段
２ｅ  送出確率変更手段
【図１】
0005413238.tif 000002
【図２】
0005413238.tif 000003
【図３】
0005413238.tif 000004
【図４】
0005413238.tif 000005
【図５】
0005413238.tif 000006
【図６】
0005413238.tif 000007
【図７】
0005413238.tif 000008
【図８】
0005413238.tif 000009
【図９】
0005413238.tif 000010
【図１０】
0005413238.tif 000011
【図１１】
0005413238.tif 000012
【図１２】
0005413238.tif 000013
【図１３】
0005413238.tif 000014
【図１４】
0005413238.tif 000015
【図１５】
0005413238.tif 000016
【図１６】
0005413238.tif 000017
【図１７】
0005413238.tif 000018
【図１８】
0005413238.tif 000019
【図１９】
0005413238.tif 000020
【図２０】
0005413238.tif 000021
【図２１】
0005413238.tif 000022
【図２２】
0005413238.tif 000023
【図２３】
0005413238.tif 000024
【図２４】
0005413238.tif 000025
【図２５】
0005413238.tif 000026
【図２６】
0005413238.tif 000027
【図２７】
0005413238.tif 000028
【図２８】
0005413238.tif 000029
【図２９】
0005413238.tif 000030
【図３０】
0005413238.tif 000031
【図３１】
0005413238.tif 000032
【図３２】
0005413238.tif 000033
【図３３】
0005413238.tif 000034
【図３４】
0005413238.tif 000035
【図３５】
0005413238.tif 000036
【図３６】
0005413238.tif 000037
【図３７】
0005413238.tif 000038
【図３８】
0005413238.tif 000039
【図３９】
0005413238.tif 000040