(57)【要約】      （修正有）【課題】可変長名称を有するパケットの転送を容易とするシステムを提供する。【解決手段】システムは、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を備える階層的構造化可変長識別子（ＨＳＶＬＩ）を有するパケットを受信する。システムは、エントリの第１のデータ構造からエントリを選択することによって最長接頭辞一致検索を行う。エントリは、名称要素、名称要素についての転送情報及びエントリを他のエントリに対してチェーン化した複数のエントリ識別子を示している。名称要素のサイズが所定の閾値以下である場合、システムは、名称要素に基づいてエントリを選択する。サイズが大きい場合、システムは、名称要素のハッシュとすることができる圧縮された鍵に基づいてエントリを選択する。システムはまた、選択されたエントリに関連した衝突を解決する。【選択図】図３Ａ
2016116215.tif 000002
【特許請求の範囲】
【請求項１】
パケットを転送するためのコンピュータ実装方法において、
コンピュータにより、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を備える階層的構造化可変長識別子（ＨＳＶＬＩ）を有するパケットを受信することと、
名称要素のサイズが所定の閾値以下であるとの判定に応じて名称要素に基づいてエントリを選択し、
前記サイズが前記所定の閾値よりも大きいとの判定に応じて、
圧縮された鍵を得るために前記名称要素を圧縮し、
前記圧縮された鍵に基づいてエントリを選択する
ことにより、前記名称要素、前記名称要素についての転送情報及びエントリを他のエントリに対してチェーン化する複数のエントリ識別子を示すエントリの第１のデータ構造からエントリを選択することによって前記パケットを転送するための最長接頭辞一致検索を行うことと、
前記選択されたエントリに関連した検索衝突を判定するのに応じて、検索衝突を解決し、それにより、可変長名称を有するパケットの転送を容易とすることとを備える、方法。
【請求項２】
コンピュータによって実行されたときに、前記コンピュータにパケットを転送するための方法を実行させる命令を記憶する持続性コンピュータ読み取り可能な記憶媒体において、前記方法が、
コンピュータにより、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を備える階層的構造化可変長識別子（ＨＳＶＬＩ）を有するパケットを受信することと、
名称要素のサイズが所定の閾値以下であるとの判定に応じて名称要素に基づいてエントリを選択し、
前記サイズが前記所定の閾値よりも大きいとの判定に応じて、
圧縮された鍵を得るために前記名称要素を圧縮し、
前記圧縮された鍵に基づいてエントリを選択する
ことにより、前記名称要素、前記名称要素についての転送情報及びエントリを他のエントリに対してチェーン化する複数のエントリ識別子を示すエントリの第１のデータ構造からエントリを選択することによって前記パケットを転送するための最長接頭辞一致検索を行うことと、
前記選択されたエントリに関連した検索衝突を判定するのに応じて、検索衝突を解決し、それにより、可変長名称を有するパケットの転送を容易とすることとを備える、コンピュータ読み取り可能な記憶媒体。
【請求項３】
コンテンツを転送するためのコンピュータシステムにおいて、
プロセッサと、
前記プロセッサに接続され且つコンピュータによって実行されたときに、前記コンピュータに方法を実行させる命令を記憶する記憶装置とを備え、前記方法が、
コンピュータにより、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を備える階層的構造化可変長識別子（ＨＳＶＬＩ）を有するパケットを受信することと、
名称要素のサイズが所定の閾値以下であるとの判定に応じて名称要素に基づいてエントリを選択し、
前記サイズが前記所定の閾値よりも大きいとの判定に応じて、
圧縮された鍵を得るために前記名称要素を圧縮し、
前記圧縮された鍵に基づいてエントリを選択する
ことにより、前記名称要素、前記名称要素についての転送情報及びエントリを他のエントリに対してチェーン化する複数のエントリ識別子を示すエントリの第１のデータ構造からエントリを選択することによって前記パケットを転送するための最長接頭辞一致検索を行うことと、
前記選択されたエントリに関連した検索衝突を判定するのに応じて、検索衝突を解決し、それにより、可変長名称を有するパケットの転送を容易とすることとを備える、コンピュータシステム。
【請求項４】
前記方法が、さらに、
前記名称要素のサイズが前記所定の閾値以下であるとの判定に応じて、前記名称要素に基づいて前記第１のデータ構造にエントリを作成することと、
前記名称要素のサイズが前記所定の閾値よりも大きいとの判定に応じて、
圧縮された鍵を得るために前記名称要素に対して第１の圧縮関数を実行し、
前記圧縮された鍵に基づいて前記第１のデータ構造にエントリを作成することと、
前記作成されたエントリに基づいて挿入衝突を判定することに応じて、前記挿入衝突を解決することとを備える、請求項３に記載のコンピュータシステム。
【請求項５】
前記方法が、さらに、
前記名称要素に基づいて、前記名称要素及び対応するインデックスを示す第２のデータ構造にエントリを作成することと、
前記第２のデータ構造における前記作成されたエントリについての前記対応するインデックスに対して前記第１のデータ構造における前記名称要素についてのエントリに文字列識別子を設定することとを備える、請求項４に記載のコンピュータシステム。
【請求項６】
前記挿入衝突を解決することが、
前記第１のデータ構造において前記作成されたエントリに衝突インジケータを含めることと、
新たな検索鍵を得るために前記名称要素に対して第２の圧縮関数を実行することと、
前記新たな検索鍵に基づいて第３のデータ構造にエントリを作成することとを備え、前記第３のデータ構造が前記名称要素についての前記新たな検索鍵及び転送情報を示す、請求項４に記載のコンピュータシステム。
【請求項７】
前記検索衝突を解決することが、さらに、
前記選択されたエントリが前記衝突インジケータを含むことを判定することと、
前記新たな検索鍵を得るために前記名称要素に対して前記第２の圧縮関数を実行することと、
前記新たな検索鍵に基づいて前記第３のデータ構造内のエントリを選択することとを備える、請求項６に記載のコンピュータシステム。
【請求項８】
前記方法が、さらに、
前記圧縮された鍵に基づいて前記第１のデータ構造内のエントリを選択することに応じて、前記選択されたエントリについての文字列識別子を判定することと、
前記第２のデータ構造から、前記判定された文字列識別子に基づいて前記名称要素を検索することと、
前記第２のデータ構造から前記検索された名称要素とＨＳＶＬＩの名称要素を比較することとを備える、請求項５に記載のコンピュータシステム。
【請求項９】
前記複数のエントリ識別子が、親識別子及びエントリ識別子を含み、前記エントリ識別子が前記第１のデータ構造における各エントリについて固有であり、前記エントリを選択することが、さらに、
各名称要素について、最も一般的なレベルにおける要素から始めて、前記親識別子に基づいて前記エントリを選択することを備え、
前記最も一般的なレベル名称要素について、前記エントリの親識別子が所定の初期値に対応し、
各後続の名称要素について、前記エントリの親識別子が、以前の最も一般的なレベルの前記名称要素に対応するエントリの前記エントリ識別子に対応する、請求項３に記載のコンピュータシステム。
【請求項１０】
前記第１のデータ構造が、鍵及びその結果から構成されたエントリのハッシュテーブルであり、
前記サイズが前記所定の閾値以下である場合、前記鍵が直接前記名称要素に基づいており、
前記サイズが前記所定の閾値よりも大きい場合、前記鍵が前記圧縮された鍵に基づいている、請求項３に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、ディジタルコンテンツの配信に関する。より具体的には、本開示は、コンテンツ中心ネットワーク（ＣＣＮ）ルータにおけるハードウェア支援ハッシュテーブルを使用することによるＣＣＮにおけるパケットの転送に関する。
【背景技術】
【０００２】
インターネット及び電子商取引の普及は、膨大な量のディジタルコンテンツを作成し続けている。コンテンツ中心ネットワーク（ＣＣＮ）アーキテクチャは、そのようなディジタルコンテンツにアクセスして処理するのを容易とするように設計されている。ＣＣＮは、様々なコンテンツアイテムについてのインタレストパケットを送信し、返送においてコンテンツオブジェクトのパケットを受信することによって互いに通信するネットワーククライアント、フォワーダ（例えば、ルータ）及びコンテンツ制作者などのエンティティ又はノードを含む。ＣＣＮインタレスト及びコンテンツオブジェクトは、通常は階層的構造化可変長識別子（ＨＳＶＬＩ）であるそれらの固有の名称によって識別される。ＨＳＶＬＩは、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を含むことができ、無制限且つ可変長の任意数のパスセグメント（例えば、名称要素）を含むことができる。
【０００３】
一般に、ＣＣＮルータは、パケットを転送する方法を決定するために転送テーブルを維持する。転送テーブルは、鍵が名称要素に基づき且つその結果が名称要素についての転送情報を含むハッシュテーブルとすることができる。ＣＣＮルータにおけるネットワークプロセッサは、ハードウェア支援ハッシュテーブルを提供することにより、転送の効率と速度を向上させることができる。これらのハードウェア支援ハッシュテーブルは、典型的には、鍵長及び結果長を固定サイズに制限する。この制限は、ＣＣＮにおいてパケットを転送するためにこれらのハードウェア支援ハッシュテーブルを使用することに制限を課しており、転送は、ハードウェア支援ハッシュテーブルによってサポートされている固定長よりも大きくすることができる無制限且つ可変長の名称要素に基づいて行われる。
【発明の概要】
【課題を解決するための手段】
【０００４】
１つの実施形態は、可変長の名称を有するパケットの転送を容易とするシステムを提供する。動作中、システムは、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を備える階層的構造化可変長識別子（ＨＳＶＬＩ）を有するパケットを受信する。システムは、エントリの第１のデータ構造からエントリを選択することによって最長接頭辞一致検索を実行する。エントリは、名称要素についての情報及びエントリを他のエントリに対してチェーン化する複数のエントリ識別子を転送する名称要素を示している。各名称要素は、所定サイズを有する。名称要素のサイズが所定の閾値以下である場合、システムは、名称要素に基づいてエントリを選択する。サイズが大きい場合、システムは、圧縮された鍵を取得するために名称要素を圧縮し、圧縮された鍵に基づいてエントリを選択する。選択されたエントリに関連付けられた検索衝突判定に応じて、システムは、検索衝突を解決し、それにより、可変長名称を有するパケットの転送を容易とする。
【０００５】
いくつかの実施形態において、名称要素のサイズが所定の閾値以下であるとの判定に応じて、システムは、名称要素に基づいて、第１のデータ構造にエントリを作成する。名称要素の大きさが所定の閾値よりも大きいとの判定に応じて、システムは、圧縮された鍵を得るために名称要素に対して第１の圧縮関数を実行し、圧縮された鍵に基づいて第１のデータ構造にエントリを作成する。作成されたエントリに基づいて挿入衝突を判定することに応じて、システムは、挿入衝突を解決する。
【０００６】
いくつかの実施形態において、システムは、名称要素に基づいて第２のデータ構造にエントリを作成する。ここで、第２のデータ構造は、名称要素及び対応するインデックスを示す。システムは、第２のデータ構造からインデックスに対する第１のデータ構造における名称要素についてのエントリに文字列識別子フィールドを設定する。
【０００７】
いくつかの実施形態において、システムは、第１のデータ構造において作成されたエントリに衝突インジケータを含めることによって挿入衝突を解決する。システムは、新たな検索鍵を得るために名称要素に対して第２の圧縮関数を実行する。システムはまた、新たな検索鍵に基づいて第３のデータ構造にエントリを作成する。ここで、第３のデータ構造は、新たな検索鍵及び名称要素についての転送情報を示す。
【０００８】
いくつかの実施形態において、システムは、選択されたエントリが衝突インジケータを含むと判定することによって検索衝突を解決する。システムは、新たな検索鍵を得るために名称要素に対して第２の圧縮関数を実行し、新たな検索鍵に基づいて第３のデータ構造におけるエントリを選択する。
【０００９】
いくつかの実施形態において、圧縮された鍵に基づいて第１のデータ構造におけるエントリを選択するのに応じて、システムは、選択されたエントリについての文字列識別子フィールドのインデックスを判定し、判定されたインデックスに基づいて第２のデータ構造から名称要素を検索する。システムは、第２のデータ構造から検索された名称要素とＨＳＶＬＩの名称要素を比較する。
【００１０】
いくつかの実施形態において、複数のエントリ識別子は、親識別子及びエントリ識別子を含み、エントリ識別子は、第１のデータ構造における各エントリについて固有である。各名称要素について、最も一般的なレベルにおける要素から始めて、システムは、親識別子に基づいてエントリを選択し、最も一般的なレベル名称要素について、エントリの親識別子は、所定の初期値に対応し、各後続の名称要素について、エントリの親識別子は、以前の最も一般的なレベルの名称要素に対応するエントリのエントリ識別子に対応する。
【００１１】
いくつかの実施形態において、第１のデータ構造は、鍵及びその結果から構成されたエントリのハッシュテーブルであり、サイズが所定の閾値以下である場合、鍵は、直接名称要素に基づいており、サイズが所定の閾値よりも大きい場合、鍵は、圧縮された鍵に基づいている。
【図面の簡単な説明】
【００１２】
【図１】図１は、本発明の実施形態にかかるハードウェア支援ハッシュテーブルを使用して可変長名称を有するパケットの転送を容易とする例示的なコンピューティング環境を図示している。
【図２】図２は、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて転送テーブルにエントリを挿入する方法を図示するフローチャートである。
【図３Ａ】図３Ａは、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて転送テーブル内のエントリを検索するための方法を図示するフローチャートである。
【図３Ｂ】図３Ｂは、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて転送テーブルにおいて遭遇した検索衝突を解決するための方法を図示するフローチャートである。
【図４Ａ】図４Ａは、本発明の実施形態にかかる９バイトまでのサイズを有する値を含む鍵を有するハッシュテーブルのデータ構造のフォーマットを示すテーブルである。
【図４Ｂ】図４Ｂは、本発明の実施形態にかかる２１バイトまでのサイズを有する値を含む鍵を有するハッシュテーブルのデータ構造のフォーマットを示すテーブルである。
【図４Ｃ】図４Ｃは、本発明の実施形態にかかる４１バイトまでのサイズを有する値を含む鍵を有するハッシュテーブルのデータ構造のフォーマットを示すテーブルである。
【図４Ｄ】図４Ｄは、本発明の実施形態にかかる４１バイトよりも大きいサイズを有する文字列用のハッシュ値を含む鍵を有するハッシュテーブルのデータ構造のフォーマットを示すテーブルである。
【図５】図５は、本発明の実施形態にかかる例示的な転送ハッシュテーブルを示すテーブルである。
【図６】図６は、本発明の実施形態にかかる文字列テーブルのフォーマットを示すテーブルである。
【図７】図７は、本発明の実施形態にかかる例示的な文字列テーブルを示すテーブルである。
【図８】図８は、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて可変長名称を有するパケットの転送を容易とする例示的なコンピュータ及び通信システムを図示している。
【発明を実施するための形態】
【００１３】
図において、同様の参照符号は、同じ図要素を指している。
【００１４】
以下の説明は、いかなる当業者も実施形態を製造して使用するのを可能とするように提示され、特定の用途及びその要件の文脈において提供される。開示された実施形態に対する様々な変更例は、当業者にとって容易に明らかであり、本願明細書において定義される一般的原理は、本開示の精神及び範囲から逸脱することなく他の実施形態及び用途に適用することができる。それゆえに、本発明は、示された実施形態に限定されるものではなく、本願明細書に開示された原理及び特徴と一致する最も広い範囲を与えられるべきである。
【００１５】
概説
本発明の実施形態は、転送ハッシュテーブルに名称要素をマッピングして転送ハッシュテーブルおいてチェーン化したハッシュ検索を実行することによってＣＣＮパケットを転送するために（典型的には固定長鍵に制限されている）ハードウェア支援ハッシュテーブルを使用するという問題を解決するシステムを提供する。ＣＣＮパケットの転送は、典型的には、最も一般的なレベルから最も特定のレベルまで順序付けられた連続名称要素を含む階層的構造化可変長識別子（ＨＳＶＬＩ）とすることができるパケットに関連付けられた名称に基づいている。本システムは、各名称要素のサイズに基づいてＣＣＮルータの転送ハッシュテーブルにおける挿入及び検索のためにＨＳＶＬＩの名称要素をマッピングすることができる。名称要素のサイズが小さい場合（例えば、４１バイト以下）、システムは、鍵が名称要素である標準的なハッシュテーブル関数を使用してハッシュテーブルエントリを作成する。サイズが大きい場合（例えば、４１バイトよりも大きい）、システムは、名称要素に対して最初に圧縮関数を適用してハッシュテーブルについての鍵として圧縮された値を使用することによってエントリを作成する。システムはまた、特定のインデックスにおける別個の文字列テーブルに圧縮されていない名称要素を挿入し、エントリの結果においてそのインデックスを示すことができる。衝突が挿入中に発生した場合、システムは、衝突を示し、新たな検索鍵を生成し、新たな検索鍵を使用して別個のテーブルにエントリを作成するために、結果にフラグを設定することができる。
【００１６】
さらにまた、システムは、パケットについての転送情報を判定するチェーン化したハッシュ検索を実行するために転送ハッシュテーブルを使用する。挿入プロセス中において、システムは、転送ハッシュテーブルの各結果に対して固有のインデックス鍵（例えば、エントリ識別子（ＥＩＤ））を割り当てる。各エントリは、独自のインデックス鍵を含み、また、以前の名称要素の固有のインデックス鍵に対するポインタ（例えば、親エントリ識別子（ＰＥＩＤ））を含む。ＣＣＮルータにおいて転送ハッシュテーブルを使用する他の方法は、米国特許第８，２４３，７３５号明細書に記載された累積的名称要素ハッシュである。
【００１７】
パケットを転送するために、システムは、各名称要素についての転送ハッシュテーブルにおける検索をチェーン化するために各エントリ結果の固有のインデックス鍵を使用して最も一般的なレベルから最も特定のレベルまでＨＳＶＬＩの各名称要素を解析する。挿入プロセスと同様に、システムは、サイズが所定のサイズ以下である場合には名称を直接使用することによって及びサイズが大きい場合には圧縮された鍵を使用することによって名称要素を検索する。衝突が検索中に発生した場合、システムは、別個の文字列テーブルから元の圧縮されていない鍵を得るためにエントリの結果に含まれるインデックスを使用し、パケットからのＨＳＶＬＩの名称要素と圧縮されていない鍵を比較することができる。さらにまた、システムは、エントリ内の結果フラグが衝突を示すことを検出し、新たな検索鍵を生成し、新たな検索鍵を使用して別個のテーブル内の検索を実行することができる。「最長接頭辞一致検索」と称されるチェーン化したハッシュ検索から返された結果は、パケットを転送するために使用される。本開示において、最長接頭辞一致検索は、ＨＳＶＬＩにおいて、最も一般的なレベルから最も特定のレベルまで、最大数の要素と一致する結果を返す検索を実行することを指す。それゆえに、転送ハッシュテーブル（例えば、ＣＣＮルータによって維持されるハードウェア支援ハッシュテーブル）に対してサイズベースの方法で名称要素をマッピングすることにより、及び、固有のインデックス鍵によってハッシュ検索をチェーン化することにより、システムは、パケット転送の効率を向上させるためにＣＣＮルータにおいてハードウェア支援ハッシュテーブルを使用することができる。
【００１８】
本開示に記載された例において、コンテンツの各部は、個々に名称付けられ、データの各部は、同じデータの他のバージョン又は他のソースからのデータなど、データの任意の他の部分からデータを区別する固有の名称に結合されている。この固有の名称は、ネットワークデバイスが固有の名称を示す要求又はインタレストを広めることによってデータを要求するのを可能とし、データの記憶場所、ネットワークの場所、アプリケーション及び伝送手段から独立してデータを得ることができる。以下の用語は、ＣＣＮアーキテクチャを説明するために使用される。
【００１９】
コンテンツオブジェクト：固有の名称に結合されている名称付きデータの単一部分である。コンテンツオブジェクトは、「永続的」であり、これは、コンテンツオブジェクトがコンピューティングデバイス内又は異なるコンピューティングデバイス間を移動することができるが変化しないことを意味する。コンテンツオブジェクトの任意の要素が変化した場合、変更を行ったエンティティは、更新されたコンテンツを含む新たなコンテンツオブジェクトを作成し、新たな固有の名称に新たなコンテンツオブジェクトを結合する。
【００２０】
固有の名称：ＣＣＮ内の名称は、通常、場所とは無関係であり、コンテンツオブジェクトを固有に識別する。データ転送装置は、コンテンツオブジェクトについてのネットワークアドレス又は物理的場所にかかわらず、コンテンツオブジェクトを生成又は記憶するネットワークノードに向けてパケットを転送するために名称又は名称接頭辞を使用することができる。いくつかの実施形態において、名称は、階層的構造化可変長識別子（ＨＳＶＬＩ）とすることができる。ＨＳＶＬＩは、様々な方法で構築可能ないくつかの階層的な要素に分割されることができる。例えば、個々の名称要素ｐａｒｃ、ｈｏｍｅ、ｃｃｎ及びｔｅｓｔ．ｔｘｔは、名称「／ｐａｒｃ／ｈｏｍｅ／ｃｃｎ／ｔｅｓｔ．ｔｘｔ」を形成するために左指向の接頭辞が主要である方法で構築可能である。それゆえに、名称「／ｐａｒｃ／ｈｏｍｅ／ｃｃｎ」は、「／ｐａｒｃ／ｈｏｍｅ／ｃｃｎ／ｔｅｓｔ．ｔｘｔ」の「親」又は「接頭辞」とすることができる。共同文書などの異なるバージョンのコンテンツアイテムを区別するためにさらなる要素が使用可能である。いくつかの実施形態において、名称は、コンテンツオブジェクトのデータ（例えば、チェックサム値）から及び／又はコンテンツオブジェクトの名称要素から導出されたハッシュ値などの非階層的識別子を含むことができる。ハッシュベースの名称の説明は、米国特許出願第１３／８４７，８１４号に記載されている。名称はまた、フラットラベルとすることができる。以下では、「名称」は、階層名称若しくは名称接頭辞、フラット名称、固定長名称、任意長名称又はラベル（例えば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ラベル）など、名称付きデータネットワークにおけるデータの一部用の任意の名称を指すのに使用される。
【００２１】
インタレスト：データの一部についての要求を示し且つデータの一部についての名称（又は名称接頭辞）を含むパケットである。データ消費者は、ＣＣＮルータが、要求やインタレストを満たすために要求されたデータを提供することができる記憶装置（例えば、キャッシュサーバ）又はデータ制作者に向けて伝播することができる情報中心ネットワークにわたって要求又はインタレストを広めることができる。
【００２２】
本願明細書に開示された方法は、ＣＣＮネットワークに限定されるものではないが、他のアーキテクチャにも同様に適用可能である。ＣＣＮアーキテクチャの例は、米国特許出願第１２／３３８，１７５号に記載されている。
【００２３】
ハードウェア支援ハッシュテーブルを使用した転送のネットワークアーキテクチャ及び概要
図１は、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて可変長名称を有するパケットの転送を容易とする例示的なコンピューティング環境１００を図示している。コンピューティング環境１００は、ネットワーク１３０を介してコンテンツについての要求を判定することができる任意のコンテンツ消費装置を含むことができる装置１３２を含むことができる。コンピューティング環境１００はまた、ネットワーク１３０を介してコンテンツについての要求を判定することができる任意のコンテンツ消費装置を含むことができる装置１３４を含むことができる。コンピューティング環境１００は、ノード１０２、１０４、１０６、１０８、１１０、１１２及び１１４を含むことができるネットワーク１３０を含むことができる。ネットワーク１３０は、コンテンツ中心ネットワーク（ＣＣＮ）とすることができ、ノード１０２〜１１４のそれぞれは、本開示に記載されたハードウェア支援ハッシュテーブルを有するネットワークプロセッサを含むＣＣＮフォワーダ又はルータとすることができる。装置１３２のユーザは、装置１３４においてコンテンツ制作者によって受信されるコンテンツの一部についての「／ｓｈｏｒｔｎａｍｅ１／ｌｏｎｇｎａｍｅ／ｓｈｏｒｔｎａｍｅ２」というＨＳＶＬＩ１４２を有するインタレストパケット１４０を生成することができる。装置１３４は、インタレスト１４０とは逆の経路に沿って、インタレスト１４０を満たすコンテンツオブジェクト１４４を返送することができる。インタレスト１４０及びコンテンツオブジェクト１４４は、ノード１０２（「ＣＣＮルータ１０２」）におけるＣＣＮルータを含むネットワーク１３０内の様々な中間ルータを通過することができる。ＣＣＮルータ１０２は、ルータ１０２のプロセッサに含まれる特定のハードウェアを使用する転送ハッシュテーブル１５０を維持する。
【００２４】
転送ハッシュテーブル１５０は、ハッシュ鍵１６０及び結果１７０を有するエントリをリスト化することによって「ｓｈｏｒｔｎａｍｅ１／ｌｏｎｇｎａｍｅ／ｓｈｏｒｔｎａｍｅ２」というＨＳＶＬＩ１４２についての転送情報を含むことができる。転送ハッシュテーブル１５０は、エントリ１５２、１５４及び１５６を含むことができる。短い名称要素（例えば、４１バイト以下）について、ＣＣＮルータ１０２は、「ｓｈｏｒｔｎａｍｅ１」という値を有するエントリ１５２及び「ｓｈｏｒｔｎａｍｅ２」という値を有するエントリ１５６におけるように、ハッシュ鍵において直接名称要素を使用することができる。長い名称要素（例えば、４１バイトよりも大きい）について、ＣＣＮルータ１０２は、圧縮された鍵ＫＣを得るために名称要素に対して圧縮関数を実行することによって名称要素を最初に圧縮することができ、「ｈａｓｈ（ｌｏｎｇｎａｍｅ）」という値を有するエントリ１５４におけるように、ハッシュ鍵においてその圧縮された鍵ＫＣを使用することができる。圧縮関数は、ハッシュ関数、辞書法又は任意の他の公知の方法に基づくことができる。エントリ１５４はまた、オリジナルの圧縮されていない「ｌｏｎｇｎａｍｅ」文字列を記憶する別個の文字列テーブルにおけるエントリに対するインデックスを示す文字列識別子（ＳＩＤ）フィールドを含むことができる。ＣＣＮルータ１０２は、図２、図３Ａ及び図３Ｂに関連して説明したように挿入及び検索衝突を検出して処理する。いくつかの実施形態において、転送ハッシュテーブル１５０は、ＳＩＤを含む長い名称要素（例えば、エントリ１５４）についてのＳＩＤ及び他のテーブルを含まない短い名称要素（例えば、エントリ１５２及び１５６）についての１つのテーブルを含む。圧縮された及び圧縮されていない鍵は、例えば、圧縮されていない鍵については図４Ａ〜図４Ｃ及び圧縮された鍵については図４Ｄに示されたデータ構造に対応する異なるテーブルに記憶されることができる。転送ハッシュテーブル１５０におけるエントリはまた、鍵が圧縮されているか又は圧縮されていないかを示すために鍵におけるビットを含むことができる。
【００２５】
さらにまた、ＣＣＮルータ１０２は、ＨＳＶＬＩ１４２についての最長接頭辞一致を判定するために転送ハッシュテーブル１５０においてチェーン化したハッシュ検索を実行することによってパケット１４０を転送する。ＣＣＮルータ１０２は、第１の名称要素（「ｓｈｏｒｔｎａｍｅ１」）についての鍵を計算する。第１の名称要素が閾値よりも長くないことから、文字としての名称要素（例えば、エントリ１５２のハッシュ鍵１６０）と連結されたＰＥＩＤに等しい圧縮されていない鍵Ｋ１を使用する。システムは、圧縮されていない鍵ハッシュテーブルにおいてＫ１を検索する。そして、ハードウェア支援ハッシュテーブルは、対応する結果を生成する。一致がＫ１に基づいてみつかった場合、結果は、ＥＩＤ及び名称についての対応する転送情報（例えば、エントリ１５２の結果１７０）を含む。そして、システムは、次の名称要素（「ｌｏｎｇｎａｍｅ」）の検索に移行する。この名称要素は、閾値よりも長いことから、名称要素のハッシュ（例えば、エントリ１５４のハッシュ鍵１６０）と連結されたＰＥＩＤに等しい圧縮された鍵Ｋ２を計算する。この場合、ＰＥＩＤは、Ｋ１から返されたＥＩＤである。システムは、圧縮された鍵ハッシュテーブルにおいてＫ２を検索する。そして、ハードウェア支援ハッシュテーブルは、対応する結果を生成する。一致がＫ２に基づいてみつかった場合、結果は、名称についてのＥＩＤ及び対応する転送情報（例えば、エントリ１５４の結果１７０）を含む。ＥＩＤは、前の鍵を効率的且つ固有に圧縮した小さな番号とすることができる。システムは、各後続の名称要素についてのこれらのチェーン化したハッシュ検索を継続し、最も特定のレベル名称要素（「ｓｈｏｒｔｎａｍｅ２」）から返される結果は、最長接頭辞一致である（例えば、エントリ１５６についての結果１７０の転送情報）。
【００２６】
ハードウェア支援ハッシュテーブルを使用したエントリの挿入
図２は、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて転送テーブルにエントリを挿入するための方法２００を図示するフローチャートである。動作中、システムは、ＨＳＶＬＩを有するパケットを判定する（動作２０２）。システムは、（例えば、最も一般的なレベルから最も特定のレベルまで各名称要素によって）順次ＨＳＶＬＩを解析する。システムは、現在の名称要素の長さを判定する（動作２０４）。長さが所定のサイズ（例えば、４１バイト）以下である場合（判定２０６）、システムは、直接名称要素（例えば、オリジナルの圧縮されていない文字列）を使用してハッシュテーブルにエントリを作成する（動作２０８）。エントリについての鍵は、名称要素のハッシュと連結された親エントリ識別子（ＰＥＩＤ）とすることができる一方で、エントリについての結果は、制御プレーンによって割り当てられた固有のエントリ識別子（ＥＩＤ）を含むことができる。各名称要素について、ＰＥＩＤは、「０」の初期値に設定され、図３Ａに関連して以下に説明するように、ＰＥＩＤが以前の名称要素からの検索のＥＩＤに設定されるように、検索プロセス中に更新される。そして、システムは、任意の名称要素が処理されることになるままであるかどうかを判定する（判定２２４）。残された名称要素が存在しない場合、動作は戻る。多くの名称要素が処理されることになるままである場合、システムは、次の名称要素に移動し（動作２２６）、次の名称要素についての挿入プロセスを開始するために動作２０４に戻る。
【００２７】
長さが所定のサイズ（例えば、４１バイト）以下である場合（判定２０６）、システムは、圧縮された鍵（ＫＣ）を得るために、例えば名称要素をハッシュすることによって名称要素を圧縮する（動作２１２）。システムは、圧縮された鍵Ｋｃを使用してハッシュテーブルにエントリを作成する（動作２１４）。システムが圧縮された鍵に基づいてエントリを挿入する際に衝突を検出しない場合（判定２１６）、システムは、特定のインデックスにおいて文字列テーブルにオリジナルの圧縮されていない文字列を挿入し、特定のインデックス値に設定された値によって転送テーブルにおけるエントリの結果において文字列識別子（ＳＩＤ）を含める（動作２２２）。ＳＩＤは、圧縮されていない鍵値を記憶するテーブルに対するポインタである。システムが圧縮された鍵に基づいてエントリを挿入する際に衝突を検出した場合（判定２１６）、システムは、衝突を示すためにエントリに結果フラグを設定する（動作２１８）。そして、システムは、新たな検索鍵を生成し、新たな検索鍵を使用して衝突テーブルにエントリを作成する（動作２２０）。システムは、上述したように、動作２２２を実行する。その後、システムは、任意の名称要素が処理されることになるままであるかどうかを判定し（判定２２４）、任意の名称要素が処理されることになるままである場合、次の名称要素についての挿入プロセスを開始するために（動作２０４）次の名称要素に移動する（動作２２６）。
【００２８】
ハードウェア支援ハッシュテーブルを使用したエントリの検索
図３Ａは、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて転送テーブル内のエントリを検索するための方法３００を図示するフローチャートである。動作中、システムは、ＨＳＶＬＩを有するパケットを受信する（動作３０２）。システムは、（例えば、最も一般的なレベルから最も特定のレベルまで各名称要素を処理することによって）順次ＨＳＶＬＩを解析し、各名称要素についての検索エントリ結果を得て、一致する各結果を記憶する。最も具体的なレベルの名称要素についての一致した結果は、最長接頭辞一致であり、パケットについての転送情報を含む。最長一致は、それは最も特異的であるため、名称要素の数の点で最良と考えられる。システムは、現在の名称要素の長さを判定する（動作３０４）。長さが所定のサイズ（例えば、４１バイト）以下である場合（判定３０６）、システムは、ＰＥＩＤ及び文字列として直接名称要素に基づいて鍵を使用して転送テーブル内の値を検索する（動作３０８）。一致がみつからない場合、システムは、一時的な記憶装置Ｒに現在記憶されている一致を返す（動作３３０）。一致がみつかった場合、システムは、一時的な記憶装置Ｒに一致した結果を記憶する（動作３１２）。一致した結果は、上述したように、ハッシュテーブル検索をチェーン化するために使用される固有のＥＩＤを含む。システムは、任意の名称要素が処理されることになるままであるかどうかを判定する（判定３１４）。残された名称要素が存在しない場合、システムは、一時的な記憶装置Ｒに現在記憶されている一致を返す（動作３３０）。多くの名称要素が処理されることになるままである場合（判定３１４）、システムは、次の名称要素に進み、現在の結果のＥＩＤに対して次の名称要素のＰＥＩＤを設定する（動作３１６）。その後、システムは、次の名称要素についての検索プロセスを開始するために動作３０４に戻る。
【００２９】
長さが所定のサイズ（例えば、４１バイト）よりも大きい場合（判定３０６）、システムは、圧縮された鍵（ＫＣ）を得るために、例えば名称要素をハッシュすることによって名称要素を圧縮する（動作３１８）。システムは、ＰＥＩＤ及び圧縮された鍵Ｋｃに基づいて鍵を使用して転送テーブル内の値を検索する（動作３２０）。一致がみつからない場合、システムは、一時的な記憶装置Ｒに現在記憶されている一致を返す（動作３３０）。一致がみつかった場合、システムは、結果についての文字列識別子（例えば、インデックス値）を判定し、文字列識別子（ＳＩＤ）のインデックス値に対応する文字列テーブルからエントリを検索する（動作３２４）。上述したように、ＳＩＤは、圧縮されていない鍵値を記憶するテーブルに対するポインタである。システムは、一時的な記憶装置Ｒに一致した結果を記憶する（動作３２６）。一致した結果は、上述したように、ハッシュテーブル検索をチェーン化するために使用される固有のＥＩＤを含む。システムは、衝突が圧縮された鍵に基づいて検索において検出されたかどうかを判定する（判定３２８）。衝突が圧縮された鍵に基づいて検索において検出された場合、図３Ｂに記載されたように動作を継続する。衝突が検出されない場合、システムは、任意の名称要素が処理されることになるままであるかどうかを判定する（判定３１４）。残された名称要素が存在しない場合、システムは、一時的な記憶装置Ｒに現在記憶されている一致を返す（動作３３０）。より多くの名称要素が処理されることになるままである場合、システムは、次の名称要素に進み、現在の結果のＥＩＤに次の名称要素のＰＥＩＤを設定する（動作３１６）。その後、システムは、次の名称要素についての検索プロセスを開始するための動作３０４に戻る。
【００３０】
ハードウェア支援ハッシュテーブルを使用した衝突解決
図３Ｂは、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて転送テーブルにおいて遭遇した検索衝突を解決するための方法３５０を図示するフローチャートである。動作中、システムは、図３Ａに関連して示して説明したプロセスからの最新の検索エントリを含む一時的な記憶結果Ｒｐｅｎｄｉｎｇを判定する（動作３５２）。システムは、エントリが文字列テーブルに由来することを判定することができる（動作３５４）。システムは、文字列テーブルからのエントリに対してインタレストのパケットメモリからの名称要素文字列を比較する（動作３５６）。上述したように、文字列テーブルエントリは、結果に含まれるＳＩＤに基づいて配置されており、ＳＩＤは、圧縮されていない鍵値を記憶したテーブルに対するポインタである。文字列が一致しない（ハッシュエントリが一致しないことを示す）場合（判定３５８）、システムは、（図３Ａにおける動作によって判定されるような以前の名称要素についての転送情報を含む）Ｒに記憶されている一致を返す。文字列が一致する場合（判定３５８）、システムは、ＲにＲｐｅｎｄｉｎｇからの結果を記憶し（動作３６０）、図３Ａの動作３１４が続くＨＳＶＬＩの処理を継続するためにＲを返す（動作３６２）。
【００３１】
システムはまた、衝突を示す結果におけるフラグに基づいて、Ｒｐｅｎｄｉｎｇにおけるエントリが衝突を示す旨を判定することができる（動作３６６）。システムは、（図３Ａにおける動作３１８の）圧縮された鍵を得るために適用されたハッシュ関数とは異なるもの及び（図２の動作２２０におけるように）挿入によって新たな検索鍵を生成するために適用されたハッシュ関数と同じものの双方であるハッシュ関数を適用することによって新たな検索鍵を生成する（動作３６８）。システムは、新たな検索鍵を使用して衝突テーブルにおいて結果を検索し（動作３７０）、一時的な記憶装置Ｒに衝突テーブル結果を記憶する（動作３７２）。その後、システムは、ＨＳＶＬＩの処理を継続するために図３Ａの動作３１４にＲを返す（動作３６２）。
【００３２】
ハードウェア支援ハッシュテーブルの例示的なフォーマット
図４Ａは、本発明の実施形態にかかる９バイトまでのサイズを有する値を含む鍵によるハッシュテーブルデータ構造４００のフォーマットを示すテーブルである。データ構造４００は、転送ハッシュテーブル内のエントリを表しており、エントリについてのハッシュ鍵４２０及び結果４２２を含む。ハッシュ鍵４２０は、３バイトの親エントリ識別子（ＰＥＩＤ）フィールド４０２と、２バイトのタイプフィールド４０４と、２バイトの長さフィールド４０６と、９バイトの値フィールド４０８とを含むことができる。ＰＥＩＤ４０２は、初期値（例えば、０）に設定される識別子を含み、その後、検索中に親名称要素からの固有のエントリ識別子によって更新される。結果４２２は、２バイトのフラグフィールド４１０と、３バイトのエントリ識別子（ＥＩＤ）フィールド４１２と、２バイトのスロットビットマップフィールド４１４及び３バイトのルート識別子（ＲＩＤ）フィールド４１６を含むことができる転送エントリとを含むことができる。フラグ４１０は、ネットワークプロセッサ（例えば、ＥＺＣｈｉｐ  ＮＰ４ネットワークプロセッサ、以下、本願明細書では「ＮＰ４」）に固有のフラグのセットを含むことができ、転送ハッシュテーブルにおける衝突を示すことができる。ＥＩＤ４１２は、制御プレーンによって割り当てられた固有の識別子である。動作中、システムは、図２及び図３Ａに関連して説明したように、以前の検索からのＥＩＤの値による初期検索の後に、検索のＰＥＩＤを更新することにより、転送ハッシュテーブル内の検索をチェーン化することができる。転送エントリ（スロットビットマップ４１４及びＲＩＤ４１６）は、インタレストについてのマルチキャスト転送を可能とする。例えば、スロットビットマップ４１４は、出力ＮＰ４アイデンティティを示すことができる。各ラインカードは、２つのＮＰ４ネットワークプロセッサを有することができる。その結果、スロットビットマップ４１４は、ラインカードよりもむしろ出力ＮＰ４を示す。ＲＩＤ４１６は、各ラインカード上の出力ポートを示すために制御ソフトウェアによって作成された固有の識別子である。制御ソフトウェアは、ＲＩＤによってインデックス付けされ且つインタレストを送信する正確なポートを示す各出力ＮＰ４のアレイエントリを作成することができる。いくつかの実施形態において、複数のルートは、同じ出力セットを共有して同じＲＩＤを使用することができる一方で、他の実施形態においては、１つのＲＩＤが各ルートについて割り当てられる。データ構造４００は、ハッシュ鍵４２０についての１６バイト及び結果４２２についての１０バイトを含む２６の行の長さを有する。
【００３３】
図４Ｂは、本発明の実施形態にかかる２１バイトまでのサイズを有する値を含む鍵によるハッシュテーブルデータ構造４２０のフォーマットを示すテーブルである。データ構造４２０は、転送ハッシュテーブル内のエントリを表しており、エントリについてのハッシュ鍵４３０及び結果４３２を含む。データ構造４２０は、データ構造４００と同様のフィールドを含む（例えば、ハッシュ鍵４３０は、ＰＥＩＤ４０２と、タイプ４０４と、長さ４０６と、値フィールド４２８とを含み、結果４３２は、フラグ４１０と、ＥＩＤ４１２と、ビットマップ４１４と、ＲＩＤ４１６とを含む）。データ構造４２０によって表されるエントリは、例えば、１０から２１バイトの長さを有する文字列についての値４２８のフィールドを含む。データ構造４２０は、ハッシュ鍵４３０についての２８バイト及び結果４３２についての１０バイトを含む３８バイトの行の長さを有する。
【００３４】
図４Ｃは、本発明の実施形態にかかる４１バイトまでのサイズを有する値を含む鍵によるハッシュテーブルデータ構造４３０のフォーマットを示すテーブルである。データ構造４３０は、データ構造４００と同様のフィールドを含む（例えば、ハッシュ鍵４４０は、ＰＥＩＤ４０２と、タイプ４０４と、長さ４０６と、値フィールド４３８とを含み、結果４３２は、フラグ４１０と、ＥＩＤ４１２と、ビットマップ４１４と、ＲＩＤ４１６とを含む）。データ構造４３０によって表されるエントリは、例えば、２２から４１バイトの長さを有する文字列についての値４２８を含む。データ構造４３０は、ハッシュ鍵４４０についての４８バイト及び結果４４２についての１０バイトを含む５８バイトの行の長さを有する。
【００３５】
図４Ｄは、本発明の実施形態にかかる４１バイトよりも大きいサイズを有する文字列についてのハッシュ値を含む鍵によるハッシュテーブルデータ構造のフォーマットを示すテーブルである。データ構造４３０は、ハッシュ鍵４５０及び結果４５２を含む。ハッシュ鍵４５０は、図２及び図３Ａに関連して説明したように圧縮された鍵を含む、ＰＥＩＤ４０２と、１６バイトのハッシュ値４４８とを含む。結果４５２は、データ構造４００と同様のフィールドを含み（例えば、フラグ４１０、ＥＩＤ４１２、ビットマップ４１４及びＲＩＤ４１６）、さらに、圧縮されていない鍵の値を記憶するテーブルに対するポインタを含む文字列識別子（ＳＩＤ）フィールド４１８を含む。いくつかの実施形態において、ＳＩＤは、フラグ４１０におけるビットによって示される衝突識別子（ＣＩＤ）である。データ構造４４０は、ハッシュ鍵４５０についての１９バイト及び結果４５２についての１３バイトを含む３２の行の長さを有する。
【００３６】
いくつかの実施形態（例えば、ＮＰ４）において、ハードウェア支援ハッシュテーブルにおけるエントリは、以下に制限される。エントリあたり３６バイト、鍵及び結果はともに３２バイト以下である；エントリあたり６８バイト、鍵及び結果はともに６４バイト以下である。データ構造４００、４２０、４３０及び４４０は、これらの制限を満たす。データ構造４００は、転送ハッシュテーブルにおけるエントリを表し、鍵（例えば、名称要素）の値は、９バイトであり、データ構造４２０及び４３０は、より大きな文字列についての値（それぞれ、２１及び４１バイト）を有するエントリを表す。データ構造４４０は、４１バイトよりも長い長さの鍵を有するエントリを表し、ネットワークプロセッサは、長さが１６バイトの圧縮された鍵（ハッシュ４４８）を得るために圧縮機又はハッシュ関数を使用する。それゆえに、データ構造４００及び４４０（それぞれ、２６及び３２バイト）は、双方とも、３２バイトにフィットする一方で、データ構造４２０及び４３０（それぞれ、３８及び５８バイト）は、６４バイトのエントリをもたらす。データ構造４２０は、データ構造４３０の大きなエントリと同じ量のメモリ及び同じサイクル数をもたらすことから、いくつかの実施形態において、システムは、データ構造４２０を使用しなくてもよいことに留意されたい。さらに、圧縮されていない鍵についてのデータ構造（例えば、データ構造４００、４２０及び４３０）は、長さ符号化された名称要素を含むことができる。例えば、データ構造４００は、タイプフィールド４０４、長さフィールド４０６及び値フィールド４２８を含むＴＬＶを有する。したがって、文字の名称要素が鍵の一部として使用される場合（例えば、圧縮されていない鍵における「ＰＥＩＤ＋名称要素」）、４１バイトの残りの部分はゼロでパディングされることから、システムは、値を正確に判定することができる。
【００３７】
例示的な転送ハッシュテーブル及び対応する使用ケース
図５は、本発明の実施形態にかかる例示的な転送ハッシュテーブル５００を示すテーブルである。転送ハッシュテーブル５００は、データ構造４００に対応するエントリ５３０、５３２、５３４、５３６及び５４０を含む（例えば、４１バイト以下の長さの文字列についての鍵）。転送ハッシュテーブル５００はまた、データ構造４４０に対応するエントリ５３８及び５４２を含む（例えば、４１バイトよりも大きい長さの文字列についての圧縮された鍵）。転送ハッシュテーブル５００における各エントリは、ハッシュ鍵５２０及び結果５２２を含む。ハッシュ鍵５２０は、ＰＥＩＤ５０２及び値５０８を含み、結果５２２は、フラグ５１０と、ＥＩＤ５１２と、スロットビットマップ５１４と、ＲＩＤ５１６と、（いくつかのエントリについて）ＳＩＤ５１８とを含む。
【００３８】
図６は、本発明の実施形態にかかる文字列テーブル６００のフォーマットを示すテーブルである。文字列テーブル６００は、２バイトのフラグフィールド６０２と、４バイトの次フィールド６０４と、５８バイトの値フィールド６０６とを含むことができる。フラグ６０２は、例えばＮＰ４プロセッサに固有とすることができる。次６０４は、複数のエントリをとる文字列についてのポインタとすることができる。文字列が複数のエントリを必要とする場合、フラグ６０２は、次の検索を実行するためのテーブルを示すことができる。例えば、６４バイトの文字列を記憶することは、２つの文字列テーブルのエントリを使用することができる。値６０６は、長さ符号化された文字列とすることができる。図７は、本発明の実施形態にかかる例示的な文字列テーブル７００を示すテーブルである。文字列テーブル７００は、「２」のＳＩＤと「ｌｏｎｇｎａｍｅ」の値を有するエントリ７０２と、「３」のＳＩＤと「ｌｏｎｇｎａｍｅ＿ｚ」の値を有するエントリ７０４とを含むことができる。
【００３９】
以下のＨＳＶＬＩ５５２の使用ケースは、図４Ａ〜Ｄ、図５、図６及び図７並びに本願明細書に開示された方法に関連して提示して説明した例示的なテーブルに基づいている。動作中、ＣＣＮフォワーダ又はルータは、「／ａｐｐｌｅ／ｐｉｅ／ｌｏｎｇｎａｍｅ／ｇｏｏｄ」というＨＳＶＬＩ５５２を有するインタレストを受信することができる。システムは、最も一般的なレベル名称要素の短い（例えば、４１バイト以下）文字列「ａｐｐｌｅ」と連結された「０」のＰＥＩＤを有するハッシュ鍵に基づいて第１の転送エントリを検索することによって最長接頭辞一致をみつける。転送ハッシュテーブルは、システムがその後に次の転送エントリを検索するためにＰＥＩＤを使用する「２」のＥＩＤを有する結果（エントリ５３２）を返す。システムは、「４」のＥＩＤを有する結果（エントリ５３６）を返す次の最も一般的なレベル名称要素の短い文字列「ｐｉｅ」と連結された「２」のＰＥＩＤを有するハッシュ鍵に基づいて次の転送エントリを検索する。次に、システムは、「２」の値を有するＳＩＤと同様に衝突を示す「１」に設定された衝突フラグを有する結果を返す長い（例えば、４１バイトよりも大きい）文字列「ｌｏｎｇｎａｍｅ」というハッシュ値と連結された「４」のＰＥＩＤを有するハッシュ鍵に基づいて次の転送エントリを検索する。システムは、衝突が同じ転送エントリをもたらす２つのハッシュ鍵に起因すると判定することができる（例えば、同じバケットにハッシュする）。システムは、新たなハッシュ鍵を得るために圧縮されていない鍵に対して新たなハッシュ関数を実行し、転送エントリを得るために新たなハッシュ鍵が別個の衝突テーブルをもたらす旨を使用し、エントリ５３８についての結果としてその値を返すことができる。他の例において、「／ｃｈｅｒｒｙ／ｐｉｅ／ｌｏｎｇｎａｍｅ＿ｚ」というＨＳＶＬＩ５５０に対する検索は、エントリ５３０、エントリ５３４及びエントリ５４２をもたらす（以前のＥＩＤにチェーン化したＰＥＩＤに基づいて）チェーン化したハッシュ検索をもたらすであろう。エントリ５４２における衝突フラグが（ＨＳＶＬＩ５５０からの名称要素「ｌｏｎｇｎａｍｅ＿ｚ」のハッシュがＨＳＶＬＩ５５２からの名称要素「ｌｏｎｇｎａｍｅ」のハッシュと同じである旨を示す）「１」に設定されるという判定により、システムは、新たなハッシュ鍵を得るために上述したような新たなハッシュ関数を実行し、別個の衝突テーブルから適切な転送エントリ結果を得るために新たなハッシュ鍵を使用する。
【００４０】
さらに、システムは、ＨＳＶＬＩの名称要素が転送ハッシュテーブルに存在しないが、そのハッシュが既存のエントリと衝突するために衝突が発生したと判定することができる。システムは、別個の文字列テーブルに記憶された圧縮されていない鍵を得るためにエントリ５３８のＳＩＤを使用し、パケットメモリにおけるＨＳＶＬＩの名称要素と得られた文字列を比較し、それに応じて進むことができる。上述したように、この比較は、パケットメモリからの文字列が文字列テーブルに存在する（したがって、転送ハッシュテーブルにおける正しいエントリである）か否かを示すブール値の結果を生み出すことができる。例えば、「ａｐｐｌｅ／ｐｉｅ／ｌｏｎｇｎａｍｅ＿ｔａｓｔｙ」というＨＳＶＬＩ５５４に対する検索は、エントリ５３２及びエントリ５３６においてチェーン化したハッシュ検索結果を生み出す。ＨＳＶＬＩ５５４の長い文字列「ｌｏｎｇｎａｍｅ＿ｔａｓｔｙ」のハッシュがＨＳＶＬＩ５５２の名称要素「ｌｏｎｇｎａｍｅ」のハッシュと同じ値をもたらすが、転送ハッシュテーブルが「ｌｏｎｇｎａｍｅ＿ｔａｓｔｙ」についてのエントリを含まない場合、この衝突は、挿入プロセス中に検出することができない。この場合、次の検索は、エントリ５３８を生み出し、システムは、結果５３８においてＳＩＤ＝２によって示される文字列を検索し且つ検索された文字列（例えば、「ｌｏｎｇｎａｍｅ」）とパケットメモリからのＨＳＶＬＩ５５４からの名称要素の文字列（例えば、「ｌｏｎｇｎａｍｅ＿ｔａｓｔｙ」）との文字列比較を実行することによって正当性を判定する。システムは、２つの文字列が等しくない旨を判定し、それは、エントリ５３８が一致として返された場合であっても、それは正しくない一致であることを示す。その後、システムは、ＨＳＶＬＩ５５４（例えば、エントリ５３６）についての最長接頭辞一致として以前の一致転送エントリを返すことができる。
【００４１】
ＨＳＶＬＩ５５２に戻ると、システムは、衝突解決及び正当性検査の後に、エントリ５３８が（文字列「ｌｏｎｇｎａｍｅ」のハッシュ値と連結された「４」のハッシュ鍵に基づいて）正確な転送エントリについての結果を含む旨を判定する。エントリ５３８は、システムが短い文字列「ｇｏｏｄ」と連結された「５」のＰＥＩＤを有するハッシュ鍵を有する次の検索についてのＰＥＩＤとして使用する「５」のＥＩＤを含む。この検索は、「６」のＥＩＤと、スロットビットマップと、ＲＩＤとを有する結果を生み出す。ＨＳＶＬＩ５５２において処理されることになるさらなる名称要素が存在しないことから、エントリ５４０についての転送エントリは、最長接頭辞一致を含み、パケットを転送するためにＣＣＮルータによって使用される。
【００４２】
例示的なコンピュータ及び通信システム
図８は、本発明の実施形態にかかるハードウェア支援ハッシュテーブルに基づいて可変長名称を有するパケットの転送を容易とする例示的なコンピュータ及び通信システム８０２を図示している。コンピュータ及び通信システム８０２は、プロセッサ８０４と、メモリ８０６と、記憶装置８０８とを含む。メモリ８０６は、管理されるメモリとして機能する揮発性メモリ（例えば、ＲＡＭ）を含むことができ、１つ以上のメモリプールを記憶するために使用することができる。さらにまた、コンピュータ及び通信システム８０２は、ディスプレイ装置８１０、キーボード８１２及びポインティングデバイス８１４に接続されることができる。記憶装置８０８は、オペレーティングシステム８１６、コンテンツ処理システム８１８及びデータ８３２を記憶することができる。
【００４３】
コンテンツ処理システム８１８は、コンピュータ及び通信システム８０２によって実行されたときに、コンピュータ及び通信システム８０２に本開示に記載された方法及び／又はプロセスを実行させることができる命令を含むことができる。具体的には、コンテンツ処理システム８１８は、コンピュータネットワークを介してＨＳＶＬＩを有するパケットを送受信するための命令を含むことができる（通信機構８２０）。コンテンツ処理システム８１８はまた、転送ハッシュテーブルにおいて最長接頭辞一致検索を実行するための命令を含むことができる（検索機構８２４）。コンテンツ処理システム８１８は、転送ハッシュテーブルにエントリを挿入するための命令を含むことができる（挿入機構８２２）。コンテンツ処理システム８１８は、転送ハッシュテーブルにおける挿入又は検索時に衝突を判定することに応答して、検索衝突を解決するための命令を含むことができる（衝突解決機構８２６）。
【００４４】
コンテンツ処理システム８１８は、さらに、パケットメモリにおける名称要素と文字列テーブルにおけるエントリを比較するための命令を含むことができる（文字列比較機構８２８）。コンテンツ処理システム８１８は、１つのエントリを他のエントリに対してチェーン化するために固有のエントリ識別子を割り当てるための命令を含むことができる（チェーン化機構８３０）。
【００４５】
データ８３２は、本開示に記載された方法及び／又はプロセスによる入力として必要とされるか又は出力として生成される任意のデータを含むことができる。具体的には、データ８３２は、少なくとも、ＨＳＶＬＩを有するパケット；本開示に記載された転送ハッシュテーブル、文字列テーブル及び別個の衝突テーブル；並びに転送ハッシュテーブルにおける各エントリについての親識別子（ＰＥＩＤ）及び固有のエントリ識別子（ＥＩＤ）を記憶することができる。
【００４６】
この詳細な説明に記載されたデータ構造及びコードは、典型的には、コンピュータシステムによって使用するためのコード及び／又はデータを記憶することができる任意の装置又は媒体であり得るコンピュータ読み取り可能な記憶媒体に記憶される。コンピュータ読み取り可能な記憶媒体は、これらに限定されるものではないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスク若しくはディジタルビデオディスク）などの磁気及び光記憶装置、又は、現在知られている若しくは今後開発されるコンピュータ読み取り可能な媒体を記憶することができる他の媒体を含む。
【００４７】
詳細な説明のセクションに記載された方法及びプロセスは、上述したようなコンピュータ読み取り可能な記憶媒体に記憶されることができるコード及び／又はデータとして具体化することができる。コンピュータシステムがコンピュータ読み取り可能な記憶媒体に記憶されたコード及び／又はデータを読み取って実行する場合、コンピュータシステムは、データ構造及びコードとして具現化されてコンピュータ読み取り可能な記憶媒体内に記憶された方法及びプロセスを実行する。
【００４８】
さらにまた、上述した方法及びプロセスは、ハードウェアモジュール又は装置に含めることができる。これらのハードウェアモジュール又は装置は、これらに限定されるものではないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定のソフトウェアモジュール又は特定時間においてコードの一部を実行する専用又は共有プロセッサ、及び、現在知られている若しくは今後開発される他のプログラマブル論理デバイスを含むことができる。ハードウェアモジュール又は装置が起動されると、それらは、それらの内部に含まれる方法及びプロセスを実行する。
【図１】
2016116215.tif 000003
【図２】
2016116215.tif 000004
【図３Ａ】
2016116215.tif 000005
【図３Ｂ】
2016116215.tif 000006
【図４Ａ】
2016116215.tif 000007
【図４Ｂ】
2016116215.tif 000008
【図４Ｃ】
2016116215.tif 000009
【図４Ｄ】
2016116215.tif 000010
【図５】
2016116215.tif 000011
【図６】
2016116215.tif 000012
【図７】
2016116215.tif 000013
【図８】
2016116215.tif 000014