(57)【要約】  本発明は、ノードを通過するフローの数を削減し該ノードに登録されるフロー情報のエントリ数の削減を可能とする。配下のノードのフローを制御するコントローラが、ノードを通過するフローを、該フローが通っていたノードを通らない別の代替経路に移す際に、移動対象のフローに対応する経路の送信元と宛先が一致し、移動対象のフローが通っていた前記ノードを通らない代替経路候補を求め、代替経路候補の中から予め定められた基準にしたがって代替経路を決定し、代替経路上の各ノードのフローを集約する（図２）。
2011043312.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードのフローを制御するコントローラを用いたネットワーク制御方法であって、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、移動対象の前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定し、
前記代替経路上の各ノードのフローを集約する、ことを特徴とするネットワーク制御方法。
【請求項２】
前記コントローラは、
前記フローに対する前記ノードでの動作を規定するフロー情報を、前記フローに対応した経路上の各ノードにそれぞれ設定し、
前記ノードは、
前記コントローラによりそれぞれ設定され、前記ノードを通過するフローの本数に対応したエントリ数のフロー情報を保持し、
前記コントローラは、
前記代替経路上の各ノードのフローを集約する際、
前記代替経路上の前記各ノードにおける前記フローに対応するフロー情報のエントリの集約を行う、ことを特徴とする請求項１記載のネットワーク制御方法。
【請求項３】
前記コントローラは、複数の前記代替経路候補の中から、前記代替経路候補上のノードのフロー情報のエントリ数に基づき、前記代替経路を決定する、ことを特徴とする請求項１又は２記載のネットワーク制御方法。
【請求項４】
前記コントローラは、前記代替経路候補上の各ノードのフロー情報のエントリ数の総計を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の総計が他よりも小さい代替経路候補を前記代替経路と決定する、ことを特徴とする請求項３記載のネットワーク制御方法。
【請求項５】
前記コントローラは、複数の前記代替経路候補上の各ノードのフロー情報のエントリ数の最大値を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の最大値が他よりも小さい前記代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項３記載のネットワーク制御方法。
【請求項６】
前記コントローラは、複数の前記代替経路候補の中から、前記代替経路候補上のノードのトラフィック量に基づき、前記代替経路を決定する、ことを特徴とする請求項１又は２記載のネットワーク制御方法。
【請求項７】
前記コントローラは、前記代替経路候補上の各ノードのトラフィック量の総計を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の総計が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項６記載のネットワーク制御方法。
【請求項８】
前記コントローラは、前記代替経路候補上の各ノードのトラフィック量の最大値を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の最大値が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項６記載のネットワーク制御方法。
【請求項９】
前記コントローラは、前記代替経路候補上の各ノードに既に設定されているフロー情報を参照し、前記代替経路候補上の前記各ノードのフロー情報のエントリが、前記ノードを通過し移動対象の前記フローに対応するフロー情報のエントリと、どの程度集約ができるかを求め、複数の前記代替経路候補のうちから代替経路を決定する、ことを特徴とする請求項２記載のネットワーク制御方法。
【請求項１０】
前記フロー情報は、前記ノードに入力されたパケットのヘッダーと照合するルールと、前記ルールにヒットしたパケットに対する前記ノードでの転送を含む動作を規定するアクションと、を少なくとも含み、
前記コントローラは、前記フローが通っていた前記ノードのフロー情報のエントリのルールとアクションに関して、前記代替経路候補上のノードのそれぞれに対してフロー情報のエントリのアクションと一致したものについて、ルールの一致数を導出し、一致数が最高値のフロー情報のエントリを、集約対象とする、ことを特徴とする請求項９記載のネットワーク制御方法。
【請求項１１】
前記コントローラは、最高値の一致数が同一のフロー情報のエントリが複数ある場合、前記フローが通っていた前記ノードのフロー情報のエントリのルールの要素との一致の組み合わせにしたがって複数の集合に類別し、
複数のグループのうちフロー情報のエントリの数が最も多い集合のフロー情報のエントリを集約対象とし、
複数の前記代替経路候補のそれぞれについて、前記代替経路候補上のノードに関する集約対象のフロー情報のエントリ数の総和に基づき、代替経路を決定する、ことを特徴とする請求項１０記載のネットワーク制御方法。
【請求項１２】
前記コントローラは、前記代替経路上のノードにおいて、集約可能な、複数のフロー情報のエントリについて、ルールのうち一致しない要素の欄をワイルドカードとした新たなフロー情報のエントリを作成して前記ノードに設定登録し、
前記ノードは、前記集約可能なフロー情報のエントリを前記ノードから削除する、ことを特徴とする請求項２乃至１１のいずれか１項に記載のネットワーク制御方法。
【請求項１３】
前記コントローラは、前記ノードを通過するフローを前記代替経路に移す際に、前記ノードが通過するフローを集約した上で、前記代替経路に移す、ことを特徴とする請求項１記載のネットワーク制御方法。
【請求項１４】
コントローラと、
前記コントローラによってフローの制御が行われる複数のノードと、
を備え、
前記コントローラは、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定し、
前記代替経路上の各ノードのフローを集約する、ことを特徴とするネットワークシステム。
【請求項１５】
前記コントローラは、
前記フローに対する前記ノードでの動作を規定するフロー情報を、前記フローに対応した経路上の各ノードにそれぞれ設定し、
前記ノードは、
前記コントローラによって設定され、前記ノードを通過するフロー数に対応したエントリ数のフロー情報を保持し、
前記コントローラは、
前記代替経路上の各ノードのフローを集約する際、
前記代替経路上の前記各ノードにおける前記フローに対応するフロー情報のエントリの集約を行う、ことを特徴とする請求項１４記載のネットワークシステム。
【請求項１６】
前記コントローラは、複数の前記代替経路候補の中から、前記代替経路候補上のノードのフロー情報のエントリ数に基づき、前記代替経路を決定する、ことを特徴とする請求項１５記載のネットワークシステム。
【請求項１７】
前記コントローラは、複数の前記代替経路候補上の各ノードのフロー情報のエントリ数の総計を、前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の総計が他よりも小さい代替経路候補を前記代替経路と決定する、ことを特徴とする請求項１６記載のネットワークシステム。
【請求項１８】
前記コントローラは、複数の前記代替経路候補上の各ノードのフロー情報のエントリ数の最大値を、前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の最大値が他よりも小さい前記代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項１６記載のネットワークシステム。
【請求項１９】
前記コントローラは、複数の前記代替経路候補の中から、前記代替経路候補上のノードのトラフィック量に基づき、前記代替経路を決定する、ことを特徴とする請求項１４又は１５記載のネットワークシステム。
【請求項２０】
前記コントローラは、複数の前記代替経路候補上の各ノードのトラフィック量の総計を、複数の前記代替経路候補のそれぞれについて求め複数の前記代替経路候補の中から、前記トラフィック量の総計が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項１９記載のネットワークシステム。
【請求項２１】
前記コントローラは、前記代替経路候補上の各ノードのトラフィック量の最大値を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の最大値が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項１９記載のネットワークシステム。
【請求項２２】
前記コントローラは、前記代替経路候補上の各ノードに既に設定されているフロー情報を参照し、前記代替経路候補上の前記各ノードのフロー情報のエントリが、前記ノードを通過し移動対象の前記フローに対応するフロー情報のエントリと、どの程度集約ができるかを求め、複数の前記代替経路候補のうちから代替経路を決定する、ことを特徴とする請求項１５記載のネットワークシステム。
【請求項２３】
前記フロー情報は、前記ノードに入力されたパケットのヘッダーと照合するルールと、前記ルールにヒットしたパケットに対する前記ノードでの転送を含む動作を規定するアクションと、を少なくとも含み、
前記コントローラは、前記フローが通っていた前記ノードのフロー情報のエントリのルールとアクションに関して、前記代替経路候補上のノードのそれぞれに対してフロー情報のエントリのアクションと一致したものについて、ルールの一致数を導出し、一致数が最高値のフロー情報のエントリを、集約対象とする、ことを特徴とする請求項２２記載のネットワークシステム。
【請求項２４】
前記コントローラは、最高値の一致数が同一のフロー情報のエントリが複数ある場合、前記フローが通っていた前記ノードのフロー情報のエントリのルールの要素との一致の組み合わせにしたがって複数の集合に類別し、複数のグループのうちフロー情報のエントリの数が最も多い集合のフロー情報のエントリを集約対象とし、
複数の前記代替経路候補のそれぞれについて前記代替経路候補上のノードに関する集約対象のフロー情報のエントリ数の総和に基づき、代替経路を決定する、ことを特徴とする請求項２３記載のネットワークシステム。
【請求項２５】
前記コントローラは、前記代替経路上のノードにおいて、集約可能な、複数のフロー情報のエントリについて、ルールのうち一致しない要素の欄をワイルドカードとした新たなフロー情報のエントリを作成して、前記ノードに設定登録し、
前記ノードは、前記集約可能なフロー情報のエントリを前記ノードから削除する、ことを特徴とする請求項１５乃至２４のいずれか１項に記載のネットワークシステム。
【請求項２６】
前記コントローラは、集約したフロー情報のエントリを記憶する集約経路記憶部を備え、
前記集約経路記憶部は、ノードに対応して、ノードの識別情報と、ノード別の集約フロー情報のテーブルへのポインタを有するエントリを、各ノードに対して備えた集約経路管理テーブルを有し、前記ノード別の集約フロー情報のテーブルは、ノード上の集約フロー情報のエントリと、前記集約フロー情報に集約された元のフロー情報のエントリを指すポインタのリストを含む、ことを特徴とする請求項１４乃至２５のいずれか１項に記載のネットワークシステム。
【請求項２７】
前記集約経路記憶部において、前記フロー情報のエントリへのポインタリストに格納されているポインタの数が２つ以上であれば、前記フロー情報のエントリへのポインタリストに対応する集約フロー情報のエントリは、ポインタでポイントされる複数のフロー情報のエントリが、前記集約したフロー情報のエントリに集約された元のフロー情報であり、
前記フロー情報のエントリへのポインタリストのポインタの数が１の場合、集約が行われていないフロー情報のエントリであり、
前記フロー情報のエントリへのポインタリストのポインタの数が０の場合、該フロー情報のエントリへのポインタリストに対応する集約フロー情報のエントリは、実際に参照されていないため、削除される、ことを特徴とする請求項２６記載のネットワークシステム。
【請求項２８】
前記コントローラは、前記ノードを通過するフローを前記代替経路に移す際に、前記ノードを通過する複数のフローを集約した上で、前記代替経路に移す、ことを特徴とする請求項１４記載のネットワークシステム。
【請求項２９】
配下のノードの状態の変更を制御するノード状態変更部と、
フローに対するノードでの動作を規定するフロー情報を、前記フローに対応した経路上の各ノードにそれぞれ設定するフロー情報設定部と、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定する代替経路算出部と、
前記代替経路上の各ノードのフローを集約する経路集約実行部と、
を備えている、ことを特徴とするコントローラ。
【請求項３０】
前記ノードには、前記ノードを通過するフロー数分に対応したエントリ数のフロー情報が設定され、
前記経路集約実行部は、
前記代替経路上の各ノードのフローを集約する際、前記代替経路上の前記各ノードにおける前記フローに対応するフロー情報のエントリの集約を行う、ことを特徴とする請求項２９記載のコントローラ。
【請求項３１】
前記代替経路算出部は、複数の前記代替経路候補の中から、前記代替経路候補上のノードのフロー情報のエントリ数に基づき、前記代替経路を決定する、ことを特徴とする請求項３０記載のコントローラ。
【請求項３２】
前記代替経路算出部は、複数の前記代替経路候補上の各ノードのフロー情報のエントリ数の総計を、前記代替経路候補のそれぞれについて求め、
前記代替経路候補の中から、前記フロー情報のエントリ数の総計が他よりも小さい代替経路候補を前記代替経路と決定する、ことを特徴とする請求項３１記載のコントローラ。
【請求項３３】
前記代替経路算出部は、前記代替経路候補上の各ノードのフロー情報のエントリ数の最大値を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の最大値が他よりも小さい前記代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項３１記載のコントローラ。
【請求項３４】
前記ノードのトラフィック量を取得して管理するトラフィック管理部を備え、
前記代替経路算出部は、複数の前記代替経路候補の中から、前記代替経路候補上のノードのトラフィック量に基づき、前記代替経路を決定する、ことを特徴とする請求項３０記載のコントローラ。
【請求項３５】
前記代替経路算出部は、前記代替経路候補上の各ノードのトラフィック量の総計を、前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の総計が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項３４記載のコントローラ。
【請求項３６】
前記代替経路算出部は、前記代替経路候補上の各ノードのトラフィック量の最大値を、前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の最大値が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項３４記載のコントローラ。
【請求項３７】
前記代替経路算出部は、前記代替経路候補上の各ノードに既に設定されているフロー情報のエントリを参照し、前記代替経路候補上の前記各ノードのフロー情報のエントリが、前記ノードを通過し移動対象の前記フローに対応するフロー情報のエントリと、どの程度集約ができるかを求め、前記代替経路候補のうちから代替経路を決定する、ことを特徴とする請求項３０記載のコントローラ。
【請求項３８】
前記フロー情報は、前記ノードに入力されたパケットのヘッダーと照合するルールと、前記ルールにヒットしたパケットに対する前記ノードでの転送を含む動作を規定するアクションと、を少なくとも含み、
前記代替経路算出部は、前記フローが通っていた前記ノードのフロー情報のエントリのルールとアクションに関して、前記代替経路候補上のノードのそれぞれに対してフロー情報のエントリのアクションと一致したものについて、ルールの一致数を導出し、前記一致数が最高値のフロー情報のエントリを集約対象とする、ことを特徴とする請求項３７記載のコントローラ。
【請求項３９】
前記代替経路算出部は、最高値の一致数が同一のフロー情報のエントリが複数ある場合、前記フローが通っていた前記ノードのフロー情報のエントリのルールの要素との一致の組み合わせにしたがって複数の集合に類別し、複数のグループのうちフロー情報のエントリの数が最も多い集合のフロー情報のエントリを集約対象とし、
前記代替経路候補のそれぞれについて前記代替経路候補上のノードに関する集約対象のフロー情報のエントリ数の総和に基づき、代替経路を決定する、ことを特徴とする請求項３８記載のコントローラ。
【請求項４０】
前記経路集約実行部は、前記代替経路上のノードにおいて、集約可能な複数のフロー情報のエントリについて、ルールのうち一致しない要素の欄をワイルドカードとした新たなフロー情報のエントリを作成して前記ノードに設定登録し、前記ノードは、集約可能なフロー情報のエントリを前記ノードから削除する、ことを特徴とする請求項２９乃至３９のいずれか１項に記載のコントローラ。
【請求項４１】
前記経路集約実行部で集約されたフロー情報のエントリを記憶する集約経路記憶部を備え、
前記集約経路記憶部は、ノードに対応して、ノードの識別情報と、ノード別の集約フロー情報のテーブルへのポインタを有するエントリを、各ノードに対して備えた集約経路管理テーブルを有し、
前記ノード別の集約フロー情報のテーブルは、ノード上の集約フロー情報のエントリと、前記集約フロー情報に集約された元のフロー情報のエントリを指すポインタのリストを含む、ことを特徴とする請求項２９乃至４０のいずれか１項に記載のコントローラ。
【請求項４２】
前記集約経路記憶部において、前記フロー情報のエントリへのポインタリストに格納されているポインタの数が２つ以上であれば、前記フロー情報のエントリへのポインタリストに対応する集約フロー情報のエントリは、ポインタでポイントされる複数のフロー情報のエントリが、前記集約フロー情報のエントリに集約されたものであり、
前記フロー情報のエントリへのポインタリストのポインタの数が１の場合、集約が行われていないフロー情報のエントリであり、
前記フロー情報のエントリへのポインタリストのポインタの数が０の場合、該フロー情報のエントリへのポインタリストに対応する集約フロー情報のエントリは実際に参照されていないため、削除される、ことを特徴とする請求項４１に記載のコントローラ。
【請求項４３】
前記ノードを通過するフローを前記代替経路に移す際に、前記経路集約実行部が、前記ノードを通過する複数のフローを集約した上で、前記代替経路に移す、ことを特徴とする請求項２９記載のコントローラ。
【請求項４４】
配下のノードの状態の変更を制御するノード状態変更処理と、
フローに対するノードでの動作を規定するフロー情報を、前記フローに対応した経路上の各ノードにそれぞれ設定するフロー情報設定処理と、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定する代替経路算出処理と、
前記代替経路上の各ノードのフローを集約する経路集約実行処理と、
をコントローラに実行させるプログラム。
【請求項４５】
前記ノードには、前記ノードを通過するフロー数分に対応したエントリ数のフロー情報が設定され、
前記経路集約実行処理は、
前記代替経路上の各ノードのフローを集約する際、
前記代替経路上の前記各ノードにおける前記フローに対応するフロー情報のエントリの集約を行う、ことを特徴とする請求項４４記載のプログラム。
【請求項４６】
前記代替経路算出処理は、複数の前記代替経路候補の中から、前記代替経路候補上のノードのフロー情報のエントリ数に基づき、前記代替経路を決定する、ことを特徴とする請求項４５記載のプログラム。
【請求項４７】
前記代替経路算出処理は、前記代替経路候補上の各ノードのフロー情報のエントリ数の総計を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の総計が他よりも小さい代替経路候補を前記代替経路と決定する、ことを特徴とする請求項４６記載のプログラム。
【請求項４８】
前記代替経路算出処理は、前記代替経路候補上の各ノードのフロー情報のエントリ数の最大値を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記フロー情報のエントリ数の最大値が他よりも小さい前記代替経路候補を前記代替経路と決定する、ことを特徴とする請求項４６記載のプログラム。
【請求項４９】
前記ノードのトラフィック量を取得して管理するトラフィック管理処理を備え、
前記代替経路算出処理は、複数の前記代替経路候補の中から、前記代替経路候補上のノードのトラフィック量に基づき、前記代替経路を決定する、ことを特徴とする請求項４５又は４６記載のプログラム。
【請求項５０】
前記代替経路算出処理は、前記代替経路候補上の各ノードのトラフィック量の総計を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の総計が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項４９記載のプログラム。
【請求項５１】
前記代替経路算出処理は、前記代替経路候補上の各ノードのトラフィック量の最大値を、複数の前記代替経路候補のそれぞれについて求め、
複数の前記代替経路候補の中から、前記トラフィック量の最大値が他よりも小さい代替経路候補を、前記代替経路と決定する、ことを特徴とする請求項４９記載のプログラム。
【請求項５２】
前記代替経路算出処理は、前記代替経路候補上の各ノードに既に設定されているフロー情報を参照し、前記代替経路候補上の前記各ノードのフロー情報のエントリが、前記ノードを通過し移動対象の前記フローに対応するフロー情報のエントリと、どの程度集約ができるかを求め、複数の前記代替経路候補の中から代替経路を決定する、ことを特徴とする請求項４５記載のプログラム。
【請求項５３】
前記フロー情報は、前記ノードに入力されたパケットのヘッダーと照合するルールと、前記ルールにヒットしたパケットに対する前記ノードでの転送を含む動作を規定するアクションと、を少なくとも含み、
前記代替経路算出処理は、前記フローが通っていた前記ノードのフロー情報のエントリのルールとアクションに関して、前記代替経路候補上のノードのそれぞれに対してフロー情報のエントリのアクションと一致したものについて、ルールの一致数を導出し、一致数が最高値のフロー情報のエントリを集約対象とする、ことを特徴とする請求項４６記載のプログラム。
【請求項５４】
前記代替経路算出処理は、最高値の一致数が同一のフロー情報のエントリが複数ある場合、前記フローが通っていた前記ノードのフロー情報のエントリのルールの要素との一致の組み合わせにしたがって複数の集合に類別し、複数のグループのうちフロー情報のエントリの数が最も多い集合のフロー情報のエントリを集約対象とし、
複数の前記代替経路候補のそれぞれについて前記代替経路候補上のノードに関する集約対象のフロー情報のエントリ数の総和に基づき、代替経路を決定する、ことを特徴とする請求項５３記載のプログラム。
【請求項５５】
前記経路集約実行処理は、前記代替経路上のノードにおいて、集約可能な複数のフロー情報のエントリについて、ルールのうち一致しない要素の欄をワイルドカードとした新たなフロー情報のエントリを作成して前記ノードに設定登録し、前記ノードは、前記集約可能なフロー情報のエントリを前記ノードから削除する、ことを特徴とする請求項４４乃至５４のいずれか１項に記載のプログラム。
【請求項５６】
前記あるノードを通過するフローを前記代替経路に移す際に、前記経路集約実行処理は、前記あるノードを通過するフローに対応する複数のフローを集約した上で、前記代替経路に移す、ことを特徴とする請求項４４記載のプログラム。
【請求項５７】
請求項４４乃至５６のいずれか１項記載のプログラムを記録したコンピュータで読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２００９−２３２３０７号（２００９年１０月６日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。【０００２】
本発明はネットワークシステムとコントローラ、方法とプログラムに関する。
【背景技術】
【０００３】
プログラマブル化ネットワークアーキテクチャのさきがけともいわれるＯＦＳ（Ｏｐｅｎ  Ｆｌｏｗ  Ｓｗｉｔｃｈ）は現在、例えば大学キャンパスや企業ネットワーク等において実験・実用化研究が行われている。はじめにＯＦＳを概説しておく。スイッチは、パケットのルックアップとフォアワーディングを行うフローテーブルと、コントローラとの通信用のセキュアチャネルを備えている。コントローラはオープンフロープロトコルを用いてセキュアチャネル上でスイッチと通信し、例えばＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍ  Ｉｎｔｅｒｆａｃｅ）レベルでフローを制御する。一例として、スイッチに最初のパケット（ｆｉｒｓｔ  ｐａｃｋｅｔ）が到着すると、該スイッチは、該パケットのヘッダー情報でフローテーブルを検索する。マッチしない場合（ミスヒット）、スイッチは、当該パケットをコントローラにセキュアチャネルで転送（ｆｏｒｗａｒｄ）する。コントローラは、当該パケットの送信先、送信元情報に基づいて、コントローラが管理するネットワークトポロジー情報から、該パケットの経路を決定する。コントローラは、決定した経路に基づいて、経路上の各スイッチに対してそれぞれのフローテーブルを設定する。２番目以降のパケットは、スイッチのフローテーブルにヒットし、コントローラへは転送せず、直接、フローテーブルのエントリで規定される次のスイッチに転送される。以下の概説も含め、ＯＦＳの詳細は、例えば非特許文献１、２等が参照される。【０００４】
スイッチのフローテーブルは、例えば図１９に示すように、パケットヘッダーと照合するルール（Ｒｕｌｅ）と、フローに対する処理を定義したアクション（Ａｃｔｉｏｎ）と、フロー統計情報（Ｓｔａｔｉｓｔｉｃｓ）をフロー毎に有する。パケットヘッダーと照合するルール（Ｒｕｌｅ）には、正確な値（ｅｘａｃｔ）、及びワイルドカード（ｗｉｌｄ  ｃａｒｄ）が用いられる。アクション（Ａｃｔｉｏｎ）は、ルールとマッチしたパケットに適用するアクションである。フロー統計情報は、アクティビティカウンタともいい、アクティブエントリ数、パケットルックアップ数、パケットマッチ数、フロー単位に、受信パケット数、受信バイト数、フローがアクティブな期間、ポート単位で受信パケット、送信パケット、受信バイト、送信バイト、受信ドロップ、送信ドロップ、受信エラー、送信エラー、受信フレームアラインメントエラー、受信オーバーランエラー、受信ＣＲＣ（Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋ）エラー、コリジョン数を含む。スイッチに入力されたパケットはフローテーブルのルールとのマッチ（照合）が行われ、ルールにマッチするエントリが見つかった場合、マッチしたエントリのアクションが当該パケットに対して施される。マッチするエントリが見つからなかった場合、該パケットはセキュアチャネルを介してコントローラに転送され、コントローラは、パケット経路を決定したフローエントリをスイッチへ送信する。スイッチでは、該スイッチのフローエントリに対して、フローエントリの追加、変更、削除を行う。【０００５】
パケットのヘッダーの所定のフィールドは、スイッチのフローテーブルのルールとの照合（マッチ）に用いられる。マッチ対象の情報は、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）  ＤＡ（ＭＡＣディスティネーションアドレス）、ＭＡＣ  ＳＡ（ＭＡＣソースアドレス）、Ｅｈｅｒｎｅｔタイプ（ＴＰＩＤ）、ＶＬＡＮ  ＩＤ（Ｖｉｒｔｕａｌ  ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）  ＩＤ）、ＶＬＡＮ  ＴＹＰＥ（優先度）、ＩＰ  ＳＡ（ＩＰソースアドレス）、ＩＰ  ＤＡ（ＩＰディスティネーションアドレス）、ＩＰプロトコル、Ｓｏｕｒｃｅ  Ｐｏｒｔ（ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）／ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）ソースポート、あるいは、ＩＣＭＰ（Ｉｎｔｅｒｎｅｔ  Ｃｏｎｔｒｏｌ  Ｍｅｓｓａｇｅ  Ｐｒｏｔｏｃｏｌ）  Ｔｙｐｅ）、Ｄｅｓｔｉｎａｔｉｏｎ  ｐｏｒｔ（ＴＣＰ／ＵＤＰディスティネーションポート、あるいは、ＩＣＭＰ  Ｃｏｄｅ）を含む（図２０参照）。【０００６】
図２１に、アクション名とアクションの内容を例示する。ＯＵＴＰＵＴは、指定ポート（インタフェース）に出力する。ＳＥＴ＿ＶＬＡＮ＿ＶＩＤからＳＥＴ＿ＴＰ＿ＤＳＴは、パケットヘッダーのフィールドを修正するアクションである。また、スイッチは、物理ポートと以下の仮想ポートへ、パケットを転送（Ｆｏｒｗａｒｄ）する。図２２に、仮想ポートを例示する。ＩＮ＿ＰＯＲＴは、パケットを入力ポートに出力する。ＮＯＲＭＡＬは、スイッチがサポートする既存の転送パスを用いて処理する。ＦＬＯＯＤは、パケットが入来したポートを除く通信可能状態（Ｆｏｒｗａｒｄｉｎｇ状態）の全てのポートに転送する。ＡＬＬは、パケットが入来したポートを除くポートに転送する。ＣＯＮＴＲＯＬＬＥＲは、パケットをカプセル化しセキュアチャネルを介してコントローラに送信する。ＬＯＣＡＬは、パケットをスイッチ自身のローカルネットワークスタックに送信する。アクションが指定されないフローエントリにマッチしたパケットはドロップ（廃棄）される。なお、本明細書では、フローエントリのルール、アクション、フロー統計情報からなるフロー情報を「フローエンティティ」という。本明細書では、フロー統計情報は、発明の主題として扱われないため、フローエンティティとしてフロー統計情報は省略され、ルール、アクションが示される。フローエンティティを格納するテーブルを、フローエンティティテーブルという。【０００７】
特許文献１には、フローテーブルに宛先ＩＰアドレスのみからなるテーブルと宛先ＩＰアドレスと送信元ＩＰアドレスの組からなるテーブルとを設け、フローの内容に応じて２つのテーブルを使い分け、段階的に送信元ＩＰアドレスやＬ４ポート番号を追加登録していくことで、きめ細かなフロー制御を行うとともにフローテーブルの増大を防ぐＩＰフロー多段ハッシュ装置が開示されているが、フローの削除、変更を行うものではない。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００４−５６３４０号公報
【非特許文献】
【０００９】
【非特許文献１】Nick McKeownその他、"OpenFlow: Enabling Innovation in Campus Networks", March 14, 2008 ＜インターネット  ＵＲＬ：http://www.openflowswitch.org//documents/openflow-wp-latest.pdf＞
【非特許文献２】"OpenFlow Switch Specification" Version 0.9.0. (Wire Protocol 0x98) July 20, 2009 ＜インターネット  ＵＲＬ：  http://www.openflowswitch.org/documents/openflow-spec-v0.9.0.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述のように、コントローラにより各ノードを制御して経路を決定するネットワークにおいて、コントローラは、パケットを転送するための経路を決定し、該経路上の各ノードに対して、パケットを、該経路に沿って、転送するためのフローエンティティの設定を指示する。しかし、各ノードのフローエンティティテーブルに登録可能なフローエンティティのエントリ数には上限がある。【００１１】
一例として、コントローラによって集中制御されるスイッチにおいて、パケットヘッダーと、フローエンティティテーブルと、の照合（マッチ）は、例えばＣＡＭ（コンテンツアドレッサブルメモリ）等のハードウエアで実装される場合がある。この場合、フローエンティティテーブルがオーバーフロー状態のときに、コントローラで、新たにフローを決めても、当該スイッチのフローエンティティテーブルは満杯であり、当該フローに対応する新たなフローエンティティを登録することはできない。このため、例えば廃棄されることになる。この結果、ネットワークのパケット転送性能、品質の劣化を招く。このことからも、フローの移動、集約によるスイッチにおけるフローエンティティの登録数を削減する機能の実現が望まれる。【００１２】
本願発明者らは、鋭意検討した結果、経路設定されたノードを通過するフローの数を削減し該ノードに登録されるフローエンティティの数を削減可能とする手法を今回創案したので、以下に提示する。【００１３】
なお、フローの集約とは、あるノードを通る複数のフローを１つのフローに統合し、当該ノードに登録される複数のフローにそれぞれ対応する複数エントリのフロー情報を、統合化した１つのフローに対応して１つのエントリに統合することをいう。
【課題を解決するための手段】
【００１４】
本願で開示される発明は課題を解決するため、概略以下の構成とされる。【００１５】
本発明によれば、配下の複数のノードのフローを制御するコントローラが、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、移動対象の前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定し、
前記代替経路上の各ノードのフローを集約するネットワーク制御方法が提供される。【００１６】
本発明によれば、コントローラによってフローの制御が行われる複数のノードと、
前記コントローラと、
を備え、
前記コントローラは、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定し、
前記代替経路上の各ノードのフローを集約するネットワークシステムが提供される。【００１７】
本発明によれば、配下のノードの状態の変更を制御するノード状態変更部と、
フローに対するノードでの動作を規定するフロー情報を、前記フローに対応した経路上の各ノードにそれぞれ設定を指示するフロー情報設定部と、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、前記フローが通っていた前記あるノードを通らない代替経路候補を複数求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定する代替経路算出部と、
前記代替経路上の各ノードのフローを集約する経路集約実行部と、
を備えているコントローラが提供される。【００１８】
本発明によれば、配下のノードの状態の変更を制御するノード状態変更処理と、
フローに対するノードでの動作を規定するフロー情報を、前記フローに対応した経路上の各ノードにそれぞれ設定するフロー情報設定処理と、
あるノードを通過するフローを、前記フローが通っていた前記あるノードを通らない別の代替経路に移す際に、
移動対象の前記フローに対応する経路の送信元と宛先が一致し、前記フローが通っていた前記あるノードを通らない代替経路候補を求め、
複数の前記代替経路候補の中から予め定められた基準にしたがって代替経路を決定する代替経路算出処理と、
前記代替経路上の各ノードのフローを集約する経路集約実行処理と、
をコントローラに実行させるプログラムが提供される。【００１９】
また本発明によれば該プログラムを記録したコンピュータで読取可能な記録媒体も提供される。
【発明の効果】
【００２０】
本発明によれば、ノードを通過するフローの数を削減し該ノードに登録されるフロー情報のエントリ数を削減することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態のネットワークシステムの構成を示す図である。
【図２】本発明におけるフローの集約を説明する図である。
【図３】本発明の一実施形態のコントローラの構成を示す図である。
【図４】本発明の一実施形態のスイッチの構成を示す図である。
【図５】本発明の一実施形態のコントローラにおける有効経路情報記憶部のデータ構造の一例を示す図である。
【図６】本発明の一実施形態のコントローラにおける集約経路記憶部のデータ構造の一例を示す図である。
【図７】本発明の一実施形態のスイッチのフローエンティティテーブルを示す図である。
【図８】本発明の一実施形態の動作を示す流れ図である。
【図９】ネットワークトポロジーとフローの一例を示す図である。
【図１０】スイッチを通るフローを移動する場合の代替経路候補を示す図である。
【図１１】スイッチのフローエンティティ数を影響度として経路を選択する場合を説明する図である。
【図１２】スイッチのフローエンティティ数の最大値を影響度として経路を選択する場合を説明する図である。
【図１３】本発明の別の実施形態のコントローラの構成を示す図である。
【図１４】本発明の別の実施形態のスイッチの構成を示す図である。
【図１５】スイッチのトラフィック量を影響度として経路を選択する場合を説明する図である。
【図１６】集約可能なフローエンティティ数を影響度として経路を選択する場合の手順を説明する流れ図である。
【図１７】集約可能フローエンティティの判定を説明する図である。
【図１８】図８のステップＳ１１の手順を示す図である。
【図１９】ＯＦＳのフローエンティティを説明する図である。
【図２０】パケットヘッダーのマッチフィールドを説明する図である。
【図２１】フローエンティティのアクション（Ｆｉｅｌｄ  Ｍｏｄｉｆｙ）を例示する図である。
【図２２】フローエンティティのアクション（仮想ポート）を例示する図である。
【発明を実施するための形態】
【００２２】
本発明の実施形態について説明する。
【００２３】
本発明においては、配下のノード（例えば図１のスイッチ１０）のフローを制御するコントローラ２０が、ノードを通過するフローを、該フローが通っていたノードを通らず別のノードを通る別の代替経路に移す際に、移動対象のフローに対応する経路の送信元と宛先が一致し、移動対象のフローが通っていたノードを通らない代替経路候補を求め、代替経路候補の中から予め定められた基準にしたがって代替経路を決定し、代替経路上の各ノードのフローを集約する。
【００２４】
本発明において、コントローラは、配下のノード（例えば図１のスイッチ１０）の状態の変更を制御する状態変更部（スイッチ状態変更部２０６）と、
フローに対するノードでの動作を規定するフロー情報を、フローに対応した経路上の各ノードにそれぞれ設定を指示するフロー情報設定部（フローエンティティ設定部２０２）と、
あるノードを通過するフローを、フローが通っていたノードを通らない別の代替経路に移す際に、
移動対象のフローに対応する経路の送信元と宛先が一致し、フローが通っていたノードを通らない代替経路候補を求め、
代替経路候補の中から予め定められた基準にしたがって代替経路を決定する代替経路算出部（２１０）と、
代替経路上の各ノードのフローを集約する経路集約部（２０７、２０８）と、を含む。
【００２５】
本発明において、コントローラ（２０）は、フローに対するノードでの動作を規定するフロー情報を設定するよう、フローに対応した経路上の各ノードにそれぞれ指示し、
各ノード（図１の１０）は、コントローラ（２０）からの指示により、ノードを通過するフロー数に対応したエントリ数のフロー情報をテーブルに保持する。コントローラ（２０）は、代替経路上の各ノードのフローを集約する際、代替経路上の各ノードにおけるフローに対応するフロー情報のエントリの集約を行う。
【００２６】
本発明において、コントローラ（２０）は、代替経路候補の中から、代替経路候補上のノードのフロー情報のエントリ数に基づき、代替経路を決定する。この場合、コントローラ２０は、代替経路候補上の各ノードのフロー情報のエントリ数の総計を、代替経路候補のそれぞれについて求め、代替経路候補の中から、フロー情報のエントリ数の総計が他よりも小さい代替経路候補を代替経路と決定するようにしてもよい。あるいは、コントローラ（２０）は、代替経路候補上の各ノードのフロー情報のエントリ数の最大値を、代替経路候補のそれぞれについて求め、代替経路候補の中から、フロー情報のエントリ数の最大値が他よりも小さい代替経路候補を、代替経路と決定するようにしてもよい。
【００２７】
本発明において、コントローラ２０は、代替経路候補の中から、代替経路候補上のノードのトラフィック量に基づき、代替経路を決定する構成としてもよい。この場合、コントローラ（２０）は、代替経路候補上の各ノードのトラフィック量の総計を、代替経路候補のそれぞれについて求め、代替経路候補の中から、トラフィック量の総計が他よりも小さい代替経路候補を、代替経路と決定するようにしてもよい。あるいは、コントローラ（２０）は、代替経路候補上の各ノードのトラフィック量の最大値を、代替経路候補のそれぞれについて求め、代替経路候補の中から、トラフィック量の最大値が他よりも小さい代替経路候補を、代替経路と決定するようにしてもよい。
【００２８】
本発明において、コントローラ（２０）は、代替経路候補上の各ノードに既に設定されているフロー情報を参照し、代替経路候補上の各ノードのフロー情報のエントリが、ノードを通過し移動対象のフローに対応するフロー情報のエントリと、どの程度集約ができるかを求め、代替経路候補のうちから代替経路を決定するようにしてもよい。
【００２９】
本発明において、フロー情報は、ノードに入力されたパケットのヘッダーと照合するルールと、ルールにヒットしたパケットに対するノードでの転送を含む動作を規定するアクションと、を少なくとも含む。コントローラ（２０）は、フローが通っていたノードのフロー情報のエントリのルールとアクションに関して、代替経路候補上のノードのそれぞれに対してフロー情報のエントリのアクションと一致したものについて、ルールの一致数を導出し、一致数が最高値のフロー情報のエントリを、集約対象とする。
【００３０】
本発明において、コントローラ（２０）は、最高値の一致数が同一のフロー情報のエントリが複数ある場合、フローが通っていたノードのフロー情報のエントリのルールの要素との一致の組み合わせにしたがって複数の集合に類別し、複数のグループのうちフロー情報のエントリの数が最も多い集合のフロー情報のエントリを集約対象とし、代替経路候補のそれぞれについて代替経路候補上のノードに関する集約対象のフロー情報のエントリ数の総和に基づき、代替経路を決定するようにしてもよい。
【００３１】
本発明において、コントローラ（２０）は、代替経路上のノードにおいて、集約可能な、複数のフロー情報のエントリについて、ルールのうち一致しない要素の欄をワイルドカードとした新たなフロー情報のエントリを作成し、ノードに設定を指示する。ノードでは、集約可能なフロー情報のエントリは、ノードから削除する。
【００３２】
本発明において、コントローラ（２０）は、ノードを通過するフローを代替経路に移す際に、ノードを通過するフローを集約した上で、代替経路に移すようにしてもよい。
【００３３】
かかる構成の本発明によれば、移動先の代替経路上のノードにおけるフロー情報のエントリ数の増大を抑制している。
【００３４】
このため、本発明によれば、ノードのフロー情報を収容するテーブル等の記憶領域がオーバーフローし、スイッチに新たに入来したパケットに対して、新たなフローを設定できないという事態の発生を回避可能としている。
【００３５】
また、本発明によれば、ノードを通過するフローを、フローが通っていたノードを通らない別の代替経路に移すことで、ノードに設定されていたフロー情報のエントリ数を削減することができる。
【００３６】
さらに、本発明によれば、ノードを通るフローを別の代替経路に移動させることで、ノードにおいて空きポート等の保守、調整等を可能とし、ノードを通るフローを別の代替経路に移動させることで、ノードをネットワークから外し、保守、調整等を行うことができる。さらにまた、本発明によれば、フローの片寄せ等（例えば夜間運転時等）を行うことで低消費電力化にも、貢献する。以下実施形態に即して説明する。なお、以下の実施例では、コントローラによってフローの制御が行われるノードを、スイッチとして説明するが、本発明においてノードはかかる構成に制限されるものでないことは勿論である。
【００３７】
＜ネットワークシステム構成＞
図１は、本発明が適用されるネットワークの一例を示す図である。図１において、スイッチ（ＯＦＳ：Ｏｐｅｎ  Ｆｌｏｗ  Ｓｗｉｔｃｈ）１０は、コントローラ（Ｃｏｎｔｒｏｌｌｅｒ）２０から設定されたフロー情報（ルール＋アクションを含む、以下、「フローエンティティ」という）を保持し、到着したパケットが該当するルールをフローエンティティテーブル（フローテーブル）から検索し、一致した場合アクションを実行する。スイッチ（ＯＦＳ）１０は、到着したパケットがフローエンティティテーブルのルールに一致しない場合、コントローラ２０に通知する。フローには、優先度があり優先度が高いものが有効となる。コントローラ２０は、スイッチ（ＯＦＳ）１０から送られてきたパケットに基づき、適切な経路を算出し、フローを生成、経路となるスイッチ群にフローの設定を指示する。なお、図１において、スイッチ（ＯＦＳ）１０の接続構成は、一例でしかなく、ＦａｔＴｒｅｅ、ＨｙｐｅｒＣｕｂｅ等、ノード等との経路が複数存在すればよい。図中のノード（Ｎｏｄｅ）３０は、サーバ、ロードバランサ、ファイアウォール、ストレージ（ＮＡＳ（Ｎｅｔｗｏｒｋ  Ａｔｔａｃｈｅｄ  Ｓｔｏｒａｇｅ）、ＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、クラスタストレージ等の分散ストレージのノード、２つ以上のネットワークインタフェースを持つ。なお、図１において、ノード３０は、複数のスイッチ１０に対してフローの制御を行うコントローラ２０からは、フローの制御は受けないノードである。ただし、ノード３０はコントローラ２０と通信する機能を備えた構成としてもよいことは勿論である。また、図１では簡単のため、１台のコントローラ２０でスイッチ１０を制御する構成として記載されているが、複数のコントローラがそれぞれ配下の１つ又は複数のスイッチを制御する構成としてもよいことは勿論である。
【００３８】
本発明の実施形態において、コントローラ２０は、スイッチ１０及びノード３０の接続状態をトポロジー情報として保持する。また、設定した経路の情報を有効経路情報として保持する。
【００３９】
コントローラ２０は、すべてのフローがどの経路を通過しているかを管理している。フローの識別には、ＭＡＣアドレス、ＩＰアドレス、ポート番号等を用いることができる。ここで、集約とは、パケットのフローに関して、フローエンティティのルールとマッチが行われるパケットヘッダーに対して同一の宛先アドレスで、他のフィールドが異なる複数のフローをまとめて一つのフローとして扱うことをいう。この場合、宛先アドレス以外のフィールドを、ａｎｙ（任意）として扱う。フローエンティティのルールはｗｉｌｄ  ｃａｒｄが設定される。
【００４０】
＜経路張替えとフローの集約＞
本発明の実施形態において、図２に示すように、経路（パス）の張替え時に、フローの集約を考慮することで、スイッチのフローエンティティテーブルのエントリ数を削減する。図２に示す例では、コントローラ２０は、スイッチＸを通過するフロー１、２、３を別に移す際に、フロー１、２は集約可能であるため、まとめて、１つのフローとしてスイッチＹを通るフローに移し、フロー３は、スイッチＺを通るフローに移している。フローの移動には、以下の２つのモードがある。
【００４１】
（Ａ）あるスイッチを通過するフロー群を別に移す際に、集約可能なフロー毎にまとめて移動する。
【００４２】
（Ｂ）移動先のスイッチ候補を参照し、各スイッチを通過する既存のフローとの集約を考慮したうえで、どちらに移動するかを決定する。
【００４３】
（Ａ）の場合、移動元からは集約可能な単位でフローが移動するため、移動先のスイッチにおいて、集約可能な単位でフローに対するフローエンティティの増大は１エントリとなる。一方、（Ｂ）の場合、移動先のスイッチにおいて、移動してきたフローに対応するフローエンティティは新たに作成されず、既存のフローエンティティと集約されるため、フローエンティティの増大が抑制できる。
【００４４】
なお、（Ａ）と（Ｂ）と混在させてもよい。この場合、集約可能な単位でまとめて移動先にフローの移動が行われ、且つ、移動先のスイッチを通過する既存のフローと集約可能とされる。このため、移動先スイッチにおいて、フロー移動後も、フローエンティティの増大が抑制できる。
【００４５】
なお、図２において、スイッチＸを通るフローのうち、１つのフローのみを、他のスイッチに移動させ、他のフローは元の通りスイッチＸを通るようにしてもよい。あるいは、スイッチＸを通る全てのフローを別の経路に移動させてもよい。この場合、スイッチＸをネットワーク上の経路から外し、他の経路に迂回させることに対応する。
【００４６】
＜フローの集約＞
次に、フローの集約の概略を説明する。
【００４７】
コントローラ２０は、管理者から指定された移動元のスイッチを受け取る。コントローラ２０は、移動元スイッチを通過するフローを出口が同じ（例えば宛先ＩＰアドレスが同じ）であるフロー毎にまとめる。
【００４８】
以下の処理は、このまとめたフロー群毎に行う。コントローラ２０は、移動先となる代替スイッチ候補を決定する。
【００４９】
コントローラ２０は、移動先スイッチ候補から、最適な移動先スイッチを決定する。
・負荷の最も小さなスイッチを最適なスイッチとする。
・各スイッチを通過しているフローのうち、出口が移動対象のフローと同じフローの数を計数する。このフロー数が一番大きいスイッチを最適なスイッチを移動先のスイッチとする。
【００５０】
コントローラ２０は、移動対象のフロー群が移動先のスイッチを通過するように、経路の変更を行う。移動対象のフロー群のフローエンティティは１つのフローエンティティに集約され、集約された状態のフローエンティティが、移動先のスイッチのフローエンティティテーブルに登録される。この際に、可能であれば、移動先のスイッチ中のフローに関しても、移動してくるフロー群と集約可能なものを集約する。
【００５１】
＜コントローラの構成例＞
次に、図１のコントローラ２０の構成を説明する。図３は、コントローラ２０の構成例を示す図である。コントローラ２０は、スイッチ１０からのパケットを受信するパケット処理部２０１と、スイッチ１０に対してフローエンティティを設定するフローエンティティ設定部２０２と、経路構成情報（経路を作成する契機となったパケットを入力するスイッチ情報、該パケットのヘッダー情報、該経路を構成するスイッチ識別情報とそのフローエンティティ）を記憶する有効経路記憶部２０３と、ノード、スイッチのネットワークトポロジーを記憶するトポロジー情報２０４と、経路を算出する経路算出部２０５と、スイッチの状態を変更するスイッチ状態変更部２０６と、経路の集約を行う経路集約実行部２０７と、集約された経路を記憶する集約経路記憶部２０８と、移動先となる代替スイッチを含む経路を算出する代替経路算出部２１０を備えている。代替経路算出部２１０は、トポロジー情報２０４を参照して、移動対象フローに対応する経路の送信元と宛先が一致する代替経路候補を算出する代替経路候補算出部２１１と、代替経路候補の影響度を算出する影響度算出部２１２と、各代替経路候補の影響度から代替経路を決定する代替経路決定部２１３を備えている。コントローラ２０の各部はコントローラ２０（コンピュータ）上で実行させるプログラムによりその機能を実現するようにしてもよいことは勿論である。
【００５２】
＜スイッチの構成例＞
図４は、スイッチ１０の構成例を示す図である。スイッチ１０は、パケット処理部１０１と、フローエンティティテーブル（「フローテーブル」ともいう）１０２と、最初のパケットをコントローラに通知するパケット通知部１０３と、コントローラ２０から指示されたフローエンティティの設定を行うフローエンティティ設定部１０４とを備えている。スイッチ１０として、ＯＦＳとして機能可能な、レイヤ２スイッチや、レイヤ３スイッチ、ルータ等として動作するノードを適用することが可能である。
【００５３】
＜有効経路記憶部＞
次に、有効経路記憶部２０３で記憶する情報を説明する。図５は、有効経路記憶部２０３に格納されるデータのデータ構造の一例を示す図である。
【００５４】
＜経路管理テーブル＞
経路管理テーブルは、経路ごとの経路構成情報を管理するテーブルである。経路管理テーブルには１エントリ毎に１つの経路が対応し、該１つの経路の経路構成情報が対応する。経路管理テーブルの１つのエントリには、経路を形成し、コントローラ２０が該経路を新たに作成する契機となったパケットが入力されたスイッチの情報（スイッチＩＤ、インタフェース）と、該パケットのヘッダー情報と、当該経路に対応する経路構成情報をさすポインタを有する。パケットのヘッダー情報に関して、ソース及びディスティネーションのＩＰアドレスを記録するようにしてもよい。
【００５５】
＜経路構成情報＞
経路構成情報は、経路ごとに、経路を構成するスイッチ群（経路の始点から経路の中間点、終点）の各スイッチについて、スイッチの識別情報と該スイッチに設定されるフローエンティティとの組を有する。経路がｎ個のスイッチから構成される場合、スイッチの識別情報と該スイッチに設定されるフローエンティティおよび集約フローエンティティへのポインタとの組をｎ組有し、これが、経路管理テーブルの該当するエントリのポインタによってポイントされる。経路構成情報を参照することで、現在有効とされる経路がいかなるスイッチから形成されているかがわかる。フローエンティティはルールとアクションを含む（フロー統計情報を含んでもよい）。経路構成情報はテーブル構成としても良いし、スイッチ情報とフローエンティティの組が、経路上の次のスイッチに対応するスイッチ情報とフローエンティティの組をポイントするポインタを備えた線形リスト（リンクドリスト）として構成しても良い。なお、経路算出部２０５で新たな経路が算出された場合、スイッチ状態変更部２０６によって有効経路記憶部２０３の経路管理テーブルに経路構成情報が登録され、経路削除等、無効化された経路は、スイッチ状態変更部２０６によって有効経路記憶部２０３から削除される。
【００５６】
＜集約経路記憶部＞
集約経路記憶部２０８は、経路集約実行部２０７で集約された経路構成情報を記憶する。図６は、集約経路記憶部２０８に格納されるデータ構造の一例を示す図である。集約経路管理テーブルはスイッチ毎にスイッチの識別情報と、スイッチ別の集約フローエンティティテーブルをポイントするポインタ（スイッチ別の集約フローエンティティテーブルへのポインタ）を有する。
【００５７】
スイッチ別の集約フローエンティティテーブルは、集約フローエンティティと、集約フローエンティティに対応するフローエンティティへのポインタリストとの組を複数格納するテーブルである。コントローラ２０の集約経路記憶部２０８に記憶保持される集約フローエンティティテーブル中の複数の集約フローエンティティが、対応するスイッチ１０に、実際に設定登録される。
【００５８】
集約フローエンティティに対応して設けられたフローエンティティへのポインタリストは、当該集約フローエンティティへと集約されているフローエンティティ（図５）を指示するポインタ（いわゆるバックポインタ）が複数格納されているリストである。
【００５９】
フローエンティティへのポインタリストに格納されているポインタの数が２つ以上であれば、当該フローエンティティへのポインタリストに対応する集約フローエンティティは、該ポインタでポイントされる複数のフローエンティティが、該集約フローエンティティに集約されて、作成されたものである。また、フローエンティティへのポインタリストのポインタの数が１の場合、集約が行われていないフローエンティティである。
【００６０】
フローエンティティへのポインタリストのポインタの数が０の場合、該フローエンティティへのポインタリストに対応する集約フローエンティティは実際に参照されていないため、削除される。
【００６１】
経路算出部２０５が算出した経路が経路管理テーブル（図５参照）に登録され、経路構成情報が作成された場合、経路構成情報中の各エントリに対し、以下の動作が行われる。
【００６２】
まず、経路構成情報中の各エントリ中のスイッチの識別情報を参照し、集約経路管理テーブルから対応するスイッチ別集約フローエンティティテーブルを選択する。
【００６３】
さらにスイッチ別集約フローエンティティテーブル中の新たなフィールドに、該当エントリ中のフローエンティティの情報をコピーして格納する。さらにフローエンティティへのポインタに、該当エントリのアドレスを格納する。
【００６４】
次に、経路管理テーブルから経路が削除された場合、削除された経路構成情報中の各エントリに対し、以下の動作が行われる。
【００６５】
該削除された経路構成情のエントリ中の集約フローエンティティへのポインタから集約フローエンティティを参照する。集約フローエンティティに対応するフローエンティティへのポインタリスト中から、該当エントリへのポインタを削除する。この結果、フローエンティティへのポインタリスト中のポインタの数が０になった場合、この集約フローエンティティ自体を削除する。
【００６６】
＜フローエンティティテーブル＞
図７は、スイッチ１０に記憶されるフローエンティティテーブル１０２の構成例を示す図である。フローエンティティテーブルは、コントローラ２０から指示されたフローエンティティをスイッチ１０が記憶保持するテーブルである。ｎ本の異なるフローがスイッチ１０を通るとき、スイッチ１０には、各フローに対応したｎ個のフローエンティティを保持するが、本実施形態によりフローの縮約が行われた場合、１個のフローエンティティが複数のフローに多重に対応することになる。なお、図７では、フローエンティティ＝｜ルール｜アクション｜とされ、１つのフローエンティティが１つのアクションを含む構成として例示されているが、本実施形態において、１つのフローエンティティが複数のアクションを含む構成、すなわち、フローエンティティ＝｜ルール｜アクション１｜アクション２｜・・・｜アクションｍ｜  （ただし、ｍは２以上の所定の整数）としてもよいことは勿論である。
【００６７】
フローエンティティテーブル１０２のフローエンティティは、ルール、アクションを含む。ルールは、
・インプットインタフェース（ポート）
・ＭＡＣソースアドレス
・ＭＡＣディスティネーションアドレス
・ＶＬＡＮ（Ｖｉｒｔｕａｌ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）  ＩＤ、
・ＴＹＰＥ
・ＩＰソースアドレス
・ＩＰディスティネーションアドレス
・プロトコル（ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）／ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）／ＩＣＰＭ）、ＩＣＭＰ（Ｉｎｔｅｒｎｅｔ  Ｃｏｎｔｒｏｌ  Ｍｅｓｓａｇｅ  Ｐｒｏｔｏｃｏｌ）の場合ＩＣＭＰタイプ、ＩＣＭＰコード、ＴＣＰ／ＵＤＰの場合、ソースポート、ディスティネーションポート
を含む。
【００６８】
アクションは、
・アクションのタイプ
・出力（ＯＵＴＰＵＴ）、
・パケットヘッダーのフィールドの変換（Ｆｉｅｌｄ  Ｍｏｄｉｆｙ）、
を含む。ヘッダーのフィールドの変換は、図２２に示したものがある。
【００６９】
アクションがＯＵＴＰＵＴの場合、出力インタフェース（ポート）を含む。
【００７０】
アクションがヘッダーのフィールドの変換の場合、変更するフィールド、変更する値を含む。
【００７１】
ルールは、全てのフィールドに値を指定しても良いし、個々のフィールド（欄）をワイルドカード（ｗｉｌｄｃａｒｄ）と指定し、当該ｗｉｌｄｃａｒｄが指摘されたフィールドの値を、フローエントリとのマッチング時に、無視するよう指定しても良い（ｗｉｌｄｃａｒｄが指定された欄は常にマッチ）。
【００７２】
＜コントローラの集約動作＞
図８は、本発明の一実施形態の動作を説明するフローチャートである。
【００７３】
ステップ１：スイッチＸを通過するフローＦを、スイッチＸを通過しないように移動させる。すなわち、管理者が、移動させるスイッチＸとフローＦを、コントローラ２０のスイッチ状態変更部２０６に入力として与える（Ｓ１）。
【００７４】
ステップ２：コントローラ２０のスイッチ状態変更部２０６は、フローの送信元、送信先を調べそれぞれＳ、Ｄとし、代替経路算出部２１０に代替経路を算出させる（Ｓ２）。
【００７５】
ステップ３：代替経路算出部２１０の代替経路候補算出部２１１は、トポロジー情報２０４を参照し、スイッチＸを取り除いたトポロジー情報２０４を基に、代替経路候補を計算する（Ｓ３）。その際、フローＦに対応する経路の送信元、宛先が同一の経路を代替経路候補とする。代替経路候補算出部２１１は、有効な経路情報を記憶する有効経路記憶部２０３の経路管理テーブル（図５）の各エントリに登録されている当該経路作成の契機となったパケットヘッダー情報の送信元と宛先情報、該エントリがポイントする経路構成情報のスイッチ識別情報を検索し、既存の経路の中から、スイッチＸを通過するフローＦに対応する代替経路候補を抽出するようにしてもよい。既存の経路の中から代替経路候補が見つからない場合、代替経路候補算出部２１１は、スイッチ状態変更部２０６を介してエラー（代替経路候補が見つからない）を管理者に通知してもよいし、あるいは、トポロジー情報２０４を参照して新しく代替経路を算出してもよい。
【００７６】
ステップ４：代替経路算出部２１０の影響度算出部２１２は、各代替経路候補Ｒｉに対して、以下のステップ５を行う（Ｓ４）。
【００７７】
ステップ５：代替経路候補Ｒｉ毎に影響度Ｅｉを求める（Ｓ５）。
【００７８】
ステップ６：ステップ４からの繰り返し（ループ）（Ｓ６）。
【００７９】
ステップ７：代替経路算出部２１０の代替経路決定部２１３は、例えば影響度Ｅｉの値が最小の代替経路候補Ｒｉを代替経路として選択する（Ｓ７）。
【００８０】
ステップ８：スイッチ状態変更部２０６は、有効経路記憶部２０の旧経路の各スイッチにおけるフローＦに関するフローエンティティを削除するように、フローエンティティ設定部２０２に指示する（Ｓ８）。スイッチ１０のフローエンティティ設定部１０４は、コントローラ２０のフローエンティティ設定部２０２から削除が指示されたフローエンティティを、フローエンティティテーブル１０２から削除する。
【００８１】
ステップ９：代替経路Ｒｉ中の各スイッチに対して以下を行う（Ｓ９）。
【００８２】
ステップ１０：経路集約実行部２０７は、集約可能な経路を集約し、集約経路記憶部２０８に登録する（Ｓ１０）。
【００８３】
ステップ１１：スイッチ状態変更部２０６は、代替経路上のスイッチのフローエンティティを設定するように、フローエンティティ設定部２０２に指示し、フローエンティティ設定部２０２は代替フローに対応した各スイッチ１０のフローエンティティを登録する（Ｓ１１）。スイッチ１０のフローエンティティ設定部１０４は、コントローラ２０のフローエンティティ設定部２０２から設定されたフローエンティティをフローエンティティテーブル１０２に登録する。このとき、コントローラ２０のスイッチ状態変更部２０６は、当該スイッチのフローエンティティテーブルに既に登録されているフローエンティティと集約可能であるか調べ、集約可能であれば、集約する。
【００８４】
ステップ１２：ステップ９からの繰り返し（Ｓ１２）。
【００８５】
ステップＳ５における影響度の定義としては、後述するように各種変形が可能である。
【００８６】
＜経路集約の詳細＞
ステップＳ１０の経路集約実行部２０７の処理手順の一例について以下に説明する。
【００８７】
代替経路Ｒｉ中の各スイッチＳｊに対し、該スイッチに設定されたフローエンティティＥ１〜Ｅｎを１つに集約して、集約フローエンティティＡｘとして集約して登録する場合について説明する。
【００８８】
ステップ１：  有効経路記憶部２０３の経路構成情報中の集約対象となるフローエンティティＥｋのエントリから集約フローエンティティＡｍのポインタ（図５参照）を取得する。
【００８９】
ステップ２：  集約経路記憶部２０８において、集約フローエンティティＡｍのポインタが指すスイッチ別集約フローエンティティテーブルの集約フローエンティティＡｍを参照し、集約フローエンティティＡｍに対応するフローエンティティへのポインタリスト中（図６参照）から、集約対象となるフローエンティティＥｋを指し示すポインタを削除する。
【００９０】
ステップ３：  ステップ２で、集約経路記憶部２０８において、スイッチ別集約フローエンティティテーブルの集約フローエンティティＡｍに対応するフローエンティティへのポインタリスト中のポインタの数が０となった場合、集約フローエンティティＡｍを削除する。さらにスイッチＳｉ中からフローエンティティＡｍを削除するように、フローエンティティ設定部２０２へ指示する。
【００９１】
ステップ４：  ステップ１からステップ３を集約対象となるすべてのフローエンティティＥ１〜Ｅｎに対して実行していなければ、ステップ１へ戻る（Ｅ１〜Ｅｎの繰り返し処理）。
【００９２】
ステップ５：  集約経路記憶部２０８において、集約経路管理テーブル中のスイッチＳｊに対応するスイッチ別集約フローエンティティテーブルに対し、新たな集約フローエンティティＡｘを追加する。さらにスイッチＳｉ中に、フローエンティティＡｘを追加するように、フローエンティティ設定部２０２へ指示する。
【００９３】
ステップ６：  集約経路記憶部２０８において、集約フローエンティティＡｘに対応するフローエンティティへのポインタリスト中に、フローエンティティＥ１〜Ｅｎへのポインタを格納する。
【００９４】
ステップ７：  有効経路記憶部２０３の経路構成情報のフローエンティティＥ１〜Ｅｎのそれぞれに対応する集約フローエンティティへのポインタに、集約フローエンティティＡｘへのポインタを格納する。
【００９５】
＜ネットワーク構成例＞
図９は、本発明が適用されるネットワーク構成を示す図である。以下では、図９において、スイッチＳＷ２を通過するフローＦを移動させる場合について説明する。フローＦの送信元のノード又はスイッチをＳ、送信先（宛先）ノード又はスイッチをＤとする。送信元、送信先は、ＩＰアドレスである場合もあるし、ＭＡＣアドレスである場合もある。このフローＦの現在の経路（パケットのフローＦを実現する経路）は、
Ｓ⇒ＳＷ１⇒ＳＷ２⇒ＳＷ３⇒Ｄ
となる。
【００９６】
この経路（Ｓ⇒ＳＷ１⇒ＳＷ２⇒ＳＷ３⇒Ｄ）は、コントローラ２０の有効経路記憶部２０３の経路管理テーブル（図５参照）において、当該経路作成の契機となったパケットヘッダー情報と、経路管理テーブルのポインタでポイントされる経路構成情報（経路を構成する各スイッチについてスイッチ情報、フローエンティティを含む）として、登録されている。
【００９７】
なお、図９に示すネットワーク構成において、スイッチＳＷ１は不図示の３つのインタフェースで送信元Ｓと、スイッチＳＷ２、ＳＷ５とそれぞれ接続し、スイッチＳＷ２は不図示の４つのインタフェースでスイッチＳＷ１、ＳＷ４、ＳＷ６、ＳＷ３とそれぞれ接続し、スイッチＳＷ４は不図示の３つのインタフェースで送信元Ｓと、スイッチＳＷ２、ＳＷ５とそれぞれ接続し、スイッチＳＷ５は不図示の４つのインタフェースでスイッチＳＷ４、ＳＷ１、ＳＷ３、ＳＷ６とそれぞれ接続し、スイッチＳＷ３は不図示の３つのインタフェースでスイッチＳＷ２、ＳＷ５、宛先Ｄとそれぞれ接続し、スイッチＳＷ６は不図示の３つのインタフェースでスイッチＳＷ２、ＳＷ５、宛先Ｄとそれぞれ接続されるものとする。
【００９８】
＜代替経路候補の例＞
図１０は、代替経路算出部２１０の代替経路候補算出部２１１（図３）による代替経路候補の選出を説明する図である。送信元（Ｓ）、送信先（Ｄ）が、旧経路（フローＦ）と同一となる代替経路候補を選出する。
【００９９】
代替経路候補算出部２１１は、有効経路記憶部２０３の経路管理テーブル（図５参照）において経路毎に設けられ当該経路作成の契機となったパケットヘッダーの送信元（Ｓ）、送信先（Ｄ）を照合し、一致する場合、該経路管理テーブルのエントリがポイントする経路構成情報を探索し、スイッチＳＷ２を経路に含まない場合、当該経路を代替経路候補として導出するようにしてもよい。図１０では、送信元（Ｓ）、送信先（Ｄ）が一致し、スイッチＳＷ２を含まない代替経路候補として以下の３つの経路が求められた。
【０１００】
代替経路候補１：Ｓ⇒ＳＷ１⇒ＳＷ５⇒ＳＷ６⇒ＳＤ
代替経路候補２：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ６⇒ＳＤ
代替経路候補３：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ３⇒ＳＤ
【０１０１】
例えば、図８のステップＳ４で、代替経路候補１が選ばれた場合、図８のステップＳ６−Ｓ９の手順において、順に、スイッチＳＷ１、ＳＷ５、ＳＷ６に対するフローＦへの影響度がそれぞれ求められ、加算された値が代替経路候補１全体の影響度Ｅ１となる。
【０１０２】
＜影響度１＞
図１１は、影響度算出部２１２における影響度Ｅiの定義の第１の例を説明する図である。図１１において、スイッチ（ＳＷ１、ＳＷ３〜ＳＷ６）のフローエンティティテーブル１０２のフローエンティティ数を影響度とする。図１１において、各スイッチＳＷ１〜ＳＷ６に付加された数値は、現在のフローエンティティ数（フローＦの旧経路分を含む）である。また旧は旧経路、候補１、２、３は代替経路候補１、２、３を示している。
【０１０３】
代替経路候補１（図１１の候補１：Ｓ⇒ＳＷ１⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ１は、
Ｅ１＝（８−１＋１）＋（３＋１）＋（４＋１）＝１７    ・・・（１）
となる。
【０１０４】
ここで、（８−１＋１）は、｛スイッチＳＷ１の現在のフローエンティティ数（＝８）｝−｛スイッチＳＷ１の旧経路で削除されるフローエンティティ数分（＝１）｝＋｛スイッチＳＷ１の新経路により追加されるフローエンティティ分（＝１）｝である。
【０１０５】
（３＋１）は、｛スイッチＳＷ５の現在のフローエンティティ数（＝３）｝＋｛スイッチＳＷ５の新経路により追加されるフローエンティティ分（＝１）｝である。スイッチＳＷ５は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１０６】
（４＋１）は、｛スイッチＳＷ６の現在のフローエンティティ数（＝４）｝＋｛スイッチＳＷ５の新経路により追加されるフローエンティティ分（＝１）｝である。スイッチＳＷ６は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１０７】
代替経路候補２（図１１の候補２：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ２は、
Ｅ２＝（５＋１）＋（３＋１）＋（４＋１）＝１５    ・・・（２）
となる。
【０１０８】
ここで、（５＋１）は、｛スイッチＳＷ４の現在のフローエンティティ数（＝５）｝＋｛スイッチＳＷ４の新経路により追加されるフローエンティティ分（＝１）｝である。スイッチＳＷ４は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１０９】
（３＋１）は、｛スイッチＳＷ５の現在のフローエンティティ数（＝３）｝＋｛スイッチＳＷ５の新経路により追加されるフローエンティティ分（＝１）｝である。前述したように、スイッチＳＷ５は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１１０】
（４＋１）は、｛スイッチＳＷ６の現在のフローエンティティ数（＝４）｝＋｛スイッチＳＷ５の新経路により追加されるフローエンティティ分（＝１）｝である。前述したように、スイッチＳＷ６は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１１１】
代替経路候補３（図１１の候補３：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ３⇒ＳＤ）の影響度Ｅ３は、
Ｅ３＝（５＋１）＋（３＋１）＋（７−１＋１）＝１７    ・・・（３）
となる。
【０１１２】
ここで、（５＋１）は、｛スイッチＳＷ４の現在のフローエンティティ数（＝５）｝＋｛スイッチＳＷ４の新経路により追加されるフローエンティティ分（＝１）｝である。スイッチＳＷ４は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１１３】
（３＋１）は、｛スイッチＳＷ５の現在のフローエンティティ数（＝３）｝＋｛スイッチＳＷ５の新経路により追加されるフローエンティティ分（＝１）｝である。前述したように、スイッチＳＷ５は旧経路を通らないため、スイッチＳＷ１の旧経路で削除されるフローエンティティ数分を減算することは行われない。
【０１１４】
（７−１＋１）は、｛スイッチＳＷ３の現在のフローエンティティ数（＝７）｝−｛スイッチＳＷ７の旧経路で削除されるフローエンティティ数分（＝１）｝＋｛スイッチＳＷ７の新経路により追加されるフローエンティティ分（＝１）｝である。
【０１１５】
代替経路決定部２１３は、代替経路候補１、２、３のうち、影響度が最小の代替経路候補２を選択する。
【０１１６】
＜影響度１の変形例＞
なお、変形例として、スイッチにおける新経路によるフローエンティティ数の増加分、旧経路によるフローエンティティ数の減少分を考慮しない場合も考えられる。この場合、
代替経路候補１（図１１の候補１：Ｓ⇒ＳＷ１⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ１は、
Ｅ１＝８＋３＋４＝１５    ・・・（４）
となる。
【０１１７】
代替経路候補２（図１１の候補２：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ２は、
Ｅ２＝５＋３＋４＝１２    ・・・（５）
となる。
【０１１８】
代替経路候補３（図１１の候補３：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ３⇒ＳＤ）の影響度Ｅ３は、
Ｅ３＝５＋３＋７＝１５    ・・・（６）
となる。この場合、代替経路候補２が代替候補として決定される。
【０１１９】
＜影響度２＞
図１２は、影響度の定義の第２の例を説明する図である。この例では、影響度として、フローエンティティ数のＭＡＸ（最大）値を用いている。すなわち、各スイッチのフローエンティティテーブル中のフローエンティティ数の最大値Ｅ２を影響度とする。図１２において、各スイッチに付加された数値は、現在のフローエンティティ数である（フローＦの旧経路分を含む）。
【０１２０】
代替経路候補１（図１２の経路１：Ｓ⇒ＳＷ１⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ１は、
Ｅ１＝ＭＡＸ（（８−１＋１）、（３＋１）、（４＋１））＝８    ・・・（７）
となる。ＭＡＸ（・・・）は引数の要素の最大値を表す。（８−１＋１）、（３＋１）、（４＋１）は式（１）と同一であるため、説明は省略する。
【０１２１】
代替経路候補２（図１２の経路１：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度：
Ｅ２＝ＭＡＸ（（５＋１）、（３＋１）、（４＋１））＝６    ・・・（８）
となる。
【０１２２】
代替経路候補３（図１２の経路３：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ３⇒ＳＤ）の影響度：
Ｅ３＝ＭＡＸ（（５＋１）、（３＋１）、（７−１＋１））＝７    ・・・（９）
となる。
【０１２３】
代替経路決定部２１３は、代替経路候補１、２、３のうち、影響度が最小の代替経路候補２を選択する。変形例として、前述と同様、スイッチにおける新経路によるフローエンティティ数の増加分、旧経路によるフローエンティティ数の減少分を考慮しない場合も考えられる。
【０１２４】
上記実施形態では、代替経路候補の影響度にスイッチのフローエンティティ数を用いていたが、スイッチを通過するトラフィックの量を用いてもよい。
【０１２５】
＜別の実施形態＞
図１３は、本発明の別の実施形態におけるコントローラ２０の構成例を示す図である。本実施形態において、影響度にトラフィック量を使用する。図１３を参照すると、コントローラ２０は、図３の構成のトラフィック量管理部２１４が追加され、影響度算出部２１２Ａは、トラフィック量管理部２１４からの各スイッチのトラフィック量に基づき影響度を算出する。
【０１２６】
図１４は、スイッチ１０の構成を示す図である。図１４を参照すると、図４の構成に、トラフィック量計測部１０５と、コントローラ２０に対してトラフィック量を通知するトラフィック量通知部１０６を備えている。トラフィック量計測部１０５は、所定の単位時間当りの受信パケットのサイズをカウンタ（不図示）に加算する。トラフィック量通知部１０６は、所定の単位時間毎に、カウンタ（不図示）の値（受信データ量）をコントローラ２０に通知し、その後、カウンタ（不図示）をゼロクリアする。カウンタ（不図示）は直ちに受信パケットサイズのカウントを開始してもよいし、所定期間経過後に受信パケットサイズのカウントを開始するようにしてもよい。あるいは、トラフィック量計測部１０５は、所定の単位時間当りの受信パケットのサイズのカウント結果を、何回か平均化し、平均化した受信データ量を、コントローラ２０に通知するようにしてもよい。あるいは、スイッチ１０のトラフィック量計測部１０５に対して、コントローラ１０側から受信パケットサイズのカウント動作開始を指示するようにしてもよいことは勿論である。以下に、影響度算出部２１２Ａの影響度の算出例を説明する。
【０１２７】
＜影響度３＞
図１５は、図１０の代替経路候補１、２、３において、代替経路候補の影響度としてトラフィック量を用いた場合の例を説明する図である。代替経路のスイッチを通過する単位時間当たりのトラフィック量の合計を影響度とする。図１５において、スイッチＳＷ１、ＳＷ２、ＳＷ３、ＳＷ４、ＳＷ５、ＳＷ６に付加した数値８、６、７、５、３、４は、各スイッチを通過する単位時間当たりのトラフィック量（相対量）を表している。
【０１２８】
代替経路候補１（図１５の経路１：Ｓ⇒ＳＷ１⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ１は、
Ｅ１＝８＋３＋４＝１５    ・・・（１０）
となる。
【０１２９】
代替経路候補２（図１５の経路２：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ２は、
Ｅ２＝５＋３＋４＝１２    ・・・（１１）
となる。
【０１３０】
代替経路候補３（図１５の経路３：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ３⇒ＳＤ）の影響度Ｅ３は、
Ｅ３＝５＋３＋７＝１５    ・・・（１２）
となる。
【０１３１】
代替経路決定部２１３は、代替経路候補１、２、３のうち、影響度が最小の代替経路候補２を選択する。
【０１３２】
＜影響度３の変形例＞
変形例として、経路中のトラフィック量が最大のスイッチのトラフィック量を影響度としてもよい。
【０１３３】
この場合、代替経路候補１（図１５の経路１：Ｓ⇒ＳＷ１⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ１は、
Ｅ１＝ＭＡＸ（８、３、４）＝８    ・・・（１３）
となる。
【０１３４】
代替経路候補２（図１５の経路２：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ６⇒ＳＤ）の影響度Ｅ２は、
Ｅ２＝ＭＡＸ（５、３、４）＝５    ・・・（１４）
となる。
【０１３５】
代替経路候補３（図１５の経路３：Ｓ⇒ＳＷ４⇒ＳＷ５⇒ＳＷ３⇒ＳＤ）の影響度Ｅ３は、
Ｅ３＝ＭＡＸ（５、３、７）＝７    ・・・（１５）
となる。
【０１３６】
この場合、代替経路決定部２１３は、代替経路候補１、２、３のうち、影響度が最小の代替経路候補２を選択する。
【０１３７】
＜影響度４＞
あるいは、本発明の別の実施形態において、影響度算出部２１２の影響度としてスイッチのフローエンティティテーブルにおいて、集約可能なフローエンティティの数を用いてもよい。図１６に、代替経路候補影響度算出部２１２の手順を示す。
【０１３８】
ステップ１：スイッチのフローエンティティテーブルにおいて、これから登録しようとするフローの移動対象のスイッチのフローエンティティ（スイッチルール＋アクション）をＦｅとする（Ｓ１０１）。
【０１３９】
ステップ２：上記フローに対して代替経路候補算出部２１１が求めた代替経路候補中の各スイッチに対して影響度算出部２１２は以下の動作を行う（Ｓ１０２）。
【０１４０】
ステップ３：  Ｍ←０（Ｓ１０３）
【０１４１】
ステップ４：代替経路候補中の各スイッチが持つフローエンティティテーブル中の各フローエンティティＦｉに対して、Ｆｅとの以下の比較を行い、それぞれの一致度を求める（Ｓ１０４）。
【０１４２】
ステップ５：代替経路候補中の各スイッチが持つフローエンティティテーブル中の各フローエンティティＦｉとＦｅのアクションを比較し、一致していなければ、一致数（一致度）を０とする（Ｓ１０５）。
【０１４３】
ステップ６：代替経路候補中の各スイッチが持つフローエンティティテーブル中の各フローエンティティＦｉとＦｅのルールのうち同一の要素の数を一致度とする（Ｓ１０６）。
【０１４４】
ステップ７：ステップ４からの繰り返し（Ｓ１０７）。
【０１４５】
ステップ８：一致数が最も高いフローエンティティを、Ｆｅとの集約の対象とする（１つのフローエンティティに集約する）（Ｓ１０８）。ただし、一致度が高いものが複数あった場合、以下のように判断する。
【０１４６】
ステップ９：Ｆｅと一致しているルールが同一のもの同士で集合を作る。ルールにおいてＦｅと同一の要素の数が最大の集合中のフローエンティティ全てを集約対象とする（１つのフローエンティティに集約する）（Ｓ１０９）。
【０１４７】
ステップ１０：集約対象エンティティの数を、Ｍに加算する（Ｓ１１０）。
【０１４８】
ステップ１１：ステップ２からの繰り返し（Ｓ１１１）。
【０１４９】
ステップ１２：Ｍの逆数を、この代替経路候補の影響度とする（Ｓ１１２）。ステップＳ１１２において、Ｍの逆数をとっているのは、図８のステップＳ７で影響度が最小の値の代替候補を選択するという動作にあわせている。
【０１５０】
＜集約可能エンティティ数の判定＞
図１７は、図１６を参照して動作を説明した影響度算出部２１２における集約可能エンティティ数の判定を説明する図である。
【０１５１】
Ｆｅはこれから登録しようとするフローエンティティ（集約対象のフローエンティティ）であり、ルールの宛先ＩＰアドレスはＡ、送信元ＩＰアドレスはＣ、送信元ポートはＸ、宛先ポートはＹである。パケットヘッダーがこのルールにマッチしたパケットに対するアクションはＳＷ５へ転送である。
【０１５２】
スイッチのフローエンティティテーブルのフローエンティティ１は、アクション（ＳＷ１へ転送）がＦｅのアクション（ＳＷ５へ転送）と異なるので、一致数は０である。
【０１５３】
フローエンティティ２は、アクション（ＳＷ５へ転送）がＦｅのアクション（ＳＷ５へ転送）と一致し、ルールは送信元ＩＰアドレスと送信元ポートが一致するので、一致数は２である。
【０１５４】
フローエンティティ３〜９は、アクション（ＳＷ５へ転送）がＦｅのアクション（ＳＷ５へ転送）と一致し、且つ、Ｆｅのルールの一致する要素数である一致数はともに３となる。これらは以下の３つの集合に分けられる。
【０１５５】
集合１：フローエンティティ３、４は、宛先ＩＰアドレス、送信元ＩＰアドレス、送信元ポートが一致する。
【０１５６】
集合２：フローエンティティ５、６は、宛先ＩＰアドレス、送信元ポート、宛先ポートが一致する。
【０１５７】
集合３：フローエンティティ７、８、９は、送信元ＩＰアドレス、送信元ポート、宛先ポートが一致する。
【０１５８】
集合３が、集合の要素（フローエンティティ７、８、９）とその数が最大であるため、集合３が選択され、３がＭに加算される。フローエンティティ７、８、９と登録対象のフローエンティティＦｅが１つのフローエンティティに集約される。
【０１５９】
＜集約したフローエンティティ設定と元のフローエンティティの削除＞
図１８は、集約されたフローエンティティのスイッチへの登録手順を示す流れ図であり、図８のステップＳ１１に対応する。
【０１６０】
コントローラ２０の経路集約実行部２０７は、集約可能なフローエンティティ（例えば図１７（Ｂ）のフローエンティティ７、８、９）と、登録しようとしているフローエンティティ（例えば図１７（Ａ）のＦｅ）のうち、ルールの一致しないフィールドをワイルドカードとした新たな集約フローエンティティを作成し、集約経路記憶部２０８の集約管理テーブルで管理されるスイッチ別集約フローエンティティの該当エントリに記憶し、スイッチ状態変更部２０６に通知する。経路集約実行部２０７からの通知を受けて、スイッチ状態変更部２０６は、フローエンティティ設定部２０２に対して、新たに作成された集約フローエンティティのスイッチ１０への設定を指示する。スイッチ１０のフローエンティティ設定部１０４は、コントローラ２０のフローエンティティ設定部２０２から通知されたフローエンティティ（集約フローエンティティ）をフローエンティティテーブル１０２に登録する（Ｓ１１−１）。
【０１６１】
新たな集約フローエンティティがスイッチ１０に登録され、スイッチ１０から登録完了の通知を受けた場合、スイッチ状態変更部２０６は、集約フローエンティティに集約された元の集約可能なフローエンティティ（例えば図１７（Ｂ）のフローエンティティ７、８、９）を、スイッチ１０のフローエンティティテーブル１０２から削除するように、フローエンティティ設定部２０２に通知する。スイッチ１０のフローエンティティ設定部１０４は、コントローラ２０のフローエンティティ設定部２０２からのフローエンティティの削除指示を受け、フローエンティティテーブル１０２から、該当するフローエンティティを削除し、削除完了を、コントローラ２０のフローエンティティ設定部２０２に通知する（Ｓ１１−２）。
【０１６２】
スイッチ１０のフローエンティティテーブル１０２に登録されたフローエンティティは、例えばシステムが規定した期間、ルールにマッチするパケットが到着しないと無効となる。このとき、有効経路記憶部２０３の経路管理テーブル（図５参照）上の経路構成情報、経路管理テーブル内の関連エントリは、削除される。
【０１６３】
なお、上記実施形態で説明した経路管理テーブル、経路構成情報、集約経路管理テーブル、スイッチ別集約フローエンティティテーブルのデータ構造はあくまで実装の一例を示したものであり、本発明はかかるデータ構造に制限されるものでないことは勿論である。また、本発明において、ノードは上記実施例のスイッチ（ＯＦＳ）を含むほか、コントローラによってフローの制御が行われる任意のスイッチ（Ｌ２／Ｌ３スイッチ）、ルータ等を含む。
【０１６４】
上記した実施形態のコントローラ２０は、専用のサーバとして実現することもでき、スイッチ１０としては、上記ＯＦＳ（ＯｐｅｎＦｌｏｗ  Ｓｗｉｔｃｈ）のほか、ＩＰ網におけるルータ、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）網におけるＭＰＬＳスイッチのようなノードであれば実現できる。その他、コントローラがネットワーク内のノードを集中管理するようなネットワークであれば、本発明を適用することが可能である。
【０１６５】
なお、上記の特許文献、非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせ、乃至、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１６６】
１０  スイッチ
２０  コントローラ
３０  ノード
１０１  パケット処理部
１０２  フローエンティティテーブル
１０３  パケット通知部
１０４  フローエンティティ設定部
１０５  トラフィック量計測部
１０６  トラフィック量通知部
２０１  パケット処理部
２０２  フローエンティティ設定部
２０３  有効経路記憶部
２０４  トポロジー情報
２０５  経路算出部
２０６  スイッチ状態変更部
２０７  経路集約実行部
２０８  集約経路記憶部
２１０  代替経路算出部
２１１  代替経路候補算出部
２１２、２１２Ａ  影響度算出部
２１３  代替経路決定部
２１４  トラフィック量管理部
【図１】
2011043312.tif 000003
【図２】
2011043312.tif 000004
【図３】
2011043312.tif 000005
【図４】
2011043312.tif 000006
【図５】
2011043312.tif 000007
【図６】
2011043312.tif 000008
【図７】
2011043312.tif 000009
【図８】
2011043312.tif 000010
【図９】
2011043312.tif 000011
【図１０】
2011043312.tif 000012
【図１１】
2011043312.tif 000013
【図１２】
2011043312.tif 000014
【図１３】
2011043312.tif 000015
【図１４】
2011043312.tif 000016
【図１５】
2011043312.tif 000017
【図１６】
2011043312.tif 000018
【図１７】
2011043312.tif 000019
【図１８】
2011043312.tif 000020
【図１９】
2011043312.tif 000021
【図２０】
2011043312.tif 000022
【図２１】
2011043312.tif 000023
【図２２】
2011043312.tif 000024
【国際調査報告】
2011043312.tif 000025
2011043312.tif 000026
2011043312.tif 000027
2011043312.tif 000028