(57)【特許請求の範囲】
【請求項１】
ネットワークを介してパケットを経路指定する方法であって、前記ネットワークのノードにおいて、
（ａ）前記パケット（Ｐ）を受信するステップ（Ｓ１）であり、
前記ノードが、それぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンク（２０）を利用することができ、前記複数の発信リンク（２０）のうちの少なくとも１つが複数のリンクＩＤと関連付けられており、
前記パケット（Ｐ）が、状態変数と、前記ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、
前記符号化が、フォールスポジティブの可能性を有する、リンクＩＤが前記リンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であるステップと、
（ｂ）前記複数の発信リンク（２０）のそれぞれについて、
（ｉ）リンクが複数のリンクＩＤと関連付けられている場合に、前記受信されたパケット（Ｐ）からの前記状態変数またはステップ（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップ（Ｓ４）、ならびに
（ｉｉ）前記データ構造を前記リンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップ（Ｓ５）と、
（ｃ）前記受信されたパケット（Ｐ）からの前記状態変数に少なくとも部分的に基づいて、新しい状態変数を決定するステップ（Ｓ７）と、
（ｄ）前記ステップ（ｂ）（ｉｉ）で前記データ構造のメンバとしての前記リンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、前記経路指定情報と前記新しい状態変数とを含む前記パケット（Ｑ）を転送するステップ（Ｓ８）と
を含み、
ステップ（ｂ）（ｉｉ）の前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、ステップ（ａ）において再度受信され、かつ、ステップ（ｂ）（ｉｉ）の検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｂ）（ｉ）において再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるためにステップ（ｃ）の実行を通して更新され、ループの再出現を回避する確率を増加する方法。
【請求項２】
前記データ構造がブルームフィルタを含む請求項１に記載の方法。
【請求項３】
前記ステップ（ａ）で受信される前記パケットが指標値を含み、前記指標値を使用して関数を決定し、前記決定された関数を使用し、前記状態変数を前記関数への入力として前記ステップ（ｂ）（ｉ）の前記判定を行い、前記ステップ（ｄ）で転送される前記パケットが前記指標値を含む、請求項１または２に記載の方法。
【請求項４】
前記複数のリンクがそれぞれ複数のリンクＩＤと関連付けられている請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記複数のリンクがそれぞれ同数のリンクＩＤと関連付けられている請求項４に記載の方法。
【請求項６】
前記パケットにより搬送される有効期間変数を前記状態変数として使用する請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記各リンクが前記ノードと前記ネットワークの個々の別のノードとの間の個々の通信経路を表し、前記リンクと関連付けられたリンクＩＤが前記通信経路または前記別のノード、あるいは前記通信経路と前記別のノードの両方を識別する、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
ネットワークを介してパケットを経路指定する方法であって、前記ネットワークを通る経路に沿った複数のノードのそれぞれにおいて、請求項１〜７のいずれか一項に記載の方法を実行するステップを含む方法。
【請求項９】
請求項８に記載の方法において使用される前記経路指定情報を提供する方法であって、前記ネットワークを通る前記経路に沿った前記複数のノードのそれぞれについて、（Ａ）前記状態変数が、前記ステップ（ｃ）で前記経路に沿った前の各ノードによりどのように更新されるかに従って、前記状態変数が前記ノードに到達するときに前記状態変数が何になるか判定するステップと、（Ｂ）前記経路の一部を形成する発信リンクごとに、（ｉ）前記リンクに複数のリンクＩＤが関連付けられている場合に、前記ステップ（Ａ）で判定された前記状態変数を使って、ステップ（Ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか選択するステップと、（ｉｉ）前記リンクと関連付けられたリンクＩＤを前記経路指定情報の前記データ構造へと符号化するステップとを含む方法。
【請求項１０】
ネットワークのノードとしてまたは前記ネットワークの前記ノードの一部として使用されてネットワークを介してパケット（Ｐ）を経路指定する装置であって、前記ノードが、それぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンク（２０）を利用することができ、前記複数の発信リンク（２０）のうちの少なくとも１つが複数のリンクＩＤと関連付けられており、前記パケット（Ｐ）が、状態変数と、前記ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、前記符号化が、フォールスポジティブの可能性を有する検査であって、リンクＩＤが前記リンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であり、当該装置が、
（ａ）前記パケット（Ｐ）を受信する手段（２）と、
（ｂ）前記複数の発信リンク（２０）のそれぞれについて、
（ｉ）前記リンクに複数のリンクＩＤが関連付けられている場合に、前記受信されたパケット（Ｐ）からの前記状態変数または決定手段（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップと、
（ｉｉ）前記データ構造を前記リンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップと
を実行する手段（４、８、１０、１２、１４）と、
（ｃ）前記受信されたパケット（Ｐ）からの前記状態変数に少なくとも部分的に基づいて、新しい状態変数を決定する手段（６）と、
（ｄ）前記ステップ（ｂ）（ｉｉ）で、前記データ構造のメンバとしての前記リンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、前記経路指定情報と前記新しい状態変数とを含む前記パケット（Ｑ）を転送する手段（１６、１８）と
を備え、
ステップ（ｉｉ）の前記実行手段（ｂ）により実行される前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、前記受信手段（ａ）において再度受信され、かつ、ステップ（ｉｉ）の前記検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｉ）において前記実行手段（ｂ）により再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるために更新され、ループの再出現を回避する確率を増加する装置。
【請求項１１】
前記データ構造がブルームフィルタを含む請求項１０に記載の装置。
【請求項１２】
前記受信する手段（ａ）によって受信される前記パケットが指標値を含む場合に、前記実行する手段（ｂ）が前記指標を使って関数を決定するように構成されており、前記ステップ（ｉ）の前記判定が、前記状態変数を前記関数への入力として、前記決定された関数を使って行われ、前記転送する手段（ｄ）によって転送される前記パケットが前記指標値を含む、請求項１０または１１に記載の装置。
【請求項１３】
請求項８に記載の方法において使用される前記経路指定情報を提供するための装置であって、前記ネットワークを通る前記経路に沿った前記複数のノードのそれぞれについて、（Ａ）前記状態変数が前記ステップ（ｃ）で前記経路に沿った前の各ノードによりどのように更新されるかに従って、前記状態変数が前記ノードに到達するときに前記状態変数が何になるか判定し、（Ｂ）前記経路の一部を形成する発信リンクごとに、（ｉ）前記リンクに複数のリンクＩＤが関連付けられている場合に、前記ステップ（Ａ）で判定された前記状態変数を使って、ステップ（Ｂ）（ｉｉ）のための前記関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか選択し、（ｉｉ）前記リンクと関連付けられたリンクＩＤを前記経路指定情報の前記データ構造へと符号化する手段を備える装置。
【請求項１４】
請求項１〜９のいずれか一項に記載の方法を実行するように装置を制御するためのプログラムであって、記憶媒体や伝送媒体といったキャリア媒体上に格納されるプログラム。
【請求項１５】
請求項１４に記載のプログラムを含む記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークにおけるパケット転送に関する。詳細には本発明は、ネットワークノードがパケットヘッダ内の転送情報からパケットがどのリンクに沿って転送されるべきか判定することができるように転送情報がパケットヘッダに含まれる方法に関する。
【背景技術】
【０００２】
同時係属の特許文献１および特許文献２に、パブリッシュ／サブスクライブ（ｐｕｂｌｉｓｈ／ｓｕｂｓｃｒｉｂｅ）型のネットワーキングスタックのための転送レイヤとしてのブルームフィルタ（Ｂｌｏｏｍ−ｆｉｌｔｅｒ）を用いた送信元経路指定の解決策が開示されている。
【０００３】
前述のＰＣＴ出願に開示されているものの要約として、少数のビットが１に設定されており、その他のビットが０である固定サイズのリンク識別子をそれぞれが備える有向リンクを有するネットワークを考える。配送経路（または木）が要求されると、トポロジ・マネージャ・エンティティは、対応するリンク識別子に対してビットごとのＯＲ演算を実行する。その結果である、ｚＦｉｌｔｅｒと呼ばれる小さいブルームフィルタは経路（木）の送信元に渡され、転送時に各ノードは、単純なビットごとのＡＮＤ演算によりそのリンク識別子のうちのどれがｚＦｉｌｔｅｒに加えられたかチェックする。
【０００４】
ｚＦｉｌｔｅｒを用いた転送レイヤの重要な一性能指標が転送効率、すなわち、転送決定時にパケットヘッダのｚＦｉｌｔｅｒを発信リンク識別子（またはリンク識別情報）に照合するときのフォールスポジティブによって生じた誤った配送のためにどれ程の帯域幅が浪費されるかである。（これは、要素をコンパクトに格納するためのデータ構造としてのブルームフィルタの性質の結果である。）正式には、特定の配送木についての転送効率は、ｚＦｉｌｔｅｒに加えられたリンクの数をパケットが使用するリンクの数で割ったものである。
【０００５】
フォールスポジティブを低減することにより転送の性能を高めるために、前述の特許文献２ではリンク識別情報の利用を提案した。この解決策では、各リンクがｄ個の異なるリンク識別情報を有し、トポロジマネージャはｄ個の異なるｚＦｉｌｔｅｒ候補を計算し、すべての候補の中で最善の性能を有すると予期される候補（予期される誤った配送の数がより低くなるように１に設定されたビットの数が最小である候補など）を選択する。
【０００６】
前述の特許文献１および特許文献２を見直せばさらなる洞察を得ることができる。
【０００７】
誤った配送の数が増加した場合には、ループが出現する確率も増加する。パケットがリンクＡ→Ｂ、リンクＢ→Ｃを通り、最後にリンクＣ→Ｄをトラバースすることになっている単純な事例を考える。その際、ノードＣとノードＡとの間にリンクが存在する場合、パケットはフォールスポジティブの場合にはそのリンク上で送信され得る。このようにしてパケットは無限ループに入ることになる。さらに、ループするパケットが十分に早く廃棄されないと、同一のパケットの数が増加することになるはずである。
【０００８】
ループするパケットの問題を解決するためのいくつかの自明の解決策が、ｈｔｔｐ：／／ｐｓｉｒｐ．ｏｒｇ／ｆｉｌｅｓ／Ｄｅｌｉｖｅｒａｂｌｅｓ／ＰＳＩＲＰ−ＴＲ０９−０００１  ＬＩＰＳＩＮ．ｐｄｆからアクセスすることができる、欧州第七次研究枠組計画テーマ、プロジェクト・パブリッシュ−サブスクライブ・インターネット経路指定パラダイム助成許諾番号：２１６１７３（Ｅｕｒｏｐｅａｎ  Ｓｅｖｅｎｔｈ  Ｆｒａｍｅｗｏｒｋ  Ｐｒｏｇｒａｍｍｅ  Ｔｈｅｍｅ，ｐｒｏｊｅｃｔ  Ｐｕｂｌｉｓｈ−Ｓｕｂｓｃｒｉｂｅ  Ｉｎｔｅｒｎｅｔ  Ｒｏｕｔｉｎｇ  Ｐａｒａｄｉｇｍ，Ｇｒａｎｔ  ａｇｒｅｅｍｅｎｔ  ｎｏ．：２１６１７３）により公開された非特許文献１、ならびに非特許文献２に開示されている。
【０００９】
１つの簡単明瞭な方法は、パケットがネットワークをトラバースする際にホップバイホップで（ｈｏｐ−ｂｙ−ｈｏｐ）減分される有効期間（ＴＴＬ：ｔｉｍｅ−ｔｏ−ｌｉｖｅ）フィールドをパケットヘッダに導入するものである。最後にパケットは、カウンタが０に達したときに廃棄される。配送木を計算するときに、（ｚＦｉｌｔｅｒ作成の責任を負う）トポロジマネージャは常に、木の特性（最大の送信側−受信側距離など）に従って初期有効期間値を調整することができる。
【００１０】
さらに進んだループ防止手法は、後でループを生じる可能性のあるブルームフィルタをキャッシュに入れるものである。この手法では、ノードごとに、隣接ノードから当該ノードを指し示すリンク識別子（およびリンク識別情報）（本明細書では着信リンク識別子／識別情報という）を知る必要がある。この解決策において転送ノードは、パケットが、実際の着信インターフェースに加えてその着信リンク識別子のいずれかにも一致するかどうかチェックする。ブルームフィルタは、複数のインターフェースに一致する場合、パケットを受信したインターフェースを有するそのループ防止キャッシュに（ｚＦｉｌｔｅｒ、インターフェースＩＤ）エントリを入れる。パケットを転送するときに、ノードは、ｚＦｉｌｔｅｒがすでにキャッシュに入っているかどうかチェックする必要がある。そうでない場合にはパケットを安全に転送することができる（また必要な場合にはｚＦｉｌｔｅｒをキャッシュにも追加する必要がある）。ｚＦｉｌｔｅｒがキャッシュに存在する場合には、パケットは、当該パケットが対応するエントリに存在する同じインターフェース上で到着した場合に限り転送される。そうでない場合、当該パケットは、予期されるのと異なる、すなわちループが検出されるインターフェース上で到着したものとして廃棄される。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】国際出願第ＰＣＴ／ＥＰ２００８／０６１１６７号明細書
【特許文献２】国際出願第ＰＣＴ／ＥＰ２００８／０６３６４７号明細書
【非特許文献】
【００１２】
【非特許文献１】Ｐ．Ｊｏｋｅｌａ，Ａ．Ｚａｈｅｍｓｚｋｙ，Ｃ．Ｅｓｔｅｖｅ，Ｓ．ＡｒｉａｎｆａｒおよびＰ．Ｎｉｋａｎｄｅｒ，「ＬＩＰＳＩＮ：Ｌｉｎｅ  ｓｐｅｅｄ  Ｐｕｂｌｉｓｈ／Ｓｕｂｓｃｒｉｂｅ  Ｉｎｔｅｒ−Ｎｅｔｗｏｒｋｉｎｇ」，ＰＳＩＲＰ  ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ，Ｊａｎｕａｒｙ  １１  ２００９
【非特許文献２】Ｐ．Ｊｏｋｅｌａ，Ａ．Ｚａｈｅｍｓｚｋｙ，Ｃ．Ｅｓｔｅｖｅ，Ｓ．ＡｒｉａｎｆａｒおよびＰ．Ｎｉｋａｎｄｅｒ，「ＬＩＰＳＩＮ：Ｌｉｎｅ  ｓｐｅｅｄ  Ｐｕｂｌｉｓｈ／Ｓｕｂｓｃｒｉｂｅ  Ｉｎｔｅｒ−Ｎｅｔｗｏｒｋｉｎｇ」，ｉｎ  ＳＩＧＣＯＭＭ  ‘０９，Ａｕｇｕｓｔ  ２００９
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本願出願者は、先に提案したループ防止技術が、リソース利用（ノードにおける状態または不必要な帯域幅消費）に関して高くつくことを理解している。
【００１４】
ＴＴＬだけを用いた解決策では、配送木ごとのＴＴＬが別々に設定される場合でさえも、ループを完全に除去することはできない。例えば、木の送信元の近くで生成されるループは、ＴＴＬが最終的に低減されて０になるまでパケットによりやはり複数回トラバースされることになり、パケットの有害な増殖を引き起こし、したがって転送効率を低下させる。
【００１５】
キャッシュを用いたループ防止手法の問題は、パケットごとに転送ノードに求められる演算の回数が増加することである。最初の転送決定に加えて、ノードは常に、転送前にパケットヘッダのｚＦｉｌｔｅｒをキャッシュエントリと比較しなければならず、これは、エントリの量が多い場合には時間がかかる可能性もあり、パケット転送の速度を何オーダーも遅らせる可能性もある。
【００１６】
これら２つの解決策の性能を推測するために、シミュレーションを行い、キャッシングを用いた解決策においてノードごとに必要とされるエントリの数および２つの異なる解決策により得られる転送効率を測定した。シミュレーションは、異なるロケット燃料参照トポロジ［Ｒｏｃｋｅｔｆｕｅｌ  ｒｅｆｅｒｅｎｃｅ  ｔｏｐｏｌｏｇｉｅｓ，ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｗａｓｈｉｎｇｔｏｎ．ｅｄｕ／ｒｅｓｅａｒｃｈ／ｎｅｔｗｏｒｋｉｎｇ／ｒｏｃｋｅｔｆｕｅｌ／ｗｅｉｇｈｔｓ−ｄｉｓｔ．ｔａｒ．ｇｚ、２００９年４月３日にアクセス］において、サイズの異なる木（発信側の数と受信側の数とが１＋７、１＋１５、１＋２３、１＋３１の場合）について行ったが、結果は質的に異なるものではなかったため、ここには１つのトポロジについての結果を示す（ＡＳ１２２１、１０４のノードおよび１５６のリンクを有し、これは３０２個のリンク識別子を意味し、すべてのリンク重みは１であると仮定した）。
【００１７】
添付の図面の図１には転送効率についての結果が示されており、キャッシングを用いたループ防止とＴＴＬを用いたループ防止とのギャップは大きく、木のサイズが増加するときに増加することが明らかである（木のサイズは、配信において関心対象とされるノードの数を意味する）。添付の図面の図２に、異なる次数を有するノードにおいて見られるすべての異なるｚＦｉｌｔｅｒ間でのキャッシュに入れられたｚＦｉｌｔｅｒの割合を示す。少なくとも高次のノードは受け入れられないほど多くキャッシングし、木のサイズが増加するにつれて必要とされるエントリ数も急速に増加すると結論付けることができる。
【００１８】
本願出願者が理解しているこれらの問題に対処することが求められている。
【課題を解決するための手段】
【００１９】
本発明の第１の態様によれば、ネットワークを介してパケットを経路指定する方法であって、ネットワークのノードにおいて、（ａ）パケットを受信するステップであり、ノードはそれぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンクを利用することができ、複数のリンクのうちの少なくとも１つが複数のリンクＩＤと関連付けられており、パケットは、状態変数と、ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、符号化は、フォールスポジティブの可能性を有する、リンクＩＤがリンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であるステップと、（ｂ）複数の発信リンクのそれぞれについて、（ｉ）リンクが複数の関連付けられたリンクＩＤを有する場合に、受信されたパケットからの状態変数またはステップ（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップと、（ｉｉ）データ構造をリンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップと、（ｃ）受信されたパケットからの状態変数に少なくとも部分的に基づいて新しい状態変数を決定するステップと、（ｄ）ステップ（ｂ）（ｉｉ）で、データ構造のメンバとしてのリンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、経路指定情報および新しい状態変数を含むパケットを転送するステップとを含み、ステップ（ｂ）（ｉｉ）の前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、ステップ（ａ）において再度受信され、かつ、ステップ（ｂ）（ｉｉ）の検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｂ）（ｉ）において再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるためにステップ（ｃ）の実行を通して更新され、ループの再出現を回避する確率を増加する方法が提供される。
【００２０】
データ構造はブルームフィルタを含み得る。
【００２１】
ステップ（ａ）で受信されるパケットは指標値を含んでいてもよく、ステップ（ｂ）（ｉ）の判定は指標値と状態変数とを使って行われてもよい。この場合、ステップ（ｄ）で転送されるパケットは指標値を含むことになるはずである。
【００２２】
指標は関数を求めるのに使用され、ステップ（ｂ）（ｉ）の判定は、状態変数を関数への入力として用いて、求められる関数を使って行われてもよい。
【００２３】
複数のリンクのそれぞれを複数のリンクＩＤと関連付けられたものとすることもできる。また、例えば複数の転送表が使用される場合などのように、複数のリンクをそれぞれ同数のリンクＩＤと関連付けられたものとすることもできる。
【００２４】
パケットにより搬送される有効期間変数が状態変数として使用されてもよい。
【００２５】
各リンクは、ノードと、ネットワークの個々の別のノードとの間の個々の通信経路を表すことができ、リンクと関連付けられたリンクＩＤは、通信経路または別のノードまたはその両方を識別する。したがって、リンクはノードから不特定のリモートの宛先までの物理リンクとすることもでき、あるいは単に、不特定の経路での経路内の次のノードへの参照とすることもできる。
【００２６】
上述したように、ステップ（ｃ）で決定される新しい状態変数は、ステップ（ｂ）（ｉ）でどのリンクＩＤを使用すべきか判定するのに使用され得る。したがって、状態変数を受信し、当該状態変数を直接使って、どのリンクＩＤまたは経路指定表を使用すべきか決定し、次いで状態変数を更新するのではなく、ノードにおいて受信し次第状態変数を更新し、更新された状態変数を、どのリンクＩＤまたは経路指定表を使用すべきか決定する際に使用することができるはずである。
【００２７】
ネットワークを通る経路は複数の分岐を含み得る。
【００２８】
本発明の第２の態様によれば、ネットワークを通る経路に沿った複数のノードのそれぞれにおいて本発明の第１の態様による方法を実行するステップを含む、ネットワークを介してパケットを経路指定する方法が提供される。
【００２９】
本発明の第３の態様によれば、本発明の第２の態様による方法において使用される経路指定情報を提供する方法であって、ネットワークを通る経路に沿った複数のノードのそれぞれについて、（Ａ）状態変数がステップ（ｃ）において経路に沿った前の各ノードによりどのように更新されるかに基づき、状態変数がノードに到達するときに状態変数が何になるか判定するステップと、（Ｂ）経路の一部を形成する発信リンクごとに、（ｉ）リンクに複数のリンクＩＤが関連付けられている場合に、ステップ（Ａ）で判定された状態変数を使って、ステップ（Ｂ）（ｉｉ）のための関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか選択するステップと、（ｉｉ）リンクと関連付けられたリンクＩＤを経路指定情報のデータ構造へと符号化するステップとを含む方法が提供される。
【００３０】
本発明の第４の態様によれば、ネットワークを介してパケットを経路指定するネットワークのノードとしてまたはその一部として使用するための装置であって、ノードはそれぞれが少なくとも１つのリンクＩＤと関連付けられている複数の発信リンクを利用することができ、複数のリンクのうちの少なくとも１つが複数のリンクＩＤと関連付けられており、パケットは、状態変数と、ネットワークを通る経路を形成する個々のリンクと関連付けられたリンクＩＤの集合を符号化している経路指定情報とを含み、符号化は、フォールスポジティブの可能性を有する、リンクＩＤがリンクＩＤの集合のメンバであるかどうかの検査に使用される確率的データ構造の形態であり、装置は、（ａ）パケットを受信する手段と、（ｂ）複数の発信リンクのそれぞれについて、（ｉ）リンクが複数の関連付けられたリンクＩＤを有する場合に、受信されたパケットからの状態変数または決定手段（ｃ）で決定される新しい状態変数を使って、ステップ（ｂ）（ｉｉ）のための関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか判定するステップと、（ｉｉ）データ構造をリンクと関連付けられたリンクＩＤのメンバであるかどうか検査するステップとを実行する手段と、（ｃ）受信されたパケットからの状態変数に少なくとも部分的に基づいて新しい状態変数を決定する手段と、（ｄ）ステップ（ｂ）（ｉｉ）で、データ構造のメンバとしてのリンクと関連付けられたリンクＩＤを有すると判定された各リンクに沿って、経路指定情報および新しい状態変数を含むパケットを転送する手段とを備え、ステップ（ｉｉ）の前記実行手段（ｂ）により実行される前記検査において発生するフォールスポジティブによりループが発生し、前記ノードで同じパケットが受信される場合に、前記受信手段（ａ）において再度受信され、かつ、ステップ（ｉｉ）において前記検査のための前記関連付けられたリンクＩＤを決定するためにステップ（ｉ）において前記実行手段（ｂ）により再度使用される前記状態変数が、同じパケットが以前前記ノードにより受信されたことがあるために更新され、ループの再出現を回避する確率を増加する装置が提供される。
【００３１】
データ構造はブルームフィルタを含み得る。
【００３２】
受信する手段（ａ）によって受信されるパケットが指標値を含む場合、実行する手段（ｂ）は、指標値および状態変数を使ってステップ（ｉ）の判定を行うように適合されており、転送する手段（ｄ）により転送されるパケットは指標値を含んでいてもよい。
【００３３】
実行する手段（ｂ）は指標を使って関数を求めるように適合されており、ステップ（ｉ）の判定は、状態変数を関数への入力として用いて、求められる関数を使って行われてもよい。
【００３４】
実行する手段（ｂ）は決定する手段（ｃ）によって決定される新しい状態変数を使って、ステップ（ｉ）でどのリンクＩＤを使用すべきか判定するように適合されていてもよい。
【００３５】
本発明の第５の態様によれば、本発明の第２の態様による方法において使用される経路指定情報を提供するための装置であって、ネットワークを通る経路に沿った複数のノードのそれぞれについて、（Ａ）状態変数がステップ（ｃ）において経路に沿った前の各ノードによりどのように更新されるかに従って、状態変数がノードに到達するときに状態変数が何になるか判定し、（Ｂ）経路の一部を形成する発信リンクごとに、（ｉ）リンクが複数の関連付けられたリンクＩＤを有する場合に、ステップ（Ａ）で判定された状態変数を使って、ステップ（Ｂ）（ｉｉ）のための関連付けられたリンクＩＤとしてどのリンクＩＤを使用すべきか選択し、（ｉｉ）リンクと関連付けられたリンクＩＤを経路指定情報のデータ構造へと符号化する手段を備える装置が提供される。
【００３６】
本発明の第６の態様によれば、本発明の第１、第２もしくは第３の態様による方法を実行するように装置を制御するためのプログラム、または、装置にロードされると、装置が本発明の第４もしくは第５の態様による装置になるようにするプログラムが提供される。プログラムはキャリア媒体上で担持され得る。キャリア媒体は記憶媒体とすることもできる。キャリア媒体は伝送媒体とすることもできる。
【００３７】
本発明の第７の実施形態によれば、本発明の第６の態様によるプログラムによってプログラムされた装置が提供される。
【００３８】
本発明の第８の実施形態によれば、本発明の第６の態様によるプログラムを含む記憶媒体が提供される。
【発明の効果】
【００３９】
本発明の一実施形態は、先行技術に関連する前述の問題のうちの少なくとも１つに対処する少なくとも１つの技術的利点を提供する。これについて以下で詳細に述べる。
【００４０】
本発明の一実施形態において使用される確率的データ構造は、要素（リンクＩＤ）の集合を符号化しており、要素（リンクＩＤ）が要素（リンクＩＤ）の集合のメンバであるかどうか検査するのに使用される。検査は通常、フォールスポジティブの可能性はあるが、フォールスネガティブの可能性はないようなものであるはずである。データ構造は、フォールスポジティブの確率が生じるために、要素が集合のメンバであるか否かを絶対確実に判定することのないデータ構造であるという意味において確率的である。データ構造は決定論的であることに対立するものとして確率的である。これは、集合要素関係の決定論的な、または完全な表現であるよりは、ブルームフィルタといった、集合要素関係のコンパクトな表現を使用することに伴う妥協点である。それが本発明で対処することを目指す技術的問題をもたらすものである。
【００４１】
確率的データ構造は、それが符号化している要素（リンクＩＤ）の数より小さい空間を占めるという意味において空間効率のよい確率的データ構造であるとみなすことができる。ある種の確率的データ構造においては、要素（リンクＩＤ）を要素（リンクＩＤ）の集合に加えることはできるが、除去することはできない。
【図面の簡単な説明】
【００４２】
【図１】先に考察したｚＦｉｌｔｅｒを用いた転送レイヤにおけるループ防止のための手法に伴う問題を例示するのに使用するための、前述の図である。
【図２】先に考察したｚＦｉｌｔｅｒを用いた転送レイヤにおけるループ防止のための手法に伴う問題を例示するのに使用するための、やはり前述の図である。
【図３】単純なネットワークにおける本発明の一実施形態の基本概念を示す図である。
【図４】本発明の一実施形態による、提案のノード内パケット処理アーキテクチャを示す図である。
【図５】ＴＴＬが状態変数として使用され、線形順序が実際の転送表を決定するのに使用される一例示的実施態様を示す図である。
【図６】図１で説明済みの元の方法と比べたＴＴＬを用いた線形順序の方法の転送性能を示す図である。
【図７】ＴＴＬを有する非自明の順序が４つの転送表を用いて、８つの転送表を用いる元の（同じ転送表指標がすべてのノードにより使用されるキャッシングを用いた解決策の）方法とほぼ同じ性能に到達し得ることを示す図である。
【図８】本発明を具現化する方法を概略的に示す図である。
【図９】本発明を具現化するネットワークノードと、ネットワークの他のノードとを概略的に示す図である。
【発明を実施するための形態】
【００４３】
以下で図８および図９を参照して本発明を具現化する方法および装置を説明する。その前に、本発明を具現化する方式の概要を、いくつかの具体例が示されている図３〜図７を参照して説明する。
【００４４】
複数の転送表の使用は先に国際出願第ＰＣＴ／ＥＰ２００８／０６３６４７号明細書において提案した。その提案では、使用される表の指標（ｄ）はすべてのパケットに含まれ、同じ指標が全転送経路／木に使用される。本発明の一実施形態では、パケットが何ホップトラバースしているかに基づく異なる表指標を有することによるこのシナリオへの改善が提案される。この改善で目指すのは、ネットワークにさらに別の状態を追加せずに、ｚＦｉｌｔｅｒを用いて転送するときにフォールスポジティブにより引き起こされるループを防止することである。
【００４５】
５つのリンク１〜５を有し、３つのノードＡ、ＢおよびＣからなる、ループにおけるパケット転送を可能にするはずの単純なトポロジを図３に示す。また図３には、異なるホップから見たパケットヘッダも示されている。パケットはリンク１、２、３および４を通らなければならない（すなわちこれらのリンクはｚＦｉｌｔｅｒ  ｚＦへと符号化されている）が、フォールスポジティブのために、パケットは誤ってリンク番号５も通る。
【００４６】
本発明の一実施形態では、パケットヘッダ内の状態情報を使って指標ｄを計算する。すなわち、パケットは、ノードＡに再度到達するときにおそらくは異なる転送表と照合されることになる。使用される状態は、例えば、（図１に示すような）ＴＴＬや他の何らかの変数などとすることができる。その場合ｄ値は、例えばモジュロ演算などを使って現在の状態変数から計算することができる。これについて以下でより詳細に説明する。
【００４７】
計算されたｄ値が偶然正しい値である場合、または別の転送表においてフォールスポジティブになる場合に、ｄは次のホップで再度変化する。このようにして、ループの各ホップにおける２回目の転送がフォールスポジティブと同程度にほとんど起こらなくなり、またコピーされるパケットも異なる状態を有するために非常に速く廃棄されることになる。
【００４８】
この考えをさらに改善するものとして、本発明の一実施形態では、現在の転送表指標（ｄ）を決定するのに複数の関数を使用し、関数の指標をパケットヘッダに加えることを提案する。この指標は、どの関数を使用すべきか指示するのに使用される。この改善により、国際出願ＰＣＴ／ＥＰ２００８／０６３６４７号明細書に開示されている有利な特徴である、複数の候補の中から最善のｚＦｉｌｔｅｒを選択するとい可能性が保持される。実際、異なるｚＦｉｌｔｅｒを生じることになる関数の数は転送表の数より大きいものとすることができ、そのため、さらに別の表（状態）を追加しなくても、一定の指標を用いる場合よりもさらに多くのｚＦｉｌｔｅｒ候補を得ることができる。より多くの候補があれば、（フォールスポジティブの最小化または他のポリシー施行の観点から見て）適切な候補を見つける確率が増大する。
【００４９】
本発明の一実施形態の転送ノードにおけるパケット処理の一般的プロセスを図４に示し、以下で説明する。
【００５０】
転送ノードはパケットを受信すると以下のステップを実行する。
１．転送ノードはヘッダから関数指標ｉを読み取り、指標に基づいて適切なｆｉ関数を選択する。
２．関数ｆｉはパケットヘッダに記載されている状態に適用され、転送表指標（ｄ）が求められる。ｄ＝ｆｉ（状態）
３．転送ノードは選択された転送表に従って発信インターフェースを決定する。
４．パケットを転送するための少なくとも１つのインターフェースがある場合、パケットの新しい状態が決定され、パケットヘッダに書き込まれる（前の状態を上書きする）。使用すべき関数が関数指標ｉにより再度正式に求められる。次の状態＝ｇｉ（状態）
５．パケットは発信インターフェース上で転送される。
【００５１】
本発明の一実施形態の転送方法は、上記のステップ１、２および４においてこれまでに知られている方法と異なる。
【００５２】
関数選択器をどのように実施すべきか、および関数を実際にどのように使用するかに関する設計上の選択肢に制約はない。これらの選択肢は、性能と、ｚＦｉｌｔｅｒ候補をいくつ生成することができるかに影響を及ぼす。当然考慮されるべき重要な制限事項は、ｚＦｉｌｔｅｒ作成時と、転送ノードにおけるパケットの転送時とで同じ順序が用いられる必要があることである。
【００５３】
以下で、関数ｆｉおよび関数ｇｉについての異なる実施態様を説明するが、最初に、これらの改変形態が、前述のｚＦｉｌｔｅｒ転送方法（国際出願ＰＣＴ／ＥＰ２００８／０６１１６７号明細書および国際出願ＰＣＴ／ＥＰ２００８／０６３６４７号明細書）を、特殊な事例として保持するものであることを説明する。
【００５４】
各ノードはＤ個の異なる転送表を含むものと仮定する。前述のｚＦｉｌｔｅｒを用いた転送アーキテクチャでは、転送表の指標はパケットヘッダ内にあった。この機能は、すべての転送ノードにおいて自明の関数ｆｉ＝＝ｉ（０…ｄ−１について）を適用し、状態変数を保持する（すなわちパケットヘッダ内の全フィールドが不変である）ものとして、本発明の一実施形態の特殊な事例とみなすことができる。この場合ノードはやはりループ回避のためのキャッシングを実施する必要がある。パケットヘッダにＴＴＬフィールドを加えることは、状態（ＴＴＬ）がすべての転送ノードにおいてホップバイホップで減らされることを意味するはずである。
【００５５】
最初の設計選択肢は、転送ノードがホップバイホップで線形順序を使用するものである。かいつまんでいうと、これは、ノードが指標０を有する転送表を使用した場合、次のノードは指標１を有する転送表を使用する必要があることなどを意味する。この順序は周期的であり、そのためノードが最後の転送表を使用したとき、配送木内のそれに隣接するノードは最初の転送表を使用するはずである。
【００５６】
これは、ＴＴＬフィールドをパケットヘッダ内の状態として利用することにより公式化することができる。状態変更として、各ノードは転送時にパケットのＴＴＬフィールドを減らす。パケットは、受信されたパケットのＴＴＬがすでに０である場合にはノードによりそれ以上転送されない。使用されるべき転送表の指標を決定する関数は以下のとおりである。
ｆｉ＝（ｉ−ＴＴＬ）ＭＯＤ  Ｄ
式中、Ｄは転送表の数であり、ＭＯＤはモジュロを表す。
【００５７】
この技法では、ｉを［０…Ｄ−１］の範囲とするＤ個の選択肢（転送表）を有することを利用することができる。
【００５８】
この解決策の１つの利点は、ループ回避の確率が非常に高まることである。というのは、パケットが、ループを完了した後でノードにおいて再度出現するときに、異なる状態を保持することになり、よってそのときには転送決定が、先の転送表と異なる転送表に基づいて行われるからである。
【００５９】
各ノードが８個の異なる表を有するものと仮定する。ここで、図５の例に関して、ノードＡがループするパケットを受信した後で、ｚＦｉｌｔｅｒを指標５の転送表と照合しようと試み、フォールスポジティブが生じない場合、転送は行われない（というのは、通常、転送決定はこの配送木において指標２の表に従って行われるはずだからである）。さらに別のフォールスポジティブが発生したために、パケットがさらにループ上に留まり続ける場合にも、連続したフォールスポジティブの確率が急速に減少し、高負荷のｚＦｉｌｔｅｒにおいてしか出現しないため、パケットはやはり十分に速く廃棄されることになる。ループが正確にＤホップの長さである場合、ＴＴＬフィールドは最終的には無限ループを防ぐことになる。
【００６０】
この解決策の転送効率を、（１）ｄが不変であるキャッシングを用いたループ防止手法、および（２）やはりｄが不変である有効期間を用いたループ防止手法を用いて得られた転送効率と比較した。
【００６１】
図６のシミュレーション結果は、転送効率の減少は許容できるものであり（小さい木を有するトポロジの中ではわずかに優れた性能を生じることさえもあり）、もっぱらＴＴＬだけを利用した場合よりも良好であり、しかも、ループ防止目的でのｚＦｉｌｔｅｒのキャッシングが完全になくなることを示している。
【００６２】
次に、状態変数としてＴＴＬを用いる非自明の順序を考察する。
【００６３】
以下の関数を考察する。
ｄ＝ｆｉ（ＴＴＬ）＝［（ＴＴＬ＋ｉ）＋（ＴＴＬ＋ｉ）／Ｄ］ＭＯＤ  Ｄ
ＴＴＬｎｅｗ＝ｇｉ（ＴＴＬ）＝ＴＴＬ−１
式中、ｉは関数指標であり、Ｄは転送表の数である。この最適化技術を用いれば、例えば、各リンクにおいて４つのリンク識別情報だけを用いて４を上回る数の候補ｚＦｉｌｔｅｒを作成することができる（よって並列転送表のメモリ所要量を低減させた）。
【００６４】
参照トポロジ（ＡＳ１２２１）についての暫定的結果を図７に示す。
【００６５】
図７には、ＴＴＬを用いた非自明の順序が、４つの転送表を用いて、８つの転送表を用いる元の方法（同じ転送表指標がすべてのノードにより使用されるキャッシングを用いた解決策）とほぼ同じ性能に到達し得ることが示されている。比較を容易にするために、元の転送解決策の４つの転送表の場合も示されており、ＴＴＬだけを用いた手法も参考のために示されている。
【００６６】
結論としては、対象とする領域（１つの木あたり１６〜２４の受信者、これはこのトポロジにおいてはおおよそ２７〜３６のリンクを意味する）において、ＴＴＬを用いたループ防止による転送解決策は、使用されるべき転送表が異なるホップバイホップの場合には実行可能である。より大きい木の場合には悪化するが、それでもなお高くつくｚＦｉｌｔｅｒキャッシングを回避し、ＴＴＬだけを用いた参考の手法を大幅にしのぐ。
【００６７】
より複雑な方法の単純な例を、以下の関数を使って実施することができる。
ｄ＝ｆｉ（状態）＝状態  ＭＯＤ  Ｄ
次の状態＝ｇｉ（状態）＝状態＋ｉ
式中、ｉは関数指標であり、Ｄは転送表の数である。
【００６８】
このようにして、異なる開始状態および異なるｉ値を取ることにより、多くの異なるフィルタ候補を生成することができる。実際には、ｚＦｉｌｔｅｒを作成するエンティティは、ｉと開始点との異なる組合せを試行してｚＦｉｌｔｅｒの集合を作成し、次いで何らかの品質指標に基づいてそれらのうちの最善のものを選択することができる。この指標は、例えば、統計的にフォールスポジティブ率に関連する充てん率（ｆｉｌｌ  ｆａｃｔｏｒ）（総ビット数に対する１に設定されたビットの量）などとすることができる（この場合もやはり選択肢の影響力が保持される）。
【００６９】
次に、図８および図９を参照して、本発明を具現化する方法および装置を概括的に説明する。図９には、ネットワークのノードＡ〜Ｄと、本発明を具現化するノード１とが示されている。ノードＡがノード１にパケットＰを転送し、パケットＰはパケットＰをノードＢ〜Ｄのうちの１つまたは複数まで転送させるための経路指定情報を含む。ノードＢ〜Ｄのうちのどれが選択されるか判定するのに経路指定情報がどのように使用されるかについては以下で詳細に説明するが、図９の例では、パケットＰは（新しいパケットＱとして）ノードＢに転送される。
【００７０】
ノード１は、パケット受信部２と、パケット処理部４と、状態変数更新部６と、リンクＩＤ選択部８と、リンク循環部１０と、リンクＩＤ記憶部１２と、データ構造検査部１４と、パケット作成部１６と、転送部１８と、複数の発信リンク２０とを備える。
【００７１】
図８に示すステップＳ１で、パケットＰがノード１のパケット受信部２により受信される。次いでパケットＰは、パケットＰから様々な情報を抽出し、その情報の各部分を状態変数更新部６、リンクＩＤ選択部８、リンクＩＤ記憶部１２、データ構造検査部１４およびパケット作成部１６に提供するように構成されているパケット処理部４に渡される。
【００７２】
これに関連してパケットＰは、パケットＰにより搬送されるデータを保持するデータ部分のみならず、ヘッダ部分に、状態変数、指標値および確率的データ構造（ブルームフィルタなど）を含む。状態変数更新部６はパケット処理部４から状態変数を受け取るように構成されており、リンクＩＤ選択部８はパケット処理部４から指標値および状態変数を受け取るように構成されており、データ構造検査部１４はパケット処理部４からデータ構造を受け取るように構成されており、パケット作成部１６はパケット処理部４から指標値、データ構造およびデータを受け取るように構成されている。またパケット作成部１６は状態変数更新部６から新しい状態変数も受け取るように構成されている。
【００７３】
図８のステップＳ２〜ステップＳ６はノード１のリンク循環部１０により制御される。これに関連してノード１は複数の発信リンク２０を利用することができ、複数のリンクはそれぞれ少なくとも１つのリンクＩＤと関連付けられており、複数のリンクのうちの少なくとも１つが複数のリンクＩＤと関連付けられている。リンク循環部１０は、複数の発信リンク２０を繰り返し循環し、現在どのリンクが処理されているかに関する情報をリンクＩＤ選択部８と転送部１８とに渡すように適合されている。ステップＳ２で、リンク循環部１０は処理のために次の発信リンクを選択する。リンクＩＤ選択部は、ステップＳ３で、現在のリンクに複数のリンクＩＤが関連付けられているかどうかチェックし、そうである場合には、ステップＳ４でリンクＩＤ選択部８は、パケット処理部４から受け取られる指標値および状態変数に基づいてリンクＩＤのうちの１つを選択する。リンクＩＤ選択部８が現在のリンクにただ１つのリンクＩＤだけが関連付けられていると判定した場合には、そのリンクＩＤが使用される。選択される（またはただ１つの）リンクＩＤはリンクＩＤ記憶部１２から取り出され、データ構造検査部１４に渡される。
【００７４】
これに関連して前の説明に戻ると、図９のリンクＩＤ選択部８は、図４を参照して先に説明したステップ１およびステップ２を実行するように構成されるはずである。というのは、複数のリンクＩＤのうちの１つの選択は複数の転送表のうちの１つの選択と類似するからである。したがって図９のリンクＩＤ記憶部１２は図４に示すＩＤ表に対応する。
【００７５】
ステップＳ５で、データ構造検査部１４は、受け取ったデータ構造を選択されたリンクＩＤのメンバであるかどうか検査し、検査結果が肯定である場合には、転送部１８に信号が送られて、転送部１８に現在処理中のリンクがパケットを転送するために準備されるべきであることを知らせる。
【００７６】
転送部により転送されるべきパケットは、パケット作成部１６により作成され、パケット処理部４から受け取られる指標値、データ構造およびデータを、状態変数更新部６から受け取られる新しい状態変数と共に含む。状態変数更新部６は、ステップＳ７で、パケット処理部４から受け取られる前の状態変数から新しい状態変数を決定する。状態変数を更新するために様々な方式については前述のとおりである。パケット作成部１６により作成されるパケットＱは転送部１８に送られる。転送部１８は、データ構造検査部１４からの信号がそうすべきであると指示する場合には現在のリンクに沿ってパケットＱを転送するように構成されている。図９に示す例では、データ構造検査部１４は、転送部１８がパケットＱをノードＢに向かうリンクに沿って転送すべきであると判定しており、これはステップＳ８で実行される。
【００７７】
リンク循環部１０は残りの発信リンク２０を循環し、ステップＳ６で、処理すべき次の発信リンクがあるかどうかチェックし、チェックに従って折り返しステップＳ２に戻る。
【００７８】
新しいパケットＱは、発信リンク２０のそれぞれについてではなく１回作成されさえすればよいことが理解されるであろう。加えて、リンクＩＤ選択部８により使用される状態変数はパケット受信部２により受け取られる状態変数であり、新しい状態変数は発信パケットＱに含まれると先に述べたが、新しい状態変数自体がリンクＩＤ選択部８により使用されることも可能である。すなわち、経路指定ノード（経路指定情報を作成するノード）が、経路指定情報を作成するときに、各ノードが状態変数をどのように使用し、更新しているか知っている限りにおいて、経路指定方法は意図されるように働く。また、指標値の有無および使用するかどうかは任意選択であることも理解されるであろう。というのは、リンクＩＤ選択部は代わりに、状態変数だけに基づいてリンクＩＤ（または経路指定表）を選択するように適合することもできるはずだからである。
【００７９】
本発明の一実施形態は以下の技術的利点のうちの１つまたは複数を有する。
・ループ防止のためにｚＦｉｌｔｅｒをキャッシュする必要がない
・元の転送方法の処理速度が維持される
・ネットワークに追加の状態が生じない
・転送効率が、ＴＴＬだけを用いたループ防止技術を用いる場合と比べてはるかに高い
・転送表より多数のｚＦｉｌｔｅｒ候補（少数の状態を用いた転送効率の最適化）
・いくつかの選択ポリシーに従って適切なｚＦｉｌｔｅｒを見つけられる可能性がより高い
・柔軟性、利用可能なリソースがあるときにより多くのｚＦｉｌｔｅｒ候補を試行することができる
【００８０】
前述の構成要素の１つまたは複数の動作は、機器または装置上で動作するプログラムによって制御され得ることが理解されるであろう。そのような動作プログラムはコンピュータ可読媒体上に記憶させることもでき、例えば、インターネットウェブサイトから提供されるダウンロード可能なデータなどといった信号において実施することもできるはずである。添付の特許請求の範囲は、動作プログラム自体、またはキャリア上のレコード、または信号、または他の任意の形態を含むものと解釈すべきである。
【００８１】
また、前述の実施形態には添付の特許請求の範囲により定義される本発明の範囲を逸脱することなく様々な改変が加えられ得ることも当業者は理解するであろう。
【００８２】
例えば、前述の実施形態では経路指定情報はブルームフィルタに含まれる。しかし、本発明はブルームフィルタの使用だけに限定されず、経路指定情報を、機能的にブルームフィルタを使用するのと同様の、経路指定情報を識別するために問い合わせることのできる集合要素関係へと符号化することを含む他のコンパクトな表現、例えば、Ａ  Ｐａｇｈらによる、「Ａｎ  Ｏｐｔｉｍａｌ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒ  Ｒｅｐｌａｃｅｍｅｎｔ」，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｓｉｘｔｅｅｎｔｈ  ａｎｎｕａｌ  ＡＣＭ−ＳＩＡＭ  ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｄｉｓｃｒｅｔｅ  ａｌｇｏｒｉｔｈｍｓ，ｐａｇｅｓ  ８２３〜８２９  （２００５）に記載されている表現などが使用されてもよい。また本発明は、例えば、Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒによる、「Ｃｏｍｐｒｅｓｓｅｄ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒｓ」，ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，Ｖｏｌ．１０，Ｎｏ．５，ｐ６０４  （２００２）、に開示されているような改変されたブルームフィルタを用いて実施されてもよい。
【００８３】
前述のように、本発明は、国際出願第ＰＣＴ／ＥＰ２００８／０６１１６７号明細書および国際出願第ＰＣＴ／ＥＰ２００８／０６３６４７号明細書に含まれる開示に厳密に基づくものであり、したがってこれら２つの開示の全内容は参照により本明細書に組み込まれる。上記説明のいずれかの部分が添付の特許請求の範囲に記載されるとおりに本発明を実行するのに不十分であるとみなされる場合には、これらの開示の内容を参照することができる。同様に、これらの開示の内容は、添付の特許請求の範囲の裏付けを提供するためにも使用することができる。
【図１】
0005551772.tif 000002
【図２】
0005551772.tif 000003
【図３】
0005551772.tif 000004
【図４】
0005551772.tif 000005
【図５】
0005551772.tif 000006
【図６】
0005551772.tif 000007
【図７】
0005551772.tif 000008
【図８】
0005551772.tif 000009
【図９】
0005551772.tif 000010