(57)【特許請求の範囲】
【請求項１】
パケットのルーティング情報を提供する方法であって、
ソースノードから１以上の宛先ノードへのルーティング情報を、集合メンバシップのコンパクト表現の中に符号化するステップを有し、
前記ルーティング情報は、１以上の識別子の表現を含み、
各識別子は、各ネットワークリンク、各ノード、又は、２以上のネットワークリンクを含む全体パス又は部分パスを識別し、
前記方法は、
前記１以上の識別子のｄ個（ｄは２以上の整数）の表現から、集合メンバシップのｄ個のコンパクト表現の候補を生成するステップと、
前記ソースノードから前記１以上のソースノードへ送信すべきパケットのヘッダの中に、集合メンバシップの前記コンパクト表現の１つを入れるステップと、
を有する、方法。
【請求項２】
前記ルーティング情報は、前記ソースノード又はルーティングサーバにおいて符号化される、
請求項１に記載の方法。
【請求項３】
前記パケットヘッダに含まれる集合メンバシップのコンパクト表現を識別する情報を、前記パケットヘッダの中に含めるステップ、
を更に有する、請求項１又は２に記載の方法。
【請求項４】
ネットワークを通ってパケットをルーティングする方法であって、
ネットワークノードにおいてパケットを受信するステップと、
前記ノードから前記パケットがこれに沿って送信されるべき１以上のリンクを判定するために、又は、前記ノードから前記パケットがそこへ送信されるべき１以上の他のノードを判定するために、又は、その両方のために、前記パケットのヘッダの中に集合メンバシップのコンパクト表現として含まれるルーティング情報を問い合わせるステップと、
前記判定された１以上のリンクに沿って、又は、前記判定された１以上の他のノードへ、又は、その両方で、前記パケットを転送するステップと、
を有し、
前記ルーティング情報は、１以上の識別子の複数の表現の候補の１つを含み、
各識別子は、各ネットワークリンク、各ノード、又は、２以上のネットワークリンクを含む全体パス又は部分パスを識別し、
前記ルーティングは、各々が前記１以上の識別子のｄ個（ｄは２以上の整数）の表現の候補の１つに対応するｄ個のルックアップテーブルから、前記１以上の識別子のうちの受信した表現に対応するルックアップテーブルを選択するステップを更に含む、
方法。
【請求項５】
ネットワークノードであって、
パケットを受信する手段と、
前記ノードから前記パケットがこれに沿って送信されるべき１以上のリンクを判定するために、又は、前記ノードから前記パケットがそこへ送信されるべき１以上の他のノードを判定するために、又は、その両方のために、前記パケットのヘッダの中に集合メンバシップのコンパクト表現として含まれるルーティング情報を問い合わせる手段と、
を有し、
前記ネットワークノードは、前記判定された１以上のリンクに沿って、又は、前記判定された１以上の他のノードへ、又は、その両方で、前記パケットを転送するように構成され、
前記ネットワークノードは、各々が１以上の識別子のｄ個（ｄは２以上の整数）の表現の候補の１つに対応するｄ個のルックアップテーブルから、前記１以上の識別子のうちの受信した表現に対応するルックアップテーブルを選択するように更に構成される、
ネットワークノード。
【請求項６】
パケットのルーティング情報を提供するネットワークノードであって、
ソースノードから１以上の宛先ノードへのルーティング情報を、前記ソースノードから前記１以上のソースノードへ送信すべきパケットのヘッダの中に含めるために、集合メンバシップのコンパクト表現の中に符号化するように構成され、
前記ルーティング情報は、１以上の識別子の表現を含み、
前記ネットワークノードは、
前記１以上の識別子のうちの少なくとも一部に関するｄ個（ｄは２以上の整数）の表現を生成し、
前記識別子の前記ｄ個の表現から集合メンバシップのｄ個のコンパクト表現の候補を生成し、
集合メンバシップの前記ｄ個のコンパクト表現の候補の１つを選択する
ことにより、前記ルーティング情報を符号化するように構成される、
ネットワークノード。
【請求項７】
前記１以上の識別子のうちの少なくとも一部に関するｄ個（ｄは２以上の整数）の表現を生成し、
前記識別子の前記ｄ個の表現から集合メンバシップのｄ個のコンパクト表現の候補を生成し、
集合メンバシップの前記ｄ個のコンパクト表現の候補の２以上を他のノードへ送信する
ことにより、前記１以上の識別子の表現を含むルーティング情報を符号化するように構成される、
請求項６に記載のネットワークノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークにおけるパケット転送に関する。特に、本発明は、パケットがどのリンクに沿って転送されるべきかをネットワークノードがパケットヘッダの中の転送情報から判定できるようにするため、転送情報がパケットヘッダの中に含まれるような方法に関する。
【背景技術】
【０００２】
２００８年６月１１日から１３日までストックホルムで開催されたＩＣＴ  Ｍｏｂｉｌｅ  Ｓｕｍｍｉｔの予稿集の中で発表された「ＲＴＦＭ：Ｐｕｂｌｉｓｈ／Ｓｕｂｓｃｒｉｂｅ  Ｉｎｔｅｒｗｏｒｋｉｎｇ  Ａｒｃｈｉｔｅｃｔｕｒｅ」の中でＭｉｋｋｏ  Ｓａｒｅｌａ、Ｔｅｅｍｕ  Ｒｉｎｔａ−Ａｈｏ、およびＳａｓｕ  Ｔａｒｋｏｍａによって記述されたＰｕｂｌｉｓｈ−Ｓｕｂｓｃｒｉｂｅ（「ｐｕｂｓｕｂ」）指向のネットワーキングは、第１に指定されるエンティティとしてホストとエンドポイントとに着目する元々のインターネットプロトコルとは対照的に、データに着目する。エンドポイントと、エンドポイント間のユニバーサルな接続性とを指定することに関するこの着目は、多くの良く知られた問題を引き起こす。第１に、現行のインターネットワーキングパラダイムでは、極悪な当事者もいれば利己的な当事者もいるにも関わらず、オープンなネットワーク内で当事者同士が相互に通信することができる。第２に、現代のアプリケーションの主要部分は、エンド・ツー・エンドの双方向通信の働きよりもむしろ、情報を広める働きを行っている。最後に、ハードウェアの観点からは、多くのタイプのネットワーク（例えば所定のタイプの無線、ケーブル、および光のネットワーク）では、ブロードキャスティングまたはマルチキャスティングは、単一の明確に識別された受信者にメッセージを送信することよりも、もっと自然で基本的な動作である。（「マルチキャスティング」は、指定された宛先のグループに情報を同時に配信することであり、「ブロードキャスティング」は、原理的にはネットワーク上のいかなるデバイスによっても受信できるように情報を送信することを言う。）これら３つの問題に照らして、ｐｕｂｌｉｓｈ−ｓｕｂｓｃｒｉｂｅパラダイムに基づくインターネットワーキングの方が、現行の送信者指向のものと比べて、より自然で、効率的で、実装が容易であろうということが提案されている。
【０００３】
次いで、ＨＴＴＰ、ピア・ツー・ピアのトラヒック、ＲＳＳフィード、ＰＳＩＰイベント、Ｓｅｒｖｉｃｅ  Ｏｒｉｅｎｔｅｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＳＯＡ）等の場合には、データをより詳しく見ると、このトラヒック（および恐らく他のトラヒックも）の大部分は、かなり単純な情報の繰り返しで構成されているように見える。例えば、動的なウェブページでさえ、典型的には、少量のクライアント固有ＨＴＭＬコードに結合された多数の静的な構成要素で構成される。多くのピア・ツー・ピアのネットワークでは、主な問題は、見込まれる消費者にできる限り近づくようにデータを最適なやり方で事前配信することである。
【０００４】
一般に、音声通話のようなリアルタイム双方向トラヒックという例外も可能性としてはあるが、現代のネットワークトラヒックの大半がデータ指向であると主張することができる。すなわち、アプリケーションは、接続を作り出すことに関心を持っているのではなく、十分に定義されたデータの断片を転送することに関心を持っているのである。一部のデータは、本質的にはトランザクションであり、すなわち、寿命が短く、かつ、通信の当事者に固有であるが、大部分のデータは、送信者および受信者には非依存であるように思える。例えば、ユーザが最新のＣＮＮニュースを知りたいと望む場合、ユーザＩＤに関係なくビットは基本的に（大体）同じであり、ユーザは、ビットが物理的にどこから来るのか気にしない。
【０００５】
比較的単純で静的ですらあるデータを配信するための技術が非常に多種多様であることから、相互接続の欠如に起因する多くの問題が生じている。将来のデータ配信標準のための競争は、もう始まっている。（現行のアーキテクチャの中での相互接続の欠如およびその他の欠陥によって生じた）動機付けが存在するのだから、データを発行して検索することについての何らかの標準的なやり方が１０年以内に提供されることが予想される。
【０００６】
Ｐｕｂｌｉｓｈ−Ｓｕｂｓｃｒｉｂｅパラダイムの背景にある１つの概念は、あるノードから別のノードへの不要なデータ配信を回避できるということである。今日のネットワークの場合のように、送信者は、グローバルに一意であるＩＰアドレスを用いて、何ら受信者からの明示的な要求がなくてもＩＰアドレスで識別されたホストにデータパケットを配信することができる。この結果、ユーザは、不要な、場合によっては悪質なデータを受信することになるため、これによって多くの問題が生じる。ＩＰアドレススキームで用いられているような、受信者に基づいたアドレス指定を廃止すれば、宛先ホストがデータを要求していないのに宛先ホストにデータを送信する可能性がこれによって除去されるのだから、この問題は克服することができるであろう。しかし、ＩＰアドレススキームが廃止された場合、ネットワークを通してパケットをルーティングするのに用いられうる新たなメカニズムを提供することが必要であろう。
【発明の概要】
【０００７】
本発明の第１の態様は、パケットのルーティング情報を提供する方法を提供する。当該方法において、ソースノードから１以上の宛先ノードへのルーティング情報が、集合メンバシップのコンパクト表現の中に符号化される。前記コンパクト表現は、前記ソースノードから前記１以上のソースノードへ送信すべきパケットのヘッダの中に入れられる。
【０００８】
集合メンバシップの前記コンパクト表現は、ブルームフィルタを含んでもよい。
【０００９】
前記ルーティング情報は、各々が各ネットワークリンク又は各ネットワークノードを識別する複数のリンク識別子又はノード識別子を含んでもよい。あるいは、前記ルーティング情報は、後で「仮想リンク」と呼ばれる、２以上のネットワークリンクを含む部分パスを識別する識別子を含んでもよい。（ここで使用されるように、「リンク」はネットワークの２つのノードを直接接続し、ネットワークを通る「パス」は、概して、複数の「リンク」を含む。）他のルーティング情報は、管理領域又は物理ネットワークエリアを識別する、ネットワーク領域の識別子を含んでもよい。
【００１０】
前記ルーティング情報は、前記ソースノードから前記１以上の宛先ノードへの１以上のパスを定義することができる。あるいは、前記ルーティング情報は、前記ソースノードから２以上の異なる宛先ノードへの各パスを定義してもよい。パスの一部が重複している場合、そのような重複している情報は１度だけ符号化され、これにより、パスの集合の代わりに配信ツリーを表す。
【００１１】
前記ルーティング情報は、前記ネットワークのソースノードで符号化されてもよい。あるいは、前記ルーティング情報は、ルーティングサーバで符号化されて、符号化されたルーティング情報が前記ソースノードへ転送されてもよい。
【００１２】
前記方法は、前記パケットのヘッダの中に含まれる前記ルーティング情報を問い合わせることにより、前記ソースノードから前記１以上の宛先ノードへのパスを判定するステップを含んでもよい。
【００１３】
前記方法は、識別子のｄ個の表現から、集合メンバシップのｄ個のコンパクト表現の候補を生成するステップを含んでもよい（ｄは２以上の整数である）。
【００１４】
その後、集合メンバシップの前記コンパクト表現の１つが、使用のために選択されてもよい。この選択は、ユーザが決定した基準（例えば、どの表現が擬陽性を生み出す確率が最も低いか、どの表現が複数の識別子のうちの１以上を含むサブセットに関して擬陽性を生み出す確率が最も低いか、又は、どの表現が複数の識別子のうちの１以上を含むサブセットに関して擬陽性を生み出さないか）に従って行われてもよい。
【００１５】
集合メンバシップの選択されたコンパクト表現は、例えば、ルーティング情報を提供するためにパケットヘッダに含められてもよい。
【００１６】
本発明の第２の態様は、ネットワークを通ってパケットをルーティングする方法を提供する。パケットが、ネットワークノードにおいて受信される。前記ノードから前記パケットがこれに沿って送信されるべき１以上のリンクを判定するために、又は、前記ノードから前記パケットがそこへ送信されるべき１以上の他のノードを判定するために、又は、その両方のために、前記パケットのヘッダの中に含まれるルーティング情報が問い合わせられる。前記ルーティング情報は、前記パケットのヘッダの中に集合メンバシップのコンパクト表現として含まれる。前記パケットは、前記判定された１以上のリンクに沿って、又は、前記判定された１以上の他のノードへ、又は、その両方で、前記ネットワークノードから転送される。
【００１７】
集合メンバシップの前記コンパクト表現は、ブルームフィルタを含んでもよい。
【００１８】
前記ルーティング情報は、各々が各ネットワークリンク又は各ネットワークノードを識別する複数のリンク識別子を含んでもよい。あるいは、前記ルーティング情報は、２以上のネットワークリンクを含む部分パスを各々が識別する１以上の識別子を含んでもよい。
【００１９】
前記ルーティング情報は、前記１以上の識別子の複数の表現の候補の１つを含んでもよい。
【００２０】
前記ルーティングは、複数のルックアップテーブルから、前記１以上の識別子のうちの受信した表現に対応するルックアップテーブルを選択するステップを含んでもよい。
【００２１】
本発明の第３の態様は、パケットを受信する手段を有するネットワークノードを提供する。前記ネットワークノードは更に、前記ノードから前記パケットがこれに沿って送信されるべき１以上のリンクを判定するために、又は、前記ノードから前記パケットがそこへ送信されるべき１以上の他のノードを判定するために、又は、その両方のために、前記パケットのヘッダの中に集合メンバシップのコンパクト表現として含まれるルーティング情報を問い合わせる手段を有する。前記ネットワークノードは、前記判定された１以上のリンクに沿って、又は、前記判定された１以上の他のノードへ、又は、その両方で、前記パケットを転送する。
【００２２】
前記ルーティング情報は、各々が各ネットワークリンク又は各ネットワークノードを識別する複数のリンク識別子又はノード識別子を含んでもよい。あるいは、前記ルーティング情報は、２以上のネットワークリンクを含む全体パス又は部分パスを各々が識別する１以上の識別子を含んでもよい。
【００２３】
前記ネットワークノードは、各々が前記１以上の識別子のｄ個の表現の候補の１つに対応するｄ個のルックアップテーブルから、前記１以上の識別子のうちの受信した表現に対応するルックアップテーブルを選択するように構成されてもよい。
【００２４】
集合メンバシップの前記コンパクト表現は、ブルームフィルタであってもよい。
【００２５】
前記第１の態様の方法は、ネットワークを通るパスを定義するステップを有してもよい。前記パスは複数の区分を含み、各区分は関連する識別子を有する。前記パスに含まれる各区分に関連する識別子とは異なる識別子が、前記パスに割り当てられる。前記ルーティング情報を符号化する前記ステップは、前記パスの各区分に関連する識別子を符号化するのではなく、前記パスに割り当てられた識別子を符号化するステップを有する。
【００２６】
前記パスに割り当てられる識別子は、前記パスに含まれる各区分に関連する識別子とは無関係であってもよい。
【００２７】
前記パスの少なくとも１つの区分は、２以上のリンクを含んでもよく、各リンクは、２つのネットワークノードを直接接続してもよい。
【００２８】
本発明の第４の態様は、パケットのルーティング情報を提供するネットワークノードであって、ソースノードから１以上の宛先ノードへのルーティング情報を、前記ソースノードから前記１以上のソースノードへ送信すべきパケットのヘッダの中に含めるために、集合メンバシップのコンパクト表現の中に符号化するように構成される、ネットワークノードを提供する。
【００２９】
前記ネットワークノードは、例えば当該ネットワークノードがルーティング機能ノードである場合に、集合メンバシップの前記コンパクト表現を前記ソースノードへ送信するように構成されてもよい。
【００３０】
あるいは、前記ネットワークノードは前記ソースノードであってもよく、この場合、前記ネットワークノードは、集合メンバシップの前記コンパクト表現を、前記ソースノードから送信すべきパケットのヘッダの中に含めるように構成されてもよい。
【００３１】
集合メンバシップの前記コンパクト表現は、ブルームフィルタであってもよい。
【００３２】
前記ネットワークノードは、１以上の識別子のうちの少なくとも一部に関するｄ個の表現を生成し、前記識別子の前記ｄ個の表現から集合メンバシップのｄ個のコンパクト表現の候補を生成し、集合メンバシップの前記ｄ個のコンパクト表現の候補の１つを選択することにより、前記１以上の識別子の表現を含むルーティング情報を符号化するように構成されてもよい。
【００３３】
あるいは、前記ネットワークノードは、１以上の識別子のうちの少なくとも一部に関するｄ個の表現を生成し、前記識別子の前記ｄ個の表現から集合メンバシップのｄ個のコンパクト表現の候補を生成し、集合メンバシップの前記ｄ個のコンパクト表現の候補の２以上を他のノードへ送信することにより、前記１以上の識別子の表現を含むルーティング情報を符号化するように構成されてもよい。前記他のノードは例えば前記ソースノードであってもよく、その後、当該ソースノードは、受信したコンパクト表現の候補の１つを選択し、当該選択したコンパクト表現をパケットヘッダの中に含めることができる。あるいは、前記他のノードは、受信したコンパクト表現の候補の１つを選択してもよいが、自分自身は当該選択したコンパクト表現を使用せずに、当該選択したコンパクト表現を他のノードへ転送してもよい。
【００３４】
各識別子は、各ネットワークリンク、各ノード、又は、２以上のネットワークリンクを含む全体パス又は部分パスを識別してもよい。
【００３５】
本発明の第５の態様は、複数の識別子の集合のコンパクト表現を生成する方法を提供する。前記方法は、最初に、前記識別子に関するｄ個の表現を生成するステップを有し、集合メンバシップのｄ個のコンパクト表現の候補が、前記識別子の前記ｄ個の表現から生成される。その後、集合メンバシップの前記ｄ個のコンパクト表現の候補の１つが、使用のために選択される。
【００３６】
前記選択は、ユーザによって事前定義された基準に基づいて行われてもよい。
【００３７】
前記方法は、適当なプロセッサによって（例えば、ネットワークノードに含まれるか又はネットワークノードを構成するプロセッサにおいて）実装可能である。
【００３８】
前記識別子の前記表現は、コンパクト表現であってもよい。識別子の「コンパクト」な表現とは、それが表す識別子よりも少ない数のビット（好ましくは、大幅に少ない数のビット）が１に設定される表現を意味する。コンパクト表現の使用には、識別子自体の長さ及び形式には（あるとしても）少ない制限しか存在しないという利点がある。
【００３９】
集合メンバシップの前記コンパクト表現は、ブルームフィルタであってもよい。
【００４０】
本発明の他の態様は、命令を含んだコンピュータ読み取り可能な物を提供する。当該命令は、プロセッサ上で実行されると、当該プロセッサに、本発明の第１の態様の方法を実行させるか、又は、本発明の第２の態様の方法を実行させる。
【００４１】
本発明はまた、１以上の識別子のうちの少なくとも一部に関するｄ個の表現を生成し、前記識別子の前記ｄ個の表現から集合メンバシップのｄ個のコンパクト表現の候補を生成することにより、前記１以上の識別子の表現を含む、パケットのルーティング情報を符号化するネットワークノードを提供する。
【００４２】
本発明はまた、１以上の識別子の表現を含む、パケットのルーティング情報を提供するネットワークノードを提供する。前記ネットワークノードは、集合メンバシップの複数のコンパクト表現の候補を受信し、事前決定された基準に従って集合メンバシップの前記コンパクト表現の１つを選択するように構成される。ユーザ定義であってもよい前記基準は、例えば、どの表現が擬陽性を生み出す確率が最も低いか、どの表現が複数の識別子のうちの１以上を含むサブセットに関して擬陽性を生み出す確率が最も低いか、又は、どの表現が複数の識別子のうちの１以上を含むサブセットに関して擬陽性を生み出さないか、であってもよい。
【００４３】
本発明はまた、ソースノードを提供する。前記ソースノードは、集合メンバシップのコンパクト表現を受信し、ルーティング情報を提供するために集合メンバシップの前記コンパクト表現をパケットヘッダの中に含めるように構成される。
【００４４】
集合メンバシップの前記コンパクト表現は、ブルームフィルタであってもよい。
【図面の簡単な説明】
【００４５】
本発明の実施形態について、添付の図面を参照しながら、例証として、さらに記述しよう。
【図１】ブルームフィルタに項目を追加するプロセスを図解する略図である。
【図２】ブルームフィルタにデータ項目が追加されたかどうかを検証するプロセスを図解する略図である。
【図３】偽陽性を返すブルームフィルタ検証を図解する略図である。
【図４】本発明の一実施形態による、ネットワークを通るパケット転送を図解する図である。
【図５】本発明の一実施形態による、ネットワークを通るパケット転送を図解する図である。
【図６】本発明の別の実施形態による、ネットワークを通る仮想リンクの作成を図解する図である。
【図７】仮想リンク・セットアップ・パケットの略図である。
【図８】ネットワークを通る仮想リンクを作成する別の方法を図解する図である。
【図９】Ｍｕｌｔｉｃａｓｔツリーを作成する仮想リンクを図解する図である。
【図１０】１個のパケットについてネットワークを通る複数のパスを図解する図である。
【図１１】（ａ）及び（ｂ）は、パスの自己生成を図解する図である。
【図１２】パケットヘッダ内での転送情報の提供を図解するブロックフロー図である。
【図１３】図５の実施形態による、ネットワークを通るパケット転送を図解するブロックフロー図である。
【図１４】識別子に対応するタグの生成を図解する図である。
【図１５】本発明の別の態様による転送ノードを図解する略図である。
【図１６】パケットヘッダの略図である。
【図１７】本発明の別の実施形態による方法を図解する図である。
【図１８】本発明の一実施形態によって得られうる偽陽性率の削減を図解する図である。
【図１９】偽陽性率を図解する図である。
【図２０】本発明の別の態様の方法のブロックフロー図である。
【発明を実施するための形態】
【００４６】
本発明について、ルーティング情報がブルームフィルタに含まれる実施形態に関して記述しよう。しかし、本発明はブルームフィルタに限定されるのではなく、ルーティング情報を、機能性ではブルームフィルタを用いるのと同様にルーティング情報を識別するために問い合わせ可能な集合メンバシップへと符号化することを含む、他のコンパクト表現が用いられてもよい。これは例えば、Ｄｉｓｃｒｅｔｅアルゴリズムに関する第１６回年次ＡＣＭ−ＳＩＡＭシンポジウム（２００５）の予稿集の８２３頁から８２９頁までに記載された「Ａｎ  Ｏｐｔｉｍａｌ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒ  Ｒｅｐｌａｃｅｍｅｎｔ」の中でＡ  Ｐａｇｈ他によって記述された表現のようなものである。また、本発明は、例えばＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、Ｖｏｌ．１０、Ｎｏ．５、ｐ６０４（２００２）の「Ｃｏｍｐｒｅｓｓｅｄ  Ｂｌｏｏｍ  Ｆｉｌｔｅｒｓ」の中でＭ．Ｍｉｔｚｅｎｍａｃｈｅｒによって開示されたもののような、修正されたブルームフィルタを使って達成されてもよい。
【００４７】
本発明は、ブルームフィルタ（ＢＦ）に基づいた新たなソースルーティングスキームを提供し、この場合、ルーティング情報はパケットヘッダの中のＢＦに含まれる。通常、「ソースルーティング」という用語は、パケットがソースノードから宛先ノードまでたどることになるパス全体をソースノードが制御する時に用いられる。用いられる他の用語として、正確なパスが既知である場合の「ストリクト・ソース・ルーティング」と、パケットが通過することになるネットワーク内の一部のポイントだけをソースノードが定義する場合の「ルーズ・ソース・ルーティング」とがある。
【００４８】
提案する解決策は、ルーティング機能性が宛先または宛先の集合までのパケットのパス全体を知っており、この情報に基づいてパケットヘッダを作成するという意味で「ソースルーティング」である。また、パス上の各ノードが知られているのだから、これはストリクト・ソース・ルーティングであると考えることもできる。（留意すべきだが、以下で説明するように、ノードは本発明では転送要素として動作するのであって、パケットがどのルートをたどるべきかについてノード自身が決定を行うことはない。）作成されたパケットヘッダは、パケットに組み込むため、ソースノードに与えられるかまたはソースノードで構築される。すべての個々の転送ステップが含まれるＢＦベースのヘッダを用いる時には、転送ノードは、いかなるノードまたはリンク情報であろうとまったくヘッダから抽出することはできない。従って、ノードは、パケットがどこへルーティングされることになるのか実際には知らない。パス上の各ノードは、自分自身のリンク情報を用いて、パケットがどこへ渡されるべきかを検証することができるだけである。
【００４９】
本発明のブルームフィルタベースの方法を用いて、ネットワークノード内で必要とされる状態情報を最小化することも可能である。
【００５０】
本発明の実施形態について記述する前に、ブルームフィルタの予備的説明をしよう。
【００５１】
ブルームフィルタ
ブルームフィルタ（ＢＦ）は、集合メンバシップのコンパクト表現の中にデータ項目を含める効率的なやり方を提供する。データに対して少数の別個のハッシュ値が算出され、これらのハッシュ値は、ブルームフィルタのビット列の中の所定のビットを表しており、それが項目を追加する間に１に設定される。
【００５２】
同じ方法論を用いて、集合表現の中にリンク情報を挿入することも可能であり、その場合、リンク情報は、ネットワーク内の２つのノード間のリンクに対応する。データ項目が追加されたブルームフィルタからは、追加された情報を抽出することは不可能である。可能なのは、その項目がその中に含まれているか否かを検証することだけである。偽陽性（データ項目が実際には追加されていないのに、追加されたと通知すること）の可能性は若干あるが、偽陰性の可能性はない。これをルーティングに適用する場合、パケット転送に用いられるＢＦは、偽陽性が原因でネットワーク内で追加パケットの増殖を生み出す可能性があるが、それはｐｕｂ／ｓｕｂネットワークでは、偽陽性率を制御するやり方がある限り、有害とはみなされない。ＢＦの場合、それは、追加されることになる項目の数とフィルタのサイズとを制御することが可能であることを意味する。しかし、もっと重要なことだが、少なくとも集合表現に追加されたリンクを介して、データは常にルーティングされる。
【００５３】
結果として、ＢＦ（例えば長さ１２８ビット）をパケットヘッダに追加することができ、そしてそれは、ソースノードから宛先ノードまでの全ルートを含む。これは、エンド・ツー・エンドであってもよいし、元のデータ発行者から加入者までのパスの一部だけであってもよい。ネットワークノードでは、最小限の転送情報だけを維持すればよい。例えば、各ノードは、典型的には、ルーティングテーブルを維持し、各テーブルエントリは、所与のリンクを介して送信されることになるパケットを識別するのに必要な情報を保持する。その場合、ノードは、自身が接続しているノードの各々について転送テーブルの中で１つのエントリだけを必要とするということでよい。
【００５４】
転送プロセスは効率的であり、転送テーブルエントリの中のパケット識別情報は、パケットヘッダ内のＢＦとの間でビット単位でＡＮＤ演算され（この場合、「ＡＮＤ演算される」とは、論理ＡＮＤ演算を意味する）、そして結果がパケット識別情報に等しい場合、パケットは対応する送出リンクへ転送される。結果が等しくない場合、特定のリンクの識別子がブルームフィルタに追加されなかったのだから、パケットはそのリンクへは転送されない。
【００５５】
従って本発明は、ブルームフィルタに基づいてパケットヘッダの中にコンパクトなソースルーティング情報を提供することができる。これによって、ネットワークノード内に保持されなければならない状態情報が最小化される。
【００５６】
さらに留意されることだが、ノード間のリンクに名前を付ける代替的方法がいくつかある。識別子は自由な形式でよく、その場合、それらのブルームフィルタ表現が、識別子に対してｋ個の異なるハッシュ値をとるような通常のやり方で演算される。あるいは、リンク名が、ｋ個の「１」のビットおよびｍ−ｋ個の「０」のビット、または、ｋ−ｚ．．、ｋ−１、ｋ、ｋ＋１、．．ｋ＋ｚ個の「１」のビット（ｚは非常に小さい）と対応する個数の「０」のビットとで、直接構築されてもよい。その場合、そのようなハッシングは、ブルームフィルタを構築するためには必要でない。いずれの場合にも、命名スキームは、ハッシュの衝突を避けるために、名前に対して十分なエントロピー（ランダムネス）を符号化しなければならない。自由形式のリンク識別子とブルームフィルタ対応のｋ−ｏｆ−ｍビット識別子とを区別するため、本発明では後者をリンクＩＤと呼ぶ。
【００５７】
ブルームフィルタ（ＢＦ）は、フィルタと呼ばれる集合のコンパクト表現に対してデータ要素を追加し、後でその要素が以前にそれに追加されたかどうかをテストするための、簡単なやり方である。ＢＦは、所定のビット数、例えば１２８ビット、を含むビット列であり、それは当初はすべて０に設定される。ＢＦのサイズは、用途によって異なりうる。一例として、図１では、ＢＦのビット数は８である。一般的には、８ビットのＢＦは非常に小さいＢＦであろうから、実際には、いかなる目的にも使用できないであろう。ＢＦにデータ項目を追加することは、１個の識別子から複数の別個のハッシュ値が演算されるプロセスである。図１の例の場合、３つの異なるハッシングアルゴリズムを識別子「データ１」に適用することによって３つの別個のハッシュ値が、これらの値の各々が１と８の間にあるように演算される。これらの値の各々は、ＢＦ内の１ビットを表す。ハッシュ値が算出された後、ＢＦ内の対応する各ビットが１に設定される。図１の例では、３つのハッシュ値は３、６、１であり、ブルームフィルタの中の第１、第３、第６ビットが「１」に設定される。これは、識別子「データ１」についてのリンクＩＤを構成する。
【００５８】
また、図１は、別の識別子「データ２」をＢＦに追加することも示す。別個のハッシュ値が同様に算出され、そして、対応するビットがＢＦにおいてすでに１に設定されている場合、ビットは１のままである。図１の例では、「データ２」から得られた３つのハッシュ値は、４、７、１であり、ブルームフィルタの中の第４および第７が「１」に設定される（第１ビットは、「データ１」がブルームフィルタに追加された時に、すでに「１」に設定されている。項目がこのように追加される場合、いずれかの項目をＢＦから削除する可能性がないのは明らかであり、値「１」を持つビットが１つ以上のデータ項目から来るかどうかは誰にも分からない。（これらの制限に対する解決策が提案されているＢＦの変形が存在し、例えば、各ビットに対してカウンタが添付されている。項目が追加されて対応するビットが１に設定される度にカウンタが増える。項目を削除すると、カウンタ値は減るであろうし、値がゼロになると、対応するビットもゼロに設定することができる。しかし、この解決策は、１ビットでもカウンタ値のオーバフローがある場合に問題をもたらす可能性があり、値を減らすことにはもはや信頼性がない。カウンタ値を含めることのもう１つのマイナス面は、ＢＦのサイズが増えることであり、もはや、含められたデータ項目のコンパクト表現とは言えなくなる。本発明はコンパクトなＢＦを必要としており、本発明の基本形としては、ＢＦから項目を削除する必要はない。ＢＦは、使用後は廃棄される。）
特定のデータ項目がＢＦに追加されたかどうか検証したい場合、データに対する必要な数の別個のハッシュ値を算出することによってプロセスを開始し、結果として、ＢＦビット列の中の所定のビットに対応する数字の集合が得られる。検証プロセスの間、ＢＦの中のこれらのビットの値がチェックされ、すべての値がＢＦの中で１に設定されている場合、検証プロセスはｔｒｕｅを返し、いずれかのビットが０である場合、検証プロセスはｆａｌｓｅを返す。これを図２に図解するが、図２は、「データ１」が図１で作成されたブルームフィルタのメンバであるかどうかチェックするプロセスを示す。ブルームフィルタを作成するために用いられたのと同じ３つのハッシュアルゴリズムを用いて、３つのハッシュ値が「データ１」について作成され、そして、これらは３、６、１である。ブルームフィルタがチェックされると、ブルームフィルタの第３、第６および第１ビットがすべて「１」に設定されていることが分かり、これは、「データ１」がブルームフィルタに含まれていることを（正確に）示す。
【００５９】
ブルームフィルタの１つの特徴は、ある項目がブルームフィルタのメンバであるかどうかを検証するプロセスが、完全には正確でなく、「偽陽性」を生じる可能性があるということである。しかし、「偽陰性」を生じる可能性はない。データ項目が実際に含まれていた場合、対応するブルームフィルタのビットはすべて「１」であろうから（算出プロセスは、ブルームフィルタに項目を追加する間と検証の間とは同じであるため）、フィルタ検証は常に「ｔｒｕｅ」を返す。こうして、正確な応答が得られる。しかし、検証プロセスでチェックされたビットのうちのいずれかがゼロであることが分かった場合、検証は、「ｆａｌｓｅ」を返し、その項目はブルームフィルタに追加されていなかったことが分かる。
【００６０】
しかし、図３に示すように、たとえばデータ項目がフィルタに追加されていなくてもフィルタ検証がｔｒｕｅを返すことがありうる。図３の例では、「データ３」から得られた３つのハッシュ値は、４、６、１であり、ブルームフィルタの第４、第６、第１ビットはすべて「１」であると分かり、従って、検証プロセスは、「データ３」がブルームフィルタに含まれているということを返す。しかし、図１でブルームフィルタが作成された時に「データ３」はブルームフィルタに追加されなかったのだから、この結果は、不正確であり、この場合、検証は「偽陽性」を返すと言える。
【００６１】
偽陽性率は、フィルタの長さと、フィルタに追加された項目の数とに依存する。
【００６２】
ブルームフィルタをルーティングに利用する
本発明によれば、ネットワークの各リンク、すなわち２つのノード間の接続は、識別子（または「名前」）を有する識別可能なデータ項目であるとみなされる。従って、本発明は、パケットが要求される場合、ネットワークを通るパスがソースノードから宛先ノードまで選択され、それがリンク識別子のシーケンスとして記述されうることを提案する。リンク識別子のシーケンスは、ＢＦへと符号化され、そして、ＢＦがパケットヘッダに入れられる。
【００６３】
あるいは、ネットワークを通るパスを構成するリンクを識別する代わりに、パス沿いのノードを識別することによってパスを定義することができるだろう。しかし、パスの２つのノード間で２つ以上の異なるリンクが存在する可能性がある場合、そのようなスキームでは、例えば、並行するリンク間でトラヒック負荷をバランスさせる必要がある場合などは、含まれる情報が減り、また、あまり適正でない動作が行われるであろう。従って、一般性を失わずに、本発明の好適実施形態は、パスを構成するリンクによってパスを識別するという点に限って記述するが、理解されるべきだが、本発明はこれに限定されない。但し、留意されるべきだが、純粋な無線ネットワークの場合、例えばＭｏｂｉｌｅ  Ａｄ  Ｈｏｃ  Ｎｅｔｗｏｒｋ（ＭＡＮＥＴ）には、識別可能なリンクは存在せず、従って、そのような環境では、本発明はリンク識別子の代わりにノード識別子を用いるであろう。さらに、留意しなければならないことだが、ノードＩＤが（一方向の）リンクＩＤの代わりに用いられる場合、過度のルーピングを避けるメカニズムが必要であり、例えば、各パケットが存続期間の指標や少数の最近訪問したノードの識別子を搬送してもよいし、あるいは各ノードが、最近出会ったパケットを十分な数だけ記憶してもよい。
【００６４】
ネットワーク内のノードは、どの送出リンクＩＤがパケットヘッダ内のブルームフィルタに追加されたのかを判定するためにパケットヘッダ内のブルームフィルタに問い合わせることによって、ノードからどの送出リンクに沿って自分がパケットを転送すべきかを判定することができ、例えば特定の送出リンク識別子がパケットヘッダ内のブルームフィルタに追加された場合、パケットはそのリンクに沿って転送される。このプロセスは、パスに沿って各ノードで繰り返される。（パスが、パスを構成するリンクの観点からではなくてパス沿いのノードの観点から定義される場合、ノードは、他のどのネットワークノードに自分がパケットを送信すべきかを判定するため、パケットヘッダ内のブルームフィルタに問い合わせるであろうし、そして、パケットは、ブルームフィルタに問い合わせることによって得られたノードに転送される。）
本発明は、ＢＦがデータ項目のコンパクト表現であり、かつ、データ項目がフィルタに追加されたかどうかについてＢＦが常に正確な応答を返すという意味で、ＢＦの利点を利用する。「ｐｕｂ／ｓｕｂ」ルーティングの場合、確率が低い限り、偽陽性は問題ではない。偽陽性は、パケットが間違った宛先に配信される原因となるが、それは、偽陽性率が制御されうる限り、有害とはみなされない。ＢＦでは、偽陽性率は、ＢＦの長さと、データ項目を表すビット数と、フィルタに追加されたデータ項目の数とに依存する。
【００６５】
本発明の一実施形態について、図４乃至図１１を参照しながら記述しよう。本実施形態は、ブルームフィルタの生成に関する。
【００６６】
図４は、ノードＲ１乃至Ｒ５を有する単純なネットワークの略図である。パケットソース１が、ノードＲ１に接続し、パケット宛先（または「シンク」）２が、ノードＲ３に接続している。ノードＲ１乃至Ｒ５のうちの２つの間の各リンクは、リンク識別子を使って提供され、図４の実施形態では、直接のブルームフィルタ対応リンクＩＤが用いられ、それらは、各リンクが、各方向に１つずつ、２つの別個のリンクＩＤを有するように、有向の識別子として生成される。これは、（以下で述べる）一部の状況でループを回避するために必要である。一例として、ノードＲ１からノードＲ２までのリンクは、リンクＩＤ  ００１００１００１  を有し、ノードＲ２からノードＲ１までの逆リンクは、リンクＩＤ  １１０００１０００  を有する。例示したリンクＩＤは、例として９ビットと非常に短いものが選択されているが、実際は、これより長いであろう。
【００６７】
図４の実施形態は、ソースノードと宛先ノードとの間でデータを捜し出して配信するのに必要な機能性が、Ｒｅｎｄｅｚｖｏｕｓ（ランデブー）、Ｒｏｕｔｉｎｇ（ルーティング）、Ｆｏｒｗａｒｄｉｎｇ（転送）という３つの異なる動作で成り立つとみなすことができるようなＰｕｂ／Ｓｕｂネットワークに関する。大まかには、ランデブーメカニズムは、ネットワーク内での位置情報の発行を維持することに責任を持ち、ルーティングメカニズムは、ランデブーシステムの中に維持される情報に基づいてデータ位置から加入者ノードまでのルートを作成して構成することに責任を持ち、転送機能は、ネットワークを通る実際のデータパケットを転送することに責任を持つ。これらを図４にそれぞれ項目３、４、５として略示する。
【００６８】
ソース１は、発行Ｐを発行すると仮定する。この情報は、発行Ｐがその現在位置をマッピングするようにランデブーシステム３に格納される。シンク２でユーザが発行２を購読する場合（図１１のステップ１）、発行Ｐの位置情報は、ランデブーシステム３から見つけることができる（図１１のステップ２）。これは、データの現在位置とそれが配信される必要がある宛先とについての情報を提供する。
【００６９】
ルーティング機能４は、ソース１と宛先（シンク２）との間の転送パスを構築するためにソースノード情報および宛先ノード情報を必要とする。ルーティング機能４は、ネットワークリンクと、関連するリンクＩＤと、リンクが接続するノードとについての情報を維持するが、例えばルーティング機能の中に維持される情報は、ノードペアと、各ノードペアについての、それらの間のリンクのリンクＩＤとであってもよい。リンクＩＤと、リンクが接続するノードとについての情報がルーティングレイヤに存在した後ならば、ソースノード情報および宛先ノード情報を用いてネットワークを通るパスを構築することができる。
【００７０】
このようにして、ルーティング機能は、ネットワークトポロジについての知識を有する。ルーティング機能は、ノードＡとノードＢとの間にパスを構築するための要求を受け取ると、ＡとＣおよびＢとＣが直接接続している場合、リンクを用いて例えばＡからＣまでの、およびＣからＢまでのパスを作成することができる。従って、ルーティング機能４は、シンク２がソース１に発行Ｐを要求したことを通知される場合、ソースノード情報および宛先ノード情報に基づいて、ソース１から宛先２までのパスを作成することができる（図１１のステップ３）。図４の例では、ルーティングシステムは、ネットワークトポロジ情報を使用して、データがパスＲ１−Ｒ２−Ｒ３を移動する必要があると判定する。
【００７１】
判定されたパスは、リンク識別子のシーケンスとして表されてもよく、この場合、リンクＲ１からＲ２までと、リンクＲ２からＲ３までとで形成されたパスを示すために｛００１００１００１，００１０１１０００｝として表されてもよい。これを行うため、ルーティング機能は、図１１のステップ３で定義したパスの中の各リンクのリンクＩＤを判定または検索する（図１１のステップ４）。
【００７２】
リンクＩＤを判定するやり方はいろいろある。それらがノードによって自動的に生成され（例えばあるノードが、自分が直接接続していると分かっているノード群に対する自分自身の送出リンクにリンクＩＤを割り当てることもできる）、その後、ルーティング機能に通信されてもよいし、あるいは、それらが他のインスタンスによって割り当てられ、ノード上で構成されてもよい。リンクＩＤが、例えば、必要数のハッシングアルゴリズムを根底にある識別子に適用して、結果として得られるハッシュ値からビットマスクを得ることによって得られてもよい。しかし、本発明において、リンクＩＤが、ＢＦの追加と検証とに直接適用されうるビットマスク以外の何かである必要はなく、適切なビットマスクが、長さｍビットのビット列のうちのｋビットを「１」に設定して残りのビットが「０」のままであるようにすることによって得られてもよい（この場合、ブルームフィルタはｍビットの長さを有し、かつｋ＜ｍである。）
【００７３】
実際には、ハードウェアの中で可変長フィールドを処理するのは非効率であるだろうから、すべてのリンクＩＤが同じビットマスク長ｍを有することが有利である。それゆえ、実際には、ｍについて無理のない最大限のサイズを決め、次いで、すべてのリンクＩＤについてのビットマスク長としてそれを使用することが、有利である。しかし、リンクＩＤを形成するビットマスク内で「１」に設定されるビット数ｋは、ネットワークによってさまざまであろうし、「１」に設定されるビット数ｋは、すべてのリンクについて同じでなくてもよい。例えば、高容量リンクについてのリンクＩＤは、長さｍビットのビット列のうちのｋ０−１ビットを「１」に設定することによって形成されてもよいし、他方、通常容量リンクは、長さｍビットのビット列のうちのｋ０ビットを「１」に設定することによって形成されるリンクＩＤを有してもよい。これによって、高容量リンクについての偽陽性の数が増す可能性があるが、他のリンクについての偽陽性の数は減るはずである。逆に、低容量リンクについてのリンクＩＤは、長さｍビットのビット列のうちのｋ０＋１ビットを、さらにはｋ０＋２ビットを「１」に設定することによって形成されてもよい。これによって、そのリンクについての偽陽性の数が減るはずであるが、他のリンクについての偽陽性の数は増すことがある。
【００７４】
リンクＩＤを形成するために「１」に設定されるｋビットは、無作為に選択されてもよい。ただし、ｋビットは、他のやり方で選択されてもよく、例えば、ローカルでは、あるノードからのリンクのリンクＩＤ間に重複がないようにノードからの各送出リンクについてｋビットを選択することは、意味を成すであろう。従って、あるノードからパケットが１つの送出リンクだけで送信されるべき場合に２つ以上のリンクでパケットを送信する確率は、大幅に減少するであろう（但し、他のどこかで偽陽性が増えているかもしれない）。
【００７５】
ブルームフィルタの長さｍは、下記のようにすべてのルーティング情報がブルームフィルタに書き込まれた後で、ブルームフィルタの中身が半分しかないように選ばれること、すなわち、ブルームフィルタの中身が半分を超えると偽陽性率が顕著になりうることから、「１」に設定されるのはｍ／２ビットを超えないことが望ましい。ただし、ブルームフィルタをパケットヘッダに入れることは、ブルームフィルタのビット数がかなり少ない場合に限って実行可能である。実際には多くの場合、１２８ビット前後の長さのブルームフィルタなら、偽陽性の数が適度に少ないはずである。
【００７６】
パスが決められると、ルーティング機能４は、パスのリンクＩＤを含むＢＦを作成する（図１１のステップ５）。上記のようにリンクＩＤが構築され、かつ、そのうちのｋ（またはｋ−１、ｋ＋１等）個が「１」ビットであるような「ｍ」ビットがそこに含まれる場合、各リンクＩＤは、ＢＦへとＯＲ演算され（この場合、ＯＲ演算されるとは、論理ＯＲ演算を意味する）、従ってこの場合、ＢＦは、パス上の各リンクについての情報を含む。図４の例では、パスは、Ｒ１からＲ２まで（リンクＩＤ：００１００１００１）とＲ２からＲ３まで（リンクＩＤ：００１０１１０００）の２つのリンクを含んでおり、従って、生成されたブルームフィルタは、００１０１１００１である。
【００７７】
ルーティング機能は、作成されたソースルーティングＢＦを発行Ｐの識別子と共にデータソース１へ送信する（図１１のステップ６）。ソースノードは発行Ｐからパケットを作成して、受信したＢＦをヘッダに入れる（図１１のステップ７）。パケットはこの時点で配信される準備が整っており、データソース１によって送信されてもよい（図１１のステップ８）。
【００７８】
原理的には、ルーティング情報は、上記のようにルーティング機能４でではなくてソースノードでブルームフィルタの中に符号化されてもよい。
【００７９】
パケットの配信を図５および図１２に図解する。パケットは、ヘッダ内にブルームフィルタ（図５の例では、パケットの中のブルームフィルタは図４で生成されたブルームフィルタ００１０１１００１である）としてルーティング情報を含んでいるが、最初にＲ１へ送信される。パケットがノードＲ１で受信される（図１２のステップ１）と、Ｒ１は、パケットヘッダの中に含まれるブルームフィルタをチェックすることによって（図１２のステップ２）、パケットヘッダの中のルーティング情報を問い合わせ、そして、パケットヘッダのＢＦの中から、Ｒ１からの送出リンクのリンクＩＤ値に一致するものを探すことを試行する（図１２のステップ３）。例えば、Ｒ１における各転送テーブルエントリは、送出リンクのリンクＩＤと、対応する物理リンクのインデックスとで構成されてもよい。一致検索プロセスを、図２に例示する。
【００８０】
パケットは、ブルームフィルタに一致するリンクＩＤを有する、ノードＲ１から送出される単数または複数のリンクに沿って転送される（図１２のステップ４）。この例では、ノードＲ１は、ノードＲ２へと（リンクＩＤ：００１００１００１）、ノードＲ４への（リンクＩＤ：００１０１０００１）２つの送出リンクを有する。Ｒ１での、受信したパケットのヘッダの中のブルームフィルタ００１０１１００１を送出リンクと照合することの結果は、２つの陽性である。これは、１つの正確な陽性と１つの偽陽性とである。リンクＲ１−Ｒ２は受信したパケットの中のＢＦに実際に追加されたものであり、結果として検証からの正確な陽性応答が行われる。しかし、リンクＲ１−Ｒ４は、ＢＦに追加されたものではなく、ノードＲ４に対する受信したパケットの中のＢＦとの一致は、偽陽性である。
【００８１】
従って、パケットは（正しく）ノードＲ２へ転送され、そして、（間違って）ノードＲ４にも転送される。パケットヘッダの中のブルームフィルタに問い合わせて、ブルームフィルタに含まれる送出リンクを探すというプロセスは、パケットが受信される各ノードで繰り返される。従って、図５の例では、パケットがノードＲ２およびＲ４で受信されると、上記のプロセスは各ノードで繰り返される。ノードＲ４では、送出用の一致するリンクＩＤが存在せず、パケットは破棄される。（ＩＰの場合は同じ宛先ＩＰアドレスを用いてネットワークのどこからでもパケットを宛先に配信することができるが、それとは違って、本発明のＢＦベースのヘッダは、特定のパスに限ってルーティング用として使用することができる。一旦パケットがパスの外に出ると、パスは一致するリンクＩＤを含まないため、パケットを正確に配信することはできない。）しかし、ノードＲ２では、パケットヘッダの中のＢＦは、Ｒ３に対するリンクにさらに一致するため（ステップ４）、パケットは、そのリンクを用いてノードＲ３に転送される。
【００８２】
ノードＲ３からシンク２までの最終配信は、いずれかの便利なやり方で扱われてもよく、本発明は、最終配信の特定の方法には限定されない。例えば、シンク２に向かうリンクＩＤを、ＢＦが作成される時にＢＦに追加することもできるだろうし、パケットが、ノードＲ１、Ｒ２、Ｒ３の間で転送されるのと同様にノードＲ３からシンクへ転送されてもよい。もう１つの例として、Ｒ３が、シンクからの購読情報を維持し、発行ＩＤを購読と照合し、データをシンクに転送することもできるだろう。
【００８３】
仮想リンク
ブルームフィルタに関する１つの問題は、それらが比較的早く「一杯」になりうることである。１つのフィルタに追加される要素が増えれば、偽陽性の確率が高まり、一般には、中身が半分をかなり超えることは、ブルームフィルタにとって望ましくない。さらに、上記のように、ブルームフィルタの長さを比較的短く維持することが望ましい。従って、本発明の好適な特長では、複数の単一のリンクから（この場合、単一の「リンク」は２つのネットワークノードを直接リンクする）１つの「仮想リンク」が定義されるが、それによって、ネットワークにおいて配信ツリーを記述する、より効率的なやり方が可能になると共に、ＢＦに追加されることが必要なリンクＩＤもより少なくて済む。本発明の方法によってパケットをルーティングするのに「仮想リンク」が用いられる場合、仮想リンクを用いるルーティングは、上記と同じやり方で行われる。仮想リンクのリンクＩＤは、例えばブルームフィルタの中で、符号化され、そして、パケットヘッダに入れられる。仮想リンク沿いのノードの転送テーブルは、仮想リンクのリンクＩＤと適切な転送の宛先とを含めるように構成される。仮想リンクのリンクＩＤをそのヘッダ内に有するパケットを受信すると、ノードは、転送テーブルの中の仮想リンクのリンクＩＤに関連する宛先にパケットを転送する。
【００８４】
ルーティング機能がデータをＲ１からＲ３まで配信する、図６に示す事例について考えよう。何らかの理由で、この部分的なパスは負荷が重くて、複数の異なる送信が同じパスを使用している。従って、Ｒ１とＲ３との間の「仮想リンク」を定義することは利益になりうる。図６では、ルーティング機能は、Ｒ１からＲ２を介してＲ３までのそのような仮想リンクを定義し、そして、それに仮想リンクＩＤを与えている。図６の例では、仮想リンクは、２つの単一リンクＲ１−Ｒ２とＲ２−Ｒ３とから定義されるが、仮想リンクは、３つ以上の単一リンクを含んでもよい。従って、新たな仮想リンクは、Ｒ１−Ｒ２−Ｒ３である。従って、ノードＲ１からノードＲ３までのパケットの配信を確実にするため、パケットヘッダの中のブルームフィルタの中に、リンクＲ１−Ｒ２とリンクＲ２−Ｒ３とのリンクＩＤを入力するのではなく、仮想リンクのリンクＩＤだけを入力することが必要である。
【００８５】
生成された仮想リンクは、リンクＩＤを有しているが、それは仮想リンクを作成するのに使用された根底にあるリンクのリンクＩＤに直接関連する必要はない。図６の例では、仮想リンクＲ１−Ｒ２−Ｒ３には、リンクＩＤ  １０１０００１００が与えられる。
【００８６】
仮想リンクのリンクＩＤは、リンクＩＤについて上述したように、ｋビットが「１」でｋ−ｍビットが「０」であるような、長さｍビットのビットマスクであってもよいし、リンクの根底にある識別子にハッシュ関数を適用することによって得られてもよい。リンクＩＤがビットマスクである場合、ビットマスクのうちの指定のビットを用いて、リンクが実際のリンクである場合には指定のビットを「１」に、リンクが仮想リンクである場合には「０」に（あるいはその逆に）設定することによって、あるリンクが実際のリンクであるか仮想リンクであるかを表すことが可能であろう。
【００８７】
仮想リンクに属するノード、すなわち仮想リンクに対応する物理パス上にあるノードは、それらがパケットを転送できるように、仮想リンクについて知る必要がある。例えば、各仮想リンクについて、（リンクの最後のノードを除いて）リンクのノードには新たな転送テーブルエントリがある可能性がある。従って、図６では、ノードＲ１についての転送テーブルは、さらに、仮想リンクＲ１−Ｒ２−Ｒ３についてのエントリを含み、それは、パケットヘッダ内にリンクＩＤ  １０１０００１００を含むパケットはノードＲ２へ転送されるべきことを示す。同様に、ノードＲ２についての転送テーブルは、さらに、仮想リンクについてのエントリを含み、それは、パケットヘッダ内にリンクＩＤ  １０１０００１００を含むパケットはノードＲ３へ転送されるべきことを示す。
【００８８】
新たな仮想リンクが設定される場合、新たに作成された仮想リンクに属するノードにそれが伝達される必要がある。仮想リンクについての情報を伝達する１つのやり方は、新たなリンクＩＤをリンクの各ノードに別々に配信することであるが、代わりに、もっと簡潔な方法を用いて、各ノードが、関連ノードを通じて配信される別個の制御パケットからこの情報を入手できるようにすることも可能であろう。
【００８９】
例えば、制御パケットを用いて新たな仮想リンクについての情報を配信するため、図７に示すように、ルーティング機能が、Ｖｉｒｔｕａｌ  Ｌｉｎｋ  Ｓｅｔｕｐ  Ｐａｃｋｅｔ（ＶｉＬＳ）を用いて新たな仮想リンクＩＤについてノードに情報提供してもよい。ＶｉＬＳのパケットヘッダの中のＢＦは、通常通り算出されたＢＦを含んでいる。すなわち、それに対して、パケットがリンクＲ１−Ｒ２−Ｒ３に沿って転送されるようにするため、上記のようにＲ１−Ｒ２リンクＩＤおよびＲ２−Ｒ３リンクＩＤが追加されている。ＶｉＬＳパケットのデータフィールドには、新たな仮想リンクＩＤが含まれ、必要に応じて仮想ＩＤの存続時間も含まれる。ＶｉＬＳパケットを受信する各ノードは、ＶｉＬＳパケットからリンクＩＤを読み取って、リンクＩＤを、対応する送出リンクと共にその転送テーブルに追加することができる。発行ＩＤフィールドまたはパケットヘッダの中の何らかの他のフィールドを用いて、ＶｉＬＳパケットのタイプを示してもよいが、これについては他の方法もある。ＶｉＬＳパケットのデータフィールドの中に、ノードの中の転送テーブルエントリをセットアップすることに関する他の情報を含める必要はなく、パケットヘッダの中のＢＦをこの目的で使用することができるのだから、ノードの転送テーブルの中で定義される送出リンクは、パケット内のＢＦがパケットをノードからルーティングするであろう場合のリンク、およびＶｉＬＳパケットが次に送信される場合のリンクと同じである。
【００９０】
上記のように、通常通り算出されたＢＦに依存して仮想リンクについての情報を配信する場合、ネットワーク内の仮想リンクの表現は、通常通り算出されたＢＦが含む（もしあれば）のと同じ偽陽性を含むであろう。そのような偽陽性を避けることが望ましい場合、ＶｉＬＳパケットは、仮想リンクを形成するリンクのリンクＩＤを、例えばパケットのデータ部分の中で、明示的に符号化してもよい。リンクＩＤがＶｉＬＳパケットの中へ明示的に符号化される場合、仮想リンク沿いの各ノードは、送出リンクＩＤをパケット内の明示的に符号化されたリンクＩＤと比較して、この目的でパケットヘッダ内のＢＦを無視することによって、仮想リンクのための転送テーブルをセットアップするであろう。
【００９１】
仮想リンクをネットワークノードの転送テーブルに追加するため、ルーティング機能は、新たに構築されたＶｉＬＳをノードＲ１に入れる。ノードＲ１は、これが制御パケットであることに気付き、新たな仮想リンクを記述する新たな転送テーブルエントリに必要な情報をパケットのデータフィールドから取得し、そして、新たなエントリをその転送テーブルに入れる。このエントリについての宛先は、ＶｉＬＳパケットヘッダ内のＢＦによってかまたは、上記のように、それらを明示的にリストすることによって、判定されてもよい。典型的には、通常のパケット転送メカニズムによってＶｉＬＳパケットがさらに配信される場合と同じ宛先が、転送テーブルに追加される。従って、この例ではノードＲ１が、ノードＲ２への送出リンクに対して、仮想リンクＲ１−Ｒ２−Ｒ３のリンクＩＤをその転送テーブルに追加する。次いでＶｉＬＳパケットがノードＲ２へ転送され、ノードＲ２でプロセスが繰り返され、その結果、ノードＲ”は、ノードＲ３への送出リンクに対して、仮想リンクＲ１−Ｒ２−Ｒ３のリンクＩＤをその転送テーブルに追加する。次いでＶｉＬＳパケットは、次のノードへ転送され、以下同様に行われる。
【００９２】
図６では、仮想リンクが実際のリンクを用いて構築される。また、既存の仮想リンクを結合することによって新たな仮想リンクを定義することも可能である。図８は、これがどのようにして行われるかを示す。仮想リンクＲ１−Ｒ２−Ｒ３−Ｒ４−Ｒ５が、１つの区分が仮想リンクＲ１−Ｒ２−Ｒ３であり、もう１つの区分が仮想リンクＲ３−Ｒ４−Ｒ５であるように定義される。あるいは、少なくとも１つの区分が実際のリンクであり、少なくとも１つの区分が仮想リンクであるように、仮想リンクが定義されてもよい。
【００９３】
このようにして定義される仮想リンクに、その構成区分の識別子とは異なり（かつ、それに関連する必要のない）、かつ、仮想リンクに含まれる実際のリンクの識別子とも異なる、リンクＩＤが与えられる。従って、図８の仮想リンクＲ１−Ｒ２−Ｒ３−Ｒ４−Ｒ５に対して、２つの構成仮想リンクであるＲ１−Ｒ２−Ｒ３およびＲ３−Ｒ４−Ｒ５のリンクＩＤにも、根底にあるネットワークリンクであるＲ１−Ｒ２、Ｒ２−Ｒ３、Ｒ３−Ｒ４、Ｒ４−Ｒ５のリンクＩＤにも関連する必要のない、リンクＩＤが当てられる。
【００９４】
仮想リンクＲ１−Ｒ２−Ｒ３−Ｒ４−Ｒ５のリンクＩＤが、上記のようにＶｉＬＳパケットを用いてノードＲ１−Ｒ２−Ｒ３−Ｒ４の転送テーブルに追加されてもよい。動作は、図６について記述したものと同様であり、ＢＦの中に含まれるリンクＩＤは、仮想リンクＲ１−Ｒ２−Ｒ３および仮想リンクＲ３−Ｒ４−Ｒ５のＩＤである。
【００９５】
仮想リンクは、存続時間が限定されなくてもよいし、存続時間が限定されてもよい。図７に示すように、ＶｉＬＳパケットは、もし分かっていれば、この存続時間情報も含んでもよい。そのような場合、ノードは、仮想リンクの存続時間が終了した後、転送テーブルから仮想リンクを消去する。
【００９６】
既存の仮想リンクの存続時間の修正を、ＶｉＬＳパケットを用いて、新たな存続時間を定義する新たなパケットを送信することによって、行うこともできる。同じ方法を用いて、存続時間がゼロに設定されているＶｉＬＳを送信することによって、既存の仮想リンクを手動で消去することもできる。
【００９７】
マルチパス／マルチキャスト・ステートレス転送
本発明の上記の記述は、ソースから単一の宛先ノードへ送信されるパケットに関する。しかし、本発明は、これに限定されず、パケットをソースから２つ以上の異なる宛先ノードへ配信するのに用いられてもよい。これは、２つ以上の宛先へのパスを定義するリンクＩＤを、パケットヘッダの中に含まれることになるブルームフィルタに追加することによって行われてもよい。
【００９８】
さらに、仮想リンクの上記の記述は、１つのソースから単一の宛先ノードまで送信されるパケットに関するが、マルチパスまたはマルチキャスト仮想リンクを作成することも可能である。これは、いずれも１つのノードから出るリンクを定義する２つ以上のリンクＩＤをＢＦに追加することによって行われてもよい。これを図９に示すが、ここではＲ１−Ｒ２−Ｒ３、Ｒ１−Ｒ４−Ｒ５およびＲ１−Ｒ４−Ｒ６を含む仮想リンクが（リンクＩＤ  ００１００１００１を使って）定義されている。完全なマルチキャストツリーは、リンクＲ１−Ｒ２、Ｒ２−Ｒ３、Ｒ１−Ｒ４、Ｒ４−Ｒ５およびＲ４−Ｒ６を同じＢＦにＯＲ演算することによって実装することができる。
【００９９】
ヘッダ内のこのＢＦを用いてソースから配信されるパケットは、図の中の３つのシンクノードすべて（Ｒ３、Ｒ５、Ｒ６）に配信されるであろう。図６で２つのノード間に仮想リンクがセットアップされるのと同様に、図９は、まったく同じ方法を用いて仮想マルチキャストツリーをセットアップする。この場合、２つ以上の宛先にデータを送信することになる各ノードは、仮想リンクＩＤを、（例えばノードＲ４の転送テーブルがノードＲ５へのリンクとノードＲ６へのリンクとを両方とも仮想リンクのリンクＩＤ（００１００１００１）に対してリストするように）複数の宛先リンクに関連付けることによって、転送テーブルの中でこれを判定するであろう。
【０１００】
この場合もやはり、仮想リンクの詳細は、ＶｉＬＳパケットを用いて配信することもできる。図９では、ルーティング機能は、ツリーのための仮想リンクＩＤ（００１００１００１）を作成し、ＶｉＬＳパケットを生成し、そしてそれをＲ１に入れる。ＶｉＬＳパケットがすべての宛先に渡された後、仮想マルチキャストツリーがネットワーク内でセットアップされる。データパケットが、ヘッダ内に仮想マルチキャストツリーのＩＤだけを含むＢＦ（００１００１００１）を使って送信される場合、データは、ソースからネットワーク内のすべてのシンクへルーティングされる。図９は、Ｒ２およびＲ４についての転送テーブルを示す。
【０１０１】
複数のパスを活用するもう１つのやり方は、それを冗長の目的で使用することである。同じソースと最終の宛先とを有するけれども、複数の並行パスを伴うようなパスを作成することは可能である（図１０）。すべてのパスは一方向であるが、２つのノード間でそのようなマルチパスルート（または仮想リンク）を容易に作成することができる。
【０１０２】
留意すべきだが、仮想リンクの生成は、本発明の特定のルーティングの方法を用いることに限定されない。
【０１０３】
上記の実施形態では、ネットワークを通るルートは、ノード間の単一のリンクかまたはノード間の単一のリンクから構築される仮想リンクを用いて、ルーティングレイヤで決められる。しかし、本発明は、これに限定されない。
【０１０４】
ステートフル・ルーティング
別の選択肢として、ネットワークを２つ以上のステートレス・ルーティング・エリアに分割するノードをネットワークに追加することが可能である。これらのプロキシノードは、異なるＢＦおよび発行間の状態情報を維持して、パケットが通過する際にＢＦヘッダ間のラベル切り替えを行う。これらのプロキシノードは、ブルームフィルタが一杯になるのを避けるために用いることもできるし、単にネットワークをさまざまな管理領域に分割するために用いることもできる。
【０１０５】
偽陽性率の削減
上記のように、ブルームフィルタの１つの特徴は、ＢＦ内のリンク識別子の存在をチェックする時、それが偽陽性を返す可能性がある（すなわち、ある項目がフィルタ内に存在すると報告するが、実際にはそれは存在しない）ということである。偽陽性の結果、パケットは、ＢＦの構築の間は含まれていなかった１つ以上のリンク上で転送される。ｐｕｂ／ｓｕｂパラダイムでは、偽陽性率が過大になることを制御するやり方がある限り、この影響は有害だとみなされない。偽陽性率は、フィルタ内に挿入された項目の数ｎと、フィルタのサイズｍと、フィルタ内の項目を表すビット数ｋとに依存する（この場合、リンク識別子は、ｋビットが１に設定され、残りのｍ−ｋビットが０に設定されたｍビットのベクトルのかたちをとる）。
【０１０６】
ＢＦに関する問題は、それらが比較的速く「一杯」になることである。偽陽性の確率は、１つのフィルタに追加される要素が増えるにつれて高くなる。それによって、所定のＢＦサイズについては、所定の偽陽性率を超えないことが望ましい場合、ＢＦによって表されうるリンクの数は限られる。一例として、現行のＢＦの設計および約２５６ビットという典型的なパケットヘッダサイズの場合、ＢＦの偽陽性率（％）に起因して、３２個を超えるリンクＩＤをＢＦに挿入することはほぼ実行不可能となるであろうが、それは、偽陽性率が高くなる（約３％）であろうという理由による。しかし、多くの場合、３２個のリンクＩＤは、（ネットワークトポロジと、３２個のリンクによって定義されるパス上で通信するノードの数と、によっては）ルーティングの目的では不十分であろう。
【０１０７】
加えて、所定のネットワークトポロジとリンクＩＤの配信とを想定した場合に、現行のＢＦの生成には、偽陽性の影響をさらに細かく制御できるようなメカニズムが欠けている。特に、想定されるシステムにおけるルーティング機能が、ルーティングＢＦを作成するという柔軟性（ネットワーク内で特定のパスを定義するという主たる目的では同等であるが、ネットワークオペレータによって指定される何らかの条件においては偽陽性がいっそう有害であるという、リンクＩＤによって識別される特定の領域では偽陽性を回避できるような、ルーティングＢＦを作成するという柔軟性）を持てば、有益であろう。
【０１０８】
提案するＢＦを利用した手法のもう１つの問題は、セキュリティである。できれば、見込まれる悪質ソースノードに対処するメカニズムが求められる。見込まれる悪質ソースノードは、見込まれるＤｅｎｉａｌ  ｏｆ  Ｓｅｒｖｉｃｅアタックのための転送ＢＦを自分自身で生成したり、あるいは、ホストＩＤではなくトポロジ内でリンクを命名することに基づく転送システムを有するという本質的なセキュリティを迂回したりするかもしれない。
【０１０９】
従って、本発明のさらなる態様は、ＢＦベースのルーティング手法の偽陽性率を削減し、そして、ルーティングパス沿いのＢＦの影響を制御する新たなメカニズムを提供するという問題に取り組む。本発明のこの態様では、複数のブルームフィルタ候補（または、本態様もブルームフィルタに限定されないことから、他のコンパクトな集合表現）が生成され、そして、ブルームフィルタ候補（または、他のコンパクトな集合表現）の１つが、例えば、どの候補が偽陽性を返す確率が最も低いか等のような、所定の基準に基づいて選択される。この態様は、リンク識別子を含むＢＦを生成する確率的プロセスの間に利用できる選択に基づく。
【０１１０】
このさらなる態様は、一例として、複数のリンクを有するネットワークにおけるルーティングに関して記述されるであろうが、この態様はこれに限定されない。
【０１１１】
上記で説明したように、例えば図４のネットワークのようなネットワークの各リンクは、関連するリンク識別子（ＬＩＤまたはリンクＩＤ）を有する。上記の実施形態では、ＬＩＤを用いてブルームフィルタが生成され、これにより、特定のネットワーク利用についてはＢＦが１つだけ生成される。しかし、本発明の別の態様は、あるネットワークのパスを同等に表現する、２つ以上のＢＦ候補を生成する。これが行われうる１つのやり方は、各リンク識別子（ＬＩＤ）に関連する複数のリンク識別子タグ（ＬＩＴ）を生成し、ＬＩＴから複数のブルームフィルタ候補を生成することである。ソースルーティングに用いられるＢＦを選択する時に、ＢＦの中に挿入されることになるＬＩＴの最適な集合が、偽陽性の確率を最小化することができるように選択される。
【０１１２】
一般論として、本発明のこの態様が、識別子の集合に適用される場合、複数の表現（または「タグ」）が各識別子について生成される。複数のブルームフィルタ候補（または集合メンバシップの複数の他のコンパクト表現）が、複数の識別子の表現から生成され、そして、ブルームフィルタ（または集合メンバシップの他のコンパクト表現）のうちの１つが、候補の中から選択される。
【０１１３】
一実施形態では、各ＬＩＤについて、ＬＩＤのｄ個のコンパクト表現を演算するが、ここでｄは、２以上の整数である。コンパクト表現の各々は、リンク識別子タグ（ＬＩＴ）として知られる。ＢＦの中に挿入されることになるリンクの各ＬＩＴについて、１度に各ＬＩＤの１つのＬＩＴ表現をＯＲ演算することによって、ＢＦ候補が生成される。この結果、ネットワークパスのリンク識別子を「等しく」表現する、ｄ個のＢＦ候補が生じることになり、ここで「等しく」とは、ｄ個のＢＦ候補の各々が、パケットがそれに沿ってルーティングされることが意図された（少なくとも）すべてのパスをパケットにたどらせることを意味する。
【０１１４】
原理的には、各リンクＩＤについてｄ個のＬＩＴを生成する必要はない。一例として、３２個のリンクがある場合、３２個のリンクＩＤのうちの３１個についてはｄ個のＬＩＴを生成するが、３２番目のリンクについては、このリンクがそのｄ個の表現の各々において同じＬＩＴを有するように、１個だけＬＩＴを生成することも可能であろう。この例では、ＢＦ候補を構築する際に３２番目のＬＩＴが何個のビットを１に設定するのかを選択する力はないであろうから、３２番目のＬＩＴは、ＢＦの中のそれらの数を削減することには貢献しないであろう。
【０１１５】
一部のリンクＩＤだけについてｄ個のＬＩＴを生成することは、ＢＦを解釈する一部の転送ノードがこのｄ個の拡張を有さず、従ってＬＩＴについての異なる転送テーブルを有しないようなシステムでは、有益でありうるだろう。それによって、より単純な転送ノードを供給することが可能になり、後方互換性サポートが提供される。
【０１１６】
ｄ個のＢＦ候補のうち、上記の実施形態の場合のように、ルーティング情報を提供する目的でパケットヘッダに挿入されるために１つが選択される。
【０１１７】
使用されることになるＢＦを選択するための主な基準は、ユーザが決めてもよく、例えば、偽陽性率を最小化することであってもよく、その場合、０の数が最も多いＢＦが、ＢＦ候補から選択される。例えば、１つ以上のリンクの部分集合について偽陽性率を最小化する（または、一般的な表現では、１つ以上の識別子の部分集合について偽陽性率を最小化する）ことのように、ＢＦを選択するための他の基準を適用することも可能であり、これは、例えば、パケットが所定のネットワーク領域に転送される結果となる偽陽性をもたらす所定のリンク識別子を避けるために（すなわち、偽陽性を所定のネットワークエリアに閉じ込める能力を提供するために）利用してもよい。
【０１１８】
この態様が上記の実施形態に適用される場合、パケットヘッダは、今度は、転送情報を含むＢＦに加えて、ＢＦを構築するのに用いられたＬＩＴの集合を識別するインデックスｄの２進法表現を含む。この態様のＢＦ（ｄ拡張型ＢＦと呼ぶ）を受信するルーティングノードは、ＢＦを構築するのに用いられたＬＩＴの集合に適した転送テーブルを選択することができる。
【０１１９】
提案するｄ拡張型ＢＦの手法は、それによって、ルーティングポリシーを実行するために適用されうる、偽陽性の影響に対するより精緻な制御を可能にし、そして、ＢＦを転送ヘッダとして用いる場合にセキュリティ機能を提供するように補強することができる。
【０１２０】
拡張型ブルームフィルタの詳細記述
ランデブー、ルーティング、転送という３つの動作レイヤを持つＰｕｂ／Ｓｕｂネットワークに関して、実施形態を記述しよう。それらは一緒に、ソースノードと宛先ノードとの間でデータを発見して配信するのに必要な機能性を提供する。ネットワークの各リンクは、関連の識別子（リンクＩＤ）を有する。本発明の本態様では、各リンクＩＤのｄ個（ｄ＞１）の表現が生成され、ｄ個のＢＦ候補が、リンクＩＤのｄ個の表現から生成される。１個のリンク識別子に関連付けられたｄ個の表現の集合を有することは、偽陽性に対するより精緻な制御を提供することによって、より効率的かつ強力な転送スキームを可能にする。さらに、ＬＩＴベースのＢＦの選択力は、セキュリティまたはゾーン間のルーティング目的のためのポリシーの実行を、これらのポリシーをＢＦの選択および最適化の基準とみなすことによって、可能にする。
【０１２１】
リンクＩＤタグの構築
リンクＩＤは、ネットワークのリンクについての有向識別子として生成される。（記述を簡単にするため、すべての「リンク」は２つのネットワークノード間の実際のリンクであるが、リンクＩＤは、図６に関して記述したように「仮想リンク」の識別子でもあってもよいと仮定しよう。）本発明の本態様では、リンクＩＤ（ＬＩＤ）は、２つのネットワーク要素（例えばルータ）間のリンクを識別するため、いかなる名前の形態でもとることができる。典型的には、ＬＩＤは、無作為に生成されたビットの組み合わせ（例えば２５６ビットのハッシュ値）であろう。
【０１２２】
本発明の別の態様は、リンクＩＤのコンパクト表現として、「リンクＩＤタグ」（ＬＩＴ）という概念を導入する。加えて、すべてのリンクＩＤは、多価のマッピング関数を各ＬＩＤに適用することによって演算されるｄ個のＬＩＴの集合に関連付けられ、従ってこの場合、ＬＩＴは、各リンクＩＤについてと同じやり方で演算される。ｄは、ネットワークに依存して最適化されうるシステムパラメータである。ｄの典型的な範囲は、２から３２までであろう。（以前のリンクＩＤのように１個のＬＩＴしか見えない場合、それはｄ＝１の場合に相当するであろう。）例えば、マッピング関数は、各リンクＩＤについて、ｋビットが１に設定され、ｍ−ｋビットが０に設定されたＬＩＴビットベクトルを作成するために各リンクＩＤに適用される、ｋ個のハッシュ関数の集合であってもよい。この形態のＬＩＴをＢＦに組み込むことは、ｋ個のハッシュ関数を用いて挿入された１つの要素を持つｍビットのＢＦと同等であろう。（ＬＩＴのｄ個の集合がどうすれば得られるかという記述を以下に示す。）
以前の実施形態では、リンクＩＤは、好都合なＢＦの追加とチェック動作のため、ｋビットが１に設定されて他のｍ−ｋビットが０に設定された、サイズｍのビットマスクのかたちであってもよい。しかし、本実施形態では、ｋビットが１に設定されて他のｍ−ｋビットが０に設定された、サイズｍのビットマスクのかたちをとるのは、ＬＩＴであり、リンクＩＤのサイズと表現とは自由であって、ＬＩＴをそこから演算することができるならばいかなる適切なかたちをもとることができ、従って、本態様では、リンクＩＤ自体についてのかたちの選択の幅が拡がる。主な違いは、今度は、同じネットワークリンクを同等に表現するｄ個のＬＩＴの集合があり、偽陽性率を最小化するようなリンク識別子の組み合わせを表現するＬＩＴの集合を選択するために、ＬＩＴおよびＢＦの生成の無作為性を利用することができるということである。
【０１２３】
加えて、１個のリンクＩＤについてｄ個のＬＩＴの集合を生成するプロセスは、無作為のプロセスであってもよいし、ネットワークの実際のトポロジによりよく適合するためのもっと制御されたプロセスであってもよい。１個のリンクＩＤについてＬＩＴを生成することが、以下のようにトポロジにリンクされてもよい。（例えば転送ノードがネットワークに接続する）ブートストラッププロセスの間、リンクＩＤがＴｏｐｏｌｏｇｙ  Ｍｏｄｕｌｅに登録される。ＬＩＴは、転送ノード自体によって生成されてもよいが、それは、ＬＩＴの生成に用いられるハッシュ関数を両者が分かっている場合である。あるいは、Ｔｏｐｏｌｏｇｙ  Ｍｏｄｕｌｅが、ＬＩＴを接続ノードに返すこともできる。この時点で、Ｔｏｐｏｌｏｇｙ  Ｍｏｄｕｌｅは、生成されたＬＩＴの衝突が最小限となり、それによって偽陽性率が低下するように、接続ノードの転送テーブルの中に「インストールされる」ことになるＬＩＴのリストを、アクティブなＬＩＴと一般に利用されるネットワークパスとに対してチェックする力を有する。
【０１２４】
図１４は、第１のハッシュ手順Ｈ１（ｘ）をリンクＩＤに適用することによって、１に設定されることになるとＨ１（ｘ）によって判断されるｋビットに基づいて第１のＬＩＴを生成し、第２のハッシュ手順をリンクＩＤに適用することによって第２のＬＩＴを生成し、ｄ番目のハッシュ関数Ｈｄ（ｘ）がリンクＩＤに適用されてｄ番目のＬＩＴを生成するまで以下同様に１個のリンクＩＤについてＬＩＴを生成する、１つの見込まれる方法を図解する。各ハッシュ手順は、ｋ個のハッシュ関数で構成され、その各々が、上記の図１に関して述べたように、１に設定されることになる、ビットベクトルの中の１つのビット位置を決める。
【０１２５】
各ハッシュ手順をリンクＩＤに適用することは、（偶然による場合を除いて）２つのハッシュ手順が同じ出力を生成しないように、各ハッシュ手順が新たなハッシュ関数の集合を含むことを必要とする。あるいは、その後のハッシュ手順を、以前に生成されたＬＩＴに繰り返して適用することもできるが、これなら、各ハッシュ手順が新たなハッシュ関数の集合を含むことは必要でないだろう。あるいは、ｋ個のハッシュ関数の集合が固定されたままで、最後に生成されたＬＩＴに繰り返して適用されてもよく、これなら、良好な無作為のＬＩＴを返すためのもう１つの有効な手順となり、必要なハッシュ関数の量が削減されるであろう。別の選択肢として、以下に述べるように、すべてのＬＩＴを生成するために必要なのは、２つの無作為な関数と２つのハッシングだけとなる。
【０１２６】
リンクＩＤ生成のプロセスの場合と同様に、リンクＩＤタグを決めるやり方はいろいろある。それらがルータによって自動的に生成され、その後、ルーティングレイヤに通信されてもよいし、それらが他のインスタンスによって割り当てられ、ルータ上で構成されてもよい。
【０１２７】
ルータは、自分が直接接続していると分かっているルータに対する自分自身の送出リンクにリンクＩＤを割り当てることができる（図１５のリンクＩＤ  ｘ  出力インタフェースを参照）。図１５は、リンクＩＤを使って各出力インタフェースを識別するネットワークノードの略図である（出力ポート１にはリンクＩＤａ、出力ポート２にはリンクＩＤｂ、以下同様）。ノードは、リンクＩＤタグによるインデックス付きのｄ個の転送テーブルを維持するが、それらは各ＬＩＴに関連する出力ポートを識別する。（すでに指摘したように、リンクＩＤは、仮想リンクに関係してもよいし、キャッシュシステムや他のネットワークプロセッサ／システムプロセスへのリンクに関係してもよい。）ルーティング機能の中に維持される情報は、今度は、各リンクＩＤに関連するｄ個のＬＩＴを含むように拡張される（ただし、原理的には、リンクＩＤだけがそこに格納されて、ＬＩＴ候補は常にオンデマンドで生成されてもよいだろう）。
【０１２８】
標準的なリンクＩＤの手法の場合と同様に、ネットワークノード内で維持されることになる転送状態は、非常に小さいままである。ｄの値が着信パケットの中に含まれている場合、各リンクＩＤについてのＬＩＴは、どのようにしてＬＩＴが当初生成されたかという知識からオンデマンドで演算されてもよいだろうが、性能上の理由で、（図１５に示すように）リンク識別子のｄ個の表現の各々について転送テーブルを維持することが望ましいことがあるだろう。図１６は、パケットヘッダの中の別のフィールドに含まれるブルームフィルタを生成するのに用いられるｄの値を与えるフィールドを有する、パケットヘッダの略図である。
【０１２９】
１個のリンクＩＤからｄ個のリンクＩＤタグを算出するのに必要な異なるハッシュ関数の数を考える場合、各ＬＩＴのビット分布において最大のエントロピーを達成するには、ＬＩＴ毎にｋ個の異なるハッシュ関数が必要であろう。それは、１個のＬＩＤについてｄ個のＬＩＴを演算するのに合計でｋ＊ｄ個のハッシュ関数が必要であろうということを意味する。本発明でハッシュ関数を用いる場合、２つの態様に注目すべきである。第１に、本発明で提案するＢＦ生成と選択プロセスとの無作為性を考えると、ＬＩＴを生成するのに用いられるハッシュが真に無作為であることは重要ではない。第２に、二重のハッシング技法を用いれば、２つだけ無作為の非依存のハッシュ関数（例えばＢＯＢ、ＯＡＡＴ、ＳＢＯＸ、Ｈｓｉｅｈ、ＴＷＭＸ、ＲＳ、ＳＨＡ、ＭＤ５）を用いることによって、漸近的な偽陽性の確率を増加させることなく、ｄ個のＬＩＴを非常に効率的に生成することができる。２つのハッシュ関数ｈ１（ｘ）およびｈ２（ｘ）は、次式の形式のｉ個のハッシュ関数をシミュレートすることができる。
ｇｉ（ｘ）＝ｈ１（ｘ）＋ｉ＊ｈ２（ｘ）ｍｏｄ  ｍ
【０１３０】
さらに、この方法を用いると、いかなるＬＩＴ生成プロセスであろうと、１に設定されるＬＩＴのｋ個の位置を演算するのに用いられたｉ個のインデックスの集合によってコンパクトに表現することができる。従って、ｈ１（ｘ）とｈ２（ｘ）とがルーティング要素によって知られている場合、いずれかのＬＩＤについてＬＩＴを導出するのに必要なのは、ｄ＊ｋ個の整数ｉを共有することだけである。Ｔｏｐｏｌｏｇｙ  Ｍｏｄｕｌｅは、転送ノードにＬＩＴ全体を返信する代わりに、ＬＩＴを演算するのに用いられることになるインデックスｉを送信するだけでよいだろう。例えば、ＬＩＴ１［ｉ＝１，２，３，４，５］は、ＬＩＴ１が、ｉの値［１，２，３，４，５］とｈ１（ｘ）とｈ２（ｘ）とを用いるｇ（ｘ）によって判定されるｋ（＝５）ビットを１に設定することによって演算されることを意味するであろう。ｈ１（ｘ）とｈ２（ｘ）とはいずれも転送ノードとＴｏｐｏｌｏｇｙ  Ｍｏｄｕｌｅとによって知られているのだから、ｄ個のＬＩＴが演算されうるようにするには、ＬＩＤとインデックスｉ（合計でｄ＊ｋ個のインデックスがある）とを共有するだけで十分である。加えて、すでに述べたように、ｉは、単なる徐々に増加するシーケンスであってもよいだろうから、この場合、知られていると想定することもでき、従って、交換される必要はない。
【０１３１】
リンクＩＤタグ転送テーブル
パケットがネットワークノードに到着する時、パケットヘッダは、パケットがそれに沿って転送されるべきリンクのＬＩＴを含むかまたは符号化するＢＦを含み、かつ、ＢＦのｄの値を識別する。上記のように、パケット転送は、図１５に示すようにリンク識別子のｄ個の表現の各々について転送テーブルを維持するネットワークノードによって行われてもよい。着信リンク上でパケットが到着した時点で、ノード内の転送機能が、ｄ拡張型ＢＦ転送ヘッダに含まれる値ｄに基づいて、用いられることになる転送テーブルを選択する。ポート転送動作は簡単であって、ＢＦは、すべてのＬＩＴエントリに対して同時にＡＮＤであり、そして、この迅速な要素チェック動作の結果としてＬＩＴエントリが得られる度に、パケットは転送テーブルの中のＰｏｒｔＯｕｔ値へ転送される。
【０１３２】
転送テーブルにＬＩＴエントリを格納するための空間効率のよい複数の選択肢について述べよう。
【０１３３】
標準的な表現
標準的な表現では、見込まれるｄの値の各々について別個のルックアップテーブルが格納されるため、ｄ個のルックアップテーブルが格納される必要がある。各ルックアップテーブルは、各リンクＩＤタグについての適切な出力ポートを、例えば以下のようにリストする（テーブルは、２個のｄ値についてのみ示す）。
0005214804.tif 000002
0005214804.tif 000003
【０１３４】
ＬＩＴベースの転送テーブルのための、ビットでの総メモリは、次式のようである。
ＦＴｍｅｍ＝ｄ＊＃ＬＩＤｓ＊（ｓｉｚｅ（ＬＩＴ）＋ｓｉｚｅ（ＰｏｒｔＯｕｔ））
例：
ｄ＝８で、５１２個のリンクＩＤが存在し、各ＬＩＴは２５６ビットのサイズを有し、各出力ポート名は１ビットのサイズを有する場合には、
ＦＴｍｅｍ＝８＊５１２＊（２５６＋８）＝１０８１３４４ｂｉｔ＝１０５６ｋｂｉｔ≒１Ｍｂｉｔ
である。（後で、図１８および図１９に要約したシミュレーションの結果を通じて、転送ＢＦのサイズが小さければ、ｄ＝８が良好なパラメータ選択であることを示す。）
【０１３５】
疎な表現
これは、１に設定されたｋビットの位置だけがＬＩＴエントリとして格納される、ＬＩＴの空間効率のよい表現である。表現は、ルックアップテーブルがＬＩＴ全体を格納せずに１に設定されるＬＩＴのｋビットの位置だけを格納するという点を除いて、標準的な表現の場合と同様にｄ個のルックアップテーブルを含む。ビットでのＬＩＴのサイズは、ｋにビット位置の２進法表現を乗じたものまで削減することができる（係数ｌｏｇ（ｘ）２／ｘでの削減）。この場合、ＬＩＴのサイズは次式で与えられる。
サイズ（ＬＩＴ）＝ｋ＊ｌｏｇ２（ＬＩＴ）
例：ｋ＝５ならば、サイズ（ＬＩＴ）＝５＊ｌｏｇ２（２５６）＝５＊８＝４０ビットである。
【０１３６】
今度は、ｄ個のＬＩＴ転送テーブルのための総メモリは、次式で与えられる。
ＦＴｍｅｍ＝８＊５１２＊（４０＋８）＝１９６６０８＝１９２ｋｂｉｔ
【０１３７】
区分されたハッシュの疎な表現
区分されたハッシュの疎な表現は、１に設定されるＬＩＴのｋビットのビット位置だけを符号化することによるＢＦの疎な表現と同じ原理を用いる。しかし、ＢＦは、区分されたハッシングを用いて生成されると仮定されており、その場合、ハッシュ動作（ビットを１に設定すること）は、ＢＦを表すｍサイズのビットのベクトルの区分に対して排他的に行われる。各ｋビットのうちの１つだけが、サイズｍ／ｋの区分に対して設定される。この技術は、偽陽性率に重大な影響は及ぼさないと証明されている。この場合、ＬＩＴサイズは、次式で与えられる。
サイズ（ＬＩＴ）＝ｋ＊ｌｏｇ２（ＬＩＴ／ｋ）
例：ｋ＝５ならば、サイズ（ＬＩＴ）＝５＊ｌｏｇ２（２５６／５）＝５＊６＝３０ビットである。
【０１３８】
ここで、ｄ個のＬＩＴ転送テーブルのための総メモリは、次式で与えられる。
ＦＴｍｅｍ＝８＊５１２＊（３０＋８）＝１９６６０８＝１４４ｋｂｉｔ
【０１３９】
効率的なルーティングのためのｄ最適化ブルームフィルタの構築
本セクションは、最適化されたＢＦを構築する手順がどのようにして行われるかを詳細に記述する。リンクＩＤタグがあれば、ネットワークリンクを表すｄ個のＬＩＴの間の選択力を利用することによって転送ＢＦのより柔軟な構築を可能にする識別子の基盤ができる。
【０１４０】
Ｔｏｐｏｌｏｇｙモジュールまたはルーティング機能が、通信ノード間でネットワークパスを確立するのに必要なリンクＩＤの集合を選択するという問題を解決したと仮定する（図１２のステップ３および４）。ＢＦの中で表現されることになるリンクＩＤの数をｎとしよう。偽陽性を最小化するための最適化手順は、以下のようである。上述のように、各リンクＩＤについてｄ個のＬＩＴが生成され、これらは、ＬＩＴ１、ＬＩＴ２、・・・ＬＩＴｄとラベル付けされる（図２０のステップ１（１）、１（２）、・・・１（ｄ））。
【０１４１】
ＢＦを構築するルーティング機能は、ＬＩＴ１の単純なＯＲ演算をすることによって、すべてのリンクＩＤのＬＩＴ１表現を第１のブルームフィルタ候補ＢＦ１の中に挿入する（図２０のステップ２（１））。同様に、同じ方法に従って、ＬＩＴ２の単純なＯＲ演算をすることによって、すべてのリンクＩＤのＬＩＴ２表現を第２のブルームフィルタ候補ＢＦ２の中に挿入し（図２０のステップ２（２））、以下同様に、ｄ番目のブルームフィルタ候補ＢＦｄが、すべてのリンクＩＤのＬＩＴｄ表現を挿入することによって構築され（図２のステップ２（ｄ））、結果として、同じネットワークパスを表現するｄ個のＢＦが生じるまで、挿入されることになるすべてのリンクの次のＬＩＴ表現を取り込む。（実際には、ｄ個のＢＦは、ここで述べるように次々にではなく、並行して構築される。）しかし、ｄ個のＢＦは同じネットワークパスを表現しているのだが、ＢＦを構築するためのＬＩＴとＯＲ演算の確率的性質が原因で、ＢＦは、１に設定されるビットの数（および位置）がさまざまである。
【０１４２】
パケットをルーティングするのに用いられることになるＢＦは、ｄ個のＢＦ候補から選択される（図２０のステップ３）。一実施形態では偽陽性を返す全体的な確率が最も低いＢＦが選択される。
【０１４３】
次いで、選択されたブルームフィルタが、上記の実施形態で記述したように用いられてもよく、そして、例えば、ソースノードに送信されてパケットヘッダに組み入れられてもよい（図１２のステップ６、７）。あるいは、ルーティング機能が、選択されたブルームフィルタをソースノード以外のノードに送信してもよい。
【０１４４】
図２０の方法は、ルーティング機能の中で行われると上述したけれども、その代わりにソースノードで行われてもよいだろう。
【０１４５】
一般に、図１２の方法で用いるＢＦを生成するのに図２０の方法が用いられる場合、３つの主な段階に分けることができるが、それらは、ｄ個のＢＦ候補を生成することと、使用される１つのＢＦ候補を選択することと、選択されたＢＦを使用することとである。これらの段階はすべて、同じネットワークノードで行われてもよいし、２つまたは３つもの異なるネットワークノードまたはエンドホストノードに分散されてもよい。例えば、上記のように、図２０の方法が全部ソースノードで行われ、ソースノードがパケットヘッダ内に選択されたブルームフィルタを含める場合、これは、生成段階と選択段階と使用段階とをすべて同じノードで実行する事例となるであろう。
【０１４６】
別の例として、図２０の方法は、ルーティング機能と別のノード（例えばソースノード）との間で分割することができるだろう。例えば、ルーティング機能がｄ個のブルームフィルタを生成するが、その後、ｄ個のブルームフィルタ全部を別のノードへ送信し、使用されることになるブルームフィルタの選択がその別のノードで行われるようにすることもできるだろう。本実施形態で望ましいならば、ルーティング機能は、ｄ個のブルームフィルタを他方のノードへ送信する時、どのブルームフィルタが選択されるべきだと自分が考えているかを示すこともできるだろうが、他方のノードは、この指示を無視することもできるだろう。他方のノードがソースノードである場合には、ソースノードは、選択されたブルームフィルタを、ソースノードから送信されることになるパケットに含めてもよい。（これは、ルーティング機能が生成段階を実行し、ソースノードが選択段階と使用段階とを実行することに相当するであろう。）しかし、他方のノードが、選択されたブルームフィルタの対象となるユーザでない場合、他方のノードは、選択されたブルームフィルタを対象となるユーザ、例えばソースノードに送信するであろう。（これは、生成段階と選択段階と使用段階とがすべて別のノードで実行される事例となるであろう。）
別の例として、ルーティング機能が、ｄ個のブルームフィルタから予備的な選択を行い、例えば、さらなる検討の結果、１つ以上の指定のリンクについて偽陽性を与える可能性のあるいずれかのブルームフィルタを廃棄することもできよう。次いでルーティング機能は、この予備的選択を通過したこれらのブルームフィルタを、（場合によっては、どのブルームフィルタが選択されるべきであるとルーティング機能が考えるかという指標と共に）別のノードに送信し、別のノードが最終選択を行うであろう。他方のノードが、選択されたブルームフィルタの対象となるユーザでなかった場合、他方のノードは、選択されたブルームフィルタを対象となるユーザに送信するであろう。
【０１４７】
ＢＦが偽陽性を返す確率は、ＢＦ内の０の１に対する割合に依存するということは重要であろうし、ＢＦの偽陽性率は、セルが空である確率の関数であることを示すことができる（例えば、Ａ．ＢｒｏｄｅｒとＭ．Ｍｉｔｚｅｎｍａｃｈｅｒとによる「Ｎｅｔｏｗｏｒｋ  ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｂｌｏｏｍ  ｆｉｌｔｅｒｓ：  Ａ  ｓｕｒｖｅｙ」、Ｉｎｔｅｒｎｅｔ  Ｍａｔｈｅｍａｔｉｃｓ、ｖｏｌ．１、ｎｏ．４、２００２を参照のこと）。
ｐ＝Ｐｒ［１個のセルが空である］＝（１−１／ｍ）ｋｎ≒ｅ−ｋｎ／ｍ
ｆｐｂ＝Ｐｒ［偽陽性］＝（１−ｐ）ｋ≒（１−ｅ−ｋｎ／ｍ）ｋ
【０１４８】
セルが空である確率は、すでに１に設定されたセルの数に依存する。０に設定されるビット数が増加する場合、要素をチェックする時に０を見つける可能性が高まり、従って、偽陽性率は減少する。ｆｐｂで与えられる数式は、ハッシングの前の偽陽性の確率である。一旦ハッシング手順が行われ、ビットがＢＦ内で１に設定されると、フィルファクターρ（ロー）は既知であり、ハッシングの後の偽陽性の確率のより良い推定量は、次式で与えられる。
ｆｐａ＝Ｐｒ［偽陽性］＝ρｋ
【０１４９】
このように、ｄ個のＢＦ候補から偽陽性を返す確率が最小であるＢＦを選択することは簡単であり、０が最も多い（または１に設定されたビット数が最も少ない）ＢＦの方が、より良い成果が得られ、偽陽性が少なくなるであろうし、その結果、本発明のルーティング方法では、要求していないトラヒックを受信するリンクが減少する。偽陽性の確率が最小であると予測されるｄ個のＢＦ候補を選択するための選択アリゴリズムは、次式のようであろう。
最小の｛ρ０ｋ，．．．，ρｄｋ｝ｆｐａを生じるｄを選択する
【０１５０】
留意すべきだが、ｋは、ｄ個のＬＩＴ表現の各々について同じである必要はない。加えて、アプリケーションのシナリオによっては、ＬＩＴ表現の各々について、１に設定されるビットの量ｋが異なることも有益でありうる。例えば、ｄ＝８の場合、ｋを例えば｛３；３；４；４；５；５；６；６｝のように配分してもよいだろう。それは、８個のＬＩＴのうちの２個のＬＩＴは、３ビットだけが１に設定され、２個のＬＩＴは、４ビットが１に設定され、以下同様に設定されることを意味する。この場合、選択アルゴリズムは、一般的な事例である上述したものであって、すべてのＬＩＴを構築するのに同じｋが用いられる場合に限って当てはまる、０の数が最小の事例に留まらない。
【０１５１】
図１７は、リンクＡとリンクＢとで構成されるパスを表すためｄ＝４のＢＦ候補を生成するという単純な事例についての最適化プロセスを示す。この例では、ＢＦ２が、パケットヘッダ内でルーティングＢＦとして用いられることになる最適なＢＦであるが、それは、最大数のゼロを含んでおり、従って、偽陽性を与える全体的な可能性が最小だからである。
【０１５２】
この最適化のもう１つの解釈は、所定の最大の所望の偽陽性率について、ｄ選択型ＬＩＴ最適化によって、ＢＦにもっと多くのリンク識別子を挿入することが今では可能であり、それによって、さらなるホップへと拡大し、もっと多くの宛先ホストに到達することができるような、より大きな配信ツリーを構築することも可能であるということであろう。
【０１５３】
ＢＦの最適化は、全体的な偽陽性率に限定される必要はなく、他のポリシー、またはネットワーク最適化ポリシーを考慮に入れてもよいだろう。例えば、ｄ個のＢＦ候補を生成した後、ルーティング最適化モジュールが、転送要素の所定のリンクＩＤタグは、リンクの特定の部分集合について望まれていない偽陽性、例えば、ピアされていない領域や遅いネットワークパスや輻輳している領域への転送をもたらそうとしているかどうかチェックすることができてもよいだろう。この場合、絶対的な値としては最良の偽陽性率を有することができたとしても、このＢＦの選択肢を廃棄することを選択してもよいだろう。この一例を表１に示す。
0005214804.tif 000004
表１
【０１５４】
表１は、各ＢＦ候補について、全体的な偽陽性率だけでなく特定のリンクの３つの部分集合（領域間リンク、低容量ゾーン内のリンク、輻輳リンク）についての偽陽性率を示す。領域間リンク、低容量ゾーン内のリンク、または輻輳リンク内の偽陽性は、その他のリンク内の偽陽性より有害であると仮定する。候補ＢＦ３は、全体的な偽陽性率は低いが、低容量ゾーン内および輻輳リンク内でのリンクについての偽陽性の確率が高い。従って、候補ＢＦ２は候補ＢＦ３よりも全体的な偽陽性率は高いけれども、低容量ゾーン内および輻輳リンク内でのリンクについての偽陽性の確率がより低いことから、パケットヘッダについてのＢＦとしてＢＦ２候補を選択する方が望ましいであろう。このようにして、本実施形態は、ＢＦが、偽陽性の全体的な確率に基づくのではなく、選択されたリンクにおける（本実施形態では、偽陽性がより有害であると考えられるリンクについての）偽陽性の確率に基づいて選択されることを可能にする。
【０１５５】
従って、本発明の本態様は、ＢＦが偽陽性を返すことが原因で一定のネットワークエリアにパケットが誤って進入することを回避する（または最小化する）ように、パケットヘッダ用の転送ＢＦを構築する強力な方法を提供することが分かる。ｄ個の同等のＢＦ候補を生成して、ＢＦ候補のうちの１つを選択することは、ネットワークを通るパケットの必須のパスは維持されていることを保証するが、所定のリンク上での偽陽性を最小化することや、偽陽性の影響をもっと好都合なパスに分散することもできる。
【０１５６】
本発明の利点
提案するリンクＩＤタグを使用すると、リンク情報の所与の集合がブルームフィルタのような確率的コンパクト表現に挿入される際の、偽陽性率が減少する。偽陽性率が減少すると、結果として、ＢＦベースのルーティング手法の帯域幅効率が向上した解決策が得られる。ＬＩＴを生成して最も適したＢＦを選択することについて提案する方法は、転送プロセスの簡素さを失うことなく、かつ、非常に安価な実装コストで、ＢＦベースのルーティングスキームの性能を大幅に向上させる。従って、所定の最大偽陽性値について、提案するリンクＩＤタグに基づくＢＦの構築は、ＢＦのサイズを増加させることなくＢＦに追加可能なリンク情報の容量を増加させる。
【０１５７】
リンクＩＤを表すリンクＩＤタグ候補を上手に選択することは、ＢＦによって決められるルーティングのホップの最大数を増加させるだけでなく、例えば、ＬＩＤによって識別される所定のネットワーク領域における偽陽性を回避（または最小化）することによって、または、例えば、偽陽性の影響をもっと好都合なパス全体にわたって拡散することによって、偽陽性の影響を制御することにおける柔軟性を高める。このより精緻な制御によって、ルーティングポリシーおよびセキュリティポリシーを本書で述べたＢＦベースのソースルーティング手法に適用することが可能になることが見込まれる。
【０１５８】
図１８は、ｄ選択型ＬＩＴ技法に従って構築されたＢＦの実際の偽陽性率の改善を示す。図１８は、偽陽性率を、５つの事例についてＢＦとして符号化されたリンクの数の関数として示す。
【０１５９】
１）ｋ＝５で、リンクＩＤをＢＦへと符号化した場合（＋で示す）
２）ｋ＝４、ｄ＝２で、ＬＩＴをＢＦへと符号化した場合（×で示す）
３）ｋ＝５、ｄ＝４で、ＬＩＴをＢＦへと符号化した場合（＊で示す）
４）ｋ＝６、ｄ＝８で、ＬＩＴをＢＦへと符号化した場合（白い四角で示す）
５）ｋ＝６、ｄ＝１６で、ＬＩＴをＢＦへと符号化した場合（黒い四角で示す）
【０１６０】
図は、５０回の実験に対する偽陽性率の平均と拡散(spread)とを、データポイント（フィルタ内の要素の数）毎に示す。
【０１６１】
ＬＩＴをＢＦへ符号化すると、偽陽性率が著しく減少し、減少幅は、ＢＦにおけるリンクの数が増加するにつれて拡大することが分かる。２４４ビットまでのＢＦのサイズについて、リンクＩＤがその中に符号化されている標準的なＢＦは、およそ３５個のリンクＩＤを含んでいる場合、４％の偽陽性率を呈する。ｄ＝８のＬＩＴ  ＢＦでは、同様の偽陽性率は、６０個のリンクＩＤがＢＦに挿入されている場合に限って観察される。ｄ選択型ＢＦは、構築された標準のＢＦより、すべての設定について勝っている。
【０１６２】
図１９は、ｄ選択型ＬＩＴ技法に従って構築されたＢＦの実際の偽陽性率の向上が、どのようにしてｄの値に依存するのかを示す。図１９は、偽陽性率を、ｋが一定である場合にｄの３つの異なる値についてＢＦとして符号化されたリンクの数の関数として示す。
【０１６３】
１）ｋ＝５、ｄ＝４で、ＬＩＴＢＦへと符号化した場合（＋で示す）
２）ｋ＝５、ｄ＝８で、ＢＦへと符号化した場合（×で示す）
３）ｋ＝５、ｄ＝１６で、ＢＦへと符号化した場合（＊で示す）
【０１６４】
図は、データポイント（フィルタ内の要素の数）毎の５０回の実験に対する偽陽性率の平均と拡散(spread)とを示す。
【０１６５】
図１９から、パラメータｄ＝８を設定することは、一方では偽陽性率の削減と、他方ではシステム内でより大きなｄの値を有すること（例えば転送テーブルのサイズとＢＦヘッダの中のビット数（ｌｏｇ２（ｄ）ビット））に関連するコストの削減との間の良いトレードオフになりそうだと推論することができる。
【０１６６】
上記の方法では、ｄ個の「同等の」タグを一意のＩＤに関連付ける方法は、ＩＤがネットワークリンクについての何らかの識別子を参照するような利用シナリオに着目した。しかし、ＩＤからタグを生成するのに用いられるハッシング手順は、ｄ個のタグが導出されるＩＤの命名形式やサイズや意味に非依存である。従って、ｄ個のＢＦ候補を構築する上記の方法は、ネットワークリンクを符号化するＢＦに限定されるのではなく、ＩＤ（識別子）の集合が、例えばＢＦのような確率的データ構造によってコンパクトに表される、他の用途の場合にも適合する。
【０１６７】
一例をあげれば、ＩＤとしてホスト名（またはいずれかのタイプのホストＩＤ、識別子、署名、鍵、等）を考える場合にホスト名の集合のコンパクト表現を構築したい場合であろう。次いで、ｄ個のタグを各ＩＤについて同様に定義し、候補となるｄ個の表現（ブルームフィルタ）を演算し、そして、特定の利用シナリオに適した選択アルゴリズムを適用することができる。この場合もやはり、基本的な基準は、ＢＦの偽陽性確率予測を最小化することであってもよいだろうから、従って、選択アルゴリズムは、１に設定されるビット数が最も少ない候補、すなわち、何個の項目が挿入されたか、および、どのようにしてタグが構築されたかということに依存（例えば、すべてのタグで、固定数ｋビットが１に設定されているのか、あるいは、タグでのｋの濃度はさまざまであるのかに依存）して、ハッシング後の偽陽性確率が最も良い候補を選択するであろう。ＢＦに含まれる要素が少ないシナリオでは、ｋが大きい方が、ハッシング後の偽陽性推定量の結果が良いであろう。逆にＢＦがもっと詰まっている場合、要素毎のビット数（ｋ）を少なくすれば、偽陽性率が良好になるであろう。ｋの値にこのような柔軟性を持たせると、より多くの利用シナリオについて選択アルゴリズムが自然に適応する。
【０１６８】
同様に、それぞれの場合に最適化目標を達成するために、もっと緻密な選択戦略をとることもでき、例えば、ホストＩＤの試験集合を構築して、ＢＦ候補に対して偽陽性を試験し、観測された偽陽性率が最も少ないＢＦ候補が選択されてもよいだろう。その他のオフラインの選択基準には、一つでも偽陽性があればＢＦ候補を選択プロセスからすぐに排除するような試験集合が含まれてもよい（例えば、所定のリンクＩＤ（例えば或るネットワーク領域に広がるかもしくは領域間リンクに広がる使用量の多い仮想リンクＩＤ）については、ＢＦは偽陽性を一切引き起こしてはならないと指定することもできよう）。
【０１６９】
また、ｄ個のタグを有することの重要な利点も当然これに当てはまり、ポリシーの実行を有効にすることと、より良い成果をもたらすことと、新たなセキュリティメカニズムを有効にすることなどが、利点に含まれる。
【０１７０】
タグがそこから構築されうる、さらに想定されるＩＤには、ネットワーク領域（管理領域および物理領域）、ネットワークシステム、アプリケーションプロセス、ネットワークインタフェース、論理ポートおよび仮想ポート等が含まれる。アプリケーションによっては、複合的な最適化戦略や特定の選択基準が定義されてもよいし、他方、ｄ個のタグとｄ個のＢＦ候補を構築する基本的な方法が、単純な偽陽性率軽減アルゴリズムに加えてかまたはその代わりに、直接適用されてもよいだろう。
【図１】
0005214804.tif 000005
【図２】
0005214804.tif 000006
【図３】
0005214804.tif 000007
【図４】
0005214804.tif 000008
【図５】
0005214804.tif 000009
【図６】
0005214804.tif 000010
【図７】
0005214804.tif 000011
【図８】
0005214804.tif 000012
【図９】
0005214804.tif 000013
【図１０】
0005214804.tif 000014
【図１１】
0005214804.tif 000015
【図１２】
0005214804.tif 000016
【図１３】
0005214804.tif 000017
【図１４】
0005214804.tif 000018
【図１５】
0005214804.tif 000019
【図１６】
0005214804.tif 000020
【図１７】
0005214804.tif 000021
【図１８】
0005214804.tif 000022
【図１９】
0005214804.tif 000023
【図２０】
0005214804.tif 000024