(57)【要約】  様々な例示的実施形態は、以下のうちの１つまたは複数を含む方法および関連ネットワークノードに関する：第１のネットワークデバイスで、転送されるべきメッセージを受信するステップと、メッセージの宛先アドレスを決定するステップと、宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップと、宛先アドレスが第１のネットワークデバイスに割り当てられていない場合、宛先アドレスのネクストホップについて第２のネットワークデバイスに問い合わせるステップと、問合せに応答して、宛先アドレスのネクストホップの表示を受信するステップと、ネクストホップの表示に応答して、第１のネットワークデバイスによってメッセージをネクストホップに転送するステップ。
2015512231.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを転送するために第１のネットワークデバイスによって実行される方法であって、
第１のネットワークデバイスで、転送されるべきメッセージを受信するステップ（７１０）と、
メッセージの宛先アドレスを決定するステップ（７１５）と、
宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップ（７３０、７４０）と、
宛先アドレスが第１のネットワークデバイスに割り当てられていない場合、宛先アドレスのネクストホップについて第２のネットワークデバイスに問い合わせるステップ（７６０）と、
問合せに応答して、宛先アドレスのネクストホップの表示を受信するステップ（７６５）と、
ネクストホップの表示に応答して、第１のネットワークデバイスによってメッセージをネクストホップに転送するステップ（７７５）とを備える、方法。
【請求項２】
宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップ（７３０、７４０）が、
ハッシュキーを生成するために、宛先アドレスにハッシュ関数を実行するステップ（１０１０）と、
ハッシュキーに最も近い複数のネットワークデバイスＩＤのネットワークデバイス識別（ＩＤ）を識別するステップ（１０４５）と、
識別されたネットワークデバイスＩＤが、第１のネットワークデバイスに関連付けられるかどうかを決定するステップ（７４０）とを備える、請求項１に記載の方法。
【請求項３】
識別されたネットワークデバイスＩＤが第２のネットワークデバイスに関連付けられる、請求項２に記載の方法。
【請求項４】
ハッシュ関数を実行するステップ（１０１０）が、
宛先アドレスの第１のコンポーネントおよび第２のコンポーネントを識別するステップと、
第１のコンポーネントをハッシュするステップと、
第１のコンポーネントをハッシュするステップとは無関係に、第２のコンポーネントをハッシュするステップと、
少なくともハッシュされた第１のコンポーネントとハッシュされた第２のコンポーネントとを結合して、ハッシュキーを生成するステップとを備える、請求項２から３のいずれかに記載の方法。
【請求項５】
第１のネットワークデバイスが、宛先アドレスに関連するキャッシュエントリを格納するかどうかを決定するステップ（７２０）と、
ネクストホップの表示に応答して、第１のネットワークデバイスで、宛先アドレスに関連して、およびネクストホップの表示に基づいて、新しいキャッシュエントリを加えるステップ（７７０）とをさらに備え、
宛先アドレスが第１のネットワークデバイスに割り当てられるかどうかを決定するステップ（７４０）が、第１のネットワークデバイスが宛先アドレスに関連するキャッシュエントリを格納しない場合に実行される、請求項１から４のいずれかに記載の方法。
【請求項６】
宛先アドレスがコンテンツ名である、請求項１から５のいずれかに記載の方法。
【請求項７】
ペンディングルートテーブルにメッセージを加えるステップ（７３５）と、
宛先アドレスのネクストホップの表示を受信するステップに応答して、ペンディングルートテーブルからメッセージを取り出すステップとをさらに備える、請求項１から６のいずれかに記載の方法。
【請求項８】
第１のネットワークデバイスで、ルート更新メッセージを受信するステップであって、ルート更新メッセージが宛先アドレスを含む、受信するステップ（９１０）と、
ルート更新メッセージに関連付けられる第１のネットワークデバイスのネクストホップを識別するステップ（９１５）と、
ルート更新メッセージを受信するステップに応答して、宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップ（９２０、９２５）と、
宛先アドレスが第１のネットワークデバイスに割り当てられていない場合、ネクストホップおよび宛先アドレスを第２のネットワークデバイスに送信するステップ（９３５）とをさらに備える、請求項１から７のいずれかに記載の方法。
【請求項９】
メッセージを受信するように構成されたネットワークインターフェース（２１０）と、
メッセージに関連付けられる宛先アドレスを決定して、
宛先アドレスがネットワークデバイスに割り当てられているかどうかを決定して、
宛先アドレスがネットワークデバイスに割り当てられていない場合、ネットワークインターフェースを介して、宛先アドレスのネクストホップについて第２のネットワークデバイスに問い合わせて、
問合せに応答して、およびネットワークインターフェースを介して、宛先アドレスのネクストホップの表示を受信して、
ネクストホップの表示に応答して、ネットワークインターフェースを介して、メッセージをネクストホップに転送する
ように構成された委任マネージャ（２３０）とを備える、ネットワークデバイス。
【請求項１０】
宛先アドレスがネットワークデバイスに割り当てられているかどうかを決定する際に、委任マネージャ（２３０）が、
ハッシュキーを生成するために、宛先アドレスにハッシュ関数を実行して、
ハッシュキーに最も近い複数のネットワークデバイスＩＤのネットワークデバイス識別（ＩＤ）を識別して、
識別されたネットワークデバイスＩＤが、ネットワークデバイスに関連付けられるかどうかを決定する
ように構成される、請求項９に記載のネットワークデバイス。
【請求項１１】
識別されたネットワークデバイスＩＤが第２のネットワークデバイスに関連付けられる、請求項１０に記載のネットワークデバイス。
【請求項１２】
ハッシュ関数を実行する際に、委任マネージャ（２３０）が、
宛先アドレスの第１のコンポーネントおよび第２のコンポーネントを識別して、
第１のコンポーネントをハッシュして、
第１のコンポーネントをハッシュするステップとは無関係に、第２のコンポーネントをハッシュして、
少なくともハッシュされた第１のコンポーネントとハッシュされた第２のコンポーネントとを結合して、ハッシュキーを生成する
ように構成される、請求項１０から１１のいずれかに記載のネットワークデバイス。
【請求項１３】
ルートキャッシュが、宛先アドレスに関連するキャッシュエントリを格納するかどうかを決定して、
ネクストホップの表示に応答して、宛先アドレスに関連して、およびネクストホップの表示に基づいて、新しいキャッシュエントリを加える
ように構成されたルートキャッシュ（２２０）をさらに備え、
委任マネージャが、ルートキャッシュが宛先アドレスに関連するキャッシュエントリを格納しないことを決定するルートキャッシュに応答して、宛先アドレスがネットワークデバイスに割り当てられるかどうかを決定するように構成される、請求項９から１２のいずれかに記載のネットワークデバイス。
【請求項１４】
宛先アドレスがコンテンツ名である、請求項９から１３のいずれかに記載のネットワークデバイス。
【請求項１５】
委任マネージャが宛先アドレスのネクストホップの表示を待つ間、メッセージを格納するペンディングルートテーブル（２４０）をさらに備える、請求項９から１４のいずれかに記載のネットワークデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に開示される様々な例示的実施形態は、一般に遠隔通信ネットワークに関する。
【背景技術】
【０００２】
インターネットは、機械を相互接続するための媒体から、ビデオや写真などのコンテンツを有する機械を接続するための媒体へと進化した。インターネットは、ＩＰアドレスを介して情報をルーティングすることなどの様々な仕組みの上に開発されたが、将来のアーキテクチャは、インターネットの現在の状態を考慮して、代替のメカニズムを使用することができる。多くの提案の中のある一般的な原則は、これらの将来のアーキテクチャは、機械自体ではなく、提供されるコンテンツを中心とすることができるということである。
【０００３】
コンテンツ中心のネットワーキングは、場所ではなく名前によってコンテンツが要求される、より新しいパラダイムである。このパラダイムは名前ベースのルーティングを使用することができ、ルータは、「コンテンツ名」に基づいて、宛先サーバにトラフィックを移動させることができる。このように、インターネットルータは、移動されるコンテンツに関する明示的な情報を提供され得る。
【０００４】
名前ベースのルーティングのある結果は、ＩＰアドレスがバリエーションの数で制約され、地理的にクラスタ化されているのに対して、類似の名前のコンテンツをホストしているサーバの位置に関係なく、コンテンツ名は事実上任意の値を取ることができ、また、任意の場所に位置するサーバを指すことができることである。このように、名前ベースのルーティングテーブル内のエントリ数は、ＩＰｖ４またはＩＰｖ６ルーティングテーブルよりもはるかに大きい場合がある。これは、テーブルを効率的に格納して、テーブルを使用してトラフィックを迅速に転送する際の新たな課題を提示している。
【発明の概要】
【課題を解決するための手段】
【０００５】
以下に、様々な例示的実施形態の要約を提示する。以下の要約において、いくつかの簡略化および省略が行われる場合があるが、それは様々な例示的実施形態のいくつかの側面を強調および紹介することを意図するものであり、本発明の範囲を限定することを意図するものではない。当業者が本発明の概念を作成および使用することを可能にするために適切な、好ましい例示的実施形態の詳細な説明を、以下のセクションに記述する。
【０００６】
様々な例示的実施形態は、メッセージを転送するために第１のネットワークデバイスによって実行される方法に関し、本方法は、以下のうちの１つまたは複数を含む：第１のネットワークデバイスで、転送されるべきメッセージを受信するステップと、メッセージの宛先アドレスを決定するステップと、宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップと、宛先アドレスが第１のネットワークデバイスに割り当てられていない場合、宛先アドレスのネクストホップについて第２のネットワークデバイスに問い合わせるステップと、問合せに応答して、宛先アドレスのネクストホップの表示を受信するステップと、ネクストホップの表示に応答して、第１のネットワークデバイスによってメッセージをネクストホップに転送するステップ。
【０００７】
様々な例示的実施形態は、メッセージを転送する際に第２のネットワークデバイスを補助するために第１のネットワークデバイスによって実行される方法に関し、本方法は、以下のうちの１つまたは複数を含む：第１のネットワークデバイスで、第２のネットワークデバイスからの問合せを受信するステップであって、問合せがデバイス識別子（ＩＤ）および宛先アドレスを含む、受信するステップと、問合せを受信するステップに応答して、少なくともデバイスＩＤおよび宛先アドレスに基づいてメッセージのネクストホップを識別するステップであって、それによってネクストホップが第２のネットワークデバイスに関するネクストホップである、識別するステップと、ネクストホップを示す応答を第２のネットワークデバイスに送信するステップ。
【０００８】
様々な例示的実施形態は、以下のうちの１つまたは複数を含むネットワークデバイスに関する：メッセージを受信するように構成されたネットワークインターフェースと、メッセージに関連付けられる宛先アドレスを決定して、宛先アドレスがネットワークデバイスに割り当てられているかどうかを決定して、宛先アドレスがネットワークデバイスに割り当てられていない場合、ネットワークインターフェースを介して、宛先アドレスのネクストホップについて第２のネットワークデバイスに問い合わせて、問合せに応答して、およびネットワークインターフェースを介して、宛先アドレスのネクストホップの表示を受信して、ネクストホップの表示に応答して、ネットワークインターフェースを介して、メッセージをネクストホップに転送するように構成された、委任マネージャ。
【０００９】
様々な実施形態が説明され、宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップは、以下を含む：ハッシュキーを生成するために、宛先アドレスにハッシュ関数を実行するステップと、ハッシュキーに最も近い複数のネットワークデバイスＩＤのネットワークデバイス識別子（ＩＤ）を識別するステップと、識別されたネットワークデバイスＩＤが、第１のネットワークデバイスに関連付けられるかどうかを決定するステップ。
【００１０】
様々な実施形態が説明され、識別されたネットワークデバイスＩＤは、第２のネットワークデバイスに関連付けられる。
【００１１】
様々な実施形態が説明され、ハッシュ関数を実行するステップは、以下を含む：宛先アドレスの第１のコンポーネントおよび第２のコンポーネントを識別するステップと、第１のコンポーネントをハッシュするステップと、第１のコンポーネントをハッシュするステップとは無関係に、第２のコンポーネントをハッシュするステップと、少なくともハッシュされた第１のコンポーネントとハッシュされた第２のコンポーネントとを結合して、ハッシュキーを生成するステップ。
【００１２】
様々な実施形態は、第１のネットワークデバイスが、宛先アドレスに関連するキャッシュエントリを格納するかどうかを決定するステップと、ネクストホップの表示に応答して、第１のネットワークデバイスで、宛先アドレスに関連して、およびネクストホップの表示に基づいて、新しいキャッシュエントリを加えるステップとをさらに含むことができ、宛先アドレスが第１のネットワークデバイスに割り当てられるかどうかを決定するステップは、第１のネットワークデバイスが宛先アドレスに関連するキャッシュエントリを格納しない場合に実行される。
【００１３】
様々な実施形態が説明され、宛先アドレスはコンテンツ名である。
【００１４】
様々な実施形態は、ペンディングルートテーブルにメッセージを加えるステップと、宛先アドレスのネクストホップの表示を受信するステップに応答して、ペンディングルートテーブルからメッセージを取り出すステップとをさらに含む。
【００１５】
様々な実施形態は、第１のネットワークデバイスで、ルート更新メッセージを受信するステップであって、ルート更新メッセージが宛先アドレスを含む、受信するステップと、ルート更新メッセージに関連付けられる第１のネットワークデバイスのネクストホップを識別するステップと、ルート更新メッセージを受信するステップに応答して、宛先アドレスが第１のネットワークデバイスに割り当てられているかどうかを決定するステップと、宛先アドレスが第１のネットワークデバイスに割り当てられていない場合、ネクストホップおよび宛先アドレスを第２のネットワークデバイスに送信するステップとをさらに含む。
【００１６】
様々な実装形態は、第１のネットワークデバイスで、第２のネットワークデバイスからルート更新を受信するステップであって、ルート更新が、宛先アドレスとネクストホップとの少なくとも一部を表示する、受信するステップと、第２のネットワークデバイスに関連して、第１のネットワークデバイスで、宛先アドレスとネクストホップの少なくとも一部を格納するステップとをさらに含む。
【００１７】
様々な実装形態が説明され、第１のネットワークデバイスはルータである。
【００１８】
様々な実装形態が説明され、少なくともデバイスＩＤおよび宛先アドレスに基づいてメッセージのネクストホップを識別するステップは、以下を含む：マッチングルーティングレコードを識別するために、宛先アドレスに基づいて最長プレフィックスマッチングを実行するステップと、デバイスＩＤに関連付けられるマッチングルーティングレコードのフィールドを識別するステップと、ネクストホップとして識別されたフィールドの値を使用するステップ。
【００１９】
様々な例示的実施形態をよりよく理解するために、添付の図面を参照する。
【図面の簡単な説明】
【００２０】
【図１】メッセージをルーティングするための例示的ネットワークを示す図である。
【図２】メッセージをルーティングするための例示的ネットワークデバイスを示す図である。
【図３】ルートキャッシュデータを格納するための例示的データ構成を示す図である。
【図４】ペンディングルートテーブルを格納するための例示的データ構成を示す図である。
【図５】フィルタを格納するための例示的データ構成を示す図である。
【図６】ルートテーブルを格納するための例示的データ構成を示す図である。
【図７】メッセージを転送するための例示的方法を示す図である。
【図８】メッセージを転送する際に、別のデバイスを補助するための例示的方法を示す図である。
【図９】ルート更新を処理するための例示的方法を示す図である。
【図１０】ルート操作を委任するための例示的方法を示す図である。
【発明を実施するための形態】
【００２１】
理解を容易にするために、実質的に同一または類似の構造、および／あるいは、実質的に同一または類似の機能を有する要素を指すために、同一の参照数字が使用されている。
【００２２】
上述のように、様々な新たなルーティングパラダイムが、インターネットや他のネットワークを介するトラフィックをルーティングする際に使用されるルーティングテーブルを拡大することを提案している。より大きなテーブルは、より大きくより高速なメモリ、およびより高速なプロセッサによって対応され得るが、この手法は法外な費用がかかる場合がある。したがって、複数のルータおよび／または他のネットワークデバイス間で、ルーティングテーブルおよび／または様々なルーティング操作を分散することができるルート解決の方法を実装することが望ましい場合がある。様々なさらなる目的および利点は、以下の説明を読めば明らかになるだろう。本明細書に記載の様々な例は、名前ベースのルーティングに関して説明されており、記載される方法およびシステムは、たとえばＩＰｖ４またはＩＰｖ６プロトコルによるルーティングなどの他の環境で有用であり得ることが、当業者には明らかであろう。
【００２３】
次に、同様の数字が同様のコンポーネントまたはステップを指す図面を参照すると、様々な例示的実施形態の広範な態様が開示されている。
【００２４】
図１は、メッセージをルーティングするための例示的ネットワーク１００を示している。様々な例示的実施形態では、例示的ネットワーク１００はインターネットまたはその一部でよい。当業者には、例示的ネットワーク１００はいくつかの点で簡略型を構成することができることが明らかである。たとえば、例示的ネットワーク１００は、多数のさらなるクライアント、サーバ、ルータ、スイッチ、および／または他のネットワークデバイスを含み得る。図示されるように、例示的ネットワーク１００は、いくつかのネットワークデバイスを含み得る：クライアントデバイス１１０、２つのサーバ１２０、１３０、および５つのルータ１４０ａ−ｅ。本明細書で使用されるように、「ルータ」という用語は、データメッセージを受信して、データメッセージをそれらの最終宛先に転送することができる任意のネットワークデバイスを指すと理解され得る。したがって、「ルータ」という用語は、たとえばスイッチ（層２）または真のルータ（層３）などのネットワークのＯＳＩモデルの任意の層で操作するネットワークデバイスを包含することができる。さらに、「メッセージ」という用語は、たとえばフレームまたはパケットなどの、あるデバイスから別のデバイスに転送されたデータの任意のチャンクを包含すると理解される。
【００２５】
図示されるように、ルータ１４０ａ−ｅは、これらのデバイス間でメッセージを交換できるように、クライアントデバイス１１０、サーバ１２０、およびサーバ１３０を相互接続することができる。上述したように、例示的ネットワーク１００は簡略型を構成してもよく、したがって、図示されるそれらのネットワークデバイス間の通信を提供するいくつかの中間ルータおよび／または他のネットワークデバイス（図示せず）があってもよい。たとえば、ルータ１４０ｃは、１つまたは複数の中間ネットワークデバイス（図示せず）を通じてサーバ１２０に接続され得る。
【００２６】
クライアントデバイス１１０は、ネットワークを介してコンテンツを要求して受信することができる任意のデバイスでよい。たとえば、クライアントデバイス１１０は、パーソナルコンピュータ、ラップトップ、モバイル電話、タブレット、または他のデバイスを含み得る。サーバ１２０、１３０は、それぞれ要求を受信してコンテンツを提供することができる任意のデバイスでよい。たとえば、サーバ１２０、１３０は、それぞれパーソナルコンピュータ、スタンドアロン型サーバ、ブレードサーバ、または他のデバイスを含み得る。サーバ１２０、１３０は、それぞれいくつかのコンテンツアイテムをホストすることができ、各アイテムは少なくとも１つのコンテンツ名によって識別される。図示されるように、たとえば、サーバ１２０は、「ＴＵＸ／ｎｏｔｅｓ．ｔｘｔ」、「ＪＤＯＥ／ｎｏｔｅｓ．ｔｘｔ」、および「／ＪＤＯＥ／ＶＩＤＥＯＳ／ＪＤ２０１２／ｖｉｄ．ａｖｉ」として識別された３つのコンテンツアイテムをホストすることができる。別の例を挙げると、サーバ１３０は、「／ＪＤＯＥ／ＰＡＰＥＲＳ／ＰａｐｅｒＡ．ｐｄｆ」、「／ＪＤＯＥ／ＰＡＰＥＲＳ／ＰａｐｅｒＢ．ｐｄｆ」、および「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」として識別された３つのコンテンツアイテムもホストすることができる。クライアントデバイス１１０は、要求メッセージを送信することによって、これらのアイテムのうちのいくつかの配信を要求することができ、その要求メッセージはルータ１４０ａ−ｅによって適切なサーバ１２０、１３０にルーティングされる。このルーティングは、要求されたコンテンツの名前に基づいて実行され得る。したがって、コンテンツ名は、要求メッセージの宛先アドレスと呼ばれ得る。次いで、サーバは、適切なコンテンツ見つけて、そのコンテンツをルータ１５０ａ−ｅを介してクライアントデバイス１１０に返送するために、要求を使用することができる。
【００２７】
一例を挙げると、図１は、要求メッセージ１５０をルータ１４０ａに送信するクライアントデバイス１１０を示している。要求メッセージ１５０は、宛先アドレス「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」を含み得る。したがって、メッセージ１５０は、サーバ１３０によって格納されたコンテンツを要求することができる。要求メッセージ１５０を受信すると、ルータ１４０ａは様々なルーティング操作を実行して、要求メッセージ１５０をその最終宛先に送るために、要求メッセージ１５０をどのルータまたは「ネクストホップ」に転送するべきか決定することができる。この機能を提供するために、ルータ１４０ａ−ｅは分散されたルーティングテーブルを実装することができる。このように、各ルータ１４０ａ−ｅは、ルータ１４０ａ−ｅのこのセットに関連付けられるルーティングテーブルの全体ではなく、ルーティングテーブルの一部を含み得る。たとえば、各ルータ１４０ａ−ｅは、ルータ１４０ａ−ｅが利用可能なルーティングレコードを格納し得るために割り当てられたアドレスの範囲を割り当てられてよい。様々な代替実施形態では、ネットワーク１００は、ルータではなく、分散されたルーティングテーブルの一部を含む、１つまたは複数のネットワークデバイスを含み得る。たとえば、ネットワーク１００は、分散されたルーティングテーブルの一部を格納する専用サーバ（図示せず）を含むことができ、ルータ１４０ａ−ｅがメッセージを転送する際に他のルータ１４０ａ−ｅに補助を提供できる方法と類似の方法でメッセージを転送する際に、ルータ１４０ａ−ｅを補助する。
【００２８】
様々な代替実施形態では、要求メッセージ１５０は、要求されたコンテンツの特定の「チャンク」をアドレス指定することができる。たとえば、要求メッセージ１５０は、「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ／ｃｈｕｎｋ２」を要求することができる。特定のコンテンツアイテムのすべてのチャンクが同じ場所に格納される、様々なそのような実施形態では、メッセージを処理する際に使用される宛先アドレスはチャンク識別子を省略することができ、したがってルーティングは「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」に基づく。たとえば、コンテンツが複数のサーバ間で分散され得る実施形態などの、様々な代替実施形態では、ルータは、チャンク識別子に基づいてルーティングすることもでき、したがってこの例では、ルーティングは「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ／ｃｈｕｎｋ２」に基づく。
【００２９】
要求メッセージ１５０を受信すると、ルータ１４０ａは、どのルータ１４０ａ−ｅに宛先アドレス「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」を割り当てるかを決定することができる。割り当てられたルータを識別した後、ルータ１４０ａはそのルータに、要求メッセージ１５０の適切なネクストホップを問い合わせることができる。たとえば、ルータ１４０ａは、アドレス「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」がルータ１４０ｅに割り当てられたと決定して、それに応答して、ルータ１４０ｅに適切なネクストホップを問い合わせることができる。
【００３０】
ネクストホップの問合わせを受信すると、ルータ１４０ａ−ｅは、問合せを送信したネットワークデバイスに関する適切なネクストホップを決定するために、ローカルに格納されたルーティングテーブルを調べることができる。ネクストホップの選択は、メッセージが転送されるべき現在のデバイスのインターフェースの選択を包含し得る。様々な代替実施形態では、ネクストホップの選択は、次のルータ、または現在のデバイスから転送されたメッセージを受信するための他のデバイスの選択を包含し得る。したがって、あるルータのネクストホップは、別のルータのネクストホップではない場合がある。上記からの例を継続すると、ルータ１４０ａに関するメッセージ１５０の適切なネクストホップは、ルータ１４０ｄである。しかしながら、メッセージ１５０がルータ１４０ｅによって転送される場合、そのルータに関するネクストホップはルータ１４０ａである。メッセージの適切なネクストホップを決定した後、問い合わせされたルータは、ネクストホップの表示を含むメッセージを問い合わせしているルータに返すことができる。たとえば、ルータ１４０ｅは、ルータ１４０ｄがメッセージ１５０ａのネクストホップであることを表示しているメッセージをルータ１４０ａに送信することができる。次いで、ルータ１４０ａは、ルータ１４０ｄへのメッセージ１５０の送信に進むことができ、その処理は、今度はルータ１４０ａではなくルータ１４０ｄに関して、それ自体を繰り返すことができる。
【００３１】
上記の説明は、ネットワーク１００の例示的操作の概要として提示され、いくつかの点で簡素化および／または抽象化を構成し得る。次に、例示的ネットワーク１００、およびルータ１４０ａ−ｅのうちの１つまたは複数のより詳細な操作を、図２−図１０を参照して提示する。
【００３２】
図２は、メッセージをルーティングするための例示的ネットワークデバイス２００を示している。例示的ネットワークデバイス２００は、例示的ネットワーク１００のルータ１４０ａ−ｅのうちの１つまたは複数に対応し得る。ネットワークデバイス２００はいくつかの点で抽象化されてよく、ネットワークデバイス２００は、様々なメモリ、ならびに、たとえばマイクロプロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、および／または特定用途向け集積回路（ＡＳＩＣ）などの１つまたは複数のプロセッサなどの様々なハードウェアコンポーネントを含み得ることが、当業者には明らかである。図示されるように、ネットワークデバイス２００は、ネットワークインターフェース２１０、ルートキャッシュ２２０、委任マネージャ２３０、ペンディングルートテーブル２４０、最長プレフィックスマッチ（ＬＰＭ）ブロック２５０、および／またはルートマネージャ２６０を含み得る。
【００３３】
ネットワークインターフェース２１０は、ハードウェア、ならびに／あるいは、クライアントデバイス、サーバ、および／またはルータなどの少なくとも１つの他のネットワークデバイスと通信するように構成された機械可読記憶媒体上で符号化された実行可能命令を含むインターフェースでよい。ネットワークインターフェースは、複数のデバイスと通信することを可能にするための、複数の物理ポートを含み得る。様々な実施形態では、ネットワークインターフェース２１０は、イーサネット(登録商標)、フレームリレー、ＡＴＭ、および／またはＰＰＰなどのプロトコルによって通信する１つまたは複数のインターフェースを含み得る。操作中、ネットワークインターフェースは、要求メッセージ、コンテンツメッセージ、ルート更新メッセージ、問合せメッセージ、および／または応答メッセージなどの様々なメッセージを送受信することができる。様々な実施形態では、ネットワークインターフェース２１０は、複数の物理インターフェースを含み得る。さらに、いくつかのそのような実施形態では、別のインターフェースを別のタイプのメッセージに関連付けることができる。たとえば、ノードは、コンテンツメッセージを送受信するために使用されるインターフェースとは別の、問合せおよび応答メッセージを送受信するための専用インターフェースを含み得る。
【００３４】
ルートキャッシュ２２０は、キャッシュされたルートを格納して利用するように構成された機械可読記憶媒体上に、ハードウェアおよび／または実行可能命令を含み得る。たとえば、ルートキャッシュは、様々な宛先アドレスに関連するキャッシュエントリを格納する、ＳＲＡＭなどの比較的高速なメモリを含み得る。各キャッシュエントリは、キャッシュされた宛先アドレスごとに、ネットワークデバイス２００に関する適切なネクストホップを指定することができる。様々な代替実施形態では、キャッシュエントリは、ネットワークデバイス２００以外のネットワークデバイスに関するネクストホップをさらに指定することができる。ルートキャッシュ２２０は、キャッシュ内のエントリを選択して保持するために、様々なキャッシュ技法を使用することができる。ルートキャッシュ２２０の例示的コンテンツは、以下で図３を参照してより詳細に説明する。
【００３５】
ルートキャッシュ２２０は、ネットワークインターフェース２１０を介して他のネットワークデバイスに転送されるべき様々なメッセージを受信することができる。たとえば、ルートキャッシュ２２０は、ネットワークインターフェース２１０を介して要求メッセージおよびコンテンツメッセージを受信することができる。そのようなメッセージを受信すると、ルートキャッシュ２２０は、メッセージから宛先アドレスを抽出して、ルートキャッシュ２２０が、抽出されたアドレスに関連するキャッシュエントリを格納するかどうかを決定することができる。格納する場合、ルートキャッシュは、一致するキャッシュエントリによって識別されたように、ネットワークインターフェース２１０を介して、受信されたメッセージを適切なネクストホップに単純に転送することができる。たとえば、一致するキャッシュエントリは、メッセージが送信されるべき複数の発信ポートのうちの１つを識別することができる。宛先アドレスについてのキャッシュヒットがない場合、ルートキャッシュ２２０は、さらなる処理のために、受信されたメッセージを委任マネージャ２３０に渡すことができる。
【００３６】
委任マネージャ２３０は、宛先アドレスがネットワークデバイス２００または別のネットワークデバイスに「割り当てられている」かどうかを決定するように構成された機械可読記憶媒体上に、ハードウェアおよび／または実行可能命令を含み得る。本明細書で使用されるように、ネットワークデバイスが、宛先アドレスに関して、他のノードの代わりにルート更新の管理および最長プレフィックス一致操作の実行を担当する場合、宛先アドレスをそのネットワークデバイスに割り当てることができる。たとえば、以下で図１０を参照してより詳細に説明するように、委任マネージャ２３０は、ハッシュキーを生成するために、宛先アドレスにハッシュ関数を実行することができる。次いで、委任マネージャ２３０は、このハッシュキーと、ネットワークデバイス２００および他の様々なネットワークデバイス間に割り当てられた様々なネットワークデバイス識別子（ＩＤ）とを比較することができる。様々な実施形態では、この目的で、各デバイスに単一のデバイス識別子を割り当てることができる。この比較に基づいて、委任マネージャは、ハッシュキーに最も近くに一致するネットワークデバイスＩＤが、宛先アドレスが割り当てられたネットワークデバイスを指すことを決定することができる。このネットワークデバイスＩＤがネットワークデバイス２００を指す場合、委任マネージャ２３０は、適切なネクストホップをローカルに決定するために、宛先アドレスをＬＰＭブロック２５０に転送することができる。あるいは、委任マネージャ２３０は、一致するネットワークデバイスＩＤが指すネットワークデバイスから適切なネクストホップを要求するために、宛先アドレスを含む問合せメッセージを生成して送信することができる。次いで、委任マネージャ２３０は、メッセージをペンディングルートテーブル２４０に格納して、適切なネクストホップの受信を待つ間、さらなるメッセージに進むことができる。ＬＰＭブロック２５０または遠隔ネットワークデバイスのいずれかから、ネットワークインターフェース２１０を介して適切なネクストホップを受信すると、委任マネージャは、ペンディングルートテーブル２４０からメッセージを取り出して、ネットワークインターフェース２１０を介してそのメッセージをネクストホップに転送することができる。
【００３７】
委任マネージャ２３０は、メッセージを送信する際に他のネットワークデバイスを補助するようにさらに構成され得る。たとえば、委任マネージャ２３０は、ネットワークインターフェース２１０を介して他のネットワークデバイスから問合せメッセージを受信することができる。それに応じて、委任マネージャは、以下で説明するように、宛先アドレス、および問い合わせしているネットワークデバイスのネットワークデバイスＩＤを抽出して、さらなる処理のためにこの情報をＬＰＭブロック２５０に渡すことができる。問い合わせしているネットワークデバイスに関するネクストホップを受信すると、委任マネージャは、決定されたネクストホップを含む応答メッセージを生成して送信することができる。様々な代替実施形態では、ＬＰＭブロック２５０に質問する前に、ルートキャッシュ２２０は、問い合わせしているネットワークデバイスに関する適切なネクストホップを表示するキャッシュエントリが存在するかどうかを決定することができる。さらに、様々な代替実施形態では、委任マネージャ２３０は、問合せメッセージがローカルに処理されるべきかどうかを決定するために、および問合せメッセージがネットワークデバイス２００に誤って到着した可能性があるかどうか決定するために、上述の処理に類似した処理を実行することができる。次いで、委任マネージャ２３０は、当業者に知られている様々な方法によって、そのような誤った問合せメッセージを処理することができる。
【００３８】
ペンディングルートテーブル２４０は、ペンディングルート操作に関する情報を格納するデバイスでよい。したがって、ペンディングルートテーブル２４０は、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、および／または類似の記憶媒体などの機械可読記憶媒体を含み得る。たとえば、ペンディングルートテーブル２４０は、委任マネージャ２３０がネクストホップの決定を待つ間にメッセージを格納するＳＲＡＭを含み得る。ペンディングルートテーブル２３０の例示的コンテンツは、以下で図４を参照してより詳細に説明する。
【００３９】
最長プレフィックスマッチ（ＬＰＭ）ブロック２５０は、所与の宛先アドレスおよびネットワークデバイスＩＤの適切なネクストホップを決定するように構成された機械可読記憶媒体上に、ハードウェアおよび／または実行可能命令を含み得る。たとえば、ＬＰＭブロック２５０は、分散されたルーティングテーブルの格納された部分に対して最長プレフィックスマッチングを実行することができる。ルーティングテーブルまたはその一部からネクストホップを識別する任意の方法がＬＰＭブロック２５０によって使用され得ることが、当業者には明らかであろう。たとえば、様々な代替実施形態では、ＬＰＭブロックは、単に最長プレフィックスマッチではなく、完全なアドレス一致に基づいてネクストホップを識別することができる。図示されるように、ＬＰＭブロック２５０は、フィルタ２５２、ルートレトリバー２５４、および／またはルートテーブル２５６を含み得る。
【００４０】
フィルタ２５２は、ルートテーブル２５６のうちの可能な結果のフィールドを絞り込むために予備的な処理を実行するように構成された機械可読記憶媒体上に、ハードウェアおよび／または実行可能命令を含み得る。様々な代替実施形態では、フィルタ２５２は、所与の宛先アドレスの最長マッチングプレフィックスの長さを推定するように構成され得る。たとえば、フィルタ２５２は、それぞれがルートテーブルに格納された共通の長さのプレフィックスから構築される、いくつかのブルームフィルタを格納することができる。したがって、あるブルームフィルタを、長さが「１」のすべての格納されたプレフィックスから構築することができ、第２のブルームフィルタを、長さが「２」のすべての格納されたプレフィックスから構築することができ、以下同様である。やはり宛先アドレスに一致する最長プレフィックスに関連付けられるブルームフィルタは、最長マッチングプレフィックスの推定された長さを表示することができる。次いで、フィルタ２５２は、最長プレフィックスマッチのさらなる解決のために、この推定された長さをルートレトリバーに渡すことができる。フィルタ２５２の様々な実装形態が可能であってよいことが、当業者には理解されよう。したがって、フィルタ２５２は、ブルームフィルタなどのソフトウェアに、および／または３値連想メモリ（ＴＣＡＭ）などのハードウェアに実装され得る。フィルタ２５２の例示的コンテンツは、以下で図５を参照してより詳細に説明する。
【００４１】
ルートレトリバー２５４は、最長マッチングプレフィックスに基づいて宛先アドレスと一致するルーティングレコードを識別するように構成された機械可読記憶媒体上に、ハードウェアおよび／または実行可能命令を含み得る。様々な実施形態では、ルートレトリバー２５４は、宛先アドレスの最長マッチングプレフィックスが見つかるまで、最長プレフィックスを格納するルーティングレコードから開始して、ルートテーブルに格納された、いくつかのルーティングレコードを通じて繰り返すことができる。フィルタ２５２が最長マッチングプレフィックスの推定された長さをルートレトリバー２５４に渡すと、ルートレトリバー２５４は、代わりに、同じ長さのプレフィックスを有するレコードを通じて反復を開始することができ、より長いプレフィックスを有するレコードをスキップする。したがって、フィルタ２５２が最長マッチングプレフィックスの長さを推定すると、ルートレトリバーは、より長いプレフィックスを有する任意のレコードをスキップすることによって検索されるべきレコードの範囲を絞り込むことができる。一致するルーティングレコードを見つけた後、ルートレトリバーは、ネットワークデバイスＩＤに関連する適切なネクストホップを抽出して、さらなる処理のためにこのネクストホップを委任マネージャ２３０に返すことができる。
【００４２】
ルートテーブル２５６は、ネットワークデバイス２００に割り当てられたプレフィックスのための知られているルーティングパスを格納するデバイスでよい。したがって、ルートテーブル２５６は、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、および／または類似の記憶媒体などの機械可読記憶媒体を含み得る。たとえば、ルートテーブル２５６は、プレフィックスおよび関連するネクストホップを含む様々なルーティングレコードを格納するＤＲＡＭを含み得る。ルートテーブル２５６の例示的コンテンツは、以下で図６を参照してより詳細に説明する。
【００４３】
ルートマネージャ２６０は、ルート更新メッセージを受信して処理するように構成された機械可読記憶媒体上に、ハードウェアおよび／または実行可能命令を含み得る。様々な実施形態によれば、ルータ１４０ａ−ｅなどのネットワークデバイスのグループは、分散されたルートテーブルを生成するために、ルート学習プロトコルを実装することができる。たとえば、ネットワークデバイスのそのようなグループは、ＢＧＰ、ＯＳＰＦ、ＲＩＰ、および／または他のルーティングプロトコルを実装することができる。そのようなプロトコルによれば、ネットワークデバイスは、そのネットワークデバイスを通じて到達され得る宛先アドレスを広告するために、ルート更新メッセージを送信することができる。たとえば、図１に戻ると、ルータ１４０ｄは、宛先「／ＪＤＯＥ／ＰＡＰＥＲＳ／ＰａｐｅｒＡ．ｐｄｆ」、「／ＪＤＯＥ／ＰＡＰＥＲＳ／ＰａｐｅｒＢ．ｐｄｆ」、および／または「ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」がルータ１４０ｄを介して到達され得ることを示すルート更新メッセージを、ルータ１４０ａおよび／またはルータ１４０ｂに送信することができる。ルート更新メッセージを受信すると、ルートマネージャ２６０が、ルート更新メッセージがローカルに、または遠隔デバイスで処理されるべきかどうかを決定するために、宛先アドレスを抽出して、コンテンツ名を委任マネージャ２３０に渡すことができる。上述のように、委任マネージャ２３０は、宛先アドレスが割り当てられるネットワークデバイスの決定と類似した方法によって、この決定を行うことができる。応答を受信した後、ルートマネージャ２６０は、まず委任マネージャがルート更新メッセージはローカルに処理されるべきであると決定したかどうかを決定することができる。ルート更新メッセージはローカルに処理されるべきであると決定した場合、ルートマネージャは、当業者に知られている任意の方法によって、ルート更新メッセージを考慮してルートテーブル２５６を更新することができる。たとえば、ルートマネージャは、広告された宛先アドレスの適切なプレフィックス、およびネクストホップとして、更新メッセージが到着したときの送信したデバイスの表示または更新メッセージが到着したときの経由したローカルインターフェースの表示を含む、新しいルーティングレコードをルートテーブル２５６内に作成することができる。
【００４４】
一方、委任マネージャ２３０が、ルート更新メッセージは別のネットワークデバイスで処理されるべきである決定すると、ルートマネージャは、宛先およびネクストホップを含む委任された更新メッセージを構築して、別のネットワークデバイスに送信することができる。ルートマネージャ２６０は、他のネットワークデバイスから受信された類似の委任された更新メッセージを処理するようにさらに構成され得る。たとえば、ルートマネージャ２６０が、ネットワークインターフェース２１０を介して委任された更新メッセージを受信すると、ルートマネージャ２６０は、メッセージから宛先アドレスおよびネクストホップを抽出して、更新するべき適切なルーティングレコードをルートテーブル２５６に問い合わせることができる。そのようなルーティングレコードを見つけるか、新しいレコードを作成した後、ルートマネージャ２６０は、適切なマッチングプレフィックス、および／またはそのネットワークデバイスのネットワークデバイスＩＤに関連して他のネットワークデバイスに関連する表示されたネクストホップを格納することができる。その後、ネットワークデバイス２００は、格納されたプレフィックスに一致するアドレス宛てのメッセージをルーティングする際に、他のネットワークデバイスを補助することができる。
【００４５】
図３は、ルートキャッシュデータを格納するための例示的データ構成３００を示している。データ構成３００は、たとえば、オブジェクト、アレイ、リンクされたリスト、ツリー、および／またはハッシュテーブルなどの様々なデータ構造を使用して実装され得る。データ構成３００は、たとえば、例示的ネットワークデバイス２００のルートキャッシュ２２０に格納され得る。データ構成３００は、コンテンツ名フィールド３１０および／またはネクストホップフィールド３２０などの、いくつかのフィールドを含み得る。
【００４６】
コンテンツ名フィールド３１０は、コンテンツ名または他の宛先アドレスを格納することができる。様々な実施形態では、コンテンツ名フィールド３１０は、コンテンツ名のいくつかのコンポーネントを格納することができる。たとえば、コンテンツ名がＢコンポーネント全体を含む場合、コンテンツ名フィールド３１０はＢ−１コンポーネントを含み得る。いくつかの実施形態では、これはコンテンツ名フィールド３１０に格納する前に、コンテンツ名から任意のチャンク識別子を単に取り除くステップを伴い得る。様々な実施形態では、コンテンツ名フィールド３１０に格納された値は、平文形式で格納されてもよく、ハッシュ値として格納されてもよい。コンテンツ名フィールド３１０がハッシュ値を格納する様々な実施形態では、ネットワークデバイス２００のルートキャッシュ２２０は、キャッシュヒットがあるかどうかを決定するために、受信されたメッセージの宛先アドレスのハッシュ操作を実行して、一致するハッシュ値をデータ構成３００に問い合わせるように構成され得る。さらなる修正は、当業者には明らかであろう。ネクストホップフィールド３２０は、コンテンツ名フィールド３１０に格納された関連付けられる値と一致するメッセージのネクストホップとして機能する発信インターフェースまたはネットワークデバイスの識別を格納することができる。
【００４７】
一例を挙げると、データ構成３００は、例示的ネットワーク１００のルータ１４０ａのルートキャッシュのコンテンツを表示することができる。キャッシュエントリ３３０は、宛先アドレス「／ＪＤＯＥ／ＰＡＰＥＲＳ／ＰａｐｅｒＡ．ｐｄｆ」を含むメッセージが、ルータ１４０ｄに対応し得るネクストホップ「ｄ」に転送されるべきであることを表示することができる。キャッシュエントリ３４０は、宛先アドレス「／ＪＤＯＥ／ｎｏｔｅｓ．ｔｘｔ」を含むメッセージが、ルータ１４０ｂに対応し得るネクストホップ「ｂ」に転送されるべきであることを表示することができる。データ構成３００は、多数のさらなるキャッシュエントリ３００を含み得る。
【００４８】
図４は、ペンディングルートテーブルを格納するための例示的データ構成４００を示している。データ構成４００は、たとえば、オブジェクト、アレイ、リンクされたリスト、ツリー、および／またはハッシュテーブルなどの様々なデータ構造を使用して実装され得る。データ構成４００は、たとえば、例示的ネットワークデバイス２００のペンディングルートテーブル２４０に格納され得る。データ構成４００は、コンテンツ名フィールド４１０、パケットフィールド４２、委任フィールド４３０、および／またはタイムスタンプフィールド４４０などの、いくつかのフィールドを含み得る。
【００４９】
コンテンツ名フィールド４１０は、コンテンツ名または他の宛先アドレスを格納することができる。様々な実施形態では、コンテンツ名フィールド３１０は、コンテンツ名のいくつかのコンポーネントを格納することができる。たとえば、コンテンツ名がＢコンポーネント全体を含む場合、コンテンツ名フィールド３１０はＢ−１コンポーネントを含み得る。いくつかの実施形態では、これはコンテンツ名フィールド３１０に格納する前に、コンテンツ名から任意のチャンク識別子を単に取り除くステップを伴い得る。様々な実施形態では、コンテンツ名フィールド４１０に格納された値は、平文形式で格納されてもよく、ハッシュ値として格納されてもよい。コンテンツ名フィールド４１０がハッシュ値を格納する様々な実施形態では、ネットワークデバイス２００の委任マネージャ２３０は、一致するペンディングルートがあるかどうかを決定するために、受信されたメッセージの宛先アドレスのハッシュ操作を実行して、一致するハッシュ値をデータ構成４００に問い合わせるように構成され得る。さらなる修正は、当業者には明らかであろう。
【００５０】
パケットフィールド４２０は、ルート操作をペンディングするメッセージを格納することができる。たとえば、委任マネージャ２３０が、ＬＰＭブロック２５０か別のネットワークデバイスのいずれかから適切なネクストホップの表示を受信すると、委任マネージャは、適切なペンディングルートを見つけて、パケットフィールド４２０に格納されたメッセージをネクストホップに転送することができる。委任フィールド４３０は、最長プレフィックスマッチングがローカルに、または遠隔ネットワークデバイスで実行されているかどうかに関する表示を格納することができる。タイムスタンプフィールド４４０は、データ構成４００にエントリが加えられた時、および／またはローカルデバイスで関連するメッセージが受信された時を表示するタイムスタンプを格納することができる。これらの値の様々な使用は、当業者には明らかであろう。
【００５１】
一例を挙げると、ペンディングルートレコード４５０は、「＜Ｐａｃｋｅｔ１４９＞」が「１３３０７７４８１５」の時間に受信されて、「／ＴＵＸ／ｎｏｔｅｓ．ｔｘｔ」の宛先アドレスを含むことを表示することができる。このパケットは、現在適切なネクストホップに関するローカル決定を待っている場合がある。別の例を挙げると、ペンディングルートレコード４６０は、パケット「＜Ｐａｃｋｅｔ１５０＞」が「１３３０７７４８１８」の時間に受信されて、「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」の宛先アドレスを含むことを表示することができる。このパケットは、現在適切なネクストホップに関する遠隔デバイスによる決定を待っている場合がある。様々な実施形態では、ペンディングルートレコード４６０は、例示的システム１００のメッセージ１５０に対応し得る。データ構成４００は、多数のさらなるペンディングルートレコード４７０を含み得る。
【００５２】
図５は、フィルタを格納するための例示的データ構成５００を示している。データ構成５００は、たとえば、オブジェクト、アレイ、リンクされたリスト、ツリー、および／またはハッシュテーブルなどの様々なデータ構造を使用して実装され得る。データ構成５００は、たとえば、例示的ネットワークデバイス２００のフィルタ２５２に格納され得る。データ構成５００は、プレフィックス長フィールド５１０、および／またはフィルタフィールド５２０などの、いくつかのフィールドを含み得る。
【００５３】
プレフィックス長フィールド５１０は、関連フィルタを構築する際に使用されるプレフィックスの長さを表示することができ、フィルタフィールド５２０はフィルタ自体を格納することができる。一例を挙げると、フィルタレコード５３０は、長さ「１」のプレフィックスが現在評価されている宛先アドレスと一致し得るかどうかを決定するために、フィルタ「０ｘ９１Ｂ２０６」を使用することができることを表示することができる。別の例を挙げると、フィルタレコード５４０は、長さ「２」のプレフィックスが現在評価されている宛先アドレスと一致し得るかどうかを決定するために、フィルタ「０ｘＣ４Ｅ２３１」が使用することができることを表示することができる。データ構成５００は、多数のさらなるフィルタフィールド５５０を含み得る。
【００５４】
様々な実施形態では、フィルタフィールド５２０に格納されたフィルタはブルームフィルタでよい。したがって、各フィルタは、関連する長さのそれぞれの格納されたプレフィックスに１つまたは複数のハッシュ関数を実行することによって構築され得る。たとえば、「０ｘ９１Ｂ２０６」は、ローカルに格納された長さ「１」のプレフィックスに複数のハッシュ関数を実行することによって生成された可能性がある。次いで、これらのフィルタは、ローカルデバイスが、宛先アドレスと一致する、関連する長さのプレフィックスを有するルートレコードを格納することは可能かどうかを決定するために、宛先アドレスから生成されたハッシュ値と比較され得る。次いで、最長プレフィックス長に関連付けられる、一致するブルームフィルタは、宛先アドレスと一致する、最長のローカルに格納されたプレフィックスに関する推定を表示することができる。さらなる最長プレフィックスマッチングを実行する際に、ネットワークデバイスは、推定された長さよりも長い任意のプレフィックスをスキップすることができる。
【００５５】
図６は、ルートテーブルを格納するための例示的データ構成６００を示している。データ構成６００は、たとえば、オブジェクト、アレイ、リンクされたリスト、ツリー、および／またはハッシュテーブルなどの様々なデータ構造を使用して実装され得る。データ構成６００は、たとえば、例示的ネットワークデバイス２００のルートテーブル２５６に格納され得る。データ構成６００は、コンテンツプレフィックスフィールド６１０、およびいくつかのネクストホップフィールド６２０、６３０、６４０などの、いくつかのフィールドを含み得る。
【００５６】
コンテンツプレフィックスフィールド６１０は、コンテンツ名または他の宛先アドレス、および／あるいはそれらの一部を格納することができる。様々な実施形態では、コンテンツプレフィックスフィールド６１０に格納された値は、平文形式で格納されてもよく、ハッシュ値として格納されてもよい。コンテンツプレフィックスフィールド６１０がハッシュ値を格納する様々な実施形態では、ネットワークデバイス２００のルートレトリバー２５４は、一致するルートがあるかどうかを決定するために、受信されたメッセージの宛先アドレスのハッシュ操作を実行して、一致するハッシュ値をデータ構成６００に問い合わせるように構成され得る。さらなる修正は、当業者には明らかであろう。
【００５７】
ネクストホップフィールド６２０は、特定のネットワークデバイスに関するネクストホップを格納することができる。たとえば、図示されるように、ネクストホップフィールド６２０は、ネットワークデバイスＩＤ「０ｘＡ２」に関連付けられるネットワークデバイスに関するネクストホップを格納することができる。ネクストホップフィールド６３０は、別のネットワークデバイスに関するネクストホップを格納することができる。たとえば、図示されるように、ネクストホップフィールド６３０は、ネットワークデバイスＩＤ「０ｘ３５」に関連付けられるネットワークデバイスに関するネクストホップを格納することができる。データ構成６００は、さらなるネットワークデバイスに対応するための、多数のさらなるネクストホップフィールド６４０を含み得る。
【００５８】
一例を挙げると、ルートレコード６５０は、ネットワークデバイスが、ネットワークデバイスＩＤ「０ｘＡ２」に関連付けられるメッセージを転送する場合、プレフィックス「／ＪＤＯＥ」が最長マッチングプレフィックスであるメッセージがネクストホップ「ａ」に転送されるべきであり、ネットワークデバイスが、ネットワークデバイスＩＤ「０ｘ３５」に関連付けられるメッセージを転送する場合、ネクストホップ「ｂ」に転送されるべきであることを表示することができる。別の例を挙げると、ルートレコード６６０は、ネットワークデバイスが、ネットワークデバイスＩＤ「０ｘＡ２」に関連付けられるメッセージを転送する場合、プレフィックス「／ＪＤＯＥ／ＶＩＤＥＯＳ」が最長マッチングプレフィックスであるメッセージがネクストホップ「ａ」に転送されるべきであり、ネットワークデバイスが、ネットワークデバイスＩＤ「０ｘ３５」に関連付けられるメッセージを転送する場合、ネクストホップ「ｂ」に転送されるべきであることを表示することができる。データ構成６００は、多数のさらなるルートレコード６７０を含み得る。
【００５９】
図７は、メッセージを転送するための例示的方法７００を示している。方法７００は、ルータ、またはネットワークデバイス２００などの他のネットワークデバイスのコンポーネントによって実行され得る。方法７００は、ルートキャッシュ２２０、委任マネージャ２３０、および／またはＬＰＭブロック２５０の間で実行され得る。
【００６０】
方法７００は、ステップ７０５で始まり、ネットワークデバイスがネクストホップに転送されるべきメッセージを受信することができるステップ７１０に進むことができる。ステップ７１５で、ネットワークデバイスは、メッセージからコンテンツ名またはその一部を抽出することができ、次いでステップ７２０で、コンテンツ名が任意のキャッシュエントリと一致するかどうかを決定する。様々な実施形態では、抽出されたコンテンツ名部分は、第１のＢ−１コンポーネントを含むことができ、コンテンツ名はＢコンポーネント長である。キャッシュヒットがある場合、ネットワークデバイスは、ステップ７２５で、一致するキャッシュエントリから適切なネクストホップを読み出すことができ、ステップ７７５に進む。あるいは、方法７００は、ステップ７２０から、ネットワークデバイスまたは遠隔ネットワークデバイスがコンテンツ名を割り当てられているかどうかを決定するために、ネットワークデバイスが委任機能を実行することができるステップ７３０に進むことができる。そのような委任処理を実行する例示的方法は、以下で図１０を参照してより詳細に説明する。
【００６１】
次に、ステップ７３５で、ネットワークデバイスは、将来の転送のために、ペンディングルートテーブルにメッセージを加えることができる。次いで、ステップ７４０で、ネットワークデバイスは、委任手順の結果が、コンテンツ名の適用可能なルートレコードがローカルに格納されること、あるいはコンテンツ名がローカルデバイスに割り当てられることを示すかどうかを決定することができる。そのように示す場合、ネットワークデバイスは、ステップ７４５で、ローカルに格納されたルートテーブルに対して最長プレフィックスマッチングを実行することによって適切なローカル処理を実行するために進むことができる。一致するルートレコードを発見した後、方法７００はステップ７５０に進むことができ、適切なネクストホップを決定するために、ネットワークデバイスは一致するルートレコードを使用することができる。ステップ７５５で、ネットワークデバイスは、将来のアクセスを容易にするために、一致するエントリをキャッシュすることができる。一致するエントリをキャッシュすることは、ルートレコード全体をルートキャッシュに格納すること、または、ルートレコードに格納された値のうちの少なくともいくつかに基づいて新しいキャッシュエントリを生成することを含み得る。次いで、方法７００はステップ７７５に進むことができる。
【００６２】
一方、ステップ７４０で、ネットワークデバイスが、コンテンツ名は遠隔ネットワークデバイスに格納されると決定する場合、方法７００はステップ７６０に進むことができる。ステップ７６０で、ネットワークデバイスは、適切なネクストホップを委任されたルータに問い合わせることができる。たとえば、ネットワークデバイスは、コンテンツ名を含む問合せメッセージを構築して、問合せメッセージを送信して、応答を待つことができる。様々な実施形態では、ネットワークデバイスは、この応答を待つ間、他のメッセージの処理を継続することができる。応答を受信した後、ネットワークデバイスは、応答に基づいて適切なネクストホップを決定することができる。次に、ステップ７７０で、ネットワークデバイスは、将来のアクセスを容易にするために、応答をキャッシュすることができる。一致するエントリをキャッシュすることは、応答全体をルートキャッシュに格納すること、または、応答に格納された値のうちの少なくともいくつかに基づいて新しいキャッシュエントリを生成することを含み得る。次いで、方法７００はステップ７７５に進むことができる。
【００６３】
ステップ７７５で、ネットワークデバイスは、ステップ７２５、ステップ７５０、および／またはステップ７６５で決定されたネクストホップにメッセージを転送することができる。次いで、方法７００はステップ７８０に進んで、終了することができる。
【００６４】
図８は、メッセージを転送する際に別のデバイスを補助するための例示的方法８００を示している。方法８００は、ルータ、またはネットワークデバイス２００などの他のネットワークデバイスのコンポーネントによって実行され得る。方法８００は、委任マネージャ２３０、および／またはＬＰＭブロック２５０の間で実行され得る。
【００６５】
方法８００は、ステップ８０５で開始して、ネットワークデバイスが別のネットワークデバイスから適切なネクストホップについての問合せを受信することができるステップ８１０に進むことができる。次いで、ステップ８１５で、ネットワークデバイスは、コンテンツメッセージおよび／または問合せメッセージの受信に関連する他の情報から、コンテンツ名および問い合わせしているデバイスＩＤを抽出することができる。次に、ステップ８２０で、ネットワークデバイスは、ルートテーブルに格納された一致するレコードを見つけるために、最長プレフィックスマッチングを実行することができる。このステップは、方法７００のステップ７４５と類似していてよい。一致するルートレコードを見つけた後、ネットワークデバイスは、問い合わせしているデバイスのデバイスＩＤと一致したルートレコードのエントリに基づいてネクストホップを決定することができる。次いで、ネットワークデバイスは、応答メッセージを構築して、問い合わせしているデバイスに送信することができる。この応答は、ステップ８２５で決定されたネクストホップ、および要求された宛先アドレスを含み得る。次いで、方法８００はステップ８３５に進んで、終了することができる。
【００６６】
図９は、ルート更新を処理するための例示的方法９００を示している。方法９００は、ルータ、またはネットワークデバイス２００などの他のネットワークデバイスのコンポーネントによって実行され得る。方法９００は、委任マネージャ２３０、および／またはルートマネージャ２６０の間で実行され得る。
【００６７】
方法９００は、ステップ９０５で開始して、ネットワークデバイスがルート更新メッセージを受信することができるステップ９１０に進むことができる。次に、ステップ９１５で、ネットワークデバイスは、更新メッセージに関連付けられるプレフィックスおよび／またはネクストホップを計算することができる。たとえば、ネットワークデバイスは、メッセージから宛先アドレスまたはプレフィックスを抽出して、更新メッセージが受信されたインターフェースを確認することができる。様々な代替実施形態では、ステップ９１５で、ネットワークデバイスはプレフィックスを計算せず、代わりに宛先アドレスを単に抽出してよい。そのような実施形態では、プレフィックスは、ステップ９３０またはステップ９３５で計算してよく、ルートレコードを格納する遠隔のネットワークデバイスによって計算してよい。
【００６８】
ステップ９２０で、ネットワークデバイスまたは遠隔ネットワークデバイスがコンテンツ名を割り当てられているかどうかを決定するために、ネットワークデバイスは、委任機能を実行することができる。そのような委任処理を実行する例示的方法は、以下で図１０を参照してより詳細に説明する。様々な実施形態では、ステップ９２０は、方法７００のステップ７３０に対応し得る。
【００６９】
ステップ９２５で、ネットワークデバイスは、委任機能の結果が、ルート更新メッセージ内の情報がローカルに格納されるべきであることを示すかどうかを決定することができる。そのように示す場合、方法９００は、アドレスプレフィックス、ネクストホップ、およびネットワークデバイスのデバイスＩＤを含むために、ネットワークデバイスが、新しいルートレコードを生成するか、既存のルートレコードを更新することができるステップ９３０に進むことができる。あるいは、方法９００は、ネットワークデバイスがアドレスプレフィックス、ネクストホップ、およびネットワークデバイスのデバイスＩＤを適切な遠隔ネットワークデバイスに格納することができるステップ９３５に進むことができる。これは、委任された更新メッセージを構築して、遠隔ネットワークデバイスに送信するステップを含み得る。次いで、方法９００はステップ９４０に進んで、終了することができる。
【００７０】
図１０は、ルーティング操作を委任するための例示的方法１０００を示している。方法１０００は、ルータ、またはネットワークデバイス２００などの他のネットワークデバイスのコンポーネントによって実行され得る。方法１０００は委任マネージャ２３０によって実行され得る。
【００７１】
方法１０００は、ステップ１００５から開始して、ネットワークデバイスがコンテンツ名の各コンポーネントをハッシュすることができるステップ１０１０に進むことができる。様々な実施形態では、ステップ１０１０で、ネットワークデバイスはコンテンツ名をいくつかのコンポーネントに分けて、各コンポーネントを個別にハッシュして、次いでコンポーネントを結合してハッシュキーを形成することができる。様々な実施形態では、この組合せは、コンテンツ名内のコンポーネントの順序によって、ハッシュされたコンポーネントのそれぞれを連結するステップを含み得る。たとえば、ネットワークデバイスは、コンテンツ名「／ＪＤＯＥ／ＶＩＤＥＯＳ／ａｂｃ．ｍｐｇ」を、「ＪＤＯＥ」、「ＶＩＤＥＯＳ」、および「ａｂｃ．ｍｐｇ」の３つのコンポーネントに分けることができる。次いで、ネットワークデバイスは、値「０ｘＡ２」、「０ｘ２１」、および「０ｘ８Ｅ」を生成するために、各コンポーネントを個別にハッシュすることができる。最後に、ネットワークデバイスは、ハッシュキー「０ｘＡ２２１８Ｅ」を生成するために、値を連結することができる。
【００７２】
次に、ステップ１０１５で、ネットワークデバイスは、ヌル、無限大、または何らかの他の高い値に変えられる「最短距離」を設定することによって、手順を開始することができる。次いで、ステップ１０２０で、ネットワークデバイスは、評価するためにルータＩＤを取り出すことができる。ステップ１０２５で、ネットワークデバイスは、現在のルータＩＤがハッシュキーにどのくらい近いかを決定することができる。たとえば、ネットワークデバイスは、ハッシュキーと同じ長さになるように、まずネットワークＩＤの右にゼロの数を埋めることができる。ネットワークデバイスは、ハッシュキーとネットワークデバイスＩＤとの間のＸＯＲ機能の実行によって「距離」を決定することができる。たとえば、ハッシュキーが「０ｘＡ２２１８０」で、ルータＩＤが「０ｘ３５」の場合、この距離は「０ｘ９７２１８０」でよい。別の例を挙げると、ハッシュキーが「０ｘＡ２」の場合、この距離は「０ｘ００２１８０」でよい。
【００７３】
現在のネットワークデバイスＩＤの距離を決定した後、ネットワークデバイスは、ステップ１０３０で、値と「最短距離」変数とを比較することによって、現在の距離が新しい最短距離かどうかを決定することができる。現在の距離が新しい最短距離であると決定した場合、ネットワークデバイスは、「最短距離」変数を更新して、現在のデバイスＩＤを現在の「最短デバイスＩＤ」として記録することができる。次に、ステップ１０４０で、ネットワークデバイスは、処理するべきデバイスＩＤが他にないかどうかを決定することができる。さらなるデバイスＩＤが残っている場合、方法１０００はステップ１０２０にループバックすることができる。あるいは、方法１０００は、ネットワークデバイスが、方法１０００を呼び出す要素によって使用するために、「最短デバイスＩＤ」変数に格納されたデバイスＩＤを返すことができるステップ１０４５に進むことができる。したがって、返されたデバイスＩＤは、方法７００および／または方法９００のために特定の宛先アドレスが割り当てられたデバイスを表示することができる。次いで、方法１０００はステップ１０５０に進んで、終了することができる。
【００７４】
様々な代替実施形態では、方法１０００は、１つまたは複数のネットワークデバイスが反応しない、あるいは使用できない時に使用されるべきデバイスアドレスが割り当てられる１つまたは複数の「バックアップデバイス」を決定することができる。様々なそのような実施形態によれば、方法１０００は、Ｎ個の最短ネットワークデバイスＩＤを識別することができ、ここでＮは１よりも大きい数である。そのような機能性を実装するための様々なさらなる修正は、当業者には明らかであろう。たとえば、ネットワークデバイスは、委任された更新メッセージを各バックアップデバイスに転送するようにさらに構成され得る。さらに、ネットワークデバイスは、アドレスが割り当てられたプライマリデバイスに問い合わせることができない場合、バックアップデバイスのうちの１つに問い合わせるように構成され得る。
【００７５】
上記によれば、様々な実施形態によって、メッセージをルーティングするために大きなルーティングテーブルを効率的に使用することが可能になることが明らかなはずである。たとえば、複数のネットワークデバイス間でルーティングテーブルを分散することによって、ネクストホップルックアップのタスクをそのようなデバイス間で分散することができ、それによって大きなルーティングテーブルをサポートするための効率的な手段を提供する。さらに、いくつかのネットワークデバイスのそれぞれに宛先アドレスのサブセットを割り当てることによって、ネクストホップルックアップが効率的かつ信頼性の高い方法で委任され得る。
【００７６】
上記の説明から、本発明の様々な例示的実施形態は、ハードウェアおよび／またはファームウェアに実装され得ることが明らかなはずである。さらに、様々な例示的実施形態は、機械可読記憶媒体に格納された命令として実装することができ、本明細書で詳細に説明した操作を実行するために、少なくとも１つのプロセッサによって読み出して実行することができる。機械可読記憶媒体は、パーソナルコンピュータやラップトップコンピュータ、サーバ、または他のコンピューティングデバイスなどの、機械によって読出し可能な形式で情報を格納するための任意のメカニズムを含み得る。したがって、有形および非有形の機械可読記憶媒体は、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、および類似の記憶媒体などの機械可読記憶媒体を含み得る。
【００７７】
本明細書の任意のブロック図は、本発明の原理を組み込む例示的回路の概念図を表すことが、当業者には理解されるべきである。同様に、任意のフローチャート、流れ図、状態遷移図、擬似コード、および同様のものは、機械可読媒体において実質的に表され、コンピュータまたはプロセッサが明示的に図辞されているか否かにかかわらず、コンピュータまたはプロセッサによってそのように実行される、様々な処理を表すことが理解されよう。
【００７８】
様々な例示的実施形態を、その特定の例示的態様を特に参照して詳細に説明してきたが、本発明は他の実施形態が可能であり、その詳細は様々な明確な点で修正が可能であることが理解されるべきである。当業者には容易に明らかなように、本発明の趣旨および範囲内にとどまりながら、変形および修正を行うことができる。したがって、前述の開示、説明、および図は、説明のみを目的とするものであり、いかなる意味においても本発明を限定するものではない。本発明は、特許請求の範囲によってのみ定義される。
【図１】
2015512231.tif 000003
【図２】
2015512231.tif 000004
【図３】
2015512231.tif 000005
【図４】
2015512231.tif 000006
【図５】
2015512231.tif 000007
【図６】
2015512231.tif 000008
【図７】
2015512231.tif 000009
【図８】
2015512231.tif 000010
【図９】
2015512231.tif 000011
【図１０】
2015512231.tif 000012
【国際調査報告】
2015512231.tif 000013
2015512231.tif 000014