(57)【要約】【課題】ネットワーク上でのパケットの転送やネットワーク構成を当該ネットワークを実際に稼働させることなく検証できるネットワーク検証方法及び装置を提供する。【解決手段】第１の通信機器の識別子と第１の通信機器から送信されたパケットを受信する第２の通信機器の識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器から送信されたパケットを受信する第３の通信機器の識別子との対応関係、第２の通信機器で受信されたパケットに付加されている第１のタグと第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係をそれぞれ表すデータから、各タグと各通信機器の識別子と各通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定されるネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成し、ネットワークモデルが要求仕様を満たすか否かを検証する。【選択図】      図１
2005218038.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信機器を接続してなるネットワークを検証するネットワーク検証方法であって、
第１の通信機器の識別子と当該第１の通信機器から送信されたパケットを受信する第２の通信機器の識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器から送信されたパケットを受信する第３の通信機器の識別子との対応関係を表すネットワーク構成データを入力する第１の入力ステップと、
前記第２の通信機器で受信されたパケットに付加されている第１のタグと第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係を表す転送ルールデータを入力する第２の入力ステップと、
前記ネットワーク構成データと前記転送ルールデータを受けて前記第１のタグ及び第２のタグ、前記第１乃至第３の通信機器の識別子、及び前記第１乃至第２の通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定される前記ネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成する生成ステップと、
前記ネットワークに対する要求仕様を入力する第３の入力ステップと、
前記ネットワークモデルが前記要求仕様を満たすか否かを検証する検証ステップと、
前記検証ステップでの検証結果を出力する出力ステップと、
を有することを特徴とするネットワーク検証方法。
【請求項２】
少なくとも１つのポートをそれぞれ有する複数の通信機器を、それぞれのポートを介して接続してなるネットワークを検証するネットワーク検証方法であって、
第１の通信機器の識別子と第１の通信機器の第１のポートの識別子と第１のポートから送信されたパケットを受信する第２の通信機器の識別子と第２の通信機器の第２のポートの識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器の第３のポートの識別子と第３のポートから送信されたパケットを受信する第３の通信機器の識別子と第３の通信機器の第４のポートの識別子との対応関係を表すネットワーク構成データを入力する第１の入力ステップと、
前記第２の通信機器の前記第２のポートの識別子と第２のポートで受信されたパケットに付加される第１のタグと第２の通信機器の前記第３のポートの識別子と第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係を表す転送ルールデータを入力する第２の入力ステップと、
前記ネットワーク構成データと前記転送ルールデータを受けて前記第１のタグ及び第２のタグ、及び前記第１乃至第３の通信機器の識別子、及び前記第１乃至第３の通信機器のポートの識別子、及び前記第１乃至第２の通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定される前記ネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成する生成ステップと、
前記ネットワークに対する要求仕様を入力する第３の入力ステップと、
前記ネットワークモデルが前記要求仕様を満たすか否かを検証する検証ステップと、
前記検証ステップでの検証結果を出力する出力ステップと、
を有することを特徴とするネットワーク検証方法。
【請求項３】
前記第３の入力ステップは、前記第１のタグ及び第２のタグのうちの１つと、前記第１乃至第３の通信機器の識別子のうちの１つと、送信及び転送モードのうちの１つとで特定される前記ネットワークの複数の状態のうちの所望の状態と、当該所望の状態に対する条件と、当該所望の状態間の状態遷移と、当該所望の状態遷移に対する条件のうちの少なくとも１つを表す前記要求仕様を入力し、
前記検証ステップは、前記ネットワークモデルに前記第２の入力ステップで入力された要求仕様に表されている前記所望の状態と前記所望の状態遷移が含まれているか否か、前記所望の状態が前記要求仕様に表されている条件を満たすか否か、前記所望の状態遷移が前記要求仕様に表されている条件を満たすか否かを検証することを特徴とする請求項１記載のネットワーク検証方法。
【請求項４】
前記第３の入力ステップは、前記第１のタグ及び第２のタグのうち１つと、前記第１乃至第３の通信機器の識別子のうちの１つと、前記第１乃至第３の通信機器のポートの識別子のうちの１つと、送信及び転送モードのうちの１つとで特定される前記ネットワークの複数の状態のうちの所望の状態と、当該所望の状態に対する条件と、当該所望の状態間の状態遷移と、当該所望の状態遷移に対する条件のうちの少なくとも１つを表す前記要求仕様を入力し、
前記検証ステップは、前記ネットワークモデルに前記第２の入力ステップで入力された要求仕様に表されている前記所望の状態と前記所望の状態遷移が含まれているか否か、前記所望の状態が前記要求仕様に表されている条件を満たすか否か、前記所望の状態遷移が前記要求仕様に表されている条件を満たすか否かを検証することを特徴とする請求項２記載のネットワーク検証方法。
【請求項５】
前記要求仕様は、前記所望の状態に対する条件と前記所望の状態遷移に対する条件が、様相論理を用いて記述されていることを特徴とする請求項３または４記載のネットワーク検証方法。
【請求項６】
複数の通信機器を接続してなるネットワークを検証するネットワーク検証装置であって、
第１の通信機器の識別子と当該第１の通信機器から送信されたパケットを受信する第２の通信機器の識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器から送信されたパケットを受信する第３の通信機器の識別子との対応関係を表すネットワーク構成データを入力する第１の入力手段と、
前記第２の通信機器で受信されたパケットに付加されている第１のタグと第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係を表す転送ルールデータを入力する第２の入力手段と、
前記ネットワーク構成データと前記転送ルールデータを受けて前記第１のタグ及び第２のタグ、前記第１乃至第３の通信機器の識別子、及び前記第１乃至第２の通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定される前記ネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成する生成手段と、
前記ネットワークに対する要求仕様を入力する第３の入力手段と、
前記ネットワークモデルが前記要求仕様を満たすか否かを検証する検証手段と、
前記検証手段での検証結果を出力する出力手段と、
を具備したことを特徴とするネットワーク検証装置。
【請求項７】
少なくとも１つのポートをそれぞれ有する複数の通信機器を、それぞれのポートを介して接続してなるネットワークを検証するネットワーク検証装置であって、
第１の通信機器の識別子と第１の通信機器の第１のポートの識別子と第１のポートから送信されたパケットを受信する第２の通信機器の識別子と第２の通信機器の第２のポートの識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器の第３のポートの識別子と第３のポートから送信されたパケットを受信する第３の通信機器の識別子と第３の通信機器の第４のポートの識別子との対応関係を表すネットワーク構成データを入力する第１の入力手段と、
前記第２の通信機器の前記第２のポートの識別子と第２のポートで受信されたパケットに付加される第１のタグと第２の通信機器の前記第３のポートの識別子と第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係を表す転送ルールデータを入力する第２の入力手段と、
前記ネットワーク構成データと前記転送ルールデータを受けて前記第１のタグ及び第２のタグ、及び前記第１乃至第３の通信機器の識別子、及び前記第１乃至第３の通信機器のポートの識別子、及び前記第１乃至第２の通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定される前記ネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成する生成手段と、
前記ネットワークに対する要求仕様を入力する第３の入力手段と、
前記ネットワークモデルが前記要求仕様を満たすか否かを検証する検証手段と、
前記検証手段での検証結果を出力する出力手段と、
を具備したことを特徴とするネットワーク検証装置。
【請求項８】
前記第３の入力手段で入力される前記要求仕様は、前記第１のタグ及び第２のタグのうちの１つと、前記第１乃至第３の通信機器の識別子のうちの１つと、送信及び転送モードのうちの１つとで特定される前記ネットワークの複数の状態のうちの所望の状態と、当該所望の状態に対する条件と、当該所望の状態間の状態遷移と、当該所望の状態遷移に対する条件のうちの少なくとも１つを表し、
前記検証手段は、前記ネットワークモデルに前記第２の入力ステップで入力された要求仕様に表されている前記所望の状態と前記所望の状態遷移が含まれているか否か、前記所望の状態が前記要求仕様に表されている条件を満たすか否か、前記所望の状態遷移が前記要求仕様に表されている条件を満たすか否かを検証することを特徴とする請求項６記載のネットワーク検証装置。
【請求項９】
前記第３の入力手段で入力される前記要求仕様は、前記第１のタグ及び第２のタグのうちの１つと、前記第１乃至第３の通信機器の識別子のうちの１つと、前記第１乃至第３の通信機器のポートの識別子のうちの１つと、送信及び転送モードのうちの１つとで特定される前記ネットワークの複数の状態のうちの所望の状態と、当該所望の状態に対する条件と、当該所望の状態間の状態遷移と、当該所望の状態遷移に対する条件のうちの少なくとも１つを表し、
前記検証手段は、前記ネットワークモデルに前記第２の入力ステップで入力された要求仕様に表されている前記所望の状態と前記所望の状態遷移が含まれているか否か、前記所望の状態が前記要求仕様に表されている条件を満たすか否か、前記所望の状態遷移が前記要求仕様に表されている条件を満たすか否かを検証することを特徴とする請求項７記載のネットワーク検証装置。
【請求項１０】
前記要求仕様は、前記所望の状態に対する条件と前記所望の状態遷移に対する条件が、様相論理を用いて記述されていることを特徴とする請求項８または９記載のネットワーク検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークを検証するための方法および装置に関する。
【背景技術】
【０００２】
パケットを転送するネットワークには、パケットにタグと呼ばれる識別子が付加されているものがある。このようなネットワークにおいては、ネットワークを構成するパケット中継装置（スイッチ）は、受信したパケットに付加されているタグとスイッチに保存された転送ルールとを照合し、パケットを転送するポートを決定する。また、このようなスイッチにはパケットを送信する際に、タグを改変する機能を持つものがある。
【０００３】
このようなネットワークの例として、ＩＥＥＥ（米国電気電子技術者協会）で標準化されている８０２．１Ｑ  ＶＬＡＮ（例えば非特許文献２参照）や、ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ）で標準化されているＭＰＬＳ（Ｍｕｌｔｉｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）（例えば非特許文献３参照）などがある。
【０００４】
このようなネットワークにおいては、スイッチの転送ルールの誤りやスイッチの故障、その他の原因によって、パケットがネットワークの要求仕様どおりに転送されない、あるいは要求仕様とは異なるように転送されるという障害が起きることがある。このような障害を発見する既存の方法として、実際にパケットを送出し、その転送のされ方を観察する方法がある。その一例として、ループ検出パケットを送出することによりパケットのループを検出する方法がある（例えば特許文献１、２、３参照）。
【０００５】
一方、状態遷移モデルの性質を柔軟に記述可能な方法として、様相論理を用いる方法がある。状態遷移モデルが、様相論理で記述された性質を満たすか否かを効率的に判定する判定方法として、モデル検査の方法が知られている。また、様相論理の１つであるＣＴＬ（computation tree logic）およびＬＴＬ(linear time temporary logic)によって記述された性質についてモデル検査を行うソフトウェアとしてＳＭＶ(symbolic model verifier)が知られている（様相論理、モデル検査、およびＳＭＶについては、例えば非特許文献１参照）。
【０００６】
【特許文献１】特開平５−１３４９９３号公報
【０００７】
【特許文献２】特開平１１−２４３４１６号公報
【０００８】
【特許文献３】特開２０００−４９８５４
【０００９】
【非特許文献１】クラルケ（Ｅ．Ｍ．Ｃｌａｒｋｅ）他著，「モデル・チェッキング（Ｍｏｄｅｌ  Ｃｈｅｃｋｉｎｇ）」（ＩＳＢＮ：０２６２０３２７０８）
【００１０】
【非特許文献２】ＩＥＥＥ規格Ｓｔｄ  ８０２．１ｑ−２００３
【００１１】
【非特許文献３】ローゼン（Ｅ．Ｒｏｓｅｎ）他著「マルチプロトコル・ラベル・スイッチング・アーキテクチャ（Ｍｕｌｔｉｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ  Ａｒｃｈｉｔｅｃｔｕｒｅ）」，ＩＥＴＦ  ＲＦＣ３０３１
【発明の開示】
【発明が解決しようとする課題】
【００１２】
ネットワーク上の障害をネットワークの稼働前に発見するためと、障害が発生したときにそれが転送ルールの誤りによるものか否かを判断するためには、ネットワーク上のスイッチが転送ルールどおりにパケットを転送したときに、パケットが要求仕様通りに転送されるか否かを実際に稼働しているネットワークを利用せずにネットワーク構成と転送ルールを用いて判定する必要がある。
【００１３】
前述の、実際にパケットを転送しその転送のされ方を観察する障害検知方法は、ネットワークの稼働前に実際にパケットを送出することができないためネットワークの稼働前に障害を発見するためには用いることができない。さらに、実際に送出されたパケットの転送のされ方は、転送ルールのみならずスイッチの故障の影響も受けるため、障害が発生したときにそれが転送ルールの誤りによるものか否かを判断するためには用いることができない。
【００１４】
このように、従来は、ネットワーク上でのパケットの転送のされ方やネットワーク構成を、当該ネットワークを実際に稼働させることなく検証することができないという問題点があった。
【００１５】
そこで、本発明は、上記問題点に鑑み、ネットワーク上でのパケットの転送やネットワーク構成を、当該ネットワークを実際に稼働させることなく容易にしかも効率よく検証することができるネットワーク検証方法および装置を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、複数の通信機器を接続してなるネットワークを検証するものであって、（ａ）第１の通信機器（例えば図２の端末ＴＥ１）の識別子と当該第１の通信機器から送信されたパケットを受信する第２の通信機器（例えば図２のスイッチＳＷ１）の識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器から送信されたパケットを受信する第３の通信機器（例えば図２のスイッチＳＷ２）の識別子との対応関係を表すネットワーク構成データを入力し、（ｂ）前記第２の通信機器で受信されたパケットに付加されている第１のタグと第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係を表す転送ルールデータを入力し、（ｃ）前記ネットワーク構成データと前記転送ルールデータを受けて前記第１のタグ及び第２のタグ、前記第１乃至第３の通信機器の識別子、及び前記第１乃至第２の通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定される前記ネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成し、（ｄ）前記ネットワークに対する要求仕様を入力し、（ｅ）前記ネットワークモデルが前記要求仕様を満たすか否かを検証し、（ｆ）検証結果を出力する。
【００１７】
また、本発明は、少なくとも１つのポートをそれぞれ有する複数の通信機器を、それぞれのポートを介して接続してなるネットワークを検証するものであって、（ａ）第１の通信機器（例えば図２の端末ＴＥ１）の識別子と第１の通信機器の第１のポートの識別子と第１のポートから送信されたパケットを受信する第２の通信機器（例えば図２のスイッチＳＷ１）の識別子と第２の通信機器の第２のポートの識別子との対応関係、及び第２の通信機器の識別子と第２の通信機器の第３のポートの識別子と第３のポートから送信されたパケットを受信する第３の通信機器（例えば図２のスイッチＳＷ２）の識別子と第３の通信機器の第４のポートの識別子との対応関係を表すネットワーク構成データを入力し、（ｂ）前記第２の通信機器の前記第２のポートの識別子と第２のポートで受信されたパケットに付加される第１のタグと第２の通信機器の前記第３のポートの識別子と第２の通信機器から第３の通信機器に転送されるパケットに付加される第２のタグとの対応関係を表す転送ルールデータを入力し、（ｃ）前記ネットワーク構成データと前記転送ルールデータを受けて前記第１のタグ及び第２のタグ、及び前記第１乃至第３の通信機器の識別子、及び前記第１乃至第３の通信機器のポートの識別子、及び前記第１乃至第２の通信機器が送信及び転送のいずれのモードであるかを示す動作モード情報で特定される前記ネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成し、（ｄ）前記ネットワークに対する要求仕様を入力し、（ｅ）前記ネットワークモデルが前記要求仕様を満たすか否かを検証し、（ｆ）検証結果を出力する。
【発明の効果】
【００１８】
タグを付加されたパケットを転送するネットワーク上でのパケットの転送やネットワーク構成を、当該ネットワークを実際に稼働させることなく容易にしかも効率よく検証することができる。
【発明を実施するための最良の形態】
【００１９】
図１は、本発明の実施形態に係るネットワーク検証装置の構成例を示したもので、タグ仕様入力部１、ネットワーク構成入力部２、転送ルール入力部３、ネットワーク要求仕様入力部４、モデル生成部５、モデル検査部６、検査結果出力部７とからなる。
【００２０】
タグ仕様入力部１は、ネットワークで使用されるタグの集合Ｔｓｅｔを入力するためのものである。
【００２１】
ネットワーク構成入力部２は、ネットワークを構成するスイッチの一意な識別子の集合Ｎｓｅｔと、関数Ｎｔａｂｌｅを入力するためのものである。Ｎｔａｂｌｅは、パケットの送信側のスイッチの識別子ｓとポートの番号ｎとを１組とする複数のデータ（ｓ、ｎ）と、当該パケットを受信側のスイッチの識別子ｓ´とポートの番号ｎ´とを１組とする複数のデータ（ｓ´、ｎ´）と、これらを対応付ける規則とを表すデータであり、Ｎｔａｂｌｅを用いれば、パケットの送信側のスイッチｓおよびポートｎから、当該パケットを受信する受信側のスイッチｓ´およびポートｎ´を特定することができる。
【００２２】
転送ルール入力部３は、関数Ｒｔａｂｌｅを入力するためのものである。関数Ｒｔａｂｌｅは、スイッチｓのポートｎで受信したパケットのタグがｔであるとき、当該スイッチｓで当該パケットを転送する際に用いるポートｎ´とタグｔ´を定めるデータであって、スイッチの識別子ｓとポート番号ｎとタグｔとを１組とする複数のデータ（ｓ、ｎ、ｔ）と、ポート番号ｎとタグｔとを１組とする複数のデータ（ｎ´、ｔ´）と、これらを対応付ける規則とを表すデータである。Ｒｔａｂｌｅを用いれば、タグｔと当該タグｔをもつパケットを受信したスイッチｓとそのポート番号ｎとから、当該パケットを当該スイッチｓから転送する際に用いるポートｎ´とタグｔ´とを特定することができる。
【００２３】
モデル生成部５は、タグ仕様入力部１から入力されたＴｓｅｔ、ネットワーク構成入力部２から入力されたＮｓｅｔおよびＮｔａｂｌｅ、転送ルール入力部３から入力されたＲｔａｂｌｅから、状態遷移モデルＭを生成する。状態遷移モデルＭは集合Ｍｓｅｔと、Ｍｓｅｔの部分集合間を対応付ける関数Ｍｔｒａｎｓからなる。
【００２４】
Ｍｓｅｔは、タグｔ、スイッチの識別子ｓ、ポート番号ｎ、フェーズｐという４つの要素からなる集合であり、これら４つの要素のそれぞれがとり得る値を定めるデータである。
【００２５】
フェーズは「ｓｗｉｔｃｈｅｄ」、「ｔｒａｎｓｍｉｔｔｅｄ」、「ｄｉｓｃａｒｄｅｄ」という３つの値のうちのいずれかの値をとる。
【００２６】
Ｍｔｒａｎｓは、Ｍｓｅｔの部分集合とこれらの間を対応付ける規則とを表すデータであって、転送ルールとネットワーク構成を表している。
【００２７】
フェーズｐがｓｗｉｔｃｈｅｄの場合  Ｒｔａｂｌｅ（ｓ，ｎ，ｌ）が空集合であるとき、４つ組（ｔ，ｓ，ｎ，ｄｉｓｃａｒｄｅｄ）のみを要素とする集合をＭｔｒａｎｓ（ｔ，ｓ，ｎ，ｐ）とする。Ｒｔａｂｌｅ（ｓ，ｎ，ｌ）が空集合でないとき、４つ組（ｔ´，ｓ，ｎ´，ｔｒａｎｓｍｉｔｔｅｄ）で（ｎ´，ｔ´）がＲｔａｂｌｅ（ｓ，ｎ，ｔ）の要素であるものの集合をＭｔｒａｎｓ（ｔ，ｓ，ｎ，ｐ）とする。
【００２８】
フェーズｐがｔｒａｎｓｍｉｔｔｅｄの場合  Ｎｔａｂｌｅ（ｓ，ｎ）が空集合であるとき、４つ組（ｔ，ｓ，ｎ，ｄｉｓｃａｒｄｅｄ）のみからなる集合をＭｔｒａｎｓ（ｔ，ｓ，ｎ，ｐ）とする。Ｎｔａｂｌｅ（ｓ，ｎ）が空集合でないとき、４つ組（ｔ，ｓ´，ｎ´，ｓｗｉｔｃｈｅｄ）で（ｓ´，ｎ´）がＮｔａｂｌｅ（ｓ，ｎ）の要素であるものの集合をＭｔｒａｎｓ（ｔ，ｓ，ｎ，ｐ）とする。
【００２９】
フェーズｐがｄｉｓｃａｒｄｅｄの場合  ４つ組（ｔ，ｓ，ｎ，ｄｉｓｃａｒｄｅｄ）のみを要素とする集合をＭｔｒａｎｓ（ｔ，ｓ，ｎ，ｐ）とする。
【００３０】
ネットワーク要求仕様入力部４は、様相論理（ＣＴＬおよびＬＴＬ）で記述されたネットワーク要求仕様を入力するためのものである。様相論理の原子論理式は、それぞれ真および偽を表わすＴＲＵＥおよびＦＡＬＳＥ、項の等式である。項の種類はタグ、整数、スイッチ識別子、フェーズ（ｓｗｉｔｃｈｅｄ、ｔｒａｎｓｍｉｔｔｅｄ、ｄｉｓｃａｒｄｅｄ）、および変数である。
【００３１】
モデル検査部６では、モデル生成部５で生成された状態遷移モデルが、ネットワーク要求仕様入力部４から入力されたネットワーク要求仕様を満たすか否かをモデル検査の方法を用いて判定し、その結果を検査結果出力部７に出力する。さらに、満たさない場合には、その実例であるＭｓｅｔの要素を検査結果出力部７に出力する。
【００３２】
検査結果出力部７は、検査結果および実例を所定のディスプレイ装置に表示する。
【００３３】
以下、様相論理の１つであるＣＴＬで記述された性質をモデル検査によって検証するソフトウェアであるＳＭＶをモデル検査部６で用いて、モデル生成部５で生成された状態遷移モデルが、ネットワーク要求仕様入力部４から入力されたネットワーク要求仕様を満たすか否かを検証する場合について説明する。
【００３４】
また、タグの集合Ｔｓｅｔ、ネットワークを構成するスイッチの識別子の集合Ｎｓｅｔ、ネットワーク構成を表す関数Ｎｔａｂｌｅ、転送ルールを表す関数Ｒｔａｂｅｌ、およびネットワーク要求仕様の具体例について以下に説明する。
【００３５】
タグの集合Ｔｓｅｔは、図３に示すように、｛ｔａｇＡ、ｔａｇＢ、ｎｕｌｌ｝である。
【００３６】
検証対象のネットワーク構成を図２に示す。図２に示すネットワークは２台のスイッＳＷ１（識別子「Ｓｗｉｔｃｈ１」）、スイッチＳＷ２（識別子「Ｓｗｉｔｃｈ２」））と４台の端末ＴＥ１〜ＴＥ４（識別子はそれぞれ「Ｔｅｒｍ１」〜「Ｔｅｒｍ４」）によって構成されている。なお、ここで言う端末もスイッチの一形態である。したがって、図２のネットワークはそれぞれ識別子「Ｓｗｉｔｃｈ１」、「Ｓｗｉｔｃｈ２」、「Ｔｅｒｍ１」、「Ｔｅｒｍ２」、「Ｔｅｒｍ３」、「Ｔｅｒｍ４」をもつ６つのスイッチによって構成されている。
【００３７】
スイッチの識別子の集合Ｎｓｅｔは、図４に示すように、｛Ｓｗｉｔｃｈ１、Ｓｗｉｔｃｈ２、Ｔｅｒｍ１、Ｔｅｒｍ２、Ｔｅｒｍ３、Ｔｅｒｍ４｝である。
【００３８】
端末ＴＥ１〜ＴＥ４が持つ唯一のポートの番号は、それぞれ「１」である。また、スイッチＳＷ１〜ＳＷ２は、３つのポートをそれぞれ持ち、３つのポートのそれぞれの番号は「１」〜「３」である。
【００３９】
図２に示すネットワークは、スイッチＳＷ１のポート「１」にスイッチＳＷ２のポート「１」が接続され、スイッチＳＷ１のポート「２」に端末ＴＥ１が接続され、スイッチＳＷ１のポート「３」に端末ＴＥ２が接続され、スイッチＳＷ２のポート「２」に端末ＴＥ３が接続され、スイッチＳＷ１のポート「３」に端末ＴＥ４が接続されて構成されている。
【００４０】
従って、このネットワーク構成では、（ａ１）「Ｓｗｉｔｃｈ１」のポート「１」から送信されたパケットは「Ｓｗｉｔｃｈ２」のポート「１」で受信される。（ａ２）「Ｓｗｉｔｃｈ１」のポート「２」から送信されたパケットは「Ｔｅｒｍ１」のポート「１」で受信される。（ａ３）「Ｓｗｉｔｃｈ１」のポート「３」から送信されたパケットは「Ｔｅｒｍ１」のポート「２」で受信される。（ａ４）「Ｓｗｉｔｃｈ２」のポート「１」から送信されたパケットは「Ｓｗｉｔｃｈ１」のポート「１」で受信される。（ａ５）「Ｓｗｉｔｃｈ２」のポート「２」から送信されたパケットは「Ｔｅｒｍ３」のポート「１」で受信される。（ａ６）「Ｓｗｉｔｃｈ２」のポート「３」から送信されたパケットは「Ｔｅｒｍ４」のポート「２」で受信される。（ａ７）「Ｔｅｒｍ１」のポート「１」から送信されたパケットは「Ｓｗｉｔｃｈ１」のポート「２」で受信される。（ａ８）「Ｔｅｒｍ２」のポート「１」から送信されたパケットは「Ｓｗｉｔｃｈ１」のポート「３」で受信される。（ａ９）「Ｔｅｒｍ３」のポート「１」から送信されたパケットは「Ｓｗｉｔｃｈ２」のポート「２」で受信される。（ａ１０）「Ｔｅｒｍ４」のポート「１」から送信されたパケットは「Ｓｗｉｔｃｈ２」のポート「３」で受信される。
【００４１】
上記（ａ１）〜（ａ１０）に示したネットワーク構成を表す関数Ｎｔａｂｌｅの一例を図５に示す。なお、図５のａ１〜ａ１０は、上記（ａ１）〜（ａ１０）をそれぞれ表したものである。
【００４２】
スイッチＳＷ１では、（ｂ１）ポート「１」で受信したタグ「ｔａｇＡ」を持つパケットはタグを「ｎｕｌｌ」に書換えてポート「２」から送信する。（ｂ２）ポート「１」で受信したタグ「ｔａｇＢ」を持つパケットはタグを「ｎｕｌｌ」に書換えてポート「３」から送信する。（ｂ３）ポート「２」で受信したタグ「ｎｕｌｌ」を持つパケットはタグを「ｔａｇＡ」に書換えてポート「１」から送信する。（ｂ４）ポート「３」で受信したタグ「ｎｕｌｌ」を持つパケットはタグを「ｔａｇＢ」に書換えてポート「１」から送信する。
【００４３】
スイッチＳＷ２では、（ｂ５）ポート「１」で受信したタグ「ｔａｇＡ」を持つパケットはタグを「ｎｕｌｌ」に書換えてポート「２」から送信する。（ｂ６）ポート「１」で受信したタグ「ｔａｇＢ」を持つパケットはタグを「ｎｕｌｌ」に書換えてポート「３」から送信する。（ｂ７）ポート「２」で受信したタグ「ｎｕｌｌ」を持つパケットはタグを「ｔａｇＡ」に書換えてポート「１」から送信する。（ｂ８）ポート「３」で受信したタグ「ｎｕｌｌ」を持つパケットはタグを「ｔａｇＢ」に書換えてポート「１」から送信する。
【００４４】
上記（ｂ１）〜（ｂ８）がスイッチＳＷ１、ＳＷ２の転送ルールである。上記（ｂ１）〜（ｂ８）に示したスイッチＳＷ１、ＳＷ２の転送ルールを表す関数Ｒｔａｂｌｅを図６に示す。なお、図６のｂ１〜ｂ８は、上記（ｂ１）〜（ｂ８）をそれぞれ表したものである。
【００４５】
端末ＴＥ１〜ＴＥ４での転送ルールは、（ｂ９）受信したパケットを全て破棄する、である。
【００４６】
図３に示したタグの集合Ｔｓｅｔ、上記（ａ１）〜（ａ１０）のネットワーク構成、上記（ｂ１）〜（ｂ９）の転送ルールの使用の目的は、（ｃ１）端末「Ｔｅｒｍ１」と「Ｔｅｒｍ３」がタグ「ｎｕｌｌ」を持つパケットを用いて通信し、（ｃ２）端末「Ｔｅｒｍ２」と「Ｔｅｒｍ４」がタグ「ｎｕｌｌ」を持つパケットを用いて通信するものであるとする。また、セキュリティ保障などの理由により、以下の（ｃ３）〜（ｃ４）が期待されている。（ｃ３）端末「Ｔｅｒｍ１」および「Ｔｅｒｍ３」から送出されたパケットは端末「Ｔｅｒｍ２」および「Ｔｅｒｍ４」には到達せず、（ｃ４）端末「Ｔｅｒｍ２」および「Ｔｅｒｍ４」から送出されたパケットは端末「Ｔｅｒｍ１」および「Ｔｅｒｍ３」には到達しない。さらに、ネットワークの負荷軽減などの理由により、（ｃ５）ネットワーク上の任意のパケットは将来破棄され、ネットワーク上を移動しつづけることはないことが期待されているものとする。
【００４７】
従って、このネットワークに要求される要求仕様は、以下の（ｄ１）〜（ｄ７）に示す通りとなる。（ｄ１）端末「Ｔｅｒｍ１」のポート「１」から送信されたタグ「ｎｕｌｌ」を持つパケットは将来端末「Ｔｅｒｍ３」に到達するような経路がある。（ｄ２）端末「Ｔｅｒｍ２」のポート「１」から送信されたタグ「ｎｕｌｌ」を持つパケットは将来端末「Ｔｅｒｍ４」に到達するような経路がある。（ｄ３）端末「Ｔｅｒｍ３」のポート「１」から送信されたタグ「ｎｕｌｌ」を持つパケットは将来端末「Ｔｅｒｍ１」に到達するような経路がある。（ｄ４）端末「Ｔｅｒｍ４」のポート「１」から送信されたタグ「ｎｕｌｌ」を持つパケットは将来端末「Ｔｅｒｍ２」に到達するような経路がある。（ｄ５）端末「Ｔｅｒｍ１」および「Ｔｅｒｍ３」から送出されたパケットが将来端末「Ｔｅｒｍ２」あるいは「Ｔｅｒｍ４」に到達するような経路がない。（ｄ６）端末「Ｔｅｒｍ２」および「Ｔｅｒｍ４」から送出されたパケットが将来端末「Ｔｅｒｍ１」あるいは「Ｔｅｒｍ３」に到達するような経路がない。（ｄ７）パケットはいずれの経路を通った場合にも将来破棄される。すなわち、パケットの転送が無限ループに陥ることはない。
【００４８】
図１４は、図１のネットワーク検証装置の処理動作を説明するためのフローチャートである。以下、図１４のフローチャートに沿って説明する。
【００４９】
タグ仕様入力部１では、図３に示したタグの集合Ｔｓｅｔが入力される（ステップＳ１０１）。
【００５０】
ネットワーク構成入力部２では、図４に示したネットワークを構成するスイッチの識別子の集合Ｎｓｅｔと、図５に示した、ネットワーク構成を表す関数Ｎｔａｂｌｅが入力される（ステップＳ１０１）。
【００５１】
転送ルール入力部３では、図６に示したような転送ルールを表す関数Ｒｔａｂｌｅが入力される（ステップＳ１０１）。なお、図６では、パケットの破棄を表わす空集合への対応の記述が省略されている。
【００５２】
モデル生成部５は、タグ仕様入力部１から入力されたＴｓｅｔ、ネットワーク構成入力部２から入力されたＮｓｅｔおよびＮｔａｂｌｅ、転送ルール入力部３から入力されたＲｔａｂｌｅから、ネットワークモデルＭを生成する（ステップＳ１０２）。ここでは、ネットワークモデルＭとして、例えばモデル検査ソフトウェアＳＭＶが解釈可能なプログラムを生成する。
【００５３】
モデル生成部５は、まず、Ｍｓｅｔを定義するテキストを生成する。このテキストは、それぞれタグｔ、スイッチｓ、ポートｎ、フェーズｐを表す変数ｔａｇ、ｓｗｉｔｃｈ、ｐｏｒｔ、ｐｈａｓｅと、それらが取り得る値の集合の宣言からなる。Ｍｓｅｔはこれらの変数の取り得る値の集合の直積集合となる。Ｍｓｅｔの一例を図７に示す。
【００５４】
変数ｓｗｉｔｃｈおよび変数ｔａｇの取り得る値の集合は、それぞれＮｓｅｔおよびＴｓｅｔである。また、変数ｐｏｒｔの取り得る値の集合はＮｔａｂｌｅおよびＲｔａｂｌｅに出現するポート番号の集合である。このポートの番号の集合をＰｓｅｔと呼ぶ。変数ｐｈａｓｅの取り得る値の集合は入力によらず｛ｓｗｉｔｃｈｅｄ，ｔｒａｎｓｍｉｔｔｅｄ，ｄｉｓｃａｒｄｅｄ｝である。この集合をＨｓｅｔと呼ぶ。
【００５５】
モデル生成部５は、次に、関数Ｍｔｒａｎｓを生成する。本実施形態では、関数Ｍｔｒａｓを、８つのデータを１組とする（ｔ，ｓ，ｎ，ｐ，ｔ´，ｓ´，ｎ´，ｐ´）を真（ＴＲＵＥ）または偽（ＦＡＬＳＥ）のいずれかの値に対応させる関数ＴＲＡＮＳを用いて定義する。Ｍｔｒａｎｓ（ｔ，ｓ，ｎ，ｐ）の値は，ＴＲＡＮＳ（ｔ，ｓ，ｎ，ｐ，ｔ´，ｓ´，ｎ´，ｐ´）の値がＴＲＵＥとなる４つ組（ｔ´，ｓ´，ｎ´，ｐ´）の全体の集合として定義される。ＴＲＡＮＳの具体例を図８に示す。
【００５６】
なお、図８において、「ＣＵＲＲＥＮＴ（ｔ，ｓ，ｎ）」という表現は、「ｔａｇ＝ｔ＆ｓｗｉｔｃｈ＝ｓ＆ｐｏｒｔ＝ｎ」の略記法であり、「ＮＥＸＴ（ｔ，ｓ，ｎ，ｐ）」という表現は、「ｎｅｘｔ（ｔａｇ）＝ｔ＆ｎｅｘｔ（ｓｗｉｔｃｈ）＝ｓ＆ｎｅｘｔ（ｐｏｒｔ）＝ｎ＆ｎｅｘｔ（ｐｈａｓｅ）＝ｐ」の略記法である。また、ｔａｇ、ｓｗｉｔｃｈ、ｐｏｒｔ、ｐｈａｓｅ、ｎｅｘｔ（ｔａｇ）、ｎｅｘｔ（ｓｗｉｔｃｈ）、ｎｅｘｔ（ｐｏｒｔ）、ｎｅｘｔ（ｐｈａｓｅ）は、それぞれ引数ｔ、ｓ、ｎ、ｐ、ｔ´、ｓ´、ｎ´、ｐ´を表わす。
【００５７】
ｔが「ｔａｇ」のときには、変数ｔａｇのとり得る値の全て、すなわち、「ｎｕｌｌ」「ｔａｇＡ」「ｔａｇＢ」のうちのいずれであってもよいという意味を表す。
【００５８】
また、図８において、「ｐｈａｓｅ＝ｓｗｉｔｃｈｅｄ：ｃａｓｅ  …  ｅｓａｃ；」の部分が転送ルールに対応し、「ｐｈａｓｅ＝ｔｒａｎｓｍｉｔｔｅｄ：ｃａｓｅ  …  ｅｓａｃ；」の部分がネットワーク構成に対応する。
【００５９】
例えば、図８の転送ルールに記載されている「ＣＵＲＲＥＮＴ（ｔａｇＡ，Ｓｗｉｔｃｈ１，１）」や「ＮＥＸＴ（ｎｕｌｌ，Ｓｗｉｔｃｈ１，２，Ｔｒａｎｓｍｉｔｔｅｄ）」のような「ｅｘｐ．１＆ｅｘｐ．２」という表現の値は、「ｅｘｐ．１」および「ｅｘｐ．２」の値がともにＴＲＵＥであるときＴＲＵＥとし、そうでないときはＦＡＬＳＥであるとする。
【００６０】
例えば、図８の転送ルールに記載されている「ｐｈａｓｅ＝ｓｗｉｔｃｈｅｄ」のような等式「ｘ＝ｙ」という表現は、「ｘ」と「ｙ」の値が等しいときＴＲＵＥ、そうでないときＦＡＬＳＥであるとする。
【００６１】
例えば、図８の転送ルールに記載されている「ｃａｓｅ  ＣＵＲＲＥＮＴ（ｔａｇＡ，Ｓｗｉｔｃｈ１，１）：ＮＥＸＴ（ｎｕｌｌ，Ｓｗｉｔｃｈ１，２，Ｔｒａｎｓｍｉｔｔｅｄ）…」のような「ｃａｓｅ  ｃｏｎｄ＿１：ｅｘｐ＿；  ｃｏｎｄ＿２：ｅｘｐ＿２；  …ｃｏｎｄ＿ｎ：ｅｘｐ＿ｎ；  ｅｓａｃ」という表現の値は、「ｃｏｎｄ＿１」、「ｃｏｎｄ＿２」、…の値を順に調べ、最初にその値がＴＲＵＥになった「ｃｏｎｄ＿ｉ」に対応する「ｅｘｐ＿ｉ」の値であるとする。また、「ｃｏｎｄ＿１」、「ｃｏｎｄ＿２」、…の値が全てＦＡＬＳＥであるときは、値はＦＡＬＳＥであるとする。
【００６２】
モデル生成部５は、以上のＭｓｅｔおよびＭｔｒａｎｓを定義する関数ＴＲＡＮＳのテキスト表現をまとめて、図９に示すような状態遷移モデルＭを生成する。
【００６３】
このように、モデル生成部５では、タグの集合Ｔｓｅｔと各スイッチ（スイッチＳＷ１〜ＳＷ２、ＴＥ１〜ＴＥ４）の識別子の集合Ｎｓｅｔとネットワーク構成を表す関数Ｎｔａｂｌｅと転送ルールを表す関数Ｒｔａｂｌｅとから、タグの集合の１つの要素と、複数のスイッチのうちの１つの識別子と、当該スイッチのポートの識別子と、当該通信機器の動作のモードに対応するフェーズ（例えば、当該通信機器からパケットを送信するフェーズ（送信モード）である「ｔｒａｓｎｍｉｔｔｅｄ」と当該通信機器の当該ポートに入力したパケットを他のポートから出力するフェーズ（転送モード）である「ｓｗｉｔｃｈｅｄ」と当該通信機器に入力したパケットを破棄するフェーズ（パケット破棄モード）である「ｄｉｓｃａｒｄｅｄ」のうちのいずれか１つ）で特定される図２のネットワークの複数の状態（ｔ，ｓ，ｎ，ｐ）のうちの１つから他の１つの状態（ｔ´，ｓ´，ｎ´，ｐ´）への当該ネットワークで起こり得る複数の状態遷移をそれぞれ表す複数の状態遷移データを含むネットワークモデルＭを生成する。なお、本実施形態の関数ＴＲＡＮＳは、上記複数の状態遷移データに対応する。
【００６４】
ネットワーク要求仕様入力部４では、様相論理の１つであるＣＴＬによって表現された例えば、図１０に示したようなネットワーク要求仕様が入力される（図１４のステップＳ１０３）。図１０の７つの各「ＳＰＥＣ」内の記述は、それぞれ上記（ｄ１）〜（ｄ２）に示したネットワーク要求仕様ｄ１〜ｄ７を表している。
【００６５】
ネットワーク要求仕様は、例えば「＝」「！（でない）」「｜（または）」「＆（かつ）」「−＞」などの種々の演算子や「ＥＦ」「ＡＦ」「−＞」などの記号と、変数ｔ（タグ）、変数（スイッチの識別子）、変数ｎ（ポート番号）、変数ｐ（フェーズ）を用いて所望の状態や所望の状態遷移、これらに対する条件などを記述した論理式などである。
【００６６】
なお、図１０において、例えばネットワーク要求仕様ｄ５の「（ｓｗｉｔｃｈ＝Ｔｅｒｍ１｜ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」のような「（ｅｘｐ＿１｜ｅｘｐ＿２）」という表現は、「ｅｘｐ＿１またはｅｘｐ＿２」を意味し、ｅｘｐ１およびｅｘｐ２のうちの少なくとも一方がＴＲＵＥの値をとるとき、そのときのみＴＲＵＥの値をとる。
【００６７】
また、例えば、ネットワーク要求仕様ｄ１の「ｔａｇ＝ｎｕｌｌ＆ｓｗｉｔｃｈ＝Ｔｅｒｍ１＆ｐｏｒｔ＝１＆ｐｈａｓｅ＝ｔｒａｎｓｍｉｔｔｅｄ−＞ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」のような「ｅｘｐ＿１−＞ｅｘｐ＿２」という表現は、「ｅｘｐ＿１ならばｅｘｐ＿２」を意味し、「！ｅｘｐ＿２」という表現は、「ｅｘｐ＿２でない」を意味し、その値は、ｅｘｐ＿２の値がＴＲＵＥのときはＦＡＬＳＥ、ｅｘｐ＿２の値がＦＡＬＳＥのときＴＲＵＥとなる。
【００６８】
さらに、「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」のような「ＥＦ  ｅｘｐ」という表現は「ある遷移について、いつかｅｘｐが成り立つ状態になる」という意味であり、「ＡＦ（ｐｈａｓｅ＝ｄｉｓｃａｒｄｅｄ）」のような「ＡＦ  ｅｘｐ」という表現は「全ての遷移について、いつかｅｘｐが成り立つ状態になる」という意味である。これらを言い換えれば、パケットがネットワーク上を転送されていく経路について、「ＥＦ  ｅｘｐ」は「ある経路を通るパケットはｅｘｐを満たす状態になる」を意味し、「ＡＦ  ｅｘｐ」は、「すべての経路についてパケットはｅｘｐを満たす状態になる」を意味する。
【００６９】
モデル検査部６には、モデル生成部５で生成された図９に示すような状態遷移モデルＭ（テキスト）と、ネットワーク要求仕様入力部４で入力された、例えば、図１０のｄ１〜ｄ７に示すようなネットワーク要求仕様を表すテキストをＳＭＶソフトウェアに入力する。その出力として得られるものでは、入力されたネットワーク要求仕様が保証されるかそうでないかに応じて、当該ネットワーク要求仕様に、“ｉｓ  ｔｒｕｅ”あるいは“ｉｓ  ｆａｌｓｅ”を付加したテキストである。当該出力のテキストは検査結果出力部７に送られる（図１４のステップＳ１０４）。
【００７０】
検査結果出力部７は、モデル検査部６から送られた検査結果のテキストをユーザに表示する（図１４のステップＳ１０５）。
【００７１】
例えば、図９に示した状態遷移モデルＭが生成され、図１０のネットワーク要求仕様ｄ１〜ｄ７のそれぞれが入力されたときに、モデル検査部６から出力される検査結果を図１１に示す。図１１の７つの各「ｓｐｅｃｉｆｉｃａｔｉｏｎ」内の記述は、図１０のネットワーク要求仕様ｄ１〜ｄ２のそれぞれに対応する検査結果ｅ１〜ｅ７を表している。なお、図９のモデルＭは、図１０のネットワーク要求仕様ｄ１〜ｄ７を全て満たすネットワーク構成と、転送ルールを表しているので、図１０のネットワーク要求仕様ｄ１〜ｄ７のそれぞれに対応する検査結果ｅ１〜ｅ７は、全て「ｉｓ  ｔｒｕｅ」が付加されている。
【００７２】
ところで、「「Ｔｅｒｍ１」のポート「１」から送出されたタグ「ｎｕｌｌ」を持つパケットは、将来端末「Ｔｅｒｍ２」に到達する。」という意味をもつ、図１２に示すようなネットワーク要求仕様ｄ８が（ネットワーク要求仕様入力部４からモデル検索部６へ）入力されたとする。このネットワーク要求仕様ｄ８は、図９のモデルＭでは成立しないので、図１３に示すように、ネットワーク要求仕様ｄ８に「ｉｓ  ｆａｌｓｅ」の付加されたテキストが検査結果ｅ８として出力される。さらに、入力されたネットワーク要求仕様が不成立である場合には、図１３に示すように、検査結果ｅ８に反例を表すテキストｆ８が追加されて、モデル検査部６から出力される。
【００７３】
次に、図１４のステップＳ１０４のモデル検査部６の処理動作について説明する。モデル検査部６では、モデルＭがもつ状態（ｔ，ｓ，ｎ，ｐ）の全部またはそのなかから得られた所定の条件を満たす状態について、ネットワーク要求仕様で指定された状態の真偽を判定し、全て真の場合には「ｔｒｕｅ」を出力し、そうでない場合には「ｆａｌｓｅ」とともに偽となる状態の１つを出力する。
【００７４】
モデルＭがもつ状態（ｔ，ｓ，ｎ，ｐ）と、ネットワーク要求仕様で指定される状態との間の具体的な判定方法は以下のように再帰的に行う。
【００７５】
（１）ネットワーク要求仕様が「ｔａｇ＝ｃ」の場合、「ｃ」が「ｔ」と等しければ真となり、そうでない場合は偽となる。
【００７６】
（２）ネットワーク要求仕様が「ｓｗｉｔｃｈ＝ｃ」の場合、「ｃ」が「ｓ」と等しければ真となり、そうでなければ偽となる。
【００７７】
（３）ネットワーク要求仕様が「ｐｏｒｔ＝ｃ」の場合、「ｃ」が「ｎ」と等しければ真となり、そうでなければ偽となる。
【００７８】
（４）ネットワーク要求仕様が「ｐｈａｓｅ＝ｃ」の場合、「ｃ」が「ｐ」と等しければ真となり、そうでなければ偽となる。
【００７９】
（５）ネットワーク要求仕様が「！ｅｘｐ」の場合、「ｅｘｐ」が真ならば偽となり、「ｅｘｐ」が偽なら真となる。
【００８０】
（６）ネットワーク要求仕様が「ｅｘｐ１＆ｅｘｐ２」の場合、「ｅｘｐ１」および「ｅｘｐ２」がともに真ならば真となり、そうでない場合には偽となる。
【００８１】
（７）ネットワーク要求仕様が「ｅｘｐ１｜ｅｘｐ２」の場合、「ｅｘｐ１」と「ｅｘｐ２」のうち少なくとも一方が真ならば真となる。それ以外の場合には偽となる。
【００８２】
（８）ネットワーク要求仕様が「ｅｘｐ１−＞ｅｘｐ２」の場合、「ｅｘｐ１」が偽であるか、「ｅｘｐ１」と「ｅｘｐ２」がともに真である場合に真となる。それ以外の場合は偽となる。
【００８３】
（９）ネットワーク要求仕様が「ＥＦ  ｅｘｐ」の場合、図１５に示すフローチャートに従って集合Ｒを求める。そして、ステップＳ９で得られた集合Ｒが、状態（ｔ，ｓ，ｎ，ｐ）を要素としてもつならば真となり、そうでない場合には偽となる。
【００８４】
例えば、図１０のネットワーク要求仕様ｄ１「ｔａｇ＝ｎｕｌｌ＆ｓｗｉｔｃｈ＝Ｔｅｒｍ１＆ｐｏｒｔ＝１＆ｐｈａｓｅ＝ｔｒａｎｓｍｉｔｔｅｄ−＞ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」がネットワーク要求仕様入力部４から入力されて、モデル検査部６で、当該ネットワーク要求仕様ｄ１により図９のモデルＭを検証する場合について説明する。
【００８５】
このネットワーク要求仕様では、（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）以外の状態では、「ｔａｇ＝ｎｕｌｌ」、「ｓｗｉｔｃｈ＝Ｔｅｒｍ１」、「ｐｏｒｔ＝１」、「ｐｈａｓｅ＝ｔｒａｎｓｍｉｔｔｅｄ」のうちの少なくとも１つが偽になる。状態（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）では、「ｔａｇ＝ｎｕｌｌ」、「ｓｗｉｔｃｈ＝Ｔｅｒｍ１」、「ｐｏｒｔ＝１」、「ｐｈａｓｅ＝ｔｒａｎｓｍｉｔｔｅｄ」が全て真になる。このとき、ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）が真ならば当該ネットワーク要求仕様ｄ１は真となる。そこで、まず、ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）を満たす状態を図１５に示すフローチャートに従って求める。
【００８６】
モデルＭの状態（ｔ，ｓ，ｎ，ｐ）のうち、ｔ＝Ｔｅｒｍ３を満たす状態の集合Ｔを求める（ステップＳ１）。この集合を図１６に示す。また、ＲをＴに等しい集合とする（ステップＳ２）。Ｔは空集合でないので、ステップＳ４へ進む。次に、Ｔの最後の要素（ｔａｇＢ、Ｔｅｒｍ３，３，ｄｉｓｃａｒｄｅｄ）をとり（ステップＳ４）、Ｔからこの要素を削除する（ステップＳ５）。次に、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｔａｇＢ，Ｔｅｒｍ３，３，ｄｉｓｃａｒｄｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する（ステップＳ６）。この場合、（ｔａｇＢ、Ｔｅｒｍ３，３，ｄｉｓｃａｒｄｅｄ）のみがあるのでステップＳ７へ進む。ステップＳ７では、（ｔａｇＢ、Ｔｅｒｍ３，３，ｄｉｓｃａｒｄｅｄ）がＲに含まれるか判定する。この場合、含まれるので、ステップＳ３へ戻る。ステップＳ４で、集合Ｔからフェーズがｄｉｓｃａｒｄｅｄである要素を選んだ場合には、上記同様にして、Ｔから当該要素が削除され、ステップＳ３〜ステップＳ７までを９回繰返す。その結果、集合Ｔは図１７に示すようになる。このとき、集合Ｒは、図１６と同様である。
【００８７】
ここで、ステップＳ３へ戻り、集合Ｔは空集合でないので、さらに、ステップＳ４へ進む。ステップＳ４で（ｔａｇＢ，Ｔｅｒｍ３，３，ｔｒａｎｓｍｉｔｔｅｄ）が選ばれた場合は、ステップＳ５で集合Ｔから（ｔａｇＢ，Ｔｅｒｍ３，３，ｔｒａｎｓｍｉｔｔｅｄ）を除き、ステップＳ６で、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｔａｇＢ，Ｔｅｒｍ３，３，ｔｒａｎｓｍｉｔｔｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する。この場合には存在しないので、ステップＳ３へ戻る。ステップＳ４で、集合Ｔからフェーズがｔｒａｎｓｍｉｔｔｅｄである要素を選んだ場合には、上記同様にして、Ｔから当該要素が削除され、ステップＳ３〜ステップＳ６までを９回繰返す。その結果、集合Ｔは図１８に示すようになる。このとき、集合Ｒは、図１６と同様である。
【００８８】
ここで、ステップＳ３へ戻り、集合Ｔは空集合でないので、さらに、ステップＳ４へ進む。ステップＳ４で（ｔａｇＢ，Ｔｅｒｍ３，３，ｓｗｉｔｃｈｅｄ）が選ばれた場合は、ステップＳ５で集合Ｔから（ｔａｇＢ，Ｔｅｒｍ３，３，ｓｗｉｔｃｈｅｄ）を除き、ステップＳ６で、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｔａｇＢ，Ｔｅｒｍ３，３，ｓｗｉｔｃｈｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する。このような状態は無いので、ステップＳ３へ戻る。ステップＳ４で、ポートが「２」、「３」の状態が選ばれた場合には、上記同様にして、ステップＳ３〜ステップＳ６を繰返す。ステップＳ４で、ポートが「２」や「３」であるような状態が選ぶこの繰返しを６回行うと、集合Ｔは図１９に示すようになる。このとき、集合Ｒは、図１６と同様である。
【００８９】
ここで、ステップＳ３へ戻り、集合Ｔは空集合でないので、さらに、ステップＳ４へ進む。ステップＳ４で（ｔａｇＢ，Ｔｅｒｍ３，１，ｓｗｉｔｃｈｅｄ）が選ばれた場合は、ステップＳ５で集合Ｔから（ｔａｇＢ，Ｔｅｒｍ３，１，ｓｗｉｔｃｈｅｄ）を除き、ステップＳ６で、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｔａｇＢ，Ｔｅｒｍ３，１，ｓｗｉｔｃｈｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する。ここでは、状態（ｔａｇＢ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）のみがあるのでステップＳ７へ進む。ステップＳ７では、この状態が集合Ｒに含まれるか否か判定する。この場合、Ｒに含まれていないので、ステップＳ８へ進み、Ｒ、Ｔにこの状態を加えて、ステップＳ３へ戻る。ステップＳ４で、（ｔａｇＡ，Ｔｅｒｍ３，１，ｓｗｉｔｃｈｅｄ）、（ｎｕｌｌ，Ｔｅｒｍ３，１，ｓｗｉｔｃｈｅｄ）が選ばれた場合も上記同様であり、ステップＳ４からステップＳ８を３回繰り返した後では、ＴおよびＲはそれぞれ図２０、図２１に示すようになる。
【００９０】
ここで、ステップＳ３へ戻り、集合Ｔは空集合でないので、さらに、ステップＳ４へ進む。ステップＳ４で（ｔａｇＢ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）が選ばれた場合は、ステップＳ５で集合Ｔから（ｔａｇＢ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）を除き、ステップＳ６で、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｔａｇＢ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する。このような状態はないので、ステップＳ３へ戻る。ここで、ステップＳ４で、（ｔａｇＡ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）が選ばれた場合も同様なので、ステップＳ３〜ステップＳ６を２回繰返した後には、Ｔは図２２に示すようになる。Ｒは図２１と同様である。
【００９１】
ここで、ステップＳ３へ戻り、集合Ｔは空集合でないので、さらに、ステップＳ４へ進む。ステップＳ４でＴの唯一の要素（ｎｕｌｌ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）を選ぶ。ステップＳ５で集合Ｔから（ｎｕｌｌ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）を除き、ステップＳ６で、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｎｕｌｌ，Ｓｗｉｔｃｈ２，２，ｔｒａｎｓｍｉｔｔｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する。ここでは、状態（ｔａｇＡ，Ｓｗｉｔｃｈ２，１，ｓｗｉｔｃｈｅｄ）のみがあるのでステップＳ７へ進む。ステップＳ７では、この状態が集合Ｒに含まれるか否か判定する。この場合、Ｒに含まれていないので、ステップＳ８へ進み、Ｒ、Ｔにこの状態を加えて、このステップＳ３からステップＳ８を４回繰り返す過程で、Ｔの要素は、図２３、図２４、図２５、図２６に示すように変化する。Ｒの要素にはステップＳ４で選ばれた要素が次々に加えられ、図２７に示すようになる。
【００９２】
ここで、ステップＳ３へ戻り、集合Ｔは空集合でないので、さらに、ステップＳ４へ進む。ステップＳ４でＴの唯一の要素（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）を選ぶ。ステップＳ５で集合Ｔから（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）を除き、ステップＳ６で、ＴＲＡＮＳ（ｔ´，ｓ´，ｎ´，ｐ´，ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）の値が「ＴＲＵＥ」になるような状態（ｔ´，ｓ´，ｎ´，ｐ´）があるか否かを判定する。このような状態はないので、ステップＳ３へ進む。ステップＳ３では、Ｔが空集合なので、ステップＳ９へ進み、図２７に示す集合Ｒを出力して終了する。
【００９３】
この最終的に得られた集合Ｒの要素には、（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）が存在するので、ネットワーク要求仕様ｄ１は真（ｔｒｕｅ）となる。
【００９４】
次に、図１２に示したネットワーク要求仕様ｄ８が入力された場合について説明する。この場合も、ネットワーク要求仕様ｄ１の場合と同様にして、まず、図１５のフローチャートに従って、ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ２）を満たす集合Ｒを求める。この場合、ステップＳ９で得られる集合Ｒは、（ｎｕｌｌ，Ｓｗｉｔｃｈ１，３，ｔｒａｎｓｍｉｔｔｅｄ）、（ｔａｇＢ，Ｓｗｉｔｃｈ１，１，ｓｗｉｔｃｈｅｄ）、（ｔａｇＢ，Ｓｗｉｔｃｈ２，１，ｔｒａｎｓｍｉｔｔｅｄ）、（ｎｕｌｌ，Ｓｗｉｔｃｈ２，３，ｓｗｉｔｃｈｅｄ）、（ｎｕｌｌ，Ｔｅｒｍ４，１，ｔｒａｎｓｍｉｔｔｅｄ）からなる集合と、モデルＭの状態（ｔ´，ｓ´，ｎ´，ｐ´）のうち、ｓ´がＴｅｒｍ２である状態の集合との和集合となる。
【００９５】
この集合Ｒには、ネットワーク要求仕様ｄ８の前提部として指定されている状態（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）が含まれていない。従って、当該ネットワーク要求仕様ｄ８は偽（ｆａｌｓｅ）であると判定される。この場合には、当該要求仕様を満たさない状態（ｎｕｌｌ，Ｔｅｒｍ１，１，ｔｒａｎｓｍｉｔｔｅｄ）も検査結果出力部７から出力される。
【００９６】
以上説明したように、上記実施形態によれば、少なくとも１つのポートをそれぞれ有する複数の通信機器を、それぞれのポートを介して接続してなる検証対象のネットワーク上で転送されるパケットに用いられるタグの集合と、各通信機器の識別子の集合と、パケットを送信する各通信機器の識別子およびそのポートの識別子とパケットを受信する各通信機器の識別子およびそのポートの識別子との対応関係を表すネットワーク構成データと、受信したパケットを転送する各通信機器の識別子およびそのポートの識別子および当該ポートに入力されたパケットのタグと、当該パケットを当該通信機器から出力する際に用いるポートの識別子とタグとの対応関係を表す上記検証対象のネットワーク上でのパケットの転送ルールデータを基に、タグの集合と、各通信機器の識別子と、各通信機器のポートの識別子と、各通信機器の動作モード（送信フェーズ、転送フェーズ、パケットを破棄するフェーズ）とで特定される上記検証対象のネットワークの状態遷移を示す状態遷移データを含むネットワークモデルを生成する。
【００９７】
各通信機器の識別子と、各通信機器のポートの識別子と、各通信機器の動作モード（送信フェーズ、転送フェーズ、パケットを破棄するフェーズ）と特定される検証対象のネットワークの複数の状態のうち、所望の状態と当該所望の状態に対する条件と当該所望の状態間の状態遷移と当該所望の状態遷移に対する条件のうちの少なくとも１つを表す当該検証対象のネットワークに対する要求仕様を入力して、上記ネットワークモデルが上記要求仕様を満たすか否かを検証して、検証結果を出力する。
【００９８】
このような構成により、上記実施形態によれば、タグを付加されたパケットを転送するネットワーク上でのパケットの転送のされ方やネットワーク構成などを、当該ネットワークの状態やその遷移から容易に検証することができるモデルを、ネットワーク構成を表すデータと当該ネットワークを構成する各スイッチの転送ルールを表すデータから容易に生成することができる。
【００９９】
また、タグを付加されたパケットを転送するネットワーク上でのパケットの転送のされ方やネットワーク構成を、当該ネットワークを実際に稼働させることなく容易にしかも効率よく検証することができる。
【０１００】
本発明の実施の形態に記載した本発明の手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０１０１】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１０２】
【図１】本発明の実施形態に係るネットワーク検証装置の構成例を示した図。
【図２】検証対象のネットワークの構成例を示した図。
【図３】タグの集合Ｔｓｅｔの一具体例を示した図。
【図４】スイッチの識別子の集合Ｎｓｅｔの一具体例を示した図。
【図５】ネットワーク構成を表す関数Ｎｔａｂｌｅの一具体例を示した図。
【図６】転送ルールを表す関数Ｒｔａｂｌｅの一具体例を示した図。
【図７】モデル生成部で生成されるＭｓｅｔの一具体例を示した図。
【図８】モデル生成部で生成される関数ＴＲＡＮＳの一具体例を示した図。
【図９】モデル生成部で生成される状態遷移モデルの一具体例を示した図。
【図１０】ネトワーク要求仕様の具体例を示した図。
【図１１】モデル検査部から出力あれる検査結果の具体例を示した図。
【図１２】ネットワーク要求仕様の他の例を示した図。
【図１３】図１２のネットワーク要求仕様に対応するモデル検索部での検査結果を示した図。
【図１４】図１のネットワーク検証装置の全体的な処理動作を説明するための図。
【図１５】モデル検査部の処理動作の一例であって、ネトワーク要求仕様に記述され得る、条件「ＥＦ  ｅｘｐ」を満たす状態の集合を求める処理動作を説明するためのフローチャート。
【図１６】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図１７】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図１８】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図１９】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２０】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２１】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２２】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２３】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２４】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２５】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２６】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【図２７】図１０のネットワーク要求仕様ｄ１に含まれる条件「ＥＦ（ｓｗｉｔｃｈ＝Ｔｅｒｍ３）」を満たす状態の集合を求める処理動作を説明するための図。
【符号の説明】
【０１０３】
１…タグ仕様入力部、２…ネットワーク構成入力部、３…転送ルール入力部、４…ネットワーク要求仕様入力部、５…モデル生成部、６…モデル検査部、７…検査結果出力部、ＳＷ１、ＳＷ２…スイッチ、ＴＥ１〜ＴＥ４…端末。
【図１】
2005218038.tif 000003
【図２】
2005218038.tif 000004
【図３】
2005218038.tif 000005
【図４】
2005218038.tif 000006
【図５】
2005218038.tif 000007
【図６】
2005218038.tif 000008
【図７】
2005218038.tif 000009
【図８】
2005218038.tif 000010
【図９】
2005218038.tif 000011
【図１０】
2005218038.tif 000012
【図１１】
2005218038.tif 000013
【図１２】
2005218038.tif 000014
【図１３】
2005218038.tif 000015
【図１４】
2005218038.tif 000016
【図１５】
2005218038.tif 000017
【図１６】
2005218038.tif 000018
【図１７】
2005218038.tif 000019
【図１８】
2005218038.tif 000020
【図１９】
2005218038.tif 000021
【図２０】
2005218038.tif 000022
【図２１】
2005218038.tif 000023
【図２２】
2005218038.tif 000024
【図２３】
2005218038.tif 000025
【図２４】
2005218038.tif 000026
【図２５】
2005218038.tif 000027
【図２６】
2005218038.tif 000028
【図２７】
2005218038.tif 000029