(57)【要約】【課題】高速メッセージストリームをコンテンツベースに送出することに対するインフラの解決策を提供する。【解決手段】コンテンツベースの送出のためのインフラストラクチュア解決策において、フィルタパイプライン処理は、高速メッセージストリームの処理を可能にする。ドキュメントは、パブリッシャプロキシサーバー２１０からメッセージの特定の属性に関連付けられた属性ツリーに送出することによって、ネットワークに分配される。該ツリーは、属性値に基づいてメッセージをフィルタし、サブスクライバへの述語ベースの分配用サブスクライバプロキシサーバにメッセージを配布する。【選択図】図２
2007234014.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークにおいてドキュメントを配布する方法であって、
属性と、関連する値とを含むメッセージを属性ベースの送出サーバにおいて受け取るステップと、
前記メッセージを、前記属性に対応しているが他の属性には対応していない、値ベースの送出ツリーのルートに送出するステップと、
前記メッセージを、前記ルートから、前記メッセージの属性に関連付けられた値を含む第１の値域に対応する、前記値ベースの送出ツリーの少なくとも１つの中間ルータに送出するステップと、
前記少なくとも１つの中間ルータから、前記メッセージを、前記第１の値域に包含されており、前記メッセージ内の属性に関連付けられた値を含む第２の値域に対応する、述語ベースの送出サーバに送出するステップと、
前記述語ベースの送出サーバにおいて、前記メッセージをユーザサブスクリプションと一致させて前記メッセージをユーザに送出するステップと、
を含む、ネットワークにおいてドキュメントを配布する方法。
【請求項２】
前記メッセージを前記属性ベースの送出サーバにおいて解析して前記属性を識別するステップをさらに含む、  請求項１に記載の方法。
【請求項３】
前記属性ベースの送出サーバにおいて、前記属性に関連付けられた値を識別するラベルを前記メッセージに付けるステップをさらに含む、
請求項２に記載の方法。
【請求項４】
前記ラベルは前記メッセージの値の位置を示すポインタである、請求項３に記載の方法。
【請求項５】
前記ラベルは固有のメッセージＩＤをさらに含む、請求項３に記載の方法。
【請求項６】
前記メッセージはＸＭＬメッセージである、請求項１に記載の方法。
【請求項７】
前記ルートからまたは前記少なくとも１つの中間ルータの１つから、前記メッセージを、前記メッセージ内の属性に関連付けられた値を含まない第３の値域に対応する中間ルータに送出するステップをさらに含む、  請求項１に記載の方法。
【請求項８】
中間ルータを前記ルートと前記述語ベースの送出サーバ間に動的に追加するステップをさらに含む、  請求項１に記載の方法。
【請求項９】
前記追加された中間ルータは、前記送出されたメッセージ内の属性に関連付けられた値を含まない値域に対応する中間ルータに送出されたメッセージの数を減らす、請求項８に記載の方法。
【請求項１０】
前記の中間ルータを動的に追加するステップは前記属性の値の人気に基づいている、請求項８に記載の方法。
【請求項１１】
前記値の人気を、中間ノードにおいて総到着統計量を保持することによって求めるステップをさらに含む、  請求項１０に記載の方法。
【請求項１２】
前記メッセージをユーザサブスクリプションと一致させて前記メッセージをユーザに送出するステップは、
前記サブスクリプションに関連付けられた属性の総数を求めるステップと、
前記述語ベースの送出サーバにおいて受信された前記メッセージのインスタンスの数を計数するステップと、
前記メッセージをユーザサブスクリプションと、前記受信されたメッセージのインスタンスの数が前記ユーザサブスクリプションに関連付けられた前記属性の総数と等しい場合に、一致させるステップと、
をさらに含む、請求項１に記載の方法。
【請求項１３】
前記メッセージを述語ベースの送出サーバに送出するステップは、
前記送出ツリーの識別を含むラベルを前記メッセージに付けるステップをさらに含む、
請求項１に記載の方法。
【請求項１４】
コンテンツベースのネットワークにおいてメッセージを受け取るサブスクリプションを受理する方法であって、
サブスクライバプロキシサーバにおいて、各サブスクリプションが属性と、該属性に関連付けられた値のサブスクリプション範囲とを含む、複数のサブスクリプションを受け取るステップと、
前記複数のサブスクリプションを、各々が少なくとも１つのサブスクリプションの一部に対応する、前記属性の複数の重複しない範囲の、前記複数のサブスクリプション範囲の交差部分に対応する端点を決定することによって、集約するステップと、
前記端点を、前記属性に対応しているが他の属性には対応していない属性ツリーのルートに送出するステップと、
前記ルートにおいて、前記端点と他のサブスクライバプロキシサーバからの他の端点との結合の最小値および最大値を求めるステップと、
前記最小値および最大値を、どのメッセージを前記ルートに送るべきかを判断する、述語ベースの送出サーバに送出するステップと、
を有する方法。
【請求項１５】
前記属性および前記値域を前記述語ベースの送出サーバに格納するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
メッセージを前記属性ツリーにおける前記ルートからリーフノードに送出するのに使用される重複しないフィルタの集合を算出するステップをさらに含む、請求項１４に記載の方法。
【請求項１７】
前記の重複しないフィルタを算出するステップは、前記フィルタの範囲を最適化して、受信ノードの属性の範囲外に属性値を持つ送信メッセージの数を最小化するステップを含む、請求項１６に記載の方法。
【請求項１８】
各サブスクリプションは複数の属性と、関連する値を含み、前記端点を属性ツリーのルートに送出するステップは、前記サブスクリプションに含まれるすべての属性よりも少ない属性に対して行われる、請求項１４に記載の方法。
【請求項１９】
前記送出ステップが行われる属性および関連する値を、前記属性によってもたらされるフィルタリングの利益の程度に基づいて、決定するステップをさらに含む、請求項１８に記載の方法。
【請求項２０】
中間ルータを前記ルートと前記述語ベースの送出サーバ間に動的に追加するステップをさらに含む、請求項１４に記載の方法。
【請求項２１】
前記中間ルータを追加するステップは、前記送出されたメッセージ内の属性に関連付けられた値を含まない値域に対応する中間ルータに送出されるメッセージの数を減らすことになる、請求項２０に記載の方法。
【請求項２２】
前記メッセージはＸＭＬメッセージである、請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概して、コンテンツベースの情報配布および分散型パブリッシュ−サブスクライブシステムに関する。特に、本発明は、サブスクライバへのメッセージの効率的でスケーラブルなコンテンツベースのルーティングシステムおよび技術である。
【背景技術】
【０００２】
コンテンツベースのネットワークは、メッセージを、該メッセージの内容と一致するサブスクリプション（ｓｕｂｓｃｒｉｐｔｉｏｎ）を登録したすべてのエンドユーザに送出する。サブスクリプションとメッセージは共にＸＭＬで記述されている。各サブスクリプションは多数の属性についての値域の結合である。例えば、＜ＳＴＯＣＫ＝”ｘｙｚ”，５＜＝ＰＲＩＣＥ＜＝ｌ０＞と記述されるサブスクリプションは、値「ｘｙｚ」を持つ属性ＳＴＯＣＫを有するすべてのメッセージが５と１０の間の値を持つ属性ＰＲＩＣＥを有する場合、これらのメッセージへの関心を表している。それらの値を満たすメッセージはすべてサブスクリプションと一致しており、ユーザへ送られなくてはならない。高入力メッセージ速度および多数のサブスクリプションを調整するコンテンツベースのネットワークにとって、高速フィルタリング機構は必須のものである。
【０００３】
コンテンツベースの既存のネットワークアーキテクチャの１つが、非特許文献１および非特許文献２に記載されているＳＩＥＮＡである。ＳＩＥＮＡフィルタリング構造の一例１００を図１Ａに示す。各ノード１１０でのＳＩＥＮＡのフィルタリングデータ構造は、各サブスクリプション１２０のすべての属性に対する関心のすべての範囲をソートされた順に組織化する。メッセージの各属性に対応する値１３０が、この値に関心を持つすべてのサブスクリプションを識別するのに使用される。これは、メッセージが有するすべての属性に対して行われる。サブスクリプションがｎ個の属性に関心を持っている場合、メッセージは、フィルタリングデータ構造中のｎ個の異なる経路を通してこのサブスクリプションに達するはずである。したがって、ＳＩＥＮＡは、サブスクリプションを満たすメッセージの属性の数を数えて、一致するサブスクリプションを識別する。ＳＩＥＮＡは、ノード１４０のサブスクリプションが、この複数の子ノードによってサービスされるサブスクリプションのカバーを含むネットワーク中のすべてのノード１１０で、この機能を複製する。
【０００４】
このＳＩＥＮＡ解決策にはいくつかの欠点がある。コンテンツベースの各ルータは、各サブスクリプションに対して複合述語を完全に照合するためにマルチ属性のデータ構造をホストする。データ構造をメモリまたはプロセッサキャッシュに保持するための大きな空間要件に結びついた完全な述語一致コストは、メッセージ処理レイテンシを増加させる。最悪のシナリオでは、各サブスクリプションはＳＩＥＮＡコンテンツベースのネットワークのノードすべてに伝播される。ＳＩＥＮＡ解決策において単一ノードで照合されるサブスクリプションの数は、このように非常に大きくなることがあり、システムの拡張性(scalability)を制限することになる。さらに、図１Ｂの典型的なブロック図１６０に示されるように、ＳＩＥＮＡはすべてのメッセージを解析し、メッセージのすべての属性を、同じノードにおいて重複する範囲を持つすべてのサブスクリプションと一致させる。図１６０では、複数のノード１６５、１６６、１６７は同じメッセージ１７０を解析する。このことは、ＳＩＥＮＡのメッセージ当たりの一致時間を長くすることになるので、高速メッセージストリームを支援するこのアーキテクチャの能力を制限することになる。
【０００５】
ごく最近、大きな一連の研究が出現し、ユーザへの情報について大規模な選択的配布の問題が注目されるようになった。マルチキャストモデルを使用することに基づいたいくつかの解決策が提案されている。あらゆる考えられるサブスクライバ集合を捕らえるためにはマルチキャストのツリー数が２nまで大きくなるので、従来のマルチキャストモデルを使用することはスケーラブル(scalable)ではない。非特許文献３で明確に示されたチャネル化問題は、限られたマルチキャストツリー集合に送信元および送信先をマップして不要なメッセージ配信を最小化する解決策を提供している。非特許文献４を含む別のカテゴリーの研究は、ユーザサブスクリプションプロファイルの適切なクラスタリングによって、限定された数のマルチキャストツリーを生成している。上記の解決策では、フィルタリングは送信元、受信ポイント、またはこの両方で行われる。これに対して、非特許文献５のような他の著者は、選択的な情報配布のために、所与のマルチキャストツリーの中間ノードでフィルタを使用することを提案している。非特許文献６は、フィルタの配置およびリーク最小化の問題に対する解決策を提供している。マルチキャストに基づいた手法では、メッセージの送出経路は、事前に定められた、マルチキャストツリーのトポロジーに制限されている。これらの手法は、単一の属性を持つトピック／サブジェクトベースのシステムまたはメッセージには良好に適用できるが、これらの手法は多数の属性についての一般的な述語を支援するのには適していない。
【０００６】
複合述語は、送信元または受信者のいずれかで最終的に一致しなければならないので、マルチキャストツリーにサブスクリプションを関連付けるという追加の利点は取るに足りないものである。モデルをマルチキャストモデルに限定しないで、一般的モデルは、ＳＩＥＮＡの研究および非特許文献７でも提案されている、コンテンツベースのルータからなるネットワークを生成することである。コンテンツベースのルータは、サブスクリプションプロファイルに基づいて送出テーブルを生成し、述語一致に基づいてデータのフィルタリングと送出の両方を行う。任意の情報配布ネットワークの場合と同じように、コンテンツベースの各ルータでサブスクリプション述語を照合する速度が、持続可能なスループットを決定する。コンテンツベースのルーティングの目的は、ワイヤスピードを満たす処理レイテンシを提供することである。
【０００７】
ＳＩＥＮＡおよびＧＲＹＰＨＯＮのいずれにおいても、各ルータは、すべてのサブスクリプションに関する状態を保持する必要がある。ＳＩＥＮＡの著者が、状態を最小化するサブスクリプションの結合を提案したとしても、この結果として得られる利点はサブスクリプション削除によって得られない。
【０００８】
非特許文献８に記載されているような膨大な量の研究が、単一ノードでの一般的述語一致に対するよりよい解決策を見つけることについて行われている。単一ノードを使用した、このような集中化された解決策は、絶えず増大していく情報フロー速度を支援しそうにない。
【０００９】
コンテンツ空間をサブスクリプションにマップする逆インデクシング構造が、非特許文献９で探求された。これらの著者はまた、単一ノードでの述語を一致させる計数ベースの機構の変形例を提案している。しかし、分散型システムに計数方法を適用することは、以下に説明する新たな問題を発生させる。
【００１０】
ＳＩＥＮＡのようなある解決策では、メッセージ配布経路がサブスクリプション移動経路と組み合わされているので、ルーティングの柔軟性に欠ける。これに対して、非特許文献１０のような他の解決策は、間接的手法に基づいており、連絡地点をメッセージがサブスクライバと出会うブローカーノードの形で使用している。
【００１１】
Ｐ２Ｐネットワーク上のコンテンツベースの情報配布が、非特許の文献１１に記載されているＸＲＯＵＴＥで提案されている。この研究の主な関心事は、ネットワーク帯域幅の使用法であり、ルーティングテーブルの大きさを最小化することである。
【００１２】
弱いフィルタリングの概念は、非特許文献１２のようなサマリーベースのルーティングで使用されている。
【非特許文献１】Ａ．Ｃａｒｚａｎｉｇａ，Ｍ．Ｒｕｔｈｅｒｆｏｒｄ  ＆  Ａ．Ｗｏｌｆ，Ａ  Ｒｏｕｔｉｎｇ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｃｏｎｔｅｎｔ  Ｂａｓｅｄ  Ｎｅｔｗｏｒｋｉｎｇ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  ＩＮＦＯ  ＣＯＭ（Ｍａｒ  ２００４））
【非特許文献２】Ａ．Ｃａｒｚａｎｉｇａ  ＆  Ａ．Ｗｏｌｆ，Ｆｏｒｗａｒｄｉｎｇ  ｉｎ  ａ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｎｅｔｗｏｒｋ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＳＩＧＣＯＭＭ（Ａｕｇ  ２００３）
【非特許文献３】Ｍ．Ａｄｌｅｒ，Ｚ．Ｇｅ，Ｊ．Ｋｕｒｏｓｅ，Ｄ．Ｔｏｗｓｌｅｙ，＆  Ｓ．Ｚａｂｅｌｅ，Ｃｈａｎｎｅｌｉｚａｔｉｏｎ  Ｐｒｏｂｌｅｍ  ｉｎ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｄａｔａ  Ｄｉｓｓｅｍｉｎａｔｉｏｎ，ＩＯＮＰ（２００１）
【非特許文献４】Ａ．Ｒｉａｂｏｖ，Ｚ．Ｌｉｕ，Ｊ．Ｗｏｌｆ，Ｐ，Ｙｕ，＆  Ｌ．Ｚｈａｎｇ，Ｃｌｕｓｔｅｒｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｐｕｂｌｉｃａｔｉｏｎ−Ｓｕｂｓｃｒｉｐｔｉｏｎ  Ｓｙｓｔｅｍｓ，  Ｐｒｏｃ．  ｏｆ  ＩＣＤＣＳ（２００２）
【非特許文献５】Ｍ．Ｏｌｉｖｅｉｒａ，Ｊ．Ｃｒｏｗｃｒｏｆｔ，＆  Ｃ．Ｄｉｏｔ，Ｒｏｕｔｅｒ  Ｌｅｖｅｌ  Ｆｉｌｔｅｒｉｎｇ  ｏｎ  Ｒｅｃｅｉｖｅｒ  Ｉｎｔｅｒｅｓｔ  Ｄｅｌｉｖｅｒｙ，Ｐｒｏｃ．ｏｆ  ２ｎｄ  Ｉｎｔ’ｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｎｅｔｗｏｒｋｅｄ  Ｇｒｏｕｐ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ（２０００）
【非特許文献６】Ｒ．Ｓｈａｈ，Ｒ．Ｊａｉｎ，＆  Ｆ．Ａｎｊｕｍ，Ｅｆｆｉｃｉｅｎｔ  Ｄｉｓｓｅｍｉｎａｔｉｏｎ  ｏｆ  Ｐｅｒｓｏｎａｌｉｚｅｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｕｓｉｎｇ  Ｃｏｎｔｅｎｔ  Ｂａｓｅｄ  Ｍｕｌｔｉｃａｓｔ，Ｐｒｏｃ．ｏｆ  Ｉｎｆｏｃｏｍ（２００２）
【非特許文献７】Ｍ．Ａｇｕｉｌｅｒａ，Ｒ．Ｓｔｒｏｍ，Ｄ．Ｓｔｕｎｎａｎ，Ｍ．Ａｓｔｌｅｙ，＆  Ｔ．Ｃｈａｎｄｒａ，Ｍａｔｃｈｉｎｇ  Ｅｖｅｎｔｓ  ｉｎ  ａ  Ｃｏｎｔｅｎｔ  Ｂａｓｅｄ  Ｓｕｂｓｃｒｉｐｔｉｏｎ  Ｓｙｓｔｅｍ，Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ（１９９９）（”ＧＲＹＰＨＯＮ”）
【非特許文献８】Ｆ．Ｆａｂｒｅｔ，Ｈ．Ａ．Ｊａｃｏｂｓｅｎ，Ｆ．Ｌｌｉｒｂａｔ，Ｊ．Ｐｅｒｅｉｒａ，Ｋ．Ａ．Ｒｏｓｓ  ＆  Ｄ．Ｓｈａｓｈａ，Ｆｉｌｔｅｒｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｆｏｒ  Ｖｅｒｙ  Ｆａｓｔ  Ｐｕｂｌｉｓｈ／Ｓｕｂｓｃｒｉｂｅ  Ｓｙｓｔｅｍｓ，ＡＣＭ  ＳＩＧＭＯＤ（２００１）
【非特許文献９】Ｔ．Ｙａｎ  ＆  Ｈ．Ｇａｒｃｉａ−Ｍｏｌｉｎａ，Ｉｎｄｅｘ  Ｓｔｒｕｃｔｕｒｅｓ  ｆｏｒ  Ｓｅｌｅｃｔｉｖｅ  Ｄｉｓｓｅｍｉｎａｔｉｏｎ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  ｕｎｄｅｒ  ｔｈｅ  Ｂｏｏｌｅａｎ  Ｍｏｄｅｌ，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ（１９９４）
【非特許文献１０】Ｐ．Ｊ．Ｚ．Ｇｅ，Ｊ．Ｋｕｒｏｓｅ  ＆  Ｄ．Ｔｏｗｓｌｅｙ，Ｍｉｎ−Ｃｏｓｔ  Ｍａｔｃｈｍａｋｅｒ  Ｐｒｏｂｌｅｍ  ｉｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｕｂｌｉｓｈ／Ｓｕｂｓｃｒｉｂｅ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ，ＯＰＥＮＳＩＧ，（２００２）
【非特許文献１１】Ｒ．Ｃｈａｎｄ  ＆  Ｐ．Ｆｅｌｂｅｒ，Ａ  Ｓｃａｌａｂｌｅ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｒｏｕｔｉｎｇ  ｉｎ  Ｏｖｅｒｌａｙ  Ｎｅｔｗｏｒｋｓ，ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｎｅｔｗｏｒｋ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ（２００３）
【非特許文献１２】Ｙ．Ｗａｎｇ，Ｌ．Ｑｉｕ，Ｃ．Ｖｅｒｂｏｗｓｋｉ，Ｄ．Ａｅｈｌｉｏｐｔａｓ，Ｇ．Ｄａｓ  ＆  Ｐ．Ｌａｒｓｏｎ，Ｓｕｍｍａｒｙ−Ｂａｓｅｄ  Ｒｏｕｔｉｎｇ  ｆｏｒ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｅｖｅｎｔ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｎｅｔｗｏｒｋｓ，ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって、現在、高速メッセージストリームをコンテンツベースに送出することに対するインフラの解決策を提供する必要がある。本発明者の知っている限りでは、このような技術は現在利用可能ではない。
【課題を解決するための手段】
【００１４】
本発明のコンテンツベースのスケーラブルなイベントマルチキャストプラットフォームは、非常に多くのエンドユーザを支援しながら、高速メッセージストリームをフィルタおよびマルチキャストするアーキテクチャである。本発明は、フィルタリングタスクをより単純な要素に分割し、それらの要素を複数のノードに分散することによって上記制限を克服するものである。メッセージは、ノードで部分的にフィルタされ、さらなるフィルタリングために１つまたは２つ以上の下流ノードに送られる。パイプラインによるフィルタリングによって、複数のノードを異なるメッセージの異なる部分で同時に作動させることができ、それによって高システムスループットを支援することができる。これは、各ノードにおけるメッセージ当たりの処理遅れが、メッセージ相互間到着時間を一致させるために減少させられるからである。ここで説明しているアーキテクチャは、異なる属性を異なるフィルタリングツリーと一致させるタスクを分割する。フィルタリングツリーのメッセージを解析する必要性は、メッセージを適切なフィルタリングツリーに送る前に属性の値をラベルとして付けることによってさらに低下する。
【００１５】
本発明のアーキテクチャは、各ノードのリソース制約を帯域幅および記憶容量の点から尊重し、各ノードにこのリソースに相応したフィルタリングおよび送出負荷を割り当てる。これは弱いフィルタリングの考えを用いて行われ、それによって、最適なアルゴリズムがこのリソース制約が与えられた各ノードにおいて最良のフィルタを生成する。本発明は、既存のツリーが負荷に対処できない場合にのみ新しいノードを追加することによって、すべての属性のフィルタリングツリーを適応的に構築する。このリソース制約を満たすために、負荷（送出および処理）と状態空間が共に各ノードで平衡を保たれるサブスクリプション分割手法も提供される。
【００１６】
本発明は、ツリーの各ノードのスループットを、選択的なサブスクリプションを使用して、調整する能力も提供する。規範的事例において、ここで説明しているアーキテクチャは、各サブスクリプションにつき１つの属性のみをサブスクライブする(subscribe)。最後のホップで、１つの属性ツリーからのサブスクリプションに対応するメッセージが受け取られると、該メッセージは解析され、この属性はすべてサブスクリプションの関心と照合させられる。解析コストを削減し、それによってシステムスループットを向上させるために、本発明は、すべてのノードがサブスクリプションの２つ以上の属性にサブスクライブし、このコピーがすべてのサブスクライブされた属性に沿って受け取られる場合のみ、メッセージを一致させる新しい技術を用いている。この選択的なサブスクリプションは解析演算数を低減し、システムスループットを向上させることになる。
【００１７】
本発明の一実施態様において、ネットワークにおいてドキュメントを配布する方法が提供される。メッセージは属性ベースの送出サーバで受け取られる。該メッセージは属性とそれに関連する値とを含んでいる。メッセージは、該属性に対応する、値ベースの送出ツリーのルート（根）に送出される。該メッセージは、該ルートから、メッセージ中の属性に関連する値を含む第１の値域に対応する、値ベースの送出ツリーの少なくとも１つの中間ルータに送出される。該メッセージは、前記の少なくとも１つの中間ルータから、第１の範囲に含まれ、メッセージの属性に関連する値を含む第２の値域に対応する、述語ベースの送出サーバに送出される。該メッセージは、該述語ベースの送出サーバにおいてユーザサブスクリプションと一致させられ、ユーザに送出される。
【００１８】
本方法は、属性を識別する、属性ベースの送出サーバにおいてメッセージを解析するステップも含んでよい。この場合、ラベルを、属性に関連する値を識別する、属性ベースの送出サーバにおいてメッセージに付けてもよい。
【００１９】
該ラベルは、値の、メッセージ中の位置を示すポインタであってもよい。該ラベルは、固有のメッセージＩＤをさらに含んでいてもよい。該メッセージはＸＭＬメッセージであってもよい。
【００２０】
本方法は、メッセージを、ルートからまたは少なくとも１つの中間ルータの１つから、属性に関連する値をメッセージに含んでいない第３の値域に対応する中間ルータに送出するステップも含んでよい。
【００２１】
本方法は、中間ルータを、ルートと述語ベースの送出サーバ間に動的に追加するステップも含んでもよい。追加された中間ルータは、送出されたメッセージの属性に関連する値を含まない値域に対応する中間ルータに送出されるメッセージ数を減らすことができる。
【００２２】
メッセージをユーザサブスクリプションと一致させて、該メッセージをユーザに送出するステップは、サブスクリプションに関連する属性の総数を求めるステップと、述語ベースの送出サーバで受信されたメッセージのインスタンス数を計数するステップと、受信したメッセージのインスタンス数がサブスクリプションに関連する属性の総数と等しい場合に、該メッセージをユーザサブスクリプションと一致させるステップとをさらに含んでいてもよい。
【００２３】
述語ベースの送出サーバにメッセージを送出するステップは、送出ツリーの識別を含むメッセージにラベルを付けるステップをさらに有していてもよい。
【００２４】
本発明の他の実施態様は、コンテンツベースのネットワークでサブスクリプションを受け取るメッセージを受理する方法である。サブスクライバプロキシサーバでは、各サブスクリプションが、属性と、該属性に関連する値のサブスクリプション範囲とを含む複数のサブスクリプションが受け取られる。該サブスクリプションは、属性の重複しない範囲の端点を求めることによって集約され、各重複しない範囲は少なくとも１つのサブスクリプションの一部に対応し、該端点はサブスクリプション範囲の共通部分に対応する。該端点は、属性に対応する属性ツリーのルートに送出される。該ルートでは、他のサブスクライバプロキシサーバからの他の端点と共に端点の集合の最小値および最大値が求められる。該最小値および最大値は、どのメッセージをルートに送るべきかを判断する、述語ベースの送出サーバに送出される。
【００２５】
本方法は、述語ベースの送出サーバにおいて属性および値域を格納するステップをさらに有していてもよい。
【００２６】
本方法は、属性ツリーのルートからリーフ(leaf)ノードにメッセージを送出するのに使用される重複しないフィルタ集合を算出するステップを含んでいてもよい。該重複しないフィルタを算出するステップは、フィルタの範囲を最適化して、受信ノードの属性の範囲外に属性値を持つ送信メッセージ数を最小化するステップも有してもよい。
【００２７】
各サブスクリプションは複数の属性とそれに関連する値を含んでいてもよく、端点を属性ツリーのルートに送出するステップは、サブスクリプションに含まれるすべての属性よりも少ない属性に対して行われる。この場合、本方法は、属性によって与えられるフィルタリングの利点の程度に基づいて、送出ステップが行われる属性およびそれに関連する値を求めるステップをさらに有していてもよい。
【００２８】
本方法は、ルートと述語ベースの送出サーバ間に中間ルータを動的に追加するステップをさらに有していてもよい。この場合、中間ルータを追加するステップは、送出されたメッセージ中の属性に関連する値を含まない値域に対応する中間ルータに送出されるメッセージ数を減らすことになる。
【発明を実施するための最良の形態】
【００２９】
コンテンツベースのネットワーキングは、メッセージが、該メッセージに付けられている特定の送信先アドレスではなく、このコンテンツに基づいて送出される新しいデータルーティングパラダイムである。このパラダイムでは、ユーザへのデータ配布は、パブリッシャ（送信元）がメッセージをパブリッシュ（発表）し、サブスクライバ（受信者）がコンテンツに関する関心を登録するというパブリッシュ−サブスクライブ（ｐｕｂｌｉｓｈ−ｓｕｂｓｃｒｉｂｅ）モデルに基づいている。各メッセージのコンテンツは、（ｓｙｍｂｏｌ＝”ｇｏｏｇｌｅ”；ｐｒｉｃｅ＝１９６．８）のような、属性の名前と値とが対になったリストを持っている。サブスクライバの関心は、通常、（ｓｙｍｂｏｌ＝”ｇｏｏｇｌｅ”＆ｐｒｉｃｅ＞２００＆ｖｏｌｕｍｅ＞１１Ｍ）のような選択述語として表される。コンテンツベースのネットワークインフラストラクチュアは、適切な選択述語を一致させることによってパブリッシャからサブスクライバへの選択的な情報配布を可能にしている。
【００３０】
しかしながら、コンテンツベースのネットワークインフラストラクチュアによって提供される豊富な機能と共に、各メッセージを解析してそれをすべてのサブスクリプションと一致させることから生ずる、メッセージ処理のかなりの複雑さが生じる。それによって生じるメッセージ処理レイテンシによって、種々のサイトから非常に多くのサブスクライバに向けられた高いメッセージパブリッシング速度の支援が困難になる。例えば、ＮＡＳＤＡＱのリアルタイムの情報だけで、市場時間外において毎秒最大６０００のメッセージを含んでおり、何十万ものユーザがそれらの情報提供にサブスクライブ（予約購読）することができる。
【００３１】
本発明者らは、高速のコンテンツベースの情報配布ができる、コンテンツベースのスケーラブルなイベントマルチキャストプラットフォームを開発した。該プラットフォームは、メッセージの高ストリーミング速度を支持するものである。この研究の特定の目的は、コンテンツベースの豊富なセマンティックス（semantics）を支援しながら、メッセージ到着率と整合可能なメッセージ処理レイテンシを達成することである。主要な設計理念は、各サーバにおけるリソース制約を尊重しながら、複数のサーバの間で戦略的に多重属性サブスクリプション一致タスクを効率的に分割することおよびそれらのタスクを配分することである。基本的に、ここで説明しているプラットフォームのスループットの向上は、タスクをより小さなサブタスクへ分割することによってシステムのエンドツーエンドスループットが向上するパイプライン処理の基本原理からもたらされるものである。
【００３２】
コンテンツベースのルータにおけるメッセージ処理速度は、サブスクリプションルックアップデータ構造、述語一致アルゴリズム、および全空間要件のような様々な要因に左右される。ここで説明しているアーキテクチャは、複数のノード上に分散型サブスクリプション一致データ構造を構築する点が、従来技術のシステムとは異なっている。本アーキテクチャは、このデータ構造を使用してメッセージ処理の高速化を達成でき、次の利点、すなわち、ａ）空間および送出帯域幅要件に対する制御が可能になる。ｂ）各ノードが、完全なサブスクリプション述語の全体的な一致を目指した分散的方法で、述語の部分的一致に参加することが可能になる。ｃ）各ノードでの処理の複雑さがメッセージ到着率と整合できるように、サブスクリプション一致プロセスを段階的に行うことが可能になる、を有する。
【００３３】
本発明のアーキテクチャは、フィルタリングパイプライン処理を可能にする３つメッセージ送出段階を有している。各段階は、参加ノード集合およびそれらの明確に定められた役割によって定められる。それらの段階は、状態空間の制約および帯域幅の制限を満たしながら、フィルタリングパイプライン処理を最大化する効率的なシステムを生成する。この結果、本発明の次の有利な特徴が得られる。
【００３４】
（１）参加ノードの空間要件を満たす、情報のフィルタリングと送出のための一貫した分散型データ構造。
【００３５】
（２）コンテンツ人気分布およびサブスクリプションプロファイルに適合可能な、メッセージのフィルタリングと送出のための、効率的で属性特有のツリー構築。空間要件が所与のものとすると、最適なフィルタリング構造を構築するアルゴリズムが提供される。
【００３６】
（３）完全なサブスクリプション述語の高速一致のための楽観的な計数アルゴリズム。
【００３７】
（４）タスク分散がシステム内のメッセージ数を増加させることにもなるので、タスク分散をコンテンツ人気およびサブスクリプションの関心に基づいて変更する手法が提供される。
【００３８】
（５）高価なメッセージ解析動作をネットワークエッジに制限する、ネットワーク内部へのラベルベースの送出。
【００３９】
ベンチマークは、本発明のアーキテクチャが、１０個の属性の述語を持つ１００，０００個のサブスクリプションに対する毎秒５，０００より多いメッセージのスループットを維持できることを示す、本発明のアーキテクチャの実システムの実施から生じる。
【００４０】
アーキテクチャ
情報モデル：本発明のインフラストラクチュアでは、パブリッシャからのイベント通知は、ＸＭＬフォーマットでの＜ｔｙｐｅ，ａｔｔｒｉｂｕｔｅ  ｎａｍｅ（ａ），ｖａｌｕｅ（ｖ）＞の３個組のリストを含むメッセージｍに関連付けられている。ここで、ｔｙｐｅは情報の種類（例えば、フロート、文字列）を指す。ユーザからの各サブスクリプションｕ（同様にＸＭＬフォーマット）はｕ＝Ｐ1∧．．．∧Ｐnのような結合形の選択述語として表される。ｕの各要素Ｐiは、＜ｔｙｐｅ；ａｔｔｒｉｂｕｔｅ  ｎａｍｅ（ａ）；ｖａｌｕｅ  ｒａｎｇｅ（Ｒ）＞として表され、ここで、Ｒ：（ｘi，ｙi）である。Ｐiは、ｘi≦νi≦ｙiとなるような、＜ａi，νi＞を含んでいるメッセージに対してのみ真と評価される。対応する述語がすべてメッセージｍのコンテンツに基づいて真であると評価された場合、メッセージｍはサブスクリプションｕに一致する。
【００４１】
概要：ここで説明しているアーキテクチャは、解析、フィルタリング、および送出負荷を複数の仮想ノード（サーバ）間に分散することによって、高速なコンテンツベースＸＭＬ情報配布のためのインフラストラクチュアを、関心を持っているサブスクライバに提供する。一般的なアーキテクチャ２００（図２）は、パブリッシュ-サブスクライブサービスモデルに基づいている。パブリッシャ２０５は、パブリッシャプロシキサーバ（ＰＰＳ）２１０と連絡をとり、該パブリッシャの情報２１２をパブリッシュする。同様に、ユーザ２９０は、サブスクライバプロキシサーバ（ＳＰＳ）２８５と連絡をとってサブスクリプション要求２８０を送り、このサブスクリプションと一致する通知２７５を得る。それらのサーバ２８５の選択は距離的に近いことまたは負荷に基づいてもよい。各属性ａに対応する１つのフィルタリングツリー２７０がある。属性の値を含むいかなるメッセージ２２０もａの属性ツリー上に送られる。
【００４２】
ＰＰＳ２１０は、メッセージに含まれる属性に対応するすべての属性ツリー２７０のルート（root）にメッセージ２２０を送る。該メッセージは他のどのツリーにも送られない。各属性ツリー２７０は、この特定の属性に対応する値を使用して範囲ベースのフィルタリングを行う。どのサブスクライバもこの値に関心を持たなければ、ツリーは該メッセージを廃棄する。そうでない場合、該メッセージは複写され、一致サブスクリプションを持つすべてのＳＰＳ２８５に送出される。ＳＰＳは、該メッセージと一致するすべてのユーザサブスクリプションを識別し、それらへ該メッセージを送出する。
【００４３】
概念的に、ＰＰＳ２１０は、メッセージ中の属性に基づいたフィルタリングを行う（図２の段階１）。属性のツリーは、このメッセージ中のこの属性の値に対してフィルタリングを行う（段階２）。メッセージと完全に一致する全てのサブスクリプションを識別する述語一致は、ＳＰＳで行われる（段階３）。
【００４４】
ここで、サブスクリプションプロセスおよびメッセージ送出プロセスの概要を説明し、各コンポーネントの機能を定義する。
【００４５】
サブスクリプションプロセス
図３を参照すると、ユーザ３０５、３０６のようなユーザが、複数の属性についてのこの関心の範囲を含むサブスクリプション３０７、３０８をＳＰＳ３１０に送る。ＳＰＳ３１０は全サブスクリプションを局所的に格納する。ＳＰＳ３１０は、この後、ユーザ３０５、３０６に代わって異なる属性の異なる値域をサブスクライブする。ＳＰＳ３１０は、個々のユーザサブスクリプションｕ（例えば、ｕ1，ｕ2）を集約して各属性に対する重複しない範囲３１５を作る。属性ａに関心のあるすべてのユーザサブスクリプションｕを持つＵa集合を考える。これらのサブスクリプションの各々は、属性ａの範囲（ｘi，ｙi）によって決定される。Ｕa中にこのようなサブスクリプションがｎ個ある場合、それらの範囲は、コンテンツ空間上で多くとも２n個の異なる点で交差することができ、そして重複するサブスクリプションがある場合には、異なる点の数はより少なくなるかもしれない。
【００４６】
例えば、所与の属性に対する範囲＜２０，７０＞および＜１０，５０＞を持った２つのサブスクリプションを考える。それらの範囲は、異なる点（１０，２０，５０，７０）でコンテンツ空間と交差する。交点の順序集合では２つの隣接した交点（ｌ，ｍ）によってこれらの範囲が定義されるものとする。上記例の場合、これら範囲は、（１０，２０）、（２０，５０）、（５０，７０）となる。これらの範囲の各々に対して、ＳＰＳ３１０は新しいサブスクリプションＳを生成し、それを対応する属性ツリーのルート３２０に送る。このサブスクリプション集約プロセスは、あるユーザサブスクリプションがそれに関心を持つ場合、およびあるユーザサブスクリプションがそれに関心を持つ場合にのみ、ＳＰＳ３１０が値をサブスクライブすることを保証することに留意されたい。
【００４７】
各属性ツリーのルート３２０は、１つまたは２以上のＳＰＳ３１０からサブスクリプションＳを受け取る。ルートは、すべてのＳＰＳからＳ中のすべての範囲の結合によってカバーされた値空間の最小値および最大値ｔ：（ｘmin，ｙmax）を見つける。該ルートは、範囲ｔ（要素３３０）をすべてのＰＰＳ３４０に通知する。
【００４８】
メッセージのフィルタリングと送出
本発明の目的は、メッセージを、コンテンツベースのルーティングを使用して、関心を持つサブスクライバに効率的かつ正確に配信することである。高いエンドツーエンドスループットを得るために、ここで説明しているアーキテクチャは、フィルタパイプライン処理の考え方を用いる。うまく設計されたコンポーネントのパイプラインは、エンドツーエンドスループットを向上させる。上述したように、イベントのフィルタリングとルーティングの複雑なタスクは、図２に示した３つの段階に分割される。段階１は属性ベースの送出であり、属性名に基づいてメッセージを送出するのに使用される。段階２は値ベースの送出であり、特定の属性の値に基づいてメッセージをフィルタし、正しいＳＰＳにそれらを送出するのに使用される。段階３は述語ベースの送出であり、複合述語に基づいて全サブスクリプションを一致させて、ユーザに通知するのに使用される。下記は図４のブロック図を参照して行う、本発明によるコンテンツベースのルーティングの概要の説明である。
【００４９】
段階１（要素４０１）は、ＰＰＳ４１０で行われる、属性ベースの送出である。各パブリッシャ４０５は、属性ベースの送出サーバ（ＰＰＳ）４１０に割り当てられている。パブリッシャ４０５は、複数の属性−値対４２０を含む新しいメッセージ４１５をＰＰＳ４１０に送る。ＰＰＳ４１０は、入力メッセージ４１５を解析してこの属性名を識別する。この後、該メッセージのコピーは、該メッセージに存在する属性ａiに対応する、すべての値ベースの送出ツリーＴiのルート４４２、４４３に送出される。ＰＰＳは、該メッセージをＴiに送出する前に、ラベル（例えば、図４のラベル４１１、４１２）として属性ａiの値Ｖiを付ける。Ｖiはどのような長さでもよいので、ラベルはメッセージ中のＶiの位置を示すポインタになりえる。ＰＰＳは、固有のメッセージＩＤ  Ｍも該メッセージに付ける。Ｍは、該メッセージのすべてのコピーに、それらがどの属性ツリーに送出されるかにかかわらず、共通である。
【００５０】
段階２（要素４４１）は値ベースの送出であり、中間ルータ（ＩＲ）４４５、４４６で行われる。メッセージを値ベースの送出ツリーＴjのルート４４２、４４３で受け取ると、本目的は、サブスクリプション一致値Ｖjを有する、すべてのＳＰＳ４８０にこのメッセージを配布することである。値ベースの送出は、２つの機能、すなわちメッセージのフィルタリングとマルチキャスティングを提供するために、中間ルータ（ＩＲ）４４５、４４６を使用して階層的送出ツリー構造として実行される。フィルタリングは、メッセージのマルチキャストを、該メッセージに含まれている値Ｖjに一致する少なくとも１つのサブスクリプションを有するそれらのＳＰＳ４８０だけに限定するものである。メッセージのフィルタリングを行うために、各ＩＲ４４５、４４６は重複しないフィルタ集合ｆａ、ｂを持っている。フィルタｆは、範囲（ａ、ｂ）（ここで、ａ、ｂ∈コンテンツ空間Ｖ）と、関連するノードＮ集合によって定められる。
【００５１】
フィルタｆは、ラベル値νがこの範囲、すなわちν∈（ａ、ｂ）にあるメッセージｍのみを通過させる。ｆを通過したメッセージはＮ中のすべてのノードに送出される。図５に示すように、送出ツリー５１０中の各ＩＲは、テーブル５２０に示すフィルタのリストを持っている。ＩＲにおいて、メッセージは、このラベル値νに対する範囲探索を用いてフィルタｆに一致させられた後、複写されてｆに関連する次のホップノード（ＩＲまたはＳＰＳ）に送出される。送出ツリー５１０は、値ν＝２０５に基づいて、種々のＩＲによって行われた動作を表している。各ＩＲでの値ベースの送出ツリーおよびフィルタの構造は、各ＳＰＳから生成された、集約されたサブスクリプションプロファイルに基づいている。全動作がラベルとして付けられた値νを使用するので、ＩＲはメッセージを解析しない。
【００５２】
段階３（図４の要素４６１）は述語ベースの送出であり、それはＳＰＳ４８０で行われる。各ＳＰＳは、ユーザによって送られた完全なサブスクリプションのリストを保持しており、ユーザサブスクリプションを一致させる、述語ベースの送出サーバのホストとして働く。ＳＰＳは、値ベースの送出ツリーから受け取ったメッセージに基づいて、サブスクリプションの複合述語を一致させる。サブスクリプションが一致すると、該メッセージは対応するユーザに送出される。ＳＰＳは、メッセージを受け取る、各メッセージの最終受取人を決定しつつ、メッセージを解析しないようにする楽観的な計数アルゴリズムを使用する。ＳＰＳは、一致に必要と考えられるサブスクリプションの数を最小化する効率的なデータ構造も保持している。
【００５３】
図４に述べた例では、ユーザ４０５は、ボックス４２０に示される２つの属性、ａ1およびａ2を持つメッセージ４１５をパブリッシュする。該メッセージはＰＰＳ１  ４１０で受け取られ、２つの属性ツリーのルート４４２、４４３に、対応するラベル４１１および４１２を付けて送られる。ＩＲ４４５、４４６はこれらのメッセージを、ツリー、該ラベルに一致したＳＰＳサブスクリプションＳ、およびメッセージＩＤを識別するラベル４７５、４７６を追加した後、ＳＰＳ４８０に送出する。ＳＰＳ４８０は、該メッセージを受け取ると、ユーザサブスクリプションとの完全な一致を行い、メッセージ４８６を、関心を持つユーザ（ユーザ２）４８５に送出する。
【００５４】
設計の基本原理
本発明のアーキテクチャは、高速メッセージフィルタリングおよび配布のための、リソースを意識したイベントの分配インフラストラクチュアである。本発明者らは、低レイテンシを持つ高いエンドツーエンドスループットを提供するために、フィルタパイプライン処理の概念を導入した。いかなるパイプラインアーキテクチャも、タスクを、各々が他から独立した、より小さくより高速の複数のコンポーネントに、これらコンポーネントが一緒になって所望のエンドツーエンドサービスを提供するように、分割するように努める。パイプラインは、複数のコンポーネントが異なるオブジェクト上で並行に動作できるので、全タスクを行う単一のコンポーネントよりも高いスループットを達成する。
【００５５】
関心を持つすべてのユーザへのメッセージの選択的な配布を可能にするフィルタリングインフラストラクチュア全体は、最終送信先に到達するためにメッセージが横断する単一のデータ構造として見ることができる。このデータ構造を単一のノードに置くことは該ノードを障害にする。ここで説明しているアーキテクチャはこの問題を認識し、フィルタリングのための分散型データ構造を構築し、異なるノードに異なるデータ構造部分を割り当てる。
【００５６】
本発明は、データ構造のコンポーネントを異なるノードに割り当てながらパイプライン処理の原理を利用する。なお、上述のように、フィルタリングプロセス全体は３つの独立した段階、すなわち属性ベースのフィルタリング、値ベースのフィルタリング、および述語一致に分解される。種々の段階への機能のこの分割は、高速フィルタリングネットワークを構築するタスクを単純化する。次の２つの重要な利点がパイプライン処理フィルタリングから得られる。
【００５７】
高いエンドツーエンドスループット：フィルタリングパイプラインの異なる段階は異なるタスクについて並行して動作する。これら段階の各々は、より短い処理時間でより単純な動作を行う。
【００５８】
個々の段階の最適化：各段階の実行は、より単純で、明確に定められたタスクを行う、独立した段階を用いることによって個別に最適化される。例えば、本構想は、属性ツリー中のＩＲが対応する属性の値だけを用いてメッセージをフィルタリングすることを必要としている。したがって、ラベルベースの送出は、ツリー内部の費用のかかるＸＭＬ解析動作をなくすことができる。
【００５９】
他のレベルの並列処理は、各属性に対して個別の、値ベースの送出ツリーを持たせることによって達成される。それによって、メッセージは複数の属性について同時にフィルタリングされ、フィルタリングプロセスが迅速化される。単一ノードを、メッセージについての多次元属性ベースのフィルタリングに適用させることは、ｄが次元数であるｌｏｇ（ｋ）dとして増加する、大きな時間的複雑さを有することになる。
【００６０】
この構造は、ツリーの各ノードでのフィルタリングおよび属性単位のツリーのトポロジーの最適化をさらに可能にしている。例えば、ストリングタイプの属性に対するフィルタリング機構は、フロートタイプの属性の機構とは異なっている。ストリングタイプの属性を一致させる場合、単語ベースのインデクシングおよび一致のために特に最適化された機構であるＳＩＦＴのような解決策を用いることができる。該ＳＩＦＴシステムについては、Ｔ．Ｙａｎ  ａｎｄ  Ｈ．Ｇａｒｃｉａ−ＭｏｌｉｎａによるＴｈｅ  ＳＩＦＴ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｄｉｓｓｅｍｉｎａｔｉｏｎ  Ｓｙｓｔｅｍ，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ（１９９９）に記載されている。
【００６１】
さらに、各属性は、サブスクリプションプロファイルおよびコンテンツ空間人気分布の点で、異なったパターンを示してもよい。この情報は、この属性に対する最適なフィルタ設計に用いることができる。新しい属性は、モジューラ構造を持たせることによって、新しいフィルタリングツリーを追加するだけでシステムに追加することができる。既存のルーティング構造の再構築は必要ない。
【００６２】
フィルタリングアーキテクチャは本来階層的である。この選択の重要な理由は、実際、ノードがリソース制約されていることにある。本発明者らは、サブスクライバの数が数百万に増加するにつれて、各ＩＲでの状態空間要件が著しく増加することがわかった。同時に、マルチキャスティング送出負荷は、サブスクライバの数またはメッセージパブリケーション速度の増大と共に増大する。ノードに十分な記憶容量がない場合、ノードは必要とされるフィルタを構築することができず、ＳＰＳが関心を持たないメッセージをすべて廃棄してしまう。代わりに、ノードは、ある望まれないトラフィックを下流に送る弱いフィルタ（後述する）を構築できるだけである。他の下流ノードは、この望まれないトラフィックを除去するためにフィルタリングを行わなければならない。同様に、ノードに十分な帯域幅がない場合、該ノードは複数のＳＰＳへの高送出速度を確保できない。したがって、該ノードは、それがある送出義務の負荷を無くすことができる送出ノードを必要とする。暗黙的に、支援ノードは、いずれの場合においてもこの子ノードとして働いており、階層的フィルタリングの概念につながるものである。
【００６３】
値ベースの送出
前のセクションで説明したように、ＰＰＳノードはパブリッシャからメッセージを受け取り、該メッセージを解析してそれが含んでいる属性を決定し、対応する属性ツリーにそれを送る。ＰＰＳノードは、メッセージをツリーＴkに送る前に、固有のメッセージＩＤ  Ｍ、および属性ａkに対応する値Ｖkを含むラベルを割り当てる。ここで、属性ツリーの値ベースの送出動作について詳述する。
【００６４】
各属性ツリーは、（ＳＰＳi：Ｓj）と表される、複数のＳＰＳからのサブスクリプションを含んでいる。ＳＰＳiは、属性にサブスクライブしたＳＰＳの固有のＩＤである。Ｓjは、ＳＰＳiが対応するサブスクリプション範囲に割り当てたサブスクリプションＩＤである。ＳＰＳiは、Ｓjで捺印されたいかなるメッセージも対応するサブスクリプション範囲と一致すると推定する。属性ツリーの目的は、入力メッセージ中の値Ｖk（ラベルの）をサブスクリプションに一致させることである。この一致は偽陽性(false positive)がゼロとなることを保証すべきである、すなわち、メッセージは、サブスクリプション範囲がメッセージの値をカバーする場合、および該場合にのみ、サブスクリプションに一致していると判定されるべきである。
【００６５】
異なったＳＰＳから到着するサブスクリプション範囲の集合が、何人かのユーザが関心を持つコンテンツ空間の一部を規定する。各値は複数のユーザ（異なったＳＰＳ上に広がる）に関心を持たれていてもよいので、この値を該ユーザ集合へのマルチキャストとして考えることは当然である。コンテンツ値の空間は、所与のサブスクリプション範囲の集合から、Ｇiとして表されるマルチキャスト集合の範囲に分割することができる。各マルチキャスト集合の範囲は、この範囲の任意の値がサブスクリプション集合Ｓ中のすべてのサブスクリプションの範囲の共通部分でカバーされるように、サブスクリプションＳ集合にマップされる。図６Ａに示す例では、範囲（１，４）,（６，９）,（１，４）、および（６，９）に対してそれぞれ４つのサブスクリプションがある。コンテンツ空間は、サブスクリプションの固有の端点を用いて、３つのマルチキャスト集合の範囲、すなわち１−４からのＧ1、４−６からのＧ2、および６−９からのＧ3に分割される。それらの集合のうち、Ｇ2に関心を持つサブスクリプションはないが、Ｇ1およびＧ3は各々２つの関心を持つサブスクリプションを持っている。これらのマルチキャスト集合はこのノードでのフィルタを構成する。
【００６６】
上述べたように、属性ツリーの各ノードでの送出構造は、重複しないフィルタ集合から成る。各フィルタは、１つまたは２つ以上のマルチキャスト集合の範囲に関連していてよい。偽陽性がゼロとなることを確保するためには、マルチキャスト集合（いくつかの関心のあるサブスクリプションを持つ）の範囲の数と同数のフィルタが必要であり、各フィルタは１つの固有の集合に関連付けられている。例えば、図６Ａの例では、各々がＧ1とＧ3に対する２つのフィルタが必要である。しかし、この構造は次の２つの問題を生ずる。
【００６７】
状態空間：送出構造の状態空間要件は、サブスクリプション範囲の分布に応じて、記憶容量を越えるほど十分に大きくなる可能性がある。状態空間の増加の一例が図６Ｂに示されており、図６Ｂは、図６Ａの４つのサブスクリプションの分布とは異なるサブスクリプション分布を持つ４つのサブスクリプションを示している。この異なる分布はＧ1からＧ6の６つの集合を生じ、６つのフィルタが必要になる。全体の状態空間要件がすべての集合の集合メンバーの累積数と考えられる場合、各ユニットは１バイトである、図６Ａの４ユニットと比較して、図６Ｂには１０ユニットが存在する。実際上、この問題の本当の重要性は単純な事例（値が１から１００，０００にあるコンテンツ空間上の１００，０００個のサブスクリプションを考える）の分析から生じる。サブスクリプション１は（１，１００，０００）の範囲についてであり、サブスクリプション２は（２，１００，０００）の範囲についてであり、以下同様に、サブスクリプションｉは（ｉ，１００，０００）の範囲についてである。１から１００，０００までのすべての値は、サブスクリプションシーケンスについての異なる複数の端点を構成する。したがって、集合Ｇiがｉに関連付けられたメンバーを持つ１００，０００個の異なる集合が存在することになる。この例の状態空間は、
【００６８】
【数１】
2007234014.tif 000003
【００６９】
個のエントリでなる。簡単な４バイト（整数）がサブスクリプションＩＤ（集合メンバー）を格納すると仮定しても、これはシステムにおいて２０ＧＢのメモリ容量を必要とする。さらに、状態空間は、上記の例を用いると、ｎ個のサブスクリプションに対してｎ2のように爆発的に増加する。
【００７０】
送出負荷：サブスクリプション分布によって引き起こされる他の問題は送出負荷の爆発的増加の問題である。図６Ａに示した例において、値ｉを持つメッセージの到着率が毎秒ｉメッセージであると仮定する。すると、すべてのサブスクリプションへの図６Ａのノードでの合計送出負荷は、毎秒（１＋２＋３＋４）のメッセージによってサブスクリプションＩＤ｛１，３｝の各々に与えられ、毎秒（６＋７＋８＋９）のメッセージによってサブスクリプションＩＤ｛２，４｝の各々に与えられ、結果として毎秒８０個のメッセージが与えられることになる。しかし、図６Ｂに示したサブスクリプション分布では、全負荷は毎秒７２個のメッセージにすぎない。したがって、状態空間要件は図６Ｂの例の方がより高くなるが、送出負荷は図６Ａの例の方がより高くなる。送出負荷の爆発的増加の考えられる重要性をよりよく理解するために、上記の例において１つの値当たり毎秒１バイトの入力メッセージ速度があれば、この結果得られる出力速度は５ＧＢ／ｓになる。
【００７１】
本発明の１つの目的は、送出空間と送出負荷の両方を複数のノードの間に分散させることによって、階層的フィルタリング構造を構築することである。該構築は、コンテンツ空間上のメッセージ値人気分布およびサブスクリプション範囲分布に適応可能である。
【００７２】
異なった値の人気分布を得るために、各ノードは、複数の異なった値に対する総到着統計量をヒストグラムの形で保持している。該ヒストグラムは、コンテンツ空間全体上の所与の単位間隔での値分布を生成する。該ヒストグラムは、メッセージが受け取られるごとにスライディングウィンドウ平均を用いて更新される。該ヒストグラムから、値空間内の任意の範囲ｒについて、この範囲ｒに複数の値を持つトラフィックｐ（ｒ）のごく一部を容易に計算することができる。範囲ｒの値を持つ全トラフィックは、λをメッセージ到着率の合計として、λｐ（ｒ）であることに留意されたい。
【００７３】
空間および負荷の分割
属性ツリーのルートノードが空間要件および送出負荷要件を処理できない場合、フィルタリング・送出タスクは複数の子ノードの間に分散させられる。本発明者らは、マルチキャスト集合の範囲の数および関連する送出負荷は共に、サブスクリプション数の増加関数であることに気づいた。したがって、サブスクリプションを複数の子ノードの間に分割することによって、各ノードの空間制約および送出制約を共に満たすことができる。したがって、各ノードは、各マルチキャスト集合の範囲に対して固有のフィルタを持たせることによって、すべてのサブスクリプションのサブセットにサービスすることができ、それによって、複数のＳＰＳへの、偽陽性がゼロの配布を確実にすることができる。
【００７４】
各ノードの利用可能な空間および送出帯域幅がリソースプール内の各ノードの利用可能な空間および送出帯域幅が与えられていると仮定する。現在の状態では、すべてのサブスクリプション集合が、すべてがルートの子ノードであるｋ個のノードの間に分割されると仮定する。ノードｉ内のサブスクリプション集合をＳiと表す。新しいサブスクリプション要求Ｓがルートにおいて受け取られると、次のサブスクリプション分割プロセスが用いられる。
【００７５】
サブスクリプションの分割と移動：最大送出容量ｃ（Ｓi）を持つノードｉを考え、この容量ｌ（Ｓi）が、現在、メッセージを下流のノードに送出するのに使用されていると仮定する。ｌ（Ｓi）はノードｉの送出負荷である。サブスクリプションＳがノードｉに割り当てられると、この送出負荷の増加はδlS＝ｐ（ｒ）λとなる、ここで、ｒはＳ中でサブスクライブされた値の範囲である。このことは、ユーザサブスクリプションが固有のＳＰＳにおいて集約されるので、各サブスクリプションが該ＳＰＳを識別するときに、言える。ｌ（Ｓi）＋δlS≦ｃ（Ｓi）を満足する、ノードＮの利用可能な集合を容易に見つけることができる。ｇを、サブスクリプション集合Ｓjを持つ、Ｎ中のノードｊのマルチキャスト集合の総数としよう。Ｓがノードｊに割り当てられると、全空間要件は、最大δgS＝ｇ’＋２だけ増加する、ここで、ｇ’は、Ｓの範囲のマルチキャスト集合の範囲の総数である。空間要件の増加を最小にするために、Ｓは、δgS（ｊ）が最小となるノードｊに割り当てられる。しかし、空間要件がＮ中のいずれのノードによっても満たされない場合には、サブスクリプションが割り当てられる新しいノードが追加される。この解決策は負荷の平衡をもたらすものではなく、この代わりに、該解決策は、ノードの容量制約を満たしながらノード数を最小にしようとするものであることに留意されたい。
【００７６】
階層的フィルタリング
ｋ個のリーフノードの各々でフィルタリングを行なわせるために、ルートは、各メッセージをこれらのノードのすべてに送出することができる。しかし、簡単な送出は次の問題すなわち、ａ）ルートでの合計の出力メッセージ送出負荷λkが高くなる、ｂ）各リーフノードによって処理されたメッセージの数が多くなる（受信メッセージの数は、リーフノードによって処理されるサブスクリプションとは無関係である）、ｃ）全体のネットワークトラフィックが増加する、を生じさせることになる。したがって、ルートが、空間制約を満たす弱い形態であるが、フィルタリングプロセスに投資することは価値がある。弱いフィルタリングを明確にするために、「リーク」がここでは次のように、すなわち、Ｓによって一致させられないサブスクリプション集合Ｓを持つノードに渡され、したがって該ノードがそれを受信すべきでなかった余分なトラフィックの量として定義される。
【００７７】
リークは、フィルタ範囲と、関連するマルチキャスト集合範囲との間に一部重複がある場合に発生する。
【００７８】
【数２】
2007234014.tif 000004
【００７９】
を、ｆによってカバーされた一連のマルチキャスト集合範囲として定義する。リーフノードｉのサブスクリプションにとって重要である
【００８０】
【数３】
2007234014.tif 000005
【００８１】
の集合範囲のサブセットを
【００８２】
【数４】
2007234014.tif 000006
【００８３】
としよう。マルチキャスト集合範囲
【００８４】
【数５】
2007234014.tif 000007
【００８５】
に向けられた、ｆによって渡されるいかなるメッセージも、ノードｉのトラフィックリークに寄与することになる。
【００８６】
定義：フィルタｆのリーク（Ｌfと表わす）は、
【００８７】
【数６】
2007234014.tif 000008
【００８８】
と与えられる、ｆによって引き起こされる全トラフィックリークと定義される。
【００８９】
ここで、
【００９０】
【数７】
2007234014.tif 000009
【００９１】
は、分割範囲
【００９２】
【数８】
2007234014.tif 000010
【００９３】
内に値を持つトラフィックのごく一部であり、ヒストグラムから得られる
【００９４】
【数９】
2007234014.tif 000011
【００９５】
に値を持つトラヒックの一部ではない。ゼロでないリークＬfを持つフィルタｆを弱いフィルタと呼ぶ。
【００９６】
図７に示したマッピング例は、所与のサブスクリプション集合７１５用のフィルタ７１０からのリークを示している。この例においては、各単位値の間隔（ｉ：ｉ＋１）が、１メッセージ／秒のトラフィックを持っていると仮定している。ｆ1からのリークを見つけるために、フィルタツリー７２０におけるリーフノード１および２を考える。ノード１は、範囲（１−４）および（３−６）をそれぞれ持つサブスクリプション１と２をホストすると仮定する。さらに、ノード２は、範囲（３−５）および（６−９）をそれぞれ持つサブスクリプション３と４をホストすると仮定する。図７に示すように、それらの範囲の分割によって５つのマルチキャスト集合Ｇ1，．．．，Ｇ5が生じる。
【００９７】
【数１０】
2007234014.tif 000012
【００９８】
が得られる。したがって、
【００９９】
【数１１】
2007234014.tif 000013
【０１００】
なので、ノード１の、ｆからのリークは０であり、
【０１０１】
【数１２】
2007234014.tif 000014
【０１０２】
なので、ノード２の、ｆからのノード２のリークは２メッセージ／秒である。
【０１０３】
フィルタｆ2に対して同じことを計算すると、フィルタｆ1およびｆ2の両方からのリークの合計として、７メッセージ／秒が得られる。注目すべき興味ある点は、フィルタがない（１つのフィルタを持っていることと等価）と、リークの合計は同様に７メッセージ／秒となることである。しかし、フィルタｆ3およびｆ4があると、リークの合計は３メッセージ／秒に減少する。適切なフィルタを形成することが、ルーにおいてフィルタリングの利点を利用するためには、重要であると結論付けることができる。次に、フィルタ構築ための最適な多項式時間アルゴリズムを述べる。
【０１０４】
最適なフィルタ構築
リーフノードの１つにおけるサブスクリプション集合およびそれらの位置が所与のものとすると、本方法は、ｋ個の重複しないフィルタを、
１）それらがサブスクリプション空間にまたがっている、すなわち、任意のサブスクリプションがサブスクライブした任意の値は、フィルタの１つを通過しなければならない、
２）全フィルタ集合Ｆの合成リークが最小化、すなわち、
【０１０５】
【数１３】
2007234014.tif 000015
【０１０６】
が最小化される
ように構築する。
【０１０７】
ここで、上記問題に対するダイナミックプログラミング法を述べる。該方法は（ｋ−１）回反復して実行される、ここで、ｋは構築されべきるフィルタの数である。ｉ番目の反復中に、該方法は、（ｉ＋１）個のフィルタだけ（Ｌ（Ｆi+1）で表される）が許可された場合に、最良のフィルタ集合を算出する。これは、（ｉ−１）番目の反復中に生成されたフィルタ集合を用いて、目的に適うように新しいフィルタを追加することによって行われる。フィルタ集合Ｆiのリークの合計はＬ（Ｆi）で表される。
【０１０８】
上述した、フィルタのリークの重要な特性は、それが自己完結的(self-contained)であり、かつ独立しているということである、すなわち、フィルタｆによるリーク合計は、それに重なるサブスクリプションの一部だけを用いて算出され、リークの値は、残りのフィルタがどのように構成されているかにかかわらず同じままである（フィルタの範囲は重複していないことを思い出されたい）。
【０１０９】
ν1，．．，νnが、マルチキャスト集合の範囲Ｇの開始または終了のいずれかに対応する、値空間内の異なるエッジポイントを昇順に表すものとする。ダイナミックプログラミングの簿記能力を利用するために、いくつかの一部の情報が各反復の後に格納される。この情報は、エッジポイントのサブ集合Ｖi上のフィルタ集合の形をしており、ここで、Ｖk＝｛νk．．．νn｝である。Ｆij（Ｖk）は、ｉ個のフィルタがある場合に、第１のフィルタスパンνk，．．．，νk+jおよび残りの（ｉ−１）個のフィルタが範囲νk+j+1，．．．，νnに広がるようにＶk上で定められたフィルタ集合を示す。ｎ−ｊ−ｋ＞ｉ−１の場合には、（ｉ−１）個の重複しないフィルタをこの範囲に割り当てる十分な値がないので、集合Ｆijは無意味となることに留意されたい。リーク合計Ｌ（Ｆi*（Ｖk））が最小化されるように、Ｆi*（Ｖk）を、Ｖk上のｉ個のフィルタからなる最適なフィルタ集合と定義しよう。
【０１１０】
本方法の基本ステップは、２つのフィルタがあると仮定してフィルタ集合を算出することを含む。全範囲をカバーするたった１つのフィルタで十分である唯一のケースは、たった１つのサブスクリプションが存在する場合である。２つまたは３以上の異なるサブスクリプションが存在する場合、２つまたは３以上のフィルタの方が単一のフィルタよりも全リークが低くなることは明らかである。２つのフィルタがあると仮定してフィルタ集合を算出するために、Ｆ21（Ｖk）からＦ2n（Ｖk）までのすべての集合、および対応するリークＬ（Ｆ2j（Ｖk））が算出される。Ｆ2*（Ｖk）が、ｍｉｎj（Ｌ（Ｆ2j（Ｖk）））として得られる。
【０１１１】
ｉ個のフィルタを持つフィルタ集合が見つかった次の反復ｉは、ｉ個のフィルタを持つすべての考えあられるフィルタ割り当てを組み合わせて検査する代わりに、集合Ｆi-1*（Ｖ１）．．．Ｆi-1*（Ｖｎ）を使用する。上に述べたように、これは、本フィルタリークが他のフィルタリークに対して独立しているため可能である。したがって、最良のフィルタ集合Ｆi*（Ｖk）を算出するために、既に算出されているフィルタ集合Ｆi-1*（Ｖj）が、前の反復のすべてのｊに対して使用される。リークの合計Ｆj+1i-1は、どのように（またはどれだけの）フィルタが範囲１からｊにわたり分散するかにかかわらず変わらず、かつＦi-1*（Ｖk）のリークはこの範囲で最小となるので、最適なＦi*はｆ1、j∪Ｆi-1*（Ｖj+1）によって与えられることになる。ここで、ｆ1、jはフィルタ域ν1：νjである。
【０１１２】
この演算は、最適なリーク合計値がｋ個のフィルタに与えられるフィルタ集合Ｆ1kが得られるまで継続される。
【０１１３】
多段階フィルタリング
上記の解決策はリークをルートにおいて最小化するが、空間制約を受けるリークを完全に除去するものではない。複数の層をルートとリーフノード間に追加してメッセージを連続的にフィルタリングし、リークの発生をゼロにすることができる。例えば、図８のフィルタツリー８１０は、ルートノード８１５からノード８２０へのリークがある。追加のノード８５５をツリー８５０に追加されており、リークを除去している。
【０１１４】
このような多段構造においては、イベント空間全体は分割され、各分割空間はこの段の所与のノードに割り当てられる。該分割は、各分割空間がマルチキャスト集合の範囲と等しい数を持つように行われる。分割空間の数は前段からのリーク量によって決定される。本発明者らは、大半のシナリオの下では、リークを処理するのに単一段のフレームワークで十分であることがわかった。
【０１１５】
ＳＰＳでの述語ベースの送出
各ＳＰＳは種々のユーザサブスクリプションを含んでおり、それらのサブスクリプションを代表して適切な属性ツリーにサブスクライブする責務を有している。ＳＰＳは、入力メッセージに基づいて述語一致を行い、該メッセージを、一致サブスクリプションを持ったユーザに送出する。しかしながら、単一のメッセージの内容をすべてのサブスクリプションと一致させることは非能率的である。さらに、各エンドユーザサブスクリプション述語は多次元であり、一方該受信メッセージは１次元に対応しているだけである。楽観的な計数アルゴリズムを以下に示す。該アルゴリズムは、高速のサブスクリプション一致を達成する効率的なデータ構造に基づいた述語評価機構である。
【０１１６】
楽観的な計数アルゴリズム
ｎ個の属性上で定義された選択述語を持つ単一のユーザサブスクリプションｓを考えてみる。ＳＰＳが、ユーザサブスクリプションのためにｎ個の属性ツリーすべてにサブスクライブするものとする。ＳＰＳが各属性ツリーに対応するメッセージのｎ個のコピーを受け取った場合、それはユーザサブスクリプションが真と評価されたことを暗に示している。ｎ個よりも少ないコピーはそうでないことを意味しているであろう。したがって、単純な計数によってサブスクリプションが一致するかどうかを立証することができる。本質的に、本アルゴリズムは、ＳＰＳに達するメッセージが異なった属性ツリーについて既にフィルタリングされていることを認識し、ローカルのさらなる一致を回避しようとする。この単純な観察が、楽観的な計数アルゴリズムの基礎をなすものである。
【０１１７】
本アルゴリズムは、該メッセージの全てのコピーが、それらがサブスクリプションと一致する場合に、はっきりと到着すると仮定しているので、楽観的であると考えられる。該アルゴリズムはさらに、メッセージのすべてのコピーが適切に有限の時間で着くと仮定している。
【０１１８】
上記のアルゴリズムを実際に使用するためには、取り組むべきいくつかの問題の問題がある。すなわち、１）所与の属性ツリーのＳＰＳの各サブスクリプションＳは、この属性のいくつかのユーザサブスクリプションｓの結合である。したがって、ＳＰＳは、メッセージｍに対して何らかの行動を取るために、それがどの属性ツリーから到着し、誰がこのユーザサブスクリプションであるかを、メッセージの内容を解析することなくわからなければならない。２）メッセージｍは、複数の異なった属性ツリーから非同期に来ることができる。３）メッセージは任意に遅延でき、この結果ＳＰＳは、ある期間複数のサブスクリプションの計数値を保持していなければならない。４）１つのサブスクリプションの複数の属性にサブスクライブすることは、受信したメッセージの複数のコピーのために、余分なオーバヘッドを発生することになり、したがってＳＰＳがサブスクライブすべき属性の数を削減する機構が必要となる。
【０１１９】
ＳＰＳにおける送出構造
ここで、図９に示した、ＳＰＳでの送出機構９００を、所与のメッセージについて取られた動作および使用されるそれに対応するデータ構造に関して説明する。メッセージ９１０がＳＰＳに到着すると、ＳＰＳは属性ツリーＩＤ  ＴおよびサブスクリプションＩＤ  Ｓを識別する。この情報は、属性ツリーの最後のホップノードからのラベルとしてメッセージ９１０に追加される。
【０１２０】
より詳細には、ツリーＩＤ  Ｔi９１４から、対応するユーザサブスクリプションマッピングテーブル９２０がテーブルポインタ９１５によってアクセスされる。各コラムが、属性ツリーにサブスクライブするためにＳＰＳによって使用されるサブスクリプションＩＤ  Ｓiを含んでいる、各属性ツリーに対して１つのテーブル９２０がある。このテーブル９２０を用いて、メッセージ９１０中のサブスクリプションＩＤ  Ｓi（行９２１）を、構成要素のユーザサブスクリプションＩＤ  ｓ（行９２２）のリストにマップすることができる。したがって、２つのルックアップ動作が、メッセージ９１０に関心を持つユーザサブスクリプションを含むユーザサブスクリプションリストを発生する。図９の例において、それらのユーザサブスクリプションはｕ1とｕ2である。
【０１２１】
ＳＰＳは、ユーザサブスクリプションｕjの固有のＩＤ９４５で索引を付けられたサブスクリプション一致テーブル９４０も保持している。各サブスクリプションに対して、属性計数フィールド９４６は、ＳＰＳが対応するサブスクリプションを持つサブスクリプションの属性数を含んでいる。完全一致フラグ９４７は、属性の計数がサブスクリプションの属性の実際の数を表すかどうかを示している。このフィールドの１の値は、ＳＰＳが、必要な数のメッセージコピーを得ることが完全な一致を意味するであろうことを示すこのサブスクリプションのすべての属性ツリーにサブスクライブしたことを示し、一方、値が０の場合には、それは部分的一致のみを示しているであろう。テーブル９４０は、ペンディング(pending)のメッセージＩＤのハッシュキュー９４８とそれらの計数値とを含んでいる。ハッシュキュー９４８は、いくつかの（ただしすべてではない）属性について一致したすべてのメッセージのリストを含んでいる。これらのメッセージは、０より大きいが属性の計数値よりも小さい計数値を持たせることによって示される。受け取ったメッセージのコピーの数を単に計数するだけでは、ユーザサブスクリプションとの一致には不十分であり、特定の複数のツリーから到着するメッセージだけが、特定のサブスクリプションの計数値をインクリメントすべきである。
【０１２２】
最後に、ＳＰＳは、サブスクリプションと一致するメッセージに必要な計数値を持つすべてのユーザサブスクリプションの完成したテーブルを保持している。各サブスクリプションと共に、現在部分的に一致しているメッセージＩＤのリストが、受け取ったメッセージのコピーの数の計数値と共に保持される。
【０１２３】
ユーザサブスクリプション一致テーブル９４０において、メッセージ９１０について、ｕ1、ｕ2に対するペンディングメッセージのリストが記載されている。それは、メッセージの固有のメッセージＩＤ  Ｍ1を用いて、該メッセージが既にペンディングになっているかどうかをチェックする。それは、ｕｉおよびｕ2の両方のＭ1の計数値をインクリメントする。ｕ1に対するＭ1の計数値がここでは３になるので、完全一致フラグ９４７が１のとき、それは完全な一致になり、該メッセージはｕ1に直接送られる。また、ｕ2のＭ1の計数値は、必要な属性の計数値９４６である５になり、これはＭ1がｕ2と一致することを暗に示している。しかし、ｕ2の完全一致フラグは０であるので、これは部分的一致であり、このことはｕ2に５つより多い属性が存在することを示している。この場合、該メッセージは次に、Ｍ1の内容に完全に一致させられるメッセージキャッシュ（次に説明する）に送られる。
【０１２４】
メッセージキャッシュおよびタイマー管理
ＳＰＳは、各到着毎にメッセージの複数のコピーを受け取ることができ、多分いくつかの部分的一致が生じる結果になるであろう。特別の機構がなくても、これは、完全一致を検査するためにメッセージを毎回、解析することを必要とするであろう。解析は高価な動作なので、このオーバヘッドは、メッセージキャッシュを用いることによっていくぶん緩和される。新しいメッセージが到着するたびに、該メッセージはメッセージキャッシュに追加される。該メッセージのいかなる次のコピーも計数アルゴリズムにのみ用いられる。さらに、メッセージはゆったりと、すなわち最初の部分的一致が発生する時だけ解析される。メッセージと一致したすべてのサブスクリプションのが完全にサブスクライブされると（すなわち、完全一致フラグが、この関心のあるすべてのサブスクリプションに対して１である）、メッセージは全く解析されないであろう。
【０１２５】
メッセージキャッシュの実現可能な実施にはタイマーを使用する必要がある。本発明のシステムではタイマーの２つの使用法がある。サブスクリプションのペンディングキュー中のメッセージのタイムアウトは、メッセージが一致しなかったこと、そしてエントリを廃棄できることを示している。メッセージキャッシュのタイムアウトは、該メッセージの重複コピーがもはや期待されず、該メッセージをキャッシュから除くことができることを示している。両タイマーの終了期間は、異なった属性ツリー間の最大の起こり得る遅延によって決まる。実際のシナリオでは、この遅延は小さいであろう。
【０１２６】
本発明の一実施形態において、ＳＰＳは、新しいメッセージを得るたびに、１つまたは２つ以上のタイマーを始動させる。しかし、この場合、アクティブなタイマーの数を実現不可能な数に素早く増加させてもよい。好ましい実施形態において、このオーバヘッドは、終了イベントを複数のバケットにグループ化し、タイマー終了を用いて対応するバケット中のすべてのイベントを処理することによって制御される。
【０１２７】
選択的サブスクリプション
ＳＰＳが各サブスクリプションのすべての属性にサブスクライブするという要件によって引き起こされる問題を緩和するために、ここに開示したアーキテクチャは、ＳＰＳが各サブスクリプションの属性のサブ集合のみにサブスクライブすることを可能にしている。この選択の論理的根拠は、ある属性および値が他と比較して非常に一般的であるということ（特に傾斜(skewed)分布において）である。したがって、人気のある属性にサブスクライブすることによって、ＳＰＳがフィルタリングの観点で多くを得ることはない。例えば、ユーザが特定の属性に対するコンテンツ空間全体にサブスクライブすると、この属性のすべてのメッセージはサブスクリプションと一致するだろう。この場合、この属性はフィルタリングプロセスを全く支援していない。このような場合、ＳＰＳは余分な属性に、それがフィルタリングされたトラフィックに関して著しい利益を得る場合にのみ、サブスクライブすることを決定する。具体的には、サブスクリプション範囲の選択能力は、ＳＰＳがそれにサブスクライブするかどうかを決定する。
【０１２８】
選択能力は、ＳＰＳがサブスクライブする属性の数を削減することによって、外部からのトラフィックを減らすが、それは、サブスクリプションと完全に一致するメッセージでさえ計数だけでは識別できなくなるという新たな問題を招くことになる。その理由は、該計数が、サブスクリプションが、サブスクライブされたすべての属性において一致することのみを保証できるからである。残りの属性が、メッセージの内容を見ずに一致するかどうかを判定する方法はない。したがって、該メッセージは、今やＳＰＳにおいて解析され一致しなければならない。
【０１２９】
上記の緩やかなアルゴリズムではもはや正確な一致が可能ではないので、その有用性を疑うことは当然である。この緩やかなアルゴリズムがそれでもなお有する重要な利点は、一致しないサブスクリプションを識別することである。サブスクリプションのｋ個の属性がサブスクライブされ、ＳＰＳが、対応するツリーからメッセージの最大で（ｋ−１）個のコピーを受け取るとすると、該メッセージは、その残りの属性の値にかかわらずサブスクリプションと一致しない。このことは、メッセージに一致されられなければならなサブスクリプションの数を劇的に減少させることになる。
【０１３０】
サブスクリプション範囲の選択
ここで説明しているアーキテクチャの選択的なサブスクリプション機構は、各属性がサブスクライブする範囲を決定する技術を必要とする。以下に、イベント到着統計量と、一致およびカウンタインクリメント動作のコストを用いて、この問題を解決する簡単な方策を示す。
【０１３１】
ＳＰＳは２つの独立したユニット、すなわち１）各メッセージに対する一致サブスクリプションを識別する一致ユニットと、２）該メッセージをすべての一致ユーザに送出する送出ユニット、を有している。送出ユニットが送出負荷を処理できない場合、該送出負荷は全く所望のメッセージから成っているので、他のＳＰＳにいくつかのサブスクリプションを移動させることが必要であることは明らかである。したがって、この議論の場合、一致ユニットが考慮される。
【０１３２】
直観的に、余分なサブスクリプションを追加することは、それがシステムのスループットを向上させる場合にのみ有用である。したがって、単位時間当たりＭ個の異なるメッセージがＳＰＳに到着すると、ＳＰＳは、それが単位時間当たりＭ個のメッセージより少ないメッセージと一致する場合に障害になる。ここで、メッセージと一致するとは、該メッセージが、すべての一致したサブスクリプションと共に送出ユニットに送られることを指す。選択的なサブスクリプションを用いると、一致ユニットのスループットを向上させることができる。
【０１３３】
ｎ個の属性ａ1，ａ2，．．．，ａnがあると仮定する。属性ａjの値域ｒiに対する到着率をλijとする。サブスクリプションをメッセージに完全に一致させるために要する平均時間をｔf、およびメッセージカウンタをインクリメントするために要する時間をｔcとする。完全一致は、メッセージを解析することと、その全ての属性をサブスクリプション内のすべての属性に一致させることを含んでいるので、ｔfはｔcよりはるかに高いと予想される。ＳＰＳによってメッセージを処理する予想時間Ｔは、ｎ1×ｔf＋ｎ2×ｔcによって与えられる。ここで、ｎ1はＳＰＳによる完全一致の数、ｎ2はＳＰＳによってインクリメントされたカウンタの数である。Ｔが１／Ｍ未満であると、ＳＰＳは障害にはならない。そうでない場合（Ｔが１／Ｍ以上）には、いくつかのサブスクリプションの追加の次元にサブスクライブすることによってＴを減少させる必要がある。
【０１３４】
任意のサブスクリプションｓは最初その属性ａsの１つ（そのサブスクリプション範囲Ｒ（ａs）にわたって最小の到着率を持つ属性）だけにサブスクライブされる。したがって、どんなメッセージ一致Ｒ（ａs）も、ｓのカウンタをインクリメントすることになり、ｓが複数の属性について範囲制約を持っていれば、それは完全に一致しなければならないだろう。その場合、ｓはｎ1およびｎ2の両方に寄与する。今や、ｓは、追加の属性が計数領域で既に一致した時にだけ完全に一致する必要があるので、予想される完全一致コストを、ｓの追加の属性ａ’sにサブスクライブすることによって減少させる。事実、ａ’にサブスクライブすることによって、ｓのすべての属性がサブスクライブされていると、それは完全には一致させる必要はない。
【０１３５】
しかしながら、追加のサブスクリプションは入力メッセージ速度を向上させる。この追加のサブスクリプションは、完全に一致しなければならないメッセージの数を、それらのメッセージが既存のサブスクリプションから既に到着しているので、増加させることはない。したがって、完全一致のコストは追加のサブスクリプションによっては決して増大しない。しかしながら、追加のサブスクリプションは、いくつかのカウンタ自体をインクリメントすることがある余分なメッセージを生じさせることになるので、カウンタインクリメントの時間は増加する。したがって、余分な属性にサブスクライブさる時、一致ユニットのスループットが減少し始める最適な時点が存在する。追加の属性にサブスクライブする際のＳＰＳの判断は、インクリメントアルゴリズムが到達できる最適なレベルで動作することを目的としている。すなわちＳＰＳは、それが最小の余分なトラフィックを持つ範囲にサブスクライブする場合、有効なスループットを算出する。有効なスループットが増加すると、ＳＰＳはサブスクライブして次の候補となる範囲をチェックし、そうでなければ、停止する。下記の評価の章では、この簡単な方策が、異なった状況の下で一致ユニットのスループットを著しく向上させることができることが示されている。
【０１３６】
評価
ここで説明しているアーキテクチャの有効性は、試作品の実施に関するいくつかの実験、およびいくつかのシミュレーションを行うことによって実証された。本発明者らは、値ｉが確率ｉ-α（値の数によって正規化される）（ここで、αはｚｉｐｆパラメータ）で発生するように、ｚｉｐｆ分布を用いてサブスクリプションとメッセージの両方を発生させたる。サブスクリプション範囲を発生させるために、１つの数がサブスクリプション範囲の下限としてｚｉｐｆ分布から取り出される。値空間のより低い値がｚｉｐｆ発生ではより優勢であるので、それらの値は、分布で人気のある値を分散させるようにランダムな置換ベクトルを用いて並べ換えられる。サブスクリプションの上端は、指定された平均値（それは実験中に変わる）を持つ均一な幅を用いて発生させられる。サブスクリプションがその範囲内のすべての値に関心を示すので、この手法によって、より多くのサブスクリプションをより人気のある値のまわりに集中させることが可能になる。さらに、パラメータとしてサブスクリプション幅を用いることによって、複数のサブスクリプション間の重複の制御が可能になり、より広い試験領域が生じる。
【０１３７】
評価のために、次の定義を述べる。
【０１３８】
定義：ノードのメッセージ当たりの処理時間は、ノードがメッセージと完全に一致する全てのサブスクリプションを識別するのに要する平均時間である。
【０１３９】
定義：ノードのスループット比は、ノードが経験するメッセージ間平均到着時間と該ノードのメッセージ当たりの処理時間との比である。１未満のスループット比が、ノードが入力メッセージストリームを切れ目なくフィルタし、送出できるために不可欠である。
【０１４０】
実施
本発明者らは、（上記した）ＩＲでの最適なフィルタ、およびＳＰＳでの楽観的な計数アルゴリズムを用いてシステム試作品を製作した。複数のノードのクラスタについて得られたいくつかの性能結果を以下に示す。重要な性能メトリック（metric）は、ＳＰＳの一致ユニットの有効スループットである。この興味ある性能メトリックは２つの理由、すなわち、１）一致は集約されたサブスクリプションの単一の属性上にあるので、ＩＲでのフィルタリングコストがＳＰＳと比較してより低いこと、２）ＳＰＳの実際のスループットが、サブスクリプションおよびメッセージ到着率に依存する、で選ばれた。したがって、本システムの能力は、送出スループットではなく一致スループットによることがよりよく示されている。
【０１４１】
次の結果は、１００Ｍｂｐｓのイーサネット（登録商標）ネットワークに接続されている、１ＧＢのＲＡＭを持つ１３個のＰｅｎｔｉｕｍ（登録商標）−４  ２．８Ｇｈｚマシンの集合上で得られた。１つのマシンがパブリッシャとＰＰＳの両方として働き、したがってメッセージを生成し、値ベースのラベルを添付し、該メッセージを適切なＩＲノードに送出する。１つのサブスクライバノードが、１００，０００個のサブスクリプションを発生して、それらを単一のＳＰＳノードに送る。ＳＰＳはそのローカルのテーブルを計算し、すべての属性上の適正範囲にサブスクライブして、計数アルゴリズムの完全一致バージョンを実現する。
【０１４２】
パブリッシャは毎秒１０，０００個のメッセージを発生し、各メッセージは５１２バイトのペイロードを有する。ペイロードは、属性数が変化するＸＭＬメッセージを含んでおり、該メッセージの残りはパディングデータである。属性の数およびトラフィックパターンは、システムの性能を試験するために変えられる。
【０１４３】
第１の実験が、サブスクリプションおよびパブリケーションのストレスの多い作業量を発生する。この場合、サブスクリプションおよびパブリケーションは、同じ値αを持つｚｉｐｆ分布を用いて発生させられた。さらに、同じ置換ベクトルが、サブスクリプションの最多数が最も人気のあるイベントに対してであるという場合を発生するために、パブリッシャ端とサブスクライバ端の両方において用いられた。これによって、非常に多くのサブスクリプションと一致する、最大の到着率を持つ範囲からのメッセージが得られ、この結果多くのカウンタインクリメントが生じることになる。したがって、このシナリオにおける一致ユニットの性能は、対応するαに対して最悪の状況を形成すると予想される。図１０のプロットは、ＳＰＳが、属性の変化する数およびαの３つの異なる値に対して、システムからのメッセージのすべてのコピーを一致、送出するのに要する実際の時間を示している。次のような観察をなすことができる。第１に、ＳＰＳは、最良の状態では、メッセージ当たりたった１６マイクロコセカンドの一致時間しか要しない。したがって、ＳＰＳは、パブリッシャによって発生させられた、毎秒１０，０００個のメッセージを処理できるだけでなく、処理機能を毎秒６０，０００メッセージ（ネットワークが許す）に高める能力を持っている。第２に、属性数の増加は一致時間を増加させる。この増加は、到着する各メッセージのより多くの数のコピーによって引き起こされ、したがってこのメッセージによってカウンタインクリメントの数が増加する。第３に、αの増加は一致時間が超線形に増加することになる。上述したように、これは、パブリッシャの間およびサブスクライバの間の両方において人気のある、同じ値を持つことを選択することによって引き起こされる。
【０１４４】
第２の実験は、より一般的条件においてシステムを試験する。この実験では、サブスクライバおよびパブリッシャに対する種々の値の人気の異なる度合いが存在している。パブリッシャに対するαの値は０．５に保たれ、サブスクライバに対するαの値は、０．３から０．７まで変化させられる。人気のある値の人為的分配が、特定の値での相対的な関心度のみが変わる（しかし、すべての値の中の値の人気インデックスは変化しない）ように、同一の置換ベクトルによって再び導入される。この実験の結果は図１１に示されている。この結果は、メッセージ処理時間が、値における関心度を変化させることによって、著しく減少したことを示している。これは、人気のある値を有するメッセージがより関心が少ないサブスクリプションを持つことがあり、その結果カウンタインクリメントの数がより小さくなるので、言えることである。これは、普通の状態においては、本発明のシステムが非常にうまく動作する可能性があることを示している。
【０１４５】
パイプライン処理結果の重要な尺度は、障害ノードがその入力トラフィックに関して提供できるスループットの量である。このシステムに対する本発明者らの経験は、障害ノードが常にＳＰＳとなることを暗示している。次の実験は、ＳＰＳが達成することができるスループットを、異なった条件についてのそのスループット比を評価することによって、定量化することを目的としている。同じ値をさらに人気のあるようにするサブスクリプションおよびメッセージを発生させるために、αが同じ置換ベクトルでパブリッシャおよびサブスクライバの両方に対して０．５に設定される。図１２のプロットは、システムにおける属性のいくつかの数、および増大するメッセージ到着率に対するＳＰＳのスループット比を示している。前に述べたように、１未満のスループット比が、ノードがその入力トラフィックを切れ目なく処理するために必須である。図１２は、システムが、１０個の属性を支援するが、１００，０００個のサブスクリプションに作用しながら毎秒約４，０００個のメッセージを処理できることを示している。図１３は、サブスクリプション分布が０．５のαを持つパブリケーション分布と同等である場合のスループット比を示している。この場合、１つのＳＰＳは、１００，０００個のサブスクリプションを持つ１０個の属性を支援しながら、毎秒約５５００個のメッセージを支援できるということがわかる。これらの結果は、高速メッセージストリームを支援するに際しての本発明の有効を強く立証している。
【０１４６】
最後に、本発明者らは、サブスクリプション数の増加が、個々のメッセージの処理時間に与える影響を検討した。この実験では、パブリケーションとブスクリプションのαは共に０．５に設定され、両者は同一の置換ベクトルを有していた。この結果は図１４に示されている。サブスクリプション数が増加するにつれ、メッセージ処理時間の合計は、ほぼ線形に増加している。この増加の理由は、新しい各サブスクリプションが、その属性の各々に対応するテーブルに追加され、したがってメッセージが一致するサブスクリプションの数が増加するからである。しかしながら、ＳＰＳでのデータ構造（３レベルのルックアップを持つ）は、サブスクリプションが、限られた数のメッセージ、すなわちいくつかの属性においてサブスクリプションに一致するメッセージに対してのみ一致させられることを保証している。これが、メッセージ当たりの処理時間の増加が限界に近いからである。
【０１４７】
選択的なサブスクリプション
この一連の実験は、シミュレーションを用いて、選択的なサブスクリプション機構の利点を示している。１０，０００個のサブスクリプションが平均で５つの属性に関心を持つと考えられた。システムには、各々が１０，０００個の異なる値を持つ５０個の異なる属性がある。各属性に対するサブスクリプション範囲が、上記で詳述した方法を用いて独立して選ばれる。各メッセージの属性および値は独立して選ばれるが、実験に用いられたｚｉｐｆパラメータによって与えられた人気分布に従う。サブスクリプションおよびメッセージを同じ分布に従わせることによって、ＳＰＳでの高い到着率が得られる。単位時間当たり２０，０００個のメッセージ到着がある。異なったシミュレーションにおいて変えられるパラメータを以下に明確に説明する。
【０１４８】
まず、選択的なサブスクリプション手法の有効性が、完全な一致のための時間（ｔf）とカウンタインクリメント時間（ｔc）の異なった比率で示す。サブスクリプションをメッセージと一致させる平均的なｔfが０．０００１の単位時間として設定される。各サブスクリプションの平均的な範囲幅は３０ユニットである。比ｔc／ｔfは、３つの異なった値、０．０１、０．００５、および０．００１に設定される。図１５のプロットは、これらの３つの場合における一致ユニットのスループットの増加を示している。システムのいくつかの特性が、図１５によって以下のように示される。１）基本的な場合では、ＳＰＳが１つのサブスクリプション当たりたった１つの属性についてサブスクライブすると、一致ユニットのスループットは低くなり、それが障害になる。この実験では、それは、異なるメッセージ到着率の約４５％である。２）ＳＰＳがサブスクリプション当たりより多くの属性にサブスクライブするので、一致ユニットのスループット（したがってシステムのスループット）は最初増加する。しかし、ある点を越えると、カウンタインクリメントの増大したコストが、完全一致の数を減少させることによって得られた増加を凌ぐ。３）ｔc／ｔf比が小さくなればなるほど、達成可能なスループットは大きくなる。これは、カウンタの増大したメインテナンスコストに関して多くのお金を支払うことなく、余分なサブスクリプションを追加し、および完全一致の数を減らすことできるからである。４）３つの場合の２つにおいて、最大達成スループットは到着率の１００％未満である。ここで説明しているシステムにおいて、これは、ＳＰＳが過負荷になっており、そのサブスクリプションのいくつかは他のＳＰＳに負荷を委ねられる必要があると示す役目をする。
【０１４９】
次の実験は、異なったサブスクリプション範囲幅が、達成可能なスループットに与える影響を示したものである。この実験では、ｔfは０．０００１のタイムユニットに設定され、ｔc／ｔf比は０．０１である。図１６は、サブスクリプション幅が増大するにつれて、達成可能な最大スループットが低下することを実証する、この実験の結果を示している。この低下の理由は、新しいサブスクリプションと一致するメッセージは、非常に多くのサブスクリプションと部分的に一致する可能性があるからである。したがって、複数のカウンタをインクリメントする累積コストは、サブスクリプションが広くなるにつれてより急激に増大する。同じ論理は、サブスクリプション幅の増加と共に減少する初期のスループット（余分なサブスクリプションがゼロである）についても説明している。
【０１５０】
余分な属性にサブスクライブすることは、一致スループットを一層高めることができるであろうが、この達成可能な最大スループットを知ることは重要である。次の実験は、種々のパラメータが最大の達成可能なスループットに与える影響を明らかにすることを目的としている。ｔc／ｔf比は０．００５に設定され、サブスクリプションおよびパブリケーションに対するｚｉｐｆパラメータは０．７に設定され、サブスクリプション範囲の幅は２０から１００まで変化し、サブスクリプション当たりの平均の属性数は、３、５、および７と連続的に設定される。図１７は、いくつかのパラメータに対する最大の達成可能なスループットを示している。この図からの２つの重要なことが得られる。１）各サブスクリプションを追加すると、新しく追加されたトラフィックに対する潜在的なカウンタインクリメント動作が非常に多くなるため、サブスクリプション幅が大きくなるにつれ、最大の達成可能なスループットは低下する。２）サブスクリプションの属性の数が多くなればなるほど、考えられるスループットは大きくなる。これは、スループットを追加し、改善するより多くの範囲があるからである。
【０１５１】
前述の詳細な説明は、あらゆる点で例示的、代表的、しかし非制限的なものと理解されるべきであり、ここに開示された本発明の範囲は、発明の詳細な説明から決定されるべきではなく、むしろ特許法によって認められた完全な範囲に従って解釈される請求項から決定されるべきである。ここに図示し説明した種々の実施形態は、本発明の原理の例証にすぎず、種々の変形が、本発明の範囲および要旨から外れることなく当業者によって実施されてもよいことが理解されるべきである。
【図面の簡単な説明】
【０１５２】
【図１Ａ】コンテンツベースの従来のルーティングアーキテクチャを示す概略図である。
【図１Ｂ】図１Ａのアーキテクチャによる例示的フローを示すブロック図である。
【図２】本発明の実施形態によるネットワークアーキテクチャを示す概略図である。
【図３】本発明の実施形態によるサブスクリプションプロセスを示すブロック図である。
【図４】本発明の実施形態によるメッセージフローを示すブロック図である。
【図５】本発明の実施形態によるツリー構造を示す概略図である。
【図６Ａ】本発明の実施形態による例示的マルチキャスト集合を示す図である。
【図６Ｂ】本発明の実施形態による例示的マルチキャスト集合を示す他の図である。
【図７】本発明の実施形態によるマルチキャスト集合およびフィルタをマップする図である。
【図８】本発明の実施形態によるツリー構造を示す概略図である。
【図９】本発明の実施形態によるサブスクリプション一致を示す概略図である。
【図１０】ストレスの多い負荷の下での本発明のシステムにおける処理時間対属性数を示すプロットである。
【図１１】一般的な条件の下での本発明のシステムにおける処理時間対属性数を示すプロットである。
【図１２】本発明のシステムにおけるスループット比対メッセージ到着率を示すプロットである。
【図１３】本発明のシステムにおけるメッセージ当たりの処理時間対サブスクリプション数を示すプロットである。
【図１４】増加したサブスクリプション数を持つ本発明のシステムにおけるスループット比対メッセージ到着率を示すプロットである。
【図１５】本発明のシステムにおいて達成された最大スループットのパーセント対３倍の比率に対する入力トラフィックの増加パーセントのプロットを示す図である。
【図１６】本発明のシステムにおいて達成可能な最大スループットのパーセント対範囲幅を示すプロットである。
【図１７】本発明のシステムにおいて達成された最大スループットのパーセント対３つのサブスクリプション幅に対する入信トラフィックの増加パーセントを示すプロットである。
【符号の説明】
【０１５３】
２００    一般的なアーキテクチャ
２０５    パブリッシャ
２１０    パブリッシャプロキシサーバ
２１２    メッセージ
２２０    メッセージ
２７０    属性ツリー
２７５    サブスクリプションと一致する通知
２８０    サブスクリプション要求
２８５    サブスクライバプロキシサーバ
２９０    ユーザ
３０５    ユーザ１
３０６    ユーザ２
３０７    サブスクリプション
３０８    サブスクリプション
３１０    ＳＰＳ
３１５    各属性に対する重複しない範囲
３２０    属性ツリーのルート
３３０    要素
３４０    ＰＰＳ
４０１    段階１
４０５    ユーザ（パブリッシャ）
４１０    ＰＰＳ
４１１    ラベル
４１２    ラベル
４１５    入力メッセージ
４２０    属性−値対
４４１    段階２
４４２    ルート
４４３    ルート
４４５    中間ルータ
４４６    中間ルータ
４６１    段階３
４７５    ラベル
４７６    ラベル
４８０    ＳＰＳ
４８５    ユーザ（サブスクライバ）
４８６    メッセージ
５１０    送出ツリー
７１０    フィルタ
７１５    サブスクリプション
７２０    フィルタリスト
８１５    フィルタツリー
８２０    ノード
８５０    ツリー
８５５    追加のノード
９１０    新しいメッセージ
９１４    属性ツリーＩＤ
９１５    テーブルポインタ
９２０    ユーザサブスクリプションマッピングテーブル
９２１    ＳＰＳサブスクリプションＩＤ
９２２    ユーザサブスクリプションＩＤのリスト
９４０    ユーザサブスクリプション一致テーブル
９４５    ユーザサブスクリプション
９４６    属性の計数値
９４７    完全一致フラグ
９４８    ハッシュキュー
【図１Ａ】
2007234014.tif 000016
【図１Ｂ】
2007234014.tif 000017
【図２】
2007234014.tif 000018
【図３】
2007234014.tif 000019
【図４】
2007234014.tif 000020
【図５】
2007234014.tif 000021
【図６Ａ】
2007234014.tif 000022
【図６Ｂ】
2007234014.tif 000023
【図７】
2007234014.tif 000024
【図８】
2007234014.tif 000025
【図９】
2007234014.tif 000026
【図１０】
2007234014.tif 000027
【図１１】
2007234014.tif 000028
【図１２】
2007234014.tif 000029
【図１３】
2007234014.tif 000030
【図１４】
2007234014.tif 000031
【図１５】
2007234014.tif 000032
【図１６】
2007234014.tif 000033
【図１７】
2007234014.tif 000034