(57)【要約】【課題】  異なるエンドホスト対間の導通パケット計算において計算結果を再利用することを可能にする。【解決手段】  検証装置は、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程で求めたフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する処理部を備える。【選択図】  図１
2017183891.tif 000002
【特許請求の範囲】
【請求項１】
検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程で求めたフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する処理部を備える検証装置。
【請求項２】
前記フロー関数は、前記ネットワークを構成する各スイッチのフローテーブルに基づいて生成された前記各スイッチの遷移関数を合成したポート対間のフロー関数である、
請求項１に記載の検証装置。
【請求項３】
前記ポート対間のフロー関数を保持する記憶部を更に備え、
前記処理部は、
前記ポート対間のフロー関数が前記記憶部に保持されていない場合、前記ポート対間のフロー関数を算出して前記記憶部に保持し、
前記ポート対間のフロー関数が記憶部に保持されている場合、前記ポート対間のフロー関数を用いて前記導通パケット計算を行う、
請求項２に記載の検証装置。
【請求項４】
前記処理部は、前記ネットワークに関するフローテーブルおよび物理トポロジに基づいて、前記ネットワークを構成する各スイッチの遷移関数を生成する、
請求項２又は３に記載の検証装置。
【請求項５】
前記処理部は、前記遷移関数と前記ネットワークの物理トポロジに基づいて、前記エンドホスト対の前記フロー関数を計算する、
請求項４に記載の検証装置。
【請求項６】
前記ネットワークに含まれるポート対間のフロー関数は、任意に設定される中間流入ポートと中間流出ポートとの間のフロー関数を含む、
請求項１から５のいずれか１つに記載の検証装置。
【請求項７】
検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成し、
前記生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する、検証方法。
【請求項８】
検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成し、
前記生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する、ことをコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの経路設定を検証する検証装置等に関する。
【背景技術】
【０００２】
非特許文献１はネットワークを導通するパケットを計算する方法であるＨＳＡ（Ｈｅａｄｅｒ  Ｓｐａｃｅ  Ａｎａｌｙｓｉｓ）について記載されている。ＨＳＡでは、各パケットヘッダはパケットヘッダの各フィールドが張る空間Ｈ（ヘッダスペース）上の１点として表現される。
【０００３】
上記ネットワークにおいて、スイッチは次に述べるように規定、動作するものとする。各スイッチは、パケットを入力及び出力可能なポートを複数有し、フローテーブル、すなわちフローエントリのリストをただ１つ持つ。各フローエントリは、入力元ポート、マッチングルール、アクション及び出力先ポートによって規定される。
【０００４】
マッチングルールにはパケットヘッダの各フィールドに対し、そのフィールドが取り得る値の集合が指定されている。アクションにはパケットヘッダの各フィールドに対し、そのフィールドが取り得る値が１つ指定されている、あるいは、ワイルドカード（＊）が指定されているものとする。
【０００５】
また、出力先ポートは、該スイッチが有するポートを１つ以上指定したリストである。パケットヘッダの各フィールドの値がマッチングルールに指定されている範囲の値であった場合、該パケットヘッダは該マッチングルール、あるいは、これを持つフローエントリにマッチする、という。
【０００６】
スイッチの動作を次に述べる。スイッチのポートに入力されたパケットは、フローテーブルのフローエントリを順に見ていき、最初にマッチしたフローエントリに基づいて処理される。パケットの処理を任されたフローエントリは、アクションに指定されているフィールドを指定されている値に書き換え、該パケットを出力先ポートに指定されているポートに転送する。ここで、ワイルドカードが指定されているフィールドはアクションによって書き変わらないものとする。
【０００７】
ＨＳＡでは、ネットワーク上の各スイッチは、パケットヘッダとポートの組をパケットヘッダとポートの組の集合に移す転送関数Ｔ: Ｈ×Ｐ→２＾（Ｈ×Ｐ）としてモデル化される。ここでＰはポートの集合を表す。転送関数Ｔ（ｈ，ｐ）＝｛（ｈｉ，ｐｉ）｜ｉ＝１，２，．．．，ｎ｝は、パケットヘッダｈを持つパケットをポートｐに入力した際、該パケットのパケットヘッダがｈｉに変換されてポートｐｉへと転送されることを意味する。ここで、ｎが２以上のときはパケットが複製されて２つ以上のポートに転送されることに対応する。
【０００８】
非特許文献１は、また、ネットワークの物理トポロジを辿りながらネットワーク内を導通するパケットの集合を計算する手法について記載している。図３１Ａは、非特許文献１におけるエンドホスト対間の前向きの導通パケットを求める手法を示す模式図である。また、図３１Ｂは、非特許文献１におけるエンドホスト対間の後向きの導通パケットを求める手法を示す模式図である。図中、ネットワークを構成する各スイッチは、ＳＷ１〜６で示される。各スイッチ間、スイッチとエンドホスト間は物理リンクによって接続される。物理リンクと接続されるスイッチのポートにはポート識別子が付与されている。
【０００９】
非特許文献１の手法は、例えば、ネットワーク内で計算対象のエンドホスト対（ａ，ｂ）間でパケットが導通するパスを一つ取り上げ、その間を前向きに導通するパケットの集合を計算し（図３１Ａ）、計算した集合が空でなければ、後向きに導通するパケットを計算する（図３１Ｂ）。これによりエンドホスト対（ａ，ｂ）間を導通するパケットの集合が計算される。
【００１０】
非特許文献２も非特許文献１と同様、ＨＳＡによって導通パケットの集合を計算する手法を用いる。非特許文献２は、非特許文献１と異なり、後向きの導通パケットの計算のみ行うことで、計算の一部を再利用可能にし、計算量を改善している。
【００１１】
図３２Ａ、図３２Ｂは、非特許文献２におけるエンドホスト対（ａ，ｂ）間の導通パケットを求める手法を説明する模式図である。特許文献２の手法は、異なるパスの計算において共通する経路部分の計算を使い回すことにより計算を高速化する。図３２Ａに示すように、エンドホスト対ａ，ｂの間の導通パケット計算で求めた計算の一部（ｈ１）を、図３２Ｂに示す導通パケット計算でも用いることで、図３２Ｂに示すスイッチＳＷ５に関する計算を省略し、計算を効率化する。
【００１２】
なお、非特許文献１、２を利用したネットワークの設定検証は、検証対象ネットワークに設定された物理トポロジと経路表データの取得を、検証対象ネットワークにおけるエンドホスト対について、その間の導通パケットの集合を計算することで得られる。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Peyman Kazemian, George Varghese, Nick McKeown著「Header space analysis: static checking for networks」、Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation (NSDI'12)、2012年、pp113-126
【非特許文献２】Toshio Tonouchi, Satoshi Yamazaki, Yutaka Yakuwa, Nobuyuki Tomizawa著「A fast method of verifying network routing with back-trace header space analysis」、Integrated Network Management (IM), 2015 IFIP/IEEE International Symposium on、2015年、pp.225-233
【発明の概要】
【発明が解決しようとする課題】
【００１４】
非特許文献２の技術の問題点は、異なるエンドホスト対に対する計算を行う上での計算の非効率性である。非特許文献２は、エンドホスト対間の導通パケット計算において、途中計算の結果をキャッシュ及び再利用し計算を効率化する。しかしながら、異なるエンドホスト対に対する計算間では計算結果の共有は行われない。
【００１５】
図３３は、エンドホスト対間のフローが共通するネットワークの例を示す概要図である。図３３は、エンドホスト対間のフローが共通するネットワークの物理トポロジの一例を示す概要図である。図３４は、エンドホスト対間のフローが共通するネットワークのフローテーブルを示す図である。なお、図３４に示すフローテーブルでは、各フローエントリもアクションによってパケットヘッダが更新されない、としてアクションの欄が省略されている。
【００１６】
図３３に示すネットワークにおいて、フローの大部分が同じになる２つのエンドホスト対の計算は、同様の計算を２度繰り返すことになる。したがって、ネットワーク中のエンドホスト対に対し導通パケットを算出し、ネットワークの設定の正当性を検証する上で、異なるエンドホスト対で計算を再利用できない非特許文献２の手法による計算は非効率的である。
【００１７】
この問題が容易に解決できない原因は、異なるエンドホスト対間のフローの大部分が同じ場合であっても、それぞれの導通パケットの計算過程で同じ計算結果はほとんど出現しないため、キャッシュした計算結果の再利用ができないという点にある。
【００１８】
図３５Ａは、非特許文献２の手法を用いて図３３に示すネットワークにおけるエンドホスト対（ａ，ｂ）の導通パケット計算を示す説明図である。図３５Ｂ、は、非特許文献２の手法を用いて図３３のネットワークにおけるエンドホスト対（ａ，ｃ）の導通パケット計算を示す説明図である。図３５Ａ、図３５Ｂに示すように、エンドホストｂとエンドホストｃとは同じスイッチＳＷ１〜ＳＷ５に接続し、フローの大部分が共通するにもかかわらず、エンドホスト対（ａ，ｂ）とエンドホスト対（ａ，ｃ）の各々の計算過程でキャッシュされた計算結果が異なる。図３５ＡのＳＷ５の計算結果、図３５ＢのＳＷ５の計算結果に示すように、最初に適用するエントリが違えばその先のフローが共通していても計算結果が異なるためである。
【００１９】
このように非特許文献１、２の技術では、異なる２つのエンドホスト対の間を跨いで再利用可能な計算結果はほとんどなく、２つの計算過程で行われているのがほぼ同じ計算でも再度計算し直す必要がある。
［発明の目的］
本発明の目的は、上記課題を解決するべく、異なるエンドホスト対間の導通パケット計算において計算結果を再利用することを可能にする技術を提供することにある。
【課題を解決するための手段】
【００２０】
本発明の検証装置は、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程で求めたフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する処理部を備える。
【００２１】
本発明の検証方法は、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成し、前記生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する。
【００２２】
本発明のプログラムの一態様は、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成し、前記生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する、ことをコンピュータに実行させる。
【発明の効果】
【００２３】
本発明は、異なるエンドホスト対間の導通パケット計算において計算結果を再利用することを可能にする。
【図面の簡単な説明】
【００２４】
【図１】第１の実施形態の検証装置の構成を示す機能ブロック図である。
【図２】第１の実施形態におけるフロー関数の一例を示す説明図である。
【図３】第１の実施形態の検証装置、第２の実施形態のネットワーク検証器をコンピュータで実現するためのハードウエア構成図である。
【図４】第１の実施形態の検証装置の動作を示すフローチャートである。
【図５】第２の実施形態におけるネットワーク検証器の構成を示す機能ブロック図である。
【図６】第２の実施形態のネットワーク検証器が検証対象とするネットワークの一例を示す説明図である。
【図７】検証対象ネットワークを構成する６つのスイッチに設定されたフローテーブルの一例を示す図である。
【図８】検証対象ネットワークの物理トポロジを示す図である。
【図９】検証対象ネットワークの物理トポロジを示す図である。
【図１０】フローエントリを合成する規則の一例を示す説明図である。
【図１１】フロー関数の合成を説明するためのスイッチの接続を示す説明図である。。
【図１２】フロー関数φ１、φ２の合成であるφ１×φ２の具体例を示す図である。
【図１３】フロー関数φ１、φ２の和であるφ１＋φ２の具体例を示す図である。
【図１４Ａ】第２の実施形態におけるフロー関数計算処理の前段を示すフローチャートである。
【図１４Ｂ】第２の実施形態におけるフロー関数計算処理の後段を示すフローチャートである。
【図１５】キャッシュされてない場合に、ポート対（１．１，６．３）に対するフロー関数を求める際の再帰呼び出し関係を示すツリー図である。
【図１６】キャッシュされたポート対（１．１，５．３）に対するフロー関数φ［１．１，５．３］を示す図である。
【図１７】キャッシュ済みの場合に、ポート対（１．１，６．３）に対するフロー関数を求める際の再帰呼び出し関係を示すツリー図である。
【図１８】ポート対（１．１，６．２）のフロー関数を示す図である。
【図１９】ポート対（１．１，６．２）の導通パケットの計算結果を示す図である。
【図２０】第３の実施形態のネットワーク検証器の構成を示す機能ブロック図である。
【図２１】第３の実施形態における検証対象ネットワークとそこに指定される中間流入ポートと中間流出ポートを示す説明図である。
【図２２Ａ】第３の実施形態における検証対象ネットワークを構成するスイッチに設定されたフローテーブルの一例を示す図である。
【図２２Ｂ】第３の実施形態における検証対象ネットワークを構成するスイッチに設定されたフローテーブルの一例を示す図である。
【図２３】第３の実施形態における検証対象ネットワークにおける物理トポロジを示す図である。
【図２４Ａ】第３の実施形態の検証対象ネットワークにおける各スイッチの遷移関数族を示す図である。
【図２４Ｂ】第３の実施形態の検証対象ネットワークにおける各スイッチの遷移関数族を示す図である。
【図２５Ａ】第３の実施形態におけるフロー関数計算処理の動作の一部を示すフローチャートである。
【図２５Ｂ】第３の実施形態におけるフロー関数計算処理の動作の一部を示すフローチャートである。
【図２５Ｃ】第３の実施形態におけるフロー関数計算処理の動作の一部を示すフローチャートである。
【図２５Ｄ】第３の実施形態におけるフロー関数計算処理の動作の一部を示すフローチャートである。
【図２６】キャッシュのない場合に、ポート対（１．１，８．３）に第２フロー関数計算処理を適用した際の再帰呼び出しをツリー状に示す図である。
【図２７】ポート対（２．１，７．４）のフロー関数の示す図である。
【図２８】キャッシュがある場合に、ポート対（１．１，８．３）に第２フロー関数計算処理を適用した際の再帰呼び出しをツリー状に示す図である。
【図２９Ａ】ポート対（１．２，８．３）のフロー関数の計算結果を示す図である。
【図２９Ｂ】ポート対（１．１，８．４）のフロー関数を計算結果示す図である。
【図３０】各エンドホスト対間の導通パケットの集合の計算結果を示す図である。
【図３１Ａ】非特許文献１におけるエンドホスト対間の前向き導通パケットを求める手法を説明する模式図である。
【図３１Ｂ】非特許文献１におけるエンドホスト対間の後向きの導通パケットを求める手法を示す模式図である。
【図３２Ａ】非特許文献２におけるエンドホスト対（ａ，ｂ）間の導通パケットを求める手法を説明する模式図である。
【図３２Ｂ】非特許文献２におけるエンドホスト対（ａ，ｂ）間の導通パケットを求める手法を説明する模式図である。
【図３３】エンドホスト対間のフローが共通するネットワークの物理トポロジの一例を示す概要図である。
【図３４】エンドホスト対間のフローが共通するネットワークのフローテーブルの設定の一例を示す概要図である。
【図３５Ａ】非特許文献２の手法を用いて図３の検証対象ネットワークにおいて２つのエンドホスト対（ａ，ｂ）の導通パケットを計算する例を示す図である。
【図３５Ｂ】非特許文献２の手法を用いて図３の検証対象ネットワークにおいて２つのエンドホスト対（ａ，ｃ）の導通パケットを計算する例を示す図である。
【図３６】フロー関数とフローテーブルの違いを示す比較図である。
【発明を実施するための形態】
【００２５】
［第１の実施形態］
第１の実施形態の検証装置について図面を用いて説明する。
【００２６】
［構成の説明］
図１は、第１の実施形態の検証装置の構成を示す機能ブロック図である。図１に示すように、第１の実施形態の検証装置１０は、処理部１１を備える。検証装置１０の処理部１１は、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程で求めたフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する。
【００２７】
例えば、検証装置１０は、一のエンドホスト対間の導通パケット計算の過程において、エンドホスト対間に含まれるスイッチのポート対間のフローをフロー関数として生成し、記憶部（図示せず）にキャッシュする。検証装置１０は、他のエンドホスト対間の導通パケット計算の際に記憶部のポート対間のフロー関数を利用することで、異なるエンドホスト対間の導通パケット計算を効率化する。なお、エンドホスト対の導通パケットの計算は、エンドホストが接続しているポートの間のフロー関数を求めることで導通パケットの計算を行う。
【００２８】
以下、フロー関数の定義について説明する。例えば、ポートｐ１からポートｐ２（異なるポート対間）へのフローを表すフロー関数は、φ［ｐ１，ｐ２］と記述される。φ［ｐ１，ｐ２］は、Ｈ→２＾Ｈの関数であり、パケットヘッダｈを入力とし、ポートｐ１からパケットヘッダがｈであるようなパケットを流したとき、ネットワークを通じてポートｐ２に流出するパケットのパケットヘッダの集合を出力する関数である。
【００２９】
フロー関数は、フローテーブルと同様にフローエントリのリストで構成されてもよい。フローテーブルは、パケットを処理する際、フローテーブルを順に見てルールにマッチする最初のフローエントリ一つが該パケットを処理する。一方、フロー関数は、ルールにマッチした少なくとも１つのフローエントリで処理した結果を返すという点でフローテーブルと異なる。
【００３０】
図３６は、フロー関数とフローテーブルの違いを示す比較図である。図３６（ａ）は、スイッチ内のフローテーブルの一例を示し、図３６（ｂ）は、フロー関数の一例を示す。図３６（ａ）、（ｂ）は、いずれも同じ挙動を示す内容が記述されている。
【００３１】
図２は、第１の実施形態におけるフロー関数の一例を示す説明図である。図２に示すネットワークは、図３３に示すネットワークと同じであり、スイッチＳＷ１〜ＳＷ５の５つのスイッチのフローテーブルは、図３４に示すフローテーブルと同様であるとする。スイッチＳＷ１〜ＳＷ５は、それぞれ対応する経路表のフローエントリを使ってパケットを処理するものとする。
【００３２】
また、図２に示すフロー関数は、スイッチＳＷ１のポート１からスイッチＳＷ４のポート３までフローを表現するものであり、処理部１１のフロー関数計算処理によって２つの経路上のフローエントリが成すフローが合成されたものである。フロー関数については、後述の第２の実施形態で更に説明する。
【００３３】
関連技術でキャッシュされる計算結果（図３４Ａ、図３４Ｂ）と、第１の実施形態の検証装置でキャッシュされる計算結果であるフロー関数（図２）とを比較する。第１の実施形態の検証装置１０の記憶部（図示せず）でキャッシュされるフロー関数は、その部分の端点である２つのポートに依存して決まり、現在計算しているエンドホスト対の始点・終点となっているエンドホストには非依存である。このため、計算途中でキャッシュしたフロー関数は、始点・終点が異なる他のエンドホスト対の計算に移っても再利用可能となる。
【００３４】
図３は、第１の実施形態の検証装置、第２の実施形態のネットワーク検証器をコンピュータで実現するためのハードウエア構成図の一例である。図５によると、コンピュータ３００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｓｅｓｓｉｎｇ  Ｕｎｉｔ）３１０、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３２０、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３３０、ハードディスク等の補助記憶装置３４０と、出力表示装置３５０及びネットワークインターフェース３７０を備える。これらは相互にデータバス３６０で接続され、自由にデータをやりとりできるものとする。検証装置１０の処理部１１は、ＲＯＭ３２０上のソフトウエアに基づいて、ＣＰＵ３１０等によってその機能が実行される。また、検証装置の記憶部は、ＲＡＭ３３０、又は、補助記憶装置３４０によって機能が実行される。
【００３５】
［動作の説明］
第１の実施形態の検証装置の動作について図面を用いて説明する。図４は、第１の実施形態の検証装置の動作を示すフローチャートである。図４に示すように、検証装置１０の処理部１１は、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成する（ステップＳ１１）。さらに、処理部１１は、生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する（ステップＳ１２）。
【００３６】
［効果の説明］
第１の実施形態の検証装置は、異なるエンドホスト対間の導通パケット計算において計算結果を再利用することを可能にし、検証対象ネットワーク内の任意のエンドホスト対に対する導通パケット計算にかかる時間を短くすることができる。
【００３７】
その理由は、検証装置の処理部が、検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程で求めたフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用するからである。
【００３８】
［第２の実施形態］
次に、第２の実施形態であるネットワーク検証器について、図面を用いて説明する。第２の実施形態のネットワーク検証器は、上述の検証装置の一態様である。
【００３９】
［構成の説明］
図５は、第２の実施形態におけるネットワーク検証器の構成を示す機能ブロック図である。図５を参照すると、ネットワーク検証器１００は、フローテーブル取得部１１０と、物理トポロジ取得部１２０と、遷移関数生成部１３０と、フロー関数計算部１４０と、ヘッダスペース計算部１５０と、結果出力部１６０を備える。
【００４０】
ネットワーク検証器１００が検証するネットワークは、例えば、１つ以上のスイッチと、２つ以上のエンドホスト、および、各スイッチ間とスイッチとエンドホスト間を接続する物理リンクによって構成される。スイッチは、２つ以上のポート及び１つのフローテーブルを持ち、エンドホストは、１つのポートを持ち、物理リンクは、異なる２つのスイッチのポート同士、或いは、１つのスイッチのポートと１つのエンドホストのポートを接続する。
【００４１】
図６は、ネットワーク検証器が検証対象とするネットワークの一例を示す説明図である。図６に示す検証対象ネットワーク２００は、エンドポストｉ１とエンドポストｏ１、ｏ２、スイッチ２１０（ＳＷ１〜ＳＷ６）、各スイッチ間、スイッチとエンドポスト間を接続する物理リンク２３０を有する。スイッチＳＷ２とＳＷ５の間には２つの経路が形成されている。なお、以下、記述の簡略化のために「スイッチＳＷｉのｊ番ポート」を「ｉ．ｊ」と表記する場合がある。
【００４２】
第２の実施形態のネットワーク検証器１００も図３に示すハードウエア構成図によって実現可能である。すなわち、ネットワーク検証器１００のフローテーブル取得部１１０及び物理トポロジ取得部１２０は、入力装置としてネットワークインターフェース３７０を利用する形でＲＯＭ３２０上にソフトウエアとして実装され、ＣＰＵ３１０によって実行される。遷移関数生成部１３０、フロー関数計算部１４０、及びヘッダスペース計算部１５０は、ＲＯＭ３２０上にソフトウエアとして実装され、ＣＰＵ３１０によって実行される。結果出力部１６０はＲＯＭ３２０上にソフトウエアとして実装され、ＣＰＵ３１０によって実行され、実行結果を出力表示装置３５０に出力する。なお、ネットワーク検証器１００のハードウエア構成及び各構成部の機能を実行するソフトウエアの実装は、上述に限定されるものではない。
【００４３】
第２の実施形態のネットワーク検証器１００の各構成部は、以下のように機能する。
【００４４】
フローテーブル取得部１１０は、検証対象ネットワーク２００を構成する各スイッチ２１０のフローテーブルを取得する。
【００４５】
物理トポロジ取得部１２０は、検証対象ネットワーク２００における物理リンク２３０によるスイッチ２１０の各ポートの接続関係を示す物理トポロジを取得する。物理トポロジ取得部１２０が取得する物理トポロジにより、物理リンク２３０によって接続されるスイッチ２１０間の指定した２つのポート、或いは物理リンク２３０によるスイッチ間の接続がないという情報が参照可能となる。
【００４６】
遷移関数生成部１３０は、フローテーブル取得部１１０及び物理トポロジ取得部１２０がそれぞれ取得したフローテーブル、物理トポロジに基づいて、各スイッチ２１０の遷移関数（の族）を生成する。すなわち、ポート対（ｐ１，ｐ２）に対するフロー関数φ［ｐ１，ｐ２］をフローエントリの情報から生成する。
【００４７】
図２０に示すように、フロー関数計算部１４０は、遷移関数生成部１３０から各スイッチの遷移関数（の族）を取得し、物理トポロジ取得部１２０から物理トポロジを取得する。そしてフロー関数計算部１４０は、取得した遷移関数（の族）と物理トポロジに基づき、各エンドホスト対間のフロー関数を計算する。
【００４８】
フロー関数計算部１４０は、はじめに、検証対象ネットワークに含まれる、あるエンドホスト対（ａ，ｂ）を固定し、その間のフロー関数を第１フロー関数計算処理によって計算する。これを検証対象ネットワークに含まれる所望のエンドホスト対間について繰り返すことで対象とするエンドホスト対間に対するフロー関数を得る。
【００４９】
フロー関数計算部１４０は、第１フロー関数計算処理によって、検証対象ネットワーク内の２つのポート対を指定し、その間の遷移関数を順次合成していくことでポート対間のフロー関数を生成する。このとき、フロー関数計算部１４０は、指定されたポート対に対し、その間のフロー関数が記憶部（図示せず）にキャッシュされているか確認する。キャッシュされていない場合、当該フロー関数を計算し、記憶部（図示せず）にキャッシュする。一方、フロー関数が記憶部（図示せず）にキャッシュされる場合、フロー関数計算部１４０は、その結果を再利用する。なお、第１フロー関数計算処理は、サブルーティンとしてフロー関数合成処理及びフロー関数加算処理を含む。
【００５０】
ヘッダスペース計算部１５０は、フロー関数計算部１４０によって計算されたフロー関数から、各エンドホスト対間を導通するパケットの集合を計算する。このとき、ヘッダスペース計算部１５０は、パケット全体を表わすヘッダスペースに得られたフロー関数を逆向きに適用することで導通パケットの集合を計算する。
【００５１】
結果出力部１６０は、ヘッダスペース計算部１５０から出力された計算結果を出力表示装置に出力する。
【００５２】
但し、フロー関数計算部１４０があるエンドホスト対についてフロー関数を得たとき、その次のエンドホスト対に対する計算を始める前にヘッダスペース計算部１５０がヘッダスペースを計算し、また、結果出力部１６０が結果を出力表示装置に出力してもよいものとする。一旦得られたエンドホスト対間のフロー関数は、その後の計算によって変化することはないので、このような手順とした場合でも最終的にネットワーク検証器１００の出力として表示される結果は変わらない。
【００５３】
上のようにネットワーク検証器１００の各構成要素が機能することで、ネットワーク検証器１００は、検証対象ネットワーク２００の各エンドホスト対間の導通パケットの集合を計算し、出力表示装置３５０に結果を出力する。
【００５４】
［動作の説明］
次に、第２の実施形態のネットワーク検証器の動作について図面を用いて説明する。フローテーブル取得部１１０は、検証対象ネットワーク２００に関するフローテーブルを取得し、ポート対を入力として対応するフローエントリを参照可能なデータに変換する。図７は、検証対象ネットワーク２００を構成する６つのスイッチに設定されたフローテーブルの一例を示す図である。図中、スイッチＳＷ１〜ＳＷ６のそれぞれのフローテーブルが示されている。
【００５５】
また、物理トポロジ取得部１２０は、検証対象ネットワーク２００に関する物理トポロジを取得し、ポートを入力として物理リンク２３０による接続先のポートを参照可能なデータに変換する。図８は、検証対象ネットワーク２００の物理トポロジを示す図である。図８に示すように、物理トポロジには、スイッチ間又はスイッチとエンドホスト間を接続する各物理リンクの接続元・接続先ポート対の情報が記述されている。
【００５６】
遷移関数生成部１３０は、フローテーブル取得部１１０が取得したフローテーブルに基づいて、各スイッチの遷移関数（の族）を生成する。具体的には、遷移関数生成部１３０は、フローテーブルの各フローエントリに対応する遷移関数を生成し、スイッチの各ポート対に対応するフロー関数を生成する。なお、生成されたスイッチの各ポート対に対するフロー関数は、参照可能な状態で記憶部（図示せず）に保持される。
【００５７】
図９は、遷移関数生成部１３０が生成する、各ポート対に対応するフロー関数の一例である。図９に示す各ポート対に対応するフロー関数は、図７に示すフローテーブルに基づいて生成されている。
【００５８】
ここで、図７に示すフローテーブルにおいて、スイッチＳＷ２の１つ目のフローエントリのマッチングルールと２つ目のフローエントリのマッチングルールは、オーバーラップしている。遷移関数生成部１３０は、これを解消すべく２つ目のフローエントリのマッチングルールに「ＶＬＡＮ＿ＩＤ≠２」を追加する。これによりフローテーブルのマッチングルールにおいてオーバーラップのないフロー関数となる。
【００５９】
フロー関数計算部４１０は、第１フロー関数計算処理によって、検証対象ネットワークの各エンドホスト対に対するフロー関数を順次計算する。すなわち、始点となるエンドホストｈを一つ固定した上で各終点に対するフロー関数を計算し、エンドホストｈを始点とするエンドホスト対に対する計算が終わり次第、始点を別のエンドホストに切り替えて計算を行う。この「始点のエンドホストを切り替える」タイミングにおいて、フロー関数計算部４１０はそれまでの計算結果をキャッシュしたテーブルをクリアしてもよい。
【００６０】
次に、第１フロー関数計算処理について説明する。そのためにまず、２つのサブルーティンであるフロー関数合成処理及びフロー関数加算処理について説明する。まず、２つのフロー関数φ１，φ２の合成であるφ１×φ２を計算するフロー関数合成処理について説明する。２つのフローエントリを合成すると、２つのフローエントリによって順番に処理された結果を返すフローエントリになる。
【００６１】
図１０は、フローエントリを合成する規則の一例を示す説明図である。図１０（ａ）は、合成に用いるフローエントリｅ１、ｅ２を示し、図１０（ｂ）は、フローエントリを合成する条件を示している。図１０（ａ）に示す２つのフローエントリｅ１，ｅ２が図１０（ｂ）に示す条件を満たすとき、図１０（ｃ）に示すフローエントリに合成される。なお、図１０（ｃ）で用いている演算子の定義は図１０（ｄ）に示している。これに従い、フロー関数φ１、φ２の、図１０（ｂ）に示す条件を満たすフローエントリの対を合成してできたフローテーブルによって表されるフロー関数をφ１×φ２と定義する。
【００６２】
図１１は、フロー関数の合成を説明するためのスイッチの接続を示す説明図である。図１２は、フロー関数φ１、φ２を合成したφ１×φ２の具体例を示す図である。図１２に示すように、フロー関数φ１とフロー関数φ２との合成によりφ１×φ２は、１つのフロー関数として取り扱うことが可能となる。
【００６３】
次に、２つのフロー関数φ１，φ２の和であるφ１＋φ２を計算するフロー関数加算処理について説明する。２つのフロー関数の和φ１＋φ２は、２つのフロー関数で並列に同じ入力を処理した結果を返すようなフロー関数になる。
フロー関数の定義より、２つのフロー関数を表すフローエントリのリストを繋ぎ合わせることでφ１＋φ２を表すフローエントリのリストを得ることができる。そのようにして得られたリストで表されるフロー関数をφ１＋φ２とする。
【００６４】
図１３は、フロー関数φ１、φ２の和であるφ１＋φ２の具体例を示す図である。図１３に示すフロー関数の和φ１＋φ２は、フロー関数φ１とフロー関数φ２のそれぞれのフローエントリが加算されたものとなっている。なお、フロー関数を表すフローエントリに重複がある場合、重複分は削除される。
【００６５】
図１４Ａは、フロー関数処理部におけるフロー関数計算処理の前段を示すフローチャートである。図１４Ｂは、フロー関数処理部におけるフロー関数計算処理の後段を示すフローチャートである。第１フロー関数計算処理は２つのポートを入力として動作する。ここではその２つをポートｐ１，ｐ２とする。
【００６６】
フロー関数計算部１４０は、第１フロー関数計算処理によって、まず入力されたポートｐ１，ｐ２が同じスイッチのポートであるかを確認する。同じスイッチの異なる２つのポートの場合（ステップＳ４１１）、フロー関数計算部１４０は、ポートｐ１，ｐ２のフロー関数として、遷移関数生成部１３０で既に計算済みのフロー関数φ［ｐ１，ｐ２］を取得する（ステップＳ４１２）。
【００６７】
それ以外の場合（ステップＳ４１１がＮｏの場合）、フロー関数計算部１４０は、記憶部（図示せず）にフロー関数φ［ｐ１，ｐ２］がキャッシュ済みであるかを確認する。キャッシュ済みの場合（ステップＳ４１３のＹｅｓ）、記憶部からフロー関数φ［ｐ１，ｐ２］を取得する（ステップＳ４１４）。
【００６８】
キャッシュされていない場合（ステップＳ４１５のＮｏ）、以下の処理に進む。
【００６９】
フロー関数計算部１４０は、φ［ｐ１，ｐ２］を空のフロー関数に初期化し（ステップＳ４１４）、ポートｐ１を持つスイッチに存在するポートのうち、ポートｐ１を入力元ポートとする各フローエントリｅｉ（ｉ＝１，２，・・・，ｎ）について次の処理を実行する（ステップＳ４１６）。
【００７０】
フロー関数計算部１４０は、フローエントリｅｉの出力先ポートをｐ’ｉとし、その物理リンクの接続先ポートをｐ＃ｉとする（ステップＳ４１７）。接続先ポートｐ＃ｉについて、フロー関数計算部１４０は、第１フロー関数計算処理（ｐ＃ｉ，ｐ２）によって、φ［ｐ＃ｉ，ｐ２］を取得し（ステップＳ４１８）、遷移関数表からφ［ｐ１，ｐ’ｉ］を取得する（ステップＳ４１９）。フロー関数計算部１４０は、フロー関数合成処理及びフロー関数加算処理によって、φ［ｐ１，ｐ＃１］×φ［ｐ’１，ｐ２］＋φ［ｐ１，ｐ＃２］×φ［ｐ’２，ｐ２］＋……＋φ［ｐ１，ｐ＃ｎ］×φ［ｐ’ｎ，ｐ２］を計算してφ［ｐ１，ｐ２］とし（ステップＳ４２０）、その値をキャッシュする（ステップＳ４２１）。
【００７１】
図１５は、記憶部（図示せず）にフロー関数がキャッシュされていない場合、スイッチのポート対に対するフロー関数を求める際の再帰呼び出し関係をツリー状に示す図である。図中、ポート対（１．１，６．２）は、スイッチＳＷ１のポート１とスイッチＳＷ６のポート２のポート対を示している。
【００７２】
図１５中、例えば、ポート対（１．１，６．２）からポート対（１．１，５．３）への矢印は、ポート対（１．１，６．２）に対する第１フロー関数計算処理の計算においてポート対（１．１，５．３）に対する第１フロー関数計算処理の再帰呼び出しが行われることを意味する。記憶部にフロー関数がキャッシュされていない場合、フロー関数計算部１４０は、必要な分だけ検証対象ネットワーク２００を走査し、各スイッチの遷移関数を合成することでフロー関数を計算する。
【００７３】
図１６は、この過程で記憶部（図示せず）にキャッシュされたポート対（１．１，５．３）に対するフロー関数φ［１．１，５．３］である。フロー関数φ［１．１，５．３］は、そのフローテーブルの情報を、対応するポート対（１．１，５．３）から逆引き可能な形で記憶部（図示せず）にキャッシュされる。
【００７４】
一方、図１７は、ポート対（１．１，６．２）のフロー関数を計算した際の情報が記憶部にキャッシュ済みの場合に、ポート対（１．１，６．３）に対するフロー関数を求める際の再帰呼び出し関係を示すツリー図である。
【００７５】
フロー関数計算部１４０は、第１フロー関数計算処理によって、ポート対（１．１，５．３）に対する再帰呼び出しが行われる。このポート対に対するフロー関数はキャッシュ済みなので、記憶部にキャッシュされたフロー関数を再利用することで計算が省略される。第１フロー関数計算処理の最終的な計算結果は図１８に示す通りである。
【００７６】
なお、第１フロー関数計算処理の再帰呼び出しによってネットワーク全体を考慮したフロー関数を求めているが、再帰呼び出しがループしてしまい処理が終了しないことがある。これを防ぐため、ポートｐ１，ｐ２に対する第１フロー関数計算処理が、その後の計算仮定で再びポートｐ１，ｐ２に対して第１フロー関数計算処理の呼び出しを行った場合、その時点で即座に復帰する。その場合、フローエントリが一つもない空のフロー関数を返り値として返す。
【００７７】
次に、ヘッダスペース計算部１５０は、各エンドホスト対間の導通パケットの集合を求める。あるエンドホスト対間の導通パケットは、該エンドホスト対に対応するフロー関数の少なくとも一つのフローエントリのマッチングルールにマッチするパケットヘッダの全体として求めることができる。
【００７８】
具体的には、図１８の２つのフロー関数φ［１．１，６．２］のマッチングルールＤＳＴ＝ｏ１，ＶＬＡＮ＿ＩＤ＝２がエンドホスト（ｉ１，ｏ１）の導通パケット、φ［１．１，６．３］の２つのマッチングルールＤＳＴ＝ｏ２，ＶＬＡＮ＿ＩＤ＝２及びＶＬＡＮ＿ＩＤ≠２，ＳＳＨ＿ＥＮＡＢＬＥ＝ＦＡＬＳＥがエンドホスト（ｉ１，ｏ２）の導通パケットとなる。図１９に最終的な計算結果を示す。
【００７９】
結果出力部１６０は、ヘッダスペース計算部１５０から出力された計算結果を出力表示装置に出力する。結果出力部１６０は、検証対象のネットワークの所定のエンドホスト対に対するヘッダスペース計算部１５０からの出力が揃った時点で出力する。あるいは、結果出力部１６０は、ヘッダスペース計算部１５０から一つのエンドホスト対に対する計算結果を取得した際に順次出力してもよい。
【００８０】
［効果の説明］
第２の実施形態のネットワーク検証器によれば、エンドホスト対（ａ，ｐ１），（ａ，ｐ２），……，（ａ，ｐｎ）を求める際にａが直接接続しているポートｐａから流入するフローは一度計算されたら必ずキャッシュされるので、第１フロー関数計算処理はｐａから始まるポート対に対して高々一回しか計算を行わない。このためａから各エンドホストへのフローに共通部分が多いネットワークにおいて、本実施形態は効率的な導通パケット計算を行うことができる。
【００８１】
［第３の実施形態］
次に、第３の実施形態のネットワーク検証器について図面を用いて説明する。
【００８２】
［構成の説明］
図２０は、第３の実施形態のネットワーク検証器の構成を示す機能ブロック図である。第３の実施形態のネットワーク検証器４００は、第２の実施形態のネットワーク検証器１００と同様の構成を有する。ネットワーク検証器４００は、ネットワーク検証器１００のフロー関数計算部１４０が、フロー関数計算部４１０となっている点で相違する。
【００８３】
第３の実施形態のフロー関数計算部４１０は、遷移関数生成部１３０からの各スイッチの遷移関数（の族）、及び、物理トポロジ取得部１２０から物理トポロジの他に、中間流入ポート又は中間流出ポートのリストをユーザ設定として受付ける。
【００８４】
［動作の説明］
第３の実施形態における動作もフロー関数計算部４１０以外は、第１の実施形態と同じである。第３の実施形態におけるフロー関数計算部４１０は３つの入力を受付ける。なお、第２の実施形態の説明と同様に、簡略化のために「スイッチＳＷｉのｊ番ポート」を「ｉ．ｊ」と表記する場合もある。
【００８５】
図２１は、第３の実施形態における検証対象ネットワークとそこに指定される中間流入ポートと中間流出ポートを示す説明図である。図２２Ａ、図２２Ｂは、第３の実施形態における検証対象ネットワークを構成するスイッチに設定されたフローテーブルを示す図である。
【００８６】
図２１に示すように、検証対象ネットワーク２００における中間流入ポートとして、スイッチＳＷ２のポート１が設定され、中間流出ポートとしてスイッチＳＷ７のポート４が設定されている。
【００８７】
物理トポロジ取得部１２０は、検証対象ネットワーク２００における物理リンク２３０によるスイッチ２１０の各ポートの接続関係を示す物理トポロジを取得する。図２３は、検証対象ネットワーク２００における物理トポロジを示す図である。物理トポロジ取得部１２０は、物理トポロジをフロー関数計算部４１０に渡す。
【００８８】
遷移関数生成部１３０は、フローテーブル取得部１１０及び物理トポロジ取得部１２０がそれぞれ取得したフローテーブル（図２２Ａ、図２２Ｂ）、物理トポロジ（図２３）に基づいて、各スイッチ２１０の遷移関数（の族）を生成する。すなわち、スイッチの各ポート対ｐ１，ｐ２に対し、フロー関数φ［ｐ１，ｐ２］をフローエントリの情報から生成する。図２４Ａ、図２４Ｂは、検証対象ネットワーク２００における各スイッチの遷移関数族を示す図である。遷移関数生成部１３０は、生成した遷移関数族をフロー関数計算部４１０に渡す。
【００８９】
フロー関数計算部１４０は、各エンドホスト対に対してフロー関数計算処理を実行し、各エンドホスト対に対するフロー関数を順次計算する。例えば、エンドホストの集合ｈ１，ｈ２，……，ｈｎに対し、（ｈ１，ｈ２），（ｈ１，ｈ３），（ｈ１，ｈ４），……（ｈ１，ｈｎ），（ｈ２，ｈ１），（ｈ２，ｈ３），……，（ｈｎ，ｈ（ｎ−２）），（ｈｎ，ｈ（ｎ−１））の順に、検証対象ネットワーク２００の所定のエンドホスト対に対してフロー関数計算処理を実行する。
【００９０】
なお、エンドホスト対に対するフロー関数の計算順序は一例であり、順序は限定されない。また、所定のエンドホスト対は、全てのエンドホスト対でもよく、あるいは、一部のエンドホスト対の組合せでよい。
【００９１】
次に、第２フロー関数計算処理の動作について述べる。内包する２つのサブルーティンであるフロー関数合成処理及びフロー関数加算処理の動作は第２の実施形態におけるフロー関数合成処理、フロー関数加算処理と同様である。このため詳細な説明は省略する。
【００９２】
図２５Ａ、図２５Ｂ、図２５Ｃ、図２５Ｄは、第３の実施形態における第２フロー関数計算処理の動作を示すフローチャートである。第３の実施形態の第２フロー関数計算処理は、第２の実施形態の第１フロー関数計算処理と同様に２つのポートを入力として動作する。以下ではその２つのポートをｐ１，ｐ２とする。第３の実施形態の第２フロー関数計算処理は、フラグとしてキャッシュフラグを持ち、初期値はＦＡＬＳＥである。このフラグは呼び出しに固有の値である。また、第２フロー関数計算処理は、フロー関数計算部１４０が入力として取得する中間流入ポート、中間流出ポートのリストを参照することができる。
【００９３】
第３の実施形態の第２フロー関数計算処理において、フロー関数計算部４１０は、まず入力されたポートｐ１，ｐ２が同じスイッチのポートであるかを確認し、同じスイッチの異なる２つのポートの場合（ステップＳ４２１のＹｅｓ）、ポートｐ１，ｐ２のフロー関数として、遷移関数生成部１３０で既に計算済みのフロー関数φ［ｐ１，ｐ２］を取得する（ステップＳ４２２）。
【００９４】
ステップＳ４２１がＮｏの場合、第２フロー関数計算処理において、フロー関数計算部４１０は、ポートｐ１が中間流入ポートであるか、及び、ポートｐ２が中間流出ポートであるかを確認する。
【００９５】
（１）ポートｐ１，ｐ２がそれぞれ中間流出ポート（ステップＳ４２３のｙｅｓ）、中間流入ポート（ステップＳ４２４のＹｅｓ）の場合、フロー関数計算部４１０は、記憶部（図示せず）にφ［ｐ１，ｐ２］がキャッシュされているかどうか確認する。φ［ｐ１，ｐ２］がキャッシュ済みの場合（ステップＳ４２５のＹｅｓ）、フロー関数計算部４１０は、その結果を取得して（ステップＳ４２６）第２フロー関数計算処理の出力とする。キャッシュされていなければ、キャッシュフラグの値をＴＲＵＥにセットする（ステップＳ４２７）。
【００９６】
（２）ポートｐ２が中間流出ポート（ステップＳ４２３のＹｅｓ）であり、ポートｐ１が中間流入ポートでない（ステップＳ４２４のＮｏ）場合、フロー関数計算部４１０は、φ［ｐ１，ｐ２］を空のフロー関数に初期化する（ステップＳ４２８）。フロー関数計算部４１０は、ポートｐ１を持つスイッチに存在するポートのうち、ポートｐ１を入力元ポートとする各フローエントリｅｊ（ｊ＝１，２，・・・，ｍ）について次の処理を実行する（ステップＳ４２９）。
【００９７】
まず、フロー関数計算部４１０は、ポートｐ１を持つスイッチに存在するポートのうち、ポートｐ１を入力元ポートとする所定のフローエントリの出力先ポートをｐ’ｊとし、その物理リンクの接続先ポートをｐ＃ｊとする（ステップＳ４３０）。次に、フロー関数計算部４１０は、接続先ポートｐ＃ｊについて第２フロー計算処理（ｐ＃ｊ，ｐ２）によってフロー関数φ［ｐ＃ｊ，ｐ２］を取得し（ステップＳ４３１）、計算済みのφ［ｐ１，ｐ’ｊ］を取得する（ステップＳ４３２）。フロー関数合成処理及びフロー関数加算処理を用いてφ［ｐ１，ｐ’１］×φ［ｐ＃１，ｐ２］＋φ［ｐ１，ｐ’２］×φ［ｐ＃２，ｐ２］＋……＋φ［ｐ１，ｐ’ｊ］×φ［ｐ＃ｊ，ｐ２］を計算してφ［ｐ１，ｐ２］とする（ステップＳ４３３）。
【００９８】
（３）（１）及び（２）に該当しない場合、フロー関数計算部４１０は、φ［ｐ１，ｐ２］を空のフロー関数に初期化する（ステップＳ４３４）。ポートｐ２を持つスイッチに存在するポートのうち、ポートｐ２を出力先ポートとする各フローエントリｅｋ（ｋ＝１，２，・・・，ｌ）について次の処理を実行する（ステップＳ４３５）。
【００９９】
フロー関数計算部４１０は、ポートｐ２を持つスイッチに存在する他ポートのうち、ポートｐ２を入力元ポートとする所定のフローエントリｅｋの出力先ポートをｐ’ｋとし、その物理リンクの接続先ポートをｐ＃ｋとする。フロー関数計算部４１０は、第２フロー関数計算処理（ｐ１，ｐ＃ｋ）によって、φ［ｐ１，ｐ＃ｋ］を取得し（ステップＳ４３７）、計算済みのφ［ｐ’ｋ，ｐ２］を取得する（ステップＳ４３８）。フロー関数計算部４１０は、フロー関数合成処理及びフロー関数加算処理を用いてφ［ｐ１，ｐ＃１］×φ［ｐ’１，ｐ２］＋φ［ｐ１，ｐ＃２］×φ［ｐ’２，ｐ２］＋……＋φ［ｐ１，ｐ＃ｎ］×φ［ｐ’ｎ，ｐ２］を計算してφ［ｐ１，ｐ２］とする（ステップＳ４３９）。
【０１００】
第２フロー関数計算処理において、上に記述した場合分け処理を終えた時点でフロー関数φ［ｐ１，ｐ２］の値は求まっている。その値を返り値として第２フロー関数計算処理に復帰する。このとき、キャッシュフラグがＴＲＵＥであるならば、φ［ｐ１，ｐ２］の値をキャッシュし（ステップＳ４４０）、ポート対ｐ１，ｐ２から逆引きできるようにする。
【０１０１】
第２フロー関数計算処理は再帰呼び出しにより処理が終了しないことがあるが、第１の実施形態と同様にこれを防ぐことができる。
【０１０２】
図２６は、記憶部（図示せず）に何もキャッシュされていない状態で、図２１に示す検証対象ネットワークのポート対（１．１，８．３）に第２フロー関数計算処理を適用した際の再帰呼び出しをツリー状に示す図である。ポート対（１．１，８．３）の計算ではポート１．１が中間流入ポートではないため（１）のケースに従って再帰呼び出しを行う。ポート対（２．１，８．３）の計算ではポート２．１は中間流入ポートだが、ポート８．３が中間流出ポートではないため（２）のケースに従って再帰呼び出しを行う。ポート対（２．１，７．４）は、ポート２．１が中間流入ポートで、ポート８．３が中間流出ポートであり、かつ、ポート対（２．１，７．４）の計算結果がキャッシュされていないので、（３）のケースにしたがって再帰呼び出しを行い、ポート対（２．１，７．４）の計算結果（図２７）は呼び出し元に返る前にキャッシュされる。ポート対（２．１，７．４）のフロー関数は、図２７に示す通りになる。
【０１０３】
図２８は、前段の計算に続いてポート対（１．２，８．４）に第２フロー関数計算処理を適用した際の再帰呼び出しをツリー状に示す図である。ここで、ポート対（２．１，７．４）は既に計算結果がキャッシュされているため、別のポート対に対する呼び出しを行わず計算を省略することができる。
【０１０４】
さらに以下、ポート対（１．２，８．３）、及び、ポート対（１．１，８．４）に対するフロー関数の計算においても、ポート対（２．１，７．４）の計算結果を再利用することができる。図２９Ａは、ポート対（１．２，８．３）のフロー関数の計算結果を示す図である。図２９Ｂは、ポート対（１．１，８．４）のフロー関数の計算結果を示す図である。
【０１０５】
ヘッダスペース計算部１５０は、図２９Ａ、図２９Ｂに示されるフロー関数を用い、各エンドホスト対間の導通パケットの集合を求める。図３０は、各エンドホスト対間の導通パケットの集合の計算結果である。
【０１０６】
［効果の説明］
第３の実施形態の効果について説明する。第３の実施形態によれば、求めるポート対間のフロー関数に中間流入ポートとの間のフロー関数をキャッシュするように設計されているため、中間流入ポート・中間流出ポートに「使用頻度の高い」ポートを指定することでより効率のよい計算を行うことができる。
【０１０７】
また、第３の実施形態では、中間流入ポート・中間流出ポートを外部から入力として受け取るように構成されている。このため、検証対象となるネットワーク構成にある特定の傾向又は特徴に関する前提知識があった場合、その前提知識を利用して中間流入ポ―ト・中間流出ポートを設定することでネットワーク固有の性質による最適化が可能になる。
【０１０８】
（実施形態の適用例）
上記の各実施形態の検証装置、又は、ネットワーク検証器は、例えば、ネットワーク管理者が稼働中のＯｐｅｎＦｌｏｗ（登録商標）ネットワークからフローテーブルの設定を吸い上げて設定の正当性を検証する用途に適用できる。また、ネットワーク設計者が設計中のネットワークの経路設定の正当性を確かめる用途にも適用可能である。
【０１０９】
また、ネットワーク検証器の各構成要素の一部又は全部は、その他の汎用または専用の回路、プロセッサ等やこれらの組み合わせによって実現される。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい
さらに、ネットワーク検証器の各構成要素の一部又は全部は、上述した回路等とプログラムとの組み合わせによって実現されてもよい。
【０１１０】
また、検証装置又はネットワーク検証器の各構成要素の一部又は全部が複数の情報処理装置や回路等により実現される場合、複数の情報処理装置や回路等は、集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【０１１１】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１１２】
また、図面中の矢印の方向は、一例を示すものであり、ブロック間の信号の向きを限定するものではない。
【０１１３】
上記の実施形態の一部又は全部は、以下の付記のように記載されうるが、以下には限られない。
【０１１４】
（付記１）
検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程で求めたフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する処理部を備える検証方法。
【０１１５】
（付記２）
前記フロー関数は、前記ネットワークを構成する各スイッチのフローテーブルに基づいて生成された前記各スイッチの遷移関数を合成したポート対間のフロー関数である、
付記１に記載の検証方法。
【０１１６】
（付記３）
前記ポート対間のフロー関数を保持する記憶部を更に備え、
前記処理部は、
前記ポート対間のフロー関数が前記記憶部に保持されていない場合、前記ポート対間のフロー関数を算出して前記記憶部に保持し、
前記ポート対間のフロー関数が記憶部に保持されている場合、前記ポート対間のフロー関数を用いて前記導通パケット計算を行う、
付記２に記載の検証方法。
【０１１７】
（付記４）
前記処理部は、前記ネットワークに関するフローテーブルおよび物理トポロジに基づいて、前記ネットワークを構成する各スイッチの遷移関数を生成する、
付記２又は３に記載の検証方法。
【０１１８】
（付記５）
前記処理部は、前記遷移関数と前記ネットワークの物理トポロジに基づいて、前記エンドホスト対の前記フロー関数を計算する、
付記４に記載の検証方法。
【０１１９】
（付記６）
前記ネットワークに含まれるポート対間のフロー関数は、任意に設定される中間流入ポートと中間流出ポートとの間のフロー関数を含む、
付記１から５のいずれか１つに記載の検証方法。
【０１２０】
（付記７）
検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成し、
前記生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する、検証方法。
【０１２１】
（付記８）
前記フロー関数は、前記ネットワークを構成する各スイッチのフローテーブルに基づいて生成された前記各スイッチの遷移関数を合成したポート対間のフロー関数である、
付記７に記載の検証方法。
【０１２２】
（付記９）
前記ポート対間のフロー関数が保持されていない場合、前記ポート対間のフロー関数を算出して保持し、
前記ポート対間のフロー関数が保持されている場合、前記ポート対間のフロー関数を用いて前記導通パケット計算を行う、
付記８に記載の検証方法。
【０１２３】
（付記１０）
前記ネットワークに関するフローテーブルおよび物理トポロジに基づいて、前記ネットワークを構成する各スイッチの遷移関数を生成する、
付記８又は９に記載の検証方法。
【０１２４】
（付記１１５）
前記遷移関数と前記ネットワークの物理トポロジに基づいて、前記エンドホスト対の前記フロー関数を計算する、
付記１０に記載の検証方法。
【０１２５】
（付記１２）
前記ネットワークに含まれるポート対間のフロー関数は、任意に設定される中間流入ポートと中間流出ポートとの間のフロー関数を含む、
付記７から１１のいずれか１つに記載の検証方法。
【０１２６】
（付記１３）
検証対象のネットワークに含まれる異なるエンドホスト対に対し、一のエンドホスト対に関する導通パケット計算の過程でフロー関数を生成し、
前記生成したフロー関数を、他のエンドホスト対に関する導通パケット計算の過程で利用する、ことをコンピュータに実行させるプログラム。
【０１２７】
（付記１４）
前記フロー関数は、前記ネットワークを構成する各スイッチのフローテーブルに基づいて生成された前記各スイッチの遷移関数を合成したポート対間のフロー関数である、
付記１３に記載のプログラム。
【０１２８】
（付記１５）
前記ポート対間のフロー関数が保持されていない場合、前記ポート対間のフロー関数を算出して保持し、
前記ポート対間のフロー関数が保持されている場合、前記ポート対間のフロー関数を用いて前記導通パケット計算を行う、
付記１４に記載のプログラム。
【０１２９】
（付記１６）
前記ネットワークに関するフローテーブルおよび物理トポロジに基づいて、前記ネットワークを構成する各スイッチの遷移関数を生成する、
付記１４又は１５に記載のプログラム。
【０１３０】
（付記１７）
前記遷移関数と前記ネットワークの物理トポロジに基づいて、前記エンドホスト対の前記フロー関数を計算する、
付記１６に記載のプログラム。
【０１３１】
（付記１８）
前記ネットワークに含まれるポート対間のフロー関数は、任意に設定される中間流入ポートと中間流出ポートとの間のフロー関数を含む、
付記１３から１７のいずれか１つに記載のプログラム。
【符号の説明】
【０１３２】
１０    検証装置
１１    処理部
１００    ネットワーク検証器
１１０    フローテーブル取得部
１２０    物理トポロジ取得部
１３０    遷移関数生成部
１４０    フロー関数計算部
１５０    ヘッダスペース計算部
１６０    結果出力部
２００    検証対象ネットワーク
２１０    スイッチ
２２０    エンドホスト
２３０    物理リンク
３００    ネットワークインターフェース
３１０    ＣＰＵ
３２０    ＲＯＭ
３３０    ＲＡＭ
３４０    補助記憶装置
３５０    出力表示装置
３６０    データバス
４００    ネットワーク検証器
４１０    フロー関数計算部
【図１】
2017183891.tif 000003
【図２】
2017183891.tif 000004
【図３】
2017183891.tif 000005
【図４】
2017183891.tif 000006
【図５】
2017183891.tif 000007
【図６】
2017183891.tif 000008
【図７】
2017183891.tif 000009
【図８】
2017183891.tif 000010
【図９】
2017183891.tif 000011
【図１０】
2017183891.tif 000012
【図１１】
2017183891.tif 000013
【図１２】
2017183891.tif 000014
【図１３】
2017183891.tif 000015
【図１４Ａ】
2017183891.tif 000016
【図１４Ｂ】
2017183891.tif 000017
【図１５】
2017183891.tif 000018
【図１６】
2017183891.tif 000019
【図１７】
2017183891.tif 000020
【図１８】
2017183891.tif 000021
【図１９】
2017183891.tif 000022
【図２０】
2017183891.tif 000023
【図２１】
2017183891.tif 000024
【図２２Ａ】
2017183891.tif 000025
【図２２Ｂ】
2017183891.tif 000026
【図２３】
2017183891.tif 000027
【図２４Ａ】
2017183891.tif 000028
【図２４Ｂ】
2017183891.tif 000029
【図２５Ａ】
2017183891.tif 000030
【図２５Ｂ】
2017183891.tif 000031
【図２５Ｃ】
2017183891.tif 000032
【図２５Ｄ】
2017183891.tif 000033
【図２６】
2017183891.tif 000034
【図２７】
2017183891.tif 000035
【図２８】
2017183891.tif 000036
【図２９Ａ】
2017183891.tif 000037
【図２９Ｂ】
2017183891.tif 000038
【図３０】
2017183891.tif 000039
【図３１Ａ】
2017183891.tif 000040
【図３１Ｂ】
2017183891.tif 000041
【図３２Ａ】
2017183891.tif 000042
【図３２Ｂ】
2017183891.tif 000043
【図３３】
2017183891.tif 000044
【図３４】
2017183891.tif 000045
【図３５Ａ】
2017183891.tif 000046
【図３５Ｂ】
2017183891.tif 000047
【図３６】
2017183891.tif 000048