(57)【要約】【課題】長さが変化する識別子を有するパケットを処理する。【解決手段】入力ポートにおいてパケットを受信し（３００）、パケットによって表されたＨＳＶＬＩを固定長キーに変換する（３１０）。固定長キーを使用する最長プレフィックス合致探索エンジンにおける１つ以上の最長プレフィックス合致探索に基づいて転送情報を取得し（３２０）、転送情報に基づいてパケットを出力ポートに転送する（３３０）。【選択図】図３
2010178342.tif 000002
【特許請求の範囲】
【請求項１】
階層的に構造化された可変長識別子（ＨＳＶＬＩ）を有するパケットを転送するための、プロセッサを含むコンピュータで実現される方法であって、
ＨＳＶＬＩが一片のコンテンツを表し、階層的に構造化されていて、最も一般的なレベルから最も特定的なレベルまで順序付けられた連続する構成要素を備えており、それぞれの識別子の長さが一定でない前記ＨＳＶＬＩを有するパケットを入力ポートにおいて受信することと、
前記ＨＳＶＬＩを固定長キーに変換することと、
前記固定長キーを使用する最長プレフィックス合致探索エンジンによって１つ以上の最長プレフィックス合致に基づく転送情報を取得することと、
前記転送情報に基づいて前記パケットを出力ポートに転送することとを備える、方法。
【請求項２】
前記ＨＳＶＬＩを前記固定長キーに変換することは、
前記固定長キーをｃ個のセグメントｓ１、・・・、ｓｃに分割することと、
前記ＨＳＶＬＩの初めのｃ−１個の構成要素に関する構成要素ハッシュをセグメントｓ１、・・・、ｓｃ−１で表すことと、
前記ＨＳＶＬＩの残りの構成要素に関するハッシュをセグメントｓｃで表すこととを備える、請求項１に記載の方法。
【請求項３】
前記ｃ個のセグメントの長さは等しくなく、それぞれのセグメントの長さは動的に再構成され得る、請求項２に記載の方法。
【請求項４】
前記ｃ個のセグメントの長さ、各セグメントにハッシュされたＨＳＶＬＩ構成要素の数、および／または少なくとも前記ＨＳＶＬＩの初めの構成要素の１つ以上に基づいて前記固定長キーに算術的に結合される値を動的に決定することを更に備える、請求項２に記載の方法。
【請求項５】
前記最長プレフィックス合致探索エンジンはインターネットプロトコル（ＩＰ）ルータである、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般的にはデータネットワーク上での通信を容易にすることに関する。特に本開示は、階層的に構造化された可変長識別子をデータを転送することに順応させるように最長プレフィックス合致探索エンジンを適応させるための方法に関する。
【背景技術】
【０００２】
インターネットプロトコル（ＩＰ）転送器は、一般的にルータと呼ばれる。ルータは、複数の入力ポート（ネットワークインターフェース）の１つでパケットを受信する。次に、ルータは、パケットのあて先アドレスに基づいて転送されるための出力ポートを見つけるため、最長プリフィックス合致探索エンジンを利用して、通常は入力ポートとは異なる当該出力ポートにパケットを送信する。最長プリフィックス合致探索エンジンは最長プリフィックス合致を用いる。なぜなら、２以上の探索エンジンエントリーはあて先アドレスに合致するからである。
なお、先行技術としては特許文献１に開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許出願第１２／１２３，３４４号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
現在のルータ技術は、ＩＰアドレスの長さに固定されたＩＰパケットについてよく機能するが、長さが変化する識別子を有するパケットを処理することはできない。
【課題を解決するための手段】
【０００５】
一実施形態は、階層的に構造化された可変長識別子（ＨＳＶＬＩ）を有するパケットを受信するシステムを提供する。ＨＳＶＬＩは、一片のコンテンツを表し、最も一般的なレベルから最も特定的なレベルまで順序付けられた連続する構成要素の階層的構造を表す。それぞれの識別子の長さは一定ではない。動作時にシステムは、ＨＳＶＬＩを固定長キーに変換する。引き続いてシステムは、固定長キーを使用する最長プレフィックス合致探索エンジンによる１つ以上の最長プレフィックス合致に基づいて転送情報を取得する。次に、システムは、転送情報に基づいてパケットを出力ポートに転送する。
【０００６】
ある幾つかの実施形態では、ＨＳＶＬＩを固定長キーに変換することは、固定長キーをｃ個のセグメントｓ１、・・・、ｓｃに分割することと、ＨＳＶＬＩの初めのｃ−１個の構成要素に関する構成要素ハッシュをセグメントｓ１、・・・、ｓｃ−１で表すことと、ＨＳＶＬＩの残りの構成要素に関するハッシュをセグメントｓｃで表すこととを含む。
【０００７】
ある幾つかの実施形態では、ｃ個のセグメントの長さは等しくなく、それぞれのセグメントの長さは動的に再構成され得る。
【０００８】
ある幾つかの実施形態では、システムは、ｃ個のセグメントの長さ、各セグメントにハッシュされたＨＳＶＬＩ構成要素の数、および／または少なくともＨＳＶＬＩの初めの構成要素の１つ以上基づいて固定長キーと算術的に結合される値を動的に決定する。
【０００９】
ある幾つかの実施形態では、最長プレフィックス合致探索エンジンは、インターネットプロトコル（ＩＰ）ルータである。
【００１０】
ある幾つかの実施形態では、固定長キーは、インターネットプロトコル・バージョン４（ＩＰｖ４）アドレスまたはインターネットプロトコル・バージョン６（ＩＰｖ６）アドレスである。
【００１１】
ある幾つかの実施形態では、転送情報は、少なくとも１つの出力ポートを含む。
【００１２】
ある幾つかの実施形態では、階層構造は、グローバルにルート指定可能な名前と組織名とバージョン識別子とダイジェストとのうちの１つ以上を含む。
【図面の簡単な説明】
【００１３】
【図１】一実施形態による、パケットがＨＳＶＬＩを有する例示的ネットワークを示す図である。
【図２】一実施形態による、ＨＳＶＬＩを有するパケットを転送するための例示的システムのアーキテクチャを示す図である。
【図３】一実施形態による、ＨＳＶＬＩを有するパケットを転送するプロセスを例示するフローチャートを提示する図である。
【図４】一実施形態による、ＨＳＶＬＩを固定長キーに変換するプロセスを例示するフローチャートを提示する図である。
【図５】一実施形態による、幾つかの異なる固定長キーに変換された例示的ＨＳＶＬＩを示す図である。
【図６】一実施形態による、ＨＳＶＬＩを有するパケットを転送するための例示的装置を提示する図である。
【発明を実施するための形態】
【００１４】
これらの図では、同様の参照数字は、同じ図要素を指す。
【００１５】
既存の最長プレフィックス合致探索エンジンは、比較的短い固定長のアドレスを処理できるだけである。本発明の実施形態は、既存の最長プレフィックス合致探索エンジンをより長い可変長パケット識別子に適応させることを含む。より具体的には本発明の実施形態は、長い可変長パケット識別子を既存の探索エンジンで使用可能な多数の短いキーにハッシュし、その結果、既存のハードウエア・ビルディングブロックを使用することによってコンテンツ中心ネットワークにおける高速転送を容易にすることを含む。本発明の実施形態は、インターネットプロトコル・バージョン４（ＩＰｖ４）アドレスおよびインターネットプロトコル・バージョン６（ＩＰｖ６）アドレスといった固定長アドレスを用いて最長プレフィックス探索エンジンを使用するＩＰ（インターネットプロトコル）ルータにおいてＨＳＶＬＩを有するパケットの転送を可能にできる。
【００１６】
コンテンツ中心ネットワークは、コンテンツ搬送に新しい手法をもたらす。コンテンツが移動する端末間会話としてアプリケーションレベルでネットワークトラヒックが見られる代わりに、コンテンツはそれに与えられた名前にある程度基づいて要求または返却され、またネットワークは、プロバイダから消費者にコンテンツをルート指定する責任を有する。コンテンツは、テキスト、画像、ビデオおよび／またはオーディオといった任意の形のデータを含む、通信システムで搬送され得るデータを含む。消費者とプロバイダは、ネットワークの内側または外側のコンピュータまたは自動化プロセスにおける人であり得る。このようなネットワークでは一片のコンテンツは、コンテンツ全体またはコンテンツのそれぞれの部分を指すことが可能である。例えば、新聞記事は、データパケットとして具現された多数片のコンテンツによって表現される可能性がある。一片のコンテンツはまた、認証データ、創作データ、コンテンツ所有者などといった情報で、一片のコンテンツを記述または増補するメタデータに関連付けられ得る。
【００１７】
コンテンツ中心のネットワークでは、従来のＩＰネットワークとは異なり、パケットは、構造化あるいは非構造化され得るＨＳＶＬＩによって識別され得る。例えば、「ａｂｃｄ／ｂｏｂ／ｐａｐｅｒｓ／ｃｃｎ／ｎｅｗｓ」は、コンテンツの名前であることが可能であり、対応するパケットを識別する、すなわち「ＡＢＣＤ」と名づけられた組織における「Ｂｏｂ」と名づけられたユーザに関する新聞の「ｃｎｎ」収集物から「ｎｅｗｓ」記事を識別する。
【００１８】
一片のコンテンツを要求するためにノードは、コンテンツの名前によってコンテンツへの関心を表明する（例えば、放送する）。一片のコンテンツへの関心は、コンテンツの名前または識別子によるコンテンツに関する問合せであり得る。コンテンツは、ネットワークにおいて利用可能な場合、コンテンツを記憶する任意のノードからコンテンツへの関心を表明したノードに戻るようにルート指定される。ルート指定インフラストラクチャは、情報を有する可能性の高い有望なノードに関心を知的に伝播し、それから関心が移動した経路に沿って利用可能なコンテンツを引き戻す。
【００１９】
図１は、本発明の一実施形態によるネットワークの例示的アーキテクチャを示す。この例では、ネットワーク１８０は、ノード１００〜１４５を備える。ネットワークにおける各ノードは、１つ以上の他のノードに接続されている。ネットワーク接続１８５はこのような接続の一例である。ネットワーク接続は実線で示されているが、各線はまた、１つのノードをもう１つのノードに接続し得るサブネットワークまたはスーパーネットワークを表し得る。ネットワーク１８０は、ローカルネットワーク、スーパーネットワークまたはサブネットワークであり得る。これらのネットワークの各々は、１つのネットワーク内のノードが他のネットワーク内のノードに到達できるように相互接続され得る。ネットワーク接続は、広帯域、無線、電話、衛星または任意のタイプのネットワーク接続であり得る。ノードは、コンピュータシステム、ユーザを表すエンドポイントおよび／または関心を生成し得る、またはコンテンツを創作し得るデバイスであり得る。
【００２０】
本発明の一実施形態によれば消費者は、一片のコンテンツへの関心を生成し、それからこの関心をネットワーク１８０内のノードに送り得る。一片のコンテンツは、ネットワークの内側または外側に位置し得る出版業者またはコンテンツプロバイダによってネットワーク１８０内のノードに記憶され得る。例えば、図１において一片のコンテンツへの関心は、ノード１０５から発生する。コンテンツがノードにおいて利用可能でない場合、関心は最初のノードに接続された１つ以上のノードに流れる。例えば、図１において、関心は利用可能なコンテンツを有さないノード１１５に流れる（関心フロー１５０）。次に、関心は、ノード１０５から再びコンテンツを有さないノード１２５に流れる（関心フロー１５５）。それから関心は、利用可能なコンテンツを有するノード１３０に流れる（関心フロー１６０）。それからコンテンツの流れは、コンテンツが配信されるノード１０５にこのコンテンツが到達するまで経路を引き返す（コンテンツフロー１６５、１７０および１７５）。認証といった他のプロセスも、コンテンツの流れに含まれ得る。
【００２１】
ネットワーク１８０において、コンテンツホルダー（ノード１３０）と関心発生ノード（ノード１０５）との間の経路内の如何なる数の中間ノード（ノード１００〜１４５）でも、コンテンツがネットワークに亘って移動するときにコンテンツのローカルコピーをキャッシュすることに関与し得る。キャッシュすることは、ローカルにキャッシュされたコンテンツへのアクセスを暗に共有することによって他の加入者の近傍に位置する第２の加入者のためのネットワーク負荷を軽減する。
【００２２】
従来のパケット転送は、ノード（またはノードのインタフェース）に割り当てられたアドレスに基づいている。ＩＰアドレス指定では、アドレスの最初の部分がネットワークを識別し、後の部分がこのネットワーク内のサブネットワークを識別し、アドレスの終端部がサブネットワーク内の特定のホストを識別するように、アドレスの階層的分割が使用される。この構成は、インターネットが世界的サイズにまで拡大できるように任務委譲され、それによって配信される一意のアドレスを割り当てる責任を可能にする。これはまた、パケットを出力ポートに転送するときにＩＰルータが処理することを必要とする情報の量を限定することによって拡張を可能にする。
【００２３】
一実施形態では、パケットは、階層構造を有するＨＳＶＬＩによって識別される。ＨＳＶＬＩの階層構造は、ＩＰアドレスの階層構造より優れた幾つかの利点を提供する。このような識別子は、サブネットマスクを含むＩＰルート指定テーブルエントリーを暗に介するよりむしろ、明らかに名前を介して構造を記述できる。したがって、ＨＳＶＬＩでは、階層における指名誤りは検査によって検出され得るが、ＩＰサブネットマスク誤りはパケットを誤ったアドレスにルート指定する可能性があり、検出がより困難である。
【００２４】
一般に、ＩＰ転送器における探索エンジンは、２つ以上の探索エンジンエントリーが宛て先アドレスに合致できるという理由で最長プレフィックス合致を使用する。最も特定的なエントリー−最も長いサブネットマスクを有するエントリー−は、最長プレフィックス合致と呼ばれる。例えば、探索エンジンが下記のＩＰｖ４エントリー：１９２．１６８．２０．１６／２８および１９２．１６８．０．０／１６を有すると仮定する。着信パケットの宛て先アドレス１９２．１６８．２０．１９は、両方のエントリーに合致する。しかしながら、最長プレフィックス合致は、サブネットマスク「／２８」が他のエントリーのサブネットマスク「／１６．」より長いので、１９２．１６８．２０．１６／２８である。サブネットマスクはその対応するアドレスに合致するときに使用される先行ビット（すなわちサブネットマスク内で「１」にセットされるビット）を指定することに留意されたい。より多くの先行ビットが「１」にセットされるほど、合致はより特定的になる。
【００２５】
最長プレフィックス合致は、データグラムの宛て先アドレスがローカル環境に依存して異なる「解像度」で解釈されることを可能にする。例えば、宛て先１３．１．６４．９３（ａｌｐｈａ．ｐａｒｃ．ｘｅｒｏｘ．ｃｏｍ）から遠く離れたところでは、データグラムを最も近いネット１３（Ｘｅｒｏｘ）境界ゲートウェイに移動させるサブネットアドレス「１３／８」（サブネットマスク２５５．０．０．０に対応する）のためのＩＰｖ４エントリーが存在するだけの可能性がある。この境界ゲートウェイでは、データグラムを最も近いサブネット１３．１（ｐａｒｃ．ｘｅｒｏｘ．ｃｏｍ）境界ゲートウェイに移動させるサブネットアドレス「１３．１／１６」およびおそらくは「１３．２／１６」、・・・（サブネットマスク２５５．２５５．０．０に対応する）のためのエントリーが存在する可能性がある。このゲートウェイでは、データグラムをＰＡＲＣの１３．１．６４サブネットに移動させるサブネットアドレス「１３．１．６４／２４」（サブネットマスク２５５．２５５．２５５．０に対応する）のためのエントリーが存在する可能性があり、以下同様である。最長プレフィックス合致は、高解像度ローカル情報（／１６および／２４プレフィックス）が同じルート指定テーブル内の低解像度グローバル情報（／８プレフィックス）を無効にすることを可能にする。
【００２６】
最長プレフィックス合致は、完全合致とは対照的にアドレスの複数部分間への分割が（グローバル）ネットワークに亘って変化することを可能にし、広く変化するトポロジーのために柔軟性をサポートする。本明細書で説明されたＨＳＶＬＩはまた、指名責任の任務委譲と最小限の転送状態とを可能にするために階層的である。しかしながら、ＩＰアドレス（および他の従来のネットワークアドレス）は比較的短い。例えば、ＩＰｖ４アドレスは、人間の理解のために１９２．９．２００．６のように書かれ得るが内部的には常に３２ビット数であるのに、ＩＰｖ６アドレスは１２８ビットの長さである。
【００２７】
既存のＩＰルータのすべてにおいて、処理されるアドレスは固定長である。したがって、従来のアドレスとは異なり、本明細書で説明されたパケット識別子の長さは一定ではない。実際にＨＳＶＬＩの個別の構成要素は、任意の長さを有し得る。このようなＨＳＶＬＩは、明確に区切られた構成要素を有することができ、任意のバイト列を含むことができ、人間可読文字に限定されない。
【００２８】
最長プレフィックス合致探索は、ＨＳＶＬＩを有するパケットの転送に有益である。例えば、「／ｐａｒｃ／ｈｏｍｅ／ｓｍｅｔｔｅｒｓ」への関心は、「／ｐａｒｃ／ｈｏｍｅ／ｓｍｅｔｔｅｒｓ／ｔｅｓｔ．ｔｘｔ」と「／ｐａｒｃ／ｈｏｍｅ／ｓｍｅｔｔｅｒｓ／ｂａｒ．ｔｘｔ」の両者（すなわちこれら両方の名前で識別されるパケット）に合致する。名前構成要素の数という点から、最長合致は、これが最も特定的であるという理由で最善と考えられる。本発明の実施形態は、可変長パケット識別子を用いて最長プレフィックス合致探索を実行できるように既存の最長プレフィックス合致探索エンジンを適応させるための機構を提供する。
【００２９】
図２は、一実施形態による、ＨＳＶＬＩを有するパケットを転送するための例示的システムの概要を示す。ＨＳＶＬＩを有するパケットを転送するためのシステム２００は、パケット受信器２２０と変換器２４０と転送情報取得器２６０とパケット転送器２８０とを含む。パケット受信器２２０は、入力ポートからパケット２１０を受信する。パケット２１０は、一片のコンテンツを表し、最も一般的なレベルから最も特定的なレベルまで順序付けられた連続する構成要素の階層構造を表すＨＳＶＬＩ２３０を含む。例えば、ＨＳＶＬＩは、「ａ」が最も一般的なレベルであって「ａ／ｂ／ｃ／ｄ」が最も特定的なレベルである「ａ／ｂ／ｃ／ｄ」である可能性がある。
【００３０】
次に、変換器２４０は、入力ＨＳＶＬＩ２３０を取得して固定長キー２５０を生成する。変換器２４０は、ＨＳＶＬＩ２３０を最長プレフィックス合致探索エンジンによって使用可能な固定長フォーマットに変換する。転送情報取得器２６０は、後でパケット転送器２８０に入力される転送情報２７０を生成するために固定長キー２５０を使用する。転送情報は、パケット転送器２８０がパケットを転送する少なくとも１つの出力ポートを表し得る。ノードは、他のノードに接続される１つ以上の入力ポートと出力ポートとを含む。一般に、システム（ノードに常駐し得る）は、ノード間のパケット移動時間またはホップ数といったある幾つかの基準を最適化する出力ポートを選択しようと試みる。典型的な最長プレフィックス合致転送器は、固定長アドレスの最長プレフィックス合致に基づいてパケットを転送するということに留意されたい。これとは対照的に、本明細書で説明された転送器はアドレスよりむしろＨＳＶＬＩに基づいてパケットを転送する。本発明の実施形態は、典型的な最長プレフィックス合致転送エンジンが可変長パケット識別子について最長プレフィックス合致を実行することを可能にする。
【００３１】
図３は、一実施形態による、ＨＳＶＬＩを有するパケットを転送するプロセスを例示するフローチャートを提示する。動作時にシステムは、入力ポートにおいてパケットを受信する（動作３００）。パケットは、最も一般的なレベルから最も特定的なレベルまで順序付けられた連続する構成要素の階層構造を表すＨＳＶＬＩを含む。階層構造における構成要素は、グローバルにルート指定可能な名前、組織名、バージョン識別子、署名、ダイジェスト、出版業者、巡回冗長検査、構成要素数の観点からの長さ、１構成要素当たりのビット数またはバイト数、あるいは寿命時間（ＴＴＬ）を含み得る。
【００３２】
いったんシステムがパケットを受信すると（動作３００）、システムはパケットによって表されたＨＳＶＬＩを固定長キーに変換する（動作３１０）。ＨＳＶＬＩは最も一般的なレベルにおける構成要素から始まる１つ以上の連続する構成要素を含むことに留意されたい。例えば、「ａ／ｂ」は「ａ／ｂ／ｃ／ｄ」のプレフィックスである。この例では、「ａ」は最も一般的なレベルにあり、「ａ」、「ｂ」、「ｃ」および「ｄ」は連続する構成要素である。
【００３３】
次に、システムは、固定長キーを使用する最長プレフィックス合致探索エンジンにおける１つ以上の最長プレフィックス合致探索に基づいて転送情報を取得する（動作３２０）。引き続いて、システムは、転送情報に基づいてパケットを出力ポートに転送する（動作３３０）。システムは、パケットが転送され得るポートとして入力ポートを除外し得る。これは、ＨＳＶＬＩに合致するコンテンツを含むノードへの最短経路ルートが入力ポートを通って引き返すルートではあり得ないからである。
【００３４】
一実施形態では、転送器は、パケットを転送する前にコンテンツ名の一部としてＴＴＬ値を減少させ得る。ＴＴＬは、パケットが循環状態に留まり得る期間またはホップの数の限度である。ＴＴＬがゼロに達すると、パケットは廃棄され得る。したがってＴＴＬは、循環における配信不能パケットの数を減らすことができる。転送器はまた、パケットの何らかの変化の後で転送の前にチェックサム（例えば、巡回冗長検査合計）を再計算できる。一般に、転送器は、転送する前にパケットの如何なる態様も修正できる。
【００３５】
図４は、一実施形態による、ＨＳＶＬＩを変換するプロセスを例示するフローチャートを提示する。最初にシステムは、固定長キーをｃ個のセグメントｓ１、・・・、ｓｃに分割する（動作４００）。次に、システムは、ＨＳＶＬＩの初めのｃ−１個の構成要素に関するハッシュを計算してこれらのハッシュ値をセグメントｓ１、・・・、ｓｃ−１に置く（動作４１０）。引き続いてシステムは、ＨＳＶＬＩの残りの構成要素についてハッシュを計算して、このハッシュ値をセグメントｓｃに置く（動作４２０）。
【００３６】
図５は、一実施形態による、幾つかの異なる固定長キーに変換された例示的ＨＳＶＬＩを示す。図５は、ＨＳＶＬＩ５００を「ａ／ｂ／ｃ／ｄ」として示す。ＨＳＶＬＩ５００は、多くの異なる仕方で変換され得て、図５はＨＳＶＬＩが変換され得るほんの僅かの仕方を例示している。図５に示されたすべての変換は、固定長３２ビットキー（３２ビットキー５１０）を使用する。ＩＰｖ６の１２８ビットアドレスといった他の固定長キーも可能である。
【００３７】
変換５２０は、１つだけのセグメント、すなわちｃ＝１に分割された固定長キーに対応する。ｃ＝１であるからｃ−１＝０であることに留意されたい。したがって、変換５２０は、初めのｃ−１（０）個の構成要素に関する構成要素ハッシュを示していない。関数「ｈ（ａ／ｂ／ｃ／ｄ）」は、「ａ／ｂ／ｃ／ｄ」から導出されたハッシュ値である「「ａ／ｂ／ｃ／ｄ」のハッシュ」の簡略表記である。ｃ＝１であるから変換５２０は、３２ビットすべてが「ｈ（ａ／ｂ／ｃ／ｄ）」を記憶するために使用されることを示している。
【００３８】
変換５３０は、２つのセグメント、すなわちｃ＝２に分割された固定長キーに対応する。この変換ではｃ−１＝１であることに留意されたい。したがって、変換５３０は、１８ビットで記憶される初めのセグメントによって表される「ａ」に関する構成要素ハッシュ（すなわち「ｈ（ａ）」）を示す。変換５３０はまた、１４ビットで記憶される最後のセグメントによって表されるＨＳＶＬＩの残り構成要素に関するハッシュ（すなわち「ｈ（ｂ／ｃ／ｄ）」）を示す。
【００３９】
変換５４０は、３つのセグメント、すなわちｃ＝３に分割された固定長キーに対応する。この変換ではｃ−１＝２であることに留意されたい。したがって、変換５４０は、１２ビットで記憶される初めのセグメントによって表される「ａ」に関する構成要素ハッシュ（すなわち「ｈ（ａ）」）と１２ビットで記憶される第２のセグメントによって表される「ｂ」に関する構成要素ハッシュ（すなわち「ｈ（ｂ）」）とを示す。変換５４０はまた、８ビットで記憶される最後のセグメントによって表されるＨＳＶＬＩの残り構成要素に関するハッシュ（すなわち「ｈ（ｃ／ｄ）」）を示す。
【００４０】
変換５５０は、４つのセグメント、すなわちｃ＝４に分割された固定長キーに対応する。この変換ではｃ−１＝３であることに留意されたい。したがって、変換５５０は、１４ビットで記憶される初めのセグメントによって表される「ａ」に関する構成要素ハッシュ（すなわち「ｈ（ａ）」）と４ビットで記憶される第２のセグメントによって表される「ｂ」に関する構成要素ハッシュ（すなわち「ｈ（ｂ）」）と６ビットで記憶される第３のセグメントによって表される「ｃ」に関する構成要素ハッシュ（すなわち「ｈ（ｃ）」）とを示す。変換５５０はまた、８ビットで記憶される最後のセグメントによって表されるＨＳＶＬＩの残り構成要素に関するハッシュ（すなわち「ｈ（ｄ）」）を示す。
【００４１】
セグメントの長さ（すなわちビット数）は等しい必要はなく、それぞれのセグメントの長さは動的に再構成され得ることに留意されたい。例えば、変換５３０は１８ビットで記憶された「ｈ（ａ）」を示し、変換５４０は１２ビットで記憶された「ｈ（ａ）」を示し、変換５５０は１４ビットで記憶された「ｈ（ａ）」を示す。第１の構成要素が異なるアプリケーションにおいて生じる異なる構成要素構造の一部であり得ることを示すために、変換５３０〜５５０における「ｈ（ａ）」に関してビット数は変化する。例えば、変換５３０では、第１の構成要素ハッシュは可能な値の１８ビットを有する。変換５４０では、第１の構成要素ハッシュは可能な値の１２ビットを有する。変換５５０では、第１の構成要素ハッシュは可能な値の１４ビットを有する。一般に、各構成要素ハッシュに関連するビット数は少なくとも、その転送ポイントにおいて必要とされる各構成要素に関する可能な値の数と各構成要素のエントロピーとに基づき得る。
【００４２】
最長合致転送の「ローカル情報のより高い解像度」という特徴を保持するために、セグメントの数とセグメントの長さはＨＳＶＬＩの初めの構成要素の１つ以上を使用して動的に決定され得ることに留意されたい。ｃの選択は、転送テーブルが一杯に占められているときに探索エントリーの集合について統計を計算することから決定され得るように、この転送ポイントにおいて必要とされる識別子の分布によって影響され得る。一実施形態では、ｃの選択と固定長キー内のビットの割当ては、ＨＳＶＬＩの初めの方の部分のコンテンツに基づいて動的に決定され得る。これは、ある範囲のプレフィックス（例えば、「ｐａｒｃ．ｃｏｍ」のような単一の値だけを含むプレフィックス）が別の仕方で処理されることを可能にする。その結果、ＨＳＶＬＩから固定長キーへの写像は、プレフィックスの異なるクラスに関連するエントロピー分布に敏感にされ得る。例えば、イントラネット名に対応するＨＳＶＬＩは、後方のＨＳＶＬＩ構成要素がより意味のある情報を保持するので、後方の構成要素に大部分のビットが割り当てられるようにされるべきである（例えば、図５の変換５５０）。これとは対照的に、外部の名前に対応するＨＳＶＬＩは、変化の大部分が異なるエントリーを区別するために使用される初めのＨＳＶＬＩ構成要素に大部分のビットが割り当てられるようにされるべきである（例えば、図５の変換５３０）。テーブルインスタンスごとに（１負荷当たりのテーブルごとに）単一の写像方式を有することよりむしろ、方式はパケットが着信するときに各パケットの初めの構成要素（またはプレフィックスの多数の構成要素）を最初に吟味することによって決定され得る。流れの点から言えばこのプロセスは、主要なテーブル探索のために使用される固定長キーを取得するために使用される写像の前に、または写像の一部として実行される特殊な探索と見られ得る。
【００４３】
更に、ビットが通信線を離れるときに増加するようにＨＳＶＬＩ変換の多くを行うことは可能である。既存の最長プレフィックス合致実現形態の一部は増加するように動作でき、したがって、ＨＳＶＬＩパケットの「カットスルー」転送を実行できる。他の一部はアドレス／キー全体を必要とするが、本発明では、ＨＳＶＬＩ・固定長キー変換はなお、探索が起きる前に、ビットが受信されたときに実行され得る。
【００４４】
探索エンジンは、下記のもの、すなわち、３進コンテンツアドレス指定可能メモリ（ＴＣＡＭ）、ツリー構造およびブルームフィルタのうちの１つ以上を含み得る。より一般的には、最長プレフィックス合致に適応し得る如何なる探索エンジンも使用可能である。
【００４５】
コンテンツアドレス指定可能メモリ（ＣＡＭ）は、ＣＡＭがすべてのコンテンツ場所に亘って並行して入力値に関して探索して、１サイクル内で関連値との合致を返すことができるように、各格納場所が１ビットごとにコンパレータを有するメモリである。ＴＣＡＭは、ある程度の合致を可能にするように記憶場所に各値ビットに関するケア／ドントケアビットを記憶する。これは、各エントリーがワードの初めのあるビット数における完全合致にセットされることが可能であって残りのビットに関しては「ドントケア」であるので、現在の「無階級」ＩＰアドレス指定のために必要とされるプレフィックス合致を可能にする。多数の合致プレフィックスの場合には一般に、最初の合致が返されるので、最長プレフィックス合致は漸減するプレフィックス長の順にＴＣＡＭをロードすることによって達成され得る。
【００４６】
ツリー構造は、最長プレフィックス合致をツリー（トリーとしても知られている）内のプレフィックスとして実現するために使用され得る。ツリーの基本形はプレフィックス内のすべての文字（アルファベットが０，１であるＩＰアドレスコンテンツにおけるすべてのビット）に関するノードブランチを有する。アドレスが通信線から（１ビットずつ）復号されるので、探索はツリーを使用して実行され得る。今までのところ最長合致は、完全合致が存在しない場合に最長プレフィックス合致が迅速に発見され得るように、ツリーが横断されるときスタック上に保持され得る。
【００４７】
基数トリーでは、各レベルにおけるサブツリーを選択するために、ある一定数のビットが使用され得る。例えば、８ビット基数によれば、初めの８ビットは根の可能な２５６個のサブツリーの１つをインデックス付けし、次の８ビットは第２のレベルにおける可能な２５６個のサブツリーの１つをインデックス付けする。
【００４８】
パトリシアツリーは、異なるエントリー間の弁別器であるこれらのビットだけを表すノードを有する最小エントロピープレフィックス探索ツリーである。各ノードは、異なるプレフィックスエントリーを区別するこのレベルにおいて吟味すべきビット位置を識別する。
【００４９】
ブルームフィルタは、ｍビットのビットアレイと、１つの要素からｍ個のアレイ位置（一様な分布からランダムに選択されたような）の１つに写像するｋ個の異なるハッシュ関数とを含む。初めに、ブルームフィルタのすべてのビットは、０にセットされる。１つの要素をブルームフィルタに加えることは、ｋ個のアレイ位置を取得するためにｋ個のハッシュ関数の各々によって要素についてハッシュすることを含む。これらすべての位置におけるビットの各々は１にセットされる。１要素のメンバーシップを決定すること（すなわちこの要素がブルームフィルタを構成する集合内に存在するかどうかを検査すること）は、ｋ個の位置を取得するためにｋ個のハッシュ関数の各々で要素をハッシュすることを含む。これらの位置のすべてが１を表す場合、要素は集合内に存在する。そうでなければ要素は、集合内に存在しない。ブルームフィルタは、偽陽性という結果をもたらし得る（すなわち、集合内に存在しない項目に関しては陽性結果が取得され得る）が、偽陰性という結果にはなり得ない（すなわち、ブルームフィルタは項目が集合のメンバーでないときに明確に断言し得る）。各プレフィックス長に関して１フィルタの１グループのブルームフィルタは、並行して問い合わせられて、合致を発見する各フィルタのためにハッシュテーブル内で２次的探索に進むことができる。極めて少数のエントリーを有し得る初めの少数のプレフィックス長に関して初期直接探索アレイといった異なるプレフィックス分布に適応するための種々の最適化が使用され得る。
【００５０】
図６は、一実施形態による、ＨＳＶＬＩを有するパケットを転送するための例示的装置を示す。
【００５１】
ＨＳＶＬＩを有するパケットを転送するための装置６００は、プロセッサ６１０、メモリ６２０、記憶装置６３０、パケット受信機構６４０、ＨＳＶＬＩ変換機構６５０、転送情報取得機構６６０、およびパケット転送機構６７０を備えており、これらのすべては種々の手段を介して互いに通信できる。
【００５２】
ある幾つかの実施形態では、機構６４０〜６７０は、プロセッサ６１０の一部であり得る。更に、ある幾つかの実施形態では、システムは、別々のプロセッサおよびメモリを含まないこともあり得る。その代わり、これらの固有のタスクを実行することに加えて機構６４０〜６７０は、別々に、または一致して汎用の計算エンジンの一部であり得る。
【００５３】
記憶装置６３０は、プロセッサ６１０によって実行されるプログラムを記憶する。具体的には、記憶装置６３０は、ＨＳＶＬＩを有するパケットを転送するためのシステム（アプリケーション）を実現するプログラムを記憶する。動作時に、アプリケーションプログラムは、記憶装置６３０からメモリ６２０にロードされてプロセッサ６１０によって実行され得る。その結果、ＨＳＶＬＩを有するパケットを転送するための装置６００は上記の機能を実行できる。ＨＳＶＬＩを有するパケットを転送するための装置６００は、任意選択的な表示装置６８５、キーボード６７５およびポインティングデバイス６８０に接続され得る。装置６００はまた、コンテンツ中心ネットワーク６９０にも接続される。
【００５４】
一実施形態では、プロセッサ６１０は、パケット受信機構６４０を駆動して、これにパケットを供給する。次に、プロセッサ６１０は、変換機構６５０を駆動して、これにパケットによって表されたＨＳＶＬＩを供給する。引き続いて、プロセッサ６１０は、転送情報取得機構６６０を駆動して、これに変換機構６５０から取得された少なくとも１つの固定長キーを供給する。次に、プロセッサ６１０は、パケット転送機構６７０を駆動して、これに転送情報取得機構６６０から取得された転送情報を供給する。
【００５５】
この詳細説明において説明されたデータ構造とコードは典型的には、コンピュータシステムによる使用のためのコードおよび／またはデータを記憶し得る任意のデバイスまたは媒体であり得るコンピュータ可読記憶媒体に記憶される。コンピュータ可読記憶媒体は、揮発性メモリ、不揮発性メモリ、例えば、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタルバーサタイル・ディスクまたはディジタルビデオディスク）といった磁気および光記憶デバイス、あるいは現在周知の、または後日開発されるコンピュータ可読媒体を格納できる他の媒体を含むが、これらに限定されない。
【００５６】
詳細説明セクションで説明された方法およびプロセスは、上記のコンピュータ可読記憶媒体に記憶され得るコードおよび／またはデータとして具現され得る。コンピュータシステムがコンピュータ可読記憶媒体に記憶されたコードおよび／またはデータを読み取って実行するとき、コンピュータシステムは、データ構造およびコードとして具現されて、コンピュータ可読記憶媒体に記憶された方法およびプロセスを実行する。
【００５７】
更に、本明細書で説明された方法およびプロセスは、ハードウエアモジュールまたは装置内に含まれ得る。これらのモジュールまたは装置は、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブル・ゲートアレイ（ＦＰＧＡ）、特定の時刻に特定のソフトウエアモジュールまたは一片のコードを実行する専用または共用プロセッサ、および／または現在周知の、または後日開発される他のプログラム可能な論理回路を含み得るが、これらに限定されない。ハードウエアモジュールまたは装置が駆動されると、これらは内部に含まれた方法およびプロセスを実行する。
【符号の説明】
【００５８】
１００、１０５、１１０、１１５、１２０、１２５、１３０、１３５、１４０、１４５  ノード
１５０、１５５、１６０  関心フロー
１６５、１７０、１７５  コンテンツフロー
１８０  ネットワーク
１８５  ネットワーク接続
２００  可変長識別子を有するパケットを転送するためのシステム
２１０  パケット
２２０  パケット受信器
２３０  可変長識別子
２４０  変換器
２５０  固定長キー
２６０  転送情報取得器
２７０  転送情報
２８０  パケット転送器
５００  可変長識別子
５１０  ３２ビットキー
５２０、５３０、５４０、５５０  変換
６００  コンテンツ中心ネットワークにおいてパケットを転送するための装置
６１０  プロセッサ
６２０  メモリ
６３０  記憶装置
６４０  パケット受信機構
６５０  可変長識別子変換機構
６６０  転送情報取得機構
６７０  パケット転送機構
６７５  キーボード
６８０  ポインティングデバイス
６８５  表示装置
６９０  コンテンツ中心ネットワーク
【図１】
2010178342.tif 000003
【図２】
2010178342.tif 000004
【図３】
2010178342.tif 000005
【図４】
2010178342.tif 000006
【図５】
2010178342.tif 000007
【図６】
2010178342.tif 000008