(57)【要約】  本発明の実施形態は、ネットワークの転送機能を表すための、プロトコル独立型で、ベンダー独立型で、効率的でスケーラブルな抽象化モデルを使用することができる。そのようなモデルは、ネットワークの系統的な分析および検証のために使用され得る。パケットヘッダ値は、１つまたは複数のワイルドカード化されたビット列のグループとして表され得、ここで、指定されていないヘッダ値は、完全にワイルドカード化されていると仮定される。この表現は、空間効率的なやり方でパケットの多くの組合せを記述することができ、より効率的な追跡および変換演算を可能にし、効率的に、大きいインターネットルーティングテーブルからトラフィックを表すことさえできる。パケット集合を記憶し、それらに対して演算するための、このより効果的なやり方のスケーラビリティ利益の結果として、ネットワークモデリングは、最大で最も複雑なネットワークのうちのいくつか、すなわち、利益が最も大きいものにスケーリングすることができる。
2019533373.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク中の複数のネットワークデバイスに関連付けられたネットワーク挙動情報を取得することと、前記ネットワーク挙動情報が、前記複数のネットワークデバイスのうちの各ネットワークデバイスのための少なくとも１つの規則テーブルを含み、前記少なくとも１つの規則テーブルが、少なくとも、前記ネットワーク内の前記複数のネットワークデバイス中の各ネットワークデバイスについて転送挙動を定義する規則のリストを含み、規則の前記リスト中の少なくとも１つの規則が、一致指定子および１つまたは複数の対応する行為を含み、前記一致指定子は、前記少なくとも１つの規則がそれに適用される一致パケットを識別し、前記一致指定子および前記１つまたは複数の対応する行為が、前記一致パケットのトラフィックフローを引き起こす、
ネットワークモデルにおいて分析すべき１つまたは複数のパケットを識別することと、前記１つまたは複数のパケットのうちの各パケットが、パケットヘッダ値を含む、
前記１つまたは複数のパケットを表す仮想パケットヘッダを作成することと、前記仮想パケットヘッダが、１つまたは複数のパケットヘッダグループを含み、前記１つまたは複数のパケットヘッダグループのうちの少なくとも１つが、２つまたはそれ以上のパケットヘッダ値の和集合を表す、
前記ネットワークモデルを通して前記仮想パケットヘッダをプッシュすることと、前記ネットワークモデルが、前記ネットワーク中の前記複数のネットワークデバイスの前記転送挙動を指定する、
前記ネットワーク中の前記複数のネットワークデバイスのうちの少なくとも１つのネットワークデバイスの第１の規則テーブルを、前記ネットワーク中の前記少なくとも１つのネットワークデバイスの前記第１の規則テーブルの規則の第１のリスト中の第１の規則の第１の一致指定子と前記仮想パケットヘッダを比較することによって、前記仮想パケットヘッダに適用することと、
前記少なくとも１つの規則の前記一致指定子に一致する前記仮想パケットヘッダに基づいて、前記少なくとも１つのネットワークデバイスの前記少なくとも１つの規則テーブルの前記少なくとも１つの規則の前記１つまたは複数の対応する行為に基づいて、前記トラフィックフローを定義する１つまたは複数のフローパスを決定することと、
を備える、ネットワークをモデル化するためのコンピュータ実装方法。
【請求項２】
前記仮想パケットヘッダの前記１つまたは複数のパケットヘッダグループのうちの少なくとも１つが、指定されていない少なくとも１つのパケットヘッダ値を含む、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記仮想パケットヘッダ中の少なくとも１つのパケットヘッダグループが、１つまたは複数のワイルドカードビット列を用いて２つまたはそれ以上のパケットヘッダ値のグループを表し、ここにおいて、少なくとも１つのワイルドカードビットが、前記２つまたはそれ以上のパケットヘッダ値中で特定のビット位置において０と１の両方を表す、請求項１に記載のコンピュータ実装方法。
【請求項４】
前記仮想パケットヘッダが、第１の仮想パケットヘッダと、１つまたは複数の他の仮想パケットヘッダとの間の差として表され、前記第１の仮想パケットヘッダが、パケットの第１のグループを表し、前記１つまたは複数の他の仮想パケットヘッダが、パケットの追加のグループを表す、請求項１に記載のコンピュータ実装方法。
【請求項５】
前記１つまたは複数のフローパスを決定することが、前記仮想パケットヘッダに対して変換演算を実施することをさらに備え、ここにおいて、前記変換演算が、少なくとも１つのパケットヘッダ値を変化させる、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記変換演算が、書換え演算、組合せ演算、移動演算、シフト演算、交差演算、および低減演算のうちの１つまたは複数を含む、請求項５に記載のコンピュータ実装方法。
【請求項７】
前記第１の仮想パケットヘッダと、変換演算の結果として計算された前記他の仮想パケットヘッダのうちの１つとのうちの少なくとも１つを変更することと、ここにおいて、前記変換演算が、少なくとも１つのパケットヘッダ値を変化させる、
前記変換演算の前記結果を低減することと、ここにおいて、前記演算の前記結果が、パケットの等価グループを表す異なる仮想パケットヘッダを生成する、
をさらに備える、請求項４に記載のコンピュータ実装方法。
【請求項８】
前記ネットワークデバイス挙動が、制御プレーン構成データに少なくとも部分的に基づいて推論される、請求項１に記載のコンピュータ実装方法。
【請求項９】
一致パケットのための前記１つまたは複数の対応する行為が、パケットに変換を適用することと、パケットを廃棄することと、後続の規則にパケットを転送することと、後続の規則テーブルにパケットを転送することと、前記ネットワーク中の後続のネットワークデバイスにパケットを転送することと、１つまたは複数のポートからパケットを転送することと、前記ネットワークから別のデバイスにパケットを転送することとのうちの少なくとも１つを含む、請求項１に記載のコンピュータ実装方法。
【請求項１０】
方法を実装するためにプロセッサによって実行可能なコードを記憶する非一時的コンピュータ可読媒体であって、前記方法が、
ネットワーク中の複数のデバイスに関連付けられたネットワーク挙動情報を取得することと、前記ネットワーク挙動情報が、前記ネットワーク中の各デバイスの転送挙動を定義する、
パケットの１つまたは複数の集合を表す仮想パケットヘッダを作成することと、前記仮想パケットヘッダが、１つまたは複数のパケットヘッダグループを含み、前記１つまたは複数のパケットヘッダグループのうちの少なくとも１つが、２つまたはそれ以上のパケットヘッダ値の和集合を表す、
前記仮想パケットヘッダを使用して、前記ネットワーク挙動情報に少なくとも部分的に基づいて、分析演算を実施することと、
前記分析演算に少なくとも部分的に基づいて、トラフィックフローを定義する１つまたは複数のフローパスを決定することと
を備える、非一時的コンピュータ可読媒体。
【請求項１１】
前記ネットワーク挙動情報が、少なくとも１つの規則テーブルを含み、前記少なくとも１つの規則テーブルが、前記パケットのフローパスまたは前記ネットワークの前記トラフィックフロー内のパケットの前記集合を定義する少なくとも１つの規則を含み、前記少なくとも１つの規則テーブル中の少なくとも１つの規則が、暗黙的または明示的であり、前記少なくとも１つの規則テーブルの各々が、暗黙的または明示的であり、少なくとも１つの規則テーブルが、規則の順序付きまたは順序なしリストを含んでいる、請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１２】
前記仮想パケットヘッダが、第１の仮想パケットヘッダと、１つまたは複数の他の仮想パケットヘッダとの間の差として表され、前記第１の仮想パケットヘッダが、パケットの第１のグループを表し、前記１つまたは複数の他の仮想パケットヘッダが、パケットの追加のグループを表す、請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１３】
前記分析演算が、前記仮想パケットヘッダに対する変換演算を含み、ここにおいて、前記変換演算が、パケットの前記１つまたは複数の集合の少なくとも１つのパケットヘッダ値を変化させる、請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１４】
前記仮想パケットヘッダの前記１つまたは複数のパケットヘッダグループのうちの少なくとも１つが、指定されていない少なくとも１つのパケットヘッダ値を含む、請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１５】
前記仮想パケットヘッダ中の少なくとも１つのパケットヘッダグループが、１つまたは複数のワイルドカードビット列を用いて２つまたはそれ以上のパケットヘッダ値のグループを表し、ここにおいて、少なくとも１つのワイルドカードビットが、前記２つまたはそれ以上のパケットヘッダ値中で特定のビット位置において０と１の両方を表す、請求項１０に記載の非一時的コンピュータ可読媒体。
【請求項１６】
システムであって、
１つまたは複数のプロセッサと、
前記１つまたは複数のプロセッサによって実行されたとき、前記システムに、
ネットワーク中の複数のデバイスに関連付けられたネットワーク挙動情報を取得することと、前記ネットワーク挙動情報が、前記ネットワーク中の各デバイスの転送挙動を定義する、
パケットの１つまたは複数の集合を表す仮想パケットヘッダを作成することと、前記仮想パケットヘッダが、１つまたは複数のパケットヘッダグループを含み、前記パケットヘッダグループのうちの少なくとも１つが、パケットの前記１つまたは複数の集合の２つまたはそれ以上のパケットヘッダ値の和集合を表す、
前記仮想パケットヘッダを使用して、前記ネットワーク挙動情報に少なくとも部分的に基づいて、分析演算を実施することと、
前記分析演算に少なくとも部分的に基づいて、トラフィックフローを定義する１つまたは複数のフローパスを決定することと
を行わせる命令を含む１つまたは複数のメモリデバイスと
を備える、システム。
【請求項１７】
前記仮想パケットヘッダが、第１の仮想パケットヘッダと、１つまたは複数の他の仮想パケットヘッダとの間の差として表され、前記第１の仮想パケットヘッダが、パケットの第１のグループを表し、前記１つまたは複数の他の仮想パケットヘッダが、パケットの追加のグループを表す、請求項１６に記載のシステム。
【請求項１８】
前記分析演算が、前記仮想パケットヘッダに対する変換演算を含み、ここにおいて、前記変換演算が、パケットの前記１つまたは複数の集合の少なくとも１つのパケットヘッダ値を変化させる、請求項１６に記載のシステム。
【請求項１９】
前記仮想パケットヘッダの前記１つまたは複数のパケットヘッダグループのうちの少なくとも１つが、指定されていない少なくとも１つのパケットヘッダ値を含む、請求項１６に記載のシステム。
【請求項２０】
前記仮想パケットヘッダ中の少なくとも１つのパケットヘッダグループが、１つまたは複数のワイルドカードビット列を用いて２つまたはそれ以上のパケットヘッダ値のグループを表し、ここにおいて、少なくとも１つのワイルドカードビットが、前記２つまたはそれ以上のパケットヘッダ値中で特定のビット位置において０と１の両方を表す、請求項１６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
[0001]本出願は、すべての目的のためにその全体が参照により本明細書に組み込まれる、Ｐｅｙｍａｎ  Ｋａｚｅｍｉａｎらによる「ＳＹＳＴＥＭ  ＡＮＤ  ＭＥＴＨＯＤ  ＦＯＲ  ＳＣＡＬＡＢＬＥ  ＮＥＴＷＯＲＫ  ＭＯＤＥＬＩＮＧ」と題する２０１６年１０月２１日に出願された米国仮特許出願第６２／４１１，３６４号の優先権を主張する。
【背景技術】
【０００２】
[0002]ネットワークは、現代の情報技術システムのバックボーンとしてますます複雑になっている。大企業は、一般に、そのネットワークインフラストラクチャを形成するために、異なるベンダーからの数百または数千個のデバイスおよびソフトウェア構成要素を採用することがある。また、複雑さおよびサイズの増大は、転送ループ、構成誤り、到達可能性問題、またはハードウェア障害など、より多くの障害点をもたらす。
【０００３】
[0003]ネットワーク障害を診断することは、いくつかの理由のために困難である。第１に、全体的なネットワーク挙動を定義する各ネットワークデバイスに関連付けられた転送状態が、ネットワーク全体にわたって分散され、ベンダー依存型のやり方およびデバイスタイプ依存型のやり方で構成されたデバイス間の新生のインタラクションの結果である。第２に、分散された転送状態は、監視することが困難であり、しばしば、ネットワーク管理者が、デバイスに手動でログインし、低レベルテストを行うことを必要とする。第３に、複数の管理者またはユーザが同時に転送状態を編集し、矛盾する構成を生じ、結果として、予期しない転送状態につながることがある。
【０００４】
[0004]ネットワークモデルは、ネットワークの挙動のソフトウェアコピーを与え、それにより、ネットワーク管理者は、現在の挙動をより良く理解し、問題をトラブルシューティングし、ネットワークがポリシーに従って挙動しているかどうかを分析し、性能およびフォールトトレランスを改善するためのやり方を試してみることさえできる。しかしながら、すべてのモデルが容易または正確にスケーリングするとは限らないので、ネットワークが大きいほど、それはモデル化することがより困難になり得る。したがって、ネットワークモデリングの利点が最も有益であり得る、大きく、高度に複雑なネットワーク中の問題を診断することを助けるために、ネットワークモデルをスケーリングする技法および方法が必要とされる。
【発明の概要】
【０００５】
[0005]本発明の様々な実施形態または例が、以下の発明を実施するための形態および添付の図面において開示される。
【図面の簡単な説明】
【０００６】
【図１】[0006]本発明の一実施形態による、デバイスのネットワークを示す高レベル図。
【図２】[0007]本発明の一実施形態による、パケットの集合を符号化することの例示的な表現を示す図。
【図３（Ａ）】[0008]本発明の一実施形態による、ワイルドカードを使用してパケットのフィールドを符号化することの例示的な表現を示す図。
【図３（Ｂ）】本発明の一実施形態による、ワイルドカードを使用してパケットのフィールドを符号化することの例示的な表現を示す図。
【図３（Ｃ）】本発明の一実施形態による、ワイルドカードを使用してパケットのフィールドを符号化することの例示的な表現を示す図。
【図４】[0009]本発明の一実施形態による、規則テーブルを通してパケット集合を追跡することの一例を示す図。
【図５（Ａ）】[00010]本発明の一実施形態による、クロス乗積問題を経験する規則テーブルの例を示す図。
【図５（Ｂ）】本発明の一実施形態による、クロス乗積問題を経験する規則テーブルの例を示す図。
【図５（Ｃ）】本発明の一実施形態による、クロス乗積問題を経験する規則テーブルの例を示す図。
【図６（Ａ）】[00011]本発明の一実施形態による、ネットワークモデルに対応するＩＰアドレスの例を示す図。
【図６（Ｂ）】本発明の一実施形態による、ネットワークモデルに対応するＩＰアドレスの例を示す図。
【図６（Ｃ）】本発明の一実施形態による、ネットワークモデルに対応するＩＰアドレスの例を示す図。
【図７】[00012]本発明の一実施形態による、ネットワークを分析する例示的な方法を示す高レベル流れ図。
【図８】[00013]本発明の一実施形態による、コンピュータシステムを示す高レベルブロック図。
【発明を実施するための形態】
【０００７】
[00014]様々な実施形態または例が、プロセス、装置、ユーザインターフェース、またはコンピュータ可読記憶媒体などのコンピュータ可読媒体上の一連のプログラム命令、またはコンピュータネットワークをシステムとして含む、多数のやり方で実装され得、ここで、プログラム命令は、光、電子、またはワイヤレス通信リンク上で送られる。概して、開示されるプロセスの演算は、特許請求の範囲において別段の定めがある場合を除き、任意の順序で実施され得る。
【０００８】
[00015]１つまたは複数の例の詳細な説明が、添付図とともに以下で与えられる。詳細な説明は、そのような例に関して与えられるが、いずれかの特定の例に限定されない。範囲は、特許請求の範囲によってのみ限定され、多数の代替形態、変更形態、および等価形態が包含される。完全な理解を与えるために、多数の具体的な詳細が以下の説明において記載される。これらの詳細は例のために与えられ、説明される技法は、これらの具体的な詳細の一部または全部なしに特許請求の範囲に従って実践され得る。明確さのために、例に関係する技術分野において知られている技術的要素は、説明を不必要に不明瞭にすることを回避するために、詳細には説明されていない。
【０００９】
[00016]ネットワーク内で、データは、あるネットワーキングデバイスから別のものにパケットを介して送信され得る。ネットワーキングデバイスは、パケットをそれらのヘッダビットに基づいて転送し、ネットワーク挙動は、複数の異なるタイプのモデルを使用してモデル化され得る。一実施形態では、データプレーンモデルが、ネットワークをモデル化するために実装され得る。データプレーンモデルでは、送信されているデータのネットワーク挙動が、パケットによって表され、ネットワークを通したそれらの挙動は、トラフィック、フローパス、トラフィックフローなどと呼ばれることがある。いくつかの実施形態では、状態情報（たとえば、構成データ、転送状態、ＩＰテーブル、規則、ネットワークトポロジー情報など）が、ネットワーク中の複数のデバイスに関連付けられ得る。状態情報、ネットワーク情報、および／またはネットワーク上のトラフィックに関する他の関連情報が、ネットワーク中のデバイスから受信されるか、あるいは別のエンティティまたはネットワークデータソースから取得され得る。状態情報は、ネットワークモデリングシステムによってパースされ、データプレーンモデルなど、ネットワークモデルを生成するために使用され得る。概して、ネットワークモデルは、ネットワークがデータのパケットをどのように処理するかを表す。モデルを使用して、ネットワークモデリングシステムは、ネットワークを通してデータのパケットによって取られる可能なフローパスを識別することが可能であり得る。ネットワークモデリングシステムは、次いで、トラフィックのタイプ、規則一致の頻度、トラフィックがネットワークを通って流れるときにどんな種類の変換が生じるか、トラフィックがどこで廃棄さるかなど、ネットワークを分析し、ネットワーク挙動を識別するためにネットワークモデルを生成することから集められた情報を使用し得る。
【００１０】
[00017]いくつかの実施形態では、ネットワークモデリングシステムは、２つの異なるタイプのモデル、すなわち、データプレーンモデルまたは制御プレーンモデルを生成し得る。データプレーン、制御プレーンおよび管理プレーンは、電気通信アーキテクチャの３つの基本構成要素である。制御プレーンおよび管理プレーンは、ネットワークがそれを搬送するために存在するトラフィックを担持するデータプレーンをサービスする。データプレーンは、ユーザトラフィックを搬送するネットワークの一部である。データプレーンは、ユーザプレーン、転送プレーン、キャリアプレーンまたはベアラプレーンとも呼ばれることがある。データプレーンは、クライアントコンピューティングデバイスとの間のデータ搬送を可能にし、複数のプロトコルを通した複数のデータ送信を扱い得る。従来のネットワーキングでは、すべての３つのプレーンは、一般に、ルータおよびスイッチのファームウェアにおいて実装され得る。ソフトウェア定義ネットワーキング（ＳＤＮ）は、データプレーンと制御プレーンとを分離し、代わりにソフトウェアで制御プレーンを実装し、これは、プログラマチックアクセスが、ネットワークアドミニストレーションをはるかによりフレキシブルにすることを可能にする。データプレーンモデルは、ネットワーク状態データをデバイスレベル転送挙動と組み合わせることによって構築され得る。たとえば、データプレーンモデルは、個々のデバイスの転送ルックアップおよび出力行為について考え得、転送ルックアップおよび出力に基づいて、知られているリンクに沿って個々のデバイスを相互接続し得る。
【００１１】
[00018]別の実施形態では、ネットワークモデリングシステムは、制御プレーンモデルを生成し得る。制御プレーンモデルは、ネットワーク構成データをプロトコル挙動と組み合わせることによって生成および構築され得る。ネットワークモデルは、パケットがネットワークを通って進むとき、パケットの個々の挙動を表すように働き得る。全体的なネットワーク挙動は、１つまたは複数の規則テーブルを使用して個々のネットワークデバイスの個々の挙動について考えることによって表され得、そこにおいて、規則テーブルは、パケットがネットワーク上のネットワークデバイスを通ってどのように進むかを規定し得る。たとえば、パケットがネットワークデバイスを介してネットワークを通ってどのように進むかを規定することによって、ネットワークリンクまたはフローパスが知られ得る。次いで、ネットワークは、図１に示されているように、知られているネットワークリンクに沿ってネットワークデバイスを相互接続することによってモデル化され得る。
【００１２】
[00019]図１は、本発明の一実施形態による、ネットワーク化されたデバイス１０２、１０４、および１０６のネットワーク１００を示す高レベル図である。ネットワーク１００は、フローパス（たとえば、１０８）によってリンクされた複数のネットワーク化されたデバイス１０２、１０４、および１０６を含み得る。一例として、各ネットワーク化されたデバイス１０６は、テーブル０およびテーブル１を含む規則テーブルのセット１１０を含んでいることがある。１１０中の各規則テーブルは、一連の規則、たとえば、パケット中のいくつかのフィールドを変換すること、それらを別のテーブルまたはデバイスポートに転送すること、あるいはパケットを廃棄することからなる。一連の規則は、一致指定子１１２、１１６を含み、パケットが、それぞれ、一致指定子１１２、１１６を満たすときにパケットに適用されるべき対応する行為１１４、１１８を指定する。例示的な例として、ネットワークデバイス１０６に到着するパケットまたはパケットのグループは、１１０中のテーブル０およびテーブル１の対象となり得、そこにおいて、パケットは、この例では、パケットヘッダ値が「１１ｘｘ．．０ｘ」に一致するかどうかを確かめるために、一致指定子１１２と比較され得る。一致指定子１１２が満たされる場合、対応する行為１１４がパケットに対して実行される。この例では、次いで、パケットヘッダ値が、「１ｘ０１ｘｘ．．ｘ１」で書き換えられ、次いで、ポート２に送られ得る。別の例示的な例では、パケットは一致指定子１１６と比較され得、一致指定子１１６が満たされる場合、対応する行為１１８が実行され、この例では、パケットが廃棄され得る。
【００１３】
[00020]様々な実施形態によれば、ネットワークモデリングシステムは、２つの異なるタイプのモデル、すなわち、データプレーンモデルまたは制御プレーンモデルを生成し得る。制御プレーンモデルでは、データプレーン規則が、制御プレーン構成および挙動から推論され得、データプレーンモデルでは、データプレーン規則は、デバイスから直接収集されるか、他のソースから取得されるか、または他の手段から取得され得る状態情報に基づき得る。概して、ネットワークモデルは、制御プレーン構成とデータプレーン状態との任意の組合せを使用して構築され得る。ネットワークモデリングシステムは、トレーニング、デバッギング、および分析目的のために、ネットワークを通して１つまたは複数のパケットをネットワーク管理者が追跡することを可能にするために、ソフトウェアでネットワークモデルを生成する。ネットワークを通して個々のパケットを追跡し、パケットの挙動を計算することは、比較的簡単であり得、既存のネットワーク分析システムは、パケットを識別し、パケットを第１の規則テーブル中の規則と照合し、得られた行為を適用し、他の規則テーブルまたは他のデバイスへのリンクをたどり、それらを通した追跡を続け、パケットがネットワークを出たかまたは廃棄されたときに停止することができる。しかしながら、あらゆる可能なパケットおよびフローパスをカバーするようにネットワークの完全な挙動モデルを構築することは、大規模ネットワークの場合、実現不可能になる。大規模ネットワーク中の別個の潜在的なパケットおよびパスの数は、長い計算時間および法外なコンピューティングリソースにつながる。大規模ネットワークまたは全ネットワークをモデル化することの困難さにもかかわらず、全ネットワーク挙動をモデル化することは、いくつかの理由のために、たとえば、事前にエラーをトリガし得るパケットを識別することなしにループのようなエラーを検出するために、および到達可能性に関する情報を与える（たとえば、ネットワーク中のホストに到達することができるすべてのパケットを見つける）ために望ましい。すべてのＩＰｖ４パケットなど、パケットの制限付きサブセットを追跡することさえ、追跡されるべきパケットのセットが大きいとき、計算量的に実現不可能であり得る。
【００１４】
[00021]ユーザまたはネットワーク管理者は、どんな特定の行為がパケットに起こったか、およびその行為がネットワーク内のどこで生じたかを発見するために、ネットワークモデルを調べ得る。たとえば、ユーザまたはネットワーク管理者は、パケットがネットワーク内のどこで廃棄されたかを決定するために、または複数のパスが２つのホストの間で利用可能であることを検証するために、ネットワークモデルを使用し得る。いくつかの事例では、ネットワークに入ったかまたはネットワーク中の特定のデバイスに到着したいくつかのパケット（たとえば、パケットのグループ）は、その後、同じフローパスを通って進むように転送される。個々にパケットのグループをダイレクトおよび転送すること（たとえば、１つずつ各個々のパケットをダイレクトおよび転送すること）は、大規模ネットワーク中の挙動分析を実現不可能にすることになる。個々に各パケットを処理することは、遅く冗長なものになるだけでなく、それは、処理リソースの非効率的で不経済な使用になる。したがって、全ネットワークモデルおよび／または大規模ネットワークモデルの完全な分析を計算量的に実現可能にするのを助けるために、パケットのグループが、同様のやり方で、ネットワークに入るかまたはネットワーク中の特定のデバイスに到着し、転送されるとき、ネットワークモデルは、パケットをパケットの集合に互いにグループ化し得る。ネットワークモデルは、パケットのグループが同様の様式（たとえば、フローパス）でまとめて転送されるべきであると決定し、続いて、パケットの集合としてそれらを処理および参照し得る。たとえば、パケット集合を規則テーブル規則と照合すること、パケットの集合と規則の一致パケットとの間の交差を見つけること、規則に一致しなかったパケットの残りの集合を見つけること、パケットの集合を変換する行為を適用すること、およびパケットの２つの集合間の交差を見つけることを含む、複素数学演算が、パケットの集合を使用して各規則テーブル中で適用され得る。これらの演算のすべては、各個々の潜在的なパケットについてではなく、全体としてパケット集合に対して実施され得る。
【００１５】
[00022]本発明の実施形態は、既存の技法よりも大きく複雑なネットワークにスケーリングされ得る改善されたモデル実装形態を生じる、パケットの集合を表す新規の技法を提供する。パケットの集合（すなわち、パケット集合）をどのように表すかを決定することが、得られたネットワークモデル分析に著しく影響を及ぼすことがあり、たとえば、表現は、どの数学演算を実行すべきかに影響を及ぼすことがあり、表現は、実装複雑さ、メモリ要件、および実行効率で変動することがある。様々な実施形態によるネットワークモデルは、パケットおよびパケットの集合をグループ化するための改善されたパケット表現を採用し、改善された表現を使用して数学演算を実施することによって、妥当な時間の量においてネットワークモデルを構成および分析する手段を提供する。
【００１６】
[00023]図２は、本発明の一実施形態による、パケットの集合を符号化することの一例２００を示す。パケットを、ネットワーク内のそれらの挙動が観測および分析され得るように表すための複数のやり方がある。パケットの集合２１２は、ネットワーク上の発信元と宛先との間でルーティングされ得る。パケットは、次いで、局所的にまたは広域的に、ワイヤードまたはワイヤレスにネットワークを移動して回り、次いで、ネットワーク上の別のノードによって非バンドル化され得る。ネットワークトラブルシューティング中に、ネットワークを分析する管理者および技術者は、パケットを開くかまたはパケットの中をのぞくために、およびそれらの内容を観測するために、プロトコル分析器を使用する必要があり得る。集合２１２中の各パケットは、ネットワーク上でのパケットの挙動に関してネットワーク管理者に重要な洞察を与えることができる内容を保持し得る、様々なフィールド２０２、２０４、２０６、２０８、および２１０を含む。たとえば、送信元ＭＡＣアドレス２０２（ＳＲＣ  ＭＡＣ）、宛先ＭＡＣアドレス２０４（ＤＳＴ  ＭＡＣ）、送信元ＩＰアドレス２０８（ＳＲＣ  ＩＰ）、宛先ＩＰアドレス２１０（ＤＳＴ  ＩＰ）、および他のフィールド２０６。図２に示されているように、集合２１２中のパケットは、フィールド２０６のためのそれらのパケットヘッダ値が異なり、したがって、値は、ワイルドカードビットを使用して組み合わせられ得る。図２に示されているように、仮想パケットヘッダ２１４は、パケットの集合２１２を符号化することの表現を示し、ここで、「ｘ」ビットは、「ｘ」ビットが、フィールド２１６に示されているように、同時に０と１の両方を表すことができるように、ワイルドカードビットとして作用し得る。
【００１７】
[00024]図３（Ａ）〜図３（Ｃ）は、本発明の一実施形態による、ワイルドカードを使用してパケットフィールドの集合を符号化することの例示的な表現を示す。図３（Ａ）に示されているように、隣接する２のべき乗領域は、単一のワイルドカード化された範囲によって表され得る。パケットの集合は、ワイルドカード化されたビット列をヘッダのフィールド中に含めることによって表され得、したがって、全ヘッダフィールドは、「ｘ」がヘッダフィールド中のすべてのビット位置にあるとき、任意の値を取ることができる。いくつかの実施形態では、パケットヘッダ値は、指定されていないか、未知であるか、空であるか、または無関係であり得、したがって、その特定のパケットヘッダフィールドのための制限付き値がない限り、完全にワイルドカード化されていると暗黙的に仮定され得る。表現３００は、隣接する２のべき乗整合範囲を有するヘッダフィールドのためにワイルドカードビットを使用することを含む。たとえば、１．２．３．０／２４のようなＩＰｖ４サブネットは、値が、２のべき乗（０）で開始し、２のべき乗のちょうど１つ前の値（２５５）で終了するので、そのサブネット中の２５６個の可能なＩＰアドレスを表すために、８つのｘビットで終了する単一のワイルドカード化されたビット列を用いて表され得る。したがって、パケットは、次いで、｛０、１｝Ｌ空間中の点としてモデル化され得、ここで、Ｌはヘッダの長さである。例示のために、表現３００では、すべてが「ｘ」ビットの完全にワイルドカード化されたヘッダ３１０は、値「００００００００」を有するパケットヘッダ３０２、値「０００００００１」を有するパケットヘッダ３０４、値「０００００００１０」を有するパケットヘッダ３０６、および値「１１１１１１１１」を有するパケットヘッダ３０８までのすべての値を表すことができる。
【００１８】
[00025]図３（Ｂ）は、ヘッダフィールド値の集合の別の例示的な表現３２０を示す。ワイルドカードビットは、１つまたは複数の特定のビット位置において異なるが、他の場所では共通の値を共有するパケットの集合を表すことができる。ちょうど１つのビット位置において異なる２つのビット列が、異なるビットをワイルドカード化することによって１つのビット列に組み合わせられ得、たとえば、値「００００」および値「００１０」は、「００ｘ０」として表され得、ここで、「ｘ」ビットは、対応するビットがワイルドカード化され、０と１の両方を示すことを示す。この手順は、表された値を、ワイルドカード化されたビット列として組み合わせるために、繰り返し実施され得る。２つの点がこのＬ次元空間中で隣接するとき、それらは、ワイルドカードを使用するコンパクトな表現によって表され得る。たとえば、４次元空間中の「００００」および「００１０」は互いに隣接し、これらの２つの点は「００ｘ０」として表され得、ここで、「ｘ」ビットは、対応するビットがワイルドカード化され、０と１の両方を示すことを示す。例示のために、表現３２０では、それぞれ、値「１０１０」を有するパケットヘッダ３２２、値「１０１１」を有するパケットヘッダ３２４、および値「１１００」を有するパケットヘッダ３２６中で参照される１０から１２までの値をもつＴＣＰポートの範囲について考える。３２２、３２４、および３２６中のこれらの３つの値は、それぞれ、値１０１ｘおよび値１１００を有する２つのワイルドカード化されたビット列３２８および３３０によって表され得、ここで、１６ビットＴＣＰポートフィールドの先行する１２ビットは、両方のビット列中ですべて０である。
【００１９】
[00026]しかしながら、ワイルドカード化することは、いくつかのパケット集合を表す場合に利益を与えないことがある。図３（Ｃ）は、ワイルドカードを使用してより少ない値で表され得ない例を示す。表現３４０は、それぞれ、値０１および値１０を有する２つの２ビット列３４２および３４４について考える。単一のワイルドカード化されたビット列がこれらの２つの値を表すことはできず、２つのビット列が必要とされる。表現３４０はまた、それぞれ、値００１、値０１０、および値１００を有する３つの３ビット列３４６、３４８、および３５０について考える。それらのいずれも組み合わせられ得ず、すべての値を表すために３つのビット列が必要とされる。
【００２０】
[00027]既存のネットワーク分析技法では、ワイルドカード化することは、パケット集合を表すために必要とされるビット列の数を低減するのを助ける。しかしながら、ＩＰアドレス範囲、イーサネット（登録商標）タイプ、およびＴＣＰポートなどのための個々のフィールド値は、しばしば、図３（Ｃ）の表現に示されているように組合せ可能でないので、単一のワイルドカード化されたビット列にいたるまでの低減はまれである。したがって、パケット集合は、一般に、複数のビット列のリストを含んでいる。パケット集合がよりコンパクトなやり方で表され得ず、多くのビット列を必要とするとき、ネットワークを通してそれらを追跡することは、多数の費用がかかる数学演算を生じることがある。したがって、パケットのグループは、それのヘッダが隣接する領域を表すもののみに限定され得る。単一のワイルドカード化されたビット列によってパケットのグループを表すことが可能でない場合、ネットワークモデルは、まとめてグループとして記述する代わりに個々にパケットを記述するために、複数のビット列のリストを使用することが必要とされる。パケットのグループ内の各パケットの個々の表現は、それがはるかにより長いビット列表現を生じるので、より多くのストレージを消費する。その結果、パケットのグループ内の個々のパケットを参照するネットワークモデルおよび分析は、無制限のメモリおよび処理リソースなしにスケーリングすることが困難であり得る。
【００２１】
[00028]さらに、ネットワーキングでは、ネットワークを通してパケットを追跡することは、ネットワーク内を進むパケットのトラフィックフローを定義する規則テーブルにアクセスすることを伴う。規則テーブルはいくつかの規則を含んでおり、ここで、各個々の規則は、パケットがどのようにダイレクトされるべきであるかを定義する条件として表され得、たとえば、パケットが条件を満たす場合、そのパケットは、その条件について定義された特定のフローパスにダイレクトされることになる。しかしながら、規則テーブルを使用して追跡することは、特に、規則テーブルが、ファイアウォールまたはルータにおいて見つけられるものなど、アクセス制御リスト（ＡＣＬ）エントリを表すとき、非効率的であり得る。多数の個々のパケットヘッダフィールド値が、デバイスＡを通して、次いで、デバイスＢ中でパケットを追跡することの結果である場合、パケットは、異なるフィールドに基づいて扱われる。その結果、追跡すべき潜在的なパケット値の数は急速に増加し、余分なメモリおよび不要な計算時間を消費することがある。
【００２２】
[00029]図４は、本発明の一実施形態による、パケット集合が規則テーブルに入ることの一例を示す。例４００では、入力パケット集合４０２は、ネットワークモデルにおいてデバイス４０４に入り得、デバイスは、規則テーブル４０８「テーブル０」と規則テーブル４１０「テーブル１」とを含む。規則テーブル４０８「テーブル０」中の第１の規則「Ｍａｔｃｈ０」４１２がパケット集合に一致するかどうかを見つけ出すために、交差演算など、数学演算が、点４４０に示されているように、実施されなければならない。「一致０」４１２のためのこの演算は、何らかの重複、したがって、一致があるかどうかを決定するためだけでなく、厳密な重複を決定するためにも実行され得る。厳密な重複は、後で点４４２において「Ａｃｔｉｏｎｓ０」４１４を適用するときに使用され得、これは、パケット集合を潜在的に変更し得る。その後、追跡は、（１）点４４６における潜在的に変更されたパケット集合を用いて次の規則テーブル４１０「テーブル１」中で、ならびに（２）点４４８において示されているパケット集合の非重複部分を用いてテーブル４０８「テーブル０」中の次の規則（たとえば、「Ｍａｔｃｈ１」４１８および「Ａｃｔｉｏｎｓ１」４２０）において続き得る。点４４６において、「Ｍａｔｃｈ０」４２６が満たされ、「Ａｃｔｉｏｎｓ０  ４３０」が取られるとき、出力パケット集合４０６は、ｐｏｉｎｔ４５０に示されているように、デバイス４０４を出ることがある。パケット集合はより多くのビット列を含んでいるので、交差演算を完了するための計算サイクルの数は増加し、したがって、交差演算は、全体的な計算時間を容易に左右することがある。さらに、点４４２においてヘッダフィールドを書き換えることと同様に、行為を適用することは、より多くのビット列がある場合、費用がかかるようになることがある。
【００２３】
[00030]ネットワークモデル上でのパケット追跡をスケーリングすることに関するこれらの問題は、ヘッダフィールドにわたる値のクロス乗積によって示されるパケットの集合を表すとき、特に顕著になる。「クロス乗積問題」と呼ばれる、この問題は、２つまたはそれ以上のヘッダフィールドにわたる値の全デカルト積を含むパケットの集合を表すときに起こる。ヘッダ値の組合せを列挙することは、集合中のすべてのパケットを表すための多数のワイルドカード化されたビット列を生じ、これは、各交差演算および書換え演算に計算コストを追加する。クロス乗積問題が、慎重なパケット集合表現、および集合に対する効率的な数学演算を通して対処されない場合、ネットワークモデルは、実際的に大きいサイズにスケーリングしないことがある。追跡プロセスは、時間がかかり過ぎることになるか、またはあまりにも多くのリソースを必要とするので有用でないことがあるかのいずれかである。
【００２４】
[00031]図５（Ａ）〜図５（Ｃ）は、本発明の一実施形態による、ネットワークモデルを計算することの例を示す。図６（Ａ）〜図６（Ｃ）は、本発明の一実施形態による、ＩＰ宛先ポートヘッダフィールドと、ＴＣＰ宛先ポートヘッダフィールドとのクロス乗積によって示されるパケットの集合の例を示す。たとえば、クロス乗積問題は、（１）図５（Ａ）中の単一のテーブル内で、（２）図５（Ｂ）中の単一のデバイスにおける規則テーブルにわたって、および（３）図５（Ｃ）中の異なるデバイスにおける独立した規則テーブルにわたって、ネットワークモデルを計算する間の少なくとも３つのシナリオに示され得る。
【００２５】
[00032]図５（Ａ）では、クロス乗積問題は、ネットワークデバイス５００における単一の規則テーブル５０２内で見られ得、ここで、個々の規則５０６、５０８、５１０、および５１２は、パケットを転送することに関連し得る。一例では、対応する図６（Ａ）において、ファイアウォール規則テーブルは、２つのフィールド、すなわち、ＩＰ宛先アドレス６０２「ｉｐ＿ｄｓｔ」およびＴＣＰ宛先ポート６１０「ｔｃｐ＿ｄｓｔ＿ｐｏｒｔ」に関して一致し得る（たとえば、図５（Ａ）中の５０２）。ＩＰ宛先アドレス６０２フィールドは、ＩＰアドレス６０４、６０６、および６０８を含み得、ＴＣＰ宛先ポート６１０フィールドは、ポート６１２および６１４を含み得る。３つのＩＰ宛先サブネット（たとえば、６０４、６０６、および６０８）ならびに２つのＴＣＰ宛先ポート値（たとえば、６１２、６１４）は、ワイルドカード化されたビット列表現を使用して組合せ可能でない。その結果、規則が一致するパケットのセットは、図６（Ｂ）に示されているように、ＩＰ宛先サブネットとＴＣＰ宛先ポート値との各可能な組合せをカバーするために、６つの異なるビット列として表され得る。図６（Ｂ）では、６３０における各ビット列は、ＩＰアドレスとＴＣＰポートとのペア６２２、ＩＰ宛先アドレス６２４「ｉｐ＿ｄｓｔ」、ＴＣＰ宛先ポート６２６「ｔｃｐ＿ｄｓｔ＿ｐｏｒｔ」、および追加のワイルドカード化フィールド６２８を含み得る。その後、これらの６ビットストリング６３０の各々は、追跡演算の結果として異なるビット列を生じる。これらのビット列の各々は、同じデバイス内の次の規則テーブル中で、またはトラフィックが別のデバイスを通して追跡されるとき、さらに多くの一意のビット列を生じ得る。
【００２６】
[00033]図５（Ｂ）は、クロス乗積問題が、単一のデバイス５２０における異なる規則テーブル５２２および５２４にわたっていつ現れるか、規則テーブル中の規則が異なるヘッダフィールドに関していつ一致するかを示す。規則テーブル５２２「ｔａｂｌｅ０」は、規則一致フィールド値５２８および５３０を含み得、規則テーブル５２４「ｔａｂｌｅ１」は、規則一致フィールド値５３４および５３６を含み得る。たとえば、アクセス制御リスト（ＡＣＬ）テーブルは、ＴＣＰ宛先ポートに関して一致し、トラフィックを可能にする規則を含み得、ＩＰルーティングテーブルは、出力ポートにトラフィックを転送するためのＩＰ宛先アドレスに関して一致する。図６（Ａ）に示されている前の例と同様に、３つのＩＰ宛先サブネットおよび２つのＴＣＰ宛先ポートがある場合、パケットの集合がデバイス５２０におけるテーブル５２２および５２４のパイプラインを通して追跡され、一致基準が各規則において適用されるとき、分析は、図６（Ｂ）に示されているように、デバイスから出てくることがあるすべてのパケットを表すために、６つの異なるワイルドカードビット列を生じる。図５（Ａ）に示されている例の場合と同様に、規則テーブルを通して追跡することは、ビット列の数の有意な増加を生じ、これは、パス中の後のデバイスで継続する。
【００２７】
[00034]同様に、図５（Ｃ）に示されているように、クロス乗積問題はまた、ネットワークが、異なるヘッダフィールドに関して一致する規則を含んでいるとき、デバイス５４０および５４２にわたって現れる。たとえば、デバイス５４０は、２つの規則５５０および５５２をもつ規則テーブル５４４を含んでいることがあり、ここで、行為は、ＩＰ宛先アドレスに基づいて出力ポートを設定することである。別のデバイス５４２は、２つの規則５５６および５５８をもつファイアウォール規則テーブル５４６を含んでいることがあり、ここで、行為は、ＴＣＰ宛先ポートに基づいて何らかのトラフィックを阻止することである。デバイス５４０を通して追跡される各パケット集合がデバイス５４２に到達したとき、最終結果は、すべての規則のクロス乗積になる。図５（Ａ）および図５（Ｂ）の例の場合と同様に、規則テーブルを通して追跡することは、ビット列の数の有意な増加を生じ、これは、パス中の後のデバイスで継続する。クロス乗積に関与するデバイスまたはテーブルの数にかかわらず、生じる問題は同じである。
【００２８】
[00035]クロス乗積問題を説明するために、以下のヘッダフィールド値リストについて考える。  
ｍｙ−ｉｐ−ｌｉｓｔ＝［１．２．３．０／２４  １０．２０．３０．０／２４  １００．２００．３００．０／２４．．．］（ｍ個の要素、ここで、ｍ＝１、２、．．．、Ｍ）
ｍｙ−ａｌｌｏｗｅｄ＿ｐｏｒｔｓ＝［８０  ４４３  ２２  ８４４３．．．］（ｎ個の要素、ここで、ｎ＝１、２、．．．、Ｎ）
【００２９】
[00036]これらのリストは、以下のものなど、ＡＣＬ規則を作成するために使用され得る。  
一致＝
ｉｐ＿ｓｒｃ：  ｍｙ−ｉｐ−ｌｉｓｔ；
ｉｐ＿ｄｓｔ：  ｍｙ−ｉｐ−ｌｉｓｔ；
ｉｐ＿ｐｒｏｔｏ＝ＴＣＰ／ＵＤＰ；
ｔｐ＿ｄｓｔ＿ｐｏｒｔ＝ｍｙ−ａｌｌｏｗｅｄ＿ｐｏｒｔｓ；
ｔｐ＿ｓｒｃ＿ｐｏｒｔ＝ｍｙ−ａｌｌｏｗｅｄ＿ｐｏｒｔｓ；
行為＝
可能
【００３０】
[00037]上記のＡＣＬ規則は、一致および対応する行為を用いてパケットのトラフィックフローを定義し、したがって、パケットが、一致によって定義されたパラメータ（たとえば、ｉｐ＿ｓｒｃ、ｉｐ＿ｄｓｔ、ｉｐ＿ｐｒｏｔｏ、ｔｐ＿ｄｓｔ＿ｐｏｒｔ、ｔｐ＿ｓｒｃ＿ｐｏｒｔ）に一致する場合、対応する行為は、パケットが通ることを可能にすることである。各ＩＰフィールドに一致するためのｍ個の要素が存在し得、各ポートに一致するためのｎ個の要素が存在し得る。この構成は、より大きいｍおよびｎの場合、巨大な数の一意のビットストリング規則であり得る、ＡＣＬ規則に一致するパケットを表すために、ｍ2ｎ2個の一意のビット列を必要とする。さらに、各規則が独立して考えられる場合、任意の後の処理段階は、はるかにより多くのビット列を確かめ、余分なＣＰＵ、メモリ、およびディスク使用を生じることになる。
【００３１】
[00038]別の例では、パケット領域が連続的であるとき、ＩＰプレフィックスのグループを表すという状況も、挑戦的であり得る。以下で示されるように、ＩＰテーブルは、３つの別個のネクストホップアドレスＡ、Ｂ、およびＣを含む。  
１０．０．０．０／８−−＞Ａ
１１．０．０．０／８−−＞Ｂ
１２．０．０．０／８−−＞Ｃ
１４．０．０．０／８−−＞Ａ
１５．０．０．０／８−−＞Ｂ
１６．０．０．０／８−−＞Ｃ
【００３２】
[00039]この構成は、同じネクストホップをもつ規則の各グループが不連続であるので、構成された挙動を表すために、６つの一意のビット規則を含み得る。しかしながら、本出願の実施形態によるネットワークモデルは、３つのグループとしてＩＰテーブルを表し得、したがって、後の処理段階における追加の作業は、最低限に低減され得る。
【００３３】
[00040]様々な適用例が、本発明の様々な実施形態の利点から利益を受け得る。たとえば、ネットワークが適切に機能することをソフトウェアコードが可能にすることを検証するために、様々な実施形態によるデータプレーンモデリングが使用され得る。代替的に、生成環境において、ネットワークの現在の挙動を確認するために、または提案される変化の効果をテストするために、データが使用され得る。
【００３４】
[00041]様々な実施形態によれば、ネットワークモデリングシステムは、ネットワークの転送機能を表すための、プロトコル独立型で、ベンダー独立型で、効率的でスケーラブルな抽象化モデルを使用し得る。そのようなモデルは、ネットワークの系統的な分析および検証のために使用され得る。ネットワークモデルは、パケットがネットワーク中のデバイスによってどのように処理されるかを決定するために使用される転送規則を含み得る。いくつかの実施形態では、ネットワークモデルは周期的に更新され得る。いくつかの実施形態では、実際のネットワークの状態が変化するたびに全ネットワークモデルを再計算する代わりに、ネットワークモデルは、関連付けられた変化した転送状態を更新することのみによって増分的に更新され得、これは、規則依存性トラッキングを通して実現され得る。規則依存性トラッキングでは、入力ポートにおけるＶＬＡＮ変化など、状態テーブルに対する個々の更新が、他の無関係の規則の再生成を必要とすることなしに、その入力ポートに一致する規則が更新することを自動的に引き起こす。次いで、更新された規則のリストは、ネットワーク中の影響を受けたトラフィッククラスおよびパスのモデリングを更新し、モデルの残りを影響を受けないままにするために使用され得る。
【００３５】
[00042]一実施形態によれば、ネットワークモデリングシステムは、パケットの集合のための効率的な表現を実装することによって、クロス乗積問題に対処し得、ここで、各個々のヘッダフィールドは、そのフィールドについて可能であるワイルドカード化されたビット列値の集合として表される。集合中に含まれるパケットは、表現中のそれぞれのヘッダフィールドについて指定されている値に限定されるヘッダ値をもつパケットである。各フィールドのためのワイルドカード化されたビット列は、そのフィールドの長さと同程度に広いにすぎない。たとえば、図６（Ａ）において定義されているパケットの集合の場合、パケット集合は、すべてのＩＰ宛先値６０２を含んでいる単一のエントリと、すべてのＴＣＰ宛先ポート６１０を含んでいる別のエントリとによって表され得る。数学演算が、次いで、個々のワイルドカード化されたビット列に対してではなく、全パケット集合に対して実施され得る。これらの演算を実施する間、それらの多くは、パケット中のすべてのヘッダフィールドをカバーする長いワイルドカード化されたビット列を計算するためにクロス乗積を列挙することを必要としない。演算は、全体的なパケット集合表現に対して、または特定のヘッダフィールドのための値のセットに対して直接演算し得る。その結果、様々な実施形態によるネットワークモデリングシステムは、ＣＰＵ、メモリ、ディスク使用コストの有意な改善によって利益を与えられ得る。
【００３６】
[00043]一実施形態では、図６（Ｃ）に示されているように、ネットワークモデリングシステムは、グループとしてパケットヘッダ値を表し得、たとえば、表現６６０は、ＩＰアドレス６６８、６７０および６７２をグループ化するためにＩＰ宛先６６２「ｉｐ＿ｄｓｔ」を、ならびにポートｐ１およびｐ２をグループ化するためにＴＣＰ宛先ポート６６４を含み得る。図に示されていない、指定されていないヘッダ値は、暗黙的にワイルドカード化されると仮定され得、それらを表すためにストレージは使用されない。このようにして、様々な実施形態によれば、単一の記述が、パケットの多くの組合せを表し、改善された効率およびスケーラビリティをもつネットワークモデルをもたらすことができる。この表現は、そのうえ、クロス乗積規則問題、ならびに大きいインターネットルーティングテーブルからトラフィックを効率的に表すことができないことなど、ビットストリング表現に伴う問題を回避し得る。表現６６０はまた、より少数のビット列が必要とされるので、および特定のヘッダフィールドのためのビット列が、他のヘッダフィールドのビット列値との各可能な組合せ（クロス乗積）について１回記憶され、繰り返されないので、いくつかのヘッダフィールドが完全にワイルドカード化されたとき、より空間効率的であり得る。
【００３７】
[00044]いくつかの実施形態では、パケット集合表現中で使用されるフィールドは、パケット転送のために一般に使用されるよく知られているヘッダフィールドに対応しないことがある。たとえば、入口点またはトラフィックのクラスを示すために、カスタムタグがネットワーク内に追加され得る。このカスタムタグは、パケット集合中に含まれ得る。ネットワークモデルはまた、モデルに関連付けられたパケットの何らかの分類を示すために、仮想フィールドのそれ自体のセットを導入し得る。
【００３８】
[00045]ワイルドカードを用いてパケット集合を表すことに関連付けられた課題があり得るが、本発明の実施形態は、これらの課題を克服し、追加の利点を与える。たとえば、どのパケットが規則に一致するかを分析すること、または２つのパケット集合を組み合わせることなど、数学演算が、パケット集合に対して実施され得る。様々な実施形態によれば、これらの数学演算が実行されたとき、得られた出力は、ヘッダフィールドにわたる値のすべてのクロス乗積が結果に含まれるべきであるという性質を満たす形式で表され得る。代替的に、表現は、どのパケットがクロス乗積から除外されるかを示すことが可能であり得る。別の例では、様々な実施形態によるネットワークモデリングシステムは、ヘッダ値の集合が交差するまたは組み合わせ得る多数のやり方にもかかわらず、組合せ演算および書換え演算を含む、各演算を正しく実装し得る。
【００３９】
[00046]様々な実施形態によれば、パケット集合表現は、汎用プロセッサまたはグラフィックスプロセッサなど、任意のコンピューティングハードウェア上で、Ｊａｖａ（登録商標）、Ｃ＋＋、Ｃ＃、または任意の好適なプログラミング言語で実装され得る。いくつかの実施形態では、本発明は、フィールドプログラマブルゲートアレイまたは特定用途向け集積回路を介して、ハードウェアで直接実装され得る。
【００４０】
[00047]図７は、様々な実施形態による、ネットワークモデリングシステム中でパケットを処理および分析する例示的な方法７００を示すブロック流れ図である。様々な実施形態によるネットワーキングデバイスは、図１に示されている規則テーブルなど、各規則テーブルが規則のリストを含み、各規則が一致と行為の集合とを含む規則テーブルの集合としてモデル化され得る。ステップ７０２において、ネットワークモデリングシステムは、図１に示されているネットワークなど、ネットワーク上のネットワークデバイスに関連付けられたネットワーク情報を取得し得る。ネットワーク情報は、サードパーティエンティティから取得されるか、またはネットワーク中のネットワークデバイスから収集され得る。図１に示されているように、各ネットワークデバイスは、ネットワーク内のパケットのための転送挙動について記述する１つまたは複数の規則テーブルを含み得る。各規則テーブルは規則のセットを含み得、ここで、規則は、特定の順序でまたは任意の順序（たとえば、無順序）で適用され得る。いくつかの実施形態では、規則は、暗黙的または明示的であり得る。各規則は、一致指定子と、対応する行為とから構成され、したがって、パケットまたはパケットのグループが一致指定子に一致するとき、規則はパケットに適用され、対応する行為は実施される。ネットワーク中の各デバイスの規則テーブル中に定義されている転送挙動は、まとめて、ネットワークのトラフィックフローを引き起こし、定義し得る。
【００４１】
[00048]７０４において、ネットワークモデリングシステムは、ネットワークモデル中で分析すべきパケットのグループを識別し得る。一実施形態では、パケットのグループは、ネットワークに入るとき、または特定のデバイスまたはポートにおいてネットワークに到着するとき、識別され得る。パケットのグループを識別することは、取得されたネットワーク情報に少なくとも部分的に基づき得、ここで、ネットワーク情報は、少なくとも、１つまたは複数の規則テーブルとネットワークトポロジーとを含む。いくつかの実施形態では、パケットのグループは、ネットワーク分析システム中で集合パケットをトラブルシューティングすることについて取得された情報に基づいて識別され得る。
【００４２】
[00049]７０６において、ネットワークモデリングシステムは、次いで、識別されたパケットのグループまたは集合を表すために、仮想パケットヘッダを作成し得る。仮想パケットヘッダは、パケットの集合を表すために、様々な実施形態によるワイルドカード化されたビットを含み得る。仮想パケットヘッダは、１つまたは複数のパケットヘッダグループを含み得、ここで、１つまたは複数のパケットヘッダグループのうちの少なくとも１つは、２つまたはそれ以上のパケットヘッダ値の和集合（union）を表す。
【００４３】
[00050]仮想パケットヘッダは、次いで、７０８において、ネットワーク挙動をシミュレートするために、ネットワークモデルを通してプッシュされる。仮想パケットヘッダがネットワークを通してプッシュされるとき、仮想パケットヘッダは、たとえば図１に示されているように、ネットワークデバイスに入り得る。仮想パケットヘッダがネットワークデバイスに入るとき、ネットワークデバイスの規則テーブルは、仮想パケットヘッダに適用され得る。規則一致は、この規則がそれに適用され、ＨＲｅｇｉｏｎとして表され得るパケットの集合を決定する。７１０において、パケットの集合中の値を一致指定子中で指定されている値と比較することによって、規則一致が生じる。パケットの集合が、この領域に属し、この規則に一致する場合、その規則中で指定されている対応する行為が、パケットのその集合に適用される。規則テーブル内で、規則（たとえば、一致および対応する行為）は、特定の順序で、または任意の順序で処理され得る。規則は、規則テーブル中で明示的であるか、または暗黙的であり得る。規則の対応する行為は、明示的または暗黙的であり、少なくとも１つのパケットヘッダ値を変化させる、仮想パケットヘッダに対して実施される任意の演算であり得る変換を含み得る。いくつかの実施形態では、規則テーブルは暗黙的であり得る。７１２において、ネットワークモデリングシステムは、次いで、ネットワークモデルを通した仮想パケットヘッダの挙動に基づいて、ネットワーク中を進むパケットのフローパスを決定し得る。
【００４４】
[00051]一実施形態において、ネットワークモデリングシステムは、集合を表すために仮想パケットヘッダを使用することによって、パケット集合をモデル化し得る。仮想パケットヘッダは、定義されたプロトコル上でヘッダフィールドの和集合を指定する。たとえば、この仮想パケットヘッダは、ＩＰｖ４パケットとＩＰｖ６パケットの両方のヘッダ中に存在するフィールドを含み得る。ＩＰｖ４パケットを表すときに、仮想パケットヘッダは、ＩＰｖ６のような他のプロトコルに関係するすべてのビットをワイルドカード化し得る。仮想パケットヘッダ中の各フィールドは、フィールドＩＤと呼ばれる、対応する一意の識別子を有する。したがって、仮想パケットヘッダは、パケットヘッダ値としてワイルドカードを使用することによって、パケットまたはパケットのクラスを識別し得る。そうすることによって、仮想パケットヘッダは、各々が個々に処理されなければならなかった場合、仮想パケットヘッダによって表されるパケットのグループ中の各個々のパケットヘッダの和よりも小さい全体的なビットサイズを有し得る。
【００４５】
[00052]所与のパケットについて、多くのフィールドが完全にワイルドカード化され得る。｛０，１，ｘ｝ビットのシーケンスを使用してパケット集合を表す代わりに、様々な実施形態によるネットワークモデリングシステムは、フィールドＩＤの集合とそれらの対応する値とからなるスパース表現を使用し得る。この集合中に存在しないフィールドは、完全にワイルドカード化されたと仮定され得る（すなわち、すべてのビットは「ｘ」値で表される）。各フィールドの値は、できる限りワイルドカード化された値の集合である。たとえば、仮想パケットヘッダは３つのフィールド、すなわち、ｆ１、ｆ２、およびｆ３を含み得、これらのフィールドの各々は４ビットを含み得る。この例では、例示的なパケット集合は、以下のコンパクトな表現を使用して表され得る。  
（ｆ１，｛「００００」｝），（ｆ３，｛「０００１」，「００ｘ０」｝）｝
【００４６】
[00053]上記のコンパクトな表現は以下と等価である。  
｛「００００，ｘｘｘｘ，０００１」，「００００，ｘｘｘｘ，００ｘ０」｝
【００４７】
[00054]上記の第１の値（「００００，ｘｘｘｘ，０００１」）は、４つのワイルドカード化されたビットを含み、したがって、１６個の別個の値を表す。同様に、第２の値（「００００，ｘｘｘｘ，００ｘ０」）は、５つのワイルドカード化されたビットを含み、したがって、３２個の別個の値を表す。その結果、コンパクトな表現は、この例では、４８個のパケットを表す。
【００４８】
[00055]本発明の実施形態は、｛０，１，ｘ｝中の３つの値のうちの１つを有することができるビットを指すために、ヘッダビット（「ＨＢｉｔ」）を使用し得る。これらＨｂｉｔのシーケンスは、ヘッダシーケンス（「ＨＳｅｑ」）と呼ばれることがある。たとえば、上記の例中の「００ｘ０」はＨＳｅｑである。ヘッダフィールドの値は、ヘッダシーケンス集合（「ＨＳｅｑＣｏｌｌｅｃｔｉｏｎ」）と呼ばれることがあるＨＳｅｑのセット、たとえば、「｛「０００１」，「００ｘ０」｝」として表され得る。上記の例の場合のように、ヘッダフィールドの集合およびそれらの対応する値は、不連続領域を表し得る。実施形態は、そのような領域、たとえば、「｛（ｆ１，｛「００００」｝），（ｆ３，｛「０００１」，「００ｘ０」｝）｝」を指すために、ヘッダ領域（「ＨＲｅｇｉｏｎ」）を使用し得る。この記法では、Ｈｒｅｇｉｏｎは、パケットフィールドからＨＳｅｑＣｏｌｌｅｃｔｉｏｎへのマップである。パケットフィールドがＨｒｅｇｉｏｎ中で完全にワイルドカード化された場合、パケットフィールドは、対応するマップ中にエントリを有しないことになる。言い換えれば、このマップ中でのパケットフィールドのためのエントリの不在は、フィールドが完全にワイルドカード化されたことを示す。
【００４９】
[00056]パケットの集合は、一実施形態では、たとえば、図４に示されているように、パケットの集合が、規則テーブルをもつネットワークデバイスに入ったとき、ｉｎｐｕｔ＿ｒｅｇｉｏｎ（ＨＲｅｇｉｏｎ）によって表され得る。規則テーブルは、［ｒ１，ｒ２，ｒ３］など、規則のセットを含んでいることがあり、各規則は、［ｍａｔｃｈ１，ｍａｔｃｈ２，ｍａｔｃｈ３］など、それぞれの一致を有し得る。ｒ１に一致するｉｎｐｕｔ＿ｒｅｇｉｏｎの部分を見つけるために、様々な実施形態によるネットワークモデリングシステムは、ｉｎｐｕｔ＿ｒｅｇｉｏｎとｍａｔｃｈ１との交差を決定し得る。ＨＲｅｇｉｏｎの交差が、本出願においてさらにより詳細に説明される。次いで、ｉｎｐｕｔ＿ｒｅｇｉｏｎ中にあるが、ｍａｔｃｈ１でないパケットの集合は、次の（１つまたは複数の）規則に繰り越され得る。
【００５０】
[00057]単一のＨＲｅｇｉｏｎとしてモデル化可能でないことがある、次の規則に繰り越されるもののようなパケット集合を表すために、様々な実施形態に従って、ネットワークモデリングシステムは、ヘッダ表現（「ＨＥｘｐｒ」）を定義し得る。ＨＥｘｐｒは、他のＨＲｅｇｉｏｎの集合の和集合を引いたＨＲｅｇｉｏｎを表し得る。言い換えれば、ＨＥｘｐｒは、「第１のパケット集合」と１つまたは複数の「他のパケット集合」との間の差を表す。例示のために、上記の例では、（「ｈｓｅ１」と呼ばれる）「ｉｎｐｕｔ＿ｒｅｇｉｏｎ−｛ｍａｔｃｈ１｝」は、処理のためにｒ２に送られるパケットの集合を表すＨＥｘｐｒであり得る。この集合中のどのパケットがｒ２を用いて処理される必要があるかを見つけるために、ネットワーキングモデリングシステムは、ＨＲｅｇｉｏｎである、ｈｓｅ１によって表されるパケットとｍａｔｃｈ２によって表されるパケットとの交差を決定し得る。ＨＥｘｐｒとＨＲｅｇｉｏｎとの交差は、規則テーブル中の各規則に入ることができるパケットのグループを追跡するときに呼び出され得る演算である。同様に、（「ｈｓｅ２」と呼ばれる）「ｉｎｐｕｔ＿ｒｅｇｉｏｎ−｛ｍａｔｃｈ１，ｍａｔｃｈ２｝は、規則ｒ３に一致することができるパケットの集合を表すＨＥｘｐｒであり得る。ｈｓｅ２では、様々な実施形態による「ｉｎｐｕｔ＿ｒｅｇｉｏｎ」は、被減数と呼ばれることがあり、「ｍａｔｃｈ１」および「ｍａｔｃｈ２」は、減数と呼ばれることがある。ＨＥｘｐｒとＨＲｅｇｉｏｎとの交差が、本出願においてさらにより詳細に説明される。
【００５１】
[00058]一実施形態では、ネットワーキングモデリングシステムは、パケット集合に対して変換演算を実施し得る。変換演算の前に、（すなわち、ＨＥｘｐｒによって表される）パケット集合は、図４に示されている例の場合のように、ネットワーク上のデバイスの規則テーブルのうちの１つ中の規則に一致し得る。その後、その規則中で指定されている行為が、そのパケット集合に適用され得る（すなわち、変換行為）。これらの行為は、入力ＨＥｘｐｒを出力ＨＥｘｐｒに変換し得る。ＨＥｘｐｒ変換に加えて、規則テーブル中の行為は、パケット集合がどのようにデバイスポートに転送または廃棄されるかを指定することができる。たとえば、デバイスが、特定のポートに到着するパケット集合中のすべてのパケットについて同じ挙動を有するとき、デバイスの挙動は、以下のフォーマットを使用してモデル化され得る。  
（ｉｎｐｕｔＨＥｘｐｒ，ｉｎｐｕｔＰｏｒｔｓ）→（ｏｕｔｐｕｔＨＥｘｐｒ，ｏｕｔｐｕｔＰｏｒｔｓ）
【００５２】
[00059]上記の表現は、「ｉｎｐｕｔＨＥｘｐｒ」によって表されるパケットの集合が「ｉｎｐｕｔＰｏｒｔｓ」によって示されるポートのいずれかに到着したとき、パケットの集合は、「ｏｕｔｐｕｔＨＥｘｐｒ」に変換され、「ｏｕｔｐｕｔＰｏｒｔｓ」に転送されることを示し得る。ＨＥｘｐｒ変換は、書換え行為および移動行為を使用して表され得る。
【００５３】
[00060]ＨＥｘｐｒ変換行為の一例は、ＨＥｘｐｒ中の単一のフィールドの値を別の値に書き換える、書換え行為である。例示のために、以下のＨＥｘｐｒがあり得る。  
｛（ｆ１，｛「００００」｝），（ｆ３，｛「０００１」，「００ｘ０」｝）｝
【００５４】
[00061]このＨＥｘｐｒは、「ｆ１」が｛「０００１」｝と交換されるように書き換えられ得、これは、以下のＨＥｘｐｒを生じる。  
｛（ｆ１，｛「０００１」｝），（ｆ３，｛「０００１」，「００ｘ０」｝）｝
【００５５】
[00062]その後、フィールド「ｆ２」が｛「１１１１」｝に書き換えられ、以下を生じ得る。  
｛（ｆ１，｛「００００」｝），（ｆ２，｛「１１１１」｝），（ｆ３，｛「０００１」，「００ｘ０」｝）｝
【００５６】
[00063]最後に、フィールド「ｆ３」が「ｘｘｘｘ」に書き換えられ得る。「ｆ３」は完全にワイルドカード化された値であるように書き込まれるので、得られた完全に書き換えられたＨＥｘｐｒは、以下の通りである。  
｛（ｆ１，｛「００００」｝）｝
【００５７】
[00064]ＨＥｘｐｒ中のフィールドを書き換えることは、少なくともＨＥｘｐｒの被減数の値を変化させることを伴い得、これは、本出願においてさらにより詳細に説明される。様々な実施形態では、書換え演算は、書き換えられているＨＥｘｐｒが減数を有する、より複雑である場合に実施され得る。多フィールド書換えは、一連の単一フィールド書換え行為と見なされ得る。
【００５８】
[00065]ＨＥｘｐｒ変換はまた、移動行為として表され得る。移動行為は、フィールドの値を別のフィールドに移動する。例示のために、以下のＨＥｘｐｒがあり得る。  
｛（ｆ１，｛「００００」｝），（ｆ３，｛「０００１」，「００ｘ０」｝）｝
【００５９】
[00066]「ｆ１」の値を「ｆ４」に移動することは、以下のＨＥｘｐｒを生じ得る。  
｛（ｆ３，｛「０００１」，「００ｘ０」｝）、（ｆ４，｛「００００」｝）｝
【００６０】
[00067]演算が減数の存在下でどのように実行されるかを含む、フィールドの値を別のＨＥｘｐｒに移動することが、本出願においてさらにより詳細に説明される。
【００６１】
[00068]本出願の別の実施形態では、ネットワークモデリングシステムがパケットに対して実施し得る別の演算は、２つのＨＥｘｐｒを交差させることを含む。ＨＥｘｐｒを交差させることは、規則テーブルを通してパケット集合を追跡するための必要とされる演算であり得る。そのような交差を完了することは、ＨＳｅｑを交差させる能力を必要とし、これは、ＨＢｉｔを交差させる能力を必要とする。
【００６２】
[00069]以下の表が、２つのＨＢｉｔ値を交差させるために使用され得る。
【００６３】
【表１】
2019533373.tif 000003
【００６４】
[00070]パケット集合をモデル化する際の様々な実施形態に従って、ネットワークモデリングシステムがパケットに対して実施し得る別の演算が、２つのヘッダシーケンス（「ＨＳｅｑ」）を交差させており、ここで、ＨＳｅｑは、ＨＢｉｔのシーケンスである。２つのＨＳｅｑは、それらが同じビット数を有する場合、およびその場合のみ、組み合わせられ得る。各位置にある対応するビットが交差され、結果は、得られたＨＳｅｑ中のその位置に配置される。同じ位置にある２つのＨＢｉｔの交差が空である場合、２つのＨＳｅｑも空の交差を有する。例示のために、２つのＨＢｉｔを交差させることの例が以下で概説される。
【００６５】
【表２】
2019533373.tif 000004
【００６６】
[00071]パケット集合をモデル化する際の別の実施形態に従って、ネットワーキングモデリングシステムがパケットに対して実施し得る別の演算が、２つのヘッダシーケンス集合（「ＨＳｅｑＣｏｌｌｅｃｔｉｏｎ」）を交差させており、ここで、ＨＳｅｑＣｏｌｌｅｃｔｉｏｎは、ＨＳｅｑの集合である。ｓ１が第１のＨＳｅｑＣｏｌｌｅｃｔｉｏｎに属し、ｓ２が第２のＨＳｅｑＣｏｌｌｅｃｔｉｏｎに属する、各ＨＳｅｑペア（ｓ１，ｓ２）について、ｓ１とｓ２との交差が、２つのＨＳｅｑを交差させるための同じ技法を使用して開示されたように計算される。この交差の結果が空でない場合、結果は、得られたＨＳｅｑＣｏｌｌｅｃｔｉｏｎに追加される。
【００６７】
[00072]例示のために、以下で示されているように、２つのＨＳｅｑＣｏｌｌｅｃｔｉｏｎがあり得る。  
ｃ１＝｛ｓ１１，ｓ１２｝
ｃ２＝｛ｓ２１，ｓ２２｝
【００６８】
[00073]２つのＨＳｅｑＣｏｌｌｅｃｔｉｏｎの上記の例では、ｓ１１、ｓ１２、ｓ２１、およびｓ２２は、異なるＨＳｅｑを表し得る。これらの２つのＨＳｅｑＣｏｌｌｅｃｔｉｏｎを交差させるために、ＨＳｅｑのすべての可能なペアの交差が、以下で考えられる。  
｛ｓ１１∩ｓ２１，ｓ１１∩ｓ２２，ｓ１２∩ｓ２１，ｓ１２∩ｓ２２｝
【００６９】
[00074]各ペアの交差の結果が空でない場合、結果は、得られたＨＳｅｑＣｏｌｌｅｃｔｉｏｎに追加され得る。
【００７０】
[00075]ネットワークモデリングシステムが、様々な実施形態のための従ってパケットに対して実施し得る別の演算は、交差する２つのヘッダ領域（「ＨＲｅｇｉｏｎ」）を含み、ここで、ＨＲｅｇｉｏｎは、パケットフィールドからＨＳｅｑＣｏｌｌｅｃｔｉｏｎへのマップである。パケットフィールドがＨＲｅｇｉｏｎ中で完全にワイルドカード化された場合、パケットフィールドは、対応するマップ中にエントリを有しないことがある。２つのＨＲｅｇｉｏｎを交差させることは、各フィールドの対応するＨＳｅｑＣｏｌｌｅｃｔｉｏｎ値を交差させることによって実施され得る。パケットフィールドが、ＨＲｅｇｉｏｎのうちの一方のみの中で完全にワイルドカード化される場合、交差結果におけるそれの値は、他方のＨＲｅｇｉｏｎ中の値からもたらされ得る。パケットフィールドが、両方のＨＲｅｇｉｏｎ中で完全にワイルドカード化されない場合、交差結果におけるそれの値は、「２つのＨＳｅｑＣｏｌｌｅｃｔｉｏｎの交差」セクションにおいて説明された方法を使用して計算された２つのＨＲｅｇｉｏｎ中のＨＳｅｑＣｏｌｌｅｃｔｉｏｎ値の交差であり得る。ＨＳｅｑＣｏｌｌｅｃｔｉｏｎのこの交差が空である場合、２つのＨＲｅｇｉｏｎの交差結果も空であり得る。
【００７１】
[00076]別の実施形態では、ネットワークモデリングシステムがパケットに対して実施し得る別の演算は、ＨＥｘｐｒとＨＲｅｇｉｏｎとを交差させることを含む。ＨＥｘｐｒをＨＲｅｇｉｏｎと交差させることの結果は、別のＨＥｘｐｒになり得る。この演算は、規則テーブル中の各規則に入ることができるパケットのグループを追跡するときに呼び出され得る。ＨＥｘｐｒ「ｈｓ」をＨＲｅｇｉｏｎ「ｒ」と交差させるために、最初に、「ｈｓ」の被減数が、２つのＨＲｅｇｉｏｎを交差させるために開示された同じ技法を使用して、「ｒ」と交差される。「ｈｓ」と「ｒ」とのこの交差の結果、すなわち、ＨＲｅｇｉｏｎ「ｎ」は、次いで、結果の被減数になり得る。「ｎ」が空である場合、「ｈｓ」と「ｒ」とを交差させることの結果も空であり得、さもなければ、「ｈｓ」の減数の各々が、２つのＨＲｅｇｉｏｎを交差させるための技法を再び使用して、「ｎ」と交差され得る。
【００７２】
[00077]これらの交差の各々について、以下の場合が適用され得る。結果が空である場合、減数は、それが、得られたＨＥｘｐｒ中に含まれないように無視され得る。結果が「ｎ」に等しい場合、この減数は、結果から「ｎ」のすべてを減算しており、得られたＨＥｘｐｒは空である。この場合、「ｈｓ」と「ｒ」とを交差させることの結果は空であり、他の減数は処理される必要がなく、さもなければ、結果は、得られたＨＥｘｐｒの減数として追加される。
【００７３】
[00078]別の実施形態では、ネットワークモデリングシステムは、２つのＨＥｘｐｒを交差させることを含む別の演算をパケットに対して実施し得る。２つのＨＥｘｐｒ、すなわち、「ｈｓ１」および「ｈｓ２」を交差させるために、最初に、それらの被減数の交差が、２つのＨＲｅｇｉｏｎを交差させるための技法を使用して計算され、結果は「ｍ」と呼ばれることがある。その交差が空である場合、最後の交差結果も空であり得る。さもなければ、「ｈｓ１」および「ｈｓ２」の減数の各々について、その減数の「ｍ」との交差が計算され得る。結果が空である場合、その減数は破棄され得る。結果が「ｍ」に等しい場合、その減数は、被減数中のすべてのデータ点を減算しており、２つのＨＥｘｐｒの交差の結果は空になる。その被減数および減数として「ｍ」をもつＨＥｘｐｒ中の結果は上記の手順を使用して計算されている。
【００７４】
[00079]さらに、様々な実施形態によれば、ネットワークモデリングシステムがパケットに対して実施し得る別の演算は、ＨＥｘｐｒを用いた減数簡略化演算を含む。以下のセクションでは、「組合せ」という用語は、和集合演算を適用し、次いで、結果を簡略化することを試みることを指すことがある。組合せ演算は、ＨＥｘｐｒの減数のセットを、パケットのまったく同じ集合を表すより少数の減数をもつ別のセットに変換することによって、計算の速度を上げるのを助ける。減数の数が低減されるとすれば、このＨＥｘｐｒに対して実施される演算は、より高速に計算され得る。
【００７５】
[00080]時々、減数の組合せは、被減数に等しい単一の減数を生じる。このような場合では、被減数によって表されるあらゆるパケットは、その減数によって除外され得、その結果、このＨＥｘｐｒは空のセットを表す。この場合の減数を組み合わせることは、空のパケット集合を識別するのを助けることができ、そのパケットのグループに対する追跡演算は、早期に停止することができる。関係する演算、すなわち、減数廃棄も、１つまたは複数の減数を含んでいるＨＥｘｐｒが、より少数の減数を用いて、場合によっては、何も減数を用いずに表され得るとき、計算の速度を上げ、メモリ要件を低減するのを助ける。これらの２つの減数簡略化演算は、規則テーブルを通してパケットの集合を追跡するときなど、新しいＨＥｘｐｒを作成するときはいつでも適用される。
【００７６】
[00081]ＨＥｘｐｒが複数の減数を有するとき、それらの減数が組み合わせられる場合、組合せは被減数に等しくなることが可能である。この場合、ＨＥｘｐｒは、空であり、どのパケットにも一致しない。減数を組み合わせることを示すために、以下のＨＥｘｐｒがあり得る。  
被減数＝｛（ｆ１，｛「０００ｘ」｝）｝
減数１＝｛（ｆ１，｛「００００」｝）｝
減数２＝｛（ｆ１，｛「０００１」｝）｝
【００７７】
[00082]この例では、２つの減数は、被減数に等しく、ＨＥｘｐｒが空であることを示す｛（ｆ１，｛「０００ｘ」｝）｝に低減され得る。空のＨＥｘｐｒは、どのパケットもそれに一致できないことを示し、パケットがネットワーク中でどのように搬送されるかをネットワークモデルが記述するとすれば、ネットワークモデリングシステムは、いつ停止すべきかを決定するために、空のＨＥｘｐｒを検出し得る。したがって、新しいＨＥｘｐｒが作成されるときはいつでも、それの減数は、以下で説明される、２つのＨＲｅｇｉｏｎを組み合わせるための技法を使用して、できる限り組み合わせられ、次いで、組み合わせられた減数のいずれかが被減数に等しいかどうかを検査し得る。
【００７８】
[00083]しかしながら、組合せは、一意の出力を必ずしも生じるとは限らない。例示的な例では、以下の３つの減数について考える。  
減数１＝｛（ｆ１，｛「００００」｝）｝
減数２＝｛（ｆ１，｛「０００１」｝）｝
減数３＝｛（ｆ１，｛「００１０」｝）｝
【００７９】
[00084]減数１および減数２は組み合わせられ得る。同様に、減数１および減数３は組み合わせられ得る。しかしながら、減数２および減数３は組み合わせられ得ない。減数１および減数２が組み合わせられた場合、以下が生じる。  
減数ａ＝｛（ｆ１，｛「０００ｘ」｝）｝
減数ｂ＝｛（ｆ１，｛「００１０」｝）｝
【００８０】
[00085]代替的に、減数１および減数３が組み合わせられた場合、結果は以下の通りである。  
減数ｃ＝｛（ｆ１，｛「００ｘ０」｝）｝
減数ｄ＝｛（ｆ１，｛「０００１」｝）｝
【００８１】
[00086]減数の上記の集合のすべては、パケットの同じ集合を表す。様々な実施形態によれば、ネットワークモデルは、ＨＥｘｐｒのための等価表現に依拠せず、空のＨＥｘｐｒを検出するために、減数を組み合わせる必要があるにすぎない。したがって、組合せの非一意の結果は、すべての結果が、パケットの同等の集合を記述するので、正当性に影響を及ぼさない。
【００８２】
[00087]減数が、単一のフィールドのみの中でそれの被減数と異なり、その減数によって減算されない被減数中の値が、ＨＳｅｑＣｏｌｌｅｃｔｉｏｎによって表され得るとき、減数は廃棄され得る。減数を廃棄する際に、その減数は削除され、被減数値はプルーニングされる。たとえば、減数が「｛（ｆ１，｛「００００」｝）｝」であり、被減数が「｛（ｆ１，｛「０００ｘ」｝）｝」であるＨＥｘｐｒについて考える。この場合、「０００ｘ」−「００００」は、ＨＳｅｑＣｏｌｌｅｃｔｉｏｎ、すなわち、「０００１」として表され得るので、減数を廃棄し、被減数を「｛（ｆ１，｛「０００１」｝）｝」に更新することができる。
【００８３】
[00088]ＨＳｅｑはまた、ネットワークモデリングシステムがパケットに対して実施し得る別の演算において組み合わせられ得る。様々な実施形態によれば、ＨＳｅｑ値は、同じパケット集合のよりコンパクトで、したがって、より効率的な表現を達成するために、できる限り組み合わせられ得る。２つのＨＳｅｑは、（１）値が等しい、（２）値のうちの一方が他方を包含する（たとえば、「００ｘｘ」が「００００」を包含する）、または（３）値がただ１つのビット位置において異なるときなど、様々な場合において組み合わせられ得る（たとえば、「００００」と「０００１」とは、単一のビット位置において異なり、「０００ｘ」に組み合わせられ得る）。３つ以上のＨＳｅｑ値を組み合わせるとき、ペアワイズ組合せの代わりに、トライ木のような代替のデータ構造が、最終結果のより効率的な計算のために使用され得る。
【００８４】
[00089]２つのＨＳｅｑＣｏｌｌｅｃｔｉｏｎの組合せはまた、最初にこれらの２つの集合中のすべての値の和集合を作成し、それらをセットに入れることによって呼び出され得る。次いで、このセット中のＨＳｅｑの各ペアについて、２つのＨＳｅｑが、様々な実施形態に従って組み合わせられ得る。２つのＨＳｅｑが１つに組み合わせられ得る場合、２つの値は、和集合から削除され、代わりに、それらの組合せに追加され得る。本出願の実施形態は、それ以上の組合せが可能でなくなるまでこのプロセスを継続することを含む。例示のために、ＨＳｅｑＣｏｌｌｅｃｔｉｏｎへの以下について考える。  
ｃ１＝｛「０００１」，「００ｘ０」｝
ｃ２＝｛「００１０」，「１０００」｝
【００８５】
[00090]値の和集合は以下の通りである。  
｛「０００１」，「００ｘ０」，「００１０」，「１０００」｝
【００８６】
[00091]しかしながら、この和集合では、第２の値と第３の値とは、様々な実施形態に従って２つのＨＳｅｑを組み合わせることによって組み合わせられ得る。この特定の場合では、第２の値は第３の値を包含する。したがって、得られた和集合は以下の通りである。  
｛「０００１」，「００ｘ０」，「１０００」｝
【００８７】
[00092]上述のように、様々な実施形態によれば、ネットワークモデリングシステムがパケットに対して実施し得る別の演算は、２つのＨＲｅｇｉｏｎの組合せを含む。２つのＨＲｅｇｉｏｎは、それらが多くとも１つのフィールドの値が異なる場合のみ組み合わせられ得る。たとえば、以下の２つの領域について考える。  
ｒ１＝｛（ｆ１，｛「００００」｝），（ｆ３，｛「００００」｝）｝
ｒ２＝｛（ｆ１，｛「００００」｝），（ｆ３，｛「０００１」，「１０００」｝）｝
【００８８】
[00093]これらの２つの領域は、フィールドｆ３の値が異なるにすぎず、以下の単一の領域に組み合わせられ得る。  
組合せ＝｛（ｆ１，｛「００００」｝），（ｆ３，｛「０００ｘ」，「１０００」｝）｝
【００８９】
[00094]２つのＨＲｅｇｉｏｎを組み合わせることは、２つのＨＲｅｇｉｏｎが異なる単一のフィールドに対応するＨＳｅｑＣｏｌｌｅｃｔｉｏｎ値を組み合わせるために２つのＨＳｅｑＣｏｌｌｅｃｔｉｏｎを組み合わせ、次いで、他のフィールドに対応する値をコピーするための説明された技法を使用して実施され得る。
【００９０】
[00095]別の実施形態によれば、ＨＲｅｇｉｏｎをＨＥｘｐｒから減算することは、ネットワークモデリングシステムによってパケット集合に対して実施される演算でもあり得る。最初に、与えられたＨＲｅｇｉｏｎが、ＨＥｘｐｒの被減数と交差される。得られたＨＲｅｇｉｏｎは、与えられたＨＥｘｐｒから減算されるべき実際の領域であり得る。この領域は、新しい減数として追加され得る。しかしながら、ＨＥｘｐｒを用いた減数簡略化演算では、ＨＲｅｇｉｏｎは、最初に、他の減数と、新しい減数としてそれを追加する前に組み合わせられ得る。組合せの後に、減数のいずれかが被減数に等しくなる場合、結果ＨＥｘｐｒは空であり得る。例示的な例として、以下のＨＥｘｐｒについて考える。  
被減数＝｛（ｆ１，｛「０００ｘ」｝）｝
減数１＝｛（ｆ１，｛「００００」｝）｝
【００９１】
[00096]｛（ｆ１，｛「００１０」｝）｝ＨＲｅｇｉｏｎをＨＥｘｐｒから減算することは、以下を生じる（すなわち、ＨＲｅｇｉｏｎは、単に、新しい減数として追加される）。  
被減数＝｛（ｆ１，｛「０００ｘ」｝）｝
減数１＝｛（ｆ１，｛「００００」｝）｝
減数２＝｛（ｆ１，｛「００１０」｝）｝
【００９２】
[00097]しかしながら、｛（ｆ１，｛「０００１」｝）｝をＨＥｘｐｒから減算することは、以下で示されるように、空のＨＥｘｐｒを生じる。  
被減数＝｛（ｆ１，｛「０００ｘ」｝）｝
減数１＝｛（ｆ１，｛「００００」｝）｝
減数２＝｛（ｆ１，｛「０００１」｝）｝
【００９３】
[00098]２つの減数は、以下の形式に組み合わせられ得る。  
被減数＝｛（ｆ１，｛「０００ｘ」｝）｝
減数１＝｛（ｆ１，｛「０００ｘ」｝）｝
【００９４】
[00099]その後、この場合、減数のうちの１つが被減数に等しいＨＥｘｐｒがある。したがって、すべての可能なパケットが被減数から除外され、何も残らない。
【００９５】
[000100]ＨＲｅｇｉｏｎ中のフィールドを書き換える際に、フィールドの値は、単に、新しい値に変化され得る。たとえば、以下のフィールドｆ１の値をＨＲｅｇｉｏｎ中のＨＳｅｑＣｏｌｌｅｃｔｉｏｎ｛「００００」｝に書き換えることは、  
｛（ｆ１，｛「０００１」，「００１０」｝），（ｆ３，｛「００００」｝）｝
【００９６】
[000101]以下のＨＲｅｇｉｏｎを生じる。  
｛（ｆ１，｛「００００」｝），（ｆ３，｛「００００」｝）｝
【００９７】
[000102]ＨＥｘｐｒ中のフィールドも、ネットワークモデリングシステムがパケットに対して実施し得る別の演算において書き換えられ得る。ＨＥｘｐｒ中のフィールド「ｆ」を書き換えるために、最初に、ＨＥｘｐｒの被減数が、ＨＲｅｇｉｏｎのフィールドを書き換えるための技法を使用して書き換えられる。この被減数書換えステップは、減数の数および形式が変動する様々な実施形態に適用され得る。たとえば、ＨＥｘｐｒのみが被減数を含んでいる場合、フィールドの書換えは完了している。代替的に、減数が存在する場合があり得る。
【００９８】
[000103]第１の場合は、フィールドｆ１、すなわち、書き換えられるべきフィールドの値が、被減数と各減数との間で同じである場合である。この場合、値は、各減数中のフィールドｆ１について書き換えられ得る。例示のために、以下のこのＨＥｘｐｒについて考える。  
被減数＝｛（ｆ１，｛ａ，ｂ｝）｝
減数１＝｛（ｆ１，｛ａ，ｂ｝），（ｆ２，｛ｚ｝）｝
【００９９】
[000104]被減数は、フィールドｆ１のための複数の値、すなわち、ａとｂとを含んでいる。代替の表現は、以下で示されるように、フィールドｆ１の各値について１つのＨＥｘｐｒを生成し、それらの和集合をとるものになる。  
被減数＝｛（ｆ１，｛ａ｝）｝
減数１＝｛（ｆ１，｛ａ，ｂ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｂ｝）｝
減数１＝｛（ｆ１，｛ａ，ｂ｝），（ｆ２，｛ｚ｝）｝
【０１００】
[000105]各ＨＥｘｐｒ中に、被減数との交差を有しない減数値がある。これらの場合、その非交差減数値は削除され得る。したがって、表現は以下に低減され得る。  
被減数＝｛（ｆ１，｛ａ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｂ｝）｝
減数１＝｛（ｆ１，｛ｂ｝），（ｆ２，｛ｚ｝）｝
【０１０１】
[000106]フィールドｆ１を値ｄに書き換えることの結果は、以下によって示され得る。  
被減数＝｛（ｆ１，｛ｄ｝）｝
減数１＝｛（ｆ１，｛ｄ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｄ｝）｝
減数１＝｛（ｆ１，｛ｄ｝），（ｆ２，｛ｚ｝）｝
【０１０２】
[000107]この結果は、以下で示されるように、和集合の両方の部分が同等であるので、単一のＨＥｘｐｒに簡略化され得る。  
被減数＝｛（ｆ１，｛ｄ｝）｝
減数１＝｛（ｆ１，｛ｄ｝），（ｆ２，｛ｚ｝）｝
【０１０３】
[000108]上記のように、この例では、ｆ１の各フィールド値は、複数のフィールド値があるときでも、ｄと交換され得る。しかしながら、フィールド値が異なる例では、これらの場合を扱うことは、より多くの注意を必要とする。
【０１０４】
[000109]別の実施形態では、（書き換えられるべき）フィールドｆ１のための値が被減数と１つの減数との間で異なる別の例について考える。例示のために、以下のこのＨＥｘｐｒの例について考える。  
被減数＝｛（ｆ１，｛ａ，ｂ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
【０１０５】
[000110]このＨＥｘｐｒのための代替の表現は、以下によって示され得る。  
被減数＝｛（ｆ１，｛ａ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｂ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
【０１０６】
[000111]第２のＨＥｘｐｒについて、減数１は、それが被減数との交差を有しないので、削除され、以下を生じ得る。  
被減数＝｛（ｆ１，｛ａ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｂ｝）｝
【０１０７】
[000112]フィールドｆ１をｄに書き換えることの結果は、以下の通りになる。  
被減数＝｛（ｆ１，｛ｄ｝）｝
減数１＝｛（ｆ１，｛ｄ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｄ｝）｝
【０１０８】
[000113]この場合、第２のＨＥｘｐｒは、第１のＨＥｘｐｒを包含し、以下を生じる。  
被減数＝｛（ｆ１，｛ｄ｝）｝
【０１０９】
[000114]この例では、単一の減数上のフィールドｆ１（すなわち、書き換えられるべきフィールド）の値が、被減数上のそのフィールドの値とは異なる場合、減数は、書換えを実施するときに破棄され得る。
【０１１０】
[000115]第３の場合では、ＨＥｘｐｒが２つまたはそれ以上の減数を含んでおり、各減数が、被減数とは異なるフィールドｆ１のための値を有するというさらなる複雑さがあり得る。課題は、各減数が被減数の部分を削除するが、非削除部分の交差が考慮されなければならないことである。例示のために、以下のこのＨＥｘｐｒについて考える。  
被減数＝｛（ｆ１，｛ａ，ｂ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
減数２＝｛（ｆ１，｛ｂ｝），（ｆ３，｛ｗ｝）｝
【０１１１】
[000116]これを代替の和集合形式で表現することは、以下を生じる。  
被減数＝｛（ｆ１，｛ａ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
減数２＝｛（ｆ１，｛ｂ｝），（ｆ３，｛ｗ｝）｝
∪
被減数＝｛（ｆ１，｛ｂ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
減数２＝｛（ｆ１，｛ｂ｝），（ｆ３，｛ｗ｝）｝
【０１１２】
[000117]減数がフィールドｆ１について被減数値との交差を有しない場合、それらは削除され得る。各ＨＥｘｐｒは、１つのそのような削除可能な減数を含んでいる。結果は以下の通りである。  
被減数＝｛（ｆ１，｛ａ｝）｝
減数１＝｛（ｆ１，｛ａ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｂ｝）｝
減数２＝｛（ｆ１，｛ｂ｝），（ｆ３，｛ｗ｝）｝
【０１１３】
[000118]次に、フィールドｆ１の値が、ｄを用いて書き換えられ得る。  
被減数＝｛（ｆ１，｛ｄ｝）｝
減数１＝｛（ｆ１，｛ｄ｝），（ｆ２，｛ｚ｝）｝
∪
被減数＝｛（ｆ１，｛ｄ｝）｝
減数２＝｛（ｆ１，｛ｄ｝），（ｆ３，｛ｗ｝）｝
【０１１４】
[000119]しかしながら、これらの２つの残りの減数は、残っている交差部分があるので、それらの被減数が同じであっても、単に直接、単一のＨＥｘｐｒに組み合わせられないことがある。したがって、上記の和集合形式ＨＥｘｐｒの正しい単一のＨＥｘｐｒ形式は、以下の通りである。  
被減数＝｛（ｆ１，｛ｄ｝）｝
減数１＝｛（ｆ１，｛ｄ｝），（ｆ２，｛ｚ｝），（ｆ３，｛ｗ｝）｝
【０１１５】
[000120]この新しい減数は、上記の和集合形式ＨＥｘｐｒ中の２つの減数の間で共有される被減数の部分を削除する。様々な実施形態によれば、ネットワークモデリングシステムは、任意の数の減数をもつＨＥｘｐｒについて、この単数の得られた減数を自動的に計算し得る。被減数とは異なるフィールドｆ１のための値を有する各減数は、計算における入力として働き得る。
【０１１６】
[000121]そのような減数の各ペアについて、新しい減数が生成され得る。この新しい減数では、フィールド「ｆ１」のための値は、２つの元の減数中の値の組合せであり、ここで、組合せは、ＨＳｅｑＣｏｌｌｅｃｔｉｏｎを組み合わせるために説明する技法によって計算される。各他のフィールドのための値は、２つの元の減数中の対応するフィールド値の交差から計算される。各非「ｆ１」フィールドの交差が空でない場合、この減数は追加されるべきであり、次のステップに移る。しかしながら、交差が空の場合、減数は保留中のＨＥｘｐｒに追加されない。
【０１１７】
[000122]様々な実施形態によれば、「中間」減数のリストを用いて、プロセスは繰り返され得る。たとえば、新たにマージされたペアが被減数と同じフィールドｆ１のための値を有するか、または減数のリストがさらに低減され得ないのいずれかまで、残りの減数のペアをマージする。例示のために、以下の例示的なＨＥｘｐｒについて考える。  
被減数＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝）｝
減数１＝｛（ｆ１，｛「０００１」｝），（ｆ２，｛「０００１」，「００１０」｝）｝
減数２＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝），（ｆ２，｛「１０００」｝）｝
減数３＝｛（ｆ１，｛「０１００」｝），（ｆ２，｛「０００１」，「０１００」｝）｝
減数４＝｛（ｆ１，｛「００１０」｝），（ｆ２，｛「０００１」，「００１０」，「０１００」｝）｝
【０１１８】
[000123]「ｆ１」の値が「１０００」に書き換えられ得る。最初に、被減数が以下のように書き込まれ得る。  
新しい被減数＝｛（ｆ１，｛「１０００」｝）｝
【０１１９】
[000124]減数の集合からの、減数２のみが「ｆ１」に関して元の被減数と同じ値を有する。その後、その減数は、それの「ｆ１」フィールドを書き換えた後に追加され得る。フィールド「ｆ１」の値が被減数とは異なる３つの減数が残っている。新しい減数が、残りの減数のこのセット中の値の各可能なペアに基づいて追加され得る。各新しい潜在的な減数について、「ｆ１」フィールド値は、２つの入力「ｆ１」値の組合せによってもたらされ、各非「ｆ１」フィールドのための値は、２つの入力非「ｆ１」値の交差によってもたらされる。例示のために、以下の例について考える。  
減数（１，３）＝｛（ｆ１，｛「０００１」，「０１００」｝），（ｆ２，｛「０００１」｝）｝
減数（１，４）＝｛（ｆ１，｛「０００１」，「００１０」｝），（ｆ２，｛「０００１」，「００１０」｝）｝
減数（３，４）＝｛（ｆ１，｛「００１０」，「０１００」｝），（ｆ２，｛「０００１」，「０１００」｝）｝
【０１２０】
[000125]これらの新しい潜在的な減数のいずれも、ｆ１について元の被減数と同じ値を有しない。しかしながら、それらは依然としてさらにマージされ得る。減数ペア（１，３）および（１，４）をマージすることは、以下を生じる。  
減数（１，３）＋（１，４）＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝），（ｆ２，｛「０００１」｝）｝
減数（３，４）＝｛（ｆ１，｛「００１０」，「０１００」｝），（ｆ２，｛「０００１」，「０１００」｝）｝
【０１２１】
[000126]これらの２つの減数をマージすることは、以下の単一の減数を生じる。  
減数（１，３）＋（１，４）＋（３，４）＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝）、（ｆ２，｛「０００１」｝）｝
【０１２２】
[000127]次に、この簡略化された減数は追加され得る。得られたＨＥｘｐｒは、以下の２つの減数を含んでいる。  
減数１＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝），（ｆ２，｛「１０００」｝）｝
減数２＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝），（ｆ２，｛「０００１」｝）｝
【０１２３】
[000128]これらの２つの減数は、ＨＥｘｐｒを用いた減数簡略化演算で説明された技法を使用して組み合わせられ、以下の単一の減数を生じることができる。  
減数＝｛（ｆ１，｛「０００１」，「００１０」，「０１００」｝）、（ｆ２，｛「０００１」，「１０００」｝）｝
【０１２４】
[000129]次いで、フィールドｆ１は書き換えられ、以下の「最終」ＨＥｘｐｒを生じ得る。  
被減数＝｛（ｆ１，｛「１０００」｝）｝
減数＝｛（ｆ１，｛「１０００」｝），（ｆ２，｛「０００１」，「１０００」｝）｝
【０１２５】
[000130]様々な実施形態に従ってパケットに対して実施され得る別の行為は、フィールドの値をＨＲｅｇｉｏｎ中の別のフィールドに移動することを含み得る。ソースフィールドとターゲットフィールドとのペアを仮定すれば、この行為は、ソースフィールドの値をターゲットフィールドに移動する。この演算は、完全にワイルドカード化されたＨＳｅｑＣｏｌｌｅｃｔｉｏｎを用いてソースフィールドを書き換え、ソースフィールドの古い値を用いてターゲットフィールドを書き換えることと等価である。例示のために、以下のＨＲｅｇｉｏｎについて考える。  
｛（ｆ１，｛「０００１」，「００１０」｝），（ｆ３，｛「００００」｝）｝
【０１２６】
[000131]ｆ１の値をｆ２に移動することは、以下を生じる。  
｛（ｆ２，｛「０００１」，「００１０」｝），（ｆ３，｛「００００」｝）｝
【０１２７】
[000132]ｆ１の値をｆ３に移動することは、以下を生じる。  
｛（ｆ３，｛「０００１」，「００１０」｝）｝
【０１２８】
[000133]様々な実施形態に従ってパケットに対して実施され得る別の行為は、フィールドの値をＨＥｘｐｒ中の別のフィールドに移動することを含み得る。ＨＥｘｐｒ「ｈｓ」中でフィールド「ｓ」の値をフィールド「ｔ」に移動するために、フィールド「ｓ」の第１の値が、ＨＲｅｇｉｏｎ中でフィールドの値を別のフィールドに移動するために説明された技法を使用して、「ｈｓ」の被減数中のフィールド「ｔ」に移動され得る。得られたＨＲｅｇｉｏｎは、結果ＨＥｘｐｒの被減数である。このシフトは、結果ＨＥｘｐｒの減数を計算するために、「ｈｓ」の減数の各々に対して同様に実施され得る。しかしながら、減数のうちのいくつかは、この演算の一部として破棄されるべきである。例示のために、以下のＨＥｘｐｒについて考える。  
被減数＝｛（ｆ２，｛「１０ｘｘ」｝）｝
減数１＝｛（ｆ１，｛「０００１」｝）
減数２＝｛（ｆ２，｛「００００」｝）
【０１２９】
[000134]フィールドｆ２の値をフィールドｆ１に移動するとき、第１の減数は、それが、新しい値に書き換えられていない領域を被減数から減算していたので、破棄されるべきである。第２の減数は、ターゲットフィールド（ｆ１）のためのエントリを有しないことがあり、最終結果において保持されるべきである。それの値を移動する必要があるにすぎない。この手順は、以下のＨＥｘｐｒを生じる。  
被減数＝｛（ｆ１，｛「１０ｘｘ」｝）｝
減数＝｛（ｆ１，｛「００００」｝）
【０１３０】
[000135]表現は、汎用プロセッサまたはグラフィックスプロセッサなど、任意のコンピューティングハードウェア上で、Ｊａｖａ、Ｃ＋＋、Ｃ＃、または任意の好適なプログラミング言語で実装され得る。いくつかの実施形態では、本発明は、フィールドプログラマブルゲートアレイまたは特定用途向け集積回路を介して、ハードウェアで直接実装され得る。
【０１３１】
[000136]本発明の実施形態は、重複一致フィールドを有する同じまたは異なるテーブル内の規則を検出し、これをユーザに提示するためのシステムおよび方法を提供する。さらに、ネットワークモデリングシステムは、所与の入力規則に関係する同じまたは異なるテーブル内の規則を、それらに一致するパケットが、所与の規則によっても一致されることになるように検出することを可能にされ得る。また、同じ一致優先度、および一致フィールド中のある程度の重複または完全な重複を有することによりあいまいである規則が、同じまたは異なるテーブル内で検出され得る。
【０１３２】
[000137]本発明の実施形態は、より一般的に規則およびネットワークを分析し、規則の消去、規則への変更、または他の規則の追加など、最適化のための示唆を与えるためのシステムおよび方法を提供する。さらに、様々な実施形態によるネットワーキングモデリングシステムは、それらをどのように決定すべきかに関してユーザに示唆を与え得る。これらの問題は、ネットワーク検査、クエリ、または他の性能、最適化によって検出されたもの、あるいは正当性関係問題を含む。本発明はまた、そのような問題を解決するために、変化を自動的に適用し得る。
【０１３３】
[000138]図８は、本発明の一実施形態による、コンピュータシステムの高レベルブロック図８００である。図８に示されているように、コンピュータシステムは、コンピュータシステムが、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、モバイルネットワーク（たとえば、ＥＤＧＥ、３Ｇ、４Ｇ、または他のモバイルネットワーク）、あるいは他のネットワーク上で他のコンピュータシステムに接続することを可能にする、ネットワークインターフェース８０２を含む、バスを介して接続されたハードウェア要素を含むことができる。コンピュータシステムは、中央処理ユニット（ＣＰＵ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、ネットワークプロセッサ、または他のプロセッサなど、１つまたは複数のプロセッサ８０４をさらに含むことができる。プロセッサは、シングルコアプロセッサまたはマルチコアプロセッサを含み得る。
【０１３４】
[000139]いくつかの実施形態では、コンピュータシステムは、グラフィカルユーザインターフェース（ＧＵＩ）８０６を含むことができる。ＧＵＩ８０６は、ユーザ閲覧可能データを出力するために、ディスプレイ（ＬＥＤ、ＬＣＤ、タブレット、タッチスクリーン、または他のディスプレイ）に接続することができる。いくつかの実施形態では、ＧＵＩ８０６は、（たとえば、タッチスクリーンまたは他の対話型インターフェースを通して）命令を受信するように構成され得る。いくつかの実施形態では、マウス、キーボード、タッチセンシティブ入力デバイス、および他の入力デバイスまたは出力デバイスなど、１つまたは複数の入力デバイスおよび／または出力デバイスに接続するために、Ｉ／Ｏインターフェース８０８が使用され得る。Ｉ／Ｏインターフェース８０８は、赤外線デバイス、Ｂｌｕｅｔｏｏｔｈ（登録商標）デバイス、または他のワイヤレスデバイスに接続するためのワイヤードまたはワイヤレスインターフェースを含むことができる。
【０１３５】
[000140]いくつかの実施形態では、コンピュータシステムは、ローカルまたはリモートデータストア８１０を含み得る。データストア８１０は、当技術分野で知られている、様々なコンピュータ可読記憶媒体、ストレージシステム、およびストレージサービス、（たとえば、ディスクドライブ、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気ストレージデバイス、リレーショナルデータベース、オブジェクトストレージシステム、ローカルまたはクラウドベースストレージサービス、あるいは他の記憶媒体、システム、またはサービス）を含むことができる。データストア８１０は、本明細書で説明されるように生成、記憶、またはさもなければ利用されるデータを含むことができる。たとえば、データストア８１０は、上記で説明されたように生成および記憶された、計算されたフロー８１２およびネットワークモデル８１４を含むことができる。メモリ８１６は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ（登録商標）、フラッシュメモリまたは他のメモリ技術を含む、様々なメモリ技術を含むことができる。メモリ８１６は、本明細書で説明される方法を実装するための実行可能コードを含むことができる。たとえば、メモリ８１６は、本明細書で説明される方法を各々実装する、ネットワーク分析器モジュール８１８と報告生成器モジュール８２０とを含むことができる。
【０１３６】
[000141]上記の例は、理解の明快のためにある程度詳細に説明されてきたが、上記で説明された本発明の技法は、与えられた詳細に限定されない。上記で説明された発明技法を実装する多くの代替のやり方がある。開示された例は、限定的ではなく例示的である。
【図１】
2019533373.tif 000005
【図２】
2019533373.tif 000006
【図３（Ａ）】
2019533373.tif 000007
【図３（Ｂ）】
2019533373.tif 000008
【図３（Ｃ）】
2019533373.tif 000009
【図４】
2019533373.tif 000010
【図５（Ａ）】
2019533373.tif 000011
【図５（Ｂ）】
2019533373.tif 000012
【図５（Ｃ）】
2019533373.tif 000013
【図６（Ａ）】
2019533373.tif 000014
【図６（Ｂ）】
2019533373.tif 000015
【図６（Ｃ）】
2019533373.tif 000016
【図７】
2019533373.tif 000017
【図８】
2019533373.tif 000018
【国際調査報告】
2019533373.tif 000019