(57)【要約】      （修正有）【課題】ネットワークデータパケットを交換するための構文解析方法を提供する。【解決手段】ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを構築することであって、グラフは、グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有する、ことと、受信されたパケットをグラフにおける一意的な識別子と関連付けることにより、一意的な識別子に基づいて、受信されたパケットの特性を解析する。【選択図】図７
2015005980.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを構築することであって、該グラフは、該グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有する、ことと、
受信されたパケットを該グラフにおける一意的な識別子と関連付けることと、
該一意的な識別子に基づいて、該受信されたパケットの特性を再構築することと
を含む、方法。
【請求項２】
前記一意的な識別子は、非可換関数に基づいている、請求項１に記載の方法。
【請求項３】
前記非可換関数は、巡回冗長検査関数である、請求項２に記載の方法。
【請求項４】
前記特性は、横断される経路に存在する前記ヘッダを規定する、請求項１に記載の方法。
【請求項５】
前記特性は、フラグの関連づけられた組を有する、請求項１に記載の方法。
【請求項６】
前記特性は、アクションの関連づけられた組を有する、請求項１に記載の方法。
【請求項７】
前記グラフを連想メモリ内に経路表としてロードすることをさらに含む、請求項１に記載の方法。
【請求項８】
１回の探索において複数の経路をマッチングすることが可能な複数同時マッチング構文解析器として前記連想メモリを動作させることをさらに含む、請求項１に記載の方法。
【請求項９】
ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを格納する連想メモリであって、該グラフは、該グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有し、該連想メモリは、受信されたパケットの属性を一意的な識別子とマッチングする、連想メモリと、
該一意的な識別子に基づいて、該受信されたパケットの特性を再構築するインデックスメモリと
を含む、プロセッサ。
【請求項１０】
前記連想メモリは、三値内容参照可能メモリ（Ｔｅｒｎａｒｙ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）である、請求項９に記載のプロセッサ。
【請求項１１】
前記連想メモリは、１回の探索において複数の経路をマッチングすることが可能な複数同時マッチング構文解析器として動作する、請求項９に記載のプロセッサ。
【請求項１２】
前記一意的な識別子は、非可換関数に基づいている、請求項９に記載のプロセッサ。
【請求項１３】
前記非可換関数は、巡回冗長検査関数である、請求項１２に記載のプロセッサ。
【請求項１４】
前記特性は、横断される経路に存在する前記ヘッダを規定する、請求項９に記載のプロセッサ。
【請求項１５】
前記特性は、フラグの関連づけられた組を有する、請求項９に記載のプロセッサ。
【請求項１６】
前記特性は、アクションの関連づけられた組を有する、請求項９に記載のプロセッサ。
【請求項１７】
グラフにおける弧に割り当てられる一意的な値を形成することと、
該グラフにおいて経路を制限することと、
該割り当てられた値に基づいて、該グラフを通る計算される経路を形成することと、
該計算された経路を用いて経路表を構築することと、
該計算された経路のうちのいずれかが同じ値を有するか否かを決定し、同じ値を有する場合に、該形成および構築の動作を繰り返すことと
を含む、方法。
【請求項１８】
前記経路を制限することは、前記グラフにおいて循環経路に至る移行の数を限定することを含む、請求項１７に記載の方法。
【請求項１９】
前記経路を制限することは、前記グラフにおける経路を選択的に除去することを含む、請求項１７に記載の方法。
【請求項２０】
前記割り当てられる一意的な値は、非可換関数に基づいている、請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願への相互参照）
本願は、米国特許出願第１３／９２１，０９０号（２０１３年６月１８日出願）に基づく優先権を主張し、その内容は、参照によって本明細書中に援用される。
【０００２】
（発明の分野）
本発明は、ネットワークデータパケットを交換することに関連する。より具体的には、本発明は、構文解析木において一意的な経路の組を列挙することによって、ネットワークデータパケットを交換することに関連する。
【背景技術】
【０００３】
（背景）
入力ポートから出力ポートへデータパケットを交換するための種々の技術が、存在する。交換デバイスに要求される第１のアクションは、デバイスが受信したパケットのタイプを識別すること、およびパケットからデータフィールドを検出して抽出することである。この工程は、パケットの構文解析として知られている。
【０００４】
構文解析は、コンピュータによる、バイト列のその構成要素への形式分析を含み、互いの構文上の関係を示す構文解析木をもたらし、構文解析木は意味に関する情報および他の情報も含み得る。したがって、構文解析木は、ある形式文法に従って、列の構文構造を表す根付き順序木である。構文解析木は、一般的に、依存文法の依存関係によって構築される。構文解析木の構造および要素が、入力言語の構文をより具体的に反映しているという点で、構文解析木は、抽象構文木（単に、構文木としても知られる）とは別個のものである。
【０００５】
過去１０年間、コンピュータネットワーキングは、広範な種々の特別目的ネットワークプロトコルおよび仕様（例えば、非同期転送モード（ＡＴＭ）、トークンリング、ファイバーチャネル、およびインフィニバンド）から、普遍的物理層およびプロトコルとしてのイーサネット（登録商標）の使用に収束してきた。特定の特徴（例えば、コールハンドリング、ディスクアクセス、およびプロセッサ相互接続）に向けられたこれらの古いネットワークプロトコルに加えて、仮想マシン、分散コンピューティング、およびクラウドコンピューティングのような新たな技術がまた、新たな種々の要件をイーサネット（登録商標）およびトランスミッションコントロールプロトコル（ＴＣＰ）／インターネットプロトコル（ＩＰ）に課している。
【０００６】
この収束は、新たなプロトコル、アルゴリズム、およびタグの急増につながり、それらは、特別目的ネットワークプロトコルが提供したものと同一の特徴を提供するが、イーサネット（登録商標）をトランスポート層として使用する。新たなプロトコル、特徴、技術の変化率が増加するにつれて、より急速にこれらの技術を本分野に展開することに対する、対応するニーズが存在する。
【０００７】
従来、新たなプロトコルは、ハードウェアに対する変化、特に、交換機能を実装する特定用途向け集積回路（ＡＳＩＣ）に対する物理的変化によって供給されてきた。これは、新たなプロトコルの展開率を、これらの変化が実装および製作され得る速度に限定する。
【０００８】
近年、産業は、変化の影響を軽減する方法としてプログラマブル構文解析器を提供する技術の方へ進展してきた。プログラマブル構文解析器は、構文解析中に発見されたヘッダに基づいて、可能性のあるパケットタイプの木を構築することによって作動する。現在の構文解析器は、発見された各ヘッダに対するビット（フラグとして知られる）を設定することによって、構文解析中に遭遇したヘッダのタイプの追跡を続ける。
【０００９】
発見されたヘッダのタイプを追跡するためにフラグを使用することは、ヘッダが発見された順序を記録しないので、いくつかの場合において不十分である。その結果、現存の構文解析器は、順序が重要である場合、順序の追跡を続けるために、特別なフラグビットを使用しなければならず、順序情報が保存される必要がある場合を知っていなければならない。
【００１０】
図１は、パケットヘッダの７つの異なるタイプを検出する見本の構文解析木を示す。すべてのパケットは、任意のヘッダＶＬＡＮ１０２またはＶＬＡＮ１０３を含み得るイーサネット（登録商標）パケット１０１として現れ、それから、ＩＰｖ４  １０４、ＩＰｖ６  １０５、またはその他１０８に分類される。ＩＰパケットは、ＴＣＰ１０６、ＵＤＰ１０７、またはその他ＩＰ１０９にさらに分類される。本構文解析木において、８つのフラグの組が、取られた経路を一意的に決定し得る。
【００１１】
図２は、図１の構文解析木を示すが、図２において、ＧＲＥヘッダ２１０が追加されている。ＧＲＥヘッダがイーサネット（登録商標）ヘッダの方向に向き得るので、このとき、ループが起こり得、フラグの組は、もはやヘッダが発見された場所を決定することができない。例えば、シーケンス
【００１２】
【数１】
2015005980.tif 000003
は、このとき、正確に同一のフラグを設定するが、構文解析されたパケットデータを受信するフォワーディングエンジンによって、別に扱われる必要があり得る。
【００１３】
上記のことから、構文解析木を通る経路を分析するための向上した技術を提供することが望ましい。
【発明の概要】
【課題を解決するための手段】
【００１４】
本発明は、例えば、以下を提供する。
（項目１）
ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを構築することであって、該グラフは、該グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有する、ことと、
受信されたパケットを該グラフにおける一意的な識別子と関連付けることと、
該一意的な識別子に基づいて、該受信されたパケットの特性を再構築することと
を含む、方法。
（項目２）
前記一意的な識別子は、非可換関数に基づいている、項目１に記載の方法。
（項目３）
前記非可換関数は、巡回冗長検査関数である、上記項目のいずれかに記載の方法。
（項目４）
前記特性は、横断される経路に存在する前記ヘッダを規定する、上記項目のいずれかに記載の方法。
（項目５）
前記特性は、フラグの関連づけられた組を有する、上記項目のいずれかに記載の方法。
（項目６）
前記特性は、アクションの関連づけられた組を有する、上記項目のいずれかに記載の方法。
（項目７）
前記グラフを連想メモリ内に経路表としてロードすることをさらに含む、上記項目のいずれかに記載の方法。
（項目８）
１回の探索において複数の経路をマッチングすることが可能な複数同時マッチング構文解析器として前記連想メモリを動作させることをさらに含む、上記項目のいずれかに記載の方法。
（項目９）
ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを格納する連想メモリであって、該グラフは、該グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有し、該連想メモリは、受信されたパケットの属性を一意的な識別子とマッチングする、連想メモリと、
該一意的な識別子に基づいて、該受信されたパケットの特性を再構築するインデックスメモリと
を含む、プロセッサ。
（項目１０）
前記連想メモリは、三値内容参照可能メモリ（Ｔｅｒｎａｒｙ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）である、上記項目のいずれかに記載のプロセッサ。
（項目１１）
前記連想メモリは、１回の探索において複数の経路をマッチングすることが可能な複数同時マッチング構文解析器として動作する、上記項目のいずれかに記載のプロセッサ。
（項目１２）
前記一意的な識別子は、非可換関数に基づいている、上記項目のいずれかに記載のプロセッサ。
（項目１３）
前記非可換関数は、巡回冗長検査関数である、上記項目のいずれかに記載のプロセッサ。
（項目１４）
前記特性は、横断される経路に存在する前記ヘッダを規定する、上記項目のいずれかに記載のプロセッサ。
（項目１５）
前記特性は、フラグの関連づけられた組を有する、上記項目のいずれかに記載のプロセッサ。
（項目１６）
前記特性は、アクションの関連づけられた組を有する、上記項目のいずれかに記載のプロセッサ。
（項目１７）
グラフにおける弧に割り当てられる一意的な値を形成することと、
該グラフにおいて経路を制限することと、
該割り当てられた値に基づいて、該グラフを通る計算される経路を形成することと、
該計算された経路を用いて経路表を構築することと、
該計算された経路のうちのいずれかが同じ値を有するか否かを決定し、同じ値を有する場合に、該形成および構築の動作を繰り返すことと
を含む、方法。
（項目１８）
前記経路を制限することは、前記グラフにおいて循環経路に至る移行の数を限定することを含む、上記項目のいずれかに記載の方法。
（項目１９）
前記経路を制限することは、前記グラフにおける経路を選択的に除去することを含む、上記項目のいずれかに記載の方法。
（項目２０）
前記割り当てられる一意的な値は、非可換関数に基づいている、上記項目のいずれかに記載の方法。
【００１５】
（概要）
方法は、ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを構築することを含む。グラフは、グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有する。受信されたパケットは、グラフにおける一意的な識別子と関連づけられる。受信されたパケットの特徴は、一意的な識別子に基づいて、再構築される。
【００１６】
プロセッサは、ネットワークトラフィックと関連づけられたパケットヘッダの組を特徴づけるグラフを格納する連想メモリを含む。グラフは、グラフにおける経路を形成するパケットヘッダの各可能な組み合わせに対して一意的な識別子を有する。連想メモリは、受信されたパケットの属性を一意的な識別子とマッチングする。インデックスメモリは、一意的な識別子に基づいて、受信されたパケットの特性を再構築する。
【００１７】
方法は、グラフにおける弧に割り当てられる一意的な値を形成することと、グラフにおいて経路を制限することと、割り当てられた値に基づいて、グラフを通る計算される経路を形成することと、計算された経路を用いて経路表を構築することと、計算された経路のうちのいずれかが同じ値を有するか否かを決定し、同じ値を有する場合に、形成および構築の動作を繰り返すこととを含む。
【００１８】
本発明は、添付の図面と合わせて考慮される以下の詳細な説明と共に、より完全に理解される。
【００１９】
同様の参照数字は、図面のうちのいくつかの図を通じて対応する部分を表す。
【図面の簡単な説明】
【００２０】
【図１】図１は、ループのないトポロジーを有する構文解析木を図示する。
【図２】図２は、ループを含む構文解析木を図示する。
【図３】図３は、本発明の実施形態に従って、割り当てられたノードおよび経路値を有する、図２からの構文解析木を図示する。
【図４】図４は、本発明の実施形態と関連づけられた処理動作を図示する。
【図５Ａ】図５Ａは、本発明の実施形態に従って、１つの例示的経路に対して計算されたヘッダ値および経路値を示す。
【図５Ｂ】図５Ｂは、本発明の実施形態に従って、第２の見本経路に対して計算されたヘッダ値および経路値を示す。
【図６】図６は、本発明の実施形態に従って、経路値計算を使用する構文解析器のハードウェア実装を図示する。
【図７】図７は、本発明の実施形態と関連づけられた処理動作を図示する。
【発明を実施するための形態】
【００２１】
（詳細な説明）
本発明は、構文解析木において横断されるヘッダの各可能な組み合わせに一意的な識別子を割り当てる。有利なことに、一意的な組み合わせは、ハードウェアにおいて効果的にコンピュータ計算され得る。図３は、本発明の実施形態に従って、割り当てられたノードおよび経路値を有する、図２からの構文解析木を図示する。
【００２２】
図４は、本発明の実施形態と関連づけられた処理動作を図示する。初めに、値が、グラフにおける弧に割り当てられる４１０。例えば、有向の循環または非循環グラフは、値をグラフにおける各弧に割り当てられ得る。値は、任意であり得るが、各弧に対して一意的であるべきである。値は、連続的に割り当てられ得るが、無作為または半無作為割り当てが、より良い結果を生み得る。本文脈において、弧は、グラフにおける２つのノード間のリンクである。経路は、グラフを通る一連の弧である。
【００２３】
それから、制限が、グラフにおける経路にかけられる４１２。例えば、図２に示されるような、有向の循環グラフは、意図されたアプリケーションの作成者の知識に基づいて、循環経路に至る移行の数を限定することによって、有向の非循環グラフに転換され得る。例えば、ＧＲＥ２１０からイーサネット（登録商標）２０１への弧が一度のみ横断され得ることの限定は、循環グラフを非循環グラフに変換する。非循環グラフが生成されると、非循環グラフは、関心のない、または作成者のアプリケーションにおいて発生しないと知られているノードへの移行を除去することによって、作成者の知識に基づいてさらに変形され得る。
【００２４】
次に、経路が、グラフにおいて計算される４１４。図５Ａおよび図５Ｂは、下記に論じられるように、２つのそのような経路における計算の例を示す。式は、作成者、または増分計算を実行する無作為選択のいずれかによって選択されるべきである。選択された式は、非可換性（Ａ＋Ｂ！＝Ｂ＋Ａを意味する）である式であるべきである。たいていの巡回冗長検査（ＣＲＣ）関数は、この基準を満たす。
【００２５】
次に、経路表が、構築される４１６。つまり、列挙された可能な経路の結果から、表が構築される。次に、表は、共通の値（衝突と称される）に関して評価される。どの２つの経路も、同一の値を有しないことがあり、そうでなければ、衝突が存在する。衝突が存在しない場合（４１８−いいえ）、処理は完了する４２０。そうでなければ（４１８−はい）、処理は、ブロック４１４に戻る。衝突が発生した場合、弧割り当ての新たな組および／または新たな式が、適用され、ブロック４１４〜４１８の処理が繰り返される。本サイクルは、衝突のない表が生成されるまで、またはアルゴリズムが任意の限界に達し、失敗を報告するまで、繰り返される。
【００２６】
図３は、図２からの、ループを有する例示的構文解析木を示すが、移行弧の各々における一意的な値の組が列挙されている。非可換関数の例は、Ｐｙｔｈｏｎ疑似コードにおいて下記に示される。図５Ａおよび図５Ｂに示される値に対して、本関数は、図５Ａおよび図５ＢのＩｎｃＣａｌｃ列に示される出力値を生成する。
【００２７】
＃簡単な非可換関数の例。
＃この関数は、ｃｓｔａｔｅの下位ビットが１であるか否かに基づいて、
＃値０ｘ８３に排他的論理和を繰り返し行い、
＃現在の状態にする。それから、ｃｓｔａｔｅの値を
＃１ビットだけシフトする。シフトは、
＃関数に非可換特性を与える。
＃これは、多項式ｘ＾７＋ｘ＋１を使用する
＃８ビットＣＲＣ関数の簡単化されたバージョンである。
【００２８】
【数２】
2015005980.tif 000004
ｆｕｎｃｔｉｏｎ８によって上記に説明された式を使用して、発明者らは、同じヘッダタイプを含むが、異なる順序で配列された２つのパケットに対する経路ハッシュ計算値が、２つの異なる経路ハッシュ計算値をもたらすことを示す。
【００２９】
第１のパケットに対する構文解析経路において、図３において示された列挙された経路値を使用して、結果として生じる経路値のシーケンスは、図５Ａに示されるように、１、７、２０、および１７になる。上記のｔｗｏｓｅｑ（）関数は、ｆｏｒｍｕｌａ８（）関数を使用することにより、図５Ａに示されるように、増分経路ハッシュ計算値１、１３２、８６、および５８をコンピュータ計算する。発明者らは、第１のパケットに対する最終経路ハッシュ値として、最後の増分経路ハッシュ計算値５８を使用する。
【００３０】
各経路ハッシュコンピュータ計算は、状態変数ｃｓｔａｔｅを一定値（この場合では０）に初期化することによって、同様に始まる。構文解析器によって横断される各弧に対して、新たな増分状態値ｃｓｔａｔｅが、ｆｏｒｍｕｌａ８（）を呼び出すことによって、ｃｓｔａｔｅの値および各弧に対する弧値を用いて、コンピュータ計算される。上記の疑似コードは、各々の新たなｃｓｔａｔｅ値をコンピュータ計算すると、ｃｓｔａｔｅおよびａｒｃＶａｌｕｅを供給する。一実施形態において、最終値のみが、保持され、次の処理のために送られる。上記の例において、ｆｏｒｍｕｌａ８（）計算は、増分経路ハッシュ計算値１、１３２、８６、５８を生む。最後の増分経路ハッシュ計算値５８のみが、第１のパケットに対する最終経路ハッシュ値として送られ得る。
【００３１】
第２のパケットに対する構文解析経路において、結果として生じる経路値のシーケンスは、３、２０、１７、１であり、増分経路ハッシュ値３、１５０、９０、４４をもたらし、４４が、次の処理のために使用される最終経路ハッシュである。これらの値は、図５Ｂに示される。
【００３２】
正しく選択された関数および弧値の組に関して、構文解析木を通るあらゆる有効な経路は、一意的な識別子をもたらし、その識別子は、後に、取られた経路と、どのヘッダが存在したかとの両方を再構築するために使用され得る。この１つの値を格納することは、すべての中間値を格納することよりも有意にコンパクトである。
【００３３】
図６は、経路値計算を使用する構文解析器のハードウェア実装を示す。例のために、図６の機能ブロックは、ＡＳＩＣにおいて実装され得る。データは、典型的に、完全なパケットよりも小さいチャンクにおいて構文解析器内に達する。構文解析器は、パケットにおけるどの決定点（パケットの冒頭からの数バイトのオフセットとして表現される）を見るべきかを決定する。このオフセットにおけるデータは、キー生成５０１ユニットによって抽出され、現在の状態と共に、次状態表５０２に送信される。次状態表は、典型的に、三値内容参照可能メモリ（Ｔｅｒｎａｒｙ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ、ＴＣＡＭ）または他の連想データ構造として実装される。ＴＣＡＭは、構文解析木における各弧に対する入力を有する。ＴＣＡＭにおけるマッチングは、次状態および／または取られるべきアクションを提供する。アクションは、抽出データ構造５０６に記録されるべきデータ（例えば、パケットから抽出されるフィールド、パケットからのフィールドのオフセット、または特定のフィールドが存在または不在であったことを示すフラグ）を規定し得る。アクションはまた、構文解析木がパケットを構文解析し続けるべきか否か、または十分な情報が明らかにされており、構文解析が、終了し得るか否かを規定し得る。
【００３４】
次状態表５０２の結果は、ブロック５０３において、現在の状態を更新するために使用され、増分経路値計算を実施する。従来技術において、フラグは、この点で設定されるが、その動作は、各経路が一意的な識別を有するので、省略され得る。したがって、その識別は、経路構成要素および順序を規定するために使用され得る。アクションが、構文解析が完了したことを示す場合、最終経路値が、経路値表５０５に転送される。そうでなければ、現在の状態および経路値が、キー生成５０１に返送され、そこで、追加のサーチが、構文解析が完了するまで実施される。
【００３５】
入ってくるデータからのパケットデータおよび次状態表５０２からのアクションは、着目するデータフィールドをパケットから抽出するために使用され、それから、そのデータフィールドは、抽出データ構造５０６に送信される。構文解析の終わりに、経路値表５０５の結果は、この構造に追加され、それから、パケットがどのように転送されるかを決定する制御経路に送信される。
【００３６】
図７は、本発明の実施形態と関連づけられた処理動作を図示する。初めに、グラフが、構築される７００。例えば、図４の動作は、グラフを構築するために使用され得る。次に、受信されたパケットが、グラフにおける一意的な識別子と関連づけられる７０２。図６のプロセッサが、本動作を実装するために使用され得る。特に、次状態表５０２が、経路の弧をインクリメンタルに横断するために使用され得る。これは、最終的に、インデックスメモリ５０５に適用される最終経路値を生成する。最後に、受信されたパケットの特性は、一意的な識別子に基づいて再構築される。本動作はまた、図６のプロセッサを用いて実装され得る。特に、抽出データ構造５０６は、横断された経路に対して生成される。抽出データ構造は、横断された経路を一意的に識別し、したがって、受信されたパケットと関連づけられたパケットヘッダを特徴づける。抽出データ構造はまた、フラグとアクションとを関連づけ得る。
【００３７】
いくつかの進歩した構文解析器は、複数同時マッチング構文解析器（時々、カンガルー構文解析と呼ばれる）を使用し、そこで、次状態表５０２は、１回の探索中に、構文解析木における複数の弧をマッチングすることが可能である。図３の場合において、１回の探索あたり３回のマッチングを実施することが可能なカンガルー構文解析器は、イーサネット（登録商標）４０１からノードＶＬＡＮ４０２およびＶＬＡＮ４０３を経由してＩＰｖ４  ４０４まで横断し得る。同一の１回の探索が、潜在的に、イーサネット（登録商標）４０１からＩＰｖ４  ４０４まで直接横断し得、経路値の目標は、取られた各経路に対して異なる経路値を有することであるので、経路値の式は、本タイプの構文解析器のために、このことを考慮に入れなければならない。
【００３８】
カンガルータイプの構文解析器において、経路値の式は、単にノード識別子ではなく、各々の取られた可能な経路に関するいくつかの情報を組み込む。図３は、図２からの構文解析木を示すが、そこで、設計における各弧は、一意的な値を列挙されている。複数の弧が１回の探索において横断されると、経路値計算は、どの弧が横断されたかを決定し、列挙された弧値に基づいて、新たな経路値をコンピュータ計算する。この場合、経路値は、１回の探索あたり３つの値まで組み込む。
【００３９】
経路値をコンピュータ計算するために使用され得る他の値が存在し、他の値は、依然として、各経路に対する一意的な列挙を生成し得る。例えば、次状態を決定するために使用されるイーサネット（登録商標）タイプ値、および次状態探索に送信されるキー値は、両方、実現可能な候補であり、ノード番号または弧番号のような内部状態と共に状態を決定するために使用されるパケットからのデータの組み合わせも同様である。
【００４０】
説明の目的のための上記の説明は、本発明の完全な理解を提供するために、特定の専門用語を使用した。しかしながら、特定の詳細が本発明を実施するために必要とされないことが、当業者にとって明白である。したがって、本発明の特定の実施形態の上記の説明は、例証および説明の目的のために提示される。それらは、網羅的であることも、本発明を開示された正確な形態に限定することも意図されない。明らかに、多くの変更および変形が、上記の教示を考慮して、可能である。本実施形態は、本発明の原理およびその実施可能な用途を最も良く説明するために選択され、説明された。それによって、本実施形態は、当業者が、想定される特定の使用に適したように、本発明および種々の変更を有する種々の実施形態を最も良く利用することを可能にする。以下の特許請求の範囲およびその均等物が本発明の範囲を定義することが、意図される。
【符号の説明】
【００４１】
１０１  イーサネット（登録商標）パケット
１０２、１０３  ＶＬＡＮ
１０４  ＩＰｖ４
１０５  ＩＰｖ６
１０６  ＴＣＰ
１０７  ＵＤＰ
１０８  その他
１０９  その他ＩＰ
【図１】
2015005980.tif 000005
【図２】
2015005980.tif 000006
【図３】
2015005980.tif 000007
【図４】
2015005980.tif 000008
【図５Ａ】
2015005980.tif 000009
【図５Ｂ】
2015005980.tif 000010
【図６】
2015005980.tif 000011
【図７】
2015005980.tif 000012