(57)【要約】【課題】経路計算負荷が増大した場合、遅延時間を抑制した経路設定を行う。【解決手段】複数のネットワーク機器を集中管理する集中管理型網制御装置は、経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し、前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う。また、前記経路計算の低負荷状態を判定したときには、前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路の設定制御を行う。【選択図】図４
2014138244.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワーク機器を集中管理する集中管理型網制御装置であって；
経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し；
前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う；
ように構成されたプロセッサを備える集中管理型網制御装置。
【請求項２】
前記経路計算の低負荷状態を判定したときには、前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路の設定制御を行う；
ように更に構成された前記プロセッサを備える請求項１記載の集中管理型網制御装置。
【請求項３】
前記過去の経路計算実行により得られた経路木は、前記経路設定要求に応じた経路計算実行により得られ、かつ保存されている最短経路木及び最短経路木候補を含む
請求項２記載の集中管理型網制御装置。
【請求項４】
前記経路計算の高負荷状態においては、前記過去の経路計算実行により得られた経路木として、前記保存されている最短経路木及び最短経路木候補の中から選択する；
ように更に構成された前記プロセッサを備える請求項３記載の集中管理型網制御装置。
【請求項５】
前記経路計算の負荷状態が高負荷状態から低負荷状態に変化したとき、一時的に設定した経路から前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路に経路変更の設定制御を行う；
ように更に構成された前記プロセッサを備える請求項１，２，３または４記載の集中管理型網制御装置。
【請求項６】
前記高負荷状態から前記低負荷状態への変化が継続している間は、前記経路変更の設定制御を繰り返す；
ように更に構成された前記プロセッサを備える請求項５記載の集中管理型網制御装置。
【請求項７】
前記経路計算実行においては、前記経路設定要求に伴って与えられる送信元ノードを経路木のルートとする単一始点の最短経路木を計算するために、ダイクストラ法のアルゴリズムを利用する
請求項１，２，３，４，５または６記載の集中管理型網制御装置。
【請求項８】
前記集中管理型網制御装置は、ＯｐｅｎＦｌｏｗコントローラであり、ＯｐｅｎＦｌｏｗプロトコルに則り、前記複数のネットワーク機器としての複数のＯｐｅｎＦｌｏｗスイッチにパケットの転送ルールを記述したフローテーブルを配信して集中管理する
請求項１記載の集中管理型網制御装置。
【請求項９】
経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し；
前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う；
ことをプロセッサが実行する集中管理型網制御方法。
【請求項１０】
経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し；
前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路
木に従った経路を利用して一時的な経路の設定制御を行う；
ことをプロセッサに実行させる集中管理型網制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集中管理型網制御システムに関する。
【背景技術】
【０００２】
ネットワーク分野においては、ＯｐｅｎＦｌｏｗを代表格とするＳＤＮ（Software Defined Network）関連技術が近年注目されている。ＯｐｅｎＦｌｏｗでは、従来のスイッチ及びルータなどのネットワーク機器が備えている、パケット形態でのデータ転送機能と、スイッチング及びルーティングなどの制御機能とが、スイッチ（ＯｐｅｎＦｌｏｗスイッチ）とコントローラ（ＯｐｅｎＦｌｏｗコントローラ）とに分離される。
【０００３】
ＯｐｅｎＦｌｏｗコントローラは、ＯｐｅｎＦｌｏｗプロトコルに則り、ＯｐｅｎＦｌｏｗスイッチにおけるデータ転送を制御する。つまり、ＯｐｅｎＦｌｏｗでは、コントローラがネットワーク中に存在する複数のスイッチを集中制御で管理する。これまでのネットワーク制御と異なりＯｐｅｎＦｌｏｗでは、２つの通信ノード間で通信を行うためには、コントローラが最適な経路（route）を決定し、経路上に存在するスイッチに対してフ
ローテーブル（Flow Table）の設定（配信）を行う必要がある。なお、コントローラは、これまでのネットワーク制御と同様に、ダイクストラ（Dijkstra）法のアルゴリズム（Single Source Shortest Path Algorithm）に基づいて、最短経路を計算することが可能で
ある。
【０００４】
また、近年のクラウドコンピューティングの発達に伴い、ユーザは、必要な時に、必要な分だけの基盤（インフラ）としての仮想マシン（ＶＭ：Virtual Machine）を立ち上げ
ることが可能である。例えば、Ａｍａｚｏｎ（登録商標）及びＧｏｏｇｌｅ（登録商標）はＶＭ単位でサーバ環境などのマシンリソースを貸し出すサービスであるＩａａＳ（イアース／アイアス（Infrastructure as a Service））を行っている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−９４２２２号公報
【非特許文献】
【０００６】
【非特許文献１】E. W. Dijkstra, "A Note on Two Problems in Connextion with Graphs", Numerische Mathematik, Vol. 1, pp.269-271, 1959
【非特許文献２】George T. Heineman et al, "アルゴリズムクイックリファレンズ", pp.169-177, オライリー, Apr. 2010
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＯｐｅｎＦｌｏｗのような集中管理型のネットワーク制御技術をＩａａＳに適用した場合を考えると、ＶＭが配備された段階で、このＶＭに対してのネットワークの疎通性が必要になる。コントローラは、配備対象のＶＭが送信元または宛先となる最短経路を計算し、経路上のスイッチに対して必要なフローテーブルの設定を行う必要がある。
【０００８】
ＩａａＳを実施する大規模ネットワークにおいて、多数のＶＭが一度に配備された場合、これらのＶＭに対するネットワークの疎通性を確保するために、これらのＶＭに対する経路設定要求が大量に発生する。この場合、コントローラは、大量の経路計算を短時間に処理する必要があり、経路計算負荷が増大するので、経路設定までの遅延時間が通常時よ
りも長くなることを免れない。
【０００９】
課題は、コントローラである集中管理型網制御装置に対して、大量の経路設定要求が発生し、経路計算負荷が増大した場合、遅延時間を抑制した経路設定を行うことを可能にする技術を提供することにある。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、複数のネットワーク機器を集中管理する集中管理型網制御装置は、経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し、前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う。また、前記経路計算の低負荷状態を判定したときには、前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路の設定制御を行う。
【発明の効果】
【００１１】
開示した集中管理型網制御装置によれば、経路計算要求が大量に発生し、経路計算負荷が高い場合に大量の経路計算を行わずに、過去に（直前を含む）求めた経路情報を利用（再利用）することにより、経路設定までの遅延時間を抑制することができ、結果として経路設定までに発生するパケットロスが低減できる。
【００１２】
他の課題、特徴及び利点は、図面及び特許請求の範囲とともに取り上げられる際に、以下に記載される発明を実施するための形態を読むことにより明らかになるであろう。
【図面の簡単な説明】
【００１３】
【図１】一実施の形態の集中管理型網制御システムの構成を示すブロック図。
【図２】図１における集中管理型網制御装置の構成を示すブロック図。
【図３】フローテーブルの構成を示す。
【図４】第１の経路設定処理を示すフローチャート。
【図５】経路木を説明するための図。
【図６】経路木を説明するための図。
【図７】第２の経路設定処理を示すフローチャート。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照して、さらに詳細に説明する。図面には好ましい実施形態が示されている。しかし、多くの異なる形態で実施されることが可能であり、本明細書に記載される実施形態に限定されない。
【００１５】
［集中管理型網制御システム］
一実施の形態におけるシステム構成を示す図１を参照すると、集中管理型網制御システム１は、集中管理型網制御装置２と、通信ネットワークＮＷを構成する複数のネットワーク機器としてのスイッチ３とを備える。ここでは、簡素化のために、少なくとも１つの通信ネットワークＮＷを構成する９個のスイッチ（ＳＷ１−ＳＷ９）３を例示している。これらのスイッチ３は、Ｌ２（レイヤ２）スイッチ、Ｌ３（レイヤ３）スイッチ、及びルータなどのいずれであってもよい。
【００１６】
この一実施の形態においては、集中管理型網制御装置２は、ＯｐｅｎＦｌｏｗコントローラであり、ＯｐｅｎＦｌｏｗプロトコルに則り、９個のスイッチ（ＯｐｅｎＦｌｏｗスイッチ）３にフローテーブル（Flow Table）を設定（配信）して集中管理する。
【００１７】
（集中管理型網制御装置）
集中管理型網制御装置（以下、単にコントローラと記載することもある）２は、図２に示すように、ハードウェア構成として、次の要素を含んでいる。つまり、プロセッサとしてのＣＰＵ（Central Processing Unit）２１と、作業用メモリとしてのＲＡＭ（Random Access Memory）２２と、立ち上げのためのブートプログラムを格納したＲＯＭ（Read Only Memory）２３とを備える。
【００１８】
また、集中管理型網制御装置２は、ＯＳ（Operating System）、各種アプリケーションプログラム、及び各種情報（データを含む）を書換え可能に格納する不揮発性のフラッシュメモリとしてのディスク２４と、通信インタフェースとしてのＮＩＣ（Network Interface Card）２５などとを備える。
【００１９】
後に詳述する経路設定処理機能を論理的に実現するには、集中管理型網制御装置２において、ディスク２４に制御プログラム（ＳＤＮ制御プログラム）をアプリケーションプログラムとしてインストールしておく。そして、この集中管理型網制御装置２においては、ＣＰＵ２１がこの制御プログラムをＲＡＭ２２に常時展開し、常駐プログラムとして実行する。
【００２０】
更に詳述すると、集中管理型網制御装置２は、経路設定要求受付部２２１、最短経路計算部２２２、経路計算負荷計測部２２３、経路設定部２２４、最短経路木保持部２２５、最短経路木選択部２２６、経路計算負荷判定部２２７、及び設定済経路情報保持部２２８を機能構成要素として備える。
【００２１】
経路設定要求受付部２２１は、集中管理型網制御装置２の外部で発生した経路設定要求をＮＩＣ２５を介して受け付ける（受信する）。この経路設定要求は、例えば、サーバ環境などのマシンリソースを貸し出すサービスであるＩａａＳ（イアース／アイアス）を実施するために、仮想マシン（ＶＭ）が配備された場合、この仮想マシンに対する通信ネットワークＮＷの疎通性を確保するために、上位のアプリケーションレイヤなどから発生する。この経路設定要求は送信元通信ノードの識別情報及び宛先通信ノードの識別情報を含む。
【００２２】
最短経路計算部２２２は、経路設定要求に伴って与えられた配備対象の仮想マシン対応の１つの通信ノード（以下、単にノードと記載することもある）を経路木（ツリー）内の最初の分岐点、つまり始点（ルート（root））とする最短経路木を計算する。最短経路計算部２２２がこのような単一始点の最短経路木を計算するためには、例えばダイクストラ（Dijkstra）法のアルゴリズム（Single Source Shortest Path Algorithm）を利用可能
である（詳細は上記非特許文献２参照）。
【００２３】
経路計算負荷計測部２２３は、集中管理型網制御装置２において現在実行している経路計算についての負荷の程度を計測する。経路設定部２２４は、後に詳述する経路設定処理によって決定された経路を実現するために、該当スイッチ３のフローテーブル（後に詳述）を設定して配信する。
【００２４】
最短経路木保持部２２５は、最短経路計算部２２２が最短経路計算を行った際に、得られた最短経路木及び最短経路木候補を記憶する。最短経路木選択部２２６は、最短経路木保持部２２５に既に保持されている複数の最短経路木候補と、新しく求められた最短経路木との中から最短経路木保持部２２５に保持すべき最短経路木候補を選択する。また、最短経路木選択部２２６は、経路計算負荷が高い際に、複数の最短経路木の候補の中から、使用する最短経路木を選択する。
【００２５】
経路計算負荷判定部２２７は、経路計算負荷計測部２２３で得られた経路計算負荷情報
に基づいて予め定められた閾値と比較し、経路計算負荷が高いか低いかを判定する。設定済経路情報保持部２２８は、２つの通信ノード間に既に設定されている経路情報を記憶する。
【００２６】
上述した集中管理型網制御装置２においては、経路設定要求が発生した際に、発生時点での経路計算負荷が予め定められた閾値に比較して高いか低いかを判定する。経路計算負荷が低いと判定したときには、オンデマンドでの経路計算（つまり、経路設定要求に応じた経路計算）を行い、この計算結果に従った経路設定を行う。一方、経路計算負荷が高いと判定したときには、過去（直前を含む）に行われた経路計算の結果を利用（再利用）して一時的な経路設定を行う。また、経路計算負荷が高い状態から低い状態に変化したときには、一時的に設定された経路からオンデマンドに経路計算して求める経路に経路設定を変更する。
【００２７】
（スイッチ）
図１に示す各スイッチ３は、ハードウェア構成として、プロセッサとしてのＣＰＵと、作業用メモリとしてのＲＡＭと、立ち上げのためのブートプログラムを格納したＲＯＭとを備える。また、各スイッチ３は、ＯＳ、各種アプリケーションプログラム、及び各種情報（データを含む）を書換え可能に格納する不揮発性のフラッシュメモリとしてのディスクと、通信インタフェースとしてのＮＩＣなどとを備える。これらのハードウェア構成は、当業者が容易に理解でき、実施可能であるので、ここではこの構成の図示を省略している。
【００２８】
集中管理型網制御装置２によって実施されるネットワーク制御とは分離された、パケット形態でのデータ転送機能を論理的に実現するには、各スイッチ３において、ディスクに制御プログラムをアプリケーションプログラムとしてインストールしておく。そして、各スイッチ３においては、集中管理型網制御装置２からの指示を受信したときを契機に、ＣＰＵがこの制御プログラムをＲＡＭに展開して実行する。これにより、各スイッチ３においては、図３に示すフローテーブル３１に設定されている経路情報に従ったスイッチング動作を行い、決定された経路を実現する。
【００２９】
図３を参照すると、フローテーブル３１は、パケットの転送ルールを記述したテーブルであり、集中管理型網制御装置２からの指示によって内容が追加、削除、または更新される。このフローテーブル３１は、スイッチ３の入力ポート番号、送信（送信元）ノード識別情報（ＩＤ）、宛先ノード識別情報（ＩＤ）、及びスイッチ３の出力ポート番号を対応付けて記憶する。
【００３０】
各スイッチ３においては、入力されたパケット（運用パケット）に関し、フローテーブル３１を参照して、入力ポート番号、送信ノードＩＤ、及び宛先ノードＩＤが一致するレコードを検索し、このレコードの出力ポート番号に対応する出力ポートに対して転送対象パケットを出力する。このフローテーブル３１における第１レコード（１行目）の例では、スイッチ３の入力ポート番号“１”から入力される、送信ノードＩＤが“３”であり、かつ宛先ノードＩＤが“５”である、パケットをスイッチ３の出力ポート番号“２”に出力することを示している。
【００３１】
ここで、送信ノードＩＤ及び宛先ノードＩＤは、転送対象パケットのヘッダ部から得られるＩＰ（Internet Protocol）アドレスだけではなく、ＭＡＣ（Media Access Control
）アドレスなどの各通信ノードを識別することができる識別情報であれば、いずれであってもよい。また、ＩＰアドレス及びＭＡＣアドレスの双方に対応する複数の識別情報の組み合わせで表現してもよい。さらに、送信ノードＩＤ及び宛先ノードＩＤの一方がワイルドカードであってもよい。
【００３２】
［動作］
次に、図１に示す一実施の形態の集中管理型網制御システム１における動作例について、関連図を併せ参照して説明する。
【００３３】
（基本的な経路設定処理）
先ず、コントローラ２における第１の経路設定処理について説明する。
【００３４】
コントローラ２においては、ノードＳ１からノードＤ１までの経路設定要求が外部から発生した場合、経路設定要求受付部２２１は、ＮＩＣ２５を介して、この経路設定要求を受け付ける（図４中のＳ３０）。
【００３５】
経路計算負荷判定部２２７は、経路計算負荷計測部２２３で得られた経路計算負荷情報に基づいて予め定められた閾値と比較し、自装置の経路計算負荷が高いかを判定する（図４中のＳ３１）。
【００３６】
経路計算負荷が高くない（つまり、低い）と判定された場合には、最短経路計算部２２２は、経路計算を実行し、ノードＳ１をルートとする最短経路木を求める（図４中のＳ３２）。
【００３７】
最短経路計算部２２２により経路計算が実行された場合、最短経路木保持部２２５は、この経路計算で得られた最短経路木候補を最短経路木と共に保持（保存）する（図４中のＳ３３）。ここで、最短経路木候補及び最短経路木を保持する理由は、Ｓ３１の処理で経路計算負荷が高いと判定された場合、過去に計算した最短経路木候補及び最短経路木を利用するためである。
【００３８】
例えば、最短経路木保持部２２５は、最大ｎ個の最短経路木を保持することを前提にすると、現在保持している最短経路木数がｎ個未満の場合は、最短経路計算部２２２により新しく計算された最短経路木を保持する。一方、最短経路木保持部２２５がｎ個の最短経路木を既に保持している場合には、新しく計算された１個の最短経路木を加えたｎ＋１個の最短経路木からｎ個の最短経路木を選択することが必要になる。このとき、最短経路木選択部２２６がｎ個の候補を如何に選択するかについては後に詳述する。
【００３９】
経路設定部２２４は、最短経路計算部２２２によって求められた最短経路木に従って経路設定を制御する。つまり、経路設定部２２４は、得られた最短経路木に基づいて、ノードＳ１からノードＤ１までの最短経路に対応する各スイッチ３のフローテーブル３１を設定制御することにより、経路の設定が行われる（図４中のＳ３４）。これにより、経路計算負荷が低いと判定された場合における経路設定処理が終了する。
【００４０】
一方、Ｓ３１の処理で経路計算負荷が高いと判定された場合には、最短経路木保持部２２５は、保存内容を参照し、ノードＳ１からノードＤ１までの経路設定対象について、最短経路木を過去に計算済みか判定する（図４中のＳ３５）。
【００４１】
最短経路計算部２２２は、最短経路木保持部２２５において最短経路木を過去に計算済みでないと判定された場合には、通常どおりの経路計算を実行する（図４中のＳ３２）。これにより、上述したＳ３３での最短経路木及び最短経路木候補の保持及びＳ３４での経路設定制御が行われた後、経路設定処理が終了する。
【００４２】
また、最短経路木保持部２２５は、最短経路木を過去に計算済みであると判定した場合には、計算済み最短経路木を取得する（図４中のＳ３６）。これにより、上述したＳ３４
での経路設定制御が行われた後、経路設定処理が終了する。過去に計算した最短経路木を利用した経路設定の詳細については後述する。
【００４３】
続いて、上述したＳ３２での経路計算実行処理及びＳ３３での最短経路木及び最短経路木候補の保持処理について、更に詳述する。
【００４４】
ノードＳ１からノードＤ１までの経路設定要求が発生し、経路計算負荷が低いと判定された場合、最短経路計算部２２２は、Ｓ３２での経路計算実行処理において、ノードＳ１をルートとする最短経路木を求める。
【００４５】
この経路計算の結果、例えば、図５に示すように、符号１をルート（始点）とし、符号４，５，８を経由点とし、符号９を末端の点（リーフ（leaf））とする、最短経路木が得られる。
【００４６】
また、この経路計算の結果、符号１，２，３を含む経路木、符号１，４，５，６を含む経路木、及び符号１，４，７を含む経路木が併せて得られる。これらの経路木は、上述したＳ３３での処理において、符号１，４，５，８，９を含む最短経路木と共に、符号１をルートとする最短経路木の候補として保持される。
【００４７】
なお、Ｓ３２及びＳ３３における処理は、Ｓ３１で経路計算負荷が高いと判定され、かつＳ３５で最短経路木を過去に計算済みでないと判定された場合にも同様に実行される。
【００４８】
この後に、符号２から符号６までの経路設定要求が新たに発生し、このときの経路計算負荷が高いと判定された場合、上述したＳ３６の処理において、最短経路木保持部２２５は過去に計算済みの最短経路木を取得する。
【００４９】
ここで取得される過去に計算済みの最短経路木は、上述した符号１をルートとする４つの最短経路木の候補である。このとき、経路設定要求は符号２から符号６までであるので、４つの最短経路木の候補の内、符号１，４，５，６を含む経路木が得られる。そして、この経路木に沿って、符号２をルートとする符号６までの経路が設定制御されることになる。この結果、図６に示すように、符号２，１，４，５，６を含む経路が設定される。
【００５０】
図４に示す上述した第１の経路設定処理においては、コントローラ２の経路計算負荷が予め定められた閾値より高いと判定された場合、例えば、符号２から符号６までの経路設定要求について、最短経路木を過去に計算済みかが判定される。そして、最短経路木を過去に計算済みであると判定した場合には、この計算済み最短経路木に基づいて、経路設定制御が行われる。つまり、経路計算の高負荷状態では、過去に計算した最短経路木を再利用することにより、経路設定処理が促進される。
【００５１】
次に、図７に示す第２の経路設定処理においては、コントローラ２の経路計算負荷の低下が検出された場合、適正な最短経路木に従った最短経路に設定し直す。この第２の経路設定処理においては、一時的（暫定的）に設定された遠回りとなる経路を最短経路に戻し、通信ネットワークＮＷの利用効率を高めることができる。
【００５２】
詳述すると、経路計算負荷判定部２２７は、経路計算負荷計測部２２３で得られた経路計算負荷情報に基づいて予め定められた閾値と比較し、経路計算負荷の低下、つまり経路計算の高負荷状態から低負荷状態への変化を検出する（図７中のＳ４１）。
【００５３】
設定済経路情報保持部２２８は、経路計算負荷判定部２２７からこの負荷状態変化を通知された場合、過去に計算した最短経路木に従って一時的に設定された経路が存在するか
保存内容を参照して判定する（図７中のＳ４２）。
【００５４】
設定済経路情報保持部２２８が否定判定した場合は、処理終了となるが、設定済経路情報保持部２２８が肯定判定した場合は、最短経路木選択部２２６が起動される。
【００５５】
最短経路木選択部２２６は、設定済経路情報保持部２２８に保存されている経路情報を参照し、一時的に設定された経路の１つに対応する最短経路木を選択する（図７中のＳ４３）。ここでは、例えばノードＳ２からノードＤ２までの経路（図６中の符号２から符号６までの経路に対応）について、ノードＳ１（図６中の符号１に対応）をルートとする最短経路木を使用していたとする。
【００５６】
最短経路木選択部２２６から選択した最短経路木に関する通知を受けた最短経路計算部２２２は、一時的に設定された経路についての経路計算を実行し、ノードＳ２をルートとする適正な最短経路木を求める（図７中のＳ４４）。この経路計算の結果、例えば、図６中の符号２をルートとし、符号５を経由点とし、符号６をリーフとする、適正な最短経路木が得られる。
【００５７】
経路設定部２２４は、最短経路計算部２２２によって求められた適正な最短経路木に従って経路設定を制御する。つまり、経路設定部２２４は、得られた最短経路木に基づいて、ノードＳ２からノードＤ２までの最短経路に対応する各スイッチ３のフローテーブル３１を設定制御することにより、経路の設定し直しが行われる（図７中のＳ４５）。
【００５８】
経路計算負荷判定部２２７が経路計算の低負荷状態を検出（判定）している間は、つまり経路計算負荷が再び高くならない限り、一時的に最短経路ではなく設定された経路を順次に取り出し、取り出した経路のそれぞれについて、最短経路に従った経路設定制御をするために最短経路木を計算する処理が繰り返される（図７中のＳ４６）。
【００５９】
（経路計算負荷の判定方法）
次に、経路計算負荷判定部２２７において実施される経路計算負荷の判定方法の実現形態について説明する。経路計算負荷判定部２２７は、上述した第１及び第２の経路設定処理において、例えば、ネットワーク運用者からの事前指示に基づき、次に説明する第１、第２及び第３の経路計算負荷の判定方法のいずれかを必要により経路計算負荷計測部２２３との協働により実施する。これらの判定方法のいずれにおいても、判定に用いる閾値の値は、事前にある１つの値に固定的に決めることが可能であるが、運用状況などに応じて動的に変更してもよい。
【００６０】
経路計算負荷判定部２２７が実施する第１の経路計算負荷の判定方法においては、過去の（厳密には、直前の数回の）経路計算時間に基づいて判定する。つまり、経路計算負荷計測部２２３において、経路設定要求が発生した時刻と、経路計算が終了した時刻とを各要求について記録しておき、経路計算が終了するまでに要した時間を計算する。経路計算負荷判定部２２７においては、経路計算が終了するまでに要した時間が、予め定められた閾値以上のとき（または超過のとき）には、経路計算負荷が高い高負荷状態と判定すると共に、予め定められた閾値未満のとき（または以下のとき）には、経路計算負荷が低い低負荷状態と判定する。
【００６１】
経路計算負荷判定部２２７が実施する第２の経路計算負荷の判定方法においては、キュー長に基づいて判定する。つまり、経路設定要求を受け付けたとき、経路設定要求が経路設定要求受付部２２１の図示省略のキュー（ＦＩＦＯ（First in First out））に格納される。このとき、キュー長に閾値を設け、予め定められた閾値以上（または超過）に未処理の経路設定要求が存在するときには、経路計算負荷が高い高負荷状態と判定すると共に
、予め定められた閾値未満（または以下）に未処理の経路設定要求が存在するときには、経路計算負荷が低い低負荷状態と判定する。
【００６２】
経路計算負荷判定部２２７が実施する第３の経路計算負荷の判定方法においては、ＣＰＵ２１の使用率に基づいて判定する。つまり、経路計算負荷計測部２２３は経路計算に使用しているＣＰＵ使用率をモニターする。経路計算負荷判定部２２７は、ＣＰＵ使用率が予め定められた閾値以上のとき（または超過のとき）には、経路計算負荷が高い高負荷状態と判定すると共に、ＣＰＵ使用率が予め定められた閾値未満のとき（または以下のとき）には、経路計算負荷が低い低負荷状態と判定する。
【００６３】
（最短経路木の選択方法）
次に、最短経路木選択部２２６において実施される過去に計算した最短経路木の選択方法の実現形態について説明する。最短経路木選択部２２６は、上述した第１及び第２の経路設定処理において、例えば、ネットワーク運用者からの事前指示に基づき、次に説明する第１、第２及び第３の過去に計算した最短経路木の選択方法のいずれかを実施する。
【００６４】
最短経路木選択部２２６が実施する第１の最短経路木の選択方法においては、最短経路計算部２２２が直前に行った経路計算結果を利用する。つまり、最短経路木選択部２２６は、最短経路計算部２２２が一番最後に経路計算を実行した際に得られ、最短経路木保持部２２５に保持されている最短経路木（最短経路木候補を含む）を選択する。
【００６５】
最短経路木選択部２２６が実施する第２の最短経路木の選択方法においては、最短経路計算部２２２による複数回の経路計算の結果を利用する。つまり、最短経路木選択部２２６は、最短経路計算部２２２による複数回の経路計算を実行した際に得られ、最短経路木保持部２２５に保持されている複数の最短経路木（最短経路木候補を含む）の中から１つを選択する。
【００６６】
この第２の最短経路木の選択方法において、どのように複数の最短経路木を選択するかについて、いつかのバリエーションが考えられる。第１には、過去における最新のｎ個の最短経路木を選択することが可能である。第２には、既に候補となっているｎ個の最短経路木と、新たに経路計算を行って得られた１つの最短経路木との合計であるｎ＋１個の最短経路木の中からｎ個の最短経路木をランダムに選択することが可能である。
【００６７】
また、第３には、複数の最短経路木を選択する際に、ネットワークＮＷの輻輳状況を考慮する方法も考えられる。つまり、既に候補となっているｎ個の最短経路木と、新たに経路計算を行って得られた１つの最短経路木との合計であるｎ＋１個の最短経路木の中から輻輳の少ない経路を使用するように、ｎ個の最短経路木を選択することが可能である。この輻輳判定には、各リンクのリンク帯域に対する使用帯域、つまり利用率を求め、利用率が閾値を超えているかで判定する。閾値を超えているリンクが多い最短経路木ほど、輻輳状態が強いと考えて候補の選択を行う。
【００６８】
さらに、第２の最短経路木の選択方法において、どのようにｎ個の最短経路木の中から１つの最短経路木を選択するかについても、いつかのバリエーションが考えられる。第１には、ｎ個の最短経路木の中から１つの最短経路木をランダムに選択することが可能である。また、第２には、経路設定要求についての送信ノード及び宛先ノード間の経路を各最短経路木候補に従って求め、ホップ数が最も少ない経路を選択することが可能である。
【００６９】
１つの最短経路木を選択するこれらの方法では、ネットワークＮＷの混雑度が加味されていないが、混雑度を考慮した方法としては、上述したｎ個の最短経路木を選択する際に用いた方法、つまりリンク利用率が閾値を超えているリンク数が最も少ない最短経路木を
選択するという方法が考えられる。これにより、なるべく輻輳を起こしているリンクを使用しないようにすることができる。また、経路設定要求についての送信ノード及び宛先ノード間の経路を候補の各最短経路木に従って求め、経路中に含まれる輻輳発生リンクの割合を基準にして、この割合が最も小さい最短経路木を選択する方法も考えられる。さらに、ネットワーク全体の輻輳の発生状況をトリガーにして、輻輳を考慮しない経路設定方法と、輻輳を考慮する経路設定方法とを切り替えてもよい。
【００７０】
（経路設定要求の優先処理方法）
コントローラ２の経路設定要求受付部２２１において受け付けられる経路設定要求のパケットには、優先度のフィールドがある。上述した第１の経路設定処理においては、最短経路計算部２２２は、この優先度フィールドの内容に基づいて、経路設定要求受付部２２１のキューから高優先度の経路設定要求を処理してもよい。
【００７１】
［変形例］
上述した一実施の形態における処理はコンピュータで実行可能なプログラムとして提供され、ＣＤ−ＲＯＭやフレキシブルディスクなどの非一時的コンピュータ可読記録媒体、さらには通信回線を経て提供可能である。
【００７２】
また、上述した一実施の形態における各処理はその任意の複数または全てを選択し組合せて実施することもできる。
【００７３】
［その他］
上述した一実施の形態及び変形例に関し、更に以下の付記を開示する。
【００７４】
（付記１）複数のネットワーク機器を集中管理する集中管理型網制御装置であって；
経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し；
前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う；
ように構成されたプロセッサを備える集中管理型網制御装置。
【００７５】
（付記２）前記経路計算の低負荷状態を判定したときには、前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路の設定制御を行う；
ように更に構成された前記プロセッサを備える付記１記載の集中管理型網制御装置。
【００７６】
（付記３）前記過去の経路計算実行により得られた経路木は、前記経路設定要求に応じた経路計算実行により得られ、かつ保存されている最短経路木及び最短経路木候補を含む
付記２記載の集中管理型網制御装置。
【００７７】
（付記４）前記経路計算の高負荷状態においては、前記過去の経路計算実行により得られた経路木として、前記保存されている最短経路木及び最短経路木候補の中から選択する；
ように更に構成された前記プロセッサを備える付記３記載の集中管理型網制御装置。
【００７８】
（付記５）前記経路計算の負荷状態が高負荷状態から低負荷状態に変化したとき、一時的に設定した経路から前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路に経路変更の設定制御を行う；
ように更に構成された前記プロセッサを備える付記１，２，３または４記載の集中管理型網制御装置。
【００７９】
（付記６）前記高負荷状態から前記低負荷状態への変化が継続している間は、前記経路変更の設定制御を繰り返す；
ように更に構成された前記プロセッサを備える付記５記載の集中管理型網制御装置。
【００８０】
（付記７）前記経路計算実行においては、前記経路設定要求に伴って与えられる送信元ノードを経路木のルートとする単一始点の最短経路木を計算するために、ダイクストラ法のアルゴリズムを利用する
付記１，２，３，４，５または６記載の集中管理型網制御装置。
【００８１】
（付記８）前記経路設定要求は、送信元ノードの識別情報及び宛先ノードの識別情報を含む
付記１記載の集中管理型網制御装置。
【００８２】
（付記９）前記集中管理型網制御装置は、ＯｐｅｎＦｌｏｗコントローラであり、ＯｐｅｎＦｌｏｗプロトコルに則り、前記複数のネットワーク機器としての複数のＯｐｅｎＦｌｏｗスイッチにパケットの転送ルールを記述したフローテーブルを配信して集中管理する
付記１記載の集中管理型網制御装置。
【００８３】
（付記１０）前記フローテーブルは、送信元ノードの識別情報、宛先ノードの識別情報、前記ＯｐｅｎＦｌｏｗスイッチの入力ポート番号、及び前記ＯｐｅｎＦｌｏｗスイッチの出力ポート番号を含む
付記９記載の集中管理型網制御装置。
【００８４】
（付記１１）経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し；
前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う；
ことをプロセッサが実行する集中管理型網制御方法。
【００８５】
（付記１２）前記経路計算の低負荷状態を判定したときには、前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路の設定制御を行う；
ことを前記プロセッサが更に実行する付記１１記載の集中管理型網制御方法。
【００８６】
（付記１３）前記過去の経路計算実行により得られた経路木は、前記経路設定要求に応じた経路計算実行により得られ、かつ保存されている最短経路木及び最短経路木候補を含む
付記１２記載の集中管理型網制御方法。
【００８７】
（付記１４）前記経路計算の高負荷状態においては、前記過去の経路計算実行により得られた経路木として、前記保存されている最短経路木及び最短経路木候補の中から選択する；
ことを前記プロセッサが更に実行する付記１３記載の集中管理型網制御方法。
【００８８】
（付記１５）前記経路計算の負荷状態が高負荷状態から低負荷状態に変化したとき、一時的に設定した経路から前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路に経路変更の設定制御を行う；
ことを前記プロセッサが更に実行する付記１１，１２，１３または１４記載の集中管理型網制御方法。
【００８９】
（付記１６）経路設定要求を受信したとき、予め定められた閾値に基づいて経路計算の負荷状態を判定し；
前記経路計算の高負荷状態を判定したときは、過去の経路計算実行により得られた経路木に従った経路を利用して一時的な経路の設定制御を行う；
ことをプロセッサに実行させる集中管理型網制御プログラム。
【００９０】
（付記１７）前記経路計算の低負荷状態を判定したときには、前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路の設定制御を行う；
ことを前記プロセッサに更に実行させる付記１６記載の集中管理型網制御プログラム。
【００９１】
（付記１８）前記過去の経路計算実行により得られた経路木は、前記経路設定要求に応じた経路計算実行により得られ、かつ保存されている最短経路木及び最短経路木候補を含む
付記１７記載の集中管理型網制御プログラム。
【００９２】
（付記１９）前記経路計算の高負荷状態においては、前記過去の経路計算実行により得られた経路木として、前記保存されている最短経路木及び最短経路木候補の中から選択する；
ことを前記プロセッサに更に実行させる付記１８記載の集中管理型網制御プログラム。
【００９３】
（付記２０）前記経路計算の負荷状態が高負荷状態から低負荷状態に変化したとき、一時的に設定した経路から前記経路設定要求に応じた経路計算実行により得られる最短経路木に従った経路に経路変更の設定制御を行う；
ことを前記プロセッサに更に実行させる付記１６，１７，１８または１９記載の集中管理型網制御プログラム。
【符号の説明】
【００９４】
１    集中管理型網制御システム
２    集中管理型網制御装置
３    スイッチ
ＮＷ  通信ネットワーク
３１  フローテーブル
【図１】
2014138244.tif 000003
【図２】
2014138244.tif 000004
【図３】
2014138244.tif 000005
【図４】
2014138244.tif 000006
【図５】
2014138244.tif 000007
【図６】
2014138244.tif 000008
【図７】
2014138244.tif 000009