(57)【特許請求の範囲】
【請求項１】
フロー毎に定められたアクションに従って各フローに対する処理を行うノードを複数備え、
各ノードに対して、個々のフローに対するアクションを通知することにより、ノード間のリンクの帯域を制御する帯域制御装置を備え、
各ノードは、自ノードのリンクにおけるフロー毎の使用帯域を含む情報を帯域制御装置に送信し、
帯域制御装置は、
フローの経路を計算する経路計算手段と、
経路計算手段によって計算された経路上の各ノードに、前記フローに関するアクションを通知する通知手段と、
個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する未使用帯域計算手段と、
未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定する除外対象リンク決定手段と、
第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定するフロー再制御対象リンク決定手段とを備え、
経路計算手段は、除外対象リンクを除外して、フローの経路を計算し、
フロー再制御対象リンク決定手段は、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を経路計算手段に再計算させ、
未使用帯域計算手段は、経路計算手段がフローの経路を計算したときに、前記フローに関連するリンクの未使用帯域を再計算する
ことを特徴とする帯域制御システム。
【請求項２】
フロー再制御対象リンク決定手段は、フロー再制御対象リンクを通過するフローのうち、予め定められた条件に合致するフローの経路を経路計算手段に再計算させる
請求項１に記載の帯域制御システム。
【請求項３】
未使用帯域計算手段は、所定の期間以上生存しているフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する
請求項１または請求項２に記載の帯域制御システム。
【請求項４】
各ノードは、自ノードのリンクにおける障害発生時に、障害が発生したリンクの情報を帯域制御装置に送信し、
帯域制御装置の経路計算手段は、障害が発生したリンクを通過するフローの経路を順次再計算する
請求項１から請求項３のうちのいずれか１項に記載の帯域制御システム。
【請求項５】
フロー毎に定められたアクションに従って各フローに対する処理を行うノード間のリンクの帯域を制御する帯域制御装置であって、
フローの経路を計算する経路計算手段と、
経路計算手段によって計算された経路上の各ノードに、前記フローに関するアクションを通知する通知手段と、
個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する未使用帯域計算手段と、
未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定する除外対象リンク決定手段と、
第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定するフロー再制御対象リンク決定手段とを備え、
経路計算手段は、除外対象リンクを除外して、フローの経路を計算し、
フロー再制御対象リンク決定手段は、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を経路計算手段に再計算させ、
未使用帯域計算手段は、経路計算手段がフローの経路を計算したときに、前記フローに関連するリンクの未使用帯域を再計算する
ことを特徴とする帯域制御装置。
【請求項６】
フロー再制御対象リンク決定手段は、フロー再制御対象リンクを通過するフローのうち、予め定められた条件に合致するフローの経路を経路計算手段に再計算させる
請求項５に記載の帯域制御装置。
【請求項７】
フロー毎に定められたアクションに従って各フローに対する処理を行う複数のノードが、自ノードのリンクにおけるフロー毎の使用帯域を含む情報を帯域制御装置に送信し、
前記帯域制御装置が、
フローの経路を計算し、
計算した経路上の各ノードに、前記フローに関するアクションを通知し、
個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算し、
未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定し、
第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定し、
経路計算時に、除外対象リンクを除外して、フローの経路を計算し、
フロー再制御対象リンクを決定したときに、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を再計算し、
フローの経路を計算したときに、前記フローに関連するリンクの未使用帯域を再計算する
ことを特徴とする帯域制御方法。
【請求項８】
帯域制御装置が、フロー再制御対象リンクを決定したときに、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローのうち、予め定められた条件に合致するフローの経路を再計算する
請求項７に記載の帯域制御方法。
【請求項９】
フロー毎に定められたアクションに従って各フローに対する処理を行うノード間のリンクの帯域を制御するコンピュータに搭載される帯域制御プログラムであって、
コンピュータに、
フローの経路を計算する経路計算処理、
経路計算処理で計算された経路上の各ノードに、前記フローに関するアクションを通知する通知処理、
個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する未使用帯域計算処理、
未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定する除外対象リンク決定処理、および、
第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定するフロー再制御対象リンク決定処理を実行させ、
経路計算処理で、除外対象リンクを除外して、フローの経路を計算させ、
フロー再制御対象リンク決定処理でフロー再制御対象リンクを決定した場合に、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローを対象に経路計算処理を実行させ、
経路計算処理によりフローの経路を計算させた場合に、前記フローに関連するリンクの未使用帯域を再計算させる
ための帯域制御プログラム。
【請求項１０】
コンピュータに、
フロー再制御対象リンク決定処理でフロー再制御対象リンクを決定した場合に、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローのうち、予め定められた条件に合致するフローの経路を再計算させる
請求項９に記載の帯域制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、帯域制御システム、帯域制御装置、帯域制御方法および帯域制御プログラムに関し、特に、オープンフローにおいてパケットを転送するパケット転送装置間のリンクにおける帯域を制御する帯域制御システム、帯域制御装置、帯域制御方法および帯域制御プログラムに関する。
【背景技術】
【０００２】
一般に、通信においては、フロー毎に予め一定の帯域を割り当てる。
【０００３】
また、パケットを転送するスイッチ（パケット転送装置）と、スイッチのパケット転送を制御することにより通信経路を制御するコントローラとを備える通信システムが知られている。コントローラがパケット転送装置を制御するために用いるプロトコルは、オープンフロー（OpenFlow）と呼ばれる。オープンフローに関する情報は、例えば、非特許文献１に記載されている。
【０００４】
オープンフローでは、未設定のフローをパケット転送装置が受信したときに、そのフローに関する情報をコントローラに送信する。そして、コントローラは、そのフローに関する経路を決定し、経路上の各パケット転送装置に対して、そのフローに関するアクションを設定する。この結果、各パケット転送装置は、受信したフローに対し、設定されたアクション（例えば、他のパケット転送装置への転送）を行う。コントローラは、各パケット転送装置に対するフロー毎の設定をまとめて管理する。
【０００５】
ここで、フローとは、レイヤ１〜４の任意の条件で識別されるパケットのことである。例えば、宛先ＭＡＣアドレスがＡであり、送信元ＩＰアドレスがＢであり、宛先ポート番号がＣとなっているパケットをフローＸとする。宛先ＭＡＣアドレス＝Ａ、送信元ＩＰアドレス＝Ｂ、宛先ポート番号＝Ｃとなっているパケットは、フローＸと識別される。フローＸとは逆向きに送信されるパケットは、送信元および宛先が逆転するので、フローＸとは別のフローとして識別される。
【０００６】
また、通信のＱｏＳ（Quality of Service）に関連する技術が種々提案されている（例えば、特許文献１，２参照）。特許文献１には、ユーザからのＱｏＳ保証の要求に応じて、ルータ間のリンクの帯域幅の確保をルータに要求するＱｏＳ情報収集管理端末装置が記載されている。また、特許文献２には、ＩＰネットワーク全体の負荷状況を考慮したネットワークトポロジー情報を受信し、そのネットワークトポロジー情報を用いて、送り先ネットワークまでの最適経路を計算し、その経路上に配置されている他のＩＰルーティング装置に対してパスを設定するＩＰルーティング装置が記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００１−３４５８０８号公報（段落００３５）
【特許文献２】特開２００２−２４７０８７号公報（段落００１５）
【非特許文献】
【０００８】
【非特許文献１】“ＯｐｅｎＦｌｏｗ”、２０１０年１月３１日、［平成２２年２月３日検索］、インターネット<http://www.openflowswitch.org/>
【発明の概要】
【発明が解決しようとする課題】
【０００９】
フロー毎に予め一定の帯域を割り当てて通信を行う一般的な通信方法では、フローの使用帯域を予測して帯域を割り当てている。割り当てられる帯域は予測された帯域であり、そのため、割り当て分の全ての帯域が使用されるとは限らない。通信に使用する経路も、予め静的または動的に決定された経路であり、決定後に経路が変更されることは基本的にない。このため、経路上のリンクに未使用のリソースが存在することになったり、未使用のリンクが存在することになってしまったりする。従って、フロー毎に予め一定の帯域を割り当てて通信を行う方法では、ネットワーク内のリソースが効率的に使用できていなかった。
【００１０】
また、特許文献１に記載された技術では、ユーザからのＱｏＳ保証の要求に応じた帯域幅を確保する。この場合にも、確保した帯域が全て効率的に使用されるとは限らない。
【００１１】
また、特許文献２に記載されたＩＰルーティング装置は、負荷状態に応じて、ＩＰレイヤにおける最適経路を計算し、その経路上に配置されている他のＩＰルーティング装置に対してパスを設定する。この技術によれば、宛先ＩＰアドレスが同じであれば、同じ経路でパケット転送が行われることになる。よって、種々のレイヤの条件で定まるフロー毎に最適な経路を定めることはできない。
【００１２】
また、近年では、ネットワークに対して、高品質保証のニーズが高まっている。
【００１３】
そこで、本発明は、各フローに対して、フローが通過できる帯域が確保されたエンドツーエンド（End to End）の経路を定めるようにしつつ、ネットワーク全体として、ネットワーク内の各リンクのリソース（帯域）を効率的に使用できるようにすることができる帯域制御システム、帯域制御装置、帯域制御方法および帯域制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明による帯域制御システムは、フロー毎に定められたアクションに従って各フローに対する処理を行うノードを複数備え、各ノードに対して、個々のフローに対するアクションを通知することにより、ノード間のリンクの帯域を制御する帯域制御装置を備え、各ノードが、自ノードのリンクにおけるフロー毎の使用帯域を含む情報を帯域制御装置に送信し、帯域制御装置が、フローの経路を計算する経路計算手段と、経路計算手段によって計算された経路上の各ノードに、フローに関するアクションを通知する通知手段と、個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する未使用帯域計算手段と、未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定する除外対象リンク決定手段と、第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定するフロー再制御対象リンク決定手段とを備え、経路計算手段が、除外対象リンクを除外して、フローの経路を計算し、フロー再制御対象リンク決定手段が、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を経路計算手段に再計算させ、未使用帯域計算手段が、経路計算手段がフローの経路を計算したときに、そのフローに関連するリンクの未使用帯域を再計算することを特徴とする。
【００１５】
また、本発明による帯域制御装置は、フロー毎に定められたアクションに従って各フローに対する処理を行うノード間のリンクの帯域を制御する帯域制御装置であって、フローの経路を計算する経路計算手段と、経路計算手段によって計算された経路上の各ノードに、フローに関するアクションを通知する通知手段と、個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する未使用帯域計算手段と、未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定する除外対象リンク決定手段と、第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定するフロー再制御対象リンク決定手段とを備え、経路計算手段は、除外対象リンクを除外して、フローの経路を計算し、フロー再制御対象リンク決定手段は、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を経路計算手段に再計算させ、未使用帯域計算手段は、経路計算手段がフローの経路を計算したときに、そのフローに関連するリンクの未使用帯域を再計算することを特徴とする。
【００１６】
また、本発明による帯域制御方法は、フロー毎に定められたアクションに従って各フローに対する処理を行う複数のノードが、自ノードのリンクにおけるフロー毎の使用帯域を含む情報を帯域制御装置に送信し、帯域制御装置が、フローの経路を計算し、計算した経路上の各ノードに、フローに関するアクションを通知し、個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算し、未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定し、第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定し、経路計算時に、除外対象リンクを除外して、フローの経路を計算し、フロー再制御対象リンクを決定したときに、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を再計算し、フローの経路を計算したときに、そのフローに関連するリンクの未使用帯域を再計算することを特徴とする。
【００１７】
また、本発明による帯域制御プログラムは、フロー毎に定められたアクションに従って各フローに対する処理を行うノード間のリンクの帯域を制御するコンピュータに搭載される帯域制御プログラムであって、コンピュータに、フローの経路を計算する経路計算処理、経路計算処理で計算された経路上の各ノードに、フローに関するアクションを通知する通知処理、個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域を計算する未使用帯域計算処理、未使用帯域の値が各リンクの未使用帯域の平均値から第１定数を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンクに決定する除外対象リンク決定処理、および、第１定数より大きな第２定数を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定するフロー再制御対象リンク決定処理を実行させ、経路計算処理で、除外対象リンクを除外して、フローの経路を計算させ、フロー再制御対象リンク決定処理でフロー再制御対象リンクを決定した場合に、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローを対象に経路計算処理を実行させ、経路計算処理によりフローの経路を計算させた場合に、そのフローに関連するリンクの未使用帯域を再計算させることを特徴とする。
【発明の効果】
【００１８】
本発明によれば、各フローに対して、フローが通過できる帯域が確保されたエンドツーエンドの経路を定めるようにしつつ、ネットワーク全体として、ネットワーク内の各リンクの帯域を効率的に使用できる。
【図面の簡単な説明】
【００１９】
【図１】本発明の帯域制御システムの例を示すブロック図である。
【図２】本発明の帯域制御装置の構成例を示すブロック図である。
【図３】経路計算の例を示す説明図である。
【図４】新規フロー発生時のコントローラの処理経過の例を示すフローチャートである。
【図５】図４に示すステップＳ５の例を示すフローチャートである。
【図６】障害が発生したリンクの通知を受けたコントローラの処理経過の例を示すフローチャートである。
【図７】各リンクのＬＲの例を示す模式図である。
【図８】経路計算後のＬＲの例を示す模式図である。
【図９】実際の使用帯域が反映されたＬＲの例を示す模式図である。
【図１０】余剰フローの経路の再計算後のＬＲの例を示す模式図である。
【図１１】本発明の帯域制御システムの最小構成の例を示すブロック図である。
【図１２】本発明の帯域制御装置の最小構成の例を示すブロック図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態を図面を参照して説明する。
図１は、本発明の帯域制御システムの例を示すブロック図である。本発明の帯域制御システムは、オープンフローネットワーク２０に属する複数のパケット転送装置２と、コントローラ１とを備える。コントローラ１は、フローに応じたアクションを各パケット転送装置２に設定することにより、オープンフローネットワーク２０内における各フローの経路を制御する。以下の説明では、パケット転送装置２を、単にノード２と記す。
【００２１】
ノード２同士は、リンク３を介して接続され、オープンフローネットワーク２０を形成する。図１では、９個のノードを図示しているが、ノード２の数や、どのノード同士を接続させるかは特に限定されない。各ノード２は、オープンフローが適用されるコントローラ１によって制御される。また、オープンフローが適用されないネットワーク（以下、レガシーネットワークと記す。）３０に接続されるノード２が存在する。
【００２２】
コントローラ１は、各フローの帯域が確保され、また、各リンクにおける残存リソース（未使用帯域）が平均化されるように、フローの経路を制御する。従って、コントローラ１は、各リンクの帯域を制御する帯域制御装置と称することもできる。
【００２３】
各ノード２は、アクションが設定されていない新規フローを受信した場合、その新規フローの識別情報（例えば、送信元、送信先のアドレスやポート番号等）、および新規フローの起点および終点を表す情報（例えば、送信元および送信先のアドレス）を、コントローラ１に送信する。コントローラ１は、経路の起点および終点を表す情報と、オープンフローネットワーク２０のトポロジー情報とから、新規フローの経路を決定し、その経路上の各ノードに対して、新規フローの識別情報と、その新規フローに対するアクションとを通知する。コントローラ１は、例えば、「経路上の次のノードにフローを転送する」というアクションを、経路上のノード毎に定め、経路上のノード毎に新規フローの識別情報およびアクションを通知（送信）すればよい。
【００２４】
新規フローの識別情報およびアクションを通知された各ノードは、そのフローの識別情報およびアクションを対応付けて記憶し、その後は、新規フローをそのアクションに従って、次のノードに転送していく。この結果、フローは、コントローラ１が決定した経路に沿って転送されていく。
【００２５】
図２は、本発明の帯域制御装置（コントローラ１）の構成例を示すブロック図である。コントローラ１は、情報取得部１１と、ネットワーク状況記憶部１２と、リンク状態計算部１３と、経路計算部１７と、経路通知部１８と、条件記憶部１９とを備える。
【００２６】
情報取得部１１は、各ノード２から諸情報を取得し、取得した情報から、オープンフローネットワーク２０の状況を認識する。そして、認識結果をネットワーク状況記憶部２０に記憶させる。情報取得部１１は、例えば、オープンフローネットワーク２０の状況として、ネットワークトポロジー情報および使用状況を認識する。ネットワークトポロジー情報には、例えば、各ノード２における各ポートがリンクアップしているかリンクダウンしているかを示すリンクアップ／ダウン情報、各リンクの通信速度やduplex（全二重、半二重等）を示すspeed/duplex情報、Ｌ２／Ｌ３におけるネットワークトポロジーを表す情報（Ｌ２／Ｌ３トポロジー情報）、レガシーネットワーク３０との境界となるノードを表す情報、その境界のノードが認識しているルーティング情報等が含まれる。使用状況に関する情報には、例えば、各リンクにおける個々のフローの使用帯域が含まれる。
【００２７】
ネットワーク状況記憶部２０は、情報取得部１１が認識したオープンフローネットワーク２０の状況を表す情報（例えば、上記のネットワークトポロジー情報および使用状況）を記憶する記憶装置である。また、ネットワーク状況記憶部２０は、経路計算部１７が計算する各フローの経路も、オープンフローネットワークの使用状況を示す情報として記憶する。
【００２８】
リンク状態計算部１３は、ネットワーク状況記憶部２０に記憶された情報を参照し、各リンクの残存リソースを計算し、経路の計算時に選択すべきでないリンク（以下、ボトルネックリンクと記す。）、および、他のリンクと比較して残存リソースが少なくなっているために、通過するフローの一部を他のリンクに振り分けるべきリンク（以下、フロー再制御対象リンクと記す。）を決定する。また、リンク状態計算部１３は、経路計算部１７がフローの経路を計算したときにも、リンクの残存リソースを再計算し、ボトルネックリンクを決定し直す。さらに、リンク状態計算部１３は、フロー再制御対象リンクが存在する場合に、フロー再制御対象リンクを通過するフローに関して経路計算部１７に経路を再計算させた場合にも、リンクの残存リソースを計算する。
【００２９】
リンク状態計算部１３は、各リンクの残存リソース（以下、ＬＲと記す。）を計算するＬＲ計算部１４と、ボトルネックリンクを決定するボトルネックリンク決定部１５と、フロー再制御対象リンクを決定するフロー再制御対象リンク設定部１６とを含む。
【００３０】
ＬＲ計算部１４は、ＬＲを計算しようとするリンクにおいて使用可能な最大帯域から、そのリンクで使用されている各フローの帯域の合計を減算することによって、ＬＲを計算する。すなわち、ＬＲ計算部１４は、以下に示す式（１）の計算を行うことによって、ＬＲを求める。
【００３１】
ＬＲ（Ｌｉ）＝ＭａｘＬｉ−ＵｓｅＬｉ          式（１）
【００３２】
式（１）において、Ｌｉは、ＬＲを計算するリンクとして着目しているリンクである。ＬＲ（Ｌｉ）は、リンクＬｉの残存リソースである。ＭａｘＬｉは、リンクＬｉで使用可能な最大帯域である。ＵｓｅＬｉは、リンクＬｉにおいて使用されている各フローの帯域の合計である。なお、ＭａｘＬｉの値は、例えば、予め定めておき、ネットワーク状況記憶部１２に記憶させておけばよい。ＬＲ計算部１４は、以下に示す式（２）の計算によってＵｓｅＬｉを算出すればよい。
【００３３】
【数１】
0005493965.tif 000002
【００３４】
式（２）において、ｕｊは、リンクＬｉを通過するフローの一定期間における使用帯域の平均値である。ただし、ＬＲ計算部１４は、予め定めた所定の期間以上生存しているフロー（long-lived flow ）のみを対象として、使用帯域の平均値ｕｊの合計を計算し、ＵｓｅＬｉを算出する。式（２）において、Ｊは、リンクＬｉを通過するlong-lived flow の数である。このようにlong-lived flow を対象としてＵｓｅＬｉを算出することによって、瞬間的に生じたフローの使用帯域の影響で不適切なＬＲが算出されることを防ぐことができる。
【００３５】
ＬＲ計算部１４は、ネットワーク状況記憶部１２に記憶された情報を参照して、ノード同士を結ぶリンク毎に、式（２）および式（１）の計算によりＬＲを算出する。
【００３６】
また、ＬＲ計算部１４は、経路計算部１７が、新規のフローまたは既存のフローに関して経路を計算した場合、新たに計算された経路上のリンクに関して、ＵｓｅＬｉに所定の固定値を加算し、ＬＲを再計算する。この所定の固定値は、新たに計算された経路をフローが通過することによる使用帯域の増加量の見込み値である。この結果、ＬＲは、この固定値分減少することになる。
【００３７】
また、ＬＲ計算部１４は、フロー再制御対象リンクを通過するフローに関して、経路計算部１７に経路を再計算させた場合に、そのフロー再制御対象リンクに関して、ＵｓｅＬｉから、そのフローの使用帯域を減算し、ＬＲを再計算する。この結果、フロー再制御対象リンクのＬＲは、経路を再計算したフローの使用帯域分増加することになる。
【００３８】
また、ＬＲ計算部１４は、リンクのＬＲを再計算したときに、オープンフローネットワーク２０内の各リンクのＬＲの平均値を計算する。各リンクにおけるＬＲの平均値を、以下、ＬＲＡと記す。
【００３９】
ボトルネックリンク決定部１５は、ＬＲ計算部１４が計算したＬＲＡを用いて、ボトルネックリンクを決定する。ボトルネックリンクは、経路の計算時に除外すべきリンクであり、除外対象リンクと称することもできる。ボトルネックリンク決定部１５は、ＬＲの値が、ＬＲＡから一定値Ｘを減算した値以下となっているリンクをボトルネックとして決定する。すなわち、ボトルネックリンク決定部１５は、ＬＲが（ＬＲＡ−Ｘ）以下となっているリンクを、ボトルネックリンクと定める。ボトルネックリンクのＬＲをＬＲ（Ｌｂｏｔｔｌｅｎｅｃｋ）とすると、以下に示す式（３）が成立する。
【００４０】
ＬＲ（Ｌｂｏｔｔｌｅｎｅｃｋ）≦ＬＲＡ−Ｘ          式（３）
【００４１】
フロー再制御対象リンク決定部１６は、ＬＲ計算部１４が計算したＬＲＡを用いて、フロー再制御対象リンクを決定する。フロー再制御対象リンクは、他のリンクと比較して残存リソースが少なくなっているために、そのリンクを経路として通過するフローの一部を他のリンクに振り分けるべきリンクである。フロー再制御対象リンク決定部１６は、ＬＲの値が、ＬＲＡから一定値Ｙを減算した値以下となっているリンクを、フロー再制御対象リンクとして決定する。すなわち、フロー再制御対象リンク決定部１６は、ＬＡが（ＬＲＡ−Ｙ）以下となっているリンクを、フロー再制御対象リンクと定める。ただし、フロー再制御対象リンクの決定時に用いる一定値Ｙは、ボトルネックリンクの決定時に用いる一定値Ｘよりも大きな値である。フロー再制御対象リンクのＬＲをＬＲ（ＬＲｅ−Ｃｏｎｔｒｏｌ）とすると、以下に示す式（４）が成立する。
【００４２】
ＬＲ（ＬＲｅ−Ｃｏｎｔｒｏｌ）≦ＬＲＡ−Ｙ          式（４）
【００４３】
Ｙ＞Ｘであるので、フロー再制御対象リンクは、ボトルネックリンクにも該当する。フロー再制御対象リンクは、ボトルネックリンクの中でも特にＬＲが少なくなっているリンクであるということができる。
【００４４】
フロー再制御対象リンク決定部１６は、フロー再制御対象リンクを決定すると、そのフロー再制御対象リンクを経路とするフローの中から、「重要でない」という条件と、「使用帯域が多い」という条件とを満たすフローを決定する。この２つの条件を満たすフローを余剰フローと記す。フロー再制御対象リンク決定部１６は、経路計算部１７に対して、余剰フローの経路の再計算を要求する。フロー再制御対象リンク決定部１６は、経路の再計算後にＬＲ計算部１４によって計算されるＬＲおよびＬＲＡに基づいて、フロー再制御対象リンクと定めたリンクが、未だフロー再制御対象リンクに該当しているか否かを判定する。フロー再制御対象リンク決定部１６は、フロー再制御対象リンクと定めたリンクがフロー再制御対象リンクに該当しなくなるまで、余剰フローを順次選択して、選択した余剰経路の経路を経路計算部１７に再計算させる。
【００４５】
条件記憶部１９は、フローが重要でないということを表す条件や、フローの使用帯域が多いということを表す条件を記憶する記憶装置である。フロー再制御対象リンク決定部１６は、フロー再制御対象リンクを経路として通過する各フローと、条件記憶部１９に記憶された条件とを照合し、条件に合致するリンクを余剰フローとして決定する。フローが重要でないということを表す条件は、予めネットワーク管理者が任意に定めておけばよい。例えば、「ＵＤＰ（User Data Protocol）を使用したフローであること」、「送信元ＩＰアドレスが所定のアドレスであること」等の条件を、「重要でない」フローの条件として予め条件記憶部１９に記憶させておけばよい。フローの使用帯域が多いということを表す条件は、例えば、予め閾値としてネットワーク管理者が定め、条件記憶部１９に記憶させておけばよい。フロー再制御対象リンク決定部１６は、フローの使用帯域がこの閾値以上であれば、フローの使用帯域が多いと判定すればよい。フロー再制御対象リンク決定部１６は、フローが重要でないという条件と、フローの使用帯域が多いという条件の二つの条件を満たすフローを余剰フローとする。なお、条件の定め方は上記の例に限定されない。例えば、フローが重要であるという条件を定めておき、フロー再制御対象リンク決定部１６は、その条件に合致しないフローを「重要でないフロー」と判定してもよい。
【００４６】
経路計算部１７は、ノード２（図１参照）から、新規フローの通知（すなわち、新規フローの識別情報、および、新規フローの起点、終点を表す情報の通知）を受けた場合、オープンフローネットワーク２０内における新規フローの経路を計算する。経路計算部１７は、オープンフローネットワーク２０内の各リンクからボトルネックリンクを除外して、例えば、ＳＰＦ（shortest Path Fast）アルゴリズムによって最短経路を計算すればよい。ここではＳＰＦを例示したが、他のアルゴリズムで経路を計算してもよい。ボトルネックリンクは、経路計算の対象から除外されるので、経路計算部１７に計算された経路にボトルネックリンクが含まれることはない。
【００４７】
また、経路計算部１７は、フロー再制御対象リンク特定部１６から余剰フローの経路計算を要求された場合に、その余剰フローの経路を再計算する。この場合にも、経路計算部１７は、オープンフローネットワーク２０内の各リンクからボトルネックリンクを除外して、例えば、ＳＰＦ（shortest Path Fast）アルゴリズムによって最短経路を計算すればよい。
【００４８】
図３は、経路計算部１７による経路計算の例を示す説明図である。図３に示す例では、リンク３ａ〜３ｂがボトルネックリンクであり、リンク３ａは、フロー再制御対象リンクでもある。例えば、レガシーネットワーク３０ａからレガシーネットワーク３０ｂに送信されるパケットのフローについて経路を計算する場合、経路計算部１７は、起点を含むレガシーネットワーク３０ａに接続されるノード２ａと、終点を含むレガシーネットワーク３０ｂに特定されるノード２ｂとを特定し、ボトルネックリンク３ａ〜３ｃを除外して、ノード２ａからノード２ｂまでの最短となる経路（例えば、図３に示す経路４ａ）を計算する。同様に、例えば、レガシーネットワーク３０ｂからレガシーネットワーク３０ｂに送信されるパケットのフローについて経路を計算する場合にも、経路計算部１７は、起点を含むレガシーネットワーク３０ｂに特定されるノード２ｂと、終点を含むレガシーネットワーク３０ａに接続されるノード２ａとを特定し、ボトルネックリンク３ａ〜３ｃを除外して、ノード２ｂからノード２ａまでの最短となる経路（例えば、図３に示す経路４ｂ）を計算する。
【００４９】
経路通知部１８は、経路計算部１７が新たにフローの経路を計算したときに、その経路上の各ノードについてアクションを定め、そのフローの識別情報およびアクションを経路上の各ノードに通知（送信）する。フローの識別情報およびアクションを受信した各ノードは、そのフローの識別情報およびアクションを記憶し、以後、その識別情報によって特定されるフローを、そのアクションに従って処理する。
【００５０】
情報取得部１１、リンク状態計算部１３（ＬＲ計算部１４、ボトルネック決定部１５、フロー再制御対象リンク決定部１６）、経路計算部１７および経路通知部１８は、例えば、帯域制御プログラムに従って動作するコンピュータのＣＰＵによって実現される。この場合、例えば、コンピュータのプログラム記憶装置（図示略）が帯域制御プログラムを記憶し、ＣＰＵがそのプログラムを読み込み、そのプログラムに従って、情報取得部１１、リンク状態計算部１３、経路計算部１７および経路通知部１８として動作する。また、各構成部が、それぞれ別のユニットで実現されていてもよい。
【００５１】
次に、動作について説明する。
まず、コントローラ１がオープンフローネットワーク２０の状況を記憶する動作について説明する。例えば、各ノード２がそれぞれ定期的にコントローラ１に対して情報を送信する。各ノードは、自ノードにおける各ポートがリンクアップしているかリンクダウンしているかを示すリンクアップ／ダウン情報、自ノードの各リンクの通信速度やduplexを示すspeed/duplex情報、自ノードの各リンクにおけるフロー毎の使用帯域を、コントローラ１に送信する。また、各ノードは、自ノードに関する他のノードとの接続状況を表す情報もコントローラ１に送信する。
【００５２】
コントローラ１の情報取得部１１は、各ノードから受信したリンクアップ／ダウン情報、speed/duplex情報、各リンクにおけるフロー毎の使用帯域の情報をネットワーク状況記憶部１２に記憶させる。また、情報取得部１１は、各ノードから受信した他のノードとの接続状況を表す情報に基づいて、Ｌ２／Ｌ３トポロジー情報を作成したり、レガシーネットワークとオープンフローネットワークとの境界となっているノードを特定し、そのノードがどのレガシーネットワークに接続されているかを認識したりして、その認識結果やＬ２／Ｌ３トポロジー情報をネットワーク状況記憶部１２に記憶させる。
【００５３】
各ノード２は定期的に各情報をコントローラ１に送信し、コントローラ１の情報取得部１１は、その情報を受信すると、その内容に応じて、ネットワーク状況記憶部１２に記憶させた情報を更新する。従って、オープンフローネットワーク２０の状況が変化しても、ネットワーク状況記憶部１２が記憶する情報にその変化が反映される。
【００５４】
次に、ノード２が新規フローを検出し、その新規フローを検出したことをコントローラ１に通知した場合のコントローラ１の動作について説明する。図４は、この場合のコントローラの処理経過の例を示すフローチャートである。なお、ここでは、既にボトルネックリンクが決定されているものとして説明する。
【００５５】
経路計算部１７は、ノード２（図１参照）から新規フローの通知（すなわち、新規フローの識別情報、および、新規フローの起点、終点を表す情報の通知）を受信すると、オープンフローネットワーク２０内における新規フローの経路を計算する（ステップＳ１）。このとき、経路計算部１７は、ボトルネックリンクを除外して、例えばＳＰＦで経路を計算する。また、ボトルネックリンクが存在しなければ、経路計算部１７は、オープンフローネットワーク２０内の各リンクからリンクを除外せずに、例えばＳＰＦで経路を計算すればよい。経路計算部１７は、フローの経路を新たに計算すると、フローの経路をネットワーク状況記憶部１２に記憶させる。この結果、ネットワーク状況記憶部１２は、フロー毎の経路の情報も記憶する。
【００５６】
なお、ステップＳ１において、経路計算部１７は、起点を含むレガシーネットワークとオープンフローネットワークとの境界となるノード（例えば、図３に示すノード２ａ）と、終点を含むレガシーネットワークとオープンフローネットワークとの境界となるノード（例えば、図３に示すノード２ｂ）とを、ネットワーク状況記憶部１２に記憶された情報に基づいて特定し、前者のノードから後者のノードまでの経路を計算すればよい。
【００５７】
また、ステップＳ１において経路計算部１７が経路を計算すると、経路通知部１８は、その経路上の各ノードについてアクションを定め、そのフローの識別情報およびアクションを経路上の各ノードに通知する。各ノードは、この通知に従って、そのフローを次のノードに転送する。この結果、新規フローは、決定された経路に沿って転送されることになる。
【００５８】
ステップＳ１で経路計算部１７が新規フローの経路を決定すると、ＬＲ計算部１４は、その新規フローの経路上の各リンクに関して、各フローの使用帯域の合計ＵｓｅＬｉに、新たに経路を決定したフロー分の使用帯域を加算する（ステップＳ２）。ステップＳ２で加算される使用帯域は、新たに経路を決定したフローの使用帯域の見込み値として予め定められている固定値である。また、ＬＲ計算部１４は、新たに計算された経路上のリンクに関して、新規フローの使用帯域の値が、上記の固定値である旨を、ネットワーク状況記憶部１２に記憶させる。
【００５９】
次に、ＬＲ計算部１４は、ステップＳ２でＵｓｅＬｉを更新したリンクのＬＲを式（１）の計算によって再計算し、さらに、オープンフローネットワーク内の各リンクのＬＲの平均値ＬＲＡを再計算する。そして、ボトルネックリンク決定部１５は、ボトルネックリンクを再決定する。すなわち、ボトルネックリンク決定部１５は、ＬＲが（ＬＲＡ−Ｘ）以下となっているリンクを、ボトルネックリンクと定める（ステップＳ３）。
【００６０】
ステップＳ３で再決定されたボトルネックリンクは、新たに経路が決定されたフローの使用帯域を、予め定めた値（固定値）と仮定した場合のボトルネックリンクである。ステップＳ３の直後にコントローラ１が新規フローの通知を受信したならば、このボトルネックリンクを除外して経路を計算すればよい。
【００６１】
また、ステップＳ１で定められた経路に沿ってフローが実際に転送されると、その経路上の各ノードは、定期的にコントローラ１に送信する情報に、そのフローの実際の使用帯域を送信する。コントローラ１の情報取得部１１は、定期的に各ノードから諸情報を受信すると、その内容に応じて、ネットワーク状況記憶部１２に記憶された内容を更新する。この結果、ステップＳ１で経路が決定されたフローの使用帯域は、見込み値（固定値）から、実際の値に更新される。情報取得部１１が、各ノードから定期的に情報を受信して、各リンクにおけるフロー毎の使用帯域の情報等を更新すると、ＬＲ計算部１４は、更新後の情報に基づいて、オープンフローネットワーク内のリンク毎に、式（２）および式（１）の計算を行い、ＬＲを再度算出する。さらに、ＬＲ計算部１４は、各リンクのＬＲの平均値ＬＲＡも再計算する（ステップＳ４）。さらにステップＳ４では、ボトルネックリンク決定部１５が、ＬＲが（ＬＲＡ−Ｘ）以下となっているリンクを、ボトルネックリンクと定める。また、フロー再制御対象リンク決定部１６が、ＬＲが（ＬＲＡ−Ｙ）以下となっているリンクを、フロー再制御対象リンクと定める。
【００６２】
ステップＳ４の後にコントローラ１が新規フローの通知を受信したならば、このボトルネックリンクを除外して経路を計算すればよい。
【００６３】
ステップＳ４の後、フロー再制御対象リンク決定部１６は、フロー再制御対象リンクを経路とするフローの中から余剰フローを決定する。そして、フロー再制御対象リンク決定部１６は、フロー再制御対象リンクと定めたリンクがフロー再制御対象リンクに該当しなくなるまで（すなわち、ＬＲ≦（ＬＲＡ−Ｙ）という条件を満たさなくなるまで）、決定した余剰フローを一つずつ選択し、選択した余剰フローの経路を経路計算部１７に再計算させる（ステップＳ５）。
【００６４】
図５は、ステップＳ５（余剰フローの経路再計算処理）の例を示すフローチャートである。ステップＳ５において、フロー再制御対象リンク決定部１６は、フロー再制御対象リンクを経路として通過する各フローの中から余剰フローを決定する（ステップＳ１１）。フロー再制御対象リンク決定部１６は、フロー再制御対象リンクを経路として通過する各フローと、条件記憶部１９に記憶された条件とを照合し、「重要でない」という条件と、「使用帯域が多い」という条件とを満たすフローを余剰フローとして決定する。例えば、条件記憶部１９において、フローが重要でないということを表す条件として「ＵＤＰを使用したフローであること」という条件が記憶され、フローの使用帯域が多いということを表す条件として閾値が記憶されているとする。フロー再制御対象リンク決定部１６は、この場合、フロー再制御対象リンクを経路として通過する各フローのうち、ＵＤＰを使用し、かつ、使用帯域が閾値以上となっている各フローを余剰フローとして決定すればよい。
【００６５】
次に、フロー再制御対象リンク決定部１６は、ステップＳ１１で決定した余剰フローの中から１つの余剰フローを選択し、経路計算部１７にその余剰フローの経路の再計算を要求する（ステップＳ１２）。
【００６６】
経路計算部１７は、この要求に応じて、ステップＳ１２で選択された余剰フローの経路を再計算する（ステップＳ１３）。ステップＳ１３において、経路計算部１７は、オープンフローネットワーク２０における余剰フローの起点から終点までの経路を、ボトルネックリンクを除外して計算する。フロー再制御対象リンクもボトルネックリンクであるので、ステップＳ１３で計算される経路上に、余剰フローがこれまで通過していたフロー再制御対象リンクが存在することはない。
【００６７】
また、ステップＳ１３において経路計算部１７が余剰フローの経路を計算すると、経路通知部１８は、その経路上の各ノードについてアクションを定め、その余剰フローの識別情報およびアクションを経路上の各ノードに通知する。各ノードは、この通知に従って、そのフローを次のノードに転送する。この結果、フロー再制御対象リンクを通過していた余剰フローは、フロー再制御対象リンクを通過しない新たな経路に沿って転送される。
【００６８】
ステップＳ１３の後、ＬＲ計算部１４は、フロー再制御対象リンク、および、余剰フローに対して新たに計算された経路上の各リンクに関してＬＲを再計算し、オープンフローネットワーク内の各リンクのＬＲの平均値ＬＲＡを再計算する（ステップＳ１４）。
【００６９】
ステップＳ４において、ＬＲ計算部１４は、フロー再制御対象リンクを通過する各フローの使用帯域ｕｊのうち、ステップＳ１２で選択された余剰フローのｕｊを削除するように、ネットワーク状況記憶部１２の記憶内容を更新する。そして、ＬＲ計算部１４は、フロー再制御対象リンクに関し、式（２）および式（１）の計算によりＬＲを算出する。フロー再制御対象リンクでは、余剰フローが減少した分、ＵｓｅＬｉも減少するので、再計算の結果ＬＲは増加する。
【００７０】
また、ＬＲ計算部１４は、ステップＳ１３で計算された新たな経路上の各リンクに関して、各フローの使用帯域の合計ＵｓｅＬｉに、新たに経路を決定したフロー分の使用帯域を加算する。加算する値は、使用帯域の見込み値として予め定められている固定値であり、ステップＳ２で加算する固定値と同じ値である。また、ＬＲ計算部１４は、新たに計算された経路上のリンクに関して、余剰フローの使用帯域の値が、上記の固定値である旨を、ネットワーク状況記憶部１２に記憶させる。ＬＲ計算部１４は、新たな経路上の各リンクに関して、固定値を加算した後のＵｓｅＬｉを用いて、ＬＲを再計算する。新たに余剰フローも通過することになったことでＵｓｅＬｉが増加するので、ステップＳ１３で計算された新たな経路上の各リンクでは、ＬＲは減少する。すなわち、ステップＳ１４のＬＲの再計算では、フロー再制御対象リンクのＬＲは増加し、ステップＳ１３で計算された新たな経路上の各リンクのＬＲは減少する。
【００７１】
ＬＲ計算部１４は、ＬＲの再計算後、ＬＲＡも再計算する。
【００７２】
次に、フロー再制御対象リンク決定部１６は、ステップＳ１４においてフロー再制御対象リンクに関して再計算されたＬＲと、ＬＲの平均値ＬＲＡとに基づいて、フロー再制御対象リンクと定められたリンクが、フロー再制御対象リンクのままであるか否かを判定する（ステップＳ１５）。すなわち、フロー再制御対象リンク決定部１６は、ＬＲ≦ＬＲＡ−Ｙが成立したままであるか否かを判定する。ＬＲ≦ＬＲＡ−Ｙが成立したままであれば、フロー再制御対象リンクと定められたリンクがフロー再制御対象リンクのままであると判定する（ステップＳ１５におけるＹｅｓ）。この場合、コントローラ１は、ステップＳ１２以降の処理を繰り返す。ＬＲ≦ＬＲＡ−Ｙが成立していなければ、フロー再制御対象リンクと定められたリンクがフロー再制御対象リンクでなくなったと判定し（ステップＳ１５におけるＮｏ）、ステップＳ５の処理を終了する。
【００７３】
なお、ステップＳ１５において、ボトルネックリンク決定部１５が、ＬＲＡを用いてボトルネックリンクを再決定してもよい。
【００７４】
ステップＳ５の後、いずれかのノードから新規フローの通知を受けた場合、コントローラ１は、ステップＳ１以降の処理を再度行えばよい。また、各ノードが定期的に送信する諸情報を受信した場合には、ステップＳ４以降の処理を行えばよい。
【００７５】
また、本実施形態において、ノード間でフロー転送に用いられていたリンクに障害が発生した場合の動作について説明する。各ノードは、自ノードと他のノードとの間のリンクに障害が発生した場合、障害が発生したリンクをコントローラ１に通知する。図６は、障害が発生したリンクの通知を受けたコントローラの処理経過の例を示すフローチャートである。
【００７６】
例えば、コントローラの情報取得部１１は、障害が発生したリンクの通知をノードから受信すると、そのリンクを通過するフローの中から一つのフローを選択し、経路計算部１７にそのフローの経路の再計算を要求する（ステップＳ２１）。
【００７７】
経路計算部１７は、情報取得部１１からの要求に応じて、ステップＳ２１で選択されたフローの経路を再計算する（ステップＳ２２）。ステップＳ２２において、経路計算部１７は、オープンフローネットワーク２０における選択されたフローの起点から終点までの経路を、ボトルネックリンクおよび障害が発生したリンクを除外して計算する。
【００７８】
また、ステップＳ２２において経路計算部１７が経路を計算すると、経路通知部１８は、その経路上の各ノードについてアクションを定め、そのフローの識別情報およびアクションを経路上の各ノードに通知する。各ノードは、この通知に従って、そのフローを次のノードに転送する。
【００７９】
経路計算部１７が選択されたフローの経路を決定すると、ＬＲ計算部１４は、そのフローの経路上の各リンクに関して、各フローの使用帯域の合計ＵｓｅＬｉに、新たに経路を決定したフロー分の使用帯域を加算する（ステップＳ２３）。この使用帯域は、見込み値として予め定められている固定値である。また、ＬＲ計算部１４は、新たに計算された経路上のリンクに関して、新たに割り当てられたフローの使用帯域の値が、上記の固定値である旨をネットワーク状況記憶部１２に記憶させる。
【００８０】
また、ＬＲ計算部１４は、障害が発生したリンクに関して、各フローの使用帯域の合計ＵｓｅＬｉから、ステップＳ２１で選択されたフロー分の使用帯域を減算する。そして、障害が発生したリンクを通過する各フローの使用帯域ｕｊのうち、ステップＳ２１で選択されたフローのｕｊを削除するように、ネットワーク状況記憶部１２の記憶内容を更新する。
【００８１】
次に、ＬＲ計算部１４は、ステップＳ２３でＵｓｅＬｉを更新したリンクのＬＲを式（１）の計算によって再計算し、さらに、オープンフローネットワーク内の各リンクのＬＲの平均値ＬＲＡを再計算する。そして、ボトルネックリンク決定部１５は、ボトルネックリンクを再決定する。すなわち、ボトルネックリンク決定部１５は、ＬＲが（ＬＲＡ−Ｘ）以下となっているリンクを、ボトルネックリンクと定める（ステップＳ２４）。
【００８２】
続いて、情報取得部１１は、障害が発生したリンクを通過するフローの中に未選択のフロー（ステップＳ２１以降の処理が行われていないフロー）が残っているか否かを判定する（ステップＳ２５）。未選択のフローが残っていれば（ステップＳ２５のＹｅｓ）、コントローラ１は、ステップＳ２１以降の処理を繰り返す。未選択のフローが残っていなければ、障害が発生したリンクに関する処理を終了する。
【００８３】
次に、本発明の動作によるリンクのＬＲの状態の変化の例を説明する。以下の示す例では、式（３）におけるＸの値が“２０”であり、式（４）におけるＹの値が“５０”であるとする。すなわち、ＬＲの値が（ＬＲＡ−２０）以下となっているリンクがボトルネックリンクであると決定され、ＬＲの値が（ＬＲＡ−５０）以下となっているリンクがフロー再制御対象リンクと決定されるものとする。
【００８４】
図７は、オープンフローネットワーク２０内の各リンクのＬＲの例を示す模式図である。なお、本例では、オープンフローネットワーク２０内にノード２Ａ〜２Ｄが存在し、各ノードはそれぞれ他のノードとリンクによって接続されている。また、ノード２Ａは、レガシーネットワーク３０Ａに接続されている。同様に、ノード２Ｂ〜２Ｄも、それぞれレガシーネットワーク３０Ｂ〜３０Ｄに接続されている。図７に示す状態では、ノード２Ａ，２Ｄ間のリンクのＬＲは“６０”であり、ノード２Ｂ，２Ｃ間のリンクのＬＲは“３０”である。その他のリンクのＬＲは、いずれも“１００”である。このとき、各リンクのＬＲの平均値ＬＲＡは、“８１．６”である。（ＬＲＡ−２０）以下のリンクがボトルネックリンクであるので、ノード２Ｂ，２Ｃ間のリンク、およびノード２Ａ，２Ｄ間のリンクがボトルネックリンクとなる。なお、ボトルネックリンクは破線で図示している。
【００８５】
次に、レガシーネットワーク３０Ａ内の装置を起点とし、レガシーネットワーク３０Ｄ内の装置を終点とする新規フローをノード２Ａが受信したとする。すると、ノード２Ａは、新規フローの通知をコントローラ１に送信する。すると、コントローラ１の経路計算部１７は、図７に示すボトルネックを除外して、ノード２Ａから、レガシーネットワーク３０Ｄに接続されたノード２Ｄへの経路を計算する（ステップＳ１、図４参照）。本例では、ノード２Ａ，２Ｂ，２Ｄを通過する経路を計算したとする。なお、経路通知部１８は、新規フローの識別情報およびその新規フローに対するアクションをノード２Ａ，２Ｂ，２Ｄに設定する。
【００８６】
図８は、経路計算後のＬＲの例を示す模式図である。上記のように、経路が計算された後、ＬＲ計算部１４は、その経路上の各リンクにおけるＵｓｅＬｉに、新規フローの使用帯域の見込み値となる固定値を加算し、その各リンクのＬＲを再計算する（ステップＳ２，Ｓ３、図４参照）。個々では、加算する固定値を“１０”とする。この結果、ノード２Ａ，２Ｂ間のリンク、および、ノード２Ｂ，２Ｄ間のリンクにおけるＬＲの値は、それぞれ９０に変化する。また、ＬＲ計算部１４は、ＬＲ再計算後にＬＲＡも再計算する。すると、ＬＲＡは、“７８．３”となる。そして、ボトルネックリンク決定部１５は、ＬＲの値が（ＬＲＡ−２０）以下となっているノード２Ｂ，２Ｃ間のリンクのみをボトルネックリンクとして決定する（ステップＳ３、図４参照）。この結果、図７に示す状態で、ボトルネックリンクであったノード２Ａ，２Ｄ間のリンクは、ボトルネックリンクに該当しなくなる。
【００８７】
各ノード２Ａ〜２Ｄは、定期的に諸情報をコントローラ１（図７から図１０では図示略）に送信する。この結果、コントローラ１の情報取得部１１は、ノード２Ａ，２Ｂ間のリンク、およびノード２Ｂ，２Ｄ間のリンクにおける新規リンクの実際の使用帯域の情報を得る。ＬＲ計算部１４は、この実際の使用帯域を用いて、ＬＲ，ＬＲＡを再計算する（ステップＳ４、図４参照）。図９は、このＬＲ再計算後のＬＲの例を示す模式図である。この再計算の結果、ノード２Ａ，２Ｂ間のリンク、およびノード２Ｂ，２Ｄ間のリンクのＬＲは、それぞれ“９５”であったとする。ＬＲ計算部１４は、ＬＲＡの値として、“８０”を得る。そして、ボトルネックリンク決定部１５は、ＬＲの値が（ＬＲＡ−２０）以下となっているリンクを特定し、ノード２Ａ，２Ｄ間のリンク、およびノード２Ｂ，２Ｃ間のリンクをボトルネックリンクとして決定する。さらに、フロー再制御対象リンク決定部１６は、ＬＲの値が（ＬＲＡ−５０）以下となっているノード２Ｂ，２Ｃ間のリンクをフロー再制御対象リンクとして決定する。
【００８８】
次に、フロー再制御対象リンク決定部１６は、ノード２Ｂ，２Ｃ間のリンクから余剰フローを決定し、経路計算部１７に余剰フローの経路を再計算させる。経路計算部１７は、図９に示すボトルネックリンクを除外して余剰フローの経路を再計算する。ここでは、ノード２Ｃからノード２Ｂへの余剰フローが再計算され、ノード２Ａを経由する新たな経路が計算されたとする（図１０参照）。そして、ＬＲ計算部は、ＬＲおよびＬＲＡを再計算する。この処理を、ノード２Ｂ，２Ｃ間のリンクがフロー再制御対象リンクに該当しなくなるまで（すなわち、ノード２Ｂ，２Ｃ間のリンクのＬＲが（ＬＲＡ−５０）より大きくなるまで）繰り返す。図１０は、この結果の各ＬＲを示す模式図である。余剰フローの経路を再計算したことにより、ノード２Ｂ，２Ｃ間のリンクのＬＲは、“６０”に上昇し、ノード２Ｃ，２Ａ間のリンクや、ノード２Ａ，２Ｂ間のリンクのＬＲは、“７０”，“６５”に下がっている。そして、ＲＬＡの値は“７５”となっている。このようにＬＲが平準化されている。この結果、ネットワーク内の各リンクの帯域を効率的に使用することができる。
【００８９】
本発明によれば、ボトルネックリンク決定部１５がＬＲＡ（各リンクの残存リソースの平均値）に基づいてボトルネックリンクを決定し、経路計算部１７は、新たに経路を計算する場合、ボトルネックリンクを除外して、経路を計算する。従って、本発明では、フローが通過できる帯域が確保されたエンドツーエンドの経路を定めることができる。
【００９０】
また、本発明によれば、フロー再制御対象リンク決定部１６が、残存リソースＬＲがＬＲＡよりも著しく低いと判断されるフロー再制御対象リンクを検出した場合、そのフロー再制御対象リンクを通過するフローの経路を経路計算部１７に再計算させる。経路計算部１７は、ボトルネックリンクを除外して経路を計算するので、新たな経路はフロー再制御対象リンクを通過しないように定められる。この結果、ＬＲの多いリンクから、フロー再制御対象リンクにＬＲを振り向けていることになる。よって、各リンクのＬＲが平準化され、ネットワーク内の各リンクの帯域を効率的に使用することができる。
【００９１】
また、フロー再制御対象リンク決定部１６は、フロー再制御対象リンクを通過するフローのうち、条件記憶部１９に記憶された条件を満たすフローを余剰フローに決定する。従って、管理者が条件を定めることにより、フロー再制御対象リンクから他のリンク振り分けられるフローの優先度を、管理者が指定することができる。
【００９２】
次に、本発明の最小構成について説明する。図１１は、本発明の帯域制御システムの最小構成の例を示すブロック図である。また、図１２は、本発明の帯域制御装置の最小構成の例を示すブロック図である。
【００９３】
本発明の帯域制御システムは、フロー毎に定められたアクションに従って各フローに対する処理を行うノード８０（例えば、実施形態におけるノード２）を複数備える。また、帯域制御システムは、各ノード８０に対して、個々のフローに対するアクションを通知することにより、ノード間のリンクの帯域を制御する帯域制御装置７０（例えば、コントローラ１）を備える。各ノード８０は、自ノードのリンクにおけるフロー毎の使用帯域を含む情報を帯域制御装置７０に送信する。
【００９４】
帯域制御装置７０は、経路計算手段７１と、通知手段７２と、未使用帯域計算手段７３と、除外対象リンク決定手段７４と、フロー再制御対象リンク決定手段７５とを備える。
【００９５】
経路計算手段７１（例えば、経路計算部１７）は、フローの経路を計算する。
【００９６】
通知手段７２（例えば、経路通知部１８）は、経路計算手段７１によって計算された経路上の各ノードに、フローに関するアクションを通知する。
【００９７】
未使用帯域計算手段７３（例えば、ＬＲ計算部１４）は、個々のリンクにおけるフロー毎の使用帯域に基づいて、リンクの未使用帯域（例えば、ＬＲ）を計算する。
【００９８】
除外対象リンク決定手段７４（例えば、ボトルネックリンク決定手段１５）は、未使用帯域の値が各リンクの未使用帯域の平均値（例えば，ＬＲＡ）から第１定数（例えば、式（３）における“Ｘ”）を減算した値以下になっているリンクを、経路計算時に除外すべき除外対象リンク（例えば、ボトルネックリンク）に決定する。
【００９９】
フロー再制御対象リンク決定手段７５（例えば、フロー再制御対象リンク決定手段１６）は、第１定数より大きな第２定数（例えば、式（４）におけるＹ）を用い、未使用帯域の値が各リンクの未使用帯域の平均値から第２定数を減算した値以下になっているリンクを、通過するフローの一部を他のリンクに振り分けるべきフロー再制御対象リンクに決定する。
【０１００】
経路計算手段７１は、除外対象リンクを除外して、フローの経路を計算する。
【０１０１】
フロー再制御対象リンク決定手段７５は、フロー再制御対象リンクに決定したリンクがフロー再制御対象リンクに該当しなくなるまで、フロー再制御対象リンクを通過するフローの経路を経路計算手段に再計算させる。
【０１０２】
未使用帯域計算手段７３は、経路計算手段７１がフローの経路を計算したときに、そのフローに関連するリンクの未使用帯域を再計算する。
【０１０３】
そのような構成により、各フローに対して、フローが通過できる帯域が確保されたエンドツーエンドの経路を定めるようにしつつ、ノードにより形成されるネットワーク全体として、ネットワーク内の各リンクの帯域を効率的に使用できる。
【産業上の利用可能性】
【０１０４】
本発明は、オープンフローにおいてパケットを転送するパケット転送装置間のリンクにおける帯域の制御に好適に適用される。
【符号の説明】
【０１０５】
１  コントローラ（帯域制御装置）
２  ノード（パケット転送装置）
３  リンク
１１  情報取得部
１２  ネットワーク状況記憶部
１３  リンク状態計算部
１４  ＬＲ計算部
１５  ボトルネックリンク決定部
１６  フロー再制御対象リンク
１７  経路計算部
１８  経路通知部
１９  条件記憶部
【図１】
0005493965.tif 000003
【図２】
0005493965.tif 000004
【図３】
0005493965.tif 000005
【図４】
0005493965.tif 000006
【図５】
0005493965.tif 000007
【図６】
0005493965.tif 000008
【図７】
0005493965.tif 000009
【図８】
0005493965.tif 000010
【図９】
0005493965.tif 000011
【図１０】
0005493965.tif 000012
【図１１】
0005493965.tif 000013
【図１２】
0005493965.tif 000014