(57)【要約】【課題】  ネットワーク特性検証方法を提供する。【解決手段】  ネットワーク特性検証方法は、検証すべきネットワークの１又は複数の特性を得るステップと、前記ネットワークの中の第１ネットワーク装置のための第１転送ルールを得るステップであって、前記第１転送ルールは、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す、ステップと、を有して良い。前記方法は、前記ネットワークの中の第２ネットワーク装置のための第２転送ルールを得るステップであって、前記第２転送ルールは、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す、ステップと、前記第１及び前記第２転送ルールに基づきプッシュダウンオートマトンを生成するステップと、を更に有して良い。前記方法は、前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップを更に有して良い。【選択図】  図２
2018117336.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク特性検証の方法であって、前記方法は、
検証すべきネットワークの１又は複数の特性を得るステップと、
前記ネットワークの中の第１ネットワーク装置のための第１転送ルールを得るステップであって、前記第１転送ルールは、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す、ステップと、
前記ネットワークの中の第２ネットワーク装置のための第２転送ルールを得るステップであって、前記第２転送ルールは、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す、ステップと、
前記第１転送ルール及び前記第２転送ルールに基づきプッシュダウンオートマトンを生成するステップと、
前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、
を有する方法。
【請求項２】
前記第１ネットワーク装置及び前記第２ネットワーク装置は、カプセル化動作及びカプセル化解除動作のうちの少なくとも１つをパケットに対して実行するよう構成される、請求項１に記載の方法。
【請求項３】
前記第１ネットワーク装置及び前記第２ネットワーク装置は、ＭＰＬＳ（multiprotocol  label  switching）を用いて動作するよう構成される、請求項２に記載の方法。
【請求項４】
前記第１ネットワーク装置から前記第２ネットワーク装置へ前記ネットワークを横断するパケットの到達可能性グラフを生成するステップ、を更に有する請求項１に記載の方法。
【請求項５】
前記ネットワークの物理レイアウトを得るステップと、
前記ネットワークの前記物理レイアウト並びに前記第１転送ルール及び前記第２転送ルールに基づき、所与の時点の前記ネットワークのデータプレーンのレイアウトを得るステップと、
を更に有する請求項１に記載の方法。
【請求項６】
前記プッシュダウンオートマトンを生成するステップは、
各ネットワーク装置を前記プッシュダウンオートマトンの中の１又は複数の状態として表すステップと、
前記第１転送ルール及び第２転送ルールのうちの各転送ルールを、カプセル化動作に対応するプッシュ動作及びカプセル化解除動作に対応するポップ動作のうちの１つとして符号化するステップと、
前記プッシュ動作及び前記ポップ動作を、前記１又は複数の状態の間の遷移として使用するステップと、
を有する、請求項１に記載の方法。
【請求項７】
前記飽和に基づくアルゴリズムを適用するステップは、
前記ネットワークの中のネットワーク装置の間の各接続を、入力状態、出力状態、及び前記入力状態から前記出力状態への遷移動作を有するタプルとして表すステップであって、前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１又は複数を含む、ステップと、
各タプルについて、前記遷移動作が前記プッシュ動作を含むか否かを決定するステップと、
を有する、請求項６に記載の方法。
【請求項８】
前記遷移動作が前記プッシュ動作を含まないタプルの各々について、
所与の到着タプルの所与の到着遷移動作が前記プッシュ動作を含むか否かを決定するために、先行状態からの前記入力状態に到着する遷移を表す到着タプルの各々を分析するステップであって、
前記所与の到着遷移動作が前記プッシュ動作を含む場合、前記先行状態から前記出力状態へ到着する遷移を表す拡張到着タプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記所与の到着遷移動作が前記プッシュ動作を含まない場合、前記所与の到着タプルが前記プッシュダウンオートマトンに追加されていることを確認する、ステップと、
前記入力状態から更なる状態への遷移を表す拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するために、前記出力状態から前記更なる状態へ出発する遷移を表す出発タプルの各々を分析するステップであって、否の場合、前記拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
更にを有する請求項７に記載の方法。
【請求項９】
前記遷移動作が前記プッシュ動作を含むタプルの各々について、
所与の出発タプルの所与の出発遷移動作が前記ポップ動作を含むか否かを決定するために、前記出力状態から更なる状態へ出発する遷移を表す出発タプルの各々を分析するステップと、
前記所与の出発遷移動作が前記ポップ動作を含む場合、前記入力状態から前記更なる状態への遷移を表す拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するステップであって、前記プッシュダウンオートマトンに含まれない場合、前記拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
を更に有する請求項７に記載の方法。
【請求項１０】
前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１より多くを含み、前記入力状態及び前記出力状態が、２つのネットワーク装置の間に介在ネットワーク装置を有する該２つのネットワーク装置を表すようにする、請求項７に記載の方法。
【請求項１１】
前記１又は複数の特性のうちの少なくとも１つはネットワーク経路を含み、前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップは、
前記プッシュダウンオートマトンへの前記飽和に基づくアルゴリズムの適用により生成される前記ネットワーク経路の観測経路を、前記ネットワーク経路の期待ネットワーク経路と比較するステップと、
前記観測経路が前記期待ネットワーク経路に一致することに基づき、前記ネットワーク経路を検証するステップと、
を有する、請求項１に記載の方法。
【請求項１２】
命令を有する１又は複数の非一時的コンピュータ可読媒体であって、前記命令は、１又は複数のプロセッサにより実行されることに応答して、システムに工程を実行させ、前記工程は、
検証すべきネットワークの１又は複数の特性を得るステップと、
前記ネットワークの中の第１ネットワーク装置のための第１転送ルールを得るステップであって、前記第１転送ルールは、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す、ステップと、
前記ネットワークの中の第２ネットワーク装置のための第２転送ルールを得るステップであって、前記第２転送ルールは、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す、ステップと、
前記第１転送ルール及び前記第２転送ルールに基づきプッシュダウンオートマトンを生成するステップと、
前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、
を有する、コンピュータ可読媒体。
【請求項１３】
前記第１ネットワーク装置及び前記第２ネットワーク装置は、ＭＰＬＳ（multiprotocol  label  switching）を用いて動作するよう構成される、請求項１２に記載のコンピュータ可読媒体。
【請求項１４】
前記プッシュダウンオートマトンを生成するステップは、
各ネットワーク装置を前記プッシュダウンオートマトンの中の状態として表すステップと、
前記第１転送ルール及び前記第２転送ルールのうちの各転送ルールを、カプセル化動作に対応するプッシュ動作及びカプセル化解除動作に対応するポップ動作のうちの１つとして符号化するステップと、
前記プッシュ動作及び前記ポップ動作を、前記状態の間の遷移として使用するステップと、
を有する、請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記飽和に基づくアルゴリズムを適用するステップは、
前記ネットワークの中のネットワーク装置の間の各接続を、入力状態、出力状態、及び前記入力状態から前記出力状態への遷移動作を有するタプルとして表すステップであって、前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１又は複数を含む、ステップと、
各タプルについて、前記遷移動作が前記プッシュ動作を含むか否かを決定するステップであって、
前記遷移動作が前記プッシュ動作を含まないタプルの各々について、
所与の到着タプルの所与の到着遷移動作が前記プッシュ動作を含むか否かを決定するために、先行状態から前記入力状態に到着する遷移を表す到着タプルの各々を分析し、
前記所与の到着遷移が前記プッシュ動作を含む場合、前記先行状態から前記出力状態への遷移を表す拡張到着タプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記所与の到着遷移が前記プッシュ動作を含まない場合、前記所与のタプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記入力状態から更なる状態への遷移を表す第１の所与の拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するために、前記出力状態から前記更なる状態へ出発する遷移を表す出発タプルの各々を分析し、否の場合、前記第１の所与の拡張出発タプルを前記プッシュダウンオートマトンに追加し、
前記遷移動作が前記プッシュ動作を含むタプルの各々について、
第２の所与の出発タプルの所与の出発遷移動作が前記ポップ動作を含むか否かを決定するために、前記出発タプルの各々を分析し、
前記第２の所与の出発遷移動作が前記ポップ動作を含む場合、前記入力状態から更なる状態への遷移を表す第２拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定し、前記プッシュダウンオートマトンに含まれない場合、前記第２拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
を有する、請求項１４に記載のコンピュータ可読媒体。
【請求項１６】
システムであって、
第１ネットワーク装置であって、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す第１転送ルールを格納する第１記憶装置を含む、第１ネットワーク装置と、
ネットワークを介して前記第１ネットワーク装置と通信する第２ネットワーク装置であって、前記第２ネットワーク装置は、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す第２転送ルールを格納する第２記憶装置を含む、第２ネットワーク装置と、
制御装置であって、
１又は複数のプロセッサと、
命令を含む１又は複数の非一時的コンピュータ可読媒体であって、前記命令は、前記１又は複数のプロセッサにより実行されることに応答して、前記制御装置に工程を実行させ、前記工程は、
検証すべき前記ネットワークの１又は複数の特性を得るステップと、
前記第１転送ルール及び前記第２転送ルールを得るステップと、
前記第１転送ルール及び前記第２転送ルールに基づき、プッシュダウンオートマトンを生成するステップと、
前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、
を含む、非一時的コンピュータ可読媒体と、
を有する制御装置と、
を有するシステム。
【請求項１７】
前記第１ネットワーク装置及び前記第２ネットワーク装置は、カプセル化動作及びカプセル化解除動作のうちの少なくとも１つを前記パケットに対して実行するよう構成される、請求項１６に記載のシステム。
【請求項１８】
前記第１ネットワーク装置及び前記第２ネットワーク装置は、ＭＰＬＳ（multiprotocol  label  switching）を用いて動作するよう構成される、請求項１６に記載のシステム。
【請求項１９】
前記プッシュダウンオートマトンを生成するステップは、
各ネットワーク装置を前記プッシュダウンオートマトンの中の状態として表すステップと、
前記第１転送ルール及び前記第２転送ルールのうちの各転送ルールを、カプセル化動作に対応するプッシュ動作及びカプセル化解除動作に対応するポップ動作のうちの１つとして符号化するステップと、
前記プッシュ動作及び前記ポップ動作を、前記状態の間の遷移として使用するステップと、
を有する、請求項１６に記載のシステム。
【請求項２０】
前記飽和に基づくアルゴリズムを適用するステップは、
前記ネットワークの中のネットワーク装置の間の各接続を、入力状態、出力状態、及び前記入力状態から前記出力状態への遷移動作を有するタプルとして表すステップであって、前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１又は複数を含む、ステップと、
各タプルについて、前記遷移動作が前記プッシュ動作を含むか否かを決定するステップであって、
前記遷移動作が前記プッシュ動作を含まないタプルの各々について、
所与の到着タプルの所与の到着遷移動作が前記プッシュ動作を含むか否かを決定するために、先行状態から前記入力状態に到着する遷移を表す到着タプルの各々を分析し、
前記所与の到着遷移が前記プッシュ動作を含む場合、前記先行状態から前記出力状態への遷移を表す拡張到着タプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記所与の到着遷移が前記プッシュ動作を含まない場合、前記所与のタプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記入力状態から更なる状態への遷移を表す第１の所与の拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するために、前記出力状態から前記更なる状態へ出発する遷移を表す出発タプルの各々を分析し、否の場合、前記第１の所与の拡張出発タプルを前記プッシュダウンオートマトンに追加し、
前記遷移動作が前記プッシュ動作を含むタプルの各々について、
第２の所与の出発タプルの所与の出発遷移動作が前記ポップ動作を含むか否かを決定するために、前記出発タプルの各々を分析し、
前記第２の所与の出発遷移動作が前記ポップ動作を含む場合、前記入力状態から更なる状態への遷移を表す第２拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定し、前記プッシュダウンオートマトンに含まれない場合、前記第２拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
を有する、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示で議論される実施形態は、ネットワーク特性検証に関する。
【背景技術】
【０００２】
コンピュータネットワークの急増に伴い、このようなコンピュータネットワークに関連する様々な異なるプロトコルも出現している。例えば、幾つかのネットワークは、通信するためにインターネットプロトコル（ＩＰ）を利用する。別の例として、幾つかのネットワークは、通信するためにＭＰＬＳ（multiprotocol  label  switching）を利用する。幾つかの例では、インターネット全域で約２５％の経路が、ＭＰＬＳネットワークの少なくとも何らかの部分を横断する。
【０００３】
本開示で請求される主題は、上述のような欠点を解決する実施形態や上述のような環境でのみ機能する実施形態に限定されない。むしろ、この背景技術は、単に、本開示に記載される複数の実施形態が実施される技術分野の一例を説明するために提供される。
【発明の概要】
【０００４】
本開示の１又は複数の実施形態は、ネットワーク特性検証方法を含み得る。方法は、検証すべきネットワークの１又は複数の特性を取得するステップと、ネットワークの中の第１ネットワーク装置のための第１転送ルールを取得するステップと、を有して良い。第１転送ルールは、第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示して良い。方法は、ネットワーク内の第２ネットワーク装置のための第２転送ルールを取得するステップを更に有して良い。第２転送ルールは、第２ネットワーク装置が入力パケットをどのように扱うかを示して良い。方法は、第１及び第２転送ルールに基づきプッシュダウンオートマトンを生成するステップと、ネットワークの１又は複数の特性を検証するためにプッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、を更に有して良い。
【０００５】
実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。
【０００６】
上述の全体的説明及び以下の詳細な説明の両方は、単なる例示及び説明のためであり、本発明の範囲を限定しないことが理解される。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
【図１】ネットワーク特性検証に関連する例示的な環境を示す。
【図２】ネットワーク特性検証の例示的な方法のフローチャートを示す。
【図３】ネットワーク特性検証の別の例示的な方法のフローチャートを示す。
【図４Ａ】ネットワーク特性の検証を実現するために、飽和に基づくアルゴリズムを適用する例示的な方法のフローチャートを示す。
【図４Ｂ】ネットワーク特性の検証を実現するために、飽和に基づくアルゴリズムを適用する例示的な方法のフローチャートを示す。
【図４Ｃ】ネットワーク特性の検証を実現するために、飽和に基づくアルゴリズムを適用する例示的な方法のフローチャートを示す。
【図５】例示的なコンピューティングシステムを示す。
【発明を実施するための形態】
【０００８】
本開示の幾つかの実施形態は、ＭＰＬＳ（multiprotocol  label  switching）ネットワークを横断するパケットについてのネットワーク経路検証を含むネットワーク特性検証に関連する。ＭＰＬＳネットワークの一例は、カプセル化及びカプセル化解除技術を用いて、ＭＰＬＳネットワークを通じてパケットをトンネリングさせるネットワークである。このようなトンネルの一例は、ＭＰＬＳネットワークのエッジにあるエッジネットワーク装置に到着するＩＰパケットを含んで良い。エッジネットワーク装置は、一方で、カプセル化パケットがＭＰＬＳネットワークを通じてどこへルーティングされるべきかに関する命令として機能するヘッダの部分として、ラベルシリーズを有するＩＰパケットをカプセル化して良い。ラベルは、パケットに含まれるデータ、パケットが向けられるＩＰアドレス、又はパケットに関連する任意の他の情報に基づき選択されて良い。カプセル化パケットがＭＰＬＳネットワークを横断するとき、ＭＰＬＳネットワークの中の各ネットワーク装置は、標準的に、該ネットワーク装置がパケットをどのように転送するかを決定するために、外部ラベルを読み取る。追加で、ＭＰＬＳネットワークの中のネットワーク装置のうちの１又は複数は、１又は複数の追加ラベルでパケットを更にカプセル化し、１又は複数のラベルをカプセル化解除し、又はヘッダの変更無しにパケットを転送するための命令を有して良い。パケットがＭＰＬＳネットワークの遠端にあるエッジルータに到着するとき、エッジルータは、ＭＰＬＳネットワークの外へパケットをルーティングするための転送ルールを有して良い。したがって、トンネルを通じてＭＰＬＳネットワークを横断するパケットは、パケットがカプセル化されているラベルの数に依存して、可変長のヘッダを有して良い。
【０００９】
ＭＰＬＳネットワークの中のパケットヘッダの可変特性のために、ＭＰＬＳネットワークを通じるネットワーク経路の分析及び検証は、非ＭＰＬＳネットワークを通じるネットワーク経路の分析及び検証と比べて、より複雑且つ困難である。例えば、非ＭＰＬＳネットワーク分析は、パケットが向けられるＩＰアドレスに基づいて良い。別の例として、ＭＰＬＳネットワーク分析又は検証技術は、固定ヘッダサイズ又はヘッダサイズのキャップに依存して良く、不定ヘッダサイズを有するパケットを扱うことができない場合がある。このように、ＩＰアドレス及び／又は特定の若しくはキャップ付きヘッダサイズに基づく分析及び／又は検証は、より大きなヘッダ又は不定サイズのヘッダを使用する場合のあるＭＰＬＳネットワークの機能及び可能な範囲を制限することがある。本開示の幾つかの実施形態は、可変ヘッダ長のパケットを検証し及び／又は分析でき、任意の数のラベルが使用でき、任意のサイズのＭＰＬＳネットワークが使用できるようにするソリューションを提供する。さらに、本開示の幾つかの実施形態は、不定ヘッダサイズ及びキャップ無しヘッダサイズのパケットを検証し及び／又は分析できる。したがって、本開示の幾つかの実施形態は、コンピュータ及びネットワークの機能を向上するソリューションを提供し、さらにネットワーク検証の分野に向上をもたらす。
【００１０】
幾つかの実施形態では、ネットワーク特性を検証するために、制御装置は、ＭＰＬＳネットワークの中のネットワーク装置のための転送ルールを得て良い。制御装置は、転送ルールを使用して、ネットワークを表すためにプッシュダウンオートマトンを生成して良い。例えば、ＭＰＬＳネットワークの中の各ネットワーク装置は状態として表すことができ、状態間の遷移は（別のラベルを有するパケットのカプセル化に対応する）プッシュ動作、（ラベルを除去するためのパケットのカプセル化解除に対応する）ポップ動作、又はプッシュ及び／又はポップ動作の１又は複数の何らかの組み合わせとして表すことができる。プッシュダウンオートマトンは、ネットワークの１又は複数の特性を検証するために使用されて良い。例えば、ある状態と別の状態との間の経路が検証されて良い。これは、あるネットワーク装置と別のネットワーク装置との間の経路又はトンネルの検証に対応して良い。別の例として、経路に沿ってパケットにより取られるホップの数が検証されて良い。これは、どれ位速くパケットがＭＰＬＳネットワークを横断し得るかを決定するのに役立つ場合がある。
【００１１】
幾つかの実施形態では、本開示の幾つかの実施形態において記載されるようなネットワーク特性検証は、到達可能性問題として解決されて良い。上述及び他の実施形態において、到達可能性問題は、飽和に基づくアルゴリズムをプッシュダウンオートマトンに適用することにより解決されて良い。例えば、到達可能性問題は、ダイク（Dyck）文脈自由言語（context  free  language：ＣＦＬ）到達可能性問題に類似し得る。上述及び他の実施形態では、飽和に基づくアルゴリズムは、特性に関連する状態間の遷移が適正に探索されるまで、プッシュダウンオートマトンの中の種々の状態間の遷移を探索するタプルを生成することにより、プッシュダウンオートマトンの到達可能性空間を探索して良い。上述及び他の実施形態では、種々の遷移は、ネットワーク特性を検証するために期待経路又は期待性能と比較されて良い。このようなアプローチを用いて、パケットが１又は複数のトンネルに沿ってカプセル化され及びカプセル化解除されるときヘッダ長が変化し得るパケットについて、ネットワーク特性が検証できる。
【００１２】
本開示の実施形態を、添付の図面を参照して以下に説明する。
【００１３】
図１は、本開示の１又は複数の実施形態による、ネットワーク特性検証に関連する例示的な環境１００を示す。図１は、環境１００の中のネットワーク１２０を通じるパケット１５０（パケット１５０ａ〜１５０ｅとして参照される）の進行を更に示す。幾つかの実施形態では、環境１００は、ネットワーク１２０と通信する第１及び第２外部ネットワーク１１０ａ及び１１０ｂを含んで良い。環境１００は、ネットワーク１２０と通信する制御装置１３０を含んで良い。
【００１４】
第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、装置間で通信を送信し及び受信するよう構成される任意のネットワーク又はネットワークの構成を有して良い。幾つかの実施形態では、第１及び第２外部ネットワーク１１０ａ及び１１０ｂは、インターネットプロトコルスーツ（例えば、ＩＰ（internet  protocol）、ＴＣＰ（transmission  control  protocol）、ＵＤＰ（user  datagram  protocol）、ＩＣＭＰ（internet  control  message  protocol）、ＨＴＴＰ（hypertext  transfer  protocol）、ＰＯＰ（post  office  protocol）、等を含む）、Apple  Talk、ＩＰＸ／ＳＰＸ（internetwork  packet  exchange/sequenced  packet  exchange）、ＯＳＩ（Open  Systems  Interconnection）、ＳＮＡ（Systems  Network  Architecture）、ＤＥＣｎｅｔ、及び他のものを含む任意の数のプロトコルを使用して通信するよう構成されて良い。追加又は代替で、第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、複数のプロトコルにより、又は複ＭＰＬＳ（multiprotocol  label  switching）のような数のプロトコルに対応する方法で、動作して良い。幾つかの実施形態では、第１及び第２外部ネットワーク１１０ａ及び１１０ｂは、インターネットプロトコルスーツを用いて動作して良く、ネットワーク１２０はＭＰＬＳネットワークとして動作して良い。上述及び他の実施形態では、ネットワーク１２０の一部は、インターネットプロトコルスーツを用いて動作しても良い。
【００１５】
幾つかの実施形態では、第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、従来の種類のネットワーク、有線又は無線ネットワークとして実装されて良く、及び／又は多数の異なる構成を有して良い。さらに、第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、ＬＡＮ（local  area  network）、ＷＡＮ（wide  area  network）（例えば、インターネット）、又は複数の装置及び／又はエンティティが通信できる他の相互接続されたデータ経路を有して良い。幾つかの実施形態では、第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、ピアツーピアネットワークを有して良い。第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、種々の異なる通信プロトコルでデータを送信する通信ネットワークの一部に結合され又はそれを含んで良い。幾つかの実施形態では、第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、Ｂｌｕｅｔｏｏｔｈ（登録商標）通信ネットワーク、又はＳＭＳ（short  messaging  service）、ＭＭＳ（multimedia  messaging  service）、ＨＴＴＰ（hypertext  transfer  protocol）、直接データ接続、ＷＡＰ（wireless  application  protocol）、電子メール等を介することを含むデータを送信及び受信するセルラ通信ネットワーク、又は他のアプローチを有して良い。第１及び第２外部ネットワーク１１０ａ及び１１０ｂ、並びにネットワーク１２０は、第３世代（３Ｇ）、第４世代（４Ｇ）、ＬＴＥ（long−term  evolution）、ＬＴＥ−Ａ（long−term  evolution  advanced）、ＶｏＬＴＥ（Voice−over−LTE）、又は任意の他のモバイルデータネットワーク又はモバイルデータネットワークの組合せを含み得るモバイルデータネットワークを更に有して良い。
【００１６】
幾つかの実施形態では、ネットワーク１２０は、エッジネットワーク装置１２２ａ及び１２２ｂのような１又は複数のエッジネットワーク装置１２２を有して良い。さらに、ネットワーク１２０は、内部ネットワーク装置１２４ａ〜１２４ｂのような１又は複数の内部ネットワーク装置１２４を有して良い。用語「ネットワーク装置」は、エッジネットワーク装置、内部ネットワーク装置、及びネットワーク内の２つの（物理的又は論理的）地点の間のデータの転送を実現するよう構成される任意の他のコンピューティング装置を含んで良い。エッジネットワーク装置１２２は、ネットワーク１２０と第１外部ネットワーク１１０ａとの間の境界で動作するエッジネットワーク装置１２２ａのような、ネットワーク１２０と外部ネットワークとの間の境界で動作して良い。上述及び他の実施形態では、エッジネットワーク装置１２２及び内部ネットワーク装置１２４のうちの任意のものは、コンピューティング装置又は図５のコンピューティングシステム５００のようなコンピューティングシステムとして実装されて良い。例えば、このようなコンピューティング装置は、パケットの転送を通知するＭＰＬＳ型転送ルールを提供されて良い。このような転送ルールは、このようなコンピューティング装置から抽出されて良い。
【００１７】
幾つかの実施形態では、エッジネットワーク装置１２２、内部ネットワーク装置１２４、及び／又は外部ネットワーク１１０のうちの任意のものの間の破線は、同軸ケーブル、光ケーブル、より対線ケーブル（カテゴリ５ケーブルのような）、等のような、ネットワーク装置間の物理的接続を表し得る。追加又は代替で、破線は、ネットワーク装置間の論理接続を示して良い。例えば、破線が１より多くの接続又は媒体を表す場合でも、制御装置１３０及び／又はネットワーク処理ソフトウェアは、２つのネットワーク装置間の物理的接続に匹敵する又は類似するとして破線を取り扱って良い。外部ネットワーク１１０からネットワーク１２０に入る破線は、エッジネットワーク装置１２２に到着する１又は複数の物理接続を示して良い。実線矢印は、ネットワーク１２０を通過するとき、パケット１５０のフローを示す。
【００１８】
図示の容易さのため及び環境１００の動作を示すために、パケット１５０は、環境１００の下に示される。パケット１５０は、パケット１５０ａにより示されるように、ＩＰアドレス１７２．５４．３．１２８を宛先とするネットワーク１２０に到着して良い。パケットがネットワーク１２０を通じて進行するにつれ、パケット１５０ａ〜１５０ｅは、パケット１５０のヘッダがプッシュ及びポップ動作を通じてどのように変更され得るかを示す。
【００１９】
幾つかの実施形態では、パケット１５０ａは、第１外部ネットワーク装置１１０ａからエッジネットワーク装置１２２ａへルーティングされて良い。エッジネットワーク装置１２２ａは、ヘッダ内のラベルによりパケット１５０ａをカプセル化するようエッジネットワーク装置１２２ａに指示する転送ルールを有して良い。ヘッダ内のラベルは、パケット１５０ａがネットワーク１２０を通じて横断し得る経路を決定して良い。例えば、ネットワーク装置は、外側ラベル（ラベルスタックの中の最上位ラベルとしても知られる）を読み取り、ネットワーク装置の転送ルールの中で該ラベルを検索し、該ラベルに対応する転送ルールに基づきパケットをルーティングして良い。幾つかの実施形態では、所与のラベルは、パケット１５０ａをルーティングして良い内部ネットワーク装置１２４に対応して良い。例えば、図１に示すように、エッジネットワーク装置１２２ａは、ヘッダ内のラベルＡ、Ｂ、Ｃによりパケット１５０ａをカプセル化して良い。ヘッダのカプセル化は、パケット１５０ａのヘッダにラベルＡ、Ｂ、Ｃを追加するプッシュ動作として参照できる。ヘッダ内のラベルＡ、Ｂ、Ｃによるパケット１５０ａのカプセル化は、結果として、ネットワーク１２０を通じてルーティングされるパケット１５０ｂを生じ得る。幾つかの実施形態では、ラベルＡ、Ｂ、Ｃは、ネットワーク装置により読み取り可能な２０ビット値を表して良い。プッシュ動作に加えて、エッジネットワーク装置１２２ａは、インターネットネットワーク装置１２４ａへパケット１５０ｂを転送するよう構成されて良い。
【００２０】
内部ネットワーク装置１２４ａは、パケット１５０ｂを受信して良く、最も外側のラベルＡを読み取って良い。内部ネットワーク装置１２４ａの転送ルールは、内部ネットワーク装置１２４ａに、ラベルＡを除去してパケット１５０ｃを生じることにより、ラベルＡに基づきパケット１５０ｂをカプセル化解除させて良い。上述及び他の実施形態では、ラベルを除去するためのパケットのカプセル化解除は、ラベルのＰＯＰ又はラベルのポッピングとして参照されて良い。追加又は代替で、内部ネットワーク装置１２４ａの転送ルールは、内部ネットワーク装置１２４ａに、パケット１５０ｃを内部ネットワーク装置１２４ｂにルーティングさせて良い。幾つかの実施形態では、内部ネットワーク装置１２４ａは、最も外側のラベルを読み取り、該ラベルを内部ネットワーク装置１２４ａの記憶媒体に格納された転送ルールと比較して良い。転送ルールの中のラベルを見付けた後に、内部ネットワーク装置１２４ａはラベルＡを除去するためのパケット１５０ｂのカプセル化解除、及びパケット１５０ｃの内部ネットワーク装置１２４ｂへのルーティングのような、転送ルールの中のラベルに関連付けられた１又は複数の動作を実行して良い。
【００２１】
同様の方法で、及び内部ネットワーク装置１２４ｂの転送ルールに基づき、内部ネットワーク装置１２４ｂは、ラベルＢを除去するためにパケット１５０ｃをカプセル化解除して（ＰＯＰ  Ｂ）、結果としてパケット１５０ｄを生じて良い。内部ネットワーク装置１２４ｄは、パケット１５０ｄを内部ネットワーク装置１２４ｄへルーティングして良い。同様の方法で、及び内部ネットワーク装置１２４ｄの転送ルールに基づき、内部ネットワーク装置１２４ｄは、ラベルＣを除去するためにパケット１５０ｄをカプセル化解除して（ＰＯＰ  Ｃ）、結果としてパケット１５０ｅを生じて良い。内部ネットワーク装置１２４ｄは、パケット１５０ｅを内部ネットワーク装置１２２ｂへルーティングして良い。エッジネットワーク装置１２２ｂは、パケット１５０ｅに関連付けられた情報に基づき、第２外部ネットワーク１１０ｂへパケット１５０ｅをルーティングするよう構成されて良い。例えば、エッジネットワーク装置１２２ｂは、パケット１５０ｅが向けられるＩＰアドレスに基づき、第２外部ネットワーク１１０ｂへパケット１５０ｅをルーティングするよう構成されて良い。
【００２２】
カプセル化解除動作（ＰＯＰ  Ａ、ＰＯＰ  Ｂ、ＰＯＰ  Ｃ）を実行するよう図示したが、幾つかの実施形態では、内部ネットワーク装置１２４はＰＯＰ動作のみを実行するよう構成されて良く、他の実施形態では、内部ネットワーク装置１２４は、いかなる動作、ＰＵＳＨ動作、ＰＯＰ動作、又はそれらの任意の組合せも実行しないよう構成されて良い。幾つかの実施形態では、実行される動作は、内部ネットワーク装置の転送ルールにより決定されて良い。
【００２３】
幾つかの実施形態では、制御装置１３０は、ネットワーク１２０の物理レイアウト及び／又はネットワーク１２０のネットワーク装置の転送ルールを得るよう構成されて良い。追加又は代替で、制御装置１３０は、所与の時点におけるネットワークのデータプレーンのレイアウトを得るよう構成されて良い。データプレーンは、パケットがネットワークを通じてどのようにルーティングされるか、例えば、ネットワークの物理レイアウトとネットワーク内の装置が転送ルールに基づき装置の間でどのようにパケットをルーティングするかの組合せ、を表して良い。例えば、制御装置１３０は、エッジネットワーク装置１２２及び内部ネットワーク装置１２４の各々の転送ルール、及びエッジネットワーク装置１２２と内部ネットワーク装置１２４との間の物理接続を得て良い。幾つかの実施形態では、制御装置は、エッジネットワーク装置１２２及び内部ネットワーク装置１２４の各々と通信して良い。追加又は代替で、制御装置は、ネットワーク１２０の物理レイアウト及び／又は転送ルールを監視する別の電子装置と通信して良い。上述及び他の実施形態では、制御装置は、コンピューティング装置又は図５のコンピューティングシステムのようなコンピューティングシステムとして実装されて良い。
【００２４】
幾つかの実施形態では、制御装置１３０は、ネットワーク１２０の１又は複数の特性を検証するよう構成されて良い。特性は、特に、ネットワーク経路、ネットワーク到達可能性、パケットが期待受信者へ配信されるために横断し得るホップ数によるネットワーク内の地点間で測定された距離、ネットワークリンクの距離及び能力の関数としてのネットワーク内の２地点間のパケット伝搬時間の形式、ネットワークサービス時間、を含んで良い。例えば、制御装置１３０は、パケットが制御装置１３０により期待されるようにネットワーク１２０と通じて横断すること、又はパケットが期待されるように速くネットワーク１２０を通じて横断すること、を検証するよう構成されて良い。例えば、ネットワーク１２０の管理者は、特定のイングレス及びイグレスが利用可能であること、特定のネットワーク経路を辿ること、又は特定のネットワークパケット伝搬時間が閾の範囲内であること、を期待して良い。幾つかの実施形態では、特性は、管理者により設定されるメトリックであって良い。上述及び他の実施形態では、特性は、ネットワーク内の１又は複数の装置の転送ルールに基づいて良い。他の特性は、ネットワーク内のループを検出すること、及びネットワーク装置からパケットが決して転送され得ない該ネットワーク装置を識別すること、を含んで良い。
【００２５】
幾つかの実施形態では、制御装置１３０は、ネットワークを表すプッシュダウンオートマトンを生成することにより及びプッシュダウンオートマトンに飽和に基づくアルゴリズムを適用することにより、ネットワーク１２０の１又は複数の特性を検証して良い。プッシュダウンオートマトンは、先入れ先出しスタックを有して良い。例えば、要素Ａ、Ｂ、Ｃをその順序で追加されて有するプッシュダウンオートマトンは、要素Ａ、Ｂ、Ｃのスタックを含んで良く、要素Ｃのみにアクセス可能である。要素Ｃが除去された後、要素Ｂがアクセス可能になって良く、要素Ｂが除去された後、要素Ａがアクセス可能になって良い。
【００２６】
例えば、制御装置１３０は、２つの外部ネットワーク装置１２２ａ及び１２２ｂからの経路のような、検証すべき特性を得て良い。プッシュダウンオートマトン表現を用いて、制御装置１３０は、ネットワーク内の到達可能性空間及び遷移を探索するために、飽和に基づくアルゴリズムを適用して良い。制御装置１３０が飽和に基づくアルゴリズムを使用してプッシュダウンオートマトンを探索するとき、制御装置１３０は、アルゴリズムの代表遷移を期待遷移又は目的地と比較して良い。例えば、制御装置１３０は、エッジネットワーク装置１２２ａに到着するＩＰアドレス１７２．５４．３．１２８を有するパケット１５０ａがエッジネットワーク装置１２２ｂへルーティングされ得ることを期待し得る。プッシュダウンオートマトンの到達可能性空間を探索する飽和に基づくアルゴリズムの適用に基づき、パケット１５０ａがネットワーク１２０を通じてエッジネットワーク装置１２２ａからエッジネットワーク装置１２２ｂへルーティングされる経路が検証できる。別の例として、制御装置１３０は、このようなパケットが内部ネットワーク装置１２４ｃを含む経路に沿って横断することを期待できる。しかしながら、飽和に基づくアルゴリズムをプッシュダウンオートマトンに適用することにより、経路が１２４ｃではなく１２４ｂを含むことが示されることがある。上述及び他の実施形態では、このような結果は、ネットワークの動作が期待される挙動の範囲外であることを示すエラーをトリガして良い。
【００２７】
幾つかの実施形態では、制御装置１３０は、ネットワーク１２０の表現をプッシュダウンオートマトンとして生成することにより、ネットワーク１２０の１又は複数の特性を検証して良い。例えば、制御装置１３０は、エッジネットワーク装置１２２及び内部ネットワーク装置１２４の各々をプッシュダウンオートマトンの中の状態として表現することにより、及び状態間の遷移を１又は複数のプッシュ動作又はポップ動作として表現することにより、プッシュダウンオートマトンを生成して良い。制御装置１３０は、エッジネットワーク装置１２２及び内部ネットワーク装置１２４の転送ルールに基づき、このようなプッシュダウンオートマトンを生成して良い。例えば、エッジネットワーク装置１２２ａに対応する第１状態から、エッジネットワーク装置１２２ｂに対応する第２状態へ、遷移は、ＰＵＳＨ  Ａ  Ｂ  Ｃ、ＰＯＰ  Ａ、ＰＯＰ  Ｂ、ＰＯＰ  Ｃの動作を有して良い。別の例として、内部ネットワーク装置１２４ｂに対応する第３状態から、内部ネットワーク装置１２４ｄに対応する第４状態へ、遷移は、動作ＰＯＰ  Ｂを有して良い。
【００２８】
幾つかの実施形態では、制御装置１３０は、ネットワーク１２０の期待される挙動を、プッシュダウンオートマトンへの飽和に基づくアルゴリズムの適用により示される挙動と比較することにより、ネットワーク１２０の１又は複数の特性を検証して良い。飽和に基づくアルゴリズムは、知られている境界を有するより小さなローカル問題を解くことにより、大きな複雑な問題を解決するアルゴリズムを有して良く、境界を検証する他のより小さな問題を解くために反復的に進行して良い。例えば、あるネットワーク装置から別のネットワーク装置への遷移は、プッシュダウンオートマトンにより表現される小さな問題（例えば、あるネットワーク装置から次のネットワーク装置への遷移）で開始して良く、既に解決した遷移による開始を複数のネットワーク装置に渡る遷移にまで拡張して良い。これらの経路が探索されるとき、ネットワーク１２０が実際にどのように動作しているかのこれらの探索経路は、制御装置１３０の探索経路と比較されて良い。
【００２９】
例えば、ネットワーク１２０の管理者は、管理者がネットワークを最初にどのように構成するかに基づき、制御装置１３０にパケットの期待経路を入力して良い。時間に渡り、フェイルオーバシナリオ、負荷平衡、等により、ネットワーク経路のうちの１又は複数は変更されていて良い。上述及び他の実施形態では、制御装置１３０は、パケットが期待経路に沿って横断することを期待し得るが、プッシュダウンオートマトンは、ネットワーク１２０が期待通りに動作しない可能性のあることを示す異なる経路に対応して良い。このような異なる経路は、パケットを誤った位置にルーティングさせる場合があり、パケットに期待されるよりネットワーク１２０を横断する長い時間を取らせる場合があり、又は誤ってルーティングされるパケットに関連する任意の他の問題を生じさせる。別の例として、管理者は、ネットワークの元の構成に基づき、パケットがネットワーク１２０を横断するための特定時間量を要することを期待し得る。ネットワークへの同様の変更に基づき、パケットは、飽和に基づくアルゴリズムの適用により識別される、より遠回りのルートを取って良く、パケットがネットワーク１２０を通じる期待横断時間を超える横断時間を有し得ることの指示を生じる。
【００３０】
幾つかの実施形態では、検証される全ての特性に基づき、制御装置は、ネットワーク１２０が期待通りに挙動していることを示すメッセージを生成して良い。幾つかの実施形態では、１又は複数の特性が検証されないことに基づき、制御装置１３０は、検証の欠如を通知し及び／又は解決するために、１又は複数の措置を取って良い。幾つかの実施形態では、制御装置１３０は、ネットワーク１２０の１又は複数のネットワーク装置にネットワーク装置の転送ルールを変更させ又は更新させるためのメッセージを生成して良い。別の例として、制御装置１３０は、ネットワーク１２０の１又は複数のネットワーク装置に、１又は複数の物理通信チャネルを有効又は無効にさせて良い。追加の例として、制御装置１３０は、ネットワーク１２０の１又は複数のネットワーク装置に、電源断、電源入り、又はその他の場合にネットワーク装置の動作モードを調整させて良い。上述及び他の実施形態では、措置は、ネットワークの期待挙動により厳密に一致するよう、ネットワークの動作を変更するための改善措置であって良い。ネットワーク内の観測される変化が、（例えば、ネットワーク内の障害ではなく）ネットワークの誤った手動若しくは自動再構成に起因する場合、制御装置は、ネットワークの期待挙動を保つために、ネットワークのトリガされた変化を無視し、（ネットワークオペレータへの適切な警告メッセージを伴い）遅らせ、又は破棄して良い。
【００３１】
幾つかの実施形態では、制御装置１３０は、ネットワーク１２０の１又は複数の特性の検証において、飽和に基づくアルゴリズムを利用して良い。このような飽和に基づくアルゴリズムのプッシュダウンオートマトンへの適用の一例は、図４Ａ〜４Ｃを参照して説明できる。
【００３２】
幾つかの実施形態では、制御装置１３０は、ネットワーク１２０を通じる１又は複数の経路の視覚化を生成して良い。追加又は代替で、制御装置１３０は、ネットワーク１２０を通じる期待経路と比較される実際経路の視覚化を含んで良い。幾つかの実施形態では、制御装置１３０は、ディスプレイに、ネットワーク１２０の管理者に視覚化を提示させて良い。このようなディスプレイは、制御装置１３０に視覚化を表示させることを含んで良く、又は制御装置１３０が管理者の電子装置へメッセージを送信して該電子装置に視覚化を表示させて良い。幾つかの実施形態では、視覚化は、グラフのような１又は複数のネットワーク経路のグラフ表現を含んで良い。追加又は代替で、視覚化は、検証される１又は複数の特性を示す１又は複数の表を含んで良い。幾つかの実施形態では、視覚化は、到達可能性グラフを示す、１又は複数の経路、ルート、イングレス−イグレス対、又は他のものを含んで良い。到達可能性グラフは、特定の特性が検証されるか否かを示して良い。
【００３３】
本開示の範囲から逸脱することなく環境１００に対し変更、追加又は省略が行われて良い。例えば、環境１００は、任意の方法で接続される任意の数のエッジネットワーク装置１２２及び内部ネットワーク装置１２４を含んで良い。多くの場合において、ネットワーク１２０は、図示されるより多くのネットワーク装置を含んで良い。追加又は代替で、環境１００は、１より多くの制御装置を含んで良い。追加又は代替で、ネットワーク１２０は、ネットワーク１２０内の任意の数の物理接続及び／又は論理接続を含んで良い。
【００３４】
図２は、本開示の１又は複数の実施形態による、ネットワーク特性検証の例示的な方法２００のフローチャートを示す。別個のブロックとして示したが、特定の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されて良い。
【００３５】
ブロック２１０で、検証されるべきネットワークの特性が取得されて良い。例えば、（図１の制御装置１３０のような）制御装置は、（図１のネットワーク１２０のような）検証されるべきネットワークの特性を取得して良い。幾つかの実施形態では、ユーザは、検証されるべき１又は複数の特性を指定するために制御装置と相互作用して良い。追加又は代替で、制御装置１３０は、ネットワークの１又は複数の特性を周期的に検証するよう構成されて良い。幾つかの実施形態では、ネットワーク障害又は（物理ネットワーク接続の再割り当てのような）ネットワーク再編成は、ネットワークの１又は複数の特性を検証するよう制御装置をトリガして良い。幾つかの実施形態では、制御装置は、ネットワークの期待挙動としてネットワークの特性を維持して良い。幾つかの実施形態では、ネットワークは、ＭＰＬＳネットワークを含んで良い。
【００３６】
ブロック２２０で、ネットワーク内のネットワーク装置のための転送ルールが取得されて良い。例えば、制御装置は、ブロック２１０で取得された特性に関連する、（図１のエッジネットワーク装置１２２のような）エッジネットワーク装置及び／又は（図１の内部ネットワーク装置のような）内部ネットワーク装置のための転送ルールを取得して良い。例えば、検証されるべき特性がネットワーク全体に渡る経路を含む場合、ネットワークの全てのネットワーク装置のための全ての転送ルールが、制御装置により取得されて良い。別の例として、検証されるべき特性が１つの特定の経路又は（新しい物理接続を使用する経路のような）１つの特定の経路の性能に関連する場合、特定の経路の中で使用されるネットワーク装置の転送ルールだけが取得されて良い。幾つかの実施形態では、制御装置は、１又は複数のネットワーク装置に格納された転送ルールを読み出し及び転送ルールと共に制御装置へメッセージを返すよう、ネットワーク装置に指示するために、１又は複数のネットワーク装置へメッセージを送信して良い。
【００３７】
ブロック２３０で、プッシュダウンオートマトンは、転送ルールに基づき生成されて良い。例えば、制御装置は、ネットワーク装置の転送ルールを利用して、ネットワークを表すためにプッシュダウンオートマトンを生成して良い。幾つかの実施形態では、プッシュダウンオートマトンの生成は、検証されるべき特性に関連する各ネットワーク装置（幾つかの実施形態では、ネットワーク内の全てのネットワーク装置を含んで良い）を、プッシュダウンオートマトンの中の１又は複数の状態として表現することにより、達成できる。例えば、図１を参照すると、エッジネットワーク装置１２２ａは第１状態であって良く、内部ネットワーク装置１２４ａは第２状態であって良く、内部ネットワーク装置１２４ｂは第３状態であって良い。追加又は代替で、プッシュダウンオートマトンを生成する際に、転送ルールは、プッシュダウンオートマトンのプッシュ動作又はポップ動作として符号化されて良い。例えば、第１状態から第２状態への遷移では、遷移は、ＰＵＳＨ  Ａ、ＰＵＳＨ  Ｂ、ＰＵＳＨ  Ｃとして符号化されて良い。別の例として、第２状態から第３状態への遷移は、ＰＯＰ  Ａとして符号化されて良い。
【００３８】
ブロック２４０で、飽和に基づくアルゴリズムは、ネットワークの特性を検証するためにプッシュダウンオートマトンに適用されて良い。例えば、制御装置は、プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用して良く、アルゴリズムを適用する際に、アルゴリズムの中の１又は複数のステップにおいて、制御装置が特性をプッシュダウンオートマトンの特徴と比較できるようにして良い。幾つかの実施形態では、飽和に基づくアルゴリズムは、ネットワーク内の複数ホップに渡る遷移を表す１又は複数の動作を検証するために、ネットワークの到達可能性空間を探索して良い。例えば、プッシュダウンオートマトンの中の単一の遷移から始めて、飽和に基づくアルゴリズムは、遷移の境界を、ネットワーク内の先の及び／又は後のネットワーク装置に対応する状態に更に更に拡張して良い。ブロック２３０の例に従い、第１状態から第３状態への遷移は、飽和に基づくアルゴリズムの適用により、ＰＵＳＨ  Ａ、ＰＵＳＨ  Ｂ、ＰＵＳＨ  Ｃ、ＰＯＰ  Ａとして符号化されて良い。空間を探索する際に、あるネットワーク装置から別のネットワーク装置への到達可能性は、空間が探索されるにつれ検証されて良い。例えば、制御装置が図１のエッジネットワーク装置１２２ａからエッジネットワーク装置１２２ｂへのパケットの到達可能性クエリを実行していた場合、制御装置は、２つのネットワーク装置からの遷移がＰＵＳＨ  Ａ、ＰＵＳＨ  Ｂ、ＰＵＳＨ  Ｃ、ＰＯＰ  Ａ、ＰＯＰ  Ｂ、ＰＯＰ  Ｃとして決定できるまで、到達可能性空間を探索して良い。このような飽和に基づくアルゴリズムの適用の一例は、図４Ａ〜４Ｃを参照して説明できる。
【００３９】
当業者は、上述の処理、動作、及び方法について、実行される機能及び／又は工程が異なる順序で実施されて良いことを理解するだろう。さらに、概略の機能及び動作は、単に例として提供され、幾つかの機能及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ない機能及び動作に組み合わされ、又は追加機能及び動作に拡張されても良い。例えば、幾つかの実施形態は、ダイク文脈自由言語の到達可能性を調べる実装及び最適化技術を含んで良い。
【００４０】
図３は、本開示の１又は複数の実施形態による、ネットワーク特性検証の別の例示的な方法３００のフローチャートを示す。別個のブロックとして示したが、特定の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されて良い。
【００４１】
ブロック３１０で、ネットワークの物理レイアウトが取得されて良い。例えば、（図１の制御装置１３０のような）制御装置は、（図１のネットワーク１２０のような）ネットワークの物理レイアウトの電子表現を維持して良く、物理接続又はネットワーク装置がネットワーク内で変更されると、制御装置が電子表現を調整できる。別の例として、制御装置は、別の装置又は複数の装置からネットワークの物理レイアウトのこのような電子表現を受信して良い。例えば、ネットワーク内の各ネットワーク装置は、ネットワーク装置及びネットワーク内の任意の関連接続を識別するメッセージを制御装置へ送信して良い。
【００４２】
ブロック３２０で、所与の時点のネットワークのデータプレーンのレイアウトが取得されて良い。例えば、制御装置は、図２のブロック２２０に関して説明したものと同様の方法で、（図１のエッジネットワーク装置１２２及び内部ネットワーク装置のような）ネットワーク装置の転送ルールを取得して良い。ネットワーク装置の物理レイアウト及び転送ルールを用いて、制御装置は、データプレーンのレイアウトを取得して良い。例えば、レイアウトは、パケットがネットワーク内のネットワーク装置の物理的接続及び転送ルールに基づき、ネットワークを通じて物理的にルーティングされる方法を表して良い。幾つかの実施形態では、制御装置はレイアウトを生成して良く、一方で、他の実施形態では、制御装置は、別の装置からレイアウトを提供されて良い。
【００４３】
ブロック３３０で、ネットワークの期待挙動を表す特性が取得されて良い。例えば、制御装置は、ネットワークを通じるパケットのルーティング、ネットワークを通じる横断時間、等のようなネットワークの期待性能を表す特性セットを維持して良い。幾つかの実施形態では、このような特性は、制御装置と相互作用することにより、ネットワーク管理者のようなユーザにより設定されて良い。幾つかの実施形態では、ブロック３３０は、図２のブロック２１０と類似し又はそれに匹敵して良い。
【００４４】
ブロック３４０で、ネットワーク内の各ネットワーク装置は、プッシュダウンオートマトンの中の１又は複数の状態として表現されて良い。例えば、ネットワークをプッシュダウンオートマトンとして表現する際に、制御装置は、各ネットワーク装置をプッシュダウンオートマトンの中の状態として表現して良い。幾つかの実施形態では、プッシュダウンオートマトンは、ネットワークの物理レイアウト及びネットワーク装置の転送ルールのうちの１又は複数を含む、データプレーンのレイアウトに基づき生成される。
【００４５】
ブロック３５０で、ネットワーク内のネットワーク装置間のネットワーク内の各ホップは、それぞれパケットのカプセル化又はカプセル化解除に対応する、状態間の遷移としての１又は複数のプッシュ又はポップ動作として符号化されて良い。例えば、制御装置は、第２ネットワーク装置への第１ネットワーク装置の転送ルールを読み出し、第１ネットワーク装置から第２ネットワーク装置への転送ルールに基づき、第１ネットワーク装置から第２ネットワーク装置への遷移を、プッシュダウンオートマトンの中の１又は複数のプッシュ又はポップ動作として符号化して良い。
【００４６】
ブロック３６０で、飽和に基づくアルゴリズムは、ネットワークの特性のうちの１又は複数を検証するためにプッシュダウンオートマトンに適用されて良い。例えば、制御装置は、ブロック３３０で取得された特性を検証するために、プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用して良い。幾つかの実施形態では、ブロック３６０は、図２のブロック２４０と類似し又はそれに匹敵して良い。
【００４７】
当業者は、上述の処理、動作、及び方法について、実行される機能及び／又は工程が異なる順序で実施されて良いことを理解するだろう。さらに、概略の機能及び動作は、単に例として提供され、幾つかの機能及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ない機能及び動作に組み合わされ、又は追加機能及び動作に拡張されても良い。
【００４８】
図４Ａ〜４Ｃは、本開示の１又は複数の実施形態による、ネットワーク特性の検証を実現するために、飽和に基づくアルゴリズムを適用する例示的な方法４００のフローチャートを示す。例えば、方法４００は、プッシュダウンオートマトンにより表現されたネットワークの１又は複数の特性が検証できるように、飽和に基づくアルゴリズムをプッシュダウンオートマトンに適用する種々の側面を示し得る。別個のブロックとして示したが、特定の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されて良い。
【００４９】
図４Ａ〜４Ｃを参照すると、ネットワーク装置は状態として表現でき、遷移動作は、ネットワーク装置間でパケットをルーティングする際にネットワークにより利用される転送ルールを表現して良い。
【００５０】
ブロック４０２で、タプルのセット（例えば、トリプル）が初期化され、セットＷとして参照される。例えば、（図１の制御装置１３０のような）制御装置は、飽和に基づくアルゴリズムの部分として、タプルセットを初期化して良い。タプルは、＜ｉ，ｊ，ｔ＞の形式を取って良い。ここで、ｉは入力状態を表し、ｊは出力状態を表し、ｔは入力状態と出力状態との間の遷移動作を表して良い。幾つかの実施形態では、タプルの中の入力状態及び出力状態は、ネットワーク内のネットワーク装置の挙動を表すプッシュダウンオートマトンからの状態であって良い。上述及び他の実施形態では、遷移動作は、タプルの中の入力及び出力状態の間で生じるプッシュダウンオートマトンからの遷移であって良い。
【００５１】
遷移動作ｔは、「ｐｕｓｈｌａｂｅｌ」又は「ｐｏｐｌａｂｅｌ」動作、又は遷移の特別な形式「Ｔｌａｂｅｌ」又は「Ｓ」を含んで良い。プッシュダウンオートマトンにより受け入れられる言語は、ダイク（Dyck）文脈自由言語の形式である。これは、ＭＰＬＳ−ＣＦＬとして参照される場合がある。数学的に記述すると、ＭＰＬＳ−ＣＦＬは以下のように定義できる。
【数１】
2018117336.tif 000003
【００５２】
例として、図１のエッジネットワーク装置１２２ａに対応する第１状態、及び内部ネットワーク装置１２４ａに対応する第２状態を参照すると、ＰＵＳＨ  Ａ、ＰＵＳＨ  Ｂ、ＰＵＳＨ  Ｃの遷移動作により、タプルは、ｉを第１状態（内部ネットワーク装置１２４ａに対応する入力状態）として、ｊを第２状態（内部ネットワーク装置１２４ａに対応する出力状態）として含んで良い。ｉは、動作シーケンス、つまりｐｕｓｈＡ、ｐｕｓｈＢ、ｐｕｈｓＣを実行するので、予備状態ｘ及びｙが導入されて良い。プッシュダウンオートマトンは、タプル＜ｉ，ｘ，ｐｕｓｈＡ＞、＜ｘ，ｙ，ｐｕｓｈＢ＞、及び＜ｙ，ｊ，ｐｕｓｈＣ＞により表現できる４個の状態及び３個の遷移を含んで良い。
【００５３】
ブロック４０２を参照すると、初期化タプルセットは、タプル＜ｋ，ｋ，Ｓ＞も含んで良い。ここで、ｋは、（図２及び／又は３を参照して説明したように生成されるプッシュダウンオートマトンのような）プッシュダウンオートマトンの中の状態を表し、Ｓは、ある状態から同じ状態へ行く動作が存在しないような上述のように定義される特別なシンボルのうちの１つである。
【００５４】
ブロック４０４で、任意のタプルがタプルセットＷの中に残っているか否かが決定されて良い。方法４００の最初の通過で、方法４００が進行するにつれ探索され得る状態の各々についてタプルが存在し得る。分析されるべき残りのタプルが存在するという決定の後、方法４００はブロック４０６に進んで良い。分析されるべき残りのタプルが存在しないという決定の後、方法４００は完了して良い。
【００５５】
ブロック４０６で、分析されるためにタプルが選択されて良い。分析されるべきタプルは、タプルの分析における便宜上、タプル＜ｉ，ｊ，ｔ＞として参照されて良く、分析における対応する変数は、これらの変数によいｒ分析されるべきタプルを参照して良い。
【００５６】
ブロック４０８で、タプル＜ｉ，ｊ，ｔ＞はセットＷから除去されて良い。
【００５７】
ブロック４１０で、ｔが形式Ｔｌａｂｅｌであるか否か、又は状態ｉから状態ｊへの遷移の動作がプッシュ動作であるか、に関して決定されて良い。ｔが形式Ｔｌａｂｅｌであるという決定の後、方法４００はブロックＢに進んで良く、図４Ｃを参照して続いて良い。ｔが形式Ｔｌａｂｅｌではないという決定の後、方法４００はブロック４１２に進んで良い。
【００５８】
ブロック４１２で、ｔが形式Ｓであるか否か（例えば、状態ｉから状態ｊへの遷移の動作がラベルスタックを空にするかどうか）に関して決定されて良い。ｔが形式Ｓであるという決定の後、方法４００はブロックＡに進んで良く、図４Ｃを参照して続いて良い。ｔが形式Ｓであるという決定の後、方法４００はブロック４０４に戻って、分析されるべき残りのタプルが存在するかどうかを決定して良い。
【００５９】
図４Ｂを参照して、ブロックＡの続きとして、方法４００は、先行状態ｋからタプル＜ｉ，ｊ，ｔ＞に到着する遷移の、又はタプル＜ｉ，ｊ，ｔ＞からタプルの後の更なる状態ｋ’に進む遷移の、拡張空間を探索して良い。
【００６０】
ブロック４１４で、方法４００は、分析されるべき所与の＜ｋ，ｉ，ｔ’＞のフローに従って良い。例えば、タプル＜ｋ，ｉ，ｔ’＞は、先行状態ｋから入力状態ｉに到着するために、遷移動作ｔ’を表して良い。
【００６１】
ブロック４１６で、入力状態ｉに到着するために遷移ｔ’がプッシュ動作ｐｕｓｈｌａｂｌｅを含むか否かに関して決定されて良い。遷移動作ｔ’がｐｕｓｈｌａｂｌｅを含むという決定の後、方法４００はブロック４１８に進んで良い。遷移動作ｔ’がｐｕｓｈｌａｂｌｅを含まないという決定の後、方法４００はブロック４２２に進んで良い。
【００６２】
ブロック４１８で、拡張入力タプル＜ｋ，ｊ，Ｔｌａｂｅｌ＞がプッシュダウンオートマトンの中にあるか否かが決定されて良い。例えば、タプル＜ｋ，ｊ，Ｔｌａｂｅｌ＞は、分析されているタプルの先行状態ｋから出力状態ｊへの遷移を表して良い。ここで、ブロック４１６において入力状態ｉに到着するための遷移がプッシュ動作を含むと決定されたので、集合Ｓは特別形式Ｔｌａｂｅｌを取る。＜ｋ，ｊ，Ｔｌａｂｅｌ＞がプッシュダウンオートマトンの中にないという決定の後、方法４００はブロック４２０に進んで良い。＜ｋ，ｊ，Ｔｌａｂｅｌ＞がプッシュダウンオートマトンの中にあるという決定の後、方法４００はブロック４２８に進んで良い。幾つかの実施形態では、ブロック４１８は、（入力状態ｉより前の）先行状態ｋから出力状態ｊまでの拡張空間の探索を実現して良い。
【００６３】
ブロック４２０で、タプル＜ｋ，ｊ，Ｔｌａｂｅｌ＞は、プッシュダウンオートマトン及び分析されるべきタプルの集合Ｗに追加されて良い。
【００６４】
ブロック４２２で、ｔ’が形式Ｓであるか否かに関する決定が行われて良い。ブロック４２２は、ブロック４１２と同様であり又はそれに匹敵し得るが、ｔではなくｔ’を比較する。ｔ’が形式Ｓであるという決定の後、方法４００はブロック４２４に進んで良い。ｔ’が形式Ｓではないという決定の後、方法４００はブロック４２８に進んで良い。
【００６５】
ブロック４２４で、拡張入力タプル＜ｋ，ｊ，Ｓ＞がプッシュダウンオートマトンの中にあるか否かが決定されて良い。例えば、タプル＜ｋ，ｊ，Ｓ＞は、分析されているタプルの先行状態ｋから出力状態ｊへの遷移を表して良い。＜ｋ，ｊ，Ｓ＞がプッシュダウンオートマトンの中にないという決定の後、方法４００はブロック４２６に進んで良い。＜ｋ，ｊ，Ｓ＞がプッシュダウンオートマトンの中にあるという決定の後、方法４００はブロック４２８に進んで良い。幾つかの実施形態では、ブロック４２４は、（入力状態ｉより前の）先行状態ｋから出力状態ｊまでの拡張空間の探索を実現して良い。
【００６６】
ブロック４２６で、タプル＜ｋ，ｊ，Ｓ＞は、プッシュダウンオートマトン及び分析されるべきタプルの集合Ｗに追加されて良い。
【００６７】
ブロック４２８で、プッシュダウンオートマトンの中に、ブロック４１４〜４２６を通じて処理されていない形式＜ｋ，ｉ，ｔ’＞の更なるタプルが存在するか否かが決定されて良い。分析されるべき形式＜ｋ，ｉ，ｔ’＞の更なるタプルが存在するという決定の後、方法４００は、形式＜ｋ，ｉ，ｔ’＞の次のタプルを分析するためにブロック４１４に戻って良い。プッシュダウンオートマトンの中の形式＜ｋ，ｉ，ｔ’＞の全てのタプル（例えば、先行状態ｋから入力状態ｉまでの全ての遷移）が分析されたという決定の後、方法４００はブロック４３０へ進んで良い。
【００６８】
ブロック４３０で、方法４００は、分析されるべき所与の＜ｊ，ｋ’，Ｓ＞のフローに従って良い。例えば、タプル＜ｊ，ｋ’，Ｓ＞は、出力状態ｊから更なる状態ｋ’に進むために、遷移動作Ｓを表して良い。
【００６９】
ブロック４３２で、拡張出発タプル＜ｉ，ｋ’，Ｓ＞がプッシュダウンオートマトンの中にあるか否かが決定されて良い。例えば、タプル＜ｉ，ｋ’，Ｓ＞は、分析されているタプルの入力状態ｉから更なる状態ｋ’への遷移を表して良い。＜ｉ，ｋ’，Ｓ＞がプッシュダウンオートマトンの中にないという決定の後、方法４００はブロック４３４に進んで良い。＜ｉ，ｋ’，Ｓ＞がプッシュダウンオートマトンの中にあるという決定の後、方法４００はブロック４３６に進んで良い。幾つかの実施形態では、ブロック４３２は、入力状態ｉから出力状態ｊを超える状態ｋ’までの拡張出発空間の探索を実現して良い。
【００７０】
ブロック４３４で、タプル＜ｉ，ｋ’Ｓ＞は、プッシュダウンオートマトン及び分析されるべきタプルの集合Ｗに追加されて良い。
【００７１】
ブロック４３６で、プッシュダウンオートマトンの中に、ブロック４３０〜４３４を通じて処理されていない形式＜ｊ，ｋ’，Ｓ＞の更なるタプルが存在するか否かが決定されて良い。’分析されるべき形式＜ｊ，ｋ’，Ｓ＞の更なるタプルが存在するという決定の後、方法４００は、形式＜ｊ，ｋ’，Ｓ＞の次のタプルを分析するためにブロック４３０に戻って良い。プッシュダウンオートマトンの中の形式＜ｊ，ｋ’，Ｓ＞の全てのタプル（例えば、出力状態ｊから更なる状態ｋ’までの全ての遷移）が分析されたという決定の後、方法４００はブロックＣへ進んで良い。図４Ａに示すように、ブロックＣは、集合Ｗの中に未だ分析されていない残りのタプルが存在するかどうかを決定するために、ブロック４０４に戻って良い。
【００７２】
図４Ｃを参照して、図４ＡのブロックＢの続きとして、方法４００は、タプル＜ｉ，ｊ，ｔ＞に到着する及びタプルの後に更なる状態ｋに進む遷移の、拡張空間を探索して良い。例えば、ブロック４４２、４４４、４４６は、それぞれブロック４３２、４３４、４３６と同様であり又はそれに匹敵し得る。
【００７３】
ブロック４３８で、方法４００は、分析されるべき所与の＜ｊ，ｋ，ｔ’＞のフローに従って良い。例えば、タプル＜ｊ，ｋ，ｔ’＞は、出力状態ｊから更なる状態ｋ’に進むために、遷移動作ｔ’を表して良い。
【００７４】
ブロック４４０で、出力状態ｊから更なる状態ｋに遷移するための遷移ｔ’がポップ動作ｐｏｐｌａｂｌｅを含むか否かに関して決定されて良い。遷移動作ｔ’がｐｏｐｌａｂｌｅを含むという決定の後、方法４００はブロック４４２に進んで良い。遷移動作ｔ’がｐｏｐｌａｂｌｅを含まないという決定の後、方法４００はブロック４４６に進んで良い。
【００７５】
ブロック４４２で、拡張出発タプル＜ｉ，ｋ，Ｓ＞がプッシュダウンオートマトンの中にあるか否かが決定されて良い。例えば、タプル＜ｉ，ｋ，Ｓ＞は、分析されているタプルの入力状態ｉから更なる状態ｋへの遷移を表して良い。＜ｉ，ｋ，Ｓ＞がプッシュダウンオートマトンの中にないという決定の後、方法４００はブロック４４４に進んで良い。＜ｉ，ｋ，Ｓ＞がプッシュダウンオートマトンの中にあるという決定の後、方法４００はブロック４４６に進んで良い。幾つかの実施形態では、ブロック４４２は、入力状態ｉから出力状態ｊを超える状態ｋまでの拡張出発空間の探索を実現して良い。
【００７６】
ブロック４４４で、タプル＜ｉ，ｋ，Ｓ＞は、プッシュダウンオートマトン及び分析されるべきタプルの集合Ｗに追加されて良い。
【００７７】
ブロック４４６で、プッシュダウンオートマトンの中に、ブロック４４０〜４４４を通じて処理されていない形式＜ｊ，ｋ，ｔ’＞の更なるタプルが存在するか否かが決定されて良い。分析されるべき形式＜ｊ，ｋ，ｔ’＞の更なるタプルが存在するという決定の後、方法４００は、形式＜ｊ，ｋ，ｔ’＞の次のタプルを分析するためにブロック４３８に戻って良い。プッシュダウンオートマトンの中の形式＜ｊ，ｋ，ｔ’＞の全てのタプル（例えば、出力状態ｊから更なる状態ｋまでの全ての遷移）が分析されたという決定の後、方法４００はブロックＣへ進んで良い。図４Ａに示すように、ブロックＣは、集合Ｗの中に未だ分析されていない残りのタプルが存在するかどうかを決定するために、ブロック４０４に戻って良い。
【００７８】
幾つかの実施形態では、方法４００が利用されるとき、関心のある１又は複数の遷移は、ネットワークの特性を検証するために分析され及び／又は観測されて良い。例えば、期待ネットワーク経路及びネットワークの実際の動作が同じであることを確かめるために、ネットワーク経路のような期待特性は、期待経路に対応する、プッシュダウンオートマトンへの飽和に基づくアルゴリズムの適用の間に観察される遷移動作と比較されて良い。飽和に基づくアルゴリズムの適用中に、特性と観測との間の不一致が存在する場合、エラー又は他の警告が上げられて良い。追加又は代替で、予期せぬネットワーク経路に対応するタプルが、飽和に基づくアルゴリズムの適用中に観測され又は生成された場合、対応するエラー又は警告が上げられて良い。幾つかの実施形態では、制御装置は、どんなエラー又は期待挙動と観測挙動との間の不一致が生じたかを示すレポートを生成して良い。幾つかの実施形態では、飽和プッシュダウンオートマトンが生成されて良く、ネットワークの１又は複数の特性は、グラフアルゴリズムの適用又は飽和プッシュダウンオートマトンに適用される他の別個の到達可能性探求により検証されて良い。
【００７９】
図２、３、４Ａ〜４Ｃの方法２００、３００、又は４００のうちの任意のものは、任意の適切なシステム、機器、又は装置により実行されて良い。例えば、図１の環境１００、又は制御装置１３０のようなそのコンポーネントのうちの１又は複数は、方法２００、３００、及び／又は４００に関連する動作のうちの１又は複数を実行して良い。上述及び他の実施形態では、コンピュータ可読媒体に格納されるプログラム命令は、方法２００、３００、及び／又は４００の動作のうちの１又は複数を実行するために実行されて良い。本開示の範囲から逸脱することなく記載の方法２００、３００、及び／又は４００のうちの任意のものに対し変更、追加又は省略が行われて良い。例えば、方法２００、３００、及び／又は４００の工程は、異なる順序で実施されて良い。追加又は代替で、２以上の工程が同時に実行されて良い。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されて良い。
【００８０】
図５は、本開示に記載の少なくとも一実施形態による例示的なコンピューティングシステム５００を示す。システム５００は、ソフトウェアを試験するよう構成される任意の適切なシステム、機器、又は装置を有して良い。コンピューティングシステム５００は、プロセッサ５１０、メモリ５２０、データ記憶装置５３０、通信ユニット５４０を有して良く、これらは全て通信可能に結合されて良い。データ記憶装置５３０は、ＭＰＬＳネットワークで使用するための転送ルールのような種々のデータを有して良い。
【００８１】
概して、プロセッサ５１０は、任意の適切な特定用途向け又は汎用コンピュータ、コンピューティングエンティティ、又は種々のコンピュータハードウェア若しくはソフトウェアモジュールを有して良く、任意の適切なコンピュータ可読媒体に格納された命令を実行するよう構成され得る処理装置を用いて実施されて良い。例えば、プロセッサ５１０は、マイクロプロセッサ、マイクロコントローラ、デジタシグナルプロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（FPGA）又はプログラム命令を解釈し及び／若しくは実行し並びに／又はデータを処理するよう構成された任意の他のデジタル若しくはアナログ回路を有して良い。
【００８２】
図５には単一のプロセッサを示したが、プロセッサ５１０は、本開示に記載の任意の数の演算を個々に又は共同で実行するよう構成される任意の数のネットワーク又は物理的位置に渡り分散される任意の数のプロセッサを有して良いことが理解される。幾つかの実施形態では、プロセッサ５１０は、プログラム命令を解釈し及び／又は実行し、及び／又はメモリ５２０、データ記憶装置５３０又はメモリ５２０及びデータ記憶装置５３０に格納されたデータを処理して良い。幾つかの実施形態では、プロセッサ５１０は、データ記憶装置５３０からプログラム命令をフェッチし、該プログラム命令をメモリ５２０にロードして良い。
【００８３】
プログラム命令がメモリ５２０にロードされた後、プロセッサ５１０は、それぞれ図２、３、４Ａ〜４Ｃの方法２００、３００及び／又は４００を実行するための命令のようなプログラム命令を実行して良い。例えば、プロセッサ５１０は、ネットワーク内のネットワーク装置の転送ルールを取得して良く、該ネットワークを表すプッシュダウンオートマトンを転送ルールに基づき生成して良い。別の例として、プロセッサ５１０は、このようなプッシュダウンオートマトンに飽和に基づくアルゴリズムを適用して良い。
【００８４】
メモリ５２０及びデータ記憶装置５３０は、コンピュータ実行可能命令又はデータ構造を伝える又は格納しているコンピュータ可読記憶媒体又は１又は複数のコンピュータ可読記憶媒体を含み得る。このようなコンピュータ可読媒体は、プロセッサ５１０のような汎用又は特定目的コンピュータによりアクセスできる任意の利用可能な媒体であって良い。幾つかの実施形態では、コンピューティングシステム５００は、メモリ５２０及びデータ記憶装置５３０のいずれかを有して良く又は有しなくて良い。
【００８５】
例として且つ限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read−Only  Memory）、ＥＥＰＲＯＭ（Electrically  Erasable  Programmable  Read−Only  Memory）、ＣＤ−ＲＯＭ（Compact  Disc  Read−Only  Memory）又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置（例えば、固体メモリ素子）を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の記憶媒体を有し得る。上述の組合せも、コンピュータ可読記憶媒体の範囲に包含され得る。コンピュータ実行可能命令は、例えば、プロセッサ５１０に特定の工程又は工程のグループを実行させるよう構成される命令及びデータを含み得る。
【００８６】
通信ユニット５４０は、ネットワークを介して情報を送信し又は受信するよう構成される任意のコンポーネント、装置、システム、又はそれらの組合せを有して良い。幾つかの実施形態では、通信ユニット５４０は、他の場所、同じ場所にある他の装置と、又は同じシステムの中の他のコンポーネントとも通信して良い。例えば、通信ユニット５４０は、モデム、ネットワークカード（無線又は有線）、光通信装置、赤外信装置、（アンテナのような）無線通信装置、及び／又は（Ｂｌｕｅｔｏｏｔｈ（登録商標）装置、８０２．６装置（例えば、ＭＡＮ（Metropolitan  Area  Network））、ＷｉＦｉ装置、ＷｉＭａｘ装置、セルラ通信設備、等のような）チップセット、及び／又は同様のものを含み得る。通信ユニット５４０は、ネットワークと及び／又は本開示に記載された他の装置若しくはシステムとデータを交換することを可能にし得る。例えば、通信ユニット５４０は、システム５００が、ネットワーク装置、制御装置、及び／又は他のネットワークのような他のシステムと通信できるようにして良い。
【００８７】
本開示の範囲から逸脱することなくシステム５００に対し変更、追加又は省略が行われて良い。例えば、データ記憶装置５３０は、複数の場所に置かれ且つネットワークを通じてプロセッサ５１０によりアクセスされる複数の異なる記憶媒体であって良い。
【００８８】
上述のように、本開示で記載した実施形態は、以下に更に詳細に議論するように、種々のコンピュータハードウェア又はソフトウェアモジュールを備えた特定用途又は汎用コンピュータ（例えば、図５のプロセッサ５１０）の使用を含み得る。さらに、上述のように、本開示に記載の実施形態は、コンピュータ実行可能命令又はデータ構造を伝える又はそれを格納されたコンピュータ可読媒体（例えば、図５のメモリ５２０又はデータ記憶装置５３０）を用いて実施されて良い。
【００８９】
本開示で用いられるように、用語「モジュール」又は「コンポーネント」は、モジュール若しくはコンポーネントのアクションを実行するよう構成される特定ハードウェア実装、及び／又はコンピューティングシステムの汎用ハードウェア（例えばコンピュータ可読媒体、処理装置、又は何らかの他のハードウェア等）に格納され及び／又はそれらにより実行され得るソフトウェアオブジェクト又はソフトウェアルーチンを表して良い。幾つかの実施形態では、本開示に記載されたのと異なるコンポーネント、モジュール、エンジン及びサービスは、（例えば、別個のスレッドとして）コンピューティングシステムで実行されるオブジェクト又は処理として実施されて良い。本開示に記載のシステム及び方法の幾つかは概して（汎用ハードウェアに格納される及び／又はそれにより実行される）ソフトウェアで実装されるように記載されたが、専用ハードウェアの実装又はソフトウェアと専用ハードウェアの組み合わせの実装も可能であり考えられる。この説明では、「コンピュータエンティティ」は、本開示で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであって良い。
【００９０】
一般的方法に従い、図中に示す種々の特徴は縮尺通りでない場合がある。本開示に提示される説明は、任意の特定の装置（例えば、装置、システム、等）又は方法の実際の概観であることを意味せず、本開示の種々の実施形態を記載するために利用される単に理想化された表現である。したがって、種々の特徴の寸法は、明確化のために適宜拡張され又は縮小される場合がある。さらに、図面のうちの幾つかは、明確化のために簡略化される場合がある。したがって、図面は、所与の機器（例えば、装置）の全てのコンポーネント又は特定の方法の全ての動作を示さない場合がある。
【００９１】
本開示で及び特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本体）で使用される用語は、概して、広義の（open）用語と考えられる（例えば、用語「含む（including）」は「含むが、限定されない」と解釈されるべきであり、用語「有する（having）」は「少なくとも有する」と解釈されるべきであり、用語「含む（includes）」は「含むが、限定されない」等と解釈されるべきである）。
【００９２】
さらに、特定数の導入された請求項の引用が意図される場合、このような意図は、請求項の中に明示的に示され、このような引用が存在しない場合はこのような意図が存在しない。例えば、理解の助けとして、以下の添付の特許請求の範囲は、請求項の引用を導入するために、「少なくとも１つの」及び「１又は複数の」をいう前置語句の使用を含み得る。
【００９３】
さらに、特定数の導入された請求項引用が明示的に引用される場合、当業者は、このような引用が少なくとも引用された番号を意味することと解釈されるべきであることを認識するだろう（例えば、「２つの引用」はそのままで、他の変更が無ければ、少なくとも２つの引用、又は２以上の引用を意味する）。さらに、「Ａ、Ｂ、Ｃ、等のうちの少なくとも１つ」又は「Ａ、Ｂ、Ｃ、等のうちの１又は複数」に類似する慣例が用いられる例では、通常、このような構成は、Ａのみ、Ｂのみ、Ｃのみ、Ａ及びＢを一緒に、Ａ及びＣを一緒に、Ｂ及びＣを一緒に、又はＡ、Ｂ、Ｃを一緒に、等を含むと意図される。
【００９４】
さらに、２以上の代替用語を表す任意の離接語又は語句は、説明、請求項、又は図面の中であるかに係わらず、用語のうちの１つ、用語のうちのいずれか、又は両方の用語を含む可能性を包含すると理解されるべきである。例えば、語句「Ａ又はＢ」は、「Ａ」又は「Ｂ」又は「Ａ及びＢ」の可能性を含むと理解されるべきである。
【００９５】
しかしながら、このような語句の使用は、同じ請求項が前置語句「１又は複数」又は「少なくとも１つの」及び「ａ又はａｎ」のような不定冠詞を含むときでも、不定冠詞「ａ、ａｎ」による請求項引用の導入がこのような導入された請求項引用を含む任意の特定の請求項をこのような引用を１つだけ含む実施形態に限定することを示すと考えられてはならない（例えば、「ａ」及び／又は「ａｎ」は「少なくとも１つの」又は「１又は複数の」を意味すると解釈されるべきである）。同様のことは、請求項引用を導入するために使用される定冠詞の使用についても該当する。
【００９６】
さらに、用語「第１」、「第２」、「第３」等の使用は、本願明細書において必ずしも要素の特定の順序又は数を暗示するために使用されない。通常、用語「第１」、「第２」、「第３」等は、一般的識別子として、異なる要素の間を区別するために使用される。用語「第１」、「第２」、「第３」等が特定の順序を暗示することを示さない場合も、これらの用語が特定の順序を暗示すると解釈されるべきではない。さらに、用語「第１」、「第２」、「第３」等が要素の特定の数を暗示することを示さない場合も、これらの用語が要素の特定の数を暗示すると解釈されるべきではない。例えば、第１ウィジェットは第１側面を有するとして記載されて良く、第２ウィジェットは第２側面を有するとして記載されて良い。第２ウィジェットに関する用語「第２側面」の使用は、第２ウィジェットのこのような側面を、第１ウィジェットの「第１側面」から区別するためであって良く、第２ウィジェットが２つの側面を有することを暗示しない。
【００９７】
本開示に記載された全ての例及び条件文は、教育上の目的で、読者が本発明の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本開示の実施形態が詳細に記載されたが、種々の変更、置換及び修正が本開示の精神及び範囲から逸脱することなく行われうることが理解されるべきである。
【００９８】
以上の実施形態に加えて、更に以下の付記を開示する。
（付記１）  ネットワーク特性検証の方法であって、前記方法は、
検証すべきネットワークの１又は複数の特性を得るステップと、
前記ネットワークの中の第１ネットワーク装置のための第１転送ルールを得るステップであって、前記第１転送ルールは、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す、ステップと、
前記ネットワークの中の第２ネットワーク装置のための第２転送ルールを得るステップであって、前記第２転送ルールは、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す、ステップと、
前記第１転送ルール及び前記第２転送ルールに基づきプッシュダウンオートマトンを生成するステップと、
前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、
を有する方法。
（付記２）  前記第１ネットワーク装置及び前記第２ネットワーク装置は、カプセル化動作及びカプセル化解除動作のうちの少なくとも１つをパケットに対して実行するよう構成される、付記１に記載の方法。
（付記３）  前記第１ネットワーク装置及び前記第２ネットワーク装置は、ＭＰＬＳ（multiprotocol  label  switching）を用いて動作するよう構成される、付記２に記載の方法。
（付記４）  前記第１ネットワーク装置から前記第２ネットワーク装置へ前記ネットワークを横断するパケットの到達可能性グラフを生成するステップ、を更に有する付記１に記載の方法。
（付記５）  前記ネットワークの物理レイアウトを得るステップと、
前記ネットワークの前記物理レイアウト並びに前記第１転送ルール及び前記第２転送ルールに基づき、所与の時点の前記ネットワークのデータプレーンのレイアウトを得るステップと、
を更に有する付記１に記載の方法。
（付記６）  前記プッシュダウンオートマトンを生成するステップは、
各ネットワーク装置を前記プッシュダウンオートマトンの中の１又は複数の状態として表すステップと、
前記第１転送ルール及び第２転送ルールのうちの各転送ルールを、カプセル化動作に対応するプッシュ動作及びカプセル化解除動作に対応するポップ動作のうちの１つとして符号化するステップと、
前記プッシュ動作及び前記ポップ動作を、前記１又は複数の状態の間の遷移として使用するステップと、
を有する、付記１に記載の方法。
（付記７）  前記飽和に基づくアルゴリズムを適用するステップは、
前記ネットワークの中のネットワーク装置の間の各接続を、入力状態、出力状態、及び前記入力状態から前記出力状態への遷移動作を有するタプルとして表すステップであって、前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１又は複数を含む、ステップと、
各タプルについて、前記遷移動作が前記プッシュ動作を含むか否かを決定するステップと、
を有する、付記６に記載の方法。
（付記８）  前記遷移動作が前記プッシュ動作を含まないタプルの各々について、
所与の到着タプルの所与の到着遷移動作が前記プッシュ動作を含むか否かを決定するために、先行状態からの前記入力状態に到着する遷移を表す到着タプルの各々を分析するステップであって、
前記所与の到着遷移動作が前記プッシュ動作を含む場合、前記先行状態から前記出力状態へ到着する遷移を表す拡張到着タプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記所与の到着遷移動作が前記プッシュ動作を含まない場合、前記所与の到着タプルが前記プッシュダウンオートマトンに追加されていることを確認する、ステップと、
前記入力状態から更なる状態への遷移を表す拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するために、前記出力状態から前記更なる状態へ出発する遷移を表す出発タプルの各々を分析するステップであって、否の場合、前記拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
更にを有する付記７に記載の方法。
（付記９）  前記遷移動作が前記プッシュ動作を含むタプルの各々について、
所与の出発タプルの所与の出発遷移動作が前記ポップ動作を含むか否かを決定するために、前記出力状態から更なる状態へ出発する遷移を表す出発タプルの各々を分析するステップと、
前記所与の出発遷移動作が前記ポップ動作を含む場合、前記入力状態から前記更なる状態への遷移を表す拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するステップであって、前記プッシュダウンオートマトンに含まれない場合、前記拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
を更に有する付記７に記載の方法。
（付記１０）  前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１より多くを含み、前記入力状態及び前記出力状態が、２つのネットワーク装置の間に介在ネットワーク装置を有する該２つのネットワーク装置を表すようにする、付記７に記載の方法。
（付記１１）  前記１又は複数の特性のうちの少なくとも１つはネットワーク経路を含み、前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップは、
前記プッシュダウンオートマトンへの前記飽和に基づくアルゴリズムの適用により生成される前記ネットワーク経路の観測経路を、前記ネットワーク経路の期待ネットワーク経路と比較するステップと、
前記観測経路が前記期待ネットワーク経路に一致することに基づき、前記ネットワーク経路を検証するステップと、
を有する、付記１に記載の方法。
（付記１２）  命令を有する１又は複数の非一時的コンピュータ可読媒体であって、前記命令は、１又は複数のプロセッサにより実行されることに応答して、システムに工程を実行させ、前記工程は、
検証すべきネットワークの１又は複数の特性を得るステップと、
前記ネットワークの中の第１ネットワーク装置のための第１転送ルールを得るステップであって、前記第１転送ルールは、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す、ステップと、
前記ネットワークの中の第２ネットワーク装置のための第２転送ルールを得るステップであって、前記第２転送ルールは、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す、ステップと、
前記第１転送ルール及び前記第２転送ルールに基づきプッシュダウンオートマトンを生成するステップと、
前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、
を有する、コンピュータ可読媒体。
（付記１３）  前記第１ネットワーク装置及び前記第２ネットワーク装置は、ＭＰＬＳ（multiprotocol  label  switching）を用いて動作するよう構成される、付記１２に記載のコンピュータ可読媒体。
（付記１４）  前記プッシュダウンオートマトンを生成するステップは、
各ネットワーク装置を前記プッシュダウンオートマトンの中の状態として表すステップと、
前記第１転送ルール及び前記第２転送ルールのうちの各転送ルールを、カプセル化動作に対応するプッシュ動作及びカプセル化解除動作に対応するポップ動作のうちの１つとして符号化するステップと、
前記プッシュ動作及び前記ポップ動作を、前記状態の間の遷移として使用するステップと、
を有する、付記１３に記載のコンピュータ可読媒体。
（付記１５）  前記飽和に基づくアルゴリズムを適用するステップは、
前記ネットワークの中のネットワーク装置の間の各接続を、入力状態、出力状態、及び前記入力状態から前記出力状態への遷移動作を有するタプルとして表すステップであって、前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１又は複数を含む、ステップと、
各タプルについて、前記遷移動作が前記プッシュ動作を含むか否かを決定するステップであって、
前記遷移動作が前記プッシュ動作を含まないタプルの各々について、
所与の到着タプルの所与の到着遷移動作が前記プッシュ動作を含むか否かを決定するために、先行状態から前記入力状態に到着する遷移を表す到着タプルの各々を分析し、
前記所与の到着遷移が前記プッシュ動作を含む場合、前記先行状態から前記出力状態への遷移を表す拡張到着タプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記所与の到着遷移が前記プッシュ動作を含まない場合、前記所与のタプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記入力状態から前記更なる状態への遷移を表す第１の所与の拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するために、前記出力状態から前記更なる状態へ出発する遷移を表す出発タプルの各々を分析し、否の場合、前記第１の所与の拡張出発タプルを前記プッシュダウンオートマトンに追加し、
前記遷移動作が前記プッシュ動作を含むタプルの各々について、
第２の所与の出発タプルの所与の出発遷移動作が前記ポップ動作を含むか否かを決定するために、前記出発タプルの各々を分析し、
前記第２の所与の出発遷移動作が前記ポップ動作を含む場合、前記入力状態から更なる状態への遷移を表す第２拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定し、前記プッシュダウンオートマトンに含まれない場合、前記第２拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
を有する、付記１４に記載のコンピュータ可読媒体。
（付記１６）  システムであって、
第１ネットワーク装置であって、前記第１ネットワーク装置が可変長パケットヘッダを有する入力パケットをどのように扱うかを示す第１転送ルールを格納する第１記憶装置を含む、第１ネットワーク装置と、
ネットワークを介して前記第１ネットワーク装置と通信する第２ネットワーク装置であって、前記第２ネットワーク装置は、前記第２ネットワーク装置が前記入力パケットをどのように扱うかを示す第２転送ルールを格納する第２記憶装置を含む、第２ネットワーク装置と、
制御装置であって、
１又は複数のプロセッサと、
命令を含む１又は複数の非一時的コンピュータ可読媒体であって、前記命令は、前記１又は複数のプロセッサにより実行されることに応答して、前記制御装置に工程を実行させ、前記工程は、
検証すべき前記ネットワークの１又は複数の特性を得るステップと、
前記第１転送ルール及び前記第２転送ルールを得るステップと、
前記第１転送ルール及び前記第２転送ルールに基づき、プッシュダウンオートマトンを生成するステップと、
前記ネットワークの前記１又は複数の特性を検証するために、前記プッシュダウンオートマトンに飽和に基づくアルゴリズムを適用するステップと、
を含む、非一時的コンピュータ可読媒体と、
を有する制御装置と、
を有するシステム。
（付記１７）  前記第１ネットワーク装置及び前記第２ネットワーク装置は、カプセル化動作及びカプセル化解除動作のうちの少なくとも１つを前記パケットに対して実行するよう構成される、付記１６に記載のシステム。
（付記１８）  前記第１ネットワーク装置及び前記第２ネットワーク装置は、ＭＰＬＳ（multiprotocol  label  switching）を用いて動作するよう構成される、付記１６に記載のシステム。
（付記１９）  前記プッシュダウンオートマトンを生成するステップは、
各ネットワーク装置を前記プッシュダウンオートマトンの中の状態として表すステップと、
前記第１転送ルール及び前記第２転送ルールのうちの各転送ルールを、カプセル化動作に対応するプッシュ動作及びカプセル化解除動作に対応するポップ動作のうちの１つとして符号化するステップと、
前記プッシュ動作及び前記ポップ動作を、前記状態の間の遷移として使用するステップと、
を有する、付記１６に記載のシステム。
（付記２０）  前記飽和に基づくアルゴリズムを適用するステップは、
前記ネットワークの中のネットワーク装置の間の各接続を、入力状態、出力状態、及び前記入力状態から前記出力状態への遷移動作を有するタプルとして表すステップであって、前記遷移動作は、前記プッシュ動作及び前記ポップ動作のうちの１又は複数を含む、ステップと、
各タプルについて、前記遷移動作が前記プッシュ動作を含むか否かを決定するステップであって、
前記遷移動作が前記プッシュ動作を含まないタプルの各々について、
所与の到着タプルの所与の到着遷移動作が前記プッシュ動作を含むか否かを決定するために、先行状態から前記入力状態に到着する遷移を表す到着タプルの各々を分析し、
前記所与の到着遷移が前記プッシュ動作を含む場合、前記先行状態から前記出力状態への遷移を表す拡張到着タプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記所与の到着遷移が前記プッシュ動作を含まない場合、前記所与のタプルが前記プッシュダウンオートマトンに追加されていることを確認し、
前記入力状態から更なる状態への遷移を表す第１の所与の拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定するために、前記出力状態から前記更なる状態へ出発する遷移を表す出発タプルの各々を分析し、否の場合、前記第１の所与の拡張出発タプルを前記プッシュダウンオートマトンに追加し、
前記遷移動作が前記プッシュ動作を含むタプルの各々について、
第２の所与の出発タプルの所与の出発遷移動作が前記ポップ動作を含むか否かを決定するために、前記出発タプルの各々を分析し、
前記第２の所与の出発遷移動作が前記ポップ動作を含む場合、前記入力状態から更なる状態への遷移を表す第２拡張出発タプルが前記プッシュダウンオートマトンに含まれるか否かを決定し、前記プッシュダウンオートマトンに含まれない場合、前記第２拡張出発タプルを前記プッシュダウンオートマトンに追加する、ステップと、
を有する、付記１９に記載のシステム。
【符号の説明】
【００９９】
１００  環境
１１０  外部ネットワーク
１２０  ネットワーク
１２２  ネットワーク装置
１３０  制御装置
１５０  パケット
【図１】
2018117336.tif 000004
【図２】
2018117336.tif 000005
【図３】
2018117336.tif 000006
【図４Ａ】
2018117336.tif 000007
【図４Ｂ】
2018117336.tif 000008
【図４Ｃ】
2018117336.tif 000009
【図５】
2018117336.tif 000010