(57)【特許請求の範囲】
【請求項１】
複数のリンクによって相互接続された複数のノードのネットワーク内の１つ又は複数の接続のルーティングを生成する方法であって、該ネットワークは、１つのプロセッサと該プロセッサに接続されたネットワーク・データベースを備えたネットワーク制御装置を含み、該方法は、
（ａ）  該プロセッサが、該ネットワーク・データベースから該ネットワークのコンテンツ・フィルタリングを有するノードのリストを受信するステップと、
（ｂ）  該プロセッサが、１組の制約条件の条件下で、コンテンツ・フィルタリングを有する該受信したノードのリストに基づいて、コンテンツ・フィルタリングによるルーティング問題（ＲＣＦＰ）を公式化するステップを含み、該ＲＣＦＰは、ルーティング問題として定義され、該１組の制約条件は、（ｉ）  各接続のフローが、コンテンツ・フィルタリングを有する該ノードのリストの少なくとも１つを通過するという制約条件と、（ｉｉ）  ネットワーク容量が相対的に最大化されるという制約条件とを含み、該方法は、さらに、
（ｃ）  該プロセッサが、ＲＣＦＰ問題を解いて該ネットワーク内の１つ又は複数の接続についてルーティングを指定するルーティング解を生成するステップとを含む方法。
【請求項２】
各接続が、少なくとも１つのコンテンツ・フィルタリング・ノードを含む該ネットワーク内の対応する経路を有するようなコンテンツ・フィルタリングを有するノードのリストを該プロセッサが生成するステップをさらに含む請求項１に記載の発明。
【請求項３】
ステップ（ａ）が、
（ａ１）  該プロセッサが、ｋ最短経路アルゴリズムで各ソース−宛先ノード・ペアについて該ネットワーク内の１組の最短経路を計算するステップと、
（ａ２）  該プロセッサが、最短経路の各組について対応する１組の中間ノードを生成するステップと、
（ａ３）  相対最小濃度を有し、中間ノードの各組の少なくとも１つのノードに一致する一致ノードの中間ノードの各組に基いて、該プロセッサが、一致セット問題（ＨＳＰ）を公式化するステップと、
（ａ４）  該プロセッサが、ＨＳＰを解いて、コンテンツ・フィルタリング・ノードのリストに対応する一致ノードの組を生成するステップとを含む請求項１に記載の発明。
【請求項４】
ステップ（ａ４）が、
（ｉ）  該プロセッサが、中間ノードの各々の組の各ノードａについて、該ノードａを含む中間ノードのいくつかの包含の組を計算するステップと、
（ｉｉ）  該プロセッサが、包含の組の最大数を有するノードを一致セット・ノードとして選択するステップと、
（ｉｉｉ）  該プロセッサが、ステップ（（ａ４）ｉｉ）の該一致セット・ノードを含む中間ノードの各組を除去するステップと、
（ｉｖ）  該プロセッサが、中間ノードの組が残らなくなるまでステップ（（ａ４）ｉ）から（（ａ４）ｉｖ）を繰り返すステップとによってＨＳＰを解く請求項３に記載の発明。
【請求項５】
ステップ（ａ４）が保証近似係数アルゴリズムに基づいてＨＳＰを解く請求項３に記載の発明。
【請求項６】
ステップ（ｂ）が、
【数１】
0004758680.tif 000025
、及び
ｘ（Ｐ）≧０  ∀Ｐ∈Ｐｋ  ∀ｋ
の初期制約条件に従う
【数２】
0004758680.tif 000026
としてＲＣＦＰを公式化して、相対的にスケール・ファクタのλを最大化し、Ｅがリンクの組Ｅのリンクで、ｕＥがリンクＥの容量で、ｋがｋ番目のコモディティを示す整数カウンタで、Ｐｋが任意のコンテンツ・フィルタリング・ノードを通過するｋ番目のコモディティのソース・ノードｓ（ｋ）から宛先ノードｔ（ｋ）へのすべての経路の組を示し、ｘ（Ｐ）が組Ｐｋ内の経路Ｐ上をルーティングされるトラヒックを示し、Ｐｋ内のすべての経路に沿ってルーティングされるコモディティｋの総需要ｄ（ｋ）がλｄ（ｋ）に等しい請求項１に記載の発明。
【請求項７】
ステップ（ｂ）がＲＣＦＰの双対を公式化するステップを含む請求項６に記載の発明。
【請求項８】
ステップ（ｂ）が
【数３】
0004758680.tif 000027
、及び
ｗ（ｅ）≧０  ∀Ｅ∈Ｅ
の双対制約条件に従う
【数４】
0004758680.tif 000028
としてＲＣＦＰの双対を公式化し、
ｚ（ｋ）が、
【数５】
0004758680.tif 000029
に対応する各コモディティｋの変数で、
ｗ（ｅ）が、
【数６】
0004758680.tif 000030
に対応するＥの要素の各リンクｅの重みである請求項７に記載の発明。
【請求項９】
ステップ（ｃ）が、
（ｃ１）  該プロセッサが、該ネットワークの各リンクに関連する各重みと各フローを初期化するステップと、
（ｃ２）（ｃ２（ｉ））  該プロセッサが、該一致セットの少なくとも１つのノードを通る需要の最短経路を生成するステップと、
（ｃ２（ｉｉ））  該プロセッサが、該需要のフローの刻み量を決定するステップと、
（ｃ２（ｉｉｉ））  該プロセッサが、該最短経路に沿ってフローの刻み量をルーティングするステップと、
（ｃ２（ｉｖ））  該プロセッサが、該フローの刻み量に基づいて各リンクのフローと重みとを更新するステップと、
（ｃ２（ｖ））  該プロセッサが、該需要がルーティングされるまでステップ（ｃ２（ｉ））〜（ｃ２（ｖ））を繰り返すステップによって各接続の需要をルーティングするステップと、
（ｃ３）  該プロセッサが、該双対制約条件を満たすまで（ｃ１）、（ｃ２）及び（ｃ３）のステップを繰り返すステップと、
（ｃ４）  該プロセッサが、リンクの最大のルーティングされたフロー及び該リンクの容量に基づいてスケール・ファクタを生成するステップとによってＲＣＦＰを解く請求項８に記載の発明。
【請求項１０】
複数のリンクによって相互接続され、ネットワーク内でルーティングされる少なくとも１つの接続を有する複数のノードからなる該ネットワークのルーティング解を生成する方法であって、該ネットワークは、１つのプロセッサと該プロセッサに接続されたネットワーク・データベースとを備えた１つのネットワーク制御装置を含み、（１）  ノードの１つ又は複数が１組のコンテンツ・フィルタリング・ノードに含まれ、各コンテンツ・フィルタリング・ノードがコンテンツ・フィルタリングを該ノードを通過する接続に適用するように構成され、（２）  各接続が少なくとも１つのコンテンツ・フィルタリング・ノードを通過し、該方法が、
（Ａ）  該プロセッサが、１組の制約条件の条件下で、コンテンツ・フィルタリングによるルーティング問題（ＲＣＦＰ）を公式化するステップであって、該ＲＣＦＰは、ルーティング問題として定義され、該１組の制約条件は、（ｉ）  各々の接続のフローが、コンテンツ・フィルタリングを有するノードのリストのうちの少なくとも１つを通過するという制約条件と、（ｉｉ）  ネットワーク容量が相対的に最大化されるという制約条件とを含むステップと、
（Ｂ）  該プロセッサが、該ＲＣＦＰを解き、該ネットワークを通る１つ又は複数の接続のルーティングを指定する１つのルーティング解を生成するステップと、
（ａ）  該プロセッサが、該ネットワークの各リンクに関連する各重みと各フローを初期化するステップと、
（ｂ）（ｂ（ｉ））  該プロセッサが、コンテンツ・フィルタリング・ノードの組の少なくとも１つのノードを通る需要の最短経路を生成するステップと、
（ｂ（ｉｉ））  該プロセッサが、該需要のフローの刻み量を決定するステップと、
（ｂ（ｉｉｉ））  該プロセッサが、該最短経路に沿って該フローの刻み量をルーティングするステップと、
（ｂ（ｉｖ））  該プロセッサが、該フローの刻み量に基づいて各リンクのフローと重みとを更新するステップと、
（ｂ（ｖ））  該プロセッサが、該需要がルーティングされるまでステップ（ｂ（ｉ））〜（ｂ（ｖ））を繰り返すステップとによって各接続の需要をルーティングするステップとによって、該プロセッサが各々の接続の需要をルーティングするステップと、
（ｃ）  プロセッサが、該双対制約条件を満たすまで（ｂ１）、（ｂ２）及び（ｂ３）のステップを繰り返すステップと、
（ｄ）  プロセッサが、リンクの最大のルーティングされたフロー及び該リンクの容量に基づいてスケール・ファクタを生成するステップと、
（ｅ）  プロセッサが、該スケール・ファクタに基いて  （ｉ）  各リンク容量、又は（ｉｉ）  各需要のいずれかをスケーリングするステップとを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワーク内のルーティングに関し、より詳細には、ネットワーク内でコンテンツ・フィルタリングを実行するノード割り当てを備えたルーティングに関する。
【背景技術】
【０００２】
相互接続された通信ネットワーク内では、ユーザはネットワーク経路を介してネットワーク内を転送されるデータ・ストリームでソース・ノードと宛先ノードとの間の接続を確立する。１つまたは複数の接点のデータはネットワーク上のトラヒックを構成する。光ネットワークは通常、光リンクを介して接続された１組の光スイッチ（すなわち、ノード）を特徴とする。パケット・ネットワーク（光ネットワークを用いて実施できる）は通常、電気または光リンクによって相互接続されたルータ（ノードとも考えられる）を特徴とする。所与のソース−宛先（ノード）ペアの間の接続のためのネットワーク経路は、接続のデータ・ストリームまたはフローを搬送するノードに接続された１組のリンクによって相互接続された１組のノード（ソースと宛先ノード・ペアおよび任意の中間ノード）によって定義される。各ノードと各リンクは搬送可能なトラヒックに対応する容量を有し、「容量」は帯域幅、有効帯域幅、リンク品質、または同様のリンク伝送特性を指す。
【０００３】
ネットワークの各リンクは対応するデータ転送容量を備える。このリンク容量は通常、帯域幅または有効帯域幅（バッファおよび／または伝送遅延、パケット損失、およびＱｏＳ保証などの伝送要件を考慮する量）として表現される。
【０００４】
パケット・ネットワークはコンピュータ・ウィルスとワームの蔓延による悪質な攻撃にますますさらされている。迅速に伝搬する攻撃の増加によって、これらの攻撃を隔離または阻止するネットワークベースの機構の必要性が明らかになってきた。ネットワーク支援の阻止方法を用いてホストの脆弱性を低減し、または感染したホストの損害を制限するためのその他の防御機構を有効に拡張することができる。Ｃｏｄｅ−Ｒｅｄ署名のためのコンテンツ・フィルタリング、アドレスのブラックリスト掲載、および特定のポートへのアクセス禁止などのいくつかの機構を用いた特別の阻止方法を通常使用して、個々のネットワークを保護する。一般の阻止方法のうち、コンテンツ・フィルタリングが好まれる。
【０００５】
トップ１０のインターネット・サービス・プロバイダ（ＩＳＰ）などのインターネットの高利用ポイントでのコンテンツ・フィルタリングは一般に個々のカスタマ・レベルでのコンテンツ・フィルタリングよりも効果的である。コンテンツ・フィルタリング機構は他のホストベースの方法より速く起動される。これは、ワームの署名（コンテンツ・フィルタリング機構で使用する）の識別および生成が新しいワームによる蔓延に使用される機構を理解するよりも速く達成できるためである。また、ワームの署名が識別されると、ネットワークベースのコンテンツ・フィルタリング機構はより速く起動できるが、これはワームの署名が配分されるノードの数が少ないためである。
【非特許文献１】Ｊ．Ｙ．Ｙｅｎ「Ｆｉｎｄｉｎｇ  ｔｈｅ  Ｋ  ｓｈｏｒｔｅｓｔ  Ｌｏｏｐｌｅｓｓ  Ｐａｔｈ  ｉｎ  ａ  Ｎｅｔｗｏｒｋ、」Ｍａｎａｇｅｍｅｎｔ  Ｓｃｉｅｎｃｅ、ｖｏｌ．１７、ｎｏ．１１、１９７１年６月
【非特許文献２】ＧａｒｇおよびＫｏｎｅｍｍａｎ「Ｆａｓｔｅｒ  ａｎｄ  Ｓｉｍｐｌｅｒ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｕｌｔｉｃｏｍｍｏｄｉｔｙ  Ｆｌｏｗ  ａｎｄ  Ｏｔｈｅｒ  Ｆｒａｃｔｉｏｎａｌ  Ｐａｃｋｉｎｇ  Ｐｒｏｂｌｅｍｓ」３９ｔｈ  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ（ＦＯＣＳ）、１９９８年
【非特許文献３】Ｅ．Ｄｉｊｋｓｔｒａ「Ａ  Ｎｏｔｅ：Ｔｗｏ  Ｐｒｏｂｌｅｍｓ  Ｉｎ  Ｃｏｎｎｅｃｔｉｏｎ  Ｗｉｔｈ  Ｇｒａｐｈｓ」Ｎｕｍｅｒｉｃａｌ  Ｍａｔｈｅｍａｔｉｃｓ、ｖｏｌ．１、１９５９年、ｐｐ．２６９〜２７１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
コンテンツ・フィルタリングによる阻止を有効にするには、ネットワークが搬送するすべてのトラヒックをフィルタリングしなければならない。フィルタリングはワームの署名を識別して各パケットのコンテンツを完全に検証することが必要だが、これは、コンテンツ・フィルタリングをネットワーク・リソースの使用（処理および遅延）に関して高価なオペレーションにする。利用可能なコンテンツ・フィルタリング機能をネットワークのノード内に最適に配置して有効利用を図らねばならない。コンテンツ・フィルタリング・ノードのランダムな（または不適切な）選択によって、より長い経路上のルーティングが実行され、接続ごとの使用帯域幅が増加し、ネットワーク・スループットが低下する。したがって、コンテンツ・フィルタリング機能をランダムに配置すると、これらの最適でなく配置されたコンテンツ・フィルタリング・ノードにトラヒックをルーティングすることでネットワーク機能が大幅に浪費されることがある。
【課題を解決するための手段】
【０００７】
本発明の例示的な実施形態によれば、リンクによって相互接続されたノードのネットワークは、一定のノードでコンテンツ・フィルタリングを指定しており、ネットワーク内のパケット接続のルーティングは指定されたコンテンツ・フィルタリング・ノードに基いて生成される。ネットワークはコンテンツ・フィルタリング・ノード配置方法とネットワーク容量最大化方法とによって指定され、ネットワークによって搬送されるほぼすべてのトラヒック（パケット・ストリーム）のパケットにコンテンツ・フィルタリングを適用する。
【０００８】
本発明の例示的な実施形態によれば、リンクによって相互接続されたノードのネットワーク内の１つまたは複数の接続のルーティングは、（ａ）ネットワークのコンテンツ・フィルタリングを有するノードのリストを提供する工程と、（ｂ）各接続のフローがコンテンツ・フィルタリングを有するノードのリストの少なくとも１つを通過するように、１組の制約条件に従う比較的最大化されたネットワーク容量のコンテンツ・フィルタリングによるルーティング問題（ＲＣＦＰ）を形成する工程と、（ｃ）ＲＣＦＰ問題を解いてネットワーク内の１つまたは複数の接続についてルーティングを指定するルーティング解を生成する工程とによって生成される。
【０００９】
本発明の別の例示的な実施形態によれば、リンクによって相互接続され、ネットワーク内でルーティングされる少なくとも１つの接続を有するノード・ネットワークであって、１）ノードの１つまたは複数が１組のコンテンツ・フィルタリング・ノードに含まれ、各コンテンツ・フィルタリング・ノードがコンテンツ・フィルタリングをノードを通過する接続に適用するように構成され、２）各接続が少なくとも１つのコンテンツ・フィルタリング・ノードを通過するノード・ネットワークのルーティング解が生成される。ルーティング解は、（ａ）ネットワークの各リンクに関連する各重みと各フローを初期化する工程と、（ｂ）各接続の需要をルーティングする工程と、（ｃ）双対制約条件を満たすまで（ａ）と（ｂ）を繰り返す工程とによって生成される。需要は、（ｂ（ｉ））コンテンツ・フィルタリング・ノードの組の少なくとも１つのノードを通る需要の最短経路を生成する工程と、（ｂ（ｉｉ））需要のフローの刻み量を決定する工程と、（ｂ（ｉｉｉ））最短経路に沿ってフローの刻み量をルーティングする工程と、（ｂ（ｉｖ））フローの刻み量に基いて各リンクのフローと重みとを更新する工程と、（ｂ（ｖ））需要がルーティングされるまで工程（ｂ（ｉ））〜（ｂ（ｖ））を繰り返す工程とによって生成される。
本発明のその他の態様、特徴、および利点は、以下の詳細な説明と、特許請求の範囲と、添付図面からより明らかになろう。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の１つの例示的な実施形態によるコンテンツ・フィルタリングを用いたネットワークの例示的なルーティング方法（「コンテンツ・フィルタリング・ルーティング」）１００を示す図である。図１の方法が終了すると、この方法は、１）ノードを通過するトラヒックのコンテンツ・フィルタリングを実施するリンクによって相互接続されたノードのネットワークの特定のノードと（２）コンテンツ・フィルタリングを実施する特定のノードが与えられると、ネットワーク内で接続をルーティングする（所与のコスト機能または測定に基いて）最適な方法を指定する。
【００１１】
工程１０１で、コンテンツ・フィルタリング・ルーティング方法１００は、関連する需要との１組の接続を有するノードおよびリンクのネットワークのモデルを生成する。接続は、例えば、対応するソースと宛先（またはイングレスおよびエグレス）ノード・ペア間でネットワーク内をルーティングされるパケット接続を表す。関連する需要は、その接続でサポートされる帯域幅または有効帯域幅などの量である。
【００１２】
工程１０２で、方法１００は、コンテンツ・フィルタリング・ノード交換方法によって、工程１０１のネットワーク・モデルのコンテンツ・フィルタリング機能を有するノードのリストを生成する。本発明の例示的な実施形態によれば、コンテンツ・フィルタリング・ノードのリストを生成する発見的方法は、１）コンテンツ・フィルタリングの一致セット問題（ＨＳＰ）を公式化し、ｉｉ）ＨＳＰの近似解を生成する。
【００１３】
工程１０３で、方法１００は、ネットワーク容量最大化方法によって、所与の接続のトラヒックがコンテンツ・フィルタリングを適用する少なくとも１つのノードを通過しなければならないという制約条件の下で、工程１０１のネットワーク・モデルのルーティング・テーブルを生成する。工程１０３は、コンテンツ・フィルタリングによるルーティング問題（ＲＣＦＰ）を線形計画（リニア・プログラミング）問題（ＬＰＰ）として解く。
【００１４】
本発明の例示的な実施形態によれば、ＲＣＦＰはＲＣＦＰの初期ＬＰＰの双対を生成し、初期双対方法を適用して（１＋ε）近似解を生成することで解く。εの値は任意に選択された比較的小さい値で（例えば、０＜ε≦１）、そのサイズは近似解のエラーおよび計算長さに関連する。
【００１５】
工程１０１、１０２、および１０３の例示の方法について以下に説明する。工程１０１で、メッセージは以下のようにモデル化される。ネットワークＧはリンクの組Ｅ（辺とも呼ばれ、このネットワークではパケットのフローが一方向なので有向辺である）によって相互接続されたノードの組Ｎによって構成される。ネットワークはＧ＝（Ｎ，Ｅ）として定義される。組Ｎの大きさはノードの数ｎである（すなわち、｜Ｎ｜＝ｎ）。組Ｅの大きさは辺数ｍである（すなわち、｜Ｅ｜＝ｍ）。ネットワーク内のノードｉからノードｊへの有向リンクは（ｉ，ｊ）で表され、リンク（ｉ，ｊ）の容量はｕｉｊで表される。表記を簡略化するために、リンク（ｉ，ｊ）に等しいｅで表し、リンクｅの容量はｕｅで表してもよい。
【００１６】
ネットワーク内のすべてのトラヒック需要は、ネットワーク内のイングレス／エグレス（境界）ペア・ノードの組Ｂの間に存在する（すなわち、Ｂ⊆Ｎ、ただし「⊆」は数学的な「部分集合」を示す）。コンテンツをフィルタリングする機能はネットワーク内のノードの、本明細書ではコンテンツ・フィルタリング・ノードと呼ぶ境界ノードのみを含む部分集合Ｃでのみ利用できる（すなわち、Ｃ⊆Ｎ−Ｂ）。したがって、パケットがＢのイングレス−エグレス・ノード・ペアの間をルーティングされる経路はすべてＣの１つのノードを通過する。Ｂのイングレス−エグレス・ノード・ペアの間のトラヒック需要の各々はコモディティと呼ばれる。コモディティの総数をＫで表すと、Ｋ≦｜Ｂ｜（｜Ｂ｜−１）である。
【００１７】
以下に説明する実施形態では、ｓ（ｋ）はｋ番目のコモディティのソース・ノードを示し、ｔ（ｋ）はｋ番目のコモディティの宛先ノードを示し、ｄ（ｋ）はコモディティｋの需要を示す。したがって、各コモディティｋで、ｄ（ｋ）単位のフローがノードｓ（ｋ）からノードｔ（ｋ）にルーティングされる。
【００１８】
図１に戻ると、工程１０２で、コンテンツ・フィルタリング・ノードの組Ｃが、選択されたノードでのコンテンツ・フィルタリング機能のインストールが先験的に行われるために、好ましくはトラヒックの仮定に依存しない方法で決定される。コンテンツ・フィルタリングはネットワーク内の限られた数のノードでのみ実行されることがあり、ネットワーク内のあらゆるイングレス−エグレス経路は少なくとも１つのコンテンツ・フィルタリング・ノードを通過する。コモディティｋのパケットは、必ずしもｓ（ｋ）からｔ（ｋ）の単一の経路に沿ってルーティングされず、各コモディティｋをルーティングするルーティング経路候補であるｓ（ｋ）からｔ（ｋ）のＬ個の最短（ｈｏｐ）経路の組Ｐｋ，Ｌ上でルーティングされることがある。各コモディティｋのこれらのＬ個の最短経路は、効率的な方法でコストの昇順に計算することができる。これらのＬ個の最短経路は、本明細書に参照により組み込まれたＪ．Ｙ．Ｙｅｎ「Ｆｉｎｄｉｎｇ  ｔｈｅ  Ｋ  ｓｈｏｒｔｅｓｔ  Ｌｏｏｐｌｅｓｓ  Ｐａｔｈ  ｉｎ  ａ  Ｎｅｔｗｏｒｋ、」Ｍａｎａｇｅｍｅｎｔ  Ｓｃｉｅｎｃｅ、ｖｏｌ．１７、ｎｏ．１１、１９７１年６月に記載のＹｅｎのｋ個の最短経路法を用いて、計算することができる。コンテンツ・フィルタリング・ノードは望ましくはコモディティｋごとに上記のルーティング経路候補の一部について利用できる。
【００１９】
本発明の例示的な実施形態によるコンテンツ・フィルタリング・ノードの選択は、以下の法則を満たすことができる。ｋ＝１，２，．．．，Ｋのコモディティｋの経路候補に沿って１組の中間ノードＳｋが与えられると、コモディティｋの最大数の経路候補の中間ノードの組Ｓｋの少なくとも１つのノードをＣが含むような所与の濃度ｐを備えたコンテンツ・フィルタリング・ノードの組Ｃを計算することはＮＰ−ｈａｒｄである。この問題には、以下の近似係数を備えた多項式時間近似アルゴリズムが存在する。
【数１】
0004758680.tif 000002
【００２０】
図２は図１の工程１０２によって採用できるネットワーク内のコンテンツ・フィルタリング・ノードの組を選択する例示的な方法を示す。工程２０１で各コモディティｋ＝１，２，．．．，Ｋについて、ｓ（ｋ）からｔ（ｋ）のＬ個の最短経路を有する組Ｐｋ，Ｌが計算される。組Ｓｋは各コモディティｋについてのＰｋ，Ｌでのルーティング経路候補に沿った中間ノードの組を示す。
【００２１】
工程２０２で、インスタンスＳ１、Ｓ２．．．、ＳＫおよび所与の一致セットＣの濃度ｐを備えた一致セット問題（ＨＳＰ）が解かれ、一致する組Ｓｋの数が最大になる。工程２０３で、一致セットＣのノードがコンテンツ・フィルタリング・ノードとして選択される。
【００２２】
本発明を理解する助けとして、ＨＳＰの背景について説明する。コモディティｋをルーティングするイングレス−エグレス・ノード・ペアｓ（ｋ）およびｔ（ｋ）間の単一の経路Ｐｋが与えられると、ｋ＝１，２，．．．，Ｋのすべてについて、組Ｓｋは経路Ｐｋに沿った中間ノードの組を示す。各コモディティｋのパケットがルーティングされる経路Ｐｋに沿って確実にフィルタリングされるように、コンテンツ・フィルタリング・ノードの組Ｃは望ましくはすべてのｋの各組Ｓｋの少なくとも１つのノードを含む（すなわち、
【数２】
0004758680.tif 000003
ただし、数学的項「∩」は共通組
【数３】
0004758680.tif 000004
はヌル・セット、「∀」は「すべてについて」を示す。さらに、可能な限り少ないコンテンツ・フィルタリング・ノードを生成するには、そのような組Ｃは望ましくは最小濃度である（集合理論では、濃度は組内のメンバの数を指す）。ＨＳＰは以下のように記述される。全体集合Ｓからの部分集合のコレクションＳ１，Ｓ２，．．．Ｓｌ（すなわち、Ｓｋ⊆Ｓ  ∀ｋ、１≦ｋ≦ｌ）が与えられると、各組Ｓｋ  ∀ｋの少なくとも１つの要素を含む（すなわち、一致する）最小濃度の部分集合Ｃ、Ｃ⊆Ｓが求まる。
【００２３】
ＨＳＰの保証近似係数アルゴリズムとして使用される発見的方法は以下の通りである。
任意の要素ａ∈Ｓについて、要素ａを含む組Ｓｋの数κ（ａ）を計算する。
一致セットＣに含めるκ（ａ）の値を最大にする要素
【数４】
0004758680.tif 000005
を選択する。
要素
【数５】
0004758680.tif 000006
を含む組Ｓｋを除去し、κ（ａ）について最大値を備えた新しい要素
【数６】
0004758680.tif 000007
を選択しながら数κ（ａ）の計算を繰り返し、新しい要素
【数７】
0004758680.tif 000008
を含む組Ｓｋを除去する。
【００２４】
すべての組を除去するまで、この繰り返しを残りの組について継続する。
この保証近似係数アルゴリズムは自然対数ｌ（ｌｎ  ｌ）の近似係数を示す。したがって、組Ｃのサイズはせいぜい最小濃度一致セットのサイズのｌｎ  ｌ倍である。ＨＳＰの変形例は、所与の濃度ｐの組を求める問題で、｜Ｃ｜＝ｐであってＣが組Ｓｋの最大数に一致する。このＨＳＰ変形例では保証近似係数アルゴリズムが｜Ｃ｜＝ｐのポイントまで計算された場合に、
【数８】
0004758680.tif 000009
の近似係数が保証される。
【００２５】
以下の擬似コードを用いて、図２の例示の方法を実施することができる。
１００  ｆｏｒ  ｋ＝１，２，．．．，Ｋの各々    ｄｏ
１０１  Ｌ個の最短（ホップ）経路｛Ｐ１ｋ，Ｐ２ｋ，．．．，ＰＬｋ｝の組Ｐｋ、Ｌを計算
１０２  Ｌ個の最短経路アルゴリズムを用いてｓ（ｋ）からｔ（ｋ）（例：ＹｅｎまたはＬａｗｌｅｒ）；
１０３  Ｓｋ←経路Ｐ１ｋ，Ｐ２ｋ，．．．，ＰＬｋに沿った中間ノードの組
１０４  ｅｎｄ  ｆｏｒ
１０５  Ｔ←｛Ｓ１，Ｓ２，．．．，ＳＫ｝
１０６  Ｓ←Ｎ−Ｂ；（非境界ノードの組）
１０７
【数９】
0004758680.tif 000010
１０８  ｗｈｉｌｅ｜Ｃ｜＜ｐ  ｄｏ
１１０  Ｎ（ａ）←ノードが組のコレクションに現れる回数
１１１  Ｔ，∀ａ∈Ｓ−Ｃ；
１１２
【数１０】
0004758680.tif 000011
←Ｎ（ａ）が最大のノードａ
１１３
【数１１】
0004758680.tif 000012
１１４
【数１２】
0004758680.tif 000013
の各ｋについて、ｄｏ
１１５  Ｔ←Ｔ−｛Ｓｋ｝
１１６  ｅｎｄ  ｆｏｒ
１１７  ｅｎｄ  ｗｈｉｌｅ
１１８  コンテンツ・フィルタリング・ノードの組としてＣを出力
【００２６】
本発明のコンテンツ・フィルタリング・ノードの組Ｃ、ネットワーク内の辺（リンク）の組Ｅのリンク容量、およびコモディティの各々のＫ個の需要ｄ（ｋ）が与えられると、需要のλｄ（ｋ）単位が、各ルーティング経路がＣ内の少なくとも１つのコンテンツ・フィルタリング・ノードを通過するという制約条件の下ですべてのｋについてｓ（ｋ）からｔ（ｋ）にルーティングされるように、最大乗数λを計算するコンテンツ・フィルタリングによるルーティング問題（ＲＣＦＰ）が公式化される。初期ＬＰＰは式（１）、（２）、および（３）についてλを最大化する。入力パラメータは、ｉ）ネットワーク内のノードｎおよびリンクｍを含むネットワーク・グラフ、ｉｉ）対応する需要ｄを備えたコモディティｋの数、およびｉｉｉ）コンテンツ・フィルタリング・ノードの組である。
【００２７】
図１を参照すると、工程１０３のＲＦＣＰは、コンテンツ・フィルタリング・ノードが工程１０２で生成される経路インデクス（最大化）リニア・プログラムとして公式化される。任意のコモディティｋについて、Ｐｋは、組Ｃ内の任意のコンテンツ・フィルタリング・ノードを通過するノードｓ（ｋ）からノードｔ（ｋ）のすべての経路の組を示す。変数ｘ（Ｐ）は経路Ｐにルーティングされるトラヒックを示す。Ｐｋ内のすべての経路に沿ってルーティングされるコモディティｋの総需要はλｄ（ｋ）と等しく、式（１）で与えられる。
【数１３】
0004758680.tif 000014
リンクｅ上の総トラヒックはリンクｅを含むすべての経路に沿ってルーティングされる全コモディティのフローの総計である。したがって、リンクｅ上の容量制約条件は式（２）で与えられる。
【数１４】
0004758680.tif 000015
さらに、リンクのフローは負でなく、式（３）で表される。
ｘ（Ｐ）≧０  ∀Ｐ∈Ｐｋ  ∀ｋ                    （３）
本発明によるＲＣＦＰのリニア・プログラミングの公式化の１つの解は、式（２）および（３）の制約条件に従う式（１）の最大λを発見しようとする。
【００２８】
ＲＣＦＰの解によって生成されるλの最大値はλ＊で示される。λ＊≧１の場合、所与の需要はネットワーク上でルーティングされ、需要がルーティングされる明示的な経路はＲＣＦＰの解を生む経路から決定される。値λ＊＜１の場合、ＲＣＦＰの所与の解についてすべての所与の需要が同時にネットワーク上でルーティングされるわけではない。ただし、値λ＊＜１の場合、ネットワーク設計者は以下の２つのオプションのうち１つを選択できる。１）需要を
【数１５】
0004758680.tif 000016
だけ縮小する。その結果、所与のリンク容量の下でのルーティングが可能な需要の組が生成される。または、２）リンク容量をλ＊だけ拡大してすべての所与の需要のルーティングを収容する。
【００２９】
実際は、ＲＣＦＰの解は計算上は手間が掛かるかも知れないし、したがって、本発明のいくつかの実施形態では、コンテンツ・フィルタリング・ノードの組Ｃが与えられたと仮定してＲＣＦＰの解について高速組み合わせアルゴリズムを採用している。ＲＣＦＰの初期ＬＰＰの双対が公式化され、高速組み合わせアルゴリズムは、初期解内のフローを増加し、しきい値を満たすまで双対の解の重みを乗算式に更新する初期双対手法を採用する。
【００３０】
ＲＣＦＰの双対公式化は、ｉ）各コモディティｋが式（１）の制約条件に対応する変数ｚ（ｋ）と、ｉｉ）各リンクｅ∈Ｅが式（２）の制約条件に対応する変数ｗ（ｅ）とを関連付ける。双対リニア・プログラムは式（５）、（６）、および（７）の制約条件に従う式（４）の量を最小化する。
【数１６】
0004758680.tif 000017
上式は以下の式に従う。
【数１７】
0004758680.tif 000018
ｗ（ｅ）≧０  ∀Ｐ∈Ｅ                    （７）
【００３１】
式（５）の制約条件は、各コモディティｋについて、ｚ（ｋ）をリンク・コストｗ（ｅ）より小さいｓ（ｋ）からｄ（ｋ）の最短経路の長さに設定することができるということを意味する。したがって、１組の重みｗ（ｅ）、∀Ｐ∈Ｅはｚ（ｋ）が決定された後に式（６）が満たされた場合には双対の可能な解である。式（７）の制約条件によって、リンク・コストは正の値になる。したがって、λを最大化する初期ＬＰＰは、ネットワーク内の各リンクの利用率を最大化し、一方、双対はネットワーク内の各リンクの最大利用率を最小化する。
【００３２】
初期双対アルゴリズムは、以下のように動作する反復方法である。少なくとも１つのフェーズが使用され、各フェーズは少なくとも１回の反復を使用する。各フェーズで、１回または複数回の反復を使用して各コモディティｋについてノードｓ（ｋ）からｔ（ｋ）のフローのｄ（ｋ）単位を徐々に増やしてルーティングする。各フェーズの終了時に、すべてのコモディティｋ＝１，２，．．．，Ｋが組Ｃ内の少なくとも１つのノードを通ってルーティングされている。ＲＣＦＰの初期ＩＰＰの双対の式（５）の制約条件が満たされたか否かが試験で判定される。双対目的関数の値の式（４）の制約条件が１より大きい場合には、初期双対アルゴリズムは終了する。
【００３３】
図３は、初期双対アルゴリズムを用いたａ（１＋ε）近似を使用するＲＣＦＰの解を生成する例示の方法を示す。工程３０１で、辺Ｅの組の各辺について、対応するリンク重みはｗ（ｅ）＝（δ／ｕｅ）（量δは以下に述べるようにεに依存する）として初期化され、各辺の対応するルーティングされたフローｆｌｏｗ（ｅ）は、０に初期化される（すなわち、ｆｌｏｗ（ｅ）＝０  ∀ｅ∈Ｅ）。さらに、フェーズ数のカウンタｐｈａｓｅも０に初期化される。工程３０２で、ｋ個目のコモディティに対応する変数ｋは１に設定される。コモディティｋの値ｄ（ｋ）のフローは以下のように複数反復回数でｓ（ｋ）からｔ（ｋ）にルーティングされる。
【００３４】
工程３０３で、すべてのＫ個のコモディティがルーティングされた（すなわち、ｋ＝（Ｋ＋１）で最後の（Ｋ番目の）コモディティは以前の反復で処理された）か否かが試験で判定される。工程３０３の試験でｋ＝（Ｋ＋１）と判定された場合、この方法は後述の工程３１１に進む。工程３０３の試験でｋ＜（Ｋ＋１）と判定された場合、この方法は工程３０４に進む。工程３０４で、ｋ番目のコモディティが選択され、この方法は工程３０５に進む。
【００３５】
工程３０５で、一時的フロー変数ｒが需要ｄ（ｋ）の値に設定される。工程３０６で、フロー変数ｒが０より大きいか、すなわち、需要ｄ（ｋ）のフローをまだルーティングする必要があるか否かが試験で判定される。工程３０６の試験でｒが０以下と判定された場合、この方法は後述の工程３１０に進む。工程３０６の試験でｒが０以上と判定された場合、この方法は工程３０７に進む。
【００３６】
工程３０７で、リンク・コストｗ（ｅ）  ∀ｅＰ∈Ｅより小さいｓ（ｋ）からｄ（ｋ）の最短経路Ｐ∈Ｐｋ（すなわち、組Ｃの少なくとも１つのコンテンツ・フィルタリング・ノードを通過する最短経路）が計算される。
【００３７】
工程３０８で、工程３０７で生成された最短経路Ｐのフローのインクリメンタル量がルーティングされ、経路Ｐ内の辺のフローおよび重みが更新される。経路ＰはＣ内のいくつかのノードを通過するように制約されているので、リンクを複数回横断することができる。変数Ｎｐ（ｅ）は経路Ｐがリンクｅを横断する回数である。次いで、経路Ｐに沿ったルーティング・フローのために、リンクｅの容量はｕｅではなく有効にはｕｅ／Ｎｐ（ｅ）である。したがって、経路Ｐ上の最小（有効）リンク容量は、
【数１８】
0004758680.tif 000019
で与えられる。
【００３８】
ｒからのフローのインクリメンタル量Δは反復内で経路Ｐに沿って送信される。ｒからのフローのインクリメンタル量Δは、総計ｄ（ｋ）になるようにｓ（ｋ）からｔ（ｋ）に送信されるフローのｉ）量ｕとｉｉ）残りの量の最小値である。値Δのフローが経路Ｐに沿って送信された後で、各リンクｅ∈Ｐ上の総フローはＮｐ（ｅ）Δだけ増加し（すなわち、ｆｌｏｗ（ｅ）はＮｐ（ｅ）Δだけインクリメントし）、重みｗ（ｅ）∀ｅ∈Ｐは式（８）に示すように更新される。
【数１９】
0004758680.tif 000020
重みｗ（ｅ）のこの更新後に、一時フロー変数がｒ←ｒ−Δと更新され、この方法は工程３０６に戻る。
【００３９】
工程３０６の試験でｒが０に等しいと判定された場合、コモディティの総フローｄ（ｋ）がルーティングされ、反復が完了し、この方法は工程３１０に進む。工程３１０で、ｋの値は１だけインクリメントし、この方法は工程３０３に戻る。前述したように、工程３０３の試験でｋ＝（Ｋ＋１）と判定された場合、コモディティ需要ｄ（ｋ）の各々がルーティングされ、この方法は後述の工程３１１に進む。
工程３１１で、カウンタｐｈａｓｅの値が１だけインクリメントし、変数Ｄが式（９）の値に設定される。
Ｄ←Σｅ∈Ｅ  ｕｅ  ｗ（ｅ）                    （９）
式（９）は式（６）の左辺の双対目的関数値に等しい。
【００４０】
工程３１２で、変数Ｄが１以上か否かが試験で判定される。工程３１２の試験で変数Ｄが１より小さいと判定された場合、双対制約条件は満たされず、フェーズは完了し、この方法は工程３０２に戻って別のフェーズを開始する。工程３１２の試験で変数Ｄが１より以上と判定された場合、双対制約条件は満たされ、この方法は工程３１３に進む。
【００４１】
工程３１３で、スケール・ファクタλが計算され、出力として提供される。工程３１２の後で、双対実行可能性制約条件が満たされるが、初期解内のリンク容量制約条件は破られることがある。これはこの方法が反復ごとの元の（残りではなく）リンク容量ｕｅを使用するためである。リンク容量制約条件の違反を補償するため、各リンク上のトラヒック（フロー）は均一にスケーリングされて容量制約条件が遵守される。その結果、スケール・ファクタは上述のようにスケーリングに対して計算され、使用される。スケール・ファクタλが、ｉ）アルゴリズムが終了した時の辺（リンク）ｅ上のルーティングされたフローのｉｉ）辺ｅの元の容量ｕｅに対する最大の割合である、リンク容量値の最大違反値の逆数に基いて計算される。この最大割合もまたこの方法が完了するフェーズの数によって増加する。
したがって、スケール・ファクタλはｐｈａｓｅ／ｓｃａｌｅ＿ｆａｃｔとして生成され、ｓｃａｌｅ＿ｆａｃｔは式（１０）で与えられる。
ｓｃａｌｅ＿ｆａｃｔ＝ｍａｘｅ∈Ｅ（ｆｌｏｗ（ｅ）／ｕｅ）        （１０）
【００４２】
図３の方法が終了すると、スケール・ファクタの提供に加え、インクリメントによる最短経路計算でのルーティング需要の反復プロセスが接続の需要をルーティングするルーティング解を生成する。
以下の擬似コードを用いて、図２の例示の方法を実施することができる。
１００
【数２０】
0004758680.tif 000021
１０１  ｆｌｏｗ（ｅ）←∀  ｅ∈Ｅ
１０２  ｐｈａｓｅ←０
１０３  ｒｅｐｅａｔ
１０４  ｆｏｒ  ｋ＝１，２，．．．，Ｋの各々    ｄｏ
１０５  ｒ＝ｄ（ｋ）
１０６  ｗｈｉｌｅ  ｒ＞０
１０７  リンク・コストより小さいｓ（ｋ）からｔ（ｋ）への最短経路Ｐを計算
１０８  Ｃ内の少なくとも１つのノードを通過するｗ（ｅ）∀  ｅ∈Ｅ
１０９  Ｎ（ｅ）←リンクｅが経路Ｐ、∀  ｅ∈Ｐ上に現れる回数
１１０
【数２１】
0004758680.tif 000022
１１１  Δ←ｍｉｎ（ｒ、ｕ）
１１２  ｆｌｏｗ（ｅ）←ｆｌｏｗ（ｅ）＋Ｎ（ｅ）Δ、∀  ｅ∈Ｐ
１１３
【数２２】
0004758680.tif 000023
１１４  ｒ←ｒ−Δ
１１５  ｅｎｄ  ｗｈｉｌｅ
１１６  ｅｎｄ  ｆｏｒ  
１１７  ｐｈａｓｅ←ｐｈａｓｅ＋１
１１８  Ｄ←Σｅ∈Ｅ  ｕｅ  ｗ（ｅ）；
１１９  ｕｎｔｉｌ  Ｄ≧１
１２０  ｓｃａｌｅ＿ｆａｃｔ＝ｍａｘｅ∈Ｅ  ｆｌｏｗ（ｅ）／ｕｅ；
１２１  出力λ＝ｐｈａｓｅ／ｐｈａｓｅ＿ｆａｃｔ；
【００４３】
εおよびδの値は関連する：任意の所与のε’＞０（すなわち、所与の設計がε’の小さい値を任意に選択する）の場合、近似リンク・パターン・アルゴリズムは、式（１１）および（１２）で与えられるように、εおよびδの最適条件の（１＋ε’）係数内の目的関数値の解を計算する。
【数２３】
0004758680.tif 000024
【００４４】
ただし、ｍはネットワーク内のリンクの数である。ε近似アルゴリズムの説明は、全体が本明細書に参照により組み込まれたＧａｒｇおよびＫｏｎｅｍｍａｎ「Ｆａｓｔｅｒ  ａｎｄ  Ｓｉｍｐｌｅｒ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｍｕｌｔｉｃｏｍｍｏｄｉｔｙ  Ｆｌｏｗ  ａｎｄ  Ｏｔｈｅｒ  Ｆｒａｃｔｉｏｎａｌ  Ｐａｃｋｉｎｇ  Ｐｒｏｂｌｅｍｓ」３９ｔｈ  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ（ＦＯＣＳ）、１９９８年に記載されている。
【００４５】
図３に戻ると、図３の工程３０７で、Ｃ内の少なくとも１つのノードを通過するリンク・コストｗ（ｅ）∀ｅ∈Ｅより小さいｓ（ｋ）からｔ（ｋ）の最短経路Ｐが計算される。図４はアルゴリズムの反復ごとに制約された最短経路を計算する工程３０７のために使用する例示の方法を示す。
【００４６】
工程４０１で、ダイクストラ法を用いて、Ｃ内のｓ（ｋ）からすべてのノードへの最短コスト経路が計算される。この処理は、ｓ（ｋ）をルートとし、Ｃ内のすべてのノードに達する最短経路のツリーを構築する単一の最短経路計算である。ｓ（ｋ）からノードｉ∈Ｃへの最短経路のコストはｄｓ（ｉ）で示される。ダイクストラの最短経路法は、全体が本明細書に参照により組み込まれたＥ．Ｄｉｊｋｓｔｒａ「Ａ  Ｎｏｔｅ：Ｔｗｏ  Ｐｒｏｂｌｅｍｓ  Ｉｎ  Ｃｏｎｎｅｃｔｉｏｎ  Ｗｉｔｈ  Ｇｒａｐｈｓ」Ｎｕｍｅｒｉｃａｌ  Ｍａｔｈｅｍａｔｉｃｓ、ｖｏｌ．１、１９５９年、ｐｐ．２６９〜２７１に記載されている。
【００４７】
工程４０２で、各リンクが反転したネットワーク・グラフ上でダイクストラ法を用いて、Ｃの各ノードからノードｔ（ｋ）への最短経路が計算される。各ノードｉ∈Ｃからノードｔ（ｋ）への最短経路のコストはｄｔ（ｉ）で示される。
【００４８】
工程４０３で、最小距離はｄｍｉｎ＝ｍｉｎｉ∈ＥＣ［ｄｓ（ｉ）＋ｄｔ（ｉ）］で、最小距離がノードｃ∈Ｃについて達成される。次いで、ｓ（ｋ）からｔ（ｋ）への制約最短コスト経路がｓ（ｋ）からノードｃへの最短コスト経路とノードｃからｔ（ｋ）への最短コスト経路との連結によって生成される（この経路はコスト［ｄｓ（ｃ）＋ｄｒ（ｃ）］を有する）。
【００４９】
本発明の１つまたは複数の実施形態によるコンテンツ・フィルタリングを用いたネットワーク・ルーティング設計は以下の利点を提供できる。第１に、ネットワークによって搬送されるすべてのトラヒックがフィルタリングされるので、コンテンツ・フィルタリングは効果的である。利用できるコンテンツ・フィルタリング機能は最適にネットワークのノード内に配置でき、その結果、接続ごとの帯域幅の使用は低減し、ネットワーク・スループットは向上する。したがって、本発明の１つまたは複数の例示的な実施形態によるコンテンツ・フィルタリング機能の配置の結果、上記の最適に配置されたコンテンツ・フィルタリング・ノードへのトラヒックのルーティングでのネットワーク機能は大幅に有効に使用される。
【００５０】
本発明の例示的な実施形態はさまざまな式を参照して説明しているが、本発明はこれらの式の形式には限定されない。当業者は、スケーリンクによってこれらの式を変更し、または当技術分野でよく知られているいくつかの技法のいずれかを用いて本明細書に記載したリニア・プログラミング問題の異なる近似解を形成することができる。
【００５１】
本発明はネットワーク制御装置またはコンピュータなどのプロセッサ内で具体化でき、プロセッサはネットワークまたは本明細書に記載の方法が使用するネットワーク・トポロジ、プロビジョニング、および容量情報を受信するネットワーク・データベースに結合できる。さらに、本発明は有線、無線、光、または光以外のネットワークで使用でき、同期または非同期ネットワークのいずれにも使用できる。
【００５２】
本発明はコンテンツ・フィルタリング用途に限定されず、一般に、プログラマブル・ネットワークの容量プランニングに使用できる。プログラマブル・ネットワーク内のネットワーク要素は特定用途向け機能を備えたコンポーネントを有することができる。機能のそれぞれのタイプについて、特別のノードの指定された組を提供して指定の機能を提供できる。所与の機能の選択を用いるすべてのアプリケーション・トラヒック・ストリームは、望ましくは、ネットワークから外に出る前に、選択内の各々のタイプの特別のノードの組から少なくとも１つのノードを通過する。各タイプの機能の特別のノードの少なくとも１つを訪れる制約条件を満たすように、個々の接続をルーティングするレイヤ化グラフ手法を使用できる。
【００５３】
当業者には明らかなように、容量フィルタリングのさまざまな機能は回路要素で実施でき、またソフトウェア・プログラム内の処理工程としてディジタル・ドメイン内で実施することもできる。そのようなソフトウェアは、例えば、ディジタル信号プロセッサ、マイクロコントローラ、または汎用コンピュータで使用することができる。
【００５４】
本発明は方法およびこれらの方法を実施する装置の形で具体化できる。また、本発明は、フロッピー（登録商標）・ディスケット、ＣＤ−ＲＯＭ、ハード・ドライブ、またはその他の任意のマシン可読記憶媒体などの有形の媒体に具体化されたプログラム・コードの形で具体化できる。プログラム・コードがコンピュータなどのマシン内にロードされマシンによって実行されると、マシンは本発明を実施する装置になる。また、本発明は、記憶媒体に記憶され、マシン内にロードされかつ／またはマシンによって実行され、電気配線またはケーブル上で、光ファイバを通して、または電磁放射によるなどの方法で何らかの伝送媒体上で送信されるかを問わず、プログラム・コードの形で具体化でき、プログラム・コードがコンピュータなどのマシン内にロードされマシンによって実行されると、マシンは本発明を実施する装置になる。汎用プロセッサ上で実施されると、プログラム・コード・セグメントはプロセッサと結合して特定の論理回路に類似した動作をする一意的なデバイスを提供する。
【００５５】
本発明の性質を説明するために記述および図示してきた部分の詳細、材料、および構成のさまざまな変更を、特許請求の範囲に記載する本発明の原理および範囲を逸脱することなく、当業者は実行することができる。
【図面の簡単な説明】
【００５６】
【図１】本発明の１つの例示的な実施形態によるコンテンツ・フィルタリングを用いたネットワークの例示的なルーティング方法を示す図である。
【図２】ネットワーク内のコンテンツ・フィルタリング・ノードの組を選択する例示的な方法を示す図である。
【図３】本発明による所与のコンテンツ・フィルタリング・ノードの組をルーティングする例示的な方法を示す図である。
【図４】制約された最短経路を計算する図３の方法によって使用できる例示的な方法を示す図である。
【図１】
0004758680.tif 000031
【図２】
0004758680.tif 000032
【図３】
0004758680.tif 000033
【図４】
0004758680.tif 000034